IntermediateAlgorithmsPython
Run this module
Algorithms – Dynamic Programming¶
Overview¶
Dynamic Programming (DP) is an algorithmic technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result to avoid redundant computation. It converts exponential-time recursive solutions into polynomial-time ones.
In quantitative finance, DP is the foundation of many core models: binomial option pricing, optimal stopping (American options), portfolio rebalancing with transaction costs, and reinforcement learning-based trading agents.
Key Concepts¶
Two Approaches¶
Top-Down (Memoisation) - Write the natural recursive solution. - Cache (memoise) the result of each unique subproblem in a hash map. - On a repeated call, return the cached result immediately. - Lazy: only computes subproblems actually reached by the recursion.
Bottom-Up (Tabulation) - Identify the smallest subproblems and fill a table iteratively. - Build up to the full solution using previously stored answers. - Usually more memory-efficient and avoids recursion overhead.
Optimal Substructure¶
A problem has optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. This is a necessary condition for DP.
Overlapping Subproblems¶
Unlike divide-and-conquer (which solves non-overlapping subproblems), DP is valuable when the same subproblems recur many times in the naive recursive solution.
Complexity Comparison¶
| Approach | Time | Space |
|---|---|---|
| Naive recursion (Fibonacci) | O(2^n) | O(n) stack |
| Memoised recursion | O(n) | O(n) cache |
| Bottom-up tabulation | O(n) | O(n) or O(1) |
Files¶
dynamic_programming.py: Classic DP problems (Fibonacci, longest common subsequence, knapsack) with memoisation and tabulation implementations, plus finance-relevant applications.
How to Run¶
Financial Applications¶
1. Binomial Option Pricing¶
- The binomial tree is a DP table: each node's value is the discounted expected value of its two children.
- American options require an additional comparison with immediate exercise value at each node.
2. Optimal Stopping (American Options)¶
- DP solves: "at each time step, is it better to exercise now or wait?"
- The Longstaff-Schwartz algorithm uses regression + DP for Monte Carlo American option pricing.
3. Portfolio Rebalancing with Transaction Costs¶
- DP determines the optimal rebalancing policy over time: when the cost of rebalancing is outweighed by the expected improvement in portfolio allocation.
4. Optimal Trade Scheduling (VWAP/TWAP)¶
- Almgren-Chriss model: DP finds the optimal execution schedule that minimises market impact plus timing risk over a fixed horizon.
5. Regime-Switching Models¶
- Hidden Markov Model decoding (Viterbi algorithm) is a DP algorithm used to identify market regimes (bull/bear/volatile).
Best Practices¶
- Draw the recursion tree first: Identify which subproblems overlap before coding — this confirms DP is applicable.
- Define the state clearly: A DP state must capture everything needed to solve all remaining subproblems from that point.
- Optimise space: Many DP tables only depend on the previous row — use a rolling array to reduce O(n*m) space to O(m).
- Watch for floating-point accumulation: In financial DP (option trees, execution models), rounding errors accumulate across many table entries — use sufficient precision.
Continue in Algorithms¶
-
Backtracking is a general algorithmic technique for solving problems by building candidates incrementally and abandoning a candidate ("backtracking") as soon as it is determined to violate the problem constraints. It is a systematic form of exhaustive search that prunes the search space to avoid exploring clearly invalid paths.
-
Graph algorithms operate on structures composed of vertices (nodes) and edges (connections). Many financial problems are naturally modelled as graphs: currency markets form weighted directed graphs, asset correlation matrices define undirected weighted graphs, and order routing networks are flow graphs.
-
This module implements fundamental machine learning algorithms from scratch using only NumPy — no scikit-learn or frameworks. Building these algorithms by hand is the most effective way to understand what happens inside the black boxes used in production trading systems.
-
Searching algorithms find a target value within a data structure. The choice of algorithm determines whether a search takes O(n) time (checking every element) or O(log n) time (dividing the search space in half each step). In latency-sensitive financial systems, this difference is meaningful at scale.
-
A comprehensive implementation of fundamental sorting algorithms with detailed explanations, complexity analysis, and performance comparisons.
-
String algorithms handle efficient manipulation, searching, and analysis of text data. In quantitative finance, string processing is essential for parsing market data feeds, extracting information from news and filings, matching ticker symbols, and cleaning raw data from APIs.