Log in

No account? Create an account

Previous Entry | Next Entry

not the smartest thing I ever did

Staying up an extra hour to code up a simple (i.e. not useful for totals > $1k) solution to xkcd and sending it in.

I bet I wasn't even the first.

But it is neat that that's the first time I ever wrote a python script.


Jul. 9th, 2007 06:15 pm (UTC)
Reminds me of my favorite paper from cryptography class, on knapsack cryptography (and why it doesn't work :). I think it was this paper. Amusingly, it has this to say on what the "knapsack problem" actually is:

'Some writers feel that knapsack cryptosystem is a misnomer because the cryptosystem is actually based on the subset sum problem. For example, Douglas R. Stinson points out that a knapsack problem usually refers to one “involving selecting objects with given weights and profits in such a way that a specified capacity is not exceeded and a specified target profit is attained.” [96, p. 190]. That is, a knapsack problem, as he sees it, is to maximize Spi*xi subject to Swi*xi £ c, where pi and wi are the profit and the weight of object i respectively, xi is a binary variable signifying whether object i is selected or not, and c is the capacity. And the subset sum problem usually is defined as one under which a finite set of natural numbers is given and we are asked whether there is a subset of this set whose elements sum up to a certain target, which is also a natural number. On the other hand, there are people (see [2], [32], and [39] for example) who define a knapsack problem (or a form thereof) exactly as the subset sum problem described above. And it is exactly [32] and [39] that Merkle and Hellman cited in their paper as the description of the knapsack problem on which they based their cryptosystem.'

So it would seem that xkcd has the same definition -- unless he wants to give a better weight to a mixed order of appetizers than to 7 orders of mixed fruit :)


just a guy made of dots and lines

Latest Month

October 2018

Page Summary

Powered by LiveJournal.com
Designed by Tiffany Chow