The test will covering these new topics

• Minimum spanning trees and Prim Algorithm (Section 12.1)
• Matroids definition, and associated definitions, independent set, dependent set, basis, cycle/circuit,
• Matroid characterization - Theorem 12.5

The test will also have questions which cover some these older topics

• General form, canonical form and standard form of an LP and converting between forms
• drawing the feasible region LP in the plane
• basic feasible solutions and their associated basis
• simplex tableaus
• lex positive, lex negative, lex zero, lexicographic ordering
• lexicographic simplex
• two phase simplex
• simplex method as a series of pre-multiplications by special matrices (any necessary formulas will be provided)
• Bland's algorithm
• definitions related to convexity: convex combination, convex set, hyperplane, halfspace, polyhedron, extreme point, facets and vertex.
• relationship between extreme points of a polyhedron, vertices of a polyhedron and the set of feasible solutions of a LP in standard form
• Duality, dual of an LP in canonical form, dual to an LP in standard form, dual of an LP in general form
• weak duality, strong duality
• dual simplex method
• Farkas Lemma (Theorem 3.5)
• Matrix games, pure strategy, mixed strategy, minimax theorem
• complementary slackness (section 3.4)
• shortest path problem as an LP (Section 3.4),
• revised simplex method (section 4.1),
• revised simplex method for max-flow (section 4.3)
• Primal dual algorithm (section 5.1 and section 5.2)
• Primal dual applied to shortes path (section 5.4)
• Primal dual applied to max flow - Ford-Fulkerson, (section 5.6 and section 6.1), Ford Fulkerson algorithm, Theorem 6.2 (min-cut,max-flow), Theorem 6.3 (Ford Fulkerson terminates)
• Definitions: the value of a flow, augmenting path, s,t-cuts, the capacity of a cut,...
• Application of the Ford-Fulkerson (maximum matching in bipartite graphs, edge verison of Menger's Theorem)
• Floyd-Warshall algorithm
• Introduction to Integer Linear Programming (ILP), representing problems as ILPs (examples:TSP and satisfiablity)
• Totally unimodular matrices (section 13.2)
• Lexicographic dual simplex algorithm (section 14.2)
• Gomory cutting plane algorithm (section 14.1)