CS447/CS647/EE667 Computer Algorithms (Fall 2002)
Course Prerequisites: CS344 Algorithms and Data Structures
and (MA211 Foundations or MA346 Applied Algebra and Discrete Mathematics)
Course Contact Information
Instructor: Christino Tamon
Lectures: Monday Wednesday Friday 11am Science Center 344
Office hours: Monday Wednesday 9-11am and Friday 10-11am Science Center 373
Contact: Science Center 373, firstname.lastname@example.org
The main text is
Introduction to Algorithms (second edition)
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2001.
A recommended supplement is
Data Structures and Algorithms in Java (second edition)
by Michael T. Goodrich and Roberto Tamassia, John Wiley, 2001.
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:
- Asymptotic notation for comparing cost measures.
- Tools for dealing with summations and recurrences.
- Design and analysis techniques: dynamic programming, greedy algorithms, and amortized analysis.
- Graph theory and some of its algorithmic problems.
- Rudimentary theory of NP-completeness.
Requirements and Policies
Although attendance is not mandatory, students are responsible for all course materials
covered in lectures and any quizzes 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. Please refer to the Clarkson
University Regulations for more guidelines on academic integrity and related matters.
There is no final exam in this course (pending approval).
- Tests (2): 50% (tentative dates: October 18th and November 29th)
- Assignments and Quizzes: 40%
- Project: 10% (due December 6th)
Tentative Course Schedule
- (Chapters 1,2) Basic divide-conquer and recurrence analysis for MIN-MAX problem.
Lower bounds for comparison-based algorithms (MIN, SORTING, and MIN-MAX).
- (Chapter 3) Asymptotic growth of functions: big-Oh, big-Omega, little-oh, little-omega, and big Theta.
Summations (Appendix A): arithmetic, geometric, Harmonic, bounding by integrals, splitting techniques,
- (Chapter 4) Recurrences: substitution method, recursion tree method, the Master Theorem.
- (Chapter 15) Dynamic Programming: assembly line scheduling, longest common subsequence, matrix chain
multiplication. Small digression: the use of generating functions (Catalan numbers expresses the
combinatorics of counting fully parenthesized expression, full binary trees with certain number of
leaves, and polygon triangulations).
- (Chapter 16) Greedy algorithms: activity selection problem, fractional knapsack.
Minimum spanning tree.
- (Chapter 17) Amortized analysis.
- (Chapters 22, 23, 35) Graph algorithms: BFS & DFS, topological sorting, strongly connected components.
Approximation algorithms for hard graph theoretic problems: vertex cover, TSP.
- (Chapter 34) NP-Completeness.