5. Apply the Earliest-Deadline-First rule to obtain the schedule for the following set of requests that minimizes the maximum lateness: (ti,di)= (1,8),(3,6),(3,4). What is the maximum lateness of the schedule you found? 6. Consider the following instance of the clustering problem where we have four objects p1,,p4 and the distance function is given in the following table: Suppose we want to group them into two groups (i.e., k=2 ). Apply the optimal greedy algorithm to find the 2-clustering with the maximum possible spacing for these objects. 7. Recall that the optimal greedy algorithm for Interval Partitioning as covered in the lectures requires computing the depth of the instance before it can assign labels to each request. In fact, it is possible to solve this problem without having to compute the depth in advance. Modify the algorithm so that it does not need to know the depth before assigning labels. Argue why the modified algorithm is still correct. As an aside, note how the modified algorithm implicitly computes the depth since the number of resources used in the resulting schedule is equal to the depth of the instance