Description

Introduction
In this programming assignment, the grader will show you the input data if your solution fails on any of the tests. This is done to help you to get used to the algorithmic problems in general and get some experience debugging your programs while knowing exactly on which tests they fail. However, for all the following programming assignments, the grader will show the input data only in case your solution fails on one of the first few tests.
Learning Outcomes
Upon completing this programming assignment you will be able to:
1. See the huge difference between a slow algorithm and a fast one.
2. Play with examples where knowing something interesting about a problem helps to design an algorithm that is much faster than a naive one.
3. Implement solutions that work much more faster than straightforward solutions for the following programming challenges:
(a) compute a small Fibonacci number;
(b) compute the last digit of a large Fibonacci number;
(c) compute a huge Fibonacci number modulo m;
(d) compute the last digit of a sum of Fibonacci numbers;
(e) compute the last digit of a partial sum of Fibonacci numbers;
(f) compute the greatest common divisor of two integers; (g) compute the least common multiple of two integers.
4. Implement the algorithms covered in the lectures, design new algorithms.
5. Practice implementing, testing, and debugging your solution. In particular, you will find out how in practice, when you implement an algorithm, you bump into unexpected questions and problems not covered by the general description of the algorithm. You will also check your understanding of the algorithm itself and most probably see that there are some aspects you did not think of before you had to actually implement it. You will overcome all those complexities, implement the algorithms, test them, debug, and submit to the system.
Passing Criteria: 4 out of 8
Passing this programming assignment requires passing at least 4 out of 8 programming challenges from this assignment. In turn, passing a programming challenge requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
Contents
1 Fibonacci Number 3
2 Last Digit of a Large Fibonacci Number 4
3 Greatest Common Divisor 6
4 Least Common Multiple 7
5 Fibonacci Number Again 8
6 Last Digit of the Sum of Fibonacci Numbers 9
7 Last Digit of the Sum of Fibonacci Numbers Again 10
8 Last Digit of the Sum of Squares of Fibonacci Numbers 11

1 Fibonacci Number
Problem Introduction
Recall the definition of Fibonacci sequence: F0 = 0, F1 = 1, and Fi = Fi−1 +Fi−2 for i ≥ 2. Your goal in this problem is to implement an efficient algorithm for computing Fibonacci numbers. The starter files for this problem contain an implementation of the following naive recursive algorithm for computing Fibonacci numbers in C++, Java, and Python3:
Fibonacci(n): if n ≤ 1:
return n return Fibonacci(n − 1) + Fibonacci(n − 2)
Try compiling and running a starter solution on your machine. You will see that computing, say, F40 already takes noticeable time.
Another way to appreciate the dramatic difference between an exponential time algorithm and a polynomial time algorithm is to use the following visualization by David
Galles: http://www.cs.usfca.edu/~galles/visualization/DPFib.html. Try computing F20 by a recursive algorithm by entering “20” and pressing the “Fibonacci Recursive” button. You will see an endless number of recursive calls. Now, press “Skip Forward” to stop the current algorithm and call the iterative algorithm by pressing “Fibonacci Table”. This will compute F20 very quickly. (Note that the visualization uses a slightly different definition of Fibonacci numbers: F0 = 1 instead of F0 = 0. This of course has almost no influence on the running time.)
Problem Description
Task. Given an integer n, find the nth Fibonacci number Fn.
Input Format. The input consists of a single integer n.
Constraints. 0 ≤ n ≤ 45.
Output Format. Output Fn.
Sample 1.
Input:
10
Output:
55
F10 = 55.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
2 Last Digit of a Large Fibonacci Number
Problem Introduction
Your goal in this problem is to find the last digit of n-th Fibonacci number. Recall that Fibonacci numbers grow exponentially fast. For example,
F200 = 280571172992510140037611932413038677189525.
Therefore, a solution like
F[0] ← 0 F[1] ← 1 for i from 2 to n:
F[i] ← F[i − 1] + F[i − 2] print(F[n] mod10)
Fi−1 and Fi−2:
F[i] ← (F[i − 1] + F[i − 2]) mod10
This way, all F[i]’s are just digits, so they fit perfectly into any standard integer type, and computing a sum of F[i − 1] and F[i − 2] is performed very quickly.
Problem Description
Task. Given an integer n, find the last digit of the nth Fibonacci number Fn (that is, Fn mod 10).
Input Format. The input consists of a single integer n.
Constraints. 0 ≤ n ≤ 107.
Output Format. Output the last digit of Fn.
Sample 1.
Input:
3
Output:
2
F3 = 2.
Sample 2.
Input:
331
Output:
9
F331 = 668996615388005031531000081241745415306766517246774551964595292186469.
Sample 3.
Input:
327305
Output:
5
F327305 does not fit into one line of this pdf, but its last digit is equal to 5.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
3 Greatest Common Divisor
Problem Introduction
The greatest common divisor GCD(a,b) of two non-negative integers a and b (which are not both equal to 0) is the greatest integer d that divides both a and b. Your goal in this problem is to implement the Euclidean algorithm for computing the greatest common divisor.
Efficient algorithm for computing the greatest common divisor is an important basic primitive of commonly used cryptographic algorithms like RSA. GCD(1344,217)
=GCD(217,42)
=GCD(42,7)
=GCD(7,0)
=7
Problem Description
Task. Given two integers a and b, find their greatest common divisor.
Input Format. The two integers a,b are given in the same line separated by space.
Constraints. 1 ≤ a,b ≤ 2 · 109.
Output Format. Output GCD(a,b).
Sample 1.
Input:
1835
Output:
1
18 and 35 do not have common non-trivial divisors.
Sample 2.
Input:
288515381183019
Output:
17657
28851538 = 17657 · 1634, 1183019 = 17657 · 67.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
4 Least Common Multiple
Problem Introduction
The least common multiple of two positive integers a and b is the least positive integer m that is divisible by both a and b.
Problem Description
Task. Given two integers a and b, find their least common multiple.
Input Format. The two integers a and b are given in the same line separated by space.
Constraints. 1 ≤ a,b ≤ 2 · 109.
Output Format. Output the least common multiple of a and b.
Sample 1.
Input:
68
Output:
24
Among all the positive integers that are divisible by both 6 and 8 (e.g., 48, 480, 24), 24 is the smallest one.
Sample 2.
Input:
288515381183019
Output:
1933053046
1933053046 is the smallest positive integer divisible by both 28851538 and 1183019.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
5 Fibonacci Number Again
Problem Introduction
To get an idea how to solve this problem without going through all Fi for i from 0 to n, let’s see what happens when m is small — say, m = 2 or m = 3.

Take a detailed look at this table. Do you see? Both these sequences are periodic! For m = 2, the period is 011 and has length 3, while for m = 3 the period is 01120221 and has length 8. Therefore, to compute, say, F2015 mod 3 we just need to find the remainder of 2015 when divided by 8. Since 2015 = 251 · 8 + 7, we conclude that F2015 mod 3 = F7 mod 3 = 1.
This is true in general: for any integer m ≥ 2, the sequence Fn mod m is periodic. The period always starts with 01 and is known as Pisano period.
Problem Description
Task. Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m).
Input Format. The input consists of two integers n and m given on the same line (separated by a space).
Constraints. 1 ≤ n ≤ 1018, 2 ≤ m ≤ 103.
Output Format. Output Fn mod m.
Sample 1.
Input:
2391000
Output:
161
F239 mod 1000 = 39679027332006820581608740953902289877834488152161 (mod 1000) = 161.
Sample 2.
Input:
2816213588239
Output:
151
F2816213588 does not fit into one page of this file, but F2816213588 mod 239 = 151.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
6 Last Digit of the Sum of Fibonacci Numbers
Problem Introduction
The goal in this problem is to find the last digit of a sum of the first n Fibonacci numbers.
Problem Description
Task. Given an integer n, find the last digit of the sum F0 + F1 + ··· + Fn.
Input Format. The input consists of a single integer n.
Constraints. 0 ≤ n ≤ 1018.
Output Format. Output the last digit of F0 + F1 + ··· + Fn.
Sample 1.
Input:
3
Output:
4
F0 + F1 + F2 + F3 = 0 + 1 + 1 + 2 = 4.
Sample 2.
Input:
100
Output:
5
The sum is equal to 927372692193078999175, the last digit is 5.
What To Do
Instead of computing this sum in a loop, try to come up with a formula for F0 + F1 + F2 + ··· + Fn. For this, play with small values of n. Then, use a solution for the previous problem.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
7 Last Digit of the Sum of Fibonacci Numbers Again
Problem Introduction
Now, we would like to find the last digit of a partial sum of Fibonacci numbers: Fm + Fm+1 + ··· + Fn.
Problem Description
Task. Given two non-negative integers m and n, where m ≤ n, find the last digit of the sum Fm + Fm+1 + ··· + Fn.
Input Format. The input consists of two non-negative integers m and n separated by a space.
Constraints. 0 ≤ m ≤ n ≤ 1018.
Output Format. Output the last digit of Fm + Fm+1 + ··· + Fn.
Sample 1.
Input:
37
Output:
1
F3 + F4 + F5 + F6 + F7 = 2 + 3 + 5 + 8 + 13 = 31.
Sample 2.
Input:
1010
Output:
5
F10 = 55.
Sample 3.
Input:
10200
Output:
2
F10 + F11 + ··· + F200 = 734544867157818093234908902110449296423262
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
8 Last Digit of the Sum of Squares of Fibonacci Numbers
Problem Description
Task. Compute the last digit of .
Input Format. Integer n.
Constraints. 0 ≤ n ≤ 1018.
Output Format. The last digit of .
Sample 1.
Input:
7
Output:
3
.
Sample 2.
Input:
73
Output:
1
.
Sample 3.
Input:
1234567890
Output:
0
What To Do

Need Help?
Ask a question or see the questions asked by other learners at this forum thread.