Tutorial Exercises Week 06

Exercise 1

Trace through the sorting of the keys
9,0,1,7,4,3,1,3,1,9, where all keys are known to be from 0..9
with the keyIndex sorting implementation below.
How does that compare to sorting the following keys with the same approach?
9,0,1,7,4,3,1,3,1,999999, where all keys are known to be from 0..999999

//Sort array of size n with keys between 0 and m-1 
void keyIndexed(int items[], int n, int m) { 
	int i, index;
	int *count = malloc((m+1)* sizeof(int)); 
	int *tmp =  malloc((n) *sizeof(int)); 

        //initialise array 
	for (i = 0; i <= m; i++){
    		count[i] = 0; 
	}
 
	//Count how many of each key 
   	for (i = 0; i < n; i++){
       		count[items[i] +  1]++;
   	}

        //cumulative total
	for (i = 1; i <= m; i++){
      		count[i] += count[i - 1]; 
   	}

   	//use cumulative totals as indexes
   	for (i = 0; i < n; i++){
      		index = count[items[i]]++; 
      		tmp[index] = items[i]; 
   	}
  

        //copy back sorted data 
   	for (i = 0; i < n; i++){
       		items[i] = tmp[i]; 
   	}
   	free(tmp); 
   	free(count); 
}

Exercise 2

Use radix sort LSD to sort the strings.

art
rub
rat
mat
are
bet
fab
wet
tub

Repeat using an MSD radix sort, where MSD is used for the initial pass and then LSD radix sort is used to sort the subfiles.

Exercise 3

Assignment: Cheapest Least Visited Strategy

In what order would you visit the nodes if you started at vertex 0 and used the cheapest least visited approach from assn2 and you had stamina of 100000? (Show the first 10 vertices you would visit in the order you would travel to them).

What about if you had a stamina level of 50?

Exercise 4

Graph Implementations

In lectures we have looked at two different implemtations of graphs. Adjacency matrices and adjacency lists. See representations below:

//Graph.h definitions
// vertices denoted by integers 0..N-1 
typedef struct graphRep * Graph;
typedef int Vertex; 
typedef struct edge Edge;

// edges are pairs of vertices (end-points) 
struct edge { 
    Vertex v; 
    Vertex w; 
} ;

//Adjacency matrix unweighted graph representation

struct graphRep { 
    int nV;        // #vertices 
    int nE;       // #edges 
    int **adj; // matrix of booleans (0 or 1)
};

//Adjacency list graph representation
typedef struct vNode *VList;
struct vNode { 
    Vertex v; 
    VList next; 
}; 

struct graphRep { 
    int nV; // #vertices 
    int nE; // #edges VList 
    VList *adj; // array of lists 
};

Show how the following graph could be stored using the given representations:
Implement a function
```
int isEdgeInGraph (Graph G, Edge e);
```
that tests whether a given graph edge is present in the graph. The function should return 1 if the edge exists in the graph and 0 otherwise.
Implement the function for both the adjacency-matrix and the adjacency-list representations.
How could you change the implementations to represent a weighted graph with weights of type int?
Would your implementations of isEdgeInGraph need to change?
Write a function that would be able to find the degree of a given Vertex for each representation. Your functions should have the following prototype:
```
int GRAPHdegree(Graph g, Vertex v);
```
How could you store a label for each vertex in the graph, that you could access easily via its vertex id?
The following edges function is designed so that it simply requires a Graph as its parameter and then returns both the array and a count of the number of edges.
```
Edge *edges(Graph g, int *nE) { ... }
// which would be used as ...
Edge *es;  int n;   es = edges(g, &n);
```
Implement this edges() function for each of the two Graph representations. It should return the edges in normalised/canonical form (e.v < e.w), so that each edge appears exactly once in the result array.

Exercise 5

The standard adjacency matrix representation for a graph uses a full V×V matrix and stores each edge twice (at [v,w] and [w,v]). This consumes a lot of space, and wastes a lot of space when the graph is sparse. One simple way to improve the space usage would be to define the matrix elements as bool rather than int, e.g.

int **edges; // matrix of booleans (0 or 1)
... becomes ...
bool **edges; // matrix of booleans (0 or 1)
... where bool is defined as ... 
typedef unsigned char bool;

We could use even less space by storing just the upper (or lower) triangular part of the matrix, as shown in the diagram below:

The V×V matrix has been replaced by a single array containing just the "useful" parts of the matrix. This gives a new Graph representation:

// Upper-triangluar adjacency matrix graph representation

struct graphRep {
    int   nV;     // #vertices
    int   nE;     // #edges
    bool *edges;  // array of booleans (0 or 1)
};

Accessing the elements is no longer as simple as edges[v][w]. Write a function that takes two vertices from an edge and determines the corresponding index in the edges array which holds the boolean value for this edge. Use the following function template:

int indexOf(Vertex v, Vertex w)
{
    assert(v != w); // no self-edges
    if (v > w) { Vertex tmp = v; v = w; v = tmp; }
    ...
}

Exercise 6

The standard implementation of the adjacency list representation for graphs stores each edge twice. The edge (v,w) appears as a w stored in the adjacency list for v and as a v stored in the adjacency list for w. A more storage efficient representation (analgous to storing just the top-right half of the adjacency matrix), would be store information for each edge just once.

Re-implement the following functions from lectures to use this each-edge-stored-once variation of adjacency lists:

void insertE(Graph g, Edge e);
void removeE(Graph g, Edge e);
int neighbours(Graph g, Vertex x, Vertex y);

You should not assume that supplied Edge values will necessarily satisfy (e.v < e.w).