• What do strings in lisp evaluate to? What does a string look like in the printed representation? How do you compare them for equality (which predicate)?
• What does FORMAT do and why would you want to use it? What value does FORMAT compute?
• What does PROGN do? Why is it (really) a non-functional construct? Which other constructs that you know have an implicit PROGN? Which don't?
• What does the READ function do? Note: In my lecture I managed to let people confuse me here. READ does not evaluate the value it reads, but does evaluate its argument, or, more correctly, Lisp evaluates the argument to READ but READ does not evaluate what it reads.

• What is an ADT (Abstract Data Type)? Why is good? How do you use ADT's in the coding of an algorithm?
• Give some examples of different encodings of a graph which all could use the same functional interface.
• What does the ASSOC function do? How can it bite you ?
• What are the goals of abstraction?

• What is the is-a relationship and why is it useful? How is it related to an inheritance or class heirarchy graph? How could encode an inherticance graph in Lisp? What would the functions of this ADT be?
• How can some psychologists consider inheritance graphs the basis of human memory (storage of info)? What experiments tested this?
• Why can you encode a network using any consistant encoding?
• Using a graph, describe the relationships between various objects in a typical kitchen.

• What is linear search? What are the trade-offs involved in linear search (i.e. how do you improve its running time)?
• What is Depth First Search? Why is it named this? Why would you want to use it (instead of linear search) for searching a graph?
• Explain the algorithm for the DFS.
• Why does depth first search not always produce the shortest path between two nodes? What approaches could you use to try to correct this? (Hint: This is hard.)
• What is the difference between a pre-order traversal and a DFS? What bookeeping is necessary to determine the path used in a DFS and/or detect cycles?
• What's a state space, and why do you want to search it?
• What are "goodness" functions and why do they help you do state-space search? Why not just pre-compute all possible points in the state space (i.e. why are you generating the points in the state space as you go)?
• Given a state in the state space, how would go about figuring what points to check next? Note: this will require knowlege of the operators in the state space and the goodness function.
• Why are huerestics a useful tool in performing state space search? How can they create a problem (i.e. What is the hill-climbing problem)?

• What are some applications of state-space searching? Why is a parser a state-space search?
• In general, why is pattern matching (searching for patterns) generally applicable to state space searching?
• Explain the algorithm for a state-space search. What are the good and bad points of the algorithm I outlined in the notes?
• How does the introduction of an adversary affect the state-space search? What can (should) we assume about our adversary (i.e. should we assume he is smart or dumb)? Why?
• Overall, there is a problem (or is there?) with hueristics: what is it? What do hueristics give you in return for this problem?

Last Modified 13 Feb 95 by Ian Smith (iansmith@cc.gatech.edu)