HOMEWORK (chapter 3: uninformed search)

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

- 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.

- 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.

- 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.

- 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.

- What is the difference between tress search and graph search?

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

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

- Under which conditions is depth-first search complete?

- 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?