Friday, November 25, 2016

The other-worldliness of CLRS algorithms

I'm teaching algorithms from Cormen, Leiserson, Rivest, and Stein, which is the current standard for advanced algorithm courses. I'm working now on coding up their rod-cutting algorithm.

Supposedly we are solving a practical problem for a company, Serling Enterprises (Rod Serling pun), that buys long steel rods and wants to know how best to cut each rod to maximize revenues, given that different rod lengths sell at different prices.

CLR&S offer an algorithm that determines the best cuts, and then... returns the maximum revenue possible, using those cuts.

Can you imagine a manager at Serling actually using this code? She has a rod of 120 inches in length, and an list of prices for various rod lengths on the market. She feeds this items into the CLRS algorithm, and gets back the answer... $43.

Say what?! The manager wants to know how she should cut the rod. Yes, it is nice to know, also, what revenue she will get from those optimal cuts. But an algorithm that returns only the maximum revenue is useless to her! OK, if she makes optimal cuts, she can get $43 in revenue. But what are those optimal cuts?


No comments:

Post a Comment

George Berkeley, Common-sense Realist

"According to Berkeley, the perceived world is itself a language -- or, rather, a discourse in a language. Berkley intends this claim...