Analysis of Algorithm – Mumbai University (NEP 2020)
Comprehensive Notes including Definitions, Algorithm Summaries, Applications, Advantages, and
Disadvantages.
Table of Contents
1. Module 1 – Introduction to Algorithm Analysis
2. Module 2 – Divide and Conquer
3. Module 3 – Greedy Algorithms
4. Module 4 – Dynamic Programming
5. Module 5 – Graph Algorithms and Backtracking
6. Module 6 – String Matching Algorithms
Module 1 – Introduction to Algorithm Analysis
1. Algorithm and Characteristics
Definition: An algorithm is a finite set of instructions that, when executed, produces a solution to a
given problem.
Characteristics: Finiteness, Definiteness, Input, Output, and Effectiveness.
Applications: Used in all computational problem-solving processes.
Advantages: Provides structured solutions and reduces errors.
Disadvantages: May require complex logic or high computation time.
2. Time and Space Complexity
Definition: Measures the amount of time and memory required by an algorithm.
Applications: Used to analyze efficiency and scalability of programs.
Advantages: Helps in selecting the most efficient algorithm.
Disadvantages: May vary across systems and inputs.
3. Asymptotic Notations
Definition: Mathematical notations to describe algorithm performance (O, Ω, Θ).
Applications: Used to compare algorithms independent of machine specifications.
Advantages: Gives theoretical performance estimate.
Disadvantages: Does not account for constant factors or real-world data.
Module 2 – Divide and Conquer
1. Binary Search
Definition: Searches an element in a sorted array by repeatedly dividing the array in half.
Applications: Searching in databases or sorted arrays.
Advantages: Very fast; O(log n) complexity.
Disadvantages: Works only for sorted data.
2. Merge Sort
Definition: A sorting technique that divides the array, sorts subarrays, and merges them.
Applications: Sorting large datasets efficiently.
Advantages: Stable and has predictable O(n log n) time.
Disadvantages: Requires extra memory for merging.
3. Quick Sort
Definition: Sorts by selecting a pivot, partitioning elements, and recursively sorting subarrays.
Applications: Used in system libraries for general-purpose sorting.
Advantages: Fast for average cases; O(n log n) average time.
Disadvantages: Poor performance (O(n²)) for already sorted data if pivot is bad.
4. Strassen’s Matrix Multiplication
Definition: An optimized divide-and-conquer matrix multiplication reducing multiplications from 8 to
7 per recursion.
Applications: Used in graphics, scientific computing, and data processing.
Advantages: Faster than conventional O(n³) method.
Disadvantages: Complex implementation and less effective for small matrices.
Module 3 – Greedy Algorithms
1. Fractional Knapsack
Definition: Selects items with maximum value/weight ratio, can take fractions.
Applications: Resource allocation problems.
Advantages: Simple and efficient (O(n log n)).
Disadvantages: Not suitable for 0/1 cases.
2. Job Sequencing with Deadlines
Definition: Schedules jobs to maximize profit before deadlines.
Applications: CPU scheduling, task management.
Advantages: Maximizes profit in limited time.
Disadvantages: Needs sorted job list; not optimal for all cases.
3. Kruskal’s Algorithm
Definition: Finds the Minimum Spanning Tree (MST) by adding edges in increasing weight order.
Applications: Network design, circuit connections.
Advantages: Simple and efficient for sparse graphs.
Disadvantages: Requires sorting and union-find structure.
4. Prim’s Algorithm
Definition: Builds MST by expanding from a starting vertex using smallest edge.
Applications: Designing network cables or electrical grids.
Advantages: Works well for dense graphs.
Disadvantages: Less efficient for sparse graphs.
5. Dijkstra’s Algorithm
Definition: Finds the shortest path from a single source to all vertices in a weighted graph.
Applications: GPS navigation, routing protocols.
Advantages: Efficient and guarantees shortest path.
Disadvantages: Fails with negative edge weights.
6. Huffman Coding
Definition: Compression algorithm assigning variable-length codes to characters.
Applications: Data compression formats (ZIP, JPEG).
Advantages: Reduces storage space.
Disadvantages: Requires decoding overhead.
Module 4 – Dynamic Programming
1. Fibonacci Sequence
Definition: Solves Fibonacci using memoization or tabulation to avoid recomputation.
Applications: Used in recursion optimization.
Advantages: Reduces redundant calculations.
Disadvantages: Requires extra space for tables.
2. 0/1 Knapsack Problem
Definition: Selects items to maximize profit without exceeding capacity (cannot take fractions).
Applications: Resource management, cargo loading.
Advantages: Guarantees optimal result.
Disadvantages: High time complexity O(nW).
3. Matrix Chain Multiplication
Definition: Finds optimal parenthesization for matrix multiplication to minimize scalar multiplications.
Applications: Used in compilers and query optimization.
Advantages: Efficient solution to exponential problem.
Disadvantages: Complex implementation.
4. Longest Common Subsequence (LCS)
Definition: Finds the longest sequence common to two strings.
Applications: DNA analysis, text comparison.
Advantages: Guarantees optimal subsequence.
Disadvantages: O(m×n) space and time usage.
5. Travelling Salesman Problem (TSP)
Definition: Finds the shortest route visiting all cities once and returning to origin.
Applications: Logistics, delivery routing.
Advantages: Finds global optimum.
Disadvantages: Very high computational cost.
Module 5 – Graph Algorithms and Backtracking
1. Breadth First Search (BFS)
Definition: Traverses graph level by level using a queue.
Applications: Shortest path in unweighted graphs.
Advantages: Simple and guarantees shortest path in unweighted graphs.
Disadvantages: Requires more memory (queue).
2. Depth First Search (DFS)
Definition: Traverses graph depth-wise using recursion or stack.
Applications: Topological sorting, detecting cycles.
Advantages: Memory-efficient for sparse graphs.
Disadvantages: May get stuck in deep recursion.
3. N-Queen Problem
Definition: Places N queens on an N×N chessboard so that none attack each other.
Applications: AI constraint satisfaction problems.
Advantages: Demonstrates backtracking efficiency.
Disadvantages: Time-consuming for large N.
4. Graph Coloring
Definition: Assigns colors to graph vertices so that adjacent vertices have different colors.
Applications: Scheduling, register allocation.
Advantages: Provides optimal scheduling solutions.
Disadvantages: NP-hard for general graphs.
5. Hamiltonian Path and Circuit
Definition: Visits each vertex once (path) or returns to start (circuit).
Applications: Routing and game theory.
Advantages: Useful in optimization problems.
Disadvantages: NP-complete; difficult for large graphs.
Module 6 – String Matching Algorithms
1. Native String Matching Algorithm
Definition: Compares pattern with text character by character, shifting one position at a time.
Applications: Text searching, word processing tools.
Advantages: Simple to implement.
Disadvantages: Inefficient for large texts (O(m×n)).
2. Rabin–Karp Algorithm
Definition: Uses hashing to match pattern substrings efficiently.
Applications: Plagiarism detection, search engines.
Advantages: Fast average time complexity (O(n+m)).
Disadvantages: Hash collisions can degrade performance.
