The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Answers by prateekdwv
User prateekdwv
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User prateekdwv
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
+7
votes
1
GATE20184
Let $\oplus$ and $\odot$ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT? $\overline{P \oplus Q} = P \odot Q$ $\overline{P} \oplus Q = P \odot Q$ $\overline{P} \oplus \overline{Q} = P \oplus Q$ $P \oplus \overline{P} \oplus Q = ( P \odot \overline{P} \odot \overline{Q})$
answered
Feb 14, 2018
in
Digital Logic

2.2k
views
gate2018
digitallogic
normal
booleanalgebra
+2
votes
2
TIFR2018B1
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$
answered
Dec 11, 2017
in
Combinatory

559
views
tifr2018
modulararithmetic
permutationandcombination
+10
votes
3
TIFR2017A15
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following reccurence: $ T(a, b) = T \biggl( \frac{a}{2}, b \biggl) +T\biggl( a, \frac{b}{2} \biggl) \quad \quad \text{ if } a, b \geq 2$ ... $\begin{pmatrix} r+s \\ r \end{pmatrix}$ $2^{rs}$ if $r \geq s$, otherwise $2^{sr}$
answered
Dec 9, 2017
in
Algorithms

546
views
tifr2017
algorithms
recurrence
+4
votes
4
TIFR2010B24
Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$. x, y, u, v:= X, Y, Y, X; While (x ≠ y) do if (x > y) then x, v := x  y, v + u; else if (y > x) then y, u:= y  x, u + v; od; ... $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$. The program does none of the above.
answered
Dec 6, 2017
in
Algorithms

517
views
tifr2010
algorithms
identifyfunction
+2
votes
5
Log formula related doubt.
Confusion regarding these log representations. 1.(logn)2 2.log2n 3.log(logn) 4.log(n)2 which of these are equal . Also explain meaning of each one.(Pls provide any source if possible).
answered
Dec 1, 2017
in
Algorithms

102
views
algorithms
timecomplexity
0
votes
6
Non deterministic finite
answered
Nov 29, 2017
in
Theory of Computation

56
views
+1
vote
7
#programming
#include<stdio.h> main() { int i=511; char *ptr=(char *)&i; printf("%d",*ptr); } explain...how output came 1????
answered
Sep 24, 2017
in
Programming

84
views
0
votes
8
LAnguage
L = { a^m b^n b^k d^l (n+k)=odd only if m=l; m, n, k , l>0}. Which is true? a)CFL but not DCFL b)regular but not CFL c)DCFL but not regular d)none
answered
Sep 19, 2017
in
Theory of Computation

71
views
+1
vote
9
PROGRAMMING
answered
Sep 18, 2017
in
Programming

109
views
programminginc
output
+1
vote
10
time complexity
If F(n) = (log n)n then, is F(n) = O(n2) true? Also, what about F(n) = $\Theta$(n2)
answered
Sep 11, 2017
in
Algorithms

93
views
timecomplexity
algorithms
asymptoticnotations
+4
votes
11
Peter Linz Edition 4 Exercise 2.1 Question 24 (Page No. 49)
Let us define an operation $truncate$, which removes the rightmost symbol from any string. For example, $truncate (aaaba)$ is $aaab$. The operation can be extended to languages by $truncate (L)= $ {$truncate(w):w ∈ L$} Show how, ... From this, prove that if $L$ is a regular language not containing $λ$, then $truncate (L)$ is also regular.
answered
Sep 8, 2017
in
Theory of Computation

482
views
peterlinz
theoryofcomputation
finiteautomata
+3
votes
12
TOC  Doubt
Consider these statements: S1: If a language is infinite, it has to be nonRegular. S2: Let L be any language. $(\overline{L})^{*} \neq (\overline{L^{*}})$ (a) Both are True (c) S1 → True, S2 → False (b) Both are False (d) S1 → False, S2 → True
answered
Sep 7, 2017
in
Theory of Computation

172
views
regularlanguages
regular
theoryofcomputation
0
votes
13
Mapping Reducible
A={<M,w> M is a TM that accepts w} B=Ʃ* Is A Mapping reducible to B? http://theory.stanford.edu/~trevisan/cs15412/reductions3.pdf
answered
Sep 6, 2017
in
Theory of Computation

251
views
theoryofcomputation
+1
vote
14
C Program 2
#include<stdio.h> int f(int a){ a > 20 ? return 10: return 20; } int main(){ int b=fun(20); return 0; } what will be the output of this program ?
answered
Aug 27, 2017
in
Programming

285
views
programminginc
+2
votes
15
identities of regular expression
how $\phi \cdot R = R \cdot \phi = \phi$ ? where R is regular expression, and why is $\phi^* is $\epsilon$
answered
Aug 18, 2017
in
Theory of Computation

957
views
+3
votes
16
Proposition
X posed many puzzles about an island that has two kinds of inhabitants knights who always tells the truth, and their opposite knaves, who always lie. You encounter two people A and B. What are A and B if A says 'B is a knight' and B says 'two of us are of opposite types'?
answered
Aug 13, 2017
in
Mathematical Logic

94
views
+3
votes
17
Array
A tridiagonal matrix [2..2,5..9] is stored in row major order with base address 301.what is the address of data [0][8] if nonzero elements are stored??
answered
Aug 9, 2017
in
DS

460
views
+1
vote
18
TOC Languages Difference
Given two languages L1 =$a^{*}(ab+a)$ L2=$a^{+}(ab+a)$ What is L1L2?
answered
Aug 4, 2017
in
Theory of Computation

113
views
theoryofcomputation
regularexpressions
+1
vote
19
first order logic
Is it always the case that implication comes with universal quantifier and conjunction comes with existential quantifier?
answered
Jun 7, 2017
in
Mathematical Logic

144
views
firstorderlogic
mathematicallogic
discretemathematics
+2
votes
20
C Programming
answered
Jun 2, 2017
in
Programming

157
views
programminginc
output
+11
votes
21
ISRO201724
When two $n$bit binary numbers are added the sum will contain at the most $n$ bits $n + 2$ bits $n + 3$ bits $n + 1$ bits
answered
May 8, 2017
in
Digital Logic

3.8k
views
isro2017
digitallogic
adder
+21
votes
22
GATE20095, ISRO201757
$(1217)_8$ is equivalent to $(1217)_{16}$ $(028F)_{16}$ $(2297)_{10}$ $(0B17)_{16}$
answered
May 7, 2017
in
Digital Logic

2.4k
views
gate2009
digitallogic
numberrepresentation
isro2017
+4
votes
23
Stack Doubt
The question basically says no. of different outputs produced for given sequence of input (1,2,...,n) I thought in terms of push  pop pairs but cant arrive at the answer @arjun sir , @bikram sir
answered
Jan 25, 2017
in
Programming

190
views
stack
datastructures
0
votes
24
GRAPH_degree seq
Is there any simple graph with degree sequence <1,1,1,1,2,2,3,3,3,3>
answered
Jan 20, 2017
in
Graph Theory

53
views
0
votes
25
Ace Test Series: Databases  Transactions
Consider the following transaction T1 T2 T3 R(A) W(A) commit W(A) commit W(A) commit Which of the following is TRUE regarding above transaction? (1) Transaction is view serializable since it has a viewequivalent serial schedule < T1, ... schedule < T3, T2 T1 > (4) Transaction is not serializable Your Answer: 3 Correct Answer: 1 Status: incorrect
answered
Jan 19, 2017
in
Databases

108
views
databases
transactions
acetestseries
+2
votes
26
Number of possible conflict equivalent serial schedules
"Number of possible conflict equivalent serial schedules to some nonserial schedule is total number of topological sorts of its precedence graph." I haven't read this method anywhere yet but I found it by myself while ... answer, please can anyone refer me to standard(reference) books about this!(I found that,too but failed)
answered
Jan 17, 2017
in
Databases

359
views
topologicalsort
databases
concurrency
conflictserializable
algorithms
+2
votes
27
If L is any language accepted by DPDA with stack containing only one symbol. Then L can be
answered
Jan 14, 2017
in
Theory of Computation

390
views
theoryofcomputation
contextfreelanguages
pushdownautomata
+2
votes
28
Quick Sort
Suppose we have a O(nlogn) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified ... quick sort. Average case time complexity of modified quick sort is same as that of original quick sort. None of the above
answered
Jan 9, 2017
in
Algorithms

780
views
+4
votes
29
Virtual Gate Test Series: Theory Of Computation  DFA
Number of states in the $\text{DFA}$ accepting the language $L=\{a^{n}b^{n}1\leq n\leq 3\}$ over $\sum=\{a,b\}.$
answered
Jan 9, 2017
in
Theory of Computation

138
views
theoryofcomputation
finiteautomata
numberofstates
virtualgatetestseries
+2
votes
30
Reader Writer
answered
Jan 8, 2017
in
Operating System

71
views
os
+2
votes
31
ADA Testbook
What is the time complexity to count the number of leaf nodes in a tree? I am getting O(nlogn) but answer is O(n) please anybody explain in detail
answered
Dec 23, 2016
in
Algorithms

104
views
+1
vote
32
is null production allowed in all type of grammar
is null production allowed in all type of grammar
answered
Aug 5, 2016
in
Theory of Computation

390
views
–2
votes
33
TOC
What wud be THE DFA for the following expression ? 0*1* + 1*0*
answered
Jul 26, 2016
in
Theory of Computation

227
views
0
votes
34
SHUFFLE PROPERTY OVER REGULAR LANGUAGES
The shuffle of two strings w and x is the set of all strings that one can get by interleaving the positions of w and x in any way.More precisely,shuffle(w,x) is the set of strings z such that 1)Each position of z canbe assigned to w ... {01110,01101,10110,01011,11001,11010}. Q) Show that if L1 and L2 are both regular languages,then so is shuffle(L1,L2)
answered
Jun 21, 2016
in
Theory of Computation

156
views
pushdownautomata
+11
votes
35
ISRO200872
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list? Deleting a node whose location is given Searching an unsorted list for a given item Inserting a node after the node with a given location Traversing the list to process each node
answered
Jun 13, 2016
in
DS

3.3k
views
isro2008
datastructures
linkedlists
+35
votes
36
GATE200362
In a permutation \(a_1 ... a_n\), of $n$ distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. . . n\) with at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)
answered
Apr 26, 2016
in
Algorithms

5.7k
views
gate2003
algorithms
sorting
normal
+5
votes
37
How to solve reccurence relation of type t(n)=t(n/5)+t(7n/10)+n ?plz specify in detail.
answered
Apr 26, 2016
in
Algorithms

2k
views
+1
vote
38
Solve recurrence using Master theorem
$T(a)=0 \hspace{0.2cm} if \hspace{0.2cm} a=1$ $T(a)=2T(a/2) + ak \hspace{0.2cm} if \hspace{0.2cm} a=2^{p}, p>0$ where $a=\frac{n}{k}$ Answer: $\Theta (n \log (\frac{n}{k}))$, This is while (n/k) is power of 2. How can I solve it using master theorem?
answered
Apr 8, 2016
in
Algorithms

309
views
mastertheorem
algorithms
timecomplexity
+2
votes
39
How to solve this using recursion tree method
answered
Mar 21, 2016
in
Algorithms

195
views
algorithms
recurrence
Page:
1
2
next »
50,737
questions
57,275
answers
198,154
comments
104,823
users