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.
Q-2: Answer the followng questions:
What is the difference between tree 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?