CS580: Algorithm Design, Analysis, and Implementation

Meeting: MWF 8:30am-9:20am, LWSN B151 (since Sep 12)
Instructor: Yi Wu ( LWSN 1169 |wuyi at purdue.edu | 9:30-10:30 Mon, 1:30-2:30 Thu)
TA: Siddharth Tiwary (LWSN B116 TA louge | stiwary at purdue.edu | 10:30-12:30 Thu), Leo Osvald ( LWSN 3133, desk 11 | losvald at purdue.edu | 11:30 - 12:30 Wed)

Course Info

Lecture summaries and clarifications are on the course blog.
Text Book: Following two books are recommended:
Dexter C. Kozen. The Design and Analysis of Algorithms, Springer-Verlag, 1992
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms , 3rd Edition, MIT Press, 2009.

Course Policy , Homework Policy , Grading , Syllabus

Homework

Homework 1, blog post, solution(hard copy due at 9/14 before class)
Homework 2, blog post, solution(hard copy due at 9/28 before class)
Homework 3, blog post solution(hard copy due at 10/26 before class)
Homework 4, blog post,solution(hard copy due at 11/9 before class)
Homework 5, blog post, solution (hard copy due at 11/26 before class)
Homework 6 , optional, blog post,solution (hard copy due at 12/7 before class)

Exam Info

(Dec 13)--Final Exam, closed book, 1pm-3pm, Qual Exam, 3pm-4pm Location Phys 203
Topics in the Final (html)
Sample Final (pdf) Solution (pdf)
Office hour in the final week

Tentative Schedule (Subject to change)

(8/20) -- Asymptotic Analysis (slide) (CLRS 3.1,3.2)
(8/22)-- Recurrence, Multiplying Numbers and Matrices (CLRS 4.2,4.3)
(8/24)-- Quicksort, Linear Time Selection (1) (CLRS 7.4)
(8/27)-- Linear Time Selection (2), (CLRS 9.2, 9.3)
(8/29)-- Treap(1) (Kozen 13, note from avrim)
(8/31)-- Treap(2) (Kozen 13)
(9/3) -- No class at labor day
(9/5) -- Amortized Analysis(1) (CLRS 17, note from Jeff)
(9/7) -- Amortized Analysis(2) (CLRS 17)
(9/10) -- Splay Tree(1)(Kozen 12,note from Daniel)
(9/12) -- Splay Tree(2) (Kozen 12)
(9/14) -- Splay Tree(3) (Kozen 12)
(9/17) -- Binomial Heap(1)(Kozen 8,note from Daniel)
(9/19) -- Binomial Heap(2) (Kozen 8)
(9/21) -- Fibonacci Heap(1) (Kozen 9, CLRS 19)
(9/24) -- Fibonacci Heap(2)(Kozen 9, CLRS 19)
(9/26) -- Fibonacci Heap (3) (Kozen 9, CLRS 19)
(9/28) -- Union Find (Kozen 10, CLRS 21,notes from Jeff)
(10/1) -- The (log*n)-analysis of Union Find
(10/3) -- Review Session
(10/4) --Midterm (pdf), closed book, 8pm-10pm, Location KRAN G016(solution, distribution, survey)
(10/5) -- No class, have a good fall break!
(10/8) -- No class, fall break.
(10/10) -- String Matching by DFA(CLRS 32)
(10/12) -- KMP algorithm (CLRS 32,note from Jeff)
(10/15) -- Approximate string matching and Polynomial Multiplication (note from Santosh)
(10/17) -- FFT(1) (CLRS 30,note from Avrim, note from Jeff)
(10/19) -- FFT(2)
(10/22) -- No Class
(10/24) -- FFT(3)
(10/26) -- Prim's algorithm for MST (MIT course, CLRS 23)
(10/29) -- Greedy algorithm (CLRS 15, note from Shuchi)
(10/31) --Dynamic Programming (1) (CLRS 16)
(11/2) -- Dynamic Programming (2)
(11/5) -- Shortest Path (CLRS 24, 25)
(11/7) -- DFS (CLSR 22)
(11/9) -- Strongly Connected Component (CLRS 22.5).
(11/12) -- Max Flow( note from Luca , note from avrim, CLRS 26, O(mn) algorithm for maxflow)
(11/14) -- Ford-Fulkerson algorithm for Max Flow
(11/16) -- Edmonds-Karp algorithm for Max Flow
(11/19) -- Applications of Max Flow: Matching, disjoint path (note from Jeff)
(11/21) -- No Class
(11/23) -- No Class
(11/26) -- NP-Completeness (1) (note from Jeff, note from Avrim,CLRS 34)
(11/28) -- NP-Completeness (2) (proof that the halting problem is undecidable)
(11/30) -- NP-Completenss (3)
(12/3) -- NP-completeness (4)
(12/5) -- Approximation Algorithms ( note from Jeff )
(12/7) -- Final Review