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(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.
Algorithms
Binary-Trees
GATE 2014 SET 3
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
number of internal nodes in the tree
number of nodes without a right sibling in the tree
number of leaf nodes in the tree
Algorithms
GATE 2014 SET 3
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.
computer organization
GATE 2014 SET 3
There are two elements , in a group ( ,∗) such that every element in the group can be written as a product of some number of x's and 's in some order. It is known that x*x=y*y=x*y*x=y*x*y*x=e where is the identity element. The maximum number of elements in such a group is
GATE 2014 SET 3
If G is a forest with n vertices and k connected components, how many edges does G have?
GATE 2014 SET 3
The CORRECT formula for the sentence, “not all rainy days are cold” is
GATE 2014 SET 3
Consider the following relational schema: employee(empId,empName,empDept) customer(custId,custName,salesRepId,rating) salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return? SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C.salesRepId = E.empId AND(GATEC.rating<>’GOOD’);
Names of all the employees with at least one of their customers having a ‘GOOD’ rating.
Names of all the employees with at most one of their customers having a ‘GOOD’ rating.
Names of all the employees with none of their customers having a ‘GOOD’ rating.
Names of all the employees with all their customers having a ‘GOOD’ rating
GATE 2014 SET 3
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 _________
Algorithms
GATE 2019
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
Data Structures
Graphs
GATE 2008 CS
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
Data Structures
GATE 2017 SET2
Graphs
GATE 2008 CS
Consider 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?
f(n) = O(g(n)); g(n) = O(h(n))
f(n) = Ω(g(n)); g(n) = O(h(n))
g(n) = O(f(n)); h(n) = O(f(n))
h(n) = O(f(n)); g(n) = Ω(f(n))
Algorithms
Time-Complexity
GATE 2008 CS
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
Algorithms
Time-Complexity
GATE 2008 CS
G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
For every subset of k vertices, the induced subgraph has at most 2k–2 edges
The minimum cut in G has at least two edges
There are two edge-disjoint paths between every pair to vertices
There are two vertex-disjoint paths between every pair of vertices
Data Structures
Graphs
GATE 2008 CS
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
T(n) ≤ T(n/5) + T(4n/5) + n
Algorithms
Sorting
GATE 2008 CS
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
only vertices a, e, f, g, h
Algorithms
Shortest-Path
GATE 2008 CS
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
None of the above, as the tree cannot be uniquely determined
Data Structures
Binary-Trees
GATE 2008 CS
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
Data Structures
Heap-Tree
GATE 2008 CS
Let xn denote the number of binary strings of length n that contain no consecutive 0s. Which of the following recurrences does xn satisfy?
Algorithms
GATE 2008 CS
Recurrence
Let xn denote the number of binary strings of length n that contain no consecutive 0s. The value of x5 is
Algorithms
GATE 2008 CS
Recurrence