Introduction to Analysis & Design of Algorithms Lecture 1 PDF

Summary

This document is a lecture on Introduction to Analysis & Design of Algorithms. It covers the basics of algorithms, including definitions, properties, and examples like converting feet to centimeters using pseudocode and flowchart. The lecture is provided by University of Saba Region.

Full Transcript

‫جامعة اقليم سباء‬ ‫كلية تكنولوجيا المعلومات وعلوم‬ ‫الحاسوب‬ ‫‪Introduction to Analysis & Design of‬‬ ‫‪Algorithms‬‬ ‫‪Lecture 1‬‬ ‫جامعة اقليم سبا ‪ -‬كلية تكنولوج...

‫جامعة اقليم سباء‬ ‫كلية تكنولوجيا المعلومات وعلوم‬ ‫الحاسوب‬ ‫‪Introduction to Analysis & Design of‬‬ ‫‪Algorithms‬‬ ‫‪Lecture 1‬‬ ‫جامعة اقليم سبا ‪ -‬كلية تكنولوجيا‬ ‫‪31-Oct-24‬‬ ‫‪www.usr.ac‬‬ ‫‪1‬‬ INTRODUCTION The word algorithm comes from the name of the person author -Abu Jafar Mohammed Ibn Musa Al khowarizmi. An algorithm is an effective method for finding out the solution for a given problem. It is a sequence of instruction that conveys the method to address a problem Algorithm : Step by step procedure to solve a computational problem is called Algorithm. or An Algorithm is a step-by-step plan for a computational procedure that possibly begins with an input and yields an output value in a finite number of steps in order to solve a particular problem. An algorithm produces one or more outputs and may have zero or more inputs which are externally supplied. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 2 INTRODUCTION problem algorithm input computer output The notion of the algorithm ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 3 INTRODUCTION  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.  The important aspects of algorithm design include creating an efficient algorithm to solve a problem in an efficient way using minimum time and space.  To solve a problem, different approaches can be followed. Some of them can be efficient with respect to time consumption, whereas other approaches may be memory efficient. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 4 PROPERTIES OF ALGORITHM TO EVALUATE AN ALGORITHM WE HAVE TO SATISFY THE FOLLOWING CRITERIA: 1.INPUT: The Algorithm should be given zero or more input. 2.OUTPUT: At least one quantity is produced. For each input the algorithm produced value from specific task. DEFINITENESS: Each instruction is clear and specified. 4.FINITENESS: The algorithm terminates after a finite number of steps. 5.EFFECTIVENESS: Every instruction must very basic, simple and sufficient. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 5 ALGORITHM (CONTD…)  A well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.  Written in a pseudo code which can be implemented in the language of programmer’s choice. ALGORITHM: is a systematic, logical approach that provides a step-by-step procedure for computers to solve a specific problem. PSEUDO CODE: is a simplified version of programming codes, written in plain English language and used to outline a program before its implementation. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 6 STUDY OF ALGORITHMS Expressing algorithms ◦ Define a problem precisely and abstractly ◦ Presenting algorithms using pseudocode Algorithm validation ◦ Prove that an algorithm is correct Algorithm analysis ◦ Time and space complexity ◦ Predict the cost of an algorithm in terms of resources and performance Designing algorithms ◦ Design algorithms which minimize the cost ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 7 How To Write an Algorithm Step-1:start Step-1: start Step-2:Read a,b,c Step-2: Read a,b,c Step-3:if a>b Step-3:if a>b then go to step 4 if a>c otherwise go to step 5 print a is largest Step-4:if a>c then else print a is largest otherwise if b>c print c is largest print b is largest Step-5: if b>c then else print b is largest otherwise print c is largest print c is largest Step-4 : stop step-6: stop ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 8 ALGORITHM SPECIFICATION Algorithm can be described (Represent) in four ways. 1.Natural language like English: When this way is chooses, care should be taken, we should ensure that each & every statement is definite. (no ambiguity) 2. Graphic representation called flowchart: This method will work well when the algorithm is small& simple. 3. Pseudo-code Method: In this method, we should typically describe algorithms as program, which resembles language like Pascal & Algol(Algorithmic Language). 4.Programming Language: we have to use programming language to write algorithms like C, C++,JAVA etc. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 9 2.How to validate an algorithm: Once an algorithm is created it is necessary to show that it computes the correct output for all possible legal input , this process is called algorithm validation. 3.How to analyses an algorithm: Analysis of an algorithm or performance analysis refers to task of determining how much computing Time & storage algorithms required. a) Computing time-Time complexity: Frequency or Step count method b) Storage space- To calculate space complexity we have to use number of input used in algorithms. 4.How to test the program: Program is nothing but an expression for the algorithm using any programming language. To test a program we need following a) Debugging: It is processes of executing programs on sample data sets to determine whether faulty results occur & if so correct them. b) Profiling or performance measurement is the process of executing a correct program on data set and measuring the time & space it takes to compute the result. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 10 Need of Algorithm 1. To understand the basic idea of the problem. 2. To find an approach to solve the problem. 3. To improve the efficiency of existing techniques. 4. To understand the basic principles of designing the algorithms. To compare the performance of the algorithm with respect to other techniques. 6. It is the best method of description without describing the implementation detail. 7. The Algorithm gives a clear description of requirements and goal of the problem to the designer. 8. A good design can produce a good solution. 9. To understand the flow of the problem. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 11 FLOWCHART  A flowchart is a diagram that depicts a process, system or computer algorithm.  A graphical representation of the sequence of operations in an information system or program.  Emphasis individual steps and their interconnection.  Control flow from one action to the next. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 12 FLOWCHART SYMBOLS ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 13 EXAMPLE Convert the length of feet to centimetre Pseudo code Input the length of feet (Lft) Calculate the length in cm (Lcm) by multiplying Lft with 30 Print length in cm (LCM) ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 14 EXAMPLE Convert the length of feet to centimetre Algorithm Step1: Input Lft Step2: Lcm=Lft*30 Step3: print Lcm ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 15 EXAMPLE Convert the length of feet to centimetre Flowchart ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 16 PERFORMANCE ANALYSIS Performance Analysis: An algorithm is said to be efficient and fast if it take less time to execute and consumes less memory space at run time is called Performance Analysis. 1. SPACE COMPLEXITY: The space complexity of an algorithm is the amount of Memory Space required by an algorithm during course of execution is called space complexity.There are three types of space a) Instruction space :executable program b) Data space: Required to store all the constant and variable data space. c) Environment: It is required to store environment information needed to resume the suspended space. 2. TIME COMPLEXITY: The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 17 Space complexity Now there are two types of space complexity a) Constant space complexity b) Linear(variable)space complexity ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 18 1.Constant space complexity: A fixed amount of space for all the input values. Example : int square(int a) { return a*a; } Here algorithm requires fixed amount of space for all the input values. ‫ كلية تكنولوجيا‬- ‫جامعة اقليم سبا‬ 31-Oct-24 www.usr.ac 19 2.Linear space complexity: The space needed for algorithm is based on size.  Size of the variable ‘n’ = 1 word  Array of a values = n word  Loop variable = 1 word  Sum variable = 1 word Example: int sum(int A[],int n) { n int sum=0,i; 1 for (i=0;i

Use Quizgecko on...
Browser
Browser