SmithLogo

CSC 250

Theory of Computation

Smith Computer Science

Schedule

Some Notes:

Fall 2022

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


Self-Scheduled Midterm ... Friday 10/28 to Sunday 10/29



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