⌬ Aytict Academy
📐

Algorithms Advanced

Graph algorithms (BFS, DFS, Dijkstra), dynamic programming, greedy algorithms, heaps, and a precise treatment of Θ, O, and Ω.

8 lessons 19 tasks
Lessons Quiz Certificate

📚 Lessons

1 Θ, O, and Ω — Precise Definitions

The three standard asymptotic notations capture tight, upper, and lower bounds:

  • O(g(n)) — upper bound: f(n) ≤ c·g(n) for all n ≥ n₀
  • Ω(g(n)) — lower bound: f(n) ≥ c·g(n) for all n ≥ n₀
  • Θ(g(n)) — tight bound: c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀

f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) AND f(n) = Ω(g(n)). Always prefer Θ when you have a tight bound; say O only when an upper bound is all that is known.

Example: bubble sort comparisons = n(n-1)/2
  Upper bound: O(n²)   (since n(n-1)/2 ≤ n²)
  Lower bound: Ω(n²)   (since n(n-1)/2 ≥ n²/4 for n ≥ 2)
  Tight:       Θ(n²)
// Verify Theta(n^2) for bubble sort comparison count
function bubbleComparisons(n) {
  return n * (n - 1) / 2;
}
for (const n of [10, 100, 1000]) {
  const ratio = bubbleComparisons(n) / (n * n);
  console.log(n, ratio.toFixed(3)); // converges to 0.5 — so Θ(n²)
}

2 Breadth-First Search (BFS) — O(V + E)

BFS explores a graph level by level starting from a source vertex. It uses a queue and marks vertices as visited to avoid cycles.

Correctness: BFS visits every vertex reachable from the source and computes the shortest path (in number of edges) to each. The key invariant is that the queue holds vertices in non-decreasing order of their distance from the source.

Complexity: each vertex is enqueued once O(V) and each edge is examined once O(E), giving O(V + E). Space: O(V) for the visited set and queue.

// BFS on an adjacency list
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue   = [start];
  const order   = [];
  while (queue.length) {
    const v = queue.shift();   // O(n) with arrays — use a real queue for O(1)
    order.push(v);
    for (const w of (graph[v] ?? [])) {
      if (!visited.has(w)) { visited.add(w); queue.push(w); }
    }
  }
  return order;
}
const g = { A: ['B','C'], B: ['D'], C: ['D','E'], D: [], E: [] };
console.log(bfs(g, 'A')); // A B C D E

3 Depth-First Search (DFS) — O(V + E)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or the call stack via recursion).

Uses: topological sort, cycle detection, connected components, strongly connected components (Kosaraju/Tarjan).

Timestamps: DFS records a discovery time d[v] and finish time f[v] for each vertex. The parenthesis theorem states that the intervals [d[u], f[u]] and [d[v], f[v]] are either disjoint or one contains the other — they never partially overlap.

Complexity: O(V + E) for adjacency-list representation.

// Recursive DFS with pre/post order tracking
function dfs(graph, start) {
  const visited = new Set();
  const pre = [], post = [];
  function visit(v) {
    visited.add(v); pre.push(v);
    for (const w of (graph[v] ?? []))
      if (!visited.has(w)) visit(w);
    post.push(v);
  }
  visit(start);
  return { pre, post };
}
const g = { A: ['B','C'], B: ['D'], C: ['D'], D: [] };
console.log(dfs(g, 'A'));
// pre:  [A,B,D,C]   post: [D,B,C,A]

4 Dijkstra's Shortest Path — O((V + E) log V)

Dijkstra's algorithm finds shortest paths from a source in a weighted graph with non-negative edge weights. It uses a min-priority queue (binary heap) and a distance array d[].

Invariant: when a vertex u is extracted from the priority queue, d[u] is the true shortest distance from the source.

Correctness relies on non-negative weights: once u is finalized, no shorter path can arrive later (because all future paths only add more non-negative weight).

Complexity: O((V + E) log V) with a binary heap; O(V² ) with a simple array (better for dense graphs).

// Dijkstra using a simple priority queue (array-based for clarity)
function dijkstra(graph, src) {
  const dist = {};
  const visited = new Set();
  for (const v in graph) dist[v] = Infinity;
  dist[src] = 0;
  // graph[u] = [[v, weight], ...]
  while (true) {
    // extract min (O(V) scan — use a heap for O(log V))
    let u = null;
    for (const v in dist)
      if (!visited.has(v) && (u === null || dist[v] < dist[u])) u = v;
    if (u === null || dist[u] === Infinity) break;
    visited.add(u);
    for (const [v, w] of (graph[u] ?? [])) {
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
  }
  return dist;
}

5 Dynamic Programming — Principles

Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure. Two conditions must hold:

  1. Optimal substructure: an optimal solution to the problem contains optimal solutions to subproblems.
  2. Overlapping subproblems: the same subproblems recur many times (unlike divide-and-conquer where subproblems are independent).

Approaches: top-down (memoisation — recursion + cache) or bottom-up (tabulation — fill a table iteratively). DP converts exponential naive recursion to polynomial time by storing subproblem answers.

Example — Fibonacci naive: T(n) = T(n-1) + T(n-2) + O(1) → O(2ⁿ)
       With memoisation: each F(k) computed once → O(n)
// Fibonacci: naive O(2^n) vs. memoised O(n)
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2); // exponential!
}
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}
console.log(fibMemo(40)); // instant; fibNaive(40) takes seconds

6 DP — 0/1 Knapsack and LIS

0/1 Knapsack: given n items with weights w[i] and values v[i] and capacity W, maximise total value without exceeding capacity. DP table: dp[i][c] = best value using first i items with capacity c.

dp[i][c] = max(dp[i-1][c],   // skip item i
               dp[i-1][c-w[i]] + v[i])  // take item i, if w[i] ≤ c
Complexity: O(n · W) time and space

Longest Increasing Subsequence (LIS): dp[i] = length of LIS ending at index i. dp[i] = 1 + max(dp[j]) for all j < i with A[j] < A[i]. O(n²). A patience-sorting approach achieves O(n log n).

// LIS — O(n^2) DP
function lis(arr) {
  const n = arr.length;
  const dp = Array(n).fill(1);
  for (let i = 1; i < n; i++)
    for (let j = 0; j < i; j++)
      if (arr[j] < arr[i] && dp[j] + 1 > dp[i])
        dp[i] = dp[j] + 1;
  return Math.max(...dp);
}
console.log(lis([10, 9, 2, 5, 3, 7, 101, 18])); // 4 → [2,3,7,18] or [2,5,7,101]

7 Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a global optimum. Greedy works when the problem has the greedy-choice property (a local optimum leads to a global one) and optimal substructure.

Classic examples where greedy is optimal:

  • Activity selection: always pick the activity that finishes earliest.
  • Huffman coding: always merge the two least-frequent symbols.
  • Fractional knapsack: take items in decreasing value-to-weight ratio order.

Greedy fails for the 0/1 knapsack — you cannot always take the best ratio item without exceeding capacity. An exchange argument or a matroid structure proves greedy correctness.

// Activity selection — greedy: sort by finish time, pick non-overlapping
function activitySelection(activities) {
  // activities = [{start, end}, ...]
  const sorted = [...activities].sort((a, b) => a.end - b.end);
  const chosen = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i].start >= chosen[chosen.length - 1].end)
      chosen.push(sorted[i]);
  }
  return chosen;
}
const acts = [{start:1,end:4},{start:3,end:5},{start:0,end:6},{start:5,end:7}];
console.log(activitySelection(acts)); // [{start:1,end:4},{start:5,end:7}]

8 Heaps and Priority Queues

A binary heap is a complete binary tree satisfying the heap property: every node's key ≤ its children (min-heap). Stored as an array where children of index i are at 2i+1 and 2i+2.

  • Insert (sift-up): O(log n)
  • Extract-min (sift-down): O(log n)
  • Build heap from n elements: O(n) — not O(n log n)!

Proof of O(n) build: most nodes are near the bottom and sift down only a few levels. The total cost is Σₕ (n/2ʰ⁺¹)·O(h) = O(n·Σₕ h/2ʰ) = O(n·2) = O(n).

Heap sort: build heap O(n), then extract-min n times O(n log n) → O(n log n) total, O(1) space.

// Min-heap (using JS array, manual sift)
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    if (this.h.length === 1) return this.h.pop();
    const min = this.h[0];
    this.h[0] = this.h.pop();
    let i = 0;
    while (true) {
      let s = i;
      for (const c of [2*i+1, 2*i+2])
        if (c < this.h.length && this.h[c] < this.h[s]) s = c;
      if (s === i) break;
      [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s;
    }
    return min;
  }
}

📝 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.