Description
Homework 1
Your first assignment includes a programming portion and a written portion. The programming portion must compile and should consist of a single file called hw01.cpp, and the written portion should consist of a single file called hw01written saved in a .pdf format. Be sure to include your name at the beginning of each file! You must hand in both files 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 file called MaxSubsequenceSum and Timer Class. You will run all three algorithms with the following values of n: 27 = 128,28 = 256,29 = 512,2 0 = 1024,211 = 2048, and 21 = 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 );
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 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 times 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 2b through 2e determine the running time for the following values of n : 28 = 256,29 = 512,210 = 1024,211 = 2048, and 212 = 4096.
Written Part:
1. Write each of the following functions in Big-Oh notation:
(a) T(n) = 12n − 204
(c) T(n) = 2n3 + 2n + 2n · log(n)
(d) T(n) = 10 · n2 + 0.002n + 82
(e) T(n) = (2n2 + 4 · logn) · 10n
(This means n choose 2)
(This means n choose 3)
2. For each of the following code fragments , determine the worst case running time using BigOh notation as a function of n.
(a) // a, b, c, d, e are integers a = b + c; d = b + e;
(b) int sum = 0; for (int i = 0; i < n; i++)
++sum;
(c) int sum = 0; for(int i = 0; i < n; i++) for(int j = 0; j < n; ++j)
++sum;
(d) int sum = 0; for(int i = 0; i < n; i++)
for(int j = 0; j < i; ++j)
++sum;
(e) 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;
(f) 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;
(g) int sum = 0; for (int i = 0; i < n; i++)
{
sum += i; for (int j = 0; j < n; j++)
sum += j;
}
(h) 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;
}
}
(i) int sum = 0; for (int i = 1; i < n; i*=2)
{
sum += i;
}
(j) int sum = 0; for (int i = 1; i < n; i*=2)
{
sum += i; for (int j = 0; j 0)
{ cout<< n%2; sum += n%2; n/=2;
}
3. For the following functions, order them by their rates of growth from fastest to slowest:
n,√n,n1.5,n2,nlogn,nlog2 n,n/2,n3. Indicate which functions grow at the same rate.
4. 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.
5. Suppose you had a very complicated code that was difficult to analyze. To get a quick ideaof 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 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
6. Using the definition of Big-Oh, show that 3n2 + 2nlog(n) + 6n + 19 = O(n2).
7. Look at the output from the programming part 1 of this assignment. Create a chart of youranswers 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
.
. .
8. Create another chart that estimates the running time for each of the algorithms using themethod 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:
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 | …
9. 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.
10. 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.)
11. Look at the output 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.
12. Circle True or False. I understand that if I don’t submit a .pdf file for the written portion of this assignment, I will receive no credit for the written part of this assignment.
13. Circle True or False. I understand that if I don’t submit code that compiles for the programming portion of this assignment, I will receive no credit for the programming part of this assignment.
