BCS-042 Solved Assignment 2021-22

BCS-042 Solved Assignment 2021-22

To get the PDF click on the button below.

Introduction to Algorithm Design (BCS-042) 2021-2022 (July-January)

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 C-language. 

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₁, X₂…………X_n)
min = X₁;
for i = 2 to n
if (min > X_i) then
min = X_i;

BCS-042 Solved Assignment 2021-22

BCA 4th Sem Solved Assignment 2021-22

BCA 4th Sem Assignment 2021-22 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)

BCS-042 Solved Assignment 2021-22

BCA 4th Sem Solved Assignment 2021-22

BCA 4th Sem Assignment 2021-22 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⁶ + 5x⁵ + 3x⁴ + 2x² + 8x + 9

Q6: Multiply 3426 × 2569 using Divide and Conquer method (Apply Karatsuba’ Method). (5 Marks)

BCS-042 Solved Assignment 2021-22

BCA 4th Sem Solved Assignment 2021-22

BCA 4th Sem Assignment 2021-22 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)

BCS-042 Solved Assignment 2021-22

(ii) Write a recurrence relation of Quick Sort Algorithm. (3 Marks)

BCA 4th Sem Solved Assignment 2021-22

BCA 4th Sem Assignment 2021-22 Question PDF