DESIGN AND ANALYSIS OF

ALGORITHMS (DAA)
(VR 23)
B.Tech CSE (AI&ML) III-I
(AY: 2025-26)
 Introduction:

What is DAA?
Design and Analysis of Algorithms
(DAA) is a fundamental subject in computer
science and engineering.
What is an Algorithm?
An algorithm is a step-by-step procedure
or a set of rules to solve a specific problem
or perform a task.
 Design & Analysis

Design of Algorithms:
Design refers to how we create an algorithm
to solve a problem effectively. It involves
choosing the best strategy based on:
 Problem type
 Input size
 Resources (time and memory)
Common algorithm design techniques:
 Divide and Conquer

 Greedy Method

 Dynamic Programming

 Backtracking

 Branch and Bound

 Design & Analysis

Analysis of Algorithms:
Analysis means studying the performance
of an algorithm.
Main factors:
 Time Complexity: How fast does the algorithm run?
 Space Complexity: How much memory does it use?
 Importance of DAA
 Helps choose the best algorithm for a problem.
 Saves time and computing resources.

 Essential for solving real-world problems efficiently

 UNIT-I
Introduction: Algorithm, Performance Analysis-
Space complexity, Time complexity, Asymptotic
Notations- Big oh notation, Omega notation,
Theta notation and little oh notation.
Divide and conquer: General method,
applications-Binary search, Quick sort, Merge
sort, Strassen’s matrix multiplication.
UNIT – II
Disjoint Sets: Disjoint set operations, union and find algorithms,
Priority Queue- Heaps, Heap sort.
Backtracking: General method, applications, n-queen’s
problem, sum of subsets problem, graph Coloring,
Hamiltonian cycles.
 UNIT-III
Dynamic Programming: General method,
applications - Optimal binary search tree, 0/1
knapsack problem, All pairs shortest path
problem, Traveling salesperson problem,
Reliability design.

UNIT – IV
Greedy method: General method, applications-
Job sequencing with deadlines, knapsack
problem, Minimum cost spanning trees, Single
source shortest path problem. Basic Traversal
and Search Techniques: Techniques for Binary
Trees, Techniques for Graphs, Connected
 UNIT-V
Branch and Bound: General method,
applications - Traveling salesperson problem, 0/1
knapsack problem - LC Branch and Bound
solution, FIFO Branch and Bound solution.
NP-Hard and NP-Complete problems: Basic
concepts, non-deterministic algorithms, NPHard
and NP-Complete classes, Cook’s theorem.

TEXT BOOK: 1. Fundamentals of Computer

Algorithms, Ellis Horowitz, Satraj Sahni and Raja
sekharan, University press, 1998.
 UNIT-I
Project Title 1: Efficient Product Search in Inventory List
using Binary Search
Problem Statement: To implement a binary search algorithm using the divide-
and-conquer method to quickly find a product in a sorted list of items in a store’s
inventory
Project Title 2: Student Report Card using Merge Sort
Problem Statement: To implement the Merge Sort algorithm and use it to sort
student marks in order to prepare a report card.

Project Title 3: Performance-Oriented Salary Sorting in HR

Systems Using Quick Sort
Problem Statement: To implement and analyze the Quick Sort algorithm,
which uses the divide-and-conquer method, and apply it to sort employees by their
salary in an employee management system.
 UNIT-I
Project Title 4 : Strassen's Matrix Multiplication for Faster
Image Processing
Problem Statement: Implement and compare Strassen’s and traditional matrix
multiplication methods based on performance, using an image processing scenario.

Project Title 5: Match Scheduling for a Sports Tournament

using Divide and Conquer
Problem Statement: To design an efficient match scheduling algorithm for
large-scale tournaments (such as school championships, e-sports leagues, or inter-
college events) that minimizes idle time, optimizes venue usage, and ensures fair play.
 INTRODUCTION
The word "algorithm" comes from the name of a Persian
mathematician: Abu Jafar Mohammed Ibn Musa Al-Khwarizmi.
In the title, “Algorithmi” is the Latinized form of Al-
Khwarizmi’s name.
He wrote a book in Latin titled “Algorithmi de numero Indorum”,
An algorithm is a step-by-step procedure or a set of
rules to solve a specific problem or perform a task.
Design refers to how we create an algorithm to
solve a problem effectively (design techniques: Divide and
Conquer, Greedy Method, Dynamic , Programming, Backtracking,
Branch and Bound)

 Analysis means studying the

performance of an algorithm (Two Main factors: Time
Complexity and Space Complexity)
 PROPERTIES OF ALGORITHM
TO EVALUATE AN ALGORITHM WE HAVE TO SATISFY THE FOLLOWING
CRITERIA:

1. INPUT: Every algorithm must require zero or more inputs.

2. OUTPUT: Every algorithm must produce at least one output.

3. FINITENESS : Every algorithm has to finish its execution after

performing a finite number of steps.

4. DEFINITENESS : Every statement in the algorithm must be clear

and understandable.

5. EFFECTIVENESS: Every statement can be easily traced with the

help of pen and paper.
 How To Write an Algorithm
Step-1:start Step-1: start
Step-2:Read a,b,c Step-2: Read a,b,c
Step-3:if a>b Step-3:if a>b then go to step 4
if a>c otherwise go to step 5
print a is largest Step-4:if a>c then
else print a is largest otherwise
if b>c print c is largest
print b is largest Step-5: if b>c then
else print b is largest otherwise
print c is largest print c is largest
Step-4 : stop step-6: stop
 Differences
Algorithm Program
1. At design phase 1. At
Implementation phase
2. Natural language 2. written in any

programming language
3. Person should have 3. Programmer
Domain knowledge
4. Analyze 4. Testing
 ALGORITHM SPECIFICATIONS

To design an algorithm, we use various points

1. Use natural language English to design algorithm

 Drawback: In some cases, the same sentence produces two
meanings, i.e., it violates the definiteness rule.
2. Using graphical representation like flowchart
 Drawback: It is easy for only small applications.
3. Pseudo code representation:
A pseudo code is an informal high-level description of a
particular program.
It can be designed with a combination of natural language
English and various programming constructs available in
languages like ‘C’ and ‘Pascal’.
Pseudo Code Rules for Designing Algorithms:
1. Every algorithm must start with an algorithm heading.
Algorithm alg_name(par_list)Example: Algorithm factorial(n)
2. Only single-line comments are allowed: //
3. A block can be defined as a set of statements enclosed between { and }
4. Every statement must end with a semicolon (;)
5. All identifiers must start with a letter.
6. Logical operators can be represented as: && → and || → or ! → not
7. Relational operators can be represented as: <, <=, >, >=, !=, ==
8. Assignment statement can be written as: var := expr; or var ← expr;
9. To access a particular element in an array: For 1D array: a[i], 2D array: a[i]
[j]
10. Loop statements are classified into 3 types:
1. while loop: 2. for loop
while (cond) do for var := value1 to valueN [step stepval] do
{ {
// statements // statements
} }
3. Repeat ... Until: It is similar to do-while
repeat {
// statements
Pseudo Code Rules for Designing Algorithms:
11. If Statements Representation.
1. if: if (cond) then { 2. if-else: if (cond) then
{ statement
statement }
} else
{ statement
}
3. switch-case: switch (exp)
{
case label1: statement; break;
case label2: statement; break;
case label3: statement; break;
...
default: statement;
}
12. Output & Return Statement:
 To display the result, use: write(msg);
 To return a value, use: return expr;
Examples
Design an Algorithm Algorithm to Check Whether a
for Matrix Addition Number is Prime
1. Algorithm prime(n)
1. Algorithm Matadd(A, 2. {
B, C)
3. count := 0;
2. // A, B, C are matrices
of order n x n 4. for i := 1 to n do
3. { 5. {
4. for i := 1 to n do 6. if (n mod i = 0) then
5. { 7. count := count + 1;
6. for j := 1 to n do 8. }
7. {
9. if (count = 2) then
8. C[i,j] := A[i,j] +
B[i,j];
10. write "Number is prime";
9. } 11. else
10. } 12. write "Number is not
11. } prime";
13. }
 Performance Analysis
Performance Analysis refers to the process of evaluating
the efficiency and effectiveness of an algorithm. It involves
analyzing how the algorithm performs in terms of time and
space requirements.
Performance analysis contains two components:
1. Space Complexity
2. Time Complexity
1. Space Complexity :
The amount of memory required for an algorithm to complete its execution is called space
complexity.
It can be estimated by two components : i) Fixed part ii) Variable part
i) Fixed part : It does not depends on input and output characteristics.
 → In fixed part i) fixed size variables ii) constants iii)Instruction space
ii) Variable part: It depends on I/O characteristics.
→ It includes i) reference variable ii)Recursive stack space to process function calls

If an algorithm is treated as P, the space complexity is represented as SC(P).

SC(P)=fixed part + variable part
Calculate space complexity for sum of array elements
Algorithm sum(A[]) space complexity
{
a → n units
sum := 0
for i := 1 to n
n → 1 unit
{ sum → 1 unit
sum := sum + A[i] i → 1 unit
} Total = n + 3 units
}
 Performance Analysis Conti…..
2. Time Complexity:
Time required for an algorithm to perform a given task is known as time
complexity.
(OR)
Time Complexity refers to the amount of time an algorithm takes to run as a
function of the size of its input.
Time complexity = Compile time + Run time
1) Compile Time:
 Compile time is considered as constant because once the code is compiled, it can be executed any
number of times without re-compilation.
2) Run Time:
It depends on: i) The input size ii) The input characteristics
If P is a given algorithm, its time complexity T(P) is:
T(P)=Compile Time+Run Time
T(P)=C+TP​(instance)

→ To analyze time complexity we need to calculate step count for a given algorithm.
→ Every meaningful statement in the algorithm is called step.
Step count = The no. of steps required by an algorithm .
 Performance Analysis Conti….
Rules for defining steps in an algorithm:
1. Comments → require 0 steps
2.Assignment statements → require 1 step
3. Return statement → requires 1 step
4. For loop → requires n + 1 steps (n for loop entries & 1 for loop exit)
5. If/else conditions → require 1 step
1.Constant Time Complexity – O(1): The algorithm takes the same
amount of time, no matter how big or small the input is
int sum(int a, int b)
{
return a + b; Always takes 1 step, so time complexity is O(1)
}
2.Linear Time Complexity – O(n): The time increases directly with
the input size.
for (int i = 0; i < n; i++) {
sum = sum + i; Total steps ≈ 2n + 1, which simplifies to O(n)
}
 ORDER OF GROWTH
(OR)
COMPARISON OF FUNCTIONS
 ASYMPTOTIC NOTATIONS
 Asymptotic Notation is a mathematical tool used to describe time complexity of
algorithms.
 It represents how the running time or resource usage of an algorithm grows with
input size.
 Focuses on asymptotic growth: how a function behaves as input becomes very
large.
Asymptotic Notation = growth calculator for algorithms.
Helps predict how slow or fast your solution will be.
Asymptotic Notations are useful for representing the time complexity of a
particular algorithm in various forms.
1. Best Case: The minimum amount of time require to complete a task
2. Worst Case: The maximum amount of time require to complete a task
3. Average Case: The average amount of time required to complete a task.
 ASYMPTOTIC NOTATIONS
Asymptotic Notations are classified as:
1.Big oh (O)notation 4.Little oh notation
2.Big omega (Ω) notation 5.Little omega(Ω) notation
3.Theta(Θ) notation
1.Big oh (O)notation :
It is used to represent worst case time complexity.
It is used to represent the upper bound value of time
It is denoted by O.
Let f(n) and g(n) be two functions. We say: f(n) = O(g(n)) iff there exist
constants c > 0 and n₀ ≥ 0 such that: f(n)≤c*g(n) for all
n≥n0​
 ASYMPTOTIC NOTATIONS
2.Big omega (Ω) notation:
It is used to represent best case time complexity.
It is used to represent the lower bound value of a particular algorithm
It is denoted by Ω.
Let f(n) and g(n) be two functions. We say: f(n) = O(g(n)) if there exist constants
c > 0 and n₀ ≥ 0 such that: f(n) ≥ c*g(n) for all n≥n0​
ASYMPTOTIC NOTATIONS
3.Theta(Θ) notation :
It is used to represent average case time complexity.
It is defines both lower and upper bound value of particular algorithm
It is denoted by Θ.
Let f(n) and g(n) be two functions. f(n) = Θ(g(n)) if there are two positive
constants c1 and c2 and a value n0, such that c1.g(n) ≤ f(n) ≤ c2.g(n) for
all n ≥ n0
ASYMPTOTIC NOTATIONS
4.Little oh (o) notation :
Little-o notation shows that one function grows much slower than another
function when input size n becomes very large.
It is denoted by o (small oh).
We write: f(n)=o(g(n)) if f(n) grows slower than g(n),
& never catches up, even when n becomes very big.
we can say that f(n) = o(g(n)) means,
5. Little omega(Ω) notation:
Little-omega notation shows that one function
grows much faster than another function as the
input size n becomes very large.
It is denoted by ω.
if f(n) grows faster than g(n), and eventually
leaves it behind completely when n gets very big
f(n)=ω(g(n)). 0 <= cg(n) < f(n) for all n ≥ no}
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

Problem Statement: To implement a

Core Areas binary search algorithm using the divide-
of Focus and-conquer method to efficiently find
products in a sorted inventory list.
• DIVIDE-AND-
CONQUER
Objectives:
• BINARY
SEARCH
 Understand how divide-and-conquer is
ALGORITHM applied in binary search.
 Implement a binary search algorithm in
•PERFORMANCE
ANALYSIS
Python (or any language).
 Apply it to a real-world scenario:

searching products in a sorted inventory.

 Analyze and compare performance with

linear search.
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

Modules/Phases
1. Requirement Analysis:
Core Areas  Understand input: Sorted list of products
of Focus
(IDs or names).
 Define expected output: Position or
• DIVIDE-AND-
CONQUER message if product not found
2. Design:
• BINARY
SEARCH Design a flowchart or pseudo code for
ALGORITHM binary search
Input: sorted list, target product
•PERFORMANCE
ANALYSIS Output: index or "Product not

found"
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

Pseudo code:
def binary search(arr, target):
Core Areas low = 0
of Focus high = len(arr) – 1
while low <= high:
• DIVIDE-AND-
CONQUER mid = (low + high) // 2
if arr[mid] == target:
• BINARY return mid # Product
SEARCH
ALGORITHM found
elif arr[mid] < target:
•PERFORMANCE
ANALYSIS
low = mid + 1
else:
high = mid – 1
return -1 # Product not found
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

3. Implementation
 Use Python to implement:
Core Areas  Sorted product inventory list.
of Focus
 Binary search function.

 Accept product name/ID as input from

• DIVIDE-AND-
CONQUER user.
4. Testing
• BINARY
SEARCH  Test with various sizes of inventory (small,
ALGORITHM
medium, large).
 Search for:
•PERFORMANCE
ANALYSIS  First item

 Middle item

 Last item

 Missing item
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

5. Performance Analysis
Compare binary search vs linear
Core Areas
of Focus search:
 Execution time
• DIVIDE-AND-  Number of comparisons
CONQUER
Use time module in Python:
• BINARY
SEARCH
ALGORITHM
import time
start = time.time()
•PERFORMANCE
ANALYSIS
binary_search(products,
"Mouse")
end = time.time()
print("Time taken:", end -
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

6. Tools & Technologies:

 Language: Python (or Java, C++)
Core Areas
of Focus  IDE: VS Code / PyCharm / Jupyter Notebook
 Libraries: time, random (for performance
• DIVIDE-AND- testing)
CONQUER
7. Expected Output:
 Efficient search result showing product index if
• BINARY
SEARCH found.
ALGORITHM
 Display comparison results between binary and
linear search.
•PERFORMANCE
ANALYSIS 8. Real-World Applications:
 E-commerce platforms: Fast search of items.
 Inventory management systems.
 Library catalog search.
 Project Title 1: Efficient Product Search in a Sorted
Inventory List - Binary Search

Core Areas Conclusion

of Focus

• DIVIDE-AND-
 Learn divide-and-conquer strategy practically.
CONQUER

 Apply algorithm to a real use case.

• BINARY
SEARCH
ALGORITHM  Understand algorithm complexity (O(log n) vs

•PERFORMANCE
ANALYSIS O(n)).
Efficient Product Search System – Fast Lookup in a Large,
Sorted Inventory
 Real-World Application Scenario:
Core
Areas of
 E-commerce platforms, retail software,
Focus
and inventory management systems
often deal with massive catalogs of
•DIVIDE-
AND- products.
CONQUER

 When customers or administrators

•BINARY
SEARCH
search for product information (like
ALGORITHM price, availability, or name), the system
must return results instantly — even
•PERFORMA with millions of items
NCE
ANALYSIS
Efficient Product Search System – Fast Lookup in a Large,
Sorted Inventory
 Objectives:
Core
 Design and implement a high-performance search
Areas of
system that:
Focus  Works with a sorted inventory list containing product
data such as:
 Product ID or name
•DIVIDE-  Price
AND-  Stock quantity
CONQUER
 Category and other attributes
 Uses an efficient searching algorithm (e.g., Binary
•BINARY Search) to:
 Retrieve product details quickly.
SEARCH
ALGORITHM  Minimize memory and CPU usage.
 Supports exact or partial match queries (e.g., search
by ID or name prefix).
•PERFORMA  (Optional) Supports enhancements like auto-complete,
NCE filters, or range-based search (e.g., price range).
ANALYSIS
 Efficient Product Search System – Fast Lookup in a Large,
Sorted Inventory

Core Areas Key Features:

of Focus
 Input: Sorted list of products (by ID or name)

•DIVIDE-AND-
CONQUER  Search Query: Product name or ID

 Algorithm: Binary Search for quick retrieval in

•BINARY
SEARCH
ALGORITHM O(log n) time

 Output: Product details (name, price, stock,

•PERFORMANC
E
etc.)
Efficient Product Search in a Sorted Inventory List -
Binary Search
Pseudo code:
Core def binary search(arr, target):
Areas of low = 0
Focus high = len(arr) – 1
while low <= high:
•DIVIDE-AND- mid = (low + high) // 2
CONQUER
if arr[mid] == target:
return mid # Product found
•BINARY
SEARCH
elif arr[mid] < target:
ALGORITHM low = mid + 1
else:
•PERFORMAN high = mid – 1
CE
return -1 # Product not found
Implementation: (Python)
# Sample product inventory (sorted by product ID)
products = [
{"id": 101, "name": "Laptop", "price": 75000, "stock": 12},
{"id": 102, "name": "Mouse", "price": 500, "stock": 150},
{"id": 103, "name": "Keyboard", "price": 1500, "stock": 80},
{"id": 104, "name": "Monitor", "price": 12000, "stock": 25},
{"id": 105, "name": "Printer", "price": 7000, "stock": 10},
]
# Ensure list is sorted by 'id'
products.sort(key=lambda x: x["id"])

def binary_search(products, target_id):

left = 0
right = len(products) - 1

while left <= right:

mid = (left + right) // 2
mid_id = products[mid]["id"]
 if mid_id == target_id:
return products[mid]
else if mid_id < target_id:
left = mid + 1
else:
right = mid - 1

return None

# Example usage
search_id = int(input("Enter Product ID to search: "))
result = binary_search(products, search_id)

if result:
print("\n Product Found:")
print(f"ID: {result['id']}")
print(f"Name: {result['name']}")
print(f"Price: ₹{result['price']}")
print(f"Stock: {result['stock']} units")
else:
print("\n Product not found in inventory.")
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

Problem Statement:
Core
To design and implement the Merge Sort algorithm to sort
Areas of
student marks and generate a structured report card. This
Focus
project demonstrates the importance of sorting techniques in
organizing academic data effectively.
• DIVIDE-
AND- Objectives:
CONQUER
 Understand how divide-and-conquer is applied in merge
sort.
• MERGE
SORT  Implement the merge sort algorithm using Python (or any
ALGORITHM
language).
• PERFORMA  Apply the algorithm to sort student marks for report card
NCE
ANALYSIS generation.
 Compare performance with other sorting techniques (e.g.,
bubble sort).
 Present a well-formatted report card using sorted data.
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

Modules/Phases
Core
Areas of 1. Requirement Analysis:
Focus  Input: List of student names with corresponding marks.
 Expected Output: Sorted list of students based on
• DIVIDE-
AND-
marks (ascending/descending), along with grades.
CONQUER

• MERGE
2. Design:
SORT  Design a flowchart or pseudo code for merge sort.
ALGORITHM
 Input: List of marks or (student name, marks) pairs.
• PERFORMA
NCE  Output: Sorted list and grade assignment.
ANALYSIS
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

Core Pseudo Code (Merge Sort):

Areas of
Focus
def merge_sort(arr):
• DIVIDE- if len(arr) > 1:
AND-
CONQUER mid = len(arr) // 2
left_half = arr[:mid]
• MERGE
SORT right_half = arr[mid:]
ALGORITHM
merge_sort(left_half)
• PERFORMA
NCE merge_sort(right_half)
ANALYSIS
i=j=k=0
 Project Title 2: Efficient Report Card Generation
Using Merge Sort
while i < len(left_half) and j < len(right_half):
if left_half[i][1] < right_half[j][1]:
Core arr[k] = left_half[i]
Areas of
i += 1
Focus
else:
• DIVIDE- arr[k] = right_half[j]
AND- j += 1
CONQUER
k += 1
• MERGE while i < len(left_half):
SORT arr[k] = left_half[i]
ALGORITHM
i += 1
• PERFORMA
NCE k += 1
ANALYSIS
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

3. Implementation:
Core  Use Python to implement:
Areas of
◦ Student data input (name and marks)
Focus
◦ Merge sort algorithm
• DIVIDE- ◦ Grade assignment logic
AND-
CONQUER  Display report card sorted by marks.

4. Testing:
• MERGE
SORT  Test with different number of students:
ALGORITHM
◦ Small (5–10 students)
• PERFORMA
NCE ◦ Medium (50 students)
ANALYSIS
◦ Large (100+ students)
 Sort in both ascending and descending orders.
 Validate correctness and stability of sorting.
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

5. Performance Analysis:
Core  Compare merge sort vs bubble sort or any basic sorting.
Areas of  Measure:
Focus
◦ Execution time
• DIVIDE- ◦ Number of comparisons
AND-
 Use time module:
CONQUER
 python
• MERGE
SORT import time
ALGORITHM
start = time.time()
• PERFORMA
NCE merge_sort(student_marks)
ANALYSIS
end = time.time()
print("Time taken:", end - start)
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

6. Tools & Technologies:

Core  Language: Python (or Java, C++)
Areas of  IDE: VS Code / PyCharm / Jupyter Notebook
Focus
 Libraries: time, random (for generating test data)
• DIVIDE-
AND-
CONQUER

7. Expected Output:
• MERGE
SORT  A sorted report card displaying:
ALGORITHM
◦ Student names
• PERFORMA
NCE ◦ Marks
ANALYSIS
◦ Grades (A/B/C etc.)
 Performance comparison report
 Project Title 2: Efficient Report Card Generation
Using Merge Sort

8. Real-World Applications:
Core  E-commerce: Sorting products by price or rating.
Areas of  Hospitals: Sorting patient data by priority.
Focus
 Banking: Sorting transactions by amount/date.
• DIVIDE-  Library Systems: Sorting books by title or author.
AND-
CONQUER

• MERGE
Conclusion
SORT  Learn how merge sort applies divide-and-conquer
ALGORITHM
practically.
• PERFORMA
NCE  Understand sorting algorithm complexity (O(n log n)).
ANALYSIS
 Apply sorting to a real-life problem (student report card).
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort
Problem Statement:
Core To implement and evaluate the Quick Sort algorithm,
Areas of
which operates on the divide-and-conquer principle, and
Focus
apply it to sort employee data by salary in an HR
management system. The goal is to optimize data
• DIVIDE-AND-
CONQUER handling, salary-based queries, and reporting in a time-
STRATEGY
efficient manner.
• QUICK SORT
Objectives:
ALGORITHM  Understand how Quick Sort operates internally.
 Sort employee salary records efficiently using Quick Sort.
• IN-PLACE
SORTING  Use the sorted data to enhance HR system features like
reporting and payroll.
• PERFORMANC
 Compare Quick Sort with other sorting algorithms in
E
COMPARISON terms of time complexity and resource usage.
 Handle both ascending and descending sorting logic as
needed.
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort

Core
Areas of Modules/Phases
Focus

• DIVIDE-AND- 1. Requirement Analysis:

CONQUER
STRATEGY
Input: A list of employees with their names and salaries.
Output: Sorted employee records based on salary
• QUICK SORT (ascending or
ALGORITHM
descending).
• IN-PLACE
2. Design Approach:
SORTING ◦ Input employee data (e.g., ("John", 50000)).
◦ Use Quick Sort with pivot-based partitioning.
• PERFORMANC
E ◦ Recursively sort left and right sub-arrays.
COMPARISON
◦ Display sorted records and optionally assign salary
grades.
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort
Pseudo code:
Core def quick_sort(arr, low, high):
Areas of
if low < high:
Focus
pivot_index = partition(arr, low, high)
• DIVIDE-AND- quick_sort(arr, low, pivot_index - 1)
CONQUER
STRATEGY
quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
• QUICK SORT pivot = arr[high][1] # Using salary as the pivot
ALGORITHM
i = low - 1
• IN-PLACE for j in range(low, high):
SORTING if arr[j][1] <= pivot:
i += 1
• PERFORMANC
E arr[i], arr[j] = arr[j], arr[i]
COMPARISON
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort

Core 3. Implementation:
Areas of ◦ Programming Language: Python (or Java/C++)
Focus
◦ Inputs:
• DIVIDE-AND-
Employee name
CONQUER Salary
STRATEGY
◦ Apply Quick Sort to the salary list.
• QUICK SORT ◦ Display sorted records.
ALGORITHM
4. Testing:
• IN-PLACE ◦ Test with employee lists of:
SORTING
10 records (small)
• PERFORMANC 50 records (medium)
E
COMPARISON 100+ records (large)
◦ Validate sorting logic and execution time.
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort

Core 5. Performance Analysis:

Areas of ◦ Best Case / Average Case: O(n log n)
Focus
◦ Worst Case: O(n²) (can be reduced using randomized
pivot selection)
• DIVIDE-AND-
CONQUER ◦ Compared with Bubble Sort and Merge Sort for similar
STRATEGY
datasets.
• QUICK SORT
◦ Used time module in Python to measure execution time.
ALGORITHM
6. Tools & Technologies:
• IN-PLACE ◦ Language: Python / Java / C++
SORTING
◦ IDE: PyCharm / VS Code / NetBeans
• PERFORMANC ◦ Libraries: time, random, csv (for optional data
E import/export)
COMPARISON
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort

Core 7. Expected Output:

Areas of A sorted list of employees:
Focus Employee Name
Salary
• DIVIDE-AND-
CONQUER 8. Real-World Applications:
STRATEGY
◦ Payroll Systems: Salary-based processing and auditing
• QUICK SORT ◦ HR Analytics: Sorting salaries for insights on pay
ALGORITHM structure
◦ Taxation Portals: Ranking by income brackets
• IN-PLACE
SORTING ◦ Recruitment Platforms: Filtering candidates based on
salary expectations
• PERFORMANC
E
◦ Enterprise BI Tools: Sorting for data visualization
COMPARISON dashboards
 Project Title 3: Performance-Oriented Salary
Sorting in HR Systems Using Quick Sort

Core
Areas of
Focus
Conclusion
• DIVIDE-AND-
CONQUER
This project demonstrates the real-world utility of
STRATEGY Quick Sort in HR systems. Its speed and in-place
sorting capability make it ideal for managing large
• QUICK SORT employee datasets efficiently. By integrating
ALGORITHM
algorithmic logic with real-time systems, we bring
• IN-PLACE
theoretical computer science into practical use.
SORTING

• PERFORMANC
E
COMPARISON