GATE CSE
| GROUP 1 | GROUP 2 |
|---|---|
| 1. Dijkstra's Shortest Path | i. Divide and Conquer |
| 2. Floyd-Warshall algorithm to compute all pairs shortest path |
ii. Dynamic Programming |
| 3. Binary search on a sorted array | iii. Greedy design |
| 4. Backtracking search on a graph | iv. Depth-first search |
| v. Breadth-first search |
Match the above algorithms on the left to the corresponding design paradigm they follow.
| 1 | 2 | 5 | 14 |
|---|---|---|---|
| 3 | 4 | 6 | 23 |
| 10 | 12 | 18 | 25 |
| 31 | ∞ |
∞ | ∞ |
When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a $$\infty $$). The minimum number of entries (other than $$1$$) to be shifted, to remove $$1$$ from the given Young tableau is ______________.
int partition(int a[], int n);int kth_smallest (int a[], int n, int k)
{
int left_end = partition (a, n);
if (left_end+1==k) {
return a[left_end];
}
if (left_end+1 > k) {
return kth_smallest (___________);
} else {
return kth_smallest (___________);
}
}(1) i = 1
(2) j = 1
(3) t1 = 5 ∗ i
(4) t2 = t1 + j
(5) t3 = 4 ∗ t2
(6) t4 = t3
(7) a[t4] = -1
(8) j = j + 1
(9) if j<=5 goto (3)
(10) i=i+1
(11) if i<5 goto (2)The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
| GROUP 1 | GROUP 2 |
|---|---|
| P. Lexical analysis | 1. Graph coloring |
| Q. Parsing | 2. DFA minimization |
| R. Register allocation | 3. Post-order traversal |
| S. Expression evaluation | 4. Production tree |
For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above.
| MUL | R5, R0, R1 |
|---|---|
| DIV | R6, R2, R3 |
| ADD | R7, R5, R6 |
| SUB | R8, R7, R4 |
In the above sequence, $$R0$$ to $$R8$$ are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $$4$$ stages: $$(1)$$ Instruction Fetch and Decode $$(IF), (2)$$ Operand Fetch $$(OF), (3)$$ Perform Operation $$(PO)$$ and $$(4)$$ Write back the result $$(WB).$$ The $$IF,$$ $$OF$$ and $$WB$$ stages take $$1$$ clock cycle each for any instruction. The $$PO$$ stage takes $$1$$ clock cycle for $$ADD$$ or $$SUB$$ instruction, $$3$$ clock cycles for $$MUL$$ instruction and $$5$$ clock cycles for $$DIV$$ instruction. The pipelined processor uses operand forwarding from the $$PO$$ stage to the $$OF$$ stage. The number of clock cycles taken for the execution of the above sequence of instructions is _______________________ .
$$ \bullet \,\,\,\,\,\,\,\,$$ Store the current value of $$PC$$ in the stack
$$ \bullet \,\,\,\,\,\,\,\,$$ Store the value of $$PSW$$ register in the stack
$$ \bullet \,\,\,\,\,\,\,\,$$ Load the starting address of the subroutine in $$PC$$
The content of $$PC$$ just before the fetch of a CALL instruction is $$\left( {5FA0} \right){\,_{16}}.$$ After execution of the CALL instruction, the value of the stack pointer is
read (x) ; x: = x - 50; write (x); read (y); y: = y + 50; write (y)The constraint that the sum of the accounts x and y should remain constant is that of
(start, $$T4$$); (write, $$T4, y, 2, 3$$); (start, $$T1$$); (commit, $$T4$$); (write, $$T1, z, 5, 7$$);
(checkpoint);
(start, $$T2$$); (write, $$T2, x, 1, 9$$); (commit, $$T2$$); (start, $$T3$$), (write, $$T3, z, 7, 2$$);
If a crash happens now and the system tries to recovver using both undo and redo operations, what are the contents of the undo list and the redo list?
Assume that $$R(A,B,C)$$ is the full natural outer join of $${R_1}$$ and $${R_2}$$. Consider the following tuples of the form $$(A,B,C): a = (1,5,null),$$ $$b = (1,null,7),$$ $$c = (3, null, 9),$$ $$d = (4,7,null),$$ $$e = (1,5,7),$$ $$f = (3,7,null),$$ $$g = (4,null,9).$$ Which one of the following statements is correct?
(i) Add the third row to the second row
(ii) Subtract the third column from the first column.
The determinant of the resultant matrix is _________.
$${\rm I}.$$ $$f$$ is continuous in $$\left[ { - 1,1} \right]$$
$${\rm I}{\rm I}.$$ $$f$$ is not bounded in $$\left[ { - 1,1} \right]$$
$${\rm I}{\rm I}{\rm I}.$$ $${\rm A}$$ is nonzero and finite
$$S1:$$ If a candidate is known to be corrupt, then he will not be elected
$$S2:$$ If a candidate is kind, he will be elected
Which one of the following statements follows from $$S1$$ and $$S2$$ as per sound inference rules of logic?
void foo(char *a){
if ( *a && *a != ' '){
foo(a+1);
putchar(*a);
}
}#include < stdio.h >
int *A, stkTop;
int stkFunc(int opcode, int val)
{
static int size=0, stkTop=0;
switch (opcode) {
case -1: size = val; break;
case 0: if (stkTop < size) A[stkTop++] = val; break;
default: if (stkTop) return A[--stkTop];
}
return -1;
}
int main()
{
int B[20]; A = B; stkTop = -1;
stkFunc (-1, 10);
stkFunc ( 0, 5);
stkFunc ( 0, 10);
printf ("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
}int fun ( int n ) {
int x = 1, k ;
if ( n == 1) return x ;
for( k = 1 ; k < n ; ++ k )
x = x + fun( k ) * fun( n - k ) ;
return x ;
}$${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right.$$ and $$\left. {\left| w \right|,\left| x \right| > 0} \right\},\,{w^R}$$ is the reverse of string $$w$$
$${L_2}:\left\{ {{a^n}{b^m}\left| {m \ne n} \right.} \right.$$ and $$m,n \ge \left. 0 \right\}$$
$${L_3}:\left\{ {{a^p}{b^q}{c^r}\left| {p,q,r \ge 0} \right.} \right\}$$
Which one of the following choices precisely represents the strings in $${X_0}$$?
$$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable
$$\,$$ $${\rm II}.\,\,\,\,\,\,\,\,\,$$ There exists some language which is in $$NP$$ but is not Turing decidable
$${\rm III}.\,\,\,\,\,\,\,\,\,$$ If $$L$$ is a language in $$NP,$$ $$L$$ is Turing decidable
Which of the above statements is/are true?