1
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)$
2
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 ___________.
3
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: ___________
4
Is an array that is in sorted order a min-heap ?
5
If C is a set with c elements, how many elements are in the power set of C? Explain your answer.
6
Show that every graph with two or more nodes contains two nodes that have equal degrees.
7
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)
8
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$
1 vote
9
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.
1 vote
10
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$?
11
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?
1 vote
12
How the limits are reduced. Please explain in simpler way.
13
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?
14
15
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.
1 vote
16
how to solve this series:
17
what is co-turing recognizable language?
18
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.
1 vote
19
20
An urn contains 10 black and 10 white balls. Draw 3 a) without replacement
21
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.
22
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?
1 vote
23
I think the past cost to G from A as computed by Dijkstra should be 2 instead of 8. Please help me verify it.
24
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$
25
A polygon has 12 edges , How many diagonals does it have? How to find the number of diagonals?