Scribd
Upload
8 views40 pages

ADA 5th Module

The document discusses the limitations of algorithm power, highlighting that not all problems can be solved by algorithms, some require non-polynomial time, and others have efficiency bounds. It introduces decision trees as a method to analyze algorithm efficiency and explores the classification of problems into P, NP, and NP-complete categories. Additionally, it covers specific algorithmic problems such as the Hamiltonian circuit and subset sum problems, illustrating their complexities and potential solutions.

Uploaded by

Karna Shaiva
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
8 views40 pages

ADA 5th Module

The document discusses the limitations of algorithm power, highlighting that not all problems can be solved by algorithms, some require non-polynomial time, and others have efficiency bounds. It introduces decision trees as a method to analyze algorithm efficiency and explores the classification of problems into P, NP, and NP-complete categories. Additionally, it covers specific algorithmic problems such as the Hamiltonian circuit and subset sum problems, illustrating their complexities and potential solutions.

Uploaded by

Karna Shaiva
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Limitations of Algorithm Power ——_—_—........____ 41.1 Introduction So far now we hav. died many algorithms. we have seen how these algorithms play_an_ important role in solving a variety of problems. But it is not possible that every problem could be solv 30 i y_ some algorithm. That means there are certain problems that could not be solved using any algorithm. In other words, we can say that lh of algorithm is limited to some extent(It is seen that power = algorithm is limited because of following reasons - 1. There are some prob! Se geen sen) Soto roblems which can 1{ot be solved with aigorithms. oe "2, There are some problems that can be solved by algorithm but such solving is not within polynomial time. ali 3, There are some problems that can be solved in polynomial time but there are Tower bounds for efficiency ofthese algorithms chapter we will discuss about limitations of algorithm, power, First of all “understand of t_of 1ods for establishing Then we will get introduced with the concept of decision trees by ithms can be studied. Finally, we will end up r-Bound Arguments ection we will first understand "how to obtain lower bounds?" Basically er bounds means : estimating minimum amount of work needed to solve = we try to obtain lower algorithm we eae of any algorithm that may ae the problem. Such a prob! unknown nding ples in which lower bounds of corresPo! mple : Following are the exam| ——— n be ol o 7. and Design of Algorithms 11-4 Limitations of aig parisions needed to sort an array of size n, Anal / 1, Number of comj /, 2. Number of comparisions that are required to search a desired ¢, sorted array. = 3. Number of additions needed to ad ney of particular algorithm there are two ways - id two n x n matrices. To obtain efficie Step 1 : First establish the asymptotic efficiency class for the given problem, Step 2: Then check where the class of given problem fits in the efficiency classes. In other words, whether the problem lies in line; logarithmic or exponential category of efficiency class, is to be checked. For instance : Consider the problem of sorting algorithms, if we sort method for sorting whose efficiency is quadrat .n?), then we “a Weig heap sort) with the efficiency of O (nlogn) efficiency class insertion sort is proved t Whenever we try to find an efficiency algorithm with other! algorithms that at® | example if we want to decide the « efficiency to Tower of Hanoi probl insertion sort. This is basically becat to be iple is oblem > find is an 4 out e the js and Design of Algorithms 44 _7 Limitations of Algorithm Power Bipecision: Trees 1 bs " sorting _and searching algorithm, are based ston all er is usually made on input ita ead oes rf comp of such algorithms which salled Decision Tegan te ee Decision Tree, compar a tree Tesults of the algorithm, may be a case that we Set more number of leaf nodes than actual outputs ae This because, we can obtain results in decision trees through a different chain Ee ns, ee eaonle © Consiciersa! decision tres drawn eo for finding largest number among variables x, y and z. The simple graj notations in decision Trees the three q 5 = Condition, Transition Analysis and Design of Algorithms _1 From above drawn decision tree following observations can be made - Let, h be the height of a tree and n be the total number of leaf nodes ——————ere Then h > [logn’] {Note [log n ] indicates the rounded y ge se In other words we can also state that 1 poses the binned esr Gore ATE information’ _ about the autput_of algo ne information” theoretic lower bound. There are two id those i Fig. 11. : ig. 11.3 Decision tree for 3 element insertion sort x this tree the From worst case number of comparisions can be obtained as - Z : Cin) > [log n!] Aer Using stirling’s formula - ae* Plog nl] = Gog 1) + dog 2) +... + (og n) 2 Plogni] = logs V2an (n/e)” ~\er i logan , log2n = nlogyn—nlog, e+ 82" +8 : ae E aie 2 = nlog.n s at least nlog.n comparisions are necessary to sort an arbitrary list of Using the decision tree, only, we can compute average number of Let us draw the decision tee for insertion sort of 3 elements Limitations of Algorithm, P Analysis and Design of Algorithms 11 - 10 11.3.2 Decision Trees for Searching A Sorted Array When a particular element has to be searched from a sorted list or elements decision trees can be drawn, We will consider an example of binary search ang ~ the lower bound using decision trees. As we know, the worst case for binary seug Ozma = [logn |+1 a C(n) = Plog (n+ 1)] Now to obtain number of comparisions using decision tree consider that there a four elements arranged in ascending order [zeae « [orn ee 1 2) als] *Ohinsg U4 al2) raft | right sublist sublist Mid Fig. 11.5 [Link] draw a ternary decision tree then for n number of elements there will approximately (2n + 1) leaf nodes. The height ternary tree with n nodes will be log,n, Thus we will obtain lower bound on number of worst case comparisions ( C(n) > [log;@n+1)] __ total number of leaf nodes. The ternary decision tree would be here ae 5 sor bese a jn te nub Cin) 14, NP and Re ae two anatysis and Design of Algorithms 11-14 Limitations of Algorithm Power yf we redraw the above Fe ones such ternary tree by eliminatit pecomes binary ones such a binary decision tree is eee ‘ Now there are 5 leaves for n = 4 nodes. the number of worst case comparisins would be : Fig. 11.7 Binary decision tree ‘That means n + 1 leaf nodes. Hence lower don Cin) > [login+D] P. NP and NP-Complete Problems e in which a problem can be classified. The first_grouj that can be solved in polynomial time. For example: searching he problems that can_be soivee Fe ment from the list O(logn), sorting of elements O(logn)- d nsists of problems that can be solved in non-determin i Fea a rr fem O(2") and Travelling Salesperson iple : Knapsa er dem. inistic ign of Algorithms 44-12 Po Problems that. can be solvedisin Polynomiay olynomial): lement, Sorting of elements, Ms VAM pair Analysis and Desi «Definition of ("P” stands for P% Examples - Searching of key ¢l path. «Definition of NP - It stands for “on-deterministic polynomial “non-polynomial”. Hime”. Ny ie, ! that NP does not stand for Examples - Travelling salesperson. problem, Graph coloring problem, Hamiltonian circuit problems © The NP class problems can be further hard problems. ‘Computational complexity problems categorized into | i aq BS i) It belongs to class NP eli) ii) every problem in NP can also be sol + If an NP-hard problem can NP-complete problems can a it fi ind Design of Algorithms 11-413 Limitations of Algorithm Power © Stage algorithm - The non determi algo: hm is a tw, Non deterministic (Guessing) sta e- Bircitot astalcansiaxts Roitites Benerate an arbitrary string that can be Deterministic (“Verification”) sta, aie i candidate solution and the ites Rate Fs candidate solution represents actual so a‘ Algorithm Non_Determin() // A{i:n] is a set of elements Be it takes as input the bI ae Problem and returns yes if the Mme Dave +o) determine the index i of A at which element //located. ie { // The following for-loop is the guessing stage for i=1 to n do Afi] == choose (i); | // Next is the verification(deterministic) stage if (A[i] = x) then write (i); success (); rministic algorithm there are three functions used - above given non dete aoe a of the element from given input set. se ~ arbitrarily chooses one indicdtes\ the unsuccessful cess — indicates successful completion. not ordered then . hen A is is erministic complexity O(1), algorithm is argentais has a complexity 2 (n): completion. se((wt>m) oF (Profitept)) then OF success ();//maximum profit earne: d ) The time required by a non dete minimum number of steps needed to rea multiple choices from input set leading deterministic algorithm is of complexity O fic algorithm with some input set is 10 a successful completion if there are successful completion. In short, a non where n is the total size of input. fy 11.4.2 NP-Hard and NP-Complete Classes As we know, P denotes the class of all deterministic polynomial language problems and NP denotes the class of all nor-determinisic polynomial language problems. Hence Pc NP. «The question of whether or not P = NP problem in the computer scinet jle. Problems question of holds, is the most famous outstanding ceca Problems whi known to lie in P are often called of i which SR ict P are often termed as intractable. ‘Thus, the Coping with the Analysia and Design of Algorithny 12.3.2 Algorithm Algorithm Quee" in) eription! gorithm 19 £0% implementing s/eropiem ai rhis al //queen's problem syinput: tetal mu umne-2 to 1 do ber set queen's for col ‘ row, column) ) #1 —_—— Af (p: ‘ ‘poard [row] cglumn//no Fg sae so. oe if(row=n) then//dead end — print boardin) Zolu 1 2 3 4 1 . 5 Q - 2 Q : “ 3 = 4 = Q 4 + Q - Press any key to continue... ee i=» Example 12.1 : Solve 8-queen’s problem for a feasible sequence (6, 4, 7, 1). Sai QR — 1234 Solution : As the feasible sequence is given, we will place the queen's accordingly and then try out the other remaining places. 1 2 3 4 5 6 FY 8 A - 2 '2 3 4 5 6 u 8 ‘Analysis and Design of Algorithms _12- 16 onal conflicts can be checked by following formula~ «= (k, I) are two positions, Then F, and P are the Poston, or Let, P = Gi, j) and Py that are on the same diagonal, if jaja k+l j-j=k-1 Now if next queen is placed on (5, Coping with the Algona 2) then Qa B-queen's with feasible solution (6, 4, 7, 1, 3, 5, 2, 8) 2.4 Hamiltonian Circuit Problem In this section we will first understand “What is Hamiltonian circuit 7" Then we discuss "How to solve Hamiltonian circuit problem using backtracking ?” Problem statement : Given an undirected connected graph, and there are any two Aand B, then there exists a path from A-B and back to A such that each vertex visited exactly once. Such a path ina giver graph-is-called Hamiltonian circuit. For example : Consider a graph G - The Hamiltonian circuit exists which isA-B-D-E-C-F-A —_e7-— | for (jel Coiniet alimag fees se aecxtj)=xtk1) ther 7 not a distinct Vv ned a distinct vertex break, ertex de(jek) then // obtal ( if((k Let us first write a general algorithm for sum Algorithm 5 ater | Let, $ be a set of elements and d Step 1 : Start with an empty set. Step 2: Add to the subset, the a 2 lb example 12.2: Consider Set § = obtaining sum of subset, solution ¢ element, Te ‘Add next element Add next element, Sum exceeds d = 39 hence backtrack, ~ | ‘Sum exceeds d = 30 alsa «Backtrack 5, 10, 12, 18 45 Sum exceeds d : ec: Algorithm j Analysis and Design of Algorithms 12 - 22 gorithm | Sum ; 8 Mie a wo i give solution it | t .. prune it Solution Fig. 12.5 State space tree for sum of subset tmp Example 12.3: Let m = 31 and W = (7, 11, 13, 24}. Draw a portion of sia tree for solving sum-of-subset problem. For the above given algorithm. Solution : Initially we pass (0, 1, 55) to sum-of-subset function. The suf index = 1 and remaining_sum = 55 initially [-- 7 + 11 + 13 + 24]. The recursive execution of the algorithm will be, ‘Analysis and Design of Algorithm: ‘To fill the given Knapsack We is put in k the Knapsack's capacity profit. This selected object selected objects. Note that the first item gives per weight unit. © First of all we compute upperbound of the free: f «We design a state space tree an be computed using following The upper bound ¢ Consider 4 items as - ub best pay off per Coping with the Limitations 42-30 of cater the object with some Weight and having son ‘he Knapsack. Thus the TW should not be exceeded. Hex, weight unit. ‘and last one gives the worst pay of vi/wi 2 v2/W2 2 va [Wao by inclusion or excl ve city W = 10 eee means next item to item 7 Now vier/Wist ie valWa = te aa = 40+ (10-6) *6 ; = 40+6*6 ‘ ub = 76 e Computation at node _Il ace tree WE assume that item 1 ‘At node III in state SP: z vz0 w=0 The capacity W = 10 Next to item 1 is item 2 Vig /Wier 9 means 2 ie. v2/w2 = 6 ‘Computation at node IV This is a node at which we hi vilkjwi os ot v3/wW5 =4 v+(W-w)ey 40 + (10-4) «4 40+ 644 64 iWin = 40+ 20= 60 = 4+5=9 Ea =10. next item would be vj, 1/Wi+1 > item 4 va/ws = 4 ub = v+(W-w)va/Wa 60 + (10-9) *4 60+4 ign of Algorithms 12-34 Analysis and Des! The next item being selected is Item 4. 2 vijwar4 Vier /Wiet ub = ve OW = w)* vie / Mart i = 40+ (10-4) *4 - = 40 +24 Nag ub = 64 1 od RW : awit ‘Computation at node_VIll ‘At node VII, we consider given problem statement. Vie1/Wist = 0 6 w = 445+3=12 — But this is exc . vy = 40+204+12=72 selection of item 1) item 9) een Aart rere tae mm 3, item 4 Therion w = 10 ub = v+(W-w) vier/Wis ub = 72+ (10-12)*0 But as weight of selected items exceed solution. ni Computation at node IX oe ‘At node IX, we consider selection given. . Viei/Wier = 0 w= 4+5=9 v4 Ww ub At node 11 we get optimum tour ie, 3 N ur Le. a-b-d-e. Hence the optimum cost ie i a tour of TSP is ab-d-e-ca with cost 16. 12.10 ADP Algorithms for NP-Hard Problems In this section we will discuss two important issues namely, "What is NP-hard problem ?" and "How approximation algorithms are used for NP-hard problems 7" Let us start our discussion with the understanding of NP-hard problems. In computational complexity theory there are different types of problems. Some problems are decision problems for which answer is yes or No, others are search problems and ep 4 Se walk around the tree. oa have ay © Fig. 12.24 Fig. 12.25 In this section we will discuss another The knapsack problem can be defined as ollo with weights w,,W2 Wn and Vir oe is 1 find the most valuable subset of iten variations of knapsack problem - + gis and Design of Algorithms, 12eg as 55 Ae Y~ vjiscrete knapsack Problem - g elect the Continuous knapsack probtem itey : rely is ’ fracti 7: now there exists {WO approximation ne ‘onal iter, for te lowed . ack Approximation 'P8ack prob, Algorithms for Greedy, Algorithm a knapsack problem Approximation ‘Schemes. Fig. 12.26 Mam tot us discuss these in detail . [Link] algorithm for knapsack Problem " using greedy approach for knay ficiently. Hence we will consider both value ji c to weight ratio. Let us discuss 6; approach for solving both discrete knapsack and continuous knap pio, Greedy algorithm for the discrete knapsack problem 1. Compute value/weight ratio v; / w; for all items. 2, Sort the items in non increasing order of the ratios v, / w,. 3, Repeat until no item is left in sorted list using following steps a) If current item fits, use it es b) Otherwise skip this item, and proceed to next item. oe ” ©] ™ Example 12.5: Solve the knapsack problem for the Hela using. Greedy i approach. The item can be completely selected or skiped comp ° Item Weight Value y 4 7 2) / ua : 3 $12 G a zs 4 3 4 ee oe 330 A s ‘an item or Consider W = 10. sper we can comple 0 in son ns = 10. a compe ion : This is also called 0-1 soarete-weit ratio 'P it. First of all we will comp™! order of the ratio- Analysis. we will have ~ ro fulfil the capacity W = 10, | add item of weight 4 «skip item of weight 7 ‘This will produce the total Jo fulfil «add item of weight 5 weight of 9 with profit of $72 bead «sale weig «skip item of weight 3 ‘This is the solution for given instance of knapsack problem. But the Greedy algorithm does not give optimal solution always rather thet upper bound on the accuracy of approximate solution. itn ntinous: knapsack problem 1. Compute value/weight ratio Vj / w; for all items. 2. Sort the items in non increasing order of their ratios - vj / Wi. 3, Repeat until no item is left in sorted list using following steps - use it. gest fraction to fill the knapsack to its full eapaciy. lem for folowing instance wing G2 Greedy algorithm for co a) if current item fits, ) Otherwise take its Tar Solve the knapsack pro ym Example 12.6 : method. The capacity of knapsack is W = 10. a + This is fractional knapsack problem. The items © be st “irst of all we will obtain value to weight ratio zo fulfill the capacity W = 10 we will ha add item of weight 4. a + select item of weight 7 and take its fractional ., Weights of selected items ate 6 5 pAdTX Gg = 10 which fits into the knapsack. Hence, the profit obtained will be 6 42 = +49x 7 =42+42 = $84 This is an optimal solution to given instance of knapsack: This algorithm always give optimal solution t° continuous knapsack problem Soros scheme Ser ees a nin hh this scheme certain approxima oe oa or 01 =a is suggested by Prof. S, es se ated version of knapsack P! £(ss) : uf) of n items Te) k here kis an integer such St Example 12.7 : For the st approximation scheme ket Y Sle ae ‘and Design of Algorithms 12 - 58 tom Weight | Value es 1 Yeast 1 4 «2 |p 108 a) Me 2 a $49 7 S$ 3 5 $30 6 a as ea Capacity W = 10 Solution : As capacity of knapsack W = 10 we will select i and giving maximum profit. The approximation scheme _k than equal to k items ie. subset with 0, 1 or 2 items can be consid items satisfying the capacity constraints are added “cr then select an optimal solution. Subset to be considered Possible added item 0) = Anon vi {1} 3,4 2) @ jal 1] 2 TI § 7 AE —~ ae mL 7 MN a pe Nye i ‘ _ Dp ,

You might also like