Homework #1 Solution

$30.00

Description

Yourfirstassignmentincludesaprogrammingportion andawritten portion. Theprogramming portion must compileand should consistofasinglefilecalledhw01.cpp, and the writtenportion should consist ofasinglefilecalledhw01writtensaved ina.pdfformat. Besuretoinclude your nameatthebeginning ofeachfile!Youmusthand inboth filesviaNYUClasses.

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, 28 = 256, 29 =

512, 210 = 1024, 211 = 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 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.

(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.

1 Some compilers require #include <ctime> or #include <time.h> to be included in your code for this class to work.

2 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.

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<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, 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.

Todeterminetheresolution usedonyourcomputertype:

cout << CLOCKS_PER_SEC << endl;

Forthe writtenhomework problem 6,ifyougetarunning time of0whenyourun the linear time algorithm,then run thatparticularfunction 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, 29 = 512, 210 = 1024, 211 = 2048, and 212 = 4096.

3 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 sufficient for this assignment.

WrittenPart:

1. Write each of the following functions in Big-Oh notation: (a) T (n) = 12n 204

(b) T (n) = 3 n2 + 5 n + 0.24

2 2

3

2

(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 ) + 2 n

n

(g) T (n) = 4n·log(n)(3n·log(n)+2n )

2

3

(h) T (n) = n (This means n choose 2) (i) T (n) = n (This means n choose 3)

2. For each of the following code fragments4 , determine the worst case running time using Big- Oh 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;

4 Some of these problems are from Weiss’ book.

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;

}

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(n2 ) running time. (c) the program had an O(n4 ) 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(n2 ), O(n3 ), O(n4 ).

n

2^7

time

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 definition of Big-Oh, show that 3n2 + 2n log(n) + 6n + 19 = O(n2 ).

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.)

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

.

.

.

Lookatyouroutputandseeifitmatches yourpredictions.