GATE CSE 2011
Q21.
Four matrices M1, M2, M3 and M4 are dimensions p x q, q x r, r x s and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example When multiplied as ((M_{1} \times M_{2})\times (M_{3}\times M_{4}) the total number of scalar multiplications is pqr+rst+prt. When multiplied as (((M_{1}\times M_{2})\times M_{3})\times M_{4}) , the total number of scalar multiplications is pqr+prs+pst. If p=10, q=100, r=20, s=5 and t=80, then the minimum number of scalar multiplications needed isQ22.
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array Which of the following statements is TRUE?Q23.
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?Q24.
On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory. Initialize the address register Initialize the count to 500 LOOP: Load a byte from device Store in memory at address given by address register Increment the address register Decrement the count If count != 0 go to LOOP Assume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute. The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory. What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven program based input-output?Q25.
A computer handles several interrupt sources of which the following are relevant for this question. Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high) Interrupt from Mouse (raises Interrupt if the mouse is moved or a button is pressed) Interrupt from Keyboard (raises Interrupt if a key is pressed or released) Interrupt from Hard Disk (raises Interrupt when a disk read is completed)Which one of these will be handled at the HIGHEST priority?Q26.
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?Q28.
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?Q29.
Consider the matrix as given below. \begin{bmatrix} 1 & 2&3 \\ 0& 4 & 7\\ 0&0 & 3 \end{bmatrix} Which one of the following provides the CORRECT values of eigenvalues of the matrix?Q30.
An undirected graph G(V, E) contains n (n>2) nodes named v1 , v2 ,...,vn. Two nodes vi , vj are connected if and only if 0\lt |i-j|\leq2. Each edge (vi,vj ) is assigned a weight i+j. A sample graph with n=4 is shown below. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?