by Dave Kellam

Bathroom skills

AHHHHHHHHHH. That’s three years of university. How did that happen? I’m starting to feel old now. And now it’s some drinkee drinkee. Starting with some tasty Guinness, followed by some not-so-tasty-but-oh-so-drunkee Olde English. It’s past noon, it’s never too early.

April 25, 2003

A Simple Definition

The formal definition of “NP-Complete” uses reductions, or transformations, of one problem to another. Suppose we want to solve a problem P and we already have an algorithm for another problem Q. Suppose we also have a function T that takes an input x for P and produces T(x), an input for Q such that the correct answer for P on x is yes if and only if the correct answer for Q on T(x) is yes. Then, by composing T and the algorithm for Q, we have an algorithm for P.

Simple. Right?

April 24, 2003

Almost there

Four exams finished, one left. The last one is algorithms, it should be interesting… i have a fair bit of material to learn.

April 23, 2003