Seminar (Combinatorial) Algorithms, Spring 2011

Current Edition. For the previous year, spring 2010, see here.

Contents | Schedule | Participants | Deliverables | References


The Seminar (Combinatorial) Algorithms is intended for Master students in Computer Science. Lectures are in English. The seminar is organised by dr. H.J. (Hendrik Jan) Hoogeboom and dr. W.A. (Walter) Kosters.

The seminar will also be given in spring 2012. The subject is not determined yet.
Dates: Thursday mornings, 9:15-11:00 hours; February 9 - May 10, 2012. Room 405, Snellius.

In 2011 we studied the book: R.A. Hearn» and E.D. Demaine», Games, Puzzles, & Computation, Peters, 2009.
Dates: Thursday mornings, 9.15-11.00, February 3 - April 28, 2011. Place: Snellius, room 401

The first lecture will cover some background. In the first half of the semester every student presents a part from the book above. After that students should study recent literature and present their results. (And perhaps even some programming?) Meetings are on a weekly basis. Students can also suggest neighbouring subjects. For a somewhat more detailed list, see below.
Credit points: 6 ECTS. There is no written exam.

Prerequisites: Algorithms, Complexity, Datastructures (all at bachelor's level, see for instance the Dutch course pages Datastructures and Complexity).

Students should register in advance, in December 2010, by personal visit to the organizers. The number of participants is at most 8 (approximately :).

Contents

In this seminar we will discuss several issues dealing with combinatorial algorithms, as described in the book mentioned above.

Students are supposed to present and discuss chapters of the book, and perhaps papers, during class. The setup depends on the number of participants.
Subjects are presented by the students in two one hour lectures (i.e., twice 45 minutes); more precisely, every student student takes care of one one hour lecture. Next to the oral presentations (using PDF or PowerPoint slides, with the additional help of the blackboard) ±eight page self-contained essays on the subject must be written (in LaTeX; in English/Dutch). Deadline: one month after the presentation. The next presenter is also asked to review the paper by his/her predecessor.
Essays should be improved until students and organizer agree on the contents. Students must be present during all sessions, and are supposed to actively take part in the presentations, e.g., ask questions. Immediately after each lecture there is a short discussion between students and organizer, where the presentation is evaluated. The first meeting is used to make a proper schedule. Every student is supposed to choose and present at least two subjects, one in the first half and one in the second half of the seminar.
You can use your own laptop for the presentations. If you don't have one available, you can use ours — let us know in advance! In that case, please email the .ppt- or (preferably) .pdf-files a day before the presentation — at the latest. It is wise to also put them on a memory-stick. A beamer is always available.

Schedule

Participants

nameremarks
Giso Dal READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓
Marius Gheorghe READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓
Wei Liu READY: first paper checked by HJ.; second version checked by W.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓
Jan van Rijn READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by HJ.; second version checked by W.; final ✓
Jurriaan Rot READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by HJ.; second version checked by W.; final ✓
Frank van Smeden READY: first paper checked by HJ.; second version checked by W.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓
Barry van Veen READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓
Sander van der Vlugt
Bob Wansink READY: first paper checked by W.; second version checked by HJ.; final ✓
READY: second paper checked by W.; second version checked by HJ.; final ✓

References

References are either books or papers, see below. Books are usually available in room 159. Remember that most doi's can only be used from computers within the university domain. Many other books and the internet may be helpful.

  1. R.A. Hearn, Games, Puzzles, and Computation; PhD thesis, MIT, 2006.


Questions/remarks: kosters@liacs.nl.

June 14, 2012 — http://www.liacs.nl/home/kosters/semalg/index2011.html