1. Algorithm's Basics

Algorithms

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation [1].

1.1. Greatest Common Divisor (GCD)

The greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $ x, y $, the greatest common divisor of $x$ and $y$ is denoted $ gcd(x,y) $ [2]. For example, the GCD of 8 and 12 is 4, that is, $ gcd(8,12)=4 $.

1.1.1. Simple approach

1.1.2. Enhanced approach

1.2. Fibonacci Serie

In mathematics, the Fibonacci numbers, commonly denoted $ F_n $, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is [3],

$ \quad F_{0}=0,\quad F_{1}=1, $
and
$ \quad F_{n}=F_{n-1}+F_{n-2} $
for n > 1.

The beginning of the sequence is thus:
$ \quad 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... $

1.2.1. Recursive algorithm

1.2.2. Iterative algorithm

1.2.3. Approximation approach

With the De Moivre's formula:

$$ f_{n} = {\frac{1}{\sqrt{5}}}{[\phi^n -(-\phi)^{-n}]} \tag{1}, $$$$ \phi = (1 + \sqrt{5})\,/\,2 $$

1.3. Integer Factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization [4].

1.4. Tower of Hanoi

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape [5].

1.4.1. The recursive and classic algorithm

1.4.2. Iterative algorithm

1.5. Sorting Algorithm

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list [6].

With time complexity of $ \Theta(n^2) $ and space complexity of $ \Theta(n) $.

Calculate the Standard Deviation of the residuals between the raw points:

Calculate the Standard Deviation of the residuals between the sorted points:

1.6. Convex Hull

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset [7].

Formally, the convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every convex set is the convex hull of its extreme points.

Andrew’s monotone chain algorithm is used, which runs in $ \Theta(n \log_{}{n}) $ time in general, or $ \Theta(n) $ time if the input is already sorted [5].

1.7. Changing Distribution

Practical example of the use of an algorithm to solve a specific problem.

Creating a toy uniform distribution

Calculate and plot new (Normal) distribution

Validation:

References

[1] Wikipedia - Algorithm.
[2] Wikipedia - Greatest common divisor.
[3] Wikipedia - Tower of Hanoi.
[4] Wikipedia - Integer factorization.
[5] Wikipedia - Bubble sort.
[6] Wikipedia - Convex hull.
[7] Andrew’s monotone chain algorithm.

« Home