WikiGalaxy
Introduction to Algorithm Design Techniques
Divide and Conquer
Overview
Divide and Conquer is a paradigm that breaks a problem into smaller sub-problems, solves each sub-problem recursively, and combines their solutions to solve the original problem.
Example: Merge Sort
Merge Sort is a classic example of Divide and Conquer. It divides the array into halves, sorts each half, and merges them back together.
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
Console Output:
Sorted Array: [1, 2, 3, 4, 5]
Dynamic Programming
Overview
Dynamic Programming is a technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
Example: Fibonacci Sequence
The Fibonacci sequence can be efficiently calculated using dynamic programming by storing previously calculated values.
int fib(int n) {
int f[] = new int[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
Console Output:
Fibonacci Number: 21
Greedy Algorithms
Overview
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or profit.
Example: Activity Selection
The Activity Selection problem is a classic example where a greedy approach can be used to select the maximum number of activities that don't overlap.
void activitySelection(int s[], int f[], int n) {
int i = 0;
System.out.print("Selected activities: ");
System.out.print(i + " ");
for (int j = 1; j < n; j++) {
if (s[j] >= f[i]) {
System.out.print(j + " ");
i = j;
}
}
}
Console Output:
Selected activities: 0 1 3
Backtracking
Overview
Backtracking is an algorithmic technique for solving problems incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point in time.
Example: N-Queens Problem
The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other.
boolean solveNQUtil(int board[][], int col) {
if (col >= N) return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) return true;
board[i][col] = 0;
}
}
return false;
}
Console Output:
Solution exists for N-Queens problem
Branch and Bound
Overview
Branch and Bound is an algorithm design paradigm for discrete and combinatorial optimization problems. It is used to solve problems like the Traveling Salesman Problem.
Example: Traveling Salesman Problem
The Traveling Salesman Problem involves finding the shortest possible route that visits each city and returns to the origin city.
void TSP(int graph[][], boolean v[], int currPos, int n, int count, int cost, int ans) {
if (count == n && graph[currPos][0] > 0) {
ans = Math.min(ans, cost + graph[currPos][0]);
return;
}
for (int i = 0; i < n; i++) {
if (!v[i] && graph[currPos][i] > 0) {
v[i] = true;
TSP(graph, v, i, n, count + 1, cost + graph[currPos][i], ans);
v[i] = false;
}
}
}
Console Output:
Minimum cost: 10
