ADA (3150703) IMP

Unit 1: Basics of Algorithms and Mathematics

1. Define Algorithm. Discuss key characteristics of algorithm.

2. Define term Quantifier.

3. What is vector? Which operations are performed on vector?

4. List types of algorithms.

Unit – 2: Analysis of Algorithm

1. Which are the basic steps of counting sort? Write counting sort

algorithm. Derive its time complexity in worst case.

2. Discuss best case, average case and worst case time complexity of

quick sort.

3. What is the average case time complexity of bubble sort?

4. Time complexity of _________ is in linear time.

(a) Bubble sort

(b) Radix sort

(c) Shell sort

(d) Selection sort

5. Which of the following case does not exist in complexity theory of an

algorithm?

(a) Average case (b) Worst case (c) Best case (d) Null case

6. Discuss insertion sort with its time complexity. Support your answer

with suitable example.

7. Sort the given numbers using heap sort.: 20, 10, 50, 40, 30

8. Find out time complexity for the following pseudo code using O-

notation.

for(i = 0; i < n; i++)

{

for(j = n ; j > 0 ; j--)

{

if( i < j )

c = c + 1;

}

}

9. Apply counting sort for the following numbers to sort in ascending

order: 4,1,3,1,3

10. Why do we use asymptotic notations in the study of algorithms?

Briefly describe the commonly used asymptotic notations.

11. What is an amortized analysis? Explain aggregate method of

amortized analysis using suitable example.

12. Explain Selection Sort Algorithm and give its best case, worst case and

average case complexity with example.

13. Sort the letters of word “EDUCATION” in alphabetical order using

insertion sort.

14. Define following terms: Big ‘Oh’ Notation, Big ‘Omega’ Notation and

‘Theta’ Notation.

15. Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60,

25, 10, 40.

16. What is worst case time complexity?

17. Define space complexity.

18. Write down the Best case, Worst Case and Average Case Complexity

for merge sort.

19. Write down the Best case, Worst Case and Average Case Complexity

for heap sort.

20. Apply the bubble sort algorithm for sorting: {U,N,I,V,E,R,S}

Unit – 3: Divide and Conquer Algorithm

1. Prove or disprove that f(n) = 1 + 2 + 3 + .... + n ∈ Θ(n^2).

2. Solve following recurrence using recursion tree method:

T(n) = 3T(n/3) + n^3.

3. Write standard(conventional) algorithm and Strassen's algorithm for

matrix multiplication problem. What is the recurrence for Strassen’s

algorithm? Solve it using master method to derive time complexity of

Strassen's algorithm.

4. Give any two sorting methods which are based on divide and conquer

strategy.

5. Check the correctness for the following equality. 5n3 + 2n = O(n3)

6. Briefly explain multiplying large integer problem with suitable

example.

7. Explain binary search with the suitable example.

8. Enlist various method(s) to solve recurrence equation and explain any

one in brief.

9. Explain the use of Divide and Conquer Technique for Binary Search

Method. What is the complexity of Binary Search Method? Explain it

with example.

10. Write a program/algorithm of Quick Sort Method and analyse it with

example.

11. Discuss matrix multiplication problem using divide and conquer

technique.

12. What is recurrence? Solve recurrence equation T (n) =T (n-1) + n

using forward substitution and backward substitution method.

13. Write an algorithm for quick sort and derive best case, worst case

using divide and conquer technique also trace given data

(3,1,4,5,9,2,6,5)

14. Define Feasible Solution.

15. Solve following recurrence using master method

T(n) = 9T(n/3) +n

16. Solve following recurrence using master method

T(n) = T(2n/3) + 1

17. Multiply 981 by 1234 by divide and conquer method.

Unit – 4: Dynamic Programming

1. What are the advantages of dynamic programming method over

divide-&-conquer method?

2. Justify with example that shortest path problem satisfies the principle

of optimality.

3. Which are the three basic steps of the development of the dynamic

programming algorithm? Mention any two examples of dynamic

programming that we are using in real life.

4. Solve the following making change problem using dynamic

programming method: Amount = Rs. 7 and Denominations: (Rs. 1, Rs.

2 and Rs. 4)

5. Justify with example that longest path problem does not satisfy the

principle of optimality.

6. State true or false: “Dynamic Programming always leads to an optimal

solution.”

7. Write the objective of making change problem.

8. What is meant by an optimal solution for a given problem?

9. Elaborate Longest Common Subsequence problem with the help of

dynamic programming. Support your answer with proper illustration.

10.Discuss knapsack problem using dynamic programming. Solve the

following knapsack problem using dynamic programming. There are

three objects, whose weights w (w1, w2, w3) ={1, 2, 3} and values

v(v1,v2,v3)={2, 3, 4} are given. The knapsack capacity M is 3 units.

11.Briefly discuss principle of optimality in dynamic programming.

12.State differences between dynamic programming and divide and

conquer strategy.

13.Discuss Assembly Line Scheduling problem using dynamic

programming with example.

14.Explain Chained Matrix Multiplication with example

15.Write equation for Chained matrix multiplication using Dynamic

programming. Find out optimal sequence for multiplication: A1 [5 ×

4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal

parenthesization of matrices.

16.Explain how to find out Longest Common Subsequence of two strings

using Dynamic Programming method. Find any one Longest Common

Subsequence of given two strings using Dynamic Programming.

X=abbacdcba

Y=bcdbbcaac

17.Solve Making Change problem using Dynamic Programming.

(Denominations: d1=1, d2=4, d3=6). Give your answer for making

change of Rs. 9.

18.Solve Making change problem using dynamic technique. D1 = 1, d2=3,

d3=5, d4=6. Calculate for making change of Rs. 8.

19.Given two sequence of characters, X={G,U,J,A,R,A,T}, Y = {J,R,A,T}

obtain the longest common subsequence.

20.For the following chain of matrices find the order of parenthesization

for the optimal chain multiplication (15,5,10,20,25)

Unit – 5: Greedy Algorithm

1. Discuss general characteristics of greedy method. Mention any two

examples of greedy method that we are using in real life.

2. What are the disadvantages of greedy method over dynamic

programming method?

3. Solve the following Knapsack Problem using 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}.

4. Write an algorithm for Huffman code.

5. Find minimum spanning tree for the following undirected weighted

graph using Kruskal’s algorithm.

6. What is the basic nature of greedy strategy?

7. State true or false: “Prim’s algorithm is based on greedy strategy.”

8. Discuss Kruskal’s algorithm for finding minimum spanning tree. Give

proper example.

9. Explain job scheduling problem using greedy algorithm. Support your

answer by taking proper illustration.

10. Define MST. Explain Kruskal’s algorithm with example for

construction of MST.

11. Compare Greedy Method with Dynamic Programming Method.

12. Write the Prim’s Algorithm to find out Minimum Spanning Tree.

Apply the same and find MST for the graph given below.

13. Write Huffman code algorithm and Generate Huffman code for

following

Letters: A B C D E

Frequency: 24 12 10 8 8

14. 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)

15. Explain the difference between Greedy and Dynamic Algorithm.

16. Compute MST using PRIM’s Algorithm of following:

17. Find an optimal Huffman code for the following set of frequency. a : 50,

b: 20, c: 15, d: 30.

18. Consider Kanpsack capacity W=50, w=(10,20,40) and v=(60,80,100)

find the maximum profit using greedy approach.

19. Explain Dijkstra algorithm to find the shortest path.

20. Define Minimum Spanning Tree

Unit – 6: Exploring Graphs

1. Solve all pair shortest path problem for the following graph using

Floyd's algorithm.

2. What is DFS? Explain with example. Show the ordering of vertices

produced by Topological-sort for the following graph.

3. Explain breadth first search with algorithm & example.

4. Define the term: Directed Graph

5. Write brief note on topological sort.

6. Explain Depth First Traversal Method for Graph with algorithm.

7. Define Directed Acyclic Graph

8. Explain: Articulation Point, Graph, Tree

Unit – 7: Backtracking and Branch and Bound

1. Explain use of branch and bound technique for solving assignment

problem.

2. Write a brief note on branch and bound strategy.

3. What do you mean by backtracking and dead node in backtracking?

Explain in brief. Discuss eight queen’s problem using backtracking

4. Explain Backtracking Method. What is N-Queens Problem? Give

solution of 4 Queens Problem using Backtracking Method.

5. Explain Traveling salesman problem with example.

Unit – 8: String Matching

1. Write Naive string-matching algorithm. Explain notations used in the

algorithm.

2. Working modulo q = 11. How many spurious hits does the Rabin-Karp

matcher encounter in the text T = 3141592653589793 when looking

for the pattern P =26?

3. Write any one application of string matching.

4. Discuss Rabin-karp algorithm for string matching

5. Explain finite automata for string matching with example.

6. What is the basic idea behind Rabin – Karp algorithm? What is

expected running time of this algorithm? Explain it with example

Unit – 9: Introduction to NP – Completeness

1. What is an approximation algorithm? Explain performance ratio for

approximation algorithm.

2. Explain polynomial-time reduction algorithm.

3. Which are the three major concepts used to show that a problem is an

NP Complete problem?

4. Write a short note on NP-Completeness Problem.

5. Write a brief note on NP-Hard Problems.

6. Write a brief note on NP-completeness and the Classes-P, NP and NPC.

7. Define P-type Problem

8. Explain Traveling salesman problem with example.