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.

Link to old all lectures: here.

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
1
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
[solutions]
2
Sep 4-8
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
DFA construction
[solutions]
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
DFA product construction
[solutions]
3
Sep 11-15
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
DFA/NFA transformation
[solutions]
Proving non-regularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides]
Proving nonregularity
[solutions]
4
Sep 18-22
Context-free languages and grammars
L7: [slides]
Context-free grammars
[solutions]
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Regular or not?
[solutions]
5
Sep 25-29
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, October 2, 7-9pm
Conflict exam: TBD TBD
6
Oct 2-6
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]
7
Oct 9-13
Backtracking: independent set, longest increasing subsequence
[slides]
Backtracking
[solutions]
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Dynamic programming
[solutions]
8
Oct 16-20
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]
9
Oct 23-27
Directed graphs, depth-first search
[slides]
Graph modeling
[solutions]
Catch up lecture
[Graph notes]
Graph modeling
[solutions]
10
Oct 30- Nov 3
BFS and Shortest Paths
[slides]
Shortest paths
[solutions]
Shortest Paths with Negative Lengths via DP
[slides]
More shortest paths
[solutions]
11
Nov 6-10
Greedy algorithms
[slides]
Greedy
[solutions]
MST Algorithms
[slides]
Optional review for Midterm 2
Midterm 2: Monday, November 13, 7-9pm
, Conflict exam: TBD TBD TBD
12
Nov 13-17
No lecture in lieu of midterm MST
[solutions]
Undecidability: halting problem, diagonalization, reductions
[slides]
Undecidability via reductions
[solutions]
Nov 18-26 Give thanks, go on vacation.
13
Nov 27
- Dec 1
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]
14
Dec 4-8
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]
15
Dec 11-15
Wrap-up and preliminary review for the final exam Review for final Reading Day
Final exam: Monday, December 18 8:00-11:00 a.m.
Conflict exam: TBD, TBD

Some of the lectures in handout format are here.
holydays : academic calendar. Rooms
Last modified: Sun 2017-09-17 15:43:10 UTC 2017 by Sariel Har-Peled