{"id":88,"date":"2018-07-19T05:28:54","date_gmt":"2018-07-19T05:28:54","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=88"},"modified":"2018-07-25T11:57:05","modified_gmt":"2018-07-25T11:57:05","slug":"transform-and-conquer-design-paradigm","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/transform-and-conquer-design-paradigm\/","title":{"rendered":"Transform and Conquer Design paradigm"},"content":{"raw":"<div>\r\n<div>\r\n<p style=\"text-align: center\"><strong>Module 17<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>Transform and Conquer Design paradigm<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">This module 17 focuses on an important design paradigm called Transform and Conquer design paradigm. The learning objectives of this module are<\/p>\r\n\r\n<ul>\r\n \t<li>To explain basics of Transform and Conquer<\/li>\r\n \t<li>To illustrate simple examples like presorting and unique elements<\/li>\r\n \t<li>To understand matrix operations<\/li>\r\n \t<li>To explain Gaussian Elimination<\/li>\r\n<\/ul>\r\n<h3>Transform and Conquer Design paradigm<\/h3>\r\n<p style=\"text-align: justify\">Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity. The problem is solved in the new domain. Then, the solutions are converted back to the original domain. In short, transform and conquer proposes two stage solution<\/p>\r\n\r\n<ol>\r\n \t<li>First stage involves the transformation to another problem that is more amenable for solution<\/li>\r\n \t<li>Second stage involves solving the new problem where the transformed new problem is solved.<\/li>\r\n<\/ol>\r\nThen the solutions are converted back to the original problem. This is illustrated through the following simple examples.\r\n\r\nConsider the problem of multiplying two simple numbers XII and IV. These numbers are in Roman number system. As many are not comfortable with Roman number system, this gets transformed to another problem where Arabic numerals are used instead of Roman system.\r\n<ol>\r\n \t<li style=\"text-align: justify\">In the first stage, the numbers XII and IV is transformed to another problem of 12 X 4.<\/li>\r\n \t<li style=\"text-align: justify\">In the second stage, the actual multiplication is done as 48, then the result is converted to Roman number as XLVIII.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<p style=\"text-align: justify\">Another good example of transform and conquer technique is finding LCM using GCD. For example, if GCD of two numbers is available, then LCM can be obtained as follows:<\/p>\r\n<em>lcm <\/em>(<em>m<\/em>,<em> n<\/em>) =\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>m <\/em>\u00b4(<em>n<\/em><em>\u00a0\u00a0 <\/em>)\r\n\r\n<em>GCD\u00a0 m<\/em>,<em> n<\/em>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Variations of Transform and Conquer<\/strong><\/p>\r\n&nbsp;\r\n\r\nThree variants of transform and conquer are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2013\u00a0 Instance Simplification\r\n\r\n\u2013\u00a0 Representation Change\r\n\r\n\u2013\u00a0 Problem Reduction\r\n<ul>\r\n \t<li class=\"hanging-indent\" style=\"text-align: justify\"><strong>Instance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance. The illustrated example of roman number to Arabic number system is an example of instance simplification.<\/li>\r\n \t<li class=\"hanging-indent\" style=\"text-align: justify\"><strong>Representation Change <\/strong>is another variety where the strategy involves the transformation of an instance to a different representation. But this is done without affecting the instance. The illustrated example of roman number to Arabic number system is an example of instance simplification.<\/li>\r\n \t<li class=\"hanging-indent\" style=\"text-align: justify\"><span style=\"font-size: 1em\">P<\/span><strong style=\"font-size: 1em\">roblem reduction<\/strong><span style=\"font-size: 1em\"> is a strategy that involves a transformation of a problem A to another type of problem B. It is assumed that the solution of problem B already exists. The illustrated example of reduction of computing LCM (Last Common Multiple) in terms of GCD is an example of problem reduction. s GCD. Hypothetically, let us assume that an algorithm exists only for GCD.<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n<p class=\"hanging-indent\"><strong>Presorting<\/strong><\/p>\r\n<p style=\"text-align: justify\">Sorting an array before processing is called presorting. Presorting is helpful in various applications such as search and in finding element uniqueness.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Finding unique elements in an array<\/strong><\/p>\r\n<p style=\"text-align: justify\">Consider a problem of finding element uniqueness in an array. The problem can be defined as follows: Example: <em>Given a random list of numbers, determine if there are any duplicates.<\/em><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Brute force Algorithm<\/strong><\/p>\r\n<p style=\"text-align: justify\">A brute force algorithm involves checking ever pair of elements for duplicated. This means comparing an element with all other elements of an array. The informal brute force algorithm for element uniqueness is given as follows:<\/p>\r\n&nbsp;\r\n\r\n<strong>Algorithm Uniqueness<\/strong>\r\n\r\n&nbsp;\r\n\r\n<em>for each x <\/em><em>\u00ce<\/em><em> A<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>for each y <\/em><em>\u00ce<\/em><em> {A-x}<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>if x=y then<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>return not unique<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>endif<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>return unique<\/em>\r\n\r\n&nbsp;\r\n\r\nThe complexity of this approach is <em>q<\/em><em>(n<\/em><em>2<\/em><em>)<\/em>.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Transform and Conquer approach<\/strong><\/p>\r\n<p style=\"text-align: justify\">One can apply the principle of instance simplification here. One can sort the array instead. The advantage of sorting here is that only the adjacent elements to be checked. So the algorithm can be stated informally as follows:<\/p>\r\n\r\n<ol>\r\n \t<li>Sort the numbers.<\/li>\r\n \t<li>Check the adjacent numbers. If the numbers are same then return uniqueness as false.<\/li>\r\n \t<li>End.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<div>\r\n\r\nThe formal algorithm is given as follows:\r\n\r\n&nbsp;\r\n\r\nAlgorithm Elementuniqueness-Presorting(A[1..n])\r\n\r\n&nbsp;\r\n\r\n%%\u00a0\u00a0 Input: Array A\r\n\r\n&nbsp;\r\n\r\n%%\u00a0\u00a0 Output: Unique or not Begin\r\n\r\n&nbsp;\r\n\r\nSort A\r\n\r\n&nbsp;\r\n\r\nfor i = 1 to n-1\r\n\r\n&nbsp;\r\n\r\nif A[i] = A[i+1] return not unique End for\r\n\r\n&nbsp;\r\n\r\nreturn unique End\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n&nbsp;\r\n\r\nSorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The second step requires at most <em>n-1<\/em> comparisons. Therefore,\r\n\r\n&nbsp;\r\n\r\nthe total complexity is <em>q<\/em> ( <em>n<\/em> )+<em>q<\/em> (<em>n<\/em> log <em>n<\/em>)\r\n\r\n&nbsp;\r\n\r\n= <em>q<\/em> (<em>n <\/em>log<em> n<\/em>)\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Search using Presorting<\/strong><\/p>\r\n&nbsp;\r\n\r\nPresorting can be done for search also. The order in the array allows the usage of binary search.\r\n\r\n&nbsp;\r\n\r\nThe informal algorithm for binary search is given as follows:\r\n\r\n&nbsp;\r\n\r\n<strong>Stage 1 <\/strong>Sort the array by Merge sort\r\n\r\n&nbsp;\r\n\r\n<strong>Stage 2 <\/strong>Apply binary search\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\nSorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The second step requires at most log(n) time. Therefore the\r\n\r\n&nbsp;\r\n\r\ntotal complexity is <em>q<\/em> ( <em>n<\/em> )+<em>q<\/em> (<em>n<\/em> log <em>n<\/em>).\r\n\r\n&nbsp;\r\n\r\nTherefore, the efficiency of the procedure is \u0398(<em>n<\/em>log <em>n<\/em>) + O(log <em>n<\/em>) = \u0398(<em>n<\/em>log <em>n<\/em>) <strong>Mode<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Mode is defined as the element that occurs most often in a given array. For example, consider the following array of elements, A = [5, 1, 5, 5,5,7, 6, 5, 7,5] . The mode of array A is 5 as 5 is the most common element that appear most. If several and different values occur most often any of them can be considered the mode.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Brute force Algorithm<\/strong><\/p>\r\n&nbsp;\r\n\r\nThe brute force algorithm is to scan the array repeatedly to find the frequencies of all elements.\r\n\r\n&nbsp;\r\n\r\nInformally, the frequency based approach is given below:\r\n\r\n&nbsp;\r\n\r\nStep 1:\u00a0 Find length of List A\r\n\r\n&nbsp;\r\n\r\nmax \u00ac max(A)\r\n\r\n&nbsp;\r\n\r\nStep 2:\u00a0 Set freq[1..max] \u00ac 0\r\n\r\n&nbsp;\r\n\r\nStep3:\u00a0\u00a0\u00a0 for each x \u00ce A\r\n\r\n&nbsp;\r\n\r\nfreq[x] = freq[x] + 1\r\n\r\n&nbsp;\r\n\r\nStep4:\u00a0\u00a0\u00a0 mode \u00ac freq[1]\r\n\r\n&nbsp;\r\n\r\nStep 5:\u00a0 for i \u00ac 2 to max\r\n\r\n&nbsp;\r\n\r\nif freq[i] &gt; freq[mode]\u00a0 mode \u00ac i\r\n\r\n&nbsp;\r\n\r\nStep6:\u00a0\u00a0\u00a0 return mode\r\n\r\n&nbsp;\r\n\r\nComplexity Analysis:\r\n\r\n&nbsp;\r\n\r\nThe complexity analysis of frequency based mode finding algorithm is <em>q<\/em><em>(n<\/em><em>2<\/em><em>)<\/em>.\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Transform and conquer approach<\/strong><\/p>\r\n<p style=\"text-align: justify\">Instead, the array can be sorted and run length of an element can be calculated on the sorted array. Informally, mode finding using presorting is given as follows:<\/p>\r\n\r\n<ol>\r\n \t<li>Sort the element of an array.<\/li>\r\n \t<li>Calculate the run length of an element<\/li>\r\n \t<li>Print the element having longest length<\/li>\r\n \t<li>Exit.<\/li>\r\n<\/ol>\r\nFormal algorithm based on [2] is given as follows:\r\n\r\nSort A\r\n\r\ni \u00ac 0\r\n\r\n&nbsp;\r\n\r\nfrequency \u00ac 0\r\n\r\nwhile i \u2264 n-1\r\n\r\nrunlength \u00ac 1;\u00a0\u00a0 runvalue \u00ac A[i]\r\n\r\n&nbsp;\r\n\r\nwhile i+runlength \u2264 n-1 and A[i+runlength] = runvalue runlength = runlength + 1\r\n\r\n&nbsp;\r\n\r\nif runlength &gt; frequency\r\n\r\nfrequency \u00ac runlength\r\n\r\nmodevalue \u00ac runvalue\r\n\r\n&nbsp;\r\n\r\ni = i + runlength\r\n\r\nreturn modevalue\r\n\r\n&nbsp;\r\n<p class=\"indent hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">Sorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The finding of a run length requires only linear time as the array is already sorted. Therefore the worst case performance of the algorithm would be less than the brute-force method.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>Matrix Operations<\/strong>\r\n<p style=\"text-align: justify\">A matrix is a rectangular table of numbers. In scientific domain, matrices have many uses. Matrix addition and subtractions are relatively easy.<\/p>\r\n<p style=\"text-align: justify\">Most of the scientific applications use matrix operations like matrix inverse and matrix determinant. So there is a need to solve these problems. As the computational complexity of these algorithms are high, transform and conquer approach can be used. Gaussian elimination uses transform and conquer approach to solve set of equations. Additionally, it can be used to decompose matrices also. Matrix decomposition is useful for find inverse of a matrix and matrix determinant.<\/p>\r\nFirst let us discuss the method of Gaussian elimination in the subsequent section.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Gaussian elimination method<\/strong><\/p>\r\nSolving an equation means finding the values of the unknown. A simplest equation is of the form:\r\n\r\n&nbsp;\r\n\r\nAx = y\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A solution of this equation is x = y\/A. but this is true only when (y \u00b9 0 and A is not zero). All values of x satisfies the equation when y=0. This logic can be extended for two unknowns. Let us consider the following set of equations:<\/p>\r\n&nbsp;\r\n\r\nA11x + A12y = B1\r\n\r\n&nbsp;\r\n\r\nA21x + A22y = B2\r\n\r\n&nbsp;\r\n\r\nThe equations can be solved first by finding x as\r\n\r\n&nbsp;\r\n\r\nx = (B1 \u2013 A12y) \/ A11\r\n\r\n&nbsp;\r\n\r\nSubstituting this in the second equation gives y.\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In general, if one plots these two equations as lines, then the intersection of two lines in a single point, then the system of linear equations has a unique solution. If the lines are parallel, then there is no solution. If the lines coincide, then there would be infinite number of solutions.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In many applications, one may have to solve \u2018n\u2019 equations with \u2018n\u2019 unknowns. The set of linear equations are as below:<\/p>\r\n&nbsp;\r\n\r\nA11x1 + A12x2 + \u2026 + A1nxn = B1\r\n\r\n&nbsp;\r\n\r\nA21x1 + A22x2 + \u2026 + A2nxn = B2\r\n\r\n<\/div>\r\n\u2026\r\n\r\n&nbsp;\r\n\r\nAn1x1 + An2x2 + \u2026 + Annxn = Bn\r\n\r\n&nbsp;\r\n\r\nIn matrix form, the above can be represented as\r\n\r\n&nbsp;\r\n\r\nAx = B\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Gaussian elimination, names after Gauss, uses transform and conquer approach to transform this set of equations with \u2018n\u2019 unknowns<\/p>\r\n<img class=\"aligncenter wp-image-249 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-300x114.png\" alt=\"\" width=\"300\" height=\"114\" \/>\r\n\r\nThe transformation can be represented as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-250\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2.png\" alt=\"\" width=\"470\" height=\"144\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Gaussian elimination aims to create a matrix with zeros in the lower triangle. This is called upper triangular matrix. This is done by elimination a variable at every stage in all equations. The advantage is that One can solve the last equation first, substitute into the second to last, and can proceed to solve the first one.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">To do the manipulations, Gaussian elimination uses some elementary steps. The following elementary steps are used by Gaussian elimination.<\/p>\r\n\r\n<ol>\r\n \t<li>Exchanging two equations of the system<\/li>\r\n<\/ol>\r\nIn this, two equations are exchanged. For example, consider the following equations.\r\n\r\n&nbsp;\r\n\r\nx + y = 3\r\n\r\n2x + y = 4\r\n\r\n&nbsp;\r\n\r\nThese equations can be exchanged as\r\n\r\n&nbsp;\r\n\r\n2x + y = 4\r\n\r\nX + y = 3\r\n\r\n&nbsp;\r\n<ol start=\"2\">\r\n \t<li>Exchanging an equation with non-zero multiples<\/li>\r\n<\/ol>\r\nSay,\r\n\r\n&nbsp;\r\n\r\nx + y = 2 can be replaced as\r\n\r\n2x + 2y = 4.\r\n\r\n&nbsp;\r\n<ol start=\"3\">\r\n \t<li>Replacing the multiple of one equation to another equation. For example, row 2, R2, can be expressed as a multiple of row 1, R1, and row 3, R3<\/li>\r\n<\/ol>\r\n&nbsp;\r\n\r\nThe informal algorithm for Gaussian elimination is given as follows:\r\n\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-251\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3.png\" alt=\"\" width=\"979\" height=\"354\" \/>\r\n\r\n&nbsp;\r\n\r\nThis illustrated in Example 1 [1].\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">Example 1<\/p>\r\n<p class=\"hanging-indent\"><strong>Solve the set of equations using Gaussian Elimination method<\/strong><\/p>\r\n<em>3x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3\u00a0\u00a0 \u00a0= 11<\/em>\r\n\r\n<em>6x<\/em><em>1 + 4x<\/em><em>2 + x<\/em><em>3\u00a0 = 29 <\/em>\r\n\r\n<em>x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3\u00a0 \u00a0 \u00a0 =\u00a0 7<\/em>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In matrix notation, this can be written it as <em>Ax = b. Augment the equation as below and apply the elementary operations as shown below:<\/em><\/p>\r\n<img class=\"aligncenter size-full wp-image-252\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4.png\" alt=\"\" width=\"639\" height=\"418\" \/>\r\n<p style=\"text-align: center\"><em>2x<\/em><em>2 \u2013 x<\/em><em>3\u00a0 = 7<\/em><\/p>\r\n<p style=\"text-align: center\"><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a02x<\/em><em>2\u00a0 = 8<\/em><\/p>\r\n<p style=\"text-align: center\"><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 x2 = 4<\/em><\/p>\r\nUsing these two variables, the remaining variable can be obtained as follows:\r\n\r\n&nbsp;\r\n\r\n<em>3x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3 = 11<\/em>\r\n\r\n<em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a03x<\/em><em>2 + 5 = 11<\/em>\r\n\r\n<em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0x2 = 11-5\/3 = 6\/3 = 2<\/em>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Apply the elementary operation to reduce the augmented matrix to a triangular form called echelon matrix. So the idea is to keep a11 as pivot and eliminate all a11 in other equations. For example, in the second equation, a11 can be eliminated by the factor R2-(a21\/a11). This operation is applied throughout the equation. Using the same logic, a11 is eliminated in all other equations. Similarly, using the multiple of (a31\/a11), (a41\/a11), \u2026, (an1\/a11), the matrix A can be reduced to a upper triangular matrix A\u2019. Then, the solution can be obtained by back substitution. The algorithm for forward elimination is given as follows:<\/p>\r\n<img class=\"aligncenter wp-image-253 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-300x113.png\" alt=\"\" width=\"300\" height=\"113\" \/>\r\n\r\n&nbsp;\r\n\r\nThe backward substitution is given as follows:\r\n\r\n&nbsp;\r\n\r\n<img class=\"aligncenter wp-image-254 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-300x142.png\" alt=\"\" width=\"300\" height=\"142\" \/>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n<p style=\"text-align: justify\">How many operations are required for Gaussian elimination? One division and n multiplication\/division\u00a0 \u00a0is\u00a0 \u00a0required.\u00a0\u00a0 \u00a0So\u00a0\u00a0 \u00a0(n+1)\u00a0\u00a0 \u00a0operations\u00a0\u00a0 \u00a0for\u00a0\u00a0 \u00a0(n-1)\u00a0\u00a0 \u00a0rows,\u00a0\u00a0 \u00a0requires (<em>n <\/em>-1)(<em>n <\/em>+1) = <em>n<\/em>2 -1 operations to eliminate the first column of matrix A. Similarly the second row involves (<em>n <\/em>-1)2 -1 operations. So all n rows, the numbers of operations are<\/p>\r\n<img class=\"aligncenter size-full wp-image-255\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic7.png\" alt=\"\" width=\"200\" height=\"122\" \/>\r\n\r\nSo Gaussian elimination method time complexity is O(n3 ) .\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\r\nIn short, one can conclude as part of this module 17 that\r\n<ul>\r\n \t<li>Transform and Conquer is an effective design paradigm<\/li>\r\n \t<li>Matrix operations are computationally very intensive<\/li>\r\n \t<li>Gaussian elimination is an effective technique that uses transform and conquer method<\/li>\r\n<\/ul>\r\n&nbsp;\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 \u00a0the 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;\r\n\r\n&nbsp;\r\n\r\n&nbsp;","rendered":"<div>\n<div>\n<p style=\"text-align: center\"><strong>Module 17<\/strong><\/p>\n<p style=\"text-align: center\"><strong>Transform and Conquer Design paradigm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This module 17 focuses on an important design paradigm called Transform and Conquer design paradigm. The learning objectives of this module are<\/p>\n<ul>\n<li>To explain basics of Transform and Conquer<\/li>\n<li>To illustrate simple examples like presorting and unique elements<\/li>\n<li>To understand matrix operations<\/li>\n<li>To explain Gaussian Elimination<\/li>\n<\/ul>\n<h3>Transform and Conquer Design paradigm<\/h3>\n<p style=\"text-align: justify\">Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity. The problem is solved in the new domain. Then, the solutions are converted back to the original domain. In short, transform and conquer proposes two stage solution<\/p>\n<ol>\n<li>First stage involves the transformation to another problem that is more amenable for solution<\/li>\n<li>Second stage involves solving the new problem where the transformed new problem is solved.<\/li>\n<\/ol>\n<p>Then the solutions are converted back to the original problem. This is illustrated through the following simple examples.<\/p>\n<p>Consider the problem of multiplying two simple numbers XII and IV. These numbers are in Roman number system. As many are not comfortable with Roman number system, this gets transformed to another problem where Arabic numerals are used instead of Roman system.<\/p>\n<ol>\n<li style=\"text-align: justify\">In the first stage, the numbers XII and IV is transformed to another problem of 12 X 4.<\/li>\n<li style=\"text-align: justify\">In the second stage, the actual multiplication is done as 48, then the result is converted to Roman number as XLVIII.<\/li>\n<\/ol>\n<\/div>\n<p style=\"text-align: justify\">Another good example of transform and conquer technique is finding LCM using GCD. For example, if GCD of two numbers is available, then LCM can be obtained as follows:<\/p>\n<p><em>lcm <\/em>(<em>m<\/em>,<em> n<\/em>) =\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>m <\/em>\u00b4(<em>n<\/em><em>\u00a0\u00a0 <\/em>)<\/p>\n<p><em>GCD\u00a0 m<\/em>,<em> n<\/em><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Variations of Transform and Conquer<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Three variants of transform and conquer are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0 Instance Simplification<\/p>\n<p>\u2013\u00a0 Representation Change<\/p>\n<p>\u2013\u00a0 Problem Reduction<\/p>\n<ul>\n<li class=\"hanging-indent\" style=\"text-align: justify\"><strong>Instance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance. The illustrated example of roman number to Arabic number system is an example of instance simplification.<\/li>\n<li class=\"hanging-indent\" style=\"text-align: justify\"><strong>Representation Change <\/strong>is another variety where the strategy involves the transformation of an instance to a different representation. But this is done without affecting the instance. The illustrated example of roman number to Arabic number system is an example of instance simplification.<\/li>\n<li class=\"hanging-indent\" style=\"text-align: justify\"><span style=\"font-size: 1em\">P<\/span><strong style=\"font-size: 1em\">roblem reduction<\/strong><span style=\"font-size: 1em\"> is a strategy that involves a transformation of a problem A to another type of problem B. It is assumed that the solution of problem B already exists. The illustrated example of reduction of computing LCM (Last Common Multiple) in terms of GCD is an example of problem reduction. s GCD. Hypothetically, let us assume that an algorithm exists only for GCD.<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p class=\"hanging-indent\"><strong>Presorting<\/strong><\/p>\n<p style=\"text-align: justify\">Sorting an array before processing is called presorting. Presorting is helpful in various applications such as search and in finding element uniqueness.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Finding unique elements in an array<\/strong><\/p>\n<p style=\"text-align: justify\">Consider a problem of finding element uniqueness in an array. The problem can be defined as follows: Example: <em>Given a random list of numbers, determine if there are any duplicates.<\/em><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Brute force Algorithm<\/strong><\/p>\n<p style=\"text-align: justify\">A brute force algorithm involves checking ever pair of elements for duplicated. This means comparing an element with all other elements of an array. The informal brute force algorithm for element uniqueness is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Algorithm Uniqueness<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><em>for each x <\/em><em>\u00ce<\/em><em> A<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>for each y <\/em><em>\u00ce<\/em><em> {A-x}<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>if x=y then<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>return not unique<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>endif<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>return unique<\/em><\/p>\n<p>&nbsp;<\/p>\n<p>The complexity of this approach is <em>q<\/em><em>(n<\/em><em>2<\/em><em>)<\/em>.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Transform and Conquer approach<\/strong><\/p>\n<p style=\"text-align: justify\">One can apply the principle of instance simplification here. One can sort the array instead. The advantage of sorting here is that only the adjacent elements to be checked. So the algorithm can be stated informally as follows:<\/p>\n<ol>\n<li>Sort the numbers.<\/li>\n<li>Check the adjacent numbers. If the numbers are same then return uniqueness as false.<\/li>\n<li>End.<\/li>\n<\/ol>\n<\/div>\n<div>\n<p>The formal algorithm is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>Algorithm Elementuniqueness-Presorting(A[1..n])<\/p>\n<p>&nbsp;<\/p>\n<p>%%\u00a0\u00a0 Input: Array A<\/p>\n<p>&nbsp;<\/p>\n<p>%%\u00a0\u00a0 Output: Unique or not Begin<\/p>\n<p>&nbsp;<\/p>\n<p>Sort A<\/p>\n<p>&nbsp;<\/p>\n<p>for i = 1 to n-1<\/p>\n<p>&nbsp;<\/p>\n<p>if A[i] = A[i+1] return not unique End for<\/p>\n<p>&nbsp;<\/p>\n<p>return unique End<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Sorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The second step requires at most <em>n-1<\/em> comparisons. Therefore,<\/p>\n<p>&nbsp;<\/p>\n<p>the total complexity is <em>q<\/em> ( <em>n<\/em> )+<em>q<\/em> (<em>n<\/em> log <em>n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p>= <em>q<\/em> (<em>n <\/em>log<em> n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Search using Presorting<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Presorting can be done for search also. The order in the array allows the usage of binary search.<\/p>\n<p>&nbsp;<\/p>\n<p>The informal algorithm for binary search is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Stage 1 <\/strong>Sort the array by Merge sort<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Stage 2 <\/strong>Apply binary search<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<\/div>\n<div>\n<p>Sorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The second step requires at most log(n) time. Therefore the<\/p>\n<p>&nbsp;<\/p>\n<p>total complexity is <em>q<\/em> ( <em>n<\/em> )+<em>q<\/em> (<em>n<\/em> log <em>n<\/em>).<\/p>\n<p>&nbsp;<\/p>\n<p>Therefore, the efficiency of the procedure is \u0398(<em>n<\/em>log <em>n<\/em>) + O(log <em>n<\/em>) = \u0398(<em>n<\/em>log <em>n<\/em>) <strong>Mode<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Mode is defined as the element that occurs most often in a given array. For example, consider the following array of elements, A = [5, 1, 5, 5,5,7, 6, 5, 7,5] . The mode of array A is 5 as 5 is the most common element that appear most. If several and different values occur most often any of them can be considered the mode.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Brute force Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The brute force algorithm is to scan the array repeatedly to find the frequencies of all elements.<\/p>\n<p>&nbsp;<\/p>\n<p>Informally, the frequency based approach is given below:<\/p>\n<p>&nbsp;<\/p>\n<p>Step 1:\u00a0 Find length of List A<\/p>\n<p>&nbsp;<\/p>\n<p>max \u00ac max(A)<\/p>\n<p>&nbsp;<\/p>\n<p>Step 2:\u00a0 Set freq[1..max] \u00ac 0<\/p>\n<p>&nbsp;<\/p>\n<p>Step3:\u00a0\u00a0\u00a0 for each x \u00ce A<\/p>\n<p>&nbsp;<\/p>\n<p>freq[x] = freq[x] + 1<\/p>\n<p>&nbsp;<\/p>\n<p>Step4:\u00a0\u00a0\u00a0 mode \u00ac freq[1]<\/p>\n<p>&nbsp;<\/p>\n<p>Step 5:\u00a0 for i \u00ac 2 to max<\/p>\n<p>&nbsp;<\/p>\n<p>if freq[i] &gt; freq[mode]\u00a0 mode \u00ac i<\/p>\n<p>&nbsp;<\/p>\n<p>Step6:\u00a0\u00a0\u00a0 return mode<\/p>\n<p>&nbsp;<\/p>\n<p>Complexity Analysis:<\/p>\n<p>&nbsp;<\/p>\n<p>The complexity analysis of frequency based mode finding algorithm is <em>q<\/em><em>(n<\/em><em>2<\/em><em>)<\/em>.<\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Transform and conquer approach<\/strong><\/p>\n<p style=\"text-align: justify\">Instead, the array can be sorted and run length of an element can be calculated on the sorted array. Informally, mode finding using presorting is given as follows:<\/p>\n<ol>\n<li>Sort the element of an array.<\/li>\n<li>Calculate the run length of an element<\/li>\n<li>Print the element having longest length<\/li>\n<li>Exit.<\/li>\n<\/ol>\n<p>Formal algorithm based on [2] is given as follows:<\/p>\n<p>Sort A<\/p>\n<p>i \u00ac 0<\/p>\n<p>&nbsp;<\/p>\n<p>frequency \u00ac 0<\/p>\n<p>while i \u2264 n-1<\/p>\n<p>runlength \u00ac 1;\u00a0\u00a0 runvalue \u00ac A[i]<\/p>\n<p>&nbsp;<\/p>\n<p>while i+runlength \u2264 n-1 and A[i+runlength] = runvalue runlength = runlength + 1<\/p>\n<p>&nbsp;<\/p>\n<p>if runlength &gt; frequency<\/p>\n<p>frequency \u00ac runlength<\/p>\n<p>modevalue \u00ac runvalue<\/p>\n<p>&nbsp;<\/p>\n<p>i = i + runlength<\/p>\n<p>return modevalue<\/p>\n<p>&nbsp;<\/p>\n<p class=\"indent hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">Sorting requires <em>q<\/em> (<em>n<\/em> log <em>n<\/em>) time. The finding of a run length requires only linear time as the array is already sorted. Therefore the worst case performance of the algorithm would be less than the brute-force method.<\/p>\n<\/div>\n<div>\n<p><strong>Matrix Operations<\/strong><\/p>\n<p style=\"text-align: justify\">A matrix is a rectangular table of numbers. In scientific domain, matrices have many uses. Matrix addition and subtractions are relatively easy.<\/p>\n<p style=\"text-align: justify\">Most of the scientific applications use matrix operations like matrix inverse and matrix determinant. So there is a need to solve these problems. As the computational complexity of these algorithms are high, transform and conquer approach can be used. Gaussian elimination uses transform and conquer approach to solve set of equations. Additionally, it can be used to decompose matrices also. Matrix decomposition is useful for find inverse of a matrix and matrix determinant.<\/p>\n<p>First let us discuss the method of Gaussian elimination in the subsequent section.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Gaussian elimination method<\/strong><\/p>\n<p>Solving an equation means finding the values of the unknown. A simplest equation is of the form:<\/p>\n<p>&nbsp;<\/p>\n<p>Ax = y<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A solution of this equation is x = y\/A. but this is true only when (y \u00b9 0 and A is not zero). All values of x satisfies the equation when y=0. This logic can be extended for two unknowns. Let us consider the following set of equations:<\/p>\n<p>&nbsp;<\/p>\n<p>A11x + A12y = B1<\/p>\n<p>&nbsp;<\/p>\n<p>A21x + A22y = B2<\/p>\n<p>&nbsp;<\/p>\n<p>The equations can be solved first by finding x as<\/p>\n<p>&nbsp;<\/p>\n<p>x = (B1 \u2013 A12y) \/ A11<\/p>\n<p>&nbsp;<\/p>\n<p>Substituting this in the second equation gives y.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In general, if one plots these two equations as lines, then the intersection of two lines in a single point, then the system of linear equations has a unique solution. If the lines are parallel, then there is no solution. If the lines coincide, then there would be infinite number of solutions.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In many applications, one may have to solve \u2018n\u2019 equations with \u2018n\u2019 unknowns. The set of linear equations are as below:<\/p>\n<p>&nbsp;<\/p>\n<p>A11x1 + A12x2 + \u2026 + A1nxn = B1<\/p>\n<p>&nbsp;<\/p>\n<p>A21x1 + A22x2 + \u2026 + A2nxn = B2<\/p>\n<\/div>\n<p>\u2026<\/p>\n<p>&nbsp;<\/p>\n<p>An1x1 + An2x2 + \u2026 + Annxn = Bn<\/p>\n<p>&nbsp;<\/p>\n<p>In matrix form, the above can be represented as<\/p>\n<p>&nbsp;<\/p>\n<p>Ax = B<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Gaussian elimination, names after Gauss, uses transform and conquer approach to transform this set of equations with \u2018n\u2019 unknowns<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-249 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-300x114.png\" alt=\"\" width=\"300\" height=\"114\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-300x114.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-225x86.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1-350x133.png 350w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic1.png 727w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>The transformation can be represented as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-250\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2.png\" alt=\"\" width=\"470\" height=\"144\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2.png 470w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2-300x92.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2-65x20.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2-225x69.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic2-350x107.png 350w\" sizes=\"auto, (max-width: 470px) 100vw, 470px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Gaussian elimination aims to create a matrix with zeros in the lower triangle. This is called upper triangular matrix. This is done by elimination a variable at every stage in all equations. The advantage is that One can solve the last equation first, substitute into the second to last, and can proceed to solve the first one.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To do the manipulations, Gaussian elimination uses some elementary steps. The following elementary steps are used by Gaussian elimination.<\/p>\n<ol>\n<li>Exchanging two equations of the system<\/li>\n<\/ol>\n<p>In this, two equations are exchanged. For example, consider the following equations.<\/p>\n<p>&nbsp;<\/p>\n<p>x + y = 3<\/p>\n<p>2x + y = 4<\/p>\n<p>&nbsp;<\/p>\n<p>These equations can be exchanged as<\/p>\n<p>&nbsp;<\/p>\n<p>2x + y = 4<\/p>\n<p>X + y = 3<\/p>\n<p>&nbsp;<\/p>\n<ol start=\"2\">\n<li>Exchanging an equation with non-zero multiples<\/li>\n<\/ol>\n<p>Say,<\/p>\n<p>&nbsp;<\/p>\n<p>x + y = 2 can be replaced as<\/p>\n<p>2x + 2y = 4.<\/p>\n<p>&nbsp;<\/p>\n<ol start=\"3\">\n<li>Replacing the multiple of one equation to another equation. For example, row 2, R2, can be expressed as a multiple of row 1, R1, and row 3, R3<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p>The informal algorithm for Gaussian elimination is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-251\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3.png\" alt=\"\" width=\"979\" height=\"354\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3.png 979w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3-300x108.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3-768x278.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3-225x81.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic3-350x127.png 350w\" sizes=\"auto, (max-width: 979px) 100vw, 979px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>This illustrated in Example 1 [1].<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Example 1<\/p>\n<p class=\"hanging-indent\"><strong>Solve the set of equations using Gaussian Elimination method<\/strong><\/p>\n<p><em>3x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3\u00a0\u00a0 \u00a0= 11<\/em><\/p>\n<p><em>6x<\/em><em>1 + 4x<\/em><em>2 + x<\/em><em>3\u00a0 = 29 <\/em><\/p>\n<p><em>x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3\u00a0 \u00a0 \u00a0 =\u00a0 7<\/em><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In matrix notation, this can be written it as <em>Ax = b. Augment the equation as below and apply the elementary operations as shown below:<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-252\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4.png\" alt=\"\" width=\"639\" height=\"418\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4.png 639w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4-300x196.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4-225x147.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic4-350x229.png 350w\" sizes=\"auto, (max-width: 639px) 100vw, 639px\" \/><\/p>\n<p style=\"text-align: center\"><em>2x<\/em><em>2 \u2013 x<\/em><em>3\u00a0 = 7<\/em><\/p>\n<p style=\"text-align: center\"><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a02x<\/em><em>2\u00a0 = 8<\/em><\/p>\n<p style=\"text-align: center\"><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 x2 = 4<\/em><\/p>\n<p>Using these two variables, the remaining variable can be obtained as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><em>3x<\/em><em>1 + x<\/em><em>2 + x<\/em><em>3 = 11<\/em><\/p>\n<p><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a03x<\/em><em>2 + 5 = 11<\/em><\/p>\n<p><em>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0x2 = 11-5\/3 = 6\/3 = 2<\/em><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Apply the elementary operation to reduce the augmented matrix to a triangular form called echelon matrix. So the idea is to keep a11 as pivot and eliminate all a11 in other equations. For example, in the second equation, a11 can be eliminated by the factor R2-(a21\/a11). This operation is applied throughout the equation. Using the same logic, a11 is eliminated in all other equations. Similarly, using the multiple of (a31\/a11), (a41\/a11), \u2026, (an1\/a11), the matrix A can be reduced to a upper triangular matrix A\u2019. Then, the solution can be obtained by back substitution. The algorithm for forward elimination is given as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-253 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-300x113.png\" alt=\"\" width=\"300\" height=\"113\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-300x113.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-225x85.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5-350x132.png 350w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic5.png 767w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>The backward substitution is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-254 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-300x142.png\" alt=\"\" width=\"300\" height=\"142\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-300x142.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-225x107.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6-350x166.png 350w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic6.png 451w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p style=\"text-align: justify\">How many operations are required for Gaussian elimination? One division and n multiplication\/division\u00a0 \u00a0is\u00a0 \u00a0required.\u00a0\u00a0 \u00a0So\u00a0\u00a0 \u00a0(n+1)\u00a0\u00a0 \u00a0operations\u00a0\u00a0 \u00a0for\u00a0\u00a0 \u00a0(n-1)\u00a0\u00a0 \u00a0rows,\u00a0\u00a0 \u00a0requires (<em>n <\/em>-1)(<em>n <\/em>+1) = <em>n<\/em>2 -1 operations to eliminate the first column of matrix A. Similarly the second row involves (<em>n <\/em>-1)2 -1 operations. So all n rows, the numbers of operations are<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-255\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic7.png\" alt=\"\" width=\"200\" height=\"122\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic7.png 200w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M17Pic7-65x40.png 65w\" sizes=\"auto, (max-width: 200px) 100vw, 200px\" \/><\/p>\n<p>So Gaussian elimination method time complexity is O(n3 ) .<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\n<p>In short, one can conclude as part of this module 17 that<\/p>\n<ul>\n<li>Transform and Conquer is an effective design paradigm<\/li>\n<li>Matrix operations are computationally very intensive<\/li>\n<li>Gaussian elimination is an effective technique that uses transform and conquer method<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\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 \u00a0the 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<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"author":4,"menu_order":7,"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-88","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\/88","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":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/88\/revisions"}],"predecessor-version":[{"id":257,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/88\/revisions\/257"}],"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\/88\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=88"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=88"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=88"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=88"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}