search
Log In

Recent activity by kunal goswami

2 answers
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 ?
answered Apr 28 in Algorithms 4.3k views
4 answers
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$
commented Apr 6 in Algorithms 3k views
9 answers
3
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.
commented Apr 1 in DS 9.3k views
3 answers
4
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______
commented Mar 20 in Graph Theory 2k views
3 answers
5
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)$
commented Mar 6 in Algorithms 3k views
4 answers
6
Consider the following C program. #include <stdio.h> int main () { int a[4] [5] = {{1, 2, 3, 4, 5}, {6, 7,8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17,18, 19, 20}}; printf(“%d\n”, *(*(a+**a+2)+3)); return(0); } The output of the program is _______.
commented Mar 1 in Programming 3.4k views
1 answer
7
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 in Operating System 804 views
4 answers
8
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements. Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is $n-k+1$ $n-k$ $n-k-1$ $n-k-2$
commented Jan 4 in DS 7k views
1 answer
9
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 676 views
3 answers
10
8 answers
12
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 8.8k views
1 answer
13
Q. Over the set A={1,2,3,4,5} two partitions a and b are defined as a={{1,2,3},{4},{5}} and b={{1},{2,3},{4,5}}.The MEET and JOIN(under refinement relations between partitions ) are respectively. A) {(1),(2,3),(4),(5)} and {(1,2,3),(4,5)} B){(1,2,3)(4,5)} and{(1,2),(3),(4,5)} C){(1,2),(3,4)(5)} and {(1,2),(3,4),(5)} D){(1,2,3,4,5)} and {(1),(2),(3),(4),(5)}
commented Dec 8, 2019 in Set Theory & Algebra 802 views
5 answers
14
Let U = {1, 2, ..., n} and A = {(x, X), x ∈ X and X ⊆ U}. Consider the following two statements for |A|. (i) |A| = n*$\small 2^{n-1}$ (ii) |A|= Sigma(k=1 to n) k.(nCk) Which of the following is correct? (a) (i) only (b) (ii) only (c) Both (i) and (ii) (d) None of the above
commented Dec 6, 2019 in Set Theory & Algebra 2.5k views
1 answer
15
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 121 views
1 answer
16
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 572 views
1 answer
17
Consider following Schedule S with data item x : S : W1(X) R2(X) W3(X) R4(X) W5(X) R6(X) W7(X) R8(X) W9(X) R10(X) The number of schedule view equivalent to Schedule S but not conflict equivalent to Schedule S ?
commented Nov 16, 2019 in Databases 328 views
2 answers
18
S: If a relation R is in 3NF but not in BCNF then relation R must consist atleast 2 overlapped candidate keys. True/False
commented Nov 13, 2019 in Databases 424 views
1 answer
19
6 answers
20
Consider the following grammar and the semantic actions to support that 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$
answer edited Nov 7, 2019 in Compiler Design 4.4k views
5 answers
21
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: ... $\text{P-iii; Q-iv; R-i; S-ii}$ $\text{P-i; Q-iv; R-ii; S-iii}$
commented Nov 5, 2019 in Compiler Design 4.3k views
4 answers
22
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.5k views
2 answers
23
how the b and b+ tree formulae computed can u explain with the proof
answered Nov 2, 2019 in Databases 338 views
2 answers
24
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 158 views
1 answer
25
The relational algebra expression equivalent to the following tuple calculus expression: $\left\{t \mid t \in r \land \left(t[A] = 10 \land t[B]=20\right)\right\}$ is $\sigma_{(A=10 \lor B=20)} (r)$ $\sigma_{(A=10)} (r) \cup \sigma_{(B=20)} (r)$ $\sigma_{(A=10)} (r) \cap \sigma_{(B=20)} (r)$ $\sigma_{(A=10)} (r) - \sigma_{(B=20)} (r)$
commented Oct 22, 2019 in Databases 2.4k views
6 answers
26
Consider the relation account (customer, balance) where the customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broke but ranks are skipped: if ... order assigning ranks using ODBC. Which two of the above statements are correct? 2 and 5 1 and 3 1 and 4 3 and 5
commented Oct 21, 2019 in Databases 8.9k views
4 answers
27
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among $\text{union, intersection, membership, cardinality}$ will be the slowest? $\text{union}$ only $\text{intersection, membership}$ $\text{membership, cardinality}$ $\text{union, intersection}$
commented Sep 29, 2019 in DS 6.3k views
10 answers
28
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 8k views
0 answers
29
WHICH OF THE FOLLOWING IS DECIDABLE? 1.WHEATHER AN ARBITRARY TURING MACHINE PRINTS SOME NON BLANK CHARACTER 2.WHEATHER A TURING MACHINE PRINTS A SPECIFIC CHARACTER 3.THE SET OF CODES FOR TURING MACHINE THAT NEVER MAKE A LEFT MOVE. 4. WHEATHER T.M EVER MOVES ITS HEAD TO THE ... REACHES STATE Q WHEN STARTED WITH INPUT W FROM ITS INITIAL STATE 6.T.M VISITS STATE Q ON SOME INPUT WITHIN 10 STEPS. 7.
commented Sep 17, 2019 in Theory of Computation 470 views
6 answers
30
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 7.7k views
...