IGNOU BCS-42 - Introduction to Algorithm Design

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.

Q1. Define time and space complexity of linear search algorithm. Calculate how many times the assignment operation will execute in the following code fragment for ( i = 0, i < n, i++) for (j = 0, j < m, j++) { x = x + 7; } Q2. For the function defined by f(n) = 3𝑛2 + 4𝑛 +6 and g(n) = 𝑛2, Check if the following are true or not? (i) f(n) = Ω(g(n)) (ii) 𝑛3 = Ω(g(n)) (iii) f(n) ≠ Ω(𝑛4) Q3. (a) Write important features of Quick Sort algorithm. How is it different from Selection Sort and Insertion Sort algorithms in terms of the sorting processes? Apply Quick Sort algorithm to do sorting of the following array of integer numbers in ascending order. Write the pseudo-code and show all the intermediate processes of the running of the code/algorithm. (b) Compute worst case and best case time complexities of Binary Search algorithm. When the worst and best cases of Binary Search algorithm would occur? Explain. Q4. (a) Describe the followings problems in brief and define its recurrence relation: (i) Merge Sort Problem (ii) Karatsuba Method (b) Define the recurrence relation of the following function (c) Solve the following recurrence relation using both Substitution and Master methods. Q5. Write a Linear Search algorithm to search for number 36 in the following list of integer numbers. How many search operations will be required in this example. Show all the intermediate steps. Which are the other algorithms which perform better than the linear search algorithm? Discuss the worst case and average case time complexity of the algorithm. Q6. What is the idea behind binary exponent evaluation? Write pseudo-code to compute a n using right to left and left to right binary exponentiation algorithm and perform its complexity analysis. Apply the algorithm to compute a 55 and calculate the total number of multiplication operations in this case. How many multiplication operations are required if brute force multiplication method is used in this example? Show all the intermediate steps. Q7. (a) Discuss the working of DFS and BFS algorithms with suitable examples. (b) Write Kruskal’s algorithm to calculate the minimum cost spanning tree of the following graph and calculate the time complexity of the algorithm. Show all the intermediate steps. Q8. Sort the following sequence using Bubble Sort algorithm. Show all the intermediate steps/ passes involved in sorting. Q9. (a) Write general form of Divide & Conquer and Greedy Techniques. (b) Formulate a Knapsack problem and apply it to find an optimal solution for the following Knapsack problem. Use any two approaches: Kapacity of Knapsack: 23 Number of Objects: 7 Profits 𝑃𝑖 and weights 𝑊𝑖 of objects are defined as follows: (𝑃1, 𝑃2 , 𝑃3 , 𝑃4 ,𝑃5, 𝑃6, 𝑃7) = (13, 11, 18, 9, 7, 22, 5) (𝑊1, 𝑊2,𝑊3,𝑊4, 𝑊5, 𝑊6, 𝑊7) = (7, 6, 8, 4, 6 , 3, 5) Q10. What is graph? List few applications of graph traversal schemes. For the following graph write adjacency list and adjacency matrix.