Tutorial Solutions Week 08

Revision: Graphs

Exercise 1

Breadth First Traversal

Suppose that you started at the node labelled 0. Show the order in which nodes might be visited while performing a breadth-first traversal of the graph. (You can assume, when faced with a choice of which node to visit next, you visit the node with the lowest label.)

0  1  2  5  6  7  3  4 

Exercise 2

Dijkstra's Shortest Path Algorithm

Suppose that you started at the node labelled 3. Trace through Dijkstra's algorithm. What values do the dist and st arrays have in them when the algorithm is completed? What is the length of the shortest path from node 3 to node 2? What is the actual path?

dist: 78 101 107 0 34 18 85 80 
  st:  5   7   0 -1 3  3  4  4 

Shortest path from 3 to 2 is of length: 107
Shortest path from 3 to 2 is: 3 5 0 2

Exercise 3

Minimal Spanning Trees

1. the Prim-Jarnik MST algorithm

   Show the resulting dist and st array values.

2. the Kruskal MST algorithm

What does the spanning tree look like?

What is the total cost? Prim

dist: 0.00 21.00 29.00 34.00 46.00 18.00 25.00 31.00 
  st:    0     7     0     4     7     3     7     0

Edges in Spanning Tree:
7 1 21.00
0 2 29.00
4 3 34.00
7 4 46.00
3 5 18.00
7 6 25.00
0 7 31.00

Total Cost: 204

3 5 18.00 accepted
1 7 21.00 accepted
6 7 25.00 accepted
0 2 29.00 accepted
0 7 31.00 accepted
0 1 32.00 rejected
3 4 34.00 accepted
4 5 40.00 rejected
4 7 46.00 accepted

Total Cost: 204

Revision Sorting

Exercise 4: Insertion Sort

1 void insertionSort(int items[], int n) {
2    int i, j, key;
3
4    for(i = 1; i <  n; i++){
5        key = items[i];
6        for(j=i; j > 0 ; j--){
7            if(key < items[j-1]){
8                items[j] = items[j-1]; //item shifts along to make room
9            } else {
10                 break;
11           }  
12       }  
13       items[j]=key;
14    }
15}   

1. Show how each of the arrays from the previous question (sorted, random, reverse), change as they are sorted by the program above. For each one count the number of comparisons and number of shifts.

   Sorted: 4 comparisons and 0 shifts
   1 2 3 4 5
   
   Random: 7 comparisons and 5 shifts
   3 2 4 8 1 
   At the end of each outer for loop
   2 3 4 8 1 
   2 3 4 8 1 
   2 3 4 8 1 
   1 2 3 4 8 
   
   Reverse: 10 comparisons and 10 shifts
   5 4 3 2 1
   At the end of each outer for loop
   4 5 3 2 1 
   3 4 5 2 1 
   2 3 4 5 1 
   1 2 3 4 5
   

2. With each line of code associate a cost and a formula expressing the number of times the C statement on that line will be executed when sorting n items in the worst case.

   Solution

   Line	Cost	Times
   4	c0	n
   5	c1	n - 1
   6	c2	2 + 3 + ... + n = (n (n+1)) /2 - 1
   7	c3	1 + 2 + ... + (n-1) = (n (n-1)) /2
   8	c4	1 + 2 + ... + (n-1) = (n (n-1)) /2
   10	c5	0
   7	c6	n-1

3. What is the asymptotic worst case time complexity of the algorithm implemented by this program. O(n^2)
4. What is the time complexity of the algorithm implemented by this program in the best case? We always break out of the inner loop after the first comparison, so we only execute lines 6 and 7 n -1 times. We never execute line 8 and we execute line 10 n -1 times. So over all we have a time complexity of O(n) for the best case. We still classify this algorithm as O(n^2) overall as that is its worst case complexity.

Exercise 5 - Sorting Linked Lists using Selection Sort

Implement selection sort, given the following definition of a linked list

typedef struct node * link;
struct node{
    Item item;
    link next;
};

link selectionSort(link list){ 
    link sorted = NULL;
    link curr = NULL;
    link prev = NULL;
    link max = NULL;
    link maxPrev = NULL;

    
    // Keep finding the max in the original list
    // and adding to the front of the sorted list
    // until the original list is empty
    while(list != NULL){
        //Find max
        prev = NULL;
        maxPrev = NULL;
        max = list;
        for(curr = list ;curr!=NULL;curr= curr->next){
           if(curr->item > max->item){
                max = curr;
                maxPrev = prev;
           }
           prev = curr;
        }
        //Remove from original list
        if(maxPrev != NULL){
            maxPrev->next = max->next;
        }else{
            list  = max->next;
        }
        // Add the max to the front of the sorted list
        max->next = sorted;
        sorted = max;
    }
    return sorted;
}

This implementation is not stable. An example of why not is that if there were duplicates, the first copy would be put a the front, then the next copy would be put at the front thus reversing the order of duplciates. By changing the code to have >= instead of > when looking for the max it would be.

  if(curr->item >= max->item){
                max = curr;
                maxPrev = prev;
  }

The implementation of selection sort using arrays from lectures is not stable as when the max/min item is selected it is swapped with the item at the appropriate location. When this swap occurs, the item that was at the appropriate location could be swapped to a position that makes it come after any of its duplicates.

Even if we were sorting something simple like 1 1 2 in descending order it would end up reversing the 1s.

This would be harder to make stable without having to shift possibly many items in the array and making the implementation less efficient.

Hashtables

Exercise 6

Draw a hash table of size 13.

Excercise

1. Chaining
2. Linear Probing
3. Double Hashing with a second hash function "7 - (k%7)". (Why would a second hash function such as "k%7" not be very useful?)

If there is any remaining time, use it to finish any questions that you did not cover in previous weeks.

1. Chaining

   Solution

   

2. Linear Probing

   Solution

   

3. Double Hashing with a second hash function "7 - (k%7)".

   Solution

   

   (Why would a second hash function such as "k%7" not be very useful?)

   Because you would get values in the range of 0 - 6. Values of 0 would not be very useful as you would just checking indexes 0 away - ie in the same spot the original collision was in.

Revision: Balanced Trees, 2-3-4 Trees

Exercise 7 - Balanced Trees

What is the minimum possible depth for a binary search tree containing 25 nodes? Note that we define depth as the number of nodes on the longest path from the root node to a leaf node.

The formula for determining this is ceil(log₂n) = ceil(log₂25) = ceil(4.6) = 5.

An alternative way of working it out would be to build a tree in level-order, filling each level before going to the next. This would give a tree like:

Note: A minimum height tree must be balanced. In a balanced tree, the height of the two subtrees differs by at most one. In a perfectly balanced tree, all leaves are at the same level. Let us consider perectly balanced trees initially. A perfectly balanced tree of height h will contain 1 node on the level 0, 2 nodes on the level 1, 4 nodes on the level 2, 8 nodes on the level 3, and so on. The j ^th level in a perfectly balanced tree always contains 2 ^j nodes.

The number of nodes in a perfectly balanced tree of height h = 2⁰+2¹+2²+...+2^j

And, by applying this formula, we have n = 2^j-1 and by rearranging the formula we have h=j = log₂(n+1) i.e

Therefore, for a tree with n nodes, minimum h = ceil(log₂(n+1)) e.g., a balanced tree with a height h can have any where from 8 to 15 nodes.

Exercise 7 - 2-3-4 Trees

Consider the following algorithm for inserting values into a 2-3-4 tree:

find leaf node where Item belongs (via search)
if node not full (i.e. order < 4)
    insert Item in this node, order++
if node is full (i.e. contains 3 Items) {
    split into two 2-nodes as leaves
    promote middle element to parent
    insert item into appropriate leaf 2-node
    if parent is full {
        continue split/promote upwards
        if promote to root and root is a 4-node
            split root node and add new root
    }
}

Show how the tree would be constructed if the following values were inserted in the order given:

 1 2 3 4 5 8 6 7 9 

While you are building the tree, keep count of the number of comparisons that are performed.

Once you have built the tree, compute the cost (#comparisons) of searching for each of the following values in the tree:

1  5  9  13

The following diagram shows how the tree grows:

Search costs (for tree after insertion of 9):

• search(1) = cmp(2),cmp(1) = 2
• search(5) = cmp(2),cmp(4),cmp(6),cmp(5) = 4
• search(9) = cmp(2),cmp(4),cmp(6),cmp(7),cmp(8),cmp(9) = 6
• search(13) = cmp(2),cmp(4),cmp(6),cmp(7),cmp(8),cmp(9) = 6

Exercise 8 - 2-3-4 Trees

A critical operation in the implementation of 2-3-4-trees is that of promoting the middle element of a 4-node to the parent node. The following diagram shows this operation for one simple case:

Implement a function that takes pointers to two nodes in a 2-3-4-tree, p points to the parent and c to the child, and implements the promotion operation. The function should implement the following requirements:

• if the child node is not a 4-node, do nothing, don't collect item, return 0
• if the parent is a 2-node or 3-node, promote, don't collect item, return 0
• if the parent is a 4 node, promote, removing the middle element of the parent,
  and copy former middle element, return 1

Use the following function interface:

int promote(Link p, Link c, Item *ret) { .... }

Assume no duplicate keys and assume a typical 2-3-4 node structure as below:

typedef struct _Item {
    int  key;
    // other fields as needed by application
} Item;
typedef struct _Node {
    int  order;    // 2, 3 or 4
    Item data[3];  // items in node
    Link child[4]; // links to subtrees
} Node;
typedef struct _Node* Link;
Link newNode(Item it); // creates new 2-node

int promote(Link p, Link c, Item *ret)
{
	assert(p != NULL && c != NULL && ret != NULL);
	if (c->order != 4) return 0;
	// split child node
	Link lc = newNode(c->data[0]);
	lc->child[0] = c->child[0]; lc->child[1] = c->child[1];
	Link rc = newNode(c->data[2]);
	rc->child[0] = c->child[2]; rc->child[1] = c->child[3];
	Item it = c->data[2];
	free(c);
	// if 4-node, extract middle item and make into 3-node
	int stat = 0;
	if (p->order == 4) {
		*ret = p->data[1];
		stat = 1;
		p->data[1] = p->data[2];
		p->child[1] = p->child[2];
		p->child[2] = p->child[3];
		p->order = 3;
	}
	// move to parent
	int i, j;
	for (i = 0; i < p->order; i++) {
		if (key(it) < key(p->data[i])) break;
	}
	for (j = p->order; j > i; j--) {
		p->data[j] = p->data[j-1];
		p->child[j+1] = p->child[j];
	}
	p->order++;
	p->data[i] = it;
	p->child[i] = lc;
	p->child[i+1] = rc;
	return stat;
}