KIT205留学生讲解、辅导Data Structures、辅导Java/Python/C++程序设计 讲解数据库SQL|讲解数据库SQL
- 首页 >> 其他 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
and 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 startKIT205 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-3Criteria 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
to build the
graph for this
problem
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
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 startKIT205 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-3Criteria 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
to build the
graph for this
problem