CSE 522 Assignment #3
Autumn 1998

Due: Tuesday, December 8, 1998

Read Chapters 6, 7, 11 of Motwani and Raghavan. Hand in as many of the following problems as you can. (When not otherwise specified, the problems are from Motwani and Raghavan.)

  1. pp. 156--159, Problems 6.1, 6.4, 6.5, 6.8, 6.9, 6.19, 6.22, 6.24

  2. Any problems you like from Chapter 7.

  3. pp. 308-- 309, Exercises 11.1, 11.2

  4. p. 317-- 318, Exercises 11.6, 11.7, 11.8, 11.9

  5. p. 333, Problems 11.2, 11.5, 11.6

  6. Try to modify Freivald's algorithm so that it only uses O(log n) random bits instead of n random bits for verifying AB=C, where A, B and C are n by n matrices.

  7. Consider a random walk on the nonnegative integers. where the probability of moving from 0 to 1 is 1, and for all i > 0, the probability of moving from i to i+1 is p and the probability of moving from i to i-1 is 1-p. Compute (exactly) the expected time, starting at the origin, to reach n.

  8. Research Problem 11.2 on page 332 of Motwani/Raghavan.

  9. Propose an interesting problem related to the material in the course that you think is unresolved. Sketch how you might go about approaching it.