|
Q.31 - Q.76 Carry Two Marks Each.
31. Let f be a function from a set A to a set B, g a function from B to C,
and h a function from A to C, such that h (A) = g(f (A))for all a E A.
Which of the following statements is always true for all such functions f and g?
(A) g is onto h is onto
(B) h is onto f is onto
(C) h is onto g is onto
(D) h is onto f and g are onto
32. Let A be a set with n elements. Let C be a collection of distinct subsets
of A such that for any two subsets S1 and S2 in C, either S1 S or 2 S1.
What is the maximum cardinality of C?
(A) n
(B) n+1
(C) 2fh+1
(D)n!
33. An unbiased coin is tossed repeatedly until the outcome of two successive
tosses is the same. Assuming that the trials are independent, the expected number
of tosses is:
(A) 3
(B) 4
(C) 5
(D) 6
34. Let n = p2q,where p and q are distinct prime numbers. How many numbers m
satisfy 1 m nand gcd(m,n) = 1? Note that gcd(m,n) is the greatest common
divisor of m and n.
(A) p(q�i)
(B) pq
(D) p(p�i)(q�i)
(C) 1 (D)t
35. What is the value of [(x � r)3 (sin x) dx
(A) -1
(B) 0
36. Let P(x) and Q(x) be arbitrary predicates. Which of the following
statements is always TRUE?
(A) ((vxP (x) v Q (x))) ((vx ( (x) v (vxQ (x)))
(B) (vx(P (x) Q(x))) ((vx(P (x) (vxQ(x)))
(C) (vx(P(x)) (vxQ(x))) ((vx(P(x) Q(x)))
(D) (vx(P(x))) (vxQ(x)))
37. Consider the non-deterministic finite automation (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the
NFA with Y as the only accepting state be Li. Similarly, let the language accepted
by the NFA with Z as the only accepting state be L2. Which of the following
statements about Li and L2 is TRUE?
(A) Li = L2
(B) LicL2
(C) L2cLi
(D) None of the above
38. Let P be a non-deterministic pushdown automaton (NPDA) with exactly one state,
q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as
well as the accepting state of the PDA. The stack is initialized with one Z before
the start of the operation of the PDA. Let the input alphabet of the PDA be .
Let L(P) be the language accepted by the PDA by reading a string and reaching
its accepting state. Let N(P) be the language accepted by the PDA by reading
a string and emptying its stack.
Which of the following statements is TRUE?
(A) L(P) is necessarily *but N(P) is not necessarily *
(B) N(P) is necessarily * but L(P) is not necessarily *
(C) Both L(P) and N(P) is necessarily E*
(D) Neither L(P) nor N(P) are necessarily *
39. Consider the regular grammar:
S - XaYa
X-Za
Z - S a B
Y � Wa
W - Sa
Where S is the starting symbol, the set of terminals is {al and the set of non-
terminals is {S,W,X,Y,Z}. We wish to construct a deterministic finite automaton
(DFA) to recognize the same language. What is the minimum number of states
required for the DFA?
(A) 2
(B) 3
(C) 4
(D) 5
40. A language L satisfies the Pumping Lemma for regular languages, and also
the Pumping Lemma for context free languages. Which of the following statements
about L is TRUE?
(A) L is necessarily a regular language
(B) L is necessarily a context free language, but not necessarily a regular language
(C) L is necessarily a non-regular language
(D) None of the above
41. Given below is a program which when executed spawns two concurrent processes:
Semaphore X:=0;
1* Process now forks into concurrent processes P1 & P2 *1
P1 : repeat forever P2 : repeat forever
V(X); P(X);
Compute; Compute;
P(X); V(X);
Consider the following statements about processes P1 and P2:
I: It is possible for process P1 to starve.
II. It is possible for process P2 to starve.
Which of the following holds?
(A) Both I and II are true
(B) I is true but II is false
(C) II is true but I is false
(D) Both I and II are false
42. Two concurrent processes P1 and P2 use four shared resources
Ri, R2, R3 and R4, as shown below.
P1: P2:
Compute; Compute;
Use Ri; Use Ri;
Use R2; Use R2;
Use R3; Use R3;
Use R4; Use R4;
Both processes are started at the same time, and each resource an be accessed by
only one process at a time. The following scheduling constraints exist between
the access of resources by the processes:
P2 must complete use of Ri before P1 gets access to Ri.
P1 must complete use of R2 before P2 gets access to R2.
P2 must complete use of R3 before P1 gets access to R3.
P1 must complete use of R4 before P2 gets access to R4.
There are no other scheduling constraints between the processes. If only binary
semaphores are used to enforce the above scheduling constraints, what is the
minimum number of binary semaphores needed?
(A) 1
(B) 2
(C) 3
(D) 4
43. We have two designs Di and D2 for a synchronous pipeline processor.
Di has 5 pipeline stages with execution times of 3 nsec, 2 nsec, 4 nsec, 2 nsec
and 3 nsec while the design D2 has 8 pipeline stages each with 2 nsec
execution time. How much time can be saved using design D2 over design
Di for executing 100 instructions?
(A) 214 nsec
(B) 202 nsec
(C) 86 nsec
(D)-200 nsec
44. A hardwired CPU uses 10 control signals Si to SiO in various time
steps Ti to T5 to implement 4 instructions ii to 14 as shown below.
| |
T1 |
T2 |
T3 |
T4 |
T5 |
| L1 |
S1,S3,S5 |
S2,4,S6 |
S1,S7 |
Sb |
S3,S8 |
| L2 |
S1,S3,S5 |
S8,S9,Sb |
S5,S6,S7 |
S6 |
Sb |
| L3 |
Si,S3,S5 |
S7,S8,Sb |
S2,S8,Sb |
Sb |
Si,S3 |
| L4 |
Si,S3,S5 |
S2,S6,S7 |
S5,Sb |
S6,S9 |
S10 |
Which of the following pairs of expressions represent the circuit for
generating control signals S5 and Sb respectively [(Ij+Ik)Tnindicates
that the control signal should be generated in time step Tnif the
instruction being executed is If or 1k].
(A) S5 =Ti + 12 .T3&SiO = (Ii + 13) .T4+ (12 + 14) .T5
(B) S5 = Ti + (12 + 14) . T3 & Sb = (Ii + 13) . T4 + (12 + 14) . T5
(C) S5 =Ti + (12 + 14) .T3&SiO = (12 + 13 + 14) .T2 + (Ii + 13) .T4+ (12
+ 14). T5
(D) S5 = Ti + (12 + 14) . T3 & Sb = (12 + 13) . T2 + 14. T3 +(Ii + 13) . T4 + (12 + 14) . T5
45. A line L in a circuit is said to have a stuck at 0 fault if the lien
permanently has a logic value 0. Similarly a line L in a circuit is said to
have a stuck at 1 fault if the line permanently has a logic value 1. a circuit
is said to have a multiple stuck at fault if one or more lines have stuck
at faults. The total number of distinct multiple stuck at faults possible
in a circuit with N lines is:
(A) 3�
(B) 3�' � 1
(C) 2�' � 1
(D) 2�'
|
