Computer Science & Software Engineering Algorithms

A structured repository dedicated to implementing, analyzing, and documenting foundational computer science algorithms and data structures using Python. This project serves as an educational sandbox to study runtime complexities, data architecture, and verification methodologies.

Project Structure

• src/: Core Python implementations categorized by algorithmic domain.
• service/: Transport-agnostic wrappers exposing the algorithms via an MCP stdio server and a FastAPI HTTP API.
• tests/: Automated unit tests mirroring the codebase layout to validate edge cases and performance boundaries.
• docs/adr/: Architectural Decision Records tracking the design choices for each algorithm (index).
• docs/RUNBOOK.md: Setup, testing, HTTP/MCP usage, sample requests, request limits, and troubleshooting.
• docs/CONTRIBUTING.md: Step-by-step branching, testing, and PR/merge workflow guide.
• pyproject.toml: Package metadata; install with pip install -e '.[dev]'.

Getting Started

The runbook is the full reference for running and testing. Quick start:

Prerequisites

• Python 3.10 or higher
• uv or pip

Installation

1. Clone the repository:

   git clone https://github.com/sjamal/csc-algorithms.git
   cd csc-algorithms

2. Create a virtual environment and install the package with development dependencies:

   uv venv --python 3.12 .venv
   uv pip install --python .venv/bin/python -e '.[dev]'
   source .venv/bin/activate  # On Windows use: .venv\Scripts\activate

   Or with pip: python -m venv .venv && source .venv/bin/activate && pip install -e '.[dev]'.

Execution and Testing

The repository uses pytest for codebase verification. Run the test suite globally using the following command:

pytest tests/

To run syntax and style validation checks using black:

black --check src/ tests/

For the full test and coverage gate, run make verify. Local commits use the tracked .githooks/pre-commit hook for fast staged-area tests by default; use TEST_SCOPE=full git commit to run the complete 100% coverage gate before committing.

Running the Service Layer

Every algorithm is also exposed via a stateless MCP server and a REST API, both backed by the same service/tools.py wrapper functions.

MCP server (stdio transport) — for use with MCP-aware agents/chat clients (Claude Desktop, VS Code, etc.):

python -m service.mcp_server

Register it with your MCP client by pointing it at this command; consult your client's documentation for its mcp.json/config format.

HTTP API — for any other programmatic caller:

uvicorn service.http_app:app --reload

Each endpoint mirrors an MCP tool, e.g. POST /sorting/quicksort, POST /graphs/dijkstra, POST /graphs/traveling-salesman, POST /machine-learning/kmeans. Interactive OpenAPI docs are available at http://127.0.0.1:8000/docs once the server is running. See the runbook for sample curl requests and MCP client configuration.

Limitations and Design Notes

• Stateless service: Every MCP and HTTP call rebuilds its data structure from the request; no state is kept between calls (ADR 0000).
• HTTP request limits: The HTTP API caps list lengths, string lengths, graph sizes, and numeric bounds, returning HTTP 422 when exceeded (ADR 0000 amendment; limits table). The MCP server does not apply these caps.
• No authentication: The HTTP API is open and intended for local or trusted-network use only.
• Choosing a transport: Use MCP for agent and chat-client integrations on the same machine; use HTTP for scripts, notebooks, or services calling over the network.
• Educational scope: Implementations favour clarity and verification over raw performance; see each ADR for trade-offs.

Architectural Decision Records (ADRs)

The architectural choices, trade-offs, and design patterns for each algorithm are fully documented below (also available as an ADR index):

• ADR 0000: Expose Algorithms via MCP and HTTP Service Layer (includes the HTTP request size limits amendment)
• ADR 0001: Hoare Partitioning for Quicksort
• ADR 0002: heapq for Dijkstra Priority Queue
• ADR 0003: LPS Array for KMP String Matching
• ADR 0004: Recursive Node-Pointer Binary Search Tree
• ADR 0005: NumPy Vectorized K-Means Clustering
• ADR 0006: NumPy eigh Covariance PCA
• ADR 0007: Edge-List Relaxation for Bellman-Ford
• ADR 0008: Euclidean Heuristic for A* Pathfinding
• ADR 0009: AVL Rotations for Self-Balancing BST
• ADR 0010: Min-Heap Greedy Merge for Huffman Coding
• ADR 0011: Kahn's In-Degree BFS for Topological Sort
• ADR 0012: Iterative Boolean Marking for Sieve of Eratosthenes
• ADR 0013: Union by Rank with Path Compression for Union-Find
• ADR 0014: Bottom-Up Divide-and-Conquer Merge for Merge Sort
• ADR 0015: Iterative Pointer Rewiring for Singly Linked List Reversal
• ADR 0016: Bottom-Up Tabulation with Backtracking for 0/1 Knapsack
• ADR 0017: Bottom-Up Tabulation with Diagonal Backtracking for LCS
• ADR 0018: Binary Max-Heap for Heap Sort
• ADR 0019: Iterative Midpoint Bisection for Binary Search
• ADR 0020: Iterative Queue and Stack for BFS and DFS
• ADR 0021: Edge-Sorted Union-Find for Kruskal's Algorithm
• ADR 0022: Character-Branching Trie for Prefix Lookups
• ADR 0023: Iterative Euclidean GCD
• ADR 0024: Stack for Valid Parentheses
• ADR 0025: Held-Karp and Nearest-Neighbor 2-Opt for the Traveling Salesman Problem

Algorithm Catalog

Browse the algorithm catalog for concise definitions, complexity notes, implementation links, tests, and guidance on choosing an algorithm or data structure.

---

Code Quality and Design Guidelines

Naming Conventions & Code Style

To ensure uniformity, this repository follows strict standards derived from PEP 8:

• Functions & Variables: Lowercase word blocks separated by underscores (snake_case).
• Protected Components: Preceded by a single leading underscore (e.g., _partition).
• Constants: Full uppercase strings separated by underscores (UPPER_SNAKE_CASE).
• Type Hinting: Mandatory on all public functions via the typing module framework.

Security, Stability & Privacy Considerations

1. Input Integrity & Memory Protection: Sorting algorithms construct a explicit local list() copy of tracking variables to prevent input reference mutation bugs.
2. Denial of Service (DoS) Boundaries: Quicksort worst-case scaling behavior is $O(n^2)$. For safety-critical systems sorting untrusted or adversarial user inputs, randomizing the pivot selection or utilizing heap-sort/merge-sort derivatives should be considered.
3. Graph Payload Resilience: The Dijkstra parser explicitly references data isolation using explicit float("inf") typing arrays. Node configurations must strictly pass hashable unique strings to mitigate graph processing collision events.
4. Data Isolation: This package operates entirely locally on internal operational states. No logging pipelines, web tracing, or environment data tracking hooks are implemented, ensuring maximum data privacy.
5. Negative-Weight Cycle Guarding: The Bellman-Ford implementation runs an explicit final relaxation pass to detect reachable negative-weight cycles and raises a ValueError rather than allowing an untrusted graph payload to loop indefinitely.
6. Heuristic Input Validation: The A* implementation validates that source, target, and coordinate metadata exist before search begins, and rejects negative edge weights, preventing malformed spatial graphs from corrupting the heuristic scoring.
7. Balanced Depth Guarantee: The AVL Tree rebalances on every insert and delete, preventing adversarial sorted-input sequences from degrading traversal operations to linear time.
8. Codebook Integrity Validation: The Huffman decoder rejects malformed or duplicate-code codebooks and dangling/invalid bitstreams with an explicit ValueError, rather than silently returning corrupted or truncated text.
9. Cycle & Referential Integrity Guards: Topological Sort validates that every edge references a declared node and raises a ValueError when a cycle prevents a complete ordering, rather than silently returning a partial or misleading sequence.
10. Bounded Memory Allocation: The Sieve of Eratosthenes allocates its boolean tracking array based on the caller-supplied boundary; callers should validate untrusted boundary inputs against a sane upper limit before use to avoid excessive memory allocation.
11. Service Layer Input Validation: The HTTP API validates request bodies via Pydantic schemas and translates algorithm-level ValueErrors into HTTP 400 responses rather than leaking stack traces; both the MCP server and HTTP API are stateless per call, so no client-supplied data persists across requests.
12. Fixed Element Universe: Union-Find validates every find()/union() call against its initial element set and raises a ValueError for unknown elements, preventing silent creation of untracked entries.
13. Worst-Case DoS Mitigation: Merge Sort guarantees $O(n \log n)$ even on adversarial input, making it the safer default over Quicksort when sorting untrusted, attacker-influenced data where worst-case scaling matters.
14. Bounded Traversal Footprint: The Singly Linked List's search/delete/reverse operations are strictly O(n) iterative walks with no recursion, preventing stack-depth exhaustion on very large untrusted input lists.
15. Iterative DP, No Recursion Limits: The 0/1 Knapsack solver uses bottom-up tabulation rather than top-down recursion, avoiding Python's RecursionError on large item counts.
16. Quadratic Complexity Awareness: LCS runs in $O(n \times m)$ time and space; callers should bound input string lengths when comparing untrusted, attacker-controlled text to avoid excessive memory allocation on very large inputs.
17. In-Place Worst-Case Guarantee: Heap Sort provides the same $O(n \log n)$ worst-case guarantee as Merge Sort but with $O(1)$ auxiliary space, useful when both adversarial-input resilience and memory constraints matter simultaneously.
18. Precondition Responsibility: Binary Search assumes sorted input and does not validate it; callers must guarantee sortedness themselves, since verifying it would negate the algorithm's logarithmic performance advantage.
19. Traversal Input Integrity: BFS and DFS validate the source and every adjacency reference before traversal, preventing malformed graph payloads from producing partial results; both use iterative state to avoid recursion-depth exhaustion.
20. Exponential Solver Cap: The Held-Karp TSP solver refuses graphs larger than 12 vertices, since its $O(n^2 2^n)$ cost grows explosively; larger inputs use the polynomial nearest-neighbor 2-opt heuristic instead.
21. HTTP Request Size Limits: Every HTTP request model caps collection sizes, string lengths, and numeric bounds so a single oversized payload cannot exhaust server CPU or memory.

---

Related docs: Runbook · Algorithm catalog · ADR index · Contributing · Roadmap · License 20. Minimum-Spanning-Tree Integrity: Kruskal validates vertex and edge references, skips cycle-forming edges with Union-Find, and rejects disconnected graphs instead of returning a partial spanning tree.