Question Bank Daa Final

S.No.
Cos Blooms Level
1 CO1 K1
2 CO1 K2
3 CO1 K1
4 CO5 K1
5 CO4 K4
6 CO5
K3
7
8 CO4 K3
CO4 K3
9
10 CO3 K3
11 CO4 K3
CO1 K3
12
13 CO5 K3
14 CO4 K6
15 CO5 K6
16 CO1 K5
17 CO1 K2
18 CO1 K2
19 CO1 K2
20 CO2 K2
21 CO5 K2
22 CO1 K2
23 CO1 K2
24 CO2 K4
25
26 CO3
K6
27
28 CO3 K1
29 CO4 K4
30 CO4 K2
31 CO3 K2
32 CO4 K6
33 CO4 K6
34 CO5 K6
35 CO3 K6
36 CO3 K5
37 CO5 K1
38 CO3 K2
39 CO2 K4
40 CO4 K3
41 CO3 K6
CO4
42
43
44
45 K5
46
47
48
49
50 CO4 k2
51 CO5 k1
52 CO4 k1
53 CO5 k6
54 CO5 k3
55 CO4 k4
56 CO4 k1
57 CO4 k1
58 CO4 K4
59 CO4 K4
60 CO4 K3
61 CO4 K5
62 CO4 K4
63 CO4 K2
64 CO4 K2
65 CO4 K3
66 CO4 K4
67 CO1 K2
68 CO1 K2
69 CO3 K3
70 CO1 K3
71 CO1 K2
72
73 CO4 K3
74 CO4 K1
75 CO1 K3
76 CO3 K2
77 CO4 K6
78 CO2 K2
79 CO5 K6
80 CO3 K6
81 CO4 K3
82 CO4 K5
83 CO5 K1
84 CO5 K5
85 CO3 k1
86 CO4 K5
87 CO2 k4
88 CO4 K3
89 CO3 K3
90 CO4 K4
91 CO3 K4
92 CO4 K3
93 CO3 K4
94 CO3 K3
95
Question
Distinguish NP- hard and NP-Complete problems

Explain NP-Hard Problems.
Write a short note on dynamic programming
List out any four techniques, which implements greedy method.
Give an algorithm for graph coloring problem and analyze its complexity
Solve the following 0/1 Knapsack Problem using Dynamic Programming.
There are five items whose weights and values are given in following arrays. Weight w [] = {1,2,5,6,7} Value v [] = {1, 6, 1
Construct a Red Black tree by inserting 9,19,30,15,16 and 27 into an initially empty tree and also delete 15,16 and 30 from
Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,...p6)=(w1,w2,...w6)=(100,50,20,1
Solve the Travelling Salesman problem using branch and bound algorithms.
Apply Merge Sort to sort the list a[1:10]=(31,28,17,65,35,42.,86,25,45,52). Draw the tree of recursive calls of merge sort, m
Solve using Masters theorem i) T(n)=2T(n/4)+√n ii) T(n)=7T(n/2)+ n2
What is backtracking ? solve 8 queens problem using backtracking and draw state space tree.
Write an algorithmt String Matching using Rabin-Karp algorithm and also analyze its complexity.
Write an algorithm to solve the N-Queens problem. Show working for N=4.
Write in detail about Hamiltonian cycles.Explain with the help of example.
Explain back tracking in algorithms.
give an algorithm for graph coloring problem and analyze its complexity
Differentiate (0/1) knapsack problem and fractional knapsack problem with examples and justify your answer.
Explain the Divide and Conquer Algorithmic Paradigm. Also list a few algorithms which use this paradigm.
Explain the greedy algorithms with an example.
Explain the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using the same.
Explain the recursive algorithms? State the important rules which every recursive algorithm must follow.
Differentiate between divide and conquer and dynamic programming problem solving approach.
Analyse and solve for optimal sequence for the folllowing matrices A 4X10, B 10X3, C 3X12, D 12X20 and E 20X7.
Prove that vertex cover is NP complete.
Define P, NP, NP-Hard and NP-Complete Problem.

Construct the state space tree Diagram for 4 Queen problem.
Demonstrate the Merge Sort Method. Give its best case, worst case and average case complexity.
Explain naive string matching algorithm with example.
Discuss how Fibonacci heap is different from binomial heap?
Build chromatic number of the following graph-
Design a fractional knapsack problem with an example.

Construct a traveling salesman problem with a suitable example. Prove that it is NP-complete problem.
State whether the Hamiltonian problem is an NP-Complete problem? Justify your answer.
Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42) find the maximum profit using dynamic method.
Write difference between P, NP, NP complete and NP hard problem.
Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.
How backtracking can be used to solve N-queens problem.
Prove Hamiltonian cycle is in NP.
Which of the following is / are Hamiltonian graphs?
Explain elements of Dynamic programming.
Differentiate greedy method and dynamic programming approach.
Analyse the need of Dynamic programming over recursion. Take example of fibonacci series to explain the same.
Compute the optimal solution for knapsack problem using greedy method N=3, M= 20, (p1,p2,p3)= (25,24,15), (w1,w2,w3
Give a linear time algorithm for fractional knapsack problem?
Why don’t we allow a minimum degree of y=1 for a B-Tree?
Show all legal B-trees of minimum degree 2 that represent {1, 2, 3, 4, 5}
Define Hamiltonian Cycle of a graph
Show the status of the array containing values 12, 1, 8, 55, 46, 33, 2, 18, 24 after two passes of Selection Sort that sorts them
A cocktail shaker sort designed by Donald Knuth is a modification of Bubble Sort in which the direction of bubbling chang
Write down the algorithm for Binary Search. What are the conditions under which sequential search of a list is preferred ov
Modify the Binary Search Algorithm such that it becomes a search and insertion algorithm. That is if the element looking f
Work through Binary Search algorithm on an ordered file with the following keys: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. D
Write down the algorithm for insertion sort. When do we use insertion sort.
Write the algorithm for selection sort. What is the best and worst case complexities of selection sort.
Sort the following set of keys using Merge sort
12, 3, 34, 45, 11, 7, 26, 98, 5, 43, 9, 15, 8
Write an algorithm to analyze the behavior of Quick Sort when the given input is already reverse sorted and all the element
Explain Asymptotic notations in algorithm analysis
Explain time and space complexity with examples
Solve the Travelling Salesman problem using branch and bound algorithms.
Solve using Masters theorem i) T(n)=2T(n/4)+√n ii) T(n)=7T(n/2)+ n2
Explain Fibonacci heap.
Construct a travelling salesman problem with a suitable example. Prove that it is a NP- Complete problem.
Explain the Quick Sort algorithm and sort the following array 4, 3, 1, 9, 8, 2, 4, 7 with the same.
Discuss the behavior of Quick Sort when the input is already sorted.
Organize the following rate of growth in increasing order. 2N, n log n, n2, 1 , n, log n, n!, n3
Explain naive string matching algorithm with example.
Create a Red Black tree given input 2, 1, 4, 5, 9, 3, 6, 7.
Explain Strassen’s algorithm for matrix multiplication.
Design a fractional knapsack problem with an example.
Construct a traveling salesman problem with a suitable example. Prove that it is NP-complete problem.
Explain Dynamic Programing with the help of matrix chain multiplication problem and discuss its necessary conditions for
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. Prove that the worst case complexi
Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42) find the maximum profit using dynamic method.
Given a set of positive integers, and a value sum, determine that the sum of the subset of a given set is equal to the given su
Explain chromatic number decision problem and clique decision problem
Deduce the complexity of Quick Sort algorithm in its best, worst and average cases.
Explain the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using t
Interpret the need of Dynamic Programming over Recursion. Take suitable example to illustrate the above need.
Examine and create a B-Tree of order 4 by inserting following key values: 6, 5, 22, 9, 2, 13, 3, 7, 11, 12, 4, 8.
Solve the below graph for the shortest path using multistage graph method with dynamic programming approach.
Construct a Red Black tree by inserting 9,19,30,15,16 and 27 into an initially empty tree
How Red-Black tree is different from B-Tree. Explain with example.
Solve the below graph for the shortest path using multistage graph method with dynamic programming approach.
. Write down the problem statement of TSP. Explain it with the help of an example.
Marks
5
5
5
5
5
10
10
5
5
15
15
5
10
5
5
10
5
10
15
5
5
5
5
5
10
10
5
5
5
5
5
10
5
10
15
10
10
5
5
5
15
5
5
5
5
5
5
5
5
5
5
10
5
5
5
5
5
10
5
5
10
10
5
15
10
10
5
5
10
5
5
10
15
5
15
10
5
5
10
15
10
15
15
10
10
10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

Question Bank Daa Final

Uploaded by

Copyright:

Available Formats

Question Bank Daa Final

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Question Bank Daa Final

Uploaded by

Copyright:

Available Formats

S.No.

Cos Blooms Level

Distinguish NP- hard and NP-Complete problems

Prove that vertex cover is NP complete.

Define P, NP, NP-Hard and NP-Complete Problem.

Design a fractional knapsack problem with an example.

You might also like