How the List Monad helped me better understand Non-deterministic Polynomial time complexity

I have always been puzzled with the definition of NP: Non-deterministic Polynomial time complexity. A problem is in NP if it can be solved by an algorithm that runs in polynomial time on a non-deterministic Turing Machine, a computer that can "guess" which path to take toward the right answer when given a choice. I... Continue Reading →

Accumulating your merge sort

In the previous post, we described an elegant algorithm that allows to stable sort a container based on fold (also known as std::accumulate or reduce). To make it simpler, we implemented it in Haskell and used it to merge lists. The subject of today's post is to: Implement this algorithm in C++ Make it work... Continue Reading →

Folding your merge sort

Back in September 2016, I was lucky enough to attend a talk from Ben Deane entitled std::accumulate: Exploring an Algorithmic Empire. In this talk, he presents the unknown possibilities of std::accumulate, an algorithm also known as fold or reduce depending on the language. The arguments were already quite compelling... then came the slide in which... Continue Reading →

Exploring Fizz Buzz

Nowadays, most developer candidate will face an algorithmic based puzzle at their hiring technical interviews. One of the favorite exercise of recruiters is the Fizz Buzz exercise. The first time a colleague of mine introduce this exercise to me, I thought it was a dumb exercise. Then he showed me how to do it. And... Continue Reading →

Open recursion (Performance)

In the two previous posts, we used open recursion to provide efficient solutions to dynamic programming problems, keeping the following aspects decoupled: The recurrence relation: the solution to our problem The memoization strategy: indexing into a vector The order in we compute the sub-solutions As a reminder, here is the open recurrence relation we based... Continue Reading →

Open recursion (C++)

In the previous post, we explored how we could leverage open recursion to solve a dynamic programming problem, while keeping the following aspect decoupled: The recurrence relation: the solution to our problem The memoization strategy: indexing into a vector The order in we compute the sub-solutions Today we will see how to apply this trick in... Continue Reading →

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: