This might seem the same file because I added the new hints on top of old
ones.. just read along :)

More hints for hw2:

1. for part b and c, write down what your intuition tells you to.we dont
expect you to derive a really good heuristic for either part.. just some
indication that you know what a heuristic is and you know how to find one
given interesting search domains.. A local maxima occurs when no matter
which action you choose you are getting away from your goal according to
the heuristic.. if this is not clear then come see me (mehmet), I can give
some nice pictorial descriptions which are always better than words :)

2. a counterexample will be enough here, if you can find one..

3. remember why the # of flips made by random walk was bounded by n^2?
does that property hold here? if you want more detailed explanation on
this please visit: http://www.ics.uci.edu/~eppstein/280e/001121.pdf

4. just follow the algorithms described in the class.. nothing tricky
about this..

6. for part c, there might be several interpretations for "on the board",
one of them is that if a and b are allies then c will be aware of this..
whether c's knowledge on this kind of situation changes anything is
something to think about.. another interpretation is that if a and b are
allies, instead of playing separately, they go together.. so in this turn
based game instead of having.. a, b, c, a, b, c we have a & b, c, a&b, c
etc..

7. Remember that the non-ES player can make errors... (why?)


8. this is more of a research question.. there are certain ratios where a
k-sat is considered to be hard.. Bart went over a few in the lecture.. and
in part b, you are not supposed to assume that the SAT instance is k-SAT
for some k.. the point of that problem is: what can you say about the
hardness of the instance if you dont know k?