Ljubljana Algorithms and Data Structures Summer School, Sept 1-5 2014

OVERVIEW AND GOAL

The Ljubljana Algorithms and Data Structures Summer School 2014 will introduce attendees to the latest developments in algorithms and data structures. The topics will include advanced topics in data structures, suffix trees and arrays, Burrows-Wheeler, implementation issues in construction and queries, and online strategies with applications to search and exploration.

 

The operation is co-financed by the European Union from the European Social Fund and the Ministry of Education, Science and Sport. The operation is performed under the Operational Programme for Human Resource Development for the period 2007-2013, priority axis 3: "Development of Human Resource and Lifelong Learning" policy orientation 3.3 "Quality, Competitiveness and Responsiveness of Higher Education." The international workshop will take place in the context of the implementation of the project »Internationalization of the University of Ljubljana«.

LECTURES

The school will be taught by experts in learning:

  • Ian Munro (University of Waterloo)
  • Roberto Grossi (University of Pisa)
  • Bengt Nilsson (Malmö University)
  • Andrej Brodnik (University of Ljubljana)

MATERIAL

Poster (pdf)
Flyer (pdf)
Registration form (pdf)
Lecture slides
Video lectures

PARTICIPATION

The summer school will take place on September 1-5, 2014 at the new building of University of Ljubljana, Faculty of Computer and Information Science, Ljubljana, Slovenia. The school is targeted at graduate students, as well as researchers interested in an in-depth introduction to algorithms and data structures.

 

The capacity of the Summer School is limited. Prospective participants should register as soon as possible. Participants should fill the registration form and send it to reg@lads14.fri.uni-lj.si. Registration is on a first-come-first-serve basis and will close on Friday August 15, 2014, but the confirmations will be sent immediately. Registration is free; handouts will be provided by the University of Ljubljana, Faculty of Computer and Information Science. Each attendant should prepare a poster describing his research field and particularly his contributions. The posters session will take place on Wednesday afternoon, however we prefer the posters to be exposed on Monday already for the duration of the whole summer school.

SCHEDULE

TRAVEL

The summer school will take place at the new building of University of Ljubljana, Faculty of Computer and Information Science. The address is Večna pot 113. Local bus line 18 and 18 L goes from the main bus station and has a stop in front of the new building. More information on local bus lines.

Ljubljana Airport (or Jože Pučnik Airport) is the nearest international airport. The international code for the airport is LJU. It is located about 25 km (~30 minutes of driving) North of Ljubljana. There are basically three ways for getting to the town:

  • by bus every 1-2 hours: check Alpetour and the Ljubljana main bus station. From station "Letališče Brnik" to "Ljubljana AP" (Ljubljana main bus station). One way ticket ~4 EUR
  • by shuttle: see Shuttle Ljubljana or GoOpti. Contact them to deliver you closer to your hotel. One way ticket ~9 EUR
  • by taxi. Delivers you to your hotel. Negotiate for the one way ticket ~25 EUR.

In case of emergency, contact the member of the organizing committee at +38640566543.

ACCOMODATION

Our assistant Jasna Bevk from the Faculty of Computer Science checked the destinations. Basically there are 3 options within 10 minutes of walking distance to the summer school location.

For more information on accomodation and travel, contact us at info@lads14.fri.uni-lj.si.

ORGANIZING COMMITTEE

  • Andrej Brodnik (University of Ljubljana, Faculty of Computer and Information Science, LUSY)
  • Matevž Jekovec (University of Ljubljana, Faculty of Computer and Information Science, LUSY)
  • Andrej Bukošek (University of Ljubljana, Faculty of Computer and Information Science, LUSY)
  • Miha Zidar (University of Ljubljana, Faculty of Computer and Information Science, LUSY)
  • Jurij Mihelič (University of Ljubljana, Faculty of Computer and Information Science, LALG)
  • Uroš Čibej (University of Ljubljana, Faculty of Computer and Information Science, LALG)

ABOUT UNIVERSITY OF LJUBLJANA, FACULTY OF COMPUTER AND INFORMATION SCIENCE

The Faculty of Computer and Information Science is the leading teaching and research institution in the field of Computer science in Slovenia, and in spite of its comparatively short history it has a number of active research groups, as well as a lengthy roster of alumni, some of whom have achieved distinction in various fields of computer science in Slovenia and abroad.

SUMMER SCHOOL LECTURES

Succinct Data Structures, Ian Munro, University of Waterloo, Canada

A succinct data structure is a representation of a combinatorial object that requires space close to the logarithm of the number of such objects of the given size and permits the expected query (and perhaps update) operations to be performed quickly. Examples of such structures include representations of tree in about 2n bits supporting most navigation operations in constant time. We will introduce the general area, discussing representations of trees and other combinatorial objects. The presentation will cover a mix of "older" and new results.

 

Ian Munro is University Professor and Canada Research Chair in Algorithm Design in the D.R. Cheriton School of Computer Science at the University of Waterloo, where he has been a faculty member since completing his PhD at the University of Toronto in 1971. His research has concentrated on the efficiency of algorithms and data structures, most notably on space efficient data structures including implicit data structures (those using essentially no space except that required for the “raw data”) and, more recently, succinct data structures (in which the representation of a combinatorial object uses essentially the information theoretic minimum space, yet the necessary operation can be performed very quickly). Other work has included streaming algorithms and hashing techniques. He has authored over 200 research papers (http://scholar.google.com/citations?user=O55rM6QAAAAJ&hl=en) and supervised more than twenty Ph.D.'s on the subject. Dr. Munro has held visiting positions at a number of major universities and research labs, including AT&T Bell Labs, Princeton University and the Max Planck Institute for Informatics. His consulting activities have included work with government and several major and minor computing companies. He has served on the editorial boards of several journals, and the program committees of most of the major conferences in the algorithms area. He is a former Director of Waterloo's Institute for Computer Research. He was elected Fellow of the Royal Society of Canada in 2003, a Fellow of the ACM in 2008, and made University Professor in 2006.

 

Lecture slides (pdf)

Video lectures

 

Topics in advanced data structures, Roberto Grossi, University of Pisa, Italy

These lectures will address new problems on classical data structures, showing how to achieve fast performance with strings, graphs, external memory and cache-obliviousness. The focus will be on general techniques to transform general purpose data structures, such as the classical binary search trees, into advanced data structures with strong properties that have been previously obtained with specialised data structures. The conceptual path is to distill the relevant properties and propose a transformation that exploits those properties. Case studies will involve standard binary search tree, AVL trees, and weight balanced trees.

 

Roberto Grossi, professor at the University of Pisa, is a member of the Algorithms and Data Structures group in the Computer Science Department, and is also a member of the International Olympiad in Informatics. He has coauthored many papers on the topics of Data Structures, Pattern Matching, Text Indexing and Compression. He serves on the editorial board of Theory of Computing Systems, Springer-Verlag, and RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications , EDP Sciences. He has served on numerous PC committees of conferences on algorithms and data structures.

 

Lecture slides (pdf)

 

Online strategies with applications to search and exploration, Bengt Nilsson, Malmö University, Sweden

This sequence of lectures will focus on online strategies for exploration and search in combinatorial environments. We introduce the concept of competitive analysis with some simple examples, including list updates in linear sequences. Competitive analysis has become the main tool for analyzing the worst case behaviour of online strategies for exploration and search. We exhibit some results on online search and exploration including searching for a target point on a line with a single agent, searching for a target on multiple lines with several agents, geometric exploration of simple polygons with a single agent and some results on exploration of trees with multiple agents.

 

PhD at Lund University, Sweden in 1995 and "docent" degree in 1999. Main research topics are in the field of approximation and online algorithms for network and path problems, in particular with geometric flavor.

 

Lecture slides (pdf)

Video lectures

 

Search in unstructured text, Andrej Brodnik, University of Ljubljana, Slovenia

More and more data is stored in an unstructured way. This includes data in noSQL databases, cloud storage systems, bioinformatics data and others. The common property of all these data is that it can be represented as a sequence of characters from a finite alphabet – can be represented as a text. In this lecture we will look at basic data structures for searching in text. We will consider the complexity of their construction and search in them in a sequential and in parallel case. Special emphasis will be put on practicality of the presented data structures.

 

Dr. Brodnik holds a position of Professor at the University of Primorska, Slovenia, and with a University of Ljubljana, Slovenia. He held also a position of Adjoint Professor with the University of Technology, Luleå, Sweden. At the University of Primorska he also served as a vice-rector and as a director of Primorska Institute of Natural Sciences and Technology. Before joining University of Primorska he was a CTO at ActiveTools, Slovenia. Among other projects he was also a chief architect of a product “ClusterServer” of TurboLinux that received a number of prestigious awards. He was also a senior developer at Effnet AB and one of the authors of the Luleå forwarding algorithm. The research work of Dr. Brodnik concentrates on efficient data structures and algorithms, and their use in practical problems. These include networking, ubiquitous computing, bioinformatics and optimization problems.

Dr. Brodnik is winner of, among others, Boris Kidrič Foundation Award (Slovenian national scientific award award), Fullbright Scholarship, ITRC/ICR Fellowship, Innovation Cup and IBM Faculty Award, University of Primorska Golden plaque, and National award for exceptional achievements in higher education. He is author of over 80 scientific papers and conference contributions and of 6 international patents. Services SCOPUS and WoS list over 200 citations of his work..

 

Lecture slides (pdf)