CS/ECE 374 - Schedule, Notes, and Handouts

CS/ECE 374: Lecture and Lab Schedule


The calendar below lists the topics of each lecture and lab section for the semester, with links to relevant lecture notes, slides, lecture videos, and lab handouts. Topics for future lectures and labs are subject to change; exam dates are not.

Videos for all lectures are automatically posted to a separate web page at most an hour after each lecture. They will not be added to the schedule page below.

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
Jan 16-20 Administrivia and course goals
Introduction and history; strings
[slides1, slides2]
String induction
[induction notes, more] [solutions]
Languages and regular expressions
[slides]
Regular expressions
[solutions]
Jan 23-27 DFAs, product construction
[Automata Tutor] [slides] DFA Proofs
DFA construction
[solutions]
Non-determinism, NFAs
Jeff's NFA notes
[slides]
DFA product construction
[solutions]
Jan�30-Feb�3 NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
[slides]
DFA/NFA transformation
[solutions]
Proving non-regularity via fooling sets
[slides] [DFA Proofs][Fooling sets guide]
Proving nonregularity
[solutions]
Feb 6-10 Context-free languages and grammars
[slides]
Context-free grammars
[solutions]
Turing machines: history, formal definitions, examples, variations
[slides]
Regular or not?
[solutions]
Feb 13-17 Universal Turing Machine, RAM simulation, P
[UTM slides][complexity slides]
Turing machine design
[solutions]
Optional review for Midterm 1 Optional review for Midterm 1
Midterm 1: Monday, February 20, 7-9pm
Conflict exam: Tuesday, February 21
Feb 20-24 Recursion: Hanoi, mergesort
[slides][solving recurrences]
Hint: Binary search
[solutions]
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides]
Divide and conquer
[solutions]
Feb�27-Mar�3 Backtracking: independent set, longest increasing subsequence
[slides]
Backtracking
[solutions]
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Dynamic programming
[solutions]
Mar 6-10 More DP: Edit Distance, MIS in trees
[slides]
More dynamic programming
[solutions]
CYK Algorithm, Graphs, basic search
[CYK slides, Graph search slides]
Yet even still more dynamic programming
Drop deadline
[solutions]
Mar 13-17 Directed graphs, depth-first search
[slides]
Graph modeling
[solutions]
Catch up lecture
[Graph notes]
Graph modeling
[solutions]
Mar 20-24 Spring break
Mar 27-31 BFS and Shortest Paths
[slides]
Shortest paths
[solutions]
Shortest Paths with Negative Lengths via DP
[slides]
More shortest paths
[solutions]
Apr 3-7 Greedy algorithms
[slides]
Greedy
[solutions]
MST Algorithms
[slides]
Optional review for Midterm 2
Midterm 2: Monday, April 10, 7-9pm
Conflict exam: Tuesday, April 11
Apr 10-14 No lecture in lieu of midterm MST
[solutions]
Undecidability: halting problem, diagonalization, reductions
[slides]
Undecidability via reductions
[solutions]
Apr 17-21 Polynomial time Reductions
[slides]
Self Reductions
[solutions]
NP, NP-Completeness, 3SAT to Independent Set
[slides][helpful video on P vs NP]
NP-hardness proofs
[solutions]
Apr 24-28 More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
NP-Hardness, the final chapter
[solutions]
Undecidability: more reductions, Rice's theorem
[slides]
ICES Forms
Using Rice's Theorem
ICES Forms
[solutions]
May 1-5 Wrap-up and preliminary review for the final exam Review for final Reading Day
Final exam: Monday, May 8th, 7-10pm
Conflict exam: May 9th, 9am-noon