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
Recent questions tagged difficult
These questions require proper application of subject concepts and is time consuming to solve.
0
votes
0
answers
1
Cormen Edition 3 Exercise 10.2 Question 8 (Page No. 241)
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$bit integers, and define $x.np$ ... $INSERT$, and $DELETE$ operations on such a list. Also, show how to reverse such a list in $O(1)$ time.
asked
Jun 30, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

101
views
cormen
datastructures
linkedlists
descriptive
difficult
0
votes
0
answers
2
Cormen Edition 3 Exercise 8.4 Question 5 (Page No. 204)
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

78
views
cormen
algorithms
sorting
bucketsort
descriptive
difficult
0
votes
0
answers
3
Cormen Edition 3 Exercise 8.4 Question 4 (Page No. 204)
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2, .,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in ... the origin. (Hint: Design the bucket sizes in BUCKETSORT to reflect the uniform distribution of the points in the unit circle.)
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

31
views
cormen
algorithms
sorting
bucketsort
descriptive
difficult
0
votes
1
answer
4
Cormen Edition 3 Exercise 7.4 Question 6 (Page No. 185)
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$to$(1\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

30
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
1
answer
5
Cormen Edition 3 Exercise 7.2 Question 6 (Page No. 179)
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $12\alpha$ that on a random input array, PARTITION produces a split more balanced than $1\alpha$ to $\alpha$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

15
views
cormen
algorithms
quicksort
descriptive
difficult
0
votes
0
answers
6
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the bestcase running time of HEAPSORT is $\Omega(n\lg\ n)$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

11
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
1
answer
7
Cormen Edition 3 Exercise 2.3 Question 7 (Page No. 39)
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

12
views
cormen
algorithms
algorithmdesigntechniques
descriptive
difficult
0
votes
0
answers
8
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, 2019
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.9k
points)

20
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
9
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, 2019
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.9k
points)

7
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
10
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

16
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
11
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

22
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
12
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
13
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, 2019
in
Set Theory & Algebra
by
Pooja Khatri
Boss
(
10.9k
points)

11
views
kennethrosen
discretemathematics
settheory&algebra
difficult
0
votes
0
answers
14
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

27
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
1
answer
15
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

40
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
+1
vote
0
answers
16
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

13
views
cormen
algorithms
asymptoticnotations
descriptive
difficult
0
votes
0
answers
17
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
18
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

14
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
19
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

12
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
20
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

23
views
peterlinz
theoryofcomputation
turingmachine
proof
difficult
0
votes
0
answers
21
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, 2019
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.9k
points)

29
views
kennethrosen
discretemathematics
propositionallogic
mathematicallogic
difficult
0
votes
0
answers
22
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, 2019
in
Mathematical Logic
by
Pooja Khatri
Boss
(
10.9k
points)

55
views
kennethrosen
discretemathematics
mathematicallogic
propositionallogic
difficult
0
votes
0
answers
23
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
24
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

13
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
1
answer
25
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, 2019
in
Computer Networks
by
Rishi yadav
Boss
(
11.6k
points)

47
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
26
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

43
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
27
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

21
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
28
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

17
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
29
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, 2019
in
Computer Networks
by
Rishi yadav
Boss
(
11.6k
points)

17
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
30
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, 2019
in
Computer Networks
by
Rishi yadav
Boss
(
11.6k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged difficult
Recent Blog Comments
@Dumbest Kid They call in 1:8 ratio, in 2018 212...
https://www.isro.gov.in/sites/default/files/comput...
Can someone please post official answer key link
I have raised objections for the (RPC, mutual...
cidacoder Because there are two questions in...
50,737
questions
57,301
answers
198,299
comments
104,999
users