**1 Schedule**

Problem sessions:

The homework is **due Nov** **18, 2008**.

The **QUIZ** will be on **Tuesday, Nov. 25**.

**2 List of algorithms covered in the class**

(B-basic, I-intermediate, A-advanced):

I: Gaussian elimination (p. 219, DSV).

I: Computing the dual of a linear program (p. 206, DSV).

A: The simplex algorithm (p. 213, DSV).

B: Zero- sum games using linear programming (p. 208, DSV).

A: Max-flow using linear programming (p. 198, DSV).

##

**3 Basic material**

**Important concepts, problems, theorems, and algorithms:**

• system of linear equations, rank of a matrix,

• linear program , dual linear program,

• basic matrix notation.

** Testing method :**

• Solve a small linear program (2-3 variables).

• Solve a system of equations using Gaussian elimination (up to 4 variables).

• Given a system of equations , write it in a matrix form.

• Compute rank of a matrix.

• Solve a zero -sum game.

**Example problems:**

**5.1 (due Nov 18, 2008)** Solve the following linear program:

**5.2 (due Nov 18, 2008)** Solve the following system of equations using
Gaussian elimination:

**5.3 (due Nov 18, 2008)** Write the following system of equations in the
matrix form Ax = b:

**5.4 (due Nov 18, 2008)** Compute the rank of the following two matrices

Does the system 2x + 4y + 9z = 3, x − 3y + 5z = −1, 10y − z = 5 have a
solution?

**5.5 ( removed )**

**5.6 (due Nov 18, 2008)** Solve the following linear program:

**Use a linear programming solver** to obtain the solution (for example
you can use freeware lpsolve or function

Maximize in Mathematica (installed in most labs)).

**5.7 (due Nov 18, 2008)** There are n bottles which contain different
mixtures of three chemicals called A,B,C.

The i-th bottle contains the chemicals in ratio a _{i} : b_{i} : c_{i} (thus, a_{i}/(a_{i} +b_{i} +c_{i})
fraction of the i-th bottle is chemical

A, b_{i}/(a_{i} +b_{i} +c_{i}) fraction of the i-th bottle is chemical B, and c_{i}/(a_{i} +b_{i} +c_{i})
fraction of the i-th bottle is chemical

C). We want to know whether it is possible to obtain a mixture containing the
chemicals A,B,C in ratio a : b : c by

mixing various amounts from the bottles. Give an efficient algorithm for this
problem.

For example, if the input is n = 2, the ratios in the bottles are 1 : 1 : 2 and
3 : 3 : 1, and we want to obtain

mixture with ratio 1 : 1 : 1 then the answer is YES (we can take 2 parts from
the first bottle and 1 part from the

second bottle).

**5.8 (due Nov 18, 2008) **Construct the linear program
dual to the following linear program:

Find the optimal solution of the primal and the dual
problem. Use a linear programming solver to obtain the

solutions.

Try to solve the following problems. A few of them **will be** on the quiz.
We will go over the ones that you choose in

the problem sessions.

• 7.1, 7.2, 7.3, 7.4, 7.7, 7.8, 7.11, 7.12, 7.13, 7.15, 7.19, 7.27.