1
Is bellman ford a dynamic programming approach? If yes, what is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ?
2
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the ... distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$
3
int readers_count = 0; semaphore mutex = 1; // binary semaphore semaphore db = 1; // binary semaphore void reader() { while(TRUE) { x. down(mutex); //or wait(mutex) or P(mutex) readers_count = readers_count + 1; y. if(readers_count == 1) down(db); up(mutex) ... . b. Multiple readers and writers are allowed in the database at the same time. c. There is possibility of deadlock. d. None of the above.
4
Consider the following schedule : S:r1(A);w1(B);r2(A);w2(B);r3(A);w3(B); Here ri(X) denotes read on data item X and wi(X) denoted write on data item X .The total number of schedules that are view equivalent to S are _______
1 vote
5
Consider the following schedule: S: W1(A) W1(B) R2(A) W2(B) R3(A) W3(B) The number schedules conflict equivalent are ______________________.
6
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n-1$ $2n$ $\frac{n}{2}$
7
Consider the following statements: (i) Accessing of data in a column wise fashion maintains spatial locality only when the block size is equal to the total size of the elements in the row (ii) Coherence in write through protocol never occurs even cache memory is organized in multilevel. Which of the above is true?
8
A $3 \times 8$ decoder with two enables inputs is to be used to address 8 blocks of memory. What will be the size of each memory block when addressed from a sixteen-bit bus with two MSBs used to enable the decoder? $i)2k$ $ii)4k$ $iii)16k$ $iv) 64k$ What does “two enable inputs is to be used” mean? I am not able to visualize the circuit.
9
10
Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders for the non-terminals $D, T, L$ or $L_1$ ... $X_1=L, \: X_2=L, \: X_3=L_1, \: X_4 = T$ $X_1=T, \: X_2=L, \: X_3=T, \: X_4 = L_1$
11
MY SOLUTION : Fix the root then next level 2 elements ( 2! possibilities) next level 4 elements( 4! possibilities) last level 2 elements ( 2! possibilities) total possibility = 2! * 4! * 2! = 2 * 24 * 2 = 96 what went wrong ? just in case if the question in image is ... 3,2,1,7,9 such that if node of above graph is filled with these elements it satisfies max heap property a)96 b)896 c)2688 d) none
1 vote
12
how the b and b+ tree formulae computed can u explain with the proof
1 vote
13
Consider the following function in a single linked list int fun(struct node *P, struct node *Q) { if(P==NULL && Q == NULL) return 0; else if(P==NULL || Q==NULL) return 1; else if(P→data!=Q→data) return 1; if(fun(P→ left, Q→ left) || ... . It returns 0, when both trees are same recursively. It compares two given binary trees but return value cannot be used to differentiate the trees None of these
14
Consider the following C program: #include <stdio.h> int r() { static int num=7; return num--; } int main() { for (r();r();r()) printf(“%d”,r()); return 0; } Which one of the following values will be displayed on execution of the programs? $41$ $52$ $63$ $630$
15
Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of "in" is ____
16
Assume that multiplying a matrix $G_1$ of dimension $p \times q$ with another matrix $G_2$ of dimension $q \times r$ requires $pqr$ scalar multiplications. Computing the product of $n$ matrices $G_1G_2G_3 \dots G_n$ can be done by parenthesizing in different ... multiplications, the explicitly computed pairs is/are $F_1F_2$ and $F_3F_4$ only $F_2F_3$ only $F_3F_4$ only $F_1F_2$ and $F_4F_5$ only
17
Consider the C functions foo and bar given below: int foo(int val) { int x=0; while(val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while(val > 0) { x= x + bar(val-1); } ... $6$ and $6$ respectively. Infinite loop and abnormal termination respectively. Abnormal termination and infinite loop respectively. Both terminating abnormally.
1 vote
18
The following function computes $X^{Y}$ for positive integers $X$ and $Y$. int exp (int X, int Y) { int res =1, a = X, b = Y; while (b != 0) { if (b % 2 == 0) {a = a * a; b = b/2; } else {res = res * a; b = b - 1; } } return res; } Which one of the following conditions is TRUE before every ... the loop? $X^{Y} = a^{b}$ $(res * a)^{Y} = (res * X)^{b}$ $X^{Y} = res * a^{b}$ $X^{Y} = (res * a)^{b}$
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a = 3; void n(x) { x = x * a; print (x); } void m(y) { a = 1 ; a = y - a; n(a); print (a); } void main () { m(a); } $6,2$ $6,6$ $4,2$ $4,4$
Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode. DOSOMETHING (c, a, n) $z \leftarrow 1$ ... , then the output of DOSOMETHING(c, a, n) is _______.
Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two instances of $U_{G}$, it is required to implement the computation $F(G(X_{i}))$ for $1 \leq i \leq 10$. Ignoring all other delays, the minimum time required to complete this computation is ____________ nanoseconds.
Consider a $2-$way set associative cache with $256$ blocks and uses $LRU$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access ... $10$ times. The number of conflict misses experienced by the cache is _________ .