Algorithmic Problems

Algorithmic Problems

There are some principles and techniques for constructing algorithms. We usually say that a problem is algorithmic in nature when its solution involves the construction of an algorithm. Some types of problems can be immediately recognized as algorithmic.

Example 6.2. Consider the well-known Goat, grass and wolf problem: A farmer wishes to take a goat, a grass bundle and a wolf across a river. However, his boat can take only one of them at a time. So several trips are necessary across the river. Moreover, the goat should not be left alone with the grass (otherwise, the goat would eat the grass), and the wolf should not be left alone with the goat (otherwise, the wolf would eat the goat). How can the farmer achieve the task? Initially, we assume that all the four are at the same side of the river, and finally, all the four must be in the opposite side. The farmer must be in the boat when crossing the river. A solution consists of a sequence of instructions indicating who or what should cross. Therefore, this is an algorithmic problem. Instructions may be like.

Let the farmer cross with the wolf.

Or

Let the farmer cross alone.

However, some algorithmic problems do not require us to construct algorithms. Instead, an algorithm is provided and we are required to prove some of its properties.

Example 6.3. Consider The Chameleons of Chromeland problem: On the island of Chromeland there are three different types of chameleons: red chameleons, green chameleons, and blue chameleons. Whenever two chameleons of different colors meet, they both change color to the third color. For which number of red, green and blue chameleons is it possible to arrange a series of meetings that results in all the chameleons displaying the same color? This is an algorithmic problem, because there is an algorithm to arrange meetings between chameleons. Using some properties of the algorithm, we can find out for which initial number of chameleons, the goal is possible.