Assignment 2 COMP3121/9101 21T3 Released September 29, due October 13 In this assignment we apply divide and conquer (including multiplication of large integers and the Fast Fourier Transform) and the greedy method. There are five problems, for a total of 100 marks. Your solutions must be typed, machine readable PDF files. All submissions will be checked for plagiarism! For each question requiring you to design an algorithm, you must justify the correct- ness of your algorithm. If a time bound is specified in the question, you also must argue that your algorithm meets this time bound. Partial credit will be awarded for progress towards a solution. 1. (20 points) You are given n stacks of blocks. The ith stack contains hi > 0 identical blocks. You are also able to move any number of blocks from the ith stack to the (i + 1)th stack. You want to know if the sizes of the stacks can be made strictly increasing. For example ⟨1, 3, 6, 8⟩ is acceptable, but ⟨1, 4, 4, 7⟩ is not. Design an O(n) algorithm that determines whether it is possible to make the sizes of the stacks strictly increasing. 2. (20 points) Alice has n tasks to do, the ith of which is due by the day di. She can work on one task each day, and will complete each task in one day. Morever, Alice is a severe procrastinator and wants to accomplish every task as close as possible to its due date. If Alice finishes the ith task on day j, her rage will increase by di − j. Design an O(n log n) algorithm that determines whether all tasks can be completed by their deadlines, and if so, outputs the minimum total rage that Alice can accumulate. 3. (20 points) Define the separation of an array of integers to be the smallest difference between any two integers in the array. You are given an array A of n distinct positive integers, each no larger than m. For a given positive integer k satisfying 2 ≤ k ≤ n, you wish to select a length k subarray of A with the largest possible separation. This subarray need not be contiguous. Design an O(n logm) algorithm to select such a subarray. 4. (20 points) You are given a set of real numbers S = {t1, t2, . . . , tn}, where n = |S| is a positive integer. Your task is to construct a polynomial P of degree n and leading coefficient 1, i.e. P (x) = xn + an−1xn−1 + an−2 xn−2 + . . .+ a2 x2 + a1 x+ a0, 1 such that P (t1) = P (t2) = . . . = P (tn). Design an O(n log2 n) algorithm to construct such a polynomial and evaluate its coefficients. 5. (20 points) Aleks received an offer from UNSW and he wants to graduate as soon as possible. His program requires him to complete n courses in an order of his choice. The courses are labelled 1, 2, . . . , n, where course i takes ti weeks to complete. Aleks gives you these values in an array A. However, some pairs of courses overlap. If courses i and j overlap, then a student who has already completed either course can complete the other in a number of weeks less than both ti and tj. Using the UNSW handbook, Aleks has produced another array B with m entries. Each entry consists of an unordered pair of distinct courses which overlap (say p = {i, j}), as well as the number of weeks tp required to complete either course if the other has already been completed. For each such pair, you are guaranteed that tp < min(ti, tj). Design an O((n+m) log(n+m)) time algorithm that finds the minimum number of weeks required to complete all n courses. Page 2