Slashdot Mirror

The U.S. Patent and Trademark Office has issued IBM a -- what the Electronic Frontier Foundation calls -- "stupefyingly mundane" patent on e-mail technology. U.S. Patent No. 9,547,842, "Out-of-office electronic mail messaging system" was filed in 2010 and granted about six weeks ago. Ars Technica reports: The "invention" represented in the '842 patent is starkly at odds with the real history of technology, accessible in this case via a basic Google search. EFF lawyer Daniel Nazer, who wrote about the '842 patent in this month's "Stupid Patent of the Month" blog post, points to an article on a Microsoft publicity page that talks about quirky out-of-office e-mail culture dating back to the 1980s, when Microsoft marketed its Xenix e-mail system (the predecessor to today's Exchange.) IBM offers one feature that's even arguably not decades old: the ability to notify those writing to the out-of-office user some days before the set vacation dates begin. This feature, similar to "sending a postcard, not from a vacation, but to let someone know you will go on a vacation," is a "trivial change to existing systems," Nazer points out. Nazer goes on to identify some major mistakes made during the examination process. The examiner never considered whether the software claims were eligible after the Supreme Court's Alice v. CLS Bank decision, which came in 2014, and in Nazer's view, the office "did an abysmal job" of looking at the prior art. "[T]he examiner considered only patents and patent applications," notes Nazer. The office "never considered any of the many, many, existing real-world systems that pre-dated IBM's application."

schwit1 writes: An ongoing two-year renovation of the University of Virginia's Rotunda has revealed a chemical lab designed by Thomas Jefferson that dates from the 19th century. Workers uncovered the early science classroom behind a wall on Monday, according to the university. The room was sealed in one of the lower-floor walls of the iconic Rotunda in the mid-1840s and protected from a fire in 1895 that destroyed much of the building's interior. The chemical hearth inside was originally built as a semi-circular niche in the Rotunda, with two fireboxes that provided heat. Brick tunnels underneath the building led fresh air to fireboxes and workstations, while ducts carried away the fumes and smoke. Students at the time worked at five workstations cut into stone countertops.

theodp writes "The Motley Fool reports that the Data Scientists at LinkedIn have been playing with their Big Data, ranking schools based on how successful recent grads have been at landing desirable software development jobs. Here's their Top 25: CMU, Caltech, Cornell, MIT, Princeton, Berkeley, Univ. of Washington, Duke, Michigan, Stanford, UCLA, Illinois, UT Austin, Brown, UCSD, Harvard, Rice, Penn, Univ. of Arizona, Harvey Mudd, UT Dallas, San Jose State, USC, Washington University, RIT. There's also a shorter list for the best schools for software developers at startups, which draws a dozen schools from the previously mentioned schools, and adds Columbia, Univ. of Virginia, and Univ. of Maryland College Park. If you're in a position to actually hire new graduates, how much do you care about applicants' alma maters?

Nerval's Lobster writes "Scientists have been using everything from supercomputing clusters to 3D printers to virtually recreate dinosaur bones. Now another expert is trying to do something similar with the ancient imperial villa built for Roman emperor Hadrian, who ruled from 117 A.D. to 138 A.D. Hadrian's Villa is already one of the best-preserved Roman imperial sites, but that wasn't quite good enough for Indiana University Professor of Informatics Bernie Frischer, who trained as a classical philologist and archaeologist before being seduced by computers into what evolved into the academic discipline of digital analysis and reproduction of archaeological and historical works. The five-year effort to recreate Hadrian's Villa is based on information from academic studies of the buildings and grounds, as well as analyses of how the buildings, grounds and artifacts were used; the team behind it decided to go with gaming platform Unity 3D as a key part of the simulation."

In an effort that took four months and $2000, instead of the quarter million dollars and two years they estimate it would have using conventional design methods, a group of University of Virginia engineering students has built and flown an airplane of parts created on a 3-D printer. The plane is 6.5 feet in wingspan, and cruises at 45 mph. I only wish this had been sponsored by Estes or Makerbot rather than the MITRE Corporation; it would be great for every high school or hobbyist group that can scrape together the printing time to have one of these on demand. (HT to Gaël Duval.)

Hugh Pickens writes "Thomas Jefferson, the author of the Declaration of Independence, whose signing we celebrate today, was considered an expert in architecture, civil engineering, geography, mathematics, ethnology, anthropology, mechanics, and the sciences. Although Jefferson never failed to acknowledge that in science he was 'an amateur,' Jefferson's home at Monticello was filled with examples of his scientific philosophy. An inventor and gadgeteer of great ingenuity, Jefferson's practical innovations or improvements on others inventions included: the swivel chair, the polygraph, letter press, hemp break. pedometer, mouldboard plow, sulky, folding chair, dumb-waiter, double acting doors, and a seven day clock. Throughout his life Jefferson experimented in agriculture with studies in crop rotation, soil cultivation, animal breeding, pest control, agricultural implements and improvement of seeds. Jefferson promoted science as President by recommending to Congress a coast survey to accurately chart the coast of America that later evolved into the United States Coast and Geodetic Survey. Jefferson's expert testimony before Congress led to the establishment of the Naval Observatory and the Hydrographic Office and Jefferson's report to Congress on a plan of coinage and weights and measures based on the decimal system was expanded into the National Bureau of Standards. Jefferson never applied for a patent, which was consistent in his belief in the natural right of all mankind to share useful improvements without restraint."

redwolfe7707 writes "Qubit registers have been a hard thing to construct; this looks to be a substantial advance in the multiple entanglements required for their use. Quoting: 'Olivier Pfister, a professor of physics in the University of Virginia's College of Arts & Sciences, has just published findings in the journal Physical Review Letters demonstrating a breakthrough in the creation of massive numbers of entangled qubits, more precisely a multilevel variant thereof called Qmodes. ... Pfister and researchers in his lab used sophisticated lasers to engineer 15 groups of four entangled Qmodes each, for a total of 60 measurable Qmodes, the most ever created. They believe they may have created as many as 150 groups, or 600 Qmodes, but could measure only 60 with the techniques they used.'" In related news, research published in the New Journal of Physics (abstract) shows "how quantum and classical data can be interlaced in a real-world fiber optics network, taking a step toward distributing quantum information to the home, and with it a quantum internet."

destinyland writes "Apple is closing in on Microsoft's share of operating systems among the computers of incoming freshmen at the University of Virginia, confirming earlier reports of an ongoing trend. A yearly survey shows that among 3,156 freshman who own computers, Microsoft's share is just 56% (down 6%), with Apple's share rising to 43% (up 6%), continuing a six-year pattern. In 2004, it was Microsoft 89% vs. 8% for Apple. 'It seems likely that the Mac-using students will outnumber their Windows cousins this school year,' notes one technology blog, citing a new study showing that 70 percent of college freshman are choosing the Mac. Other interesting data from the Virginia study: In 1997, 26% of incoming freshmen said they didn't own a computer, a number which has now dropped to 0. Laptops now comprise 99% of the computer population. And Linux use has dropped from a high of 2.5% in 2004 to a rounding error this year."

JumperCable writes "Ginkgo biloba has failed — again — to live up to its reputation for boosting memory and brain function. Just over a year after a study showed that the herb doesn't prevent dementia and Alzheimer's disease, a new study from the same team of researchers has found no evidence that ginkgo reduces the normal cognitive decline that comes with aging. In the new study, the largest of its kind to date, DeKosky and his colleagues followed more than 3,000 people between the ages of 72 and 96 for an average of six years. Half of the participants took two 120-milligram capsules of ginkgo a day during the study period, and the other half took a placebo. The people who took ginkgo showed no differences in attention, memory, and other cognitive measures compared to those who took the placebo, according to the study, which was published in this week's Journal of the American Medical Association."

wjousts writes "Several high-profile break-ins have resulted from hackers guessing the answers to secret questions (the hijacking of Sarah Palin's Yahoo account was one). This week, research from Microsoft and Carnegie Mellon University, presented at the IEEE Symposium on Security and Privacy, will show how woefully insecure secret questions actually are. As reported in Technology Review: 'In a study involving 130 people, the researchers found that 28 percent of the people who knew and were trusted by the study's participants could guess the correct answers to the participant's secret questions. Even people not trusted by the participant still had a 17 percent chance of guessing the correct answer to a secret question.'" Schneier pointed out years ago how weird it is to have a password-recovery mechanism that is less secure than the password.

theodp writes "When every student has a laptop, why run computer labs? That's a question schools have been asking themselves as computer ownership rates among incoming freshmen routinely top 90%. After only four freshmen showed up at the University of Virginia in 2007 without a computer of their own, the school decided that it's no longer worth the expense of running campus computer labs. Student computer labs have been a staple of campus life since the '60s. So what are the benefits that will be missed as other schools follow UVa's lead?" The university's report notes understanding that "that students need collaborative space where they can bring their laptops and mobile devices to conduct group work, especially as the curriculum becomes increasingly team- and project-based." One of the spaces formerly occupied by computer labs "has been transformed into a technology-rich collaboration area."

Lumenary7204 writes "According to the Register, Apple recently received US Patent Application No. 20080291629 for a 'liquid-cooled portable computer.' The filing describes a system where a 'pump ... coupled to the heat pipe is configured to circulate the liquid coolant through the heat pipe.' All claims of obviousness aside (after all, PC enthusiasts have been using liquid and phase-change cooling for years), the existence of the patent application seems to indicate that laptop manufacturers are in agreement with physicists and engineers who say we are running up against the practical limits of air-cooling such compact pieces of equipment."

An anonymous reader writes "Remember the Facebook News Feed privacy uproar? What about the Beacon scandal from late last year? Privacy activists are rallying around yet another major issue at Facebook, in which the company is secretly sharing user data with third parties. Researchers from the University of Virginia recently announced that in a study of the top 150 Facebook applications, more than 90% were given access to information that was not needed to function correctly. That Scrabble or Superpoke application you really like? Its developers get access to your religion, sexuality and home town. Facebook's position was summed up by Georgetown Law Professor Dan Solove, 'They seem to be going on the assumption that if someone uses Facebook, they really have no privacy concerns.' Do Facebook users deserve privacy? "

Roland Piquepaille writes "When oncologists meet a new patient affected by a cancer, they have to take decisions about the best possible treatment. Now, U.S. researchers have devised an algorithm which matches tumor profiles to best treatments. They've used a panel of 60 diverse human cancer cell lines from the National Cancer Institute — called NCI-60 — to develop their "coexpression extrapolation (COXEN) system." As said one researcher, "we believe we have found an effective way to personalize cancer therapy." Preliminary results have been encouraging and clinical trials are now planned."

Roland Piquepaille writes "We all want smaller and faster computers. Of course, this increases the complexity of the work of computer designers. But now, computer scientists from the University of Virginia are coming with a radical new idea which may revolutionize computer design. They've developed Tortola, a virtual interface that enables hardware and software to communicate and to solve problems together. This approach can be applied to get a better performance from a specific system. It also can be used in the areas of security or power consumption. And it soon could be commercialized with the help of IBM and Intel."

prostoalex writes "The Computer Science Department at the University of Virginia has published a comparative study of security in Java and .NET in Portable Document Format. DevMktg blog on MSDN summarizes the findings saying that due to careful design process, .NET presents security advantages over Java platform in several areas." From the article: "Where Java evolved from an initial platform with limited security capabilities, .NET incorporated more security capability into its original design. With age and new features, much of the legacy code of Java still remains for backwards compatibility including the possibility of a null SecurityManager, and the absolute trust of classes on the bootclasspath. Hence, in several areas .NET has security advantages over Java because of its simpler and cleaner design."

Chris Acheson writes "John Taylor Gatto is a former New York City school teacher. During his 30-year career, he has taught at 5 different public schools, has had his teaching license suspended twice for insubordination, and was once covertly terminated while on medical leave. He has also won the New York City Teacher of the Year award three times and the New York State Teacher of the Year award once during the final year of his career. The whole time he has been an outspoken critic of the school system. Nine years after leaving his career, he published The Underground History of American Education (full text available here), in which he puts forth his insider's vision of what is wrong with American schooling. His verdict is not what you'd expect: the school system cannot be fixed, Gatto asserts, because it has been designed not to educate. Skeptical? So was I." Read on for the rest of Acheson's review. The Underground History of American Education author John Taylor Gatto pages 700 publisher Oxford Village Press rating 9 reviewer Chris Acheson ISBN 0945700040 summary A damning look at the institution of modern compulsory schooling and the factors which brought it about.

The true purpose of schooling, according to Gatto, is to produce an easily manageable workforce to serve employers in a mass-production economy. Actual education is a secondary and even counterproductive result since educated people tend to be more difficult to control.

Over the course of the book, Gatto exposes many of the individuals, organizations, and crises (both real and manufactured) that helped to make our public school system what it is today. Such architects as Rockefeller, Carnegie, Ford, and a handful of teaching and management experts sought to benefit directly from a dumbed-down citizenry. Others contributed in a naive attempt at Utopian social engineering, mostly unaware of the harm that they were doing. There was never any master plan, though. The author puts it best:

With conspiracy so close to the surface of the American imagination and American reality, I can only approach with trepidation the task of discouraging you in advance from thinking my book the chronicle of some vast diabolical conspiracy to seize all our children for the personal ends of a small, elite minority.

Don't get me wrong, American schooling has been replete with chicanery from its very beginnings: indeed, it isn't difficult to find various conspirators boasting in public about what they pulled off. But if you take that tack you'll miss the real horror of what I'm trying to describe, that what has happened to our schools was inherent in the original design for a planned economy and a planned society laid down so proudly at the end of the nineteenth century. I think what happened would have happened anyway-without the legions of venal, half-mad men and women who schemed so hard to make it as it is. If I'm correct, we're in a much worse position than we would be if we were merely victims of an evil genius or two.

Gatto maintains throughout the book that all individuals have an innate curiosity and desire to learn. Examples are given in the first chapter of prominent historical figures who prospered with little or no formal schooling. But I found the examples of desire for substantive education on the part of "the masses" to be most compelling:

When a Colorado coalminer testified before authorities in 1871 that eight hours underground was long enough for any man because "he has no time to improve his intellect if he works more," the coaldigger could hardly have realized his very deficiency was value added to the market equation.

The real function of the school system is not to empower people by giving them knowledge, but to crush this instinct toward self-improvement before it makes the workers too independent and troublesome. Another compelling example is the "Jewish Student Riots" described in chapter 9:

Thousands of mothers milled around schools in Yorkville, a German immigrant section, and in East Harlem, complaining angrily that their children had been put on "half-rations" of education. They meant that mental exercise had been removed from the center of things.

The book does have a few problems. Gatto is by his own admission somewhat casual about citing his sources. This is important because there are some assertions made that many will find dubious. For example:

Looking back, abundant data exist from states like Connecticut and Massachusetts to show that by 1840 the incidence of complex literacy in the United States was between 93 and 100 percent wherever such a thing mattered.

This would be a great fact to toss out when trying to convince someone that schooling is unnecessary. But where does this statistic come from? What does "wherever such a thing mattered" mean? Some readers may be willing to simply take Gatto's word for it and accept this assertion, but skeptics will be left unsatisfied. According to historical census data from 1840, the national average literacy rate for white adults was indeed approximately 93%, and the literacy rate for white adults living in Connecticut was 99.67%. Why not simply say that the statistic refers to white adults? The omission hurts the author's credibility in the eyes of a skeptical reader.

The other thing that I found disappointing is that Gatto doesn't discuss solutions to the schooling problem as thoroughly as I wanted. Throughout the book examples are shown of educational methods which have worked well. As I read, I mulled these over, and anticipated that the final chapter (titled "Breaking Out Of The Trap") would be a comprehensive look at these methods and ways to promote their implementation. But that final chapter is mostly a collection of anecdotes. Gatto does provide a short list of positive suggestions and a promise to cover solutions more fully in a future book.

The picture that Gatto paints for us of our school system and society is frightening, but I also found it comforting to see evidence that ignorance and apathy are not the natural state of humanity. I found hope in the fact that things were once different. Having a clearly defined problem that can be solved is preferable to having a vague suspicion that something is wrong, but no clear idea what it is.

The ideas presented in Gatto's Underground History have the potential to change our society and our individual lives for the better. Even when we are trapped within the system, knowing how it works and what it is really up to can help us retain our wit and our humanity. If you are a student, if you are a parent, if you know or care about anyone who is in school, or even if you are just concerned about corporate and government control versus individual freedom, you need to read this book.

You can purchase The Underground History of American Education from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

ptorrone writes "The New York Times had a great story about Dr. Mark Whittle, a professor of astronomy at the University of Virginia who has taken the cosmic background radiation of the universe and made a series of sounds. The folks over at Engadget made the sounds available in MP3s so you can listen to them on your computer, iPod or whatever. Also, If you'd like to read more about Dr. Mark Whittle's work visit his site, there are a lot of presentations and information regarding Big Bang Acoustics."

nate writes "Convinced your favorite programming language provides unbeatable productivity? Convinced you and your friends are world-class programmers? If so, we're providing you the opportunity to prove it! We are pleased to announce the 7th ICFP Programming Contest to be held in conjunction with ICFP 2004. All programmers are invited to enter the contest, either individually or in teams; we especially encourage students to enter. You may use any programming language (or combination of languages) to show your skill." Read on below for the details.

"On Friday, 4 June at 12:00 Noon (EDT), we will publish a challenge task on the Web site and by e-mail to the contest mailing list. Teams will have 72 hours until Monday, 7 June 12:00 Noon (EDT) to implement a program to perform this task and submit it to the contest judges. We have designed the contest for direct, head-to-head comparison of language technology and programming skill. We have a range of prizes including cash awards and, of course, unlimited bragging rights for the winners.

Previous contests included: 2003, 2002, 2001, 2000, 1999 and 1998."

RobotWisdom (Jorn Barger) writes "Imagine if William Gibson wrote a James Bond adventure in which a sexual tigress seduces Bond into a Caribbean political crisis, requiring a nighttime scuba-dive into a sunken treasure-wreck, and then a voodoo ceremony that reads like a nightmare acid trip. Now replace James Bond with an "overeducated hick" atheist literature professor from Minnesota. And target the writing to intelligent adults, rather than adolescents. That should give you an idea of the latest novella from Robert Stone, Bay of Souls: A Novel." The book is compact, and so is the rest of Barger's review (below). Bay of Souls: A Novel author Robert Stone pages 256 publisher Houghton Mifflin Company rating 9 reviewer Jorn Barger ISBN 0395963494 summary Classy, intelligent adventure for William Gibson fans

The William Gibson comparison is only a little farfetched -- Gibson acknowledges Stone's "paranoid fiction" as the stylistic inspiration for Neuromancer, so if you liked that writing style, you owe it to yourself to try reading Stone. But his books aren't science fiction, and they aren't just adventure stories by any stretch of the imagination.

Stone's been living on the edge of the counterculture since before Ken Kesey's famous 1964 Magic Bus trip. (In fact, his next book will be a memoir of his adventures with Kesey & Co.) His 1974 tour-de-force Dog Soldiers was about southern California drug smugglers in the Vietnam era. His 1981 A Flag for Sunrise was a painfully realistic study of central American political corruption. And 1998's Damascus Gate explored dozens of flavors of religious fanaticism in present-day Israel. [more background]

But Stone's style is the bedrock these are all anchored by. On the one hand, he uses his style to give a gritty, macho, hardboiled detective-story authenticity, but at the same time he's aiming much higher, into the realm of the literary classics (two of his novels qualified for Harold Bloom's exclusive Western Canon of all-time greats). He likes to weave in lots of casual allusions to interesting-but-obscure historical tidbits (I've started compiling online annotations for Damascus Gate and now for Bay of Souls as well).

You can read a sample online [more] to get a sense of Stone's writing, although that first chapter just shows "the calm before the storm," as the hick professor goes on a short hunting trip, and encounters a tragicomic loser who becomes a recurring motif in the book:

...He was struggling with the odd wheelbarrow across which he had slung his prize deer. It was a thing full of seams and joins and springs. Though it appeared altogether large enough to contain the kill, it could not, and its inutility was the source of his sobs and curses and rage and despair. And as the unfortunate man shoved and hauled, pushed and pulled his burden, covering the ground by inches, the extent of his rage became apparent. To Michael, observing from the tree, it was terrifying ...

This short book (250 pages) isn't for everybody, but I strongly recommend it to Gibson fans who feel curious to explore beyond sci-fi.

You can purchase Bay of Souls from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

thomasmd writes "Yahoo has an article describing the results of a new study by American and Scottish researchers that looked at the number of deaths by drowning of cetaceans (fishlike sea mammals) caught in fishing nets. Their alarming estimate was that more than 1000 cetaceans die every day from net entanglement."

user555 writes "The RIAA and MPAA have seen Palladium as a way to prevent piracy. But this article argues that ironically Palladium may actually make P2P piracy more widespread (PDF). They argue that the security features of Palladium could be used to create P2P networks that are more resistant to attacks from content owners."

Slashback tonight with followups on previous stories about tablet computers, the fire at Mt.Stromlo, and Mandrake Linux -- read below for the details. Update: 01/24 00:08 GMT by T : One more update added below, regarding the post earlier this week on nVidia's new video card.

The silver lining.dragonsister writes "Regarding the recent slashdot story on Mount Stromlo Observatory being hit by fire, it seems the damage is not nearly as extensive as it might have been. The Australian National University has posted details here. In particular, the office buildings were spared, meaning that the work of staff and students is safe, and the many years worth of data collected should still be usable. The main question remaining in my mind is whether or not there were backups of the data on the computers that were actually located in the telescope buildings themselves, as these contained information crucial to the interpretation of some of the data. The importance of off-site backups has just been demonstrated. Everybody backup now!"

And blakduk writes "We were able to enter the site and retrieve computing equipment that survived the fire. This enabled us to set up our servers and have all staff back on-line within 24 hours."

Other than that, how was the parade? Back in November, I posted an article about the DocuNote, an inexpensive tablet PC available with Linux. According to richardbondi , maybe "cheap" would be a better word. He writes:

"I bought one, it arrived today. It was clearly used, not new, and didn't work. If you tilted it, it hung. I gave up after a dozen reboots. Only purchasable from www.microsono.com, where all sales are final.

The handwriting recognition software turned out to be trialware.

And although the stepupcomputing.com site says it works with Windows 2000, it came with a note that said now it has to be OEM installed.

One user's bad experience -- bad hardware, deceptive advertising re software."

Looks nice over two monitors, too. Znonymous Coward writes "Mandrake is trying to prove it's not dead yet. Yesterday[Note: the 19th, that is], they released Beta 2 of Mandrake 9.1. You can get the 2 ISO images from the usual mirrors." There's a (critical but mostly positive) review of this 2nd beta running at DistroWatch, too.

Once this starts it always gets messy. Per Hansson writes

"Yesterday we at Techspot posted a Interview with Nvidia plus high-resolution pictures of the Geforce FX.

A few sites rightfully claimed that this material had been stolen from Nordichardware however this was not the case, we interviewed Nvidia at the same time and therefore our Interviews looks so similar."

Anton Nilsson, assistant editor in chief of Nordic Hardware writes, in contrast,

"... [I]t seems as if they have used my material as found here.

I've spoken to the TechSpot staff and the person who reported the news item to you and it seems as if they overheard me doing my interview with nVidia at Comdex. Since they didn't want to bug nVidia with the same questions again they later on read the interview at my page and then posted it on theirs. Still that doesn't make up a fair excuse in my opinion."

You'll have to make up your own mind on this.

bmooney28 asks: "After maintaining a single permanent email address through 8 years and five ISP's (via a forwarding service), I lost it all in a day. My first sign of trouble came when I found a message undeliverable email in my inbox containing hundreds of failed email addresses. Apparently, my email address had been pasted as the return address in a mass mailing similar to this one sent to hundreds of random recipients. This process repeated a few times over the next day or so, effectively blacklisting my email address on various master lists and adding my address to thousands of random address books (virus magnets). In the past, I have had a great deal of luck fighting off SPAM and other unwanted email via throwaway email addresses and preemptive email filtering. Now, the email address that I use to communicate with friends, former students, and coworkers around the world is useless. Have any of you ever found yourself in a similar situation? Are there any legal steps that I could take against this company?"

Creosote asks: "Concerns about piracy are no longer just for the big commercial media outfits. JSTOR, one of the major repositories and distributors of online versions of scholarly journals, has been hit by crackers taking advantage of open proxy servers to download about 51,000 articles from 11 JSTOR journals. Even nonprofit academic publishers rely on income from publications to exist, so the spectre of large-scale unauthorized copying is legitimately scary to them. In a letter to librarians and publishers, the president of JSTOR notes that while the "threat of open proxies has been recognized for some time in the web community...it does not appear that network administrators, librarians, or content providers are aware that organized efforts are being employed to gain unauthorized access to restricted campus resources" through them. I work for a nonprofit publisher (a university press) that will soon be making peer-reviewed digital projects available online, and they can't all be given away for free, so this hits close to home. Are there better solutions than turning into an attack dog, ala the RIAA and the MPAA?"

foobar104 writes "Details are scarce, but SGI announced this morning that their prototype Itanium 2 system has demonstrated more than 120 GB/s to and from main memory on the STREAM TRIAD benchmark, which is the fourth best result in the world. For comparison, the Cray C90 sustains 105 GB/s, while an even larger Sun Fire 15K clocks a measly 55 GB/s. The interesting part? The system wasn't running IRIX, SGI's proprietary version of UNIX. It was running Linux. More information on STREAM TRIAD, including results from other systems, is available here. The system, incidentally, was an Origin 3800 straight out of manufacturing equipped with Itanium 2 processor modules. SGI will start selling the systems early next year."

Cryptographrix writes "Just came across this site, thought slashdot users should check it out, definately worth a read, has everything from the original Osborne portable computer to such memorables as the Altair...supposedly from the UVA staff's personal collection. Even has old (1950's and another board that looks like ESS3, maybe) telephone switching equipment."

Phil Bewig writes: "Results of the 2001 ICFP Programming Contest (previously mentioned at SlashDot here and here) have been announced. First place is to a program in Haskell, second place is to a program in Dylan, and the judges' prize is to a program in Erlang. The judges also named third place (ocaml) and fourth place (C) entries that were not awarded prizes. ICFP Programming Contest pages for prior years are available: 2000, 1999, and 1998."

gdon writes: "So you are the best and fastest coder in town? Take a chance to exhibit your skills and maybe win a prize at the 4th ICFP programming contest at the International Conference on Functional Programming. The programming challenge task will be published on July 26, 2001 at 15:00 UTC and program submission ends 72 hours later." Check out the previous contests: 1998, 1999, or 2000.

[cx] writes "There is one here at a U-Virginia college site. "

Reader John Regehr contributed this review of O'Reilly's Understanding the Linux Kernel, which goes into greater depth than most people have ever seen of the kernel source itself. (I wonder what it costs to look at the Windows source.)

Understanding the Linux Kernel author Author: Bovet, Daniel P. / Cesati, Marco pages 684 publisher O'Reilly & Associates rating 8.5 reviewer John Regehr ISBN 0596000022 summary The guts of the kernel, labeled and explained.

Although isolated pieces of operating system internals are usually not difficult to understand, learning how a significant portion of a real OS works is a daunting task: there's a lot of code, some of it is complicated, and some of it operates under obscure assumptions that can be difficult to figure out by reading the sources. Two of the best existing books about OS internals have explained either a simplified but working OS (Tanenbaum's Minix book) or a real, but very small OS (Lions' book on Unix v6). Although these systems have the advantage of being easier to understand, there's an important reason why one might want to study Linux internals instead: Linux is currently relevant, it's likely to be around for a while, and any code you write can potentially be used by thousands of people the day after tomorrow. So, taking it as a given the a book about Linux internals is a good thing, how good is this one? Happily, it's very good - better than any previous such book that I've seen (Rubini's Linux Device Driver book is also excellent, but it has a limited scope).

Understanding the Linux Kernel is good for several reasons. First, the authors have included quite a bit of explanatory material that isn't specifically about Linux - it's the kind of thing one would find in a good undergraduate OS textbook. This helps the reader link explanations of pieces of code to the abstract OS functions that they implement. Second, the authors have chosen a good level of abstraction: core kernel algorithms are explained in text, supplemented with short code sequences (simplified to remove optimizations) for important routines. Flowcharts are used to explain components with complex control flow, and tables and other diagrams are used when appropriate. Finally, the book is well arranged and well written, and there's an auxiliary index at the end that maps symbols mentioned in the book to source code files.

There are a few things I don't like about this book. Most importantly, there is no discussion of the network stack. As the authors say, this is a subject for another book, but by leaving out one of the most interesting and relevant parts of the kernel they are limiting their audience. A second drawback of this book (and of any Linux kernel book) is that since it seems to take about as long to write a good book as it does to write a major version of the Linux kernel, as I write this review it's about to become obsolete - it describes Linux version 2.2. However, at the end of each chapter there's a short note about things that are done differently in version 2.4. This will help preserve the relevance of the book after 2.4 comes out and, maybe more importantly, it gives the reader a sense of what parts of the kernel are under active development and what parts have become mature and stable.

Although Linux is very much in the Unix tradition, many details have changed. For example, early Unix kernels used simple algorithms (such as linear searches) and fixed table sizes. Modern Linux kernels, on the other hand, avoid arbitrary limits on the numbers of many kinds of internal OS objects, do not use linear searches when the number of objects to be searched is potentially large, and use amortized algorithms in many places. In all parts of the kernel, any special knowledge about the way that OS services will be used is exploited in order to improve average-case performance. For example, the slab memory allocator makes use of the fact that kernels often allocate many objects of the same size in order to reduce memory fragmentation and to avoid creating hot spots in the data cache. These algorithmic optimizations are much more pervasive (and much more effective) than micro-optimizations such as tuning register allocation or packing flags into the bits of a memory word - they're what make Linux useful in large-scale server environments where high throughput is critical. However, they also make the kernel code quite a bit more difficult to understand.

Given this complexity, it seems reasonable to ask who needs to read this book and how well does it suit their needs. Three groups of people come to mind. First, potential kernel hackers will find this book to be a good overview of different parts of the kernel. Of course, for people like this a book is no substitute for lots of code reading, but it's a good start. Another potential audience is the group of people who need to understand the kernel in order to extract high performance from it; for example, authors of databases or network servers. This group's needs are well served by this book: the authors often point out why certain heuristics were chosen - this may help people whose applications have run afoul of a resource allocation policy that was designed to serve a different class of applications. Finally, computer science students interested in the internals of a real OS would do well to read this book. It would make a good supplement to a standard OS textbook in an introductory class on operating systems. However, Linux appears to be far too large to understand in its entirety in a single semester: classes that attempt to do this should use a teaching OS like Minix. To benefit from this book, readers should have knowledge equivalent to a couple of semesters of computer science: a basic understanding of programming, of the services an OS provides to user-level programs, and of the hardware mechanisms used by an OS.

This is a good book. The authors have cracked open a large collection of code that's currently very relevant. If they are in for the long haul and release revised books in a timely way, then this will likely become and remain the definitive explanation of Linux internals.

The web site for the book is here.

You can purchase this book at Fatbrain.

On May 23 we requested questions for Greg Lindahl, chief designer of the new NOAA Forecast Systems Laboratories massive Alpha Linux Cluster. Here are his answers. Fascinating stuff for people interested in big-time parallel computing.

Who Else?
(Score:4, Insightful)
by Alarmist

You've built a large cluster of machines on a relatively pea-sized budget.

Are other government agencies going to duplicate your work? Have they already? If so, for what purposes?

Greg:

There are a lot of government agencies building large clusters, such as the Department of Energy's Sandia National Lab, which has the 800+ processor CPlant cluster today, with another 1,400 processors on the way. Like FSL, they use their cluster for scientific computing. The well-known Beowulf clusters started within NASA, another U.S. government agency.

However, the Forecast Systems Lab (FSL) system is a bit different from these other clusters: it's intended to be a production-quality "turn key" supercomputer, and it contains all the things supercomputer users are used to, such as a huge robotic tape storage unit (70 terabytes of tapes), and a fast disk subsystem (a bandwidth of 200 megabytes/second.) The FSL system is also much more reliable than your average cluster -- in its first three months of operation, it was up 99.9% of the time. During that time we had quite a few hardware failures (due to a power supply problems), but no work was lost, because of our fault-tolerant software.

Beowulf in General
(Score:4, Interesting)
by BgJonson79

How do you think the new wave of Beowulf clusters will affect all of supercomputing, not just forecasting?

Greg:

The kinds of problems that scientists solve have different computational needs. In the mid 1970's, the most cost effective machine to use for just about any problem was a Cray supercomputer. These days, desktop PCs far are cheaper per operation than the "big iron", so that's why this interest in clusters has sprung up. The availability of production-quality commodity clusters like the FSL machine is a new development in the field.

IBM already sells IBM's idea of a commodity cluster; it uses IBM's RS/6000 business servers as building blocks. I think commodity clusters can deliver far more bang for the buck as an IBM SP supercomputer, but then again I am a cluster evangelist.

In the beginning...
(Score:5, Interesting)
by zpengo

How did you come to be the project's chief designer? I'm curious to know the background of anyone who gets to work on such an interesting project.

Greg:

Well, let's see: I'm a dropout from an Astronomy PhD, and for fun I dress up in funny clothes (I'm the one in yellow) and play the hurdy gurdy. I've only taken one computer science class since I started college. I assure you that you're never going to meet anyone much like me in this field.

Seriously, I've worked in scientific computing for quite a while, and I've had a chance to work with a lot of people and learn from them. I was also helped quite a bit learning about distributed systems while working on IRC and later, the Legion distributed operating system. The art of designing a system like this is understanding the customer's needs, understanding what solutions are possible, and understanding what can actually be delivered, be made reliable, and hit the budget.

In addition, it's worth pointing out what this sort of project involves. Most of the interesting development parts are done by other people. Compaq designed the Alpha processor, and they and legions of Linux hackers provided Linux on the Alpha. Compaq supplied their extremely good compilers (FSL mostly uses Fortran.) Myricom supplied the interconnect and an MPI message-passing library which was optimized for their interconnect. HPTi provided the software glue that turned all this into a complete, fault-tolerant system. Without all these great building blocks, we would never have been able to produce this system.

The Future of the Control Software
(Score:5, Interesting)
by PacketMaster

I built a Beowulf-style cluster this past semester in college for independent study. One of the biggest hurdles we had was picking out a message passing interface such as MPI or PVM. Configuring across multiple platforms was then even worse (we had a mixture of old Intels, SunSparcs and IBM RS/6000's). What do you see in the future for these interfaces in terms of setup and usage and will cross-platform clusters become easier to install and configure in the future?

Greg:

We provided an easy-to-use set of administrator tools so that the Forecast Systems Lab (FSL) cluster can be administered as if it were a single computer. This is a fairly difficult to do if you have a big mix of equipment, but the FSL system will never become that complex. There's already been a lot of development of programs for administering large clusters of machines; they just tend to not get used by other people. I'll admit that I'm part of that problem; I took some nice ideas from other people's tools, added some of my own, and re-invented the wheel slightly differently from everyone else.

Beowulf Alternatives?
(Score:5, Interesting)
by vvulfe

Before deciding on a Beowulf clusters, what different options did you explore (Cray? IBM?), and what motivated you to choose the Beowulf System?

Additionally, to what would you compare the system that you are planning to build, as far as computing power is concerned?

Greg:

The company I work for, HPTi, is actually a systems integrator, so we didn't decide to go out and build our own solution until we had checked out the competition and thought they didn't have the right answer. For the computational core of the system, Alpha and Myrinet were much more cost effective than the Cray SV-1, the IBM SP, and the SGI O2000. A more cost-effective machine gives the customer more bang for their buck.

I'd compare the system that we built to the IBM SP or the Cray T3E, as far as computing power is concerned. Both are mostly programmed using the same MPI programming model that FSL uses, which is the main programming model that we support on our clusters.

Biggest whack in the head?
(Score:5, Insightful)
by technos

Having built a few small ones, I got to know quite a bit about Linux clusters, and about programming for them. Therefore, this question has nothing to with clusters.

What was the biggest 'WTF was I thinking' on this project? I'd imagine there was a fair amount of lateral space allowed to the designers, and freedom to design also means freedom to screw up.

Greg:

We actually didn't make that many mistakes in the design. We had some wrong guesses about when certain technology was going to be delivered -- the CentraVision filesystem (more about that below) for Linux arrived late, and we had to work with Myrinet to shake out some bugs in their new interconnect hardware and software. Our biggest problem with our stuff was actually getting the ethernet/ATM switches from Fore Systems to talk to each other!

Imagine ...
(Score:4, Interesting)
by (void*)

... a beowulf of these babies - oh wait! :-)

Seriously, what was the most challenging of maintenance tasks you had to undertake? Do you anticipate that a trade off point where the number of machines makes maintenance impossible? Do you have any pearls of wisdom for those of us just involved in the initial design of such clusters, so that maintaining it in the future is less painful?

Greg:

Hardware maintenance of the FSL machine actually isn't hard at all. If a computational node fails, we have a fault tolerance daemon which removes the failed node from the system and restarts the parallel job that was using that node. The physical maintenance of a few hundred machines actually isn't so bad; these Alphas came with three-year on-site service from Compaq. (Hi, Steve!)

More interesting than hardware maintenance is software maintenance. You can imagine how awful it would be to install and upgrade 276 machines one by one. Instead, we have an automated system that allows the system admin to simultaneously administer all the machines. We suspect that these tools could scale to thousands of nodes; after all, they're just parallel programs, like the weather applications that the machine runs.

Question about maintenance.
(Score:5, Interesting)
by Legolas-Greenleaf

A major problem with using a beowulf cluster over a single supercomputer is that you now have to administer many computers instead of just one. Additionally, if something is failing/misbehaving/etc., you have to determine which part of the cluster is doing it. I'm interested a] how much of a problem this is over a traditional single machine supercomputer, b] why you chose the beowulf over a single machine considering this factor, and c] how you'll keep this problem to a minimum.

Besides that, best of luck, and I can't wait to see the final product. ;^)

Greg:

You haven't described a problem, you've described a feature.

We've provided software that allows administration of the cluster as if it was one machine, not many. This software also allows FSL to test new software on a portion of the machine, instead of taking the whole thing down. The software on the machine can also be upgraded while the machine is running, instead of requiring downtime.

Since the hardware is fairly simple, it's actually quite easy to find a misbehaving piece of hardware. And in this kind of system, a hardware failure only takes out a small portion of the machine.

For example, on an SGI O2000 or similar large shared-memory computer, a single CPU or RAM chip failure takes out the entire machine. The interconnect on an O2000 is not self-healing like the interconnect we used, Myrinet. These features make a cluster more reliable than a "single machine".

Why alpha?
(Score:5, Insightful)
by crow

Why did you choose Alpha processors for the individual nodes? Why not something cheaper with more nodes, or something more expensive with fewer nodes? What other configurations did you consider, and why weren't they as good?

Greg:

We did a lot of benchmarking before settling on Alphas for this particular system -- in general we're processor agnostic, happily using whatever gives the highest performance for each customer. We could have bought more nodes if we had gone with Intel or AMD, but the total performance would have been much lower for this customer.

The Future of Scientific Programming?
(Score:5, Interesting)
by Matt Gleeson

The raw performance of the hardware being used for scientific and parallel programming has improved by leaps and bounds in the past 10-20 years. However, most folks still program these supercomputers much the same way they did in the 80's: Unix, Fortran, explicit message passing, etc.

You have worked in research with Legion and in industry at HPTi. Do you think there is hope for some radical new programming technology that makes clusters easier for scientists to use?

If so, what do you think the cluster programming environment of tomorrow might look like?

Greg:

Actually, in the end of the 1980's, Unix was new in the supercomputing scene, and most sites still used vector machines. It's only in the 1990s that microprocessors and MPI message-passing have become big winners. And that's because of price-performance, not because it's easier to use than automatic vectorizing compilers. Ease of use for supercomputers reached its peak around 1989.

I do think there's hope of new approaches, however. One great example is the SMS software system developed at FSL. This software system is devoted to make it easy to write weather-forecasting style codes, and involves adding just a few extra lines of source code to parallelize a previously serial program. The result can sometimes efficiently scale to hundreds of processors, still can run on only one processor, and FSL has enough experience with non-parallel-programming users to know that they can change working programs and end up with a working program. (If you've ever heard of HPF, then this is somewhat like HPF, except it actually works.)

Today, the best programming environments are ones that hide message-passing, either in specialized library routines or using a preprocessor approach like SMS. By the way, Legion allows you to program distributed objects with minimal source code changes. I expect more of the same thing in the future.

My crystal ball isn't good enough to tell me what the next revolutionary change will be. I'm actually pretty happy with the evolutionary changes I've seen recently.

Job management
(Score:4, Interesting)
by gcoates

One of the weaknesses for beowulfs seems to me to be a lack of decent (job) management software. How do you split the clusters resources? Do you run one large simulation on all the CPUs, or do you run 2 or 3 jobs on 1/2 or 1/3 of the available CPUs?

Is there provision for shifting jobs onto different nodes if one of them dies during a run?

Greg:

We use the PBS batch system to manage jobs; it handles splitting the cluster resources among the jobs. At FSL, there are typically 10+ jobs running at the same time; the average job uses around 16 out of the 264 compute nodes.

If a compute node dies during a run, a HPTi-written reliability daemon marks the dead node as "off-line" and restarts the job. The user never knows there was a failure.

Weather forecasting in general.
(Score:5, Interesting)
by Matt2000

Ok, a two parter:

As I understood it weather models are a fairly hard thing to paralleliz (how the hell do you spell that?) because of the interdependence of pieces of the model. This would seem to me to make a Beowulf cluster a tough choice as it's inter-CPU bandwidth is pretty low right? And that's why I thought most weather prediction places chose high end super-computers because of their custom and expensive inter-CPU I/O?

Greg:

Weather models are moderately hard to parallelize; in order to process the weather in a given location, you need to know about the weather to the north, south, east, and west. For large numbers of processors, this does require more bandwidth than fast ethernet provides, and that's why we used the Myrinet interconnect, which provides gigabit bandwidth, and which scales to thousands of nodes with high bisection bandwidth, unlike gigabit ethernet.

As far as disk I/O goes, yes, most clusters are fairly weak at disk I/O compared to traditional supercomputers from Cray. We are using the CentraVision filesystem from ADIC along with fibre channel RAID controllers and disks. This is more expensive than normal SCSI or IDE disks, but provides much, much greater bandwidth for our shared filesystem.

Second part: Is weather prediction getting any better? Everything I've read about dynamic systems says that prediction past a certain level of detail or timeframe is impossible. Is that true?

Greg:

The quality of a weather prediction depends on a lot of things: the quality of the input data, which has gotten a lot better with the new satellites and other data collection systems recently deployed; the speed of the computer used to run the prediction; the quality of the physics algorithms used in the program, which have to get better and better as the resolution gets finer and finer; and the expertise of the human forecaster who interprets what comes out of the machine. All of these areas have limits, and that's why forecasts have limits.

What about a dnet type client?
(Score:5, Interesting)
by x0

I am curious as to whether (no pun intended...:)) or not you have ever done any testing to see if a distributed.net type environment would be useful for your type of work?

It seems to me that there are more than a few people who are willing to donate spare cpu cycles for various projects. At a minimum. you could concentrate on the client side binaries and not worry as mouch about hardware issues.

Greg:

Most supercomputers, like the FSL system, are in use 100% of the time doing real work. The biggest provider of cycles to distributed.net are desktop machines, which aren't used most of the time. Running distributed.net type problems on the FSL cluster is a bit of a waste, since the FSL cluster has a lot more bandwidth than distributed.net needs.

---------------

In closing, I'd like to thank Slashdot for interviewing me, and I'd like to point out that I got first post on my own interview -- perhaps the only time that this will ever happen in the history of the Universe?

jmobiusmaximus writes "Right next to the wormhole site on the BBC News page is an article about the results of the Boomerang project in Antarctica. This resulted in a new map of the 2.7K cosmic microwave background radiation, which is thought to be a remnant of the energy released in the Big Bang. The BBC News synopsis isn't bad, and has some links that will answer most "WTF?" questions. For those of you who have taken a little bit of physics, the original Nature article is better. This could have a large impact on our understanding of the universe's evolution and will probably be the source of much debate in the near future. "

John Regehr sent us an excellent review of Mastering Algorithims with Perl, another O'Reilly & Associates effort. Written by Jon Orwant, Jarkko Hietaniemi, and John Macdonald, this is a book designed to take your Perl to a new level of wizardery. Mastering Algo author Jon Orwant, Jarkko Hietaniemi, and John Macdonald pages 704 publisher O'Reilly, 08/1999 rating 8/10 reviewer John Regehr ISBN 1-56592-398-7 summary The intended audience is programmers who don't have a background incomputer science, who know at least some Perl. However, experiencedprogrammers who don't know Perl should have no trouble picking up thebasics of the language with this book and a copy of ProgrammingPerl. In The New Hacker's Dictionary under "superprogrammer," we read that "productivity can vary from one programmer to another by three orders of magnitude." I would argue that at least one of these factors of ten comes from the ability to quickly recognize what algorithms should be used to solve different parts of a problem and to find or write implementations of those algorithms that will result in an efficient program, given the available time and the characteristics of the problem. This ability is developed through experience and by understanding the highlights of the large body of algorithms and analysis of algorithms that has been developed to solve problems that occur over and over again in computer programs.

Mastering Algorithms with Perl is designed to provide the necessary background. It's structured like a traditional algorithms textbook: after describing some basic and advanced data structures (linked lists, trees, heaps, etc.), it has chapters about searching, sorting, sets, matrices, graphs, strings, and some related topics. After the introduction and discussion of data structures, the chapters are relatively independent and could be read in any order. The authors provide plenty of cross-references as well as pointers to books that describe individual subjects in more detail.

The intended audience is programmers who don't have a background in computer science, who know at least some Perl. However, experienced programmers who don't know Perl should have no trouble picking up the basics of the language with this book and a copy of Programming Perl. Also, computer scientists can often use a review of algorithms, and the CPAN pointers are very useful. So, I would go so far as to say that this book would enrich any programmer's bookshelf. A stringent test of the merit of a new technical book is to ask if it adds some value, given the best existing books in its area? I think that Mastering Algorithms with Perl definitely does. It is a well-written introduction to algorithms that is more accessible, practical, and entertaining than standard algorithm books. It leverages off of the strengths of a powerful language and a large base of reusable code.

The rest of this review will evaluate the strengths and weaknesses of Mastering Algorithms with Perl in more depth. The central issue that I will consider is why the reader might or might not prefer an algorithms book that concentrates on a single language, as opposed to a general algorithms book. I will try to be up-front about my biases: as a computer scientist, I consider this book to be a compromise between an algorithms book and a how-to manual. This compromise makes it much more useful to Perl programmers, but it sometimes causes the algorithms content to be too watered down.

It is traditional in algorithms books to describe algorithms in pseudocode, which often superficially resembles Pascal. The difference between pseudocode and real code is that pseudocode is not compilable - it ignores implementation details that are not helpful to understanding a particular example. This is considered to be an advantage: without the clutter, the core of the algorithm is easier to see and understand. At the beginning of the book the authors make the point that the Perl code for a binary search is actually shorter than the corresponding pseudocode. And it's true! The advantage of the Perl program is that we have a readable description of the algorithm, and it's executable too. (Unfortunately, it's often nontrivial to convert pseudocode into real source code - the devil is in the details.) The binary search example is slightly misleading, however, because in this case a native Perl data structure (the array) matches the semantics of the problem extremely well, leading to a clear and concise implementation. Later in the book, particularly in the chapter on graphs, we see examples where Perl's built-in data structures are less well suited to the problems. The executable Perl code for graph operations are much longer than the corresponding pseudocode, and are often so syntactically cluttered that they are difficult to read. Is this a flaw in the book or in Perl? No - it's a consequence of giving examples in runnable code instead of pseudocode. Is the tradeoff worth it? Probably, but it depends on what you're trying to get out of the book.

Another consequence of basing an algorithms book on a real language is that the authors can point readers to existing implementations of the algorithms, in CPAN. It's hard to overstate how big of a win this is. Perl is a powerful language to begin with, but it becomes far more powerful when programmers are able to take advantage of the large body of existing code modules. An unfortunate side effect of the fact that the book talks about specific versions of Perl and about specific CPAN packages is that this information will become outdated much more quickly than the algorithms will. Unless the Perl language and CPAN are exceptionally stable in the future, I would not expect most of this information to be valid for more than a few years - hopefully a new version of the book will be available before this one becomes too out of date.

Because the book provides executable code for the algorithms, it's possible to evaluate the performance of the example code (which is available at the O'Reilly site). The authors benchmark a number of the algorithms that they present, and compare the results. This is a nice change from the discussion of asymptotic running times found in traditional algorithm books, which generally ignore the constant factors that often make the difference between an algorithm being useful in practice or not.

The design and analysis of algorithms is a highly mathematical discipline. A sophisticated set of tools has been developed to evaluate the tradeoffs between various algorithms: How efficiently do they use memory and processor cycles? What is the best, average, and worst case running time of various operations? How does the algorithm scale as the size of the input grows? As it turns out, programmers need to understand a few of these formalisms, particularly the "big O" notation for describing asymptotic running time. I think that Mastering Algorithms with Perl uses theory in just the right way: as an aid to programmers' intuition about algorithms, rather than beating us over the head with formulae and proofs. That said, I think there is one area of theory that this book should have spent more time on: NP completeness. NP-complete problems are solvable, but are believed to be inherently hard: no efficient algorithm has been discovered to solve them. There are a wide variety of NP-complete problems, and they do come up in practice. For programmers, the important thing is first to recognize that an NP-complete problem has been encountered, and that it cannot be solved exactly except in small instances. Then, a heuristic that comes up with a good enough approximation of the solution needs to be found and implemented. This is a practical and well-studied part of algorithm design, and in a 650-page book I would expect more than a page or two to be devoted to it.

Several chapters of Mastering Algorithms with Perl are too shallow to be considered good introductions to the associated areas of algorithms. For example, the chapter on matrices only shows code for some of the more trivial matrix operations; for complex tasks, it tells the reader how to use PDL - the Perl Data Language. Although PDL looks like a useful and powerful package, readers should not confuse knowing how to use it with understanding matrix algorithms. In other words, the matrix chapter is too much of a how-to manual. Other chapters such as the ones on searching and sorting are excellent and avoid falling into this trap. Algorithms is a huge area, and it can't all be covered well in 650 pages. The later chapters are a lot of fun to read, but some of them should probably have been scrapped in favor of more depth in core areas.

In conclusion, this is a well-written, useful book. Viewed as a Perl book it's superb; it complements the strengths of Programming Perl and The Perl Cookbook, and I think most or all Perl programmers would benefit from having a copy. Viewed as a computer science book, it has made a number of compromises in order to focus on a specific language; this is not necessarily a problem but it is something that readers should be aware of.

Acknowledgments: Thanks to Tom Christiansen, Dave Coppit, Bill Pearson, and Jamie Raymond for helpful comments on previous drafts of this review.

Purchase this book at fatbrain.

John Regehr sent us an excellent review of Mastering Algorithims with Perl, another O'Reilly & Associates effort. Written by Jon Orwant, Jarkko Hietaniemi, and John Macdonald, this is a book designed to take your Perl to a new level of wizardery. Mastering Algo author Jon Orwant, Jarkko Hietaniemi, and John Macdonald pages 704 publisher O'Reilly, 08/1999 rating 8/10 reviewer John Regehr ISBN 1-56592-398-7 summary The intended audience is programmers who don't have a background incomputer science, who know at least some Perl. However, experiencedprogrammers who don't know Perl should have no trouble picking up thebasics of the language with this book and a copy of ProgrammingPerl. In The New Hacker's Dictionary under "superprogrammer," we read that "productivity can vary from one programmer to another by three orders of magnitude." I would argue that at least one of these factors of ten comes from the ability to quickly recognize what algorithms should be used to solve different parts of a problem and to find or write implementations of those algorithms that will result in an efficient program, given the available time and the characteristics of the problem. This ability is developed through experience and by understanding the highlights of the large body of algorithms and analysis of algorithms that has been developed to solve problems that occur over and over again in computer programs.

Mastering Algorithms with Perl is designed to provide the necessary background. It's structured like a traditional algorithms textbook: after describing some basic and advanced data structures (linked lists, trees, heaps, etc.), it has chapters about searching, sorting, sets, matrices, graphs, strings, and some related topics. After the introduction and discussion of data structures, the chapters are relatively independent and could be read in any order. The authors provide plenty of cross-references as well as pointers to books that describe individual subjects in more detail.

The intended audience is programmers who don't have a background in computer science, who know at least some Perl. However, experienced programmers who don't know Perl should have no trouble picking up the basics of the language with this book and a copy of Programming Perl. Also, computer scientists can often use a review of algorithms, and the CPAN pointers are very useful. So, I would go so far as to say that this book would enrich any programmer's bookshelf. A stringent test of the merit of a new technical book is to ask if it adds some value, given the best existing books in its area? I think that Mastering Algorithms with Perl definitely does. It is a well-written introduction to algorithms that is more accessible, practical, and entertaining than standard algorithm books. It leverages off of the strengths of a powerful language and a large base of reusable code.

The rest of this review will evaluate the strengths and weaknesses of Mastering Algorithms with Perl in more depth. The central issue that I will consider is why the reader might or might not prefer an algorithms book that concentrates on a single language, as opposed to a general algorithms book. I will try to be up-front about my biases: as a computer scientist, I consider this book to be a compromise between an algorithms book and a how-to manual. This compromise makes it much more useful to Perl programmers, but it sometimes causes the algorithms content to be too watered down.

It is traditional in algorithms books to describe algorithms in pseudocode, which often superficially resembles Pascal. The difference between pseudocode and real code is that pseudocode is not compilable - it ignores implementation details that are not helpful to understanding a particular example. This is considered to be an advantage: without the clutter, the core of the algorithm is easier to see and understand. At the beginning of the book the authors make the point that the Perl code for a binary search is actually shorter than the corresponding pseudocode. And it's true! The advantage of the Perl program is that we have a readable description of the algorithm, and it's executable too. (Unfortunately, it's often nontrivial to convert pseudocode into real source code - the devil is in the details.) The binary search example is slightly misleading, however, because in this case a native Perl data structure (the array) matches the semantics of the problem extremely well, leading to a clear and concise implementation. Later in the book, particularly in the chapter on graphs, we see examples where Perl's built-in data structures are less well suited to the problems. The executable Perl code for graph operations are much longer than the corresponding pseudocode, and are often so syntactically cluttered that they are difficult to read. Is this a flaw in the book or in Perl? No - it's a consequence of giving examples in runnable code instead of pseudocode. Is the tradeoff worth it? Probably, but it depends on what you're trying to get out of the book.

Another consequence of basing an algorithms book on a real language is that the authors can point readers to existing implementations of the algorithms, in CPAN. It's hard to overstate how big of a win this is. Perl is a powerful language to begin with, but it becomes far more powerful when programmers are able to take advantage of the large body of existing code modules. An unfortunate side effect of the fact that the book talks about specific versions of Perl and about specific CPAN packages is that this information will become outdated much more quickly than the algorithms will. Unless the Perl language and CPAN are exceptionally stable in the future, I would not expect most of this information to be valid for more than a few years - hopefully a new version of the book will be available before this one becomes too out of date.

Because the book provides executable code for the algorithms, it's possible to evaluate the performance of the example code (which is available at the O'Reilly site). The authors benchmark a number of the algorithms that they present, and compare the results. This is a nice change from the discussion of asymptotic running times found in traditional algorithm books, which generally ignore the constant factors that often make the difference between an algorithm being useful in practice or not.

The design and analysis of algorithms is a highly mathematical discipline. A sophisticated set of tools has been developed to evaluate the tradeoffs between various algorithms: How efficiently do they use memory and processor cycles? What is the best, average, and worst case running time of various operations? How does the algorithm scale as the size of the input grows? As it turns out, programmers need to understand a few of these formalisms, particularly the "big O" notation for describing asymptotic running time. I think that Mastering Algorithms with Perl uses theory in just the right way: as an aid to programmers' intuition about algorithms, rather than beating us over the head with formulae and proofs. That said, I think there is one area of theory that this book should have spent more time on: NP completeness. NP-complete problems are solvable, but are believed to be inherently hard: no efficient algorithm has been discovered to solve them. There are a wide variety of NP-complete problems, and they do come up in practice. For programmers, the important thing is first to recognize that an NP-complete problem has been encountered, and that it cannot be solved exactly except in small instances. Then, a heuristic that comes up with a good enough approximation of the solution needs to be found and implemented. This is a practical and well-studied part of algorithm design, and in a 650-page book I would expect more than a page or two to be devoted to it.

Several chapters of Mastering Algorithms with Perl are too shallow to be considered good introductions to the associated areas of algorithms. For example, the chapter on matrices only shows code for some of the more trivial matrix operations; for complex tasks, it tells the reader how to use PDL - the Perl Data Language. Although PDL looks like a useful and powerful package, readers should not confuse knowing how to use it with understanding matrix algorithms. In other words, the matrix chapter is too much of a how-to manual. Other chapters such as the ones on searching and sorting are excellent and avoid falling into this trap. Algorithms is a huge area, and it can't all be covered well in 650 pages. The later chapters are a lot of fun to read, but some of them should probably have been scrapped in favor of more depth in core areas.

In conclusion, this is a well-written, useful book. Viewed as a Perl book it's superb; it complements the strengths of Programming Perl and The Perl Cookbook, and I think most or all Perl programmers would benefit from having a copy. Viewed as a computer science book, it has made a number of compromises in order to focus on a specific language; this is not necessarily a problem but it is something that readers should be aware of.

Acknowledgments: Thanks to Tom Christiansen, Dave Coppit, Bill Pearson, and Jamie Raymond for helpful comments on previous drafts of this review.

Purchase this book at fatbrain.

Meghan Eckman asks: "I am wondering what Visual Effects companies there are which strive to bring filmmaking up to the cutting edge of technology. Particularly, I am interested in the visual effects similar to those used in 'The Matrix' (such as the virtual camera set-up). I am a fourth year University student with Linux, programming, and digital media experience, but with a strong desire to go into the filmmaking industry, particularly in New York. I'd like to combine my technical and media skills to create stunning visual effects for the next generation of filmmaking. Where should I look?"

PsionV writes "The second annual ICFP Programming Contest begins September 2nd. For those of you who didn't participate in this last year, this is a contest where competitors enter programs written in any language which then compete tournament style against each other in a processing intensive task to possibly win money, books, bragging rights, and more. "

Derek Cornish writes "Here is a news article about how Gassee, CEO of Be Inc., has challenged OEMs of the world to bundle Linux and BeOS for free on their computers. Unwillingness to do so would help show Microsoft's stranglehold on the computer market does, in fact, exist. " I'd like to take this time to thank Mr. Gassee....

J.D. Jordan wrote in to tell us that Mandrake has mentioned that E14 is in CVS now, and the rest of the world is just waiting for Anonymous CVS access. Very cool. Having personally witnessed some of the many wonders in E14 while at LinuxExpo, I'm more than excited to get my copy and start working on a couple of theme ideas I'm toying with....

J.D. Jordan writes "GameSpot anouced that unreal has gone Golden, this time its for real, unlithe last site that announced this.... The gamespot article is here" This time it looks legit. I've been looking forward to this one for years; Glad to see it hit light of day. Now if we could get a Linux port, I could play it :)