# 程序代写代做代考 algorithm ANLY550–Spring, 2017 Homework 4 Out: April 7, 2017

ANLY550–Spring, 2017 Homework 4 Out: April 7, 2017

Due: April 25, 2017

1. Recall that a hash family H of hash functions mapping [n]→ [r] is pairwise independent if for every 2 distinct

values x1,x2 ∈ [n] = {1, . . . ,n}, and any y1,y2 ∈ [r],

Pr

h←H

[h(x1) = y1 and h(x2) = y2] = 1/r

2.

Also, recall that H is universal if for every pair of distinct values x1,x2 ∈ [n],

Pr

h←H

[h(x1) = h(x2)]≤ 1/r.

Construct a specific family H that is universal, but not pairwise independent, and justify your answer. Write

down the family as a table, with one column per input to the hash function (i.e., one column for each number

in [n]), and one row per hash function. Try to make |H |, n, and r as small as possible! (There is a way to

accomplish this with all of these quantities equal to 2).

2. You are given a bag of n balls, with at least 10% of the balls being blue, at least 5% of the balls being yellow,

and no more than 80% of the balls being red. Asymptotically, as n grows, how many balls do you have to

draw at random from the bag to see a blue ball with probability at least 2/3? (Assume that the balls are drawn

with replacement, meaning that as soon as a ball is drawn, it is placed back in the bag before the next draw.)

3. Let A be a randomized algorithm for a decision problem (where the correct output is always YES or NO).

Suppose that on YES instances the algorithm is always correct, but on NO instances the algorithm outputs

YES with probability at most 1/2. Derive a new algorithm B that is always correct on YES instances, and on

NO instances outputs YES with probability at most 2−100. How much slower is Algorithm B than Algorithm

A?

4. Sometimes for special classes of inputs, NP-hard problems are solvable in polynomial time. For example, we

have seen on an earlier problem set that computing the size of a maximal independent set in a tree can be done

in polynomial time. Here, we will consider counting the number of independent sets in even more specialized

graphs.

Consider a graph that is a line on n vertices. (That is, the vertices are labelled 1 to n, and there is an edge from

1 to 2, 2 to 3, etc.) How many independent sets are there on a line graph?

Similarly, describe how you could quickly compute the number of independent sets on a complete binary tree.

(Here, just explain how to compute this number.) Calculate the number of independent sets on a complete

binary tree with 127 nodes.

5. Recall that a clique in a graph G is a collection of mutually adjacent vertices. The decision version of the clique

problem is to take a graph G and an integer k and decide if G has a clique of size k or not. The optimization

version of the problem takes a graph G, and returns a largest clique in G. Show that if the decision problem

has a polynomial time algorithm, then the optimization problem also has a polynomial time algorithm.

6. Consider the following problem, called 2Clique:

INPUT: A undirected graph G and an integer k.

1

OUTPUT: 1 if G has two vertex disjoint cliques of size k, and 0 otherwise. (Two cliques are vertex disjoint if

they do not share any vertices in common).

Show that this problem is NP-hard. Use the fact that the decision version of the clique problem in NP-

complete.

7. We know that that all of NP-complete reduce to each other. It would be nice if this meant that an approximation

for one NP-hard problem would lead to another. But this is not the case.

Given a graph G, the Minimum Vertex Cover problem is to find the smallest set of vertices such that each

edge of the graph is incident to at least one vertex of the set. Minimum Vertex Cover has a polynomial 2-

approximation algorithm; that is, the algorithm always outputs a vertex cover whose size is within a factor

of 2 of the optimal solution. The algorithm is to repeatedly choose an edge, add both of its endpoints into

the cover, throw the vertices and its adjacent edges out of the graph, and continue. It is a 2-approximation

algorithm because each edge that gets chosen during the course of the algorithm must have one of its endpoints

in the cover; hence we have merely always thrown two vertices in where we might have gotten away with

throwing in 1.

We know (from the NP-completeness notes, which you may want to check) that C is a cover in a graph

G = (V,E) if and only if V −C is an independent set in V . Explain why this does not yield an approximation

algorithm that is within a constant factor of optimal for Maximum Independent Set. That is, show that for any

constant c, there exists a graph for which even if we obtain a 2-approximation of the Minimum Vertex Cover,

the corresponding independent set is not within a factor of c of the Maximum Independent Set.

The Maximum Independent Set problem and the Maximum Clique problem are related in the following way:

an independent set of a graph G is a clique in the complement of G. (The complement of G is the graph that

contains exactly the edges that are not in G.) Does an approximation algorithm (that is, an algorithm within a

constant factor of the optimal) for the Maximum Clique problem yield an approximation algorithm (within a

constant factor of optimal) for Maximum Independent Set?

2