The oxford College of Engineering
ADA Question Bank - All 5 modules
[Link] Sri,Ap/CSE
Find the time efficiency for computing product of n x n matrices with an CO1
11
algorithm
Develop an algorithm to determine the minimum and maximum values in an CO1
12
array of integers. Determine the worst case complexity
Write down the Selection sort and Bubble sort algorithm with example and find CO1
13
its time complexity for both.
CO1
14 Write the Sequential search algorithm with example and analyse its efficiency.
Describe brute-force approach. What are the advantages and disadvantages of CO1
15
this approach?
Design a brute-force algorithm for string matching with example and find its CO1
16
time complexity for the same.
MODULE 2
Give the general divide and conquer recurrence and explain the same. CO2
1
Explain the Exhaustive Search method using Travelling Salesman problem with CO2
2 the example.
Describe how the Knapsack Problem work using Exhaustive Search method with CO2
3 the example.
.
Write the Insertion sort algorithm and sort the list 89,45,68,90,29,34,17 using CO2
4 insertion sort algorithm and discuss the time efficiency.
What is topological sorting? Explain the Source Removal algorithm for CO2
topological Sort. Obtain topological sorting for the given diagraph using source
removal method
Inscribe the algorithm for DFS and explain how it canbe used to solve the CO2
6
topological sorting problem with one example
Write down the algorithm for BFS and explain how it canbe used to solve the CO2
7
topological sorting problem with one example
8 Construct an algorithm for merge sort. Analyze its efficiency. CO2
Write the merge sort algorithm and Sort the list E, X, A, M, P, L, E in CO2
9 alphabetical order using merge sort and discuss the efficiency of merge sort.
10 Trace the merge sort algorithm for the data set 8, 4, 1, 6, 7, 2, 3, 9. CO2
11 Construct an algorithm for Quick sort. Analyze its efficiency. CO2
Discuss how quick sort works to sort an array. Trace quick sort algorithm for the CO2
12
following data set 65, 70, 75, 80, 85, 60, 55, 50, 45
Consider the numbers given below. Show how partitioning algorithm of quick CO2
13
sort will place 106 in its correct position. Show all the steps clearly. “106 117
Downloaded by Ramya Sri (rmsri45@[Link])
128 134 141 91 84 63 42”
14 Explicate the Binary tree Traversals with an example CO2
15 Explain Strassen’s matrix multiplication and derive its time complexity CO2
MODULE 3
1 Define Binary Tree. What is the important for Balanced Binary search tree CO3
explain its Types
2 Define AVL trees explain its Rotations with example CO3
3 Construct AVL trees for the list 5,6,8,3,2,4,7 by successive insertion along with CO3
its time complexity.
4 Define heap. Explain the properties of heap along with its representation. CO3
Construct bottom up heap for the list 2,9,7,6,5,8. Obtain its time complexity
5 Write the algorithm of Heap sort. Along with the bottom approach for CO3
constructing the heap. Find its Time complexity.
6 Algorithm for Comparison Counting sort and sort the list 62,31,84,96,19,47 using CO3
the same.
7 Algorithm for Distribution Counting sort and sort the list 13,11,12,13,12,12 using CO3
the same.
8 Explain Horspool’s algorithm cases with example. CO3
9 Design Horspools algorithm for string matching. Apply Horspools algorithm to CO3
find the pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP.
10 Write Horspool’s algorithm and find the pattern SORTING in the text CO3
BRUTE_FORCE_METHOD_USED_FOR_SORTING_ALGORITHM
MODULE 4
1 Using dynamic programming, solve the following instance of knapsack problem, CO3
for M=20
2 Solve the knapsack instance n=3, (w1,w2,w3)=(1,2,2) and (p1,p2,p3)=(18,16,6) CO3
and M=4 by dynamic programming
3 Define Transitive closure. Write Warshall‟s algorithm to compute transitive CO3
closure. Find its efficiency.
4 Apply Warshall’s Algorithm to find transitive closure of graph defined by the CO3
following adjacency matrix.
5 Define transitive closure of a graph. Apply Warshalls algorithm to compute CO3
transitive closure of a directed graph.
Downloaded by Ramya Sri (rmsri45@[Link])
6 Using Warshall‟s algorithm to find transitive closure of a digraph. CO3
7 Explain all Pair Shortest Path Floyd’s Algorithm with its time complexity. CO3
8 Relate Floyd‟s algorithm to compute all pairs shortest paths for the following CO3
graph.
9 Elaborate the concept of greedy technique for prim’s algorithm. Obtain the CO4
minimum cost spanning tree for the graph below using the same.
Find the minimum spanning tree using Prim’s algorithm for the given graph CO4
along with the Algorithm.
10
Construct minimum cost spanning tree using Kruskals algorithm for the CO4
11
following graph
Downloaded by Ramya Sri (rmsri45@[Link])
Develop the minimum cost spanning tree for the below graph using kruskal’s CO4
algorithm along with the
12
13 Explain the Kruskals algorithm . Find its efficiency. CO4
Apply Dijkstra’s algorithm to find single source shortest path for the given graph CO4
by considering S as the source vertex.
14
Solve the below instance of the single source shortest path with vertex a as the CO4
source with the help of Dijikstra’s algorithm
15
16 Explain the Dijikstra’s algorithm. Find its efficiency. CO4
Construct the Huffman tree for the following data. CO4
17
Encode DAD-CBE using Huffman Encoding.
What is Huffman tree? Construct a Huffman tree and resulting code word for the CO4
following and Encode the words DAD and ADD
18
Downloaded by Ramya Sri (rmsri45@[Link])
MODULE 5
Explain the following with examples
1 CO5
i) P problem ii) NP Problem iii) NP- Complete problem iv) NP – Hard Problems
What is backtracking? Apply backtracking to solve the below instance of sum of CO6
2
subset problem S={5,10,12,13,15,18} d=30
3 Illustrate N queen’s problem using backtracking to solve 4-Queens problem CO6
Using Branch and Bound technique solve the below instance of knapsack CO6
problem. Capacity 5
5 Discuss the concept of Classes of NP- Hard and NP-Compete CO5
Course Outcomes: Students will be able to
Apply asymptotic notational method to analyze the performance of the algorithms in terms of
CO1 time complexity.
CO2 Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
Computational problems.
CO3 Make use of transform & conquer and dynamic programming design approaches to solve the
given real world or complex computational problems.
CO4 Apply greedy and input enhancement methods to solve graph & string based computational
Problems.
CO5
Analyse various classes (P,NP and NP Complete) of problems
CO6 Illustrate backtracking, branch & bound and approximation methods.
Downloaded by Ramya Sri (rmsri45@[Link])