Disjoint Sets - Disjoint Set Operations, Union and Find Algorithms, Priority Queue - Heaps, Heapsort. Backtracking - General Method, Applications, n-queen's Problem, Sum of Subsets Problem, Graph Coloring, Hamiltonian Cycles. LEARNING GBJECTIVES Representation of Sets using Trees Various Disjoint Set Operations Union and Find Algorithms Overview of Heaps ond Heapzort Concepts of Backtracking NASER ON SON Applications of Backtracking such as n-Queen's Problem, Sum of Subset Problem and Graph Coloring Problem. Y¥ “Usage of Hamiltonian Cycles. INTRODUCTION A disjoint set iso data structure containing non-overlapping set. I two sets A and B exist and the intersection of A and B is the empty set, then A and B are called disjoint sets. In other, isjoin(A, B) = True iff A 7B ={4}. An immediate benefit of the disjoint set of data structures is its abllity to perform very quick find and union operations. sactracrig's a method of determining the correct sluon fo any computations problem by examining all the available paths. In this method, if « particular path leads te en unsuccessful solution, then its previous path is ex; to that problem. The applications of backtracking are m Problem, Graph Coloring problem. Among these, Queen's problem is the most common puzzle ‘on which backtracking is used. The backtracking technique is similar too der tree technique used for directed graph: Since, backtracking algorithm is an exhaustive search therefcire it considers all feasible solutions and produces the optimal solution. amined in order to find the correct solution Queen's problem, Sum of Subset, pth first search iy I IABIE face LEGAL proceedings) (Ceres iereattiicepron ot pad hawks @ CRIMINAL octI On s’~tCOC)QOOl ; ja 2.4 DISJOINT. 2.1.1 Disjoint Set Oper Q1. How to implement disjoint sets? Explain. Answer : joint Set : ‘ 7 A disjoint setisa data structure containing non-overlapping ses ftwosetsA and Bexistand the inere, of A and B is the empty set, then A and B are called disjoint sets. nother words dig (A, B) = True iff A B= (0h) : very quick find ‘An immediate benefit of the disjoint set data structures is its ability to perform very q) 4 nie operations, Example Consider two sets, A= (3, 4,5) and B= (6,9). Since, A.B = { }, therefore A and B are said to be disjoint sets. Representation of Sets using ‘Trees Suppose, a set $= (5, 6,7, 8, 9, 10, 11, 12, 13} which is divided into 3 subsets say J, K, L. Where, J=15, 6,7}, K= {8,9, 10}, L= (11, 12, 13) Then, = {5,6,7) can be represented as, K= (8, 9, 10} can be represented as, © © L= (11, 12, 13) can be represented as,Beet Lnit2 : Disjoint Sets and Backtracking “The root nodes 5, 8, 11 have a parent ‘The K" element shows the tree node which has element K. It also identifies the parent pointer of the fespective tree node. Find and union operations can be performed on disjoint sets. Disjoint Sets If two sets A and B exist and the intersection of A and B is the empty set, then A and B are called disjoint sets. In other words disjoint (A, B) = True iff A.A B =(¢) ‘An immediate benefit of the disjoint set data structures is its ability to perform very quick find and union operations. Disjoint Set ADT ‘The disjoint set ADT is a data structure that éan store information about a group of sets. It supports the following operations, (® _ make(i): This operation is used to construct the set(i). (i) find(i): This operation is used to find the ‘name’ of the set to which it belongs. The name returned. is the item ‘?” which is at the root of the tree (the sets are stored as trees). unionG, j): This operation takes the name (root nodes) of two sets and combines them into one. ii) Example After ‘make(1) make(2) make(3) make(4) make(5) ie (1), (2), (3), (4), (5) Each element is- marked so, the value of find(i) isi, for all i. After union(1, 4) union(3, 5) Then, {1,4}, (2), (3,5). Notice that,.find can be used to check whether, elements i and j belong to the same set. For ‘example, find(1) = = find¢4) is true; but find(2) = = find(3) is false (The value of find(2) is 2, and the value 0f find(3) is either 3 or 5 whichever is marked). After union(4,2) + * ‘i gaan Warning :Xerox/Photocopying of this book lt 49 Then, (1,2,4), (3,5). and after union(1, 5) Then, (1,2)3,4,5). + ‘To implement the disjoint set abstract datatype, a set can be represented as a tree with the marked element - as the root. The elements in a set are not arranged in any special way, and the tree is not necessarily a binary tree. @ Algorithm of make Input parameter: i Output parameter: None make(i) { parent] = i; } Algorithm of find Input parameter: i Output parameter: None find(i) { i) while(i ! = parent{i}) i = parentli]; return is, } Algorithm of w Input parameter Output parameter: None union(i, j) { Gil) parent[find(i)} = find@); ) Q2, Explain the usefulness of the following fundamental operations on sets. «MIN (ii) DELETE (i) FIND (iv) UNION (v) INTERSECT (vi) INSERT. Answer : @ MIN: Min operation is used to determine the number of elements in the set that contains the minimum number of elements. Example ). If P= (1, 2.3, 4,5) and disjoint sets then min{P, Q) ‘elements and Q has 2 elements. DELETE: Delete operation is used to delete the given element from the respective set. This is done by finding the set to which the element belongs to. (4, 5) are two, 2, since P has 5 w@ saNiNNAL ac Aryans fond glty WLIABLE wo fe LEGAL proceeings)50 = (4, 5,6, 7) and Q = (10, 11, 12) are two disjoint sets then to delete the element 6, first find the set that contains the element 6. find(6) = P Now, delete the element 6 from set P i.e. delete(6) ©. The resulting set P = (4, 5.7), (ii) FIND: Find operation i.c., find(i) is used to find the set to which the given element ‘i’ belongs to. Example If P= (1, 2, 3)’and Q = (4, 5) are two disjoint sets then, find(4) = @ (iv) UNION: Union operation is used to combine all the elements of two given sets. It is represented by ‘U’ operation. Example . If P=(1,2,3) and Q= (4,5, 6) are two disjoint sets then, - PUuQ=(1,2,3,4,5,6) (%) INTERSECT: Intersect. operation is used to determine the commin elements of the two given sets. It is represented by ‘n’ operation. Examples 1. FP ={3, 4,5, 6) and Q= (4, 6,7, 8) then the intersection of P and Qie., * PnQ=(4,6) But if the sets P and Q are two disjoint sets with unique elements then the intersection of P and Q results in an empty set. 2 IP =(3,4/5) andQ= (6,7) ° then PAO =44) (vi) INSERT: INSERT operation is ,used for inserting a new element in.the list. But before inserting a seach is carried out in, the tree | whether the’ element is already present in the list. If search is successful then that element is ignored and if the search result is unsuccessful then new element is inserted in the list. Example F If the element 80 has to inserted in the list then first search is performed to check whether it is “already present or not, If it is valready present then that element is ignored and if it is not Present then jt is inserted in the list. Before Insertion , 20 [30 [40] 10 a “DESIGN AND ANALYSIS OF. ALGORITHM After Insertion 30 | 40 [80 20 10 G3. Two sets 1 and S2 are given as belay 81 = {1, 2,4, 6} and S2={7, 8} (a) Draw disjoint sots $1 and $2 using trees Draw disjoint sets S3 using treo, such that $3 = S1U S2 Draw disjoint sets S4 using trees such that S4 = S281 Give pointer representation of $1 ‘$2, $3 and S4. (b) (c) (a) Answer : @ ‘Two sets $1 and S2 are given below, $1 = (1,2, 4, 6) and $2 = (7, 8). Set S1 can be represented as, De Figure: $1 Set S2 can be represented as, ® Figure: S2 1,2,4,6) and S2 = {7,8} S1US2 : 6,7,8} si s3 + $3 = (1,2, : Figui S1US2 ¢ SIA PUBLISHERS AND DISTRIBUTORS PVT. LTD. A)‘Unit:2 : Disjoint Sets and Backtracking ( S4=S2uSl S4 = (7,8,1,2,4,6,) 2 © dO Figure: $4=S2U S1 (a) Pointer presentation of SI, 82,83, 54 ‘pea «| 4 () Ow ® \f © i dHo.0 © Tele] Q O. (seses Ko) S1 Write an algorithm of weighted union and also compute tho time comploxity of the same. (Refer Only Topic: Weighting Rule for UNION(,J)) Fob.ttarch-22(R18), Q3(b) (oR) Write and oxplain find algorithm with collapsing rule. (Refer Only Topic: Collapsing Rule) ‘Aug-22(R16), C3) (OR) What are union and find operations? Explain with suitable examples. (Refer Only Topics: UNION Operation, FIND Operation.) ‘Aug.-22(R18), Q4(a) Answer : UNION Operation UNION(i, j) means the elements of set i and elements of set j are combined. If UNION operation should be represented in the form of a tree. Then UNIONG, j), ‘is the parent, jis the child is represented as, UMont.9 (i vuviove.) @) © Example ‘The algorithm of UNION is as follows, Procedure Uti j) Replace the disjoint sets with \ roots i and j,i, Moy thei union integer i, jt PARENT()<-i; . end U Now, consider some examples for above algorithm, Initially PARENT array contains zeros. Figure: Pointer Representation of St, $2, $3, $4 P Q4. plain about the union and find 0 o[o][o]o algorithms in detail. 1[2]3)41516 ‘Apeilt0(R19), 4a) | Example ; NS) (oR) UNION( (Cg pg rn RU GRINAL oor ult RLIABLE to face LEGAL proceedings.)ALGORITI DESIGN AND ANALYSIS OF ‘HM 52 P PaRENT@)-1 [oToT 1 [ofofo 1 3 5 6 Example UNION(2, 5) P parentisy-2 [oTo Ti To 2 123456 Example ION(1, 2) UNION(, 2) p a PaRENT@y-1 [oT Ti To[3To] an) | ® | ‘Time Complexity : ‘The time taken to perform UNION operation is Constant therefore alln ~ 1 unions can be processed in time 1m), FIND Operation 2 FIND(), implies that it finds the Toot node of * node, in other. ‘words, it returns the name of set i, Example UNION(1, 3) ie UNION(1, 3) FIND(1) = 1 FIND(S) = 1 since its patentis Iie, Toot node is 1) i Algorithm ‘The algorithm. of FIND is Biven below, Procedure Fi) é {ind the 1008 forthe tee containing elements integeri,j; * : ici ny while PARENT() > 0. do JCPARENT§); tepeat ; returng); . end F : now explore this algortim with previous example “Example 12) Ary reprerentation j P © @ bhorpy aft L234 5Disjoint Sets and Backtracking “Unit While (PG) > 0) do condition true, j=2 So, jP(2) ie. while(P(1) > 0) do condition false return(j), $0 1 is root node of node 5. Tt can be observed same thing from above figure. Time Complexity Each FIND operation requires following a chain of PARENT links from node 1 to the root.node. The time required to perform a FIND operation for an element at level {of a tree is O(i). Therefore, the total time needed to process the 1 ~ 2 finds is O(n’). ‘Weighting Rule for UNIONG, j) If the number of nodes in tree / is less than the number of nodes in tree j, then make j as the parent node of ielse make i as the parent node of j. Note Both the arguments of UNION must be roots. ‘A more sophisticated UNION algorithm using weighting rule. Procedure UNIONG, j) {Onion sets with roots i and j, i #j, using the Weighting rule WPARENT(i) = -COUNT() and PARENT(j) = -COUNT@G) integer i,j. x3 x © PARENT() + PARENT() if PARENT(i) > PARENT() ; then PARENT(i)<—j Wi has fewer nodes PARENT(j)-x; : else PARENT(j)<-i; Hy has fewer nodes PARENT()<-x ; end if 5 : end UNION . “ The above rule explained with an example. there are n sets, UNION(1, 2),'the number of = | orwecanuse @@O--O | nodes in tree 1 equal to number of nodes in ree 2 UNION(I, 2)= umber of nodes in wee 381. $0, 2> I make 2 as parent anda ND ANALYSIS OF ALGoR DESIGN AI THM, 54 Pic ic bby “Untonceinng).4) UMNO CEIND 8 Initially, the depth of every clement involve rule for union (i) involves the They cam be done n number of times Ns mbroves the performance of union The worst Performed on n, Union operation will be less than fog (n +1). Bit Weighing PL where the depth of every element increases, twice as before, Therefore, {he tree contains n number of elements and the find becomes Oftogp) ij). . "Case time complenity for Wenion is O(1). However, when Tements, the time complexity will be O¢mtogn), Collapsing Rule there are m>=n operations tg be {fi is @ mode on the path from ito Fenn teh Se PARENTG)< oot, P.more sophisticated algorithm OF FIND using collapsing rule is given below. Nile PARENT()>0 do ing Foot JPARENT(); Tepeat kei: Implement followi UNION, 2), UNION;Disjoint Sets and Backtracking @ Gg) G) UNION(1, 5) @O@ @ % -@ ® B® wnons.n Figure: AWorst CaseTree using the Weighting Rule Next, 8 is applied in FIND operations for above tree as follows. FIND(8) FIND(8) FIND(8) FIND(8) FIND(8) FIND(8) FIND(8) _ FIND(@®) FIND(8) = Root node ic., 1. By using first FIND algorithm, it will require 3 moves upward to reach the root node. Similarly, for 8 FIND operations it will require 8 x 3 = 24 moves. If FIND algorithm uses collapsing rule, then first FIND(8) requires going up 3 link fields (moves) and then resetting 3 links. Each of remaining 7 finds requires going up only 1 move (link field), the total cost is now only 13 moves. Q5. Suppose we start with n sets, each containing a distinct element. (a) Show that if u unions are performed, then no set contains more than u+1 elements. i (b) Show that at most n— 1 unions can be performed before the number of sets becomes 1. (6) Show that. jf fewer than (n/2) unions are performed, then at least one set with a ‘single element in it remains. Answer: ‘ugiSep-21(R10), 04 (®) If w Unions are Performed, then no Set Contains more than u = 1Elements Consider four séts A, B, C, D with distinct nts, : © Given that each set contains a distinct element. 5 iy LIABLE ei _aroupnconcspifig iv BOOK sw CRIMINAL SEEIADORN TEU lity 1 LA 55 ‘Then, MAU B) = nA) +B) = nA 0B) =14120 [-AnB=01 First union (= 1) between two sets i.c., (AUB) contains «+ 1 elements ice., 2. Consider the second union between two sets i.e, AUB nA UB)UC) NIA UB) + nlC) = nA UBC) +1-0 :. Second union (u = 2) between two sets i.c., (AUB) UC contains w+ 1 elements ‘Therefore, it can be said that if 'w’ unions are performed then no set contains more than u +1 elements. (b) © At most n—1 Unions can be Performed Before the Number of Sets Becomes 1 Consider three sets “A,B,C “ic. m=3 with distinct elements. A=(12} B= (3,4) 5,6) ‘The union between A and B results as, AUB= (12) U (3.4) = {123.4} Now, the remaining set are (A UB) U C. ‘The second union between (A U B) and C results UBUC = (1234) U {56} = (1.2:3,4,5,6) Inabove example, there are’3' sets, where atmost 2(n ~'1) unions aré performed to result a single set. ‘Therefore, itcan be said that atmost (n ~ 1) unions = ‘can be performed before the number of sets becomes 1. (© If Fewer than n/2 Unions are Performed, then at Least One Set with a Single Elenient in it Remains Given that, ‘There are 'n'sets with distinct elements. ‘Case 1: If 'n’ is odd na2k+1 : ‘The maximum number of unions performed ust be lesser than 1/2 i.e. Maximum number of unions < 1 ie REY “| Maximum number of unions that can be performed is k. tw face LEGAL proceedinBut each union can combine maximum 2 sets ingle clement. So, Maximum numberof single element sets can be ined are 2 x, k=dk ‘Therefore, im contains odd numberof sets, then ‘he single clement sets will be, = n-2k Chem Ey 1 =2k+1) Case 2: f'n is even The maximum nu f mantel imber of unions performed union can combine m, So, maximum m iaximum 2 sets f Single ~Dsx-2 Tumber of sets then the single is call + A’ graph that is jt only one connected component, ‘The number of connected componer “Undirected raph can be determined by the, erations like: Make-Set( ). Union() and Which is shown in the following procedure, CONNECTED-COMPONENTS(G) foreach vertex v © V{G] do Make.Set(y) for each edge (u,v) & EG] 1 2. 3 4 doit Find Seicyy + Find-Set(v) 5. DESIGN AND ANALYSIS OF AL Gop SAME-COMPONENT(: 1. if Find-Set(u) = Find-Set(y) 2. — then return true 3. else return false. The procedure CONNECTED-COMPO} a, works as follows, Line 1-2 inthe above code, paces each inits own set. Then, for each edge (u, v) in the edge the for loop of lines 3-5 units the sets Contzining V-using union( ) operation, Aer processing of each edge in the edge it is said that two vertices are in the Same component if and only if their associated objects are; the same set, then Union(u, yy,unit pigjoint Sets and Backiracking ‘Now consider two subsequent trees from above n/2 trees and apply UNION as shown in the figui AAA Figure (3):'n/4 Trees each with 4 Nodes and Height 2 Now, consider two subsequent trees from about n/4 trees and apply UNION as shown in the figure (4). UNION G5) UNION @, 13) ks t BUNION... penton 3. ONION (1,3) UNION (5,7) : UNION @, 11) es i oS ns UNION i erations UNION (a= 3,n= 1) UNION (a~7,~3) ™ 2 OOQ ®%® ® O® @O® Figure (4): n/8 Trees each with 8 Nodes and Height 3 5. Repeat the same procedure for the above 1/8 trees. This results in n/16 trees with height 4. Continue this Procedure till only one tree is obtained having ‘n’ nodes. A single tree is obtained after log n steps of height log n. This is because at each step, the size of the tree is doubled and the number of trees are reduced by half. ‘The number of UNION opefation are, = nt n/2 + n/4+n/8+n/16+- = Oca) operation. : > nig, NOW: Perform FIND on remaining (m—n) operations. In worst case, each FIND operation takes atleast log © Q(log n) time. a “The total minimum cost of MAKESET, FIND and UNION is, = MAKESET + FIND + UNION ny + Qn) + (Cm — mlogn) = Ocny +.2(mlogin) — A(nlogn) A(mlogn) Cc m>n) XerevPnococopring of this book Iv CRIMINAL se “payors ound gully & LIABLE to face LEGAL proceedings,What is weighting rule for union (I, })? How it improves the performance of union operation? Answer ; For answer refer Unit-Il, Q4, Topic: Weighting Rule for UNION (i, j). Initially, the depth of every element involved in union operation will be less than log (n +1). But Neighting rule for union (jj) involves the concept Where the depth of every element increases twice as before. Therefore. union can be done n number of times &S the tree contains 1 number of elements and the find becomes O(log 1}. This improves the performance of union Gi.) May-45(R13), Q4(0) Heap 2.4.2 Priority Queue-Heaps, Sort A Q8. What is priority queue? Explain the implementation of priority queue? Write 2n algorithm for operations of. priority. queues. Answer: Priority Queue Priority queue can be defined as a queue that ce oct OF elements depending on priority. In Priority queue, every element contains unique Priority and based on that priority, various operations aro being: performed on priority queue, Implementing Priority Queue Using Heap A heap is a special kind of tree that has an efficient implementation of a priority queue. It has two Properties that are not generally true for other trees, They are, + 1 Completeness: The tree is complete, which means that nodes are added from top to bottom, left to right, without leaving any spaces, 2. Heapness: The item in the tree with the highest Priority is at the top of the tree and the same is true for every structure: ‘as heap is a perfectly balanéed tree, It reguires only O(log n) searches to reach a leaf node, which is very efficient. Thus, heaps are generally used to implement ‘priority queues’. The two operations that ‘te carried out on priority queues are, : (@ Enquewing ~ To insert a new element in the Priority queue, . ‘As 16 is still greater than its @) Dequewing To delete an element from the _, Aisi in pl oe Priority queue, ae DESIGN AND ANALYSIS OF. ALGor @ — Enqueuing Algorithm heapEnQ(e) place e at the end of heap; while ¢ is not in root and e > parent(e) swap e with its parent; In enquewing, the element tobe inserted is ag atthe end of the heap. IF the insertion of new clemen destroys the heap property then this property is res by moving the element up from the bottom of the heap to the top in search’of an appropriate place for it, Example: Consider the following heap. Suppose, number 16 is to be inserted in the Biven heap, using heapEnQ0 algorithm as follows, Step 1: At first, element to be inserted, i.e., 16 will be Placed at the end ofthis heap, O35 RKI + 1Omtwatee~35 md CLs s mlehloroform, Tira again 005 M1 KIO,, uni is of purple colour occurs from elon appearance foam layer i thas greater value than its parent is greater than its parent 7, they are PATENE 12, they 4 STA PUBLISHERS AND DISTRIBUTORS PVT. LTD.= pisjoint Sets and Backtracking ® fs) ©) 2) © SG OOO a heap as it satisfies the ‘The tree thus obtaine heap property @ Dequeving Algorithm eapDeQd, Extract the root element; Select the element in the last leaf of the heap and place it in the root: Delete last leaf: 17a make both subtrees of the roots as heaps theRoot; while n = leaf and n < any of its children swap n-with its larger child; In dequeuing, the root element is removed by replacing it with the element in the last leaf. If the deletion of the root destroys the heap opery then, this property is restored by moving the lement down from the top of the heap to the bottom in seuch ofan appropriate place for it. Example: Consider the following heap. @ @ ©) Sy Q © © O80 iga,, The largest element in the heap is dequeued ge the heapDeQ() algorithm as follows. At first, the root element is removed as itis the “tes clement inthe heap. = 59 ‘The new tree obtained from step 3 does not satisfy the heap property and is thus not a heap. Step4: The heap property is restored by swapping the element 7 with 16, as it is the largest element between its children. (o) GY (a oa) =) Oo O® ‘The element 7 is swapped again with 12, as itis the largest element between its children. © @ (2 QMO. } OS O® The tree thus obtained is a heap, as it satisfies the heap property. Q10. Explain the procoss of heap sort. Answer: ‘Heap Sort ; Heap sort is also known ‘as selection sort sigorithm. A selection sort algorithm is an internal sorting technique. It sorts the list by selecting the Targest element in the unsorted list and places it atthe appropriate position (ie swapping).60 In each pas » the Targest eletnent in the list is Placed at appropriate position. If there are n élements in the list, ° In first pass, all the elements are compared and largest element is placed at the last position. % _Insecond pass, first n - 1 elements are compared ‘and process continues for list of ~ 2 elements, then for m — 3 élements and so on until first element, ‘Heap Sorting Techniques 1 Sorting of a giver list using heap sort algorithm requires two phases, ie., construct heap and sort heap. Construct Heap: In this phase, an array based. list is transformed into a heap. Note that a heap is a list wherein each element ‘i’ is stored such that, it is greater than or equal to elements at. location 2i + 1 and 2i + 2. An array based list can be viewed as a binary tree, in which case a binary tree would be called a heap if each node in it is greater than or equal ‘to its left and right children. In order to transform 4 list into heap, follow the steps given below, @ ‘Start at the last non-leaf element of the list. This can be done using the formula, i= (sizeofLis/2) - 1 ‘Where, ‘i’ is the index to such a node/ ‘element which is not leaf and has at least ‘one child. (Gi) Transform the subtree pointed by index ‘f intoaheap. © (iii) Decrement the index ‘i’,to point to other parent node. : Gv) Repeat steps (ii) and (iii) if the value of =o. : To transform a pafticular subtree into a heap, follow the steps given below, @ Suppose that List{J/c] and List{rc] are the Jeft and right children of List{i], Gi) If Listflc] and List{rc] finds the largest of them. The index of largest element is Stored in ‘largest’. Gil) IF List is less than List(largest, sw List] with Listlargest). Otherwise, exit ice. the subtree is already a heap, (i If i (1) Hf yalues have been swapped instep i) heh, there are chances thatthe substree prey act might have become a non- p. Therefore, apply steps (ii) and (iii) at that sub-tree‘until all the-heaps in th substree i 7 P are restored or until an empty subtree is encountered, After constructing a heap, the : the next phase 4.., sorting heap begins. 2. > | ~_ DESIGN AND ANALYSIS OF ALGORITHMg ‘Algorithm (Construct Heap) : Step 1: Consider’a heap tree which is empy Begin at the first step, . while (ic =n) do Step 2: Repeat step 2 for all the elements Step 2.1: Sclect the i"* element from list and ag ‘an element to the ith place in array n= Arti] Arrifi]=n j Step 2.2: Repeat step 2.2 to step 2.3 until the root is checked IArr{j] >Arri[j/2] then tmp =Arri{j] Arrifj] = Arrl [2] Arrl{j/2] = tmp isi else jel End If Step 2.3: End while isiel Step 2.4: End while Step 3: stop Sort Heap: In this phase, the given heap is sorted. Note that the root node of heap (ie, the first clement of the list) will be the largest «element in the tree or list. The following steps sort the heap, (Swap the root node (i.e, first element of array list) with the last node of the tree (ie., last element of array list). Now, last node is in its proper place. Gi) Leave the last element and consider the remaining elements as the new list. ii) The new list may not be in heap form. + Therefore, construct a heap of new list. (iv) Repeat steps (j), (ii) and (ii) until all elements are placed at their proper place i.e, until all elements are sorted. “Algorithm ‘ ‘Step 1: Read all the elements and store in the array, Step 2: ConstructHeap (Arr) ‘Step 3: Repeat this'step for n— 1 times : Step 3.1: Remove the root element and swap it with the i" element. tmp = Arr[i) Arrl{i) = Arrl[1] Arrl[1) = tmp | b SUA PUBLISHERS AND DISTRIBUTORS PVT LTD.; Disjoint Sets and Backtracking ‘Step 3.2: Pre build Step 3.2.1: Cannot build heap with one element in the tree If G=1) then heap, exit Step 3.2.2: Begin at the root node jet flag = TRUE while (flag =TRUE) do left =2*j right = 2%) +1 Step 3.2.3: Cheek whether the right is.in the rangé of heap and check whether left or right will move up or not. If (ight s i) then If (ArrIfj} s Arriflef™) AND Arrlfleft] 2 Arrl [right] then swap (Arrfj], Arrtleft)) jeleft else If (Arr [j] < Arr[right]) swap (Arrl {j), Arr] [right]) j=right Else End If Step 3.2.4: If (lefts i) then If (ArrI{j] < Arrifleft}) then swap (Arrl{j], Arrifleft)) j=left’ else flag = FALSE EndIf Endif EndIf 1 Tex Anyone found guile 61 Q11. Perform heap sort algorithm for (10 15 6 22518162204), Answer: Given elements are, 10, 15, 6, 2, 25, 18, 16, 2, 20,4 Constructing Heap Tree DEBT ep Tele Lel sz Tals rr rr ‘Now, start heapifying the above heap tree by making the large number as a parent node. Start from the bottom of the tree of * position as parent node. Where, Sizeoflist_ Step 1 Now, compare 25 with child node ie., 4. Since, 25 > 4, no swapping is required. Step? Now decrement the i value ie.,7=3. 2isparentnode. As2-<20, swap them. For TABLE to face LEGAL proceedings.DESIGN AND ANALYSIS OF ALGORIny ®) Step3 Now decrement the f value i, i=2 For i= 2, 6s parent node. 6 > 18, s0 swap these nodes Step4 Now decrement the i value ie, sia. For (= 1, 15is parent node. 15 <25, so swap them, @ ; 3int Sets and Backtracking unit 63 “Traverse back and check if 10 is greater th its child nodes or not, As 10 < 20, swap them. Now required heap tree is obtained. ‘Sorting Heap Tree ‘The root node in the heap is largest node in the tree. Swap it with the last node of the tree. a ‘Now heapify the above tree excluding the sorted clement i.e., 25. Then swap 20 with 4 followed by swapping 4and 15, copying of tid book i & CRIMINAL act, Anyone ound guilty is LIABLE to face LEGAL proceedings. )DESIGN AND ANALYSIS OF ALGORITHM, 64 ( ® SIA PUBLISHERS AND DISTRIBUTORS PVT.LTD. sae a]pisjoint Sets and Backtrackihg: | Now swap node 16 with the last nod le i, 2, delete the feaf node 16 and pli 6 and place it in the sorted fist Now, ; swap 10 with 2, delete node 10 and place it in the sorted list. vo [15 Lis [18 [20 [3s Ca tecmenapiti ; copring drthis Hook law CRIMINAL Set: Anyone ound guley Taiko ce LEGAL pecone)a DESIGN AND ANALYSIS OF ALGORITHIg 66 ‘Then heapi ‘Next swap 6 with node 2, delete the leaf node 6 and place it in the sorted list. sw node 2, 1 [20 [3 Delete the leaf node 4 and place it in the sorted list. Ta] 6 [10 15 [16 Tis [30 [25 . ‘Thus, the sorted list obtained is as follows, 2 22 [4 [6 Tio [isis Tis [20_ Jas]. | General, 4 a q Q12. Describe the general method of backtracking, Aug-22(ni8), 98) (OR) hee E | Explain the General Backtracking method in detail, 1 Ariss om i ae - Il ees | (OR) 4 SIA PUBLISHERS AND DISTRIBUTORS PVT: LTD.Qe 2: Disoint Sets and Backtrackitd Explain about backtrack solution, (Refer Only Topic: Example) Feb-23(R18), 05(0) (oR) Describe recursive formulation ‘of backtracking technique. (Refer Only Topic: Control Abstraction for Recursive Backtracking) Fob-23(R18), Qa) (OR) Explain 4-Queen's problem. (Refer Only Topic: Example) Answer Backtracking Backtracking is a method of determining the comet solution to any computational problem by examining all the available paths. In this method, if a particular path Jeads to kn unsuccessful solution, then itsprevious path'is examined in order to find the correct solution to that problem. That is, instead of examining from the start, the’ previous points of the path that led twincorrect solution are traversed one after the another. Backtracking ‘approach helps to return to a postion ina problem from where there is a possibility to chiain the correct solutions to the given problem. There are various problems on which backtracking algorithm isapplicable. Among all, Queen's problem is the most common puzzle on which-backtracking is used. The backtracking technique is similar to a depth first search tte technique used for dirécted graph. According to bicktracking, the solution to the problem is obtained by ‘presenting the given problem as an implicit gfaph and then petforining backtracking as an “intelligent” depth fistsearch on it. In this way, one or all feasible solutions ‘an be obtained. Since, backtracking algorithm is an thaustive search, therefore it considers all feasible ‘lutions and produces the optimal solution. Hage Solutions to the problems on, which ue ‘king is applicable are produced as a vector, x= chang Bs 4), Whee i the vector component Sion pt 88 Si andthe feasible solution has a isgy tn P. Thus, POX) ean be minimized or cont on the method call. | Abstraction of Backtracking bear Com] abstraction or the general scheme for din 2, Biven in two ways, that is in recursive niterative way, Doc.-17(R15), a8(a) (a) (b) 67. Contro} Iterative ‘Abstraction Backtracking: ‘The control abstraction for iterative backtracking method is given below, for Consider that (xy. x3... Xi) 18 @ path from Patent node to a child node in the state space tree. Also consider that (xy, X2y «+ Kiet) 18 a set of all probable values of xis where (x1, Kar + 4) isa path to problem state. Assume that, the presence of bounding function Bigs where Bist (x45. Xyy1) is not true for the path (xy, x2. « « + Xiq1) from parent node to a problem state iff the path cannot be extended to reach the answer node, Hence, the elements of solution veétor x{1 + nl] at elements position i + 1 are the values that are generated by A and satisfy Byes. The following algorithm is a general iterative backtracking schema which makes use of A and Busts 1, Algorithm Backtrack (n) 2.» While (k 0) do 3. IEG IK] ©A (x [1], [2], - xf IJ and By (x [1], ... x {k] == true)) then 4, If ( [1]... +x [k] is a path towards the answer node) then 5. Print the output using write (x [1 : k]) 6. Initialize the set k tok + 1. 7. Else backtrack k by initializing k to k— 1. ‘The above algorithm explains the backtracking process. This algorithm returns the solution in the form of an array x{1 : n}. In this algorithm, A () produces a set of all probable values, which are placed as the initial component x, of the solution vector. Moreover, x; will acquire the values sucti that the bounding function B1 (x,) is true, Here, the elements are generated in a depth first order. In this algorithm, the value of k is incremented continuously and the solution vector is increased until a final solution is obtained or until no values. of x, are left untried. However, the value of k is decremented in some cases. If itis deciemented, then the algorithm should continue generating the probable elements for k position which are left untried. However, if the user requires a single solution, then‘a return statement should be added after the step 7 of the above algorithm, Control Abstraction for. Recursive Backtracking: The control abstraction for recursive backtracking method is given below, ‘A recursive backtracking method performs the post order traversal of a tree. Itis given using the following algorithm, 1... Algorithm RBacktrack (k) 2. For(x({K]EA (Ih... x{k-1)) do “che XaratPhcscapng FV Hook Wa CRIMINAL ct Any found gy LIABLE to face LEGAL procoaangs.)68 3. (By (x [1], x (2), Uk} 0) then 4 HOI. 12}... x 1k] isa path towards J the answer node) then 5. print the output using write (x {1 sk): 6 if(k jons of backtracking, Q14, Explain the applications a oe cking is an algorithm design technique a eects ve he lage nance onbe mal pubis, ® felons a systemal mea fe being sakion 02 problem, The Sprains of ecksing nce, Container-oading problem 1 21 knapsack problem 3 Max-cligue problem 4 ‘Traveling salesperson Problem S. Board permutation 5 S.queens problem % Sum-of subsets, Problem & Hamilton circuit ‘Problem, J continer loading Problem, backtracking method is implemented for developing an QQ") algorithm that Proves to be more beneficial than the Synamic Programming algorithm for Some instances, For OM knapsack prob Provides a the: Possible each ntuple 8 algorithm: Xin lependent-set lution space the Solution led using a ‘POnsible for Of elements raises in the Using the Mutation ined tracking ficiently ch na ing in es th tchacking ot Grea i cision jg Id ofthe Het ng d White St element Ment backtachs "4 for ay Ine qual Re. | DESIGN AND ANALYSIS OF ALGORITy, um of elements in a subset Sum of elements inthe substi oo sina, Backtracking. approach can alo a we rinination ofthe Hamiltonian circuit ie, ig enone during the formation ofthe eyelet backtracking one step before and selecting ge cod vertex could be the optimal solution, Q15. Write an algorithm to estimate gy efficiency of backtracking, Answer : Efficiency of Backtracking Algorithm Efficiency of ba depends on four factors, 1 Time consumed to produce the sol 0k) for child node ke 2. ‘The total number fulfill all the explicit constraints, 3. The time taken by the Pounding function Bp, 4 The number of child nodes CK) that satisty the bounding function BF, for all values of i, Following points are impsrtant Points When "ncy is considered, Except the fourth are independent of solved, Worst case Of backtracking algorithm is givenas OPM") of OCGmy(ntyy if Nodes in the sotution ‘Space are 2" spectively, where ‘P(n) and an) are Polynomials in 7, 7 Backtracking_ 50 amount of time. cktracking algorithm main, lution vecry of child nodes yz) Whey efficies 1. Factor, all the three facto the problem instance being Wes large value of in small the given problem instance. iciency, of Backtracking Algorithm For (termining the efficiency of this algorithm ‘atlo method is used, tice 9 Oasic idea behind Monte Carlo method is to * random path inthe state space tree, Bolte, metho, Slowing SPS are followed in Monte Cato 1, q : sides y 8 a node on the enerated random 2 : 7. St pose 38 at level i of the State space tree. jor tS stage, bounding functions come: into Picture. Boun ing functions are Used to find out Dumber of chil, that do eo eaeetinte ildren of node y the chig 'Child node.that do not get bounded are represented as 7. Next node is selected from the set of n, The set of ms is useful in finding the total umber of nodes n, in the state space space tree that will not get bounded. It can also be used for searching. Answer nodes in the set of all unbounded nodes. ‘When only a single solution is desired, selecting n from the set of unbounded nodes is not suitable. In such situations, backtracking algorithm is assumed and uses a static bounding functional ‘and the same bounding function is used for all ‘nodes on the same level. With this assumption the number of nodes at level (/ + 1) will bem, n. ny. The total n= 1+ my + mp4 my rpms +o. ‘Algorithm for Estimating Efficiency of Backtracking ‘An algorithm for estimating the efficiency of backtracking. is ESTIMATE-EFFICIENCY. This algorithm selects a random path from the root of state space tee and determines the estimated number of unbounded nodes n, that will be generated for solving a problem instances. It usés a furiction SIZEOF( ) that returns the size of the set of values y(k) and a function SELECT( ) that chooses a random element from the ‘sty. Procedure ESTIMATE-EFFICIENCY nel; 10. res; -k@1 — Munitial values are assigned Joop S,€ {y(k) : 0k) € S(y(1), 2» Yl 1) nd BFY(1), --- YO) Write an algorithm of n-queens problem. (OR) Write an algorithm of n-queen’s problems and explain. Answer: n-Queen’s Problem The n-queens problem is the problems ix wise “nt queens are placed on a cheisbourd of size m = i= such a way that, nose of them can capeare any other & means of the standard chess queen's moves. A soistia to this problem requires that, no two queens mast be placed in the same row, or cobuma or deagonal ‘Algorithm of n-queens problem i Algorithms POSITION‘. k) ME 2 queen can be column, HOrherwise it renaras false begin form if (Gim] = or (ABS. UNetifes wheter tao guess xe im same column or in same diazocal return false: endif are. lwx-Ido cn as Ses. Algorithm N_QUEENS SOLUTION (1.2) Ufhis algorithm wses backracking to solve tbe problem (Mt prints all the possible positions of s-quesas in x nichessboard sock thar none of them 1S, is the set of values y(k); BF is the bounding on a function attack i = i begin Oe ee forj=ltomdo an if POSITION(x. ek : [Checks whether 3 queen can be positioned im tes < res * SIZEOF(S): x® row and j® column nen sres; x tes’ ; yk) < SELECT (Sy); Pf}: =i: /A position s found kekst; ifix=™) . : - whether solution is complete or moe mn —_. oP wwrite(P{1 : mf Yes, print the arraye N_QUEENS_SOLUTION (x +1, m); Move to the next row endElse else X: =x ~ 1; //Backtracking takes place endEIse repeat end N_ QUEENS_SOLUTION ‘The n-queens problem is one of the example of queens problem in which 8-queens are placed on an 8X8 chessboard. 8-Queens Problem For answer refer Unit Problems. Therefore. m+ n= that the two queens are pl 1, QI7, Topic: 8-Queens +borm-n=a-b specify ed on the same diagonal. Q17. Give the solution to the 8-queens Problem using backtracking. Nov/Dec.-18(R16), a5 (OR) Write an algorithm for the 8-queens problem using backtracking, (Refer Only Topic: Algorithm of 8-Queens Problem) Fob /March-22(R18), Q4(b) Answer : 8-Queens Problem ‘ The 8-Queens problem is a classic combinatorial problem to place 8-queens on 8 x 8 chessboard in such # way that no two queens can attack each other i, 20 two queens are placed on the same row, column or 8 queens problem can be solved by using sitnilar acute adapted for 4 queeiss problem. The algorithm of F-aueens problem can be obtained by placing n = §, in N queens algorithm, i i In order to determine whether more than one deen Ying on the same diagonal, The following is device. : Assume that the chessboard is divided into rows and columns say, A[ 1... 8,1...8 wi kev § c rows aed ‘This can be diagrammatically represented as follows, 12345675 2 DESIGN AND ANALYSIS OF Algo me that a queen is placed at pon Now, if the diagonal cells Dea, Bp a traversed from upper left t0 lower right ang thee present in these cells are subracted, then ak values obtained will be same. That is 2 _\)°" rt 5—4= 1. In the same way, if the 4isgong §s are traversed from upper right to lower joy al values present in these cells are added, sine My are obtained. That is 24+3=5,144= 5 4 BT Hence, it can be said that, on traversing from 4° 3} to lower righ, if (m,n) (a, b) are the diagona (of a cell) than m —n = a ~ b or on traversing upper right to lower left if (m, n) (a, 6) are the diag’ elements (of a cell) then m-+n=a+b, ty Algorithm of 8-Queens Problem begin integer k,n, AI: 8) A(1) 0; k 1 //k is the current row; Ai the current column while k > 0 do // Move for all Tows AW) < AQ) +1 // Move to the next colum, while A(k) <8 and not PLACE(k) do // Place ty queen if possible A(k) — AK) +1 repeat if AW) < 8 // If a position is found then if k= 8// Check for the completion of solution then Print(A) // Yes, print the array else Tkeks; A(K) < 0// Move to the next row endElse else : kk~-1// Backtrack endElse repeat // while end 8-QUEENS Solution for 8-Queens Problem The solution of 8-queens problem can obtained similar to the solution of 4-queens problem. as Gx =wxgeT. 1X7 = 8, xg= 5! Te means, first queen is placed in third column Second queen is placed in sixth column third queen i3'placed in second column fourth queen is placed in seventh column 5 fifth queen is placed in first column sixth queen is placed in fourth column Seventh queen is placed in eighth column cighth queen is placed if fifth column75 = Disjoint Sets and Backtracking The solution is shown below, State Space Tree ‘The state space tiee for the above solution is given as follows, Apeli-18(R15), 28(b) yroblem. 18. State and prove sum of subsets P Auswer ; ubset Sum Problem us 4 ‘set 5 (containing n positive numbers) A i jem to determine & SUBSE! nae or a given set S of n objects with 2S tage Prope othe given inset Me ‘That if “orthe given set S, such that, wih the sum of subset should be aay are eguired 0 find 8 subset S (Way) and a positive inteser - 7 LIABLE to face LEGAL, proceedings, Fae, Anne found gully- ey me DESIGN AND ANALYSIS OF ALGORITHIy LS @ ses Gi) Sum of the elements of subset S$" is equal to M. | For example, if a given set $= (1, 2, 3, 4) and = 5, then there exists sets 5’ = (3, 2) and S'= (1,4 whose sum is equal to M. It can also be noted that, some instance of the problem does not have any solution. For example, if a given set $= (1, 3, 5) and M= 7, then no subset occurs for which the sum is equal y Mat. ’ . ‘The subset sum problem can be solved by using the backtracking approach, In this, implicit tree is crea which is a binary tree, The root of the tree is selected in such a way that it represents that no decision is yet take, on any input. Assume that, the elements of thie given set are arranged in increasing order. ‘The left child of the root node indicates that, the first element should be included and right child of the oa. node indicates that the first element should be excluded. The same procedure is applied for the other nodes. Each node stores the sum of the partial solution element, If at any stage, the number equals to ‘M’, then the search i successful, At this time, search will terminate or continue if all the possible solutions need to be obtained. The dead end in the tree occurs only when, the sum of S”is too large. Thus, backtrack one step and continue the search, Algorithm SUBSET SUM : This procedure finds all subsets of W(1 : n) that sum to M. The values of X(j), 1s j M* 1, Global integer’M, n; 2. Reals, s; integer k, j /* Generate left child. Note that s + W(k) < M because Bk - lobal real W(1 :n); global boolean X(J : n) } truet/ 3. Xe] , 4. ifs +W() =Mi/ subset found 5. then print (XQ), j = 1 10k) Mherg is no recursive call here as WG) >0, Isis n 6. else : ‘ 7. fs+W(k) + W(k-+ 1) 5M then /Bk = true ; 8. call SUMOFSUB (s + W(k), K+ 1,1 WO) 9. endif 10. endif ‘Generate tight child and evaluate Bk ML ifs +r—W() 2 Mand s + W(k +1) 8 SHS>8 asmR TEoe ors wyAws4wy | | ets of w which sum to-m, They re 88 = 5410420 i = 35=m | 2, BULOOIOI > m+ Wat We : ia | = 54124 IB i = 35=m :jacktracking 9; Disjoint Sets and Bi G01 1001) > w+ w5+ 1% 7410418 =35=m pl0000101) > ws+ wy = 154+20 rithm for it and explain with an example. pescribe the backtracking t ae et racking technique to the m-c col ie an loring graph. Explain with an example. FebsMarch-22(R18),a3(a) Explain about graph coloring algorithm. (Refer Only Topic: Graph Coloring, Algorithm) ‘au-22(R18), O41 22184), 410) (OR) Draw the state space tree for 'm’ coloring when n= 3 and m=3. (Refer Only Topic: Example) Feb March-22(R1), 4a) (OR) Define Graph. : (Refer Only Topic: Graph) _ Apel 8(R15), 6(a) : (OR) Explain about Graph coloring in detail. (Refer Only Topic: Graph Coloring) Api 18(R15),23(2) A graph is defined as G= (V, E) where, Vis the set of elements called nodes or vertices or points. i) is the set of edges of the graph identified with a unique pair (U, Here (U, V) pair denotes that there isan edge from node U to node V. Graph Coloring : Consider G=(V.E) ‘such that each vertex is assigned one color Let G be a graph and m be a given positive integer. The graph col Gan be colored in such a way that no two adjacent nodes have the same color, yet only m colors are used. This is termed as the m-colorability decision problem. ‘The m-colorability opti tion problem asks for the smallest integer m for which the graph G can be colored. This integer is refered to as the chromatic number ofthe graph. Algorithm ‘ Algorithm meGraph (vertex) { iy while (true) //repeat until either, { Y ; clr = Next ae IF ee / @ lor. iteotor==0). Exit if the given erp cannot be solaied wih monk Teturn; ee aaa V) of nodes. ‘as an undirected graph. A valid coloring of G isan assignment of colors to the vertices ‘and no two adjacent vertices have the same color. loring problem is to find if the nodes of ‘all the vertices have been colored, or if iis not possible 10 0 50. = a rR URBL HGRL a): oN DESIGN AND ANALYSIS OF, ALGORITHyg x[Vertex] = color; HAssign the color to the vertex if(vertex = =n) AI the vertices have been colored t fori= ton do print x{i) retum ; } else . meGraph(vertex +1) (Color the remaining vertices ) ) funetion NextColor (vertex) { while (true) { color = mod ((x [vertex]"+ 1), (m+ 1))s Generate the next po: le color fot index = 1 ton do ( if (Glvertex, index] +,0) AND (x{vettex} break; findex})) +1) /INew color'found, hence return it Example State space tree for m-Coloring when 1 =3, m=3 Ttmeans, there are 3 vertices in graph and it is Fequired to use atmost 3.olors, to color the graph. (ome moves leads to solution of may lutions, yi “STA PUBLISHERS AnD DisRIUTO1xG)=3_ GY"? xG)=1 XG, )=3 xG)=2 xG)=1 xG)=3 x xG)=3 x@)=1 DO 60:90 60-60" Go ‘The possible solutions are 12, within that, 6 solutions are exist with exactly 2 colors. In the above tree, when (1) <1, then x12) contain either 2 or 3 but not 1, since two adjustment nodes should not have same color, when 22)=2, then x) contain either 1 or 3. Similarly remaining nodes can be processed. Analysis ‘sn upper bound on the computing time of algorithm may be arived at by noticing that the number of jetemal nodes in the state space tree is ew. ‘At each internal node, O(mn) time is spent by NEXTVALUE to enmine the children corresponding to legal colorings. Hence, the total time is bounded ag nin! — (n-1) = Olnm). 22. Apply backtracking to solve the 3-coloring problem for the graph of figure. Answer : Backtracking is a technique used to solve the 3-coloring problem by employing any one of the following two algorithms, 1. Recursive algorithm 2. Iterative algorithm. 1 Recursive Algorithm Algorithm 3-COLOR_RECURSIVE. : 5 ( 3 fori:=1tokdo i ' : : color fi] } , f: = false; /Mf indicates flag - GRAPH _ COLOR (1); iff return true; INenexihas color else return false; 4 ¢ ‘Nertex i has no color82 { fore: = 1t03do { color {i} :=¢; if(color is a partial ) fr=tue; else if (color is non-partial) GRAPH_COLOR (i +1) } 1 The input provided to this algorithm is an undirected graph G = (V; E). The output obtained is a 3-coloring [1...A] of the vertices of graph G, where every vertex has a color [v] = 1, 2 0r 3: Initially, the vertices of the graph have no color. ‘Thus, color 0 is used to color them. When the call procedure GRAPH_COLOR(1) is invoked, the first Yertex i; is colored using color 1. Since, 1 is partial coloring (.e., adjacent vertices having different colors), ‘the call procedure is invoked recursively with i = 2, ‘which specifies that the second vertex ip is also colored ‘using color 1. Now, both the vertices j, and iy has colors G51) respectively. If there is no edge between these veitices, then the coloring is said to be partial, otherwise, itis said to bbe non partial (adjacent vertices having same colors). Since, (1, 1) is non partial, a different color ie., color 2 is used to color the second vertex i. Hence, the colors of i and ip are (1, 2) respectively. Now, again the call procedure'is invoked with i = 3 and the process is continued. In some situations, the call procedure fails 10 color the vertex v for v3. This is because of partial coloring that is not obtained even’ after executing for loop three times. In such situations, the last recursive procedure is called again to color the vertex v-1. If the resultant coloring is still non partial then the last but one procedure is called. Here, backtracking occurs, which is continued tll all the vertices are colored with a legal or partial coloring. : 2> Iterative Algorithm Algorithm 3-COLOR_ITERATIVE t . 2 for i:=1t0kdo { color fi) J f= false; M indicates fag iis ak * while (21) Salis: “while (color [i] < 2) DESIGN AND ANALYSIS OF. ALGORITHM, color {i} : = color [i + 1 if(color is partial) f= true; else if (color is non-pattial) issitd Generates new vertices ) colori =0; zi-k Moacktracking takes place } if return true; INertex i has color else retum false; INeitex i has no color J ‘The input provided to this algorithm is ay undirected graph G = (VY E). The output obtained is a 3-coloring color [1....k] of the vertices of graph G, where every vertex has a color [v] = 1, 2 or 3. Iterative algorithm contains two nested while oops in which new vertices are generated in the inner while loop and backtracking takes place in. the outer while loop. Iterative algorithm works similar to the recursive algorithm. The time complexity of both algorithms is O(n - 3") where O(3") is the time used to generate nodes and O(1) is the time used to check whether the current coloring is partial, non-partial or neither. 923. Use the backtracking algorithm for the m-coloring problem to find all possible colorings of the graph using the three colors red, green and white. Show the Figure: M-Coloring Problem Graph Answer : "The given graph is, Figure: Graph~ — Se STA PUBLISHERS AND DISTRIBUTORS P\ VT. LTD. 7)olor red, green afd white be represented Gand W. The step-wise coloring of graph using 9G Wis ven below, : «@® 7 @ R G w o Om . k 7 a @—@) : i § g C—O) Woe oe : Here, backtracking technique is not applied 4s there is no problem in assigning either of the three colors Q24. What are Hamiltonian graphs? Explain briefly with an example. What are basic tules for constructing Hamiltonian cycles? ° Answer : Mamittonian Graphs A.graph G is said to be Hamiltonian if there ‘iss a cycle’containing every vertex of G. This cycle ‘called Hamiltonian cycle. Therefore, Hamiltonian Sph isa graph containing a Hamiltonian cycle. A path in a connected graph which includes Svery vertex of the graph is called a Hamiltonian path. is a cycle in G which contains all the vertices + itis known as Haxitilfonian cycle. A Buler circuit thus traverses each vertex at least once, on the other hand a Hamiltonian cycle traverses each vertex exactly once. Example Figure (1) In the above graph, there exists a Hamiltonian cycle (shown in thick lines). Since it contains a Hamiltonian cycle it is a Hamiltonian graph. There exists a Hamiltonian path which is shown in thick lines in figure (2). A B Figure (2) Rules for Constructing Hamiltonian Paths and Cycles 1, Ifa graph G has n vertices, then a Hamiltonian path should contain exactly n—1 edges, and a Hamiltonian cycle should contain exactly n edges. 2. Ifa vertex V in graph G has degree’k, then a Hamiltonian path should contain at least one edge incident on V and at most two edges incident on V. In a Hamiltonian cycle there should not be 3 or more edges incident with one vertex. 3. Nocycle which does not contain all vertices of G can be formed when building Hamiltonian cycle or path. 4. All unused edges incident on V can be deleted, once the Hamiltonian eycle which we are , building has passed through a vertex V. CIRC igs book Ts FERIMINAL 0 Anon e plts ABLE oc LEGAL proceeding)