# Problem Set - I9/12/11

(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]