Chapter 9

Find the general solution for a first-order homogeneous recurrence relation with constant coefficients. Is the restriction that the coefficients be constant necessary?

Let \(A\) be an array with \(N\) elements for some positive integer \(N .\) SelectionSort sorts the elements of \(A\) in decreasing order by swapping the largest element in \(A[1], A[2], A[3], \ldots, A \mid S-1]\) with \(A[S]\) where \(S\) ranges from \(N\) down to \(1 .\) Find and solve a recurrence relation that describes the complexity of SelectionSort. Let comparison of two elements be the key operation. Assume that the minimum operation on a set of size \(M\) requires \(M-1\) comparisons for any \(M \in \mathbb{N}\).

For \(2 \times 2\) matrices, the complexity of matrix multiplication can be determined using the algorithm described below where the number of arithmetic operations (additions, subtractions, and multiplications) are one measure of complexity. Let \(A=\) \(\left(\begin{array}{ll}a_{11} & a_{12} \\ a_{21} & a_{22}\end{array}\right)\) and \(B=\left(\begin{array}{ll}b_{11} & b_{12} \\\ b_{21} & b_{22}\end{array}\right) .\) Calculate $$\begin{array}{l} m_{1}=\left(a_{11}+a_{22}\right)\left(b_{11}+b_{22}\right) \\ m_{5}=\left(a_{21}+a_{22}\right) b_{11} \\ m_{2}=\left(a_{11}-a_{22}\right)\left(b_{21}+b_{22}\right) \\ m_{6}=a_{11}\left(b_{12}-b_{22}\right) \\ m_{3}=\left(a_{11}-a_{21}\right)\left(b_{11}+b_{12}\right) \\ m_{7}=a_{22}\left(b_{21}-b_{11}\right) \\ m_{4}=\left(a_{11}+a_{12}\right) b_{11} \end{array}$$ $$\text { Now, let } C=\left(\begin{array}{ll}c_{11} & c_{12} \\\c_{21} & c_{22}\end{array}\right) \text { where }$$ $$\begin{aligned}c_{11} &=m_{1}+m_{2}-m_{4}+m_{7} \\\c_{12} &=m_{4}+m_{6} \\\c_{21} &=m_{5}+m_{7} \\\c_{22} &=m_{1}-m_{3}-m_{5}+m_{6}\end{aligned}$$ $$\text { (a) Use the algorithm described to find the matrix product for }$$ $$ \left(\begin{array}{ll} 3 & 5 \\ 4 & 8\end{array}\right) \quad\left(\begin{array}{ll}2 & 7 \\\5 & 9\end{array}\right)$$ (b) For matrices of size \(2^{r} \times 2^{r}\), partition them into \(2^{r-1} \times 2^{r-1}\) submatrices, and use the procedure shown for \(2 \times 2\) matrices to compute the product. Carry out this process for the following matrices: $$\left(\begin{array}{llll}3 & 5 & 2 & 5 \\\4 & 8 & 7 & 3 \\\4 & 6 & 9 & 9 \\\3 & 6 & 9 & 7\end{array}\right) \quad\left(\begin{array}{llll}2 & 7 & 3 & 5 \\\5 & 9 & 4 & 6 \\\3 & 5 & 9 & 8 \\\5 & 3 & 2 & 1\end{array}\right)$$ (c) Show that matrix multiplication using this algorithm satisfies the recurrence relation $$f_{r}=7 f_{r-1}+18 \cdot 2^{r-2} \text { for } r \geq 1$$ Solve this recurrence. How does this result compare with the classical method of multiplying matrices?

Write a procedure to solve the general \(n\) -disk Tower of Hanoi problem using the following idea: Number the disks from smallest to largest, starting at \(1 .\) Consider the towers as being in a triangular formation with the pegs numbered counterclockwise. Describe the disk moved and the direction it should be moved where \(X\) C means move the top disk on peg \(X\) in a clockwise direction to the next peg and \(X\) A means to move the top disk on peg \(X\) in a counterclockwise direction. For example, the following moves solve the problem for \(n=3\) : $$1 \mathrm{C} 2 \mathrm{~A} 1 \mathrm{C} 3 \mathrm{C} 1 \mathrm{C} 2 \mathrm{~A} 1 \mathrm{C}$$ Draw pictures of the three towers and how the disks are positioned for each of the moves indicated.