DEV Community: Gustavo Reis Bauer

The Queue Data Structure

Gustavo Reis Bauer — Thu, 08 Feb 2024 17:29:36 +0000

Queue

Often taught along with stacks, queues are also, abstract data types that are defined in term of the operations we perform in them. The big difference between stacks and queues is, the order of operations they enforce, queues are FIRST IN FIRST OUT, or FIFO, that means that, the first thing that gets inside a queue is the first to go out, while stacks are LAST IN FIRST OUT, so the last we put is the first we will get back

Queues are defined in term of three operations:

enqueue (put an element at the end of the queue)
dequeue (take an element of the front of the queue)
peek (get the first element while not removing it from the queue)

We can think of queues as lines in a restaurant, when we get into a line, we have to wait everyone on our front to be served before it's our time.

Implementation

Here is a simple implementation of a queue using an array:

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

#define QUEUE_LEN 1024

struct queue_t {
    uint32_t data[QUEUE_LEN];
    size_t ptr;
};

void enqueue(struct queue_t *queue, uint32_t value)
{
    if (queue->ptr + 1 >= QUEUE_LEN)
    {
        fprintf(stderr, "The queue is full");
        exit(1);
    }

    queue->data[queue->ptr++] = value;
}

uint32_t dequeue(struct queue_t *queue)
{
    if (queue->ptr == 0)
    {
        fprintf(stderr, "Cannot dequeue empty queue");
        exit(1);
    }
    uint32_t val = queue->data[0];

    for (size_t i = 1; i < queue->ptr; ++i)
    {
        queue->data[i - 1] = queue->data[i];
    }
    queue->ptr--;
    return val;
}

uint32_t peek(struct queue_t *queue)
{
    if (queue->ptr == 0)
    {
        fprintf(stderr, "Cannot peek empty queue");
        exit(1);
    }
    return queue->data[0];
}

There is an interesting implementation detail here, whenever we dequeue, since we are removing an element from the front of the queue,
we must move all the following elements back, so in this implementation, the queue has a complexity of O(n), to avoid that, we would need to have a LinkedList as the underlying data structure, by doing it, we could just move the head pointer to the next, instead of having to do all of this.

The best implementation

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

struct node_t {
    uint32_t data;
    struct node_t *next;
};

struct linked_list_t {
    struct node_t *head;
    struct node_t *tail;
    size_t len;
};

void enqueue(struct linked_list_t *list, uint32_t data)
{
    struct node_t *node = malloc(sizeof(struct node_t));

    node->data = data;
    node->next = NULL;

    list->len++;

    if (list->len == 1)
    {
        list->head = list->tail = node;
        return;
    }

    list->tail->next = node;
    list->tail = node;
}

uint32_t dequeue(struct linked_list_t *list)
{
    if (list->len == 0)
    {
        fprintf(stderr, "Cannot dequeue empty list");
        exit(1);
    }

    struct node_t *aux = list->head;
    uint32_t data = aux->data;

    list->head = list->head->next;
    list->len--;
    free(aux);

    return data;
}

uint32_t peek(struct linked_list_t *list)
{
    if (list->len == 0)
    {
        fprintf(stderr, "Cannot peek empty list");
        exit(1);
    }

    return list->head->data;
}

void list_free(struct linked_list_t *list)
{
    struct node_t *prev = NULL;
    struct node_t *aux = list->head;
    while (aux != NULL)
    {
        prev = aux;
        aux = aux->next;
        if (prev) {
            free(prev);
        }
    }
}

Here you can see that there is no iteration when enqueuing nor dequeueing, we are just adjusting pointers, so that's why this implementation has a better time complexity when dequeueing.
There is a small caveat though, thanks to cache locality even though this implementation is faster in the worst case, it probably is not in most of them.

Quick Sort

Gustavo Reis Bauer — Thu, 08 Feb 2024 14:41:24 +0000

Quick Sort Algorithm

The quick sort is one of the most famous sorting algorithm, because it is implemented in several programming languages inside the standard library. Why is this algorithm so used??
Because of its speed, the quick sort algorithm is one of the fastest sorting algorithms having a time complexity of O(n * log n) where n is the size of the array and log is the logarithm base 2.

How does it work?

The main concept necessary to understand the quick sort algorithm, is the divide and conquer strategy.
The divide and conquer strategy is a famous military term, that used to mean that to conquer a big nation you should make first the nation, divided, often by internal conflict or civil war, and then you go and swipe the whole nation while they are busy.
Ok, but how does this concept translates to computer science? The divide and conquer, in algorithms, mean that he solve a problem by solving smaller problems, this is rather similar to the concept of mathematical induction, in which, we establish f(1), then we establish f(n) and then, we show that f(n - 1) works, by doing this, we can proof a concept.
Divide and conquer problems works the same way, first we solve the simplest problem, often called the base case, then, we formulate the recursive case, and, at last, we make so the problem, is broken down into the the simplest problems, because those we know how to solve.

The algorithm

I will show an implementation in C, and then I am going to explain line by line how this works, since it is a fairly complicated idea.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i < 11; ++i)
    {
        printf("%u ", list[i]);
    }

    return EXIT_SUCCESS;
}

// Just a helper to have a cleaner interface
void quick_sort(uint32_t *arr, size_t size)
{
    // Note: here we are passing the high bound as the size - 1,
    // so in here we are having an inclusive range
    // this is important because it makes the algorithm slightly simpler
    // and it requires less -1's which usually causes a lot of off-by one mistakes
    _quick_sort(arr, 0, size - 1);
}

size_t partition(uint32_t *arr, size_t low, size_t high)
{
    // Partition is the operation that puts all the elements smaller than the pivot
    // We are picking the last element as the pivot always,
    // I guess we could be more clever and pick a random element
    // or the median of the first, middle and last elements
    // but this is just a simple example
    size_t pivot_index = high;
    uint32_t pivot = arr[pivot_index];

    // This is going to be the index of the pivot at the end
    // of the loop
    size_t i = low;
    for (size_t j = low; j <= high; ++j)
    {
        // If the current element is less than the pivot,
        // we swap it with the element at index i
        // and increment i,
        // doing this we will know exacyly where the pivot
        // should be placed after the iteration is done
        // because all the elements of index < i are less than the pivot
        // and all the elements of index > i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] < pivot)
        {
            uint32_t temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;

            ++i;
        }
    }

    // putting the pivot at the right spot, remember, it could've been anywhere
    arr[pivot_index] = arr[i];
    arr[i] = pivot;

    return i;
}

void _quick_sort(uint32_t *arr, size_t low, size_t high)
{
    // The main idea of this function, is to use a window, that has the bounds
    // [low, high] inclusive, so if the window has length 0, low = high
    // it means we reached our base case, and the list is already sorted
    // since an array without elements is always going to be sorted
    // I guess
    if (low >= high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index + 1, high);
}

So the main idea of the algorithm is rather simple, break the array partition the list into two parts, one in which all the elements are smaller than the pivot and one in which all the elements are larger than the pivot.
And then, recursively apply this algorithm to the parts themselves, until the part has no elements, in this case, we can be sure it is properly sorted.

There's an important nuance on picking a pivot in the quick sort algorithm, if we choose bad pivots, we are going to end up with a terrible complexity, because every time we split the array into two arrays, we end up with small arrays, in this case, we are going to have n recursive calls and we will have to walk n elements, therefore quick sort has a worst case scenario of O(n*n), which is awfull, so we ned to be careful when picking a pivot, one good approach is to pick a random number, by doing so, we are pretty sure going to get the middle case, which is O(n * log n), log n since in the average case, we will split the array into two arrays that have half the elements of the initial array, and since we have to go through all the elements, there is a factor of n.

Hanoi Towers

Gustavo Reis Bauer — Wed, 07 Feb 2024 23:06:28 +0000

Hanoi Towers

The towers of hanoi, is a famous kids puzzle, that consists of three rods (usually made of wood) connected by a wider piece of wook. The puzzle comes with, a few cilindrical disks with different widhts, and to start the puzzle, we must put all the disks in ascending order (the largest will be at the bottom and the smallest on the top). The goal is to move all the disks in the same order to some other rod.
But there is a catch. A smaller cylinder cannot, ever, be under a bigger cylinder.
And that's what makes this problem much harder, so ok, how should we approach it?

I guess, we can just check, let's say we have two cylinders, and we want to move them from rod 1 to rod 3, how do we do it?
Ok it's simple:

Move the top cylinder from rod 1 to rod 2
Move the largest cylinder from rod 1 to rod 3
Move ther cylinder from rod 2 to rod 3

Ok, we solved the problem for 2 cylinders, now let's try with 3

Let's call the cylinders by name, A = smallest, B = middle one, C = largest

Move cylinder A, from rod 1 to rod 3
Move cylinder B, from rod 1 to rod 2
Move cylinder A, from rod 3 to rod 2
Move cylinder C, from rod 1 to rod 3
Move cylinder A, from rod 2, to rod 1
Move cylinder B, from rod 2, to rod 3
Move cylinder A, from rod 1, to rod 3

Now, I hope you can see the pattern, the first thing we do is, to put the largest rod at the desired, final spot they are going to be in. After that we can solve the problem as if we had one less rod, so if you see, from the 5th stop to the last one, the problem is the same, the only thing that changes, is the destination and the source rods.
So we can think that from step 5 to the end we were solving for number_of_cylinders = 2, and start = rod 2, end = rod 3

Then we mostly figured out how to solve it, there is just one piece that we did't look into yet, ok, let's say we are solving for just one cylinder, what should be the step?

Move cylinder, from rod 1 to rod 3

So in this case, we just move from start to end

Ok, so now we are ready to implement this:

Implementation

I will write this implementation in Golang, because I feel like it, if you think I could implement in another language let me know, I will do it.

// Just a way to call the _hanoi function without having to allocate an array manually
// this is just a convenience, you should not pay a lot of attention here
func Hanoi(n, start, end int) [][2]int {
    var moves [][2]int
    _hanoi(n, start, end, &moves)
    return moves
}

func _hanoi(n, start, end int, moves *[][2]int) {
    // There is only one disk, therefore we can safely assume that we can
    // move it from start to end.
    if n == 1 {
        *moves = append(*moves, [2]int{start, end})
        return
    }

    // Checking the formula works:
    // if start = 1, end = 3, other = 6 - (1 + 3) = 2
    // if start = 2, end = 3, other = 6 - (2 + 3) = 1
    // if start = 1, end = 2, other = 6 - (1 + 2) = 3
    // if start = 3, end = 2, other = 6 - (3 + 2) = 1
    // if start = 2, end = 1, other = 6 - (2 + 1) = 3
    // if start = 3, end = 1, other = 6 - (3 + 1) = 2
    // It works, because the sum of start, end and other must be 6, since we have
    // rod 1, 2 and 3, and the sum of 1, 2 and 3 is 6.
    // Therefore, we know that sum + start + other = 6,
    // solving for other, we get 6 - (start + end) = other
    other := 6 - (start + end)

    // Now, what can we do to solve, is, find the next subproblem, which in this case
    // is moving the smaller tower from the place we started, to the other place, when we do that,
    // we can be sure, that all of the disks except the largest are in the correct order and in the
    // 'other' rod
    _hanoi(n-1, start, other, moves)

    // Now, the largest disk is alone in the start rod, and we can move it to the end rod
    *moves = append(*moves, [2]int{start, end})

    // Now that our largest disk is alone in the end rod, we can move the tower that has n - 1 disks,
    // that we put in the 'other' rod, to the end rod
    _hanoi(n-1, other, end, moves)
}

If we try to use it, let me show the test cases I've implemented for this algorithm:


// Just a helper to help me check the slices are equal
func isEqualMoves(a, b [][2]int) bool {
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i][0] != b[i][0] || a[i][1] != b[i][1] {
            return false
        }
    }
    return true
}

func TestHanoi(t *testing.T) {
    moves := Hanoi(1, 1, 3)

    if !isEqualMoves(moves, [][2]int{{1, 3}}) {
        t.Errorf("Expected [[1, 3]], got %v", moves)
    }

    moves = Hanoi(2, 1, 3)
    if !isEqualMoves(moves, [][2]int{{1, 2}, {1, 3}, {2, 3}}) {
        t.Errorf("Expected [[1, 2], [1, 3], [2, 3]], got %v", moves)
    }

    moves = Hanoi(3, 1, 3)
    if !isEqualMoves(moves, [][2]int{{1, 3}, {1, 2}, {3, 2}, {1, 3}, {2, 1}, {2, 3}, {1, 3}}) {
        t.Errorf("Expected [[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]], got %v", moves)
    }

    // Good enough for me :P
}

This solution has a complexity of O(2^n) because the algorithm solves two problems of size n - 1 (where n is the number of disks) for each step, branching out in a tree that has 2^n leafs.

Integer Overflow

Gustavo Reis Bauer — Tue, 06 Feb 2024 11:27:00 +0000

Integer Overflow

Integer overflow is a problem that occurs when we have a constraint in the maximum size of an integer and we have a result that goes through that maximum size, let me demonstrate in base 10.

Let's say we have a maximum of 3 base 10 digits, so the largest value we can have is 999, but let's try to go over the limit and understand better by adding 1 to the 999, we obviously know that the result should be 1000, but in our constrained environment we get the value 0.... Why is that?

It is simple, it did the normal addition algorithm to our number, so it added 1, to the last digit, and got 10, then the carry was 1, so it added, 9 and 1 again, same thing, the result is 0, and there is a carry of 1, and in the last digit, we added 1 to 9, got a carry of 1, and the value was zero, but we can't add the carry digit to the front of the number, since our number is constrained to 3 digits, therefore we forget about the carry, and set a overflow flag in the processor.

This is the same thing that happens in a computer. so let's look at this example in C:

#include <stdint.h>
#include <stdio.h>

uint8_t get_overflow(uint8_t num)
{
    uint8_t max = 255;

    return max + num;
}

int32_t main(void)
{
    printf("%u\n", get_overflow(1));
    printf("%u\n", get_overflow(2));
    printf("%u\n", get_overflow(3));
    return 0;
}

Here, since we are using an 8 bits unsigned integer, it means that the we can only represent the largest 8 bit unsigned number, which is 255 (it goes from 0 to 255), and if we try to add one to 255, it wraps up and starts counting again from 0.

But something weird happens if we are using signed numbers, see the following example:

#include <stdint.h>
#include <stdio.h>

int8_t get_overflow(int8_t num)
{
    int8_t max = 127;

    return max + num;
}

int32_t main(void)
{
    printf("%d\n", get_overflow(1));
    printf("%d\n", get_overflow(2));
    printf("%d\n", get_overflow(3));
    return 0;
}

Obs: Here we must remember that since the sign takes one bit, the range of the unsigned integer is cut in half, so it goes from -128 to 127.
If you run the code above you might have had a surprise, the value is not zero, but the smallest number the type can hold (-128), why is that??

That happens because of how signed numbers are stored in binary, they are stored in a way we call two's complement, for ease of operating on top of it.

Two's complement??

Two complement is a rather simple way to representing binary numbers, you can follow the following algorithm to test it out.
Input: a number x

flip all of 'x's bits (if it is one, it becomes 0, if it is zero it becomes 1)
Add one to the number

So let's look at a quick example with the number 3, that in binary is 0011, flipping all the bits, would be 1100, and then adding one would be 1101

Because of this odd representation, that we are getting the number -128 when it overflows. And the cool thing is, that we can use the same circuit for adding and subtracting if we are using two's complement.

Heap vs Stack Allocation

Gustavo Reis Bauer — Mon, 05 Feb 2024 23:33:00 +0000

Heap Memory and Stack Memory

So before talking anything about stacks, heaps and dynamic memory management, I believe it is really usefull to understand a bit about how the lifetime of the variables in our code work. Because it might seem weird that whenever we declare a variable it lives long enough to serve its purpouse and then we forget about it.

A bit about scoping

Ok, then, WTF is scoping, and why should I care?
In most modern day programming languages, there is not a lot of reasons to care about scoping, you only need to now when you can access the variable you want, and if you cannot for some odd reason, you can just hoist it up to the previous scope, for example, let's look at a few examples in JavaScript:

if (number % 2 == 0) {
    let message = 'the number is divisible by 2';
} else {
    let message = 'the number is not divisible by 2';
}

// here we have no access to the message variable

In this case, we have two distinct variables with the exact same name message but we can be pretty sure they are diffent, since we cannot access the value of one from the scope of the other, so they must be different.
If we want to be able to access the message variable in the outermost scope, we would have to hoist it up, like this":

let message;
if (number % 2 == 0) {
    message = 'the number is divisible by 2';
} else {
    message = 'the number is not divisible by 2';
}

// here we can freely use the message variable

OK, so we can establish that the lifetime of a variable is tied to the scope the variable is located in, right?
Yea, kind of... In most modern programming languages, sure, you can think about scoping like that, it is a useful abstraction. But let us think about functions then, see the following example:

function getVal() {
    const retVal = {
        message: 'idk'
    };
    return retVal;
}

let value = getVal();

In this case, we declared a variable in the scope of the getVal function, but we can still acess the value of the poorly named retVal variable in the global scope. So we can establish that the language has some semantics to check for variable lifetime, normally in most modern programming languages, it checks if there is not any pointer to the value of the variable still accessible, and if so, the variable is elegible for garbage collection.

But what happens in languages that are not garbage collected? Can we return pointers to memory scoped to a specific function, let's look at the C programming language?

int *my_pointer()
{
    int a = 10;
    return &a;
}

This code seems rather inoccent, we assume we are just returning a pointer to a variable, but whenever we try to run this code, we get a beutiful error: segmentation fault (core dumped). WTF???? What happened? It should work right?

Yea, no... This is the most fundamental difference between heap allocation and stack allocation.
Whenever we create a new variable in C, we are directly tying it to the scope it was declared, so whenever the scoped is poped of, think of all the function scopes as items in a big stack (we call it the 'call stack'), we are fundamentally forgetting the values of all the variables inside the function, so if we have a reference to some memory allocated by the poped off function, we give this reference the dangling reference name, since it points to memory that is not acessible anymore.
This is called Allocation on the Stack, since the variables are stored inside stack frames in the call stack.

But what if I want to allocate something in my function and then return it to another, can I do it?? If you guess yes, you are correct.
This type of allocation is called Allocation on the heap

Heap allocations

Ok, so what is the heap and how can I allocate variables in it? So, the heap is a big chunk of memory, that can be associated with a single process, but the memory a process has access is only one, so all the memory stored in the heap will continue to live there for as long as the program does if not freed up correcly.
In most languages heap vs stack allocations is an implementation detail, and most of them tend to stack allocate primitives and heap allocate anything else.
In C, you can do whatever you want, so for example, let's say I want to allocate an integer on the heap:

#include <stdlib.h> //necessary for the heap allocation functions

int main(void)
{
    int *pointer = malloc(sizeof(int));

    *ponter = 20;
}

So, let's dissect what happened here.

We declare a pointer to an integer called pointer
We set the value of pointer to equal malloc(sizeof(int))
We set the value pointed at by pointer to 20

WTF does malloc(sizeof(int)) mean??? It is rather simple, malloc is the stdlib function for memory allocation, it stands for 'memory alloc', and we need to say how big the block of the memory we want, so in this case, I passed sizeof(int), which in many platforms is 4 bytes, so the malloc function returned a pointer to the block of 4 bytes it allocated on the heap for us, so we can use it like a normal pointer.
But the cool thing is, that the value of the pointer is not tied to any scope, so we can do something like this:

#include <stdlib.h>
#include <stdio.h>

int *get_val()
{
    int *ptr = malloc(sizeof(int));

    *ptr = 20;
    return ptr;
}

int main(void)
{
    int *ptr = get_val();

    printf("%d\n", *ptr);
}

And the printf now shows the value 20, and there is no segmentations fault.

Ok but, for the keen eye reading this, you might have thought, ok, but if the heap allocated values are not tied to any scope, when do they get deallocated?
And the short answer is: they don't. You have to manually deallocate it, like this:

#include <stdlib.h>
#include <stdio.h>

int *get_val()
{
    int *ptr = malloc(sizeof(int));

    *ptr = 20;
    return ptr;
}

int main(void)
{
    int *ptr = get_val();

    printf("%d\n", *ptr);

    free(ptr);

    // you can't use the *ptr afterward
}

So you must call the free function to deallocate memory, otherwise it will cause what is known as a memory leak which is going to eat up all your memory if you have a long running program and no low level programming skills.
But if you kill the process, the memory will be automatically freed thanks to your operating system!

The Stack Data Structure

Gustavo Reis Bauer — Sun, 04 Feb 2024 21:53:07 +0000

Stack

The stack is an abstract data type, and by this I mean that the stack is defined in terms of the operations we perform on it rather than the specifics of its implementation. The stack supports 3 main operations on it:

push (insert at the end)
pop (remove the last element)
peek (check the value of the last element)

And so, by the operations we can see that the stack works just like a stack of plates, whenever we want to access a plate, we need to keep lifting all the plates up to fetch the plate we want, then we need to put all the plates back. Because of this simple nature, the stack is really easy to implement using any data structure, and it is also a really importanty concept for how the computer actually works.

Here is an image representing how the stack operations work:

Implementation

Most of the modern programming languages already provide a Stack class or object, that provides the abstract operations I previously mentioned above, for example, in java there is a Stack class, in Javascript we use the Array class along with the methods push, pop. If the language being in use does not provide a stack we could just use an array and an integer to keep the stack, here is how it would be in the C programming language:

#include <stdint.h>
#include <stdlib.h>

#define STACKLEN 1024

struct stack_t
{
    int32_t data[STACKLEN];
    uint32_t stackptr;
};

void push(struct stack_t *stack, int32_t val)
{
    if (stack->stackptr + 1 > STACKLEN)
    {
        fprintf(stderr, "Error: stack overflow");
        exit(1);
        return;
    }

    stack->data[++stack->stackptr] = val;
}

int32_t pop(struct stack_t *stack)
{
    if (stack->stackptr == 0)
    {
        fprintf(stderr, "Error: stack underflow");
        exit(1);
        return;
    }
    return stack->data[stack->stackptr--];
}

int32_t peek(struct stack_t *stack)
{
    return stack->data[stack->stackptr];
}

So you can see how easy it is to implement those operations, even on such a barebones language such as C, we implemented a stack with security checks in a bit over 20 lines.

To insert a new element onto the stack, we bump the pointer, to store the element we want to insert and then we store it there, and to pop it, we do the opposite, we get the value that is being currently pointed by the stackptr and then decrement it, so we basically 'forget' about the value that was previously there.

So if we take a detour to look at the operations complexity, we can see, that peeking, pushing and poping a stack all have complexity O(1), since all we are doing is reading/writing to an array and updating a pointer

The name of the error stack overflow might have caught your attention, the stack overflow is a common error name whenever we want to push a new element onto a stack but the stack is not large enough to store it, it is also the name of the famous programming forums out there, see: Stack overflow.

Selection Sort

Gustavo Reis Bauer — Sun, 04 Feb 2024 20:42:32 +0000

Selection Sort

Selection sort, is a really famous and easy sorting algorithm, that is quite slow, but it is so trivially simple it is the most common one to teach first.
Ok, but what does a sorting algorithm do?

A sorting algorithm puts a set of values in an order according to a comparator, so for example, let's say we have an array of numbers and we want to put it into ascending order for convenience, or because we want to perform binary search on it.
What does it mean to put an array of numbers in ascending order? It means that every single element follows the maxim that every single element must be bigger than the previous, but smaller than the next, mathematically speaking

For each element Xn of an array A, [ Xn <= X(n+1) and Xn >= X(n-1) ]

So for example the array: [1, 10, 2, 4, 129, 0, 4] would be: [0, 1, 2, 4, 4, 10, 129]

The algorithm

The main idea of this algorithm is, go through all the elements and find the index of the smallest element, and then if the index is not the same as we currently are, swap the elements

Implementation

function selectionSort(array) {
    for (let i = 0; i < array.length; ++i) {
        let lowest = i;

        for (let j = i + 1; j < array.length; ++j) {
            if (array[j] < array[lowest]) lowest = j;
        }

        if (lowest !== i) {
            const aux = array[i];
            array[i] = array[lowest];
            array[lowest] = aux;
        }
    }
}

Ok, cool, and what is the complexity of this algorithm? Considering that, for each element we are trying to find the smallest which require us to go through each element inside of the loop, therefore, the complexity is O(n*n), making this algorithm terribly slow for big arrays, since it grows as bases of power two, so 1, 2, 4, 8, 16, 32, ...

There is one really cool implementation detail in this algorithm that is the swapping part, since we cannot just store the value of array[lowest] inside of array[i] because if we dit it like this, we would wipe the list with the same element, so we have to keep a pointer to the value of the old element before we wipe it with the value of the smallest one. This operation is often called swapping elements
In most languages there is specific syntax for that, we could do it in javascript like this: [array[i], array[lowest]] = [array[lowest], array[i]];, but I thought that would make such a simple and beautiful idea obtuse and kinda hard to follow

Pointers

Gustavo Reis Bauer — Wed, 31 Jan 2024 19:32:38 +0000

Pointers

Ok so before anything, what is a pointer, where does it live why do we need it??
A pointer is nothing more than just a data type, usually some kind of unsigned integer that has a really big range (big enough to fit all the adressable memory in the computer).
Usually whenever we want to store something in a computer program, we use a variable and store the actual thing we want inside the variable, for example, look at this C code:

#include <stdint.h>

int main(void)
{
    uint8_t really_important_value = 69;
    return 1;
}

In this case, we are storing inside the really_important_value variable, the actual decimal number 69, so whenever we reference the name really_important_value we are aliasing the number 69.
Ok but where does the pointer fit in?
One thing that I did not explain, is that there is an important thing that every single variable in a program has, that is its memory addres, and by memory address I mean where you can find it in the memory of the computer.

So, every single has a memory address, but how can I access it? In most programming languages there is no such way to get the address of a variable, since pointers are implicit. Here is how we can access and print the memory address of a variable in C:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    uint8_t really_important_value = 69;
    printf("%p\n", &really_important_value); // the hex representation of the memory address
    return 1;
}

Then, we now know that & is used to get the memory addrees, or more commonly, the reference of a value, so we can't do stuff like &420, since 420 is a constant, it does not have a memory address, (and I don't think you would ever need it).
The pointer is nothing more than the type that can contain a reference, se the example bellow:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    uint8_t really_important_value = 69;
    uint8_t *a_not_that_important_pointer = &really_important_value;
    printf("%p\n", a_not_that_important_pointer); // the same as printing &really_important_value
    return 1;
}

The only new syntax introduced in this example is the type definition uint8_t *, this type can be interpreted as a pointer to an unsigned int of 8 bits, so what do we mean by that? It means that the value inside a_not_that_important_pointer is not a uint8_t but it is a pointer to one.

Ok but can we actually get the value of thing being pointed at, from the pointer? And the answer is YES but for that you have to use the dereference operator, that is also a *
See the following example:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    uint8_t really_important_value = 69;
    uint8_t *a_not_that_important_pointer = &really_important_value;
    printf("%d\n", *a_not_that_important_pointer); // the same as printing really_important_value
    return 1;
}

Here when we were acessing the pointer, we add a * before the pointer, achieving the same result as printing the value of really_important_value.

Everything is cool and all, but why do I actually need pointers then, if it's just a way to acessing the same memory, shouldn't I just access the value itself instead of adding indirection?

There is a really cool benefit of having this indirection which might not seem obvious, so let me show with a quick example:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    uint8_t really_important_value = 69;

    uint8_t *a_not_that_important_pointer = &really_important_value;
    uint8_t not_a_pointer = really_important_value;

    really_important_value = 0;

    printf("%d\n", *a_not_that_important_pointer); // prints 0
    printf("%d\n", not_a_pointer); // prints 69 

    return 1;
}

Here is one of the most obvious benefits of this indirection, even though we are storing the same value as really_important_value into not_a_pointer, we are just doing a simple copy, so there is no 'binding' from the value in really_important_value and not_a_pointer.
But when we set a pointer to that memory address, we are 'binding' to the value of that variable, so whenever we change the value of really_important_value, we can acess the updated value from *a_not_that_important_pointer while we can't through not_a_pointer.

Ok? But that still sounds a bit weid, why would we need that? Since that 'binding' which is not a binding is just a side effect of how pointers work, that also happens when passing arguments to functions, and so we can change the value of variables that are not in our scope, which is really powerfull, since now we can have multiple return values for example, let's think of a function that goes through a list of student grades, and computes the average and the sum of all grades, how would we return it? Here's a simple way to do that:

void compute_grades_info(double grades[], size_t num_grades, double *sum, double *avg)
{
    for (size_t i = 0; i < num_grades; ++i)
    {
        *sum += grades[i];
    }
    *avg = (*sum) / (double) num_grades;
}

int main(void)
{
    double grades[] = { 10.0, 5.8, 7.0, 5.2 };
    double average_grade = 0.0, sum_of_grades = 0.0;
    compute_grades_info(grades, 4, &sum_of_grades, &average_grade);
    return 0;
}

In the example above, we computed both the sum and the average in the function compute_grades_info and stored the result inside the average_grade and sum_of_grades variables.

Pass by Value vs Pass by Reference

This is a really common way of teaching about passing pointers to functions, so I am going to explain, but I don't think this is the correct way of thinking about passing pointers.

Pass by Value

Is the default way of passing arguments to functions, when we pass a variable into a function, the program copies the value and puts it inside the argument, so any change to the argument won't have any kind of effect on the value passed to it, for example:

void compute_grades_info(double grades[], size_t num_grades, double sum, double avg)
{
    for (size_t i = 0; i < num_grades; ++i)
    {
        sum += grades[i];
    }
    *avg = sum / (double) num_grades;
}

If we try to call this function, passing our sum, and avg arguments, the only thing they will contain is garbage, since when we call the function compute_grades_info all of our arguments are copied over, so the value inside the parameter sum and avg, will be correct at the end of the calculation, but it won't affect the outside scope, since when we copy, we create a new variable, with its own address.

Pass by Reference

Happens when we pass a pointer into the argument of a function, so whenever we change the value pointed by the pointer we actually change the variable itself, the following example shows this, the values of average_grade and sum_of_grades were actually altered, since we altered it using the deref operator, we altered the thing that was beign pointed by sum and avg instead of the parameters themselves

void compute_grades_info(double grades[], size_t num_grades, double *sum, double *avg)
{
    for (size_t i = 0; i < num_grades; ++i)
    {
        *sum += grades[i];
    }
    *avg = (*sum) / (double) num_grades;
}

int main(void)
{
    double grades[] = { 10.0, 5.8, 7.0, 5.2 };
    double average_grade = 0.0, sum_of_grades = 0.0;
    compute_grades_info(grades, 4, &sum_of_grades, &average_grade);
    return 0;
}

Why I don't like this distinction

I have a clear objection to this way of teaching passing by value/reference since I don't really think there is such a think as a pass by reference, since that when you pass a reference into a function, you are passing by value, but the value is pointer, so a copy is going to happen anyway, but it is the copy of a pointer instead of the value, that allows us to have the 'binding' that I mentioned earlier.

Altough it is a weird distinction it makes a lot of sense in languages such that pointer syntax is abstracted, for example, let's look at a quick example in JavaScript:

function mutateObject(obj) {
    obj.dumbThing = 420;
}

function sum(number) {
    number += 2;
}

var obj = {};
var num = 2;

mutateObject(obj);
sum(num);

Here if we run this code, we can easily check that the value of obj is { dumbThing: 420 } after the function mutateObject runs, altough the num variable is still equal to 2 after the sum function.
This happens because we don't actually store the object when we assign it to a variable, we store a pointer to it, while when we have a number we have the actual number, so it is 'passed by value' while the obj is 'passed by reference'.

Pointer Arithmetic

Now we are actually getting inside the C programming language semantics, so if you are not a C programmer, or curious this part won't make a lot of sense. Ok? Ok, so I what the fuck do I actually mean about pointer arithmetic?
Recall when I said earlier that pointer are just big unsigned integers, that are big enough to address any memory, so the cool part about it is that, since a pointer is a number, we can treat it like so, for example:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    const uint8_t *message = "Hello world";
    uint8_t *pointer = message;

    // we can add
    ++pointer;
    printf("%c\n", *pointer); // prints 'e'

    // subtract
    --pointer;
    printf("%c\n", *pointer); // prints 'H'
}

That way, we can use pointers as windows into larger pointers, in this case the string is nothing more than a pointer, and we are going through it by incrementing and subtracting the pointer variable.
Why does this work?

Whenever we declare a pointer with multiple elements such as const uint8_t *message = "Hello world" we get back a pointer to the very first character of the string, and when going through the string, the only way we can tell we are done, is to look if the value of the pointer is NULL, thats what we mean when we try to say that strings in C are null terminated byte arrays.
Does it make sense to be like this? Yea, kind of. There are two ways to actually do that, we could either null terminate the string thus wasting one byte, or we could pack the pointer with a counter that indicates how big the string is, which seems far better right?
But how big would this counter have to be? 1 byte, nah that would only allow strings from up to 255 elements, 2 bytes, still really small, probably the counter would need to have the same size as a pointer, which would waste a lot of memory.

Here is an example of how to iterate over a string using pointer arithmetic:

#include <stdlib.h>

size_t strlen(const char *buffer)
{
    char *a = buffer;
    while (*a++) {}

    return a - buffer;
}

Here you can see how we can use both the - and the + operators to calculate the size of a string, without even having to allocate a counter or something like this.
Obs: the ++ there does not actually add one to the pointer, it adds one times the size of the thing being pointed at, this is one of the few C abstractions.

Array Decay Into Pointers

This is another C specific point, what I mean by array decay, is that arrays in C are a contiguous block of memory, so we use bracket syntax to access the elements of our array, but the bracket syntax is nothing more than just syntax sugar, since every time we create an array we actually get back a pointer to the first element of the list, for example:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
    int32_t a[] = {1, 2, 3, 4};

    printf("%d\n", *a); // this is the same as a[0], they both print '1'
    printf("%d\n", a[0]);

    printf("%d\n", *(a + 1)); // this is the same as a[1]
    printf("%d\n", a[1]);

    return 1;
}

So this is a really cool thing, an array is nothing more than just a pointer with some syntax capabilities, so whenever we pass an array into a function we must understand that we are actually passing a pointer, and not the value of the array itself, or, 'passing by reference'.
This also explains why in C arrays are 0 based, accessing the element using bracket notation is nothing more than *(array_ptr + offset), when we add 0, we just get the very first element of the array.

Linear Search

Gustavo Reis Bauer — Wed, 31 Jan 2024 19:30:38 +0000

Linear Search

Linear search is the most common way we might think about searching for somehting in a continuous list of elements.
We usually have to resort to linear search whenever we want to find something inside a list but we are not sure about how the elements
are structured inside said list. So for example, let's say we want to find a specific page in a book, but we are not sure where the page is, how would we do to find the page?

Since we can't tell anything about the list, there is no way to find the page without going through every single page, comparing the value to the value you have.
The algorithm is something like this:

Let i be 0
While i is less than the number of pages
1. Check if the ith page is the same we are looking for
2. If it is return true
3. Otherwise increment i
If i = number of pages, we could not find the page, therefore the page must not be in the book

So let's say the number of pages is 120, and the page we want to find is the same as the last one, we would need to iterate all over the list
the find the page 120, so in the worst case scenario, we would have to go through all the elements in the list, which might seem really expensive (and it can be for huge lists), but it is usually really fast because of cache locality.
Because of this limitation, we say that linear search has a complexity of O(n) such that n is the number of the input list.

Implementation

The implementantion is pretty much the same in every single language, but let us implement it in C:

#include <stdint.h>

uint8_t linear_search(uint8_t page_to_search_by, uint8_t *pages, uint_8 pagenumber)
{
    uint8_t i = 0;
    while (i < pagenumber)
    {
        if (pages[i] == page_to_search_by) return 1;
        i++;
    }
    return 0;
}

When should I use linear search?

Linear search should be used whenever we cannot apply some sort of sorting to all the elements of the list, or the list is not really big.
Small lists can fit in L3 cache and are really fast for the computer to access so it is a lot faster to just go through the whole list than doing something more sophisticated such as binary search.
If the list can be big and it is sorted, binary search is the best approach.

Binary Search

Gustavo Reis Bauer — Wed, 31 Jan 2024 19:28:33 +0000

Binary Search

Binary Search is one of the most famous searching algorithms, since it is kind of a natural way of thinking about searching a sorted list.
So we can think of an imaginary guessing game, that has two players, player A and player B.
Player A, thinks of a number while player B tries to guess exactly which number has Player A thought of.
The only kind of response Player A can give to player B is whether the guessed number is too high, too low, or correct.

How would you do about figuring out what number is player A thinking about? In the worst case scenario, how many attempts would be needed?

The bad approach

I guess, the most intuitive way to reason about this problem would be going one number at a time, so you would guess, 1, 2, 3, 4, ...
Until you find the number Player A is thinking about. This is called Linear search.
In the worst case scenario, how many attemps would be necessary to figure out exactly which number is Player A thinking about?
Let's say in this case, Player A picked, the number 1000, and the accorded range of numbers is from 0 to 100 (inclusive).
So in this case, Player B, would guess incorrectly 100 times, (0 -> 99) before guessing the correct number (100).
100 is small enough that for a computer it would not really matter, since in such small lists, the computer's cache is more efficient, and 100 numbers is nothing for a modern computer. But let's think about a billion numbers, we would have to do 1 billion + 1 guesses, which would be laughably inefficient.
We can do better.

The best approach

The best approach would be to use the information that the number you'd guessed is to low or to high to make a more informed guess.
Since all the numbers follow a crescent order (from smallest to biggest) we can be sure the list is sorted, therefore we can do something such as:

Guessing a number in the middle of the range, in this case 50
If we found the number, return true
If the number is too high, it means the number Player A picked is contained in the subset '(lower bound, 50]'
If the number is too low, it means the number Player A picked is cointained in the subset '[50, upper bound)'
Go back to step 1 with the adjusted ranges, until the upper bound is smaller or equal to the lower bound, in this case, return false

Ok. This seems really eficient, now how does this algorithm do in the worst case scenario then?
Let's assume the range is (0, 100]. In this case our first iteration would be:

50 -> too high? -> 25 -> too high? -> 13 -> too high? -> 7 -> too high? -> 3 -> too high? -> 1
Ok, so it took 6 guesses instead of 100, which is a major improvement.
If we look at mathematics, what is the inverse of an exponential, since we can easily check that the number of steps increase inverse to the powers of two, so if the list has 8 elements, the max number of guesses would be 3.
It is a function that grows really fast in the beggining and then really slow as the numbers grow.
This is called a logarithmic complexity, so we can say that binary search has a complexity of O(log n) where log means log base 2, and n is the size of the list.

Implementation

I will implement the binary search in the C programming language, since there is a really interesting implementation detail that
dynamically typed programming languages hide from you in the following implementation

#include <stdint.h>

uint8_t binary_search(uint8_t value_to_search, uint8_t *list, uint8_t lowerbound, uint8_t upperbound)
{
    while( lowerbound <= upperbound )
    {
        uint8_t middle = (lowerbound + upperbound) / 2;
        uint8_t guess = list[middle];

        if (value_to_search == guess) return 1;

        if (guess > value_to_search)
        {
            upperbound = middle - 1;
        }
        else
        {
            lowerbound = middle + 1;
        }
    }

    return 0;
}

Could you spot the bug? No? I don't blame you, this bug was hidden inside the JVM source code for years until it was found.
The problem is in the uint8_t middle = (lowerbound + upperbound) / 2; line. In this line we are getting the middle point of our list, so this appears to be correct right?
The problem comes when we add lowerbound to upperbound, because both of them are unsigned integers of 8 bits, so they have a range of (0, 255)
And the C programming language along with most statically typed languages, will see two 8 bit numbers being added and will assume that the result is also an 8 bit unsigned integer, but that might not be the case, since lets assume we are in the second iteration, and we guessed the wrong number, so in this case, our upperbound would be 255 (for a list that goes from 0 to 255) and our lowerbound would be half of it that is 127.
So in the line were we would get the middle, we would add 255 and 127 and we would get a number that is outside of the range of unsigned 8 bits integers (382), which would result in an integer overflow.

Ok. But how do we fix this? There is a simple way we can change the calculation, that keeps the same result but does avoid the overflow issue, the code would be:

#include <stdint.h>

uint8_t binary_search(uint8_t value_to_search, uint8_t *list, uint8_t lowerbound, uint8_t upperbound)
{
    while( lowerbound <= upperbound )
    {
        uint8_t middle = lowerbound + (uperbound - lowerbound) / 2;
        uint8_t guess = list[middle];

        if (value_to_search == guess) return 1;

        if (guess > value_to_search)
        {
            upperbound = middle - 1;
        }
        else
        {
            lowerbound = middle + 1;
        }
    }

    return 0;
}

Proof that (l + r) / 2 is the same as l + (r - l) / 2: