Anna University Regulation 2013 Information Technology (IT) CS6402 DAA Notes for all 5 units are provided below. Download link for IT 4th SEM CS6402 Design & Analysis of Algorithms Lecture Notes are listed down for students to make perfect utilization and score maximum marks with our study materials.
1.2.2 MEASURING AN INPUT SIZE
An algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
In most cases, selecting such a parameter is quite straightforward.
For example, it will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists. For the problem of evaluating a polynomial p(x) = a n x n + . . . + a 0 of degree n, it will be the polynomial’s degree or the number of its coefficients, which is larger by one than its degree.
There are situations, of course, where the choice of a parameter indicating an input size does matter.
Example – computing the product of two n-by-n matrices.
There are two natural measures of size for this problem. The matrix order n. The total number of elements N in the matrices being multiplied.
Since there is a simple formula relating these two measures, we can easily switch from one to the other, but the answer about an algorithm’s efficiency will be qualitatively different depending on which of the two measures we use.
The choice of an appropriate size metric can be influenced by operations of the algorithm in question. For example, how should we measure an input’s size for a spellchecking algorithm? If the algorithm examines individual characters of its input, then we should measure the size by the number of characters; if it works by processing words, we should count their number in the input.
We should make a special note about measuring size of inputs for algorithms involving properties of numbers (e.g., checking whether a given integer n is prime). For such algorithms, computer scientists prefer measuring size by the number b of bits in the n’s binary representation:
b= log2n +1
This metric usually gives a better idea about efficiency of algorithms in question.
1.2.3 UNITS FOR MEASURING RUN TIME:
We can simply use some standard unit of time measurement-a second, a millisecond, and so on-to measure the running time of a program implementing the algorithm. There are obvious drawbacks to such an approach.
They are Dependence on the speed of a particular computer Dependence on the quality of a program implementing the algorithm The compiler used in generating the machine code The difficulty of clocking the actual running time of the program. Since we are in need to measure algorithm efficiency, we should have a metric that does not depend on these extraneous factors. One possible approach is to count the number of times each of the algorithm’s operations is executed. This approach is both difficult and unnecessary.
The main objective is to identify the most important operation of the algorithm, called the basic operation, the operation contributing the most to the total running time, and compute the number of times the basic operation is executed.
WORST CASE, BEST CASE AND AVERAGE CASE EFFICIENCY
It is reasonable to measure an algorithm’s efficiency as a function of a parameter indicating the size of the algorithm’s input. But there are many algorithms for which running time depends not only on an input size but also on the specifics of a particular input. Example, sequential search. This is a straightforward algorithm that searches for a given item (some search key K) in a list of n elements by checking successive elements of the list until either a match with the search key is found or the list is exhausted. Here is the algorithm’s pseudo code, in which, for simplicity, a list is implemented as an array. (It also assumes that the second condition A[i] i= K will not be checked if the first one, which checks that the array’s index does not exceed its upper bound, fails.)
ALGORITHM
Sequential Search(A[0..n -1], K) //Searches for a given value in a given array by sequential search //Input: An array A[0..n -1] and a search key K //Output: Returns the index of the first element of A that matches K // or -1 ifthere are no matching elements i 0 while i < n and A[i] ≠ K do i i+1 if i < n return i else return -1 Clearly, the running time of this algorithm can be quite different for the same list size n.
Worst case efficiency
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size. In the worst case, when there are no matching elements or the first matching element happens to be the last one on the list, the algorithm makes the largest number of key comparisons among all possible inputs of size n:
Cworst(n) = n.
The way to determine is quite straightforward To analyze the algorithm to see what kind of inputs yield the largest value of the basic operation’s count C(n) among all possible inputs of size n and then compute this worst case value Cworst(n)
The worst-case analysis provides very important information about an algorithm’s efficiency by bounding its running time from above. In other words, it guarantees that for any instance of size n, the running time will not exceed Cworst(n) its running time on the worst-case inputs.
CS6402 DAA Unit 1 notes – Download Here
CS6402 DAA Unit 1 notes – Download Here
CS6402 DAA Unit 2 notes – Download Here
CS6402 DAA Unit 3 notes – Download Here
CS6402 DAA Unit 4 notes – Download Here
CS6402 DAA Unit 5 notes – Download Here
If you require any other notes/study materials, you can comment in the below section.
Related Links
For CS6402 DAA Previous Year Question Papers – Click here
For CS6402 DAA Question Bank/2marks 16marks with answers – Click here
For CS6402 DAA Important Questions/Answer Key – Click here
Search Terms
Anna University 4th SEM IT DAA Lecture Notes
CS6402 Design & Analysis of Algorithms Notes free download
Anna University IT DAA Notes Regulation 2013
CS6402 Notes, DAA Unit wise Lecture Notes – IT 4th Semester