Practice: Algorithms, correctness and efficiency

Algorithms, correctness and efficiency

Warm-upHuman

What is the largest number of comparisons binary search can make on a sorted list of $1000$ entries?

Algorithms, correctness and efficiency

Warm-upHuman

How many comparisons does insertion sort make, in the worst case, to sort a list of $10$ entries?

Algorithms, correctness and efficiency

CoreHuman

This loop adds up a list $a$ of length $n$ :

s = 0
for i in range(n):      # i = 0, 1, ..., n - 1
    s = s + a[i]

Which statement is a loop invariant that holds at the start of each pass (before $a_i$ is added) and proves that $s$ is the total at the end?

Choose one

s = a_0 + a_1 + \dots + a_{i-1}

s = a_0 + a_1 + \dots + a_i

s \ge 0

s = a_0 + a_1 + \dots + a_{n-1}

Algorithms, correctness and efficiency

CoreHuman

A classmate's sorting function passed $1000$ random tests on lists of up to $50$ numbers. Which statement is correct?

Choose one

This is evidence that the function works, but it does not prove it works on every list.It is now proved correct for all lists of length at most

50

.It is proved correct, since

1000

is a large number of tests.The tests are useless; only proofs matter.

Algorithms, correctness and efficiency

CoreHuman

An algorithm takes $n^2$ steps on inputs of size $n$ . A new computer is $100$ times faster. In the time the old computer needed for size $n$ , the new one can handle size $k \cdot n$ . What is $k$ ?

Algorithms, correctness and efficiency

CoreHuman

In the correctness proof of binary search, suppose $a_{mid} < t$ . Why may we discard the indices $lo, \dots, mid$ ?

Choose one

The list is sorted, so

a_i \le a_{mid} < t

for every

i \le mid

: none of these entries equals

t

.Because

mid

is the middle, so

t

is equally likely to be in either half.Because we have already compared

t

with all of

a_{lo}, \dots, a_{mid}

.Because

lo \le mid \le hi

.

Algorithms, correctness and efficiency

CoreFormal

Let r := bsearch p lo hi. Which Lean proposition says that r is the first point where the test p gives true?

Choose one

p r = true ∧ ∀ k, k < r → p k = falsep r = true∃ k, p k = true∀ k, k < r → p k = true

Algorithms, correctness and efficiency

CoreComputational

Write binary_search(a, t) for a sorted list a. Return a pair (index, probes): an index i with a[i] == t (or -1 if t is absent), and the number of times you compared t with an entry of the list. The tests check correctness on many lists and that probes never exceeds $\lfloor \log_2 n \rfloor + 1$ , which is len(a).bit_length() in Python.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Algorithms, correctness and efficiency

StretchHuman

Using the decision-tree argument (Theorem 6), what is the smallest number of comparisons that any comparison-based method could need, in the worst case, to sort $5$ different numbers?

Algorithms, correctness and efficiency

StretchHuman

Run Euclid's algorithm on $(89, 55)$ . How many divisions with remainder does it perform before reaching a pair whose second number is $0$ ? (Count every step $(a, b) \to (b, a \bmod b)$ .)