CS220 — 2023 Semester 1 Assignment 2
There are four problems listed below. To get full credit for this assignment you need to complete
all of them!
If you are stuck or confused by any of the problems, please ask your tutor, lecturer or post to
Piazza.
To get full marks, you need to show all working.
You should submit via Canvas a single PDF file containing the answers to the written questions. A
scanned handwritten submission is acceptable if it is neatly written (if it’s hard to read, it will not be
marked). If typing the assignment, do the best you can with mathematical symbols. For exponents,
write something like 2?n if using plain text. Use LaTeX if you really want it to look good.
Answers to programming questions must be submitted via the automated marker system:
https://www.automarker.cs.auckland.ac.nz/student.php.
Please try to submit your assignments no later than 5 min before the due time. Even though the
time is a universal thing your watch and Canvas built-in clock could show a different time. It is quite
possible that you might be on time on your watch and late on Canvas. To avoid this kind of situation
submit the assignments at least 5 min before the due time.
Late assignments will not be accepted. If you need an extension due to illness or other personal
circumstance, please email marc.vinyals@auckland.ac.nz as early as possible before the due date.
Best of luck, and enjoy the problems!
Problem 1 (10 marks). Consider the following sorting algorithm
1 Function unstablesort(a):
2 return selsort(shuffle(a))
a is a list. shuffle is an algorithm that randomly permutes its input. selsort is the selection
sort algorithm.
Your task is to build a stable sorting algorithm using unstablesort as a subroutine. Your algorithm
may call unstablesort for free; in other words you should not count time spent inside function
unstablesort towards the running time of your algorithm. Besides calls to unstablesort your
algorithm is allowed a budget of O(n) elementary operations. Your algorithm must call unstablesort
at least once and use its results in a meaningful way. Your algorithm only needs to work when the
input is a list of integers. You may call unstablesort on an input that is a list of objects other than
integers, but in that case you need to specify (informally) how to compare those objects.
a) Describe your algorithm in pseudocode.
b) Explain why your algorithm is stable. You do not need to write a formal proof, but your
argument should be detailed enough to convince a fellow student.
c) Show that the running time of your algorithm is O(n) excluding calls to unstablesort.
1
University of Auckland — CS220 — 2023 Semester 1 Assignment 2
Problem 2 (15 marks). You found a dusty old book describing a forgotten algorithm merge3 that can
merge three sorted lists using at most n comparisons. That is, if the sizes of the lists are n1, n2, and
n3 respectively, then the algorithm does n= n1 + n2 + n3 comparisons in the worst case. Calculate
the number of comparisons in the worst case of the following algorithm.
1 Function sort(a):
2 if n≤ 1 then
3 return a
4 a1← sort(a[1 .. n/3])
5 a2← sort(a[n/3+ 1 .. 2n/3])
6 a3← sort(a[2n/3+ 1 .. n])
7 return merge3(a1, a2, a3)
a) Write down a recurrence relation that describes the number of comparisons done by the
algorithm in the worst case. Do not count the comparison in line 2.
b) Find a closed form for (in other words, solve) the recurrence. You may ignore any rounding
issues.
c) Prove that your guess for the closed form is correct.
d) Name the algorithm seen in class that is the closest to algorithm sort, and how many
comparisons it performs in the worst-case.
e) Given the points above, what is wrong with algorithm merge3?
Hint: constant factors are relevant for this subquestion. That is, whether a function is 2n3 or
5n3 can make a difference.
Problem 3 (5 marks). The quicksort algorithm recurses (calls itself) on the two sublists of elements
strictly smaller than the pivot and strictly larger that the pivot. What would happen if it recursed on
the sublists strictly smaller than the pivot and larger or equal than the pivot, including the pivot?
a) Is the algorithm correct? i.e. does it ever produce a wrong answer?
b) Is the worst-case running time better or worse than the original? Give an example supporting
your claim.
You can choose to work with the simpler partitioning method using multiple output lists instead
of Hoare’s partitioning method. You may also assume that the leftmost element in the input is chosen
as the pivot.
2
University of Auckland — CS220 — 2023 Semester 1 Assignment 2
Problem 4 (10 marks). Write a programme that takes input as described below and prints output as
described below. The programme must work with the automated marker.
A variant of the game of boules works as follows. First, a small ball is thrown onto a field, and
then every player throws one large ball each, attempting to get it as close as possible to the first
ball. Finally players are ranked by how close their ball is to the small ball. Given the names and
coordinates of all balls, compute the player ranking.
Input: The first input line is a non-negative integer n indicating how many players there are. The
next n lines consist of three elements each, separated by spaces: one string indicating the owner
of a ball, and the (x , y) coordinates of the ball with respect to the small ball in millimetres, as two
integers. For example:
3
Antoine 0 100
Brigitte 100 -10
Camille 50 50
You can assume that the small ball is at position (0,0).
Output: The output must consist of the player names, ranked by the proximity of their ball to the
small ball. You may assume that there are no ties. For example, for the input given above the output
should be:
Camille
Antoine
Brigitte
Access the automarker via https://www.automarker.cs.auckland.ac.nz/student.php.
You must submit your solution as a Python programme. You may not call Python’s built-in
functions for sorting, nor use code from Canvas. Implementing any algorithm we have seen in
class is allowed as long as you write the implementation yourself.
There are two problems BoulesEasy and BoulesHard set up, with different time limits. You can
submit the same programme to both problems.
You can assume that input will come from standard input (stdin) in a stream that represents one
string per line. Output should be sent to standard output (stdout). In the automarker, the input will
come from a file that is piped to standard in and the output redirected to a file, but your programme
shouldn’t know that.
Your code should be contained in a single file. You may assume that the automarker has access to
all standard libraries.
If your submission was put in the queue before the assignment due time then it will be accepted.
Submissions after the assignment due time will not be considered.
Start early! Lots of students will be submitting their work closer to the deadline so it might take
30 min before your programme is executed and you get to see the results.
Your output should exactly match the one in the system for the submission to be correct. So be
careful with the printing. No extra symbols! It may look the same on the first glance but may have a
different end of line character or extra space.
Please test your programme locally before submitting it. You may use a command sequence like
the following.
$ python3 task1.py < sample.in > my.out
$ diff my.out sample.out