The University of Melbourne School of Computing and Information Systems COMP90038 Algorithms and Complexity Assignment 1, Semester 1 2020
To improve your understanding of the time complexity of algorithms and recurrence relations. To develop problem-solving and design skills. To improve written communication skills; in particular the ability to present algorithms clearly, precisely and unambiguously.
[4 marks] Consider the following pseudocode:
x ← 0
for k ← 1 to n do
for j ← k to 2n do
x ← x + 1
where c is a positive constant. Assume that n = 3m.
Solve the recurrence. Your answer should show how you derive the closed form.
Design an algorithm to find how many different combinations that the manager can choose from. For example, if there are five different products, of which the prices are A = [1,2,3,4,6] the budget k = 4, the algorithm should return 2 as only the combinations of (1,2) and (1,3) do not exceed the budget.
Note, that the algorithm would be incorrect if it returned a value of 1 corresponding to the product in A = 4 as this would not meet the criteria of ‘two different products’ given the budget constraint.
Full marks will be given if your algorithm runs in time. Your algorithm should be presented in unambiguous pseudocode or Python code.
Your colleague has won the lottery and decided to leave university, so it is up to you to finish the algorithm. Unfortunately, she did not define the data structure for the variable X. However, you can tell from the documentation that the data structure was supposed to be either a stack or a queue.
function IsBipartite(G[0...n − 1][0...n − 1]) . Input is an adjacency matrix n × n
numSeen = 0
colour[0...n-1] ← [-1, ···, -1]
X ← EmptyQueueOrStack( ) PushOrEnqueue(X, <0, RED>) while numSeen < n do i, c ← PopOrDequeue(X) if colour[i] = -1 then
numSeen ← numSeen + 1
colour[i] ← c
nextColour ← RED if c = RED then nextColour ← BLUE
for j ← 0 to n − 1 do if G[i][j] = 1 then if colour[j] = c then return false
PushOrEnqueue(X, <j, nextColour>)
A number of simplifying assumptions have been made in this task:
For example, in the 2D array below, the size of the largest connected burnt area is 5.
Your algorithm should be presented in unambiguous pseudocode or Python code. Note: it may be necessary to modularise your solution using multiple functions.
Full marks will only be awarded if your algorithm is correct with appropriate time complexity. Here, we have not provided a clear definition of ‘appropriate time complexity’. We do this, as we want you to think carefully about the design of your solution – lots and lots of nested for loops is not the correct approach to use.