MODULE-1
1. Explain any one Efficient sorting technique in detail.
A/Merge Sort (Efficient Sorting Technique)
Definition
Merge Sort is a divide-and-conquer algorithm that recursively divides the array into smaller subarrays,
sorts them, and then merges them back to produce a sorted array.
Working Principle
1. Divide the array into two halves.
2. Recursively sort both halves.
3. Merge the sorted halves into a single sorted array.
Algorithm Steps
If the array has only one element → already sorted.
Otherwise:
o Find the middle index.
o Split the array into left and right subarrays.
o Apply Merge Sort on both halves.
o Merge the two sorted halves.
Pseudo Code
MergeSort(A, low, high):
if low < high:
mid = (low + high) / 2
MergeSort(A, low, mid)
MergeSort(A, mid+1, high)
Merge(A, low, mid, high)
Merge(A, low, mid, high):
create temporary arrays
compare elements from both halves
copy smaller element into original array
repeat until all elements are merged
Time and Space Complexity
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Space Complexity: O(n) (extra space required)
Advantages
Stable sorting algorithm.
Works efficiently for large datasets.
Predictable time complexity.
Disadvantages
Requires extra memory.
Not suitable for very small datasets compared to simpler algorithms.
2. Discuss about graph and Adjacency matrix.
A/Graph and Adjacency Matrix
Graph – Definition
A graph is a non-linear data structure used to represent relationships between objects. It consists of:
Vertices (V): Nodes or points
Edges (E): Connections between vertices
A graph is represented as G = (V, E).
Types of Graphs
Undirected Graph: Edges have no direction
Directed Graph (Digraph): Edges have direction
Weighted Graph: Edges have weights (costs)
Unweighted Graph: Edges have no weights
Adjacency Matrix – Definition
An Adjacency Matrix is a way of representing a graph using a 2D array (matrix) of size V × V.
If there is an edge between vertex i and j, then:
o Matrix[i][j] = 1 (or weight of edge)
Otherwise:
o Matrix[i][j] = 0
Example
For a graph with 3 vertices:
1—2
\ |
3
Adjacency Matrix:
123
1 [0 1 1]
2 [1 0 1]
3 [1 1 0]
Properties
For undirected graphs, the matrix is symmetric.
For directed graphs, the matrix may not be symmetric.
Diagonal elements are usually 0 (no self-loops).
Advantages
Simple and easy to implement
Efficient to check if an edge exists → O(1) time
Useful for dense graphs
Disadvantages
Requires O(V²) space even if few edges exist
Not efficient for sparse graphs
3. Explain Dijkstra’s algorithm and write time complexity.
A/Dijkstra’s Algorithm
Definition
Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a source vertex to all other
vertices in a weighted graph with non-negative edge weights.
Working Principle
Start from a source node.
Assign:
o Distance = 0 for source
o Distance = ∞ (infinity) for all other vertices
Repeatedly select the vertex with the minimum distance and update its neighbors.
Algorithm Steps
1. Initialize distance of source = 0, others = ∞
2. Mark all vertices as unvisited
3. Select the unvisited vertex with the smallest distance
4. Update distances of its adjacent vertices:
o If new distance < current distance, update it
5. Mark the current vertex as visited
6. Repeat until all vertices are visited
Pseudo Code
Initialize dist[source] = 0
For all other vertices dist[v] = ∞
While there are unvisited vertices:
u = vertex with minimum distance
Mark u as visited
For each neighbor v of u:
if dist[u] + weight(u,v) < dist[v]:
dist[v] = dist[u] + weight(u,v)
Time Complexity
Using Adjacency Matrix: O(V²)
Using Min Priority Queue (Heap):
o O((V + E) log V)
Advantages
Efficient for shortest path problems
Works well for graphs with non-negative weights
Limitations
Does not work with negative edge weights
Can be slower for very large graphs without optimization
4. Explain Dijkstra’s algorithm with example and write disadvantages of it.
A/Dijkstra’s Algorithm with Example
Definition
Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a source vertex to all other
vertices in a weighted graph with non-negative edge weights.
Working Steps
1. Initialize distance of source = 0, others = ∞
2. Select the vertex with minimum distance
3. Update distances of adjacent vertices
4. Mark the vertex as visited
5. Repeat until all vertices are visited
Example
7
Consider graph with vertices: A, B, C, D
Edges:
A→B=1
A→C=4
B→C=2
B→D=5
C→D=1
Step-by-Step Solution (Source = A)
Vertex Distance
A 0
B 1
C 3
D 4
Explanation:
From A → B = 1
A → B → C = 1 + 2 = 3 (better than 4)
A→B→C→D=3+1=4
Disadvantages
Does not work with negative edge weights
Cannot detect negative cycles
May be inefficient for very large graphs without using advanced data structures
Requires more memory in some implementations
5. Describe shortest path by using BFS.
A/Shortest Path using BFS (Breadth-First Search)
Definition
Breadth-First Search (BFS) is a graph traversal algorithm used to find the shortest path in an unweighted
graph (or graph with equal edge weights).
Working Principle
BFS explores the graph level by level starting from the source node.
It uses a queue (FIFO) data structure.
The first time a node is reached, the path used is the shortest path.
Algorithm Steps
1. Initialize:
o Mark all vertices as unvisited
o Set distance of source = 0
2. Insert source into queue and mark it visited
3. While queue is not empty:
o Remove a vertex u from queue
o For each adjacent vertex v:
If v is not visited:
Mark it visited
Set distance[v] = distance[u] + 1
Insert v into queue
Pseudo Code
BFS(G, source):
create queue Q
mark source as visited
distance[source] = 0
enqueue(source)
while Q is not empty:
u = dequeue(Q)
for each neighbor v of u:
if v is not visited:
mark v visited
distance[v] = distance[u] + 1
enqueue(v)
Example
5
Graph:
A connected to B and C
B connected to D
C connected to D
Shortest path from A to D:
A → B → D (2 steps)
A → C → D (2 steps)
(BFS finds one of the shortest paths)
Time Complexity
O(V + E)
Where V = vertices, E = edges
Advantages
Finds shortest path in unweighted graphs
Simple and efficient
Uses queue for systematic traversal
Limitations
Not suitable for weighted graphs
Requires memory for storing queue
6. List and Explain Amortized Analysis.
A/Amortized Analysis
Definition
Amortized Analysis is a technique used in algorithm analysis to determine the average cost per operation
over a sequence of operations, rather than analyzing a single worst-case operation.
It ensures that even if some operations are expensive, the overall average cost remains small.
Need for Amortized Analysis
Some operations are occasionally costly but occur rarely
Helps in understanding the true performance over time
Commonly used in data structures like stacks, dynamic arrays, etc.
Methods of Amortized Analysis
1. Aggregate Method
Total cost of all operations is calculated
Average cost = Total cost / Number of operations
Example:
In a stack, push = O(1), pop = O(1)
For n operations → Total cost = O(n)
So, amortized cost per operation = O(1)
2. Accounting Method (Banker’s Method)
Assign an artificial cost to operations
Some operations are charged extra to pay for future expensive operations
Idea:
Cheap operations store “credits”
Expensive operations use those credits
3. Potential Method
Uses a potential function (Φ) to measure stored work
Amortized cost = Actual cost + Change in potential
Formula:
Amortized Cost=Actual Cost +Φ(new)−Φ (old)
Advantages
Gives a more accurate performance measure
Useful for analyzing complex data structures
Avoids misleading worst-case analysis
7. List out Time and Space Complexity Comparison Table:
A/Time and Space Complexity Comparison Table
Definition
Time complexity represents the execution time of an algorithm, while space complexity represents the
memory usage required during execution.
Comparison Table
Algorithm Best Time Average Time Worst Time Space Complexity
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Algorithm Best Time Average Time Worst Time Space Complexity
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)
Heap Sort O(n log n) O(n log n) O(n log n) O(1)
Linear Search O(1) O(n) O(n) O(1)
Binary Search O(1) O(log n) O(log n) O(1)
Key Observations
Efficient algorithms: Merge Sort, Quick Sort, Heap Sort → O(n log n)
Simple but slow algorithms: Bubble, Selection, Insertion → O(n²)
Searching efficiency:
o Linear Search → O(n)
o Binary Search → O(log n) (requires sorted data)