Understanding Binary Search, Graphs, and Priority Queues
Q) How is binary search different from linear search?
| Linear Search | Binary Search |
|---|---|
| 1. Checks each element one by one from start to end. | 1. Repeatedly divides the sorted list into halves to find the element. |
| 2. Works on unsorted or sorted lists. | 2. Works only on sorted lists. |
| 3. Time complexity is O(n). | 3. Time complexity is O(log n) (much faster). |
| 4. Simple and easy to implement. | 4. Slightly more complex due to mid calculations. |
| 5. Inefficient for large datasets. | 5. Highly efficient for large datasets. |
| 6. No prerequisite of data order. | 6. Requires data to be in ascending or descending order. |
Q) What is the difference between a BST and a heap?
| Binary Search Tree (BST) | Heap |
|---|---|
| 1. Follows BST property: Left child < Root < Right child. | 1. Follows heap property: Parent is ≥ children (max-heap) or ≤ children (min-heap). |
| 2. Used mainly for fast searching. | 2. Used mainly in priority queues and Heap Sort. |
| 3. Search, insert, and delete take O(log n) in balanced BST. | 3. Search takes O(n), but insert and delete take O(log n). |
| 4. BST may become unbalanced, degrading to O(n). | 4. Heap is always a complete binary tree, so operations remain efficient. |
| 5. Inorder traversal gives sorted order. | 5. No traversal gives sorted order. Only the root is the largest/smallest. |
| 6. Node arrangement is based on key ordering. | 6. Node arrangement is based on priority, not sorting order. |
Q) What is the number of edges in a regular graph of degree d and n vertices?
In a regular graph with n vertices where each vertex has degree d:
Each vertex connects to d edges.
Since each edge is counted twice (once at each end vertex), the total number of edges E is given by:
E = n × d / 2
Q) Explain two ways to represent a graph in memory and compare their advantages.
(i) Adjacency Matrix (ii) Adjacency List
Two Ways to Represent a Graph in Memory
(i) Adjacency Matrix
An adjacency matrix is a 2D array of size n × n, where n is the number of vertices.
Each cell A[i][j] = 1 (or weight w) if there is an edge from vertex i to j, otherwise 0.
Advantages
Easy to implement and simple to understand.
Checking whether an edge exists between two nodes takes O(1) time.
Suitable for dense graphs (large number of edges).
Works well for graph algorithms like Floyd–Warshall.
(ii) Adjacency List
In an adjacency list, each vertex stores a list of all its adjacent (connected) vertices.
Uses linked lists or dynamic lists.
Advantages
Space efficient for sparse graphs (few edges). Uses O(V + E) space.
Easy to traverse all neighbors of a node.
Faster and more memory-efficient for large graphs.
Good for algorithms like DFS and BFS.
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space Required | O(V²) | O(V + E) |
| Edge Lookup Time | O(1) | O(k) where k = degree of vertex |
| Suitable For | Dense graphs | Sparse graphs |
| Memory Usage | High | Low |
| Implementation | Simple | Less simple |
| Adding/Deleting Edges | O(1) | O(1) (if using linked list) |
| Graph Traversal | Slower | Faster |
Q) Explain the DFS algorithm with an example. Which data structure is used for DFS and BFS?
Depth First Search (DFS) is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. It explores one path deeply before moving to others until all vertices are visited.
DFS Algorithm (using stack):
Start from a source vertex and mark it as visited.
Push the source vertex onto a stack.
While the stack is not empty:
Peek at the top vertex in the stack.
Find an unvisited adjacent vertex.
If found, mark it visited and push onto the stack.
If none found, pop the top vertex from the stack (backtrack).
Repeat until all reachable vertices are visited.
Example:
Consider a graph with vertices A, B, C, D and edges (A−B), (A−C), (B−D), (C−D):
Start at A, mark visited, push A.
Move to adjacent unvisited B, mark visited, push B.
From B, move to D, mark visited, push D.
D has no unvisited neighbors, pop D.
Backtrack to B, no other unvisited neighbors, pop B.
Back to A, move to adjacent unvisited C, mark visited, push C.
From C, all neighbors visited, pop C.
Stack empty, traversal ends.
Traversal Order: A→B→D→C.
Data Structures Used:
DFS: Uses a stack (either explicitly or via recursion call stack).
BFS (Breadth First Search): Uses a queue to explore neighbors level by level.
This data structure choice influences the order of vertex exploration and traversal behavior. DFS explores depth-wise using a stack, whereas BFS explores breadth-wise using a queue.
Q) Explain the following graph terminology with examples. (AKTU 2024-25)
(i) Graph (ii) Weighted Graph (iii) Degree of a vertex (iv) Cycle in a graph
Here is a complete, exam-ready answer for all graph terminologies with simple examples (perfect for AKTU 2024–25):
(i) Graph
A graph is a collection of vertices (nodes) and edges (links) connecting pairs of vertices.
It is represented as G = (V, E), where V = vertices, E = edges.
Example:
Vertices = {A, B, C},
Edges = {(A, B), (B, C)}
A ― B ― C(ii) Weighted Graph
A weighted graph is a graph in which each edge has a weight or cost, such as distance, time, or capacity.
Example:
A --5-- B
| |
3 2
| |
C --4-- DWeights = {5, 3, 2, 4}
(iii) Degree of a Vertex
The degree of a vertex is the number of edges incident (connected) to it.
Example:
A
/ \
B CDegree(A) = 2
Degree(B) = 1
Degree(C) = 1
(iv) Cycle in a Graph
A cycle is a path that starts and ends at the same vertex, with no repeated edges or vertices (except the starting point).
Example:
A ― B
| |
D ― CA → B → C → D → A forms a cycle.
(v) Connected and Disconnected Graph
Connected Graph:
A graph is connected if every vertex is reachable from every other vertex.
A ― B ― CAll vertices are connected → Connected Graph
Disconnected Graph:
A graph where some vertices are not reachable from others.
A ― B C ― DTwo separate components → Disconnected Graph
(vi) Directed and Undirected Graph
Undirected Graph:
Edges have no direction.
A ― BMeans: A connected to B in both directions.
Directed Graph (Digraph):
Edges have direction represented by arrows.
A → B → CMeans: You can go from A to B, but not from B to A unless an arrow exists.
(vii) MST (Minimum Spanning Tree)
A Minimum Spanning Tree is a subgraph of a connected weighted graph that:
Connects all vertices,
With no cycles,
And minimum total edge weight.
Example:
For a graph with edges:
A-B(4), B-C(2), A-C(5)
The MST will choose the minimum edges that connect all vertices:
A ― B ― C(4) (2)Total cost = 6 (minimum possible)
Short Exam Summary
| Term | Meaning |
|---|---|
| Graph | Set of vertices and edges |
| Weighted Graph | Graph with edge weights |
| Degree | Number of edges connected to a vertex |
| Cycle | Closed loop path |
| Connected Graph | All vertices reachable |
| Disconnected Graph | Not all vertices reachable |
| Directed/Undirected Graph | Arrows or no arrows on edges |
| MST | Minimum-cost tree connecting all vertices |
Q) Write an algorithm to obtain connected components of a graph
Here is a simple algorithm to find the connected components of an undirected graph using Depth First Search (DFS):
Algorithm to Find Connected Components
1. Initialize a visited array to keep track of visited vertices, set all to false.
2. Initialize component count to 0.
3. For each vertex v in the graph:
* If v is not visited:
* Increment component count
* Call DFS starting from v to visit all vertices reachable from v.
* Mark all visited vertices in this DFS as part of the current component.
4. Repeat until all vertices are visited.
5. The number of times DFS is called gives the number of connected components.
Q) Write an algorithm for Breadth First Search (BFS) traversal of a graph
BFS Algorithm
1. Start from the chosen source vertex, mark it as visited.
2. Initialize an empty queue and enqueue the source vertex.
3. While the queue is not empty:
* Dequeue a vertex v from the front of the queue.
* Visit the dequeued vertex v.
* For each adjacent vertex u of v:
* If u is not visited, mark it as visited and enqueue it.
4. Repeat step 3 until the queue is empty.
Explanation:
BFS explores the graph level by level, visiting all neighbors of a vertex before moving to the next level.
It uses a queue to track the order in which vertices are visited, ensuring vertices closest to the source are processed first.
Q) Write different representations of a graph in memory
Adjacency Matrix:
Uses a 2D matrix of size n × n (where n is the number of vertices).
The entry at [i][j] is 1 (or the edge weight) if there is an edge from vertex i to vertex j; otherwise 0.
Suitable for dense graphs but uses O(n²) space.
Adjacency List:
Uses an array or list of lists. Each vertex stores a list of its adjacent vertices.
Space efficient for sparse graphs as only existing edges are stored.
Allows easy iteration over neighbors.
Edge List:
Stores all edges as a list of pairs (or triples if weighted) (u,v) representing an edge between u and v.
Simple but not efficient for adjacency queries.
Each representation suits different scenarios based on graph density, memory usage, and required operations like edge lookup or neighbor traversal.
Q) Define transitive closure in a graph
The transitive closure of a directed graph is a graph that shows which vertices are reachable from every other vertex.
If there exists a path (direct or indirect) from vertex u to v, then the transitive closure contains an edge from u → v.
Q) Compare Adjacency Matrix and Adjacency List Representation of a Graph
| Adjacency Matrix | Adjacency List |
|---|---|
| Uses a V × V matrix to store edges. | Uses a list of neighbors for each vertex. |
| Requires O(V²) space even if few edges. | Requires only O(V + E) space (more efficient for sparse graphs). |
| Checking if an edge exists is O(1). | Checking an edge may take O(k), where k = degree of vertex. |
| Good for dense graphs. | Good for sparse graphs. |
| Simple to implement. | Slightly more complex. |
Q) What is a Minimum Spanning Tree? Give its applications.
A Minimum Spanning Tree is a subgraph of a connected weighted graph that connects all the vertices with the minimum total edge weight and contains no cycles.
It uses exactly (V – 1) edges for V vertices.
Applications of MST
Network Design: Designing least-cost networks like telephone lines, electrical grids, computer networks.
Transportation Systems: Finding shortest routes for roads, pipelines, railways.
Clustering in Machine Learning: Used in hierarchical clustering algorithms.
Approximation Algorithms: Basis for algorithms like Traveling Salesman Problem approximation.
Q) What do you mean by a priority queue? Explain all its types with suitable examples. What are the applications of a priority queue?
Priority Queue
A priority queue is a special type of queue in which each element is assigned a priority, and deletion always removes the element with the highest (or lowest) priority, not the one that arrived first.
It is an abstract data type commonly implemented using heaps.
Types of Priority Queue
1. Max Priority Queue
In this type, the element with the highest priority (maximum value) is removed first.
Example:
Insert: 10, 30, 20 → Queue becomes: {30, 20, 10}
Delete → 30
2. Min Priority Queue
The element with the lowest priority (minimum value) is removed first.
Example:
Insert: 40, 15, 25 → Queue becomes: {15, 25, 40}
Delete → 15
3. Ascending Priority Queue
Elements are arranged in increasing order, minimum element removed first.
Same as min-priority queue.
4. Descending Priority Queue
Elements are arranged in decreasing order, maximum element removed first.
Same as max-priority queue.
5. Double-Ended Priority Queue (DEPQ)
Allows deletion of both minimum and maximum elements.
Can remove highest or lowest priority element.
Example:
Queue: {10, 25, 40}
Delete-min → 10
Delete-max → 40
Applications of Priority Queue
CPU Scheduling
Processes with higher priority are executed first.
Dijkstra’s Shortest Path Algorithm
Uses a min-priority queue to pick the next minimum distance vertex.
Prim’s Minimum Spanning Tree Algorithm
Job Scheduling in Operating Systems
Event Simulation Systems
Events processed based on time priority.
Data Compression (Huffman Coding)
Uses priority queue to always pick smallest frequency nodes.
Load Balancing and Bandwidth Management