Hi Simon, you're great! I appreciate your efforts for moving forward CS education and of course your incredible contribution to the development of Haskell. Just a couple of corrections: 1. Factorization isn't NP complete 2. Andrew Whiles proved Fermat's last theorem, not the 4-color map theorem.
An important characteristic of faster algorithms are they are leveraging the "information" available or generating it and using it as they compute. This leverage we get from "information" is what helps us write speedy algos. eg: binary search relies on the information that the data is sorted, so the search is much faster than a linear search (which is the only option if we have no information about the data we are trying to search)
Yes, the principle is always: when there is extra structure (like a preordered dictionary) then you can speedup. Complexity calculations always neglect the necessary preparatory work required for these faster algorithms, and this work can grow exponentially in size but it's considered cost-free.
I think it's interesting to note that even "perfect" algorithms that give a single unambiguous definitive answer can be wrong simply because they are run on a physical computer. even if we disregard logic errors in the code, the program still executes in some sort of runtime which can have bugs, and further on we have hardware malfuntions or cosmic rays flipping random bits in memory and so on. really, nothing is certain!
Yeah, true, but I think there are even more "exciting" everyday problems than cosmic rays flipping random bits, such as how you model a continuous physical system in a computer program with finite precision, numerical analysis algorithms, or even 'prediction' problems, requiring some form of extrapolation of data (e.g. predicting the weather in a week's time). Even if your problem is completely deterministic, you may face numerical problems in the end.
A great talk from Simon on "Getting From A-B: Fast Route-Finding Using Slow Computers", via Microsoft Research at research.microsoft.com/apps/video/default.aspx?id=146561&r=1
I'm delighted by the way he expresses his ideas, in a visually and auditory way. Simon Peyton Jones is respectable man.
Think about how awesome an actor he would have made.
Hi Simon, you're great! I appreciate your efforts for moving forward CS education and of course your incredible contribution to the development of Haskell.
Just a couple of corrections:
1. Factorization isn't NP complete
2. Andrew Whiles proved Fermat's last theorem, not the 4-color map theorem.
I like his explanation of NP-complete problems. Makes the point clearly.
An important characteristic of faster algorithms are they are leveraging the "information" available or generating it and using it as they compute. This leverage we get from "information" is what helps us write speedy algos. eg: binary search relies on the information that the data is sorted, so the search is much faster than a linear search (which is the only option if we have no information about the data we are trying to search)
Yes, the principle is always: when there is extra structure (like a preordered dictionary) then you can speedup. Complexity calculations always neglect the necessary preparatory work required for these faster algorithms, and this work can grow exponentially in size but it's considered cost-free.
Thanks for your comment. We're really pleased you found it useful.
I think it's interesting to note that even "perfect" algorithms that give a single unambiguous definitive answer can be wrong simply because they are run on a physical computer. even if we disregard logic errors in the code, the program still executes in some sort of runtime which can have bugs, and further on we have hardware malfuntions or cosmic rays flipping random bits in memory and so on. really, nothing is certain!
Yeah, true, but I think there are even more "exciting" everyday problems than cosmic rays flipping random bits, such as how you model a continuous physical system in a computer program with finite precision, numerical analysis algorithms, or even 'prediction' problems, requiring some form of extrapolation of data (e.g. predicting the weather in a week's time). Even if your problem is completely deterministic, you may face numerical problems in the end.
A great talk from Simon on "Getting From A-B: Fast Route-Finding Using Slow Computers", via Microsoft Research at research.microsoft.com/apps/video/default.aspx?id=146561&r=1
serting and sorching :)
people like this is why we have crappy software, especially from Microsoft .