Seminar on Combinatorial Pattern Matching

Advanced studies
This seminar will be a kind of retrospective on the Annual Symposium on Combinatorial Pattern Matching (CPM). We will look at both the key and more obscure results that have appeared at the conference over the last 25 years, with the aim of uncovering interesting open problems and paths less travelled.
Year Semester Date Period Language In charge
2015 autumn 07.09-07.12. 1-2 English Simon Puglisi


Time Room Lecturer Date
Mon 14-16 C220 Simon Puglisi 07.09.2015-12.10.2015
Mon 14-16 C220 Simon Puglisi 26.10.2015-07.12.2015


Combinatorial Pattern Matching is a field of computer science concerning the search for (and discover of) patterns in discrete structures, such as strings, trees, and graphs. For the last 25 years the main venue for results in the field has been CPM: the Annual Symposium on Combinatorial Pattern Matching. This seminar will be a retrospective on CPM, highlighting a dozen (or so) of the papers that have appeared at the conference over the years. We will rummuge through the attic, covering both "important" and quirky results, shedding light in the dark corners, with the aim of uncovering fruitful directions for furture work.

Completing the course

The main aim of the course is for students to get an idea of the kind of research done in the CPM community by closely examining a few research papers. The (rough) idea is to select a couple of seed papers that have been published in CPM (preferably prior to 2004), study those papers and the work that has been done on those topics since (including that published outside of CPM), and arrive at a solid understanding of the topic/problems and some ideas for future research.

In the first 3-4 weeks of the course your task is to dig around in the CPM proceedings and find a (small) set of articles you are interested in. It might be advisable to choose a few different topics, because I might tell you that one of them is not suitable (for some yet to be defined reason).

At the half-way point (12.10.2015) we might have a meeting where we each briefly present the topic/problem definitions we have picked (TBD).

To get a mark you can submit a typed report (approximately 10 pages, a kind of mini survey), or give an presentation (of approximately 40 minutes in length) at the end of semester.

Throughout the term I will also advertise relevant research talks on the course web page. These research talks will usually be given by visitors to our group, and will fall in the broad area of CPM. You should attend at least three of these guest talks.

Literature and material

You can access the CPM symposium proceedings via DBLP here.

You should be able to access articles freely when on campus. If you're off campus, then you should first connect via the VPN.

Relevant talks:

Andrea Farrugia, Optimized Lempel-Ziv Data Compression, 14:00, 08.09.2015, room A218.

Matthias Petri, Compressed Suffix Trees for Machine Translation, 14:00, 09.09.2015, room B119.

Simon Gog, Flexible Document Retrieval, 14:00, 10.09.2015, room B119.

Marco Previtali, Queries on colored variable-order de Bruijn graphs, 15:15, 10.09.2015, room C222.

Juho Lauri, On the Complexity of Rainbow Coloring Problems, 16:15, 10.09.2015, room C222.