COMP SCI 3AC3 - Algorithms and Complexity

3 unit(s)

Basic computability models; the Church-Turing thesis, complexity classes; P versus NP; NP-completeness, reduction techniques; algorithmic design strategies; flows, distributed algorithms, advanced techniques such as randomization.
Three lectures, one tutorial (one hour), second term
Prerequisite(s): COMP SCI 2C03, COMP SCI 2FA3
Not offered before 2015-16.