Question

Karp and Zhang used a parallel branch-and-bound algorithm with an input with this property to complete the node expansion step in dynamic task scheduling. The Karger-Stein minimum cut algorithm contracts a given graph by repeatedly taking an input with this property until only two nodes remain. Yao’s principle is typically used to prove lower bounds on the worst-case time complexity of algorithms with this property. (*) Quotient filters use a transformation with this property to hash keys to fingerprints. By construction, the initial population in a genetic algorithm has this property, and Las Vegas algorithms take inputs of this type. In quicksort, (10[1])the choice of pivot element is this type of input common in (10[1])non-deterministic algorithms. For 10 points, guessing and checking generally take in what type of input that may be outputted by an RNG? ■END■ (10[1])

ANSWER: randomized [accept random or randomly generated or pseudorandomly generated; accept stochastic]
<KJ, Other Science: Computer Science>
= Average correct buzz position

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
Dimitris KalafatisTAMUTexas B10010
Chinmay MurthyTexas Atag magnet: taylor's version11210
Pablo LloydHCCTexas C13510