Linear Data Structures

Question 1 (10)

(a) With capacity doubling from 1, resizes happen at sizes $1,2,4,8,\dots,2^{k}$ where $2^{k}<n$. Copy cost at each resize equals current element count: $\text{total copies} = \sum_{i=0}^{\lfloor\log_2 n\rfloor} 2^i = 2^{\lfloor\log_2 n\rfloor+1}-1 < 2n.$ Adding $n$ for the actual writes: total $= n + (2n-1) < 3n = O(n)$. Amortized per append $= O(n)/n = O(1)$. (3 for summation + evaluation, 2 for concluding amortized O(1))

(b) Fixed growth by $c$: resizes at sizes $c,2c,3c,\dots,n$, copy cost $\sum_{i=1}^{n/c} c\cdot i = c\cdot\frac{(n/c)(n/c+1)}{2} = \Theta(n^2/c).$ Total $\Theta(n^2)$ ⇒ amortized $\Theta(n)$ per append. Doubling makes resize count logarithmic and geometric copy cost sums to $\Theta(n)$; fixed growth makes it linear count with arithmetic cost sum $\Theta(n^2)$. (2 summation, 1 conclusion)

(c) Array elements are contiguous in memory, so sequential access loads whole cache lines (spatial locality) with few cache misses; linked-list nodes are scattered, causing a cache miss / pointer chase per node. (2)

Question 2 (12)

(a)

def insert_at_head(head, value):
    node = Node(value)
    node.next = head
    return node

(1 create, 1 link, 1 return new head)

(b)

def delete_value(head, target):
    if head is None:            # empty
        return None
    if head.data == target:     # target at head
        return head.next
    prev, cur = head, head.next
    while cur is not None:
        if cur.data == target:
            prev.next = cur.next   # unlink
            return head
        prev, cur = cur, prev.next
    return head                 # target absent

(1 empty, 1 head case, 2 traversal+unlink, 1 absent case)

(c)

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Time $O(n)$ (one pass), space $O(1)$ (three pointers). (3 code, 1 complexity)

Question 3 (10)

(a)

def balanced(s):
    stack = []
    pairs = {')':'(', ']':'[', '}':'{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

(2 push opens, 2 match on close, 1 final empty check)

(b) Input ([)]:

Returns False (verdict: not balanced). (3)

(c) A single counter tracks only how many brackets are open, not which type. ([)] has counter returning to 0 yet is invalid because types interleave incorrectly. A stack preserves the nesting order/type needed to verify correct matching. (2)

Question 4 (10)

(a) Precedence: * / > + -; all left-associative. Tokens of $A + B * C - D / E$:

(6 — deduct per wrong step)

(b) Final postfix: A B C * + D E / - (2)

(c) * / have higher precedence than + -; all are left-associative, so on a tie an incoming operator does not exceed the stack top and the stack operator is popped first. (2)

Question 5 (12)

(a)

def enqueue(x):
    if size == capacity:
        raise Overflow
    rear = (rear + 1) % capacity
    arr[rear] = x
    size += 1
 
def dequeue():
    if size == 0:
        raise Underflow
    x = arr[front]
    front = (front + 1) % capacity
    size -= 1
    return x

(3 enqueue incl. overflow+wrap, 3 dequeue incl. underflow+wrap)

(b) With only front and rear, the condition front == rear (or rear+1 == front) occurs both when the buffer is completely empty and completely full — indistinguishable. A size counter (or leaving one slot unused) removes the ambiguity. (3)

(c) Trace (cap 5, front=0, rear=-1):

• enq 10,20,30 → arr [10,20,30,_,_], front=0, rear=2, size=3
• dequeue → removes 10, front=1, size=2
• dequeue → removes 20, front=2, size=1
• enq 40 → rear=3, arr [10,20,30,40,_]
• enq 50 → rear=4, arr [10,20,30,40,50]
• enq 60 → rear=(4+1)%5=0, arr [60,20,30,40,50], size=4

Final: front = 2, rear = 0, array = [60, 20, 30, 40, 50]. (Indices 0,1 hold stale/overwritten values; only indices 2,3,4,0 are live: 30,40,50,60.) (3)

Question 6 (6)

(a) Operations: push_front, push_back, pop_front, pop_back. Use case: sliding-window maximum (monotonic deque), or an undo/redo browser history where both ends are accessed. (2 ops, 1 use case)

(b) FIFO queue dequeues strictly in insertion order (oldest first). A priority queue dequeues the element with the highest priority regardless of insertion time. Application: task/job scheduling, Dijkstra's shortest path. (2 difference, 1 application)

[
  {"claim":"Doubling total copies from cap 1 to n=1024 is less than 2n and equals 2047","code":"n=1024; k=n.bit_length()-1; total=sum(2**i for i in range(k+1)); result = (total==2047 and total<2*n)"},
  {"claim":"Fixed growth by c=1 gives sum of copies = n(n-1)/2 for n=1000, which is Theta(n^2)","code":"n=1000; c=1; total=sum(c*i for i in range(1,n//c)); result = (total == (n-1)*(n)//2 - 0 and total==sum(range(1,n)))"},
  {"claim":"Postfix of A+B*C-D/E has operators in order * + / -","code":"post=['A','B','C','*','+','D','E','/','-']; ops=[t for t in post if t in '+-*/']; result = ops==['*','+','/','-']"},
  {"claim":"Circular queue final rear index is 0 after the given operation sequence, cap 5","code":"cap=5; rear=-1; front=0; size=0\ndef enq():\n    global rear,size\n    rear=(rear+1)%cap; size+=1\ndef deq():\n    global front,size\n    front=(front+1)%cap; size-=1\nenq();enq();enq();deq();deq();enq();enq();enq()\nresult = (front==2 and rear==0)"}
]