COMP 7/8713 -- Fall 98
Course Homepage
Office: 355 Dunn; Phone: 678-2487;
e-mail: giri@msci.memphis.edu
Office Hours: Tue (11-5); or by Appt.;
ABSOLUTELY NO HOURS ON THURSDAYS
Class Notes:
Assignments
Sample Solution
Click above for a sample solution for
an algorithmic problem. Note that the file is in postscript format.
Homework Assignments
Note that these are postscript files:
TEXTS:
Required Text: "Algorithms", by Cormen, Leiserson, Rivest,
1990 (CLR)
NOTE: If you are buying a new copy at the book store, make
sure you pay a price of approximately $61. If you paid anything more
from the book store on a recent purchase, Mr. Tony Metcaf (sp.?) from
the store has agreed to refund the excess.
Recommended Text: "Approximation Algorithms for NP-hard
Problems", by Dorit Hochbaum, PWS Publishing Co., 1997.
EVALUATION:
- Written homeworks
- Take home exams
- 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