Analysis of Algorithms
CPSC 629, Course Information, Spring 2005
The course CPSC 629 gives an introduction to the analysis of
algorithms. We study several fundamental algorithms and discuss basic
design principles of algorithms. We introduce some mathematical
methods and tools that are useful in the analysis of algorithms. A
brief exposition of complexity theory concludes the course.
The course is a sequel to the undergraduate course CPSC 311.
General Information
Homework
Lecture Notes
Lectures
- W Jan 19 Subtractive Euclidean algorithm
- F Jan 21 Analysis of the Euclidean algorithm
- M Jan 24 Extended GCD, linear Diophantine equations
- W Jan 26 Chinese Remainder Theorem, RSA
- F Jan 28 Factorization: Pollard's ρ-algorithm
- M Jan 31 Factorization: Quadratic sieve
- W Feb 02 Birthday paradox, review, graph algorithms
- Suggested Reading
- M Feb 07 Depth-First Sort, Topological Sort
- F Feb 11 Topological Sort, Strongly connected components
- M Feb 14 Strongly connected components
- W Feb 16 Minimum spanning trees, Kruskal and Prim
- M Feb 21 Greedy algorithms and matroids
- W Feb 23 Generic greedy algorithm, Kruskal's algorithm
- M Feb 28 Greedy algorithms and matroids, Dijkstra's algorithm
- W Mar 02 Transitive hull, all pair shortest path, closed semirings
Required Textbook
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 2nd edition, MIT Press, 2001
This book gives a nice elementary exposition of many algorithms and data structures.
Recommended Books
- Aho, Hopcroft, Ullman: The Design and Analysis of
Algorithms, Addison Wesley, 1974
An excellent exposition of many useful algorithms. Shorter and deeper than CLRS.
- Knuth: The Art of Computer Programming, Volumes 1-3,
Addison Wesley.
This book series gives an encyclopedic treatment by the founder of the analysis of algorithms. A wonderful classic!
- Graham, Knuth, Patashnik: Concrete Mathematics, 2nd edition,
Addison Wesley, 1994
An excellent introduction to mathematical techniques that are useful for the analysis of algorithms.
- Garey, Johnson: Computers and Intractability, Freeman and Company, 1979
A useful compendium of NP-complete problems.
Copyright 2005 by Andreas Klappenecker, Texas A&M University.
Back to Andreas
Klappenecker's home page.