Table of Contents

Toggle**Important RGPV Question**

**CS-402 (****Analysis And Design Of Algorithms ****)**

**IV Sem, CS**

**UNIT 1- Algorithms, Designing algorithms, analyzing algorithms**

**Q.1)**Β Explain Divide and Conquer techniques

**RGPV June 2022**

**Q.2)**Β Sort the following array using heap-sort techniques. 7 heap-sort

(5, 8, 3, 9, 2, 10, 1, 45, 32)

**RGPV June 2022**

**Q.3) **Define Big “Oh” with example.

**RGPV June 2022**

**Q.4) **What do you mean by performance analysis of an algorithm? Explain.

**RGPV June 2023**

**Q.5)**Write short note on Quick Sort.

**RGPV June 2022**

**Q.6) **Trace the quick sort algorithm to sort the list C, O, L, L, E, G, E in alphabetical order.

**RGPV June 2023**

**Q.7) **Β Discuss Strassen’s matrix multiplication and derive its time complexity.

**RGPV June 2023**

**Q.8) **Design merge sort algorithm and discuss its best-case, average-case and worst-case Efficiency.

**RGPV June 2023**

**Q.9) **Discuss briefly Heap sort.

**RGPV June 2023**

**Q.10) **Give an algorithm for quick sort and analyze the algorithm.

**RGPV Nov 2023**

**Q.11) **Explain Heap? Sort the following data using heap sort.

81, 39, 10, 36, 45, 15, 55, 23, 91, 88, 12

**RGPV Nov 2023**

**Q.12) **Solve the following recurrence relations using the substitution method.

**RGPV June 2023**

**Q.13)** What do you mean by Asymptotic Notations? Explain different asymptotic notations used in algorithms.

**RGPV Dec 2020, June 2020**

**Q.14) **What is the need of obtaining the time and space complexity measures of an algorithm? Justify your answer by some example.

**RGPV Dec 2020, June 2020**

**Q.15) **Sort the following array using Heap sort.

66, 33, 40, 20, 50, 88, 60, 11, 77, 30, 45, 65

**RGPV Dec 2020**

**Q.16) **Write short notes

a) Subset sort problem

b) Big ‘oh’ Notation

**RGPV Dec 2020**

**Q.17) **Show the various steps involved in the quick sorting of (23, 67, 12, 78, 33, 28, 97, 10, 6, 87, 39).

**RGPV June 2020**

**Q.18) **Explain merge sort algorithm and find the complexity of the algorithm.

**RGPV June 2020**

**UNIT 2- Study of Greedy strategy, examples of greedy method like optimal merge patterns**

### Β **Q.1)**Β Explain Prim’s algorithm with example.

**RGPV June 2023**

**Q.2)**Β Solve the following instances of the single source shortest path problem with vertex ‘a’ as the source.

**RGPV June 2022**

**Q.3) **“How to solve the Knapsack problem with greedy method? Explain.

**RGPV June 2023**

**Q.4) **Write an algorithm for single source shortest path and explain with an example.

**RGPV June 2023**

**Q.5) **Discuss briefly about the minimum spanning tree.

**RGPV June 2023**

**Q.6) **Find an optimal solution for following 0/1 Knapsack problem using dynamic programming:

Number of objects n = 4, Knapsack Capacity M = 5, Weights

and Profits

**RGPV June 2023**

**Q.7) **Β Show that if r is a spanning tree for the undirected graph

G, then the addition of an edge q, qβE(t) and qβ E(G), to creates a unique cycle.

**RGPV Nov 2023**

**Q.8)**

**RGPV Nov 2023**

**Q.9) **Give an example of a set of knapsack instances for which

The set should include one instance for each n.

**RGPV Nov 2023**

**Q.10) **Tabulate the differences between Kruskal’s and Prim’s algorithm.

**RGPV Dec 2020**

**Q.11) **What is Knapsack problem? How can we solve using Greedy approach?

**RGPV Dec 2020**

**Q.12) **Write algorithm for single source shortest path and find its complexity?

**RGPV Dec 2020**

**Q.13) **Β Apply Kruskal’s and Prim’s algorithm for the following graph? Write their time complexities. Find the minimum cost in each case.

**RGPV Dec 2020**

**Q.14) **Using Dijkstra’s algorithm find the shortest path from A to D for the following graph.

**RGPV June 2020**

**Q.15) **Write an algorithm to solve Knapsack problem using Greedy technique. Find the optimal solution to the Knapsack instance n = 7, m = 15 (P1, P2, P3… P7) (10, 515, 7, 6, 18, 3) = (W1, W2, W3… W7)= (2, 3, 5, 7, 1, 4, 1)

**RGPV June 2020**

**UNIT 3- Concept of dynamic programming**

**Q.1)**Β What do you mean by forward and backward approach of problem solving in Dynamic Programming?

**RGPV June 2023**

**Q.2)**Β How the reliability of a system is determined using dynamic programming? Discuss.

**RGPV June 2023**

**Q.3) **How reliability design can be obtained using dynamic programming?

**RGPV Nov 2023**

**Q.4) **What is multistage graph? Write down its properties?

**RGPV Dec 2020**

**Q.5) **Use the Floyd-Warshall algorithm and find shortest path between all pairs of vertices for the following graph.

**RGPV Dec 2020**

**Q.6) **Explain Floyd-Warshall algorithm with an example of your choice.

**RGPV June 2020**

**UNIT 4- ****Backtracking concept and its examples like 8 queenβs problem**

**Q.1)**Β Write short notes.

i) Parallel Algorithm

ii) Graph Coloring

**RGPV June 2022**

**Q.2)**Β Explain the 8 queen’s problem and apply the backtracking to solve the 8 queen’s problem.

**RGPV June 2023**

**Q.3) **Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB.

**RGPV June 2023**

**Q.4) **Generalize Hamiltonian so that it processes a graph whose edges have costs associated with them and finds a Hamiltonian cycle with minimum cost. Assume that all edge costs are positive.

**RGPV Nov 2023**

**Q.5)**

**RGPV Nov 2023**

**Q.6) **What is the meaning of Lower bound theory and how can it be used in solving algebraic problems?

**RGPV Dec 2020**

**Q.7) **Β Write short notes.

a) Hamiltonian cycle

b) Β Graph coloring problem

**RGPV Dec 2020**

**Q.8) **Explain how to solve travelling salesman problem by the method of branch and bound and analyze complexity of the algorithm.

**RGPV June 2020**

**Q.9) **Construct state space tree for solving four queen’s problem using backtracking.

**RGPV June 2020**

**Q.10) **What is Backtracking? Discuss any one problem solved by backtracking. Also give its advantages and disadvantages.

**RGPV June 2020**

**UNIT 5- Binary search trees, height balanced trees**

Β Β **Q.1)**Β Discuss in detail NP complete problems with example.

**RGPV June 2022**

**Q.2)**Β Construct B tree of order 5 for the list of elements.

2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21

**RGPV June 2022**

**Q.3) **Compare Bfs and Dfs.

**RGPV June 2022**

**Q.4)**Show preorder, inorder and postorder for the following tree.

**RGPV June 2022**

**Q.5) **Discuss the differences between BFS and DFS.

**RGPV June 2023**

**Q.6) **What are 2-3 trees used for? Why are 2-3 trees better than BST trees? Write the limitations of 2-3 tree in CSE.

**RGPV June 2023**

**Q.7) **Β Write a function to construct the binary tree with a given inorder sequence I and given postorder sequence P. What is the complexity of the function?

**RGPV Nov 2023**

**Q.8) **Give an example of an n-vertex graph for which the depth of recursion of DFS starting from a particular vertex V is n-1 whereas the queue of BFS has at most one vertex at any given time, if BFS is started from the same vertex V.

**RGPV Nov 2023**

**Q.9) **In what way is an AVL tree is better than a binary tree insert these keys in to an AVL tree.

**RGPV Dec 2020**

**Q.10) **What are B-trees? Write down its properties? What is the need for B tree? What is the height of a B tree of order m?

**RGPV Dec 2020**

**Q.11) **Write short notes.

a) NP-Completeness

b) Tree Traversals

**RGPV Dec 2020, June 2020**

**Q.12) **Differentiate between DFS and BFS algorithms by an example.

**RGPV June 2020**

**Q.13) **Β What are B-trees? How are they created? Give its advantages.

**RGPV June 2020**

**EXTRA QUESTIONS**

**Q.1)**Β How can comparison trees be used for deriving lower bounds on problem of sorting.

**RGPV June 2023**

**Q.2)**Β

**RGPV Nov 2023**

**— Best of Luck for Exam —**