KIT205编程代写、代做c/c++程序语言

日期：2023-10-18 10:21

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.

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?)

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

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:

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.

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.