Consider the polynomial p(x) = a₀ + a₁x + a₂x² + a₃x³, where a_i ≠ 0, ∀_i. The minimum number of multiplications needed to evaluate p on an input x is:

Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X×Y and E be the set of all subsets of W. The number of functions from Z to E is:

The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?

A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:

For which one of the following reasons does Internet Protocol (IP) use the time-to- live (TTL) field in the IP datagram header?

Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

Consider the following grammar.

   S → S * E
   S → E
   E → F + E
   E → F
   F → id 

Consider the following LR(0) items corresponding to the grammar above.

(i) S → S * .E
(ii) E → F. + E
(iii) E → F + .E 

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

You are given a free running clock with a duty cycle of 50% and a digital waveform f  which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f  by 180°?

A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?

In a binary max heap containing n numbers, the smallest element can be found in time

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Consider the following C-program fragment in which i, j and n are integer variables.

 for (i = n, j = 0; i >0; i /= 2, j += i);  

Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

We are given a set X = {x₁, .... x_n} where xi = 2ⁱ. A sample S ⊆ X is drawn by selecting each x_i independently with probability p_i = 1/2. The expected value of the smallest number in sample S is:

Let L₁ = {0^n+m1ⁿ0^m|n,m ≥ 0}, L₂ = {0^n+m1^n+m0^m|n,m ≥ 0}, and L₃ = {0^n+m1^n+m0^n+m|n,m ≥ 0}. Which of these languages are NOT context free?

Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.

         
            1. T1 start
            2. T1 B old=12000 new=10000
            3. T1 M old=0 new=2000
            4. T1 commit
            5. T2 start
            6. T2 B old=10000 new=10500
            7. T2 commit

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?

For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is: