Course Code BCSL-045 Course Title Introduction to Algorithm Design Lab Assignment Number BCA(4)/L-045/Assignment/2019-20 Maximum Marks 50 Weightage 25% Last date of Submission 15th October, 2019 (For July 2019 Session) : 15th April, 2020 (For January 2020 Session)

Note: Answer all the questions in the assignment having 40 marks in total. 10 marks are for viva voce. You are required to write programs in C-language for all the problems , execute and show the results. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. Make suitable assumption if necessary.

Q1. Write a program to compute Xn, where both X and n and integer numbers using

left to right binary exponentiation algorithm. (5)

Q2. Write a program to find the largest number in the five array using linear search algorithm. Calculate the total no of comparison operations and the number of times the loop will execute. (5)

85 45 70 30 25 35 40 5 10 17

Q3. Write a program to traverse a graph using BFS. Apply this algorithm to the following graph and write the sequence of vertices to be travelled. Also calculate the number of times the loop(s) will execute. (7)

A B

D E F G

Q4. Implement GCD (Greatest common divisor) problem using Euclid’s algorithm. Apply this algorithm to find the output of GCD of 225 and 15. Also calculate how many times the mod and equal operations will execute. (5)

Q5. Implement and apply Kruskal’s algorithm to find a minimum cost spanning tree

and test the result for the following graph: (7)

18

14 6

e 9 7

12

f 6 10 c 5 1

d 2 8

5

Q6. Implement Karatsuba’s method using Divide & Conquer method to multiply two integer numbers. Test the result in multiplication of the following numbers and count the number of multiplication operations. 5 3 2 6 8 0 * 4 3 2 8 6 (5)

Q7. Draw a complete graph with 6 vertices. Write a C-Program to represent the graph using adjacency matrix and adjacency list. (6)