CS580 Algorithm Design, Analysis, And Implementation

Lectures

3 PM - 4:15 PM, Tue/Thu, FNY B124

Instructor

Jeremiah Blocki, [jblocki AT purdue]

Office Hours: W/F 11AM to noon

TAs

Akash Kumar: [akash DOT mnnit AT gmail]

Office Hours: Mondays from 10 AM to 12 noon @ LWSN 3133

Hamidreza Amini Khorasgani: [haminikh AT purdue]

Office Hours: Tuesday/Thursday from 1-2PM @ HAAS G50

Announcements

Welcome to CS 580!

Please sign-up on Piazza to ask/answer questions. We will send class announcements through this site.

Syllabus

Texts

Required: Algorithm Design
J. Kleinberg, E. Tardos. Pearson Education.

Book slides by Kevin Wayne
Recommended: Introduction to Algorithms
T. Cormen, C.Leiserson, R. Rivest, C. Stein. MIT

LaTeX resources

Check here for pointers on LaTeX.

Course description
A tentative list of topics includes scheduling problems, minimum spanning tree problems, data compression, network flow, NP and computational intractability, approximation algorithms, randomized algorithms, sublinear algorithms.

Prerequisites: Mathematical maturity. Undergraduate algorithms (CS 381).

Grading

20% for homework
20% for the midterm 1
20% for the midterm 2
35% for the final
5% for class participation.

Academic integrity policy.

Schedule (subject to change)

Jan. 8 Lecture 1 (Slides). Introduction. The stable matching problem.
[Read Chapter 1 of Algorithm Design]. Homework 0 [.tex]
Jan. 10 Lecture 2 (Slides). Asymptotic complexity.
[Read Chapter 2]
Jan. 15 Lecture 3 (Slides). Basic graph algorithms
[Read Chapter 3] Hw 1 Released [.tex]
Jan. 17 Lecture 4 (Slides). Lecture 4. Graph Algorithms Continued
[Read Chapter 4.1-4.3]
Jan. 22 Lecture 5 (Slides). Greedy Algorithms, Shortest Path, Cache Policies
[Read Chapter 4.4]
Jan. 24 Lecture 6. (Slides) Minimum Spanning Tree & Clustering applications
[Read Chapter 4.5-4.6] Homework 1 Due, Hw 2 Released [.tex]
Jan. 29 Lecture 7. (Slides) Divide and conquer. Review recursions. Counting inversions.
[Read Chapter 4.6-4.7]
Jan. 31 Lecture 8. (Slides)Divide and conquer. Review recursions. Counting inversions. [Read Chapter 5.1-5.4]
Feb. 5 Lecture 9. (Slides) Order statistics. Closest pair of points. Integer multiplication [Read Chapter 5.5-5.6] Hw 2 Due, Hw 3 Released [.tex]
Feb. 7 Lecture 10. (Slides) Dynamic Programming
[Read Chapter 6.1-6.4]
Feb. 12 Lecture 11. (Slides) DP.
[Read Chapter 6.5-6.7]
Feb. 14 Lecture 12. (Slides) Bellman-Ford
[Read Chapter 6.8-6.10] Homework 3 Due
Feb. 19 Lecture 13. (slides) Max-flow, Min cut
[Read Chapter 7.1-7.2]
Feb. 20. MIDTERM 1. Evening Exam (8pm -10pm) @ EE 170
Feb. 21 Lecture 14. (slides) More Efficient Max-Flow Algorithms.
[Read Chapter 7.3-7.4]
Feb. 26 Lecture 15. (slides) Applications of flow networks
[Read Chapter 7.5-7.12] Homework 4 Released [.tex]
Feb. 28 Lecture 16. (slides) Linear Programming and Applications
[Read Chapter 11.6]
Mar. 5 [No Class]
Mar. 7 Lecture 17. (slides) Intractability. Reductions.
[Read Chapter 8.1-8.2]
(Homework 4 Due Friday, March 8)
Mar. 12 No Class. Spring Break.
Mar. 14 No Class. Spring Break.
Mar. 19 Lecture 18. (slides) NP completeness
[Read Chapter 8.3] Hw 5 Released [.tex]
Mar. 21 Lecture 19. (slides) NP completeness
[Read Chapter 8.4]
Mar. 26 Lecture 20. (slides) NP completeness
[Read Chapter 8.9]
Mar. 28 Lecture 21. (slides) Dealing with NP completeness.
[Read Chapter 10] Hw 5 Due
Apr. 2 Lecture 22. (slides) PSPACE games.
[Read Chapter 9]
Apr. 3 MIDTERM 2. Evening Exam (8PM-10PM) @ EE 170
Apr. 4 [No Class]
Apr. 9 Lecture 23. (slides) Approx algorithms
[Read Chapter 11.1-11.4]
Apr. 11 Lecture 24. (slides) Randomized algorithms, Basic probability. Contention resolution [Read Chapter 13.1-13.3 and 13.12] Hw 6 Released [.tex]
Apr. 16 Lecture 25. (slides) Randomized algorithms, MAX-3SAT, Quicksort
[Read Chapter 13.4-13.5]
Apr. 18 Lecture 26. (slides) Approx/randomized algorithms
[Read Chapter 13.6-13.8]
Apr. 23 Lecture 27. (slides) Chernoff bounds applications
[Read Chapter 13.9-13.11] Hw 6 Due
Apr. 25 Lecture 28. Review for Final Exam
Apr. 29 FINAL EXAM (8AM-10AM) @ PHYS 223 *

* Important: The final exam is scheduled by the university and the time/date may still be subject to change (within the range April 29 and May 4). See here for the current schedule. If the final exam time conflicts with another course you are taking please let the instructor know as soon as possible so that we can work out an alternative arrangement.