April 24, 2018
Let’s continue with lesser known color spaces. In 1980, Yu-Ichi Ohta [1] to segment images based on colors, and to do this, introduced a new colorspace—or more precisely, two variants of the same color space.
Ohta’s concern wasn’t image coding but region separation. He supposed (without much evidence) that a color space with a basis close to the principal components of the colors in the image should be maximally discriminant. He then proposed that the colorspace
Read the rest of this entry »
Leave a Comment » |
algorithms, data structures | Tagged: Color Space, compression, Lossess Compression, Ohta |
Permalink
Posted by Steven Pigeon
March 27, 2018
Last week, we had a look at how to implement a trool, or a tri-valued boolean what accepts true, false, and undefined. We remarked that the storage of an enum likely defaults to int, and that my poc wouldn’t play well with std::vector as that container has no specialization to deal with this new type.
A specialization would be interesting because we can do much better than using an integer to store three different values. We can do much, much better.
Read the rest of this entry »
2 Comments |
algorithms, C-plus-plus, data compression, data structures | Tagged: integer division, modulo, Power, shift, trool |
Permalink
Posted by Steven Pigeon
December 6, 2016
More often than I’d like, simple tasks turn out to be not that simple. For example, displaying (beautifully) a binary tree for debugging purpose in a terminal. Of course, one could still use lots of parentheses, but that does not lend itself to a very fast assessment of the tree. We could, however, use box drawing characters, as in DOS’s goode olde tymes, since they’re now part of the Unicode standard.

Read the rest of this entry »
1 Comment |
algorithms, data structures, hacks, programming | Tagged: Box, Box-Drawing, Pretty-Printing, recursion, terminal, Tree, Unicode |
Permalink
Posted by Steven Pigeon
September 6, 2016
Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.
But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.
Read the rest of this entry »
Leave a Comment » |
algorithms, C-plus-plus, data structures, programming | Tagged: bit, C, Deserialization, Pointers, serialization, Standish, Tree |
Permalink
Posted by Steven Pigeon
January 19, 2016
We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is
for a list of
values, making it a very efficient algorithm for searching.
One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?
Read the rest of this entry »
Leave a Comment » |
algorithms, data structures | Tagged: Binary Search, complexity, interpolation, Interpolation Search, PoC, search |
Permalink
Posted by Steven Pigeon
January 5, 2016
Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.

Read the rest of this entry »
Leave a Comment » |
bit twiddling, C, C99, data structures, programming | Tagged: Alignment, bit-field, C, File format, gif |
Permalink
Posted by Steven Pigeon
December 29, 2015
While preparing my lecture notes on sorting, I rediscovered the Dutch flag problem proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.

Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?
Read the rest of this entry »
Leave a Comment » |
algorithms, data structures, programming | Tagged: Dijkstra, Dutch Flag, Dutch Flag Problem, Partition, QuickSort, sorting |
Permalink
Posted by Steven Pigeon