UNIT — Disjointsets and Back tracking Ss Disjoint set Opesations set; A set is acollection of distinct elements. eq: Si = he 10 { Disjoint set? Disjoint sets awe those do not have any common element. disisint (Q,.S2 )= True iF sias.= {lot eg: Sie [789] ond Sr -} 245,104 5 The disjoint set. clea stoucluse is wed to stose cuch sets. Tt supposts llooing Operations, = Bouicablyy we hove two cisjoint opesations awe these - }- Onion 2. Find x Union 2 Meaging two disjdint sets to a single set using Unie operation. -Heve “We hove two Bypes of union operations oda Then: Thy oe. |. Simole Union 2. weighted Union > A simple union joins ‘two sets without considesing thelr | — exsentially malcing one set's vot the parent of the other, while a wie hted union * stértegically na the smallex seti woot to the lasger sel ‘wood L\+ Simple Union + Unron Ci,5) eneans the eloments seti ond eloments ,of set 3 ase combined» IP UNion — opexation of a tye. Then UNton Li, ya the pasent, Ss fee presented Os, @ j Set $, can be Bepresented ou, set 5, com be teptesented as. Now, Union cs, Sx) 2 SUS =f 1s, 3,244 3 6 the child ff Sf ss So 324) 1 %4Or Should be sepsesented in the -fosrna Agosithin : / Simple Union (i, 3) ij &€4: ONlon (1,2) tse a ede | i P - - CG Time Complexity /_ oe oe taleen +o pextosey Union Operation is Constant yn). Therefore oll (n-1) Unions can be processed in time On). a- Inleighted Union ¢ TH the number of Nodes T in tree is tess than the number of nodes in tree j, then make jas the pant node of i, Che make fas the parent node of }.- Algovithro eq S, Se Weighted Union Ci, 3) © {MFA are dicisine sets @ PLi] =- Count Li) 5 (i; © PLIJ= — Count Cid; Th s> Sr => S)- Parent tree sum= PLII+ PLIIS Sp- Child tree a CPL 7 PO) che S28, 9 Sie child tvee - S)- Peent ‘tee i ploid= 35 Racer itp fe [s [fale ptsd= sum; es) als che a wish t pesde 13 SVs, o PLA} - eLid= sum}Co > Pooceduxe to pevtoorn giraple Union ¢ Sf \- Initially consides oll she elomnent s ane “bead a asx separate Agee: a PLi] — parent} node 1- 3B. For Mook node epud i cL y Arter performing each unio Operation updaki PLid- eq. | p38, 4, Br6- tit step. Make taee- os individually. o oe © © © Parent child : Sstep26 ‘Union C 1,2 step, Parent i 7 2 43/4 ae bila 1 : PLAI-] {ifs fat, = UNION C34) Yrant 5.6) alififa [als or i g afi [: a[t © step 4: UNION C14)se / ne Complenity of Weighed Unions Union coun be done “0 Numbers of times ot as the tree ond tind Contains n nurn beg elements becomes O Clog nj. — The worst case time Complenity tor W-Union is OU)- tohen there ose ™>=N oOpesations tv be perfosrned on © elaments , the time complemity will be OGmlegn) X Find Opersation : Searching am elarnent in a disjornt seb is called nd opexation. Tt can be ccepresented by jth Eon Ui), implies that it finds the tout node of i Node , in other words , it seturns the nome of set i Hese We have two Find operation: are there. = L Simple FIND 2- Coll apsng FIND 1. Simple FIND 3 Seoreching e elament in the qiven set, Te itis setuens set vepsesentative elaments -[-anvt | Arent} Algosithny 6 t eqt 1, 2 a, yy. Fino C+) prsjornt set C17 3) 8 aihile (pti) 2) Find (4%) ft return I tfifefafa | ; j= PLT Oo & i 3 PLiy 2] | 1] aeturn 15 i Or Find (4), i= 4 P04) = 320 re3 Find (3) '=3 3 ecad= 1 0 ecit=) 10 termindey:i a Tiene Complenity: each FInd operation wequires tind | links feom node | to “the wot Node. The time ‘tequived ts peeforrn a FIND _ Operation fos an ee ot Level a chain PARENT 7 of a tree fs Ow) Therefore , the total time needed process the n-r +tinds is Oln+)- 2 Collapsing finds The main Reson 2erton -for uxmg ‘ collaping whe No need t traverse the tree -for ‘Searching 09 elarment- Algoaithm ¢ ' vt Collapiny Fimd i> 1a é4: tai while CPC >0) t TH PLDs jou while Cit) A Se PLATS =i PLid= 3 5 i] osing eallopse Bale callape all modes Se! Oreo oda of i 18 e- qeturn% 5 a> we 2% ye i \- merou4 Repsesentation of Binary “Tree “Repsesentation of Binoay Tue 2+ Complete Binary Tsee 3. Heap ye Ensevtion & Delete 5 Heap gost 6 Heapifg v Prioaity Auwue- x Arvoy. eg! fe @® © 6 606 12545 6- -s Tk aNode ts ak ander -% = > ts “ight child is of - xt's Tt's leftchild is at — pacrent node ab - 2xt — 2x1 +] ° t > Bo. o z yu S & ©) (alee TTS} Toe uaeComplete Binary Tree t = é Hight of a Binary ince b) is Full nodes No spuce a fr new Noor . meons Pun Nodis in the Binary tree ts atu Binasy tree. : Tt we DRepserent an sors thee Ose NO Gaps iN the : nee tree is acomplete bmary toee with hight ot the tvee must be full bmary -tres. with (hl) hight: ani [moda Should Stl Loht to aught: i h Xf ot - /\ 41 8 O wa & r 9 ©@ {2 be = © y els eoreng fafelefeel CRETE) Complete 8 Not ce complete BF | Full nary tree Chat to, Rigit’) “> Hight of a complete benany tree mininawen Joy 0- ! ¥ Heap e- ! ae Minn Heaneyar % cop is a complete Sinarey tree. Hease we have two dypes ok Heaps ade there, & Max Heap 2 ON). Heap Max Heaps Mar heap is a complete Satishes a cond Binaay tree Hon gy ever node ic hauing ’ the Chament qrealir, than on Equal fo all it's docendences Min Heaps min heap 's a complete Binoy tree satishier a condition at every ede is having the Clement Sever than lor) equol So all it's clecerdunces Insestion y— : hed @ , am i o. W [50 “ic ‘s|iols v6 69) ee <1 rors es oats a el fio ao lio, \s [Ie | 3) Ansest 60° axis 24 he BP ; ede 4 eo - 2has taken thas time teeny er : 2 Time Complenity § So, ‘the maximurn meumber of ab S the Number of senps- swaps 1s equal do height of the heap: So height of heap %S © Loy) - the go, minimum oh OU) * rani OlLogn) Deletion 2- : ‘Sele > tle conrot delete “any other eloment pea bf, wot eloment con be deleted . Z = like ‘Apple Phiponid - Tn heap also toprrost elomert will be dotted» Tn minimum heap abso Sopmost clamed will ke deleted , Delete 50. (s > ¢ : “8 yo 89= fne complenity of heagl of deleton Operation \<, height of the heap. $0, Tt is Oltogn). > Like this we delete apis nodes amd eee up anna4. And we com aliy insest WO Avec spaces bay Acleted ehamenta « the occupies the Then Aralby it gives) the — sovted ednouy « GISTs 3 Heap Sosts— a 6 5 stepl: Cueat a heap Stepre Delete the hed: eg (00 Jeof is] aol tg} an & oar criny —_ yesu § % Time taben by ologysep? $ oon oe & ane BEE ° BEE] sa sucha eas T2aeu Dele ou Del 30 Del 20 Del is Time taleen by Aeletion 1 bogn a = For Insestion time will tetker, 9) 40q9 ema Deletion time will taken n legn. ,rtheo nlogn + nlegn= 2n loan = (nlegn- = Heap Sot = time complenit-y te On logn- Heapitys Paces of Cucatng aheap , bt it's AiHferee child 40 poaent node- wa ditvecton te =Chon words » by ths weoele : hemp- 7B> Time Cornplenity toe heapity olny > MAIN mum Ame Otn) - Potortty uo & : ~ Queue means FIFO. > Poiovity queue is a Hype Sok “oueut that 099 y elomnents barsed.on. Ihein -parfooitty valiirs ; Tr the Most commen method +o implement ar priority hove Easy access te the in mak heap) ond biney hy tenelernented i. ie ques. To Bimony heaps , We, min Cin mm heap) or maul being a complete binary tore ane eas} using ada0446- cf no <3 The bat ‘nplementation ob” paiovity, ‘queue is heop- ‘ i “insertion, = Operations on aprionty Gite Vode leletnn ond Peak Crnin Juthan fositien ok heap]. Bye Heap. eaplain in delat’ annyk Toa cking 5 Zt is a pooblem aalving Technique lilee Dyide'and conquer , Gacedy mMethed, Oynamic pogwarnming and . Bmanch amd Bound all Ahese alt different ptoblem solving algo thrng . > Tr wed for sdving Aecursive poobleins , thd means part of the prollom cthat havens Sepeatedly « > BY amy Backbrmacking we will ae muthple sdutions net a single solutbQ , $2 cthis ts @ not aophmisation padblern > Optimisation Pooblem Means we will get the one beat solutoo. Gut is backtoacking we get muttiple ofetions, Lo cthese sdurtiony We ave te gick one opticna) soliction « > casing back ond comiusy agai until condition. is sattctied « | 5 deadendN ich Route focce Approach 7 TAS gy wa ) 2 i> Back “Foacking uses Prolem solving strategy . Tr says that for amy given solickons ond pickup | problem we should try alk possible deshed solution. Libe 1 Oynamic Prksamming we were solving optimisation problern « T+ Allows DES CDeapth frst seve | “4 BiB, G = CET neg, Bie axle, q& & of Nee 6 salrhny & al Ae Oo . 7 “ v 6 i> state space trees TH solution space is gepsesented using a tvee then that see (6 welersed +o as the state space tree: > Live Node: Live Node is defined as anode which con \\ be qenezated without generating “its childyen nodes: ee 16) ae a, 7 : ® / @ Ais not a live node , but Band coe te nodes. A E-~nede is alive Node which can be node. énde > €- node t Ctpanded 0 generate — it's childsen node p ab «=O Here 1 node. Ais @-Mede arits childyen \ are csuerently being qenefated Cexpanded) - ©5 5 x Nodet A dead node is dekned asa node Which can be generated with all it's childxen omd cannot be expanded fasthes . Ens ws 6, : Node A, p,¢ ade dead nodes 0 A, C,0 OF do ad nedes: hecate ftode A's children 97° a pnoraiz One generated Lut node 8, C oF nok & ton yrer more Nake eupanded: Tmplictt constraints 3 The wmplitit conctsaints O52 set | Leck of qules Usted for determining which tuple inthe ee Space 7 Pe ear ileal of the coite sion funckon - Explicit constraints: Explicit constvaints ae get of gules \ sy ot that inplises ses certain tenit 9? ba ee the cxteron tuncton Se that they wnuck —poswss only he Volts that od defwd inthe Per set:ions. of backtracking ; N- Queen's problem ¥ Sumof Subsets Pollen * Spaph Coloring ¥ dtamiltonian Cycles. N- Queens’ Problem ': The n-queens problem is the pivblerg ‘io which ‘W'queens ave placed ona chesshoaid ot size nxn wo such a wou that, none of ‘therm can Capture amy other by means of the stand ard Chess queens moves. = No ‘two queens con ‘be ‘placed in ‘the same ow: > No two queens can be placed ‘in “the Same Column. > No two queens con be placed in the same diagnal. eqs 4-queens problem is an instance ot the qeremabized N- queens gooblern- The backtracking is applied on t-queers problem to detesmine the solution: The -folloeving steps ‘Wusteate the wosking of backtracking on A- Queens grobler . Begin the’ process “by placing’ Hist queen ‘in Fivst poston ve CU) on ‘the eynpty chess boasd- - G& Ga, @,- : aag —> Next, place the Second queen at (2, 3) position - Si is mot possible to place it at ipostttons cz), niente, Un eae Ta x fe PO 7 x x x Shows ‘thot Q, atlack + @ Hf placed in that: position >, Now, adjust the position ot the third Position . since queen? 1 Qr ts, placed at (2,3) it is not possitle to a the Q, at Next position. _ : ctHence backtracking ‘s pestormed on the setond Bow and sewnd queen 1s Teplaced at the pxston (2,4) ond & is adjusted wat position ce 2). ; us Qi Bilx [xf [a i fe : ee PSD ST Aa al ef ed Jay. im 1A “TA uh [as « : Lhe SPD bel EE] Now , to adpat ithe position, ot fousth queen @y pexfosrn Fist, second and. thitd wow : Reawscinge the position of Hest, second ond third Queen C@,,8, 8Q,) as it leads +t dead node: hacktwacking on the [x ]a,] x |* «| 4] * | x lalx |» xix >[xfelal Lele] xfe x ee ee A rT x [x] x |x xx Hence after this, A, 4. 0s 4 O, o placed et permissible such as W2), belo sequence * We have one golution. ie, (2,4), CB: amd (413) respectively a4 shoon in ao &% 8 2 falda mote Sdlutiory that is missy image ot test uw QO By Oy afi fs a x Thus the optimal solution obtained alter pestering backtiacking ~The state space tvee is sh O is (2, 4,13} and 23, 1,42} im wo taskion- oan below- x This sepsesents postion of twee of -Lhat a? is qenesated luring Gacktracking.Complexity Analysis of Backtsacking ¢ Since bacle tacking algorithm js pusel 7 + Hele, He \y boute -fosee therefore, fo tesms of time complerity , it performs very poosly» Grenerallay backtwacking fan be seen hawing below mentioned time compen *% Exponential O02") . * Factorial OCNI) ; ¥ Sur of Subsets Paoblern : sum) Given a Set tJ of non ~negative integess ond avalue the, task is to point tthe subset of the qiven set whose cum ‘8 equal to the qiven sun. el a4: €4* x Dnput + set C= {ur}, sume Output + fury ft] Euplanation + These ave subsets wy Cd ath cite! 3. @nput + set C1 > {3,34 4,12,5, 1 ee Output + CJ Explanation : These fs no subset that add up to 50, Using Bocktoacking Leet gurn can abto be thought of a4 a special care ob the subsel rn cle Puoblern” For each item, these ase two possi bilities, 0-1 Knap nclude ¢ “The cusrent eloment in the subset omd csetus tor the sermaining alernent’s with “the “senaining ‘sum, ;oy the wernaining elements” “Fnatly if cui becomes. 0 then: print the elements, of cussent subset» The ecussion's base Case | would be when no items are lebt ond the Sumo becomes neggttive , then sivnply speturn + .\4 0% Subset (1) sot subset TargetSame | subset [1] Tasgek Sum = 2 ania subset 1) “Tauget Suro 22. Subset (1) Targd Seme | subset GE] Tasqek sum =| Tasgetsume 2 Surn of Subset Problemsing Assian Cornplenity Analysis +, Time complevity s OCs") the solution may. try aU subse p of the given set io the worst care: Theset@se -time compleaay of the atove solution is exponen tal: Space complenity ts On) where Nis secusion stack space. Siwaph Coloring « Graph coloving wefess to the problem of colosing vestices ot a graph in such a way that no two adjacent vestices have the same Colot- This is also called the vestex colosing Pooblem . Tf coloxing is done using at most rm coloss, it is callad m-colosing. x% ch tye Nurnbex ¢ The minimum numbers ot colors needed + Chsoma to color a asap is called 4 OW x 3 -cdeable 2 - Calorable 2-Colssale it's chsomatic number - lan) oat x Gyagh coloring problern is both, a decision paoblem as wellds an optimization pooblem. Th optimization pooblem ty stated as, Given 1 colors « e 4 colors a the minimun number 0 and Gwaph &, Fn. aequited fe qeaph coloring.f ésing Racktvacking ; to Aitlerent vestices , starting 0. Gelove assigning color, Check if the adjaced game clot oF not. Tf there is ang color violate “the conditions , mak the + the solution + Tt no assignment nd oetuy alse: ots Hesigh colors one by O% Aro verter vertices hove the & that does not gnment as pat © ‘then assignmen colow assi of colos iS possible af Evade Coloring $ packtoack Applicator s = oesign a Emetable 5 Sudoku > Register all ocation iw the compiler. = Map coloring» Hamiltonian Cycle + Hamiltonian eycle oo -choeul that visists every Vester of G eractly once the stasting “verter: : t ina graph Gis a cycle ond ‘setumms to —> a yaph contains atlamiltonion cycle, itis called “Hawestion' at is ron~ Hamiltonian. qeaph otheswise na azsaph is awell-knoon > Finding a Hamiltonian Cycle \ which means. ‘that, these’s no fenown NP- complete prodern i few all types of gaaphs: Hooeuey efficient algerithy ‘to salve * t ‘ it con be solved for small or. specific types of ysaphs.le pooblern has practical application s > The Hamiltonian Cye netwosk design, & in ‘various -Belds , such as logistics, computer Science: > +lamiltonian Path in’ 4 graph ais apath that visits every vate ol & exactly once and sHamillonian path doesn't have to setum to “the stovting verter: Tt's an open path. €4: Using Racktuacking Algootthm : Start “ out puts out puts. ; {o.3, 4,2) 1.04 , | 41,2, 4,300) i VG a 30, tt : tars, ots 45 (he 5 ' . 15 e 3 ; Ac: : ol wei athe ‘omiltorian path fo3,u.2., ol we get cycle” = ao as ‘node 1 is ‘the. Neighbour of made O- So, this is | a ae Hariltonion cyle- : i |S ito ao sk 2, 3,4 abso we gd soluting. | <> Time Complexity ts OWL) where Waumber of vertees «