(40 marks) Consider the following optimization problem. You are are writing your final term paper for PHIL 999. You have taken n books out of the library that you need for your paper, and you have read none of them. The books are all overdue by now, and the library is charging you a late fee of S1 per day per book. For each book j, you have already determined that it will take you tj days to read the book. You can only read one book at a time, and you want to return each book as soon as you finish it so you won't have to pay late fees on a book you have finished reading. The library books problem is to find the order in which to read all n books that minimizes the late fees. (a) (5 marks) Give a formal definition (pre- and post-conditions) of the problem described. (b) (5 marks) Consider the case where there are three books that take t 10, t2 5, and t3- 8 days to read, respectively. What is the optimal solution to the problem? (c) (10 marks) Give an efficient greedy algorithm that finds an optimal solution for the general case. (d) (5 marks) Explain why your algorithm returns an optimal solution (e) (10 marks) Prove that your algorithm returns an/the optimal solution. (f) (5 marks) Prove a tight asymptotic bound on the running time of your algorithm (40 marks) Consider the following optimization problem. You are are writing your final term paper for PHIL 999. You have taken n books out of the library that you need for your paper, and you have read none of them. The books are all overdue by now, and the library is charging you a late fee of S1 per day per book. For each book j, you have already determined that it will take you tj days to read the book. You can only read one book at a time, and you want to return each book as soon as you finish it so you won't have to pay late fees on a book you have finished reading. The library books problem is to find the order in which to read all n books that minimizes the late fees. (a) (5 marks) Give a formal definition (pre- and post-conditions) of the problem described. (b) (5 marks) Consider the case where there are three books that take t 10, t2 5, and t3- 8 days to read, respectively. What is the optimal solution to the problem? (c) (10 marks) Give an efficient greedy algorithm that finds an optimal solution for the general case. (d) (5 marks) Explain why your algorithm returns an optimal solution (e) (10 marks) Prove that your algorithm returns an/the optimal solution. (f) (5 marks) Prove a tight asymptotic bound on the running time of your algorithm