23/12/2014
In my discrete mathematics class, I often use the Fibonacci rabbits example, here to show how to resolve a recurrence, there a variant where some rabbits go away, here again for rewrite systems.

What are rewrite systems? Not unlike context-free grammars, they provide rules generate “words” in a “language”. Turns out the Fibonacci rabbit population problem is super-easy to model as a rewrite system.

Read the rest of this entry »

Leave a Comment » | algorithms, Mathematics, theoretical computer science | Tagged: Fibonacci, mitosis, Rabbits, rewrite systems | Permalink

Posted by Steven Pigeon

27/12/2011
In a previous installment, about filtering noise, we discussed how to use a moving average to even out irregularities in a sequence. Averaging over a window is tricky. First, the window size must make sense in terms of the speed at which the signal changes (in samples), and the average is (overly) sensitive to outliers.

One way to limit the influence of the outliers for denoising is to use the median. However, computing the median is usually more tricky than computing the average, or mean, and this first post (in a series of three, in the next few weeks), discusses how to compute the median efficiently using the *selection* algorithm.

Read the rest of this entry »

4 Comments | algorithms, C, C-plus-plus, data structures, programming, theoretical computer science | Tagged: Lomuto, median, QuickSort, selection, Wirth | Permalink

Posted by Steven Pigeon

16/03/2010
QuickSort, due to Hoare, is one of the best comparison-based sorting algorithms around. There are a number of variations, but the vanilla QuickSort does a great job… most of the times.

Indeed, there are occasions where QuickSort leaves its expected run-time to reach run-time, its worst case. But what does it take to push QuickSort into its worst behaviour?

Read the rest of this entry »

4 Comments | algorithms, hacks, Mathematics, programming, rants, theoretical computer science, wtf | Tagged: bubble sort, C, comparison sort, computational complexity, evil, Hoare, malicious data, QuickSort, sort, sorts, Worst Case, Worst Case Behavior | Permalink

Posted by Steven Pigeon

07/03/2010
Ulrich Meyer, Peter Sanders, Jop Sibeyn (eds.) — *Algorithms for Memory Hierarchies* — Springer, (Lectures Notes on Computer Science LNCS # 2625), 2003, 428 pp. ISBN 978-3540-00883-5

(Buy at Amazon.com)

This book is a collection of chapters on various topics pertaining to memory hierarchies and their algorithms, but written by several different authors, without any special uniformity in tone or topics; but that’s OK because it allows the reader to have a broad view of algorithms for memory hierarchies.

Read the rest of this entry »

Leave a Comment » | algorithms, data structures, Mathematics, Operating System, programming, Suggested Reading, theoretical computer science | Permalink

Posted by Steven Pigeon

07/03/2010
Peter Brass — *Advanced Data Structures* — Cambridge University Press, 2008, 492 pp. ISBN 978-0521-88037-4

(Buy at Amazon.com)

The first part of the book concentrates on search trees and variants, whether balanced trees, interval trees, or heaps. Chapters are dedicated to connected components and like algorithms, one to algorithms for strings, and one for hash tables. Follows appendices on computation, cache oblivious algorithms, etc.

Read the rest of this entry »

1 Comment | algorithms, data structures, Mathematics, Object Oriented Programming, programming, Suggested Reading, theoretical computer science | Permalink

Posted by Steven Pigeon

24/11/2009
There’s a theorem that, although its formulation is trivial, is of paramount importance in many things, including data compression. I’m talking about the frivolous theorem of arithmetic, of course. The theorem takes many forms, but one being:

Almost all natural numbers are very, very, very large.

The converse implies that there are a lot more big numbers than there are smaller numbers. Of course, this is trivially self-evident. But this trivial theorem can serve as a brutal reality check for many hypotheses. For example, one can use the frivolous theorem of arithmetic to disprove the existence of a lossless data compression method that compresses *all* inputs to smaller bit strings.

Read the rest of this entry »

8 Comments | data compression, Mathematics, theoretical computer science | Tagged: bit strings, common sense, counting argument, data compression, frivolous theorem of arithmetic, numbers, pidgeonhole principle | Permalink

Posted by Steven Pigeon

13/10/2009
Programmers aren’t always the very rational beings they please themselves to believe. Very often, we close our eyes and take decisions based on what we *think* we know, and based on what have been told by more or less reliable sources. Such as, for example, taking red-black trees rather than AVL trees because they are faster, while not being able to quite justify in the details why it must be so. Programming using this kind of decision I call *cargo cult programming*.

Originally, I wanted to talk about red-black *vs.* AVL trees and how they compare, but I’ll rather talk about the STL `std::map` that is implemented using red-black trees with G++ 4.2, and `std::unordered_map`, a hash-table based container introduced in TR1.

Read the rest of this entry »

3 Comments | algorithms, data structures, Design, hacks, Mathematics, programming, theoretical computer science | Tagged: algorithmics, assumptions, AVL tree, balancing tree, C, cargo, cargo cult, complexity, hash table, magic, magic thinking, red-black tree, Scrabble, Splay Tree, std::map, std::unordered_map, stl, TR1 | Permalink

Posted by Steven Pigeon

21/07/2009
I once worked in a company specializing in embedded electronics for industrial applications. In one particular project, the device communicated through a RS-422 cable to the computer and seemed to return weird data once in a while, causing unwanted behavior in the control computer whose programming did not provide for this unexpected data. So I took upon myself to test the communication channel as it seemed that the on-board software was operating properly and did not contain serious bugs. I added a check-sum to the data packet and it turned out that some packets came in indeed corrupted despite the supposedly superior electrical characteristics of the RS-422 link.

After a few days’ work, I implemented the communication protocol that could detect and repair certain errors while reverting to a request to retransmit if the data was too damaged. I then started gathering statistics on error rate, number of retransmit, etc, and the spurious behavior on the controller’s side went away. My (metaphorically) pointy-haired boss opposed the modification because “*we didn’t have any of these damn transmission errors until you put your fancy code in there*“. Of course, this was an epic facepalm moment. I tried to explain that the errors have always been there, except that now they’re caught and repaired. Needless to say, it ended badly.

Notwithstanding this absurd episode, I kept using check-sum to validate data whenever no other layer of the protocol took care of transmission errors. So, this week, let us discuss check-sums and other error detection algorithms.

Read the rest of this entry »

1 Comment | algorithms, bit twiddling, embedded programming, hacks, Life in the workplace, Mathematics, programming, theoretical computer science | Tagged: check-sum, check-sums, checksum, checksums, CRC, cyclical redundancy check, data packet, divisor polynomial, Don Knuth, error correction, error detection, ethernet, hash, ISBN, ISBN 10, ISBN 13, Knuth, Luhn, md5, mod, modulo, remainder, RS-232, RS-422, salt, searching, secure hashes, sha, SIN, social insurance number, sorting, sorting and sorting, The Art of Computer Programming, zip, zip file | Permalink

Posted by Steven Pigeon

29/06/2009
I am not sure if you are old enough to remember the 1977 IBM movie Powers of Ten (trippy version, without narration) [also at the IMDB and wikipedia], but that’s a movie that sure put things in perspective. Thinking in terms of powers of ten helps me sort things out when I am considering a design problem. Thinking of the scale of a problem in terms of physical scale is a good way to assess its true importance for a project. Sometimes the problem *is* the one to solve, sometimes, it is not. It’s not because a problem is fun, enticing, or challenging, that it has to be solved optimally right away because, in the correct context, considering its true scale, it may not be as important as first thought.

Maybe comparing problems’ scales to powers of ten in the physical realm helps understanding where to put your efforts. So here are the different scales and what I think they should contain:

Read the rest of this entry »

1 Comment | algorithms, assembly language, bit twiddling, CPU Architecture, data structures, Design, hacks, Instruction Sets, Life in the workplace, Object Oriented Programming, Operating System, Portable Code, programming, theoretical computer science, Zen | Tagged: 1977, atomic, bit twiddling, branch prediction, C Standard Library, class, classes, coding, compatibility, CPU, ecosystem, global, graphical user interface, GUI, IBM, instruction, instruction set, interoperability, macroscopic, mesoscopic, methods, micro-code, micro-instruction, micro-optimization, microscopic, molecular, networking, Object Oriented Programming, Operating System, optimization, out of order execution, POD, powers of ten, premature optimization, registers, speculative execution, string, subatomic, system | Permalink

Posted by Steven Pigeon

23/06/2009
Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.

Read the rest of this entry »

2 Comments | algorithms, bit twiddling, C, C99, data structures, hacks, Mathematics, programming, theoretical computer science, Uncategorized | Tagged: address transformation, box plot, box-and-whiskers, boxplot, comparison sort, gettimeofday, graphs, median, microsecond, quartile, quartiles, Quick Sort, QuickSort, radix, Radix Sort, tests, timer, trials | Permalink

Posted by Steven Pigeon