07 Divide-and-Conquer

. ## The Concept of Divide and Conquer Algorithmic Technique

• Break the input into two or more parts,
• Solve the problem in each part (subproblems) recursively, and
• Combine the solutions to these subproblems into an overall solution.

Merge Sort

Problem: Given a list of numbers, sort them in ascending order. (In practice, we can sort strings, too. We can also sort them in descending order.)

Idea

• Cut the list (array) of numbers in half.
• Recursively merge sort each half.
• Merge the two sorted halves into one sorted list (in O(n) time).

Example of Merge Sort

Mergesort Pseudocode

Mergesort(L)
    If the list has one element then
        Return L.
    Else
        Divide the list into two halves:
            A contains the first ⌈n/2⌉ elements
            B contains the remaining ⌊n/2⌋ elements
        A = Mergesort(A)
        B = Mergesort(B)
        L = Merge(A, B)
        Return the sorted list L
    EndIf

Merging two sorted lists in O(n) time: The Idea

• Suppose the two sorted lists are called A and B.
• Compare the smallest element in A with the smallest element in B.
• Remove the smaller element from the corresponding list (A or B) and add it to the end of the output list L.
• Repeat until one of the lists is empty. Add the remaining elements from the other list to the end of L.

Merge Pseudocode

Merge(A, B)
    Maintain a Current pointer into each list, initialized to 
    point to the front elements
    While both lists are nonempty:
        Let a_i and b_j be the elements pointed to by the Current pointers
        Append the smaller of these two to the output list
        Advance the Current pointer in the list
        from which the smaller element was selected
    EndWhile
    Once one list is empty, append the remainder of the other list to
    the output
    Return the merged list

• ก็ไม่มีไรนะ จำได้ใช่มั้ยว่า Merge Sort มันจะมีอยู่ 2 functions: แยกกับจับรวม อันนี้ก็แค่มาเขียนของ รวม ให้ดู!

Note that the running time of merge sort satisfies the two inequalities in Theorem (5.2) above.

Theorem (ไม่พูดเลย)

The Merge sort algorithm correctly sorts the input list; it runs in O(n log n) time for a list with n elements.

Proof: Note: The natural way to prove that a divide-and-conquer algorithm is correct is by induction.

Let's prove the correctness of Mergesort by induction.

• Base case: n = 1.
  • Trivially true as a list with one element is "sorted" correctly without having to do anything.
• Induction case: n > 1.
  • Suppose Mergesort is correct on any inputs containing fewer than n elements. (This is our I.H.)
  • That is, calling Mergesort on A and B return the correctly sorted lists.
  • After A and B are sorted, showing that Merge(A,B) correctly returns the whole sorted list of size n completes the induction (Details left as an exercise).
  • The running time follows from Theorem (5.2) directly.

Quick Sort

Quicksort is also a divide-and-conquer algorithm.

Quick sort Idea

• Choose an element to be a pivot (somehow).
• Move all elements smaller than the pivot to the left "half" of the list and all elements larger than the pivot to the right "half" of it (in $O(n)$ time). This step is known as partitioning.
• (Elements equal to the pivot can be on either side.)
• Recursively quick sort the left part and the right part.

Note on Partitioning

• There are many ways to partition the arrays.
• We will cover Hoare partition scheme, which is quite efficient but may not be as easy to understand.
  • (Lomuto scheme is easy to understand but not as efficient)
• With Hoare scheme, the final location of the pivot after partitioning can be anywhere so we need to adjust the recursive calls accordingly.
• In addition, care must be taken in order to deal with elements equal to the pivot correctly.
• There are even better and more complicated schemes.

Quicksort Pseudocode

Quicksort(L, l, r)
    If l < r then
        p = Partition(L, l, r)
        Quicksort(L, l, p)
        Quicksort(L, p + 1, r)
    EndIf

Hoare Partition Scheme: The Idea

• Have one pointer starting from the leftmost element.
• Move the pointer toward the right until we find an element that is greater than or equal to the pivot.
• Have another pointer starting from the rightmost element.
• Move the second pointer toward the left until we find an element that is smaller than or equal to the pivot.
• Swap the two elements that the two pointers point to (as they are out of order).
• Keep going until the two pointers meet or cross.
• Return the location of the second pointer as p.
• (Now, all elements smaller than or equal to the pivot are in position l, l + 1, ..., p and all elements greater than or equal to the pivot are in position p + 1, ..., r.)

Partition Pseudocode (Hoare scheme)

Partition(L, l, r) // Hoare scheme
    Let piv be a chosen pivot (i.e., piv = L[k] for a chosen k).
    Set i = l - 1 and j = r + 1
    While true
        Do
            i = i + 1
        While L[i] < piv
        Do
            j = j - 1
        While L[j] > piv
        If i ≥ j then
            Return j
        EndIf
        Swap L[i] with L[j].
    EndWhile

The pseudocode assumes that L is passed by reference. The initial call to sort the array L[1...n] is Quicksort(L, 1, n).

Lomuto

• เหมือนครูจะพยายามพูดถึง ไปเรียนด้วยว่ามันคืออะไรนะ!

Running Time

• Worst-case: $O(n^2$).
• Average-case: $O(n \log n)$.
• Good ways to choose a pivot to avoid the worst-case:
  • Choosing randomly.
  • Choosing the median of the first, middle, and last elements (Median-of-three).
• In practice, quicksort is faster than mergesort on average.

More comments

• For Mergesort, the dividing step is trivial but the combining step requires a lot of work.
• For Quicksort, the dividing step requires a lot of work but the combining step is trivial.
• For other problems, you may have to do lots of work for both the dividing and the combining steps.

Finding the kth smallest element in an unordered list

Example: 10, 4, 5, 7, 2.

• The 2nd smallest element is 4.
• The 3rd smallest element is 5.
• The 4th smallest element is 7.

Naive way (Brute Force นั่นแหละ): Sort the list and then look at the element in the kth position. O(n log n).

But we can do better using the idea from quicksort.

The Idea

• After we partition (e.g. using Hoare scheme) the unordered list, elements in the left "half" stay in the left "half" until the end.
• Similarly, elements in the right "half" stay there until the end.
• That is, if k ≤ p, then the kth smallest element is somewhere in the left "half".
• If k > p, the kth smallest element is somewhere in the right "half".
• Then we recursively find the desired element in the correct half only.
• No need to search in the other half.
• The resulting algorithm is known as Quickselect.

Quickselect Pseudocode

Quickselect(L, l, r, k)
    If l = r then
        Return L[l].
    Else
        p = Partition(L, l, r)
        If k ≤ p then
            Quickselect(L, l, p, k)
        Else
            Quickselect(L, p + 1, r, k)
        EndIf

Running time of Quickselect

• Worst-case is O(n²).
• But average-case is O(n).

"Proof" that the average-case running time of Quickselect is O(n)

• Suppose each call reduces the number of elements by a constant factor of $m > 1$.
• The recurrence of the running time is therefore $T(n) = T(n/m) + cn$, where T(n) is the running time of Quickselect on n elements.

since (1/m) < 1 as m > 1.

Counting Inversions

Suppose we have ten different movies and we ask two people to rank them according to their preferences. Question: How similar are the two rankings?

Applications: Recommendation systems in many web sites (e.g. online shopping, online video sharing sites), meta-search tools in the Web (searching the same query on many different search engines and synthesizing the results).

Say, we want to compare your ranking and a stranger's ranking. We have a set of n movies. Let's label the movies 1, 2, ..., n according to your ranking. Then order the labels according to the stranger's ranking and see how many pairs are "out-of-order."

Problem Formulation

Given a sequence of n distinct numbers $a_1,\dotso,a_n$ (This is the stranger's ranking). We want to define a measure of how far this list is from being in ascending order 1, ..., n (Your ranking). One measure: Counting the number of inversions. Two indices i < j are said to form an inversion if aᵢ > aⱼ. That is, aᵢ and aⱼ are "out-of-order."

Example of inversions

Count the number of inversions for the following:

• 3, 2, 1, 4.
• 1, 2, 5, 3, 4.

Solution

• 3, 2, 1, 4.
  • The inversions are: (3, 2), (3, 1), (2, 1). So three inversions.
• 1, 2, 5, 3, 4.
  • The following are inversions: (5, 3), (5, 4). So two inversions.

Brute-force algorithm for counting inversions

To count inversions, we can simply check every pair for possible inversions in O(n²) time, as in the following pseudocode:

Set c to 0
For i = 1 to n - 1
    For j = i + 1 to n
        If aᵢ > aⱼ
            Increase c by one.
        EndIf
    EndFor
EndFor
Return c // This is the number of inversions.

Designing the Algorithm

Say we want to count the number of inversions for 1, 8, 5, 6, 3, 7, 4, 2 efficiently.

First, let's try cutting the sequence in half. Then recursively count inversions on each half.

• That is, the left half is 1, 8, 5, 6 and the right half is 3, 7, 4, 2.
• Recursively count the inversions on the left half. We get two inversions: (8, 5) and (8, 6).
• Recursively count the inversions on the right half. We get four inversions: (3, 2), (7, 4), (7, 2) and (4, 2).

Are we done? Six inversions for the original sequence?

No. Because we haven't count inversions $(a_i,a_j)$ where $a_i$ and $a_j$ are in different halves!

• Specifically, $a_i>a_j$ and $a_i$ is in the left half while $a_j$ is in the right half.
• Examples: (8, 7), (6, 2).

Counting across-half inversions

Note: For the whole divide-and-conquer algorithm to be faster than O(n²) time, we must count across-half inversions in $O(n)$ time.

Moreover, there can be up to $\frac{n^2}{4}$ across-half inversions.

Let's assume that the two halves are sorted in ascending order.

• First, since we already divide the list by half and recursively work on each half, this is very much like mergesort.
• So we can mergesort and count inversions at the same time! Merging the two halves is $O(n)$ so it won't make our algorithm asymptotically slower anyway.
• So the assumption that the two halves are sorted is OK.

Consider the merging step of mergesort.

• Let A be the left half and B be the right half.
• We have two pointers, one for A and one for B as before, initialized to point to the front elements.
• Let aᵢ and bⱼ be the elements pointed to by the two pointers.
• Recall we compare aᵢ and bⱼ and add the smaller one to the sorted list.

Observe: If aᵢ is smaller than bⱼ,

• It means aᵢ is also smaller than everything left in B and comes before all of them.
• This means there are no across-half inversions involving aᵢ at all!
• So we append aᵢ to the sorted list and advance the pointer normally.

What if bⱼ is smaller than aᵢ instead?

• It means bⱼ is also smaller than everything left in A and comes after all of them.
• That is, bⱼ forms across-half inversions with all remaining elements in A (including aᵢ)!
• So we append bⱼ to the sorted list, advance the pointer normally, and add the number of elements currently in A to the number of across-half inversions.

Merge-and-Count Pseudocode

Merge-and-Count(A, B)
    Maintain a Current pointer into each list, initialized to
    point to the front elements
    Maintain a variable Count for the number of inversions,
    initialized to 0
    While both lists are nonempty:
        Let aᵢ and bⱼ be the elements pointed to by the Current pointer
        Append the smaller of these two to the output list
        If bⱼ is the smaller element then
            Increment Count by the number of elements remaining in A
        EndIf
        Advance the Current pointer in the list
        from which the smaller element was selected
    EndWhile
    Once one list is empty, append the remainder of the other list to
    the output
    Return Count and the merged list

Sort-and-Count Pseudocode

Sort-and-Count(L)
    If the list has one element then
        there are no inversions. Return 0 and L.
    Else
        Divide the list into two halves:
            A contains the first ⌈n/2⌉ elements
            B contains the remaining ⌊n/2⌋ elements
        (rA, A) = Sort-and-Count(A)
        (rB, B) = Sort-and-Count(B)
        (rX, L) = Merge-and-Count(A, B)
        Return r = rA + rB + rX and the sorted list L
    EndIf

• Use sort-and-count to count the number of inversions for the following sequence: 7, 1, 6, 2, 5, 3, 8, 4

Theorem

The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in $O(n \log n)$ time for a list with n elements. Already proven in the derivation.

Finding the Closest Pair of Points

The Problem: Given n points in the plane, find the pair that is closest together. Applications in graphics, computer vision, geographic information systems, and molecular modeling, for example.

Simple Algorithm: Compute the distance between every possible pair of points and output the closest one. $O(n^2)$ running time.

Can we do better with a divide and conquer approach?

Notations and Assumptions

• Denote the set of points by P = {p₁, ..., pₙ}.
• pᵢ has coordinates (xᵢ, yᵢ).
• Use d(pᵢ, pⱼ) to denote the standard Euclidean distance between them.
• Goal: Find a pair of points pᵢ, pⱼ that minimizes d(pᵢ, pⱼ).
• Assume no two points in P have the same x-coordinate or the same y-coordinate.
• This assumption can be removed by rotating the points to make it true, or by slightly extending the algorithm.

Designing the Algorithm

• Divide the points in the middle, to the "left half" and the "right half".
• Use recursion to find the closest pair among the points in the left half and the closest pair among the points in the right half.
• We also have to consider the pairs of points where one point is in the left half and the other is in the right half.
• There are about $\frac{n^2}{4}=\frac{n}{2}*\frac{n}{2}$ such pairs.
• But we need to find the smallest one among them in $O(n)$ time (Otherwise, the whole algorithm would not be faster than the brute-force algorithm).
  • 55555 ไม่ใช่ว่า ทำ algorithm มาแล้วช้ากว่า brute force จะบ้า

Start with a few things first

• Before any recursion begins, sort all the points in P in increasing x-coordinate and again by y-coordinate, producing lists Pₓ and Pᵧ.
• At the beginning of every recursive call, on a set P' ⊆ P, we want to have the lists P'ₓ and P'ᵧ (which will be useful later).
• P'ₓ is the list of all points in P' sorted by increasing x-coordinate.
• P'ᵧ is the list of all points in P' sorted by increasing y-coordinate.
• Define Q to be the set of points in the first ⌈n/2⌉ positions of the list Pₓ (the "left half" of P).
• Define R to be the set of points in the final ⌊n/2⌋ positions of the list Pₓ (the "right half" of P).
• Note that we can create Qₓ, Qᵧ, Rₓ, and Rᵧ in O(n) time by a single pass through Pₓ and Pᵧ.

Let x* denote the x-coordinate of the rightmost point in Q. Let L denote the vertical line described by the equation x = x* Let q_₀ and q_₁ be the closest pair of points in Q. Let r_₀ and r_₁ be the closest pair of points in R. Let δ = min{d(q_₀, q_₁), d(r_₀, r_₁)}. This means that we need only consider the across-half pairs whose distances may be smaller than δ.

Lemma (5.8)

If there exist q ∈ Q and r ∈ R for which d(q, r) < δ, then each of q and r lies within a distance δ of L.

Let S ⊆ P denote the set of points in P within δ of L. Let Sᵧ be the list of the points in S sorted by increasing y-coordinate. Note: Sᵧ can be constructed in O(n) time by a single pass through Pᵧ.

Restate (5.8) in terms of S as follows:

Lemma (5.9)

There exist q ∈ Q and r ∈ R for which d(q, r) < δ if and only if there exist s, s' ∈ S for which d(s, s') < δ.

But how many points can lie in S? It's possible for all points in P to be in S! So it still takes longer than O(n) time to check all across-half pairs. Fortunately, because of a clever observation, it turns out we do not need to check all pairs in S after all.

Theorem (5.10)

If s, s' ∈ S have the property that d(s, s') < δ, then s and s' are within 15 positions of each other in the sorted list Sᵧ.

Proof: Consider the subset Z of the plane consisting of all points within distance δ of L. Partition Z into boxes: squares with horizontal and vertical sides of length δ/2. One row of Z will consist of four boxes whose horizontal sides have the same y-coordinates.

Question: How many points can lie in the same box? Suppose there are two points lying in the same box. What is the maximum possible distance between these two points? Note: The maximum possible distance occurs when the points are on opposite corner. By the Pythagorean theorem, this distance is δ/√2. (ก็ยังน้อยกว่า δ ธรรมดา)

• ไม่ต้อง Compare หมดทุกอัน เอาแค่อีกฝั่งก็พอ เพื่อหา cross pair อะไรงี้

But each box is completely on the same side of L. That is, the two points in the same box are on the same side of L. The two points in the same box are within distance δ/√2 < δ. But this contradicts the definition of δ as the minimum distance between any pair of points in Q or R. Therefore, each box contains at most one point in S.

Now, suppose s, s' ∈ S satisfying d(s, s') < δ and that they are at least 16 positions apart in Sᵧ. Assume without loss of generality that s has the smaller y-coordinate. Since there can be at most one point per box, there are at least three rows of Z lying between s and s' (See the next slide). Each row is δ/2 high. So apart by at least three rows means the distance between s and s' is at least 3δ/2, which is greater than δ. So this is a contradiction.

Closest-Pair Algorithm

Closest-Pair(P)
    Construct Pₓ and Pᵧ (O(n log n) time)
    (p*₀, p*₁) = Closest-Pair-Rec(Pₓ, Pᵧ)

Closest-Pair-Rec(Pₓ, Pᵧ)
    If |P| ≤ 3 then
        Find the closest pair by measuring all pairwise distances
    EndIf
    Construct Qₓ, Qᵧ, Rₓ, Rᵧ (O(n) time)
    (q*₀, q*₁) = Closest-Pair-Rec(Qₓ, Qᵧ)
    (r*₀, r*₁) = Closest-Pair-Rec(Rₓ, Rᵧ)
    δ = min{d(q*₀, q*₁), d(r*₀, r*₁)}
    x* = the maximum x-coordinate of the points in the set Q
    L = {(x, y) : x = x*}
    S = points in P within distance δ of L
    Construct Sᵧ (O(n) time)
    For each point s ∈ Sᵧ, compute the distance from s to each of the
    next 15 points in Sᵧ
    Let s, s' be the pair achieving the minimum of these distances (O(n) time)
    If d(s, s') < δ then
        Return (s, s')
    Else if d(q*₀, q*₁) < d(r*₀, r*₁) then
        Return (q*₀, q*₁)
    Else
        Return (r*₀, r*₁)
    EndIf

Theorem (5.11)

The algorithm correctly outputs a closest pair of points in P.

Theorem (5.12)

The running time of the algorithm is $O(n \log n)$.

Proof: Because the running time is $T(n) = 2T(n/2) + cn$ so it follows from Theorem (5.2).

Multiplying Two (Large) Integers

The Problem: Multiply two given integers x and y that are too large to use machine instructions on.

Recall long multiplication:

  2 6
× 1 3
  7 8
2 6
3 3 8

That is, $26×13 = (2×1)×10^2 +(2×3)×10+(6×1)×10+(6×3)×10^0 = 338.$

In other words, we multiply each digit of x and y separately, place the results in correct positions, and add them up.

We can do the same thing in binary:

  1 1
× 1 0
  0 0
1 1
1 1 0

That is,

x = x_1 · 2^{n/2} + x_0

y = y_1 · 2^{n/2} + y_0