GTU 3150703 Analysis and Design of Algorithms (ADA) Winter 2023 Question Paper & PDF

Illustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 50, 52, 60. Comment on the nature of input i.e. best case, average case or worst case. Also discuss worst and best case of quick sort algorithm.

Sort the List “G,U,J,A,R,A,T,S,A,R,K,A,R” in alphabetical order using merge sort.

Following are the details of various jobs to be scheduled on multiple processors such that no two processes execute at the same on the same processor. Show schedule of these jobs on minimum number of processors using greedy approach. Jobs J1 J2 J3 J4 J5 J6 J7 Start time 0 3 4 9 7 1 6 Finish time 2 7 7 11 10 5

Using algorithm find an optimal parenthesization of a matrix chain product whose sequence of dimension is (5,10,3,12,5,50,6) (use dynamic programming).

Solve the following Task Assignment problem for minimization using following cost matrix. (Cost matrix represents cost of Task T performed by Person P). T1 T2 T3 P1 10 20 25 P2 20 23 26 P3 12 16 25

Given coins of denominations 2, 3 and 4 with amount to be pay is 5. Find optimal no. of coins and sequence of coins used to pay given amount using dynamic method.

Write an algorithm to find out the articulation points of an undirected graph. Find out articulation points for the following graph. Consider vertex 0 as the starting point.

Demonstrate Binary Search method to search Key = 14, form the array A = <2,4,7,8,10,13,14,60>.

Solve the following knapsack problem using greedy method. Number of items = 5, knapsack capacity W = 100, weight vector = {50,40,30,20,10} and profit vector = {1,2,3,4,5}.