COSC5313
Test-1
3/21/2012
Keys
Used:
1-5:
BBCCB
6-10:
CAAAD
11-15: CBCCC
16-20: BBAAC
21-25: AAAAE
Part-A.
Multiple Choice Questions.
(75 points)
Answer all 25 questions by writing down your best
choice to the left of each question number in CAPITAL such as A, B, C, D, or
F. Each question is three points
worth.
For the first five
questions, consider the following LP problem in the standard
form:
Minimize 3*x1 - x2 +x3 subject to:
x1
+ x5 = b1
x2
+ x4
= b2
x3 +
2x5
=
b3
x1, x2 , x3 , x4
, x5
>= 0
Assume that, for the first
four questions, b1=b2=b3=10.
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.
3
b.
4
c.
5
d.
None of
above.
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.
f(n) = O(g(n))
b.
g(n) = q
(f(n)/n)
c. both.
d. neither.
a.
max(O(f(n)),
O(g(n)))
b.
O (g(n))
c. both.
d. neither.
a.
YNN(n,k)
b.
YNY(n,k)
c.
YYN(n,k)
d. cannot tell.
a.
k*(k-1)*YNN(n,k-2)/2
b.
k*YNN(n,k-2)
c. both.
d. neither.
a.
it is the exponential
generating function for the sequence, (1, 2, 22, 23,
24 …
)
b.
it is the ordinary
generating function for the sequence, (1, 2/1!, 22/2!,
23/3!, 24 /4! …)
c.
both.
d.
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.
14. Which is a characteristic of Chromatic
Polynomials?
a.
The sum of all coefficients
equals zero unless the polynomial
has just one term.
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.
15. Which is a Chromatic
polynomial?
a.
x4 -
3x3 + 2x2
b.
x4 -
3x3 + 3x2 - x
c.
both.
d.
neither.
Next three
questions are about a board B of size 5-4 with three available
squares:
(1, 1)
(2, 2)
(5, 4)
16. R(B), Rook Polynomial, is
a.
1 + 3x +
3x2
b. 1 + 3x +
3x2 + x3
c. 1 + 3x +
4x2
d.
None
17. 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 – 3*4*3*2 + 3*3*2 -
1
b.
5*4*3*2 – 3*4*3*2 + 3*3*2 –
2
c.
5*4*3*2 – 3*4*3*2 + 3*3*2 –
3*2
d.
none
18. The count of all possible placements of
four rooks onto this board (assuming that all 20 squares are available)
is
a.
5*4*3*2
b. 4*4!
c.
4!
d.
None of above.
T(n) = T(n/2)+n where n >=2 is a power of 2 and
T(1)=1.
In this case, T(n) is
a.
Linear
b.
Polynomial of degree at
least 2.
c.
Log n
d.
None above.
19. Suppose that we have a line
segment connecting three points, A, B, and C in that order and that
AC/AB equals the Golden Ratio.
In this case, which is also the Golden Ratio?
a.
AB/BC
b.
BC/AB
c.
AC/BC
d.
Two above.
e.
none above.
20. The time complexity of the Simplex
Algorithm is
a.
exponential in theory
b.
linear in practice
c.
both.
d.
neither.
21. Suppose that T(m) = O(f(m)) (or
more precisely, T(m) is in O(f(m))
).
In this case, there are two constants, c1 and c2, such
that
a.
T(m) <= c2 * f(m)
for m >= c1
b.
T(m) >= c2 * f(m)
for m >= c1
c.
Both.
d.
neither.
22.
for (k=1; k<=n;
k++)
for (m=1; m<=k; m++)
for (j=1; j<=n; j++)
cout << 1000*k + 100*m + 10*j;
The time complexity of the above is
a.
O(n3)
b.
O(n2)
c.
O(n4)
d.
None above.
23.
The time complexity of above
(Question #22) is
a.
Omega(n2)
b.
Omega(n3)
c.
Omega
(n4)
d.
None
above.
For the
next two questions, consider the following five points in the plane
(2-dimensional):
P1:
3, 1.5
P2:
2, 1
P3:
4, 2
P4:
4, 3
P5:
5, 1.5
24.
Which is a convex combination for
p1?
a.
0.5*p2 +
0.5*p3
b.
0.5*p2 + 0.5*p4
c. both.
d. neither.
25.
Which point cannot be inside the convex
hull formed by other points?
a.
p1
b.
p5
c.
p4
d.
all above.
e. p4 and p5.
f. none above.
PART-B. Other problems.
(25 points)
Do three
problems.
A.
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 the four women get 1,
1, 1, and 3 men, respectively?
B.
Consider a general
solution: an =
c12n + c24n + c3n4n +
c4n24n
for any values of
c1, c2, c3, and c4.
Find a particular solution
assuming four initial conditions:
a0=0, a1=
a2=1, and
a3=2.
C.
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);
}
D. Prove the
following: cR
(n, k) = c(n+k-1,
k)
E.
Solve the following recurrence
using an ordinary generating function:
t(m) = 4t(m-1) –4t(m-2),
m>=2.
Assume that we have initial conditions, t(0) and t(1).
F. Compute the number of
possible passcodes of length 5 when up to 3 a’s and up to 2 b’s and up to 1 c
are used.
G.
Minimize x1 + 10*x2 -
4*x3 subject to:
x1
+ x3 + x5 = 100
x2 -
x4
+ x5 = 20
x1, x2 , x3 , x4
, x5
>= 0
Choose
x1 and x2 for the initial basis and Find the first two basic feasible solutions
and values of the objective
function.