CS172 Computability & Complexity (Spring’09)Instructor: Mihai Pˇatra¸scu GSI: Omid EtesamiMidterm Exam 1.5 hoursAll electronics must be off. You may bring one sheet of paper (double-sided, letter size) containing anynotes you care to use. No other materials allowed. You may answer questions in any order.1. [10 points] Write your name, email, and student ID on top of all sheets of paper. Makesure your cell phone (or other device) will not produce sound during the exam.2. [10 points] Draw the automaton (with ε-transitions) that the Knuth-Morris-Pratt algorithmbuilds for the needle tatutatutata.3. [20 points] The ? operator from the C programming language is used in expressions like:A?B : C. Here A, B, C are themselves expressions. If A evaluates to non-zero, the entire expression“A?B : C” evaluates to the value of B; if A is zero, the entire expression evaluates to the value ofC. For instance, 7 − 7?3 + 9 : 1 + 2 evaluates to 3. The ? operator has lower precedence than +and −, so the expression is the same as (7 − 7)?(3 + 9) : (1 + 2).(a) Write an expression that evaluates to different values if ? : is left-associative versus right-associative.(b) Write a context free grammar that parses expressions involving +, −, ? :, parentheses, andsingle-digit numbers. Assume ? is left-associative. You may ignore the use of minus fornegation (ignore expressions like −3).(c) Same as (b), but ? is right associative.(d) Give succinct pseudocode for parsing the grammar in (c).(e) Informally explain why the following grammar is harder to parse. Illustrate with a couple ofexamples. (Note: this grammar is rather unrelated to the answers you must give in (b) and(c). Please do not get confused by using this as a starting point.)S → T ?T : T | U?U#UT → T + V | T − V | VU → V + U | V − U | VV → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94. [10 points] Consider a stream containing n − 1 distinct numbers from {1, . . . , n}. In otherwords, the stream contains all numbers from 1 to n, except one. Describe an algorithm usingO(lg n) bits of space that outputs the missing number. You may assume n is known in advance.15. [10 points] Consider a stream of n integers in {0, . . . , n2}. The goal is to determine whetherthe average of the values is also an element of the stream. For instance, in the stream [3, 7, 1, 2, 2],the average is 3, which does appear in the stream. In the stream [4, 7, 1, 2, 2], the average is 3.2,which does not appear in the stream.Show that any algorithm answering this question must use Ω(n) bits of memory. (Your proofwill likely invoke the communication lower bound for Indexing.)6. [10 points] Prove or disprove:(a) There exists a bijection between the set of real numbers in (0, 1) and the set of points withreal coordinates in (0, 1)2.(b) Let F be the set of functions f : N → N satisfying: (∀)n ∈ N, n ≤ f (n) ≤ n2. The set F iscountable.6. [10 points] Socrates arrives in a new town with n people, at mostn2− 1 of which are liars.His goal is to determine which ones are honest and which not.To accomplish this goal, he can organize debates between any pair of the n people. After Afinished debating B, A tells Socrates what he believes about B, and B tells what he believes aboutA. An honest person will always identify the other person correctly (as an honest man, or as aliar). But a liar might say anything (including the truth).How can Socrates identify the honest people?8. [20 points] A little known fact is that the Incas designed a Turing Machine many centuriesago. Their machine model was identical to the regular Turing Machine, except for the Sacred InputCommendment: “Thou shalt not overwrite a tape location where thy input hast been placed.”(a) Assume the input is represented with one free (unwritten) cell in between each two input cells.That is, if the input is s1, s2, s3. . . , the beginning of the tape will read s1, free cell, s2, freecell, s3, free cell, etc. Show that the Inca Machine can compute anything that a regularTuring Machine can compute.(b) Now assume the input is written contiguously at the beginning of the tape (as usual forTuring Machines). Show that the Inca Machine is exactly as powerful as a Read-Only TuringMachine. A Read-Only Turing Machine is a Turing Machine that cannot write to tape at all(it may only move its head around and read cells).(c) What exactly is the set of languages decidable by a Read-Only Turing