(a) Item i starts at address(i) = base + i · s, where s is the item size. With base 5000 and s = 4, item 250 starts at 5000 + 4·250 = 6000. It is one multiplication and one addition whatever i is: no loop, no walk past the earlier items, so reading or writing item i is O(1). For the table, row-major order puts cell (r, c) at index r·C + c, so its address is base + (r·C + c)·s. With r = 3, c = 5, C = 8, s = 8 and base 2000: index 3·8 + 5 = 29 and address 2000 + 8·29 = 2232.

(b) There are n + 1 equally likely positions k = 0, …, n, and position k moves n − k items, so the average is (1/(n+1)) · Σₖ (n − k) = (1/(n+1)) · (n + (n−1) + … + 0) = (1/(n+1)) · n(n+1)/2 = n/2. A random insert still moves half the array: Θ(n).

(c) Claim P(n): after n inserts at index 0 into an initially empty array the total number of moves is n(n − 1)/2. Base n = 0: no insert, 0 moves, and 0·(−1)/2 = 0. ✓ Step: assume P(n). The (n+1)-th insert finds n items in the array and moves all of them (n − 0 = n), so the total becomes n(n − 1)/2 + n = (n*² + *n)/2 = (n + 1)n/2, which is P(n + 1). ∎ n inserts at the front cost Θ(*n*²), the same sum as the pair count of chapter 1, and the same shape the stopwatch showed (eight times the items, about eight times the time of one insert).

(a) Let n ≥ 2 and let J be the largest j with 3ʲ + 1 ≤ n, that is 3ᴶ ≤ n − 1. The resizes happen at appends 3⁰ + 1, 3¹ + 1, …, 3ᴶ + 1 and copy 1, 3, …, 3ᴶ elements, in total (3^(J+1) − 1)/2 (geometric series). Since 3^(J+1) = 3·3ᴶ ≤ 3(n − 1), the total is at most (3(n − 1) − 1)/2 = (3*n* − 4)/2 < 1.5·n. For n = 1 there is no copy. Check: n = 10 has resizes at appends 2, 4, 10: 1 + 3 + 9 = 13 < 15; n = 100 has resizes at 2, 4, 10, 28, 82: 1 + 3 + 9 + 27 + 81 = 121 < 150.

(b) The same argument with g in place of 3: copies = (g^(J+1) − 1)/(g − 1) with g*ᴶ ≤ *n − 1, so copies ≤ (g(n − 1) − 1)/(g − 1) < g·n/(g − 1). Adding the n writes, an append costs on average less than 1 + g/(g − 1) = (2*g* − 1)/(g − 1): for g = 2 that is 3 (the "fewer than 3*n* steps" of chapter 1), for g = 3 it is 2.5, for g = 4 about 2.33. The argument also works for a real factor g > 1 (the capacities form a geometric series whose sum is at most g/(g − 1) times its largest term). A factor as small as CPython's roughly 1.125 therefore allows up to about 9 copies per append, against under 2 for doubling: a small factor means frequent resizes.

(c) Right after the resize at append g*ʲ + 1 the capacity is *g^(j+1) and the size is g*ʲ + 1, so the filled fraction is (*g*ʲ + 1)/*g^(j+1) > 1/g. While you only append, the array is never less than 1/g full, so less than (g − 1)/g of the slots are idle: under 1/2 for g = 2 and under 2/3 for g = 3. The trade-off: a bigger factor copies less (under 2 copies per append for g = 2, under 1.5 for g = 3) but can leave more memory unused.

(a) Let the list have m nodes, well formed. Step 1 (new node n: n.next ← head): starting at n we visit n and then the m old nodes, ending at the old last node, whose next is empty. Step 2 (head ← n): a traversal from head now follows exactly that chain: m + 1 nodes. Step 3: if m = 0, n.next is empty and n is the only node, so tail ← n makes the last node the tail; if m > 0 the last node is still the old tail, which stays correct. Step 4: size = m + 1. So the traversal visits size nodes, the last is tail, tail.next is empty, and head is empty only when size is 0. ∎

(b) After head ← n, the old first node is referenced by nothing: the only reference to it was the old value of head, and no node points at the first node. Then n.next ← head reads the new head, which is n itself, so n.next is n: a cycle of length 1. All m old nodes are unreachable (garbage in Python and Java) although size says m + 1, and a traversal from head visits n, n, n, … forever. (If the second step read the old next field after head had moved, n.next would be empty and the list would shrink to the single node n: that is the bug in Exercise 10.)

(c) To remove the last node t the program must set p.next to empty and tail ← p, where p is the node just before t, the (n − 1)-th node. By assumption the only ways to reach a node are head, tail and next. tail is t, and t has no reference back to p; the only route to p is from head, which is node 1, and node n − 1 is n − 2 next hops later. So at least n − 2 hops, and the loop while p.next is not tail: p = p.next does exactly that many (a 4-node list A → B → C → D takes 2 hops, as in video 4). In a doubly linked list tail.prev is p: 0 hops, and the whole removal is a fixed handful of assignments.

Answers vary; these are defensible ones with their costs.

For (d): removing from the front of an array with s items shifts s − 1 of them, and the sizes go n, n − 1, …, 1, so the total is Σ(s − 1) = n(n − 1)/2 = 499,999,500,000 moves for n = 1,000,000, against 1,000,000 constant-time removals from the linked list.

(a) Capacity 8, 8 items. Append: the array is full, so it grows to 16 and copies 8; size 9. Pop: size 8 ≤ 16/2, so Policy H shrinks to 8 and copies 8; size 8, capacity 8: the state we started from. Every operation copies 8 = n elements, so m operations copy m·n (2000 operations: 16,000 copies, against 8 for Policy Q). With n as large as you like, the cost per operation is Θ(n), not O(1).

(b) After a shrink from capacity c: the capacity is c/2 and the size c/4; the shrink copied c/4. The next shrink needs size ≤ (c/2)/4 = c/8, which takes at least c/4 − c/8 = c/8 pops; the next growth needs the array full and one more append: at least c/4 + 1 appends. So at least c/8 operations pass, and the shrink's cost c/4 is at most 2 per operation. After a growth from capacity c: the capacity is 2*c*, the size c + 1, and the growth copied c. The next shrink needs size ≤ 2*c*/4 = c/2: at least c/2 + 1 pops; the next growth needs the array full (2*c* items) and one more append: at least c appends. So at least c/2 operations pass, and the growth's cost c is at most 2 per operation. Charge each resize's copies to the operations between it and the next resize: every operation lies after exactly one resize and is charged at most 2 copies, so the total is at most 2*m* plus the cost of the last resize, which is at most the current size ≤ m. Altogether at most 3*m* copies for m operations: O(m), amortized O(1) per append or pop. (Rounding at tiny capacities changes nothing: a resize at capacity 1 or 2 copies at most 2 items.)

(c) For "halve when size ≤ capacity/t" (growth factor 2): after a shrink from c the array has c/t items in capacity c/2, so the next shrink needs at least c/(2*t*) pops and the next growth at least c(t − 2)/(2*t*) appends; the shrink copied c/t, at most max(2, 2/(t − 2)) per operation. After a growth from c the next shrink needs at least c(t − 2)/t pops and the next growth c appends: c copies, at most t/(t − 2) per operation. Both stay bounded exactly when t > 2. For t = 2 (Policy H) the array is right at the threshold after a growth: one pop shrinks it again, and every operation copies n. Larger t only lets the array get emptier before it shrinks (wasting memory), so t = 4 is the usual choice: after a shrink the array is exactly half full, the same distance (a factor of 2) from the next shrink and from the next growth, and both ratios equal 2.

Reference implementation in solutions/. The loop in insert runs from the first free slot down to index + 1: it moves the last item first, so nothing is overwritten before it has moved. A forward loop would copy the same item into every later slot: inserting X at index 2 of A B C D E that way produces A B X C C C, because C overwrites D and then the copy of C overwrites E before either has moved. The loop runs size − index times, so insert adds size − index shifts; the loop in remove runs from index to size − 2, size − 1 − index times. Both formulas are what the random test accumulates. Appending (index == size) and removing the last item run no loop at all: 0 shifts.

Reference implementation in solutions/. The numbers the tests encode: appending 9 items gives capacities 1, 2, 4, 4, 8, 8, 8, 8, 16 and 15 copies (resizes at appends 2, 3, 5, 9 copy 1, 2, 4, 8); 17 appends give capacity 32 and 31 copies; inserting 100 items at index 0 shifts 0 + 1 + … + 99 = 4,950 items (Exercise 1(c)) and copies 127 = 1 + 2 + … + 64 (resizes at 2, 3, 5, 9, 17, 33, 65). Popping 9 items from the 9-item array gives capacities 16, 16, 16, 16, 8, 8, 4, 2, 1: the shrinks happen at sizes 4 (16 → 8, copies 4), 2 (8 → 4, copies 2), 1 (4 → 2, copies 1) and 0 (2 → 1, copies 0), so 15 + 4 + 2 + 1 = 22 copies in all. Alternating append and pop with 8 items copies 8 once (the growth to 16) and then nothing; Policy H of Exercise 5 would copy 8 on every operation (16,000 in the test), which is what the thrash test catches. The invariant capacity = 1 or capacity < 4·size (and size ≤ capacity) holds after every operation. Proof: capacities are powers of two. A growth from c leaves capacity 2*c* and size c + 1, and 4(c + 1) > 2*c*; an insert without growth only increases the size; a pop that does not shrink leaves 4·size > capacity or capacity 1 by the shrink condition; a pop that shrinks from c ≥ 8 had 4(size + 1) > c before the pop, so 4·size > c − 4 ≥ c/2, the new capacity; from c = 4 the size is 1 and the new capacity 2 < 4; from c = 2 the new capacity is 1. So the array never keeps more than four slots per item. Note that only append and pop are amortized O(1); insert(i, x) costs n − i shifts.

Reference implementation in solutions/. The structure of the cases:

• add_first: head = Node(value, head) creates the node with the old head as its next and only then moves head (Exercise 3(a)). If tail was empty the new node is also the tail.
• remove(value): walk with a trailing reference prev. Cases: not found (return false, nothing changes); prev empty, so the node is the head (head = node.next); otherwise prev.next = node.next. If the node was the tail, tail = prev (empty when the list had one node, which makes head and tail both empty). Without prev you would have to walk the list a second time to find the predecessor.
• reverse: one pass with three references: before overwriting node.next, save it in following; then node.next = prev, prev = node, node = following. At the end head = prev and tail is the old head. No new node is created and only O(1) extra space is used.
• DoublyLinked: insert_between sets the new node's prev/next first and then pred.next and succ.prev; delete_node makes the neighbours skip the node with two assignments (node.prev.next = node.next, node.next.prev = node.prev); remove_last is delete_node(trailer.prev). Thanks to the sentinels there is no special case for the first, last or only item: the neighbours always exist.

The bug: the loop starts at size − 1 instead of size. The first free slot is size, and the item in slot size − 1 has to move into it; the loop never does that move, so slot size − 1 is overwritten by its left neighbour (or by the new value) and slot size is never written. Smallest input: items = ["A", None], size = 1, index = 0: the loop range(0, 0, -1) is empty and items[0] = "X" overwrites A: the result is ["X", None] instead of ["X", "A"]. With ["A","B","C","D","E",None,None], size = 5, index = 2 the result is A B X C D None: E is lost (D overwrote it), and slot 5 is None although the caller now thinks the array holds 6 items. Appending (index == size) works, which is why the bug is easy to miss. Why the AI's test passes: it inserts at index = size − 1 = 2 into ["A","B","C"] and checks only the first three slots, ["A","B","X"]; the lost item C would have been in slot 3, which the test never reads. Test the whole array and the item that should have moved. Fix: for k in range(size, index, -1): (Java: for (int k = size; k > index; k--)). The docstring's "size − index moves" was right; the buggy loop makes size − 1 − index.

Bug 1, add_first: the order of the first two steps is wrong. self.head = node moves head first, and then node.next = self.head.next reads the new head's next, which is node.next, which is empty. So the old list is not connected to the new node: all m old nodes become unreachable while size becomes m + 1. Shortest sequence: add_last(1); add_first(0): to_list() is [0], not [0, 1], and size is 2. The AI's test used an empty list for add_first, where there is nothing to lose. Fix: connect the new node to the rest of the list first, then move head: node.next = self.head; self.head = node (Java: node.next = head; head = node;). Bug 2, insert_after: when node is the tail, the new node becomes the last node but tail still points at the old one. Shortest sequence: add_last(1); insert_after(tail, 2); add_last(3): the list is [1, 2] and tail.value is 1; then add_last(3) sets tail.next = 3, which overwrites the link from node 1 to node 2, so to_list() is [1, 3] and 2 is lost. The AI's test inserted after the head of a three-node list, so the tail was never involved. Fix: if node is self.tail: self.tail = new (Java: if (node == tail) tail = created;). The lesson is the one of Exercise 8: after every operation the three facts size = number of reachable nodes, tail = last node reachable, empty list = head and tail both empty must hold. Write a check() like the one in Exercise 8 and call it in the tests; test the empty list, a one-node list and the tail as special cases.