List of top Questions asked in GATE XE, GATE CS

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity \(\Theta(n)\)?

Consider a table \(T\), where the elements \(T[i][j]\), \(0 \leq i, j \leq n\), represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:

\[ T[0][k] = T[k][0] = 1 \quad \text{for } k = 0,1,2,\dots,n \] \[ T[i][j] = 2T[i-1][j] + 3T[i][j-1] \quad \text{for } 1 \leq i,j \leq n \]
Consider the following two algorithms to compute entries of \(T\). Assume that for both the algorithms, for all \(0 \leq i,j \leq n\), \(T[i][j]\) has been initialized to 1.

Algorithm \(B_1\):

For i = 1, 2, ..., n
    For j = 1, 2, ..., n
        T[i][j] = 2*T[i-1][j] + 3*T[i][j-1]

Algorithm \(B_2\):

For s = 2, 3, ..., 2n
    For i = 1, 2, ..., n
        For j = 1, 2, ..., n
            If (i + j == s)
                T[i][j] = 2*T[i-1][j] + 3*T[i][j-1]

Algorithm \(B_k\), \(k \in \{1,2\}\) is said to be correct if and only if it calculates the correct values of \(T[i][j]\), for all \(0 \leq i,j \leq n\), (as per the recursive formulation) at the end of the execution of the algorithm \(B_k\).

Which one of the following statements is true?

Consider the following functions, where \(n\) is a positive integer.

\[ n^{1/3}, \quad \log(n), \quad \log(n!), \quad 2^{\log(n)} \]

Which one of the following options lists the functions in increasing order of asymptotic growth rate?

Note: Assume the base of log to be 2.

Consider an array \(A = [10,\ 7,\ 8,\ 19,\ 41,\ 35,\ 25,\ 31]\). Suppose the merge sort algorithm is executed on array \(A\) to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array \(L\) and sorted right array \(R\) is said to be void if the output of the merge operation is the elements of array \(L\) followed by the elements of array \(R\).

The number of void merge operations among these 7 merge operations is ______.

Consider the following ANSI-C program.

#include <stdio.h>

int main(){
    int *ptr, a, b, c;
    a=5; b=11; c=20;
    ptr=&a; *ptr=c; ptr=&c;
    a=*(&b); c=*ptr-a;
    printf("%d",c);
    return(0);
}

The output of this program is ______.

Note: Assume that the program compiles and runs successfully.

For a real number \(a\), let \(I(a) = \displaystyle\int_{-1}^{1} (3x^2 - ax + 1)\, dx\). Which of the following statements is/are true?

Expedite, Hasten, Hurry,
Fill the blank by choosing a word with a meaning similar to that of the words given above.

Consider the system of linear equations given below.
\[ ax + y = b \] \[ 16x + ay = 24 \] Suppose the values of \(a\) and \(b\) are chosen such that the system of linear equations produce multiple solutions. Then the product of \(a\) and \(b\) is _____. (answer in integer)

A black square PQRS has been cut into two parts. One part of it is shown in Panel I. Which one of the shapes in Panel II is the other part?

The determinant of a \(4 \times 4\) matrix \(A\) is 3. The value of the determinant of \(2A\) is ____________.

Two tiles are missing in Panel I. Which one of the options in Panel II is the appropriate choice for the missing tiles?

Let \(R\) be a binary relation on the set \(\{1, 2, \ldots, 10\}\), where \((x,y) \in R\) if the product of \(x\) and \(y\) is square of an integer. Which of the following properties is/are satisfied by \(R\)?

Consider a function \(f:(0,1) \to \{0,1\}\) defined as follows.

For a real number \(r \in (0,1)\), \(f(r) = 1\) if the second digit after the decimal point in \(r\) is one of the four digits 2, 3, 6 and 7. Otherwise, \(f(r)\) is equal to 0.

The number of points in \((0,1)\) at which \(f\) is discontinuous is ____________.

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0. The word with physical address 0xA2C28 is mapped to the cache block number \(176_{10}\). The maximum possible size of the cache (in KB) is ______.

Note: \(1\text{K}=2^{10}\) and \(1\text{M}=2^{20}\)

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an average of 5 clock cycles to complete the execution of an instruction. To improve the performance, the system was pipelined with a goal of achieving an average throughput of one instruction per clock cycle. However, it could operate only at 1.2 GHz due to pipeline overheads. While executing a program in the pipelined design, 30% of instructions encountered a stall of 2 cycles due to pipeline hazards. The speed-up obtained by the pipelined design over the non-pipelined one for this program is ______ (rounded off to two decimal places).

Note: \(1\text{G}=10^{9}\)

Consider the following three ANSI-C programs, P1, P2, and P3.

P1:
#include <stdio.h>
int a=5;
int main(){
int a=7;
return(0);
}

P2:
#include <stdio.h>
int main(){
int a=5;
int a=7;
return(0);
}

P3:
#include <stdio.h>
int main(){
int a=5;
float a=7;
return(0);
}

Which one of the following statements is true?

Consider a new TCP connection between a sender and a receiver. The receiver advertised window is constant at 48 KB, the maximum segment size (MSS) is 2 KB, and the slow start threshold for TCP congestion control is 16 KB. Assume that there are no timeouts or duplicate acknowledgements. The number of rounds of transmission required for the congestion control algorithm of the TCP connection to reach the congestion avoidance phase is ______.

Note: \(1\text{K}=2^{10}\)

Let \(G\) be a weighted directed acyclic graph with \(m\) edges and \(n\) vertices. Given \(G\) and a source vertex \(s\) in \(G\), which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from \(s\) to all vertices that are reachable from \(s\) in \(G\)?

Consider the following ANSI-C function.

int func(int start, int end){
    int length=end+1-start;
    if((length<1)||(start<0)||(end<0)){ return(0); }
    if(length%3==0){
        return(func(start+1, end));
    } else if(length%3==1){
        return(1+func(start, end-1));
    } else {
        return(func(start+2, end));
    }
}

The maximum possible value that can be returned from this function is ______.

Note: Ignore syntax errors (if any) in the function.

Which one of the following options is not a property of Boolean Algebra?
Note: + is the OR operation, \(\cdot\) is the AND operation, and \('\) is the NOT operation.

Which one of the following CPU scheduling algorithms cannot be preemptive?

Consider three processes \(P1\), \(P2\), and \(P3\) running identical code, as shown in the pseudocode below. \(A\) and \(B\) are two binary semaphores initialized to \(1\) and \(0\), respectively. \(X\) is a shared variable initialized to \(0\). Each line in the pseudocode is executed atomically.

Pseudocode of P1, P2, and P3

Wait(A);
Print(*);
X = X+1;
If (X == 2)
 {
    Print($);
    Signal(B);
  }
Signal(A);
Wait(B);
Print(#);
Signal(B);

Assume that any of the three processes can start to execute first and context switching can happen between these processes at any arbitrary time and in any arbitrary order.

Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?

The values of Stock A and Stock B on a particular day are Rs. 50 and Rs. 80, respectively. An investor invests Rs. 100 in Stock A and Rs. 80 in Stock B. He sells all the stocks the next day when the value of Stock A is Rs. 55 and Stock B is Rs. 70. The profit made by the investor is Rs.

A system has a Translation Lookaside Buffer (TLB) that has a reach of \(1\) MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size \(4\) KB. The virtual address space is \(64\) GB and physical address space is \(1\) GB. If each TLB entry stores a \(4\)-bit process id, page number, frame number, and a \(2\)-bit control field, then the size of the TLB (in bytes) is ______. (answer in integer)

Note: \(1K=2^{10}\), \(1M=2^{20}\), \(1G=2^{30}\)

A day can only be cloudy or sunny. The probability of a day being cloudy is 0.5, independent of the condition on other days. What is the probability that in any given four days, there will be three cloudy days and one sunny day?