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 —