Module MA341a: Computational complexity, mostly geometry
- Credit weighting (ECTS)
- 5 credits
- Semester/term taught
- Michaelmas term 2016-17
- Contact Hours
- 10 weeks, 3 lectures including tutorials per week
- 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
- Extend their knowledge in
or proceed to further study of complexity or
- 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).