” COSC 1285编程 写作、 辅导Java程序设计Algorithms and AnalysisCOSC 1285/2123Assignment 1Assessment Type Group assignment. Groups as allocated and notified on Canvas.Submit online via Canvas Assignments Assignment1. Marks awarded for meeting requirements as closely aspossible. Clarifications/updates may be made via announcements/relevantdiscussion forums.Due Date Friday 16th April 2021, 11:59pmMarks 301 OverviewOne of the frequent phrases we hear during the COVID-19 panademic are epidemicmodelling and contract tracing. As the virus is transmitted human to human, one ofthe effective methods to stop an outbreak is to identify the close contacts of an infectedindividual, and isolate all of them for a period of time (typically 14 days). To estimatethe impact of outbreaks, epidemic modelling is an extremely important tool. A graphis a natural Representation for these close contacts, tracing outbreaks and for epidemicmodelling.When we represent these networks as a graph, the vertices in such a graph representpeople and edges represents close contact relationship.In class, we studied three methods to represent the graph, the adjacency list, adjacencymatrix and vertex/edge list representations. There is a fourth type of representationcalled incident matrix (see below for details). The performance of each representationvaries depending on the characteristics of the graph. In this assignment, we will implementthe adjacency list, adjacency matrix and incident matrix representations for therelational parts, and evaluate on how well they perform when modelling close contactsand for epidemic modelling. This will assist with your understanding of the tradeoffsbetween data structure representations and its effect when implementing operations orsolving problems using algorithms and data structures.2 Learning OutcomesThis assessment Relates to all of the learning outcomes of the course which are:CLO 1: Compare, contrast, and apply the key algorithmic design paradigms: bruteforce, divide and conquer, decrease and conquer, transform and conquer, greedy,dynamic programming and iterative improvement;CLO 2: Compare, contrast, and apply key data structures: trees, lists, stacks,queues, hash tables and graph representations;CLO 3: Define, compare, analyse, and solve general algorithmic problem types:sorting, searching, graphs and geometric;CLO 4: Theoretically compare and analyse the time complexities of algorithms anddata structures; andCLO 5: Implement, empirically compare, and apply fundamental algorithms anddata structures to real-world problems.3 Background3.1 Networked SIR ModelThere are several well-known epidemic models, but the one that we will focus on inthis assignment is the (Networked) SIR model. The SIR epidemic model assumes eachindividual has three states – Susceptible (S) to the disease, Infected (I) by the disease andRecovered (R) to the disease. The progression of states is assumed to be susceptible (S)to Infected (I) to Recovered (R). Initially some in the initial population are infected andall others are susceptible. Once recovered, an individual has immunity and will not befurther infected. There are also other models, like SIS (Susceptible, Infected, Susceptible),but for the purpose of this assignment, we will stick with the most fundamental model,the SIR model, as others are really variations on this.In the traditional SIR model, there is assumption of full mixing between individuals- i.e., any individual can potentially infect another. The model then derives differentialequations that estimates the changes in the total number of susceptible, infected andrecovered individuals over time, and these are proportional to the numbers of the othertwo states – e.g., Change in number of infected individuals is dependent on the numberof susceptible and the number of recovered individuals. It is able to model some diseasesrelatively well, but is inaccurate for others and misses out on local spreading and effects.Hence a networked SIR model was proposed, where instead of full mixing between individuals,infected individuals can now only infect its neighbours in the graph/network,which typically represents some form of close contact.The networked SIR model works as follows.At each timestep, each susceptible individual can be infected by one of its infectedneighbours (doesnt matter which one, as an individual is infected regardless of whocaused it). Each infected neighbour has a chance to infect the susceptible individual.This chance is typically modelled as an infection parameter – for each chance, thereis probability of infection. In addition, at each timestep each infected individual havea chance of recovering, either naturally or from medicine and other means (this modeldoesnt care which means). Let the recovery parameter represent this, which meansthere is probability that an infected individual will recover and change to recoveredstate. There is no transition for susceptible to recovered (which could be interesting, e.g.,to model vaccination, but left for future assignments).As you can probably infer, the more neighbours one has, the higher potential forinfection. Hence one reason for the general advice from the health departments to reducethe number of close contacts. Also wearing masks reduces the infection probability, againreducing the spread of an outbreak. In this assignment, you will get an opportunity toexperiment with these parameters and see what differences they make.2For more information about SIR and epidemic modelling, have an initial read here httpss://en.wikipedia.org/wiki/Compartmental_models_in_epidemiology. We willalso release some Recordings talking more about the model on Canvas, particularly providingmore details about how to run the SIR model to simulate an epidemic, please lookat those also when they become available.3.2 Incidence Matrix RepresentationThe incidence matrix Represents a graph as a set of vertices and list of edges incident toeach vertex as a 2D array/matrix. More formally, let the incidence matrix of a undirectedgraph be an n x m matrix A with n and m are the number of vertices and edges of thegraph respectively. The values in the matrix A follows the following rules:Each edge ek is represented by a column in A.Each vertex is represented by a row in A.Let the two incident vertices to an edge ek be vi and vj. Then the matrix entriesAi,k and Aj,k are both = 1.Ai,k = 0 for all other non-incident edges.For example, the following graph:has its incidence matrix as below:AB AC AD BC CDA 1 1 1 0 0B 1 0 0 1 0C 0 1 0 1 1D 0 0 1 0 1For further readings about this graph representation, please see httpss://en.wikipedia.org/wiki/Incidence_matrix.4 Assignment DetailsThe assignment is broken up into a number of tasks, to help you progressively completethe project.3Task A: Implement the Graph Representations, their Operationsand the Networked SIR model (10 marks)In this task, you will implement data structures for representing undirected, unweightedgraphs using the adjacency list, adjacency matrix and incidence matrix representations.Your implementation Should also model vertices that have SIR model states associatedwith them. Your implementation should support the following operations:Create an empty undirected graph (implemented as a constructor that takes zeroarguments).Add a vertex to the graph.Add an edge to the graph.Toggle the SIR state on vertices.Delete a vertex from the graph.Delete an edge from the graph.Compute the k hop neighbours of a vertex in the graph.Print out the set of vertices and their SIR states.Print out the set of edges.In addition, we want you to implement the (networked) SIR epidemic model to simulatehow a virus can spread through a population.Note that you are welcome to implement additional functionality. When constructingour solutions to the assignment, we have found that adding some methods was helpful,particularly for implementing the SIR model. But the above functionalities are ones youshould complete and ones you will be assessed on.Data Structure DetailsGraphs can be implemented using a number of data structures. You are to implementthe graph abstract data type using the following data structures:Adjacency list, using an array of linked lists.Adjacency matrix, using a 2D array (an array of arrays).Incidence matrix, using a 2D array (an array of arrays).4For the above data structures, you must program your own implementation, and notuse the LinkedList or Matrix type of data structures in java.utils or any other libraries.You must implement your own nodes and methods to handle the operations. If you usejava.utils or other implementation from libraries, this will be considered as an invalidimplementation and attract 0 marks for that data structure. The only exceptions are:if you choose to implement a Map of vertex labels to a row or column index for theadjacency matrix or incidence matrix, you may use one of the existing Map classesto do this.if you choose to implement a map of vertex labels to its associated SIR state, youmay use of the existing Map classes to do so.Operations DetailsOperations to perform on the implemented graph abstract data type are specified on thecommand line. They are in the following format:operation [arguments]where operation is one of {AV, AE, TV, DV, KN, PV, PE, SIR, Q} and arguments is foroptional arguments of some of the operations. The operations take the following form:AV vertLabel add a vertex with label vertLabel into the graph. Has defaultSIR state of susceptible (S).AE srcLabel tarLabel add an edge with source vertex srcLabel, targetvertex tarLabel into the graph.TV vertLabel toggle the SIR state of vertex vertLabel. Togglng means go tothe next state, i.e., from S to I, from I to R (if in R, remain in R).DV vertLabel delete vertex vertLabel from the graph.DE srcLabel tarLabel remove edge with source vertex srcLabel and targetvertex tarLabel from the graph.KN k vertLabel Return the set of all neighbours for vertex vertLabel thatare up to k-hops away. The ordering of the neighbours does not matter. See belowfor the required format.PV prints the vertex set of the graph. See below for the required format. Thevertices can be printed in any order.PE prints the edge set of the graph. See below for the required format. The edgescan be printed in any order.SIR infected seed vertices, delimited by ; infection probability recoverprobability Run the networked SIR model simulation, using the current graphas the network, the specified seed vertices as additional set of infected vertices (inaddition to any existing in the Current graph) and the two infection and recover5probabilities. Runs the model simulation to completion, which means two thingsa) there are no more vertices with Infected (I) state and there are no changes in thenumber of infected or recovered in the latest iteration of the model; or b) if conditionthere are still infected vertices but there has been no changes in the number ofinfected or recovered for 10 iterations, then can stop the simulation. Outputs thelist of nodes infected at each iteration, see below for format.Q quits the program.k-hop Neighbour operation format details The format of the output of the neighbouroperation for vertex A should take the form:A: neighbour1 neighbour2 …If a vertex has no neighbours, then the list of neighbours should be empty. The nodeA should not be in the list of neighbours, and the graphs can be assumed to have noself-loops (self loops dont necessarily make sense for epidemic modelling).Print vertex operation format details The print vertex operation output the verticesand associated SIR state in the graph in a single line. The line should specifies allthe valid vertex (indices) in the graph.(vertex1,state1) (vertex2,state2) (vertex3,state3) …where state1 is the SIR state of vertex 1 etc.Print edge operation format details The print edge operation output the edges inthe graph in over a number of lines. Each line specifies an edge in the graph, and shouldbe in the following format:srcVertex tarVertexSIR operation format details The networked SIR model file output format is eachline represents one iteration of the Process, and each line will record the number of newlyinfected and recovered vertices (newly infected or recovered nodes are ones that becomeinfected or recovered in this iteration). The format is as follows:iteration number : [space separated, list of newly infectedvertices] : [space separated, list of newly recovered vertices]Example of all operations As an example of the operations, consider the outputfrom the following list of operations:The output from the four neighbour operations (KN 1 A, KN 2 A KN 1 F, KN 1H) should be (remember that the order these neighbourhoods do not matter so if youroutput differs from this ordering but has the same set of vertices, that is fine):A: B E FA: B C D F E GF: A B GH:The output from the print vertices operation (PV) could be (remember that the orderdoesnt matter):(A, S ) (B,R) (D, S ) (E, I ) (F, S ) (G, S ) (H, S )The output from the print edges operation (P E) could be (remember that the orderdoesnt matter):The output from the SIR A;F 0.8 0.5 operation could be (note that it is a stochasticmodel, so you can get different results for different runs, so use the following more forwhat the output format should look like):1 : [G] : [ ]2 : [ ] : [A]3 : [ ] : [ ]4 : [ ] : [ ]5 : [ ] : [ F G]6 : [ ] : [ ]Testing FrameworkWe provide Java skeleton code (see Table 1 for the important files) to help you getstarted and automate the correctness testing. You may add your own Java files to yourfinal submission, but please ensure that they compile and can be run on the core teachingservers.NotesConsider the specifications here carefully. If you correctly implement the Implementme! parts and follow the output formating for operations like PV, PE andSIR, you in fact do not need to do anything else to get the correct output formatting.The main class in the provided skeleton code will handle this.The implementation details are up to you, but you must implement your own datastructures and algorithms, i.e., do not use the built-in structures in Java unless forthe purposes outlined in the box above.If you develop on your own machines, please ensure your code compiles and runson the universitys core Teaching servers. You dont want to find out last minutethat your code doesnt compile on these machines. If your code doesnt run onthese machines, we unfortunately do not have the resources to debug each one andcannot award marks for testing. All submissions should compile with no warnings on Oracle Java 1.8 – this is theversion on the core teaching servers. Any clarifications on the Canvas FAQ or Assignment 1 Update page will overridethe specifications here if they are conflicting.8file descriptionRmitCovidModelling.java Main class. Contains code that reads in operation commandsfrom stdin then executes those on the selected graph implementation.Also will format the output as required. No needto modify this file.ContactsGraph.java Interface class for the graph representations. It contains thecommon interface/methods that youll need to implement forthe various representations. Generally no need to modify thisfile, but you might want to add helper functionality, and herewould be one place to do so for common ones across all representations..AdjacencyList.java Code that implements the adjacency list implementation ofa graph. Complete the implementation (implement parts labelledImplement me!).AdjacencyMatrix.java Code that implements the adjacency matrix implementationof a graph. Complete the implementation (implement partslabelled Implement me!).IncidenceMatrix.java Code that implements the incidence matrix implementationof a graph. Complete the implementation (implement partslabelled Implement me!).SIRState.java Code that Implements the three vertex states of a SIR model.No need to modify this file.SIRModel.java Code that implements the networked SIR model. Completethe implementation (implement parts labelled Implementme!).Table 1: Table of Java files.Task B: Evaluate your Data Structures and SIR model (20 marks)In this second task, you will evaluate your implemented structures in terms of their timecomplexities for the different operations and different use case scenarios. Scenarios arisefrom the possible use cases of contract tracing and epidemic modelling on a graph. Inaddition, run some epidemic modelling simulations to evaluate your structures within anapplication (epidemic modelling and simulation) and to explore more about the effect ofthe model parameters on epidemic spreading.Write a report on your analysis and evaluation of the different implementations. Considerand recommend in which scenarios each type of implementation would be mostappropriate. Report the outcomes of your SIR epidemic model simulations. The reportshould be 10 pages or less, in font size 12. See the assessment rubric (Appendix A) forthe criteria we are seeking in the report.9Graph generatorsTo evaluate the data structures, we will generate a number of graphs, then apply anumber of operations on them, see the Use Case Scenarios section next. In this section,we describe more about how to generate the graphs, and see on Canvas for further detailsand videos.There are many ways to generate graphs, but we will focus on two:Random (Erdos-Renyi) there is a probability for generating an edge between anypair of vertices.Scale-free graphs whose degree distribution follow a power law (see httpss://en.wikipedia.org/wiki/Scale-free_network).We suggest to use Pajek1, which is available on multiple platforms and has visualisation,which allows one to look at the Generated graphs. But it also has basic graphgeneration functionality and doesnt require programming to use, unlike more powerfulgraph libraries2.Use Case ScenariosTypically, you use real usage data to evaluate your data structures. However, for this assignment,you will write data generators to enable testing over different scenarios ofinterest. We are also interested in the effect of the average degree of the graph3 on thesescenarios. There are many possibilities, but for this assignment, consider the followingscenarios:Scenario 1 k-hop Neighbourhoods: When doing contract tracing and/or epidemicmodelling, computing neighbourhoods is an important function. In this scenario, thegraph is not changing, but important operations such as k-hop neighbourhood (recallthis is all neighbours up to k-hops away) are requested.You are to evaluate the performance of the the k-hop neighbourhood implementations,as the average degree of the evaluated graph and k are varied.Scenario 2 Dynamic Contact Conditions: In the real world, the contact conditionsbetween people are likely not static and there will be need to update these over time. Inthis scenario, the contacts are changing (been added and deleted). In this scenario, youare to evaluate the performance of your implementations in terms of:edge additionsedge deletionsYou are to evaluate the performance the edge operations as the average degree andsize (number of vertices) of the initial graph (before edge changes) are varied.1 https://mrvar.fdv.uni-lj.si/pajek/ the website looks a bit dated, but this is one of the wellknown social network analysis tools.2Networkx httpss://networkx.org/ if you know Python, you are more than welcome to use thisinstead.3Average number of neighbours per node, which both graph generator models allows to be specified10Scenario 3 Dynamic People Tracing: As time goes on, the people been traced willchange. Although it is possible to have a large graph that tries to capture every possibleperson, it is computationally Difficult to do so and run simulations on it. In this scenario,you are to evaluate the performance of your implementations in terms of:vertex additionvertex deletionYou are to evaluate the performance the vertex operations as the average degree and size(number of vertices) of the initial graph (before vertex changes) are varied.SIR Model Epidemic SimulationIn addition to evaluating how well the graph representations perform for the contracttracing and epidemic modelling simulations, we also want to experiment with how thenetworked SIR model works and performs.Run epidemic simulation for different graph types (Erdos-Renyi and Scale-free), differentseed initialisations and different infection and recover probabilities. For performanceevaluation, evaluate each of the three data structures on a subset of the possible simulationparameters and compare how they perform (in terms of timing efficiency).We dont expect a comprehensive analysis, but want you to explore and gain a betterunderstanding of epidemic modelling and what it implies for how to limit the spread ofepidemics.Consider how you might present the results, but at a minimum plot the following:Number of susceptible, infected and recovered after every iteration.Data GenerationWhen generating the vertices and edges to add or remove and find neighbourhoods for,the distribution of these elements, compared to what is in the graph already, will havean effect on the timing performance. However, without the usage and query data, it isdifficult to specify what this distributions might be. Instead, in this assignment, uniformlysample from a fixed range, e.g., 0 to max vertex label of your graph when generating thevertices and edges for removing and adding and k-hop neighbourhoods, and a differentrange (e.g., greater than the largest vertex label when adding vertices (we do not wantto repeatingly add vertices that are in the graph already).For generating graphs with different initial average degrees and sizes, you can eitheruse Pajek or your favourite graph generator, we will not prescribe one particular approach.Whichever method you decide to use, remember to generate graphs of different averagedegrees to evaluate on. Due to the randomness of the data, you may wish to generate afew graphs with the same average degrees and sizes and take the average across a numberof runs when performing the performance evaluation and analysis.AnalysisIn your analysis, you should evaluate each of your representations and data structures interms of the different scenarios outlined above.Note, you may be generating and evaluating a significant number of graphs and evaluationdatasets, hence we advise you To get started on this part relatively early.115 Report StructureAs a guide, the report could contain the following sections:Explain your data and experimental setup. Things to include are (brief) explanationsof the data scenarios you decide to evaluate on (e.g., how many additions/removalsoperations did you evaluate and why these), size of the graphs, the range ofaverage degrees tested (add some brief explanation of why this range selection), describehow the scenarios were generated (a paragraph and perhaps a figure or highlevel pseudo code suffice), which approach(es) you decide to use for measuring thetiming results, and briefly describe the fixed set(s) you sampled from to generatethe elements for addition, removal of vertices and edges and k-hop neighbourhoodof the graphs.Evaluation of the data structures using the generated data (different scenarios,average degree, graph size). Analyse, compare and discuss your results. Provideyour explanation on why you think the results are as you observed. You mayconsider using the known theoretical time complexities of the operations of eachdata structure to help in your explanation if useful.Summarise your analysis as recommendations, e.g., for this certain data scenarioof this average degree (and size), I recommend to use this data structure because…We suggest you refer to your previous analysis to help.Evaluate the different parameters of the SIR model and its effect on the numberof susceptible, infected and recovered individuals over time. Which combinationof parameters has the fastest infection spread, which one has the most extensivenumber of infected? How does the average timing compare between your threegraph representation? Can you explain why?6 SubmissionThe final submission will consist of three parts:Your Java source code of your implementations. Include only source codeand no class files, we will compile your code on the core teaching serers. Makesure that your assignment can run only with the code included! That is, it shouldbe self contained, including All the skeleton code needed to run it.Your source code should be placed into in a flat structure, i.e., all the files shouldbe in the same directory/folder, and that directory/folder should be named asAssign1-your student number. Specifically, if your student number is s12345,when unzip Assign1-s12345.zip is executed then all the source code files shouldbe in directory Assign1-s12345.Your data generation code. Create a sub-directory/sub-folder called generationwithin the Java source file directory/folder. Place your generation codewithin that folder. We will not run the code, but may examine their contents.Your written report for part B in PDF format, called assign1.pdf. Submitthis separately to a Turnitin submission.12Note: submission of the report and code will be done via Canvas. We willprovide details closer to the submission deadline. We will also provide details on howthe setup we use to test the correctness of your code will be like, so you can ensure yoursubmitted structure will conform to the automated testing we will perform.7 AssessmentThe project will be marked out of 30. Late submissions will incur a deduction of 3 marksper day, and no submissions will be accepted 5 days beyond the due date and will attract0 marks for the assignment.The assessment in this project will be broken down into two parts. The followingcriteria will be considered when allocating marks.Implementation (10/30):You implementation will be assessed based on the number of tests it passes in ourautomated testing.While the emphasis of this project is not programming, we would like you to maintaindecent coding design, readability and commenting, hence commenting andcoding style will make up a portion of your marks.Report (20/30):The marking sheet in Appendix A outlines the criteria that will be used to guide themarking of your evaluation Report4. Use the criteria and the suggested report structure(Section 5) to inform you of how to write the report.8 Team StructureThis project should be done in pairs (group of two). If you have difficulty in finding apartner, post on the discussion forum or contact your lecturer. If you want to do theassignment individually, please contact one of your lecturers first and obtain hisapproval.In addition, please submit what percentage each partner made to the assignment (acontribution sheet will be made available for you to fill in), and submit this sheet in yoursubmission. The contributions of your group should add up to 100%. If the contributionpercentages are not 50-50, the partner with less than 50% will have their marks reduced.Let student A has contribution X%, and student B has contribution Y%, and X Y .The group is given a group mark of M. Student A will get M for assignment 1, but studentB will get MXY.This semester we will also institute some additional group management initiatives,including registration and not allowing further group changes in the week before the duedate. We will detail more about this on Canvas.4Note for the marking guide, if one of the criteria is not demonstrated a tall, then 0 marks will be”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
