Learning Materials
Features
Discover
Chapter 8: Problem 13
Find the solution to \(a_{n}=7 a_{n-2}+6 a_{n-3}\) with \(a_{0}=9\) \(a_{1}=10,\) and \(a_{2}=32 .\)
Over 30 million students worldwide already upgrade their learning with 91影视!
These are the key concepts you need to understand to accurately answer the question.
All the tools & learning materials you need for study success - in one app.
Get started for free
This exercise deals with the problem of finding the largest sum of consecutive terms of a sequence of n real numbers. When all terms are positive, the sum of all terms provides the answer, but the situation is more complicated when some terms are negative. For example, the maximum sum of consecutive terms of the sequence \(-2,3,-1,6,-7,4\) is \(3+(-1)+6=8 .\) (This exercise is based on \([\mathrm{Be} 86] .\) Recall that in Exercise 56 in Section 8.1 we developed a dynamic programming algorithm for solving this problem. Here, we first look at the brute-force algorithm for solving this problem; then we develop a divide- and-conquer algorithm for solving it. a) Use pseudocode to describe an algorithm that solves this problem by finding the sums of consecutive terms starting with the first term, the sums of consecutive terms starting with the second term, and so on, keeping track of the maximum sum found so far as the algorithm proceeds. b) Determine the computational complexity of the algorithm in part (a) in terms of the number of sums computed and the number of comparisons made. c) Devise a divide-and-conquer algorithm to solve this problem. [Hint: Assume that there are an even number of terms in the sequence and split the sequence into two halves. Explain how to handle the case when the maximum sum of consecutive terms includes terms in both halves.] d) Use the algorithm from part (c) to find the maximum sum of consecutive terms of each of the sequences: \(-2,4,-1,3,5,-6,1,2 ; 4,1,-3,7,-1,-5, \quad 3,-2 ;\) and \(-1,6,3,-4,-5,8,-1,7\) e) Find a recurrence relation for the number of sums and comparisons used by the divide-and-conquer algorithm from part (c). f ) Use the master theorem to estimate the computational complexity of the divide-and-conquer algorithm. How does it compare in terms of computational complexity with the algorithm from part (a)?
In Exercises \(29-33,\) assume that \(f\) is an increasing function satisfying the recurrence relation \(f(n)=a f(n / b)+c n^{d},\) where \(a \geq 1, b\) is an integer greater than \(1,\) and \(c\) and \(d\) are positive real numbers. These exercises supply a proof of Theorem \(2 .\) Show that if \(a \neq b^{d}\) and \(n\) is a power of \(b,\) then \(f(n)=\) \(C_{1} n^{d}+C_{2} n^{\log _{b} a}\) , where \(C_{1}=b^{d} c /\left(b^{d}-a\right)\) and \(C_{2}=\) \(f(1)+b^{d} c /\left(a-b^{d}\right)\)
Use generating functions to find an explicit formula for the Fibonacci numbers.
Exercises \(38-45\) involve the Reve's puzzle, the variation of the Tower of
Hanoi puzzle with four pegs and \(n\) disks. Before presenting these exercises,
we describe the Frame-Stewart algorithm for moving the disks from peg 1 to peg
4 so that no disk is ever on top of a smaller one. This algorithm, given the
number of disks \(n\) as input, depends on a choice of an integer \(k\) with \(1
\leq k \leq n .\) When there is only one disk, move it from peg 1 to peg 4 and
stop. For \(n>1\) , the algorithm proceeds recursively, using these three steps.
Recursively move the stack of the \(n-k\) smallest disks from peg 1 to peg \(2,\)
using all four pegs. Next move the stack of the \(k\) largest disks from peg 1
to peg \(4,\) using the three-peg algorithm from the Tower of Hanoi puzzle
without using the peg holding the \(n-k\) smallest disks. Finally, recursively
move the smallest \(n-k\) disks to peg \(4,\) using all four pegs. Frame and
Stewart showed that to produce the fewest moves using their algorithm, \(k\)
should be chosen to be the smallest integer such that \(n\) does not exceed
\(t_{k}=k(k+1) / 2,\) the \(k\) th triangular number, that is, \(t_{k-1}
(Calculus required) Let \(\left\\{C_{n}\right\\}\) be the sequence of Catalan numbers, that is, the solution to the recurrence relation \(C_{n}=\sum_{k=0}^{n-1} C_{k} C_{n-k-1}\) with \(C_{0}=C_{1}=1\) (see Example 5 in Section 8.1\()\) a) Show that if \(G(x)\) is the generating function for the sequence of Catalan numbers, then \(x G(x)^{2}-G(x)+\) \(1=0 .\) Conclude (using the initial conditions) that \(G(x)=(1-\sqrt{1-4 x}) /(2 x)\) b) Use Exercise 42 to conclude that $$ G(x)=\sum_{n=0}^{\infty} \frac{1}{n+1}\left(\begin{array}{c}{2 n} \\\ {n}\end{array}\right) x^{n} $$ so that $$ C_{n}=\frac{1}{n+1}\left(\begin{array}{c}{2 n} \\ {n}\end{array}\right) $$ c) Show that \(C_{n} \geq 2^{n-1}\) for all positive integers \(n\)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
Explanations 
Textbooks 
Flashcards 
91影视 AI 
Notes 
Study Plans 
Study Sets 
Find a degree 
Magazine