Binary Trees are optimal… except when they’re not.

20/07/2021

The best case depth for a search tree is O(\log_b n), if b is the arity (or branching) of the tree. Intuitively, we know that if we increase b, the depth goes down, but is that all there is to it? And if not, how do we chose the optimal branching b?

measuring-tree

While it’s true that an optimal search tree will have depth O(\log_b n), we can’t just increase b indefinitely, because we also increase the number of comparisons we must do in each node. A b-ary tree will have (in the worst case) b-1 keys, and for each, we must do comparisons for lower-than and equal (the right-most child will be searched without comparison, it will be the “else” of all the comparisons). We must first understand how these comparisons affect average search time.

Read the rest of this entry »


The very long summer

12/02/2019

The original plan was to come back in september 2018, but it turns out, I was rather busy with everything else. I missed blogging, so I’ve decided to continue, but it will be at a much softer rate of about a post of month, rather than once a week.


swappity::swap

03/04/2018

constexpr is one of C++11’s features I’m starting to like very much. constexpr is a bit finicky, but it allows you to evaluate functions—including ctors—at compile time. This of course, allows computations to be replaced directly by results.

So in the best of cases, you could end-up with less code, or better yet, no code at all!

Read the rest of this entry »


ANSI soit-il.

24/10/2017

There’s no easy way of getting a console-based color output with standard C++. Of course, you can use ncurse, which does pretty much everything, but that is also quite tedious to use. But if you need just a little bit of color, ncurse is pretty overkill. Fortunately, if you have an ANSI capable terminal, that’s much easier.

Read the rest of this entry »


l8r, allig8r

02/05/2017

See you all in september!


Reading cassettes, tout azimuth (Part II)

18/04/2017

Last week we started to look at the problem of azimuth alignment on olden compact cassette tape drives, and how this misalignment affects the sound. Let’s now have a look at how azimuth affects the frequencies.

Read the rest of this entry »


Closed for Summer (2016)

26/04/2016

It’s that time again. The semester’s almost over, only a few assignments and exams to mark; everybody’s busy at their own stuff. Like the last few summers, I’ll kind of close the blog until September. I said “kind of” because maybe I’ll post a few things anyway. Especially that this summer will be interesting: more time for research, 7ECM, which I will attend, and a few other things. Seeya in September!

(RGB II, 2560×1440)

(RGB II, 2560×1440)


Science!

08/03/2016

Sorry, no entry for this week: I’ve been rather busy lately (because of science).

science


Busy doing Science

03/11/2015

Sorry, no entry for this week… I’ve been busy doing science ¯\_(ツ)_/¯


No post today

14/04/2015

Except to say that there’sn’t a post today. Things have been busy lately, so no entry for this week. ¯\_(ツ)_/¯