算法代写 | 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.