COMPSCI220 - CS220 Algorithms and Data Structures - Assignment 1
Compsci 220
Assignment 1
Due: Monday, 8th August, by 10pm. Semester 2, 2022
There are five 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!
Show all working; if you do not show your work the mark will be reduced. 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 very 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:
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 us as soon as possible. We can come up with solutions to help you succeed in CS220!)
Best of luck, and enjoy the problems!
1. (10 marks) Suppose you are given 3 algorithms A1, A2 and A3 solving the same problem. You know that in the the running times are
T1(n) = n5n, T2(n) = 210n2 + n3, T3(n) = 105 log10(nn)
(a) Which algorithm is the fastest for very large inputs? Which algorithm is the slowest forvery 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.)
2. (10 marks) Asymptotic Notations:
1. (a) Prove using definitions only that nnlog(n) is not O(nn). (HINT: proof by contradiction)
2. (b) Prove that n3 − 50 is Ω(n2), either with limit laws or definitions.
3. (c) Prove that ?(15)n2 log(5n) + 0.4n + √n is Θ(n2 log(n)) using definitions only.
4. (d) Suppose that f, h, g, k are functions and that f = h · g + k. Suppose further, that h is O(n2), g is Θ(log(n)) and k is Ω(n). What do we know about f? State everything we can determine for full marks.
3. (10 marks) Elementary operations and algorithms:
(a) Work out the number of elementary operations in the following algorithm. For this exercise only count the constant number C of elementary operations as executed on lines 2 and 4.
1 function Blah (positive integer n)
2 fori←2 to n do
3 Constant number C of elementary operations.
4 for j ← 1 to i do
5 Constant number C of elementary operations.
(b) Work out the number of elementary operations the following algorithm uses in an average case. You can assume that the probability of getting a number divisible by 3 is 1/ 3
1 function Meh (positive integer n)
2 ifn%3=0do
3 for i ← 0 to n − 1 do
4 for j ← 0 to n − 1, j ← j + 2 do
5 if i=j do
6 for k←0 to n4, k←k+n2 do
7 Constant number C of elementary operations.
8 else
9 Constant number C of elementary operations.
10 else
11 Execute Meh(3n2)
4. (10 marks) Elementary operations and algorithms:
(a) What is the explicit form of the following recurrence relation: T(n) = 3T(n/3) + 1; T(1) = 1.
(b) What is the explicit form of the following recurrence relation: T(n) = T(n − 1) + log2 n; T(0) = 0. Hint n! is approximately
5. (10 marks) Programming question:
· Question: Write a program that takes an input as described below, and prints an output also 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 Python, Python, Python, or Python, whichever you fancy the most!
· 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.
· 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 shouldn’t 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.txt canvas.out1
If you are on a Windows platform you may need to download diff.exe or use alternatives fc or comp.
