1. You are given a list of activities, similar to what we discussed in the class, but already sorted by their starting time . Design an O(N) algorithm to maximize the number of non-conflicting activities (20) 2. Assume you are responsible to schedule the final exams at Dal for this semester, and you are given starting and ending time of every exam. This is a different situation than what we discussed in the class, as you cannot simply ignore an exam! Every exam must happen at the announced starting to the ending time. However, you are allowed to book multiple rooms. Given n exams, write an algorithm that schedules all events using minimum number of rooms . Prove that your solution works and state the complexity of the algorithm. (25) 3. Now you are assigned to another job, registrar office administrator. You are given the list of all students that will register at the first day of the registration, with their exact appointment time. Your job is to hire enough staff to do the task. For obvious reasons, you cannot hire an employer for less than hour and the hourly cost of an employee is some constant. Write an algorithm to minimize the total cost by minimizing the number of employer hours. Assume that registering a student is just a click and can be done instantly (takes 0 seconds!) (25) 4. G(V,E) is a graph with T as its MST, prove or disprove the following statements (25): a) If If we replace all edge weights w(u,v) by w(w,v)2, T still is a MST b) If no two edges of E have the same weight, MST will be unique 5. G(V,E) is a graph with T as its MST, suddenly an edge is added to G, (25) a) Provide an efficient algorithm (O(|E| or O(|V|) that can check whether T is still a MST b) If T is not a MST anymore, provide an efficient algorithm to build a new T’ from T.
