Algorithm-Design-Homework 1 Solved

Exercise 1
A group of n kids (denoted by K) wants to play football. Each kid has a level denoted by ℓk ∈ {1,...,L}, and they want to be partitioned into 3 (not necessarily of the same size) groups, with the same aggregated level.

a.    Provide an algorithm that finds whether such partition exists, and if so, returns it.

b.    What is the complexity of the algorithm as a function of n and L?

c.    Prove the correctness of the algorithm.

Exercise 2
There is a network N of n people, in which every person i is associated with a subset of people Fi ⊆ N . For every i ∈ N, it holds that i ∈ Fi, and if person j is in Fi, then it must be that i is in Fj as well. Your goal is to advertise a product to every person in N. To do so, you need to choose a set of advertisers among N that will promote it, each will advertise it among his associates.

Prove that the problem of finding whether there exists a set of size at most k of advertisers that can promote your product, is NP-Complete.

Exercise 3
You play the following game: At each time t = 1,...,n, you see a prize of value of xt, and you need to decide whether to take it and go home, or continue to the rest of the prizes. All xt are distributed independently from the uniform distribution over [0,1]. A dynamic threshold-strategy is described by τ1,...,τn, where you select the first xi that exceeds the corresponding τi. A static threshold-strategy is described by a single parameter τ where you select the first xi that exceeds τ.

a.    Calculate the best dynamic threshold-strategies for n = 2,3, along with their expected performances.

b.    Calculate the best static threshold-strategies for n = 1,2, along with their expected performances.

c.    What is the expectation of the best dynamic threshold as a function of n (write a recursive formula)?

Exercise 4
You have k houses located on a line in locations L1 < L2 < ... < Lk. You need to build hospitals on the line (i.e., to choose locations H1,...,Hm), so that all houses will be at most d far from a hospital (i.e., for all i, |Li − Hj| ≤ d for some j).

Your goal is to design an algorithm that finds the minimal amount m of hospitals that are needed to be built.

a.    Provide an algorithm that finds the minimal value m of hospitals that are needed, as well as a valid values of H1,...,Hm.

b.    What is the complexity of the algorithm as a function of k?

c.    Prove the correctness of the algorithm.

Exercise 5
Consider a graph G = (V,E), with integer capacities on the edges, such that for all e ∈ E \ {e∗}, it holds that ce is an even number, and ce∗ is odd. Suppose that there is a maximum flow in this graph with odd flow.

a.    Prove/Disprove: It must be that in every maximum flow, there is a flow in e∗ (i.e., fe∗ > 0).

b.    Prove/Disprove: It must be that in every maximum flow, there is a full flow in e∗ (i.e., fe∗ = ce∗).