CS 232

Data Structures
Lecture-03

Department of Computer Science & IT

Sarhad University of Science and Information
Technology, Peshawar
Last
Last Lecture
Lecture Summary
Summary
• Introduction to Algorithms
• What is an Algorithm?
• Computer Algorithm and Program
• Favorite and Efficient Algorithm
• Measuring Efficiency
• Running Time of an Algorithm
• Analyzing an Algorithm with Simple Example
• Algorithm History
• Algorithm Applications

CS 232: Data Structures 2

Today’s
Today’s Lecture
Lecture
• Algorithm Specification
• Algorithm Analysis
• Algorithm Performance Calculation
– Empirical Method
– Analytical Method
– Visualization

CS 232: Data Structures 3

Algorithm
Algorithm Specification
Specification
• Algorithms are often specified either in Natural Language or
Pseudo Code Specification
1. Natural Language Specification (NLS)
– In this form of specification, English language words, phrases and
terminology are used to describe the algorithm important steps.
– NLS highlight the algorithm design features.

Example; Algorithm for inorder traversal of a binary tree

 Step #1: Visit Left Node
 Step #2: Visit Root Node
 Step #3: Visit Right Node
– In NLS there are no formalities in phrases and words.
– Freedom in choice of words and style variation.

CS 232: Data Structures 4

Algorithm
Algorithm Specification
Specification –– Cont…
Cont…
2. Pseudo Code Specification (PCS)
• In this form of specification symbol and phrases of some high level
programming (a combination of English words and mathematical
symbols) are used to describe the working of an algorithm.
• It is more useful for analysis purpose.
• There is no standardized notation used for the pseudo code.
− However, the following notation is normally followed.
 Procedures: Name followed by input parameters enclosed in
parentheses. For example, FINDMAX (A, n).
 Assignments to variables: left arrows (←) e.g., j← k ← p
 Variables comparison: symbols x ≤ y, x ≥ y, x ≠ y, x = y, x > y, x < y
 Logical expressions: connectives exp1 AND exp2 , exp1 OR exp2,
NOT exp.
 Computations: arithmetic symbols +, -, *, /

CS 232: Data Structures 5

Algorithm
Algorithm Specification
Specification –– Cont…
Cont…
 Exchanges (Swapping): symbol ↔ e.g., A[i] ↔ A[k]
 Loops and iterations: Words for, do, repeat, while, until are used to
describe loops, such as: for ----, do ----, while ----, do ---- while, do
----- until etc.
 Conditionals: Words if and then are used to specify conditional
statements, such as: if ---- then-----else----
 Block structure: Using indentation i.e., a block with in another block.
For example a block is illustrated as below.
for --- (start of outer most block)
for --- (start of next / inner block)
if --- else ---- ( start of a new block)
 Array: Name followed by size in brackets, e.g., A[1..n]

CS 232: Data Structures 6

Algorithm
Algorithm Specification
Specification –– Cont…
Cont…
• Pseudo Code for displaying even and odd numbers

for i ← 1 to n
if i%2 = 0
print “even number”
else
print “odd number”

CS 232: Data Structures 7

Algorithm
Algorithm Analysis
Analysis
• In general, the purpose of algorithm analysis is to determine
the performance of the algorithm to solve a given problem in
terms of
– Time taken and
– Storage requirements.

• An other objective can be to check

– whether the algorithm produces consistent, reliable, and accurate
outputs for all instances of the problem and under all circumstances.

• The common metrics that are used to gauge the performance

are referred to as
– time efficiency, space efficiency, and correctness.

CS 232: Data Structures 8

Algorithm
Algorithm Analysis
Analysis –– Cont…
Cont…
• Input Size
– The performance is often expressed
• in terms of problem size, or more precisely,
• by the number of data items (input) processed by an algorithm.

• Time Efficiency
– The time efficiency determines how fast an algorithm
solves a given problem.
– Quantitatively, the time taken by the algorithm to produce
an output with a given input.

CS 232: Data Structures 9

Algorithm
Algorithm Analysis
Analysis –– Cont…
Cont…
• Time efficiency is a mathematical function of the input size.
– Suppose, an algorithm takes T(n) time to process n data items.
– The function T(n) is referred to as the running time of the algorithm –
also known as time complexity.

• The time efficiency is the most significant metric for algorithm

analysis.
– For this reason, the main focus of algorithm analysis would be on
determining the time complexity.

CS 232: Data Structures 10

Algorithm
Algorithm Performance
Performance Calculation
Calculation
• Performance = Efficiency = Complexity
• Several ways to determine the time efficiency of an
algorithm.
• Generally, performance of an algorithm is computed
either by:
– Empirical Method or
– Analytical Method and / or
– Visualization

CS 232: Data Structures 11

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• Empirical Method
– With empirical approach, the running time is determined
experimentally.
– The performance is measured by testing the algorithm with inputs of
different sizes.
• Analytical Method
– The analytical method uses mathematical and statistical techniques to
observe the time efficiency.
– The running time is expressed as mathematical function of input size.
• Visualization Method
– The visualization technique is sometimes used to study the behavior
and performance of an algorithm by generating graphics and
animation, based on interactive inputs

CS 232: Data Structures 12

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• Empirical Analysis Methodology
– Assume, two algorithms A & B solve Problem X.
– The empirical methodology broadly has the following
steps.
1. The algorithm is coded and run on a computer. The running times
are measured, by using some timer routine, with inputs of different
sizes.
2. The output is logged and analyzed with the help of graphical and
statistical tools to determine the behavior and growth rate of
running time in terms of input size.

CS 232: Data Structures 13

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• Limitation
– The empirical analysis provides estimates of running times
in a real life situation.
– It has, however, several limitations, because when running
a program on a computer there are some factors that affect
the speed of running such as:
1. Hardware types (CPU speed, IO throughput, RAM size etc.)
2. Software environment (Compiler, Programming Language etc.)
3. Program design (Conventional, Structured, Object Oriented)
4. Composition of data sets (Choice of data values and the range
of input)

CS 232: Data Structures 14

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• Analytical Analysis Methodology
– In analytical approach the running time is estimated by
studying and analyzing the basic or primitive operations
involved in an algorithm.
– Broadly, the following methodology is adopted:
 The code for the algorithm is examined to identify basic
operations.
 The number of times each basic operation is executed, for a given
input, is determined.
 The running time is estimated by taking into consideration the
frequency and cost of significant operations.
 The total time, for each algorithm, is expressed as a function of the
input size.
 Finally, the functions are compared in terms of their growth rate to
decide which one is better.
CS 232: Data Structures 15
Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• Analytical Analysis: Basic Operations
– The code for an algorithm, generally, consists of a mix of
the following basic operations:
1. Assigning value to a variable
2. Comparing a pair of data items (values)
3. Incrementing a variable
4. Performing arithmetic and floating point operations
5. Moving a data item from one storage location to another location
6. Calling a procedure / function
7. Returning a value
8. Accessing an array element

CS 232: Data Structures 16

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• The time taken by the basic operation to complete a single step
is often referred to as the cost of the operation.
• Some operations are relatively more expensive than others.
– For example, operations involving data movement and arithmetical
computations are costly compared to logical or assignment operations.

• Running time is measured by number of steps / primitive

operations performed. Steps means elementary operations.
– For example: +, *,<, =, A[i] etc
• Measure the number of steps taken in term of size of input.

CS 232: Data Structures 17

Algorithm
Algorithm Performance
Performance –– Cont…
Cont…
• For example:

1,2,8: Once
3: N+1 iteration
4,5,6,7: Once per each iteration
of for loop, i.e., N iteration
Total: 1+1+1+(N+1)+N+N+N+N = 5N + 4
The complexity function of the
algorithm is : f(N) = 5N +4

CS 232: Data Structures 18

Summary
Summary
• Algorithm Specification
• Algorithm Analysis
• Algorithm Performance Calculation
– Empirical Method
– Analytical Method
– Visualization (Next Lecture)

CS 232: Data Structures 19

CS 232: Data Structures 20
CS 232: Data Structures 21
CS 232: Data Structures 22
THANK
THANK YOU
YOU

CS 232: Data Structures 23