CS/ECE 374 B: 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, 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
Jan 15-19 Administrivia, strings, and languages
[slides], [string notes], [languages notes (sec. 2.1 & 2.2)]
Preliminaries, Strings, and Languages
[Induction notes]
[More induction notes]
Regular expressions and Introduction to DFAs
[regular expressions notes], [DFA notes (upto sec. 3.5.3)]
Regular expressions and DFA design, [automatatutor]
Jan 22-26 DFAs: correctness proofs, lower bounds
[notes (sec. 3.3, 3.8)], [DFA proof notes]
DFA proofs Nondeterminism: intuition, examples, NFA definitions, equivalence with DFAs [notes] NFA constructions
Jan 29-Feb 2 Equivalence among NFAs, DFAs & Regular Expressions [notes (sec. 4.6, 4.8)] Regular expressions, DFAs, and NFAs Non-regularity [notes (sec. 3.8)], [Infinite Fooling Sets Guide] Regular or not?
Feb 5-9 Context-free grammars
[notes]
Context-free grammars constructions Turing machines: history, definitions, examples, variations and extensions
[notes]
Turing machine design
Feb 12-16 Turing machine variants and Church-Turing thesis
[notes], [CT notes]
Church-Turing thesis Optional review for Midterm 1 (No lecture) Optional review for Midterm 1 (No lab)
Midterm 1, Monday Feb 19, 7-9pm
Conflict Midterm: Tuesday Feb 20
Feb 19-23 Measuring Time, Invariance thesis, Divide and conquer: MergeSort
[notes] [slides]
Jeff's [notes] on recurrences
Chapter 2 of DPV book
Merge Sort and Recurrences Divide and Conquer: Recurrences, Quick sort, Karatsuba's algorithm, Linear selection
[notes] [slides]
Jeff's [notes] on recurrences
Chapter 2 of DPV book
Binary Search
Feb 26-Mar 2 Backtracking, Intro to Dynamic Programming: Fibonacci
[notes]
Backtracking Dynamic Programming: Longest Increasing Subsequence, String Splitting
[notes]
Chapter 6 of DPV book
Dynamic Programming
Mar 5-9 Dynamic Programming: Edit Distance, Max Independent Set in Trees
[notes] [slides]
Chapter 6 of KT book, Chapter 6 of DPV book
Dynamic Programming Greedy Algorithms: techniques, examples
[notes] [slides]
Chapter 4 of KT book, Chapter 5 of DPV book
Greedy Algorithms
Drop deadline
Mar 12-16 Graph search
[notes] [slides]
Chapter 3 of KT book, Chapter 3 of DPV book
Graph modeling Directed graphs, Strong components, DAGs, Topological sort
[Notes] [slides]
Chapter 3 of KT book, Chapter 3 of DPV book
Directed graphs
(End of Midterm 2 material)
Mar 19-23 Spring Break
Mar 26-30 BFS, Single-source shortest paths, Dijkstra
[notes] [slides]
Chapter 4 of DPV book, Chapter 4 of KT book
Shortest Paths
[lab work]
Optional review for Midterm 2 (No lecture) Optional review for Midterm 2 (No lab)
Apr 2-6 Priority Queues, Bellman-Ford and Shortest Paths with negative lengths
[notes] [slides]
Chapter 4 of DPV book, Chapter 6 of KT book
Shortest paths with negative lengths
[lab work]
All-pairs shortest paths, DFA to regular expressions, Minimum spanning tree algorithms
[notes] [slides]
Chapter 5 of DPV book, Chapter 4 of KT book
Minimum spanning trees
[lab work]
Midterm 2 — Monday, April 9, 7–9pm
Conflict exam: Tuesday, April 10
Apr 9-13 MST correctness, Decidability and recursive enumerability
[notes] [slideshow | pdf ]
Closure properties
[lab work]
Reductions, undecidability, and non r.e.-ness
[notes], [reduction notes] [slideshow | pdf ]
Reductions, and undecidability
[lab work]
Apr 16-20 Polynomial-time Reductions
[notes] | [slides]
Chapter 8 of Kleinberg-Tardos
P and NP
[lab work]
NP-Completeness via Reductions
[notes] | [slides]
Chapter 8 of Kleinberg-Tardos
Video on P vs NP
Reductions and NP-completeness
[lab work]
Apr 23-27 More hard problems, Cook-Levin theorem
[notes] [slides]
Chapter 8 of Kleinberg-Tardos, Chapter 7 of Sipser
NP-Completeness proofs
[lab work]
NP-Completeness
[notes] [slides]
More NP-Completeness
[lab work]
ICES Forms
Apr 30-May 4 Wrapup: Tying up loose ends, and course overview
ICES Forms
Review for final Reading Day
Office Hours (Mahesh) 11am to 12:15pm in 3405 Siebel
Office Hours (Mahesh) 11:30am to 1pm in 4403 Siebel
Final exam — Tuesday, May 8, 8–11am
Conflict exam: TBA