Recent questions in Discrete Mathematics - GATE Overflow

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 169 views

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?

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 62 views

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.

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 69 views

0 votes

0 answers

4

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 Boss | 44 views

+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.$

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 47 views

0 votes

0 answers

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.

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 15 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 13 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 11 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 11 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 15 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 8 views

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.

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

0 votes

0 answers

13

Kenneth Rosen Edition 7th Exercise 8.3 Question 4 (Page No. 535)
Express the fast multiplication algorithm in pseudocode.

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 9 views

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.

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 11 views

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

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 9 views

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?

asked May 10 in Combinatory by Lakshman Patel RJIT Boss | 20 views

+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}.$

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

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

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

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.]

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

+1 vote

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}.$

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

Page:

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

Recent questions in Discrete Mathematics

52,215 questions

60,006 answers

201,216 comments

94,687 users