Reference no: EM132390841

COMP1002 Data Structures and Algorithms Assignment

Department of Computing, Faculty of Engineering and Science - Curtin University, Australia

1. Introduction

In practicals you have implemented and learned about a number of algorithms and ADTs and will be implementing more of these in the remaining practicals. In this assignment, you will be making use of this knowledge to implement a system to explore and compare a variety of ADT implementations. Feel free to re-use the generic ADTs from your practicals. However, remember to self-cite; if you submit work that you have already submitted for a previous assessment (in this unit or any other) you have to specifically state this. Do not use the Java implementations of ADTs - if in doubt, ask.

2. The Problem

This assignment requires the extension of your graph code to apply it to social network analysis. You will be simulating the spread of information (or disease) through a social network. In the network, at each timestep, there will be a probability of "liking" a post, which will expose your followers to the information. Liking a post also gives a probability of "following" the original poster - making a direct connection to the original source. Sample input files are available.

Your program should be called SocialSim, and have three starting options:

• No command line arguments : provides usage information
• "-i" : interactive testing environment
• "-s" : simulation mode (usage: SocialSim -s netfile eventfile prob_like prob_foll)

When the program starts in interactive mode, it should show the following main menu:

(1) Load network

(2) Set probabilities

(3) Node operations (find, insert, delete)

(4) Edge operations (like/follow - add, remove)

(5) New post

(6) Display network

(7) Display statistics

(8) Update (run a timestep)

(9) Save network

You can structure the menu/UI differently, just make sure at least those options are included.

When running in simulation mode, you will give the input files and probabilities on the command line, then output (append) the simulation state and statistics for each "timestep" to a file (unique filename per run).

In interactive mode you should be able to display the following statistics/information:

• Posts in order of popularity
• People in order of popularity
• A person's record - #posts, #followers, #following etc.

Once you have a working program, you will investigate the behaviour of social networks, and the impact of their structure on their performance. This investigation will be written up as The Report.

Documentation and Report -

You need to submit documentation in docx or pdf format.

Your Documentation will be minimum 2-4 pages (excluding UML and Javadocs) and should include the following:

• An overview of your code, explaining any questions that the marker may have. This is supplemented by the comments in your code. In general, if the marker is looking at your code and isn't sure why you have done something in that particular way, they will check your documentation to see if they can find an explanation.
• A UML Class diagram of your code
• A description of any classes you have, you need to let us know not only what the purpose of that class is but why you chose to create it. As part of this, also identify and justify any places where it was possibly useful to create a new class but you chose not to, especially when it comes to inheritance.
• Justification of all major decisions made. In particular, when you choose an ADT, underlying data structure or an algorithm, you need to justify why you chose that one and not one of the alternatives. These decisions are going to be of extreme importance in this assignment.

The Report will follow the structure of a standard academic report or paper. It should be at least 4-6 pages long. Required sections are:

• Abstract: Explain the purpose of the report and state what you are investigating, and the outcomes/recommendations.
• Background: Discuss your approach to developing the simulation code, and the aspects of the simulation that you will be investigating.
• Methodology: Describe how you have chosen to profile and compare multiple runs of the simulation, and why. You should give some prediction of the expected "performance" of the aspects of your code you are investigating - this includes time complexity and/or memory usage. Include the commands, input files, outputs - anything needed to reproduce your results.
• Results: Present the results of your simulations, and what you discovered.
• Conclusion and Future Work: Give your conclusions and what further investigations could follow. Do the actual results match your prediction?

PRACTICAL - GRAPHS

AIMS -

• To create a general purpose Graph class.
• To implement search algorithms in the Graph class.

ACTIVITY 0: UML CLASS DIAGRAM

We will be using an Adjacency List implementation of graphs in this practical. Before you start coding, draw up the class diagrams for the DSAGraph and DSAGraphNode classes. Make sure to include any other Classes they make use of. Update this diagram as you work through the practical.

ACTIVITY 1: GRAPH IMPLEMENTATION

Now let's create a DSAGraph class using linked list to store the list of nodes, and linked lists within each node to store the adjacency list.

• Make sure you can display() the graph to the screen to help your testing
• Test it with a small graph at first, then display(), add more nodes/edges and display again.

ACTIVITY 2: READ GRAPH FROM FILE

Two input files for graphs have been uploaded to the Prac area. Create a FileIO class to read in the graph information and create a DSAGraph object. Work out manually what they should look like and check it against your display() output.

ACTIVITY 3: MANUAL DEPTH FIRST SEARCH / BREADTH FIRST SEARCH

Consider the following graphs and carry out a breadth-first search and a depth-first search manually based on the algorithms in the lecture notes. (Assume they are sorted alphabetically - so you will choose vertices in alphabetical order).

ACTIVITY 4: IMPLEMENT DEPTH FIRST SEARCH / BREADTH FIRST SEARCH

Add methods for depthFirstSearch() and breadthFirstSearch() to your DSAGraph class. Test them against the graphs from Activity 2.

Attachment:- Data Structures and Algorithms Assignment Files.rar