Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms
This paper documents our experience of adapting and using the QuickCheck-style approach for extensive randomised property-based testing of computational geometry algorithms.
The need in rigorous evaluation of computational geometry procedures has naturally arisen in our quest of organising a medium-size programming contest for second year university students—an experiment we conducted as an attempt to introduce them to computational geometry. The main effort in organising the event was implementation of a solid infrastructure for testing and ranking solutions. For this, we employed functional programming techniques. The choice of the language and the paradigm made it possible for us to engineer, from scratch and in a very short period of time, a series of robust geometric primitives and algorithms, as well as implement a scalable framework for their randomised testing.
We describe the main insights, enabling efficient random testing of geometric procedures, and report on our experience of using the testing framework, which helped us to detect and fix a number of issues not just in our programming artefacts, but also in the published algorithms we had implemented.
I am a lecturer (assistant professor) at University College London.
Prior to joining UCL, I was a postdoctoral researcher at IMDEA Software Institute (Madrid, Spain). I defended my PhD in 2012 in the DistriNet research group at the Department of Computer Sciences of KU Leuven (Belgium). Before that I received my MSc degree in Mathematics and Computer Science from Saint Petersburg State University (Russia) in 2008.
My research interests dwell in the area of the design and implementation of programming languages, including but not limited to program semantics, certified programming, concurrency and abstract interpretation. I am particularly interested in developing verification techniques and static analyses for higher-order and concurrent programs.
Tue 20 Sep Times are displayed in time zone: Osaka, Sapporo, Tokyo change
|10:35 - 11:00|
|A Glimpse of Hopjs|
|11:00 - 11:25|
|Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms|
Ilya SergeyUniversity College London, UKDOI
|11:25 - 11:50|
|Think Like a Vertex, Behave Like a Function! A Functional DSL for Vertex-Centric Big Graph Processing|
Kento EmotoKyushu Institute of Technology, Japan, Kiminori MatsuzakiKochi University of Technology, Japan, Zhenjiang HuNational Institute of Informatics, Japan, Akimasa MorihataUniversity of Tokyo, Japan, Hideya IwasakiUniversity of Electro-Communications, JapanDOI
|11:50 - 12:15|
|Datafun: A Functional Datalog|