Date | Topic | Slides | Reading |
July 26 | Recap. of basic concepts | Section 2.1 and 2.2 | |
July 27 | Recap. of basic concepts | Section 2.1 and 2.2 | |
July 29 | Introduction | Section 2.1 and 2.2 | |
August 02 | Graph Algorithms: BFS | Section: 3.1, 3.2, 3.4, 3.5 | |
August 03 | Graph Algorithms: BFS, DFS | Section: 3.1, 3.2, 3.4, 3.5 | |
August 05 | Graph Algorithms: DAG, Strongly Connected Components (SCC) | Section: 3.5 | |
August 09 | Graph Algorithms: Strongly Connected Components (SCC) | Section: 3.5 | |
August 10 | Greedy Algorithms: Interval Scheduling, Job Scheduling | Section: 4.1 | |
August 12 | Greedy Algorithms: Job Scheduling, Minimum Spanning Tree | Section: 4.2, 4.5 | |
August 16 | Greedy Algorithms: Minimum Spanning Tree | section: 4.5, 4.4 | |
August 17 | Greedy Algorithms: Minimum Spanning Tree, Shortest Path | Section: 4.5, 4.4 | |
August 19 | Greedy Algorithms: Huffman Encoding & Quiz-1 | Section: 4.8 | |
August 23 | Greedy Algorithms: Huffman Encoding | Section: 4.8 | |
August 24 | Greedy (approximation) Algorithms: Set Cover, Minimum Makespan | Section: 11.1, 11.2 | |
August 26 | Review of material & Quiz-2 | - | |
August 27-30 | Minor-I | - | - |
August 31 | Divide and Conquer: Introduction, Closest Pair of Points | Section: 5.1, 5.2, 5.4 | |
September 02 | Divide and Conquer: Closest pair of points, Median finding | Section: 5.4, 5.5 | |
September 06 | Divide and Conquer: Median Finding, Fast Fourier Transform (FFT) | Section: 5.6 | |
September 07 | Divide and conquer: Fast Fourier Transform (FFT) | Section: 5.6 | |
September 09 | Dynamic Programming: Longest Increasing Subsequence, Longest Common Subsequence | - | |
September 12 | Dynamic Programming: Longest Common Subsequence, 0/1 Knapsack |
PDF |
Section: 6.4 |
September 13 | Holiday (no class) | - | - |
September 14 | Holiday (no class) | - | - |
September 16 |
Dynamic Programming: 0/1 Knapsack, Travelling Salesperson Network Flow: Introduction |
Section: 6.4 | |
September 20 | Network Flow: Ford-Fulkerson Algorithm | Section: 7.1, 7.2 | |
September 21 | Network Flow: Ford-Fulkerson Algorithm | Section: 7.1, 7.2 | |
September 23 | Midterm Evaluations (no class) | - | - |
September 27 | Network Flow: Scaling max-flow and Quiz-3 | Section: 7.3 | |
September 28 | Network Flow: Edmonds-Karp, Maximum Matching | Section: 7.5 | |
September 30 | Network Flow: Hall's Theorem, Team Elimination | Section: 7.5, 7.12 | |
October 04 | Network Flow: Team Elimination and Quiz-4 | Section: 7.12 | |
October 05 | Network Flow: Feasible Circulation, Survey Design, Edge-disjoint Paths | Section: 7.6, 7.7, 7.8 | |
October 07-10 | Minor-II | - | - |
October 11 | Holiday (no class) | - | - |
October 12 | Holiday (no class) | - | - |
October 14 | Network Flow: Image Segmentation, Project Selection | Section: 7.10, 7.11 | |
October 18 | Computational Intractability: Introduction, Polynomial-time reduction | Section: 8.1, 8.2 | |
October 19 | Computational Intractability: Polynomial-time reduction | Section: 8.1, 8.2 | |
October 21 | Computational Intractability: NP, NP-complete | Section: 8.3, 8.4 | |
October 25 | Semester break (no class) | - | - |
October 26 | Semester break (no class) | - | - |
October 28 | Semester break (no class) | - | - |
November 01 | Computational Intractability: NP-complete problems | Section: 8.5, 8.6, 8.7, 8.8 | |
November 02 | Computational Intractability: NP-complete problems | Section: 8.5, 8.6, 8.7, 8.8 | |
November 04 | Computational Intractability: NP-complete problems and Quiz-5 | - | |
November 08 | Computational Intractability: NP-complete problems | Section: 8.8 | |
November 09 | Linear Programming: Introduction, ILP | See LP chapter in CLRS | |
November 11 | Linear Programming: Simplex | See LP chapter in CLRS | |
November 15 | Linear Programming: Rounding | - | |
November 16 | Tutorial 15 | - | - |
November 18 | Review of previous year exams and Quiz-6 | - | - |
November 19-24 | Major Exam | - | - |