Strictly as per the New Revised Syllabus (REV- 2019 ‘C’ Scheme) of Mumbai University wef. academic year 2020-21 (As per Choice Based Credit and Grading System) Analysis of Algorithms (Code : CSC402) Semester IV - Computer Engineering f Includes : > © Solved Latest University Question Papers Dr. Mahesh M. Goyani upto Dec. 2019. @ im ~ ze TechKnowledge PublicationsAnalysis of Algorithms (Code :CSC402) Strictly as per the New Revised Syllabus (Rev-2019 ‘C’ Scheme) of Mumbai University w.e.f. academic year 2020-2021 Prof. (Dr.) Mahesh M. Goyani Ph.D., B.A., ME. BE. Assistant Professor, Department of Computer Engineering, Government Engineering College, Modasa Gujarat, India. MEL35A Price t 250/- IO Se TechKnowledge ¥ Publicationsee Analysis of Algorithms (csc402) prof. (Dr.) Mahesh M. Goyani Semester IV - Computer Engineering (Mumbai University) © by Author. All rights reserved. No part of this publication may be reproduced, copied, o- uted or transmitted in any form or by any means, including photocopy chanical methods, without the prior written permission of ty Copyright stored in a retrieval system, distri recording, or other electronic or met publisher. wn that it shall not, by the way of trade or otherwise, be lent, resold Jor written consent in any form of binding cr ilar condition including this condition b der copyright reserved above. This book is sold subject to the conditio hired out, or otherwise circulated without the publisher's Pr cover other than which it is published and without a sim! imposed on the subsequent purchaser and without limiting the rights un First Printed in India + January 2018 First Edition : January 2021 Maldives, Nepal, Pakistan, Sri Lanka and « Bangladesh, Bhutan, ss is unauthoriz This edition is for sale in India, rrchase of this book outside of these countrie: countries in South-East Asia. Sale and pu the publisher. ISBN : 978-93-90428-49-6 Pung ‘TechKnowledge Publications Pare ites 37/2, Ashtavinayak Industrial Estate, B/S, First floor, Maniratna Complex ‘Taware Colony, Aranyeshwar Corner, | Narhe, Pune, Maharashtra State, India, Pune - 411.009, Maharashtra state, Indi? | Pune 411041 Ph: 91-20-24221234, 91-20-24225678 Email : info@techknowledgebooks©o™ | Website : www.techknowledgebooks i Near Pari Company Subject Code : CSC402 Book Code__: ME135A,‘We dedicate this Publication soulfully and wholeheartedly, in loving memory of our beloved founder director, Late Shri. Pradeepji Lalchandji Lunawat, who will always be an inspiration, a positive force and strong support behind us. “My work. is my prayer to God” ~ Lt. Shri. Pradeepji L. Lunawat Soulful Tribute and Gratitude for all Your Sacrifices, Hardwork, and 40 years of Strong Vision...reface ar Students, Jam extremely happy to present the book of “Analysts of Algorithms” for you. I have divided the subject into small chapters so that the toplcs can be arranged and understood properly. The 1 the chapters have been arranged in a proper sequence to ensure smooth flow of the topics subject. 1 present this book in the loving memory of Late. Shri. Pradeepji Lunawat, our source of inspiration and a strong foundation of “TechKnowledge Publications”. He will always be remembered in our hearts and motivate us to achleve our new milestone, J. 8. Katre, Shri, Shital Bhandari, Shri, Arunoday Kumar and 1 am thankful to S r the encouragement and support that they have extended. | am also Shri. Chandroday Kumar fi Seema Lunawat for technology enhanced reading, E-books support and the staff thankful to ‘Knowledge Publications for their efforts to make this book as good as it is. We members of have jolntly made every possible efforts to eliminate all the errors in this book, However if you find any, please let us know, because that will help us to improve further. - Author goore, Ero Mumbai University Second Year of Computer Engineering (2019 Course) Analysis of Algorithms (cSc402) Credits 3 Course Code Course Name csc402 _| Analysis of Algorithms Prerequisite Courses: Data structure concepts, Discrete structures Course Objectives : 1. Toprovide mathematical approaches for Analysis of Algorithms. 2. Tounderstand and solve problems using various algorithmic approaches. 3. Toanalyze algorithms using various methods. Course Outcomes : At the end of the course learner will be able to Analyze the running time and space complexity of algorithms, Describe, apply and analyze the complexity of divide and conquer strategy. Describe, apply and analyze the complexity of greedy strategy. Describe, apply and analyze the complexity of dynamic Programming strategy. 1 2 3. 4. 5. Explain and apply backtracking, branch and bound. 6 Explain and apply string matching techniques, 7 Detailed Contents Hous i Introduction 8 matical hae? lexity Growth of function, Big-0h. ao background for algorithm analysis. NP. NP-Hard, NP-Complete Analysis of 12 19 (Refer Chapters 1 and 2)Hours: nding minimum and maximum of Binary search. (Refer Chapter 3) Qt Zeneral method, Merge sort, Quick s Analysis, Analy: algorithms and thei 3 Greedy Method Approach 3.1 | General Method, Single source shortest path: Dijkstra Algorithm, Fractional Knapsack problem, Job sequencing with deadlines, Minimum cost spanning tr (Refer Chapter 4) - Dynamic Programming Approach 4.1 | General Method, Multistage graphs, Single source shortest path: Bellman Kruskal and Prim’s algorithms, Ford Algorithm, All pair shortest path: Fl Problem0/1 knapsack _| common subsequence. 5 Backtracking and Branch and bound 5.1 | General Method, Backtracking: N-queen problem, Sum of subsets, Graph yyd Warshall Algorithm, Assembly-line scheduling ‘oblem, Travelling Salesperson problem, Longest (Refer Chapter 5) coloring. \d Bound: Travelling Salesperson Problem, 15 Puzzle problem. (Refer Chapter 6) 5.2 6 String Matching Algorithms 4 atching algorithm, The Rabin Karp algorithm, The Knuth- (Refer Chapter 7) 6.1 | The Naive string: Morris-Pratt algorithm . Analysis of Algorithms Lab (CSL401) Lab Code Lab Name Credits ‘CSL401 | Analysis of Algorithms Lab - Prerequisite : Basic knowledge of programming and data structure Lab Objectives : 4. Tointroduce the methods of designing and analyzing algorithms >. Design and implement efficient algorithms for a specified application 3, strengthen the ability to identify and apply the suitable algorithm for the given real-world problem. 4, analyze worst-case running time of algorithms and understand fundamental algorithmic problems. Lab Outcomes : At the end of the course, the students will be able to 1, Implement the algorithms using different approaches. 2. Analyze the complexities of various algorithms. 3, Compare the complexity of the algorithms for specific problem.Rien Implementation can be in any language. — Suggested Practical List : 7 Pato conasus Sr.No. Suggested Experiment List 1 Introduction 14 Selection sort, Insertion sort Divide and Conquer Approach 24 Finding Minimum and Maximum, Merge sort, Quick sort, Binary search Greedy Method Approach 31 Single source shortest path- Dijkstra Fractional Knapsack problem Job sequencing with deadlines Minimum cost spanning trees-Kruskal and Prim’s algorithm Dynamic Programming Approach 4 Single source shortest path- Bellman Ford All pair shortest path- Floyd Warshall 0/1 knapsack Travelling salesperson problem Longest common subsequence Backtracking and Branch and bound 5.1 N-queen problem Sum of subsets Graph coloring 64 String Matching Algorithms The Naive string-matching Algorithms The R Karp algorithm, ‘The Knuth-Morris-Prate algorithmWF _Analysis of Algorithms (MU) 1 Table of Contents Risse Chapter 1: Introduction to Analysis of Algorithm 1-110 1-27 Md IntFOdUCIOR enn At 1.4.1 Whatis Algorithm?, io 1.1.2 Properties of Algorithm. Ad 143 Howto Write an Algorithm 12 12 Performance Analysis ncn a8) 12.1 Space Complexity . 13 122 Time Complexity. 15 123. Growth of Function... 16 1.2.4 Asymptotic NOtAtIOM nnenn 17 1.2.4(A) Big Oh. 18 1.2.4(B) Big Ome gener 19 12.4(0) Big Theta.. 1.9 13 Mathematical Background for Algorithm Analysis.. 1.3. Framework for Analysis of Non-Recursive Algorithms. 1.32 Framework for Analysis of Recursive Algorithm: 14 Complexity Class. 141 Introduction to Complexity Theory 142 PProblems... 143 NP Problem 144 Difference between P and NP. 145 NP-Completeness and Reducibility. 146 NP-Completeness Proofs. 14,6(A) Vertex Cover Problem.. 1.4,6(B) Clique Problem 1.4.7 NP-Hard Problem. 148 Comparison between NP Hard and NP Complete 15. ‘Analysis of Selection Sort and Insertion Sort... 1-22 15.1 Selection Sort... 1.22 152 Insertion Sort. ant 24 Chapter 2:_ Recurrence 21 to27 2a ‘The Substitution Method 2A 22 Recursion Tree. 24 23 Master Method men BS Chapter 3: Divide and Conquer 341 to 3-29 3a General Method ... 31 3,1 Introduction... : 34 31.2 Control Abstraction... a 32 313° EMMiciency Analysis. 32 a 33 32 Merge Sort 33 33 Quick Sort... 3.9 34 Binary Search.. 3:23 35 Min-Max Problem : 3-26 36 Strassen's Matrix Multiplication 3-28 ee ———— Cheplor4_Greedy Algorithme ee 888 <1 General tho #1 $12 cond Abaacton + 413° Guratersi +2 tia Apleatons of Greedy Appreash_—_ 425 Dvdeand Conquers. credy Algoritins- 416 Dyan Progamming Vs red approach 3 42, Single Source shortest Pl 43° Krapsack ble. 431 FocionalKapsck Problem 44 lobsequencng 453. Kr agontim 454 —_biflerence beeen Prins and Seopa sain 462 Stonge one Tapes Chapter; Dynamic Programming 1108-1 Sr Gener Neted 2 ye 52 Pancpleofopinaliy 53 Bloentsof Dynamic hogTabi, Backtracking Vs Branch and Boung SS Analysis of Algorithms (MU) 55 Multistage Graph mnamem——— 56 ‘Single Source Shortest Path =n 87 All Pair Shortest Path... 58 Assembly Line Scheduling 59 0/1 Knapsack.- 594 First Approach. 5.10 Travelling Salesman Problem 5-45 ett Langest Common SUBSeqUEnCEmmnnenm—ee 5 Chapter 6: Backtracking & Branch and Bound 6-1 10 6-35, 64 614 61.4(4) 61.108) 61.2 Control Abstraction 61.2(A) Recursive Backtracking Method 6:1.2(8) Iterative Backtracking Method 613 Applications of Backtracking 614 8-Queen Problem. 615 SumofSubset Problem. 616 Graph Coloring 62 621 ‘Applications of Backtracking Control Abstraction... 624(A) LCSearch. __™ 624(8) Control Abstraction for Least Cost Sean, 62.4(0) Bounding. on Seah 62.4(0) Control Abstraction for FIFO Branch and Bound... 625 15 Puzzle Problem. = 626 Travelling Salesman Problem. 62.6(A) LCBB using Static State Space Tree... = 626(B) | LCBB using Dynamic State Space Tree, 627 Comparison between Divide and Conquer, Dynamic Programming and Backtracking._, epi ee Chapter 7 :_ String Matching 74 Introduction. 72 ‘The Naive String Matching Algorithms 73 ‘The Rabin Karp Algorithm. 74 String Matching with Finite Automata.. 78 The Knuth-Morris-Pratt Algorithm... + Lab Manual setIntroduction to Analysis of Algorithm Analysis of selection sor, Insertion sort 1.1 _ Introduction = The term Algorithm was coined by the Persian mathematician al-Khowarizm in the ninth century, The algorithm is a set of rules which are used to solve real~ life problems. The algorithm provides a loose form of a solution in a pseudo-programming language. ~ Given the algorithm, itis easy to program the solution. It bridges the gap between natural language description of the solution and syntax of programming language. = The first ever algorithm was developed by Babylonians for factorization of a number and to find roots of the equation. Euclid had proposed a famous algorithm for finding greatest common divisor (GCD) of two numbers. = We can treat an algorithm as a set of finite instruct which solves a particular problem when applied it Is applied to that problem with legal input. 4.1.1. What is Algorithm? [ek Define algorithm. (2 Marks) Definition The algorithm is set of rules defined in specific ‘order to do certain computation and carry out some predefined task. It is a step by step procedure to solve the problem. = Initially, the solution to the problem is thought as a natural language description, whose syntax Is too far from the programming language. Performance analysis, Space, and time complexity, Growth of Mathematical background for algorithm analysis. Complexity class function, Big-Oh, Omega, Theta notation, Definition of P, NP, NP-Hard, NP-Complete, = Before the actual problem solved in a programming atural language description of the solution is first represented as an algorithm. The algorithm is then language, n converted to code. = The process of solving a problem is depicted in the Fig. 1.1.1. Input 4 Problem vee Program Naural Pau Progen tanguese code “anoweoe ou os conéét ort wit any Fig, 1.1 : Design of solution to the problem = If the algorithm is correct, then the program should produce correct output on valid input, otherwise, it should generate an appropriate error message. For example, to find the division 4/B, correctly written program would return value of A/B for B > 0, and it would show the error message like “Invalid divisor” for 1.1.2. Properties of Algorithm @. Discuss various characteristics of the algorithm. (4 Marks) (4 Marks) Q. Explain properties of the good algorithm. = A good algorithm should have following properties / characteristics :2810 Anay ot Ago (MU ey : 11) How to Welte an Algoritin, Fig. 1.1.2 : Characteristics of good algorithm 4) Input Algorithor may take zero or more input arguments Depending on the problem, the input may be a scalar, tree, graph or some other data structures. vector, ar 2) Ontput Algorithm reads input, processes it and produces at east one output, Depending on the problem being solved, the output may ofthe form scalar, vector, array, tree, graph ‘or some other data structures. 3) Definiteness AA instructions in algorithm should be unambiguous and simple to interpret. There should not be multiple ways to interpret the same Instruction, Instructions should be precise and concise, 4) Finiteness Every algorithm must terminate aftera finite number of steps. If algorithm contains a loop, the upper bound of the loop must be finite. Recursive calls should have defined base case to terminate the algorithm, a well. 5) Effectiveness The algorithm should be written with a haste set of instructions. The operations should be perform exactly using basic set, ust lke them with per Performed using a combination of baste Instruction, Fer example, multiplication should he performe, and addition, sorting should be comparison, swapping e basic enough to fone can perform lons should be «d_paper. Compley oper “t using loop ‘carved out using looping, a —— , Discuss the rulos to write an aigoritig Q. What are the general rules followog whi 6 algorithm? oy 6 te agorthn basiealy consists of yy body. H ~ Heal pat consists of agorthn name de problem being solved, input to the na espected output I may als nce he ga input arquoent amd output variable The ge provides clear idea to the use about te agg, thealgorithm, = Body part Includes a Logie sequence of gy involving va expressions, loops, breaks, function calls et Aigorthm namo, Description, input and output Logical sequence of statements to solve problem lous constructs lke conltonl yy Fig. 1.1.3 : Structure of algorithm An algorithm is a lucid form of program and ita have rigid restrictions of syntax. One can writeanalgs Using his own terminology. However, some of the common rules folie! writing algorithms, w 1, The algorithm should start with the Algorithm, followed by name of algoritha, foe alist of arguments to be passed to the algoritht Algorithm FIND_SUM(A, B) 2 Comments start with // sign, In very next I wo should specify the description and input-att™" algorithm, ich are stated below: es // Problem Description : Add two integer asi 7/Mpat s Two numbers A and B on which st performed ——___ 17 Output : Sum of given two numbers eeWF Analysis of Algorithms (MU) 13 Introduction to Analysis of Algorithm Examples of how to write algorithms 3, Next, comes body part, which contains various logical statements in proper sequence. These statements may | Ex. 1.4.1: Write an algorithm for finding the factorial of contain control statements, loops, expressions ete. number n. 4. Compound statements are enclosed within the opening | Soin. : and closing curly brace ie.{..}. “Algorithm FACTORIAL (a) 5, Use left arrow forassignment : C— A+B, 11 Deseription : Find factorial of given 6 Array index usually starts with index 0 oF 1 I npat : Number n whose factorial is to he computed 11 Output : Factorial of n = 0X {n= 1) X...X2X1 7. Relational operations are performed using relational operators like <, zands 8 Logical operations are performed using logical operators like and (a), or (v) and $ not (—). else 9. Inpat and output are performed using read and write |] "=" " “FACTORIAL(a= 1) statement. read (A) / read “A" write (A) / write “A” or print (A) / print “A” 10, Control statements are written as follows if (condition) then Statement end if (condition) then Statement else Statement end Multiple statements are enclosed within {...} 11, While loop is written as follows : while (condition) do 1 Do some work } ‘Sometimes curly braces are omitted and block is closed with end keyword. Ex. 1.4.2 :Write an algorithm to perform matrix mutipication Soin.: “Algorithm MATRIX_MULTIPLICATION(A, B) 1] Description : Perform matrix multiplication of two mares. {Input : Two matrices A and B of wi 1 Output : Resultant matrix containing multiplication of Aand B fori Ltondo for} 1 ton do cui e0 fork @ 1 to ndo CEL — CL] + ALTE * BOG) end xn, end end. while (condition) do Do some work end 12, For loop is written as follows for index < FirstIndex to LastIndex do { Do some work } Som: with end keyword, es curly braces are omitted and block is closed for index € FirstIndex to LastIndex do Do some work end | 12 Space ‘Complexity = However, there is no strict rule to follow these standards. Algorithm syntax may vary from person to person. 1.2. Performance Analysis @. What are the basic components which contribute to space complexity? (4 Marks) @. What do you mean by space complexity of an algorithm? How do we measure the space comploxity of an algorithm? Explain with suitable example. (4 Marks) ‘@. Explain space complexity in detail Tetawutetgt'& Analysis of Algorithms (MU) en = space complexity is very important nation of efficiency 14 Introducty 2 Example 1: Addition of two seal yee a Algorithm ADD_SCALAR(A, py analysis. I Description: Pesform aitintc aii Definition [Input :"Two scalar variables 4 ang y Problem-solving using computer requires memory 1 Output : variable C, which holds the ada to hold temporary data or final result while the vten y program is in execution (the amount of memory |)) C-A+B required by the algorithm to solve given problem i |) return C called space complexity of the algorithm.) Controlling components | of Space Complexity 1. Fixed size components 2. Variable size components Fig. 1.21 : Controlling components of ‘Space complexity of algorithm ‘The space complexity of the algorithm is controlled by two components: 1) Fixed size components It includes the programming part whose memory Fequirement does not alter on program execution. For example, © Instructions © Variables ‘© Constants © Arrays 2) Variable size components Ie Includes the part of the program which whose size depends on the problem being solved. For example, © Size of loop © Stack required to handle recursive call © Dynamic data structures like linked list We use the notation S(n) to specify the space co of the problem for input sizen, The term n ig the size of input or the problem size, The notion of space complexity is expla following examples: —__| ence mplexity treated as ined with The addition of two scalar numbers en, memory location to hold the resuj, 1, complexity ofthis algorithm is constant hese. Example 2 : Addition of two arrays ‘Algorithm ADD_ARRAY(A, B) I Description : Performa element two arrays W Input : Two number arrays A and B 1/ Output : Array C holding the element-vise sae AandB fori 1ltondo Cli] Abi] + BE end return C se arithnetss = Adding corresponding elements of two a8 size n requires extra n memory locatiots result. As input size n increases, required the result also grows in the linear order oe the space complexity of above code s# S(n) = On). Example 3 : Sum of elements of array Algorithm SUM_ARRAY_ELEMENTS(\) !! Description : Add all elements of aay A Input : Array A of size n // Output : Variable Sum whieh holds the i? clements, Sum <0 fori —1 tondo Sum Sum + Afi lend . return Sum 5 4 The addition of all array eleme® Iocatot extra variable (j sum, th one memory independent of array s##°& Analysis of Algorithms (MU) 15 Introduction to Analysis of Algorithin ‘Thus the space complexity of the algorithm is constant and S(n) = 0(1). je Time Complexity ‘@. How do we analyze and measure the time complexity, of an algorithm? (4 Marks) @. What do you mean by time complexity of an algorithm? How do we measure the time complexity of an algorithm? Explain with suitable example. (4 Marks) @. Explain time complexity in det = Goodness of algorithm is often determined by the time complexity. Time complexity is the most fundamental component of analysis framework. Definition The valid algorithm takes a finite amount of time for execution( The time required by the algorithm to solue given problem is called time complexity of the algorithm. Time complexity is very useful measure in algorithm analysis.) ‘Time complexity is not measured in physical clock ticks, rather it is a function of a number of primitive operations. Primitive operation is the most frequent operation in algorithm (We use the notation T(n) to symbolize the time ‘complexity of the problem for input size. = The notion of time complexity is explained with following examples: Example 1 : Addition of two scalar variables “Algorithm ADD_SCALAR(A, B) ‘J Description : Perform arithmetic addition of two numbers I Input : Two scalar variables A and B 1] Output : variable C, which holds the additi nof Aand B CeA+B return ‘The sum of two scalar numbers requires one addition operation. Thus the time complexity of this algorithm is constant, so T(n) = O(1). Example 2 : Perform addition of two arrays Algorithm ADD_ARRAY(A, 1) 11 Deseription : Performa elem of two arrays Input 11 Output : Array G holding, the « and B fori 1 tondo ff one comparison Chi] ALi + BM wo number arrays A andl 1 of length a jv an of array A ininligaton, 1 ineeementy 1) n addition und 1 asigament return C hove code, addition array able 1 Is nd ‘As it can be observed from a elements required iterating loop n times. initialized once, the relation between control variable 1 ate checked n times, and I is incremented n times. With the loop, addition operations performed n time. and assignment ‘Thus the total time of algorithm is measured T(n) = 1(initilization) + n{copmparis + Increment addition + assignment) = 1t4n While doing efficiency analysis of the algorithm, we are interested in the order of complexity in term of input size n. What is the relationship between Input size n and the ‘number of steps to be performed? So all multiplicative and divisive constants should be dropped. Thus, for given algorithm T(n) = O(n) Example 3 : Sum of elements of array ‘Algorithm SUM_ARRAY_ELEMENTS(A) 11 Description : Add all elements of array A UM nput : Array A of size 0 um which holds the addition of array Sum <0 fori 1tndo Sum «Sum + Ali] end = The addition of all array elements requires n additions {we shall omit the number of comparisons, assignment, initialization etc, to avoid the multiplicative or additive constants). TecateIntroduction 1 Ana, 16 oy, WF Analysis of Algorithms (MU) X a — Anumber of additions depend on the size of| aes Erelercy ae Hi grows in the linear order of input size. Thus the ae Br ple complexity of above code is T(n) = O(n). = Time and space complexity of discussed problem Is Binary search -—~ Logarithmic | logn | insert / delete ler compared in the Table 1.2.1 binary search tee. Table 1.2.1 : Comparison of space and time complexity for various problems Linear search Insert nod FER a ne | timc nr ode at the 4, s(n) Tn) Linear a linked list Find minimum / ma, Add scalar ou) ow) element from array Add two om) om) Merge sort easve) Binary search Tal of nlogn Add array on) ¢n) nlogn 8 | uicksort elements Heap Sort 1.2.3 Growth of Function Q. Define order of growth. List various efficiency classes Selection Sort with example, Show the. relationship between Bubble sort efficiency classes, (Marks) | || ou sdratc Sr Definition Find maximum element The efficiency of the algorithm is expressed in term 2D matrix of input size n. The relationship between input size it Cubic n Matrix Multiplication and performance of the algorithm is called order u of growth. Finding power set of BP ~ Order of growth indicates how quickly the time required Find optimal solution by algorithm grows with respect to input size, Exponential 2" | Knapsack problem ~ For input size n the algorithm may execute a number of Solve TSP using 47" steps in order of log n,n, n,n or something else, programming Efficiency classes are categorized into differe, {as shown in Table 1.2.2. nt classes, Generating permutations given set : Solve TSP problem © EMciency | Onder of HL] J brute force approach_— Table 1.2.2 : Various efficiency classes Factorial nl class | Erowth Example EMMiciency classes are sorted as: ; ae oft . no It is denoted as fin) = Q(g(n)). Loose bounds ‘All the set of functions with growth rate slower than its actual bound are called loose lower bound of that function, on+3 = Q(1) ané+2n+4 = Q(n)=2(1) 2n44n45 = Q(n?)=2(n)=2(1) Incorrect bounds All the set of functions with growth rate lower than its actual bound are called Incorrect bound of that function. 23 ¢ Q(n)e (n')#Q(0"}#2.(n1) 6n+3 4 O(n!) ¢(n)#.Q(nl) 3n?+2n44 # O(n!) #2 (nl) 2n'+4n+5 # 2 (2")49(n!) nen ed For fuention f(n) f(n) = 2 (n®) = 2 (nlogn) = 2 (n) = 2 (logn) =2(1) ((n) # Q(n)#2(2") 42 (nl) + O(n") = This notation is denoted by “O’, and it is pronounced as “Big Theta’. Big Theta notation defines tight bound for the algorithm. It means the running time of algorithm cannot be less than or greater than it’s asymptotic tight bound for any random sequence of data. Growth of function Fig. 1. 6 : Tight bound Definition Let fin) and g(n) are two nonnegative functions indicating running time of two algorithms. We say the function g(n) is tight bound of function fin) if there exist some positive constants cy, cz, and no such that 0 $cy-g(n) Sit) ny Osc+g(n) s(n) Osc+g(n)s10n?+2n+1 and ny 0's 10n?s 10n? + 2n + 1,9 true, forall n2 1 An) = 2 (g(n)) = 2 (n?) for c= 3,ng=1 f(n) = © (g(n)) = © (n*) for cs = 10,02= 13,4 3. Mathematical Background for Algorithm Analysis Before we start analyzing algorithm, we wilt some important mathematical formulas, which to simplify the computation further. lathematics to simplify the summation = 1+1+14..¢1=n=0(0) n 5 al Di s14243+ tne 7 n (n?) 14 2k4 3844WB anaysis of Algorithms (MU) 1 1.3.1. Framework for Analysis of Non-Recursive Algorithms @. Discuss the general plan for analyzing efficiency of ron-rocursive algorithm. (6 Marks) @. Explain the framework of elficiency analysis of non-recursive algorithms with sultable examples. (6 Marks) = Finding complexity of the non-recursive algorithm simpler than that of recursive algorithms. A number of primitive operations define the complexity of the algorithm. By following below steps we can find the complexity of non-recursive algorithms ©. Determine size of problem / input © Find out primitive / elementary operation © Find count of primitive operations for best, worst or average case. © Simplify the summation by dropping multiplicative and divisive constants of highest degree polynomial term in sum, Ex. 1.3.4 : Determine the complexity to find the sum of elements of the array. Soin. : Soin, Algorithm BUBBLE_SORT(A, n) 1 Deseription : Sort the given numerical data UHnput Array A of randomly place 1 ele 1/ Ouiput: Sorted sexquence of input data fori ¢~ 1 tondo forj 1 wn~i~1do if Alj] > Alj + 1 then ‘Move largostolamont at tho ond of unsorted iat swap (ALi), Ali) Algorithm SUM_ARRAY(A, n) 1) Description : Find the sum of elements of array [input : Array A of length n 1/ Output : Variable Sum which holds the summation of array elements ‘over length of array A Sum <0 fori ltondo ‘Sum < Sum + Afi] ’Add each element in patil sum end print “Sum of Array Elements: ", Sum Step 1: Size of problem is n because length of array is Step2: Primitive operation is addition: Sum = Sum + Ati Step3: For loop iterates, n time and hence addition is performed n times, so T(n) = O(n) Tin) = DL ia141 41+ ..ntimes = O(n) 1 Ex. 1.3.2 : Find complexity of bubble sort Step1: Size of proble Step 2: Primitive operation is comparison loop, inner loop Step3: For each instance of outer iterate (n -) times. r loop does n - 1 comparisons, for For = nn Inner oop doesn 2 comparisons and soon The) = (1) + (0-2) #at 3424 nt FS tens 243+) Len-1y2 Bt = F* = 010’) ‘Ex. 1.3.3 Wile an algorithm for searching an olomont in array of size n, Calculate complexly of this algorithm. Soin. : = We will discuss and derive the complexity of linear search technique to search an element from an array of sizen. = Linear search Is a very simple way of searching an element from the list. Let Key is the element that we want to search, The key element is compared with on by one all index locations of A. Algorithm halts in two ed, cases : Key element is found or entire array Is ses ‘nis shown below : = Algorithm for linear ‘Algorithm LINEAR_SEARCIH(A, Key) 1] Description ; Pesform linear search on array A to search clement Key I Anpat : Array of length 1 1/ Output : Success / failure mess flag 0 fori C1 tondoIntroduetio, ty o ICAfi] > Max, algorithen updates y, Ue ify Ali then a to All]. The process Is repeated oye, is ‘ print “Element Found on Location” 1 pseudo code of the process i ven bey, Mi flag 1 Set flag if Key fs found ‘Algorithm FIND_MAX(A) Tim, peel 11 Description: Fil the maxim ley [Input : Array A of length ™ M1 Ourpat: Variable Max oling the acing ‘ array A Max @ A[]] fori 2tondo if Max < Ali] then Complexity analysis is ZAG Unioonare Best case ead Smaller an ‘The algorithm needs a minimum number of || end int “Maximum Element of Array A is", Max ‘comparisons if the key element is on the first position. In the best cas, the size of input array does not matter. Inthe | oor eyity analysis best case, the algorithm does only one comparison Irrespective of array length. Hence the running time of the linear search in the best case is, T(n) = (1). problem size is reduced by 1. Recurrence frthiy formulated as, T(n) = T(n-1)+1 In every iteration, algorithm does one con: Worst case ‘The algorithm does a maximum number of comparisons if the key element is on the last position of the array or itis | Let us solve this using iterat not present at all. The entire array needs to be scanned, T(n-1) = T(n-2)+1 Numbers of comparisons linearly grow with the size of the Input Hence the running time oftinear search in worst case | > TC) = [M(n=2) + 1}+1=T(n-2)+2 T(n-3)+1 is, T(n) = O(n) T(n-2) => Tn) = [T(n-3) +1) +2=T(n-3)+3 After k Iterations, in method, Average case ‘The average case occurs when an element is neither on the first location norat last. The key element may be near to T(n) = T(n-k) +k the beginning of array or it may be towards the end, or it For k =n may be somewhere near the middle, So on an average, the T(n) = T(n-n)+n=T(0)+0 algorithm does (n / 2) comparisons, cc fii! . st for solving problem of size 0 is defi Thus,T(0) = o($) = on) =0 The time complexity of e Hence, T(n) me compleaty of al three cases is depicted in the | (a) = O(n) Next Next # NULL && Temp —9 Next > Data # Key do Go up to second last node Temp = end 1) node tobe deleted is not the last node Key && Temp — Next remp —> Next if Temp — Next > Dat Next # NULL then Hold = Temp — Next ‘Temp —> Next = Hold — Next Free(Hold) ‘Stop on node before the node to be deleted 1) node to be deleted is last node else if Temp — Next > Dat Next == NULL then Hold = Temp — Next ‘Temp — Next = NULL (Hold) Key && Temp — Next > 1 key docs not exist HAL node with yi else print “Node not found” end ‘The problem is similar to linear search. On each iteration, problem size is reduced by 1, and one comparison is done. Thus, the recurrence for the above algorithm can be formulated as, ‘T(n) = T(n-1) +1 Let us solve this using iteration method, Tn 1) = Tin 2)+1 => Ta) = [Mn-2)4 1] 412 Tn-2)42 Tn-2) = T(n-3)+1 = Ta) = (Tin-3) +1]+ =~ 3)43 After kiterations, Tn) = T(n-K)+k For k=n Tn) = T(n-n)+n=T(0)+n Cost for solving problem of size 0 is definitely 0, so T(0) =o Hence, T(n) = O(n) Worst case for the problem occurs when the node to be deleted is at the end of the list or itis not present at all. For the list of n nodes, the worst case running time would be T(n) = O(n). Ex. 1.3.6 : Consider the following algorithm. ALGORITHM sum (n) 1! Input: A non-negative integer n sco fori=1tondo SeSti return §, i) What does this algorithm compute ? li) What is its basic operation ? ji) How many times the basic operations executed ? iv) What is the efficiency class of this algorithm 7 v) Suggest an improved algorithm and indicate its efficiency class. If you cannot do it, try to prove that it cannot be done, Soin. 1) This algorithm computes the summation of numbers from 1ton li) The basic operation is an addition, ie, computing sum fil) Basic operation executes m times iv) Ast performs n basic operations, efficiency class of this algorithm is O(n). v) An improved version ofthe algorithm ‘Algorithm IMPROVED_SUM (a) [J Description: Add first numbers UAInput: Number 1/ Output: Variable Sum holding the summation of first su numbers Suni Cn * (n+ 1)/2 return Sum ‘The complexity of this algorithm is O(1), it performs only one computation to find the sum of first m natural numbers. ©“Analysis of Algorithms (MU) Forn=6, Using algorithm SUMQ):1+2+3+4+5+6=21 Using Algorithm IMPROVED_SUMQ nt(n+1)/2=(6"7)/2=21 1.3.2 Framework for Analysis of Recursive Algorithms @. Explain the framework of efficiency analysis of recursive algorithms with suitable exampk (6 Marks) = By following steps, we can find the complexity of recursive algorithms: = Determine size of problem Identity primitive operation — Find count of primitive operation in each call =. Set up and solve recurrence equation using appropriate method. Ex. 1.8.7 : Write @ recursive algorithm for Tower of Hanol problem, setup its recurrence and soWve it Soin. : — ‘The tower of Hanoi is very well known the recursive problem. The problem is based on 3 pegs (source, ‘auxiliary and destination) and 1 disks. Tower of Hanol is the problem of shifting all n disks from source peg to destination peg using auxiliary peg with following constraints = Only one disk can be moved ata time. ‘A Larger disk cannot be placed on smaller disk ‘The initial and final configuration of the disks is shown in Fig. P.1.3.7(a) and Fig, P.1.3.7(b), respectively = Sovran po 708 estat pg Fig. P. 1.9.7(a) : Initial state of Tower of Hanot A ectnaten pag aon Poo Troan a Fig. P. 1.3.7(b) : Final state of Tower of Hanoi 4 Introduction 0 Analysis fg, Jen number of disks on soure © = There can bs trace the problem for n= 3 disks. The solution is : step 1 :Move disk a ‘oun P29 C from the sre peg to dst peg ‘naar Bea Desire, step 2: Move disk B from the se peg to aux peg ea el _ oem ‘uaiary poo Desir step 3: Move disk C from the dst peg to aux peg op ‘Sour poe emaary pe Dosa ‘Step 4: Move disk A from the sre peg to dst peg _—— “auney5e9 Step 5: Move disk C from the aux peg to sr Reg eres Sours pee —E]__ e1 ad Seu Peo ‘usary pe) Step 6 : Move disk B from the aux peg to dst pes cS Doon —f__ Source peg ‘Aamiary peg Step 7: '€P 7 : Move disk C from the sre peg to dst pe& ae‘Analysis of Algorithms (MU) Recursive approach is the best suitable for solving this problem, The recursive formulation for tower of Hanol is givenas, HANOI(source, aux, dest, n) = (en from sre to dst inst HANOI (sre, dst, aus, n = 1) Jaxon i. dst. 1) HANOI(aus, ste, dst.n= 1) _ otherwise Algorithm HANOM (sr, ats 1, Description: Move 1 di pee J Anpu 1/ Output: n disks on destination peg ‘peg to destination 3 pages, anal clisks on souree peg HANOMsre, dest, aus, n= 1) HANOI (re, aus, dst 1) HANOI(aux, ste, dest, n= 1) end Step 1: Sizeofproblem isn Step2: Primitive operation is to move disk from one peg to another peg Step 3: Every call makes other two recursive cals with problem size n- 1. And each call corresponds to ‘operation, so recurrence for this ‘one primiti problem can be set up as follow : T(n) = 2T{n-1) +4 a Let us solve this recurrence using forward and backward substitution: Substitute n by n = 1 in Equation (1), Ten=1) = 2T(n-2)+1, By putting this value back in Equatton (1), Tn) = 2[2T(n-2)+ 1] 41 = 2T(n-2)+241 = 2T(n-2)+ (2-1) Similarly, replace n by n ~2in Equation (1), ‘T(n-2) = 27(n-3)+ 1, (2) From Equation (2), Tn) = 2[2T(n-3) +A} H2eL = 2T(n-3)4 224241 Introduction to Analysis of Algorithm = 20T(n~ 3) +(2!-1) In general, ‘T(n) By putting k=n- 1, T(n) = 2-4(TC)] + (et 1) 2aT(n-k) + (241) T(1) indicates problem of size 1. To shift 1 disk from source to destination peg takes only one move, so Ta)eL, Tn) = 21+ (2-1) m1 02") Ex. 1.3.8 : Setup and solve a Recurrence relation for the number of calls made by F(n), the recursive algorithms for ‘computing nt oR ‘Write an algorithm to find factorial using recursion. Find the time complexity. Soln, : Factorial of number n is computed as : n (n-2) 0242 Recursive algorithm for finding factorial of any number is described below: +o Algorithm FACTORIAL(n) 1 Description: Fi A Input: Integer vale n i factorial of given number number n ifn ==Oor 1 then return 1 & Base case else retumn* (0=1) /Recursive case end For each call, problem size reduces by one and each call performs one multiplication, We can setup the recurrence as follow: Cost of one ‘multiplication ‘T(n) = T(n- 1) +1 (Inductive case) (1) ‘T(n) =n, ifn=Oorn= (Base case)\nalysis of Algorithms (MU) hod solves this recurrence using two meth Forward ‘Substitution From Equation a), T(2) T(3) = Metered? = T(2jels24i=3 Alter ksteps 1) =k Fork T(n) Backward substitution To find T(n), we need to ‘Tn Dstetus putin =n 1 in Equation (1), = O(n) Mn 1) = Tn~1-1)41eT(n-2)41 So,T(n) = Tin=2)+141=1(n-2)42 Simitarly, Tn-2) = MKn-2-1)412T(n-3)61 So, T(n) = Tn-3)+241=T(n~3)43 After k steps, TO) = TK Fork = n, Wek Tn) = Tn-n)+n 700) +n 4 Complexity Class n= O(n) Introduction to Complexity . Explain the folowing: (0) Computational comploxty (t) Decision probioms (Wi) Deterministic and ny (W) Comploxty classes (Y)_Intractabity, Theory 'on-dlerministc algorithms We can classify the ccategorles : 2 The problem which canbe 3 The problem which can computationally they takes ver «but can "be solved, n be solved retlcally, hue Algorithm, ™S, and the rte fee tn Force met ind 4 jane Practical not accep Forex peahenemend 6 the guar by by nd Tn = 1}, To solve Introd Del Problem is called intractayy,, ring, takes too tong time t0 be solyeg My a oh roblems has no practical apology, 2 — Problems which can be sojyy : practically in a reasonable anon, problems, there exists a determin e that can solve the problem jn ¢ tony p(n) is polynomial in n, a pro os Momign, nd n is Definition If the problem is solvable in yyy, ealled tractable. Such problems 4,, deny |problems. bea Se oe ——~ 5. The problem which is not known whey not In P. Such problems falls. som, class 3 and 4, [Definition ~The problem is said to be decision nk, they produce output “Yes” or = input. An algorithm which problem is called decision a > An optimization problem air solution from the set of all feasi An algorithm whieh Problem is calted optimiz, Optimization algorithm or least cost solution solve solves op ‘ation algeria seeks to find Decision pro ‘onal problem can be functioaF* © Such problem differs on 3 Classes are set of Lae Complexity, like Pp probl * Decision te. The Melaes falls 1 problems, complexity of ar) F ithin certain rans< Natinfiabilily Awaivels af Algun init (MU) Problonne Which take pr Vivully diiineviita lili Hindawi #0 Be ave cre ed dntrnwtable prablesie snninsny Hoes of Une adn té tin a fired fo Cupar), shen pid) fe autthe polyinanitid Hi Hh ihre a» typtusonede (hes wise yf Che pin 1D siay that the phubleate han palynanitie ani iy the eamplenity. Problent vbw the aphictabonn nf aswigninlenil, Sie ia7iebidity phabewt finn out whether fOr abe fMhpw HH eypenafonh fi tome fi Cir envatginnonh Redueibitity | Let Bi aid Beare tea protons and there evista weno biter indanintio algo itn A for Pr anet that Dy ean be wolvedd in polynuniial tine tating Ac If the sane ahgoritiine eae aalbe the problem Ps then tw ean way that Pe te redueible ta Bic 1.4.2 P Probleme: “@. What do you mean by P problem? Give an exainles (6 Marke) Q. Wille a short note on P probiens, Definition P problemn are net of probleme that ean be naliad: in polynomial tine by determin iatte aigrithinns Pix abo known a8 PTIME or DTI voniplenity lana. nia ak They ave stmple to salve, enay to verity and take computationally acceptable Unie far sulvliyy any ‘stance af the probleny, Save prcbaeanes ate alae Kinny “eractabile®, Lu the worst ease, searching a element fran the Hato ‘ze 1 takes 1 comparisons, Phe number af eanapa lenny ly with roapmet toy tnt alee Su Heat Increneo th sare Ix P problem. Iv practice, most of the problema are 1 prolen varelong, an elenvent tthe atvaay (EQ), tse tM Ah floment at dhe end a Hie Ht (Ho) went slat Uist, selection aant(O(n’)), ling Hewwht ot Wee COWoyen)), sore ata Wednyg merge ant (CAEHTOIN)) ‘mate toattypltentton 0") ae Faw a Che esas of problems, ‘alot ithnn with (26) connpilentty tes tote sa veh patton Win tested on a prafilony at alae (01 Ho not nye tn ela Be W vos titie all jvuly tuna ene Jit Wa Avalyole of Algor ily NDI HAN CAMKOL He sap gv allen age HAH Fone app sare canna vtviad 1 plyaninolal Hv: Hee As AF abe {oe wat ney magna bas ystems valine oui fy Hat fennel plyninntal Fine 9H fan, HE Hivvend Ha auele oulnttine aes ah eh PM, drape loti ae UHH aii, Kine te, ate laut Fevamploe of P prablann i d 4 ‘ i 1 {a Avon HH av Merwe ail linea auto A Finting. ontitinini aud masini eleriont th NP Problem Wivachiileonit (OSI anes HP fe aut a yaiions which can be solved tn non lujor satis joalynnnatal tie, A oes not mean non Junlynnital, Waban tay fon Deter naiatte Polynonntal tine ‘Hh nun-detoyministhe algorittiae operates In wo lane Nondotorminiatio (guessing) stage + flor input Hwvstanee 1, anne anlution string 8 ts generated, which ‘oa he tht va eantcate alt Dotwrmbuiatie (veritication) stage 11 and 8 are given fae ane Tipit to) thie ataternotastte algorithm, whieh fone "Wee 178 bra goution for input instance b folation (1 NP problems cannot te obtatned tn aly fine, hut given the solution, WC ean be vette gyi ne NP ne hilo al praitonns oF Py be POND. Ninapaarh prablon (042), Peavelting salesman Jnvahony ({n1)}, Hower at Hawt (0(2"= 1D), Hanutlionian eyete (O()) are examples of NP often, Inlonna are further classified tn NP-complete and Wig, WALL shows the taxonomy of aval eategor npletiy ehiase Proviens | ii on] Fig. 1.4.1 | Tavonomy of complexity clasNE Analysis of Algorithms (MU) 1.4.4. Difference between P and NP Q. Differentiate between P and NP. mn NP Problem Sr, Problem [Aa een ats Ach stands for Stands for Non- polynomial Deterministic Polynomial Problem can not be solved in polynomial time, but given the solution it can be verified in polynomial time. Problem be solved in polynomial time, can 3 NP prablems are superset P problems are sub set of NP problems. All P- problems are deterministic in ature, All NP problems are non- oterministic in nature. Ex: Selection Binary search, Sort, | Ex: Knapsack problem, TS! problem, 1.4.5 NP-Completeness and Reducibility Q. What is Reduction in NP-complotenoss proofs? What ‘are types of reductions? (7 Marks) . Explain Polynomial Timo Algor (6 Marks) 418 Inrodueton 1 Anja Su, Definition he polynomial time reduction solving problem A by the hypothtigy, solving aifferent problem B, polynomial time. Basically, the polynomial reduction showing that the problem Ais 01 hare 8 problem B. | = For example, we have sme hypoth which can sort numerical data in some point ‘The Input tothe algorithm can Only be i nen Suppose we have a new problem t0 sor ping, cities across the country. What can be done? = Suppose we don't have an efficient algorithm ig, string data, We can apply some hashing funcigg, names to map them to numeric Values, Now, "| identical to the first approach. = Thus, the polynomial reduction is the way of uni, problem into another problem whose solution found in polynomial time, = Reduction takes one of the three forms 1. Restriction 2. Local Replacement 3. Component design applying some transformation function on x So given an input x to A, reduction algorithm produces “yes” only Ifinput x to A returns "Yes Input x tor ‘oolon 109) tho probiom A, Input to 8 Tranetorm | Algorithm tor A Fig. 2 hus, we say As yoynoma ne edule to th input x © produced for A, © f(x) should be computable in poh reduetble to B, di BeP. ‘© Transformation function f{.) may as x would answi Iynomial time wted aS AHH. ASU nap Consider two declston problems A and B, Reduction from A {intermediate if 14.2 shows the scenario, es OF probley of x, Be P they ‘0 Bransforms input x of A to equivalent input fel ‘result {(x) to problem B such that (x) to Bret Yos/No | Yos/'No oulput for 8 foutput for A Agorhav aD) On mput x) Fon inputx + > Reduction some *ransformation function (,) such that mA to o ‘010 such that, input (x) to B produce th Wsueh f, Unction ¢ NAG p, al ists, we say Ais polyol However this does not imply #°! wn |1-19 Introduction to Analysis of Algorith Anaysis of Aigorthms (MU) shows the mode of reduction from one - Rg 143 problem to other. Eaypennte Out SAT OE SAT {scl elasement sit ‘conor do8on cclrelscenent Lesaleiacement | Component desgn Camgenant design Pea ee wow] [Seen] [Bese Sse) ks 8 [Resicion' ——PRastcton Kens Ter. Fig. 1.4.3 : Reductions used in some fundamental NNP-completeness proof 1.4.6 NP-Completeness Proofs @. What do you mean by NP-Compiete Problems? Give an example. (2 Marks) Q. What are the conditions to prove that a problem P is NP.Complete? (8 Marks) @. Write short notes on steps for NP_Completeness proofs. Eee 1fB< >A, implies B is reducible to A and Bis not harder than A by some polynomial factor. Definition Decision problem C is called NP-complete if it has following two properties : 1.Cis in NP, and 2Every problem X in NP is reducible to C in polynomial time, i.e. For every X € NP, X $C. ‘These two facts prove that NP-complete problems are the harder problems in class NP. They are often referred as NPC. Problem satisfying condition 2 is sald to be NP-hard, whether or not it satisfies condition 1 If any NP-complete problem belongs to class P, then P=NP. However, a solution of any NP-complete problem can be verified in polynomial time, it cannot be obtained in polynomial time. Method for solving NP-complete problems in reasonable time remains undiscovered. NP-complete problems are often solved using randomization algorithms, heuristic approach or approximation algorithms. Examples of NP-Complete problems y 2 3) 4) 5) 6) 7 8) Clique problem. 1.4.6(A) Vertex Cover Problem ee @. Specify one example of the NP-complete problem. ‘Also, ustty that why itis NP-complete. (10 Marks) 4. Prove that vertex cover problem is NP complete. (Eee ees Boolean satisfiability problem. Knapsack problem Hamiltonian path problem. ‘Traveling salesman problem. Subset sum problem. Vertex cover problem. Graph colouring problem. Definition Vertex cover of Graph G = (V, B) is set of vertices such that any edge (u, v) € B, incident to at least one vertex in the cover. In other words, vertex cover is a subset of vertices Vc V such that if the edge (u, o) € Ethenu € Vorv eV. ‘The size of the cover is a number of vertices in Ww Vertex cover problem is to find out such minimum size cover. A decision problem is to check if given graph has vertex cover of size k. = The simplest way of finding vertex cover of graph G= (V, E)is to randomly select the edge (u, v) € E and delete adjacent edges of u and v. — Repeat the procedure until the cover is found. For example, consider Fig. 144, Fig. 1.44 oxenie “2 Serre ey ER Ca (ab 6) form aang wn Let S represents the solution set. nti .2> a8 SREP 1: Select any random edge, let us select edge <1 shown inthe Pg 1.45. Remove the incident edert of vertex 1 and 2 Se, $* (1.2) Fig. 14.5: Atter electing edge <1, 2> ‘Still few edges are not adjacent to vertices in S, $0 60 08. Step 2: Let us now select edge <5, 6» Remove adjacent eon © 6» Sa.S= (1, Fig. 1.46 : After selecting edge <5, 6> 7 Stil few edges are not adjacent to vertices in S10 g0 0m. ‘Step 3: Let us now select the edge <3, 7», SoS={1,2,3,5,6) and all the edges are adjacent to at least cre vertex in S.SoS isthe cover of graph G. o—-® ~ However. Sts the cover ofthe graph but it may not be tminimum Instead of wlecting edge <5, 6> instep 2 wwe would have selected edge <3. 6>, it would have resulted in a minimum numberof vertices Theorem : Vertex cover is NP-complete Proof - Fe, prove that vertex cover bs MPcompee, we wy inate USAT problem to vertex cover problem. Lat ¢ pe the Boolean function with k clauses ~ For each Weral an’ in the clause, we create an vwm tn Fig, 148 Bag is truth setting cont ‘ertex cover must inchude at eas one of or 3 Fig. 140 = Vertex caver of such graph conta: ~ Let os build the graph 3-SAT Bootes Fig. 149 = ay verte cover wil ave tice i ae vertices trom (a,b. 6. Join the correspensy from triangle to edge 23 per cine where 9 is a pumber of variables cases ola ‘This Boolean expression generates the gra x, in Pig 14.20 bred arbed)irced Fig. 14.10 For given Boolean function 4» number of vartabies «4 number of clauses = 3 kensameto $2 vertex cover of this graph must costae 1° One verten of each trungie and one ve" eee oo of vertex cover{Wana o Algortms (MU) Fig. 1.4.11 4.4.6(B) Clique Problem @ Prove that Clique Decision Problem is NP-Hard, (7 Marks) Q. Prove that a clique problem is NP-complete (7 Marks) Problem = Clique is the complete subgraph of graph G. In complete subgraph, there exists an edge between every pair of vertices The size of a clique is given by a number of vertices init. Max clique is the clique of maximum size, Finding max clique is obviously optimization problem. Checking if graph G has a clique of size k is decision problem, ‘The optimization problem is to find a clique of ‘maximum size for given graph. A decision problem is to check whether a clique of size k exists for graph G. Q—OH SZ YI Graph Cique of tees Ciquo ot azes Fig, 1.4.12 : Graph G and its cliques Let algorithm CLIQUE(G, k) returns true if graph G has a clique of size k. We shall start with k = n,n ~ .-until CLIQUE(G, k) returns true, Theorem : Clique Decision Problem is NP- complete ~ To prove that clique belongs to NP-complete, we use V" as a certificate for graph G. Checking ifV'is a clique, can be done in polynomial time by checking the presence of edge for each u,veV". ‘To show that clique is NP-complete, we will show that 2- CNF-SAT S, CLIQUE, {Introduction to Analysis of Algority = Let @= CLA C2A CA 4G bea Boolean function of k clause, where each clause C, 1s in 3-CNE, Le. each clause has exactly three literals. We shall construct a graph such that Boolean function @ be satisfiable i and Ghas a clique of size k. The graph can be constr follows: Each vertex corresponds toa litera = Connect each vertex to remaining all vertices in remaining cause except for and —x Example: 02 (s:V4%2V 735) A(R Y VIA) ALY xv%) We shall show that the transformation @ to G is polynomial reduction. Let us consider that 9 has satisfying assignment, All literals x: in each clause are ORed with each other. = Soat least one literal in each clause is assigned value 1 If we pick up one such literal from each clause, it forms set V' of k vertices as we have k clauses in ¢. There exist an edge for each u, veV’ Fig. 1.4.13 NF satisfiability is NP-complete and it is reducible to clique, so clique is also NP-complete. 1.4.7. NP-Hard Problem @. Explain class : NP-Hard, Formally, a decision problem p is called NP-hard, every problem in NP can be reduced to p in polynomial time. = NP-hard is a superset of all problems, NPC is in NP-hard, but converse may not be true, NP-hard problems are at least as hard as the hardest (2 Marks) problems in NP.lysis of Algorithms (MU) 7 om 1rd problem in polyoma, Meee problems in NP if we can solve a tine, we would beable to save all the in polynomial time. ~ NP-hard problems do not have to be in may not be decision problem. F ~ Subset subproblem, travelling salesman problem 8 NPC and also belong to NP-hard. There are ce! i they are not Problems which belong to NP-hard but they NP-complete. : ~ A well-known example of the NP-hard problem Is Halting problem, ~The halting problem is stated as, “Given an algorithm and set of inputs, will itrun forever The answer to this question is Yes or No, so this is decision problem. ~ There does not exist any known algorithm which can decide the answer for any given input in polynomial ‘me, So halting problem is NP-hard problem. ~ Different mathematicians have given different relationship considering possibilities of P = NP and PaNp. ~The relationship between P, NP, NP-Complete and NP- hard is described in below Fig. 1.4.14 assuming that P # NP. This is widely accepted relationship among these complexity classes. ‘NP complete J Fig. 1.4.14 Ip. Even they lem are NP 1.4.8 Comparison between NP Hard and NP Complete ©. Differentiate between NP-hard and NPeompise algorithms, (4 Marks) Is Problem y Problem X ~ complete Hf NP problem! NP-compjyg My ¥ is reducible to X infreducihie = polynomial time, — 1s, | Ex.3 SAT problem. Hal rote te | 1.5 Analysis of Selection Sor ang Insertion Sort ___Insertion Sort 4.5.1 Selection Sort @, Explain selection sort and drive its conpiga (0m ky Like bubble sort, selection sort is also compan, in place algorithm. Selection sort is simple ayy obvious advantage of minimum swaps any algorithms. For list of size m, selection sor ps maximum (n ~ 1) swaps. However, quadratic and hence not accepted for a large list Funning tg ~ In every iteration 1, Selection sort finds the mies element from the unsorted list and swap it withe element in the list. At the end of the i® pass, i dene Bet sorted. Sorting starts from the beginning ~ At the end of the first pass, minimum element sexs the first location, in the second pass, second misc: clement seats on the second location and so on ~ Wf the list is Teverse sorted, bubble sort does n- 1s" in the first pass, whereas selection sort does ea SWap- Algorithm for selection sort is shown below Sr, No, NP-Complete NP-Hard, 1. JNP-complete problems|The NP-hard problem ‘aredecision problem. | might not be decision, problem, 2. |NP-complete problems are harder problems. NP-hard problems are the hardest problem, 3. [NP-complete problem] NP-hard problems may ny bein NP, ae are in NP. Aeovithm SELECTION SORT(A) Ais an array of size for Flton-tdy mine j ii + wendy (AG) < Almin) do min j nul end * (ALi) Almin)jorithms (MU) 23, alysis of Al Introduction to Analysis of Algorithen Ex. 1.5.1 : Sort the lotors of word “DESIG! in alphabotical order usi Soin, : ‘The following figure shows the simulation to sort characters of word "DI a Pass-1 Pass -2 =Ts[ 1 [8] mn=0 SELL [18] n=0 STeTsT Lele ]mine> [BETS e [eT e]mn-e Teles [ele]aneo PETS] Le] 8] mine Te] A] nines Plel['[si[s|n Diels] [e[N]min-e [io TG] N] mint PEL [ele] s]nn-0 PETS] LoL] mnae TS] *) in -o sTeTiTe[a[s]om-o PLElsp fe [a]nn-c [elpels[ Tele] m-o No swappia is oqud $109 5) Pass - 5 Output inet min=1 E N] min=s Tal [s[* N] min Tbs) No swapping is required ‘Complexity analysis Put n= n-1 inabove equation, — Similarly bubble sort, selection sort also dose the same number of comparisons. It iterates both loops Irrespective of input data pattern. = Unlike bubble sort, selection sort cannot detect sorted sequence. So running time of selection sort In best, average and worst case is O(n’). We can come to this conclusion by adding number of comparisons just lke bubble sort, but here we use recurrence equation to T(n-1) = Tn-2)+ (0-3) Put value of T(n~ 1) in previous equation of T(n). Tn) = T(n-2)+(n- 1) +n Put n=n-2 inabove equation, ‘T(n-2) = Tn-3)+n-2 Put value of T(n - 2) in previous equation of T(n}. 4.) = T(n-3)+(n-2)4(n-1) +0 ‘After k iterations, derive the complexity. = Let's assume T(n) defines the running time to solve the Tn-K) = Thn-k-1)+(n-1) problem of size n. In selection sort, after each iteration, T{n) = Thn-K) + (n-k #1) + (n-K+2)+ = ‘one element gets sorted and problem size reduces by +(n-dtn When kapproaches to n, one. For each problem of size n, inner loop iterates n times. So recurrence equation for selection sort can be written a5, T(n)=T{n- 1) +n Tn) = TE) +142434—+(n- Dem +1(0) = 0, because it is running time of problem of size zero, and no effort is needed to solve this problem T(n) = 1424340040 Se atnatetst¥F Anaiyss of Algotns (MU) = 0(max( T(n) = O(n’) Best case | Average case | Worst cas O(n?) O(n?) O(n’) 1.5.2 Insertion Sort ‘Q._ Explain insertion sort and darive ita comploxly. CARO ‘We will analyze insertion sort algorithm in depth and for rest of the algorithms we will ind out its running time from its structure, ts obvious observation that to sort hundred elements Will take more time than just sorting five elements. Running time is function of input size, Insertion sort uses the analogy of sorting cards in hand. Teworks ina way people are used to sort cards. One card 1s removed at a time from the deck and itis inserted at Correct location in hand. Upcoming cards are processed in same way, To insert new card, all the cards in hand having value larger than new card are shifted on right side by one New card is inserted on space created after moving some k cards on right side. Insertion sort in inplace algorithm, it does not require extra memory. Sorting is done in input array ise, in iteration k first k elements are always sorted, Running time isthe number of steps required to solve Problem on RAM model Each instruction may take different amount of time, Let us consider instruction isc, the cost of {Introduction to Ay ‘Aipurthm Insertion Cost J Ainarray of size for} 2tndo % ey © ALT a icin} _ n-1 bile (i> 0 88 Ali]>key) cy Atit Ue Ali] Ali +1] — key end ° Complexity Analysis ~ Slze of input array is n, Total time taken by al the summation of time taken by each of its instn 2 Ma) = eym¥ ey (n= 1) 465+ (n= 1) ees De a a te te Sew ecinet = a ~ Best ease analysis: Best case gives the lower ‘running time of algorithm, Limvenee of data, running time cannot be less means for any ot Dest case running time, Best ease for inset ects when data is already sorted. For thé © condition in while loop will never satisfies and UE Lso we Wrcienseelaetysqefatiea E191-25 Introduction to Analysis of Algorithm WF Analysis of Algorithms (MU) Where, n Bp terere tt (a= atimes) = j=2 cqemt cys —C2 + Cy N= C5 + Cy Cy + on= Cy ey #2 + Cy + Cy) MN (C3 + 4+ C4 + C7) n+b Which is linear function of n O(n) — Worst case analysis : ‘The worst-case running time gives an upper bound of running time for any input. It indicates that for any arbitrary sequence of input data, running time of algorithm cannot get worse than its worst case running time, Worst case for insertion sort ‘occurs when data is sorted in reverse order. So we must have to compare Alj] with each element of sorted array AlL..J- 11. Sjezsseae—on j=2 = (1+2+3+.¢n)-1 > n-1 afn+t) | and, D) G-1)=1+24+34+.+n-1 j=2 =5qn-1 2) a Te) = center (a-D+e-(n-N+e-] DI n a tes: G- 1) tee DL G-1) ter (a-1) ja2 j=2 = center(n-1)4cy-(n-1) +e, mate rete) = anttbn+c which is quadratic function of n = O(n?) = Average case analysis : Average case is often roughly, as bad as worst case. On an average, half of the elements ‘are greater than Alj] and other is less than that. So, t,= / 2) It agai ‘Average case running time of insertion sort is O(n’). turns out to be quadratic function of n. ‘Average case | Worst case O(n?) O(n?) O(n) Ex. 1.8.2 : Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort. Soin. : Initial array of alphabets E,X}A[M = One by one element is scanned from array. In iteration ky if incoming character is greater than previous element, then copy newly read character at location k. — If e* element is smaller than (k - 1)" element, then keep movie elements on right side until we get element smaller than newly coming element. Insert new element in created free space. Step by step simulation of insertion sort is shown hel TechhanaledgtAnalysis of Algonittyns (MU) | Stey tread HH is the any chatact | | xtep 2 Read S sexe gin | GREED ERPEEET) t \ hihi, sus wo AIIM OF wis required | sian 3 ond ee oe ee ate ee sine move | 3" position tn array. Gompare A with E Agaity | li ana = : : em wh ng | A and E are out oner, so move 6 on 2" aro inorder, 0 insert M20 3 vacant ogy position in array. Now there arene tor elements (eft iy array, so insert Aon 1" vacant position | ~~ | ter aad Stop: Real PP onl Nate out of ander, se move Non 5° position inv arr | three characters on right by position i + Compare Pith M-They are in order, so insert P on 4! vacant pasion Lana" vacant position ule] Step 7: Read EBs less thi four characters on right by position and insert array is sorted. Mand L. se moveall | Stop 0 No more elements are left the array Eon 3" vacant position Crh x GEEDP TT 411,717, 3,9, 20, 85, 9> Soln. : Initial array of numbere = One by one element is seat from array: tn ter tration Kk, Af inc copy newly read character at location k ming characteris greater than previous elm ~ Wi element is smaler than (= 2)" element, then koe N keep movie newly coming element. Insert new element in ere created tree y pac element yl nts On righ side unttt wo get element 5" 7s of Algorithms (MU) op by step simulation of inst Step 1:Read 11, 11 is the only number, so shifting or | Step 2: Read 7. 7 and 11 are out of order, so move 11 swapping is not requil on 2%" position in array. Now there are no more elements left in array on left of side, so insert 7 on 1" vacant position Pll*[: Step 4:Read 3, It is not in correct position, so shift Pele Tels fo [=[=[> Step 3: Read 17, It is in correct position, so sl swapping is not required, elements greater than 3 on the right side by one position until the correct location for 3 Is found. Step 5:Read 9. It is not in correct position, so shift | Step 6+ Read 29. It is in correct position, so shifting or elements greater than 9 on the right side by swapping is not required. one position until the correct location for 9 is found 17 | 29 | 05 | 9 ead 85. It is in correct position, so shifting or | Step 8 Read 9. It is not in correct position, so shift swapping is not required, elements greater than 9 on the right side by fone position until the correct location for 9 is Step 7+ found.Recurrence 0d. The substitution method - Recursion tree method - Master meth Introduction Define recurrence equation. What is the use of? (4 Marks) = Time complexity of certain recurrence cans, solved using master methods. 2.1_The Substitution Method Definition : Recurrence equation recursively defines a sequence of function with different argument. Behavior of recursive algorithm is better represented using recurrence equations, — Recurrence are normally of the form Tn) = T(n-1) + f{n), forn> 1. T(n) = 0,forn=0 (2.1.4) ~ The function f(n) may represent constant or any polynomial in n. ~ Equation (2.1.1) is called recurrence equation. T(n) is interpreted as the time required to solve the problem of size n. On recursively solving T(n) for n = n - 1, recurrence will ht tothe base case T(n) = 0, forn = 0 Values will be back propagated and the final value of T(n) is computed. ~ Recurrence of linear search / factorial Tn) =T(n- 1) +1 = Recurrence of T(n)=T(n-1) +n ~ Let us discuss various methods to so recurrence equation. selection / bubble sore Wve the = Recurrence relation can effectively re Present running time of recursive algorithms, the @) Explain substitution method with example. > (iow Q. Write a short note on recurrences. TEST . Explain recurrences and various methods i; ecurrences. z _E_ C Linear homogeneous recurrence of polynonid ‘sreater than 2 hardly arises in practice. inthis se shall discuss two unfolding methods which are wi tosolveallarge class of recurrence. Risalso known iteration methods. There arett tosolve such equations. Ways to Solve Unfolding Method () Forward substitution (i) Backward substitution 241.1 : Ways to solve unfolding metho 9 Forward substitution Fig, Forward substitution method finds the so sulk probem using bese sondvan A soi ‘er Problem is obtained using the previous! ©" Solution of the g js mall lem, This process ! aa ler problem. This pr the solution for problem nis achieved:‘Analysis of Algo oive the recurence of linear arch using ex 200 forward substitution method, soln. Recurrence of linear search is, n(n) = T= 1), forn> Oand ‘1{n) = 0, forn=0 (Base condition) Inductive case of the recurrence Is n(n) = Ten 1) +1 (1) Forward substitution finds the solution of T(n) by solving the progressively bigger problems, starting from smallest possible case. Here, the base case is ‘r(n) = 0,forn=0 =2T(0) = 0 2) put n= Lin Equation (1) to solve problem of size 1 cpn(t) = T= 1) 1 = TCO) 41-041 (From Equation (2)) 70) =1 Forn = 2, 72) = pa-aet=Taysretet TQ) =2 Forn = 3 T(3) = reg-1) +2272) +1=2+7 21) = 3 ‘After k substitutions, Tk) =k And fork = 1% T{n) = O(n) ii) Backward substitution n-i ‘This method substitutes the value of » bY ler and smaller problem It to solve smal recursivel vvorks exactly in reverse order OF forward substitution ca za : sove the recurence of moar search using forward substitution method Soin. : Recurrence of inear search I any = Tn th forn> oand -r(n) = 0,forn=0 (Base condition) Inductive case of the recurrence is oe Yo) = Tn-1) +1 __The problem canbe sled I (0 = 1) snow. 7 ‘T(n~ 1), substitute n= n~1 In Equation (1), be ‘T(m-1) = T(n=2)41 Replace this T(n ~ 1) in Equation (1) n(n) = [T(n-2) 41] +4 = T(n-2)+2 (2) ‘The problem can be solved if T(n - 2) Is known, To find 2), substitute n= n - 1 in Equation (2), T(n-2) = Tn-3)+1 3) Replace this T(n - 2) In Equation (2) a(n) = [T(n-3)41]+2= 79-3) +3 ‘After k substitutions, T(n) = Tin-K) +k, Tomatch the base case assume that k=, T(n) = Tenn) +n= TO) =n= 04" (From base case) a(n) = O(n) yen we recurrence equation T (n) = T (0 Ex. 2.1.8 : Soh packward substitution method. using forward substitution and ‘Soin, : Backward substitution Given the recurrence, ten) = T=) +h wl) peplace nby nin Equation (1) =o T(n- 1) = T(n-2)+(0-1) a2) put it in Equation (1) “etin) = (TO-DO DIM peplace n by n~ 11m Equation @ qn-2) = TE0-3)+ 0-2) 8) =T(n) Srn-aye(n-aee-yen 4) “after k substitutions: Tn) = ren-W een kD a (neha aye na" When kapproaches (0% en) = THES (neem =T(0) = prenen sy /22 0012) 00) so, T(n) = Ol) an __ |23 BF Analysis of Algorithms (MU) Forward substitution Tn) = T(n-1)+n Forward substitution finds the solution by replacing the solution of smaller problem into large problem. Forn= 0,7(1)=1(0) + Forn= 2,1(2)=T(1)+ Forn= 3,1(3)=T(2)+3=3+3 Forn=4,1(4)=1(3)+4=6+4= After k substitutions, Forn=K,T(n)=T(k-1)+k=1424+3+..+k When k approaches ton, T(n) = T(n-1)+n=14+2+3+..4n=3n So,T(n) = O(n") Ex. 2:14 Solve folowing recurrence using iteration method. Te) Soin. : (n-1)4n* Given that, T(n) = Tin- 1) +n* Substitute n by n= 1 “T(n-1) = T(n-2)+ (0-1) 2 T(n) = [T(n-2)+ (n-1)']+nt ‘Substituting n by n ~ 2 in main recurrence, T(n-2) = T(n-3)+(n-2)¢ 2 Ten) = [T(n-3) + (n-2)4] + (n= 1) nt After iterations, T(n) = T(n-K)+(n- ks 1's (ks Ihe n Fork = n Tn) = T(n-n)+T(n~n41)'+(n-n 426404 n = TO)+18+ 2443s ents Sis “T(n)_= O(n') Ex. 2.1.6: Solve folowing recurrence using iteration tt at twa 2Mn-t) mot Soln.: Given that T(n) = 2T{(n-1) Substitute n= n-1inthis equation T(n-1) = 2T(n-2) n-2in main recurs Substitute n = “i T(n-2) = 2T(n-3) T(n) = 27[2T (n-3)] = ‘After k iterations T(n) = 2T(n-K) Whenk = n-1 Ta) = 27g (aan t= 2 T(a) Ex. 2.1.6 : Find out the time cox ‘equation as follows : (i) Tia) = T(nv2) + 4 (i) T(n) = 2T(rv2) +19 ‘Also explain the searching/sorting algorithms. Soln. : above equation: i) Tea) =T(n/2)+1 Given recurrence is of binary search In every iteration, binary search does on and creates the new problem of equation of binary search is given as, To = T(8) +1 T(n) = 1,n= Lie. only one comparison there is only one element in the arra case. This is the boundary condition fo Uussolve this by iterative approach, Toy = T(B)e1 Putn = n/2 in Equation (1) to find T(0/2) 1(3) «7(8) 1 Substitute v; 2 ‘alue of T(n/2) in Equation (1) 2T(n) = (3) Putn =n/2 Equation (2) to find T(0/4) (3) «2(8) 4 4 Substitute value of T(a/4) in Equation (3) +2 wt oof Algorithms (MU) a wees Given recurrence is of merge sort. In merge sort, after each iteration, the list is divided into two parts, and problem size reduces by half. Unlike binary search, in merge sort, we will get two sub problems after divide stage. After sorting two sub lists of size (n / 2), combine procedure takes n comparisons.So, total running time of merge sort is given by {2 sifnst TE 0+} g(8)-r(Q)somece soe Where art (3) = costfor solving left sub list 2 ‘And second 1(3) = cost for solving right sub list Tin) = ar(3) +0(n)+0(1) 2.T(n) (2) Tha) = Tn) Suppose, n (2) slogan men 7 (1) + m-fogsn bu TQ) = the lst of size 1. | because no comparison is needed to sort 0 (log: n) 2.2 Recursion Tree recurrence is the set of function: tree represents the cast of 20 family of problems belonging to Summation of cast across all bra el i. And su total cost at lei ng Co! the total cast for solving the recurrence. Let us consider the recurrence T(n) = Let us derive the recurrence tree step by step as Fig. 2.2.1. Problem is divided in to two sub pro’ of size n/2. The cost of salving problem of size n shall keep exploring the tree until it hits the bo! condition. es Tina) T(n) (a) Tin) (b) First level expansion of T(n) —— ania} etn Asus ae Tie) Teva) Tyee) Tirvd) (c) Second level expansion of T(n) Fig. 22.1 : Recurrence tree formulation “At every level, problem is being reduced by factor of size 2, Size of sub problem at level is n/2- Hence, size of sub problem becomes 1 when n/2' = 1. Thus, tree has logsn + 1 level. (depth vary from 0 to login). Fully expanded tree is shown in Fig. 2.2.2. EE teatonaiestee Sh cot vat at qt mom (aed A Fig. 2.2.2 : Fully expanded recurrence tree ‘We will compute the cost at each level in above tree. AS {tis a binary tree, number of nodes at depth { would be 2! Cost at depth i would be c(n/2'), Cost of base problem has size 1, so we can consider the cost of T(1) as constant. Height ofthe tree is logan. By summing up the cost at every level, we can find the cost of whole problem. 10) = e+ Qare( ate +O mem Togen=1 XZ Bars omy 2n? +8 (n) on’) Ex. 2.2.4 : Solve the following recurrenco? a Ten) TO) (2) +7 (aid) +T (x) +n, Sol Recurrence tree foi . elven recurrence equation i own elow a 4 = tn, ee ee : i “om TO) = TOM) + T/A) eT (4/0, Te) $e C/AIN* 770+ C/0P a4 4 5, Ins the height of tree wh TE) = O(n) ‘Thus, 2,3° Master Method ee @. Explain three casos of mastor thao Q, Explain master method with example Q. Write a short note on recurrences MU= Dec. 18,19 . Defina master theorem, @. Explain recurrences and various methais recurrences, @. Write a short note on Master theorem, Ee ~ Divide and conquer strategy uses recurso complexity of the recursive prog recurrence, In the chapter 3, we ha sti methods for solving the recurrence. The mast 's offen suitable to find the time complexity eft Problems. Master method is used to quickly the form T(n) = ap () + Fn), Master solve the rer the solution without Substituting the v: Inabove equation, ® © Size of the problem * © Number of sub problems created in, Pecursive solution mb = ize of each sub problem, 0) = Work done outside recursive This includes cost of division of __ Problem and merging of the s0 ’& analysis of Algorithms (MU) variant 1 tef{a is the polynomial of degree d and 1. T(n)= @(n*logn) If a=bs 2 em) = O(n) ea >be 3, T(n) = O(n!) If a 0, then a(n) = 0( n!984) 2. it ffn) = @( n!8 ) , then (0) = O(n! stogn ) 1 FO) 3. if fay = (08'S), ror some constant ¢ > 0, and ifaf{n/b) Given equation is of the form T(n) = a 7(2) +f) Where,a=1,b= 3 and £(n)=1 lB, 1 logs = © (n!°8), so solution of recurrence would be, T(n) = © (n!°%. Jog") = © (log") ©. 23.2: Solve following recurrence equation using master method: T(n) = 3T (2) +n bean Soln,: Here, F(n) a Given equation is of the form T(n) =a 7() +E(0) Where, a = .b=4andf(n)=nlogn O(nI8) = oH) = 0(n8™) Since, f(a) = Q(n®™*** J. with ew ae We af(ayd) S calm) shall check the regulary af(ayd) = 3(n/4Mloginya) 3(n/4Mlog(n/4) S (3/4)ntog W= on), with ‘Thus, it satistles the oo hence Soln. : Compare this equation with Tn) «aT P) eG) Whereas 4.b=2.£(n) = nds t, where dis the degree of polynomial, vt = 2t Were, = a = bY So, T(n) = © (n'logn) = © (log). Ex. 234 : Solve the falowing recurrence using. master mathod. Tin) = aT (3) ont CUE Soln, : Compare this equation with Tea) =a (ft Here, a= 8b= 2 and f(n) =n dee Checking relation between a and? Asam bi (lee roy (a8) -0(8%) -0( 0) ofa!) oon solution to this Hauation fs given as, Ex, 2.9.5 method: T (Nn Soho the following recuiTENE® ung Master aT (nayen’, Soln, + Compare given recurrence with equation with pl roy=at(2) +t Werea4yb= Sand t (nye aka Checking relation between a and bt Asa

You might also like

• Computer Organisation and Architecture Handwritten Notes

  

  0% (1)

  Computer Organisation and Architecture Handwritten Notes

  152 pages
• DBMS Techmax PDF

  

  50% (4)

  DBMS Techmax PDF

  276 pages
• Em4 GVK

  

  60% (5)

  Em4 GVK

  501 pages
• Techmax of Computer Networks

  

  73% (11)

  Techmax of Computer Networks

  368 pages
• Techknowledge Publication: Artificial Intelligence and Soft Computing

  

  No ratings yet

  Techknowledge Publication: Artificial Intelligence and Soft Computing

  336 pages
• MP Techknowledge

  

  100% (2)

  MP Techknowledge

  175 pages
• Software Engineering Techmax Semester 6 Computer Engineering

  

  88% (8)

  Software Engineering Techmax Semester 6 Computer Engineering

  244 pages
• Web Technology Techneo Sem 5

  

  No ratings yet

  Web Technology Techneo Sem 5

  241 pages
• Internet Programming Techknowledge Sem 5

  

  100% (1)

  Internet Programming Techknowledge Sem 5

  241 pages
• DSGT TechNeo

  

  67% (3)

  DSGT TechNeo

  226 pages
• AOA

  

  100% (1)

  AOA

  219 pages
• Theory of Computer Science by Techknowledge

  

  0% (1)

  Theory of Computer Science by Techknowledge

  589 pages
• Theory of Computation Technical Book 2021

  

  100% (1)

  Theory of Computation Technical Book 2021

  341 pages
• CSS Techmax

  

  83% (6)

  CSS Techmax

  392 pages
• Oop by Anonymous

  

  100% (1)

  Oop by Anonymous

  236 pages
• Machine Learning 2019 (TechNeo) - 1

  

  No ratings yet

  Machine Learning 2019 (TechNeo) - 1

  158 pages
• Tafl Unit 1 Notes

  

  No ratings yet

  Tafl Unit 1 Notes

  44 pages
• Computer Graphics PDF

  

  No ratings yet

  Computer Graphics PDF

  308 pages
• OS Techmax

  

  100% (2)

  OS Techmax

  98 pages
• Tech Max

  

  No ratings yet

  Tech Max

  51 pages
• Software Engineering Techmax - Compressed

  

  No ratings yet

  Software Engineering Techmax - Compressed

  244 pages
• Tcs (Theory of Computer Science) - Compressed

  

  100% (3)

  Tcs (Theory of Computer Science) - Compressed

  589 pages
• DWM Toppers Solution 2018 PDF

  

  100% (1)

  DWM Toppers Solution 2018 PDF

  107 pages
• (DBMS) Database Management System Text Book

  

  No ratings yet

  (DBMS) Database Management System Text Book

  296 pages
• CNS TechMax

  

  0% (1)

  CNS TechMax

  99 pages
• DLCA TechNeo

  

  100% (1)

  DLCA TechNeo

  285 pages
• AOA Techmax PDF

  

  100% (2)

  AOA Techmax PDF

  173 pages
• DSGT Tech Knowledge

  

  100% (2)

  DSGT Tech Knowledge

  167 pages
• Internet Programming Techneo Sem 5

  

  No ratings yet

  Internet Programming Techneo Sem 5

  241 pages
• Iot Tech Neo

  

  100% (1)

  Iot Tech Neo

  177 pages
• Statistics TechNeo

  

  100% (1)

  Statistics TechNeo

  226 pages
• DBMS (Decode)

  

  100% (1)

  DBMS (Decode)

  175 pages
• Operating System (Decode)

  

  No ratings yet

  Operating System (Decode)

  117 pages
• AOA-Paper Solutions

  

  No ratings yet

  AOA-Paper Solutions

  68 pages
• DWM Tech-Neo Book

  

  100% (3)

  DWM Tech-Neo Book

  197 pages
• Analysis of Algorithm by Techknowledge

  

  No ratings yet

  Analysis of Algorithm by Techknowledge

  221 pages
• System Programming and Compiler Construction Techmax

  

  No ratings yet

  System Programming and Compiler Construction Techmax

  408 pages
• QA

  

  No ratings yet

  QA

  264 pages
• ML Techmax

  

  100% (1)

  ML Techmax

  202 pages
• SPCC - Tech Max

  

  0% (1)

  SPCC - Tech Max

  408 pages
• Microprocessor Module-5 Question Answers

  

  No ratings yet

  Microprocessor Module-5 Question Answers

  8 pages
• Cloud Techmax

  

  No ratings yet

  Cloud Techmax

  125 pages
• Artificial-Intelligence-Toppers Solution Book

  

  No ratings yet

  Artificial-Intelligence-Toppers Solution Book

  108 pages
• Data Warehouse and Mining Techmax - Compressed

  

  No ratings yet

  Data Warehouse and Mining Techmax - Compressed

  429 pages
• M4, Extc, Kumbhojkar

  

  0% (1)

  M4, Extc, Kumbhojkar

  306 pages
• Daa

  

  No ratings yet

  Daa

  68 pages
• Bda Sem 7 Book

  

  No ratings yet

  Bda Sem 7 Book

  188 pages
• DMW Ebook TechKnowledge

  

  No ratings yet

  DMW Ebook TechKnowledge

  216 pages
• Daa Notes Complete Aktu

  

  100% (1)

  Daa Notes Complete Aktu

  203 pages
• Distributed Computing Tech Knowledge

  

  100% (1)

  Distributed Computing Tech Knowledge

  149 pages
• DC Techmax Everything You Need To Prepare For Distributed Computing Subject in The Final

  

  No ratings yet

  DC Techmax Everything You Need To Prepare For Distributed Computing Subject in The Final

  193 pages
• Cryptography and Security Systems (CSS) Toppers Solution

  

  0% (1)

  Cryptography and Security Systems (CSS) Toppers Solution

  104 pages
• DBMS Technical Publications Chapter 1

  

  100% (3)

  DBMS Technical Publications Chapter 1

  24 pages
• BDA Techmax (Searchable)

  

  No ratings yet

  BDA Techmax (Searchable)

  150 pages
• Dsa Sppu PDF

  

  No ratings yet

  Dsa Sppu PDF

  617 pages
• Computer Network Techmax

  

  No ratings yet

  Computer Network Techmax

  368 pages
• Daa Unit 1 Notes

  

  67% (3)

  Daa Unit 1 Notes

  67 pages
• Analysis of Algorithms: Syllabus

  

  No ratings yet

  Analysis of Algorithms: Syllabus

  100 pages
• Analysis of Algorithms

  

  No ratings yet

  Analysis of Algorithms

  2 pages
• Seminar Report Format (1) Shreyas666

  

  No ratings yet

  Seminar Report Format (1) Shreyas666

  16 pages