>

Question 1

The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students doubled in 2009, by what percent did the number of male students increase in 2009?

•
.

•   Question 2

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by p Then 100p= _____________.

•
.

Correct answer is =11.85 - 11.95

Solution :
p= P [at least three computers are working]
=P (3 or 4 computers working)
= (4C3) * (6C1) / 10C4 + 4C4 / 10C4 = 5/42
100p=11.9

•   Question 3

Each of the nine words in the sentence ”The quick brown fox jumps over the lazy dog” is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is _____________. (The answer should be rounded to one decimal place.

•
.

•   Question 4

The maximum number of edges in a bipartite graph on 12 vertices is __________________________.

•
.

Solution :
The number of edges in a bipartite graph on n-vertices is atmost n2/4
The maximum number of edges in a bipartite graph on 12 –vertices is n2 /4 = 12*12 /4 = 36

•   Question 5

If the matrix A is such that
Then the determinant of A is equal to ________.

•
.

Solution :
|A| = 0

•   Question 6

Consider the equation (123)5 = (x8)y with x and y as unknown. The number of possible solutions is _____ .

•
.

Solution :
(123)5 = (x8)y
Converting both sides to decimal:
25 +10 +3 = xy+ 8
xy +8=38 => xy=30
x=1 , y=30
or , x=2 , y=15 or x=3 , y=10
Total number of solutions: 3

•   Question 7

A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits for the TAG field is _____

•
.

Solution :
tag = 32 - (7+5) =20 bits

•   Question 8

Consider the function func shown below:
int func(int num)
{
int count = 0;
while (num)
{
count++;
num>>= 1;
}
return (count);
}
The value returned by func(435)is __________.

•
.

•   Question 9

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 x 106 bytes disk on which the file system is stored and data block size is 103 bytes, the maximum size of a file that can be stored on this disk in units of 106 bytes is ____________.

•
.

Correct answer is =99.55 - 99.65

Solution :
Number of entries in the FAT = Disk Capacity/Block size = 108/103 = 105
Total space consumed by FAT = 105 * 4 B = 0.4 * 106 B
Maximum size of file that can be stored = 100 * 106 – 0.4 * 106 = 99.6 * 106 B 

•   Question 10

The maximum number of super keys for the relation schema R (E, F, G, H) with E as the key is __________.

•
.

Solution :
The maximum number of super keys for the relation schema R(E,F,G,H) with E as the key is 23 = 8 as any subset of non key attributes along with key attribute will form the super key of R.
As we have 3 nonkey all (F, G and H) so subsets will be 23

•   Question 11

Given an instance of the STUDENTS relation as shown below For (StudentName, StudentAge) to be a key for this instance, the value X should NOT be equal to____________

•
.

Solution :
For (Student Name, student age) to be a key for given instance of STUDENTS relation, the pair value should not get repeated in any two tuples p and q (uniqueness in forced by the definition of key)
Output :-
Shankar age should not b 19
Shankar 19

•   Question 12

In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender S and traverses to R, as shown. The links within each ISP and across the two ISPs, are all point-to-point’ optical links. The initial value of the TTL field is 32. The maximum possible value of the TTL field when R receives the datagram is ____________.

•
.

Solution :
The TTL field is set by the sender of the datagram, and reduced by every router on the route to its destination. So, there are 5visits at 5 routers and one visit at receiver R in above figure which leads 32 – 6 = 26.

•   Question 13

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires tc CPU milliseconds and then initiates a single I/O operation that lasts for tio milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:
The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.

•
.

Solution :
There are three processes A, B and C that run in round robin manner with time slice of 50 ms. Processes atart at 0, 5 and 10 miliseconds. The processes are executed in below order A, B, C, A 50 + 50 + 50 + 50 (200 ms passed) Now A has completed 100 ms of computations and goes for I/O now B, C, B, C, B, C 50 + 50 + 50 + 50 + 50 + 50 (300 ms passed) C goes for i/o at 500ms and it needs 500ms to finish the IO. So C would complete its first IO at 1000 ms

•   Question 14

Consider two strings A "= q pqrr " and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

•
.

Solution :
Given is
A = “qpqrr”
B = “pqprqrp”
The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:
(1) qpqr
(2) pqrr
(3) qprr
So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34.

•   Question 15

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

•
.

Solution :
The implementation of optimal algorithm for merging sequences is as follows. In it total number of comparisons is (44-1)+(94-1)+(65-1)+(159-1) = 358

•   Question 16

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.

•
.

•   Question 17

Consider the following function
double f (double x) {
if ( abs (x*x – 3) < 0. 01) return x;
else return f (x / 2 + 1.5/x);
}
Give a value q (to 2 decimals) such that f (q) will return q:______

•
.

Correct answer is =1.72 - 1.74

Solution :
If condition given in function definition should be ‘TRUE’, for f (q) to return value q. The condition is as follows:
if (abs(x ×x - 3)<0.01) return x;
The above condition will be true when x=1.73.

•   Question 18

The product of the non-zero eigenvalues of the matrix is

•
.

•   Question 19

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .

•
.

Correct answer is =0.259 - 0.261

Solution :
Let A = divisible by 2, B = divisible by 3 and C = divisible by 5, then
n(A) = 50, n(B) = 33, n(C) = 20
n(A ∩ B) = 16 (100/6)
n(A ∩ C) = 10 (100/10)
n(B ∩ C) = 6 (100/15)
n(A ∩ B ∩ C) = 3 (100/(2*3*5))
Now find n(A U B U C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ B) -n(B ∩ C) + n(A ∩ B ∩ C)
(100 - n(A U B U C))/100
Substituting the values we get answer as 0.26

•   Question 20

The number of distinct positive integral factors of 2014 is _________________________

•
.

Solution :
2014 = 2×19×53 i.e., product of prime factors
Number of distinct positive integral factors of 2014 is (2)×(2)×(2) = 8.

•   Question 21

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

•
.

Solution :
Consider a cycle on five vertices C5
C5 and C5` are isomorphic

•   Question 22

The number of distinct minimum spanning trees for the weighted graph below is

•
.

•   Question 23

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in 1 millisecond is ____________

•
.