Set 01

1 b i]. Write an algorithm to find the sum of n

numbers and analyze its time and space
complexity. (8 Marks)
Algorithm: Sum of n Numbers

Step 1: Start

Step 2: Read n

Step 3: Initialize sum ← 0

Step 4: Repeat for i = 1 to n

a. Read number

b. sum ← sum + number

Step 5: Display sum

Step 6: Stop

Time Complexity Analysis

 The loop executes n times.

 Each iteration performs one addition operation.

Therefore,

Time Complexity = O(n)

Space Complexity Analysis

 Only variables sum, i, and num are used.

 No extra memory depends on n.

Therefore,

Space Complexity = O(1)

2 b ii]. Algorithm to check whether all
elements in an array are distinct. Find Worst
Case Complexity. (7 Marks)
Given Array
A = {91, 65, 72, 31, 45, 61, 2, 8, 9, 25, 60, 17, 10}

Algorithm

Step 1: Start

Step 2: Read array A of size n

Step 3: Compare each element with all remaining elements

Step 4: If any two elements are equal

Print "Not Distinct"

Stop

Step 5: If no duplicates are found

Print "All elements are Distinct"

Step 6: Stop

Checking the Given Array

91, 65, 72, 31, 45, 61, 2, 8, 9, 25, 60, 17, 10

All elements are different.

Result: All elements are Distinct.

Worst Case Complexity

Worst case occurs when:

 All elements are distinct.

  Every comparison must be performed.

Number of comparisons:

n(n-1)/2

Therefore,

Worst Case Time Complexity = O(n²)

Space Complexity

Only variables i and j are used.

Space Complexity = O(1)

2 b]Radix Sort Algorithm [15m]

Definition

Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting
from the least significant digit (LSD) to the most significant digit (MSD).

It uses Counting Sort as a subroutine for sorting each digit.

Given Array
170, 45, 75, 90, 802, 24, 2, 66

Pass 1: Sort according to Unit's Digit (1's

place)
Number Unit Digit
170 0
45 5
75 5
Number Unit Digit
90 0
802 2
24 4
2 2
66 6

After sorting:

170, 90, 802, 2, 24, 45, 75, 66

Pass 2: Sort according to Ten's Digit (10's

place)
Number Ten Digit
170 7
90 9
802 0
2 0
24 2
45 4
75 7
66 6

After sorting:

802, 2, 24, 45, 66, 170, 75, 90

Pass 3: Sort according to Hundred's Digit

(100's place)
Number Hundred Digit
802 8
2 0
24 0
45 0
66 0
170 1
75 0
Number Hundred Digit
90 0

After sorting:

2, 24, 45, 66, 75, 90, 170, 802

Final Sorted Array

2, 24, 45, 66, 75, 90, 170, 802

Algorithm
RADIX_SORT(A,n)

1. Find maximum element in array

2. For exp = 1 while max/exp > 0
Apply Counting Sort on digit at exp
exp = exp × 10
3. Return sorted array

Time Complexity Analysis

Let,

 n = Number of elements
 d = Number of digits in largest number

For each digit, Counting Sort takes O(n).

Therefore,

Time Complexity = O(d × n)

Best Case
O(dn)

Average Case
O(dn)

Worst Case
O(dn)
Space Complexity
Radix Sort requires an output array.

Space Complexity = O(n + k)

where

k = range of digits (0–9)

Hence,

Space Complexity = O(n)

Advantages
1. Faster for large integers.
2. Stable sorting algorithm.
3. Does not compare elements directly.
4. Efficient when number of digits is small.

Disadvantages
1. Extra memory is required.
2. Not suitable for floating-point numbers.
3. Performance depends on number of digits.

Conclusion
Radix Sort sorts the given array by processing digits from least significant digit to most
significant digit. The final sorted array is:

2, 24, 45, 66, 75, 90, 170, 802

Time Complexity = O(dn)

Space Complexity = O(n) ✅

3 A i]Explain Strassen's Matrix Multiplication with Example (7 Marks)

Definition
Strassen's Algorithm is a Divide and Conquer algorithm used for matrix multiplication.

Normal matrix multiplication requires 8 multiplications for a 2×2 matrix.

Strassen's algorithm reduces it to 7 multiplications, making it faster for large matrices.

Given Matrices

Let MATRIX A=[ 1 2 ] MATRIX B =[ 5 6 ]

[34] [78]

a=1 , b=2
c=3 , d=4

e=5 , f=6
g=7 , h=8

Compute 7 Products
P1 = a(f-h) = 1(6-8) = -2
P2 = (a+b)h = (1+2)8 = 24
P3 = (c+d)e = (3+4)5 = 35
P4 = d(g-e) = 4(7-5) = 8
P5 = (a+d)(e+h) = (1+4)(5+8)=65
P6 = (b-d)(g+h) = (2-4)(7+8)=-30
P7 = (a-c)(e+f) = (1-3)(5+6)=-22

Calculate Result Matrix

C11 = P5 + P4 - P2 + P6
= 65+8-24-30
= 19

C12 = P1 + P2
= -2+24
= 22

C21 = P3 + P4
= 35+8
= 43

C22 = P1 + P5 - P3 - P7
= -2+65-35+22
= 50

Final Matrix

C=[ 19 22]

[ 43 50]
Time Complexity

Normal Matrix Multiplication:

O(n³)

Strassen's Algorithm:

O(n^2.81)

Advantages

1. Faster than normal multiplication.

2. Uses only 7 multiplications.
3. Efficient for large matrices.

A ii) Prim's Algorithm (8 Marks)

4 a i]Breadth First Search (BFS) [5mrk]

Definition

Breadth First Search (BFS) is a graph traversal algorithm that visits all vertices level by level
starting from a source vertex. It uses a Queue (FIFO) data structure.

Algorithm
BFS(G, S)

1. Create an empty Queue Q

2. Mark source vertex S as visited
3. Enqueue S into Q

4. While Q is not empty do

a. Dequeue a vertex u from Q
b. Visit u
c. For each adjacent vertex v of u
If v is not visited then
Mark v as visited
Enqueue v into Q
End If
End While

5. Stop
Example
Consider the graph:

A
/ \
B C
/ \ / \
D E F G

BFS Traversal

Start vertex = A

Visit A
Queue = [B, C]

Visit B
Queue = [C, D, E]

Visit C
Queue = [D, E, F, G]

Visit D → E → F → G

Final BFS Order

A → B → C → D → E → F → G

Complexity
Time Complexity: O(V + E)

Space Complexity: O(V)

where:

 V = Number of Vertices
 E = Number of Edges

Set 02:
1 a i] Illustrate in detail about Asymptotic
Notations and Basic Efficiency Classes of
Algorithm (9 Marks)
Asymptotic Notations

Asymptotic Notations are used to describe the performance of an algorithm when the input size
(n) becomes very large.

They help compare algorithms based on their growth rate.

1. Big O Notation - O

Definition

Big O notation represents the upper bound (Worst Case) of an algorithm.

It indicates the maximum time required by an algorithm.

Example
T(n) = 3n² + 2n + 1

Ignoring constants and lower-order terms:

O(n²)

Example Algorithms

 Linear Search → O(n)

 Bubble Sort → O(n²)
 Binary Search → O(log n)

2. Omega Notation - Ω

Definition

Omega notation represents the lower bound (Best Case) of an algorithm.

It indicates the minimum time required.

Example
T(n) = 3n² + 2n + 1
Ω(n²)

3. Theta Notation - Θ

Definition

Theta notation represents the exact bound of an algorithm.

It gives both upper and lower bounds.

Example
T(n) = 3n² + 2n + 1
Θ(n²)
Diagram
Ω(n)
|
|
Θ(n)
|
|
O(n)

 O → Upper Bound
 Ω → Lower Bound
 Θ → Tight Bound

Basic Efficiency Classes of Algorithms

Complexity Name

O(1) Constant

O(log n) Logarithmic

O(n) Linear

O(n log n) Linearithmic

O(n²) Quadratic

O(n³) Cubic

O(2ⁿ) Exponential
 Complexity Name

O(n!) Factorial

Examples

Constant Time
O(1)

Example:

x = a + b;

Logarithmic Time
O(log n)

Example:

Binary Search

Linear Time
O(n)

Example:

Linear Search

Quadratic Time
O(n²)

Example:

Bubble Sort
Selection Sort

Exponential Time
O(2ⁿ)
Conclusion
Asymptotic notations are used to measure algorithm efficiency. The three main notations are Big
O, Omega, and Theta.

O (Big O) → Worst Case

Ω (Omega) → Best Case

Θ (Theta) → Average/Exact Case

A ii) Element Uniqueness Problem –

Algorithm (Word Format)
Algorithm

Step 1: Start

Step 2: Read the array A containing n elements.

Step 3: Set i = 0.

Step 4: Compare each element with all the remaining elements in the array.

Step 5: If any two elements are equal, display "Elements are not distinct" and stop.

Step 6: If no duplicate element is found after all comparisons, display "All elements are
distinct".

Step 7: Stop.

Example
Array:

A = [10, 20, 30, 40, 50]

Comparisons:

10 with 20,30,40,50
20 with 30,40,50
30 with 40,50
40 with 50

No duplicate found.

Result: All Elements are Distinct.

2 b]Counting Sort Algorithm [15mrk]

Definition

Counting Sort is a non-comparison sorting algorithm used when the input elements are
integers within a limited range.

Instead of comparing elements, it counts the number of occurrences of each element.

Given Array
A = [7, 4, 1, 3, 4, 1, 2]

Step 1: Find Maximum Element

Maximum Element = 7

Create a count array from 0 to 7.

Count = [0,0,0,0,0,0,0,0]
Index = 0 1 2 3 4 5 6 7

Step 2: Count Occurrences

Array:

7, 4, 1, 3, 4, 1, 2

Count frequency of each element.

Element Frequency

0 0

1 2

2 1
 Element Frequency

3 1

4 2

5 0

6 0

7 1

Count Array:

Index : 0 1 2 3 4 5 6 7
Count : 0 2 1 1 2 0 0 1
Step 3: Construct Sorted Array

Write each element according to its frequency.

1 occurs 2 times → 1 1
2 occurs 1 time → 2
3 occurs 1 time → 3
4 occurs 2 times → 4 4
7 occurs 1 time → 7

Final Sorted Array

[1, 1, 2, 3, 4, 4, 7]

Algorithm (Word Format)

Step 1

Start.

Step 2

Read the array elements.

Step 3

Find the maximum element in the array.

Step 4
Create a count array of size (maximum element + 1) and initialize all values to zero.

Step 5

Count the occurrence of each element and store it in the count array.

Step 6

Traverse the count array and place elements into the output array according to their frequencies.

Step 7

Display the sorted array.

Step 8

Stop.

Pseudocode
COUNTING_SORT(A)

1. Find maximum element max

2. Create Count[0...max] and initialize to 0

3. For each element x in A

Count[x]++

4. For i = 0 to max
While Count[i] > 0
Print i
Count[i]--

Time Complexity Analysis

Let:

n = Number of elements
k = Maximum element

Counting Frequencies
O(n)

Traversing Count Array

O(k)

Total Time Complexity

O(n + k)

Space Complexity
Additional count array is required.

Space Complexity = O(k)

Advantages
1. Faster than comparison-based sorting for small ranges.
2. Stable sorting algorithm.
3. Simple to implement.
4. Works efficiently for integers.

Disadvantages
1. Requires extra memory.
2. Not suitable when the range of values is very large.
3. Works mainly for integer keys.

Conclusion
Counting Sort sorts the array by counting the frequency of each element. For the given array:

Original Array : [7, 4, 1, 3, 4, 1, 2]

Sorted Array : [1, 1, 2, 3, 4, 4, 7]

Final Complexity
Time Complexity = O(n + k)

Space Complexity = O(k)

3 b]N-Queen Problem using Backtracking

[15 mrk]
Definition

The N-Queen problem is to place N queens on an N × N chessboard such that:

 No two queens are in the same row.

 No two queens are in the same column.
 No two queens are in the same diagonal.

Backtracking is used to find a valid arrangement of queens.

Why Backtracking?
Suppose we place a queen.

If later we find that another queen cannot be placed safely,

👉 We remove the previously placed queen.

👉 Try another position.

This process is called Backtracking.

Algorithm (Word Format)

Step 1

Start from the first column.

Step 2

Place a queen in a safe row.

Step 3

Move to the next column.

Step 4

Check whether the queen can be placed safely.

Step 5

If safe, place the queen and move to the next column.

Step 6

If no safe position exists, remove the previous queen and try another row.

Step 7

Repeat until all queens are placed.

Step 8

Display the solution.

Example: 4-Queen Problem

Place 4 queens on a 4 × 4 chessboard.

4 a]Breadth First Search (BFS) and Depth

First Search (DFS) [15 mrk]
Introduction

Graph traversal means visiting all vertices (nodes) of a graph.

The two important graph traversal algorithms are:

1. Breadth First Search (BFS)

2. Depth First Search (DFS)

1. Breadth First Search (BFS)

Definition

Breadth First Search (BFS) is a graph traversal algorithm that visits vertices level by level.

It uses a Queue (FIFO) data structure.

BFS Algorithm

Step 1
Start from the source vertex.

Step 2

Mark the source vertex as visited.

Step 3

Insert the source vertex into the queue.

Step 4

Remove a vertex from the queue.

Step 5

Visit all its unvisited adjacent vertices.

Step 6

Add those vertices to the queue.

Step 7

Repeat until the queue becomes empty.

Step 8

Stop.

Example

Graph:

A
/ \
B C
/ \ / \
D E F G

BFS Traversal

Start Vertex = A

Visit A
Queue = [B,C]

Visit B

Queue = [C,D,E]

Visit C

Queue = [D,E,F,G]

Visit D → E → F → G

BFS Order
A → B → C → D → E → F → G
Time Complexity
O(V + E)

where

V = Vertices
E = Edges
Space Complexity
O(V)

Advantages of BFS
1. Finds shortest path in an unweighted graph.
2. Simple to implement.
3. Visits vertices level by level.

2. Depth First Search (DFS)

Definition

Depth First Search (DFS) is a graph traversal algorithm that explores a path as deep as possible
before backtracking.

It uses a Stack (or recursion).

DFS Algorithm

Step 1

Start from the source vertex.

Step 2

Mark it as visited.

Step 3

Visit an unvisited adjacent vertex.

Step 4

Continue moving deeper until no unvisited vertex remains.

Step 5

Backtrack to the previous vertex.

Step 6

Repeat until all vertices are visited.

Step 7

Stop.

Example

Graph:

A
/ \
B C
/ \ / \
D E F G

DFS Traversal

Start Vertex = A

A → B → D

D has no child.

Backtrack to B.

A → B → E
Backtrack to A.

A → C → F → G

DFS Order
A → B → D → E → C → F → G

Time Complexity
O(V + E)
Space Complexity
O(V)

Advantages of DFS
1. Requires less memory than BFS in many cases.
2. Useful for cycle detection.
3. Used in topological sorting.
4. Suitable for maze and puzzle solving.

Difference Between BFS and DFS

BFS DFS

Uses Queue Uses Stack

Visits level by level Visits depth by depth

Finds shortest path Does not guarantee shortest path

More memory required Less memory required

FIFO LIFO

20 marks
Set 1]i) Define P, NP and NP-Complete
Problems and derive the relationship between
them (10 Marks)
Introduction

In Computational Complexity Theory, problems are classified based on the time required to
solve them.

The main classes are:

1. P Problems
2. NP Problems
3. NP-Complete Problems

1. P Problems
Definition

P (Polynomial Time) problems are problems that can be solved efficiently by an algorithm in
polynomial time.

Examples:

 Linear Search
 Binary Search
 Merge Sort
 Breadth First Search (BFS)

Complexity
O(n)
O(n²)
O(n³)

These are polynomial-time complexities.

2. NP Problems
Definition

NP (Non-deterministic Polynomial Time) problems are problems whose solutions can be verified
in polynomial time.

Finding the solution may be difficult, but checking the solution is easy.

Example

Suppose someone gives a route for a Travelling Salesman Problem.

Finding the best route is difficult.

Checking whether the route cost is correct is easy.

Therefore it belongs to NP.

3. NP-Complete Problems
Definition

NP-Complete problems are the hardest problems in NP.

A problem is NP-Complete if:

1. It belongs to NP.
2. Every NP problem can be reduced to it in polynomial time.

Examples

 Travelling Salesman Problem (decision version)

 N-Queen Problem
 Hamiltonian Cycle Problem
 Vertex Cover Problem
 Graph Coloring Problem
Relationship Between P, NP and NP-
Complete
+--------------------------------+
| NP |
| |
| +-----------+ |
| | P | |
| +-----------+ |
| |
| +-----------+ |
| | NP-Complete| |
| +-----------+ |
+--------------------------------+

Explanation

 All P problems are also NP problems.

 NP problems may or may not be solved efficiently.
 NP-Complete problems are the most difficult problems in NP.
 If one NP-Complete problem is solved in polynomial time, then all NP problems can be solved in
polynomial time.

Conclusion
P problems are easy to solve, NP problems are easy to verify, and NP-Complete problems are the
hardest problems within NP.

ii) Describe how efficient algorithms are used

in applications like Google Maps and
computer network routing (10 Marks)
Introduction

Efficient algorithms help solve real-world problems quickly and accurately.

Two important applications are:

 1. Google Maps
2. Computer Network Routing

1. Google Maps
Google Maps uses graph algorithms to find the shortest and fastest route between locations.

How it Works

 Locations are represented as vertices (nodes).

 Roads are represented as edges.
 Distance and travel time are edge weights.

Algorithms Used

Dijkstra's Algorithm

Finds the shortest path from one location to another.

Example:

Home → College

Google Maps calculates the minimum distance route.

A* Algorithm

An improved shortest path algorithm.

Uses destination information to reach the target faster.

Benefits

 Fast route calculation

 Reduced travel time
 Real-time navigation
 Traffic-aware routing

Example
Home ----5km---- School
\ /
\ /
8km 3km
 \ /
College

Google Maps selects the shortest route automatically.

2. Computer Network Routing

Network routing is the process of sending data packets from source to destination.

Routers use efficient algorithms to determine the best path.

Algorithms Used

Dijkstra's Algorithm

Used in routing protocols such as OSPF.

Finds the shortest path between routers.

Bellman-Ford Algorithm

Used in routing protocols such as RIP.

Calculates shortest paths even when network conditions change.

Example
Router A ---- Router B ---- Router C
\ /
\------Router D----/

The routing algorithm selects the path with minimum cost and delay.

Benefits of Efficient Routing Algorithms

1. Faster packet delivery.
2. Reduced network congestion.
3. Better bandwidth utilization.
4. Improved network performance.
5. Reliable communication.
Comparison
Application Algorithms Used Purpose

Google Maps Dijkstra, A* Shortest/Fastest Route

Network Routing Dijkstra, Bellman-Ford Best Path for Data Packets

Conclusion
Efficient algorithms play a vital role in real-world applications. Google Maps uses shortest-path
algorithms to provide optimal routes, while computer networks use routing algorithms to transfer
data efficiently and reliably.

Format 2 20 mrk i. Approximation Algorithms for NP-Hard Problems

(10 Marks)

Introduction

Many optimization problems such as the Traveling Salesman Problem (TSP), Vertex Cover, Set
Cover, and Knapsack are NP-hard. Since finding an exact optimal solution requires exponential
time in the worst case, approximation algorithms are used to obtain near-optimal solutions in
polynomial time.

Definition

An approximation algorithm is a polynomial-time algorithm that produces a solution close to the

optimal solution.

If:

 OPT = Optimal solution value

 A = Approximate solution value

Then the approximation ratio (ρ) is:

 For minimization problems: ρ = A / OPT

 For maximization problems: ρ = OPT / A
A smaller approximation ratio indicates a better algorithm.

Characteristics

1. Runs in polynomial time.

2. Produces near-optimal solutions.
3. Provides a guaranteed bound on solution quality.
4. Useful for large-scale optimization problems.

Common Approximation Algorithms

1. Vertex Cover (2-Approximation)

 Repeatedly select an uncovered edge.

 Add both endpoints to the cover.
 Remove all covered edges.
 Continue until no edges remain.

Performance Guarantee: Solution size ≤ 2 × Optimal solution.

2. Traveling Salesman Problem (Metric TSP)

 Construct a Minimum Spanning Tree (MST).

 Perform preorder traversal.
 Generate a Hamiltonian cycle.

Approximation Ratio: 2.

3. Set Cover Problem

 Greedily choose the set covering the maximum number of uncovered elements.

Approximation Ratio: ln(n), where n is the number of elements.

4. Knapsack Problem

 Use a greedy strategy based on profit-to-weight ratio.

 Produces near-optimal solutions efficiently.

Advantages

 Fast execution.
 Suitable for large datasets.
 Provides quality guarantees.
 Practical for real-world applications.
Limitations

 Does not always produce the optimal solution.

 Approximation quality varies by problem.
 Some NP-hard problems have poor approximation bounds.

Conclusion

Approximation algorithms provide efficient and practical solutions for NP-hard problems by
trading exactness for speed. They are widely used in optimization, networking, logistics,
scheduling, and resource allocation problems.

ii. Role of Sorting Algorithms in Large E-Commerce Platforms like

Amazon (10 Marks)

Introduction

E-commerce platforms such as Amazon manage millions of products. Sorting algorithms help
organize products based on attributes such as:

 Price
 Customer ratings
 Popularity
 Sales volume
 Discounts
 Relevance

Efficient sorting ensures fast search results and better user experience.

Role of Sorting Algorithms

1. Product Ranking

Products are sorted by:

 Lowest to highest price

 Highest-rated items
 Best-selling products
 New arrivals

2. Fast Search and Retrieval

Sorted data enables efficient searching techniques like Binary Search, reducing search time
significantly.
3. Data Analytics

Sorting helps analyze:

 Top-selling products
 Customer preferences
 Market trends

4. Inventory Management

Products can be sorted by stock availability, warehouse location, or demand.

Complexity of Different Sorting Algorithms

Algorithm Best Case Average Case Worst Case 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)

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)

Tim Sort O(n) O(n log n) O(n log n) O(n)

Optimization Techniques for Large Datasets

1. Use Efficient Algorithms

 Merge Sort, Quick Sort, Heap Sort, and Tim Sort are preferred.
 Complexity: O(n log n).

2. Parallel and Distributed Sorting

Large platforms divide data across multiple servers and sort in parallel using frameworks such
as:

 Hadoop
  Spark

This significantly reduces processing time.

3. External Sorting

When data does not fit into memory:

 Data is divided into chunks.

 Each chunk is sorted separately.
 Sorted chunks are merged.

Used for terabytes of product data.

4. Hybrid Sorting (Tim Sort)

 Combines Merge Sort and Insertion Sort.

 Performs exceptionally well on real-world datasets.
 Used in Python and Java libraries.

5. Indexing and Caching

Frequently requested sorted lists (e.g., "Top Rated Products") are cached and indexed to avoid
repeated sorting.

6. Database-Level Sorting

Modern databases use optimized indexing structures such as:

 B-Trees
 Hash Indexes

to speed up sorting and retrieval operations.

Conclusion

Sorting algorithms are essential for handling massive product datasets in e-commerce platforms.
While simple algorithms like Bubble Sort are unsuitable for large-scale applications, efficient
algorithms such as Merge Sort, Quick Sort, Heap Sort, and Tim Sort provide O(n log n)
performance. Combined with parallel processing, caching, indexing, and distributed computing,
these algorithms enable platforms like Amazon to deliver fast and accurate product rankings to
millions of users.