MCA_Sem-1_DESIGN AND ANALYSIS OF ALGORITHMS_U-1

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

2 Unit 1 Introduction Characteristics of algorithm, Algorithm Specification Analysis Framework www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

ALGORITH Unit-1(MAP-607) 3 M All right are reserved with CU-IDOL •An algorithm is a set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks. An algorithm is an efficient method that can be expressed within finite amount of time and space. •An algorithm is the best way to represent the solution of a particular problem in a very simple and efficient way. If we have an algorithm for a specific problem, then we can implement it in any programming language, • Algorithm is independent from any programming languages. www.cuidol.in

4 Criteria 1. Input : Zero or more quantities are externally supplied. 2. Output: At least one quantity is produced. 3. Definiteness: Each instruction is clear and unambiguous. 4. Finiteness: If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps. 5. Effectiveness : Eery instruction must be very basic so that it can be carried out, in principle, by a person using only pencil and paper. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

5 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

•Input: It should externally supply zero or more quantities. 6 •Output: It results in at least one quantity. •Definiteness: Each instruction should be clear and ambiguous. •Finiteness: An algorithm should terminate after executing a finite number of steps. •Effectiveness: Every instruction should be fundamental to be carried out, in principle, by a person using only pen and paper. •Feasible: It must be feasible enough to produce each instruction. •Flexibility: It must be flexible enough to carry out desired changes with no efforts. •Efficient: The term efficiency is measured in terms of time and space required by an algorithm to implement. Thus, an algorithm must ensure that it takes little time and less memory space meeting the acceptable limit of development time. •Independent: An algorithm must be language independent, which means that it should mainly focus on the input and the procedure required to derive the output instead of depending upon the language. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Advantages of an 7 Algorithm •Effective Communication: Since it is written in a natural language like English, it becomes easy to understand the step-by-step delineation of a solution to any particular problem. •Easy Debugging: A well-designed algorithm facilitates easy debugging to detect the logical errors that occurred inside the program. •Easy and Efficient Coding: An algorithm is nothing but a blueprint of a program that helps develop a program. •Independent of Programming Language: Since it is a language-independent, it can be easily coded by incorporating any high-level language. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

Disadvantages of an 8 Algorithm •Developing algorithms for complex problems would be time-consuming and difficult to understand. •It is a challenging task to understand complex logic through algorithms. www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

9 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

The important aspects of algorithm 10 design include creating an efficient Algorithm algorithm to solve a problem in an Design efficient way using minimum time and space. www.cuidol.in How to devise algorithms? How to validate algorithms? How to analyze algorithms? How to test a program? Unit-1(MAP-607) All right are reserved with CU-IDOL

11 ALGORITHM SPECIFICATION www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

12 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

13 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

14 www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

REFERENCES 15 TEXT BOOKS T1 Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 2rd Edition, 2009. Pearson. T2 Satraj Sahni and Rajasekaran, “Computer Algorithms/C++, Ellis Horowitz”, 2nd Edition, 2014, Universities Press REFERENCE BOOKS R1 Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, “Introduction to Algorithms”, Clifford Stein, 3rd Edition, PHI R2 S. Sridhar, “Design and Analysis of Algorithms”, Oxford (Higher Education). www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

16 THANK YOU www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL