Introduction To Analysis of Algorithms: Al-Khowarizmi

CS5613- Advanced Analysis of Algorithms MS(CS) - MAJU
LECTURE 1
INTRODUCTION TO ANALYSIS OF ALGORITHMS

ABU JAFAR MUHAMMAD IBN MUSU AL-KHOWARIZMI:
 Abu Ja'far Muhammad ibn Musa Al-Khwarizmi
[Born: about 780 in Baghdad (now in Iraq). Died: about 850]
 An algorithm, named after the ninth century scholar Abu Jafar Muhammad Ibn Musu
Al-Khowarizmi.
What is Algorithm?
An algorithm is a step-by-step procedure for performing some task in a finite amount of time.
What is the difference between an Abstract Data Type (ADT) and a Data Structure?
Abstract Data Type (ADT) Data Structure
ADT is the logical picture of the data and the Data structure is the actual representation of
operations to manipulate the component the data during the implementation and the
elements of the data. algorithms to manipulate the data elements.
What is Data Structure?

A data structure is a systematic way of organizing and accessing data.
Some basic data structure as follows.
 Array
 Link List
 Stacks
 Queues
 Trees
Program:
Program is an implementation of an algorithm in some programming language.
Data structure + Algorithm = Program
Model of Computation:
An abstract sequential computer, called a Random Access Machine or RAM. Uniform cost
model.
Prepared by: Engr. M. Nadeem Page 1

Design and Analysis of Algorithm:
1. The “design” pertains to
i. The description of algorithm at an abstract level by means of a pseudo language, and

ii. Proof of correctness that is, the algorithm solves the given problem in all cases.
2. The “analysis” deals with performance evaluation (complexity analysis).
Problems, Solutions, and Tools

 A computer does not solve problems; it's just a tool that I can use to implement my plan
for solving the problem.
 A computer program is a set of instructions for a computer. These instructions describe
the steps that the computer must follow to implement a plan.
 An algorithm is a plan for solving a problem.
 A person must design an algorithm.
 A person must translate an algorithm into a computer program.
Algorithm Development Process

Our algorithm development process consists of five major steps.
Step 1: Obtain a description of the problem.

Step 2: Analyze the problem.
Step 3: Develop a high-level algorithm. Or Find an algorithm to solve it.
Step 4: Refine the algorithm by adding more detail.
Step 5: Review the algorithm.
What is a good algorithm?

Good algorithm is an efficient algorithm.
What is efficient?
Efficient is something, which has small running time and takes (spaced used) less memory.
 We would be spending more time on analyzing the running time of an algorithm.

 We will also spend some time on analyzing the space.
Efficiency of algorithms is as a function of input size.
Measuring the Running Time:

How should we measure the running time of an algorithm?

Experimental Study
 Write a program that implements the algorithm?
 Run the program with data sets of varying size and composition.
 Use a method like System. CurrentTimesMillis() to get an accurate measure of actual
running time.
Limitations of Experimental Studies:

 It is necessary to implement and test the algorithm in order to determine its running time.
 Experiments can be done only on a limited set of inputs, and may not be indicative of the running
time on other inputs not included in the experiment.
 In order to compare two algorithms, the same hardware and software environments should be
used
Beyond Experimental Studies:

We will develop a general methodology for analyzing running time of algorithms. This approach
 Uses a high-level description of the algorithm instead of testing one of its implementations.
 Takes into account all possible inputs
 Allows one to evaluate the efficiency of any algorithm in a way that is independent of the
hardware and software environment
Pseudo-Code
 A mixture of natural language and high-level programming concepts that describes the
main ideas behind a generic implementation of a data structure or algorithm
 It is more structured than usual prose but less formal than a programming language
 Expressions:
o Use standard mathematical symbols to describe numeric and Boolean expressions
o Use  for assignment (“-“ in Java)
o Use = for the equality relationship (“= =” in Java)
 Method Declarations:
o Algorithm name (param1. param2)
 Programming Constructs:
o decision structures: if ... then ... [else
o while-loops. while ... do
o repeat-loops: repeat ... until ...

o for loop: for ... do
o array indexing A[i], A[i.j]
 Methods:
o calls: object method(args)
o returns: return value
Primitive Operation:
 Primitive Operation: Low-level operation Independent of programming language. Can be
identified in pseudo-code for example:
o Data movement (assign)
o Control (branch, subroutine call, return)
o Arithmetic an logical operations (e.g. addition, comparison)
 By inspecting the pseudo-code, we can count the number; primitive operations executed by
an algorithm.
Time complexity
 Design of Algorithm
 Implementing
 Testing
 Analysis of Algorithm
Time and space
 To analyze an algorithm means:

o developing a formula for predicting how fast an algorithm is, based on the size of
the input (time complexity), and/or
o developing a formula for predicting how much memory an algorithm requires,
based on the size of the input (space complexity)
 Usually time is our biggest concern
o Most algorithms require a fixed amount of space
Time Complexity
 Factors that should not affect time complexity analysis:

o The programming language chosen to implement the algorithm
o The quality of the compiler
o The speed of the computer on which the algorithm is to be executed

How to analyze time complexity?
Algorithm Primitive Frequency Count = (PS x F)

Steps Max. Max.
int sum (int n)
{
int S=0; 1 1 1
for(int i=1; i<=n; i++)
{
S=S+i; 1 N N
}
return(S); 1 1 1
}
Total: 2 + N
T(n) = 2 + N


Asymptotic Analysis:
Some general rules again


Common time complexities:
 O(1) constant time

 O(log n) log time
 O(n) linear time
 O(n log n) log linear time
 O(n2) quadratic time
 O(n3) cubic time
 O(2n) exponential time
Difference between Normal Algorithm and Optimized Algorithm:

Steps Max. Max.
int sum (int n)
{
int S=0; 1 1 1
for(int i=1; i<=n; i++)
{
S=S+i; 1 N N
}
return(S); 1 1 1
}
Total: 2 + N
T(n) = 2 + N

Steps Max. Max.
int sum (int n)
{
int S=0; 1 1 1
S = N*(N+1)/2; 5 1 5
return(S) 1 1 1
}
Total: 7

Types of Asymptotic Analysis:
Example of Best Case, Average Case, Worst Case:
Problem: Searching a key in a set A = {a1, a2, a3 . . . an} => (Linear searching in array)

Conclusion:
 Best case => Minimum No. of comparison (Not much use) => 1 comparison
 Worst case=> Maximum No. of comparison (Most Important) => n comparison
 Average case=> Average No. of comparison =>n/2 comparison
Note: Sometime difficult to find average case
How to analyze space complexity?

Introduction To Analysis of Algorithms: Al-Khowarizmi

Uploaded by

Copyright:

Available Formats

Introduction To Analysis of Algorithms: Al-Khowarizmi

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Analysis of Algorithms: Al-Khowarizmi

Uploaded by

Copyright:

Available Formats

CS5613- Advanced Analysis of Algorithms MS(CS) - MAJU

INTRODUCTION TO ANALYSIS OF ALGORITHMS

What is Data Structure?

Prepared by: Engr. M. Nadeem Page 1

Design and Analysis of Algorithm:

1. The “design” pertains to

i. The description of algorithm at an abstract level by means of a pseudo language, and

2. The “analysis” deals with performance evaluation (complexity analysis).

Problems, Solutions, and Tools

Algorithm Development Process

Step 1: Obtain a description of the problem.

What is a good algorithm?

 We would be spending more time on analyzing the running time of an algorithm.

Measuring the Running Time:

Prepared by: Engr. M. Nadeem Page 2

Limitations of Experimental Studies:

Beyond Experimental Studies:

o repeat-loops: repeat ... until ...

Time and space

 To analyze an algorithm means:

 Factors that should not affect time complexity analysis:

Prepared by: Engr. M. Nadeem Page 4

How to analyze time complexity?

Algorithm Primitive Frequency Count = (PS x F)

Prepared by: Engr. M. Nadeem Page 5

Prepared by: Engr. M. Nadeem Page 6

Some general rules again

Prepared by: Engr. M. Nadeem Page 7

Prepared by: Engr. M. Nadeem Page 8

Common time complexities:

 O(1) constant time

Difference between Normal Algorithm and Optimized Algorithm:

Algorithm Primitive Frequency Count = (PS x F)

Prepared by: Engr. M. Nadeem Page 9

Types of Asymptotic Analysis:

Example of Best Case, Average Case, Worst Case:

Prepared by: Engr. M. Nadeem Page 10

How to analyze space complexity?

Prepared by: Engr. M. Nadeem Page 11

You might also like