Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization


Seminar Advanced Algorithms and Data Structures

Organization: Peter Widmayer, Stefano Leucci and Przemysław Uznański
Teaching language: English
Level: Advanced BSc students
Academic Year: Fall 2018
Dates: Thursday 20.09.2018 15:15-17.00h ETHZ CAB H52
Saturday 03.11.2018 in ETHZ CAB G52 from 9:30 AM
Saturday 10.11.2018 in ETHZ CAB G52 from 9:30 AM
Saturday 17.11.2018 in ETHZ CAB G52 from 9:30 AM

Overview and objectives: The areas of this seminar are Algorithms and Data Structures with emphasis on modern, breakthrough results. Students learn how to critically read and study research papers, how to summarize the contents of a paper, and how to present it in a seminar.

Teaching format: Each participant writes a self-contained report of about 10 pages and gives a 30 minutes presentation (blackboard, without a computer). Each participant has a buddy. Buddies read the report, make suggestions for improvements, and help with the presentation (e.g., dry runs). The report is due three weeks before the date of the presentation, and will be discussed with the buddy and the professor about one week before the presentation. The final version of the report is due one week before the date of the seminar.

Setup and Organization: The setup of the seminar will be discussed on Thursday September 20, 2018 from 15:15 until 17:00 in room CAB H 52 at ETHZ. At the first meeting the available slots for the seminar will be distributed and papers will be assigned.


Participation at all three meetings is compulsory for students. The assessment depends on the quality of the report, presentation, active participation during the seminar, and input as a buddy.

Useful links:

Schedule of Saturday 03.11.2018:

Paper Student Advisor Buddy Report
B. Chazelle. The soft heap: an approximate priority queue with optimal error rate Blatter Philippe Peter Widmayer Först Mathis Report
I. Finocchi, F. Grandoni, G. F. Italiano. Resilient dictionaries Morandini Dario Stefano Leucci Basil Fuerer Report
J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan. Making Data Structures Persistent Huang Shengyu Peter Widmayer Wiegner Jan Report
R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees Sara Steiner Stefano Leucci Nowack Manuel Report
M. A. Bender, M. Farach-Colton. The Level Ancestor Problem simplified Cai Qi Peter Widmayer Roshardt Matthias Report
U. Feige, P. Raghavan, D. Peleg, E. Upfal. Computing with Noisy Information Schmetz Felix Stefano Leucci Passweg Jonas Report
R. Klein, R. Penninger, C. Sohler, D. P. Woodruff. Tolerant Algorithms Giamarchi Gabriel Stefano Leucci Yuan Simon Report

Schedule of Saturday 10.11.2018:

Paper Student Advisor Buddy Report
R. Pagh, F. F. Rodler. Cuckoo Hashing Brunner Lucas Stefano Leucci Stöckli Mario Report
I. Abraham, A. Fiat, A. V. Goldberg, R. F. Werneck. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms Först Mathis Peter Widmayer Saeedi Orhan  Report
M. B. T. Knudsen. Additive Spanners: A Simple Construction Basil Fuerer Peter Widmayer Fabian Grob Report
T. M. Chan. Approximation Schemes for 0-1 Knapsack Wiegner Jan Stefano Leucci Balla Adrian Report
Y. Cao. A Naive Algorithm for Feedback Vertex Set Nowack Manuel Peter Widmayer Bachmann Jules Report
H. L. Bodlaender, T. C. van der Zanden. On the Exact Complexity of Polyomino Packing Scheel Börge Stefano Leucci Schilliger Julian Report
E. D. Demaine, I. Grosof, J. Lynch, M. Rudoy. Computational Complexity of Motion Planning of a Robot through Simple Gadgets Roshardt Matthias Peter Widmayer Andrei Herasimau Report
D. Bilò, L. Gualà, S. Leucci, G. Proietti, M. Rossi. On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games Passweg Jonas Stefano Leucci Luca Mondada  Report

Schedule of Saturday 17.11.2018:

Paper Student Advisor Buddy Report
D. Alistarh, J. Kopinsky, J. Li, N. Shavit. The SprayList: A Scalable Relaxed Priority Queue Balla Adrian Przemysław Uznański Scheel Börge Report
Y. Perl, E. M. Reingold. Understanding the complexity of interpolation search Yuan Simon Przemysław Uznański Blatter Philippe Report
M. A. Bender, M. Farach-Colton, R. Johnson, S. Mauras, T. Mayer, C. A. Phillips, H. Xu. Write-Optimized Skip Lists Fabian Grob Przemysław Uznański Sara Steiner Report
A. Conway, M. Farach-Colton, P. Shilane. Optimal Hashing in External Memory Stöckli Mario Przemysław Uznański Morandini Dario Report
M. A. Bender, J. Christensen, A. Conway, M. Farach-Colton, R. Johnson, M. Tsai. Optimal Ball Recycling Saeedi Orhan Przemysław Uznański Huang Shengyu Report
A. Kosowski. Faster Walks in Graphs: A Õ(n²) Time-Space Trade-off for Undirected s-t Connectivity Schilliger Julian Przemysław Uznański Schmetz Felix Report
S. Alstrup, C. Gavoille, E. B. Halvorsen, H. Petersen. Simpler, faster and shorter labels for distances in graphs Bachmann Jules Przemysław Uznański Cai Qi Report
A. Kosowski, L. Viennot. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons Andrei Herasimau Przemysław Uznański Giamarchi Gabriel Report
A. Condon, M. Hajiaghayi, D. Kirkpatrick, J. Maňuch Simplifying Analyses of Chemical Reaction Networks for Approximate Majority Luca Mondada Przemysław Uznański Brunner Lucas Report