, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
1/6
Assignment 2: Graph Problem
Weight: 40%
Due: October 20th, 11:55pm
Learning Outcomes
1. Transform a real world problem into a simple abstract form that
is suitable for computation
2. Implement common data structures and algorithms using a
common programming language
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 graphbased
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.
, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
2/6
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 the test file
format and redirected input as used in tutorials, or by reading other
file formats, or procedurally generated.
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?)
, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
3/6
Compare a single solution for different types of graphs.
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
, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
4/6
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.
Submission and Marking
You just need to submit your report (containing the GitHub link) on
MyLO. Do not modify your GitHib project after submission. If you
have made a small mistake that you would like to correct, please
check with the unit coordinator first.
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.
1. For LO1, we want to see that you are able to transform your
real-world problem into a graph data structure.
2. 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!
3. 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:
, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
5/6
Quality of code and code comments. However, by now you
should realise that it helps everyone (inlcuding 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.
See the rubric for more detail on assessment.
Academic Integrity
In this unit you are expected to use all resources at your disposal to
develop your code. This includes:
Tutorial and unit materials
Code that you find online
Code written wholly or in part by AI tools (e.g. Copilot or
ChatGPT)
Regardless of how you develop your code, you must document
any sources or resources you used. This can be a code comment
before the relevant part of code, or a comment at the top of the file.
And you are responsible for the code you submit, including any
errors, regardless of the source.
You may also use tools like ChatGPT or Grammarly to assist with
writing your report. This is especially useful if English is not your first
language. Again, you are responsible for what you submit, and
please also add the tools used to your list of resources.
You may also discuss the assignment with other students or help
each other with related tutorial work. And of course you may discuss
the assignment with your tutor or unit coordinator. But you may not
directly assist another student with their assignment or receive
assistance from anyone on your own assignment.
Under no circumstances should you share your code with
another student - and that includes sharing your screen in
online chat! It is very easy for someone to take a screen shot
without your permission, and you will both be in breach of academic
integrity - even if it is just carelessness on your part.
, 15:16 Assessment Task 2: Graph Problem - KIT205 Data Structures and Algorithms
6/6
At no time should your GitHub repository be made public. It is a
good idea to add the unit coordinator as a contributor as soon as
you start the code.
We take any breach of academic integrity very seriously. If you fail to
properly document sources, or get help from other people, or
provide help to other students (intentionally or just carelessly), we
will report it and the consequences can be severe.