Bonus
Early implementations of this algorithm exhibited its worst-case runtime on sorted arrays, which can be avoided using the “median-of-three” rule. For 10 points each:
[10m] Name this divide-and-conquer algorithm that repeatedly partitions an array about a pivot, moves smaller values to the left of the pivot, and moves larger values to the right of the pivot.
ANSWER: quicksort [or partition-exchange sort; reject “exchange sort”]
[10e] A sorted list admits a search algorithm named for this word that also works by repeated partition. Computer science typically works in a base with this name, which is synonymous with base-2.
ANSWER: binary [accept binary search]
[10h] The parity of k partitions of a string of 2 to the k binary digits is checked in an “extended” error correction code named for this American computer scientist, which is robust when his namesake “distance” is at most 1.
ANSWER: Richard Hamming [accept Hamming code or extended Hamming code; accept Hamming distance]
<Editors, Other Science>
| Editions | Heard | PPB | Easy % | Medium % | Hard % |
|---|---|---|---|---|---|
| 2 | 125 | 14.48 | 95% | 31% | 18% |
Conversion
Summary
| Tournament | Edition | Exact Match? | Heard | PPB | Easy % | Medium % | Hard % |
|---|---|---|---|---|---|---|---|
| UK (North) | UK | Y | 5 | 22.00 | 100% | 60% | 60% |
| UK (South) | UK | Y | 7 | 20.00 | 100% | 43% | 57% |
| Northern California | US | Y | 4 | 15.00 | 100% | 25% | 25% |
| Southern California | US | Y | 7 | 18.57 | 100% | 57% | 29% |
| Eastern Canada (1) | US | Y | 5 | 10.00 | 80% | 0% | 20% |
| Eastern Canada (2) | US | Y | 9 | 14.44 | 100% | 33% | 11% |
| Florida | US | Y | 4 | 10.00 | 75% | 25% | 0% |
| Great Lakes | US | Y | 12 | 16.67 | 100% | 33% | 33% |
| Lower Mid-Atlantic | US | Y | 9 | 11.11 | 100% | 11% | 0% |
| Upper Mid-Atlantic | US | Y | 10 | 13.00 | 90% | 40% | 0% |
| Upper Mid-Atlantic | US | Y | 2 | 25.00 | 100% | 100% | 50% |
| Midwest | US | Y | 9 | 16.67 | 100% | 33% | 33% |
| North | US | Y | 4 | 17.50 | 100% | 50% | 25% |
| Northeast | US | Y | 11 | 10.91 | 82% | 18% | 9% |
| Pacific | US | Y | 8 | 8.75 | 88% | 0% | 0% |
| Southeast | US | Y | 13 | 13.85 | 100% | 31% | 8% |
| Upstate NY | US | Y | 6 | 13.33 | 100% | 33% | 0% |