AoA Part1 Notes
Uploaded by
221nicole0006AoA Part1 Notes
Uploaded by
221nicole0006Note s for Lecture 1
Topic 1 - Introduction to Analysis of Algorithms
Definition of an Algorithm
Input Algorithm Output
Definition 1
An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.
Definition 2
An algorithm is defined as a collection of unambiguous instructions occurring in some
specific sequence and such an algorithm should produce an output for a given set of input in
finite amount of time.
Design, Analysis, and Implementation of Algorithms
Algorithm.
"Step-by-step recipe" used to solve a problem.
Generally independent of programming language or machine on which it is to be
executed.
Design.
Find a method to solve the problem.
Analysis.
Evaluate its effectiveness and predict theoretical performance.
Implementation.
Write actual code and test your theory.s
ImplementAnalysis
Properties of an Algorithm
• Non-ambiguity – each instruction must be clear and precise
• Range of input – should be specified to prevent the algorithm from going into an
infinite state
• Multiplicity – one algorithm can be written in different ways ie. Searching a number
can be done using linear search or binary search. Also an algorithm can be expressed
in different ways ie. A flow chart, simple English or psuedo code
• Speed – algorithm should have logic that produces the output with speed.
• Finiteness – algorithm must terminate after performing required operations.
How to write an Algorithm
1) Algorithm consists of two parts: heading and body
2) Heading has the name of algo, problem description, i/p and o/p
3) Body has logical body of algo making use of various programming constructs and
assignment statements.
4) Compound statements must be enclosed withinh { } brackets
5) Single line comment is written as // at the beginning of comment
6) Assignment operator is Variable expression
7) Boolean operators such as true or false, logical operators such as and, or , not.
Relational operators such as <,>,<=,>=,=,=
8) Array indices use square brackets [ ]
9) Input and output statements
write(“ this is an o/p message”)
read(val)
10) Conditional statements:
If (condition) then stmt
If (condition) then stmt elase stmt
{ } to be used for compound if-then
11) While statement
While (condition) do
{
stmt1;
stmtn;
}
12 For loop
For variable value1 to value n, do
{
Stmt1;
Stmtn
}
13) For i 1 to n step 1
{
}
here variable I is incremented by 1 at each step
14) repeat
stmt1;
stmtn;
Until(cond);
15) break; to break from a loop
16) return; return control from one point to another
Example: find max element of an array
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax ¬ A[0]
for i ¬ 1 to n - 1 do
if A[i] > currentMax then
currentMax ¬ A[i]
return currentMax
Above is an algorithm written in pseudocode. There are two other ways of expressing an
algorithm:
1) Flow chart
2) English language
Designing an Algorithm
The steps are:
1) Understanding the problem – clarifying doubts about the problem, checking if
problem is of a common type, whether algorithms already exist.
2) Decision making – need to analyze i/p, decide on computational devices, whether to
use exact or approximate problem solving, which data structures to be used, find the
algorithmic technique to be used.
3) Specification of algorithm:
1) Using natural language
2) Pseudo code
3) Flow chart
4) Algorithmic verification – check if algortihm gives correct o/p in finite amount of time.
For a a valid set of i/p
5) Analysis of Algorithm – finding the time efficiency, space efficiency, range of i/p,
simplicity of algorithm
6) Implementation of Algorithm
Performance Analysis of an Algorithm
• The efficiency of an algorithm can be decided by measuring the performance of the
algorithm which mainly focuses on the following factors:
• Measuring input size
• Measuring Space complexity
• Measuring Time Complexity
• Computing Order of Growth of an Algorithm
• Best Case, Worst Case and Average Case
Measuring Input size
Measuring the performance of an Algorithm in relation with the input size n is called order of
growth.
Most algorithms transform input objects into output objects.
The running time of an algorithm typically grows with the input size.
Average case time is often difficult to determine.
We focus (primarily) on the worst case running time.
Easier to analyze
Crucial to applications such as games, finance and robotics
best case
average case
worst case
120
100
Running Time
80
60
40
20
0
1000 2000 3000 4000
Input Size
Depending on the input distribution the performance of an algorithm can vary
anywhere between the Best Case and the Worst Case time.
Measuring Space Complexity
• Space Complexity refers to the amount of memory required by an algorithm to run to
completion.
• It is denoted by S(P) and is compose of two factors:
• 1) A fixed part ie: is constant and is independent of the characteristics such as i/p,o/p
– typically includes the space for constants, simple variables and instruction space
( space for code)
• 2) A variable part – consists of the space needed by component variable – which
depends on the particular problem instance being solved, recursion stack space,
referenced variables etc.
• S(P) = C + Sp
Algorithm abc(a,b,c)
{
return a+b+b*c+(a+b-c)/(a-b)
}
For every instance 3 computer words are required to store 3 variables a, b & c
Therefore S(P) = 3
Type Bytes
Boolean 1
Byte 1
Char 2
Int 4
Float 4
Long 8
Double 8
Note: For estimating memory usage, count up number of variables
and weight them by the number of bytes as per their type.
Calculate space complexity for the following algorithm
Algorithm sum(a[ ],n)
{
s 0.0;
for i 1 to n do
s s + a[ I ];
return s;
}
Every instance needs to store array a[ ] and n.
Space needed to store n = 1 word
Space needed to store a[ ] = n words
Space needed to store s and I = 2 words.
= 3 words + n words
