COS 102-PROBLEM SOLVING

THE PROBLEM SOLVING PROCESS

Regardless of the area of study, computer science is all about solving problems with
computers. The problems that we want to solve can come from any real-world problem
or perhaps even from the abstract world. We need to have a standard systematic
approach to solving problems. Since we will be using computers to solve problems, it is
important to first understand the computer’s information processing model. The model
shown in Fig. 1-1 below assumes a single CPU (Central Processing Unit). Many
computers today have multiple CPUs, so it can be imagined the above model being
duplicated multiple times within the computer.

Storage/Network devices

1
A typical single CPU computer processes information as shown in the diagram.
Problems are solved using a computer by obtaining some kind of user input (e.g.,
keyboard/mouse information or game control movements), then processing the input
and producing some kind of output (e.g., images, text, sound). Sometimes the incoming
and outgoing data may be in the form of hard drives or network devices.

Computer as a model of computation

In regards to problem solving, we will apply the above model in that we will assume
that we are given some kind of input information that we need to work with in order to
produce some desired output as solution. However, the above model is quite simplified.
For larger and more complex problems, we need to iterate (i.e., repeat) the
input/process/output stages multiple times in sequence, producing intermediate results
along the way that solve part of our problem, but not necessarily the whole problem.
For simple computations, the above model is sufficient.

Since it is the “problem solving” part of the process that is the main focus in this unit,
more attention will be devoted to this. Among the many definitions for “problem
solving”, the following will be adopted in this unit:

Definition 1-1: Problem Solving is the sequential process of analysing information

related to a given situation and generating appropriate response options.

In solving a problem, there are some well-defined steps to be followed. For example,
consider how the input/process/output works on a simple problem:
Example: Calculate the average grade for all students in a class.
1. Input: get all the grades … possibly by typing them in via the keyboard or by
reading them from a USB flash drive or hard disk.
2. Process: add them all up and compute the average grade.
3. Output: output the answer to either the monitor, to the printer, to the USB flash
drive or hard disk … or a combination of any of these devices.
It is noted that the problem is easily solved by simply getting the input, computing
something and producing the output. We now examine the steps to problem solving
within the context of the above example.

2
Understand the Problem

It sounds strange, but the first step to solving any problem is to make sure that one
understands the problem about to be solved. One needs to know:
What input data/information is available?
▪ What does the data/information represent?
▪ In what format is the data/information?
▪ What is missing in the data provided?
▪ Does the person solving the problem have everything needed?
▪ What output information needs to be produced?
▪ In what format should the result be: text, picture, graph?
▪ What are the other requirements needed for computation?

In the example given above, it is understood that the input is a bunch of grades. But we
need to understand the format of the grades. Each grade might be a number from 0 to
100 or it may be a letter grade from A to F. If it is a number, the grade might be a
whole integer like 73 or it may be a real number like 73.42. We need to understand the
format of the grades in order to solve the problem.

We also need to consider missing grades. What if we do not have the grade for every
student: for instance, some were away during the test? Should we be able to include
that person in our average (i.e., they received 0) or ignore them when computing the
average? We also need to understand what the output should be. Again, there is a
formatting issue. Should the output be a whole or real number or a letter grade? Do we
want to display a pie chart with the average grade? The choice is ours.

Finally, one needs to understand the kind of processing that must be performed on the data.
This leads to the next step.

Formulating a Model

The next step is to understand the processing part of the problem. Many problems break
down into smaller problems that require some kind of simple mathematical
computations in order to process the data. In the example given, the average of the
incoming grades is to be computed. A model (or formula) is thus needed for computing
the average of a bunch of numbers. If there is no such “formula”, one must be

3
developed. Often, however, the problem breaks down into simple computations that is
well understood. Sometimes, one can look up certain formulas in a book or online if
there is a hitch.
In order to come up with a model, we need to fully understand the information
available to us. Assuming that the input data is a bunch of integers or real numbers
𝑥1, 𝑥2, ⋯ , 𝑥𝑛 representing a grade percentage, the following computational model
may apply:
𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 = (𝑥1 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛)/𝑛
where the result will be a number from 0 to 100.
That is very straight forward, assuming that the formula for computing the average of a
bunch of numbers is known. However, this approach will not work if the input data is a
set of letter grades like B-, C, A+, F, D-, etc., because addition and division cannot be
performed on the letters. This problem solving step must figure out a way to produce an
average from such letters. Thinking is required.

After some thought, we may decide to assign an integer number to the incoming letters as
follows:
𝐴+ = 12
𝐵+ = 9 𝐶+ = 6 𝐷+ = 3
= 11 𝐵 =8 𝐶 =5 =2 𝐹=0
𝐴 = 10
−
𝐵− = 7 𝐶− = 4 𝐷− = 1
If it is assumed that these newly assigned grade numbers are 𝑦1, 𝑦2, ⋯ , 𝑦𝑛, then the
following computational model may be used:
𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 = (𝑦1 + 𝑦2 + 𝑦3 + ⋯ + 𝑦𝑛)/𝑛
where the result will be a number from 0 to 12.

As for the output, if it is to be represented as a percentage, then 𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 can

either be used directly or one may use (𝐴𝑣𝑒𝑟𝑎𝑔𝑒2/12), depending on the input that
we had originally. If a letter grade is preferred as output, then one may need to use
(𝐴𝑣𝑒𝑟𝑎𝑔𝑒1/100 ∗ 12) or
(𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 ∗ 0.12) or 𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 and then map that to some kind of “lookup table”
that allows one to look up a grade letter according to a number from 0 to 12.

4
The main point to understand this step in the problems solving process is that it is all about
figuring out how to make use of the available data to compute an answer.

Develop an Algorithm

Having understood the problem and formulated a model, it is time to come up with a
precise plan of what the computer is expected to do.

Definition 1-2: Algorithm is a precise sequence of instructions for solving a problem.

Some of the more complex algorithms may be considered randomized algorithms or

nondeterministic algorithms where the instructions are not necessarily in sequence and
may not even have a finite number of instructions. However, the above definition will
apply for all algorithms that will be discussed in this course.

To develop an algorithm, the instructions must be represented in a way that is

understandable to a person who is trying to figure out the steps involved. Two
commonly used representations for an algorithm is by using (1) pseudo code, or (2)
flowcharts. Consider the following example for solving the problem of a broken lamp.
First is the example in a flowchart, and then in pseudocode.

Lamp not working

Lamp No
p lugged Plug in Lamp
in?

Yes

Bulb Yes
burned Replace Bulb
out?

No

Buy new Lamp

5
 Figure 1-2: Flowchart for a broken Lamp

Pseudocode
1. IF lamp works, go to step 7.
2. Check if lamp is plugged in.
3. IF not plugged in, plug in lamp.
4. Check if bulb is burnt out.
5. IF blub is burnt, replace bulb.

6. IF lamp doesn’t work buy new lamp.

7. Quit ... problem is solved.
Note: pseudocode is a simple and concise sequence of English-like instructions to solve a
problem.

Pseudocode is often used as a way of describing a computer program to someone who

doesn’t understand how to program a computer. When learning to program, it is
important to write pseudocode because it helps to clearly understand the problem that
one is trying to solve. It also helps avoid getting bogged down with syntax details (i.e.,
like spelling mistakes) when writing the program later (see step 4).

Although flowcharts can be visually appealing, pseudocode is often the preferred choice for
algorithm development because:
▪ It can be difficult to draw a flowchart neatly, especially when mistakes are made.
▪ Pseudocode fits more easily on a page of paper.
▪ Pseudocode can be written in a way that is very close to real program code, making it
easier later to write the program (i.e., in step 4).
▪ Pseudocode takes less time to write than drawing a flowchart.
Pseudocode will vary according to whoever writes it. That is, one person’s pseudocode
is often quite different from that of another person. However, there are some common
control structures (i.e., features) that appear whenever pseudocode is written. These
features are shown along with some examples:
▪ Sequence: Listing instructions step-by-step in order (often numbered)

1. Make sure switch is turned on

6
 2. Check if lamp is plugged in
3. Check if bulb is burned out
4. ……

▪ Condition: Making a decision and doing one thing or something else depending on the
outcome of the decision.

If lamp is not plugged in

then plug it in
If bulb is burned out
then replace bulb

Else buy new lamp

• Repetition: repeating something a fixed number of times or until some condition

occurs

Repeat
get a new light bulb
put it in the lamp
Until lamp works or no more bulbs left

Repeat 3 times
Unplug lamp
Plug into different socket
…..

• Storage: storing information for use in instructions further down the list

x ← a new bulb
count ← 8

• Transfer of Control: being able to go to a specific step when needed

If bulb works then
go to step 7

Note:

7
 • The bold in the above examples highlights the specific control structure.
• For the condition and repetition structures, the portion of the pseudocode that is part of
the condition or the repeat loop are indented a bit in order to make it clear that these
kinds of inner steps that belong to that structure. Braces ({ }) may also be used to
indicate what is in or out of a control structure as shown below.

If (bulb is burned out) then {

Replace bulb
}
Else {
Buy a new bulb
}

Repeat {
Get a new light bulb
Put it in the lamp
} until lamp works or no more bulbs left

Repeat 3 times {
Unplug lamp
Plug into different socket
}

The point is that there are a variety of ways to write pseudocode. The important thing to
remember is that the algorithm should be clearly explained with no ambiguity as to
what order the steps are performed in.
Whether using a flow chart of pseudocode, an algorithm should be tested by manually
going through the steps in mentally to make sure a step or a special situation is not
missed out. Often, a flaw will be found in one’s algorithm because a special situation
that could arise was missed out. Only when one is convinced that the algorithm will
solve the problem, should the next step be attempted.

Consider the previous example of finding the average of a set of 𝑛 grades stored in a
file. What would the pseudocode look like? Here is an example of what it might look

8
like if we had the example of 𝑛 numeric grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 that were loaded from
a file:

Algorithm: Display Grades

1. set the sum of the grade values to 0.

2. load all grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 from file.
3. repeat n times {
4. get grade xi
5. add xi to the sum
}

6. compute the average to be sum / n.

7. print the average

It would be wise to run through the above algorithm with a real set of numbers. Each time an
algorithm is tested with a fixed set of input data, this is known as a test case.
Many test cases can be created. Here are some to try:
𝑛 = 5, 𝑥1 = 92, 𝑥2 = 37, 𝑥3 = 43, 𝑥4 = 12, 𝑥5 = 71… result should be 51

𝑛 = 3, 𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 1……………………….… result should be 1

𝑛 = 0…………………………………………………… result should be 0

Writing the Program

Now that we have a precise set of steps for solving the problem, most of the hard work
has been done. The next step is to transform the algorithm from step 3 into a set of
instructions that can be understood by the computer.

Writing a program is often called "coding" or “implementing an algorithm”. So the

code (or source code) is actually the program itself. Without much of an explanation,
below is a program (written in processing) that implements the given algorithm for
finding the average of a set of grades. Note that the code looks quite similar in
structure, however, the processing code is less readable and seems somewhat more
mathematical:

9
Pseudocode Processing code (Program)

1. set the sum of the grade values to 0. int sum = 0;

2. load all grades 𝑥1, 𝑥2, ⋯ , 𝑥𝑛 from file. byte[] x =
loadBytes("numbers");
repeat 𝑛 times {
get grade 𝑥𝑖 for (int i=0; i<x.length; i++)
3.
4.

5. 5. add 𝑥𝑖 to the sum sum = sum + x[i];

}
int avg = sum / x.length;
6. compute average to be sum/𝑛.
7. print the average. print(avg);

For now, the details of how to produce the above source code will not be discussed. In
fact, the source code would vary depending on the programming language that was
used. Learning a programming language may seem difficult at first, but it will become
easier with practice.

The computer requires precise instructions in order to understand what it is being asked
to do. For example, removing one of the semi-colon characters (;) from the program
above, will make the computer become confused as to what it’s being asked to do
because the semi-colon characters (;) is what it understands to be the end of an
instruction. Leaving one of them off will cause the program to generate what is known
as a compile-time error.

Definition 1-3: Compiling is the process of converting a program into instructions that can be
understood by the computer.

The longer a program is, the more the likelihood of having multiple compile-time errors. One
needs to fix all such compile-time errors before continuing on to the next step.

Test the Program

Once a program is written and compiles, the next task is to make sure that it solves the
problem that it was intended to solve and that the solutions are correct.
Running a program is the process of telling the computer to evaluate the compiled
instructions. When a program is run and all is well, you should see the correct output. It
10
is possible however, that a program works correctly for some set of input data but not
for all. If the output of a program is incorrect, it is possible that the algorithm was not
properly converted into a proper program. It is also possible that the programmer did
not produce a proper algorithm back in step 3 that handles all situations that could
arise. Perhaps some instructions are performed out of sequence. Whatever happened,
such problems with the program are known as bugs.

Definition 1-4: Bugs are errors with a program that cause it to stop working or produce
incorrect or undesirable results.

It is the responsibility of the programmer to fix as many bugs in a program as are

present. To find bugs effectively, a program should be tested with many test cases
(called a test suite). It is also a good idea to have others test one’s program because
they may think up situations or input data that one may never have thought of.

Definition 1-5: Debugging is the process of finding and fixing errors in program code.
Debugging is often a very time-consuming “chore” when it comes to being a
programmer. However, if one painstakingly and carefully follows steps 1 through 3,
this should greatly reduce the amount of bugs in a program, thus making debugging
much easier.

Evaluating the Solution

Once the program produces a result that seems correct, the original problem needs to be
reconsidered to make sure that the answer is formatted into a proper solution to the
problem. It is often the case that it may be realised that the program solution does not
solve the problem the way it is expected. It may also be realised that more steps are
involved.

For example, if the result of a program is a long list of numbers, but the intent was to
determine a pattern in the numbers or to identify some feature from the data, then
simply producing a list of numbers may not suffice. There may be a need to display the
information in a way that helps visualise or interpret the results with respect to the
problem; perhaps a chart or graph is needed. It is also possible that when the results are
examined, it is realised that additional data are needed to fully solve the problem.

11
Alternatively, the results may need to be adjusted to solve the problem more efficiently
(e.g., a game is too slow).

It is important to remember that the computer will only do what it is told to do. It is up
to the user to interpret the results in a meaningful way and determine whether or not it
solves the original problem. It may be necessary to re-do some of the steps again,
perhaps going as far back as step 1 again, if data were missing.

12