Lab Questions and Solutions of DAA
Ques 1/ Assi 1 Hi All, in this lab you will design and Implement an algorithm for fractional knapsack in O(n) time. Plot the runtime with respect to the varying input size. Also, submit the documentation + code including the screenshots if any. You can choose the C/C++/python to implement it. You can use MS excel/matplotlib to plot the graph.
Ques 2/ Assi 2 Hi All, in this lab you will Design and Implement an algorithm for 0/1 knapsack using branch and bound. Also, submit the documentation + code including the screenshots if any. You can choose the C/C++/python to implement it. You can use MS excel/matplotlib to plot the graph.
Ques 3/ Assi 3 Hi All, in this lab you will code the following problem problem statement: Given a matrix whose rows and columns are sorted. Design and implement an efficient algorithm for searching a given element. Take a small matrix say 4x4 which satisfies the above condition to prove the correctness of your algorithm.
Ques 4/ Assi 4 Problem statement. Design and implement matrix chain multiplication using dynamic programming and print the minimum number of multiplications required to perform the operation. Consider the matrix with dimension A(4060), B(6020), C(2010), D(105), E(5*80). Please mention time complexity of the algorithm in the documentation.
Ques 5/ Assi 5 Problem statement: We have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Examples:
Input : k = 2, A = {10, 10, 10, 10}
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter
gets 20 units of board and the total
time taken is 20.
Input : k = 2, A = {10, 20, 30, 40}
Output : 60.
Here we can divide first 3 boards for
one painter and the last board for
second painter.
Also, submit the documentation including time complexity, algorithm and code. You can also include the screenshots if any.