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?
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?
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?
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 ______
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.
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?
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)?
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
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 _______.
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 ________.
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)___________.
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
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 __ .
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 _________.
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:
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?
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 ___________.
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 _______.
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 _______.
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
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
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 ______.
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.
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?
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 _______.
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?
