Ada Imp

Analysis & Design of Algorithms
1) What is an Algorithm? Explain Various Properties of an Algorithm.
2) What do you mean by Asymptotic Notations? Explain.
3) Explain why analysis of algorithms is important? Explain: Worst Case, Best Case & Average Case
Complexity.
4) What is the difference between Selection Sort & Bubble Sort?
5) Apply the Bubble Sort Algorithm for Sorting {U,N,I,V,E,R,S}.
6) Sort the Letters of word “EDUCATION” in Alphabetical Order using Insertion Sort.
7) Write Iterative & recursive Algorithm for finding the Factorial of N. Derive the Time Complexity of
both Algorithms.
8) Explain an Algorithm for Selection Sort Algorithm. Derive its Best Case, Worst Case & Average
Case Time Complexity.
9) How Divide & Conquer Approach Work?
10) Trace the Quick Sort for Data A = {6,5,3,11,10,4,7,9}.
11) Write an Algorithm for Quick Sort & Derive Best Case, Worst Case using Divide & Conquer
Technique also Trace given data (3,1,4,5,9,2,6,5).
12) Analyze Quick Sort Algorithm in Best Case & Worst Case.
13) Discuss Insertion Sort with its Time Complexity. Support your answer with suitable example.
14) Trace the Merge Sort for data A = {6,5,3,11,10,4,7,9}.
15) Discuss Matrix Multiplication Problem using Divide & Conquer Technique.
16) Explain Binary Search with the suitable example.
17) Multiply 981 by 1234 by Divide & Conquer Method.
18) What is Principal of Optimality? Explain its use in Dynamic Programming Method.
19) 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].
20) 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.
21) Write equation for Chained Matrix Multiplication using Dynamic programming.
22) 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).
23) 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} &
values v(v1,v2,v3)={2, 3, 4} are given. The knapsack capacity M is 3 units.
24) Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42) find the maximum profit
using dynamic method.
25) Solve Making change problem using dynamic technique. D1 = 1, d2=3, d3=5, d4=6. Calculate for
making change of Rs. 8
26) Solve Making Change problem using Dynamic Programming. (Denominations:
d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.
27) Solve Making change problem using dynamic technique. d1 = 1, d2=2, d3=4, d4=6, Calculate for
making change of Rs. 10.
28) Elaborate Longest Common Subsequence problem with the help of dynamic programming.
Support your answer with proper illustration.
29) Given two sequence of characters, X={G,U,J,A,R,A,T}, Y = {J,R,A,T} obtain the longest common
subsequence.
30) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L}.
31) For the following chain of matrices find the order of parenthesization for the optimal chain
multiplication (15,5,10,20,25).
32) For the following chain of matrices find the order of parenthesization for the optimal chain
multiplication (13,5,89,3,34).
33) 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
34) Discuss Assembly Line Scheduling problem using dynamic programming with example.
35) Explain the difference between Greedy and Dynamic Algorithm.
36) Write down the characteristics of Greedy Algorithm.
37) Find an optimal Huffman code for the following set of frequency. a : 50, b: 20, c: 15, d: 30.
38) Consider Kanpsack capacity W=50, w=(10,20,40) and v=(60,80,100) find the maximum profit
using greedy approach.
39) How huffman code is memory efficient compare to fixed length code?
40) Find the Huffman code for each symbol in following text
ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE
41) Briefly discuss Huffman code.

42) Explain job scheduling problem using greedy algorithm. Support your answer by taking proper
illustration.
43) Expalin Dijkstra algorithm to find the shortest path.
44) Define MST. Explain Kruskal’s algorithm with example for construction of MST.
45) Discuss Kruskal’s Algorithm for finding minimum spanning tree. Give proper example.
Using Greedy Algorithm to 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).
46) Find out the NCR ( 5 3 )Using Dynamic Method.

47)
48) Find single source shortest path using Dijkstra’s algorithm form a to e.
49)
50)
51)
52)
Chapter:- 7
53) Write a brief note on branch & bound strategy.
54) What do you mean by backtracking? Explain in brief. Discuss eight queens problem using
backtracking .
55) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4-Queens Problem
using Backtracking Method.
56) Explain 4 queen problem with one of the solution.
57) Draw the state space tree diagram for 4 Queen problem and also show the tree after applying
backtracking.
58) Explain Traveling salesman problem with example.
59) Explain Minimax Principle.
Chapter:- 8
60) What is Finite Automata? Explain use of finite automata for string matching with suitable
example.
61) Explain naïve String Matching algorithm with example.
62) What is the basic idea behind Rabin - Karp algorithm? What is expected running time of this
algorithm ? Explain it with example.
63) Explain The Knuth-Morris-Pratt algorithm.
Chapter:- 9
64) Write a brief note on NP-Hard Problems.
65) Write a short note on NP-Completeness Problem.
66) Write a brief note on NP-completeness and the classes-P, NP & NPC.
67) Define P and NP problems. Also give example of each type of problem.
68) State whether Hamiltonian problem is a NP-Complete problem? Justify your answer.

Ada Imp

Uploaded by

Copyright:

Available Formats

Ada Imp

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ada Imp

Uploaded by

Copyright:

Available Formats

Analysis & Design of Algorithms

1) What is an Algorithm? Explain Various Properties of an Algorithm.

2) What do you mean by Asymptotic Notations? Explain.

capacity W=5, Weight and Value are as follows :(2,12),(1,10),(3,20),(2,15).

41) Briefly discuss Huffman code.

46) Find out the NCR ( 5 3 )Using Dynamic Method.

56) Explain 4 queen problem with one of the solution.

58) Explain Traveling salesman problem with example.

59) Explain Minimax Principle.

61) Explain naïve String Matching algorithm with example.

63) Explain The Knuth-Morris-Pratt algorithm.

64) Write a brief note on NP-Hard Problems.

65) Write a short note on NP-Completeness Problem.

You might also like