CS580 Algorithm design and analysis

10:30 am - 11:20 am, MWF, Lawson Computer Science Bldg B155

Instructors

Prof. Elena Grigorescu, elena-g purdue.edu

Office Hours: Wed 1-2pm LWSN 1209.

TAs:

Young-San Lin: nilnamuh gmail.com

Office Hours: 1:30-2:30 Tue/Th HAAS G50

Minshen Zhu: minshen.zh gmail.com

Office Hours: 2-3pm Mon/Fri HAAS G50

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 (Subject to change)
Four lectures will be cancelled to make up for the evening exams

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