Note: for references on Unix commands you can see the Unix manual pages. For example, for the make utility "make", you would type:
man make
We'll see that the run-time behavior of such programs is sometimes machine-dependent (depending on things such as the way memory is laid out, and how new works), and sometimes also depends on the surrounding code; making it important to use other means to verify their correctness, such as hand-tracing the code.
In the second exercise, you'll get a better idea of how big data sets are necessary to make an observable difference in execution speed of algorithms with different big-O properties.
Download the following files to a directory in your account:
Each of the programs str1.cc through str6.cc has a memory management error in it. For each one, you are going to do the following:
Step A. Without running it examine the code (possibly drawing diagrams to help) and determine the problem with the program. Write down the problem in your lab notebook. Do NOT fix the program.
Step B. Compile and run the program on aludra or one of the other SunOS5 (Solaris) machines, and observe its behavior. We've provided a Makefile: you can compile the first one by doing gmake str1, and the other ones similarly. Write down the program's exact behavior.
Step C. Redo step B, but on a machine with a different architecture or different compiler than you did for the last part and observe its behavior on that machine. You could use one of the SunOS4 machines for this (e.g., rlogin nunki), or you could use your PC and C++ compiler at home, if that is an environment you normally use. Note: the UNIX command echo $OS will tell you which kind of Sun you are using.
Step D. Write down your hypotheses for why you got the behavior you did for each machine, if it is different than the behavior you expected.
For checkoff show your written answers to each of the steps. You'll get 1 checkoff point for correctly doing steps A, B, & D, on any three out of the six programs, 1 checkoff point for the other three, and 1 checkoff point for doing step C on all six (i.e., running on another machine).
Consider comparing an O(n) algorithm with an O(1) algorithm using the example of push on an array-based stack where in one version the stack representation uses the first element in the array as the top, and in the other version the "end" of the array is the top. In insert.cc we've implemented both push algorithms: one is called insertFront, and the other insertEnd so you can see how the big-O behavior translates into actual execution times.
The program in insert.cc makes repeated calls to each of these functions, and then times them to compare the two algorithms. When you run the program it asks you for an array size n, and then starting with an empty array it repeatedly calls one of the routines to insert n elements in the array, and then, starting with an empty array again, it uses the other routine to insert n elements into the array, and then gives the times it took to do each set of inserts (in seconds). We have to do many inserts, otherwise the time would be too small to detect differences between the two algorithms.
Do gmake insert to compile this program, and run it on different array sizes, to answer the following questions. Note: if it says it took 0 seconds, that means it took less than 1 second.
Question A. What's the smallest array size for which it takes longer in seconds to do the front inserts than the end inserts?
Question B. What's the smallest value for which the it takes at least 10 times longer to do the front inserts than the end inserts?
The following questions involve big-O analysis (not running the program):
Question C. What is the big-O worst-case time of testInsertEnd as a function of n, the size of the final array? Hint: you need to figure out the time for each call to insertEnd, and then add up all these times.
Question D. What is the big-O worst-case time of testInsertFront as a function of n, the size of the final array? (NOTE: includes times for all calls to insertFront) Hint: (1) the first call to insertFront inserts in an array of size 0, and the second one inserts in an array of size 1, etc. (2) the sum of the numbers 1 through n is n(n+1)/2.