Homework 2

Due October 12, 2000

1. True/False

a) Depth-first search always finds a solution

b) Algorithm A is always more efficient than uniform-cost search

c) IDDF has time complexity is in the same order of that of breadth first search

2. Define the following terms

a) Open node in state space search

b) Admissible heuristic function

c) A solution in state space search

3. Briefly answer the following questions

a) What is the major problem of breadth first search

b) What is the major advantage of IDA* over A*

c) What is the “delayed goal testing”? Explain why delayed goal testing is crucial for guarantying the optimality of A* search.

4. Problem 3.3.d of the Textbook (p.87)

5. Problem 4.4 of the Textbook (p.118)