I tend to remember techniques more than specific algorithms, but:
One really fun algorithm involved optimizing an n^2 naive tree algorithm to O(n), ignoring logs.
For me, the way I reasoned about it was expanding the number of objects to consider (n^3), then there were observations you could apply to bring it down to O(n).
If you asked me what exactly the correspondence was between the final reduction and the original problem statement, I couldn't tell you. Maybe there was a more direct way to get to the solution.
But that style of thinking carries on with me to real tasks too. Sometimes it's easier to simplify, other times it might actually be easier to complexify, as long as you trust that you're not going down "arbitrary" complexity.
Long, long ago I came up with a text search algorithm while working on PCxRef to help technical sales support at IBM. My first approach using a naive string search took about 30 seconds on a PC. My algorithm got it down to the speed of disk access.
Basically I precomputed a table of masks and used the XLAT instruction in a very tight loop to fly though all the product descriptions for everything IBM offered back around 1983. I could accommodate case insensitivity and single character wildcards.
The test search was always "dos tech ref" to find the IBM DOS Technical reference manual.
An auto-arrange feature for a LabVIEW/ComfyUI type DAG programming language. Could take a program with hundreds of nodes and edges and arrange them nicely so none of the lines intersected and blocks were grouped logically.
Nothing says efficiency like a sorting algorithm where Big O is more influenced by the largest element's value rather than the number of elements in the array. /s
I tend to remember techniques more than specific algorithms, but:
One really fun algorithm involved optimizing an n^2 naive tree algorithm to O(n), ignoring logs.
For me, the way I reasoned about it was expanding the number of objects to consider (n^3), then there were observations you could apply to bring it down to O(n).
If you asked me what exactly the correspondence was between the final reduction and the original problem statement, I couldn't tell you. Maybe there was a more direct way to get to the solution.
But that style of thinking carries on with me to real tasks too. Sometimes it's easier to simplify, other times it might actually be easier to complexify, as long as you trust that you're not going down "arbitrary" complexity.
Long, long ago I came up with a text search algorithm while working on PCxRef to help technical sales support at IBM. My first approach using a naive string search took about 30 seconds on a PC. My algorithm got it down to the speed of disk access.
Basically I precomputed a table of masks and used the XLAT instruction in a very tight loop to fly though all the product descriptions for everything IBM offered back around 1983. I could accommodate case insensitivity and single character wildcards.
The test search was always "dos tech ref" to find the IBM DOS Technical reference manual.
I'd say nothing has beaten the association rules + graph search I did for my thesis about restocking an automated picking machine in a warehouse (https://github.com/aleda145/product_allocation_aframe)
code: https://github.com/aleda145/product_allocation_aframe/blob/m...
I'm not proud of this code, but it yielded 0.2% better result than the naive approach!
Javascript logic for a clickable three.js 3d menu / world environment with animated planets going on their own trajectories.
An auto-arrange feature for a LabVIEW/ComfyUI type DAG programming language. Could take a program with hundreds of nodes and edges and arrange them nicely so none of the lines intersected and blocks were grouped logically.
diff in a text editor
The collapse sort "algorithm".
Nothing says efficiency like a sorting algorithm where Big O is more influenced by the largest element's value rather than the number of elements in the array. /s