algorithms-education

name

algorithms-education

description

Skills and conventions for an educational algorithms and data structures repository. Use this skill whenever working on algorithm implementations, data structure code, LeetCode-style problems, graph theory, dynamic programming, or any Java-based educational coding project. Trigger on mentions of: algorithms, data structures, graph theory, sorting, searching, trees, DP, BFS, DFS, linked lists, heaps, segment trees, union-find, or any request to write, refactor, document, or test educational code. Also trigger when the user asks to "clean up", "simplify", "document", "refactor" or "add tests" to algorithm code.

Algorithms Education Skills

This skill defines the conventions and standards for an educational algorithms repository. The goal is to make every algorithm implementation clear, well-tested, and accessible to learners who may not have deep CS backgrounds.

---

Skill 1: Code Documentation

Goal: Every file should teach, not just implement.

Method-Level Documentation

Every public method gets a doc comment that explains:

1. What the method does (in plain English, one sentence)
2. How it works (brief description of the approach/algorithm)
3. Parameters — what each input represents
4. Returns — what the output means
5. Time/Space complexity — always include Big-O

/**
 * Finds the shortest path from a source node to all other nodes
 * using Bellman-Ford's algorithm. Unlike Dijkstra's, this handles
 * negative edge weights and detects negative cycles.
 *
 * @param graph - adjacency list where graph[i] lists edges from node i
 * @param start - the source node index
 * @param n     - total number of nodes in the graph
 * @return dist array where dist[i] = shortest distance from start to i,
 *         or Double.NEGATIVE_INFINITY if node i is in a negative cycle
 *
 * Time:  O(V * E) — relaxes all edges V-1 times
 * Space: O(V)     — stores distance array
 */

Inline Comments on Key Lines

Comment the why, not the what. Focus on lines where the logic isn't obvious:

// Relax all edges V-1 times. After V-1 passes, shortest paths
// are guaranteed if no negative cycles exist.
for (int i = 0; i < n - 1; i++) {
  for (Edge e : edges) {
    if (dist[e.from] + e.cost < dist[e.to]) {
      dist[e.to] = dist[e.from] + e.cost;
    }
  }
}

// If we can still relax an edge after V-1 passes, that node
// is reachable from a negative cycle — mark it as -infinity.
for (int i = 0; i < n - 1; i++) {
  for (Edge e : edges) {
    if (dist[e.from] + e.cost < dist[e.to]) {
      dist[e.to] = Double.NEGATIVE_INFINITY;
    }
  }
}

File-Level Header

Every file starts with a comment block explaining the algorithm in the file

/**
 * Bellman-Ford Shortest Path Algorithm
 *
 * Computes single-source shortest paths in a weighted graph.
 * Handles negative edge weights and detects negative cycles.
 *
 * Use cases:
 *   - Graphs with negative weights (where Dijkstra fails)
 *   - Detecting negative cycles (e.g., currency arbitrage)
 *
 * Run with:
 *   bazel run //src/main/java/com/williamfiset/algorithms/graphtheory:BellmanFordAdjacencyList
 *
 * @see <a href="https://en.wikipedia.org/wiki/Bellman-Ford_algorithm">Wikipedia</a>
 */

---

Skill 2: Test Coverage

Goal: Every algorithm has tests that prove it works and teach edge cases.

Test File Structure

Place tests alongside source files or in a tests/ directory. Name test files to mirror the source: BellmanFord.java → BellmanFordTest.java.

What to Test

For every algorithm, cover these categories:

1. Basic/Happy path — typical input, expected output
2. Edge cases — empty input, single element, duplicates
3. Boundary conditions — max/min values, zero, Integer.MAX_VALUE
4. Known tricky inputs — cases that commonly break naive implementations
5. Performance sanity check — large input doesn't hang or crash (optional)

Test Naming Convention

Use descriptive names that read like a sentence:

@Test
public void testShortestPathSimpleGraph() { ... }

@Test
public void testDetectsNegativeCycle() { ... }

@Test
public void testSingleNodeGraph() { ... }

@Test
public void testDisconnectedNodes() { ... }

Test Documentation

Each test method gets a brief comment explaining what scenario it covers and why that scenario matters:

/**
 * Graph with a negative cycle reachable from the source.
 * Bellman-Ford should mark affected nodes as NEGATIVE_INFINITY.
 *
 *   0 --5--> 1 --(-10)--> 2 --3--> 1
 *                (creates cycle 1→2→1 with net cost -7)
 */
@Test
public void testDetectsNegativeCycle() {
  // ... test body
}

When Modifying Code, Update Tests

Every code change must be accompanied by:

• Running existing tests to check for regressions
• Adding new tests if new behavior is introduced
• Updating existing tests if method signatures or behavior changed
• Removing tests only if the feature they cover was deliberately removed

---

Skill 3: Refactoring and Code Debt

Goal: Keep the codebase clean without losing educational value.

When to Remove Code

Remove code that is:

• Exact duplicates of another implementation with no added educational value
• Dead code (unreachable, unused helper methods)
• Commented-out blocks with no explanation of why they exist
• Temporary debug/print statements

When to Keep "Duplicate" Code

Keep alternative implementations when they teach different approaches:

// ✓ KEEP — BFS and DFS solutions to the same problem teach different techniques
public int[] bfsSolve(int[][] grid) { ... }
public int[] dfsSolve(int[][] grid) { ... }

// ✓ KEEP — iterative vs recursive shows tradeoffs
public int fibRecursive(int n) { ... }
public int fibIterative(int n) { ... }

// ✗ REMOVE — identical logic, just different variable names
public int search_v1(int[] arr, int target) { ... }
public int search_v2(int[] arr, int target) { ... }

When keeping alternatives, clearly label them with a comment explaining the educational purpose:

/**
 * Recursive implementation of binary search.
 * Compare with binarySearchIterative() to see the iterative approach.
 * The iterative version avoids stack overhead for large arrays.
 */

Debt Checklist

When refactoring, scan for:

• Unused imports
• Unused variables or parameters
• Methods that can be combined or simplified
• Magic numbers that should be named constants
• Inconsistent naming within the same file
• Copy-pasted blocks that should be extracted into a helper

---

Skill 4: Code Formatting and Consistency

Goal: Uniform style across the entire repository.

Naming Conventions

Use short, clear variable names. Prefer readability through simplicity:

// ✓ GOOD — short and clear
int n = graph.length;
int[] dist = new int[n];
boolean[] vis = new boolean[n];
List<int[]> adj = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
int src = 0;
int dst = n - 1;

// ✗ BAD — verbose names that clutter algorithm logic
int numberOfNodesInGraph = graph.length;
int[] shortestDistanceFromSource = new int[numberOfNodesInGraph];
boolean[] hasNodeBeenVisited = new boolean[numberOfNodesInGraph];
List<int[]> adjacencyListRepresentation = new ArrayList<>();
Queue<Integer> breadthFirstSearchQueue = new LinkedList<>();
int sourceNodeIndex = 0;
int destinationNodeIndex = numberOfNodesInGraph - 1;

Common short names (use consistently across the repo):

Name	Meaning
n	number of elements/nodes
m	number of edges
i, j	loop indices
from, to	graph node endpoints
cost	edge weight
dist	distance array
vis	visited array
adj	adjacency list
q	queue
pq	priority queue
st	stack
dp	dynamic programming table
ans	result/answer
lo	low pointer/bound
hi	high pointer/bound
mid	midpoint
src	source node
dst	destination node
cnt	counter
sz	size
cur	current element
prev	previous element
next	next element (use nxt if shadowing keyword)

Formatting Rules

• Braces: opening brace on the same line (if (...) {)
• Indentation: 2 spaces (no tabs)
• Blank lines: one blank line between methods, none inside short methods
• Max line length: 100 characters (soft limit)
• Imports: group by package, alphabetize within groups, no wildcard imports

Big-O Notation Convention

Always use explicit multiplication and parentheses in Big-O expressions for clarity:

// ✓ GOOD — explicit and unambiguous
// Time:  O(n*log(n))
// Time:  O(n*log^2(n))
// Time:  O(n^2*log(n))

// ✗ BAD — missing multiplication and parentheses
// Time:  O(n log n)
// Time:  O(n log^2 n)
// Time:  O(n^2 log n)

// Simple expressions without multiplication are fine as-is
// Time:  O(n)
// Time:  O(n^2)
// Time:  O(log(n))
// Space: O(n)

For Loop Body on Its Own Line

Always place the body of a for loop on its own line, even for single statements. This improves readability, especially in nested loops:

// ✗ BAD — body on same line as for
for (int j = 0; j < n; j++) augmented[i][j] = matrix[i][j];

// ✓ GOOD — body on its own line
for (int j = 0; j < n; j++)
  augmented[i][j] = matrix[i][j];

// ✓ GOOD — nested for loops, each level on its own line
for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    for (int k = 0; k < n; k++)
      result[i][j] += m1[i][k] * m2[k][j];

Avoid Java Streams

Streams hurt readability for learners. Use plain loops instead:

// ✗ AVOID — streams obscure the logic for beginners
int sum = Arrays.stream(arr).filter(x -> x > 0).reduce(0, Integer::sum);

// ✓ PREFER — a loop is immediately readable
int sum = 0;
for (int x : arr) {
  if (x > 0) sum += x;
}

---

Skill 5: Simplification

Goal: The simplest correct code teaches the best.

Simplification Strategies

1. Reduce nesting — invert conditions, return early

// ✗ AVOID — deep nesting
if (node != null) {
  if (node.left != null) {
    if (node.left.val == target) {
      return true;
    }
  }
}
return false;

// ✓ PREFER — early returns keep code flat
if (node == null) return false;
if (node.left == null) return false;
return node.left.val == target;

2. Extract repeated logic — but only if it genuinely reduces complexity

3. Use standard library where it clarifies — Arrays.sort(), Collections.swap(), Math.min(), etc. are fine because learners need to know these exist

4. Remove unnecessary wrappers — don't wrap a single method call in another method

5. Prefer arrays over complex data structures when the problem allows it — int[] is clearer than ArrayList<Integer> when the size is known

What NOT to Simplify

• Don't merge two clearly distinct algorithm phases into one loop just to save lines
• Don't replace clear if/else chains with ternary operators if it reduces readability
• Don't remove intermediate variables that give a name to a complex expression

---

Skill 6: Bug Detection

Goal: Catch bugs proactively whenever touching code.

Bug Scan Checklist

When modifying any lines of code, actively check for and report:

• Off-by-one errors — loop bounds, array indices, fence-post problems
• Integer overflow — multiplication or addition that could exceed int range
• Null/empty checks — missing guards for null arrays, empty collections
• Uninitialized values — using variables before assignment (especially in dp arrays)
• Wrong comparison — == vs <=, < vs <= in loop conditions
• Infinite loops — conditions that never become false, missing increments
• Array out of bounds — indexing with i+1, i-1 without range checks
• Graph issues — missing visited check (infinite loop in cycles), wrong direction in directed graph
• Incorrect base cases — dp[0], recursion base case, empty graph
• Mutation bugs — modifying input that caller expects unchanged
• Copy vs reference — shallow copy when deep copy needed
• Return value misuse — ignoring return value, returning wrong variable

How to Report Bugs

When a bug is found, report it clearly:

🐛 BUG FOUND in BellmanFord.java line 42:
   Loop runs `i < n` but should be `i < n - 1`.
   The extra iteration incorrectly marks reachable nodes as
   being in a negative cycle.
   FIX: Change `i < n` to `i < n - 1`

---

Skill 7: Algorithm Explanation Comments

Goal: Help learners understand the why behind each algorithm.

---

Skill 8: Place main method at the bottom

Goal: The main java method should be near the bottom of the Java file for consistency throughout the project