Design and analysis of algorithm lec 01_1.pptx

This ppt about Design and analysis of algorithm introduction

1. Design and Analysis of Algorithms Lecture 01 Name of the Instructor Yasmeen

2. Introduction Find the largest number among three numbers?

3. Computing start '. Read the three numbers to be compared, as A, B, C Check if A is greater than B. 3.1 If true, then check if A is greater than C. 3.1.1 If true, print 'A' as the greatest number. 3.1.2 If false, print 'C' as the greatest number. 3.2 If false, then check if B is greater than C . 3.2.1 If true, print 'B' as the greatest number. 3.2.2 If false, print 'C' as the greatest number. End

4. Flowchart C

5. Simple program #include < studio.h > int main() { int A, B, C; printf ("Enter the numbers A, B and C: "); scanf ("%d %d %d", &A, &B, &C); if (A >= B && A >= C) printf ("%d is the largest number.", A); if (B >= A && B >= C) printf ("%d is the largest number.", B); if (C >= A && C >= B) printf ("%d is the largest number.", C); return 0; }

6. Introduction to Algorithm In mathematics and computer science, an algorithm is a finite sequence of well-defined , computer-implementable instructions, typically to solve a class of problems or to perform a computation. A stem by step Procedure.

7. Introduction to Algorithm Algorithms are unambiguous specifications for performing calculation, data processing, automated reasoning, and other tasks.

8. Introduction to Algorithm Will accept zero or more input, but generate at least one output .

9. Introduction to Algorithm Properties of Algorit h m Should terminate in finite time Unambiguous Input Zero or more output at least one Every instruction in algo should be effective It should be deterministic

10. Parallel Computing Architecture Algorithm Program Written in design phase Written in implementation phase Needs domain knowledge Needs programmer knowledge Can be written in any language Can be written in programming language Independent of H/w & S/w Dependent on H/w & S/w We analyze algorithm for time & space We test programs for faults.

11. Problem Solving Cycle Problem Definition: Understand Problem Constraints & Conditions: Understand constraints if any Design Strategies (Algorithmic Strategy) Express & Develop the algo Validation (Dry run) Analysis (Space and Time analysis) Coding Testing & Debugging Installation Maintenance

12. Need for Analysis We do analysis of algorithm to do a performance comparison between different algorithm to figure out which one is best possible option."

13. Need for Analysis What parameters can be considered for comparison between cars ?

14. Need for Analysis Following are the parameters which can be considered while analysis of an algorithm" Time ✅ Space ✅ Bandwidth ✅ Register ✅ Battery power ✅

15. How to Analysis of time?

16. Need for Analysis Experimental Analysis or Apostrium Analysis Relative Analysis Apriori Analysis Independent Analysis’ Absolute Analysis

17. Need for Analysis Experimental or Apostrium or relative analysis: Means analysis of algorithm after it is converted to code. Implement both the algorithms and run the two programs on your computer for different inputs and see which one takes less time.

18. Need for Analysis Advantage: Exact values, no rough estimation . Disadvantage: The final result, instead of depending only on the algorithm, depends on many other factors like background software & hardware, programming language, even the temperature of the room.

19. Need for Analysis Apriori Analysis or Independent analysis or Absolute analysis : We do analysis using asymptotic notations and mathematical tools of only the algorithm, i.e., before converting it into a program of a particular programming language . It is a determination of the order of magnitude of a statement.

20. Asymptotic Analysis: In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate how the time (or space) taken by an algorithm increases with the input size.

21. Asymptotic Analysis: Asymptotic Analysis is not perfect, but it’s the best way available for analyzing algorithms. It might be possible that those large inputs are never given to your software, and an algorithm that is asymptotically slower always performs better for your particular situation. So, you may end up choosing an algorithm that is asymptotically slower but faster for your software. Advantage: Uniform result depends only on the algorithm. Disadvantage: Estimated or approximate value; no accurate and precise value.

22. Asymptotic Notations Asymptotic notations are abstract notations for describing the behavior of an algorithm and determining the rate of growth of a function .

23. Asymptotic Notations After a while, there were many workstations in the office building, and the users recognized it would be desirable to share data and resources among the individual computers. They accomplished this by connecting the workstations over a netword .

24. Asymptotic Notations

25. Big O Notation (O-notation) Definition : Big O notation defines an upper bound of an algorithm; it bounds a function only from above . Purpose: It is useful when we only need the upper bound on time complexity . Formula: O(g(n))={f(n) : there exist positive constants C and N0 such that 0≤f(n)≤ C⋅g (n) for all N≥N0}O(g(n)) = \{ f(n) \text{ : there exist positive constants } C \text{ and } N_0 \text{ such that } 0 \ leq f(n) \ leq C \ cdot g(n) \text{ for all } N \ geq N_0 \}O(g(n))={f(n) : there exist positive constants C and N0​ such that 0≤f(n)≤ C⋅g (n) for all N≥N0​}