Skip to content

Algorithms

Bloom filter

Bloom filters are space-efficient probablistic data structures used to test whether an element is a member of a set.

Channel coding&Error-correcting codes

CRC

Breadth First Search (BFS)

In this mode you explore all states that can be reached on one step, then all states that can be reached in two steps, etc...

Its time complexity can be expressed as

$$ O\left(| V | + | E |\right) $$

0-1 BFS

It's used for weighted graphs.

Sorting

Selection sort

Time: \(\Omega(n^2)\) Space: \(\Omega(1)\)

It works by iterating over each element of the list, in order to find the smallest element to move in the needed position

Insertion sort

Time: \(\Omega(n^2)\) or \(\Omega(n)\) Space: \(\Omega(1)\)

This works iterating over all elements for each entry ordering the ith element via insertion in the right position (practically implemented swapping). This has the property that at the ith step, the first i elements are ordered.

In general, insertion sort will write to the array \(\Omega(n^2)\) times, whereas selection sort will write only \(\Omega(n)\) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory.

Merge sort

Time: \(\Omega(n\log(n))\) Space: \(\Omega(n)\)

This algorthm acts recursively: it works in two steps

  1. split in half the input and calls itself in each piece if length(piece) >= 4

  2. when it merges, it builds the new piece taking the smallest element available between the two originals

  3. Wikipedia

Quick sort

Time: \(\Omega(n\log(n))\) Space: \(\Omega(\log n)\)

This is a divide and conquer algorithm that works in the following way

  1. picks a pivot element

  2. reorders the elements so that

  3. Insertion sort vs Bubble Sort Algorithms

Procedural generation

Recursion

Tail call

If a recursive call happens at the very end of the function, then the recursion can be substituted with loop, reducing the space complexity from O(N) to O(1). For example:

int sum(List* list, int acc) {
    if (list == nullptr)
        return acc;
    return sum(list->next, acc + list->val);
}


int sum(List* list, int acc) {
    while (list != nullptr) {
        acc = acc + list->val;
        list = list->next;
    }
    return acc;
}