91影视

In justifying our matrix multiplication algorithm (Section 2.5), we claimed the following block wise property: if X and Y are $\mathit{n}\mathbf{脳}\mathit{n}$n matrices, and

$\mathit{X}\mathbf{=}\left[\begin{array}{cc}A& B\\ C& D\\ & \end{array}\right]\mathbf{,}\mathit{Y}\mathbf{=}\left[\begin{array}{cc}E& F\\ G& H\\ & \end{array}\right]$,

where A,B,C,D,E,F,G, and H are $\mathit{n}\mathbf{/}\mathbf{2}\mathbf{脳}\mathit{n}\mathbf{/}\mathbf{2}$ sub-matrices, then the product XY can be expressed in terms of these blocks:

$\mathit{X}\mathit{Y}\mathbf{=}\left[\begin{array}{cc}A& B\\ C& D\\ & \end{array}\right]\left[\begin{array}{cc}E& F\\ G& H\\ & \end{array}\right]\mathbf{=}\left[\begin{array}{cc}AE+BG& AF+BH\\ CE+DG& CF+DH\\ & \end{array}\right]$

Prove this property.

A binary tree is full if all of its vertices have either zero or two children. Let ${\mathit{B}}_{\mathbf{n}}$denote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of ${\mathit{B}}_{\mathbf{3}}$, ${\mathit{B}}_{\mathbf{5}}$, and ${\mathit{B}}_{\mathbf{7}}$. Why have we left out even numbers of vertices, like ${\mathit{B}}_{\mathbf{4}}$?

(b) For general n, derive a recurrence relation for ${\mathit{B}}_{\mathbf{n}}$.

(c) Show by induction that ${\mathit{B}}_{\mathbf{n}}$is $\mathit{惟}\left(2^n\right)$.

You are given an array of $\mathbf{n}$elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time $\mathbf{O}\mathbf{(}\mathbf{n}\mathbf{}\mathbf{log}\mathbf{}\mathbf{n}\mathbf{)}$ .

In our median-finding algorithm (Section 2.4), a basic primitive is the split operation, which takes as input an array S and a value V and then divides S into three sets: the elements less than V , the elements equal to V , and the elements greater than V . Show how to implement this split operation in place, that is, without allocating new memory.

Question: You are given an infinite array $\mathit{A}[路]$in which the first n cells contain integers in sorted order and the rest of the cells are filled with $\mathbf{鈭�}$. You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has infinite length, assume instead that it is of length n, but that you don鈥檛 know this length, and that the implementation of the array data type in your programming language returns the error message $\mathbf{鈭�}$whenever elements $\mathit{A}\mathbf{\left[}\mathit{i}\mathbf{\right]}\mathbf{}\mathbf{}\mathbf{with}\mathbf{}\mathbf{}\mathit{i}\mathbf{>}\mathit{n}$ are accessed.)

Given a sorted array of distinct integers$\mathbf{A}\mathbf{[}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{n}\mathbf{]}$ , you want to find out whether there is an index$\mathit{i}$ for which $\mathbf{A}\mathbf{\left[}\mathbf{i}\mathbf{\right]}\mathbf{=}\mathbf{i}$. Give a divide-and-conquer algorithm that runs in time $\mathbf{O}\mathbf{\left(}\mathbf{log}\mathbf{n}\mathbf{\right)}$.

A $\mathit{k}\mathbf{鈭�}$way merge operation. Suppose you have $\mathit{k}$sorted arrays, each with $\mathit{n}$elements, and you want to combine them into a single sorted array of$\mathit{k}\mathit{n}$ elements.

(a)Here鈥檚 one strategy: Using the merge procedure from Section 2.3, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of $\mathit{k}$and $\mathit{n}$?

(b) Give a more efficient solution to this problem, using divide-and-conquer.

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 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 鈥渋s $\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: 鈥渋s ..?鈥� 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鈥檚 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.)