Daa

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Daa as PDF for free.

More details

  • Words: 501
  • Pages: 2
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.

Related Documents

Daa
November 2019 35
Daa
November 2019 28
Daa
August 2019 63
Daa Notes.pdf
November 2019 21