Foundations: correctness and asymptotic analysis

Correctness

Question 1

A recursive procedure is given a whole number n, has base case n == 0, and calls itself with n - 2. What is the state of its termination argument?

A.It is fine, because the measure strictly decreases at every callB.It fails for odd n, because the measure decreases but steps over the only base caseC.It fails for every n, because a measure must decrease by exactly 1D.It is fine, because a recursion on numbers always reaches zero eventually

Question 2

You have shown that a loop invariant holds before the first pass and that every pass preserves it. What else must be shown before the algorithm can be called correct?

A.Nothing further: initialisation and maintenance are the whole argumentB.That the loop stops, and that the invariant together with the reason it stopped gives the postconditionC.That the invariant mentions every variable the loop changesD.That the invariant is also true after the loop body's last statement

Question 3

A procedure is meant to return the largest value in a non-empty list of whole numbers. It starts a variable at 0 and replaces it whenever it meets a larger entry. Which statement is right?

A.It is correct, but only for lists of at least two entriesB.It is incorrect, because on a list whose entries are all negative it returns 0, a value that never appears in the listC.It is correct, because it returns the largest value it foundD.It is incorrect only if the list is empty, which the precondition rules out

Question 4

Someone proposes this invariant for insertion sort's outer loop: 'positions 0 to i - 1 are in increasing order'. What is wrong with it?

A.It is true and sufficient, since sorted is exactly what the algorithm promisesB.It is unusable because it mentions the loop variable iC.It is false, because the front of the array is not sorted until the loop endsD.It is true but too weak: a procedure that overwrote the front of the array with copies of one value would satisfy it and would not have sorted anything

Cost

Question 5

A recursive procedure sums a list by adding the first entry to the sum of the rest, allocating nothing. What is its auxiliary space?

A.Theta(1), because it never allocates any memoryB.Theta(1), because each call's frame is released as soon as that call is madeC.Theta(n), because one stack frame per call is alive at the deepest pointD.Theta(log n), because that is the usual depth of a recursion

Question 6

A problem states that n is at most 20 and asks for the best arrangement of n items, with a one second limit. What does that constraint suggest?

A.Nothing at all: the largest n is a testing detail and says nothing about the intended methodB.A linear solution, because the limit is small enough that anything slower is unnecessaryC.A quadratic solution, since 20 squared is tinyD.A solution that examines every subset of the items, since 2^20 is about a million and a polynomial cost would have allowed a far larger n

Question 7

A growable array offers appends with amortised cost O(1) and worst case O(n) for a single append. Which claim does that support?

A.Every append costs a constant number of operationsB.The average append costs a constant number of operations, provided the data is randomC.Any sequence of m appends costs O(m) in total, though one append in the sequence may cost O(n)D.The expected cost of an append is constant, over the coin flips the structure makes

Question 8

An algorithm's running time satisfies T(n) = O(n^2). Which conclusion is justified?

A.On large inputs T(n) is no more than a constant multiple of n squared, and it may be far smallerB.The algorithm is slower than one whose time is O(n log n) on every inputC.T(n) grows like n squared, so doubling the input roughly quadruples the timeD.There are inputs of size n on which the algorithm performs about n squared operations

Question 9

What exactly must you produce to establish that f(n) = O(g(n))?

A.A value of n at which f(n) is smaller than g(n)B.A constant c such that f(n) <= c g(n) for every n, with no exceptions allowedC.A proof that f(n) <= g(n) for every n from 1 upwardsD.A constant c > 0 and a starting point n0 such that f(n) <= c g(n) for every n >= n0

9 questions left to answer.