Assigned: September 24, 2015. Due: October 9, 2015.
Go to Problem 3905.
Sign up in their system, solve the problem, show me that you
did it (e.g., screenshot).
It turns out that this is very difficult to do in the stated
time (and memory) limits if you are programming in Java.
So you can simply download the input file
here and run your program on that.
You will get extra credit if you demonstrate that you succeeded
on their system in Java. Of course, knowing the data file
makes it easier for everyone!
To turn in: your output and program listing.
Explain the 3984 in Table 4 on page 79. Also try to get the
37333248 for n=5. You can do
this by ad hoc methods, or by mathematics (e.g., Burnside's
Lemma), or by writing a program. Your choice.
What are the last 100 digits of the billion-th Fibonacci number?
Use binary powering and turn in your program.
HINTS: See
onlineCLRS:
See the "Powers of an element" section in the Number-Theoretic Algorithms chapter.
That matrix we looked at in class occurs in the exercises at the end of the chapter.
[0 marks]
Watch Knuth's movie about platologic (broadword) computation.
Nothing to turn in here. A warm-up for coming attractions.
the movie.