The calendar below lists the topics of each lecture and lab section for the semester, with links to typeset notes, slides, and scribbles, as well as problem handouts and solutions for each lab. Solutions will be posted on Saturday. Future lecture topics are subject to change. Exam dates are not.
Textbook chapters or lecture notes are available for each lecture, and problem handouts are available for each lab. Lecture videos can be found on Echo360.
| # |
Monday | Tuesday |
Wednesday | Thursday |
Friday |
|
| 1 |
Jan. 20
Martin Luther King Day (No Classes) |
Jan. 21
LEC 1: Adminis+triva &
Introduction & Strings
Slides:
[Intro],
[Strings]
|
Jan. 22
LAB 1a: String Induction
Solution:
[Lab1aSol]
Extra Notes:
[Induction]
|
Jan. 23
LEC 2: Languages & Regular Expressions
Slides:
[Reg.Lang.]
[scribbl]
|
Jan. 24
LAB 1b: Regular Experssions
Solution:
[Lab1bSol]
|
|
| 2 |
Jan. 27
HW 1 Due |
Jan. 28
LEC 3:
DFAs
Slides:
[DFA]
[scribbl]
[ipynb]
|
Jan. 29
LAB 2a: DFAs
Solution:
[Lab2aSol]
|
Jan. 30
LEC 4: DFA Product Construction
Slides:
[DFA]
[scribbl]
[ipynb]
|
Jan. 31
LAB 2b: DFA product construction
Solution:
[Lab2bSol]
|
|
| 3 |
Feb. 3
HW 2 Due |
Feb. 4
LEC 5:
NFAs
Slides:
[NFA] [scribbl]
|
Feb. 5
LAB 3a: NFAs
Solution:
[Lab3aSol]
|
Feb. 6
LEC 6: Equivalence of Regular Exp. NFAs & DFAs
Slides:
[Eq.Reg.NFA.DFA]
[scribbl]
|
Feb. 7
LAB 3b: Reg. Exp. to NFA to DFA
Solution:
[Lab3bSol]
|
|
| 4 |
Feb. 10
HW 3 Due |
Feb. 11
LEC 7:
Proving Non-regularity via fooling sets
Slides:
[Non Reg.]
[scribbl]
|
Feb. 12
LAB 4a: Proving non-regularity
Solution:
[Lab4aSol]
|
Feb. 13
LEC 8: Context Free Languages & Grammar
Slides:
[CFG]
[scribbl]
|
Feb. 14
LAB 4b: Context Free Grammar
Solution:
[Lab4bSol]
|
|
| 5 |
Feb. 17
HW 4 Due |
Feb. 18
LEC 9:
Turing Machines
Bonus content: Mechanized Proofs
Slides:
[TM], [Exta: UTM]
|
Feb. 19
LAB 5a: Language Transformations
Solution:
[Lab5Sol]
|
Feb. 20
Optional Review for Midterm 1
[scribble]
|
Feb. 21
Optional Review for Midterm 1
|
|
|
Midterm 1: Monday, February 24, 7-9pm, ECEB 1002
Conflict Exam: Tuesday, February 25, 7-9pm, ECEB 5034
|
|
| 6 |
Feb. 24
Midterm 1 |
Feb. 25
LEC 10:
Recursion: Hanoi, MergeSort
Slides:
[Recursion]
[scribbl]
|
Feb. 26
LAB 6a: Binary Search
Solution:
[Lab6aSol]
Extra Notes:
[Recurrences]
|
Feb. 27
LEC 11: Divide and Conquer: QuickSelect, Karatsuba Multiplication
Slides:
[Divide Conquer]
[scribbl]
|
Feb. 28
LAB 6b: Divide and Conquer
Solution:
[Lab6bSol]
|
|
| 7 |
Mar. 2
HW 5 Due |
Mar. 3
LEC 12:
Backtracking
Slides:
[Backtrack]
[scribbl] [calibron12.py]
[ipynb]
|
Mar. 4
LAB 7a: Backtracking
Solution:
[Lab7aSol]
|
Mar. 5
LEC 13:Dynamic Programming
Slides:
[DP 1]
[scribbl]
|
Mar. 6
LAB 7b: Dynamic Programming
Solution:
[Lab7bSol]
|
|
| 8 |
Mar. 9
HW 6 Due |
Mar. 10
LEC 14:
More DP
Slides:
[DP 2] [scribbl]
[ipynb]
|
Mar. 11
LAB 8a: More DP
Solution:
[Lab8aSol]
|
Mar. 12
LEC 15: Even More DP
Slides:
[DP 2], [Extra: CYK]
|
Mar. 13
LAB 8b: Still DP
[scribbl]
Solution:
[Lab8bSol]
|
|
|
Spring Break |
|
| 9 |
Mar. 23
HW 7 Due |
Mar. 24
LEC 16:
Graphs Introduction
Slides:
[Graphs]
[scribbl]
[ipynb]
[zoomvideo]
|
Mar. 25
LAB 9a: Graph Modeling
Solution:
[Lab9aSol]
|
Mar. 26
LEC 17: DFS, DAGs, Topological Sort
Slides:
[DFS]
[scribbl] [ipynb]
|
Mar. 27
LAB 9b:DAGs, DFS
Solution:
[Lab9bSol]
|
|
| 10 |
Mar. 30
HW 8 Due |
Mar. 31
LEC 18:
DFS & Strongly Connected Components
Slides:
[DFS]
[scribble] [ipynb]
|
Apr. 1
LAB 10a:Topological Sort, BFS
Solution:
[Lab10aSol]
|
Apr. 2
LEC 19: Shortest Path: BFS, Dijkstra
Slides:
[Shortest Path]
[scribble]
|
Apr. 3
LAB 10b: Shortest Path
Solution:
[Lab10bSol]
|
|
| 11 |
Apr. 6
HW 9 Due |
Apr. 7
LEC 20:
Shortest Path: DP, Bellman Ford
Slides:
[DP Shortest Path]
[scribbl] [ipynb]
|
Apr. 8
LAB 11a: More Shortest Path
Solution:
[Lab11aSol]
|
Apr. 9
Optional Review for Midterm 2
[zoom]
|
Apr. 10
Optional Review for Midterm 2
|
|
|
Midterm 2: Monday, April 13, 9pm (CST) to Wednesday, April 15, 9am (CST), GradeScope
|
|
| 12 |
Apr. 13
Midterm 2 |
Apr. 14
LEC 21:
Greedy Algorithms
Gale-Shapley in newer version
Slides:
[Greedy] [scribbl]
|
Apr. 15
LAB 12a: Greedy Algorithms
Solution:
[Lab12aSol]
|
Apr. 16
LEC 22: Minimum Spanning Trees
Slides:
[MST]
[scribbl]
[zoom]
|
Apr. 17
LAB 12b: MST Algorithms
Solution:
[Lab12bSol]
|
|
| 13 |
Apr. 20
HW 10 Due |
Apr. 21
LEC 23:
NP, NP-Hardness, Reductions: Independent Set, Cliques, Vertex Cover,
Slides:
[NPC 1]
[scribbl]
|
Apr. 22
LAB 13a: Reductions
Solution:
[Lab13aSol]
|
Apr. 23
LEC 24: Cook-Levin Theorem, Circuit SAT, 3SAT to Indpendent Set
Slides:
[NPC 2]
[scribbl]
|
Apr. 24
LAB 13b:NP-Hardness Reductions
Solution:
[Lab13bSol]
|
|
| 14 |
Apr. 27
|
Apr. 28
LEC 25:
NP-Hardness: 3-Coloring, Hamiltonian Cycle,
Slides:
[NPC 3], [Extra: NPC 4]
[scribbl]
|
Apr. 29
LAB 14a: More NP Hardness
Solution:
[Lab14aSol]
|
Apr. 30
LEC 26: Undecidability: halting problem
Slides:
[Undecidability]
[scribbl]
[zoom video]
|
May. 1
LAB 14b: Undecidability
Solution:
[Lab14bSol]
|
|
| 15 |
May. 4
HW 11 Due |
May. 5
Wrap-up and review for the final exam
|
May. 6
Review for Final Exam
|
May. 7
Reading Day
|
May. 8
|
|
|
Final: Tuesday, May 12, 1:30pm (CST) to Thursday, May 14, 1:30pm (CST), GradeScope
|
|
