Link Search Menu Expand Document
CS 161 (Archived)

Lectures

Lecture 1: Welcome / Asymptotic Analysis

Mon, Jun 20, 1:30 pm – 3:00 pm
  • Readings (optional): AI(1) Chapter 2.
  • Slides: [PDF]
  • Recording: On Canvas.

Lecture 2: Karatsuba / MergeSort

Wed, Jun 22, 1:30 pm – 3:00 pm
  • Readings (optional): AI(1) Chapter 1.1-1.5.
  • Slides: [PDF]
  • Recording: Two parts, on Canvas:

Lecture 3: k-Select / Radix Sort and the Limits of Sorting

Mon, Jun 27, 1:30 pm – 3:00 pm
  • Readings (optional): AI(1) Chapters 5.6, 6.3, 6.4
  • Slides: [PDF]
  • Recording: On Canvas.

Lecture 4: Randomized Algorithms and QuickSort / Karger's Algorithm

Wed, Jun 29, 1:30 pm – 3:00 pm
  • Readings (optional): AI(1) Chapter 5.1-5.5. Unfortunately, Karger’s Algorithm is not covered in AI.
  • Slides: [PDF]. Note the red text in slides 27-29, which turns the analysis into what it was supposed to be :\
  • Recording: On Canvas.

Lecture 5: Universal Hashing / Bloom Filters

Wed, Jul 6, 1:30 pm – 3:00 pm
  • Readings (optional): AI(2) Chapter 12.1-12.3, 12.5
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 6: Heaps and Priority Queues / Self-Balancing Binary Trees

Fri, Jul 8, 1:30 pm – 3:00 pm
  • Readings (optional): AI(2) Chapters 10.1-10.3, 10.5, 11.1-11.2, 11.4
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 7: Graphs, BFS / Dijkstra's

Wed, Jul 13, 1:30 pm – 3:00 pm
  • Readings (optional): AI(2) Chapters 7, 8.1-8.3, 9
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 8: DFS and Topological Sort / Kosaraju's Algorithm

Fri, Jul 15, 1:30 pm – 3:00 pm
  • Readings (optional): AI(2) Chapter 8.4-8.6
  • Slides:
  • Recording: On Canvas.

Lecture 9: Midterm Review

Wed, Jul 20, 1:30 pm – 3:00 pm

Lecture 10: Bellman-Ford / Dynamic Programming

Mon, Jul 25, 1:30 pm – 3:00 pm
  • Readings (optional): AI(3) Chapters 18.1-2, 16.4
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 11: Edit Distance, Knapsack

Wed, Jul 27, 1:30 pm – 3:00 pm
  • Readings (optional): AI(3) Chapter 16.5.
  • Slides:
  • Recording: On Canvas.

Lecture 12: Spanning Trees / Greedy Algorithms

Mon, Aug 1, 1:30 pm – 3:00 pm
  • Readings (optional): AI(3) Chapters 13, 15.1-15.4.
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 13: Maximum Flow / Bipartite Matching

Wed, Aug 3, 1:30 pm – 3:00 pm
  • Readings (optional): Unfortunately, neither of these topics is covered in AI.
  • Slides: [PDF].
  • Recording: On Canvas.

Lecture 14: Final Review

Wed, Aug 10, 1:30 pm – 3:00 pm