Welcome! As the name suggested, in this course, you will learn advanced algorithm design and implementation. Please join Piazza and Gradescope.

Logistics

  • Instructor: Tianhao Wang
  • Location: Thornton Hall E316
  • Time: MoWe 3:30pm - 4:45pm
  • TA: Zhifan Lu
  • Discussion:
  • Office Hour
    • Zhifan: Tu 12pm-1pm and Th 11am-12pm Rice 442, Zoom and by appointment
    • Tianhao: Fri 2pm-3pm Rice 506, Zoom, and by appointment

Grading

  • Six weekly/bi-weekly assignments (30%, 5% each. Submit on Gradescope. You should use the latex template and write on your own.)
  • Midterm (30%)
  • Final (40%)

Textbook

  • Algorithm design, J. Kleinberg, E. Tardos
    • We will follow slides of this textbook. You do not need to read/access the book.
  • (Optional) Intro to algorithms, T. Cormen, C.Leiserson, R. Rivest, C. Stein.

Schedule

Week Dates Monday Wednesday
1 Jan 16 - Jan 20 No Class. Introduction. The stable matching problem.
2 Jan 23 - Jan 27 Asymptotic complexity. Basic graph algorithms, Greedy (coin change, interval scheduling)
3 Jan 30 - Feb 3 Greedy (interval partitioning, lateness, Cache Policies) Greedy (Dijkstra, MST, Prim, Kruskal, Boruvka…)
4 Feb 6 - Feb 10 Minimum Spanning Tree & Clustering applications TA Office Hour for Homework
5 Feb 13 - Feb 17 Divide and conquer. Review recursions. Counting inversions. Order statistics. Closest pair of points. Integer multiplication
6 Feb 20 - Feb 24 Dynamic Programming Dynamic Programming Continued
7 Feb 27 - March 3 Bellman-Ford Midterm
8 March 6 - March 10 Spring Break Spring Break
9 March 13 - March 17 More Efficient Max-Flow Algorithms. Applications of flow networks
10 March 20 - March 24 Linear Programming and Applications Intractability. Reductions.
11 March 27 - March 31 NP completeness NP completeness
12 April 3 - April 7 NP completeness Dealing with NP completeness.
13 April 10 - April 14 PSPACE games. Approx algorithms
14 April 17 - April 21 Randomized algorithms, Basic probability. Randomized algorithms, MAX-3SAT, Quicksort
15 April 24 - April 28 Approx/randomized algorithms Chernoff bounds applications
16 May 1 - May 5 Review for Final Exam (Last Class)