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.
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.
- Read the assignment specifification as soon as possible and write out a list of questions you have about it.
- Clarify these questions. You can go to a consultation, talk to your tutor, discuss the tasks with friends or ask in the forums.
- 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.
- 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?
- 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).
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
- 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
:Output, return or postcondition:
:Aux space complexity:
# Write your codes here.