# Problem Set - II9/26/11

(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 + log2n – 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 d1, d2dn, show how to decide in polynomial time whether there exists an undirected simple graph whose node degrees are precisely the numbers d1, d2… dn.  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 a1, a2…, an and b1, b2…bn, find, in polynomial time a permutation Π such that ∑i |ai - 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 = 2d -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 M1 and M2 prove that M1 ∆ M2 (∆ denotes the symmetric difference, i.e. M1 M2  U  M2 – M1) consists of alternating cycles and paths i.e. paths and cycles where the edges alternate between M1 edges and M2 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*n1/2 colors.

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

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

iii)    Prove that the entire graph can be colored with 4*n1/2 colors. [2]

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