AOA Paper Analysis
Chapter 1: Introduction and Analysis
● Explain asymptotic notations. And explain Best Case, Average Case and Worst Case
● Explain Master's Theorem to find the complexity of a recurrence relation
● Definition of NP Class,P, NP, NP-Hard, NP-Complete., what is the relation between them?
● An algorithm takes 0.5ms for input size 100. How long will it take for an input size 500. If the
running me is following 1) Linear 2) Quadra c 3) Cubic 4) √n 5) nlog2n
● Write the algorithm for insertion sort. Also sort the following numbers using same algorithm
11,7,17,3,9,29,85,9 and show output after every pass.
● Write algorithm for insertion sort and sort the following elements using the same: 22, 15, 11,
16, 19. Show all the passes.
●
●
●
Chapter 2: Divide and Conquer Approach
● Write an algorithm to find minimum and maximum values using divide and conquer strategy
and also derive it;s time complexity
● Write algorithm for quick sort. Derive its time complexity. And sort the following elements
[40,11,4,72,17,2,49]
● Sort the following numbers using Merge Sort. Also derive the time complexity of Merge Sort.
70, 20, 30, 40, 10, 50, 60
● Write the algorithm and explain/derive the complexity of the binary search algorithm.
● Find Minimum and Maximum elements of an array X[0 : 9] = (45, 83, 75, 17, 43, 37, 80, 53,
61, 22) using divide and conquer strategy.Also how many comparisons have been made
● Difference between Divide and Conquer and Dynamic Programming Approach
Chapter 3: Greedy Method Approach
● Find an optimal solution to the knapsack instance n=5, m=60 profit={30, 20, 100, 90, 160}
weight={5, 10, 20, 30, 40}
● Consider the instance of knapsack problem where n=6, M=15, Pro ts are
(P1,P2,P3,P4,P5,P6)=(1,2,4,4,7,2) and weights are (W1,W2,W3,W4,W5,W6) =
(10,5,4,2,7,3). Using fractional knapsack
AOA Paper Analysis
● Dijkstra’s Prim’s And Kruskals
●
●
●
●
● Explain job sequencing with deadline with an example.
● Explain the difference between greedy knap sack and 0/1 knapsack
● What is greedy algorithm? Write an algorithm for general greedy method.
● Write Kruskal’s/Prims algorithm for finding a minimum spanning tree. Explain its working with
an example. Also derive the time complexity for the same.
●
● Write algorithm for greedy knapsack and derive its time complexity
AOA Paper Analysis
Chapter 4: Dynamic Programming Approach
● Find Longest Common Subsequence for the following string X=xyzytxy and Y=ytzxyx
● Find Longest Common Subsequence for the following string X=acbaed and Y=abcabe
Explain in brief the concept of Multistage graphs also write the algorithm
● What is LCS? Explain with example.
● Write algorithm for 0/1 knapsack using dynamic programming and obtain the solution to
following 0/1 knapsack problem where: n = 4, Knapsack Capacity M= 5, Weights (W1, W2,
W3, W4) = (2, 3, 4,5) and profits (P1, P2, P3, P4) = (3, 4, 5, 6).
Explain Single source shortest path algorithm using Dynamic programming with suitable
example.
Explain Dijkstra's Single source shortest path algorithm. Explain how it is different from
Bellman Ford algorithm.
Multistage graph problems
Solve the following multistage graph problem
AOA Paper Analysis
Use Bellman Ford Algorithm to find shortest path
Chapter 5: Backtracking and Branch and Bound
● Explain the Concept of backtracking using N-Queen Problem
● Give the algorithm for the N-Queens problem and give any two solutions to the 8-Queens
problem(basically example)
AOA Paper Analysis
● Explain the N queen Problem for N=4
● Give the algorithm to solve the N-Queen Problem using backtracking. Give any 2 solutions
for the 4-Queen Problem.
● Write and explain sum of subset algorithm for n=4, m= 17, w = {2,7,8,15}. Show the entire
state space tree and find all the solutions
● Explain with an example how the Travelling Salesman Problem can be solved using Branch
and Bound method.
● What is Backtracking
● Explain 15-puzzle problem using branch and bound strategy./ LC search technique.
●
● Explain optimal storage on tape
● Write an Algorithm for Graph Coloring problem.
Travelling Salesperson Problem
Chapter 6: String Matching Algorithms
Explain Naive String matching algorithm with example
Rewrite and Compare Rabin Karp and Knuth Morris Pratt Algorithms Give the pseudo code
for the KMP String Matching Algorithm.
Give the pseudo code for the KMP String Matching Algorithm. Use KMP algorithm to find
pattern=”ababada” in text=”badbabababadaab”. Show the prefix table and the valid shifts.
AOA Paper Analysis
Explain and apply Naïve string matching on following strings
S1: COMPANION
S2: PANI
]Show the steps and find number of shifts to find the Pattern "aabc" in the Text String
"abaaabccb" using Naïve String Matching Method.
What is Knutt Morris Pratt Algorithm?,give pseudo code.and explain with an example
Give the Rabin-Karp Algorithm for string matching. Explain its working with a suitable
example. List a few areas where String Matching Algorithms can be applied.
Explain different string matching algorithms.
