# Recent questions tagged descriptive

1
State whether the following statements are True or False with reasons for your answer: A two pass assembler uses its machine opcode table in the first pass of assembly.
2
State whether the following statements are True or False with reasons for your answer A symbol declared as ‘external’ in an assembly language program is assigned an address outside the program by the assembler itself.
1 vote
3
For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(\_)$.
1 vote
4
Consider the matrix $A=\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$. Find $A^n,$ in terms of $n,$ for $n\geq2.$
5
A multi-national conglomerate sells soap products for five different market segments, namely (i) Women, (ii) Men, (iii) Kids, (iv) Sports, and (v) Luxury. The sales of these five segments (in lakh number of packs) during $2012$ and $2017$ are shown in the ... than the sales of the Men segment in $2017$? During the period $2012-2017$, which segment experienced the minimum rate of increase in sales?
6
How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k > 0$. Solve by summation rules. Solve by combinatorial argument.
7
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
8
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
9
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.
10
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.$
1 vote
11
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
12
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
13
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
14
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)$
15
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)$
16
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)$
17
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
18
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.
19
Express the fast multiplication algorithm in pseudocode.
20
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
21
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
22
How many comparisons are needed for a binary search in a set of $64$ elements?
1 vote
23
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}.$
24
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.$
25
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.]
26
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}.$
27
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$
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)}$
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.
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.$