menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Quick search syntax
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
Recent Posts
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
IITH CSE interview M Tech RA Winter admission 2021
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.4k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent questions tagged kenneth-rosen
Recent Blog Comments
Hi, could you please update us about the Mock...
Hi, just curious if there are any updates...
thanks himanshu2021. But I am asking for the page...
But IISc hasn't mentioned TCS as one of their...
@kiioo https://gateoverflow.in/blog/11426/jest-20...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions tagged kenneth-rosen
0
votes
1
answer
1
Kenneth Rosen Edition 7th Exercise 8.3 Question 16 (Page No. 535)
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
407
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
2
Kenneth Rosen Edition 7th Exercise 8.3 Question 15 (Page No. 535)
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
151
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
2
answers
3
Kenneth Rosen Edition 7th Exercise 8.3 Question 14 (Page No. 535)
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
196
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
4
Kenneth Rosen Edition 7th Exercise 8.3 Question 13 (Page No. 535)
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
189
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
1
vote
2
answers
5
Kenneth Rosen Edition 7th Exercise 8.3 Question 12 (Page No. 535)
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
135
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
6
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.
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
82
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
7
Kenneth Rosen Edition 7th Exercise 8.3 Question 10 (Page No. 535)
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
57
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
8
Kenneth Rosen Edition 7th Exercise 8.3 Question 9 (Page No. 535)
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
62
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
9
Kenneth Rosen Edition 7th Exercise 8.3 Question 8 (Page No. 535)
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
57
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
10
Kenneth Rosen Edition 7th Exercise 8.3 Question 7 (Page No. 535)
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
50
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
11
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?$
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
85
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
12
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.
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, 2020
in
Combinatory
Lakshman Patel RJIT
56
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
13
Kenneth Rosen Edition 7th Exercise 8.3 Question 4 (Page No. 535)
Express the fast multiplication algorithm in pseudocode.
Express the fast multiplication algorithm in pseudocode.
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
54
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
14
Kenneth Rosen Edition 7th Exercise 8.3 Question 3 (Page No. 535)
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
51
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
15
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$?
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, 2020
in
Combinatory
Lakshman Patel RJIT
99
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
16
Kenneth Rosen Edition 7th Exercise 8.3 Question 1 (Page No. 535)
How many comparisons are needed for a binary search in a set of $64$ elements?
How many comparisons are needed for a binary search in a set of $64$ elements?
asked
May 10, 2020
in
Combinatory
Lakshman Patel RJIT
88
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
1
vote
0
answers
17
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}.$
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}$ ... is $m,$ there is a particular 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, 2020
in
Combinatory
Lakshman Patel RJIT
68
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
18
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.$
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}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
62
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
19
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.]
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, 2020
in
Combinatory
Lakshman Patel RJIT
56
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
2
votes
0
answers
20
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}.$
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, 2020
in
Combinatory
Lakshman Patel RJIT
43
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
21
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$
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, 2020
in
Combinatory
Lakshman Patel RJIT
32
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
22
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 ...
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$ ... relation to obtain $a_{n} = \dfrac{C +\displaystyle{} \sum_{i = 1}^{n}Q(i)h(i)}{g(n + 1)Q(n + 1)}$
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
54
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
23
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.
A new employee at an exciting new software company starts with a salary of $\$50,000$ and is promised that at the end of each year her salary will be double her salary of the previous year, with an extra increment of $\$10,000$ for each year she has been with the ... $n^{\text{th}}$ year of employment. Solve this recurrence relation to find her salary for her $n^{\text{th}}$ year of employment.
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
52
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
24
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.$
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 on the island at the start of the ... $n^{\text{th}}$ year for each $n \geq 3.$
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
50
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
25
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.
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. None of the rabbits ever die or leave ... relation in $(A)$ determine the number of pairs of rabbits on the island $n$ months after one pair is left on the island.
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
45
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
26
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}.$
(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, 2020
in
Combinatory
Lakshman Patel RJIT
35
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
27
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}.]$
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, 2020
in
Combinatory
Lakshman Patel RJIT
28
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
28
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.$
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, 2020
in
Combinatory
Lakshman Patel RJIT
25
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
0
answers
29
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}.$
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}$ ... $n\: f_{n}$ is less than $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}.$
asked
May 6, 2020
in
Combinatory
Lakshman Patel RJIT
32
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
0
votes
1
answer
30
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.$
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 5, 2020
in
Combinatory
Lakshman Patel RJIT
68
views
kenneth-rosen
discrete-mathematics
counting
recurrence-relations
descriptive
Page:
1
2
3
4
5
6
...
38
next »
...