Description
Consider the abstract datatype SEQ whose objects are sequences of elements and which supports
two operations:
• PREPEND(x, S), which inserts element x at the beginning of the sequence S and
• ACCESS(S, i), which returns the i’th element in the sequence.
Suppose that we represent S by a singly linked list. Then PREPEND(x, S) takes 1 step and
ACCESS(S, i) takes i steps, provided S has at least i elements.
Suppose that S initially has exactly one element. A sequence of n operations are performed.
Each operation in the sequence is (independently) chosen to be an ACCESS with probability q and
a PREPEND with probability 1 − q, where 0 < q < 1. For each ACCESS operation, the value of
the parameter i is chosen uniformly from [1..|S|].
1. Let 0 ≤ k ≤ n. Determine the expected length of the linked list after k operations have been
performed.
2. Let 0 ≤ k ≤ n. Determine the expected number of steps taken to perform the k’th operation.
3. Determine the expected number of steps taken to perform all n operations.
Justify your answers. Remember to begin by describing the relevant probability space(s) and
defining appropriate random variables.
1
