Linear Data Structures

Question 1

(a) — 8 marks

Resizes happen when the array becomes full, at capacities $1, g, g^2, \dots, g^{k-1}$ (for $n=g^k$). At the resize from capacity $g^{i}$ we copy $g^{i}$ elements. Total copy cost: $C = \sum_{i=0}^{k-1} g^{i} = \frac{g^{k}-1}{g-1} = \frac{n-1}{g-1}.$ (2 marks for identifying resize points, 3 for the geometric sum.)

The problem statement's target $\dfrac{g(n-1)}{g-1}$ arises if copying is charged at the new capacity or if the first buffer copies $g$ elements; using the standard model $C=\frac{n-1}{g-1}$. Accept either provided the geometric series is correct. (1 mark.)

Amortized copy per append $= C/n = \frac{n-1}{n(g-1)} < \frac{1}{g-1} = O(1)$, a constant independent of $n$. Adding the $n$ store operations (cost $n$), total $= n + \frac{n-1}{g-1}$, amortized $= 1 + \frac{1}{g-1} = \frac{g}{g-1}$, constant. ∴ $O(1)$ amortized. (2 marks.)

(b) — 8 marks

Doubling case $g=2$. Potential $\Phi = 2\cdot\text{size} - \text{capacity}$.

• Initially size$=0$, capacity chosen so $\Phi \ge 0$; after first element size$=1=$capacity so $\Phi=2-1=1\ge 0$. When size $\ge$ capacity/2, $\Phi = 2s-c \ge 2(c/2)-c = 0$. Valid (non-negative). (2 marks.)

Append without resize: actual cost $=1$ (one store). size increases by 1, capacity constant: $\Delta\Phi = 2$. Amortized $= 1 + 2 = 3$. (2 marks.)

Append with resize: just before, size$=$capacity$=c$, so $\Phi_{before}=2c-c=c$. Actual cost $= c$ (copies) $+1$ (store) $=c+1$. After: size$=c+1$, capacity$=2c$, $\Phi_{after}=2(c+1)-2c=2$. $\Delta\Phi = 2-c$. Amortized $= (c+1)+(2-c)=3$. (3 marks.)

Both cases give amortized $=3$. Since $\Phi\ge0=\Phi_{init}$ always, sum of amortized $\ge$ sum of actual, so amortized total upper-bounds real total. ∴ amortized $=3=O(1)$. (1 mark.)

(c) — 6 marks

Out of $B$ consecutive accesses to a contiguous array, 1 is a miss ($t_m$) and $B-1$ are hits ($t_h$): $\bar t = \frac{(B-1)t_h + t_m}{B} = \frac{(B-1)t_h + (t_h+\tau)}{B} = t_h + \frac{\tau}{B}.$ (4 marks.) As $B\to\infty$, $\bar t \to t_h$ (perfect locality amortizes the penalty). For a scattered linked list, each node lives on its own line, so essentially every access is a miss: effective $B\to 1$, giving $\bar t \to t_h + \tau$. Thus arrays exploit spatial cache locality that pointer-chasing lists cannot. (2 marks.)

Question 2

(a) — 8 marks

prec: +,- → 1 ;  *,/ → 2 ;  ^ → 3
rightAssoc(^) = true, else false
function toPostfix(tokens):
  out = []; op = emptyStack
  for t in tokens:
    if t is operand: out.append(t)
    elif t == '(': op.push('(')
    elif t == ')':
       while op.top != '(': out.append(op.pop())
       op.pop()                       # discard '('
    else:  # t is an operator
       while (not op.empty) and op.top != '(' and
             ( prec[op.top] > prec[t] or
               (prec[op.top]==prec[t] and not rightAssoc(t)) ):
           out.append(op.pop())
       op.push(t)
  while not op.empty: out.append(op.pop())
  return out

(4 for structure, 2 for correct precedence comparison, 2 for right-associativity handling.)

(b) — 7 marks

Invariant: Just before reading each token, reading top-to-bottom, the operators on the stack (ignoring ( markers) appear in non-increasing precedence order, with strict ordering enforced except that equal-precedence right-associative operators may stack. Equivalently: every operator already emitted to out was popped before any operator of strictly lower precedence that governs the same operands.

Proof (induction on tokens):

• Base: empty stack — vacuously true. (1)
• Operand/(: pushing ( inserts a barrier; operands don't touch operator ordering — invariant holds. (1)
• Operator $t$: the while pops every stacked operator with prec > prec[t], and for left-assoc also prec == prec[t]. After popping, all remaining stacked operators have prec < prec[t] (or = prec[t] if $t$ right-assoc). Pushing $t$ therefore keeps the stack non-increasing. Because higher/equal-precedence operators were emitted first, they act on their operands before lower-precedence ones — this is exactly correct evaluation order. (3)
• ): pops everything down to matching (, which preserves the order property within that parenthesized subexpression. (1) ∴ At termination every operator is popped in correct precedence/associativity order, giving valid postfix. (1)

(c) — 5 marks

Convert $3 + 4 \times 2 \wedge 2 \wedge 3 - 1$:

Final postfix: 3 4 2 2 3 ^ ^ × + 1 − Value check: $2^{2^3}=2^8=256$, $4\times256=1024$, $+3=1027$, $-1=1026$. (3 for trace, 2 for final string.)

Question 3

(a) — 7 marks

Fields: head (index of front), count, array A[0..m-1].

enqueue(x): if count==m: overflow
            A[(head+count) mod m] = x; count += 1
dequeue():  if count==0: underflow
            x = A[head]; head = (head+1) mod m; count -= 1; return x
size(): return count

(3 marks.) Both are $O(1)$ (only modular arithmetic). Invariant $0\le count\le m$: enqueue increments only when count$<m$ (guard), dequeue decrements only when count$>0$; both stay in range. (2) FIFO: enqueue writes at logical position head+count (tail); dequeue reads at head (front) then advances. The first element written is at head and is read first; the $(k)$th enqueued element sits at offset $k-1$ from head and is dequeued only after the previous $k-1$. Hence order preserved. (2)

(b) — 11 marks

Deque simulates stack: use only pushFront/popFront (or only back operations) → LIFO. (1) Deque simulates queue: pushBack to enqueue, popFront to dequeue → FIFO. (1) So a deque is strictly more general. (1)

Single stack cannot give FIFO in O(1): A stack exposes only its top. To dequeue the oldest (bottom) element while elements remain above it, you must remove and later restore all $k-1$ elements above it — $\Theta(k)$ work, and this cannot be amortized away with a single stack because after restoring, the same worst case recurs on the next dequeue interleaved with enqueue (adversary alternates enqueue/dequeue keeping one element resident, forcing repeated full transfers). No potential can absorb this since the LIFO exposure order is the exact reverse of the required removal order and there is no second buffer to hold the reversed sequence. Hence worst-case amortized cost is $\Omega(n)$. (4)

Two stacks achieve amortized O(1): Keep in and out. enqueue(x): in.push(x) — O(1). dequeue(): if out empty, pop all of in into out (reversing order → oldest on top), then out.pop(). (2) Amortized proof (potential): $\Phi = |in|$. enqueue: actual 1, $\Delta\Phi=1$ → amortized 2. dequeue with transfer of $j$ elements: actual $= j\ (\text{pops}) + j\ (\text{pushes}) + 1 = 2j+1$; $\Delta\Phi = -j$ → amortized $= 2j+1 - j = j+1$... use $\Phi=2|in|$: transfer amortized $=(2j+1)-2j=1$; enqueue amortized $=1+2=3$. Each element moved at most once from in to out, so all operations are $O(1)$ amortized. (2)

[
  {"claim":"Total copy cost sum_{i=0}^{k-1} g^i = (g^k-1)/(g-1), n=g^k=8,g=2 -> 7",
   "code":"g=2;k=3;n=g**k;C=summation(g**i,(i,0,k-1));result=(C==(n-1)) and (simplify(C-(g**k-1)/(g-1))==0)"},
  {"claim":"Amortized append cost with potential 2*size-capacity equals 3 in both cases",
   "code":"c=symbols('c',positive=True); no_resize=1+2; resize=(c+1)+((2)-c); result=(no_resize==3) and (simplify(resize-3)==0)"},
  {"claim":"Average access time (B-1)*th + tm over B with tm=th+tau equals th+tau/B",
   "code":"th,tau,B=symbols('th tau B',positive=True); tbar=((B-1)*th+(th+tau))/B; result=simplify(tbar-(th+tau/B))==0"},
  {"claim":"Postfix of 3+4*2^2^3-1 evaluates to 1026",
   "code":"val=3+4*(2**(2**3))-1; result=val==1026"}
]