Daa

DRONACHARYA COLLEGE OF ENGINEERING Subject : DAA Trade : CSE/IT

Sem : Vth

UNIT - 2 1. Prove that a red-black tree with n internal node has height at most 2lg(n+1). 2. Show the result of inserting the keys F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E in order ,in an empty B-tree.Use t=4, where t is min degree of B-tree. 3. Write an algorithm to perform insertion into a B-tree 4. What are three different cases, where inserting a node into a Red Black Tree ? Explain with example. 5. Explain the different conditions of getting union of two existing binomial heaps.

UNIT – 3 1. Explain dynamic programming. Apply it on Matrix Chain-Multiplication problem. 2. Explain 0/1 and fractional knapsack problem with the help of greedy algorithm. 3. What are different Greedy Criterion ? Explain. Consider the five items along with their respective weights and values : I = { I1, I2, I3, I4, I5 } W = {5, 10, 20, 30, 40 } V = { 30, 20, 100, 90, 160 } The knapsack has capacity W = 60 . Find the solution of the problem using the Concept of fractional knapsack. 4. Find the amortized cost for Enqueue ( Insertion ) and Dequeue ( Deletion ) Operations in a queue using accounting method. 5. What is backtracking. Explain subset sum problem using backtracking.

UNIT – 4 1. Show how to compute transitive closure of a graph using Floyd – warshell’s algorithm for all pairs shortest paths. 2. What is minimum spanning tree of a graph ? Describe PRIM’s algorithm to find MST alongwith its running time 3. Explain and write the Bellman – Ford algorithm. You are also required to find the running time of the algorithm. 4. Prove that if the weights on the edge of the connected undirected graph are distinct

then there is a unique Minimum Spanning Tree. Give an example in the regard. Also Discuss Kruskal’s Minimum Spanning Tree in detail. 5. We would like to solve, as efficiently as possible , the single source shortest path Problems in each of the following graphs. For each graph, state which algorithm would be best use and give its running time : (i) A weighted directed acycled graph. (ii) A weighted directed graph, where all edge weights (iii) A weighted directed graph in which some, but not all, of the edges,but negative weights, the graph contains a directed cycle.

UNIT – 5 1. Write knuth-Morris-Pratt algorithm for string matching. 2. Show that 3-CNF is a NP-Complete class of problem. 3. Define approximation algorithms.What is approximation ratio?Approximate the Traveling salesman problem with triangle inequality. 4. Give the randomized version of Quicksort. Analyse it for finding the expected running time. 5. Explain and write the Naïve-String string matching algorithm : Suppose the given pattern P = a a b and given and text T = a c a a b c. Apply Naïve – String Matching algorithm on above Pattern (P) and Text (T) to find the number of occurrences of P in T.