a.This is because when it comes to representation of distances where the shortest and the longest paths to a destination have to be computed, graph data structure is best suited (Puntambekar 2009). To represent the given data you will have to develop a matrix containing all the vertices as graph nodes and edges. In the given information the nodes will be Marker 1, Marker 2, Marker 3, Marker 4, Marker 5 and Marker 6. The edges are the distances between the Markers. The choice of graph to represent the information is because graph data structure will capture all the information and enable the implementation of the operations to be done on the information. It will also enable the implementation of operations like finding the shortest path to a certain node or vertex(Mehlhorn 2012)
b.The graphical representation of the information will be as follows
Code representation of the storage of the information in java will be as follows
import java.util.LinkedList;
public class Game
{
//this class is for defining the graph
static class Graph
{
int N;
LinkedList<Integer> adjListArray[];
Graph(int N)
{
this.N = N;
//the size of the array is equal to the number of nodes
adjListArray = new LinkedList[N];
for(int i = 0; i < N ; i++){
adjListArray[i] = new LinkedList<>();
}
}
}
// adding of edges
static void addEdge(Graph navigationGame, int src, int dest)
{
navigationGame.adjListArray[src].addFirst(dest);
navigationGame.adjListArray[dest].addFirst(src);
}
//displays the graph
static void printGraph(Graph navigationGame)
{
for(int n = 0; n < navigationGame.N; n++)
{
System.out.println(“the adjacent vertices are “+ n);
for(Integer pCrawl: navigationGame.adjListArray[n]){
System.out.println(” -> “+pCrawl);
}
}
}
public static void main(String args[])
{
// create the graph given in above figure
int N = 6;
Graph navigationGame = new Graph(N);
addEdge(navigationGame, 1, 5);
addEdge(navigationGame, 1, 4);
addEdge(navigationGame, 1, 6);
addEdge(navigationGame, 2, 3);
addEdge(navigationGame, 2, 1);
addEdge(navigationGame, 3, 6);
addEdge(navigationGame, 5, 2);
printGraph(navigationGame);
}
}
From the above code, a graph named navigationGame is created. The respective edges are then added to the graph using navigationGame.addEdge specifying the starting and ending points which are the nodes for the edges. In this case the nodes are the Markers1 to Marker6.
After identifying the nodes/ the vertices the weights of the edges are specified.
// Breath First Search function to check whether there exists a path between Mark 6 and Mark 2.
import java.io.*;
import java.util.*;
class Graph
{
private int N;
private LinkedList<Integer> adj[];
Graph(int n)
{
N = n;
adj = new LinkedList[v];
for (int r=0; r<n; ++r)
adj[r] = new LinkedList();
}
void addEdge(int n,int y)
{
adj[n].add(y);
}
void BFS(int mark2)
{
// have all the vertices not visited
boolean visited[] = new boolean[V];
// creation of a queue
LinkedList<Integer> queue = new LinkedList<Integer>();
// have mark2 vertex as visited and push it in the queue
visited[]=true;
queue.add(mark2);
while (queue.size() != 0)
{
//
mark2 = queue.poll();
System.out.print(mark2);
//the marked vertex Mark2 will be used to identify the adjacent vertices
Iterator<Integer> n = adj[mark2].listIterator();
while (n.hasNext())
{
int v = n.next();
if (!visited[v])
{
visited[v] = true;
queue.add(v);
}
}
}
public static void main(String args[])
{
Graph navigationGame = new Graph(6);
navigationGame.addEdge(1, 5);
navigationGame.addEdge(1, 4);
navigationGame.addEdge(1, 6);
navigationGame.addEdge(2, 1);
navigationGame.addEdge(2, 3);
navigationGame.addEdge(3, 6);
navigationGame.addEdge(5, 2);
System.out.println(“the breadth first traversal is”
navigationGame.BFS(mark2);
}
}
Giving the shortest distance between two markers. This is where the kruskal’s or the prism methods of finding the minimum spanning tree comes in handy. Kruskals MST algorithm first needs to sort the edges in the graph according to their weights (Quirin et.al 2008). This is done in an increasing order, from the one with the smallest weight to the one with the largest weight Najman et.al (2013). The MST found from the graph will be the shortest path between the two markers.
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
{
int src, dest, weight;
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
{
int parent, rank;
};
int vertices, edge;
Edge edge[];
Graph(int ve, int edg)
{
vertice = ver;
edge = edg;
edge = new Edge[edge];
for (int r=0; r<edg; ++r)
edge[r] = new Edge();
}
int find(sub subs[], int r)
{
if (subs[r].parent != r)
subs[r].parent = find(subs, subs[r].parent);
return subs[r].parent;
}
void Union(subs subs[], int z, int d)
{
int zroot = find(subsets, z);
int droot = find(subsets, d);
if (subs[zroot].rank < subs[droot].rank)
subs[zroot].parent = droot;
else if (subs[zroot].rank > subs[droot].rank)
subs[droot].parent = zroot;
else
{
subs[zroot].parent = zroot;
subs[zroot].rank++;
}
}
void KruskalMST()
{
Edge result[] = new Edge[mst]; // Tne minimum spanning tree is stored here
int a = 0;
int f = 0;
for (r=0; r<mst; ++r)
result[r] = new Edge();
//sort all the edges depending on their weight
Arrays.sort(edge);
sub subs[] = new sub[mst];
for(r=0; r<mst; ++r)
subs[r]=new sub();
for (int n = 0; n < mst; ++n)
{
subs[n].parent = n;
subs[n].rank = 0;
}
r = 0;
while (a < mst – 1)
{
//the smallest edge is picked
Edge next_edge = new Edge();
next_edge = edge[r++];
int z = find(subsets, next_edge.src);
int d = find(subsets, next_edge.dest);
if (z != d)
{
result[a++] = next_edge;
Union(subs, z, d);
}
//do away with the next edge
}
//display results of the minimum spanning tree
System.out.println(“the mst is”);
for (r = 0; r < a; ++r)
System.out.println(result[r].src+” — ” +
result[r].dest+” == ” + result[r].weight);
public static void main (String[] args)
{
int vertices = 6;
int edges = 7;
Graph navigationGame = new Graph(vertices, edges);
navigationGame.edge[0].src = 1;
navigationGame.edge[0].dest = 5
navigationGame.edge[0].weight = 125;
navigationGame.edge[1].src = 1;
navigationGame.edge[1].dest = 4;
navigationGame.edge[1].weight = 460;
navigationGame.edge[2].src = 1;
navigationGame.edge[2].dest = 6;
navigationGame.edge[2].weight = 940;
navigationGame.edge.edge[3].src = 2;
navigationGame.edge.edge[3].dest = 1;
navigationGame.edge.edge[3].weight = 426;
navigationGame.edge.edge[4].src = 2;
navigationGame.edge.edge[4].dest = 3;
navigationGame.edge.edge[4].weight = 732;
navigationGame.edge.edge[4].src = 3;
navigationGame.edge.edge[4].dest = 6;
navigationGame.edge.edge[4].weight = 655;
navigationGame.edge.edge[4].src = 5;
navigationGame.edge.edge[4].dest = 2;
navigationGame.edge.edge[4].weight = 80;
navigationGame.edge.KruskalMST();
}
Kruskal method takes a lot of processing time because the edges have to be sorted in an increasing order which consumes more time and space because of the utilization of the quick sort algorithm. The time complexity for this is O(ElogE + ElogV)
Swimmer code
Public void Wait(poolSpace){
if(poolSpace = 5){
enque[];
poolSpace–;
signal(poolSpace);
}else{
Signal(poolSpace){
poolSpace++;
}
}
public static void main (String[] args)
{
int poolSpace = 5;
Wait(poolSpace);
If(poolSpace > 5){
poolSpace–;
}
Signal(poolSpace);
}
If a person wants to swim, he initializes the wait process. If the poolSpace is equal to 5 the maximum number of people the pool can hold, the person is queued up and has to wait until the number of people in the pool reduces by at least one. If the poolSpace is less than five then the person is signaled to enter the pool, therefore the poolSpace increases by one person.
The initial value of the poolSpace is five. If the wait process is executed that means the poolSpace is equal to five and when the signal process is executed that means the poolSpace is less than five and after execution of the signal process the poolSpace is increased by one person who initiated the process.
Swimmer code
Consider the given code
wait(poolSpace);
swim();
if (fastest > myTime)
{ fastest = myTime; }
signal(poolSpace);
The shared variable fastest is not initialized to hold the value of the fastest swimming time before comparing it with the swimming time variable myTime for the current swimmer. Therefore during the code execution before comparison the shared variable fastest is reset to a null value. The comparison is done between a null value and the time taken by the current swimmer to swim in the pool. The shared variable fastest then takes up the myTime value for the current swimmer as the fastest time.
The shared variable fastest is then implemented in a way that all the swimmers access it at the same time. With this type of implementation the fastest time will pick the local variable myTime for the last swimmer in the pool. If only there could be an array of swimmers where each swimmer accesses the shared variable fastest one at a given time then the accurate and correct fastest time in the pool could be achieved.
References
Puntambekar, A. A. (2009). Data structures and algorithms. Technical Publications.
Mehlhorn, K. (2012). Data structures and algorithms 2: graph algorithms and NP-completeness (Vol. 2). Springer Science & Business Media.
Beamer, S., Asanovic, K., Patterson, D. A., Beamer, S., & Patterson, D. (2011). Searching for a parent instead of fighting over children: A fast breadth-first search implementation for graph500. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2011-117.
Goldberg, A. V., Hed, S., Kaplan, H., Tarjan, R. E., & Werneck, R. F. (2011, September). Maximum flows by incremental breadth-first search. In European Symposium on Algorithms(pp. 457-468). Springer, Berlin, Heidelberg.
Quirin, A., Cordón, O., Guerrero?Bote, V. P., Vargas?Quesada, B., & Moya?Anegón, F. (2008). A quick MST?based algorithm to obtain Pathfinder networks (∞, n− 1). Journal of the American Society for Information Science and Technology, 59(12), 1912-1924.
Najman, L., Cousty, J., & Perret, B. (2013, May). Playing with Kruskal: algorithms for morphological trees in edge-weighted graphs. In International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing (pp. 135-146). Springer, Berlin, Heidelberg.
Ton, H. T., & Yellai, P. R. (2008). U.S. Patent No. 7,353,515. Washington, DC: U.S. Patent and Trademark Office.
Ben-Ari, M. (2012). Principles of concurrent and distributed programming (Vol. 2). Addison-Wesley.
Essay Writing Service Features
Our Experience
No matter how complex your assignment is, we can find the right professional for your specific task. Contact Essay is an essay writing company that hires only the smartest minds to help you with your projects. Our expertise allows us to provide students with high-quality academic writing, editing & proofreading services.
Free Features
Free revision policy
$10Free bibliography & reference
$8Free title page
$8Free formatting
$8How Our Essay Writing Service Works
First, you will need to complete an order form. It's not difficult but, in case there is anything you find not to be clear, you may always call us so that we can guide you through it. On the order form, you will need to include some basic information concerning your order: subject, topic, number of pages, etc. We also encourage our clients to upload any relevant information or sources that will help.
Complete the order form
Once we have all the information and instructions that we need, we select the most suitable writer for your assignment. While everything seems to be clear, the writer, who has complete knowledge of the subject, may need clarification from you. It is at that point that you would receive a call or email from us.
Writer’s assignment
As soon as the writer has finished, it will be delivered both to the website and to your email address so that you will not miss it. If your deadline is close at hand, we will place a call to you to make sure that you receive the paper on time.
Completing the order and download
