HOMEWORK  (chapter 3: uninformed search)

Q-1: Give a complete problem formulation for each of the following.

1. The map coloring problem: Using only four colors, you have to color a planar map in such a way that no two adjacent regions have the same color.

2. The monkey-and-banana problem: A 3-foot-tall monkey is in a room where a banana is suspended from the 8-foot ceiling. He would like to get the banana. The room contains two stackable, movable, climbable 3-foot-high crates.

3. There are an empty 3-gallon jug and an empty 5-gallon jug. The jugs can be filled from a fountain of water, water can be poured between the two jugs, and the jugs can be emptied. The problem is to fill one of the jugs with exactly 4 gallons of water.

4. The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.

1. What is the difference between tress search and graph search?

2. What is the preferred uninformed search algorithm if we know the length of the path?

3. What is the difference between breadth-first search and uniform-cost search?

4. Under which conditions is depth-first search complete?

5. What are the major difficulties of bidirectional search?

Q-3: Apply breadth-first and depth-first graph search algorithms separately to the above water-jugs problem. Is the solution found by depth-first search optimal?

Q-4: Apply bi-directional search to the 8-puzzle. Is the first solution found by bi-directional search guaranteed to be optimal?