DESIGN AND ANALYSIS OF
ALGORITHMS – NOTES
1. Introduction to Algorithms
An Algorithm is a step-by-step procedure used to solve a problem or perform a task in a finite
amount of time.
In computer science, algorithms are used to process data, perform calculations, and automate
tasks.
Definition
An algorithm is a finite sequence of instructions that are used to solve a specific problem.
Example of a Simple Algorithm (Addition)
Step 1: Start
Step 2: Read two numbers A and B
Step 3: Add A + B
Step 4: Display the result
Step 5: Stop
Characteristics of an Algorithm
1. Input – Takes input values
2. Output – Produces output
3. Definiteness – Steps must be clear
4. Finiteness – Must finish in limited steps
5. Effectiveness – Steps must be simple and executable
2. Importance of Algorithm Design
Algorithm design is important because it helps to create efficient programs that run faster and
use less memory.
Advantages
Reduces execution time
Efficient use of memory
Solves complex problems easily
Improves program performance
Helps in better software development
3. Algorithm Design Techniques
There are several techniques used to design algorithms.
1. Divide and Conquer
Divide and Conquer is a technique where a problem is divided into smaller subproblems.
Each subproblem is solved separately and then combined to get the final solution.
Steps
1. Divide the problem
2. Solve subproblems
3. Combine the solutions
Example Algorithms
Merge Sort
Quick Sort
Binary Search
Advantages
Reduces complexity
Efficient for large data
2. Greedy Method
The Greedy method solves problems by choosing the best option at each step.
It does not consider future consequences.
Examples
Dijkstra’s Algorithm
Prim’s Algorithm
Kruskal’s Algorithm
Applications
Network routing
Minimum spanning tree
Shortest path problems
3. Dynamic Programming
Dynamic Programming is used to solve problems by breaking them into smaller subproblems
and storing the results to avoid repeated calculations.
Examples
Fibonacci sequence
Knapsack problem
Shortest path problems
Advantages
Saves computation time
Avoids repeated work
4. Backtracking
Backtracking is a technique used to solve problems by trying all possible solutions and
removing incorrect ones.
Examples
N-Queens problem
Sudoku solving
Maze solving
Working Principle
1. Try a possible solution
2. Check if it works
3. If not, go back and try another option
4. Algorithm Analysis
Algorithm analysis is the process of evaluating the efficiency of an algorithm.
It mainly focuses on:
Time complexity
Space complexity
5. Time Complexity
Time complexity measures how long an algorithm takes to run depending on the input size.
Common Time Complexities
Complexity Description
O(1) Constant time
O(log n) Logarithmic time
O(n) Linear time
O(n log n) Linear logarithmic
O(n²) Quadratic time
Example
Linear search has time complexity:
O(n)
Because it checks each element one by one.
6. Space Complexity
Space complexity refers to the amount of memory required by an algorithm during execution.
It includes:
Input storage
Auxiliary space
Temporary variables
Example:
If an algorithm uses extra arrays or memory, its space complexity increases.
7. Asymptotic Notations
Asymptotic notation is used to describe the efficiency of algorithms mathematically.
Types of Asymptotic Notations
1. Big O Notation
Big O represents the worst-case performance of an algorithm.
Example:
If an algorithm takes at most n² steps:
O(n²)
2. Omega Notation (Ω)
Omega represents the best-case performance of an algorithm.
Example:
Ω(n)
3. Theta Notation (θ)
Theta represents the average case performance of an algorithm.
Example:
θ(n log n)
8. Searching Algorithms
Searching algorithms are used to find an element in a data structure.
Linear Search
Linear search checks elements one by one.
Example:
Array = 10, 20, 30, 40
Searching 30:
10 → 20 → 30 ✔
Advantages
Simple
Works on unsorted data
Disadvantages
Slow for large datasets
Binary Search
Binary search works on sorted arrays.
The array is divided into two halves repeatedly.
Example:
Array = 10, 20, 30, 40, 50
Search for 40:
Step 1: Middle = 30
Step 2: 40 > 30 → search right
Step 3: Found 40
Advantages
Very fast
Efficient for large data
9. Sorting Algorithms
Sorting algorithms arrange data in a specific order.
Example:
Ascending order:
10, 20, 30, 40
Types of Sorting Algorithms
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Bubble Sort
Bubble sort repeatedly compares adjacent elements and swaps them if necessary.
Example:
Initial:
5382
Sorted:
2358
Disadvantages
Slow for large datasets
Merge Sort
Merge sort uses the divide and conquer technique.
Steps:
1. Divide the array
2. Sort each half
3. Merge the sorted halves
Advantages
Very efficient
Works well for large data
Quick Sort
Quick sort selects a pivot element and partitions the array around the pivot.
Elements smaller than pivot go to the left and larger elements go to the right.
Advantages
Fast sorting algorithm
Widely used in programming
10. Applications of Algorithms
Algorithms are used in many areas of computer science.
Examples
1. Search engines
2. Artificial intelligence
3. Data compression
4. Computer graphics
5. Network routing
6. Cryptography
7. Machine learning
11. Advantages of Good Algorithm Design
Faster program execution
Reduced memory usage
Better problem solving
Efficient data processing
Improved system performance
12. Conclusion
Design and Analysis of Algorithms is an important subject in computer science. It helps
programmers develop efficient solutions to complex problems.
By understanding algorithm design techniques and analyzing their performance, developers can
build faster and more efficient software systems.