# Computer Science and Information Technology - GATE 2007 Paper Solution

Consider the following two statements the function f(x) = |x|:

P. f(x) is continuous for all real values of x
Q. f(x) is differentiable for all real values of x

Which of the following is TRUE?

Let S be a set of n elements. The number of ordered  pairs in the largest and the smallest equivalence relations on S are:

What is the maximum number of different Boolean functions involving n Boolean variables?

Let G be the non-planar graph with the minimum possible number of edges. Then G has

Consider the DAG with = V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

Which of the following problems is undecidable?

Which of the following is TRUE?

How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?

Consider the following Boolean function of four variables:

$f\left(w,x,y,z\right)=\sum \left(1,3,4,6,9,11,12,14\right)$

The function is

Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:

Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Which of the following sorting algorithms has the lowest worst-case complexity?

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is:

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.

 Group 1 Group 2 P. Gang Scheduling 1. Guaranteed Scheduling Q. Rate Monotonic Scheduling 2. Real-time Scheduling R. Fair Share Scheduling 3. Thread Scheduling

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?