algorithms

Machine learning algorithms and a deep learning framework implemented from scratch in NumPy.

Package	What it is
ml/	Classical ML: linear and logistic regression, SVM, KNN, naive Bayes, decision trees, random forest, AdaBoost, gradient boosting, XGBoost-style boosting, k-means, k-medoids, agglomerative clustering, Gaussian mixture models, PCA, Gaussian processes. Every model exposes fit(X, y) and predict(X).
network_nn/	A PyTorch-style framework: Tensor with reverse-mode autograd, nn layers (linear, conv 1D/2D/3D, pooling, batch/layer norm, RNN/GRU/LSTM, multi-head attention, transformer block), losses, optimizers and LR schedulers.
tests/	pytest suite. tests/network_nn/ checks every autograd op against finite differences; tests/ml/ trains each model on toy data.

Setup

The project uses a local virtualenv managed with uv.

uv venv .venv
uv pip install --python .venv/bin/python -e ".[dev]"

Runtime dependencies are NumPy, pandas and SciPy (SciPy is used only for a few numerical helpers such as Cholesky solves and Bessel functions). No scikit-learn, no PyTorch.

Tests

.venv/bin/python -m pytest              # everything
.venv/bin/python -m pytest tests/ml     # one package
.venv/bin/python -m pytest -k conv      # by keyword

Quick start

import numpy as np
from ml.models import RandomForest
from network_nn import Tensor, nn, optim, functional as F

X = np.random.randn(200, 2); y = (X[:, 0] * X[:, 1] > 0).astype(int)

forest = RandomForest(n_trees=20).fit(X, y)
print("forest accuracy:", (forest.predict(X) == y).mean())

model = nn.Sequential(nn.Linear(2, 16), nn.Tanh(), nn.Linear(16, 2))
opt = optim.Adam(model.parameters(), lr=0.05)
for _ in range(300):
    opt.zero_grad()
    loss = F.cross_entropy(model(Tensor(X)), y)
    loss.backward()
    opt.step()
print("mlp accuracy:", (model(Tensor(X)).data.argmax(1) == y).mean())

---

Algorithm collection

✅ marks what is implemented. Everything else is the to-do list.

Graph Algorithms

Dijkstra's Algorithm for Shortest Path Challenge: Implementing it efficiently using priority queues (like heaps) for weighted graphs.

Floyd-Warshall Algorithm for All-Pairs Shortest Path Challenge: A dynamic programming approach for finding shortest paths between all pairs, especially challenging in dense graphs.

Bellman-Ford Algorithm Challenge: Handles negative weights and detects negative cycles, useful for dynamic programming and shortest-path optimizations.

A* Search Algorithm Challenge: An advanced pathfinding algorithm using heuristics for faster searches, often applied in game development and AI.

Tarjan's Algorithm for Strongly Connected Components Challenge: Uses depth-first search and low-link values for efficient SCC detection in directed graphs.

Hopcroft-Karp Algorithm for Maximum Matching in Bipartite Graphs Challenge: Efficiently finds maximum matchings in bipartite graphs using DFS and BFS.

Edmonds-Karp Algorithm for Maximum Flow Challenge: Uses breadth-first search for finding augmenting paths in flow networks, a variant of the Ford-Fulkerson method.

Prim's and Kruskal's Algorithms for Minimum Spanning Tree Challenge: Building MSTs with different approaches, including priority queues (Prim's) and sorting/union-find (Kruskal's).

Computational Geometry

Convex Hull (Graham's Scan and Jarvis March) Challenge: Efficient algorithms to find the convex hull of a set of points, often used in computer graphics.

Line Segment Intersection Detection (Sweep Line Algorithm) Challenge: Detecting intersections in a set of line segments, requiring complex data structures for event handling.

Closest Pair of Points Challenge: A divide-and-conquer algorithm to find the closest two points in a plane, requiring advanced problem partitioning techniques.

Voronoi Diagram Construction Challenge: Divides a plane into regions based on the closest points, requiring a complex combination of geometry and data structures.

Bentley-Ottmann Algorithm for Finding All Intersections in a Plane Challenge: Sweep line algorithm to efficiently detect all intersections in a set of line segments.

Other Challenging Algorithms

FFT (Fast Fourier Transform) Challenge: Used in signal processing, it's complex due to its recursive divide-and-conquer approach in the frequency domain.

Simulated Annealing for Optimization Challenge: A probabilistic technique for approximating the global optimum of a function, requiring careful control of parameters.

Genetic Algorithms for Optimization Challenge: A population-based search algorithm using selection, crossover, and mutation, complex due to parameter tuning.

Bloom Filter Challenge: A space-efficient probabilistic data structure for set membership, requiring careful handling of false positives and hashing.

Data Structures

1. Red-Black Tree A self-balancing binary search tree with complex rules for insertion, deletion, and color rotations to maintain balance. Challenge: Implementing the color-based balancing rules, especially during deletions.

2. AVL Tree Another self-balancing tree that maintains balance by tracking the height of subtrees and performing rotations. Challenge: Implementing the different types of rotations (single and double rotations) efficiently.

3. Segment Tree with Lazy Propagation Used for range queries and updates, where updates are delayed (lazy) to avoid excessive computations. Challenge: Implementing lazy propagation for efficient range updates and maintaining a complex structure.

4. Suffix Tree (Ukkonen's Algorithm) A compressed trie of all suffixes of a string, allowing for efficient substring searches. Challenge: Ukkonen's algorithm is intricate and involves maintaining suffix links and edge compression.

5. Trie with Word Suggestion Extending a basic trie to implement prefix-based word suggestion, often with frequency-based sorting. Challenge: Managing memory and implementing efficient sorting of suggestions based on frequency.

6. Persistent Segment Tree Allows previous versions of the tree to be maintained after updates, making it useful for time-travel queries. Challenge: Implementing versioning while maintaining efficient memory usage and update times.

7. K-D Tree (K-Dimensional Tree) A data structure for organizing points in a k-dimensional space, used for nearest neighbor searches. Challenge: Partitioning space correctly and managing k-dimensional recursive tree structures.

8. Treap (Tree + Heap) A randomized binary search tree with heap properties to maintain balanced structure without explicit rotations. Challenge: Implementing tree rotations while maintaining both heap and BST properties.

9. B-Tree A multi-way search tree used in databases and filesystems for storing large amounts of sorted data. Challenge: Implementing node splitting and merging for insertions and deletions, with different levels of children.

10. Range Minimum Query (RMQ) using Segment Tree Segment Tree used specifically for finding minimum values within a given range. Challenge: Efficiently handling range queries and understanding segment tree applications in RMQ problems.

11. Fenwick Tree (Binary Indexed Tree) with Range Updates An efficient structure for prefix sums, extended with range updates. Challenge: Implementing efficient range updates with additional complexity compared to the basic Fenwick Tree.

12. Cartesian Tree A binary tree that maintains both a heap order and an in-order sequence of an array. Challenge: Building the tree in O(n) time for array-based Cartesian Trees, managing both order properties.

13. Wavelet Tree A data structure that efficiently represents arrays and can answer complex range queries. Challenge: Implementing multiple levels of bit vectors for querying sub-ranges and handling rank and select operations.

14. 2-3 Tree and 2-3-4 Tree Multi-way trees used for self-balancing with 2, 3, or 4 children per node. Challenge: Insertion and deletion rules, which require restructuring nodes while preserving balance.

15. Dynamic Aho-Corasick Trie (with failure links) An extension of the Trie for pattern matching with failure links for efficient searching across multiple patterns. Challenge: Building failure links, especially when patterns have overlaps or share common prefixes.

16. Heavy-Light Decomposition A technique to break down a tree into "heavy" and "light" paths for efficient path queries. Challenge: Decomposing paths correctly, maintaining path indices, and answering queries efficiently.

17. Dynamic Tree (Link/Cut Tree) A complex structure that allows for dynamic modifications of tree structure, supporting link and cut operations. Challenge: Implementing and maintaining the tree while allowing dynamic connectivity queries.

18. Compressed Trie (Radix Tree) A compact trie where nodes with a single child are merged to save space, used in applications like IP lookup. Challenge: Implementing node compression while preserving prefix-search properties.

19. Van Emde Boas Tree A highly efficient tree structure for maintaining a dynamic set of integers, allowing O(log log U) queries. Challenge: Complex recursive structure and memory-intensive design.

20. Top-Tree (for Tree Path Queries) A tree decomposition structure that allows efficient path queries, especially in graph applications. Challenge: Maintaining top-tree properties dynamically as nodes are added or removed.

---

Supervised Learning Algorithms

• Linear Regression ✅
• Logistic Regression ✅
• k-Nearest Neighbors (k-NN) ✅
• Support Vector Machine (SVM) ✅
• Naive Bayes Classifier ✅
• Decision Tree Classifier ✅
• Random Forest Classifier ✅
• Gradient Boosting Machines (GBM) ✅
• AdaBoost ✅
• XGBoost ✅
• LightGBM
• CatBoost
• Perceptron ✅
• Artificial Neural Network (ANN) ✅
• Convolutional Neural Network (CNN) ✅
• Recurrent Neural Network (RNN) ✅
• Long Short-Term Memory (LSTM) ✅
• Bidirectional LSTM ✅
• GRU (Gated Recurrent Unit) ✅
• Transformer Models ✅
• Multi-Layer Perceptron (MLP) ✅
• Ridge Regression ✅
• Lasso Regression ✅
• Elastic Net Regression ✅
• Polynomial Regression ✅
• Quantile Regression ✅
• Stochastic Gradient Descent (SGD) ✅

Unsupervised Learning Algorithms

• k-Means Clustering ✅
• Hierarchical Clustering ✅
• DBSCAN (Density-Based Spatial Clustering) ✅
• Gaussian Mixture Model (GMM) ✅
• Principal Component Analysis (PCA) ✅
• Independent Component Analysis (ICA) ✅
• t-Distributed Stochastic Neighbor Embedding (t-SNE) ✅
• Uniform Manifold Approximation and Projection (UMAP)
• Autoencoders ✅
• Self-Organizing Maps (SOM)
• Latent Dirichlet Allocation (LDA) ✅
• Apriori Algorithm (for association rule learning) ✅
• FP-Growth Algorithm ✅
• Mean Shift Clustering ✅

Semi-Supervised Learning Algorithms

• Self-Training Classifier ✅
• Co-Training ✅
• Tri-Training
• Generative Adversarial Networks (GANs) ✅

Reinforcement Learning Algorithms

• Q-Learning
• SARSA (State-Action-Reward-State-Action)
• Deep Q-Networks (DQN)
• Policy Gradient Methods
• Actor-Critic Methods
• Proximal Policy Optimization (PPO)
• Trust Region Policy Optimization (TRPO)
• Deep Deterministic Policy Gradient (DDPG)
• Soft Actor-Critic (SAC)
• Monte Carlo Tree Search (MCTS)

Ensemble Learning Algorithms

• Bagging ✅
• Boosting (Gradient Boosting, AdaBoost) ✅
• Stacking ✅
• Voting Classifier ✅
• Blending ✅

Dimensionality Reduction Algorithms

• Principal Component Analysis (PCA) ✅
• Linear Discriminant Analysis (LDA) ✅
• t-SNE ✅
• UMAP
• Singular Value Decomposition (SVD) ✅

Clustering Algorithms (for Specific Purposes) ✅

• k-Medoids ✅
• Affinity Propagation ✅
• Spectral Clustering ✅
• BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)
• OPTICS (Ordering Points To Identify the Clustering Structure)

Other Advanced Techniques

• Gaussian Processes (regression and classification) ✅
• Bayesian Networks
• Hidden Markov Models (HMM) ✅
• Markov Chains ✅
• VAE (Variational Autoencoder) ✅
• Deep Belief Networks (DBN)
• Attention Mechanisms and Self-Attention Models ✅