Date | Topic | Slides | Reading |
January 05 | Introduction, Recap. of basic concepts | Section 2.1 and 2.2 | |
January 07 | Introduction, Graph Algorithms | Section 2.1, 2.2, 3.1, 3.2 | |
January 12 | Graph Algorithms: BFS | Section: 3.1, 3.2, 3.4, 3.5 | |
January 14 | Graph Algorithms: BFS, DFS, Strongly Connected Components | Section: 3.1, 3.2, 3.4, 3.5 | |
January 19 | Graph Algorithms: DAG, Strongly Connected Components | Section 3.5 | |
January 21 | Graph Algorithms: Strongly Connected Components (SCC) | Section 3.5 | |
January 26 | Greedy Algorithms: Interval Scheduling, Job Scheduling | Section 4.1 | |
January 28 | Greedy Algorithms: Job Scheduling, Minimum Spanning Tree | Section 4.2, 4.5 | |
January 29 |
Midterm 1
(Midterm)
(Solution) (Section B00: 6:00-7:20pm, PCYNH 109) (Section C00: 6:00-7:20pm, CENTR 113) |
- | - |
February 02 | Greedy Algorithms: Minimum Spanning Tree, Shortest Path | Section 4.5, 4.4 | |
February 04 | Divide and Conquer: Introduction, Merge Sort, Recurrence Relations | Section 5.1 | |
February 09 | Divide and Conquer: Recurrence Relation, Counting Inversions | Section 5.2, 5.3 | |
February 11 | Dynamic Programming: Longest Increasing Subsequence | - | |
February 16 | Dynamic Programming: Longest Common Subsequence, 0-1 Knapsack |
PDF |
- |
February 18 | Dynamic Programming: 0-1 Knapsack, Maximum independent set of tree | Section 6.4 | |
February 23 | Network Flow: Introduction, Ford-Fulkerson | Section 7.1, 7.2 | |
February 25 | Network Flow: Ford-Fulkerson | Section 7.1, 7.2 | |
February 26 |
Midterm 2
(Midterm)
(Solution) (Section B00: 6:00-7:20pm, PCYNH 109) (Section C00: 6:00-7:20pm, CENTR 113) |
- | - |
March 01 | Network Flow: Bipartite Matching, Hall’s Theorem | Section 7.5 | |
March 03 | Network Flow: Team Elimination | Section 7.12 | |
March 08 | Computational Intractability: Polynomial-time reduction | - | |
March 10 | Computational Intractability: NP, NP-complete | - |