DAA QUESTION BANK (END SEM)
UNIT -3
[Link]. Questions
Q1 Solve the matrix chain multiplication for the following matrix problem using Dynamic
programming.
Matrix A1 A2 A3 A4 A5 A6
Dimensions 10*20 20*5 5*15 15*50 50*10 10*15
Q2 Explain Greedy strategy: Principle, control abstraction, time analysis of control abstraction
with suitable example.
Q3 Differentiate between O (1) and O(n)? ls algorithm performance depends on input size
(True/False) Justify your answer with suitable example?
Q4 What are the applications of greedy strategy? Explain the concept of optimal solution
Q5 Write an algorithm for job scheduling. Also comment on its
Time complexity.
Q6 Explain Dynamic programming: Principle, control abstraction, time analysis of control
abstraction with suitable example.
UNIT -4
[Link]. Questions
Q1 What is branch and bound algorithmic strategy? Apply branch n bound
algorithmic strategy to solve traveling salesman problem for
Q2 Explain with suitable example Backtracking: Principle, control abstraction, time
analysis of control abstraction.
Q3 Explain the ‘branch and bound’ approach for solving problems. Write a branch
and bound algorithm for solving the 0/1 Knapsack problem. Use the same
algorithm to solve the following 0/1 Knapsack problem. The capacity of the
knapsack is 15 kg.
Q4 What is Branch and Bound method? Write control Abstraction for Least Cost search?
Q5 Obtain any two solutions to 4 queen problem .Establish Relation between them.
Q6 Compare between dynamic programming and greedy approach.
UNIT 5
[Link]. Questions
Q1 Write short notes on with suitable example of each
i) Randomized algorithm
ii)Approximation algorithm
Q2 What is embedded algorithm? Explain Embedded System scheduling using power optimized
scheduling algorithm.
Q3
Q4 What is Potential function method of amortized analysis? To illustrate Potential method, find
amortized cost of PUSH, POP and MULTIPOP stack operations.
Q5 What is amortized analysis? Explain the aggregate method with example
Q6 What are special needs of embedded algorithm? Which sorting algorithm is best for
embedded systems? Why
UNIT 6
Q1 Write and explain pseudo code for Multi-threaded merge sort algorithm. How parallel
merging gives a significant Parallelism advantage over Merge Sort?
Q2 With respect to Multithreaded Algorithms explain Analyzing multithreaded algorithms,
Parallel loops, Race conditions.
Q3 Write a pseudo code for naïve string matching algorithm and Rabin- Karp algorithm for
string matching and analyze the same.
Q4 For string matching, working module q = 11, how many spurious hits does the Rabin-
Karp matcher encounters in Text T = 31415926535
i) T = 31415926535
ii) P=26
iii) Here [Link] = 11 so Q = 11
iv) And P mod Q = 26 mod 11 = 4
v) Now find the exact match of P mod Q...
Q5 Explain an algorithm for Distributed Minimum Spanning Tree.
Q6 Write short notes on the following.
i) Multithreaded matrix multiplication.
ii) Multi threaded merge sort
iii) Distributed breadth first search