Important RGPV Question
AL-402 (Analysis And Design Of Algorithms )
IV Sem, AI
UNIT-1 Definitions of algorithms and complexity, Time and Space Complexity
Q.1) What do you mean by performance analysis of an algorithm? Explain.
Q.2) Explain the various criteria used for analyzing algorithm.
Q.3) Define algorithm. Discuss how to analyse algorithms.
Q.4) Describe the performance analysis of an algorithm in detail.
RGPV June 2023
Q.5) Consider the following recurrence T(n)=3T(n/3) + n obtain asymptotic bound using substitution method.
RGPV June 2023
Q.6) What are the factors which affect the running time of an algorithm?
Q.7) How recursive algorithms are analyzed? Analyze the execution time of recursive algorithm for tower of Hanoi problem.
Q.8) Write Divide – And Conquer recursive Quick sort algorithm and analyze the algorithm for average time complexity.
RGPV June 2023
Q.9) What do you understand by the term asymptotics?
Or What is the significance of asymptotic notations?
Q.10) What is the use of asymptotic notations?
Q.11) What is an asymptotic notations? Give the different notations to used to represent the complexity of algorithms.
Q.12) Give the definition of Big “oh” with example.
Q.13) Define Ω notation.
Q.14) What are the differences between big-oh (0), omega (ω) and theta (θ) notations?
Q.15) Why do we use asymptotic notations in the study of algorithms? Briefly describe the commonly used asymptotic notation.
Q.16) Briefly describe the asymptotic notations used in the study of algorithms. Also write the relational properties of the asymptotic notations.
Q.17) Apply the Greedy method to solve Knapsack problem for given instance. Where n = 3, m= 20, (p1, p2, p3) = (25, 24, 15) and weight (w1, w2, w3) = (18, 15, 10)
RGPV June 2023
Q.18) Give all the steps to convert the following complete binary tree into heap (max).
Q.19) Define time complexity. Describe different notations used to represent time complexity.
RGPV Nov 2023
Q.20) Explain heapsort algorithm with example.
Q.21) Discuss Strassen’s matrix multiplication as well as classical O (n²) one. Determine when Strassen’s method outperforms the classical one.
RGPV Nov 2023
Q.22) Following nodes are inserted in empty tree, to form minimum heap. With neat sketches show how insertion will be done. 8, 7, 11, 6, 2, 1, 5, 12.
Q.23) Illustrate heapsort on the array- A= [15, 8, 3, 9, 2, 10, 1, 40]
Q.24) Explain the various criteria used for analyzing algorithm.
RGPV June 2022
Q.25) What is the data structures used to perform recursion?
Q.26) Explain briefly binary search technique.
Or Explain any one application that can be solved by divide and conquer.
Q.27) How divide and conquer technique can be applied to binary tree Also write algorithm for divide and conquer.
Q.28) Implement an algorithm for binary search. Discuss in detail abo time complexity of binary search algorithm.
Q.29) Write and explain an algorithm to search an item in array using divide and conquer strategy with complexity O(logn).
Q.30) Give the divide and conquer solution for binary search and analyze its complexity.
Q.31) What is merge sort? Explain merge sort algorithm for
the list: 65, 47, 24, 83, 91, 14, 53, 12.
RGPV June 2022
Q.32) Discuss in which condition binary search is better than linear search.
Q.33) Find optimal solution for 0/1 Knapsack problem (w1, w2, w3, w4) = (10, 10, 12, 18); (P1, P2, P3, P4) = (2, 4, 6, 0) and M = 15.
RGPV June 2022
Q.34) Define and explain mergesort algorithm.
Q.35) Find the optimal solution using least cost branch and bound with n = 4, m = 15.
(w1, w2, w3, w4)=(3, 5, 6, 9); (P1, P2, P3, P4)=(15, 15, 17, 23)
RGPV June 2022
Q.36) Solve the recurrence relation- T(n)-3(n/4)+n
Or Solve the following recurrence relation –
T(n) 3T(n/4)+n “
Q.37) Apply binary search to find 123 in a list- 45, 96, 105, 121, 145, 192, 199, 205, 245, 275,123, 850, 905.
UNIT-2 Study of Greedy strategy, examples of greedy method like optimal merge patterns
Q.1) Explain about greedy technique.
Or Explain the concept behind greedy strategy.
Or What is greedy approach?
Q.2) Write the general characteristics of greedy algorithm.
Q.3) Write and explain the greedy strategy for optimal merge patterns. Or How two way merge pattern can be represented by binary merge tree?
Or Explain the concept behind greedy strategy. Using optimal merge pattern reedy method, merge the following files, f1, f2, f3,f4 and f5 with 20, 30, 10, 5 and 30 number of elements respectively.
Q.4) Write Kruskal’s Algorithm. Generate the MCST for the graph given in Figure 1 by applying Kruskal’s algorithm. RGPV June 2023
Q.5) Define the external path length.
Q.6) Obtain a set of optimal Huffman codes for the seven messages (M1, … , M7) with relative frequencies (q1, …, q7) = (4, 5, 7, 8, 10, 22, 15). Draw the decode tree for this set of codes.
RGPV June 2023
Q.7) What is minimum spanning tree?
Or Define minimum spanning tree.
Or Write short note on minimum spanning tree.
Q.8) Write the Kruskal’s algorithm for obtaining minimum spanning tree. Calculate its time in worst case.
Q.9) What is Knapsack problem in greedy strategy? Write the running time and recurrence relation of Knapsack algorithm.
Q.10) Discuss job sequencing problem by an example.
Q.11) Solve the following 0/1 Knapsack problem using dynamic programming P = (11, 21, 31, 33), W= (2, 12, 23, 15), C=42, n=4.
RGPV June 2023
Q.12) Explain how job sequencing with deadline can be solved using greedy approach.
Q.13) State the Job-Sequencing with deadlines problem. Find an optimal sequence to the n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines (d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3).
RGPV Nov 2023
Q.14) Explain prim’s and Kruskal’s algorithm shown in figure with the following example.
RGPV Nov 2023
Q.15)
Q.16) Explain how job sequencing with deadline can be solved using deadlines.
RGPV June 2022
Q.17) 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.
Q.18) What is minimum spanning tree? Using Prim’s algorithm find minimum spanning tree of the following graph-
Q.19) Explain minimum spanning tree using Prim’s algorithm for the given graph below.
RGPV June 2023
Q.20) Apply Kruskal’s and Prim’s algorithm for the following graph. Write their time complexities. Find the minimum cost in each case.
Q.21)
Q.22) A Knapsack capacity is 100. The weights and values objects are as follows-
Weight wi: 10 20 30 40 50 Value Pi: 20 30 66 20 60 Solve the Knapsack problem using greedy strategy and find maximum profit that can be obtained.
Q.23) A Knapsack capacity is W 60. The weights and profits of four items are as follows-
Solve the Knapsack problem using greedy strategy and find the maximum profit that can be obtained.
Q.24) Solve the following instances of the single source shortest path problem with vertex ‘a’ as the source.
Q.25) Write a greedy algorithm for sequencing unit time jobs with deadlines and profits. Using this algorithm, find the optimal solution when n=5.
Q.26) Find the shortest path from vertex I to vertex 3 in the following weighted graph using Dijkstra’s greedy algorithm.
UNIT-3 Concept of dynamic programming, problems based on this approach such as 0/1 knapsack
Q.1) Define dynamic programming. Or Write short note on dynamic programming.
Or Explain the concept of dynamic programming.
Q.2) Write the characteristics of dynamic programming.
Q.3) What is principle of optimality? Explain with suitable example. Or Explain principle of optimality
Q.4) What is multistage graph problem? Discuss its solution based on dynamic programming approach. Also give a suitable algorithm and find its computing time?
RGPV June 2023
Q.5) Discuss the elements of dynamic programming.
Or What are the key ingredients that an optimization problem must have for dynamic programming to be applicable? Explain them.
Q.6) Give the commonly used designing steps for dynamic programming algorithm.
Q.7) Define binomial coefficient.
Q.8) Discuss 0/1 Knapsack problem.
Q.9) Discuss about Multistage graph problem. Also give a suitable algorithm and find its computing time.
RGPV Nov 2023
Q.10)Write the recursive equation for 0/1 Knapsack problem based on the principles of optimality. Explain its execution strategy
Q.11) Solve the following instance of 0/1 Knapsack problem dynamic algorithm. The capacity of Knapsack m is 10
Q.12) Explain multistage graphs. Or Write a short note on multistage graphs. Or What is multistage?
Q.13) What is LCS problem? Write an algorithm to solve longest common sequence problem using dynamic programming approach.
Q.14) Explain how a reliability design can be obtained using dynamic programming.
Q.15) Briefly explain the concept of dynamic programming. Discuss how a reliability design can be obtained using dynamic programming.
Q.16) Explain Floyd Warshall algorithm problem with the graph given in figure.
RGPV June 2023
Q.17) Explain Floyd-Warshall algorithm with suitable example.
RGPV June 2022
Or Give Floyd-Warshall algorithm. What is its running time? Or Discuss Floyd-Warshall algorithm. Write its pseudocode.
Or Explain how to implement Warshall’s algorithm without using extra memory for storing elements of the algorithms intermediate matrices.
Or Write down the pseudocode for Floyd-Warshall algorithm. Take one graph and apply this algorithm to find all pair shortest path on it.
Q.18) Find the optimal solution for 0/1 Knapsack problem (w1, w2, w3, w4) = (10, 15, 6, 9), (P1, P2, P3, P4) = (2, 5, 8, 1) and w=30.
Q.19) Use the Floyd-Warshall algorithm and find all pair shortest paths for the following adjacency weighted matrix. RGPV June 2017
Q.20) Solve the following multistage problem using both forward and backward reasoning.
Q.21) Find minimum cost path from ‘s’ to ‘t’ in multistage graph using dynamic programming.
Q.22) Find a minimum cost path from ‘s’ to ‘t’ in multistage forward using dynamic programming-
Q.23) Solve the following multistage problem using both forward and backward reasoning.
UNIT-4 Backtracking concept and its examples like 8 queen’s problem
Q.1) What is Backtracking? Discuss any one problem solved by backtracking. Also give its advantages and disadvantages.
RGPV June 2023
Q.2) Explain backtracking technique for designing an algorithm.
Q.3) Explain and solve 4-queen’s problem using backtracking.
Q.4) Explain eight queen’s problem and apply backtracking to solve this problem.
Or What is backtracking ? Explain 8 queen’s problem and how can we solve it using backtracking.
Q.5) Explain n-queens problem.
Q.6) Solve 8-queen’s problem for a feasible sequence (6, 4, 7, 1).
Q.7) Give the definition of Hamiltonian cycle.
Q.8) Find a solution to the 8-Queens problem using backtracking strategy. Draw the solution space using necessary bounding function.
RGPV June 2023
Q.9) Write short note on Hamiltonian cycle.
Or Define Hamiltonian cycle with example.
Q.10) Write an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.
RGPV Nov 2023
Q.11) Apply and explain the backtracking method to solve the following (i) Hamiltonian circuit problem (ii) Subset-sort problem.
Q.12) Solve the following instance of travelling sales person problem using Least Cost Branch Bound. RGPV Nov 2023
Q.13) Write short note on graph coloring problem.
Q.14) Design a backtracking for graph coloring problem.
Or Write a pseudo algorithm for graph coloring problem.
Q.15) Explain graph coloring problem with their complexity.
Q.16) Construct state space tree for solving four queen’s problem using backtracking.
RGPV Nov 2023
Q.17) Colour the following graph using a vertex colouring algorithm. What is the minimum number of colours required?
Q.18) Define branch and bound method.
Q.19) Explain in detail 8-Queens problem.
RGPV June 2022
Q.20) Write about different types of bounding functions with example.
RGPV June 2022
Q.21) Solve travelling salesman problem by using branch and bound technique with example.
RGPV June 2023
Q.22) Solve the traveling salesperson problem using branch and bound technique.
Q.23) What do you understand by travelling salesman problem? Discuss with suitable example.
Q.24) Solve the TSP using branch and bound technique-
Q.25) Consider the following initial cost matrix for traveling salesman problem. Solve this problem using branch and bound technique.
Q.26) Solve the following instance of the Knapsack problem by the branch and bound algorithm. The Knapsack capacity m is 10.
Q.27) Write a short note on lower bound theory.
UNIT-5 Advanced tree and graph algorithms, NP-hard and NP-complete problems
Q.1) Compare and contrast NP-Hard and NP-Complete classes.
RGPV June 2023
Q.2) Define binary tree.
Or Write the rules to construct binary search tree.
Or Write short note on binary search tree.
Q.3) Create a B-tree for the following list of elements L= (86, 50, 40, 3, 94, 10, 70, 90, 110, 113, 116} given minimization factor t 3, minimum degree = 2 and maximum degree = 5.
RGPV June 2023
Q.4) How search can be applied on a binary search tree? Explain vis example.
Or Write an algorithm to search a binary search tree T for an identified Assume that each node in T has three fields LCHILD, DATA and RCHILD. What is the computing time of your algorithm.
Q.5) What is height balanced trees? Why to be balanced a height in a trees?
Q.6) Explain the concept of height balanced trees with their operations.
Q.7) Write short note on B-tree.
Q.8) Explain 2-3 trees with examples.
Q.9) Explain the P, NP-Hard and NP-complete classes? Give the relation between them.
RGPV Nov 2023
Q.10) Show the inorder, preorder and postorder for the following tree.
RGPV Nov 2023
Q.11) How multiway search is different from binary search tree?
Q.12) . Discuss in detail P, NP, NP complete and NP Hard problems with examples
RGPV June 2022
Q.13) The post order traversal of a binary tree T is DFEBGLJKHCA and inorder traversal of T is DBFEAGCLJHK. Construct the binary tree T and also writes the steps to construct the binary tree in postorder-inorder combination.
Q.14) A binary tree T has 9 nodes the inorder and preorder traversal of T yield the following sequence of nodes –
Inorder – E A C K F H D B G Preorder- F A E K C D H G B Draw the tree T.
Q.15) Discuss polynomial and non-polynomial time algorithms.
Q.16) (i) Insert the following sequence of elements into an AVL tree, starting with an empty tree- 10, 20, 15, 25, 30, 16, 18, 19
(ii) Delete 30 in the AVL tree that you got and re-balance the tree (if required).
Q.17) Obtain height balanced trees starting with empty tree on the following set of instructions- Dec, Jan, Apr, Mar, Jul, Aug, Oct, Feb, Nov, May, June.
Q.18) Insert the elements in the order shown below to build into an AVL tree. Also determine the complexity of this procedure 1, 26, 2, 25, 3, 24, 4, 23, 5, 22, 6.
Q.19) Create a B-tree for the following list of elements- L= (86, 50, 40, 3, 94, 10, 70, 90, 110, 113, 116) given minimization factor t=3, minimum degree=2 and maximum degree = 5.
Q.20) Write short note on tree traversals.
Q.21) Describe the graph traversal techniques.
Or Write short note on graph traversal.
Q.22) Compare DFS and BFS.
Q.23) Write any two data structures that are suitable for representing a graph. Write an algorithm for depth first traversal of a graph using one of your two data structures.
Q.24) List out the techniques for traversals in graph. Also explain each in detail with its procedure.
Q.25) Define P and NP problems.
Or Explain class P problem.
EXTRA QUESTIONS-
Q.1) Write short notes on any two of the following:
a) Reliability design
b) Correctness proof of Greedy algorithms
c) Design and complexity of Parallel Algorithms
d) Graph coloring problem
RGPV June 2023
Q.2) Explain partition exchange sort algorithm and trace this algorithm for n 8 elements: 24, 12, 35, 23, 45, 34, 20, 48.
RGPV Nov 2023
Q.3) Design a three stage system with device types D₁, D₂ and D3. The costs are $30, $15 and $20 respectively. The Cost of the system is to be no more than $105. The reliability of each device is 0.9,0.8 and 0.5 respectively.
RGPV Nov 2023
Q.4) Write short notes on any two of the following
a) Data Transfer Optimization and Logic Optimization
b) Differentiate between prim’s algorithm and Kruskal’s algorithm
c) Parallel algorithms
d) Approximation Algorithms
RGPV Nov 2023
Q.5) Write short notes on any three of the following.
a) Binary search trees
b) Huffman coding
c) Multistage graph
d) Hamiltonian cycle
e) Quick sort.
RGPV June 2022
— Best of Luck for Exam —
