And now for something completely different.
It's been a while since we've had fun with mathematics so I'm going to put you to work. I want an elegant way to explain algorithmic complexity to people who never heard of it before, and I want to back up that explanation with concrete examples that are closely related to one another. Let me explain.
As the nerdier of you will know, different problems have different algorithmic complexities, as in:
- O(1): constant time
- O(log n): logarithmic
- O(n): linear
- O(n log n): ... whatever the hell that's called ...
- O(n^2): n squared, or quadratic
- O(n^3): n cubed (cubic)
- O(2^n): exponential (ouch)
- O(n!): n factorial (serious ouch)
and so on.
What I want to do is demonstrate each type of complexity with an actual problem but, to make it even clearer, I want those problems to be closely related -- as in, starting with a common set of data.
For example, if I start with a random handful of playing cards, it's easy to define a few problems with different complexities using those same cards:
- pick a random card: O(1)
- find the largest card: O(n)
- sort the cards: O(n log n)
But once I list those examples, what's left? Can I use those same cards to show a problem that has quadratic complexity? Or cubic complexity? And so on. I don't think so -- at least I can't think of any. So I don't think there's much that can be done with that handful of random playing cards.
So what else is there? What I'm after is some initial set of data that's trivially easy to describe, but allows for the definition of various problems with as many different complexities as possible. I already have a couple ideas but I'm not giving any hints. You're on your own.
JUST SO YOU UNDERSTAND, I really do know my computational complexity and NP stuff, and I'm quite capable of producing problems whose solutions have one of the complexities above. What I'm after -- as I'm sure most of you now realize -- is a relatively simple starting scenario whose variations will produce as many different complexities as possible.
So while the weighted knapsack problem is a good example of a particular complexity, can you generalize it to invent other problems of other complexities? It is a promising direction as it's something I thought of fairly quickly.
18 comments:
Could I just list some more of my favourite movie lines, please?
Not unless they involve algorithmic complexity. Now go away, or I shall have to taunt you a second time.
Nobody likes a math geek, Scully.
No. no. no ... math is bad. I already told you, the only reason I passed Trig was because of my rugby captain boyfriend with the freakish talent for numbers. And it wasn’t because I wasn’t smart enough to understand Trig, it was because I couldn’t (or wouldn’t) get past the fact that I was never going to use it in real life. So there.
He probably sat in math class thinking, "There should be more math. This could be mathier."
Well, it's not very creative, but lists of cities has the advantage that the objects have lots of different properties associated with them; populations (for sorting by size) and geographic locations, for two classic classes of problems. The problem with cards is that they only have two values associated with them.
i'm so white, i'm almost translucent. everybody knows, white folk ain't got algorhythm.
This wouldn't have something to do with Blogging Tories now would it?
Oh, hold on a tic. You were asking for complexities.
My bad.
I'd be suspicious if it were otherwise, PSA. Algorhythm (sic) is one of them MOOOOOZLIM!111! werds (sic).
Hey, I should get extra marks for including quotes that both had the word math in them.
An O(n^2) example for cards:
Sort the cards when the only allowable operation is exchanging two adjacent cards.
The proof is easy, but it's rather contrived for my taste.
Climate Change is Al-Gore-ythmic, isn't it?
I'm sure the BTs are all over this potty mouthed post: "We see through the flimsy 'Big O notation' euphemism for SEX just as easily as we see through someone saying 'flick off'. You lefties are obsessed with sex.
Two more possibly:
Place some of the cards in an m x n grid.
1. Determining the number of cards with m rows and n columns is O(log m log n) i.e. conventional multiplication.
2. Given the number of cards, determining values for the number of rows and columns is O(2^^n) i.e. exponential, though sub exponential algorithms exist. Note to BT potty mouth patrol, this is sometimes called NP-hard.
I am going on memory so I may be inaccurate in this. I have only needed to use it for arm waving explanations about why some things that programs do are so slow.
the angle of the dangle is proportional to the heat of the meat. was that helpful at all?
KEvron, neither athlete nor mathlete
I feel the need to nitpick:
Sorting a random pile of playing cards: O(n). First, arrange space for 52 piles of cards, one pile for each possible card (so you have the 2 of clubs pile, 3 of clubs pile, all the way to the ace of clubs pile, and similar piles for all other suits). Then make one pass through the n cards, placing each card in the appropriate pile. Then stack the piles together. Sure, there's an O(52) search for the correct pile for each of the n cards, but 52's just a constant.
In general, since you know that there are only 52 possible different cards in the pile, a lot of problems become bounded in their complexity.
I haven't worked this out for certain, but I think that you can do a variation of the Weighted Knapsack problem using a random pile of n cards, i.e., Given a random pile of n cards, is there subset of those cards such that their numeric values, added together, equal m, for some constant m? (This requires assigning some numeric value to the face cards). I think that this is another exponential time problem, assuming that NP != P.
For other problems, I think Traveling Salesman is one of the easier ones to understand.
Show off.
I too was going to use the weighted knapsack problem as a starting point.. Damnit, I'm just too slow.
The one thing that you really need to make a point of is the algorithm that is used to do the sorting of the cards, you automatically assume that you're using the best sorting algorithm when there are hundreds to choose from. As someone mentioned above, you can limit the swapping to adjacent pairs or worse, you can even limit the sorting to the suit of the cards to get even more specific.
There are so many algorithm games that can be played with a deck of cards, for instance you could do a "shortest path" problem that involved suits and values, for instance.
Complexity I can give you, terse explanations? Not so much.
The cards should work for producing whatever you need.
What is needed, of course, is a clearer definition of the actual problem you are trying to solve.
Post a Comment