Advanced Algorithms

3 Units

Design and analysis of efficient algorithms, with emphasis on network flow, combinatorial optimization, and randomized algorithms. Linear programming: duality, complementary slackness, total unimodularity. Minimum cost flow: optimality conditions, algorithms, applications. Game theory: two-person zero-sum games, minimax theorems. Probabilistic analysis and randomized algorithms: examples and lower bounds. Approximation algorithms for NP-hard problems: examples, randomized rounding of linear programs. Prereq: ( CSDS 310 or CSDS 410 ) and ( MATH 201 or MATH 307 or EPOM 420 ). Prereq or Coreq: MATH 380 or OPRE 207 or STAT 301 or STAT 312 or STAT 313 or STAT 332 or STAT 333 .