[Tech] Algorithms Dissolved In Water

A masterclass on the Fibonacci sequence so you can know it once and for all.

This newsletter is best read with the soundtrack OceanView by Amalou. To listen, click here ▶️ Spotify, Apple Music or stream it from other apps.

Winners of last week’s reward from the comment section of “If Only Hakimi could read this poem”

• Aeesha (First commenter)

• Dapo Micheal.

• Taiwo Esther.

We will contact the above people this week for their preferred mode of receiving their $15 cash.

Table of Content:

• Introduction

• What is an Algorithm?

• Why are some people more expert than others?

• How do I know which Algorithm to use?

• The Fibonacci sequence problem.

• What Next? Is this end of the river? No.

• Basic Algorithms for solving Fibonacci sequence problems.

• Interactive session and questions.

Introduction:

Sometimes, the hardest part of creative writing is what to start with. AND there it is, done and dusted. This week’s newsletter is not totally poems, but as you would guess, you may find some poetic personalities inside the article, making it more enjoyable and easy-to-understand.

This article help shape understanding. This article is written in a simple and easy-to-understand manner so that even if you're not into tech, you'd say, hold my beer; I want to go into tech. You don't need to be on your laptop or type anything; it's a conversational class.

Starting…

What is an Algorithm?

That name Algo already puts most of us into a heart palpitation, gbim-gbim, but let's replace that name (Algo) in our mind with: How can we make it better and faster? Then, we can graduate to how can we make it more efficient? Efficiency means achieving the best with the least.

As you already know, there are different ways of doing things; Jollof rice, for example, can be cooked differently, but if you want a Nigerian party Jollof, there is a roadmap you must follow. That is not to say Basmati rice is not delicious, but basmati is not Nigerian Jollof.

So, any way of doing things is an algorithm. Anyway, at all.

HEY you, you’re 25% there, what is worth starting, is worth finishing.

Why are some people more expert than others?

Simple because they know how to achieve the best with the least, even though other experts can make it better and faster.

So, you can have a problem statement, and on Leetcode, you'd see different answers written as codes, then you'd get confused as, say, what is going on here? So, how can you see a problem and know the type of Algorithm to use?

Like the day I called an engineer to fix my gas pipes, the apprentice beside him had a bunch of spanners—inside a long grey roped bag wrapped around him. His boss will say, hand me 1.2, bring 2.4, hammer, please. Sometimes, because he has worked with a similar problem before, he knows the best is to use 1.2.

How do I know which Algorithm to use?

As you already know, there are many life problems in this world that we won't even experience. But we all have, at one time or another, shared/everyday experiences like grief, disappointment, pain, and pleasure, but not everyone has experienced a Solomon style with Palace ladies, who they call gift-givers.

Similarly, we have common problems in coding algorithms; they are common in both small and big companies. 

So, when you see a cat, even though all cats look different, all cats still look the same. Simply because something makes the problem statement a kind of problem.

Imagine both of us, outside at the backyard, there is a table tennis in our front 🏓, and we were standing about to solve a Fibonacci sequence problem.

Well done champ, you’re doing great, we are 50% there, keep going champ!

Fibonacci sequence problem using coins analogy

Coins aligned horizontally on a table tennis

Imagine like you have 10 coins in your pocket, each currency is written on a number, and you want to present it so that you and I can see it clearly. How would you present it?

You would place the coins on the table tennis, one coin beside the other, lined up straight.

Val coins = {0, 1, 2, 3, 4, 5, 6, 7, 8,9}

This presentation is called Linear.

Let's erase the board and imagine you have only two coins on the tennis table.

Val coins = {0, 1, 1, 2},

What is the Fibonacci number n at the 5th position on the linear scale (coins)?

I.E
Val coins = {0 (first position) , 1 (second), 1(third), 2(fourth), ???(Fifth)}

If you counted the coins that ended with 9 and guessed the answer as 2, 

you did well by trying, but that is incorrect.

A Fibonacci is the result of the two previous numbers added together.

Val bronzeCoins = {0, 1, 1, 2}, the Fibonacci at position 5 would be equal to 3 (1+2 is three).

[Correction] Val silverCoins = {0, 1, 1, 2, 3, 5} the Fibonacci at p7, is 8 (5+3)

Val goldCoins = {0, 1, 1, 2, 3, 5, 8}, the Fibonacci at p8 is 13 (5+8)

Hey CHAMP! What would you if you’ve gained so much at 75%? Are you a hundred percent go-getter? Don’t quit now, keep going Champ.

What Next? Is this end of the river? No.

It is possible to calculate the answer because it is a small dataset. Because a short position was asked.

But what if we asked for p75? Or position 873? At that stage, our heads will begin to boil.

This is where we ask a computer to solve it for us, and we program the process, i.e. the Algorithm, the steps it should take to return back for you the Fibonacci of any position born of man, woman or alien.

You may ignore the coding language in the examples below and focus on the written steps instead. There are many languages, but they all try to speak the same idea.

Algorithms for solving Fibonacci sequence problems.

At this stage, you already know two algorithms; you just did not realise there was a name for them.

• Basic Approaches

  • Recursive

  • Iterative

• Advanced Approaches

  • Memoisation

  • Matrix exponential.

Recursive

This is when you sum up the two previous Fibonacci numbers until the desired number is reached. However, this approach can be inefficient for significant inputs as it involves redundant calculations and can result in many function calls.

Val = {0, 1, 1, 2, 3, 5, 8, 13}, you've used the recursive approach when you sum up 8 and 5 to give you 13. Because to get the following number, 21, and would need to loop over again, just to sum of 13 and 8. (Keep reading…)

Code example

Where p, is the desired position.

fun fibonacciRecursive(p: Int): Int {
    if (p <= 1) {
        return p
    } else {
        return fibonacciRecursive(p - 1) + fibonacciRecursive(p - 2) //loop over again
    }
}

95%, do you have a celebration wine close to you?

Iterative

Say you have the coins { 0, 1, 1, 2, 3, 5, 8, 13 }; you only need to “loop once for each position up to the desired position” because you save the last two numbers, then pick them back to calculate the next.

It's very different from recursive. In recursive, once you've discovered that 5+8 is 13, you would start over again, from 0, 1, 1, 2…. To get the next Fibonacci. You would forget what you wrote and start again for the next Fibonacci. So, if your last position is to be 70, it would loop over again 70 times.

That is why we say the Recursive approach can be inefficient for significant inputs, as it involves redundant calculations and can result in many function calls.

But Iterative only loops once because it memorises the last two digits each time; like us, the way we might think it, we know that, 

3 plus 2 is 5. 

5 plus 3 is 8.

8 plus 5 is 13.

Where p, is the desired position,
And a and b are like {a, b, 1, 2, 3}


fun fibonacciIterative(p: Int): Int {
    if (p <= 1) {
        return p
    }
    var a = 0
    var b = 1
    for (i in 2..p) { //Loop once, last two, until position is reached
        val temp = a + b
        a = b
        b = temp
    }
    return b //Last Fibonacci at end of position that saved from temp.
}

Iterative saves the last two digits of its finds, so it keeps calculating it until the desired position on the linear scale is reached.

We are so proud of you. This is time valuably spent.

Algorithms Dissolved In Water

Other Advanced Approaches

• Memoisation.

• Matrix exponential.

…Coming up in another episodes of this newsletter.

Interactive Session And Questions

Question 1: Can you identify the primary difference between the recursive and iterative approaches? What is it?

Question 2: What is the Fibonacci number at Position 13.

Please write your answers in the comment section 💬, and I’ll be waiting for you there to respond. Tobi Akinpelu.