Advisor(s): Dr. Bruce Weide,
Dr. Tim Long, Dr.
Paolo Bucci
Participants: Jen Kannen,
Susan Hohenberger
Start Date: Fall Quarter 1997
Project Status: Completed (research ended May 1998)
Abstract
Calendar
Project
Development
Findings and
Contributions
Links and
References
Return
to EuropaThe Least_Cost_Path_Machine project was established to study the CPU timing differences of procrastination on a graph theory problem. We wanted to know if it would be more efficient to do all, some, or none of the computational work until the user specifically asked for a result. To do this, we implemented over six varying Least_Cost_Path_Machines and tracked their timing performances on categories of random data.
The development of Least_Cost_Path_Machine occurred over a span of seven months, allowing us to explore several avenues of the problem. Our six different implementations all sprung from two main algorithms.
Procrastination definitely improved timing performance on data in the 100 vertices, 100 edge range - even saving the user minutes! However, too much procrastination involved weighty overhead that reduced performance gains. We discovered that there existed a threshold amount of work that could be delayed until later computation in the Least Cost Path Machine problem.
Last modified: Sat Dec 4 15:29:14 EST 1999