Tutorial Solutions Week 07

Exercise 1

Suppose that you started at the node labelled 0. Show the order in which nodes might be visited while performing a depth-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 7 4 3 5 6 2

What would the contents of the st array be?

0 0 0 4 7 3 4 1

Show the same DFS traversal, but include vertices you backtrack to. Stop when you have visited every node in the graph.

0 1 7 4 3 5 3 4 6 4 7 1 0 2

What about if you started from node 3?

 3 4 5 0 1 7 6 2
5 0 0 3 3 4 7 1
3 4 5 0 1 7 6 7 1 0 2

Exercise 2

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.) Show what values will be in the ST array.

What is the shortest (unweighted) path from 0 to 4 that BFS finds? By inspecting the graph is this the same as the shortest weighted path?

0  1  2  5  6  7  3  4 
ST ARRAY
0  1  2  3  4  5  6  7
-  0  0  5  5  0  0  0                   

This would find 0->5->4

0->6->4 and 0->7->4 would also be the shortest unweighted paths as they also contains only 2 edges.

If we wanted the shortest weighted path, 0->5->4 would not be the best as its cost would be 100, whereas 0->7->4 would only be 77.

Exercise 3

Dijkstra's Shortest Path Algorithm

Suppose that you started at the node labelled 3. What values do the dist and st arrays have in them when the Dijkstra's 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 - 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 4

Minimal Spanning Trees

Find a minimal spanning tree of the weighted graph in Question 2 using:
  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

Kruskal

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

Exercise 5

Graph Properties

In the 18th Century, the Prussian town of Konigsberg (now Kaliningrad) was famous for the seven bridges connecting its two central islands with the ban ks of the River Pregel, as shown in the diagram. Can you draw a path which crosses each bridge exactly once? If not, explain why.

Each landmass can be represented by a "vertex" or node, and each bridge with an an "edge",

The resulting graph looks something like:

Note that all four vertices have odd degree. The path can only exist if at most two vertices have odd degree. This is because it is an Euler path.

Exercise 6

Your boss asks you to write a program to find a path in a graph that visits every vertex at least once. Your boss tells you that you may go to lunch after you have run your program on a graph with 100 vertices. Will you ever get to have your lunch?

Your boss asks you write a program to verify whether a given path visits every vertex in a given graph exactly once. Your boss tells you that you may go to lunch after you have run your program on a graph with 100 vertices. Will you ever get to have your lunch?

This is the hamilton path problem. There is no known solution to this problem in less than exponential time. So if you try to run it on a graph with 100 vertices, you could be waiting an eternity. But it would depend on the number of edges in the graph you needed to run it on. If the graph had 0 edges, or say 1 edge etc, it would run very quickly. However if you had a complete graph there could be V! different paths to check. So worse case scenario would be that you would never get your lunch (assuming you obeyed your boss).

To verify a given solution to the hamilton path problem can be done in polynomial time, (so assuming you know how to write the program), you can run it in a reasonable amount of time regardless.

Exercise 7

Binary Search Trees

Consider the alternate implementation of BSTs discussed in lectures represented by:

typedef struct STnode* link;
struct STnode { 
  Item item; 
  link left, right; 
  int size;
};

static link rootNodeLink, emptyTree;
void STinit (int n) { 
  rootNodeLink = NEW (NULLitem, NULL, NULL, 0); 
  emptyTree = rootNodeLink;
}

Given the following tree (this picture does not show the links to the external empty tree nodes).

  1. What are the values of the following expressions

    1. t0->size 11
    2. t2->size 3
    3. t3->size 1
    4. key(STselect(0)) A
    5. key(STselect(3)) F
  2. Implement a non-recursive version of the select function given below.

    Item selectR (link currentTree, int k) {
      if (currentTree == emptyTree) {
        return NULLitem;
      }
      if (currentTree->left->size == k) {
        return (currentTree->item);
      }
    
      if (currentTree->left->size > k) {
        return (selectR (currentTree->left, k));
      }
    
      return (selectR (currentTree->right, k - 1 - currentTree->left->size));
    }
    
    Item STselect (ST st,int k) {
      return (selectR (st->root, k));
    }
    
    
    Item STselect (ST st, int k) {
        link currentTree = st->root;
        while (currentTree != emptyTree) {
            if (currentTree->left->size == k) {
                return (currentTree->item);
            }
            if (currentTree->left->size > k) {
                currentTree = currentTree->left;
            } else {
                k =  k - 1 - currentTree->left->size;
                currentTree = currentTree->right;
            }
         }
         return NULLitem;
    }
    
    
  3. In each of the following questions, start with the tree in the state shown above. Show the effect of executing each of the following operations on the tree:

    1. t4->right = rotateRight(t5)

                   M(11)
                   / \
                  /   \
                 /     \
                /       \
               /         \
              /           \
            E(6)         Q(4)
            / \           / \
           /   \         /   \
          /     \       /     \
        C(2)   H(3)   P(1)   S(2)
        /       / \             \
      A(1)     /   \           T(1)
              /     \  
            F(1)   J(1)
      
          
    2. t0 = rotateLeft(t0)

         
                    Q(11)
                     / \  
                    /   \  
                   /     \   
                  /       \  
                M(8)     T(2) 
                / \       /
               /   \    S(1)
              /     \
            E(6)   P(1)
            / \
           /   \
          /     \
        C(2)   H(3)
        /       / \
      A(1)     /   \    
              /     \
            F(1)   J(1)   
        
    3. t0 = rotateRight(t0)

           E(11)
             / \
            /   \
           /     \
         C(2)   M(8)
         /       / \
       A(1)     /   \
               /     \
              /       \
             /         \
            /           \
          H(3)         Q(4)
          / \           / \
         /   \         /   \
        /     \       /     \
      F(1)   J(1)   P(1)   T(2)
                            /
                          S(1)
        
    4. t0 = partition(t0,5)

                 J(11)
                  / \ 
                 /   \ 
                /     \ 
               /       \ 
              /         \  
            E(5)       M(5)
            / \           \ 
           /   \         Q(4)
          /     \         / \  
        C(2)   H(2)      /   \
        /       /       /     \
      A(1)    F(1)    P(1)   T(2)
                              /
                            S(1)   
        
    5. t0 = partition(t0,8)

        
                    Q(11)
                     / \ 
                    /   \  
                   /     \ 
                  /       \ 
                M(8)     T(2)
                / \       /    
               /   \    S(1)  
              /     \
            E(6)   P(1)
            / \
           /   \
          /     \
        C(2)   H(3)
        /       / \
      A(1)     /   \   
              /     \
            F(1)   J(1)  
        
    6. t0->left = partition(t1,3)

                    M(11)
                     / \       
                    /   \     
                   /     \
                  /       \
                 /         \
                /           \
              F(6)         Q(4)
              / \           / \
             /   \         /   \
            /     \       /     \
          E(3)   H(2)   P(1)   T(2)
          /         \           /
        C(2)       J(1)       S(1)
        /
      A(1)
      

The following questions are extra questions to do at home

Extra Question 1

Directed Graph DFS

What order would the nodes be visited while performing a depth first search starting at node d. What about if we started at node g?

If we called dfsR with starting node d we would get
d b a c g f
We would have to call dfsR again starting at node e to get all nodes in 
graph. 
So overall:
d b a c g f e

If we called dfsR with starting node g we would get
g
We would have to call dfsR again, starting at say node a, then again starting at node e to visit all nodes
So overall:
g a d b c f e

Extra Question 2

Directed Graph BFS

What order would the nodes be visited while performing a breadth first search starting at node d. What about if we started at node g?

If we called bfs with starting node d we would get
d b f g a c
We would then have to call bfs with starting node e
So overall:
d b f g a c e

If we called bfs with starting node g we would get
g
We would have to call bfs again, starting at say node a, then again starting at node e to visit all nodes
So overall:
g a d b f c e