أسئلة المقال وتتبع الشيفرة وتصحيح الأخطاء وكتابة الشيفرة في بنك أسئلة الأسبوع:
هياكل البيانات والخوارزميات (DSA27) · الأسبوع 4
Dynamic arrays and amortised analysis (Lecture 04)
هذه اختبارات للتدريب الذاتي، تُحفظ إجاباتك على هذا الجهاز فقط ولا تُرسل إلى أحد. الأسئلة والشرح بالإنجليزية لغة المقرر.
-
For a
DynamicArray,len(a)returns:lenis the number of elements the user stored. The capacity (b) is internal; showing it would expose the implementation. -
With doubling, what is the capacity after 5 appends?
Capacity 1 → 2 (2nd append) → 4 (3rd) → 8 (5th).
-
With doubling, how many resizes do 1,000 appends cause?
Resizes happen when the size reaches 1, 2, 4, …, 512 — ten powers of two below 1,000 — so exactly 10 (210 = 1024). 999 (d) is growing by one.
-
If the capacity grows by one slot at every resize, the total number of copies for n appends is:
Every append copies everything already there: 0 + 1 + … + (n-1) = n(n-1)/2.
-
If the capacity grows by a constant 100 slots at every resize, the amortised cost of
appendis:Copies are 100, 200, 300, …: about n2/200 in total — still quadratic, so O(n) per append on average. A constant step only changes the constant. (d) confuses the step size with the cost.
-
With doubling, the amortised cost of
appendis:Fewer than 3n units of work for n appends: under 3 each.
-
With doubling, the worst-case cost of a single
appendis:The append that finds the array full copies all n elements. The amortised bound does not change that single worst case.
-
How does amortised cost differ from average-case cost?
Amortised analysis bounds the total over any sequence — a guarantee. Average case (c) averages over an assumed distribution of inputs.
-
With doubling, the total number of element copies for n appends is:
1 + 2 + 4 + … + 2k = 2k+1 - 1 < 2n, since 2k < n.
-
With doubling, which of these appends triggers a resize?
Appends that find the array full are those made when the size is a power of two: the 2nd, 3rd, 5th, 9th, 17th, 33rd, … (one more than a power of two).
-
To shrink without thrashing, a dynamic array should halve its capacity when the size falls to:
A gap between the grow threshold (full) and the shrink threshold (one quarter) means many cheap operations must happen between resizes. Halving at one half (a) leaves no gap.
-
"Thrashing" in a dynamic array means:
For example: full at capacity 8, append (grow to 16), pop (shrink to 8), append (grow), … — an O(n) copy on every operation.
-
CPython's
listgrows its capacity by about:Capacities 4, 8, 16, 24, 32, 40, 52, 64, 76, … on Python 3.13.
-
How can you see a Python list's capacity from Python?
sys.getsizeofreturns the header plus one reference (8 bytes) per slot of capacity; subtract the empty list's size and divide by 8. -
In a
DynamicArrayof size 5 and capacity 8,a[-1]readsself._blockat index:−1 + size = 4: the last used slot, not the last slot (a).
-
insert_at(0, x)on a dynamic array of size n costs:All n elements shift right — whether or not a resize is needed.
-
pop()— removing the last element — costs:Nothing moves; clear the slot and decrement the size.
-
Why does growing by a factor give amortised O(1) append?
The copies at each resize double, so the last resize copies more than all the earlier ones together, and it copies fewer than n.
-
Growing by a factor of 1.5 instead of 2:
Any factor r > 1 gives a geometric series: about n · r/r-1 copies — 3n for r = 1.5 against 2n for r = 2 — while the unused space after a resize is about a third rather than a half.
-
With doubling and no shrinking, just after a resize, about how much of the capacity is unused?
Growing from c to 2c with c + 1 elements leaves c − 1 slots unused: about half.
-
Which structure in
dsa/stores its items in the student's ownDynamicArray?Stackkeeps its top at the end of aDynamicArray.CircularQueueand the open-addressing map use a plainArray; the tree uses nodes. -
In the accounting ("bank") proof for doubling, how many coins must each append be charged?
One coin for the append's own write, two saved to pay for copying at the next doubling.
-
With the course
DynamicArray(capacity 1, doubling), what arelen(a)anda._capacityaftera = DynamicArray(range(6))?Resizes on appends 2, 3 and 5 take the capacity 1 → 2 → 4 → 8; the sixth append fits.
lenis the size, 6. (a) confuses size with capacity; (d) grows by a factor of 3 from 4. -
Why does
__getitem__checkindex < self._sizerather thanindex < self._capacity?The
Arrayhas allcapacityslots (so (b) is wrong), but the ones beyondsizeare not part of the user's data. Reading one must be anIndexError, not a silentNone— W4-B2 is exactly this bug. -
What does this print?
a = DynamicArray() for i in range(9): a.append(i) print(a.resize_count, a._capacity)Appends 2, 3, 5 and 9 find the array full: 4 resizes, capacity 1 → 2 → 4 → 8 → 16. (c) gives the size as the capacity; (a) misses the 9th append, which finds 8 of 8 slots used.
-
When the course
DynamicArrayresizes, it:Allocate, copy, switch — Lecture 04's three steps. An
Arraycannot grow in place (a), and the dynamic array is one contiguous block, not a chain of blocks (d). -
Why can
_resizenot simply make the existingArraylonger?An array's speed comes from being one contiguous block, and the memory after it is not guaranteed to be free. So a larger block is made elsewhere, and everything is copied. (b) is backwards: a contiguous block is exactly what keeps indexing O(1).
-
A
DynamicArrayholds 8 elements and has capacity 8. Counting the elements copied by a resize and the elements shifted, how many existing elements move duringinsert_at(0, "x")?The array is full, so
insert_atfirst resizes: 8 copies. Then all 8 elements shift one place right to free slot 0: 8 more. Then"x"is written. (a) forgets one of the two, and (b) counts the new element as a moved one. -
a = DynamicArray([10, 20, 30, 40, 50]). What doesa.pop(2)return, and how many elements move?pop(2)returnsa[2], which is 30, and 40 and 50 shift left to close the gap. (c) counts from 1; (d) also counts the removed element. -
After 9 appends and then 8 calls of
pop(), what is the capacity of the courseDynamicArray?The course
DynamicArray.popshifts and clears a slot, but never resizes: the capacity stays 16. Shrinking at one quarter (c) is the Homework 4 extension,ShrinkingArray(W4-C3), not the course class. -
During 1,000,000 appends to an array that doubles, the single most expensive append copies how many elements?
Resizes copy 1, 2, 4, …; the last one happens when the size is 219 = 524288, because 220 is over a million. (a) and (b) would need the array to be full at that size, which it never is; (d) is the number of resizes, not the size of the largest.
-
With
DynamicArray(growth=3), the total number of elements copied by n appends is always less than:The copies are 1 + 3 + 9 + … + 3k = (3k+1 - 1)/2 with 3k < n, which is less than 1.5 · 3k < 1.5n — the general bound n · r/(r-1) with r = 3. (b) is true but weaker, and (c) is not even linear.
-
Which of these statements is an amortised bound rather than a worst-case bound for a single operation?
A bound on the total of any sequence, shared over its operations, is amortised. (b), (c) and (d) each bound one operation: worst-case statements.
-
DynamicArray(growth=1.5)fails at its first resize. Why?make_block(1 * 1.5)asks for 1.5 slots, and theArrayraisesTypeError: 'float' object cannot be interpreted as an integer. A factor of 1.5 is fine in theory — (a) and (c) are wrong — it only needs rounding to a whole number, as Lecture 04 shows. -
What does
DynamicArray([1, 2], growth=1)do?The first append fits. The second finds the array full and calls
_resize(1 * 1), which copies into a new block of the same size, so the write to slot 1 raisesIndexError. A factor of 1 is not growth at all, and certainly not growth by one slot (a). -
An array that grows by a constant +10 slots copies 798,400 elements for 4,000 appends. For 8,000 appends it copies about:
Constant-step copying is quadratic, about n2/(2 × 10): double n and the copies multiply by about 4 (3,196,800 in fact). (b) is what doubling gives — linear.
-
A
DynamicArrayholds 5 elements in capacity 8. What doesa[5] = "x"do?__setitem__accepts the same indices as__getitem__, 0 to size − 1. Slot 5 is not yet an element, so it is anIndexError, as it is for a Python list; writing never changes the size (a). To add an element, useappend(d). -
In the accounting argument (3 coins per append), the doubling from capacity 8 to 16 copies 8 elements. Which coins pay for it?
After the resize to capacity 8 at size 4, the appends of elements 5, 6, 7 and 8 each paid 1 coin for their own write and saved 2: 8 coins, exactly enough to copy 8 elements. Earlier appends' coins (b) were spent on earlier resizes; nothing is borrowed (d) — the bank never goes negative.
-
A student's
_resizecopies into the new block and setsself._block, but forgetsself._capacity = capacity. Starting empty with capacity 1, what happens?Append 2 sees size 1 = capacity 1 and resizes to a 2-slot block, but
_capacitystays 1. From then onsize == _capacityis never true again, so there are no more resizes: append 3 writes to slot 2 of a 2-slot block and raisesIndexError. (b) is the bug of W4-B1. -
Which methods of the course
DynamicArraycan trigger a resize?appendandinsert_atadd an element, so either may find the array full.popnever resizes in the course class (c), and__setitem__only overwrites an existing slot (d).
34 درجات
أسئلة المقال
9 أسئلة مقالية (34 درجة). اكتب إجابتك أولًا، ثم اعرض الإجابة النموذجية ونقاط التصحيح، وقدّر درجتك بأمانة: كل نقطة تساوي درجة تقريبًا.
مجموع درجات المقال: 0 / 34
-
Define amortised cost. Prove that n appends to a dynamic array that doubles cost O(n) in total, and conclude the amortised cost of one append.
الإجابة النموذجية ونقاط التصحيح
- Definition: the amortised cost of an operation is the maximum total cost of any sequence of n operations, divided by n. It is a guarantee over sequences, not an average over inputs.
- Writes: each of the n appends writes one element: n.
- Copies: resizes happen when the size reaches 1, 2, 4, …, 2k with 2k < n, each copying that many elements.
- Sum: 1 + 2 + … + 2k = 2k+1 - 1 < 2 · 2k < 2n.
- Conclusion: total < 3n = O(n), so the amortised cost of one append is < 3 = O(1). (The accounting argument — 3 coins per append — is equally acceptable.)
-
Explain why growing the capacity by a constant number of slots gives Θ(n2) total cost for n appends, however large the constant, while growing by a constant factor gives Θ(n).
الإجابة النموذجية ونقاط التصحيح
- Each resize copies everything stored so far.
- Constant step c: resizes come every c appends, at sizes about c, 2c, 3c, …; the amounts copied grow linearly, and a sum of n/c linearly growing terms is about n2/(2c) — Θ(n2). A larger c only shrinks the constant.
- Factor r: resizes come at sizes growing geometrically; each one copies r times more than the last, so the whole sum is dominated by its last term, which is less than n: total Θ(n).
- The difference is linear against geometric spacing of the resizes — not the size of the step.
-
appendis "worst-case O(n) and amortised O(1)". Explain both statements, why both are true, and when the worst case still matters.الإجابة النموذجية ونقاط التصحيح
- Worst case O(n): a single append that finds the array full must copy all n elements before writing.
- Amortised O(1): such appends are exponentially rare; any n appends cost under 3n in total. Both are true because they measure different things — one operation, against a whole sequence.
- When the worst case matters: when one slow operation is itself a failure — real-time systems, a game frame, a latency-critical request. Those reserve capacity in advance.
-
Explain thrashing with a concrete sequence of operations, and the shrinking rule that prevents it.
الإجابة النموذجية ونقاط التصحيح
- Thrashing: operations alternating around a single boundary force a resize almost every time, so each costs O(n).
- Example (grow at full, shrink at half full): capacity 8, size 8.
append→ grow to 16 (copy 8);pop→ size 8 = half of 16 → shrink to 8 (copy 8);append→ grow (copy 8); and so on. - Rule: grow when full, but shrink (halve) only when the size falls to one quarter of the capacity.
- Why it works: after any resize the array is about half full, so at least about n/4 cheap operations must happen before the next resize, which pays for it: amortised O(1) for any mix of appends and pops.
-
Growth factor is a time–space trade-off. Explain the trade-off, and why CPython's
listuses a small factor (about 1.125).الإجابة النموذجية ونقاط التصحيح
- A larger factor resizes less often (fewer total copies, e.g. under 2n for ×2) but can leave more capacity unused (up to about half).
- A smaller factor wastes less memory but copies more (about n r/(r-1) in total — around 9n for r = 1.125).
- Any factor > 1 keeps append amortised O(1). CPython chooses a small one because Python programs create huge numbers of lists, most of them small, so the saved memory matters more than the extra copying.
-
A
DynamicArrayholdsa b c din capacity 4. Describe every step ofinsert_at(1, "x"), give the final contents, size and capacity, and count the elements copied and shifted. Why mustinsert_atcheck for a full array before it shifts?الإجابة النموذجية ونقاط التصحيح
- Bounds:
0 <= 1 <= 4holds. Full: size 4 = capacity 4, so resize to 8: allocate anArray(8)and copya b c d— 4 copies. - Shift right, from the end down to the gap:
dto slot 4,cto 3,bto 2 — 3 shifts. Then write"x"into slot 1; size becomes 5. - Result:
a x b c d, size 5, capacity 8; 7 elements moved, plus 1 write. - Why first: the first shift writes into slot
size, which does not exist in a full block, so shifting before resizing raisesIndexError.
- Bounds:
-
Stack,SlowQueue,MinHeapandGraphare all built on yourDynamicArray. For the stack and the slow queue, explain how the cost of each operation follows from theDynamicArraytable. Why does a bug inDynamicArrayshow up in the tests of other weeks?الإجابة النموذجية ونقاط التصحيح
- Stack: the top is the end of the
DynamicArray, so push isappend(amortised O(1)), and pop and peek touch only the last slot (O(1)). - SlowQueue: enqueue is
append(amortised O(1)), but dequeue ispop(0), which shifts every remaining element: O(n) — the cost Week 7 measures. - The structure's costs are the
DynamicArray's costs at the end it uses: the stack chose the cheap end; the queue cannot avoid the expensive one. (MinHeapadds a leaf withappend;Graphkeeps each neighbour list in one.) - Bugs travel: these classes call your
append,popand__getitem__, so a wrong bound or a broken resize fails their tests too — the storage rule makes week 4 the foundation of weeks 6, 7, 12 and 14.
- Stack: the top is the end of the
-
Explain the accounting ("bank") argument for a doubling array: how many coins each append is charged, what each coin pays for, and why the bank never goes negative.
الإجابة النموذجية ونقاط التصحيح
- Charge every append 3 coins: 1 pays for its own write, 2 are saved in the bank.
- At a resize from capacity c to 2c, the c/2 appends since the previous resize have saved 2 · c/2 = c coins — exactly enough to copy the c elements.
- So the balance never goes negative: every resize is paid for by coins already saved. Total cost ≤ 3n, amortised O(1) per append.
-
A game appends one record to a dynamic array every frame and must never take longer than one frame. Explain why a doubling array is a risk even though append is amortised O(1), and describe two ways to remove the risk.
الإجابة النموذجية ونقاط التصحيح
- The risk: amortised O(1) bounds the total, not each append. The append that finds the array full copies everything — with a million records, one frame does a million copies and the game stutters.
- Fix 1 — reserve: allocate enough capacity in advance for the expected number of records, so no resize happens during play.
- Fix 2 — spread the copy: when the array is half full, allocate the bigger block and copy a few old elements on each later append, so the copy is finished before the old block fills; every append is then worst-case O(1).
- Also acceptable: store the records in a chain of fixed-size blocks (as
collections.dequedoes) or in a linked list — worst-case O(1) append, at a cost in memory and locality.