Ishareyoublog.files.wordpress.com



HOLYCROSS ENGINEERING COLLEGEDEPARTMENT OF COMPUTER SCIECNE AND ENGINEERINGCS5151-ADVANCED DATA STRUCTURES AND ALGORITHMS(I-ME-CSE : R2017)UNIT I : ROLE OF ALGORITHMS IN COMPUTINGAlgorithms - Algorithms as a Technology- Insertion Sort - Analyzing Algorithms - Designing Algorithms- Growth of Functions: Asymptotic Notation - Standard Notations and Common Functions- Recurrences: The Substitution Method - The Recursion-Tree Method PART-AWhat is mean by algorithmWrite any four properties of algorithmDefine algorithm validationHow to choose best searching algorithmWrite an algorithm to find the number of binary digits in the binary representation of the positive decimal integerWhat is average case analysisWhat are the components of fixed and variable part in space complexity Give any two example explaining the time space tradeoffProve that any comparison of sorting Write down the properties of asymptotic notationsDefine theta notationDefine little Oh and Omega NotationsDefine Big-Oh notationWrite a recursive Fibonacci algorithm and its recursion relationWhat is meant by substitution methodWhat is meant by linear searchGive example for recurrence equationWrite 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 algorithmPART-BDefine the term algorithm and mention its propertiesWhat are the steps that need to be followed while designing and analysis an algorithm?Write the insertion sort algorithm and estimate its running timeWhat is space complexity ?With an example explain the components of fixed and variable part in space complexityExplain analysis framework of algorithm with suitable exampleDiscuss in detail all the asymptotic notation with exampleDistinguish between Big-Oh ,Theta and Omega NotationDiscuss the properties of big-oh notationSolve 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)T(n)=5T(n-2)-6T(n-2)T(n)=2T(n/2)+nlognT(n)=9T(n/3)+n3Find 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)]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)Solve the recurrence equation(NOV/DEC12)(4+4)(1)T(n)=2Tn2+3 n>22 n=2Give the algorithm to check whether all the elements in a given array of n elements are distinct. Find worst case Complexity of the sameDerive the recursion relation for fibonacci series algorithm also carry out the time complexity analysisDiscuss How recurrence equation can be solvedExplain Towers of Hanoi problem and solve it using recursionShow how to implement a stack using two queues. Analyze the running time of the stack operationUNIT II : HIERARCHICAL DATA STRUCTURESBinary Search Trees: Basics - Querying a Binary search tree - Insertion and Deletion- Red-Black trees: Properties of Red-Black Trees - Rotations - Insertion - Deletion -B-Trees: Definition of B- trees - Basic operations on B-Trees - Deleting a key from a B-Tree- Fibonacci Heaps: structure - Mergeable-heap operations- Decreasing a key and deleting a node-Bounding the maximum degree. PART-AGive various implementation of treeDefine Binary and Complete binary treeHow is binary tree represented using an array?Construct an expression tree for the expression A+(B-C)*D*(E+F)Write an algorithm to declare node of a tree structureWhat are the application of treeWhat are B-treeEnlist the properties of B-treeWhat are red black treeExplain the properties of red-black tree What are the advantages of Fibonacci heapPART-BDiscuss about various operation of binary search tree with suitable example(16)Explain the insertion and deletion of nodes in the B-tree with suitable example and also explain the properties of B-tree(16)Explain the insertion and deletion of nodes in the Red-black tree with suitable example and also explain the properties of Red-black tree(16)Explain what are the operation performed in Fibonacci heap(16) Problem(8)Draw the binary search tree for the following input list 60,25,75,15,50,66,33,34.Trace the algorithm to delete the node25,75,44,fromthe treeDraw the Red-Black tree for the following input list 60,25,75,15,50,66,33,34.Trace the algorithm to delete the node25,75,44,fromthe treeExplain insertion procedure in Red-Black tree and insert the following sequence: { 20,10,5,30,40,57,3,2,4,35,25,18,22,21} (8)Construct a binary search tree by inserting 30,10,4,19,62,35,28,73 into an initially empty tree .show the result of splaying the nodes 4, 62 one after the other of the constructed tree.(10)construct a B-tree with order m=3 for the key values 2,3,7,9,5,6,4,8,1 and delete the values 4,6,show the tree in performing all operations(6)UNIT III : GRAPHSElementary Graph Algorithms: Representations of Graphs - Breadth-First Search - Depth-First Search - Topological Sort - Strongly Connected Components- Minimum Spanning Trees: Growing a Minimum Spanning Tree - Kruskal and Prim- Single-Source Shortest Paths:The Bellman-Ford algorithm - Single-Source Shortest paths in Directed Acyclic Graphs - Dijkstra‘s Algorithm; All-Pairs Shortest Paths: Shortest Paths and Matrix Multiplication - The Floyd- Warshall Algorithm; PART-AWhat are the storage representation of the graphWhat are the application of graphProve the number of odd degree vertices in a connected graph should be evenDifferentiate between Prim’s and Kruskal’s algorithmDefine spanning tree of a graphWhat are articulation pointsDefine regular graphDefine critical pathWhat is weakly connected graphWhat is the purpose of Dijkstra’s algorithmWhat is adjacency list ?when it is usedWhat is an activity node graphWhen graph is said to be bipartiteWhat is directed and undirected graphPART-BDiscuss Prim’s and Kruskal’s algorithm for computing the minimal spanning tree weighted undirected graph(16)(OR)i)Explain Prim’s algorithm to find the minimum spanning tree for a graph(8)ii) Explain Kruskal’s algorithm to find the minimum spanning tree for a graph(8) Explain BFS and DFS in detail .Write the algorithm(16)(OR)i) Explain breadth first search algorithm for traversal of any graph with suitable example? Define the time complexity(8)ii) What is graph? Explain the depth first search tree (8)Explain the topological Sorting algorithm(8)Discuss all pair Shortest path algorithm with an example (16)(OR)i)Explain Dijkstra’s algorithm with suitable example(8)ii)Explain Floyd’s Algorithm with suitable example(8)iii)Explain about warshall algorithm with exampleApply Prim’s algorithm to find a minimum spanning tree of a graph(8)bcaed1534662Sort the given digraph using topological sort with suitable step(8)ADCBEi)Write an algorithm, for breath first search on a gragh and give the nodes of the graph G given diagram based on the algorithmii)using Dijikstra’s algorithm find the shortest path from the source to all other nodes of the graph given (16) V1V2V3V5V6V7V4 2 4 1 3 10 5 2 2 8 61Consider a directed acylic graph D given in fig sort the node nodes of ‘D’ by applying topological sort on D(10)ABDCEFG.for the given graph i)find the shortest path from vertex 1 to all other vertice(8)ii)find the shortest path from each vertex to all other vertex(8)mention and use the appropriate algorithm28174654323154 Explain Prim’s and Kruskal algorithm .Find the minimum spanning tree for the following graph using any one of the algorithm’s(16) abcedfg4333452241121UNIT IV : ALGORITHM DESIGN TECHNIQUESDynamic Programming: Matrix-Chain Multiplication - Elements of Dynamic Programming - Longest Common Subsequence- Greedy Algorithms: An Activity-Selection Problem - Elements of the Greedy Strategy- Huffman Codes. PART-AList out the advantages of Dynamic ProgrammingCompare greedy technique with dynamic programming method(Compare Divide and Conquer with Dynamic programming and Dynamic Programming with greedy methodWhat is the best algorithm suited to identify the topography for a graph .Mention its efficiency factorsState how dynamic Programming solves complex problemFor 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 paradigmWhat is the purpose of huffman’s treePART-BDYNAMIC PROGRAMMINGHow dynamic programming is used for computing Binomial Coefficient(16)Consider 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)GREEDY 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‘’etloFrequency111122233Write the procedure to compute Huffman code(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(8)Explain about Huffman tree with example(8)UNIT V : NP COMPLETE AND NP HARD NP-Completeness: Polynomial Time - Polynomial-Time Verification - NP- Completeness and Reducability - NP-Completeness Proofs - NP-Complete Problems PART-AP-NP-NP Complete ProblemsDepict the proof which says that a problem ‘A’ is no harder or no easier than problem ‘B’How NP hard problem are different from NP-CompleteCompare NP-hard and NP-completenessState the property of NP-Complete ProblemList the two properties that must be satisfied by a problem L to be NP completeWhat is NP CompletenessPART-BExplain 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(12)Write notes on deterministic and non-deterministic algorithms(8)State the relationship among the complexity class algorithms with the help of neat diagrams(4)Suggest an approximation algorithm, for traveling salesperson problem. Assume that the cost function satisfies the triangle inequality(8)Implement an algorithm for Knapsack problem using NP-hard approach(8)***** ................
................

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

Google Online Preview   Download