Theory of Computation
Smith Computer Science
Some Notes:
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 1 | ||||
Wed 09/07 | (No prep Yet) | Lecture: Welcome to CSC 250 Lecture Notes 01 | ||
Fri 09/09 | Read the Class Information found here | Lecture: Intro to Logic and Proofs Lecture Notes 02 | Problem Set 1 (Moodle)
Skim through this LaTeX reference tutorial |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 2 | ||||
Mon 09/12 | review the lecture and be ready to solve exercises | Lecture: More Logic and Proofs AND Using Overleaf Lecture Notes 03 | ||
Wed 09/14 | Lecture: Intro to Regular Expressions and Regular Languages Lecture Notes 04 | Problem Set 2 (Moodle) | Problem Set 1 (Moodle) | |
Fri 09/16 | Lecture: More Regular Expressions and Intro to Finite Automata Lecture Notes 05 |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 3 | ||||
Mon 09/19 | Lecture: Practice with Regular Expressions Lecture Notes 06 | |||
Wed 09/21 | Lecture: Finite Automata Lecture Notes 07 | Problem Set 3 | Problem Set 2 (Thursday 11:59 PM) | |
Fri 09/23 | Lecture: DFAs, NFAs, and REs Lecture Notes 08 |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 4 | ||||
Mon 09/26 | Lecture: Non-REs and the Pumping Lemma Lecture Notes 09 | |||
Wed 09/28 | Mountain Day | |||
Fri 09/30 | TBD | Lecture: More on Non-REs and PL + Properties of Regular Languages Lecture Notes 10 |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 5 | ||||
Mon 10/03 | Lecture: Properties of Regular Languages Lecture Notes 11 | Problem Set 4 | Problem Set 3 (Monday 11:59) | |
Wed 10/05 | Lecture: Context-Free Grammars Lecture Notes 12 | |||
Fri 10/07 | Lecture: More CFGs and Intro to Push-Down Automata Lecture Notes 13 + Practice and Review Day |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 6 | ||||
Mon 10/10 | Autumn Recess | |||
Wed 10/12 | Lecture: Intro to Turing Machines Lecture Notes 14 | Problem Set 5 (Due Next Thursday 11:59PM) | ||
Fri 10/14 | Lecture:More on Turing Machines Lecture 15 | Problem Set 4 (Friday 11:59 PM) |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 7 | ||||
Mon 10/17 | Lecture: DecidabilityLecture 16 | |||
Wed 10/19 | Lecture: Decidability Vs Undecidability Lecture Notes 17 | TBD | Problem Set 5 (This day 11:59 PM) | |
Fri 10/21 | Lecture: Undecidability and Reductions Lecture 18 | Problem Set 6 (Due 11-14 11:59 PM) |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 8 | ||||
Mon 10/24 | Lecture: Undecidabile ProblemsLecture 19 | |||
Wed 10/26 | Lecture: Midterm REVIEW Lecture Notes 20 | TAKE-HOME Practice Midterm | ||
Fri 10/28 | Study for practice midterm | Lecture: Midterm PRACTICE Lecture 21 + Review Lecture 22 | TAKE-HOME Practice Midterm |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 9 | ||||
Mon 10/31 | Lecture: Recap: Reductions Lecture Notes 23 | STUDY REDUCTIONS | ||
Wed 11/02 | Lecture: Enumeration Lecture 24 | STUDY REDUCTIONS | ||
Fri 11/04 | Lecture: Mapping Reducibility Lecture 25 | STUDY REDUCTIONS |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 10 | ||||
Mon 11/07 | Lecture: Mapping Reductions and Intro to Rice's Theorem Lecture Notes 26 | |||
Wed 11/09 | Lecture: Rice's Theorem Lecture 27 | TBD | TBD | |
Fri 11/11 | Review Class Lecture 28 | Bring questions / work |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 11 | ||||
Mon 11/14 | Lecture: Intro to Complexity Lecture Notes 29 | Problem Set 6 (Due 11-14 11:59 PM) | ||
Wed 11/16 | Lecture: More on Complexity Lecture 30 | Problem Set 7 (Due 11-22 11:59 PM) | TBD | |
Fri 11/18 | Lecture: Even More on Complexity Lecture 30 |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 12 | ||||
Mon 11/21 | Lecture: NP-Completeness, P v NP, and Poly-Time-Reductions Lecture Notes 32 | Problem Set 7 (Due 11-22 11:59 PM) | ||
Wed 11/23 | Thanksgiving Break | |||
Fri 11/24 | Thanksgiving Break |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 13 | ||||
Mon 11/28 | Lecture: More Poly-Time-Reductions Lecture 33 | |||
Wed 11/30 | Lecture: UnRecognizable Ls and Poly-Time Reductions in NP-C Lecture 34 | |||
Fri 12/02 | Lecture: More Poly-Time Reductions in NP-C Lecture Notes 35 |
Date | Prep | Topic | Issued | Due |
---|---|---|---|---|
Week 14 | ||||
Mon 12/05 | Lecture: Work on Problem Sets Lecture 36 | |||
Wed 12/07 | Lecture: Work on Problem SetsLecture 37 | |||
Wed 12/09 | Lecture: Work on Problem SetsLecture 37 |