5 ms·

Hmm, let's see: One of the algorithms is the fast Fourier transform (FFT). It is sometimes described as a form of matrix factorization and multiplication. An

Hmm, let's see: One of the algorithms is the fast Fourier transform (FFT). It is sometimes described as a form of matrix factorization and multiplication. Another algorithm is Dantzig's simplex algorithm for linear programming: It is basically just elementary row operations much as in Gauss elimination on a, usually, vastly 'under determined' system of linear equations. The math for the simplex algorithm is mostly nicely presented via matrix theory. A third algorithm in the list is the QR algorithm for finding eigenvalues. So, of the 10 algorithms, at least three are closely related to just matrix theory. Amazing. Then, for computer science I would add an observation: A few days ago a venture firm principal asked me about my project, "So you have an algorithm?". I had to respond, "Well, yes, but by itself an algorithm doesn't have much to recommend it and, thus, doesn't mean much.". Well, this list of 10 algorithms supports my observation: For a problem as complicated as those solved by the 10 algorithms in the list, an algorithm by itself doesn't mean much, really doesn't mean anything. Instead, to take any such algorithm seriously, we need something we can take seriously and logically prior to the algorithm. Well, as in the 10 algorithms, what is prior is just some applied math, typically with theorems and proofs. Then due to the theorems and proofs, we take the applied math seriously. Then we take the algorithm seriously because and only because it is a careful implementation of the data manipulations in the applied math. So, net, what is really crucial for such an algorithm is the logically prior applied math. Of course, at times we can proceed without any prior applied math and work just with an algorithm that we got, say, from just heuristics. Then we may be able to take the algorithms seriously after a lot of empirical testing. So, here's my point: For reasonably complicated problems, the key is some applied math, and we take a corresponding algorithm seriously only because of the logically prior applied math. Or, computer science: The most important work with algorithms is work with logically prior applied math complete with theorems and proofs. Work with algorithms without such prior applied math is close to hopeless. Venture firms and limited partners: If an entrepreneur has some crucial, core 'secret sauce' in running code that can be called an 'algorithm', what is crucial (prior to already having a financially successful company based on that code) is the corresponding applied math, not the 'algorithm' and not just the code. Information technology entrepreneurs: If your business is trying to solve a serious problem with an algorithms and some corresponding code, then don't start with the algorithm and, instead, start with some applied math. Computer science students: If you want to do good work with algorithms, study appropriate topics in a math department, not 'algorithms' in a computer science department. Computer science professors: Algorithms are crucial to your field, but your approach to algorithms skipping prior applied math complete with theorems and proofs is bankrupt, with no good reason to take any such algorithm seriously, and will lead to a long walk on a short pier and blocked progress for your field. What's just crucial for your interest in algorithms is in the math department and not in your department. Sorry 'bout that!

psykotic 14y ago
It's an article from SIAM. Of course it's heavily biased towards applied mathematics. It's not only biased against computer science, it's biased against pure mathematics. Do you doubt that Buchberger's algorithm will reverberate down through the millenia? Even within applied mathematics, the list leaves out multigrid methods, the only linear-time algorithms in their class, which seem a shoe-in given their criteria for inclusion. It would hardly be difficult to make a very long list of pure CS algorithms and data structures that could stand head to head against the likes of the multipole method in both industrial application and scientific value. Your knowledge of computer science is evidently shallow. Educate yourself and you might think twice before making such ignorant pronouncements.
- dvse 14y ago
  I wonder what proportion of "pure" CS algorithms can be conceptualized as an application of one of the fixed point theorems and/or properties of monotone operators. There has got to be _something_ useful about the functional analysis perspective and people doing serious work in algorithms are certainly familiar with it as a group.
  - psykotic 14y ago
    > I wonder what proportion of "pure" CS algorithms can be conceptualized as an application of one of the fixed point theorems and/or properties of monotone operators. You might enjoy http://www.amazon.com/Graphs-Dioids-Semirings-Algorithms-Operations/dp/0387754490 http://www.amazon.com/Graphs-Dioids-Semirings-Algorithms-Ope.... It has some cool ideas, but you'll first have to wade through a sea of abstract nonsense a la Bourbaki.
- ten_fingers 14y ago
  You make several points. It appears that you don't like my main point but have no good argument against it or replacement for it; I will respond and try to explain my main point again. One of your points seems to be that the selection of 10 best algorithms is not very good. I would agree: I would have selected heap sort instead of quicksort because, given a positive integer n, the execution time of heap sort in sorting n items is proportional to n ln(n) in both average case and worst case and, thus, heap sort meets the Gleason bound for the fastest possible sort by comparing pairs of keys. The execution time of quicksort on average is n ln(n), and in practice faster than heap sort, but in worst case appears to run in n^2. Quicksort seems to do better on locality of reference for a virtual memory system, but there are ways to improve the locality of reference of heap sort. For my main point, that the list of 10 best algorithms was well chosen is not very important. Here is my main point again: "For reasonably complicated problems, the key is some applied math, and we take a corresponding algorithm seriously only because of the logically prior applied math." So, since you don't like this point, I will try to explain in more detail: First, we are considering 'algorithms'. So, let's agree on what we mean by an algorithm: I will accept running code in a common programming language -- C/C++, Fortran, PL/I, etc. -- or something similar in 'pseudo-code'. So, the issue is, given an algorithm, what do we need to take it "seriously", that is, be sure it does what it is intended to do? Second, briefly let's return to sorting: Quicksort and heap sort are darned clever. But, given the algorithms, in the form I just mentioned, it's easy enough to trace the logic informally and confirm that the algorithms actually do sort. For the running times, finding those is more work but not very notable math. So, net, for these sorting algorithms, it is easy enough for us to take them seriously for their ability to do what is promised -- sort or sort in n ln(n). You also mentioned data structures. Well we can say much the same for AVL trees or the data structures used in a fast implementation of the network simplex algorithm for least cost capacitated network flows, etc. For some of the data structures used in, say, dynamic programming, more is needed to take the algorithms for those data structures seriously. Similarly for some uses of k-D trees. So, for some algorithms and data structures, we can take them seriously just 'by inspection'. Third, consider, as in the list of 10 algorithms, trying to solve a fairly complicated problem. Examples could include the discrete Fourier transform, finding eigenvalues and eigenvectors of a symmetric, positive definite matrix, least cost network flows, matching to minimize the most expensive single match used, linear programming, quadratic programming, iterative solution of large systems of linear equations (e.g., via Gauss-Seidel). Maybe we are trying to solve a problem in non-linear programming and want an algorithm to achieve the Kuhn-Tucker conditions. Given an algorithm for one of these problems, to take the algorithm seriously we need more than just 'inspection'. So, since just 'inspection' no longer works, the question is, how can we take such an algorithm seriously? Actually, there is some fairly tricky math needed for us to take seriously the simplex algorithm for linear programming: For the set of real numbers R, a positive integer n, and Euclidean R^n with the usual topology, let F be the intersection of finitely many closed half spaces of R^n, and let linear function z: R^n --> R. Claim: If z is bounded above on F, then z achieves its least upper bound. For us to take the simplex algorithm seriously, we need to know that this claim is true. Note: The proof is not just usual analysis with converging sequences from Rudin's 'Principles'. For more, given a linear programming problem, it may be feasible or infeasible. If the problem is feasible, then it may be bounded or unbounded. If the problem is feasible and bounded, then we want to know that there is an optimal solution and that the simplex algorithm can find one in finitely many iterations. Since the simplex algorithm considers only extreme point solutions, we would like to know that, if there is an optimal solution, then there is an optimal extreme point solution. In the simplex algorithm, there is a sufficient condition for optimality, but there can be optimal solutions and optimal extreme point solutions without this sufficient condition. So, we need to know that the simplex algorithm can achieve the sufficient condition. The nicest solution to these issues I know of is via Bland's rule by R. Bland, long at SUNY. It's not obvious. Again, let's be more clear: Given an algorithm as above, that is, just code or pseudo-code, for the simplex algorithm with Bland's rule, solution of linear equations with double precision inner product accumulation and iterative improvement (Forsythe and Moler), detecting and handling degeneracy (basic variables with value 0), detecting infeasibility, detecting unboundedness, considering the reduced costs as a sufficient condition for optimality, the code will look like just so much gibberish with no good reason to take it seriously. To take the code seriously, we need some prior math where the algorithm just implements the manipulations specified by the math. Yes, apparently computer science regards the simplex algorithm as an algorithm in computer science: E.g., the algorithm is discussed in Chapter 29 of Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 'Introduction to Algorithms, Second Edition', The MIT Press Cambridge. commonly called 'CLRS'. E.g., recently I encountered a question: For some positive integer n, given n client computers and one frequency band with bandwidth x Mbps, design a wireless network to provide all x Mbps to all n client computers simultaneously. Is such possible? Yes. Does this violate Shannon's information theory? No. So, how to take any such proposal seriously? Sure, some math. Basically the solution is one heck of a strange 'antenna' pattern with n nodes with each client getting just the node with just their data. It all boils down just to linear algebra after taking some Fourier transforms. So, again, given a fairly complicated problem, when trying to evaluate an algorithm to solve this problem where just 'inspection' no longer works, the question is, how can we take such an algorithm seriously? Well, to take the algorithm seriously, we need more than just the algorithm, that is, more than just the code or pseudo-code. As I mentioned, one way to take the algorithm seriously is a lot of empirical evidence. Alas, this can be slow and is not very satisfactory. So, what is left? You mentioned nothing. And computer science has nothing. I gave a solution: Start with the real problem. Get a solution via some applied math complete with theorems and proofs. That is, properties of the real problem provide assumptions for the theorems, and the conclusions of the theorems provide the desired solution. Then the software, that is, the 'algorithm', implements the data manipulations specified by the math. We take the math seriously because of the theorems and proofs. Then we take the algorithm seriously because, and only because, we took the math seriously. Net, without the math, there is little reason to take the algorithm seriously. With the math, to evaluate the algorithm, we should evaluate the math and then confirm that the algorithm does what the math specifies. So, for your "Your knowledge of computer science is evidently shallow. Educate yourself and you might think twice before making such ignorant pronouncements." What is relevant here is what I wrote; whether my "knowledge of computer science" is "shallow" or not is irrelevant. I said nothing "ignorant"; you gave no solution to the question of how to take an algorithm seriously when 'inspection' is not sufficient; and I gave apparently the only good solution we have.

psykotic 14y ago

It's an article from SIAM. Of course it's heavily biased towards applied mathematics. It's not only biased against computer science, it's biased against pure mathematics. Do you doubt that Buchberger's algorithm will reverberate down through the millenia? Even within applied mathematics, the list leaves out multigrid methods, the only linear-time algorithms in their class, which seem a shoe-in given their criteria for inclusion. It would hardly be difficult to make a very long list of pure CS algorithms and data structures that could stand head to head against the likes of the multipole method in both industrial application and scientific value. Your knowledge of computer science is evidently shallow. Educate yourself and you might think twice before making such ignorant pronouncements.

dvse 14y ago
I wonder what proportion of "pure" CS algorithms can be conceptualized as an application of one of the fixed point theorems and/or properties of monotone operators. There has got to be _something_ useful about the functional analysis perspective and people doing serious work in algorithms are certainly familiar with it as a group.
- psykotic 14y ago
  > I wonder what proportion of "pure" CS algorithms can be conceptualized as an application of one of the fixed point theorems and/or properties of monotone operators. You might enjoy http://www.amazon.com/Graphs-Dioids-Semirings-Algorithms-Operations/dp/0387754490 http://www.amazon.com/Graphs-Dioids-Semirings-Algorithms-Ope.... It has some cool ideas, but you'll first have to wade through a sea of abstract nonsense a la Bourbaki.
ten_fingers 14y ago
You make several points. It appears that you don't like my main point but have no good argument against it or replacement for it; I will respond and try to explain my main point again. One of your points seems to be that the selection of 10 best algorithms is not very good. I would agree: I would have selected heap sort instead of quicksort because, given a positive integer n, the execution time of heap sort in sorting n items is proportional to n ln(n) in both average case and worst case and, thus, heap sort meets the Gleason bound for the fastest possible sort by comparing pairs of keys. The execution time of quicksort on average is n ln(n), and in practice faster than heap sort, but in worst case appears to run in n^2. Quicksort seems to do better on locality of reference for a virtual memory system, but there are ways to improve the locality of reference of heap sort. For my main point, that the list of 10 best algorithms was well chosen is not very important. Here is my main point again: "For reasonably complicated problems, the key is some applied math, and we take a corresponding algorithm seriously only because of the logically prior applied math." So, since you don't like this point, I will try to explain in more detail: First, we are considering 'algorithms'. So, let's agree on what we mean by an algorithm: I will accept running code in a common programming language -- C/C++, Fortran, PL/I, etc. -- or something similar in 'pseudo-code'. So, the issue is, given an algorithm, what do we need to take it "seriously", that is, be sure it does what it is intended to do? Second, briefly let's return to sorting: Quicksort and heap sort are darned clever. But, given the algorithms, in the form I just mentioned, it's easy enough to trace the logic informally and confirm that the algorithms actually do sort. For the running times, finding those is more work but not very notable math. So, net, for these sorting algorithms, it is easy enough for us to take them seriously for their ability to do what is promised -- sort or sort in n ln(n). You also mentioned data structures. Well we can say much the same for AVL trees or the data structures used in a fast implementation of the network simplex algorithm for least cost capacitated network flows, etc. For some of the data structures used in, say, dynamic programming, more is needed to take the algorithms for those data structures seriously. Similarly for some uses of k-D trees. So, for some algorithms and data structures, we can take them seriously just 'by inspection'. Third, consider, as in the list of 10 algorithms, trying to solve a fairly complicated problem. Examples could include the discrete Fourier transform, finding eigenvalues and eigenvectors of a symmetric, positive definite matrix, least cost network flows, matching to minimize the most expensive single match used, linear programming, quadratic programming, iterative solution of large systems of linear equations (e.g., via Gauss-Seidel). Maybe we are trying to solve a problem in non-linear programming and want an algorithm to achieve the Kuhn-Tucker conditions. Given an algorithm for one of these problems, to take the algorithm seriously we need more than just 'inspection'. So, since just 'inspection' no longer works, the question is, how can we take such an algorithm seriously? Actually, there is some fairly tricky math needed for us to take seriously the simplex algorithm for linear programming: For the set of real numbers R, a positive integer n, and Euclidean R^n with the usual topology, let F be the intersection of finitely many closed half spaces of R^n, and let linear function z: R^n --> R. Claim: If z is bounded above on F, then z achieves its least upper bound. For us to take the simplex algorithm seriously, we need to know that this claim is true. Note: The proof is not just usual analysis with converging sequences from Rudin's 'Principles'. For more, given a linear programming problem, it may be feasible or infeasible. If the problem is feasible, then it may be bounded or unbounded. If the problem is feasible and bounded, then we want to know that there is an optimal solution and that the simplex algorithm can find one in finitely many iterations. Since the simplex algorithm considers only extreme point solutions, we would like to know that, if there is an optimal solution, then there is an optimal extreme point solution. In the simplex algorithm, there is a sufficient condition for optimality, but there can be optimal solutions and optimal extreme point solutions without this sufficient condition. So, we need to know that the simplex algorithm can achieve the sufficient condition. The nicest solution to these issues I know of is via Bland's rule by R. Bland, long at SUNY. It's not obvious. Again, let's be more clear: Given an algorithm as above, that is, just code or pseudo-code, for the simplex algorithm with Bland's rule, solution of linear equations with double precision inner product accumulation and iterative improvement (Forsythe and Moler), detecting and handling degeneracy (basic variables with value 0), detecting infeasibility, detecting unboundedness, considering the reduced costs as a sufficient condition for optimality, the code will look like just so much gibberish with no good reason to take it seriously. To take the code seriously, we need some prior math where the algorithm just implements the manipulations specified by the math. Yes, apparently computer science regards the simplex algorithm as an algorithm in computer science: E.g., the algorithm is discussed in Chapter 29 of Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 'Introduction to Algorithms, Second Edition', The MIT Press Cambridge. commonly called 'CLRS'. E.g., recently I encountered a question: For some positive integer n, given n client computers and one frequency band with bandwidth x Mbps, design a wireless network to provide all x Mbps to all n client computers simultaneously. Is such possible? Yes. Does this violate Shannon's information theory? No. So, how to take any such proposal seriously? Sure, some math. Basically the solution is one heck of a strange 'antenna' pattern with n nodes with each client getting just the node with just their data. It all boils down just to linear algebra after taking some Fourier transforms. So, again, given a fairly complicated problem, when trying to evaluate an algorithm to solve this problem where just 'inspection' no longer works, the question is, how can we take such an algorithm seriously? Well, to take the algorithm seriously, we need more than just the algorithm, that is, more than just the code or pseudo-code. As I mentioned, one way to take the algorithm seriously is a lot of empirical evidence. Alas, this can be slow and is not very satisfactory. So, what is left? You mentioned nothing. And computer science has nothing. I gave a solution: Start with the real problem. Get a solution via some applied math complete with theorems and proofs. That is, properties of the real problem provide assumptions for the theorems, and the conclusions of the theorems provide the desired solution. Then the software, that is, the 'algorithm', implements the data manipulations specified by the math. We take the math seriously because of the theorems and proofs. Then we take the algorithm seriously because, and only because, we took the math seriously. Net, without the math, there is little reason to take the algorithm seriously. With the math, to evaluate the algorithm, we should evaluate the math and then confirm that the algorithm does what the math specifies. So, for your "Your knowledge of computer science is evidently shallow. Educate yourself and you might think twice before making such ignorant pronouncements." What is relevant here is what I wrote; whether my "knowledge of computer science" is "shallow" or not is irrelevant. I said nothing "ignorant"; you gave no solution to the question of how to take an algorithm seriously when 'inspection' is not sufficient; and I gave apparently the only good solution we have.