NP-Complete

On 11.15.08, In computer science, By Dan

My friends are not computer science, but I’ve talked about NP-Completeness enough for them to know to zone out when the phrase comes up. I find the topic extremely fascinating, as at some level I feel like Algorithms courses are where math best meets computer science. Well, outside of scientific computing. Or graphics. Regardless, the two disciplines meet here.

Reading Coding Horror, I found this gem:

NP-complete problems are like hardcore pornography. Nobody can define what makes a problem NP-complete, exactly, but you’ll know it when you see it. Just this once, I’ll refrain from my usual practice of inserting images to illustrate my point.

Hilarious. The rest of the article is good, too.

Recently, my friends and I were at my school’s Divali festival. It was very crowded, and it was tough to find a set of three consecutive chairs at any table for us to all sit at. I recognized this immediately as bin-packing, an NP-hard problem. Basically, the tables are bins, and you have groups of various sizes (some people came alone, some in pairs, etc.) that you want to fit into these bins wasting as little space as possible / using as few tables as possible. Another example of this problem might be going to the movie theatre with your friends / family. My friends got bored pretty quickly when I brought this up.

Tagged with: • • •
 
0 Comments
Leave A Response

Heapsort

On 06.24.08, In computer science, math, proofs, By Dan

I was reading about Algorithm Geeks, a Google Group dedicated to algorithm-related questions apparently. I looked at one of the topics, Unique Elements in an Array, wondering what the chatter looked like.

To remove duplicate elements of an array, the best way I know is to sort your array, and then do a linear traversal, comparing each to its successor, and when they match, deleting the one of them. Quicksort is generally the algorithm-of-choice in large part because of its simplicity, but someone on this thread suggested heapsort – an algorithm of which I had never heard. I looked it over, and was drawn to the article on heaps. On that page, I was looking at an analysis of the time complexity for building the heap, and I got curious about the summation they present (h/2^h). So, I took some time and proved its convergence:

Convergence of Infinite Sum

Tagged with: • • •
 
2 Comments
Leave A Response

NP-Complete Library Puzzle

On 10.05.07, In computer science, By Dan

It seems like the last month, the only thing on my mind is NP-completeness. For those of you who are not cool enough, er, nerdy enough to know about this class of problems, the basic idea is this: if you want to solve a NPC problem, you’re f**ked. See Wikipedia.

The library on campus has had a puzzle available for people to take a crack at, with the potential for $50 at the book store. If you can solve one half of it, you get one entry, and if you can solve the other half, you get a second. The drawing is at 1 PM today.

The problem? Shape-separability. You’ve seen these genre of puzzles before: a hopeless tangle of metal parts one of which can be removed from the mess. This… is an NP-Complete problem.

We even talked about shape-separability in Applied Algorithms, proving that it’s NPC by reducing it from set-partition – a problem we proved NPC on a homework (I used subset-sum). (A quick note: a problem is shown NPC by demonstrating that a known NPC problem, and reduce it to your problem, the thinking being that if you can solve your problem in polynomial time, you can solve this NPC complete problem in polynomial time. Therefore, your problem is in NPC.)

I took a look at it yesterday and played with it for about an hour, leaving irked that I couldn’t solve it – I had expected not a physical puzzle, but rather something a computer scientist might like. I had also expected that it would be the kind of thing I could just show up for and solve on the spot. On the way to school this morning, I had a sort of ‘ah-ha’ moment (no, not “Take On Me”), and so before class, I hopped on over the library and the solution was exactly what I had come up with. A good start to hopefully a good day.

I’ve got my two entries and we’ll see what happens at 1 – it’s a tough problem (after all, it’s NPC), and it was not well-advertised.

Tagged with: • • •
 
1 Comments
Leave A Response
Go To Top »