Implicit Recursive Slowdown

Prev: Data-Structural Bootstrapping

Prev: Data-Structural Bootstrapping

11.1 Queues and Deques

Exercises

Exercise 11.1

Implement lookup and update functions for these queues. Your functions should run in $O(\log i)$ amortized time. You may find it helpful to augment each queue with a size field.

Exercise 11.2

Implement double-ended queues using the techniques of this section.

11.2 Catenable Double-Ended Queues

Exercises

Exercise 11.3

Prove that both tail and init run in $O(1)$ amortized time by combining their respective debit allowances as suggested by implicit recursive slowdown.

Exercise 11.4

Given an implementation D of non-catenable deques, implement catenable lists using the type:

datatype a Cat =
    SHALLOW of a D.Queue
  | DEEP of a D.Queue * a CmpdElem Cat susp * a D.Queue
and a CmpdElem = CMPD of a D.Queue * a CmpdElem Cat susp

Both the front deque of a DEEP node and the deque in a CMPD node contain at least two elements. Prove that every function in your implementation runs in $O(1)$ amortized time, assuming that all the functions in D run in $O(1)$ time, worst-case or amortized.

11.3 Chapter Notes