BCS-042 SOLVED ASSIGNMENT 2017-18 FOR IGNOU BCA 4th SEMESTER

IGNOU BCA 4th SEMESTER SOLVED ASSIGNMENT 2017-18

BCS-042 Algorithm Design

QUESTIONS SOLVED IN ASSIGNMENT:

1. Use a big O notation to estimate the time required to calculate the Fibonacci series: 0 1 12 3 5 8 13 21
2. Apply Karatsuba’ algorithm using Divide and Conquer method to multiply two numbers: 2106589 and 150658
3. Question 4 is not solved.
4. Question 5 is not solved.
5. Write pseudocode for left to right binary exponentiation evaluation. Apply the algorithm for evaluating ?280 and show a step by step result.
6. 1. Write few applications of BFS and DFS. Write BFS and DFS sequences of the following graph:
   2. Write DFS algorithm and do the complexity analysis of the algorithm.
7. Explain the following terms:
   • Connected Graph
   • Optimization Problem
   • Triangle Inequality
   • Recurrence Relation
   • Mathematical Induction
8. 1. Write two applications of a spanning tree.
   2. 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.
   3. Do analysis of the algorithm.