Two Wrongs

Computing Science Dictionary

Computing Science Dictionary

I prefer being precise with terminology, sometimes to the point of annoying others.11 I have learned recently that this is a general trait among hackers, which is interesting. So here’s a list of good words to know, if you, too, want to be precise.

I’ll start with just a few and then expand on it as I go, when I remember to. Actually, the primary reason I’m writing it now is that I always forget pathological, but now I have it written down!

Amortized analysis
Figuring out the average performance of an algorithm when it is run a bunch of times, instead of just once22 This is an important distinction. Some algorithms, like for example quicksort, is generally only run once. Others, like inserting an element into a hashtable, is generally run many times in sequence.. This is interesting because some algorithms are designed such that when they are run over and over, it is impossible for them to exhibit worst-case performance each time; often they are designed such that the worst case only happens very rarely, and then we want to know that when comparing it to similar algorithms.
Continuous
Smooth; ongoing. Opposite of discrete.
Deterministic
Not random; running with the same inputs gives you the same outputs; independent of time or other hidden variables.
Dirac delta function
The function \(\delta(i)\) takes the value 1 when \(i = 0\), and 0 otherwise. Informally, one can also speak of the indicator function \(1_{i=0}\); these are two and the same.
Discrete
Stepwise; jagged; cut into a finite number of pieces. Opposite of continuous.
Dynamic programming
Entropy
Concept from information theory; essentially synonymous with “how many bits are needed to reconstruct this, if trying to use as few as possible?” In other words, when you remove all redundancies, how much information remains33 Note that this implies that a completely random string has the most information, because it cannot be generated by any other means than storing it in full.? Used when talking about compression (lower entropy means it’ll get smaller when compressed), password strength (lower entropy means it’s easier to guess), randomness (lower entropy is less random) and physical processes (lower entropy means less work, because it implies some sort of order already exists, and as long as you follow that you are being helped by the universe44 In other words: the common saying not wanting to burn any bridges can in many cases be put more literally as wanting to maintain a low entropy or not increase entropy without good reason.).
Metasyntactic variable
A placeholder in general code examples that you’re supposed to replace with your concrete code.
Nondeterministic
Appears random. Gives different results even when run with the same inputs.
Pathological case
Evil case. Insidious input. Input that in some way triggers bad performance. A situation that leads to a known bad code path.55 As an example of pathological input, feed a list that is sorted in reverse to the insertion sort algorithm, and you get terrible performance.