CSE202: Lecture Notes


Date Topic Slides Reading
September 24 Introduction PDF Chapters 1 and 2
September 29 Introduction, Graph algorithms PDF Section 3.1, 3.2, 3.3, 3.4
October 01 Graph algorithms PDF Section 3.1, 3.2, 3.3, 3.4, 3.5, 3.6
October 06 Greedy Algorithms: Interval Scheduling, Fractional Knapsack PDF Section 4.1
October 08 Greedy Algorithms: Fractional Knapsack, Job scheduling PDF Section 4.2
October 13 Greedy algorithms: Minimum Spanning Tree PDF Section 4.5, 4.6
October 15 Greedy algorithms: Minimum Spanning Tree, Shortest Path
Greedy (approximation) algorithms: Set Cover, Minimum Makespan
PDF Section 4.6, 4.4
Section 11.1, 11.2
October 20 Greedy (approximation) algorithms: Minimum Makespan
Divide and conquer: Closest pair of points, Median finding
PDF Section 11.1
Section 5.1, 5.2, 5.3, 5.4. 5.5
October 22 Divide and conquer: Median finding, Fast Fourier Transform (FFT) PDF Section 5.6
October 27 Divide and conquer: Fast Fourier Transform, Master Theorem
Dynamic Programming: Longest increasing subsequence
PDF Section 5.6
October 29 Midterm (Solution) - -
November 03 Dynamic Programming: Longest increasing subsequence, Longest common subsequence PDF
PDF
-
November 05 Dynamic Programming: Floyd-Warshall, 0-1 Knapsack, Travelling Salesperson PDF Section 6.4, 6.8
November 10 Network Flow: Introduction, Ford-Fulkerson PDF Section 7.1, 7.2
November 12 Network Flow: Ford Fulkerson, Scaling Max-flow PDF Section 7.1, 7.2, 7.3
November 17 Network Flow: Edmonds-Karp, Maximum Matching, Hallís Theorem PDF Section 7.5
November 19 Network Flow: Team Elimination, Feasible Circulation,
Image Segmentation
PDF Section 7.7, 7.10, 7.12
November 24 Network Flow: Edge-disjoint path
Computational Intractability: Introduction, Polynomial-time reduction
PDF Section 7.6
Section 8.1, 8.2
November 26 No class: Thanksgiving - -
December 01 Computational Intractability: Polynomial-time reduction, NP, NP-complete PDF Section 8.3, 8.4
December 03 Computational Intractability: NP, NP-complete, NP-hard PDF Section 8.4, 8.5, 8.7
December 10 Final Exam (3-6pm at CENTR 214) - -