19867962
submission
Velcroman1 writes:

*s this the future of manned missions into deep space?*

Lockheed Martin on Tuesday unveiled the first Orion spacecraft, a part of what NASA had planned as the sprawlingly ambitious Constellation project that would offer a replacement for the space shuttle — and a means to ferry humans into outer space and back to the moon.

Orion and the companion Ares heavy-lift rocket were part of Constellation, a program cancelled under President Barack Obama's 2011 budget proposal. Instead Obama urged NASA to work toward sending humans to an asteroid and then on to Mars. Reports indicated NASA intended Orion to be merely a crew-escape vehicle. NASA and Lockheed Martin had other plans. They pushed ahead on the Orion space capsule despite their ambiguous status. Tuesday Lockheed Martin showed off the fruits of its labor — and it's far more ambitious than a crew-rescue ship.
19866314
submission
Shining Celebi writes:

*Mozilla has finally released Firefox 4, a couple months behind schedule. It features hardware accelerated graphics, UI performance improvements, a massive boost in Javascript performance, reduced memory usage, WebGL, a new HTML5 parser, App Tabs, tab grouping via the Panorama feature, bookmark and history syncing, and much more. Many users will also be happy to know the status bar has been more-or-less restored after Mozilla removed it in early betas. Firefox 4 scores over 3 times faster on Sunspider, V8, and Kraken.*
19819176
submission
asgard4 writes:

*Statistics*

Title: The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1

Author: Donald E. Knuth

Pages: 883

Rating: 9/10

Publisher: Addison-Wesley Publishing http://www.awl.com/

ISBN-10: 0-201-03804-8

ISBN-13: 978-0-201-03804-0

Price: $74.99 US

Summary: Knuth's latest masterpiece. Almost all there is to know about combinatorial search algorithms.

Decades in the making, Donald Knuth presents the latest few chapters in his by now classic book series "The Art of Computer Programming". The computer science pioneer's latest book on combinatorial algorithms is just the first in an as-of-yet unknown number of parts to follow. While these yet-to-be-released parts will discuss other combinatorial algorithms, such as graph and network algorithms, the focus of this book titled "Volume 4A Combinatorial Algorithms Part 1" is solely on combinatorial search and pattern generation algorithms. Much like the other books in the series, this latest piece is undoubtedly an instant classic, not to be missing in any serious computer science library or book collection.

The book is organized into four major parts, an introduction, a chapter on Boolean algebra, a chapter on algorithms to generate all possibilities (the main focus of the book), and finally 300 pages of answers to the many exercises at the end of every section in the book. These exercises and answers make this work an excellent companion for teachers of a university course.

The book begins with some introductory examples of combinatorial searching and then gives various definitions of graphs and directed acyclic graphs (DAGs) since a lot of combinatorial algorithms conveniently use graphs as the data structures they operate on. Knuth's writing style is terse and to the point, especially when he presents definitions and proofs. However, the text is sprinkled with toy problems and puzzles that keep it interesting.

After the introduction, the first chapter of the book (out of only two) is titled "Zeros and Ones" and discusses Boolean algebra. Most readers that have studied computer science in some form should be intimately familiar with most of the discussed basics, such as disjunctive normal forms and Boolean functions and their evaluation. The reader might be surprised to find a discussion of such an elemental foundation of computer science in a book on combinatorial algorithms. The reason is that storage efficiency is especially important for these types of algorithms and understanding the basic storage unit of computer systems nowadays (as the decimal computer is a definite thing of the past) is of importance.

After covering the basics of Boolean algebra and Boolean functions in quite some detail, Knuth gets to the most fun part of this chapter in my opinion: the section on bitwise tricks and techniques on integer numbers. Being a software engineer in the video games industry, I recognized a lot of the techniques from my day-to-day work, such as bit packing of data and various bit shifting and bit masking tricks. There is also a discussion of some interesting rasterization-like algorithms, such as the shrinking of bitmaps using Levialdi's transformation or filling of regions bounded by simple curves. The chapter concludes with Binary Decision Diagrams that represent an important family of data structures for representing and manipulating Boolean functions. This topic was also quite interesting to me since I have never been exposed to it before.

The second and main chapter of the book is titled "Generating All Possibilities". In this particular volume of the "The Art of Computer Programming" series, the only subsection of the chapter in this volume is on generating basic combinatorial patterns, or more specifically generating all n-tuples, permutations, combinations, partitions, and trees. We can expect more on this topic from Knuth in his continuation in Volume 4B and beyond.

The discussion on n-tuples starts out with a lengthy focus on Gray codes, which are binary strings of n bits arranged in an order such that only one bit changes from string to string.

A quite fun example for generating all permutations presented in this part of the book is alphametics, also sometimes known as verbal arithmetic — a kind of puzzle where every letter of a word stands for a digit and words are used in equations. The goal is to assign digits to letters in such a way that the equation is correct. A classic example is SEND + MORE = MONEY (the solution is left as an exercise for the reader).

The next section deals with generating all combinations. Given a set of n elements, the number of all possible combinations of distinct subsets containing k elements is the well-known binomial coefficient, typically read as "n choose k". One of the more interesting algorithms in this section of the book to me was generating all feasible ways to fill a rucksack, which can come in quite handy when going camping :P

After combinations, Knuth moves on to briefly discuss integer partitions. Integer partitions are ways to split positive integer numbers into sums of positive integers, disregarding order. So, for example 3, 2+1, and 1+1+1 are the three possible partitions of the integer 3. Knuth, in particular, focuses on generating all possible integer partitions and determining how many there are for a given number. The book continues with a concise presentation of the somewhat related topic of set partitions, which refer to ways of subdividing a set of elements into disjoint subsets. Mathematically, a set partition defines an equivalence relation and the disjoint subsets are called equivalence classes; concepts that should be familiar to any mathematics major. Again, the focus is on generating all possible set partitions and determining how many partitions can be generated.

The main part of the book closes with a discussion of how to exhaustively generate all possible trees, which is a topic that I have never given much thought to. I am familiar with generating permutations, combinations, and partitions, but have never really been confronted with generating all possible trees that follow a certain pattern. One main example used throughout this part of the book is generating all possible strings of nested parentheses of a certain length. Such strings can be represented equivalently as binary trees.

Knuth's latest book is comprehensive and almost all encompassing in its scope. It compiles an incredible amount of computer science knowledge on combinatorial searching from past decades into a single volume. As such, it is an important addition to any computer science library. This book is not necessarily an easy read and requires a dedicated reader with the intention of working through it from front to back and a considerable amount of time to fully digest. However, for those with patience, this book contains a lot of interesting puzzles, brain teasers, and almost everything there is to know on generating combinatorial patterns.

On a final note, if you don't have volumes 1-3 yet you can get all volumes in a convenient box set (http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043).

About the review author:

Martin Ecker has been involved in real-time graphics programming for more than 10 years and works as a professional video game developer for High Moon Studios http://www.highmoonstudios.com/ in sunny California.
18742740
story
universegeek writes

*"Mathematician Ken Ono, from Emory, has solved a 250-year-old problem: how to exactly and explicitly generate partition numbers. Ono and colleagues were able to finally do this by realizing that the pattern of partition numbers is fractal (PDF). This pattern allowed them to find a finite, algebraic formula, which is like striking oil in mathematics."*
18715806
story
An anonymous reader writes

*"Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical."*
18633248
story
Kevin Fishburne writes

*"According to WtF Dragon at Ultima Aiera, 'The long and short: Arkane Studios have released what is probably going to be the final patch for their **Ultima Underworld*-inspired game (which, indeed, they tried to license as the third entry in that series), *Arx Fatalis*. They have also released the source code for the game. That's right, the complete source of *Arx Fatalis* is available for download.' The readme notes that the original game installation is required in order to play the compiled game, as the data files are certainly still copyrighted. Linux is in need of a good FPS dungeon crawler, though the code will need a hell of a lot of cleanup as it's a VC8/9 project and uses DirectX (ugh...)."
18251558
story
Hugh Pickens writes

*"Network World reports that Facebook has just released an analysis of the word usage for about one million status updates from its US English speakers with the words in updates organized into 68 different word categories based on the Linguistic Inquiry and Word Count (LIWC)--a text analysis software program that calculates the degree to which people use different categories of words across a wide array of texts. The results? To be popular on Facebook all you have to do is write longer status updates, talk about music and sports, don't be overly emotional, don't talk about your family, don't refer to time and use the word 'you' a lot. Facebook's study also confirms something that bloggers and Fox News have known for years: negative comments produce more online activity. Sure, Facebook users might click the like button more often on updates expressing positive emotion. But Facebook found you can't beat negativity for user engagement, as dismal status updates garnered more comments than positive ones."*
18209958
story
flintmecha writes

*"A group of British schoolchildren may be the youngest scientists ever to have their work published in a peer-reviewed journal. In a new paper in Biology Letters, children from Blackawton Primary School report that buff-tailed bumblebees can learn to recognize nourishing flowers based on colors and patterns. The paper itself is well worth reading. It's written entirely in the kids' voices, complete with sound effects (part of the Methods section is subtitled, ''the puzzle'duh duh duuuhhh') and figures drawn by hand in colored pencil."*
17938996
submission
wierd_w writes:

*Daniel Ellsberg: “EVERY attack now made on WikiLeaks and Julian Assange was made against me and the release of the Pentagon Papers at the time.”*

Due to the recent debates over the pros and cons between the wikileaks releases and those of the historic "Pentagon papers", Journalist Daniel Ellsberg, who released the pentagon papers in 1971, has written an editorial on the subject declaring that he rejects the mantra of “Pentagon Papers good; WikiLeaks material bad", and that further “That’s just a cover for people who don’t want to admit that they oppose any and all exposure of even the most misguided, secretive foreign policy. The truth is that EVERY attack now made on WikiLeaks and Julian Assange was made against me and the release of the Pentagon Papers at the time.”
17938788
submission
Dialecticus writes:

*According to an article by Lewis Page at The Register, NASA says that most theoretical models of global warming fail to take into account the cooling effects of how plant life would react to higher CO2 levels in the atmosphere. NASA's new model reportedly indicates that even something as extreme as a doubling of current CO2 levels would only result in a 1.64 degree Celsius increase in overall global temperatures, with temperature increases over land being even less than that. The article does not specifically mention whether increased photosynthesis would have a natural regulating effect on CO2 levels due to the commensurate increase in the rate of naturally occurring carbon sequestration.*
17540814
story
ceswiedler writes

*"Wired is reporting that the Stuxnet worm was apparently designed to subtly interfere with uranium enrichment by periodically speeding or slowing specific frequency converter drives spinning between 807Hz and 1210Hz. The goal was not to cause a major malfunction (which would be quickly noticed), but rather to degrade the quality of the enriched uranium to the point where much of it wouldn't be useful in atomic weapons. Statistics from 2009 show that the number of enriched centrifuges operational in Iran mysteriously declined from about 4,700 to about 3,900 at around the time the worm was spreading in Iran."*
17543880
submission
suraj.sun writes:

*At last count, exoplanet hunters have dead-eyed 495 distant worlds. Granted, none of them are "Earth-like," but what will we do if such a world finally pops up? Will we be able to travel there in person or send a probe?*

According to Centauri Dreams ( http://www.centauri-dreams.org/ ) writer Paul Gilster, one of the founders of Tau Zero ( http://www.tauzero.aero/ ), getting to another star isn't beyond reach. Getting there within a human lifetime? Now that's a problem.

In order to speed the whole process up, physicist Robert Forward ( http://www.robertforward.com/ ) proposed pushing on the sail with a laser beam. "Some of Forward's designs got to speeds up to 10 percent of light speed," Gilster says. "And if you are talking about 4.3 light-years away from Earth, which is where the Centauri primary stars are, that gets you there in about 43 years."

Interstellar propulsion inevitably comes down to energy, and few future energy sources are as promising as fusion power ( http://science.howstuffworks.com/fusion-reactor.htm ), the joining of atomic nuclei to produce a single nuclei and a release of energy.

"Fusion is another possibility, particularly deuterium/helium-3 fusion," Gilster says. "We haven't yet figured out how to [initiate] this reaction on Earth, but it's possible that in the next 50 or 100 years we'll learn how to tap this kind of fusion for propulsion."

Discovery News: http://news.discovery.com/space/is-it-possible-to-travel-to-another-star.html
17537766
story
angry tapir writes

*"In an effort to expand software compatibility for its upcoming Fusion chips, AMD has joined rival Intel's efforts to develop the open-source MeeGo OS. AMD 'will provide engineering expertise intended to help establish the technical foundations for next-generation mobile platforms and embedded devices,' the company said in a blog post on its website."*