Tutorial Solutions Week 06

Exercise 1

//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); 
} 
Key indexed-counting sort has a time comlexity of O(N+M) where N is the size of the data set we are sorting and M is the size of the range of possible keys. In both data sets we are sorting in this question, N is 10. In the first data set M is also only 10 but in the second M is 10000000. This means we would have to use additional space to store the counts for the 10000000 possibilities and then traverse through these arrays, making the second data set much more inefficient to sort with this algorithm.

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. Do a stable sort on the right most character, then the middle character, then the first character.
rub
fab
tub
are
art
rat
mat
bet
wet

fab
rat
mat
bet
wet
are
art
rub
tub

are
art
bet
fab
mat
rat
rub
tub
wet
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.

Sort on the first letter.

art
are
bet
fab
mat
rub
rat
tub
wet
Then sort each subfile. In this case only the words starting with a and r need to be sorted. We start with the LSD so the right-most character.
are
art
bet
fab
mat
rub
rat
tub
wet
Now the middle character.
are
art
bet
fab
mat
rat
rub
tub
wet

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).

0 2 0 7 1 7 6 4 3 5 3

What about if you had a stamina level of 50?

0 2 2 0 0 7 7 1 7 7 6

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 
};

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; }
    ...
}
int indexOf(Vertex v, Vertex w)
{
    assert(v != w); // no self-edges
    if (v > w) { Vertex tmp = v; v = w; v = tmp; }
    assert(w > v);  // redundant
    int i;  // counts the number of iterations
    int j;  // gives the increment for eah iteration
    int k;  // accumulates the index value
    for (i = 0, j = nV-1, k = 0; i < v; i++, j--) {
        k += j;
    }
    k += w-1;
    return k;
}

Maybe the use of comma in for loops hasn't been introduced. Re-write the function without using it if the above is not clear:

int indexOf(Vertex v, Vertex w)
{
    assert(v != w); // no self-edges
    if (v > w) { Vertex tmp = v; v = w; v = tmp; }
    assert(w > v);  // redundant
    int i;          // counts the number of iterations
    int j = nV-1;   // gives the increment for eah iteration
    int k = 0;     // accumulates the index value
    for (i = 0; i < v; i++) { k += j; j--; }
    k += w-1;
    return k;
}

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).

The following functions support the each-edge-stored-once variation of adjacency lists:

Edge normalise(Edge e)
{
    if (e.v > e.w) {
        Vertex tmp = e.v; e.v = e.w; e.w = tmp; 
    }
    return e;
}
void insertE(Graph g, Edge e)
{
    assert(g != NULL);
    assert(validV(g,e.v) && validV(g,e.w));
    e = normalise(e);
    int orig = length(g->edges[e.v]);
    g->edges[e.v] = insertVList(g->edges[e.v], e.w);
    if (length(g->edges[e.v]) > orig) g->nE++;
}
void removeE(Graph g, Edge e)
{
    assert(g != NULL);
    assert(validV(g,e.v) && validV(g,e.w));
    e = normalise(e);
    int orig = length(g->edges[e.v]);
    g->edges[e.v] = deleteVList(g->edges[e.v], e.w);
    if (length(g->edges[e.v]) < orig) g->nE--;
}
int neighbours(Graph e, Vertex v, Vertex w)
{
    if (v > w) { Vertex t = v; v = w; w = t; }
    return searchVList(g->edges[v], w);
}