CSI/MAT 350 - Theory of Computation

Week #

Lecture #s

Description

15
  • Exam: Wednesday or Friday 4:00-6:00 Dunn 106
14
  • 40
  • 41
  • FINAL REVIEW
  • #3 Review
13
  • 39
  • 38
  • 37
  • Exam #3
  • Review #3
  • SPACE
12
  • 36
  • 35
  • 34
  • The class NP
  • The class P
  • Algorithm Analysis
11
  • 33
  • 32
  • 31
  • Reducibility proofs
  • Reducibility
  • Tightest Classfications
10
  • 30
  • 29
  • 28
  • Tightest Classification
  • ADVISING DAY
  • Venn, ATM, Halting Problem, an unrecognizable laguage
9
  • 27
  • 26
  • 25
  • ACFG and ECFG - recognizable
  • Decidable problems (dealing wit A,E, and regular languages)
  • Decidable, Recognizable
8
  • 24
  • 23
  • 22
  • Review
  • Exam #2
  • Turing Machines
7
  • 21
  • 20
  • 19
  • Chapter 2 Review
  • Chapter 2 problems: 2.18, 2.26, 2.31, 2.33, 2.38, 2.39
  • CFG pumping lemma problems: 2.30
6
  • 18
  • 17
  • 16
  • CFGs written as PDAs problems: 2.2, 2.11, 2.12
  • PDAs continued. (minor proofs: 2.15, 2.16)
  • PDAs, problems: 2.5, 2.7, 2.10
5
  • 15
  • 14
  • 13
  • Chomsky's Normal Form, problems: 2.14
  • CFGs problems: 2.8, 2.9, 2.13
  • CFGs problems: 2.1, 2.3, 2.4
4
  • 12
  • 11
  • 10
  • Exam #1
  • Snow Day
  • Context Free Languages
3
  • 9
  • 8
  • 7
  • Review Problems
  • more pumping lemma, Chapter 1, PROBLEMS:1.31,1.36,1.39,1.41, 1.46, 1.48,1.53-1.55
  • GNFA->reg exp example, pumping lemma 1.16-1.23, 1.28-1.30
2
  • 6
  • 5
  • 4
  • regular expressions, proof reg = NFA, GNFA, NFA->GNFA->reg exp
  • NFA construction proofs, regular expressions 1.12-1.15
  • NFA, proofs problems: 1.7-1.11,1.16,1.17
1
  • 3
  • 2
  • 1
  • DFA, NFA, operations C1 problems 1.4,1.5,1.6,
  • Regular Languages, Finite Automata - Chapter 1 problems: 1.1, 1.2, 1.3
  • Sets - Chapter 0                                                               
  • Syllabus