本次Java代写是完成图论相关的算法题

COMP3506/7505 Homework 4 – Graph Algorithms

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.