Tutorial Revision

Insertion sort takes the next element, slot[i], and compares it with its left neighbour, again and again.

• If the left neighbour is bigger, the two swap.
• If the left neighbour is not bigger, the loop stops. That costs one comparison.
• If the element reaches index 0, the loop stops with no further comparison.

So iteration $i$ makes between 1 and $i$ comparisons. The worst total is $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$. Every iteration must make $i$ comparisons to reach it.

Two other worst cases:

$$(n, n-1, n-2, \dots, 3, 1, 2) \qquad \text{and} \qquad (1, n, n-1, n-2, \dots, 2).$$

In each list, the $i$-th key still needs $i$ comparisons to find its place. But a comparison is not always followed by a swap.

• $(n, n-1, \dots, 3, 1, 2)$. Every key up to 1 is smaller than everything on its left, so it travels to index 0. The last key, 2, swaps past $n, \dots, 3$. Then it compares with 1, which is smaller, and stops. That last comparison has no swap, but it is still the $i$-th comparison.
• $(1, n, n-1, \dots, 2)$. Each new key is smaller than every key on its left except 1. It swaps all the way to index 1, then compares with 1 and stops. Again $i$ comparisons.

Iteration $i$ makes all $i$ comparisons exactly when the new element reaches index 1. After that, either it moves to index 0, or the element at index 0 stops it. Both cost $i$ comparisons.

So an input is a worst case for comparisons when each new element is smaller than every element on its left, except possibly the smallest one.

• Check this for each position from left to right.
• Comparisons and swaps are different counts. Swaps equal the number of inversions (pairs in the wrong order). Only the reversed array has the most swaps, $\frac{n(n-1)}{2}$.

Comparisons: $1 + 2 + 3 = 6 = \frac{4 \cdot 3}{2}$. So it is a worst case for comparisons. Each new element is smaller than everything on its left except the smallest, as the method says.

Swaps: 4, which equals the inversions $(2,1), (4,3), (4,1), (3,1)$. The maximum is 6. So it is not a worst case for swaps.

The → direction. Suppose $f(n) = \Theta(g(n))$. By definition, there are $c_1, c_2, n_0 > 0$ such that

$$0 \le c_1 g(n) \le f(n) \le c_2 g(n) \quad \text{for all } n \ge n_0.$$

Pick the constants from here. The pair $c_2, n_0$ satisfies the definition of $O(g(n))$. The pair $c_1, n_0$ satisfies the definition of $\Omega(g(n))$. So $f(n)$ lies in both sets.

The ← direction. Suppose $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Then, for some constants $c_3$ and $c_4$:

$$0 \le c_3 g(n) \le f(n) \quad \text{for all } n \ge n_1,$$

$$0 \le f(n) \le c_4 g(n) \quad \text{for all } n \ge n_2.$$

Pick $n_3 = \max\{n_1, n_2\}$. Both inequalities hold from $n_3$ on, so merge them:

$$0 \le c_3 g(n) \le f(n) \le c_4 g(n) \quad \text{for all } n \ge n_3.$$

That is the definition of $f(n) = \Theta(g(n))$.

1. Write out each definition you are given, with its own constants: “$\exists\, c, n_0$ such that … for all $n \ge n_0$”. Give each one a new name ($c_1, n_1$, then $c_2, n_2$).
2. Write out the definition you must reach.
3. Build its constants from the ones you have. Two tools cover most proofs:
   • Take the maximum of the thresholds. Each fact holds from its own $n_i$. All of them hold from $\max_i n_i$.
   • Multiply or add the constants. If $f \le c_1 g$ and $g \le c_2 h$, then $f \le c_1 c_2 h$.

From the first fact: $0 \le f(n) \le c_1 g(n)$ for all $n \ge n_1$. From the second: $0 \le g(n) \le c_2 h(n)$ for all $n \ge n_2$.

Take $n_0 = \max\{n_1, n_2\}$. For $n \ge n_0$, both hold, so

$$0 \le f(n) \le c_1 g(n) \le c_1 c_2\, h(n).$$

With $c = c_1 c_2$, this is the definition of $f(n) = O(h(n))$. The proof used both tools of the method: the maximum threshold and the product of constants.

Take

$$f(n) = n \qquad \text{and} \qquad g(n) = \begin{cases} 1 & \text{if } n \text{ is even}, \\ n^2 & \text{otherwise}. \end{cases}$$

Proof that $f(n) \notin O(g(n))$. Suppose, for a contradiction, that $f(n) \in O(g(n))$. Then for some positive constants $c$ and $n_1$:

$$0 \le n \le c\,g(n) \quad \text{for all } n \ge n_1. \qquad (*)$$

Let $n_2$ be the smallest even number strictly larger than $\max\{n_1, c\}$. In particular, $n_2 > c$. $(**)$

Put $n_2$ into $(*)$. Since $n_2$ is even, $g(n_2) = 1$, so $0 \le n_2 \le c$. This contradicts $(**)$.

Proof that $g(n) \notin O(f(n))$. The official solution leaves this as an exercise. The proof is the same, with an odd number. Suppose $g(n) \le c\,n$ for all $n \ge n_1$. Let $n_2$ be an odd number larger than $\max\{n_1, c\}$. Then $g(n_2) = n_2^2$, so $n_2^2 \le c\,n_2$, which gives $n_2 \le c$. This contradicts $n_2 > c$.

1. Assume the constants exist: $f(n) \le c\,g(n)$ for all $n \ge n_0$.
2. Choose one value of $n$ that is larger than $n_0$ and breaks the inequality. Usually you pick $n$ larger than both $n_0$ and $c$, from the part of the domain where $g$ is small.
3. Put it in and reach a contradiction such as $n \le c$ with $n > c$.

To build two functions that cannot be compared, make one of them jump between a value below the other and a value above it, for example on even and odd $n$.

Neither.

• $f \ne O(g)$: suppose $n \le c\,g(n)$ for $n \ge n_0$. Take an odd $n > \max\{n_0, c^2\}$. Then $n \le c\sqrt{n}$, so $\sqrt{n} \le c$, so $n \le c^2$. Contradiction.
• $g \ne O(f)$: suppose $g(n) \le c\,n$ for $n \ge n_0$. Take an even $n > \max\{n_0, c^2\}$. Then $n^{1.5} \le c\,n$, so $\sqrt{n} \le c$. Contradiction.

Here $g$ jumps above $f$ on even $n$ and below it on odd $n$, as the method says.

A loop invariant is a statement that is true before every iteration of the loop.

1. Initialization: it is true before the first iteration.
2. Maintenance: if it is true before one iteration, it is true before the next.
3. Termination: when the loop stops, the invariant shows that the answer is correct.

First rewrite the for loop as a while loop. Then you can see the value of i when the loop stops.

def isPrime(n):
    p = true
    i = 2
    while (i <= floor(sqrt(n))):
        if n is divisible by i then:
            p = false
        i++
    return p

Invariant: “$p$ is true if and only if there is no integer $k$ such that $2 \le k < i$ and $k$ divides $n$.”

Initialization. At the start, $i = 2$. No integer $k$ satisfies $2 \le k < 2$, and $p$ is true. So the invariant holds before the loop.

Maintenance. After one full iteration, $i$ has grown by 1. The iteration tested the number that is now $i - 1$. There are two cases.

• If $i - 1$ divides $n$, the code set $p$ to false. The invariant for the new $i$ holds, because $k = i - 1$ divides $n$.
• If $i - 1$ does not divide $n$, $p$ is unchanged. By the inductive hypothesis, the old value of $p$ was correct for the range $2 \le k < i - 1$. The range grew by one number, $i - 1$, and that number does not divide $n$. So the answer to “is there a divisor in the range?” did not change, and $p$ is still correct. (The official solution asks “why?”. This is the reason.)

Termination. The loop stops when $i = \lfloor \sqrt{n} \rfloor + 1$. By the invariant, $p$ is true if and only if no integer $k$ with $2 \le k < \lfloor \sqrt{n} \rfloor + 1$ divides $n$.

This condition means $n$ is prime, for every $n > 1$. (The official solution says “prove it!”. Here is the proof.) Suppose $n$ is not prime, so $n = a \cdot b$ with $2 \le a \le b$. Then $a \cdot a \le a \cdot b = n$, so $a \le \sqrt{n}$, and $a \le \lfloor \sqrt{n} \rfloor$ because $a$ is a whole number. So a composite $n$ always has a divisor in the range, and $p$ is false. A prime $n$ has no divisor in the range, and $p$ stays true.

1. Rewrite a for loop as a while loop, so the loop variable has a clear value at every check and at the end.
2. State the invariant as what the loop has done so far, in terms of the loop variable: “the first $i$ elements are sorted”, “$m$ is the largest of $A[0..i-1]$”, “no divisor below $i$”.
3. Initialization: put in the start value of the loop variable. The range is usually empty, so the statement is easy.
4. Maintenance: follow one iteration. Split into cases by the if inside the loop.
5. Termination: put in the stop value. The invariant must now say exactly what the function returns.

Invariant: “$m$ is the largest element of $A[0..i-1]$.”

• Initialization. $i = 1$, and $m = A[0]$, the largest (only) element of $A[0..0]$.
• Maintenance. The iteration looks at $A[i]$. If $A[i] > m$, then $A[i]$ is the new largest of $A[0..i]$, and $m$ becomes $A[i]$. Otherwise $m$ is still the largest. Then $i$ grows by 1, so $m$ is the largest of $A[0..i-1]$ for the new $i$.
• Termination. The loop stops at $i = n$. Then $m$ is the largest of $A[0..n-1]$, the whole array.

void findMinMax(int[] ar, int start, int end, int[] minMax)
// minMax is an array of two integers to return the minimum
// and maximum found
{
    int tempMinMax1[] = new int[2];
    int tempMinMax2[] = new int[2];
    int mid;

    if (start == end) {              // one element array
        minMax[0] = ar[start];
        minMax[1] = ar[start];
    }
    else if (end - start == 1) {     // two element array
        if (ar[start] > ar[end]) {
            minMax[1] = ar[start];
            minMax[0] = ar[end];
        } else {
            minMax[0] = ar[start];
            minMax[1] = ar[end];
        }
    }
    else {                           // array longer than two elements
        mid = (start + end) / 2;

        findMinMax(ar, start, mid, tempMinMax1);
        findMinMax(ar, mid+1, end, tempMinMax2);

        if (tempMinMax1[0] < tempMinMax2[0])
            minMax[0] = tempMinMax1[0];
        else minMax[0] = tempMinMax2[0];

        if (tempMinMax1[1] > tempMinMax2[1])
            minMax[1] = tempMinMax1[1];
        else minMax[1] = tempMinMax2[1];
    }
}

• One element: it is both the min and the max. No comparison.
• Two elements: one comparison decides both the min and the max.
• More: solve each half, then compare the two minimums and the two maximums: 2 comparisons.

Let $W_i$ be the number of comparisons for $i$ elements. Then the recurrence is

$$W_1 = 0, \qquad W_2 = 1, \qquad W_n = W_{n/2} + W_{n - n/2} + 2.$$

If $n = 2^k$, where $k$ is a positive integer, the two halves are equal:

$$W_n = 2W_{n/2} + 2.$$

Expand it:

$$\begin{aligned} W_n &= 2W_{n/2} + 2 \\ &= 2(2W_{n/2^2} + 2) + 2 = 2^2 W_{n/2^2} + 2^2 + 2 \\ &= 2^2(2W_{n/2^3} + 2) + 2^2 + 2 = 2^3 W_{n/2^3} + 2^3 + 2^2 + 2 \\ &\;\;\vdots \\ &= 2^{k-1} W_{n/2^{k-1}} + 2^{k-1} + 2^{k-2} + \dots + 2^2 + 2. \end{aligned}$$

Since $n = 2^k$, we get $n/2^{k-1} = 2$, and $W_2 = 1$. So

$$\begin{aligned} W_n &= 2^{k-1} + 2^{k-1} + 2^{k-2} + \dots + 2^2 + 2 \\ &= 2^{k-1} + 2\,(2^{k-2} + 2^{k-3} + \dots + 2 + 1) \\ &= 2^{k-1} + 2\,(2^{k-1} - 1) \qquad \text{(geometric series)} \\ &= 2^{k-1} + 2^k - 2 \\ &= \frac{n}{2} + n - 2 = \frac{3}{2}n - 2. \end{aligned}$$

1. Read the base cases off the code, with their cost. Here: 1 element costs 0, 2 elements cost 1.
2. Write the recurrence: (number of recursive calls) $\times$ $W$(size of each) + (comparisons in the combine step).
3. Expand it until the size reaches a base case. Count the expansions: from $n = 2^k$ down to size 2 takes $k - 1$ halvings.
4. Add up the combine costs, usually as a geometric series $1 + 2 + \dots + 2^j = 2^{j+1} - 1$.

The saving here comes from the base case of 2: one comparison does the work of two. Compare it with the plain scan, which compares each element with both the current min and the current max: $2(n - 1)$ comparisons.

Now $W_1 = 0$ and $W_n = 2W_{n/2} + 2$. Expand all the way, $k$ times:

$$W_n = 2^k W_1 + (2 + 4 + \dots + 2^k) = 0 + (2^{k+1} - 2) = 2n - 2.$$

That is no better than the plain scan. The $\frac{3}{2}n$ result depends on the two-element base case. At the bottom level there are $n/2$ pairs. Without the base case, each pair costs 2 comparisons (min against min, max against max) instead of 1.

The array is first divided into two equal parts. Each part is sorted by mergesort, which divides it again, until each part holds one item:

Then the parts are merged back:

In total, $4 + 5 + 7 = 16$ comparisons are made.

Where the 5 comes from: merging [14 40] with [28 31] compares 14:28, 40:28, 40:31, then the right list is empty (3). Merging [3 15] with [17 51] compares 3:17, 15:17, then the left list is empty (2).

The splits are the same as for the first array, down to eight single 23s. Then:

In total, $4 + 4 + 4 = 12$ comparisons.

Why only 4 at each level: with equal keys, a merge of $m$ elements costs only $m/2$ comparisons. In the lecture’s in-place merge, one comparison of two equal keys places both of them (Case 3). In a buffer merge that takes from the left on a tie, the left list empties after $m/2$ comparisons. Either way, the count is the best case.

Each comparison sends one element to the output. The comparisons stop when one list is empty. So for two lists with $m$ elements in total:

$$\text{comparisons} = m - (\text{elements still left in the other list}).$$

• Most: $m - 1$, when the last two elements are in different lists (the lists interleave).
• Fewest: the size of the smaller list, when all of it is smaller than all of the other list.

Trace mergesort bottom-up, level by level, and add one count per merge. Check the total against the bounds for $n = 2^k$: best $\frac{n}{2}\lg n$, worst $n \lg n - n + 1$.

In every merge, the left list is entirely smaller, so it empties first. A merge of $m$ elements costs $m/2$:

• pairs: $4 \times 1 = 4$;
• pairs of pairs: $2 \times 2 = 4$;
• final: $4$.

Total 12, the best case $\frac{n}{2}\lg n = 4 \times 3 = 12$.

The worst case is $n \lg n - n + 1 = 24 - 8 + 1 = 17$. So the three arrays give 12 (sorted), 12 (all equal) and 16 (first array). All lie between 12 and 17, as they must.

First, sort the array in increasing (or decreasing) order. Then scan the sorted array once and check for equal adjacent elements. After sorting, equal elements always sit next to each other.

Bool ExistDuplicate(int A[], int n) {
    MergeSort(A, n);   // or Heapsort
    for (int i = 1; i < n; i++) {
        if (A[i] == A[i-1])
            return true;
    }
    return false;
}

The worst-case time for sorting is $\Theta(n \lg n)$, using mergesort (or heapsort). The time for the scan is $\Theta(n)$. Therefore, the overall worst-case running time is $\Theta(n \lg n)$.

Do not use quicksort here: its worst case is $\Theta(n^2)$.

Count how many elements have each key value. Use an array of $2n$ counters, one for each possible value, and use the key value as the index.

• We can quit as soon as any count becomes 2.
• We scan the $n$-element array once, and each element takes constant time to count. So the overall worst-case running time is $\Theta(n)$.
• It uses $\Theta(n)$ extra memory for the counters. Setting them all to 0 also costs $\Theta(n)$.

Many problems ask whether two items are equal, or close, or related. Comparing every pair costs $\Theta(n^2)$. Two faster ways:

1. Sort, then scan neighbours. Related items end up next to each other. Cost: $\Theta(n \log n)$ with mergesort or heapsort, plus $\Theta(n)$ for the scan. This needs only comparisons.
2. Use the key as an index. If the keys are integers in a range of size $R$, an array of $R$ counters answers in $\Theta(n + R)$ time and $\Theta(R)$ memory. This beats sorting only when $R$ is $O(n)$, or at least $o(n \log n)$.

Sort the array with mergesort: $\Theta(n \log n)$. Then scan from both ends:

i = 0; j = n - 1;
while (i < j) {
    if (A[i] + A[j] == x) return true;
    else if (A[i] + A[j] < x) i++;   // need a bigger sum
    else j--;                        // need a smaller sum
}
return false;

Each step moves $i$ or $j$ by one, so the scan is $\Theta(n)$. Total: $\Theta(n \log n)$. It is the “sort, then scan” method: after sorting, the scan never needs to look back.

No. The counter array now needs $R = n^2$ entries. Setting them to 0 alone costs $\Theta(n^2)$ time, and they take $\Theta(n^2)$ memory. Sorting and scanning costs $\Theta(n \log n)$, which is better. The counter method pays off only when the range $R$ is small compared with $n \log n$.

A comparison sort on $n$ elements can be drawn as a decision tree. Each internal node is one comparison. Each leaf is one final order. One run of the algorithm follows one path from the root to a leaf, and the number of comparisons is the length of that path.

• The height (the longest path) is the worst case. It is at least $\lg(n!) = \Omega(n \log n)$, because the tree needs at least $n!$ leaves.
• The shallowest leaf is the best case. This question asks for it.

The smallest possible depth of a leaf is $n - 1$.

Proof sketch.

• Suppose, for a contradiction, that there is a leaf of depth $k < n - 1$.
• Construct a graph $G$ whose vertices are the elements of the array. Connect $(i, j)$ if the algorithm compared the elements at these positions on the path to that leaf. With $k$ comparisons, the graph has only $k < n - 1$ edges, so it cannot be connected.
• In particular, you can split the vertices into two non-empty parts $A$ and $B$, such that no element of $A$ was compared to any element of $B$.
• So the algorithm knows nothing about the order of any element of $A$ against any element of $B$.
• So the order that the leaf gives must be wrong (not sorted) on some input. For example, take an input that agrees with every comparison made, then add a large constant to every element of $A$. The comparisons give the same results, so the run reaches the same leaf, but the correct order has changed.

Insertion sort reaches depth $n - 1$ on a sorted array, so $n - 1$ is achieved.

• Worst case (height): the tree has at least as many leaves as there are possible answers, $L$. A binary tree of height $h$ has at most $2^h$ leaves. So $h \ge \lceil \lg L \rceil$. For sorting, $L = n!$.
• Best case (shallowest leaf): every element must be linked to every other by some chain of comparisons. A connected graph on $n$ vertices needs $n - 1$ edges.

• Worst case: the tree needs $3! = 6$ leaves. Height 2 gives at most $2^2 = 4$ leaves, which is too few. So the height is at least $\lceil \lg 6 \rceil = 3$.
• Best case: at least $n - 1 = 2$. Insertion sort reaches it on a sorted input: $a_1 \le a_2$, then $a_2 \le a_3$, and it stops.

The two versions differ only in the last loop:

for i <- 0 to k                        for i <- 0 to k
    do C[i] <- 0;                          do C[i] <- 0;
for j <- 0 to length[A] - 1            for j <- 0 to length[A] - 1
    do C[A[j]] <- C[A[j]] + 1;             do C[A[j]] <- C[A[j]] + 1;
for i <- 1 to k                        for i <- 1 to k
    do C[i] <- C[i] + C[i-1];              do C[i] <- C[i] + C[i-1];
for j <- length[A] - 1 downto 0   =>   for j <- 0 upto length[A] - 1
    do begin                               do begin
        C[A[j]] <- C[A[j]] - 1;                C[A[j]] <- C[A[j]] - 1;
        B[C[A[j]]] <- A[j];                    B[C[A[j]]] <- A[j];
    end-for                                end-for
return B                               return B

Example of the “new” counting sort on $[3, 4, 1, 4]$, with keys 0 to 4:

• Histogram: $[0, 1, 0, 1, 2]$.
• Cumulative sum: $[0, 1, 1, 2, 4]$.
• Placement loop run, from $j = 0$:

• It would still be correct. Every element still lands in the block of slots for its key, so the output is sorted.
• But it would no longer be stable. The first 4 in $A$ took the last slot for 4. The order of equal-valued elements is reversed, instead of being preserved.

Take two equal keys, $x_a$ before $x_b$ in the input. Follow the algorithm and ask: which one ends at the higher index?

• For counting sort, the last loop fills each key’s slots from the right, because it decrements before it writes. So the element it meets first gets the rightmost slot. To keep $x_a$ before $x_b$, the loop must meet $x_b$ first: it must run backwards.
• Correctness and stability are separate questions. A sort can be correct and not stable.

• Pass 1, last digit: the digits are 2 and 1. The keys differ, so the pass sorts them correctly: 11, 12.
• Pass 2, first digit: both first digits are 1, so the keys are equal. The forward loop reverses equal keys: 12, 11.

The result, 12 then 11, is not sorted. Radix sort needs a stable inner sort. The second pass must keep the order that the first pass set up.

Consider a subrange of $k$ elements to be partitioned.

• Choosing the pivot requires 3 key comparisons in the worst case.
• Now $k - 3$ elements remain to be compared to the pivot. It is easy to avoid comparing the other two candidates again: swap them to the two ends of the subrange. Their side is already known.
• So $k$ comparisons are done by the time the partition is finished.
• This is one more than if the middle element is simply chosen as the pivot ($k - 1$).

• An example of the worst case: E[first] = 100, E[(first + last)/2] = 99, E[last] = 98, and all other elements are over 100.
• Then 99 becomes the pivot. 98 is the only element smaller than the pivot, and $k - 2$ elements are greater than the pivot.
• The remaining keys can be chosen so that the worst case repeats: the median of three always comes out as the second-smallest key in the range.
• The larger subrange shrinks by only 2 at each level of recursion. So quicksort needs $n/2$ calls to partition, on ranges of size $n, n-2, n-4, \dots, 2$ (suppose $n$ is even). The total number of comparisons is

$$\begin{aligned} f &= n + (n-2) + (n-4) + \dots + 2 \\ f &= 2 + 4 + \dots + (n-2) + n \\ 2f &= (n+2) + (n+2) + \dots + (n+2) = \frac{n(n+2)}{2} \qquad (n/2 \text{ terms}) \\ f &= \frac{n^2 + 2n}{4} = \Theta(n^2). \end{aligned}$$

• When $n$ is odd, the total number of comparisons is also about $n^2/4$.
• So the worst-case time complexity with the median-of-3 strategy is $\Theta(n^2)$.

Error in the official solution: it writes the middle position as “E[first + last/2]”. The middle index is $\lfloor(\text{first} + \text{last})/2\rfloor$. Without the brackets, it would be first + (last/2).

1. Find the worst pivot the rule can pick: how many elements can the adversary force onto the small side? Say the small side gets $r - 1$ elements, so each partition removes only $r$ elements (the pivot plus $r - 1$).
2. The ranges then have sizes $n, n - r, n - 2r, \dots$. That is about $n/r$ partitions.
3. Each partition of $k$ elements costs about $k$ comparisons. The sum is about $\frac{n}{r} \cdot \frac{n}{2} = \frac{n^2}{2r}$.

Any rule that looks at a constant number of elements leaves $r$ constant, so the worst case stays $\Theta(n^2)$. Middle element: $r = 1$, about $n^2/2$. Median of three: $r = 2$, about $n^2/4$.

The adversary makes the five sampled elements the five smallest of the range. Their median is then the third-smallest of the range. Only 2 elements go to the small side, so each partition removes $r = 3$ elements.

By the method: about $\frac{n^2}{2 \cdot 3} = \frac{n^2}{6}$ comparisons, plus a few more per partition to find the median. Still $\Theta(n^2)$.

At an intermediate step, the elements are divided into four regions:

• the first contains only reds;
• the second contains only whites;
• the third contains elements whose colours are not known yet;
• the fourth contains only blues.

There are three indexes: r (end of the reds), u (first unknown) and b (the edge of the blues).

The official algorithm:

int r; // index of last red
int u; // index of first unknown
int b; // index of first blue

r = 0; u = 0; b = n-1;
while (u < b)
    if (E[u] == red)
        Interchange E[r] and E[u];
        r++;
        u++;
    else if (E[u] == white)
        u++;
    else // (E[u] == blue)
        Interchange E[b] and E[u]
        b--;

• With each iteration of the while loop, either u increases by one or b decreases by one. So there are $n$ iterations.
• Each iteration takes constant time, so the overall time is linear, $\Theta(n)$.

Error in the official code. With b = n-1 and the blue case “swap, then b--”, the index b points at the last unknown element, not the first blue. The loop while (u < b) then stops one element early: the element at u == b is never examined. Example: $[\text{white}, \text{red}]$. It starts with r = 0, u = 0, b = 1. E[0] is white, so u = 1. Now u < b is false and the loop ends, leaving white before red.

The fix is one character: while (u <= b). (Chapter 4 uses the other common form: b = n, and in the blue case b-- first, then swap, with while (u < b).)

1. Draw the array as regions, one per group, plus one unknown region. Name the index at each border.
2. Write what each region holds. This is the loop invariant.
3. For each possible value of the next unknown element, write the swap and the index moves that put it in its region and keep the invariant.
4. Check that every iteration shrinks the unknown region by exactly one. Then the loop runs $n$ times: $\Theta(n)$.
5. Test the code by hand on two-element inputs. Off-by-one errors in the stop condition show up at once.

Each iteration makes at most one swap, and there are $n$ iterations. So at most $n$ swaps.

An array of $n$ blues reaches it. Every iteration finds a blue at u and swaps it with the element at b (also a blue), then moves b down. That is $n$ swaps, even though nothing needed to move. Each iteration still shrinks the unknown region by one, as the method requires.

• In a max-heap, every node is at least as large as its children. Node $k$ has children $2k$ and $2k+1$.
• fixHeap repairs one node whose two subtrees are already heaps. At each level it makes 2 comparisons: one to find the larger child, one to compare that child with the sinking key. If the child is larger, the child moves up.
• To build a heap, fix every node that has a child, children before parents. The lecture’s recursive heapifying does this in post-order: left subtree, right subtree, then the root. The loop from node $\lfloor n/2 \rfloor$ down to 1 gives the same heap.
• Here “larger” means “earlier in the year”.

heapifying fixes the nodes in post-order: 4, 5, 2, 3, then 1.

Heapifying performs 14 date comparisons and 5 swaps in the heap construction phase. The resulting array is:

1. Draw the array as a tree, level by level. Number the nodes.
2. List the nodes with children: $\lfloor n/2 \rfloor$ down to 1. (Post-order gives the same final heap.)
3. For each one, sink its key: compare the two children (1), then compare the larger child with the key (1). If the child is larger, it moves up and the key continues down. A node with one child costs only 1 comparison at that level.
4. Count per fix: moves = levels sunk; comparisons = about 2 per level visited.
5. Check the result: every parent beats both children.

Insert puts 15 Jan at the next free position, node 12, then bubbles it up while it beats its parent.

• The parent of 12 is node 6 (22 Mar). 15 Jan is earlier, so they swap. (1 comparison)
• The parent of 6 is node 3 (21 Feb). Swap. (1 comparison)
• The parent of 3 is node 1 (30 Jan). 15 Jan is earlier. Swap. (1 comparison)

3 comparisons, one per level. Insert costs at most the height, $\lfloor \lg 12 \rfloor = 3$.

$2 + 1 + 2 + 2 + 2 = 9$.

Node $i$ is an internal node (not a leaf) if and only if $1 \le 2i \le n$, so $\frac{1}{2} \le i \le \frac{n}{2}$. Thus:

• if $n$ is even, there are $n/2$ internal nodes;
• if $n$ is odd, there are $(n-1)/2$ internal nodes.

Since the keys are in decreasing order, fixHeap does only one or two key comparisons each time it is called, and no key moves.

• If $n$ is even, the last internal node has only one child. So fixHeap does only one comparison at that node, and two at each other internal node. Total: $2(n/2 - 1) + 1 = n - 1$.
• If $n$ is odd, each of the $(n-1)/2$ internal nodes has two children. fixHeap does two comparisons at each. Total: $2 \times (n-1)/2 = n - 1$.

In both cases, the total is $n - 1$ key comparisons.

It is the best case. No key moves. So in the heapifying algorithm, fixHeap only compares the root with its two children, and never needs to continue down, as it does in an intermediate or worst case.

Every internal node must be compared with its children at least once, so no input can do fewer comparisons.

• Best case (no key moves): each internal node costs 2, or 1 if it has a single child. There are $\lfloor n/2 \rfloor$ internal nodes, and only node $n/2$ (when $n$ is even) has one child. The total is always $n - 1$.
• Any other input: trace it with the method of Q1. Each extra level a key sinks costs up to 2 more comparisons.
• Worst case: still $O(n)$, because most nodes sit near the bottom and can sink only a little.

Use the loop order 5, 4, 3, 2, 1.

Total: $1 + 2 + 2 + 3 + 6 = 14$ comparisons, against 9 for the decreasing array. The increasing array is not the best case, because keys must sink.

One algorithm is to use a maximizing heap.

1. First, insert the $k$ elements from the heads of the $k$ sorted lists into a maximizing heap. This takes $O(k)$ time.
2. Then, use getMax() to obtain the maximum element from the heap, and append it at the end of the merged list (initially empty). Suppose this element came from the $j$-th list. Then insert the element from the next position of the $j$-th list into the heap, using fixHeap: it takes the place of the root and sinks.
3. Continue in this fashion until all the $k$ lists have been exhausted. (When list $j$ is empty, the last heap element takes the root’s place instead, and the heap shrinks by one.)

Analysis. For one element, an insertion using fixHeap takes $O(\log k)$ time, because the heap never holds more than $k$ elements. Hence for the $n$ elements, the running time is $O(n \log k)$.

Example. Input: three sorted arrays $A_1 = [9, 7, 5, 2]$, $A_2 = [4, 3, 1]$, $A_3 = [8, 6, 2, 1, 0]$. Output: a merged list $M$.

Continue in this fashion until all the input lists are exhausted.

When the answer comes out in order but only a few items can be “next” at any time, keep only those candidates in a heap.

• Here, the next output is always one of the $k$ current heads. So the heap holds $k$ items, and each step costs $O(\log k)$, not $O(\log n)$.
• Total = (number of outputs) $\times$ (cost per heap step) = $n \times O(\log k)$.
• Use a max-heap for lists in decreasing order, a min-heap for increasing order.

Merging two lists costs about their total length.

• Merge $i$ joins a list of $i \cdot n/k$ elements with one of $n/k$, so it costs about $(i+1)\,n/k$.
• Summed over $i = 1, \dots, k-1$: about $\frac{n}{k} \cdot \frac{k^2}{2} = \frac{nk}{2}$.

That is $O(nk)$, worse than $O(n \log k)$. The early elements are copied again in every merge. The heap touches each element only once.

The BFS from the lecture:

function bfs(v1):
    queue := {v1}
    mark v1 as visited
    v1.d = 0

    while queue is not empty:
        v := queue.removeFirst()
        for each unvisited neighbour n of v:
            n.d = v.d + 1
            mark n as visited
            queue.addLast(n)

Adjacency list.

• We iterate through Adj[$v$] once for every vertex.
• This has worst-case runtime $\Theta(|E|)$ per vertex (when all edges are adjacent to $v$), but is typically lower.
• The overall runtime is $\Theta(|V| + |E|)$, by considering the total length of the adjacency lists.

Adjacency matrix.

• We must iterate through the whole row of $v$ in the matrix $A_G$.
• This always has runtime $\Theta(|V|)$.
• Since we do this for every vertex, the overall runtime is $\Theta(|V|^2)$.

The modification: replace “for each unvisited neighbour $n$ of $v$” with a scan of row $v$:

        for n = 1 to |V|:
            if A[v][n] == 1 and n is unvisited:
                n.d = v.d + 1
                mark n as visited
                queue.addLast(n)

Total = (work per vertex) + (cost of finding the neighbours of every vertex once).

The algorithm is the same. Only the neighbour loop changes. The same table holds for DFS.

• Adjacency list: about $|V| + |E| = 1000 + 3000 = 4000$. (An undirected graph stores each edge twice, so about 7000.)
• Adjacency matrix: about $|V|^2 = 1{,}000{,}000$.

The graph is sparse ($3000 \ll 1000^2$), so the list is far better.

We can use a last-in, first-out (LIFO) stack.

function dfs():
    mark all vertices as unvisited
    while there exists an unvisited vertex v:
        dfsVisit(v)

// Explore all vertices reachable from v in depth-first order
function dfsVisit(v):
    S = empty stack
    S.push(v)

    while S is non-empty:
        w = S.pop()
        mark w as visited
        for each unvisited neighbour x of w:
            S.push(x)

A gap in the official code. A vertex can be pushed more than once before it is visited. Example: the triangle $a$–$b$, $a$–$c$, $b$–$c$. Visiting $a$ pushes $b$ and $c$. Popping $c$ visits it and pushes $b$ again, because $b$ is still unvisited. Now $b$ is on the stack twice, and the code visits it twice. Add one line after the pop:

        w = S.pop()
        if w is visited: continue     // w was pushed more than once
        mark w as visited

• The call stack holds “work still to do”. Replace it with your own stack: push what the recursion would call, pop to continue.
• The stack returns the last item pushed. So to visit the neighbours in the same order as the recursive version, push them in reverse order.
• Check “already visited” when you pop, because an item can be pushed several times.
• BFS is the same loop with a queue in place of the stack.

• Recursive: $a$, then its first neighbour $b$, then $b$’s neighbour $d$. Back up to $a$, then $c$. Order: $a, b, d, c$.
• Stack: pop $a$, push $b$ then $c$. Pop $c$ (last pushed): visit it. Pop $b$: visit it, push $d$. Pop $d$. Order: $a, c, b, d$.

Push the neighbours in reverse alphabetical order ($c$ then $b$). Then $b$ is popped first, and the order becomes $a, b, d, c$.

Row $i$, column $j$ holds the weight of the edge from $i$ to $j$.

After initialization:

1st iteration: vertex 1 joins $S$. Its edges set $d$ = 4, 2, 6, 8.

2nd iteration: vertex 3 ($d = 2$) joins. Edge 3→4: $2 + 1 = 3 < 6$.

3rd iteration: vertex 4 ($d = 3$) joins. Edge 4→2: $3 + 1 = 4$, not smaller than 4. Edge 4→5: $3 + 3 = 6 < 8$.

4th iteration: vertex 2 ($d = 4$) joins. Edge 2→5: $4 + 3 = 7$, not smaller than 6. (Edge 2→4 leads to a vertex already in $S$.)

5th iteration: vertex 5 joins.

Shortest paths (follow $pi$ back to 1): 1 – 2, 1 – 3, 1 – 3 – 4, 1 – 3 – 4 – 5.

1. One column per vertex, rows $S$, $d$, $pi$. Start: $d = 0$ at the source, $\infty$ elsewhere.
2. Each iteration: among the vertices with $S = 0$, pick the smallest $d$ (break ties by the rule the question gives). Set its $S = 1$.
3. For each edge from it to a vertex with $S = 0$: if $d(u) + w < d(v)$, write the new $d$ and set $pi = u$. Equal is not smaller: leave it.
4. Checks: vertices join $S$ in non-decreasing $d$; a vertex in $S$ never changes again.
5. Read each path backwards through $pi$.

• Iteration 1: vertex 1. $d$ = (0, 4, 2, 6, 8), $pi$ = (null, 1, 1, 1, 1).
• Iteration 2: vertex 3 ($d = 2$). 3→4: $2 + 5 = 7$, not smaller than 6. No change.
• Iteration 3: vertex 2 ($d = 4$). 2→4: $8$, no. 2→5: $4 + 3 = 7 < 8$, so $d(5) = 7$ and $pi(5) = 2$.
• Iteration 4: vertex 4 ($d = 6$). 4→5: $9$, no.
• Iteration 5: vertex 5.

Vertex 4 is now reached by the direct edge, and vertex 5 through vertex 2.

Add a counter v.count: the number of shortest paths from the source to $v$ found so far.

shortest_paths( Graph g, Node source )
// The array count[] records the number of shortest paths from
// source to each of the vertices
{
    for each vertex v {
        v.d = infinity;
        v.pi = null pointer;
        S[v] = 0;
        v.count = 0;
    }
    source.d = 0;
    source.count = 1;
    put all vertices in queue, Q, in v.d's order;

    while not Empty(Q) {
        u = ExtractCheapest( Q );
        S[u] = 1;  /* Add u to S */
        for each vertex v adjacent to u
            if (S[v] != 1 && v.d > u.d + w[u,v]) {
                remove v from Q;
                v.d = u.d + w[u,v];
                v.pi = u;
                // the shortest paths to u extends to v, the
                // previously known shortest path(s) to v is replaced
                v.count = u.count;
                insert v into Q according to its v.d;
            }
            else if (v.d == u.d + w[u, v]) {
                // additional shortest path(s) through u to v is found
                v.count += u.count;
            }
    }
}

At the end, z.count is the answer.

• A strictly shorter path through $u$: every old path to $v$ is no longer shortest. The new shortest paths are exactly the shortest paths to $u$, plus the edge. So v.count = u.count.
• An equally short path through $u$: these are new shortest paths, added to the old ones. So v.count += u.count.

Error in the official code: it sets source.d = 1 after source.d = 0. It must be source.count = 1. Otherwise every count stays 0, and the source’s distance is wrong.

Attach an extra value to each vertex, and update it in the relax step, with two cases:

• Count of shortest paths: replace with u.count; combine by adding.
• Fewest edges among the shortest paths: replace with u.edges + 1; combine by taking the minimum.

Why positive weights matter: every vertex before $v$ on a shortest path has a strictly smaller $d$, so it leaves the queue before $v$. Its count is final before it is passed on. With a zero-weight edge, $u$ and $v$ can have the same $d$, and $v$ may leave the queue first and miss $u$’s paths.

3 shortest paths, each of length 2: $s \to t$, $s \to a \to t$, $s \to b \to t$. The first relax of $t$ used “replace”. The next two used “combine”.

Proof by contradiction. Suppose there exists a connected weighted graph $G = (V, E, W)$ whose edge weights are all different, with two distinct minimum spanning trees $T_1$ and $T_2$.

Among all the edges where $T_1$ and $T_2$ differ, that is, from the set $(T_1 \setminus T_2) \cup (T_2 \setminus T_1)$, select the edge $(p, q)$ of minimum weight. This edge is unique, because all edge weights are different. Assume, without loss of generality, that $(p, q) \in T_1$. Now, $T_2$ must contain some other path from $p$ to $q$, which is not simply the edge $(p, q)$.

In particular, there must be some edge $e$ along this path in $T_2$ which does not occur in $T_1$. If all edges in the path occurred in $T_1$, then $T_1$ would contain a cycle (that path plus $(p, q)$). Notice that $T = T_2 \cup \{(p, q)\} \setminus e$ is a spanning tree: adding $(p, q)$ makes one cycle, and removing $e$ from that cycle breaks it again.

However, from the way we selected $(p, q)$, we know that $e$ must have greater weight than $(p, q)$: $e$ is also a differing edge, and $(p, q)$ is the lightest of them. Thus, $T$ is a spanning tree of smaller weight than $T_2$. This contradicts the assumption that $T_2$ is a minimum spanning tree.

Most MST proofs use the same swap:

1. Add an edge $e$ that is not in tree $T$. This creates exactly one cycle.
2. Remove any other edge $f$ of that cycle. The result is again a spanning tree.
3. Its weight changes by $w(e) - w(f)$. If that is negative, $T$ was not minimum.

To prove uniqueness, pick the lightest edge where two trees differ, and swap it into the other tree. To prove that an edge is in no MST, show that some swap would remove it and lower the weight.

No. Take edges $s$–$a$ (1), $a$–$t$ (2) and $s$–$t$ (3). All weights differ. Both $s \to t$ and $s \to a \to t$ have length 3.

The MST argument works because two trees can be compared by swapping one edge for one edge. A path length is a sum along a path, and two different sums of distinct numbers can still be equal.

In Prim’s algorithm, $v.d$ is the weight of the cheapest single edge from $v$ to the tree so far, and $v.\pi$ is the tree vertex at the other end. The update is $v.d = w(u, v)$, not $u.d + w(u, v)$ as in Dijkstra. Each iteration adds the vertex outside the tree with the smallest $d$.

After initialization (the official tables mark G in $S$ from the start):

1st iteration: G’s edges update A, B, D and E.

2nd iteration: edge GD becomes part of the MST. D’s edges: E gets 2 (better than 3), F gets 5.

3rd iteration: edge DE becomes part of the MST. E’s edges: C gets 2.

4th iteration: edge EC becomes part of the MST. C’s edges: B gets 4 (better than 6).

5th iteration: edge GA becomes part of the MST. A’s edges: B gets 2 (better than 4). F: 7 is not better than 5.

6th iteration: edge AB becomes part of the MST.

7th iteration: edge DF becomes part of the MST.

The MST edges are GD, DE, EC, GA, AB and DF. The total weight is $1 + 2 + 2 + 3 + 2 + 5 = 15$, the sum of the final $d$ values.

It is Dijkstra’s table with one change in the update.

1. Pick the vertex with $S = 0$ and the smallest $d$. Set $S = 1$. The edge $(\pi, v)$ joins the tree.
2. For each neighbour $w$ with $S = 0$: if the edge weight $w(v, w)$ is smaller than $w.d$, set $w.d$ to that weight and $w.\pi = v$.
3. The MST weight is the sum of the final $d$ values.