Discrete optimization

This course is an introduction to linear and discrete optimization which is a ubiquitous paradigm in modern data science. Warning: This is a mathematics course! While much of the content will be about algorithms having impact in practice, we will look at these from the angle of a mathematician/theoretical computer scientist. The most important prerequisite is advanced linear algebra I&II. 

Syllabus:

• Linear optimization problems
  
• Convex geometry: Polyhedra, convex sets, Farkas' Lemma
• The simplex algorithm, duality
  
• Zero sum games: Von Neumann's theorem 
• Analysis of algorithms: Gaussian elimination and running time of simplex algorithm
  
• Ellipsoid method and convex optimization problems