DESIGN AND ANALYSIS OF

ALGORITHM
 UNIT 1

INTRODUCTION
 Fundamentals Of Algorithm Problem
Solving Algorithm
• An algorithm is a finite set of instructions that
accomplishes a particular task.
• An algm is a actual procedure to solve a
particular pbm.
• An algm is step by step procedure to solve a
pbm.
 Notion of an Algm
• An algm is a sequence of unambigous instruction for
solving a pbm.
• An input to an algorithm specifies an instance of the pbm.
• An algm can be specified in a natural language or pseudo
code.
• Algm can be implemented as comp pgm.
• An algm is a sequence of finite no of steps involved in
solving a pbm.
• Each algm is a module, designed to handle, specific pbm
relative to particular data struture.
 Characteristics of an Algorithm
1. Input
– Zero (or) more quantities externally supplied
2. Output
– At least one quantity is produced
3. Definiteness
– Each instruction is clear and ambiguous
4. Finiteness
– The algm terminates after a finite number of steps
5. Efficiency
– Every instruction must be very basic
6. Unambiguity
– An algorithm must be expressed in a fashion that is completely
free of ambiguity
 Example 1
• An algm to calculate simple interest
– Step 1: Read the input values for principles(P),
No of years (N), Rate (R)
– Step 2: Compute SI=P*N*R
– Step 3: Print SI
– Step 4: Stop the process
 Example 2
• Euclid’s algorithm to compute gcd(m,n)
– Step 1: If n=0, return the value of m as the answer
and stop, otherwise proceed to step 2.
– Step 2: Divide m by n and assign the value of the
remainder to r.
– Step 3: Assign the value of n to m and the value of
r to n.
– Step 4: Stop the process.
• We apply the rule:
GCD(a, b) = GCD(b, a mod b)
until b = 0.
• Step 1:
• a = 60, b = 24
Compute:
60 mod 24 = 12
So:
GCD(60, 24) = GCD(24, 12)
• Step 2:
• a = 24, b = 12
Compute:
24 mod 12 = 0
So:
GCD(24, 12) = GCD(12, 0)
• Final Step:
• Since the second number is now 0, the GCD is the first number:
GCD = 12
 Algorithm Design and Analysis
1. Understanding the pbm
2. Ascertaining the capabilities of a computational device
3. Choosing between exact and approximate pbm solving
4. Deciding on appropriate data structures
5. Algm design techniques
6. Methods of specifying an algorithm
7. Proving an algorithms’s correctness
8. Analyzing an algm
9. Coding an algm
The following criteria are used to analyze
the algorithm
1. Correctness
2. Amount of work done
3. Amount of space used
4. Simplicity
5. Clarity
6. Optimality
 1.Understanding The Pbm
• This is the first step in designing of algm.
• Read the pbm description carefully to
understand the pbm stmt completely.
• Ask doubt clarifying the doubts about the pbm.
• Identify the pbm types and use existing algm to
find soln.
• Input (instance) to the pbm and range of input
get fixed.
 2.Ascertaining The Capabilities Of A
Computational Device
• Instruction are executed one after another,
one opr at a time.
• Algm are designed to be executed such
machine are called sequential algm.
 3.Choosing Between Exact and
Appropriate Pbm solving
• Choose between solving the pbm exactly and
solving the pbm approximately.
• Exact Algm
– Solve the pbm exctly is called exact algm.
• Appropriate Pbm Solving
– Solve the pbm approximately is called
approximate algm
4. Deciding an Appropriate Data Structure

• Data Structure
– Algm + Data structure=Pgm
– Ds is important for both design and analysis of
algm
 5.Algm Design Techniques
• It is general approach to solving pbm
algorithmically that is applicable to a variety of
pbm from diff areas of computing.
6. Methods of Specifying an Algm
• 2 options:
1. Euclid’s Algm
2. Pseudo Code
1. Euclid’s Algm:
• Specified by simple eng stmt
• Step by step format
2. Pseudo Code:
• Mixture of NL and PL
• If and while stmt are used to show the scope of the variables.
• Arrow is used for assignment operation
• // is used for cmd
 7.Proving an Algm Correctness
• Ex:
– Euclid’s Algm
• The 2nd number is gets smaller on every iteration.
• The algm stops when the second number becomes
zero.
 8.Analyzing Algm
• It measured by space and time
1. Space:
– The no of units, it requires for memory storage.
2. Time:
– Amount of time needed to be executed.
Time complexity:
– Compilation time
– Run time
• Ex 1:
Sum 1()
{
Int x,y,z;
Read x,y;
Z=x+y;
Print “sum of x & y:”,Z
}
Classificaition of Time Complexity
• Worst case
f(n)=n2 (or) f(n)=n log n
• Average case
• Best case
T(n)=0 omega(f(n))
 Space Compexity
• Types of memory:
– Fixed amount of memory (fixed)
– Variable amount of memory (increase or
decrease)
 9.Coding an Algm
• Implementing an algm correctly
 1.2 Important Pbm Types
1. Sorting
2. Searching
3. String processing
4. Graph pbm
5. Combinational pbm
6. Geometric pbm
7. Numerical pbm
 1.Sorting
• Asecending or decending
• Properties:
– 2 imp prop:
• Stable
• In place
• Classification:
1. Internal Sorting
• Sorting with the main memory
• Ex: bubble sort, selection sort, quick sort
2. External Sorting
• Such as tape or disk
• Ex: merger sort, poly phase merge
 2.Searching
• Types:
1. Sequential Search (Linear search)
• Search with first available records and proceed
next ,until the required data item is found
2. Binary Search
• Search the element in the list.
• Split the list and locate the middle element in the list
 3.String Processing
• Sequence of char from an alphabet
• Types:
– Text string
• num ,letters ,spl char
– Bit string
• 0’s or 1’s
• String Matching
– 2 algm are used for matching
• Simple pattern matching algm
• Pattern matching using morn’s pratt algm
• String Operation
– Str concat
– Finding str length
– Substr opr
– Str copy
– Str comp
 4.Graph Algm
• Graph G={V,E}
– V-collection of nodes
– E- collection of edge
• Various Graph Algm:
1. Graph traversal
• Types:
1. DFS
2. BFS
2. Shortest path
3. Topological Sorting
4. Travelling
5. Graph Coloring pbm
 2.5 Combinational Pbm
• Permutation, combination and subset
 2.6 Geometric Pbm
• Points, lines and polygons
• Algm:
– Closest pair pbm
– Convex Hull pbm
2.7 Numerical Pbm