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
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 difficult
These questions require proper application of subject concepts and is time consuming to solve.
0
votes
0
answers
1
Kenneth Rosen Edition 7th Exercise 2.3 Question 35 (Page No. 154)
If $f$ and $fog$ are onto, does it follow that $g$ is onto?Justify your answer.
asked
Apr 9
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.7k
points)

17
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
2
Kenneth Rosen Edition 7th Exercise 2.3 Question 34 (Page No. 154)
If $f$ and $fog$ are onetoone, does it follow that $g$ is onetoone? Justify your answer.
asked
Apr 9
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.7k
points)

5
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 9.3 Question 1 (Page No. 248)
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
4
Cormen Edition 3 Exercise 4.6 Question 3 (Page No. 106)
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b)\geq cf(n)$ for some constant $c<1$ implies that there exists a constant $\epsilon >0$ such that $f(n)=\Omega(n^{log_ba+\epsilon})$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
40.4k
points)

17
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
5
Cormen Edition 3 Exercise 4.6 Question 2 (Page No. 106)
Show that if $f(n)=\Theta(n^{log_ba}\lg^kn )$, where $k\geq0$ then the master recurrence has solution $T(n) =\Theta(n^{log_ba} \lg^{k+1}n)$.For simplicity, confine your analysis to exact powers of $b$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
40.4k
points)

10
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
6
Kenneth Rosen Edition 7th Exercise 2.1 Question 45 (Page No. 126)
The defining property of an ordered pair is that two ordered pairs are equal if and only if their first elements are equal and their second elements are equal. Surprisingly, instead of taking the ordered pair as a primitive concept, we can construct ordered pairs ... $a = c$ and $b=d.$]
asked
Apr 5
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.7k
points)

6
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
7
Cormen Edition 3 Exercise 4.5 Question 5 (Page No. 97)
Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $c<1$,which is part of case 3 of the master theorem. Give an example of constants $a\geq 1$ and $b>1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
40.4k
points)

17
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
1
answer
8
Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
40.4k
points)

24
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
9
Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
asked
Apr 4
in
Algorithms
by
akash.dinkar12
Boss
(
40.4k
points)

6
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 9.1 Question 1 (Page No. 238)
Write a Turing machine simulator in some higherlevel programming language. Such a simulator should accept as input the description of any Turing machine, together with an initial configuration, and should produce as output the result of the computation.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 10.2 Question 6,7 (Page No. 264)
Exercise 6: Show that for every Turing machine there exists an equivalent standard Turing machine with no more than six states. Exercise 7: Reduce the number of required states in Exercise 6 above as far as you can (Hint: The smallest possible number is three)
asked
Mar 30
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

13
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 10.2 Question 5 (Page No. 264)
A $\text{queue automaton}$ is an automaton in which the temporary storage is a queue. Assume that such a machine is an online machine, that is, it has no input file, with the string to be processed placed in ... of the computation. Give a formal definition of such an automaton, then investigate its power in relation to Turing machines.
asked
Mar 30
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 10.2 Question 8 (Page No. 264)
A counter is a stack with an alphabet of exactly two symbols a stack start symbol and a counter symbol. Only the counter symbol can be put on the stack or removed from it. A $\text{counter automaton}$ is a ... one or more counters as storage. Show that any Turing machines can be simulated using a counter automaton with four counters.
asked
Mar 28
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

20
views
peterlinz
theoryofcomputation
turingmachine
proof
difficult
0
votes
0
answers
14
Kenneth Rosen Edition 7th Exercise 1.6 Question 35 (Page No. 80)
Determine whether this argument, taken from Kalish and Montague [KaMo64], is valid. If Superman were able and willing to prevent evil,he would do so. If Superman were unable to prevent evil, he would be impotent; ... does not prevent evil. If Superman exists, he is neither impotent nor malevolent. Therefore, Superman does not exist.
asked
Mar 20
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.7k
points)

16
views
kennethrosen
discretemathematics
propositionallogic
mathematicallogic
difficult
0
votes
0
answers
15
Kenneth Rosen Edition 7th Exercise 1.6 Question 34 (Page No. 80)
The Logic Problem, taken from WFF'N PROOF, The Game of Logic, has these two assumptions:1. Logic is difficult or not many students like logic. 2. If mathematics is easy, then logic is not difficult. By translating ... not easy. That if not many students like logic, then either mathematics is not easy or logic is not difficult.
asked
Mar 20
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.7k
points)

40
views
kennethrosen
discretemathematics
mathematicallogic
propositionallogic
difficult
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find contextsensitive grammars for the following languages. $(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$. $(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.
asked
Mar 17
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the contextsensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n1} : n\geq 1\}$. $\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$. $\text{(c)}$ $L=\{a^{n}b^mc^{n}d^m : n\geq 1, m\geq1\}$. $\text{(d)}$ $L=\{ww : w\in \{a,b\}^+\}$. $\text{(e)}$ $L=\{a^{n}b^nc^{n}d^m : n\geq 1\}$.
asked
Mar 17
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

10
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 12.4 Question 8 (Page No. 321)
Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted, $\text(b)$ when $G_2$ is contextfree, $\text(c)$ when $G_2$ is regular$?$
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.5k
points)

14
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a contextfree grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

12
views
theoryofcomputation
peterlinz
decidability
proof
difficult
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 12.4 Question 6 (Page No. 321)
Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation $q_0w\vdash x_1\vdash x_2\vdash ...\vdash x_n$, we can then construct the string ... to show that $ L(G) = \Sigma^* $ is undecidable over the domain of all contextfree grammars G.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

11
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a contextfree grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

6
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given contextfree grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in Theorem is regular, then it must be empty. Use this to show that the problem $“L(G)$ is regular $”$ is undecidable for contextfree $G$.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.5k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 12.4 Question 3 (Page No. 321)
Show that for arbitrary contextfree grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is contextfree$”$ is undecidable.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.5k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 12.4 Question 2 (Page No. 321)
Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for contextfree grammars $G_1,\space G_2$.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

5
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
25
Kenneth Rosen Edition 7th Exercise 1.3 Question 45 (Page No. 36)
Show that $\sim$ and $\vee$ form a functionally complete collection of logical operators.
asked
Mar 16
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.7k
points)

26
views
kennethrosen
discretemathematics
mathematicallogic
propositionallogic
difficult
descriptive
0
votes
0
answers
26
Kenneth Rosen Edition 7th Exercise 1.3 Question 44 (Page No. 36)
Show that $\sim$ and $\wedge$ form a functionally complete collection of logical operators. [Hint: First use a De Morgan law to show that $p \vee q$ is logically equivalent to $(\sim(\sim p \wedge \sim q)).$]
asked
Mar 16
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.7k
points)

11
views
kennethrosen
discretemathematics
mathematicallogic
propositionallogic
difficult
0
votes
0
answers
27
Kenneth Rosen Edition 7th Exercise 1.2 Question 15 (Page No. 23)
Each inhabitant of a remote village always tells the truth or always lies. A villager will give only a Yes or a No response to a question a tourist asks. Suppose you are a tourist visiting this area and come to a ... is standing at the fork in the road. What one question can you ask the villager to determine which branch to take?
asked
Mar 15
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.7k
points)

8
views
kennethrosen
discretemathematics
mathematicallogic
difficult
0
votes
1
answer
28
TIFR2019B12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
asked
Dec 18, 2018
in
Graph Theory
by
Arjun
Veteran
(
407k
points)

239
views
tifr2019
engineeringmathematics
discretemathematics
graphtheory
difficult
+5
votes
1
answer
29
Mathematics: GATE 2017 MA
ANSWER GIVEN IS 0.270.37
asked
Sep 16, 2017
in
Probability
by
Amit puri
Active
(
2.4k
points)

116
views
discreteprobability
difficult
gate2017ma
+39
votes
3
answers
30
GATE2017139
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ ... If $f$ is computable then $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
asked
Feb 14, 2017
in
Theory of Computation
by
Arjun
Veteran
(
407k
points)

5.3k
views
gate20171
theoryofcomputation
decidability
difficult
Page:
1
2
3
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
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
IIIT Hyerabad Interview Expeience  MS by Research in CSE
Follow @csegate
Recent questions tagged difficult
Recent Blog Comments
My rank in gate was a disaster...2111 rank and...
Sir whats you rank ?
Ok,Thank you for replying!
By a good profile I mean having academic...
Thank you sir..
49,532
questions
54,134
answers
187,337
comments
71,058
users