Ishareyoublog.files.wordpress.com



HOLYCROSS ENGINEERING COLLEGEDEPARTMENT OF COMPUTER SCIECNE AND ENGINEERINGCS 6402-DESIGN AND ANALYSIS OF ALGORITHMUNIT-IINTRODUCTIONNotation of an algorithm-fundamentals of algorithmic problem solving –important problem types-fundamentals of the analysis of algorithm efficiency-analysis framework-asymptotic notations and its properties-mathematical analysis for recursive and non-recursive algorithmPART-ANotation of an algorithmWhat is mean by algorithm(MAY/JUNE13)Give the Euclid’s algorithm for computing gcd(m,n)(MAY/JUNE16)Write any four properties of algorithmFundamentals of algorithmic problem solvingDefine algorithm validation(NOV/DEC12)Define program proving and program verification(MAY/JUNE14)Important Problem TypesHow to choose best searching algorithmDefine In-place sorting algorithm?ExampleFundamentals of the analysis of algorithm efficiency-analysis frameworkThe (log n)th smallest number of n unsorted numbers can be determined in O(n) average case time(TRUE/FALSE)(NOV/DEC15)Write an algorithm to find the number of binary digits in the binary representation of the positive decimal integer(APR/MAY15)What is average case analysis (MAY/JUNE14)What are the components of fixed and variable part in space complexity (NOV/DEC13)What is time and space complexity (NOV/DEC12)(OR)Differentiate time complexity from space complexity(APR/MAY10)Using the step count method analyze the time complexity when 2 m*n matrices are added(APR/MAY11)]An array has exactly n nodes .they are filled from the set {0,1,2,….n-1,n}.There are no duplicate in the list .Design an O(n)worst case time algorithm to find which one of the elements from the above set is missing in the array(APR/MAY11)Compare the orders of growth of n(n-1)/2 and n2(MAY/JUNE16)What is time space tradeoffGive any two example explaining the time space tradeoffProve that any comparison sort algorithm requires ?(n log n)comparisons in worst case(NOV/DEC15)Asymptotic notations and its propertiesWrite down the properties of asymptotic notations(APR/MAY15)(OR)What is the properties of big -oh notation(NOV/DEC11)Define theta notation(NOV/DEC14)Define little Oh and Omega Notations(NOV/DEC13)Define Big-Oh notation(MAY/JUNE13,MAY/JUNE12,MAY/JUNE11)Mathematical analysis for recursive and non-recursive algorithmWrite a recursive Fibonacci algorithm and its recursion relation(NOV/DEC15)What is meant by substitution method(NOV/DEC14)(OR)State the principle of substitution method(MAY/JUNE14)What is meant by linear search(MAY/JUNE12,NOV/DEC11)Give example for recurrence equation(MAY/JUNE11,APR/MAY10)Write General plan for analyzing efficiency of recursive algorithmWrite an algorithm for factorial of numbers using recursion functionWrite General plan for analyzing efficiency of non recursive algorithmWrite down algorithm to find the number of binary digits in the binary representation of a positive decimal integerPART-BNotation of an algorithmWhat are the features of an efficient algorithm?Explain(OR)Define the term algorithm and mention its properties(8M)(OR)Explain the structure of writing the algorithm (8M)Explain what the three algorithms to compute the gcd of two numbers(8M)Fundamentals of algorithmic problem solvingWhat are the steps that need to be followed while designing and analysis an algorithm?(OR) Explain about fundamentals of algorithm problem solving methods(16M)Important problem typesExplain the concept of in-place sorting with illustrate example?(8M)Explain in detail about important problem types(8M)Fundamentals of the analysis of algorithm efficiency-analysis frameworkWrite the insertion sort algorithm and estimate its running time(NOV/DEC15)(8M)What is space complexity ?With an example explain the components of fixed and variable part in space complexity(MAY/JUNE14)(OR)Briefly explain the time complexity and space complexity estimation(MAY/JUNE13)(8M)Explain analysis framework of algorithm with suitable example(16M)Asymptotic notations and its propertiesDiscuss in detail all the asymptotic notation with example(MAY/JUNE12)(OR)Give the definition and graphical representation of O-notation(8)(MAY/JUNE16)Distinguish between Big-Oh ,Theta and Omega Notation(NOV/DEC12)(8M)Discuss the properties of big-oh notation(NOV/DEC14)(8M)Is Big oh notation transitive ?Discuss an example(MAY/JUNE11)(4M)How can condition be removed from conditional asymptotic notation?Discuss(MAY/JUNE11)(4M)Recurrence equationSolve the following recurrence relation using substitution method(8)T(n)=T(n-1)+1 with T(0)=0 as initial condition. Also find big-oh notationT(n)=2T(n/2)+nT(n)=T(n/3)+C with T(1)=1T(n)=T(n-1)+n4Solve the following recurrence relation using recursion tree method(8)T(n)=2T(n/2)+n with T(1)=O(1)T(n)=3T(n/4)+Cn2Solve the recurrence relation using master method(8)i=1n-1Ti+1 if n≥2T(n)=5T(n-2)-6T(n-2)T(n)=2T(n/2)+nlognT(n)=9T(n/3)+n3Solve the following equalities are correct(4)5n2-6n=θ(n2)n!=O(nn)n3+106n2=θ(n3)2n22n+nlogn=θ(n22n)State whether following equality is correct or wrong?(4)5n3+4n=Ω(n2)(4)10n3+nlogn+9=O(n2)(4)Find the closest asymptotic tight bound by solving the recurrence equation T(n)=8T(n/2)+n2 with T(1)=1 using recursion tree method [Assume that T(1)€O(1)](NOV/DEC15)(8)Suppose W satisfies the following recurrence equation and base (where C is a constant)W(n)=c.n+W(n/2) and W(1)=1 what is the asymptotic order ofW(n)(NOV/DEC15)(6)Solve the recurrence equation(NOV/DEC12)(4+4)(1)T(n)=2Tn2+3 n>22 n=2With the suitable example explain the method of solving recurrence equation(MAY/JUNE12)(16)(2)T(n)=2Tn2+cn n>1a n=1a,c are constantsSolve the given recurrence relation(NOV/DEC13)(16)2Tn2+2 n>21 n=20 n=1Mathematical analysis for recursive and non-recursive algorithmGive the algorithm to check whether all the elements in a given array of n elements are distict.Find worst case Complexity of the same(8)(MAY/JUNE16)Give the recursive algorithm for finding the number of binary digits in n’s binary representation,where n is a positive decimal integer .Find the recurrence relation and Complexity(16) (MAY/JUNE16)Derive the recursion relation for fibonacci series algorithm also carry out the time complexity analysis(MAY/JUNE14)(8M)Discuss How recurrence equation can be solved(MAY/JUNE11,NOV/DEC14)(8,16)Explain Towers of Hanoi problem and solve it using recursion(MAY/JUNE14,NOV/DEC13)(8)Show how to implement a stack using two queues. Analyze the running time of the stack operation(NOV/DEC15)(10M)Find the time complexity and space complexity of the following problems .Factorial using recursion AND compute nth Fibonacci number using Iterative statements(NOV/DEC12-(4+4))UNIT-IIBRUTE FORCE AND DIVIDE AND CONQUERBrute ForceClosest pair and Convex hull problems-Exhaustive Search-Travelling Salesman Problem-Knapsack Problem-Assignment ProblemDivide and Conquer Merge sort-Quick Sort-Binary Search-Multiplication of Large integers-Strassen’s Matrix multiplication-Closest Pair and Convex Hull ProblemsPART-A Brute forceDesign a brute force algorithm for computing the value of a polynomial p(x)=anxn+an-1xn-1+….+a1x…a0 at a given point x0 and determine its worst case efficiency class(APR/MAY15)Define feasible and Optimal solution(MAY/JUNE15,NOV/DEC13,MAY/JUNE14)State principle of optimality(MAY/JUNE15,NOV/DEC14,NOV/DEC13,MAY/JUNE12,NOV/DEC10)What is exhaustive search? Enlist the problem in which exhaustive search is carried out.Closest pair and Convex hull problemsGive the mathematical notations to determine if a convex direction is towards left to right and write the algorithm(NOV/DEC15)Travelling Salesman ProblemWhat is travelling salesman problem(NOV/DEC11)Knapsack ProblemDefine Knapsack Problem(NOV/DEC14,NOV/DEC13,NOV/DEC11)Divide and ConquerGive the control abstraction for divide and conquer technique(Nov/DEC13,NOV/DEC12,MAY/JUNE13)(OR)Give the general strategy of divide and Conquer method(MAY/JUNE16)What do you mean by divide and conquer strategy(MAY/JUNE13)Differentiate between subset paradigm and ordering paradigm(NOV/DEC12)How divide and conquer algorithms are implemented?(MAY/JUNE11)Merge sortShow the intermediate steps when the numbers 123,23,1,43,54,36,75,34 are sorted using merge sort(APR/MAY11)What is the difference between quick sort and merge sort?Give the time efficiency and drawback of merge sort algorithmQuick SortIs quick sort stable sorting algorithmBinary SearchWhat is binary search ?What is the necessary precondition for the binary searchTrace the operation of the binary search algorithm for the input –15,-6,0,7,9,23,54,82,101,112,125,131,142,151 if you are searching for the element 9(NOV/DEC10)Derive the complexity of binary search algorithm(APR/MAY15,MAY/JUNE12)Differentiate linear search and Binary search techniques(NOV/DEC14)Multiplication of Large integersState the formula for multiplying two large numbers using divide and conquer methodStrassen’s Matrix multiplicationWrite down the formula used by strassen’s method for multiplication of two matricesClosest Pair and Convex Hull ProblemsWhat is the closest –pair problem? (MAY/JUNE16)PART-BBrute Force and Convex hullExplain the closest pair and convex hull problem using Brute Force method in detail(16)(OR)Explain the convex hull problem and the solution involved behind itSolve the following using Brute force algorithm(16)Find whether the given string follows the specified pattern and return 0 or 1 accordingly(1)Pattern “abba”,input “redblueredblue” should return 1(2)Pattern “aaaa” input “asdasdasdasd” should return 1(3) pattern “aabb” input “xyzabcxzyabc” should return 0Explain the concept of exhaustive search with the help of an example(8)Explain how to solve travelling salesman problem using brute force approach(8)Explain how to solve Knapsack problem using brute force approach(8)Explain how to solve assignment problem using brute force approach(8)Find the optimal solution to the fractional knapsack problem with given dataItem weightbenefitA260(NOV/DEC15)(8)B375C490DIVIDE AND CONQUERMerge SortDerive the worst case analysis of Merge sort using suitable illustrations(APR/MAY15-8)Sort the following set of elements using merge sort :12,24,8,71,4,23,6,89,56.(MAY/JUNE11)(8)Devise an algorithm to sort the following elements using mergesort technique 286,45,278,368,475,389,656,788,503,126.(8)Trace the steps of Mergesort algorithm for the elements 122,25,70,175,89,90,95,102,123 and also compute its time Complexity(NOV/DEC12)(16)Explain divide and conquer method with merge sort algorithm give an example(MAY/JUNE12)(16)Apply the merge sort algorithm for the following data set999,45,12,99,65,43,121,21,122,32,44,55,77,66,11,222 Illustrate each step of the algorithm (MAY/JUNE11)(16)Write an algorithm for merge sort.Explain how the elements get sorted310,285,179,652,652,351,423,861,254,450,520(NOV/DEC14)(16)Distinguish between quick sort and merge sort and arrange the numbers in increasing order using merge sort 18,29,68,32,43,37,87,24,47,50(MAY/JUNE13)(16)State and Explain the merge sort algorithm and give the recurrence relation and efficiency(16)(MAY/JUNE16)Quick SortExplain about quick sort algorithm with suitable example?Binary SearchWrite the algorithm to perform Binary Search and compute its run time complexity(NOV/DEC15,NOV/DEC12,NOV/DEC14)(8,16)(OR)Develop an algorithm for Binary search Illustrate how best case ,average case and worst case complexity of binary search can be computed(MAY/JUNE11-16)Multiplication of Large two integer40. A pair contains two numbers and its second number is on the right side of the first one in an array.The difference of a pair is the minus result while subtracting the second number from the first one .Implement a function which gets the maximal difference of all pairs in an array(using divide and conquer method)(APR/MAY15)(16)41. Explain the method used for performing Multiplication of two large integers. Explain how divide Conquer method can be used to solve the same(16)(MAY/JUNE16)Strassen Matrix Multiplication42. Compute the multiplication of given two matrices using strassen’s matrix multiplication method(NOV/DEC15)(8)A=1021411001305021B=0101210420111350Closet and Convex Problem43. Write down the algorithm to construct a convex hull based on divide and conquer strategy(NOV/DEC15)(8)\UNIT-IIIDYNAMIC PROGRAMMING AND GREEDY TECHNIQUEDynamic ProgrammingComputing a Binomial Coefficient-warshall’s and Floyd’s algorithm-Optimal Binary search tree-Knapsack Problem and memory functionGreedy TechniquePrim’s algorithm-Kruskal’s Algorithm –Dijkstra’s algorithm-Huffman treesPART-ADynamic Programming& Computing a Binomial CoefficientList out the advantages of Dynamic Programming(MAY/JUNE14)Compare greedy technique with dynamic programming method(NOV/DEC12,MAY/JUNE12,APR/MAY11)Compare Divide and Conquer with Dynamic programming and Dynamic Programming with greedy method(NOV/DEC10)What is the best algorithm suited to identify the topography for a graph .Mention its efficiency factors(NOV/DEC15)State how dynamic Programming solves complex problem(MAY/JUNE11)State how binomial co-efficient is computed(NOV/DEC15)warshall’s and Floyd’s algorithmWrite down the optimization technique used for warshall’s algorithm .State the rules and assumption which are implied behind that.(APR/MAY15)Optimal Binary search treeDefine Optimal Binary tree(APR/MAY 10)Knapsack Problem and memory functionList out the memory function used under Dynamic Programming(APR/MAY15) Greedy TechniqueFor what type of problem greedy algorithm are best suited(MAY/JUNE 11)Devise an algorithm to make a change for 1655 using the Greedy strategy The coins are available are {1000,500,100,50,20,10,5}(APR/MAY11)Differentiate between subset paradigm and ordering paradigmWrite control abstraction for the ordering paradigmPrim’s algorithm&KruskalWhat is spanning tree?Give an example(NOV/DEC11)What is Euclidean minimum spanning tree problem(MAY/JUNE2016)Differentiate between prim’s and kruskal’s algorithmWhat is the best algorithm suited to identify the topography for a graph .Mention its efficiency factors(NOV/DEC15)Define the single Source shortest path problem(MAY/JUNE2016)Huffman TreeWhat is the purpose of huffman’s treePART-BDYNAMIC PROGRAMMINGComputing a Binomial Coefficient44. How dynamic programming is used for computing Binomial Coefficient(16)Warshall’s and Floyd’s algorithm45. Write down and explain the algorithm to solve all pairs shortest paths problem.(16)Solve All pairs shortest path problem for the digraph with the weight matrix given below(8)ABCDA0∞∞3B20∞∞C∞701D6∞∞0Consider the following graph solve all pairs shortest path problem of the graph .the al pair shortest paths problem is to determine the shortest path between every pair of vertices(8)Optimal Binary search treeObtain OBST for(q1,q2,q3,q4)=(do,if,int,while) p(1:4)=(3,3,1,1) q(0:4)=(2,3,1,1)Write an algorithm to construct the OBST given the roots r(I,j) 0<=i<=j<=n.Also prove that this could be performed in time .O(n)(MAY/JUNE-15)(8)Using OBST algorithm compute wi,rij,cij where j=0 to 4 for the identifier set (a1,a2,a3,a4)=(end,goto,print,stop)with P1=1/20,P2=1/5,P3=1/10,P4=1/20Q0=1/5,q1=1/10,q2=1/5,q3=1/20,q4=1/20Using rij construct the Optimal binary search tree(NOV/DEC13)(16)Knapsack Problem and memory functionExplain Knapsack’s problem and memory function with following exampleN=3 (w1,w2,w3)=(1,2,2) and (p1,p2,p3)=(18,16,6) and M=4.(16)Apply the dynamic programming following instance of the knapsack problem and solve w=5(8)ItemWeightValue12$1221$1033$2042$15GREEDY TECHNIQUEPrim’s algorithmConstruct the minimum spanning tree using prim’s algorithms(8)Explain Prim’salgorithm for constructing minimum cost spanning tree(8)13524462 1677 9 Kruskal’s AlgorithmExplain Kruskal’s algorithm for constructing minimum cost spanning tree(8)Explain Dijistra’s algorithm for constructing minimum cost spanning tree(8)Consider the graph given below fins the minimum spanning tree of this graph using a)Kruskal’s algorithm b)Dijkstra’s algorithm(16)Huffman treesThe Binary string below in the title of a song encoded using Huffman code001100010111110011101100000100111010010101Gibe n the letter frequencies listed in the table below build the Huffman coded and use them to decode the title .In cases where there are multiple greedy choices the coded are assembled by combining the first letters from left to right in the order given in the table.Also the code are assigned by labeling the left and right branches of the prefix/code tree with ) and 1 respectivelyLetterahvw‘’etloFrequency111122233(APR/MAY-15)(10)Write the procedure to compute Huffman code(APR/MAY-15)(6)Let A={l/119,m/96,c/247,g/283,h/72,f/77,k/92,j/19}be the letters and its frequency of distribution in a text file .Compute a suitable Huffman coding to compress the data effectively(MAY/JUNE-14)(8)Explain about Huffman tree with example(8)UNIT-IVITERATIVE IMPROVEMENTThe Simplex Method-The maximum Flow problem-maximum matching in Bipartite graphs-The stable marriage ProblemPART-AThe Simplex MethodDetermine the dual Linear program for the following LPMax 3a+2b+c 2a+b+c<=3,a+b+c<=4,3a+3b+6c<=6,a,b,c>=0; (NOV/DEC15)What is iterative improvement methodEnlist various application of iterative methodWhat are basic and non basic variablesWhat is pivot element in simplex methodWhen can we say that the optimal solution is obtained in simplex methodWhat is linear programming problemThe maximum Flow problemDefine Network flow and cut(NOV/DEC15,APR/MAY15)Maximum matching in Bipartite graphsWhat is bipartite graphWhat is two colorable graphWhat is maximum cardinality matchingWhat is maximum matching problemThe stable marriage ProblemState the stable marriage problemPART-BThe Simplex Methodsolve the following linear programming problem geometrically(8)maximize 3x+ysubject to –x+y<=1 2x+y<=4 x>=0,y>=0solve the following linear programming problem geometrically(8)maximize x+2ysubject to 4x>=y y<=3+x x>=0,y>=0Write the procedure to initialize simplex which determines if a linear program is feasible or not?((NOV/DEC15)(4)Maximize p=2x+3y+z (APR/MAY15)(8)Subject to x+y+z<=402x+y-z>=10-y+z>=10x>=0,y>=0,z>=0Use simplex to solve the farmers problem given belowA farmer has a 320 acre farm on which he plants two crops: rice and wheat .For each acre of rice planted his expenses are 50 and for each acre of wheat planted his expenses are100.Each acre of rice requires 100 quintals of storage and yields a profit of 60 each acre of wheat requires 40 quintals of storage and yields a profit of 90.If the total amount of storage space available is 19200 quintals and the farmer has only 20000on hand how many acres of each crop should he plant in order maximize his profit ?What will his profit be if he follows this strategy?(NOV/DEC15)(12)Summarize the simplex method(8)(MAY/JUNE16)The maximum Flow problemHow do you compute maximum flow for the following graph using Ford-Fulkerson method(APR/MAY15)(10)SXUYVSXUYV10 13247652State and prove Max-Flow Min cut theorem(8)(MAY/JUNE16)Apply the shortest augmenting-path algorithm to the network shown below(16)(MAY/JUNE16)Maximum matching in Bipartite graphsApply the maximum matching algorithm to following bi-partite graph(8)123456For each matching shown below in bold, find an augmentation or explain whyno augmentation exists.(8)lefttop74. Illustrate the working of the maximum matching algorithm on the following weighted tree(NOV/DEC15)(12)ABDCHJGIEF12=2=3551463The stable marriage ProblemConsider an instance of the stable marriage problem given by the following ranking matrix(16) A B Cα 1,32,2 3, 1β 3,11,3 2, 2γ 2,23,1 1, 3For each of its marriage matching’s, indicate whether it is stable or not. For the unstable matching, specify a blocking pair. For the stable matchings’, indicatewhether they are man-optimal, woman-optimal, or neither. (Assume that the Greek and Roman letters denote the men and women, respectively.)Find a stable marriage matching for the instance defined by the followingranking matrix(16) A B C Dα1,3 2,3 3,2 4, 3β1,4 4,1 3,4 2, 2γ2,2 1,4 3,3 4, 1δ4,1 2,2 3,1 1, 4UNIT-VCOPYING WITH THE LIMITATIONS OF ALGORITHM POWERLimitations of algorithm power-lower bound arguments-Decision trees-P,NP and NP Complete problems-copying with the Limitations.BacktrackingN Queens Problem-Hamiltonian circuit problems-subset sum problemBranch and BoundAssignment problem-Knapsack Problem-Traveling sales man Problem-Approximation algorithm for NP-hard problems-traveling salesman problem-Knapsack problemPART-ALimitations of algorithm powerWhat are explicit and Implicit Constraints(MAY/JUNE14,NOV/DEC13,NOV/DEC12,MAY/JUN12)Decision treeDraw the decision tree for comparison of three values(NOV/DEC15)P-NP-NP Complete ProblemsDepict the proof which says that a problem ‘A’ is no harder or no easier than problem ‘B’(NOV/DEC15)How NP hard problem are different from NP-Complete(APR/MAY15)Compare NP-hard and NP-completeness(MAY/JUNE14,Nov/DEC10)State the property of NP-Complete Problem(NOV/DEC13,NOV/DEC12)List the two properties that must be satisfied by a problem L to be NP complete(MAY/JUNE11)What is NP Completeness(NOV/DEC11)N-Queen ProblemDefine the basic principles of back tracking(MAY/JUNE12)(OR)State the general backtracking method(NOV/DEC11)Write rule for N-Queen ProblemHamiltonian Circuit ProblemDraw a graph with cycle but no Hamiltonian cycle(APR/MAY11)What is the difference between a Live and dead node(NOV/DEC10)What is a state space graph(MAY/JUNE16)Define Articulation Point.Give the condition to identify an articulationAssignment ProblemState the assignment Problem(MAY/JUNE16) What is a FIFO branch and bound algorithm What are the two methods of Branch and bound techniques(NOV/DEC13)PART-BLimitations of algorithm powerExplain the trivial bounds method(8)Explain the problem reduction technique?(8)Decision treeExplain decisions tree for sorting algorithms(8)Explain decision tree technique for searching a sorted array(8) P-NP-NP Complete ProblemsExplain the P , NP and NP completeness with suitable example (16)Explain Cook’s theorem(8)Using an example prove that satisfiablitity of Boolean formula in 3-conjunctive Normal Form is NP-complete(NOV/DEC15)(12)Write notes on deterministic and non-deterministic algorithms(MAY/JUN14)(8),(NOV/DEC13)(8)BACKTRACKING N-Queen ProblemThe Knight is placed on the first block of an empty board and moving according to the rules of chess must visit each square exactly once .solve the above problem using backtracking procedure(APR/MAY15)(8)Describe the backtracking solution to solve 8-Queens problem.(8)(OR)Explain 8-queen problem with an algorithm .Explain why backtracking is the default procedure for solving problem(MAY/JUN14)(8)(OR)Explain control abstraction for backtracking method. How 8 queens problem could be solved using backtracking method?(NOV/DEC12)(8) Hamiltonian Circuit ProblemDescribe the backtracking solution to solve Hamiltonian problem.(8)(OR)Show that the Hamiltonian path problem reduce to the Hamiltonian circuit problem and vice versa(NOV/DEC15)(10) Subset –sum ProblemDescribe the backtracking solution to solve sum of sub-set problem.(8)(OR)Using backtacking technique solve the following instance of the subset sum problems s=(1,3,4,5) and d=11(MAY/JUN14)(8)(OR)Let w={5,7,10,12,15,18,20}and m=35 Find all possible subset of w whose sum equivalent to m .Draw the portion of state space tree for this problem(NOV/DEC12)(8)(OR)State the subset –sum problem and complete state space tree of the backtracking algorithm applied to the instance A={3,3,6,7}and d=15 of the subset –sum problem(16)(MAY/JUNE16)BRANCH AND BOUNDAssignment problemExplain how job assignment problem could be solved given n tasks and n agents where each agent has a cost to complete each task using branch and bound technique(APR/MAY15)(8)Knapsack ProblemWith an example, explain how the branch-and-bound technique is used to solve 0/1 knapsack problem.(8)Let n=4 and m=15 the profits for the instance are (p1,p2,p3,p4,p5)=(10,10,12,18) and the weights are(w1,w2,w3,w4,w5)=(2,4,6,9).Explain the working of 0/1 kanpsack problem using LC branch and bound technique.(16)Traveling sales man ProblemSolve the following 6 city travelling salesperson problem using the Branch and Bound algorithm(NOV/DEC13)α 21 42 31 6 24 11 α 17 7 35 1825 5 α 27 14 912 9 24 α 30 1214 7 21 15 α 4839 15 16 5 20 α Approximation algorithm for NPState the relationship among the complexity class algorithms with the help of neat diagrams(NOV/DEC15)(4)What is an approximation algorithm ?Give example(NOV/DEC15)(4)Suggest an approximation algorithm, for traveling salesperson problem. Assume that the cost function satisfies the triangle inequality(APR/MAY15)(8)Implement an algorithm for Knapsack problem using NP-hard approach(APR/MAY15)(8)Compare backtracking branch and bound techniques with example(MAY/JUN14)(8) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download