Design and Analysis of Algorithm

All Q&A

Given weight vector {15,25,35,45,55} and the profit vector {10,20,30,40,50} and a knapsack of capacity 100, find atleast three feasible solutions including optimal one for the knapsack problem of 5 items.

21 November, 2024

Why Recursion tree method is best than the Substitution method for solving a recurrence relation? Find the asymptotic upper bound of the following recurrence relation with the help of recursion tree method.

T(n)=T(n/4)+T(n/2)+Θ(n²)

21 November, 2024

Recursion tree method is best than the Substitution method for solving a recurrence relation because in recursion tree method, we draw a recurrence tree and calculate the time taken by every level of tree.

What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.

21 November, 2024

It is a problem solving technique like divide and conquer where problems are divided into subproblems. Dynamic programming is used when the subproblems are not independent.

Write quick sort algorithm. Analyze the best case and worst case time complexities of your algorithm. Perform the PARTITION operation once(one time) on the following array as per the requirement of the quicksort algorithm, assuming the last element of the array to be the pivot element. Clearly mention the steps. Arr=[2,8,7,1,3,5,6,4].

21 November, 2024

The array A[p….r] is divided into two subarrays A[p…….(q-1)] and A[(q+1)…….r] where q is the partitioning element.

Find the recurrence relation of binary search and derive the time complexity of binary search.

21 November, 2024

Binary search is a technique to find a particular element in a sorted list of elements. Suppose L is the sorted list and d is the element to be searched, lb is the lower bound of the list and ub is the upper bound of the list.

Subjects

C Programming and Practices Computer Graphics and Multimedia Mobile computing Compiler Design Database Management System Data Structures & Algorithm

Browse Streams