Integer division by constants

Today I’m going to discuss a few clever algorithms for dividing values by constant values known at compile-time, without the use of the division instruction. In compiler optimization theory, the basic problem we attempt to solve is to create algorithms which take a specific program as input and produce a better program, for example a program which…

8

Succinct data structures

Sorry for the long hiatus, everyone. Today I’m going to talk about succinct data structures, which are informally data structures that use very close to the absolute minimum possible space. This material is largely based on lectures by MIT professor Erik Demaine, as transcribed by 6.897 students Wayland Ni and Gautam Jayaraman (link). Also see…

4

Persistent data structures

When learning to program in a functional language such as Lisp, Ocaml, or Haskell, one of the most difficult aspects of the paradigmic shift is that data in these languages is almost entirely immutable, or read-only. In purely functional programs, there is no assignment, and data structures cannot be modified. But how are we to…

3

Software transactional memory

Software transactional memory (STM) is a scheme for concurrent programming with multiple threads that uses transactions similar to those used in databases. Today I’ll discuss what STM is, how it works, some implementations, and why you should care. It’s well-known that if two or more threads blindly try to access the same data at the…

7

Non-nullable types

If you write programs in C, C++, Java, or C#, you’ve gotten used to having the null value around. The null value is a special reserved reference (or pointer) value indicating that a reference does not refer to any object. It’s useful for constructing a variety of data structures, but it’s also a notoriously common…

5

Secret sharing

One of the most difficult problems in cryptographic key management is keeping a secret key safe from both compromise and loss. If you don’t make enough backups, the key might be destroyed in a hardware failure or natural disaster. But if any backup is compromised, the key is compromised. Rather than invent new tools, one…

2

Custom building and code generators in Visual Studio 2005

I’m a fervent fan of using code generator tools wherever possible to make your life easier. Although they come with issues related to effective building, diagnostics, and debugging, the amount of value they add to your application is immense: they can eliminate entire classes of potential bugs, save you a great deal of effort and…

11

Modular arithmetic and primality testing

Number theory is, roughly speaking, the study of properties of integers. Often a problem which is easy for real numbers, such as factoring or linear programming, seems to be considerably more difficult when restricted to integers (in fact, integer programming is NP-hard). Much of the focus of modern number theory is on solving these problems…

7

The point location problem

Computational geometry is a field that studies efficient solution of geometric problems, which are critical in mapping, manufacturing, and particularly graphics applications. If you find data structures and algorithms interesting, it’s likely you’d also find computational geometry interesting, because it often combines and adapts well-known data structures and algorithms in novel ways to solve natural problems…

0

The Visitor pattern and multiple dispatch

Today I’ll talk about multiple dispatch, a programming language feature that increases flexibility of method calls and eliminates the need for awkward pattern constructions, at the cost of some additional complexity in the dispatch algorithm. The Visitor pattern Those who have read the Gang of Four’s seminal Design Patterns may recall the Visitor pattern. Its…

14