CS580 Algorithm design and analysis

Tu/Th 10:30-11:45 pm, Felix Haas Hall G066

Instructor

Elena Grigorescu, elena-g purdue.edu

Office Hours: Tue 3:30-5 pm LWSN 1209.

TAs: Leo Osvald (main), losvald purdue.edu.

Office Hours: Fri 10:30-11:30am. LWSN B116D, desk 1.

Akash Kumar (half) akash.mnnit gmail.com

Office Hours: LWSN S3 lab (cube #32) on Mondays from 1:30 PM to 2:30 PM.

Announcements

Akash's office hours are from now on in LWSN S3 lab (cube #32) on Mondays from 1:30 PM to 2:30 PM.

The dealine for hw2 has been extended.

HW1 posted on 8/22. File sligthly modified on 8/23 to add new instruction for it.

Welcome to CS 580!

Please use piazza.com/purdue/fall2013/cs580 to ask/answer questions.

Texts
  • Recommended: Algorithm design

    J. Kleinberg, E. Tardos. Pearson Education.

  • 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 (381).

Grading
  • 35% for homeworks (biweekly Psets)
  • 25% for the midterm
  • 35% for the final
  • 5% for class participation.
Schedule
  • Aug. 20 Lecture 1. Introduction. The stable matching problem.
    Lecture slides. Book slides
  • Aug. 22Lecture 2. Finish Stable matching analysis. Asymptotic complexity.
    HW1 out. Book slides.
  • Aug. 27 Lecture 3. Review: Basic graph algorithms Book slides
  • Aug. 29 Lecture 4. Greedy algorithms: scheduling problems Book slides.
  • Sep. 3 Lecture 5. Greedy algorithms: scheduling (contd.), shortest paths. Book slides.
  • Sep. 5 Lecture 6. Greedy algorithms: Minimum spanning tree. HW2 out. Book slides
  • Sep. 10 Lecture 7. Greedy algorithms: Finish MST.
  • Sep. 12 Lecture 8. Greedy algorithms: Huffman codes. Book slides
  • Sep. 17 Lecture 9. Divide and conquer: Recursions. Counting inversions. Book slides
  • Sep. 19 Lecture 10. Divide and conquer: Closest pair of points.
  • Sep. 24 Lecture 11. Divide and conquer: Integer, matrix, polynomial multiplication. HW3 out. Book slides
  • Sep. 26 Lecture 12. Fast Fourier Transform
  • Oct. 1 Lecture 13. Midterm.
  • Oct. 3 Lecture 14. Midterm discussion. Fun with dynamic programming (lecture by Akash) Ref1 Ref2 Ref3
  • Oct. 8 October break.
  • Oct. 10 Lecture 15. Dynamic Programming: Interval Scheduling, Segmented Least Squares. Book slides . Chapter 6 .
  • Oct. 15 Lecture 16. Dynamic Programming: SLS (contd), Sequence Alignment. Book slides. . HW4 out.
  • Oct. 17 Lecture 17. DP: Subset-Sum, Knapsack.
  • Oct. 22 Lecture 18 DP: Bellman-Ford.
  • Oct. 24 Lecture 19. Max-flow, Min-cut Book slides
  • Oct. 29 Lecture 20. Max-flow Min-cut (contd), Application: Bipartite matching Book slides HW 5 out.
  • Oct. 31 Lecture 21. Application: Disjoint paths
  • Nov. 5 Lecture 22 Extensions to Max flow: demands and lower bounds
  • Nov. 7 Lecture 23 Linear programming Notes.
  • Nov. 12 Lecture 24 LP duality
  • Nov. 14 Lecture 25 Computational intractability: Reductions Books slides HW6 out
  • Nov. 19 Lecture 26 NP completeness Book slides
  • Nov. 21 Lecture 27 NP completeness: Hamiltonian cycle Book slides
  • Nov. 26 Lecture 28 NP completeness: 3D Matching
  • Nov. 28 Thanksgiving. No Class
  • Dec. 3 Lecture 29 Dealing with NP completeness Book slides
  • Dec. 5 Lecture 30 Approximation algorithms, randomized algorithms Book slides
  • Dec. 9 Final exam. 3:30p - 5:30p MSEE B012
  • Dec. 10 Qual Supplement 11am-12pm LWSN B151
webpage designed by Will Perkins. Contact him if you'd like to use this template.