Let D be a topological space containing at least two points with the discrete topology. Prove that a topological space X is connected if and only if each continuous function f:X® D is constant.
2.
Find a continuous bijection f:[0,p)® S1 such that f is not a homeomorphism.
Note that the half-open interval [0,p) and S1 are given the subspace Euclidean topologies of \R1 and \R2 respectively. You should give a formal justification that shows that f is not a homeomorphism. You may not use any algebraic topology results.
3.
Let A be a subset of a topological space X. Define the closure of A, cl(A), to be the intersection of all closed subsets of X which include A. Let A¢ be the set of all limit points of A (also
called accumulation points or cluster points). Prove:
i.
x Î cl(A) if and only if each open set containing x intersects A.
ii.
cl(A)=AÈA¢.
4.
Let X be a Hausdorff space. Prove:
i.
For each compact subset A of X and each point x not in A, there exist disjoint open subsets U
and V such that A Í U and x Î V.
ii.
For any disjoint compact subsets A and B of X, there exist disjoint open subsets W and N such that A Í W and B Í N.
Department of Mathematics and Computer Science
Comprehensive Examination-Option III
Spring 2004
where A is an m×n matrix and ct is the transpose of the column vector c.
a.
Define: Optimal solution of problem P
b.
Prove: If u and v are optimal solutions of problem P and 0 £ t £ 1, then tu+(1-t)v is also
an optimal solution of problem P.
c.
Let Q be the following linear programming problem.
maximize w=y1+2y2
subjectto 3y1+4y2
£ b1
5y1+6y2
£ 7
y1 ³ 0; y2
³ 0
For what value(s) of b1 does the dual of problem Q have more than one optimal solution? Justify your answer geometrically.
2.
Let P be the following linear programming problem.
minimize z=4x1+5x2+x3
subjectto x1+x2+x3
³ 3
2x1+2x2-x3
³ 2
x1+2x2
³ 4
x1 ³ 0; x2 ³ 0; x3
³ 0
Find optimal solutions to both problem P and its dual.
3.
Consider the following cost matrix for an assignment problem.
A=(aij)=
æ ç ç ç ç ç
ç ç ç ç è
4
9
2
9
7
8
4
3
8
4
5
1
6
9
1
3
7
9
4
4
6
5
2
7
8
ö ÷ ÷ ÷ ÷ ÷
÷ ÷ ÷ ÷ ø
where aij is the cost of assigning person i to job j.
a.
Find the optimal assignments and the minimal total cost for this problem.
b.
Find an optimal solution to the dual of this assignment problem.
4.
Let P be the linear programming problem
maximize z=ctx
subjectto Ax
=b
x
³ 0
where A is an m×n matrix and ct is the transpose of the column vector c. Let Q be the dual of problem P. In the following proofs do not assume any duality theorems.
a.
Prove: If [`x] and [`y] are feasible vectors for problems P and Q, respectively, and
ct[`x]=bt[`y], then [`x] and [`y] are optimal solutions of problems P and Q, respectively.
b.
Prove: If [^x] and [^y] are feasible vectors for problems P and Q, respectively, and
[^x]t(At[^y]-c)=0, then [^x] and [^y] are optimal solutions of problems P and Q, respectively.
Show that there exists a unique real solution of the equation; let us call it z.
b.
Find an approximation, say a, of z such that |z-a| < 10-6.
c.
Prove that your approximation a is in fact within 10-6 of z.
2.
Suppose 0 < h and f Î C2[-h,h] with |f¢¢¢(x)| £ M "x Î [-h,h]. Let p(x) be the polynomial
that interpolates f at x=-h, 0, and h. Use the interpolation error formula to find a bound on
max{|f(x)-p(x)| | x Î [-h,h]} in terms of M and h.
3.
Let
A=
æ ç ç ç
ç ç è
9
0
3
0
2
1
3
1
2
ö ÷ ÷ ÷
÷ ÷ ø
.
a.
Prove that A is positive definite.
b.
Consider the use of Jacobi's method to solve the equation Ax=b. Prove that the Jacobi iterates will converge for any initial approximation.
4.
Let p2(x)=a0+a1x+a2x2 be the second degree least squares approximation for f(x)=ex on [-1,1].
Construct the linear system used to determine a0, a1, and a2. Evaluate each definite integral involved in the construction, but do not solve the system.
A purse contains twenty different coins. Six of them are quarters, three of them are dimes, four of them are nickels, and seven of them are pennies.
a.
Suppose that eight coins are randomly removed from the purse without replacement.
(i) How many ways can this be done?
(ii) What is the probability that exactly two of the removed coins are nickels?
(iii) If exactly two of the removed coins are dimes, then what is the probability
that the other six removed coins are pennies?
(iv) If exactly three of the removed coins are pennies, then what is the proba-
bility that exactly two of the other removed coins are nickels and the other
three removed coins are quarters?
b.
Suppose that three coins are randomly removed from the purse without replacement. What is the expected number of nickels among the three removed coins?
2.
Twenty per cent of the houses in a large city have wooden roofs. Suppose that houses in the city are selected at random, one by one, until the first house with a wooden roof is selected. Let X be the number of houses selected.
a.
Find P[X=3].
b.
If X exceeds three, then what is the probability that X is five?
c.
Find E(e-tX) for 0 < t < ¥.
d.
Find E(X).
e.
If X is at most five, then what is the probability that X is three?
3.
Suppose the time X, in minutes, that Fred requires to drive to work has the probability density function
fX(x)=
ì ï ï í
ï ï î
3
(x-14)4
ifx > 15,
0
elsewhere.
a.
Find the probability that X is at most seventeen.
b.
Find the expected value of X.
c.
If X is more than sixteen, then what is the probability that X is at most seventeen?
d.
If Fred drives to work for twelve independent trips, then what is the probability that his driving time is at most sixteen minutes for exactly two of the twelve trips?
4.
Suppose that X and Y have the joint probability density function
fX,Y(x,y)=
ì ï í
ï î
24xy3
for0 < x < 1and0 < y < x,
0
elsewhere.
a.
Find the probability density function fX(x) of X.
b.
Find the expected value of Y.
c.
If X is 1/2, then what is the expected value of Y?