3. In this question well consider weighted problems. (a) Consider the weighted interval scheduling problem. In this problem, the input is a list of n intervals-with-weights, each of which is specified by (starti , endi , wti). The goal is now to find a subset of the given intervals in which no two overlap and to maximize the sum of the weights, rather than the total number of intervals in your subset. That is, if your list has length n, the goal is to find S {1, . . . , n} P such that for any i, j S, interval i and interval j do not overlap, and maximizing iS wti. Consider the greedy algorithm for interval scheduling from class, which selects the job with the earliest end time first. Give an example of weighted interval scheduling with at least 5 intervals where this greedy algorithm fails. Show the order in which the algorithm selects the intervals, and also show a higher-weight subset of non-overlapping intervals than the subset output by the greedy algorithm. Same comments apply as on problem 2

(b) Consider the Knapsack problem: the input is a list of n items, each with a value and weight (vali , wti), and a threshold weight W. All values and weights are strictly positive. The goal is to select a subset P S of the items such that iS wti W and maximizing P iS vali. (Note that, unlike change-making, here there is only one of each item, whereas in change-making you in principle have an unlimited number of each type of coin.) Consider a greedy algorithm for this problem which makes greedy choices as follows: among the remaining items, choose the item of maximum value such that it will not make the total weight exceed the threshold W. Give an example of knapsack with at least 5 items where this greedy algorithm fails. Show the order in which the algorithm selects the items, and also show a higher-value subset whose weight does not exceed the threshold. Same comments apply as on problem 2.

(c) Now consider the following algorithm for the knapsack problem. Call the relative value of item i the ratio vali/wti. Consider the greedy algorithm which, among the remaining items, chooses the item of maximum relative value such that it will not make the total weight exceed the threshold W. Give an example of knapsack where this greedy algorithm fails. Show the order in which the algorithm selects the items, and also show a higher-value subset whose weight does not exceed the threshold. Same comments apply as on problem 2.

example of problem 2(no need to answer)

3. In this question we'll consider weighted problems. (a) Consider the weighted interval scheduling problem. In this problem, the input is a list of n intervals-with-weights, each of which is specified by starti, endi, wti). The goal is now to find a subset of the given intervals in which no two overlap and to maximize the sum of the weights, rather than the total number of intervals in your subset. That is, if your list has length n, the goal is to find S {1,...,n} such that for any i,j ES, interval i and interval j do not overlap, and maximizing Lies wti. Consider the greedy algorithm for interval scheduling from class, which selects the job with the earliest end time first. Give an example of weighted interval scheduling with at least 5 intervals where this greedy algorithm fails. Show the order in which the algorithm selects the intervals, and also show a higher-weight subset of non-overlapping intervals than the subset output by the greedy algorithm. Same comments apply as on problem 2. (b) Consider the knapsack problem: the input is a list of n items, each with a value and weight (vali, wti), and a threshold weight W. All values and weights are strictly positive. The goal is to select a subset S of the items such that Dies wt;