Seminar (Combinatorial) Algorithms, Spring 2013

Current Edition. For the previous years: spring 2010, spring 2011 and spring 2012.

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 7 - May 2, 2013. Room 402 OR 405, Snellius.

This year's book is A.N. Langville and C.D. Meyer, Who's #1? The Science of Rating and Ranking, Princeton University Press, 2012.

In the first half of the semester every student presents a part from the book above. After that students should study recent literature (or later chapters of the book) and present their results. And 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 2012, by personal visit to the organizers. The number of participants is at most 12 (approximately :).

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 40 minutes); more precisely, every student takes care of one (academic) hour lecture twice. The lecture includes discussion of experiments with the method: one with the running example from the book (five football teams) and one with, e.g., the Dutch football competition. 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). See here for a template. 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. 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.
You should use your own laptop for the presentations. It is wise to also have the file on a memory-stick. A beamer is always available.

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

Schedule

Thursday February 7, 2013, 9:15, room 402: Introduction.
Thursday February 14, 2013, 9:15, room 402: questions, answers, final schedule.

========== 1st half: ==============
Thursday February 21, 2013, 9:15, room 402: Leroy and Jan, Chapter 2: Massey.
Thursday February 28, 2013, 9:15, room 405: Benjamin and Sander, Chapter 3: Colley.
Thursday March 7, 2013, 9:15, room 405: Xiaolong and Alex, Chapter 6: Markov
Thursday March 14, 2013, 9:15, room 405: Bas and Matthieu, Chapter 4: Keener.
Thursday March 21, 2013, 9:15, room 405: Katherina and Mahya, Chapter 7: Offense/defense.
Thursday March 28, 2013, 9:15, room 405: Jambul and Karim, Chapter 5: Elo.

========== 2nd half: ==============
Thursday April 4, 2013, 9:15, room 405: Alex & Jan, Chapter 8: Reordering.
Thursday April 11, 2013, 9:15, room 402: Leroy & Xiaolong, Chapter 9: Point spreads.
Thursday April 18, 2013, 9:15, room 402: Katherina & Sander, Chapter 11: Ties.
Thursday April 25, 2013, 9:15, room 402: Bas & Jambul, Chapter 16: Methods comparison.
Thursday May 2, 2013, 9:15, room 402: Benjamin & Mahya, Page Rank.
Thursday May 2, 2013, 13:30, room 405: Karim & Matthieu, Chapter 14: Rank aggregation.

Participants

Email at Liacs (or at Gmail, at Umail).

name	email	remarks
Alex(andros) Kavvadias	alx8619 @G	Chapter 6 & 8
Bas Harenslak	b.p.harenslak @U	Chapter 4 & 16
Benjamin van der Burgh	bvdburgh @L	Chapter 3 & PR
Jambul Tologonov	tologonovd @G	Chapter 5 & 16
Jan Kalmeijer	jkalmeij @L	Chapter 2 & 8
Karim Sydygaliev	ksydygal @L	Chapter 5 & 14
Katherina Kondyli	kousouni @G	Chapter 7 & 11
Leroy van Delft	cvdelft @L	Chapter 2 & 9
Mahya Mirtar	mahyaa.mirtar @G	Chapter 7 & PR
Matthieu Mimpen	m.mimpen @U	Chapter 4 & 14
Sander van Rijn	svrijn @L	Chapter 3 & 11
Xiaolong Mu	muyuze @G	Chapter 6 & 9

Deliverables

subject	who	remarks
Massey	Leroy & Jan	✓ first version checked by W; second version checked by HJ; final version OK.
Colley	Benjamin & Sander	✓ first version checked by W; second version checked by HJ; final version OK.
Markov	Xiaolong & Alex	✓ first version checked by W; second version checked by HJ; final version OK.
Keener	Bas & Matthieu	✓ first version checked by W; second version checked by HJ; final version OK.
Offense/defense	Katherina & Mahya	✓ first version checked by W; second version checked by HJ; final version OK.
Elo	Jambul & Karim	✓ first version (J's part) checked by W; second version checked by HJ; final version OK.
Reordering	Alex & Jan	✓ first version checked by W; second version checked by HJ; final version OK.
Point spreads	Leroy & Xiaolong	✓ first version checked by W; second version checked by HJ; final version OK.
Ties	Katherina & Sander	✓ first version checked by W; second version checked by HJ; final version OK.
Methods comparison	Bas & Jambul	✓ first version checked by W; second version checked by HJ; final version OK.
Page Rank	Benjamin & Mahya	✓ first version checked by W; second version checked by HJ; final version OK.
Rank aggregation	Karim & Matthieu	...

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.

A.N. Langville and C.D. Meyer. Who's #1? The Science of Rating and Ranking, Princeton University Press, 2012.
A.N. Langville and C.D. Meyer. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.
Dutch football [Dutch link]

September 1, 2013 — http://www.liacs.nl/home/kosters/semalg/index2013.html