GATE CSE & IT

Consider the following recurrence relations: For all $n>1$, $$ \begin{aligned} & T_1(n)=4 T_1\left(\frac{n}{2}\right)+T_2(n) \\ & T_2(n)=5 T_2\left(\frac{n}{4}\right)+\theta\left(\...

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 numb...

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?

Consider the following functions, where $n$ is a positive integer. $$ n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)} $$ Which one of the following options lists the functions in incr...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

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. $\fora...

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 t...

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 $d_1(u, v)$ and $d_2(u, v)$ be the sho...

Consider the following recurrence relation : $$T(n)=2 T(n-1)+n 2^n \text { for } n>0, T(0)=1$$ Which ONE of the following options is CORRECT?

$$\text { The pseudocode of a function fun( ) is given below : }$$ fun(int A[0, .., n-1]) { for i = 0 to n-2 for j=0 to n-i-2 if (A[]]>A[j + 1]) then swap A[j] and A[j+1] } Let $A[...

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following state...

Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1=i=n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 . . n]$...

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 thro...

Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the followin...

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 \geq 2$ Which one of the following statements is TRUE?

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 result...

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 statemen...

Let $$f$$ and $$g$$ be functions of natural numbers given by $$f(n)=n$$ and $$g(n)=n^2$$. Which of the following statements is/are TRUE?

Consider functions Function_1 and Function_2 expressed in pseudocode as follows: 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...

Which one of the following statements is TRUE for all positive functions f(n) ?

Consider the following recurrence : f(1) = 1; f(2n) = 2f(n) $$-$$ 1, for n $$\ge$$ 1; f(2n + 1) = 2f(n) + 1, for n $$\ge$$ 1; Then, which of the following statements is/are TRUE?

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] = \l...

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

Define R n 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] denotes the selling p...

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$...

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one lette...

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

Consider the following three functions. f 1 = 10 n , f 2 = n logn , f 3 = n √n Which one of the following options arranges the functions in the increasing order of asymptotic growt...

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 above arr...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$ Wh...

Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tree...

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 s...

For parameters a and b, both of which are $$\omega \left( 1 \right)$$, T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1. Then T(n) is

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) $$ \in $$ V $$ \t...

Consider a sequence of 14 elements : A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum $$S\left( {i,j} \right) = \sum\limits_{k = 1}^j {A\left[ k \right...

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 array...

Consider the following statements : I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node I...

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...

Assume that multiplying a matrix $${G_1}$$ of dimension $$p \times q$$ with another matrix $${G_2}$$ of dimension $$q \times r$$ requires $$pqr$$ scalar multiplications. Computing...

Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24 The...

The number of possible min-heaps containing each value from $$\left\{ {1,2,3,4,5,6,7} \right\}$$ exactly once is _____.

Consider the following functions from positive integers to real numbers : $10, \sqrt{n}, n, \log _2 n, \frac{100}{n}$. The CORRECT arrangement of the above functions in increasing...

Consider the following table : Algorithms Design Paradigms (P) Kruskal (ii) Greedy (Q) Quicksort (i) Divide and Conquer (R) Floyd–Warshall (iii) Dynamic Programming Match the algor...

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...

An operator $$delete(i)$$ for a binary heap data structure is to be designed to delete the item in the $$i$$-th node. Assume that the heap is implemented in an array and i refers t...

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given by the entry $${W_{ij}}$$ in the matrix $$W.$$ $$$W = \left...

A complete binary min-heap is made by including each integer in $$[1,1023]$$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to th...

Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$$ and $$10 \times 5,\,$$ respectively. The minimum number of...

$$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...

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 ? $$\,\,\,\,\,\,...

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

A Young tableau is a $$2D$$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $$\infty ,$$ and hence there cannot be any...

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Array Index 1 2 3 4 5 6 7 8 9 Value 40 30 20 10 15 16 17 8 4 Now consider that a value 35 is insert...

Consider two decision problems $${Q_1},{Q_2}$$ such that $${Q_1}$$ reduces in polynomial time to $$3$$-$$SAT$$ and $$3$$-$$SAT$$ reduces in polynomial time to $${Q_2}.$$ Then which...

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equation...

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

Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positive integer. Which of the following statements is/are correct...

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; }...

Given below are some algorithms, and some algorithm design paradigms. GROUP 1 GROUP 2 1. Dijkstra's Shortest Path i. Divide and Conquer 2. Floyd-Warshall algorithm to compute all p...

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 pi...

An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N insert operations, $${\left( {\log N} \right)^{1/2}}$$ delete operations, and $${\left( {\log N} \right...

Match the following: List 1 (P) Prim’s algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S) Hamiltonian circuit List 2 (i...

Consider the following array of elements. $$\,\,\,\,\,\,\,\,$$$$〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉$$ The minimum number of interchanges needed to convert it into a ma...

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$ $$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr &...

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 p...

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 su...

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 th...

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X 5 + 4X 3 + 6X + 5 for a given value of X using only one temporary variable is _____.

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

Consider the decision problem 2CNFSAT defined as follows: { $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause} For example, $$...

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....

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

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

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct V...

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...

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t 1 and t 2 be the number of comparisons made by P for the inputs {1, 2, 3, 4,...

Which of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?