Chapter 2
Algorithms
Learning outcome
At the end of this chapter, student should be able to:
1. Apply the steps in the program development life cycle.
2. Solve problems using two algorithm representative techniques.
3. Test the algorithm execution process with step-by-step detailing
Program Development Process
• Programming processes can be divided to two
phases:
o The problem solving phase
o The implementation phase
Program Development Process
Problem Solving Phase
• There are three steps to be taken during
problem solving phase:
o To perform a problem analysis,
o Create a general algorithm design, and
o Walkthrough the algorithm.
Analysis
• Is a process of understanding and defining a
problem.
• At this stage, programmer must state the problem
clearly and identify the needs to solve the problem.
• This part is crucial to be determined because it will
influence the next step in the problem-solving
phase.
General Design (Algorithm)
• Algorithm is a set of logical sequential steps used
to solve a problem.
• You need to identify three sub-problems:
o Data collection
o Process calculations
o Output results
• Once the sub-problem is identified, you can refine
the solution one-by-one.
Walkthrough
• This is a process of checking each step of the algorithm to see if
the algorithm really does solve the problem.
• This process is also called as tracing algorithm.
• Use sample of input and check it step-by-step.
• If errors are found, fix the algorithm and repeat the processes in
this phase until you get a working algorithm.
Implementation Phase
• The implementation phase consists of three
steps:
o Program coding
o Code testing
o Program maintenance
Program Coding
• Each algorithm step is interpreted into one or more statements
in programming language.
• Process of writing code (or called programming) happens at this
stage.
• Programmer normally follows all instructions stated in the
algorithm.
Code Testing
• This is a process of running program and checking for errors.
• There are sets of data used to test the program to make sure the
program functions well for different situations.
• If errors are found, the program must be corrected until it produces
the right output.
Maintenance
• This stage is meant for a process of finding errors that could not
be found before, and update it according to the current changes
needed.
• It is important for programmer to write the codes in a very good
style of coding so that the other programmers can do the
maintenance.
algorithms
13
Introduction
• Algorithm is a step-by-step problem solving method in a
limited time.
• Two algorithm representations:
o Flowchart:
▪ Represented by geometry nodes
▪ Each node represents different activities
▪ The nodes are joined using arrows to show the flow or sequential activity
o Pseudo-codes
▪ Pseudo-codes are instructions that mimic the program code.
Flowchart
Example
Problem statement: Get two integer numbers,
sum the numbers and display the output.
Pseudo-codes
• Problem statement: Get two integer numbers, sum the
numbers and display the output.
Pseudo-code:
1.0 Start
2.0 Input two integers: num1 and num2
3.0 Sum the numbers => sum = num1 + num2;
4.0 Display the sum
5.0 End
Algorithm Development Method
• Use divide and conquer method.
• Guideline to build algorithms:
o Identify the input and output of a problem
o Identify and list the sub-problems. Each problem must be solved in
order to get the results needed
o For every sub-problem, identify and list the steps that must be taken
to solve it
Selection Structure
• Selection structure is a structure design that gives a few
choices during execution.
• The choices made are dependent of the conditions that are
given.
• THREE types of general selection structure:
o Single Selection
o Dual Selection
o Multiple Selection
Single Selection
Step a
If <condition true>
Start_If
step 1
step 2
:
step k
End_If
Step k + 1
Flowchart Pseudo-code
Dual-Selection
If <true condition>
Start
step 1
step 2
:
step k
End_If
If_Not
Start
step k+1
step k+2
:
step n
End_If_Not
Step n + 1
Multi-Selection
If <true condition1>
Start
step 1
step 2
:
step k
End_If1
If_Not
If <true condition2>
Start
step k+1
step k+2
:
step m
End_If2
:
If_Not2
If <true condition h>
Start
step n+1
step n+2
:
step p
End_If h
If_Not
step q
step q+1
:
step r
End_If_Not
Repetition Structure
• Repetition structure is a structure where one block of statements
is executed repeatedly.
• THREE types of general repetition structure:
o Counter controlled loop
o Condition controlled loop
o Sentry controlled loop
Counter Controlled Loop
Condition Controlled Loop
• Loops are controlled by true conditions
• There are two types of loops:
• Loops with conditions tested first
• Loops with conditions tested later
Loops with condition tested first
Loops with condition tested later
Sentry Controlled Loop
• Loops of this type are actually subset loops controlled by
condition.
• Sentry value is a signal to stop the loop.
• Loops of these are also called uncertain loops because the
number of loop executions are not known before the execution
starts
• Sentry value chosen must not be an input data.
• Sentry value can also be of type character.
Example
• Design an algorithm to find the perimeter and area of
a rectangle
• The perimeter and area of the rectangle are given by
the following formulas:
perimeter = 2 * (length + width)
area = length * width
17/5/2022
Example
• Algorithm
• Get the length of the rectangle
• Get the width of the rectangle
• Find the perimeter with this equation:
perimeter = 2 * (length + width)
• Find the area with this equation:
area = length * width
17/5/2022
Example
• Calculate each student’s grade
• There are 10 students in a class
• Each student has taken five tests
• Each test is worth 100 points
• Design algorithms to:
• Calculate the grade for each student and class average
• Find the average test score
• Determine the grade
• Use the provided data: students’ names and test scores
17/5/2022
Example
• Algorithm to determine the average test score
• Get the five test scores
• Add the five test scores
• The sum of the test scores is represented by sum
• Suppose average stands for the average test score:
average = sum / 5;
17/5/2022
Example
• Algorithm to determine the grade:
if average is greater than or equal to 90
grade = A
otherwise
if average is greater than or equal to 80 and less than 90
grade = B
otherwise
if average is greater than or equal to 70 and less than 80
grade = C
otherwise
if average is greater than or equal to 60 and less than 70
grade = D
otherwise
grade = F
17/5/2022
Example
• Main algorithm is presented below:
1. totalAverage = 0;
2. Repeat the following for each student:
• Get student’s name
• Use the algorithm to find the average test score
• Use the algorithm to find the grade
3. Update totalAverage by adding current student’s average test
score
4. Determine the class average as follows:
classAverage = totalAverage / 10
17/5/2022
Summary
• Algorithms is a step-by-step problem-solving method
in a limited time.
• Flowchart is represented by geometry nodes. Each
node represents different activities and connected
by arrows to show the flow of sequential activity.
• Pseudo-code are instructions that mimic the
program code.
• Three components need to identified to solve a
problem: input, process and output.
Summary (cont.)
• There are three types of selection structures in
programming called single selection, dual
selection and multiple selection.
• There are three types of repetition structures
called counter-controlled loops, condition-
controlled loops and sentry-controlled loops.
Exercise
• Show pseudocode to identify whether a number is a positive or
negative number.
• Show flowchart to identify whether a number is a positive or
negative number.