$24
Homework 1 Solution
Your rst assignment includes a programming portion and a written portion. The programming portion must compile and should consist of a single le called hw01.cpp, and the written portion should consist of a single le called hw01written saved in a .pdf format. Be sure to include your name at the beginning of each le! You must hand in both les via NYU Classes.
Programming Part:
You will compare the time it takes to solve the Max Contiguous Subsequence sum problem, using the three algorithms provided in the le called MaxSubsequenceSum and Timer Class. You will run all three algorithms with the following values of n: 27 = 128; 28 = 256; 29 = 512; 210 = 1024; 211 = 2048; and 212 = 4096.
What you will need to do:
Look at the code for the timer class in the le MaxSubsequenceSum and Timer Class, and then apply it in your own code.1
Fill a vector with n random integers in the range from -1000 to 1000. There is a func-tion2 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.
Time how long it takes the function maxSubSum1 to nd 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 );
Early submissions 5:00 p.m. Fri. Sept 16, 2016 for 5% bonus.
1Some compilers require #include <ctime or #include <time.h to be included in your code for this class to work.
The 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();
Time how long it takes the function maxSubSum2 to nd the maximum subsequence sum, using the same n elements.
Time how long it takes the function maxSubSum4 to nd 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 o 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 signi cant digits. Here are two choices for how to do this:
cout.setf( ios::fixed, ios::floatfield );
cout.precision( 6 );
or
cout.precision(numeric_limits<double::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, di erent systems keep track of the time di erently. 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 7, 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 in uence the time. If you wanted a more accurate time estimate you would run each algorithm on for a xed value of n several times and average the results.
For the code snippets 2b through 2e determine the running time for the following values of n : 28 = 256; 29 = 512; 210 = 1024; 211 = 2048, and 212 = 4096.
E.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 su cient 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) = 32 n2 + 52 n + 0:24
(c) T (n) = 2n3 + 2n + 2n log(n)
(d) T (n) = 10 n2 + 0:002n + 82
(e) T (n) = (2n2 + 4 log n) 10n
(f) T (n) = 34 log(n5) + 23 n
(g) T (n) = 4n log(n)(3n log(n)+2n2)
n
T (n) = n2 (This means n choose 2)
T (n) = n3 (This means n choose 3)
For each of the following code fragments4, determine the worst case running time using Big-Oh notation as a function of n.
// a, b, c, d, e are integers a = b + c;
d = b + e;
int sum = 0;
for (int i = 0; i < n; i++) ++sum;
int sum = 0;
for(int i = 0; i < n; i++) for(int j = 0; j < n; ++j)
++sum;
4Some of these problems are from Weiss’ book.
3
int sum = 0;
for(int i = 0; i < n; i++) for(int j = 0; j < i; ++j)
++sum;
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;
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;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
for (int j = 0; j < n; j++) sum += j;
}
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;
}
}
int sum = 0;
for (int i = 1; i < n; i*=2)
{
sum += i;
}
4
int sum = 0;
for (int i = 1; i < n; i*=2)
{
sum += i;
for (int j = 0; j < n; j++)
{
sum += j;
}
}
int sum = 0; while (n0)
{
cout<< n%2; sum += n%2; n/=2;
}
For the following functions, order them by their rates of growth from fastest to slowest: n; pn; n1:5; n2; n log n; n log2 n; n=2; n3. Indicate which functions grow at the same rate.
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:
the program had an O(n) running time.
the program had an O(n2) running time.
the program had an O(n4) running time.
Suppose you had a very complicated code that was di cult to analyze. To get a quick idea of your algorithm’s running time you ran your program on di erent 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(n2); O(n3); O(n4).
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
Using the de nition of Big-Oh, show that 3n2 + 2n log(n) + 6n + 19 = O(n2).
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 speci ed 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
.
.
.
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 7.) Display your answer in a chart, e.g.
Predicted Times:
| 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
|
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.
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
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 speci ed 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.
Circle True or False. I understand that if I don’t submit a .pdf le for the written portion of this assignment, I will receive no credit for the written part of this assignment.
Circle True or False. I understand that if I don’t submit code that compiles for the pro-gramming portion of this assignment, I will receive no credit for the programming part of this assignment.
Note: the table should be lled with values from running the code, not prediction values
7
