Skip to main content

Trinity College Dublin, The University of Dublin

Trinity Menu Trinity Search

School of Mathematics

You are here Courses > Undergraduate > Courses & Modules

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
 
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.
  • 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).