for second question answer is b On Thu, Jan 13, 2011 at 4:41 AM, Anand <[email protected]> wrote:
> > > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, "Let's not do it your way or my way; let's do it the best way." -- 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.
