Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Learning Outcomes
This assignment achieves the Learning Outcomes of:
• Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;
• Prove correctness of programs, analyse their space and time complexities;
• Compare and contrast various abstract data types and use them appropriately;
• 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 specifications 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
1. Read the assignment specification as soon as possible and write out a list of questions you have about it.
2. Try to resolve these questions by viewing the FAQ on Ed, or by thinking through the problems overtime.
3. 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.
4. 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.
5. Write down a high-level description of the algorithm you will use.
6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.
Implementing
1. 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.
2. Code up your algorithm (remember decomposition and comments), and test it on the tests you have thought of.
3. 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 different?
• etc...
Before submission
• Make sure that the input/output format of your code matches the specification.
• Make sure your filenames match the specification.
• Make sure your functions are named correctly and take the correct inputs.
• Remove print statements and test code from the file you are going to submit.
Documentation
For this assignment (and all assignments in this unit) you are required to document and com- ment 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 might result in you getting 0 for the entire question for which it is insufficient.
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: :Time complexity analysis: :Space complexity: :Space complexity analysis: """ # 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 Question 1: Ultimate Fuse
(10 marks, including 2 marks for documentation)
You are an adventurer in FITWORLD – a magical world where humans and FITMONs live in harmony. FITMONs are insanely cute creatures which make everyone around them happy. Each FITMON has a cuteness_score where a higher score means a cuter FITMON.
Recently, it was discovered that it is possible to fuse FITMONs together. The fusing process could increase or decrease the cuteness_score of the resulting FITMON. Thus, you set out to fuse FITMONs together, to create the very cutest FITMON possible, that no FITMON ever was. In order to do so, you head over to a FITMON Center.
1.1 Input
You have a list of fitmons:
• Contains N fitmon in the list [0...N − 1]. N isanon-zero, positive integer where N > 1.
• Each fitmon is identified by their index in the fitmons list.
• Each fitmon in the list is a list of 3 values
[affinity_left, cuteness_score, affinity_right] .
• affinity_left is a positive float in the range of 0.1...0.9 inclusive. Only the left-most fitmons[0] will have an affinity_left of 0 as there isno fitmon on the left for it to fuse.
• affinity_right is a positive float in the range of 0.1...0.9 inclusive. Only the right-most fitmons[N-1] will have an affinity_right of 0 as there isno fitmon on the right for it to fuse.
• cuteness_score is anon-zero, positive integer.
An example of the input list fitmons is illustrated below:
fitmons = [ [0, 29, 0.9], [0.9, 91, 0.8], [0.8, 48, 0.2], [0.2, 322, 0] ] |
In this input, fitmons[1] has a:
• affinity_left of 0.9.
• cuteness_score of 91.
• affinity_right of 0.8.
1.2 Fusing Logic
From the fitmons list, you realize that each fitmon can only fuse with the adjacent fitmon in the adjacent fitmon. Your goalis to fuse all of the given fitmons into only 1 fitmon. Thus:
• fitmons[i] can only fuse with either fitmons[i-1] or fitmons[i+1].
• The affinity for the 2 fusing fitmons are the same as illustrated in the example input. We see that fitmons[i][0] would have the same value as fitmons[i-1][2] and similarly fitmons[i][2] would have the same value as fitmons[i+1][0].
• However, fitmons[0] can only fuse with fitmons[1] as there isno fitmon on its left.
• Likewise, fitmons[N-1] can only fuse with fitmons[N-2] as there isno fitmons on its right.
• Once a fitmon is fused, it no longer exist and thus cannot be used for fusing again.
When 2 fitmons fuse, their cuteness changes based on their cuteness_score and the affinity of the fuse. Fusing fitmons[i] with fitmons[i+1] will create a new fitmon with:
• The affinity_left will be based on the affinity_left of the left fitmon, affinity_left = fitmons[i][0]
• The cuteness_score is computed using the affinity_score of the fusing fitmons mul- tiplied with their cuteness_score based on the following equation,
cuteness_score = fitmons[i][1] * fitmons[i][2] +
fitmons[i+1][1] * fitmons[i+1][0]
• The affinity_right will be based on the affinity_right of the right fitmon, affinity_right = fitmons[i+1][2]
• Note: as the cuteness_score is an integer, you can use int() on it after each and every fuse; before the next fuse (if any).