UNIT-01

Q1) Explain different asymptotic notations.

Q2) Define algorithm.What is the need of algorithm analysis ? Which factors affect the runtime of an
algorithm ?

Q3) Define Algorithm? State the main characteristics of Algorithm

Q4) Describe Asymptotic notations with expression

Q5) Evaluate 9T(n/3) + n

n
Q6) Write down properties of algorithms

lo
Q7) Explain any three asymptotic notations.

si
Q8) What is the max heap? Explain with examples.

Q9) What is Algorithm? Explain criteria of Algorithms. Remember

Ep
Q10) What are Asymptotic Notations? Explain any three Asymptotic Notations

Q11) Define Max and Min Heap and write an algorithm to insert into a heap.
By
A
A
D
UNIT-02
Q1)

Q2) Write an algorithm for merge sort.Apply merge sort on following array
A=51263794

Q3) Write an algorithm of merge sort and illustrate the operation on an array using Merge Sort.
A = {5 2 4 7 1 3 2 6}

n
Q4)Multiply following two matrices using Strassen’s matrix multiplication algorithm.

lo
A=(12
34)
B = (5 6

si
78) Ep
Q5) Describe an algorithm for Merge Sort and find its time complexity

Q6) Evaluate and write the algorithm for Quick sort describe its best and worst case with suitable example

Q7) Solve using Strassen's Matrix Multiplication, and Calculate its time complexity
A = (6 7
By

54)
B = (1 2
34)

*Q8) Explain Binary Search with its time complexity

A

*Q9) Write down a quick sort algorithm with its time complexity.

*Q10) Explain strassen’s matrix multiplication with its performance analysis.

A
D
UNIT-03
*Q1) Write Huffman Coding algorithm . Obtain Huffman tree for following data.

CHARACTER A B C D E

FREQUENCY 6 11 19 35 50

Q2) What are the different elements of greedy strategy ? Explain the steps to solve the problem by greedy
strategy.

Q3) What is Greedy method? Explain elements of Greedy method.

*Q4) Construct an optimal instance of Huffman Code for the following set of frequencies using the Greedy

n
method.

lo
CHARACTE A B C D E F
R

FREQUEN 45 13 12 16 9 5

si
CY

Q5) Draw a state space tree for finding four queens solutions
Ep
Q6) Apply branch and bound technique to solve travelling salesman problem for the graph whose matrix is
By

*Q7) Describe Graph Colouring Problem with suitable example

Q8) Explain four queen problems and draw its state space tree.
A

Q9) What is graph colouring problem? Explain with examples.

Q10) Differentiate between backtracking and branch and bound.

A

Q11) Draw a state space tree for finding Four Queens problems solution.
D

Q12) Explain Branch and Bound with suitable example.

UNIT-04
Q1) Compute Longest Common Subsequence using Dynamic Programming approach for sequences X and Y if X
=A, B, C, B, D, A, B and Y = B, D, C, A, B, A . What is the length of LCS.

Q2) Compare Greedy Strategy , Dynamic Programming and Divide and Conquer approach.

Q3) Determine longest common subsequence using dynamic programming approach for X and Y. What is the
length of the longest common subsequence?
X = < A, B, C, B, D, A, B >
Y = < B, D, C, A, B, A >

n
Q4) Find the shortest path using Bellman Ford algorithm for the following graph.
Note that vertex z is the source vertex.

lo
si
Ep
Q5)A) Solve the Fractional Knapsack problem Given n = 5 objects and a knapsack capacity
W = 60 profit (30, 20, 100,90,160) Weight = (5,10,20,30,40)

Q6) Solve knapsack problem by greedy method where capacity of knapsack is 15kg, profits of seven object are
(P1,P2,P3,P4,P5,P6,P7) (10,5,15,7,6,18,3) and weights (w1,w2,w3,w4,w5,w6,w7)(2,3,5,7,1,4,1).
By

Q7) Solve an optimal Huffman code for the following set of frequencies
a: 50 b: 25 c: 15 d: 40 e=75

Q8) Solve Job sequencing with deadlines n=4,

p=(100,10,15,27) and d =(2,1,2,1) find optimal solution
A

Q9) What is optimal merge pattern?

A

Q10) Explain Huffman coding with a suitable example.

Q11) Find an optimal solution to the knapsack instance n = 7, m = 15, (P1 ,P2, P3 ,P4 P5 ,P6 P7 ) =
D

(10,5,15,7,6,18,3), and (w1, w2, w3, w4, w5, w6, w7) = (2,3,5,7,1,4,1).
Q12) What is the Minimum Cost Spanning Tree? Explain with suitable example.

Q13) Explain Job Sequencing with Deadlines.

UNIT-05
*Q1) What is state space tree ?Using state space tree show that there exist an solution to 4-Queens problem

Q2) Given n=6 weights, w={5,10,12,13,15,18} and M=30 .Find all possible subsets for which sum=M using sum of
subsets algorithm.

Q3) What is P class and NP class? Show relationship between them.

*Q4) Explain Class P, Class NP and Class NPC problems in detail.

Q5) Calculate the shortest path by using Floyd's Warshall Algorithm

n
lo
Q6) Calculate the longest common subsequence for
X={ A,B,C,B,D,A,B}

si
Y={B,D,C,A,B,A} Ep
*Q7) Differentiate between Dynamic Programming and greedy Approach

Q8) Write down characteristics of dynamic programming.

Q9) Explain different applications of dynamic programming.

By

Q10) What is complexity class P?

Q11) Analyze Floyd Warshals algorithm for Dynamic Programming.

A
A
D