Assignments for Ling645/CMSC723

Assignment 1

This is the first assignment for Ling645/CMSC723, a simple version of depth first search in action. It will also allow us to calibrate everyone's programming skills and design apporpriate assignments for subsequent classes. contact us by email with questions.

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
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!
	 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 in 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

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

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

Have fun!

Return to the course home page.