Become a fan of Slashdot on Facebook

typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. ×

## Comment Re:"functional programming languages can beat C" (Score 2, Informative)502

Paul Graham has commentary from an ITA insider.

6. If you want to do a simple round-trip from BOS to LAX in two weeks, coming back in three, willing to entertain a 24 hour departure window for both parts, then limiting to "reasonable" routes (at most 3 flights and at most 10 hours or so) you have about 5,000 ways to get there and 5,000 ways to get back. Listing them is a mostly trivial graph-search (there are a few minor complications, but not many), that anybody could do in a fraction of a second.

7. The real challenge is that a single fixed itinerary (a fixed set of flights from BOS to LAX and a fixed set back) with only two flights in each direction may have more than 10,000 possible combinations of applicable "fares", each fare with complex restrictions that must be checked against the flights and the other fares. That means that the search space for this simple trip is of the order 5000 x 5000 x 10000, and a naive program would need to do a _lot_ of computation just to validate each of these possibilities. Suitably formalized, its not even clear that the problem of finding the cheapest flight is NP-complete, since it is difficult to put a bound on the size of the solution that will result in the cheapest price. If you're willing to dispense with restrictions on the energy in the universe, then it is actually possible to formalize the cheapest-price problem in a not-too-unreasonable way that leads to a proof of undecidability by reduction to the Post correspondance problem :-).

So it seems that your assumption that "Fares just aren't that complex. It's a straightforward directed graph." is in error. Remember that this work used to require dedicated intelligence (i.e. a travel agent) who was at a serious disadvantage in terms of fare data.

## Comment Re:Not rabbit ears (Score 1)265

Actually, given a strong signal, analogue is better. Digital TV is compressed with a lossy algorithm, which always leads to some deterioration in picture quality.

Because I'd much rather have 300,000 "uncompressed" pixels than 900,000 "compressed" ones...

# Slashdot Top Deals

Machines certainly can solve problems, store information, correlate, and play games -- but not with pleasure. -- Leo Rosten

Working...