Task Description

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.

1. Finding whether a path exists or does not exist between two markers in the information given. Consider two Markers Marker2 and Marker6  from the given information.  The code below is an implementation of breath first search algorithm in java to find whether there exists a path between two markers.  Breath first search(Beamer et.al 2011) is implemented in two steps  first of all there is the implementation of the queue where the first element in the queue will be the first out then, checks whether a vertex/node has been visited instead of waiting until it is dequeued from the queue (Goldberg et.al 2011).

// 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);

Data Structure Selection Criteria

    }

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;

Example Operations for Selected Data Structure

                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 

1. (Ton & Yellai 2008)

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

1. In the above given code is incorrect because the fastest time recorded will always be the time for the last person to swim. Therefore finding and storing the accurate fastest swimming time so far would be difficult as the fastest time recorded is for the last swimmer in the pool.

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.