Learning Outcomes
This assignment achieves the Learning Outcomes of:
1) Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;
2) Prove correctness of programs, analyse their space and time complexities;
3) Compare and contrast various abstract data types and use them appropriately;
4) Develop and implement algorithms to solve computational problems.
In addition, you will develop the following employability skills:
Text comprehension.
Designing test cases.
Ability to follow specififications precisely.
Assignment timeline
In order to be successful in this assessment, the following steps are provided as a suggestion.
This is an approach which will be useful to you both in future units, and in industry.
Planning
Read the assignment specifification as soon as possible and write out a list of questions you have about it.
Try to resolve these questions by viewing the FAQ on Ed, or by thinking through the problems over time.
As soon as possible, start thinking about the problems in the assignment.
It is strongly recommended that you do not write code until you have a solid feeling for how the problem works and how you will solve it.
Writing down small examples and solving them by hand is an excellent tool for coming to a better understanding of the problem.
As you are doing this, you will also get a feel for the kinds of edge cases your code will have to deal with.
Write down a high-level description of the algorithm you will use.
Determine the complexity of your algorithm idea, ensuring it meets the requirements.
Implementing
Think of test cases that you can use to check if your algorithm works.
Use the edge cases you found during the previous phase to inspire your test cases.
It is also a good idea to generate large random test cases.
Sharing test cases is allowed, as it is not helping solve the assignment.
Code up your algorithm (remember decomposition and comments), and test it on the tests you have thought of.
Try to break your code. Think of what kinds of inputs you could be presented with which your code might not be able to handle.
Large inputs
Small inputs
Inputs with strange properties
What if everything is the same?
What if everything is difffferent?
etc…
Before submission
Make sure that the input/output format of your code matches the specifification.
Make sure your fifilenames match the specifification.
Make sure your functions are named correctly and take the correct inputs.
Make sure you zip your fifiles correctly (if required).
Documentation
For this assignment (and all assignments in this unit) you are required to document and comment your code appropriately. Whilst part of the marks of each question are for documentation,there is a baseline level of documentation you must have in order for your code to receive marks.
In other words:
INSUFFICIENT DOCUMENTATION MEANS YOU GET 0 FOR THE ENTIRE ASSIGNMENT
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.
Your main function in the assignment should contain a generalised description of the approach your solution uses to solve the assignment task.
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 appropriate Big-O or Big-Θ 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):
“””
Function description:
Approach description (if main function):
:Input:
argv1:
argv2:
:Output, return or postcondition:
:Time complexity:
:Aux space complexity:
“””
# Write your codes here.
There is a documentation guide available on Moodle in the Assignment section, which contains a demonstration of how to document code to the level required in the unit.
1 Should I give a ride? (10 marks)
As a smart student you are always trying to optimise the driving time to your early morning algorithms lectures so that you can sleep more. You will be leveraging your algorithms skills to get an optimal solution.
Some of the roads in your city have carpool lanes that can only be used if there are at least 2 persons in the car, so you have to decide if you will be giving a ride to a fellow student or not.
You have access to precise travel time information among key locations in your city, both with single car occupancy and with 2 or more persons in the car. And you have a list of locations in which there are students looking for a ride to the same destination you are going. You can assume that the potential passengers are always on time at the agreed location and there will be no additional time incurred for getting them into the car. You will either pickup passenger(s) with the same destination as you, or go alone the whole trip. Your absolute priority during those very early morning hours is maximising your sleeping time, so you are looking for the shortest total driving time and will not give a ride if that increases the total driving time.