# 算法代写 | Compsci 220 Assignment 1

这个作业是分析算法的最坏运行时间

Compsci 220 Assignment 1

1. (10 marks) Suppose you are given 3 algorithms A1, A2 and A3 solving the same problem. You

know that in the worst case the running times are

T1(n) = 108n

4 + 1010n, T2(n) = n

2

10n

, T3(n) = 1012n

2

log10 n

10 + log10(n

n

)

(a) Which algorithm is the fastest for very large inputs? Which algorithm is the slowest for

very large inputs? (Justify your answer.)

(b) For which problem sizes is A2 the better than A1? (Justify your answer.)

(c) For which problem sizes is A2 the better than A3? (Justify your answer.)

You can consider inputs only of size ≥ 2.

1

2. (10 marks) Work out the recurrence relation which describes the number of elementary operations in the worst/best/average cases (justify your answer). In this question comparisons and

all arithmetic operations are considered to be elementary.

List a is a global variable, which has at least 2n elements.

0: function Blah (positive integer n)

1: if n < 3 then

2: return 0

3: if n%2 = 0 then

4: for i ← 0 to

n

2

do

5: a[n] ← a[n] + i

6: else

7: a[n] ← a[n] · 2

8: return Blah(jn

2

k

+ 1)

3. (10 marks) Work out the number of elementary operations in the worst, the best and the

average cases for the following algorithm (justify your answer):

00: function Nonsense (arrays a[1..n] and b[1..n] of length n)

01: If n < 3 then

02: return a

03: If n%3 = 0 then

04: for i ← 1 to n do

05: for j ← 2 to n do

06: If i = j − 1 then

07: a[i] ← 5

08: else

09: a[i] ← 10

10: b[i] ← 5

11: else

12: for i ← 1 to n do

13: If a[i] > b[i] then

14: for j ← 1 to n do

15: b[i] ← b[i] · j

16: else

17: a[i] ← 0

18: return a and b

2

4. (10 marks) Work out the number of elementary operations in the worst, the best and the

average cases for the following algorithm (justify your answer):

00: function Nonsense (positive integers n and m)

01: i ← 1

02: while i < n do

03: for j ← 1 to n do

04: if j%7 = 0 then

05: constant number C of elementary operations.

06: else

07: for k ← 0 to n do

08: constant number C of elementary operations.

09: i ← 5i

10: k ← 5

11: while k ≤ n do

12: Cn elementary operations

13: k ← k · k

14: for i ← 1 to n do

15: for j ← 1 to i do

16: constant number C of elementary operations.

17: for i ← 1 to n do

18: for j ← 1 to n do

19: C · i of elementary operations.

20: return m

5. (10 marks) Programming question:

• Question: Write a program that takes input as described below and prints output as

described below. The program must work with the automated marker. This question

is purely for you to obtain familiarity with the automated marker system which will be

used more in later assignments.

• Input: Input consists of many lines. At the end of each line there is hash symbol #. For

example:

blah#

45 67#

ddgfh fjhg gjkhgk#

• Output: Output consists of the same lines as the input but without #. For example,

for the input given above the output should be:

blah

45 67

ddgfh fjhg gjkhgk

• Language: You can use Java, C,C++, PyPy, Python, Go, C#, Rust, F#, Javascript.

• Number of attempts: There is a limit of 10 submission attempts for this assignment

in order to get full mark. The last submission submitted before the assignment deadline

will be the one marked. Beyond 10 submissions, a penalty will apply, but every student

who eventually submits a correct answer on time will get 75% for this question. In future

assignments, restrictions and penalties may be stronger.

3

• Useful information: 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.

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 program shouldnt know that.

Your answer to each question should be a single file (containing all nonstandard classes

you use). 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. All submissions after the assignment due time will not be considered.

Exceptions: people who have an extension.

Start early! Lots of students will be submitting their work closer to the deadline so it

may take 30 min before your program will be executed and you will 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 at the command-line like the following.

python3 task1.py <canvas.in> myout1.txt

diff myout1.txtcanvas.out1

If you are on a Windows platform you may need to download diff.exe or use alternatives

fc or comp.