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

While it’s true that an optimal search tree will have depth , we can’t just increase indefinitely, because we also increase the number of comparisons we must do in each node. A -ary tree will have (in the worst case) 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 »

15 Comments | Uncategorized | Permalink

Posted by Steven Pigeon

25/08/2020
Preparing lecture notes (or videos) sometimes brings you to revisit things you’ve known for a while, but haven’t really taken time to formalize properly. One of those things is fixed-point arithmetic.

Read the rest of this entry »

Leave a Comment » | algorithms, C-plus-plus, hacks | Tagged: Arithmetic, C++20 C++2a, computer arithmetic, DSP, fixed-point | Permalink

Posted by Steven Pigeon

04/08/2020
This week, I’ll show my mirror assembly to reverse the image “in hardware” for the lightboard.

Read the rest of this entry »

Leave a Comment » | hacks | Tagged: camera, glue, lightboard, mirror, screw, teaching, teaching online, wood | Permalink

Posted by Steven Pigeon

28/07/2020
Last time, I gave the instruction on how to build a lightboard, but not much in terms of how you actually use it. Now I’ve been giving lectures from it (with graduate students as test subjects), I’ve started recording for the undergrad courses, and so I’ve tweaked my setup and learnt a few tricks. This week, I’ll discuss some of them

Read the rest of this entry »

Leave a Comment » | hacks | Tagged: hardware, lightboard, teaching, teaching online, zoom | Permalink

Posted by Steven Pigeon

30/06/2020
The C99 <stdint.h> header provides a plethora of type definition for platform-independent safe code: `int_fast16_t`, for example, provides an integer that plays well with the machine but has at least 16 bits. The `int_fast`xx`_t` and `int_least`xx`_t` defines doesn’t guarantee a tight fit, they provide an *machine-efficient* fit. They find the fastest type of integer for that machine that respects the constraint.

But let’s take the problem the other way around: what about defines that gives you the smallest integer, not for the number of bits (because that’s trivial with `int`xx`_t`) but from the maximum value you need to represent?

Read the rest of this entry »

Leave a Comment » | C-plus-plus, C99, data compression, data structures, hacks | Tagged: Bits, C, C Preprocessor, C99, Log2, Portable software, template | Permalink

Posted by Steven Pigeon

09/06/2020
As you may have noticed, a global pandemics got many of us working from home. While one can argue that you can do accounting from home, it’s a lot more complicated to *teach* from home. Pretty much everyone is trying to figure that one out. For my part, I decided that zoom and the virtual whiteboard is not very interesting. Like many, I decided to use a lightboard.

So, the problem is, where do you get a lightboard on short notice? Well, you can build one. Let’s see how:

Read the rest of this entry »

2 Comments | hacks | Tagged: lightboard, pandemic, studio, teaching, week-end project, woodworking | Permalink

Posted by Steven Pigeon

05/05/2020
Evaluating polynomials is not a thing I do very often. When I do, it’s for interpolation and splines; and traditionally those are done with relatively low degree polynomials—cubic at most. There are a few rather simple tricks you can use to evaluate them efficiently, and we’ll have a look at them.

Read the rest of this entry »

Leave a Comment » | algorithms, C, C-plus-plus, Mathematics | Tagged: Estrin, Horner, Parallelism, Polynomial, SIMD | Permalink

Posted by Steven Pigeon

24/03/2020
In this quarantine week, let’s answer a (not that) simple question: how many bits do you need to encode sound and images with a satisfying dynamic range?

Let’s see what hypotheses are useful, and how we can use them to get a good idea on the number of bits needed.

Read the rest of this entry »

6 Comments | data compression | Tagged: dB, Dynamic Range, Luminosity, Pain Threshold, Photopic, Scotopic, sound, Threshold of hearing | Permalink

Posted by Steven Pigeon

14/01/2020
In one of the classes I teach, we end up writing assembly language programs. And while I explain the (sometimes very relative) benefits of writing assembly language, I use bubble sort as an example where even carefully crafted assembly language doesn’t mean much: it’s a bad algorithm to start with.

YoU CanT MaKE BuBBleSorT FaSTER With ASseMbLY

Except that it’s not quite true.

Read the rest of this entry »

4 Comments | algorithms, programming | Tagged: assembly language, AVX, bubble sort, Shell sort, sort, sorting, xmm, ymm, zmm | Permalink

Posted by Steven Pigeon