Algorithm 3 simulator · Shuffle the toads

CSE301 · Homework 2 · Problem 3 · Algorithm 3

Shuffle the toads, then ask in order

n toads, strictly more than n/2 of them trustworthy.
The expert checks one toad in Θ(1) time.

p = t/n =4/7
The line
the toad expert

Random order
0 steps
Asks
0 asks
Algorithm 3 : FindTrustworthyToad3

Asks in each run

one runrunning average

Asks a run needed

t = the number of trustworthy toads (t > n/2), and p = t/n is their share. Gold line: in a random order the average stays under the bound 1/p = n/t asks; in the worst order (every tricky toad first) every run needs n − t + 1 asks.

Space play / pause  ·  Enter one run  ·  A keep playing  ·  Q +100 runs  ·  R reset  ·  F full screen  ·  the sliders change the number of toads and tricky toads