Amazing Algorithms

For Solving Problems in Software

Barry S. Stahl

Principal Engineer - AZNerds.net

@bsstahl@cognitiveinheritance.com

https://CognitiveInheritance.com

Favorite Physicists

1. Harold "Hal" Stahl
2. Carl Sagan
3. Richard Feynman
4. Marie Curie
5. Nikola Tesla
6. Albert Einstein
7. Neil deGrasse Tyson
8. Niels Bohr
9. Galileo Galilei
10. Michael Faraday

Other notables: Stephen Hawking, Edwin Hubble, Leonard Susskind, Christiaan Huygens

Favorite Mathematicians

1. Ada Lovelace
2. Alan Turing
3. Tim Berners-Lee
4. Isaac Newton
5. Emmy Noether
6. Johannes Kepler
7. René Descartes
8. George Boole
9. Carl Friedrich Gauss
10. Grace Hopper

Other notables: Blaise Pascal, Daphne Koller, Grady Booch, Evelyn Berezin, Pascal Van Hentenryck

• See my presentation from CodeMash 2025: How the Fediverse Could Save Democracy & Why It Probably Won't

• Hear my thoughts on why a thriving Fediverse is so critical on David Giard's Technology and Friends show.

• Learn more about the Fediverse at fediverse.party.

• Get your own Mastodon account at Join Mastodon.

  • Don't stress on what server to use, just pick one and go. You can always move later.

• Follow me on Mastodon at @bsstahl@CognitiveInheritance.com.

Attempts to make the best possible decision​ based on the model and the data

• Model - Our description of the problem
• Data - Our understanding of the state of the domain

The success of a problem-solving algorithm is often determined before the algorithm even runs -- by how the problem is modeled

• Modeling defines the problem space
  • What’s included & what’s ignored
  • Poor models lead to irrelevant solutions

• Modeling shapes the solution strategy
  • Logical models » OOP or Rules Engines
  • Graph models » traversal algorithms
  • Constraint models » LP or MIP
  • Probabilistic models » Neural/Bayesian Networks

• Modeling can determine tractability
  • Some formulations make problems NP-hard
  • Others reveal polynomial-time solutions
  • Examples
    • Conference Scheduling with LP vs MIP
    • Traveling Salesman with OOP

• Describe these algorithms
  • Show models that work well with each type of problem
  • Describe sample implementations for your use
  • Provide intuition as to why they work as they do

• A family of combinatorial optimization problems
• Goal
  • Select a subset of items from a larger set
  • Without exceeding resource constraints
  • Such that total value is maximized

Store the results of function calls for reuse when the same inputs occur again

• Goal: Compute the nth Fibonacci number
  • F(n) = F(n-1) + F(n-2)
• Naïve Recursion
  • Recomputes each subproblem multiple times
  • O(2ⁿ) Problem - Exponential time
• With Memoization
  • Store results of F(k)
  • Reuse stored values
  • O(n) Problem - Linear Time

In optimization, decision variables are the values we are solving for

• In knapsack problems, each candidate item has a boolean decision variable

  • \(x_i = 1\) means include item \(i\)
  • \(x_i = 0\) means exclude item \(i\)

• The goal is to choose the combination of \(x_1, x_2, ... x_n\) that gives the best valid knapsack

• Start at the 1st space on the board​
• While we haven't reached the last space​
  • Add the space to the current path​
  • If the current space has a ladder​
    • Add the end of the ladder to the path​
    • Make that space the current space​
  • Move to the next space on the board​
• Return the completed path through the board

DetermineDistance(s,d)

• Call DetermineDistance(space[0], 0)
• If shorter​ than previously found
  • Set DistanceFromStart property
  • If this space starts a chute or ladder​
    • DetermineDistance(endOfNavigation, distanceFromStart+1​)
  • If not at the end of board​
    • DetermineDistance(nextSpace, distanceFromStart+1)
• Return all spaces with their DistanceFromStart property populated

• Start at the last space on the board​
• While we are still on the board​
  • Add the current space to the path​
  • Set the current space to a space that is a neighbor of the current space and whose DistanceFromStart is space.DistanceFromStart-1​
• Reverse the direction of the path​

• Populate the cache​
  • Simple calculations​
  • Build from the ground-up​
• Use the cached data to determine the answer(s)​
  • Work backwards through the cache​
• Guaranteed Optimality​
  • A fully populated cache means all options are explored​
  • Works in any number of dimensions​
• Works with any graph (nodes & edges)​
  • Works best when​
    • Problems can be described recursively​
    • 1 or more axis are limited in scope

• Beary is chunking content inefficiently

• We really have a segmentation problem

  • Given a paragraph, where do the boundaries belong?

• Each candidate chunk has a quality score

  • Semantically coherent chunks > mixed-topic chunks

• The goal is global, not local

  • Maximize the total chunk quality across the whole paragraph

• This is the same shape as earlier DP problems

  • We are choosing an optimal partition, like shortest-path and knapsack style decisions

• Score each candidate chunk with a simple objective

• High internal similarity is good

  • Sentences that belong together should raise the score

• Bigger chunks pay a penalty

  • We do not want one oversized chunk to absorb unrelated ideas

• This is value minus cost

  • Reward improvements to the solution
  • Penalize what bloats the solution

• Greedy segmentation can look right and still lose

  • Local best can block a better score later

• Brute-force segmentation is expensive over large datasets

  • Combinations grow exponentially with sentence count

• Dynamic Programming gives optimal chunking in O(n^2)

  • Solve each suffix once and reuse it

• Uses the same memoization pattern
  • State at index \(i\), try choices \(j\), cache best future value

• AIDemos Repo

• Exercise Spreadsheet

• AIDemos Repo

• Exercise Spreadsheet

Find Solutions by Simulating Darwinian Evolution​

• Each candidate solution is defined by its properties (chromosomes)​
• A fitness function is used to determine which solutions "survive"
  • A simulation may be used as the fitness function
• Surviving solutions may mutate and evolve other solutions​

• Optimal solution may never be found
  • i.e. If a optimality requires a large combination of elements
• Optimum may be found but not recognized
  • If conditions make that solution non-optimal at that moment
    • i.e. If a key feature is not used during the simulation
  • Minimize the liklihood by increasing simulation size

• Want the full Genetic Algorithms deep dive?

• Dedicated 1-hour session

  • Tomorrow at 10:00 AM

• We will cover

  • DNA representation and fitness design
  • Evolution parameters and convergence tradeoffs
  • End-to-end implementation details and experimentation

Ways to organize a collection of items into meaningful subsets

• Classification - grouping using known categories
• Clustering - grouping by discovering categories

Grouping data into known categories based on features of each item

• Can be used for:
  • Grouping items with shared properties together
  • Identifying which known group a new item belongs to
  • Normalization of input/output
• Usually based on a training set of labeled data
  • The model learns the features that define each category
  • New items are classified based on learned features
  • Classification is a supervised learning problem

• A classifier divides feature space into regions

• Each region predicts a different target class

• The line between regions is a decision boundary

• New inputs are classified by where they land

• Different algorithms draw different kinds of boundaries

• Class Imbalance: one class dominates the training data

• Majority Class Bias: model defaults to the common class

• Example: 99% dogs, so a wolf is predicted as "dog"

• Why: loss is optimized by being right on frequent examples

• Fixes: class weighting, oversampling/SMOTE, undersampling, threshold tuning

• Decision trees are readable classification models

  • Each split asks a question about a feature
  • Each branch narrows the possible class
  • Each leaf predicts a target class
  • Random forests use many trees & combine votes
    • Less explainable
    • Often generalize better

• Rule-based classifiers

  • Explicit if/then rules
  • Usually written by people

• Separate classes with a weighted feature score

  • Each feature contributes to the final decision
  • The boundary is a line or flat surface in feature space

• Boundary Identification Methods

  • Logistic regression
    • Estimates the probability of a class
  • Linear SVMs
    • Support Vector Machines
    • Find the hyperplane that maximizes margin between classes

• k-Nearest Neighbors

  • Which labeled examples are closest
  • Predicted class is the majority of neighbors

• Nearest Centroid

  • Compute the centroid of each class
  • Predicted class is the closest centroid

• The same concept is central in clustering

Estimate which label is most likely

• Naive Bayes

  • Combines evidence from observed features
  • Lightweight and useful for text-like signals
  • Often used in spam detection & sentiment analysis

• Gaussian Mixture Models (GMMs)

  • Classes modeled as a mix of distributions
  • Assumes features follow a normal distribution
  • Complicated and expensive but can be very accurate

• In both cases output is a ranked set of class scores

• The final label is the highest-scoring class

Accuracy alone can hide important mistakes

• A "confusion matrix" shows prediction vs actual
• False positives and negatives may have different costs
  • Please no false negatives from my fire alarm
  • False positives are annoying but not dangerous
• Precision: are positive predictions trustworthy?
  • High-Precision: Usually predicts wolves properly
  • Low-Precision: May predict wolf when just a dog
• Recall: were the important positives found?
  • High-Recall: Usually finds all the wolves
  • Low-Recall: May miss a wolf but often correct when it predicts one

• Classification starts with known target classes

  • Which known label fits this item?

• Clustering starts without those labels

  • What groups seem to exist?

• Both can use the same feature space

• Unsupervised machine learning technique
• Clusters form around centroids (geometric center)
• Data points are grouped based on their similarity
  • Minimize the error (distance from centroid)
• Advantages
  • No need to define a distance threshold
• Disadvantages
  • Quality is use-case dependent
  • Often requires the number of clusters to be specified

Groups points around centroids

• Iterative process

  • Start by choosing \(k\), the number of clusters
  • Assign each point to the nearest centroid
  • Move each centroid to the middle of its assigned points
  • Repeat until the assignments converge

• Different \(k\) values can tell different stories

• Use context and experimentation to determine utility

  • Quality metrics can help

Builds a similarity tree (dendogram)

• Iterative process

  • Start with each item in its own group
  • Nearby items merge into small groups
  • Small groups merge into larger groups

• Cutting the tree at different heights gives different cluster counts

• Useful when the right number of groups is not obvious

Finds dense regions in feature space

• Crowded neighborhoods become clusters
  • Clusters high density regions separated by low density
  • Does not require \(k\) up front
  • Sparse isolated points are treated as noise
• Can find irregular shapes that k-Means misses
  • k-Means centroids assume spherical clusters
  • Mapping is a common use-case
• Can be distributed using DDBSCAN
  • Similar to MapReduce, but with a merge step

Clusters are groupings without meaning

• LLMs can identify themes in textual clusters
  • Other models needed for different data types
  • Can be used on the group or on the centroid
• Labels identify groups with usable categories
  • Unlocks routing, triage, and analytics workflows

Labeled clusters become direct decision inputs

• Routes can be mapped
  • Teams
  • Pipelines
  • Archives
  • Queues
• Automation replaces keyword rules
  • Reduces brittleness
  • Reduces maintenance
  • Updates can be automated

With no existing labels, we need to evaluate cluster structure directly

• Silhouette Score
  • Higher scores: tighter clusters and better separation
  • \(\text{Silhouette} = \frac{\text{separation}}{\text{cohesion}}\)
• Davies-Bouldin Index
  • Lower scores: less overlap and cleaner boundaries
  • \(\text{DBI} = \frac{\text{within‑cluster scatter}}{\text{between‑cluster separation}}\)
• Calinski-Harabasz Score
  • Higher scores: clusters more tighter and more separated
  • \(\text{CH} = \frac{\text{between‑cluster variance}}{\text{within‑cluster variance}}\)

Good scores \(\neq\) fitness for purpose

• Evaluation is about whether the grouping is useful
  • Will the grouping help the real task?
• Good clusters are:
  • Cohesive internally
  • Separated from each other
  • Interpretable and actionable
  • Useful for our needs

• A point in multi-dimensional space
• Mathematical representation of a word or phrase
• Encode both semantic and contextual information

• Model: text-embedding-ada-002
• Vectors normalized to unit length
• Use 1536 dimensions

Creating Order from Chaos

• Unstructured string => Structured float[]
• Allows mathematical operations
  • Cosine Similarity & Distance
  • Nearest Neighbor Search
  • Clustering
  • Vector Addition & Subtraction
  • Dimensionality Reduction (e.g., PCA)
  • Anomaly Detection

Relate vectors based on the angle between them

• Cosine Similarity ranges from -1 to 1, where:

  • +1 indicates that the vectors represent similar semantics & context
  • 0 indicates that the vectors are orthogonal (no similarity)
  • -1 indicates that the vectors have opposing semantics & context

• Cosine Distance is defined as 1 - cosine similarity where:

  • 0 = Synonymous
  • 1 = Orthogonal
  • 2 = Antonymous

Note: For normalized vectors, cosine similarity is the same as the dot-product

• Embeddings: place similar statements close together
• Clustering: group them into meaningful categories
• LLMs: can label each cluster
• Routing: new statements to the best cluster
• Actions: each cluster maps to a workflow

• \(\text{text}➝\text{embedding}➝\text{cluster}➝\text{label}➝\text{routing}➝\text{action}\)
• Clustering is the structural bridge from text to automation

Goal: To see unsupervised structure emerge from embeddings using clustering

• Download the code for k-Means clustering from GitHub
• Review the axioms.js data file
• Review the k-Means loop
• Review the quality scoring code
• Run the code to create 4 clusters
  • Review the Representative axioms for each cluster
  • Review the quality scores
• Choose a different \(k\) and rerun
  • See how cluster structure changes

• LLMs are one kind of learning model
• Learning models are one kind of AI model
• Logic, search, optimization, and planning are often AI

Image: Yoshua Bengio by By Xuthoria

Attempts to make the best possible decision​ based on the model and the data

• Model - Our description of the problem
• Data - Our understanding of the state of the domain

• Logic​al - Reducible to conditionals​
  • Object Oriented​
  • Rules Engine

• Search/Optimization - Reduce and Search the Solution Space
  • Dynamic Programming​
  • Constraint Programming

• Probabilistic/Learning - Predicts best solution from earlier data
  • Neural/Bayesian Networks
  • Genetic Algorithms

Finding the best available solution to a problem by minimizing or eliminating undesirable factors and maximizing desirable ones.

• A Combinatorial Puzzle
  • 9x9 grid
  • Each row, column and 3x3 region contains [1 to 9]
• AllDifferent constraints
  • With values restricted to integers [1 to 9]
  • 27 Constraints in total (9 rows, 9 columns, 9 regions)

• Solution Space (aka Search Space or Feasibility Set)

  • All values that satisfy the constraint(s)

• The solution space for a 9x9 grid is inconceivably large

  • Roughly \(2 \times 10^{77}\) possible solutions
  • At 1 Trillion per second it would take \(6 \times 10^{57}\) years

• Even with the AllDifferent constraint, its \(6.7 \times 10^{21}\)

  • Naïve (brute-force) methods are not practical

• Using constraints, we can reduce the possibilities
• Each new learning adds new constraints

• Question: How do we check for feasibility here?

• Possible solutions: \(5 \times 10^{73}\)

  • Search space reduced by 4 orders-of-magnitude
  • Roughly 10K Possibilities Eliminated

• Let's jump ahead

  • All of the values we've been given are filled-in

• All starting info filled-in
  • Search space pruned appropriately
  • Possible solutions: \(4 \times 10^{21}\)
  • Eliminating 56 orders of magnitude
• We're not nearly done yet
  • Look closely at the remaining options

• The reduction of search options
  • "Fixed" the value of 4 cells

• Adding info means we learn even more
  • We can reduce the search space further
• Possible solutions: \(2 \times 10^{20}\)

• We now have even more "fixed points"
• We continue to iteratively propagate constraints
  • Known as a "Fixed-Point Algorithm"
• Let's jump ahead to completion of the propagation

• Possible solutions: 1
• “Guesses” Required: 0
  • Only solution was apparent after propagation
• CSPs are not always this easy
  • Many require some form of search

Determine the ideal production targets for Pete's Pottery Paradise

• Products​
  • Small Vase​
    • 1 oz. clay, 1 oz. glaze​
    • Sells for $3.00 each​
  • Large Vase​
    • 4 oz. clay, 2 oz. glaze​
    • Sells for $9.00 each​

• Inventory​
  • Clay - 24 oz.​
  • Glaze - 16 oz.​

• Goal
  • Maximize Revenue

• Created by George Dantzig in 1947
• Built to solve linear programming problems
  • Allocate scarce resources under constraints
• Searches the vertices of the feasible region
  • Usually far fewer places than every possible solution
• Still used inside modern optimization solvers
  • Planning, routing, scheduling, logistics, finance

Simplex turns optimization into a short guided walk

• Start at any feasible vertex
  • Determine direction that improves revenue fastest
  • Move along an edge until a constraint stops you
• Pivot to the new axis
  • Repeat from the new vertex
• Stop when every neighboring vertex is worse

• Start: (0 small, 0 large) -> revenue $0
• Enter: make large vases first
  • They add $9 each, so revenue rises quickly
• Leave: clay becomes the limiting constraint
  • 24 oz clay / 4 oz per large = 6 large
• New corner: (0 small, 6 large) -> revenue $54
• Pivot: trade along the clay edge
  • Stop at (8 small, 4 large) when glaze also binds
• No adjacent corner improves revenue -> optimum $60

Determine the best schedule for talks at a conference

• Relax the constraints:

  • Boolean vars → continuous vars \(\in [0,1]\)
  • Run Simplex to find a solution in the continuous space
  • This becomes a "smooth" estimate of good solution locations

• Use this to guide a search through nearby boolean options

• Repeat until the best integral solution is found

A Suite of Tools for Solving Combinatorial Optimization Problems

• Constraint Solver
• Unified LP & MIP Interface
  • GLOP – LP Solver
  • CBC – MIP Solver
  • Can be built with other solvers, including Gurobi

• Define Constraints that the Solution Must Satisfy​
  • Use these constraints to limit the search space​
    • More constraints = smaller search space
      • Solutions that exist are found faster
      • May not find a feasible solution

• Add an Objective Function to Improve Solutions​
  • All constraints must be satisfied first​
  • Objectives are a goal relative to an equation​
    • i.e. Maximize revenue where r = 3X + 9Y

Build the Pete's Pottery Paradise LP model and solve it with Google OR-Tools.

• Define the decision variables
• Add the constraints
• Add the objective function
• Ask the solver for the best feasible solution

• Google OR-Tools Docs
• Google.OrTools NuGet Package
• Scan the QR code to open the exercise solution.

• Best Path Algorithms

  • Ant Colony Optimization
  • Bee Colony Optimization

• Cost Reduction Algorithms

  • Firefly Optimization
  • Amoeba Optimization

• AI Models

  • Intro to Optimizing AI Models
  • Training an AI Model Using Amoebas

• Greater Usage => More Pheromones
• Shorter Path Length => More Pheromones Remain
• More Pheromones => Higher Probability of Usage

• Neighborhood Search
  • Start with random paths
  • Explore neighboring paths based on probability
  • More pheromone = Higher probability of use
  • Can get stuck in a local minima
• Tweaks
  • Number of ants
  • Pheromones to dispense
  • Pheromone dissipation rate
• Features
  • Less sensitive to scale
  • Optimality not guaranteed

Active Workers

Forage on their known path and on a neighboring path

Scouts

Forage on a random path

Inactive Workers

Wait for information from other bees

• Multiple Search types
  • Active Workers perform neighborhood search
  • Scouts perform random search
  • Best known path propogates
• Tweaks
  • Number of each type of bee
  • Probability of persuasion
  • Visit limit
• Features
  • Less Sensitive to Scale
  • Optimality not guaranteed

Optimization algorithm used to minimize the cost function of a model

• Shifts the parameters in the opposite direction of the cost gradient

  • The 1st derivative of the cost function

  • Represents the slope of that function

• Hyperparameters include:

  • Number of iterations

  • Learning rate

  • Convergence criteria

• Stochastic Gradient Descent

  • Updates parameters using a subset of data each cycle

Y = mX + B

• Every neuron gets its value from a linear transformation

• Multiple inputs result in a sum of the linear transformations

  • The sum of a linear transformation is linear

• Only linearly-separable functions can be modeled without a non-linear activation

• Parameters: Internal values learned during training

  • Define the relationship between input and output

  • Adjusted to minimize prediction error

• In Linear Regression: Y = mX + b

  • m: Slope (Weight) - The influence of X on Y

  • b: Intercept (Bias) - Shifts the output vertically

• In more complex models:

  • Counts include weights/biases across layers

  • Can capture non-linear relationships

  • Parameter counts are a proxy for complexity

  • GPT-4 uses roughly 1.8 trillion parameters

• X-Axis: The value of the weight (m)
• Y-Axis: The value of the bias (b)
• Z-Axis: The size of the error

The weight (m) often has a greater effect on the error than the bias (b)

• Objective: Minimize the error
  • Error: The difference between the predicted value and the actual value
  • MSE: Mean Squared Error - Avg of the squared differences between predicted and actual
• Means: Gradient Descent Optimization
  • Nearly any Optimization algorithm can be used
  • Gradient Descent is the most common/suited

• Linear Regression - C# Code
• AND Gate Model - Excel
• Maintainability Model - Excel

Predict the unknown values in a linear equation​

• Given X (time), predict Y (location)​
  • Y = mX + b​
• Find the best values for m and b ​
  • Minimize total error

• Roach Infestation Optimization
• Particle Swarm Optimization
• Multi-Swarm (Birds) Optimization
• Bacterial Foraging Optimization

• Code Samples

  • Dynamic Programming

  • AI Demos

  • The Algorithms Repo

• My Articles/Presentations

  • Scalable Decision Making

  • AI That Can Explain Why

  • An Example of a Hybrid AI Implementation

  • Building AI Solutions with Google OR-Tools

• Academic Resources

  • Optimization - Coursera Course

  • Clemson University

• Other Articles

  • MSDN Magazine - Firefly Optimization

  • MSDN Magazine - Bee Colony Optimization

  • MSDN Magazine - Amoeba Optimization

  • MSDN Magazine - Ant Colony Optimization

Would you like to try to model a problem from one of your domains?