Description

COMP3121/9101 21T3
In this assignment we review some basic algorithms and data structures. 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. You are given an array A of n positive integers. A pair of indices (i,j) where i < j is said to be consistent if A[j] − A[i] = j − i.
(a) (10 points) Design an algorithm which runs in expected O(n) time and counts the number of pairs of consistent indices.
(b) (10 points) Design an algorithm which runs in worst case O(nlogn) time and counts the number of pairs of consistent indices.

An index i is said to be fulfilling if A[1..i] has strictly greater beauty than A[1..i−1]. Design an algorithm which runs in O(n) and finds all fulfilling indices.
1
4. (20 points) You have 2n + 1 ants along a line. Their positions are described by the real numbers x−n < x−n+1 < … < xn−1 < xn. You will place food at a point x on the line, and all ants will walk along the line to reach the food. Find the value of x which minimises the total distance walked by all ants.

5. Determine whether:
(I) f(n) = O(g(n)),
(II) f(n) = Ω(g(n)), i.e. g(n) = O(f(n)),
(III) both (I) and (II), i.e. f(n) = Θ(g(n)), or
(IV) neither (I) nor (II)
for the following pairs of functions, and justify your answer. Note that log denotes the natural logarithm, with base e.
(a) (6 points) f(n) = n1+logn; g(n) = nlogn;
(b) (8 points) ;
(c) (6 points) f(n) = log2 nlog(nlogn); g(n) = (logn)2.

Page 2