CS/ECE 374 A (Spring 2020): Schedule, Notes, and Handouts

CS/ECE 374 A (Spring 2020): Lecture and Lab Schedule

The calendar below lists the topics of each lecture and lab section for the semester, with links to relevant chapters in Jeff Erickson's book/lecture notes, slides, and lab handouts. (Links to the slides and lab handouts will be activated as the semester progresses.) Topics for future lectures and labs are subject to change; exam dates are not.

Link to recording of lectures

Week Tuesday Lecture Tue/Wed Lab Thursday Lecture Thu/Fri Lab
Jan 20-24
Administrivia and course goals
Introduction and history; strings
L1: [scribbles]
String induction
[more] [solutions]
Languages and regular expressions
L2: [slides] [annotated slides]
Regular expressions
Jan 27-31
L3: [slides] [annotated slides]
DFA construction
DFA product construction
L4: [slides] [annotated slides]
DFA product construction
Feb 3-7
Non-determinism, NFAs
L5: [slides] [annotated slides]
NFAs continued, equivalence with DFAs and regular expressions
Converting NFA to regex (Sariel's notes)
L6: [slides] [annotated slides] [scribbles]
Regular language transformation
Feb 10-14
Proving non-regularity via fooling sets
L7: [slides] [annotated slides]
Proving non-regularity
Context-free languages and grammars
L8: [slides] [annotated slides]
Context-free grammars
Feb 17-21
Turing machines: history, formal definitions, examples, variations
L9: [slides]
Turing machine design
Optional review for Midterm 1
Optional review for Midterm 1
Midterm 1: Feb 24 Monday 7-9pm, at Foellinger Auditorium (cover page : skillset)
Conflict: Feb 26 Wednesday 7-9pm, at DCL 1310
Feb 24-28
Recursion: Hanoi, mergesort
[slides] [annotated slides] [solving recurrences] [Big-O Notation]
Hint: Binary search
Divide and conquer: linear-time selection, Karatsuba multiplication
[slides] [annotated slides] [recurrence notes] [Big-O Notation]
Divide and conquer
Mar 2-6
Backtracking: independent set, longest increasing subsequence
[slides] [annotated slides]
Dynamic programming: splitting strings, longest increasing subsequence
[slides] [annotated slides]
Dynamic programming
Mar 9-13
More DP: LIS, Edit Distance
[slides] [annotated slides on LIS] [annotated slides on Edit distance]
More dynamic programming
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides] [annotated slides]
Yet even still more dynamic programming
Old drop deadline.
Mar 14-22 Spring break.
Mar 23-27
Graphs, basic search
[slides], [annotated slides]
Graph modeling
DFS/Strong connected compoments
[slides] [annotated slides]
Graph modeling
Mar 30-
Apr 3
BFS and Shortest Paths
[slides] [annotated slides]
Shortest paths
Shortest Paths with Negative Lengths via DP All-Pair-Shortest-Path via DP
[slides] [annotated slides]
More shortest paths
Apr 6-10
Greedy algorithms
[slides] [scribbles]
Optional review for Midterm 2
Optional review for Midterm 2
Midterm 2: Apr 13 Monday 7pm-10pm Central Time (skillset)
Conflict: Apr 14 Tuesday 7am-10am Central Time
Apr 13-17
MST Algorithms
[slides] [scribbles]
Undecidability: halting problem, diagonalization, reductions
[slides] [scribbles]
Undecidability via reductions
Apr 20-24
Polynomial time Reductions
[slides] [scribbles]
Self Reductions
NP, NP-Completeness, 3SAT to Independent Set
[slides] [scribbles]
[helpful video on P vs NP]
NP-hardness proofs
Apr 27
- May 1
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides] [scribbles]
More NP-hardness
More more more NP Completeness.
[slides] [scribbles]
NP-hardness: The final chapter
[(revised) solutions]
May 4-8
Wrap-up and preliminary review for the final exam
Scribbles: [Undecidability] [NPC]
Review for final
New new drop deadline (5/6).
Reading Day
Final exam: May 8 Friday 7pm-11pm Central Time (skillset)
Conflict final: TBA