COM1201 Lab/Machine-Problem Assignment #1. Due Tuesday April 18, 2000

COM1201 Lab/Machine-Problem Assignment #1, updated 4/12/2000

Run-Time experiments to estimate algorithm complexity

Labs of Wednesday, April 12th, 2:50 or 4:05pm

DUE DATE: Tuesday April 18th

The six files: NOW AVAILABLE FOR DOWNLOADING BELOW

Getting Started

First, download all the files listed above in the Files section by simply clicking each link, and save them onto your Windows Desktop or some folder you've set up for them. Better than that, be at one of the labs Wednesday and Ms. Zheng has the executables on a floppy so you can copy them to your hard drive to use them and copy them to your own floppy if you'd like. The programs can be run by double clicking on the icons.

The Assignment

The assignment is to determine the time complexity (in "Big Oh" notation, e.g., O(N) ) of each of the six programs by running them with different values of input (N) and noting the time taken for the completion of the program. A table with the values of N and the corresponding time taken should be constructed for each of the programs and an estimate of the complexity of each of the program should be made from the tables. A sufficient number of runs at appropriate N values should be made so that the true time complexity of the programs is discovered.

How to do the computations

Assume that you run one of the executables for various N values, time them and record a table of values such as the following:

N value	Time in seconds
4	4
8	12
16	40
32	144
64	544

Say you decide to test these values to see if they're closer to O(N) or to O(N²). If they're O(N) then for large enough N they should obey Time = b*N where b is some constant (whose exact value is unimportant). Then the ratio of two times should obey Time1/Time2 = b*N1/b*N2 = N1/N2. For example we should have Time(N=32)/Time(N=16) = 32/16 = 2, whereas the actual ratio from the table you've collected is 144/40 = 3.6, which is a lot larger than 2.

So it appears as if the complexity is worse than O(N) so you try O(N²). In this case you should eventually see Time1/Time2 = b*N1²/b*N2² = N1²/N2². For the case we looked at before, comparing N=32 to N=16 gave us a ratio of 3.6 whereas 32²/16² = (32/16)² = 2² = 4. Now 3.6 is a lot closer to 4 than 2 is to 4. If you're patient enough to run the N=64 case and wait for about 9 minutes for it to complete, the ratio of the two times is 3.8 or so, even closer to 4.

In doing all these computations, you might want to add a few columns to your table and fill in some ratios. Also note that it is not necessary to compare the ratios of times for N values that are just a factor of 2 apart. In fact, for O(NlgN) behavior it is better to compare times for N values that are 4x or 8x or even 16x apart to see the difference between O(N) and O(NlgN) behavior. But of course don't use such small values of N that an interfering term could be deceiving you.

In conclusion, in this example we've found that as N gets large, the ratio of successive times for doubled N values is approaching 4, which would suggest O(N²) behavior.

Now I'll reveal the actual function that was used to create the values above. It is Time = (1/8)*(N² + 4*N). This function eventually is dominated by the N² term so it truly is O(N²). But for small values of N the linear 4*N factor contributes significantly. In fact, the ratio of the two contributions is N²/(4*N) = N/4, so for N=4 they contribute equally, whereas for N = 64, the second term is only 1/16 the first, or about 6% of the dominate term.

What to turn in

You should turn in a hardcopy of your tables of all the timing experiments and the inferences for each of the 6 programs.
At the top of the first page put your name, your ID number, your email address, the date, "COM1201 Spring 2000", and "Machine Problem 1". If you attach additional pages, put your name on each page, at a minimum. Only hardcopy will be accepted.
All homework should be handed in to Professor Futrelle by the beginning of class on Tuesday, May 2nd.
All late homework should be handed in to Ms. Zheng, Room 23CN, or in her mailbox in CCS headquarters, Room 161CN. Grade is reduced 10% x number of classes late it is handed in.
The percent credit for this lab towards your grade will be worked out in relation to the total number of assignments and labs that are ultimately assigned for this course.

I think you'll find this lab interesting and instructive and not that difficult or time-consuming to do.