CS580 Algorithm design and analysis

4:30 pm - 5:45 pm, MW, Lawson Computer Science Bldg B155

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Mon 9:30-10:30 am LWSN 1209.

TAs:

Nima Darivandpour: jdarivan purdue.edu

Office Hours: Mon/Wed 12-1pm, B107

Young-San Lin: nilnamuh gmail.com

Office Hours: Tue/Thr, 4-5pm, B107

Announcements

Welcome to CS 580!

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

Texts
  • Algorithm design

    J. Kleinberg, E. Tardos. Pearson Education.

    Book slides by Kevin Wayne

  • Recommended: Intro to algorithms

    T. Cormen, C.Leiserson, R. Rivest, C. Stein. 3rd edition. 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) or equivalent.

Grading
  • 20% for homework
  • 20% for the midterm 1
  • 20% for the midterm 2
  • 35% for the final
  • 5% for class participation.
Schedule (tentative)
  • Aug. 21 Lecture 1. Solar eclipse day. Introduction. The stable matching problem. HW0 out.
  • Aug. 23Lecture 2. Asymptotic complexity. Review: Basic graph algorithms HW1 out.
  • Aug 28 Lecture 3. Continue basic graph algorithms
  • Aug 30 Lecture 4. Greedy algorithms: scheduling problems
  • Sep 4 Labor day. No class.
  • Sep. 6 Lecture 5. Shortest path
  • Sep. 11 Lecture 6. Minimum Spanning Tree
  • Sep. 13 Lecture 7. Finish Union-Find. Clustering applicattion
  • Sep. 18 Lecture 8.Divide and conquer. Review recursions. Counting inversions.
  • Sep. 20 Lecture 9. Order statistics. Closest pair of points. Integer/Matrix multiplication
  • Sep. 25 Lecture 10. Dynamic Programming
  • Sep. 27 Lecture 11. DP. Bellman-Ford
  • Oct. 2 Lecture 12. Lower bounds: the adversary method
  • Oct. 4 Lecture 13. MIDTERM 1
  • Oct. 9 October break
  • Oct. 11 Lecture 14 Max-flow, Min cut
  • Oct. 16 Lecture 15. Capacity scaling algorithms.
  • Oct. 18 Lecture 16. Applications of flow networks
  • Oct. 23 Lecture 17. Extentions to flow networks
  • Oct. 25 Lecture 18 Intractability. Reductions.
  • Oct 30 Lecture 19. NP completness
  • Nov. 1 Lecture 20. NP completness
  • Nov 6 Lecture 21. NP completness
  • Nov. 8 Lecture 22 PSPACE games. Dealing with NP completness.
  • Nov. 13 Lecture 23 MIDTERM 2
  • Nov. 15 Lecture 24 Approx algorithms
  • Nov. 20 Lecture 25 Approx algorithms
  • Nov. 22 Lecture 26 Thanksgiving break.
  • Nov. 27 Lecture 27 Randomized algorithms. Contention resolution
  • Nov. 29Lecture 28 Randomized min-cut, MAX-3SAT
  • Dec 4 Lecture 29 Approx/randomized algorithms; Chernoff bounds applications.
  • Dec. 6 Lecture 30 Review
  • Wed Dec. 13 FINAL 7-9 pm. In room KRAN G016
webpage designed by Will Perkins. Contact him if you'd like to use this template.