Implementing progress indicators for recursive algorithms
Dave A. Berque, Mark Goldberg, Jeffrey A. Edmonds · 1993
A percent-done progress indicator is a software tool that allows a user to monitor the progress that a software system h= made toward responding to a command.Formal experiments have demonstrated that users prefer software systems that incorporate percent-done progress indicators over those that do not.Obviously, a system must be able to calculate (or at least estimate) the percentage of a computation that has been completed in order to support a percent-done progress indicator.This is generally straightforward for programs that make a fixed number of linear passes over their input and then terminate (e.g., file transfer programs).Most previous percent-done progress indicators have been limited to such programs.This paper presents a new technique called "dynamic bound evaluation" that allows percentdone progress indicators to be routinely incorporated into a wide range of programs that are driven by recursive algorithms that are not required to follow the "linear pass over data" paradigm.In addition, the paper discusses the application of this technique to the standard Quicksort algorithm as well as to an algorithm for computing the number of vertex covers in a graph. Int roduct ionMany software systems incorporate algorithms that execute almost instantly for some inputs while requiring a very long period of time to terminate for other inputs.This can be unsettling for users, particularly if a good estimate on the total computation time is not available.A percent-done progress indicator is a software tool that allows a user to monitor the progress that a software system has made toward responding to a command.This information can be displayed in a variety of textual or graphical formats depending on the particular interface style of the application.