On Wed, Jan 12, 2011 at 1:14 AM, snehal jain <[email protected]> wrote:
> 1. Quick-sort is run on two inputs shown below to sort in ascending > order > (i) 1,2,3, ….,n > (ii) n, n - 1, n - 2, …., 2, 1 > Let C1 and C2 be the number of comparisons made for the inputs (i) and > (ii) respectively. Then, > a) C1 < C2 > b) C1 > C2 > c) C1 = C2 > Answer is c http://codepad.org/8xpqfGwJ > d) We cannot say anything for arbitrary n > 2. Which of the following languages over {0, 1} is regular? > a) 0i1j such that i ≤ j > b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0 > c) All strings of 0s and 1s such that every pth character is 0 where p > is prime > d) None of the above > 3. We are given a set X = {x1, x2, ..., xn} where xi = 2i. A sample S > (which is a subset of X) is > drawn by selecting each xi independently with probability pi = 1 / 2. > The expected value of the > smallest number in sample S is: > a) 1 / n > b) 2 > c) sqrt(n) > d) n > 4. 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? > a) R is NP-complete > b) R is NP-hard > c) Q is NP-complete > d) Q is NP-hard > 5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s > (eg: d(101) = 5, d(011) = 3). > Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the > following statements is > true? > a) L is recursively enumerable, but not recursive > b) L is is recursive, but not context-free > c) L is context-free, but not regular > d) L is regular > Common data for questions 6 and 7 > The 2n vertices of a graph G corresponds to all subsets of a set of > size n. Two vertices of G are > adjacent if and only if the corresponding sets intersect in exactly 2 > elements > 6. The number of vertices of degree zero in G is: > a) 1 > b) n > c) 2n - 1 > d) None > 7. The number of connected components in G is: > a) 2n > b) n + 2 > c) n C 2 > d) None > 8. There are 5 nested loops written as follows, > int counter = 0; > for (int loop_1=0; loop_1 < 10; loop_1++) { > for (int loop_2=loop_1 + 1; loop_2 < 10; loop_2++) { > for (int loop_3=loop_2 + 1; loop_3 < 10; loop_3++) { > for (int loop_4=loop_3 + 1; loop_4 < 10; loop_4++) { > for (int loop_5=loop_4 + 1; loop_5 < 10; loop_5++) { > counter++; > } > } > } > } > } > What will be the value of counter in the end (after all the loops > finished running)? > a) 15C5 > b) 14C5 > c) 10C5 > d) 10 * 9 * 8 * 7 * 6 * 5 > Answer is D > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
