COSC5313                             Test-2                                      4/28/2011  

 

Keys Used:

          1-5:             BBBBB

          6-10:           BCADA

          11-15:         BEBBD

          16-21:         DBAAAC

---------------------------------------------

 

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.

                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.                                                              (63 points)

 

Write down your best choice to the left of each question number in CAPITAL such as A, B, C, D, or F.

 

For the next six 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 Restrictive Cutset?

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

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

c.                    both.                                               d.             neither. 

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

3.  The Max Flow is

a.                   24

b.                   28

c.                    32                                                   d.        none

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

 

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

a.                   30

b.                   34

c.                    48

d.                   none above

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

a.             node#1

b.                   node#5 

c.                    both.                                                       d.    neither

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

       7.  Which is a characteristic of Chromatic Polynomials?

a.       The sum of all coefficients equals zero if the polynomial has two or more terms.

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

c.        both.                                                               d.   neither.                                                                                           

 

       8.                      x⁴  -  4x³   + 6x²    - 3x   

                Suppose that above is the Chromatic polynomial of a graph.

                In this case,

a.       the graph has four vertices and four edges

b.       one vertex has three edges incident on it.

c.        Both.                                              d.             neither.

 

       9.  Which is a Chromatic polynomial?

a.       x⁴  -  3x³   + 3x²     

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

c.        both.                                               d.   neither.

 

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

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

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

 

10.    The rank of BPE2 is

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

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

c.        Neither.

11.    Which corresponds to BPE1?

a.       ((M1M2)M3)((M4M5)(M6M7))

b.       ((M1M2)M3)((M4(M5M6))M7)

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

d.       (M1(M2(M3M4)))(M5(M6M7))

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

 

          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.                Knapsack 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-2)

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 probabilistic algorithm may never return a wrong solution?

                a.             Factorizing large integers

                b.             Primality testing

                c.             both.                                       d.   neither.

 

       19.   In an undirected graph, a vertex, v,  is an articulation point if and only if, in a spanning tree of the graph,

                                a.             it has a child, c , such that highest (c) >= prenum(v)

                                b.             it is the root of the spanning tree.

                                c.             both.                                       d.             neither.

 

       20.   Which is a Monte Carlo algorithm?

                                a.             Miller Rabin Primality testing

                                b.             Computing Bset(k) which is the set of all Strong False Witnesses of an odd composite k.

                                c.             Factorization

                                d.             all above.                              e.             two above.

 

      21.    An advantage of depth-first search of graphs includes

                                a.             no need to use a queue or a stack

                                b.             finding cycles (or loops) of a graph is easier.

                                c.             both.                                       d.             neither.

 

PART-B.    Other problems.                                                 (37 points)

 

 Do four problems.

 

 

A.      Give an algorithm for computing the Bset(n) where n is an odd positive composite integer and Bset(n) is

   the set of all Strong False Witnesses of primality for n, which are less than  n.

 

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

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

 

 

C.      Find two numbers for 25 satisfying the Splitting Theorem of the Factorization Problem.

 

D.    Give an algorithm for Depth-First Search of an undirected graph.    

 

 

E.     Compute and clearly show the Chromatic polynomial for the following graph with four vertices and four edges:

(1,2)

(1,3)

(1,4)

(2,4)

 

F.     Compute the rank of each of the following BPE expressions:

((())) (())

((())) ()()

(()()) ()()

 

G.    Give an algorithm for deciding if man-A and Woman-B can be matched according to the Stability Requirement of Program-5 (Stability Matching Problem)