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

Using LISP one might represent this as follows:

  (defvar *graph*
    '((Nodes (A B C D E F G))
      (Edges ((A C) (A B) (C D) (C E) (D F) (E F) (E G)))))

Something you do frequently with DAGs is SEARCH: start at a node, and
wee if you can find a path to some other specified 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 (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 first node x off S  (that is, S is being treated as a stack)
    If x is the target
      Report success and exit --- we found the target!
      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!

Your assignment, due at the start class next week, is to implement
this algorithm.  Please turn in hardcopies of a program listing and a
few examples of the algorithm running on the above graph, with at
least one success and one failure.  Feel free to add statements to the
program that print out messages as the search is in progress letting
you know what's going on.

For those who have less programming experience, I recommend simulating
the algorithm by hand with pencil and paper for one or two cases
first.

For those with more programming experience, or for whom this is easy,
let me suggest the following two optional extensions:

  (1)  Modify the algorithm and implementation so that cycles in the graph
       don't cause you to go into an infinite loop

  (2)  Modify the algorithm and implementation so that on success the program
       returns its path through the graph rather than just saying it
       succeeded.

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.

Have fun!