Sequential And Concurrent Data Structures And Algorithms For Navigation Game

Task Description

The objective of this assessment is for you to demonstrate your understanding of issues related to the design and use of sequential and concurrent data structures and algorithms.

Some school students are playing a navigation game where they have to visit various locations around their school, identified by markers. Due to the layout of the school, it is not always possible to reach every marker directly from every other marker. The teacher wants to store some information about the markers and the distances between them. Here is an example of the information to be stored: (a distance of x from Marker Y to Marker Z means that Z can be reached directly from Y and vice versa, in x distance).

Marker 1 to Marker 5 – distance = 125m

Marker 1 to Marker 4 – distance = 460m

Marker 1 to Marker 6 – distance = 940m

Marker 2 to Marker 3 – distance = 732m

Marker 2 to Marker 1 – distance = 426m

Marker 3 to Marker 6 – distance = 655m

Marker 5 to Marker 2 – distance = 80m

Marker 4 to Marker 3 – distance = 750m

Marker 3 to Marker 5 – distance = 242m

Marker 6 to Marker 4 – distance = 676m

Your task is to decide what data structure/s would be best to store this information. This can include any of the data structures studied in the module, e.g. graphs, hash maps, trees, linked lists. When selecting a data structure, think about what operations the teacher might want to perform with the data, and which structures would be more efficient for these operations.

• Explain which data structure/s you chose and how it would store the information. Give full details about the types of the required objects and any other information relevant to the chosen data structure. Explain your reasons why you chose this data structure.

• Show, with the aid of diagrams or tables if appropriate, how the specific example information given above would be stored in your chosen structure.

• Give two examples of operations that can be performed using your data structure. Here are some suggestions (but feel free to think of other ideas):

• Finding whether or not it is possible to reach a given marker from another given marker without visiting another marker in between.

• Listing all the markers that can be reached from a given marker without visiting another in between.

• Giving the distance between two given markers without visiting another in between.

• Giving the shortest distance between two given markers (including paths with other markers in between).

• Finding a path between two given markers or stating that no path exists.

For each of the example operations you chose, explain how it would work using the data structure/s you chose and what time complexity it would have.

There is a public swimming pool with a limit of 5 swimmers in the pool at one time. (It is a very small pool!) The code for each swimmer is given below. It uses a semaphore poolSpace, to represent whether there is space left in the pool for more swimmers.

Swimmer code:

wait(poolSpace);

swim();

signal(poolSpace);

• There are six people, A, B, C, D, E and F who want to swim in the pool. Each person is an instance of the Swimmer class. Demonstrate how the semaphore prevents more than five people being in the pool at the same time by giving an example execution trace. Show the value of poolSpaceafter each wait or signal Ensure that you state the initial value of poolSpace.

If a wait operation executes, indicate whether the process succeeds or is placed in the queue. If a signal operation executes, indicate whether the value is changed or a sleeping process is woken up.

• The swimmers have become more competitive. They want to keep track of the fastest time to swim a length of the pool. They decide to use the code below, which uses a sharedvariable fastest to record the fastest time (i.e. smallest value) so far. Assume that when the method swim runs, it updates the Swimmer’s myTime int variable to the time just taken for this current swim. The details of how it does this is irrelevant.

Global shared variable: int fastest;

Swimmer code:

wait(poolSpace);

swim();

if (fastest > myTime){

fastest = myTime;

}

signal(poolSpace);

The code given is incorrect. It needs another semaphore to restrict access to fastest to one Swimmer at a time. Your task is to show how the given code (as shown, without another semaphore) could result in an incorrect value for fastest, i.e. where the time stored in fastest is not the actual quickest time so far. Give an example trace to show how this situation occurs, clearly stating the values of fastest and the local variable myTime for each swimmer at each step. Note: You can select any arbitrary times for myTime for each swimmer as long as it demonstrates how the problem occurs. 

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.