BCS042 Solved Assignment 202122
BCS042 Solved Assignment 202122
Subject Name  Introduction to Algorithm Design 
Assignment Code  BCS042 
Session  20212022 (July – January) 
File Type  
Number of Pages  28 
Price  Rs. 40 
To get the PDF click on the button below.
Note:

Introduction to Algorithm Design (BCS042) 20212022 (JulyJanuary)
Note: Answer all the questions in the assignment which carry 80 marks in total. 20 marks are for viva voce. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. Make suitable assumption if necessary. All algorithms should be nearer to Clanguage.
Q1: (i) Define asymptotic analysis and explain the three notations which are primarily used for asymptotic analysis with the help of examples. (7 Marks)
(ii) Write all the three cases of asymptotic analysis of the following sorting algorithms. (6 Marks)
 Bubble Sort
 Selection Sort
Q2: Find out the complexity of the following algorithm: (5 Marks)
function min (X_{1}, X_{2}…………X_{n})
min = X_{1};
for i = 2 to n
if (min > X_{i}) then
min = X_{i};
BCS042 Solved Assignment 202122
BCA 4th Sem Solved Assignment 202122
BCA 4th Sem Assignment 202122 Question PDF
Q3: Write a binary search algorithm (non recursive version) and show the complexity analysis of the algorithm step by step. (10 Marks)
Q4: (i) Write an algorithm for the fractional knapsack using greedy approach and perform complexity analysis. (5 Marks)
(ii) Find an optimal solution for the Knapsack problem for n = 5 (the number of objects) and M (Knapsack capacity) = 10. Profit and weight of each object is as follows: (10 Marks)
(P1, P2, P3, P4, P5) = (10, 25, 30, 15, 35)
(W1, W2, W3, W4, W5) = (5, 7, 4, 8, 3)
BCS042 Solved Assignment 202122
BCA 4th Sem Solved Assignment 202122
BCA 4th Sem Assignment 202122 Question PDF
Q5: (i) Write a pseudocode of evaluating polynomial expression using Horner’s rule and perform complexity analysis (step by step) (6 Marks)
(ii) Apply the above algorithm to evaluation the following polynomial expression. (4 Marks)
P(x) = 6x^{6 }+ 5x^{5 }+ 3x^{4 }+ 2x^{2 }+ 8x + 9
Q6: Multiply 3426 × 2569 using Divide and Conquer method (Apply Karatsuba’ Method). (5 Marks)
BCS042 Solved Assignment 202122
BCA 4th Sem Solved Assignment 202122
BCA 4th Sem Assignment 202122 Question PDF
Q7: Discuss all the three cases of master method to solve the recurrence. (9 Marks)
Q8: (i) Illustrate the operation of partition procedure used in Quicksort algorithm for the following array elements: (10 Marks)
45  35  10  25  18  15  22  11 
BCS042 Solved Assignment 202122
(ii) Write a recurrence relation of Quick Sort Algorithm. (3 Marks)
BCA 4th Sem Solved Assignment 202122
BCA 4th Sem Assignment 202122 Question PDF