Theory of Computation Peer Instruction Materials

Topics Coverage Summary: Deterministic Finite Auotmata (DFA), Nondeterministic Finite Auomata (NFA), Regular Expressions, Pushdown Auomata (PDA), Context-Free Grammars, Turing Machines, Decidability, Halting Problem, Undecidability, Diagonalization, Reductions, P vs NP.

Number of Questions/Slides Available: 
– Regular languages: 25 questions
– Context-free languages: 21 questions
– Turing machines: 10 questions
– Decidability, undecidability, cardinality, halting problem, diagonalization: 34 questions
– Reductions, polynomial-time reductions, P vs NP: 14 questions

Materials Author: Cynthia Lee, Stanford University
Additional Contributors:
Alex Tsiatas, UCSD
Thérèse Smith, UConn


Sample Peer Instruction Questions (click to enlarge):


Creative Commons License
Slides for Intro. to Theory of Computation Course Lectures by Dr. Cynthia Lee, UCSD is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Based on a work at www.peerinstruction4cs.org.
Permissions beyond the scope of this license may be available at http://www.peerinstruction4cs.org/2012/03/19/theory-of-computation-peer-instruction-materials/.


These materials are divided into 3-hour long lectures. We take a 10-minute break in the middle, so most of these break fairly naturally into 1.5-hour lectures (and I’ve taught it in 1.5-hour format using these materials and it worked well). I can’t speak to the 1-hour lecture scenario.

Lecture01_SyllabusDFAsClosurePropertiesofRegularLangs

Lecture02_NFAsandRegularExpressions

Lecture03_PumpingLemmaandCFGs

Lecture04_PDAsandCFLPumpingLemma

Lecture05_AlanTuringandTuringMachines (python code accompanies this lecture: alphabeticenumerator.py and lexographicenumerator.py)

Lecture06_TMVariantsandEnumeratorsandHilbert

Lecture07_DecidabilityandDiagonalizationandCardinality

Lecture08_ATMUndecidableandHaltingProbandReductions

Lecture09_ReductionsFromATMandPvNP

Lecture10_FinalReview

These are additional materials:

–Instructor’s guide to understanding the pedagogical strategy behind the DFA introduction slides: Introducing DFA Formal Description Using Peer Instruction

–Student study guide for Pumping Lemma (packages up the lecture slides in that segment): The Pumping Lemma

–Student study guide for Reductions from A_TM (packages up lecture slides and adds extensive additional commentary): ReductionFromATM_StudentSelf-StudyTutorial

Additional slides by Alexander Tsiatas:

Lecture 1, Lecture 2 – Please refer to Lecture01_SyllabusDFAsClosurePropertiesofRegularLangs

Lecture 3 – Slides 3-5 have additional questions, please refer to Lecture02_NFAsandRegularExpressions otherwise

Lecture 4 – Slide 8 is a slightly different version of the same question in Lecture02_NFAsandRegularExpressions, Slide 9 provides additional examples of regular expressions, Slides 12-21 have additional questions and material, please refer to Lecture02_NFAsandRegularExpressions otherwise

Lecture 5 – Slides 11-12 have additional Pumping Lemma introductory material, please refer to Lecture03_PumpingLemmaandCFGs otherwise

Lecture 6 – Slides 2-4 have additional preliminary exam questions, slides 6-14 have additional material on CFGs, please refer to Lecture03_PumpingLemmaandCFGs otherwise

Lecture 7 – Slides 13-17 have additional material, refer to Lecture04_PDAsandCFLPumpingLemma otherwise

Lecture 8 – Slides 2-5 and 18-22 have additional material, refer to Lecture04_PDAsandCFLPumpingLemma otherwise

Lecture 9 – Slide 8 has an additional question, slides 12-23 have additional material, refer to both Lecture05_AlanTuringandTuringMachines and Lecture06_TMVariantsandEnumeratorsandHilbert otherwise

Lecture 10 – Slides 18-22 have additional material, refer to Lecture06_TMVariantsandEnumeratorsandHilbert otherwise

Lecture 11Lecture 12 –  All supplementary material

Lecture 13 – Please refer to Lecture07_DecidabilityandDiagonalizationandCardinality

Lecture 14 – Slides 22-23 have addtional questions, please refer to both Lecture07_DecidabilityandDiagonalizationandCardinality and Lecture08_ATMUndecidableandHaltingProbandReductions otherwise

Lecture 15 – Slide 13 and slides 19-25 have additional material, please refer to Lecture08_ATMUndecidableandHaltingProbandReductions otherwise

Lecture 16 –  All supplementary material

Lecture 17 – Slides 2-8 and slides 20-27 have additional material, please refer to Lecture09_ReductionsFromATMandPvNP otherwise

Lecture 18 –  All supplementary material

Additional slides by Thérèse Smith:

New PI questions in these slides are offered under a Creative Commons license as follows:
Creative Commons License
Theory of Computation Lecture Materials by Thérèse Smith is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Based on a work at http://peerinstruction4cs.org.
Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.

Clickers Week 4
Clickers Week 5
Lecture Notes Week 7
Clickers Week 7

 

Leave a Reply

Your email address will not be published. Required fields are marked *