📐

Algorithms Professional

Advanced DP, minimum spanning trees, Bellman-Ford, Floyd-Warshall, amortised analysis, NP-completeness, reductions, and lower bounds.

8 lessons 19 tasks

Lessons Quiz Certificate

📚 Lessons

1 Minimum Spanning Trees — Kruskal and Prim

A minimum spanning tree (MST) of a connected weighted undirected graph is a spanning tree with minimum total edge weight.

Cut property: for any cut (S, V−S), the minimum-weight edge crossing the cut belongs to some MST. Both algorithms are applications of this property.

Kruskal's algorithm: sort edges by weight O(E log E), then add the next lightest edge if it doesn't create a cycle (Union-Find). Total: O(E log E).

Prim's algorithm: like Dijkstra but keys are edge weights. With a binary heap: O((V + E) log V). With a Fibonacci heap: O(E + V log V).

// Kruskal's MST using Union-Find
function kruskal(n, edges) {
  // edges = [[u, v, w], ...], vertices 0..n-1
  const parent = Array.from({length: n}, (_, i) => i);
  function find(x) { return parent[x] === x ? x : (parent[x] = find(parent[x])); }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb; return true;
  }
  edges.sort((a, b) => a[2] - b[2]);
  const mst = [];
  for (const [u, v, w] of edges)
    if (union(u, v)) mst.push([u, v, w]);
  return mst;
}
// Total MST weight:
const mstEdges = kruskal(4, [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,3]]);
console.log(mstEdges.reduce((s, e) => s + e[2], 0)); // 6

2 Bellman-Ford and Floyd-Warshall

Bellman-Ford computes single-source shortest paths and handles negative edge weights. It relaxes all E edges V−1 times.

For k = 1 to V−1:
  for each edge (u,v,w): relax d[v] = min(d[v], d[u]+w)
Detect negative cycles: if any edge still relaxes after V−1 rounds,
  a negative cycle is reachable from the source.

Complexity: O(VE).

Floyd-Warshall computes all-pairs shortest paths in O(V³):

for k ← 1 to V:
  for i ← 1 to V:
    for j ← 1 to V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Correctness: after considering k as an intermediate vertex, dist[i][j] is the shortest path using only vertices {1 … k} as intermediates.

// Bellman-Ford — O(VE)
function bellmanFord(n, edges, src) {
  const dist = Array(n).fill(Infinity);
  dist[src] = 0;
  for (let k = 0; k < n - 1; k++)
    for (const [u, v, w] of edges)
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  // Detect negative cycles
  for (const [u, v, w] of edges)
    if (dist[u] + w < dist[v]) throw new Error('Negative cycle detected');
  return dist;
}
const edges = [[0,1,4],[0,2,5],[1,2,-3],[2,3,2]];
console.log(bellmanFord(4, edges, 0)); // [0,4,1,3]

3 Advanced Dynamic Programming — Edit Distance

Edit distance (Levenshtein distance) between strings A and B is the minimum number of insertions, deletions, and substitutions to transform A into B.

dp[i][j] = edit distance between A[0..i-1] and B[0..j-1]

Base: dp[i][0] = i, dp[0][j] = j

Recurrence:
  if A[i-1] = B[j-1]:   dp[i][j] = dp[i-1][j-1]
  else: dp[i][j] = 1 + min(dp[i-1][j],    // delete from A
                            dp[i][j-1],    // insert into A
                            dp[i-1][j-1])  // substitute

Complexity: O(|A| · |B|) time and space (O(min(|A|,|B|)) space with rolling rows)

// Edit distance — O(m*n)
function editDistance(a, b) {
  const m = a.length, n = b.length;
  // dp[i][j] = edit dist between a[0..i-1] and b[0..j-1]
  const dp = Array.from({length: m + 1}, (_, i) =>
    Array.from({length: n + 1}, (_, j) => i || j ? (i === 0 ? j : (j === 0 ? i : 0)) : 0)
  );
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
  return dp[m][n];
}
console.log(editDistance('kitten', 'sitting')); // 3

4 Amortised Analysis

Amortised analysis averages the cost of a sequence of operations over the entire sequence, giving a more accurate per-operation cost than worst-case analysis applied to each operation independently.

Three methods:

Aggregate: total cost / n operations
Accounting: assign amortised costs; excess is "credit" stored for future expensive ops
Potential method: define Φ (potential), amortised cost = actual cost + ΔΦ

Example — dynamic array (doubling): each push costs O(1) amortised even though occasional resizes cost O(n). Using aggregate method: n pushes cost at most 3n total operations (n insertions + at most n copies + amortised ≤ n more), so O(1) per push.

// Dynamic array to illustrate amortised O(1) push
class DynArray {
  constructor() { this.data = new Array(1); this.size = 0; this.copies = 0; }
  push(v) {
    if (this.size === this.data.length) {
      const old = this.data;
      this.data = new Array(this.data.length * 2);
      for (let i = 0; i < old.length; i++) { this.data[i] = old[i]; this.copies++; }
    }
    this.data[this.size++] = v;
  }
}
const da = new DynArray();
for (let i = 0; i < 16; i++) da.push(i);
console.log('copies:', da.copies); // 15 = n-1 → O(1) amortised per push

5 Lower Bounds — Sorting is Ω(n log n)

Any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case. The proof uses a decision tree argument:

A sorting algorithm on n elements corresponds to a binary decision tree where each internal node is a comparison A[i] vs A[j].
There are n! possible orderings (leaves), so the tree has at least n! leaves.
A binary tree of height h has at most 2ʰ leaves, so h ≥ log₂(n!).
By Stirling's approximation: log₂(n!) = Θ(n log n).

This shows merge sort and heap sort are asymptotically optimal among comparison-based sorts. Non-comparison sorts (counting sort, radix sort) can achieve O(n) by exploiting the structure of the keys.

// Counting sort — O(n + k) where k = range of values
function countingSort(arr, k) {
  const count = new Array(k + 1).fill(0);
  for (const v of arr) count[v]++;
  const out = [];
  for (let v = 0; v <= k; v++)
    for (let i = 0; i < count[v]; i++) out.push(v);
  return out;
}
console.log(countingSort([3,1,4,1,5,9,2,6,5,3,5], 9));
// [1,1,2,3,3,4,5,5,5,6,9]

6 NP-Completeness and P vs NP

P is the class of decision problems solvable in polynomial time. NP is the class of decision problems whose solutions can be verified in polynomial time. P ⊆ NP; whether P = NP is the most famous open problem in computer science.

NP-hard: at least as hard as every problem in NP. NP-complete: NP-hard AND in NP.

Reduction: problem A reduces to B if every A-instance can be transformed into a B-instance in polynomial time such that answers correspond. If B is in P and A reduces to B, then A is in P.

Classic NP-complete problems: SAT, 3-SAT, vertex cover, clique, Hamiltonian cycle, travelling salesman (decision form), subset sum, 0/1 knapsack.

Cook's theorem (1971): SAT is NP-complete.
Every NP problem polynomial-time reduces to SAT.

// Subset-sum (NP-complete) — exponential brute force vs DP pseudo-poly
// DP approach O(n * target):
function subsetSum(nums, target) {
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const n of nums)
    for (let s = target; s >= n; s--)
      dp[s] = dp[s] || dp[s - n];
  return dp[target];
}
console.log(subsetSum([3, 1, 4, 1, 5, 9], 14)); // true (5+9 or 1+4+9...)
console.log(subsetSum([3, 1, 4, 1, 5, 9], 2));  // false

7 Advanced Graph Techniques — Topological Sort and SCCs

Topological sort orders vertices of a DAG (directed acyclic graph) so that for every edge (u,v), u appears before v. Applications: build systems, course scheduling, dependency resolution.

Kahn's algorithm: repeatedly enqueue vertices with in-degree 0, reduce neighbours' in-degrees. O(V + E). If fewer than V vertices are processed, the graph has a cycle.

Strongly Connected Components (SCCs): a maximal set of vertices where each is reachable from every other. Kosaraju's algorithm: two DFS passes, O(V + E). Tarjan's algorithm: single DFS using a stack and low-link values, O(V + E).

// Kahn's topological sort — O(V + E)
function topoSort(n, adj) {
  const inDeg = new Array(n).fill(0);
  for (let u = 0; u < n; u++)
    for (const v of (adj[u] ?? [])) inDeg[v]++;
  const queue = [];
  for (let i = 0; i < n; i++) if (inDeg[i] === 0) queue.push(i);
  const order = [];
  while (queue.length) {
    const u = queue.shift(); order.push(u);
    for (const v of (adj[u] ?? []))
      if (--inDeg[v] === 0) queue.push(v);
  }
  if (order.length < n) throw new Error('Cycle detected');
  return order;
}
// DAG: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1
const adj = [[],[],[3],[1],[0,1],[2,0]];
console.log(topoSort(6, adj)); // valid topo order

8 String Algorithms — KMP and Rabin-Karp

Naive string matching tries every starting position: O((n−m+1)·m) worst case, where n = text length, m = pattern length.

KMP (Knuth-Morris-Pratt): precomputes a failure function π[j] = length of longest proper prefix of pattern[0..j] that is also a suffix. This allows the search to skip ahead without re-examining text characters. Total: O(n + m).

Rabin-Karp: hashes the pattern and each text window. On a hash match, verify character by character. Average O(n + m); worst-case O(nm) with many hash collisions, but rare with a good hash. Excellent for multi-pattern search.

// KMP string search — O(n + m)
function kmpSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  // Build failure function
  const pi = new Array(m).fill(0);
  for (let i = 1, k = 0; i < m; i++) {
    while (k > 0 && pattern[k] !== pattern[i]) k = pi[k - 1];
    if (pattern[k] === pattern[i]) k++;
    pi[i] = k;
  }
  const matches = [];
  for (let i = 0, k = 0; i < n; i++) {
    while (k > 0 && pattern[k] !== text[i]) k = pi[k - 1];
    if (pattern[k] === text[i]) k++;
    if (k === m) { matches.push(i - m + 1); k = pi[k - 1]; }
  }
  return matches;
}
console.log(kmpSearch('ababcabcabababd', 'ababd')); // [9]

📝 Tasks

19 tasks across 7 pages — multiple-choice and fill-in (type the answer). Score 70% or higher to earn your certificate.

🎓 Certificate of Completion

🔒 Pass the quiz above (70%+) to unlock your downloadable certificate.