ITEC 420 - Final Exam Material - Fall 2019
ITEC 420 - Final Exam Material - Fall 2019
Updates: Last modified on
- Material
- Topics from Exams 1 and 2
- Material from chapters 17, 18, 19, 20, 21, and 28, as specified
- Approximate point distribution (about 150 points in total):
- 32 - Languages and Regular Languages
- 35 - Context Free Languages
- 45 - Turing Machines, Halting, and Decidability
- 21 - Reduction, P, NP, and NP Completeness
- 16 - Span all topics
- Chapter 17 - Turing Machines
- Give the formal definition of a TM (ie tuple: states, alphabets, transitions, initial state, final states;
transitions: read/write/direction; no transitions from halt state).
- Describe the contents of a TM configuration, written as a 4-tuple (ie current state, string to left of head, symbol
under head, string to right of head).
- Distinguish between a machine that defines a language (eg halts in Yes/No state, ignoring output string)
and one that implements a function (ie has a Halt state, and output string defines function result)
- Describe what it means for a TM to be a decider, for a TM to decide a language, and for a language to be decidable.
- Describe what it means for a TM to be a semidecider, for a TM to semidecide a
language, and for a language to be semidecidable.
- Draw or interpret a TM that implements a specified algorithm, with and without the macro language.
- Describe the comparative power of single tape deterministic TM, multi-tape deterministic TM, and nondeterministic TM
and briefly explain why this is true.
- Describe how to enumerate all TMs (ie generate all strings in lexicographic order and print the
ones that are valid TMs).
- And thus that the TMs are countably infinite.
- Describe, in general,
and interpret how a TM can be encoded.
- Describe the input, operation, and output of U, the Universal Turing Machine (aka UTM).
- Describe and interpret languages whose strings are (or contain) encoded TMs (ie how a TM can decide or semidecide a
language whose elements are themselves encodings of TMs).
- Chapter 18 - The Church-Turing Thesis
- Give a simple counting proof that there are more languages than there are Turing Machines.
- Describe the Church-Turing Thesis and its relevance.
- Chapter 19 - Unsolvability of the Halting Problem
- Define the language H.
- Show that the language H is semidecidable.
- Define the TM Trouble.
- Use the TM Trouble to prove that H is not decidable.
- Chapter 20 - Decidability and Semidecidable Languages
- Define the language classes D and SD
- Explain why D is a subset of SD (ie why every language in D is also in SD)
- Give a counting argument that not all languages are in SD.
- Show that the class D is closed under complement.
- Explain why if L and ¬L are in the class SD, then L is in D.
Show that the class SD is NOT closed under complement.
- Reproduce and be able to use the diagram on page 445 of your text (excluding parts we didn't discuss).
- Describe what an enumerator is.
- Build an enumerator for a given language.
- Chapter 21 - Decidability and Semidecidable Proofs
- Describe and give examples of the general concept of reducing one problem to another.
- Use and interpret the notation for reduction (ie A ≤ B).
- Describe the relative asymptotic complexity of the best algorithms for problems in a given reduction.
- Explain how to use reduction to show that a language is not in D.
- Construct a proof that uses reduction to show that a language such as
Hε is not in D.
- Describe how proving a language is not in D makes it easier to subsequently
prove that other languages are
not in D.
- Chapter 28 - Time Complexity Classes (ie P, NP,
NP-Hard, NP-Complete)
- Define the terms "polynomial time" and "exponential time".
Explain how to express an instance of a problem as a language.
- Define the language class P.
- Explain how to show that a language is in P.
- Define the language class NP (two definitions)
- State the Cook-Levin Theorem and explain it's significance.
- Define the term NP-Hard.
- Define the language class NP-Complete.
- Explain what you can say about the hardness of solving NP-Complete
languages as compared to solving other languages in NP.
- Here, "solve" means find a deterministic TM that halts in polynomial time.
- Explain the significance of NP-Complete languages.
- Explain the significance of finding a polynomial time solution to an NP-Complete language.
- Explain how one NP-Complete language can be used to show that another language is NP-complete
- Show that P = NP!