## Math 340 Assignment/Quiz/Exam Info

### Main Page — Lecture schedule

Each week there will be either a quiz or an assignment (or a midterm), the details of which will be on this page. There will be a total of 5 quizzes and 5 assignments throughout the semester (with more quizzes at the beginning and more assignments towards the end).

• Quiz 1 - Friday Sept 15 (Solution)
• This quiz will cover things through Wednesday Sept 13:
• Linear programs in standard form (suggested problems: Chvátal 1.1, 1.2)
• Feasible/infeasible/unbounded linear programs (suggested problems: Chvátal 1.3, 1.4)
• Solving 2-variable linear programs graphically (suggested problems: try this for any of the 2-variable linear programs in the exercises of Chvátal ch. 2 or Vanderbei ch. 2)
• Rewriting a linear program in standard form with slack variables (suggested problems: try this for any of the linear programs in the exercises of Chvátal ch. 2 or Vanderbei ch. 2)
• Quiz 2 - Friday Sept 22 (Solution)
• This quiz will cover things through Wednesday Sept 20:
• The simplex method (suggested problems with feasible initial dictionaries: Exercises 2.1, 2.2 of Chvátal; also any of 2.1, 2.2, 2.8, 2.9 of Vanderbei you want to do).
• The two-phase simplex method for infeasible initial dictionaries (suggested problems: Exercise 3.9 of Chvátal; also any of 2.3-2.7,2.10 of Vanderbei you want to do).
• (Feel free to use computer tools to help with the simplex method computations - just remember, on the quiz you'll have to do it by hand, and it will be designed to be reasonable to do by hand).
• Quiz 3 - Friday Oct 5 (Solution)
• This quiz will cover things through Wednesday Oct 3:
• The definition of the dual to an LP, and its relation to the primal. (suggested problems: Chvátal 5.1-5.2, Vanderbei 5.1-5.4, 5.6)
• Midterm: in class on Friday October 20. (Version 1 Solutions and Version 2 Solutions)
• A past exam for practice (and its Solutions). We won't cover the revised simplex method before the exam, so that sort of problem won't be on our midterm.
• Problem 5 as stated also isn't something that could be on our exam, because it involves duals to LPs with free variables / equalities. Sorry I didn't notice that when I posted it! For a problem that could be on our exam you could replace it with "prove that either there exists a x0 such that Ax0 and c·x>0, or a y0 with ATyc, but not both."
• Topics covered by the midterm are as follows.
• Linear programs (especially in standard form) and what it means to be infeasible, unbounded, or to have an optimal solution. (Chvátal Ch. 1 / Vanderbei Ch. 1)
• The simplex method, following the standard rule: dictionaries, how to pivot for a feasible dictionary, and understanding uniqueness or non-uniqueness of optimal solutions. (Chvátal Ch. 2 / Vanderbei Ch. 2)
• The two-phase simplex method for initially infeasible dictionaries. (Chvátal Ch. 3 / Vanderbei Ch. 2.3)
• Degeneracy, the possibility of cycling, and anti-cycling methods. (Chvátal Ch. 3 / Vanderbei Ch. 3)
• Matrix formalism for linear programs and for dictionaries (Beginnings of Chvátal Ch. 7 / Vanderbei Ch. 6)
• The dual to a standard form LP, weak and strong duality, (Chvátal Ch. 5 / Vanderbei Ch. 5)
• Applications of duality: the theorem of the alternative, complementary slackness, and the economic significance of dual variables. (Chvátal Ch. 5 / Vanderbei Ch. 5)
• Quiz 4 - Friday Oct 27 (Solution)
• This quiz will cover the revised simplex method. (suggested problems: Chvátal 7.1-7.2; Vanderbei 6.1-6.3, minus the parts about dual vectors/solutions)
• Quiz 5 - Friday Nov 10 (Solution)
• This quiz will cover problems in general form, and the dual simplex method. (Suggested problems: Chvátal 9.1, 9.2; Vanderbei 5.6 (via the dual simplex method)).
• Final Exam: December 5 at noon, Henry Angus building room 098.
• The exam covers the entire contents of the course, so roughly Chvátal chapters 1-5, 7, 9, and 10, plus the additional topics discussed at the end (and of course minus the things not covered in class, such as eta factorization in chapter 7).
• Old exams are available on the department website. Unfortunately these don't have solutions; however, if you try them I can check if what you're doing looks right, and tell you whether or not a given problem would be reasonable for this semester's final.
• Some practice problems for the topics of the last week or so from the course, and Solutions. Questions 3 and 4 here are taken from past exams, and are a bit trickier than would be reasonable on ours (past semesters have spent more time on matrix games, I think).

For homework assignments, you may collaborate, but each person must write up their solutions independently in their own words. Two or more people turning in identical homework assignments are in violation of the UBC academic integrity code and will be given a 0. Late homeworks may not be accepted.

At the end of the semester, your lowest quiz grade and lowest homework grade will be dropped. This policy is intended to cover situations where you may miss a quiz or assignment for whatever reason, without you needing to come to me to ask for a concession. Beyond this, missed quizzes, assignments, or midterms will be given a 0 by default - the only exceptions to this are by instructor permission beforehand, or in the case of a medical emergency notifying me within 48 hours and presenting a doctor's note. In such cases there will be no make-up quiz or exams; your grade will be determined from your other work throughout the term.