Data Structures and Algorithms — Winter 2025

Define Stack. Differentiate between Stack and Queue.

Compare various asymptotic notations. Mention properties of properties of an algorithm.

Define data structures. Draw classification diagram of various data structures. Mention the operations that can be performed over data structures. Show that 4n2 = O(n3) , using concept of asymptotic notations.

Evaluate given prefix expression + - 9 2 7 * 8 / 4

Show how the given expression can be converted from Infix to Postfix notation using Stack: ((A – B) + D / ((E + F) * G))

Write the algorithm for insertion of a new node at the beginning of singly linked list. Consider the Queue given below which has FRONT =1 and REAR=5 A B C D E Now perform the following operations on the queue: 1. Add F 2. Delete two letters 3. Add G 4. Add H 5. Delete four letters 6. Add I

Write a program to perform insert and delete operations in a doubly linked list.

Solve the following recurrence relation T(n) =T(n-1) + 5 for n >1, and T(1) = 0 as initial condition.

Apply a quick sort algorithm to sort the following data. Justify the steps. 41,27,74,10,64,53

Construct AVL tree for following sequence: 45,36,27,63,39. After the creation of AVL tree insert 72 ,18 and delete 72. (Show each iteration)

Find the order of growth for solutions of following recurrences using master’s theorem:

T(n) = 4T(n/2) + n, T(1) =1 ii) T(n) = 4T(n/2) + log n

Apply a merge sort algorithm to sort the following data. Justify the steps. 41,27,74,10,64,53

Create a Binary Search Tree for given elements 84, 25, 36, 15, 48, 09, 17, 55, 92, 11, 15, 7, 1, 12. Find in order and preorder traversal for the same.1

What is principal of optimality? Explain its use in Dynamic Programming Method.

Perform Depth First Search on below given undirected graph starting at node 1 Show the resultant stack.

Solve the following making change problem using dynamic programming method: Amount = Rs. 8 and Denominations: (Rs. 1, Rs. 3, Rs. 5 and Rs. 6)

Differentiate between greedy method and dynamic programming.

Perform Breadth First Search on previously mentioned graph of Q.4(c) starting at node 1. Show the resultant queue.

Describe longest common subsequence problem. Find longest common subsequence of following two strings Xand Yusing dynamic programming. X=<MLNOM>, Y=<MNOM>

Consider the graph given below:

Write the adjacency matrix of G. ii) Write the path matrix of G. iii) Is the graph complete? Justify.

Find out the Minimum Spanning Tree using Kruskal algorithm for given Graph:

Find a minimum number of multiplications required to multiply: A [1 × 5], B [5 × 4], C [4 × 3], D [3 × 2], and E [2 × 1]. Also, give optimal parenthesization.

Identify mutually compatible activities and the feasible solution set for below given activity selection problem:

Find out the Minimum Spanning Tree using Prim’s algorithm for given Graph; for previously mentioned graph of Q.5(b) .

Find the optimal solution of the knapsack instance n=4,W=5(capacity), w=(2,1,3,2) and v= (12,10,20,15)