Dark Mode

Recent activity by Hardik Maheshwari

2 answers

1

GATE IT 2007 | Question: 48
Consider the grammar given below: $S \rightarrow x \ B \mid y \ A$ $A \rightarrow x \mid x \ S \mid y \ A \ A$ $B \rightarrow y \mid y \ S \mid x \ B \ B$ Consider the following strings. $xxyyx$ $xxyyxy$ $xyxy$ $yxxy$ $yxx$ $xyx$ Which of the above strings are generated by the grammar ? i, ii and iii ii, v and vi ii, iii and iv i, iii and iv

commented in Theory of Computation Jan 19, 2019

6.0k views

0 answers

2

Reading Doubt
Which has lower latency amongst “Switch” and “Router”. And why ?

asked in Computer Networks Jan 18, 2019

252 views

1 answer

3

Test Series
If $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..

asked in Theory of Computation Jan 14, 2019

997 views

1 answer

4

Practice Question
How to prove that $ (a+b)^*ab(a+b)^*+b^*a^* = (a+b)^*$

answer selected in Theory of Computation Jan 14, 2019

227 views

1 answer

5

Conflict Serializabilty
How many conflict equivalent schedules are possible for the given schedule ? $R_1(A), R_2(A), R_3(A), R_4(A), W_1(B), W_2(B), W_3(B), W_4(B)$

asked in Databases Oct 10, 2018

734 views

1 answer

6

Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????

commented in Algorithms Jul 6, 2018

2.7k views

1 answer

7

Space Complexity of Build Max Heap
Since Heapify is a recursive function, its space complexity is $O(logn)$ because of the stack space required for recursion. I also read that space complexity of heapsort is $O(1)$ beause of the explanation here - https://gateoverflow.in/79909/ ... complexity of build heap is $O(logn)$ then heapsorts complexity should also be the same . What am I missing here ?

asked in Algorithms Jun 14, 2018

3.7k views

1 answer

8

Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this ... masters theorem, like the way Tauhin Gangwar has solved here - https://gateoverflow.in/60532/find-tc-t-n-2t-n-1-2-1

answer selected in Algorithms Jun 12, 2018

2.7k views