Description
Programming Part:
1. You will compare the time it takes to solve the Max Contiguous Subsequence sum problem,
using the three algorithms provided in the file called MaxSubsequenceSum and Timer Class.
You will run all three algorithms with the following values of n: 27 = 128, 2
8 = 256, 2
9 =
512, 2
10 = 1024, 2
11 = 2048, and 212 = 4096.
What you will need to do:
(a) Look at the code for the timer class in the file MaxSubsequenceSum and Timer Class,
and then apply it in your own code.1
(b) Fill a vector with n random integers in the range from -1000 to 1000. There is a function2
from the standard library called rand() that returns a value from 0 to RAND_MAX;
(RAND_MAX is at least 32767.) The code x = (rand() % 2001) – 1000 puts a random
number in the range [-1000, 1000] into the variable x.
(c) Time how long it takes the function maxSubSum1 to find the maximum subsequence sum.
The code might look like the following
timer t;
double nuClicks;
// other code to fill in the vector with n items, etc.
t.reset();
maxSubsequenceSum1( items );
∗Late submissions accepted until 5:00 p.m. Wed. Feb 3, 2016 for 10% penalty.
1Some compilers require #include or #include to be included in your code for this class to
work.
2The function rand() is not cryptographically strong, and our use of the mod function will not create a uniform
distribution in the range -1000 to 1000. You do not need to ”seed” the random number generator for this assignment.
C++11 has introduced a library for producing “good” random numbers, but using it is more complicated and the
better quality random numbers provided by the library is not needed for this assignment.
1
nuClicks = t.elapsed();
(d) Time how long it takes the function maxSubSum2 to find the maximum subsequence sum,
using the same n elements.
(e) Time how long it takes the function maxSubSum4 to find the maximum subsequence
sum, again using the same n elements. (Yes, this is function number 4; I am using the
textbook’s name for the functions.)
Note: Here are three suggestions to help you:
First, after debugging your code, turn off your debugger. Do not run any other program
while solving this problem. Your program should take no more than 20 min. (My code
took much less.)
Second, make sure when you print the running times you are printing enough significant
digits. Here are two choices for how to do this:
cout.setf( ios::fixed, ios::floatfield );
cout.precision( 6 );
or
cout.precision(numeric_limits::digits10 + 1);
Third, we are using the clock function (you need to add the header ctime or time.h)
that allows us to get an estimate of the CPU time spent on the program. The problem is,
different systems keep track of the time differently. My computer’s clock function returns
returns a value in units of (approx) 1, 000, 000 of a second. Other computers have a clock
that returns a value of (approx) 1000 of a second. Therefore, some short time intervals
are distinguishable from zero on my computer, but not on other computers.
To determine the resolution used on your computer type:
cout << CLOCKS_PER_SEC << endl;
For the written homework problem 6, if you get a running time of 0 when you run the
linear time algorithm, then run that particular function with the same input multiple
times3 and then divide by the number of times you ran the program.
Be aware that the measurements you are getting are ”rough” because other factors will
influence the time. If you wanted a more accurate time estimate you would run each
algorithm on for a fixed value of n several times and average the results.
2. For the code snippets 2a through 2d determine the running time for the following values of
n : 28 = 256, 2
9 = 512, 2
10 = 1024, 2
11 = 2048, and 212 = 4096.
3E.g. clock how long it takes to run the algorithm 10,000 times and then divide by 10,000 to get an estimate that
is sufficient for this assignment.
2
Written Part:
1. Write each of the following functions in Big-Oh notation:
(a) T(n) = 12n − 204
(b) T(n) = 3
2
n
2 +
5
2
n + 0.24
(c) T(n) = 2n
3 + 2n + 2n · log(n)
(d) T(n) = 10 · n
2 + 0.002n + 82
(e) T(n) = (2n
2 + 4 · log n) · 10n
(f) T(n) = 34 log(n
5
) + 2
3
n
(g) T(n) = 4n·log(n)(3n·log(n)+2n
2
)
n
(h) T(n) = n
2
(This means n choose 2)
(i) T(n) = n
3
(This means n choose 3)
2. For each of the following code fragments4
, determine the worst case running time using BigOh notation as a function of n.
(a) int sum = 0;
for (int i = 0; i < n; i++)
++sum;
(b) int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; ++j)
++sum;
(c) int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < i; ++j)
++sum;
4Some of these problems are from Weiss’ book.
(d) int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; ++j)
for(int k = 0; k < n; ++k)
++sum;
(e) int sum = 0;
for (int i = 0; i < n; i++)
sum += i;
for (int j = 0; j < n; j++)
sum += j;
for (int k = 0; k < n; k++)
sum += k;
(f) int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
for (int j = 0; j < n; j++)
sum += j;
}
(g) int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
for (int j = 0; j < n; j++)
{
sum += j;
for (int k = 0; k < n; k++)
sum += k;
}
}
(h) int sum = 0;
for (int i = 1; i < n; i*=2)
{
sum += i;
}
4
(i) int sum = 0;
for (int i = 1; i < n; i*=2)
{
sum += i;
for (int j = 0; j < n; j++) { sum += j; } } (j) int sum = 0; while (n>0)
{
cout<< n%2;
sum += n%2;
n/=2;
}
3. Suppose a program takes 0.05 seconds to run on input size of 2048. Estimate how long it
would run for an input size of 213 if:
(a) the program had an O(n) running time.
(b) the program had an O(n
2
) running time.
(c) the program had an O(n
4
) running time.
4. Suppose you had a very complicated code that was difficult to analyze. To get a quick idea
of your algorithm’s running time you ran your program on different sized inputs. Suppose
the following are the timing results for your algorithm. Using the timing results below,
indicate the most likely running time in big-Oh notation; choose one from the following list.
O(1), O(n), O(n
2
), O(n
3
), O(n
4
).
n time
2^7 0.002094
2^8 0.00834
2^9 0.033412
2^10 0.133054
2^11 0.532501
2^12 2.12835
5
5. Using the definition of Big-Oh, show that 3n
2 + 2n log(n) + 6n + 19 = O(n
2
).
6. Look at the output from the programming part 1 of this assignment. Create a chart of your
answers including times for all three algorithms and for all the specified input sizes, e.g.
Actual Times:
n | maxSubsequenceSum1 O(n^3) | maxSubsequenceSum2 O(n^2) | maxSubsequenceSum4 O(n)
—- | ————————- | ————————- | ————————-
128 | 0.00228 | 6.2e-05 | 3e-06
256 | 0.01676 | 0.000237 | 2e-06
.
.
.
7. Create another chart that estimates the running time for each of the algorithms using the
method presented in class, and using the time your computer took for the algorithms when
n = 27
. (If you did not receive valid answers, use the run times from question 6.) Display
your answer in a chart, e.g.
Predicted Times:
n | Exp. maxSubseq. 1 O(n^3) | Exp. maxSubseq. 2 O(n^2) | Exp. maxSubseq. 4 O(n)
— | ————————- | ————————- | ————————-
256 | 0.01824 | 0.000248 | 6e-06
512 | 0.14592 | 0.000992 | 1.2e-05
1024 | …
2048 |
4096 |
8. Using the method given in class, predict how long each algorithm would take if n = 218
.
Show how you made your prediction by providing the formula (presented in class), and then
evaluate your formula.
9. Using your answer from the previous question, rewrite your answer cumulatively in seconds,
minutes, hours, days, and weeks. (To clarify: you are not going to re-express that time in
terms of weeks and then again in terms of days and then again in terms of hours. You should
only express it once, using weeks, days, hours, minutes, and seconds.)
6
10. Look at the output5
from the programming part 2 of this assignment. Create a chart of your
answers including times for all four algorithms and for all the specified input sizes, e.g.
Actual Times:
n | a | b | c | d
—- | ————- | ————- |————- |————-
256 | 0.000002 | 0.000169 | 0.000072 | 0.046341
.
.
.
Look at your output and see if it matches your predictions.
5Note: the table should be filled with values from running the code, not prediction values
7
