Milestone for MIT Press’s bestseller, "Introduction to Algorithms"
web.mit.edu
web.mit.edu
(And my life is full of excitement, trust me!)
Great book, one of the must-reads. Though I'll admit I've only gotten like a third of the way through it...
Monzy was my TA for CS147 (intro to HCI). Small world.
Since my friend has it, I wanted to get something different and picked up Skiena's Algorithm Design Manual. Anyone have thoughts between the two?
My opinion of the book nowadays is actually somewhat low. The content and style is competent but generic and uninspiring. It does a poor job of teaching algorithm design, but admittedly that is a flaw with most of these books. Udi Manber's lesser-known textbook is just a lot better in that regard. It does mean sacrificing some breadth of coverage compared to CLR. For me it's the right trade-off because so much of CLR's coverage comes across as perfunctory, as if they're just checking boxes off an endless curriculum list that's intended to please everyone, much like the big calculus books. The grab bag of advanced chapters in the book's last half are the exception to that rule. They're usually in the authors' own research areas, and it shows.
It's true that I don't get to university bookstores as often as I'd like.
Anyone who want to learn algorithms & data stuctures should get this & read it cover-to-cover. PERIOD
CLR is sitting by my desk now. Seeing this book inspires me to code.
In places the authors of the book have bitten off more than they can chew well. E.g., in linear programming they have:
"Gaussian elimination begins with a system of linear equalities whose solution is unknown. In each iteration, we rewrite this system in a equivalent form that has some additional structure. After some number of iterations, we have rewritten the system so that the solution is simple to obtain. The simplex algorithm proceeds in a similar manner, and we can view it as Gaussian elimination for inequalities."
NO! They blew it! That just ain't the point! They failed to 'get it'! They don't understand! With liberal grading, they get a gentleman C- for effort!
They get a grade of B until they get to:
"we can view it as Gaussian elimination for inequalities."
where they get a big red mark through their effort!
They emphasized the role of inequalities, but that is really trivial. With no difficulty at all, we convert a linear programming problem with inequality constraints (<= or >= but not < or >) to one with (a) equality constraints and (b) all the variables greater than or equal to zero. Fine. But notice the part (b) where we still have some inequalities although some simpler ones.
That conversion was easy. But it didn't do us any good at all for the main point of linear programming or the simplex algorithm for finding solutions since the main point is optimization, that is, doing good things for the objective function.
So, with the equality constraints, in the simplex algorithm, we proceed with elementary row operations. Yes, each "iteration" is in terms of elementary row operations on a system of linear equations. It is MUCH better to mention "elementary row operations" than "iterations"(s) because the 'iterations' can't be easily justified but the elementary row operations can. That is, there's no doubt that elementary row operations yield an equivalent system of linear equations; either we learned this well enough in high school or we can easily establish it ourselves in a few minutes.
Yes, so does Gauss elimination use elementary row operations. But, for the simplex algorithm itself, directly, that's the end of the connection with Gauss elimination!
Why? Gauss elimination, for numerical stability, should emphasize careful selection of the 'pivot' elements, e.g., as in
George E. Forsythe and Cleve B. Moler, 'Computer Solution of Linear Algebraic Systems', Prentice-Hall, Englewood Cliffs.
and the simplex algorithm of linear programming does not have that freedom or luxury.
So, each 'iteration' in the simplex algorithm is just an application of elementary row operations on a system of linear equations. Nice to know this.
Next, and the main point of the simplex algorithm, which elementary row operations are selected? That is, there is enormous freedom, and all the freedom would result in an equivalent system, so how to exploit the freedom?
Well, the authors omitted a step! Once we have converted the given linear program with, possibly, some <= or >= constraints, to all equality constraints and all variables >= 0 (and all the right sides >= 0), we want an 'initial basic feasible solution'. How do we get one? We in effect just 'glue it on'!
So, if for some positive integer n we have n constraints, then we glue on, that is, append, n more variables, that is, n more columns, where the n x n matrix in the constraints is just the identity matrix. These variables are called 'artificial'. We (temporarily) modify the objective function: We set each of the old cost coefficients to, say, 0 and the cost coefficients of each of the artificial variables to, say, 1.
What's going on with the artificial variables? Sure: The first question about a linear program is, does it have a feasible solution or not? We say that a solution, that is, values for the variables, is 'feasible' if it satisfies the constraints. It may be that there is no feasible solution; we want to know.
So, this work with artificial variables answers the question about feasible or not.
How? The problem with the artificial variables is obviously feasible (before we appended the artificial variables, we multiplied some of the equality constraints by -1 so that all the constants on the right side were >= 0). So, if we just assign the right side variable values to the artificial variables (the only way we can given that n x n identity matrix), then we will have a basic feasible solution to the problem with the artificial variables.
Then we apply the simplex algorithm to minimize. We look at the resulting optimal value of the objective function. If that value is positive, then the initial problem is infeasible. If the value is 0, then the initial problem is feasible and we have a feasible solution for it. With some inspection, we also have a basic feasible solution for the initial problem after dropping some redundant rows.
Also, easily we can put the original cost coefficients back where they belong in place of the 0s we inserted.
So, due to the artificial variables, we have a basic feasible solution and, if you will, an identity matrix that is the goal of Gauss elimination. So, Gauss elimination can't really help us.
But some elementary row operations can help us, and they do, that's what we use, and that's the core of the simplex algorithm.
Now we address a crucial issue: Looking at what are called 'reduced costs', it may be that they tell us that our present basic feasible solution is optimal. If so, then we stop.
Else, we pick a variable not in the basis and ask what would happen to the objective function value if we (a) increased this non-basic variable and (b) adjusted the basic variables to maintain equality in the constraints.
Now we address another major point: Looking at increasing the value of this non-basic variable, it may be that we can increase it all we want, without bound. In this case we have just discovered that our problem is unbounded. That is, assuming we are minimizing, we can save all we want. Else, there is a maximum value to which we can increase this non-basic variable without driving one of the old basic variables negative and, thus, giving us an infeasible solution. That is, increasing this non-basic value to its maximum value drives one or more old basic variables to zero.
So, we say that this non-basic variable 'enters' the basis and some old basic variable at zero 'leaves' the basis.
This calculation needs only elementary row operations.
So, each iteration of the simplex algorithm, actually including finding the reduced costs, needs only elementary row operations on a system of linear equations.
Then, the big point, the HUGE point, the main point about the simplex algorithm is WHAT elementary row operations are used. The answer is, we use elementary row operations that, one non-basic variable at a time, improve the value of the objective function.
THAT'S what's special in the simplex algorithm and NOT that it's 'Gauss elimination on systems of inequalities'.
For more, geometrically, the feasible region is an intersection of finitely many half spaces and, thus, is a closed, convex set with extreme points, edges connecting pairs of extreme points, and flat sides. Each basic feasible solution corresponds to an extreme point. One simplex iteration, when it improves the value of the objective function, leaves its extreme point and moves along an edge from that extreme point.
It is possible to move from one basis to another with no change in the value of the objective function; in this case it is possible for the simplex algorithm to 'cycle', that is, return to a given basis infinitely often. By being more selective about entering variables, we can avoid cycling.
If there is an optimal solution, then there is an optimal basic feasible solution; there is an optimal basic feasible solution where the reduced costs will show that the solution is optimal; and the simplex algorithm that does not cycle will find such a solution in finitely many iterations.
Once again, don't go to computer science people, not even the ones at MIT, to learn some applied math, not even applied math as simple, elementary, old, and beautifully polished as the simplex algorithm of linear programming.
Well said. I've taken courses both in CS and Math. CS people think they know math, but most of the time they have very poor math skills, and this is true even in Theoretical CS. Most proofs in CS are way too complicated and badly written. I think this book is one of the reasons for this -- most of the time the proofs are extremely complicated and verbose, it is a bad example for students that want to learn algorithms. Sedgewick's book is much better, in my opinion.
Mostly fields outside math try hard to teach math within their fields. Examples of such fields include physics, chemistry, economics, psychology, sociology, electronic engineering, and, yes, computer science, In all cases, the results are at best poor. Of course, those fields are helped by the fact that the math departments don't want to do well teaching service courses, say, in second order stationary stochastic processes for signal processing in electronic engineering with the fast Fourier transform!
But you noticed the problem: The CS profs make a mess out of math.
For the book of this thread from MIT, that fact is a bit surprising: For one, among the authors, at least Rivest has done some good math. For another, for each math topic in that book, MIT has some high expertise. E.g., in optimization, Bertsekas is there and long there have been others.
Once the basic ugrad lessons in math are learned, one still has to learn how to communicate in less severe forms. So, the book failed there, too: Their algebra for the core steps of the simplex algorithm was too long. And, their intuitive explanation, as I objected to here, really was not correct. Sadly they just wrote their chapter on the simplex algorithm too quickly from too little study. This is especially sad since there are many highly polished presentations of the simplex algorithm.
They got pushed into attention to linear programming, and the simplex algorithm, because of some important connections with some problems, e.g., flows on networks that they want to regard as part of computer science, where linear programming is a very important tool.
So, really, it's a strain to call 'flows on networks' computer science. Instead, it's a topic in applied math, back to Ford and Fulkerson, yes, with some by Dantzig, but more from Cunningham and Bertsekas, in particular, part of operations research. So, CS wants to hijack flows on networks. Not really good.
I omitted a more serious objection to the book: It makes a mess, a really bad mess, out of probability. Yes, in the study of the performance of algorithms, probability is important. So, once again, CS wants to borrow and use or just hijack some applied math and makes a mess. That at MIT they make such a big mess out of probability is something of a surprise. Still, in the US, the good courses in probability require both measure theory and functional analysis and are rare, even in math departments. Sad situation.
In using probability for performance of algorithms, in TACP Knuth did better: He stayed with a more elementary approach to probability and made it powerful enough.
E.g., in the book, I saw where they mentioned that the need for probability was that the data had a 'distribution'. Mostly that's not what have to pay attention to: E.g., don't much care about Gaussian, uniform, exponential, etc. Instead, what care about most of all is independence and, then, sometimes, lack of ties. Sad situation.
For both teaching and research, CS needs to clean up its act in math.
Still better, math should just open up, welcome, take in, and take over all the more important fields that are heavily math -- physics, economics, social science, electronic engineering, computing, operations research, etc. Instead of being one of the smallest departments on campus, teaching a few service courses, and otherwise struggling, math could be one of the biggest departments on campus, awash in both funding and students, and one of the most important pillars of growth in our economy.
I have an example: Some years ago I took a problem in practical computing and derived some new probabilistic math for a solution. Right, I used measure theory. I wrote prototype software, ran it on some real data, etc., and wrote a paper. So that I could get the paper in front of people in computing, where the applications are, I looked for journals in computer science. From one editor in chief of one of the best journals, a chaired prof of computer science at one of the best research universities, I got back "Neither I nor anyone on my board of editors has the prerequisites to review your paper.". Later I got almost the same statement from a second such person. For a third such person, at MIT, I wrote custom tutorials for two weeks before they gave up. But in the end the editor in chief of a good Elsevier journal seems to have walked the paper around campus and gotten feedback enough to get the paper reviewed -- the editor couldn't review it!
The paper was a nice contribution to computer science. Generally nice contributions will want some math. For all concerned, CS needs to learn some math.
Here's what they need to do: After calculus, get a good book on abstract algebra, pay full attention to the proofs, and learn some 'mathematical maturity'. Then get a good, first book on linear algebra and learn some important material, still paying attention to the proofs, and get more maturity. Then get Halmos, 'Finite Dimensional Vector Spaces' and learn from one of the best writers of math ever and get an introduction to Hilbert space theory. Then go carefully through Rudin's 'Principles'. Then do some more in ordinary differential equations where get to use both Rudin and Halmos. Then do some optimization -- e.g., pick from linear programming and some of Bertsekas. Then learn some measure theory, functional analysis, and probability based on measure theory. Cover basic stochastic processes, e.g., Markov, Gaussian, and martingales. Then learn some mathematical statistics. THEN return to computer science.
>The CS profs make a mess out of math.
Properly done CS _is_ maths. Maybe most of it is not in the branches you're interested in, but the core of CS is maths (think Turing, Church, Von Neumann, Codd, Hoare, Martin-Löf, etc.).
>it's a strain to call 'flows on networks' computer science.
I've always heard it called part of operations research, which happens to be an rather useful field to teach CS students. Yes, it is taught at probably a very basic level, but it is still useful as taught. And saying that:
>So, CS wants to hijack flows on networks. Not really good.
is disingenuous at best. Actual networks, like the one you're using now to post about your discontent with CS are basically run on computers, and are, not surprisingly, part of what CS people worry about. There's a whole field of very applied CS that's a direct application of some basic operations research results.
>For both teaching and research, CS needs to clean up its act in math.
In a general sense, yes, it would be good. Maybe you also need to read some better CS stuff?
>I have an example: Some years ago I took a problem in practical computing and derived some new probabilistic math for a solution.
You go on to rant how editors of CS journals weren't smart enough to understand your paper. That might well be the case, but it is obvious that you were not any smarter, sending a paper which is pure maths in nature to several CS journals, when the "problem in practical computing" was merely an application of your result, and not the main point of your paper. If you were a physicist working on some very deep results of quantum mechanics that happen to have a direct application to, say, molecular biology, you would still send it to a physics journal, not a biology journal, wouldn't you?
>Here's what they need to do:...
That's a good plan for learning a bunch of maths, not CS.
Okay, then you would agree with my thought on this thread that the math departments should just take over CS! The CS would get some much better math, and the math departments would get a big head and tummy ache from the much needed contact with applications. Fine with me.
"is disingenuous at best."
No. That chemistry uses some group theory for molecular spectroscopy and makes a mess out of it, which it has been known to do, doesn't mean that a mathematician who sits in a chair with plastic fake leather shouldn't comment. So, yes, IP routing has been based on some network shortest path algorithms. So, they used some operations research material since really it was operations research that first dug into networks that deeply -- yes, I know, there was a Nobel prize in economics for some work by Kantorovich (?) in the late 1940s on the transportation problem and, earlier, work in circuit theory as in Kirchhoff. Still, e.g., with Ford and Fulkerson and then Jack Edmonds, network shortest path and flows on networks should be attributed to operations research. If IP routing got to use it, then fine. Once I used Cunningham's version of the network simplex algorithm on a problem in allocating sales forces in a tricky situation: The problem looked like just integer linear programming, but if looked again it was just network flows where can get integer solutions for no extra effort. That doesn't mean that network flows should be part of courses in selling!
But CS is not just using network flows but calling the subject part of computer science. That's hijacking! Or it justifies my "Not really good.".
But, such things will happen. There is no law that says that have to be an operations research person to publish in an operations research journal or to publish about networks in a computer science journal. The NSF even works to encourage 'cross-cutting'.
Since my writing is so 'succinct', maybe I wasn't clear! If CS wants to take a field like network flows for their own, then actually do a competent job of it and don't mess it up. So, when there's is need, as there is, for the simplex algorithm, and not just using it but calling it part of CS, then do a competent job with the simplex algorithm. If probabilistic analysis of the performance of algorithms is to be part of CS, then CS should do a competent job with the probability. Else, CS is diluting the quality of these subjects. I argued elsewhere on HN that CS has diluted the meaning of dynamic programming, also essentially hijacked by CS.
If you want to say that CS done well is math, then they should do the math well.
When I was in grad school, I took some courses in measure theory and functional analysis from a department not the pure math department. And I took some statistics. When the statistics got to sufficient statistics, which is from the Radon-Nikodym theorem of measure theory, the prof totally blew it. I just walked out of the class; mostly I knew the material at the elementary level anyway, and at the level I wanted to learn the material the course was a waste of my time. Well, in the courses in measure theory and functional analysis, the profs maintained quality only slightly short of Bourbaki. They didn't have less than a beautifully polished proof for anything. Any hint or suggestion that there was a logical gap was a very big deal in the department. When I walked out of the stat course, the department dumped on me. Then I dumped back on the mess made of the R-N theorem. The next year the stat prof was gone. That department, not pure math, took the math fully seriously: A prof who blew a good proof of one important theorem was looking for a job. The situation was SERIOUS. We weren't a pure math department, but we did the math in rock solid ways. The department also had some operations research: Similarly. The math was rock solid. E.g., at one point in the Kuhn-Tucker conditions, I objected that a proof had used but not assumed continuous differentiability. I worked up a proof with just differentiability, and my proof was in the course the next semester.
So, broadly, just because we were interested in some math topics not common in pure math departments, and interested in applications, didn't mean we did the math at a lower level of quality. We were as close to Bourbaki as anyone. It can be done. CS should do it, too. Sorry 'bout that. Low quality is not good; I called out some low quality. I was fully correct to do so. The problem is not my arrogance but their low quality.
"In a general sense, yes, it would be good. Maybe you also need to read some better CS stuff?"
So, we are in agreement, "it would be good".
For my reading, that's about me, and that's not appropriate. The issue is the book CLRS or whatever it is called. I'm not the issue.
But for some "better CS stuff", you mentioned von Neumann. Right: In my favorite source of the R-N theorem, the proof is by von Neumann. In my current project, there's some math at the core, some original, and some due to von Neumann. I credit him and Kolmogorov.
For the paper I sent, I sent it to an appropriate journal. The motivation for the research was a problem in computer science. The main application for the original part of the research was just to that problem. That there was some original math at the core of the paper was part of the work as in your remark that CS should be math.
You are agreeing with my main point that CS should clean up its math and then calling me arrogant for making this point. Can't have it both ways.
For the course of study I outlined, what important about CS does that omit! I know; I know; it omits heap sort! And AVL trees. Gee, looks like that course of study needs more, maybe a lecture, maybe even two, of an hour each?
Do the math. For the CS, do that in the exercises and footnotes!
I really hope you were being sarcastic when referring to your writing as succinct. Anyway, who is claiming anything for their own? If some problem in CS leads to some new result in operations research, then a paper will be published in a nice operations research journal, and everyone will be happy. If the math is not good enough, the paper will not be published, and the author will have to rework it. Now maybe your claim is that CS journals with a focus on operations research are not sufficiently rigorous to your taste, but that's a different matter altogether.
>Okay, then you would agree with my thought on this thread that the math departments should just take over CS!
No, I don't. Firstly, CS is in itself a branch of maths, but in practice, most of the stuff that CS people do is of basically no interest to pure mathematicians, and vice-versa. Hence, I don't see any point in having a math department take over a CS department. Secondly, there are many things that normally fall within the purview of CS departments which are not at all related to maths (in any meaningful, abstract way), such as OSs, computer architecture courses, software engineering, compilers, etc. While all of those have a basis in maths, they certainly don not belong under a maths department. Of course it could be argued that there should be some "Applied CS department" or "Software Engineering" department or some such that would take those courses and research areas out of the "Pure CS" field, but that would end up doing a disservice to students and researchers alike.
>For the paper I sent, I sent it to an appropriate journal.
Sorry, but I disagree. If none of the reviewers, and none of the editors, or anyone they knew was able to understand your paper, either you wrote something incomprehensible, or you submitted it to the wrong venue. I don't doubt that you're a math genius who rocks measure theory and functional analysis, but I find it hard to believe that it an on-topic paper flew over the head of all the editorial staff and reviewers in any given area.
>You are agreeing with my main point that CS should clean up its math
Only up to a point. Better maths in CS research could be an improvement, as long as it doesn't veer into non-CS areas just for the sake of doing maths. I don't agree at all that CS students should master mostly unrelated areas of pure maths, though, as there are much more relevant issues within CS (plus its "applied" branches) and only so much time students can spend at the university.
>For the course of study I outlined, what important about CS does that omit! I know; I know; it omits heap sort! And AVL trees. Gee, looks like that course of study needs more, maybe a lecture, maybe even two, of an hour each?
I would think Donald Knuth would be in disagreement with you there. Also, your suggested program veered into pure maths for things that are 99.99999% out of scope in CS, while neglecting seemingly all applications of CS.
Also, I called you arrogant because that's how you come through in your writing. As I said, I don't doubt you're a very gifted mathematician, but from what you just wrote here, I think your grasp of actual CS topics is not so great.
"Anyway, who is claiming anything for their own?"
From CLRS and much more, it is fully fair to say that CS is "claiming" that linear programming (LP) is part of CS.
Beyond what I've mentioned so far about LP in CLRS, there is a much bigger reason to claim that CS is "claiming" LP: The history is that operations research wrestled with integer LP (ILP). There is a claim that for a while G. Dantzig, the inventor of the simplex algorithm, looked at ILP and guessed that he would be able to modify the simplex algorithm to handle integers easily. Of course, decades later, no one has!
So, slowly the image appeared: In worst case, for exactly optimal solutions, the ILP algorithms had running time exponential in the size of the input data. So, they were like total enumeration. Bummer. So, then, asymptotically, polynomial would be faster, and Jack Edmonds said that a 'good' algorithm had polynomial running time in the worst case.
Klee and Minty showed that with one of the most popular pivot rules, simplex had exponential running time; the assumption has been that with any pivot rule, simplex is exponential.
Practice showed that with the usual practical problems on an LP with m constraints, the running time was about 3m iterations and, thus, polynomial on average.
K. Borgward did some 'random geometry' and showed that on average simplex would have polynomial running time, explaining the 3m performance.
Eventually Shor, Khachiyan, etc. showed a polynomial algorithm for linear programming based on cutting planes for ellipsoids. Alas, apparently whenever the polynomial algorithm was faster than simplex, both ran too long to be practical!
So, for the first test of the importance of polynomial algorithms, the effort fell face down in the mud: Simplex is exponential worst case and polynomial average case, and the polynomial algorithms are essentially never faster in a practical way!
So, dear Bell Labs was working on designing communications networks, discovered the role of ILP, encountered the worst case exponential execution time, and got with the theory of NP-completeness and wrote:
Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.
Here can see the role of the 'satisfiability' (SAT) problem -- it is in NP-complete.
Presto! CS, long interested in 'computational complexity', especially running time, and, of course, regarding SAT as part of both EE and CS but not really operations research or optimization, takes NP-completeness as its own!
In money, students, profs, department sizes, headlines, etc., poor, little operations research, optimization, and even all of applied math can't compete with CS. So, CS grabs LP, ILP, network flows, NP-completeness, etc. along with SAT!
Okay, CS, it you are going to hijack all of 'combinatorial optimization', then realize that progress will require some good math research, and step up to the math.
Now back to this thread: So far, as in CLRS, CS is having trouble even writing with high quality about the simplex algorithm. So, putting combinatorial optimization and NP-completeness in the butter finger, dirty fingernails, unwashed hands of CS is a bad move for the future.
That's some of the larger story about the significance of CS hijacking topics from applied math.
Am I torqued? Sure: CS grabs the ball, claims to want to run with it, and then falls into the mud. I'm calling them out on it. It needs to be done.
"Throw me the ball! Throw it to me! I can score .... Splat." CS, even at MIT, too often can't even write with high quality about the simplex algorithm. REALLY big BUMMER.
Just like on a ball team, just ain't throwing CS the ball anymore. Again, they need to clean up their act in math. As CS hijacks LP, simplex, ILP, network flows, combinatorial optimization, and NP-completeness, they are getting into some of the hardest math research in all of history. For that they will need to be good at, would you believe, a junior level ugrad course in LP, and even there, even the MIT profs, need to 'pull up their grade'.
There's a war story: In some parts of 'enterprise software', a user gets to enter 'constraints'. E.g., let's figure out what we are going to do in the factory today. We know that want all the trucks loaded by 5 PM. Want all the painting done by noon so that it can be dry by 3 PM in time to be packed. Only have 2000 gallons of paint so whatever we do today has to use no more than the 2000 gallons. Etc. So, not really optimizing but are just 'satisfying'.
So, seeing this enterprise software problem, CS started the field of 'constraint logic programming'. Great! Hot new field! Charging forward!
Only a few weeks later, CS discovered that writing software to take just any collection of constraints and satisfy all of them is not so easy. I mean, even permitting using things as awesomely powerful as neural nets, AI, and, even, genetic programming, it wasn't so easy!
A few weeks after that they discovered that even if all the constraints are linear, it's not so easy! Soon they learned a lesson from operations research: They were looking for a feasible solution to an LP, and generally finding if there is a feasible solution is about the same 'difficulty' as finding an optimal solution. So, really, the linear 'constraint satisfaction' problem is not much different than just LP. Sorry guys. Better luck next time. Pick yourselves out of the mud and hit the showers.
So, SAP got interested in a French company that was interested in R. Bixby's LP software C-PLEX.
And the hot, new CS field of 'constraint logic programming' got to look a bit silly. Splat.
On my research paper, grow up! We're talking adult level activity here! No longer is it fair to plead that haven't covered that material yet! Instead, the goal is progress in research. If start with a computing problem, then the research is 'CS'. We do the research the best way we can. If we have a powerful, clean, rock solid solution with some new math theorems and proofs, then okay. So be it. That's just part of 'research'. If CS doesn't yet know this material, then maybe they will have to learn it.
Parts of academic finance learned about stochastic integration. Parts of mathematical physics learned about that math also along with Riemannian geometry and Hilbert space theory. Parts of chemistry learned about group representation theory. Parts of chemical engineering learned about ILP and dynamic programming.
Actually, reviewing my paper was not so difficult: I suspect that the editor in chief walked the paper to the math department, found a good probabilist, and got told "The math looks fine; I don't know what it means for CS.". Then he walked to the CS department, found an appropriate guy, and got told "It looks good for CS, but I can't say if the math is correct.". Done. How hard is that?
Grow up: The math is fair game. Not only that, the math is the main tool for the future of CS. If you didn't realize that, then you can say that you learned it first here. I can understand why one wouldn't get this lesson from CLRS!
Net big picture: Math is by a wide margin the oldest, deepest, most solid, most powerful, and most general subject in all of academics. Moreover, nearly uniformly, in all fields, the best progress is from 'mathematization' of the field. Get used to it! For CS, do the math. For the applications to computing, do that in the footnotes or the exercises!
For the CS topics you listed, e.g., programming languages, that field has for decades just cried out for some good math but gotten nearly none! Clearly compiling and executing a program are necessarily mathematically something, understood or not, powerful or not. For progress, we need to understand the subject mathematically. E.g., given a programming language statement, what are its mathematical properties so that given a sequence of two such statements, what are the mathematical properties? Can't see any? Okay: Change programming languages until can. Then with the properties, what can we conclude about the program? Anything useful, say, about correctness, running time, storage utilization, approaching limitations? Given some properties, can we have some code transformations with some known properties? Are some such useful? If not, can we define some useful programming languages that admit such transformations?
There are some simple, illustrative, pregnant cases that just leap off the screen: Write a collection of routines for sort by surrogate, i.e., finding a permutation, maybe honoring sort 'stability', applying a permutation to an array, chasing through the fact that each permutation is a product of disjoint cycles, etc. Then with such routines, will see some properties that are close to algebraic, e.g., where some combinations of the routines are the identity transformation, where one routine is the algebraic inverse of another, where we might have commutativity and/or associativity, or are equivalent to other combinations, etc. Can we preserve sort 'stability'? So, we see that we should have an 'algebra' of those routines and be able to derive known properties. Then we see that due to 'boundary' limitations, etc., our algebra is only roughly correct. So, maybe we should fix that.
This is old stuff. It has leaped off the screen for decades. We want some known properties we can use to derive new, useful properties. Instead all we get is programming languages that compete in some absurd 'beauty contest' or that 'encourage' programming 'styles' seen as 'helpful'. Sicko.
E.g., it has been common now in server farms to be concerned about reliability. So, we set up systems so that when system A gets too busy or fails, then system B takes over, etc. However, what we've seen, including at some of the most important farms, for decades, up to this year, is that these intuitive approaches far too easily go "splat" in the mud: They are 'unstable', have problems that propagate, and are surprisingly UNreliable.
So, we need some new math of 'reliability' for such server farms, math that can write us some guarantees. That math will start with the real problems, have definitions, theorems, and proofs, and, if successful, some solid tools for building reliable server farms.
All across computing, CS needs to give us progress, and for that they need to proceed essentially only mathematically.
It's the math. The CS is the math. Server farm reliability is just the application of the math and is not the CS. Ignoring math, CS is "A little people. A silly people."! Until CS gets serious about the math, it is writing checks its methodology can't cash.
To get serious about math, CS first has to learn LP well!
The would you believe probability? How about stochastic processes? Any stochastic processes in server farms and networks? Any uses of the axiomatic derivation of the Poisson process? Any roles for one of the strongest inequalities in math, the martingale inequality and the associated convergence theorem? Measure preserving transformations as in ergodic theory -- I'll answer that one, "Yes!". The renewal theorem and loads at server farms? How 'bout a little in probability?
Understanding now?
Not really, as your raving all over the place and still not making a lot of sense, argument-wise.
I guess I'll just agree to disagree, I feel bad for making your write so much.
Just a few of parting shots:
>Clearly compiling and executing a program are necessarily mathematically something, understood or not, powerful or not. For progress, we need to understand the subject mathematically.
If you think that there has been no progress in these areas, I'm sorry, but you really don't know what you are talking about. Could that progress have been faster, had the maths behind it been formalized? Maybe so, yet I don't see that many mathematicians working on branch prediction on deep pipelining processor architectures, and plenty of other things that lowly CS-ers have worked out. Want to see more maths in all of CS? Maybe you need to bring them to it, in the form of useful tools that can deal with fast moving targets.
>what are the mathematical properties? Can't see any? Okay: Change programming languages until can.
I regret to say that that's not as easy as it sounds. There are issues of tractability, and more importantly, there's this not-quite-cottage industry of software development, which needs good-enough languages to use _today_.
> this is old stuff. It has leaped off the screen for decades. We want some known properties we can use to derive new, useful properties.
You mean like Agda, Epigram, and countless other formal systems for program specification, derivation and correctness proving?
> Instead all we get is programming languages that compete in some absurd 'beauty contest' or that 'encourage' programming 'styles' seen as 'helpful'. Sicko.
This coming from a mathematician is strange to hear. Elegance and expressiveness are important when programming. It makes for succinctness and less bugs, and improves programmer productivity (which down here in the real world, means $$$).
>How about stochastic processes? Any stochastic processes in server farms and networks?
How about them? Plenty of very CS-oriented research based on stochastic processes. I should know, I did my doctoral research within a 45 person team on networks and network modelling, where most of the big guys were mathematicians. These people (not me, I do very applied stuff in a very bastardized field) breathe and live Markov processes and queuing systems. I don't see what you're complaining about here.
>E.g., it has been common now in server farms to be concerned about reliability. So, we set up systems so that when system A gets too busy or fails, then system B takes over, etc. However, what we've seen, including at some of the most important farms, for decades, up to this year, is that these intuitive approaches far too easily go "splat" in the mud: They are 'unstable', have problems that propagate, and are surprisingly UNreliable.
The folks over at Google would like a word or two with you on this.
> Until CS gets serious about the math, it is writing checks its methodology can't cash.
Maybe, and yet it seems to be doing not at all bad, as far as I can see. Would more and better maths be useful? Surely so. Would relegating CS to "footnotes" make any sense? We surely disagree there.
There's a whole continuum in CS, from the highly abstract and "math-y" to very applied stuff that has a very faint, if any, relation with what mathematicians normally worry about, and yet is critical for actual applications. I just find it odd that you don't see that fact.
There is a trend towards more maths in plenty of CS topics that were once just "practical stuff", so maybe the day will come when maths departments will branch out into real-world CS, and CS students will need more math, as you'd like. Given that we've been doing "maths" for 3K years, and CS for less than 100, you might need to wait a bit, though.
Anyway, thanks for the discussion, and have a nice weekend.
"I regret to say that that's not as easy as it sounds. There are issues of tractability, and more importantly, there's this not-quite-cottage industry of software development, which needs good-enough languages to use _today_."
I didn't say it was "easy", and clearly my point is progress and not current software development. Sure, for my project, I'm typing in code in Visual Basic .NET. For writing code today, all things considered for my context, that is about the best option.
But what I'm typing in is hardly different from what anyone might have typed in all the way back to Algol.
Here's the point: People type in all that code, and then what? Can some software go over it, report properties, do some transformations with known, useful properties? Not very much. Such things won't be better for Visual Basic than they were for Algol or anything between.
So, they type in the code, and then all they have is just that code. They can desk check it, test it, try it, revise it, etc., but it's all still digging the Panama Canal with a teaspoon one canal at a time. That is, there's no real automation and no significant exploitation of mathematical properties that could lead to automation.
Or, return to most of the rest of engineering where we have specifications of resistors, capacitors, inductors, transistors, fans, copper wire, steel sheets, aluminum bars, etc. with ohms, farads, density, tensile strength, electrical conductivity, etc. Okay, now compare with some DLL or its source code: What engineering properties do we have. Essentially none. It's like building with iron before we knew about tensile strength.
Sure, with some such research progress, eventually programmers would benefit. Obviously the intention is real progress in software productivity. We're not going to get such productivity by more of the same that got us C, C++, Java, Python, Visual Basic .NET, C#, etc.
Also for another of your points, I'm not talking about anything like branch prediction or deep pipelining. That's basically what to do with with the hardware to execute an existing instruction set.
Also the point is not math or not. The point is progress. Math will be necessary but not sufficient. That is, just stuffing in some math won't yield more than the old trick of putting two extra, unused transistors in a radio to claim nine transistors instead of seven.
Your point that there's a lot of good CS to do without 'mathematizing' the field is not promising for research or significant progress.
Maybe you should try something other than VB.NET, then. There are ways of constructing correct code, if you're patient enough, that is. If you're using the CLR, why not use F# instead of VB? That'd be a big step towards being able to prove some things about your code. Or if you really want to take out the big guns, go for Coq, Isabelle, Agda, Epigram, etc.
> Can some software go over it, report properties, do some transformations with known, useful properties?
Yes, in many cases. There's a whole lot of work in static code analysis, and refactoring tools. It's not perfect (the halting problem being non-decidable and all that) but there have been _significant_ improvements since the Algol60 days, and that's not counting functional languages and type-theoretic approaches.
> Or, return to most of the rest of engineering
That goes a bit off topic, but at the stage we are in, for most practical purposes, "software engineering" is not really engineering. Except maybe when done by NASA, but then again, that's not a practical approach either.
> Also for another of your points, I'm not talking about anything like branch prediction or deep pipelining. That's basically what to do with with the hardware to execute an existing instruction set.
Oh, but you were talking about compilers. Modern optimizing compilers have to take those things into account, among many other things.
> Clearly compiling and executing a program are necessarily mathematically something, understood or not, powerful or not. For progress, we need to understand the subject mathematically.
(from your previous post) My point was that very significant progress has been made in many fields, even if not necessarily formalized.
> Also the point is not math or not.
Sorry, but when you state that CS should be a footnote in a math book, you are kinda making the point that everything in CS (even in those sub-domains that are eminently practical) should be math-based to do anything meaningful. This is demonstrably not true.
> The point is progress.
And I've agreed with you on this. More and better maths can help advance CS. But we knew that already.
> Your point that there's a lot of good CS to do without 'mathematizing' the field is not promising for research or significant progress.
I contend that there has been significant progress in many CS areas without 'mathematizing' them. That is a fact. I also stated, in my previous post, that I agree that maths could help improve this progress. I think my problem with your position is that you're talking in absolutes in topics where those absolutes clearly don't hold.
I'm exaggerating, but, still there is a reasonable point here. CS is about some 'science', and call that the mathematical part where we have some solid material worth being called 'science', For the rest, call that 'computer practice' or some such.
The upside of my view is that for some serious progress we're going to have to use some serious methodology. So, I'm proposing if not mathematical physics envy then applied math envy. Applied math didn't take on how to design the display lights in a scientific pocket calculator although without the lights the thing wouldn't work.
My view is not the most extreme: Last year I communicated with a CS prof whose position was that CS is looking for the 'fundamentals of computation'. Hmm .... It sounds like he believes that the P versus NP question should be right at the top of the list, and I don't. I'll settle for anything that is solid and a contribution, even if small, to the 'science' and not just to current practice.
LIkely many people here know the current state of programming language research much better than I do. If that field has gotten nicely mathematical with some solid material, great. The progress from Fortran, Cobol, Algol, Basic, PL/I, Pascal, C, C++, etc. was pragmatic and important and of enormous value to the economy but not much progress in a 'science' of programming languages, and that progress, with poor methodology, has slowed as we might have expected.
Maybe I'm saying that, in 1920, if we wanted a really good airplane, then maybe we should set aside the wood, linen, and glue and go do some aerodynamiocs calculations, discover Reynolds number, and discover that those really thin wings were a mistake. Or, observational astronomy was just a lot of curiosity until Newton came along and made progress in understanding the universe. The practical chemists had discovered a LOT, but by applying quantum mechanics they made HUGE progress.
If we are going to make the huge progress we want in computing, then history suggests that we can't be just pragmatic and that "theory is under-rated". We can't expect that chemistry will do much to help CS, but the obvious tool is math, to turn CS, the science, part into some applied math.
"I'm sure that there is a lot of good material in that book, especially on core computer science topics."
If you look carefully, then you will find that as my first sentence.
I'm "aware" is about me, which is not appropriate, instead of about the book, which is appropriate, but, as explained early in the book, nearly no course covers the whole book.
But I was kind to the book: It made an even worse mess out of probability, and that material was farther from the back cover. Also see another post on this thread saying that generally in the book the proofs are poorly written.
"For those skimming the book, or perhaps more commonly, keeping it as a reference, it's a great compendium of algorithms references, much like a slightly more rigorous, paper version of Wikipedia." I can believe that, but it doesn't conflict with what I wrote. Indeed, I found and downloaded a PDF of the book for just the purpose you mentioned and that I mentioned in my first sentence: The book likely has some core computer science stuff, that is, not just poorly done, hijacked applied math that apparently I know much better than the authors, that I may be able to use as I finish the software for my server farm.
Gads, it looks like they want to use the approximation approach of starting with a minimum spanning tree to solve the traveling salesman problem in the plane. The idea also works in any Euclidean R^n. It's a CUTE idea. I first saw it in a paper of Karp who easily has some nice proofs of some astounding properties. Sadly in the book I saw some references for the idea but not from Karp, and I didn't see mention of some of the really nice properties. There's a chance of a biggie point there: For all the teeth grinding over NP-complete, that problem is NP-complete but surprisingly easy to solve with surprisingly good accuracy; so, the suggestion is that there is a crack in the armor of the NP-complete difficulty. That suggestion is actually more important than the problem itself which in practice people are not struggling with. Yes, the traveling salesman problem remains important, say, for production scheduling, but there the problem is not on a Euclidean R^n.
Some computer science is nice and useful. Hopefully there has been some such since I put down Knuth's TACP! So, maybe in some issues of handling deadlocks, transactions, race conditions, reliability via parallelism, and more, there will be something useful in the book it would take me more than 90 seconds to reinvent!
Still I'm correct: They should clean up their act in their math. We should get better from MIT.
I thought you were serious with all your writing, but after reading this bit, I can only conclude that you're either trolling, or delusional.
I nailed them on their description that the simplex algorithm was like Gaussian elimination for systems of linear inequalities.
No, The simplex algorithm is selecting elementary row operations to improve the value of the objective function.
Gaussian elimination also uses elementary row operations, but that is about the end of the direct connection. In particular, how Gaussian elimination selects elementary row operations is quite different from how simplex selects them.
For more detail, I explained the role of artificial variables where we just 'glue on' an identity matrix. So, since we just glue on an identity matrix, we never, directly in simplex, go through anything like Gaussian elimination to GET an identity matrix. Yes, at times, for numerical reasons, one should 'reinvert' the basis in simplex, and here Gaussian elimination, etc., might be used, but such 'reinversion' is not really simplex.
The authors mentioned Gaussian elimination when they should have mentioned elementary row operations. Next, what is special about simplex is improving the objective function, not working with linear inequalities. Indeed, simplex doesn't work with linear inequalities; instead, we just use 'slack' and 'surplus' variables to get a system of linear equalities (with non-negative variables) before simplex even gets the problem.
The authors were being sloppy. I called them out on it. It was appropriate that I do so.
If you believe that my remarks about simplex are in error, then by all means make your claims.
But the issue is not me; it's the book.
I found your additional input on the topic helpful, but I'm having trouble picking out more helpful insights about LP from all the other unrelated discussion.
So, the core really isn't Gaussian elimination for systems of linear inequalities.
For more, LP and the simplex algorithm are surprisingly powerful: Part of the reason is, for a huge range of optimization problems, taking a local linear approximation and then attacking that with simplex is often the best technique known. There are also surprising connections with combinatorial optimization and some classic NP-complete problems. What LP and simplex do on networks is also surprising and powerful; e.g., there simplex takes on a special form based on spanning trees.
"Introduction" is the first word in the title. Its intentions should be quite clear.
Maybe if I wrote twice as much as I did, then people would just find other objections, e.g., with length!
If you were more succinct, people would probably object to your writing less. Your verbosity clouds your meaning.
Early in my career, I got each volume of Knuth's TACP right away and dug in. No, I didn't solve all the exercises with stars! Later I had a course. The prof covered the high points of the sorting and searching volume in about two lectures. He was correct: Those were the high points. So, the prof gave an 'introduction', in two lectures. Knuth didn't give an 'introduction'. 1000 pages ain't an 'introduction' although in depth that book often is.
You are not concerned about the book but are torqued at me for some of what I said about the book. You took what I said personally, as if I was mean to your favorite baby.
You need to grow up.