[go: up one dir, main page]
Scribd
Upload
54 views6 pages

Sample Questions Daa

Uploaded by

Anshu Bhadani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views6 pages

Sample Questions Daa

Uploaded by

Anshu Bhadani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Sample Questions

1. Construct a dynamic programming algo to find the length of the longest common
subsequences of two strings.
2. Explain what "asymptotic analysis" is and how it helps in evaluating the efficiency of
algorithms.
3. Solve the recurrence relation 1. T(n)=128T(n/2)+log⁡ 3n 2. T(n)=9T(n/3)+n
3. T(n)=T(2n/3)+1 4. T(n)=3T(n/4)+nlogn

4. Use the recursion tree method to solve the recurrence 1. T(n)=2T(n/2)+Θ(n)


2. T(n)= 2T (n/4) + cn2

5. Explain best-case, worst-case and average-case time complexity.


6. Analyze the space complexity of an iterative approach to calculating factorials and
bubble sort.
7. Design a recursive algorithm to calculate the factorial of a natural number. Establish the
recurrence relation for the number of basic operations and solve it.
8. Using the heap sort algorithm, sort the sequence {42, 19, 33, 78, 56, 90, 24, 67}.
Demonstrate each step of the sorting process and provide the final sorted sequence.
Given integers {18, 54, 9, 72, 30, 41, 85, 11, 25, 67, 29, 88, 35, 14, 70, 52}, construct a
Max-heap and a Min-heap. Afterward, perform re-heaping when the root node is deleted
in both cases.
9. Insert the keys {20, 18, 22, 25, 17, 30, 12, 27} into an empty red-black tree. For each
insertion, identify the applicable case and illustrate the tree's structure after each step.
10. Explain Radix Sort algorithm step wise with proper examples. Apply Radix Sort to the
following set of numbers: 5874, 2993, 7401, 8052, 4126, 1639, 9547, 2885, 6708, 3914,
2356, 8142, 4617, 3829, 1456.
11. Explain Bucket Sort algorithm step wise with proper examples. Sort the values [0.42,
0.23, 0.89, 0.56, 0.34] using the bucket sort algorithm.
12. Design a binomial heap for the sequence of numbers 5, 12, 3, 19, 8, 14, 7, 11, 9, 16, 4.
Additionally, perform the operation of extracting the minimum key from the resulting
binomial heap.
13. Describe the CONSOLIDATE and UNION operation in a Fibonacci Heap using an
appropriate example.
14. Develop an algorithm for counting sort. Apply your algorithm to the following set of data
and show the status of all three arrays used: 3, 1, 4, 1, 2, 5, 2, 7, 6, 3, 8, 5, 9, 1, 4, 6, 7,
2.
15. Compare the trade-offs between various sorting algorithms using their time and space
complexities, considering algorithms like Merge Sort, Quick Sort, and Heap Sort.
16. Develop the Quicksort algorithm and apply it to the following sequence: { 15, 6, 3, 9, 12,
4, 18, 25, 7 }, using 3 as the pivot element.
17. Develop the Merge Sort algorithm and apply it to the following sequence: { 14, 5, 9, 2, 7,
10, 20, 11, 3 }. Show the steps involved in sorting the sequence.
18. Compare the trade-offs between dynamic programming and greedy algorithms in terms
of efficiency and applicability to different types of problems.
19. Explain the method of designing a greedy algorithm and the key steps involved in its
development.
20. Describe the working of a greedy algorithm using the coin change problem and traveling
salesman problem as an example to illustrate the process.
21. What is an optimal Huffman code for the following set of frequencies, based on the first 8
prime numbers? a:2, b:3, c:5, d:7, e:11, f:13, g:17, h:19
22. Explain the 0/1 knapsack problem? Solve the following instance using the Greedy
approach and write the corresponding algorithm. Knapsack Capacity = 15, P = <4, 10,
15, 25, 30> and w = <2, 3, 4, 6, 8>
23. Describe the string matching problem? Consider a modulus q=13, how many spurious
hits does the Rabin-Karp matcher encounter when searching for the pattern P=34 in the
text T=2718281828459045
24. Use LUP Decomposition to solve the following system of equations. As an example of
this method, consider the system of linear equations defined by:

2x + 3y - z = 5, 4x + y + 2z = 6, -3x + 2y + 3z = 7n

25. In question different type of graph is given, you can evaluate the performance of
fibonacci heap after applying consolidation process
26. Explain the Fib-Heap Extract min process and apply the process in the given examples.

27. Explain the minimum spanning tree. Explain the BFS and DFS process with proper
example apply BFS and DFS in below example.

28. Explain the travelling salesman problem with approximation and Dynamic programming.
Find the TSP tour of the given garph.
29. Draw BSTs of height 2, 3 and 4 on the set of keys { 10, 4, 5, 16, 1, 17, 21}.
30. Draw all legal B-Trees of minimum degree 2 that represent { 10, 12, 13, 14, 15}.
31. Let X be a no-full internal node of a B-Tree. Let be an index such that Y = Ci[X] is
a full child of X. Write a procedure that splits Y such that X has an additional child
now.
32. Define Fibonacci Heap. Discuss the structure of a Fibonacci Heap with the help of
a diagram. Write a function for uniting two Fibonacci Heaps.
33. Describe the properties of binomial tree. Construct the binomial heap for the
following sequence of numbers 7,2,4,17,1,11,6,8,15,10,20. Also apply the
operation of extracting the minimum key in the resulting binomial heap.
34. Solve the following recurrences using suitable methods:
i. T(n)=5T(n/2 +16) +n2
ii. T(n) = T(√n) +n
1
iii. 𝑇 (𝑛) = 3𝑇(𝑛 ⁄3 ) + 𝑙𝑜𝑔3 n
𝑛 𝑛
iv 𝑇 (𝑛) = 𝑇 ( ) + 𝑇 ( ) + 𝑛2
4 2
v. T(n) = 2T(n/2) +n2
35. Explain in detail about Prims’s algorithm with example and analyze its efficiency.
36. Define knapsack problem. Find the optimal solution to the knapsack instance n=5.
W={20, 30, 40, 10, 7}, p={7, 8, 9, 1,6} and C=80 using greedy method.
37. Why Dijkartra and Bellmen ford algorithm are differing from each other? Even both
are single-source SP.
38. Find the shortest path using Dijkatra algorithm, Explain properly

39. Apply Bellman Ford algorithm and find the result in all iteration

40. Use Prim.s and Kruskal Algorithm to find the minimum spanning tree of the following
41. Explain Floyd Warshell all pair shortest path method and construct the all pair shortest
path of the given graph using above method.

42. Define knapsack problem. Find the optimal solution to the knapsack instance n=5.
W={20, 30, 40, 10, 7}, p={7, 8, 9, 1,6} and C=80 using greedy method.
43. What is 0/1 knapsack problem? Solve the following instance using Greedy
approach, also write the algorithm Knapsack Capacity = 10, P=<1, 6, 18, 22, 28>
and w=<1, 2, 5, 6, 7>
44. For N=4, write all the valid solutions (row-column placements) where 4 queens can be
placed on a 4x4 chessboard without threatening each other. Visualize one solution as a
chessboard.
45. What are the constraints in the N-Queens Problem, and how do they ensure that no
two queens threaten each other on the chessboard?
46. Explain how backtracking is used to solve the N-Queens Problem. What are the key
steps involved in the algorithm?
47. Describe the structure of a Fibonacci Heap and explain the role of the following
components:

 Root list
 Marked nodes
 Child pointers
How do these contribute to its efficiency?

48. Explain BST algorithm and its time complexity.

Given the dimensions of matrices:

 A1: 2×4
 A2: 4×5
 A3: 5×6
 A4: 6×3
 A5: 3×2

Determine the optimal order of multiplication to minimize the total number of scalar
multiplications using the Dynamic Programming Approach.

Matrix Dimensions Array:


p=[2,4,5,6,3,2]

Compute the minimum cost of matrix multiplication.

 Provide the optimal parenthesization.

49. Discuss the Longest Common Subsequence (LCS) problem. Generate one LCS for
the given two strings using Dynamic Programming.

Given the strings:

 X=agbcba
 Y=abcbga

Find one Longest Common Subsequence (LCS) using the Dynamic Programming approach.

You might also like