Notation: cell(k) = (front + k) mod N. Invariant I: for 0 ≤ k < size, data[cell(k)] holds the k-th item (k = 0 the oldest), and every other cell holds None.

(a) Suppose 0 ≤ k < l ≤ N − 1 and cell(k) = cell(l). Then (front + k) ≡ (front + l) (mod N), so N divides l − k. But 0 < l − k < N, so this is impossible. Hence cell(0), …, cell(N−1) are pairwise different: the N cells are visited exactly once each as k runs from 0 to N − 1.

(b) Empty queue: size = 0, so I says that every cell holds None, which is how the array is created. ✓ enqueue with size < N: the item goes to r = (front + size) mod N = cell(size). By (a), cell(size) differs from cell(k) for every k < size, so by I the cell r holds None: nothing is overwritten. After the call the size is size + 1 and the item is at cell(size), the new last position; the other items are untouched, so I holds. dequeue with size > 0: the call returns data[front] = data[cell(0)], the oldest item, sets that cell to None, sets front′ = (front + 1) mod N and size′ = size − 1. Now cell′(k) = (front′ + k) mod N = cell(k + 1), so the items that were at positions 1 … size − 1 are at positions 0 … size′ − 1 under the new front. The vacated cell(0) is not among cell′(0..size′−1) = cell(1..size−1), by (a), and it holds None. So I holds. ∎

(c) Before the copy size = N. The copy walks the old array from front in queue order and stores item k in cell k of the new array of capacity 2N, then sets front = 0. Then cell′(k) = (0 + k) mod 2N = k for k < N = size, so item k is at cell′(k) and the cells N … 2N − 1 hold None: I holds for the new array. The enqueue then continues as in (b) with size = N < 2N.

(d) If only front and rear = (front + size) mod N are stored, the empty queue (size 0) and the full queue (size N) have the same rear: (front + 0) mod N = (front + N) mod N. So the pair (front, rear) cannot tell empty from full. Counting: the queue has N · (N + 1) states (N values of front, N + 1 values of size) but the pair (front, rear) takes only N · N values, so some states must share a pair. The fix is to store size (as the code does), or a boolean flag, or to leave one cell always unused (capacity N − 1 effectively).

(a) Stack invariant S(p): after the first p characters, if the checker has not returned False, the stack holds exactly the positions of the openers among them that have not been popped, in increasing order from bottom to top. Induction on p. p = 0: both are empty. Step p → p + 1 with character c:

• c is an opener: it is pushed, and its position is larger than every position already on the stack, so the order is kept and the stack is the old set plus this opener. ✓
• c is a closer: if the stack is empty the checker returns False, which the statement excludes. Otherwise it pops the top, the largest position on the stack; if the kinds differ it returns False (excluded); else the stack is the old stack without its top, still in increasing order, and the popped opener is no longer unpopped. ✓
• c is another character: nothing changes. ✓

(b) True ⇒ balanced. Let P be the set of pairs (position of the popped opener, position of the closer), one per closer. Each pair has i < j (the opener was read before), the kinds match (otherwise False), every closer is in exactly one pair (it pops exactly one opener, otherwise False at an empty stack), and every opener is in exactly one pair: an opener that was pushed is either popped once, or is still on the stack at the end, but the checker returned True only because the stack is empty at the end. No crossing: suppose (i, j) and (k, l) in P with i < k < j < l. When the closer at j is read, S says that the stack is in increasing position order and that j pops i. The opener at k satisfies i < k < j, so k was pushed after i and before j; it is not popped before j (its pop happens at l > j), so it is on the stack at that moment and above i (larger position). But j pops the top of the stack, which is above i: it would pop k or something above k, not i. Contradiction. So P is a nesting. ∎

(c) Balanced ⇒ True. Let P be a nesting. Claim: the brackets strictly between a pair (i, j) are paired among themselves. Take a bracket at k with i < k < j and its partner m. If k is an opener then m > k; m > j would give i < k < j < m, a crossing, so m < j. If k is a closer then m < k; m < i would give m < i < k < j, a crossing, so m > i. Either way m is also strictly between i and j. Now run the checker. Claim: at every closer at position j with partner i in P, the checker finds i on top of the stack, so the pop succeeds and the kinds match (P pairs equal kinds). Proof by induction on the closers in left-to-right order. At the time j is read, i has been pushed and not popped: the only closer that can pop it is j, because by the induction hypothesis every earlier closer popped its own partner (which is not i). Every opener at k with i < k < j has been popped already, because its partner is a closer before j (by the first claim), which popped it by the induction hypothesis. So the top of the stack is i. At the end every opener has been popped by its own partner, so the stack is empty and the checker returns True. ∎

(d) ([)]: at ) the top of the stack is [; the line that compares the kinds of opener and closer returns False (mismatch). ()): at the second ) the stack is empty; the check "stack empty at a closer" returns False (underflow: nothing to match). ((()): all three closers match, but at the end one ( is still on the stack; the final return stack is empty is False (leftover opener). The same loop catches all three; counting openers and closers cannot: ([)] has one of each kind.

(a) Invariant: reading outbox from top to bottom, followed by inbox from bottom to top, lists the queue from front to rear. Empty: both empty. enqueue(x) pushes x on top of inbox, which is its last position in "bottom to top" reading: x is appended at the rear. ✓ dequeue with outbox non-empty: pops the top of outbox, which is the first item in the reading, i.e. the front. ✓ dequeue with outbox empty: the queue is inbox bottom to top, say x₁ … xₘ. Popping inbox yields xₘ, …, x₁ and pushing them on outbox leaves x₁ on top: reading outbox top to bottom gives x₁ … xₘ and inbox is empty, so the reading is unchanged. ✓ Then the pop takes x₁, the front. ∎

(b) Put n items in with enqueue (cost n), then dequeue: it pops n items from inbox (n), pushes n on outbox (n) and pops one (1): 2n + 1 = Θ(n) for this one call.

(c) Charge 4 coins per enqueue and 0 per dequeue. An enqueue spends 1 coin on its own push and stores 3 coins on the new item. Over its life an item can cause only these operations: its push on inbox (paid by the enqueue), its pop from inbox and its push on outbox during a transfer, and its pop from outbox by a dequeue. An item moves from inbox to outbox at most once, because items leave outbox only by being dequeued and nothing ever goes back. So the three remaining operations cost at most 3 coins per item, exactly what it stores. Every dequeue's work is the sum of those operations, so the stored coins pay for all of it and the account never goes negative. A sequence with e enqueues therefore costs at most 4e in total (dequeues that find an empty queue are errors and are not counted). Since the number of dequeues is at most e, the total over all operations is at most 4e ≤ 4 · (number of operations), so the amortized cost per operation is O(1). (Run it: test_ex3_claims.py counts the unit operations on random sequences and checks cost ≤ 4e.)

(d) In the variant, each enqueue first moves everything from outbox back to inbox, and each dequeue moves everything from inbox to outbox. Start with n items in the queue and alternate dequeue, enqueue n times: every dequeue transfers the whole queue (about n − 1 or n items, each costing 2) and every enqueue moves it back (again about 2n), so each pair costs about 4n and the 2n operations cost about 4n² = Θ(n²), against at most 4n for the real design. The argument of (c) breaks because an item can now move many times.

For (e) keep in the deque the indices of the readings that can still become the maximum of a future window, so that their values decrease from front to rear. For each new reading a[i]: remove from the rear every index whose value is ≤ a[i] (it can never be the maximum while a[i] is in the window, because a[i] is newer and at least as large); append i; if the front index is i − k (it fell out of the window), remove it from the front; once i ≥ k − 1 the maximum of the current window is a[front]. Example a = 1, 3, −1, −3, 5, 3, 6, 7 with k = 3 gives 3, 3, 5, 5, 6, 7. Each index is appended once and removed at most once, so there are at most 2n deque operations, each O(1): O(n) in total, against O(nk) for rescanning every window. (test_ex3_claims.py checks the example, compares with brute force and counts the operations.)

(a) Keep the items on main and, on mins, those items that are at most every item below them.

push(x):  main.push(x);  if mins is empty or x <= mins.top():  mins.push(x)pop():    x = main.pop();  if x == mins.top():  mins.pop();  return xmin_value():  return mins.top()

(b) Invariant: mins contains exactly the items of main that are ≤ every item below them in main, in the same order; in particular mins.top() = the minimum of main (and mins is empty iff main is). Push of x: if x ≤ the current minimum (mins.top()), x is ≤ everything below it, so it belongs to mins and is pushed there, and it is the new minimum; otherwise x has a smaller item below it, so it does not belong, mins is unchanged and the minimum is unchanged. Pop of x: the top item x of main has the property "≤ everything below" exactly when x equals mins.top() (if it has the property it is the last such item in order, so it is mins.top(); if it does not, some item below is strictly smaller, so the minimum of main, which is mins.top(), is smaller than x and differs from it). So testing x == mins.top() decides correctly whether x must leave mins, and after the pop the invariant holds again. Every operation does at most one push or pop on each stack: O(1) worst-case. ∎

(c) With < instead of ≤: push 2, push 2, pop. After the pushes mins holds only the first 2 (the second was not smaller). The pop removes a 2 from main, sees that it equals mins.top() and pops mins, which is now empty, although main still holds a 2: min_value() fails (or returns garbage). With ≤ both 2s are on mins, and one stays after the pop. (Checked in test_ex3_claims.py.)

(d) Worst case: pushing a strictly decreasing sequence makes every item a new minimum, so mins has n entries and the total is 2n items; best case: an increasing sequence leaves mins with 1 entry. Alternative: store pairs (x, minimum of everything at or below x) on one stack: always exactly 2n numbers, with simpler code (min_value is the second part of the top pair).

Reference: solutions/py/ex3_stack.py, solutions/java/Ex3Stack.java. push checks size == capacity first, copies item by item into an array of twice the length (adding 1 to copies per item), then stores the item at index size; pop decrements size, reads the item and writes None / null into the freed slot (otherwise the array keeps the object alive); top and pop throw on an empty stack. Copies: the resizes happen at capacities 2, 4, 8, …, C/2 and copy that many items, so the total is 2 + 4 + … + C/2 = C − 2 when the final capacity is C (for C = 2 there is no resize and C − 2 = 0). After n pushes C is the smallest power of two that is ≥ n (and ≥ 2), so C < 2n for n ≥ 2 and the total C − 2 < 2n; for n = 1 the total is 0 < 2. As in chapter 1: fewer than 2n copies in total, so fewer than 3n steps counting the writes, amortized O(1) per push. The capacity sequence for 9 pushes is 2, 2, 4, 4, 8, 8, 8, 8, 16.

Reference: solutions/py/ex3_circqueue.py, solutions/java/Ex3CircQueue.java. The next free cell is (front + size) % capacity; dequeue clears the cell and moves front to (front + 1) % capacity; when size == capacity, enqueue allocates an array of twice the size, copies item k to cell k walking from front with walk = (walk + 1) % old_capacity, and sets front = 0. The correctness is exactly Exercise 1. A common mistake is copying old[0..n-1] straight over (a bulk copy that ignores front): it gives the wrong order whenever the queue has wrapped, which is what the test with E and F and the later G catches.

Reference: solutions/py/ex3_postfix.py, solutions/java/Ex3Postfix.java. Pop the right operand first, then the left; compute left ∘ right. Division: Java's / truncates toward zero, Python's // floors (−7 // 2 = −4), and int(a / b) goes through a float and is wrong for large ints. The reference computes the quotient of the absolute values and gives it the sign of the true quotient (negative when exactly one operand is negative): −7 / 2 = −3, 7 / −2 = −3, −7 / −2 = 3. Errors: an operator needs two items on the stack (otherwise ValueError / IllegalArgumentException); at the end exactly one item must remain (an empty list leaves none, 1 2 leaves two); int(t) / Integer.parseInt(t) reject tokens that are neither numbers nor operators (NumberFormatException is an IllegalArgumentException); division by zero is a ZeroDivisionError / ArithmeticException.

The bug: dequeue does self._front += 1 (Java: front++) and never takes the remainder, while enqueue computes (front + size) % capacity and does wrap. For RingQueue(3): enqueue 1, 2, 3, dequeue three times (front is now 3 = capacity), enqueue 4 (it lands in cell (3 + 0) % 3 = 0, correctly), and now dequeue: it reads data[3] from an array of length 3 and fails with an IndexError (Java: ArrayIndexOutOfBoundsException). The AI's test enqueued three, dequeued three and enqueued once more but never dequeued after the front had reached the capacity, so the line that fails never ran. In general the queue works for exactly capacity dequeues and then breaks. Fix: self._front = (self._front + 1) % len(self._data). The test that catches it: do more than a full lap of operations (more than capacity dequeues in total, with the queue never empty for long) and compare with a trusted reference, such as collections.deque / ArrayDeque, on a long random sequence: the same test as in Exercise 7. The "O(1)" claim is true; the bug is in the claim of testing, not in the complexity. (The test test_buggy_ring_queue_fails_on_the_fourth_dequeue and test_buggy_ring_queue_needs_exactly_capacity_dequeues in solutions/py/test_ex3_read.py show the failure for capacities 1, 2, 3 and 5.)

Two bugs. (1) stack.pop() on an empty stack: for ")", "())" or "a]", a closer arrives with nothing to match and Python raises an IndexError (Java: NoSuchElementException from ArrayDeque.pop) instead of returning False. (2) The loop ends with return True (Java return true): leftover openers are never noticed, so "((", "([" and "((())" are reported as balanced. Why the three tests passed: ([]{}) and (a[b]c) are balanced, and [(]) fails on a mismatch inside the loop, the only failure kind the code handles; none of the tests exercised underflow or a leftover opener. Fix:

if not stack: return False        # before popping at a closer...return not stack                  # at the end

The test that catches it: one test per way to fail (mismatch, underflow, leftover), the empty string, and, best, all strings up to length 8 over a small alphabet compared with an independent definition (balanced_by_grammar in solutions/py/ex3_claims.py does that for Exercise 2).