Current Edition.  

Seminar Combinatorial Algorithms (Spring 2010)

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

In spring 2011 we will organize a similar seminar. The precise subject is not yet known at the moment, but will be in the same vein — whatever that means. Probably: R.A. Hearn and E.D. Demaine, Games, Puzzles, & Computation, Peters, 2009. (But if in the meantime P appears to be different from NP, we will examine that.)
Dates: Thursday mornings, 9.15-11.00, February 3 - April 28, 2011. Place: Snellius, room 401

The seminar examines algorithms as they appear in the (current) last volume of Donald Knuth's seminal work. The first lecture will cover some background. Then, 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.
Dates: Thursday February 4 - Thursday April 29, 2010; 9.15-11.00. Room 401 (or 412), Snellius, Niels Bohrweg 1, Leiden. Credit points: 7 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 2009, by personal visit to the organizer. The number of participants is at most 8 (approximately :).

Contents

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 student takes care of one one hour lecture.. Note that this year's lectures are in Dutch. Next to the oral presentations (that perhaps make use of PowerPoint or PDF, but the blackborad is also fine) 8 page self-contained essays on the subject must be written (in LaTeX; in 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 .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

=============BDD's=======================
• Thursday February 4, 2010, 9.15, room 402: first meeting — 1st lecture
  Walter Kosters: Introductory lecture, pp. 70-73
• Thursday February 11, 2010, 9.15, room 401: 2nd lecture
  Jonathan Vis: pp. 73-75
• Thursday February 18, 2010, 9.15, room 401: 3rd lecture
  Giso Dal: pp. 76-78; Sjoerd van Egmond: pp. 78-80
• Thursday February 25, 2010, 9.15, room 403: 4th lecture
  Sjoerd van Egmond: exercise 55; Bob Wansink: pp. 81-83
• Thursday March 4, 2010, 9.15, room 401: 5th lecture
  Tom ter Laak: pp. 84-85; Rick van der Zwet: pp. 86-88
• Thursday March 11, 2010, 9.15, room 401: 6th lecture
  Rick van der Zwet: exercise 63; Erik Jongsma: pp. 101-107; Johan de Ruiter: pp. 117-120
• Thursday March 18, 2010, 9.15, room 401: 7th lecture
  Johan de Ruiter: pp. 117-120 (continued); Wouter de Zwijger: pp. 121-122

  =============N-Queens=======================

• Thursday March 25, 2010, 9.15, room 401: 8th lecture
  Jonathan Vis: papers by Chatham et al.; Sjoerd van Egmond: papers by Sosic and Gu ("efficient" and "3,000,000")
• Thursday April 1, 2010, 9.15, room 401: 9th lecture
  Bob Wansink: paper by Han Jing et al. (Alife); Hendrik Jan Hoogeboom: BDD's, master profiles
• Thursday April 8, 2010, 9.15, room 401: 10th lecture
  Giso Dal: paper by Keating about Hopfield networks; Tom ter Laak: paper by Erbas, Sarkeshik and Tanik ("perspectives")
• Thursday April 15, 2010, 9.15, room 401: 11th lecture
  Rick van der Zwet: paper by Cournia; Erik Jongsma: Quantum papers
• Thursday April 22, 2010, 9.15, room 401: 12th lecture
  Wouter de Zwijger: paper by Vasquez ("$n^2$ Graph Coloring"); Johan de Ruiter: paper by Larson
• Thursday April 29, 2010, 9.15, room 401: 13th lecture
  ===spare===cancelled===

Participants

Deliverables

The column "version 1 BDD" deals with the first report on BDDs. And the "2" column has the second version. Analogous for the "n-Q" columns on N-Queens. "OK" means that the version has been checked. An m-dash "—" means that yours truly is still busy reading ;-). And "nothing" means that we are still waiting ... After the second version has been submitted, it will be made available, i.e., clickable. A ✓ denotes that the paper is fully approved.

References

1. Donald E. Knuth, The Art of Computer Programming, Volume 4, Combinatorial Algorithms:
   • Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions
   • Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams
   • Fascicle 2: Generating All Tuples and Permutations
   • Fascicle 3: Generating All Combinations and Partitions
   • Fascicle 4: Generating All Trees
2. Computer Musings, lectures given by Donald E. Knuth.
3. Papers from our n-Queens bibliography.

Questions/remarks: kosters@liacs.nl.

September 16, 2010 — http://www.liacs.nl/home/kosters/semcom/index.html