Divide and Conquer Algorithms

A divide-and-conquer algorithm

• Derives the output directly, for small instances
• Divides large instances to smaller ones, and (recursively) applies the algorithm on the smaller instances.
• Combines the solutions for the subinstances, to produce a solution for the original instance.

18.1 Merge Sort

Sets of cardinality greater than one are decomposed into two equal subsets, the algorithm is recursively invoked on the subsets, and the returned ordered subsets are merged to provide a sorted variant of the original set.
The time complexity of the algorithm satisfies the recurrence equation

whose solution is T(n) = O(n log n).

18.2 Quick Sort

Sets of cardinality greater than one are partitioned into two subsets, and then the algorithm is recursively invoked on the subsets. The partitioning uses a key from the set as a pivot. Values smaller than the pivot are sent to one subset, and values greater than the pivot are sent to the other subset.
For randomly chosen pivots, the expected running time of the algorithm satisfies the recurrence equation

whose solution is T(n) = O(n log n). The worst case time complexity of the algorithm is O(n2).

18.3 Tiling with L-Grouped Tiles

The problem is to tile a board of size 2k × 2k with one single tile and 22k - 1 L-shaped groups of 3 tiles. A divide-and-conquer approach can recursively divide the board into four, and place a L-grouped set of 3 tiles in the center at the parts that have no extra tile.

18.4 Closest Pair

Given a set of n points (xi, yi) the problem asks what is the distance between the two closest points. A brute force approach in which the distances for all the pairs are measured takes O(n2) time.
A divide-and-conquer algorithm can sort the points along the x-axis, partition the region into two parts Rleft and Rright having equal number of points, recursively apply the algorithm on the sub-regions, and then derive the minimal distance in the original region.
The closest pair resides in the left region, the right region, or across the borderline. The last case needs to deal only with points at distance

The points in the region around the boundary line are sorted along the y coordinate, and processed in that order. The processing consists of comparing each of these points with points that are ahead at most in their y coordinate. Since a window of size × 2can contain at most 6 points, at most five distances need to be evaluated for each of these points.
The sorting of the points along the x and y coordinates can be done before applying the recursive divide-and-conquer algorithm; they require O(n log n) time.
The processing of the points along the boundary line takes O(n) time. Hence, the recurrence equation for the time complexity of the algorithm:

The solution of the equation is T(n) = O(n log n).

18.5 Strassen’s Matrix Multiplication

Given: Two N by N matrices A and B.
Problem: Compute C = A × B

Brute Force

for i:= 1 to N do 

  for j:=1 to N do 

     C[i,j] := 0; 

     for k := 1 to N do 

        C[i,j] := C[i,j] + A[i,k] * B[k,j] 

O(N3) multiplications

From

T(n) = O(nlog 7) = O(n2.81).
Best known upper bound is n2.376

18.6 Assignment #8 (due We, Nov 17)

1. Show that our greedy algorithms for the Egyptian fractions and vertex cover problems need not provide optimal answers.

An optimal vertex cover is one which uses a minimal number of vertices, and an optimal Egyptian number is one which uses a minimal number of terms.

2. Assume the greedy algorithm for the vertex cover problem uses a heap-based priority queue for selecting a node at each stage. Consider the following graph.

1. Provide an initial priority queue for the algorithm on the above graph.
2. Show all the the transformations the priority queue goes through, in response to the selection of the first node by the greedy algorithm.
3. Find the time and space complexities of the algorithm on arbitrary graphs G = {V, E}.
2. Find out what is Huffman’s compression algorithm, and explain what makes it a greedy algorithm.
3. Provide a divide-and-conquer algorithm for determining the largest and second largest values in a given unordered set of numbers. Provide a recurrence equation expressing the time complexity of the algorithm, and derive it’s solution.