Teacher: Paolo Ferragina

CFU: 9 (first semester).

Course ID: 531AA.

Language: English.

Degree: Master degree in Computer Science and Master degree in CS&Networking.

Question time: Monday: 15-17, or by appointment (given COVID-19 situation, it will occur in video-conferencing within the virtual room of the course)

News: about this course will be distributed via a Telegram channel.

Official lectures schedule: The schedule and content of the lectures is available below and with the official registro.

In this course we will study, design and analyze advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. The design and analysis will involve several models of computation— such as RAM, 2-level memory, cache-oblivious, streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs and the availability of Big Data upon which those algorithms could work on. We will add to such theoretical analysis several other engineering considerations spurring from the implementation of the proposed algorithms and from experiments published in the literature.

Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithms aimed at minimizing the use of some computational resources like time, space, communication, I/O, energy, etc. Some of these solutions will be discussed also at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.

News: We will have one midterm exam in November and one in December, this will be done virtually via MS forms with a set of questions and a short time to answer. At the end of the midterm, you'll have also to upload the papers in which you sketched the calculations/simulations that allowed you to get your solutions/answers. The two midterms will be combined with an oral exam to be given in December/January.

The exam will consist of a written pre-test (up to 1hr) and an oral discussion on the pre-test and the whole course program.

This year students can participate to an (discretionary) coding project in which they have to design-engineer-implement a compressed and learned index for the predecessor search problem (see survey) by deploying advanced libraries (such as SDSL-lite), an available learned index (i.e. the PGM-index) and, of course, the knowledge acquired during the course.

This will be organized in the form of a coding contest (C, C++) so that you will be also provided with a baseline (the PGM-index, indeed) against which to compete, a machine on which running your experiments, and a collection of datasets in order to test your proposals.

Students can participate alone or in groups of two.

The students/groups that will improve the space-time Pareto curve of the PGM-index will be awarded by some points to be added to the final exam ranking: +3 for the top-5 results (where “top” is a combination between time/space performance and algorithmic elegance), +2 for the ones up to the top-15 results, +1 the others (including the ones that just propose an interesting algorithmic solution to the predecessor problem via compressed and learned indexes).

Discussing the project, the design, and the implementation with other students is allowed and encouraged, but your code must be your own. The instructors will evaluate each final submission for originality and correctness.

Details will be provided on a set of web pages prepared by the teaching assistant Giorgio Vinciguerra (email: giorgio.vinciguerra@phd.unipi.it):

* https://github.com/gvinciguerra/AE2020-tutorial - A repository containing code and instructions to set up an environment to experiment with the Succinct Data Structure Library (sdsl).

* Slides of the lab lectures with an explanation of the Challenge (part 1, part 2).

* Video-recordings are also available in the repository of the course.

* A screenshot of the web page of the contest follows below, just to give an idea of the platform we set up to make students compete and evaluate the performance of their codes:

I strongly suggest refreshing your knowledge about basic Algorithms and Data Structures by looking at the well-known book Introduction to Algorithms, Cormen-Leiserson-Rivest-Stein (third edition). Specifically, I suggest you look at the chapters 2, 3, 4, 6, 7, 8, 10, 11 (no perfect hash), 12 (no randomly built), 15 (no optimal BST), 18, 22 (no strongly connected components). Also, you could look at the Video Lectures by Erik Demaine and Charles Leiserson, specifically Lectures 1-7, 9-10, and 15-17.

We'll use the old-fashioned blackboard and few slides. Most of the content of the course will be covered by some notes I wrote in these years; for some topics, parts of papers/books will be used. You can download the latest version of these notes from this link.