ITEC 420 - Final Exam Material - Fall 2019

Updates: Last modified on

• No updates at this time

1. 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
2. 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 U_TM).
   • 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).


3. 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.


4. 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.


5. 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.
   
   
6. 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.
   
   
7. 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!
   • Automatic grade of "A"!