CSE101: Lecture Notes


Date Topic Slides Reading
September 25 Recap. of basic concepts PDF Section 2.1 and 2.2
September 28 Recap. of basic concepts PDF Section 2.1 and 2.2
September 30 Introduction PDF Section 3.1 and 3.2
October 02 Graph Algorithms PDF Section 3.1 and 3.2
October 05 Graph algorithms: BFS PDF Section 3.1 and 3.2
October 07 Graph algorithms: BFS application (Bipartite graph) PDF Section 3.4
October 09 Graph algorithms: DFS, strongly connected components PDF Section 3.5
October 12 Graph algorithms: DAG, Strongly connected components PDF Section 3.5
October 14 Graph algorithms: Strongly connected components
Greedy algorithms: Introduction
PDF Section 3.5
Section 4.1
October 16 Graph algorithms: Strongly connected components PDF Section 3.5
October 19 Greedy algorithms: Interval scheduling PDF Section 4.1
October 21 Greedy algorithms: Job scheduling PDF Section 4.2
October 23 Midterm 1 (Solution) - -
October 26 Greedy algorithms: Job Scheduling, Minimum Spanning Tree PDF Section 4.5
October 28 Greedy algorithms: Minimum Spanning Tree PDF Section 4.5
October 30 Greedy algorithms: Minimum Spanning Tree, Shortest Path PDF Section 4.5, 4.4
November 02 Greedy algorithms: Shortest path
Divide and conquer: Introduction, Merge Sort
PDF Section 4.4
Section 5.1
November 04 Divide and conquer: Merge sort, recurrence relations PDF Section 5.1, 5.2
November 06 Divide and conquer: Counting inversions PDF Section 5.3
November 09 Dynamic Programming: Longest increasing subsequence PDF -
November 11 No class: Veteranís day - -
November 13 Dynamic Programming: Longest increasing subsequence
Longest common subsequence
PDF -
November 16 Dynamic Programming: Longest common subsequence PDF -
November 18 Dynamic Programming: Longest common subsequence (memoization)
Network Flow: Introduction
PDF
PDF
-
November 20 Midterm 2 (Solution) - -
November 23 Network Flow: Ford-Fulkerson Algorithm PDF Section 7.1, 7.2
November 25 Network Flow: Ford-Fulkerson Algorithm PDF Section 7.1, 7.2
November 27 No class: Thanksgiving - -
November 30 Network Flow: Bipartite matching, Team elimination PDF Section 7.5, 7.12
December 02 Network Flow: Team elimination
Computational Intractability: Polynomial-time reduction
PDF Section 7.12
December 04 Computational Intractability: Polynomial-time reduction PDF -
December 07 Final (Solution) - -