Overview
COMP3506 Homework 1
Weighting: 15%
Due date: 21st August 2020, 11:55 pm
This purpose of this assignment is for you to become familiar with understanding the main concepts and notation of asymptotic analysis of algorithms, to gain practice writing simple mathematical proofs, to learn how to read and write pseudocode algorithms, and to practice using binary search and writing and analysing recursive algorithms.
Marks
This assignment is worth 15% of your total grade. COMP3506 students will be marked on questions 1 to 4 out of 50 marks. COMP7505 are required to additionally do question 5 and will be marked out of 60 marks.
Partial marks may be awarded for partially correct answers and answers lacking justification where it is required. Submission Instructions
• Your answers to the written questions should be submitted as a file called A1-[Your Student Number Here].pdf via the Homework 1 – Written submission. Do not include your full name in your pdf submission.
• Hand-written answers will not be marked. If you are comfortable with the LATEX typesetting system, it is strongly recommended that you write your answers using it, however it is not a requirement.
• Your solution to Q3a will be submitted via Gradescope to the Homework 1 – Q3 Programming submission. You should only submit your completed ArrayCartesianPlane.java file. No marks will be awarded for non- compiling submissions, or submissions which import non-supported 3rd party libraries. You should follow all constraints laid out in question 3 or risk losing marks for the question.
Late Submissions and Extensions
Late submissions will not be accepted. It is your responsibility to ensure you have submitted your work well in advance of the deadline (taking into account the possibility of computer, internet, or Gradescope issues). You are allowed to submit multiple times, and only the latest submission before the deadline will be marked. See the ECP for information about extensions.
Academic Misconduct
This assignment is an individual assignment. Posting questions or copying answers from the internet is considered cheating, as is sharing your answers with classmates. All your work (including code) will be analysed by sophisti- cated plagiarism detection software.
Students are reminded of the University’s policy on student misconduct, including plagiarism. See the course pro- file and the School web page: http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism.
1
Questions
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16:
1. Consider the following algorithm, CoolAlgorithm, which takes a positive integer n and outputs another integer. Recall that ‘&’ indicates the bitwise AND operation and ‘a >> b’ indicates the binary representation of a shifted to the right b times.
procedure CoolAlgorithm(int n) sum ← 0
if n%2==0then for i = 0 to n do
forj=iton2 do sum ← sum + i + j
end for end for
else
while n > 0 do
sum ← sum + (n & 1)
n ← (n >> 1) end while
end if
return sum end procedure
Note that the runtime of the above algorithm depends not only on the size of the input n, but also on a numerical property of n. For all of the following questions, you must assume that n is a positive integer.
(a) (3 marks) Represent the running time (i.e. the number of primitive operations) of the algorithm when the input n is odd, as a mathematical function called Todd(n). State all assumptions made and explain all your reasoning.
(b) (2 marks) Find a function g(n) such that Todd(n) ∈ O(g(n)). Your g(n) should be such that the Big-O bound is as tight as possible (e.g. no constants or lower order terms). Using the formal definition of Big-O, prove this bound and explain all your reasoning.
(Hint: you need to find values of c and n0 to prove the Big-O bound you gave is valid).
(c) (2 marks) Similarly, find the tightest Big-Ω bound of Todd(n) and use the formal definition of Big-Ω to prove the bound is correct. Does a Big-Θ bound for Todd(n) exist? If so, give it. If not, explain why it doesn’t exist.
(d) (3 marks) Represent the running time (as you did in part (a)) for the algorithm when the input n is even, as a function called Teven(n). State all assumptions made and explain all your reasoning. Also give a tight Big-O and Big-Ω bound on Teven(n). You do not need to formally prove these bounds.
(e) (2 marks) The running time for the algorithm has a best case and worst case, and which case occurs for a given input n to the algorithm depends on the parity of n.
Give a Big-O bound on the best case running time of the algorithm, and a Big-Ω bound on the worst case running time of the algorithm (and state which parity of the input corresponds with which case).
(f) (2 marks) We can represent the runtime of the entire algorithm, say T(n), as
algorithm exists, describe it. If not, explain why it doesn’t exist.
(g) (2 marks) Your classmate tells you that Big-O represents the worst case runtime of an algorithm, and similarly that Big-Ω represents the best case runtime. Is your classmate correct? Explain why/why not. Your answers for (e) and (f) may be useful for answering this.
(h) (1 mark) Prove that an algorithm runs in Θ(g(n)) time if and only if its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).
Teven(n) if n is even Todd(n) if n is odd
T(n) =
Give a Big-Ω and Big-O bound on T(n) using your previous results. If a Big-Θ bound for the entire
2
2. (a)
(4 marks) Devise a recursive algorithm that takes a sorted array A of length n, containing distinct (not necessarily positive) integers, and determines whether or not there is a position i (where 0 ≤ i < n) such that A[i] = i.
• Write your algorithm in pseudocode (as a procedure called FindPosition that takes an input array A and returns a boolean).
• Your algorithm should be as efficient as possible (in terms of time complexity) for full marks.
• You will not receive any marks for an iterative solution for this question.
• You are permitted (and even encouraged) to write helper functions in your solution.
(b) (1 mark) Show and explain all the steps taken by your algorithm (e.g. show all the recursive calls, if conditions, etc) for the following input array: [−1, 0, 2, 3, 10, 11, 23, 24, 102].
(c) (3 marks) Express the worst-case running time of your algorithm as a mathematical recurrence, T(n), and explain your reasoning. Then calculate a Big-O (or Big-Θ) bound for this recurrence and show all working used to find this bound (Note: using the Master Theorem below for this question will not give you any marks for this question).
(d) The master theorem is a powerful theorem that can be used to quickly calculate a tight asymptotic bound on a mathematical recurrence. A simplified version is stated as follows: Let T(n) be a non- negative function that satisfies
aTn+g(n) forn>k
T(n) = b c
for n = k wherekisanon-negativeinteger,a≥1,b≥2,c>0,andg(n)∈Θ(nd)ford≥0. Then,
Θ(nd) T(n) ∈ Θ(nd logn)
Θ(nlogb a)
if a < bd if a = bd if a > bd
i. (1 mark) Use the master theorem, as stated above, to find a Big-Θ bound (and confirm your already found Big-O) for the recurrence you gave in (b). Show all your working.
ii. (1 mark) Use the master theorem to find a Big-Θ bound for the recurrence defined by
T(n) = 5·T n+n2 +2n 3
and T (1) = 100. Show all working.
iii. (1 mark) Use the master theorem to find a Big-Θ bound for the recurrence defined by
T(n)=8·Tn+5n+2logn+ 1 4n
and T (1) = 1. Show all working.
(e) (2 marks) Rewrite (in pseudocode) the algorithm you devised in part (a), but this time iteratively. Your algorithm should have the same runtime complexity of your recursive algorithm. Briefly explain how you determined the runtime complexity of your iterative solution.
(f) (2 marks) While both your algorithms have the same runtime complexity, one of them will usually be faster in practice (especially with large inputs) when implemented in a procedural programming language (such as Java, Python or C). Explain which version of the algorithm you would implement in Java – and why – if speed was the most important factor to you. You may need to do external research on how Java method calls work in order to answer this question in full detail. Cite any sources you used to come up with your answer.
In addition, explain and compare the space complexity of your both your recursive solution and your iterative solution (also assuming execution in a Java-like language).
3
3. In the support files for this homework on Blackboard, we have provided an interface called CartesianPlane which describes a 2D plane which can hold elements at (x, y) coordinator pairs, where x and y could potentially be negative.
(a) (5 marks) In the file ArrayCartesianPlane.java, you should implement the methods in the interface CartesianPlane using a multidimensional array as the underlying data structure.
Before starting, ensure you read and understand the following:
• Your solution will be marked with an automated test suite.
• Your code will be compiled using Java 11.
• Marks may be deducted for poor coding style. You should follow the CSSE2002 style guide, which
can be found on Blackboard.
• A sample test suite has been provided in CartesianPlaneTest.java. This test suite is not com-
prehensive and there is no guarantee that passing these will ensure passing the tests used during
marking. It is recommended, but not required, that you write your own tests for your solution.
• You may not use anything from the Java Collections Framework (e.g. ArrayLists or HashMaps). If
unsure about whether you can use a certain import, ask on Piazza.
• Do not add or use any static member variables. Do not add any public variables or methods.
• Do not modify the interface (or CartesianPlane.java at all), or any method signatures in your
implementation.
(b) (1 mark) State (using Big-O notation) the memory complexity of your implementation, ensuring you define all variables you use. Briefly explain how you came up with this bound.
(c) (1 mark) Using the bound found above, evaluate the overall memory efficiency of your implementation. You should especially consider the case where your plane is very large but has very few elements.
(d) (3 marks) State (using Big-O notation) the time complexity of the following methods:
• add
• get
• remove • resize • clear
Ensure you define all variables used in your bounds, and briefly explain how you came up with the bounds. State any assumptions you made in determining your answers. You should simplify your bounds as much as possible.
4
4. The UQ water well company has marked out an n × n grid on a plot of land, in which their hydrologists know exactly one square has a suitable water source for a water well. They have access to a drill, which uses drill bits and can test one square at a time. Now, all they they need is a strategy to find this water source.
Let the square containing the water source be (sx,sy). After drilling in a square (x,y), certain things can happen depending on where you drilled.
• If x > sx or y > sy, then the drill bit breaks and must be replaced.
• If x = sx or y = sy, the hydrologists can determine which direction the water source is in.
Note that both the above events can happen at the same time. Below is an example with n = 10 and (sx,sy) = (3,4). The water source is marked with S. Drilling in a shaded square will break the drill bit, and drilling in a square with a triangle will reveal the direction.
(a) (3 marks) The UQ water well company have decided to hire you – an algorithms expert – to devise a algorithm to find the water source as efficiently as possible.
Describe (you may do this in words, but with sufficient detail) an algorithm to solve the problem of finding the water source, assuming you can break as many drill bits as you want. Provide a Big-O bound on the number of holes you need to drill to find it with your algorithm. Your algorithm should be as efficient as possible for full marks.
You may consult the hydrologists after any drill (and with a constant time complexity cost to do so) to see if the source is in the drilled row or column, and if so which direction the water source is in.
(Hint: A linear time algorithm is not efficient enough for full marks.)
(b) (5 marks) The company, impressed with the drilling efficiency of your algorithm, assigns you to another n × n grid, which also has a water source you need to help find. However, due to budget cuts, this time you can only break 2 drill bits (at most) before finding the source. (Note that you are able to use a 3rd drill bit, but are not allowed to ever break it).
Write pseudocode for an algorithm to find the source while breaking at most 2 drill bits, and give a tight Big-O bound on the number of squares drilled (in the worst case). If you use external function calls (e.g. to consult the hydrologist, or to see if the cell you drilled is the source) you should define these, their parameters, and their return values.
Your algorithm’s time complexity should be as efficient as possible in order to receive marks. (Hint: A linear time algorithm is not efficient enough for full marks.)
5
5. (COMP7505 only) Binary search is fast because each step halves the search array. Can we do better? Maybe we could quarter the input at every step. Would this make the algorithm faster?
This “quaternary search” algorithm takes a sorted array A of length n and an integer x. It determines which quarter of A the value x would occur in, then recurses into that subarray of length n/4. When reaching an array of length n ≤ 4, it returns the index of x or −1 if x cannot be found.
(a) (3 marks) From the description above, write pseudocode for a quaternary search algorithm.
(b) (1 mark) Express the worst case running time of quaternary search as a recurrence.
(c) (2 marks) Solve the recurrence above to determine a Big-O bound on the worst case running time of quaternary search.
(d) (1 mark) Is quaternary search faster than binary search? If so, is it substantially faster? Explain briefly.
(e) (3 marks) What if we go even further? Suppose we can do k-ary search, which reduces n to n/k at each step (e.g. binary is 2-ary search). With (c) in mind, we hypothesise that k-ary search has complexity O(logk n).
Now, we can use n-ary search to search inside an n-length array. Our search finishes in one iteration because n/n = 1 and O(logn n) = O(1). We’ve solved algorithms!
Unfortunately, nothing is that easy (or we wouldn’t be here). Explain why this is not the case and comment on the actual performance of k-ary search.
6