#data-structures

For a sequence $S$ of accesses to keys in a binary search tree with $n$ keys, let $\mathrm{OPT}(S)$ be the minimum total cost of serving $S$ by any binary search tree algorithm that may rotate the tree, even one that knows $S$ in advance. Prove or disprove that splay trees serve every access…

A singly linked list either ends in a null pointer or eventually loops back into itself. Using $\mathcal{O}(1)$ extra memory and time linear in the number of nodes, decide whether it has a cycle, and if it does, find the first node on the cycle and the cycle length.