6 ms·

I'm sure that there is a lot of good material in that book, especially on core computer science topics. But the book is only an 'introduction' since for many o

I'm sure that there is a lot of good material in that book, especially on core computer science topics. But the book is only an 'introduction' since for many of the topics for serious interest in practice it will be important to go deeper than the book. 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.

coliveira 15y ago
"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.
- NY_Entrepreneur 15y ago
  Learning 'math' as a good ugrad or grad student is NOT easy and involves a special step often called 'mathematical maturity' where the student learns to be good at reading and writing definitions, theorems, and proofs in math. This step is NOT easy to learn and in practice is nearly impossible to learn without some careful teaching. The usual place to learn the step is in a very precise course, with a lot of very well graded homework, in abstract algebra and then to strengthen the learning via very precise courses in advanced calculus and, maybe, point set topology or measure theory. Without that step, nearly no one knows how to do well writing definitions, theorems, and proofs in math. 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.

coliveira 15y ago

"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.

NY_Entrepreneur 15y ago
Learning 'math' as a good ugrad or grad student is NOT easy and involves a special step often called 'mathematical maturity' where the student learns to be good at reading and writing definitions, theorems, and proofs in math. This step is NOT easy to learn and in practice is nearly impossible to learn without some careful teaching. The usual place to learn the step is in a very precise course, with a lot of very well graded homework, in abstract algebra and then to strengthen the learning via very precise courses in advanced calculus and, maybe, point set topology or measure theory. Without that step, nearly no one knows how to do well writing definitions, theorems, and proofs in math. 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.