Assignment 1
1. What is an algorithm? Explain characteristics of any algorithm.
2. Explain why analysis of algorithms is important? Explain: Worst Case, Best
Case & Average Case Complexity.
3. (a) Answer the following
(i) What is relation? Explain equivalence relation.
(ii) Explain linear inequality and equations.
4. Define:
(1) Algorithm (2) Average case (3) Time complexity
(4) Space complexity (5) Set (6) Function (7) Relation
Assignment 2
1. Explain asymptotic analysis of algorithm.
2. (ii) Let f(n) and g(n) be asymptotically positive functions. Prove or
disprove following.
f(n) + g(n) = Θ(min(f(n), g(n)))
b b
3. (i) Prove that (n + a) = Ө( n ) , b>0
(ii) Find big oh(Ο) notation for following:
(1) f(n) = 6993 (2) f(n) = 6n2 + 135
4. (i) Find big theta(Ө) and big omega(Ω) notation.
(1) f(n) = 14 * 7 + 83. (2) f(n) = 83n3 + 84n
n+1 n
(ii) Is 2 = Ο(2 ) ? Explain.
5. Explain why analysis of algorithms is important? Arrange the following
growth rate in increasing order:
3 2 2
n , 1, n , nlog(n), n log(n), log(n), n
6. Arrange following rate of growth in increasing order.
N 2 3
2 , n log n, n , 1 , n, log n, n!, n
7. Compare Iterative and Recursive algorithm to find out Fibonacci series.
Explain why analysis of algorithms is important? Explain: Worst Case, Best Case
& Average Case Complexity.
8. What is Recursion? Give Recursive algorithm for Tower of Hanoi Problem and
give analysis of it.
9. Write a program/algorithm of Selection Sort Method. What is Complexity of the
method?
10. Give the properties of Heap Tree. Sort the following data with Heap Sort
Method: 65, 75, 5, 55, 25, 30, 90, 45, 80.
11. Sort the letters of word “EDUCATION” in alphabetical order using insertion sort.
12. Sort the following elements in ascending order using bucket sort. Show all
passes121,235,55,971,321,176
13. Sort the following elements using counting sort method :6 0 2 0 1 3 3 6 1 3 2
Assignment 3
1. What is Divide and Conquer Technique? Give the use of it for Binary
Searching Method. Also give its Time Complexity.
2. Write a program/algorithm of Quick Sort Method and analyze it.
3. Write an algorithm for merge sort with divide and conquer strategy.
Analyze each case
4. Explain the use of Divide and Conquer Technique for Binary Search Method.
What is the complexity of Binary Search Method?
ADA-ASSIGNMENT -4
1 Explain Backtracking Method. What is N-Queens Problem? Give
solution of 4 Queens Problem using Backtracking Method
2 What is the basic idea behind Rabin – Karp algorithm? What is expected
running time of this algorithm ? Explain it with example. 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 = 31415?
3 Write a brief note on NP-completeness and the classes-P, NP and NPC.
4 Find an optimal solution to the knapsack instance n=4, M=8,
(P1,P2,P3,P4)=(3,5,6,10) and (W1,W2,W3,W4)=(2,3,4,5) using
backtracking. Also draw the corresponding state space tree.
5 What is finite automata? Explain with example how finite automaton is
used for string matching?
6 Explain use of Branch & Bound Technique for solving Assignment
Problem.
7 Explain with example how backtracking algorithm useful in solving
Hamiltonian cycle problem.
8 Explain in brief : P problrm, NP problem ,travelling sales man problem
9 Solve the following knapsack problem using back tracking. Capacity of
knapsack is 11.
10 How branch and bound is different from backtracking ?
ADA-ASSIGNMENT -5
1. Write the Prim’s Algorithm to find out Minimum Spanning Tree. Apply the same and find
MST for the graph given below.
2. Write Huffman code algorithm and Generate Huffman code for following.
Letters A B C D E
Frequency 24 12 10 8 8
3. Using greedy algorithm find an optimal schedule for following jobs with n=6.
Profits: (P1,P2,P3,P4,P5,P6) = (20, 15, 10, 7, 5, 3)
Deadline: (d1,d2,d3,d4,d5,d6) =(3, 1, 1, 3, 1, 3)
4. Explain Depth First Traversal Method for Graph with algorithm with example
5. Explain Breath First Traversal Method for Graph with algorithm with example
6. Define MST. Explain Kruskal’s algorithm with example for construction of MST.
7. Explain in brief characteristics of greedy algorithms.
8. Mention applications of minimum spanning tree. Generate minimum spanning tree from
the following graph using Prim’s algorithm. (Start at vertex a)
9. 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.
Jobs J1 J2 J3 J4 J5 J6 J7
Start Time 0 3 4 9 7 1 6
Finish Time 2 7 7 11 10 5 8
Show schedule of these jobs on minimum number of processors using greedy approach.
Derive an algorithm for the same. What is the time complexity of this algorithm?
10. 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)
11. Differentiate BFS and DFS.
12. Solve the following Knapsack Problem using Greedy Approach Method.
Write the equation for solving above problem.
n = 5, W = 100
Object 1 2 3 4 5
Weight (w) 10 20 30 40 50
Value (v) 20 30 66 40 60
13. Solve the following 0/1 Knapsack Problem using Greedy Approach Method.
Write the equation for solving the problem.
n = 5, W = 11
Object 1 2 3 4 5
Weight (w) 1 2 5 6 7
Value (v) 1 6 18 22 28
14. Find Minimum Spanning Tree for the given graph using Kruskal’s Algo.
ASSIGNMENT: 6
1 Explain in brief characteristics of greedy algorithms. Compare Greedy Method with
Dynamic Programming Method.
2 Differentiate the following: 1. Divide and conquer & Dynamic Programming
2. Greedy Algorithm & Dynamic Programming
3 Explain how to apply the divide and conquer strategy for sorting the elements using
merge sort
4 Write an algorithm for quick sort with divide and conquer strategy. Analyze each
case.
5 Explain the use of Divide and Conquer Technique for Binary Search Method. Give
the algorithm for Binary Search Method. What is the complexity of Binary Search
Method?
6 Explain how multiplication of large integers can be done efficiently by using divide
and conquer technique?
7 Using algorithm find an optimal parenthsization of a matrix chain product whose
sequence of dimension is ﴾5,10,3,12,5,50,6﴿ (use dynamic programming).
8 Explain how divide and conquer method help multiplying two large integers.
9 Explain chained matrix multiplication with an example.
10 Solve making change problem for d1=1, d2=4, d3=6, n=3, and N=8 unites.
