On successful completion of this module, students will be able to
Understand the principles of computational complexity.
Be aware of applications of linear algebra, group
theory, and topology, to the complexity of geometric
Extend their knowledge in
or proceed to further study of complexity or
Convex Hulls: McMullen's upper bounds and matching lower bounds.
Ben-Or's algebraic computation trees.
Evasiveness --- Rivest and Vuillemin.
Topological forms of evasiveness.
MA1213 Introduction to Group Theory, MA1212 Linear Algebra.
This module will be examined
in a 2-hour examination in Trinity term.
Fortnightly written assignments will count 10%, and
90% for the final.
Supplementals are normally not available in this module (except in the
case of JS TSM pattern A students).