CS/ECE 374A fa22: Lecture and Lab Schedule

Recording of live lectures: Mediaspace, Classtranscribe
Old prerecorded lectures: here.

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.

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
Aug 22-26
Adminis+ trivia and course goals
Introduction and history; strings
L1: [slides1, slides2 : scribbles]
String induction
[induction notes, more] [solutions]
Languages and regular expressions
L2: [slides : scribbles]
Regular expressions
Aug 29-Sep 2
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides : scribbles]
DFA construction
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
DFA product construction
[ms : ct]
Sep 5-9
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides : scribbles]
DFA/NFA transformation
Proving non-regularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides : scribbles : h]
Proving non-regularity
Sep 12-16
Context-free languages and grammars
L7: [slides : scribbles]
Context-free grammars [h]
More on Context-free languages and grammars
L7: [slides : scribbles]
Regular or not? [h]
Sep 19-23
Turing machines: history, formal definitions, examples, variations
L8: [slides]

Algorithms for langs
Optional review for Midterm 1
Optional review for Midterm 1
Midterm 1: Monday, September 26, 7pm-9:30pm (details): solution.
Sep 26-30
Recursion: Hanoi, mergesort
[slides : scribbles] [solving recurrences]
Hint: Binary search
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides : scribbles]
Divide and conquer
Oct 3-7
Backtracking: independent set, longest increasing subsequence
[slides : scribbles]
Dynamic programming: splitting strings, longest increasing subsequence
[slides : scribbles]
Dynamic programming
Oct 10-14
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides : scribbles]
More dynamic programming
More dynamic programming, CYK Algorithm
DP via DAGs
[CYK : scribbles] ,
Yet even still more dynamic programming
Drop deadline
Oct 17-21
Graphs, basic search, Directed graphs, depth-first search
[slides : scribbles]
Graph modeling
DFS/Strong connected components
[slides : scribbles]
[Graph notes]
Graph modeling
Oct 24-28
DFS/Strong connected components
[slides : scribbles]
Shortest paths
BFS and Shortest Paths
[slides : scribbles]
More shortest paths
Oct 31 - Nov 4
Shortest Paths with Negative Lengths via DP
[slides : scribbles]
Review sessions for midterm
Fodder: Optional review for Midterm 2
Midterm 2: Monday, November 7, 7pm-9:30pm (details): solution.
Nov 7-11
Vote early and vote often
No discussion in lieu of midterm MST Algorithms
[slides : scribbles]

Nov 14-18
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
Nov 19-27 Definitely give thanks, go on vacation.
Nov 28-Dec 2
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides : scribbles]
NP-Hardness, the final chapter
More more more NP Completeness.
[slides : scribbles]

Self redutions and NPC
Dec 5-9
Wrap-up and preliminary review for the final exam
Review for final READING DAY  
Final exam: Friday, 12/9/22 8-11
Conflict exam. See here.
Study material for the final

Some additional notes:



  1. Negating NFA directly is a bad idea.
  2. Converting DFA/NFA to regular expression. .
  3. Drawing DFAs using Dot.
  4. A list of "useful" NP-Complete problems

Some of the lectures in handout format are here.

holidays : academic calendar.


Last modified: Thu 2022-12-01 22:25:54 UTC 2022 by Sariel Har-Peled