CSCE 3313 – Algorithms
Syllabus – Fall 2005
General Information
· Time/Location: MWF 11:30 – 12:20 in ENGR 307
· Instructor: Dr. Gordon Beavers, ENGR 314A, 479-575-6040, , http://csce.uark.edu/~beavers, Office Hours: By appointment.
· Required Text: Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2005
· Online Syllabus: http://csce.uark.edu/~beavers
Catalog Description
CSCE 3313 Algorithms – 3 credits – Provides an introduction to formal techniques for analyzing the complexity of algorithms. The course surveys important classes of algorithms used in computer science and engineering. Prerequisite: CSCE 2143 or CSCE 2143 and MATH 2564 or MATH 3103.
Prerequisite Knowledge
Some material in this course requires considerable mathematical maturity as might be acquired from advanced mathematics courses. Discrete mathematics will be used throughout the course. Later chapters will assume knowledge of common data structures and elementary graph theory. Problem sets will require the ability to code in C or C++. This is a difficult course that requires discipline and concentration.
Schedule
Dates / Topic / Reading22 Aug. / Introduction: Some Representative Problems / Chapter 1
29 Aug. / Basics of Algorithm Analysis / Chapter 2
7 Sept. / Graphs / Chapter 3
14 Sept. / Greedy Algorithms / Chapter 4, Sections 1 - 2, and 4 - 6
21 Sept. / Divide and Conquer / Chapter 5, Sections 1 – 4
3 Oct. / Dynamic Programming / Chapter 6, Sections 1 – 4 and 6 - 9
12 Oct / Network Flow / Chapter 7, Sections 1 – 3, 5 -10
19 Oct. / NP and Computational Intractability / Chapter 8
26 Oct. / PSPACE: A Class of Problems beyond NP / Chapter 9, briefly
9 Nov. / Extending the Limits of Tractability / Chapter 10, Sections 1 and 2
16 Nov. / Approximation Algorithms / Chapter 11, Sections 1,2,6, and 8
30 Nov. / Local Search / Chapter 12, Sections 1 - 3
Student Evaluation
· Problem Sets 20% Weekly assignments
· Weekly Quizzes 40% In class, equally weighted
· Final Exam 30% Cumulative
· Class Participation 10%
Since we have an ambitious schedule, you will have to assume responsibility for the mastery of this material. Complete understanding will normally come only with considerable study. Students should expect to spend two hours of individual study for each hour of lecture. Please look over the material before class so that you may ask relevant questions. Should you find that you still have questions after class, or that there is a problem you cannot solve on your own, please write the question down and submit it during a following class.
Your grades on the problems sets, quizzes and the final examination will be based not only on the correctness of your solution, but also on the clarity and precision of your presentation. Discussion of the problems is encouraged, however, problem sets must be completed independently. Please give credit to individuals or other sources from which you have obtained assistance. Class participation will be taken into account in
Course Policies
· Class Attendance – You are responsible for all material covered in class. If you must miss a class, it is your responsibility to get the notes, handouts, assignments, etc. from someone else in class. Class participation grade will reflect attendance in part.
· Academic Honesty – The policy specified in the University of Arkansas Undergraduate Studies Catalog, Academic Regulations, Academic Dishonesty will be followed.
ACM Core Topic Mapping
List and refer to ACM/IEEE knowledge units covered (see ACM/IEE Computing Curriculum 2001 Computer Science Final Report). Core topics are in bold.
45 contact hours
ACM Core Topics / Program Core Target / AlgorithmsDS. Discrete Structures (43 core hours)
DS1. Functions, relations, and sets / 6
DS2. Basic logic / 10
DS3. Proof techniques / 12 / 2
DS4. Basics of counting / 5
DS5. Graphs and trees / 4 / 3
DS6. Discrete probability / 6
PF. Programming Fundamentals (38 core hours)
PF1. Fundamental programming constructs / 9
PF2. Algorithms and problem-solving / 6 / 5
PF3. Fundamental data structures / 14 / 3
PF4. Recursion / 5
PF5. Event-driven programming / 4
AL. Algorithms and Complexity (31 core hours)
AL1. Basic algorithmic analysis / 4 / 3
AL2. Algorithmic strategies / 6 / 6
AL3. Fundamental computing algorithms / 12 / 12
AL4. Distributed algorithms / 3
AL5. Basic computability / 6 / 2
AL6. The complexity classes P and NP / - / 6
AL7. Automata theory / -
AL8. Advanced algorithmic analysis / - / 3
AL9. Cryptographic algorithms / -
AL10. Geometric algorithms / -
AL11. Parallel algorithms / -
AR. Architecture and Organization (36 core hours)
AR1. Digital logic and digital systems / 6
AR2. Machine level representation of data / 3
AR3. Assembly level machine organization / 9
AR4. Memory system organization and architecture / 5
AR5. Interfacing and communication / 3
AR6. Functional organization / 7
AR7. Multiprocessing and alternative architectures / 3
AR8. Performance enhancements / -
AR9. Architecture for networks and distributed systems / -
OS. Operating Systems (18 core hours)
OS1. Overview of operating systems / 2
OS2. Operating system principles / 2
OS3. Concurrency / 6
OS4. Scheduling and dispatch / 3
OS5. Memory management / 5
OS6. Device management / -
OS7. Security and protection / -
OS8. File systems / -
OS9. Real-time and embedded systems / -
OS10. Fault tolerance / -
OS11. System performance evaluation / -
OS12. Scripting / -
NC. Net-Centric Computing (15 core hours)
NC1. Introduction to net-centric computing / 2
NC2. Communication and networking / 7
NC3. Network security / 3
NC4. The web as an example of client-server computing / 3
NC5. Building web applications / -
NC6. Network management / -
NC7. Compression and decompression / -
NC8. Multimedia data technologies / -
NC9. Wireless and mobile computing / -
PL. Programming Languages (21 core hours)
PL1. Overview of programming languages / 2
PL2. Virtual machines / 1
PL3. Introduction to language translation / 2
PL4. Declarations and types / 3
PL5. Abstraction mechanisms / 3
PL6. Object-oriented programming / 10
PL7. Functional programming / -
PL8. Language translation systems / -
PL9. Type systems / -
PL10. Programming language semantics / -
PL11. Programming language design / -
HC. Human-Computer Interaction (8 core hours)
HC1. Foundations of human-computer interaction / 6
HC2. Building a simple graphical user interface / 2
HC3. Human-centered software evaluation / -
HC4. Human-centered software development / -
HC5. Graphical User Interface Design / -
HC6. Graphical User Interface Programming / -
HC7. HCI aspects of multimedia systems / -
HC8. HCI aspects of collaboration and communication / -
GV. Graphics and Visual Programming (3 core hours)
GV1. Fundamental techniques in graphics / 2
GV2. Graphic systems / 1
GV3. Graphic communication / -
GV4. Geometric modeling / -
GV5. Basic rendering / -
GV6. Advanced rendering / -
GV7. Advanced techniques / -
GV8. Computer animation / -
GV9. Visualization / -
GV10. Virtual reality / -
GV11. Computer vision / -
IS. Intelligent Systems (10 core hours)
IS1. Fundamental issues in intelligent systems / 1
IS2. Search and constraint satisfaction / 5
IS3. Knowledge representation and reasoning / 4
IS4. Advanced search / -
IS5. Advanced knowledge representation and reasoning / -
IS6. Agents / -
IS7. Natural language processing / -
IS8. Machine learning and neural networks / -
IS9. AI planning systems / -
IS10. Robotics / -
IM. Information Management (10 core hours)
IM1. Information models and systems / 3
IM2. Database systems / 3
IM3. Data modeling / 4
IM4. Relational databases / -
IM5. Database query languages / -
IM6. Relational database design / -
IM7. Transaction processing / -
IM8. Distributed databases / -
IM9. Physical database design / -
IM10. Data mining / -
IM11. Information storage and retrieval / -
IM12. Hypertext and hypermedia / -
IM13. Multimedia information and systems / -
IM14. Digital libraries / -
SP. Social and Professional Issues (16 core hours)
SP1. History of computing / 1
SP2. Social context of computing / 3
SP3. Methods and tools of analysis / 2
SP4. Professional and ethical responsibilities / 3
SP5. Risks and liabilities of computer-based systems / 2
SP6. Intellectual property / 3
SP7. Privacy and civil liberties / 2
SP8. Computer crime / -
SP9. Economic issues in computing / -
SP10. Philosophical frameworks / -
SE. Software Engineering (31 core hours)
SE1. Software design / 8
SE2. Using APIs / 5
SE3. Software tools and environments / 3
SE4. Software processes / 2
SE5. Software requirements and specifications / 4
SE6. Software validation / 3
SE7. Software evolution / 3
SE8. Software project management / 3
SE9. Component-based computing / -
SE10. Formal methods / -
SE11. Software reliability / -
SE12. Specialized systems development / -
CN. Computational Science (no core hours)
CN1. Numerical analysis / -
CN2. Operations research / -
CN3. Modeling and simulation / -
CN4. High-performance computing / -
TOTAL / 45
Course Outcomes
Course outcomes are capabilities that you expect a student to be able to do upon successful completion of this course.
Outcome 1
Upon the successful completion of this course a student should understand and be able to use
· key mathematical definitions and notations used for analyzing the time and space costs of algorithms;
· basic concepts and algorithms of graph theory;
· four major algorithm design techniques: greedy algorithms, divide and conquer algorithms, dynamic programming, and network flow
· computational intractability results related to the class of NP-complete problems.
More specifically, the student will be able to do the following:
Specific Outcomes / Chapteruse the Gale – Shapley algorithm for the stable matching problem, recognize representative problems from a variety of time complexity classes. / 1
establish upper, lower, and tight asymptotic bounds of functions, find the asymptotic bounds of common functions, and implement linked lists, a priority queue using a heap / 2
implement breadth-first and depth-first search, graph traversal using queues and stacks, test a graph for bipartiteness, determine the strongly connected components of a directed graph, and determine a topological ordering for a DAG / 3
implement the interval scheduling algorithms, scheduling to minimize lateness, Dijkstra’s and Bellman-Ford shortest paths algorithm, and Kruskal’s and Prim’s minimum spanning tree algorithms / Chapter 4 Sections 1-2 and 4-6
analyze and implement the Merge-Sort algorithm, the Count-Inversions algorithm, and the closest pair of points algorithm / Chapter 5 Sections 1-4
analyze and implement the Weighted-Interval-Scheduling, Segmented-Least-Squares, Subset-Sums and Knapsack, Optimal-Alignment, All-Pairs-Shortest-Paths algorithms / Chapter 6 Sections 1-4 and 6-9
analyze and implement the Ford-Fulkerson, the Maximum-Bipartite-Matching, the Edge-Disjoint-Paths algorithms, and extensions to the Maximum Flow Problem / Chapter 7, Sections 1-3, 5-10
carry out polynomial reductions of simple problems,
to efficiently certify that some common problems are in NP and that a given problem is NP-Complete / 8
prove that problem is in PSPACE / 9 briefly
analyze and implement Vetex-Cover, Independent-Set and Maximum-Independent-Set algorithms / Chapter 10 Sections 1-2
analyze and implement Greedy-Load-Balance, Center-Selection, Integer-Program-Vertex-Cover, and Approximate-Knapsack algorithms / Chapter 11 Sections 1,2,6, and 8
implement the Metropolis algorithm and to use simulated annealing / Chapter 12 Sections 1-3
Assessing Course Effectiveness
What do you, the instructor, do to assess the effectiveness of your course? How do you make decisions to change the course? How do you assess how well the course is achieving its outcomes?
· During the semester:
o In class participation, Homework, Quizzes, Final Exam
· At the end of the semester:
o Course Evaluation
o CSCE Outcomes Assessment – begun in Spring 2005
· Other feedback:
o Discussions and feedback from students during the semester
o Feedback from instructors in courses that depend on this course
· At the end of the program (final semester senior year):
o Senior Competency Exam – covers Algorithms, a core course
o Exit Interviews
Program Outcomes
Fill in the table relating your course outcomes to CS program outcomes. Indicate the extent to which each CSCE Program Outcome listed below is related to a course outcome. Use a 5 point scale: 0=not at all, 1=very slight, 2=slight, 3=moderate, 4=significant, 5=highly significant. For any outcome with a score of 4 or 5, identify the course outcomes that relate to the program outcome.
Computer Science Outcomes – Algorithms / Extent / Course Outcome1) Demonstrate proficiency in algorithms, data structures, software design, concepts of programming languages, and computer organization and architecture. / 5 / 1
2) Develop breadth in advanced Computer Science topics that build on the core (Database Management, Operating Systems, Formal Languages). / 2 / 1
3) In a collaborative, team project, analyze, design, and implement a significant software solution to a problem. / 0
4) Compose, test, and document programs in several different programming paradigms. / 3 / 1
5) Have expertise in at least one important programming language. / 4 / 1
6) Be able to use easily several operating systems, computer architectures, and network environments. / 2 / 1
7) Apply knowledge of mathematics and natural science. / 1 / 1
8) Communicate effectively. / 3 / 1
9) Understand the history of computing, the social context of computing, professional and ethical responsibilities, risks and liabilities of computer-based systems, intellectual property, and privacy and civil liberties. / 1 / 1
10) Recognize the need for, and have the ability to engage in life-long learning. / 2 / 1
11) Have knowledge of contemporary issues. / 1 / 1
Computer Engineering Outcomes – Algorithms
A an ability to apply knowledge of mathematics, science, and engineering / 3 / 1
B an ability to design and conduct experiments, as well as to analyze and interpret data / 1 / 1
C an ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability / 4 / 1
D an ability to function on multi-disciplinary teams / 1 / 1
E an ability to identify, formulate, and solve engineering problems / 3 / 1
F an understanding of professional and ethical responsibility / 1 / 1
G an ability to communicate effectively / 3 / 1
H the broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context / 3 / 1
I a recognition of the need for, and an ability to engage in life-long learning / 2 / 1
J a knowledge of contemporary issues / 1 / 1
K (k) an ability to use the techniques, skills, and modern engineering tools necessary for engineering practice. / 4 / 1
The analysis of algorithms relies on mathematical skills developed in discrete mathematics and calculus and thus addresses outcome A. Designing an efficient algorithm to accomplish a specific task often requires analysis, interpretation, and synthesis of known methods, which address outcomes C, and E. Effectively justifying the use of a particular algorithm to accomplish a task requires effective communication and addresses outcome G. Understanding the cost of an algorithm addresses outcome H, while every activity in the class addresses outcome K.