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.