Introduction to Algorithmic Warm Up

Chapter goal

This chapter aims to demonstrate how a good understanding of an issue can make an algorithm for it a billion times faster! We will consider a number of programming challenges that share the following property: For each challenge, it is easy to come up with a naive algorithm consisting of a single loop. This solution, however, will be catastrophically slow. Together, we will design algorithms for these programming challenges that will be as simple as the naive solutions but much more efficient.

We will look at the following programming challenges in this chapter.

---

Fibonacci number

Compute the $n$-th Fibonacci number.

Input: An integer $n$.

Output: The $n$-th Fibonacci number.

---

Last digit of the Fibonacci number

Compute the last digit of the $n$-th Fibonacci number.

Input: An integer $n$.

Output: The last digit of the $n$-th Fibonacci number.

---

Huge Fibonacci number

Compute the $n$-th Fibonacci number modulo $m$.

Input: Integers $n$ and $m$.

Output: The $n$-th Fibonacci number modulo $m$.

---

Last digit of the sum of Fibonacci numbers

Compute the last digit of $F_{0} + F_{1} + \cdot\cdot\cdot + F_{n}$ ...