GATE CS question library

Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the following sentence so that it is TRUE? “The shortest paths in $G$ under $w$ are shortest …

An organization requires a range of IP address to assign one to each of its $1500$ computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space $202.61.0.0/17$. The ISP wants to assign an address space to the organization which will minimize the …

In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported elements is $k$.

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.

Consider a non-pipelined processor operating at $2.5$ GHz. It takes $5$ clock cycles to complete an instruction. You are going to make a $5$- stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at $2$ GHz. In a given program, assume that $30\%$ are memory instructions, $60 \%$ …

A processor has $64$ registers and uses $16$-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a $4$-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are $8$ distinct I-type opcodes, then the maximum number of …

For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigma_{i=1}^n a_i x_i$ is an odd number is______________

Consider the following C functions. int fun1(int n) { static int i= 0; if (n > 0) { ++i; fun1(n-1); } return (i); } int fun2(int n) { static int i= 0; if (n>0) { i = i+ fun1 (n) ; fun2(n-1) ; } return (i); } The return value of $\text{fun}2 (5)$ is _________

Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

Consider the following C functions. int tob (int b, int* arr) { int i; for (i = 0; b>0; i++) { if (b%2) arr [i] = 1; else arr[i] = 0; b = b/2; } return (i); } int pp(int a, int b) { int arr[20]; int i, tot = 1, ex, len; ex = a; len = tob(b, arr); for (i=0; i<len ; i++) { if (arr[i] ==1) tot = tot * ex; ex= ex*ex; } return (tot) ; } The value returned …

Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________

Consider the following set of processes, assumed to have arrived at time $0$. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order$P_1, P_2, P_3, P_4$. …

Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

Consider a paging system that uses $1$-level page table residing in main memory and a $\textsf{TLB}$ for address translation. Each main memory access takes $100$ ns and $\textsf{TLB}$ lookup takes $20$ ns. Each page transfer to/from the disk takes $5000$ ns. Assume that the $\textsf{TLB}$ hit ratio is $95 \%$, page fault rate is $10 \%$. …

Consider a database implemented using $B^+$ tree for file indexing and installed on a disk drive with block size of $\text{4 KB}$. The size of search key is $\text{12 bytes}$ and the size of tree/disk pointer is $\text{8 bytes}$. Assume that the database has one million records. Also assume that no node of the $B^+$ tree and no records are present …

Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Consider a $\textsf{TCP}$ connection between a client and a server with the following specifications; the round trip time is $6$ ms, the size of the receiver advertised window is $50$ KB, slow-start threshold at the client is $32$ KB, and the maximum segment size is $2$ KB. The connection is established at time $t=0$. Assume that there are no …

The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs.

The search engine’s business model ____ around the fulcrum of trust.

Ten friends planned to share equally the cost of buying a gift for their teacher. When two of them decided not to contribute, each of the other friends had to pay Rs. $150$ more. The cost of the gift was Rs. ____