Written and Programming Assessment Due date: 11:55 pm AEST, Friday of Week 8 (03 May 2024)  

Weighting: 25%

Mode: Individual 

Length: Maximum 2,000 words (Assessment Report – Max. 1,500  

words, and Reflection – Max. 500 words) 

Full Mark: 100 

Objectives 

This assignment is designed to reinforce the knowledge and skills acquired in Week 5 to Week 7. It is an  individual assessment to be submitted in Week 8. The assessment task relates to Unit Learning Outcomes  1, 2 and 4, and must be done and submit individually.  

Problem Description 

Bakers Fresh, a local bakery in Brisbane, prides itself on delivering freshly baked products to its loyal  customers. As the customer base grows, planning optimal delivery routes for its trucks has become  increasingly challenging. Currently, the bakery relies on a manual process for assigning deliveries to its  drivers. This often leads to sub-optimal routes, resulting in longer delivery times that has negatively  impacted customer satisfaction. 

To address this problem, Bakers Fresh is hiring you to develop a more efficient method for planning the  delivery routes. As an example, figure 1 shows how delivery routes may be seen as paths in a graph. The  numbers on the edges denote the distances between pairs of locations.  

Figure 1. This figure is by an Unknown Author licensed under CC BY-SA-NC

Tasks 

Part 1: Modelling and Algorithm Design (25 marks) 

1. Problem Modelling (10 marks):  

o Explain how the delivery scenario can be modelled as a graph. Identify nodes and edges  and their meaning in the context of the problem. 

o Consider the choice of data structures for representing nodes and edges. Explain your  choice. If the choice of data structures is different for both uninformed and informed search  algorithms, explain the difference.  

2. Algorithm Design (15 marks):  

o Design an algorithm based on A* search to find the shortest delivery route. Include pseudo  code with comments explaining the major steps of the algorithm. 

o Briefly discuss the heuristic function that you are using in the A* search. 

o Choose an uninformed search algorithm you have come across as the candidate to compare with the A* search. Explain this uninformed search algorithm. 

Part 2: Implementation (40 marks) 

1. Python Implementation (30 marks):  

o Implement the A* search algorithm in Python using your chosen data structures.

o Implement the uninformed search algorithm in Python for comparison. 

o Ensure your code is well-documented and includes comments explaining your logic. 

2. Test Data Design (10 marks):  

o Design the test data, including at least 20 delivery locations (discounting the location of  Bakers Fresh), for the comparison.  

o Include the test data in your Python code.  

Part 3: Testing and Analysis (20 marks) 

1. Testing (10 marks):  

o Test your implemented algorithms (A* and chosen uninformed) with the designed test data.

o Capture screenshots of the test output from your Python program for both algorithms. 

2. Analysis (10 marks):  

o Compare and analyse the performance of both the A* and the uninformed search algorithm  in terms of: 

Efficiency (number of nodes explored) 

Optimality (shortest route found) 

Other relevant performance metrics you can think of 

o Discuss which of A* search and the uninformed search performs better in the specific  problem of this assignment. Why? 

Part 4: Reflection (15 marks) 

1. Reflection (15 marks):  

o Summarise your learnings from this assignment. 

o Reflect on the strengths and limitations of the implemented algorithms. 

o Propose potential improvements on either or both algorithms.  

Submission 

Each student must upload these two files via the Assignment 2 submission link on the COIT20277 HT1, 

2  

2024 Moodle assessment block by the specified due date. Late submission will incur a penalty as per the  university’s Assessment Policy and Procedure. 

1. Submit a Jupyter notebook containing your Python code, test data, and analysis with screenshots. 2. Include a separate Word document containing your written report, covering problem modelling,  algorithm design, and reflection. 

Marking Rubric (maximum 100 marks) 

Part 1: Modelling and Algorithm Design (25 marks)  

Part 2: Implementation (40 marks) 

Part 3: Testing and Analysis (20 marks)

3  

Part 4: Reflection (15 marks) 

Note: You must follow the APA 7 or the latest version for citation and referencing guidelines when writing your report. 

Academic Integrity 

Students must write the report, the reflection, and the Python program themselves. You may be asked to prove that you have written these items. You should keep evidence that you have written them yourself, for  example, early drafts of your report and the Python code. 

ALL assignments will be checked for plagiarism (materials copied from other students and/or material copied from other sources) using TurnItIn. If you are found to have plagiarised material or if you have used someone else’s words without appropriate referencing, you will be penalised for plagiarism which could result in zero (0) marks for the whole assignment. If you falsify references/information you will also be penalised. In some circumstances, a more severe penalty may be imposed such as having a plagiarism incident raised. Please refer to CQUniversity’s policy and procedure on academic integrity for details. 

Once the assessment is marked, the Unit Coordinator (or nominee) may request additional written  information and/or an oral discussion to clarify the student’s understanding of the submitted  work. Failure to comply and/or to demonstrate an understanding of the assignment’s submitted  items could result in 0 marksfor the assignment.