{"id":77,"date":"2018-07-19T05:20:06","date_gmt":"2018-07-19T05:20:06","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=77"},"modified":"2018-07-25T09:06:15","modified_gmt":"2018-07-25T09:06:15","slug":"decrease-and-conquer-design-paradigm","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/decrease-and-conquer-design-paradigm\/","title":{"rendered":"More Applications of Divide and Conquer"},"content":{"raw":"<p style=\"text-align: center\"><strong>Module 14<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>More Applications of Divide and Conquer<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">This module 14 focuses on decrease and conquer paradigm. The Learning objectives of this module are as follows:<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">To understand decrease and conquer paradigm<\/li>\r\n \t<li style=\"text-align: justify\">To understand Insertion Sort<\/li>\r\n \t<li style=\"text-align: justify\">To understand topological Sort<\/li>\r\n \t<li style=\"text-align: justify\">To understand Permutations and Subsets<\/li>\r\n \t<li style=\"text-align: justify\">To know the algorithms for generation of Permutations and Subsets<\/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. This paradigm is useful for solving a variety of problems in the computer science domain.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The steps of decrease and conquer is given as follows:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Reduce problem instance to same problem with smaller Instance<\/span><\/li>\r\n \t<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Solve problem of smaller instance<\/span><\/li>\r\n \t<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Extend solution of smaller instance to obtain solution to original problem with larger instance<\/span><\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">For example, consider the following problem, of computation of <em>a<\/em><em>n<\/em> . The problem can be solved by reducing it another problem of <em>a<\/em> <em>n<\/em> = <em>a<\/em> \u00b4 <em>a<\/em><em>n<\/em>-1 if n&gt;0, If n =0, then its value is n. the problem can further be reduced. It can be observed that this design paradigm reduces a given problem size by a certain decreasing factor. Then it establishes a relationship between the solution to a given instance of the problem and that to a smaller instance of it. Once the relationship is established, it is exploited using the top-down (recursive) or bottom-up (iterative) approach to derive the final solution.<\/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 and Conquer by a constant:<\/strong>\r\n<p style=\"text-align: justify\">In decrease by a constant variation, the problem size is reduced by a constant (mostly one) at every iteration. In this category, a problem of size <em>n<\/em> is divided into a subproblem of size \u2018<em>n<\/em> \u2212 1\u2019 and an individual element <em>n<\/em>. This design paradigm then incorporates the individual element into the subproblem solution to obtain the final solution. The examples of this category are Insertion sort, Topological sort, generation of permutations and subsets. The steps of the decrease by a constant are as follows:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 1:<\/strong> Reduce a problem <em>A<\/em> of size <em>n<\/em> into a problem of size \u2018<em>n<\/em> \u2212 1\u2019 and an individual element <em>n<\/em>.<\/p>\r\n<p style=\"text-align: justify\"><strong>Step 2:<\/strong> Solve the subproblem recursively or iteratively.<\/p>\r\n<p style=\"text-align: justify\"><strong>Step 3:<\/strong> Incorporate the individual element into the solution of the subproblem to obtain the solution of the given problem.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In decrease by a constant factor, a problem instance is reduced by a constant factor, which is 2 in most of the cases. The examples of this category are binary search, faster exponentiation, and Russian Peasant method for multiplying two numbers. In decrease by a variable factor, the reduction size varies from one iteration of the algorithm to another. The number of subproblems may also vary. The examples of this category are Euclid algorithm, selection by partition and Nim type games.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\">Decrease and conquer by a constant approach is discussed in the following sections.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Insertion Sort<\/strong><\/p>\r\n<p style=\"text-align: justify\">Insertion sort is based on decrease and conquer design approach. Its essential approach is to take an array A[0..n-1] and reduces its instance by a factor of 1, Then the instance A[0..n-1] is reduced to A[0..n-2]. This process is repeated till the problem is reduced to a small problem enough to get solved.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The first element is initially considered to be a sorted element; therefore, the second element needs to be compared with one element, requiring only one comparison. The third element needs to be compared with the previous two elements. Thus, the logic of insertion sort is to take an element and copy it to a temporary location. Then the position is looked after for insertion. Once, a position is located, then the array is moved right and the element is inserted. This process is repeated till the entire array is sorted.<\/p>\r\n<p class=\"hanging-indent\">Informally the procedure is as follows:<\/p>\r\n\r\n<ul>\r\n \t<li>Finding the element\u2019s proper place<\/li>\r\n \t<li>Making room for the inserted element (by shifting over other elements)<\/li>\r\n \t<li>Inserting the element<\/li>\r\n<\/ul>\r\n<strong>Formal Algorithm<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe formal insertion sort algorithm [2,3] is given below:\r\n\r\n&nbsp;\r\n\r\nALGORITHM InsertionSort(A[0..N-1])\r\n\r\n&nbsp;\r\n\r\nfor i = 1 to N-1 do\r\n\r\n&nbsp;\r\n\r\ntemp = A[i]\r\n\r\n&nbsp;\r\n\r\nj = i-1\r\n\r\n&nbsp;\r\n\r\nwhile j \u2265 0 and A[j] &gt; temp do\r\n\r\n&nbsp;\r\n\r\nA[j+1] &lt; A[j]\r\n\r\n&nbsp;\r\n\r\nj = j-1\r\n\r\n&nbsp;\r\n\r\nA[j+1] = temp\r\n\r\n&nbsp;\r\n\r\nThis procedure is illustrated in the following numerical example.\r\n\r\n&nbsp;\r\n\r\nExample 1: Apply quicksort to the following set of numbers and show the intermediate result.\r\n\r\nSolution:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As discussed earlier, the first number is considered as a sorted number. Then one by one elements are inserted into its appropriate position, and the length of the sorted list is increased. This process is continued till all the elements are sorted.<\/p>\r\n\r\n<ul>\r\n \t<li>88 | 43 68 92 23 34 11<\/li>\r\n \t<li>43 88 | 68 92 23 34 11<\/li>\r\n \t<li>43 68 88 | 92 23 34 11<\/li>\r\n \t<li>43 68 88 92 | 23 34 11<\/li>\r\n \t<li>23 43 68 88 92 | 34 11<\/li>\r\n \t<li>23 34 43 68 88 92 | 11<\/li>\r\n<\/ul>\r\nThe final sorted list is : 11 23 34 43 68 88 92\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">The basic operation of this algorithm is a comparison operation. The number of comparisons\u00a0depends on the nature of inputs. As said earlier, The first element is initially\u00a0 considered to be a\u00a0\u00a0sorted element; therefore, the second element needs to be compared with one element, requiring\u00a0\u00a0only one comparison. The third element needs to be compared with the previous two elements.\u00a0Worst case analysis: The worst-case complexity analysis of insertion sort can be determined as<\/p>\r\n&nbsp;\r\n\r\nfollows: Hence, this requires two comparisons. Thus, in general, for <em>n<\/em> elements, the number of\r\n\r\n&nbsp;\r\n\r\ncomparisons would be as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-238\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic1-1.png\" alt=\"\" width=\"163\" height=\"127\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Best-case complexity analysis The best-case complexity of insertion sort occurs when the list is in a sorted order. Even in this case one comparison is required, to compare an item with its previous element. Thus, at least <em>n<\/em> \u2212 1 comparisons are required. Therefore, the complexity analysis of insertion sort in best case would be<\/p>\r\n<img class=\"aligncenter size-full wp-image-239\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic2.png\" alt=\"\" width=\"132\" height=\"60\" \/>\r\n\r\n&nbsp;\r\n\r\nTherefore, the complexity of the algorithm is <em>O<\/em>(<em>n<\/em>). In addition, no shifting of data is required and space requirement for the sort is <em>n<\/em>. Similarly, the average case complexity of insertion sort is\u00a0 \u00a0O (<em>n<\/em>2 )\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Topological Sort<\/strong><\/p>\r\n<p style=\"text-align: justify\">Topological sort is one of the most important sorting used in variety of applications such as course prerequisites and project management. Thus, the objective of topological sort is to produce an ordering that implies a partial ordering on the elements. Thus, the ordering of the elements satisfies the given constraints. First, given a set of constraints graph is constructed. Every vertex represents an item. Every constraint is represented as an edge. For example, the constraint where item A must finish before B, then a directed edge is created from A to B. If the edge is represented as &lt;A,B&gt;, then the vertex A appears before vertex B in the linear ordering list.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Topological sort is performed for directed acyclic graphs (DAGs), and it aims to arrange the vertices of a given DAG in a linear order. Thus, a DAG is an essential and necessary condition for topological sort. What is a DAG? A DAG has no path that starts and ends at the same vertex. A sample DAG is shown below in Fig. 1.0<\/p>\r\n<img class=\"aligncenter size-full wp-image-240\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3.png\" alt=\"\" width=\"344\" height=\"213\" \/>\r\n<p style=\"text-align: center\"><strong>Fig. 1.0: A sample DAG<\/strong><\/p>\r\n\r\n<div>\r\n<p style=\"text-align: justify\">Recollect that a node of a graph that has no incoming edge is called a source and a vertex that has no outgoing edge is called a sink. A DAG has only one source and one sink. If a graph has many sources, then one can create a super source by creating a node and connecting it to all source nodes.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Topological Sort using DFS<\/strong><\/p>\r\n<p style=\"text-align: justify\">Topological sorting can be performed using BFS and DFS algorithms. The following is the informal algorithm for performing topological sort using DFS [2,3]:<\/p>\r\n\r\n<ol>\r\n \t<li>Perform DFS traversal, noting the order of the vertices that are popped off stack<\/li>\r\n \t<li>Reverse order solves topological sorting problem<\/li>\r\n<\/ol>\r\n<\/div>\r\n<div>\r\n\r\nIn other words, the finish time F(u) of all the vertices of a graph is obtained. Then a queue Q is created and all the vertices are inserted on to the queue Q based on finish time. Then the contents of the queue is printed as the sorted sequence.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Formal Algorithm<\/strong><\/p>\r\nThe formal algorithm for Topological sort is given as follows:Topological-\r\n\r\n&nbsp;\r\n\r\nSort()\r\n\r\n&nbsp;\r\n\r\nBegin\r\n\r\n&nbsp;\r\n\r\nRun DFS\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">When a vertex is finished, output it and assign a number<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Vertices are output in reverse topological order<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">End.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be used on the following problem. Consider the following graph shown in Fig 2.<\/p>\r\n\r\n<\/div>\r\n<img class=\"aligncenter wp-image-241 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-300x280.png\" alt=\"\" width=\"300\" height=\"280\" \/>\r\n<p style=\"text-align: center\"><strong> Fig 2: Initial Graph <\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Initially A is visited. Then the verted D is visited. Then, vertex E is visited. Then, vertex F is visited. Finally, vertex H is visited. This is numbered as 5. By reversing the DFS traversal, it can be observed that F is numbered as 4, vertex E is 3, vertex D is numbered as 2 and finally vertex A as 1. By reversing this one get the topological order which is given as A D E F H.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Topological ordering using source node removal algorithm<\/strong><\/p>\r\n<p style=\"text-align: justify\">In source node removal algorithm, one has to identify the source repeatedly and it is removed. Simultaneously, all the edges incident to it are removed. This process is repeated till either no vertex is left or there is no source among remaining vertices left.\u00a0As an example, consider the following graph shown in Fig. 3. This represents the prerequisites of a set of courses that needs to be taken.<\/p>\r\n<img class=\"aligncenter size-full wp-image-243\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1.png\" alt=\"\" width=\"389\" height=\"193\" \/>\r\n\r\n&nbsp;\r\n<div>\r\n<p style=\"text-align: center\"><strong>Fig. 3. : Example course graph<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed, the node that has no incoming edges is C1. Therefore, it is removed along with its incident edges. Then, C3 is the vertex that is source. Then, it is removed. Then C4 is the vertex , that is source and hence removed. Finally, the node c5 is selected. Therefore, the sorting order is given as follows: C1, C3, C4 and C5.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n<p style=\"text-align: justify\">Let there be <em>m<\/em> vertices and <em>n<\/em> edges of a graph. Then the topological algorithm takes <em>O<\/em>(<em>m<\/em>) time for picking the vertex that has no incoming edges. This is done by examining the corresponding adjacency matrix or adjacency list. Picking the vertex after identification takes a constant time. Deleting the vertex along with its edges takes <em>O<\/em>(<em>n<\/em>) time. Putting together, the algorithm takes <em>O<\/em>(<em>m <\/em>+<em> n<\/em>) time.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Permutations<\/strong><\/p>\r\n<p style=\"text-align: justify\">Permutation is an arrangement of objects in a linear order. A permutation of a set of objects is a particular ordering of those objects For example, for three objects A, B and C, the first element\u00a0\u00a0A can be arranged in three ways, the second object B in two ways, and the third object C in one way. Thus, the three objects can be arranged in 3! Ways. Therefore, the permutations are {ABC, ACB, BAC, BCA, CAB, CBA}. Each arrangement is called a <em>permutation<\/em>. In general, there are <em>n<\/em>! ways of arranging a set of<em> n <\/em>elements.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">Generating a permutation may seem to be a trivial task. However, in reality, it is not so. For example, if there are 100 elements, then there are 100! ways of arranging the elements. Therefore, there is a need for generating permutations in an effective manner.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Decrease and Conquer Approach:<\/strong><\/p>\r\n<p style=\"text-align: justify\">Decrease-and-conquer paradigm is used for permutation generation. In order to generate <em>n<\/em>!\u00a0permutations using the decrease-and-conquer paradigm. For example, consider the problem of\u00a0generating permutations for the set {A,B,C}.<\/p>\r\n&nbsp;\r\n\r\nThe solution using the decrease-and-conquer paradigm can be given as follows:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The problem of permutation of three elements <em>P<\/em> is reduced to the subproblem(<em>P<\/em>\u00a2) of generating permutation of two elements {A,B}. Then, this problem is reduced to the problem of generating permutation of subproblem {A}.The permutation of {A} is {A}. Then, the element {B} is introduced to enlarge the solution. Then the element {A} is added to get the final answer.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Informal Algorithm<\/strong><\/p>\r\n&nbsp;\r\n\r\nTo find all permutations of n objects:\r\n\r\n&nbsp;\r\n\r\nFind all permutations of n-1 of those objects\r\n\r\n<\/div>\r\nInsert the remaining object into all possible positions of each permutation of n-1 objects\r\n\r\n&nbsp;\r\n\r\nThis can be illustrated as follows:\r\n\r\n&nbsp;\r\n\r\nThis process is described as follows:\r\n\r\n&nbsp;\r\n\r\nGiven the empty set { }, the only possible permutation is { }\r\n\r\n&nbsp;\r\n\r\nGiven the set {A}, the only possible permutation is {A}\r\n\r\n&nbsp;\r\n\r\nGiven the set {A, B}, the possible permutations are\r\n\r\n&nbsp;\r\n\r\n{AB, BA}\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-244 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6.png\" alt=\"\" width=\"684\" height=\"456\" \/>\r\n\r\n&nbsp;\r\n<div>\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<p class=\"hanging-indent\"><strong>Johnston\u2013Trotter Algorithm<\/strong><\/p>\r\n<p style=\"text-align: justify\">Another way of generating permutations is by using the Johnston\u2013Trotter algorithm that uses the decrease-and-conquer strategy. This algorithm generates permutations in a non-lexicographical order. In this algorithm, every integer is associated with a direction. For example, &lt;3 means the integer 3 is assigned a direction left and &gt;3 means it is assigned a direction right. The core idea of this algorithm is that, a integer is called a mobile integer if it points to a neighbouring integer than is lesser than it. For example, in the generation of a permutation like &lt;2 &lt;3 &lt;1, 3 is a mobile integer as it is pointing to an integer that is lesser than it. The right- and left-most columns of a list are called its boundaries. If any mobile integer in a boundary does not point to any integer, then the number is not a mobile number. In the generated sequence &lt;3 &lt;2 &lt;1, 3 is no longer a mobile number as it is in the left-most column (or boundary).<\/p>\r\n&nbsp;\r\n\r\nInformally, the Johnston\u2013Trotter algorithm is given as follows:\r\n\r\n&nbsp;\r\n\r\nALGORITHM Johnson Trotter (n)\r\n\r\n&nbsp;\r\n\r\nInitialize the first permutation with 1 2 \u2026 n\r\n\r\n&nbsp;\r\n\r\nwhile there exists a mobile integer k do\r\n\r\n&nbsp;\r\n\r\nfind k \u2013 the largest mobile integer\r\n\r\n&nbsp;\r\n\r\nswap k and the adjacent integer pointed by arrow reverse the direction of all integers that are larger than k\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\nThis algorithm for generating permutations for three elements {1,2,3} is given below in Table 1.:\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Table 1. Generating permutations for three elements using the Johnston\u2013Trotter\u00a0<\/strong><strong>algorithm<\/strong><\/p>\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td>Permutations<\/td>\r\n<td>Descriptions<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>&lt;1 &lt;2 &lt;3<\/td>\r\n<td>3 is the mobile integer as it points to \u20182\u2019 that is smaller. Therefore, move the mobile integer.<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>&lt;1 &lt;3 &lt;2<\/td>\r\n<td>Now the mobile integer is pointing to \u20181\u2019, which is smaller. Therefore, move it<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>&lt;3 &lt;1 &lt;2<\/td>\r\n<td>The mobile integer 3 has reached the boundary and does not point to any element. Therefore, look for the next largest integer, which in this case is \u20182\u2019. Move it to get the next permutation and also change the direction of the integers that are larger than the current mobile integer.<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>3&gt; &lt;2 &lt;1<\/td>\r\n<td>It can be observed that the direction of 3 is changed. In other words, 3 has become a mobile integer again. Now move it again.<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>&lt;2 3&gt; &lt;1<\/td>\r\n<td>Now the mobile integer 3 points to a smaller number \u20181\u2019. Therefore, move it again.<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>&lt;2 &lt;1 3&gt;<\/td>\r\n<td>The numbers 2 and 3 have reached the boundaries and do not point to any integers that are lesser than these. As there are no mobile integers, exit.<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<strong><span style=\"text-align: initial;font-size: 1em\">Generating Subsets<\/span><\/strong>\r\n<div>\r\n\r\nThe following are the important terminologies related to this problem:\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">Set : A collection of distinct elements. For example = colour = { red, Blue, Green}<\/p>\r\n<p class=\"hanging-indent\">Subset : A set B is a subset of A , if its all elements are in A. For example, A = {1,2}, then the subsets of A are { }. {1}, {2}, {1,2}<\/p>\r\n<p class=\"hanging-indent\">Power set: The set of all subsets is called power set<\/p>\r\n<p class=\"hanging-indent\"><strong>Generating Subsets Using Decrease-and-conquer Strategy<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">To generate subsets <em>A<\/em> = {<em>a<\/em>1, <em>a<\/em>2, <em>a<\/em>3, \u2026, <em>a<\/em><em>n<\/em>,}, one has to divide this into two groups: <em>S<\/em>1 = {<em>a<\/em>1, <em>a<\/em>2, <em>a<\/em>3, \u2026,<em> a<\/em><em>n<\/em>\u22121} and<em> S<\/em>2 = {<em>a<\/em><em>n<\/em>}. Add<em> a<\/em><em>n<\/em> to each subset of<em> S<\/em>1 to get the final solution. Example:<\/p>\r\n{1,2}\r\n\r\n&nbsp;\r\n\r\nreduce this problem to\r\n\r\n&nbsp;\r\n\r\n{1}\r\n\r\n&nbsp;\r\n\r\nreduce this problem to\r\n\r\n&nbsp;\r\n\r\n{}\r\n\r\n&nbsp;\r\n\r\nSo the solution is\r\n\r\n&nbsp;\r\n\r\n{}\r\n\r\n&nbsp;\r\n\r\n{1} {} after {1} is inserted\r\n\r\n&nbsp;\r\n\r\n{1, 2} {2} {1} {}\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">Another easy approach to generate subsets is to use a binary string for <em>n<\/em> digits. The idea is to have a 1:1 correspondence between a binary string and the generation of subsets. Informal algorithm based on [1] is given as follows:<\/p>\r\n\r\n<ol>\r\n \t<li>Initialize the counter i to 2<em>n<\/em> \u22121<\/li>\r\n \t<li>Initialize the item counter j = number of items<\/li>\r\n \t<li>Extract the jth bit from the counter. If binary digit is 1, then include the item , otherwise, exclude it<\/li>\r\n \t<li>Print the subsets.<\/li>\r\n<\/ol>\r\nThe following Table 2 summarizes the generation of the subsets.\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong> Table 2: Generation of Subsets<\/strong><\/p>\r\n<img class=\"aligncenter size-full wp-image-245\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7.png\" alt=\"\" width=\"752\" height=\"441\" \/>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\" style=\"text-align: justify\"><strong>Table 1: Generation of Subsets <\/strong>Informally, the algorithm for generation of subsets [1,2] is given as follows:<\/p>\r\n<p style=\"text-align: justify\"><strong>Step 1<\/strong>: For <em>n <\/em>elements represent sets with an <em>n<\/em>-bit string.<\/p>\r\n<p style=\"text-align: justify\"><strong>Step 2<\/strong>: For each bit of the <em>n<\/em>-bit string, perform the following operation:<\/p>\r\n<p class=\"hanging-indent\" style=\"text-align: justify\"><span style=\"text-align: initial;text-indent: 1em;font-size: 1em\"><img class=\"aligncenter size-full wp-image-246\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic8.png\" alt=\"\" width=\"198\" height=\"57\" \/>Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the<\/span><span style=\"text-align: initial;text-indent: 1em;font-size: 1em\">\r\n<strong>Step 3:\u00a0<\/strong><\/span>Print the resulting subsets 0 \u2192 2<em>n<\/em>\u22121, which represents the power set of <em>n <\/em>elements. Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the counting can be said as follows:<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\r\n&nbsp;\r\n\r\nThe complexity analysis is O(n 2<em>n<\/em> ).\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\r\n<p style=\"text-align: justify\">In short, one can conclude as part of this module 14 that<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">Decrease and conquer guarantee solution and effective.<\/li>\r\n \t<li style=\"text-align: justify\">Insertion sort and Topological sort are important problems and can be solved by decrease and conquer strategy.<\/li>\r\n \t<li style=\"text-align: justify\">Generating Permutations and subsets are important problems that can be solved effectively using decrease and conquer strategy.<\/li>\r\n<\/ul>\r\n<strong>References:<\/strong>\r\n<ol>\r\n \t<li style=\"text-align: justify\"><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\r\n \t<li style=\"text-align: justify\"><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t<li style=\"text-align: justify\">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":"<p style=\"text-align: center\"><strong>Module 14<\/strong><\/p>\n<p style=\"text-align: center\"><strong>More Applications of Divide and Conquer<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This module 14 focuses on decrease and conquer paradigm. The Learning objectives of this module are as follows:<\/p>\n<ul>\n<li style=\"text-align: justify\">To understand decrease and conquer paradigm<\/li>\n<li style=\"text-align: justify\">To understand Insertion Sort<\/li>\n<li style=\"text-align: justify\">To understand topological Sort<\/li>\n<li style=\"text-align: justify\">To understand Permutations and Subsets<\/li>\n<li style=\"text-align: justify\">To know the algorithms for generation of Permutations and Subsets<\/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. This paradigm is useful for solving a variety of problems in the computer science domain.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The steps of decrease and conquer is given as follows:<\/p>\n<ol>\n<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Reduce problem instance to same problem with smaller Instance<\/span><\/li>\n<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Solve problem of smaller instance<\/span><\/li>\n<li style=\"text-align: justify\"><span style=\"font-size: 1em\">Extend solution of smaller instance to obtain solution to original problem with larger instance<\/span><\/li>\n<\/ol>\n<p style=\"text-align: justify\">For example, consider the following problem, of computation of <em>a<\/em><em>n<\/em> . The problem can be solved by reducing it another problem of <em>a<\/em> <em>n<\/em> = <em>a<\/em> \u00b4 <em>a<\/em><em>n<\/em>-1 if n&gt;0, If n =0, then its value is n. the problem can further be reduced. It can be observed that this design paradigm reduces a given problem size by a certain decreasing factor. Then it establishes a relationship between the solution to a given instance of the problem and that to a smaller instance of it. Once the relationship is established, it is exploited using the top-down (recursive) or bottom-up (iterative) approach to derive the final solution.<\/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 and Conquer by a constant:<\/strong><\/p>\n<p style=\"text-align: justify\">In decrease by a constant variation, the problem size is reduced by a constant (mostly one) at every iteration. In this category, a problem of size <em>n<\/em> is divided into a subproblem of size \u2018<em>n<\/em> \u2212 1\u2019 and an individual element <em>n<\/em>. This design paradigm then incorporates the individual element into the subproblem solution to obtain the final solution. The examples of this category are Insertion sort, Topological sort, generation of permutations and subsets. The steps of the decrease by a constant are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 1:<\/strong> Reduce a problem <em>A<\/em> of size <em>n<\/em> into a problem of size \u2018<em>n<\/em> \u2212 1\u2019 and an individual element <em>n<\/em>.<\/p>\n<p style=\"text-align: justify\"><strong>Step 2:<\/strong> Solve the subproblem recursively or iteratively.<\/p>\n<p style=\"text-align: justify\"><strong>Step 3:<\/strong> Incorporate the individual element into the solution of the subproblem to obtain the solution of the given problem.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In decrease by a constant factor, a problem instance is reduced by a constant factor, which is 2 in most of the cases. The examples of this category are binary search, faster exponentiation, and Russian Peasant method for multiplying two numbers. In decrease by a variable factor, the reduction size varies from one iteration of the algorithm to another. The number of subproblems may also vary. The examples of this category are Euclid algorithm, selection by partition and Nim type games.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Decrease and conquer by a constant approach is discussed in the following sections.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Insertion Sort<\/strong><\/p>\n<p style=\"text-align: justify\">Insertion sort is based on decrease and conquer design approach. Its essential approach is to take an array A[0..n-1] and reduces its instance by a factor of 1, Then the instance A[0..n-1] is reduced to A[0..n-2]. This process is repeated till the problem is reduced to a small problem enough to get solved.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The first element is initially considered to be a sorted element; therefore, the second element needs to be compared with one element, requiring only one comparison. The third element needs to be compared with the previous two elements. Thus, the logic of insertion sort is to take an element and copy it to a temporary location. Then the position is looked after for insertion. Once, a position is located, then the array is moved right and the element is inserted. This process is repeated till the entire array is sorted.<\/p>\n<p class=\"hanging-indent\">Informally the procedure is as follows:<\/p>\n<ul>\n<li>Finding the element\u2019s proper place<\/li>\n<li>Making room for the inserted element (by shifting over other elements)<\/li>\n<li>Inserting the element<\/li>\n<\/ul>\n<p><strong>Formal Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The formal insertion sort algorithm [2,3] is given below:<\/p>\n<p>&nbsp;<\/p>\n<p>ALGORITHM InsertionSort(A[0..N-1])<\/p>\n<p>&nbsp;<\/p>\n<p>for i = 1 to N-1 do<\/p>\n<p>&nbsp;<\/p>\n<p>temp = A[i]<\/p>\n<p>&nbsp;<\/p>\n<p>j = i-1<\/p>\n<p>&nbsp;<\/p>\n<p>while j \u2265 0 and A[j] &gt; temp do<\/p>\n<p>&nbsp;<\/p>\n<p>A[j+1] &lt; A[j]<\/p>\n<p>&nbsp;<\/p>\n<p>j = j-1<\/p>\n<p>&nbsp;<\/p>\n<p>A[j+1] = temp<\/p>\n<p>&nbsp;<\/p>\n<p>This procedure is illustrated in the following numerical example.<\/p>\n<p>&nbsp;<\/p>\n<p>Example 1: Apply quicksort to the following set of numbers and show the intermediate result.<\/p>\n<p>Solution:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As discussed earlier, the first number is considered as a sorted number. Then one by one elements are inserted into its appropriate position, and the length of the sorted list is increased. This process is continued till all the elements are sorted.<\/p>\n<ul>\n<li>88 | 43 68 92 23 34 11<\/li>\n<li>43 88 | 68 92 23 34 11<\/li>\n<li>43 68 88 | 92 23 34 11<\/li>\n<li>43 68 88 92 | 23 34 11<\/li>\n<li>23 43 68 88 92 | 34 11<\/li>\n<li>23 34 43 68 88 92 | 11<\/li>\n<\/ul>\n<p>The final sorted list is : 11 23 34 43 68 88 92<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">The basic operation of this algorithm is a comparison operation. The number of comparisons\u00a0depends on the nature of inputs. As said earlier, The first element is initially\u00a0 considered to be a\u00a0\u00a0sorted element; therefore, the second element needs to be compared with one element, requiring\u00a0\u00a0only one comparison. The third element needs to be compared with the previous two elements.\u00a0Worst case analysis: The worst-case complexity analysis of insertion sort can be determined as<\/p>\n<p>&nbsp;<\/p>\n<p>follows: Hence, this requires two comparisons. Thus, in general, for <em>n<\/em> elements, the number of<\/p>\n<p>&nbsp;<\/p>\n<p>comparisons would be as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-238\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic1-1.png\" alt=\"\" width=\"163\" height=\"127\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic1-1.png 163w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic1-1-65x51.png 65w\" sizes=\"auto, (max-width: 163px) 100vw, 163px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Best-case complexity analysis The best-case complexity of insertion sort occurs when the list is in a sorted order. Even in this case one comparison is required, to compare an item with its previous element. Thus, at least <em>n<\/em> \u2212 1 comparisons are required. Therefore, the complexity analysis of insertion sort in best case would be<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-239\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic2.png\" alt=\"\" width=\"132\" height=\"60\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic2.png 132w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic2-65x30.png 65w\" sizes=\"auto, (max-width: 132px) 100vw, 132px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Therefore, the complexity of the algorithm is <em>O<\/em>(<em>n<\/em>). In addition, no shifting of data is required and space requirement for the sort is <em>n<\/em>. Similarly, the average case complexity of insertion sort is\u00a0 \u00a0O (<em>n<\/em>2 )<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Topological Sort<\/strong><\/p>\n<p style=\"text-align: justify\">Topological sort is one of the most important sorting used in variety of applications such as course prerequisites and project management. Thus, the objective of topological sort is to produce an ordering that implies a partial ordering on the elements. Thus, the ordering of the elements satisfies the given constraints. First, given a set of constraints graph is constructed. Every vertex represents an item. Every constraint is represented as an edge. For example, the constraint where item A must finish before B, then a directed edge is created from A to B. If the edge is represented as &lt;A,B&gt;, then the vertex A appears before vertex B in the linear ordering list.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Topological sort is performed for directed acyclic graphs (DAGs), and it aims to arrange the vertices of a given DAG in a linear order. Thus, a DAG is an essential and necessary condition for topological sort. What is a DAG? A DAG has no path that starts and ends at the same vertex. A sample DAG is shown below in Fig. 1.0<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-240\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3.png\" alt=\"\" width=\"344\" height=\"213\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3.png 344w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3-300x186.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic3-225x139.png 225w\" sizes=\"auto, (max-width: 344px) 100vw, 344px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Fig. 1.0: A sample DAG<\/strong><\/p>\n<div>\n<p style=\"text-align: justify\">Recollect that a node of a graph that has no incoming edge is called a source and a vertex that has no outgoing edge is called a sink. A DAG has only one source and one sink. If a graph has many sources, then one can create a super source by creating a node and connecting it to all source nodes.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Topological Sort using DFS<\/strong><\/p>\n<p style=\"text-align: justify\">Topological sorting can be performed using BFS and DFS algorithms. The following is the informal algorithm for performing topological sort using DFS [2,3]:<\/p>\n<ol>\n<li>Perform DFS traversal, noting the order of the vertices that are popped off stack<\/li>\n<li>Reverse order solves topological sorting problem<\/li>\n<\/ol>\n<\/div>\n<div>\n<p>In other words, the finish time F(u) of all the vertices of a graph is obtained. Then a queue Q is created and all the vertices are inserted on to the queue Q based on finish time. Then the contents of the queue is printed as the sorted sequence.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Formal Algorithm<\/strong><\/p>\n<p>The formal algorithm for Topological sort is given as follows:Topological-<\/p>\n<p>&nbsp;<\/p>\n<p>Sort()<\/p>\n<p>&nbsp;<\/p>\n<p>Begin<\/p>\n<p>&nbsp;<\/p>\n<p>Run DFS<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">When a vertex is finished, output it and assign a number<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Vertices are output in reverse topological order<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">End.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be used on the following problem. Consider the following graph shown in Fig 2.<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-241 size-medium\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-300x280.png\" alt=\"\" width=\"300\" height=\"280\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-300x280.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-768x716.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-65x61.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-225x210.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4-350x326.png 350w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic4.png 852w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p style=\"text-align: center\"><strong> Fig 2: Initial Graph <\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Initially A is visited. Then the verted D is visited. Then, vertex E is visited. Then, vertex F is visited. Finally, vertex H is visited. This is numbered as 5. By reversing the DFS traversal, it can be observed that F is numbered as 4, vertex E is 3, vertex D is numbered as 2 and finally vertex A as 1. By reversing this one get the topological order which is given as A D E F H.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Topological ordering using source node removal algorithm<\/strong><\/p>\n<p style=\"text-align: justify\">In source node removal algorithm, one has to identify the source repeatedly and it is removed. Simultaneously, all the edges incident to it are removed. This process is repeated till either no vertex is left or there is no source among remaining vertices left.\u00a0As an example, consider the following graph shown in Fig. 3. This represents the prerequisites of a set of courses that needs to be taken.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-243\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1.png\" alt=\"\" width=\"389\" height=\"193\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1.png 389w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic5-1-350x174.png 350w\" sizes=\"auto, (max-width: 389px) 100vw, 389px\" \/><\/p>\n<p>&nbsp;<\/p>\n<div>\n<p style=\"text-align: center\"><strong>Fig. 3. : Example course graph<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed, the node that has no incoming edges is C1. Therefore, it is removed along with its incident edges. Then, C3 is the vertex that is source. Then, it is removed. Then C4 is the vertex , that is source and hence removed. Finally, the node c5 is selected. Therefore, the sorting order is given as follows: C1, C3, C4 and C5.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p style=\"text-align: justify\">Let there be <em>m<\/em> vertices and <em>n<\/em> edges of a graph. Then the topological algorithm takes <em>O<\/em>(<em>m<\/em>) time for picking the vertex that has no incoming edges. This is done by examining the corresponding adjacency matrix or adjacency list. Picking the vertex after identification takes a constant time. Deleting the vertex along with its edges takes <em>O<\/em>(<em>n<\/em>) time. Putting together, the algorithm takes <em>O<\/em>(<em>m <\/em>+<em> n<\/em>) time.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Permutations<\/strong><\/p>\n<p style=\"text-align: justify\">Permutation is an arrangement of objects in a linear order. A permutation of a set of objects is a particular ordering of those objects For example, for three objects A, B and C, the first element\u00a0\u00a0A can be arranged in three ways, the second object B in two ways, and the third object C in one way. Thus, the three objects can be arranged in 3! Ways. Therefore, the permutations are {ABC, ACB, BAC, BCA, CAB, CBA}. Each arrangement is called a <em>permutation<\/em>. In general, there are <em>n<\/em>! ways of arranging a set of<em> n <\/em>elements.<\/p>\n<\/div>\n<div>\n<p style=\"text-align: justify\">Generating a permutation may seem to be a trivial task. However, in reality, it is not so. For example, if there are 100 elements, then there are 100! ways of arranging the elements. Therefore, there is a need for generating permutations in an effective manner.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Decrease and Conquer Approach:<\/strong><\/p>\n<p style=\"text-align: justify\">Decrease-and-conquer paradigm is used for permutation generation. In order to generate <em>n<\/em>!\u00a0permutations using the decrease-and-conquer paradigm. For example, consider the problem of\u00a0generating permutations for the set {A,B,C}.<\/p>\n<p>&nbsp;<\/p>\n<p>The solution using the decrease-and-conquer paradigm can be given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The problem of permutation of three elements <em>P<\/em> is reduced to the subproblem(<em>P<\/em>\u00a2) of generating permutation of two elements {A,B}. Then, this problem is reduced to the problem of generating permutation of subproblem {A}.The permutation of {A} is {A}. Then, the element {B} is introduced to enlarge the solution. Then the element {A} is added to get the final answer.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Informal Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>To find all permutations of n objects:<\/p>\n<p>&nbsp;<\/p>\n<p>Find all permutations of n-1 of those objects<\/p>\n<\/div>\n<p>Insert the remaining object into all possible positions of each permutation of n-1 objects<\/p>\n<p>&nbsp;<\/p>\n<p>This can be illustrated as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>This process is described as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>Given the empty set { }, the only possible permutation is { }<\/p>\n<p>&nbsp;<\/p>\n<p>Given the set {A}, the only possible permutation is {A}<\/p>\n<p>&nbsp;<\/p>\n<p>Given the set {A, B}, the possible permutations are<\/p>\n<p>&nbsp;<\/p>\n<p>{AB, BA}<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-244 alignleft\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6.png\" alt=\"\" width=\"684\" height=\"456\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6.png 684w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6-300x200.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6-225x150.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic6-350x233.png 350w\" sizes=\"auto, (max-width: 684px) 100vw, 684px\" \/><\/p>\n<p>&nbsp;<\/p>\n<div>\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 class=\"hanging-indent\"><strong>Johnston\u2013Trotter Algorithm<\/strong><\/p>\n<p style=\"text-align: justify\">Another way of generating permutations is by using the Johnston\u2013Trotter algorithm that uses the decrease-and-conquer strategy. This algorithm generates permutations in a non-lexicographical order. In this algorithm, every integer is associated with a direction. For example, &lt;3 means the integer 3 is assigned a direction left and &gt;3 means it is assigned a direction right. The core idea of this algorithm is that, a integer is called a mobile integer if it points to a neighbouring integer than is lesser than it. For example, in the generation of a permutation like &lt;2 &lt;3 &lt;1, 3 is a mobile integer as it is pointing to an integer that is lesser than it. The right- and left-most columns of a list are called its boundaries. If any mobile integer in a boundary does not point to any integer, then the number is not a mobile number. In the generated sequence &lt;3 &lt;2 &lt;1, 3 is no longer a mobile number as it is in the left-most column (or boundary).<\/p>\n<p>&nbsp;<\/p>\n<p>Informally, the Johnston\u2013Trotter algorithm is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>ALGORITHM Johnson Trotter (n)<\/p>\n<p>&nbsp;<\/p>\n<p>Initialize the first permutation with 1 2 \u2026 n<\/p>\n<p>&nbsp;<\/p>\n<p>while there exists a mobile integer k do<\/p>\n<p>&nbsp;<\/p>\n<p>find k \u2013 the largest mobile integer<\/p>\n<p>&nbsp;<\/p>\n<p>swap k and the adjacent integer pointed by arrow reverse the direction of all integers that are larger than k<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>This algorithm for generating permutations for three elements {1,2,3} is given below in Table 1.:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Table 1. Generating permutations for three elements using the Johnston\u2013Trotter\u00a0<\/strong><strong>algorithm<\/strong><\/p>\n<table>\n<tbody>\n<tr>\n<td>Permutations<\/td>\n<td>Descriptions<\/td>\n<\/tr>\n<tr>\n<td>&lt;1 &lt;2 &lt;3<\/td>\n<td>3 is the mobile integer as it points to \u20182\u2019 that is smaller. Therefore, move the mobile integer.<\/td>\n<\/tr>\n<tr>\n<td>&lt;1 &lt;3 &lt;2<\/td>\n<td>Now the mobile integer is pointing to \u20181\u2019, which is smaller. Therefore, move it<\/td>\n<\/tr>\n<tr>\n<td>&lt;3 &lt;1 &lt;2<\/td>\n<td>The mobile integer 3 has reached the boundary and does not point to any element. Therefore, look for the next largest integer, which in this case is \u20182\u2019. Move it to get the next permutation and also change the direction of the integers that are larger than the current mobile integer.<\/td>\n<\/tr>\n<tr>\n<td>3&gt; &lt;2 &lt;1<\/td>\n<td>It can be observed that the direction of 3 is changed. In other words, 3 has become a mobile integer again. Now move it again.<\/td>\n<\/tr>\n<tr>\n<td>&lt;2 3&gt; &lt;1<\/td>\n<td>Now the mobile integer 3 points to a smaller number \u20181\u2019. Therefore, move it again.<\/td>\n<\/tr>\n<tr>\n<td>&lt;2 &lt;1 3&gt;<\/td>\n<td>The numbers 2 and 3 have reached the boundaries and do not point to any integers that are lesser than these. As there are no mobile integers, exit.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong><span style=\"text-align: initial;font-size: 1em\">Generating Subsets<\/span><\/strong><\/p>\n<div>\n<p>The following are the important terminologies related to this problem:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Set : A collection of distinct elements. For example = colour = { red, Blue, Green}<\/p>\n<p class=\"hanging-indent\">Subset : A set B is a subset of A , if its all elements are in A. For example, A = {1,2}, then the subsets of A are { }. {1}, {2}, {1,2}<\/p>\n<p class=\"hanging-indent\">Power set: The set of all subsets is called power set<\/p>\n<p class=\"hanging-indent\"><strong>Generating Subsets Using Decrease-and-conquer Strategy<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To generate subsets <em>A<\/em> = {<em>a<\/em>1, <em>a<\/em>2, <em>a<\/em>3, \u2026, <em>a<\/em><em>n<\/em>,}, one has to divide this into two groups: <em>S<\/em>1 = {<em>a<\/em>1, <em>a<\/em>2, <em>a<\/em>3, \u2026,<em> a<\/em><em>n<\/em>\u22121} and<em> S<\/em>2 = {<em>a<\/em><em>n<\/em>}. Add<em> a<\/em><em>n<\/em> to each subset of<em> S<\/em>1 to get the final solution. Example:<\/p>\n<p>{1,2}<\/p>\n<p>&nbsp;<\/p>\n<p>reduce this problem to<\/p>\n<p>&nbsp;<\/p>\n<p>{1}<\/p>\n<p>&nbsp;<\/p>\n<p>reduce this problem to<\/p>\n<p>&nbsp;<\/p>\n<p>{}<\/p>\n<p>&nbsp;<\/p>\n<p>So the solution is<\/p>\n<p>&nbsp;<\/p>\n<p>{}<\/p>\n<p>&nbsp;<\/p>\n<p>{1} {} after {1} is inserted<\/p>\n<p>&nbsp;<\/p>\n<p>{1, 2} {2} {1} {}<\/p>\n<\/div>\n<p style=\"text-align: justify\">Another easy approach to generate subsets is to use a binary string for <em>n<\/em> digits. The idea is to have a 1:1 correspondence between a binary string and the generation of subsets. Informal algorithm based on [1] is given as follows:<\/p>\n<ol>\n<li>Initialize the counter i to 2<em>n<\/em> \u22121<\/li>\n<li>Initialize the item counter j = number of items<\/li>\n<li>Extract the jth bit from the counter. If binary digit is 1, then include the item , otherwise, exclude it<\/li>\n<li>Print the subsets.<\/li>\n<\/ol>\n<p>The following Table 2 summarizes the generation of the subsets.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong> Table 2: Generation of Subsets<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-245\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7.png\" alt=\"\" width=\"752\" height=\"441\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7.png 752w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7-300x176.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7-65x38.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7-225x132.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic7-350x205.png 350w\" sizes=\"auto, (max-width: 752px) 100vw, 752px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\"><strong>Table 1: Generation of Subsets <\/strong>Informally, the algorithm for generation of subsets [1,2] is given as follows:<\/p>\n<p style=\"text-align: justify\"><strong>Step 1<\/strong>: For <em>n <\/em>elements represent sets with an <em>n<\/em>-bit string.<\/p>\n<p style=\"text-align: justify\"><strong>Step 2<\/strong>: For each bit of the <em>n<\/em>-bit string, perform the following operation:<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\"><span style=\"text-align: initial;text-indent: 1em;font-size: 1em\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-246\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic8.png\" alt=\"\" width=\"198\" height=\"57\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic8.png 198w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M14Pic8-65x19.png 65w\" sizes=\"auto, (max-width: 198px) 100vw, 198px\" \/>Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the<\/span><span style=\"text-align: initial;text-indent: 1em;font-size: 1em\"><br \/>\n<strong>Step 3:\u00a0<\/strong><\/span>Print the resulting subsets 0 \u2192 2<em>n<\/em>\u22121, which represents the power set of <em>n <\/em>elements. Thus, the algorithm for generating subsets becomes a sort of a counting algorithm. Informally, the counting can be said as follows:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity Analysis<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The complexity analysis is O(n 2<em>n<\/em> ).<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Summary<\/strong><\/p>\n<p style=\"text-align: justify\">In short, one can conclude as part of this module 14 that<\/p>\n<ul>\n<li style=\"text-align: justify\">Decrease and conquer guarantee solution and effective.<\/li>\n<li style=\"text-align: justify\">Insertion sort and Topological sort are important problems and can be solved by decrease and conquer strategy.<\/li>\n<li style=\"text-align: justify\">Generating Permutations and subsets are important problems that can be solved effectively using decrease and conquer strategy.<\/li>\n<\/ul>\n<p><strong>References:<\/strong><\/p>\n<ol>\n<li style=\"text-align: justify\"><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\n<li style=\"text-align: justify\"><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n<li style=\"text-align: justify\">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":6,"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-77","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\/77","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":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/77\/revisions"}],"predecessor-version":[{"id":248,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/77\/revisions\/248"}],"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\/77\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=77"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=77"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=77"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=77"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}