CompSci 220

Assignment 1

Due: Monday, August 9th, by 10pm.

Semester 2, 2021

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, feel free to post on Piazza! You can also contact the tutors and the lecturer. Note that sometimes we can’t answer all your questions (we don’t want to be giving away the answers) but we will help you as much as we can.

You must show your working to get full marks You should submit via Canvas a single PDF file containing the answers to the written questions. A scanned handwritten submission is acceptable if and only if it is clearly legible. Hard to read work may 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 the different time. It is quite possible that you might be on time on your watch and late on Canvas. To avoid these kind of situation submit the assignments at least 5 min before the due time.

Please note that late assignments cannot be marked under any circumstances. (With that said: if you find yourself unable to complete this assignment due to illness, injury, or personal/familial misfortune, please email Richard as soon as possible.)

Best of luck, and enjoy the problems!

1. Running times (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

You may assume the minimum input size is 10. Answer the following questions. You must justify your answers.

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

(b) For what problem sizes range is A1 the best algorithm to use? Answer the same question for A2 and A3.

(c) Suppose that we run each algorithm on a large problem instance of size n. Then we feed in an input of size 100n and re-run the algorithms on the new input. What would you expect to happen to the running times of each algorithm?

(d) Suppose that we have limited computation resource that only allows us to do at most 10⁹ elementary operations. And we wish to process as much input as we can. Which algorithm should we choose?

2. Asymptotic notations (10 marks).

Answer each of the following questions.

(a) Suppose T(n) = 15n+ 10. Prove that T(n) is not O() using the definition of Big-O only.

(b) Suppose T(n) = log 15n + 0.3n² + . Prove that T(n) is both Θ(n³ log n) and O(n⁴) using the definition of Big-O only.

(c) Suppose T(n) is Ω(n) and O(n³). Decide whether this implies the conclusion that T(n) is Θ(n²) and prove your decision.

(d) Suppose T(n) = 7 lg n + 5n + n lg lg n + 3n ln n. For each of the following, decide whether T(n) is:

i. Ω(n²)

ii. O(n²)

iii. Ω(n)

iv. O(n log² n)

 v. Θ(n log n)

Justify your answer for each.

3. Pseudo-code analysis (10 marks)

(a) How many elementary operations does the following pseudo-code have? Here we are only considering the number of elementary operation e within the main loop-body (i.e. you can ignore all other operations such as additions, multiplications, condition checks, etc.) Show all working.

function Meh (positive integer n)

for (int i = 1; i ≤ n; i = i ∗ 2)

for (int j = 0; j < n; j + +)

if i == j

for (int k = 1; k < n³; k+ = n)

... constant number C of elementary operations e

end for

else

... constant number C of elementary operations e

end if

end for

end for

(b) Show that the number of elementary operations of the following pseudo-code is in order of Θ(n log n). Hint: you may find the approximation formula  useful.

function Huh (positive integer n)

for (int i = 1; i ≤ n; i + +)

for (int j = 1; j < i; j = j ∗ 2)

... constant number C of elementary operations e

end for

end for

4. (10 marks) Programming question:

The purpose of this question is to get you familiarized with the automarker system which we will use more later in the course.

● Question: Given a string S and a char c, we wish to remove all occurrences of c from S. For example, let S = reGedazxEreQpt and c = e, then the result is rGdazxErQpt.

● Input: The first line of the input consists of a single integer n, denoting the number of cases we have, followed by n lines of strings. Each of the n lines contains the string S and c, separated by a comma ‘,’. You may assume the string S does not contain any commas.

● Output: For each of the n lines of S, c pairs. Print a single line containing the string S with all occurrences of c removed.

● Sample input:

2

ufIurkfzMMkrqkPAfnzqw,f

NUiRelrqrnNRaJvngjAsdrARQxr,R

● Sample output:

uIurkzMMkrqkPAnzqw

NUielrqrnNaJvngjAsdrAQxr

● Language: Your program has to be written in Python 3.

● Note: There is a limit of 10 submission attempts for this question. This is to prevent people from spamming the automarker (i.e. please don’t use the automarker as a de-bugger, you should test your program carefully before submitting it to the automarker). You should test your program with different inputs, a small sample input and its corre-sponding output will be on Canvas. Just getting the correct output with the sample is not enough to ensure the correctness of your program.

Please do not share your code with other students. However, I’m happy if you want to share test cases. I have uploaded a simple Python program to randomly generate input on Canvas as well. You are welcome to use it or develop your own test cases.

The last submission submitted before the assignment deadline will be the one marked. 

Good luck and have fun.

● Other 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.

Your can only submit a single program file (containing all nonstandard classes you use, e.g. you can have nested classes if you use Java).

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.txt canvas.out1

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