Homework 2 Clarifications
Added 10-13-2011:
Problem 4: I have had a few people asking questions about whether
they are seeing what they should be seeing in their timing. Here are
a few pointers:
- Be sure that you have your code correct: In between the two calls
to System.nanoTime() you should only have the code that is one of the
loop bodies shown below. Double check that you copied the code from
the book correctly, that you have an n when you should and an i when
you should - these make a big difference in the running time.
- Run each loop several times: For each value of n that you try,
for each of the 5 pieces of code you are trying, run it 3-4 times or
more. One thing you can do is to throw out the smallest and the
largest time you get and take an average of the remaining ones.
- Values for n: Be sure that you run each piece of code for at
least 4 different values of n. You do not have to use the exact same
values of n for each of the 5 pieces of code. For some pieces of code
you may not want to wait for it to finish for any value of n > 1000
(which is not actually a very large value of n). For other pieces of
code you will want to run for larger values in order to see the trend
for large n.
- Should my timing values map exactly (or even approximately?)
to a curve of some function of N? Shouldn't this be identical to what
I predicted the big-O running time to be? What if it isn't? Don't
worry if the timings you get don't match exaclty what you
think they should be based on your big-O analysis. Hopefully you will
see that if you had based your choice of algorithm on big-O you still
would have made the right choice in terms of observed running times
(e.g. that one piece of code runs slower than another for large values
of N as big-O would have predicted). NOT nescessarily that the
observed running times of one piece of code exactly match a curve of
the big-O function you think represents that code. Look for relative
trends.
- I did everything you mention above but I still get crazy
values I don't understand. To some extent your answers will depend
on your machine. You may have multiple cores or only one. You may
have some other process running on your machine that is causing your
code to run more slowly (I would try to close other active programs
while timing.). In the end just be sure you have followed all the
instructions in the assignment, reported timing for at least 4 values
of n for each piece of code and have said *something* about what you
saw in your results even if they did not make complete sense to you.
- Problem #2 (Weiss 2.1) For this question in general, the main
thing you need to do is to be able to compare two functions to see
which one grows faster. A couple of techniques that are useful in this
respect are things like taking the log of both sides, or treating both
sides as exponents when the base is something that leads to further
simplification. We are talking about "growth rate", thus another way
of thinking about these is saying find their running time in terms of
big O, and then order them by that.
- Problem #4 (Weiss 2.7) The idea of part c is that we talked about
how big-O was useful for comparing the run time of two algorithms. And
we said that in fact we could do a big-O analysis and then use THAT to
decide which algorithm to use. (as opposed to implementing the
algorithms and then running them and timing them and seeing which was
faster). Well in this case we are asking you to do both! So you can
actually see what the running time is if you DO implement and time
them.