COSC5313                             Final Exam                              5/5/2011  

 

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.

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

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

                                                a Hamiltonian cycle.

Do nine problems.                                                           (200 points)

 

 

A.     Check to see if 8 is in Bset (49)

 

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

            M1:  50-by-200,   M2:  200-by-20,  M3:  20-by-50, and  M4:  50-by-10

 

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

 

D.     You have six distinguishable men and three 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 every woman gets exactly

two men, respectively? 

 

E.      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);   }

 

F.           Minimize  x₁ +  2*x₂   + x₄     subject to:

 

                  x₁           + 2* x₃                  -   x₅                         =   10

                        x₂                - x₄          +5* x₅                                 =   10

                        x₁, x₂ , x₃ , x₄ , x₅     >=  0

 

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

G.          Minimize  x₁ +  2*x₂  - x₃ + x₄     subject to:

 

                  x₁           + 2* x₃                  -   x₅                         =   10

                        x₂                - x₄          +5* x₅                                 =   10

                        x₁, x₂ , x₃ , x₄ , x₅     >=  0

 

 Convert the above LP problem in the Standard form to one for the two-phase Simplex version.

 

 

H.   Compute and clearly show the Chromatic polynomial for the following graph with four vertices and

 five edges:

(1,2)

(1,3)

(1,4)

(2,3)

(3,4)

 

I.      Compute and clearly show the rank of each of the following BPE expressions:

(((()))) ()(())

(((()))) ()()()

((()())) ()()() 

 

 

J.     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) 

 

K.   Show that  HAM(G) and HAMD(G) are polynomially equivalent. 

 

L.   Consider a general solution:  a_n = c₁2ⁿ + c₂4ⁿ  + c₃n4ⁿ + c₄n²4ⁿ  for any values of  c₁, c₂, c₃, and c₄.                  

Find a particular solution assuming four initial conditions: a₀=0,  a₁= a₂=1, and  a₃=2.

  

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

 

N.  Give a Generating function for the counts of passcodes when up to four a’s and up to two b’s and up to one c are to be used for a maximum length of 7.