Mathematics

This two-part talk will cover the basics of algorithm design and analysis and an overview of computational complexity theory.  The list of topics will be drawn from: greedy, divide & conquer and dynamic programming algorithms; polynomial time; P, NP and NP-complete; reductions; approximation algorithms; approximation schemes, constant factor and logarithmic factor approximation ratios; APX-hardness.  The talk will assume no background in algorithms and complexity, but will include pointers to the most recent results in each area and open questions.