(Due at the beginning of
class on 10/12/11)

This problem set will be graded out of 50 points. It
will count for 20% of your final grade.

1) Random questions

a) Find the minimum and maximum
of n numbers using no more than (3n/2) - 2 comparisons. [2]

b) Find the minimum and second
minimum of n numbers using no more than n + log_{2}n – 2 comparisons.
[2]

c) Give an example, along with
proof, of a monotone increasing function from the natural numbers to the
natural numbers that grows faster than any computable function. [2]

d) A Platonic solid is the 3D analogue of a regular polygon; all its faces are congruent regular polygons. Use Euler’s formula to argue that there are exactly 5 Platonic Solids. [4]

2) Greedy

a) Given a list of n natural
numbers d_{1}, d_{2}… d_{n},
show how to decide in polynomial time whether there exists an undirected simple
graph whose node degrees are precisely the numbers d_{1}, d_{2}…
d_{n}. A simple graph is one
that does not contain self loops or multi-edges. [4]

b) Given a network (undirected
graph) with an available bandwidth for each link (edge), the bottleneck
bandwidth of a path is defined to be the minimum bandwidth of any edge on the
path and the bottleneck bandwidth of a pair of nodes, u, v, is defined to be
the maximum, over all paths connecting u to v, of the bottleneck bandwidth of
that path. Prove that there exists a tree such that for each pair of nodes
their bottleneck bandwidth in the tree is the same as in the graph. Give a
polynomial time algorithm to find such a tree. [4]

c) Given two sets of n numbers
a_{1}, a_{2}…, a_{n} and b_{1}, b_{2}…b_{n},
find, in polynomial time a permutation Π such that ∑_{i} |a_{i}
- b _{Π(}_{i)}| is minimized.? [2]

3) Divide and Conquer

a) You are given n FPGA chips
and an FPGA tester. The tester takes two FPGA chips and tells you whether the
chips are equivalent (from a logic standpoint) or not. Give an algorithm that
runs O(nlogn) tests to decide whether more than half
the chips are equivalent. [2]

b) The setup is the same as in
2a). Give an algorithm that runs O(n) tests to decide
whether more than half the chips are equivalent. [4]

c) You are given a complete
binary tree with n nodes (n = 2^{d} -1 for some d). Each node is
labeled with a unique real number. A node is a local minimum if its label is less
than the labels of its neighbors. You can find out the label of a node only by
probing it. Show how to find a local minimum using O(log
n) probes. [4]

4) Matroids

a) Prove that the exchange
property does not imply hereditariness, i.e. give an example of a set system which
contains the empty set and has the exchange property but is not hereditary. [3]

b) A matching in a graph is
defined to be a collection of edges such that no two edges share an endpoint.
An edge in a matching is said to cover its endpoints. A vertex is said to be
covered by a matching if it is covered by some edge in the matching. A subset
of vertices is said to be coverable if there exists a matching that covers each
vertex in the subset. Let F be the family of coverable sets.

i)
Prove that (V,F) has the hereditary property.
[1]

ii) Given two matchings M_{1}
and M_{2} prove that M_{1} ∆ M_{2} (∆
denotes the symmetric difference, i.e. M_{1 }–_{ }M_{2} U M_{2} – M_{1}) consists of
alternating cycles and paths i.e. paths and cycles where the edges alternate
between M_{1} edges and M_{2} edges. [2]

iii) Prove that (V, F) has the
augmentation property. (Hint use 4a ii)) [4]

5) More problems

a) Given an array of n numbers
find in linear time that contiguous sub-array which has the largest sum. [4]

b) Suppose I give you a graph
with n nodes and tell you that it is 3-colorable (i.e. the vertices can b
colored with one of 3 colors such that no edge has both its endpoints of the
same color) but I don’t tell you the coloring. The following subparts will show
how you can color this graph with no more than 4*n^{1/2} colors.

i)
Consider the following step – if the graph has a vertex of degree >=
n^{1/2} then remove the vertex and its
neighbors from the graph. Prove that you can run this step only at most n^{1/2}
times before you have no vertex with degree >= n^{1/2} left. [2]

ii) Prove that after running 5b
i) as many times as you can, the residual graph can be colored with n^{1/2}
colors in polynomial time. [1]

iii) Prove that the entire graph
can be colored with 4*n^{1/2} colors. [2]

iv) Can you give a
polynomial-time algorithm to color any 3-colorable graph with 3 colors? [1]