Log In

Answers by goxul

7 votes
Let $G = (V, G)$ 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 of the resultant graph ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
answered Feb 12 in Algorithms 2.5k views
13 votes
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 Feb 12 in Algorithms 1.7k views
0 votes
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 Jul 4, 2019 in Algorithms 5.4k views
0 votes
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 Mar 22, 2019 in Algorithms 37 views
0 votes
1 vote
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 Dec 7, 2018 in Algorithms 153 views
1 vote
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 virtual pages ... mappings.A TLB lookup requires $100ns$.What TLB hit-rate is required to ensure an average virtual address translation time of $200ns$?
answered Dec 2, 2018 in Operating System 194 views
2 votes
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 Nov 30, 2018 in Probability 118 views
1 vote
How the limits are reduced. Please explain in simpler way.
answered Nov 29, 2018 in Algorithms 67 views
2 votes
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)*P( ... The 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 Nov 28, 2018 in Probability 58 views
0 votes
answered Nov 28, 2018 in Algorithms 69 views
0 votes
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 emails? ... Encrypted message, Alice should sign the encrypted message and then should send this signature along with the encrypted message to BOB. Please help.
answered Nov 27, 2018 in Computer Networks 373 views
0 votes
what is co-turing recognizable language?
answered Nov 24, 2018 in Theory of Computation 42 views
0 votes
Consider Main memory M and Cache C. 1.When we say acess time of main memory is T what parameters does it include.Is it . just obtaining data from M or .obt data from M and Transferring it to cache(I understood as this) or . Obt data from M ,Transferring ... is given which scenario do we take. Pls help me with these finer aspects. I understood the overall idea.In NATs Im missing by small margins.
answered Nov 24, 2018 in CO and Architecture 38 views
1 vote
answered Nov 22, 2018 in Algorithms 94 views
0 votes
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 outcome is a set of $n$ (ordered) pairs, giving the winner and the loser in each of the $n$ matches. (a) Determine the number of outcomes.
answered Nov 22, 2018 in Probability 39 views
3 votes
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 Nov 22, 2018 in Algorithms 1.9k views
1 vote
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 Nov 18, 2018 in Algorithms 80 views
3 votes
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 Nov 17, 2018 in Computer Networks 11.4k views
0 votes
A polygon has 12 edges , How many diagonals does it have? How to find the number of diagonals?
answered Nov 16, 2018 in Numerical Ability 57 views
0 votes
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 Nov 16, 2018 in Programming 36 views
1 vote
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 Nov 15, 2018 in Compiler Design 60 views
2 votes
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 Nov 15, 2018 in Mathematical Logic 76 views
1 vote
Which classful subnet mask is useful for need of subnet a network that has 5 subnet each with at least 20 hosts. A. B. C. D.
answered Nov 12, 2018 in Computer Networks 68 views