BCS 42 Introduction to Algorithm Design

Q1. For the function defined by

f(n) = 2n3 + 3n2 +1 and g(n) = 2n3 + 1: show that
(i) f(n) = Ɵ(g(n))
(ii) f(n) != Ɵ(n2)
(iii) n4 != Ɵ (g(n))

Q2. Find the optimal solution for the knapsack instance n=7 and M=15

(P1, P2,——————–Pn) = (12, 4, 14, 8, 9, 20, 3)
(W1, W2, ——————–Wn) = (3, 2, 5, 6, 4, 1, 7)

Q3. Apply Kruskal’s Algorithm on the following graph to find minimum cost spanning tree

Q4. Apply Dijkastra’s Algorithm to find the shortest path from source vertex ‘A’ to all other vertices for following graph.

Q5. Analyze best case, average case, and worst-case time complexities of following algorithms with the help of suitable examples.

(i) Insertion sort
(ii) Quick sort
(iii) Binary search
(iv) Selection sort

Q6. Multiply 2146782 x 0422812 using divide and conquer technique(use karatsuba method).

Q7. Explain DFS and BDS graph traversal algorithms with the help of a suitable example.

Q8. Write recurrence relations for matrixmultiplication using Strassen’s method andsolve it using the Master method.

Q1. Define asymptotic analysis and explain the three notations which are primarily used for asymptotic analysis with the help of examples.

Q2. (a) Define Tower of Hanoi problem as a recurrence relation problem and solve it through a recurrence tree.
(b) What is Master Method? Write all the three cases of Master Method to solve the following recurrence relation:
T(n) = aT (n/b) + f(n) and explain.

Q3. (a) Find the optimal solution to the fractional Knapsack problem using Greedy technique:
Number of objects n: 6
Maximum Weight M = 25
Value of each item:
(𝑃1 , 𝑃2 , 𝑃3 , 𝑃4 , 𝑃5 ,𝑃6 ) = (10, 20, 30, 35, 45, 55)
Weight of each item:
(𝑊1 , 𝑊2 , 𝑊3 , 𝑊4 , 𝑊5 ,𝑊6 ) = (5, 10, 12, 13, 15, 20)
(b) Perform the multiplication of the following two matrices A and B using Strassen’s method showing all the intermediate steps.

Q4. Write a pseudocode of evaluating polynomial expression using Horner’s rule and perform complexity analysis (step by step). Apply it to evaluation the polynomial expression:
P(x) = 3x 6 + 4x 5 + 2x 4 + 2x 3 + 8x + 9

Q5. Write pseudocode for left to right binary exponentiation evaluation. Apply the algorithm `for evaluating a280 and show a step by step result.

Q6. Write Kruskal’s algorithm for finding minimum cost spanning tree using greedy approach and apply to the following graph and show step by step results

Q7. What is edge relaxation technique in shortest path algorithm? Write and apply Bellman Ford’s algorithm to find the shortest path from a node A to all the remaining nodes in the following graph:

Q8. Write Quick Sort algorithm to sort the following list of integer numbers. Show all the intermediate steps
15, 12, 18, 5, 6, 8, 22, 3, 25, 30, 35, 8, 32
Also compute the worst case time complexity of the algorithm.