DEV Community: David

Discovering JavaScript's Hidden Secrets: Understanding String Matching Algorithms.

David — Thu, 30 Oct 2025 08:17:59 +0000

Welcome to the Algorithm Series: String Matching Algorithms

Imagine trying to find a single word in a thousand-page book by flipping through every page, scanning every line, and hoping your eyes catch the right sequence of letters.

Now imagine a system that can do the same thing across millions of documents in milliseconds.

That’s the magic of String Matching Algorithms, the invisible engines making modern search possible.

They’re the hidden force behind Google’s lightning-fast searches, code editors that highlight matches as you type, plagiarism detectors that scan billions of texts, and even bioinformatics tools that compare DNA sequences.

String Matching Algorithms, also known as Pattern Matching Algorithms is the process of finding one or more occurrences of a pattern (substring) inside a text (main string). these algorithms teach computers how to “read” and recognize patterns within text.

From validating user input and parsing data to building full-scale search engines, string matching lies at the heart of how machines understand language.

In this article, we’ll peel back the curtain to understand how string matching truly works, explore the mechanics and intuition behind legendary algorithms like Naïve Search, Knuth–Morris–Pratt (KMP), Rabin–Karp, and Boyer–Moore, and implement them step by step using JavaScript — revealing how a few lines of logic can transform raw text into intelligent, searchable data.

Why String Matching Matters

String matching is used everywhere:

Search engines to find keywords in web pages
Chat filters to detect banned words
Bioinformatics to find gene sequences
Compilers to tokenize source code
AI/ML preprocessing to clean and analyze text

Common Categories of String Matching Algorithms

Naïve String Matching Algorithm
Knuth–Morris–Pratt (KMP) Algorithm
Rabin–Karp Algorithm (Hash-Based Search)
Boyer–Moore Algorithm

Naïve String Matching Algorithm

The Naïve approach (also called the Brute-Force String Matching Algorithm) operates by sliding the pattern over the text one character at a time and checking, at each position, whether the pattern matches the substring of the text beginning at that point.

This comparison continues character by character until a mismatch occurs or the entire pattern matches.

How It Works

Start at index 0 of the text and compare each character of P with the corresponding character in T.
If all characters match, record the index as a match position.
If a mismatch occurs, shift the pattern one character to the right and compare again.
Continue this process until the pattern has been aligned with every possible substring of the text.

JavaScript Implementation

function naiveSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const positions = [];

  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) positions.push(i);
  }

  return positions;
}

console.log(naiveSearch("AABAACAADAABAABA", "AABA"));
// Output: [0, 9, 12]

Knuth–Morris–Pratt (KMP) Algorithm

The KMP algorithm is a pattern searching algorithm designed to improve upon the inefficiencies of the Naïve String Matching Algorithm.

It precomputes the Longest Proper Prefix of the pattern which is also a Suffix, allowing the search to skip redundant comparisons.

How It Works

Step 1: Preprocessing Phase (Build the LPS Array)

Before searching, KMP preprocesses the pattern to build the LPS (Longest Proper Prefix which is also a Suffix) array.

This array tells the algorithm how many characters can be skipped after a mismatch occurs.

Prefix → A substring starting at the beginning of the pattern.
Suffix → A substring ending at the end of the pattern.

The LPS value for each position indicates the length of the longest proper prefix that is also a suffix up to that point.

Step 2: Searching Phase

Using the LPS array:

Start comparing the pattern with the text from left to right.
When characters match, move both pointers (text and pattern) forward.
If a mismatch occurs:
- Instead of restarting the pattern from index 0, use the LPS value of the previous pattern index to skip ahead.
Continue this process until the end of the text.

JavaScript Implementation

function computeLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      lps[i++] = ++len;
    } else if (len !== 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  return lps;
}

function kmpSearch(text, pattern) {
  const lps = computeLPSArray(pattern);
  const positions = [];
  let i = 0, j = 0;

  while (i < text.length) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      positions.push(i - j);
      j = lps[j - 1];
    } else if (i < text.length && pattern[j] !== text[i]) {
      j !== 0 ? (j = lps[j - 1]) : i++;
    }
  }

  return positions;
}

console.log(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));
// Output: [10]

Rabin–Karp Algorithm (Hash-Based Search)

The Rabin–Karp Algorithm is a string-searching method that uses hashing to find a pattern inside a text.

Instead of checking each character, it converts substrings into hash values for faster comparison.

How It Works

Compute the hash of the pattern.
Compute the hash of the first window of text (same length as the pattern).
Slide the window one character at a time and update the hash using a rolling hash formula:
- If the hash of the window matches the pattern hash, check the actual substring to confirm.
- Repeat until the end of the text.

JavaScript Implementation

function rabinKarp(text, pattern, prime = 101) {
  const n = text.length;
  const m = pattern.length;
  const d = 256; // number of possible characters
  let h = 1;
  let p = 0; // hash for pattern
  let t = 0; // hash for text
  const result = [];

  for (let i = 0; i < m - 1; i++) h = (h * d) % prime;

  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % prime;
    t = (d * t + text.charCodeAt(i)) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      if (text.slice(i, i + m) === pattern) result.push(i);
    }
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
      if (t < 0) t += prime;
    }
  }

  return result;
}

console.log(rabinKarp("GEEKS FOR GEEKS", "GEEK"));
// Output: [0, 10]

Boyer–Moore Algorithm

The Boyer–Moore Algorithm is one of the fastest and most efficient string matching algorithms in practice.

It compares the pattern from right to left, and when a mismatch occurs, it uses two powerful heuristics to skip over large sections of text — rather than moving just one character at a time.

This makes it especially effective for long texts and complex patterns, often outperforming other algorithms in real-world applications.

How It Works

Start Matching from the Right

The comparison starts from the rightmost character of the pattern and moves leftward.
If all characters match → ✅ Pattern found.
If a mismatch occurs → the algorithm decides how far to shift the pattern using two heuristics:
1. Bad Character Heuristic
2. Good Suffix Heuristic

1. Bad Character Heuristic

When a mismatch occurs at text character c while comparing pattern character P[j]:

If c exists to the left in the pattern, shift the pattern so that the rightmost occurrence of c in the pattern aligns with the mismatched text character.
If c does not exist in the pattern, shift the pattern beyond that character entirely.

This allows Boyer–Moore to skip text characters that could never lead to a match.

Example:

When a mismatch occurs at D, and since D does not appear in "EFG",

the algorithm shifts the pattern past D, skipping unnecessary comparisons.

2. Good Suffix Heuristic

When a mismatch occurs after part of the pattern has matched,

Boyer–Moore uses the matched suffix (called the good suffix) to determine the next shift.

If a portion at the end of the pattern matched:
- Shift the pattern so the next occurrence of that suffix aligns in the text.
If the suffix does not appear elsewhere:
- Shift so that the longest prefix matching the suffix aligns instead.

This heuristic lets Boyer–Moore reuse previously matched information efficiently and skip redundant checks.

JavaScript Implementation

function badCharHeuristic(pattern) {
  const badChar = {};
  for (let i = 0; i < pattern.length; i++) {
    badChar[pattern[i]] = i;
  }
  return badChar;
}

function boyerMooreSearch(text, pattern) {
  const badChar = badCharHeuristic(pattern);
  const n = text.length, m = pattern.length;
  let s = 0;
  const result = [];

  while (s <= n - m) {
    let j = m - 1;

    while (j >= 0 && pattern[j] === text[s + j]) j--;

    if (j < 0) {
      result.push(s);
      s += m - (badChar[text[s + m]] || -1);
    } else {
      s += Math.max(1, j - (badChar[text[s + j]] ?? -1));
    }
  }

  return result;
}

console.log(boyerMooreSearch("ABAAABCD", "ABC"));
// Output: [4]

Conclusion

String matching algorithms may seem simple, but they’re the invisible power behind search engines, code editors, and even DNA analysis.

The Naïve algorithm is easy to understand but slow for large data. KMP improves efficiency by avoiding redundant checks. Rabin–Karp shines when comparing multiple patterns using hashing, while Boyer–Moore excels in practical performance by skipping ahead intelligently.

Beyond theory, these algorithms teach a crucial engineering lesson: the right approach depends on your data and context. Whether you’re building a search feature, validating input, or analyzing text, knowing how these algorithms work gives you the power to make software faster and smarter.

In essence, string matching turns plain text into meaningful information — and understanding it turns a good developer into a great problem solver.

Discovering JavaScript's Hidden Secrets: Understanding Numerical Algorithms.

David — Thu, 30 Oct 2025 08:17:39 +0000

Welcome to the Algorithm Series: Numerical Algorithms

Our journey through "Discovering JavaScript's Hidden Secrets" has reached its final destination. We're incredibly grateful to have shared this exploration with you. For our final series, we're looking at the algorithms that don't just solve problems but build the future.

Imagine a world where we can perfectly simulate the behaviour of new medicines, design hyper-efficient energy grids, or create AI with a deep understanding of complex systems. This vision is rapidly becoming a reality, thanks to a specialized field of computation.

At the heart of this revolution are Numerical Algorithms. They are the quiet, mathematical engines that empower computers to tackle problems in physics, engineering, and finance that were once thought impossible. By translating the elegant language of continuous mathematics into practical, step-by-step digital processes, they unlock solutions that drive innovation.

In this article, we'll explore the core ideas that make these algorithms so powerful. Through clear explanations and practical pseudocode in JavaScript, you will learn how these computational techniques are applied. Join us one last time to discover how mathematics and code unite to engineer a better, smarter world.

By the end, you'll understand how mathematics and computation merge to solve real-world problems.

What Are Numerical Algorithms?

Numerical algorithms are systematic, step-by-step computational methods designed to perform numerical calculations — things like solving equations, integrating functions, or approximating results that are too complex for direct calculation.

Unlike symbolic math (which gives exact answers), numerical algorithms focus on approximation, accuracy, and efficiency, especially for real-world problems where perfect solutions don't exist.

Core Principles to Understand

1. Number Representation

Computers represent numbers using floating-point arithmetic, meaning real numbers are approximated, not exact. This leads to rounding and truncation errors. Understanding how these errors propagate is key to writing stable algorithms.

Example: The number 0.1 cannot be represented exactly in binary — tiny errors add up over millions of computations.

2. Error Analysis

In numerical computing, small mistakes can grow large:

Absolute Error: |x_true - x_approx|
Relative Error: |x_true - x_approx| / |x_true|
Error Propagation: How early errors affect later results

A good numerical algorithm minimizes these errors and ensures results remain reliable even with imperfect inputs.

3. Efficiency and Complexity

Speed matters. Efficiency is measured by:

Time Complexity → How fast the algorithm runs
Space Complexity → How much memory it uses

Essential Numerical Algorithms to Know

Euclidean Algorithm for GCD
Fast Exponentiation (Modular Exponentiation)
Root-Finding Algorithms
Numerical Integration and Differentiation
Optimization Algorithms
Solving Linear Systems

Euclidean Algorithm (for GCD)

The Euclidean Algorithm is one of the oldest and most fundamental algorithms in mathematics, dating back over 2,000 years to ancient Greece. It provides an efficient way to compute the Greatest Common Divisor (GCD) — the largest positive integer that divides two numbers a and b without leaving a remainder.

The core idea behind the algorithm is simple yet powerful: The GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number.

JavaScript Implementation

// Recursive implementation of the Euclidean Algorithm
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

// Example usage
console.log(gcd(48, 18)); // Output: 6

Fast Exponentiation (Modular Exponentiation)

In computational mathematics, directly calculating aᵇ can be extremely inefficient, especially when b is large. Imagine trying to compute something like 7¹⁰⁰⁰⁰⁰⁰ — the number of multiplications would be enormous, and the result far too large to handle in memory.

To solve this, we use Fast Exponentiation, also known as Exponentiation by Squaring. When combined with modular arithmetic, it becomes Modular Exponentiation, which efficiently computes:

aᵇ mod m

This method dramatically reduces computation time by repeatedly squaring and taking remainders at each step, keeping numbers manageable and operations efficient.

Mathematical Concept

The recursive logic behind the algorithm is based on the parity (evenness or oddness) of the exponent b:

If b is even: aᵇ = (aᵇ/²)²
If b is odd: aᵇ = a × (a⁽ᵇ⁻¹⁾/²)²

At each step, the exponent b is halved, reducing the number of multiplications from O(b) to O(log b) — a major performance improvement.

JavaScript Implementation

function modExp(a, b, m) {
  // Base case: anything to the power of 0 is 1
  if (b === 0) return 1;

  // If exponent is even
  if (b % 2 === 0) {
    const half = modExp(a, b / 2, m);
    return (half * half) % m;
  } 
  // If exponent is odd
  else {
    const half = modExp(a, Math.floor(b / 2), m);
    return (a * half * half) % m;
  }
}

// Example usage
console.log(modExp(3, 5, 13));  // Output: 9
console.log(modExp(7, 3, 11));  // Output: 2
console.log(modExp(2, 10, 100)); // Output: 24

Root-Finding Algorithms

In many scientific, engineering, and financial problems, we often face equations that cannot be solved analytically (that is, using algebra alone). In such cases, we turn to root-finding algorithms — numerical methods used to approximate solutions for equations of the form:

f(x) = 0

A root (or zero) of a function is a value of x for which the function equals zero. These algorithms iteratively refine guesses for x until they converge to an acceptable approximation of the true root.

Popular Root-Finding Methods

Below are three commonly used approaches — each with unique strengths and trade-offs.

1. Bisection Method

The Bisection Method is one of the simplest and most reliable root-finding techniques. It works by repeatedly dividing an interval in half and selecting the subinterval in which the sign of f(x) changes — meaning a root must lie within it (by the Intermediate Value Theorem).

Steps

Choose two initial points a and b such that f(a) and f(b) have opposite signs
Compute the midpoint c = (a + b) / 2
Evaluate f(c):
- If f(c) = 0, you've found the root
- If f(a) and f(c) have opposite signs, the root lies in [a, c]
- Otherwise, it lies in [c, b]
Repeat until the result is within a desired tolerance

Pros & Cons

Pros: Simple, stable, guaranteed to converge
Cons: Converges slowly compared to other methods

JavaScript Implementation

function bisection(f, a, b, tolerance = 1e-6, maxIter = 1000) {
  if (f(a) * f(b) >= 0) throw new Error("f(a) and f(b) must have opposite signs");

  let c;
  for (let i = 0; i < maxIter; i++) {
    c = (a + b) / 2;
    if (Math.abs(f(c)) < tolerance) return c;

    if (f(a) * f(c) < 0) b = c;
    else a = c;
  }
  return c;
}

// Example: Solve f(x) = x^3 - x - 2 = 0
console.log(bisection(x => x ** 3 - x - 2, 1, 2)); // Output ≈ 1.521

2. Newton–Raphson Method

This is one of the fastest root-finding methods, using calculus to refine guesses. It approximates the root by iteratively following the tangent line at the current point until it converges to zero.

Formula
x_{n+1} = x_n - f(x_n)/f'(x_n)

Pros & Cons

Pros: Very fast convergence when the starting guess is close to the root
Cons: Requires derivative f'(x); can diverge if the initial guess is poor

JavaScript Implementation

function newtonRaphson(f, df, x0, tolerance = 1e-6, maxIter = 100) {
  let x = x0;F

  for (let i = 0; i < maxIter; i++) {
    const fx = f(x);
    const dfx = df(x);
    if (Math.abs(fx) < tolerance) return x;
    if (dfx === 0) throw new Error("Derivative is zero — method fails.");

    x = x - fx / dfx;
  }
  return x;
}

// Example: f(x) = x^3 - x - 2
console.log(
  newtonRaphson(
    x => x ** 3 - x - 2,
    x => 3 * x ** 2 - 1,
    1.5
  )
); // Output ≈ 1.521

3. Secant Method

The Secant Method is similar to Newton–Raphson but doesn't require the derivative of the function. Instead, it approximates the derivative using the slope of a secant line through two recent points.

Formula
x_{n+1} = x_n - f(x_n) × (x_n - x_{n-1})/(f(x_n) - f(x_{n-1}))

Pros & Cons

Pros: Faster than Bisection and doesn't need f'(x)
Cons: May fail to converge if guesses are poor

JavaScript Implementation

function secant(f, x0, x1, tolerance = 1e-6, maxIter = 100) {
  for (let i = 0; i < maxIter; i++) {
    const f0 = f(x0);
    const f1 = f(x1);
    if (Math.abs(f1) < tolerance) return x1;

    const x2 = x1 - f1 * ((x1 - x0) / (f1 - f0));
    x0 = x1;
    x1 = x2;
  }
  return x1;
}

// Example: f(x) = x^3 - x - 2
console.log(secant(x => x ** 3 - x - 2, 1, 2)); // Output ≈ 1.521

Use Cases

Root-finding algorithms appear across numerous fields:

Engineering simulations: To find equilibrium points, stresses, and voltages
Finance: Calculating interest rates (IRR), option pricing, or break-even points
Scientific computing: Solving nonlinear equations in physics and chemistry models

Numerical Integration (Approximation Methods)

In many real-world scenarios, finding the exact integral of a function analytically is impossible or extremely complex. This is where numerical integration methods — or approximation techniques — come in.

These methods estimate the area under a curve by breaking it into smaller, manageable parts that can be computed efficiently.

Popular Numerical Integration Methods

Below are three of the most popular and widely used numerical integration methods:

1. Trapezoidal Rule

The Trapezoidal Rule approximates the area under a curve by dividing it into trapezoids instead of rectangles. It then sums up the areas of these trapezoids to estimate the integral.

Mathematically:

∫[a to b] f(x) dx ≈ (h/2) × [f(a) + 2 × Σ(i=1 to n-1) f(x_i) + f(b)]

where h = (b - a)/n is the width of each subinterval.

JavaScript Implementation

function trapezoidalRule(f, a, b, n) {
  const h = (b - a) / n;
  let sum = f(a) + f(b);

  for (let i = 1; i < n; i++) {
    sum += 2 * f(a + i * h);
  }

  return (h / 2) * sum;
}

// Example: integrate f(x) = x^2 from 0 to 3
const result = trapezoidalRule(x => x ** 2, 0, 3, 1000);
console.log("Trapezoidal Rule Result:", result.toFixed(4));

2. Simpson’s Rule

Simpson’s Rule provides a more accurate approximation by fitting parabolas through sections of the curve rather than straight lines. It requires that the number of intervals n be even.

Mathematically:

∫[a to b] f(x) dx ≈ (h/3) × [f(a) + 4 × Σ(odd i) f(x_i) + 2 × Σ(even i) f(x_i) + f(b)]

JavaScript Implementation

function simpsonsRule(f, a, b, n) {
  if (n % 2 !== 0) throw new Error("n must be even for Simpson's Rule");
  const h = (b - a) / n;
  let sum = f(a) + f(b);

  for (let i = 1; i < n; i++) {
    sum += f(a + i * h) * (i % 2 === 0 ? 2 : 4);
  }

  return (h / 3) * sum;
}

// Example: integrate f(x) = Math.sin(x) from 0 to π
const resultSimpson = simpsonsRule(Math.sin, 0, Math.PI, 100);
console.log("Simpson’s Rule Result:", resultSimpson.toFixed(4));

3. Monte Carlo Integration

The Monte Carlo Method uses random sampling to estimate the area under a curve. It's particularly useful for high-dimensional integrals or cases where the function is too complex for analytical or deterministic numerical methods.

Mathematically:

∫[a to b] f(x) dx ≈ (b - a) × (1/N) × Σ(i=1 to N) f(x_i)

where x_i are random points between a and b.

JavaScript Implementation

function monteCarloIntegration(f, a, b, n) {
  let sum = 0;
  for (let i = 0; i < n; i++) {
    const x = a + Math.random() * (b - a);
    sum += f(x);
  }
  return ((b - a) / n) * sum;
}

// Example: integrate f(x) = Math.exp(-x*x) from -2 to 2
const resultMonteCarlo = monteCarloIntegration(x => Math.exp(-x * x), -2, 2, 100000);
console.log("Monte Carlo Result:", resultMonteCarlo.toFixed(4));

Use Cases

Numerical Integration algorithms play a vital role in numerous real-world applications, such as:

Estimating areas under complex curves
Solving physics or engineering equations
Data-driven analytics and machine learning
Financial modeling (option pricing, risk estimation)

When exact calculus is impossible, approximation methods step in:

Trapezoidal Rule
Simpson’s Rule
Monte Carlo Integration

Optimization Algorithms

Optimization lies at the heart of machine learning, engineering design, finance, and scientific research. In simple terms, optimization algorithms are methods used to find the minimum or maximum of a function — for example, minimizing loss in a machine learning model or maximizing profit in an investment portfolio.

Mathematically, the problem is often expressed as:

min_x f(x) or max_x f(x)

where f(x) is the objective function we want to optimize.

Because many real-world problems are too complex for exact calculus-based solutions, these algorithms iteratively improve guesses for x to move closer to the optimal point.

1. Gradient Descent

Gradient Descent is one of the most widely used optimization algorithms, especially in machine learning. It works by iteratively moving in the direction of steepest descent — the negative gradient — to minimize the objective function.

Mathematically:
x_{n+1} = x_n - η · f'(x_n)

where η (eta) is the learning rate, controlling the step size.

JavaScript Implementation

function gradientDescent(f, df, x0, learningRate = 0.1, tolerance = 1e-6, maxIter = 1000) {
  let x = x0;

  for (let i = 0; i < maxIter; i++) {
    const grad = df(x);
    const nextX = x - learningRate * grad;

    if (Math.abs(nextX - x) < tolerance) break;
    x = nextX;
  }

  return x;
}

// Example: Minimize f(x) = (x - 3)^2
const f = x => (x - 3) ** 2;
const df = x => 2 * (x - 3);

console.log("Minimum at x ≈", gradientDescent(f, df, 10));

Pros & Cons

Pros: Simple, efficient, and widely applicable
Cons: May get stuck in local minima; choice of learning rate affects performance

2. Newton's Method (for Optimization)

While Gradient Descent uses only the first derivative, Newton's Method also considers the second derivative (curvature) of the function for faster convergence. It adjusts the step size adaptively based on how steep or flat the function is.

Formula
x_{n+1} = x_n - f'(x_n)/f''(x_n)

JavaScript Implementation

function newtonsMethod(f1, f2, x0, tolerance = 1e-6, maxIter = 100) {
  let x = x0;

  for (let i = 0; i < maxIter; i++) {
    const grad = f1(x);
    const hess = f2(x);

    if (Math.abs(grad) < tolerance) break;
    if (hess === 0) throw new Error("Zero curvature — Newton's Method fails.");

    x = x - grad / hess;
  }

  return x;
}

// Example: Minimize f(x) = (x - 2)^2 + 1
const f1 = x => 2 * (x - 2);   // First derivative
const f2 = x => 2;             // Second derivative

console.log("Minimum at x ≈", newtonsMethod(f1, f2, 5));

Pros & Cons

Pros: Fast convergence near the minimum
Cons: Requires computing second derivatives; can diverge with poor initial guesses

3. Simulated Annealing

Inspired by metallurgical annealing, this method explores the search space randomly, accepting worse solutions with a certain probability that decreases over time (the "cooling schedule"). This helps the algorithm escape local minima — something gradient-based methods struggle with.

It's particularly useful for non-convex, discrete, or combinatorial problems (like traveling salesman or scheduling).

JavaScript Implementation (Simplified)

function simulatedAnnealing(f, x0, temp = 100, coolingRate = 0.95, tolerance = 1e-6) {
  let x = x0;
  let best = x;
  let bestVal = f(x);

  while (temp > tolerance) {
    const newX = x + (Math.random() - 0.5) * temp;
    const newVal = f(newX);
    const delta = newVal - bestVal;

    if (delta < 0 || Math.exp(-delta / temp) > Math.random()) {
      x = newX;
      if (newVal < bestVal) {
        best = newX;
        bestVal = newVal;
      }
    }

    temp *= coolingRate; // Gradual cooling
  }

  return best;
}

// Example: Minimize f(x) = (x - 5)^2 + Math.sin(5x)
const f2 = x => (x - 5) ** 2 + Math.sin(5 * x);
console.log("Best solution ≈", simulatedAnnealing(f2, 0));

Pros & Cons

Pros: Can escape local minima; works for complex landscapes
Cons: Computationally slower; requires tuning cooling parameters

4. Genetic Algorithms

Genetic Algorithms (GAs) mimic biological evolution — using operations like selection, crossover, and mutation to evolve a population of candidate solutions toward optimal results.

These algorithms are especially effective for multi-variable, non-differentiable, or discrete optimization problems.

JavaScript Implementation (Simplified)

function geneticAlgorithm(f, popSize = 20, generations = 100, mutationRate = 0.1) {
  let population = Array.from({ length: popSize }, () => Math.random() * 10 - 5);

  for (let gen = 0; gen < generations; gen++) {
    // Evaluate fitness (lower is better)
    const fitness = population.map(x => f(x));
    const sorted = population
      .map((x, i) => [x, fitness[i]])
      .sort((a, b) => a[1] - b[1]);

    // Select top half
    const survivors = sorted.slice(0, popSize / 2).map(([x]) => x);

    // Crossover and mutation
    const newPop = [...survivors];
    while (newPop.length < popSize) {
      const [p1, p2] = [
        survivors[Math.floor(Math.random() * survivors.length)],
        survivors[Math.floor(Math.random() * survivors.length)]
      ];
      let child = (p1 + p2) / 2;
      if (Math.random() < mutationRate) child += (Math.random() - 0.5);
      newPop.push(child);
    }

    population = newPop;
  }

  const best = population.reduce((a, b) => (f(a) < f(b) ? a : b));
  return best;
}

// Example: Minimize f(x) = x^2 + sin(3x)
const f3 = x => x ** 2 + Math.sin(3 * x);
console.log("Optimal x ≈", geneticAlgorithm(f3));

Pros & Cons

Pros: Works on complex, non-differentiable problems
Cons: Slow; requires parameter tuning (population size, mutation rate, etc.)

Use Cases

Optimization algorithms power a vast range of modern applications:

Machine Learning: Minimizing cost or loss functions
Control Systems: Tuning system parameters for stability and performance
Finance: Portfolio optimization, risk minimization
Engineering Design: Reducing material usage or maximizing efficiency
Operations Research: Scheduling, routing, and resource allocation

Solving Linear Systems

In mathematics and computational science, many real-world problems boil down to solving a system of linear equations, often written as:

Ax = b

where:

A is a matrix of coefficients,
x is a vector of unknowns, and
b is a vector of constants.

Linear systems appear everywhere — from machine learning (solving for model parameters) to engineering simulations, computer graphics, and optimization problems.

Popular Methods for Solving Linear Systems

1. Gaussian Elimination (Direct Method)

The Gaussian Elimination method systematically transforms the matrix A into an upper triangular form, then uses back-substitution to find the values of the unknowns. It's a foundational algorithm used in almost all linear algebra libraries.

JavaScript Implementation

function gaussianElimination(A, b) {
  const n = A.length;

  // Forward elimination
  for (let i = 0; i < n; i++) {
    // Pivot for numerical stability
    let maxRow = i;
    for (let k = i + 1; k < n; k++) {
      if (Math.abs(A[k][i]) > Math.abs(A[maxRow][i])) maxRow = k;
    }
    [A[i], A[maxRow]] = [A[maxRow], A[i]];
    [b[i], b[maxRow]] = [b[maxRow], b[i]];

    // Eliminate below
    for (let k = i + 1; k < n; k++) {
      const factor = A[k][i] / A[i][i];
      for (let j = i; j < n; j++) {
        A[k][j] -= factor * A[i][j];
      }
      b[k] -= factor * b[i];
    }
  }

  // Back substitution
  const x = new Array(n).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    let sum = b[i];
    for (let j = i + 1; j < n; j++) {
      sum -= A[i][j] * x[j];
    }
    x[i] = sum / A[i][i];
  }

  return x;
}

// Example: Solve A·x = b
const A = [
  [2, 1, -1],
  [-3, -1, 2],
  [-2, 1, 2]
];
const b = [8, -11, -3];

console.log("Solution (Gaussian Elimination):", gaussianElimination(A, b));

2. LU Decomposition

Instead of transforming the matrix multiple times, LU Decomposition splits A into two simpler matrices:

A = L × U

where:

L is a lower triangular matrix,
U is an upper triangular matrix.

This makes solving for multiple b vectors efficient — useful in machine learning and simulations.

JavaScript Implementation

function luDecomposition(A) {
  const n = A.length;
  const L = Array.from({ length: n }, () => Array(n).fill(0));
  const U = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) {
    for (let k = i; k < n; k++) {
      let sum = 0;
      for (let j = 0; j < i; j++) sum += L[i][j] * U[j][k];
      U[i][k] = A[i][k] - sum;
    }

    for (let k = i; k < n; k++) {
      if (i === k) L[i][i] = 1;
      else {
        let sum = 0;
        for (let j = 0; j < i; j++) sum += L[k][j] * U[j][i];
        L[k][i] = (A[k][i] - sum) / U[i][i];
      }
    }
  }

  return { L, U };
}

// Example
const A2 = [
  [4, 3],
  [6, 3]
];
const { L, U } = luDecomposition(A2);
console.log("L =", L);
console.log("U =", U);

3. Jacobi and Gauss–Seidel Methods (Iterative Methods)

When the system is large or sparse, direct methods become computationally expensive. Iterative methods like Jacobi and Gauss–Seidel approximate solutions by refining guesses over multiple iterations.

JavaScript Implementation

function jacobiMethod(A, b, tolerance = 1e-6, maxIterations = 1000) {
  const n = A.length;
  let x = new Array(n).fill(0);
  let xNew = new Array(n).fill(0);

  for (let iter = 0; iter < maxIterations; iter++) {
    for (let i = 0; i < n; i++) {
      let sum = 0;
      for (let j = 0; j < n; j++) {
        if (i !== j) sum += A[i][j] * x[j];
      }
      xNew[i] = (b[i] - sum) / A[i][i];
    }

    // Check for convergence
    if (xNew.every((val, i) => Math.abs(val - x[i]) < tolerance)) break;
    x = [...xNew];
  }

  return x;
}

// Example
const A3 = [
  [10, -1, 2, 0],
  [-1, 11, -1, 3],
  [2, -1, 10, -1],
  [0, 3, -1, 8]
];
const b3 = [6, 25, -11, 15];
console.log("Jacobi Method Result:", jacobiMethod(A3, b3));

4. Conjugate Gradient Method

The Conjugate Gradient (CG) method is a powerful iterative algorithm optimized for large, sparse, symmetric, and positive-definite systems — common in scientific computing and machine learning.

It converges faster than basic iterative methods for well-conditioned systems.

JavaScript Implementation (Simplified)

function conjugateGradient(A, b, tolerance = 1e-6, maxIterations = 1000) {
  const n = b.length;
  let x = new Array(n).fill(0);
  let r = b.map((val, i) => val - A[i].reduce((sum, aij, j) => sum + aij * x[j], 0));
  let p = [...r];
  let rsOld = r.reduce((sum, val) => sum + val * val, 0);

  for (let i = 0; i < maxIterations; i++) {
    const Ap = A.map(row => row.reduce((sum, val, j) => sum + val * p[j], 0));
    const alpha = rsOld / p.reduce((sum, val, j) => sum + val * Ap[j], 0);
    x = x.map((xi, j) => xi + alpha * p[j]);
    r = r.map((ri, j) => ri - alpha * Ap[j]);

    const rsNew = r.reduce((sum, val) => sum + val * val, 0);
    if (Math.sqrt(rsNew) < tolerance) break;

    p = r.map((ri, j) => ri + (rsNew / rsOld) * p[j]);
    rsOld = rsNew;
  }

  return x;
}

// Example
const A4 = [
  [4, 1],
  [1, 3]
];
const b4 = [1, 2];
console.log("Conjugate Gradient Result:", conjugateGradient(A4, b4));

Use Cases

Solving Linear Systems power a vast range of modern applications:

Machine Learning: Solving systems in linear regression, SVMs, and optimization problems
Physics Simulations: Modeling motion, energy, or stress systems
Computer Graphics: Solving transformation and rendering equations
Optimization & Control Systems: Computing constraints or equilibrium states

Conclusion

As we close this final chapter of “Discovering JavaScript’s Hidden Secrets,” we’ve seen how Numerical Algorithms serve as the bridge between abstract mathematics and real-world innovation. From optimizing complex systems to simulating the forces that shape our world, these algorithms transform theory into tangible impact — one calculation at a time.

Through this journey, you’ve learned how JavaScript, often seen as a web language, can also become a tool for exploring deep computational logic. Whether it’s approximating roots, solving equations, or modeling dynamic systems, numerical computation reminds us that code is more than syntax — it’s a language of discovery.

As we look to the future, remember that every technological breakthrough, every AI model, every engineered system begins with algorithms like these — the invisible foundations of progress. Keep experimenting, keep questioning, and let the blend of mathematics and programming continue to inspire your next innovation.

Discovering JavaScript's Hidden Secrets: Understanding Graph Algorithms.

David — Sun, 31 Aug 2025 12:38:14 +0000

Welcome to the Algorithm Series: Graph Algorithms

When we think of algorithms, sorting and searching often come to mind first because most of the time we feel they are considered the building blocks of computer science. But beyond these foundations lies a more powerful concept: graphs. Graphs aren’t just abstract data structures; they mirror the way our world is connected. Cities and roads, friends on social media, airline routes, even the pathways in our brains — all of these can be represented as graphs.

In this article, we’ll explore how JavaScript can be used to bring graph algorithms to life. From understanding nodes and edges to traversals like BFS and DFS, and finally to real-world applications such as pathfinding and network optimization, you’ll see how graphs unlock solutions to problems that ordinary arrays and objects simply can’t handle.

Understanding Graphs and Graph Algorithms

Before diving into graph algorithms, it’s important to first understand what a graph is as a data structure.

What is a Graph?

A graph is a data structure made up of:

Nodes (or vertices): the objects or points in the graph.
Edges (or connections): the links that connect one node to another.

You can imagine a graph like a map of a city:

The intersections are the nodes.
The roads are the edges that connect those intersections.

For a more detailed explanation of graph data structures, you can check out this article: Understanding Graphs as a Non-Linear Data Structure

What is a Graph Algorithm?

A graph algorithm is a method or set of steps used to solve problems involving graphs. Graph algorithms play a vital role in analyzing and processing graphs across various domains, including: Networking, Social Media, Search Engines, Recommendation Systems, Route Optimization.

Graph algorithms help us work with these connections and answer questions such as:

What’s the fastest route from one point to another?
Which connections are the most important?
How do we find groups or clusters inside a network?

Common categories of Graph Algorithms

Graph Traversal Algorithms
Pathfinding Algorithms
Minimum Spanning Tree (MST) Algorithms

Graph traversal refers to the process of systematically visiting all the nodes and edges in a graph. It is often the first step in understanding a graph’s structure and is divided into two main techniques:

Breadth-First Search (BFS)
Depth-First Search (DFS)

Breadth-First Search (BFS) Breadth-First Search is a fundamental algorithm used for traversing or searching through tree or graph data structures. It starts at a selected node (called the source or root) and explores all of its neighbor nodes at the present depth level before moving on to nodes at the next depth level.

A Visual Example Of Breadth-First Search Algorithm

Traversal Order: A → B → C → D → E → F

JavaScript Implementation

function breadthFirstSearch(graph, startNode) {
  const queue = [startNode];       // Queue to manage nodes
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(`Visiting node: ${current}`);

    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// Example graph (Adjacency List)
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

breadthFirstSearch(graph, 'A');
// Output: A, B, C, D, E, F

Depth-First Search (DFS): Depth-First Search is a fundamental algorithm for traversing or searching tree or graph data structures. The algorithm starts at a selected node (called the source or root) and explores as far as possible along each branch before backtracking.

A Visual Example of Depth-First Search Algorithm

Possible Traversal Order: A → B → D → E → C → F

JavaScript Implementation

function depthFirstSearch(graph, node, visited = new Set()) {
  visited.add(node);
  console.log(`Visiting node: ${node}`);

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      depthFirstSearch(graph, neighbor, visited);
    }
  }
}

// Reuse the same graph
depthFirstSearch(graph, 'A');
// Possible Output: A, B, D, E, F, C

Pathfinding Algorithms: A pathfinding algorithm is a step-by-step procedure designed to find the shortest or most optimal path between two points in a graph. Breadth-First Search (BFS) and the Depth-First Search (DFS) are basic types of Pathfinding Algorithms. Other advanced types of pathfinding algorithms include Dijkstra's Algorithm, Bellman-Ford, and Floyd-Warshall. For the purpose of this article, we will be treating Dijkstra's Algorithm.

Dijkstra's Algorithm: Dijkstra's Algorithm finds the shortest path from a single starting point to all other nodes in a graph. It works on graphs where:

Key Features of Dijkstra's Algorithm

Works on weighted graphs (edges have weights like distance, time, or cost).
Requires non-negative edge weights.
Guarantees the shortest path.

A Visual Example of Dijkstra's Algorithm

         4
    (A) ------> (B)
     |           |
     | 2         | 5
     |           |
    \/          \/
    (C) ------> (D)
         1

Shortest path from A to D: A → C → D with total cost 3.

JavaScript Implementation

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(node, priority) {
    this.heap.push({ node, priority });
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return min;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  updatePriority(node, newPriority) {
    const index = this.heap.findIndex(item => item.node === node);
    if (index === -1) return;
    const oldPriority = this.heap[index].priority;
    this.heap[index].priority = newPriority;
    if (newPriority < oldPriority) this.bubbleUp(index);
    else this.sinkDown(index);
  }

  bubbleUp(index) {
    const element = this.heap[index];
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parent = this.heap[parentIndex];
      if (element.priority >= parent.priority) break;
      this.heap[parentIndex] = element;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let swap = null;
      if (left < length && this.heap[left].priority < element.priority) {
        swap = left;
      }
      if (
        right < length &&
        ((swap === null && this.heap[right].priority < element.priority) ||
          (swap !== null && this.heap[right].priority < this.heap[left].priority))
      ) {
        swap = right;
      }
      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }
}

function dijkstra(graph, source) {
  const dist = {};
  const prev = {};
  const Q = new MinHeap();

  // Initialize distances
  for (const vertex in graph) {
    dist[vertex] = Infinity;
    prev[vertex] = null;
    Q.push(vertex, Infinity);
  }

  // Start node distance = 0
  dist[source] = 0;
  Q.updatePriority(source, 0);

  while (!Q.isEmpty()) {
    const { node: u, priority: currentDist } = Q.pop();
    if (currentDist > dist[u]) continue;

    for (const neighbor in graph[u]) {
      const weight = graph[u][neighbor];
      const alt = dist[u] + weight;
      if (alt < dist[neighbor]) {
        dist[neighbor] = alt;
        prev[neighbor] = u;
        Q.updatePriority(neighbor, alt);
      }
    }
  }

  return { distances: dist, previous: prev };
}

function getShortestPath(prev, target) {
  const path = [];
  let current = target;
  while (current !== null) {
    path.unshift(current);
    current = prev[current];
  }
  return path;
}

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

const result = dijkstra(graph, 'A');
console.log('Distances:', result.distances);
console.log('Previous nodes:', result.previous);

const pathToD = getShortestPath(result.previous, 'D');
console.log('Shortest path to D:', pathToD); // [ 'A', 'C', 'D' ]

Minimum Spanning Tree Algorithm

A Minimum Spanning Tree (MST) is the subset of connections in a weighted network that achieves the absolute lowest total cost for connecting all points, while rigorously avoiding any redundant loops. It guarantees that every single point is included and reachable, yet it forms a efficient "tree" structure where there is only one unique path between any two points, ensuring no resources are wasted on unnecessary connections. A common example of a Minimum Spanning Tree algorithm is Kruskal's Algorithm.

Kruskal's algorithm: Kruskal's Algorithm is a greedy, efficient method for finding an MST by iteratively adding the smallest available edge and using the Union-Find data structure to intelligently avoid cycles, ensuring the result is both spanning and of minimum cost.

A Visual Example of Kruskal's Algorithm

        (A)
     5/  |  \5
    (B) 3|   (C)
     2\  |  /4
        (D)

Steps

Sort edges by weight: BD(2), AD(3), CD(4), AB(5), AC(5).
Pick edges in order, skipping ones that form cycles.
Final MST:
- B–D (2)
- A–D (3)
- C–D (4)

Total Cost = 9

JavaScript Implementation

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array(size).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false;

    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}

Conclusion

Graphs give us a way to map complexity into something we can analyze, optimize, and solve with code. By learning how to implement graph algorithms in JavaScript, we open the door to practical applications like smarter navigation systems and efficient social media recommendations. What begins as a study of nodes and edges soon reveals itself as a tool for tackling some of the biggest challenges in technology and daily life.

As you continue experimenting with graph algorithms, remember: the value isn’t only in writing the code, but in learning to see the world as a network of connections so that you can use that perspective to design smarter solutions.

Discovering JavaScript's Hidden Secrets: Understanding Sorting Algorithms.

David — Fri, 30 May 2025 06:52:46 +0000

Welcome to the Algorithm Series: Sorting Algorithms

This is part of the Discovering JavaScript's Hidden Secrets series. After covering searching algorithms, we now shift our focus to sorting algorithms — a cornerstone of efficient data manipulation and performance optimization in computer science.

What Are Sorting Algorithms?

A sorting algorithm is a step-by-step procedure used to reorder elements in a collection (like an array or list), usually in ascending or descending order. Sorting is essential in computing because it improves the efficiency of search operations, enhances data presentation, and underpins key operations in databases, machine learning pipelines, and UI design.

Why Are Sorting Algorithms Important?

Sorting algorithms are foundational for:

Fast Data Retrieval: Algorithms like Binary Search require sorted data to operate efficiently (O(log n)). Database indexing, autocomplete systems, and filtering rely on sorted structures.
Efficient Processing: Sorting assists in grouping, aggregating, and comparing data. For example, sorting enables streamlined JOIN and ORDER BY operations in SQL.
Enhanced User Experience: Product listings (e.g., by price or rating), recommendation feeds (Netflix, Spotify), and dashboards often rely on sorting to improve usability.
Memory Optimization: Sorted data enables techniques like run-length encoding and improves caching behavior in large systems.

Common Types of Sorting Algorithms

Here are widely-used sorting algorithms, each with its own trade-offs in time complexity, memory use, and implementation style:

Bubble Sort
Insertion Sort
QuickSort
Merge Sort
Heap Sort
Radix Sort

Bubble Sort

A simple, intuitive algorithm that repeatedly compares and swaps adjacent elements if they’re in the wrong order. Best used for small or nearly sorted datasets.

Time Complexity: O(n²)
Design Pattern: Brute Force
Use Case: Small datasets, teaching concept

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

Insertion Sort

Builds the final sorted array one element at a time. Effective on small or nearly sorted datasets.

Time Complexity: O(n²)
Design Pattern: Brute Force
Use Case: Nearly sorted arrays, small input size

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

QuickSort

A fast, recursive algorithm that uses the divide-and-conquer approach by selecting a pivot and partitioning the array around it.

Time Complexity: Best/Average: O(n log n), Worst: O(n²)
Design Pattern: Divide and Conquer
Use Case: General-purpose, large datasets

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[high]] = [arr[high], arr[i]];
  return i;
}

Merge Sort

Another divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and merges the sorted halves.

Time Complexity: O(n log n)
Design Pattern: Divide and Conquer
Use Case: Stable sort, large data with guaranteed performance

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) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

Heap Sort

Uses a binary heap to sort elements by first building a max-heap and then extracting the maximum repeatedly.

Time Complexity: O(n log n)
Design Pattern: Heap-based / Divide and Conquer
Use Case: In-place sort with good worst-case performance

function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr, size, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, size, largest);
  }
}

Radix Sort

A non-comparative sorting algorithm used for sorting integers by processing individual digits.

Time Complexity: O(d × (n + k)), where d is the number of digits
Design Pattern: Digit-by-digit bucketing
Use Case: Large sets of integers or fixed-length strings

function radixSort(arr) {
  const maxDigits = Math.max(...arr).toString().length;
  for (let k = 0; k < maxDigits; k++) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (const num of arr) {
      const digit = Math.floor(num / Math.pow(10, k)) % 10;
      buckets[digit].push(num);
    }
    arr = [].concat(...buckets);
  }
  return arr;
}

Conclusion

Sorting algorithms are not just academic exercises — they are real-world tools used in search engines, databases, e-commerce, and even daily frontend rendering. By understanding their strengths and limitations, you equip yourself to choose the right approach for your application’s needs. From brute force to divide-and-conquer to digit-level bucketing, each algorithm plays a unique role in the programmer’s toolkit.

Keep exploring, keep coding — and remember: every efficient program begins with an efficient sort.

Discovering JavaScript's Hidden Secrets: Understanding Searching Algorithms.

David — Fri, 30 May 2025 02:24:34 +0000

Welcome back to another section of Discovering JavaScript's Hidden Secrets. Having introduced algorithms, we now begin our exploration of searching algorithms—a core part of solving data-related problems in programming.

This part of the series dives into searching algorithms—what they are, why they matter, and how two fundamental types (Linear and Binary Search) work in practice.

What Is a Searching Algorithm?

A searching algorithm is a step-by-step method used to locate a specific element within a collection of data—such as an array, list, tree, graph, or database. The primary goal is to determine whether the target element exists in the dataset and, if it does, return its position or relevant information.

Why Are Searching Algorithms Important?

Searching algorithms are essential in both everyday computing and advanced software systems. They play a major role in:

Databases: Quickly locating records using queries and indexing.
AI & Machine Learning: Efficiently accessing and retrieving relevant data from vast datasets.
Networking: Searching through routing tables, IP addresses, and DNS entries.
User Interfaces: Powering features like file searches, autocomplete suggestions, and command filters.

Types of Searching Algorithms

There are several searching algorithms used in computer science, including:

Linear Search
Binary Search
Hash-Based Search
Tree-Based Search
Advanced Methods (e.g., Interpolation Search, Exponential Search)

In this series, we will focus on two foundational algorithms: Linear Search and Binary Search.

Linear Search

Linear Search (or sequential search) is the simplest search algorithm. It checks each element in a list or array one-by-one until the target value is found or the list ends.

Time Complexity: O(n)
Design Technique: Brute Force
Use Case: Works on unsorted data

Example:

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

// Example usage
const numbers = [4, 2, 7, 1, 9, 3, 6];
const targetNumber = 9;

const result = linearSearch(numbers, targetNumber);

if (result !== -1) {
    console.log(`Element found at index ${result}`);
} else {
    console.log("Element not found in the array");
}

Binary Search

Binary Search is an efficient algorithm that works only on sorted arrays. It repeatedly divides the search range in half, comparing the target value to the middle element.

Time Complexity: O(log n)
Design Technique: Divide and Conquer
Use Case: Requires sorted data

Example:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

// Example usage
const sortedNumbers = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedNumbers, 9)); // Output: 4
console.log(binarySearch(sortedNumbers, 2)); // Output: -1

Conclusion

Searching algorithms are at the heart of data processing, enabling computers to quickly and accurately locate information. Whether you're working with unsorted or sorted data, understanding how to apply linear and binary search is fundamental to writing efficient and responsive code.

In the next section of Discovering JavaScript’s Hidden Secrets, we’ll explore sorting algorithms, diving into their logic, performance, and real-world uses. By mastering these foundational concepts, you'll be better equipped to build high-performance applications and solve complex problems with confidence.

Discovering JavaScript's Hidden Secrets: Understanding Algorithms.

David — Wed, 28 May 2025 09:02:26 +0000

Welcome to the Algorithm Series

Welcome back to another section of Discovering JavaScript's Hidden Secrets. Having explored the basic data structures, we now shift our focus to algorithms, discussing what they are, why they matter, how they differ from problem-solving patterns, and how they shape the software systems we build.

This part of the series will dive into the essence of algorithms, their historical background, their impact on modern computing, and the common design techniques used to build them.

What Is an Algorithm?

An algorithm is a step-by-step procedure for solving a problem or performing a task. The word “algorithm” comes from the name of the 9th-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, who wrote a book in Arabic titled Kitāb al-ḥisāb al-hindī (The Book of Calculation with Hindu Numerals). His methods for arithmetic and algebra were so influential that his name was Latinized as “Algoritmi” in European texts. Over time, the term came to represent any well-defined procedure for solving computational problems.

In computer science, algorithms are used to perform operations like searching, sorting, pathfinding, optimization, and more. These procedures are the backbone of every piece of software, from simple scripts to large-scale applications.

Why Are Algorithms Important in Computing?

Efficiency: A well-designed algorithm significantly reduces the time and resources required to solve a problem. Efficient algorithms make programs faster and more responsive.
Scalability: As systems grow in size and complexity, the underlying algorithms determine whether they can still perform well with large datasets or user bases.
Automation: Algorithms enable systems to operate without constant human intervention, allowing automation in areas like data analysis, robotics, and artificial intelligence.
Foundation of Software Logic: Every program—whether a mobile app, a web service, or an AI system—relies on algorithms to control logic and decision-making.
Economic and Societal Impact: Algorithms power everything from search engines and recommendation systems to financial models and health diagnostics, shaping the way we live and interact with technology.

Algorithm Design Techniques (a.k.a. Problem-Solving Patterns)

These are abstract strategies used to craft algorithms that are efficient, reusable, and adaptable to various problem domains.

1. Brute Force

Brute Force is the most straightforward approach to problem-solving. It involves trying every possible option until the correct one is found.

Pros: Simple to implement.
Cons: Inefficient for large datasets.
Example: Checking every number in a list to find the maximum.

2. Divide and Conquer

This technique involves breaking a problem into smaller subproblems, solving each independently, and then combining their results.

Steps:
- Divide: Split the problem into smaller parts.
- Conquer: Solve each subproblem recursively.
- Combine: Merge the results into a final solution.
Examples: Merge Sort, Quick Sort, Binary Search, Karatsuba Multiplication.

3. Dynamic Programming (DP)

Dynamic Programming solves problems by breaking them down into overlapping subproblems. It stores solutions to subproblems to avoid redundant work.

Use Case: When the same subproblem is solved multiple times.
Key Idea: Memorization (top-down) or tabulation (bottom-up).
Examples: Fibonacci sequence, Longest Common Subsequence, Knapsack Problem.

4. Greedy Algorithms

Greedy algorithms make the best choice at each step, hoping that these local optima will lead to a global optimum.

When to Use: If the problem has the greedy-choice property and optimal substructure.
Examples: Dijkstra’s algorithm, Prim’s algorithm, Huffman Encoding.

5. Backtracking

Backtracking builds candidates for the solution incrementally and abandons a candidate (“backtracks”) as soon as it determines it cannot lead to a valid solution.

Use Cases: Combinatorial problems with constraints.
Examples: N-Queens Problem, Sudoku Solver, Maze Solving.

6. Randomized Algorithms

These algorithms use random inputs or decisions to improve performance or simplify logic. They can have varying outputs even on the same input.

Types:
- Las Vegas: Always produce the correct output; runtime may vary.
- Monte Carlo: May produce incorrect results, but run faster.
Examples: Randomized QuickSort, Probabilistic Primality Testing, Randomized Hashing.

Difference Between Algorithms and Design Techniques

Understanding the distinction between algorithms and problem-solving patterns (or design techniques) is essential:

Algorithms are concrete, step-by-step procedures for solving a specific problem (e.g., Dijkstra’s algorithm for finding shortest paths).
Design Techniques are abstract strategies that guide how to build those algorithms (e.g., Greedy Choice, Divide and Conquer).

You can think of problem-solving patterns as blueprints and algorithms as the actual buildings constructed from those blueprints.

Real-World Applications of Algorithms

Algorithms are behind many of the technologies we use every day:

Search Engines: Ranking pages using PageRank and indexing.
Navigation Apps: Finding optimal paths with shortest-path algorithms.
AI & Machine Learning: Training models using optimization and classification algorithms.
Cybersecurity: Encryption and hashing algorithms for data protection.
Finance: Algorithms for fraud detection, trading strategies, and risk analysis.

Conclusion

Algorithms are not just lines of code—they are logical, structured problem-solving tools that power the digital world. Whether you're sorting a list, finding the shortest path, or training a neural network, algorithms form the bedrock of how solutions are built in computing.

As we continue our journey through Discovering JavaScript’s Hidden Secrets, the following episodes will take a closer look at the fundamental categories of algorithms—such as searching algorithms, sorting algorithms, and more—unpacking how they work, their real-world use cases, and how to implement them effectively in JavaScript.

In this series, we’ve laid the foundation by exploring the fundamental algorithm design techniques. In the upcoming sections, we will explore specific fundamental algorithms, analyzing how they work, where they’re used, and why they matter.

Understanding algorithms isn't just about passing interviews—it's about becoming a better problem-solver, architect, and engineer.

How to 10X Sales for any Product or Service.

David — Wed, 31 Jul 2024 08:56:46 +0000

My uncle Alex and his business partner Charlene were the masterminds behind Niko, a fashion brand that had captured the hearts of millions. Niko wasn’t just a brand; it was a movement that revolutionized both sports and fashion. They had started the business from scratch, driven by a mission to blend fashion with innovation, creating products that were not only functional but also aesthetically pleasing.

However, over the years, competition had intensified, and the fashion market became increasingly crowded. Their profit margins had dropped drastically as competitors began offering similar quality products at lower prices. Alex and Charlene knew they needed something extraordinary to stand out but hadn't figured out what that was yet.

Three months ago, during a school break, I visited my uncle to spend a few weeks with him. Every Sunday evening, Charlene and her family would meet at my uncle's house for a get-together, and this particular Sunday, they were discussing ways to differentiate their brand. I, being part of the meetup, suggested that they needed to create an immersive experience for their audience using illustrations and 3D animations. I explained that by creating a virtual universe, their audience could explore, interact with, and see their products in action.

They embraced this idea with great excitement and immediately began working on it by contracting Uigraphic, the best illustrators and 3D animators in the business. Uigraphic promised to deliver the project in two weeks, and they did not disappoint. Just two days before the deadline, Uigraphic delivered an outstanding project.

The marketing department took over, preparing for the grand unveiling. Niko's headquarters was transformed into a futuristic gallery, with giant screens displaying vibrant illustrations and intricate 3D animations. Uigraphic had created an experience that was more than just a showcase of products; it was a journey into the heart of Niko, a testament to the power of creativity.

In the weeks that followed, the response was overwhelming. Social media buzzed with praise, and sales soared to new heights. More importantly, Niko had strengthened its connection with its audience, proving that they were not just a brand but a beacon of inspiration and innovation. Alex and Charlene knew this was just the beginning. With Uigraphic’s illustrations and 3D animations, they had found the tools to take Niko to the next level.

Judging from the whole story, who should take the credit for transforming the sales?

You can check the Uigraphic website using this link https://uigraphic.com for more information on its product and service.

Discovering JavaScript's Hidden Secrets: Understanding Trees as a Non Linear Data Structure.

David — Fri, 14 Jun 2024 16:28:05 +0000

Welcome back to another section on non-linear data structures. In this episode, we'll explore trees as a type of non-linear data structure. Our focus will be on understanding the fundamental concepts and operations associated with trees.

We'll embark on an exploration of trees, a foundational non-linear data structure widely utilized in computer science. Trees serve as a fundamental data structure, adept at representing hierarchical relationships between entities. Join us as we examine the concepts, properties, and operations that define trees.

Trees: A tree, as the name suggests, is a top-down structure consisting of nodes connected by edges. Trees are hierarchical structures that represent a collection of elements, where each element is connected to one or more elements in a parent-child relationship. Trees are used to model various kinds of data, including file systems, databases, and organizational structures. To understand trees as a data structure, there are some basic terminologies you need to know, which we will be exploring.

Terminologies Used In Tree Data Structure

Node: Node is the basic unit of a tree, which contains data. Each node can have zero or more child nodes.
Edge: An edge is a connection between two nodes, representing the parent-child relationship.
Root: A root refers to the topmost node of a tree, from which all nodes descend. There is only one root in a tree.
Parent: Parent refers to a node that has one or more child nodes.
Child: A child is a node that descends from another node (its parent).
Leaf (or External Node): A leaf refers to a node that does not have any children. It is the end of a path in the tree.
Internal Node: An internal node is a node that has at least one child.
Subtree: A subtree is a portion of a tree that includes a node and all its descendants.

A picture of a tree data structure is shown below

When discussing trees, it's important to note that there are different types of trees, including Binary Trees, Binary Search Trees (BST), Balanced Trees, Heaps, B-trees, and Tries. Let's discuss them in detail.

Binary Tree: A binary node has at most two children (left and right).
Binary Search Tree (BST): A binary search tree is a binary tree with the additional property that the left child is less than the parent node and the right child is greater.
Balanced Trees: A balanced tree is a tree that maintains a balanced structure to ensure efficient operations, like AVL trees and Red-Black trees.
Heaps: These are complete binary trees used to implement priority queues, with properties like the min-heap or max-heap.
B-trees: B-trees are generalizations of binary search trees used in databases and filesystems, designed to work well on storage systems.
Tries: Tries trees are used to store dynamic sets of strings, useful for tasks like autocomplete and spell checking.

An implementation of a tree data structure with various operations is illustrated below.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // Insertion in a Binary Search Tree (BST)
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // In-order Traversal
  inOrderTraversal(node = this.root) {
    if (node !== null) {
      this.inOrderTraversal(node.left);
      console.log(node.value);
      this.inOrderTraversal(node.right);
    }
  }

  // Pre-order Traversal
  preOrderTraversal(node = this.root) {
    if (node !== null) {
      console.log(node.value);
      this.preOrderTraversal(node.left);
      this.preOrderTraversal(node.right);
    }
  }

  // Post-order Traversal
  postOrderTraversal(node = this.root) {
    if (node !== null) {
      this.postOrderTraversal(node.left);
      this.postOrderTraversal(node.right);
      console.log(node.value);
    }
  }

  // Level-order Traversal
  levelOrderTraversal() {
    const queue = [];
    if (this.root !== null) {
      queue.push(this.root);
    }
    while (queue.length > 0) {
      let node = queue.shift();
      console.log(node.value);
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }

  // Search in a Binary Search Tree (BST)
  search(value) {
    return this.searchNode(this.root, value);
  }

  searchNode(node, value) {
    if (node === null) {
      return false;
    }
    if (value < node.value) {
      return this.searchNode(node.left, value);
    } else if (value > node.value) {
      return this.searchNode(node.right, value);
    } else {
      return true;
    }
  }
}

// Example Usage
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);
tree.insert(13);
tree.insert(17);

console.log("In-order Traversal:");
tree.inOrderTraversal(); // 3, 5, 7, 10, 13, 15, 17

console.log("Pre-order Traversal:");
tree.preOrderTraversal(); // 10, 5, 3, 7, 15, 13, 17

console.log("Post-order Traversal:");
tree.postOrderTraversal(); // 3, 7, 5, 13, 17, 15, 10

console.log("Level-order Traversal:");
tree.levelOrderTraversal(); // 10, 5, 15, 3, 7, 13, 17

console.log("Search for 7:");
console.log(tree.search(7)); // true

console.log("Search for 8:");
console.log(tree.search(8)); // false

Conclusion

In this episode, we have extensively discussed trees as a type of non-linear data structure in JavaScript. We implemented a detailed example demonstrating how to create and manipulate trees, covering various operations. This brings us to the end of our discussion on data structures. In the next episode, we'll discuss some common algorithms.

Resources and References

You can check out some of the resources listed below to learn more about trees as a non-linear data structure:

Discovering JavaScript's Hidden Secrets: Understanding Graphs as a Non Linear Data Structure.

David — Fri, 03 May 2024 13:30:26 +0000

Welcome to another section on data structures. In this segment, we'll explore non-linear data structures, which present more intricate relationships between their elements compared to linear structures like stacks and queues, discussed in the previous section. Our focus will be on understanding the fundamental concepts and operations associated with these non-linear structures.

We'll embark on an exploration of graphs, a cornerstone non-linear data structure extensively employed in computer science. Graphs offer a versatile means to represent relationships between objects or entities. Join us as we unravel the concepts, properties, and operations integral to graph

Graphs: A graph, as a type of non-linear data structure, consists of a collection of nodes and edges that connect pairs of nodes. Graphs are a fundamental concept in computer science and are utilized to represent various relationships between objects. As we explore graphs as a topic, it's essential to grasp some key concepts, namely: Nodes and Edges.
- Nodes: Nodes, also known as vertices, are fundamental building blocks of a graph. Each node represents an entity or an object in the graph. For example, in a social network graph, nodes could represent individuals, while in a transportation network, nodes could represent cities or junctions
- Edges: Edges, also known as links, are fundamental components of a graph data structure. They represent the relationships or connections between pairs of nodes. In essence, an edge defines how nodes are related to each other within the graph.

A picture of a graph is shown below

In discussing graphs, it's important to note that there are different types of graphs, which include: directed graphs, undirected graphs, weighted graphs, unweighted graphs, cyclic graphs, and acyclic graphs. Let's discuss them in detail

Directed Graph: A directed graph, also known as a digraph, is a type of graph where edges have a direction associated with them, indicating a specific direction of connection between nodes. Directed graphs depict asymmetric relationships by indicating a specific direction of connection between nodes.
Undirected Graph: An undirected graph is a type of graph in which edges do not have a direction associated with them. Undirected graphs depict symmetric relationships by indicating that the relationship between two nodes is bidirectional.
Weighted Graph: A weighted graph is a type of graph in which each edge has an associated numerical value called a weight or a cost. These weights represent quantitative measures of the relationships between pairs of nodes in the graph. Weighted graphs provide additional information about the strength, distance, or any other relevant metric of the connections between nodes.
Unweighted Graph: An unweighted graph is a type of graph in which edges do not have any associated numerical value or weight. Unweighted graphs simply indicate the presence or absence of connections between pairs of nodes without considering any specific weight or cost associated with those connections.
Cyclic Graph: A cyclic graph is a type of graph that contains at least one cycle, which is a closed path in the graph where the starting node and ending node are the same. In other words, a cyclic graph is a graph that has a sequence of edges that forms a loop, allowing traversal from a node back to itself by following the edges of the cycle.
Acyclic Graph: An acyclic graph, also known as a DAG (Directed Acyclic Graph), is a type of graph that does not contain any cycles. In other words, it is a directed graph in which it is impossible to traverse through the graph and return to the starting node by following the direction of the edges.

An implementation of a graph with various operations is illustrated below.

class Graph {
  constructor() {
    this.vertices = {};
  }
  addVertex(vertex) {
    if (!this.vertices[vertex]) {
      this.vertices[vertex] = [];
    }
  }
  addEdge(vertex1, vertex2) {
    if (!this.vertices[vertex1] || !this.vertices[vertex2]) {
      console.log("Vertex not found");
      return;
    }
    if (!this.vertices[vertex1].includes(vertex2)) {
      this.vertices[vertex1].push(vertex2);
    }
    if (!this.vertices[vertex2].includes(vertex1)) {
      this.vertices[vertex2].push(vertex1);
    }
  }

  removeVertex(vertex) {
    if (!this.vertices[vertex]) {
      console.log("Vertex not found");
      return;
    }
    for (let adjacentVertex of this.vertices[vertex]) {
      this.vertices[adjacentVertex] = this.vertices[adjacentVertex].filter(
        (v) => v !== vertex
      );
    }
    delete this.vertices[vertex];
  }

  removeEdge(vertex1, vertex2) {
    if (!this.vertices[vertex1] || !this.vertices[vertex2]) {
      console.log("Vertex not found");
      return;
    }
    this.vertices[vertex1] = this.vertices[vertex1].filter(
      (v) => v !== vertex2
    );
    this.vertices[vertex2] = this.vertices[vertex2].filter(
      (v) => v !== vertex1
    );
  }

  hasEdge(vertex1, vertex2) {
    if (!this.vertices[vertex1] || !this.vertices[vertex2]) {
      console.log("Vertex not found");
      return false;
    }
    return this.vertices[vertex1].includes(vertex2);
  }

  printGraph() {
    for (let vertex in this.vertices) {
      console.log(vertex + " -> " + this.vertices[vertex].join(", "));
    }
  }
}

// Example usage:
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("A", "C");
graph.printGraph();
// output
// A -> B, C
// B -> A, C
// C -> B, A
console.log("Has edge between A and B:", graph.hasEdge("A", "B")); // true ;
console.log("Has edge between A and C:", graph.hasEdge("A", "C")); // true;
graph.removeVertex("B");
graph.printGraph();
// output
// A -> C
// C -> A

Conclusion

In this segment, we have comprehensively discussed graphs as a type of non-linear data structure in JavaScript. We implemented a detailed example demonstrating how to create and manipulate graphs, covering various operations. In the next episode, we'll explore trees as a type of non-linear data structure.

Resources and References

You can check out some of the resources listed below to learn more about graphs as a non-linear data structure:

Discovering JavaScript's Hidden Secrets: Understanding Stacks and Queues as Linear Data Structures.

David — Fri, 26 Apr 2024 12:15:44 +0000

Welcome to the final episode of our series on linear data structures. In the previous episode, we explored linked lists as a type of data structure and discussed the two main types: singly linked lists and doubly linked lists. Additionally, we implemented typical operations for both types of linked lists.

In this episode, we'll be exploring stacks and queues, which are fundamental linear data structures used in computer science. Let's dive in.

Stacks: A stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle. Think of a stack as a collection of items stacked on top of each other, similar to a stack of plates in a cafeteria. The last plate placed on the stack is the first one to be removed. A picture of a stack is shown below.

An implementation of a stack data structure with its various operations is illustrated below.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  printStack() {
    console.log(this.items.toString());
  }
}

// Example usage:
const stack = new Stack();

console.log("Is stack empty?", stack.isEmpty()); // Output: true

stack.push(10);
stack.push(20);
stack.push(30);

console.log("Stack after pushing 10, 20, and 30:");
stack.printStack(); // Output: [10, 20, 30]

console.log("Peek:", stack.peek()); // Output: 30
console.log("Stack size:", stack.size()); // Output: 3

console.log("popped element:", stack.pop()); // Output: 30

console.log("Stack after popping:");
stack.printStack(); // Output: [10, 20]

Queues: Queues are another fundamental data structure that follows the First In, First Out (FIFO) principle. Unlike stacks, where the last element added is the first to be removed, queues operate on the principle that the first element added is the first to be removed, similar to a line or queue of people waiting for service. A picture of a queue is shown below.

An implementation of a queue data structure with its various operations is illustrated below.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow"; 
    }
    return this.items.shift();
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  printQueue() {
    console.log(this.items.toString());
  }
}

// Example usage:
const queue = new Queue();

console.log("Is queue empty?", queue.isEmpty()); // Output: true

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log("Queue after enqueuing 10, 20, and 30:");
queue.printQueue(); // Output: [10, 20, 30]

console.log("Peek:", queue.peek()); // Output: 10
console.log("Queue size:", queue.size()); // Output: 3

console.log("Dequeued element:", queue.dequeue()); // Output: 10

console.log("Queue after dequeuing:");
queue.printQueue(); // Output: [20, 30]

This concludes our discussion on stacks and queues, as well as our exploration of linear data structures as a whole. In the next episode, we will explore graphs as a non-linear data structure.

Conclusion

In this episode, we have comprehensively discussed stacks and queues as a type of linear data structure in JavaScript. We implemented a detailed example demonstrating how to create and manipulate them, covering various operations. In the next episode, we'll explore graphs as a type of non-linear data structure.

Resources and References

You can check out some of the resources listed below to learn more about stacks and queues as linear data structures:

Discovering JavaScript's Hidden Secrets: Understanding Linked List as Data Structures.

David — Thu, 25 Apr 2024 14:01:06 +0000

Welcome back! In the last episode, we started exploring data structures in detail. We discussed fundamental concepts, including the definition of a data structure, the categories of data structures, and specifically explored arrays as a type of linear data structure.

In this episode, we'll explore Linked Lists as another type of linear data structure.

Linked List:
A linked list is a collection of nodes, with each node containing a data element and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation. This characteristic enables dynamic memory allocation and facilitates efficient insertion and deletion operations. Linked lists can be categorized into two major types: singly linked lists and doubly linked lists.

Singly linked List: A singly linked list is a fundamental data structure widely used in computer science and programming. It consists of nodes, where each node has two components: data and a reference (or pointer) to the next node in the sequence. In a singly linked list, each node points only to the next node in the sequence, with the last node pointing to null, indicating the end of the list. Various operations can be performed on a singly linked list, similar to those on an array. These operations include access, insertion/deletion, traversal, and search. A picture of a singly linked list is shown below.

An implementation of a singly linked list with its various operations is illustrated below.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Insertion at the beginning
  insertFirst(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  // Insertion at the end
  insertLast(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Deletion by value
  delete(value) {
    if (!this.head) return;

    if (this.head.data === value) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next) {
      if (current.next.data === value) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  // Search
  search(value) {
    let current = this.head;
    while (current) {
      if (current.data === value) {
        return true;
      }
      current = current.next;
    }
    return false;
  }

  // Traversal
  printList() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

// Example usage:
const singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.insertFirst(3);
singlyLinkedList.insertFirst(2);
singlyLinkedList.insertFirst(1);
singlyLinkedList.insertLast(4);
singlyLinkedList.insertLast(5);

singlyLinkedList.printList(); // Output: 1 -> 2 -> 3 -> 4 -> 5

singlyLinkedList.delete(3);
console.log('\nLinked List after deleting 3:');
singlyLinkedList.printList(); // Output: 1 -> 2 -> 4 -> 5

console.log('\nIs 4 present in the list?', singlyLinkedList.search(4)); // Output: true
console.log('Is 6 present in the list?', singlyLinkedList.search(6)); // Output: false

Doubly linked lists: A doubly linked list is a data structure similar to a singly linked list, but with the addition of each node containing references to both the next node and the previous node in the sequence. In a doubly linked list, each node has three fields: data, a pointer to the next node (often called 'next'), and a pointer to the previous node (often called 'prev'). This bidirectional linkage allows traversal in both forward and backward directions. Various operations can be performed on a doubly linked list, similar to those on an array. These operations include access, insertion/deletion, traversal, and search. A picture of a doubly linked list is shown below.

An implementation of a doubly linked list with its various operations is illustrated below.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // Insertion at the beginning
  insertFirst(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  // Insertion at the end
  insertLast(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  // Deletion by value
  delete(value) {
    if (!this.head) return;

    let current = this.head;
    while (current) {
      if (current.data === value) {
        if (current === this.head && current === this.tail) {
          this.head = null;
          this.tail = null;
        } else if (current === this.head) {
          this.head = current.next;
          this.head.prev = null;
        } else if (current === this.tail) {
          this.tail = current.prev;
          this.tail.next = null;
        } else {
          current.prev.next = current.next;
          current.next.prev = current.prev;
        }
        return;
      }
      current = current.next;
    }
  }

  // Search
  search(value) {
    let current = this.head;
    while (current) {
      if (current.data === value) {
        return true;
      }
      current = current.next;
    }
    return false;
  }

  // Traversal forward
  printListForward() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  // Traversal backward
  printListBackward() {
    let current = this.tail;
    while (current) {
      console.log(current.data);
      current = current.prev;
    }
  }
}

// Example usage:
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.insertFirst(3);
doublyLinkedList.insertFirst(2);
doublyLinkedList.insertFirst(1);
doublyLinkedList.insertLast(4);
doublyLinkedList.insertLast(5);

console.log('Forward Traversal:');
doublyLinkedList.printListForward(); // Output: 1 -> 2 -> 3 -> 4 -> 5

console.log('\nBackward Traversal:');
doublyLinkedList.printListBackward(); // Output: 5 -> 4 -> 3 -> 2 -> 1

doublyLinkedList.delete(3);
console.log('\nList after deleting 3:');
doublyLinkedList.printListForward(); // Output: 1 -> 2 -> 4 -> 5

This concludes our discussion on Linked Lists. In the next episode, we will explore Stacks and Queues as additional data structures.

Conclusion

In this episode, we have comprehensively discussed linked lists as a type of linear data structure in JavaScript. We explored their main types and implemented a detailed example demonstrating how to create and manipulate linked lists, covering various operations. In the next episode, we'll continue our exploration by discussing stacks and queues, which are also linear data structures.

Resources and References

You can check out some of the resources listed below to learn more about linked list as a linear data structure:

Discovering JavaScript's Hidden Secrets: Understanding Arrays as a Data Structure.

David — Sat, 10 Feb 2024 12:18:23 +0000

One of the essential attributes of a proficient Software Engineer or Data Engineer is the ability to choose suitable data structures that match the characteristics of the data being processed. Regrettably, this skill isn't universally prioritized among engineers, who often focus more on solving immediate problems rather than considering the most efficient data structure for the task at hand.

A thorough grasp of data structures empowers engineers to tackle problems with optimal efficiency. It's crucial to revisit our earlier lesson on Big O notation, emphasizing the significance of algorithmic efficiency in terms of both time and space complexity. In this context, 'space' directly relates to the careful selection of data structures used to address the given problem.

In this episode, we'll explore data structures in detail, a crucial concept essential for comprehending algorithmic efficiency and performance

Prerequisites

To fully understand data structures in JavaScript, it's essential to have a strong foundation in JavaScript fundamentals. This includes mastery of basic syntax, variables, data types, control flow structures, functions, and scope.

What is a Data Structure?

A data structure is a method of organizing and storing data in a computer, facilitating efficient organization, management, and manipulation of information. Data structures enable data to be accessed and modified efficiently, optimizing operations such as insertion, deletion, searching, and sorting. Understanding data structures is crucial for efficient programming and problem-solving in computer science.

Data structures can be mainly categorized into three types:

Primitive Data Structures
Linear Data Structures
Non-linear Data Structures

Primitive Data Structures: Primitive data structures, also referred to as basic data structures, are essential components used to represent and store data in computer memory. They consist of simple, predefined data types provided by programming languages to store raw data values efficiently. These structures are directly supported by hardware and are typically implemented within the language's syntax. Examples of primitive data structures include integers, floating-point numbers, characters, and boolean values. In JavaScript, additional primitive types such as null, undefined, BigInt, Symbol, and infinity are also available

Linear Data Structures: Linear data structures are a type of data structure in which data elements are organized sequentially, with each element connected to its previous and next element. The elements are arranged in a linear order, meaning that each element has exactly one predecessor and one successor, except for the first and last elements. Examples include arrays, linked lists, stacks, and queues.

Non-linear Data Structures: Non-linear data structures are data structures in which elements are not organized sequentially or in a linear order. Unlike linear data structures, where each element has a single predecessor and successor, non-linear data structures allow for more complex relationships between elements, such as branching or hierarchical structures. These structures are essential for representing relationships between data in a variety of applications, including hierarchical data, graphs, trees, and more.

In the upcoming lessons, we will extensively discuss other examples of linear data structures. However, in this lesson, we will focus specifically on arrays

Arrays: - Arrays: An array is one of the fundamental data structures in computer science, commonly used for storing collections of elements, such as numbers or strings, that are accessed by indices. It provides a way to store multiple elements of the same data type in a contiguous block of memory, with each element occupying a fixed-size memory space.

A picture of Array is shown below.

There are various operations that can be performed on an array, including:

Access: Elements in an array are accessed using their indices. Accessing an element at a specific index typically has a time complexity of O(1), as it involves a simple calculation to determine the memory address of the desired element.
Insertion/Deletion: Insertion and deletion operations in arrays can be costly, especially if they require shifting elements to accommodate the change. In the worst-case scenario, these operations have a time complexity of O(n), where n is the number of elements in the array.
Traversal: Arrays can be traversed sequentially to perform operations on each element. This is commonly done using loops, such as for loops, iterating over each index of the array.
Search: Searching for an element in an array typically involves iterating through each element sequentially until the desired element is found. In the worst-case scenario, this operation has a time complexity of O(n), where n is the number of elements in the array.

Types of Arrays

One-dimensional Arrays: These are the simplest form of arrays where elements are arranged in a single row or column.
Multi-dimensional Arrays: Arrays can have multiple dimensions, forming a matrix-like structure. Common examples include two-dimensional arrays (rows and columns) and three-dimensional arrays (rows, columns, and depth).

The basic implementation of an array data structure using JavaScript is illustrated below.

class Array {
  constructor() {
    this.length = 0;
    this.data = {};
  }
  // Get element at index
  get(index) {
    return this.data[index];
  }

  // Push element to end of array
  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  // Pop element from end of array
  pop() {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }

  // Delete element at index
  delete(index) {
    const deletedItem = this.data[index];
    this.shift(index);
    return deletedItem;
  }

  // Helper function to shift items to the left after deletion
  shift(index) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
  }
}

// Example usage:
const array = new Array();
array.push(1);
array.push(2);
array.push(3);
array.pop();
console.log(array);
// resilt: Array { length: 2, data: { '0': 1, '1': 2 } }

This brings us to the end of this episode. In the next episode, we will explore linked lists as a data structure.

Conclusion

In this episode, we covered the fundamentals of data structures, with a focus on arrays in JavaScript. We explored their key operations, types, and practical implementations. Mastering these concepts is essential for efficient programming. In the next episode, we'll delve into linked lists, continuing our journey through fundamental data structures.

Resources and References

You can check out some of the resources listed below to learn more about Data structures.