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

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

Inline Comments on Key Lines

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

java
1// Relax all edges V-1 times. After V-1 passes, shortest paths
2// are guaranteed if no negative cycles exist.
3for (int i = 0; i < n - 1; i++) {
4  for (Edge e : edges) {
5    if (dist[e.from] + e.cost < dist[e.to]) {
6      dist[e.to] = dist[e.from] + e.cost;
7    }
8  }
9}
10
11// If we can still relax an edge after V-1 passes, that node
12// is reachable from a negative cycle — mark it as -infinity.
13for (int i = 0; i < n - 1; i++) {
14  for (Edge e : edges) {
15    if (dist[e.from] + e.cost < dist[e.to]) {
16      dist[e.to] = Double.NEGATIVE_INFINITY;
17    }
18  }
19}

File-Level Header

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

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

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:

java
1@Test
2public void testShortestPathSimpleGraph() { ... }
3
4@Test
5public void testDetectsNegativeCycle() { ... }
6
7@Test
8public void testSingleNodeGraph() { ... }
9
10@Test
11public void testDisconnectedNodes() { ... }

Test Documentation

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

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

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:

java
1// ✓ KEEP — BFS and DFS solutions to the same problem teach different techniques
2public int[] bfsSolve(int[][] grid) { ... }
3public int[] dfsSolve(int[][] grid) { ... }
4
5// ✓ KEEP — iterative vs recursive shows tradeoffs
6public int fibRecursive(int n) { ... }
7public int fibIterative(int n) { ... }
8
9// ✗ REMOVE — identical logic, just different variable names
10public int search_v1(int[] arr, int target) { ... }
11public int search_v2(int[] arr, int target) { ... }

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

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

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:

java
1// ✓ GOOD — short and clear
2int n = graph.length;
3int[] dist = new int[n];
4boolean[] vis = new boolean[n];
5List<int[]> adj = new ArrayList<>();
6Queue<Integer> q = new LinkedList<>();
7int src = 0;
8int dst = n - 1;
9
10// ✗ BAD — verbose names that clutter algorithm logic
11int numberOfNodesInGraph = graph.length;
12int[] shortestDistanceFromSource = new int[numberOfNodesInGraph];
13boolean[] hasNodeBeenVisited = new boolean[numberOfNodesInGraph];
14List<int[]> adjacencyListRepresentation = new ArrayList<>();
15Queue<Integer> breadthFirstSearchQueue = new LinkedList<>();
16int sourceNodeIndex = 0;
17int destinationNodeIndex = numberOfNodesInGraph - 1;

Common short names (use consistently across the repo):

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:

java
1// ✓ GOOD — explicit and unambiguous
2// Time:  O(n*log(n))
3// Time:  O(n*log^2(n))
4// Time:  O(n^2*log(n))
5
6// ✗ BAD — missing multiplication and parentheses
7// Time:  O(n log n)
8// Time:  O(n log^2 n)
9// Time:  O(n^2 log n)
10
11// Simple expressions without multiplication are fine as-is
12// Time:  O(n)
13// Time:  O(n^2)
14// Time:  O(log(n))
15// 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:

java
1// ✗ BAD — body on same line as for
2for (int j = 0; j < n; j++) augmented[i][j] = matrix[i][j];
3
4// ✓ GOOD — body on its own line
5for (int j = 0; j < n; j++)
6  augmented[i][j] = matrix[i][j];
7
8// ✓ GOOD — nested for loops, each level on its own line
9for (int i = 0; i < n; i++)
10  for (int j = 0; j < n; j++)
11    for (int k = 0; k < n; k++)
12      result[i][j] += m1[i][k] * m2[k][j];

Avoid Java Streams

Streams hurt readability for learners. Use plain loops instead:

java
1// ✗ AVOID — streams obscure the logic for beginners
2int sum = Arrays.stream(arr).filter(x -> x > 0).reduce(0, Integer::sum);
3
4// ✓ PREFER — a loop is immediately readable
5int sum = 0;
6for (int x : arr) {
7  if (x > 0) sum += x;
8}

Skill 5: Simplification

Goal: The simplest correct code teaches the best.

Simplification Strategies

1. Reduce nesting — invert conditions, return early

java
1// ✗ AVOID — deep nesting
2if (node != null) {
3  if (node.left != null) {
4    if (node.left.val == target) {
5      return true;
6    }
7  }
8}
9return false;
10
11// ✓ PREFER — early returns keep code flat
12if (node == null) return false;
13if (node.left == null) return false;
14return 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