BCS-042 Solved Assignment with solved question paper

BCS-042

1.         How can big O-notation be used to estimate the sum of the first n positive integers. (5 marks)

2.         Show how the following matrices should be multiplied using the Strassen’s algorithm.

            and       (5 marks)

3.         Using Induction method, show that for all the integers n 1² + 2² + ….. + n² =  (5 marks)

4.         What is a recurrence relation ? Where it is used ? Write recurrence relation for the followings and explain it.      (8 marks)

            (i)    Binary Search Algorithm

            (ii)   Merge Sort Algorithm

            (iii)  Fibonacci Series Algorithm

            (iv)  Quick Sort Algorithm

5.         What are the applications of spanning tree. Write Prim’s algorithm and apply it to the following graph to find out total cost of a minimum spanning tree. Show all the intermediate steps. Also, discuss time complexity of Prim’s algorithm.

6.         Define what is an optimization problem ? What are the tasks performed in Greedy method to solve optimization problem. Design a Greedy algorithm for Knapsack problem. We are given n objects and a Knapsack or a bag object. It has a weight W_i and the Knapsack has capacity m. If a fraction X_i, 0 ≤ X_i ≤ 1, of object i is placed into the Knapsack, profit of P_iX_i is earned. The objective is to fill the Knapsack in such a way as to maximize the total profit earning. (10 marks)

7.         What are the properties of a shortest path. Write Bellman Ford’s algorithm and apply it to the following graph.

            Show all the intermediate steps of the algorithm. (10 marks)

8.         Write Merge Sort algorithm and explain the operation of the algorithm with help of the following example. 70 30 20 80 40 90 25 50     (7 marks)

9.         Explain the following terms : (10 marks)

            (i)    Adjacency matrix

            (ii)   Convected graph

            (iii) Asymptote

            (iv) Time complexity             

            (v) Branch and broad

10.      Write a Pseudocode to perform a Linear Search Algorithm. Calculate the total number of comparison-operations, assignment-operations and how many times the loop will execute for finding the smallest number in an array ?

****************************************************************

Note: Answer with Dotcom Books

www.dotcombooks4u.com

(Last 5 year solved question paper with Assignment solutions)

9825183881

 ***************************************************************