-
1.
Statement for Linked Answer Questions ::
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j ) then it can move to either (i + 1, j ) or (i, j + 1).
[1] How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)? [2 marks]
(A) 20C10
(B) 220
(C) 210
(D) None of the above
[2] Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)? [2 marks]
(A) 29
(B) 219
(C) 8C4*11C5
(D) 20C10 - (8C4*11C5)
asked in Computer Science And Engineering, 2007
View Comments [0 Reply]
-
2.
Statement for Linked Answer Questions ::
A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1.[1] If optimal page replacement policy is used, how many page faults occur for the above reference string? [2 marks]
(A) 7
(B) 8
(C) 9
(D) 10[2] Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy? [2 marks]
(A) 0
(B) 1
(C) 2
(D) 3last reply by CpjJwWHV • 14 years ago • asked in Computer Science And Engineering, 2007
View Comments [1 Reply]
-
3.
Statement for Linked Answer Questions ::
Consider a machine with a byte addressable main memory of 216 bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.[1] How many data cache misses will occur in total? [2 marks]
(A) 48
(B) 50
(C) 56
(D) 59[2] Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time? [2 marks]
(A) line 4 to line 11
(B) line 4 to line 12
(C) line 0 to line 7
(D) line 0 to line 8asked in Computer Science And Engineering, 2007
View Comments [0 Reply]
-
4.
Statement for Linked Answer Questions::
Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b}as the terminal alphabet, S as the start symbol and the following set of production rules:
S →aB, S→ bA
B→ b, A→ a
B→ bS, A→ aS
B→ aBB, S →bAA
[1] Which of the following strings is generated by the grammar? [2 marks]
(A) aaaabb
(B) aabbbb
(C) aabbab
(D) abbbba[2] For the correct answer strings to above question, how many derivation trees are there?
[2 marks]
(A) 1
(B) 2
(C) 3
(D) 4asked in Computer Science And Engineering, 2007
View Comments [0 Reply]
-
5.
Statement for Linked Answer Questions
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32, respectively.
[1] Which of the following is the Huffman code for the letter a, b, c, d, e, f?
[2 marks]
(A) 0, 10, 110, 1110, 11110, 11111
(B) 11, 10, 011, 010, 001, 000
(C) 11, 10, 01, 001, 0001, 0000
(D) 110, 100, 010, 000, 001, 111[2] What is the average length of the correct answer to the above question ? [2 marks]
(A) 3
(B) 2.1875
(C) 2.25
(D) 1.9375asked in Computer Science And Engineering, 2007
View Comments [0 Reply]
-
6.
Consider the following Finite State Automaton:
[1] The language accepted by this automaton is given by the regular expression
[2 marks]
(A) b*ab*ab*ab*
(B) (a+b)*
(C) b*a (a+b)*
(D) b*ab*ab*
[2] The minimum state automaton equivalent to the above FSA has the following number of states [2 marks]
(A) 1
(B) 2
(C) 3
(D) 4asked in Computer Science And Engineering, 2007
View Comments [0 Reply]