• Exercises
  • Multiple Choice
  • Articles
  • Open Problems
  • Login
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 …
  • Computer Science
  • Algorithms
  • Randomized Algorithms
  • expectation
  • sorting
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 …
  • Computer Science
  • Randomized Algorithms
  • canonical paths
  • coupling
  • random walk
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…
  • Computer Science
  • Randomized Algorithms
  • linear time algorithms
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 …
  • Computer Science
  • Randomized Algorithms
  • generator
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…
  • Computer Science
  • Randomized Algorithms
  • sampling
  • icon Sign In or Sign Up
  • icon Invite Friends
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

  • Articles
  • Open Problems
  • Exercises
  • Multiple-Choice Questions

Levels

  • High school
  • Undergraduate
  • Graduate

Subjects

  • Mathematics
  • Computer Science
  • Puzzles
  • Optimization

Trending tags

  • primes
  • formal languages
  • trees
  • dynamic programming
  • polynomials
  • infinite series
  • digraphs
  • fermats little theorem
  • asymptotic analysis
  • differentiation

Topics

  • Algebra
  • Algorithms
  • Approximation Algorithms
  • Calculus
  • Combinatorial Optimization
  • Combinatorics
  • Complexity Theory
  • Data Structures
  • Discrete Mathematics
  • Game Theory
  • Geometry
  • Graph Theory
  • Linear Algebra
  • Linear Programming
  • Logic
  • Mathematical Analysis
  • Mathematics
  • Matrix Theory
  • Number Theory
  • Optimization
  • Probability
  • Programming
  • Puzzles
  • Randomized Algorithms
  • Real Analysis
  • Trigonometry
Home
Team Terms of Service Privacy Policy Careers Contact Us
Tags Topics IIT JEE Problems International Mathematical Olympiad
Twitter Instagram Slack Telegram
Social learning platform. © 2016 True Group Inc. All Right Reserved