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
problems.
Extend their knowledge in
or proceed to further study of complexity or
computational geometry.
Module Content
Convex Hulls: McMullen's upper bounds and matching lower bounds.
Davenport-Schinzel sequences.
Ben-Or's algebraic computation trees.
Evasiveness --- Rivest and Vuillemin.
Topological forms of evasiveness.
Module Prerequisite
MA1213 Introduction to Group Theory, MA1212 Linear Algebra.
Assessment Detail
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).