Some useful infos on the course:

• Teacher: Paolo Ferragina and Rossano Venturini
• CFU: 6
• Period: First semester
• Language: English
• Lectures schedule: Tuesday 9-11 (N1) and Thursday 16-18 (C).
• Question time: After lectures or by appointment.
• Allowed Degree: Master degree in Computer Science, or Computer Science and Networking, or Business Informatics
• News: about this course will be distributed via a Twitter-channel.
• Official lectures schedule: The schedule and content of the lectures is available below and with the official registro.

The course consists of a first part of lectures describing advanced algorithms and data structures (3 CFU), and a laboratory in the second part (3 CFU) in which the students will deploy these techniques to develop a software project. The students will select their projects among a set of proposals by some IT companies which are challenging from an algorithmic perspective. These companies will also contribute to identify/construct significant datasets that will help in testing the proposed algorithmic solutions.

The course will provide the opportunity of

• facing with difficult algorithmic problems of practical interest involving big data;
• evaluating the impact of efficient algorithmic solutions in the design of software managing big data;
• implementing advanced software by using powerful and sophisticated libraries;
• getting in touch with some companies for internships, scholarships, or thesis proposals.

The exam consists of three parts: Project 70%, Written/oral test 20%, Project presentation 10%. Students can attend the written/oral test before the presentation/development of the project.

As far as the two projects are concerned, we list below the datasets for each of them. These are warm-up datasets of moderate size, yet sufficient to start designing your solutions and be concerned with time/space efficiency issues. We will provide you larger datasets to test the final codes you'll produce.

Project 1. The dataset consists of the following parts:

• Dictionary of English terms (3.5Mb, 354.984 terms);
• Dictionary of titles of Wikipedia articles (116 Mb, 6.971.668 titles). This dataset has been modified by introducing errors;
• Queries obtained by introducing errors in the dictionary of terms above (2.126.355 queries);
• Queries obtained by taking the Wikipedia titles (376.304 queries).

Few related papers.

Project 2. The dataset consists of 2.8Gb of 7zipped web pages drawn from the UK-GOV2 collection, and in WARC format. Some techniques that you can use for your project are described in these papers. Software libraries are indicated here, plus few additional softwares from students listed below:

• WARC parser (by Andrea Cardaci).

If you wish to refresh your mind on basic Algorithms and Data Structures, we suggest you to look at the well-known book Introduction to Algorithms by Cormen-Leiserson-Rivest-Stein, third edition.

Moreover, you can look at the content of the Algorithm Engineering course by Paolo Ferragina. Anyway, depending on the topics addressed in the lectures you'll be pointed out to the suitable chapters of Ferragina's notes.

We'll often do not project slides for teaching, but use mainly the old-fashioned blackboard. Most of the content of the course will be covered by notes, sometime we'll use parts of papers/books.