Multiple Choice — 5 Points Each

1.  A certain recursive algorithm is analyzed using the master theorem, which shows it to run in Θ(n2 ) time. Which of the following could have been the algorithm’s recurrence? Mark all correct answers.

。 A(n) = 6A(n/3) + n

。 B(n) = 16B(n/4) + n2

。 C(n) = 9C(n/3) + nlog n

。 D(n) = 17D(n/11) + n2

。 E(n) = 4E(n/2) + n2 log n

    2.  Recall that Euclid(x,y) computes the greatest common divisor (gcd) of positive integers x and y, where

x > y. Mark all true statements.

。 If Euclid(x, y) = 1 then either x or y is prime.

。 If x  > x,  and y  > y, , then  Euclid(x, y) makes at least as many recursive calls in total as  Eu- clid(x, , y, ).

。  Euclid(22, 17) eventually makes the recursive call Euclid(5, 2).

。 There exists a positive integer x such that Euclid(2x, x) eventually makes the recursive call Eu- clid(5, 2).

3.  Consider the following statements about Turing Machines. Mark all those that are true.

。 There are Turing Machines that can be used to simulate any other Turing Machine.

。 Every decidable language can be decided by some Turing Machine.

。 The number of states of a Turing Machine depends on the input length  jxj .

。 Some Turing Machines decide languages that no DFA can decide.

。 Every language decidable by a DFA is also decidable by a Turing machine.

4.  Consider 3 languages L1 ,  L2   and L3 ,  where L1   is decidable and L2   is undecidable.   Mark  all statements that are necessarily true.

。 If L1  ≤T  L3 , then L3  is decidable.

。 If L2  ≤T  L3 , then L3  is undecidable.

。 If L3  ≤T  L2 , then L3  is decidable.

。 If L3  ≤T  L2 , then L3  is undecidable.

。 If L3  ≤T  ;, then L3  is decidable.

5.  The function SubsetSum(A[1, . . . , n], k) is defined as follows.  Given an array of positive integers A, and an integer k, return True if there is a subset of elements of A that sums to k, and False otherwise.

Which of the following are true statements we can use to build a recurrence relation for computing SubsetSum(A[1, . . . , n], k)?  (Recall that ∨ is boolean OR.) Select all that apply.

。  SubsetSum(A[1, . . . , n], k) = True if k = 1

。  SubsetSum(A[1, . . . , n], k) = True if k = 0

。  SubsetSum(A[1, . . . , n], k) = False if k < 0

。  SubsetSum(A[1, . . . , n], k) =  SubsetSum(A[1, . . . , n — 1], k — A[n]) if k > 1 and n ≥ 1

。  SubsetSum(A[1, . . . , n], k) =  SubsetSum(A[1, . . . , n — 1], k)

∨ SubsetSum(A[1, . . . , n], k),   if k ≥ 1 and n ≥ 1

。  SubsetSum(A[1, . . . , n], k) =  SubsetSum(A[1, . . . , n — 1], k — A[n])

∨ SubsetSum(A[1, . . . , n — 1], k),   if k ≥ 1 and n ≥ 1

6.  Consider the set of all languages LΣ  over an alphabet Σ = {a} consisting of one character ‘a,.  Mark all true statements.

。 Some L ∈ LΣ  is finite.

。 Some L ∈ LΣ  is countable.

。 Some L ∈ LΣ  is uncountable.

。 LΣ  is uncountable.

。 LΣ  is countable.

7. Which ONE of the following languages is unrecognizable?

。 L∈ -HALT  = {〈M〉j M halts on input ∈}

。 LTwo  = {〈M〉j M accepts two strings with the same length}

。  L;  = {〈M〉j L(M) = ∅}

。 LIntersect  = {〈M1 , M2〉j L(M1 ) ∩ L(M2 )  ∅}

8.  The set of recognizable languages over the binary alphabet Σ = {0, 1} is uncountable.

。 True

。 False

9.  Consider the activity scheduling problem, where we are given a list of intervals  (s1 , f1 ), . . . , (sn , fn ) indicating the start and finishing time of each activity, and want to pick a maximum size subset of compatible activities (having disjoint intervals). A generic greedy algorithm sorts the activities in some way, then runs through the sorted list, including each activity if it is compatible with previously chosen activities. Which ONE of the following sorting strategies ensures that the greedy algorithm produces an optimal answer?

。 Sort the activities in increasing order by start time, so s1  ≤ s2  ≤ · · · ≤ sn.

。 Sort the activities in decreasing order by start time, so s1  ≥ s2  ≥ · · · ≥ sn.

。 Sort the activities in increasing order by length, so f1 — s1  ≤ f2  — s2  ≤ · · · ≤ fn — sn.

Shorter Answer — 6 points each

1. What language does the following DFA decide?  Give your answer as a regular expression.  It should only use the symbols a, b, ∈,* , j , (, ).

2.  Karatsuba(x, y) computes the product xy using Karatsuba’s algorithm, where x and y are written in base 10. Karatsuba(1023, 2114) makes three recursive calls.  What are the numerical arguments to those recursive calls?

3.  Suppose Kruskal’s algorithm is run on the following edge-weighted graph.

List the edge weights of the edges chosen by Kruskal’s algorithm, in the order chosen.

Long Answers — 12 Points Each

1a.  Given an array A[1; . . . ; n] of distinct positive integers,  a  zigzag  subsequence is a subsequence of A such that consecutive pairs of elements alternate between increasing and decreasing.  Give a dynamic programming algorithm for computing the length of a longest zigzag subsequence.  Write a recurrence, and explain how a solution to it can be used to find the length of a longest zigzag subsequence.  You do not need to write pseudocode.   Express the runtime of a dynamic programming algorithm that implements your recurrence, as a function of n.

For example, zigzag subsequences of (3; 6; 2; 1; 8; 5) include (3; 6; 1; 8; 5), (3; 2; 5), and (2; 8; 5), but not (3; 2; 1) or (3; 6; 8; 5).

1b.  The 1-complexity of a positive integer n is the minimum number of 1s in an expression over the alphabet {(; ); × ; +; 1} that evaluates to n. For example, the following expressions

17 = (1 + 1 + 1 + 1) × (1 + 1 + 1 + 1) + 1

17 = (1 + 1) × (1 + 1) × (1 + 1) × (1 + 1) + 1

17 = (1 + 1 + 1) × (1 + 1 + 1) + (1 + 1 + 1 + 1) × (1 + 1)

49 = ((1 + 1 + 1) × (1 + 1) + 1) × ((1 + 1 + 1) × (1 + 1) + 1)

49 = (1 + 1 + 1) × (1 + 1 + 1) × (1 + 1 + 1 + 1 + 1) + 1 + 1 + 1 + 1

demonstrate that the 1-complexity of 17 and 49 are at most 9 and 12, respectively.

Write a recurrence for the 1-complexity of n, including base case(s).  You do not need to write pseu- docode. Express the runtime of a dynamic programming algorithm that computes the 1-complexity of all integers between 1 and n, as a function of n.  (Hint:  Consider every two numbers whose sum is n, or whose product is n.)

2.  Prove that the language LSingle  = {〈M1 , M2〉 :   M1  and M2  are TMs and jL(M1 ) ∩ L(M2 )j =  1} is undecidable. Use a reduction from either LACC  or Lε-HALT .

LACC  = {(〈M〉, x) : M is a Turing machine that accepts x}.

Lε-HALT  = {〈M〉: M is a Turing machine that halts on ε}

3.  A string over the alphabet Σ = {(, )} is called “balanced” if it has equal number of ( and ) symbols, and any prefix of the string has at least as many ( symbols as ).  For example, the expressions  “()”, “(()())”,  and  “((()))” are balanced, but “(()”,  “())(”,  “)(”  and  “((()” are not.

Construct a DFA that decides the language of balanced strings over Σ = {(, )}, or give a proof by contradiction that no such DFA exists.