Ursinus CS 373: Theory of Computation, Fall 2023
Week 13 Module: The Class NP: P = NP??
Chris Tralie
<--- Previous
Watch the two videos below, then
click here
to complete an exercise on Canvas.
Notes
Menu
General
Overview
Technology Logistics
Readings
Deliverables
Schedule
Grading
Classroom Environment
Collaboration Policy
Other Resources / Policies
Software
Schedule
Final Project
Assignments
HW1: Discrete Math Practice
HW2: DFAs
HW3: DFAs And NFAs
HW4: Regular Expressions And Nonregular Languages
HW5: Context Free Grammars And Pushdown Automata
HW6: Turing Machines
HW7: Turing Machines, Turing Enumerators, And Decidability
HW8: Decidability
HW9: Computability
Class Exercises
Week 1: Acting Out DFAs
Week 1: Discrete Math Review
Week 1: Binary And JFLAP
Binary Drills
JFLAP Exercises
Week 2: Formal Description of DFAs, Divisibility
Formal Regular Languages: Code
Week 2: Union of Regular Languages
Week 3: Nondeterministic Finite Automata (NFAs), Reversing Regular Languages
Week 3: NFAs Recognize Regular Languages (i.e. NFAs To DFAS)
Week 4: Efficiently Evaluating NFAs in Python with and without Lambda
Week 4: Converting Regular Expressions To DFAs And Back
Week 4: Grep: Regular Expression Parsing And Evaluating
Week 5: The Pumping Lemma
Week 7/8: Turing Machine Examples
Week 8: Multitape Turing Machine Examples
Week 10: Decidability
Week 11: Countable And Uncountable Infinities
Week 12: Undecidability
Week 13: The Class P
Week 13: The Class NP
Week 14: Cook Levin Theorem And SAT Solving