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.

cole@cs.nyu.edu (Richard Cole)