the selection problem theoretical improvements for arithmetic problems dynamic programming using table instead of recursion ordering matrix multiplications optimal binary search tree all-pairs shortest path randomized algorithms random-number generators skip lists primality testing backtracking algorithms the turnpike reconstruction problem games summary exercises references amortized analysis an unrelated puzzle binomial queues skew heaps fibonacci heaps cutting nodes in leftist heaps lazy merging for binomial queues the fibonacci heap operations proof of the time bound splay trees summary exercises references advanced data structures and implementation top-down splay trees red-black trees bottom-up insertion top-down red-black trees top-down deletion treaps xiii