{"id":62,"date":"2018-07-19T04:44:02","date_gmt":"2018-07-19T04:44:02","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=62"},"modified":"2018-07-25T07:08:46","modified_gmt":"2018-07-25T07:08:46","slug":"62","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/62\/","title":{"rendered":"More Decrease and Conquer Algorithms"},"content":{"raw":"<div>\r\n<p style=\"text-align: center\"><strong>Module 16<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>More Decrease and Conquer Algorithms<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">This module 16 focuses on an important design paradigm called decrease and conquer by variable factor algorithms. The Learning objectives of this<\/p>\r\n\r\n<ul>\r\n \t<li>To explain Euclid Algorithm<\/li>\r\n \t<li>To explain Interpolation Search<\/li>\r\n \t<li>To explain Order statistics<\/li>\r\n \t<li>To explain Deterministic Selection<\/li>\r\n<\/ul>\r\n<strong>Decrease and Conquer Design paradigm:<\/strong>\r\n<p style=\"text-align: justify\">The decrease and conquer paradigm is based on problem reduction strategy. Problem reduction is a design strategy that aims to reduce a given problem to another problem with a reduced problem with smaller size. Then, attempts are made to solve the problem. Decrease and conquer is a design paradigm that uses the problem reduction strategy. It is also known as the incremental or inductive approach. As discussed earlier in the previous module, the steps of decrease and conquer is given as follows:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Reduce problem instance to same problem with smaller Instance<\/li>\r\n \t<li style=\"text-align: justify\">Solve problem of smaller instance<\/li>\r\n \t<li style=\"text-align: justify\">Extend solution of smaller instance to obtain solution to original problem with larger instance<\/li>\r\n<\/ol>\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">Thus, it can be seen that the logic involves the following steps:<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">Establish the relationship between problem of the given instance and its reduced instance of the smaller problem<\/li>\r\n \t<li style=\"text-align: justify\">Exploit this relation top-down or Bottom-up<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">Design and conquer design paradigm can be implemented using both top-down or bottom-up approach. Also, this design paradigm is known as inductive or incremental approach.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Type of Decrease and Conquer Strategy<\/strong><\/p>\r\n<p style=\"text-align: justify\">Based on the decreasing factor, the decrease-and-conquer strategy can further be categorized into the following types:<\/p>\r\n\r\n<ol>\r\n \t<li>Decrease by a constant<\/li>\r\n \t<li>Decrease by a constant factor<\/li>\r\n \t<li>Decrease by a variable factor<\/li>\r\n<\/ol>\r\n<strong>Decrease by Variable Factor Method<\/strong>\r\n<p style=\"text-align: justify\">One more category of the decrease-and-conquer algorithm is decrease by a variable factor. It can be observed that as the name implies, the decreasing factor varies. Some examples of the algorithms that belong to this category are interpolation search, selection, and deterministic selection algorithms.<\/p>\r\n&nbsp;\r\n\r\nLet us start the discussion on Euclid algorithm.\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>Euclid Algorithm<\/strong>\r\n<p style=\"text-align: justify\">Euclid algorithm is one of the oldest algorithms designed by Euclid about 300 B.C. Euclid algorithm is useful to find the largest integer that divides both a and b. For example, GCD of two integers 36 and 24 , GCD(36,24) can be obtained using factoring method. Let us try , one of the standard method of finding GCD using factoring method: Factor a and b into primes and then choose the common ones:<\/p>\r\n&nbsp;\r\n\r\n\u2013\u00a0\u00a0 24 = 2 x 2 x 2 x 3 and 36 = 2 x 2 x 3 x3\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Hence, GCD of 36 and 24 can be obtained as 2 x 2 x 3 = 12. Factoring method takes a lot of time. Therefore, a recursive method based on Euclid method can be done as follows: Euclid\u2019s algorithm is based on repeated application of equality<\/p>\r\n&nbsp;\r\n\r\nGCD(<em>m, n<\/em>) = GCD(<em>n, m<\/em> mod <em>n<\/em>)\r\n\r\n&nbsp;\r\n\r\nIt can be done as follows:\r\n\r\ngcd(36, 24) = gcd(24, 36 mod 24)\r\n\r\n=\u00a0 gcd(24, 12)\r\n\r\n=\u00a0 gcd(12, 24 mod 12)\r\n\r\n=\u00a0 gcd(12,0)\r\n\r\n=\u00a0 12\r\n\r\n&nbsp;\r\n\r\nThe Iterative algorithm for finding GCD is given as follows:\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>Iterative form:<\/strong>\r\n<ol>\r\n \t<li>Read two numbers x and y<\/li>\r\n \t<li>If y = 0, then return x as GCD<\/li>\r\n \t<li>Repeat While y is not zero, Divide x by y and set remainder to r<\/li>\r\n<\/ol>\r\nChange value of x to y Change value of y by r\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The same algorithm can be done using recursive form as illustrated in the numerical example. The informal algorithm for finding GCD is given as follows:<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Recursive form:<\/strong><\/p>\r\n&nbsp;\r\n\r\nEuclid (x,y)\r\n\r\n1. Input numbers x and y\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2. if y == 0 return x\r\n\r\nelse\r\n\r\nreturn Euclid(y, x mod y)\r\n\r\nThe formal algorithm for Euclid algorithm is as follows:\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Algorithm Euclid(x,y)<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">%%\u00a0 Input: x and y Begin<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">If (y == 0) return x<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Else return Euclid(y, x mod y) End if<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">End.<\/span>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>Complexity Analysis:<\/strong>\r\n<p style=\"text-align: justify\">What is the complexity analysis of Euclid algorithm? One can prove that the size, measured by the second number, decreases at least by half after two consecutive iterations. This, the complexity analysis of Euclid algorithm is T(<em>n<\/em>) \u00ce O(log <em>n<\/em>) .<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Interpolation Search<\/strong><\/p>\r\n<p style=\"text-align: justify\">Interpolation search is another example of decrease and conquer by a variable factor. Interpolation search is faster than binary search. To illustrate this, let us consider the following scenario: Searching for the element 18 in an array, A = 12 13 14 16 18. The binary search for item 18 starts by finding the middle element 14. Then it proceeds. It can be observed that the idea of even split as in the case of binary search is not of much use here. On the contrary, if one searches from right to left, one can find easily the element 18.\u00a0\u00a0<span style=\"text-align: initial;font-size: 1em\">The idea of interpolation search is to adopt a modified middle element finding. In the case of interpolation that is closer to the element to be searched. Therefore, interpolation search uses the approximate \u2018middle point\u2019, say C, which is a constant, for finding the target item.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"aligncenter size-full wp-image-225\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1.png\" alt=\"\" width=\"101\" height=\"47\" \/>This approximate middle element or constant <em>C<\/em> replaces the \u2018exact mid\u2019 of the binary search algorithm.\r\n\r\n&nbsp;\r\n\r\nThe informal Interpolation search is given as follows:\r\n\r\n&nbsp;\r\n\r\n1.\u00a0 Read array A and target key k\r\n\r\n2.\u00a0 Computer approximate middle\r\n\r\n<img class=\"aligncenter size-full wp-image-226\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-1.png\" alt=\"\" width=\"101\" height=\"47\" \/>\r\n\r\nHere, k = key, low = first and high = last element\r\n\r\n&nbsp;\r\n\r\n3.\u00a0 Compare k with A[C] if equal return C else recurse . The formal algorithm is given as follows:\r\n\r\n&nbsp;\r\n\r\n<em>Algorithm IS(A[0..n-1], k )<\/em>\r\n\r\n&nbsp;\r\n\r\n%% <em>Input: Array A and key k<\/em>\r\n\r\n<em>\u00a0<\/em>\r\n\r\n%% <em>Output: k if present, -1 if not present Begin<\/em>\r\n\r\n<em>\u00a0<\/em>\r\n\r\n<em>low <\/em>\u00ac 0;\u00a0 high \u00ac<em> n<\/em>-1\r\n\r\n<\/div>\r\n<div>\r\n\r\nwhile <em>low<\/em> \u00a3 high do\r\n\r\n<img class=\"aligncenter size-full wp-image-227\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-2.png\" alt=\"\" width=\"101\" height=\"47\" \/>\r\n\r\nif k <em>=<\/em> A[C] return C else if k <em>&lt;<\/em> A[C]\r\n\r\n&nbsp;\r\n\r\ncall IS(A,l,C-1) else\r\n\r\n&nbsp;\r\n\r\ncall IS(A,C+1,r) End if\r\n\r\n&nbsp;\r\n\r\nEnd While return -1 End\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that the interpolation search is similar to binary search except in finding the middle element.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n<p style=\"text-align: justify\">Interpolation search depends on the distribution of elements of an array. If the elements are distributed uniformly, then the complexity of the algorithm would be <em>O<\/em>(log(log <em>n<\/em>)) . On the other\u00a0 hand, if the distribution is not uniform, the complexity of the algorithm is <em>O<\/em>(<em>n<\/em>). One can observe that for binary search, the complexity of the algorithm is <em>O<\/em>(log <em>n<\/em>) for all cases.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Order Statistics:<\/strong><\/p>\r\n<p style=\"text-align: justify\">The problem of finding the <em>k<\/em>th smallest element in an unordered array is called selection or order statistics. Finding the smallest element in an ordered array is easy, as the first element of an array sorted in an increasing order is the minimum element and the last element is the maximum element. The brute force algorithm is given as follows:<\/p>\r\n\r\n<\/div>\r\n<ul>\r\n \t<li>Input: A set S of n elements and k<\/li>\r\n \t<li>Output: The kth smallest element of S<\/li>\r\n<\/ul>\r\nstep 1: Sort the n elements\r\n<p class=\"hanging-indent\">step 2: Locate the kth element in the sorted list.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\nThe time complexity is O(nlogn)\r\n<p style=\"text-align: justify\">On the other hand, finding these in unordered array is difficult. So, these elements should be sorted first before finding minimum, maximum and median. Deterministic selection is linear finding of these statistics. Let us discuss the statistical terms now:<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Minimum and maximum<\/strong><\/p>\r\n<p style=\"text-align: justify\">In general, ith order statistic: ith smallest element of a set of n elements. The first order statistic is minimum and nth order statistic is maximum.<\/p>\r\n&nbsp;\r\n\r\n<strong>Median<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Median is the \u201chalf-way point\u201d of the set. When \u2018n\u2019 is odd, the median location can be obtained as follows: median = (<em>n+<\/em>1)\/2. In n is even, then lower median, at = <em>n<\/em>\/2 and upper median, at <em>i =<\/em> <em>n<\/em>\/2+1. But lower medi an is always chosen for consistency. This is given as below:<\/p>\r\n<img class=\"aligncenter size-full wp-image-228\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2.png\" alt=\"\" width=\"516\" height=\"160\" \/>\r\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">Blum, Floyd, Pratt, Rivest, and Tarjan proposed a linear-order algorithm for finding the <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th smallest element in a linear order without using the sorting procedure. This algorithm follows the decrease-and-conquer approach, as the strategy is to split the problem into subproblems and then select the appropriate subproblem for finding solutions. The procedure for selecting the <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th smallest element in an unsorted array is given informally as follows:<\/span><\/p>\r\n<img class=\"aligncenter size-full wp-image-229\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3.png\" alt=\"\" width=\"266\" height=\"424\" \/>\r\n<div>\r\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">It can be observed that the algorithm partitions the given array using a partitioning element. Then it finds the rank. The algorithm compares the expected <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th element with the rank to get the appropriate subarray. Then the algorithm is used recursively till the target key is obtained. This concept is illustrated in the following Example 1.<\/span><\/p>\r\n\r\n<\/div>\r\n<strong>Example 1: Find the element k = 3 and k = 7 using the above procedure.<\/strong>\r\n\r\n<img class=\"aligncenter size-full wp-image-230\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4.png\" alt=\"\" width=\"646\" height=\"81\" \/>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Solution<\/strong><\/p>\r\n<p style=\"text-align: justify\">As discussed earlier, the pivot element can be obtained using a partitioning procedure.\u00a0 \u00a0After partitioning, the pivot element is given as below:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-231\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5.png\" alt=\"\" width=\"615\" height=\"69\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here, the number of elements less that pivotal element is <em>A<\/em><em>count<\/em> =3. As, <em>A<\/em><em>count<\/em> = k-1, return the pivot element 4 as the answer for k = 4.<\/p>\r\n&nbsp;\r\n\r\nFor k = 7, count is greater than k \u2013 count -1, 7 \u2013 3 -1 = 3rd element right subarray.\r\n\r\n&nbsp;\r\n\r\nThe process can be repeated on the right subarray. It can be found that the k = 7, is 7.\r\n\r\n&nbsp;\r\n\r\nThe formal algorithm is given as follows:\r\n\r\nAlgorithm Selection(A,k)\r\n\r\n%% Input: k is the smallest item\r\nBegin\r\nFind pivot q\r\nAless = {All elements less than q}\r\nAequal = {q}\r\nAgreater = { Elements greater than q}\r\nCount = number of elements of Aless\r\nIf count = k-1, then return q\r\nelse If count &gt; k-1, then\r\nSelection(Aless,k) else\r\nSelection(Agreater,k-count-1)\r\nEnd if\r\nEnd if\r\nEnd\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">Each time when the pivot element partition the array exactly into two halves, the recurrence equation is\u00a0 T(n)=T(n\/2)+n, where n is required for separating the n elements into two sets. This T(n) =O(n), which is\u00a0 \u00a0the best case. However, in the worst case, the pivot element will be either the largest or the smallest element in the set. Thus, the array is partitioned into only one set of size n-1. Hence the recurrence\u00a0 equation is, T(n)=T(n-1)+n, which is O(n^2)<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Deterministic Selection<\/strong><\/p>\r\n<p style=\"text-align: justify\">The informal algorithm for finding median using deterministic selection is given as follows:\u00a0 Find Median problem \u2013 Deterministic Algorithm\r\nInput: A set A of n distinct numbers and a number i, with 1\uf0a3 i \uf0a3 n.<\/p>\r\nFind median of medians:\r\n<p style=\"text-align: justify\"><img class=\"size-full wp-image-232 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6.png\" alt=\"\" width=\"524\" height=\"289\" \/><\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">The formal segment of deterministic selection is given as follows<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-233 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7.png\" alt=\"\" width=\"432\" height=\"518\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-234 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8.png\" alt=\"\" width=\"514\" height=\"524\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<div>\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>In short, one can conclude as part of this module 16 that<\/li>\r\n \t<li>Euclid algorithm uses decrease and conquer approach.<\/li>\r\n \t<li>Interpolation search is effective than even binary search.<\/li>\r\n \t<li>Selection algorithms finds smallest k in linear time.<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">Deterministic median algorithm finds median in linear time.<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<p class=\"hanging-indent\"><strong>References:<\/strong><\/p>\r\n\r\n<ol>\r\n \t<li><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\r\n \t<li><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t<li>T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\r\n<\/ol>\r\n&nbsp;","rendered":"<div>\n<p style=\"text-align: center\"><strong>Module 16<\/strong><\/p>\n<p style=\"text-align: center\"><strong>More Decrease and Conquer Algorithms<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This module 16 focuses on an important design paradigm called decrease and conquer by variable factor algorithms. The Learning objectives of this<\/p>\n<ul>\n<li>To explain Euclid Algorithm<\/li>\n<li>To explain Interpolation Search<\/li>\n<li>To explain Order statistics<\/li>\n<li>To explain Deterministic Selection<\/li>\n<\/ul>\n<p><strong>Decrease and Conquer Design paradigm:<\/strong><\/p>\n<p style=\"text-align: justify\">The decrease and conquer paradigm is based on problem reduction strategy. Problem reduction is a design strategy that aims to reduce a given problem to another problem with a reduced problem with smaller size. Then, attempts are made to solve the problem. Decrease and conquer is a design paradigm that uses the problem reduction strategy. It is also known as the incremental or inductive approach. As discussed earlier in the previous module, the steps of decrease and conquer is given as follows:<\/p>\n<ol>\n<li style=\"text-align: justify\">Reduce problem instance to same problem with smaller Instance<\/li>\n<li style=\"text-align: justify\">Solve problem of smaller instance<\/li>\n<li style=\"text-align: justify\">Extend solution of smaller instance to obtain solution to original problem with larger instance<\/li>\n<\/ol>\n<\/div>\n<div>\n<p style=\"text-align: justify\">Thus, it can be seen that the logic involves the following steps:<\/p>\n<ul>\n<li style=\"text-align: justify\">Establish the relationship between problem of the given instance and its reduced instance of the smaller problem<\/li>\n<li style=\"text-align: justify\">Exploit this relation top-down or Bottom-up<\/li>\n<\/ul>\n<p style=\"text-align: justify\">Design and conquer design paradigm can be implemented using both top-down or bottom-up approach. Also, this design paradigm is known as inductive or incremental approach.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Type of Decrease and Conquer Strategy<\/strong><\/p>\n<p style=\"text-align: justify\">Based on the decreasing factor, the decrease-and-conquer strategy can further be categorized into the following types:<\/p>\n<ol>\n<li>Decrease by a constant<\/li>\n<li>Decrease by a constant factor<\/li>\n<li>Decrease by a variable factor<\/li>\n<\/ol>\n<p><strong>Decrease by Variable Factor Method<\/strong><\/p>\n<p style=\"text-align: justify\">One more category of the decrease-and-conquer algorithm is decrease by a variable factor. It can be observed that as the name implies, the decreasing factor varies. Some examples of the algorithms that belong to this category are interpolation search, selection, and deterministic selection algorithms.<\/p>\n<p>&nbsp;<\/p>\n<p>Let us start the discussion on Euclid algorithm.<\/p>\n<\/div>\n<div>\n<p><strong>Euclid Algorithm<\/strong><\/p>\n<p style=\"text-align: justify\">Euclid algorithm is one of the oldest algorithms designed by Euclid about 300 B.C. Euclid algorithm is useful to find the largest integer that divides both a and b. For example, GCD of two integers 36 and 24 , GCD(36,24) can be obtained using factoring method. Let us try , one of the standard method of finding GCD using factoring method: Factor a and b into primes and then choose the common ones:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0\u00a0 24 = 2 x 2 x 2 x 3 and 36 = 2 x 2 x 3 x3<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Hence, GCD of 36 and 24 can be obtained as 2 x 2 x 3 = 12. Factoring method takes a lot of time. Therefore, a recursive method based on Euclid method can be done as follows: Euclid\u2019s algorithm is based on repeated application of equality<\/p>\n<p>&nbsp;<\/p>\n<p>GCD(<em>m, n<\/em>) = GCD(<em>n, m<\/em> mod <em>n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p>It can be done as follows:<\/p>\n<p>gcd(36, 24) = gcd(24, 36 mod 24)<\/p>\n<p>=\u00a0 gcd(24, 12)<\/p>\n<p>=\u00a0 gcd(12, 24 mod 12)<\/p>\n<p>=\u00a0 gcd(12,0)<\/p>\n<p>=\u00a0 12<\/p>\n<p>&nbsp;<\/p>\n<p>The Iterative algorithm for finding GCD is given as follows:<\/p>\n<\/div>\n<div>\n<p><strong>Iterative form:<\/strong><\/p>\n<ol>\n<li>Read two numbers x and y<\/li>\n<li>If y = 0, then return x as GCD<\/li>\n<li>Repeat While y is not zero, Divide x by y and set remainder to r<\/li>\n<\/ol>\n<p>Change value of x to y Change value of y by r<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The same algorithm can be done using recursive form as illustrated in the numerical example. The informal algorithm for finding GCD is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Recursive form:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Euclid (x,y)<\/p>\n<p>1. Input numbers x and y\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2. if y == 0 return x<\/p>\n<p>else<\/p>\n<p>return Euclid(y, x mod y)<\/p>\n<p>The formal algorithm for Euclid algorithm is as follows:<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Algorithm Euclid(x,y)<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">%%\u00a0 Input: x and y Begin<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">If (y == 0) return x<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Else return Euclid(y, x mod y) End if<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">End.<\/span><\/p>\n<\/div>\n<div>\n<p><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">What is the complexity analysis of Euclid algorithm? One can prove that the size, measured by the second number, decreases at least by half after two consecutive iterations. This, the complexity analysis of Euclid algorithm is T(<em>n<\/em>) \u00ce O(log <em>n<\/em>) .<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Interpolation Search<\/strong><\/p>\n<p style=\"text-align: justify\">Interpolation search is another example of decrease and conquer by a variable factor. Interpolation search is faster than binary search. To illustrate this, let us consider the following scenario: Searching for the element 18 in an array, A = 12 13 14 16 18. The binary search for item 18 starts by finding the middle element 14. Then it proceeds. It can be observed that the idea of even split as in the case of binary search is not of much use here. On the contrary, if one searches from right to left, one can find easily the element 18.\u00a0\u00a0<span style=\"text-align: initial;font-size: 1em\">The idea of interpolation search is to adopt a modified middle element finding. In the case of interpolation that is closer to the element to be searched. Therefore, interpolation search uses the approximate \u2018middle point\u2019, say C, which is a constant, for finding the target item.<\/span><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-225\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1.png\" alt=\"\" width=\"101\" height=\"47\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1.png 101w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-65x30.png 65w\" sizes=\"auto, (max-width: 101px) 100vw, 101px\" \/>This approximate middle element or constant <em>C<\/em> replaces the \u2018exact mid\u2019 of the binary search algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p>The informal Interpolation search is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>1.\u00a0 Read array A and target key k<\/p>\n<p>2.\u00a0 Computer approximate middle<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-226\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-1.png\" alt=\"\" width=\"101\" height=\"47\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-1.png 101w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-1-65x30.png 65w\" sizes=\"auto, (max-width: 101px) 100vw, 101px\" \/><\/p>\n<p>Here, k = key, low = first and high = last element<\/p>\n<p>&nbsp;<\/p>\n<p>3.\u00a0 Compare k with A[C] if equal return C else recurse . The formal algorithm is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><em>Algorithm IS(A[0..n-1], k )<\/em><\/p>\n<p>&nbsp;<\/p>\n<p>%% <em>Input: Array A and key k<\/em><\/p>\n<p><em>\u00a0<\/em><\/p>\n<p>%% <em>Output: k if present, -1 if not present Begin<\/em><\/p>\n<p><em>\u00a0<\/em><\/p>\n<p><em>low <\/em>\u00ac 0;\u00a0 high \u00ac<em> n<\/em>-1<\/p>\n<\/div>\n<div>\n<p>while <em>low<\/em> \u00a3 high do<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-227\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-2.png\" alt=\"\" width=\"101\" height=\"47\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-2.png 101w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic1-2-65x30.png 65w\" sizes=\"auto, (max-width: 101px) 100vw, 101px\" \/><\/p>\n<p>if k <em>=<\/em> A[C] return C else if k <em>&lt;<\/em> A[C]<\/p>\n<p>&nbsp;<\/p>\n<p>call IS(A,l,C-1) else<\/p>\n<p>&nbsp;<\/p>\n<p>call IS(A,C+1,r) End if<\/p>\n<p>&nbsp;<\/p>\n<p>End While return -1 End<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that the interpolation search is similar to binary search except in finding the middle element.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p style=\"text-align: justify\">Interpolation search depends on the distribution of elements of an array. If the elements are distributed uniformly, then the complexity of the algorithm would be <em>O<\/em>(log(log <em>n<\/em>)) . On the other\u00a0 hand, if the distribution is not uniform, the complexity of the algorithm is <em>O<\/em>(<em>n<\/em>). One can observe that for binary search, the complexity of the algorithm is <em>O<\/em>(log <em>n<\/em>) for all cases.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Order Statistics:<\/strong><\/p>\n<p style=\"text-align: justify\">The problem of finding the <em>k<\/em>th smallest element in an unordered array is called selection or order statistics. Finding the smallest element in an ordered array is easy, as the first element of an array sorted in an increasing order is the minimum element and the last element is the maximum element. The brute force algorithm is given as follows:<\/p>\n<\/div>\n<ul>\n<li>Input: A set S of n elements and k<\/li>\n<li>Output: The kth smallest element of S<\/li>\n<\/ul>\n<p>step 1: Sort the n elements<\/p>\n<p class=\"hanging-indent\">step 2: Locate the kth element in the sorted list.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p>The time complexity is O(nlogn)<\/p>\n<p style=\"text-align: justify\">On the other hand, finding these in unordered array is difficult. So, these elements should be sorted first before finding minimum, maximum and median. Deterministic selection is linear finding of these statistics. Let us discuss the statistical terms now:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Minimum and maximum<\/strong><\/p>\n<p style=\"text-align: justify\">In general, ith order statistic: ith smallest element of a set of n elements. The first order statistic is minimum and nth order statistic is maximum.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Median<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Median is the \u201chalf-way point\u201d of the set. When \u2018n\u2019 is odd, the median location can be obtained as follows: median = (<em>n+<\/em>1)\/2. In n is even, then lower median, at = <em>n<\/em>\/2 and upper median, at <em>i =<\/em> <em>n<\/em>\/2+1. But lower medi an is always chosen for consistency. This is given as below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-228\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2.png\" alt=\"\" width=\"516\" height=\"160\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2.png 516w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2-300x93.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2-65x20.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2-225x70.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic2-350x109.png 350w\" sizes=\"auto, (max-width: 516px) 100vw, 516px\" \/><\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">Blum, Floyd, Pratt, Rivest, and Tarjan proposed a linear-order algorithm for finding the <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th smallest element in a linear order without using the sorting procedure. This algorithm follows the decrease-and-conquer approach, as the strategy is to split the problem into subproblems and then select the appropriate subproblem for finding solutions. The procedure for selecting the <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th smallest element in an unsorted array is given informally as follows:<\/span><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-229\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3.png\" alt=\"\" width=\"266\" height=\"424\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3.png 266w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3-188x300.png 188w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3-65x104.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic3-225x359.png 225w\" sizes=\"auto, (max-width: 266px) 100vw, 266px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">It can be observed that the algorithm partitions the given array using a partitioning element. Then it finds the rank. The algorithm compares the expected <\/span><em style=\"text-align: justify;font-size: 1em\">k<\/em><span style=\"text-align: justify;font-size: 1em\">th element with the rank to get the appropriate subarray. Then the algorithm is used recursively till the target key is obtained. This concept is illustrated in the following Example 1.<\/span><\/p>\n<\/div>\n<p><strong>Example 1: Find the element k = 3 and k = 7 using the above procedure.<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-230\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4.png\" alt=\"\" width=\"646\" height=\"81\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4.png 646w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4-300x38.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4-65x8.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4-225x28.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic4-350x44.png 350w\" sizes=\"auto, (max-width: 646px) 100vw, 646px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Solution<\/strong><\/p>\n<p style=\"text-align: justify\">As discussed earlier, the pivot element can be obtained using a partitioning procedure.\u00a0 \u00a0After partitioning, the pivot element is given as below:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-231\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5.png\" alt=\"\" width=\"615\" height=\"69\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5.png 615w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5-300x34.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5-65x7.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5-225x25.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic5-350x39.png 350w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here, the number of elements less that pivotal element is <em>A<\/em><em>count<\/em> =3. As, <em>A<\/em><em>count<\/em> = k-1, return the pivot element 4 as the answer for k = 4.<\/p>\n<p>&nbsp;<\/p>\n<p>For k = 7, count is greater than k \u2013 count -1, 7 \u2013 3 -1 = 3rd element right subarray.<\/p>\n<p>&nbsp;<\/p>\n<p>The process can be repeated on the right subarray. It can be found that the k = 7, is 7.<\/p>\n<p>&nbsp;<\/p>\n<p>The formal algorithm is given as follows:<\/p>\n<p>Algorithm Selection(A,k)<\/p>\n<p>%% Input: k is the smallest item<br \/>\nBegin<br \/>\nFind pivot q<br \/>\nAless = {All elements less than q}<br \/>\nAequal = {q}<br \/>\nAgreater = { Elements greater than q}<br \/>\nCount = number of elements of Aless<br \/>\nIf count = k-1, then return q<br \/>\nelse If count &gt; k-1, then<br \/>\nSelection(Aless,k) else<br \/>\nSelection(Agreater,k-count-1)<br \/>\nEnd if<br \/>\nEnd if<br \/>\nEnd<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">Each time when the pivot element partition the array exactly into two halves, the recurrence equation is\u00a0 T(n)=T(n\/2)+n, where n is required for separating the n elements into two sets. This T(n) =O(n), which is\u00a0 \u00a0the best case. However, in the worst case, the pivot element will be either the largest or the smallest element in the set. Thus, the array is partitioned into only one set of size n-1. Hence the recurrence\u00a0 equation is, T(n)=T(n-1)+n, which is O(n^2)<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Deterministic Selection<\/strong><\/p>\n<p style=\"text-align: justify\">The informal algorithm for finding median using deterministic selection is given as follows:\u00a0 Find Median problem \u2013 Deterministic Algorithm<br \/>\nInput: A set A of n distinct numbers and a number i, with 1\uf0a3 i \uf0a3 n.<\/p>\n<p>Find median of medians:<\/p>\n<p style=\"text-align: justify\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-232 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6.png\" alt=\"\" width=\"524\" height=\"289\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6.png 524w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6-300x165.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6-65x36.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6-225x124.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic6-350x193.png 350w\" sizes=\"auto, (max-width: 524px) 100vw, 524px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">The formal segment of deterministic selection is given as follows<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-233 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7.png\" alt=\"\" width=\"432\" height=\"518\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7.png 432w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7-250x300.png 250w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7-65x78.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7-225x270.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic7-350x420.png 350w\" sizes=\"auto, (max-width: 432px) 100vw, 432px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-234 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8.png\" alt=\"\" width=\"514\" height=\"524\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8.png 514w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8-294x300.png 294w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8-65x66.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8-225x229.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M16Pic8-350x357.png 350w\" sizes=\"auto, (max-width: 514px) 100vw, 514px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<div>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>In short, one can conclude as part of this module 16 that<\/li>\n<li>Euclid algorithm uses decrease and conquer approach.<\/li>\n<li>Interpolation search is effective than even binary search.<\/li>\n<li>Selection algorithms finds smallest k in linear time.<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">Deterministic median algorithm finds median in linear time.<\/span><\/li>\n<\/ul>\n<\/div>\n<p class=\"hanging-indent\"><strong>References:<\/strong><\/p>\n<ol>\n<li><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\n<li><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n<li>T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n","protected":false},"author":4,"menu_order":5,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-62","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/62","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":7,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/62\/revisions"}],"predecessor-version":[{"id":236,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/62\/revisions\/236"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/62\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=62"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=62"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=62"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=62"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}