Basic Concepts

and Notation
 Algorithm
Statements that provide solution

Making a cup of Tea

1. Put the teabag in a cup

2. Fill the kettle with water
3. Boil the water in the kettle
4. Pour some of the boiled water into
the cup
5. Add milk to the cup
6. Add sugar to the cup
7. Stir the tea
8. Drink the tea
 Boost post on Facebook

1. Create a fb page
2. Create a post
3. Click boost post

Boost post on Facebook

1. Open Facebook App

2. Click on the hamburger menu
3. Click on pages
4. Click on “Create”
5. Enter details: name of the page, category of the
page, websites, and image
6. Create your post
7. Locate your post
8. Click on Boost Post Now
9. Accomplish details: audience (age range),
number of users, preferred payment method
10. Click Boost Now
Fundamental Properties of
Algorithms

Finiteness
Definiteness
Input
Output
Effectiveness
Example of Finiteness
Properties of an Algorithm

Example 1:
PROBLEM SOLVING PROCESS

Problem Domain
Machine Domain
Solution Domain
 WRITING AN ALGORITHM

Step 1 - START
Step 2 - DECLARE three integers a, b
& c Step 3 - DEFINE values of a & b
Step 4 - ADD values of a & b
Step 5 - STORE output of Step 4 to c
Step 6 - PRINT c
Step 7 - STOP

Step 1 − START ADD

Step 2 − GET values of a & b
Step 3 − c ← a + b //assigning value
to c
Step 4 − DISPLAY c
Step 5 − STOP
USING PSEUDO CODE
USING PSEUDO CODE
ENTER
ACCEPT
CALCULATE
HALT/STOP
INCREMENT/ i++
DECREMENT/ i--
ENTER LOOP
SHOW
ACCEPT
PERFORM
CALCULATE
COMPUTE
SOLUTION ALGORITHM
Mathematical Functions

floo
r

3.14

ceiling

5.65

mod
5%2
Mathematical Functions in C
Mathematical Functions in Java
ALGORITHM EFFICIENCY

Criteria

Time Complexity
Space Complexity

Method

Emperical Method

Theoretical Method

Input (worst case & best case)

Process
Big O-Notation
 Time Complexities

Linear Time
Constant Time
Quadratic Time

Types of measurement

Worst Case
Average Case
Best Case
 Constant Time

Example:

a = 10
b = 10
c=a+5*b

Linear Time

Example 1: Example 2:

a=0 a=0
while b < n Do while b < n Do
b=b+1 b=b+3
 Quadratic Time
Must be proportional
N = 6 //36 times
N = 10 //100 times

Q 1:

O(1) or O(n)?
Constant time (example)
A=0
While a < 11 Do
A=a+1
Q 2:
 Linear Time

Series 1

Graphical Representation of
O(n)
Time = .266
Time = .281
 Logarithmic

Log2(16) = 2 x 2 x 2 x 2
=4
Log2(8) = 2 x 2 x 2
=3
 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

MODULE TITLE

BASIC CONCEPTS AND NOTATION

MODULE OVERVIEW

This module aims to enable you to understand the concepts and properties of
algorithm, the problem solving process, different mathematical functions that can be used
to analyze an algorithm and measuring algorithm complexity using Big – Oh Notation.
Problem solving and programming exercises were included in every section in order to test
your understanding of the lesson.

LEARNING OBJECTIVES

By the end of this module you should be able to:

 Define Algorithm
 Explain the process of problem solving
 Identify properties of algorithms
 Use basic mathematical functions to analyse algorithms
 Measure complexity of algorithms (Big – Oh Notation)

LEARNING CONTENTS

Unit 1: Algorithm and Properties of Algorithm

Introduction
The term algorithm is used in computer science to describe a finite, deterministic,
and effective problem-solving method suitable for implementation as a computer program.
It is a strictly defined finite sequence of well – defined statements that provides the solution
to a problem or to a specific class of problems for any acceptable set of input values (if
there are any inputs). The term “finite” means that the algorithm should reach an end point
and cannot run forever.

Unit learning outcomes

By the end of this unit you should be able to:
 Define what algorithm is
 Differentiate the different properties of algorithms
 Apply these properties to design an algorithm for a specific problem

What is Algorithm?

PANGASINAN STATE UNIVERSITY 1

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

Algorithm is a step-by-step procedure, which defines a set of instructions to be

executed in a certain order to get the desired output. Algorithms are generally created
independent of underlying languages, i.e. an algorithm can be implemented in more than
one programming language.
The following demonstrates how algorithm is being applied in real world:

The Algorithm for Making a Cup of Tea

1. Put the teabag in a cup
2. Fill the kettle with water
3. Boil the water in the kettle
4. Pour some of the boiled water into the cup
5. Add milk to the cup
6. Add sugar to the cup
7. Stir the tea
8. Drink the tea

As you can see, there are certain steps that must be followed. These steps are in
specific order, even though some of the steps could be rearranged. For example, steps 5
and 6 can be reversed. You will also notice that aside from the sequence of steps that must
be performed, the entire process is finite and reach its end point which enable you to
achieve your goal (in this case, making a cup of tea).

Fundamental Properties of Algorithms

 Finiteness - an algorithm must terminate after a finite number of steps
 Definiteness - ensured if every step of an algorithm is precisely defined. For
example, "divide by a number x" is not sufficient. The number x must be define
precisely, say a positive integer.
 Input - domain of the algorithm which could be zero or more quantities
 Output - set of one or more resulting quantities; also called the range of the
algorithm
 Effectiveness - ensured if all the operations in the algorithm are sufficiently basic
that they can, in principle, be done exactly and in finite time by a person using
paper and pen

PANGASINAN STATE UNIVERSITY 2

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

CHECK YOUR UNDERSTANDING – Consider the following Java Code (Adopted

from JEDI Teacher’s Manual for Data Structure and Algorithm). Analyse the code
fragment below:
public class Minimum {
public static void main(String[] args) {
int a[] = { 23, 45, 71, 12, 87, 66, 20, 33, 15,
69 };
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) min = a[i];
}
System.out.println("The minimum value is: " +
min);
}
}
What does the program do? Identify and discuss the different properties that the
algorithm possess.

Unit 2: Problem Solving Process

Introduction
Programming is a problem-solving process, i.e., the problem is identified, the data
to manipulate and work on is distinguished and the expected result is determined. It is
implemented in a machine known as a computer and the operations provided by the
machine is used to solve the given problem.

Unit learning outcomes

By the end of this unit you should be able to:
 Understand the problem solving process
 Design an algorithm for a specific problem

The Problem Solving Process

The problem solving process could be viewed in terms of domains – problem,
machine and solution.

Problem domain includes the input or the raw data to process, and the output or
the processed data. For instance, in sorting a set of numbers, the raw data is set of numbers
in the original order and the processed data is the sorted numbers.

PANGASINAN STATE UNIVERSITY 3

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation
Source: JEDI Teacher’s Manual for Data Structures and Algorithm

The machine domain consists of storage medium and processing unit. The storage
medium – bits, bytes, words, etc – consists of serially arranged bits that are addressable
as a unit. The processing units allow us to perform basic operations that include arithmetic,
comparison and so on.

Source: JEDI Teacher’s Manual for Data Structures and Algorithm

Solution domain, on the other hand, links the problem and machine domains. It is
at the solution domain where structuring of higher level data structures and synthesis of
algorithms are of concern.

Source: JEDI Teacher’s Manual for Data Structures and Algorithm

How to Write an Algorithm

There are no well – defined standards for writing algorithms. Rather, it is problem
and resource dependent. Algorithms are never written to support a particular programming
code. The common constructs across programming languages such as loops and other
flow control can be used to write an algorithm. Writing an algorithm is a process that is only
executed after the problem domain is well – defined. That is, we should know the problem
domain, for which we are designing a solution.

EXAMPLE:
Problem – Design an algorithm to add two numbers and display the result
Step 1 – START
Step 2 – Declare three integers a, b & c
Step 3 – Define values of a & b
Step 4 – Add values of a & b

PANGASINAN STATE UNIVERSITY 4

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

Step 5 – Store output of Step 4 to c

Step 6 – Print c
Step 7 - STOP

Algorithms tell the programmers how to code the program. Alternately, the algorithm
can be represented using a flow chart (which was discussed during your CC 102 class) or
using a pseudocode.

Step 1 − START ADD

Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

We design an algorithm to get a solution of a given problem. A problem can be

solved in more than one ways. Hence, many solution algorithms can be derived for a
given problem.

Source:
https://www.tutorialspoint.com/data_stru
ctures_algorithms/algorithms_basics.ht
m

CHECK YOUR UNDERSTANDING – Design an algorithm for the following using

Pseudocode and Flowcharts
1. Show the algorithm for computing the velocity of the car. Having the following
inputs:
D1 – the starting point
D2 – the ending point
T – Time interval to reach D2
V = (D2 – D1) / T

PANGASINAN STATE UNIVERSITY 5

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

2. Show the algorithm for computing the density of a given square. Use the
following as your inputs:
M – Mass of the object
V – Volume of the square (S6)
D=M/V
- Density of the object
3. Compute the greatest common divisor of two nonnegative integers’ p and q as
follows: If q is 0, the answer is p. If not, divide p by q and take the remainder r.
The answer is the greatest common divisor of q and r.

Unit 3: Mathematical Functions

Introduction

Mathematical functions are useful in the creation and analysis of algorithms. In this
section, some of the most basic and most commonly used functions with their properties
are listed.

Unit learning outcomes

By the end of this unit you should be able to:
 Understand the mathematical functions in the creation and analysis of algorithms
 Solve problems using the different mathematical functions
 Discuss the different identities in relation to mathematical functions

The Mathematical Functions

 Floor of x (⎿x⏌) - greatest integer less than or equal to x, x is any real number
o e.g.:
 ⎣ 3.14 ⎦ = 3
 ⎣ 1/2 ⎦ = 0
 ⎣ -1/2 ⎦ = -1
 Ceiling of x (⎾x⏋) - smallest integer greater than or equal to x, where x is any
real number
o e.g.:
 ⎾3.14⏋= 4
 ⎾1/2⏋= 1
 ⎾-1/2⏋= 0
 Modulo - given any two real numbers x and y,
o x mod y = x if y = 0
o =x-y*⎣x/y⎦ if y <> 0
o e.g.:
 10 mod 3 = 1
 24 mod 8 = 0
 -5 mod 7 = 2

Identities

PANGASINAN STATE UNIVERSITY 6

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

The following are the identities related to the mathematical functions defined above

o ⎾x⏋= ⎿x⏌ if and only if x is an integer

o ⎾x⏋ =⎿x⏌ + 1 if and only if x is not an integer
o ⎣ - x ⎦ = -⎾x⏋
o ⎣ x ⎦ + ⎣ y ⎦ <= ⎣ x + y⎦
o x = ⎣ x ⎦ + x mod 1
o z ( x mod y ) = zx mod zy

CHECK YOUR UNDERSTANDING – Problem Solving: Floor, Ceiling and Modulo

Functions. Compute for the resulting value:

a. ⎣ -5.3 ⎦
b. ⎣ 6.14 ⎦
c. 8 mod 7
d. 3 mod –4
e. –5 mod 2
f. 10 mod 11
g. ⎾ (15 mod –9) + ⎣ 4.3 ⎦ ⏋

Unit 4: Complexity of Algorithm

Introduction

Several algorithms could be created to solve a single problem. These algorithms

may vary in the way they get, process and output data. Hence, they could have significant
difference in terms of performance and space utilization. It is important to know how to
analyse the algorithms, and knowing how to measure the efficiency of algorithms helps a
lot in the analysis process.

Unit learning outcomes

By the end of this unit you should be able to:
 Discuss the different methods on measuring algorithm efficiency
 Understand the impact of Time Efficiency and Space Utilization to the performance
of the algorithm
 Apply Big Oh Notation in determining algorithm complexity

Measuring Algorithm Efficiency

Algorithm efficiency is measured in two criteria: space utilization and time efficiency.
 Time complexity (Time Efficiency) of an algorithm quantifies the amount of time
taken by an algorithm to run as a function of the length of the input.
o Execution time - amount of time spent in executing instructions of a given
algorithm. Notation: T(n). Several factors that affect the execution time
include:

PANGASINAN STATE UNIVERSITY 7

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation


input size

Instruction type

machine speed

quality of source code of the algorithm implementation

quality of the machine code generated from the source code
by the compiler
 Space complexity (Space Utilization) of an algorithm quantifies the amount of
space or memory taken by an algorithm to run as a function of the length of the input.
- Time and space complexity depends on lots of things like hardware,
operating system, processors, etc.

There are several methods on how to measure the efficiency of an algorithm. Some
of these methods include Empirical Method, Theoretical Method, Input and the Process.

 The Empirical Method

- Def.: A method of analyzing an algorithm by determining:
 The number of times each program line runs
 The amount of time required to execute each line
 The number of times each procedures were called
 The amount of time each calls were executed
 Total space allocated to run the program
- A program can be written using some programming language and
execute in a machine.
- Measure the elapsed time from the start of execution to completion.
- The amount of memory utilized can also be monitored.
- The analysis is a results are based on actual experiences with the
program’s execution.
- External Factors affecting the performance of the algorithm
o Programming language employed
o Computer processor
o Available memory
o Users concurrently using the computer

 The Theoretical Method

- Def.: The analysis is based solely on the way algorithms solve problems.
- The algorithm is language and machine independent.
- Runtime and space consumptions are not measured in milliseconds,
minutes, kilobytes and gigabytes.
- Algorithms are compared based on which runs faster or which takes less
space when implemented in the same programming language and
runtime environment.

 The Input
- Algorithms should be given the same input to compare them fairly.
- Algorithms may be compared when they are given inputs of the same
size to keep the efficiency analysis manageable but still fair.
- Factors to consider when analysing algorithms using Input:

 Input Size

PANGASINAN STATE UNIVERSITY 8

 FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in CC 104 (Data Structures and Algorithms) Module 1 Basic Concepts and Notation

 The size of the input is a factor in the time and space

needed by an algorithm to execute.
 If the input to an algorithm is a number, then the
number of bits to store the number, the magnitude of
that number, or the number itself can be the size of
the input.
 If the input is a string, the input size could be the
number of symbols in that string.
 If the input is a two – dimensional array with m rows
and n columns with k integers per cell, then the input
size could be m x n x k.
 The more inputs there are, the more time and space
algorithms take to process.
 Algorithm’s performance is put to the test when the input
size is large enough.
 Inefficiency is magnified by the size of the input.
 As the input size increases, algorithms tend to exhibit
performance patterns.
 When input size becomes sufficiently large, some
algorithms will always be more efficient than others.

 Best, Worst and Average Input Cases

 An algorithm may have different runtimes for inputs of the
same sizes.
 Consider a problem of finding a key in a list of n values.
 The algorithm halts the moment a key matches the value in
a list or did not match any of these values. Matching begins
from left to right of the key.
 Best Case: it will run the fasters when the first value
equals the key.
 Worst Case: When the key matches to the rightmost
value in the list or the key does not match any value.

 The Process
- The input is not under the control of the algorithm designer. The
algorithm should is supposed to work for all valid inputs.
- Process is what the designer can control.
- One way to analyze algorithms is to find an upper bound to the time and
space required by an algorithm.
 The space required is the total memory that needs to be allocated.
 This includes the input, constants and variables at runtime.

The Big Oh Notation

 T(n) grows at a rate proportional to n and thus T(n) is said to have “order of
magnitude n” denoted by the O-notation: T(n) = O(n)
 Formal definition: g(n) = O(f(n)) if there exists two constants c and n0 such that |
g(n) | <= c * | f(n) | for all n >= n0.

PANGASINAN STATE UNIVERSITY 9