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.