As I pointed out earlier, "constant time" applies only to look-up. [Though when working out against resistance, I have observed that stretching the arms does tend to slow down somewhat with repetition ...] Set-up has to take time at least order #edges, whether on SWASC or on boring old serial computer, because that's the number of data variables. WFL On 9/12/14, meekerdb <meekerdb@verizon.net> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun