首页
编程语言
数据库
网络开发
Algorithm算法
移动开发
系统相关
金融统计
人工智能
其他
首页
>
> 详细
辅导CO2226留学生、辅导Creative Computing、Java程序调试、讲解Java 讲解SPSS|解析R语言编程
University of London
Computing and Information Systems/Creative Computing
CO2226 Software engineering, algorithm design and analysis
Coursework assignment 2 2018–19
Submission details
What to hand in
Marks will be awarded for correct code (i.e. for code that produces results; if your code does
not produce the correct result, no marks will be awarded for that part of the question).
You must submit one Java file called Ass226
.java. For example, if your student
number ID is 101031722, your file will be named: Ass226101031722.java
When this file is compiled it must produce a single file Ass226
.class e.g.
Ass226101031722.class. When run, this must produce the answers to all the coursework
assignment questions by implementing the appropriate algorithms.
Your java file may contain other classes, but they must all be included in the single java file;
please do not submit multiple Java files as you will get a mark of zero – we only need one
file. You must write your code assuming all data files are in the same directory as the program.
Failure to do this will lead to a mark of zero. If you cannot complete a particular question the
answer should say ‘NOT DONE’. Your program should take the text files described below as
command-line arguments.
To run your program, the examiners will type (pay attention that the filenames are referenced
without the file extension):
java Ass226101031722 cities cities_lon_lat randomGraph
Your output should look like this:
Name: Joe Doe
Student ID: 101031722
Question 1: 2
Question 2: 200 205
Question 3: 4
Question 4: 15
Question 5: [350, 352]
Question 6: 5.12
Question 7: 29.47
Execution Time: 32094 milliseconds
These are just sample answers to give you an idea of what output format is expected from your
program. The examiners will change the data files to test your programs so make sure your
program works with files containing fewer/more cities. Try deleting some lines from the files and
see if your program gives different answers.2
Efficiency
You will be penalised if your program runs too slowly (5 marks for every minute over 5 minutes
on a machine with Intel Core i7 processor with12 gigabytes of RAM).
Try to speed up your program, by not recomputing values that you have already computed.
Instead, store them (rather than recomputing).
Use System.nanoTime(); to time your program. (Read the value at the beginning and end
of your program and subtract and divide by a million.)
IF YOU DO NOT INCLUDE THE EXECUTION TIME OF YOUR PROGRAM YOU WILL
SCORE ZERO.
IF YOU DO NOT USE THE DATA PROVIDED YOU WILL SCORE ZERO.
ALL SOLUTIONS SHOULD INVOLVE CALLS TO YOUR GRAPH INSTANCE METHODS;
DO NOT TRY TO CHEAT BY FINDING ANSWERS ELSEWHERE.
CO2226 Coursework assignment 2 – preparation and pre-assignment tasks
Finding the shortest paths in unweighted graphs (breadth-first search)
Find out about Adjacency matrices for representing Graphs. Here is a program to help you
become familiar with them:
import java.util.HashSet;
import java.util.ArrayList;
public class graph
{
double [] [] adj;
graph (double [] [] a)
{
adj= new double [a.length][a.length];
for (int i=0;i
for (int j=0;j
adj[i][j]=a[i][j];
}
public HashSet
neighbours(int v)
{
HashSet
h = new HashSet
();
for (int i=0;i
return h;
}
public HashSet
vertices()
{
HashSet
h = new HashSet
();
for (int i=0;i
return h;
}3
ArrayList
addToEnd (int i, ArrayList
path)
// returns a new path with i at the end of path
{
ArrayList
k;
k=(ArrayList
)path.clone();
k.add(i);
return k;
}
public HashSet
> shortestPaths1(HashSet
> sofar, HashSet
visited, int end)
{
HashSet
> more = new HashSet
>();
HashSet
> result = new HashSet
>();
HashSet
newVisited = (HashSet
)
visited.clone();
boolean done = false;
boolean carryon = false;
for (ArrayList
p: sofar)
{
for (Integer z: neighbours(p.get(p.size()-1)))
{
if (!visited.contains(z))
{
carryon=true;
newVisited.add(z);
if (z==end) {
done=true;
result.add(addToEnd(z,p));
}
else
more.add(addToEnd(z,p));
}
}
}
if (done) return result; else
if (carryon)
return shortestPaths1(more,newVisited,end);
else
return new HashSet
>();
}
public HashSet
> shortestPaths( int first,
int end)
{
HashSet
> sofar = new HashSet
>();
HashSet
visited = new 4
HashSet
();
ArrayList
starting = new ArrayList
();
starting.add(first);
sofar.add(starting);
if (first==end)
return sofar;
visited.add(first);
return shortestPaths1(sofar,visited,end);
}
public static void main(String [] args)
{
double [ ] [] a = {
{0.0, 1.0, 1.0, 0.0},
{0.0, 0.0, 1.0, 1.0},
{0.0, 1.0, 0.0, 1.0},
{0.0, 1.0, 1.0, 0.0}
};
graph g = new graph(a);
for (int i=0;i
{for (int j=0;j
if (i!=j) System.out.println(i + " to " + j +": "+
g.shortestPaths(i,j));
}
}
}
Draw a picture of the graph and see if you agree with the output. Play with the program and
alter the graph in order to check that you understand how the program works.
The cities distance problem
Study the following files of data about main cities:
cities.csv. This file has two fields in the following order: id code for the country and
the name of the city in English, and it is used for describing cities.
randomGraph.csv. This file contains three fields, the id code of the source city, the id
code of the destination city and the cost for taking this route.
cities_lon_lat.csv. This file has three fields in the following order: the id code for the
city, the city’s longitude and the city’s latitude.
Examine the following program:
import java.io.*;
import java.util.Scanner;
import java.util.*;
class Assignment2
{
static int N= 500;
static double [][] edges = new double[N][N];
static TreeMap
cityNames = new TreeMap
();5
static ArrayList
convert(ArrayList
m)
{
ArrayList
z= new ArrayList
();
for (Integer i:m)
z.add(cityNames.get(i));
return z;
}
static HashSet
> convert
(HashSet
> paths)
{
HashSet
> k= new HashSet
>();
for (ArrayList
p:paths)
k.add(convert(p));
return k;
}
public static void main(String[] args) throws Exception
{
for(int i=0;i
for(int j=0;j
edges[i][j]=0.0;
Scanner s = new Scanner(new FileReader("randomGraph"));
String z =s.nextLine();
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
edges[Integer.parseInt(results[0])]
[Integer.parseInt(results[1])]=1.0;
edges[Integer.parseInt(results[1])]
[Integer.parseInt(results[0])]=1.0;
}
s = new Scanner(new FileReader("cities"));
z =s.nextLine();
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
cityNames.put(Integer.parseInt(results[0]),
results[1]);
}
graph G= new graph(edges);
int st =Integer.parseInt(args[0]);
int fin = Integer.parseInt(args[1]);
System.out.println("Shortest path from " + =
cityNames.get(st) + " to " +
cityNames.get(fin) + " is" +
convert(G.shortestPaths(st,fin)));
}
}6
Dijkstra’s algorithm (Finding the shortest path in a weighted graph)
Watch Dijkstra’s Algorithm (YouTube video) and Dijkstra's Algorithm again.
Study Dijkstra's algorithm MIT Lecture 17 Video.
Study the pseudo code below for Dijkstra's Algorithm to find a shortest path from
start to end:
Set S = {start};
//S is the set of vertices for which the shortest paths from
start have already been found
HashMap
Q = Map each Vertex to Infinity
(Double.POSITIVE_INFINITY), except map start -> 0;
// Q.get(i) represents the shortest distance found from start
to i found so far
ArrayList
[] paths;
For each i
set path[i] to be the path just containing start.
while (Q is not empty)
{
let v be the key of Q with the smallest value;
//I've given you a method int findSmallest(HashMap
t) for this
if (v is end and Q does not map v to infinity)
return paths[end]; let w be the value of v in Q;
add v to S;
for (each neighbour u of v) do
{
if (u not in S)
{
let w1 be the the weight of the (v,u) edge + w;
if w1 < the value of u in Q, then do the following:
{
update Q so now the value of u is w1
update paths(u) to be paths(v) with u stuck on the
end
}
}
remove v from Q;
}
}7
Task 1
Implement Dijkstra’s Algorithm using the pseudo-code above; namely, put a function
dijkstra into the graph class.
Here are some hints:
int findSmallest(HashMap
t)
{
Object [] things= t.keySet().toArray();
double val=t.get(things[0]);
int least=(int) things[0];
Set
k = t.keySet();
for (Integer i : k)
{
if (t.get(i) < val)
{
least=i;
val=t.get(i);
}
}
return least;
}
Now, fill in the following bits:
public ArrayList
dijkstra (int start, int end)
{
int N= ...;
HashMap
Q = new HashMap
();
ArrayList
[] paths = new ArrayList [N];
for (int i=0;i
{
Q.put(i,...);
paths[i]=new ArrayList
();
paths[i].....;
}
HashSet
S= new HashSet();
S.add(...);
Q.put(start,....);
while (!Q.isEmpty())
{
int v = findSmallest(...);
if (v==end && ...) return ....;
double w = Q.get(...);
S.add(...);
for(int u: neighbours(v))
if (...)
{
double w1= ....;
if (w1 < Q.get(u))
{8
Q.put(u,...);
paths[u]= addToEnd(...);
}
}
Q.remove(...);
}
return new ArrayList
();
}
Task 2
Test your implementation using the following test program:
class testDijk
{
public static void main(String [] args) throws Exception
{
int N=1000;
double edges[][]=new double[N][N];
for(int i=0;i
for(int j=0;j
edges[i][j]=0.0;
Scanner s = new Scanner(new FileReader("randomGraph"));
String z;
while (s.hasNext())
{
z =s.nextLine();
String[] results = z.split(",");
edges[Integer.parseInt(results[0])]
[Integer.parseInt(results[1])]=Double.parseDouble(
results[2]);
}
graph G= new graph (edges);
System.out.println(G.dijkstra(Integer.parseInt(args[0]),
Integer.parseInt(args[1])));
}
}
Use this randomGraph file (please note that this example is from a different scenario which
refers to tube stations so you might need to make some adjustments when reading in the
data).
Each line of the file has three values: the first two are vertices and the thirds is the weight
of the edge between them.
When you run:
java testDijk 0 999
You should get:
[0, 492, 665, 114, 452, 999]9
CO2226 Coursework assignment 2 – main questions
Please note that cities in the questions are referred to by their name. As part of the
assignment, you will need to resolve them into their ISO codes (e.g. 300 for Athens). In
the case of a direct link, please ignore this option and look for a route that includes
at least one extra link.
1. How many shortest paths exist between the cities of Athens and Tehran? A
shortest path here means a path with a minimal number of vertices. (Note: Use
the shortestPaths method above.)
[15 marks]
2. Which pair of cities have the highest number of shortest paths between them?
Just give the city IDs.
[10 marks]
3. How many shortest paths do they have?
[10 marks]
4. How long are each of these shortest paths?
Hint: You may wish to use the following method.
static ArrayList
firstElement (HashSet
> s)
{
return ( ArrayList
)s.toArray()[0];
}
[10 marks]
5. Which set of cities are furthest away from the city of Toronto in terms of number
of stops? (Just print out the set of numbers corresponding to the cities).
[15 marks]
6. What is the length in terms of sum of the weights of the edges of the shortest path
(in terms of the sum of the weights of the edges) between the cities of Rome and
New York? (use Dijkstra's Algorithm).
[20 marks]
7. What is the length (in km) of the shortest path (in terms of distance) between the
cities of Lisbon and Manila? (Note: Use Dijkstra's Algorithm).
[20 marks]10
You will need to use the following method (and the relevant data from the cities_lon_lat
file).
static double realDistance(double lat1, double lon1,
double lat2, double lon2)
{
int R = 6371;
// km (change this constant to get miles)
double dLat = (lat2-lat1) * Math.PI / 180;
double dLon = (lon2-lon1) * Math.PI / 180;
double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 *
Math.PI / 180 )* Math.sin(dLon/2) * Math.sin(dLon/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-
a)); double d = R * c;
return d;
}
For finding the distance in km between any two points on the Earth's surface with given
latitude and longitude: the latitude and longitude of each city is given in the cities_lon_lat
file. You will have to use this to compute the adjacency matrix for the weighted graph
representation of the cities problem. We need the ad[i][j] to be the distance from city i to
city j now.
You will also need to write a method for finding the length of path by adding up all the
weights of the edges in the path.
[Total: 100 marks]
[END OF COURSEWORK ASSIGNMENT 2]
联系我们
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-21:00
微信:codinghelp
热点文章
更多
讲解 artificial intelligence...
2024-04-18
辅导 kxo206 database managem...
2024-04-18
辅导 comp9417 project: multi...
2024-04-18
辅导 bl5611 drugdiscovery202...
2024-04-18
辅导 comp5313/comp4313—larg...
2024-04-18
辅导 aem 4500 / econ 3860 / ...
2024-04-18
辅导 math 1151, spring 2024 ...
2024-04-18
辅导 7ssmm712 – topics in a...
2024-04-18
辅导 elec eng 3088/7088 comp...
2024-04-18
辅导 pols0010 data analysis ...
2024-04-18
辅导 econ 602: course projec...
2024-04-18
讲解 economics 253 - spring ...
2024-04-18
辅导 artd 6151: sustainabili...
2024-04-18
讲解 ifn647 text, web and me...
2024-04-18
讲解 cse340 project 2: pars...
2024-04-18
讲解 mane - 4500 modeling an...
2024-04-18
讲解 civil 750 - timber engi...
2024-04-18
辅导 qbus6860 sustainable en...
2024-04-18
辅导 25721 investment manage...
2024-04-18
讲解 eeee4123 hdl for progra...
2024-04-18
热点标签
hpm 573
dts101tc
cs 2820
cpt108
math2319
dts204tc
qm222
comp2511
ccs599
infs1001
mat2355
eeee4123
25721
ifn647
pols0010
7ssmm712
comp5313/comp4313—large
bl5611
kxo206
comp532
elec207
kxo151
cs 2550
comp9417
qbus6860
stat0023
csci 1100
comp2003j
cse340
cs 61b
cs360
fin 3080
ierg 4080
cs6238
cit 594
finm7406
hw6
elec9713
asb-2522
lit301
mcd4540
geog0030
125.330
biol0006
125.320
cs3334
fit2093
acct1101
110.309
masy1-gc
cs314
elec0048
gds104
mg5637
fit2096
comp3411
07
mso3610
math5905
eel4837
sehs4515
cpt s 321
asb2522 investment
ma214
co2104
comp30023
mgmt2015
32516
math32051
econ1012
mark2052
dsci 525
comp3310
econ0019
abmf3184
aps106
antc27
finm7401
itp122
tech2300
math3026
cs 211
36318
cao107
fit1047
is2022
comp9024
ics4u
2xc3
en.540.635
4qqmn506
finn3081
phys10362
sta601
ec481e
math5165
csi 2120
el1205
comp7250
ecos3013
beam065
swen90004
info1113
sehh2042
comp2051
csc325
mne 6130
ai6126
inu1111
ecs150
is61x6
cse115
seng6110
bus265
cpts260
mphy0009
csc306
eco2011
ee3004
st332
idepg001
info6001
cpt106
qbus2820
fins5516
finm7409
fit3152
isom3028
eece 6083
ceg5304
mcd4700
eecs 493
eg25h4
38173
elc5216
infs6071
lubs5996m
7ssmm803
glbh0031
phys1120
comp52715
eeb240
soci3403
psyc3241
fin570
218.323
lng310
rim3352
bio206
bu.450.760
math3836
cmns3490
iy5610/4610
cpt304
ac6105
comp3334
ac.f633
asb-3525
cs 1501
cpt408
bust10134
lng206
acfi302
soc100
infr11199
csc1002
comp9334
csci 2122
etf5650
eco202y1y
acct608
apm236
gbsh0007
efim20005
actl5105
elec 292
sdsc4026
ds2500
dts205tc
cs 455
swen20003
cs202
158.739-2024
eco2101
benv0149
ifb001
mth6142
phy344
infs3202/7202
fc308
st332/st409
eeng20004
cmt313
chc4008
6g6z0041
1cwk100
ec204
stat512
eng2008
comp20007
联系我们
- QQ: 99515681 微信:codinghelp
© 2024
www.7daixie.com
站长地图
程序辅导网!