Question:

1. For all algorithms that you are asked to "give" or "design", you should Describe your algorithm clearly in English. Give pseudocode. Argue correctness. Give the best upper bound that you can for the running time. 2. If you give a Dynamic Programming algorithm, the above requirements are modified as follows: (a) Clearly define the subproblems in English. (b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an inductive proof of correctness too for practice but points will not be deducted if you don't). Then give the recurrence in symbols. (c) State boundary conditions. (d) Analyze time. (e) Analyze space. (f) If you're filling in a matrix, explain the order to fill in subproblems in English. (g) Give pseudocode. 5. (30 points) There are n libraries L1, L2, ..., Ln. We want to store copies of a book in some libraries. Storing a copy at Li incurs a purchase cost Gi (assume integer (i > 0). A copy of the book is always stored at Ln. If a user requests the book from Li and Li does not have it, then Lil1, Li 12, ... are searched sequentially until a copy of the book is found at L; for some j>i. This results in a user delay of j - i. (Note that, in this case, no library Lk with an index k smaller than i is searched; also, if the user finds the book at L, then the user delay is 0.) We define the total cost as the sum of the purchase costs and the user delays associated with all n servers. For example, if there are 4 libraries, and copies of the book are stored at Li and L4, the total cost is c +64 +2+1. Give an efficient algorithm that returns (a) the minimum total cost; and (b) a set of libraries where copies of the books must be placed to achieve the minimum total cost