COMP 7/8713 -- Fall 00
Course Homepage

Instructor: Giri Narasimhan

Office: 355 Dunn; Phone: 678-2487;
e-mail: giri@msci.memphis.edu

Class Notes and Transparencies:

Aug 28: Transparencies
Aug 30: Transparencies
Sep 18: Red-Black Trees: Notes by Hui Chen
Sep 20: Greedy Algorithms: Notes by Ralph Claflin
Sep 25: Dynamic Programming: Notes by Kang Sun
Sep 27: Amortized Complexity: Notes by Bo Guan
Oct 2 : Graphs : Notes by Roman Ilin
Oct 4 : Biconnectivity: Notes by Greg O'Keefe
Oct 9 : FALL BREAK
Oct 11: Minimum Spanning Tree: Notes by Shahidul Pramanik
Oct 16: All-Pairs-Shortest-Paths : Notes by Yang Qing
Oct 18: All-Pairs-Shortest-Paths : Notes by Girish Sheelvant
Oct 23: Bipartite Matching [pdf Version]: Notes by Fabio Gonzalez
Oct 25: NP-Completeness : Notes by Zazil Villanueva
Oct 30: NP-Completeness: Notes by Jenny Wang
Nov 1 : NP-Completeness: Notes by Chien-Ying Wen
Nov 6 : Approximation Algorithms: Notes by Zhongming Yang
Nov 8 : Approximation Algorithms: Notes by Hui Chen
Nov 13: Approximation Algorithms; Geometric Algorithms: Notes by Greg O'Keefe
Nov 15:
Nov 20: Roman Ilin
Nov 22: Planar Point Location: Notes by Jenny Wang
Nov 29:
Dec 4 :
Dec 6 :

Homework Assignments

Homework 1: [pdf version]; Due Sept. 25
Check the typo in problem 1 that is corrected in this version.
Homework 2: [pdf version]; Due Oct. 11
Homework 3: [pdf version]; Due Nov. 8
Homework 4: [pdf version]; Due Nov. 22

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
Semester Project

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)

Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. Garey and D.S. Johnson, 1979 (Publishers: W. H Freeman and Company).
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

COMP 7/8713 -- Fall 00 Course Homepage