CPT121 - INTRODUCTION TO PROBLEMS
SOLVING
The Process of Problem Solving
Module 1 - Unit 2
The Process of Problem Solving - Content
Content of Module 1 - Unit 2
Computer as a model of computation
Understanding the Problem
Formulating a Model
Developing an Algorithm
Writing the Program
Testing the Program
Evaluating the Solution
Conclusion
Summary
2
The Process of Problem Solving - Objectives
Objectives
By the end of this unit, you will be able to:
Understand the computer as a model of computation
Explain the problem solving process in detail
Apply the problem solving paradigm to routine elementary
problems
3
The Process of Problem Solving - Introduction
Introduction
Regardless of the area of study:
Computer science is all about solving problems with
computers.
The problems,
can come from any real-world problem or
perhaps even from the abstract world.
There is a need to have a standard systematic approach to
solving problems.
4
The Process of Problem Solving - Introduction
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 on next slide assumes
a single CPU (Central Processing Unit).
Many computers today have multiple CPUs,
so it can be imagined the model on the next slide being
duplicated multiple times within the computer.
5
The Process of Problem Solving - Introduction
A Simplified Uni-
Processing
Computer System
6
The Process of Problem Solving - Introduction
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
7
The Process of Problem Solving - Computer as a
Model of Computation
Computer as a Model of Computation
With regards to problem solving:
we will apply the above model in that we are given
some kind of input information 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,
swe need to iterate the input/process/output stages multiple times in
equence,
producing intermediate results along the way that solve part of our
problem, but not necessarily the whole problem. 8
The Process of Problem Solving - Computer as a
Model of Computation
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: Problem Solving is the sequential process of analysing
information related to a given situation and generating
appropriate response options.
9
The Process of Problem Solving - Computer as a
Model of Computation
In solving a problem, there are some well-defined steps to be
followed.
For example, consider how the input/process/output works n a
simple problem:
Calculate the average grade for all students in a class.
Input: get all the grades … by typing them in via the keyboard or by
reading them from a USB flash drive or hard disk.
Process: add them all up and compute the average grade.
Output: output the answer to either the monitor, printer, USB flash or
10
hard disk … or a combination of any of these devices.
The Process of Problem Solving - Computer as a
Model of Computation
It can be 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
11
The Process of Problem Solving - Understand the
Problem
Understand the Problem
The first step to solving any problem is to
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?
12
The Process of Problem Solving - Understand the
Problem
One also needs to know
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 clear that the input is a bunch of grades, but we need to
understand the format of the grades.
13
The Process of Problem Solving - Understand the
Problem
Each grade might be:
a number from 0 to 100, or
a letter grade from A to F.
If it is a number, the grade might be:
a whole integer like 73, or
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. 14
The Process of Problem Solving - Understand the
Problem
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.
15
The Process of Problem Solving - Understand the
Problem
Also, 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.
Let us move to the next step for this.
16
The Process of Problem Solving - Fomulating a Model
Formulating a Model
The next step is to understand the processing part of the problem.
Many problems are broken down into smaller problems
that require some kind of simple mathematical computations in order
to process the data.
From the given example, the average of the incoming grades is
to be computed.
Thus, a model (or formula) is needed for computing the average
of a bunch of numbers.
such a “formula”, needs to be developed if does not exist.
17
The Process of Problem Solving - Fomulating a Model
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:
x1, x2, ... , xn, representing a grade percentage,
The following computational model may apply:
Average1 = (x1 + x2 + ... + xn,)/n
where the result will be a number from 0 to 100.
However, this approach will not work if the input data is a set
of letter grades like,
A , B, C, D, F, etc., because 18
The Process of Problem Solving - Develop an Algorithm
Develop an Algorithm
After the formulation of a model,
It is time to come up with a precise plan of what the computer is
expected to do.
Definition: Algorithm is a precise sequence of instructions for
solving a problem.
Some of the more complex algorithms may be considered
Randomized algorithms or non deterministic algorithms,
where the instructions are not necessarily in sequence and may not even
have a finite number of instructions.
19
The Process of Problem Solving - Develop an Algorithm
In this course, the above definition will apply for all algorithms
that will be discussed.
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 are:
pseudo code, or
flowcharts.
20
The Process of Problem Solving - Develop an
Algorithm
Consider the following example for solving the problem of a broken
lamp.
First is the example in a flowchart, and then in pseudocode
21
The Process of Problem Solving - Develop an
Algorithm
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
Pseudocode fits more easily on a page of paper.
It can be written in a way that is very close to real program code, making
it easier to write the program
It takes less time to write than drawing a flowchart
Pseudocodes vary but there are some common control structures, these
features are shown along with some examples, in the slides that follow:
22
The Process of Problem Solving - Develop an
Algorithm
1. Sequence Structure:
Listing instructions step-by-step in order (often numbered)
1. Make sure switch is turned on
2. Check if lamp is plugged in
3. Check if bulb is burned out
4. ……
23
The Process of Problem Solving - Develop an
Algorithm
2. Condition Structure
This implies 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 outs
then replace bulb
ElSE buy new lamp
24
The Process of Problem Solving - Develop an
Algorithm
3. Repetition Feature: 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
25
The Process of Problem Solving - Develop an
Algorithm
4. Storage Feature
Storing information for use in instructions further down the
list:
x ← a new bulb
count ← 8
5. Transfer of Control
Being able to go to a specific step when needed
If bulb works
then goto step 7
26
The Process of Problem Solving - Develop an
Algorithm
Further Example
Algorithm: DisplayGrades
1. set the sum of the grade values to 0.
2. load all grades x1, x2, ⋯ , x𝑛 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 27
The Process of Problem Solving - Develop an
Algorithm
Test Case
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.
Here is an instance:
Given n = 5, x1 = 95, x2 = 55, x3 = 43, x4 = 60, x5 = 71
the result should be .....
28
The Process of Problem Solving - Writing the
Program
Writing the Program
In this step, we 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.
Below is a program that implements the given algorithm for
finding the average of a set of grades.
29
Program examples
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. 30
The Process of Problem Solving - Test the Program
Test the Program
Once a program is written and compiled,
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.
31
The Process of Problem Solving - Test the Program
It 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.
the programmer did not produce a proper algorithm
some instructions are performed out of sequence.
Whatever happened, such problems with the program are called
bugs.
32
The Process of Problem Solving - Test the Program
Definition: Bugs are errors with a program that cause it to stop
working or produce incorrect or undesirable results.
The programmer is responsible to fix all the bugs in the
program.
To find bugs effectively,
a program should be tested with many test cases (a test suite).
It is a good idea to have others test one’s program because they
may think up situations or input data diferrently
33
The Process of Problem Solving - Test the Program
Definition: Debugging is the process of finding and fixing errors in a
program code.
Debugging is often:
a very time-consuming “chore” when it comes to being a
programmer, however,
if one painstakingly and carefully follows the previous steps,
this should greatly reduce the amount of bugs in a program, thus
making debugging much easier
34
The Process of Problem Solving - Evaluating the
Solution
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:
the program solution does not solve the problem the way it is expected,
or
that more steps are involved.
35
The Process of Problem Solving - Evaluating the
Solution
For example, if the result of a program is a long list of numbers,
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.
36
The Process of Problem Solving - Evaluating the
Solution
It is also possible that when the results are examined that:
additional data are needed to fully solve the problem, or
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:
user to interpret the results in a meaningful way, and
determine whether or not the original problem is solved
It may be necessary to re-do some of the steps again.
37
The Process of Problem Solving - Conclusion
Conclusion
To get a solution to any existing problem involves a cycle that
consist of the following:
Using a Computer as a model of computation
Understanding the Problem
Formulating a Model
Developing an Algorithm
Writing the Program
Testing the Program
38
Evaluating the Solution.
The Process of Problem Solving - Summary
Summary
The various stages involved in the problem solving processing are
learnt in this unit. They are seven and sequential:
Computer as a model of computation
Understanding the Problem
Formulating a Model
Developing an Algorithm
Writing the Program
Testing the Program
39
Evaluating the Solution
nd
e E
T h
40
