CS220编程代写、代写Python语言程序

日期：2023-04-20 09:23

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