Seminar (Combinatorial) Algorithms, Spring 2019

Spring 2020: Tuesdays, 11:15-13:00. Dates: February 4 - May 12, 2020. No class on May 5. Location: Snellius, room 401.

Want to participate? Send an e-mail to w.a.kosters@liacs.leidenuniv.nl before February 1, 2020, with an answer to the following exercise from the Siegel book: Show that Blue-Red Hackenbush does not have N-positions, i.e., in ordinary Hackenbush there are no positions where the first player can always win.

Subject: "Combinatorial Game Theory"
Literature: see below.
Schedule: Spring 2019, Tuesday mornings, 11:00-13:00; February 5 - April 23, 2019; perhaps May 7.
Location: Snellius, room 408.

Contents | Schedule | Deliverables | References

Winning Ways ... Siegel ... 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.

This year's subject is "Combinatorial Game Theory".
In the first half of the semester every student presents a part from the book/papers mentioned above/below. After that students should study recent literature (or later chapters of the book) and present their results. And maybe do 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 2018, by personal visit to the organizers (come on, please do this). The number of participants is at most 10 (approximately :).

In this seminar we will discuss several issues dealing with algorithms, as described in the books/papers mentioned above/below.

Students are supposed to present and discuss papers, during class. The setup depends on the number of participants.
Every student presents two papers, one in each half of the semester. Each presentation takes about 30 minutes, so in a session we have three presentations. Next to the oral presentations (using PDF or PowerPoint slides, with the additional help of the blackboard) ± ten page self-contained essays on the subject must be written (in LaTeX; in English/Dutch). See here for a template; and this is what it will look like. Deadline: one month after the presentation.
Essays should be improved until students and organizers 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. Some form of peer review will be used. Immediately after each lecture there is a short discussion between students and organizers, where the presentation is evaluated. The first and second meetings are used to make a proper schedule. Every student is supposed to choose and present two subjects, one in the first half and one in the second half of the seminar.
Students should use their own laptop for the presentations. It is wise to also have the slides for the presentation on a memory-stick, in PDF. A beamer is always available.

Grading The final grade is composed of the four Ps: presentation (2x), paper (2x), participation (including presence) and peer review OR programming.

Winning Ways ... Lessons in Play ...

Schedule

Here S refers to the Siegel book, WW denotes Winning ways (see the References).

========== 1st half: ==============

February 5, 2019: Introduction; slides and subjects / part 2.
February 12, 2019: Scheduling.
February 19, 2019: Questions and answers.
February 26, 2019 (13:30-15:15): Group discussion on pages 1-15 from the Siegel book; exercises 1.1, 1.2, 1.3, 1.5, 1.6 and 1.7 (page 14-15).
March 5, 2019: Group discussion on pages 53-60 from the Siegel book.
March 12, 2019: Jimmy: Some simple games, S53-57; Gilles: Sequel, S57-60.
Monday March 18(!), 2019, room B1: Thomas and Levi: Canonical form, S62-68.

========== 2nd half ==============
March 26, 2019 (13:30-15:15): Scheduling second part; discussion about preliminary two-page papers.
April 2, 2019: skipped, work on paper. Submit first version.
April 9, 2019 (13:30-15:15): Thomas (tiny and miny, S88-89)
Monday April 15(!), 2019 (13:30-15:15), room 402: Jimmy (Nim, Sprague-Grundy, S180-181) and Levi (heap games, S184-188)
April 23, 2019 (13:30-15:15): Gilles (flowers, S90-93)
No class on April 30, 2019!
May 7, 2019 (13:30-15:15): questions, room 159

Deliverables

The list below shows the progress of the submitted papers.

Here 1 is the first, 2 the second paper; V denotes "handed in and checked", I denotes "handed in but not yet checked", and - means "not handed in yet"; usually, there are three versions per paper. An R denotes that the paper is ready, so the target per paper is VVVR.

References

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

E.R. Berlekamp, J.H. Conway and R.K. Guy, Winning Ways for your Mathematical Plays, Academic Press, two volumes, 1982. Second edition: AK Peters, four volumes, 2001-2004.
A.N. Siegel, Combinatorial Game Theory, AMS, 2013.
M.H. Albert, R.J. Nowakowski and D. Wolfe, Lessons in Play, An Introduction to Algorithmic Game Theory, CRC Press, 2019.
J.H. Conway, On Numbers and Games, second edition, AK Peters, 2001.
T.S. Ferguson, Game Theory, Part 1: Impartial Combinatorial Games, web version

July 8, 2019 — http://www.liacs.leidenuniv.nl/~kosterswa/semalg/index.html