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 - Computer Science>
Summary
| 2024 ARGOS @ McMaster | 11/17/2024 | Y | 4 | 22.50 | 100% | 75% | 50% |
Data
| Communism is Soviet power plus the yassification of the whole country | Moderator Can't Neg me While in Alpha | 10 | 0 | 0 | 10 |
| Simpson Agonistes: The Crisis of Donut | She Dicer On My Argonaute Till I RNA Interfere | 10 | 10 | 10 | 30 |
| Tensei Shitara Flashcard Data Ken | I'd prefer to have the team name be Christensen et al. than anything that Erik cooks up | 10 | 10 | 0 | 20 |
| You cannot go to Aarhus to see his peat-brown head / With eyes like ripening fruit | The Only Existing Manuscript from A Clockwork Orange | 10 | 10 | 10 | 30 |