53:04duration 53 minutes 4 seconds
Midterm 2 Practice 1 Part II
01:24:59duration 1 hour 24 minutes
Midterm 2 Practice 1 Part I
Nov 3 — Shortest paths via direct dynamic…
Nov 3 — Shortest paths via direct dynamic programming: Bellman-Ford for real this time, Floyd-Warshall all-pairs shortest paths
Oct 29 —Single-source shortest paths:…
Oct 29 —Single-source shortest paths: DagSSSP, layered "Bellman-Ford"
01:25:00duration 1 hour 25 minutes
Oct 27 — Cycle detection, topological sort;…
Oct 27 — Cycle detection, topological sort; Single-source shortest paths: generic single-source shortest paths, Dijkstra’s algorithm
Oct 22 — Graph layering,…
Oct 22 — Graph layering, WhateverFirstSearch variants, depth-first search
Oct 20 — Graphs: definitions,…
Oct 20 — Graphs: definitions, representations, traversal, reductions
Oct 15 — Tree shaped dynamic programming:…
Oct 15 — Tree shaped dynamic programming: woodcutting, maximum independent set in trees
Oct 13 — Dynamic programming with…
Oct 13 — Dynamic programming with sequences: Edit distance
Oct 8 — Dynamic programming: Fibonacci…
Oct 8 — Dynamic programming: Fibonacci numbers, faster text segmentation
Oct 6 — Divide and conquer: multiplication;…
Oct 6 — Divide and conquer: multiplication; Backtracking: text segmentation
Oct 1 — Divide and conquer: quicksort and…
Oct 1 — Divide and conquer: quicksort and linear time selection
Class recording
Sep 29 — Recursion: Tower of Hanoi and…
Sep 29 — Recursion: Tower of Hanoi and mergesort
02:10:26duration 2 hours 10 minutes
Midterm 1 Practice 3
47:29duration 47 minutes 29 seconds
Midterm 1 Practice 2
01:14:20duration 1 hour 14 minutes
Midterm 1 Practice 1 Part II
Midterm 1 Practice 1 Part I
Sep 22 — Turing machines
Sep 17 — Context-free grammars and languages
Sep 15 — Language transformations
Sep 10 — Proving nonregularity: fooling…
Sep 10 — Proving nonregularity: fooling sets (and closure properties)
Sep 8 — NFAs: ε-transitions,…
Sep 8 — NFAs: ε-transitions, equivalence with DFAs and regular expressions
Sep 3 — DFAs: product construction,…
Sep 3 — DFAs: product construction, closure, automatic=regular; NFAs: intuition and examples
Sep 1 — DFAs: intuition, definitions,…
Sep 1 — DFAs: intuition, definitions, examples