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.