Requirements Document

The algorithm efficiency program must be capable of measuring the running time associated with specific blocks of code at varying complexity levels.

The program needs to aid in analyzing algorithms to determine their efficiency as input levels increase. It should calculate and display the elapsed time a specified block of code takes to execute. It must also be capable of accepting an input quantity from the user at run-time and use this quantity to directly determine the number of times an algorithm will execute (i.e. instruct the program to "jump through a hoop" n times). Specific algorithms will be specified by the user prior to run-time and are subject to constant change. Additionally, this program will be subject to evolution and reuse in the future. Therefore, the program needs to be easily modifiable and reusable.

The mandatory program attributes are as follows: 1. It must accept and handle a valid input quantity from user. 2. The user must be capable of entering new algorithms into the program. 3. The program must display the elapsed run time for each algorithm.

Some optional attributes are: 1. Accepting multiple algorithms at a time. 2. Display the start and stop times. 3. Capability of clearing all values on the user interface.

Testing the validity of input is vital to the success of this program. Specifically, it needs to check the input quantity issued by the user and make certain that it's there and it's valid. A valid quantity is a whole number that is greater than 0.

Behavioral Specification

This program determines the elapsed time involved with various algorithms of changing input sizes. The following system is approximately 90% compliant with the user requirements.

This program will receive input via a Graphical User Interface and display the output on that same interface. The input will come in three forms: 1. An integer value that specifies the number of times an algorithm must perform. 2. Six algorithm buttons that test the timing of pre-specified algorithms. 3. One clear button that clears out the time and input values. It will output the start time, finish time, and elapsed time for each algorithm specified.

When the user presses one of the six algorithm buttons the system's timer will kick in and time the execution of the particular algorithm that corresponds to the button pressed. This timing mechanism will have start and stop capabilities. It will be activated directly prior to the algorithm under examination and deactivated upon completion of that algorithm. The output times will then be displayed. This system has a couple limitations: 1. It can't allow for the user to enter an algorithm directly through the front end GUI. 2. The time may not be the same on every machine due to varying processor speeds.

To verify that the system does in fact do what it is supposed to do, the following testing procedures should be executed: 1. Test several algorithms, increase their input quantity, and compare the behavior to that algorithms Big-O value. 2. Observe effects of dramatically increasing input sizes (within range) and confirm that the time behavior is expected for the given algorithm. 3. Test the system in the user's environment and note its effectiveness for the task at hand. (i.e. is it user friendly, are the results clear, is it modifiable, does it crash consistently, etc.).

Development requirements for this system are as follows: Staff: 1 Time: 20 hours Cost: $0/hr * 20 hrs = $0.00 Risk: Student (me) could flunk this assignment and therefore wasted much time.

Design

The algorithm timing system will correspond to the principles of Object-Oriented Programming and will contain a user friendly Graphical User Interface. The program will be platform independent and will be running on high-powered CPU's.

Future modifications and extensions call for a program that is extremely modifiable with objects that can be instantiated in future endeavors. The system's timing mechanism should be a separate object, the graphical user interface should be defined separately, and the event handling needs to be handled without adding much confusion to the program (needs to be separate). The system needs to be as modular as possible so that its individual functions can be easily accessed in the future.

Within the GUI class there needs to be methods for getting the input value from a text field (which allows input), running the algorithms associated with the buttons, displaying the results in the text fields (which should not allow input from the user), and clearing all of the values on the interface. These methods should be in this class because they need access to the interface directly. The timer object can also be instantiated within this class and its methods can then be easily accessed.

Within the timer class there needs to be methods for starting the timer, stopping the timer, and calculating the difference. Each of these methods should return a value to the calling method in the GUI class above so that the values can be displayed on the interface.

The event handler needs to handle action events (listens for buttons) and all of the buttons in the GUI need to be connected to this handler. The event handler can then find out which button is pressed and call the appropriate method to handle the event. The method will most likely be located in the GUI class because in most cases the program needs to grab the user input located in a text field on the GUI and then perform the appropriate function. Alternatively, the program could send the text field object to the timer class and the methods involving interface objects could be placed there.

Another important aspect of this system is the reliability of its performance in the presence of error. The system shouldn't crash and burn every time it receives invalid values. Rather the system should check the validity of the input as it comes in and prior to its use in the program. In the event that the input is invalid the program should simply notify the user and reset itself. On that note, the user needs to be somewhat restricted from entering outrageously large input quantities that lock up the system. In other words, it should not accept anything larger than a regular integer. Initially, this system will not be set up with the ability to easily stop an executing timer.

The GUI for this system needs to be understandable and friendly to the user. It should be very simple to inspect the start, finish, and elapsed times of six different algorithms. The user should be able to enter in a single input quantity and then rapidly review the times of each algorithm separately.

Conclusions

My timer shows that the total time it takes to fill and dynamically resize an array of initial size 10 with 5,120 random numbers is right around 10 millisecs. This doesn?t appear to be an extremely substantial amount of time, especially when compared with the other data structures in this project which attempt the same task.

I set up a method that will do the process described above on different array sizes and will do it a various number of times. Therefore, this method accepts a user-specified array size and a user-specified ?run-number? (number of times to build the array) and then calculates the average time it takes to build this specific array. To find the rate-determining characteristics, I first left the array size as specified above (5120) and gradually increased the ?run-number?. This seemed to produce the same average regardless of the number of times it created the array, which makes sense because nothing is really changing. Next, I played with the array size and left the ?run-number? alone. Now I was getting some variation. Clearly and obviously, the size of the array is what determines the length of time required to build it.

Filling up a default vector behaves very similar to resizing an array at first. However, once the number of elements increases past 10,000 or so, the vector?s efficiency level drops significantly. The time appears to be growing semi-exponentially and the space it takes up in memory behaves similarly. In fact, my computer can?t fill a vector of size 1,000,000 (which is quite big) and yet the array had no trouble with it. Therefore, the default vector is much less efficient than the array when the size is substantial.

This is, of course, even less efficient than the default vector because it initializes with the same size but doesn?t double the size every time it reaches capacity, it only increases capacity by 20. The inefficiencies with this vector are apparent right from the get go (5120) and increase rapidly. As a matter of fact, I grew extremely impatient waiting for it to calculate the time for size 100,000 and finally ended the task before it completed. Therefore, when deciding whether or not to include an increment capacity, the programmer needs to consider the size the vector can potentially grow to. If it?s considerably large, the programmer should definitely leave it to the default vector to double it every time.

Guess what? It?s even worse. This vector takes 1602 millisecs just to add the first 5120 elements. Compared with the 10 millisecs it took the array (3 on average) it?s not hard to see which one is more efficient. The same considerations specified above are relevant here. In this case, if the programmer is looking for a structure to store over around 500 elements, he/she should not implement the vector in this fashion.

The linked list seems to take longer than A, C, and D above but shorter than E for just about every ?N? I tried. This is because every time a singly-linked list wants to add a new element it has to traverse through the entire list (which takes O(N)) and then plant it at the end. Vectors and arrays, on the other hand, have direct access to elements within their structures and can, therefore, add an element to the end much more efficiently. That is, of course, with the exception of E above. E is so much slower because it only expands its capacity by one each time and is, therefore, constantly increasing its capacity which can be very time consuming.

Complete Date

May 2001