COMP 7/8713 -- Fall 99
Course Homepage
Office: 355 Dunn; Phone: 678-2487;
e-mail: giri@msci.memphis.edu
Class Notes and Transparencies:
Homework Assignments
Sample Solution
Click here for a sample solution.
[Postscript]; [pdf]
TEXTS:
Required Text: "Algorithms", by Cormen, Leiserson, Rivest,
1990 (CLR)
NOTE: If you are buying a new copy, make
sure you pay a price of approximately $61. If you paid anything more
you probably paid too much.
Recommended Text: "Approximation Algorithms for NP-hard
Problems", by Dorit Hochbaum, PWS Publishing Co., 1997.
EVALUATION:
- Written homeworks
- Take home exams
- Class notes or Paper presentation.
- Class participation
PREVIOUS KNOWLEDGE EXPECTED
From CLR: Chapters 1-17, 23, 24
SYLLABUS
- Augmented data structures
- Dynamic Programming and Greedy Algorithms
- Graph Algorithms (Kruskal, Prim, Dijkstra, Floyd-Warshall,
Network Flow)
- Geometric Algorithms (Convex Hull, Problems related to distance,
structure, visibility)
- Time and Space Complexity, Lower Bounds, NP-Completeness
- Approximation Algorithms, Hardness of approximation
- String Matching
- Computational Biology (String problems, Suffix trees)
- Amortized Analysis
- Fibonacci Heaps
- Randomized Algorithms
- Branch-and-Bound algorithms, Exhaustive Search
- Linear Programming and Combinatorial Optimization
- Parametric Search
Other Reference Books (Available in Math Library - Reference
Section)
- Computational Geometry, by de Berg, van Kreveld,
Overmars, Schwazkopf
- Randomized Algorithms, by Motwani and
Raghavan
- Algorithm on Strings, Trees, and Sequences, by Gusfield
- Handbook of Discrete and Computational
Geometry, by Goodman and O'Rourke
- Combinatorial Optimization, by
Papadimitriou and Steiglitz