Previous bonus - Next bonus

Packet J: Bonus 10

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> | Packet J

HeardPPBE %M %H %
13114.5095%31%19%

Back to bonuses

Conversion

TeamOpponentPart 1Part 2Part 3TotalParts
Binghamton ARIT B010010E
Binghamton CRochester010010E
Cornell CBinghamton B1010020ME
Cornell DCornell A1010020ME
ESFRIT A010010E

Summary

TournamentEditionMatchHeardPPBE %M %H %
Northern CaliforniaMain✓415.00100%25%25%
Southern CaliforniaMain✓718.57100%57%29%
Eastern Canada (1)Main✓510.0080%0%20%
Eastern Canada (2)Main✓914.44100%33%11%
FloridaMain✓410.0075%25%0%
Great LakesMain✓1216.67100%33%33%
Lower Mid-AtlanticMain✓911.11100%11%0%
Upper Mid-AtlanticMain✓1013.0090%40%0%
Upper Mid-AtlanticMain✓225.00100%100%50%
MidwestMain✓916.67100%33%33%
NorthMain✓417.50100%50%25%
NortheastMain✓1110.9182%18%9%
PacificMain✓88.7588%0%0%
South CentralMain✓714.29100%14%29%
SoutheastMain✓1313.85100%31%8%
Upstate NYMain✓514.00100%40%0%
UK (North)UK✓522.00100%60%60%
UK (South)UK✓720.00100%43%57%