G@i2 MU QUANTUM Series PU Debate x ‘ = c jon = * Topic-wise coverage of entire syllabus < sess'25 in Question-Answer form: . gq Short Questions (2 Marks), : facies ‘solution ¢ of following AKTU Question Papers 2020-21 * 2021-22 - 2022-23 - 2023-24UNIT-1 : INTRODUCTION (1-1 B to 1-44 B) Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of Functions, Performance Measurements, Sorting and Order Statist Shell Sort, Quick Sort, Merge Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time. UNIT-2 : ADVANCED DATA STRUCTURE (2-1 B to 2-42 B) Red-Black Trees, B - Trees, Binomial Heaps, Fibonacci Heaps, Tries, Skip List. UNIT-3 : GRAPH ALGORITHMS (3-1 B to 3-39 B) Divide and Conquer with Examples Such as Sorting, Matrix Multiplication, Convex Hull and Searching. Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack, Minimum Spanning Trees — Prim’s and Kruskal’s Algorithms, Single Source Shortest Paths - Dijkstra’s and Bellman Ford Algorithms. UNIT-4: DYNAMIC PROGRAMMING —(4-1 B to 4-44 B) Dynamic Programming with Examples Such as Knapsack. All Pair Shortest Paths — Warshal’s and Floyd’s Algorithms, Resource Allocation Problem, Backtracking, Branch and Bound with Examples Such as Travelling Salesman Problem, Graph Coloring, n- Queen Problem, Hamiltonian Cycles and Sum of Subsets.a 4 UNIT-5 : SELECTED TOPICS (5-1 B to 5-39 p) Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NP-Completeness, Approximation Algorithms and Randomized Algorithms. SHORT QUESTIONS (SQ-1 B to SQ-31 B) SOLVED PAPERS (2020-21 TO 2023-24) (SP-1 B to SP-13 B)Introduction CONTENTS Part-1 : Algorithms, Analyzing Algorithms, Complexity of Algorithms Part-2 Growth of Functions, .. Performance Measurements ..1-8B to 1-14B Part-3 : Sorting and Order Statisti: Shell Sort, Quick Sort .1-15B to 1-19B Part-4 : Merge Sort .. 1-20B to 1-24B Part-5 : Heap Sort. .1-24B to 1-31B Part-6 : Comparison of Sorting. Algorithms, Sorting in Linear Time 1-S1B to 1-43B 1-1 B(CS/IT-Sem-5)P| 2BICSAT-Sem-5)_ Intro ee uti oe or it ly rithms, Com, : Algorithms, Analyzing Algorithms, Introduction : Algc ve re Quel. | What do you mean by algorithm ? Writ, the characteristics of algorithm. Answer Dlexity of 1, Analgorithm is aset of rules for carrying out calculation either by hy, nd or on machine. | : 2. It isa finite step-by-step procedure to achieve a required result, 3. Itis a sequence of computational steps that transform the input into the yut. 4, an ‘algorithm isa sequence of operations performed on data that have to be organized in data structures. Characteristics of algorithm are : : 1, Input and output : The algorithm must accept zero or more inputs and must produce at least one output. 2 Definiteness : Each step of algorithm must be clear and unambiguous, 3. Effectiveness : Every step must be basic and essential. 4._Finiteness : Total number of steps used in algorithm should be finite, Que 12. | What do you mean by analysis or complexity of an algorithm ? Give its types and cases, Answer Analysis/complexity of an algorithm ; The complexity of an algorithm is a function bound of the number of oj eration (or i is algorithm when the input size isn.” TUNTIRE time) performed by an Types of. complexity Space complexity : Sp: of memory it needs to values for execution. an algorithm is the amount including the space for input timesa statement executes, Iti Tem tt 5s the number of a particular code, Cases of complexity : 1. Worst ease: It is the u 2. Average case complexity : jee to be executed : for any givers cxecuted. Will be the average number of operations over ah prope Sze input for a given size. ™ instancesDosign and Analysis of Algorithms 1-9 B(CSNT-Sem-5) Best case complexity : The best ease complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n PART-2 Growth of Functions, Performance Measurements. Que 1.3. ] What do you understand by asymptotic notations ? Describe important types of asymptotic notations. OR Discuss asymptotic notations in brief. Answer 1. Asymptotic notation isa shorthand way to represent the fastest possible and slowest possible running times for an algorithm. 2. Itisa line that stays within bounds. 3. These are also referred to as ‘best case’ and ‘worst case’ scenarios and are used to find complexities of functions. Notations used for analyzing complexity are : 1. ©-Notation (Same order) : cog(n) fin) e,g(n) Tg m fin) © (gin) Fig. 1.3.1. a. This notation bounds a function within constant factors. We say fin) = Og(n) if there exist positive constants no, c, and cy such that to the right of ng the value of f(n) always lies between ¢,g(n) and c,g(n) inclusive. 2. O-Notation (Upper bound) : a, Big-oh is formal method of expressing the upper bound of an algorithm's running time. It is the measure of the longest amount of time it could possibly take for the algorithm to complete. More formally, for non-negative functions, f(n) and gin), if there exists an integer ny and a constant c > 0 such that for all integers nen 0 b. c. fn) < can) dd. Then, f(n) is big-oh of g(n). This is denoted as : fn) € Ofg(n))14 B(CSAT-Sem-5) iir., the set of functions which, as n gets large, grow faster than , constant time fn), ce(n) fin) n fin) = Olgin)) Fig. 1.3.2. 3 _Q.Notation (Lower bound) : - 8. This notation gives a lower bound for a function within a constant factor. ti b. Wewrite fn)= Qgin)) ifthere are positive constants n, and ¢ such that to the right of ng, the value of fin) always lies on or above og(n), fin) ceg(n) 1 ! 1 n No fin) = 9 (g(n)) Fig. 1.3.3. 4. Little-oh notation (0) : It is used to denote an upper bound that is asymptotically not tight. o(gin)) = (fn) :for any positive constant c > 0, if a constant n,>0 such that 0 < fin) ng) Little omega notation () : It is used to denote lower bound that is asymptotically not tight. (gin) = (fin) : For any positive constant c > 0, if a constant Ng>Osuch that 0 ng) Que 14. | Write Master's theorem and explain with suitable examples, Answer Master's theorem ; Let T\n) be defined on the non-negative integers by the recurrence. a Tin) = aT (2) + An) where a 2 1, 6 > 1 are constantsDesign and Analysi of Algorithms 1-5 B (CS/IT-Sem-5) a Number of sub-problems in the recursion vb Portion of the original problem represented by each sub- problem ln) = Cost of dividing the problem and the cost of merging the solution ‘Then Tin) can be bounded asymptotically as follows : Case 1: If itis true that : fin) = O(n'orF) for E> 0 It follows that : Tin) = © (n'®*) Example: T(n) = 8T (2) + 1000n? In the given formula, the variables get the following values : a= 8,b = 2, fin) = 1000n2, log,a = log,° = 3 plea = ploe28 = 3 An) = O(nlos aE) = O(n3-F) For E = 1, we get fin) = O(n3- 4) = O(n?) Since this equation holds, the first case of the Master's theorem applies to the given recurrence relation, thus resulting solution is T(n) = © (n!?®2) = O(n3) Case 2: If it is true that : fin) = © (n'ee 2) It follows that : T(n) = © (n* login) Example: Tin) = or(%) +n In the given formula, the variables get the following values : a=2,b= plowe = plow? ; Rin) = (n"*2) = On) Since this equation holds, the second case of the Master's theorem applies to the given recurrence relation, thus resulting solution is : , fin) = n, log,a = log,2 T(n) = O(n!8# Jogin)) = O(n log n) Case 3: If itis true that: fin) = Q(nle 2 +2) for E> 0 and ifit is also true that : if af (2) Sofin) for a,c < 1 and all sufficiently large n Itfollowsthat: T(n) = ©(fin)) Example: Tn) = 2 (3) +n? In the given formula, the variables get the following value: a=2,b=2, =n] = eat eae n?, log, a = log,1-6 B(CSITT 5) Introduction An) © Q(nlowhas BY Por & 1 we got ; fn) = On") = Qn?) : Since the equation holds, third case of Master's theorem is applied, Now. we have to check for the second condition of third case, if it ig true that or (#) seam Ifwe insert once more the values, we get : (2) 1 S) < 2\3] se => 2 n® fin) = O(n? 81-081) => An) = O(n?) Hence, case 1 of Master's theorem is satisfied. Thus, Tin) = O(n") => Tin) = 0(n241) Since the recurrence given by eq. (1.5.1) is asymptotically bounded by @-notation 6(n?). ‘The recurrence given by eq, (1.5.2) will be as fast as algorithm A when its time complexity is also @(n281)_ So for this we can equate, log7 _ loga log2 log4 loga = 287 , jog 4 = 1.6902 1092 Taking antilog = 48.015. So for a= 49, A’ complexity will be equal to A. For A’ to be faster than A, the largest integer value of A should be 48. m a=48 Que 1.6. | Therecurrence T(n) = 7T(n/3) +n? describes the running time of an algorithm A. Another competing algorithm B has a running time of S(z1) = a S(/9) + n®. What is the smallest value of a such that B is asymptotically faster than A ? Answer Algo. A = T(n) = 7T (n/3) + n? 1.6.1) Algo. B = S(n) = aS (n/9) + n2 wf 1.6.2) Smallest value of a such that B is faster than A. From eq. (1.6.1), we have Tin) = TT (nl3) + 2 Comparing it with Tin) = aT (nib) + fin), we get a=7,b=3,fin)=n? ae be? = yim Now, fn = fin) an Case 3: fin) = Q(n'*-"*) = Q(n'™*) [+ ¢=0.23) fin) = Q (8774023) = 9 (n?) Regularity condition af (nlb) < ¢ fin) Unl3? < cn? U9 n®< cn? c= 79<1Introduety n Hence proved. Nn) = O(n?) FP rithm Bi ; For Algor en) = a (nl) +2 ime & finan? =81 borst =n? & fn) =n? ore n So, ifwe keep value of Loge = n lene = fn) => Sin) = O(n lgn) ower than algorithm A. For B to be faste 1B should be less than (0(n?)) T So by case 2: 1 ‘That will make algorithm B sl than A, the time complexity of So, ifwekeep _ 2< 81 in) = ln?) = Ten) Then, Fora =81 Stn)= O(n? Zgn) > Thr) Fora>81 Sin) = O nF") > O(n?) «> T (n) ‘Therefore, algorithm B can never be faster than A. Que 1.7. Solve the recurrence T (n) = 2T(n/2) + n?+2n+1 Prove that worst case running time of any comparison sort is Q (n log n). Answer i 7 n)=2ttnlay + nt an et 2r(2) +n? Compare it with T(n) = or (2) +fln) we have, a=2,b=2,fn=n? Now, we apply cases for Master's theorem. ne = lO? = py This satisfies case 3 of Master's theorem. = fln) = 2(n!982*®) 9 (n1+8) = O(nt*t) =Q (n?) where E =1 2 Again of) se fin’) : (LT) eq. (1.7.1) is true for ¢ = 2 = Tin) = 0 (fin) = T(n) = 0 fin?) ii, Let T(n) be the time taken by merge sort to sort any array of n eley ments.Design and Analysis of Algorithms 1-9 B (CSAT-Sem-5) Therefore, Tin) = T| where gin) « On) This recurrence, which becomes : ( Tin) = 2r|4)+ gin) when n is even is a special case of our general analysis for divide-and conquer algorithms. ci Compare the above given recurrence with Tin) = ert ‘}+ fn) we get a=2 Now we find, n° fin) ie. case 2 of Master's theorem applied then Tin) = 2(n8* log n) Tin) = Q(n log n) Hence, the worst case running time of merge sort is O(n log n). Que 1.8. | What do you mean by recursion ? Explain your answer with an example. Answer 1. Recursion isa process of expressing a function that calls itself to perform specific operation. 2. Indirect recursion occurs when one function calls another function that then calls the first function. 3. Suppose P is a procedure containing either a call statement to itself or acall statement to a second procedure that may eventually result ina call statement back to the original procedure P. Then Pis called recursive procedure. A recursive procedure must have the following two properties : a There must be certain criteria, called base criteria, for which the procedure does not call itself. b. Each time the procedure does call itself, it must be closer to the criteria. A recursive procedure with these two properties is said to be well- defined. For example : The factorial function may also be defined as follows : a Ifn=0,thenn!=1. Here, the value of n! is explicitly given when n = 0 (thus 0 is the ‘base value). 5.| 1-10 B (CS/IT-Sem-5) pac lea tna Introduction b. If'n > 0, then n! =n. (n= 1)! 7 Here, the value of n! for arbitrary n is defined in value of n which is closer to the base value 0, terms ofa smayy, br Observe that this definition of 11! is recursive, since it refers to itselr when i uses (n — 1)! Que 1.9. | What is recursion tree ? Describe. Answer 1. Recursion tree is a pictorial representation of an iteration m which is in the form ofa tree, where at each level nodes are tho des are expanded!’ 2. Inarecursion tree, each node represents the cost of a single subproblem 3. Recursion trees are particularly useful when the recurrence describe, the running time ofa divide and conquer algorithm. 4. Arecursion tree is best used to generate a good guess, which ig they verified by the substitution method. 5. tis a method to analyze the complexity of an algorithm by diagramming the recursive function calls in the form of tree. Que 1.10. | Solve the following recurrences : Tin) = T(nl2) + T(n/4) + Tinl8) +n Answer height height 4 cost/level calf Ta/8 (7/8) cn. cn/2 tee VAN ZN, “ cn/4 cn/8 cn/16 en/8 en/16 cn/32! en/16 en/32 en/64~ (49/64) on ' He 1. Left subtree Right subtree At 0 level size is At 0 level size n At 1°" level size is n/2 At 1" level size is n/8 At 2" level size is n/22 At 2™ level size is n/8? At it™ level size is n/2! At last level size is n/2/ = 1 > n=2! = i= logs Longest branch worst case Ati" level size is n/8! At last level size is n/8 Sn=8' i= log," Best case shortest branch 11-11 B (CSAT-Sem-5) 1 4 (TAB) en 4 CTIBY® en sooo (TB) oN Nay Vga = DL (7/8) en = en ¥) (7/8y Total cost sen Yurisy =en [ Tin) = O(n) Que L11.] Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(an) + T((1 - a)n) + en, where a is a constant in the range 0 0 is also a constant. Answer T(n) = Tian) + T (1 — an) + en where O0. cn cost en AN ten 7 RON. ati = Ben = O(n) 1-7/8 a(l-an — a(1-a)n (1-a)"n den 1 1 1 ' ' 1 ' ' t 1 ' ‘ t t ' 1 1 1 1 tf If a> (1-a) then Va< U-a) So logy. 2 > lO ya) 2 Longest height = log, n Shortest height = log,,,,_,, 2 ‘Total cost = Cost per level x No. of leaves Worst case = cn x (log,,, n +1) nlog,,, n +en 0 is also a constant. Answer Tin) = Tian) + T ((1— an) + en where O0. A (-a)n logy VAN JN > Sia an a(1-a)n a(l-an = (1-a)n cn 1 1-7/8 O(n) cost en i 1 1 1 1 If a>(1-a) then Va< V1 -a) So Jogi. 2 > lO yaa" Longest height = log,,, 7 Shortest height = logy),)-., 7 Total cost = Cost per level x No. of leaves Worst case = en x (log,,, ” +1) = cnlog,,, n +en Scr logn Tin) = O(n Ign) (LALA) Best case = en x (log,);., 2 +1) = en logyy., 2 +en Scu logn Tin) = Q (n ign) (L112) Using (1.11.1) and (1.11.2), we get @ (n Ign)| — ety 1-198 (CBAT.Bem-5) Que 1.12. | Solve the following recurrence relation ; i Tine Tine tant Sie Dn) = P n/a) + 7 (12) +n? AKTU 2020.21, Markey aT Answer i Tn) = Tin 1) nt ‘Using Master's method for decreasing function Tin) =a Tin ~b) +f (n) where a2 1 and b > 0 and fin) is a positive function ie, fin) = O(n") for k20 Case 1: If 1 ‘Then Tn) = a * fln)) or O(n'*}) Case 2: If a>l Then Tin) = O(a * fin)) = O(a" nk) Tn) = Tin-1)+n!4 Here =landk=4, Applying Case 1, we get Tin) = O(n * n4) = O(n5) i Din) =P (wld) + 7 (n/2) + n2 cn” ~~ costievel Kem cn? ay 5/16 en* / log, n Je ~ “ logpn 2 2. ne A og eh oy ay 16. 8 8 -- 25, 1 1 1 1 eng 1 1 1 1 ' ' 1 1 1 ' ' i) i) 1 t 7 1 1 1 ' height height Height n—nl,—nlyg....1. i Jevel = n/A! Left n/A' = Lat the last level n=4!=i=logyn Right n (2 = at the last level n= 2 =i=logyn As logn > logyn; worst case height = logyn Cost at last level (logyn) : Number of nodes at it level = 2'Design and Analysis of Algorithma “13. (CANT-Born-6) Lovol aoe Oaee es 1 2 2 4 i 2 Last level is at log At logyn — number of nodes = 2!"2" each contributing to cost 0(1), Cost at last level = O(2!2") = O(n!) = O(n) Cost from 0 to log,""" level wert Bat oY crt” et myrt/ 5)! mel 6 Total cost = Di (4) en* + O(n) = en > (4) +OIn) ‘ ont (5) +OIn) ad 16a A paneiaanas 226 = Oln) nig tlm =F en? + O(n) = ln Que 1.18. | Solve the recurrence T @) = 8T (0/4) + en? using recursion tree method. T (n) =n+ 2T (n/2) using iteration method. (Given T (1) = 1). AKTU 2021-22, Marks 10PAABCCRTT Bem) _—_ bred wet * : Pi a st tn a : s } | / \\ gee eae ee je ie? 16? 16? 167 ie MAM MIM (cba retoureggng 1 at 1 ' ' ' ternae ) 1 1 1 ' ' 1 ' ' 1 ' Ta) TH) TU) TA) TO) TH) Td) k= log? Ska ght = plat 1,16 = net 162 Tin) = nt 4 on! Tin) = O(n?) Tn) = 20(2) +n 2 = afar). ahem -27(2)+n+n ri. #[21(2)+2]+nene va(s t)enenen =2[21( 2) 2 ]inensna27(2)enenenen Repeat upto k times Mn) = 2 72 =} mh Given: 7( n 3)- 1) Assume, 2. 2 =1, n=2, k=logn Tn) = 2! TO) + kn Tin) = nlogn +n Tin) = O(nlogn) =n.1+nlognDesign and Analysis of. ‘Algorithms 1-15 B (CSAT-Sem-5) PART-3 Sorting and Order Statistic : Shell Sort, Quick Sort. Que 1.14. | Explain shell sort with example. Answer 1. Shell sort isa highly efficient sorting algorithm and is based on insertion sort algorithm and we can code it easily. 2, Itroughly sorts the data first, moving large elements towards one end and small elements towards the other. 3. In shell sort several passes over the data is performed. 4. After the final pass, the data is fully sorted. 5. The shell sort does not sort the data itself; it increases the efficiency of other sorting algorithms. Algorithm : Input: An array a of length n with array elements numbered 0 ton — 1. 1. ine + round (n/2) jei while j 2 ine and a [j—ine] > temp ali] < aj-inc} jej-ine al] < temp 4, ine < round (ine/2.2) For example : 45 | 36| 75 | 20 | 05] 90] 80] 65 | 30] 50] 10] 75] 85 ‘The distance between the elements to be compared is 3. The subfiles generated with the distance of 3 are as follows : Subfile 1 a0] a3) a6] al9] a(12] Subfile 2 all] al4) a(7] (10) Subfile 3 a(2] al5) [8] a(ll) Input to pass 1 with distance = 3 45 | 36 | 75 | 20 | 05 | 90 | 80 | 65 | 30 | 50 J 10 tT tT T a & (a)1-16B (CS/T-Sem-5) Introduct, Output of pass 1 is input to pass 2 and distance = 2 20 | 05 | 30] 45] 10 | 75] 50 | 86 75 | 80 | 65 | 90 | a5 I aa (b) and distance = 1 Output of pass 2 is input to pass 3 To] 05 | 20] 36 | 30 | 45 | 50] 75] 65 al 90] 85] [sales eer ese[eeal (c) Output of pass 3 05 | 10 | 20 | 30 | 36 | 45 50 | 65 | 75 | 75 | 80] 85 | 90 (d) Fig. 1.14.1. Que 1.16. | Describe any one of the following sorting techniques: i, Selection sort ii, Insertion sort OR Write an algorithm for insertion sort. Find the time complexity of Insertion sort in all cases. AKTU 2020. 6 10 Answer i, Selection sort (A): 1. n< length [A] 2 forjelton-1 3. smallest —j 4. foricj+iton 5. ifA [i) 0 and Ali] > key do Ali +1] Alr] 8 returni+1 Example: 1. PARTITION always selects an element q = Alr] as a pivot element around which to partition the subarray A[p ..r]. 2. Asthe procedure runs, the array is partitioned into four (possibly empty) regions. 3, AllentriesinAlp..i] are <(pivot) 4, Allentriesin Ali +1....j- are > (pivot) 5. Alr] = pivot a Ba ©) &=5 [fAlicx STi [é[4[olsi9 is ino] 8 3 iste 1 swap AN OT) fe] fes][=ie 1 & awap Al = O] Fes][icie 1 awap Al Oy VI 8 aap An OOT4 TOTS Ts TsT9Te) we Ali To Ale1-18 B (CS/T-Sem-5) Introdueti 6. PARTITION will return 7 = 5 7. Mer this we will call QUICKSORT (A, 1, 4) QUICKSHORT (A, g, Eat 4 o [3 8 pauls Ga} Cori rss) CeTrTs Crorcoersrrs Corors Ts [ Co Recursively until we get the sorted array. Performance of quicksort : 1. The running time of quicksort depends on the partitioning of th subarrays. 2, Ifthe subarrays are balanced, then quicksort can run as fast as merg sort. 3, Ifthey are unbalanced, then quicksort can run as slowly as insertion sort, 4. Assuming that all inputs are distinct elements, the running time of th algorithm depends on the distribution of splits. Analysis of complexity of Quicksort : + Worst case for the algorithm ? + Partition is always unbalanced -> Sorted array (either way), all element same + What will be the best case for the algorithm ? + Partition is perfectly balanced — pivot nearly divide the array into tw parts Which is more likely ? A. Best case: 4, Ideal situation > partition splits the array evenly in every recursiot Tn) = 2T(n/2) + On) { n n _— a 2 Wi a a nf WA 8 GMS AN FN ON eS Ign 8 n8 8 n/ DS nS WB DB a DAOPN IN PAIN PN PN VN TN (a Ign) B. Worst case: 7 1. When the array is sorted > One side of the partition has element and the other with 0 elements. 1 n6. PARTITION will return g = 5 7. After this we will call QUICKSORT (A, 1, 4) QUICKSHORT (A, 6, 5 feeds Oe ne Tee Cees $13 Ts) a Cer rToTs tT 4 fl (eesti Ea) Recursively until we get the sorted array. Performance of quicksort : 1. The running time of quicksort depends on the partitioning of the subarrays. 2, Ifthe subarrays are balanced, then quicksort.can run as fast as merge sort. 3, Ifthey are unbalanced, then quicksort can run as lowly as insertion sort, 4. Assuming that all inputs are distinct elements, the running time of the algorithm depends on the distribution of splits. Analysis of complexity of Quicksort : ‘© Worst case for the algorithm ? ® Partition is always unbalanced -> Sorted array (either way), all elements same + What will be the best case for the algorithm ? * Partition is perfectly balanced -> pivot nearly divide the array into two parts Which is more likely ? A. Best case: 1. Ideal situation — partition splits the array evenly in every recursion. Tn) = 2Tn/2) + On) —— { n n ae =o E nif Wd ni 4——> 9 LN eS \ ign nf 08 m8 98 0/8 n8 we ne ® vOPN Ty ek AN B. Worst case: 1 1. When the array is sorted > One side of the partition has 2 ~ olement and the other with 0 elements.serena : iS 5) Design and Analysis of Algorithms TB CSTE Sem5) ) = TH) + Tin-1) + An) 2. aeons = Dow a = ODA) a = O(n?) : n iT 7 n-1 my 1 7 n-2 nl i 1 a — n-2 a 5, 1 bo ~ 2 —> 3 an 1 en)? 3. Worst case occurs in quicksort when the input array is sorted, Whereas an array sorted in increasing order will be the best case for insertion sort. C. Average case: L ‘Assuming random input, average-case running time is much closer to O(n Ig n) than O(n?) Consider the following example ; Suppose that partition() always produces a9-to-1 split. ‘The recurrence is thus : Tin) <= T(9n/10) + T(n/0) +n 5. Suppose the split is 1/10: 9/10 Tin) = Tin/10) + T(9r/10) + On) = On log n)! eo pop —- 1 9 login 10 102 " Bion | __—10_ 0 g g 81 aot jo Sn . ins | j09 100 300 100 S 7 PY 2 7X p wX i ie Pn —s a \—> sn 1——> zn O(n Ign)+ 1-20 B (CSIT-Sem-5) Tntry ——— oduct; ee oy ON 1 Merge Sort. 7 TE Que 1.17. | Explain the concept of merge sort with example, Answer Merge sort is a sorting algorithm that uses the idea of divide and conquer, ‘This algorithm divides the array into two halves, sorts them Separately and then merges them. 8. This procedure is recursive, with the base criteria that the m ‘umber of elements in the array is not more than 1, Algorithm : MERGE_SORT (a, p,r) 1. ifper 2. theng Lip +r/2] 3. MERGE-SORT (A, p,q) 4, MERGE-SORT (A, q + 1, r) 5. MERGE (A, p, q,r) MERGE (A, p,q,7r) 1 nyeq-p+l 2 nyer-q 3. Create arrays L (1.. 1+Iand 4. Li) =A [p+i-) endfor 5. forj=1ton, - do RU) =Alg+J/) endfor 6 Liny+1) In, + 1 7. islje 8 fork=ptor do if Lii) < RG) then — Alk] — Ii) init] else Alh] = RU) j=i+l endif endfor 9. exit Example: 10, 25, 16, 5, 35, 48, 8PF Decign and Analysis of Algorithms 1-21 B (CSAT-Sem-5) cign and Analysis of Algorithms | 1, Divide into two halves (3533) 2 Consider the first part:10, 25, 16, 5 again divide into two sub- arrays 5 5, 10, 16, 25 3 Consider the second half : 35, 48, 5 again divide into two sub-arrays 35, 48 8 a 8, 35, 48 4. Merge these two sorted sub-arrays, 5,10, 16, 25) 8, 35, 48 5, 8, 10, 16, 25, 35, 45 ‘This is the sorted array. Que 1.18. | Write merge sort algorithm and sort the following sequence (23, 11, 5, 15, 68, 31, 4, 17) using merge sort. AKTU 2020-21, 2022-23; Marks 10 Answer Merge sort : Refer Q. 1.17, Page 1-20B, Unit-1. Numerical : Given array : (23, 11, 6, 15, 68, 31, 4, 17) 1. Divide into two halves + 11, 6, 1 2 Consider first part : Again divide into Gwo sub arrays 20,11 B18 ‘Afior t ray sorting ; subarrays [11 8,18 \ Morne [ 6.1 Mh °1-32 B (CSTT-Sem-5) Introdueti, vide i 1 &_ Consider the second half: Again divide into two sub arrays 68,31 4,17 After t t setting [31,68 4,17 sub arrays \_ Merge [ 4,17, 31,68 4. Merge these two sorted sub arrays 5,11, 15,23 | 4,17, 31, 68 | 4,5, 11, 15, 17, 23, 31,68 ‘Que 119. | Write an algorithm of merge sort and prove its wors time complexity. ‘Answer | Algorithm of merge sort : Refer Q. 117, Page 1-20B, Unit-1. Te) =1 Tn) = 7(2) + 7(2) an Tin) = ar(2)+n (1.19.1) Substitute 3 in place of n in eq. (1.19.1) 7(3) = or) +5 (1.19.2) ‘Substitute eq. (1.19.2) in eq. (1.19.1) Tin) = afer(2) othe Tin) = 2? 7(3) +2n (1.19.3) tute Substitute 7 in place of nin eq, (1.19.1) 7() ~ 2r(2) +t (1.19.4)Design and Analysis of Algorithms 1-23 B (CBT -Bem-6) = f) 2 Tin) = 2’ fer(2) + “ye Qn Tn) 27( 4) +30 Tn) = atr() +4n Let log, n = log,2 = i log,2 logan =i Tin) = nT\d) +7 log.n Tin) =n+nlog,n Tin) = O(n log,n) Que 1.20. | Determine the best case time complexity of merge sort algorithm. Answer L__ The best case of merge sort occurs when the largest element of one array is smaller than any element in the other array. 2. For this case only n/2 comparisons of array elements are made. 3. Merge sort comparisons are obtained by the recurrence equation of the recursive calls used in merge sort. 4. Asit divides the array into half so the recurrence function is defined as: Tin) = 7(3) +1(2) +n= or(2) +n ...1.20.1) 5. By using variable k to indicate depth of the recursion, we get Tin) = a7(3) +hn --(1.20.2) 6. For the best case there are only n/2.comparisons hence equation (1.20.2) can be written as Tin) = 24( 5) +2 7. At the last level of recursion tree k= log,n 8. So the recurrence function is defined as :‘ w 1-24B (CSAT-Sem-5) Introg ee a w(t). Tn) = 2 r(5t +f logs n n n nT) + g loeyn e glean +n Tin) = O(n logyn) Hence, the best case complexity of merge sort is O(n log,n). Heap Sort. Que 1.21. | Explain heap sort algorithm with its complexity, OR Discuss Max-Heapify and Build-Max-Heap procedures, Answer 1. Heap sort is a comparison based sorting technique based on binary heap data structure, 2. Heapsort finds the largest élement and puts it at the end of array, then the second largest item is found and this process is repeated for all other elements. 3. The general approach of heap sort is as follows : a. From the given array, build the initial max heap. b. Interchange the root (maximum) element with the last element. ¢. Use repetitive downward operation from root node to rebuild the heap of size one less than the starting, 4. Repeat step a and b until there are no more elements. Analysis of heap sort : Complexity of heap sort for all cases is O(n logy). MAX-HEAPIFY (A, i): L icleR iil 2. reright [i] 3. if! Ali] 4. then largest <1 5. else largest A [largest] 7. then largest 45 (False) Then, largest — 4, Similarly for i = 3, 2, 1 we get the following heap tree :1428 B (CS/IT-Sem-5) Now call MAX-HEAPIFY (A, 1) and size = 4 and exchanging ALN © Al2} a5 Thus, sorted array 1.5] 6] 9] 9 [7] 18] 25] 45) Que 1.23. | Explain HEAP SORT on the array. Mlustrate tl operation HEAP SORT on the array A = (6, 14, 3, 26, 2, 10, 20,7, 9)" Answer Heap sort : Refer Q. 1.21, Page 1-24B, Unit-1. Numerical : Originally the given array is : (6, 14, 3, 25, 2, 10, 20, 7, 6] First we call BUILD-MAX-HEAP heap size [A] = 9 © my ® @ O@© © So, i= 4 to 1, call MAX-HEAPIFY (A, i) i.e., first we call MAX-HEAPIFY (A, 4) Az [I] = 7, A [i] =A [4] = 25, A [r] =6 Le left [4] =8 r 25 (False) Then, largest — 4 9<9 and 6 > 25 (False) Then, largest = 4 Ali) oA [4] Now call MAX-HEAPIFY (A, 2) w Similarly for i = 3, 2, 1 we get the following heap tree.Design and Analysis of Algorithms 1-29 R (CS/IT-Sem-5) | wid (wii) (viii) Now i = 9 down to 2, and size = size — 1 and call MAX-HEAPIFY (A, 1) each time. Exchanging A [1] < A [9] @ EX Q O© © © © a1-30 B (CS/IT-Sem-5) Introd, Now call MAX-HEAPIFY (A, 1) we get Now Exchange A [1] and A [8] and size = 9-1-8 a \ © ay oo Gy WH, ® ©@ © OO Oe 6) © 20 [25] Again call MAX-HEAPIFY (A, 1), we get Exchange A (1] and A [7] and size = 8 - 1= 7 6 ® qe OB). Kw, S 06 B S 66 @ 14] 20 Again call MAX-HEAPIFY (A, 1), we get Exchange A [1] and A [6] and now size = 7-1= 6 @® (3) “oe — fe © ©O® Q@ 4} 20 | 25 10 | 1, 25] Again call MAX-HEAPIFY (A, 1) Exchange A [1] and A [5] and now size =6-1=5 @ 2) . © © © @ 14 | 20 | 25 7/10Design and Analysis of Algorithms 1-31 B (CSAT-Sem-5) Again, call MAX-HEAPIFY (A, 1) Exchange A [1] and A [4] and size = 6 2D — 6) | 7 | 210 25 call MAX-HEAPIFY (A, 1) Exchange A [1] and A [3], size =4-3=1 (6) =a : co) 6 14 | 20 | 25 call MAX-HEAPIFY (A, 1) Exchange A [1] and A [2] and size = 3-1=2 GC — g® 3] 66 | 7 | 10] 14] 20[ 25 ‘Thus, sorted array : 2] 3| 6] 6 | 7 | 10] 14] 20] 25 PART-6 Comparison of Sorting Algorithms, Sorting in Linear Time. | Que 1.24. | How will you compare various sorting algorithms ? |ay Worst enee Other noigy implemente, a stable on ws Say where d inte, number of inversion on) Kn?) Yes Ineertion Om On acon sort Shell = Otn log?) No Insertion | No extra sort MEMOTY required | Menze Omlogm | Owlogm| Yes | Merging | Recursive, exe sort, memory require Heap Oinlogn) | Otnlogn) | No Selection Recursive, extra sort memory required Recursive, basa on divide conqy, technique" Quick Otmlogn) | O(n) No Partitioning sort Que 1.25. | Explain the counting sort algorithm. Answer Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Algorithm : Counting Sort(A, B, k) 1. let C{0..k] be a new array 2. fori S eS = BICIAU]] —A ), CAG ecu i j | au | cayn' | [eatin caw-1] 14 3 10 Cci3] — 9 13 2 7 Cl] 6 12 2 7 u 6 4 B13) =6 Cl6) — 14-1= 10 4 12 Bu= Cla) — 12-1211 9 2 7 B(4)=2 Cia] — 5-1-4 IDesign and Analysis of Algorithms Bia= 5 ‘| Bitor=4 i rcrereres Yo | Cla] — 9-1-8 “clo 2-1-1 Cla) 8-1-7 ci 3-1=2 Clo) —1-1=0 9 10 11 12 13 B 3[4]4]5[6 | “Que 129. ] Sort the following array by counting sort | A= (2,5,3, 0, 2, 3, 0,3) Answer A= (2,5,3, 0, 2,3, 0, 3) Step1: = [2]5]3]0[2[s3]o]3 123845678 k = 5 (Largest element in array A) Step2: = [ofofofofoyo 0123465 Step3: c= Po2isfoa 0123465 o, 2 4 XK _ AKT Step4: c=([222]41717 012346 Step5: B= [ofo]2]2[3]3]3[5 12345678 ‘Que 1.30, | What do you mean by stable sort algorithms ? Explain it with suitable example. Answer | | 1. A sorting algorithm is said to be stable if two objects with equal keys | appear in the same order in sorted output as they appear in the input | sorted array, | |1-98B (CS/1T-Sem-5) Introg ey, 2. Astable sort is one wh the i | order of equal items . 3. Some sorting algorithms are stable by nature, such a8 babe insertion sort, merge sort, counting sort ete, on 4 Tet be an array, and let _ (i) @ 36 | 48 | 57 | 86 | 91 Now, call MAX-HEAPIFY (A, 1) Now, exchange A[1] @ A [3], size =4-1=3 Now, call MAX-HEAPIFY (A, 1) Now, exchanging A[1] © A [2], si i. Ej) 25 | 32] 36 | 48] 57] 86] 91 ‘Thus, sorted array : 12 | 25 | 32 | 36 | 48] 57] 86] 91 Que 1.32. | What is stable sorting algorithm ? Which of the sorting algorithms we have seen are stable and which are unstable ? Give name with explanation. AKTU 202: » Marks 10 Answer Stable sorting algorithm : Refer Q. 1.30, Page 1-37B, Unit-1. Stable sorting algorithms : 1. Bubble sort : Stable - It compares adjacent elements and swaps them only if they are out of order. 2. Insertion sort : Stable - It moves each element to its correct position relative to previous elements. 3. Merge sort : Stable - It merges two sorted subarrays while preserving the relative order of equal elements. 4 Counting sort : Stable - It counts occurrences of each element and places them in the output array based on their counts. Unstable sorting algorithms : 1. Selection sort : Unstable - It selects the smallest (or largest) element and swaps it with the element in the current position.1-428 (CSIT-Sem-5) a % partitions the array based ona pivot ele, relative order of equal elements, dly extracts the maximum (or minimy rupting the relative order of eq Quick sort Unstable - It and may not preserve the Heap sort: Unstable - It repeate clement from the heap, potentially elements. Mey e 1.33. | Write a short note on radix sort. wre] aor] Answer 3 & Radix sort is a sorting algorithm which consists of list of integers », words and each has d-digit. We can start sorting on the least significant digit or on the most significan, Hi Of the first pass entire numbers sort on the least significant digit (o, most significant digit) and combine ina array. Then on the second pass, the entire numbers are sorted again on the second least significant digits and combine in an array and so on. RADIX_SORT (4, d) L 2 fori 1toddo use a stable sort to sort array A on digit i // counting sort will do the job ‘The code for radix sort assumes that each element in the n-element array A has d-digits, where digit 1 is the lowest-order digit and dis the highest-order digit. Analysis : 1 The running time depends on the table used as an intermediate sorting algorithm. 2. When each digit is in the range 1 to k, and k is not too large, COUNTING_SORT is the obvious choice. 3, In case of counting sort, each pass over nid-digit numbers takes O(n +h) time. 4. There ared passes, so the total time for radix sort is 6(n +k) time. ‘There are d passes, so the total time for radix sort is @(dn + kd). When dis constant and k = ©(n), the radix sort runs in linear time. For example : This example shows how radix sort operates on seven 3-digit number. Table 1.33.1. Input 15 pass 2"4 pass 3° pass 329 720 720 329 457 365 329 355 657 436 436 436 839 457 839 457 436 657 365 657 720 329 457 720 355 839 657 839 ___Introduet b ston De 4 2a mazoZnalDesign and Anal; 1-43 B (CS/IT-Sem-5) In the table 1.33.1, the first column is the input and the remaining shows the list after successive sorts on increasingly significant digits position, Que 1.34, | Among Merge sort, Insertion sort and quick sort which sorting technique is the hest in worst case. Apply the best one among these algorithms to sort the list Z, X,A, M, P, L, Ein alphabetic order. Answer Merge sort technique is best in worst case because of its time complexity ‘O(n log n). Numerical : Given: E,X, A, M, PL, E Pass 1 : Merge each pair of element to obtain sorted list : E[Xx]A]M PILE After sorting each pair, we get E|X A|M L|P E Pass 2: Merge each pair to obtain the list : A[e] Mx E[L]P Pass $ : Again merge the two sub arrays to obtain the list : A] ®] © [LC] Plx ‘VERY IMPORTANT QUESTIONS Following questions are very important. These questions may be asked in your SESSIONALS as well as UNIVERSITY EXAMINATION, Q.1. What do you mean by algorithm ? Write the characteristics of algorithm. Ane, Refer Q. 1.1. Q2. What do you understand by asymptotic notations ? Describe important types of asymptotic notations. Ang; Refer Q. 1.3, Q.3. Solve the following recurrence relation : i, Tin)=T(n-1) +n4 ii, T(n) = T (n/4) + T (n/2) +n? ans; Refer Q. 1.12.i 4a BC IS/IT-Sem-5) Introd, $reg Q.4, Describe any one of the following sorting technigue, i, Selection sort fi, Insertion sort Ans, Refer Q. 1.15. Q.5. Explain the concepts of quick sort method and anal complexity with suitable example. Vee iy Ang, Refer Q. 1.16, 6. Explain the concept of merge sort with example, : Refer Q. 1.17. . Explain heap sort alj An. Q7. gorithm with its complexity, Ans: Refer Q. 1.21. Q.8. Ans. . Explain the counting sort algorithm. Refer Q. 1.25. ©©0Advanced Data Structure CONTENTS a Part-1 : Red-Black Trees .... 2-2B to 2-20B | Part-2 : B-Trees ...2-20B to 2-27B Part-3 : Binomial He: 2-27B to 2-34B Part-4 : Fibonacci Heaps | (parts : Tries, Skip List .. 2-1 B(CS/IT-Sem-5)Advanced Data gy, Str fear] Red-Black Trees. 2-2 B(CS/IT-Sem-5) | Que 2.1, | Define a red-black tree with its properties, the insertion operation in a red-black tree. Answer Red-black tree : Ared-black tree is a binary tre attribute, either red or black. Expy neers where each node has colour as an e, th Iisa self-balancing Binary Search Tree (jy where every node follows following properties : Every node is either red or black. ‘The root is black, Every leaf (NIL) is black. Ifa node is red, then both its children are black. For each node, all paths from the node to descendent leave contain y same number of black nodes. Insertion : i We begin by adding the node as we do in asimple binary search t, and colouring it red. RB-INSERT(T, z) Lo yeniliy x < root [T] while x #nil (T] doyex if keylz] < key (x] then x < left [x] else x — right [x] pkl ) ROY a) Cano 0 O G4) da B 0) Fig. 2. Que 2.2. | What are the advantages of red-black tree over binary search tree ? Write algorithms to insert a key in a red-black tree insert the following sequence of information in an empty red-black tree 1, 2,3, 4,5, 5. Answer | Advantages of RB-tree over binary search tree : so 1. The main advantage of red-black trees over AVL trees is that a single top-down pass may be used in both insertion and deletion operations. 2. Red-black trees are self-balancing while on the other hand, simple binary search trees are unbalanced, It is particularly useful when inserts and/or deletes are relatively frequent Time complexity of red-black tree is O(log n) while on the other hand, a simple BST has time complexity of O(n). Algorithm to insert a key in a red-black tree : Refer Q. 2.1, Page 2-2B, Unit-2. Numerical : Insert 1, 2, 3, 4, Sin an initially empty RB tree, Insert: @?. 3 Insert 2: R4 2-6 B(CS/T-Bem-6) Advanced Data Struct, B Inert: Q) = b Cane dy Cane 1 Innort 41 (2) As root is B alway Black @ control black and exist, Insert 6; Case 3 "3 Fig. 2.2.1, Que 2.3, Explain. ved-black tree. Show Steps of inserting the keys 41,38, 31,12, 19,8 into initially empty red-black tree, OR I What is red-black tree ? Write an algorithm to insert a node in an empty red-black tree explain with suitable example. Anewer Red-black tree. ‘and insertion algorithm : Refer Q.2.1, Page 2-28, Unit-2. Insert 41, 38, 31, 19, 19, 8is aRB Tree, Insert 41; Insert 38; 6 Insert 31;Design and Analysis of Algorithms 2-7B (CS/IT-Sem-5) R a@) Case 3 RV — color Pa) — B ‘Piz)Sy color P(P(z)) —R @? RR on P(P(z)) Insert 12: Case 1 color P(2)— B r & @* color 4B color P(P(2) — R As zis Root color move z to P(P(2)) it black exist Case 2 Insert 8: As P(2) is now black Que 2. Insert the following elements using the property of RB 61, 58, 51, 32, 39, 29 AKTU 2023-24, Marks 10 Answer 61, 58, 51, 32, 39, 29 B Insert 61: | | | | | eeON 28B (CSAT-Som-5) Advanced ey Se seamen Aly Insert 68: Shy Insert me Ci cae SS A \ ® ‘ase ng ay ©. SesDesign and Anal; 8 of Algorithms 2-9B (CSAT-Sem-5) Que 25. Write an algorithm for insertion of key in the Red-Black Tree. Discuss the various cases for insertion of key in red-black tree for given sequence of key in an empty red-black tree 5, 16, 22, 25, 2, 10, 18,30, 50, 12, 1. AKTU 2020-21, Marks 10 Answer Algorithm for insertion, various cases for insertion : Refer Q. 2.1, Page 2-2B, Unit-2. Various cases : Insert 5: Insert 16 : P() = Black ‘No change Insert 22: B _ P(g) = Red 2’s uncle Pwr) G) a ifBlack zis Tet of Pi) @P lor Pla R R P(2) GQ) Change color P(x) « Black Ry 2) R PP[zil = Red 2) Left rotate PQ) is Red and 2's uncle is Red i.e., ¥ (16) B Case 1 B B os Color P@)< Black (©) %23) R Color 2’s uncle « Black Insert 10, 182-10 B (CS/IT-Sem-5) Insert 301 P(x) is Red and z's uncle is Red i.e., ¥ Case 1 —— Color P(x) & Black Color 2’s uncle Black B, P(z) = Red z’s uncle if Black z is left of P(z) Case3 — Change color P(z) < Black P[P{z]] = Red Left rotate Insert 12, 1: Que 2.6. | How to remove ano. de from RB- i Cae coe B-tree ? Discuss all cases Answer To remove a node from RB-tre -tree RB-DELI See RE DELETE , after splitting out oe ae ie procedure RB- 1E-FIXUP that changes le, it calls an auxiliary to restore the red-black properties, colours and performs rotations RB-DELETE(T, 2) 1. if left{z) = nill7] or rightle) = nilt7) 2 theny -2Pag pesign and Anal ais of Algorithms 2-11 B (CS/T-Sem-5) a eres" 1 atten] nill7] 5 then x < leftly! 6 elsex < rightly] 7. ple pb! itp) =nill7] 9. then root 7] <— x yo, elseify=leftipbyll 1 then leftiplyl] case 1 6 colour(p[x]] — RED = case 1 1 LEFT-ROTATE(T, plx]) => case 1 8 w < right([plel] = case 1 9. if colourfleft{w}] = BLACK and colour[right{w]] = BLACK 10. then colour{w] < RED’ => case 2 u. x case 2 2 else if colour{right[w]] = BLACK 13, then colourfleft{w}] <- BLACK = case 3 4. colour{w] « RED = case 3 16. RIGHT-ROTATE(T, w) => case 3 16. w < right[p[x]) => case 3 7. colourlw] < colour{p[x]] = case 4 18. colour[p[x]] <- BLACK => case 42-12B (CS/IT-Sem-5) Advanced Data g 19. 20. 21, 22, 23. colourlright{wl] — BLACK LEFT-ROTATE(T, plx)) x root(T] ee =e else (same as then clause with “right” and “left exchanges colour{x] — BLACK Cases of RB-tree for deletion : Case 1: x’s sibling w is red: a 2. 1. 2: 3 It occurs when node w the sibling of node x, is red. Since w must have black children, we can switch the colours of ,, ang p\x] and then perform a left-rotation on p[x] without violating any of red-black properties. i ' The new sibling ofx, which is one ofw’s children prior to the rotation 4 now black, thus we have converted case 1 into case 2, 3 or 4. Case 2, 3 and 4 occur when node w is black. They are distinguisheg by colours of w’s children. Fig. 2.6.1. Case 2: x’s sibling w is black, and bot! 'h of w’s children are black: black. Sincew is also black, we take one bl jack = with only one black and leaving w red, For removing one black from x and w, we add an extra bl which was originally either redor black ara Mack to ple}, Both of w’s children are of both x and w, leaving We do so by repeating the while loop with Pls] as the new node x If we enter in ease 2 through ease 1. the nee i : treater in ease 2 thr node x is red and black, The value c of the colour attribute of loop terminates when it tests the loo, the new node then coloured black. P condition,2-13 B (CSAT-Sem-5) Fig. 2.6.2. 6) :x’s sibling w is black, w’s left child is red, and w’s right child 1. Case 3 occurs when w is black, its left child is red and its right child is black. 2. We can switch the colours of w and its left child left{w] and then perform a right rotation on w without violating any of the red-black properties, the new sibling w of x is a black node with a red right child and thus we have transformed case 3 into case 4. (a) Fig. 2.6.3. Case 4 : 2’s sibling w is black, and w’s right child is red: 1. When node 2’s sibling w is black and w’s right child is red. 2. By making some colour changes and performing a left rotation on plz], we can remove the extra black on x, making it singly black, without violating any of the red-black properties.pruetre 2-14 B (CS/AIT-Sem-5) ‘Advanced pate rr seeeeeneee Serer eee ty in omP Que 2.7. | Insert the nodes 15, 13, 12, 16, 1% 23, 5 8 n redeblack tree and delete in the reverse order of incor tio 5 ¢ for 7 -plack t Discuss the various cases for insertion of Key. in wets, 12, 16, 19 23, given sequence of key in an empty red-black (75° 7 58). ARTO 2021-22 Maris Ani swer wee : Refer @ 2, Various cases for insertion of key in red-black # Page 2-2B, Unit-2. Insertion : Insert 15: @ Insert 16: B (a Case 3 (a3) aaa 4s G B ge @ R RF W® 7 BG) 7 R Insert 19: B BDesign and Analysis of Algorithms 2-15 B(CS/AT-Sem-5) Insert 23: B @ Q ‘o_o "Oa" GC @, S @ B Insert 5: Insert 8: Deletions: Delete8:Delete 12: Delete 13: Delete 15: No tree Que 2.8. | Describe the properties of red. black tree, red-black tree with n internal nodes has height at Show the OR most 2 log (n +1).Design and Analysis of Algorithme 2N7TWICBAT-Bem-5) Prove the height # of a red-black (ree with n internal nodes ia not greater than 2 log (n #1), Answer Properties of red-black (ree t Refer Q. 2.1, Page 2-2B, Unit-2 Proof: 1. By property 5 of RB-tree, every root-to-leaf path in the tree has the same number of black nodes, let this number be 2. 2. Sothere are no leaves in this tree at depth less than B, which means the tree has at least as many internal nodes as a complete binary tree of height B. Therefore, n < 2° —1. This implies B < log (n + 1). 4. By property 4 of RB-tree, at most every other node on a root-to-leaf path is red, therefore, h < 2B. Putting these together, we have hs 2login+1). Que 2.9. | Discuss the various cases for insertion of key in red- black tree for given sequence of key in an empty red-black tree- {15, 13, 12, 16, 19, 23, 5, 8). Also show that a red-black tree with n internal nodes has height at most 2lg(n + 1). AKTU 2022-23, Marks 10 Answer Various cases : B Insert 15: p(z) = Black Insert 18 No change Insert 12: B p(z)=Redz's uncle R29 if Black zis (Bo ‘elk of pra) Case 3 =a Change color p(z) — Black plplz|] = Red Right rotate