Algorithms
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.
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?Q144.
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) isQ145.
Consider the following recurrence:T(n)=2T\left ( \sqrt{n}\right )+1, T(1)=1Which one of the following is true?Q146.
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(n)=2T(\frac{n}{2})+lognQ147.
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_______.Q148.
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?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