WikiGalaxy
Divide and Conquer
Concept Overview:
Divide and Conquer is a fundamental algorithm design paradigm. It involves breaking a problem into smaller subproblems, solving each subproblem recursively, and combining their solutions to solve the original problem.
Example: Merge Sort
Merge Sort is a classic example of the divide and conquer technique. It divides the unsorted list into n sublists, each containing one element, and repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.
public class MergeSort {
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
merge(array, left, middle, right);
}
}
private static void merge(int[] array, int left, int middle, int right) {
// Merging logic...
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}
Console Output:
[5, 6, 7, 11, 12, 13]
Dynamic Programming
Concept Overview:
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the subproblems overlap, and it optimizes by storing the results of these subproblems.
Example: Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. Dynamic programming can efficiently compute Fibonacci numbers by storing previously computed values.
public class Fibonacci {
public static int fibonacci(int n) {
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
public static void main(String[] args) {
System.out.println(fibonacci(10)); // Output: 55
}
}
Console Output:
55
Greedy Algorithms
Concept Overview:
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. They are used for optimization problems where local optimization leads to global optimization.
Example: Activity Selection
The activity selection problem involves selecting the maximum number of activities that don't overlap. A greedy approach sorts activities by their finish time and selects the next activity that starts after the last selected one finishes.
import java.util.Arrays;
import java.util.Comparator;
public class ActivitySelection {
public static void selectActivities(int[] start, int[] finish) {
int n = start.length;
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) indices[i] = i;
Arrays.sort(indices, Comparator.comparingInt(i -> finish[i]));
int lastFinishTime = 0;
for (int i : indices) {
if (start[i] >= lastFinishTime) {
System.out.println("Activity " + i + ": [" + start[i] + ", " + finish[i] + "]");
lastFinishTime = finish[i];
}
}
}
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};
selectActivities(start, finish);
}
}
Console Output:
Activity 0: [1, 2] Activity 1: [3, 4] Activity 3: [5, 7] Activity 4: [8, 9]
Backtracking
Concept Overview:
Backtracking is a general algorithm for finding all (or some) solutions to computational problems, notably constraint satisfaction problems. It incrementally builds candidates to the solutions and abandons a candidate as soon as it determines that this candidate cannot lead to a valid solution.
Example: N-Queens Problem
The N-Queens problem is to place N queens on an N×N chessboard so that no two queens threaten each other. Backtracking is used to explore all possible placements and backtrack upon reaching an invalid configuration.
public class NQueens {
static int[] board;
static int N;
public static boolean isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
return false;
}
}
return true;
}
public static void solveNQueens(int row) {
if (row == N) {
printBoard();
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(row, col)) {
board[row] = col;
solveNQueens(row + 1);
}
}
}
public static void printBoard() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print((board[i] == j ? "Q " : ". "));
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
N = 4;
board = new int[N];
solveNQueens(0);
}
}
Console Output:
. Q . . . . . Q Q . . . . . Q . . . Q . Q . . . . . . Q . Q . .
Branch and Bound
Concept Overview:
Branch and Bound is an algorithm design paradigm for discrete and combinatorial optimization problems. It involves systematically enumerating candidate solutions by means of state space search and pruning branches that cannot yield better solutions.
Example: Traveling Salesman Problem (TSP)
TSP seeks the shortest possible route that visits each city exactly once and returns to the origin city. Branch and Bound can be used to prune paths that exceed the current best solution, reducing the number of routes to be explored.
// Simplified pseudo-code for TSP using Branch and Bound
public class TSP {
static int[][] graph;
static boolean[] visited;
static int N;
static int minCost = Integer.MAX_VALUE;
public static void tsp(int currPos, int cost, int count) {
if (count == N && graph[currPos][0] > 0) {
minCost = Math.min(minCost, cost + graph[currPos][0]);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i] && graph[currPos][i] > 0) {
visited[i] = true;
tsp(i, cost + graph[currPos][i], count + 1);
visited[i] = false;
}
}
}
public static void main(String[] args) {
N = 4;
graph = new int[][]{{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
visited = new boolean[N];
visited[0] = true;
tsp(0, 0, 1);
System.out.println("Minimum cost: " + minCost);
}
}
Console Output:
Minimum cost: 80
