Recent questions without answers - GATE Overflow

0 votes

0 answers

1

Kenneth Rosen Edition 7th Exercise 8.3 Question 13 (Page No. 535)
Give a big-O estimate for the function $f$ in question $12$ if $f$ is an increasing function.

asked May 10 in Combinatory by Lakshman Patel RJIT | 96 views

0 votes

0 answers

2

Kenneth Rosen Edition 7th Exercise 8.3 Question 11 (Page No. 535)
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.

asked May 10 in Combinatory by Lakshman Patel RJIT | 25 views

0 votes

0 answers

3

Kenneth Rosen Edition 7th Exercise 8.3 Question 6 (Page No. 535)
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$

asked May 10 in Combinatory by Lakshman Patel RJIT | 18 views

0 votes

0 answers

4

Kenneth Rosen Edition 7th Exercise 8.3 Question 5 (Page No. 535)
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplication algorithm.

asked May 10 in Combinatory by Lakshman Patel RJIT | 17 views

0 votes

0 answers

5

Kenneth Rosen Edition 7th Exercise 8.3 Question 3 (Page No. 535)
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.

asked May 10 in Combinatory by Lakshman Patel RJIT | 21 views

0 votes

0 answers

6

Kenneth Rosen Edition 7th Exercise 8.3 Question 2 (Page No. 535)
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?

asked May 10 in Combinatory by Lakshman Patel RJIT | 16 views

+1 vote

0 answers

7

Kenneth Rosen Edition 7th Exercise 8.2 Question 52 (Page No. 527)
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 32 views

0 votes

0 answers

8

Kenneth Rosen Edition 7th Exercise 8.2 Question 51 (Page No. 527)
Prove Theorem $4:$ 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 $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 19 views

0 votes

0 answers

9

Kenneth Rosen Edition 7th Exercise 8.2 Question 53 (Page No. 527)
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]

asked May 6 in Combinatory by Lakshman Patel RJIT | 18 views

+1 vote

0 answers

10

Kenneth Rosen Edition 7th Exercise 8.2 Question 50 (Page No. 527)
It can be shown that Cn, the average number of comparisons made by the quick sort algorithm (described in preamble to question $50$ in exercise $5.4),$ when sorting $n$ ... $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 16 views

0 votes

0 answers

11

Kenneth Rosen Edition 7th Exercise 8.2 Question 49 (Page No. 527)
Use question $48$ to solve the recurrence relation $(n + 1)a_{n} = (n + 3)a_{n-1} + n, \:\text{for}\: n \geq 1, \:\text{with}\: a_{0} = 1$

asked May 6 in Combinatory by Lakshman Patel RJIT | 15 views

0 votes

0 answers

12

Kenneth Rosen Edition 7th Exercise 8.2 Question 48 (Page No. 526)
Some linear recurrence relations that do not have constant coefficients can be systematically solved. This is the case for recurrence relations of the form $f (n)a_{n} = g(n)a_{n-1} + h(n).$ Exercises $48-50$ illustrate this. Show that the recurrence relation ...

asked May 6 in Combinatory by Lakshman Patel RJIT | 12 views

0 votes

0 answers

13

Kenneth Rosen Edition 7th Exercise 8.2 Question 47 (Page No. 526)
A new employee at an exciting new software company starts with a salary of $\$ ... year of employment. Solve this recurrence relation to find her salary for her $n^{\text{th}}$ year of employment.

asked May 6 in Combinatory by Lakshman Patel RJIT | 13 views

0 votes

0 answers

14

Kenneth Rosen Edition 7th Exercise 8.2 Question 46 (Page No. 526)
Suppose that there are two goats on an island initially.The number of goats on the island doubles every year by natural reproduction, and some goats are either added or removed each year. Construct a recurrence relation for the number of goats ... assuming that n goats are removed during the $n^{\text{th}}$ year for each $n \geq 3.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 19 views

0 votes

0 answers

15

Kenneth Rosen Edition 7th Exercise 8.2 Question 45 (Page No. 526)
Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of $1$ month and six new pairs of rabbits at the age of $2$ months and every month afterward ... $n$ months after one pair is left on the island.

asked May 6 in Combinatory by Lakshman Patel RJIT | 14 views

0 votes

0 answers

16

Kenneth Rosen Edition 7th Exercise 8.2 Question 44 (Page No. 526)
(Linear algebra required ) Let $A_{n}$ be the $n \times n$ matrix with $2s$ on its main diagonal, $1s$ in all positions next to a diagonal element, and $0s$ everywhere else. Find a recurrence relation for $d_{n},$ the determinant of $A_{n}.$ Solve this recurrence relation to find a formula for $d_{n}.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 11 views

0 votes

0 answers

17

Kenneth Rosen Edition 7th Exercise 8.2 Question 43 (Page No. 526)
Express the solution of the linear nonhomogenous recurrence relation $a_{n} = a_{n-1} + a_{n-2} + 1\:\text{for}\: n \geq 2 \:\text{where}\: a_{0} = 0\:\text{and}\: a_{1} = 1$ in terms of the Fibonacci numbers. [Hint: Let $b_{n} = a_{n + 1}$ and apply question $42$ to the sequence $b_{n}.]$

asked May 6 in Combinatory by Lakshman Patel RJIT | 13 views

0 votes

0 answers

18

Kenneth Rosen Edition 7th Exercise 8.2 Question 42 (Page No. 526)
Show that if $a_{n} = a_{n-1} + a_{n-2}, a_{0} = s\:\text{and}\: a_{1} = t,$ where $s$ and $t$ are constants, then $a_{n} = sf_{n-1} + tf_{n}$ for all positive integers $n.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 13 views

0 votes

0 answers

19

Kenneth Rosen Edition 7th Exercise 8.2 Question 41 (Page No. 526)
Use the formula found in Example $4$ for $f_{n},$ the $n^{\text{th}}$ Fibonacci number, to show that fn is the integer closest to $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}$ Determine for which $n\: f_{n}$ is ... for which $n\: f_{n}$ is less than $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 14 views

0 votes

0 answers

20

Kenneth Rosen Edition 7th Exercise 8.2 Question 40 (Page No. 526)
Solve the simultaneous recurrence relations $a_{n} = 3a_{n-1} + 2b_{n-1}$ $b_{n} = a_{n-1} + 2b_{n-1}$ with $a_{0} = 1 \: \text{and}\: b_{0} = 2.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 19 views

0 votes

0 answers

21

Kenneth Rosen Edition 7th Exercise 8.2 Question 39 (Page No. 526)
a) Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = a_{n-4}.$ [Note: These include complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1, a_{1} = 0, a_{2} = -1,\: \text{and}\: a_{3} = 1.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 11 views

0 votes

0 answers

22

Kenneth Rosen Edition 7th Exercise 8.2 Question 38 (Page No. 526)
Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = 2a_{n-1} - 2a_{n-2}.$ [Note: These are complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1\:\text{and}\: a_{1} = 2.$

asked May 6 in Combinatory by Lakshman Patel RJIT | 6 views

0 votes

0 answers

23

Kenneth Rosen Edition 7th Exercise 8.2 Question 37 (Page No. 526)
Let an be the sum of the first $n$ triangular numbers, that is, $a_{n} = \displaystyle{}\sum_{k = 1}^{n} t_{k},\:\text{where}\: t_{k} = k(k + 1)/2.$ Show that $\{an\}$ satisfies the linear nonhomogeneous ... and the initial condition $a_{1} = 1.$ Use Theorem $6$ to determine a formula for $a_{n}$ by solving this recurrence relation.

asked May 6 in Combinatory by Lakshman Patel RJIT | 10 views

0 votes

0 answers

24

Kenneth Rosen Edition 7th Exercise 8.2 Question 36 (Page No. 526)
Let an be the sum of the first $n$ perfect squares, that is, $a_{n} = \displaystyle{}\sum_{k = 1}^{n} k^{2}.$ Show that the sequence $\{a_{n}\}$ ... initial condition $a_{1} = 1.$ Use Theorem $6$ to determine a formula for $a_{n}$ by solving this recurrence relation.

asked May 5 in Combinatory by Lakshman Patel RJIT | 13 views

0 votes

0 answers

25

Kenneth Rosen Edition 7th Exercise 8.2 Question 35 (Page No. 526)
Find the solution of the recurrence relation $a_{n} = 4a_{n-1} - 3a_{n-2} + 2^{n} + n + 3\:\text{with}\: a_{0} = 1\:\text{and}\: a_{1} = 4.$

asked May 5 in Combinatory by Lakshman Patel RJIT | 13 views

0 votes

0 answers

26

Kenneth Rosen Edition 7th Exercise 8.2 Question 34 (Page No. 526)
Find all solutions of the recurrence relation $a_{n} =7a_{n-1} - 16a_{n-2} + 12a_{n-3} + n4^{n}\:\text{with}\: a_{0} = -2,a_{1} = 0,\:\text{and}\: a_{2} = 5.$

asked May 5 in Combinatory by Lakshman Patel RJIT | 10 views

0 votes

0 answers

27

Kenneth Rosen Edition 7th Exercise 8.2 Question 33 (Page No. 525)
Find all solutions of the recurrence relation $a_{n} = 4a_{n-1} - 4a_{n-2} + (n + 1)2^{n}.$

asked May 5 in Combinatory by Lakshman Patel RJIT | 10 views

0 votes

0 answers

28

Kenneth Rosen Edition 7th Exercise 8.2 Question 32 (Page No. 525)
Find the solution of the recurrence relation $a_{n} = 2a_{n-1} + 3 \cdot 2^{n}.$

asked May 5 in Combinatory by Lakshman Patel RJIT | 12 views

0 votes

0 answers

29

Kenneth Rosen Edition 7th Exercise 8.2 Question 31 (Page No. 525)
Find all solutions of the recurrence relation $a_{n} = 5a_{n-1} - 6a_{n-2} + 2^{n}+ 3n.$ [Hint: Look for a particular solution of the form $qn2^{n} + p_{1}n + p_{2},$ where $q, p_{1}, \text{and}\: p_{2}$ are constants.]

asked May 5 in Combinatory by Lakshman Patel RJIT | 11 views

0 votes

0 answers

30

Kenneth Rosen Edition 7th Exercise 8.2 Question 30 (Page No. 525)
Find all solutions of the recurrence relation $a_{n} = -5a_{n-1} - 6a_{n-2} + 42 \cdot 4^{n}.$ Find the solution of this recurrence relation with $a_{1} = 56\:\text{and}\: a_{2} = 278.$

asked May 5 in Combinatory by Lakshman Patel RJIT | 12 views

Page:

1
2
3
4
5
6
...
514
next »

Recent questions without answers

52,345 questions

60,501 answers

201,879 comments

95,329 users