General Lecture Information
Lecture will be held in-person in Graham Hall 210. The course staff wil make an effort to make lecture recordings available. If you cannot attend lecture, it will be broadcast on Zoom. However, lectures are optimized for in-class experience.
Recordings for the lectures will be posted here as part of the Lecture resources when available.
Lectures
Lecture 1: Karatsuba's Algorithm & Pseudocode Practice
Lecture 2: Insertion Sort, Proofs, and Formal Big-Oh
Lecture resources
Recording
More Resources
Video Resources
- Guiding Principles for the Analysis of Algorithms (Section 1.6)
- Asymptotic Notation: The Gist (Section 2.1)
- Big-O Notation (Section 2.2)
- Basic Examples (Section 2.3)
Sneak Peak at Next Lecture
Lecture 3: Asymptotics and Worst-Case Analysis
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 3.1, 3.2
Recording
More Resources
Video Resources
- Big-Omega and Big-Theta Notation (Section 2.4)
- Additional Examples (Section 2.5)
- MergeSort: Motivation and Example (Section 1.4, part 1)
- MergeSort: Pseudocode (Section 1.4, part 2)
- MergeSort: Analysis (Section 1.5)
- The Divide-and-Conquer Paradigm (Section 3.1; part 1 of Section 3.2)
Sneak Peak at Next Lecture
- Master Method: Motivation (Section 4.1)
- Master Method: Formal Statement (Section 4.2)
- Master Method: Six Examples (Section 4.3)
- Proof of the Master Method (Part 1) (Section 4.4, part 1)
- Master Method: Interpretation of the Three Cases (Section 4.4, part 2)
- Proof of the Master Method (Part 2) (Section 4.4, part 3)
Lecture 4: MergeSort and Introduction to Recurrence Relations
Lecture resources
Recording
More Resources
Video Resources
- MergeSort: Motivation and Example (Section 1.4, part 1)
- MergeSort: Pseudocode (Section 1.4, part 2)
- MergeSort: Analysis (Section 1.5)
- The Divide-and-Conquer Paradigm (Section 3.1; part 1 of Section 3.2)
- Master Method: Motivation (Section 4.1)
Sneak Peak at Next Lecture
Lecture 5: Master Theorem
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 4.4, 4.5, 4.6
Recording
Video Resources
- Master Method: Motivation (Section 4.1)
- Master Method: Formal Statement (Section 4.2)
- Master Method: Six Examples (Section 4.3)
- Proof of the Master Method (Part 1) (Section 4.4, part 1)
- Master Method: Interpretation of the Three Cases (Section 4.4, part 2)
- Proof of the Master Method (Part 2) (Section 4.4, part 3)
Sneak Peak at Next Lecture
Lecture 6: Substitution Method and Selection Problem Intro.
Lecture 7: k-Select Problem and Median Selection
Lecture resources
Recording
Code Resources
Video Resources
- Recursion
- Partitioning Around a Pivot Element (Section 5.2)
- Choosing a Good Pivot (Sections 5.3 and 5.4)
Sneak Peak at Next Lecture
Lecture 8: Median of Medians
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 7.1, 9.1, 9.2, 9.3
Recording
Code
Video Resources
- Recursion
- Quick Review of Discrete Probability (Appendix B)
- Partitioning Around a Pivot Element (Section 5.2)
- Choosing a Good Pivot (Sections 5.3 and 5.4)
Sneak Peak at Next Lecture
Lecture 10: QuickSort and Non-Comparison Sorts
Lecture 11: Radix Sort and Wrap-Up
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 8.1, 8.2
Recording
Code
Video Resources
Lecture 12: Self-Balancing BSTs
Lecture resources
Recording
Video Resources
- Binary Search Trees
- Data Structures Overview (Section 10.1)
- Heaps: Operations and Applications (Sections 10.2 and 10.3)
- Heaps: Implementation Details (Section 10.5)
- Balanced Search Trees: Operations and Applications (Sections 11.1 and 11.2)
- Search Trees: Implementation Details (Part 1) (Section 11.3, Part 1)
- Search Trees: Implementation Details (Part 2) (Section 11.3, Part 2)
- Rotations (Section 11.4)
Lecture 14: Universal Hash Families and Intro to Graphs
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 11, CLRS 22.1
Video Resources
Lecture 15: Graph Representations and Depth-First Search
Lecture 16: Applications of Depth-First Search
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 22.2, 22.3, 22.4
Recording
Code
Video Resources
Lecture 18: Strongly Connected Components
Lecture 19: SCCs in Linear Time, Weighed Graphs
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 24.1
Video Resources
Lecture 20: Midterm Review
Lecture resources
Recording
The midterm will take place in-class, in-person, on 3/4 (Friday Lecture). It is a 50-minute exam.
What’s covered?
- Material from Lecture 0 to Lecture 18
- Material from Homework 0 to Homework 5
- Material from Quiz 0 to Quiz 6
Practice Midterm
Lecture 21: Midterm Overview
Lecture resources
Recording
Midterm Overview (Part 2)
- Zoom Part II
- Passcode: r2&yDHQ=
- YouTube Part II
Midterm Corrections
- Due Friday 3/18!
- Return the copy of your exam with your corrections.
- Half-credit for each question fully corrected.
- Midterm Statistics
Lecture 22: Dijkstra's Algorithm
Lecture resources
Recording
Video Resources
- Shortest Paths and Dijkstra’s Algorithm (Sections 9.1 and 9.2, Part 1)
- Dijkstra’s Algorithm: Examples (Section 9.2, Part 2)
- Correctness of Dijkstra’s Algorithm (Section 9.3)
- Implementation and Running Time of Dijkstra’s Algorithm (0:00-4:30) (Section 9.4)
- Speeding Up Dijkstra’s Algorithm With Heaps (4:30-26:27) (Section 10.4)
Lecture 23: Dynamic Programming I with Bellman Ford
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 24.3
Recording
Video Resources
Lecture 26: Dynamic Programmig IV - LCS, Unbounded Knapsack
Lecture 27: Dynamic Programming V - 0/1 Knapsack, Independent Set
Lecture 28: Activity Selection and Scheduling
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 16.1, 16.2, 16.3
Recording
Video Resources
Lecture 30: Activity Selection, Scheduling, and Huffman Coding
Lecture resources
Recording
Video Resources
- Scheduling: Correctness Proof (Part 1) (Section 13.4, Part 1)
- Scheduling: Correctness Proof (Part 2) (Section 13.4, Part 2)
- Scheduling: Correctness Proof (Part 3) (Section 13.4, Part 3)
- Codes (Section 14.1)
- Codes as Trees (Section 14.2)
- Huffman’s Greedy Algorithm (Part 1) (Section 14.3, Part 1)
- Huffman’s Greedy Algorithm (Part 2) (Section 14.3, Part 2)
- Huffman’s Algorithm: Correctness Proof (Part 1) (Section 14.4, Part 1)
- Huffman’s Algorithm: Correctness Proof (Part 2) (Section 14.4, Part 2)
Lecture 31: Minimal Spanning Trees
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 23
Recording
Video Resources
- Minimum Spanning Trees: Problem Definition (Section 15.1)
- Prim’s MST Algorithm (Section 15.2)
- Speeding Up Prim’s Algorithm via Heaps (Part 1) (Section 15.3, Part 1)
- Speeding Up Prim’s Algorithm via Heaps (Part 2) (Section 15.3, Part 2)
- Prim’s Algorithm: Correctness Proof (Part 1) (Section 15.4, Part 1)
- Prim’s Algorithm: Correctness Proof (Part 2) (Section 15.4, Part 2)
Lecture 32: Kruskal's Algorithm and Max Flow
Lecture resources
Recording
Video Resources
- Kruskal’s MST Algorithm (Section 15.5)
- Speeding Up Kruskal’s Algorithm via Union-Find (Part 1) (Section 15.6, Part 1)
- Speeding Up Kruskal’s Algorithm via Union-Find (Part 2) (Section 15.6, Part 2)
- Lazy Unions (Section 15.6, Part 3)
- Kruskal’s Algorithm: Correctness Proof (Section 15.7)
Optional Resources
Lecture 33: Max Flows and Mininim Cuts
Lecture resources
- Weekly Quiz: [Google Form]
- Lecture notes: [PDF][TeX]
- Slides: [PDF][PPT]
- Additional reading: CLRS 26.1, 26.2, 26.3