Search this site
Embedded Files
Skip to main content
Skip to navigation
CS 311 - Theory of Computation
Home
Syllabus
Schedule
Notes
Notes 01 - Overview, Intro to DFAs
Notes 02 - Regular Operations
Notes 03 - NFAs
Notes 04 - DFAs and NFAs
Notes 05 - Closure Under Regular Operations
Notes 06 - Regular Expressions
Notes 07 - Regular Expressions and Regular Languages
Notes 08 - Nonregular Languagas
Notes 09 - Nonregular languages (cont'd)
Notes 10 - Context-Free Grammars
Notes 11 - Pushdown Automata
Notes 12 - Pushdown Automata and Context-Free Grammars
Notes 13 - Pushdown Automata and Context-Free Grammars
Notes 14 - Turing Machines
Notes 15 - More Turing Machines
Notes 16 - Algorithms
Notes 17 - Decidability
Notes 18 - The Halting Problem
Notes 19 - Reducibility
Notes 20 - Mapping Reducibility
Notes 21 - Measuring Time Complexity
Notes 22 - P and NP
Notes 23 - NP-Completeness
Notes 24 - More NP-Completeness
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Tools & Resources
CS 311 - Theory of Computation
Home
Syllabus
Schedule
Notes
Notes 01 - Overview, Intro to DFAs
Notes 02 - Regular Operations
Notes 03 - NFAs
Notes 04 - DFAs and NFAs
Notes 05 - Closure Under Regular Operations
Notes 06 - Regular Expressions
Notes 07 - Regular Expressions and Regular Languages
Notes 08 - Nonregular Languagas
Notes 09 - Nonregular languages (cont'd)
Notes 10 - Context-Free Grammars
Notes 11 - Pushdown Automata
Notes 12 - Pushdown Automata and Context-Free Grammars
Notes 13 - Pushdown Automata and Context-Free Grammars
Notes 14 - Turing Machines
Notes 15 - More Turing Machines
Notes 16 - Algorithms
Notes 17 - Decidability
Notes 18 - The Halting Problem
Notes 19 - Reducibility
Notes 20 - Mapping Reducibility
Notes 21 - Measuring Time Complexity
Notes 22 - P and NP
Notes 23 - NP-Completeness
Notes 24 - More NP-Completeness
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Tools & Resources
More
Home
Syllabus
Schedule
Notes
Notes 01 - Overview, Intro to DFAs
Notes 02 - Regular Operations
Notes 03 - NFAs
Notes 04 - DFAs and NFAs
Notes 05 - Closure Under Regular Operations
Notes 06 - Regular Expressions
Notes 07 - Regular Expressions and Regular Languages
Notes 08 - Nonregular Languagas
Notes 09 - Nonregular languages (cont'd)
Notes 10 - Context-Free Grammars
Notes 11 - Pushdown Automata
Notes 12 - Pushdown Automata and Context-Free Grammars
Notes 13 - Pushdown Automata and Context-Free Grammars
Notes 14 - Turing Machines
Notes 15 - More Turing Machines
Notes 16 - Algorithms
Notes 17 - Decidability
Notes 18 - The Halting Problem
Notes 19 - Reducibility
Notes 20 - Mapping Reducibility
Notes 21 - Measuring Time Complexity
Notes 22 - P and NP
Notes 23 - NP-Completeness
Notes 24 - More NP-Completeness
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Tools & Resources
Notes 19
Reducibility
reducibility
reducibility.pdf
Report abuse
Report abuse
