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.

Link to recording of lectures (old lectures).

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
Aug 28
- Sep 1
Adminis+trivia and course goals
Introduction and history; strings
L1: [slides1, slides2]
String induction
[induction notes, more] [solutions]
Languages and regular expressions
L2: [slides]
Regular expressions
Sep 4-8
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
DFA construction
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
DFA product construction
Sep 11-15
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
DFA/NFA transformation
Proving non-regularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides]
Proving nonregularity
Sep 18-22
Context-free languages and grammars
L7: [slides]
Context-free grammars
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Regular or not?
Sep 25-29
Halting and undecidability
Turing machine design
Optional review for Midterm 1 Optional review for Midterm 1
Skillset for midterm 1
Midterm 1: Monday, October 2, 7-9pm
Conflict exam: TBD TBD
Oct 2-6
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Hint: Binary search
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides]
Divide and conquer
Oct 9-13
Backtracking: independent set, longest increasing subsequence
Dynamic programming: splitting strings, longest increasing subsequence
Dynamic programming
Oct 16-20
More DP: Edit Distance, MIS in trees
memoization and edit distance
More dynamic programming
CYK Algorithm, Graphs, basic search
[CYK, Graph search slides]
Yet even still more dynamic programming
Drop deadline
Oct 23-27
Directed graphs, depth-first search
Graph modeling
DFS/Strong connected compoments

[Graph notes]
Graph modeling
Oct 30- Nov 3
BFS and Shortest Paths
Shortest paths
Shortest Paths with Negative Lengths via DP
More shortest paths
Nov 6-10
Greedy algorithms
MST Algorithms
Optional review for Midterm 2
Skillset for midterm 2
Midterm 2: Monday, November 13, 7-9pm
Where + cover page
Conflict exam: Wednesday, November 15, 7-9pm, in SC 1131
Nov 13-17
No lecture in lieu of midterm MST
Undecidability: halting problem, diagonalization, reductions
Undecidability via reductions
Nov 18-26 Give thanks, go on vacation.
Nov 27
- Dec 1
Polynomial time Reductions
Self Reductions
NP, NP-Completeness, 3SAT to Independent Set
[helpful video on P vs NP]
NP-hardness proofs
Dec 4-8
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
NP-Hardness, the final chapter
More more more NP Completeness.
ICES Forms
Using Rice's Theorem
ICES Forms
Dec 11-15
Wrap-up and preliminary review for the final exam Review for final Reading Day
Skill set for final
Final exam: Monday, December 18 8:00-11:00 a.m.
Conflict final: Tuesday, December 19, 10:00-13:00 SC 0216
Some additional notes:
  1. Negating NFA directly is a bad idea.

Some of the lectures in handout format are here.
holydays : academic calendar. Rooms
Last modified: Wed 2017-12-13 16:15:35 UTC 2017 by Sariel Har-Peled