Cs373 Final Exam Guidelines
CS373 FINAL EXAM GUIDELINES ... NMG (Spring 2003)
Posted 5/5/03
Final Exam given on Tuesday, 5/13/03 from 2:00PM-4:00PM in LH009.
Weight of exam is 25% of final grade.
Exam is CLOSED BOOK, CHEAT SHEETS ARE ALLOWED. You may bring in the two “cheat sheets” you used for the first two exams (or a re-make of them), plus one additional “cheat sheet”
(8½ x11) for the material after these exams. All cheat sheets will be subject to same restrictions and guidelines as described in the coverage documents for the first two exams – please review these restrictions. If you decide use photocopies of text material or material you did not personally write, there will be a 5 point penalty!
The final exam will be comprehensive with extra focus on the material not covered by the two midterm exams. Thus, the material covered from chapters 1 through 8 will be the same as that described in the handouts for the coverage of exams 1 and 2 and will not be repeated here (review these documents). Coverage after the two exams is as follows:
Chapter 9, Turing machines.
-All of chapter 9 will be covered.
-Problems similar to those in homework 9 would be likely, but perhaps not as lengthy as the homework problems.
-TM’s as transducers (general computation) and as language acceptors will be important.
-Understand Turing’s Thesis from a conceptual point of view.
Chapter 10, other models of Turing machines as covered in the lectures.
-Meaning of equivalence of automata
-Simulation on a TM
-TM with stay option
-Multi track TM
-Semi infinite tape TM
-Multitape TM’s ... very useful section
-Nondeterministic TM - know and understand its definition and relationship to the deterministic TM.
-Universal TM - key concept
-Countable sets
-Enumeration procedure and how it related to Recursively Enumerable Languages
-Linear bounded automata its definition and how its relationship to language hierarchy.
-Countability of the set of all TM’s
Chapter 11, A Hierarchy of Formal languages and Automata:
-Understand the meaning, relationships, and implications of all theorems in
chapter 11,
-The distinction between Recursively enumerable languages, and recursive languages
-Enumeration procedure and how it relates to Recursively Enumerable
and Recursive Languages
-Use of TM to list strings in a specified language (enumeration procedure) and its implication on Recursively enumerable languages (p. 277, 3rd ed.)
- Countable sets and enumeration procedures
- The distinction between a set being countable and having an enumeration procedure.
-Languages that are not recursively enumerable
-Cantor’s proof that the collection of all subsets of a countably infinite set is not countably infinite (Theorem 11.1).
-Proof of the existence of non-recursively enumerable languages - very basic and elegant - uses Cantor’s diagonalization method and the fact that the powerset (set of all subsets) of a countably infinite set is not countable. (Theorem 11.2)
-Theorem 11.3 – the proof that there exists a recursively enumerable language whose complement is not recursively enumerable – the proof given is elegant and not difficult.
-Unrestrictive grammars and relationship to recursively enumerable languages
-Context sensitive grammars/language and relationship to Linear bounded automata
-The relationship between unrestricted grammars, context sensitive grammars, and corresponding automata and languages generated by each.
-The Chomsky hierarchy
Chapter 12: We had a high level introduction to the concepts in Chapter 12 at the end of the courses. The concepts outlined in class are based 100% on the material we have already covered. You should now be able to easily read and understand the meaning of “computability”, “decidability”, and specifically the classic Turing Machine Halting Problem as given on page 301 (313 2nd ed). The coverage will only be one section: 12.1. Although we did not have time cover the proof of theorem 12.1 (The halting problem is undecidable), you should be able to read and understand it with little difficulty. Note the mind boggling and ”paradoxical” conclusion to this “proof by contradiction”: assuming there exists a TM, H, solving the halting problem, leads us to the paradoxical conclusion that H halts if it does not halt, and that it does not halt if it halts … page 301 (315, 2nd ed). This happens when it tries to analyze itself. The same could be said about the material in the latter part of section 12.1 for which we did not have time to cover; it is fascinating and could be read on your own. There could be a “thinking question”, a “gedanken experiment”, or philosophical question asked on this material - set your mind free!
Understanding concepts will be the focus of coverage of chapters 10, 11, and especially 12, although chapter 10 may also be used for a quantitative problem (alternate forms of the TM).
Finally, there may be some historical questions related to automata as per the coverage in the lectures.
Test problems may involve
-answering questions
-Specify an automaton (or grammar) to do a given task.
-proving claims
-applying theorems
-applying definitions
-Basic principles.
Note: I expect clear concise answers. Handwriting MUST be legible - if I cannot decipher an answer after a short period of time, it gets marked wrong and will not be contestable. Illegible, microscopic, or incomprehendable writing will not be tolerated. All definitions of automatons (transition function) and grammars MUST be commented. If comments are omitted, and I cannot understand what you are doing, points will be lost.
I am also very intolerant of “smoke screens”, ie., lots of words not saying very much or having little relationship to the question.
Finally: By now you should realize that I demand rigor, formalism, and justification of all mathematical steps - especially in proofs and pumping lemma problems. I WILL NOT ACCEPT RESULTS OR FORMULAS WRITTEN DOWN BY INSPECTION (EVEN IF CORRECT), UNLESS EXPLICITELY ALLOWED - YOU MUST SHOW THE STEPS LEADING TO THE RESULTS. POINTS TAKEN OFF FOR NOT DOING SO WILL BE INCONTESTABLE - YOU HAVE BEEN INFORMED.
One parting thought: some of my heros in mathematics are the British Mathematician G. H. Hardy who wrote the book “A Course in Pure Mathematics”, and Martin Gardner who wrote a monthly mathematical column for the magazine “Scientific American”. Hardy’s mentor was Srinivasa Ramanujan the famous self-taught math genius from India. These guys saw the beauty and elegance of mathematics, and saw beyond the modern world view of pragmatism, money, and profit