Assignment 1

----------------------------------------------------------------
Assignment 1: Implementing Depth-First Search
----------------------------------------------------------------

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, the following is a DAG.

  A --> C --> D --> F
  \      \          ^
   \      \         |
    \      \--> E --+
     \          \
      \--> B     \
                  \--> G

There are lots of ways to represent graphs.  A typical choice would be
to store the outgoing edges for each node.  For example, in perl one
might use a hash:

  %edges = (
    "a" => [ "c", "b" ],
    "c" => [ "d", "e" ],
    "d" => [ "f" ],
    "e" => [ "f", "g" ],
  );

so that @{$edges{"a"}} would be an array containing "c" and "b".

Something you do frequently with DAGs is SEARCH: start at a node, and
find.  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
(for 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 here is one
of the most common: depth-first search.

  Algorithm DFS(start-node,target)

    Create a list S, initially containing start-node as its only member

    While (S is not empty)
    {
      Pop the top node x off S  (that is, S is being treated as a stack)

      If x is the target {
         Report success and quit --- we found the target!
      }

      Else {
        For each edge (x, y) in the graph, i.e. for each edge departing x,
           Put y on the front of list S (that is, push y onto stack S)
      }
    }

    Report failure --- target can't be reached from start-node!


Here's what you need to do:


  PROBLEM 1

  Implement the DFS algorithm.  Please turn in: (a) the program
  listing, and (b) examples of the algorithm running on the above
  graph with two searches: the first search should start at A and look
  for F (success), and the second search should start at C and look
  for A (failure).  Feel free to add statements to the program that
  print out messages as the search is in progress letting us know
  what's going on. We will not be grading the program itself, so
  informative messages are the best way to ensure we can give you
  partial credit.

  Note: Graph information can be hard-coded in your program.  However,
  the starting node and the edge node must be input as two
  command-line parameters. For example, suppose you have a perl
  program called "hw1_prob1.pl", and you want to search for target
  node B starting at node A.  Your program must work with a command
  line "hw1_prob1.pl A B", i.e. "executable starting_node
  target_node".  (Same for the command line using any other
  programming language,) This will allow us to test your program by
  typing, e.g., "executable start_node target_node".


  PROBLEM 2

  Modify the algorithm and implementation so that cycles in the graph
  don't cause you to go into an infinite loop.  Test this by modifying
  the above graph to add an edge from node F to node C, and then doing
  the same two searches as in Problem 1.

  You can use the same program for both Problem 1 and Problem 2,
  e.g. distinguishing the two cases using an additional parameter on
  the command line.  Just make sure you tell us the appropriate
  command lines to use.


  EXTRA CREDIT (10% of this homework)

  Modify the algorithm and implementation so that on success the
  program returns its path through the graph rather than just saying
  it succeeded.  Demonstrate using both searches from Problem 1 and
  both searches from Problem 2.



TO TURN IN THE ASSIGNMENT

If you are registered for the class, please follow the instructions on
turning in assignments.

If you are not registered but would still like to have us look at your
assignment (time permitting!), you can e-mail the instructor a gzipped
tar file, as long as it's not too large.  (Say, no more than 2
megabytes.)



OTHER NOTES

A general note: depth-first search can be implemented using recursion
rather than an explicit stack, but we want you to use a stack.  This
turns out to be a special case of a more general notion called
agenda-driven processing that will be discussed in lecture.

Feel free to talk to each other, but make sure that you turn in
assignments individually and that what you turn in is sufficiently
your own work to meet the University's standards for academic
integrity.  (If you do collaborate, you must clearly identify who did
what.)