Log In

Answers by kunal goswami

0 votes
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 ?
answered Apr 28, 2020 in Algorithms 5.2k views
0 votes
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$
answered Apr 6, 2020 in Algorithms 4.9k views
0 votes
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.
answered Jan 27, 2020 in Operating System 1k views
0 votes
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 _______
answered Dec 26, 2019 in Databases 1.1k views
1 vote
0 votes
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}$
answered Dec 12, 2019 in Algorithms 10.6k views
0 votes
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?
answered Dec 4, 2019 in CO and Architecture 142 views
0 votes
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.
answered Nov 22, 2019 in Digital Logic 737 views
0 votes
3 votes
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$
answered Nov 7, 2019 in Compiler Design 6.1k views
0 votes
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
answered Nov 4, 2019 in Combinatory 1.9k views
1 vote
how the b and b+ tree formulae computed can u explain with the proof
answered Nov 2, 2019 in Databases 459 views
1 vote
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
answered Oct 27, 2019 in Programming 275 views
8 votes
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$
answered Sep 28, 2019 in Programming 9.9k views
2 votes
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 ____
answered Jul 5, 2019 in Digital Logic 9.9k views
3 votes
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
answered Jan 29, 2019 in Algorithms 8.7k views
5 votes
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.
answered Dec 9, 2018 in Programming 12.9k views
1 vote
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}$
answered Jun 15, 2018 in Programming 5.5k views
13 votes
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$
answered Jun 14, 2018 in Compiler Design 12.9k views
3 votes
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 _______.
answered Jun 14, 2018 in Algorithms 3.5k views
14 votes
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.
answered Jun 7, 2018 in CO and Architecture 12.3k views
11 votes
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 _________ .
answered Jun 6, 2018 in CO and Architecture 20k views