本次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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。