KIT205留学生代做、代写Data Structures、代写Java/Python/C++程序设计

日期：2019-05-05 11:08

KIT205 Data Structures and Algorithms

Assignment 2

Due: Friday 1st June, 11:55pm

Introduction

MiniMetro (https://dinopoloclub.com/minimetro/) is a game about designing efficient metro

transport. You design your tracks and assign your trains, and then commuters pop up wanting

to go somewhere. Each stop has a symbol indicating the type of neighbourhood. Each

commuter wants to get to a particular type of neighbourhood and will take the first train that

will get them there quickly.

This assignment is about some first steps towards an optimal solution for this game and will

involve graph algorithms and data structures. The assignment will give you some practice

working with graph data structures and implementing standard algorithms based on

pseudocode. It will also give you some experience developing unique algorithms for specific

problems by extending a standard algorithm.

Assignment Specification

For this assignment, we will create a simpler and more abstract representation of the

problem. You will be given a set of stops, their neighbourhood type and x,y coordinates. A

stop will be represented by the following struct:

typedef struct stop{

int type;

int x;

int y;

} Stop;

You will also be provided with the following function that generates an array of stops.

Stop* get_stops(int num_stops);

The main task for this assignment is to build a new graph using a subset of these edges that

connects all stops. You will attempt to build a track of minimal cost, where the cost is a

function of the edge weights (the cost of building the track) and the time taken for simulated

commuters to complete their journey.

You will be provided with a function that calculates the cost for a given graph:

float get_score(Graph *self);

This function calculates the cost for edges, and then simulated 1000 random trips. Each trip is

from a random stop to the nearest stop of a random type. It needs to have a working

Dijkstra’s algorithm to work properly.

Part A Converting the Data into Graph Format (~55%)

Your first task is to convert the stop information into a complete weighted graph where every

stop is connected to every other stop with the weight calculated as the distance between

stops. The distance can be calculated using sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) where

<x1,y1> and <x2,y2> are the coordinates of two cities (this function will be provided in the

base code).

You should store this initial graph using an adjacency list as specified below (given that this is a

complete graph, an adjacency matrix might be preferred, but our algorithms are going to work

with adjacency list representations, so we will stick with that). We are building an undirected

graph for this problem. To represent this as an adjacency list, each edge from u->v needs to

have a matching edge from v->u.

typedef struct edge{

int to_vertex;

float weight;

} Edge;

typedef struct edgeNode{

Edge edge;

struct edgeNode *next;

} *EdgeNodePtr;

typedef struct edgeList{

EdgeNodePtr head;

} EdgeList;

typedef struct graph {

int V;

int *vertex_types;

EdgeList *edges;

} Graph;

Part B Dijkstra’s Algorithm (~15%)

The get_score function makes use of Dijkstra’s algorithm, so your first step is to implement

this algorithm. You should implement Dijkstra’s algorithm based on the pseudocode on

Wikipedia (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). While a priority-queue

implementation might be best for our scenario, you should instead use a simple search to find

the nearest vertex.

Once you have correctly implemented this algorithm, you should be able to test it by

calculating a score for the initial fully connected graph.

Part C Minimal Spanning Tree (~15%)

Next, we want to see if we can improve on this score. Since there is a cost for each edge, it

makes sense to remove as many edges as possible while keeping the graph connected. A

minimal spanning tree should be a good starting place. So, your next task is to implement

Prim’s minimal spanning tree algorithm that will take the initial graph and return the MST.

There is a little pseudocode for Prim’s algorithm on Wikipedia

(https://en.wikipedia.org/wiki/Prim%27s_algorithm), but this is more abstract than the

pseudocode for Dijkstra. However, you can base your solution on your solution for Dijkstra.

The only things that change are:

The way you calculate the nearest unknown vertex. Instead of storing the distances

found so far, instead store the cost of connecting a vertex. You will also need to know

the edge that gives this cost, so add an array to keep track of this that stores the

vertex to connect to.

How you store your solution. We need to build a new graph, so start by initialising a

new graph with the same number of vertices as the graph provided, but no edges (but

don’t forget to initialise the edge lists). Then, when you find the nearest unknown

vertex, add two (one for each direction) edges into the graph to connect the new

vertex. These edges need to have the same weights as the corresponding edges in

the original graph.

How to process the nearest unknown vertex. This is very similar to Dijkstra. Just

loop through all of the edges from this vertex. If the edge connects to an unknown

vertex, and if the weight of this edge is less than the best cost found so far, then

update the cost for to-vertex, and store the current vertex to keep track of the edge

that gives this cost.

You can then check to see if the MST has improved the score.

Part D Can You Do Better? (~15%)

There is no need for us to use an MST. It is going to give the lowest possible cost for laying the

track, but it won’t necessarily give good commute times. So, your final task is to see if you can

improve on the MST. You might like to try:

Start with an MST, but add in some extra edges

Use MST, but try to force it to use edges that you think are useful (e.g. modify the

weights that the algorithm uses)

A combination of both methods, or something not based on MST at all (maybe

something based on graph colouring would work?)

To get good marks for this section, you must make a serious attempt to improve the score (not

just make a random change to the MST algorithm, for example).

Base Code, Program Output, and Testing

You will be provided with a Visual Studio base project that contains some utility functions for

generating stops and simulating commutes to calculate a score. The main function is already

set up for you, and comments show where you need to add your own code.

As you complete each part of the assignment, there are commented printf statements in the

main function that can be uncommented to test your implementation. However, it is best to

do additional testing. For the standard graph algorithms in particular, this should be tested on

graphs where the correct solution is known (either because you have calculated it by hand, or

because you found a suitable example online).

Once you start testing with the randomly generated graphs, you might like to use a fixed

random number seed (e.g. srand(123); ). This will make it easier to compare different runs.

The required output for this assignment is very minimal. The necessary printf statements

already exist in the code, you just need to uncomment them as you complete each part. With

a randomly generated graph of 20 stops, the output might be as follows:

base score: 2423.639160

mst score: 737.128357

my score: 728.430176

press enter to exit

The exact output that you get will depend on the random graph generated.

Assignment Submission

Assignments will be submitted via MyLO (an Assignment 2 dropbox will be created). You

should use the following procedure to prepare your submission:

Make sure that your project has been thoroughly tested using the School’s lab

computers

Choose “Clean Solution” from the “Build” menu in Visual Studio. This step is very

important as it ensures that the version that the marker runs will be the same as the

version that you believe the marker is running.

Quit Visual Studio and zip your entire project folder along with a completed

assignment cover sheet

Upload a copy of the zip file to the MyLO dropbox

History tells us that mistakes frequently happen when following this process, so you should

then:

Unzip the folder to a new location

Open the project and confirm that it still compiles and runs as expected

o If not, repeat the process from the start

KIT205 Data Structures and Algorithms: Assignment 2

Synopsis of the task and its context

This is an individual assignment making up 15% of the overall unit assessment. The assessment criteria for this task are:

1. Implement code to construct an adjacency list representation of a graph

2. Implement Dijkstra’s algorithm to find shortest paths

3. Implement Floyd-Warshall algorithm to find shortest paths

Match between learning outcomes and criteria for the task:

Unit learning outcomes

On successful completion of this unit… Task criteria:

On successful completion of this unit, you will be able to:

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

4. Use common algorithm design strategies to develop new algorithms when there are no pre-existing solutions

5. Create diagrams to reason and communicate about data structures and algorithms

1-3

1-3

-

-

1-3

Criteria HD (High Distinction) DN (Distinction) CR (Credit) PP (Pass) NN (Fail)

You have: You have: You have: You have: You have:

1. Implement generic

graph data

structures and

algorithms

Weighting 60%

Adjacency list correctly implemented

Correctly implemented Dijkstra’s

algorithm

Correctly implemented Prim’s MST

algorithm

Adjacency list correctly

implemented

Correctly implemented

Dijkstra’s and/or Prim’s

algorithm

Adjacency list correctly

implemented

Implemented Dijkstra’s

and/or Prim’s algorithm

with some errors

Adjacency list

correctly

implemented

Basic graph

tutorial code

attempted

2. Apply graph data

structures and

algorithms to solve

a specific problem

Weighting 40%

Correctly built an adjacency list graph

to represent the problem

Correctly implemented a custom

function to solve the problem

Freed all memory when no longer

needed

Correctly built an adjacency list graph to represent the

problem

Correctly implemented a custom function to solve the

problem

Correctly built an

adjacency list

graph to

represent the

problem

Some attempt