Welcome back my friend! With this post I want to talk about some interesting applications of the theory of generating functions in relation to the enumeration of combinations. For this purpose let’s introduce a very simple problem: “Say we throw three regular dice, in how many ways the sum of the upper faces can be […]
Algorithms
Short post about the GCD.
You probably think you know everything about what the Greatest Common Divisor is and how to calculate it quickly! Well, that’s most probably the case, but just in case you do not remember all the details then here’s a short post about the GCD! (All the code is available here) Simple GCD Let’s start with the basic […]
Stern-Brocot tree’s.
I’ve encountered this mirable structure this weekend when dealing with cleaver ways to represent fraction of rational numbers n/m where gcd(n,m)=1 (nominator and denominator are relatively prime), Stern-Brocot tree’s are just all about building all the possible fractions that are in they lowest form. What’s interesting (but that came as evident once one understand this structure) is […]
- Algorithms
- ...
Segment tree
What is the best thing you may possible do when having a eight hours train trip? Writing a blog post of course! That’s actually an interesting story by itself: Where I was and why it take that long to come back home! Anyway! Let’s say you’ve an array of integers, as usual from index 0 to […]
- Algorithms
- ...
Solution space.
Certain problems required us to try all the possible solutions to find the one that best fit the given constraint, a very popular brute force way is to perform a complete search of the solution space by iterating over and over the data and changing each time the input variables. If the problem require to […]
Suffix trees.
An entire post covering both the theoretical part and the implementation is going to take too long, for this reason I’m splitting the material in two parts: A post with some theory introduction, and one post which will be focused on implementation details. The algorithm I would like to show you is the Ukkonen method for […]
String searching algorithms comparison.
With nature OPHELIA sick had. heel him my MARCELLUS the A with my in comes not sweet if! A means may too; that quantity prepare did! have would not thou But do; thirty fortune, lament And are A of and havior There and. QUEEN am What worse kind. at might at wears that as That […]
- Algorithms
- ...
Jewels and Endomondo, reviews.
I spent a reasonable amount of time on Jewels of Stringology and I feel ready to share with you what do I think about the book, I’m also ready to share with you how do I like endomondo since I’ve bee using it in the past two weeks, but let’s start with Jewels! Jewels. I like […]
Subsequences and Fenwick tree’s
Let’s say that we have a sequence A of 1<=n<=10^5 elements, and that this sequence may or may not be ordered but all the numbers {1…n} are present exactly once. And now given 1<=k<=10, you’re asked to find all the increasing sub-sequences of A with exactly k+1 elements. This is a problem I get from a competitive programming […]
Labyrinths (not really)
The labyrinthitis is a serious problem* which effect many people, is particularly common in people between the age of 18 to 99 owning a driving license and a car, you may encounter on the road on a daily basis people with this illness! Drive safe out there! If you are confused, well I understand!I’m trying to […]