Algorithms in Engineering Contexts

Lesson 8 gave you the vocabulary — Big-O, arrays, hash tables, trees, graphs. This lesson puts those tools to work in engineering contexts. You won’t implement these algorithms from scratch (use libraries), but you need to know which algorithm to reach for and why.

Sorting and Searching: The Workhorses

Sorting and searching are the most common algorithmic operations in any software system. Engineering is no exception.

Standard Library Sort

Modern language runtimes use highly optimized sorting algorithms. Python uses Timsort (a hybrid merge sort / insertion sort), which is O(n log n) worst case and performs especially well on partially sorted data — which is common in engineering (sensor data is nearly time-ordered, node IDs are nearly sequential).

# Sort sensor readings by timestamp
readings.sort(key=lambda r: r["timestamp"])

# Sort elements by stress (descending) to find critical ones
elements.sort(key=lambda e: e["von_mises_stress"], reverse=True)
top_10_critical = elements[:10]

# NumPy sort for large numerical arrays
import numpy as np
stresses = np.array([145.2, 132.7, 178.4, 121.0, 165.9])
sorted_indices = np.argsort(stresses)[::-1]  # indices of descending order

Binary Search

If your data is sorted, binary search finds an element in O(log n) instead of O(n). For 1 million elements, that’s 20 comparisons instead of 1 million.

import bisect

# Sorted list of timestamped events
timestamps = [1.0, 2.5, 3.2, 4.8, 6.1, 7.3, 8.9, 10.0]

# Find where t=5.0 would be inserted (i.e., find the nearest event)
idx = bisect.bisect_left(timestamps, 5.0)
# idx = 4, so timestamps[3]=4.8 is just before and timestamps[4]=6.1 is just after

# Find all events in range [3.0, 7.0]
lo = bisect.bisect_left(timestamps, 3.0)
hi = bisect.bisect_right(timestamps, 7.0)
events_in_range = timestamps[lo:hi]  # [3.2, 4.8, 6.1]

Engineering context: Binary search is essential for time-series data. “Find the sensor reading closest to t = 14.7 seconds” is a binary search on a sorted timestamp array. “Find all events between 09:00 and 17:00” is two binary searches.

Hash-Based Lookup

When data isn’t sorted and you need O(1) lookup, use a hash table. This was covered in Lesson 8, but the pattern is worth repeating: if you’re searching a list repeatedly, convert it to a set or dictionary first.

# BAD: O(n) search on every iteration
flagged_nodes = ["N001", "N042", "N099", "N187", "N255"]
for node in all_nodes:          # 1,000,000 nodes
    if node.id in flagged_nodes: # O(n) scan of list each time
        process(node)
# Total: O(n * m) where m = len(flagged_nodes)

# GOOD: O(1) lookup per iteration
flagged_set = set(flagged_nodes)   # O(m) one-time build
for node in all_nodes:              # 1,000,000 nodes
    if node.id in flagged_set:      # O(1) average
        process(node)
# Total: O(n + m)

Graph Algorithms

Graphs model connections, dependencies, and networks. Three graph algorithms appear constantly in engineering:

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of a node before moving to the next level. It finds the shortest path (in terms of number of edges) between two nodes.

Engineering context — Structural connectivity: “If we remove beam B-17, is the structure still connected?” Remove the beam from the graph, run BFS from any node. If BFS doesn’t reach all nodes, the structure is disconnected — a critical safety concern.

from collections import deque

def is_connected(graph, start):
    """BFS to check if all nodes are reachable from start."""
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return len(visited) == len(graph)

Depth-First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It’s the basis for topological sorting, cycle detection, and finding connected components.

Engineering context — Dependency resolution: “In what order should I compile these 200 modules?” Model modules as nodes and imports as directed edges. A topological sort (based on DFS) gives a valid build order. If DFS finds a cycle, you have a circular dependency — a design flaw.

def topological_sort(graph):
    """DFS-based topological sort for dependency ordering."""
    visited = set()
    order = []

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for dep in graph.get(node, []):
            dfs(dep)
        order.append(node)

    for node in graph:
        dfs(node)

    return order[::-1]  # reverse post-order

# Module dependencies
deps = {
    "post_processor": ["solver", "mesh_io"],
    "solver": ["mesh_io", "materials"],
    "mesh_io": ["utils"],
    "materials": ["utils"],
    "utils": [],
}
build_order = topological_sort(deps)
# ["utils", "materials", "mesh_io", "solver", "post_processor"]

Dijkstra’s Algorithm

Dijkstra’s finds the shortest (lowest-cost) path in a weighted graph. It uses a priority queue to always expand the cheapest unexplored node.

Engineering context — Critical path analysis: In a project schedule, tasks are nodes and dependencies are weighted edges (task duration). The longest path through the graph is the critical path — the minimum possible project duration. Any delay on the critical path delays the entire project. (Note: critical path uses longest path, which is a variant, but the algorithmic concept is the same.)

Engineering context — Network routing: In a sensor network, Dijkstra’s finds the lowest-latency path from a sensor to the data collection hub, accounting for link speeds and hop counts.

Optimization Algorithms

Engineering is fundamentally about optimization: minimize weight, maximize stiffness, minimize cost subject to safety constraints. Different problem structures call for different optimization approaches.

Gradient-Based Optimization

When you have a smooth, differentiable objective function, gradient-based methods (gradient descent, Newton’s method, L-BFGS) are the fastest path to a solution. They follow the gradient downhill to a local minimum.

When to use: Structural topology optimization, shape optimization, neural network training, parameter fitting. The objective function must be differentiable (or approximately so).

Limitation: Gradient-based methods find local optima. If the landscape has multiple valleys, you may not find the global best. Common mitigations: multiple random starts, simulated annealing for initial exploration.

Metaheuristic Optimization

When the objective function is noisy, discontinuous, or has many local optima, metaheuristics explore the search space more broadly. Common approaches:

• Genetic algorithms: Evolve a population of candidate solutions through selection, crossover, and mutation. Good for multi-objective optimization (Pareto fronts).
• Simulated annealing: Random exploration that gradually becomes more focused. Good for combinatorial problems.
• Particle swarm optimization: Candidates (“particles”) explore the space and share information about good regions. Popular in antenna design and composite layup optimization.

When to use: Problems with discrete variables, non-smooth objectives, or many local optima. Sensor placement, material selection, structural member sizing with discrete catalogs.

Linear Programming (LP) and Integer Programming (IP)

When the objective function and constraints are all linear (or can be linearized), LP/IP solvers (Gurobi, CPLEX, or open-source GLPK/CBC) are dramatically more efficient than metaheuristics. They guarantee global optimality for linear problems.

When to use: Resource allocation, scheduling, supply chain optimization, budget-constrained material procurement.

Integer programming adds the constraint that some variables must be integers (e.g., you can’t buy 2.7 steel beams). IP is NP-hard in general, but modern solvers handle problems with millions of variables.

Choosing an Optimization Approach

Problem Characteristic	Recommended Approach
Smooth, differentiable objective	Gradient-based (L-BFGS, Adam)
Linear objective and constraints	Linear programming (LP solver)
Discrete decision variables	Integer programming or metaheuristics
Many local optima, noisy landscape	Genetic algorithms, simulated annealing
Multiple competing objectives	Multi-objective GA (NSGA-II)
Expensive function evaluations (FEA in the loop)	Surrogate-based / Bayesian optimization

Algorithms for Time-Series and Sensor Data

Engineering systems produce continuous streams of time-series data. Five algorithmic techniques appear repeatedly:

Moving Average (Smoothing)

Replaces each data point with the average of its neighbors. Removes high-frequency noise while preserving trends. A simple window of size k computes the mean of the k nearest points.

import numpy as np

def moving_average(signal, window_size):
    """Simple moving average filter."""
    return np.convolve(signal, np.ones(window_size) / window_size, mode="valid")

# Smooth noisy accelerometer data
raw_accel = np.array([0.12, 0.15, 0.98, 0.14, 0.13, 0.16, 0.95, 0.12])
smoothed = moving_average(raw_accel, window_size=3)

Trade-off: Larger window = smoother signal but slower response to real changes. Smaller window = noisier but more responsive. For structural monitoring, a 1-second window (100 samples at 100 Hz) is a common starting point.

Fast Fourier Transform (FFT)

Converts a time-domain signal to its frequency-domain representation. Reveals the dominant frequencies in the signal. O(n log n) using the FFT algorithm (vs. O(n²) for the naive DFT).

Engineering context: Identify the natural frequencies of a bridge from accelerometer data. If the dominant frequency shifts over time, the structure’s stiffness is changing — a potential sign of damage.

import numpy as np

# Accelerometer signal sampled at 100 Hz for 10 seconds
fs = 100  # sampling frequency
t = np.linspace(0, 10, fs * 10, endpoint=False)
signal = 0.5 * np.sin(2 * np.pi * 2.3 * t) + 0.3 * np.sin(2 * np.pi * 7.8 * t)

# FFT
freqs = np.fft.rfftfreq(len(signal), d=1/fs)
magnitudes = np.abs(np.fft.rfft(signal))

# Peaks at 2.3 Hz and 7.8 Hz reveal the natural frequencies

Kalman Filtering

A recursive algorithm that estimates the true state of a system from noisy measurements. It combines a prediction (from a physical model) with an observation (from sensors) to produce an optimal estimate.

Engineering context: GPS + accelerometer sensor fusion for structural displacement monitoring. GPS is accurate but slow (1 Hz). Accelerometers are fast (100 Hz) but drift. A Kalman filter fuses both to get fast, accurate displacement estimates.

When to use: Any situation where you have a physical model of the system and noisy sensor measurements. The Kalman filter optimally weights the model prediction vs. the sensor reading based on the uncertainty of each.

Change Point Detection

Algorithms that detect when the statistical properties of a time series change abruptly. Used to identify events: a sudden increase in vibration amplitude, a shift in temperature baseline, or a step change in strain readings.

Engineering context: Detect the exact moment a crack initiates in a fatigue test by identifying the change point in the strain gauge signal. Detect sensor malfunction by identifying sudden shifts in noise characteristics.

Common approaches: CUSUM (cumulative sum), Bayesian online change point detection, and the PELT (Pruned Exact Linear Time) algorithm.

Dynamic Time Warping (DTW)

Measures similarity between two time series that may be misaligned in time. Unlike Euclidean distance, DTW can match signals that are stretched or compressed along the time axis.

Engineering context: Compare vibration signatures from two different sensors or two different time periods. “Does this bridge’s vibration pattern today look like the pattern from last year?” DTW handles the fact that traffic patterns (and therefore load timing) differ between the two recordings.

Exercise 9.1: Algorithm Sketch for a Sensor Pipeline

Quiz

A build system has 200 Python modules with complex import dependencies. You need to determine a valid order to load them such that no module is loaded before its dependencies. Which algorithm solves this, and what graph concept does it rely on?

Answer

Topological sort on a directed acyclic graph (DAG). Each module is a node. Each import statement creates a directed edge from the importing module to the imported module. Topological sort produces a linear ordering where every module appears after all of its dependencies. The algorithm is O(V + E) where V is the number of modules and E is the number of import relationships. If the graph contains a cycle (circular import), topological sort will detect it — circular imports are a design flaw that must be resolved before a valid load order can exist.