14# Algorithms Education Skills
15
16This skill defines the conventions and standards for an educational algorithms
17repository. The goal is to make every algorithm implementation clear, well-tested,
18and accessible to learners who may not have deep CS backgrounds.
19
20---
21
22## Skill 1: Code Documentation
23
24**Goal:** Every file should teach, not just implement.
25
26### Method-Level Documentation
27
28Every public method gets a doc comment that explains:
291. **What** the method does (in plain English, one sentence)
302. **How** it works (brief description of the approach/algorithm)
313. **Parameters** — what each input represents
324. **Returns** — what the output means
335. **Time/Space complexity** — always include Big-O
34
35```java
36/**
37 * Finds the shortest path from a source node to all other nodes
38 * using Bellman-Ford's algorithm. Unlike Dijkstra's, this handles
39 * negative edge weights and detects negative cycles.
40 *
41 * @param graph - adjacency list where graph[i] lists edges from node i
42 * @param start - the source node index
43 * @param n - total number of nodes in the graph
44 * @return dist array where dist[i] = shortest distance from start to i,
45 * or Double.NEGATIVE_INFINITY if node i is in a negative cycle
46 *
47 * Time: O(V * E) — relaxes all edges V-1 times
48 * Space: O(V) — stores distance array
49 */
50```
51
52### Inline Comments on Key Lines
53
54Comment the **why**, not the **what**. Focus on lines where the logic isn't obvious:
55
56```java
57// Relax all edges V-1 times. After V-1 passes, shortest paths
58// are guaranteed if no negative cycles exist.
59for (int i = 0; i < n - 1; i++) {
60 for (Edge e : edges) {
61 if (dist[e.from] + e.cost < dist[e.to]) {
62 dist[e.to] = dist[e.from] + e.cost;
63 }
64 }
65}
66
67// If we can still relax an edge after V-1 passes, that node
68// is reachable from a negative cycle — mark it as -infinity.
69for (int i = 0; i < n - 1; i++) {
70 for (Edge e : edges) {
71 if (dist[e.from] + e.cost < dist[e.to]) {
72 dist[e.to] = Double.NEGATIVE_INFINITY;
73 }
74 }
75}
76```
77
78### File-Level Header
79
80Every file starts with a comment block explaining the algorithm in the file
81
82```java
83/**
84 * Bellman-Ford Shortest Path Algorithm
85 *
86 * Computes single-source shortest paths in a weighted graph.
87 * Handles negative edge weights and detects negative cycles.
88 *
89 * Use cases:
90 * - Graphs with negative weights (where Dijkstra fails)
91 * - Detecting negative cycles (e.g., currency arbitrage)
92 *
93 * Run with:
94 * bazel run //src/main/java/com/williamfiset/algorithms/graphtheory:BellmanFordAdjacencyList
95 *
96 * @see <a href="https://en.wikipedia.org/wiki/Bellman-Ford_algorithm">Wikipedia</a>
97 */
98```
99
100---
101
102## Skill 2: Test Coverage
103
104**Goal:** Every algorithm has tests that prove it works and teach edge cases.
105
106### Test File Structure
107
108Place tests alongside source files or in a tests/ directory. Name test files
109to mirror the source: BellmanFord.java → BellmanFordTest.java.
110
111### What to Test
112
113For every algorithm, cover these categories:
114
1151. **Basic/Happy path** — typical input, expected output
1162. **Edge cases** — empty input, single element, duplicates
1173. **Boundary conditions** — max/min values, zero, Integer.MAX_VALUE
1184. **Known tricky inputs** — cases that commonly break naive implementations
1195. **Performance sanity check** — large input doesn't hang or crash (optional)
120
121### Test Naming Convention
122
123Use descriptive names that read like a sentence:
124
125```java
126@Test
127public void testShortestPathSimpleGraph() { ... }
128
129@Test
130public void testDetectsNegativeCycle() { ... }
131
132@Test
133public void testSingleNodeGraph() { ... }
134
135@Test
136public void testDisconnectedNodes() { ... }
137```
138
139### Test Documentation
140
141Each test method gets a brief comment explaining what scenario it covers and
142why that scenario matters:
143
144```java
145/**
146 * Graph with a negative cycle reachable from the source.
147 * Bellman-Ford should mark affected nodes as NEGATIVE_INFINITY.
148 *
149 * 0 --5--> 1 --(-10)--> 2 --3--> 1
150 * (creates cycle 1→2→1 with net cost -7)
151 */
152@Test
153public void testDetectsNegativeCycle() {
154 // ... test body
155}
156```
157
158### When Modifying Code, Update Tests
159
160Every code change must be accompanied by:
161- Running existing tests to check for regressions
162- Adding new tests if new behavior is introduced
163- Updating existing tests if method signatures or behavior changed
164- Removing tests only if the feature they cover was deliberately removed
165
166---
167
168## Skill 3: Refactoring and Code Debt
169
170**Goal:** Keep the codebase clean without losing educational value.
171
172### When to Remove Code
173
174Remove code that is:
175- Exact duplicates of another implementation with no added educational value
176- Dead code (unreachable, unused helper methods)
177- Commented-out blocks with no explanation of why they exist
178- Temporary debug/print statements
179
180### When to Keep "Duplicate" Code
181
182Keep alternative implementations when they teach different approaches:
183
184```java
185// ✓ KEEP — BFS and DFS solutions to the same problem teach different techniques
186public int[] bfsSolve(int[][] grid) { ... }
187public int[] dfsSolve(int[][] grid) { ... }
188
189// ✓ KEEP — iterative vs recursive shows tradeoffs
190public int fibRecursive(int n) { ... }
191public int fibIterative(int n) { ... }
192
193// ✗ REMOVE — identical logic, just different variable names
194public int search_v1(int[] arr, int target) { ... }
195public int search_v2(int[] arr, int target) { ... }
196```
197
198When keeping alternatives, clearly label them with a comment explaining the
199educational purpose:
200
201```java
202/**
203 * Recursive implementation of binary search.
204 * Compare with binarySearchIterative() to see the iterative approach.
205 * The iterative version avoids stack overhead for large arrays.
206 */
207```
208
209### Debt Checklist
210
211When refactoring, scan for:
212- [ ] Unused imports
213- [ ] Unused variables or parameters
214- [ ] Methods that can be combined or simplified
215- [ ] Magic numbers that should be named constants
216- [ ] Inconsistent naming within the same file
217- [ ] Copy-pasted blocks that should be extracted into a helper
218
219---
220
221## Skill 4: Code Formatting and Consistency
222
223**Goal:** Uniform style across the entire repository.
224
225### Naming Conventions
226
227Use **short, clear** variable names. Prefer readability through simplicity:
228
229```java
230// ✓ GOOD — short and clear
231int n = graph.length;
232int[] dist = new int[n];
233boolean[] vis = new boolean[n];
234List<int[]> adj = new ArrayList<>();
235Queue<Integer> q = new LinkedList<>();
236int src = 0;
237int dst = n - 1;
238
239// ✗ BAD — verbose names that clutter algorithm logic
240int numberOfNodesInGraph = graph.length;
241int[] shortestDistanceFromSource = new int[numberOfNodesInGraph];
242boolean[] hasNodeBeenVisited = new boolean[numberOfNodesInGraph];
243List<int[]> adjacencyListRepresentation = new ArrayList<>();
244Queue<Integer> breadthFirstSearchQueue = new LinkedList<>();
245int sourceNodeIndex = 0;
246int destinationNodeIndex = numberOfNodesInGraph - 1;
247```
248
249Common short names (use consistently across the repo):
250
251| Name | Meaning |
252|--------|-------------------------------|
253| n | number of elements/nodes |
254| m | number of edges |
255| i, j | loop indices |
256| from, to | graph node endpoints |
257| cost | edge weight |
258| dist | distance array |
259| vis | visited array |
260| adj | adjacency list |
261| q | queue |
262| pq | priority queue |
263| st | stack |
264| dp | dynamic programming table |
265| ans | result/answer |
266| lo | low pointer/bound |
267| hi | high pointer/bound |
268| mid | midpoint |
269| src | source node |
270| dst | destination node |
271| cnt | counter |
272| sz | size |
273| cur | current element |
274| prev | previous element |
275| next | next element (use nxt if shadowing keyword) |
276
277### Formatting Rules
278
279- Braces: opening brace on the same line (if (...) {)
280- Indentation: 2 spaces (no tabs)
281- Blank lines: one blank line between methods, none inside short methods
282- Max line length: 100 characters (soft limit)
283- Imports: group by package, alphabetize within groups, no wildcard imports
284
285### Big-O Notation Convention
286
287Always use explicit multiplication and parentheses in Big-O expressions for clarity:
288
289```java
290// ✓ GOOD — explicit and unambiguous
291// Time: O(n*log(n))
292// Time: O(n*log^2(n))
293// Time: O(n^2*log(n))
294
295// ✗ BAD — missing multiplication and parentheses
296// Time: O(n log n)
297// Time: O(n log^2 n)
298// Time: O(n^2 log n)
299
300// Simple expressions without multiplication are fine as-is
301// Time: O(n)
302// Time: O(n^2)
303// Time: O(log(n))
304// Space: O(n)
305```
306
307### For Loop Body on Its Own Line
308
309Always place the body of a for loop on its own line, even for single statements.
310This improves readability, especially in nested loops:
311
312```java
313// ✗ BAD — body on same line as for
314for (int j = 0; j < n; j++) augmented[i][j] = matrix[i][j];
315
316// ✓ GOOD — body on its own line
317for (int j = 0; j < n; j++)
318 augmented[i][j] = matrix[i][j];
319
320// ✓ GOOD — nested for loops, each level on its own line
321for (int i = 0; i < n; i++)
322 for (int j = 0; j < n; j++)
323 for (int k = 0; k < n; k++)
324 result[i][j] += m1[i][k] * m2[k][j];
325```
326
327### Avoid Java Streams
328
329Streams hurt readability for learners. Use plain loops instead:
330
331```java
332// ✗ AVOID — streams obscure the logic for beginners
333int sum = Arrays.stream(arr).filter(x -> x > 0).reduce(0, Integer::sum);
334
335// ✓ PREFER — a loop is immediately readable
336int sum = 0;
337for (int x : arr) {
338 if (x > 0) sum += x;
339}
340```
341
342---
343
344## Skill 5: Simplification
345
346**Goal:** The simplest correct code teaches the best.
347
348### Simplification Strategies
349
3501. **Reduce nesting** — invert conditions, return early
351
352```java
353// ✗ AVOID — deep nesting
354if (node != null) {
355 if (node.left != null) {
356 if (node.left.val == target) {
357 return true;
358 }
359 }
360}
361return false;
362
363// ✓ PREFER — early returns keep code flat
364if (node == null) return false;
365if (node.left == null) return false;
366return node.left.val == target;
367```
368
3692. **Extract repeated logic** — but only if it genuinely reduces complexity
370
3713. **Use standard library where it clarifies** — Arrays.sort(), Collections.swap(),
372 Math.min(), etc. are fine because learners need to know these exist
373
3744. **Remove unnecessary wrappers** — don't wrap a single method call in another method
375
3765. **Prefer arrays over complex data structures** when the problem allows it —
377 int[] is clearer than ArrayList<Integer> when the size is known
378
379### What NOT to Simplify
380
381- Don't merge two clearly distinct algorithm phases into one loop just to save lines
382- Don't replace clear if/else chains with ternary operators if it reduces readability
383- Don't remove intermediate variables that give a name to a complex expression
384
385---
386
387## Skill 6: Bug Detection
388
389**Goal:** Catch bugs proactively whenever touching code.
390
391### Bug Scan Checklist
392
393When modifying any lines of code, actively check for and report:
394
395- [ ] **Off-by-one errors** — loop bounds, array indices, fence-post problems
396- [ ] **Integer overflow** — multiplication or addition that could exceed int range
397- [ ] **Null/empty checks** — missing guards for null arrays, empty collections
398- [ ] **Uninitialized values** — using variables before assignment (especially in dp arrays)
399- [ ] **Wrong comparison** — == vs <=, < vs <= in loop conditions
400- [ ] **Infinite loops** — conditions that never become false, missing increments
401- [ ] **Array out of bounds** — indexing with i+1, i-1 without range checks
402- [ ] **Graph issues** — missing visited check (infinite loop in cycles), wrong direction in directed graph
403- [ ] **Incorrect base cases** — dp[0], recursion base case, empty graph
404- [ ] **Mutation bugs** — modifying input that caller expects unchanged
405- [ ] **Copy vs reference** — shallow copy when deep copy needed
406- [ ] **Return value misuse** — ignoring return value, returning wrong variable
407
408### How to Report Bugs
409
410When a bug is found, report it clearly:
411
412```
413🐛 BUG FOUND in BellmanFord.java line 42:
414 Loop runs i < n but should be i < n - 1.
415 The extra iteration incorrectly marks reachable nodes as
416 being in a negative cycle.
417 FIX: Change i < n to i < n - 1
418```
419
420---
421
422## Skill 7: Algorithm Explanation Comments
423
424**Goal:** Help learners understand the *why* behind each algorithm.
425
426---
427
428## Skill 8: Place main method at the bottom
429
430**Goal:** The main java method should be near the bottom of the Java file for consistency throughout the project
431