Quiz 4, Thursday, 10/30

(20 minutes. Open notes)

Suppose that Darth Vader has tampered with your implementation of the stack data structure. When you perform a pop operation, you don't get the top most element from the stack; instead you get the element just below the top most element. Of course, if the stack has only one element, then that is what you get when you perform a pop.

Using the stack so maliciously tampered by Lord Vader, perform depth first traversal on the graph shown below, starting from vertex A. For the traversal, show (i) the order in which vertices are discovered by depth first traversal and (ii) the depth first traversal tree. Assume that the neighbors of each vertex are scanned in alphabetical order of their names.