Q.1. Data Structure and Algorithms
In a box there are random number of white and black marbles. At a time two marbles are taken out at random and if

A) Both Black: Discard both and insert a white
B) Both White: Discard one and retain one
C) One Black and One White: Discard White and retain Black.

If initially there are nb black and nw white marbles then determine the color of the only marble remaining at the end.

Options
1. white if nb is even
2. white if nw is odd
3. black if nb is even
4. black if nw is odd

Ans: 1

Explanation:
Here parity of black is preserved and the parity of white is neglected.

Lets consider each case
A) Both Black: Discard both and insert a white Parity of back is preserved by discarding both, i.e if there are nb marbles then nb-2 remain. Thus if nb is even, nb-2 is also even. For nw, it becomes nw+1 and hence parity is changed(or is not conserved).

B) Both White: Discard one and retain one Again no change to nb and nw parity is neglected.
C) One Black and One White: Discard White and retain Black. Same applies here also.

Thus, the color of last marble depends on nb and not on nw.

Hence, we get the following table:

nb	nw	remaining
even	even	white
even	odd	white
odd	even	black
odd	odd	black

which can be further reduce to :

nb	nw	remaining
even	X	white
odd	X	black

---

Q.3. Databases
Consider three tables with following number of tuples in each

S(a,b,c) = 100
R(a,d,e) = 80
T(x,d,f) = 90

Tuples in S and R with same value of attribute "a" = 60
Tuples in R and T with same value of attribute "d" = 70

Maximum and minimum number of tuples in (S left outer join R) full outer join T is:

Options
1. 130 120
2. 150 140
3. 140 130
4. 140 120

Ans: 3

Explanation:
Consider, X = ( S left outer join R ) This will have 100 rows, with d = null for 40(100-60) rows.

X full outer join T: Here, the common values of d in tables X and T can be between 50 and 60.

Case 1: Minimum value of common values of d between X and T
Out of 80 values of d in R, 20 were not found in X (since X has only 60 non-null values of d). These 20 can all be the ones that were common between S and T. In this case the common values between X and T will be 50.

Case 2: Maximum value of common values of d between X and T
Now assume that 20 values of d that were lost, none was common between S and T. But this is not possible, because S has 80 tuples and 70 values are common with T. So at least 10 common values will get lost. Thus max. value of common d's will b 60.

Now full outer join (X + T - common values of d in X and T) will be either
100 + 90 - 50 or 100 + 90 - 60.

Thus the answer is 140,130. Hence 3

---

Q.4. Data Structures - Hashing
A hash table implementation uses function of (% 7) and linear probing to resolve collision. What is the ratio of numbers in the following series with out collision and with collision if 7 buckets are used:
32, 56, 87, 23, 65, 26, 93

Options
1. 2,5
2. 3,4
3. 4,3
4. 5,2

Ans: 3

Explanation:
Since we're using mod 7 hash function, we've a hash table with 7 buckets numbered from 0 to 6. Any number x will be mapped to x % 7 bucket.

Lets look at the insertion of sequence into hash table:

1. 32 is inserted into 32 % 7 = 4 i.e. 4th bucket.

0	1	2	3	4	5	6
				32

2. 56 is inserted into 56 % 7 = 0 i.e. 0th bucket.

0	1	2	3	4	5	6
56				32

3. 87 is inserted into 87 % 7 = 3 i.e. third bucket.

0	1	2	3	4	5	6
56			87	32

3A
4. 23 is inserted into 23 % 7 = 2

0	1	2	3	4	5	6
56		23	87	32

5. 65 is inserted 65 % 7 = 2. Since bucket 3 also contains 23, its a collision. We'll put 65 into the next empty bucket i.e. 5

0	1	2	3	4	5	6
56		23	87	32	65

6. 26 is inserted into 26 % 7 = 5. However, since bucket 5 is also full, its a collision and 26 is inserted into the next empty bucket i.e. 6.

0	1	2	3	4	5	6
56		23	87	32	65	26

7. 93 is inserted into 93 % 7 = 2. However, since bucket 2 is also full, its a collision and 93 is inserted into the next empty bucket i.e. 1.

0	1	2	3	4	5	6
56	93	23	87	32	65	26

Final position of buckets will be:

Bucket #	Element	Remark
0	56
1	93
2	23 - 65 - 93
	65 ( move to next empty - 5)	Collision
	93 ( move to next empty - 1)	Collision
3	87
4	32
5	65 - 26
	26 (move to next empty - 6)	Collision
6	26

---

Q.5. Computer Organization
In a certain machine data references constitute 40% of the mix, and that the ideal CPI of the pipelined machine is 1. Assume that the machine with structural hazards has a clock rate that is 1.05 times higher than the clock rate of machine without hazard. What is effective speedup with pipelining without structural hazard?

Options
1. 1.05
2. 1.3
3. 1
4. none of above

Ans: 2

Explanation:
We major the average instruction time on both the machines to access speedup/slowdown.

Avg. instruction time = CPI * clock cycle time

Since there are no stalls/hazards, the average instruction time for ideal machine is the clock cycle times.

The average clock cycle time for the machine with 40% structural hazard is M
= (1+0.4 x 1) x Clock cycle time ideal/1.05 = 1.3 clock cycle time ideal

Machine without structural hazard is 1.3 times faster.