[next] [prev] [prev-tail] [tail] [up]

 Exercises

  
6.1.1
The recursive program in Figure 6.E.1 sorts any given sequence A of natural numbers. The program requires time T(n) = T(m - 1) + T(n - m) + O(n) under the uniform cost criteria for some 1 <= m <= n. The recurrence equation in T(n) implies that T(n) <= O(n2). That is, the program is of O(n2) time complexity.

Find a probabilistic variation of the program that has O(n log n) expected time complexity.

Hint: A proof by induction can be used to show that T(n) = O(n log n) if T(n) <= cn + 2/n sum i=0n-1 T(i).

  
call QuickSort(A) 
procedure QuickSort(A)
   if A has cardinality 1 then return
    A1 := elements in A that are smaller than A(1)
   A2 := elements in A that are greater than A(1)
   call QuickSort(A1)
   call QuickSort(A2)
   A := concatenation of (A1, A - A1 - A2, A2)
   return
end
 
Figure 6.E.1
  
6.2.1
Let K be the problem in Example 6.2.2 of deciding the inequality AB/= C for matrices. Consider the following algorithm.
Step 1
Randomly choose an entry (i, j) in matrix C for the given instance (A, B, C) of K, and let d1 denote the element at this entry.
Step 2
Use the ith row of A and the jth column of B to compute the value d2 at entry (i, j) of AB.
Step 3
Declare that the inequality AB/= C holds if d1/= d2. Otherwise, declare that AB = C.
What are the time complexity and the error probability of the algorithm?  
6.2.2
A univariate polynomial s(x) in variable x of degree N has the form a0xN + a1xN-1 + . . . + aN-1x + aN . A brute-force algorithm for deciding the equality p(x) . q(x) = t(x) takes O(N2) time under the uniform cost criteria, if p(x), q(x), and t(x) are univariate polynomials of degree N, at most, and the coefficients are natural numbers. Show that a probabilistic program can decide the problem in O(N) time, with an error probability smaller than some constant e < 1/2.

Hint: Note that a univariate polynomial s(x) of degree N has at most N roots, that is, N values x0 such that s(x0) = 0.  

6.2.3
Let K be the problem defined by the following pair. (See page 83 for the definitions of polynomial expressions and Diophantine polynomials.)
Domain:
{ E(x1, . . . , xm) | E(x1, . . . , xm) is a polynomial expression with variables x1, . . . , xn }.
Question:
Does the given instance represent a Diophantine polynomial that is identically equal to zero?
Show that K is solvable
  1.  Deterministically in exponential time.
  2.  Probabilistically in polynomial time.
Hint: Show that each Diophantine polynomial E(x1, . . . , xm) of degree d that is not identically equal to 0 has at most Nm/c roots (^x1, . . . , ^xm) that satisfy 1 <= ^x1, . . . , ^xm <= N, if N >= cd and c >= 1.   
6.3.1
Let M1 be a probabilistic Turing machine with error probability e(x) < 1/3. Find a probabilistic Turing machine M2 that accepts L(M1) with error probability e(x) < 7/27.  
6.3.2
Show that an error-bounded probabilistic pushdown automaton can accept the language { aibici | i >= 0 }.  
6.3.3
  1.  Show that if (v1, . . . , vm) is a nonzero vector of integers and d1, . . . , dm are chosen randomly from {1, . . . , r} then d1v1 + . . .+ dmvm = 0 with probability no greater than 1/r.
  2.  Show that L = { a1bma2bm-1 . . . amb1 | m >= 0 } is accepted by a bounded-error probabilistic pushdown automaton.

    Hint: Use part (a) of the problem to check that the inputs have the form ai1bj1ai2bj2 . . . aimbjm with i2 - i1 - 1 = 0, i3 - i2 - 1 = 0, . . .  and  j1 - j2 - 1 = 0, j2 - j3 - 1 = 0, . . .

 
6.3.4
Show that a language accepted by an n-states, nondeterministic finite-state automaton M1 is also accepted by an (n + d)-states, bounded-error, two-way, probabilistic finite-state automaton M2, that is, an (n + d)-states, bounded-error, 0 auxiliary-work-tape, probabilistic Turing machine M2. d is assumed to be a constant independent of M1.

Hint: Allow M2 to halt in a rejecting configuration with probability (1/2)n and to start a new simulation of M1 with probability 1 - (1/2)n, after simulating a nonaccepting computation of M1.   

6.4.1
Show that ZPP and BPP are each closed under union.  
6.4.2
Show that each function computable by a bounded-error probabilistic Turing transducer with polynomially time-bounded complexity, is also computable by a polynomially space-bounded, deterministic Turing transducer.

[next] [prev] [prev-tail] [front] [up]