COSC5313                             Test-1                            3/3/2011

 

Keys Used:

          1-5:             CBABA

          6-10:           ACCAA

          11-15:         ABABA

          16-21:         ACBBAA

 

Name:___________________________________

 

Part-A.  Multiple Choices                                                                  (72 points)

Answer 18 questions by writing down your best choice to the left of each question number

in CAPITAL. (if not following, you lose 10 points)

 

For the first six questions, consider the following LP problem in the standard form:

 

      Minimize  x1+ x2  +x3  subject to:

 

                  x1                            -2 x5           =   b1

                        x2            +  x4             =   b2

                                     x3             + x5    =   b3

                        x1, x2 , x3 , x4 , x5     >=  0

 

Assume that, for the first five questions, b1=b2=b3=100.

 

  1. Which is a feasible solution?

a.                   x1=x3=x4=100, x2=x5=0  

b.                   x1=x2=x3=100, x4=x5=0.                 c. both.             d. neither.

  1. Which set of basic variables represents a feasible solution?

a.                   x1, x2, x4

b.                   x1, x2, x5                           

c.                   x3, x4, x5                           

d.                   all above.                            e.  two above.               f.  none

 

  1. For the next two questions suppose that the initial basis is formed by x1, x2 and x3.

In this case, which non-basic variable is to become basic next?

       a.       x4                            b.    x5                                      c.  cannot tell

  1. In the above case, which basic variable is to become non-basic next?

       a.         x1                          b.   x2                           c.  x3                d.  none

 

  1. Which set of variables can form a basis regardless of  whether yielding a feasible solution or not?

a.                   x1, x2, x3

b.                   x3, x2, x4

c.                   x2, x3, x4                            d.  all above.                             e.  two above.

 

  1. Which is true  if  b1 = b2 = b3 =  -100 ?

a.                   the objective function has no feasible value.

b.                   the objective function has is unbounded (i.e., it can be as small as we wish).

c.                   both.                                   d. neither.

      *****************************************************

 

  1. Which is in O(n2)?

a.                   2*n2 + 10*n

b.                   100*n*log (n*n*n)                           c. both.             d. neither.

  1.  Which is in W(n2)?

a.                   O(n2)  

b.                   12*n3                                              c. both.             d. neither. 

  1.  Suppose that g(n) = W(f(n))  . Which is true in this case?

a.                   f(n) = O(g(n))

b.                   g(n) = q (f(n))                                 c. both.             d. neither.

  1.  O(f(n)+2*g(n)) is the same as

a.                   max(O(f(n)), O(g(n)))

b.                   O (g(n))                                          c. both.             d. neither.

  1.  Time complexity of the Select Sorting and that of the Heap Sorting is

a.                   quadratic and O(n*log(n)), respectively.

b.                   both quadratic.       

  1. Given a fixed number of balls and of cells, respectively, which count is the largest?

a.                   NYN(n,k)

b.                   NYY(n,k)

c.                   NNY(n,k)                                       d. cannot tell. 

  1. Which is the count of YYY(n, k) when exactly one cell is unoccupied assuming that there are at least two cells?

a.                   k*YYN(n, k-1)

b.                   YYY(n, k) -  YYN(n, k)                  c. both.             d. neither.

  1.             (2x+1)2*n where n is a positive integer.

a.                   above is the ordinary generating function for the sequence    (c(2*n, k)), k=0,1,2,…,2*n

b.                   above is the ordinary generating function for the sequence (2kc(2*n, k)), k=0,1,2,…,2*n

c.                   neither.

  1.             e2x

a.                   it is the exponential generating function for the sequence, (1, 2, 22, 23, 24    … )

b.                   it is the exponential generating function for the sequence, (1, 2/1!, 22/2!, 23/3!, 24 /4! …)

c.                   neither.

 

  1.             a0t(m) + a1t(m-1) + a2 t(m-2) = 5m2  

 For the above recurrence relation, the characteristic function is

a.                   (a0 x2 + a1 x+ a2) (x-1)3  

b.                   (a0 x2 + a1 x+ a2) (x-1)2  

c.                   neither.           

 

  1.             (x-2)(x-3)2  =  0

Suppose that above is the characteristic function for a recurrence relation.

In this case, the general solution is, for some constants, c1, c2, c3, and c4,

a.                   c1*2m  + c2*3m      

b.                   c1*2m  + c2*3m  +  c3*m*3m

c.                   c1*2m  + c2*3m  +  c3*m*3m  + c4*m*m*3m

d.                   none above.                

 

 

      Next three questions are about a board B of size 5-4 with three available squares:

                        (1, 1)

                        (2, 2)

                        (3, 4)

 

  1. R(B), Rook Polynomial,  is

a.                   1 + 3x  +  3x2     

b.                   1 + 3x  +  3x2   + x3     

c.                   1 + 3x  +  4x2    

d.                   None

  1. Let B’ be the complement of this board B.  The coefficient of the highest exponent term of R(B’), Rook Polynomial,  is

a.                   5*4*3*2 – 3*4*3*2 + 3*3*2

b.                   5*4*3*2 – 3*4*3*2 + 3*3*2 – 1*2

c.                   5*4*3*2 – 3*4*3*2 + 3*3*2 – 1

d.                   none                                                                                                         

  1. The count of all possible placements of 3 rooks onto this board (assuming that all 20 squares are available) is

a.                    5*4*3*4

b.                   5*4*3

c.                    neither. 

 

21.     for (k=1; k<=n; k++)

         for (m=1; m<=n; m++)

                for (j=1; j<=m; j++)

                          return 100*k+10*m+j;

The time complexity of the above is

a.        O(n3)  

b.       O(n2)  

c.        O(n)  

d.       None above.

 

PART-B.         Other problems.                                                         (28 points)

Do three problems.

 

A.  You have six distinguishable men and four distinguishable women.

1.      In how many different ways do you distribute these men to these women so that exactly one woman does not get a man at all?

2.      In how many ways do you distribute these men to women so that the four women get 1, 1, 2, and 2 men, respectively? 

 

B.     Give the Time Complexity function for:

int what (int k)

{          if (k==0  || k==1) return k;  

            else   return what(k-1)*what(k-2);   }

 

C.     Consider the standard LP problem.

   Show that if X1 and X2 are two distinct optimal solutions, then every convex

   combination of X1 and X2 is also an optimal solution.

 

D.     Minimize  2*x1 +  x2  - 2*x3  subject to:

 

                        x1         + 5* x3               -   x5                 =   10

                        x2                - x4       +   x5                       =   10

                        x1, x2 , x3 , x4 , x5     >=  0

 

           Find the first two basic feasible solutions and values of the objective function.