Dark Mode

Answers by goxul

40 votes

1

GATE CSE 2020 | Question: 31
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$

answered in Algorithms Feb 12, 2020

14.3k views

33 votes

2

GATE CSE 2020 | Question: 47
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

answered in DS Feb 12, 2020

10.7k views

0 votes

3

GATE CSE 2019 | Question: 25
Consider a sequence of $14$ elements: $A=[-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]$. The sequence sum $S(i,j) = \Sigma_{k=i}^j A[k]$. Determine the maximum of $S(i,j)$, where $0 \leq i \leq j <14$. (Divide and conquer approach may be used.) Answer: ___________

answered in Algorithms Jul 4, 2019

14.8k views

0 votes

4

Cormen Edition 3 Exercise 6.1 Question 5 (Page No. 154)
Is an array that is in sorted order a min-heap ?

answered in Algorithms Apr 14, 2019

202 views

0 votes

5

Michael Sipser Edition 3 Exercise 0 Question 5 (Page No. 26)
If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

answered in Theory of Computation Apr 14, 2019

2.1k views

0 votes

6

Michael Sipser Edition 3 Exercise 0 Question 13 (Page No. 27)
Show that every graph with two or more nodes contains two nodes that have equal degrees.

answered in Theory of Computation Apr 14, 2019

427 views

0 votes

7

MOCK TEST
Consider an array consisting of –ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other? a)N-1 b)N c)N+1 d) (N*(N-1))/2 answer given is a)

answered in Algorithms Mar 22, 2019

233 views

0 votes

8

Gateforum Test Series: Algorithms - Asymptotic Notations
Which of the following is not true in the function $f(n)=2^{n-4}$? $f(n)$=Θ($2^{n+3}$) $f(n)$=Ω($n^{1000}$) $f(n)$=Ο($2^{n-10}$) $f(n)$=$None$

answered in Algorithms Dec 7, 2018

450 views

1 vote

9

Gateforum Test Series: Algorithms - Asymptotic Notations
Consider the following function $f(x)$ = $x^8$+6$x^7$-9$x^5$-$x^4$+2$x^2$-18. Which of the following is true if x is greater than 56? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above.

answered in Algorithms Dec 7, 2018

487 views

1 vote

10

OS-Virtual Memory
A computer system has a page size of 1024 bytes and maintains page table for each process in the main memory.The overhead required for doing a lookup in the page table is $500ns$.To reduce this overhead, the computer has a TLB that caches 32 ... mappings.A TLB lookup requires $100ns$.What TLB hit-rate is required to ensure an average virtual address translation time of $200ns$?

answered in Operating System Dec 2, 2018

861 views

2 votes

11

Doubt on probability
15 students among whom are A and B arranged randomly in a row. Obtain the probability that there will be 3 students between A and B?

answered in Probability Nov 30, 2018

258 views

1 vote

12

Doubt : TC
How the limits are reduced. Please explain in simpler way.

answered in Algorithms Nov 29, 2018

217 views

2 votes

13

Probability
The probability of a student passing an exam is 0.1. What is the probability that he passes the exam in the 3rd attempt? Please explain in details. I am confused about these two approaches: Approach 1: P(passing in 3rd attempt)=P(failed in 1st)*P(failed in 2nd ... pass rate will always remain constant no matter on which attempt he is trying. ie. Answer = 0.1 Which one is wrong and why?

answered in Probability Nov 28, 2018

217 views

0 votes

14

Time Complexity

answered in Algorithms Nov 28, 2018

347 views

0 votes

15

GATEBOOK_CN_20
Let M be a confidential email that Alice wants to send to Bob, $K_B$ be Bob's encryption public key, and $K_A^{-1}$ be Alice's private key for signing. Which of the following options would be the best choice for protecting confidential ... message, Alice should sign the encrypted message and then should send this signature along with the encrypted message to BOB. Please help.

answered in Computer Networks Nov 27, 2018

1.4k views

1 vote

16

How to solve this series which is in both AP and GP?
how to solve this series:

answered in Set Theory & Algebra Nov 24, 2018

3.8k views

0 votes

17

Turing machine
what is co-turing recognizable language?

answered in Theory of Computation Nov 24, 2018

145 views

0 votes

18

Self-Doubt
Consider Main memory M and Cache C. 1. When we say the access time of main memory is T what parameters does it include?Is it . just obtaining data from M or .obt data from M and Transfer it to cache(I understood as this) or . Obt data from M, ... which scenario do we take? Pls, help me with these finer aspects. I understood the overall idea. In NATs, I'm missing by small margins.

answered in CO and Architecture Nov 24, 2018

162 views

1 vote

19

answered in Algorithms Nov 22, 2018

313 views

0 votes

20

Probability - Gravner-33.a
An urn contains 10 black and 10 white balls. Draw 3 a) without replacement

answered in Probability Nov 22, 2018

253 views

0 votes

21

Probability - Gravner-15.a
A tennis tournament has $2n$ participants, $n$ Swedes and n Norwegians. First, $n$ people are chosen at random from the $2n$ (with no regard to nationality) and then paired randomly with the other $n$ people. Each pair proceeds to play one match. An ... $n$ (ordered) pairs, giving the winner and the loser in each of the $n$ matches. (a) Determine the number of outcomes.

answered in Probability Nov 22, 2018

306 views

4 votes

22

T(n) = sqrt(n) * T(sqrt(n)) + n
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?

answered in Algorithms Nov 22, 2018

9.2k views

1 vote

23

METest_Algo
I think the past cost to G from A as computed by Dijkstra should be 2 instead of 8. Please help me verify it.

answered in Algorithms Nov 18, 2018

426 views

9 votes

24

GATE CSE 2006 | Question: 44
Station $A$ uses $32\; \text{byte}$ packets to transmit messages to Station $B$ using a sliding window protocol. The round trip delay between A and $B$ is $80\; \text{milliseconds}$ and the bottleneck bandwidth on the path between $A$ and $B$ is $128\; \text{kbps}$ . What is the optimal window size that $A$ should use? $20$ $40$ $160$ $320$

answered in Computer Networks Nov 17, 2018

23.1k views

1 vote

25

Self Doubt
A polygon has 12 edges , How many diagonals does it have? How to find the number of diagonals?

answered in Quantitative Aptitude Nov 16, 2018

162 views

0 votes

26

ibps2014
the run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is 1. o (n log n) 2. o (n) 3. o(sqrt(n)) 4. o (log n)

answered in Programming Nov 16, 2018

166 views

1 vote

27

compiler design
One of the purposes of using intermediate code in compilers is to increase the chances of reusing the machine-independent code optimizer in other compilers. eleborate this ??

answered in Compiler Design Nov 15, 2018

433 views

2 votes

28

Made easy test series
What is the difference between (ii) and (iv). I understood (ii) as "All the engineers like at least some doctor" What will be the translation for (iv) ?

answered in Mathematical Logic Nov 15, 2018

213 views

1 vote

29

CN-Doubt
Which classful subnet mask is useful for need of subnet a network that has 5 subnet each with at least 20 hosts. A.255.255.255.192 B.255.255.255.248 C.255.255.255.240 D.255.255.255.224

answered in Computer Networks Nov 12, 2018

317 views

Page:

1
2
3
4
next »