SYLLABUS Design & Analysis of Algorithms (CS501PC) Unit - I (Chapters - 1,2) Introduction : Algorithm definition, Algorithm specfication, Performance analysis - Space complexity. Time complexity, Randomized algorithms. Divide and Conquer : General method, Applications - Binary search, Merge sort, Quick sort, Strassen's ‘matrix multiplication Unit - II (Chapters - 3,6) Disjoint set operations, Union and find algorithms. AND/OR graphs, Connected components, and Spanning trees, Bi-connected components, Backtracking -general method, applications. The &-queen problem, sum of subsets problem, Graph coloring, Hamiltonian cycles. Unit - III (Chapter - 4) Greedy Method : General method, Applications - Knapsack problem, Job sequencing with deadlines, ‘Minimum cost spanning trees, Single source shortest path problem. Unit - IV (Chapter - 5) Dynamic Programming : General method, Applications - Chained matrix multiplication, All pairs shortest path problem, Optimal binary search trees, 0/1 Knapsack problem, Rellabiltiy design Travelling salesperson problem, Unit - V (Chapters - 7,8) Branch and Bound : General method, Applications - 0/1 Knapsack problem - LC branch and bound solution, FIFO branch and bound solution, Travelling salesperson problem, NP-Hard and NP-Complete Problems : Basic concepts, Non-deterministic algorithms, NP-hard and NP-complete classes, Cook's theorem, : oy ‘Seamed nth CamScannerTABLE OF CONTENTS Chapter-1 Introduction _—(1 - 1) to (1 - 19) 1.1 Algorithm, 1.2. Pseudo Code for Expressing Algorithms. . 1.3. Performance Analysis ... 1.4 Asymptotic Notation 15. Probabilistic Analysis, 1.6 Amortized Complexity 1.7, Recurrence Relation Chapter-2 Divide and Conquer (2-1) to (2-22) 2.1 General Method...........ceceeeeseee eee 2-1 2.2 Binary Search . 23° Quick Sort .. 2.4 Merge Sort. 2.5. Strassen’s Matrix Multiplication........... 2-15 2.6 More examples on Divide and Conquer .....2-17 », Multiple Choice Questions with Answers ..2- 19 Fill in the Blanks with Answers 2-21 Chapter-3 Searching and Traversal Techniques — (3-4) to (3-29) 3.1 Efficient Non-Recursive Binary Tree Traversal Algorithms, , 3.2. Disjoint Set Operations .. 3.3. Union and Find Algorithms......0........ 3-7 3.4 Spanning Trees .. 3.5. Graph Traversals . ww) 3.6 ANDIOR Graphs. 37 38 39 Multiple Choice Questions with Answers ..3-29 Fill in the Blanks with Answers Chapter-4 Greedy Method (4-1) to (4-18) 4.1 General Method. . o4el 42 Job Sequencing with Deadlines............. 43 43° The 0/1 Knapsack Problem .............4.4 4-5 4.4 Minimum Cost Spanning Trees. 4.5. Single Source Shortest Path Problem. ‘Multiple Choice Questions with Answers ..4 - 17 Fillin the Blanks with Answers. 4-17 Chapter-§ Dynamic Programming (8-1) to (5-36) Sed 5.1 General Method. . 5.2. Multistage Graphs .. 5.3 Optimal Binary Search Tree 5.4 The 0/1 Knapsack Probler 5.5 All Pairs Shortest Path Problem .. 5.6 Travelling Salesperson Problem .. 31 ‘Multiple Choice Questions with Answers Fill in the Blanks with Answers... ‘Seamed nth CamScannerChapter-6 Backtracking (6 - 1) to (6 - 16) 6.1 General Method. . 62 The n-queen Problem... 6.3. Sum of Subsets Problem . . 6.4 Graph Coloring .. 6.5 Hamiltonian Cycles... Chapter-7 Branch and Bound (7-1) to (7 - 23) 7.1 General Method . adel 7.2 LC Search .. w), 73. Bounding 7.4. Travelling Salesperson Problem .......++0447-5 7.5. The O/1 Knapsack Problem... ..+ss0eeee0e7- 18 7.6 FIFO and LC Branch and Bound Solution . ..7- 22 Chapter-8 NP-Hard and NP-Complete Problems (8-1) to (8 - 12) 8.1 Basic Concepts .... vee B-d 8.2. Non-deterministic Algorithms. ..... 8.3 NP-hard and NP-complete Classes 8.4. NP-hard Problems . . 8.5 Cook’s Theorem .+.+++eeeseeeeeerseeeeee 8-8 ‘Multiple Choice Questions with Answers... 8 - 10 Fill in the Blanks with Answers = 8-12 Solved JNTU Question Papers (S - 1) to (S - 26) ‘Seamed nth CamScannerINTRODUCTION 1.1 Algorithm Q.1 What is algorithm ? ‘Ans : Definition of algorithm : The algorithm is defined as a collection of unambiguous instructions eccurting in some specific sequence and such an algorithm should produce output for given set of input in finite amount of time. Q2 Define algorithm = and characteristics of the algorithm. ES INTU : Part B, March-06, Nov.-06, Marks 8] Ans, : Algorithm ~ Refer Q.1. Characteristics : Algorithm should posses following Properties - D) Input - The input of zero or more’ number of quantities should be given to the algorithm, Output - The algorithm should produce at least one quantity, as an output. Definiteness - Each instruction in algorithm should be specific and unambiguous. Finiteness - The algorithm should be finite, That means after finite number of steps it should terminate. Effectiveness - Every step of algorithm should be feasible. In other words, every step of algorithm should be such that it can be carried out by pen and pencil. Q.3 Differentiate between profiling and debugging. ESr[INTU : Part B, May-08, Marks 6) describe the 2 3 4 5) Ans: * Debugging is a technique in which a sample set of data is tested to see whether faulty results occur or not. If any faulty result occurs then those ‘results are corrected. # But in debugging technique only presence of error is pointed out. Any hidden error can not be identified. Thus in debugging we cannot verify correctness of output on sample data. Hence profiling concept is introduced. © Profiling or performance measurement is the process of executing a correct program on a sample set of data. Then the time and space required by the program to execute is measured. 2 Pseudo Code for Expressing Algorithms Q4 Write a recursive algorithm that converts a string of numerals to an integer, for example "34567" to 34567. CS [INTU : Part B, Dec.-11, Marks 7] Ans. : Algorithm StrToNum(char *c, double *i) /fiitially {is initialised to 0 if ("e == NO" || lisdigit(*c)) then return "i; WSF tc. retum StrToNum (c + 4, i); + Q65 Write a recursive algorithm that calculates and returns the length of a list. GP [INTU : Part B, Dec.-11, Marks 8] Ans.: Algorithm stringlen( char *p1,int *count) { /Kaitially count is intialised to 0 if(*p1 == \0) then retum "count; “count=*count+1; retum stringlen (p1+1,count); /nally the count contains the length of the string // main procedure simply print the value of count } rs asa ‘Seamed nth CamScanner| | | | | } | Design and Analysis of Algorithms, Q.6 Write an algorithm to evaluate a polynomial using Honor's rule. T&F[INTU : Part B, May-09, Marks 8, Dec.-11, Marks 7] Ans.: ‘Algorithm Poly_Honor(n.x) { /fnitialize array a by coefficients of polynomial int kom sum «0; for (ik; 1>0; -) { sum < (sum+alil)"=; } sum © sum+al0|; Write(sum)://evaluated result } Q7 Write an algorithm in pseudocode to count the number of capital letters in a file of text. How many comparisons does it do ? What Is fewest number of increments it might do ? What is the largest number ? Assume that N. is number of characters in a file. EP [ANTU : Part April-t1, Marks 15] Ans. Algorithm Count, Capitals { FILE "fp; Write(‘Enter flé name: sgets( filename ); fp = fopent filename, "**); if ( fp == NULL ) then { Write(‘Cannot open for reading "); exit(1); /* terminate program */ + ¢ = gete( fp); while ( cl= EOF) do { A) AND (c<: eo = gete (fp); } felose( ip ): | Write('Capital Letters in the file are "+count ); ) Introduction: If there are N number of characters in the file then, N comparisons are needed to obtain the count for capital letters. Fewest Number - If the file-is sorted and searched for the capital letter using binary search technique then in logN number of comparisons the capital letters can be obtained. Largest Number - Comparing each letter for ensuring capital or not gives largest number of comparisons. It takes N number of comparisons. 1.2 Performance Analysis Q8 Define time complexity. EP LINTU : Part A, Nov.-16, Marks 2] ‘Ans. : Time complexity is the amount of time taken by the computer to execute an algorithm. It is denoted by the asymptotic notations Q9 Define space complexity. CGF [INTU = Part A, Nov.-16, Marks 2] ‘Ans.: Space complexity is the amount of space required by an algorithm to execute. It is denoted by the asymptotic notation. Q.10° What are the two factors used for defining the space complexity ? CS°[JNTU : Part A, Marks 2] ‘Ans, : To compute the space complexity we use two factors : constant and instance characteristics. The space requirement S(p) can be given as : Sp) = C+Sp where C is a constant i.e. fixed part and it denotes the space of inputs and outputs. This space is an amount of space taken by instruction, variables and identifiers. And Sp is a space dependent upon instance characteristics. This is a variable part whose space requirement depends ‘on particular .problem instance. Q.11 Describe the performance analysis in detail. E&P [INTU : Part B, May-08, May-12, Marks 8] ‘Ans. : The efficiency of an algorithm can be decided by measuring the performance of an algorithm. We SF rectnucat Pus.icarions™. An up thrust for knowledge es ‘Seamed nth CamScannerDesign and Analysis of Algorithms a can measure the performance of an algorithm by computing two factors. 1, Amount of time required by an algorithm to execute. . 2. Amount of storage required by an algorithm. This is popularly known as time complexity and space complexity of an algorithm. ol Se® Fig. Q.11.1 Analysis of algorithms Q42 Why it is difficult to compute the time complexity in terms of physically clocked time ? Ans. : It is difficult to compute the time complexity in terms of physically clocked time, because in multiuser system, executing time depends on many factors such as - System load ‘+ Number of other programs running ‘Instruction set used * Speed of underlying hardware. ‘The time complexity is therefore given in terms of frequency count. Frequency count is a count denoting number of times of execution of statement, Q.43 What is frequency count ? USP [INTU : Part A, Marks 3] Ans. : Frequency count is a count denoting number of times of execution of statement. Consider following code for counting the frequency count. ‘void fun() { int a; printf("%d" } For each statement except declaration statement, the frequency count will be - void fun() { int a; a=10; ‘The frequency count of above program is 2. Q.14 Obtain the frequency count for the following i++; }while(i<=n) Ans. : Statement Frequency count 5 while(ic=n) 5 ‘Total | 22 Q5 What is the smallest value of n such that an algorithm whose running time is 100 n?"runs faster than the algorithm whose running time is 2" on the same machine ? C&P [NTU + Part B, Marks 5] Ans.: Finding the smallest value of n for an algorithm with 100n? running time which runs faster than algorithm with 2" running time means we have to obtain value of n such that 100n? < 2°. If n= 10 then FP! TECHNICAL PUBLICATIONS". An up thrust for knowledge cont ‘Seamed wth Camscanner109(10)? + 21° 10000 > 1024 It n= 12 then 100(12)? 2 212 14400 > 4096 If n too)? 2 2 19600 > 16384 If n = 16 then sone)? £ 26 25600 < 65536 < Found If n= 15 then 100(15)? = 275 22500 < 32768 As n= 15 the 2" exceeds 100n?. Hence n = 15, is the smallest value satisfying the given condition. Q.16 Arrange following rate of growth in increasing order. 2", nlogn, n?, 1, n, logn, nl, n® (1GP [JNTU : Part A, Marks 2) Ans. | logn, n, nlogn, n?, n, 2, nt Q.17 Reorder the following complexity from smallest to largest 1) nlog,(n), n + n? + n°, 24, sart(n) ii) n?, 2, nlog,(n), log,(n), n> Ii) nlog (n), nf, niflog n, (n?—n + 1) iv) nl, 2*, (2 +1)!, 2%, ne, nbe™ GINTU + Part A, Marks 3] Ans. i) sqrt(n), n logy n, n+n?+n°, 24 fi) log n,n log n, n¢, n°, 2" p 2 iii) n log n, oan’ x? —n +1), n® iv) 96, 2", nt, (n+ 1)!, 2%, n™ {PF recsmen pusucaToNs"- Ann mtr owt 1.4 Asymptotic Notation Q.18 List out the reasons for the difficulties that one faces while determining lower bound. (GP [INTU : Part A, Nov.-16, Marks 2] ‘Ans. : A lower bound of a problem is the least time ‘complexity required for any algorithm which can be used to solve. this problem. The problem with computing lower bound is that - The lower bound for a problem is not unique. For example - 2(1), 2 (n), Q (n log n) are all lower bounds for sorting. Due to this - i) We always try to find higher lower bound ii) We always try to find better algorithm Q.49 Define time complexity. Describe different notations used to represent these complexities. GF [NTU : Part B, May-09,13, Marks 10] ‘Ans. : Time complexity - Refer Q. 8. Asymptotic notation is a shorthand way to represent the time complexity. Using. asymptotic notations we can give: time complexity as “fastest possible”, “slowest possible” or “average time”. ‘Various notations such as @, © and O used are called asymptotic notions. 1. Big oh notation The Big oh notation is denoted by 'O’. It is a method of ‘representing the upper bound of algorithm's running time. Using big oh notation we can give longest amount of time taken by the algorithm to complete, Definition Let f(n) and g(n) be two non-negative functions. Flo) Flo) « ofan) Fig. 0.19.4 ‘Seamed nth CamScannerAnalysis of Algorithms Let ng and constant ¢ are two integers such that ng denotes some value of input and n > no. Similarly ¢ is some constant such that c > 0, We can write f(n)s.c*g(n) then f(n) is big oh of g(n). It is also denoted as f(n) € © (g(n)). In other words f(n) is less than g(n) if g(n) is multiple of some constant c. For Example : If f(n) = 2n + 2 and g(n) = n? then. {(a) = O (g(a) for n> 2 2. Omega notation Omega notation is denoted by '®' This notation is used to represent the lower bound of algorithm's running time. Using omega notation we can denote shortest amount of time taken by algorithm. Definition A function {(n) is said to be in Q (g(n) if f(n) is bounded below by some positive constant multiple of g(n) such that f(n) 2 c* gin) For alln>ng Fo) Fin)e ain) Fig. 0.19.2 Wilt is denoted as f(n) €Q (g(n)). Following graph lustrates the curve for 2 notation. consider f(n) = 2n? +5 and g(n) = 7n n>3 we get f(a) > ¢* g(a). It can be represented as 2n? +5 € Q(n) 3. @ notation The theta notation is denoted by @. By this method the running time is between upper bound and lower i Introduction Definition Let f(n) and g(n) be two non negative functions There are two positive constants namely c, and c, such that cy S$ g(n) Scp a(n) ‘aa cain Fede O(n) Fig. 0.19.3 ‘Then we can say that fn) € 0 (g(n)) If f(a) = 2n +8 and g(n) = 7n. where n22 Similarly f(n) = 2n+8 s(n) = 7m ie. Sn < 2n+8<% = Forn22 Here qs and ¢2 =7 with ny =2. » Then fn) = O(n) The theta notation is more precise with both big oh and omega notation. Q20 Compare Big-oh notation notation. Illustrate with an example. SGP[INTU : Part B, May-12, Marks 7] Ans, : Big- Oh notation ~ Refer Q.19. and _Little-oh Little oh notation - The little Oh is denoted as o. It is defined as : Let, f(n) and g(n) be the non negative functions then such that f(n) = o(g(n)) i f of n is little Oh of g of {(n) = o(g(n)) if and only if f(n) = o(g(n)) and f(a) #8 (gn) bound. Q.21 Find Big-oh notation and Little-oh notation for f(n) = 7n® + 50n* + 200. GP LINTU : Part B, May-12, Marks 8] ‘ JF recroucas rus.icarions”- Anup trust for knonodge @xconit a ‘Seamed nth CamScanner‘Design and Analysis of Algorithnis 16 _Introduction ‘Ans. : Let f(n) = 7n? + 50n? + 200 | Patan oa Se == 3 instance of elements f(a) < 300 n | eo For n larger than some crossing point. Say n> 10. 300+ n? < c#nt an < a? 3= ¢ For calculating little oh we have to pick up n such that f(n) < ¢ + n‘ is true. So pick up nie. max(10.2). Hence for given f(n) = 0 (n'). The big-oh notation f(n) = O(n). Q.22 What are the basic efficiency classes ? Ans. : The classification of different order of growth is as follows - Name of Order Description Example efficiency class of growth Constant 1 | As input size | Scanning | grows the | array | we get larger elements. running time. Jogn | When we get Performing logarithmic binary search | running time | operation. then it is sure that the algorithm | does not | consider all its input | rather the | problem is | divided into | | | smal pc | on each | eration, Linear a Be: |The raring | Performing | | sequential | | ee | search | | depends on | operation. | [the input rs [sen | considered | sort or quick for the list of | sort | | < | input is Cubic Exponential Factorial When an | Generating all algorithm is | permutations. ‘computing, all the permutations then this type of efficiency | occurs. Table Q.22.1 Basic asymptotic efficiency classes Q.23 Write the non-recursive algorithm for finding the Fibonacci sequence and derive its time ‘complexity. EG [INTU : Part B, Sept.-08,-May-09, Marks 10, Nov.-16, Marks 5] Ans. 1. Algorithm Fibbo(n) 24 3, //Problem Description : This problem is to compute 4, //fbonacci sequence using non recursive method 5. //Input : Integer n for length of Fibbenacci sequence "FF recimicat PuaLicanions”- An op thrust for knowledge coy ‘Seamed nth CamScannerDesign and Analysis 6. //Output: The Fibonaccl number present at n location 7. tf (a<=1) then 8 Write(n); 9. else 10.{ Mf 5 12, for(i=2 to n) do 13 a fente; 15, 16} 17. Write(p; 18. } 19.) Analysis Jn above algorithm, basic operation is computing of next value in the Fibonacci sequence. Frequency count “ane By neglecting the constants, and by considering the order of magnitude we can denote the complexity of the above algorithm as O(n). Q.24 Show that f(a) + g(n) = O(n) where f(n) = 3 nt n+ 4 and g(n) = nlogn + 5. BRP [INTU : Part B, Sept.-08, May-09, Marks 8] ‘Ans. : This problem is for defining big oh notation. By definition big oh notation. We should have, f(n) < c# g(n) where: is a constant. For the given problem we have to prove, f(n) + g(n) < O(n). We will select some positive constant c and value of n = Antroduction Ifn=2 then LHS. = f(n) + g(n) = @n?-n+4)+ (nlogyn+'5) = (2)? 24 4)+ @log24+5) (12 -2+4)+(2+5) . =a RHS. = n? = cen? = 6* (2)? where c is a constant with value 6. = 684 = ‘That is LHS. < RHS. Hence f(n) + g(n) tor ‘Seamed nth CamScannerIntroduction Design and g(a) = n° = @) = 27 . If we choose ¢ = 3 then c# g(n) = 3# 27 = aL Thus we get f(a) = c# gin). Hence fn) = 2 (Gn) Now we have to prove that f(n) # © (g(n)). ie, ¢,*g(n) S$ fin) < cy * g(n) is not true, Ifn=3,c, =2andc, = 3 then. 2#(3)5 $12)? +6(3) < 3«(3)3 2827 $6481. f(n) # (gin) Hence {(n) = ©(g(n)) is proved. Q.26 Show that —_fx(n)x fo(n) = O(ay(n)x go(n)) where fy(n) = O(g3(n)) and fa(n) =O (ga(n)). TS[INTU : Part B, Sept-08, Marks 6] Ans. : Let f(n)€O (g(n)) when f(n) $c; * g(n) is true. We assume fy(n) S cy * (g;(n))- Similarly,t(n) < ¢2 * p(n). Let, 3 = cy *¢2 where cy is a new constant. Hence we can write the functions as Aya) (a) = 1 * Gr(A))Xc2 * (Balm) Fy(n)x fy(n) = ¢1 *¢2 (B1(M)x Bai) f,(n)x (n) = ¢3 * g1((n)x B20) cn (Q.26.1) If we assume : f,(0)x y(n) = f(n) and 81(n)x go(n) = gin) then f(n) = c3 + g(n). f(@) = O(g(n)). Hence we can say about eqution (Q.26.1) as 0 (Bi ")x g2(n)). Q.27 Show that f(n)=4n?-64n+ 288 = 2(n)?, EGP [NTU : Part B, May-09, Marks 6] Ans.: The given function f(n)= (g(n)) only when {(n) 2c (g(n)). Where c is some positive constant. £y(n)x fo(n) = "IF recnucat PusLicarions”- An up thrust for knowiodgo Let, Assume, LHS. = f(n) RHS. = c* g(n) LHS. ie. f(n) f(n) = 4n? -64n+ 288 n = Landc=5 then, = 4n? ~ 64n+ 288 = 4(1)? - 64(1) + 288 = 4-644 288 = 28 = 5+ (ny? = 5 (1)? =5 > RHS. 2 c*g(n) Hence f(n) = Q(g(n)) is proved. Q.28 Show that n° logn is (n°). SG [INTU : Part B, Sept.-08, Marks 6] ‘Ans. : To prove f(n) = @ (g(n)) we have to prove two cases Case: fin) = Q(g(n)) fn) # © (gin) Let us prove both of these cases - Case 2: Case 1: LHS. = £(n) = n3 logn Assume n= 4then = (43 log 4 = 6x2 = 128 RHS. = c *g(n) =4 and c#1 RHS. = 1+ (03) = 1+ (4)3 = 64 LHS. = RHS. ‘Seamed nth CamScannerpy _ 7 ie, f(n) 2 c#g(n) we can say, For example consider an array af ] f(n) = 2 gin) Case 2: To prove f(n) # © (g(n)) we have to prove - that, cy * 8(n) § f{n) scp * g(n) is not true. me ans We will form temp array as, The f(a) = nSlogn and gin) = n°. ae Assume n= 4, ¢, =3, ¢ =4, then of [0 ° 323043 ifs: on sorting i cy* g(a) = 3*n 923943 = 192 210 ae eyasieen 3 3 f(n) = in tog : ; = 43 (log 4) 5 5 Om temp temp Value index Value index cp *g(n) = den? : of On Deleting = 4? 1 nee aps fos ® : etersiep2f 3} = 256 3 |= Delete {10 [0 <1s< 4 ie, 192 < 128 < 256 is not true. 7 Dasa Hence * g(n) < f(n) < 256 is not true. temp ‘temp s f(a) = © (g(n)) is not true. Now sorting temp based on index. % . Value index ) Hence fin) = o(g(n)) is proved ofsaozhes aan rc Transfer alee 2.29 Given an array of n elements, (possibly with oleae Tearaya some of the elements are duplicates). Write an ~ aay 2) algorithm to remove all duplicates from the array afz [es af 2 in time O(n log n). > 5S [INTU : Part B, April, Marks 15] temp ‘Ans. : We will consider an array af } in which all the ) elements with duplicates are stored. The logic to remove duplicates is as follows - Thus we get an array b without duplicates, Note that the order of elements in original array is maintained. ‘The rithm: - Store all the elements in templ J array. The temp ws slgocithn can be so given below Algorithm remove_duplicates (int a1...n]) array will have two fields index and value. ; 1. Now sort the array temp based on value, /f Magu: An axay of | ith funtiosnes 2. Remove duplicate elements (for searching // output : An array b [ ] without duplicates duplicates just see the adjacent element in array). Array temp [1 ... n] with two fields. ‘The duplicate with greater index value will be for (i= 1 ton) do removed. { 3. Now sort the array temp based on index. tompli].value = ali); ‘Transfer the contents of temp array to array b. Z j tompfil.index = 1; 1 rectnucaL PUBLICATIONS". Anup ht or krone ‘Seamed nth CamScannerDesign and Analysis of Algorithms sort temp array based on value, Remove duplicates with higher index. Sort tomp array based on index. ‘Transfer contents of array temp to b. Display array b, } The two sortings take O(n logn) time. Removing of duplicates takes O(n) time. Hence this algorithm takes O(n logn) time. Q30 Hf % (n) = O(f(n)) and 7 (n)=O(g(n)) { | } then show that Tj (n) +Tp (n) = O(max(f(n), g(n)). NES'[INTU : Part B, May-08, Marks 8] | i | t | ‘Ans. : Let there be some constant c, such that T(n) <$cg)() — forn2n,_... (Q30.1) Similarly there will be some constant cp Such that T, (m) $ cp B2 (m) (Q.30.2) forn2 ny Let c3 = max(c;,cp) such that n2max (ny ,n9) Then we can write using equations (Q30.1) and (Q302) as: Ty (n)+ Ty (n) ¢ ¢ By (+e Bat) S (cy +¢2) (81 (m)+ B2(n)) Seg G1 + 82(n) S cg 2max(g; (n)+ gp (n)) Hence Ty(n)+T, (n) € O (max (g; (n)+ gp (n)) is true. Q31 Develop an algorithm to determine the minimum and maximum values in an array 41 22 ...ay of integer (Here 21 and the entries in the array need not be distinct). Determine worst-case complexity function for this algorithm. Ans. : Algorithm for minimum and maximum values in an array. Algorithm Min-Max-element (a[0...~1}) /fpxoblem Description : This algorithm is for finding the /roinimum and maximum element in an array. /haput : An array al] of some size n Hovtput : Prints minimum and maximum Helement of an array Max < alo] Introduction. ‘Min & a[0} for (i 1 ton) do { if (ali] > Max) then Max laxge) large « alil; } : Write("The largest element: "+arge); } Time complexity = O(n) | L5 Probabilistic Analysis Q.33 Write short note on probabilistic analysis. SEPLONTU + Part B, Marks 5) Ans, : ©1n probability theory various “experiments” are cartied out, The outcomes or results of those experiments determine the specific characteristics, © For example : Picking up a card from a deck of 52 cards, tossing coin for five times, choosing a.red ball from an urn containing red and white balls, rolling die four times. Each possible result of such experiment is called sample point. The set of -all sample points is called sample space. The sample space is denoted by S.’The sample space S is finite set. An event E occurs from sample space. For m sample points there are 2" possible events. * Probability : The probability of event E is the ratio of E to S. Hence = !El is} © For example : When a coin is tossed, then we may get either head (H) or tail (T). Suppose, we have tossed four coins together then there are 16 possible outcomes : HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, HTTH, HTTT, THHH, THHT, . THTH, THTT, TTHH, TTHT, TITH, TITT. For 4 events (HTH, THTT, TTHH, TITT), the probability is Probability ‘+ Mutual exclusion : Two events A and B are said tg bbe mutually exclusive if they do not have any common sample point. Hence ANB=( For example A =(HHTH,HHTT), B = (HTTT, THHT| are mutually exclusive. # Independence : Two events A and B are said to be independent if P(A MB] = PLA}*PIB] + Random variable : The random variable is basically a function that maps elements of S to set of real numbers. + For sample point acS the F (a) denotes the mapping. If F denotes a finite set of elements then it is called discrete. Thus the random variables can be discrete random variables. For example - If we pick up four balls from an umn containing red and white balls then the number of red balls that get selected is F (RRRW) = 3 or F (RWWW) = 1 and so on. Q.34 Explain the distribution. concept of probability USP [INTU : Part A, Marks 3] Ans. : Probability distribution : If F is discrete random variable for sample space S then probability distribution can be defined for a range of elements fay/aj,.aq) such that P[F=a,], P[F=a,] ... = For a probability distribution For example if we pick up four balls randomly from an um containing red and white balls and F is number of red balls, then F can take on five values 0, 1, 2, 3 and 4 then On| mo eo [ete “0 of 1 | 9 1 “o | 1 0 ° [so [a [- of repr yr i Osho sloet SF recrivicat PuaLicarions” An up trust for knowledge ‘Seamed nth CamScannerj | 1 Analysis of Algorithms Introduction. 0 Here 1 means presence of red balls and 0 means absence of red ball from the four balls that are picked up. — + Hence probability ere of F is given by P(F actual cost, the difference is saved in specific objects called credits, e) When for particular operation amortized cost < actual cost the stored credits are utilized. For example - In case of multiple_pop() operation the amortized cost for each operation is O(n)/n. Potontial Method: The working of method is as follows - * Let, Do be the initial data structure. Hence for n operations Ds, Di, Dz....Ds will be the data structure. Let c1, c, .... cadenotes the actual cost. *Let ® is a potential function which is a real number. © (Di) is called potential of Di. * Let, cj be the amortized cost of itt operation potential d= 4+ O(D;)-0(D,_,) A Potential change Actual cost dq = 2 @+0@)-00,.)) and ase = Se +e,)-Dp) * If ©(D;) 2 (Do), then amortized cost is an upper bound of actual cost. For example - The amortize cost of each stack operation is O(n). Probabilistic analysis : Refer Q. 33. 17 Recurrence Relation 2.43 What is recurrence relation ? CGP [INTU = Part A, Marks 3] Ans.: The recurrence equation is an equation that defines a sequence recursively. It is normally in following form - Ten) = Tin-1) +n for n>0 TO) =0 w+ (Q43.1) ~» (Q432) Here equation (Q.43.1) is called recurrence relation and equation (Q.43.2) is called initial condition. The Tecurrence equation can have infinite number of sequences. The general solution ‘to the recursive function specifies some formula. Q.44 Explain the method of solving recurrence relation. SSF [INTU : Part B, Marks 5] Ans. : There are two types of substitution - * Forward substitution * Backward substitution. Forward substitution method - This method makes uuse of an initial condition in the initial term and value for the next term is. generated. This process is continued until some formula is guessed. Thus in this kind of substitution method, we use recurrence equations to generate the few terms. For example : Consider a recurrence relation Tn) = T(m-1)+n with initial condition T(0) = 0. Let, Tm) = Tir-1)+n os (Q441) Ien=1 then Td) = TO) +1 =0+1 Initial condition at TQ) =1 o= (Q44.2) Ten =2, then TQ) = Ta) +2 =1+2 w+ Equation (Q.44.2) s TQ) =3 + (Q443) Ten =3 then 1) = T@)+3 = 343 Equation (Q.44.3) TQ) = 6 w= (Q444) By observing above generated equations we can derive a formula n2 Te) = es y nip °F recsucar pusuicaions”- An up tvs for knowledge ‘Seamed nth CamScannerDesign and Analysis of Algorithms We can also denote T(n) in terms of big oh notation as follows - Tin) = O(n?) But in practice, it is difficult to guess the pattern from forward substitution. Hence this method is not very often used. Backward substitution method - In this__-method backward values are substituted recursively in order to derive some formula. For example - Consider, a recurrence relation Tin) = Tin-1)+n w+ (Q.445) With initial condition T(0) = 0 Ter-1) = T-1-1)+(n-1) ... Qase) Putting equation (Q.44.6) in equation (Q.44.5) we get, Te) = Tm-2)4+(n-1) +n... (Q447) Let Tin -2) = Tim-2-1)+ (m2) ... (Q448) Putting equation (Q.44.8) in equation (Q.44.7) we get, Te) = T(n-3)+(n-2)+(-1)+n Tn) = Tink) +(n-k +1) +(m-k +2) tate k= n then Ti) = TO) +1424... Ti) = 0+142+ (n+) _n? De .¥ TO) =0 Tin) = ze Again we can denote T(n) in terms of big oh notation as Ta). € O(n?). Q.45 Solve the following recurrence relation Tio) =T(a - 1) + 1 with T(0) = 0 as initial condition. Also find big oh notation. ‘E&P [INTU = Part 8, Makrs 5] ‘Ans. : Let, Tin) = Tin-1) +1 By backward substitution, BP recrnucat PUBLICATIONS”. Anup taster krondge ——_Iroduetion Tin -1) = Tin-2) +1 T(n) = Tin -1)+1 = (Mn -2)+1) +1 Tin) = Tin -2) +2 Again T(n-2) = Tin-2-1)+1 = Tin-3)+1 Tin) = Tin 2) +2 becomes = (Tin -3) +1) +2 Ten) = Tin -3)+3 Tia) = Tn-k) +k (245.1) If k = n then equation (Q.45:1) becomes Ta) = Ti) +n =0+n ++. Initial condition T(0) = 0 Ti) =n + We can denote T(n) in terms of big oh notation as Tin) = O@). Q.46 Solve the recurrence relation Tin) = als +n C= [NTU : Part 8, Marks 5} Ans. : With TQ) = 1. as initial condition Te) = 2(a(g}ea)en Ti) = a(z}ta Tia) = 4(=(e}+g}em sr (3) 3n 2°13 }+90 Tin) ea ‘Seamed nth CamScanner Dest ie. Her We Nov‘Design and Analysis of Algorithms ' : i Tn) = 2a} Tir) = nfz} logn-n s+ TE we assume 2% =n = ne T()+n-logn Tin) = n +n log (n) Ta)=1 Sie Tin) = nlogn "Hence in terms of big oh notation - Tin) = O (n log n) QAT What is Master's theorem ? NES[INTU : Part B, May-17, Marks 5] ‘Ans. : Consider the following recurrencé relation - Ten) = aT (nb) + Fin) where n 2d and d is some constant. Then the Master theorem can be stated for efficiency analysis as - If F(n) is @(n4) where d 20 in the recurrence relation then, . 1 Ta) = Om) ifabé Let us understand the Master theorem with some examples : Example 1: Tin) = 4T (n/2) +n We will map this equation with Tia) = aT (wb) + f(a) Now f(n) is nie. n!, Hence d = 1. a=4 and b=2and a>blie, 4>27 Tea) = @(n'?®*) = e(n824y = O(n?) ‘Hence time complexity is ©(n?) log 4 =2 oa Introductlon Another variation of Master theorem is For T(n) = aT (n/b) + f(n) ifned 1. He f(n) is © (n'8b*~*), then | Tin) = 0 (n") | 2, Tf f(a) is © (n'°8* logkn), then T(n) = © (n!%b* Jog*! ny 3. If f(a) is Q (n!%b***), then Tin) is = © (Ha) 7 Example 2: Tin) = 2T(n/2) +n log n Here -f(n) = nlogn a=2,b=2 log)2 = 1 According to case 2 given in above Master theorem f(n) = © (n!827 login) ie, k= Then — Tin) = © (n'°8* log**!n) = © (n'82? log?n) = © (n? log?n) Tin) = © (n log?n) Q48 Let a, b, ¢ be numbers such that 0 < a, b<1 and c > 0. Let T(n) be defined by ‘T(n) = Tian) + T(bn) + cn. a) Show that if (a + b) < 1 then T(n) is bounded by linear function. 'b) Does there exist a, d such that, for all a, b, ¢ above T(n) = O(n!) 2 USPIINTU : Part B, Marks 5] ‘Ans. :a) To show that T(n) is bounded by linear function when (a + b) < 1, we will consider a = 3, 1 bez ‘The recurrence equation will then be Tee) = t(g)e(Sn}eom pee i Cee SB recanucar PUBLICATIONS An up rat kono ‘Seamed nth CamScannerDesign and Analysis of Algorithms _ 1 5 ws = = ‘The recurrence tree will be - Tn) ot a —-s =4T (5) 2 vm) EQ) — ter on a(}s)ea me (Ha) (a) @a) Qu) = Boalt watl™ es Fig. Q.48.1 (3 At third level we will get - Tn) = 2T 5) 2 (y= +93) (s}s + 9(3)(aF= (ayn a : a(S Be 3,1) : ih Thus (+2) n pattern woiks f 1 ws(F 5)nPa 2m woiks for i level Pras (3-8) =(B)a tor eve ten by sing wp Te) - 21(Z) + 45 20 total amount of work done by T(n) will be Ten) = 2" 70) +k... Assuming T(1) «1 loge Tr - ¥ =o+k a Tog, o 3 (a) = en Tn) +log,n Hence T(n) = O(n) and the 2 bound of above recurrence will be to This proves that T(n) is bounded by linear function. Tm) = 2@°%3" b) Ifa=b then, we can write, in following form b) Let Tin) = a 1(5)* f(a) Tia) = 5 1(z)+ n By Master's theorem Here a= 5,b=4, f(n) = e Te) ow when a 0 the a=b,a 1, a constant SP NTU B, Marks 5] Ans. : a) Let, Ten) = 7 Te/7) +n Here a=7,b=7, f(n) =n log, a = logy 7 = 0.845 FP récnwca. ussicaTions™- Anup wrt or inven Introduction _ As a=b, by Master's theorem, Tin) = © (n@ log n) As fn) = O(n*)=n Hence T(n) = (n log n) b) Let, Tin) = 8 T(ev2) +n? Here a= 8, b= 2, f(n) = n° logya = log, 8=3 f(a) = n° = n!°8b ie, case 2 of Master's theorem Hence Tia) = @(n!2ebalo8**'n) Tin) = Q (n? log n) o T(n) = Tin-1) +2 By backward substitution, Tin -1) = Tea-2) +2 Ti) = Tn-1) +2 T(n) = (Tin - 2) +2) +2 Te) = Ta-2) +4 Similarly, Tin) = Tin -3) +6 Tn) = Tin -k) + 2k i k = n-1 then Ten) = Tn-n+1)+2(n-1) Tin) = TQ) + @n-2) Tin) = 1+2n-2 coe TOYS 1 ‘Then we can represent recusrence as Ta) =,2(n) ) Let, Tin) = Tin) +1 We will put n= 2™, Then we get T@™) = TE) +1 ‘Seamed nth CamScannerDesign and Anatyssofalgorithns We will write T(2™) = s(m) S(m) = ‘S(m/2) +1 Here a= 1, b=2,f(n) =1 Joga = log) 1=0 ° fmm) =1=m? = ml i.e. Case 2 of Master's theorem By Master's theorem S(m) = © (log m) ie. Tin) = © (log log n) e) Let, Tin) = Tia-1) +c where ¢>1 By backward substitution, Te) = Tm-)+e Te) = (Tin-2)+ 8-H Ten) = Tin-2)4 2-14 Similarly, Tn) = Tin-3)+ P24 P14 Te) = Ta)+ > Thus Tin) = Q(c) for > 1 Q. 61 Suppose you are choosing between the following three algorithms : a) Algorithm A solves problems by dividing them into five sudproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. b) Algorithm B solves problems of size n by recursively solving two subproblems of size (n-1) and then combining the solutions in constant time. ©) Algorithm C solves problems of size n by dividing them into nine subproblems of size n=3, recursively solving each subproblem, and then combining the solutions in O(n2) time. What are the running times of each of these ithms (in big-O notation), and which would you choose ? GP [NTU : Part B, Marks 5] “Ans. + will write the recurrence relati problem for computing its running time. a) T(n) = 5T (3) +n . Apply Master's theorem Th) = (5) Fin) Here, a = 5, b = 2, Fin) = As a>b! ie 5>2! Tin) = e(n!e*) Tin) = e(n'*825) » Tin) where C denotes a constant time. By solving recurrence by backward substitution method, we get. Ten) = 2(2Tm-2)+C)+C = 2T(n-2)+2C+C Mn -1)+C 2 2 T(n-3)+C)+3C = 2 T(n-3)+P7C+3C =2-1C assuming T(0) =1 Tm) = 6 2") 9 Tin) = 9 7(3) fond "Apply Master's theorem, Tin) = a7(8)+ Fo) Here, a=9,b =3, F(n) =n? As a® blag ag? Ten) = 0 (a4 tog n) Tin) = © (n? Jog n) From above three complexities, the third algorithm takes the least running time, Hence third algorithm can be chosen. END. SP recenicat PusLICATIONS™. Anup trust fr knowledge ‘Seamed nth CamScanner[une] Divide and Conquer 2.1 General Method Important Points to Remember — |e In divide and conquer method, a given problem. is, i) Divided into smaller sub problems. ii) These sub problems are solved independently. iii) Combining all the solutions of sub problems| into a solution of the whole. If the sub problems are large enough then divide and conquer is reapplied. | Various applications of divide and conquer are - 1. Binary Search 2. Merge Sort 3. Quick Sort 4. Strassen’s matrix 5. Convex Hull Problems. Q1 Write and explain the control abstraction for divide and conquer and give the time complexity. E&P [INTU : Part B, May-09,13, Marks 8, April-t4, 12, Marks 7] Ans. : A control abstraction for divide and conquer is as given below - using control abstraction a flow of control of a procedure is given. Algorithm DC(P) { + if Pis too small then retum solution of P. else { Divide (P) and obtain P,P where n 21 Apply DC to each subproblem return combine (DC(P,),DC(P2)... (DCP,)); } z Py } Generalized Recurrence : Let recurrence.relation be; Tia) = aTinvb) + fin) Consider a 2 1 and b 2 2 Assume n = bk, where KHL, 2, we TX) 1 aT (bK/b) + £ (b*) aT (ok) + (0%) alaTio2) + OD] + £04 a2T (bk-2) + af (E> 1) + £(b*) Tok2) Now _ substituting by using back substitution, = a? [aT (DE 9) + £(bK°2)] + ae (DE?) + £(0*) = adT(bk- 3) +a26(Dk-2) + af(bk-3) + (0) Continuing’ in this fashion we get, _ abr (OE-#) + ak 1 £(bl) +a*-2 £002) + 2. 4a £00) « fa¥T (1+ ak-? fb) + a¥-? £(b4) + ta f(b*)] This can also be written as, = atta) + 2a) +2284) +: a Taking a* as common factor = fb) , f(b?) = [ro at a tn ak [ro + $ | a if By property of logarithm, al8yX = x!8b* Hence we can write a* ak = al? = n)8* as ‘Seamed nth CamScannerDesign and Analysis of Algorithme — We can rewrite the equation, Tin) = fro x ay] it t ee Tin) = n'85 prove x cya! | Thus order of growth of T(n) depends upon values of constants a and b and order of growth of function f(a). Q2 What are the applications of divide and conquer method ? Ans. : Various applications that use the divide and conquer strategy are - 1. Binary search 2 Merge sort 3.” Quick sort 4. Strassen's Matrix multiplication, 5. Finding maximum and minimum element, Q.3 What is Binary Search ? OSE [INTU : Part A, Marks 3) Ans : Binary search is an efficient searching method While searching the elements using this method. the ‘most essential thing is that the elements in the array should be sorted one. An element which is to be searched from the list of elements stored in array A[0...n ~ 1] is called KEY element. Let A{m} be the mid element of array A. Then there are three conditions that needs to be tested while searching the array using this method 1. _ If KEY = Afm] then desired element is present in the list. 2. Otherwise if KEY < A[m] then search the left sub list Otherwise if KEY > A[m] then search the right sub list. Q4 Search the element 60 from the list of elements as 10, 20, 30, 40, 50, 60, 70. 3. . 6 oT t Hi, ‘The KEY clement (ie, the element t0 be searches 60. Now to obtain middle element we will gy, formula: m = (low + high)/2 m= +62 m=3 Then Check Alm] 2 KEY ie. Aps] 260, NO AlS] = 40 and 49.<« v Search the right sublist. ete eee ce (oar ee Ta] LT Lot Sublist mid igh bist The right sublist is Now we will again divide this list and check the mid element. 4 5 6 50 | © | 70 | m= dow + highy2 en subst sublet mas i 2 ke ABB] = 60 Yes, ie. the number is present in the list, ‘Thus we can search the desired number from the lst of elements, SBF recroucan puaLicarions™ An up trust fr knowledge ‘Seamed nth CamScannerDesign and Analysis of Algorithms 0.5 Write recursive and non recursive algorithm for binary search using divide and conquer method. ERP [INTU : Part B, May-17, Marks 5] ‘Ans.: Algorithm (Non-recursive) Algorithm BinSearch(A(0...n-1], KEY) //Problem Description: This algorithm is for searching //the element using binary search method. /fnpst: An array A from which the KEY element is to be searched. {Output It retums the index of an array element if it is equal to KEY otherwise it retums -1 low 0 high ont while (low +G) tor n> 4 Time required ‘One comparison to compare left ‘made with sublist or right sublist middle element Also, Cyorst (1) = 1 But as we consider the rounded down value when array gets divided the above equations can be written as worst (A) = Cworst (L0/2,]) + 1)for n> 1 ... (Q.6.1) wort (I) = 1 ww (Q6.2) The above recurrence relation can be solved further. Assume n = 2* the equation (Q.6.1) becomes, Crear 2) = Cort (24/2) + 1 Cororst (28) = Cworst (2°) + 1 » (263) Using backward substitution method, we can substitute Crear 251) = Cyorst 24°) + 1 Then equation (Q.6.3) becomes, Cororst (28) * [Cworst (24°?) + 1+ 1 © Cororst (2°72) +2 Then Cworst 2) = [Crrorst 2*°9)+1] +2 Cworst 2") = Corse (2°°3) +3 Coram 2*) * Const 2*7 8) + = Cworst (2°) + k F rectewcat PuBuicaTions”- Anup tt fr komedi ‘Seamed nth CamScannerCoworst 28) = Crorg (1) + But as per equation (Q.62), Cvworst (1) = 1 Put this value in As. - have assumed uation (6.4), n=2 “ 60 Te logarithm (base Cwort 28) = 1+ kc 2) on both sides logan = log, 2* logan = k-log,2 logan = k(1) *' logy 2 =1 k= logan + Cyomt(Q) = 14 logy * Cworst() = logy n forn>1 The worst case time complexity of binary search is Slogan). | Average Caso * In average case, the search target is equally likely to bbe located in any array position, +The average number of probes made by binary search algorithm into an array of n elements is given by (1.142244348440421 y/a k ($2 yer » a 4 1¥ 1 Ke = 3] 26-24] /ak—-1 a x a i{dor|er-n a & - (Sen/oe-v a = 2-1). 2* +/2.2 1) = K-12 +H /k —1) Substituting back in terms of n where n= 2k] Ment fe. k= log, (n+1) We will get - og, 0 +1)-1-@+t)+1y/a > (ology (a+ 1)=n Hog, (0+1)=141yn log, (a+1)~ 1+ (log (a +1))/n Thus ; ‘The average case complexity is O(log) | Bost caso The best case of binary search occurs when the clement you are searching for is the middle clement of the list/array Q case complexity is @(1) | — 1 Q.7 What are advantages and disadvantages of binary search ? Ans, Advantage of binary search : i 1. Binary search is an optimal searching algorithm using which we can search the desired element / very efficiently. Disadvantage of binary search : 1. This algorithm requires the list to be sorted. Then only this method is applicable. : Q8 Enlist the applications of binary search | method. 2 G9 Design Divide and conquer algorithm for Somputing the number of levels in a binary tree. ‘SSP[INTU : Part B, May-09, Marks 8] Ans. - Algorithm Level_Count(root) { if(root==NULL) then return 0; if(root->leR== NULL then retum AND root ->right==NULL) 41 tet) Pin dani acide Le ee ‘Seamed nth CamScanner| | Design and Analysis of Algorithms /reomputing height of leftsubtree d2 + Level_Count (root->right); //computing height of rightsubtroo ig(d1>d2) then return di+1: else return d2+1; //maximum lovel = height of the tree Q.10 Solve the recurrence relation of formula on nis small Tele! aT in /2)+ F(a), otherwise when D gin) = O(1) and fin) = O(n) H g(t) = 01) and f(a) = O11). ES[INTU : Part B, May-09, Marks 8, May-12, Marks 15] fin) = O(n). Then the given recurrence relation is - Tia) = 27 (v2) + Fin) Tin) <2 Pr($) +Fo)]* F(n) Ans.:i) Let gin) (1) and If we assume F(n) = O(n) then Tin) = 2 [er (3) + 06] + O(n) - a3). O(n) + O(n) Tn) = (3) 2.0(n) : Tin) = sr(1(5) + 20) +2 O(n) Tia) = 2 1(B)+3.00 Tin) = 24[ J, }e009 But if we assume =n — then k = log n. Tin) = 24) Hema- O(n) Ie2* =n then Divide and Conquer Tn) = nerf )Hoan-0cm T(n) = n-T(n) + log n-O(n) Tn) = p(n) When nis small, and gin) = O(1) Tin) = n-Q{) +logn-O(n) Tin) = nlogn ii) g(r) ~ O(1) and F(n) = O(1) then the recurrence relation is Tn) = 27(3) +Fe) “2 [2t( 21( 5 ]+2 Fe #13 } + Fio)} +F(n) : (3). 2F(n) Tin) = (a): k-F(n) If we assumen=2* then ant (3) log n+ Fla) k=logn T(a) = nT(l) + logn-F (a) (1) is small hence we assume T(1) = g(n) = O(1) Tin) = n-O(1)+Iog n-O(1) Ti) = logn Q.11 Modify binary search of text so that in the case of unsuccessful search It returns the index I such that k(i) < key < k (1 +1). ES[INTU : Part B, Dec.-09, Marks 8} Ans. : Algorithm BinSearch(A(0:n- { /fProblem Description : This algorithm retums index //for an unsuccessful search using Binary search /Muput : The array A from which the KEY element /fneeds to be searched //Output : retums the index on unsuccessful search, lowe-0; high-n-t; while(low<=high}do { KEY) me(low-+high)/2;_ //mid of the array is obtained A(KEY==A[m)) then TECHNICAL PUBLICATIONS". Anup thrust for knowledge = ‘Seamed nth CamScannerWrito("The eloment is prosont in the lst"); ‘else if(KEY pivot, then decrement j Swap Ai] and A Gi] (fala [ul aa Swap A [i] and A {j] a[s ajn i a[s[>] ; i ‘As j pivot element and A [j] < pivot element we need not have to increment or decrement i or j. Just swap A [j] and A [i] elements, Le | [7 js los [oe [ss | 9 4 i Step 6: Go on incrementing i when A [i] < pivot clement and decrementing j when A {j] > pivot element, fF Tecra, PUBLICATIONS”. Anup est tr hownage ‘Seamed nth CamScanner2-7 Ysa] ss] 9] sls] 8151] ag j nas crossed 4 svvap pivot element ; ) with AU —fals|z}s| «|| s[ >] — aa ‘stop T: We will sort sublist 2, ss | | 5 | | 9 [coon incrementing | when AlN] < pivot element and ___aecrementing 559 | Al}> pivot element. ee i when Step §: As j has crossed i, we will swap Alj] and pivot element. element swap As i= pivot Alj}? Tes low high Array A[7] We assume Al0] = pivot. .. The pivot is E . Also set i and j pointers as E |x AMP [UE Prot i j Is pivot > Ali]? = No. ‘Then do not increment i, Now if Alj] 2 pivot, go on decrementing j © [X[A[M]P [TE] ast > decrement}, pivot i j E [x]A]M]P[L]E] as p> decrement j. Pivot i j B [x[A MPL] 8] AsM>E decrement j. pivot ij o 123456 B [x[A[M|P[t] 8] AsAE. Do not move i and j. But Piet tj Swap Ali] and Ali] BE LA[x[M|P/IL/E] NowAcE pivot ij &, decrement j. pivot j FF recnrcx, ruaucarons”. np rt rong ‘Seamed nth CamScanner> Divide and 28 onguey ~ . SS If Ali] $ pivot, increment i, 1 As j >i. We swap pivot AE. & [M|P[L[X] AsM>E, donot and Aj Then aye Increment But ie ys | pivot i i pivot then go on decrement j. As there is only one ALE[ © [M|P|L |X] Asp>£, decrement} element in the left sublist ak ist Sip We do not sort lett wot tj sublist ee ‘sublist, X_TMT PTL] E] Now set first element of Ale, E [M/ Pt] X] As ati> pivot decrement FE ight sublist as pivot. al 1 Hence AQ] = pivot. And vee | AL] =i Al6] =}. [ALEL X [M/PILTE] As pivot Ati increment 0123456 }, swap pivot “AE] B] M [P| tL] x] set pivot, i andj. pivot joi mall Pivot j i 01 2 3 4 5 6 As pivot has occupied its T - © [ETE Mm] e [x [x] postion we get only lt ABLE] M [PIL] X] AsP>m, donot sublist and no element in. pivot ij ifcrement i similarly SF the right ublist. Hence L a q Justify your answer. % BF [JNTU + Part B, Dec.-09, April-14, Marks a) P ‘Ans. : No, quick sort is not a stable sorting algorithn because after applying this sorting method the ordering of similar elements may not be preserved (Gince swapping is involved in this sorting with pivo, element). Q.18 Determine the running time of quick sort for 1) sorted input ii) recerse - ordered input Hii) random input 03> [JNTU : Part B, May-09, Marks 8} Ans.: Assumption : For finding. out the time complexities for given cases we assume that the pivot is somewhere at the middle of the list. Hence running time of quick sort differs based on selection of pivot. a) Sorted input : In sorted input, the left and right pointers of the array simply move without any swapping. Thus the problem is divided into two equal problems. Hence th recurrence relation for this case is - : Tin) = 2*T(n/2) +0 (n) Hence time complexity is O(nlogn) b) Reverse - ordered input : This case is similar to Previous éase. But in this case on each increment of left and right pointer the swapping takes Place. This affects O(n) part of the recurrence relation. But every swap is of O(1) time’ complexity The division of array still remains the same, Hence the time complexity is O(nlogn). ©) Random input : This is average case time complexity. The recurrence relation for random input array is - : Ten) = 10) + Tm -1) +n Tn) = TQ) +Tm-2)4+n es ‘Seamed nth CamScannerDesign and Analysis of Algorithms _ Tin) = TQ2)+T(n-3) +n Tin) = Thr =1) +T(0) +n ‘This tum out to be O(nlog n) time complexity [aa merge son | Q.19 Apply merge sort to sort the list E, X, A, M, P, L, Ein alphabetical order. (GP [INTU : Part B, Marks 5) Fig. .18.1 2.20 Explain the merge sort with the example. Write the algorithm of merge sort and the running time of the algorithm. EGP IINTU + April-14, May-12, 17, Marks 7] Ans. : Example - Refer Q. 19. Algorithm and Time Complexity : Algorithm MergeSort(int A(0...n-1),low,high) {f(ow < high)then { mid < (low+high)/2 // split the list at mid MergeSort(Alow,mid) // first sublist ‘MergeSort(A,mid+1,high)// second sublist Combine(A,low,mid,high) 1 merging of two sublists Divide and Conquer Algorithm Combino(A(0...n-1],low, mid, high) { ik © low;// kas index for array temp i¢low; — // as index for left sublist of array A jmid+1 //j as index for right sublist of array A while(i <= mid and j <= high)do { if(Ali]<=Alj)then // if smaller element is present in left sublist { // copy that smaller element to temp array temp{k] + Ali] jeu keok+t else //smaller element is present in right sublist copy that: smaller element to temp array templk] < Ali jest kekHt + } /eopy remaining elements of left sublist to temp while(i<=mid)do tomp|k] <— Ali] ici kek+t + /copy remaining elements of right sublist to temp while(j<=high)do { temp[k] — Ali jejet kek+d + Time Complexity Analysis In merge sort algorithm the two recursive calls are made, Each recursive call focuses on n/2 elements of the list. After two recursive calls one call is made to combine two sublists ‘ie. to merge all n elements. Hence we can write recurrence relation as JP ecru pusucarons”- snp tino ‘Seamed nth CamScanner2-18 Design and Analysis of Algorithms Tia + Tm) * en for Time taken by Time taken by Time taken Tin) = left sublist to right sublist to combining two getsorted get sorted sublists where n>1T (1) =0 Let the recurrence relation for merge sort is | Tea) = Tr/2) + Tén2) + en ie, Tin) = 2T(n/2) + on Let ~ Q) m7 +0 he) = atta) + Key]. 2) ‘AS per Master theorem Tin) = @(n4 logn) fa As in equation (1), a=2,b=2and f(n) =n ie. n4 withd = 1. and a=be | Hence the average and worst case time complexity of merge sort is @(n logon). Q.21 Determine the running time of merge sort for i) sorted input fi) reverse - ordered input ii) random - ordered input, ‘ES [INT : Part B, May-09, Marks 8] Ans. +i) The merge sort is the only sorting algorithm Whose time complexity does not get affected by the ordeting of the input. The ordetin i ig of the input impact on merge pi pitoohe rocedure. And merge proced ‘anyway requires logN iterations, Hence i) Sorted input ; 1 Reverse» ordere = ordered input tx which both the . subarrays get case ‘ombined and then get sorted. Hence time < complexity still O(nlogn). . to merge sort to make it 0.22 Sugcest rence Fa B Nay-08, Hak in place. Ans. below - iti) Random Algorithm Morge_srt(low,bigh) a alin] is for storing the unsorted list of //elements declared globally,initially low is set at first /Mocation of array & ‘fizitially high is set to last location of array @ if (n==1) then return; elso t if(lowlowy; auiti-lj=alt- 4; for()=midichighj++) do aux{high+midj}:=afj+1); for(int k=lowre< highe++) do ~ Aauxtj] min_new) then } min @min_new ——_//eombine solution 2.28 Consider a list of some elements from which maximum and minimum element can be found out. Sublist 1 6 7 « | « Sublist 2 We have divided the original list at mid and two sublists : Sublist 1 and sublist 2 are created. We will find min and max values respectively from each step 2: 12s ae = [ey] [Pe] s] suis . 7 so » [8 a S| sae Again divide each sublist and create further sublists. ‘Then from each sublist obtain min and max values. Step 3: ‘stop 4 Now further division of the list is not possible, Henoy ‘we start combining the solutions of min and may values from each sublist. 3 1 2 Combine (1, 2) and (3) Min = ~ 5, Max = 50 fo 435 foo [-5] =9 45 7 Combine (1, ... 3) and (4, 5) Min = - 9, Max = 50 Now we will combine (1, .. 3) and (4, 5) and the min ‘and max values among them are obtained. Hence, a min value max value = 50 Stop 5: 6 7 8 9 T T Q 0 | 3 | Combine (6, 7) and (8, 9) Min = 25, Max = 90 Stop 6 : fi0:2.3 4°55 6 7 8 8 Q so[w|-si-9[s] [2 6/3 [| Combine the sublists (1, .... 5) and (6, .... 9). Find out min and max values which are min=-9 . max=90 Thus the complete list is formed from which the min and max values are obtained. Hence final min and max values are ia 3 sos x] 0 [sTs min = ~9 and max = 90 : fae dog os C= : 2 It is possible to divide the list (50, 40, - 5) further. Hence we have divided the list into sublists and min, ‘max values are obtained. 7 I ec0cn aLcAToNe np mattriomman cal ‘Seamed nth CamScannerSearching and Traversal Techniques 3.1 Efficient Non-Recursive Binary | l ‘Tree Traversal Algorithms | Important Points to Remember + The binary tree contains at the most two child nod . | « There are three traversal techniques - inorder, | preorder and postorder technique. | Q.1 What is binary tree ? What are three traversals used in traversing binary tree ? TEP[INTU : Part B, May-17, Marks 5] ‘Ans, : A binary tree is a data structure that contains at the most two child nodes. For example - ‘There are three traversals used for traversing binary tree those are - 1. Preorder traversal - In this traversal the root/parent node is visited first, ‘then the left child and then right child. For example for tree given in Fig. Q.1.1 the preorder traversal is, 10, 8 12, 11, 14. Inorder traversal - In this traversal the left node is visited first, then parent node and then right node. For Fig. Q.1.1 the inorder traversal is, 8, 10, 11, 12, 14. @) QO ; QO ©& Fig. Q.1.1 Binary tree Postorder traversal - In this traversal the left node, then right node and then the parent node is visited. For Fig. Q.l.1 the postorder sequence is, 8 11, 14 12, 10. 3. Q2 Show that the inorder and postorder sequences of a binary tree uniquely define the binary tree. =P [Part 8] ‘Ans. : For defining a binary tree uniquely atleast two sequences are required. Following example shows that using inorder and postorder sequences a binary tree can be uniquely defined. Let us write the sequences as follows EICFJBGDKHLA Inorder : Postorder: IEJFCGKLHDBA Step 1: The last node in postorder sequence is root node. We will locate "A" in inorder sequence. The left sequence of "A" is the left subtree. EIC FISGDKHLA Stop 2: mort: G1 CF UO O KHL ® Povorders EDF CO KL Of @ ery woe Stop 3: ® Inert: € UE wo Powtordors 1 J (G) © me ‘Seamed nth CamScannerDesign and Analysis of Algorithms Step 4: ® tronrs Dt fo} reste: 9 6 . @& O Stop 5: ® toon: By © reser: 1] SS ag a Oo 0 Stop 6 : © more IK He o eK tnd re 5 QQ. 0 ea oOo oO Step :7 trons enor: « G5] is the required binary tree. Q3 The preorder and postorder binary tree do not uniquely define binary tree. Justify your answer. ES [Part B, Marks §] ‘Ans, : In preorder sequence the first element denotes the root node. On the other harid in postorder sequence the last element denotes the root node. Thus determining a root node is very easy when pre and postorder sequences are given but decision on the remaining nodes for becoming left or right child is conflicting. Because left and right children get accumulated on one side in both these sequences. ‘Along with either preorder or postorder sequence if inorder sequence is given then it partitions the left and tight subsequences using the parent node. For example - jequences of a ® @ q O CQ D | oO © 0 Consider Preorder [10 8 2 u Postorder 8 u 2 10 ‘The element 10 denotes the root node. From the sequences Preorder 8, 12, 1 Postorder 8 1, 12 It is not possible to determine which node should 4 attached as a left or right child of. root 10. Thy building 2 unique binary tree is not possible usin preorder and postorder sequence. Q4 Write and explain the non recursive inordy traversal. Ans. = void inorder(node *root) { node *current,*s{10}; rint{("\n Tree is empty\n"); retum; + ‘current=root; for(i) t ‘while(current! 4 push(current,&top,s); current=current->left; i {f(lstempty(top)) { pop(&top,s.¤t); rinti(* %a",current->data); current=current->right; } else return; |=NULL) 5F recrnucat PUBLICATIONS”. a up tus for krowledge ‘Seamed nth CamScannercurrent = NULL | i Q © | | | We will consider following tree as an example. @O) = Rect / current ° Searching and Traversal Techniques = root = 10. Initially we assume current ‘As current != NULL the while statement from the routine inorder will get executed. Push 10 Move onto left branch ssourrent = current — left Push 8 ‘Move onto left branch c-current = current —> left Move onto left branch s-eurrent = current + left Fl Now as current becomes NULL, we will come out of the while statements and following code fragment will get executed. Code if ( stempty (top)) { pop (&top,s, ¤t); cout <<"* << current > data; current = current — right}, + APE recrnacas PUBLICATIONS”. An wp tuto konto Meaning : We will pop the topmost element from the stack ie. 7. Then we will print it, And then we will move to right branch or right child of 7, calling it as new current. ‘Seamed nth CamScannerDesign and Analysis of Algoritions — urent current = NULL Output Now we will enter the for loop iteratively, but this time while statement will not get executed because current = NULL. Hence following code fragment will get executed. code Meaning (1 stempty (top) We will pop the topmost element from the stack . { je. 8. Then we will print it. And then we will move op (&top,s, ¤t); onto right branch. That mean now current = right cout <<"* << curent — data; child of 8=9. ccuent = current — right; + current = NULL Now we will enter the for loop iteratively and while loop will be executed because current = 9, Hence 9 will be pushed onto the stack. And now current = current —» left. As there is no left child for the node current; current = NULL. Hence following code fragment will be executed. Code Meaning i stempty (top)) Now 9 which lies on the top of the stack will ¥ popped off. It will be printed as an output, And not pop (&top,s, ¤t); P 7 - ee cout <<"" << current — data; current will set to right child of 9 which is NULL. current = current — right; } JF" TECHNICAL PUBLICATIONS". An up this for knowledge ‘Seamed nth CamScannerDesign and Analysis of Algorithms 3-5 INGLE] current Stack ' ind Traversal Techniques current = NULL Now we will enter the for loop iteratively but this time while statement will not be executed. The if statement will be executed. According to this code fragment, 10 will be popped off, it will be printed as an output and we will move onto the right branch of 10. Hence now, current = 11 as an output we will get 78 9 10. Again we will enter the for loop iteratively. The while statement will be executed because current = 12. We will push 11 onto the stack. And move onto the left branch of 11. But there is no left child to 11. Hence value of current becomes NULL. Then if statement will get executed. According to it, 11 will be popped off, it will be printed as an output and we will move onto right branch of 11. 7 89 0 1 Output current = NU Lu. Again we will enter the for loop iteratively: But current = NULL ; hence while statements will not be executed, stack is empty; hence if statements will not be executed. The else will be executed, by which control returns to main function. Thus we will get 7 8 9 10 11 as an output of non-recursive inorder traversal. 10 10 Stack 10 FY TECHNICAL PUBLICATIONS” An up thrust for knowledoo e ‘Seamed wth CamScanmer— ‘an output and push it onto the stack ‘,”™* esgnand Analysis of Algriims—___ cao Qs Write and explain the non recursive preorder | print 9 as me traversal. | Ans. | ‘vold preorder(node *root) | { | 9 10 a 7 9 node *current,*s{10}: ‘a int top=—1i | oy ouput ‘if(root= =NULL) | : ‘then 9 will be popped off, but 9 has no right chig so we will pop 10. The 10 has tight child ie. 11 | Hence print 11 as an output and push it onto th: | stack. | oo a7 oe Ht 1 printi(’ %d",current->data); ‘Stack ‘Output ] ‘push(current,&top.s) } current=current->left; | Finally 11 will be popped off. ‘The node 11 has no leftT t | or right child so nothing will be pushed. As a resul, if{tstempry(tor)) we get 10 8 79 11 as an output for non-recursive { preorder traversal 1 nt) a are ee Q.6 Write a non-recursive algorithm of postorder , traversal of tree and also analyze its time, , complexity. c co [GP [JNTU : Part B, April-09, Marks 10, Nov.-16, Marks 5] | return; } Ans. v } Algorithm postorder(node *root) : r { c Explanation : ‘/Minput: The root node t The logic for preorder traversal is similar to the a eae — sequen, ’ inorder traversal. But the only difference is that we tgiooe =U) tien will print the vallie of each visited current node | before pushing it onto the stack, Hence oe . Visiting each node, calling it as current, printing it as return; an output, pushing current node onto the siack and } 4 moving onto the left child. These are the sequence of | current «root; . operation which we must follow at every stage. for(; ‘Above is the scenario for stage J, II and IIL- { Now if we move onto left branch of 7 we will get To 2. : current = NULL. We will pop 7 check if it has any oer right. As 7 has no right child we will pop the next pate clement ie. 8. As 8 has a right child ic. 9, we will stltop] elementecurrent; : Sf recmucAt PUBLICATIONS”. Anup ht or knowledge ‘Seamed nth CamScannerIfcheck 1 means visiting left subtree dicheck 0 means visiting right subtree st[top].check«~1;//visiting the left subbranch currente-current-> loft; } while(st{top|.check: { current«-st{top].clement; top — Write(cuntent-> data); it(stempty(top)) then rotum; } current«-st{top].element;//pushing the element onto Iithe stack current current->right; st[top].check«-0;//visiting right subtree 0) do } } | The above algorithm takes O(n”) time Explanation [In the non-recursive postorder traversal we have to || add extra field in the stack structure. This field keeps a check on whether the node is visited once or not. If we visit that node for the first time then we set that || check to 1, if we again visits that node then we reset || that check. This extra logic: we have to put because | Q7 Write a non recursive algorithm of post order tree traversal. CSP [INTU : Part B, Nov.-16, Marks 5] || Ans. : Refer Q.6. 3.2 Disjoint Set Operations rt A, Marks 3] A disjoint set is a kind of data structure that contains partitioned sets. These partitioned sets are separate non overlapping sets. ||* For example : If there are n=10 elements that can be partitioned into three disjoint sets. Sj, S, and S3 such that no element is common among these sets. Searching and Traversal Techniques * Let, S={5, 4, 7,9}, S={ 10, 12, 14), $3={2,3,6 }, then each set can be represented as a tree, It is as shown in Fig. Q8.1. ® Q Q 6oO © © 6 © 8) % 8 Fig, Q.8.1 Tree representation of sets Q9 Explain the disjoint set operations using trees? SGP {INTU : Part B, May-12, Marks 7] ‘Ans,: There are two operations that can be performed on the data structure : disjoint set. These operations are union and find. 5, 4,7, 9, S2={ 10, 12, 14}, Ss 1. Disjoint set union : If there exists two sets S; and §; then 5; U S = fall the elements from set S; and §}. In above example SU S) = { 5, 4, 7, 9, 10, 12,14). 2. Find (i): For finding out the element i from given set, is done by this operation. For example ~ Element 7 is in $,,.element 14 is in S, 3.3 Union and Find Algorithms Q.10 What is union operation ? Explain. ES’[INTU : Part A, Marks 2] Let, $; = 2,36), Ans.: The union operation combines the elements from two sets. Consider S, = { 5, 4, 7,9} and S,={ 10, 12, 14) then ; US is Fig. Q.40.1 Union operation Q.14 Explain the method of representation of data of sets. S&P LINTU = Part B, Marks 5] 21) recmucar PUBLICATIONS”. Anup st fr komen . : ‘Seamed nth CamScannerDesign and Analysis of Algorithms = ‘Ans. : To perform union or find operations efficiently fon sets, it is necessary to represent the set elements in a proper manner. The data representation of sets is illustrated by following example - Consider $= (5,479) So ={ 10, 12, 14) and $3={2,3,6} For finding out any desired element, Set Panter eS & Fig. Q.11.1 Data represontation _ - i Find the pointer of corresponding set fi, Then find the desired element from that set. the root node of z 13 = 7s . ots sop = Temeans root apat! . eioane 7 ‘dni be }-—_J Fig. 0.11.2 ‘The sets can be represented using arrays as follows - The find operation can be performed as follows - Find (9) = 5. Now obtain af5]J= -1 means we have reached at the root node. Then node 5 is a root node whose child is 9. Thus element 9 is present in set S,. The union operation can be performed as follows - union (10, 20), union (20, 30), union (30, 40), (40, 50). ee Searching and Traversal Technigyy, @®@O®@! @) ©) @-©—-©-© Fig, 0.11.3 Degenerated tree Q.12 Two sets S, and Sp are as given below Sy = (1, 2, 4, 6} and Sp = {7, 8) @) Draw disjoint sets S, and Sp using tree: 6) Draw disjoint sets Sg using trees such that Sg = S, U Sp ©) Draw disjoint sets Sz using trees such that Sq = 82 U8; 4) Give pointer representation of Sy, Sp, Sg and Sq. SGP LINTU : May-12, Part B, Marks 15] Ans, a) The — trees are - peimuseneede 9 S4=S, US, = (7, 8,1, 2, 4, 6} © 8 @ Q © ®@ © 8 SF rectncat PUBLICATIONS". an up trust for knowledge (orcoot ‘Seamed nth CamScannerQ13 Explain the usefulness of the following fundamental operations on sets i) FIND ii) DELETE ii) UNION iv) INSERT. ‘S&P [INTU : Part B, May-12, Marks 15] Ans. : Various operations used by disjoint set are - UNION, FIND, INSERT, DELETE and MAKE SET. Following are the algorithms for these operations - 1) MAKESET(x) - This function is used for creating a new set. |MAKESET(x) iC ale] ox rank [x] 0 child [x] <0 // stores number of children marked [x] <0 // indicates if node is marked for Hasletion BY rechimca PUBLICATIONS" Anup thst for knowedge | | | | | The running time of this algorithm is (1). 2) UNION UNION (x1, x2) { ‘UNK (FIND (x1), FIND (x2) } LINK (x1, x2) { if rank [x1] > rank [x2] then alx2] xt child [x1] ¢ child [x2] + child [x1] + 1 elso afl] <— x2 child [x2] < child [x1] + child [x2] + 1 if rank [x1] = rank [x2] then rank [xe2] < rank [x2] + 1 } 3) INSERT: INSERT (x1, x2) { ‘MAKESET (x1) ‘UNION (x1, x2) t Using this function the elements of. the set can be inserted in tree. 4) DELETE : Operation has following goals - a) Either immediately remove a node or mark it for deletion. b) Remove any nodes that are’ marked for deletion and having no child. ©), Decrement. all child attributes for deleted nodes ancestors. These goals can be satisfied by two ~oprations - DELETE and CLEAN DELETE (x) { if (x # alx]) then ‘CLEAN (a{x]) if child [x] #0 then matked [x] <1 else 1/ marked for deletion ‘Seamed nth Camscanner—————— is of Algorithins Design and Analysl FREE (x) y CLEAN) { chil fx] child fe) = 1 fx a [xl thon CLEAN (alx)) € marked [x] = 1 then ifchild [x] = 0 //.0. no child to x node FREE (x) } The worst case running time of DELETE operation is O(logn), 5) FIND FIND (x) { sfx alx] thon alx] < FIND_SET (ax), child [x] + 1) retum alx] y FIND_SET (x, ch) { Pealx] — // making x parent if alx] then P< FIND SET (afx}, child [x] + 1) ax]

alj] ) then,// i has few nodes than j {. ali} =j // {becomes parent of 1 ali] = temp ; } t else Messer or equal to condition { . ali) =i Wibecomes parent of j all] = temp _Searching and Traversal Techniques _ Algorithm using collapsing rule - Definition Collapsing Rule : If j is a node on the path from i to its root and a[i) # root [i] then set afj] to root [i]. Using collapsing rule, the find operation can be performed. |For example [Step 1: Consider a tree of unions, Now we will find 6 using collapsing rule, Q ® QO @ Let, root = 1 Step 2 itemp = parent[6] |As root | = temp i.e. 145 Step 3: JAgain root | = temp ie. 1#5 Set temp = parent { temp } Step 4: Again root | = temp ie. 143 Sot temp ='parent | temp ] fomp_= 1 Step 5 : [Now root=temp ie. 1=1. return root ie. 1 Step 6: Thus we can find (6) as 6-95-31 ‘Seamed nth CamScanner