COSC5313
Test-1
3/3/2011
Keys
Used:
1-5:
CBABA
6-10:
ACCAA
11-15:
ABABA
16-21:
ACBBAA
Part-A. Multiple Choices
(72
points)
Answer 18 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 six questions,
consider the following LP problem in the standard form:
Minimize x1+ x2 +x3 subject to:
x1
-2
x5
=
b1
x2
+ x4
= b2
x3 +
x5 = b3
x1, x2 , x3 , x4
, x5
>= 0
Assume that, for the first
five questions, b1=b2=b3=100.
a.
x1=x3=x4=100, x2=x5=0
b.
x1=x2=x3=100, x4=x5=0.
c. both.
d. neither.
a.
x1, x2,
x4
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,
x3
b.
x3, x2,
x4
c.
x2, x3, x4
d. all above.
e. two
above.
a.
the objective function has
no feasible value.
b.
the objective function has
is unbounded (i.e., it can be as small as we wish).
c.
both.
d. neither.
*****************************************************
a.
2*n2 +
10*n
b.
100*n*log (n*n*n)
c. both.
d. neither.
a.
O(n2)
b.
12*n3
c. both.
d. neither.
a.
f(n) = O(g(n))
b.
g(n) = q
(f(n))
c. both.
d. neither.
a.
max(O(f(n)),
O(g(n)))
b.
O (g(n))
c. both.
d. neither.
a.
quadratic and O(n*log(n)),
respectively.
b.
both quadratic.
a.
NYN(n,k)
b.
NYY(n,k)
c.
NNY(n,k)
d. cannot tell.
a.
k*YYN(n, k-1)
b.
YYY(n, k) - YYN(n, k)
c. both.
d. neither.
a.
above is the ordinary
generating function for the sequence (c(2*n, k)),
k=0,1,2,…,2*n
b.
above is the ordinary
generating function for the sequence (2kc(2*n, k)),
k=0,1,2,…,2*n
c.
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-1)3
b.
(a0 x2
+ a1 x+ a2) (x-1)2
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*m*m*3m
d.
none above.
Next three
questions are about a board B of size 5-4 with three available
squares:
(1, 1)
(2, 2)
(3, 4)
a.
1 + 3x +
3x2
b.
1 + 3x +
3x2 + x3
c.
1 + 3x +
4x2
d.
None
a.
5*4*3*2 – 3*4*3*2 +
3*3*2
b.
5*4*3*2 – 3*4*3*2 + 3*3*2 –
1*2
c.
5*4*3*2 – 3*4*3*2 + 3*3*2 –
1
d.
none
a. 5*4*3*4
b. 5*4*3
c. neither.
21. for (k=1; k<=n; k++)
for (m=1; m<=n; m++)
for (j=1; j<=m; j++)
return 100*k+10*m+j;
The time complexity of the above is
a. O(n3)
b. O(n2)
c. O(n)
d. None above.
PART-B.
Other problems.
(28 points)
Do
three problems.
A.
You
have six distinguishable men and four 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 the four women get 1,
1, 2, and 2 men, respectively?
B.
Give the Time Complexity
function for:
int
what (int k)
{
if (k==0 || k==1) return
k;
else return what(k-1)*what(k-2); }
C.
Consider the standard LP
problem.
Show that if X1 and X2 are two
distinct optimal solutions, then every convex
combination of X1 and X2 is also
an optimal solution.
D.
Minimize 2*x1 + x2 -
2*x3 subject to:
x1
+ 5* x3 - x5
=
10
x2
-
x4
+ x5
=
10
x1, x2 , x3 , x4
, x5
>= 0
Find the first two basic feasible solutions and values of the objective
function.