Here are examples of the types of questions one might find on the
upcoming midterm exam. While this gives you some idea about the kinds
of knowledge you might need or the complexity of individual
questions, you shouldn't make assumptions about the length
of the exam based on what you see below. Also, don't assume that
because some topic doesn't appear below that it won't appear on
your exam this Thursday. Everything that we've covered since
the beginning of the course if fair game, but the emphasis
will be on material we've covered since the first midterm exam.
1. (10 points): In the space below, use a directed graph representation
to construct an inheritance hierarchy for dinosaurs. Here are some
specific dinosaurs (and selected features) that you'll want to include
in your type hierarchy:
allosaurus brontosaurus pterodactyl
cold-blooded cold-blooded cold-blooded
eats meat eats plants eats plants
lays eggs lays eggs lays eggs
moves by walking moves by walking moves by flying
no. of legs is 2 no. of legs is 4 no. of legs is 2
stegosaurus triceratops tyrannosaurus
cold-blooded cold-blooded cold-blooded
eats plants eats plants eats meat
lays eggs lays eggs lays eggs
moves by walking moves by walking moves by walking
no. of legs is 4 no. of legs is 4 no. of legs is 2
2. (5 points): What advantages do you gain by representing knowledge in
an inheritance hierarchy?
3. (10 points): Below is a highly-abstracted map of routes between some
selected cities in Georgia, including estimated driving distances between
these cities. Construct a Common LISP data structure in which all this
information is represented. Call it *map*. Make sure that your data
structure is easy to use by the Common LISP function(s) that you'll be
designing for problem 4 and constructing for problem 5. Also make sure
that the data structure is easily understood by the professor-type who'll
be grading it.
[In this spot we'd have a graph with names of cities at the vertices
and numbers representing distances between cities on the edges]
4. (10 points): Using English or some simple pseudo-code language,
provide a high-level design for a function which takes as parameters
the names of two cities on the map in problem 3 and uses depth-first
search to find all the paths which connect one city to the other along
with the total driving distances for each of those paths. Don't forget
that a human has to read and grade this design. Call this function
find-all-paths. If this were a Common LISP function, it would be
invoked like this:
? (find-all-paths 'atlanta 'valdosta)
and it would return this:
((233 (atlanta macon perry tifton valdosta))
(234 (atlanta perry tifton valdosta))
(260 (atlanta butler albany tifton valdosta)))
5. (10 points): Using Common LISP, now implement the function you
designed for problem 4. For convenience, *map* can be a global variable.
6. (5 points): The HAL-9000 computer is playing a heated game of
hexapawn with his fellow space traveler, the enigmatic Dave Bowman. Part of
the state space for the game is described by the MiniMax search tree below:
[Here there would be a diagram of a state space with some numeric
evaluations of the goodness of the boards at the bottom level]
HAL has a static board evaluation function which returns a high number
for boards which are favorable to him, and low numbers for boards which
are favorable to Dave. The evaluation function is expensive to run, so
HAL wants to use it as little as possible.
After applying the evaluation function to boards A, B, and C, and returning
the values shown above, HAL is about to apply the function to board D. But
the SAL-9000 computer has been looking over HAL's digital shoulder and
whispers to him, "You need not do that, HAL. Given those values for boards
A, B, and C, you can choose your best move without evaluating board D."
HAL replies, "I believe there is a fault in your game-playing logic,
SAL. I must examine all boards in order to select my best move."
Which computer is right? Explain.
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: February 16, 1998