Consider a 6-sided die with all sides not necessarily equally likely such that probability of an even number is P({2,4,6})=1/2, probability of a multiple of 3 is P({3,6})=1/3, and probability of 1 is P({1})=1/6. Given the above conditions, choose the strongest (most stringent) condition of the following that must always hold about P({5}), the probability of 5

Consider a circle with a circumference of one unit length. Let d < 1/6. Suppose that we independently throw two arcs, each of length d, randomly on this circumference so that each arc is uniformly distributed along the circle circumference. The arc attaches itself exactly to the circumference so that arc of length d exactly covers length d of the circumference. What can be said about the probability that the two arcs do not intersect each other?

The Boolean function obtained by adding an inverter to each and every input of an AND gate is:

What is logically equivalent to “If Kareena and Parineeti go to the shopping mall then it is raining”:

Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half (1/2). He repeatedly tosses the coin until he gets heads in two consecutive tosses. The expected number of coin tosses that Ram does is

A 1 X 1 chessboard has one (1) square, a 2 X 2 chessboards has five (5) squares. Continuing along this fashion, what is the number of squares on the (regular) 8 X 8 chessboard?

There is a set of 2n people: n male and n female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is

Consider a square of side length 2. We throw five points into the square. Consider the following statements:
(i) There will always be three points that lie on a straight line.
(ii) There will always be a line connecting a pair of points such that two points lie on one side of the line and one point on the other.
(iii) There will always be a pair of points which are at distance at most √2 from each other.
Which of the above is true:

Suppose that f(x) is a continuous function such that 0.4 ≤ f(x) ≤ 0.6 for 0 ≤ x ≤ 1. Which of the following is always true?

Consider two independent and identically distributed random variables X and Y uniformly distributed in [0, 1]. For α ϵ [0, 1], the probability that α max(X,Y) < XY is

Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has 4 corners: (i, j), (i + 1, j), (i + 1,j + 1), and (i, j + 1), where (i, j) is a pair of non-negative integers. Suppose a line segment ℓ connecting (0, 0) to (90, 1100) is drawn. We say that ℓ passes through a unit square if it passes through a point in the interior of the square. How many unit squares does ℓ pass through?

Consider the following recurrence relation:

Which of the following statements is TRUE?

Consider the following undirected connected graph G with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second-best minimum spanning tree is a spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in G.

Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)

Consider the following code fragment in the C programming language when run on a non-negative integer n.
int f(int n)
{
if(n==0 || n==1) return 1;
else
return f(n-1) + f(n-2);
}
Assuming a typical implementation of the language, what is the running time of this algorithm and how does it compare to the optimal running time for this problem?

First, consider the tree on the left.

On the right, the nine nodes of the tree have been assigned numbers from the set {1, 2,. .., 9} so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.

Let B consist of all binary strings beginning with a 1 whose value when converted to decimal is divisible by 7.

Let a, b, c be regular expressions. Which of the following identities is correct ?

Let K_n be the complete graph on n vertices labelled {1, 2,. .., n} with m = n(n — 1)/2 edges. What is the number of spanning trees of K_n?

Consider the following concurrent program (where statements separated by || within cobegin-coend are executed concurrently).
x:=1;
cobegin
x:= x+1 || x:= x+1 || x:=x+1
coend
Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of x at the end of execution of the program is

For a time-invariant system, the impulse response completely describes the system if the system is

Let h(t) be the impulse response of an ideal low-pass filter with cut-o↵ frequency 5kHz. Let g[n] = h(nT), for integer n, be a sampled version of h(t) with sampling frequency 1=10kHz. The discrete time filter with g[n] as its unit impulse response is a

The capacity of a certain additive white Gaussian noise channel of bandwidth 1 MHz is known to be 8 Mbps when the average transmit power constraint is 50 mW. Which of the following statements can we make about the capacity C (in Mbps) of the same channel when the average transmit power is allowed to be 100 mW?

Let X and Y be two independent and identically distributed random variables. Let Z = max(X, Y ) and W = min(X, Y ). Which of the following is true?

Consider a random variable X that takes integer values 1 through 10 each with equal probability. Now consider random variable
Y = min(7, max(X, 4)).
What is the variance of Y ?

Consider the following optimization problem
max (2x + 3y)
subject to the following three constraints
x + y ≤ 5,
x + 2y ≤ 10, and
x < 3.
Let z* be the smallest number such that 2x + 3y ≤ z* for all (x, y) which satisfy the above three constraints. Which of the following is true?

Consider a frog that lives on two rocks A and B and moves from one rock to the other randomly. If it is at Rock A at any time, irrespective of which rocks it occupied in the past, it jumps back to Rock A with probability 2/3 and instead jumps to Rock B with probability 1/3. Similarly, if it is at Rock B at any time, irrespective of which rocks it occupied in the past, it jumps back to Rock B with probability 2/3 and instead jumps to Rock A with probability 1/3. After the first jump, it is at Rock A. What is the limiting probability that it is at Rock A after a total of n jumps as n --> ∞?