Homework 1 FAQ

  1. 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.
  2. What about late homeworks?
    You can hand it in up to 2 days late, losing 30 points (out of 100) per day (including weekends).

  3. 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.
  4. In problem 1, there seems to be a missing path cost between nodes F & C!
    Yes, the cost is 2. The homework html and doc files are updated.
  5. 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) = 7.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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 imply A>C.