GATE CSE
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent activity by srestha
User srestha
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User srestha
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
0
answers
1
Merge sort vs heap sort
Which of the following algorithm gives best performance when items are in reverse order ? a) Merge sort. b) Heap sort.
commented
43 minutes
ago
in
Algorithms

20
views
algorithms
timecomplexity
mergesort
3
answers
2
GATE20152_1
Consider the following transaction involving two bank accounts $x$ and $y$. read(x); x:=x50; write (x); read(y); y:=y+50; write(y) The constraint that the sum of the accounts $x$ and $y$ should remain constant is that of Atomicity Consistency Isolation Durability
comment edited
6 hours
ago
in
Databases

1.2k
views
gate20152
databases
transactions
easy
3
answers
3
GATE20152_46
Consider a simple checkpointing protocol and the following set of operations in the log. (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7); (checkpoint); (start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3); ... : T3, T1; Redo: T2 Undo: T3, T1; Redo: T2, T4 Undo: none; Redo: T2, T4, T3, T1 Undo: T3, T1, T4; Redo: T2
comment edited
21 hours
ago
in
Databases

2.1k
views
gate20152
databases
transactions
normal
2
answers
4
GATE 2016251
Consider the following database schedule with two transactions $T_{1}$ and $T_{2}$. $S= r_{2}\left(X\right); r_{1}\left(X\right); r_{2} \left(Y\right); w_{1} \left(X\right); r_{1} \left(Y\right); w_{2} \left(X\ ... schedule is TRUE? $S$ is nonrecoverable. $S$ is recoverable, but has a cascading abort. $S$ does not have a cascading abort. $S$ is strict.
commented
1 day
ago
in
Databases

1.5k
views
gate20162
databases
concurrency
transactions
normal
0
answers
5
Gate 2018
for(i=1; i<=n; i++) { for(j=i; j<=n; j++){ for(k=j+1; k<=n; k++){ printf("Hello"); } } } How many times print statement is executed for n=4 and what is the time complexity?
commented
2 days
ago
in
Programming

41
views
1
answer
6
Continuity
Function f(x) = cos x is (A) Continuous only in [0, π/2] (B) Continuous only in [−π/2, π/2] (C) Continuous only in [−π, π] (D) None
commented
2 days
ago
in
Set Theory & Algebra

103
views
calculus
continuity
2
answers
7
GATE2017142
In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $TS(T_{1})$ and $TS(T_{2})$ be the timestamps of transactions $T_{1}$ and $T_{2}$ respectively. Besides, $T_{1}$ ... The database system is starvationfree, but not deadlockfree. (D) The database system is neither deadlockfree nor starvationfree.
commented
2 days
ago
in
Databases

2.1k
views
gate20171
databases
timestampordering
deadlock
normal
2
answers
8
GATE2017123
Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below: EMP EmpId EmpName DeptName 1 XYA AA 2 XYB AA 3 XYC AA 4 XYD AA 5 XYE ... DeptName, COUNT(EmpId) AS EC(DeptName, Num) FROM EMP GROUP BY DeptName) The output of executing the SQL query is _____________ .
commented
2 days
ago
in
Databases

854
views
gate20171
databases
sql
numericalanswers
3
answers
9
GATE2017141
Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus. $\left ( I ... only. (D) $\left ( I \right )$, $\left ( II \right )$ an$\left ( III \right )$.
commented
3 days
ago
in
Databases

1.2k
views
gate20171
databases
relationalcalculus
safequery
normal
1
answer
10
Algorithm doubt
Q. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is either maximum or minimum is A O(nlogn) B O(n) C O(logn) D O(1)
answer selected
4 days
ago
in
Algorithms

22
views
timecomplexity
1
answer
11
find complexity
for(i=0;i<=n;i++) for(j=i;j<=n;j++) for(k=j;k<=n;k++) S++;
edited
4 days
ago
in
Algorithms

19
views
1
answer
12
GO2017Programming130
Consider the following incomplete C function for reversing a singly linked list. node* reverse(node* trav){ if(trav>next) __________________ else { head > next = null; head = trav; } return trav; } Here, head is a global pointer pointing to ... = trav; trav>next > next = trav; trav > next = trav; trav = reverse(trav>next);
commented
4 days
ago
in
Programming

166
views
go2017programming1
programming
programminginc
linkedlists
1
answer
13
GO2017Programming128
int foo(int n) { if(n > 10000) return 1; int sum = 0, i; for( i = 0; i < n; i++) { sum += i; } return sum; } The value returned by the above function is $\Theta\left(n^2\right)$ $\Theta\left(n\right)$ $\Theta\left(1\right)$ $\Omega\left(n^2\right)$
answer selected
4 days
ago
in
Programming

163
views
go2017programming1
programming
asymptoticnotations
programminginc
1
answer
14
GO2017Programming119
Arnold is a novice in C and by mistake he typed "intt" for all usage of "int" in a C code. Which of the following statement added at the beginning of the code should fix the issue for him? typedef int intt; typedef intt int; #define intt int; #define intt int 1 and 3 2 and 4 3 and 4 1 and 4
answer selected
4 days
ago
in
Programming

101
views
go2017programming1
programming
programminginc
5
answers
15
GATE201350
The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array ... above, how many test cases will be able to capture the flaw? Only one Only two Only three All four
commented
4 days
ago
in
DS

868
views
gate2013
datastructure
arrays
normal
4
answers
16
GATE20124
Assuming P ≠ NP, which of the following is TRUE? NPcomplete = NP NPcomplete $\cap$ P = $\phi$ NPhard = NP P = NPcomplete
recategorized
5 days
ago
in
Theory of Computation

801
views
gate2012
theoryofcomputation
npcompleteness
1
answer
17
GATE2013_18
Which of the following statements are TRUE? The problem of determining whether there exists a cycle in an undirected graph is in P. The problem of determining whether there exists a cycle in an undirected graph is in NP. If a problem A is NPComplete, there exists a nondeterministic ... A. (A) 1, 2 and 3 (B) 1 and 2 only (C) 2 and 3 only (D) 1 and 3 only
recategorized
5 days
ago
in
Theory of Computation

627
views
gate2013
theoryofcomputation
npcompleteness
normal
2
answers
18
GATE200652
The median of $n$ elements can be found in $O (n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$
commented
5 days
ago
in
Algorithms

1.1k
views
gate2006
algorithms
sorting
easy
3
answers
19
GATE2014338
Consider the decision problem $2CNFSAT$ defined as follows: $$\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$$ For example, $\phi = (x1 \vee ... reduction to directed graph reachability. solvable in constant time since any input instance is satisfiable. NPhard but not NPcomplete.
retagged
5 days
ago
in
Theory of Computation

356
views
gate20143
theoryofcomputation
pnpnpcnph
easy
outofsyllabusnow
3
answers
20
GATE2014237
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=$ ___.
answer selected
5 days
ago
in
Algorithms

865
views
gate20142
algorithms
normal
numericalanswers
dynamicprogramming
3
answers
21
GATE2014138
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)?
recategorized
5 days
ago
in
Theory of Computation

536
views
gate20141
algorithms
pnpnpcnph
normal
outofsyllabusnow
6
answers
22
GATE20153_25
Consider a binary tree T that has 200 leaf nodes. Then the number of nodes in T that have exactly two children are ______.
commented
6 days
ago
in
DS

1.7k
views
gate20153
datastructure
binarytree
normal
numericalanswers
1
answer
23
GATE201522
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3SAT and 3SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.
recategorized
6 days
ago
in
Theory of Computation

604
views
gate20152
algorithms
pnpnpcnph
easy
outofsyllabusnow
3
answers
24
GATE20152_33
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for $i$ ranging from 0 to 2020? $h(i) = i^2 \text{mod } 10$ $h(i) = i^3 \text{mod } 10$ $h(i) = (11 \ast i^2) \text{mod } 10$ $h(i) = (12 \ast i^2) \text{mod } 10$
commented
6 days
ago
in
DS

1.2k
views
gate20152
datastructure
hashing
normal
3
answers
25
GATE2015236
Given below are some algorithms, and some algorithm design paradigms. 1. Dijkstra's Shortest Path i. Divide and Conquer 2. FloydWarshall algorithm to compute all pairs shortest path ii. Dynamic Programming 3. Binary search on a sorted array iii. Greedy design 4. Backtracking search on a ... 2iii, 3i, 4v 1iii, 2ii, 3i, 4iv 1iii, 2ii, 3i, 4v
commented
Aug 9
in
Algorithms

788
views
gate20152
algorithms
easy
algorithmdesigntechniques
1
answer
26
GATE20151_35
What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x [4] [3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; printf ("%u, %u, %u, x + 3, * (x + 3), * (x + 2) + 3); } 2036, 2036, 2036 2012, 4, 2204 2036, 10, 10 2012, 4, 6
commented
Aug 9
in
Programming

2.4k
views
gate20151
programming
programminginc
normal
4
answers
27
GATE20151_40
An algorithm performs (log N)1/2 find operations , N insert operations, (log N)1/2 delete operations, and (log N)1/2 decreasekey operations on a set of data items with keys drawn from a linearly ordered set . ... to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min  heap Sorted array Sorted doubly linked list
commented
Aug 9
in
Algorithms

2.2k
views
gate20151
algorithms
datastructure
normal
timecomplexity
1
answer
28
Recursive tree
If T(n) = T(n/4) + T(n/2) +n2 , then using recursion tree method
commented
Aug 8
in
Algorithms

52
views
3
answers
29
#Number of Elements in Circular Queues and Simple Queues #Doubt
answer selected
Aug 8
in
DS

67
views
queues
circularqueue
1
answer
30
How many vertices and how many edges do these graphs have? a) Kn b) Cn c) Wn d) Km,n e) Qn
commented
Aug 8
in
Graph Theory

411
views
3
answers
31
GATE 2016111
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
commented
Aug 8
in
Algorithms

2.3k
views
gate20161
algorithms
graphalgorithms
normal
numericalanswers
2
answers
32
GATE1994_1.11
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, nonzero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, ... is: $i+j$ $i+j1$ $(j1)+\frac{i(i1)}{2}$ $i+\frac{j(j1)}{2}$
commented
Aug 7
in
DS

1.4k
views
gate1994
datastructure
arrays
normal
3
answers
33
GATE2004IT42
Using a 4bit 2's complement arithmetic, which of the following additions will result in an overflow? 1100 + 1100 0011 + 0111 1111 + 0111 i only ii only iii only i and iii only
commented
Aug 7
in
Digital Logic

560
views
gate2004it
digitallogic
numberrepresentation
normal
4
answers
34
TIFR2012B15
Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$. Let $u_{3}$ ... For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.
commented
Aug 6
in
DS

280
views
tifr2012
datastructure
trees
3
answers
35
GATE2017113
Consider the following C code: #include<stdio.h> int *assignval (int *x, int val) { *x = val; return x; } void main () { int *x = malloc(sizeof(int)); if (NULL == x) return; x = assignval (x,0); ... not as shown. (C) compiles successfully but execution may result in dangling pointer. (D) compiles successfully but execution may result in memory leak.
commented
Aug 5
in
Programming

1.5k
views
gate20171
programminginc
programming
1
answer
36
GATE19893ixa
Answer the following: Which one of the following statements (s) is/are FALSE? Overlaying is used to run a program, which is longer than the address space of the computer. Optimal binary search tree construction can be performed efficiently ... of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
commented
Aug 4
in
DS

195
views
normal
gate1989
overlay
binarytree
graphsearch
1
answer
37
GATE19887iii
Consider the tree given in the below figure, insert 13 and show the new balance factors that would arise if the tree is not rebalanced. Finally, carry out the required rebalancing of the tree and show the new tree with the balance factors on each mode.
answered
Aug 4
in
DS

51
views
gate1988
normal
descriptive
datastructure
2
answers
38
Self Doubt in linked list
Which of the following operations is performed more efficiently by doubly linked list than by singly linked list? (a) Deleting a node whose location in given (b) Searching of an unsorted list for a given item (c) Inverting a node after the node ... q>next>next; free(q>next); it is easy to delete in singly than in doubly. crct me?
commented
Aug 4
in
Algorithms

106
views
datastructure
linkedlists
2
answers
39
GATE1997_4.7
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as ... sequence of operations, the keys chosen are in nonincreasing order nondecreasing order strictly increasing order strictly decreasing order
commented
Aug 4
in
DS

1.2k
views
gate1997
datastructure
stack
normal
3
answers
40
GATE20001.14
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right subtrees, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree? (1 2 (4 5 6 7)) (1 (2 3 4) 5 6) 7) (1 (2 3 4) (5 6 7)) (1 (2 3 NULL) (4 5))
commented
Aug 3
in
DS

602
views
gate2000
datastructure
binarytree
easy
24,796
questions
31,866
answers
73,707
comments
30,011
users