Design and Analysis of Algorithms.pptx

Design and analysis of algorithm

1. Design and Analysis of Algorithms

2. What is an algorithm? Algorithm is a set of steps to complete a task. For example, Task: to make a cup of tea. Algorithm: • add water and milk to the kettle, • boil it, add tea leaves, • Add sugar, and then serve it in cup.

3. What is Computer algorithm? ‘’a set of steps to accomplish or complete a task that is described precisely enough that a computer can run it’’ Described precisely: very difficult for a machine to know how much water, milk to be added etc. in the above tea making algorithm. These algorithms run on computers or computational devices.For example, GPS in our smartphones, Google hangouts. GPS uses shortest path algorithm. Online shopping uses cryptography which uses RSA algorithm.

4. Characteristics of an algorithm:- • Must take an input. • Must give some output(yes/no,value etc.) • Definiteness –each instruction is clear and unambiguous. • Finiteness –algorithm terminates after a finite number of steps. • Effectiveness –every instruction must be basic i.e. simple instruction

5. Expectation from an algorithm • Correctness:- Correct: Algorithms must produce correct result. Produce an incorrect answer:Even if it fails to give correct results all the time still there is a control on how often it gives wrong result. Eg.Rabin-Miller Primality Test (Used in RSA algorithm): It doesn’t give correct answer all the time.1 out of 250 times it gives incorrect result. Approximation algorithm: Exact solution is not found, but near optimal solution can be found out. (Applied to optimization problem.) Less resource usage: Algorithms should use less resources (time and space).

6. Expectation from an Algorithm • How long the algorithm takes: will be represented as a function of the size of the input. • f(n)→how long it takes if ‘n’ is the size of input. • How fast the function that characterizes the running time grows with the input size. • “Rate of growth of running time”. • The algorithm with less rate of growth of running time is considered better.

7. Resource usage: Here, the time is considered to be the primary measure of efficiency .We are also concerned with how much the respective algorithm involves the computer memory.But mostly time is the resource that is dealt with. And the actual running time depends on a variety of backgrounds: like the speed of the Computer, the language in which the algorithm is implemented, the compiler/interpreter, skill of the programmers etc. So, mainly the resource usage can be divided into: 1.Memory (space) 2.Time

8. Algorithm Specification • We can describe an algorithm in many ways. • A natural language like English, • Graphic representations: flowcharts (recommended if the algorithm is small and simple). • A pseudocode that resembles C

9. Algorithm Specification 1. Comments begin with // and continue until the end of line. 2. Blocks are indicated with matching braces:{ and }. • A compound statement (i.e., a collection of simple statements) can be represented as a block. • The body of a procedure also forms a block. • Statements are delimited by ;.

10. 3. An identifier begins with a letter. • The data types of variables are not explicitly declared. The types will be clear from the context. Whether a variable is global or local to a procedure will also be evident from the context. • We assume simple data types such as integer, float, char, boolean, and so on. • Compound data types can be formed with records.

11. For example: node= record { datatype_1 data_1; : datatype_n data_n; node *link; }

12. 4. Assignment of values to variables is done using the assignment statement variable:= expression; 5. There are two Boolean values true and false. • In order to produce these values, the logical operators and, or, and not and the relational operators <, <=, =, <>, >, >= are provided 6. Elements of multi-dimensional arrays are accessed using [ and ]. • For example, if A is a two dimensional array, the (i,j)th element of the array is denoted as - A[i, j]. • Array indices start at zero.

13. 7. The following looping statements are employed: for, while, and repeat- until. • The while loop takes the following form: while (condition) do { (statement_1) : (statement_n) }

14. • As long as (condition)is true, the statements get executed. When (condition) becomes false, the loop is exited. • The value of (condition) is evaluated at the top of the loop. • The general form of a for loop is for variable := value1 to value2 step step do { (statement_1) : (statement_n) }

15. • Here value1, value2, and step are arithmetic expressions. • A variable of type integer or real or a numerical constant is a simple form of an arithmetic expression. • The clause "step step" is optional and taken as +1 if it does not occur, step could either be positive or negative. • Variable is tested for termination at the start of each iteration.

16. Variable := value1; fin :=value2; incr:=step; while ((variable - fin) * step <= 0) do { Statement_1 : statement_n variable:=variable+ incr; }

17. A repeat-until statement is constructed as follows: repeat statement_1 : statement_n until (condition) The statements are executed as long as {condition) is false. The value of {condition) is computed after executing the statements

18. • The instruction break; can be used within any of the above looping instructions to force exit. • In case of nested loops, break; results in the exit of the innermost loop that it is a part of. • A return statement within any of the above also will result in exiting the loops. • A return statement results in the exit of the function itself

19. 8. A conditional statement has the following forms: if {condition) then {statement) if {condition) then {statement1) else (statement2) Here (condition) is a boolean expression and (statement), (statement1) and (statement2) are arbitrary statements (simple or compound)

20. We also employ the following case statement: case { :{condition_1): (statement_1) : : (condition_n): (statement_n) :else:(statement_n + 1) }

21. 9. Input and output are done using the instructions read and write. No format is used to specify the size of input or output quantities. 10. There is only one type of procedure: Algorithm. An algorithm consists of a heading and a body. The heading takes the form Algorithm Name ((parameter list)) { }

22. Asymptotic notation It is a way to describe the characteristics of a function in the limit. • It describes the rate of growth of functions. • Focus on what’s important by abstracting away low-order terms and constant factors. • It is a way to compare “sizes” of functions: O≈ ≤ Ω≈ ≥ Θ ≈ = o ≈ < ω ≈ >

23. • One goal of this subject is to develop skills for making evaluative judgments about algorithms. • There are many criteria upon which we can judge an algorithm. • Does it do what we want it to do? • Does it work correctly according to the original specifications of the task? • Is there documentation that describes how to use it and how it works? • Are procedures created in such a way that they perform logical subfunctions? • Is the code readable?

24. Space/Time complexity: • The space complexity of an algorithm is the amount of memory it needs to run to completion. • The time complexity of an algorithm is the amount of computer time it needs to run to completion. • Performance evaluation can be loosely divided into two major phases: • a priori estimates • a posteriori testing • We refer to these as performance analysis and performance measurement respectively.

25. Space Complexity: • The space needed by all algorithms is the sum of the following components. • A fixed part that is independent of the characteristics (e.g., number, size) of the inputs and outputs. • The instruction space (i.e., space for the code), • Space for simple variables • Space for fixed-size component variables Space for constants, and so on. • A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved. • The space needed by referenced variables (this depends on instance characteristics) • The recursion stack space (this depends on the instance characteristics).

26. Time Complexity • The time T(P) taken by a program P is the sum of the compile time and the run (or execution) time. • The compile time does not depend on the instance characteristics. • A compiled program will be run several times without recompilation. • We will consider only the run time of a program. • This run time is denoted by tp (instance characteristics).

27. Because many of the factors tp depends on are not known at the time a program is conceived, it is reasonable to attempt only to estimate tp. • If we knew the characteristics of the compiler to be used, we could proceed to determine the number of additions, subtractions, multiplications, divisions, compares, loads, stores, and soon, that would be made by the code for P. • So, we could obtain an expression for tp(n) of the form