First solve the problems that are given. Next, make a list of the subproblems you considered while solving them. Discuss how a computer might be programmed to solve each of the given problems, and how each of the problems might be represented to the computer. If you find a state-space representation for a problem, estimate the size of the state space and try to identify heuristics and algorithms the machine could use to search it. If computer time is available to you, choose a problem and try to implement a computer program that can solve it.

(a) Given a 3-gallon jug and a 4-gallon jug, how can precisely 2 gallons be put into the 4-gallon jug? There is a sink nearby, such that either jug can be filled from the tap and its contents can be poured down the drain. Also, water can be poured from either jug into the other, but the jugs themselves are the only measuring devices available.

(b) Given a 5-gallon jug and an 8-gallon jug, how can precisely 2 gallons be put into the 5-gallon jug? The conditions for this problem are the same as those in (a).

(c) Given a 5-gallon jug filled with water and an empty 2-gallon jug, how can precisely 1 gallon be obtained in the 2-gallon jug? In this problem, water may be either discarded or poured from one jug into another, but there is no source of water other than the initial 5 gallons. Again, the jugs themselves are the only measuring devices to be used.