## IGNOU BCA 4th SEMESTER SOLVED ASSIGNMENT 2017-18

### BCS-042 Algorithm Design

#### QUESTIONS SOLVED IN ASSIGNMENT:

- Use a big O notation to estimate the time required to calculate the Fibonacci series: 0 1 12 3 5 8 13 21
- Apply Karatsuba’ algorithm using Divide and Conquer method to multiply two numbers: 2106589 and 150658
- Question 4 is not solved.
- Question 5 is not solved.
- Write pseudocode for left to right binary exponentiation evaluation. Apply the algorithm for evaluating ?280 and show a step by step result.
- Write few applications of BFS and DFS. Write BFS and DFS sequences of the following graph:
- Write DFS algorithm and do the complexity analysis of the algorithm.

- Explain the following terms:
- Connected Graph
- Optimization Problem
- Triangle Inequality
- Recurrence Relation
- Mathematical Induction

- Write two applications of a spanning tree.
- 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.
- Do analysis of the algorithm.

**« BCA 4th SEMESTER SOLVED ASSIGNMENTS**