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)
Criteria
Excellent
(100%)
Good (70%)
Satisfactory
(40%)
Unsatisfactory
(10%)
Problem
Modelling (5
marks)
Clear and
accurate
Mostly clear
Some clarity
issues
Unclear or
inaccurate
Data Structure
Justification (5
marks)
Well-explained
and appropriate
Explained, but
minor issues
Briefly
explained
Not explained
A* Search
Algorithm
Design (5
marks)
Clear, well
commented, and
correct
Mostly clear
and correct
Some errors
or missing
information
Unclear or
incorrect
Heuristic
Function
Explanation (5
marks)
Clear
explanation of
purpose and
choice
Basic
understanding
Limited
understanding
No explanation
Uninformed
Search
Algorithm
Choice (5
marks)
Justified and
relevant to
comparison
Mentioned but
not justified
Not chosen or
irrelevant
Not mentioned
Part 2: Implementation (40 marks)
Criteria
Excellent (100%)
Good (70%)
Satisfactory
(40%)
Unsatisfactory (10%)
A* Search
Implementation (20 marks)
Correct, well
documented, and
efficient
Mostly correct and documented
Some errors or inefficiency
Incorrect or
incomplete
Uninformed Search Implementation (10 marks)
Correct and
documented
Mostly correct
Some errors
Incorrect or
incomplete
Test Data Design
(10 marks)
Clear, well-structured, and relevant
Mostly clear and relevant
Missing clarity or relevance
Unclear or
irrelevant
Part 3: Testing and Analysis (20 marks)
Criteria
Excellent (100%)
Good (70%)
Satisfactory
(40%)
Unsatisfactory (10%)
Testing Completion (10 marks)
Both A* and
uninformed search
algorithms are tested with the designed test data, and screenshots of
Both algorithms are tested, but
only screenshots for one algorithm are provided, or
Only one
algorithm is
tested, or the
provided
screenshots are
No testing is
conducted, or the provided
information is
not related to
3
final output (e.g.,
console output or
visualizations) are
captured for both
algorithms.
the provided
screenshots are
incomplete.
irrelevant to the task.
testing.
Analysis (10 marks)
The analysis clearly compares and contrasts the performance of A* and the uninformed search algorithm in
terms of efficiency
(number of nodes
explored) and
optimality (shortest route found).
The analysis
attempts to
compare the
performance of
both algorithms, but it might lack detailed
explanation or
may contain minor errors.
The analysis
attempts to
compare the
performance, but it lacks
crucial aspects like efficiency or optimality
comparison.
The analysis is missing or
irrelevant to
comparing the
algorithms or
explaining A*’s advantage.
Part 4: Reflection (15 marks)
Criteria
Excellent (100%)
Good (70%)
Satisfactory
(40%)
Unsatisfactory (10%)
Reflection
The reflection paper effectively summarizes the student’s learnings from the assignment.
The reflection
paper covers the key aspects
mentioned above, but it might lack depth or detail in some areas.
The reflection paper attempts to address the required points but might be
incomplete or lack clarity.
The reflection
paper is missing crucial aspects or is not relevant to the task.