1.1 Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

• There is a sample point at which X has the value 5.
• There is a sample point at which X has value greater than 5.
• There is a sample point at which X has a value greater than or equal to 5.
• None of the above.

1.2 The number of binary relations on a set with n elements is:

• n 2
• 2 n
• 
• None of the above

1.3 The number of binary strings of n zeros and k ones that no two ones are adjacent is

• n-1 C k
• n C k
• n C k+l
• None of the above

1.4 Consider the regular expression (0 + 1) (0 + 1)……..n times. The minimum state finite automation that recognizes the language represented by this regular expression contains

• n states
• n + I states
• n + 2 states

(d) None of the above

1.5 Context-free languages are closed under:

• Union , intersection
• Union , Kleene closure
• Intersection, complement
• Complement, Kleene Closure

1.6 Let L p be the set of all languages accepted by a PDA by final state and L E the set of all languages accepted by empty stack. Which of the following is true?

(a) L D = L E (b) L D É L E

(c) L D = L E (d) None of the above

1.7 Which of the following expressions is not equivalent to ?

• x NAND x
• x NOR x
• x NAND 1
• x NOR 1

1.8 Which of the following functions implements the Karnaugh map shown below?

(a)

(b) D (C + A)

(c)

(d)

1.9 Listed below are some operating system abstractions (in the left column) and the hardware components (in the right column)?

• Thread 1. Interrupt
• Virtual address space 2. Memory
• File system 3. CPU
• Signal 4. Disk

• (A)-2, (B)-4, (C)-3, (D)-1
• (A)-I, (B)-2, (C)-3, (D)-4
• (A)-3, (B)-2, (C)-4, (D)-1
• (A)-4, (B)-1, (C)-2, (D)-3

1.10 Which of the following disk scheduling strategies is likely to give the best through put?

• Farthest cylinder next
• Nearest cylinder next
• First come first served
• Elevator algorithm

1.11 System calls are usually invoked by using

• a software interrupt
• polling
• an indirect jump
• a privileged instruction

1.12 A sorting technique is called stable if

• it takes 0 (n log n) time
• it maintains the relative order of occurrence of non-distinct elements
• it uses divide and conquer paradigm

(d) it takes 0 (n) space.

1.13 Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

• n-I
• n
• n + 1
• None of the above