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

## 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

, J. Kleinberg, E. Tardos*Algorithm design*- We will follow slides of this textbook. You do not need to read/access the book.

- (Optional)
, T. Cormen, C.Leiserson, R. Rivest, C. Stein.*Intro to algorithms*

## 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) |