Reference no: EM133698288

Assignment: Graph Problem

Learning Outcome 1: Transform a real world problem into a simple abstract form that is suitable for computation

Learning Outcome 2: Implement common data structures and algorithms using a common programming language

Learning Outcome 3: Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms for specific tasks

Introduction
This assignment is more like a mini project. You will pick a graph-based problem of your choice and investigate potential problem solutions. Your submission will consist of both a Visual Studio project and a written report.

Project Choice
You may choose any type of graph problem. For example, the domain might be:

Social networks (online or real-world)
Computer networks
Navigation graphs
Neural networks
Road networks
Waterpipe networks
Project dependency graphs
Having chosen the domain that interests you, you should choose a specific problem within that domain. e.g. disease transmission, pathfinding, data propagation.

Next choose a standard graph algorithm that might form part of a solution to your problem, or one that is related to your problem domain. This could be one discussed in lectures, or another standard graph algorithm. For example:

Minimal spanning tree
Shortest path
Network flow
Topological sort
A big part of this assignment is the process of identifying a problem. The ability to identify real world problems and relevant algorithms is one of the key skills that you will need in your career. You should read about what is happening in the world around you and talk to other people (including, but not limited to, teaching staff) to find a topic that interests you.

Task 1: Standard Algorithm and Data Structure

For the first task, you should implement the standard algorithm of your choice using the adjacency list graph data structure developed in the tutorials. You may make minor modifications to the data structure to accommodate your problem domain, and you may convert the graph into a different format (e.g. adjacency matrix) if it makes sense to do so - but your graph must be initially constructed as an adjacency list. This could be achieved using a graph input file as used in tutorials, or procedurally generating a graph (e.g. using the Watts &Strogatz method).

Task 2: Problem Specific Algorithm
Your next task is to implement one or more solutions to your chosen problem and conduct an investigation. As with the first assignment you should be exploring alternatives, but the task now is more open ended. For example you might:

Compare two different solutions in terms of time and/or space efficiency
Compare two different solutions in terms of accuracy (e.g. exact solution vs approximate solution)
Compare a single solution with different configurations (e.g. how does a particular parameter affect performance?)
Compare a single solution for different types of graphs (e.g. random graph vs small world).
Or your particular problem and domain might lend itself to some other type of analysis. If you are unsure, check with your tutor or unit coordinator.

For this part of the assignment you should use the graph data structure (e.g. adjacency list or adjacency matrix) that is most appropriate.

As with the first assignment, you need to think about how to test your solution. Ideally, this will involve real-world graph data. You will find some real-world graph datasets online that you can use (e.g. graphdatasets.com). These datasets may also give you some inspiration for choosing a problem. Alternatively, you may need to generate random graphs for thorough testing (e.g. using one of the small-world graph construction techniques).

Task 3: Report
You will then write a report that includes the following sections:

Introduction and Background: introduce your problem domain and clearly describe the specific problem that this report addresses. Describe the significance of the problem and any trade-offs that might be relevant.
Methodology: describe in detail the approaches you have implemented, including pseudocode for each approach. Also describe your testing methodology.
Results and Discussion: present your results clearly and concisely, paying particular attention to the visual presentation of graphs and tables so that the reader is able to quickly and accurately compare your methods.
Conclusion: summarise your findings and discuss the significance of the results and potential future work that could be undertaken.
Unlike the first assignment, this should be a longer document in the style of a scientific report. The writing, structure, and presentation should be such that information is quickly and easily understood - it doesn't have to look pretty.

The following resources might help:

Computer Science Writing
How to write a first-class paper
Scientific Writing Made Easy
There is no word limit. As with any scientific writing, you should write as much as necessary so that another person could fully understand and reproduce your results - but absolutely no longer than necessary!

While there is no word limit, it is expected that around 1000 words should be ample for this report.

Your code submission should be structured in such a way that the marker can easily run your program to test your standard algorithm. Ensure that there are clear instructions for testing and include multiple test files.

It should also be easy for the marker to run and test your custom solution and make comparisons. Again, there should be multiple test files and/or the ability to procedurally and randomly generate graph data for testing. Think carefully about how best to display output to make it easy to interpret the results.

You can get an idea of what the marker is looking for by checking the learning outcomes at the top of the page.

For LO1, we want to see that you are able to transform your real-world problem into a graph data structure.

For LO2, we want to see that your code is correct, written in C, and that you have followed good development practices. This means that we want to see your test code and testing files, but we also want to see that your commit history on GitHub shows a well documented history of iterative and incremental development - not just one big commit. This will be absolutely essential for this assignment - submissions that do not show iterative and incremental development and testing will receive a failing grade!

For LO3 we will be looking at your approach to the investigation, your presentation of results, and your understanding of the significance of the results.

What we won't be assessing:

Quality of code and code comments. However, by now you should realise that it helps everyone (including you) if your code is clear, with at least some comments for difficult sections. If there is an error in your code, the marker may be able to correct it and continue marking if your code is clear and commented - but they don't have much time!

The presentation of your report. Again, it still helps you and the marker to make it clear and logical - it just won't be directly assessed for this assignment. So make it clear and concise, don't waste time making it fancy.