Description

Assignment 1: Searching Graphs & Climbing Trees
NOTE: This assignment is meant as a “warm-up” exercise with the goal of introducing you to Python. If these problems takes you more than a few hours, you might want to reconsider whether you have the programming background necessary for the course.
1 Graphs
A directed acyclic graph (DAG) consists of a set of nodes and a set of directed arcs (also known as directed edges) between those nodes. For example, Figure 1 shows a DAG.

Figure 1: An example of a directed acyclic graph.
There are many ways to represent graphs. One choice is to store, for each node, a list of all the nodes it is connected to via outgoing edges. In Python, one might use a dictionary, as in Listing 1. For example, edges[’A’] is a list containing all nodes connected to node A via outgoing edges.
Listing 1: Encoding an acyclic graph with a Python dictionary
Something you do frequently with DAGs is Search: start at a node, and find another node. For example, in the above graph a search starting at D for target node F would succeed, but a search starting at D for target node B would fail. Search of this kind is the heart of a great deal of work in artificial intelligence; for example, game-playing programs (such as tic-tac-toe, chess, checkers, backgammon, etc.) often view the game as a search for a winning board configuration, and parsing a sentence can be viewed as searching for a legal parse tree that fits the sentence.
There are different algorithms for searching a graph, but one of the most common ones is the depth-first search (DFS) algorithm. Algorithm 1 shows how depth-first search works on a graph.
Algorithm 1 DFS(S,T): An algorithm for depth-first search Require: A starting node S and the target node T.
1: Create a list L, initially containing S as its only member
2: while L is not empty do
3: Pop the top node x off L (think of L as a stack)
4: if x is the target then
5: Report success and quit — we found the target !
6: else
7: for each outgoing edge (x,y) of x do
8: Put y on the front of list L (that is, push y onto stack L)
9: end for
10: end if
11: end while
12: Report failure — T can’t be reached from S !
Problems (30 points)
1. Implement the DFS algorithm in Python. Please turn in: (a) the program listing, and (b) examples of the algorithm running on the graph in Figure 1 with three searches: the first search should start at A and look for G (success), the second search should start at A and look for D (success), and the third search should start at C and look for A (failure).
Note: Graph information can be hard-coded in your program. However, the start node and the end node must be input as command-line parameters. For example, suppose your DFS program is called dfs.py, and you want to search for target node B starting at node A. Your program must work with the following command line invocation:
dfs.py A B
2. Modify the algorithm and implementation so that on success the program returns its path through the graph (i.e., list of nodes that were examined, in order) rather than just saying it succeeded. Demonstrate using the searches from (1) above.
3. Modify the algorithm and implementation so that on success the program returns the actual path from the start node to the end node. Demonstrate using the searches from part (1) above.
Note: Since problems (1) through (3) are closely related, you can elect to turn in a program listing that addresses all three problems if you wish. Alternatively, you can turn in a program listing for each problem.
2 Trees

Figure 2: An example of a rooted tree.
Instead of using a simple Python dictionary for rooted trees, we have provided you with a simple library called trees.py that makes it very easy to create trees of the form needed for this assignment. Listing 2 shows how you would create the example tree shown here using this library.
One of the operations employed on a rooted tree is to find the Lowest Common Ancestor (LCA) of any two nodes in the tree. The LCA of any two nodes u and v is simply as the lowest (or deepest) node in the tree that has both u and v as descendants (where we allow a node to be a descendant of itself). For example, in our example tree, nodes D and E have B as their LCA. Given how we have defined a rooted tree, finding the LCA is straightforward as shown in Algorithm 2.
Algorithm 2 LCA(U,V ): An algorithm to find the LCA
Require: A Rooted Tree T which contains the given nodes U and V.
1: Find the path PU from the node U to the root of T. PU starts at U, contains all intervening nodes between U and the root, and ends at the root node.
2: Find the path PV from the node V to the root of T.
3: Find the intersection L of these two paths that is furthest from the root node.
4: return L
Listing 2: Creating and Exploring a Rooted Tree
Problem (20 points)
4. Extend the Trees class defined in trees.py with an additional method called lca() which takes the names of two nodes as input and returns their LCA. Please turn in: (a) the program listing, and (b) traces of your program running on a few examples.