2. (15 marks) Consider the abstract datatype SEQ whose objects are sequences of elements and which...

  

Transcribed Image Text:

2. (15 marks) Consider the abstract datatype SEQ whose objects are sequences of elements and which supports two operations: PREPEND(x, S), which inserts element r 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 a PREPEND with probability p and an ACCESS with probability 1-p. For each ACCESS operation, the value of the parameter i is chosen uniformly from [1..|S|]. (d) (4 marks) Derive the expected number of steps taken to perform all n operations. 2. (15 marks) Consider the abstract datatype SEQ whose objects are sequences of elements and which supports two operations: PREPEND(x, S), which inserts element r 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 a PREPEND with probability p and an ACCESS with probability 1-p. For each ACCESS operation, the value of the parameter i is chosen uniformly from [1..|S|]. (d) (4 marks) Derive the expected number of steps taken to perform all n operations.

Answer rating: 100% (QA)

To derive the expected number of steps taken to perform all n operations we need to consider the exp... View the full answer