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

What would the contents of the st array be?

Show the same DFS traversal, but include vertices you backtrack to.

What about if you started from node 3?

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?

Exercise 3

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

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.

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?

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
    2. t2->size
    3. t3->size
    4. key(STselect(0))
    5. key(STselect(3))
    6. key(STselect(9))
  2. Implement a non-recursive version of the select function show 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));
    }
    
  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)

    2. t0 = rotateLeft(t0)

    3. t0 = rotateRight(t0)

    4. t0 = partition(t0,5)

    5. t0 = partition(t0,8)

    6. t0->left = partition(t1,3)

The following questions are extra questions to do at home as practice for the prac exam.

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?

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?