FIT2004 2024 Semester 1: Assignment 1

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:

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:

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).

Using the example input earlier:

• Fusing fitmons[0] with fitmons[1], will produce a fitmon with the value of [0, 108, 0.8].

• Fusing fitmons[1] with fitmons[2], will produce a fitmon with the value of [0.9, 111, 0.2].

• Fusing fitmons[2] with fitmons[3], will produce a fitmon with the value of [0.8, 74, 0].

Therefore, you implement a function called fuse(fitmons) which accepts the list fitmons and this function would fuse all of the fitmon in the list into a single ultimate final fitmon.  The resulting fitmon will have the highest possible cuteness_score from the fusing.

1.3    Output

The fuse(fitmons) function would return an integer, where it is the cuteness_score of the highest possible cutenness_score from fusing all of the fitmons – if there are N fitmonns then you would need N − 1 fuses in total.  We illustrate a simple example in the next section 1.5.

1.4    Complexity

The function fuse(fitmons) must run at the worst-case, O(N3 ) time and O(N2 ) space where N is the number of items the list fitmons.  It is possible for your solution to run better than the complexity stated here.

1.5    Example

Consider the following input list of fitmons with a total of 3 fitmon in it.

Figure 1: The 3 FITMONs from the input.

We can proceed to fuse any 2 of the fitmons in Figure 1 as long as they are next to each other. As a start, we can choose to fuse fitmons[0] with fitmons[1], creating a fitmon with the stats of [0, 108, 0.8] as illustrated below in Figure 2:

Figure 2: Fusion of fitmons[0] with fitmons[1].

Then we can fuse this new fitmon with fitmons[2], creating the final fitmon with the stats of [0, 124, 0] as illustrated below in Figure 3.

Figure 3: Fusion of fitmons[0] with fitmons[1], which is then fused with fitmons[2] after.

Alternative, the fusion can be done as illustrated in Figure 4 – where we first fuse fitmons[1] with fitmons[2] first. Then fitmons[0] is fused with the resulting fitmon. This creates the final fitmon with the stats of [0, 126, 0].

Figure 4: Fusion of fitmons[1] with fitmons[2], which is then fused with fitmons[0] after.

Putting both fusion order side by side as in Figure 5, we can see that the latter fusion order described (the one on the right) resulted in a cuter final fitmon with a cuteness_score of 126.

Figure 5: Side-by-side comparison of the fusing orders described earlier.  Left has a fusion order of ((0, 1), 2) and right has a fusion order of (0, (1, 2)).

In summary, the example above can be run using the following code snippet with the resulting returned values.

To aid your exploration, consider the following additional examples:

In the example below, the same fitmons have been swapped around while retaining their cuteness_score and affinity_score. This different order will still produce the same optimal fused fitmon with the highest cuteness_score of 126.

For the above example, there are several observations to be made.  Firstly, all of the fitmons have the same cuteness_score and the same affinity_score. Thus, the order of their fusing does not matter.

Fusing them alltogether will produce a final fitmon with a cuteness_score of 24.  This value is less than the original cuteness_score but as you need to always fuse all of the fitmons together, you have no choice but to accept a less cute final outcome.  The same can be observed with the next 2 examples below:

As for the example below, it is just an example of a larger input.  Do note that your solution would be tested against very large input sizes in the range of thousands.

It is important to note that the examples provided are not exhaustive.There are many other possible cases, with specific edge cases which you would need to validate for your solution to ensure correctness.  Thus, do ensure your solution is sufficiently tested using techniques you have learnt in prerequisite units such as unit-testing.

2    Question 2:  Delulu is not the Solulu

(10 marks, including 2 marks for documentation)

You are a bear stuck in the forest and would like to escape the forest.   Unfortunately, the forest itself is known as the Delulu Forest where it is easy to get lost. Your ancestors have left markings on various large trees in the forest to help you escape the forest, where each of the large tree will provide a road to one or more other large tree.  This is drawn onto a treemap that is given to you:

• There area total of |T| trees in the forest, from t0  all the way to t|T|−1 .

•  One of the trees would be start which is where you begin from.

•  One or more trees would be exits which is where you can exit from. These trees would be marked in the treemap given to you.

• There are |R| roads in total connecting the trees, from r0  all the way to r|R|−1 .

• You can go from tree-u to tree-v if a road r = (u,v) exist.  However, you can’t go from tree-v to tree-u unless the opposite road r′  = (v, u) also exist in the treemap.

• It takes w-minutes to travel along the road r = (u,v, w).  The travel time could differ between, and all of the time to travel along the road is stated in the treemap itself.

You then find out the reason why it is called the Delulu Forest – the exit is nothing but a delusion and even after reaching the exit tree, you are still stuck in the forest due to the seal of the forest.  However, your ancestor left a hint – certain trees are Solulu trees. You can claw at the tree to destroy that Solulu tree. Doing so will undo the seal of the forest, and then you will be able to exit the forest at an exit tree.

• There are |S| Solulu trees in the forest, from s0  all the way to s|S|−1 .

• You would require y-minutes to claw at a Solulu tree-s in order to destroy it.

•  Some Solulu trees will teleport you to another tree-t upon destruction.  This teleportation might bring you closer to, or further from your exit.

You can’t bear to be in the forest anymore and would want to escape as soon as possible.  Thus, you use your pawsome computer science knowledge of Graphs to find figure out the quickest way to exit the Delulu forest. You would model the treemap using the graph ADT as follow: