Don't like this style? Click here to change it! blue.css
Register at this link for the 14 GORE 208 presentation slots (11-12:15)
Register at this link for the 12 Willard 116 presentation slots (2:10-3:15)
Restraints: for testing your project I will feed you two files, int1 and int2
which have large numbers stored in them (10000 digits at least). Your program should take the two numbers in and output files
named sum, prod, and quo with the sum, product, and quotient respectively.
Before you present: share your cloud9 workspace with AndyNovo so that I can execute your code
(you can do this now to be sure).
In the last lecture we built a "dynamic" array which doubles its size every time it runs out of space. At that point it copies all of its data from the old location to the new location. Based on that setup answer the following.
Something like this:
Task 1: If you were to append one character at a time to your string until you had 1000 characters. How many times would you copy a single character in memory? How big is your character array?
Task 2: How about with 2000 characters?
Task 3: How about with 4000 characters?
This is a common practice with "dynamic" arrays, which have the property that they should allow as much space as you need but are contiguous in memory. Let's see if we can ballpark the number of "copy" operations it takes to fill an array of \(n\) things.
If we start with 1 item in our array, the next time we double we'll move 2 things, then 4, then 8 etc. So if eventually \(n\) is \(2^k\) then we moved $$ 1 + 2 + \cdots + 2^{k-1} = 2^k - 1 = n - 1 $$ things.
I've built an example project for you at http://github.com/cisc220/complexity-examples. It has four "algorithms" which don't accomplish much but do demonstrate different running costs.
Setup Task 4: Create a cloud9 workspace from the above repo. Change the
contents of the file input to be the number 30000.
Quadratic Task 5: How often is line 9 called in quadratic.cpp if
the input is 30000? What about if it is 60000?
Time Task 6: Compile quadratic.cpp and time it using the command
time ./a.out < input (be sure that input is 30000). Now change the contents of input to
60000 and time it again (no need to recompile). How long would you estimate that 1 loop of line
9 takes?
Estimate Task 7: Use your new insights to predict what value for input would lead to a running time of 30 seconds. Test it. How large of a problem can this code tackle in 1 day? (Don't test.)
A general observation: if you double the size of your input and the cost quadruples then you have a quadratic algorithm.
Estimate Task 7.5: How many times does line 8 get called when input is 10000? 20000?
Time Task 8: Compile linear.cpp, run time ./a.out <
input. Change the value of input until it really takes about 1-2 seconds. How big is
your input?
Time Task 9: double the size of your input and run time ./a.out <
input again.
Estimate Task 10: What size input would you guess gives you a run time of 3 seconds? Try it. How about the largest problem you think it can tackle in 1 day? (Don't try it.)
Push It Task 11: Try the same set of tasks but for sqrt.cpp. How
big of a problem can you tackle in one day?
Logarithmic Task 12: So how is this function so fast? What happens when you double the size of your input? How big of a problem can you do in one day?
For this chunk I want to have you explore the families of running times and get a feel for how different they are. Let's move over to a different set of slides from my old CISC320 class:
http://cs.prof.ninja/slides/class3/#3
If you are following along at home, I find that it helps to look at the scale of the universe when contemplating the sheer size of this numbers.
I don't expect to have too much time in class for this, but I want you to have some nice pointers.
As you work on your projects for class I expect you are facing a ton of error messages. I want to give you some guidance on how to find those bugs quickly.
Get to know the basic errors of omission which include missing }, ;, ClassName::,
and type declarations. Learn to recognize what sorts of error messages you see in each of these cases.
Another very nefarious bug is a single equals when you meant a double equals. = vs
== in an if statement. It passes right under your human radar so you have to learn to hunt this
one.
Debug Task: Create some code that works, has an if statement, and a
for loop. Then take away a semi-colon from
several different lines. Observe the messages. Try again but removing a }. Now remove a type
declaration. Recognize the styles of these messages. Replace an == with = and note
the error or lack of error.
Comment everything out until it works. Then slowly add in features until it breaks.
Use lots of cout statements, but please use endl, you might end up thinking that
code doesn't run but it actually does.
Check out these 15 Common C/C++ errors
This is another aside for you guys, but please check out Valgrind, which is great at detecting memory leaks. If you do big C/C++ libraries you have to know valgrind well.
Valgrind Task: Make a cloud9 workspace from cisc220/valgrind-basics. Compile the program with
g++ -g leak.cpp then evaluate the program with valgrind using valgrind --leak-check=yes
./a.out.
There are many many ways to use this tool, and I encourage you to spend some time mastering it. I've found many a bug this way. But for now, just see if your bigInt project is leaking memory!