Exam 3 Study Guide
The third exam will questions that cover Turing machines and decidable languages. Some questions you may be asked to solve on the exam are:
- Write high-level descriptions of Turing machines. Study M1 on page 167. See Example 3.7 on page 171, Example 3.9 on page 173, Example 3.11 on page 174, and Example 3.23 on page 185.
- Draw Turing machines and step through configurations. See Figure 3.4 on page 169. Study Figures 3.8 and 3.10 on pages 172-173.
- Consider variations of the standard Turing machine. See Theorem 3.16, read Section 3.2 beginning on page 176 (skip enumerators).
- Show that a problem is decidable or recognizable. See Section 4.1 beginning on page 194 (Skip Theorem 4.7). The Theorems we did in class (Theorems 4.1 through 4.5 and also 4.8) should be in your cheat sheet. The proofs themselves do not need to copied.
- Consider graph related problems such as finding a Hamiltonian path (Figure 7.17 in page 292) and finding a clique of size k (Theorem 7.24). What is the minimum worst-case time-complexity of solving these problems?
Additional and relevant practice from the textbook (Sipser):
3.2
3.10
3.11
3.12
3.13
4.3
4.4
4.14
4.16
Select solutions to the above are here. Do not view the solutions before attempting the problems yourself.