Question

When performing this action, careful indexing of the median element must be performed in order to avoid an accidental integer overflow. For 10 points each:
[10h] Name or describe this task, often performed using Robert Sedgewick’s “median of three” rule, that is performed to improve the runtime of an algorithm with an average-case runtime of O(n log n) (“Big O of n log n”).
ANSWER: pivot selection for Quicksort [reject “Quicksort” on its own; prompt on pivot selection by asking “for which algorithm?”; prompt on optimizing Quicksort, making Quicksort faster, or similar answers]
[10m] Early implementations of quicksort chose the first element of the array as a pivot, which would produce this worst-case runtime for pre-sorted lists. In Big O notation, this is also the average-case runtime of bubble sort.
ANSWER: O(n^2) [or quadratic runtime]
[10e] Quicksort’s relative slowness for arrays with many repeated elements is a problem named after one of these physical objects. A naval communication system using these objects inspired Edsger Dijkstra to create semaphores.
ANSWER: flags (The aforementioned problem is the Dutch National Flag problem.)
<DM>

Back to bonuses

Summary

2023 BHSU @ Berkeley03/18/2023Y326.67100%100%67%
2023 BHSU @ Maryland03/11/2023Y316.6767%100%0%
2023 BHSU @ Northwestern02/25/2023Y621.67100%83%33%
2023 BHSU Online04/15/2023Y417.5075%100%0%
2023 BHSU @ Sheffield04/15/2023Y225.00100%100%50%
2023 BHSU @ Waterloo04/15/2023Y316.6767%67%33%
2023 BHSU @ Yale04/08/2023Y326.67100%100%67%

Data

Neg 5! Playing Quizbowl, Liddy StyleCameron et al.0101020
Parth et al.The Passion According to C.H.0000
The Vulture's Guide to BuzzMilan et al.10101030