Algorithm
Q141.
Let G(V, E) be a directed graph, where V = \{1, 2, 3, 4, 5 \} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right. A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____Q142.
For constants a\geq 1 and b \gt 1, consider the following recurrence defined on the non-negative integers: T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n) Which one of the following options is correct about the recurrence T(n)?Q143.
For parameters a and b, both of which are \omega(1) , T(n)=T(n^{1/a})+1, and T(b)=1. Then T(n) isQ144.
The running time of an algorithm is given by:T(n)=\left\{\begin{matrix} T(n-1)+T(n-2)-T(n-3), &\text { if } n>3\\ n, &\text{ otherwise}\end{matrix}\right.Then what should be the relation between T(1),T(2),T(3), so that the order of the algorithm is constant?Q145.
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(n)=2T(\frac{n}{2})+lognQ146.
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i,j with i \lt j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is_______.Q147.
Consider the following recurrence relation. T\left ( n \right )=\left\{\begin{array} {lcl} T(n/2)+T(2n/5)+7n & \text{if} \; n > 0\\1 & \text{if}\; n=0 \end{array}\right. Which one of the following options is correct?Q148.
Consider the following recurrence:T(n)=2T\left ( \sqrt{n}\right )+1, T(1)=1Which one of the following is true?Q150.
Consider the recurrence function T(n)=\left\{\begin{matrix} 2T(\sqrt{n})+1, & n \gt 2\\ 2,& 0 \lt n\leq 2 \end{matrix}\right. Then T(n) in terms of \theta notation is