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: TBD @ Haas G50

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.

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.
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. Review: Basic graph algorithms [Read Chapter 2]
  • Jan. 16 Lecture 3 (Slides). Basic graph algorithms
    [Read Chapter 3] Hw 1 Released
  • Jan. 18 Lecture 4. Greedy algorithms: scheduling problems
    [Read Chapter 4.1-4.3]
  • Jan. 23 Lecture 5. Shortest path
    [Read Chapter 4.4]
  • Jan. 25 Lecture 6. Minimum Spanning Tree
    [Read Chapter 4.5-4.6] Homework 1 Due, Homework 2 Released
  • Jan. 30 Lecture 7. Finish Union-Find. Clustering application
    [Read Chapter 4.6-4.7]
  • Feb. 1 Lecture 8.Divide and conquer. Review recursions. Counting inversions. [Read Chapter 5.1-5.4]
  • Feb. 6 Lecture 9. Order statistics. Closest pair of points. Integer/Matrix multiplication [Read Chapter 5.5-5.6] Hw 2 Due, Hw 3 Released
  • Feb. 8 Lecture 10. Dynamic Programming
    [Read Chapter 6.1-6.4]
  • Feb. 13 Lecture 11. DP.
    [Read Chapter 6.5-6.7]
  • Feb. 15 Lecture 12. Bellman-Ford
    [Read Chapter 6.8-6.10] Homework 3 Due
  • Feb. 20 Lecture 13. Max-flow, Min cut
    [Read Chapter 7.1-7.2]
  • Feb. 21 MIDTERM 1. Evening Exam (8pm -10pm) @ MTHW 210
  • Feb. 22 Lecture 14. More Efficient Max-Flow Algorithms.
    [Read Chapter 7.3-7.4]
  • Feb. 27 Lecture 15. Applications of flow networks
    [Read Chapter 7.5-7.12] Hw 4 Released
  • Mar. 1 [No Class]
  • Mar. 6 Lecture 16. Linear Programming and Applications
    [Read Chapter 11.6] Hw 4 Due
  • Mar. 8 Lecture 17. Intractability. Reductions.
    [Read Chapter 8.1-8.2]
  • Mar. 13 No Class. Spring Break.
  • Mar. 15 No Class. Spring Break.
  • Mar. 20 Lecture 18. NP completeness
    [Read Chapter 8.3] Hw 5 Released
  • Mar. 22 Lecture 19. NP completeness
    [Read Chapter 8.4]
  • Mar. 27 Lecture 20. NP completeness
    [Read Chapter 8.9]
  • Mar. 29 Lecture 21. Dealing with NP completeness.
    [Read Chapter 10] Hw 5 Due
  • Apr. 3 Lecture 22. PSPACE games.
    [Read Chapter 9]
  • Apr. 4 MIDTERM 2. Evening Exam (8PM-10PM) @ Math 175
  • Apr. 5 Lecture 23. Lecture 22. Approx algorithms
    [Read Chapter 11.1-11.4]
  • Apr. 10 Lecture 24. Randomized algorithms, Basic probability. Contention resolution [Read Chapter 13.1-13.3 and 13.12] Hw 6 Released
  • Apr. 12 Lecture 25. Randomized algorithms, MAX-3SAT, Quicksort
    [Read Chapter 13.4-13.5]
  • Apr. 17 Lecture 26. Approx/randomized algorithms
    [Read Chapter 13.6-13.8]
  • Apr. 19 Lecture 27. Chernoff bounds applications
    [Read Chapter 13.9-13.11] Hw 6 Due
  • Apr. 24 Lecture 28. Review for Final Exam
  • Apr. 26 [No Class]
  • TBD FINAL EXAM (April 30-May 5)
webpage designed by Will Perkins. Contact him if you'd like to use this template.