The Importance of Problem Decomposition

This is my very first attempt at blogging. I hope I am not too bad.

For my first blog ever, I am choosing a topic that I believe is very important for all students and not just those majoring in Computer Sciences, Software Engineering, etc. Even entry-level professionals might benefit from the contents of this blog. At least, that's what I hope. That said, the example I am using in my blog was the result of a practical exercise I gave my Computer Sciences students a few days ago.

I have been teaching part time since 2008. Since I started teaching, I am noticing a trend that alarms me a great deal. It seems to me that students nowadays either lack effective problem solving skills or completely undermine the importance of effective problem solving. In fact, I have even notice this trend on exceptional students.

I hope that my effort in shedding some light in the subject is futile. Therefore, I ask of you to leave feedback, positive or negative, once you finish reading this blog. I assigned my students a problem from Y. Daniel Liang's book, Introduction to Java™ Programming (8th Edition), in which they had to generate a software solution to display a sequence of numbers in the following matter:

                                       1
                                  1    2    1
                             1    2    4    2    1
                        1    2    4    8    4    2    1
                   1    2    4    8   16    8    4    2    1
              1    2    4    8   16   32   16    8    4    2    1
         1    2    4    8   16   32   64   32   16    8    4    2    1
    1    2    4    8   16   32   64  128   64   32   16    8    4    2    1

FIGURE 1

On the surface, this problem seems simple; especially for the seasoned professional.  However, often we rushed to judgement and start generating solutions without really understanding the problem.  The number one rule of problem solving is to seek to understand the problem first.  This seems pointless to mention, but experience has shown me that the reason why dedicated students fail to come up with effective solutions to problems is because they started on this task without gaining a true understanding of the problem at hand.

One technique to effectively understand problems is called "Problem Decomposition."  This is a process where a big problem is broken down into smaller, more manageable problems.  The idea behind Problem Decomposition is that once you truly understand each individual sub-problem and generate effective solutions for each one independently, integrating the solutions should solve the bigger problem.  The best text I have found on this topic is Software Engineering Theory and Practice by Dr. Shari Lawrence Pfleeger.  Going back to the topic at hand, I will illustrate how this technique helps in generating an effective solution to the problem illustrated in Figure 1.

Initially, I broke down the problem into two parts:

1. Displaying the right numeric sequence, and
2. Aligning the numbers correctly (padding).

   Because padding is nothing more that printing out spaces, I decided to leave that problem for last and decided to solve the numeric sequencing part of the problem first. Since I decided to solve the numeric sequencing sub-problem, I decided transform the output shown in Figure 1 to fit my numeric sequencing sub-problem (without padding). The result is shown in Figure 2 below:
   
   

   
   1
   1  2  1
   1  2  4  2   1
   1  2  4  8   4   2   1
   1  2  4  8  16   8   4    2   1
   1  2  4  8  16  32  16    8   4   2   1
   1  2  4  8  16  32  64   32  16   8   4  2  1
   1  2  4  8  16  32  64  128  64  32  16  8  4  2  1
   

   FIGURE 2

   Having removed the padding from the original output allowed me to see this problem in a different light. However, this problem can be further decomposed. I can see that there are two numeric sequences:

   1. Numeric sequence in ascending order, and
   2. Numeric sequence in descending order.
   Since the ascending order sequence is displayed first, I will once again transform my output to include only this sub-problem. The result is shown in Figure 3 below:
   
   

   
   1
   1    2
   1    2    4
   1    2    4    8
   1    2    4    8   16
   1    2    4    8   16   32
   1    2    4    8   16   32   64
   1    2    4    8   16   32   64  128
   

   FIGURE 3

   The level of problem decomposition I have achieved now allows me to see this part of the problem much easier than before.  I can see now that, in order to display this numeric sequence, I need to implement some kind of nested loop.  The outer loop controls my rows and my inner loop controls the columns.  A structure such as the one below should provide the control I need to create new rows.
   
   

   
   for(int row = 1; row <=8; row++) {
     // TODO inner loop goes here
     System.out.println();
   }
   

   Now, I am ready to determine what my inner loop should do.  I know that the number of digits displayed is related to the number of rows (row 1 had one number, row 2 has two numbers, and so on).  I also see that the sequence is powers of two, where the index of the column equals the exponent value.  For example, in every row, the number in the first column (column index 0) is 1, or 2⁰.  Decomposing the original problem down to this level has allowed me to easily determine that an effective solution to this sub-problem, can be something like the code snippet below:
   
   

   
   for(int row = 1; row <=8; row++) {
     for(int column = 0; column <=row; column++) {
       System.out.print((int)Math.pow(2, column)); //I am ignoring the padding for now
     }
     System.out.println();
   }
   

   By analyzing the code above, you can see that I have addressed the two main points I discovered:

   1. The sequence displayed is powers of two. For this, I used the Java Math.pow method. This method takes two arguments; base and exponent. The base is just a literal constant and the exponent is the current column index location, just as I determined during my problem analysis.
   
   
   2. I am using the current row's index value to determine how many iterations I am going to have for each row. This is because I established a relationship between the number of columns displayed in each row and the row number. I am also sticking to my plan not to worry about number alignment or padding until it is time to address that part of the problem.
   
   Until now, everything had gone smoothly. But as it is often the case, our first solution might not be correct, or as effective as we had hoped. Once I execute the code above, I obtained the output shown below in Figure 4:
   
   

   
   12
   124
   1248
   124816
   12481632
   1248163264
   1248163264128
   

   FIGURE 4

   I am missing the first row.  This is an indication that my initial index location is off.  I can now refine my code much easier since I only have one simple problem to solve, rather than a bunch of  integrated sub-problems. Initializing my row counter variable with zero instead of one, and changing my row limit to seven instead of eight does the trick.  However, my goal is to create a solution that looks like Figure 3 and not like Figure 4.  At this point, I decided to add temporary padding to align the numbers so that my output looks like what I expect to see.
   
   

   
   for(int row = 0; row <=7; row++) {
     for(int column = 0; column <=row; column++) {
       System.out.print((int)Math.pow(2, column)); //This is not the final padding
     }
     System.out.println();
   }
   

   Changing my solution to start at index 0 instead of 1 is a code refinement made so that the solution for this sub-problem displays exactly as expected.  Now, my output looks exactly like Figure 3, and the sub-problem regarding displaying a numeric sequence in ascending order is solved!  I can now attempt to solve the next sub-problem which is displaying a identical numeric sequence, in the same row, in descending order.  How can this be done?  Simple.  Because the descending order sequence starts immediately after the ascending order concludes AND because it is displayed in the same row, it means that I need another looping mechanism following the one I created to solve the first sub-problem.  In fact, because they are so similar, I could use a similar structure with slight modifications and I should be able to solve this particular sub-problem.

   Analyzing Figure 2, I realized that the descending numeric sequence does not start with the largest number obtained from the ascending order sequence.  For example, the third row's values are 1 2 4 2 1.  This means that the initial value of the descending order sequence is one less than the current row index value.  Because my sequence is descending this means that my counter variable for that loop must also be decreasing at the same rate.  Lastly, the number being displayed is still a power of 2 relative to the current column index location.  For this part of the problem, the columns are arranged in descending order.  With that, I came up with the solution shown below:
   
   

   
   for(int row = 0; row <= 7; row++) {
     // Display ascending sequence
     for(int column = 0; column <=row; column++) {
       System.out.print((int)Math.pow(2, column)); //This is not the final padding
     }
     // Display descending sequence
     for(int column = row - 1; column>=0; column--) {
       System.out.print((int)Math.pow(2, column) + "  " ); //This is not the final padding
     }
     System.out.println();
   }
   

   The descending sequence code displays an output basically identical to the one shown in Figure 2.  Therefore, another sub-problem has been solved!  All there is left to be solved is the padding sub-problem.  Once this is resolved, the entire solution should be solved.

   I want to emphasize that, before I integrated the descending numeric sequence code with the ascending numeric sequence, I tried it in isolation by commenting my previous code out.  Once I was satisfied with my solution to that sub-problem, I integrated it to my previous solution without any issues.  That said, for problems more complex than my example, it is often the case that further refinement, tuning, etc must take place in order to integrate solutions in order for them to work.  I want to make that point clear.  Nevertheless, the issue that cannot be ignored is the fact that Problem Decomposition allows us to generate solutions much faster and much more effective than pure "Brute Force."  Understand that I am not totally dismissing Brute Force as a technique for developing software.  Rapid prototyping might be one of those cases where Brute Force might be the way to go.  But, the topic of this blog is to get in the habit of using other techniques to effectively solve problems.  I really hope that by now, you agree with me; even if it is up to a certain extent.

   The last part of the problem is to come up with a padding scheme that will make my output look like the output illustrated in Figure 1.  Once I started analyzing the alignment, I noticed that the number are right justified.  When looking at the middle "column" of Figure 1, we see the following:
   
   

   
     1
     2
     4
     8
    16
    32
    64
   128
   

   Common sense tells me that in order to align the top "1" with the "128", I must pad the "1" with two leading spaces.  In fact, this is true for any single-digit number.  Aligning two-digit number only require a single leading space.  However, I must also pad the "128" in order to get some separation between it and the previous number (64).  I determined that two leading spaces should be sufficient.  Therefore, I can derive the following logic from my decision:  If a number is three-digits in size, pad it with two leading spaces.  Otherwise, if the number is two-digits in size, pad it with three leading spaces.  Lastly, if the number is a single digit, pad it with four leading spaces.  However, what of the "columns" with no numbers?  The logic above allows me to determine that any given "column" is composed of 5 positions as shown below:

   A column containing a one digit number: 4 spaces + number
   A column containing a two digit number: 3 spaces + number
   A column containing a three digit number: 2 spaces + number

   This forces me to refine my code once again.  I can see that wherever I am resolving for a number to be displayed, I must pad first, then display the value.  Previously, I was doing the opposite.  The result of my code refinement looks like the code snippet below:
   
   

   
   for(int row = 0; row <=7; row++) {
     // Display ascending sequence
     for(int column = 0; column <=row; column++) {
       int number = (int)Math.pow(2, column);
       if( number >= 100 ) // Number is 3 digits
       {
         System.out.print("  " + number); // 2 spaces + number
       }
       else if ( number >= 10 ) // Number is 2 digits
       {
         System.out.print("   " + number); // 3 spaces + number
       }
       else // number is 1 digit
       {
         System.out.print("    " + number); // 4 spaces + number
       }
     }
   
     // Display descending sequence
     for(int column = row - 1; column >= 0; column--)  {
       int number = (int)Math.pow(2, column);
       if( number >= 100 ) // Number is 3 digits
       {
         System.out.print("  " + number); // 2 spaces + number
       }
       else if ( number >= 10 ) // Number is 2 digits
       {
         System.out.print("   " + number); // 3 spaces + number
       }
       else // number is 1 digit
       {
         System.out.print("    " + number); // 4 spaces + number
       }
     }
     System.out.println();
   }
   

   
   
   It is worth pointing out that the solutions inside each of the inner for loops are not the most effective, but it works well for this problem since we are bound to display powers of two from 1 to 128 (2⁰ to 2⁷).  In order to perfectly align digits, we must pad empty columns with spaces which result in the same column width as columns with numbers.  We already determined that the column width is 5.  Therefore, "empty" columns must be padded with 5 spaces.  And, these columns precede any numeric columns; which means another loop structure before we display any numbers.  Also, the number of empty columns is inversely proportional to the number of columns containing numbers.  For example, the first row has one numeric column and many empty columns.  As we move to the next row, we notice that the number of empty columns have decreased by the same number of new numeric columns added.  Therefore, a structure such as the one below should provide the necessary padding for empty colums:
   
   

   
   // Default padding
   for(int column = 1; column <= 7 - row; column++) {
     System.out.print("     "); // Pad empty columns with 5 spaces
   }
   

   Because this "default padding" must precede insertion of any numeric column, I must add the previous code snippet as the first process inside my row controlling looping structure as shown below:
   
   

   
   for(int row = 0; row <=7; row++) {
     // Default padding
     for(int column = 1; column <= 7 - row; column++) {
       System.out.print("     "); // Pad empty columns with 5 spaces
     }
   
     // Display ascending sequence
     for(int column = 0; column <=row; column++) {
       int number = (int)Math.pow(2, column);
       if( number >= 100 ) // Number is 3 digits
       {
         System.out.print("  " + number); // 2 spaces + number
       }
       else if ( number >= 10 ) // Number is 2 digits
       {
         System.out.print("   " + number); // 3 spaces + number
       }
       else // number is 1 digit
       {
         System.out.print("    " + number); // 4 spaces + number
       }
     }
   
     // Display descending sequence
     for(int column = row - 1; column >= 0; column--)
     {
       int number = (int)Math.pow(2, column);
       if( number >= 100 ) // Number is 3 digits
       {
         System.out.print("  " + number); // 2 spaces + number
       }
       else if ( number >= 10 ) // Number is 2 digits
       {
         System.out.print("   " + number); // 3 spaces + number
       }
       else // number is 1 digit
       {
         System.out.print("    " + number); // 4 spaces + number
       }
     }
     System.out.println();
   }
   

   
   
   At this point, our problem is solved!  Executing the code snippet above should display an output similar to the one illustrated in Figure 1.  But, there is one more step that should be taken to make this solution more elegant are more readable.  The code inside the numeric sequence loops is identical.  Therefore, it should be extracted out into a method.
   
   

   
   public class Problem4_19 {
     public static void main(String[] args) {
       for (int row = 0; row <= 7; row++) {
         // Default padding
         for (int column = 1; column <= 7 - row; column++) {
           System.out.print("     "); // Pad empty columns with 5 spaces
         }
   
        // Display ascending sequence
        for (int column = 0; column <= row; column++) {
          alignNumber(column);
        }
   
       // Display descending sequence
       for (int column = row - 1; column >= 0; column--) {
         alignNumber(column);
       }
   
       System.out.println();
       }
     }
   
     private static void alignNumber(int column) {
       int number = (int) Math.pow(2, column);
       if (number >= 100) // Number is 3 digits
       {
         System.out.print("  " + number); // 2 spaces + number
       }
       else if (number >= 10) // Number is 2 digits
       {
         System.out.print("   " + number); // 3 spaces + number
       }
       else  // number is 1 digit
       {
         System.out.print("    " + number); // 4 spaces + number
       }
     }
   }
   

   Executing the code above results in an output exactly as the one shown in Figure 1.  I believe I have effectively demonstrated the benefits of using Problem Decomposition to solve complex problems (even though some of you think this problem was too easy).  I have to go back again to my experience teaching, and even my experience as an experienced professional.  I often see people jumping into coding without fully understanding the problem that needs to be solved.  The overwhelming majority of the time, this results in time and money wasted, and, in some cases, this also results in a solution that partially works; which can be extremely dangerous for safety-critical systems.

   This concludes my first blog.  I hope I was able to explain Problem Decomposition in a manner that was both systematic and easy to follow.  Please, leave me some feedback if you found this useful or not.  I wish to do this more often and I need your help to get better at it.

   Thank you!