The test format will be mostly short answer, and some discussion
questions. Further, there may be some questions that are analogous to
the questions last time. Remember, this exam is cumulative, so
everything from the first third of the course is also fair game.
- 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?
Back To The CS2360 Home Page
Ian Smith (iansmith@cc.gatech.edu)
Last Modified 13 Feb 95 by Ian Smith (iansmith@cc.gatech.edu)