CS 332: Theory of Computation Professor Mark Bun Boston University April 6, 2020
Homework 7 – Due Monday, April 13, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on the following exercises and solved problems in Chapter 7: 7.1, 7.2, 7.4, 7.6, 7.8–7.11. The material they cover may appear on exams.
Note If you need to describe a Turing machine, please give a high-level description as in Chapter 4.1 of Sipser or in Lecture 13.
Problems There are 3 mandatory problems.
1. (Review of asymptotic notation) This problem will be graded automatically by Grade- scope. Please enter your answers manually by completing the assignment Homework 7- Problem 1. For each of the following, select true or false using the radio buttons on Grade- scope.
(a) 210 = O(n) (b) 16n = O(n)
(c) n4 = O(n2 logn)
(d) nlogn+10n=O(n2)
(e) 3n = O(2n) (f) 3n = 2O(n)
(g) 22n = O(22n) (h) nn = O(n!)
(i) n = o(n) (j) 2n = o(n2)
(k) 2n = o(3n) (l) 1 = o(n)
2. (Exponentiation cipher) An exponentiation cipher encodes a message A using a ciphertext C = Ae (mod p) where p is a prime number and e is an integer exponent. (Here A and C are also integers.) You are given integers A, C, e and p, and you would like to determine whether C is a valid ciphertext for message A.
1
(m) 2logn = o(logn) (n) 1 =o(1)
3
(o) log2 n = Θ(log3 n)
(p) 2n = Θ(4n)
(q) n5 = Θ(32log2 n)
(r) n3 = Ω(n3)
(s) log n = Ω(log(log n)) (t) 25n = Ω(52n )
(a) Formulate this problem as a language EC.
(b) Explain why the following algorithm for EC does not run in polynomial time: Compute Ae using e − 1 multiplications. Take the result modulo p using one integer division, and compare the answer to C.
(c) Show that EC ∈ P. Analyze the running time of your algorithm using O-notation. Hint: First, find an algorithm for the case when e is a power of 2.
3. (Closure properties of P) For both parts of this problem, analyze the running time of your algorithms using O-notation. Prove that P is closed under
(a) concatenation;
(b) star.
Hint: Use dynamic programming. Let A ∈ P. On input y = y1 ···yn for yi ∈ Σ, build a table indicating for each i ≤ j whether the substring yi · · · yj ∈ A∗.
2