GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY

Knowledge Park-II, Greater Noida, U.P.

Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

Important Question Bank

Unit-1
I Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of
Functions, Performance Measurements, Sorting and Order Statistics - Shell Sort, Quick
Sort, Merge Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time.
1. Solve the following recurrences: -
a. T(n) = T(n/2) + T(n/4) + T(n/8) + n
b. T(√n) = T(n) +O(ln n)
2. What is the time complexity of counting sort? Illustrate the operation of counting sort on array
A={1,6,3,3,4,5;6,3,4,5}
3. Discuss asymptotic notations in brief.
4. Discuss the best case and worst case complexities of quick sort algorithm in detail.
5. Rank the following by growth rate: n, 2lgn √n, log n, log (log n), log 2 n, (lg n)lg n , 4, (3/2)n, n!

6. Use a recursion tree to give asymptotically tight solution to the recurrence

T(n) = T (αn) + T((1-a)n +cn
where ‘α’ is a constant in the range 0 <α< l and c>0 also constant.
7. What are the fundamental steps involved in algorithmic problem solving?
8. Write recursive function to find nth Fibonacci number.
9. Explain the concepts of quick sort method and analyze its complexity with suitable example
10. Explain the concept of merge sort with example.
11. Among Merge sort, Insertion sort and quick sort which sorting technique is the best in worst case. Apply
the best one among these algorithms to Sort the list E, X, A, M, P, L, E in alphabetic order.
12. What do you understand by 'stable’ sort? Name two stable sort algorithms
13. Solve the following recurrence using Master method: T (n) = 4T (n/3) + n2
14. Solve the following By Recursion Tree Method T(n)=n+T(n/5)+T(4n/5).
15. Explain HEAP-SORT on the array. Illustrate the operation of HEAP-SORT on the array A= {6,
14, 3, 25, 2, 10, 20, 7, 6}
16. How will you sort following array A of elements using heap sort: A = (23, 9,18, 45, 5,9, 1,17, 6).

1
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

II Advanced Data Structures: Red-Black Trees, B – Trees, Binomial Heaps, Fibonacci

Heaps, Tries, Skip List
1. Describe the puberties of red Black tree. Show that Red Black Tree with 11 internal nodes has
height at most 2 lg(n+1).
2. Discuss the complexity of Max-Heapify and Build- Max Heap procedures.
3. What are the advantages of Red Black Tree over Binary Search Tree? Write algorithms to insert a
key in a red black tree, Insert the following sequence of information in an empty red _black tree 1,
2, 3, 4, 5, 5.
4. Define the binomial heap in detail. Write an algorithm for performing the union Operation of two
binomial heaps and also explain with suitable example.
5. How B-Tree differs with other tree structures. Insert the following information E S, Q, K, C, L,
V,’ W M, R, N, P, A, D, Z, E into an empty B-Tree with degree t = 2.
6. Prove that if n>=l, then for any n-key B-Tree of height h and minimum degree t >=2. h<= log ((n
+1)/2).
7. Insert the following keys in a 2-3-4 B Tree: 40, 35, 22, 90, 12, 45, 58, 78, 67, 60 and then delete
key 35 and 22 one after other.
8. Insert the following element 1n an initially empty RB- Tree -12, 9, 81, 76, 43 65, 88, 76, 32, 54.
Now Delete 23 and 81
9. Insert the nodes 15, 13, 12, 16, 19, 23', 5, 8 in empty Red Black Tree and delete in the reverse
order of insertion.
10. Using minimum degree ‘t’ as 3, insert following sequence of integers 10, 25, 20, 35, 30, 55, 40,
45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty B-Tree. Give the number of nodes
splitting operations that take place.
11. Insert the following information F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E,G,I. Into an
empty B-tree with degree t=3.
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

Unit-III
III Divide and Conquer with Examples Such as Sorting, Matrix Multiplication, Convex Hull
and Searching.
Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack,
Minimum Spanning Trees – Prim’s and Kruskal’s Algorithms, Single Source Shortest Paths
- Dijkstra’s and Bellman Ford Algorithms.
1. What do you mean by minimum spanning “tree? Write an algorithm for minimum spanning tree
that may generate multiple forest trees and also explain with suitable example.
2. Describe in detail the Strassen’s Matrix Multiplication algorithms based on divide and conquer
strategies with suitable example.
3. Prove that if the weights on the edge of the connected undirected graph are distinct then there is a
unique Minimum Spanning Tree. Give an example in this regard. Also discuss Prim’s Minimum
Spanning Tree Algorithm in detail.
4. When do Dijkstra and the Bellman-Ford algorithm both fail to find a shortest path? Can Bellman
ford detect all negative weight cycles in a graph‘? Apply Bellman Ford Algorithm on the
following graph:

5. List out the disadvantages of divide and conquer algorithm.

6. Briefly explain the Prim’s algorithm.
7. Consider following instance for simple knapsack problem. Find the solution using greedy method.
N=8 P= {11, 21, 31, 33, 43, 53, 55, 65} W: {1, 11, 21, 23, 33, 43,45, 55} M: 110.
8. Find the shortest path in the below graph from the source vertex 1 to all other vertices by using
Dijkstra’s algorithm.
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

9. What is Minimum Cost Spanning Tree? Explain Kruskal’s Algorithm and Find MST of the
Graph. Also write its Time-Complexity

10. Define spanning tree. Write Kruskal’s algorithm for finding minimum cost spanning tree.
Describe how Kruskal s algorithm is different from Prim s algorithm for finding minimum cost
spanning free.
11. What do you mean by convex hull? Describe an algorithm that solves the convex hull problem.
Find the time complexity of the algorithm.
12. Given the six items in the table below and a Knapsack with Weight 100, what is the solution to
the Knapsack problem in all concepts. I.e. explain greedy all approaches and find the optimal
solution
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

Important Questions
Unit-IV
IV Dynamic Programming with Examples Such as Knapsack. All Pair Shortest Paths –
Warshal’s and Floyd’s Algorithms, Resource Allocation Problem. Backtracking, Branch
and Bound with Examples Such as Travelling Salesman Problem, Graph Coloring, n-Queen
Problem, Hamiltonian Cycles and Sum of Subsets.
1. Differentiate between Dynamic programming and Greedy approach. What is 0/1 knapsack
problem? Solve the following instance using Dynamic programming write the algorithm also.
Knapsack Capacity=10 P=<1,6,18,22,28> and w=<l,2,5,6,7>.
2. Differentiate between Backtracking and Branch and Bound approach. Write an algorithm for sum
subset problem using back tracking approach. Find all possible solution for following instance
using same if m=30, s=< 1,2,5,7,8,10,15,2o,25 >.
3. Define TSP problem in detail. Find the solution for the following instance of TSP problem using
branch and bound.
4. Define principal of optimality, When and how dynamic programming is applicable.
5. Explain application of graph coloring problem.
6. Differences between branch & bound and backtracking technique.
7. Compare adjacency matrix and linked Adjacency lists representation of a Graph with suitable
example/diagram.
8. Solve the Subset sum problem using Backtracking where n=4 m=18 w [4] = {5, 10, 8, 13}.
9. Give Floyd War shall algorithm to find the shortest path for all pairs of vertices in a graph. Give
the complexity of the algorithm Explain with example
10. What is travelling salesman problem? Find the solution ‘of following travelling salesman problem
using branch and bound method. Cost matrix =
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

11. Solve the following 0/1 knapsack problem using dynamic programming. P=[11,21,31,33]
w=[2,11,22,15] c=40, n=4. ,
12. Find an LCS for the sequences. X={x1, x2 ......Xm,} and Y={y1 ,y2. .. yn }. Also show that it
requires o (m+n) time.
 GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY
Knowledge Park-II, Greater Noida, U.P.
Department of CSE & Allied Specialized Branches
Odd Semester, 2024-25

Important Questions
Unit-V
V Selected Topics: Algebraic Computation, Fast Fourier Transform, String Matching, Theory
of NP-Completeness, Approximation Algorithms and Randomized Algorithms
1. Define different complexity classes in detail with suitable example. Show that TSP problem is
NP Complete. ,
2. Describe approximation Algorithm in detail. What is the approximation ratio? Show that vertex
cover problem is 2 approximate. ,
3. What is string matching algorithm? Write Knuth-Morris-Pratt algorithm and also calculate the
prefix function for the pattern P=ababaaca. ,
4. What are approximation algorithms? What meant by P (n) approximation algorithms. What do
you mean by stability of algorithm? Explain its application.
5. Define BNP, NP hard and NP Complete Problems: time. Prove Travelling Salesman Problem is
NP Complete.
6. What is the application of ‘Bast Fourier Transform (F F T )7 Also write the recursive algorithm
for FFT.
7. How approximation algorithms help to solve the problems? What is the approximation ratio?