GATE CSE
f1 = 2n f2 = n3/2
f3(n) = $$n\,\log _2^n$$
f4 (n) = n log2n


Let Li, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize Ln−1=1.
For all i such that $$0 \leq i \leq n-2$$
$$L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$$
Finally, the length of the longest monotonically increasing sequence is max(L0, L1,…,Ln−1)
Which of the following statements is TRUE?
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:
The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following
N1 : ( 0, 1, 7, 8, 4 )
N2 : ( 1, 0, 6, 7, 3 )
N3 : ( 7, 6, 0, 2, 6 )
N4 : ( 8, 7, 2, 0, 4 )
N5 : ( 4, 3, 6, 4, 0 )
After the update in the previous question, the link N1-N2 goes down. N2 will reflect this change immediately in its distance vector as cost, $$\infty $$. After the NEXT ROUND of update, what will be the cost to N1 in the distance vector of N3?
The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following
N1 : ( 0, 1, 7, 8, 4 )
N2 : ( 1, 0, 6, 7, 3 )
N3 : ( 7, 6, 0, 2, 6 )
N4 : ( 8, 7, 2, 0, 4 )
N5 : ( 4, 3, 6, 4, 0 )
The cost of link N2 - N3 reduces to 2 in (both directions). After the next round of updates, what will be the new distance vector at node, N3?
m1: Send an email from a mail client to a mail server
m2: Download an email from mailbox server to a mail client
m3: Checking email in a web browser
$$\,\,\,\,$$$$1$$ Valid bit
$$\,\,\,\,$$$$1$$ Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache.
What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?

What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation?
$$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 speed up when the $$DMA$$ controller based design is used in place of the interrupt driven program based input- output?
$$ * \,\,\,\,\,\,\,\,\,\,\,$$ 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 when 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?
$$LOOP:$$ Load a byte from device Store in memory at address given by address register $$$\eqalign{ & Increment\,\,\,the\,\,\,address\,\,register \cr & Decrement\,\,\,the\,\,count \cr & If\,\,\,count!\,\,\, = 0\,\,\,go\,\,\,to\,\,\,LOOP \cr} $$$
Assume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is 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 speed up when the $$DMA$$ controller based design is used in place of the interrupt driven program based input-output?
Database table by name Loan_Records is given below.
Borrower | Bank_Manager | Loan_Amount |
---|---|---|
Ramesh | Sunderajan | 10000.00 |
Suresh | Ramgopal | 5000.00 |
Mahesh | Sunderajan | 7000.00 |
What is the output of the following SQL query?
SELECT count(*)
FROM (
(SELECT Borrower. Bank_Manager FROM Loan_Records) AS S
NATURAL JOIN
(SELECT Bank_Manager, Loan_Amount FROM Loan_Records) AS T );
Consider a database table T containing two columns X and Y each of type integer. After the creation of the table, one record (X = 1, Y = 1) is inserted in the table.
Let MX and MY denote the respective maximum values of X and Y among all records in the table at any point in time. Using MX and MY, new records are inserted in the table 128 times with X and Y values being MX + 1, 2*MY + 1 respectively. It may be noted that each time after the insertion, values of MX and MY change.
What will be the output of the following SQL query after the steps mentioned above are carried out?
SELECT Y FROM T WHERE X=7;
$$Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$$ where is a constant
$$Q2: \pi_{A_1, \dots ,A_p} \left(\sigma_{c_1 \leq A_p \leq c_2}\left(r\right)\right)$$ where c1 and c2 are constants
The database can be configured to do ordered indexing on Ap or hashing on Ap. Which of the following statements is TRUE?
$$1.$$ $$Registration$$ $$Num:$$ Unique registration number of each registered student.
$$2.$$ $$UID :$$ Unique identity number, unique at the national level for each cityzen.
$$3.$$ $$BankAccount_Num:$$ Unique account number at the bank. A student can have multiple accounts or joint accounts. This attribute stores the primary account number.
$$4.$$ $$Name:$$ Name of the student
$$5.$$ $$Hostel$$ $$Room:$$ Room number of the hostel.
Which of the following options is INCORRECT?
$$\left( {P + \overline Q + \overline R } \right).\left( {P + \overline Q + R} \right).\left( {P + Q + \overline R } \right)$$ is

If all the flip-flops were reset to $$0$$ at power on, what is the total number of distinct outputs (states) represented by $$PQR$$ generated by the counter?

If at some instance prior to the occurrence of the clock edge, $$P, Q$$ and $$R$$ have a value $$0,1$$ and $$0$$ respectively, what shall be the value of $$PQR$$ after the clock edge?
$$P\left( x \right) = \neg \left( {x = 1} \right) \wedge \forall y\left( {\exists z\left( {x = y * z} \right) \Rightarrow \left( {y = x} \right) \vee \left( {y = 1} \right)} \right)$$
Which one of the following statements is TRUE in relation to these graphs?
Which of the following options provides the Correct values of the Eigen values of the matrix?
Which of the following is TRUE?
$$ * \,\,\,$$ 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 when a key is pressed or release)
$$ * \,\,\,$$ Interrupt from Hard Disk (raises interrupt when a disk read is completed)>/p>
Which one these will be handled at the HIGHEST priority?
Process | Arrival Time | Burst Time |
---|---|---|
P0 | 0 ms | 9 ms |
P1 | 1 ms | 4 ms |
P2 | 2 ms | 9 ms |
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only a arrival or completion of processes. What is the average waiting time for the three processes?
char c[ ] = "GATE2011";
char *p = c;
printf("%s", p + p[3] - p[1]);
unsigned int foo (unsigned int n, unsigned int r) {
if (n > 0) return((n % r) + foo(n/r, r));
else return 0;
}
What is the return value of the function foo when it is called as foo (513, 2)? unsigned int foo (unsigned int n, unsigned int r) {
if (n > 0) return((n % r) + foo(n/r, r));
else return 0;
}
What is the return value of the function foo when it is called as foo (345, 10)?Total cost of the project includes cost of development & maintenance. What is the $$LOC$$ for $${L_1}$$ for which the cost of the project using $${L_1}$$ is equal to the cost of the project using $${L_2}$$
$$i)$$ When coefficient $$a$$ is zero or irrespective of discriminate
$$ii)$$ When discriminate is positive.
$$iii)$$ When discriminate is zero
$$iv)$$ When discriminate is negative
Only in cases $$(ii)$$ & $$(iii)$$ the stored roots are valid Otherwise $$0$$ is stored in the roots the function returns $$0$$ when the roots are valid & - $$1$$ otherwise. The function also ensures root $$1$$ $$> =$$ root $$2.$$
int get QuadRoots(float a, float b, float c, float $${}^ * root1$$, float $${}^ * root2$$);
A software test engineer is assigned the job of doing block box testing. He comes up with the following test cases, many of which are redundant

Which one of the following options provide the set of non-redundant tests using equivalence class partitioning approach from input perspective for black box testing?
What is the minimum number of states needed in a $$DFA$$ to recognize $$L$$?
Which of the following statements is not TRUE?

Which of the following finite state machines is a valid minimal $$DFA$$ which accepts the same languages as $$D?$$