Design and Analysis of
Algorithms
Textbook: Introduction to Algorithms (3rd Edition) by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Reference Book : Introduction to Algorithms (3rd Edition) By Anany Levitin
Engr.Simran Melwani
Introduction
• Simran
• Masters In Software Engineering
• Research Area : AI role in Software Quality
Assurance
• Contact : Email
What is 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.
• Algorithms are not just answers but precisely defined
procedures for getting answers.
• If you leave the lion alone with the goat, the lion will eat the goat.
• If you leave the goat alone with the grass, the goat will eat the grass.
If you Go On Wrong Order
Algorithm Vs Program
Algorithm Program
Algorithm is abstract Concept Implementation for of algorithm.
Language Independent Language Dependent
Does not Depend on Hardware, OS etc Depend on Hardware, OS etc
Algorithm is analyzed Program is tested
Algorithm Vs Program
1. Start • result = 1
2. Initialize a variable result to 1 • n = int (input ("Enter a non-negative integer"))
3. Read the Input Number n
• while n > 0:
4. Multiply result By n
• result *= n
5. Decrement n by 1
6. Repeat Steps 4 and 5 until n become 0 • n-=1
7. Print the value of result • print(f“ Factorial is : {result}")
8. Stop
Why we need to study Algorithms?
• Computer programs would not exist without Algorithms.
• Useful in Developing an Analytical skills.
• By studying algorithms, we learn how to choose or design efficient solutions that save time and resources,
particularly in large-scale applications.(An algorithm should take less time and space to Execute- Effectiveness)
• A bad Algorithm can lead to longer execution time.
Analysis of Algorithm
1. Experimental/Apostrium : Depends on Many Other factors
2. Apriori Analysis (Describing the Behavior of Algorithm and Determine the Rate of Growth of
Function)
1. Worst Case Analysis
2. Best Case Analysis
3. Average Case Analysis
Asymptotic Notations
Big O
Big Omega
Big Theta
Common Function
Find Time Complexity
Thank you
