Lab 13: Instructor's Notes

This exercise uses a platform-independent Timer class to time various operations on a vector, and compare them with the times to perform the same operations on a list. In this way, students will directly experience the time difference of the same operation on the two containers. The exercise introduces pointers, analysis of algorithms, and computational complexity.

To get measureable times, the exercise runs the operations on problems of size n, with n ranging from 5000 to 50000 in increments of 5000. These values were selected as reasonable ones on our machine, but the optimal values will vary with your CPU and memory. (e.g., An experiment will likely "crash" if you exhaust your machine's memory.) You should do each of the exercises ahead of time on your lab's machines in order to select an appropriate range of values for n, and inform your students of any changes.

The exercise consists of four experiments, conducted using four different programs:

1. appending n values to each container (append1.cpp);
2. appending 1 value to each container of size n; (append2.cpp);
3. prepending n values to each container; and (prepend1.cpp);
4. prepending 1 value to each container of size n. (prepend2.cpp);

Back to This Lab's Home Page

Forward to the Prelab Questions