CS 583
Analysis of Algorithms

Required Textbook:
Cormen, Leiserson & Rivest, Introduction to Algorithms, McGraw Hill, 1990

Recommended Textbook:
S. Dasgupta, C.H.Papadimitriou and U.V. Vazirani: Algorithms

Schedule

Date Topic, Handouts Assignments/Due dates
week 1   Introduction and course logistics
  Insertion Sort, Merge Sort, Asymptotic Notation (slides)
  Ch 1, 2, 3
week 2   Solving Recurrences, Masters Theorem (slides)
  Ch 4 (4.1, 4.3-4.5)
week 3   Sorting (Quicksort, Heapsort) (slides)
  Ch 6, 7
week 4   Sorting in Linear time, Order statistics (slides)
  Ch 8, 9
week 5   Advanced Data Structures (slides)
  Ch 11.1-11.4.
week 6   Advanced Data Structures (slides)
 
week 7   Red-Black Trees (slides)
  Ch 13.1-13.4

week 8   Break
 
week 9   Midterm exam
   
week 10, March 27   Connected Comp., MST, Topological Sort, Dijstra's alg. (slides)
  Ch 22.4-5, 23, 24.3
week 11, April 3   Bellman-Ford, All-Pairs-Shortest-Path, Dynamic Prog. (slides)
  Ch 24.1-3, 25.1-2, 15.1-2
week 12, April 10   Dynamic Programming, Greedy Algorithms (slides)
  Ch 15.1-2, 16.1-3
week 13, April 17   Disjoint Sets, Amortized Analysis (slides)
  Ch 21.1-3
week 14 April 25   Max Flow, Bipartitie Matching (slides)   Ch 26
week 15, May 1   Intractability, NP Completeness (slides)  
week 16, May 8   Approximation Algs, Review (slides)  
week 18, May 10   Final Exam