Linear Data Structures

Question 1 (12)

(a) Growth by ⌈1.5×cap⌉ from cap 1: 1 → 2 → 3 → 5 → 8 → 12 → 18 → 27. Sequence of capacities passed through until ≥20: 1, 2, 3, 5, 8, 12, 18, 27. (3: correct rounding & stopping at 27)

(b) Copies happen at each resize = old size copied. Resizes occur when going from cap 1→2 (copy 1), 2→3 (copy 2), 3→5 (copy 3), 5→8 (copy 5), 8→12 (copy 8), 12→18 (copy 12), 18→27 (copy 18). We need capacity ≥20, so we grow up to 27. Total copies = 1+2+3+5+8+12+18 = 49. (4: correct set of resizes 2, correct sum 2)

(c) Growing by +1 each fill: appending $n$ elements triggers a resize almost every append, total copies $\approx \sum_{i=1}^{n} i = \Theta(n^2)$, so amortized cost per append is $O(n)$ (not constant). (3)

(d) Array elements are contiguous in memory, so sequential access loads whole cache lines and prefetching works; linked-list nodes are scattered, causing cache misses per hop. (2)

Question 2 (14)

(a) Shunting-yard on A + B * C - ( D / E + F ) * G:

• A → output: A
• + → stack:+
• B → A B
• * (higher than +) → stack:+ *
• C → A B C
• -: pop *,+ (both ≥ -) → output A B C * +; push -. stack:-
• ( → stack:- (
• D → A B C * + D
• / → stack:- ( /
• E → A B C * + D E
• + inside: pop / (higher) → output ... D E /; push +. stack:- ( +
• F → A B C * + D E / F
• ): pop until ( → pop + → output ... F +; discard (. stack:-
• * → stack:- *
• G → append G
• end: pop *,-

Postfix: A B C * + D E / F + G * - (6)

(b) Just after the inner + is processed, stack (bottom→top): - ( +. (3)

(c) Values A=6,B=2,C=3,D=8,E=4,F=1,G=5. Tokens: A B C * + D E / F + G * -. Value stack after first five tokens:

(5: 1 each row) Full evaluation continues: D E / = 8/4=2, F=1, + =3, ×G(5)=15, then 12−15 = −3.

Question 3 (12)

(a) Use a queue (or ring buffer) to hold the window elements in insertion order, plus a monotonic decreasing deque of candidate maxima. The deque's front is always the current max. (3)

(b)

insert(x):
    if count == k:          # evict oldest
        old = queue.dequeue()
        if maxdq.front == old:
            maxdq.pop_front()
        count -= 1
    while not maxdq.empty and maxdq.back < x:
        maxdq.pop_back()
    maxdq.push_back(x)
    queue.enqueue(x)
    count += 1

max():
    return maxdq.front

(6: correct eviction 2, correct monotonic maintenance 2, max()=front 2)

(c) Each element is pushed to and popped from the max-deque at most once, so over $m$ inserts total deque work is $O(m)$ → amortized $O(1)$ per insert, max is $O(1)$. (3)

Question 4 (12)

(a) Three-phase technique:

1. Find middle with slow/fast pointers, split into two halves.
2. Reverse the second half in place.
3. Merge the two halves alternately. (5)

(b)

reorder(head):
    if head==null or head.next==null: return
    # 1. find middle
    slow=head; fast=head
    while fast.next and fast.next.next:
        slow=slow.next; fast=fast.next.next
    second = slow.next; slow.next = null
    # 2. reverse second half
    prev=null
    while second:
        nxt=second.next; second.next=prev; prev=second; second=nxt
    # 3. merge
    first=head; second=prev
    while second:
        f2=first.next; s2=second.next
        first.next=second; second.next=f2
        first=f2; second=s2

(5)

(c) Time $O(n)$, space $O(1)$. Harder than an array because a singly linked list has no random access / backward links, so index $L_{n-i}$ can't be reached in $O(1)$ — hence the reverse-and-merge trick. (2)

Question 5 (10)

(a) rear = next free slot, arithmetic mod 8.

• enqueue×6: rear=6, count=6, front=0
• dequeue×4: front=4, count=2, rear=6
• enqueue×5: rear=(6+5)mod8=3, count=7, front=4
• dequeue×2: front=6, count=5, rear=3

Final: front=6, rear=3, count=5. (5: front 2, rear 2, count 1)

(b) With only front and rear, the condition front==rear occurs both when the queue is empty and when it is completely full, so the two states are indistinguishable. A count variable (or leaving one slot unused) resolves the ambiguity. (3)

(c) Fixed-size streaming/producer-consumer buffers: e.g. audio/network packet buffers, keyboard input buffer, or a bounded log — reuses memory with no reallocation. (2)

[
  {"claim":"Q1b total copies for growth to hold 20 elements = 49","code":"cap=1; total=0\nwhile cap<20:\n    total+=cap\n    cap=-(-3*cap//2)  # ceil(1.5*cap)\nresult = (total==49)"},
  {"claim":"Q1a capacity sequence is 1,2,3,5,8,12,18,27","code":"seq=[1]; cap=1\nwhile cap<20:\n    cap=-(-3*cap//2)\n    seq.append(cap)\nresult = (seq==[1,2,3,5,8,12,18,27])"},
  {"claim":"Q2c postfix evaluation of A B C * + D E / F + G * - equals -3","code":"vals={'A':6,'B':2,'C':3,'D':8,'E':4,'F':1,'G':5}\ntokens='A B C * + D E / F + G * -'.split()\nst=[]\nimport operator\nops={'+':operator.add,'-':operator.sub,'*':operator.mul,'/':lambda a,b:a//b}\nfor t in tokens:\n    if t in ops:\n        b=st.pop(); a=st.pop(); st.append(ops[t](a,b))\n    else:\n        st.append(vals[t])\nresult = (st[-1]==-3)"},
  {"claim":"Q5a final front,rear,count = 6,3,5","code":"N=8; front=0; rear=0; count=0\ndef enq():\n    global rear,count; rear=(rear+1)%N; count+=1\ndef deq():\n    global front,count; front=(front+1)%N; count-=1\nfor _ in range(6): enq()\nfor _ in range(4): deq()\nfor _ in range(5): enq()\nfor _ in range(2): deq()\nresult = (front==6 and rear==3 and count==5)"}
]