NUMERICALS

UNIT-2 : ANALYSIS OF ALGORITHM

1. Find out big-oh notation of the f(n)= 3n2+5n+10
2. Sort the following numbers using heap sort. 20, 10, 50, 40, 30
3. State whether the statements are correct or incorrect with reasons. 1. O(f(n)) + O(f(n)) = O (2f(n)) 2.
If 3n + 5 = O(n2 ) , then 3n + 5 = o(n2 )
4. Arrange the growth rate of 2 n , n2 , 1, log n, n log n, 3 n and n in increasing order of growth.
5. Find out the Ө-notation for the function: f(n)=27n2+16n.
6. Find Omega (Ω) notation of function f(n) = 2n^2 + n log n + 6n

7. Solve the following recurrence using Master Theorem: T(n) = 3T(n/3) + n^3

8. Solve the following using Master’s theorem:

a. T(n) = 2T(n/4) + 1
b. T(n)=3T(n/4) + n log n

9. What is asymptotic notation? Find out big-oh notation of the f(n) = 3n^2+5n+10

10. Write selection sort algorithm and compute running time of algorithm

11. Properties of Heap Tree. Sort data using Heap Sort: 20, 50, 30, 75, 90, 60, 80, 25, 10, 40

12. Apply counting sort for the following numbers to sort in ascending order. 3, 1, 2, 3, 3, 1

UNIT-3 : DIVIDE AND CONQUER ALGORITHM

1. Solve following recurrence relation using iterative method T(n)=2T(n / 2) + n.
2. Trace the quick sort for data A = {6,5,3,11,10,4,7,9}
3. Explain master theorem and solve the recurrence T(n)=9T(n/3)+n with master method.
4. Trace the merge sort for data A = {6,5,3,11,10,4,7,9}.
5. Apply merge sort algorithm on array A = {2,7,3,5,1,9,4,8}. What is time complexity of merge sort in
worst case?
6. Perform the analysis of a recurrence relation T(n)= 2𝑇 ( 𝑛 2 ) + 𝜃(𝑛 2 ) by drawing its recurrence tree
7. Consider the array 2,4,6,7,8,9,10,12,14,15,17,19,20. Show (without actually sorting), how the quick
sort performance will be affected with such input.
8. Sort the following list using quick sort algorithm:< 5, 3 ,8 ,1 ,4 ,6 ,2 ,7 > Also write Worst and Best
case and Average case of quick sort algorithm.
9. Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,10,13,14,60>.
10. Solve following recurrence using master theorem. (i)T(n)= T(n/2) + 1 (ii) T(n)=2T(n/2) + n logn
11. Solve following recurrence relation using iterative method T(n) = T(n - 1) + 1 with T(0) = 0 as initial
condition. Also find big oh notation.
12. Use Iteration method to solve recurrence T(n) = T(n-1) + 1 , here T(1)= Ө(1).

13. Illustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 50, 52, 60.
Comment on the nature of input i.e., best case, average case or worst case. Also, discuss worst and
best case of quick sort algorithm
 14. Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,9,10,12,14,18>

15. Solve the following Task Assignment problem for minimization using following cost matrix. (Cost
matrix represents cost of Task T performed by Person P).

16. Sort the List “G,U,J,A,R,A,T,S,A,R,K,A,R” in alphabetical order using merge sort.

17. Demonstrate Binary Search method to search Key = 14, form the array A = <2,4,7,8,10,13,14,60>.

UNIT-4 : DYNAMIC PROGRAMMING

1. Find out minimum number of multiplications required for multiplying: A[1 × 5], B[5 × 4],
C[4× 3], D[3 × 2], and E[2 × 1].
2. Solve following knapsack problem using dynamic programming algorithm with given capacity W=5,
Weight and Value are as follows : (2,12),(1,10),(3,20),(2,15).
3. Solve the following 0/1 Knapsack Problem using Dynamic Programming. There are five items whose
weights and values are given in following arrays. Weight w [] = {1,2,5,6,7} Value v [] = {1, 6, 18, 22,
28} Show your equation and find out the optimal knapsack items for weight capacity of 11 units.
4. Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B =
“bacac”.
5. Apply LCS on sequence <A,B,A,C,B,C> for pattern <A,B,C>.
6. Given is the S-table after running Chain Matrix Multiplication algorithm. Calculate the parenthesized
output based on PRINT_OPTIMAL_PARENTHESIS algorithm. Assume the matrix are names from A1,

A2, ….,An.
7. Consider a Knapsack with maximum weight capacity M is 7, for the three objects with value <3,4,5>
with weights <2,3,4> solve using dynamic programming the maximum value the knapsack can have.
8. Find out LCS (Longest Common Subsequence) of A={K,A,N,D,L,A,P} and B = {A,N,D,L}.
9. Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B =
“bacac”
10. Consider a Knapsack with the maximum weight capacity M is 7, for the objects with value
[12,10,20,15] with weights [2,1,3,2] solve using dynamic programming the maximum value the
knapsack can have
11. Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,9,10,12,14,18>
 12. Find out the NCR (5, 3) Using Dynamic Method
13. Using algorithm find an optimal parenthesization of a matrix chain product whose sequence of
dimension is (5,10,3,12,5,50,6) (use dynamic programming).
14. Solve following knapsack problem using dynamic programming algorithm with given capacity
W=5, Weight and Value are as follows (2,12),(1,10),(3,20),(2,15)
15. Given coins of denominations 2, 3 and 4 with amount to be pay is 5. Find optimal no. of coins and
sequence of coins used to pay given amount using dynamic method.
16. Find all pair of shortest path using Floyd’s Algorithm for following graph.

1.

UNIT-5 : GREEDY ALGORITHM

2. Find minimum spanning tree for the given graph in fig-1 using prim’s algorithm.

3. Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15, 12, 8) find the maximum profit
using greedy method.
4. Find the Huffman code for each symbol in following text
ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE
5. Find an optimal Huffman code for the following set of frequency. A : 50, b: 20, c: 15, d: 30
6. Find Minimum Spanning Tree for the given graph using Kruskal Algo. and Prim’s algorithm.
7. Apply Kruskal’s algorithm on the given graph and step by step generate the MST.

8. Apply Prim’s algorithm on the given graph in FIG:1 Graph G(V,E) and step by step generate the MST.
9. Using greedy algorithm find an optimal schedule for following jobs with n=7 profits: (P1, P2, P3, P4,
P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline (d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)
Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15, 12, 8) find the maximum profit
using greedy method.
10. Using a greedy algorithm, find an optimal schedule for jobs with n=7: profits (3, 5, 18, 20, 6, 1, 38)
and deadline (1, 3, 3, 4, 1, 2, 1)

11. Solve the following Knapsack Problem using the greedy method. Number of items = 5, knapsack
capacity W = 100, weight vector = {50, 40, 30, 20, 10} and profit vector = {1, 2, 3, 4, 5}

12. What is a minimum spanning tree? Draw the minimum spanning tree correspond to following
graph using Prim’s algorithm.

13. Using greedy algorithm find an optimal schedule for following jobs with n=7 profits: (P1, P2, P3,
P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline (d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)

14. Following are the details of various jobs to be scheduled on multiple processors such that no two
processes execute at the same on the same processor. Show schedule of these jobs on minimum
number of processors using greedy approach.
 15. Write the Kruskal’s Algorithm to find out Minimum Spanning Tree. Apply the same and find MST
for the graph given below. (Asked Again)

(Repeated in winter 2023)

UNIT-6 : EXPLORING GRAPHS

1. Apply the algorithm to find strongly connected components from the given graph.

2. Given is the DAG, apply the algorithm to perform topological sort and show the sorted graph
 3. Write an algorithm to find out the articulation points of an undirected graph. Find out articulation
points for the following graph. Consider vertex 0 as the starting point.

4. Traverse the following graph using Breadth First Search Technique. Also draw BFS Tree for a given
graph.

UNIT-8 : STRING MATCHING

1. Show the comparisons that naïve string matcher makes for the pattern p=0001 in the text
T=000010001010001
2. Explain spurious hits in Rabin-Karp string matching algorithm with example. Working modulo q=13,
how many spurious hits does the RabinKarp matcher encounter in the text T =
2359023141526739921 when looking for the pattern P = 31415?
3. Create an example of string P of length 7 such that, the prefix function of KMP string matcher
returns π[5] = 3, π[3] = 1 and π[1] = 0.
4. Show that if all the characters of pattern P of size m are different, the naïve string matching
algorithm can perform better with modification. Write the modified algorithm that performs better
than O(n.m).

5. Explain spurious hits in Rabin-Karp string matching algorithm with example. Working modulo
q=13, how many spurious hits does the Rabin-Karp matcher encounter in the text T =
2359023141526739921 when looking for the pattern P = 26739?

UNIT -9 : Introduction to NP-Completeness

1. Show that if all the characters of pattern P of size m are different, the naïve string matching
algorithm can perform better with modification. Write the modified algorithm that performs better
than O(n.m).