COMP3506/7505 S2 2023 Assignment 2, Report Template
Due: 3pm on Friday October 13th (Week 11)
Full Name Student ID
Details
1. Overview
This document is the mandatory template which must be used to submit the report section of your second
assignment. This template is automatically synced with Gradescope to identify the location of each section of the
report; therefore, it is imperative that the overall format/layout of this document not be modified. Modification of the
template will result in a penalty being applied. You have been warned.
You are permitted to make changes inside the purple boxes for each question provided. However the overall
size of the box cannot change. Your report should easily fit within the boxes provided however please be aware
the minimum font size allowed is Arial 10pt. If you are exceeding the box size, then this may be a good indication
your response is too verbose. Please keep responses short and to-the-point.
2. Submission
Once you have completed your report this document must be exported as a pdf and uploaded to the relevant
“Assignment Two Report” area on Gradescope assignment. This document should not be uploaded to the
autograder.
3. Marking
The report will be marked by the teaching team. Information regarding the rubrics used while marking will be made
available after grades are released. While this report will indicate the relative weighting of each section of the
report, should there be any discrepancy with the official assignment specification, the assignment specification
shall take precedent.
4. Plagiarism
The University has strict policies regarding plagiarism. Penalties for engaging in unacceptable behaviour can
range from cash fines or loss of grades in a course, through to expulsion from UQ. You are required to read and
understand the policies on academic integrity and plagiarism in the course profile (Section 6.1).
The assignment specification contains more information on plagiarism. If you have any questions regarding
acceptable level of collaboration with your peers, please see either the lecturer or your tutor for guidance.
Remember that ignorance is not a defence!
5. Task
You are required to complete all sections of this report in line with the programming tasks completed in the
assignment.
The University of Queensland
Brisbane, QLD, Australia
Task 1.1: (Priority) Queue (2 marks)
1. State the concrete data structure you used to implement your priority queue. In two or
three sentences, justify why you selected this data structure.
2. Describe, in either plain language or bullet points, the algorithm used for inserting an
element e = (priority, value) to your priority queue.
3. What is the worst-case time complexity of this insertion call in terms of big-O notation?
Briefly explain. You may assume the structure contains n elements at the point of
enqueueing e.
Copyright, The University of Queensland, 2023 2
4. Directly paste either your insertion algorithm code, or a screenshot of your code here.
You need to include any helpers. We have provided two pages for you. This code must
match your submission.
Copyright, The University of Queensland, 2023 3
Continue answer 4 here if necessary.
Copyright, The University of Queensland, 2023 4
Task 1.2: Associative Map (2 marks for 3506, 3 marks for 7505)
1. State the concrete data structure you used to implement your map. In two or three
sentences, justify why you selected this data structure.
2. Describe the hash function you used for hashing nodes in order to store them in your
map. How does the algorithm work? Explain why you used this hash function with
respect to the map implementation you used. You may provide references if you used
an existing (known) hash function. If you didn’t use hashing, explain how you store
nodes, and contrast your solution to a hash-based method.
Copyright, The University of Queensland, 2023 5
3. Describe, in either plain language or bullet points, the algorithm used for locating a key
k in your map implementation.
4. What is the worst-case time complexity of this lookup in terms of big-O notation? Briefly
explain. You may assume the structure contains n elements at the point of locating k.
Copyright, The University of Queensland, 2023 6
5. Directly paste either your map lookup code, or a screenshot of your code here. You
need to include any helpers. We have provided two pages for you. This code must
match your submission.
Copyright, The University of Queensland, 2023 7
Continue answer 5 here if necessary.
Copyright, The University of Queensland, 2023 8
Task 2 and 3: Graph Algorithms (1 mark for 3506, 2 marks for 7505)
1. Which distance metric did you use for your greedy search algorithm (Task 2.2)? Is the
greedy algorithm guaranteed to visit fewer vertices than the simple DFS or BFS
algorithms? Why or why not?
2. COMP7505 [must be answered to achieve the bonus mark for COMP3506]
Briefly outline how your max_traversal algorithm (Task 2.3) works. How do you force
your algorithm to avoid the goal vertex?
\\\
Copyright, The University of Queensland, 2023 9
END OF REPORT
Copyright, The University of Queensland, 2023 10
ALIGNMENT TEST BOX
DO NOT EDIT