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/Tue 3-4pm Haas G50

Young-San Lin: nilnamuh gmail.com

Office Hours: Wed/Fri 3-4pm 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
  • 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).

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. 22 Lecture 1. Introduction. The stable matching problem. HW0 out.
  • Aug. 24Lecture 2. Asymptotic complexity. Review: Basic graph algorithms HW1 out.
  • Aug 29 Lecture 3. Continue basic graph algorithms
  • Aug 31 Lecture 4. Greedy algorithms: scheduling problems
  • Sep 5 Labor day. No class.
  • Sep. 7 Lecture 5. Shortest path
  • Sep. 12 Lecture 6. Minimum Spanning Tree
  • Sep. 14 Lecture 7. Finish Union-Find. Clustering applicattion
  • Sep. 19 Lecture 8.Divide and conquer. Review recursions. Counting inversions.
  • Sep. 21 Lecture 9. Order statistics. Closest pair of points. Integer/Matrix multiplication
  • Sep. 26 Lecture 10. Dynamic Programming
  • Sep. 28 Lecture 11. DP.
  • Oct. 3 Lecture 12. Bellman-Ford
  • Oct. 5 Lecture 13. Max-flow, Min cut
  • Oct. 10 Lecture 14. October break
  • Oct. 12 MIDTERM 1
  • Oct. 17 Lecture 15. Capacity scaling algorithms.
  • Oct. 19 Lecture 16. Applications of flow networks
  • Oct. 24 Lecture 17. Extentions to flow networks
  • Oct. 26 Lecture 18 Intractability. Reductions.
  • Oct 31 Lecture 19. NP completness
  • Nov. 2 Lecture 20. NP completness
  • Nov 7 Lecture 21. NP completness
  • Nov. 9 Lecture 22 PSPACE games. Dealing with NP completness. Approximation algorithms.
  • Nov. 14 Lecture 23 MIDTERM 2
  • Nov. 16 Lecture 24 Approx algorithms
  • Nov. 21 Lecture 25 Randomized algorithms, Basic probability. Contention resolution
  • Nov. 23 Lecture 26 Thanksgiving break.
  • Nov. 28 Randomized algorithms Randomized min-cut, MAX-3SAT
  • Nov. 30 Approx/randomized algorithms
  • Dec 5 Chernoff bounds applications
  • Dec. 7 Lecture 29 Review
  • Dec. 15 FINAL 7-9pm in MATH 175
webpage designed by Will Perkins. Contact him if you'd like to use this template.