Hey... we can complain on slashdot all we like. If you do not like what is going on politically then you can voice your opinion with your i) vote and ii) communication to your representative.
I've been involved with communicating with senators/housereps before and its amazing what can happen if a lot of constituents get together and complain.
The links you need are below! Remember, in your letter be polite but to the point. Say that you hope that they will not support Author, Consumer, and Computer Owner Protection and Security (ACCOPS) Act of 2003. Explain that destroying this nascent technology, P2P, which has so much to offer would be a serious error. And that the interests of the few elite (hollywood) and corporate interests should not prevail over public interests.
This is similar to research being done at MIT in the Computer Architecture Group by Martin Rinard and his graduate student Brian Demsky. They are building and researching ways to automatically detect and repair data structure errors so that if a programs data structures get corrupted their tool will repair the heap so the program can keep running.
There was related work done like this back in the day at AT&T but Rinard and Demsky have introduced automatic repair which, as you might imagine like this security idea, is scary to some people. Imagine a program that would have crashed due to some bug or malicious data mangling, now kept running by a tool... But the tool chooses the repair actions based on heuristics and specifications by the developer... takes some getting used to!
All of this stuff falls under fault tolerance... its pretty crazy to look at what the AT&T/Lucent Phone Switches do when they fail... they try a million different things to keep operating no matter what happens...
Re:Correct me if i'm wrong, why not FreeNet-Napste
on
Freenet 0.5.2 Released
·
· Score: 1
There are a couple of good user interfaces for Freenet; the best is probably FROST, which includes messaging and searching. look in the "tools" section of the freenet site.
I'll check this out. But correct me if I'm wrong... we should be pushing frost to newbies not directly to freenet... If you send some novice to freenet and they don't get the intuitive interface then they'll leave freenet and not get involved.
this is very similar to mozilla and the problem with trying to convince laypersons that standards-compliance is good...
So, at least I know frost now and know what to check out and (hopefully, upon review) suggest to people...
I downloaded freenet a while ago and from a user-friendly standpoint it seemed like a nightmare. Why doesn't someone build a Napster-esque front-end to freenet to help catapult the network into a reasonable market??
The kiddies (read everyone) can get their movies/music while providing bandwidth and storage for the rest of freenet's uses as well...
If the Apache developers simply want to fix the bugs, they can use the Defect Report. If they want conduct a brutal purge of their contributors, they can use the Metric report.
Any developer knows that code that crashes is rarely the code that contains the defect. If this were the case then the bug would have been found long ago because its faultly behaviour would have presented itself immediately. Difficult bugs (those probably found by this test) are those that start somewhere in the code but do not surface until much later, masking their true identity.
That being said, certainly a list of crash sites may provide hints as to where to look for the real bug.
I guess the next question is: why isn't anyone one in your compilers group doing anything to correct that problem? Or libc? If you think the existing code is crap, then release your superior alternative and become an open source diety.
that certainly makes sense, but unfortunately we're here to do research and at the current moment we're more interested in pointer analysis, escape analysis, ownership types, modelling, fault-tolerance transformations or tools. We work all week on this sort of thing and we generally don't have time to spend rewriting code that mostly works... as hard as it is to mess with their code, its certainly a lot more work to rewrite it... of course we do have our own version of java... but that makes sense because C is a mess anyway and at least we can work to save/improve java
if everyone benchmarked with open source compilers, there would be none of the shady benchmark-specific optimizations you'd expect to see in proprietary compilers. Everything would be above the table.
have you ever looked at the GCC code? i work with the compilers group at my university and the running joke is how shoddy gcc is... how ugly the gcc code is...
you gotta remember sometime open source software is just a hodge podge of hacks thrown together.. nobodies ever bothered to refactor gcc so that its design is consistent, modular, extensible and readable...
a lot of the systems code you find out there (don't get me started on libc!!!) is crap.. plan crap
so point is, if you want to get a decent compiler for your chip porting gcc is a possibility but its code is mangled and unintuitive. nobody in their right mind (certainly not intel) is going to abandon their nice compiler for the mess that is gcc
man. that movie rock'd... i was a preteen and man mario 3 was SOOOO cool... hahahah.. remember those dinosaurs in the movie? i was driving from la to las vegas and saw them!! (either that or i was driving from l.a. to palm springs and saw them... anyway... they are much smaller now that i am an adult...
that movie rocked so much... remember the dad played link all night... hahah... that's what my dad did... i used to wake up and he would be bleary eyed having played legend of zelda all night long...
the good old days!!!
they don't make em like that anymore!!! even doom doesn't compare to the awesome time i had with legend of zelda and final fantasy...
for about four years my parents unplugged the TV. that was basically 8th grade through most of junior year of high school. and to be quite frank those are still my most productive years. i wrote more code and learned more outside of school during those years than i have learned on my own for the last 6... crazy. and i'll add one more thing, the thing that brought my incredible self learning to end was first college applications and then college when i was forced to sit down and be taught rather than exploring and teaching myself...
now i certainly played video games during that period so i wasn't completely immune to imitated violence completely, but i certainly kept out of trouble...
TV rots the mind... specially in the crucial early years... if your typical day is get home watch 2-4 hours of TV than you are falling behind your potential...
crazy thing is now i use the internet like the TV. i have my "channels" (websites) that i check often, don't really stray that far. and i check them constantly even if nothing has changed. i waste so much time with the internet its stupid. don't get me wrong some things i do are impossible without the internet and when i do use it to research its fantastic...
so i think what's happened to TV will happen to the internet... most content in the hands of a few corporates and nothing really "on" even though we have tons of channels
Yeah yeah... 13$ is about the price of a CD... so whatever you don't feed it right back into the machine that is the RIAA... instead go donate it to a good cause like the couple below (no affiliation)
Making this mandatory, in my opinion, goes against everything that open source stands for - choice. To not keep choices as free as possible to choose whatever is the best solution - be it proprietary or open - defeats the entire purpose of the choice open source provides.
I may be wrong, but I seem to remember the Brazilian economy not being that hot. That being said the *mandatory* switch could just be a cost cutting decision... Perhaps the 20% that the decision leaves open to choice (commercial or open source) is that window which is for the small amount of situations where commercial would be preferable...
I don't think that the government could have said, "yeah... lets start thinking about using open source" and had much happen in terms of adoption because then people would stick with what they are used to (which is getting forced fed microsoft)
Somebody correct me if I'm wrong (I can certainly count on that around here...) but I thought it was pretty widely accepted that the Dvorak keyboard being faster or better is a myth.
Dvorak is not crap. When people watch me type they usually comment that my fingers hardly move. I watch people type on a qwerty and their fingers are all over the place for most words. Dvorak is optimized for the english language and most words can be typed on the home row. (~1600 to be specific).
About the military (lack of) adoption. The military found that learning dvorak took about 50 hours to reach proficiency while learing qwerty took several weeks. I believe the legend is that they would have switched but there was corporate pressure for the typewriter makers.
(Remember, qwerty was originally developed to prevent the typewriter from getting mechanically stuck... not efficiency for typing)
My only problems with dvorak is that it isn't optimized for c/java code because the brackets and some other characters are kinda a bitch to get at. for that there are emacs key bindings and kinesis keyboard macros. though typing in a language like lisp/scheme or a more verbal language (more reserved words, like vhdl/vb/) is a delight because most of the typing done is done typing words.
radical like one of those Logitech/MS 'natural' keyboards
natural keyboards are crap. check out a real ergonomic keyboard [kinesis-ergo.com]. Natural keyboards have positive wrist angle which is really bad for you. With the kinesis, not only do my fingers move less with dvorak, but the kinesis eliminates any need for wrist swivel.
i used to throw parties when i was in highschool called "nerdsexfests" where 15 or so of my friends would come over and we would network and play doom, doom2, warcraft, etc. etc. i remember our first one was a little iffy because we had to go to fry's electronics to buy ethernet cards (BNC no less!) to outfit 80% of the computers my friends bought (we returned the gear the day after!!)
anyway, these nerdsexfests grew longer and longer. we did a two once and i'd say the most important thing about having a long lan party is *pace*...
Pace your playing (don't stay up *all* night), pace your food (junk food all day => feel shitty, want to leave)
We often interleaved playing actual sports to get our blood flowing...
and of course, there is nothing like good ol' loud techno blasting to keep everybody psyched...
I attended a talk by the head of the RLE lab at MIT a few weeks back. They are working on quantum entanglement and quantum teleportation as means of delivering quantum information over classical "internet" networks. The hitch is that they need an entanglement source to distribute entangled electrons to both ends of a connection...
am not complaining about a penalty. But why so much for EACH offense [of calling a number on the do-not-call list]? Is $11,000 arbitrary, or is there some reasoning behind it? It just seems like a big contrast with the couple hundred dollar fine at the State level.
don't listen to the other posts. 11,000 is calculated by an equation like this.
11,000 x (expected number of callers that report them) = (money made per call on average) x (number of calls)
that number, i suspect, is something like what they have set up. therefore, if a company ignores the list, they can't make a profit because, even though these numbers that are blacklisted are far and few between, if they ignore the list they will be fined often enough to eat their profits...
otherwise, they'd just ignore the list... a good example of this is car companies who decide based on equations whether to recall cars based on the probability of the crashes and the cost of the settlements (think "Fight Club")
I don't think you understood the article. I watched this class take place and it was drastically different than anything else I've seen... of course other classes at MIT related things to real world situations and provide examples, but this class is also about getting an *intuitive* understanding of the material...
about the no-theory objection... theory comes much easier once you have a practical understanding of a system. it is much harder to learn theory (think, "why the hell do i need to know algebra" in grade school) if you have no idea *WHY* you need to know it!
thank god.... from a developer standpoint having to have 'n' different database table entries for all the countries you support is a pain in the ass...
most of the classes i take provide lecture notes on the web in some form. i usually find that for these types of classes there is no need to take notes. it is far better to just listen intently. using a computer in class usually means you aren't paying attention... and small devices are useless for note taking at any decent speed.
as for a computer, i definitely suggest a laptop. if you are in a dorm i'd suggest a laptop-lock so that you don't have to worry about it getting stolen (still possible, but less likely)... i'd say personall, get a nice mac ibook, they work and they're simple. and with OS10 you get a nice bsd core...
for most classes all you'll have to do is write, code, or surf. you can use anything to do that.
PDA's are a waste of time, unless you can check email on them. you will never do serious work on a PDA as the display is rediculous...
>> What you really mean is "with coinage denomination systems which do not satisfy the greedy choice property, finding optimal change is non-trivial".
actually your statement is a superstatement of mine...
optimization is no non-trivial
on
Making Change
·
· Score: 2, Informative
with denominations that do not divide evenly into each other it is non-trivial to find the optimal change for a given transaction.
whereas with the US denomination (and most denominations are designed for this reason) you can use a greedy algorithm to give back change (always choose the largest coin possible, repeat) and you are guaranteed to be giving back the fewest coins.
you can prove that a greedy algorithm provides an optimal solution if the problem has optimal substructure and the greedy choice property.
To prove optimal substructure consider a collection of coins for an optimal solution, $c_1,..., c_k$, such that $\Sigma_{i=0}^k = n$ where $n$ is the amount of money in cents to change. Assume that we remove the coin with the largest value. The remaining coins, $c_2,..., c_k$, represent the solution to the sub problem of changing $(n - c_1)$. If $c_2,..., c_k$ is not optimal there exists another set of coins for this subproblem, $x_2,..., x_k$, such that this solution has fewer coins. However this is a contradiction because we can now form a solution for the original problem, $n$, by combining $c_1$ with $x_2,..., x_k$ that has a smaller size than the original optimal problem. This is a contradiction and hence $c_2,..., c_k$ is an optimal answer to the subproblem and therefore the coin changing problem exhibits optimal substructure.
To prove the greedy choice property we must show that a globally optimal solution can be arrived at by making a locally optimal, this is, greedy, choice.
For this particular set of American denominations we can prove the greedy property with a proof by contradiction. If the greedy choice were not optimal there would be an optimal collection such that:
1. some set of dimes, nickels, pennies added to more than 25 cents or
2. some set of nickels, pennies added to more than 10 cents or
3. some set of pennies added to more than 5 cents
However, all of these situations are impossible. If some set of pennies add to more than 5 cents, simply replace 5 pennies with a nickel (the greedy algorithm is better). If some set of nickel and pennies add to more than 10 cents and if there are two nickels, replace them with a dime; If there are a nickel and the rest pennies, replace a nickel and 5 pennies with a dime. The same holds for a quarter. If three dimes, replace it with a quarter and a nickel. If it's two dimes and nickel/pennies, replace it with a quarter. And so on... The property of the coins that results in the greedy property is that each coin denomination divides evenly into the next larger coin denomination. Therefore each larger coin denomination that is removed must be replaced by at least two additional coins.
With non-even denominations you are required to actually search an n^2 space for the correct set of denominations. in fact, the algorithm is:
$C(n) = 1 + min \{C(n-d_1), C(n-d_2),..., C(n-d_k)\}$.
Additionally, $C(n) = 0$ for $n = 0$. We can ignore $n 0$ are we just define $C(n 0) = \infty$. By building the array in time/size $\Theta(nk)$, and keeping track at each step which value of was chosen for the minimum, then we can list the coins by tracing backwards through these recorded values. This augmentation takes no additional time since it can be done during building the array in time $\Theta(1)$.
So, basically you've changed the problem from a linear time algorithm in the amount of change to a quadratic time algorithm in the amount of change...
big deal. we drop twice that into the charles river for the naive freshmen each year at MIT... i'm sure you can find information about it on google site:mit.edu
There are some goggles out there that can replace your monitor... that way you can buy a mini LAN-party case which you can carry-on along with a pair of goggles...
** PLUS! THINK HOW COOL YOU'LL LOOK! **
Imagine, fencing whilst goggling, defeating TWO OPPONENTS at once!
In fact, you should buy one of those remote-porno suits so that you get the full gaming experience... you'll be a...
Slashdot Mirror
Hey... we can complain on slashdot all we like. If you do not like what is going on politically then you can voice your opinion with your i) vote and ii) communication to your representative.
I've been involved with communicating with senators/housereps before and its amazing what can happen if a lot of constituents get together and complain.
The links you need are below! Remember, in your letter be polite but to the point. Say that you hope that they will not support Author, Consumer, and Computer Owner Protection and Security (ACCOPS) Act of 2003. Explain that destroying this nascent technology, P2P, which has so much to offer would be a serious error. And that the interests of the few elite (hollywood) and corporate interests should not prevail over public interests.
Links to email representatives
Berman's contact page
Conyers webmail page
Write your house representative
RIAA's going down. down. down. down.
This is similar to research being done at MIT in the Computer Architecture Group by Martin Rinard and his graduate student Brian Demsky. They are building and researching ways to automatically detect and repair data structure errors so that if a programs data structures get corrupted their tool will repair the heap so the program can keep running.
There was related work done like this back in the day at AT&T but Rinard and Demsky have introduced automatic repair which, as you might imagine like this security idea, is scary to some people. Imagine a program that would have crashed due to some bug or malicious data mangling, now kept running by a tool... But the tool chooses the repair actions based on heuristics and specifications by the developer... takes some getting used to!
All of this stuff falls under fault tolerance... its pretty crazy to look at what the AT&T/Lucent Phone Switches do when they fail... they try a million different things to keep operating no matter what happens...
There are a couple of good user interfaces for Freenet; the best is probably FROST, which includes messaging and searching. look in the "tools" section of the freenet site.
I'll check this out. But correct me if I'm wrong... we should be pushing frost to newbies not directly to freenet... If you send some novice to freenet and they don't get the intuitive interface then they'll leave freenet and not get involved.
this is very similar to mozilla and the problem with trying to convince laypersons that standards-compliance is good...
So, at least I know frost now and know what to check out and (hopefully, upon review) suggest to people...
RIAA's going down. down. down. down.
I downloaded freenet a while ago and from a user-friendly standpoint it seemed like a nightmare. Why doesn't someone build a Napster-esque front-end to freenet to help catapult the network into a reasonable market??
The kiddies (read everyone) can get their movies/music while providing bandwidth and storage for the rest of freenet's uses as well...
If I'm way off base, please inform me why...
RIAA's going down, down. down. down.
If the Apache developers simply want to fix the bugs, they can use the Defect Report. If they want conduct a brutal purge of their contributors, they can use the Metric report.
Any developer knows that code that crashes is rarely the code that contains the defect. If this were the case then the bug would have been found long ago because its faultly behaviour would have presented itself immediately. Difficult bugs (those probably found by this test) are those that start somewhere in the code but do not surface until much later, masking their true identity.
That being said, certainly a list of crash sites may provide hints as to where to look for the real bug.
I guess the next question is: why isn't anyone one in your compilers group doing anything to correct that problem? Or libc? If you think the existing code is crap, then release your superior alternative and become an open source diety.
that certainly makes sense, but unfortunately we're here to do research and at the current moment we're more interested in pointer analysis, escape analysis, ownership types, modelling, fault-tolerance transformations or tools. We work all week on this sort of thing and we generally don't have time to spend rewriting code that mostly works... as hard as it is to mess with their code, its certainly a lot more work to rewrite it... of course we do have our own version of java... but that makes sense because C is a mess anyway and at least we can work to save/improve java
if everyone benchmarked with open source compilers, there would be none of the shady benchmark-specific optimizations you'd expect to see in proprietary compilers. Everything would be above the table.
... how ugly the gcc code is...
have you ever looked at the GCC code? i work with the compilers group at my university and the running joke is how shoddy gcc is
you gotta remember sometime open source software is just a hodge podge of hacks thrown together.. nobodies ever bothered to refactor gcc so that its design is consistent, modular, extensible and readable...
a lot of the systems code you find out there (don't get me started on libc!!!) is crap..
plan crap
so point is, if you want to get a decent compiler for your chip porting gcc is a possibility but its code is mangled and unintuitive. nobody in their right mind (certainly not intel) is going to abandon their nice compiler for the mess that is gcc
man. that movie rock'd... i was a preteen and man mario 3 was SOOOO cool... hahahah.. remember those dinosaurs in the movie? i was driving from la to las vegas and saw them!! (either that or i was driving from l.a. to palm springs and saw them... anyway... they are much smaller now that i am an adult...
that movie rocked so much... remember the dad played link all night... hahah... that's what my dad did... i used to wake up and he would be bleary eyed having played legend of zelda all night long...
the good old days!!!
they don't make em like that anymore!!! even doom doesn't compare to the awesome time i had with legend of zelda and final fantasy...
for about four years my parents unplugged the TV. that was basically 8th grade through most of junior year of high school. and to be quite frank those are still my most productive years. i wrote more code and learned more outside of school during those years than i have learned on my own for the last 6... crazy. and i'll add one more thing, the thing that brought my incredible self learning to end was first college applications and then college when i was forced to sit down and be taught rather than exploring and teaching myself...
...
now i certainly played video games during that period so i wasn't completely immune to imitated violence completely, but i certainly kept out of trouble
TV rots the mind... specially in the crucial early years... if your typical day is get home watch 2-4 hours of TV than you are falling behind your potential...
crazy thing is now i use the internet like the TV. i have my "channels" (websites) that i check often, don't really stray that far. and i check them constantly even if nothing has changed. i waste so much time with the internet its stupid. don't get me wrong some things i do are impossible without the internet and when i do use it to research its fantastic...
so i think what's happened to TV will happen to the internet... most content in the hands of a few corporates and nothing really "on" even though we have tons of channels
Yeah yeah... 13$ is about the price of a CD... so whatever you don't feed it right back into the machine that is the RIAA... instead go donate it to a good cause like the couple below (no affiliation)
boycott-riaa.com
digital-consumer.org
do something useful and fight this idiotic RIAA crap!
Making this mandatory, in my opinion, goes against everything that open source stands for - choice. To not keep choices as free as possible to choose whatever is the best solution - be it proprietary or open - defeats the entire purpose of the choice open source provides.
... lets start thinking about using open source" and had much happen in terms of adoption because then people would stick with what they are used to (which is getting forced fed microsoft)
I may be wrong, but I seem to remember the Brazilian economy not being that hot. That being said the *mandatory* switch could just be a cost cutting decision... Perhaps the 20% that the decision leaves open to choice (commercial or open source) is that window which is for the small amount of situations where commercial would be preferable...
I don't think that the government could have said, "yeah
just an opinion
Somebody correct me if I'm wrong (I can certainly count on that around here...) but I thought it was pretty widely accepted that the Dvorak keyboard being faster or better is a myth.
Dvorak is not crap. When people watch me type they usually comment that my fingers hardly move. I watch people type on a qwerty and their fingers are all over the place for most words. Dvorak is optimized for the english language and most words can be typed on the home row. (~1600 to be specific).
About the military (lack of) adoption. The military found that learning dvorak took about 50 hours to reach proficiency while learing qwerty took several weeks. I believe the legend is that they would have switched but there was corporate pressure for the typewriter makers.
(Remember, qwerty was originally developed to prevent the typewriter from getting mechanically stuck... not efficiency for typing)
My only problems with dvorak is that it isn't optimized for c/java code because the brackets and some other characters are kinda a bitch to get at. for that there are emacs key bindings and kinesis keyboard macros. though typing in a language like lisp/scheme or a more verbal language (more reserved words, like vhdl/vb/) is a delight because most of the typing done is done typing words.
radical like one of those Logitech/MS 'natural' keyboards
natural keyboards are crap. check out a real ergonomic keyboard [kinesis-ergo.com]. Natural keyboards have positive wrist angle which is really bad for you. With the kinesis, not only do my fingers move less with dvorak, but the kinesis eliminates any need for wrist swivel.
A room full of guys at an event called "nerdsexfest" ... I don't even want to know what part of the fest involved sex.
:)
Ha ha.
You are right. It certainly does sound odd! Well, the explanation is quite straightforward:
nerd - we are nerds
fest - its a party
nerd + sex + fest - nerds having nerdsex (gaming)
ok... we're really nerdy!
i used to throw parties when i was in highschool called "nerdsexfests" where 15 or so of my friends would come over and we would network and play doom, doom2, warcraft, etc. etc. i remember our first one was a little iffy because we had to go to fry's electronics to buy ethernet cards (BNC no less!) to outfit 80% of the computers my friends bought (we returned the gear the day after!!)
anyway, these nerdsexfests grew longer and longer. we did a two once and i'd say the most important thing about having a long lan party is *pace*...
Pace your playing (don't stay up *all* night), pace your food (junk food all day => feel shitty, want to leave)
We often interleaved playing actual sports to get our blood flowing...
and of course, there is nothing like good ol' loud techno blasting to keep everybody psyched...
pace, my friend
I attended a talk by the head of the RLE lab at MIT a few weeks back. They are working on quantum entanglement and quantum teleportation as means of delivering quantum information over classical "internet" networks. The hitch is that they need an entanglement source to distribute entangled electrons to both ends of a connection...
am not complaining about a penalty. But why so much for EACH offense [of calling a number on the do-not-call list]? Is $11,000 arbitrary, or is there some reasoning behind it? It just seems like a big contrast with the couple hundred dollar fine at the State level.
don't listen to the other posts. 11,000 is calculated by an equation like this.
11,000 x
(expected number of callers that report them)
=
(money made per call on average) x
(number of calls)
that number, i suspect, is something like what they have set up. therefore, if a company ignores the list, they can't make a profit because, even though these numbers that are blacklisted are far and few between, if they ignore the list they will be fined often enough to eat their profits...
otherwise, they'd just ignore the list... a good example of this is car companies who decide based on equations whether to recall cars based on the probability of the crashes and the cost of the settlements (think "Fight Club")
I don't think you understood the article. I watched this class take place and it was drastically different than anything else I've seen... of course other classes at MIT related things to real world situations and provide examples, but this class is also about getting an *intuitive* understanding of the material...
about the no-theory objection... theory comes much easier once you have a practical understanding of a system. it is much harder to learn theory (think, "why the hell do i need to know algebra" in grade school) if you have no idea *WHY* you need to know it!
thank god.... from a developer standpoint having to have 'n' different database table entries for all the countries you support is a pain in the ass...
most of the classes i take provide lecture notes on the web in some form. i usually find that for these types of classes there is no need to take notes. it is far better to just listen intently. using a computer in class usually means you aren't paying attention... and small devices are useless for note taking at any decent speed.
as for a computer, i definitely suggest a laptop. if you are in a dorm i'd suggest a laptop-lock so that you don't have to worry about it getting stolen (still possible, but less likely)... i'd say personall, get a nice mac ibook, they work and they're simple. and with OS10 you get a nice bsd core...
for most classes all you'll have to do is write, code, or surf. you can use anything to do that.
PDA's are a waste of time, unless you can check email on them. you will never do serious work on a PDA as the display is rediculous...
u
>> What you really mean is "with coinage denomination systems which do not satisfy the greedy choice property, finding optimal change is non-trivial".
actually your statement is a superstatement of mine...
with denominations that do not divide evenly into each other it is non-trivial to find the optimal change for a given transaction.
..., c_k$, such that $\Sigma_{i=0}^k = n$ where $n$ is the amount of money in cents to change. Assume that we remove the coin with the largest value. The remaining coins, $c_2, ..., c_k$, represent the solution to the sub problem of changing $(n - c_1)$. If $c_2, ..., c_k$ is not optimal there exists another set of coins for this subproblem, $x_2, ..., x_k$, such that this solution has fewer coins. However this is a contradiction because we can now form a solution for the original problem, $n$, by combining $c_1$ with $x_2, ..., x_k$ that has a smaller size than the original optimal problem. This is a contradiction and hence $c_2, ..., c_k$ is an optimal answer to the subproblem and therefore the coin changing problem exhibits optimal substructure.
..., C(n-d_k)\}$.
whereas with the US denomination (and most denominations are designed for this reason) you can use a greedy algorithm to give back change (always choose the largest coin possible, repeat) and you are guaranteed to be giving back the fewest coins.
you can prove that a greedy algorithm provides an optimal solution if the problem has optimal substructure and the greedy choice property.
To prove optimal substructure consider a collection of coins for an optimal solution, $c_1,
To prove the greedy choice property we must show that a globally optimal solution can be arrived at by making a locally optimal, this is, greedy, choice.
For this particular set of American denominations we can prove the greedy property with a proof by contradiction. If the greedy choice were not optimal there would be an optimal collection such that:
1. some set of dimes, nickels, pennies added to more than 25 cents or
2. some set of nickels, pennies added to more than 10 cents or
3. some set of pennies added to more than 5 cents
However, all of these situations are impossible. If some set of pennies add to more than 5 cents, simply replace 5 pennies with a nickel (the greedy algorithm is better). If some set of nickel and pennies add to more than 10 cents and if there are two nickels, replace them with a dime; If there are a nickel and the rest pennies,
replace a nickel and 5 pennies with a dime. The same holds for a quarter. If three dimes, replace it with a quarter and a nickel. If it's two dimes and nickel/pennies, replace it with a quarter. And so on... The property of the coins that results in the greedy property is that each coin denomination divides evenly into the next larger coin denomination. Therefore each larger coin denomination that is removed must be replaced by at least two additional coins.
With non-even denominations you are required to actually search an n^2 space for the correct set of denominations. in fact, the algorithm is:
$C(n) = 1 + min \{C(n-d_1), C(n-d_2),
Additionally, $C(n) = 0$ for $n = 0$. We can ignore $n 0$ are we just define $C(n 0) = \infty$. By building the array in time/size $\Theta(nk)$, and keeping track at each step which value of was chosen for the minimum, then we can list the coins by tracing backwards through these recorded values. This augmentation takes no additional time since it can be done during building the array in time $\Theta(1)$.
So, basically you've changed the problem from a linear time algorithm in the amount of change to a quadratic time algorithm in the amount of change...
GOOD LUCK WALMART EMPLOYEES!
big deal. we drop twice that into the charles river for the naive freshmen each year at MIT... i'm sure you can find information about it on google site:mit.edu
I'm sooo funny!
There are some goggles out there that can replace your monitor... that way you can buy a mini LAN-party case which you can carry-on along with a pair of goggles...
...
n g- Fool
** PLUS! THINK HOW COOL YOU'LL LOOK! **
Imagine, fencing whilst goggling, defeating TWO OPPONENTS at once!
In fact, you should buy one of those remote-porno suits so that you get the full gaming experience... you'll be a
Walking-Action-Cyber-Killing-Opponent-Functioni
--otherwise known as a--
WACKOFF
(for short)
*******
Never underestimate the power of the wang... WA WA WA WANG!
> * How dare they call it The Two Towers after 9-11.
i'm guessing your joking because the book was called that a long time before 9-11....
and... even if you did realise that, there is no point in renaming, readjusting, realigning anything in acknowledgment of the terrorist actions...
i still like the twin towers... lets not make them go away too soon...