Algorithmic Thinking with Python. Decrease and Conquer Strategy

This article is about computational thinking. Before we dive in though, check out this puzzle:

The Ferrying Soldiers Puzzle

A troop of 20 soldiers must cross a river with with no bridge. There are two boys playing in a small by the shore. The boat is only large enough to carry a single soldier or two boys.

How can the soldiers all get across the river, leaving the two boys in the boat on the same side as they started? Work out the minimum number of crossings that the boat must make.

You can try this puzzle out for yourself in the trinket below. I will give the solution later on in this article.

The Decrease and Conquer Problem Solving Strategy

Decrease and Conquer is a computational problem solving technique which takes a problem and reduces it to a smaller problem which is easier to solve. Sometimes this is confused with Divide and Conquer which is similar, but which breaks up a problem into multiple smaller problems. For comparison, Merge Sort and Quicksort are examples of divide and conquer algorithms.

Classic examples of Decrease and Conquer are:

  • Binary Search
  • Euclid’s algorithm
  • Depth-First Search
  • Breadth-First Search
  • Insertion Sort and Selection Sort

For example, in Binary Search, the search space is decreased by a factor of 2 at each step, leading to a very efficient algorithm (with a time complexity of O(log n)). In the case of Euclid’s Algorithm for finding the greatest common divisor of two integers, the larger number is divided by the smaller at each step and the algorithm repeats using the smaller number and the remainder of the previous division. For insertion sort, the size of the unsorted section of data is decreased at each step.

There are different categories of amounts that an original problem is decreased by in a Decrease and Conquer algorithm. However for all of them the basic principle holds:

At each step of the algorithm, the problem is reduced to a smaller version of the same problem, until a solution is found (or found not to be possible).

The categories for the amount of decrease are:

Decrease by a constant

This is often by a constant of one.

Examples:

  • Insertion sort
  • Graph search algorithms: DFS, BFS

Decrease by a constant factor

Most commonly by a factor of two, as in Binary Search

Examples:

  • Binary search
  • Fake-coin problems
  • “Russian peasant multiplication”

Variable size decrease

A classic example here would be the Euclidean Algorithm, where the amount of decrease depends on the values given.

Solution to the Ferrying Soldiers Puzzle

And now for the moment you have all been waiting for, the solution to the Ferrying Soldiers Puzzle.

First, the two boys must row the boat to the other side, after which one of them returns with the boat. Then a single soldier rows the boat to the other side and stays there while the other boy returns the boat. These four trips reduce the problem size by 1 (described by the number of soldiers needing to cross the river). Thus, if this four-trip procedure is repeated a total of 20 times, the problem will be solved after the total of 80 trips. For the general instance of n soldiers, 4n trips will need to be made.

How did you do? Did you get the same result?

The Ferrying Soldiers Puzzle provides a great illustration of the Decrease and Conquer strategy for solving computational problems.

Python Listing for the Ferrying Soldiers Puzzle

For your reference, here is a Python 3 version of the Ferrying Soldiers Puzzle

Happy computing!

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Join our mailing list

Join our mailing list to receive awesome articles about learning Python and Computer Science in a fun and accessible way, straight to your inbox.

 Take your Python skills to the next level!

with our free email course on object oriented programming with Python