Module MA341a: Computational complexity, mostly geometry
 Credit weighting (ECTS)
 5 credits
 Semester/term taught
 Michaelmas term 201617
 Contact Hours
 10 weeks, 3 lectures including tutorials per week

 Lecturer
 Prof. Colm Ó Dúnlaing
 Learning Outcomes
 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.
 DavenportSchinzel sequences.
 BenOr'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 2hour 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).