ADA – BCS401
Module-1
1. Summarize the sequence of steps involved in designing and analyzing an algorithm and explain any
two steps in detail.
2. Explain the notion of an algorithm. Design Euclid’s algorithm for computing GCD(m,n). Find the
GCD(60,24) using Euclid’s algorithm.
3. If t1(n) ∈ O(g1(n)) and t2(n) ∈O(g2(n)) , then prove that : t1(n) + t2(n) ∈ O(max(g1(n), g2(n))).
4. Develop an algorithm for pattern matching by using brute force technique. Trace the algorithm for
the text string “ NOBODY_NOTICED_HIM” and pattern string “ NOT”
5. Explain the general plan for analyzing recursive algorithms mathematically and apply it to determine
the time complexity of an algorithm to find the factorial of a number
6. Explain general plan of mathematical analysis of non-recursive algorithms and use the same to find
the time complexity of element uniqueness problem.
7. Discuss the characteristics of an Algorithm. Write the algorithm for finding the Fibonacci series of a
number. Find its worst time complexity
8. Asymptotic efficiency plays a crucial role in analysingx the performance of algorithms. For each
efficiency class, Provide formal definitions, mathematical representations, and real-world examples
to illustrate their practical applications in algorithm analysis.
9.
i). What does the Algorithm verifies or calculates?
ii). What is the basic operation?
iii). What is the efficiency of this algorithm?
iv). Calculate the worst time complexity of this algorithm.
v). Identify the type of this algorithm(Recursive/Non-
Recursive).Give the reason for your choice
10. Demonstrate space and time complexity with relevant examples. Apply these concepts to solve a
problem and show their impact on algorithm performance.
Module-2
1. Explain Strassen’s Matrix Multiplication approach with a suitable example. Apply its method to solve
a 2×2 matrix multiplication and derive its time complexity.
2. Apply Insertion on these elements– [learn the steps, numbers may differ]. Find its worst case and
Average case efficiency.
3. Explain the concept of Divide and Conquer. Apply this approach to write and solve a recursive
algorithm for Binary Search on a given list of elements.
4. Apply Source removal method and DFS method to obtain Topological sort for the Given Graph: –[learn
the steps, Graph may differ].
5. Construct a 2-3 Tree for the list – [learn the steps, numbers may differ]. Use the alphabetical order
of letters and insert them successively starting with the empty tree.
6. Solve the following instance of brute force knapsack problem where, n=4, m=10,p={40,42,25,12} and
w={4,7,5,3} – [learn the steps, numbers may differ].
7. Apply Merge sort on these elements – [learn the steps, numbers may differ]. Find its worst case and
Average case efficiency.
8. Write merge sort algorithm with example and also calculate the efficiency.
Module-3
1. Define Heap and give out any two properties of Heap. Construct bottom up heap for the list : – [learn
the steps, numbers may differ]
2. Construct top down heap for the list – [learn the steps, numbers may differ]. Obtain its time
complexity
3. Define AVL Trees. Obtain its four rotation types. Construct an AVL Tree for the list of elements –[learn
the steps, numbers may differ].
