-
1.
Statement for Linked Answer Questions ::
Consider the following floating-point format.
Mantissa is a pure fraction in sign-magnitude form.
[1] (A) The decimal number 0.239 × 213 has the following hexadecimal representation (without normalization and rounding off): [2 marks]
(a) 0D 24
(b) 0D 4D
(c) 4D 0D
(d) 4D 3D[2] (B) The normalized representation for the above format is specified as follows.
The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0’s are padded in while shifting a field.
The normalized representation of the above number (0.239 × 213 ) is:
(a) 0A 20
(b) 11 34
(c) 49 D0
(d) 4A E8asked in Computer Science And Engineering, 2005
View Comments [0 Reply]
-
2.
Statement for Linked Answer Questions::
We are given 9 tasks T1, T2, …. T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di. Profit Pi is earned if the task is completed before the end of the di th unit of time.Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3
[1] (A) Are all tasks completed in the schedule that gives maximum profit? [2 marks]
(a) All tasks are completed
(b) T1 and T6 are left out
(c) T1 and T8 are left out
(d) T4 and T6 are left out[2] (B) What is the maximum profit earned? [2 marks]
(a) 147
(b) 165
(c) 167
(d) 175asked in Computer Science And Engineering, 2005
View Comments [0 Reply]
-
3.
Statement for Linked Answer Questions::
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.
[1] (A) The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar? [2 marks]
(a) It detects recursion and eliminates recursion
(b) It detects reduce-reduce conflict, and resolves
(c) It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action.
(d) It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action.[2] (B) Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize? [2 marks]
(a) Equal precedence and left associativity; expression is evaluated to 7
(b) Equal precedence and right associativity; expression is evaluated to 9
(c) Precedence of ‘×’ is higher than that of ‘+’, and both operators are left associative; expression is evaluated to 7
(d) Precedence of ‘+’ is higher than that of ‘×’, and both operators are left associative; expression is evaluated to 9asked in Computer Science And Engineering, 2005
View Comments [0 Reply]
-
4.
Statement for Linked Answer Questions :
Let s and t be two vetices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X,Y] be a partition of V such that s ε X and Tε Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.[1] (A) The edge e must definitely belong to: [2 marks]
(a) the minimum weighted spanning tree of G
(b) the weighted shortest path from s to t
(c) each path from s to t
(d) the weighted longest path from s to t[2] (B) Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion? [2 marks]
(a) a path from s to t in the minimum weighted spanning tree
(b) a weighted shortest path from s to t
(c) an Euler walk from s to t
(d) a Hamiltonian path from s to tasked in Computer Science And Engineering, 2005
View Comments [0 Reply]
-
5.
Statement for Linked Answer Questions ::
Consider the following C-function:
double foo (int n) {
int i;
double sum;
if (n==0) return 1.0;
else {
sum = 0.0;
for (i =0; i<n; i++)
sum +=foo(i);
return sum;
} }
[1] (A) The space complexity of the above function is: [2 marks]
(a) O(1)
(b) O(n)
(c) O(n!)
(d) O(nn)[2] (B) Suppose we modify the above function foo() and store the values of foo(i), 0<=I<n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:
[2 marks]
(a) O(1)
(b) O(n)
(c) O(n2)
(d) O(n!)asked in Computer Science And Engineering, 2005
View Comments [0 Reply]
-
6.
Consider the following data path of a CPU.
The ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation – the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.
[1] The instruction “add R0, R1” has the register transfer interpretation R0<= R0+R1. The minimum number of clock cycles needed for execution cycle of this instruction is:
[2 marks]
(a) 2
(b) 3
(c) 4
(d) 5[2] The instruction ‘call Rn, sub” is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is
Rn<= PC+1;
PC<=M[PC];
The minimum number of CPU clock cycles needed during the execution cycle of this instruction is: [2 marks]
(a) 2
(b) 3
(c) 4
(d) 5asked in Computer Science And Engineering, 2005
View Comments [0 Reply]