Welcome to algorithms! We have four main sections.
There are also minor units on maxflow, linear programming, greedy algorithms, and randomized and approximation algorithms. It is expected that you read the class notes in parallel with class attendance.
This is subject to change as I realize what takes more or less time.
| No. | Date | Lecture |
|---|---|---|
| L01A | May 18 | Introduction, Big O |
| L01B | May 18 | Master Theorem, MergeSort |
| L02A | May 20 | Arithmetic |
| L02B | May 20 | Lack of Lower Bounds |
| L03A | May 27 | QuickSort |
| L03B | May 27 | Median of Medians |
| L04A | Jun 01 | Fast Fourier Transform |
| L04B | Jun 01 | Closest Pair of Points |
| Jun 01 | Exam 1 | |
| L05A | Jun 03 | DFS |
| L05B | Jun 03 | Applications of DFS |
| L06A | Jun 08 | BFS, Dijkstra’s |
| L06B | Jun 08 | Heaps |
| L07A | Jun 10 | Kruskal’s, Prims, Union-Find |
| L07B | Jun 10 | The Cut Property |
| L08A | Jun 15 | Bellman-Ford, Floyd-Warshall |
| L08B | Jun 15 | Kirchoff’s Matrix Tree Theorem |
| Jun 15 | Exam 2 | |
| L09A | Jun 17 | Dynamic Programming |
| L09B | Jun 17 | Longest Sequences |
| L10A | Jun 22 | Chain Matrix Multiplication |
| L10B | Jun 22 | Knapsack |
| L11A | Jun 24 | Tree DP |
| L11B | Jun 24 | Aliens Trick |
| Jun 24 | Exam 3 | |
| L12A | Jun 29 | NP-completeness |
| L12B | Jun 29 | Satisfiability |
| L13A | Jul 01 | Hard Graph Problems |
| L13B | Jul 01 | Hard Constraint Problems |
| L14A | Jul 06 | 3 Coloring |
| L14B | Jul 06 | Zero Knowledge Proofs |
| L15A | Jul 08 | Hard Puzzles and Games |
| L15B | Jul 08 | Hamiltonian Path |
| Jul 08 | Exam 4 | |
| L16A | Jul 13 | Max Flow Min Cut Theorem |
| L16B | Jul 13 | MFMC Applications |
| L17A | Jul 15 | Linear Programming |
| L17B | Jul 15 | Duality |
| L18A | Jul 20 | Randomized Algorithms |
| L18B | Jul 20 | Randomized Algorithms |
| L19A | Jul 22 | Approximation Algorithms |
| L19B | Jul 22 | FPTAS for Knapsack |
| L20A | Jul 27 | Open Topic |
| L20B | Jul 27 | Open Topic |
Submission of any work not your own will result on a zero on the assignment to a report to OSI, which may incur further sanctions.
As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.