COSC5313
Final Exam
12/15/2009
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.
a. x1, x2, x3
b. x1, x2, x5
c. x3, x4, x5
d. all above. e. two above. f. none
In this case, which non-basic variable is to become basic next?
a. x4 b. x5 c. cannot tell
a. x1 b. x2 c. x3 d. none.
a. x1, x2, x5
b. x1, x2, x4
c. x2, x3, x5
d. all above. e. two above. f. none.
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.
*****************************************************
a. 2*n2 + 10*n
b. n *log (n3) c. both. d. neither.
a. max(O(f(n)), O(g(n)))
b. O (g(n)) c. both. d. neither.
a. NNY(n,k)
b. YNN(n,k)
c. YNY(n,k) d. cannot tell.
a. k*YNN(n, k-1)
b. YNN(n, k-1) c. both. d. neither.
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.
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.
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)
a. {(1,2), (3,6), (4,5), (4,6)}
b. {(1,4), (3,6)}
c. both. d. neither.
a. {(1,2), (3,6), (4,5), (4,6)}
b. {(1,4), (3,6)}
c. both. d. neither.
a. 1 – 2 - 4 – 3 – 5 - 6
b. 1 – 4 - 2 – 3 - 5 - 6
c. both. d. neither.
a. 26
b. 28
c. 32 d. none
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.
b.
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
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.