CSE 522 Assignment #2
Autumn 1998

Due: Thursday, November 12, 1998

Read Sections 5.1, 5.5, 5.6, 9.10, 10.3, and 12.6 of Motwani and Raghavan. Hand in as many of the following problems as you can.

  1. Simplify Ben-Or's algorithm for Consensus in the Presence of Malicious (Byzantine) Faults so that it only works in the case of fail-stop faults but can tolerate more faults, in particular any t < n/2 faults, rather than t < n/5 faults.

  2. A form of Stirling's approximation to the factorial function says that n! is of the form (2 pi n)1/2 (n/e) n (1+x) where there are constants c and d > 0 such that c/n > x > d/n. Use this to compute an estimate of the probability that the binomial distribution B(n,1/2) takes on the value n/2. Generalize your argument to show that for any constant c', Pr[ B(n,1/2) > n/2 + c' n1/2 ] is at least some fixed constant depending on c', but not on n.

  3. Motwani and Raghavan, Problem 5.3, page 124.

  4. Motwani and Raghavan, Problem 5.8, page 125.

  5. Show how the method of conditional probabilities can be used to derive a deterministic algorithm for finding a 1/2-approximate solution to the MAX-SAT problem based on the simple randomized algorithm discussed in class that on average satisfies 1/2 of the clauses. (The randomized algorithm is given in the proof of Theorem 5.2 of Motwani and Raghavan.)

  6. Motwani and Raghavan, Problem 9.11, page 277

  7. Motwani and Raghavan, Problem 10.16, page 305

  8. The current known linear time algorithms for MST verification are not as simple as one would like. Think about how you might solve this problem in linear time.

  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.