Assignment 4 - JBP030 (Fall 2017)

Note: You should always justify your answers. Whenever you are asked to describe an algorithm, you should present three things: the algorithm, a proof of its correctness, and a derivation of its running time.

Exercise 1 [5 points]

(a) [2 points] Insert items with the following keys (in the given order) into an initially empty binary search tree: 23, 27, 12, 42, 34, 19, 5, 7. Draw the tree after any two insertions.

(b) [2 points] Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Why?

i.) 925, 210, 920, 234, 897, 256, 362, 363.

ii.) 2, 255, 411, 398, 320, 334, 397, 363.

iii.) 2, 395, 390, 211, 276, 382, 381, 250, 363.

iv.) 929, 268, 345, 623, 291, 395, 360, 363.

v.) 920, 200, 910, 240, 909, 250, 363.

(c) [1 point] Is the operation of deletion ''commutative'' in the sense that deleting $x$ and then $y$ from a binary search tree leaves the same tree as deleting $y$ and then $x$? Argue why it is or give a counterexample.

Exercise 2 [5 points]

(a) [1 point] Draw a binary tree (not a search tree) of height as small as possible that contain single symbols as keys such that running InorderTreeWalk would produce the sequence CHRISTMASTREE.

(b) [2 points] Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child (assuming that all keys are distinct).

(c) [2 points] Prove by induction that InorderTreeWalk outputs the nodes of a binary search tree in sorted order.

Exercise 3 [5 points]

A path in a graph is simple if all vertices in the path are distinct. Give a linear time algorithm that takes as input a directed acyclic graph $G$ and two vertices $s$ and $t$, and returns the number of simple paths from $s$ to $t$ in $G$. Note that your algorithm needs to only count the simple paths, it does not have to list them.

Exercise 4 [5 points]

For both of the directed graphs below: compute a topological ordering or show that it does not exist. If there is a topological order, give the discovery and finishing time for every node. When there are several possibilities to continue a search use the alphabetical order for tie-breaking (e.g., always visit node $a$ first).

In [ ]: