Question
Answer the following about the Robert Tarjan and Daniel Sleator-created splay tree, for 10 points each.
[10e] Splay trees belong to a class of trees named for this algorithm, in which nodes less than the root are in the left subtree. This algorithm finds an element in a sorted array in O(log n) time by repeatedly comparing it to the middle.
ANSWER: binary search [accept binary search trees; prompt on search]
[10m] The “splay” operation executes “zig” and “zig-zag” steps by performing these operations to center the queried element. Self-balancing BSTs such as AVL trees perform “left” and “right” instances of these operations.
ANSWER: tree rotations [accept left rotation or right rotation]
[10h] The hypothetical runtime of a splay tree used as a deque is given by the minimum number of applications of this function of n that yields a constant. Tarjan proved that a sequence of operations on an union-find structure has runtime proportional to this function of the number of nodes.
ANSWER: inverse Ackermann function [prompt on a or alpha; reject “Ackermann function”]
<Science - Other Science - Math>
Summary
| 2024 ARGOS @ Brandeis | 03/22/2025 | Y | 2 | 5.00 | 50% | 0% | 0% |
| 2024 ARGOS @ Chicago | 11/23/2024 | Y | 6 | 15.00 | 83% | 50% | 17% |
| 2024 ARGOS @ Christ's College | 12/14/2024 | Y | 3 | 13.33 | 67% | 33% | 33% |
| 2024 ARGOS @ Columbia | 11/23/2024 | Y | 2 | 20.00 | 100% | 100% | 0% |
| 2024 ARGOS @ Stanford | 02/22/2025 | Y | 3 | 20.00 | 100% | 67% | 33% |
| 2024 ARGOS Online | 03/22/2025 | Y | 3 | 16.67 | 100% | 67% | 0% |
Data
| CLEVELAND, THIS IS FOR YOU! | I wish it were possible to freeze time so I would never have to watch you retire | 10 | 10 | 0 | 20 |
| Thompson et al. | UBC | 10 | 0 | 0 | 10 |
| throw away your cards, rally in the streets | Aw we're so sorry to hear that maman died today, she gets five big booms | 10 | 10 | 0 | 20 |