Recent questions without answers / GATE Overflow for GATE CSE

0 votes

0 answers

3151

Kenneth Rosen Edition 7 Exercise 8.2 Question 24 (Page No. 525)
Consider the nonhomogeneous linear recurrence relation $a_{n} = 2a_{n-1} + 2^{n}.$ Show that $a_{n} = n2^{n}$ is a solution of this recurrence relation. Use Theorem $5$ to find all solutions of this recurrence relation. Find the solution with $a_{0} = 2.$

Consider the nonhomogeneous linear recurrence relation $a_{n} = 2a_{n-1} + 2^{n}.$Show that $a_{n} = n2^{n}$ is a solution of this recurrence relation.Use Theorem $5$ to ...

admin

258 views

admin asked May 5, 2020

0 votes

0 answers

3152

Kenneth Rosen Edition 7 Exercise 8.2 Question 23 (Page No. 525)
Consider the nonhomogeneous linear recurrence relation $a_{n} = 3a_{n-1} + 2^{n}.$ Show that $a_{n} = -2^{n+1}$ is a solution of this recurrence relation. Use Theorem $5$ to find all solutions of this recurrence relation. Find the solution with $a_{0} = 1.$

Consider the nonhomogeneous linear recurrence relation $a_{n} = 3a_{n-1} + 2^{n}.$Show that $a_{n} = -2^{n+1}$ is a solution of this recurrence relation.Use Theorem $5$ t...

admin

256 views

admin asked May 5, 2020

0 votes

0 answers

3153

Kenneth Rosen Edition 7 Exercise 8.2 Question 17 (Page No. 525)
Prove this identity relating the Fibonacci numbers and the binomial coefficients: $f_{n+1} = C(n, 0) + C(n − 1, 1) +·\dots+ C(n − k, k),$ where $n$ is a positive integer and $k = n/2 .$ ... Show that the sequence $\{a_{n}\}$ satisfies the same recurrence relation and initial conditions satisfied by the sequence of Fibonacci numbers.]

Prove this identity relating the Fibonacci numbers and the binomial coefficients: $f_{n+1} = C(n, 0) + C(n − 1, 1) +·\dots+ C(n − k, k),$ where $n$ is a positive int...

admin

220 views

admin asked May 3, 2020

0 votes

0 answers

3154

Kenneth Rosen Edition 7 Exercise 8.2 Question 16 (Page No. 525)
Prove Theorem $3:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots - c_{k} = 0$ has $k$ distinct roots $r_{1},r_{2},\dots r_{k}.$ Then a sequence $\{a_{n}\}$ ... $n = 0,1,2,\dots,$ where $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$ are constants.

Prove Theorem $3:$Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $$r^{k}-c_{1}r^{k-1}-\dots – c_{k} = 0$$has $k$ distinct roots...

admin

229 views

admin asked May 3, 2020

0 votes

0 answers

3155

Kenneth Rosen Edition 7 Exercise 8.2 Question 11 (Page No. 525)
The Lucas numbers satisfy the recurrence relation $L_{n} = L_{n−1} + L_{n−2},$ and the initial conditions $L_{0} = 2$ and $L_{1} = 1.$ Show that $L_{n} = f_{n−1} + f_{n+1}\: \text{for}\: n = 2, 3,\dots,$ where fn is the $n^{\text{th}}$ Fibonacci number. Find an explicit formula for the Lucas numbers.

The Lucas numbers satisfy the recurrence relation $L_{n} = L_{n−1} + L_{n−2},$ and the initial conditions $L_{0} = 2$ and $L_{1} = 1.$ Show that $L_{n} = f_{n−1} + ...

admin

242 views

admin asked May 3, 2020

0 votes

0 answers

3156

Kenneth Rosen Edition 7 Exercise 8.2 Question 10 (Page No. 525)
Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ ... $n = 0,1,2,\dots,$ where $\alpha_{1}$ and $\alpha_{2}$ are constants.

Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ is ...

admin

230 views

admin asked May 3, 2020

0 votes

0 answers

3157

Kenneth Rosen Edition 7 Exercise 8.2 Question 9 (Page No. 525)
A deposit of $\$100,000$ is made to an investment fund at the beginning of a year. On the last day of each year two dividends are awarded. The first dividend is $ ... $n$ years if no money has been withdrawn?

A deposit of $\$100,000$ is made to an investment fund at the beginning of a year. On the last day of each year two dividends are awarded. The first dividend is $20\%$ of...

admin

567 views

admin asked May 3, 2020

0 votes

0 answers

3158

Kenneth Rosen Edition 7 Exercise 8.2 Question 8 (Page No. 524 - 525)
A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. Find a recurrence relation for $\{L_{n}\},$ ... if $100,000$ lobsters were caught in year $1\:\text{ and}\: 300,000$ were caught in year $2.$

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two ...

admin

343 views

admin asked May 3, 2020

0 votes

0 answers

3159

Kenneth Rosen Edition 7 Exercise 8.2 Question 7 (Page No. 524)
In how many ways can a $2 \times n$ rectangular checkerboard be tiled using $1 \times 2 \:\text{and}\: 2 \times 2$ pieces?

In how many ways can a $2 \times n$ rectangular checkerboard be tiled using $1 \times 2 \:\text{and}\: 2 \times 2$ pieces?

admin

292 views

admin asked May 3, 2020

0 votes

0 answers

3160

Kenneth Rosen Edition 7 Exercise 8.2 Question 6 (Page No. 524)
How many different messages can be transmitted in $n$ microseconds using three different signals if one signal requires $1$ microsecond for transmittal, the other two signals require $2$ microseconds each for transmittal, and a signal in a message is followed immediately by the next signal?

How many different messages can be transmitted in $n$ microseconds using three different signals if one signal requires $1$ microsecond for transmittal, the other two sig...

admin

391 views

admin asked May 3, 2020

0 votes

0 answers

3161

Kenneth Rosen Edition 7 Exercise 8.2 Question 5 (Page No. 524)
How many different messages can be transmitted in $n$ microseconds using the two signals described in question $19$ in Section $8.1?$

How many different messages can be transmitted in $n$ microseconds using the two signals described in question $19$ in Section $8.1?$

admin

282 views

admin asked May 3, 2020

0 votes

0 answers

3162

Kenneth Rosen Edition 7 Exercise 8.2 Question 4 (Page No. 524)
Solve these recurrence relations together with the initial conditions given. $a_{n} = a_{n-1}+ 6a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 3, a_{1} = 6$ $a_{n} = 7a_{n-1}− 10a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 2, a_{1} = 1$ ... $a_{n+2} = −4a_{n+1} + 5a_{n} \:\text{for}\: n \geq 0, a_{0} = 2, a_{1} = 8$

Solve these recurrence relations together with the initial conditions given.$a_{n} = a_{n-1}+ 6a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 3, a_{1} = 6$$a_{n} = 7a_{n-1}− ...

admin

384 views

admin asked May 3, 2020

0 votes

0 answers

3163

Kenneth Rosen Edition 7 Exercise 8.1 Question 57 (Page No. 512)
Dynamic programming can be used to develop an algorithm for solving the matrix-chain multiplication problem introduced in Section $3.3.$ This is the problem of determining how the product $A_{1}A_{2} \dots A_{n}$ can be computed ... algorithm from part $(D)$ has $O(n^{3})$ worst-case complexity in terms of multiplications of integers.

Dynamic programming can be used to develop an algorithm for solving the matrix-chain multiplication problem introduced in Section $3.3.$ This is the problem of determinin...

admin

250 views

admin asked May 3, 2020

0 votes

0 answers

3164

Kenneth Rosen Edition 7 Exercise 8.1 Question 56 (Page No. 512)
In this question, we will develop a dynamic programming algorithm for finding the maximum sum of consecutive terms of a sequence of real numbers. That is, given a sequence of real numbers ... worst-case complexity in terms of the number of additions and comparisons of your algorithm from part $(C)$ is linear.

In this question, we will develop a dynamic programming algorithm for finding the maximum sum of consecutive terms of a sequence of real numbers. That is, given a sequenc...

admin

352 views

admin asked May 3, 2020

0 votes

0 answers

3165

Kenneth Rosen Edition 7 Exercise 8.1 Question 55 (Page No. 512)
For each part of question $54,$ use your algorithm from question $53$ to find the optimal schedule for talks so that the total number of attendees is maximized. $20, 10, 50, 30, 15, 25, 40.$ $100, 5, 10, 20, 25, 40, 30. $ $2, 3, 8, 5, 4, 7, 10. $ $10, 8, 7, 25, 20, 30, 5.$

For each part of question $54,$ use your algorithm from question $53$ to find the optimal schedule for talks so that the total number of attendees is maximized.$20, 10, 5...

admin

184 views

admin asked May 3, 2020

0 votes

0 answers

3166

Kenneth Rosen Edition 7 Exercise 8.1 Question 54 (Page No. 512)
Use Algorithm $1$ to determine the maximum number of total attendees in the talks in Example $6$ if $w_{i},$ the number of attendees of talk $i, i = 1, 2,\dots, 7,$ is $20, 10, 50, 30, 15, 25, 40.$ $100, 5, 10, 20, 25, 40, 30. $ $2, 3, 8, 5, 4, 7, 10. $ $10, 8, 7, 25, 20, 30, 5.$

Use Algorithm $1$ to determine the maximum number of total attendees in the talks in Example $6$ if $w_{i},$ the number of attendees of talk $i, i = 1, 2,\dots, 7,$ is$20...

admin

210 views

admin asked May 3, 2020

0 votes

0 answers

3167

Kenneth Rosen Edition 7 Exercise 8.1 Question 53 (Page No. 512)
Construct the algorithm described in the text after Algorithm $1$ for determining which talks should be scheduled to maximize the total number of attendees and not just the maximum total number of attendees determined by Algorithm $1.$

Construct the algorithm described in the text after Algorithm $1$ for determining which talks should be scheduled to maximize the total number of attendees and not just t...

admin

191 views

admin asked May 3, 2020

0 votes

0 answers

3168

Kenneth Rosen Edition 7 Exercise 8.1 Question 52 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ ... The resulting equation involving the sequences and its differences is called a difference equation.

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

172 views

admin asked May 3, 2020

0 votes

0 answers

3169

Kenneth Rosen Edition 7 Exercise 8.1 Question 51 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ ... $a_{n}, \triangledown a_{n},\: \text{and}\: \triangledown^{2}a_{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

138 views

admin asked May 3, 2020

0 votes

0 answers

3170

Kenneth Rosen Edition 7 Exercise 8.1 Question 50 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ ... expressed in terms of $a_{n}, \triangledown a_{n}, \triangledown ^{2}a_{n},\dots, \triangledown^{k}a_{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

155 views

admin asked May 3, 2020

0 votes

0 answers

3171

Kenneth Rosen Edition 7 Exercise 8.1 Question 49 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ ... $a_{n−2} = a_{n} − 2\triangledown a_{n} + \triangledown^{2}a_{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

140 views

admin asked May 3, 2020

0 votes

0 answers

3172

Kenneth Rosen Edition 7 Exercise 8.1 Question 48 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ ... $a_{n−1} = a_{n} − \triangledown a_{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

166 views

admin asked May 3, 2020

0 votes

0 answers

3173

Kenneth Rosen Edition 7 Exercise 8.1 Question 47 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ The $(k + 1)^{\text{st}}$ ... $a_{n} = 4.$ $a_{n} = 2n.$ $a_{n} = n^{2}.$ $a_{n} = 2^{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

136 views

admin asked May 3, 2020

0 votes

0 answers

3174

Kenneth Rosen Edition 7 Exercise 8.1 Question 46 (Page No. 512)
Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$ is $\triangledown a_{n} = a_{n} − a_{n−1}.$ The $(k + 1)^{\text{st}}$ ... $a_{n} = 4.$ $a_{n} = 2n.$ $a_{n} = n^{2}.$ $a_{n} = 2^{n}.$

Let $\{a_{n}\}$ be a sequence of real numbers. The backward differences of this sequence are defined recursively as shown next. The first difference $\triangledown a_{n}$...

admin

146 views

admin asked May 3, 2020

0 votes

0 answers

3175

Kenneth Rosen Edition 7 Exercise 8.1 Question 45 (Page No. 512)
Question $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 ... how the disks are moved. Show that $R(n)\: \text{is}\: O(\sqrt{n}2^{\sqrt{2n}}).$

Question $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 th...

admin

171 views

admin asked May 2, 2020

0 votes

0 answers

3176

Kenneth Rosen Edition 7 Exercise 8.1 Question 44 (Page No. 512)
Question $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$ ... number of moves required to solve the Reve's puzzle for all integers $n$ with $1 \leq n \leq 25.$

Question $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 th...

admin

147 views

admin asked May 2, 2020

0 votes

0 answers

3177

Kenneth Rosen Edition 7 Exercise 8.1 Question 43 (Page No. 512)
Question $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 ... then $R(n) = \displaystyle{}\sum_{i = 1}^{k} i2^{i−1} − (t_{k} − n)2^{k−1}.$

Question $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 th...

admin

151 views

admin asked May 2, 2020

0 votes

0 answers

3178

Kenneth Rosen Edition 7 Exercise 8.1 Question 42 (Page No. 512)
Question $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 ... that if $k$ is as chosen in question $41,$ then $R(n) − R(n − 1) = 2^{k−1}.$

Question $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 th...

admin

132 views

admin asked May 2, 2020

0 votes

0 answers

3179

Kenneth Rosen Edition 7 Exercise 8.1 Question 41 (Page No. 512)
Question $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 ... $R(0) = 0\:\text{and}\: R(1) = 1.$

Question $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 th...

admin

237 views

admin asked May 2, 2020

0 votes

0 answers

3180

Kenneth Rosen Edition 7 Exercise 8.1 Question 40 (Page No. 512)
Question $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$ ... $5$ disks. $6$ disks. $7$ disks. $8$ disks.

Question $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 th...

admin

118 views

admin asked May 2, 2020

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true