CS156 Spring 2004Practice Midterm 1
To study for the midterm I would suggest
you: (1) Know how to do (by heart) all the practice problems. (2)
Go over your notes three times. Second and third time try to see how much
you can remember from the first time. (3) Go over the homework problems.
(4) Try to create your own problems similar to the ones I have given and
solve them. (5) Skim the relevant sections from the book. (6) If you want
to study in groups, at this point you are ready to quiz each other.
The practice midterm is below. Here are some facts about the actual
midterm: (a) The midterm will be in class .
(b) It is
closed book, closed notes. Nothing will be permitted on your desk except
your pen (pencil) and test. (c) You should bring photo ID.
(d) There will be more than one version of the test. Each version
will be of comparable difficulty. (e) If your cell-phone or beeper
goes off you will be excused from the test at that point and graded
on what you have done till your excusal. (f) One problem (less typos)
on the actual test will be from the practice test.
Student created solutions.
1. Consider the variation of the 8-puzzle where rather than having the
number 1 through 8, we instead have two red tiles, three white tiles,
and three blue tiles. The task in this variant is to arrange the two red
tiles to the right at the top, then the next row in white and the last row
in blue. Formally express this puzzle as a problem that might be solved by
a problem solving agent.
2. For each of the following uninformed search strategies say whether or
not it is complete. If it is not, give a counter-example situation:
breadth first search, depth-first seach, depth-limited search.
3. Suppose uniform cost search was being used with a step size of 2 on
the following weighted graph.
a---4-->b
|\
3 \
| 2
V V
c<-1-d
Explain how the nodes would be expanded (starting from root a).
4. Suppose Manhattan distance was being used. Explain which would be
the first four board considered after the initial board
5 X 2
1 4 8
6 7 3
using the A* algorithm. Give your
reasoning.
5. Explain briefly the simulated annealing algorithm.
6. Suppose we are using an inductive learning approaches to learn a
heuristic function for the A* algorithm. We have two feature f1 and f2 we
are considering. Our training set consists of n1, for which f1(n1)=10
f2(n1)=7 and the value of the exact solution is 15 and n2, for which
f1(n2)=7
f2(n2)=10 and the value of the exact solution is 20. What are the
values of the constants c1 and c2 that we will learn?
7. Give an example where one can do an alpha prune and an example of
where one can do a beta prune while doing minimax. Explain why your
example works.
8. Consider the following situation for four light switches on the control
panel of a nuclear power plant: (a) The leftmost two can never be
both on. (b) At most three light can ever be on. Express this as
a propositional logic knowledge base.
9. Give examples of situations of where hill-climbing algorithms can
get stuck.
10. Explain how the SMA* and IDA* algorithms work.
|