Link Search Menu Expand Document
CS 161 (Archived)

General Lecture Information

  • Lectures will be held live on Zoom. The Zoom links can be found on Canvas.
  • Lectures will be recorded and the recordings can be accessed on Canvas.

Lectures

Lecture 1: Why are you here?

Mon, Jan 11, 10:00 am – 11:20 am (Moses)
Lecture resources
Recording

Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort

Wed, Jan 13, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
  • Pre-lecture Python notebook: [Colab] [Zip]
Lecture resources
Recording

Lecture 3: Solving Recurrences and the Master Theorem

Wed, Jan 20, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
  • Lecture notes: [PDF]
  • Slides: [PDF] [PowerPoint]
  • Lecture live notes: [PDF]
  • Additional reading: CLRS 4.3, 4.4, 4.5
Recording

Lecture 4: Median and Selection

Mon, Jan 25, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 5: Randomized Algorithms and QuickSort

Wed, Jan 27, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 6: BucketSort and Lower Bounds for Sorting

Mon, Feb 1, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 7: Binary Search Trees and Red-Black Trees

Wed, Feb 3, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
Lecture resources
  • Lecture notes: [PDF]
  • Slides: [PDF] [PowerPoint]
  • Lecture live notes: [PDF]
  • Additional reading: CLRS 12.1, 12.2, 12.3, 13
Recording

Lecture 8: Hashing

Mon, Feb 8, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 9: Graphs and BFS and DFS

Wed, Feb 10, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
  • Lecture notes: [PDF]
  • Slides: [PDF] [PowerPoint]
  • Python notebook: [Colab] [Zip]
  • Additional reading: CLRS 22.1, 22.2, 22.3, 22.4
Recording

Lecture 10: Strongly Connected Components

Wed, Feb 17, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 11: Dijkstra and Bellman-Ford

Mon, Feb 22, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
  • Lecture notes: [PDF] (added section on amortized time)
  • Slides: [PDF] [PowerPoint]
  • Python notebook: [Colab] [Zip]
  • Additional reading: CLRS 24.1, 24.3
Recording

Lecture 12: Dynamic Programming: Bellman-Ford and Floyd-Warshall

Wed, Feb 24, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 13: More Dynamic Programming: LCS, Knapsack, Independent Set

Mon, Mar 1, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: None this time!
Lecture resources
Recording

Lecture 14: Greedy Algorithms

Wed, Mar 3, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording
Additional problem-solvings

Lecture 15: Minimum Spanning Trees

Mon, Mar 8, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 16: Min Cuts and Karger's Algorithm

Wed, Mar 10, 10:00 am – 11:20 am (Moses)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
Recording

Lecture 17: Max-Flow and the Ford-Fulkerson Algorithm

Mon, Mar 15, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: [PDF]
Lecture resources
  • Lecture notes: [PDF]
  • Slides: [PDF] [PowerPoint]
  • Additional reading: CLRS 26.1, 26.2, 26.3
Recording

Lecture 18: What's next?

Wed, Mar 17, 10:00 am – 11:20 am (Nima)
Pre-lecture resources
  • Pre-lecture exercise: None this time!
Lecture resources

Recording