COSC5313                                                           Test2                                                      11/25/2008    

 

Name (Please print, else you lose 5 points)

 

Results:  

          Keys Used:

                   1-5:             BBBBB

                   6-10:           DCDBA

                   11-15:         AEBBD

                   16-21:         EBAAAA

_________________________________________________________

 

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.

 

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

 

Answer all 21 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 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,6)

                        (1,3,6)

                        (1,4,20)

                        (2,3,6)

                        (3,6,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.  

2. Which is a Restrictive Cutset?

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

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

c.                    both.                                               d.             neither. 

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

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

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

c.                    both.                                               d.             neither.

4.  The Max Flow is

a.                   24

b.                   28

c.                    32                                                   d.        none

5.  MTL is

a.                   32

b.                   40

c.                    50.                                                  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.

 

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

a.                   30

b.                   34

c.                    48                                                           d.             none above

      7.   Which node cannot be included into an MST as the last node at all?

a.             node#1

b.                   node#5 

c.                    both.                                                       d.             neither

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

 

      8.  Which is a characteristic of Chromatic Polynomials?

a.       The sum of all coefficients equals zero regardless of the number of terms of the polynomial.

b.       The coefficient of the second highest exponent term is negative and its absolute value equals the number of nodes of the graph.

c.        both.                                                               d.             neither.  

                                                                               

      9.  Which is a Chromatic polynomial?

a.             x⁴  -  4x³   + 2x²     

b              x⁴  -  3x³   + 3x²   - x

c              both.                                                       d.   neither.

 

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

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

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

 

10.    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.

 

11.    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.                                                                                                                                       

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

 

12.    Which can represent a BPE or a Binary tree?

a.       5 4 3 2 1

b.       2 3 4 5 1

c.        3 5 4 1 2                                               d.     all.                                             e.   a and b above.                      

 

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

     between 1 and 8 with the following five chords:

                 1 – 6,  2 – 6,  3 – 6,  3 – 5  and   6 – 8.

 

              13.    Assume that the side 2 – 3  is fixed.

                      Which corresponds to this triangulation?

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

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

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

 

         14.    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.

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

  15.    DP is the most suitable for

a.                Make-Change problem when the set of denominations does not allow GA.

b.                Chained Matrix Multiplication problem

c.                Triangulation problem

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

 

  16.     T(n) equals 

a.               B(n-2)

b.               M(n-1)

c.               P(n-1)

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

 

     17.     A directed graph has a topological ordering of its nodes if and only if

a.                   it is connected.

b.                   it has no cycle involving at least two nodes.

c.                    both.                                         d.    neither.

 

     18.     Which is a characteristics of GA’s?

a.                   local optimization is equivalent to global optimization.

b.                   mostly exponential time complexity

c.                    both.                                       d.             neither.

 

Next two questions are about the following Rooted Tree representation of Disjoint sets:

                        1  2  1  2  1  4  7  7  7  9

 

19.    How many disjoint sets are represented?

        a.         3

        b.         4

        c.         5                                  d.         none

 

20.   Assume that a tree with only one node is of height 1.

Which is the height of the highest tree of all the trees representing these Disjoint sets we have?              

a.                   3

b.                  4

c.                   5                            d.         none.

  

     21.   To which set of coin denominations, is the Greedy Algorithm  applicable?

a.             1, 4, and 25

b.            1, 6, and 25

c.             1, 8, and 25.               

d.             all.                              e.         a and b above.                         f.          none.              

 

 

 

 

PART-B.        Other problems.                                                                               (16 points)

 

Do two problems.

 

A.             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

 

B.            Consider the expressions:                  (())(())((()))

                                1.             Calculate the rank of this expression.

                                2.             Clearly show the corresponding binary tree and also the corresponding triangulation.

 

C.            Consider the following flow network with 7 nodes and  9 edges:

                                                (1, 2, 10)

                                                (1, 3, 20)

                                                (1, 4, 30)

                                                (2, 5, 40)

                                                (3, 2,  15)

                                                (3, 6,  25)

                                                (4, 6, 10)

                                                (5, 7, 20)

                                                (6, 7, 40)

 

                                Give the optimal topological ordering of nodes that should reveal the MTL of this network.

 

D.            Explain three problems for which DP works in no more than 9 lines.