@lakhan..cn u plz explain
On Thu, Jan 13, 2011 at 10:48 PM, Lakhan Arya <lakhan.a...@gmail.com> wrote:
> Answer for question 6 maybe b)
> also for question 7 maybe b)
>
> On Jan 12, 2:14 pm, snehal jain <learner....@gmail.com> 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
> > 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
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
