|Mehran Sahami Handout #3
CS121 July 5, 2001
Problem Set #1
Due: Beginning of class, Thursday, July 12th
General guidelines for problem sets
If anything is ambiguous or unclear:
1. Check the class web page for "Problem Set Clarifications"
2. Ask the instructor or TA for clarification
3. Make assumptions, state them clearly in your solution, and then work out the
You may discuss problems with colleagues, but all work must be done individually. Remember to cite the people you discussed a problem with on your assignment.
1. (15 points) Uninformed search
Consider the following search tree:
In what order are the nodes expanded using:
(a) breadth-first search
(b) depth-first search
(c) iterative deepening search (starting with depth 0, and incrementing the depth
by 1 in each iteration)
2. (20 points) Formulating search problems
In cryptarithmetic problems, letters stand for digits and the aim is to find a substitution of digits for letters such that the resulting sum is arithmetically correct. Each letter must stand for a different digit. Here is an example of such a problem:
FORTY Solution: 29786
+ TEN + 850
+ TEN + 850
That is: F=2, O=9, R=7, T=8, Y=6, E=5, N=0, S=3, I=1, X=4
Such problem can be solved using search techniques. Formulate cryptarithmetic as a search problem, by describing the states, operators, initial state, and goal test for such problems. Make you answer general enough to be applicable to any cryptarithmetic problem.
3. (10 points) Search spaces
Describe a search space (a graph is sufficient – it need not correspond to a real-world problem) in which iterative deepening search performs much worse, in terms of the number of nodes expanded, than depth-first search.
4. (20 points) A* Search
Problem 9.1 in Nilsson textbook, p. 160-161.
5. (15 points) Termination of A*
Problem 9.3 in Nilsson textbook, p. 161.
6. (20 points) Non-admissible heuristics
Invent and describe a heuristic for the 8-puzzle that sometimes over-estimates the cost to the goal (i.e., is not an admissible heuristic), and show how it can lead to a sub-optimal solution for a particular instance of the 8-puzzle.