Part I – Unit 5

Algorithm
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

2
Steps to solver problems using a computer

• Define the problem

• Choose a solution method
• Design the algorithm
• Implement the program
• Debug the program
• Run the program

3
Step 1: Define the problem

• Describe the problem

• Input data
• Input constraints: conditions and relationships
• Output data
• Output constraints: conditions and relationships
• Feasibility analysis
• Time, budget, resources, etc.
• Example: Finding the GCD of two positive integers
• Input: X and Y
• Input constraints: X and Y are positive integers
• Output: Z
• Output constraints: Z is the GCD of X and Y

4
Step 2: Choose a solution method

• Multiple methods may exist. They differ from:

• Execution time
• Memory usage
• Accuracy
• Choose the suitable method based on requirements
and system capabilities.
• Example: Sorting a sequence
• Bubble sort
• Selection sort
• Quick sort
• etc.

5
Step 3: Design the algorithm

• Build a precise and detailed model for the chosen

method.
• Iteratively refine the algorithm (step-by-step
improvement):
• Define and clarify operation: What need to be done to
achieve the result?
• Identify required data and its properties: What inputs are
needed and what outputs are produced?
• Determine the sequence of operations:
• Which steps come first?
• Which steps are repeated, and under what conditions?

6
Step 3: Design the algorithm (cont.)

• The refinement process stops when:

• Required outputs are clearly defined
• A value can be computed using known formulas
• Results can be properly reported
• After refinement, the algorithm should be
represented in a standard form:
• Pseudocode
• Flowcharts

7
Step 4: Implement the program

• Encode the program using a programming language

• Replace operations with corresponding language
statements. For example:
• Operation: Display a message
• Statement: print("...") / write("...")
• Choose a programming language based on the
problem:
• Low-level languages: Assembly
• High-level languages: C, Java, Python, etc.

8
Step 5: Debug the program

• Test and debug to identify and fix errors from Step

4.
• Syntax errors: Incorrect programming language syntax
• Semantic errors:
• Incorrect algorithm implementation
• Incorrect algorithm

9
Step 6: Run the program

• Execute the program on a computer

• Analyze the results
• Check if the results are correct
• If not, review all steps

10
Example

Calculate the area of a trapezoid given its four sides.

b

a c

d
Step 1. Define the problem
• Input: Four sides a, b, c, d
• Input constraints: a, b, c, d > 0 and d > b
• Output: A numeric value representing the area of
the trapezoid.

11
 Example
b
2 p ( p − a )( p − b)( p − c)
hc =
c

a f c
h
1
d e
1. To calculate the area, compute the height (so 𝑆 = ℎ(𝑏 + 𝑑)/2)
2. To find the height h, need three sides of the triangle (1) f = a, e,
and c.
3. Therefore, compute the sides of the triangle (1) before finding h.

12
Example

• To compute the sides of the triangle (1), the

trapezoid sides are required.
• These sides are given in the problem, so the problem
is solvable.

a f c
h
1
d e

13
Step 3. Design the algorithm

1. Input a, b, c, d
2. Compute the sides of triangle (1)
• fa
• ed–c
• p  (f + e + c) / 2
3. Compute the height of triangle (1)
2 p ( p − e)( p − f )( p − c)
h=
e
4. Compute the area of the trapezoid 𝑆 = ℎ(𝑑 + 𝑏)/2
5. Output S

14
Approaches to problem solving with computers

• Direct solution method

• Search for a solution

15
Direct solution method

• Common and simple problems with known solutions.

• The solution can be determined directly through:
• Mathematical formulas, equations, laws, etc.
• These procedures consist of a finite number of basic
operations which can be translated into algorithms and
computer programs.

16
Direct solution method

• Use iterative formulas to appropriate solutions.

• The solution is refined through iterations and
accuracy improves with each step.
• Example: Solve f(x) = 0 using Bisection method
• A limitation for manual computation, but a strength
of computers.
• Considered a direct solution approach.

17
Search for a solution

• An approach based on the “trial-and-error” principle.

• Effective for certain complex problems.
• Various methods and techniques has been proposed.

18
Search for a solution → Some methods

• Brute-force (Exhaustive search):

• Enumerate all possible solutions.
• Test each without missing any case.
• Randomized method:
• Test randomly selected possibilities from a large set.
• Success depends on the strategy and problem conditions.
• Divide into subproblems:
• Break the problem down until solvable subproblems are reached.
• Backtracking:
• Mark failed attempts and try alternative paths.

19
Search for a solution → 8-Queens Problem

20
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

21
Definition

• Algorithm is a fundamental concept in Mathematics

and Computer Science.
• Studying algorithms plays a crucial role in Computer
Science.
• Computers can only perform tasks based on algorithms.
• An algorithm directs the computer step by step on what
to do.

22
Definition

• A set of instructions guiding the execution of a task.

• Consists of a finite sequence of clear and executable
steps:
• Arranged in a special order.
• Applied to input data to produce results in a finite number
of steps.
• An algorithm represents a method for solving a
problem.

23
Example

Problem: Find the maximum element in a finite

sequence of integers.
• Initialize:
• Set MAX to the first element
• (MAX stores the largest value so far)
• Process:
• If all elements are checked => Go to final step
• Compare the next element with Max
• If greater => Update MAX
• Repeat the process
• Output:
• MAX is the largest value in the sequence.

24
Definition in Computer Science

• An algorithm is a finite sequence of ordered steps

that transforms input into the desired output.

25
Operation / Instruction

• An operation is an action performed by algorithm.

• Operations transform the problem from one state to another.
• A sequence of operations transforms the initial state into the
result.
• Operations can be decomposed into smaller steps.
• The order of operation is important
• The same operations in different orders may produce different
results.
• The structure that defines execution order is called control
structure.
• 3 basic types: Sequence, Loop, Branch

26
Characteristics of an algorithm

• When describing an algorithm, consider:

• Input
• Output
• Definiteness
• Finiteness
• Efficiency
• Generality

27
Input/Output

• Input:
• Input values from a defined set.
• Output:
• Output values from a defined set.
• Represent the solution to the problem.
• Correspond to the given input set.

28
Definiteness

• Steps must be precise and unambiguous.

• Given the same input and algorithm, different
processors (human or machine) must produce the
same result.

29
Finiteness

• For all inputs, the algorithm must produce a result in

a finite time.
• Execution time depends on the problem, input data,
and chosen algorithm.
• Example: Sorting a sequence
• Bubble Sort
• Quick Sort
• Etc.

30
Efficiency

• Executing an algorithm requires:

• Execution time
• Supporting resources (paper, memory, etc.) for
intermediate results
• Algorithm complexity:
• Time and space requirements
• More efficient algorithms have lower complexity
• In computing, we focus:
• Time: number of basic operations
• Space: memory usage

31
Generality

• An algorithm is general if it can solve a broad class of

problems.
• Example
• The algorithm for solving ax2 + bx + c = 0 is more general
than the algorithm for solving x2 + 5x + 6 = 0.

32
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

33
Algorithm representation

• Clearly describe the algorithm

• Describe the algorithm to others
• “Describe” the algorithm to a computer
• Methods:
• Natural language: human - human
• Flowchart: using symbols, diagrams
• Pseudocode: like programming language
• Programming language: executable program

34
Natural language

• Principle:
• Use natural language to list the steps of the algorithm.
• Characteristics:
• No special knowledge required
• Verbose: using more words than necessary
• Does not clearly highlight the algorithm structure

35
Example

Problem: Solve the linear equation 𝑎𝑥 + 𝑏 = 0

• Step 1: Input a and b.
• Step 2: If a ≠ 0 then output “The equation has a
unique solution x = -b/a”. Go to end.
• Step 3: (a=0) If b ≠ 0 then output “The equation has
no solution”. Go to end.
• Step 4: (a=0)(b=0) Output “The equation has infinite
solutions”. Go to end.
Example

Problem: Find the maximum element of a sequence of

N elements.
• Step 1: Input N
• Step 2: Input a sequence of N elements a1, a2, …, aN
• Step 3: Assign a1 to Max, assign 2 to the variable i
• Step 4: If i > N, go to step 8
• Step 5: If ai > Max, assign ai to Max.
• Step 6: Increase i by 1
• Step 7: Repeat step 4.
• Step 8: Output: Max is the maximum element
• Step 9: End.

37
Flowchart – Terminal blocks

• 2 types of terminal block: START (BEGIN) and END

• Clearly indicate the beginning and termination of the
algorithm.

START END

38
Process block

• A rectangle containing a sequence of data

processing instructions.

= b-
2 4ac

39
Input/Output block

• Parallelogram: represents input/output operations.

Input a, b

Output Max

40
Decision block

• A diamond shape containing a condition or logical

expression to evaluate.
• Has 1 or many input flows and always 2 output
flows.

True False
a<b

41
Predefine process block

• A rectangle with double edges containing the name

of a subroutine to execute.
• Subroutine: a predefined algorithm.
• Used to reduce complexity and improve the
structure of the flowchart.

Swap A and B

42
Flowline

• Lines connecting one node to another in a flowchart.

True False
>0

X=… No solution

43
How flowchart work?

• Start from the START block.

• Follow the flowline.
• Execute the operation in each block.
• If it is a decision block: evaluate the condition and
follow the corresponding path.
• The algorithm stops at the END block.

44
Example: Represent an algorithm using flowchart

45
Example: Represent an algorithm using flowchart

46
Pseudocode

• Describe algorithms using a programming-like

language (pseudocode)
• Use standardized structured statements
• Still based on natural language
• May include mathematical notation
• Can use procedural structures for recursion or complex
algorithms
• Characteristics:
• Convenient, simple, and easy to understand
• Common structures:
• Assignment, selection, iteration, jump, function call

47
Assignment

• Purpose: Assign a value to a variable

• Notation:
• Max := a1
• Max  a1
• n  n + 1

48
Selection / branching structure

IF <condition> THEN
<action>
ENDIF
Or:
IF <condition> THEN
<action 1>
ELSE
<action 2>
ENDIF

49
Loop structure

WHILE <condition> DO REPEAT

<action> <action>
END WHILE UNTIL <condition>

FOR variable  start_value TO end_value DO

<action>
end FOR
FOR variable  start_value DOWNTO end_value DO
<action>
END FOR

50
Unconditional jump

• Jump to the position labeled L

goto L

• Note: Not recommended!

51
Function/Procedure

• Declare a function
FUNCTION <Function name>(<Parameters>)
Do actions with parameters
Return <Value>
END FUNCTION
• Call a function
[Call] <Function name>(<Arguments>)

52
Example: Find the maximum element of a sequence
1. BEGIN
2. Input N
3. Input a1, a2, …, aN
4. Max a1
5. i  2
6. WHILE i  N DO
7. IF ai > Max THEN
8. Max  ai
9. END IF
10. i  i + 1
11. END WHILE
12. Output Max
13. END

53
Programming language

• Solve the linear equation ax + b = 0

#include <stdio.h>
int main() {
float a, b;
scanf("%f %f", &a, &b);
if (a==0)
if (b==0) printf("No solution");
else printf("Infinite solutions");
else printf("Solution %f",-b/a);
return 0;
}

➔ Will be covered in the next part of the course

54
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

55
Examples

56
Definition

• A problem can be reduced to a smaller instance of

the same type:
• Smaller input size
• Smaller value to compute
• Example: Factorial of a natural number n:
0! = 1,
n! = (n-1)! * n, where n > 0
• Recursive algorithm: Each step calls itself with a
smaller input.

57
Example: Calculate n!

• Input: a natural number n

• Output: F(n) = n!
• Algorithm:
FUNCTION F(n):
IF n = 0 THEN
Return 1
ELSE
Return n * F(n-1)
END IF
END FUNCTION

58
Example: Tower of Hanoi

Rules
• Only one disk can be moved at a time
• Each move consists of taking the top disk from one peg and placing it on
another peg
• A larger disk cannot be placed on top of a smaller disk

59
Example: Tower of Hanoi

• Special case, N = 2
Example: Tower of Hanoi

• General case, PROCEDURE TowerOfHanoi(N, A, B, C)

IF N = 2 Then Print(A→C, A→B, C→B)
N>2 ELSE
TowerOfHanoi(N - 1, A, C, B)
Print(A→B)
TowerOfHanoi(N - 1, C, B, A)
ENDIF
END

61
Note

• A recursive algorithm has two parts

• Base case:
• No recursive call required
• Defines the stopping condition
• Recursive case:
• Calls itself with smaller input
• Controlled by a condition
• Note: Recursion may create many function calls →
can lead to stack overflow.
• Recommendation: Replace recursion with iteration
when possible.

62
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

63
Common algorithms and their applications
Algorithms Applications
RSA algorithm Encryption, Information security
Simplex algorithm Linear programming optimization
Rabin-Karp and Boyer-Moore algorithms Text processing, bioinformatics
Quick sort, Heap sort Data management, processing, and analysis
Hungarian algorithm Maximum matching
Breadth-First search (BFS) and Depth-First Finding connected components of a graph,
search (DFS) solving combinatorial optimization problems
Kruskal’s algorithm for finding maximum Network design
spanning trees
Dijkstra’s algorithm for finding shortest path on Remote sensing, navigation in transportation
a graph and logistics
Ford-Fulkerson algorithm for finding maximum Supply chain, image processing
flow in a network
Fast Fourier Transform Signal processing
Karatsuba algorithm for fast multiplication of Cryptography, scientific computing
large integers

64
Unit 5: Algorithm

1. Solving problems using computer

2. Definition of algorithm
3. Algorithm representation
4. Recursive algorithms
5. Common algorithms and applications
6. Examples

65
Common problems

• Numerical algorithms
• Swap values
• Prime numbers, prime factorization
• GCD, fraction simplification
• Perfect numbers
• Array algorithms
• Input/output sequences
• Find Max, Min
• Sorting
• Search, count elements
• Computations on elements: sum, average, etc.
• Insert / delete elements

66
Swap 2 variables X and Y

• Principle: Using an intermediate variable T

FUNCTION swap(X, Y)
T  X
X  Y
Y  T
END FUNCTION

67
Check a prime number
1. BEGIN
2. Input P
3. flag  FALSE
4. IF P = 1 THEN Go to step 13
5. flag  TRUE
6. FOR k := 2 TO p - 1 DO
7. IF (k is a divisor of P) THEN
8. flag  FALSE
9. Go to step 13
10. END IF
[Link] FOR
[Link] flag = TRUE THEN Output: P is a prime number
[Link] Output: P is not a prime number
[Link] IF
[Link]

68
Find GCD of two natural numbers (1/3)

1. Input a
2. Input b
3. Divide a by b remains r
4. If r = 0 go to step 6
5. (r ≠ 0) assign b to a, assign r to b and
repeat step 3
6. Output: b is the GCD value
7. End

69
Find GCD of two natural numbers (2/3)

1. BEGIN
2. Input a, b
3. REPEAT
4. r  a MOD b
5. IF r = 0 THEN Go to 8
6. a  b
7. b  r
8. UNTIL r = 0
9. Output GCD is b
[Link]

70
Find GCD of two natural numbers (3/3)

1. BEGIN
2. Input a, b
3. REPEAT
4. r  a MOD b
5. a  b
6. b  r 1
7. UNTIL r = 0
8. Output GCD is a
9. END

71
Find the smallest element of a sequence
1. BEGIN
2. InputSequence(N)
3. p  1
4. i  2
5. WHILE i  N DO
6. IF ai < ap THEN
7. p  i
8. END IF
9. i  i + 1
[Link] WHILE
[Link]: The smallest
element is at position p
[Link]

72
 Calculate the sum of a sequence

BEGIN BEGIN
1. InputSequence(N) 1. InputSequence(N)
2. S  0 2. S  0
3. i  1 3. FOR i 1 TO N DO
4. WHILE i  N DO 4. S  S + ai
5. S  S + ai 5. END FOR
6. i  i +1 6. Output: Sum is S
7. END WHILE END
8. Output: Sum is S
END

73
Check whether an element belongs to a sequence

Begin
1. Input N, a sequence a1, a2, … aN and A
2. i  1
3. If i > N go to step 7
4. If A = ai go to step 8
5. i  i + 1
6. Repeat step 3
7. Output: A is not found and go to End
8. Output: A is found and go to End
End

74
Check whether an element belongs to a sequence

BEGIN
1. InputSequence(N)
ERROR !? 2. Input A
3. i  1
4. WHILE (iN AND aiA) DO
5. i  i + 1
6. END WHILE
aN+1 = A? 7. IF i  N THEN
8. Output A is at position i
9. ELSE
ia
i=A
N 10. Output A is not found
[Link] IF
END

75
Sort a sequence in ascending order
Begin
1. Input N and sequence a1, a2, … aN
a1
2. i  1

Sorted

3. If i = N, go to End
4. j  i + 1 ai-1
i Current
5. If j > N go to step 9 ai
j
6. If aj < ai then swap ai and aj ai+1
7. j  j + 1

Unsorted
8. Repeat step 5 
9. i  i + 1
[Link] step 3
End aN

76
Sort a sequence in ascending order
BEGIN
[Link](N)
2.i  1
[Link] i < N DO
4. j  i + 1
1
5. WHILE j  N DO
6. IF aj < ai THEN
7. Swap(ai, aj)
2
8. END IF
9. j  j + 1
3
10. END WHILE
4 11. i  i + 1
[Link] WHILE
END
77
Homework

Describe the following algorithms using flowchart and

pseudocode.
1. Count the number of even elements in a sequence
of N integers.
2. Compute the average of positive numbers in a
sequence of N values.
3. Rearrange a sequence of N numbers: zeros first,
then negative numbers, then positive numbers.
4. Find the maximum value in a sequence and count
its occurrences.

78