Tutorial
COMP20007 Design of Algorithms
Week 6 Workshop
1. Topological sorting A topological ordering of a directed acyclic graph (DAG) is a way of sorting the nodes of the graph such that all edges point in one direction: to nodes later in the ordering.
One of the algorithms discussed in lectures involves running a DFS on the DAG and keeping track of the order in which the vertices are popped from the stack. The topological ordering will be the reverse of this order.
Find a topological ordering for the following graph.
ABC
DEF
GHI
2. Binary tree traversals When traversing a binary tree we have a decision to make about order. If we represent a general binary tree as follows, where x is the root, and l and r are the (possibly empty) left and right sub-trees respectively, we can discuss different traversal orders more concretely.
x
lr
Now, we can define the traversal orders like so:
Inorder: traverse l, visit x, traverse r
Preorder: visit x, traverse l, traverse r
Postorder: traverse l, traverse r, visit x
Write the inorder, preorder and postorder traversals of the following binary tree:
6 48 079
3
1
3. Level-order traversal of a binary tree A level-order of a binary tree first visits the root, then the left child of the root, then the right child of the root, then the left child of the left child (the leftmost grandchild of the root) etc., going left to right at each level.
In which order are the nodes of the binary tree from Question 3 visited in a level-order traversal.
Which graph traversal algorithm could we modify to perform a level-order traversal of a binary tree? Write the pseudo-code.
4. Binary tree sum Write a recursive algorithm to calculate the sum of a binary tree where each node contains a number.
Confirm that your algorithm works on the tree from Question 3.
Which order does your algorithm process nodes in? Inorder, preorder or postorder?
Computer Lab
Use today¡¯s lab time to work on Assignment 1. Make sure you can log in to dimefox, copy your code over, compile and run your program on the server.
If you¡¯ve completed the assignment already feel free to use this time to complete previous lab exercises.
2