Comparing performance of two programs - problem with missing data I'm measuring running times of two programs on $n$ inputs and I want to know whether one of the programs is faster. Each program has 30 seconds and 8 GB of memory for processing one input. If the program successfully solves the problem within the limits I record its running time, otherwise I record t when the time limit was exceeded or m when the memory limit was exceeded.
Now I want to test hypothesis that the first program is faster than the second. But I don't know how to deal with t and m in the results. If the result were complete I would do paired t-test.
 A: You're dealing with censored data rather than missing data.
As a result (because you don't know when the censored ones might have finished), unless you have a parametric model, you can't compare means; with a nonparametric comparison you can compare medians (or perhaps some other quantile), as long as more than that fraction complete running.
This is essentially a survival problem - you want to test for a difference in survival time in the presence of censoring. As such, there are a number of standard tools available in many stats packages.
The presence of a second source of censored data (exceeding the memory limit) complicates things somewhat, but there are still tools for this sort of thing, such as competing risks models.

Edit in response to comments:
At first glance it seems that if the mode of censoring doesn't affect the distribution of survival time and you're not interested in the relative rates of censoring, then you could simply consider it as censored/not censored as you suggest. (As I said, I'm not remotely an expert on this stuff)
Your first issue would then be whether to use nonparametric approaches such as comparing Kaplan-Meier curves and using say a log-rank test, or semiparametric approaches, such as a Cox proportional hazards type model, where the shape of the hazard functions are assumed to be the same, or a parametric approach, such as a Weibull model.
Inserted in edit: The above advice didn't properly discuss the pairing; you can incorporate the pairing as a blocking factor in the parametric and semiparametric models, I am not sure there's a nice way to deal with it with the nonparametric censored models. An alternative would be to look at the pairing as a random effect in mixed effects models, but I have no experience whatever of using these models with censored data and probably won't be much help.
In each case, your problem would seem to fit directly into the standard sort of testing typical for each kind of model. All of these are standard analyses available in software, and in R you have the very handy resource of the survival analysis Task View, which maps out dozens of packages relating to survival. 
I think you should have the survival package in vanilla R (try library(survival)), which covers all of those things I mentioned (but you might also want to look into Frank Harrell's rms package  -- and the book is worth a read just as a part of a general statistical education, especially chapter 4).
relevant functions in survival include (not a complete list!)
survdiff - tests for differences in survival, and includes the logrank test as a special case
coxph (it looks like you can also get the logrank test as part of its summary output)
survfit (create survival curves)
survreg (parametric models)
aareg
That lot (and the associated functions, like the various summary., plot. and lines. functions) should cover you to get started, I think.
