Description

COMP3121/9101 21T3
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.
For each question requiring you to design an algorithm, you must justify the correctness 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.
Design an O(nlogn) 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(nlogm) 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(nlog2 n) algorithm to construct such a polynomial and evaluate its coefficients.
5. (20 points) Aleks received an offer from UNSW and he wants to graudate 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.
However, some courses are extensions of other courses. If course j is an extension of course i, then a student who has already completed course i can complete course j in fewer than tj weeks.
Aleks provides you with a set S consisting of m ordered pairs of courses, as well as a helper function f which he has conveniently produced from the UNSW handbook. For a pair (i,j) ∈ S, f(i,j) calculates in constant time the number of weeks required to complete course j if course i has already been completed. Note that f(i,j) ≤ tj, with equality if i = j or if course j is not an extension of course i. Note also that the function f only accepts pairs from S.
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