Exercise (Ambitious Student Revisited) Recall the Ambitious Student problem from the lecture: Given intervals L1=[s1,e1),,Ln= [sn,en), compute the largest number k such that there is a conflict-free set of k intervals Li1,,Lik. In the lecture you have seen that this problem can be solved by a greedy algorithm using a carefully chosen strategy. In this exercise, we will investigate further strategies; your task is to decide for each one whether it leads to a correct greedy algorithm, or whether the strategy is wrong. In the first case, give a short correctness proof (you don't have to analyze the running time). In the second case, give a counterexample. a. Pick the interval Li that ends last, discard all intervals that conflict with Li and recurse. b. Pick the interval Li that starts first, discard all intervals that conflict with Li and recurse. c. Pick the interval Li that starts last, discard all intervals that conflict with Li and recurse. d. Pick the interval Li that conflicts with the fewest other intervals, discards all intervals that conflict with Li and recurse. e. If no intervals conflict, pick them all. Otherwise, discard the interval with the longest duration and recurse. f. If no intervals conflict, pick them all. Otherwise, discard the interval that conflicts with the most other intervals and recurse. g. Let Li be the interval with the earliest start time, and let Lj be the interval with the second earliest start time. - If LiLj=, pick Li and recurse on everything but Li. - If LjLi, discard Li and recurse. - Otherwise, discard Lj and recurse. h. If any interval Li completely contains another interval, discard Li and recurse. Otherwise, pick the interval Lj that ends last, discard all intervals that conflict with Lj and recurse. Exercise (Ambitious Student Revisited) Recall the Ambitious Student problem from the lecture: Given intervals L1=[s1,e1),,Ln= [sn,en), compute the largest number k such that there is a conflict-free set of k intervals Li1,,Lik. In the lecture you have seen that this problem can be solved by a greedy algorithm using a carefully chosen strategy. In this exercise, we will investigate further strategies; your task is to decide for each one whether it leads to a correct greedy algorithm, or whether the strategy is wrong. In the first case, give a short correctness proof (you don't have to analyze the running time). In the second case, give a counterexample. a. Pick the interval Li that ends last, discard all intervals that conflict with Li and recurse. b. Pick the interval Li that starts first, discard all intervals that conflict with Li and recurse. c. Pick the interval Li that starts last, discard all intervals that conflict with Li and recurse. d. Pick the interval Li that conflicts with the fewest other intervals, discards all intervals that conflict with Li and recurse. e. If no intervals conflict, pick them all. Otherwise, discard the interval with the longest duration and recurse. f. If no intervals conflict, pick them all. Otherwise, discard the interval that conflicts with the most other intervals and recurse. g. Let Li be the interval with the earliest start time, and let Lj be the interval with the second earliest start time. - If LiLj=, pick Li and recurse on everything but Li. - If LjLi, discard Li and recurse. - Otherwise, discard Lj and recurse. h. If any interval Li completely contains another interval, discard Li and recurse. Otherwise, pick the interval Lj that ends last, discard all intervals that conflict with Lj and recurse
