2CS503 Design & Analysis of Algorithm PDF

2CS503 Design & Analysis of Algorithm Introduction to course Introduction to Algorithm References 1. Charles E. Leiserson, Thomas H. Cormen, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms, PHI 2. Ellis Horowitz, SartajSahni, Sanguthevar Rajasekharan, Fundamentals of Computer...

2CS503 Design & Analysis of Algorithm Introduction to course Introduction to Algorithm References 1. Charles E. Leiserson, Thomas H. Cormen, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms, PHI 2. Ellis Horowitz, SartajSahni, Sanguthevar Rajasekharan, Fundamentals of Computer Algorithms,Galgotia. 3. Jean-Paul Tremblay and Paul G. Sorenson, An Introduction to Data Structures with Applications, Tata McGraw Hill 4. Karumanchi, Narasimha, Data Structures and Algorithms Made Easy, CareerMonk Publications. Design & Analysis of Algorithm 3 Syllabus Blog Link: http://3cs1103pbt.wordress.com/ Course Site: https://sites.google.com/a/nirmauni.ac.in/3cs1 103---data-structures-and-algorithm/ All resources will be available on Moodle Design & Analysis of Algorithm 4 Teaching & Evaluation Scheme Teaching Scheme: Evaluation Methodology: LPW SEE CE Exam Duration Continuous Evaluation of 3.0 Hrs Continuous Evaluation lab + Semester Endexam Component Weightage 20%(75+25) 40% 40% (CT-35 +Sessional-35 + Conceptual Test 30) Assignments in CE: MOOC Design & Analysis of Algorithm 5 What is an Algorithm? A step-by-step procedure, to solve the different kinds of problems. Suppose, we want to make a Chocolate Cake. Input Process Output Ingredients Recipe Cake An unambiguous sequence of computational steps that transform the input into the output. Design & Analysis of Algorithm 6 What is an Algorithm? A process or a set of rules to be followed to achieve desired output, especially by a computer. Input Algorithm Program Output An algorithm is any well-defined computational procedure that takes some value, or a set of values as input and produces some value, or a set of values as output. Design & Analysis of Algorithm 7 Characteristics of An Algorithm Finiteness: An algorithm must always terminate after a finite number of steps. Definiteness: Each step of an algorithm must be precisely defined. Input: An algorithm has zero or more inputs. Output: An algorithm must have at least one desirable output. Effectiveness: All the operations to be performed in the algorithm must be sufficiently basic and essential. Correctness: An algorithm must produce correct output on every possible input instance of the problem. It is the most important property of an algorithm. Design & Analysis of Algorithm 8 Simple Multiplication Methods 1. American approach 2. English approach 981 981 1 23 4 1 23 4 3924 981 2943 1962 1962 2943 981 3924 1210554 1210554 Design & Analysis of Algorithm 9 Introduction What is an algorithm? Algorithms are the ideas behind computer programs. An algorithm is the thing which stays the same whether the program is in Pascal running on a Cray in New York or is in BASIC running on a Macintosh in Kathmandu! An algorithm has to solve a general, well-specified problem. An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. Design & Analysis of Algorithm 10 What is an algorithm? We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship. An algorithmic problem is specified by describing the complete set of instances it must work on and what desired properties the output must have. For example, we might need to sort a sequence of numbers into nondecreasing order. Here is how we formally define the sorting problem: Design & Analysis of Algorithm 11 Instance of a problem ⮚For example, given the input sequence (31, 41, 59, 26, 41, 58), a sorting algorithm returns as output the sequence (26, 31, 41, 41, 58, 59). Such an input sequence is called an instance of the sorting problem. ⮚In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem. Design & Analysis of Algorithm 12 When can we say that the algorithm is correct? An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves the given computational problem. An incorrect algorithm might not halt at all on some input instances, or it might halt with an incorrect answer. Contrary to what you might expect, incorrect algorithms can sometimes be useful, if we can control their error rate. Ordinarily, however, we shall be concerned only with correct algorithms. Design & Analysis of Algorithm 13 Design of an algorithm Designing an algorithm refers to the method/process used to solve the well-specified computational problem. Two basic design methods are:- Recursive: A recursive algorithm works by splitting the input into two or more smaller inputs, calls itself to solve smaller inputs and then combine partially computed results to solve the original problem. Ex:- Merge Sort, Quick Sort Non-recursive: A non-recursive algorithm works on “all at once” approach. It does not split the original input. Ex:- Bubble Sort, Insertion Sort Design & Analysis of Algorithm 14 Types of problem which can be solved by algorithms: Managing, manipulating & retrieving the voluminous data Shortest Route finding Public-key cryptography and digital signatures Resource scheduling, etc. ⮩ A political candidate may want to determine where to spend money buying campaign advertising in order to maximize the chances of winning an election. ⮩ An airline may wish to assign crews to flights in the least expensive way possible, making sure that each flight is covered and that government regulations regarding crew scheduling are met. ⮩ An Internet service provider may wish to determine where to place additional resources in order to serve its customers more effectively. ⮩ All of these are examples of problems that can be solved using linear programming Design & Analysis of Algorithm 15 Efficiency of an Algorithm – Does it Matter? Different algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than differences due to hardware and software. As an example, we will see two algorithms for sorting. The first, known as insertion sort, takes time roughly equal to c1*n2 to sort n items, where c1 is a constant that does not depend on n. That is, it takes time roughly proportional to n2. The second, merge sort, takes time roughly equal to c2 *nlogn, where lg n stands for log2 n and c2 is another constant that also does not depend on n. Insertion sort typically has a smaller constant factor than merge sort, so that c1 < c2. We shall see that the constant factors can have far less of an impact on the running time than the dependence on the input size n. Design & Analysis of Algorithm 16 Efficiency of an Algorithm – Does it Matter? Let’s write insertion sort’s running time as c1*n*n and merge sort’s running time as c2*n*logn. Then we see that where insertion sort has a factor of n in its running time, merge sort has a factor of log n, which is much smaller. (For example, when n = 1000, log n is approximately 10, and when n equals one million, log n is approximately only 20.) Although insertion sort usually runs faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of log n v/s n will more than compensate for the difference in constant factors. No matter how much smaller c1 is than c2, there will always be a crossover point beyond which merge sort is faster. Design & Analysis of Algorithm 17 Efficiency of an Algorithm – Does it Matter? Different algorithms, constants & hardware proficiency Problem: Sort 10 million numbers Computer A: insertion sort, 10bi/s, c1=2 Computer B: merge sort, 10mi/s, c2=50 Computer A: Computer B: Design & Analysis of Algorithm 18 Analyzing Algorithms Analysing an algorithm means predicting the resources that the algorithm requires What is to be analyzed? Memory, communication bandwidth, hardware, computational time One processor Random Access Machine (RAM) model Implementation Technology Instructions are executed one after another, with no concurrent operations Instructions of RAM model Arithmetic (such as add, subtract, multiply, divide, remainder, floor, ceiling) Data movement (load, store, copy) and control (conditional and unconditional branch, subroutine call and return) Each such instruction takes constant amount of time – Primitive / Elementary Operations In the literature of “Algorithms”, space and time requirements of an algorithm are commonly referred to as “Space Complexity” and “Time Complexity” respectively. Design & Analysis of Algorithm 19 Analyzing Algorithms Input Size ⮩ The best notion for input size depends on the problem being studied. ⮩ For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. ⮩ For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. ⮩ Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. ⮩ For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. ⮩ We shall indicate which input size measure is being used with each problem we study. Design & Analysis of Algorithm 20 Analyzing Algorithms Running Time ⮩ The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. For the moment, let us adopt the following view. ⮩ A constant amount of time is required to execute each line of our pseudocode. ⮩ One line may take a different amount of time than another line, but we shall assume that each execution of the ith line takes time ci, where ci is a constant. (Precisely, ci bounds the time required to execute ith line, from above or below, based on whether we want to think of upper bound or lower bound on time requirement.) Design & Analysis of Algorithm 21 Analyzing Algorithms Space Complexity : Space complexity is a measure of the amount of working storage (memory) an algorithm needs. That means, how much memory, in the worst case, is needed at any point in the algorithm. Ex:- int sum(int x, int y, int z) { int r = x * y * z; return r; } The code requires 3 units of space for the parameters and 1 unit for the local variable. Design & Analysis of Algorithm 22 Analyzing Algorithms Time Complexity : Time complexity is a measure of the amount of execution time an algorithm needs. It is most commonly estimated by counting the number of elementary steps (operations) performed by any algorithm to finish its execution. Ex:- int sum(A,n) // A is an array and n is the number of elements in A { total = 0; // cost = 1 and no. of times = 1 for i = 0 to n-1 // cost = 2 and no. of times = n+1 sum = sum + A[i]; // cost = 3 and no. of times = n return sum; // cost = 4 and no. of times = 1 } Time required = 1(1) + 2(n+1) + 3(n) + 4(1) = 1 + 2n +2 + 3n + 4 = 5n + 7 = cn + b (c and b are constants) Design & Analysis of Algorithm 23 Significance of Time Complexity As memory is available cheaply and in abundance, the space complexity of an algorithm is not considered as an effective measure for analysing an algorithm’s performance. Running time of an algorithm with respect to the problem instances of different sizes, is often considered to be the decisive measure in differentiating between average algorithms and the optimal one. Thus, analysing the time complexity of an algorithm is more important than analysing the space complexity. Design & Analysis of Algorithm 24