Documentation
For this assignment (and all assignments in this unit) you are required to document and comment
your code appropriately. This documentation/commenting must consist of (but is not
limited to):
• For each function, high-level description of that function. This should be a two or three
sentence explanation of what this function does and the approach undertaken within the
function.
• For each function, specify what the input to the function is, and what output the function
produces or returns (if appropriate).
• For each function, the Big-O time and space complexity of that function, in terms of the
input size. Make sure you specify what the variables involved in your complexity refer
to. Remember that the complexity of a function includes the complexity of any function
calls it makes.
• Within functions, comments where appropriate. Generally speaking, you would comment
complicated lines of code (which you should try to minimise) or a large block of code
which performs a clear and distinct task (often blocks like this are good candidates to be
their own functions!).
A suggested function documentation layout would be as follows:
def my_function(argv1, argv2):
"""
High level description about the functiona and the approach you
have undertaken.
:Input:
argv1:
argv2:
:Output, return or postcondition:
:Time complexity:
:Aux space complexity:
"""
# Write your codes here.
4
1 Salesperson Revenue
(4 marks + 1 mark for documentation)
You are a travelling salesperson that sells your products in n cities (numbered 0, 1,...,n
1)
and you are trying to decide your schedule for the next d days (numbered 0, 1,...,d
1) in
order to maximize your revenue. You need to decide when it is better to sell on the city you
are located in and when it is better to move to another city.
As a super-competent salesperson, you already know how much revenue you would be able to
make on each day in each city. revenue is a list of lists. All interior lists are length n. Each
interior list represents a different day. revenue[z][x] is the revenue that you would make if
you work in city x on day z.
You also have information about travel routes. travel_days is a list of lists. travel_days[x][y]
will contain either:
• A positive integer number indicating the number of days you need to spend to travel on
the direct road from city x to city y.
• -1, to indicate that there is no direct road for you to travel from city x to city y.
At the beginning of each day z, if you are located in some city x, you have the following options:
• Spend the whole day selling in that city, making a revenue of revenue[z][x] on day z.
• Start a travel on the direct road to some city y. In this case this travel will start in city x at
the beginning of day z and will finish in city y at the end of day z+travel_days[x][y]1
(and you will not be able to do anything other than travel on the road from city x to city
y on days z,..., z + travel_days[x][y]
1).
Let start denote the city you start in on day 0.
To solve this problem, you should write a function best_revenue(revenue, travel_days,
start) that returns the maximum possible revenue.
1.1 Complexity
Your solution should have a worst-case time complexity of O (n2 (d + n)).
5
2 Saving the Multiverse
(4 marks + 1 mark for documentation)
You are Dr Weird, gifted with the power travel across the multiverse. Your archnemesis Master
X has duplicated himself and sends copies of himself across the multiverse.
Through the power of the echo, you are able to see when Master X would attack each multiverse:
• Multiverse 1, from day 2 to day 7 with a force of 5 clones.
• Multiverse 2, from day 1 to day 4 with a force of 4 clones.
• Multiverse 3, from day 6 to day 9 with a force of 2 clones.
• ... and so on.
Through masterful planning, Master X is able to coordinate his attacks and you can only be
at a single multiverse at a single moment of time. Thus, you would need to decide which
multiverse to be at to stop him; leaving the rest to each multiverse’s defenders. In the example
above, you can either:
• Defend multiverse 1 from day 2 to day 7; defeating 5 clones; or
• Defend multiverse 2 from day 1 to day 4 and then head to multiverse 3 from day 6 to day
9. In total, you would have defeated 6 clones.
Your goal is to defeat the most Master X clones you can in order to weaken him. In order to
do so, you wrote a simple Python function hero(attacks) to quickly determine the optimal
multiverse travel before Master X rules the multiverse.
PS: You can assume that you will always defeat the Master X clones. As a hero, you would
always find a way and wouldn’t need any hints.
2.1 Input
attacks is a non-empty list of N attacks, where each attack is a list of 4 items [m, s, e, c]:
• m is the multiverse which Master X is attacking.
– m is an integer in the range of 1 to N.
– Master X will only attack each multiverse once; because he do not like setbacks.
• s and e are the starting and ending days of the attack.
– s and e are integers in the range of 1 to D.
– You can assume that s <= e.
– You would need to be throughout the entire attack duration from day s to day e
inclusive in order to defeat the clones.
• c is the number of Master X clones in the attack.
– c is an integer in the range of 2 to C.
– Master X will always attack with at least 2 clones because he needs friends.
6
2.2 Output
Your algorithm returns a list of Master X attacks that you, Dr Weird, will attend to:
• Result in the most Master X clones defeated.
• The returned list doesn’t need to be sorted.
• It is possible for the return list to not be unique.
2.3 Examples
Consider the following examples below.
The first example is based on the simple example given in the question description where a
total of 6 clones were defeated.
# Example 01
attacks = [[1, 2, 7, 5], [2, 1, 4, 4], [3, 6, 9, 2]]
>>>hero(attacks)
[[3, 6, 9, 2], [2, 1, 4, 4]]
For the second example below, we observe 2 possible solutions where either [[3, 5, 6, 2], [2, 1, 4, 4]]
or [[1, 2, 7, 6]] would result in 6 clones being defeated.
# Example 02 (not unique)
attacks = [[1, 2, 7, 6], [2, 1, 4, 4], [3, 5, 6, 2]]
>>>hero(attacks)
[[3, 5, 6, 2], [2, 1, 4, 4]]
In the last example below, it can be observed that upon defeating the clones in the attack
[1, 2, 7, 6] you can only move on to attack [3, 8, 9, 5] because attack [2, 7, 9, 10] starts on day 7
itself when you are still occupied.
# Example 03 (ending condition overlap)
attacks = [[1, 2, 7, 6], [2, 7, 9, 10], [3, 8, 9, 5]]
>>>hero(attacks)
[[3, 8, 9, 5], [1, 2, 7, 6]]
2.4 Complexity
hero(attacks) should run in O(NlogN) worst case time complexity and O(N) auxiliary space
complexity, given that N is the number of attacks in attacks.
7
Warning
For all assignments in this unit, you may not use python dictionaries or sets. This is because
the complexity requirements for the assignment are all deterministic worst-case requirements,
and dictionaries/sets are based on hash tables, for which it is difficult to determine the deterministic
worst-case behaviour.
Please ensure that you carefully check the complexity of each in-built python function and
data structure that you use, as many of them make the complexities of your algorithms worse.
Common examples which cause students to lose marks are list slicing, inserting or deleting
elements in the middle or front of a list (linear time), using the in keyword to check for
membership of an iterable (linear time), or building a string using repeated concatenation
of characters. Note that use of these functions/techniques is not forbidden, however you
should exercise care when using them.
These are just a few examples, so be careful. Remember, you are responsible for the complexity
of every line of code you write!