CS447 Computer Algorithms (Fall 2004)

Course Prerequisites: CS344 Algorithms and Data Structures and (MA211 Foundations or MA346 Applied Algebra and Discrete Mathematics)

Course Contact Information

Instructor: Chris Lynch
Lectures: MWF 11am SC 354
Office hours: MW 2-4pm and F 3-4pm SC 377
Contact: SC 377, clynch@clarkson.edu

Text: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms (2nd ed.) MIT Press (2001).

Topical Outline

This course studies the algorithmic techniques for solving computational problems efficiently. In particular, the following techniques are covered: basic divide-conquer techniques and analysis using recurrences, dynamic programming, greedy methods, and amortized analysis. Some emphasis will be put on graph-theoretic problems and data structures that are relevant to them. Finally, a discussion of the theory of NP-completeness on the limitations of solving problems efficiently will end the course.

Objectives and outcomes

The objective of this course is to learn fundamental algorithmic techniques, to gain the ability to evaluate the efficiency of algorithms, and to understand certain intractability issues concerning hard algorithmic questions.

The specific outcomes are basic knowledge of the following:

Requirements and Policies

Although attendance is not mandatory, students are responsible for all course materials covered in lectures given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. If a student exchanges ideas with another student or gets ideas from another source, then that source must be mentioned on the homework paper. If that is not done, then it is consdidered cheating. Of course it is also considered cheating to copy something even if the source is referenced. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

Grading Scheme

There is no final exam in this course (pending approval).

Tentative Course Schedule

  1. (Chapters 1,2) Analyzing efficiency of loops. Divide-conquer and recurrence analysis for recursive programs.
  2. (Chapter 3) Asymptotic growth of functions: big-Oh, big-Omega, little-oh, little-omega, and big Theta. Summations (Appendix A): arithmetic, geometric, Harmonic, splitting techniques, telescoping sums.
  3. (Chapter 4) Recurrences: substitution method, recursion tree method, the Master Theorem.
  4. (Chapters 6-9) Review of Sorting programs and Analysis of SELECTION problem.
  5. (Chapter 15) Dynamic Programming: assembly line scheduling, longest common subsequence, matrix chain multiplication..
  6. (Chapter 16) Greedy algorithms: activity selection problem, fractional knapsack.
  7. (Chapter 17) Amortized analysis.
  8. (Chapters 22-26) Graph algorithms: basic searches: BFS, DFS. Topological sorting. Strongly connected components. Minimum Spanning Trees (Kruskal & Prim). Single-source Shortest Paths (Dijkstra). All-pairs Shortest Paths: matrix multiplication, Floyd-Warshall. Maximum Flow: Edmonds-Karp algorithm.
  9. (Chapter 32) String Matching.
  10. (Chapter 34) NP-Completeness; efficient reductions: CLIQUE, INDEPENDENT SET, VERTEX COVER.