LESSON 4.2 Data Structures and Algorithms for Financial Applications

1. LEARNING OBJECTIVES

By the end of this lesson, you will be able to:

Understand and implement fundamental data structures (arrays, linked lists, stacks, queues, trees, graphs, hash maps).
Analyze algorithmic complexity using Big-O notation.
Implement sorting and searching algorithms.
Build an order book using a priority queue (heap).
Implement a simple matching engine.
Use recursion for financial algorithms (e.g., binomial option pricing, amortization schedules).
Apply dynamic programming to solve financial optimization problems.
Understand and implement graph algorithms for financial networks (e.g., shortest path in payment systems).

2. ALGORITHMIC COMPLEXITY – BIG-O NOTATION

2.1 Definition

Big-O notation describes the asymptotic upper bound of an algorithm’s time or space complexity as the input size n grows.

Complexity	Name	Example
O(1)	Constant time	Array access, hash map lookup
O(log n)	Logarithmic time	Binary search, balanced tree operations
O(n)	Linear time	Linear search, iterating an array
O(n log n)	Linearithmic time	Merge sort, heap sort
O(n²)	Quadratic time	Nested loops, bubble sort
O(2^n)	Exponential time	Fibonacci (naive recursion)
O(n!)	Factorial time	Travelling salesman problem

2.2 Why Complexity Matters in Finance

HFT Systems: O(log n) or O(1) are required for order matching.
Risk Systems: O(n log n) is acceptable for portfolio calculations.
Monte Carlo Simulations: O(n) per path; we optimize with O(1) operations per step.

2.3 Space Complexity

Measures the memory required by an algorithm:

O(1): In-place operations.
O(n): Creating a copy of the data.
O(n²): Storing a full matrix.

3. FUNDAMENTAL DATA STRUCTURES

3.1 Arrays (Contiguous Memory)

# Python lists are dynamic arrays
prices = [100, 102, 98, 105, 110]

# Access: O(1)
print(prices[2])  # 98

# Append: O(1) amortized
prices.append(115)

# Insert: O(n)
prices.insert(2, 99)  # Insert at index 2

# Delete: O(n)
del prices[1]

3.2 Linked Lists

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def find(self, data):
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None
    
    def __len__(self):
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

# Time Complexity:
# Append: O(n)
# Find: O(n)
# Insert at head: O(1)
# Delete at head: O(1)

3.3 Stacks (LIFO)

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop() if not self.is_empty() else None
    
    def peek(self):
        return self.items[-1] if not self.is_empty() else None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def __len__(self):
        return len(self.items)

# Time Complexity: O(1) for all operations
# Application: Evaluating mathematical expressions, recursion simulation

3.4 Queues (FIFO)

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.popleft() if not self.is_empty() else None
    
    def peek(self):
        return self.items[0] if not self.is_empty() else None
    
    def is_empty(self):
        return len(self.items) == 0

# Time Complexity: O(1) for all operations
# Application: Order processing, task scheduling, message queues

3.5 Hash Maps (Dictionaries)

# Python dictionaries are optimized hash maps
order_book = {
    "AAPL": {"bid": 150.00, "ask": 150.25},
    "GOOGL": {"bid": 2800.00, "ask": 2805.00}
}

# Insert: O(1) average
order_book["MSFT"] = {"bid": 330.00, "ask": 330.50}

# Lookup: O(1) average
price = order_book["AAPL"]["bid"]

# Delete: O(1) average
del order_book["AAPL"]

# Iteration: O(n)
for symbol, data in order_book.items():
    print(f"{symbol}: {data}")

3.6 Heaps (Priority Queues)

import heapq

class OrderPriorityQueue:
    def __init__(self):
        self.heap = []
    
    def push(self, priority, order):
        # For buy orders: higher price = higher priority (negative)
        # For sell orders: lower price = higher priority
        heapq.heappush(self.heap, (priority, order))
    
    def pop(self):
        return heapq.heappop(self.heap) if self.heap else None
    
    def peek(self):
        return self.heap[0] if self.heap else None
    
    def __len__(self):
        return len(self.heap)

# Time Complexity:
# Push: O(log n)
# Pop: O(log n)
# Peek: O(1)
# Application: Order matching engine (buyers sorted descending, sellers sorted ascending)

4. BINARY SEARCH TREES (BST)

4.1 Implementation

class TreeNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key, value):
        if not self.root:
            self.root = TreeNode(key, value)
            return
        
        current = self.root
        while True:
            if key < current.key:
                if current.left:
                    current = current.left
                else:
                    current.left = TreeNode(key, value)
                    return
            elif key > current.key:
                if current.right:
                    current = current.right
                else:
                    current.right = TreeNode(key, value)
                    return
            else:
                current.value = value
                return
    
    def find(self, key):
        current = self.root
        while current:
            if key == current.key:
                return current.value
            elif key < current.key:
                current = current.left
            else:
                current = current.right
        return None
    
    def inorder_traversal(self):
        result = []
        def _inorder(node):
            if node:
                _inorder(node.left)
                result.append((node.key, node.value))
                _inorder(node.right)
        _inorder(self.root)
        return result

# Time Complexity:
# Insert: O(log n) average, O(n) worst-case
# Find: O(log n) average, O(n) worst-case
# Inorder Traversal: O(n)
# Application: Order book price levels, time-series data indexing

4.2 Self-Balancing Trees (AVL, Red-Black)

Python’s sortedcontainers library provides efficient balanced tree implementations:

from sortedcontainers import SortedDict

# Sorted dictionary maintains keys in sorted order
order_volume = SortedDict()
order_volume[100] = 1000   # Price 100, volume 1000
order_volume[101] = 500
order_volume[99] = 2000

# Find nearest price levels
above_100 = order_volume.iloc[1:]  # Prices >= 100
below_100 = order_volume.iloc[:1]   # Prices < 100

5. SORTING ALGORITHMS

5.1 QuickSort (O(n log n))

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

5.2 MergeSort (O(n log n))

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

5.3 Python’s Built-in Sort (Timsort)

# Python's sort uses Timsort (O(n log n) worst-case, O(n) best-case)
prices = [100, 102, 98, 105, 110]
prices.sort()  # In-place sorting
sorted_prices = sorted(prices)  # Returns new list

6. SEARCHING ALGORITHMS

6.1 Binary Search (O(log n))

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

6.2 Interpolation Search (O(log log n) average)

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and target >= arr[low] and target <= arr[high]:
        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

6.3 Hash Map Lookup (O(1))

# For exact matches, hash maps are optimal
price_lookup = {100: "AAPL", 102: "GOOGL", 98: "MSFT"}
symbol = price_lookup.get(102)  # O(1)

7. RECURSION IN FINANCIAL ALGORITHMS

7.1 Binomial Option Pricing

def binomial_option_price(S, K, T, r, sigma, n_steps, option_type='call'):
    dt = T / n_steps
    u = np.exp(sigma * np.sqrt(dt))
    d = 1 / u
    p = (np.exp(r * dt) - d) / (u - d)
    
    # Terminal payoffs
    prices = S * (u ** np.arange(n_steps, -1, -1)) * (d ** np.arange(0, n_steps + 1))
    if option_type == 'call':
        payoffs = np.maximum(prices - K, 0)
    else:
        payoffs = np.maximum(K - prices, 0)
    
    # Backward induction
    for i in range(n_steps - 1, -1, -1):
        payoffs = np.exp(-r * dt) * (p * payoffs[:-1] + (1 - p) * payoffs[1:])
    
    return payoffs[0]

7.2 Amortization Schedule Generation

def generate_amortization_schedule(principal, rate, periods):
    def _generate(remaining, period):
        if period > periods:
            return []
        payment = principal * rate * (1 + rate)**periods / ((1 + rate)**periods - 1)
        interest = remaining * rate
        principal_paid = payment - interest
        schedule = [{
            'period': period,
            'payment': payment,
            'interest': interest,
            'principal': principal_paid,
            'remaining': remaining - principal_paid
        }]
        return schedule + _generate(remaining - principal_paid, period + 1)
    
    return _generate(principal, 1)

7.3 Recursion in Dynamic Programming (DP)

def max_profit_from_trades(prices, transaction_fee=0):
    """
    Maximize profit from stock trades using DP with recursion.
    """
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(day, holding):
        if day >= len(prices):
            return 0
        
        # Do nothing
        do_nothing = dp(day + 1, holding)
        
        if holding:
            # Sell
            sell = prices[day] - transaction_fee + dp(day + 1, 0)
            return max(do_nothing, sell)
        else:
            # Buy
            buy = -prices[day] + dp(day + 1, 1)
            return max(do_nothing, buy)
    
    return dp(0, 0)

8. GRAPH ALGORITHMS FOR FINANCIAL NETWORKS

8.1 Shortest Path (Dijkstra’s Algorithm)

import heapq

def shortest_path(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    previous = {}
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current == end:
            break
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current].items():
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                previous[neighbor] = current
                heapq.heappush(pq, (new_dist, neighbor))
    
    # Reconstruct path
    path = []
    current = end
    while current in previous:
        path.append(current)
        current = previous[current]
    path.append(start)
    path.reverse()
    
    return path, distances[end]

# Application: Finding the cheapest payment route in a correspondent banking network

8.2 Transaction Graph Analysis

class TransactionGraph:
    def __init__(self):
        self.graph = defaultdict(dict)
    
    def add_transaction(self, sender, receiver, amount):
        self.graph[sender][receiver] = self.graph[sender].get(receiver, 0) + amount
    
    def detect_cycles(self):
        """
        Detect circular transactions (potential money laundering).
        """
        visited = set()
        path = []
        
        def dfs(node):
            if node in path:
                cycle_start = path.index(node)
                return path[cycle_start:]
            if node in visited:
                return None
            visited.add(node)
            path.append(node)
            for neighbor in self.graph.get(node, {}):
                result = dfs(neighbor)
                if result:
                    return result
            path.pop()
            return None
        
        for node in self.graph:
            result = dfs(node)
            if result:
                return result
        return None

9. PRACTICAL IMPLEMENTATION

A. Order Book Implementation Using Heaps:

class OrderBook:
    def __init__(self):
        self.buy_orders = []  # Max-heap (using negative prices)
        self.sell_orders = []  # Min-heap
        self.order_count = 0
    
    def add_buy_order(self, price, quantity):
        self.order_count += 1
        heapq.heappush(self.buy_orders, (-price, self.order_count, quantity))
    
    def add_sell_order(self, price, quantity):
        self.order_count += 1
        heapq.heappush(self.sell_orders, (price, self.order_count, quantity))
    
    def match_orders(self):
        trades = []
        while self.buy_orders and self.sell_orders:
            buy_price = -self.buy_orders[0][0]
            sell_price = self.sell_orders[0][0]
            
            if buy_price >= sell_price:
                buy_order = heapq.heappop(self.buy_orders)
                sell_order = heapq.heappop(self.sell_orders)
                
                buy_qty = buy_order[2]
                sell_qty = sell_order[2]
                
                trade_qty = min(buy_qty, sell_qty)
                trade_price = sell_price  # For simplicity
                
                trades.append({
                    'price': trade_price,
                    'quantity': trade_qty
                })
                
                if buy_qty > trade_qty:
                    heapq.heappush(self.buy_orders, (-buy_price, self.order_count, buy_qty - trade_qty))
                if sell_qty > trade_qty:
                    heapq.heappush(self.sell_orders, (sell_price, self.order_count, sell_qty - trade_qty))
            else:
                break
        
        return trades

# Example usage
order_book = OrderBook()
order_book.add_buy_order(100, 500)
order_book.add_buy_order(101, 300)
order_book.add_sell_order(99, 200)
order_book.add_sell_order(102, 400)

trades = order_book.match_orders()
print(trades)

B. Dynamic Programming for Portfolio Optimization:

def knapsack_portfolio(capital, assets):
    """
    Select assets to maximize expected return given capital constraint.
    assets: list of (cost, expected_return)
    """
    n = len(assets)
    dp = [0] * (capital + 1)
    selected = [[] for _ in range(capital + 1)]
    
    for i, (cost, return_val) in enumerate(assets):
        for c in range(capital, cost - 1, -1):
            if dp[c - cost] + return_val > dp[c]:
                dp[c] = dp[c - cost] + return_val
                selected[c] = selected[c - cost] + [i]
    
    return dp[capital], selected[capital]

C. Graph-Based Payment Routing:

def find_cheapest_routing(correspondent_network, source_bank, target_bank):
    """
    Find the cheapest payment routing path through a correspondent banking network.
    """
    return shortest_path(correspondent_network, source_bank, target_bank)

10. SUMMARY FOR THE FINANCE PRACTITIONER

Data Structures are the building blocks of financial systems. Choose wisely based on operations:
- Arrays for price history (O(1) access).
- Hash maps for order books (O(1) lookup).
- Heaps for priority queues (O(log n) insert/pop).
- Trees for price levels (O(log n) search).
Algorithmic Complexity determines system performance. HFT systems require O(1) or O(log n) operations.
Sorting and Searching are fundamental. Python’s Timsort is optimized for real-world data.
Recursion and Dynamic Programming are essential for financial algorithms (option pricing, optimization).
Graph Algorithms are used for payment routing, transaction analysis, and systemic risk measurement.

Diploma in Financial Technology LESSON 4.2 Data Structures and Algorithms for Financial Applications

Diploma in Financial Technology