151 questions in 7 topics. Try each one before you press "Show answer".
Consider the following recurrence relations: For all n>1, T1(n)=4T1(n/2)+T2(n) T2(n)=5T2(n/4)+Θ(log2n) Assume that for all n≤1, T1(n)=1 and T2(n)=1. Which one of the following options is correct?
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity O(n)?
Consider the following functions, where n is a positive integer. n1/3 , logn , log(n!) , 2logn Which one of the following options lists the functions in increasing order of asymptotic growth rate? Note: Assume the base of log to be 2.
Consider the following recurrence relation: T(n)=2T(n-1)+ n2n for n>0, T(0)=1 Which ONE of the following options is CORRECT?
Consider the following recurrence relation:
T(n) = {√n ⋅ T(√n) + n
for n ≥ 1
1
for n = 1
Which one of the following options is CORRECT?Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2 and T(n) = 5T(n - 1) - 6T(n - 2) for n ≥ 2 Which one of the following statement is TRUE?
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n2. Which of the following statements is/are TRUE?
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:Function 1 and Function 2 Function 1 while n > 1 do for i = 1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function 2 for i = 1 to 100 * n do x = x + 1; end for Let f1(n) and f2(n) denote the number of times the statement x = x + 1; is executed in Function 1 and Function 2, respectively.
Which one of the following statements is TRUE for all positive functions f(n)?
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers: T(n) = a T (n/b) + f(n) Which one of the following options is correct about the recurrence T(n) ?
Consider the following three functions. f1 = 10n f2 = n logn f3 = n✓n Which one of the following options arranges the function in the increasing order of asymptotic growth rate?
Consider the following recurrence relation.
T(n) = T(n/2) + T(2n/5) + 7n
, if n > 0
{
1 , if n = 0For parameters a and b, both of which are ω(1), T(n) = T(n 1/a ) + 1, and T(b)=1. Then T(n) is:
Consider the following functions from positives integers to real numbers 10, √n, n, log2n, 100/n. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
Consider the following C function
int fun(int n) {
int i, j;
for(i=1; i<=n; i++) {
for (j=1; j<n; j+=i) {
printf("%d %d", i, j);
}
}
}
Time complexity of fun in terms of θ notation isConsider the recurrence function 2 × T(√n) + 1, if n > 2
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst-case time complexity of this function is O(nα ), then the least possible value (accurate up to two decimal positions) of α is . Flowchart for Recursive Function A(n)
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?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?
T(n) = {
2,
if 0 < n ≤ 2
I. f(n) = O(g(n))
Then T(n) in terms of θ notation isConsider a complete binary tree where the left and the right subtrees of the root are max heaps. The lower bound for the number of operations to convert the tree to a heap is
Consider the equality X =∑i=0 n i3 following choices for X: I. Θ(n4) II. Θ(n5) III. O(n5) IV. Ω(n3)
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 O(na logb n + mc logd n) the value of a + 10b + 100c + 1000d is . for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is
Which one of the following correctly determines the solution of the recurrence relation with T(1)=1? T(n)=2T(n/2) + logn
Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
The equality above remains correct if X is
replaced byLet 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?
Which of the given options provides the increasing order of asymptotic complexity of functions f 1 , f 2 , f 3 and f 4 ? f1(n)=2n , f2(n)=n3/2, f3(n)=nlog2n , f4(n)=nlog n
The running time of an algorithm is represented
by the following recurrence relation:
n ; n ≤ 3
T(n) = {
n
T ( ) + cn; otherwise
3Consider the following functions: f(n) = 2n g(n) = n! h(n) = nlogn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
When n = 2(2k) for some k >= 0, the recurrence relation T(n) = √(2)T(n/2) + √(n), T(1) = 1 evaluates to :
Arrange the following functions in increasing asymptotic order: a. n1/3 b. en c. n7/4 d. nlog9n e. 1.0000001n
Consider the following C functions:int f1(int n)
{
Which one of the following represents the time
complexity of the algorithm?Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute bnmod m,0≤b , n≤m?
In the following C function, let n≥m.
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
How many recursive calls are made by this
function?Consider the following C code segment: int
IsPrime(n)
{What is the Asymptotic Notation of the following
recursive function:
int DoSomething (int n) {
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n); }Consider the following C-program fragment in which i, j, and n are integer variables. for (i = n, j = 0; i > 0; i/=2, j += i); Let Val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
Consider the following recurrence:
T(n) = 2T([√n]) + 1, T(1) = 1
Which one of the following is true?
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Primen"); return 0;}
return 1;
} Let T(n)denote the number of times the for
loop is executed by the program on input n.
Which of the following is TRUE?Suppose T(n)=2T(n/2)+n, T(0)=T(1)=1 Which one of the following is FALSE?
The Asymptotic Notation of computing the transitive closure of a binary relation on a set of n elements is known to be:
Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}
Suppose we modify the above function foo() and
store the values of foo (i), 0≤i < n, as and
when they are computed. With this modification,
the time complexity for function foo() is
significantly reduced. The space complexity of
the modified function would be:Consider an array A = [10, 7, 8, 19, 41,35, 25, 31]. Suppose the merge sort algorithm is executed on array A to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations. A merge operation on sorted left array L and sorted right array R is said to be void if the output of the merge operation is the elements of array L followed by the elements of array R. The number of void merge operations among these 7 merge operations is . (answer in integer)
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?
Consider the following array: 23 , 32 , 45 , 69 , 72 , 73 , 89 , 97 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is
Consider a sequence of 14 elements:A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3 ,0].The sequence sum S(i, j) = ∑j k=i A[k].Determine the maximum of S(i ,j), where 0≤ i≤ j< 14.(Divide and conquer approach may be used.)
There are n unsorted arrays: A 1 , A 2 , ..., A n . Assume that n is odd. Each of A 1 , A 2 , ..., A n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A 1 , A 2 , ..., A 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. Quick sort runs in Θ(n2) time II. Bubble sort runs in Θ(n2) time III. Merge sort runs in Θ(n) time IV. Insertion sort runs in Θ(n) time
The worst-case running time of Insertion sort, Merge sort and Quick sort, respectively, are:
Suppose you are provided with the following
function declaration in the C programming
language.
int partition(int a[ ], int n);
The function treats the first element of a[] as a
pivot, and rearranges the array so that all elements
less than or equal to the pivot is in the left part of
the array, and all elements greater than the pivot
is in the right part. In addition, it moves the pivot
so that the pivot is the last element of the left part.
The return value is the number of elements in the
left part. The following partially given function in
the C programming language is used to find the
k-th smallest element in an array a[ ] of size n
using the partition function. We assume k <= n
C
int kth_smallest(int a[], int n, int k)
{
int left_end = partition(a, n);
if ( left_end+1 == k ){
return a[left_end];
}
if ( left_end+1 > k ){
return kth_smallest(
);
} else {
return kth_smallest(
);
}
}
The missing arguments lists are respectivelyWhich one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( >=2) numbers? In the recurrence equations given in the options below, c is a constant.
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
Let P is a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons 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 finding the minimum and the maximum of 100 numbers is ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank ! HINTS & SOLUTIONS
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
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
The average case and worst case complexities for Merge sort algorithm are
Let G(V,E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let s∈V be a vertex in G. For every u∈V and for every k ≥0, let dk(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then dk(u)=∞.Consider the statements: S1: For every k ≥0 and u ∈V, dk+1(u)≤dk(u). S2: For every (u,v)∈E, if (u,v) is part of a shortest path (in terms of weight) from s to v, then for every k≥ 0,dk(u)≤dk(v). Which one of the following options is correct?
Let G(V,E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of G is/are true?
Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a source vertex s in G, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from s to all vertices that are reachable from s in G?
Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d1(u,v) and d2(u,v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant α is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is . (Answer in integer)
Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value of d(u, v), u, v ∈V such that u ≠ v, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
The number of spanning tree in complete labelled graph of 4 vertices labelled A, B, C, and D is......
Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?
The number of distinct minimum-weight spanning trees of the following graph is .
"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] = 1 indicates a directed edge from node i
to node j."A directed spanning tree of G, rooted at
r ∈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
.Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
Consider the following undirected graph with edge weights as shown: The number of minimum-spanning trees of the graph is .
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?
Let G be a connected undirected weighted graph. Consider the following two statements. S1 : There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S2 : If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?
Let G = (V, E) be a directed, weighed graph with weight function w : E -> R. For some function f : V - > R, for each edge (u, v) in E, define w'(u, v) as w(u, v) + f(u) - f(v). Which one of the options completes the following sentence so that it is TRUE? "The shortest paths in G under w are shortest paths under w' too, ".
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V × V is added to G. The worst case time complexity determining if T is still an MST of the resultant graph is
Consider a graph G = (V, E), where V = {v 1 , v 2 ,
..., v 100 }, E = {(v i , v j ) | 1 <= i <= j <= 100}, and
weight of the edge (v i , v j ) is |i – j|. The weight of
the minimum spanning tree of G is .
ALGORITHMS
Check Out Our Gate Courses & Secure Your Dream Rank !
5Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum- weight edge crossing the cut. Which of the above two statements is/are TRUE?
Consider the following undirected graph G: Choose a value of x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is .
Let G be a complete undirected graph on 4 vertices having 6 edges with weights being 1,2 a minimum weight spanning tree of G can have is .
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 Q: Shortest path between any pair of vertices does not change
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
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.A message is made up entirely of characters from
the set X = {P,Q,R,S,T} . The table of
probabilities of each character is shown below :
Character
Probability
P
0.22
Q
0.17
R
0.34
S
0.19
T
0.08
Total
1.00
A message of 100 characters over X is encoded
using Huffman coding. Then the excepted length
of the encoded message in bits isThe 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 isLet 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 .
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
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?
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 undirected graph G(V,E) contains n (n > 2) nodes named v1, v2... vn. Two nodes vi , vj are connected if and only if 0 < | i- j | < = 2 . Each edge ( vi, vj )is assigned a weight i + j. A sample graph with n = 4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with 11 nodes?
An undirected graph G(V, E) contains n (n > 2) nodes named v1, v2, . . . , vn. Two nodes vi, vj are connected if and only if 0 < |i - j| ≤ 2. Each edge (vi, vj) is assigned a weight i + j. A sample graph with n = 4 is shown below. The length of the path from v5 to v6 in the MST of previous question with n = 10 is
Consider a complete undirected graph with vertex
set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below
is the weight of the edge {i, j}.
0
1
8
1 4
l1
0
12
4 9
W = ⎪8 12
0
7 3⎪
1
4
7
0 2
h4
9
3
2 0)
What is the minimum possible weight of a spanning
tree T in this graph such that vertex 0 is a leaf node
in the tree T?Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
Consider a weighted, undirected graph with positive edge weights and let u v be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements ?
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is False ?
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the Huffman code for the letters a,b,c,d,e,f?
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21 A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s∈ X and t∈Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. The edge e must definitely belong to:
An undirected graph G has n nodes. Its adjacency matrix is given by an nxn square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. which one of the following is TRUE?
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is:
We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the d th unit of time. What is the maximum profit earned?
We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the d th unit of time. Are all tasks completed in the schedule that gives maximum profit?
Consider a table T, where the elements T[i][j],
0 <= i, j <= n, represent the cost of the optimal
solutions of different subproblems of a problem
that is being solved using a dynamic
programming algorithm. The recursive
formulation to compute the table entries is as
follows:
T[0][k] = T[k][0] = 1
for k = 0, 1, 2, ..., n
T[i][j] = 2T[i-1][j]+3T[i][j-1] for 1 ≤ i, j ≤ n
Consider the following two algorithms to
compute entries of T. Assume that for both the
algorithms, for all 0 ≤ i, j ≤ n, T[i][j] has been
initialized to 1.
Algorithm B1:
For i = 1 to n
For j = 1 to n
T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]
Algorithm B2:
For s = 2 to 2n
For i = 1 to n
For j = 1 to n
If (i + j == s)
T[i][j] = 2T[i - 1][j] + 3T[i][j - 1]
Algorithm Bk, k ∈ {1, 2}, is said to be correct if
and only if it calculates the correct values of
T[i][j], for all 0 ≤ i, j ≤ n, as per the recursive
formulation, at the end of the execution of the
algorithm Bk.
Which one of the following statements is true?Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling prices of a rod whose length is i meters. Consider the array of prices : p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18 Which of the following statements is/are correct about R 7 ?
Assume that multiplying a matrix G 1 of dimension p×q with another matrix G 2 of dimension q × r requires scalar multiplications. Computing the product of matrices G1 G2 G3 ......Gn can be done by parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G1 G2 G3 G4 G5 G6 using parenthesization ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank ! (G1(G2G3)) (G4(G5G6)).G2 G3 and G5 G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1 F2 F3 F4 F5 , where matrices F1 F2 F3 F4 F5 are of dimensions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and 1×1000, respectively.In the parenthesization of F1 F2 F3 F4 F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are:
Consider the weights and values of items listed below. Note that there is only one unit of each item. The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt - Vgreedy is
Let A 1 , A 2 , A 3 , and A 4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is .
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 =
.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;
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 ≤
i ≤ n – 2
b) F2 F3 only
L = 1 + Li+1
if A[i] < A[i + 1]
i
{
c) F3 F4 only
d) F1,F2 and F4Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is: ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !
The weight of a sequence a0 , a1 , ..., an–1 of real numbers is defined as a0 + a1 / 2 + ...+ a n–1 /2n–1 . A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0 , a1 ,..., an-1 . Then X is equal to
A sub-sequence of a given sequence is just the
given sequence with some elements (possibly
none or all) left out. We are given two sequences
X[m] and Y[n] of lengths m and n, respectively,
with indexes of X and Y starting from 0.
We wish to find the length of the longest
common sub-sequence (LCS) of x[m] and Y[n]
as l(m,n), where an incomplete recursive
definition for the function l(i,j) to compute the
length of the LCS of x[m] and Y[n] is given
below:
0, if either i = 0 or j = 0
l(i, j) = { expr1, if i, j > 0 and x [i-1] = Y [j -1]
expr2, if i, j > 0 and x [i - 1] ! = Y [j - 1]
Which one of the following options is correct?The subset-sum problem is defined as follows.
Given
a
set
of
n
positive
integers,
S={a1,a2,...,an} and positive integer W, is there
a subset of S whose elements sum to W? A
dynamic program for solving this problem uses
a 2-dimensional Boolean array, X, with n rows
and W+1 columns. X[i,j], 1≤i≤n, 0≤j≤W, is
TRUE if and only if there is a subset of
{a1,a2,...,ai }whose elements sum to j.
Which entry of the array X, if TRUE, implies
that there is a subset whose elements sum to W?The subset-sum problem is defined as follows.
Given a set of n positive integers, S={a1,a2,...,an
} and positive integer W, is there a subset of S
whose elements sum to W? A dynamic program
for solving this problem uses a 2-dimensional
Boolean array, X, with n rows and W+1
columns. X[i,j], 1≤i≤n, 0≤j≤W, is TRUE if and
only if there is a subset of {a1,a2,...,ai }whose
elements sum to j.Which of the following is
valid for 2≤i≤n and ai≤j≤W?Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V,E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v ∈V. DFS(G) : unmark all v ∈ V t ← 0 for each v ∈ V if v is unmarked t ← Explore (G, v, t ) end if end for Explore ( G, v, t ): mark v t ← t + 1 d[v] ← t for each (v, w) ∈ E if w is unmarked t ← Explore (G, w, t) end if end for t ← t + 1 f[v] ← t return t Suppose that the input directed graph G(V,E) is a directed acyclic graph (DAG). For an edge (u,v)∈E, which of the following options will NEVER be correct?
An undirected, unweighted, simple graph G(V, E) is
said to be 2 -colorable if there exists a function c: V →
{0,1} such that for every (u, v) ∈ E, c(u) ≠ c(v).
Which of the following statements about 2-
colorable graphs is/are true?Consider the following algorithm someAlgo that takes an undirected graph G as input. someAlgo(G) : 1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at maximum distance from v as given by the BFS. 2. Run BFS on G again with u as the starting vertex. Let z be the vertex at maximum distance from u as given by the BFS. 3. Output the distance between u and z in G. The output of someAlgo(T) for the tree shown in the given figure is . (Answer in integer) 5 5 ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex
The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is Which one of the following statements is true?
Let U = {1, 2, 3}. Let 2U denote the powerset of U.
Consider an undirected graph G whose vertex set is
2U. For any A, B in 2U, (A, B) is an edge in G if and
only if (i) A != B, and (ii) either A ⊆B or B ⊆A.
For any vertex A in G, the set of all possible orderings
in which the vertices of G can be visited in a Breadth
First Search (BFS) starting from A is denoted by
B(A).
If Φ denotes the empty set, then the cardinality of
B(Φ) is .Let G = (V, E) be an undirected unweighted
connected graph. The diameter of G is defined as:
diam(G)=max{" the length of shortest path
between " u" and " v}
Let M be the adjacency matrix of G. Define graph
G2 on the same set of vertices with adjacency
matrix N, where
v. Suppose T is also a breadth first search (BFS)
N
1
if Mij > 0 or Pij > 0
tree in G, rooted at v. Which of the following
statements is/are TRUE for every such graph G and
ij = {0
where P = M2.
otherwise
tree T?Match Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i - j| = 1. Which of the statements above must necessarily be true?
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 .
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the Time Complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Let G= (V,E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈ V, let d (x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d (u) - d (v)?
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 .
Consider the following sequence of nodes for the undirected graph given below: 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which of the above is/are possible output(s)?
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u terminates. Which of the following statements is always TRUE for all edges (u, v) in the graph ?
Consider the DAG with V = {1,2,3,4,5,6}, shown
below
Which of the following is NOT a topological
ordering?Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that d(P)=5 units f(P)=12 units d(Q)=6 units f(Q)=10 units d(R)=14 unitf(R)=18 units Which one of the following statements is TRUE about the graph?
Let T be a depth first search tree in a undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?
Consider an array A of integers of size n. The
indices of A run from 1 to n. An algorithm is to
be designed to check whether A satisfies the
condition given below.
for all i, j {1, ..., n - 1} such that i > j,
( A[i + 1] - A[i] ) > ( A[j + 1] - A[j] )
Which one of the following gives the worst case
time complexity of the fastest algorithm that can
be designed for the problem?Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting array is sorted in non- decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is .
Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n
Let A be an array of 31 numbers consisting of sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index i that A[i] is 1 by probing the minimum numbers of locations in A. The worst case number of probes performed by an optimal algorithm is .
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly linked list with pointers to the head node and tail node of the list. Q: Min-heap implemented using an array. R: Binary Search Tree. Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size n of these data structures?
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract- Max(A) extracts and deletes the maximum element from A. The operation Insert(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Which one of the following sequences when stored in an array at locations A[1], ..., A[10] forms a max-heap?
Consider the following table: Algorithms Design Paradigms P Kruskal i Divide and Conquer Q Quicksort ii Greedy R Floyd- Warshall iii Dynamic Programming
Match the algorithms with their time complexities: Algorithm Time complexity P Towers of Hanoi with n disks i Θ(n2 ) Q Binary search given n sorted numbers ii Θ(nlog n) R Heap sort given n numbers at the worst case iii Θ(2n ) S Addition of two n × n matrices iv Θ(logn) ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !
Given below are some algorithms, and some algorithm design paradigms. List - I P. Dijkstra's Shortest Path Q. Floyd-Warshall algorithm to compute all pairs shortest path R. Binary search on a sorted array S. Backtracking search on a graph List – II i. Divide and Conquer ii. Dynamic Programming iii. Greedy design iv. Depth-first search v. Breadth-first search Match the above algorithms on the left to the corresponding design paradigm they follow.
Match the following: (P) Prim's algorithm for minimum spanning tree (i) Backtracking (Q) Floyd-Warshall algorithm for all pairs shortest paths (ii) Greedy method (R) Mergesort (iii) Dynamic programming (S) Hamiltonian circuit (iv) Divide and conquer
An algorithm performs (logN)1/2 find operations, N insert operations, (logN)1/2 delete operations, and (logN)1/2 decrease-key operations on a set of data items with keys drawn from 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 total asymptotic complexity considering all the operations?
The number of elements that can be sorted in Θ(log n) time using heap sort is
Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10n log10 n time units to process n records. What is the smallest value of k for which package B will be preferred over A?