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>
Summary
| 2023 BHSU @ Berkeley | 03/18/2023 | Y | 3 | 26.67 | 100% | 100% | 67% |
| 2023 BHSU @ Maryland | 03/11/2023 | Y | 3 | 16.67 | 67% | 100% | 0% |
| 2023 BHSU @ Northwestern | 02/25/2023 | Y | 6 | 21.67 | 100% | 83% | 33% |
| 2023 BHSU Online | 04/15/2023 | Y | 4 | 17.50 | 75% | 100% | 0% |
| 2023 BHSU @ Sheffield | 04/15/2023 | Y | 2 | 25.00 | 100% | 100% | 50% |
| 2023 BHSU @ Waterloo | 04/15/2023 | Y | 3 | 16.67 | 67% | 67% | 33% |
| 2023 BHSU @ Yale | 04/08/2023 | Y | 3 | 26.67 | 100% | 100% | 67% |
Data
| Magisters Ludi | Broken Imperial Nomads | 0 | 10 | 10 | 20 |
| Oxford Hornets | Buzzers Karamazov | 10 | 10 | 10 | 30 |