Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
| 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.
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:
| 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 |
| 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 |
| 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 |