CSI 350 - Theory of Computation

Week #

Description

Files/HW/Links

16
  • Final Exams
    • Final Exams
    15
  • Reading Day
  • Review
  • NP-complete and problems
    • 14
  • PSPACE NPSPACE, L, NL, relationships
  • PvNP
    •  
    •  
    13
  • P vs. NP
    • No Class
    •  
    12
  • Complexity
  • Space
  • Exam 3
    •  
    •  
    11
  • Space
  • Reducibility/Review
  • Reducibility Problems/Rice's Thm
    • RS#3
    •  
    • C15: 1a,c, 3, 7
    10
  • Reducibility
  • Recursive, Recursively Enumerable, TMs, Decidability, etc
    •  
    •  
    9
  • Halting Problem
  • Countable
  • Turing Machines/Decidable vs. Recognizable
    •  
    • C14: 1, 3, 6
    •  
    8
  • Exam 2
  • Review
    • C13: 1, 2, 3, 5, 8, 17
    • C12: 2, 3.a, 7, 13, 15, 18, 19
    7
  • Turing Machines
    • 6
  • Pumping Lemma
  • CFG Properties
    • C9.1, 9.3, 9.5, 9.9, 9.10, 9.15
    • C8.1, 8.10, 8.11
    5
  • CNF, CFGs, HW
  • CNF
  • PDAs, CFGs, CNF
    •  
    • C7: 7.2, 7.3, 7.6, 7.18 (look at the rest)
    • C6: 6.2, 6.5, 6.10, 6.11, 6.17 (look at the rest)
    4
  • Exam #1
  • Review / Context Free Grammars/Languages
    • 3
  • Applications
  • Closure Properties
  • Pumping Lemma
  • Chapter 4 Hand In: 1, 2, 3, 5, 8, 11, 12, 13, 14
  • In C4: Think About: 4, 6, 7, 9, 10, 15, 16, 17
  •  
    • 2
  • Pumping Lemma
  • Conversions,Regular Languages
  • Conversions (RE->NFA<->DFA->RE)
  • Chapter 3: all problems except #3 and 16
  •  
  •  
    • 1
  • Nondeterminism
  • Regular Expressions
  • Automata, Finite, Regular Expressions
  • Chapter2 problems 1-5, 6 (REs only), 7-12, 13(hard),14-17,18(e.c)
  • All of chapter 1
  • Syllabus