Introduction to Problem Solving

Learning Objectives

At the end of this sub-unit, students should

• know the meaning of programming problem.
• know the basic of problem solving steps.

What is a Programming Problem

A programming problem is typically presented as the following information.

1. Problem Description.
2. Input-Output Pairs.

To solve the programming problem, we need to write a program such that if we pass the input to the program, then program will produce the output such that the output satisfies the problem description. We do not normally care how the solution is derived, as long as a solution is given. Then, using the solution code, we can provide the output for any given valid input.

Take for instance, the "problem" of brewing a coffee.

• Input: Coffee beans.
• Output: A cup of coffee.
• Problem Description: It must be a nice and hot cup of coffee.

Our task is to provide the steps to transform any "coffee beans" into "a cup of coffee". We can then specify the steps as follows.

1. Prepare the coffee.
2. Pour the coffee.
3. Serve the coffee.

Unfortunately, our computer is not as smart as you. It cannot understand the meaning of "prepare", "pour", and "serve". However, a computer is very precise and it will do what we asked of it without getting bored.

So we must "talk" in the "language" that a computer can understand. That language is the programming language. In our case, that is the Python programming language. We have to know the capability of Python before we can ask a computer to solve the problem using the language of Python.

Even then, we still have to precise and very specific in our instruction. If the computer cannot understand "prepare" but it can understand the more specific instruction of "boil", "grind", and "brew", then we have to make our instruction more specific.

1. Boil a pot of water into hot water.
2. Grind the coffee bean into ground coffee.
3. Brew the ground coffee bean by pouring the hot water into the ground coffee and produce a pot of hot coffee.
4. Pour the hot coffee into a cup.
5. Serve the hot coffee in the cup.

Programming Context

In the context of programming, we had several ways to describe a programming problem. One of the most common way to describe a programming problem is to describe the input is the user input. This is typically from keyboard or from a file. The output is simply the output to be displayed on a computer (e.g., via print).

Now that we know about functions, we can describe the input as the argument to a function. The output is naturally the return value from the function. In both cases, the problem description is typically going to be a mix of informal English description or a more precise mathematical description. We have to familiarize ourselves with both.

A good programming problem will also specify the assumptions and the restrictions. Assumptions describe what are considered valid inputs while the restrictions describe some conditions that cannot be violated. As you learn more programming concepts, restrictions such as run-time may be imposed. For now, we simply want to have a correct program with reasonable run-time¹.

So far, we have written our programming exercises by assuming a variable is initialized. Going forward, we will specify the function to be implemented. This means that we will be using the input argument and return value as our description of input-output pairs.

Pólya Problem Solving Process

You may have learnt about the Pólya problem solving process invented by George Pólya. The steps are listed below.

1. Understand the problem.
2. Formulate the plan.
3. Carry out the plan.
4. Reflect on the plan.

Unfortunately, the steps are intended for mathematical problems. It is not exactly suitable for programming problem because the "plan" is generally what we have to produce. Our problem may not be as specific as finding the root of \(x^2 + 5x + 6\) but can be the more general problem of finding the root of any quadratic equation of the form \(ax^2 + bx + c\).

So we cannot just carry out our plan with a single value. Instead, we need to carry out our plan with many values and we have to check that it is correct for all of them. So to update the Pólya problem solving process, we may need to expand on step 4 and split it into testing and analyzing our solution. Additionally, if we take a more general view of the "plan" not as a program but as how we are going to write the program, then we can adapt Pólya problem solving process for programming problem as follow.

1. Understand the problem.

2. Design your solution.

3. Write your program.

4. Test your program.

5. Analyze your solution.

These are the steps that needs to be done during the problem solving process. Note that the steps are not linear. If there are problems encountered in Step 4 and Step 5, we should go back to the beginning. This is repeated until we are confident with out solution or until time is running out (e.g., end of assessment). In which case, we submit our best solution.

We would like to add two additional steps to be done after solving a problem to help with solving future problems.

6. Generalize your solution.

7. Record to pattern bank.

We will explain the usage of the last two steps in future sub-unit. For now, we will show some potential work to be done for each step. These are intended to be rather general and may not be applicable to all problems.

Understanding the Problem

To understand the problem, we will need to focus our attention to the important description on the question. These are typically the keywords in the problem descriptions. If possible, you might want to highlight the key terms.

Additionally, if sample runs are given, then we have at least possible input-output pairs to work with. We need to roughly understand how the output is related to the input. At this point, we do not have to know how to actually solve the problem. Take for instance, the problem of counting the number of digits in a positive number. Without knowing how to write a function to solve this, we can figure out how the output can be obtained from the input. Often, this rough understanding is still useful.

To make the rough understanding more concrete, we also recommend creating our own input-output pairs. If we can construct our own input-output pairs, it means our understanding of the problem is more concrete than before.

At this point, we should have quite a number of test cases. Given these test cases, we want to categorize the test cases. The way we categorize the test cases depends on our knowledge of the problem. But there are some general categories of test cases according to the data type.

Data Type	Categories
Boolean	True / False
Integer/Float	Positive / Zero / Negative
Integer	Even / Odd (can be generalized to other remainders)
Integer	Prime / Composite

To illustrate, consider the simple problem of classifying the input integet into either even or odd. We may have the following test cases already given.

Input	Output
1	False
2	True
3	False
100	True

Now it is time to add more test cases. At first, we may just add our own test cases that continues from 3. Then we try to classify the test cases. Obviously, classifying as even / odd is not useful as it is what we are trying to solve. But we can use the positive / zero / negative classification and found that we only have positive number input. So we add more test cases from the other categories.

Our Own Test CasesCategorization

Input	Output
1	False
2	True
3	False
100	True
4	True
5	False

Input	Output	Categories
1	False	Positive
2	True	Positive
3	False	Positive
100	True	Positive
4	True	Positive
5	False	Positive
0	True	Zero
-1	False	Negative
-2	True	Negative

Design Your Solution

There are many different ways to design our solutions. In the explanation of the behavior of if-statement and while-loop, we show one possible way of designing which is using flowchart. Below is an example of a design for the problem of checking if a number is even or odd.

However, this is not the only way. As such, we will not restrict how you design your solution. But as a good practice, your design should be simpler than a program. Usually, the design will not be as clear as that. Below is an example of a design for the Collatz conjecture simulation.

Remember our tips on invention notation? You may want to invent some notations in this step. This assumes that the design is not part of the submission.

Typically, for a 1 hour assessment, we should spend around 15 minutes to design. During the design, we should think about the ways our design may break. This will guide us towards better solutions. The time spent designing will be shorter than the time spent fixing codes.

Quote

"There has never been an unexpectedly short debugging period in the history of computers."

Steven Levy

So invest your time well, do not start typing immediately when you see a problem. It will also help to find the "obvious" solution first. By using the most obvious solution, it will be likely that your solution is correct. Try not to be clever in formulating the solution as your first attempt. Of course what is obvious for one person may not be obvious for another. Therefore, it will also helps greatly to improve your general mathematical skill.

Quote

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

Donald Knuth

Quote

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it."

Brian Kernighan

Quote

"If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with."

Edsger Dijkstra

Write Your Program

The next step is to translate your design into Python code. But before we do that, we need to ensure that the design is clear. Since there are many ways to design a program², at the very least, the design should be clear to us.

In this step, we need to ask ourselves about the Python construct to use. Consider the even or odd problem again. We came up with a flowchart that has a diamond. But a diamond can mean an if-statement or a while-loop. Which one do we mean?

Additionally, the condition is "is n divisible by 2?" which is not precise. How do we check for divisibility? Once we have answered these questions, we may come up with an annotated flowchart shown below.

Once the design is clear, the remaining task is to actually type the solution.

Is Even?

def is_even(n):
  if n % 2 == 0:
    return True
  else:
    return False

A simpler alternative is the following.

def is_even(n):
  return n % 2 == 0

At this point, your typing skill should matter more than your designing skill. It is always good to practice typing so that

• you can type very quickly, and
• you can type correctly.

Mistakes during typing is common but it is important to quickly realize when mistakes occur. Some common technique to avoid potential mistakes are listed below.

• Write comments before codes. The comments may come from the design. This way, you can also quickly check if the code match the comment.

• Write stubs or placeholder codes. This way, you can observe the overall code structure before writing details.

  def is_even(n):
    pass
    # check if n is divisible by 2
    # this is a stub
  

• Close parentheses (or other brackets) before writing the content. This ensures that all brackets are matched, especially for function calls with lots of chaining.

Furthermore, since we are already typing, we should also typed our own additional test cases from the first step. To avoid manual checking of the correctness of the answer by eye-balling, we recommend testing for equality with the expected answer.

BadGoodBetter

Bad Test Case

print(is_even(-2))  # True
print(is_even(-1))  # False
print(is_even(0))   # True
print(is_even(1))   # False
print(is_even(2))   # True

Good Test Case

print(is_even(-2) == True )
print(is_even(-1) == False)
print(is_even(0)  == True )
print(is_even(1)  == False)
print(is_even(2)  == True )

Better Test Case

print("is_even(-2)", is_even(-2) == True )
print("is_even(-1)", is_even(-1) == False)
print("is_even(0)" , is_even(0)  == True )
print("is_even(1)" , is_even(1)  == False)
print("is_even(2)" , is_even(2)  == True )

With the bad test cases we need to look at both the output and the comments. Even worse will be if there is no comment to check the answer with. This can be improved by automatically checking with equality operator ==. What we need to do is then only to check if any output is False because we expect all of it to be True.

But it is still not the best because if there is an output that is False, we need to locate the cause by matching the output to the code. As an improvement, we can also print the code we are testing. This way, if we found a False output, we immediately know the input corresponding to this output.

More importantly, it is critical that we write the test cases correctly. The aim of the test cases is to check for mistakes, they should not have mistakes themselves.

Test Your Program

This step is straightforward once you have correctly code the test cases. Simply execute the program --which can be as simple as pressing F5-- and check the output. If all the test cases pass, that is great, we can continue to the next step. Otherwise, understand the cause of the problem and repeat from Step 1 with this additional knowledge.

There are many ways to find the cause of the problem. We did recommend the use of comments to guide through the thinking process. This will also help in testing and understanding the program when problem occurs. However, no debugging technique is more general than simply printing the values at important locations to check their values.

Quote

"The most effective debugging tool is still careful thought, coupled with judiciously placed print statements."

Brian Kernighan

Alternatively, we may want to come up with more test cases if we have the time. This may uncover more problems with our code.

Analyze Your Solution

This step involve careful analysis of programs. The technique we will be introducing is called white-box testing. White-box testing requires us to look at the code and scrutinize every aspect of it. What we need to do is to uncover potential problems related to the code or the structure of the code. Problems may be an actual hidden error (i.e., error for which we have no test case for it yet) or bad practices.

Some common technique to look for potential problems include the following.

• Identify redundant codes (e.g., duplicated code).

  Redundant codes are prone to mistakes even if they are duplicated via copy-and-paste. There may be more mistakes if we actually type twice, but even with copy pasting, mistakes may occur. Even worse, if it contains error, then we have to perform correction on several places.

• Identify and justify constant values.

  Some constant values are justifiable For instance, when checking if a number is even or odd, we cannot escape using the constant 2 and 0. Not using 2 or 0 may lead to an overly complicated solution. However, using the constant 10 for checking even or odd may not be justifiable.

• Cover all branches.

  Often, we want to know that all parts of the program is correct. However, some parts of the program may not be executed given the test case that we have. In such cases, we want to add new test cases to force our code to execute certain lines. Unfortunately, finding such input may not be trivial.

There are still yet other techniques we have not mentioned. After all, this is still an active area of reasearch. But note that when analyzing the code and trying to find an example that may break our code, we need to ensure that the input is within the specification (i.e., within the assumption of valid input). We have to play the Devil's advocate, but even the Devil has to play by the rules.

Quote

"Discovering the unexpected is more important than confirming the known."

George E.P. Box

Generalize Your Solution

The idea of generalizing the solution is to find common patterns from multiple solutions. It can also be done by looking at a single code and finding the possible ways it can be used to solve slightly different problem. We did this by generalizing our mystery function into summation function using function.

While generalizing using function is good, it may be more difficult to think about. A simpler approach is to literally add blanks on parts of the code. We can say that a code with blanks to be filled in as called a "programming pattern".

Programming Pattern

A programming pattern is a code such that parts of the code is left blank to be filled in with specific instructions to solve a new problem.

Take our transformation from mystery to summation again. We can illustrate this with blanks instead of function call.

• Mystery Function

  ---

  def mystery(x, n):
    y, i = 0, 0
    while i <= n:
      y = y + (x ** i) / fn(i)
      i = i + 1
    return y
  

• Abstraction with Function

  ---

  def summation(x, n):
    y, i = 0, 0
    while i <= n:
      y = y + f(i)
      i = i + 1
    return y
  

• Abstraction with Blank

  ---

  def summation(x, n):
    y, i = 0, 0
    while i <= n:
      y = y + ░░░░░
      i = i + 1
    return y
  

• Further Abstraction

  ---

  def accumulation(x, n):
    y, i = ░, 0
    while i <= n:
      y = y ░ ░░░░░
      i = i + 1
    return y
  

In "Abstraction with Blank", we leave the second operand of the addition blank. This can be filled in any values we want. So, in a way, this is equivalent to abstraction with function. We can extend this abstraction further to not only abstracting the value but also the operation. For instance, we may change the + into *. Then, using the appropiate value, we can also solve factorial with this.

So using generalization with blanks, we can prepare ourselves to solve future problems. Since the structure is somewhat fixed, we can focus our energy and effort to fill in the blank to solve new problems. At the same time, because the code structure is somewhat fixed, there will still be certain problems we cannot solve with this. So more blanks may be needed.

However, it is very easy to get carried away with generalizing our code that the code becomes so general it has practically no structure. When that happens, our programming pattern is no longer useful because for each blank, we need to fill that in with the actual code. We call this over-generalization.

• Over-Generalized #1

  ---

  def iteration(x, n):
    ░░░░░░░░░░░░░
    while ░░░░░░░:
      ░░░░░░░░░░░░░░░░░░░░░░
      ░░░░░░░░░░░░░░░░░░░░░░
    return ░
  

• Over-Generalized #2

  ---

  def five_statements(x, n):
    ░░░░░░░░░░░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░░░░░░░░░░
  

Although having a more general pattern means that the pattern can be used to solve more problem (i.e., more general), using it is more difficult because of the lack of structure. Take for instance the five_statements function. It can be used as a template for factorial, summation, or even making coffee (i.e., the five steps are: boil, grind, brew, pour, and serve). So we need to find a balance between generality and usability.

Record to Pattern Bank

Finally, the last step is to maintain a collection of programming patterns obtained from the generalization above. We call this collection of programming patterns as "pattern bank". Even at the level of International Collegiate Programming Contest (ICPC), the teams have what they call as team notebook³⁴.

This pattern bank should be like a recipe book for chef. It should contain details but also some general idea. If we put different entries for chocolate cake and strawberry cake on our recipe book, we will quickly run out of space as well as our patience to search for a specific recipe.

But if the difference is only on the glazing, then we can leave it to the chef's need. The cake is the same whether we will be adding chocolate or strawberry glazing at the end. So we leave the recipe for the cake the same and let the glazing be the blanks.

As such, we would recommend storing the generalized solution from the previous step to avoid clutter. Additionally, it will be good to mention the kind of problems that can be solved by the pattern as well as the assumptions on the input.

More importantly, once you have a pattern bank, you should check the usefulness of the pattern bank. This can be done by trying to solve past problems using the idea from the pattern banks or even try it on future problems. Potentially, a ranking system can be made to select which patterns are to be kept and which are to be discarded. This is another way to avoid over-generalization or even under-generalization (i.e., simply storing the code for the mystery instead of generalizing it into summation or accumulation).

Lastly, do not be afraid of naming things. As we often think in terms of categories and names are convenient ways to categorize concepts into buckets. We may be able to quickly retrieve the relevant concepts simply by attaching a name to the concept. The name can be unique to each of us. But as a reminder, if a common name already exist, it is best to use that instead.

Problem Solving Techniques

There are some common techniques to solve programming problems. The list we show is not by any means exhaustive but will only serve as a sample. Some techniques will be subsumed by other more general techniques in this notes too.

1. Guess-and-Check
2. Connecting-the-Dots
3. Exploration
4. Programming Patterns

The third technique (i.e., exploration) is the most general technique we will explain in this notes. However, our expectation is that we will be solving problems using the fourth technique (i.e., programming patterns). The patterns should come from our own individual pattern banks. We will only list the basic patterns and leave further generalization or other patterns up to your imagination.

The techniques are used on the first two steps of problem solving process (i.e., understanding the problem and designing your solution). When encountering a new problem, our task will be to figure out which technique is applicable based on our understanding of the problem and then apply the design to our solution. Initially, we will show the 5 problem solving steps in greater details but as we progresses, we will skip some of them. Despite the note skipping the steps, you should attempt the missing steps on your own to further your understanding of the steps.

---

1. The meaning of reasonable is intentionally left vague. Your program should not compute the correct answer and then go into an infinite loop. What is reasonable is usually based on common sense and on the obvious solution. ↩

2. There are even more standard ways called UML diagram, but we will not go through that as it is as technical as explaining a new programming language. ↩

3. Team notebook from one of NUS team can be found here. ↩

4. Team notebook from one of Stanford team can be found here. ↩