Algorithms GATE PYQ Solutions

Algorithms GATE PYQ Solutions

Q1➡ | GATE CSE 2021 Set-1
Consider the following three Functions

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
i ➥ f2, f1, f3
ii ➥ f3, f2, f1
iii ➥ f2, f3, f1
iv ➥ f1, f2, f3

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeAsymptotic Complexity Help-Line

Q2➡ | GATE CSE 2021 Set-1
Consider the following array:

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?
i ➥ Quicksort using the last element as pivot
ii ➥ Selection sort
iii ➥ Mergesort
iv ➥ Insertion sort

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q3➡ | GATE CSE 2021 Set-1
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?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Time Complexity Help-Line

Q4➡ | GATE CSE 2021 Set-1
Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ______

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q5➡ | GATE CSE 2021 Set-1
Consider the following recurrence relation.

Which one of the following options is correct?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q6➡ | GATE CSE 2021 Set-1
Define Rn to be the maximum amount earned by cutting a rod of length n metres into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price 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 R7?
i ➥ R7 cannot be achieved by a solution consisting of three pieces.
ii ➥ R7 is achieved by three different solutions.
iii ➥ R7=19
iv ➥ R7=18

Show Answer With Best Explanation

Answer: II, IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDynamic Programming Help-Line

Q7➡ | GATE CSE 2021 Set-2
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q8➡ | GATE CSE 2021 Set-2
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 letter must not be a prefix of the code assigned to the other letter.
2. 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?
i ➥ 25
ii ➥ 21
iii ➥ 30
iv ➥ 23

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHamming code Help-Line

Q9➡ | GATE CSE 2021 Set-2
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

Which one of the following options is correct about the recurrence T(n)?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMaster Theorem Help-Line

Q10➡ | GATE CSE 2020
For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.
Then T(n) is
i ➥ θ(logab n)
ii ➥ θ(logb loga n)
iii ➥ θ(loga logb n)
iv ➥ θ(log2 log2 n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRecurrences Help-Line

Q11➡ | GATE CSE 2020
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 of determining if T is still an MST of the resultant graph is
i ➥ θ(|E||V|)
ii ➥ θ(|E|+|V|)
iii ➥ θ(|V|)
iv ➥ θ(|E| log|V|)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q12➡ | GATE CSE 2020
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is _______.

Show Answer With Best Explanation

Answer: 99
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q13➡ | GATE CSE 2019
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 ________.

Show Answer With Best Explanation

Answer: 0.08
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting Help-Line

Q14➡ | GATE CSE 2019
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(i,j)=
Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)___________.

Show Answer With Best Explanation

Answer: 29
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDynamic ProgrammingHelp-Line

Q15➡ | GATE CSE 2019
There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An 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 A1, A2, …, An is
i ➥ O(n2)
ii ➥ Ω(n2 log n)
iii ➥ O(n)
iv ➥ O(n log n)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting Help-Line

Q16➡ | GATE CSE 2018
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 __ .

Show Answer With Best Explanation

Answer: 16
Explanation: Upload Soon

More DiscussionExplanation On YouTube0/1-Knapsack Help-Line

Q17➡ | GATE CSE 2018
Consider the following undirected graph G:

Choose a value for 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 _________.

Show Answer With Best Explanation

Answer: 4
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum-Spanning-Tree Help-Line

Q18➡ | GATE CSE 2017 Set-1
Consider the following table:

Match the algorithm to design paradigms they are based on:
i ➥ (P)↔(ii), Q↔(i), (R)↔(iii)
ii ➥ (P)↔(ii), Q↔(iii), (R)↔(i)
iii ➥ (P)↔(i), Q↔(ii), (R)↔(iii)
iv ➥ (P)↔(iii), Q↔(i), (R)↔(ii)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Design paradigms Help-Line

Q19➡ | GATE CSE 2017 Set-1
Consider the following functions from positives integers to real numbers

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeAsymptotic ComplexityHelp-Line

Q20➡ | GATE CSE 2017 Set-1
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum 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?
i ➥ (II) only
ii ➥ (I) only
iii ➥ neither (I) nor (II)
iv ➥ both (I) and (II)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q21➡ | GATE CSE 2017 Set-1
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 ___________.

Show Answer With Best Explanation

Answer: 5
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSearching Help-Line

Q22➡ | GATE CSE 2017 Set-2
Match the algorithms with their time complexities:
i ➥ P→(iv), Q→(iii), R→(i), S→(ii)
ii ➥ P→(iv), Q→(iii), R→(ii), S→(i)
iii ➥ P→(iii), Q→(iv), R→(ii), S→(i)
iv ➥ P→(iii), Q→(iv), R→(i), S→(ii)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q23➡ | GATE CSE 2017 Set-2
Consider the recurrence function

Then T(n) in terms of Θ notation is
i ➥ Θ(n)
ii ➥ Θ(√n)
iii ➥ Θ(log⁡n)
iv ➥ Θ(log⁡log⁡n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Time Complexity Help-Line

Q24➡ | GATE CSE 2017 Set-2
Consider the following C function.

Time complexity of fun in terms of Θ notation is
i ➥ Θ(n2 logn)
ii ➥ Θ(n log⁡n)
iii ➥ Θ(n2)
iv ➥ Θ(n√n)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q25➡ | GATE CSE 2017 Set-2
A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is _______.

Show Answer With Best Explanation

Answer: 225
Explanation: Upload Soon

More DiscussionExplanation On YouTubeHuffman Coding Help-Line

Q26➡ | GATE CSE 2016 Set-1
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
i ➥ Θ(nlogn), Θ(nlogn), and Θ(n2)
ii ➥ Θ(n2 ), Θ(n2 ), and Θ(nlogn)
iii ➥ Θ(n2), Θ(nlogn), and Θ(nlogn)
iv ➥ Θ(n2), Θ(nlogn), and Θ(n2)

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting Help-Line

Q27➡ | GATE CSE 2016 Set-1
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 _______.

Show Answer With Best Explanation

Answer: 7
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning Tree Help-Line

Q28➡ | GATE CSE 2016 Set-1
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
i ➥ neither I nor II
ii ➥ both I and II
iii ➥ II only
iv ➥ I only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning TreeHelp-Line

Q29➡ | GATE CSE 2016 Set-2
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 Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
i ➥ I and II only
ii ➥ I and III only
iii ➥ II and IV only
iv ➥ I and IV only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting Help-Line

Q30➡ | GATE CSE 2016 Set-2
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
i ➥ Greedy paradigm.
ii ➥ Divide-and-Conquer paradigm.
iii ➥ Dynamic Programming paradigm.
iv ➥ Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFloyd Warshall Algorithm Help-Line

Q31➡ | GATE CSE 2016 Set-2
Let A1, A2, A3 and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively.

Show Answer With Best Explanation

Answer: 1500
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMatrix Chain MultiplicationHelp-Line

Q32➡ | GATE CSE 2016 Set-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 upto two decimal positions) of α
is ______.

Show Answer With Best Explanation

Answer: 2.2 to 2.4
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime ComplexityHelp-Line

Q33➡ | GATE CSE 2015 Set-1
i ➥ P-iii, Q-ii, R-iv, S-i
ii ➥ P-i, Q-ii, R-iv, S-iii
iii ➥ P-ii, Q-iii, R-iv, S-i
iv ➥ P-ii, Q-i, R-iii, S-iv

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Matching Help-Line

Q34➡ | GATE CSE 2015 Set-1
Which 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.
i ➥ T(n) = 2T(n/2) + cn
ii ➥ T(n) = T(n – 1) + T(1) + cn
iii ➥ T(n) = 2T(n – 1) + cn
iv ➥ T(n) = T(n/2) + cn

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Quick Sort Help-Line

Q35➡ | GATE CSE 2015 Set-1
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 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?
i ➥ Unsorted array
ii ➥ Min-heap
iii ➥ Sorted array
iv ➥ Sorted doubly linked list

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q36➡ | GATE CSE 2015 Set-1
The graph shown below 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 _______.

Show Answer With Best Explanation

Answer: 69
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning Tree Help-Line

Q37➡ | GATE CSE 2015 Set-2
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
i ➥ Q1 is in NP, Q2 in NP hard
ii ➥ Q1 is in NP, Q2 is NP hard
iii ➥ Both Q1 and Q2 are in NP
iv ➥ Both Q1 and Q2 are NP hard

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeComplexity Help-Line

Q38➡ | GATE CSE 2015 Set-2
Given below are some algorithms, and some algorithm design paradigms

Match the above algorithms on the left to the corresponding design paradigm they follow Codes:
i ➥ 1-i, 2-iii, 3-i, 4-v.
ii ➥ 1-iii, 2-iii, 3-i, 4-v.
iii ➥ 1-iii, 2-ii, 3-i, 4-iv.
iv ➥ 1-iii, 2-ii, 3-i, 4-v.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Algorithms Paradigm Help-Line

Q39➡ | GATE CSE 2015 Set-2
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 kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n

The missing argument lists are respectively
i ➥ (a, left_end, k) and (a + left_end + 1, n – left_end – 1, k – left_end – 1)
ii ➥ (a, left_end, k) and (a, n – left_end – 1, k – left_end – 1)
iii ➥ (a + left_end + 1, n – left_end – 1, k – left_end – 1) and (a, left_end, k)
iv ➥ (a, n – left_end – 1, k – left_end – 1) and (a, left_end, k)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubePartitioning Algorithm Help-Line

Q40➡ | GATE CSE 2015 Set-3
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?
i ➥ 256
ii ➥ 512
iii ➥ 1024
iv ➥ 2048

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMerge Sort Help-Line

Q41➡ | GATE CSE 2015 Set-3
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?
i ➥ 256
ii ➥ 512
iii ➥ 1024
iv ➥ 2048

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMerge Sort Help-Line

Q42➡ | GATE CSE 2015 Set-3
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P
i ➥ II only
ii ➥ III only
iii ➥ I and IV only
iv ➥ I only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Complexity Class Help-Line

Q43➡ | GATE CSE 2015 Set-3
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__________.

Show Answer With Best Explanation

Answer: 995
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSpanning Tree Help-Line

Q45➡ | GATE CSE 2015 Set-3
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) = Ω(g(n))
i ➥ Only I
ii ➥ Only II
iii ➥ Both I and II
iv ➥ Neither I nor II

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube ComplexityHelp-Line

Q46➡ | GATE CSE 2014 Set-1
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is .

Show Answer With Best Explanation

Answer: 12
Explanation: Upload Soon

More DiscussionExplanation On YouTube Algorithms Help-Line

Q47➡ | GATE CSE 2014 Set-1
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 Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeP-NP ProblemHelp-Line

Q48➡ | GATE CSE 2014 Set-1
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is .

Show Answer With Best Explanation

Answer: 147.1 To 148.1
Explanation: Upload Soon

More DiscussionExplanation On YouTubePartitioning Algorithm Help-Line

Q49➡ | GATE CSE 2014 Set-2
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
i ➥ Θ(n)
ii ➥ Θ(n log n)
iii ➥ Θ(n2)
iv ➥ Θ(log n)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube recurrence relationHelp-Line

Q50➡ | GATE CSE 2014 Set-2
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 =________.

Show Answer With Best Explanation

Answer: 34
Explanation: Upload Soon

More DiscussionExplanation On YouTube Dynamic Programming Help-Line

Q51➡ | GATE CSE 2014 Set-2
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 .

Show Answer With Best Explanation

Answer: 358
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGreedy AlgorithmHelp-Line

Q52➡ | GATE CSE 2014 Set-3
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
i ➥ O(n2)
ii ➥ O(n log n)
iii ➥ Θ(n log⁡n)
iv ➥ O(n3)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeSorting Help-Line

Q53➡ | GATE CSE 2014 Set-3
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 < 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_______________.

Show Answer With Best Explanation

Answer: 150
Explanation: Upload Soon

More DiscussionExplanation On YouTube Algorithms Help-Line

Q54➡ | GATE CSE 2014 Set-3
Consider the decision problem 2CNFSAT defined as follows:
{ 0 | 0 is a satisfiable propositional formula in CNF with at most two literals per clause }
For example, 0 = (x1 ˅ x2)⋀(x1 ˅ x3)⋀(x2 ˅ x4) is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is____.
i ➥ NP-Complete.
ii ➥ solvable in polynomial time by reduction to directed graph reachability.
iii ➥ solvable in constant time since any input instance is satisfiable.
iv ➥ NP-hard, but not NP-complete.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeP-NP ProblemHelp-Line

Q55➡ | GATE CSE 2013
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
i ➥ O(log n)
ii ➥ O(n)
iii ➥ O(n log n)
iv ➥ O(n2)

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Sorting Help-Line

Q56➡ | GATE CSE 2013
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?
i ➥ O(1)
ii ➥ O(log n)
iii ➥ O(n)
iv ➥ O(n log n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Sorting Help-Line

Q57➡ | GATE CSE 2013
Which of the following statements are TRUE?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there exists a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
i ➥ 1, 2 and 3
ii ➥ 1 and 2 only
iii ➥ 2 and 3 only
iv ➥ 1 and 3 only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeNP-Complete Help-Line

Q58➡ | GATE CSE 2013
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
i ➥ Θ(n2)
ii ➥ Θ(n2 log n)
iii ➥ Θ(n3)
iv ➥ Θ(n3 log n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeBellman – Ford Help-Line

Q59➡ | GATE CSE 2013
The number of elements that can be sorted in Θ(log n) time using heap sort is
i ➥ Θ(1)
ii ➥ Θ(√log⁡n)
iii ➥ Θ (log⁡n/log⁡log⁡n)
iv ➥ Θ(log n)

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Sorting Help-Line

Q60➡ | GATE CSE 2012
Assuming P ≠ NP, which of the following is TRUE?
i ➥ NP-complete = NP
ii ➥ NP-complete ∩ P = ∅
iii ➥ NP-hard = NP
iv ➥ P = NP-complete

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Complexity Class Help-Line

Q61➡ | GATE CSE 2012
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
i ➥ T(n) = 2T(n – 2) + 2
ii ➥ T(n) = 2T(n – 1) + n
iii ➥ T(n) = 2T(n/2) + 1
iv ➥ T(n) = 2T(n – 1) + 1

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRecursion Help-Line

Q62➡ | GATE CSE 2012
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?
i ➥ A(n) = Ω (W(n))
ii ➥ A(n) = Θ (W(n))
iii ➥ A(n) = O (W(n))
iv ➥ A(n) = o (W(n))

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTime Complexity Help-Line

Q63➡ | GATE CSE 2012
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?
i ➥ T’ = T with total weight t’ = t2
ii ➥ T’ = T with total weight t'<t2
iii ➥ T’ ≠ T but total weight t’ = t2
iv ➥ None of the above

Show Answer With Best Explanation

Answer: Marks to All
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMinimum Spanning Tree Help-Line

Q64➡ | GATE CSE 201GATE CSE 2012
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