Analysis and Designs of Algorithms- BCS401 Solved Important Questions
Module 1
1] Define algorithm. Explain the Fundamentals of Algorithmic Problem Solving (or) Explain the algorithm design and analysis process
2] Design an algorithm for performing sequential / linear search and compute best case, worst case, and average case efficiency.
3] What are the various basic efficiency classes? Explain Big O, Big Omega and Big Theta asymptotic notations.
4] Prove the following theorem if t1(n) ϵO((g1(n)) and t2(n) ϵ O(g2(n)) then t1(n)+ t2(n) ϵ O(max{g1(n),g2(n}).
5] Explain the general plan for analyzing the efficiency of recursive algorithm. Write the algorithm to find factorial of a given number. Derive its efficiency.
6] Write an algorithm to find the uniqueness of elements in an array and give the mathematical analysis of this non-recursive algorithm with all steps.
7] Write Tower of Hanoi algorithm and steps for analysis of recursive algorithm. Show the analysis of above algorithm.
8] Write an algorithm for Selection sort, trace its working for the given elements and also analyze its efficiency. 89 45 68 90 29 34 17
9] With the algorithm, derive the worst-case efficiency for Bubble Sort.
10] Explain Brute Force String matching problem with an example. Write an algorithm for same and analyze its efficiency.
Module 2
1] Explain Exhaustive Search with reference to the Traveling Salesman Problem and the Knapsack Problem.
2] Design an algorithm for performing insertion sort. Analyze its time efficiency; apply the same to sort the following number. 89 45 68 90 29 34 17
3] Define topological sorting. list the two approaches of topological sorting and illustrate with examples. Or Explain Topological Sorting. Give its definition, algorithm, and applications.
4] Design an algorithm for performing merge sort. Analyze its time efficiency; apply the same to sort the following number. 4 9 0 -1 6 8 9 2 3 12 or explain the concept of divide and conquer. Design an algorithm for merge sort and derive its time complexity another example… 8, 3, 2, 9, 7, 1, 5, 4
5] Design an algorithm for performing quick sort . Apply the same to solve the following set of numbers : 5 3 1 9 8 2 4 7 and write its best case
6] Sort the following keyword A,L,G,O,R,I,T,H,M by applying Quicksort method.
7] Apply quick sort algorithm to sort the list E,X,A,M,P,L,E in alphabetical order. Draw tree of recursive calls made
8] Explain binary tree traversals and related properties.
9] Explain Strassen’s matrix multiplication and derive its time complexity
Module 3
1] Define AVL Trees. Explain its four rotation types. Explain AVL tree with an example. Give worst case efficiency of operations on aviary construct an avail tree of the list of keys 5683247 indicating each step of key insertion and rotation
2] Define 2-3 tree. Give the worst-case efficiency of operations on 2-3 tree, build 2-3 tree for the list of keys 9, 5, 8, 3, 2, 4, 7by indicating each step of key insertion and node fits.
3] Explain Heap, Bottom-up Heap and Top-down heap with example.
4] Explain Heapsort with example
5] Design Horspools algorithm for string matching. Apply Horspools algorithm to find the pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP
Module 4
1] Using Dynamic Programming solve the below instance of knapsack problem. Capacity W=5
2] Apply Warshall’s algorithm to compute transitive closure for the graph below.
3] Define transitive closure of a graph. Write Warshall’s algorithm to compute transitive closure of a directed graph. Apply the same on the graph defined by the following adjacency matrix:
4] Design Floyd’s algorithm to find shortest distances from all nodes to all other nodes
5] Apply Floyd’s algorithm to find all pair shortest path for the given graph.
6] Obtain a minimum cost-spanning tree for the graph below using Prim’s algorithm
7] Apply prim’s algorithm and kruskal’s algorithm method to find the minimum cost spanning tree to graph shown below
8] Apply Prim’s algorithm and Kruskal’s algorithm to find the minimum cost-spanning tree in the graph below.
9] Find the minimum spanning tree using Kruskal’s algorithm
10] Calculate the shortest distance and shortest path from vertex 5 to vertex 0 using Dijkstra’s algorithm.
11] Explain Dijkstra’s Algorithm with example
12] Construct a Huffman code for the following data
Encode the text ABACABAD and decode 100010111001010.
13] Construct a Huffman code for the following data and encode the test BADEC
14] Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence frequencies in a text made up of these symbols:
Module 5
1] Explain the following with examples i) P problem ii) NP Problem iii) NP- Complete problem iv) NP – Hard Problems
2] Construct state space tree for solving four queens problem using backtracking. Or Illustrate N queen’s problem using backtracking to solve 4-Queens problem
3] Explain Subset sum problem with suitable example.
4] Apply backtracking technique to solve the below instance of the subset sum problem.
S={1,3,4,6} d=7
S={5, 10, 12, 13, 15, 18} d=30
5] How the branch and bound technique is different from backtracking? Solve the following instance of knapsack problem using Branch and Bound technique. Give knapsack capacity = 10.
6] Explain Greedy Approximation Algorithm for the Discrete Knapsack Problem
Note: If you 21 scheme Analysis and Designs of Algorithms Solved Important Questions, Click here.
