Randomised Algorithms and the Probabilistic Method · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Luck with a proof attached

Computing · Algorithms & Data Structures · ages 22-23
Name ______________________   Date ____________

  1. Which routine is always correct and sometimes slow?

    • A Las Vegas routine
    • A Monte Carlo routine
    • A deterministic routine with no coins

  2. A random coloring works with positive chance. What follows?

    • Every coloring works
    • At least one good coloring exists
    • No coloring can work

  3. Randomized quicksort averages n log n on any input, with only unlucky coins slowing it.

    Circle one:   True   False

  4. A Monte Carlo test errs with small chance per run. How do you shrink the error?

    • Run it once and trust the speed
    • Remove the coins and hope
    • Repeat it and combine the runs

  5. What is expected running time counted over?

    • The coin flips, on a worst-case input
    • The input size, on lucky coins only
    • The programmer's patience across edits

  6. Failure chance is bounded below one. What does the bound buy?

    • A proof that success sits somewhere
    • A faster computer for the search
    • A list of every failing case

  7. A manager demands a routine that is both always fast and always right. What do you tell them?

    • Coins grant both at once for every problem
    • Randomness trades one for the other: fixed speed or certainty must give
    • Deterministic code already guarantees both

  8. A team needs a tournament schedule with a rare property. Counting all schedules is hopeless. Which plan fits the method?

    • Build one schedule by hand and declare it good
    • Draw one at random, bound the failure chance below one, and conclude one exists
    • Ask every team to vote on their favorite schedule
LightMySky · lightmysky.comW1-mt_4ShN_WlT0--s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Luck with a proof attached W1-mt_4ShN_WlT0--s1

  1. A Las Vegas routine · Correctness stays fixed while only the running time wobbles.
  2. At least one good coloring exists · Positive chance needs somewhere for the luck to land.
  3. True · Chance spreads over flips while the input stays adversarial.
  4. Repeat it and combine the runs · Repeats multiply small chances into tiny ones.
  5. The coin flips, on a worst-case input · The adversary picks the list and chance does the rest.
  6. A proof that success sits somewhere · Chance of failure under one leaves room where success must live.
  7. Randomness trades one for the other: fixed speed or certainty must give · Las Vegas surrenders fixed speed, Monte Carlo surrenders certainty.
  8. Draw one at random, bound the failure chance below one, and conclude one exists · The random draw plus the bound turns chance into an existence proof.
Worksheet · LightMySky