Design and Analysis of Algorithm

Couse code: CoSc3094

 Chapter- One
Introduction and Elementary Data Structures

Introduction to Algorithm analysis

Review of elementary Data Structures
Set Representation
 Basic Topics of Chapter- One

– Introduction to Algorithm
– How to analyze algorithm?
– Characteristics algorithms
– Algorithm Design – Asymptotic Notations

– What kinds of problems are – Methods for Solving

solved by algorithms?
Recurrences
– What is Analysis of • Iteration method
• The substitution method
algorithm.
• The recursion tree method
– Why Analyze an Algorithm? • The master method
 What is algorithm?

 An algorithm is a step-by-step procedure for solving a problem in a

finite amount of time. Or

 An algorithm is any-well-defined computational procedure that

takes value, or set of values, as input and produces some value,

or set of values, as output.

 An algorithm is thus a sequence of computational steps that

transform the input into the output.

 What is algorithm? …..

 An algorithm is:

 an efficient method that can be expressed within finite

amount of time and space.

 the best way to represent the solution of a particular

problem in a very simple and efficient way.

 If we have an algorithm for a specific problem, then we can
implement it in any programming language, meaning that the
algorithm is independent from any programming languages.
 Characteristics of Algorithms
 The main characteristics of algorithms should have are as follows:

 Input: zero or more quantities are externally supplied

 Output: at least one quantity is produced

 Definiteness: Each instruction is clear and unambiguous

 Finiteness: Algorithms halt in a finite amount of time. Algorithms

should not run for infinity, i.e., an algorithm must end at some point

 Effectiveness: every instruction must be very basic, so that it can be

carried out, in principle by a person using only paper and pencils.

 Algorithms must have a unique name

 Example #1: Algorithm to add two numbers
Q1. Algorithm to add two numbers entered by the user.
Step1: Start
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2
Step 5: Display sum
Step 6: Stop
Example- #2: Algorithm to solve the problem of
factorials number
Q #1. Problem: Find the factorial of n
Initialize fact = 1
For every value v in range 1 to n:
Multiply the fact by v
fact contains the factorial of n
 Note: Here, the algorithm is written in English. If it was written in a
programming language, we would call it to code instead. Here is a code for
finding the factorial of a number in C++.
int factorial(int n) {
int fact = 1;
for (int v = 1; v <= n; v++) {
fact = fact * v;
}
return fact;
}
 Example #3: The problem of sorting

 For example a sorting algorithm take a sequence of numbers as input,

and a sorted list is output.
 Issues or study of Algorithm

• How to device or design an algorithm creating and algorithm.

• How to express an algorithm definiteness.

• How to analysis an algorithm time and space complexity.

• How to validate an algorithm fitness.

• Testing the algorithm checking for error.

 Data structures vs Algorithms
 Programming is all about data structures and algorithms.

 A data structure is a way to store and organize data in order to

facilitate access and modifications while algorithms are used to
solve the problem using that data.
 Data structures and algorithms (DSA) goes through solutions to
standard problems in detail and gives you an insight into how
efficient it is to use each one of them.
 It also teaches you the science of evaluating the efficiency of an
algorithm.
 This enables you to choose the best of various choices.
 When an algorithm is correct?

 An algorithm is said to be correct if, for every input instance, it halts

with the correct output.

 We say that a correct algorithm solves the given computational

problem.

 An incorrect algorithm might not halt at all on some input

instances, or it might halt with an incorrect answer.

 What kinds of problems are solved by
algorithms?

 Human Gene Project

 Identifying genes on DNA

 Determining the chemical base pair

 Internet – retrieve relevant data(Search Engine)

 E-Comerce: exchange, security

 Commercial Enterprise : allocate resource in order to get

better benefit
 Design of Algorithm
 Involves:
 The description of the algorithm at an abstract level by
means of speudo-language.
 Proof of correctness(Algorithm validation). The algorithm
should solve the given problem.
 The important aspects of algorithm design include creating an
efficient algorithm to solve a problem in an efficient way using
minimum time and space.
 Design of Algorithm…

 To solve a problem, different approaches can be followed.

 Some of them can be efficient with respect to time consumption,

whereas other approaches may be memory efficient.

 However, one has to keep in mind that both time consumption and

memory usage cannot be optimized simultaneously.

 Note: If we require an algorithm to run in lesser time, we have to invest in

more memory and if we require an algorithm to run with lesser memory,

we need to have more time.

 Problem Development Steps
 The following steps are involved in solving computational problems.

Problem definition

Development of a model

Specification of an Algorithm

Designing an Algorithm

Checking the correctness of an Algorithm

Analysis of an Algorithm

Implementation of an Algorithm

Program testing

Documentation
 Exercise #1

1. What is Pseudocode ?
2. What are the difference between Algorithm and Pseudocode
3. Write an algorithms for the following questions
a) Roots of a quadratic equation ax2 + bx + c = 0
b) Check whether a number is a prime number or not
c) find the largest number among three different numbers
 Analysis of algorithms
 In theoretical analysis of algorithms, it is common to estimate their
complexity in the asymptotic sense, i.e., to estimate the complexity
function for arbitrarily large input.
 The term "analysis of algorithms" was coined by Donald Knuth.
 Algorithm analysis is an important part of computational
complexity theory, which provides theoretical estimation for the
required resources of an algorithm to solve a specific computational
problem.
 Most algorithms are designed to work with inputs of arbitrary
length.
 Analysis of algorithms…

 Analysis of algorithms is the determination of the amount of time

and space resources required to execute it. i.e. predicting the resources

that the algorithm requires.

Analysis of algorithm usually deals with time and space complexity.

Usually, the efficiency or running time of an algorithm is stated as a

function relating the input length to the number of steps, known as

time complexity, or

volume of memory, known as space complexity.

 Analysis of algorithms…

 The two most valuable resources for a computer program

are time and memory. where as

 The time taken by the computer to run code is:

Time to run code = number of instructions * time to execute

each instruction.

 The number of instructions depends on the code you used, and

the time taken to execute each code depends on your machine
and compiler.
 Analysis of algorithms…

 Time taken to execute depends on varies factors such as:

 memory,
 band width or
 computer hardware.
 Use the Random Access Memory (RAM) which state that all
instructions are executed sequentially one after another with
no concurrent operations, that is count the number of steps
there runtime of an algorithm is measured.
 How to analyze algorithm ?

This field of study is called analysis of algorithms.

As an algorithm is executed, it makes use of the computer's

central processing unit (cpu) to perform operations and it uses

the memory (both immediate and auxiliary) to hold the program

and its data.

Analysis of algorithms refers to the process of determining how

much computing time and storage an algorithm will require.

This area is a challenging one which sometimes requires great

mathematical skill.
 CASE:PROBLEM

 Suppose that 50 packages are to be delivered to 50 different

houses. The shop, while making the route, finds that the 50
houses are one mile apart and are in the same area.
 SOLUTOIN:ONE

 To deliver 50 packages to their destinations, one of the drivers

picks up all 50 packages, drives one mile to the first house and
delivers the first package. Then he drives another mile and
delivers the second package, drives another mile and delivers
the third package.
 SOLUTOIN:TWO

 Another driver has a similar route to deliver another set of 50

packages. The driver looks at the route and delivers the
packages as follows: The driver picks up the first package,
drives one mile to the first house, delivers the package, and
then comes back to the shop.SO ON.
 The Need for Analysis

Q1. What are the need for analysis of algorithms?

Q2. How to choose a better algorithm for a particular

problem as one computational problem can be solved by

different algorithms?

By considering an algorithm for a specific problem, we can

begin to develop pattern recognition so that similar types of

problems can be solved by the help of this algorithm.

 The Need for Analysis…
Algorithms are often quite different from one another, though the objective

of these algorithms are the same.

For example, we know that a set of numbers can be sorted using different

algorithms.

Number of comparisons performed by one algorithm may vary with others

for the same input. Hence, time complexity of those algorithms may differ.

At the same time, we need to calculate the memory space required by each

algorithm.
 The Need for Analysis…

 Analysis of algorithm is the process of analyzing the problem-

solving capability of the algorithm in terms of the time and
size required (the size of memory for storage while
implementation).
 However, the main concern of analysis of algorithms is the
required time or performance.

 Generally, we perform the following types of analysis:

Worst-case, Best-case & Average-case
 Types of analyses

 Worst-Case Analysis –The maximum amount of time that an

algorithm require to solve a problem of size n.
 This gives an upper bound for the time complexity of an
algorithm.
 Normally, we try to find worst-case behaviour of an
algorithm.

 Best-Case Analysis –The minimum amount of time that an

algorithm require to solve a problem of size n.
 The best case behavior of an algorithm is NOT so useful.
 Types of analyses…

Average-Case Analysis –The average amount of time that an

algorithm require to solve a problem of size n.

 Sometimes, it is difficult to find the average-case behavior of

an algorithm.

 We have to look at all possible data organizations of a given size

n, and their distribution probabilities of these organizations.

 Worst-case analysis is more common than average-case analysis

 Complexity of an algorithm

In designing of Algorithm, complexity analysis of an algorithm is an

essential aspect.
Mainly, algorithmic complexity is concerned about its performance,
how fast or slow it works.
The complexity of an algorithm describes the efficiency of the
algorithm in terms of the amount of the memory required to process
the data and the processing time.
Complexity of an algorithm is analyzed in two perspectives:

i. time complexity and ii. space complexity.

 Complexity of an algorithm …

Most of what we will be discussing is going to be how efficient various

algorithms are in terms of time, but some forms of analysis could be done

based on how much space an algorithm needs to complete its task.

This space complexity analysis was critical in the early days of computing when

storage space on a computer (both internal and external) was limited.

Time and space complexity depends on lots of things like hardware,

operating system, processors, etc.

 However, we don't consider any of these factors while analyzing the

algorithm. We will only consider the execution time of an algorithm.

 i. Time Complexity
The time complexity of an algorithm is the amount of time taken by the

algorithm to complete its process as a function of its input length, n.

Time complexity estimation is based on execution time

The time complexity of an algorithm is commonly expressed

using asymptotic notations:

•Big O - O(n), Big Theta - Θ(n), Big Omega Ω(n)

"Time" can mean the number of memory accesses performed, the number of

comparisons between integers, the number of times some inner loop is executed, or

some other natural unit related to the amount of real time the algorithm will take.
 ii. Space Complexity

The space complexity of an algorithm is the amount of space (or memory) taken by

the algorithm to run as a function of its input length, n.

Space complexity estimation is based on memory space

Space complexity includes both auxiliary space and space used by the input.

• Auxiliary space is the temporary or extra space used by the algorithm while it is being

executed.

Space complexity of an algorithm is commonly expressed using Big O (n) notation.

Many algorithms have inputs that can vary in size, e.g., an array.
 In such cases, the space complexity will depend on the size of the input and hence,
cannot be less that O(n) for an input of size n.
 For fixed-size inputs, the complexity will be a constant O(1).
 Asymptotic Notations

They are used to make meaningful statements about the efficiency of

algorithm.
These notations help us to make approximate but meaningful assumptions
about the time and space
Execution time of an algorithm depends on the instruction set, processor
speed, disk I/O speed, etc.
Hence, we estimate the efficiency of an algorithm asymptotically.
The best, average and worst cases of an algorithm as function of input of size n is
analysis based on the analysis of the algorithm mathematically.
 Asymptotic Notations…

•
 i. O:Big Oh notations
‘O’ (Big Oh) -pronounced “big-oh of g of n”

 is the most commonly used notation.

To denote asymptotic upper bound(at most) i.e. maximum time complexity

Worst case time complexity

Definition: The function 𝐟(𝐧) = 𝑶(𝒈(𝒏)), if there exists a positive constant c

and no such that: 𝒇(𝒏) ≤ 𝒄. 𝒈(𝒏) for 𝒏 ≥ 𝒏o in all case.
It means function g is a upper bound for function f; after a certain value of n, f
will never go above g.
i.e.to the right of no the value of f(n)

always lies on or below c.g(n).

 O:Big Oh Example
•
 O:Big Oh- Questions
•
 ii. Ω: Big omega- notations
 Lower bound (at least) i.e. minimum time complexity

 Best case time complexity

 Definition: The function 𝒇(𝒏) = 𝛀(𝐠(𝒏)) if there exists positive constants

c and no such that 𝒇(𝒏) ≥ 𝒄. 𝒈(𝒏) for 𝒏 ≥ 𝒏𝟎 in all case
 It means function g is a lower bound for function f; after a certain value
of n, f will never go below g.
 i.e. to the right of no, the value of f(n)

lies on or above c.g(n)

 Ω: Big omega-Example
•
 iii. Ɵ: Big theta notations
 To denote asymptotic tight bound
 Average case time complexity
 The function 𝑓(𝑛) = Ɵ(g(𝑛)) if there exist positive constants c1, c2
and no. Such that 𝑐1. 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2. 𝑔(𝑛) 𝒏 ≥ 𝒏𝟎 in all case
 To the write of no the value of f(n) always lies between c1.g(n) and
c2.g(n) inclusive.
 Ɵ: Big theta- Example
•
 Exercise #2
•
 Time complexity notations

•
 Recurrences and Running Time

•A recurrence is an equation or inequality that describes a function in terms of its

value on small inputs.
• T(n) = T(n-1) + n

•Recurrences arise when an algorithm contains recursive calls to itself (i.e the way of
solving a problem by having a function call itself.)

•What is the actual running time of the algorithm?

•The running time of the recursive algorithm can be obtained by a

recurrence.

•Need to solve the recurrence

– Find an explicit formula of the expression

– Bound the recurrence by an expression that involves n
 Example Recurrences
•T(n) = T(n-1) + n Θ(n2)

– Recursive algorithm that loops through the input to eliminate one item

•T(n) = T(n/2) + c Θ(lgn)

– Recursive algorithm that halves the input in one step

•T(n) = T(n/2) + n Θ(n)

– Recursive algorithm that halves the input but must examine every item
in the input

•T(n) = 2T(n/2) + 1 Θ(n)

– Recursive algorithm that splits the input into 2 halves and does a
constant amount of other work
Example #2- Recursive formula for factorials number

•
 Assignment 1 (10%)

Methods for Solving Recurrences

a. Master method
b. Recursion tree method
c. Iteration method
d. Substitution method