Reference no: EM132863894

COSC 1285 Algorithms and Analysis - RMIT University

Learning Outcome 1: Compare, contrast, and apply the key algorithmic design paradigms: brute force, divide and conquer, decrease and conquer, transform and conquer, greedy, dynamic programming and iterative improvement;
Learning Outcome 2: Compare, contrast, and apply key data structures: trees, lists, stacks, queues, hash tables and graph representations;
Learning Outcome 3: Define, compare, analyse, and solve general algorithmic problem types: sorting, searching, graphs and geometric;
Learning Outcome 4: Theoretically compare and analyse the time complexities of algorithms and data structures; and
Learning Outcome 5: Implement, empirically compare, and apply fundamental algorithms and data structures to real-world problems.

Task A: Implement the Graph Representations, their Operations and the Networked SIR model

In this task, you will implement data structures for representing undirected, unweighted graphs using the adjacency list, adjacency matrix and incidence matrix representations. Your implementation should also model vertices that have SIR model states associated with them. Your implementation should support the following operations:
ˆ Create an empty undirected graph (implemented as a constructor that takes zero arguments).
ˆ 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 sim- ulate how a virus can spread through a population.
Note that you are welcome to implement additional functionality. When constructing our 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 you should complete and ones you will be assessed on.

Data Structure Details
Graphs can be implemented using a number of data structures. You are to implement the 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).

For the above data structures, you must program your own implementation, and not use 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 use java.utils or other implementation from libraries, this will be considered as an invalid implementation 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 the adjacency matrix or incidence matrix, you may use one of the existing Map classes to do this.
ˆ if you choose to implement a map of vertex labels to its associated SIR state, you may use of the existing Map classes to do so.

Task B: Evaluate your Data Structures and SIR model

In this second task, you will evaluate your implemented structures in terms of their time complexities for the different operations and different use case scenarios. Scenarios arise from the possible use cases of contract tracing and epidemic modelling on a graph. In addition, run some epidemic modelling simulations to evaluate your structures within an application (epidemic modelling and simulation) and to explore more about the effect of the model parameters on epidemic spreading.

Write a report on your analysis and evaluation of the different implementations. Con- sider and recommend in which scenarios each type of implementation would be most appropriate. Report the outcomes of your SIR epidemic model simulations. The report should be 10 pages or less, in font size 12. See the assessment rubric (Appendix A) for the criteria we are seeking in the report.

Use Case Scenarios
Typically, you use real usage data to evaluate your data structures. However, for this as- signment, you will write data generators to enable testing over different scenarios of interest. We are also interested in the effect of the average degree of the graph3 on these scenarios. There are many possibilities, but for this assignment, consider the following scenarios:

Scenario 1 k-hop Neighbourhoods: When doing contract tracing and/or epidemic modelling, computing neighbourhoods is an important function. In this scenario, the graph is not changing, but important operations such as k-hop neighbourhood (recall this 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 conditions between people are likely not static and there will be need to update these over time. In this scenario, the contacts are changing (been added and deleted). In this scenario, you are to evaluate the performance of your implementations in terms of:
ˆ edge additions
ˆ edge deletions
You are to evaluate the performance the edge operations as the average degree and size (number of vertices) of the initial graph (before edge changes) are varied.

Scenario 3 Dynamic People Tracing: As time goes on, the people been traced will change. Although it is possible to have a large graph that tries to capture every possible person, 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 addition
ˆ vertex deletion
You 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 Simulation
In addition to evaluating how well the graph representations perform for the contract tracing and epidemic modelling simulations, we also want to experiment with how the networked SIR model works and performs.

Run epidemic simulation for different graph types (Erdos-Renyi and Scale-free), differ- ent seed initialisations and different infection and recover probabilities. For performance evaluation, evaluate each of the three data structures on a subset of the possible simula- tion parameters and compare how they perform (in terms of timing efficiency).

We don't expect a comprehensive analysis, but want you to explore and gain a better understanding of epidemic modelling and what it implies for how to limit the spread of epidemics.

Consider how you might present the results, but at a minimum plot the following:
ˆ Number of susceptible, infected and recovered after every iteration.

Data Generation
When 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 have an effect on the timing performance. However, without the usage and query data, it is difficult to specify what this distributions might be. Instead, in this assignment, uniformly sample from a fixed range, e.g., 0 to max vertex label of your graph when generating the vertices and edges for removing and adding and k-hop neighbourhoods, and a different range (e.g., greater than the largest vertex label when adding vertices (we do not want to repeatingly add vertices that are in the graph already).

For generating graphs with different initial average degrees and sizes, you can either use 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 average degrees to evaluate on. Due to the randomness of the data, you may wish to generate a few graphs with the same average degrees and sizes and take the average across a number of runs when performing the performance evaluation and analysis.

Attachment:- Algorithms and Analysis.rar