Assume that multiplying a matrix $\style{font-family:'Times New Roman'}{G_1}$ of dimension $\style{font-family:'Times New Roman'}{p\times q}$ with another matrix $\style{font-family:'Times New Roman'}{G_2}$ of dimension $\style{font-family:'Times New Roman'}{q\times r}$ requires pqr scalar multiplications. Computing the product of n matrices $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3\mathit.\mathit.\mathit.G_\mathit n}$ can be done by parenthesizing in different ways. Define $\style{font-family:'Times New Roman'}{G_\mathit i\mathit\;G_{\mathit i\mathit+\mathit1}}$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3G_\mathit4G_\mathit5G_\mathit6}$ using parenthesization $\left(G_\mathit1\left(G_\mathit2G_\mathit3\right)\right)\left(G_\mathit4\left(G_\mathit5G_\mathit6\right)\right)\mathit,G_\mathit2G_\mathit3\mathit\;$ and $ G_\mathit5G_\mathit6 $ are the only explicitly computed pairs.
Consider a matrix multiplication chain $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5,}$ where matrices $ F_1,F_2,F_3,F_4 $ and $ F_5 $ are of dimensions $ 2\times25,\;25\times3,\;3\times16,\;16\times1 $, and $ 1\times1000,$ respectively. In the parenthesization of $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5}$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
Consider the following undirected graph G:
The value of V_{opt} − V_{greedy} is ____________.
Consider the following function from positive integers to real numbers:
$\style{font-family:'Times New Roman'}{10,\;\sqrt n,\;n,\;\log_2n,\;\frac{100}n.}$
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Consider the following table:
Match the algorithms to the design paradigms they are based on.
Let G= (V,E) be any connected undirected edge-weighted graph. The weight of the edges in E are positive and distinct. Consider the following statements:
(I) Munimum Spanning Tree of G is always unique.
(II) shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The Problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________
Match the algorithms with their time complexities:
The Breadth First search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
Consider the recurrence function $\style{font-family:'Times New Roman'}{T(n)=\left\{\begin{array}{l}2T\;(\sqrt n)+1,\;\;\;\;n>2\\2,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0<n\leq2\end{array}\right.}$
Then T(n) in terms of $\style{font-family:'Times New Roman'}\Theta$ notation is
Consider the following C function
Let a_{n} be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$?
Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is .
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Consider the recurrence relation $\style{font-family:'Times New Roman'}{a_1=8,a_n=6n^2+2n+a_{n-1}.\mathrm{Let}\;a_{99}=K\times10^4.}$ The value of $K$ is __________.
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry $W_{ij}$ in the matrix W.
$W=\left[\begin{array}{cccc}0& 2& 8& 5\\ 2& 0& 5& 8\\ 8& 5& 0& x\\ 5& 8& x& 0\end{array}\right]$
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ________ .
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _______.
G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in $ \mathrm\Theta\left(\mathit n^\mathit2\right) $ time
II. Bubblesort runs in $ \mathrm\Theta\left(\mathit n^\mathit2\right) $ time
III. Mergesort runs in $ \mathrm\Theta\left(\mathit n\right) $ time
IV. Insertion sort runs in $ \mathrm\Theta\left(\mathit n\right) $ time
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Match the following:
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n\left(\geq2\right)$ numbers? In the recurrence equations given in the options below, $ c $ is a constant.
Consider the following C program segment.
while(first <= last) { if(array[middle] < search) first = middle + 1; else if (array[middle] = = search) found = TRUE; else last = middle – 1; middle = (first + last)/2; } if (first > last) notPresent = TRUE;
The cyclomatic complexity of the program segment is ______.
Let $a_n$ represent the number of bit strings of length $n$ containing two consecutive 1s. What is the recurrence relation for $a_n$?
Let $G=\left(V,\;E\right)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $G=\left(V,\;E\right)$ let $ d\left(x\right) $ denote the shortest distance in $G$ from $s$ to $x.$ A breadth first search (BFS) is performed starting at $s.$ Let $T$ be resultant BFS tree. If $ \left(u,\;v\right) $ is an edge of $G$ that is not in $T$ , then which one of the following CANNOT be the value of $ d\left(u\right)-d\left(v\right)? $
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn form a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best asymptotic complexity considering all the operations?
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.
Consider the following C function. int fun1 (int n){ int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for(j = n; j > 1; j = j/2) ++p; for(k =1; k < p; k = k*2) ++q; } return q; } Which one of the following most closely approximates the return value of the function fun1?
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Given below are some algorithms, and some algorithm design paradigms.
Match the above algorithms on the left to the corresponding design paradigm they follow.
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
Consider the equality $\sum\limits_{i=0}^ni^3=X$ and the following choices for X.
I. $\theta \left({n}^{4}\right)$
II. $\theta \left({n}^{5}\right)$
III. $O\left({n}^{5}\right)$
IV. $\Omega \left({n}^{3}\right)$
The equality above remains correct if X is replaced by
Given a hash table T with 25 slots that stores 2000 elements, the load factor $\alpha $ for T is ______.
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes______.
Suppose $c=\left\langle c\left[0\right],\;...,\;c\left[k-1\right]\right\rangle$ is an array of lengt $k$, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c, a, n) z ← 1 for i ← 0 to k – 1 do z ← z^{2}mod n if c[i] = 1 then z ← (z $\times$ a) mod n return z
If $k=4,\;c=\left\langle1,\;0,\;1,\;1\right\rangle a=2$ and n = 8, then the output of DOSOMETHING (c, a, n) is _________.
Let f (n) = n and g(n) = n^{(1+sin n)}, where n is a positive integer. Which of the following statements is/are correct?
I. f (n) = O(g(n)) II. f (n) = $\Omega $(g(n))
Let G be a graph with n vertices and m edges.what is the tightest upper bound on the running time of depth first search on G, when G is represented as an adjecency matrix?
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtree having exactly 4 nodes is $O\left({n}^{a}{\mathrm{log}}^{b}n\right).$ Then the value of a+10b is _____.
Consider the directed graph given below.
which of the following is TRUE?
Let P be a quicksort program to sort numbers in ascendinng order using the first element as the pivot. Let t_{1} and t_{2} be the number of comparisions made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. which one of the following holds?
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
Consider the following pseudo code. What is the total number of multiplications to be performed?
D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
$T\left(n\right)=2T\left(\frac{n}{2}\right)+\mathrm{log}n$
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
Consider two strings A = ”qpqrr” and B = ”pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
The number of distinct minimum spanning trees for the weighted graph below is _____
The minimum number of arithematic operation required to evaluate the polynomial $P\left(X\right)={X}^{5}+4{X}^{3}+6X+5$ for a given value of X,using only one temporary variable is_____.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is 0(n^{a} log^{b}n + m^{c} log^{d}n), the value of a + 10b + 100c + 1000d is ____.
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
The number of elements that can be sorted in Θ(log n) time using heap sort is
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements is
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n- 1] is given below.
Let L_{i} denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize L_{n-1} =1.
For all i such that $0\le i\le n-2$
${L}_{i}=\begin{array}{l}\left\{\begin{array}{ll}1+{L}_{i+1}& ifA\left[i\right]<A[i+1]\\ 1& otherwise\end{array}\right.\end{array}$
Finally the length of the longest monotonically increasing sequence is Max (L_{0}, L_{1},…….L_{n-1}).
Which of the following statements is TRUE?
Which of the given options provides the increasing order of asymptotic complexity of functions ${f}_{1},{f}_{2,}{f}_{3}$, and ${f}_{4}$?
${f}_{1}\left(n\right)={2}^{n}$ ${f}_{2}\left(n\right)={n}^{\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}$ ${f}_{3}\left(n\right)=n{\mathrm{log}}_{2}n$ ${f}_{4}\left(n\right)={n}^{{\mathrm{log}}_{2}n}$
Four matrices M_{1}, M_{2} , M_{3} and M_{4}, of dimensions p × q , q × r , r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M_{1} × M_{2}) × (M_{3} × M_{4})). The total number of scalar multiplications is pqr + rst + prt. When multiplied as (((M_{1} × M_{2}) ×M_{3}) ×M_{4}), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is
An undirected graph G(V,E) contains n (n > 2) nodes named v_{1},v_{2}.....v_{n}.two node v_{i},v_{j} are connected if and only if 0 <| i - j | ≤ 2. Each edge (v_{i}, v_{j})is assigned a weight i +j. A sample graph with n = 4 is shown below.
What will be the cost of minimum spanning tree(MST) of such agraph with n node?