Homework 1 FAQ
- How and when do I hand in the homework?
The homework is due at the start of the 4/17 class. Remember to write
your name *AND* email address on the homework!
You can hand in the homework one of two ways:
(A) Hand in your written/printed assignment at the start of class. Printed
text is preferred but not required, but if you write please write clearly.
You can work on the assignment in any word processors that can handle HTML
text (such as MS Word 97, or emacs), or in MS Word; a Word version of the
homework is provided on the classweb.
(B) This is experimental; you can hand in your homework by emailing me an
electronic version (Word or HTML only) of your homework before the start of
class. I'm trying to save paper, but this may be a little inconvenient for
you. The marked homework will be returned to you in electronic form.
- What about late homeworks?
You can hand it in up to 2 days late, losing 30 points (out of 100) per day
- Is this homework hard?
You should start on it early; the homework is not very hard, but there are
a few trickier questions which requires thinking.
- In problem 1, there seems to be a missing path cost between nodes F &
Yes, the cost is 2. The homework html and doc files are updated.
- We need the h value for a node for problem 1.
The h value is provided beside the nodes. For example, the node D has h(D)
- We can't find the h value for node A anywhere.
You don't need it. You also don't need to write the f value for this node.
- In problem 2, is it sufficient to show a case where the heuristic gives
the same value for each move?
No, you should come up with a case where the heuristic thinks one move is
better than the other.
- Hints for Problem 2
This problem is trivial if you think in higher abstraction. Spoiler warning.
A. It is possible to use the same example for both heuristics.
B. In the min # of misplaced tiles heuristic, the heuristic will only give
judgements that one move is better than the other in a relatively limited
number of board configurations. This heuristic wants "order", i.e.
wants tiles to be in their final resting place as soon as possible. Do you
always want this? Playing just one game of 8-puzzle will give you the insights
on why or why not.
- Hints for Problem 4
Think of time table slots for the classrooms as grids on a chessboard, and
define new variables that work on this chessboard. The "variables"
c, k, s and e mentioned in the problem are actually constants in a real world
setting, so you may run into trouble if you use them as variables for the
CSP. To formulate the CSP, you should give the variables, domains for these
variables and constraints on the variables in this CSP, just like the CSPs
we did in class.
- Hints for Problem 3
Best-first search relies on a priority queue to keep track of nodes. What
are the properties of the priority queue data structure? Can you implement
the comparison-based algorithm with these same properties? Also, the comparison
function may not be transitive, i.e. if A>B, B>C, doesn't necessarily