(Due at the beginning of
class on 9/26/11)
This problem set will be graded out of 50 points. It
will count for 20% of your final grade.
1) Computability
a) A virus is defined as a program
that “infects” other computers. Prove that there can be no universal program
for catching all viruses and only viruses. [3]
b) Prove that it is possible to
decide, on any real-world computer, whether a program terminates or not. Why is
this not in conflict with the undecidability of the
Halting Problem. [3]
c) Consider a real-world
computer with a true source of randomness. Show that it is possible to compute
the probability that a program will halt. [3]
d) Can a quantum computer solve
the Halting Problem? [1]
2) The comparison model
a) Given 12 coins of which one
is fake show that it is possible to identify the fake coin and whether it is
heavy or light using 3 weighings with a balance. [3]
b) Why are 3 weighings insufficient for detecting the fake coin and
whether it is heavy or light out of 14 coins [1]
c) Why are 3 weighings insufficient for detecting the fake coin and
whether it is heavy or light out of 13 coins [2]
d) Prove that n! is 2^q(nlog
n). (Hint: observe that (n/2)^(n/2) <= n! <= n^n.) [2]
e) Prove an W(nlog n) lower
bound on sorting n elements in the comparison model. [2]
3) Order notation
a) Solve the recurrence T(n) = 2T(n/2) + n^2; T(1) = 1. [3]
b) Solve the recurrence T(n) = T(n/2) + T(n/3) + q(n); T(3) = T(2) = T(1) = 1.
[3]
c) Give an example of two
functions f(n) and g(n) such that neither f(n) =
O(g(n)) nor g(n) = O(f(n)) is true. [2]
d) Give an example of a
function f(n) such that it grows faster than any
polynomial but slower than any exponential. [2]
4) Stable and other matchings
a) Given an instance of the
Stable Matching problem where there exists a man m and a woman w such that each
is ranked first on the preference list of the other, show that in every stable
matching m and w must be paired together. [3]
b) Consider a variant of the
Stable Matching problem where there is no distinction between men and women.
Consider a world with 2n individuals where each individual ranks the rest on a
preference list. Give an example where there does not exist a stable pairing.
(A pairing is unstable if there exist two individuals
who occur in different pairs but prefer each other over their partners.) [3]
c) There are n men and n women
located on a field in general position (i.e. no 3 in a line). Show that there
exists a way to pair them up such that if we build roads between the members of
each pair then the roads do not intersect. [4]
5) Greedy algorithms
a) Given a graph with maximum
node degree d, show that it can be vertex colored with d+1
colors such that no edge has both of its endpoints colored the same. [2]
b) You are given a graph with
edge weights. Given a spanning tree T of the graph, cost(T)
is defined to be the value of the minimum weight edge in T. Give a
polynomial-time algorithm to find the tree with the largest cost. What is the
time complexity of your algorithm. [4]
c) Consider the problem of
making change for n cents using the fewest number of coins. Describe a greedy
algorithm to make change consisting of quarters (25c), dimes (10c), nickels
(5c) and pennies (1c). Prove that your algorithm works. Give a set of coin
denominations for which the greedy algorithm does not work. [4]