CSI 350 - Theory of Computation

Week #

Lecture #s

Descriptions

Handouts/Homework

• 28
• 27

• Final Review
• P, NP, P-SPACE, NP-SPACE

• Final Review
•  

• xx
• 26

• NO CLASS
• Exam Review, The class P and NP

• 25
• 24

• Exam #3
• Review

• Exam #3
• 15.1a,c, 15.3, 15.7, Exam Review

• 23
• 22

• Reducibility
• No class - Ramsey out sick

• 13.1, 13.2, 13.3, 13.5, 13.17 and 14.1, 14.3, 14.6
• No class - Ramsey out sick

• 21
• 20

n
• Countable Sets, Diagonalization, Halting Problem
• Librarian's Paradox, Recursive and Recursively Enumerable

• Test Submission, Chapter 12: 12.2, 12.3a, 12.13, 12.15, 12.18, 12.19
• Chapter 11, 11.1, 11.2, 11.3, 11.5-11.9 (describe algorithms),11.10, 11.11, 11.13a-c, 11.14a-c, 11.15, 11.17

• 19
• 18

• Some decidable problems and proofs
• Turing machines and variations

• 17
• 16

• Exam #2
• Review

• Exam #2
• Exam Review

• xx
• 15

• Break
• Church's Thesis, HW Review

• Break
•  

• 14
• 13

• Turing Machine, Halting, Nondeterminism, Multiple Tapes
• Pumping Lemma

•  
• Chapter 9: 1-6,8-10,12,13,15a,16,17,20

• 12
• 11

• Chomsky's Normal Form, Pumping Lemma
• Chomsky's Hierarchy, CFG->PDA

•  
• Chapter 8: 1-4,8,10-12 (#6 for EC, but #5 may help)

• 10
• 9

• Exam #1
• Review/PDA Intro

•  
• ALL Chapter 7 Problems (skip 7.7), Due Thursday 10/2

• 8
• 7

• Context-Free Grammars
• Pumping Lemma, Closure Properties for Proofs

• All Chapter 6 problems Due Tuesday 9/30 (first T after Exam #1)
•  

• 6
• 5

• Applications: Bots, Elevators, Automatic Doors
• Pumping Lemma, Closure Properties

•  
• Chapter 4 Homework: All (except 4.6b and 4.6c)

• 4
• 3

• Regular Languages, Pumping Lemma
• Conversions ( RE->NFA<->DFA->RE )

• Chapter 3: all problems. (except #3 and #16)
•  

• 2
• 1

• Nondeterminism
• Finite Automata, Regular Expressions

• C2 1-5, 6 (REs only), 7-12, 13 (hard), 14-17, 18 (e.c.)
• Syllabus - All Chapter 1 Problems.