Chapter 2: Divide-and-conquer algorithms

Question: Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers $\mathit{10011011}\mathit{}\mathbf{and}\mathbf{}\mathit{10111010}$ and .

You are given two sorted lists of size mandn. Give an $\mathit{O}\mathbf{(}\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{m}\mathbf{+}\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{n}\mathbf{)}$time algorithm for computing the $\mathbf{k}$ th smallest element in the union of the two lists.

An array $\mathbf{A}[\mathbf{1}...\mathbf{n}]$ is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form “ is $\mathbf{A}\left[\mathbf{i}\right]>\mathbf{A}\left[\mathbf{j}\right]$ ?”. (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is ..?” in constant time.

(a) Show how to solve this problem in $\mathbf{O}(\mathbf{nlog}\mathbf{n})$ time. (Hint: Split the array $\mathbf{A}$ into two arrays ${\mathbf{A}}_{\mathbf{1}}$and ${\mathit{A}}_{\mathbf{2}}$of half the size. Does knowing the majority elements of ${\mathbf{A}}_{\mathbf{1}}$and ${\mathbf{A}}_{\mathbf{2}}$help you figure out the majority element of ${\mathbf{A}}_{}$? If so, you can use a divide-and-conquer approach.)

(b) Can you give a linear-time algorithm? (Hint: Here’s another divide-and-conquer approach:• Pair up the elements of ${\mathbf{A}}_{}$ arbitrarily, to get $\mathbf{n}\mathbf{/}\mathbf{2}$ pairs• Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them . Show that after this procedure there are at most $\mathit{n}\mathbf{/}\mathbf{2}$ elements left, and that they have a majority element if ${\mathbf{A}}_{}$ does.)

An array A [1...n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, a A₂ nd so there can be no comparisons of the form “is $\mathit{A}\mathbf{\left[}\mathit{i}\mathbf{\right]}\mathbf{>}\mathit{A}\mathbf{\left[}\mathit{j}\mathbf{\right]}$?”. (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is ..?” in constant time.

(a) Show how to solve this problem in O(nlog n) time. (Hint: Split the array A into two arrays A₁ and of half the size. Does knowing the majority elements of A₁ and A₂ help you figure out the majority element of A? If so, you can use a divide-and-conquer approach.)

(b) Can you give a linear-time algorithm? (Hint: Here’s another divide-and-conquer approach:

• Pair up the elements of A arbitrarily, to get n/2 pairs
• Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them
  Show that after this procedure there are at most n/2 elements left, and that they have a majority element if A does.)

Question: On page 66 there is a high-level description of the quicksort algorithm.

(a) Write down the pseudocode for quicksort.

(b) Show that its worst - case running time on an array of size n is $\mathbf{\Theta }{\left(n\right)}^{\mathbf{2}}$.

(c) Show that its expected running time satisfies the recurrence relation.

$\mathit{T}\left(n\right)\mathbf{\le }\mathit{O}\left(n\right)\mathbf{+}\frac{\mathbf{1}}{\mathbf{n}}\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}\mathbf{-}\mathbf{1}}\left(T\left(i\right)+T\left(n-i\right)\right)$

Then, show that the solution to this recurrence is $\mathit{O}\mathbf{(}\mathit{n}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$.

In Section 2.1 we described an algorithm that multiplies two n-bit binary integers x and y in time ${\mathit{n}}^{\mathbf{a}}$, where $\mathbf{a}\mathbf{=}{\mathbf{log}}_{\mathbf{2}}\mathbf{3}$. Call this procedure fast multiply (x,y).

function pwr2bin(n)

if n = 1: return${\mathbf{1010}}_{\mathbf{2}}$

else:

z= ???

return fastmultiply(z,z)

Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.

function dec2bin(x)

if n=1: return binary [ x ]

else:

split x into two decimal numbers ${\mathit{x}}_{\mathbf{t}}\mathbf{,}\mathbf{}\mathbf{}{\mathit{x}}_{\mathbf{R}}$with n/2 digits each

return ???

Here binary [.] is a vector that contains the binary representation of all one-digit integers. That is, binary role="math" localid="1659333641173" $\left[0\right]\mathbf{=}{\mathbf{0}}_{\mathbf{2}}$, binary $\mathbf{\left[}\mathbf{1}\mathbf{\right]}\mathbf{=}{\mathbf{1}}_{\mathbf{2}}$, up to binary $\mathbf{\left[}\mathbf{9}\mathbf{\right]}\mathbf{=}{\mathbf{1001}}_{\mathbf{2}}$. Assume that a lookup in binary takes 0(1) time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it.

Professor F. Lake tells his class that it is asymptotically faster to square an -bit integer than to multiply two n-bit integers. Should they believe him?

Thesquare of a matrix A is its product with itself, AA.

(a) Show that five multiplications are sufficient to compute the square of a 2 x 2 matrix.

(b) What is wrong with the following algorithm for computing the square of an n x n matrix?

“Use a divide-and-conquer approach as in Strassen’s algorithm, except that instead of getting 7 subproblems of size $\frac{\mathbf{n}}{\mathbf{2}}$, we now get 5 subproblems of size $\frac{\mathbf{n}}{\mathbf{2}}$ thanks to part (a). Using the same analysis as in Strassen’s algorithm, we can conclude that the algorithm runs in time O (n^c) .”

(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(n^c), then any two n x n matrices can be multiplied in time O(n^c) .

1. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n² ) .
2. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B,L as follows:
   $A=\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]andB=\left[\begin{array}{cc}0& Y\\ 0& 0\end{array}\right]$
   What is AB + BA, in terms of X and Y?
3. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n² ). Conclude that matrix multiplication takes time O(n^c ).

The Hadamard matrices${\mathit{H}}_{\mathbf{0}}\mathbf{,}{\mathit{H}}_{\mathbf{1}}\mathbf{,}{\mathit{H}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }$ are defined as follows:

• • ${\mathit{H}}_{\mathbf{0}}$ is the $\mathbf{1}\mathbf{\times }\mathbf{1}\mathbf{}\mathit{m}\mathit{a}\mathit{t}\mathit{r}\mathit{i}\mathit{x}\mathbf{}\mathbf{\left[}\mathbf{1}\mathbf{\right]}\mathbf{}$
• For $\mathit{k}\mathbf{>}\mathbf{0}\mathbf{,}\mathbf{}{\mathit{H}}_{\mathbf{k}}\mathit{i}\mathit{s}\mathbf{}\mathit{t}\mathit{h}\mathit{e}\mathbf{}{\mathbf{2}}^{\mathbf{k}}\mathbf{\times }{\mathbf{2}}^{\mathbf{k}}$ matrix

localid="1658916810283" ${\mathit{H}}_{\mathbf{k}}\mathbf{=}\mathbf{\left[}\frac{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}\mathbf{-}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}\mathbf{\right]}$

Show that if $\mathit{\upsilon }$ is a column vector of lengthlocalid="1658916598888" $\mathit{n}\mathbf{=}{\mathbf{2}}^{\mathbf{k}}$, then the matrix-vector product localid="1658916618774" ${\mathit{H}}_{\mathbf{k}}\mathit{v}$can be calculated using localid="1658916637767" $\mathit{O}\mathbf{(}\mathit{n}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathit{n}\mathbf{}\mathbf{)}\mathbf{}$ operations. Assume that all the numbers involved are small enough that basic arithmetic operations like addition and multiplication take unit time.

Suppose we want to evaluate the polynomial P(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ at point x.