CS 583
Analysis of Algorithms
Required Textbook:
Cormen, Leiserson & Rivest, Introduction to Algorithms, McGraw Hill, 1990Recommended 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