Link Search Menu Expand Document

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 0: Why are we here?

Jan 10, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 1.1, 1.2
More Resources
Sneak Peak at Next Lecture

Lecture 1: Karatsuba's Algorithm & Pseudocode Practice

Jan 12, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
More Resources
Additional Divide & Conquer Algorithm

Lecture 2: Insertion Sort, Proofs, and Formal Big-Oh

Jan 14, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 2.1, 2.2, 2.3, 3.1
Recording
More Resources
Video Resources
Sneak Peak at Next Lecture

Lecture 6: Substitution Method and Selection Problem Intro.

Jan 26, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 4.3, 9.1
Recording
Video Resources

Sneak Peak at Next Lecture

Lecture 7: k-Select Problem and Median Selection

Jan 28, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 9.1, 9.2, 9.3
Recording
Code Resources
Video Resources

Sneak Peak at Next Lecture

Lecture 8: Median of Medians

Jan 31, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Code
Video Resources

Sneak Peak at Next Lecture

Lecture 9: Randomized Algorithms and QuickSort

Feb 02, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 5.1, 5.2, 5.3, 7
Recording
Code
Video Resources

Lecture 10: QuickSort and Non-Comparison Sorts

Feb 04, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 8.1, 8.2
Recording
Code
Additional Reading
Probability Review
Video Resources

Lecture 11: Radix Sort and Wrap-Up

Feb 07, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Code

Video Resources

Lecture 14: Universal Hash Families and Intro to Graphs

Feb 16, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Video Resources
Feb 18, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 22.1, 22.3, 22.4
Recording
Code
Video Resources
Feb 21, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Code
Video Resources
Feb 23, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 22.3, 22.4, 22.5
Recording
Code

-Breadth-First Search

Video Resources

Lecture 18: Strongly Connected Components

Feb 25, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 22.5
Recording
Code

-Strongly Connected Components

Video Resources

Lecture 19: SCCs in Linear Time, Weighed Graphs

Feb 28, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Video Resources

Lecture 20: Midterm Review

Mar 02, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
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?
Practice Midterm

Lecture 21: Midterm Overview

Mar 16, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording

Midterm Overview (Part 2)

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 23: Dynamic Programming I with Bellman Ford

Mar 21, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Video Resources

Lecture 24: Dynamic Programming II with Fibonnaci

Mar 23, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 25.2, 15.1
Recording
Video Resources

Lecture 25: Dynamic Programming III with Floyd-Warshall

Mar 25, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 15.4
Recording

Lecture 26: Dynamic Programmig IV - LCS, Unbounded Knapsack

Mar 28, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 15.4, CLRS 16.1
Recording
Video Resources

Lecture 27: Dynamic Programming V - 0/1 Knapsack, Independent Set

Apr 01, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 16.1, 16.4
Recording
Video Resources

Lecture 28: Activity Selection and Scheduling

Apr 01, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Video Resources

Lecture 29: Quiz Review

Apr 06, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Recording
Quiz Recap

Lecture 33: Max Flows and Mininim Cuts

Apr 20, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Additional Readings

Lecture 34: Max Flow, Minimum Cuts II

Apr 22, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: CLRS 26.1, 26.2, 26.3
Recording
Video Resources

Lecture 35: Deferred Acceptance

Apr 25, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
  • Lecture notes: [PDF][TeX]
  • Slides: [PDF][PPT]
  • Additional reading: N/A
Recording
Video Resources
Additional Readings

Lecture 36: Advanced Topics I

Apr 27, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Video Resources

Lecture 37: P vs NP

Apr 29, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording
Video Resources

Lecture 38: Review I

May 02, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording

Lecture 39: Review II

May 04, 12:00 PM · 12:50 PM (Graham Hall 210; In Person)
Lecture resources
Recording