COMP3506/7505 Homework 4 – Graph Algorithms
Weighting: 15%
Due date: 23rd Oct 2020, 11:55 pm
Overview
The purpose of this assignment is to gain practice converting worded scenario problems into graph problems,
implementing graph data structures, and implementing various graph algorithms to solve such graph problems.
Marks
This assignment is worth 15% of your total grade. Both COMP3506 and COMP7505 students will be marked on
questions 1 to 3 out of 30 marks.
Submission Instructions
• Your solutions to Q1, Q2 and Q3 will be submitted via Gradescope to the Homework 4 submission. You
should only submit the following Java files:
– ErdosNumbers.java
– FactChecker.java
– ContactTracer.java
• No other submitted files will be marked.
• ZIP files (or other compressed file formats) won’t be marked - you should only submit the relevant Java files
to Gradescope.
• No marks will be awarded for non-compiling submissions, or submissions which import non-supported 3rd
party libraries. If one of your files isn’t compiling, then it will cause you to receive 0 for the entire assignment.
If you can’t manage to get a class compiling, don’t submit that broken file.
• You should follow all constraints laid out in the relevant questions and in the next section.
Late Submissions and Extensions
Late submissions will not be marked. It is your responsibility to ensure you have submitted your work well in
advance of the deadline (taking into account the possibility of internet or Gradescope issues). Only the latest
submission before the deadline will be marked. See the ECP for information about extensions.
Academic Misconduct
This assignment is an individual assignment. Posting questions or copying answers from the internet is considered
cheating, as is sharing your answers with classmates. All your work (including code) will be analysed by
sophisticated plagiarism detection software. Students are reminded of the University’s policy on student misconduct,
including plagiarism. See the course profile and the School web page: http://www.itee.uq.edu.au/
itee-student-misconduct-including-plagiarism.
1
Support Files Provided
The following provided support files have been provided to you:
• ErdosNumbers.java - You will implement question 1 in this file and submit it.
• Fact.java - A support file for question 2. Do not modify or submit this file.
• FactChecker.java - You will implement question 2 in this file and submit it.
• Trace.java - A support file for question 3. Do not modify or submit this file.
• ContactTracer.java - You will implement question 3 in this file and submit it.
Notes and Constraints
• You may use code (or implement the pseudocode) provided in lecture slides and tutorials.
• Your solution will be automatically marked using Java 11.
• You may use anything from the Java standard library (unless otherwise stated in the question).
• You may add private helper methods and inner classes.
• You should not create additional files in your solution - these won’t be marked.
• Do not modify any of the provided method or class signatures. In particular, do not add a package declaration.
Doing so will mean receiving a mark of 0 for your submission as it won’t work with the automated tests.
• Do not add static variables to any classes.
• Sample tests have been provided. However, these are far from exhaustive and your actual submissions will be
marked on a much larger set of test cases. You should write your own tests while working on your assignment.
• You may be penalised for bad code style and formatting, or inefficient algorithm implementations.
2
Questions
1. (10 marks) The famous Hungarian mathematician Paul Erd˝os was particularly renowned for his social practice
of mathematics, in which he engaged with more than 500 different collaborators on research papers. His
collaboration was so prolific in the mathematics community that it prompted the creation of the “Erd˝os
number”, which describes the “collaborative distance” between Paul Erd˝os and another person.
The calculation of Erd˝os numbers can be aided through the construction of a graph, where each node or
vertex represents a distinct person, and edges between persons indicate a paper co-authorship. The length of
the shortest path between a person and Paul Erd˝os is that person’s Erd˝os number.
For this question, you will implement the following parts in the class ErdosNumbers.java.
(a) Implement the constructor for ErdosNumbers, which takes as input a list of papers for use in the subsequent
parts. In addition, implement
• The method getPapers, which returns the set of papers an author has written.
• The method getCollaborators, which returns the set of unique co-authors an author has written
a paper with before.
(b) In isErdosConnectedToAll, implement an efficient algorithm to determine if every author has an Erd˝os
number. Consult the Javadoc for more specific details.
(c) In calculateErdosNumber, implement an efficient algorithm to determine the Erd˝os number of a given
author. Consult the Javadoc for more specific details.
(d) In averageErdosNumber, implement the code to determine the average Erd˝os number of all the co-authors
on a given paper.
(e) Multiple variants of the Erd˝os number exist that consider more information about co-authorships. One
variant, which we will call here the “weighted Erd˝os number”, weights each edge in the graph between
two authors a and b as w(a, b) = 1
c(a,b)
, where c(a, b) is the number of papers the two authors have
published together.
Then, the “weighted Erd˝os number” is the shortest weighted path between a person and Erd˝os in this
graph - and will hence be a real number instead of an integer.
In calculateWeightedErdosNumber, implement an efficient algorithm to calculate the weighted Erd˝os
number of a given author. Consult the Javadoc for more specific details.
Notes and Hints:
• A constant has been defined in ErdosNumbers.java for you to test against for Erd˝os’s name in the
datasets.
• Authors and papers have unique names (e.g. you can consider authors with the exact same name to be
the exact same author).
• It may make more sense to do some pre-processing in your constructor in order to make other methods
more efficient (as they may be called multiple times).
3
2. (10 marks) Over the mid-semester break, Kristian spent an entire day baking some delicious triple chocolate
chip cookies. He then hid them in his cupboard so no one would eat them during a (COVIDSafeTM) party he
was hosting later that night for the other tutors. It was a great night with many people (all 1.5 meters apart
from each other) coming and going throughout.
Later that week, he went to his secret stash of delicious cookies that would help him get through a COMP3506
marking filled night. However, to his dismay and shock, they were all gone! Only crumbs were left at the scene
of the crime. Immediately, he interrogated the other tutors who attended the party to attempt to narrow
down the potential suspects.
After interviewing them, he collated a bunch of information about the attendees at the party. Each fact he
collected was of the following type:
• Type I: Person Pa left the party before person Pb arrived.
• Type II: Person Pa and Pb were both at the party at the same time at some point.
for persons Pa and Pb at the party.
Before he investigates further, Kristian first needs to figure out if the facts he’s collected are “consistent” -
that is, can they all be true at the same time... or is someone lying?
The number of facts he has collected makes this task too difficult to do manually. However, he luckily
knows some COMP3506 students who he thinks will be able to devise an algorithm to determine this task
automatically for him!
For this task, you will need to implement areFactsConsistent in FactChecker.java, which will take as
input a list of such facts, and returns true if they are all internally consistent (or otherwise false).
Your algorithm should run in worst case O(|P| + |F|) time, where |P| is the number of people who were at
the party, and |F| is the number of facts to process.
(Hint: Can you make a graph out of the information you are given?).
4
3. (10 marks) The year is 3506 and a very contagious new virus, named COMP-3506, is spreading rapidly.
Queensland Health has finally decided to invest in some new advanced computer programs for contact tracing,
as the current ones haven’t been upgraded since the last pandemic, COVID-19.
Currently, they have a database storing a list of person-to-person contact traces of the form of a tuple
(Pi
, Pj , tk), where Pi and Pi and Pj are the two people involved in the interaction that happened at time tk.
Note that traced interactions are directionless, as in the trace (A, B, tk) is the same as the trace (B, A, tk).
They have hired you to improve their algorithms for contact tracing by extending this current system into
ContactTracer.java.
Note that it would be wise to understand the entire question before attempting to do the individual parts (as
your design decisions may change).
(a) Implement the constructors for ContractTracer, which takes as input a list of check-ins of the form
described above. Additionally, implement addTrace which adds a new contact trace datum to the
internal data structure.
(b) Implement getContactTimes, which returns a list of times that two people have been in direct contact
in the tracing data. This list should be returned in ascending order of time.
(c) Implement the getContacts and getContactsAfter methods, which take as input a person and then
return the set of people that person has come into direct contact with in the tracing data. For the
getContactsAfter method, it only returns contacts that have happened at or after the given timestamp.
(d) Now that we have a data structure which can help us store and query the tracing information, we want
to implement an algorithm to help find potential infectees from a given source.
That is, given a person P who become contagious with COMP-3506 at exactly time t, we want to find all
the people who now may have contracted COMP-3506 from person P (and therefore need to be contacted
for testing and tracing), or may have contracted it from someone else who P has infected (and so on...).
For this question, we will assume the following:
• If a person comes into contact with COMP-3506 at time t and they do not have it already, they
might contract the virus and become contagious at exactly t + 60 minutes.
• If a person is contagious with COMP-3506 at time t, then they may instantly spread it to anybody
they come into contact with at or after time t.
In contactTrace, implement an efficient algorithm that takes a person P, who became contagious with
COMP-3506 at time t, and return the set of all other people in the dataset who may now have contracted
COMP-3506 under the above assumptions.
Small example: For example, suppose your contact tracing database has the following information
(note: this is not necessarily how you may choose to store this information but just a representation of
it).
Person 1 Person 2 Time
Anna Sanni 1st October 3PM
Anna Matt 2nd October 8PM
Matt Kristian 3rd October 9PM
Kristian Sanni 3rd October 9:30PM
Kristian Kenton 3rd October 11PM
Kristian Max 3rd October 11PM
Kenton Kristian 4th October 10AM
Table 1: Representation of example database
If Anna become contagious with COMP-3506 at 1st October 3:30PM, then Matt, Kristian, Kenton, and
Max would need to be contacted for tracing due to possible transmission.