Actually, at the NSA (and CIA, too IIANM), they shred documents with a cross-cut shredder, then dump it all into a mulching vat where the documents are slowly dissolved and made into a greyish goo which can be used to make brown paper. I don't recall if they actually make the paper at the end or how they dispose of the goo, if they don't make paper from it.
They make and sell cardboard pizza boxes out of it.
No, I'm not kidding. Read James Bamford's "The Puzzle Palace" or "Body of Secrets."
(Bart at his new, good school is having troubles.)
Teacher: Don't you know cursive?
Bart: Well, I know hell, and damn, and bi--
Teacher: No no, that's not what I mean. What about fractions? Long division?
Bart:...I know *of* them...
But seriously folks. I remember a few years back, I was just about to take the GRE, and the last thing on the signup sheet is to copy this long, drawn-out "I will not cheat and I will not tell anybody else about the questions and bla bla bla" integrity statement. In *cursive*. It was seriously 15 lines long. I hadn't written cursive since 2nd grade. So I was sitting there for minutes, trying to remember how to draw a capital G, and looking like a general imbecile. The lady was delaying the start of the test because she had to wait for me to pump out this crap that looked like it was written by an epileptic. "And this kid wants to go to *grad school*?" they must have been thinking.
Re:5?! -Interesting +Utter Crap
on
Making Change
·
· Score: 2, Insightful
Hmm, is this more support for the argument that people are getting dumber?
It says that the practice didn't start catching on until the 1920s, when merchants would under-price things at.95 and.99 to convince gullible people that they were getting "a bargain."
So there must be a *lot* of suckers out there today...
That hard problem is more interesting. Isn't it NP-hard?
Yeah, it's NP-hard, for the reason you gave (in fact, this is also an integer knapsack problem, which is also NP-hard).
However, the number of animals is limited to 16. This means that it ought to be feasible to iterate over all subsets of animals (there are 2^16 such). For example, it should be feasible to compute (in a couple of seconds) whether each subset of animals can occupy a boat together.
Summarizing your algorithm: for every pair of nodes that are not connected, do the proper intersections of their in/out-neighborhoods. (Note however that the pair of nodes in the other corners must be checked for connectedness too.)
"For every pair" => O(n^2) "intersect neighborhoods" => O(n log n) (by sorting the entries in the neighborhoods and comparing from there) But as for checking connectedness of pairs in the two intersections, that's again O(n^2).
So we're back at O(n^4) (not to mention the work that goes into preventing double-counting of cycles that are found in several different ways).
Given a set of up to 16 animals and what animals can't be placed on a boat together, find the minimum number of trips it takes to get all the animals across the river. Oh yeah, the animals also have weights and if the weight of the animals on the boat exceeds a certain threashold, you can't transport them.
Neat - when you say "what animals can't be placed on a boat together," do you mean "what animals can't be left alone together?" I'm thinking of the classic problem of the farmer with the chicken, grain, and fox. The farmer can only take 1 item with him at a time... but if he leaves the chicken and grain together, the chicken eats the grain, etc.
If that isn't what you mean, that one would make a nice problem too:).
well after 69 comments (hehe), there has not been a SINGLE one discussing the competition problems, all three of which are quite interesting.
I'll take a shot.
Ironically, I find the "easiest" one the hardest. I can think of a brute-force O(n^4) algorithm, but it's not pretty.
The medium problem seems to be straight-up dynamic programming.
Sadly, the "hard" problem is also straight-up dynamic programming, and is well-known. It's very lame that they chose this problem -- I'm pretty sure it's in CLR (Cormen, Leiserson, Rivest "Introduction to Algorithms"), and it's definitely considered in many other sources.
Overall, these questions don't seem to be testing for breadth of knowledge, or even ability to think creatively. They all have essentially cookie-cutter answers.
Coding up correct answers under time pressure is another matter, of course. I give all the credit in the world to someone who can crank out the code and test out all the corner cases properly.
If its non-random, then its a pattern, and can be expressed as a fraction, which means that pi is rational. But we've already said that its irrational. Contradiction.
The flaw in your argument is here. Just because something has "a pattern" doesn't make it rational. The number 0.101001000100001... (where the count of 0s between successive 1s increases by one) is irrational, however, it certainly has a pattern.
In order for a number to be rational, its decimal expansion must eventually become an infinitely-repeated fixed, finite-length string (and nothing else!). This doesn't happen in pi, or in sqrt(2), or in the number I wrote above. However, certain finite strings may show up infinitely often (such as "000" in my example) in various places, they'll just have other junk between them.
Palladium itself hasn't been proven insecure(yet).
That depends on what the meaning of the word "secure" is. Or to which party (i.e., user, vendor, etc.) the word "secure" applies.
With Palladium, I won't be able to inspect the memory or other operational aspects of any program that is running in the "nexus," and which doesn't give me permission to do so. Supposing some kind of virus or, more likely, spyware starts running in the nexus layer, I have no way (short of pulling the power plug) of preventing it from running. That doesn't sound like the kind of "security" I'm interested in.
I bought a Brother HL-1050. It worked great (quiet, fast, clean output), when it worked.
About a month after the 1-year warrantee ran out, the drum unit failed. It cost over $100 to replace, and the printer itself was only $290. A year after that, I turned it on to discover a weird pattern of blinking status lights. Looking at the manual, this indicated some kind of super-fatal breakage. "Replace entire mechanism, minus plastic shell" or some such nonsense. I haven't gotten around to that, and probably never will, because it'll undoubtedly cost more time and convenience than buying a new printer.
In the more than one year I've been printerless, it turns out that there've only been a couple times when it would have been nice to have one; never was it absolutely necessary. So I think I'll stick it out without a printer for awhile.
1 followed by 100 zeros. A googol is a very large number. There isn't a googol of anything in the universe. Not stars, not dust particles, not atoms.
I think you mean a googol-plex, which is a googol raised to a googol. That's more than the number of atoms in the universe.
The original poster is right - a googol is 1 followed by 100 zeros, aka 10 to the 100th power, or 10^100. The number of particles in the universe is estimated to be between 10^72 and 10^87. Even if the high estimate is right, a google is 10 trillion times more. The US federal budget is "only" 2 trillion dollars per year, so a googol is bigger than the number of particles in the universe, by a wide margin.
A googolplex is not a googol to the googol (that's an even bigger number, and is actually a googolplex to the 100th power). A googolplex is "only" 10 raised to the googol, or 1 followed by a googol zeros, or 10^(10^100). Of course, this number is definitely larger than the number of particles in the universe, too.
The two funniest newspaper names that Dave has ever mentioned in his columns (I swear, I am not making these up):
The "St. Louis Post-Dispatch" (as in, "Harlin's ferret really went crazy when it got stuck in his Post-Dispatch"), and the "Portland Oregonian" (as in, "That email promised to increase the size of my Oregonian!").
Compared to those, the "Kalamazoo Gazette" sounds about as normal as The New York Times.
are you often recognized "on the street"? What I mean is, you're obviously very famous and have tons of fans. But at the same time, I get the sense that you have more of a "cult" following and maybe aren't as well-recognized as, say, Ben Affleck or Chris Rock. Do you have to change your daily routine to avoid being swarmed by adoring fans, or do or do you enjoy relative anonymity in your daily life?
PS - you recently wrote that Michigan ranked among the stupidest states because we have an "official state soil." I heartily agree, but boy did your column provoke some angry letters in the Kalamazoo Gazette!
Re:The Book, and what it might contain
on
Immortal Code
·
· Score: 1
Martin Aigner and Gunter Ziegler have taken a crack at what a few chapters of The Book might look like. The result is "Proofs from The Book," which is both an excellent tribute to Paul Erdos and a beautiful collection of simple and elegant proofs from several branches of mathematics. It's a great book, and accessible even to those with just a high school math background.
Here's one place to get it: http://www.amazon.com/exec/obidos/tg/detail/-/3540 678654/
I can envision people discovering the waremarking technology though. You and a friend register and download the same track, then run a binary diff on the files. Should be pretty easy to determine where the watermark is and change it though.
Yep, this is called collusion in the literature, and it's been considered (even for the case of several users comparing their files). Lots of work has been put into developing codes that are immune to collusion in various ways. Examples include "identifiable parent property (IPP) codes," "traceability (TA) codes," and "collusion-secure codes."
The upshot is that it is provably impossible to construct collusion-secure codes unless they have very large "alphabets" or require lots of bits to be embedded in the media. Both situations are bad for the distributors, because watermarking technology is pretty inefficient in terms of how much raw data it needs to robustly embed marks.
I have a paper with some of these results on my webpage, if you're interested.
Slashdot Mirror
Actually, at the NSA (and CIA, too IIANM), they shred documents with a cross-cut shredder, then dump it all into a mulching vat where the documents are slowly dissolved and made into a greyish goo which can be used to make brown paper. I don't recall if they actually make the paper at the end or how they dispose of the goo, if they don't make paper from it.
They make and sell cardboard pizza boxes out of it.
No, I'm not kidding. Read James Bamford's "The Puzzle Palace" or "Body of Secrets."
They wrote a book about it. It's called "Bringing Down the House."
Kevin Spacey has optioned the movie rights, I think.
... to put my brain in "counting cards" mode.
Now, off to watch Wapner. Six minutes till Wapner.
(Bart at his new, good school is having troubles.)
...I know *of* them...
Teacher: Don't you know cursive?
Bart: Well, I know hell, and damn, and bi--
Teacher: No no, that's not what I mean. What about fractions? Long division?
Bart:
But seriously folks. I remember a few years back, I was just about to take the GRE, and the last thing on the signup sheet is to copy this long, drawn-out "I will not cheat and I will not tell anybody else about the questions and bla bla bla" integrity statement. In *cursive*. It was seriously 15 lines long. I hadn't written cursive since 2nd grade. So I was sitting there for minutes, trying to remember how to draw a capital G, and looking like a general imbecile. The lady was delaying the start of the test because she had to wait for me to pump out this crap that looked like it was written by an epileptic. "And this kid wants to go to *grad school*?" they must have been thinking.
Hmm, is this more support for the argument that people are getting dumber?
.95 and .99 to convince gullible people that they were getting "a bargain."
It says that the practice didn't start catching on until the 1920s, when merchants would under-price things at
So there must be a *lot* of suckers out there today...
That hard problem is more interesting. Isn't it NP-hard?
Yeah, it's NP-hard, for the reason you gave (in fact, this is also an integer knapsack problem, which is also NP-hard).
However, the number of animals is limited to 16. This means that it ought to be feasible to iterate over all subsets of animals (there are 2^16 such). For example, it should be feasible to compute (in a couple of seconds) whether each subset of animals can occupy a boat together.
Summarizing your algorithm: for every pair of nodes that are not connected, do the proper intersections of their in/out-neighborhoods. (Note however that the pair of nodes in the other corners must be checked for connectedness too.)
:)
"For every pair" => O(n^2)
"intersect neighborhoods" => O(n log n)
(by sorting the entries in the neighborhoods and comparing from there)
But as for checking connectedness of pairs in the two intersections, that's again O(n^2).
So we're back at O(n^4) (not to mention the work that goes into preventing double-counting of cycles that are found in several different ways).
Which solution would you rather code up?
Given a set of up to 16 animals and what animals can't be placed on a boat together, find the minimum number of trips it takes to get all the animals across the river. Oh yeah, the animals also have weights and if the weight of the animals on the boat exceeds a certain threashold, you can't transport them.
:).
Neat - when you say "what animals can't be placed on a boat together," do you mean "what animals can't be left alone together?" I'm thinking of the classic problem of the farmer with the chicken, grain, and fox. The farmer can only take 1 item with him at a time... but if he leaves the chicken and grain together, the chicken eats the grain, etc.
If that isn't what you mean, that one would make a nice problem too
well after 69 comments (hehe), there has not been a SINGLE one discussing the competition problems, all three of which are quite interesting.
I'll take a shot.
Ironically, I find the "easiest" one the hardest. I can think of a brute-force O(n^4) algorithm, but it's not pretty.
The medium problem seems to be straight-up dynamic programming.
Sadly, the "hard" problem is also straight-up dynamic programming, and is well-known. It's very lame that they chose this problem -- I'm pretty sure it's in CLR (Cormen, Leiserson, Rivest "Introduction to Algorithms"), and it's definitely considered in many other sources.
Overall, these questions don't seem to be testing for breadth of knowledge, or even ability to think creatively. They all have essentially cookie-cutter answers.
Coding up correct answers under time pressure is another matter, of course. I give all the credit in the world to someone who can crank out the code and test out all the corner cases properly.
If its non-random, then its a pattern, and can be expressed as a fraction, which means that pi is rational. But we've already said that its irrational. Contradiction.
The flaw in your argument is here. Just because something has "a pattern" doesn't make it rational. The number 0.101001000100001... (where the count of 0s between successive 1s increases by one) is irrational, however, it certainly has a pattern.
In order for a number to be rational, its decimal expansion must eventually become an infinitely-repeated fixed, finite-length string (and nothing else!). This doesn't happen in pi, or in sqrt(2), or in the number I wrote above. However, certain finite strings may show up infinitely often (such as "000" in my example) in various places, they'll just have other junk between them.
FFT is O(n log n), not O((log n)^2). There's a big difference.
Naive bignum multiplication would be O(n^2), which is a good bit slower than O(n log n).
Palladium itself hasn't been proven insecure(yet).
That depends on what the meaning of the word "secure" is. Or to which party (i.e., user, vendor, etc.) the word "secure" applies.
With Palladium, I won't be able to inspect the memory or other operational aspects of any program that is running in the "nexus," and which doesn't give me permission to do so. Supposing some kind of virus or, more likely, spyware starts running in the nexus layer, I have no way (short of pulling the power plug) of preventing it from running. That doesn't sound like the kind of "security" I'm interested in.
I bought a Brother HL-1050. It worked great (quiet, fast, clean output), when it worked.
About a month after the 1-year warrantee ran out, the drum unit failed. It cost over $100 to replace, and the printer itself was only $290. A year after that, I turned it on to discover a weird pattern of blinking status lights. Looking at the manual, this indicated some kind of super-fatal breakage. "Replace entire mechanism, minus plastic shell" or some such nonsense. I haven't gotten around to that, and probably never will, because it'll undoubtedly cost more time and convenience than buying a new printer.
In the more than one year I've been printerless, it turns out that there've only been a couple times when it would have been nice to have one; never was it absolutely necessary. So I think I'll stick it out without a printer for awhile.
If government spending on something isn't an indication that that something is dying, I don't know what is.
This reminds me of "Government in three easy steps:"
1. If it moves, tax it.
2. If it keeps moving, regulate it.
3. If it stops moving, subsidize it.
I remember playing a 'warezed' (didn't have that word back then) version of Test Drive cracked by Paul.
This is interesting, considering Paul's assertion:
The fact that the Internet can be used to massively violate intellectual property rights doesn't make it moral to do so.
Paul, you got some 'splainin' to do!!
(It's a joke - I can do the math. :)
Wow, 50% more comments on Slashdot!
1 followed by 100 zeros. A googol is a very large number. There isn't a googol of anything in the universe. Not stars, not dust particles, not atoms.
I think you mean a googol-plex, which is a googol raised to a googol. That's more than the number of atoms in the universe.
The original poster is right - a googol is 1 followed by 100 zeros, aka 10 to the 100th power, or 10^100. The number of particles in the universe is estimated to be between 10^72 and 10^87. Even if the high estimate is right, a google is 10 trillion times more. The US federal budget is "only" 2 trillion dollars per year, so a googol is bigger than the number of particles in the universe, by a wide margin.
A googolplex is not a googol to the googol (that's an even bigger number, and is actually a googolplex to the 100th power). A googolplex is "only" 10 raised to the googol, or 1 followed by a googol zeros, or 10^(10^100). Of course, this number is definitely larger than the number of particles in the universe, too.
The two funniest newspaper names that Dave has ever mentioned in his columns (I swear, I am not making these up):
The "St. Louis Post-Dispatch" (as in, "Harlin's ferret really went crazy when it got stuck in his Post-Dispatch"), and the "Portland Oregonian" (as in, "That email promised to increase the size of my Oregonian!").
Compared to those, the "Kalamazoo Gazette" sounds about as normal as The New York Times.
Dave,
you've written many hilarious columns about the foibles of the Federal Government. Isn't this like shooting fish in a barrel?
Dave,
are you often recognized "on the street"? What I mean is, you're obviously very famous and have tons of fans. But at the same time, I get the sense that you have more of a "cult" following and maybe aren't as well-recognized as, say, Ben Affleck or Chris Rock. Do you have to change your daily routine to avoid being swarmed by adoring fans, or do or do you enjoy relative anonymity in your daily life?
PS - you recently wrote that Michigan ranked among the stupidest states because we have an "official state soil." I heartily agree, but boy did your column provoke some angry letters in the Kalamazoo Gazette!
Martin Aigner and Gunter Ziegler have taken a crack at what a few chapters of The Book might look like. The result is "Proofs from The Book," which is both an excellent tribute to Paul Erdos and a beautiful collection of simple and elegant proofs from several branches of mathematics. It's a great book, and accessible even to those with just a high school math background.
0 678654/
Here's one place to get it: http://www.amazon.com/exec/obidos/tg/detail/-/354
I can envision people discovering the waremarking technology though. You and a friend register and download the same track, then run a binary diff on the files. Should be pretty easy to determine where the watermark is and change it though.
Yep, this is called collusion in the literature, and it's been considered (even for the case of several users comparing their files). Lots of work has been put into developing codes that are immune to collusion in various ways. Examples include "identifiable parent property (IPP) codes," "traceability (TA) codes," and "collusion-secure codes."
The upshot is that it is provably impossible to construct collusion-secure codes unless they have very large "alphabets" or require lots of bits to be embedded in the media. Both situations are bad for the distributors, because watermarking technology is pretty inefficient in terms of how much raw data it needs to robustly embed marks.
I have a paper with some of these results on my webpage, if you're interested.
Let's hope the thieves read the book while they air-walk over a deep gorge...
To finish:
Lisa: "Ohhhh... it's *so* decomposed.."