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: Tue 9-10 am LWSN 1209.

TAs:

Young-San Lin nilnamuh gmail.com

Office Hours: Mon 2:30-3:30pm, Wed 9-10 am LWSN B116

Samson Zhou zhou230 purdue.edu

Office Hours: Tue 4-5pm, Fri4-5 LWSN B116

Announcements

Note the shift in the office hrs on Mon

Welcome to CS 580!

Please sign-up on Piazza to ask/answer questions. We will send class announcements through 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, FFT, network flow, linear programming, NP and computational intractability, approximation algorithms, randomized algorithms, sublinear algorithms.

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

Grading
  • 30% for homeworks (6-10 Psets)
  • 30% for the midterm
  • 35% for the final
  • 5% for class participation.
Schedule
  • Aug. 24 Lecture 1. Introduction. The stable matching problem. HW0 out, on Blackboard.
  • Aug. 26Lecture 2. Asymptotic complexity. Review: Basic graph algorithms HW1 out.
  • Aug 31 Lecture 3. Continue basic graph algorithms
  • Sep 2 Lecture 4. Greedy algorithms: scheduling problems HW2 out
  • Sep. 7 Lecture 5. Labor day. No class
  • Sep. 9 Lecture 6. Shortest path, MSTs. HW3 out
  • Sep. 14 Lecture 7. Finish Union-Find. Divide and conquer. Review recursions. Counting inversions
  • Sep. 16 Lecture 8. Closest pair of points. Integer/Matrix multiplication
  • Sep. 21 Lecture 9. Fast Fourier Transform
  • Sep. 23 Lecture 10. Finish FFT, Start Dynamic Programming. HW4 out
  • Sep. 28 Lecture 11. Weighted interval scheduling. LCS. Sequence allignment
  • Sep. 30 Lecture 12. Segmented least squares, Knapsack
  • Oct. 5 Lecture 13. MIDTERM.
  • Oct. 7 Lecture 14. Bellman-Ford
  • Oct. 12 October break.
  • Oct. 14 Lecture 15. Max-flow, Min cut. HW5 out.
  • Oct. 19 Lecture 16. Capacity scaling algorithms.
  • Oct. 21 Lecture 17. Applications of flow networks
  • Oct. 26 Lecture 18 Extentions to flow networks
  • Oct. 28 Lecture 19. Linear programming CLRS Ch 29
  • Nov. 2 Lecture 20. Linear programming Jeff Erickson's notes
  • Nov 4 Lecture 21. Intractability. Reductions. HW 6 out
  • Nov. 9 Lecture 22 NP completness
  • Nov. 11 Lecture 23 NP completness
  • Nov. 16 Lecture 24 NP completness
  • Nov. 18 Lecture 25 PSPACE games. Dealing with NP completness
  • Nov. 23 Lecture 26 Approximation algorithms. HW 7 out
  • Nov. 25 Thanksgiving break. No class
  • Nov. 30 Lecture 27 Local Search
  • Dec 2 Lecture 28 Randomized algorithms, Basic probability. Chernoff bounds. Contention resolution
  • Dec. 7 Lecture 29 Randomized algorithms Randomized min-cut, MAX-3SAT
  • Dec. 9 Lecture 30 Review
  • Dec. 14 QUAL SUPPLEMENT 4-5pm LWSN B155 (usual classroom)
  • Dec. 14 FINAL 7-9 pm WTHR 104
webpage designed by Will Perkins. Contact him if you'd like to use this template.