Analysis of Algorithms — Complete (Definition + Solved)
Divide and Conquer
Definition: A technique in which a problem is divided into smaller subproblems, each solved independently, and then combined to form final solution.
Concept: Divide → Conquer → Combine
Example (Merge Sort):
Array: [8,3,5,2]
Steps:
Divide → [8,3] [5,2]
Divide → [8][3] [5][2]
Merge → [3,8] [2,5]
Final → [2,3,5,8]
Definition: A technique in which a problem is divided into smaller subproblems, each solved independently, and then combined to form final solution.
Concept: Divide → Conquer → Combine
Example (Merge Sort):
Array: [8,3,5,2]
Steps:
Divide → [8,3] [5,2]
Divide → [8][3] [5][2]
Merge → [3,8] [2,5]
Final → [2,3,5,8]
[8,3,5,2]
/ \
[8,3] [5,2]
/ \ / \
[8] [3] [5] [2]
\ / \ /
[3,8] [2,5]
\ /
[2,3,5,8]
Time Complexity: O(n log n)
Binary Search
Definition: A searching algorithm that finds an element in a sorted array by repeatedly dividing the search space in half.
Concept: Compare with middle element and reduce search space.
Example: Find 5 in [2,3,5,8]
Steps:
Mid = 3 → go right
Mid = 5 → FOUND
Definition: A searching algorithm that finds an element in a sorted array by repeatedly dividing the search space in half.
Concept: Compare with middle element and reduce search space.
Example: Find 5 in [2,3,5,8]
Steps:
Mid = 3 → go right
Mid = 5 → FOUND
[2 3 5 8] ↑Time Complexity: O(log n)
Greedy Algorithm
Definition: An algorithm that makes the best choice at each step to find optimal solution.
Concept: Local optimum → Global optimum
Example (Activity Selection):
A(1-3), B(2-5), C(4-6), D(6-7)
Steps:
Select A
Skip B
Select C
Select D
Result: A, C, D
Definition: An algorithm that makes the best choice at each step to find optimal solution.
Concept: Local optimum → Global optimum
Example (Activity Selection):
A(1-3), B(2-5), C(4-6), D(6-7)
Steps:
Select A
Skip B
Select C
Select D
Result: A, C, D
A |---| B |-----| C |---| D |-|
Dynamic Programming
Definition: Technique that solves problems by storing results of subproblems to avoid recomputation.
Concept: Overlapping subproblems + optimal substructure
Example (Fibonacci):
Steps:
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
Definition: Technique that solves problems by storing results of subproblems to avoid recomputation.
Concept: Overlapping subproblems + optimal substructure
Example (Fibonacci):
Steps:
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
n:0 1 2 3 4 5 f:0 1 1 2 3 5
Dijkstra Algorithm
Definition: Algorithm to find shortest path from a source node to all other nodes in weighted graph.
Concept: Always choose minimum distance node
Example:
A→B(1), B→C(2), A→C(4)
Steps:
Start A=0
B=1
C=min(4,1+2)=3
Result: A→C = 3
Definition: Algorithm to find shortest path from a source node to all other nodes in weighted graph.
Concept: Always choose minimum distance node
Example:
A→B(1), B→C(2), A→C(4)
Steps:
Start A=0
B=1
C=min(4,1+2)=3
Result: A→C = 3
A --1--> B | | 4 2 | | v v C <------
Hashing
Definition: Technique to map keys to specific index using hash function.
Concept: Fast search (O(1))
Example:
h(k)=k%10
23→3, 43→3
Collision Solution: Chaining
Definition: Technique to map keys to specific index using hash function.
Concept: Fast search (O(1))
Example:
h(k)=k%10
23→3, 43→3
Collision Solution: Chaining
3 → 23 → 43
Heap
Definition: A complete binary tree that satisfies heap property.
Concept: Max Heap → parent > children
Example: Insert 20,10,5
Definition: A complete binary tree that satisfies heap property.
Concept: Max Heap → parent > children
Example: Insert 20,10,5
20 / \ 10 5
Binary Search Tree
Definition: A tree where left subtree < root < right subtree.
Example: Insert 10,5,15
Definition: A tree where left subtree < root < right subtree.
Example: Insert 10,5,15
10 / \ 5 15
String Matching
Definition: Finding occurrence of pattern in text.
Example:
Text: ABCABC
Pattern: ABC → index 0,3
Definition: Finding occurrence of pattern in text.
Example:
Text: ABCABC
Pattern: ABC → index 0,3
NP-Complete Problems
Definition: Problems for which no efficient solution is known.
Example: Traveling Salesman Problem
Definition: Problems for which no efficient solution is known.
Example: Traveling Salesman Problem
Approximation Algorithms
Definition: Algorithms that give near-optimal solution for hard problems.
Example: Greedy for NP problems
Definition: Algorithms that give near-optimal solution for hard problems.
Example: Greedy for NP problems
0 Comments