CS580 Algorithm design and analysis

Lectures

10:30 AM - 11:45 AM, Tue/Thu, WANG 2599

Instructor

Jeremiah Blocki, j...@purdue.edu

Office Hours: Wed/Fri 11am-noon @ LWSN 1165.

TAs:

Akash Kumar: a...@purdue.edu

Office Hours: Tuesday, 1PM @ LWSN 3133

Chang Li: l...@purdue.edu

Office Hours: Monday, 11AM-1PM @ 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. 9 Lecture 1 (Slides). Introduction. The stable matching problem.
[Read Chapter 1 of Algorithm Design]. Homework 0
Jan. 11 Lecture 2 (Slides). Asymptotic complexity. [Read Chapter 2]
Jan. 16 Lecture 3 (Slides). Basic graph algorithms
[Read Chapter 3] Hw 1 Released [.tex]
Jan. 18 Lecture 4 (Slides). Lecture 4. Graph Algorithms Continued [Read Chapter 4.1-4.3]
Jan. 23 Lecture 5 (Slides). Greedy Algorithms, Shortest Path
[Read Chapter 4.4]
Jan. 25 Lecture 6. (Slides) Cache Policies, Minimum Spanning Tree
[Read Chapter 4.5-4.6] Homework 1 Due, Hw 2 Released [.tex]
Jan. 30 Lecture 7. (Slides) MST. Clustering application
[Read Chapter 4.6-4.7]
Feb. 1 Lecture 8. (Slides)Divide and conquer. Review recursions. Counting inversions. [Read Chapter 5.1-5.4]
Feb. 6 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. 8 Lecture 10. (Slides) Dynamic Programming
[Read Chapter 6.1-6.4]
Feb. 13 Lecture 11. (Slides) DP.
[Read Chapter 6.5-6.7]
Feb. 15 Lecture 12. (Slides) Bellman-Ford
[Read Chapter 6.8-6.10] Homework 3 Due
Feb. 20 Lecture 13. (slides) Max-flow, Min cut
[Read Chapter 7.1-7.2]
Feb. 21 MIDTERM 1. Evening Exam (8pm -10pm) @ MTHW 210
Feb. 22 Lecture 14. (slides) More Efficient Max-Flow Algorithms.
[Read Chapter 7.3-7.4]
Feb. 27 Lecture 15. (slides) Applications of flow networks
[Read Chapter 7.5-7.12] Homework 4 Released [.tex]
Mar. 1 [No Class]
Mar. 6 Lecture 16. (slides) Linear Programming and Applications
[Read Chapter 11.6]
Mar. 8 Lecture 17. (slides) Intractability. Reductions.
[Read Chapter 8.1-8.2]

Homework 4 Due Friday, March 9)

Mar. 13 No Class. Spring Break.
Mar. 15 No Class. Spring Break.
Mar. 20 Lecture 18. (slides) NP completeness (Guest Lecture: Prof. Maji)
[Read Chapter 8.3] Hw 5 Released [.tex]
Mar. 22 Lecture 19. (slides) NP completeness
[Read Chapter 8.4]
Mar. 27 Lecture 20. (slides) NP completeness
[Read Chapter 8.9]
Mar. 29 Lecture 21. (slides) Dealing with NP completeness.
[Read Chapter 10] Hw 5 Due
Apr. 3 Lecture 22. (slides) PSPACE games.
[Read Chapter 9]
Apr. 4 MIDTERM 2. Evening Exam (8PM-10PM) @ Math 175
Apr. 5 Lecture 23. (slides) Approx algorithms
[Read Chapter 11.1-11.4]
Apr. 10 Lecture 24. (slides) Randomized algorithms, Basic probability. Contention resolution [Read Chapter 13.1-13.3 and 13.12] Hw 6 Released [.tex]
Apr. 12 Lecture 25. (slides) Randomized algorithms, MAX-3SAT, Quicksort
[Read Chapter 13.4-13.5]
Apr. 17 Lecture 26. (slides) Approx/randomized algorithms
[Read Chapter 13.6-13.8]
Apr. 19 Lecture 27. (slides) Chernoff bounds applications
[Read Chapter 13.9-13.11] Hw 6 Due
Apr. 24 Lecture 28. Review for Final Exam
Apr. 26 [No Class]
May 3 FINAL EXAM (PHYS 203)
Thursday (8AM-10AM)