Chapter 5

Let \(b_{n}\) denote the number of element-comparisons needed by the bubble sort algorithm in Algorithm 5.9 Let \(a_{n}\) denote the number of additions needed to compute the \(n\) th Fibonacci number \(F_{n},\) using Algorithm \(5.4 .\) Prove that a_{n}=\sum_{i=1}^{n-2} F_{i} \(n \geq 3\)

Find the general form of a particular solution of the LNHRRWCCs \(a_{n}=4 a_{n-1}-4 a_{n-2}+f(n)\) corresponding to each function \(f(n)\). $$f(n)=3 \cdot 2^{n}$$

The 91 -function \(f,\) invented by John McCarthy, is defined recursively on \(\mathbf{W}\) as follows. $$f(x)=\left\\{\begin{array}{ll}{x-10} & {\text { if } x > 100} \\\ {f(f(x+11))} & {\text { if } 0 \leq x \leq 100}\end{array}\right.$$ Compute each $$ f(99)=91 $$

Let \(X=\left[x_{1}, x_{2}, \ldots, x_{n}\right]\) and \(Y=\left[y_{1}, y_{2}, \ldots, y_{n}\right]\) be two lists of numbers. Write a recursive algorithm to accomplish the tasks. Sort the list \(X\) using bubble sort.

Solve each recurrence relation. $$\begin{aligned} &c_{0}=1\\\ &c_{n}=c_{n-1}+b, n \geq 1 \end{aligned}$$

Find the general form of a particular solution of the LNHRRWCCs \(a_{n}=4 a_{n-1}-4 a_{n-2}+f(n)\) corresponding to each function \(f(n)\). $$f(n)=n 2^{n}$$

Let \(X=\left[x_{1}, x_{2}, \ldots, x_{n}\right]\) and \(Y=\left[y_{1}, y_{2}, \ldots, y_{n}\right]\) be two lists of numbers. Write a recursive algorithm to accomplish the tasks. Use the recursive bubble sort algorithm to sort the list 13,5,2,8,3.

Solve each recurrence relation. $$\begin{aligned} &\cdot a_{2}=0\\\ &a_{n}=a_{n-1}+b, n \geq 3 \end{aligned}$$

Find the general form of a particular solution of the LNHRRWCCs \(a_{n}=4 a_{n-1}-4 a_{n-2}+f(n)\) corresponding to each function \(f(n)\). $$f(n)=23 n^{2} 2^{n}$$

Solve each recurrence relation. $$ \begin{array}{l}{c_{1}=0} \\ {c_{n}=c_{n-1}+b n, n \geq 2}\end{array} $$

Use quicksort to sort the list \(7,8,13,11,5,6,4\)

The 91 -function \(f,\) invented by John McCarthy, is defined recursively on \(\mathbf{W}\) as follows. $$f(x)=\left\\{\begin{array}{ll}{x-10} & {\text { if } x > 100} \\\ {f(f(x+11))} & {\text { if } 0 \leq x \leq 100}\end{array}\right.$$ Compute each $$ f(x)=91 \text { for } 0 \leq x < 90 $$

Quicksort, invented in 1962 by \(\mathrm{C}\). Anthony \(\mathrm{R}\). Hoare of Oxford University, is an extremely efficient technique for sorting a large list \(X\) of \(n\) items \(x_{1}, x_{2}, \ldots, x_{n} .\) It is based on the fact that it is easier to sort two small lists than one large list. Choose the first element \(x_{1}\) as the pivot. To place the pivot in its final resting place, compare it to each element in the list. Move the elements less than \(x_{1}\) to the front of the list and those greater than \(x_{1}\) to the rear. Now place pivot in its final position. Partition the list \(X\) into two sublists such that the elements in the first sublist are less than \(x_{1}\) and the elements in the second sublist are greater than \(x_{1}\). Continue this procedure recursively with the two sublists. Use quicksort to sort the list 7,8,13,11,5,6,4

Solve each recurrence relation. $$\begin{array}{l} c_{1}=0 \\ c_{n}=c_{n-1}+b n, n \geq 2 \end{array}$$

Find the general form of a particular solution of the LNHRRWCCs \(a_{n}=4 a_{n-1}-4 a_{n-2}+f(n)\) corresponding to each function \(f(n)\). $$\left(17 n^{3}-1\right) 2^{n}$$

Solve each recurrence relation. $$ \begin{array}{l}{c_{1}=a} \\ {c_{n}=c_{n-1}+b n^{3}, n \geq 2}\end{array} $$

Use quicksort to write a recursive algorithm to sort a list \(X\) of \(n\) elements.

Quicksort, invented in 1962 by \(\mathrm{C}\). Anthony \(\mathrm{R}\). Hoare of Oxford University, is an extremely efficient technique for sorting a large list \(X\) of \(n\) items \(x_{1}, x_{2}, \ldots, x_{n} .\) It is based on the fact that it is easier to sort two small lists than one large list. Choose the first element \(x_{1}\) as the pivot. To place the pivot in its final resting place, compare it to each element in the list. Move the elements less than \(x_{1}\) to the front of the list and those greater than \(x_{1}\) to the rear. Now place pivot in its final position. Partition the list \(X\) into two sublists such that the elements in the first sublist are less than \(x_{1}\) and the elements in the second sublist are greater than \(x_{1}\). Continue this procedure recursively with the two sublists. Use quicksort to write a recursive algorithm to sort a list \(X\) of \(n\) elements.

Solve each recurrence relation. $$\begin{aligned} &c_{1}=a\\\ &c_{n}=c_{n-1}+b n^{3}, n \geq 2 \end{aligned}$$

The number of operations \(f(n)\) required by an algorithm is given by \(f(n)=f(n-1)+(n-1)+(n-2),\) where \(f(1)=1\) Find an explicit formula for \(f(n)\)

The number of operations \(f(n)\) required by an algorithm is given by \(f(n)=f(n-1)+(n-1)+(n-2),\) where \(f(1)=1\) Show that \(f(n)=\mathbf{O}\left(n^{2}\right)\)

The sequence defined by \(a_{n+1}=\frac{1}{2}\left(a_{n}+\frac{N}{a_{n}}\right)\) can be used to approximate \(\sqrt{N}\) to any desired degree of accuracy, where \(a_{1}\) is an estimate of \(\sqrt{N}\). Use this fact to compute \(\sqrt{19}\) correct to six decimal places. Use \(a_{1}=4\)

Let \(F_{n}\) denote the \(n\) th Fibonacci number. Compute \(\frac{F_{n+1}}{F_{n}}\) correct to eight decimal places for \(1 \leq n \leq 10 .\) Compare each value to \((1+\sqrt{5}) / 2\) correct to eight decimal places.

Let \(f(n)\) denote the number of bits in the binary representation of a positive integer \(n\). Show that \(f(n)=\mathbf{O}(\lg n)\)

Let \(t_{n}\) denote the \(n\) th triangular number. Define \(t_{n}\) recursively.

Let \(t_{n}\) denote the \(n\) th triangular number. Define \(t_{n}\) recursively.

(For those familiar with the concept of limits) Use Exercise 37 to predict \(\lim _{n \rightarrow \infty} \frac{F_{n+1}}{F_{n}}\)

Let \(t_{n}\) denote the \(n\) th triangular number. Find an explicit formula for \(t_{n}.\)

Prove each, where \(F_{n}\) is the \(n\) th Fibonacci number, \(L_{n}\) the \(n\) th Lucas number, and \(\alpha=(1+\sqrt{5}) / 2,\) the golden ratio. $$F_{n}=2 F_{n-2}+F_{n-3}, n \geq 4$$

Let \(t_{n}\) denote the \(n\) th triangular number. Find an explicit formula for \(t_{n}\).

Let \(x \in \mathbb{R}^{+}\) and \(n \in \mathbb{N} .\) The technique of successive squaring can be applied to compute \(x^{n}\) faster than multiplying \(x\) by itself \(n-1\) times. For example, to find \(x^{43},\) first evaluate \(x^{2}, x^{4}, x^{8}, x^{16},\) and \(x^{32} ;\) then multiply \(x^{32}, x^{8}, x^{2},\) and \(x^{1}: x^{43}=x^{32} \cdot x^{8} \cdot x^{2} \cdot x^{1} .\) This process takes only \(5+3=8\) multiplications instead of the conventional method's 42\. The powers of \(x\) used in computing \(x^{n}\) are the place values of the bits in the binary representation of \(n ;\) in fact, the number of powers of \(x\) used equals the number of nonzero bits in the binary representation of \(n .\) Let \(f(n)\) denote the number of multiplications needed to compute \(x^{n}\) by successive squaring. Show that \(f(n)=\mathbf{O}(\lg n)\)

Let \(A=\left(a_{j}\right)\) and \(B=\left(b_{i j}\right)\) be two \(n \times n\) matrices. Let \(f_{n}\) denote the number of computations (additions and multiplications) to compute their product \(C=\left(c_{i j}\right),\) where \(c_{i j}=\sum_{k=1}^{n} a_{k} b_{k j}\) Evaluate \(f_{n}\)

Let \(t_{n}\) denote the \(n\) th triangular number. Prove that \(8 t_{n}+1\) is a perfect square.

Prove each, where \(F_{n}\) is the \(n\) th Fibonacci number, \(L_{n}\) the \(n\) th Lucas number, and \(\alpha=(1+\sqrt{5}) / 2,\) the golden ratio. $$F_{n}^{2}-F_{n-1} F_{n+1}=(-1)^{n-1}, n \geq 2$$

Let \(t_{n}\) denote the \(n\) th triangular number. Prove that \(8 t_{n}+1\) is a perfect square.

Let \(A=\left(a_{i j}\right)\) and \(B=\left(b_{i j}\right)\) be two \(n \times n\) matrices. Let \(f_{n}\) denote the number of computations (additions and multiplications) to compute their product $$C=\left(c_{i j}\right), \text { where } c_{i j}=\sum_{k=1}^{n} a_{i k} b_{k j}$$ Evaluate \(f_{n}\)

Let \(r_{n}\) and \(s_{n}\) be two solutions of the recurrence relation \((5.8) .\) Prove that \(a_{n}=r_{n}+s_{n}\) is also a solution.

Let \(A=\left(a_{j}\right)\) and \(B=\left(b_{i j}\right)\) be two \(n \times n\) matrices. Let \(f_{n}\) denote the number of computations (additions and multiplications) to compute their product \(C=\left(c_{i j}\right),\) where \(c_{i j}=\sum_{k=1}^{n} a_{k} b_{k j}\) Estimate \(f_{n}\)

Prove each, where \(F_{n}\) is the \(n\) th Fibonacci number, \(L_{n}\) the \(n\) th Lucas number, and \(\alpha=(1+\sqrt{5}) / 2,\) the golden ratio. \(F_{5 n}\) is divisible by \(5, n \geq 1\)

Let \(A=\left(a_{i j}\right)\) and \(B=\left(b_{i j}\right)\) be two \(n \times n\) matrices. Let \(f_{n}\) denote the number of computations (additions and multiplications) to compute their product $$C=\left(c_{i j}\right), \text { where } c_{i j}=\sum_{k=1}^{n} a_{i k} b_{k j}$$ Estimate \(f_{n}\)

Solve the recurrence relation \(C_{n}=2 C_{n / 2}+1,\) where \(C_{1}=a\) and \(n\) is a power of 2

Prove each, where \(F_{n}\) is the \(n\) th Fibonacci number, \(L_{n}\) the \(n\) th Lucas number, and \(\alpha=(1+\sqrt{5}) / 2,\) the golden ratio. $$F_{n}<\alpha^{n-1}, n \geq 3$$

Let \(\alpha\) be a characteristic root of the LHRRWCC \(a_{n}=a a_{n-1}+b a_{n-2}+\) \(c a_{n-3}\) with degree of multiplicity three. Show that \(\alpha^{n}, n \alpha^{n}, n^{2} \alpha^{n}\) are solutions of LHRRWCC.

Prove each, where \(F_{n}\) is the \(n\) th Fibonacci number, \(L_{n}\) the \(n\) th Lucas number, and \(\alpha=(1+\sqrt{5}) / 2,\) the golden ratio. $$F_{n} \leq 2^{n}, n \geq 1$$

Let \(c_{n}\) denote the maximum number of comparisons needed to search for a key in an ordered list \(X\) of \(n\) elements, using the recursive binary search algorithm. Prove that \(c_{n}=1+\lfloor\lg n\rfloor,\) for every \(n \geq 1\)

Let \(A=\left[\begin{array}{ll}{1} & {1} \\ {1} & {0}\end{array}\right] .\) Then \(A^{n}=\left[\begin{array}{cc}{F_{n+1}} & {F_{n}} \\ {F_{n}} & {F_{n-1}}\end{array}\right], n \geq 1 .\) Assume \(F_{0}=0\)

$$\text { Let } A=\left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] . \text { Then } A^{n}=\left[\begin{array}{cc} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{array}\right], n \geq 1 . \text { Assume } F_{0}=0$$

Let \(a, b, k \in \mathbb{N}, b \geq 2,\) and \(n=b^{k} .\) Consider the function \(f\) defined by \(f(n)=a f(n / b)+g(n) .\) Show that \(f(n)=a^{k} f(1)+\sum_{i=0}^{k-1} a^{i} g\left(n / b^{i}\right)\)

Using Exercise 44, deduce that \(F_{n+1} F_{n-1}-F_{n}^{2}=(-1)^{n}\) .

Solve the recurrence relation \(a_{n}=2 a_{n / 2}+n,\) where \(a_{1}=0\) and \(n=2^{k}\)