# CS2134 Homework 1 solution

\$24.99

Original Work ?

## Description

5/5 - (1 vote)

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:
1. 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:
(a) Look at the code for the timer class in the ﬁle 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 ﬁ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 );
∗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 ﬁnd the maximum subsequence sum, using the same n elements. (e) 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::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: