Least_Cost_Path_Machine

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)

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

The 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.

Calendar:

• November 1997: Accepted project and began research
• Dec 1997-May 1998: Implemented six varying Least_Cost_Path_Machines and recorded timing differences
• May 1998: Presented "Efficiency Studies on Varying Implementations of a Least_Cost_Path_Machine" at the Ohio State Undergraduate Research Forum.

Project Development:

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.

Findings and Contributions:

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.

  Return to Europa

Last modified: Sat Dec 4 15:29:14 EST 1999