CSI 350 - Theory of Computation

• 350 Review Sheets
• Final Exam
• Part 4 of Finals: Infinities, Space and Time! - Practice 4
• Chapter 19: 10,11,14
• Chapter 18: 2,4,8
• Chapter 17: P v NP, 1,2,3,4,8,9,10,12,13,15
• Chapter 15: 1-8
• Chapter 14: 1-4,6
• Exam 3: TMs - Practice 3
• Chapter 13: 1-10,14,16
• Chapter 12: 1-6, 8-10, 12-16, 19-20, 23
• Chapter 11: 1-17
• Exam 2: CFLs - Practice 2
• Chapter 9: 1-6, 8-13, 15- 16
• Chapter 8: 1, 8, 10-12
• CNF example: CNF.txt
• Chapter 7: 1-6, 8-18, #19: arf
• Chapter 6: 1-8,10-14, 17-20
• Exam 1: Regulars
• NFA to DFA and NFA to RE conversions.
• Sample Quizzes: Quiz 1 | Quiz 2 | Quiz 3 | Quiz 4
• Closure Properties: Kleene, complement, intersect, Chapter 4: 4.1-7
• Chapter 4: 4.8-15
• Pumping Lemma: 0^i 1^j, ww^R, ww, 0^n 1^n 2^n, a^2^n, 0^n 1^m 0^n, a^i b^j c^k i=j when k=1
• Chapter 3: 1-14
• Chapter 2: 1-12, 13 (hard), 14-17, 18 (hard)
• Chapter 1: All
• Recall starred problems are in the back - answered.
• Syllabus is here.