sQ1: Define graph and write down the properties and representation of graph.

(Long)

A graph is a non-linear data structure consisting of a set of vertices (also called nodes) and a set of edges (connections between nodes). It is used to model pairwise relationships between objects. Graphs are
widely used in real-life applications such as social networks, transportation networks, and computer networks.

Types of Graphs:

Directed Graph (Digraph): Edges have direction.

Undirected Graph: Edges do not have direction.

Weighted Graph: Each edge has a weight or cost.

Unweighted Graph: All edges are considered equal.

Cyclic Graph: Contains at least one cycle.

Acyclic Graph: Contains no cycles.

Connected Graph: There is a path between any pair of vertices.

Disconnected Graph: Some vertices are not connected.

Properties:

Vertex (V): A node in the graph.

Edge (E): A connection between two vertices.

Degree: Number of edges incident on a vertex.

Path: A sequence of edges connecting a sequence of vertices.

Cycle: A path that starts and ends at the same vertex.

Connectivity: The ability to reach one vertex from another.

Graph Representations:

Adjacency Matrix: A 2D matrix where matrix[i][j] = 1 (or weight) if an edge exists between vertex i and j, else 0. Space Complexity: O(V²)

Adjacency List: An array of lists where each list contains the neighbors of a vertex.

Space Efficient for sparse graphs.

Space Complexity: O(V + E)

Q3: Describe the maximum flow problem and explain Steps:

the working of Ford Fulkerson’s algorithm and Initialize flow to 0.
Edmond's Karp algorithm. (Long) While there exists an augmenting path:
Maximum Flow Problem: Find the path.
It deals with finding the maximum possible flow from a Determine minimum capacity
source to a sink in a flow network. Each edge has a (bottleneck).
capacity, and flow must not exceed this capacity. Augment the flow.
Ford-Fulkerson Algorithm: Update the residual capacities.
Uses residual graphs to find augmenting paths. Edmonds-Karp Algorithm:
Keeps adding flow until no more augmenting paths are A specific implementation of Ford-
[Link] flow added is the minimum capacity along Fulkerson.
the path. The algorithm works for both integer and Uses Breadth-First Search (BFS) to find
fractional capacities. the shortest augmenting path.
Time Complexity: O(VE²)
Q6: What do you know about Memoization and Tabulation:
Tabulation? Bottom-up approach.
Memoization and Tabulation are two techniques Builds the solution from base cases
used in Dynamic Programming to optimize recursive iteratively.
solutions by storing the results of subproblems. Example: Iteratively computing Fibonacci
Memoization: numbers from index 0 to n.
Top-down approach. Difference:
Uses recursion and stores results in a dictionary or Memoization uses recursive calls;
array. Tabulation avoids recursion.
Example: Fibonacci sequence using recursion with Tabulation generally has better space
cache. optimization.
Q9: List down the different types of sorting algorithms and write down their time complexity. (Long)

Algorithm Best Case Average Worst Case Space Stable

Case
Bubble Sort O(n) O(n²) O(n²) O(1) Yes

Insertion Sort O(n) O(n²) O(n²) O(1) Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Radix Sort O(nk) O(nk) O(nk) O(n+k) Yes
n = number of elements
k = number of digits in largest number (for Radix Sort)

Q10: Explain Minimum Spanning Tree (MST) with example.

A Minimum Spanning Tree (MST) is a subset of the edges in a connected, weighted graph that connects all vertices with the minimum total edge weight and no cycles.

Applications:

Network design (e.g., laying cables)

Cluster analysis

Approximation algorithms for NP-Hard problems

Algorithms to Find MST:

Kruskal’s Algorithm:

o Sort all edges by weight.

o Pick smallest edge that doesn’t form a cycle.

o Use Disjoint Set Union (DSU) to detect cycles.

Prim’s Algorithm:

o Start from any node.

o Add the smallest edge connecting visited to unvisited nodes.

o Repeat until all nodes are connected.

Example:

Vertices: A, B, C, D
Edges with weights:
A-B: 2, B-C: 3, A-C: 6, C-D: 1

MST includes edges: A-B, B-C, C-D → Total Weight = 6

1. What is a Data Structure?

Answer: ✅ c) A way to store and organize data

2. What is the disadvantage of arrays?

Answer: ✅ d) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

3. Which data structure uses LIFO (Last In First Out) principle?

Answer: ✅ a) Stack

4. Which data structure is used for function calls in most programming languages?

Answer: ✅ b) Stack

5. Which data structure is used to handle asynchronous data transfer between two processes?

Answer: ✅ a) Data Transfer between two asynchronous processes

6. Which data structure is most suitable to reverse a word or expression?

Answer: ✅ c) Stack

7. Evaluate the postfix expression: 6 3 2 4 + - *

Answer: ✅ b) -18
8. Which data structure uses the push and pop operations?

Answer: ✅ a) Stack

9. Which statement about stack is not true?

Answer: ✅ b) Stack is a FIFO (First In First Out) data structure ❌

(Correct explanation: Stack is LIFO, not FIFO)

10. Which data structure follows the FIFO (First In First Out) rule?

Answer: ✅ d) Queue

11. What is the prefix form of the infix expression: A / B - C + D * E?

Answer: ✅ a) - / A B + C * D E

12. Which statement about linked lists is false?

Answer: ✅ b) Accessing elements in linked list is faster than arrays

13. Which data structure is used for recursion in programming?

Answer: ✅ c) Stack

14. Which of the following operations cannot be implemented using a stack?

Answer: ✅ d) Allocating CPU to resources

15. What is a bit vector?

Answer: ✅ a) A data structure that compactly stores bits

16. Which of the following is a self-balancing binary search tree?

Answer: ✅ b) B-tree

17. A queue in which elements can be inserted or deleted only at one end is called?

Answer: ✅ c) Single ended queue

18. Which data structure uses the undo functionality in editors?

Answer: ✅ d) Stack

19. Which algorithm design technique is used in Merge Sort?

Answer: ✅ b) Divide and Conquer

20. What is an advantage of linked lists over arrays?

Answer: ✅ c) Effective usage of memory

Q2: Define graph traversal with example. While heap has more than one node:
Example:
Remove
Graph Traversal refers to the process of visiting two nodes
all the with the lowest frequency.
Graph:
nodes or vertices in a graph systematically. Create a new node
less with combined frequency.
Types of Traversal: Insert the new node
A into the heap.
Breadth-First Search (BFS): The remaining node
/ \ is the root of the Huffman Tree.
Traverses the graph level-by-level. Example: B C
Uses a queue data structure. Characters: A(5),| B(9), C(12), D(13), E(16), F(45)
Huffman Tree Result:
Good for finding the shortest path in unweighted D
graphs. F: 0  BFS Traversal from A: A →
Depth-First Search (DFS): C: 100 B→C→D
D:
Explores as far as possible before backtracking.101
Uses a stack (or recursion). A: 1100
 DFS Traversal from A: A →
B→D→C
Good for path finding and cycle detection. B: 1101
E: 111
Q4: Describe the working of
Huffman’s coding and elaborate its
working with the help of code
example. (Long)
Huffman Coding is a greedy algorithm
used for lossless data compression. It
assigns variable-length codes to
characters based on their frequencies
frequent characters get shorter codes.
Steps:
Calculate frequency of each character.
Create a min-heap (priority queue) of
leaf nodes.
Q5: Differentiate between Travelling Salesman Problem and Knapsack Problem.

Feature Travelling Salesman Knapsack Problem

Problem
Problem Type NP-Hard, Optimization NP-Complete, Optimization
Goal Minimum cost route Maximum value within weight limit
covering all cities
Data Representation Graph with weighted Items with weight and value
edges
Complexity Exponential Pseudo-polynomial

Real-life Application Logistics, Routing Budget allocation, Resource management

Q7: Describe Greedy Algorithm with the help of Example:

Dijkstra Algorithm and write down the two basic Graph with nodes A, B, C, D.
properties of greedy algorithm. Start at A. Choose nearest neighbor.
Greedy Algorithm: A problem-solving strategy where Continue until all nodes are visited with
the best choice is made at each step, hoping that these the shortest paths known.
choices lead to a global optimum. Two Properties of Greedy Algorithms:
Dijkstra’s Algorithm: Finds the shortest path from a 1. Greedy Choice Property:
source to all nodes in a weighted graph. At each step, it Local optimum leads to
selects the vertex with the minimum tentative distance. global optimum.
Then it relaxes the adjacent edges and updates their 2. Optimal Substructure:
distances. Optimal solution can be
built from optimal solutions
of subproblems.
Q8: Describe Dynamic Programming with its Key Features:
properties. Avoids repeated work using caching
Dynamic Programming (DP): (memoization) or tabulation.
An optimization method for solving complex Works efficiently for problems with:
problems by breaking them into simpler Overlapping Subproblems
overlapping subproblems and solving each once. Optimal Substructure
Common Problems:
Fibonacci Sequence
Knapsack Problem
Longest Common Subsequence
Matrix Chain Multiplication

Boti Raj ZindaBad

21. Which data structure is commonly used in databases and file systems for indexing?

Answer: ✅ a) B-tree

22. Which of the following is not a linear data structure?

Answer: ✅ d) Cord

23. What is the output of the reverse of the string "sanduryn"?

Answer: ✅ a) yrdnuas

24. Which tree data structure is used in search engines and database indexing?

Answer: ✅ c) 2-3 Tree

25. What is an AVL Tree?

Answer: ✅ b) A tree which is balanced and is a height-balanced binary search tree

26. What is the best case time complexity of interpolation search?

Answer: ✅ c) O(log(log M))

27. Which of the following is not required for a queue implementation?

Answer: ✅ d) Stack

28. Why are K-D Trees used?

Answer: ✅ b) To have efficient region search/query in multidimensional data

29. What is the best data structure to reverse a string?

Answer: ✅ a) Stack

30. Which operation is not performed in a singly linked list?

Answer: ✅ a) Display the list ❌ (It can be done – ambiguous question)

31. Which tree is a type of binary search tree?

Answer: ✅ d) Binary search trees

32. What is the primary benefit of arrays?

Answer: ✅ b) Faster access of data using index

33. Which data structure allows elements to be removed based on priority?

Answer: ✅ d) Priority Queue

34. What is a deque (double-ended queue)?

Answer: ✅ c) A queue with insert/delete defined for both front and rear ends

35. Which of these is a double-ended queue?

Answer: ✅ b) Dequeue

36. What are the in-degrees of the following directed graph's nodes 3 and 5?

Answer: ✅ d) 3 and 5

37. Which type of linked list has only one link per node and allows only forward traversal?

Answer: ✅ c) Singly linked list