The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged descriptive
0
votes
0
answers
1
ISI2018PCBB10
Consider two $n \times 1$ vectors $u$ and $v$ , stored as table $U(ind,val)$ and $V(ind,val)$ with the same schema A row $(i,u_i)$ of table $U$ specifies the $i^{th}$ element of vector $u$ has value $u_i$ (similarly for $v$, respectively). ... $u + v$ of the two vectors $u$ and $v$. Explain your solution.
asked
May 12
in
Databases
by
akash.dinkar12
Boss
(
40.6k
points)

14
views
isi2018pcbb
databases
relationalalgebra
sql
descriptive
0
votes
0
answers
2
ISI2018PCBB9
The data link layer uses a fixedsize sliding window protocol, where the window size for the connection is equal to twice the bandwidthdelay product of the network path. Consider the following three scenarios, in each of which only the given parameter changes as specified (no ... minimum value of the round trip time $R$ increases to $1.8R$; the window size $W$ decreases to $W/3$
asked
May 12
in
Computer Networks
by
akash.dinkar12
Boss
(
40.6k
points)

20
views
isi2018pcbb
computernetworks
datalinklayer
descriptive
0
votes
0
answers
3
ISI2018PCBB8
Consider a $5$ ... $(in\ ns)$ needed to execute the program.
asked
May 12
in
Operating System
by
akash.dinkar12
Boss
(
40.6k
points)

17
views
isi2018pcbb
coandarchitecture
pipelining
descriptive
0
votes
0
answers
4
ISI2018PCBB7
A context switch from a process $P_{old}$ to a process $P_{new}$ consists of the following steps: Step I:saving the context of $P_{old}$; Step II: running the scheduling algorithm to pick $P_{new}$; Step III: restoring the saved context of $P_{new}$. Suppose Steps ... in the order $P_1, P_2, . . . , P_k;$ each process requires exactly one CPU burst of $20$ms and no I/O burst.
asked
May 12
in
Operating System
by
akash.dinkar12
Boss
(
40.6k
points)

9
views
isi2018pcbb
operatingsystem
processschedule
descriptive
0
votes
0
answers
5
ISI2018PCBB6
The following function computes an array $SPF$, where, for any integer $1 < i < 1000$, $SPF[i]$ is the smallest prime factor of $i$. For example, $SPF[6]$ is $2$, and $SPF[11]$ is $11$. There are five missing parts in the following code, commented as $/* Blank */$. For each of them ... < 1000; j+= i) { /* Blank 4 */ if (SPF[j] == j) { SPF[j] = _____; /* Blank 5 */ } } } } }
asked
May 12
in
Programming
by
akash.dinkar12
Boss
(
40.6k
points)

7
views
isi2018pcbb
programming
descriptive
0
votes
0
answers
6
ISI2018PCBB5
Consider a maxheap of $n$ distinct integers, $n ≥ 4$, stored in an array $\mathcal{A}[1 . . . n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.
asked
May 12
in
Algorithms
by
akash.dinkar12
Boss
(
40.6k
points)

9
views
isi2018pcbb
algorithms
algorithmdesign
heap
descriptive
+1
vote
1
answer
7
ISI2018PCBB4
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person is initially ... returns to the base of the staircase after the final step. Show that $L$ is not regular Write a context free grammar for accepting $L$
asked
May 12
in
Theory of Computation
by
akash.dinkar12
Boss
(
40.6k
points)

15
views
isi2018pcbb
theoryofcomputation
contextfreegrammars
descriptive
0
votes
1
answer
8
ISI2018PCBB3
An $n$variable Boolean function $f:\{0,1\}^n \rightarrow \{0,1\} $ is called symmetric if its value depends only on the number of $1’s$ in the input. Let $\sigma_n $ denote the number of such functions. Calculate the value of $\sigma_4$. Derive an expression for $\sigma_n$ in terms of $n$.
asked
May 12
in
Set Theory & Algebra
by
akash.dinkar12
Boss
(
40.6k
points)

10
views
isi2018pcbb
engineeringmathematics
discretemathematics
settheory&algebra
functions
descriptive
0
votes
1
answer
9
ISI2018PCBB2
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_n$ by solving your recurrence.
asked
May 12
in
Algorithms
by
akash.dinkar12
Boss
(
40.6k
points)

19
views
isi2018pcbb
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
10
ISI2018PCBB1
Consider an array of length n consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only a constant amount of extra space.
asked
May 12
in
Algorithms
by
akash.dinkar12
Boss
(
40.6k
points)

9
views
isi2018pcbb
algorithms
algorithmdesign
descriptive
0
votes
1
answer
11
ISI2018PCBA4
Let $A$ and $B$ are two nonempty finite subsets of $\mathbb{Z}$, the set of all integers. Define $A+B=\{a+b:a\in A,b\in B\}$.Prove that $A+B\geq A +B 1 $, where $S$ denotes the cardinality of finite set $S$.
asked
May 12
in
Set Theory & Algebra
by
akash.dinkar12
Boss
(
40.6k
points)

16
views
isi2018pcba
engineeringmathematics
discretemathematics
settheory&algebra
descriptive
+1
vote
0
answers
12
ISI2018PCBA3
Let $n,r\ $and$\ s$ be positive integers, each greater than $2$.Prove that $n^r1$ divides $n^s1$ if and only if $r$ divides $s$.
asked
May 12
in
Numerical Ability
by
akash.dinkar12
Boss
(
40.6k
points)

9
views
isi2018pcba
generalaptitude
numericalability
descriptive
0
votes
0
answers
13
ISI2018PCBA2
Let there be a pile of $2018$ chips in the center of a table. Suppose there are two players who could alternately remove one, two or three chips from the pile. At least one chip must be removed, but no more than three chips can be removed in a ... game, that is, whatever moves his opponent makes, he can always make his moves in a certain way ensuring his win? Justify your answer.
asked
May 12
in
Numerical Ability
by
akash.dinkar12
Boss
(
40.6k
points)

6
views
isi2018pcba
generalaptitude
numericalability
logicalreasoning
descriptive
+1
vote
1
answer
14
ISI2018PCBA1
Consider a $n \times n$ matrix $A=I_n\alpha\alpha^T$, where $I_n$ is the $n\times n$ identity matrix and $\alpha$ is an $n\times 1$ column vector such that $\alpha^T\alpha=1$.Show that $A^2=A$.
asked
May 12
in
Linear Algebra
by
akash.dinkar12
Boss
(
40.6k
points)

33
views
isi2018pcba
engineeringmathematics
linearalgebra
matrices
descriptive
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give contextfree grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w w contains at least three 1's}}$ $\text{{w w starts and ends with the same symbol}}$ ... $\text{{$ww=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

16
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
descriptive
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 2 Question 3 (Page No. 155)
Answer each part for the following contextfree grammar $G.$ $R\rightarrow XRX  S$ $S\rightarrow aT b  bT a$ $T\rightarrow XT X  X  \epsilon$ $X\rightarrow a  b$ What are the variables of $G?$ What are the terminals ... $:S\overset{*}{\Rightarrow}\epsilon.$ Give a description in English of $L(G).$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

20
views
michaelsipser
theoryofcomputation
contextfreegrammars
descriptive
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 1 Question 73 (Page No. 93)
Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

10
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
descriptive
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $s < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $s < k1k2.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{www\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

19
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 1 Question 67 (Page No. 93)
Let the rotational closure of language $A$ be $RC(A) = \{yx xy ∈ A\}.$ Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$ Show that the class of regular languages is closed under rotational closure.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

4
views
michaelsipser
theoryofcomputation
regularlanguages
rotationalclosureoflanguage
descriptive
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 1 Question 66 (Page No. 93)
A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w_{1})f(w_{2})...f(w_{n}),$ ... Is it a DFA in every case$?$ Show, by giving an example, that the class of nonregular languages is not closed under homomorphism.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

13
views
michaelsipser
theoryofcomputation
finiteautomata
homomorphism
descriptive
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 1 Question 65 (Page No. 93)
Prove that for each $n > 0,$ a language $B_{n}$ exists where $B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, and if $B_{n} = A_{1}\cup...\cup A_{k},$ for regular languages $A_{i},$ then at least one of the $A_{i}$ requires a $\text{DFA}$ with exponentially many states$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 1 Question 64 (Page No. 92)
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$ Show that if $A$ is nonempty, A contains some string of length at most k. Show, by giving an example, that $\text{part (a)}$ is not necessarily ... $k.$ Come as close to the bound in $(c)$ as you can$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 63 (Page No. 92)
Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets. Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if $B\subseteq D$ and $D$ contains infinitely many ... regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 62 (Page No. 92)
Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}a(\sum \cup \epsilon)^{k1}$.Describe a $\text{DFA}$ with at most $k+ 1$ states that recognizes $D_{k}$ in terms of both a state diagram and a formal description.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
descriptive
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 60 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
Page:
1
2
3
4
5
6
...
38
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has begun
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
Follow @csegate
Recent questions tagged descriptive
Recent Blog Comments
@Anuj Mishra how did you study CLRS?what...
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
49,430
questions
53,616
answers
185,966
comments
70,892
users