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
