Seminar (Combinatorial) Algorithms, Spring 2012

Current Edition. For the previous year, spring 2011, see here. And in 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.

Dates: Thursday mornings, 9:15-11:00 hours; February 9 - May 10, 2012. Room 405, Snellius.

This year's book is Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (3rd ed.), 2009, MIT Press and McGraw-Hill.

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 2011, 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 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 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). See here for a template. Deadline: one month after the presentation.
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

Email at liacs (or at Gmail).
nameemailremarks
Alberto Baggio baggio.alberto87 @G
Bas van Stein bas9112 @G
Erik Zandvliet ezandvli
Frank van Rijn fwvanrijn @G
Hao Wang wangronin @G
Hervé Kabamba hkabamba
Jim (Yuxiang) Liu liuyuxiang66383 @G
Martin Wimmers mwimmers
Oswald de Bruin snake.ossi @G
Tom Groentjes gentleman281083 @G
Yi Wang csimplestring @G

Deliverables

subjectwhoremarks
Red-black trees Erik & Oswald ✓ first version checked by W; second version checked by HJ; final
Amortized analysis Alberto & Hervé ✓ first version checked by W; second version checked by HJ; final
Van Emde Boas trees Frank & Martin ✓ first version checked by HJ; second version checked by W; final
Topological sort & Strongly connected components    Bas & Tom ✓ first version checked by W; second version checked by HJ; final
All pairs shortest paths Hao & Yi ✓ first version checked by W; second version checked by HJ; final
Maximum flow Jim & Erik ✓ first version checked by W; second version checked by HJ; final
Fast Fourier Transform Martin & Oswald    ✓ first version checked by W; second version checked by HJ; final
String matching Alberto & Tom ✓ first version checked by W; second version checked by HJ; final
Computational Geometry Yi & Hervé ✓ first version checked by W; second version checked by HJ; final
Medians Hao & Frank ✓ first version checked by W; second version checked by HJ; final
Approximation algorithms Jim & Bas ✓ first version 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. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (3rd ed.), 2009, MIT Press and McGraw-Hill.

Questions/remarks: kosters@liacs.nl.

September 27, 2012 — http://www.liacs.nl/home/kosters/semalg/index2012.html