Algorithms for problem solvingPerformance analysis of algorithmsAlgorithmssteps needed to solve the problemDefinition of an algorithman ordered sequence ofwell-defined and effective operations which,when executed,will terminate in a finite amount of timeand produce correct resultSoftware developmentunderstand and define the problemwhat is it that needs to be solvedIdentify an approachthe basic equations, relations, etcDevelop and specify an algorithmsequence of steps to be executedspecify how data is organized.Evaluate the algorithmalways provide correct results ?efficient ?Coding (or Programming).Test and validateDebug programconfirm -- gives expected results?confirm efficiency.Documentationproblem, its solution, algorithm, program, testing procedureProgram maintenanceMake necessary changes if errors are foundEnsure that it meets user changing requirementsComplexity of testing elements of an arrayAlgorithms for problemsolving Performance analysis ofalgorithmsAlgorithms– steps needed to solve the problem• Definition of an algorithm• an ordered sequence of well-defined and effective operations which, when executed, will terminate in a finite amount of time and produce correct result– Software development• understand and define the problem– what is it that needs to be solved• Identify an approach– the basic equations, relations, etc• Develop and specify an algorithm– sequence of steps to be executed– specify how data is organized.• Evaluate the algorithm– always provide correct results ? efficient ?• Coding (or Programming).Test and validate• Debug program• confirm -- gives expected results?• confirm efficiency.• Documentation– problem, its solution, algorithm, program, testing procedure• Program maintenance• Make necessary changes if errors are found• Ensure that it meets user changing requirementsFinding largest sequence of OnesConsider a two dimensional array. Each row consists of sequenceof Ones, followed by sequence of Zeros. The problem is to find themaximum number of Ones in any row. 111111000000000000000000111111111111100000000000111110000000000000000000111111111111111111111000111100000000000000000000111111111111110000000000110000000000000000000000Algorithm 1:Let any element of this 2 dimensional array of rows x cols bea(j,k)max = 0;for j = 1 to rows {find total number of Ones; if total >max set max = total;}How many operations involved? = cols x rowsAlgorithm 2:Find the position of last 1 in first row.Start examining second row from that position onward.Get the position of last 1.Start next row from that position.If that position contains zero, skip that row.Keep a record of row where change was made.Stop when all rows examined.How many operations now? ( number of cols+ no. of rows ).Measuring Performance of AlgorithmsThere are two aspects of algorithmic performance:• Time- Instructions take time.- How fast does the algorithm perform?- What affects its runtime?• Space- Data structures take space- What kind of data structures can be used?- How does choice of data structure affect the runtime?Algorithms can not be compared by running them on computers. Run time is system dependent.Even on the same computer runtime would depend on language used for coding.Real time units like microseconds not to be used.Generally concerned with how the amount of work varies with the data.Measuring Time ComplexityCounting number of operations involved in the algorithms to handle n items.Meaningful comparison possible for very large values of n.Algorithm Analysis: LoopsLOOP 1:a= 0; b = 0;for (k=0; k< n; k++) {for (j = 0; j < m; j++)a= a + j;} It takes nm addition operations. LOOP 2:a= 0; b = 0;for (k=0; k< n; k++) { a= a+k;for (j = 0; j < m; j++)b= b + j;} It takes nm+ n addition operations. LOOP 3:total = 0;for (k=0; k<n; ++k) {rows[k] = 0;for (j = 0; j <n; ++j){rows[k] = rows[k] + matrix[k][j];total = total + matrix[k][j];}} It takes 2n2 addition operations LOOP 4:total =0;for (k=0; k<n; ++k)rows[k] = 0;for (j = 0; j <n; ++j)rows[k] = rows[k] + matrix[k][j];total = total + rows[k];}This one takes n2 + n operations .Complexity of testing elements of an arrayLet ar[ ] be an array containing n integer values. It is desired to find number of elements having values more than 50. for(k = 0; k<n; k++) if(ar[k]>50) sum+=ar[k];for each value one comparison is carried out, and the assignment statement may get executed only for some of the values.Worst case: All values are more than 50, (all values are checked and total gets incremented every time).no. of operations = 2nBest case: When all values are less than 50. (all values are checkedand none gets incrementednumber of operations = nComplexity of Linear Search: searching for an element in an arrayConsider the task of searching a list to see if it contains a particularvalue.• A useful search algorithm should be general.• Work done varies with the size of the list• What can we say about the work done for list of any length?i = 0;while (i<MAX && array[i] != target) i = i + 1;if (i <MAX) printf (“Yes, target found \n” );elseprintf(“No, target not found \n” );The work involved : Checking target value with each of the n elements. no. of operations: 1 (best case)n (worst case)n/2 (average case)Computer scientists tend to be concerned about the worst time complexity. Worst Case complexity. The worst case guarantees that the performance of the algorithm will be at least as good as the analysis indicates.Average Case Complexity:It is the best statistical estimate of actual performance, and tells us how well an algorithm performs if you average the behavior over all possible sets of input data. However, it requires considerable mathematical sophistication to do the average case analysis.Complexity of Selection SortThe sorting process consists of reordering the elements in an arrayso that they are arranged in an increasing or decreasing sequence.One simple sorting method is known as the Selection sort. To sortthe elements in ascending order, it examines each element in thelist, finds the smallest element and swaps it with the first elementin the array. Then it examines the array starting with the secondelement, finds the smallest element and swaps it with the secondelement. The steps are repeated till it has swapped the last elementin place.56 25 37 58 95 19 73 3019 25 37 58 95 56 73 30Algorithm for selection sort:for lh = 0 to n {rh = lh,for j = lh +1 to