CS6033 Homework Assignment 8∗
1. Create the adjacency list for the graph above. Create the adjacency matrix for the subgraph composed of nodes v, s, w, q and t. If I had asked you to create the adjacency matrix for the entire graph, how many entries would it have?
2. Create a Breadth-first tree. Show the d (distance) and π (predecessor) values that result from running breadth-first search on the directed graph above when starting at vertex q.
Draw the predecessor subgraph.
3. Show how depth-first search works on the graph of above. Assume that the for loop of lines 5 − 7 of the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex.
Draw the predecessor subgraph.
4. What is the running time of DFS if the graph is given as an adjacency matrix? Justify your running time.
5. Show that edge (u, v) is a:
• tree edge or forward edge if and only if u.d < v.d < v.f < u.f. • backedgeifandonlyifv.d<u.d<u.f<v.f
• crossedgeifandonlyifv.d<v.f<u.d<u.f
∗Many of these questions came from outside sources. 1
6. Let G = (V, E) be a connected1, undirected graph. Give an O(V + E) running time algorithm to compute a path in G that traverses each edge in E exactly once in each direction.
7. Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.
8. Write a method that takes any two nodes u and v in a tree2 T , and quickly determines if the node u in the tree is a descendant or ancestor of node v.
You may spend O(n) time preprocessing the tree, where n is the number of nodes in the tree.
Give the running time of your method and justify your running time.
9. You are working for the local animal shelter, and part of your job is to let the dogs play with each other.
There are two large fenced play areas at the shelter. Unfortunately, not all dogs get along with each other. During your training, the shelter has told you which dogs do not get along with each other.
Design an efficient algorithm to determine if/how you can separate the dogs into two groups so that in each group, the dogs do not fight with each other.
State your running time using Big-Oh notation. Justify your running time.
10. You are working at the local Dude(ette) Ranch, Rancho Costa Plenty, leading horse- back riding adventures. Part of your job is to ensure all your customers get back safely from their time on the trail. To do this, you must carefully consider the riders and horses personalities.
The owner told you before leaving on a vacation to Hawaii that some horses could not be behind other horses on the trail. You were surprised to hear that between any pair of horses on this ranch, there was alway at least one horse who could be in front of the other horse. However, it could be the case that Usain Colt must not be in front of Sir Neighs Alot; Sir Neighs Alot must not be in front of Hermoineigh; Hermoineigh must not be in front of Usain Colt. The owner gave you the list of which horses could not be behind which other horses.
Design an efficient algorithm to determine the order of the horses on the moun- taineering adventure.
State the running time of your algorithm.
Prove your algorithm works correctly.
1A undirected graph is connected if for any u,v in G.V the G contains a path from u to v. 2You know who is the parent of any non-root node.
11. (3 bonus points) Think of a good exam/homework question for the lecture 8.
