dsa - data structures and algorithms

data strucutures and algorithms in Java

A hands-on workbook for mastering data structures and algorithms from the very first principles. It pairs a readable mdBook (theory, complexity proofs, edge cases) with Java skeletons and JUnit 5 tests you implement yourself.

This repo ships blank on purpose: skeletons with TODOs, failing tests, and prompts to fill in. The answers are yours to write.

What's inside

Each module folder under src/ holds:

• notes/NN-<topic>.md — the mdBook pages (numbered in reading order).
• code/NN-<Class>.java — the Java skeletons you implement.
• problemset/ProblemNN.java — one stub per problem.
• tests/concepts/*Test.java — JUnit 5 tests for the topic skeletons.
• tests/problemset/*Test.java — JUnit 5 tests for the problem set.
• PROBLEM_SET.md — the module's problems (Foundational + Applied).
• extra-practice/ — generated on demand by /extra-practice (problems + stubs + tests); not shipped, gitignored archives aside.

All .java files use the default package (no package line) and are compiled per module — flat and dependency-free. Topic skeleton classes are package-private so the numbered filenames compile.

AI tooling. The repo is built to be worked with an AI coding agent as a tutor. Guard + teaching protocol live in one canonical AGENTS.md (the other agents' files symlink/import it); Claude Code skills are in .claude/skills/ (portable copies in .agents/skills/); and a zero-dependency MCP server in mcp/ exposes teach_topic / generate_extra_practice to any MCP agent. See Learning with AI.

Table of Contents

18 modules, 112 topics. Each topic is a fill-in-yourself lecture outline (concept → time & space complexity → implementation walkthrough) paired with a Java skeleton and JUnit 5 tests — except a few concept/proof topics that are notes-only.

Module 0 — Foundations · 5 topics

1. Asymptotic Analysis
2. Recurrence Relations
3. Proof Techniques
4. Logarithms And Summations
5. Amortized Analysis

Problem Set »

Module 1 — Arrays · 4 topics

1. Memory Model
2. Dynamic Arrays
3. Multidimensional Arrays
4. Prefix & Suffix Sums and Products

Problem Set »

Module 2 — Linked Lists · 3 topics

1. Singly Linked List
2. Doubly Linked List
3. Skip Lists

Problem Set »

Module 3 — Stacks & Queues · 4 topics

1. Stacks
2. Queues
3. Deques
4. Monotonic Stack

Problem Set »

Module 4 — Recursion & Divide and Conquer · 6 topics

1. Recursion Deep
2. Divide and Conquer
3. Backtracking
4. Closest Pair of Points
5. Fast Exponentiation
6. Karatsuba Multiplication

Problem Set »

Module 5 — Searching & Sorting · 13 topics

1. Linear Search
2. Binary Search
3. Comparison Lower Bound
4. Bubble Sort
5. Selection Sort
6. Insertion Sort
7. Merge Sort
8. Quicksort
9. Heapsort
10. Counting Sort
11. Radix Sort
12. Bucket Sort
13. Quickselect

Problem Set »

Module 6 — Trees · 7 topics

1. Binary Trees
2. Binary Search Trees
3. 2-3 Trees
4. AVL Trees
5. Red-Black Trees
6. Splay Trees
7. B-Trees

Problem Set »

Module 7 — Heaps & Priority Queues · 4 topics

1. Binary Heap
2. Build-Heap
3. d-ary Heaps
4. Fibonacci Heaps

Problem Set »

Module 8 — Spatial Trees · 2 topics

1. kd-Trees
2. Quadtrees

Problem Set »

Module 9 — Disjoint Sets · 4 topics

1. Union-Find
2. Path Compression
3. Union by Rank
4. Amortized Analysis & the Inverse Ackermann Function

Problem Set »

Module 10 — Graph Fundamentals · 10 topics

1. Graph Representations
2. Breadth-First Search
3. Depth-First Search
4. Topological Sort
5. Strongly Connected Components
6. Articulation Points & Bridges
7. Euler Paths & Circuits
8. Hamiltonian Paths & Cycles
9. Bipartite Graphs & Matching
10. DAG Shortest Paths

Problem Set »

Module 11 — Graph Algorithms · 9 topics

1. Dijkstra's Shortest Paths
2. Bellman-Ford Shortest Paths
3. Floyd-Warshall All-Pairs Shortest Paths
4. Johnson's Algorithm
5. Prim's Minimum Spanning Tree
6. Kruskal's Minimum Spanning Tree
7. Ford-Fulkerson Maximum Flow
8. Edmonds-Karp Maximum Flow
9. Minimum Cut

Problem Set »

Module 12 — Hash Tables · 6 topics

1. Hash Functions
2. Chaining
3. Open Addressing
4. Amortized Resizing
5. Universal Hashing
6. Bloom Filters

Problem Set »

Module 13 — Dynamic Programming · 9 topics

1. The Dynamic Programming Paradigm
2. 0/1 Knapsack
3. Longest Common Subsequence
4. Longest Increasing Subsequence
5. Edit Distance
6. Matrix Chain Multiplication
7. Coin Change
8. Rod Cutting
9. Dynamic Programming on Trees

Problem Set »

Module 14 — Greedy Algorithms · 6 topics

1. The Greedy Paradigm
2. The Exchange Argument
3. Activity Selection
4. Huffman Coding
5. Fractional Knapsack
6. Stable Matching

Problem Set »

Module 15 — String Algorithms · 3 topics

1. KMP
2. Rabin–Karp
3. Z-Algorithm

Problem Set »

Module 16 — Tries · 4 topics

1. Trie Basics
2. Prefix Search
3. Autocomplete
4. Compressed Tries (Radix Trees)

Problem Set »

Module 17 — Advanced · 13 topics

1. Order-Statistics Trees
2. Interval Trees
3. Treaps
4. van Emde Boas Trees
5. Cache-Oblivious Algorithms
6. External-Memory Model
7. Segment Trees
8. Lazy Propagation
9. Fenwick Tree (Binary Indexed Tree)
10. Fenwick vs Segment Tree
11. Sparse Tables
12. Suffix Arrays
13. Suffix Trees

Problem Set »

Build & tooling

• Java 21 + JUnit 5, built with Gradle (Kotlin DSL).
• The Gradle wrapper (./gradlew) downloads Gradle and pulls JUnit from Maven Central, so a JDK on your PATH is all you need to install.

Run the book

You can run the book locally using mdbook. The roadmap on the intro page is a Mermaid diagram, so you also need the mdbook-mermaid preprocessor. Install both via cargo:

cargo install mdbook mdbook-mermaid

Run the book locally to preview it in your browser

mdbook serve --open

NOTE: Math (recurrences, bounds, proofs) renders via MathJax, and the roadmap renders via mdbook-mermaid.

Run the tests

./gradlew test              # compile + test every module
./gradlew test_06-trees     # just one module (task name == folder name)

Each module gets its own isolated Gradle source set and test task, so the duplicate default-package class names across modules (every module has its own Problem01, etc.) don't collide. ignoreFailures keeps the build green so every module runs and reports.

Tests fail initially — that's the point. Implement a skeleton until its tests go green.

Lint

Style is enforced by editorconfig-checker against the root .editorconfig (LF endings, final newline, no trailing whitespace, tab indentation for .java). Run the exact same check CI runs:

./gradlew lint

The checker binary is fetched into build/tools/ on first use, then run with .editorconfig-checker.json. It exits non-zero and lists file:line for any violation, so run it before you push.

Student workflow

Work this with an AI coding agent (Claude Code, Cursor, Copilot, Codex, Gemini, Windsurf, Aider) — but as a tutor, never an autocomplete. The repo ships guard files that put any cooperating agent into tutor mode: it teaches and grades, but never fills in your notes, code, or problems. Full guide: Learning with AI.

Per topic:

1. Learn it — /teach <topic> (or "teach me <topic>"): a section-gated lecture that stops after each section until you understand it and have written that section's notes in your own words.
2. Implement the code/ skeleton until ./gradlew test_<module> passes.
3. Get reviewed — "review my passing code for edge cases, don't fix it."
4. Drill the module's PROBLEM_SET.md — Foundational cold, then Applied.
5. More reps — /extra-practice <module> (or "more problems on <topic>") generates fresh problems + stubs + tests into src/<module>/extra-practice/.
6. Space it out and check the topic off in TODO.md.

The teach + extra-practice flows work in any agent three ways: the instruction files (zero setup), the zero-dependency MCP server in mcp/ (approve once), and Claude Code skills (/teach, /extra-practice).

Distribution & usage

The main repo holds only the blank skeletons (the template).

• It is marked as a GitHub Template Repository
• Click "Use this template" to create a standalone repo of your own — not a fork, no "forked from" link, clean history, its own repo Public or private, your choice. Fill in your answers there

CI / CD

• ci.yml — compiles every module and runs ./gradlew test. Tests run informationally (ignoreFailures) since the template ships unimplemented, so the build stays green on the blank workbook
• deploy-book.yml — builds and deploys the book to GitHub Pages on push to main. Enable via Settings → Pages → Source: "GitHub Actions"

Progress

See TODO.md for the full module/topic checklist.