Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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.

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.

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