CSW 4231 Analysis of Algorithms I, Comprehensive Exam
Readings
Required textbook:
- T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction
to Algorithms, MIT Press, 1990.
Other reference:
- A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis
of Computer Algorithms, Addison Wesley, 1974.
(Note: does not include approximation algorithms and uses of randomness
in hashing, median selection, and min-cut)
See also additional material on the home page of the
Fall'99 offering.
Syllabus for Fall'99 and Spring'00
- Introduction: models of computation, lower bounds, analysis of algorithms.
- Divide and Conquer: recurrences, max-min,
linear-time median (deterministic and randomized).
- Linear time sorting algorithms.
- Searching: hash tables, balanced search trees, binomial heaps,
Fibonacci heaps.
- Basic Graph algorithms: connected components, topological sort.
- Advanced graph algorithms: max flow, min cut, edge-connectivity,
maximum matching.
- Dynamic Programming: subset sum, knapsack, iterated matrix multiplication,
approximate string matching
- Introduction to NP-completeness
- Algorithms for number-theoretic problems (GCD, modular exponentiation);
RSA encryption, primality testing.
Past Comprehensive Exams
Material From Fall'98
Note that the Fall'98 Syllabus was different:
it did not include Fibonacci heaps and RSA, and it included
approximation algorithms and more examples of divide-and-conquer
algorithms and of greedy algorithms.
Lecture Notes
Slides