Practice · algos

P1. Cases

Linear search returns the index of the first occurrence of target in \(A[0..N-1]\), or \(-1\) if it is absent.

Describe a best-case input. How many comparisons?
Describe two worst-case inputs with different return values.
Why is “about \(N/2\), so \(\Theta(1)\)” wrong?

Show the answer

Best: target sits in \(A[0]\). One comparison. \(\Theta(1)\) for that input only.

Worst, found: target equals \(A[N-1]\), return \(N-1\). Worst, missing: target is absent, return \(-1\). Both take \(N\) comparisons.

\(N/2\) is still linear. \(\Theta(1)\) means the cost stops growing with \(N\).

P2. Count this

total = 0
i = 0
while (i < N)
    j = 0
    while (j < N)
        total = total + 1
        j = j + 1
    i = i + 1

How many times does total = total + 1 run? How many times does the inner test run? What is \(\Theta\)? Is there a separate best case?

Show the answer

The increment runs \(N^2\) times. For each of \(N\) outer passes the inner test runs \(N+1\) times, so \(N(N+1)\) inner tests. The outer test runs \(N+1\) times. \(T(N) = \Theta(N^2)\). No separate best case: both bounds are \(N\), and nothing returns early.

P3. True, false, or sloppy

\(4N^2 + 9N = \Theta(N^2)\)
\(N = O(N^2)\), and the bound is tight
\(\log N = o(N)\)
\(N^2 = \omega(N \log N)\)
\(2N^2 = o(N^2)\)
\(3N\log N = O(N^2)\)

Show the answer

(a) True. Leading term \(4N^2\).

(b) \(N = O(N^2)\) is true and not tight. Tight is \(\Theta(N)\). In fact \(N = o(N^2)\), because \(1/N \to 0\).

(c) True. \(\log N / N \to 0\).

(d) True. \(N^2 / (N\log N) = N/\log N \to \infty\). \(\omega\) means the left side grows strictly faster. That is a worse running time, not a better one.

(e) False. The ratio tends to 2. They are \(\Theta(N^2)\) of each other.

(f) True, and loose. It is also \(o(N^2)\). An \(O\) answer does not claim tightness.

P4. Strongest postcondition

Chain forward: \([x = x_0 \land y = y_0]\{\texttt{t = x; x = y; y = t;}\}\).

Show the answer

After t = x: \([t = x_0 \land x = x_0 \land y = y_0]\).

After x = y: \([t = x_0 \land x = y_0 \land y = y_0]\).

After y = t: \([t = x_0 \land x = y_0 \land y = x_0]\).

That is the strongest postcondition. If \(t\) is never mentioned again you may keep only \([x = y_0 \land y = x_0]\). Dropping a conjunct is a weakening.

P5. Weakest precondition

Find the weakest precondition on \(a\) so that \([z \ge 0]\) holds after:

if (a > 0) z = a - 3;
else       z = -a;

Show the answer

True branch: \(a > 0\) and \(a - 3 \ge 0\), so \(a \ge 3\).

False branch: \(a \le 0\). Then \(z = -a \ge 0\) already, so the whole else branch is fine.

Weakest precondition: \((a \ge 3) \lor (a \le 0)\). A failing integer is \(a = 1\), which sets \(z = -2\). Also \(a = 2\). The boundaries work: \(a = 3\) and \(a = 0\) both give \(z = 0\).

P6. A full invariant proof

Prove that \(s\) ends as the sum of \(A[0..N-1]\), for \(N \ge 0\).

s = 0
k = 0
while (k < N)
    s = s + A[k]
    k = k + 1

Show the answer

Invariant. At the top, \(s\) is the sum of \(A[0..k-1]\). The empty sum is 0.

Initialization. \(k = 0\), \(s = 0\). The range is empty.

Maintenance. Assume the invariant and \(k < N\). After adding \(A[k]\), \(s\) is the sum of \(A[0..k]\). Then \(k\) increases by 1, and the invariant matches the new counter.

Termination. \(k\) increases by exactly 1 from 0, so the test fails at \(k = N\). If \(N = 0\) it fails immediately, same value. The class is \(\Theta(N)\) for every input of length \(N\).

P7. Insertion sort

\(A[1..3] = [3,\; 1,\; 2]\). Show the array after each outer iteration, give each \(t_j\), compare the sum with best and worst for \(n = 3\), and state the outer invariant at the start of \(j = 3\).

Show the answer

Start \([3,\;1,\;2]\).

\(j = 2\), key \(1\). Shift the \(3\). Array \([1,\;3,\;2]\). Tests: one success and one failure on \(i > 0\), so \(t_2 = 2\).

\(j = 3\), key \(2\). \(A[2] = 3 > 2\), then \(A[1] = 1 \not> 2\). Array \([1,\;2,\;3]\). \(t_3 = 2\).

Sum \(= 4\). Best-case sum is \(n-1 = 2\). Worst-case sum is \(2+3 = 5\). This input sits between them.

At the start of \(j = 3\), before the body: \(A[1..2]\) is the original prefix \([3,\;1]\), sorted, hence \([1,\;3]\). The \(2\) is still in \(A[3]\).

P8. Selection sort

\(A = [8,\; 3,\; 3,\; 1]\), \(N = 4\), using <=. Trace \(k\), mi, and the array. How many comparisons? Why is there no best case? State the invariant and the exit value of \(k\).

Show the answer

Start \([8,\;3,\;3,\;1]\).

\(k = 0\), mi moves \(0 \to 1 \to 2\) on the tie \(3 \le 3\), then to \(3\) because of the \(1\). Swap to \([1,\;3,\;3,\;8]\).

\(k = 1\), the two \(3\)s tie and the later index wins, so mi \(= 2\). Swapping equal values leaves \([1,\;3,\;3,\;8]\).

\(k = 2\), \(8 \le 3\) is false, mi stays \(2\), self-swap. No body for \(k = 3\).

Comparisons: \(3+2+1 = 6 = N(N-1)/2\). The inner bounds ignore the data and there is no early exit, so a sorted array costs the same. Exit at \(k = N-1 = 3\).

Invariant: the first \(k\) cells are the \(k\) smallest, sorted, and each is \(\le\) the suffix; the array is a permutation of the input. Clause (ii) is what forces the last cell to be the maximum. “The prefix is sorted” alone does not.