5 exercises
Topic:
  • Randomized Algorithms x

Start over - to expand, or dig in by adding more tags and revising the query.

Sort By: trending ▼ date
0
Undergraduate
By Shiva Kintali on May 19, 2013 | Updated Dec. 6, 2017

Randomized QuickSort

Consider Randomized-Quicksort operating on a sequence of \(n\) distinct input numbers. Prove that the expected running time of Randomized-Quicksort is \(O(n{\log}n)\) Prove that for any constant …
0
Graduate
By Shiva Kintali on June 10, 2012 | Updated Dec. 6, 2017

Card shuffling using pairwise-swapping

You are given a deck of \(n\) cards. In each step you select two cards independently and uniformly at random and swap their positions. This defines a random walk on the set of all permutations of the …
0
Undergraduate
By Shiva Kintali on May 19, 2013 | Updated Dec. 6, 2017

Generating random numbers

You are given a fair coin that comes up with heads (or tails) with probability 1/2. Using this fair coin, implement a random number generator \(Random(a,b)\) that returns an integer between \(a\) and …
0
Undergraduate
By Shiva Kintali on July 21, 2012 | Updated Dec. 6, 2017

Linear time shuffling

Consider the following algorithm to shuffle an array \(A\) of \(n\) elements (with indices from \(0\) to \(n-1\) : for \(i = 0\) to \(n - 1\) Let j be a random integer between 0 and i exchange A…
0
Undergraduate
By Shiva Kintali on June 6, 2012 | Updated Dec. 6, 2017

Reservoir Sampling

You are watching a stream of packets go by one at a time, and want to take a random sample of \(k\) distinct packets from the stream. You only have room to save \(k\) packets at any one time. You do…
Post Something
x

Select What You'd Like To Post

POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION

Content Types

Social learning platform. © 2016 True Group Inc. All Right Reserved