{"id":118,"date":"2018-07-19T06:05:51","date_gmt":"2018-07-19T06:05:51","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=118"},"modified":"2018-07-19T06:11:53","modified_gmt":"2018-07-19T06:11:53","slug":"more-transform-and-conquer-problems-2","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/more-transform-and-conquer-problems-2\/","title":{"rendered":"More Transform and Conquer Problems"},"content":{"raw":"
\r\n\r\nThis module 19 focuses on an important design paradigm called Transform and Conquer. This module discusses problems related to polynomial evaluation and faster exponentiation. The learning objectives of this module are\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Transform and conquer variant representation change.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain polynomial evaluation using Horner\u2019s method.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain faster exponentiation\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To problem reduction method\r\n\r\n \r\n\r\nTransform and Conquer Design paradigm<\/strong>\r\n\r\n \r\n

Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity [2,3]. 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\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 First stage involves the transformation to another problem that is more amenable for solution\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.\r\n\r\n \r\n\r\n \r\n\r\nVariations of Transform and Conquer<\/strong>\r\n\r\n \r\n\r\nThree variants of transform and conquer are as follows:\r\n\r\n \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\r\n \r\n\r\nInstance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance.\r\n\r\n<\/div>\r\n \r\n\r\nChange of Representation<\/strong>\r\n\r\n \r\n

Change of representation is another useful variant of transform and conquer design paradigm. As part of this technique, two examples are discussed as part of the problem.<\/p>\r\n \r\n\r\n \r\n\r\nPolynomial Evaluation<\/strong>\r\n\r\n \r\n\r\nOne of the common problem is scientific domain is the evaluation of polynomial. A polynomial is given as follows:\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nFaster Exponentiation<\/strong>\r\n\r\n \r\n\r\nExponentiation is the problem of finding x<\/em>n<\/em>.<\/em> The traditional algorithm for solving this is given below:\r\n\r\n \r\n\r\nAlgorithm Exp(x, n)\r\n\r\n \r\n\r\nif n = 1 then\r\n\r\n \r\n\r\nreturn x\r\n\r\n \r\n\r\nelse\r\n\r\n \r\n\r\nreturn x \u00b4 Exp(x,n-1)\r\n\r\n \r\n\r\nend if\r\n\r\n \r\n\r\nend\r\n\r\n \r\n\r\nComplexity Analysis<\/strong>\r\n\r\n \r\n

What is the complexity of this algorithm? The complexity is O(n) as the algorithm requires (n-1<\/em>) multiplications. If the exponent is large, the number of multiplications required would increase considerably. Therefore, a better solution can be provided for finding exponentiation using transform and conquer method.<\/p>\r\n \r\n\r\nIdea of Faster Exponentiation:<\/strong>\r\n\r\n \r\n\r\nThe concept of fast exponentiation was given in a Hindu literature Chandah Sutra in 200 BC.\r\n

x<\/em>2 can be computed with one multiplication. If x<\/em>4 needs to be computed, it can be computed as ( x<\/em>2 )2 . In this case, only two multiplications are required instead of traditional four multiplications. Similarly, x<\/em>8 can be computed as (( x<\/em>2 ) 2 )2 with three multiplications. In general, the faster exponentiation can be done using log n computations.<\/p>\r\n \r\n\r\nThe informal algorithm for computing is given as follows:\r\n

    \r\n \t
  1. Represent the exponent as a binary pattern P. Let the maximum number of bits be p.<\/em><\/li>\r\n<\/ol>\r\n
      \r\n \t
    1. Scan the binary bits of pattern P.<\/em><\/li>\r\n<\/ol>\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n
      \r\n\r\nb<\/em>i<\/em>\u00a0 <\/em>=1: term = x *\u00a0 term\r\n\r\n \r\n\r\nEnd case\r\n\r\n \r\n\r\nEnd for\r\n\r\n \r\n\r\nReturn Product\r\n\r\n \r\n\r\nEnd.\r\n\r\n \r\n\r\n \r\n\r\nComplexity analysis:<\/strong>\r\n\r\n<\/div>\r\n
      \r\n\r\n \r\n

      The complexity of the algorithm depends on the binary representations of\u00a0 Therefore, the number of multiplications would be between \u00ea log n<\/em> \u00fa and 2 \u00eb 2 \u00fb<\/p>\r\ncomplexity of the algorithm is O(log n).\u00a0 the given number. \u00ea\u00eb log2 n<\/em>\u00fa\u00fb . Hence, the\r\n\r\n<\/div>\r\n \r\n\r\nProblem Reduction:<\/strong>\r\n\r\n \r\n

      Problem reduction is another variant of this paradigm. Assume that there are two problems A and B. The problem A is unsolvable and problem B has an algorithm. Hence, the logic of problem reduction is the conversion of instance of problem A into instance of problem B using an algorithm. Then the problem A can be solved by invoking the problem solver of B as a subroutine. Then, the result can be converted back. Some of the examples of problem reduction are computation of LCM in terms of GCD, reducing game problems to graph search problems.<\/p>\r\n \r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n \r\n\r\nIn short, one can conclude as part of this module 19 that\r\n

        \r\n \t
      • Representation Change is an effective way to solve problems.<\/li>\r\n \t
      • Horner method uses representation Change.<\/li>\r\n \t
      • Faster exponentiation can be done using transform and conquer method.<\/li>\r\n<\/ul>","rendered":"
        \n

        This module 19 focuses on an important design paradigm called Transform and Conquer. This module discusses problems related to polynomial evaluation and faster exponentiation. The learning objectives of this module are<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Transform and conquer variant representation change.<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain polynomial evaluation using Horner\u2019s method.<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain faster exponentiation<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To problem reduction method<\/p>\n

         <\/p>\n

        Transform and Conquer Design paradigm<\/strong><\/p>\n

         <\/p>\n

        Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity [2,3]. 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

         <\/p>\n

        1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 First stage involves the transformation to another problem that is more amenable for solution<\/p>\n

        2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.<\/p>\n

         <\/p>\n

         <\/p>\n

        Variations of Transform and Conquer<\/strong><\/p>\n

         <\/p>\n

        Three variants of transform and conquer are as follows:<\/p>\n

         <\/p>\n

        \u2013\u00a0 Instance Simplification<\/p>\n

        \u2013\u00a0 Representation Change<\/p>\n

        \u2013\u00a0 Problem Reduction<\/p>\n

         <\/p>\n

        Instance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance.<\/p>\n<\/div>\n

         <\/p>\n

        Change of Representation<\/strong><\/p>\n

         <\/p>\n

        Change of representation is another useful variant of transform and conquer design paradigm. As part of this technique, two examples are discussed as part of the problem.<\/p>\n

         <\/p>\n

         <\/p>\n

        Polynomial Evaluation<\/strong><\/p>\n

         <\/p>\n

        One of the common problem is scientific domain is the evaluation of polynomial. A polynomial is given as follows:<\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        Faster Exponentiation<\/strong><\/p>\n

         <\/p>\n

        Exponentiation is the problem of finding x<\/em>n<\/em>.<\/em> The traditional algorithm for solving this is given below:<\/p>\n

         <\/p>\n

        Algorithm Exp(x, n)<\/p>\n

         <\/p>\n

        if n = 1 then<\/p>\n

         <\/p>\n

        return x<\/p>\n

         <\/p>\n

        else<\/p>\n

         <\/p>\n

        return x \u00b4 Exp(x,n-1)<\/p>\n

         <\/p>\n

        end if<\/p>\n

         <\/p>\n

        end<\/p>\n

         <\/p>\n

        Complexity Analysis<\/strong><\/p>\n

         <\/p>\n

        What is the complexity of this algorithm? The complexity is O(n) as the algorithm requires (n-1<\/em>) multiplications. If the exponent is large, the number of multiplications required would increase considerably. Therefore, a better solution can be provided for finding exponentiation using transform and conquer method.<\/p>\n

         <\/p>\n

        Idea of Faster Exponentiation:<\/strong><\/p>\n

         <\/p>\n

        The concept of fast exponentiation was given in a Hindu literature Chandah Sutra in 200 BC.<\/p>\n

        x<\/em>2 can be computed with one multiplication. If x<\/em>4 needs to be computed, it can be computed as ( x<\/em>2 )2 . In this case, only two multiplications are required instead of traditional four multiplications. Similarly, x<\/em>8 can be computed as (( x<\/em>2 ) 2 )2 with three multiplications. In general, the faster exponentiation can be done using log n computations.<\/p>\n

         <\/p>\n

        The informal algorithm for computing is given as follows:<\/p>\n

          \n
        1. Represent the exponent as a binary pattern P. Let the maximum number of bits be p.<\/em><\/li>\n<\/ol>\n
            \n
          1. Scan the binary bits of pattern P.<\/em><\/li>\n<\/ol>\n

            \"\"<\/p>\n

            \"\"<\/p>\n

            \"\"<\/p>\n

            \n

            b<\/em>i<\/em>\u00a0 <\/em>=1: term = x *\u00a0 term<\/p>\n

             <\/p>\n

            End case<\/p>\n

             <\/p>\n

            End for<\/p>\n

             <\/p>\n

            Return Product<\/p>\n

             <\/p>\n

            End.<\/p>\n

             <\/p>\n

             <\/p>\n

            Complexity analysis:<\/strong><\/p>\n<\/div>\n

            \n

             <\/p>\n

            The complexity of the algorithm depends on the binary representations of\u00a0 Therefore, the number of multiplications would be between \u00ea log n<\/em> \u00fa and 2 \u00eb 2 \u00fb<\/p>\n

            complexity of the algorithm is O(log n).\u00a0 the given number. \u00ea\u00eb log2 n<\/em>\u00fa\u00fb . Hence, the<\/p>\n<\/div>\n

             <\/p>\n

            Problem Reduction:<\/strong><\/p>\n

             <\/p>\n

            Problem reduction is another variant of this paradigm. Assume that there are two problems A and B. The problem A is unsolvable and problem B has an algorithm. Hence, the logic of problem reduction is the conversion of instance of problem A into instance of problem B using an algorithm. Then the problem A can be solved by invoking the problem solver of B as a subroutine. Then, the result can be converted back. Some of the examples of problem reduction are computation of LCM in terms of GCD, reducing game problems to graph search problems.<\/p>\n

             <\/p>\n

             <\/p>\n

            Summary<\/strong><\/p>\n

             <\/p>\n

            In short, one can conclude as part of this module 19 that<\/p>\n

              \n
            • Representation Change is an effective way to solve problems.<\/li>\n
            • Horner method uses representation Change.<\/li>\n
            • Faster exponentiation can be done using transform and conquer method.<\/li>\n<\/ul>\n","protected":false},"author":4,"menu_order":9,"template":"","meta":{"_acf_changed":false,"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-118","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\/118","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":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/118\/revisions"}],"predecessor-version":[{"id":128,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/118\/revisions\/128"}],"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\/118\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=118"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=118"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=118"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}