# Design and Analysis of Algorithms - Essay Example

Question 1 In what follows we consider two simple algorithms for the Knapsack problem. We assume without loss of generality, that for every object I we have is B (or else we can remove the object from the set of objects). Item A. Consider the following greedy algorithm for the knapsack problem: For each object l, compute the “profit-to-size” ratio RL = Pl/SSL. We order the objects according to RL, from big to small, and then go over the objects In this order and add an object If It doesn’t violate the size constraint (that Is, the total size of the selected objects Is at cost B).

Show that the approximation factor this algorithm gives may grow (at least) linearly with B (so that In particular It Is not any fixed constant or even a function of the number of objects). Item B. We modify the algorithm In the previous Item as follows. We still order the objects according to the Uri’s. We then find the minimal k such that the total size of the first k objects according to this order exceeds B. The algorithm now compares the total profit of the first k – 1 objects to the profit of object k and takes the better of the two. Show that this algorithm gives an approximation factor of 2.

Question 2 As mentioned in class, there is a more “natural” pseudo-polynomial algorithm for solving the Knapsack problem using a dynamic programming approach. Specifically, for each 1 I and for each O b B, let V (I, b) be the maximum of 12TH where the maximum is taken over all subsets T {1, , I) such that 12TH b. Answer the following (and explain each answer that you give). 1 . What is V (I, O) for every l? 2. What b) for 1 b B? 3. Write an expression for V (I, b) where 2 1 n and 1 b Bas a function of values of he form V (I – 1, boo) (for boo b). . Based on the previous items write pseudo;–code for an algorithm whose running time Is O(n ;B) and that computes the maximum profit that can be obtained P for a , n} such that 12TH so] B (using an nix(B +1) matrix V , and given as Input, set T n, B, and arrays so and pop where so] = s’, = 5. Suppose you are given an n x (B + 1) matrix V such that V = V (l, b). Write pseudo-code for an efficient procedure that given V, n,B, p[], s[], prints the elements , n} such that In a set T 12TH B and p 12TH p]] is maximized.

Question 3 identical) machines on which the Jobs can be processed (e. G. , the machines are printers and the Jobs correspond to files that should be printed). Job I requires processing time pi where pi is an integer. The goal is to assign each Job to one of the two machines (where on each machine the Jobs assigned to that machine are processed one after the other according to some order), so the that total time it takes until all Jobs 1 are processed is minimized. In other words, the goal is to find a partition of the Jobs into two subsets,J {1, , n} and 12 = {1, . N} J, so that Max{ P J Pi, xiii pi} is the smallest possible. We refer to this measure as the makes of the Jobs (on two machines). It is possible to compute the minimum makes exactly in time polynomial in n and P = Pen and furthermore, to find an optimal partition of Jobs on the two machines. Assuming you have such an exact, pseudo-polynomial time algorithm, show how you can get an FATS for the problem. Question 4 Let P be a set of points and d(;, a distance measure over P that obeys the triangle inequality.

As we defined in class, For a point pi 2 P and a subsets P we let d(pi, S) fee = minibus{d(pi, and we use the notation R(P, S) deaf = maximum {d(pi, S)}. Consider the following procedure that gets as input P and a distance parameter r. Centers(P, r) l. C {Pl} 2. For I = 2 to n do ; if or thence c [ 3. Output(C) Item A. Explain why the output C satisfies R(P,C) or. Item B. For an integer eke use the notation Ark(P) = miss: SIS k{R(P, S)}. Show that if Ark(P) r then the output C satisfies Cyclic k. Item C. Suppose that the minimal distance between any two points in P is 1 and the maximum distance is D 2 where D = at for some integer t.

Describe an algorithm hat receives as input P, D, and k, uses calls to the procedure Centers and returns a subset C P such that Cyclic k and R(P,C) ark(P). The running time of the algorithm should be O(no log(D)). Guidance: The algorithm should call Centers(P,r) with growing values of r, starting from r = 1. Question 5 be a discrete and finite probability space, and let be a random variable over . Suppose we know that: (1) The range of is {O, 1, . ,M} for some integer value M; (2) The expectation of is p, which is an integer. Give as good a lower bound as you can on Pr[ p].

Question 6 SMS} be a family of subsets such that for every 1 I m we have that Is , n} and Soil = 3. For a partition of {1, , n} into three (disjoint) parts AY,AY,AY we denote by c(AY the number of subsets Is 2 F such that each of the AY, 3 2 AY, 8 2 AY then Is is such a subset). We would like to find a partition (AY,AY,AY) that maximizes c(AY Since this problem is hard we will design an approximation algorithm. Describe and analyze an efficient randomized approximation algorithm for this problem that with probability at least 1 – gives a constant-factor approximation (where is a parameter to the algorithm).