01:19:59duration 1 hour 19 minutes
Mar 12 – Tree shaped dynamic programming:…
Mar 12 – Tree shaped dynamic programming: maximum weight independent set in a tree, inclusion in a context-free language
Class recording
Mar 10 — More dynamic programming: word…
Mar 10 — More dynamic programming: word splitting, subset sum
Mar 05 — Dynamic programming: longest…
Mar 05 — Dynamic programming: longest increasing subsequence, longest common subsequence
Mar 03 — Backtracking: maximum independent…
Mar 03 — Backtracking: maximum independent set, longest increasing subsequence
Feb 26 — Divide and conquer: linear-time…
Feb 26 — Divide and conquer: linear-time selection, multiplication
Feb 24 – Recursion: Tower of Hanoi,…
Feb 24 – Recursion: Tower of Hanoi, mergesort, quicksort
01:28:36duration 1 hour 28 minutes
Midterm 1 Practice 3
02:23:59duration 2 hours 23 minutes
Midterm 1 Practice 2
47:28duration 47 minutes 28 seconds
Midterm 1 Practice 1 Part II
01:20:00duration 1 hour 20 minutes
Midterm 1 Practice 1 Part I
Feb 17 — Turing machines
Feb 12 — Context-free grammars and languages
Feb 10 — Language transformations
Feb 5 — NFAs: ε-transitions,…
Feb 5 — NFAs: ε-transitions, equivalence with DFAs and regular expressions
Feb 3 — Proving nonregularity via fooling…
Feb 3 — Proving nonregularity via fooling sets; NFAs: intuition and example
Jan 29 — DFAs: product construction,…
Jan 29 — DFAs: product construction, closure, automatic=regular
Jan 27 — DFAs: intuition, definitions,…
Jan 27 — DFAs: intuition, definitions, examples
Jan 22 — Languages and regular expressions
Jan 20 — Course goals and administrivia;…
Jan 20 — Course goals and administrivia; strings and induction