CHAPTER 3:

PROBLEM SOLVING TECHNIQUES

1
Faculty of Computing
@2017/2018-1
Chapter 3 Objectives

• Use the basic problem-solving

techniques.

• Develop algorithms through the

process of top-down.

• To use the logical operators to form a

conditional expression in control
statements.

2
Chapter 3 Contents

3.1 Introduction
3.2 Development Algorithms
3.3 Control Structures
3.4 Top-Down Design
3.5 Summary

3
Chapter 3 3.1 Introduction

• Before writing a program to solve a problem, we

need to to really understand the problem and plan
the solution approach carefully.

• Therefore, we need a solving technique or

algorithm that can facilitate the development of
structured computer program.

• Note: One problem can has more than a solving

algorithm but it must has only a single definition so
that everybody will has the same interpretation of
the algorithm.

4
Chapter 3 3.1 Introduction

(Recall in Chapter 2: System Development Life Cycle)

• A step-by-step program plan is created during the design stage.

• Three tools in the problem solving techniques will be discussed:
Development algorithms
o Pseudo-code
o Flowchart
Top-down design
o Structured chart

5
Chapter 3 Contents

3.1 Introduction
3.2 Development Algorithms
• Pseudo-code
• Flowchart
3.3 Control Structures
3.4 Top-Down Design
3.5 Summary

6
Chapter 3 3.2 Development Algorithms
Introduction

• The solution to any computing problem will involves

a series of action in a specific order.

• Algorithm is a procedure for solving a problem in

terms of:
• the actions to be executed, and
• the order in which these actions are to be
executed.

7
Chapter 3 3.2 Development Algorithms
Pseudo-code

• Pseudo-code is an English-like language with

limited vocabulary that helps to develop and
describe algorithms.
• It defines the procedural logic of an algorithm in
a simple and easy-to-understand.
• The pseudo-code consists of characters and
sentencess that are not executed on a
computers.
• A carefully prepared pseudo-code may be easily
to converted to a any computer programs.

8
Chapter 3 3.2 Development Algorithms

Example: Pseudo-code

Algorithm for multiplying two numbers.

1. Start
2. Read (Get) the first number, let say A
3. Read (Get) the second number, let say B
4. Multiply A * B, store the result in C.
5. Display the result, C
6. End.
9
 Chapter 3 3.2 Development Algorithms

Write the pseudo-code program to calculate and

display the volume of a cylinder.
1. Start
2. Read (Get) the high, let say h
3. Read (Get) the radius, let say
r
4. Multiply π * h * r2, store the
result in V.
5. Display the result, V
6. Stop.
10
 Chapter 3 3.2 Development Algorithms
Flowchart
• A flowchart is a graph of geometrical shapes and
connected by lines to develop and represent an
algorithm.
• Flowcharts clearly show how the control structures
operate.
• 2 important elements in flowchart:

Geometrical shapes – Flowlines –

represent type of show the order in which
statements in the the statements of an
algorithm algorithm are executed.
11
 Chapter 3 3.2 Development Algorithms
Some of typical flowchart symbols
Terminal: Indicates the start and end of a flowchart. Single flow line.
Only one “Start” and “Stop” terminal for each program. The end
terminal for function/subroutine must use “Return” instead of “Stop”.
Process: Used whenever data is being processed (manipulated). One
flow line enters and one flow line exits.
Input/Output: Used whenever data is entered (input) or displayed
(output). One flow line enters and one flow line exits.
Decision: Used to represent operations in which there are two possible
selections. One flow line enters and two flow lines (labelled as “Yes” and
“No”) exit.
Function / Subroutine: Used to identify an operation in a separate
flowchart segment (module). One flow line enters and one flow line exits.
On-page Connector: Used to connect remote flowchart portion on the
same page. One flow line enters and one flow line exits.
Off-page Connector: Used to connect remote flowchart portion on
different pages. One flow line enters and one flow line exits.
Comment: Used to add descriptions or clarification.
Flow line: Used to indicate the direction of flow of control.
12
 Chapter 3 3.2 Development Algorithms

Example: Flowchart Start Start Terminal:

Program start here

Algorithm for Get first number,

A Input: Enter values
multiplying two Get second for A and B
number, B
numbers.

Calculate Resut
C=A*B Process

Display the
Result C Output

End Stop Terminal:

Program end here

13
 Chapter 3 3.2 Development Algorithms

Example: Flowchart Start

Use of Comments Read N, N = The number of students

/Description M M = The number of subjects

Yes

No

Stop

14
 Chapter 3 3.2 Development Algorithms

Start

Example: Flowchart 1
2

Use the connectors

of the same page

1  connection on the same

flowchart portion

2  connection on the 1
Stop

different flowchart portion

15
 Chapter 3 3.2 Development Algorithms

Example: Flowchat - Use the connectors of the different page.

Page 1 Page 2
Start

1 2

Yes 1

No End

16
 Chapter 3 3.2 Development Algorithms
The details (how the function works)
we put in another flowchart.
Example: This also known as Function-Definition

Function-Call
Page 1 Start terminal for a Page 2
Start Function is different.
Do not use “Start”
AVRG ( result,n1, n2,n3)
Note:
Module = Function Read
n1, n2 , n3
= Subroutine .
sum = n1+ n2+n3

Body of a function is
AVRG (result, n1, n2,n3) the same with
normal flowchart

result = sum/3

At this part, Print

we only know what result
we want to do. But we
don’t know how to do it Return

This part also known as

Function-Call End
End terminal
must be “Return”
17
 Chapter 3 3.2 Development Algorithms
Draw the flowchart design to
calculate and display the
volume of a cylinder. Start

Get first number,

Get theAhigh, h
Get
Get thesecond
radius, r
number, B

Calculate Resut
Calculate volume,
C=A*B2
V= π*h*r

Display the
Display the
Result C
result V

End

18
 Chapter 3 3.2 Development Algorithms

Convert the temperature

entered by the user in the unit
of Fahrenheit (F) to the unit of
Celsius (C). The conversion
formula is as follows:

F =(C * 9/5) + 32

a) Identify the input, process

and output.
b) Write the pseudo-code
design of the problem.
c) Draw the flowchart design
of the problem.

19
 Chapter 3 Contents

3.1 Introduction
3.2 Development Algorithms
3.3 Control Structures
• Introduction
• Sequential Structure,
• Selective Structure,
• Repetition Structure
3.4 Top-Down Design
3.5 Summary

20
 Chapter 3 3.3 Control Structures
Introduction
• Programs could be written in three way of control
structures (flow of execution):

• Programs produced with structured techniques

(no goto) were clearer, easier to debug and
modify.

21
 Chapter 3 3.3 Control Structures
(a) Sequential Structure
• A series of
statements that are
executed in the order 1. Start
they are written. 2. Statement_1
3. Statement_2
4. Statement_3
• Pseudo-code: mark

the beginning and n. Statement_n+1
end of a block of n+1. End
statements.

22
 Chapter 3 3.3 Control Structures
(a) Sequential Structure
• Multiple statements considered as one statement.

23
 Chapter 3 3.3 Control Structures
(a) Sequential Structure
Trace in sequential
Start

structure Input Input:

Length,
Width
Length  5
Width  3

Calculate Area Process:

Area=Length * Width Area = 5 * 3 = 15

Calculate Perimeter Process:

Perimeter=
2 * (Width+Length)
Perimeter =
2* (5+3) = 16

Print Output:
Area,
Perimeter Area = 15
Perimeter = 16

End
24
 Chapter 3 3.3 Control Structures
(a) Sequential Structure
Calculate the total salary for Ahmad based on the number of days in
a month. Everyday he spent 8 hours with pay RM3 per hour.

a) Identify the input, process and output.

b) Draw the sequential structure of the flowchart design of the
problem.

25
 Chapter 3 3.3 Control Structures
(b) Selection Structure

• Selection by a computer allows you to choose between

two alternatives; that is it allows you to make decision.
• Decisions made by a computer must be very simple
either true (1) or false (0).
• If complex decisions are required, it is the
programmer’s job to reduce them to a series of true or
false decisions that the computer can handle.

26
 Chapter 3 3.3 Control Structures

Selection Structure – Problem Examples.

Problem 4:
Problem 1:
Determine whether the speed limit exceeds 110
Determine whether
km per hour. If the speed exceeds 110, then
profit, return capital
fine = RM300, otherwise fine = 0. Display fine.
or loss.

Problem 2:
Determine whether a
number is even or odd.

27
 Chapter 3 3.3 Control Structures

• C provides three types of selection structures in the form of

statements.

Selective Structures
(statement)

Single-selection Double-selection Multiple-selection

if if...else switch

28
 Chapter 3 3.3 Control Structures

if selection statement

• Pseudo-code: • If set condition is true,

Requires the use execute the statement,
of the keywords if. otherwise false or do
nothing

Algorithm: one choice (one-choice)

selection

: TRUE
n. if condition condition
condition
n.1 statement FALSE
n+1. end_if
: statement

29
 Chapter 3 3.3 Control Structures

• Example: if
Suppose the passing grade on an exam is 60.
The pseudo-code statement:

Flowchart of the single-selection if statement

30
 Chapter 3 3.3 Control Structures

if...else selection statement

• Pseudo-code: Requires • If set condition is true, execute
the use of the keywords the statement_1. If set condition
if and else. is false execute the
statement_2.
Algorithm: two choices
selection (two-choices)

:
TRUE FALSE
n. if condition condition
condition
n.1 statement_1
n+1. else condition
n+1.1 statement_2 statement_1 statement_2
n+2. end_if
:

31
 Chapter 3 3.3 Control Structures

• Example: if...else
Suppose the passing grade on an exam is 60.
The pseudo-code statement:

Flowchart of the double-selection if...else statement

32
 Chapter 3 3.3 Control Structures

Question:

Determine whether an input number is even or odd.

If the number is even, print “This is even number”. If the
number is odd, print “This is odd number”.

a) Write the pseudo-code design of the problem.

b) What is the selective structure type of the problem?
c) Draw the flowchart design of the problem.

(Hint: Use modulus 2 = 0 as even number)

33
 Chapter 3 3.3 Control Structures
c)
Solution 3.5:
Start
a) 1. Start
2. Read n
Get n
3. if n modulus 2 = 0
3.1 Print “This is an even number”
3.2 Go step 5
4. else n % 2 == 0?
4.1 Print “This is an odd number”
False
5. End if True

6. End Print “this Print “this

is an even is an odd
number” number”

b) Double selection
End

34
 Chapter 3 3.3 Control Structures

• The control statements can be combined in only two ways:

1) Stacking: connecting control statement in sequence.

2) Nesting:
• a connecting control statement can be within another
control statement.

35
 Chapter 3 3.3 Control Structures

Stacked if

False
Age > 21?

True Print
Print “kid/teenager”
“Adult”

Gender == True
‘F’ ?

False Print “Female”

Print
“Male”

36
 Chapter 3 3.3 Control Structures

Nested if

• if within if FALSE
• Pseudo-code: test1
TRUE

Algorithm: nested if FALSE °

: test2
n.if condition
TRUE
:
n.m if condition statement
n.m.1 statement
:
n+1. end_if
: it is an
“one-choice” if
37
 Chapter 3 3.3 Control Structures

• Example: Nested if
Print “Excellent” for the grades on an exam equal to 100 for
the passed students. Suppose the passing grade is 60.

The pseudo-code statement:

FALSE
If student’s grade is greater than or Grade≥60
equal to 60
If student’s grade is equal to 100 TRUE
Print “Excellent” FALSE
Grade=100

TRUE

Print “Excellent”

38
 Chapter 3 3.3 Control Structures

Nested if...else
• if...else within if
• The pseudo-code statement:

Algorithm: nested if
:
n.if condition
:
n.m if condition
n.m.1 statement
:
n+1. end_if
:

39
 Chapter 3 3.3 Control Structures

Nested if...else

40
 Chapter 3 3.3 Control Structures

Example: Nested if...else

Print A for exam grades greater than or equal to 90,

Print B for grades greater than or equal to 80 (but less than 90),
Print C for grades greater than or equal to 70 (but less than 80),
Print D for grades greater than or equal to 60 (but less than 70),
and F for all other grades.

41
 Chapter 3 3.3 Control Structures
The pseudo-code statement:

42
 Chapter 3 3.3 Control Structures

Flowchart design
of the problem.

43
 Chapter 3 3.3 Control Structures

Redraw the
flowchart design
of the problem
by comparing
the smaller value
of grade.

44
 Chapter 3 3.3 Control Structures

Relational Operators Relational Expressions

• Used to compare charecters • Boolean expressions: true or

to determine relative order false

• Examples:
• Operators:
> Greater than 12 > 5 is true
< Less than
>= Greater than or equal to 7 <= 5 is false
<= Less than or equal to
if x is 10, then
== Equal to
x == 10 is true
!= Not equal to
x != 8 is true
x == 8 is false
45
 Chapter 3 3.3 Control Structures

Logical Operators
• Used to create relational expressions from other relational
expressions
• Operators, meaning, and explanation:
&& AND New relational expression is true if both
expressions are true
|| OR New relational expression is true if either
expression is true
! NOT Reverses the value of an expression – true
expression becomes false, and false
becomes true

46
 Chapter 3 3.3 Control Structures

Examples: Logical operators

int x =12, y = 5, z = -4;

(x > y) && (y > z) true

(x > y) && (z > y) false
(x <= z) || (y == z) false
(x <= z) || (y != z) true
?
!(x >= z) false
?

47
 Chapter 3 3.3 Control Structures

Trace the selection Start

structure in the the
following flowchart.
a) What is the output Read Num
when the input, Category A
Num = 10?
b) What is the output Num>0? No
when the input,
Print
Num = 0? "Category B"
c) How to correct the Yes
flowchart?
Print
"Category A"

Answer: Logical error!!!

a) Category A
b) Category B Stop
48 Category A
 Chapter 3 3.3 Control Structures
c) Corrected flowchart
Start

Read Num

Num>0? No

Print
"Category B"
Yes

Print
"Category A"

Stop

49
 Chapter 3 3.3 Control Structures
(c) Repetition Structure
• Most programs involve repetition or looping.

• A loop specifies one or more statements that are repeatedly

executed until a condition is satisfied.

• Loop has two important parts:

1. An expression that is tested for a true / false.
2. A statements (block) that is repeated as long as the
expression is true.

• Control statements: while, do...while

for, repeat...until

50
 Chapter 3 3.3 Control Structures
• Two means of repetition / looping:

• 2 styles of repetition / looping:

51
 Chapter 3 3.3 Control Structures

Counter-controlled repetition:

• Known in advance exactly how many times the loop will be

executed.

• A control variable is used to count the number of repetitions.

o Must be initialized before entering loop
o It will increment or decrement each time a loop repeats

52
 Chapter 3 3.3 Control Structures

x Start

initialization cnt=0

FALSE
FALSE
condition cnt<5
TRUE TRUE

body of loop Print “C++”

increment cnt=cnt+1

y End
(a) (b)

(a) Flowchart of counter-controlled repetition with increment counter (b)

53 Example
 Chapter 3 3.3 Control Structures

Sentinel-controlled
repetition:
• Pseudo-code:
• Unknown in advance
exactly how many times the Algorithm: Loop control
loop will be executed. by sentinel value
1. Start
• Use sentinel values to 2. Set repeat = 1
control repetition (indicate 3. while (repeat == 1)
end of the data). 3.1 Read no1
3.2 Read no2
3.4 Print no1 + no2
3.5 Read repeat
4. end_while
5. End
54
 Chapter 3 3.3 Control Structures

Pre-test loop
Pseudo code: requires the • while a set condition is true,
use of the keywords while or repeat statement (body of loop)
for
(one choice)

Algorithm: one choice

FALSE
selection
condition
condition
:
n. while condition TRUE
n.1 statement
body of loop
:
n+1. end_while
:

55
 Chapter 3 3.3 Control Structures

Post-test loop
Pseudo code: requires the use of • statement (body of loop)
the keywords do...while or will be repeated while a set
repeat...until condition is true

Algorithm: one choice

selection statement(s)
:
n. do
n.1 statement
:
n+1. while condition
:

56
 Chapter 3 3.3 Control Structures

Letting the user control a loop Start

• Program can be written so that cnt=0

user input determines loop

repetition Get limit

• Used when program processes

a list of items, and user knows
FALSE
the number of items cnt<limit
TRUE
• User is prompted before loop. Print “C++”
Their input is used to control
number of repetitions
cnt=cnt+1

End

57
 Chapter 3 3.3 Control Structures
Activity : trace output
What is the Output of the following flowchart when the input is Num= 4
Variables (in memory):
Start

Num [ ]
Read Num
Result [ ]
Count [ ]
Initialize

Result=0
Count=Num

Print Count

Result=Result + Count
Count>0? Yes
Count=Count - 1

No

Print
Result

Stop
58
 Chapter 3 3.3 Control Structures
Activity : trace output
What is the Output of the following flowchart when the input is Num= 4
Start
Variables
Variables
Variables (in
(in
(in memory):
memory):
memory):
Num
Num
Num [[[ 444 ]]]
Input: Result
Result
Read Num
Num <- 4
Result [[[ 4
0710]
9 ]]] 049
7 +++ 431
2
Count
Count [[[ 4
Count 320
1 ]]] 431
2 --- 111

Initialize

Result=0
Count=Num

Enter a Number => 4

Count
Count
Count=
Count ===4
132
0
Print Count Count: 4
4
132>
>>>0
000?? ??=>
=>
=>YES
YES
YES
0 => YES
NO Count: 3
Count: 2
Result=Result + Count
Count>0? Yes Count: 1
Count=Count - 1
Count: 0
No
Result: 10

Print
Result

Stop
59
 Chapter 3 Contents

3.1 Introduction
3.2 Development Algorithms
3.3 Control Structures
3.4 Top-Down Design
3.5 Summary

60
 Chapter 3 3.4 Top-Down Design
Introduction

• Structure chart / module chart / hierarchy chart is a graphic

depiction of the decomposition of a problem.
o Illustrates the partitioning of a problem into sub-problems
and shows the hierarchical relationships among the parts.

• It is a tool to aid in software design - aid the programmer in

dividing and conquering a large software problem, that is,
recursively breaking a problem down into parts that are small
enough to be understood by a human brain.

• The process is called top-down design, or functional

decomposition.

61
 Chapter 3 3.4 Top-Down Design

• NOT a flowchart.

• It has nothing to do with the logical sequence of tasks.

• It does NOT show the order in which tasks are

performed.

• It does NOT illustrate an algorithm

62
 Chapter 3 3.4 Top-Down Design

Structured software follows rules:

① Modules are arranged hierarchically.

② There is only one root (i.e., top level) module.

③ Execution begins with the root module.

④ Program control must enter a module at its entry point

and leave at its exit point.

⑤ Control returns to the calling module when the lower

level module completes execution.

63
 Chapter 3 3.4 Top-Down Design
Left-right on the chart is irrelevant
Top- a box
representing the
entire problem

Bottom- a number of boxes

representing the less
64 complicated sub-problems
 Chapter 3 3.4 Top-Down Design

When designing structured software or program,

THREE basic constructs are represented :

1) Sequence - items are executed from top to bottom.

2) Repetition - a set of operations is repeated.

3) Condition - a set of operations are executed only if a

certain condition or CASE statement applies.

65
 Chapter 3 3.4 Top-Down Design

66 Figure: Example of ATM Structure chart

 Chapter 3 Contents

3.1 Introduction
3.2 Development Algorithms
3.3 Control Structures
3.4 Top-Down Design
3.5 Summary

68
 Chapter 3 3.4 Summary

• Before writing a program to solve a particular problem, we

must have a thorough understanding of the problem and
carefully planned a solution approach to solve it.

• A solution to any computing problem involves executing a

series of actions in specific order called algorithm.

• We have learnt that structured programming produces

program that:
• easier to understand,
• easier to test, debug and modify, and
• even prove correct in mathematical sense.

69
 Chapter 3 3.4 Summary

• Three forms of control statement are needed:

• Sequence
• Selection
• Repetition

• All these control statements can be combined in only two

ways:
• Stacking
• Nesting

____________________________________________________________________________________________________________________________________
70 _
 Chapter 3 3.4 Summary

71
 Chapter 3

Self-Reviews

72
 Chapter 3 Self-Review

Exercise 3.1: Fill in the blanks in each of the following questions.

a) A procedure for solving a problem in terms of the

actions to be executed and the order of the
execution is called __________.

b) All programs can be written in terms of three

types of control statement including
__________, __________ and __________.

c) When it is unknown in advance how many times

a set of statements will be repeated, a(n)
__________ value can be used to terminate the
repetition.
73
 Chapter 3 Self-Review

Solution 3.1: Fill in the blanks in each of the following questions.

a) A procedure for solving a problem in terms of the

actions to be executed and the order of the
execution is called algorithm.

b) All programs can be written in terms of three

types of control statement including
sequence, selection and repetition.

c) When it is unknown in advance how many times

a set of statements will be repeated, a(n)
sentinel value can be used to terminate the
repetition.
74
 Chapter 3 Self-Review

Exercise 3.2: A class of ten students took a quiz. The grades

(integers in the range 0 to 100) for this quiz are
available to you. Determine and display the class
average on the quiz.

a) What is the type of control repetition?

b) Write the pseudo-code to solve the problem.
c) Draw the flowchart of the solution.

75
 Chapter 3 Self-Review

Solution 3.2: a) counter-controlled repetition

b) Pseudo-code:

76
 Chapter 3 Self-Review

Solution 3.2:
Start

c) Flowchart:
cnt=0
Total=0

Get num

FALSE
Cnt < num

TRUE Average = total/cnt

Get G
Average

Total = total + G
cnt=cnt+1

End

77
 Chapter 3 Self-Review

Exercise 3.3: A class of students took a quiz. Some of the grades

(integers in the range 0 to 100) for this quiz are
available to you. Determine and, display the class
average with number of students on the quiz.

a) What is the type of control repetition?

b) Write the pseudo-code to solve the problem.
c) Draw the flowchart of the solution.

79
 Chapter 3 Self-Review

Solution 3.3: a) sentinel-controlled repetition

b) Pseudo-code:

80
 Chapter 3 Self-Review

Solution 3.3:

Start Start
c) Flowchart:
cnt=0 cnt=0
Total=0 Total=0

Get
Get G Repeat

FALSE FALSE
G != 999 Repeat ==1

TRUE Average = total/cnt TRUE Average = total/cnt

Total = total + G Get G
cnt=cnt+1 Average Average
Total = total + G
Get G cnt=cnt+1

Get End
End
Repeat
81