Imagine that you have never cooked a chocolate cake before and you want to. You need the instruction to bake a good cake, so you search for a recipe. Once you have found the most suitable recipe, based on the ingredient you have, you start following the procedures illustrated.

You have to combine the ingredient requested in order to bake the cake.

We can see an algorithm like a well-defined “to do” list of procedure, like a recipe.

 

In fact, an algorithm is a well-defined computational procedure that takes some value as input and produces some value as output.

 

We combine our ingredients (input) following the recipe (algorithm) to produce a good cake (output).

Data structure

In Computer Science we have to deal with data and we need a way to access them and at the same time modify them.

Data structures can help us!

 

The data structure is a way to store and organize data in order to facilitate the computation through the algorithm. 

 

We have to choose a structure based on the problem we are dealing with.

We will analyze the pros and cons of each data structure in the next articles.

Proprieties

What kind of proprieties adopts our algorithm?

Correctness

Our algorithm must be correct.

Imagine that you take the ingredients and you want to bake a chocolate cake, but in this case, you follow the wrong recipe and you pop out a Margherita cake. It’s always a cake but it’s not the cake that we want to eat. In order to pop out a chocolate cake, you have to follow the correct recipe.

Generalizing this propriety: an algorithm is correct if, for every input instance, it halts with the correct output.

Efficiency

A lot of algorithms can solve the same problem, but how can we choose the best? Fortunately, they differ dramatically in their efficiency. Every time we write an algorithm we have to consider how many resources does it use and how much time it takes to compute the correct output.

We have to consider time complexity and space complexity.

Time complexity quantifies the amount of time taken by an algorithm to run as a function of the length of the input.

Space complexity quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

Time and space complexity depends on a lot of things because we are going to execute our algorithm on a limited machine. We will only consider the execution time of an algorithm in order to compare them.

There are a few methods used to calculate the execution time.

We will talk about that in the next articles.

The conjecture of Collatz

A typical example of an algorithm to start is the famous Collatzt conjecture.

We will analyze it and write a C++ program to calculate the length of the sequence.

Let's start!

Basically, the conjecture consists in:

 

Start with any positive integer number N.

 

Each term is obtained from the previous term as follow:

If the previous term is even the next one is one half the previous term

N/2

If the previous term is uneven the next one is three times the previous term plus one.

3N+1

The algorithm ends when N is equal to 1.

For example, if N = 6 the next term is equal to 3 (6/2), then the next one is equal to 10 (3*3+1) and so on, obtaining this sequence that ends with 1:

6,3,10,5,16,8,4,2,1 

The conjecture is that no matter what value of n, the sequence will always reach 1. 

We want to calculate the length of the sequence of numbers.

Count is variable that counts the number of step of the sequence until it ends to 1.

The idea is to calculate the sequence step by step and increment count.

While N!=1 

Count++

If (N%2==0) --> N=N/2

Else --> N=3*N+1

The final step is to write the algorithm in a high-level language.

C++

 

#include <iostream>

using namespace std;

int main() {
    int N = 0, count = 1;
    cin >> N;
    
    while(N!=1){
        count++;
        if(N%2==0) {
            N=N/2;
            
        }
        else {
            N=3*N+1;
            
        }
    }
    
    cout<<count;
}

This example shows you how to relate algorithms to Computer-Science.

By the way there are a lot of applications in this field, for example algorithms are useful to:

  • Calculate the human genome
  • Connect people through the internet
  • Sell and buy things via web
  • Calculate the shortest or the cheapest route for a travel

...and much more!

 Curiosity

First algorithm in the history of IT

The first algorithm on the history of IT was developed by Ada Lovelace on paper in the 1840s. She has been called the world's first computer programmer. She described, step by step, how a machine could calculate a sequence of Bernoulli numbers.

First algorithm

The first Google algorithm

 

The first algorithm written in the phase of creation of Google is PageRank and was named after Larry Page. Basically, it's an algorithm to the rank website on the search engine results. It assigns a numerical weighting to each element of a hyperlinked set of documents with the purpose of measuring its relative importance within the set.

This is the simplified formula of the algorithm

Google pageRank

Where

  • PR[A] is the value of the PageRank we want to calculate
  • N is the number of known pages
  • n is the number of pages that include a link to A
  • PR[Pk] are the values of the PageRank of each page
  • C[Pk] is the number of the links of the current page
  • d = 0,85 is a constant decided by Google 

That's all!