Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Seminar Advanced Algorithms and Data Structures FS2018

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:Spring 2018
Dates: Friday 23.2.2018 15:15-17.00h ETHZ CAB G 11
Saturday 07.4.2018 9:00-12:30h ETHZ HG F 26.3
Saturday 21.4.2018 9:30-16:00h ETHZ HG F 26.1
Saturday 12.5.2018 9:30-15:30h ETHZ HG F 26.3

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 first version of 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 versions of the report are due one week before the date of the seminar.

Setup and Organization: The setup of the seminar will be discussed on Friday February 23, 2018 from 15:15 until 17:00 in room CAB G 11 at ETHZ. At the first meeting the available slots for the seminar will be distributed and papers will be assigned.

Presentations:

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

Saturday 07.4.2018 (in order of presentation)
PaperStudentAdvisorBuddyReport
I. Althöfer, G. Das, D. Dobkin, D. Joseph. Generating sparse spanners for weighted graphs SWAT 1990Hörmann TierryStefano LeucciKäppeli Lukas Thomas Wilhelmreport
N. Alon, Z. Galil, O. Margalit, M. Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths FOCS 1992Signer MatteoPrzemysław UznańskiChristian Faniareport
D. Dor, S. Halperin, U. Zwick. All Pairs Almost Shortest Paths FOCS 1999Gessler Fabian DieterStefano LeucciLi Er Lu Lawrencereport
P. N. Klein, R. E. Tarjan. A randomized linear-time algorithm for finding minimum spanning trees STOC 1994Grob FabianStefano LeucciMohler Jonas Oliverreport
A. Backurs, P. Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) STOC 2015Weber Simon LukasPrzemysław UznańskiKaufmann Jean Martin Charlesreport

Saturday 21.4.2018 (in order of presentation)
PaperStudentAdvisorBuddyReport
D. Bilò, L. Gualà, S. Leucci, G. Proietti Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees STACS 2016Rimle PhilippStefano LeucciGrob Fabianreport
N. Khanna, Neelesh, S. Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs STACS 2010Käppeli Lukas Thomas WilhelmPeter WidmayerPeter Emanuel Viktorreport
U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication JACM 2002Kapfhammer Johannes Felix Przemysław UznańskiStampfli Timonreport
M. Parter, D. Peleg. Sparse Fault-Tolerant BFS Trees ESA 2013Li GengyanPeter WidmayerKapfhammer Johannes Felixreport
S. Alstrup, I. L. Gørtz, T. Rauhe, M. Thorup, U. Zwick. Union-Find with Constant Time Deletions ICALP 2005Rüegge Sandro GuidoStefano LeucciHörmann Tierryreport
O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication FOCS 2010Dominik HänerPrzemysław UznańskiWeber Simon Lukasreport
M. Pǎtraşcu, M. Thorup. The Power of Simple Tabulation Hashing STOC 2011Mohler Jonas OliverPrzemysław UznańskiEngel Lowis Antonreport

Saturday 12.5.2018 (in order of presentation)
PaperStudentAdvisorBuddy
C. Demetrescu, M. Thorup. Oracles for distances avoiding a link-failure SODA 2002Gjini GabrielPeter WidmayerRüegge Sandro Guido
M. B. T. Knudsen. Linear Hashing Is Awesome FOCS 2016Kaufmann Jean Martin CharlesPrzemysław UznańskiLi Gengyan
M. Thorup, U. Zwick. Approximate Distance Oracles STOC 2001Christian FaniaStefano LeucciGjini Gabriel
Y. Peres, D. Sotnikov, B. Sudakov, U. Zwick. All-Pairs Shortest Paths in O(n2) Time with High Probability FOCS 2010Li Er Lu LawrencePrzemysław UznańskiDominik Häner
D. R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-out algorithm SODA 1993Engel Lowis AntonStefano LeucciGessler Fabian Dieter
T. D. Hansen, H. Kaplan, R. E. Tarjan, U. Zwick. Hollow Heaps ICALP 2015Peter Emanuel ViktorPeter WidmayerRimle Philipp