Learning Goals, Math 421-101, Fall 2015
Materials here may contain errors; some corrections might only be announced in class.
| Coverage for the Final Exam |
|
|---|---|
| Learning Goals for the Midterm (2015) |
Topic 1: Uncomputability and Self-Referencing, Sections 1--4
(including various paradoxes, countable versus uncountable, set versus its
power set).
Learning Goals and Sample Exam Problems given in Section 7 of the article
Uncomputability and Self-Referencing in CPSC 421.
From Sipser's textbook:
Chapter 3: Turning machines and multitape Turing machines,
PALINDROME;
Chapter 4: Countable and uncountable sets, universal Turning machines,
recognizability but undecidability of the acceptance problem (A_TM);
Chapter 7: Time (i.e., number of steps), space (i.e., rightmost tape
cell visited), polynomial time.
All homework problems are good sample exam problems. Other sample exam problems: Mid 2007: 3(a); Fin 2007: 2, 4; Mid 2009: 1; Mid 2010: 1; 4 (also the same question where "decidable in polynomial time" is replaced with "decidable" or "recognizable"); Fin 2010: 4, 7 (with "L_yes" replaced with the acceptance problem for Turing machines); Mid 2011: 1, 2(a), 3, 4; Fin 2011: 1, 2, part of 7; Mid 2014: 1, 2 (b,c,d). |
| Previous Exams |
Note that material and emphasis changes from year to year; look at
"Learning Goals" above to see which problems on which exams
are relevant to our course.
Exams available (some with brief solutions):
|