Algorithmic Paradigms

Introduction

Algorithmic paradigms are general approaches or methods used to design and implement algorithms to solve computational problems. Each paradigm has its own set of principles, techniques, and strategies that guide the algorithm design process. Understanding these paradigms is essential for developing efficient and effective algorithms for a wide range of problems.

We are going to review some of the most common algorithmic paradigms.

• Brute Force
• Greedy Algorithms
• Dynamic Programming
• Divide and Conquer
• Backtracking
• Branch and Bound

Brute Force

Overview: Brute force algorithms try all possible solutions to find the correct one. They are often simple to implement but can be inefficient for large datasets.

Example Algorithms:

• Linear Search
• Bubble Sort
• Traveling Salesman Problem (TSP)

Code Sample: Linear Search

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

const arr = [10, 20, 30, 40, 50];
const target = 30;
console.log(linearSearch(arr, target)); // Output: 2

Greedy Algorithms

Overview: Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

Example Algorithms:

• Prim's Algorithm
• Kruskal's Algorithm
• Dijkstra's Algorithm

Code Sample: Dijkstra's Algorithm

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({val, priority});
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

function dijkstra(graph, start) {
  const pq = new PriorityQueue();
  const distances = {};
  const previous = {};
  let smallest;

  for (let vertex in graph) {
    if (vertex === start) {
      distances[vertex] = 0;
      pq.enqueue(vertex, 0);
    } else {
      distances[vertex] = Infinity;
      pq.enqueue(vertex, Infinity);
    }
    previous[vertex] = null;
  }

  while (pq.values.length) {
    smallest = pq.dequeue().val;
    if (smallest === start) break;

    for (let neighbor in graph[smallest]) {
      let distance = distances[smallest] + graph[smallest][neighbor];
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        previous[neighbor] = smallest;
        pq.enqueue(neighbor, distance);
      }
    }
  }

  return distances;
}

const graph = {
  A: {B: 1, C: 4},
  B: {A: 1, C: 2, D: 5},
  C: {A: 4, B: 2, D: 1},
  D: {B: 5, C: 1},
};

console.log(dijkstra(graph, 'A')); // Output: { A: 0, B: 1, C: 3, D: 4 }

Dynamic Programming

Overview: Dynamic programming solves problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computations.

Example Algorithms:

• Fibonacci Sequence
• Knapsack Problem
• Longest Common Subsequence (LCS)

Code Sample: Fibonacci Sequence

function fibonacci(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  const dp = Array(n + 1).fill(0);
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fibonacci(10)); // Output: 55

Divide and Conquer

Overview: Divide and conquer algorithms solve a problem by dividing it into smaller subproblems, solving each subproblem recursively, and then combining their solutions.

Example Algorithms:

• Merge Sort
• Quick Sort
• Binary Search

Code Sample: Merge Sort

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // Output: [3, 9, 10, 27, 38, 43, 82]

Backtracking

Overview: Backtracking algorithms try to build a solution incrementally, removing solutions that fail to satisfy the constraints of the problem.

Example Algorithms:

• N-Queens Problem
• Sudoku Solver
• Subset Sum Problem

Code Sample: N-Queens Problem

function solveNQueens(n) {
  const solutions = [];
  const board = Array(n).fill(-1);

  function isValid(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i] === col || Math.abs(board[i] - col) === Math.abs(i - row)) {
        return false;
      }
    }
    return true;
  }

  function solve(row) {
    if (row === n) {
      solutions.push(board.slice());
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row] = col;
        solve(row + 1);
        board[row] = -1;
      }
    }
  }

  solve(0);
  return solutions;
}

console.log(solveNQueens(4)); // Output: [ [ 1, 3, 0, 2 ], [ 2, 0, 3, 1 ] ]

Branch and Bound

Overview: Branch and Bound algorithms systematically explore branches of a decision tree, bounding branches that cannot yield a better solution than the current best.

Example Algorithms:

• Traveling Salesman Problem (TSP)
• 0/1 Knapsack Problem
• Job Scheduling Problem

Code Sample: 0/1 Knapsack Problem

class Item {
  constructor(value, weight) {
    this.value = value;
    this.weight = weight;
  }
}

class Node {
  constructor(level, profit, weight, bound) {
    this.level = level;
    this.profit = profit;
    this.weight = weight;
    this.bound = bound;
  }
}

function knapsackBranchAndBound(W, items, n) {
  function bound(u, n, W) {
    if (u.weight >= W) return 0;
    let profitBound = u.profit;
    let j = u.level + 1;
    let totweight = u.weight;

    while (j < n && totweight + items[j].weight <= W) {
      totweight += items[j].weight;
      profitBound += items[j].value;
      j++;
    }

    if (j < n) {
      profitBound += ((W - totweight) * items[j].value) / items[j].weight;
    }

    return profitBound;
  }

  items.sort((a, b) => b.value / b.weight - a.value / a.weight);

  const Q = [];
  const u = new Node(-1, 0, 0, 0.0);
  const v = new Node(0, 0, 0, 0.0);
  Q.push(u);

  let maxProfit = 0;

  while (Q.length) {
    u = Q.shift();

    if (u.level === -1) {
      v.level = 0;
    } else if (u.level === n - 1) {
      continue;
    }

    v.level = u.level + 1;

    v.weight = u.weight + items[v.level].weight;
    v.profit = u.profit + items[v.level].value;

    if (v.weight <= W && v.profit > maxProfit) {
      maxProfit = v.profit;
    }

    v.bound = bound(v, n, W);

    if (v.bound > maxProfit) {
      Q.push(new Node(v.level, v.profit, v.weight, v.bound));
    }

    v.weight = u.weight;
    v.profit = u.profit;
    v.bound = bound(v, n, W);

    if (v.bound > maxProfit) {
      Q.push(new Node(v.level, v.profit, v.weight, v.bound));
    }
  }

  return maxProfit;
}

const items = [new Item(60, 10), new Item(100, 20), new Item(120, 30)];
const W = 50;
const n = items.length;

console.log(knapsackBranchAndBound(W, items, n)); // Output: 220

Comments

Recent Work

Basalt

basalt.software

Free desktop AI Chat client, designed for developers and businesses. Unlocks advanced model settings only available in the API. Includes quality of life features like custom syntax highlighting.

Learn More

BidBear

bidbear.io

Bidbear is a report automation tool. It downloads Amazon Seller and Advertising reports, daily, to a private database. It then merges and formats the data into beautiful, on demand, exportable performance reports.

Learn More