# Recent activity by kunal goswami

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
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 __________.
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 _______
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)$
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 _______.
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.
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$
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 _______
10
Consider the following schedule: S: W1(A) W1(B) R2(A) W2(B) R3(A) W3(B) The number schedules conflict equivalent are ______________________.
11
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}$
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)}
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
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?
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.
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 ?
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
19
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$
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}$
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
23
how the b and b+ tree formulae computed can u explain with the proof
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
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)$
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
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}$
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$