CSE101: Lecture Notes


Date Topic Slides Reading
January 05 Introduction, Recap. of basic concepts PDF Section 2.1 and 2.2
January 07 Introduction, Graph Algorithms PDF Section 2.1, 2.2, 3.1, 3.2
January 12 Graph Algorithms: BFS PDF Section: 3.1, 3.2, 3.4, 3.5
January 14 Graph Algorithms: BFS, DFS, Strongly Connected Components PDF Section: 3.1, 3.2, 3.4, 3.5
January 19 Graph Algorithms: DAG, Strongly Connected Components PDF Section 3.5
January 21 Graph Algorithms: Strongly Connected Components (SCC) PDF Section 3.5
January 26 Greedy Algorithms: Interval Scheduling, Job Scheduling PDF Section 4.1
January 28 Greedy Algorithms: Job Scheduling, Minimum Spanning Tree PDF 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 PDF Section 4.5, 4.4
February 04 Divide and Conquer: Introduction, Merge Sort, Recurrence Relations PDF Section 5.1
February 09 Divide and Conquer: Recurrence Relation, Counting Inversions PDF Section 5.2, 5.3
February 11 Dynamic Programming: Longest Increasing Subsequence PDF -
February 16 Dynamic Programming: Longest Common Subsequence, 0-1 Knapsack PDF
PDF
-
February 18 Dynamic Programming: 0-1 Knapsack, Maximum independent set of tree PDF Section 6.4
February 23 Network Flow: Introduction, Ford-Fulkerson PDF Section 7.1, 7.2
February 25 Network Flow: Ford-Fulkerson PDF 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 PDF Section 7.5
March 03 Network Flow: Team Elimination PDF Section 7.12
March 08 Computational Intractability: Polynomial-time reduction PDF -
March 10 Computational Intractability: NP, NP-complete PDF -