Develop a randomized algorithm for ?nding the target

Assignment Help Data Structure & Algorithms

Reference no: EM131942367

Assignment: Introduction to Algorithms

Problems

(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.)

(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.)

Reference no: EM131942367

Questions Cloud

How does careful revision reflect the you attitude : Why should you limit the number of typefaces and type styles in most business documents?

Is the escrow agent liable to the plaintiff : The escrow agent failed to withhold the funds as agreed. The plaintiff was not a party to the escrow. Is the escrow agent liable to the plaintiff?

Why does a company want to produce newer versions : Why does a company want to produce newer versions. Under what circumstances would they not want to develop upgrades?

Why did global green books publishing struggle : Are you aware of other similar start-up businesses that struggle in a similar manner? How did they overcome the challenges?

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

Compute cost of goods manufactured and sold : Perry Company incurred the following costs while manufacturing its product. Factory supplies used 23,000 clerks 50,000. Compute cost of goods sold

Effects of Having ADHD in the Workforce : The Effects of Having ADHD in the Workforce- ADHD Grows Up - he abstract should state the most important facts and ideas in your paper. It should be complete

Calculate the cost of goods manufactured : Beginning raw materials inventory $46,800 and Ending goods in process inventory 20,000, Calculate the Cost of Goods Manufactured and the Cost of Goods Sold

Explain the effect of power and influence that leaders have : Final Assignment on Leadership - Explain the effect of power and influence that leaders have on followers in the organization. Are the followers receptive?

User Account

All Pages