Lesson test: Arrays and amortised cost

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Arrays and amortised cost

1.[2p]
An array of 8-byte elements starts at address 4096. At what address does element 250 begin, with 0-based indexing?

CorrectNot quite: 6096

2.[2p]
Why does reading `a[999999]` cost the same as reading `a[0]`?

The address is computed by arithmetic on the index alone, so no intervening element is examined

Correct

The elements in between are cached

The answer is: The address is computed by arithmetic on the index alone, so no intervening element is examined

The array is stored back to front

The answer is: The address is computed by arithmetic on the index alone, so no intervening element is examined

Both reads are counted as one step only in the RAM model, and in reality the second is slower by a factor of a million

The answer is: The address is computed by arithmetic on the index alone, so no intervening element is examined

3.[3p]
A dynamic array with growth factor 2 starts at capacity 1 and receives 1000 pushes. How many element copies occur in total?

CorrectNot quite: 1023

4.[3p]
Growing a dynamic array by a fixed 1000 extra slots each time it fills gives an amortised push cost of

$Θ (n)$ , because the total copying is $Θ (n^{2})$

Correct

$Θ (1)$ , because 1000 is a constant

The answer is: $\Theta(n)$, because the total copying is $\Theta(n^2)$

$Θ (\log n)$

The answer is: $\Theta(n)$, because the total copying is $\Theta(n^2)$

$Θ (1)$ amortised but $Θ (n)$ worst case, exactly as doubling

The answer is: $\Theta(n)$, because the total copying is $\Theta(n^2)$

5.[2p]
Amortised analysis is a worst-case statement about a sequence of operations, and involves no assumption about the distribution of inputs.

True

Correct

False

The answer is: True

6.[2p]
With growth factor $g = 1.5$ , about how many element copies does building a dynamic array up to $10^{6}$ elements cost? Give the answer in millions.

CorrectNot quite: 2

7.[3p]
Match each array operation to its cost on $n$ elements.

Read by index
Insert at the front
Push at the end
Delete at position k, order not preserved

constant
constant
linear
amortised constant

Show the answer

Read by index: constant Insert at the front: linear Push at the end: amortised constant Delete at position k, order not preserved: constant

8.[2p]
Why does a dynamic array shrink only when its length falls below a quarter of its capacity, rather than a half?

Otherwise pushing and popping across the boundary reallocates on every operation

Correct

A quarter is the smallest fraction the allocator supports

The answer is: Otherwise pushing and popping across the boundary reallocates on every operation

Halving would lose data

The answer is: Otherwise pushing and popping across the boundary reallocates on every operation

Shrinking at a half wastes more memory than shrinking at a quarter

The answer is: Otherwise pushing and popping across the boundary reallocates on every operation

9.[3p]
Which are true of raising the growth factor from 2 to 4?

Select all that apply

Fewer copies per element

Correct

More memory can sit empty just after a growth

Correct

The amortised push cost stops being constant

The answer is: Fewer copies per element, More memory can sit empty just after a growth, The worst-case cost of a single push is still linear

The worst-case cost of a single push is still linear

Correct

1.[2p] An array of 8-byte elements starts at address 4096. At what address does element 250 begin, with 0-based indexing?

2.[2p] Why does reading a[999999] cost the same as reading a[0]?

3.[3p] A dynamic array with growth factor 2 starts at capacity 1 and receives 1000 pushes. How many element copies occur in total?

4.[3p] Growing a dynamic array by a fixed 1000 extra slots each time it fills gives an amortised push cost of

5.[2p] Amortised analysis is a worst-case statement about a sequence of operations, and involves no assumption about the distribution of inputs.

6.[2p] With growth factor g=1.5, about how many element copies does building a dynamic array up to 106 elements cost? Give the answer in millions.

7.[3p] Match each array operation to its cost on n elements.

8.[2p] Why does a dynamic array shrink only when its length falls below a quarter of its capacity, rather than a half?

9.[3p] Which are true of raising the growth factor from 2 to 4?

1.[2p]
An array of 8-byte elements starts at address 4096. At what address does element 250 begin, with 0-based indexing?

2.[2p]
Why does reading `a[999999]` cost the same as reading `a[0]`?

3.[3p]
A dynamic array with growth factor 2 starts at capacity 1 and receives 1000 pushes. How many element copies occur in total?

4.[3p]
Growing a dynamic array by a fixed 1000 extra slots each time it fills gives an amortised push cost of

5.[2p]
Amortised analysis is a worst-case statement about a sequence of operations, and involves no assumption about the distribution of inputs.

6.[2p]
With growth factor $g = 1.5$ , about how many element copies does building a dynamic array up to $10^{6}$ elements cost? Give the answer in millions.

7.[3p]
Match each array operation to its cost on $n$ elements.

8.[2p]
Why does a dynamic array shrink only when its length falls below a quarter of its capacity, rather than a half?

9.[3p]
Which are true of raising the growth factor from 2 to 4?