You can cut a string into N lengths in constant time, independent of N? :-) Brent On 9/12/2014 7:51 AM, Fred Lunnon wrote:
The SWASC (Sealing-Wax and String Computer) had a walk on and trip up part when I discussed finding shortest paths between towns on a road-map in my Algorithms course.
Set-up: (1) Cut the string into segments representing town-to-town distances; (2) Join the ends together with wax blobs representing towns.
Operation: (3) Grasp start and finish towns in left and right hand resp. (4) Pull.
Output: (5) The straight line of string gives the shortest route. Unless you pulled too hard. Or your arms were too short.
Performance: constant time: knocking Dijkstra's algorithm into a cocked hat. Along with itself when it overheats.
WFL