ANALYSIS DESIGN OF ALGORITHM (ADA) | TUTORIAL QUESTIONS

📌 ANALYSIS DESIGN OF ALGORITHM (ADA) 📌

TUTORIAL QUESTIONS

TUTORIAL - 1

1. WRITE THE PROCEDURE OF MERGE SORT AND SORT THE GIVEN ARRAY OF 8 ELEMENTS USING MERGE SORT.35,10,7,22,5,13,16,3

2. WHAT ARE THE FACTORS WHICH EFFECT THE RUNNING TIME OF AN ALGORITHM.

3. IMPLEMENT AN ALGORITHM FOR BINARY SEARCH. DISCUSS IN DETAIL ABOUT TIME COMPLEXITY OF BINARY SEARCH ALGORITHM.

4. EXPLAIN VARIOUS ASYMPTOTIC NOTATION METHODS USED TO REPRESENT THE RATE OF GROWTH OF RUNNING TIME OF ALGORITHM.

5. WRITE AN ALGORITHM TO SEARCH AN ITEM IN A LINEAR LIST. IF THERE ARE N ELEMENTS IN THE LIST, WHAT IS THE RUNNING TIME OF ALGORITHM.

6. EXPLAIN A SEARCH PROCEDURE USING DIVIDE AND CONQUER TECHNIQUE. PROVE THAT THE PROCEDURE WORK CORRECTLY. GIVE THE TIME COMPLEXITY OF ALGORITHM.

7. EXPLAIN MATRIX MULTIPLICATION USING DIVIDE AND CONQUER STRATEGY

8. DERIVE THE RECURRENCE RELATION FOR SELECTION SORT AND ANALYSE THEIR TIME COMPLEXITY.

9. WHAT IS AN ALGORITHM? WHY WE DESIGN ALGORITHM? WHAT ARE THE DIFFERENT WAY TO DESIGN ALGORITHM?

10. HOW WE ANALYSE ALGORITHM.WHAT ARE THE FACTORS TO ANALYSE ALGORITHM AND WHAT ARE THEIR BENEFITS.

TUTORIAL - 2

1. Apply Kruskal’s algorithm to find a generic minimum spanning tree for the graph:

2. Find the optimal merge problem for the following data:      28, 32, 12, 5, 84, 53, 91, 35, 3, 11

3.  Find an optimal solution for the Knapsack problem: n =7, M = 15 (P1, P2,….p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, ……, w7) = (2, 3, 5, 7, 1, 4).

4. Compute the minimum travel cost for the given graph G.

5. What is the optimal-Haffman code for the following set of frequencies based     on first 8 Fibonacci numbers:     a:1      b:1      c:2      d:3      e:5      f:8       g:13    h:21

6.    Find the shortest path from vertex 1 to vertex 3 in the following weighted graph using Dijkstra’s greedy algorithm.

7. Explain concept behind greedy strategy.

8. Write difference between Prim’s algorithm and Kruskal’s  algorithm.

9. Find the optimal binary merge tree (pattern) for ten files whose length   are 28, 32, 12, 5, 84,53, 91, 35, 3 and 11. Also find its weighted          external path length.

10. What is the principle of optimality? Explain with the help of suitable                  example.

11. Consider  n=7, m-15, (P1,P2,….P7)=(10,5,15,7,6,18,3) and (w1,w2,…..w7)     = (2, 3, 5, 7, 1, 4 1) Obtain the optimal solution for this knapsack instance.

12. Find an optimal merge pattern for 11 files whose length are 28, 32, 12, 5,         84, 5, 3, 9, 35, 3, 11.Write and explain the algorithm used and determine         its complexity.

13. Write Dijkstra’s algorithm to find the shortest path between two given vertices. Using this algorithm find shortest path from vertex 3 in the  following weighted graph.

14. Find the optimal schedule for the following job with n=7 profits: (P1, P2, …..     P7) = (1, 3 , 5, 18, 20, 6, 1, 38) and deadlines (d1, d2, d3,  … d7) = (1, 3,     3, 4, 1, 2, 1).

15. Consider the graph G=(V, E) given below     Find the minimum spanning tree by Prim’s algorithm.

16. What is the optimal Huffman code for the following set of frequencies based     on first 8 fibonacci numbers:     a: 1     b:1      c:2      d:3      e:5      f:8       g:13    h:21

17. There are 5 jobs whose profits (P1….P5) = (20, 15, 10, 1, 6) and deadlines     = (2, 2, 1, 3, 3). Find the optimal solution that maximises profit on                 scheduling these jobs. Discuss it algorithm too.

18. Obtain a set of optimal Huffman codes for the seven message (M1, ….. M7)     with relative frequencies (q1,………, q7) = (4, 5, 7, 8, 10, 22, 15). Draw the     decode tree for this set of codes.

19. Obtain a set of optimal Huffman codes for the seven message (M1, ….. M7)     with relative frequencies (q1,………, q7) = (4, 5, 7, 8, 10, 22, 15). Draw the     decode tree for this set of codes.

20. Consider the Knapsack instance n=3, (W1, W2, W3) = (2, 3, 4) and (P1,P2, P3) = (1, 2, 5) and m =5. Find the optimal solution.

21. There are 5 jobs whose profits.(P1, …., P2) = (20, 15,10, 1, 6) and deadline (2, 2, 1, 3, 3).Find the optimal solution that minimizes profit on scheduling      these jobs. Discuss its algorithm too.

22.  What is Greedy approach?

23. How to way merge pattern can be represented by binary merge tree?

24. Discuss job sequencing problem by an example.

25. Find an optimal solution to the knapsack instance n=3, m=20, (P1, P2, P3)     = (25, 24, 15) AND (W1, W2, W3) = (18, 15, 10).

26. What is greedy techniques? Derive the equation for the optimal solutions.

27. Solve the following instance of the single source shortest path problem with     vertex ‘a’ as the source.

28. Solve the following instance of the single source shortest path problem with     vertex ‘a’ as the source.

29.  Construct a Huffman code for the following data :              Character   :       A         B         C          D        E               Probability:       0.4      0.1      0.2      0.15    0.15      Decode the text whose ending 100010111001010 using the above Huffman       code.

30. Write a greedy algorithm for sequencing unit time jobs with deadline and         profits. Using this algorithm, Find the optimal solution when n=5 ,Job(P1,P2, P3, P4, P5), Profit(20, 15, 10, 5, 1), Deadline(2, 2, 1, 3, 3).

TUTORIAL - 3

1. Explain Reliability design briefly.

2 . Define how knapsack problem is solved by using dynamic programming?    Consider n=3,   (w1,w2,w3)=(2,3,3), (p1,p2,p3)=(1,2,4) and m=6.find optimal solution for the given data.

3. What is the difference between Greedy Knapsack and 0/1 knapsack.Show that 0/1 knapsack solution not be an optimal solution.

4 . Explain dynamic programming. Explain multistage graph algorithm briefly.

5 .    Apply floyd-warshall algorithm for constructing shortest path. Show the matrices D(k) and ∏(k) computed for the graph.

6.  Find a minimum cost path ‘s’ to ‘t’ in multistage graph using dynamic programming.

1.

1.

1.

1.

1.

1.

1.

TUTORIAL - 4

1.  Explain travelling salesman problem using branch and bound method. Generate a state space tree for the following cost matrix:

2 . Design a backtracking algorithm for graph-coloring problem.

3 . Explain travelling salesman problem using branch and bound method. Generate a state space tree for the following cost matrix:

4. Find a Hamiltonian circuit using backtracking method.

5 . Explain Graph Coloring problem with example.

6 . What do you mean by FIFO Branch and Bound algorithm and LC search algorithm ? Explain briefly.

1.

1.

1.

1.

1.

TUTORIAL - 5

1. Create a B-tree of order 5 from the following list of data items: 15, 20, 35, 95, 13, 10, 50, 65, 5, 70, 30, 40, 45, 80, 25, 6, 22, 33

2 . Write an algorithm for BFS and DFS.

3 . Define NP completeness and reducibility of problems.What are NP hard problems ?

4. A binary tree has 9 nodes. The inorder and preorder traversal of tree yield the following sequence of nodes:     Inoredr   : E A C K F H D B G      Preorder : F A E K C D H G B

5 .  Insert these keys into an AVL tree:     342, 206, 444, 523, 607, 301, 142, 183, 102, 157, 149.

1.