Chapter 5

Algorithm 5.10 computes the \(n\) th power of a positive real number \(x,\) where \(n \geq 0 .\) Use it to answer Exercises \(18-24\) (EQUATION CAN'T COPY) Let \(a_{n}\) denote the number of multiplications (lines \(7-10\) ) required by the algorithm to compute \(x^{n} .\) Compute each. $$a_{5}$$

Using generating functions, solve each LHRRWCC. $$a_{n}=4 a_{n-1}-4 a_{n-2}, a_{0}=3, a_{1}=10$$

Using generating functions, solve each LHRRWCC. $$a_{n}=6 a_{n-1}-9 a_{n-2}, a_{0}=2, a_{1}=3$$

Algorithm 5.10 computes the \(n\)th power of a positive real number \(x,\) where \(n \geq 0 .\) Use it to answer Exercises 18-24 . Algorithm exponentiation(x,n) (* This algorithm computes the nth power of \(x\) using recursion and returns the value in the variable answer.*) 0\. Begin (* algorithm *) 1\. if \(n=0\) then 2\. answer \(\leftarrow 1\) 3\. else 1 if \(n=1\) then 4\. answer \(\leftarrow x\) 5\. else 6\. begin (* else *) 7\. value \(\leftarrow\) exponentiation \((x,\lfloor n / 2\rfloor)\) 8\. answer \(\leftarrow\) value \(\cdot\) value 9\. If \(n\) is odd then 10\. answer \(\leftarrow\) answer \(\cdot\) \(x\) 11\. endelse 12\. End (* algorithm *) Find the recurrence relation satisfied by \(a_{n}.\)

Solve each LHRRWCC. $$a_{n}=13 a_{n-2}-36 a_{n-4}, a_{0}=7, a_{1}=-6, a_{2}=38, a_{3}=-84$$

Using induction, prove that each is a solution to the corresponding recurrence relation, where \(c\) is a constant and \(f(n)\) a function of \(n\). $$-a_{n}=c^{n} a_{0}+\frac{c^{n}-1}{c-1}, a_{n}=c a_{n-1}+1 \text { (assume } c \neq 1)$$

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. Compute the product of the numbers from right to left.

Using generating functions, solve each LHRRWCC. $$a_{n}=3 a_{n-1}+4 a_{n-2}-12 a_{n-3}, a_{0}=3, a_{1}=-7, a_{2}=7$$

Algorithm 5.10 computes the \(n\)th power of a positive real number \(x,\) where \(n \geq 0 .\) Use it to answer Exercises 18-24 . Algorithm exponentiation(x,n) (* This algorithm computes the nth power of \(x\) using recursion and returns the value in the variable answer.*) 0\. Begin (* algorithm *) 1\. if \(n=0\) then 2\. answer \(\leftarrow 1\) 3\. else 1 if \(n=1\) then 4\. answer \(\leftarrow x\) 5\. else 6\. begin (* else *) 7\. value \(\leftarrow\) exponentiation \((x,\lfloor n / 2\rfloor)\) 8\. answer \(\leftarrow\) value \(\cdot\) value 9\. If \(n\) is odd then 10\. answer \(\leftarrow\) answer \(\cdot\) \(x\) 11\. endelse 12\. End (* algorithm *) Solve the recurrence relation in Exercise \(22,\) where \(n=2^{k}.\)

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 in Exercises \(19-31 .\) Find the maximum of the numbers in the list.

Solve each LHRRWCC. $$\begin{array}{l}{a_{n}=9 a_{n-1}-30 a_{n-2}+44 a_{n-3}-24 a_{n-4}, a_{0}=5, a_{1}=12, a_{2}=38}{a_{3}=126}\end{array}$$

Define each recursively, where \(n \geq 0\) The number \(S_{n}\) of subsets of a set with \(n\) elements.

Using induction, prove that each is a solution to the corresponding recurrence relation, where \(c\) is a constant and \(f(n)\) a function of \(n\). $$a_{n}=c^{n} a_{0}+\sum_{i=1}^{n} c^{n-i} f(i), a_{n}=c a_{n-1}+f(n)$$

Estimate the number \(a_{n}\) of times the statement, \(x \leftarrow x+1,\) is executed by each nested for loop. $$\begin{aligned} \text { for } i &=1 \text { to } \mathrm{n} \text { do } \\ \text { for } & \mathrm{j}=1 \text { to }\lfloor i / 2\rfloor \mathrm{do} \\ & \mathrm{x} \leftarrow \mathrm{x}+1 \end{aligned}$$

Solve each LHRRWCC. $$\begin{aligned} &a_{n}=9 a_{n-1}-30 a_{n-2}+44 a_{n-3}-24 a_{n-4}, a_{0}=5, a_{1}=12, a_{2}=38\\\ &a_{3}=126 \end{aligned}$$

Using generating functions, solve each LHRRWCC. $$a_{n}=8 a_{n-1}-21 a_{n-2}+18 a_{n-3}, a_{0}=0, a_{1}=2, a_{2}=13$$

Algorithm 5.10 computes the \(n\)th power of a positive real number \(x,\) where \(n \geq 0 .\) Use it to answer Exercises 18-24 . Algorithm exponentiation(x,n) (* This algorithm computes the nth power of \(x\) using recursion and returns the value in the variable answer.*) 0\. Begin (* algorithm *) 1\. if \(n=0\) then 2\. answer \(\leftarrow 1\) 3\. else 1 if \(n=1\) then 4\. answer \(\leftarrow x\) 5\. else 6\. begin (* else *) 7\. value \(\leftarrow\) exponentiation \((x,\lfloor n / 2\rfloor)\) 8\. answer \(\leftarrow\) value \(\cdot\) value 9\. If \(n\) is odd then 10\. answer \(\leftarrow\) answer \(\cdot\) \(x\) 11\. endelse 12\. End (* algorithm *) Establish the correctness of Algorithm 5.10 .

Solve each LHRRWCC. $$\begin{array}{l}{a_{n}=8 a_{n-1}-24 a_{n-2}+32 a_{n-3}-16 a_{n-4}, a_{0}=1, a_{1}=4, a_{2}=44} {a_{3}=272}\end{array}$$

Define each recursively, where \(n \geq 0\) The \(n\) th term \(a_{n}\) of an arithmetic sequence with first term \(a\) and common difference \(d\)

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. Find the minimum of the numbers in the list.

Estimate the number \(a_{n}\) of times the statement, \(x \leftarrow x+1,\) is executed by each nested for loop. $$\begin{array}{l} \text { for } i=1 \text { to } n \text { do } \\ \text { for } j=1 \text { to }\lceil i / 2\rceil \text { do } \\ \qquad x \leftarrow x+1 \end{array}$$

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed by the following loops. for \(i=1\) to \(n\) do for \(j=1\) to \(\lfloor i / 2\rfloor d o\) \(x \leftarrow x+1\) Define \(a_{n}\) recursively.

Solve each LHRRWCC. $$\begin{aligned} &a_{n}=8 a_{n-1}-24 a_{n-2}+32 a_{n-3}-16 a_{n-4}, a_{0}=1, a_{1}=4, a_{2}=44\\\ &a_{3}=272 \end{aligned}$$

Algorithm 5.10 computes the \(n\) th power of a positive real number \(x,\) where \(n \geq 0 .\) Use it to answer Exercises \(18-24\) (EQUATION CAN'T COPY) Let \(a_{n}\) denote the number of multiplications (lines \(7-10\) ) required by the algorithm to compute \(x^{n} .\) Compute each. Establish the correctness of Algorithm \(5.10 .\)

Show that $$a_{n}=\left\\{\begin{array}{ll}{0} & {\text { if } n=1} \\ {a_{n-1}+n / 2} & {\text { if } n>1 \text { and even }} \\ {a_{n-1}+(n-1) / 2} & {\text { if } n>1 \text { and odd }}\end{array}\right.$$

Estimate the number \(a_{n}\) of times the statement, \(x \leftarrow x+1,\) is executed by each nested for loop. $$\begin{array}{l} \text { for } i=1 \text { to } n \text { do } \\ \text { for } j=1 \text { to } i \text { do } \\ \text { for } k=1 \text { to } j \text { do } \\ \text { for } 1=1 \text { to } j \text { do } \\ \qquad x \leftarrow x+1 \end{array}$$

Using generating functions, solve each LHRRWCC. $$a_{n}=7 a_{n-1}-16 a_{n-2}+12 a_{n-3}, a_{0}=0, a_{1}=5, a_{2}=19$$

The \(n\) th term \(a_{n}\) of a geometric sequence with first term \(a\) and common ratio \(r\)

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. Print the numbers in the given order \(x_{1}, x_{2}, \ldots, x_{n}\)

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed by the following loops. for \(i=1\) to \(n\) do for \(j=1\) to \(\lfloor i / 2\rfloor d o\) \(x \leftarrow x+1\) Show that \(a_{n}=\left\\{\begin{array}{ll}0 & \text { if } n=1 \\ a_{n-1}+n / 2 & \text { if } n>1 \text { and even } \\ a_{n-1}+(n-1) / 2 & \text { if } n>1 \text { and odd }\end{array}\right.\)

Using generating functions, solve each LHRRWCC. $$a_{n}=3 a_{n-1}+4 a_{n-2}-12 a_{n-3}, a_{0}=3, a_{1}=-7, a_{2}=7$$

Let \(f: X \rightarrow X\) be bijective. Define \(f^{n}\) recursively, where \(f^{2}=f \circ f\)

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. Print the numbers in the reverse order \(x_{n}, x_{n-1}, \ldots, x_{2}, x_{1}\)

Estimate the number \(a_{n}\) of times the statement, \(x \leftarrow x+1,\) is executed by each nested for loop. $$\begin{array}{c} \text { for } i=1 \text { to } n \text { do } \\ \text { for } j=1 \text { to } i \text { do } \\ \text { for } k=1 \text { to } j \text { do } \\ \text { for } 1=1 \text { to } k \text { do } \\ x \leftarrow x+1 \end{array}$$

Using generating functions, solve each LHRRWCC. $$a_{n}=6 a_{n-1}-12 a_{n-2}+8 a_{n-3}, a_{0}=0, a_{1}=2, a_{2}=-2$$

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)$$

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. (Linear search) Search the list for a specific item (key). Return the location of key if the search is successful.

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed by the following for loops: for \(i=1\) to \(n\) do $$\begin{array}{l}\text { for } j=1 \text { to }\lceil i / 2\rceil \text { do } \\\x \leftarrow x+1\end{array}$$ Define \(a_{n}\) recursively.

Using generating functions, solve each LHRRWCC. $$a_{n}=13 a_{n-2}-36 a_{n-4}, a_{0}=7, a_{1}=-6, a_{2}=38, a_{3}=-84$$

Show that $$\mathrm{a}_{n}=\left\\{\begin{array}{ll}{1} & {\text { if } n=1} \\\ {a_{n-1}+n / 2} & {\text { if } n>1 \text { and even }} \\ {a_{n-1}+(n+1) / 2} & {\text { if } n>1 \text { and odd }}\end{array}\right.$$

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(98)$$

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. Determine if two lists \(X\) and \(Y\) of \(n\) items of the same type are identical.

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed by the following for loops: for \(i=1\) to \(n\) do $$\begin{array}{l}\text { for } j=1 \text { to }\lceil i / 2\rceil \text { do } \\\x \leftarrow x+1\end{array}$$ Show that \(a_{n}=\left\\{\begin{array}{ll}1 & \text { if } n=1 \\ a_{n-1}+n / 2 & \text { if } n>1 \text { and even } \\ a_{n-1}+(n+1) / 2 & \text { if } n>1 \text { and odd }\end{array}\right.\)

Let \(b_{n}\) denote the number of element-comparisons needed by the bubble sort algorithm in Algorithm 5.9 Find a big-oh estimate of \(b_{n}\)

Using generating functions, solve each LHRRWCC. $$a_{n}=-a_{n-1}+3 a_{n-2}+5 a_{n-3}+2 a_{n-4}, a_{0}=0, a_{1}=-8, a_{2}=4, a_{3}=-42$$

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(f(99))$$

Let \(a_{n}\) denote the number of times the statement \(x \leftarrow x+1\) is executed by the following for loops: for \(i=1\) to \(n\) do $$\begin{array}{l}\text { for } j=1 \text { to }\lceil i / 2\rceil \text { do } \\\x \leftarrow x+1\end{array}$$ Solve the recurrence relation satisfied by \(a_{n}\)

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\)

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 in Exercises \(19-31 .\) Evaluate Ackermann's function \(A(x, y),\) where \(x\) and \(y\) are nonnegative integers. See Exercises 5.1 for a definition of \(A(x, y) .\)

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(f(91))$$