Archive for the 'Basics' category

Basics: Binary Search

Apr 07 2007 Published by under Basics, Computational Complexity, Programming

For the basics, I wrote a bunch of stuff about sorting. It seems worth taking a moment
to talk about something related: binary search. Binary search is one of the most important
and fundamental algorithms, and it shows up in sorts of places.

It also has the amazing property that despite being simple and ubiquitous, it's virtually
always written wrong. There's a bit of subtlety in implementing it correctly, and virtually
everyone manages to put off-by-one indexing errors into their implementations. (Including me; last time I implemented a binary search, the first version included one of the classic errors.) The errors are so ubiquitous that even in a textbook that discusses the fact that most programmers get it wrong, they got it wrong in their example code!

Continue Reading »

No responses yet

Basics: Parallel, Concurrent, and Distributed

Mar 22 2007 Published by under Basics, Programming

This came up in a question in the post where I started to talk about π-calculus, but I thought it was an interesting enough topic to promote it up to a top-level post. If you listen to anyone talking about computers or software, there are three worlds you'll constantly hear: parallel, concurrent, and distributed. At first glance, it sounds like they mean the same thing, but in fact, they're three different things, and the differences are important.

Continue Reading »

No responses yet

Basics: Tautology (with a free bonus rant!)

Mar 14 2007 Published by under Basics, Debunking Creationism, Intelligent Design

Today's bit of basics is inspired by that bastion of shitheaded ignorance, Dr. Michael Egnor. In part of his latest screed (a podcast with Casey Luskin of the Discovery Institute), Egnor discusses antibiotic resistance, and along the way, asserts that the theory of evolution has no relevance to antibiotic resistance, because what evolution says about the subject is just
a tautology. (I'm deliberately not linking to the podcast; I will not help increase the hit-count that DI will use to promote it's agenda of willful ignorance.)

So what is a tautology?

A tautology is a logical statement which is universally true, by nature of its fundamental structure. That is, even without knowing anything about what the statement means,
you can infer that it must be true.

Continue Reading »

73 responses so far

Theories, Theorems, Lemmas, and Corollaries

Mar 13 2007 Published by under Basics

I've been getting so many requests for "basics" posts that I'm having trouble keeping up! There are so many basic things in math that non-mathematicians are confused about. I'm doing my best to keep up: if you've requested a "basics" topic and I haven't gotten around to it, rest assured, I'm doing my best, and I will get to it eventually!

One of the things that multiple people have written to be about is confusion about what a mathematician means by a theory; and what the difference is between a theory and a theorem?

Continue Reading »

No responses yet

Basics: Modal Logic

Mar 12 2007 Published by under Basics, Logic

I've received a request from a long-time reader to write a basics post on modal logics. In particular, what is a modal logic, and why did Gödel believe that a proof for the existence of God was more compelling in modal logic than in standard predicate logic.

The first part is the easy one. Modal logics are logics that assign values to statements that go beyond "This statement is true" or "This statement is false". Modal logics add the concepts of possibility and necessity. Modal logic allows statements like "It is necessary for X to be true", "It is possible for X to be true", etc.

Continue Reading »

No responses yet

Basics: Going Meta

Mar 11 2007 Published by under Basics

In math and computer science, we have a tendency to talk about "going meta". It's actually a
pretty simple idea, which tends to crop up in other places, as well. It's also one of my favorite concepts - the idea of going meta is just plain cool. (Not to mention useful. There's a running joke among computer scientists that the solution to any problem is to add a level of indirection - which is programmer-speak for going meta on constructs inside of a programming language. Object-orientation is, in some sense, just an example of how to go meta on procedures. Haskell type-classes are an example of going meta on types.)

Going meta basically means taking a step back, and instead of talking about some subject X, you talk about talking about X.

Continue Reading »

18 responses so far

Basics: Axioms

Mar 07 2007 Published by under Basics, Logic

Today's basics topic was suggested to me by reading a crackpot rant sent to me by a reader. I'll deal with said crackpot in a different post when I have time. But in the meantime, let's take a look at axioms.

Continue Reading »

No responses yet

Basics: Discrete vs Continuous

Mar 01 2007 Published by under Basics

One thing that I frequently touch on casually as I'm writing this blog is the distinction between continuous mathematics, and discrete mathematics. As people who've been watching some of my mistakes in the topology posts can attest, I'm much more comfortable with discrete math than continuous.

Continue Reading »

No responses yet

Not Quite Basics: Sorting Algorithms

Feb 28 2007 Published by under Basics, Computational Complexity, information theory

Multiple people have written to me, after seeing yesterday's algorithms basics post, asking me to say more about sorting algorithms. I have to say that it's not my favorite topic - sorting is one of those old bugaboos that you can't avoid, but which gets really dull after a while. But there is a kernel of interest to it - sorting can be used to demonstrate a lot of interesting ideas about
computational complexity.

Continue Reading »

52 responses so far

Basics: Algorithm

Feb 27 2007 Published by under Basics

A kind reader pointed out that I frequently mention algorithms, but that I haven't defined them in the basics posts. To me, they're so fundamental to the stuff I do for a living that I completely forgot that they're an interesting idea.

It's really pretty simple: an algorithm is description of a mechanical procedure for performing a mathematical task. But that's actually a fairly sophisticated idea - the general concept of things that describe a procedure, and which can be discussed, described, and reasoned about as entities in their own right is something quite different from nearly anything that came before it.

Continue Reading »

18 responses so far

« Newer posts Older posts »