Reduction

Reduction are to algorithms what using libraries are to programming. You might not have seen reduction formally before but it is an important tool that you will need in CSE 331.

Thanks to Anna Gilbert and Martin Strauss for suggesting this example.
You may assume that your container is such that the RapidGrowers can continue replicating every second till you come back to Buffalo.
In other words, we will cast the given problem into a problem for which we know the solution and then directly appeal to the previously known solution. In the present case the reduction is just a matter of changing the language: in later problems in the course, you will have to do more work in the reduction.
Technically, you should prove this claim by induction too but here you can make this claim without a formal proof. In general, you will have to make such decisions at many points while writing your HW solutions. If you are not sure, take the conservative approach. That is, in the present case, go ahead and present the formal proof by induction.

Background

This is a trick that you might not have seen explicitly before. However, this is one trick that you have used many times: it is one of the pillars of computer science. In a nutshell, reduction is a process where you change the problem you want to solve to a problem that you already know how to solve and then use the known solution. Let us begin with a concrete non-proof examples.

Example of a Reduction

We begin with an elephant joke . There are many variants of this joke. The following one is adapted from this one .¹

Question 1 How do you stop a rampaging blue elephant?
Answer 1 You shoot it with a blue-elephant tranquilizer gun.

Question 2 How do you stop a rampaging red elephant?
Answer 2 You hold the red elephant's trunk till it turns blue. Then apply Answer 1.

Question 3 How do you stop a rampaging yellow elephant?
Answer 3 Make sure you run faster than the elephant long enough so that it turns red. Then Apply Answer 2.

In the above both Answers 2 and 3 are reductions. For example, in Answer 2, you do some work (in this case holding the elephant's trunk: in this course this work will be a mathematical argument) to change Question 2 in a way so that you can map it to Question 1. Once you have the mapping, then you use the known Answer 1 to Question 1 to arrive at Answer 2 for Question 2.

When folks actually tell this joke, they do not say apply Answer 1: they spell it out but as CSE folks we know we should just call existing functions instead of re-writing the function in full when we need it. This actually also points to where you have been using reductions when you program: whenever you use a library function, you are essentially doing reduction. Say in your program you need to sort numbers, then you just call a sorting routine from the library. The sequence of steps by which you went from your original problem to the point where you need to sort the numbers is the reduction in this case. Typically, this is not the end of the story since you might have to write more code to use the result of sorting to obtain the final desired output. Similarly, for general reductions, just using the solution to a known problem might not be enough: you might have to do some "post-processing" to convert the known solution into a format that is suitable for your problem. (In the elephant joke above, there is no need for post-processing.)

A more formal example

We now present a more mathematical example for reduction. In fact, we are just going to re-use Sample question from Homework 0.

Exercise 1

Deep in the Pacific ocean you discover the RapidGrowers bacteria. These are single cell organism that divide themselves into two (identical) organisms/cells in one second. When you start going back to the surface you store one organism in a special container that exactly replicates their habitat. From the moment you put the organism in, it takes you $s$ seconds to come back to Buffalo to find your container bursting at its seams.²

Prove or disprove the following:

There are $2^s$ RapidGrowers in your container.

Proof Idea

There are two ways of solving this problem. (See Homework 0 for the induction based proof.)

We begin with the approach of reducing the given problem to a problem you have seen earlier.³ Build the following complete binary tree: every internal node in the tree represents a "parent" RapidGrower while its two children are the two RapidGrowers it divides itself into. After $s$ seconds this tree will have height $s$ and the number of RapidGrowers in the container after $s$ seconds is the number of leaf nodes these complete binary tree has, which we know is $2^s$. Hence, the claim is correct.

Proof Details

Consider the complete binary tree with height $s$ and call it $T(s)$. Further, note that one can construct $T(s+1)$ from $T(s)$ by attaching two children nodes to all the leaves in $T(s)$. Notice that the newly added children are the leaves of $T(s+1)$. Now assign the root of $T(0)$ as the original RapidGrower in the container. Further, for any internal node in $T(s)$ ($s\ge 0$), assign its two children to the two RapidGrowers it divides itself into. Then note that there is a one to one correspondence between the RapidGrowers after $s$ seconds and the leaves of $T(s)$.⁴ Then we use the well-known fact (cite your 191/250 book here with the exact place where one can find this fact): $T(s)$ has $2^s$ leaves, which means that the number of RapidGrowers in the container after $s$ seconds is $2^s$, which means that the claim is correct.