### **Homework 2, Randomized Algorithms**

Due date: Feb 18.

All references are to the course text.

Page 188, Exercise 7.1.

Page 189, problem 7.3.

Comment: A sum of Boolean terms is an `or' and a product is an `and'.
The arithmetization of the boolean formula treats the sums and products
as plus and times, respectively.

Hint:

(i) Show that each path of G from s (the start vertex) to f (the finish
vertex) represents a distinct conjunction of Boolean variables or their
complements.

(ii) Suppose variables x1, x2, ..., xn are given values r1, r2, ..., rn,
respectively.

Let u be a vertex in G and let v and w be the other endpoints of its
outedges. Suppose the values of the expressions corresponding to the
subgraphs rooted at v and w, respectively, are known (the subgraphs are
defined by the reachable vertices). Show how to calculate the value of the
expression for the subgraph rooted at u.

Page 191, problem 7.13.

The `earlier algorithm' refers to the algorithm in section 7.6.

Try to give an algorithm that uses O(m) additional storage, rather than
O(n^2) (^ denotes exponentiation).

Hint:

Lat A be an m x m block in the text. Let Ar denote the block obtained
by shifting A one position to the right, Ad denote the block
obtained by shifting A one position down, and Adr denote the block
obtained by shifting A both one position down and one position to the
right.

Show that if Fp(Ad) and Fp(Ar) are known (generalizing the notation Fp
in the obvious way) then Fp(Adr) can be computed in O(1) time.

Though it is not necessary, it may be helpful to store the values of
expressions associated with length d portions of rows of the text.

Course Home Page

cole@cs.nyu.edu (Richard Cole)

Last modified: Jan 21, 1997