How many good pivots will guarantee

Assignment Help Computer Engineering

Reference no: EM133258601

Question: Consider the following randomized algorithm for Select(S, k) which outputs kth smallest key from a set S of keys. We use pivoting strategy for this. We first select a random pivot r and partition S around r. This will create parts A and B of S such that all the keys in A are smaller than r and all the keys in B are bigger than r.

Depending on the value k and size of A, we decide to recurse either on A or B. Both A and B are smaller problems than the original. However, to ensure that they are smaller by at least some constant fraction. So we call, r a good pivot if it is ranked within 25% to 75% of set S. What is the probability of finding a good pivot? Next, we see that at every good pivot the problem size reduces by 75% of the original. So how many good pivots will guarantee that the problem size goes down to 1 starting from the original set S of cardinality |S| = n.

To ensure those many good pivots how many pivots totally will be required to be chosen over the entire algorithm. This is asking to find the expected number of coin tosses do you need to get k heads. Let's call this expectation of random variable X (number of coin tosses). Break it up into X1, X2, ..., Xk and find X.

Reference no: EM133258601

Questions Cloud

Perform etl operation using query editor : CS 102 Federal Science & Commerce College, Perform ETL operation using Query editor Make table relationship with Data Model

Critical discourse analysis for the movies enemy : Critical discourse analysis for the movies Enemy of the State, The Immortal Life of Henrietta Lacks and Miss Evers' Boys

Identify the environmental influences important to sportz : Identify the environmental influences important to SPORTZ? Does Mazen need to do anything else to set up a strategic HR function

How their actions in battle reflect the qualities of heroes : Using the actions you have noted for Grendel and Beowulf, discuss how their actions in battle reflect the qualities of heroes and monsters.

How many good pivots will guarantee : How many good pivots will guarantee that the problem size goes down to 1 starting from the original set S of cardinality |S| = n

Evaluate the mean of all three crops : CSIS San Diego Christian College Create a S3 class named crops that will track soybeans, wheat, and corn harvests. Include a function to evaluate the mean

What are three different cognitive levels in children : What are three different cognitive levels in children and examples of behaviours that reflect this level and how this can be managed.

What are the challenges facing mobile payment systems : what are the challenges facing mobile payment systems like that from Technology, Business, and Users prospectives ?

Write at least two actors for hotel management : BIOL 408 St. Augustine's University Write at least two actors for hotel management, their activities, functional requirement, and Non-functional requirement

User Account

All Pages