Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
These questions require proper application of subject concepts and is time consuming to solve.
Recent questions tagged difficult
6
votes
1
answer
1
GATE CSE 2021 Set 1 | Question: 35
Consider the two statements. $S_1:\quad$ There exist random variables $X$ and $Y$ such that $ \left(\mathbb E[(X-\mathbb E(X))(Y-\mathbb E(Y))]\right)^2>\textsf{Var}[X]\textsf{Var}[Y]$ $S_2:\quad$ For all random variables $X$ ... $S_2$ are true $S_1$ is true, but $S_2$ is false $S_1$ is false, but $S_2$ is true Both $S_1$ and $S_2$ are false
Arjun
asked
in
Probability
Feb 18, 2021
by
Arjun
3.4k
views
gatecse-2021-set1
probability
random-variable
difficult
2-marks
0
votes
0
answers
2
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.
akash.dinkar12
asked
in
Algorithms
Jun 30, 2019
by
akash.dinkar12
522
views
cormen
data-structures
linked-list
descriptive
difficult
1
vote
0
answers
3
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.
akash.dinkar12
asked
in
Algorithms
Jun 28, 2019
by
akash.dinkar12
346
views
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
0
votes
0
answers
4
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 BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)
akash.dinkar12
asked
in
Algorithms
Jun 28, 2019
by
akash.dinkar12
385
views
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
1
vote
1
answer
5
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$.
akash.dinkar12
asked
in
Algorithms
Jun 28, 2019
by
akash.dinkar12
672
views
cormen
algorithms
quick-sort
descriptive
difficult
1
vote
1
answer
6
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 $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1-\alpha$ to $\alpha$.
akash.dinkar12
asked
in
Algorithms
Jun 27, 2019
by
akash.dinkar12
220
views
cormen
algorithms
quick-sort
descriptive
difficult
0
votes
0
answers
7
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
akash.dinkar12
asked
in
Algorithms
Jun 27, 2019
by
akash.dinkar12
194
views
cormen
algorithms
heap
heap-sort
descriptive
difficult
0
votes
1
answer
8
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$.
akash.dinkar12
asked
in
Algorithms
Jun 26, 2019
by
akash.dinkar12
269
views
cormen
algorithms
algorithm-design-techniques
descriptive
difficult
0
votes
1
answer
9
Kenneth Rosen Edition 7 Exercise 2.3 Question 35 (Page No. 154)
If $f$ and $fog$ are onto, does it follow that $g$ is onto?Justify your answer.
Pooja Khatri
asked
in
Set Theory & Algebra
Apr 9, 2019
by
Pooja Khatri
230
views
kenneth-rosen
discrete-mathematics
set-theory&algebra
difficult
0
votes
0
answers
10
Kenneth Rosen Edition 7 Exercise 2.3 Question 34 (Page No. 154)
If $f$ and $fog$ are one-to-one, does it follow that $g$ is one-to-one? Justify your answer.
Pooja Khatri
asked
in
Set Theory & Algebra
Apr 9, 2019
by
Pooja Khatri
132
views
kenneth-rosen
discrete-mathematics
set-theory&algebra
difficult
0
votes
0
answers
11
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.
Rishi yadav
asked
in
Theory of Computation
Apr 9, 2019
by
Rishi yadav
132
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
difficult
0
votes
0
answers
12
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})$.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
181
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
13
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$.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
152
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
14
Kenneth Rosen Edition 7 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.$]
Pooja Khatri
asked
in
Set Theory & Algebra
Apr 5, 2019
by
Pooja Khatri
277
views
kenneth-rosen
discrete-mathematics
set-theory&algebra
difficult
0
votes
0
answers
15
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.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
204
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
1
answer
16
Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
209
views
cormen
algorithms
asymptotic-notations
descriptive
difficult
1
vote
0
answers
17
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 ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
118
views
cormen
algorithms
asymptotic-notations
descriptive
difficult
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 9.1 Question 1 (Page No. 238)
Write a Turing machine simulator in some higher-level 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.
Rishi yadav
asked
in
Theory of Computation
Apr 3, 2019
by
Rishi yadav
138
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
difficult
0
votes
0
answers
19
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)
Rishi yadav
asked
in
Theory of Computation
Mar 30, 2019
by
Rishi yadav
142
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
difficult
0
votes
0
answers
20
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.
Rishi yadav
asked
in
Theory of Computation
Mar 30, 2019
by
Rishi yadav
149
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
difficult
0
votes
0
answers
21
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.
Rishi yadav
asked
in
Theory of Computation
Mar 28, 2019
by
Rishi yadav
132
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
difficult
0
votes
0
answers
22
Kenneth Rosen Edition 7 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; if ... does not prevent evil. If Superman exists, he is neither impotent nor malevolent. Therefore, Superman does not exist.
Pooja Khatri
asked
in
Mathematical Logic
Mar 20, 2019
by
Pooja Khatri
501
views
kenneth-rosen
discrete-mathematics
propositional-logic
mathematical-logic
difficult
0
votes
0
answers
23
Kenneth Rosen Edition 7 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 these ... not easy. That if not many students like logic, then either mathematics is not easy or logic is not difficult.
Pooja Khatri
asked
in
Mathematical Logic
Mar 20, 2019
by
Pooja Khatri
491
views
kenneth-rosen
discrete-mathematics
mathematical-logic
propositional-logic
difficult
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find context-sensitive 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)\}$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
91
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the context-sensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : 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\}$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
113
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
1
answer
26
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 context-free, $\text(c)$ when $G_2$ is regular$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
190
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
Page:
1
2
3
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(854)
Recent questions tagged difficult
Recent Blog Comments
please add GO Classes 2023 Computer Networks...
Please upload 4th Mock Test, due date was 4th Dec.
The counts of answered, marked etc in the exam...
Tests have been sent and all tests will be...
Maximum age limit changed from 35 yrs. to 28...