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

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?

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?

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.

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.
3. What is the asymptotic worst case time complexity of the algorithm implemented by this program.
4. What is the time complexity of the algorithm implemented by this program in the best case?

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

Is this implementation stable?

Hashtables

Exercise 6

Draw a hash table of size 13. Use the hash function "k%13" and insert the keys: 5, 29, 32, 0, 31, 20, 23 and 18 into your table (in that order) using the following strategies for handling collisions.

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

(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