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

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
1
Jan 14- 18
Adminis+trivia and course goals
Introduction and history; strings
L1: [slides1, slides2]
Scribbles: A, B.
String induction
[induction notes, more] [solutions]
Languages and regular expressions
L2: [slides]
Scribbles: A, B.
Regular expressions
[solutions]
2
Jan 21-25
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
Scribbles: A, B.
DFA construction
[solutions]
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles: A, B.
DFA product construction
[solutions]
3
Jan 28
-Feb 1
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
Scribbles: A, B.
DFA/NFA transformation
[solutions]
Proving non-regularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides]
Scribbles: A, B.
Proving nonregularity
[solutions]
4
Feb 4-8
Context-free languages and grammars
L7: [slides]
Scribbles: A, B.
Context-free grammars
[solutions]
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Scribbles: A, B.
Regular or not?
[solutions]
5
Feb 11-15
Halting and undecidability
L9: [slides]
Scribbles: A, B.
Turing machine design
[solutions]
Optional review for Midterm 1
Scribbles: A, B.
Optional review for Midterm 1
Skillset for midterm 1
Midterm 1: Monday, February 18, 7-9pm (rooms)
Conflict: Gregory Hall, 213: Wednesday, February 20, 7-9pm.
Cover page
6
Feb 18-22
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
Feb 25
-Mar 1
Backtracking: independent set, longest increasing subsequence
[slides]
Backtracking
[solutions]
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Dynamic programming
[solutions]
8
Mar 4-8
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
More dynamic programming
[solutions]
CYK Algorithm, Graphs, basic search
[CYK, Graph search slides]
Yet even still more dynamic programming
Drop deadline
[solutions]
9
Mar 11-15
Directed graphs, depth-first search
Graph modeling
[solutions]
DFS/Strong connected compoments
[slides]

[Graph notes]
Graph modeling
[solutions]
Mar 16-24 Don't give thanks, go on vacation anyway.
10
Mar 25- 29
BFS and Shortest Paths
[slides]
Shortest paths
[solutions]
Shortest Paths with Negative Lengths via DP
[slides]
More shortest paths
[solutions]
11
Apr 1-5
Greedy algorithms
[slides]
Greedy
[solutions]
MST Algorithms
[slides]
Optional review for Midterm 2
Skillset for midterm 2
Midterm 2: Monday, April 8, 7-9pm
(rooms)

Conflict exam: Wednesday, April 10, 7-9pm, Siebel 1404
12
Apr 8-12
No lecture in lieu of midterm MST
[solutions]
Undecidability: halting problem, diagonalization, reductions
[slides]
Undecidability via reductions
[solutions]
13
Apr 15-19
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
Apr 22-26
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[Slides]
NP-Hardness, the final chapter
[solutions]
More more more NP Completeness.
[slides]
ICES Forms
Using Rice's Theorem
ICES Forms
[solutions]
15
Apr 29
-May 3
Wrap-up and preliminary review for the final exam Review for final Reading Day
Skill set for final
Final exam: TBD TBD.
Conflict final: TBD TBD TBD
Some additional notes:
  1. Negating NFA directly is a bad idea.
  2. Converting DFA/NFA to regular expression. .
  3. Drawing DFAs using Dot.

Some of the lectures in handout format are here.
holydays : academic calendar. Rooms
Last modified: Tue 2019-02-12 16:40:26 UTC 2019 by Sariel Har-Peled