Abstract: Computational Geometry (CG) is an elegant field of Computer Science, whose roots originate in antiquity. The benefits of computational geometry applications have brought to us in areas such as fast geolocation, robotics, data clustering and image recognition, to mention just a few. What makes the CG problems so unique is the simplicity of their formulations: “How to guard a gallery?”, “How to move a sofa bed with less effort?”, “How to stay away from dangerous neighbourhoods?”, combined with the fact that most of them require truly ingenious approaches to be solved efficiently, or simply turn out to be NP-hard.
In this talk, I will share my experience of using Computational Geometry for Fun and Education, turning its various NP-hard problems into programming competitions for 2nd year students of the Computer Science department at University College London. The intuitive and practical nature of the suggested problems made them easy to motivate, while the inherent computational complexity encouraged the teams to try and combine multiple approaches, in their attempts to earn a better score in the overall ranking. The competitions, which were running for two years now, were greatly enjoyed by the participants (~120 students each year), and are now are a part of the UCL CS curriculum.
About the speaker: Ilya Sergey from University College London (UCL). Dr. Sergey is a Lecturer (Assistant Professor) in the Department of Computer Science at UCL. He is doing research in programming language theory, i.e., types, semantics, and software verification. At the moment, he is focusing on developing scalable and sound methodologies for building provably correct concurrent and distributed systems. For his work, he writes a lot of mechanized proofs in Coq, as well as functional code in Scala, Haskell, and OCaml.