daaunit-1-IT-3
daaunit-1-IT-3
daaunit-1-IT-3
ALGORITHMS
UNIT-I
IT-3 1/11/2024 1
CONTENTS
Notion of an Algorithm
Fundamentals of Algorithmic Problem Solving
Important Problem Types
Fundamentals of the Analysis of Algorithm Efficiency
Analysis Framework
Asymptotic Notations and its properties
Mathematical analysis for Recursive algorithms
Mathematical analysis for Non-recursive algorithms
IT-3 1/11/2024 2
Introduction To Algorithm:
NOTION OF AN ALGORITHM
• An algorithm is a sequence of unambiguous instructions for solving a problem,
i.e., for obtaining a required output for any legitimate input in a finite amount of
time.
Problem to be
solved
Algorithm
Computer
Input Output
Program
IT-3 1/11/2024 3
Characteristics of an algorithm:
IT-3 1/11/2024 4
Steps for writing an algorithm:
An algorithm is a procedure. It has two parts; the first part is head and the second part is
body.
The Head section consists of keyword Algorithm and Name of the algorithm with
parameter list. E.g. Algorithm name1(p1, p2,…,p3). The head section also has the
following:
//Problem Description
//Input:
//Output:
In the body of an algorithm various programming constructs like if, for, while and some
statements like assignments are used.
The compound statements may be enclosed with { and } brackets. if, for, while can be
closed by endif, endfor, endwhile respectively. Proper indention is must for block.
The identifier should begin by a letter and not by digit. It contains alpha numeric letters
after first letter. No need to mention data types.
Input and Output can be done using read and write.
IT-3 1/11/2024 5
FUNDAMENTALS OF ALGORIHTMIC PROBLEM SOLVING
Design An algorithm
Prove corectness
IT-3 1/11/2024 6
(i) Understanding the Problem
This is the first step in designing of algorithm.
Identify the problem types and use existing algorithm to find solution.
Input (instance) to the problem and range of the input get fixed.
In some newer computers, operations are executed concurrently, i.e., in parallel. Algorithms that take
advantage of this capability are called parallel algorithms.
Choice of computational devices like Processor and memory is mainly based on space and time efficiency.
If the problem is so complex and not able to get exact solution, then we have to choose an algorithm called an
approximation algorithm. i.e., produces an approximate answer. E.g., extracting square roots, solving nonlinear
equations, andevaluating definite integrals.
IT-3 1/11/2024 7
(c) Algorithm Design Techniques
An algorithm design technique (or “strategy” or “paradigm”) is a general approach
to solving problems algorithmically that is applicable to a variety of problems from different areas of
computing.
Algorithms+ Data Structures = Programs
(iii) Methods of Specifying an Algorithm
There are three ways to specify an algorithm. They are:
a. Natural language:
b. Pseudocode:
c. Flowchart:
Algorithmic Specifications
IT-3 1/11/2024 8
a. Natural Language
It is very simple and easy to specify an algorithm using natural language. But many
times specification of algorithm by using natural language is not clear and thereby we
get brief specification.
Example: An algorithm to perform addition of two
numbers. Step 1: Read the first number, say a.
Step 2: Read the first number, say b.
Step 3: Add the above two numbers and store the result in
c. Step 4: Display the result from c.
Such a specification creates difficulty while actually implementing it. Hence many programmers
prefer to have specification of algorithm by means of Pseudocode.
b. Pseudocode
Pseudocode is a mixture of a natural language and programming language constructs. Pseudocode is
usually more precise than natural language.
For Assignment operation left arrow “←”, for comments two slashes “//”,if condition, for,while loops
are used.
ALGORITHM Sum(a,b)
//Problem Description: This algorithm performs addition of two numbers
//Input: Two integers a and b
//Output: Addition of two
integers c←a+b
return c
IT-3 1/11/2024 9
c. Flowchart
Flowchart is a graphical representation of an algorithm. It is a a method of
expressing an algorithm by a collection of connected geometric shapes
containing descriptions of the algorithm’s step
IT-3 1/11/2024 10
(iv) Proving an Algorithm’s Correctness
Once an algorithm has been specified then its correctness must be proved.
An algorithm must yields a required result for every legitimate input in a finite
amount of time.
(v) Analyzing an Algorithm
For an algorithm the most important is efficiency. In fact, there are two kinds
of algorithm efficiency. They are:
Time efficiency, indicating how fast the algorithm runs, and
Space efficiency, indicating how much extra memory it uses.
The efficiency of an algorithm is determined by measuring both time
efficiency and space efficiency.
So factors to analyze an algorithm are:
Time efficiency of an algorithm
Space efficiency of an algorithm
Simplicity of an algorithm
Generality of an algorithm
IT-3 1/11/2024 11
(vi) Coding an Algorithm
The coding / implementation of an algorithm is done by a suitable programming
language like C, C++, JAVA.
It is very essential to write an optimized code (efficient code) to reduce the burden of
compiler.
IT-3 1/11/2024 12
FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY:
The efficiency of an algorithm can be in terms of time and space. The algorithm
efficiency can be analyzed by the following ways:-
a. Analysis Framework.
b. Asymptotic Notations and its properties.
c. Mathematical analysis for Recursive algorithms.
d. Mathematical analysis for Non-recursive algorithms.
Analysis Framework
There are two kinds of efficiencies to analyze the efficiency of any algorithm. They
are:
• Time efficiency, indicating how fast the algorithm runs, and
•Space efficiency, indicating how much extra memory it uses.
The algorithm analysis framework consists of the following:
• Measuring an Input’s Size
• Units for Measuring Running Time
• Orders of Growth
• Worst-Case, Best-Case, and Average-Case Efficiencies
IT-3 1/11/2024 13
Orders of Growth
A difference in running times on small inputs is not what really distinguishes efficient
algorithms from inefficient ones.
For example, the greatest common divisor of two small numbers, it is not immediately clear
how much more efficient Euclid’s algorithm is compared to the other algorithms, the
difference in algorithm efficiencies becomes clear for larger numbers only.
IT-3 1/11/2024 15
The standard assumptions are that
• The probability of a successful search is equal to p (0 ≤ p ≤ 1) and
• The probability of the first match occurring in the ith position of the list is the
same for every i.
IT-3 1/11/2024 16
ASYMPTOTIC NOTATIONS AND ITS PROPERTIES
Asymptotic notation is a notation, which is used to take meaningful statement about the
efficiency of a program.
The efficiency analysis framework concentrates on the order of growth of an
algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency.
To compare and rank such orders of growth, computer scientists use three notations,
they
are:
O - Big oh notation
Ω - Big omega notation
Θ - Big theta notation
Let t(n) and g(n) can be any nonnegative functions defined on the set of natural
numbers.
The algorithm’s running time t(n) usually indicated by its basic operation count C(n),
and g(n),some simple function to compare with the count.
IT-3 1/11/2024 17
(i) O - Big oh notation
A function t(n) is said to be in O(g(n)), denoted t (n) ∈ O(g(n)),if t (n) is bounded above
by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c
and some non-negative integer n0 such that
t(n) ≤ c g(n) for all n ≥ n0
Where t(n) and g(n) are nonnegative functions defined on the set of natural numbers.
O = Asymptotic upper bound = Useful for worst case analysis = Loose bound
IT-3 1/11/2024 20
MATHEMATICAL ANALYSIS FOR RECURSIVE ALGORITHMS
IT-3 1/11/2024 21
MATHEMATICAL ANALYSIS FOR NON-RECURSIVE ALGORITHMS
IT-3 1/11/2024 22
Example For Substitution Method
We make a guess for the solution and then we use mathematical induction to prove the the
guess is correct or incorrect.
For example:
consider the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn).
Now we use induction to prove our guess.
We need to prove that T(n) <= cnLogn.
We can assume that it is true for values smaller than n.
T(n) = 2T(n/2) + n
<= cn/2Log(n/2) + n
<= cnLogn - cnLog2 + n
= cnLogn - cn + n
<= cnLogn
IT-3 1/11/2024 23
Example For Recurrence Tree Method:
In this method, we draw a recurrence tree and calculate the time taken by every level of
tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from
the given recurrence and keep drawing till we find a pattern among levels. The pattern is
typically a arithmetic or geometric series.
For example consider the recurrence relation T(n) = T(n/4) + T(n/2) + cn2
cn2
T(n/4) T(n/2)
If we further break down the expression T(n/4) and T(n/2), we get following recursion
tree.
cn2
c(n2)/16 c(n2)/4
IT-3 1/11/2024 24
Breaking down further gives us following
cn2
c(n2)/16 c(n2)/4
To know the value of T(n), we need to calculate sum of tree nodes level by level.
If we sum the above tree level by level, we get the following series
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....
The above series is geometrical progression with ratio 5/16. To get an upper
bound, we can sum the infinite series.
We get the sum as (n2)/(1 - 5/16) which is O(n2)
IT-3 1/11/2024 25
Example For Master Method:
The master method works only for following type of recurrences or for recurrences that can
be transformed to following type.
(Contd….)
IT-3 1/11/2024 26
In recurrence tree method, we calculate total work done. If the work done at leaves is polynomially more,
then leaves are the dominant part, and our result becomes the work done at leaves (Case 1). If work done
at leaves and root is asymptotically same, then our result becomes height multiplied by work done at any
level (Case 2). If work done at root is asymptotically more, then our result becomes work done at root
(Case 3).
IT-3 1/11/2024 27
Notes:
1) It is not necessary that a recurrence of the form T(n) = aT(n/b) + f(n) can be solved
using Master Theorem. The given three cases have some gaps between them. For
example, the recurrence T(n) = 2T(n/2) + n/Logn cannot be solved using master method.
2) Case 2 can be extended for f(n) = Θ(ncLogkn)
If f(n) = Θ(ncLogkn) for some constant k >= 0 and c = Logba, then T(n) = Θ(ncLogk+1n)
IT-3 1/11/2024 28