Lectures

CS/ECE 374 B, Fall 2019

Lecture recordings (except first lecture) are available at Echo 360. You will need to log in with your @illinois.edu email address and AD password to see them.

Aug 27
Lec 1: Course overview; Strings
Strings lecture notes
Scribbles
Slides
Aug 28
Lab 1: induction on strings
Notes on induction
Solutions
Aug 29
Lec 2: Strings, Languages, Regular Expressions
Notes on languages and regular expressions
Slides
Aug 30
Lab 1b: Regular expressions
Solutions
Sep 3
Lec 3: Finish regular expressions, DFAs
Notes on DFAs
Automata tutor
Scribbles
Jupyter notebook (PDF version)
Sep 4
Lab 2: Defining DFAs
Solutions
Sep 5
Lec 4: Formal DFA definitions, Product Construction
Scribbles
Sep 6
Lab 2b: Product Construction
Solutions
Sep 10
Lec 5: Non-deterministic finite automata (NFAs)
NFA notes
Scribbles
Python notebook (PDF version)
Sep 11
Lab 3: NFA construction
Solutions
Sep 12
Lec 6: Equivalence of NFAs, DFAs, and regular expressions
Scribbles
Sep 13
Lab 3b: Regex to NFA to DFA
Solutions
Sep 17
Proving non-regularity via fooling sets
Scribbles
Sep 18
Lab 4: Proving non-regularity
Solutions
Sep 19
Context-free grammars/languages, rewriting systems
Notes on CFLs
Scribbles
Sep 20
Lab 4b: Context-free grammars
Solutions
Sep 24
Models of computation
Scribbles
Sep 25
Lab 5
Solutions
Sep 26
Optional Midterm Review
Notes from reviewing FA18 midterm
Notes from Sunday's review session
Sep 27
Midterm review lab
Sep 30
Midterm 1, 7–9 p.m.
Oct 1
Performance analysis, Recursion
Notes on recursion
Scribbles
Jupyter notebook (PDF)
Oct 2
No lab
Oct 3
Divide and conquer: mergesort, quicksort
Scribbles
Jupyter notebook (PDF)
Oct 4
Binary search lab
Solution
Oct 5
Divide and conquer: Quick Select, Start Karatsuba
Scribbles
Jupyter notebook (PDF)
Oct 6
Lab 7: Karatsuba
Solution
Oct 7
Finish Karatsuba; Backtracking: n queens, subset sum
Notes on backtracking
Scribbles
Jupyter notebook (PDF)
Oct 8
Lab 7: Backtracking
Solution
Oct 15
Performance analysis; Backtracking: text segmentation
Scribbles
Jupyter notebook (PDF)
Oct 16
Lab 8: Performance analysis
Solutions
Oct 17
Dynamic programming
Notes on dynamic programming
Jupyter notebook (PDF)
Oct 18
Lab 8b: Dynamic programming
Solution
Oct 22
More dynamic programming: LCS, subset sum
Lecture by Prof. Kirill Levchenko
Oct 23
Lab 9: More DP
Solutions
Oct 24
DP: Optimal binary search trees
Scribbles
Oct 25
Lab 9b: More DP still
Solution
Oct 29
DP on trees, CYK
Scribbles
Oct 30
Lab 10: DP on trees
Solutions
🎃ct 31
Graph algorithms introduction
Graph algorithm notes
Scribbles
Nov 1
Midterm review lab
Nov 5
Optional review lecture in the morning
Exam 2: 7–9 p.m.
Nov 6
Lab 11: Graph transformation
Solutions
Nov 7
DFS, DAGs, Topological sort, SCC
Notes
Scribbles
Nov 8
Lab 11bis: More graph transformations
Solutions
Nov 12
SCC decomposition. Shortest paths: BFS, DAGs, Dijkstra
Notes
Scribbles
Nov 13
Lab 12: Shortest paths
Solutions
Nov 14
Dijkstra, bidirectional Dijkstra, A*, Bellman-Ford
Scribbles
Nov 15
Lab 12bis: More shortest paths
Solutions
Nov 19
Greedy algorithms: Shortest Job First, Class Scheduling, Gale-Shapley
Readings
Scribbles
Nov 20
Lab 13: Greedy algorithms
Solutions
Nov 21
Finish Gale-Shapley; Reductions, NP-hardness
NP-hardness notes
Scribbles
Gale Shapley notebook (PDF)
Nov 22
Lab 13b: Reductions
Solutions
Nov 25–29
Fall break, no classes, labs, or office hours
Dec 3
NP-hardness: definition, Cook-Levin, reductions: 3SAT, MIS
Scribbles
Dec 4
NP-hardness reductions lab
Solutions
Dec 5
NP-hardness: SAT, max clique, vertex cover, 3-color
Start on undecidability (not on final)
Undeciadability notes (warning: uses Turing machines)
Dec 6
NP-hardness reductions lab #2
Solutions
Dec 10
Undecidability, final review, ICES forms
Dec 11
Final review lab
Dec 17
Final exam: 1:30-4:30 p.m.