Assignment: Introduction to Algorithms

Problems

1.

(a) We have n users on a P2P network who want to pick distinct IDs in a distributed fashion. Each user independently picks one uniformly random b bit number. Show that when b ≥ 6 + 2 log n, the probability of the users picking distinct IDs is at least 0:99.

(b) We have n users with distinct IDs on a P2P network, who want to elect a leader in a distributed fashion. Each user independently picks a uniformly random b-bit number, and the leader is determined to be the user with the smallest number. Show that when b ≥ 8 + log n, the probability that a unique leader is chosen is at least 0:99.

(Hint: To obtain a simple bound on the sum of a series, approximate it by an integral. In particular, for a positive increasing function h, _i=1 ∑^k h(i) ≥ _i=0∑^k h(i) di.)

2.

(a) You are given a circle of unit circumference. You pick k points on the circle independently and uniformly at random and snip the circle at those points, obtaining k different arcs. Determine the expected length of any single arc.

(Hint: Note that the length of each arc is identically distributed, so each has the same expectation. What is the sum of their expectations?)

(b) You are given a sorted circular linked list containing n integers, where every element has a "next" pointer to the next larger element. (The largest element's "next" pointer points to the smallest element.) You are asked to determine whether a given target element belongs to the list. There are only two ways you can access an element of the list: (1) to follow the next pointer from a previously accessed element, or (2) via a given function RAND that returns a pointer to a uniformly random element of the list.

Develop a randomized algorithm for ?nding the target that makes at most O(√n) accesses in expectation and always returns the correct answer.

(Hint: Your algorithm will perform some random accesses and some amount of linear search. Use part (a) to analyze the number of steps in the linear search.)