Within our ADA group, we are passionate about the cutting-edge research we do, but we are also always keen on sharing our passion with others – most recently, with a group of talented high-school students, some of whom we hope will become part of the next generation of advanced computer science researchers.
Students from several VWOs (secondary school for future university students) of Leiden and neighbouring cities came to the Leiden Institute of Advanced Computer Science (LIACS) to get a hands-on experience of computer science and to see if they would like to join our university as bachelor students in 2019.
15 top students participated in this introductory course. First, they got an introduction to networks and shortest path algorithms from Dr. Michael Emmerich (Associate Professor at LIACS). Then, the ADA group took the torch: Dr. Holger Hoos (Professor of Machine Learning), Marie Anastacio and Can Wang (PhD candidates) set out to give them a taste of computational complexity and some of the techniques used to deal with complex problems.
To do so, we built on the shortest path idea and worked with out pre-university students on the travelling salesman problem (TSP). The TSP involves finding a shortest, quickest or cheapest round trip visiting a number of locations – e.g., cities or villages. It is one of the most widely studied problems in computer science and has a broad range of important applications in logistics, manufacturing and even biology. We helped the students to discover effective techniques for finding shortest round trips visiting various locations in the Netherlands and introduced them to slightly simplified versions of the best known algorithms.
More precisely, endeavoured to find the shortest tour visiting every provincial capital of the continental Netherlands (by bicycle, of course). As we bet on the length of the resulting “grand tour of the Netherlands”, almost all of our ADA group members overestimated the size of the country, and we were all surprised by the result. Somewhat embarrassingly for our Dutch group members, the winner of our little game was Chuan, our Chinese postdoc. To give Dutch national pride a second chance, we asked each of our high-school students to place a bet on the length of the optimal tour. The best of these bets came from Jonas, who precisely tied with Chuan – estimating the shortest bicycle your through the 12 provincial capitals at 900km. We decided to declare him the winner of our game, breaking the tie in favour of the younger and less experienced student.
The actual shortest tour is 1013.45 km long and would take around 52h to cycle, according to Google Maps:
Working with the pre-university students was a very interesting and highly enjoyable experience for all of us, and we look forward to doing it again next year. As for our college students, we hope to meet them again soon. And who know, perhaps one day, we’ll cycle the tour …