# Computer Science

Task 1: Sort of Sorted Arrays [50 marks]
Your genius friend discovered an amazingly fast sorting algorithm using deep quantum neural networks.
Unfortunately, due to complicated quantum physics beyond the scope of this unit, the algorithm’s output
is only sort of sorted. An array S of n integers is sort of sorted if for some x, S[i] is the (x+ i mod n)-th
smallest number. (Note that 0-th smallest number is the smallest and the (n − 1)-th smallest is the
largest.)
For example, [2, 3, 4, 5, 1] is a sort of sorted array with x = 1 and [4, 5, 1, 2, 3] is sort of sorted with
x = 3.
You are given a sort of sorted array S containing n distinct integers, but you are not given x. Your
task is to design an O(log n)-time divide-and-conquer algorithm that finds the largest number in S.
(a) Description of how your algorithm works (“in plain English”). Make sure to clearly define your
divide step (i.e. subproblems and base cases) and merge step.
(b) Prove that your algorithm is correct.
(c) Prove an upper bound on the time complexity of your algorithm.
(d) Implement your algorithm on Ed.
Task 2: Gotta Catch the Most [50 marks]
After a hard day’s work, you relax by playing Pokemon Go. You only have enough time to visit one
Pokestop and want to find one with the most Pokemon in its vicinity.
We now state the problem more formally. You are given a set S of ns non-overlapping squares
(representing the area near a Pokestop) with a common side length L and a set P of np distinct points
(representing Pokemon). Every point has integer coordinates, L is an integer, and the corners of every
square have integer coordinates. Let n = ns + np. Your task is to design an O(n log n)-time divide-and-
conquer algorithm that finds the square that contains the most number of points.
Figure 1: The left-most square has the most points.
(a) Description of how your algorithm works (“in plain English”). Make sure to clearly define your
divide step (i.e. subproblems and base cases) and merge step.
1
(b) Prove that your algorithm is correct.
(c) Prove an upper bound on the time complexity of your algorithm.
Here are some guidelines to make it easier for you to write and for us to mark:
• Assume that you can check in O(1) time whether a square s contains a point p, whether a point
p is on a line `, and whether a line ` passes through a square s. Please do not describe your
own methods for these simple checks. For instance, you can simply write “if square s contains
point p, …” without further explanation.
• Assume that you can sort n squares and points in O(n log n) time. Please do not describe your
own sorting algorithm. For instance, you can simply write “sort squares in ascending order of
their center’s y-coordinate”
Submission details
• Submission deadline is Wednesday 31 March, at 23:59. Late submissions without special
consideration will be subject to the penalties specified in the first lecture (20% per day). Submis-
sions later than Friday 2 April, 23:59 will not be accepted.
• Submission time is the max of the submission times to Gradescope and Ed. For example, if you
submit to Gradescope on time but your implementation on Ed is one day late, 20% will be deducted
from the entire assignment. 