CS/ECE 374: Lecture and Lab Schedule


Zoom link : Recording of live lectures: Mediaspace, Classtranscribe : Prerec lectures


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
1
Aug 24-28
Adminis+ trivia and course goals
Introduction and history; strings
L1: [slides1, slides2]
Scribbles
String induction
[induction notes, more] [solutions]
[pre-recording]
Languages and regular expressions
L2: [slides]
Scribbles
Regular expressions
[solutions]
2
Aug 31-Sep 4
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
Scribbles
DFA construction
[solutions]
[prerecorded]
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles
DFA product construction
[solutions]
[yt : ms : ct]
3
Sep 7-11
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
Scribbles
DFA/NFA transformation
[solutions]
Proving non-regularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides]
Scribbles
Proving nonregularity
[solutions]
4
Sep 14-18
Context-free languages and grammars
L7: [slides]
Scribbles
Context-free grammars
[solutions]
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Scribbles
Regular or not?
[solutions]
5
Sep 21-25
Halting and undecidability
L9: [slides]
Scribbles
Undecidability
[solutions]
Optional review for Midterm 1
Scribbles
Optional review for Midterm 1
Midterm 1: Sunday/Monday, September 27/28 (details (TBD))
6
Sep 28-Oct 2
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Scribbles
Hint: Binary search
[solutions]
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides]
Scribbles
Divide and conquer
[solutions]
7
Oct 5-9
Backtracking: independent set, longest increasing subsequence
[slides]
Scribbles
Backtracking
[solutions]
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Scribbles
Dynamic programming
[solutions]
8
Oct 12-16
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
Scribbles
More dynamic programming
[solutions]
CYK Algorithm, Graphs, basic search
[CYK, Graph search slides]
Scribbles
Yet even still more dynamic programming
Drop deadline
[solutions]
9
Oct 19-23
Directed graphs, depth-first search
Scribbles
Graph modeling
[solutions]
DFS/Strong connected compoments
[slides]
[Graph notes]
Scribbles
Graph modeling
[solutions]
10
Oct 26-30
BFS and Shortest Paths
[slides]
Scribbles
Shortest paths
[solutions]
Shortest Paths with Negative Lengths via DP
[slides]
Scribbles
More shortest paths
[solutions]
11
Nov 2-6
ELECTION DAY
Vote early and vote often
Greedy
[solutions]
Greedy algorithms
[slides]
Scribbles
Fodder: Optional review for Midterm 2
OLD Skillset for midterm 2
Midterm 2: Sunday/Monday, November 8/9
(details TBD : OLD cover page : dead link)
12
Nov 9-13
MST Algorithms
[slides]
Scribbles
MST
[solutions]
No lecture in lieu of midterm Turing Machines?
[solutions]
13
Nov 16-20
Polynomial time Reductions
[slides]
Scribbles
Self Reductions
[solutions]
NP, NP-Completeness, 3SAT to Independent Set
[slides]
Scribbles

[helpful video on P vs NP]
NP-hardness proofs
[solutions]
Nov 21-29 Definitely give thanks, go on vacation.
14
Nov 30-Dec 4
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
Scribbles
NP-Hardness, the final chapter
[solutions]
More more more NP Completeness.
[slides]

Scribbles
Using Rice's Theorem
ICES Forms
[solutions]
15
Dec 7-9
Wrap-up and preliminary review for the final exam
Scribbles
Review for final    
Dec 10 Reading day (Thursday)
OLD Skill set for final
Study material for the final
Final exam: 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.


Last modified: Fri 2020-09-18 02:49:34 UTC 2020 by Sariel Har-Peled