COSC5313                                                           Final Exam                                          12/15/2009  

 

Name (Please print, else you lose 10 points)

 

 

___________________________________

Throughout this exam, the following notations are used:

                a. GA:                    Greedy Algorithms.

                b. DP:                     Dynamic Programming

                c. BT:                     Backtracking

                d. PA:                     Probabilistic Algorithms.

                e. LP:                      Linear Programming

                f. RC:                     Restrictive Cutset.

                g. C(m,n):              Number of combinations of n objects out of m.

                h. B(m):                 Number of distinct binary trees of m nodes.

                i. M(m):                 Number of distinct multiplications of m chained-matrices.

j. T(m):                  Number of distinct triangulations of a polygon with m sides (and as many vertices)

k. P(m):                  Number of distinct Balanced Parenthesis Expressions with m pairs of parentheses.

l.  Bset(n):              Set of strong false witnesses of primality for n, a composite.

                m. MTL:                Minimum Total Load (Problem).

                n.  MST:                                Minimum Spanning Tree.

                0:  HAM(G):         The problem of finding a Hamiltonian cycle of the given undirected graph, G.

                p:  HAMD(G):      The decision problem of deciding whether or not the given undirected graph, G,

                                                has a Hamiltonian graph.

 

Part-A.                  Multiple Choice Questions.                                                              (144 points)

 

Write down your best choice to the left of each question number in CAPITAL (if not following, you lose 10 points).

 

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

 

Minimize  x1 +  x2  - 10*x3  subject to:

 

                        x1                               +  x5                    =   b1

                        x2       +    2*x4                                          =   b2  

                                      x3               -  x5                      =   b3

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

 

Assume that b1=b2=b3=10 unless specified otherwise.

 

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

a.                   x1, x2, x3

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, x5

b.                   x1, x2, x4

c.                    x2, x3, x5                                     

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

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

a.                   the objective function has an optimal minimum value.

b.                   the objective function has no feasible value (i.e., the objective function has no defined value satisfying all constraints)

c.                    both.                                               d. neither.

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

  1. Which is in O(n2)?

a.                   2*n2 + 10*n

b.                   n *log (n3)                                      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. Given a fixed number of balls and of cells, respectively, where n,k>2, which count is the largest?

a.                   NNY(n,k)

b.                   YNN(n,k)

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

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

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

b.                   YNN(n, k-1)                                  c. both.                   d.   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) = 4m * m3  

 For the above recurrence relation, the characteristic function is

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

b.                   (a0 x2 + a1 x+ a2) (x-4)4  

c.                    neither.             

 

  1.                 (x-2)(x-3)3  =  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* m2 * 3m

d.                   none above.                

 

For the next seven questions, consider the following flow network with 6 nodes and 8 edges:

(Note that each triple has the starting node, the terminating node and the edge weight in that order)

                        (1,2,20)

                        (1,4,20)

                        (2,3,6)

                        (3,6,30)

                        (4,3,20)

                        (4,5,6)

                        (4,6,10)

                        (5,6,6)

 

  1. Which is a Cutset?

a.                   {(1,2), (3,6), (4,5), (4,6)}

b.                   {(1,4), (3,6)}

c.                    both.                                               d.             neither.  

  1. Which is a Restrictive Cutset?

a.                   {(1,2), (3,6), (4,5), (4,6)}

b.                   {(1,4), (3,6)}

c.                    both.                                               d.             neither. 

  1. Which is an optimal topological ordering for the MTL?

a.                   1 – 2 -  4 – 3 – 5 - 6

b.                   1 – 4 -  2 – 3 - 5  - 6

c.                    both.                                               d.             neither.

  1.  The Max Flow is

a.                   26

b.                   28

c.                    32                                                   d.        none

  1.  MTL is

a.                   46

b.                   56

c.                    66.                                                  d.        none.

 

For the next two questions, assume that above flow network (which is really an acyclic weighted connected directed graph) is undirected instead. So, assume that we have a cyclic weighted connected undirected graph instead.

18.   What is the value of the MST for the entire resulting undirected graph?

a.                   30

b.                   38

c.                    50

d.                   none above

      19.   Which node can be included into an MST as the last node at all?

a.             node#4

b.                   node#6

c.                    both.                                                       d.    neither

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

      20.   Which returns either no solution or an exact solution and never a wrong solution?

                a.             Monte Carlo algorithms

                b.             Las Vegas algorithms

                c.             both                                        d.             neither.

 

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

                                (1, 1)

                                (2, 2)

                                (3, 2)

                                (4, 4)

 

21.      R(B), Rook Polynomial,  is

a.       1 + 4x  +  5x2     

b.     1 + 4x  +  5x2   + 2x3     

c.     1 + 4x  +  5x2                                          d.             None

22.      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 – 4*4*3*2 + 5*3*2

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

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

d.       none                                                                                                                                                       

 

       Next two questions are about the following two BPE’s: 

                   BPE1:  ( ( (  ) ) ) ( ) ( )

                   BPE2:  ( (  ) ( ) ) ( ( ) )

 

23.    The rank of BPE2 is

a.       Catalan(4)*Catalan(0) + Catalan(3)*Catalan(1) + Catalan(2)*1 + 1

b.       Catalan(4)*Catalan(0) + Catalan(3)*Catalan(1) + 1

c.        Neither.

24.    Which corresponds to BPE1?

a.       ((M1M2)M3)(M4(M5M6))

b.       ((((M1M2)M3)M4)M5)M6

c.        (((M1M2)M3)M4)(M5M6)

d.       M1(M2(M3(M4(M5M6))))

e.        None above.

 

          Next two questions are about a triangulation of a polygon with eight vertices numbered      

          between 1 and 8 clockwise with the following five chords:

                 1 – 5,  2 – 4,  2 – 5,  5 – 7  and   5 – 8.

 

              25.    Assume that the side 1 -- 2  is fixed.

                      Which corresponds to this triangulation?

  a.    ((()))()()()

b.       ((()))((()))

c.        (()(()))()()                            d.    none above

         26.    Suppose that the chord 3-5, above, is replaced by the chord 4-6.

                   In this case, the new triangulation corresponds to

                              a.    (()())()()()

b.       (()())((()))

c.        (()()())()()                           d.      none above.

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

  27.    DP is the most suitable for

a.                make-change problem when the set of denominations does not allow GA.

b.                knapsack problem

c.                Triangulation problem                d.     All above                 e.   two above.             f.  none above.

  28.     T(n) equals 

a.               B(n-2)

b.               M(n-1)

c.               P(n-1)                   d.     All above.                        e.   two above.                        f.   none above

     29.     Suppose that problem P is in NP.  In this case,

a.                   it is polynomially reducible to any NP-Complete problem.

b.                   any NP-Complete problem is polynomially reducible to this problem.

c.                    Both.                                      d.   neither.

     30.     Suppose that problem P is in NP and that a certain NP-Complete problem is polynomially

                reducible to this problem. In this case,

a.                   problem P is NP-Complete.

b.                   Problem P is polynomially reducible to any NP-Complete problem.

c.                    Both.                                      d.   neither.

    31.      In order to show that each and every NP problem is polynomially reducible to a certain problem P,

                we can show instead that

a.                   a certain NP-Complete problem is polynomially reducible to this problem P.

b.                   this problem P is polynomially reducible to a certain NP-Complete problem.

c.                    Both.                                      d.   neither

32.         Which is a Monte Carlo algorithm?

a.                   Fermat Theorem

b.                   Miller Rabin Primality testing

c.                    Computing Bset(k)

d.                   All above                                          e.     a and b above.                             f.     b and c above. 

33.         Which is true about a backward edge of a program diagraph (which is essentially a cyclic directed graph)

   with loops, natural or otherwise? 

a.       The depth-first number of the originating node is smaller than that of the terminating node.

b.       It is the only entry point of a loop if the loop is natural.

c.        Both.                                                              d.             neither

 

34.         Suppose that a spanning tree T has been obtained through a dfs of an undirected connected graph G.

   In this case,

a.       The tree T may not be the only one possible spanning tree for G.

b.       The root node of T must be an articulation point in G if and only if it has two or more children.

c.        The leaf node of T cannot be an articulation point in G.

d.       All above.                                      e.  two above.                                       f.   none above.

35.         Backtracking approach is suitable for

a.       Queens problem

b.       Stable Marriage problem.

c.        Missionaries/Cannibals problem

d.       All above.                                      e.  two above.                                       f.  none above.

 

36.         A set of vertices the next edge to be selected for inclusion in the Prim’s algorithm for MST can leave is

    one consisting of

a.       all nodes already selected into the MST

b.       each and every node not yet selected into the MST

c.        an independent set                                      d.  all above.                                         e.  two above.

 

PART-B.               Other problems.                                                                                (36 points)

 

 Do four problems.

 

A.      Decide whether or not 10 is in Bset(25).

 

B.      Find and clearly show an optimal sequence of multiplications for the following chain of four matrices:

            M1:  40-by-30,   M2:  30-by-100,  M3:  100-by-10, and  M4:  10-by-50

 

C.     Design and show a non-deterministic algorithm for a function, HAMD(G).

  You can use three special non-deterministic instructions:

  (1) accept, (2) reject and (3) choose n between i and j.

 

D.   Show that  HAM(G) is polynomially reducible to HAMD(G). 

 

E.    Find two numbers for 49 satisfying the Splitting Theorem of the Factorization Problem.

 

F.    What are some significant characteristics of NP-Complete problems?             

           

G.   You have six distinguishable men and four indistinguishable 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  women get 1, 1, 2, and 2 men, respectively?

 

H.      Give the Time Complexity function for:

int what (int k)

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

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

 

I.         Solve the following recurrence relation:

D n    =    (n-1) (D n-1  +   D n-2  )

 

J.            Give a Generating Function for the counts of passcodes when up to 3 a’s and up to 2 b’s and

                          up to one c are to be used for a maximum passcode length of 6.