CSC402

PROGRAMMING 1
LECTURE: 02 – ALGORITHMIC PROBLEM SOLVING
 2

Learning Objectives:

After completing this chapter, you will be able to:

• describe an algorithm
• differentiate between pseudocode and flow chart
• compare various control structures for a given problem
• construct an appropriate algorithm to a given problem
 3

Problem Solving
• Programming is a process of problem solving
 In 1994, reports
• An algorithm specifies a series of steps that perform a
 31%
particular cancelled
computation or task. Algorithms were
originally
 born
53% as
morepart than
of mathematics – the word
2x over budget
“algorithm” comes from the Arabic writer Muḥammad
ibn Mūsā al-Khwārizmī

Algorithm:
Step-by-step problem-solving process
Solution achieved in finite amount of time
 4

Problem Solving Phases

 In 2014, reports
Problemsolving
31.1% phases are acancelled
total failure, series of steps,
programmers useover
 52.7% to build
budgetcomputer programs.
– Analysis
 Average 16.2% completed
– Design
 9% on-time and on-budget
– Implementation
– Testing/Debugging
– Maintenance
 5

Problem Solving Process

Step 1 – Analysis
– Analyze the problem
– Outline the problem and its requirements
Step 2 - Design
– Design steps (algorithm) to solve the problem
Step 3 - Implementation
– Implement the algorithm in code
Step 4 – Testing/Debugging
– Verify that the algorithm works
Step 5 - Maintenance
– Use and modify the program if the problem
domain changes
 6

Analyze The Problem

• The process of understanding the purpose of a program

and finding the solution to the problem.
▫ Specify program objectives and users
▫ Specify the input - Does program require user interaction?
▫ Specify the output and expected screen
▫ Specify the process (formulas)
▫ Document the findings.

• If the problem is complex, divide it into subproblems

▫ Analyze each subproblem as above
 7

Understanding the Output Screen

• Data values are often entered
from a keyboard.
• The user is shown a prompt.
• A prompt is a message that is
displayed on a monitor, asking the
user for a response.
 8

Understanding the Output Screen

• Many programs run using a
graphical user interface (GUI)
which allows users to interact
with a program in a graphical
environment.
 9

Design
• The process of designing the steps which are
needed to solve the required problem.
▫ Produce an algorithm by writing a pseudo code or a flow
chart.

• 2 types of design:
▫ Structured analysis and design
▫ Object oriented analysis and design
 10

Structured Analysis & Design

• Top-down design
• Programmer begins with a general design and move towards
detail design.
 11

Designing The Algorithm

• Step-by-step instructions that the computer must follow to
transform the problem’s input into its output.

• 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.

• Can be written in two ways:

▫ Pseudocode
▫ Flowchart
 12

Pseudocode
• Step-by-step instructions that the computer must follow to
transform the problem’s input into its output.

• 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.

• Can be written in two ways:

▫ Pseudocode
▫ Flowchart
 13

Pseudocode
• A method of designing a
program using normal
human-language statements
to describe the logic and
processing flow.
 14

Pseudocode
• A method of designing a
program using normal
human-language statements
to describe the logic and
processing flow.
 15

Pseudocode
• Uses short English statements to show
the steps the computer must take to
accomplish the program’s goal.
• Consists of natural language-like
statements that precisely describe the
steps of an algorithm or program
• Statements describe actions
• Focuses on the logic of the algorithm
or program
 16

Pseudocode
• Avoids language-specific elements
• Written at a level so that the desired
programming code can be generated almost
automatically from each statement
• Steps are numbered. Subordinate numbers
and/or indentation are used for dependent
statements in selection and repetition
structures.
 17

Pseudocode
• Avoids language-specific elements
• Written at a level so that the desired
programming code can be generated almost
automatically from each statement
• Steps are numbered. Subordinate numbers
and/or indentation are used for dependent
statements in selection and repetition
structures.
 18

Pseudocode
Several keywords are often used to indicate
common input, output, and processing
operations.

• Input: READ, OBTAIN, GET, ENTER

• Output: PRINT, DISPLAY, SHOW
• Compute: COMPUTE, CALCULATE, DETERMINE
• Initialize: SET, INIT
• Add one: INCREMENT
 19

Pseudocode
• Sequence
▫ Sequential control is indicated by writing one action after
another, each action on a line by itself, and all actions
aligned with the same indent. The actions are performed in
the sequence (top to bottom) that they are written.

▫ Example
1. READ height of rectangle
2. READ width of rectangle
3. COMPUTE area as height times width
 20

Pseudocode

• Selection
▫ Single-Selection IF
1. IF condition THEN (IF condition is true, then
do subordinate statement 1, etc. If condition is
false, then skip statements)
1.1 statement 1
1.2 etc.
 21

Pseudocode

▫ Double-Selection IF
• 2. IF condition THEN (IF condition is true, then do
subordinate statement 1, etc. If condition is false, then
skip statements and execute statements under ELSE)
2.1 statement 1
2.2 etc.
• 3. ELSE (else if condition is not true, then do
subordinate statement 2, etc.)
3.1 statement 2
3.2 statement 3
 22

Pseudocode

• 4. SWITCH expression TO
4.1 case 1: action1
4.2 case 2: action2
4.3 etc.
4.4 default: actionx
 23

Pseudocode

• Repetition
• 5. WHILE condition (while condition is true,
then do subordinate statements)
5.1 statement 1
5.2 etc.
 24

Pseudocode
• DO – WHILE structure (like WHILE, but tests
condition at the end of the loop. Thus, statements
in the structure will always be executed at least
once.)
6. DO
6.1 statement 1
6.2 etc.
7. WHILE condition
 25

Pseudocode

• FOR structure (a specialized version of WHILE

for repeating execution of statements a
specific number of times)
8. FOR bounds on repetition
8.1 statement 1
8.2 etc.
 26

Pseudocode
Pseudocode
27

Express an algorithm to get two numbers from the user (dividend and divisor),
testing to make sure that the divisor number is not zero, and displaying their
quotient using pseudocode
1. Start
2. Declare variables: dividend, divisor, quotient
3. Prompt user to enter dividend and divisor
4. Get dividend and divisor
5. IF divisor is equal to zero, THEN
5.1 DO
5.1.1 Display error message, “divisor must be non-zero”
5.1.2 Prompt user to enter divisor
5.1.3 Get divisor
5.2 WHILE divisor is equal to zero
6. ENDIF
7. Display dividend and divisor
8. Calculate quotient as dividend/divisor
9. Display quotient
10. End
 28

Flowchart
• A chart that graphically
presents the detailed series
of steps needed to solve
programming problems.
 29

Flowchart
 30

Flowchart
Example:
 31

Flowchart
Decision Flowchart:
 32

Flowchart
Looping Flowchart:
 33

Class Average Algorithm (Example)

• Problem: Calculate and report the grade-point average for a

class
• Discussion: The average grade equals the sum of all grades
divided by the number of students
Output: Average grade
Input: Student grades
Processing: Find the sum of the grades; count the number of
students; calculate average
 34

Flowchart
 35

Pseudocode
Program : Determine the average grade of a class
1. Start
2. Initialize counter and sum to 0
3. Do While there are more data
3.1 Get the next grade
3.2 Add the grade to the sum
3.3 Increment the counter
4. Loop
5. Compute average = sum / counter
6. Display average
7. End
 36

Qualities Of A Good Algorithm

• Inputs and outputs should be defined precisely.

• Each steps in algorithm should be clear and
unambiguous.
• The algorithm should be the most effective
among many different ways to solve a problem.
• An algorithm shouldn't have computer code.
Instead, the algorithm should be written in such a
way that, it can be used in similar programming
languages.
 37

Implementation
• The process of writing the code that translates
the design into a computer program using a
programming language.
• Different languages have different syntax.
• A language syntax’s is the set of grammar and
rules that specifies how to write instructions
for an algorithm.
 38

Write The Code

• Once the algorithm is designed and

correctness verified
▫ Write the equivalent code in high-level language
• Enter the program using text editor
 39

Testing
• The process of running the program and checking for
errors. This is to ensure that the program works like it is
supposed to.
• Types of errors:
▫ Syntax error
 Code violates the syntax, or grammar, of the programming language.
▫ Run-time error
 Error that occurs while program is running.
▫ Logic error
 A logic error (or logical error) is a ‘bug’ or mistake in a program’s
source code that results in incorrect or unexpected behaviour.
• Debugging
▫ Process of locating and correcting syntax and logic errors in a
program.
 40

Edit-Compile-Debug-Loop
Begin

Edit
Program

Compile
Program

Compiler True
Errors?

False
Test
Program

Run-time True
Errors?

False
End
 41

Compiling And Linking

• Run code through compiler
• If compiler generates errors
▫ Look at code and remove errors
▫ Run code again through compiler
• If there are no syntax errors
▫ Compiler generates equivalent machine code
• Linker links machine code with system
resources
 42

The Loader And Executing

• Once compiled and linked, loader can place
program into main memory for execution
• The final step is to execute the program
• Compiler guarantees that the program follows
the rules of the language
▫ Does not guarantee that the program will run
correctly
 43

Example 1: Problem Statement

• Write a program that accepts

the year you were born and
calculates and displays your age.
 44

Step 1: Analysis

• Input: yearBorn, curYear

• Output: age
• Process: age = curYear - yearBorn
 45

Step 2: Design

1. Begin
2. Input curYear
3. Input yearBorn
4. age = curYear – yearBorn
5. Output age
6. End
 46

Step 3: Coding
#include <iostream>
using namespace std;
int main()
{
int yearBorn;
int curYear;
int age;
cout << "Please enter the current year: ";
cin >> curYear;
cout << "Please enter the year you were born: ";
cin >> yearBorn;
age = curYear - yearBorn;
cout << "Your age is " << age;
cout << endl;
return 0;
}
 47

Step 3: Coding (cont.)

#include <iostream>
using namespace std;
int main()
{ Main function
int yearBorn;
int curYear;
int age; Variables declaration
curYear = 2013;
cout << "Please enter the year you were born: ";
cin >> yearBorn;
age = curYear - yearBorn; Statements
cout << "Your age is " << age;
cout << endl;
Take note of the semicolon at the
return 0;
} end of each variable declarations
and statement (instructions)
 48

Compilation Process
hello.obj hello
hello.o hello.exe
Source Object Executable
Code Compiler Code Linker Program

hello.cp
p Library

hello.C
A library is a collection of code that has
been programmed and translated by
other programmers
 49

Maintenance

• Modify your program so that you will have to

enter the current year.
▫ Back to step 1 & 2: Analysis & Design
 50

Example 2: Problem Statement

• Write a program that computes

the sum of two integer
numbers.

• Note: do the design.

 51

Codes in C++
• /* This is a program that computes the sum of two integer numbers */
• #include <iostream.h> //preprocessor directive
• main()
• { int x, y, sum; //declaration of variables
• cout<<”Enter first number:”; //user promt
• cin>>x; //input from console
• cout<<”Enter second number:”; //user prompt
• cin>>y; //input from console
• sum=x+y; //add x and y
• cout<<endl <<”Sum= “<<sum; //display output to console
return 0; //return a value to the environment and program
//ended successfully
• }
 52

Example 3 - Rectangle

• 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
 53

Example 3(Continued)
• Analysis:
• Input:
▫ Get length of the rectangle
▫ Get width of the rectangle
• Process:
▫ Find the perimeter using the following equation:
perimeter = 2 * (length + width)
▫ Find the area using the following equation:
area = length * width

• Output:
▫ Display perimeter, area

Note: do the design

 54

Example 4
• Every salesperson has a base salary
• Salesperson receives $10 bonus at the end of the month for each
year worked if he or she has been with the store for five or less
years
• The bonus is $20 for each year that he or she has worked there if
over 5 years
• Additional bonuses are as follows:
▫ If total sales for the month are $5,000-$10,000, he or she receives a
3% commission on the sale
▫ If total sales for the month are at least $10,000, he or she receives a
6% commission on the sale
 55

Example 4 (continued)
1. Input: base salary, no of service years, total
sale
2. Process:
• Calculate bonus
• Calculate additional bonus
3. Output: pay check
 56

Example 4 (continued)
• Calculate bonus using the following formula:
if (noOfServiceYears is less than or equal to five)
bonus = 10 * noOfServiceYears
otherwise
bonus = 20 * noOfServiceYears

• Calculate additionalBonus as follows:

if (totalSale is less than 5000)
additionalBonus = 0
otherwise
if (totalSale is greater than or equal to 5000 and
totalSale is less than 10000)
additionalBonus = totalSale · (0.03)
otherwise
additionalBonus = totalSale · (0.06)
 57

Example 4 (continued)

• Calculate payCheck using the equation

payCheck = baseSalary + bonus + additionalBonus
 58

Example 5

• 10 students in a class
• Each student has taken five tests and each test is
worth 100 points.
• Design an algorithm to calculate the grade for
each student as well as the class average.
▫ Design an algorithm to find the average test score.
▫ Design an algorithm to determine the grade.
• Data consists of students’ names and their test
scores.
 59

Example 5 (continued)

• Algorithm to determine the average test score.

1. Get the five test scores.

2. Add the five test scores. Suppose sum stands for the sum of the test
scores.
3. Suppose average stands for the average test score. Then
average = sum / 5;
 60

Example 5 (continued)
• 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
 61

Example 5 (continued)
• Main algorithm is as follows:
1. totalAverage = 0;
2. Repeat the following steps for each student in the class.
a. Get student’s name.
b. Use the algorithm as discussed above to find the average test score.
c. Use the algorithm as discussed above to find the grade
d. Update totalAverage by adding current student’s average test score.
3. Determine the class average as follows:
classAverage = totalAverage / 10
 62

Typical Real World Problem Solving

1. Transaction
2. Decision making
3. Control Problem
4. Searching Problems
5. Sorting Problems
THANK YOU…