ADVANCED ALGORITHMS

The course addresses advanced techniques in the field of randomized algorithms and compressed data structures, with a particular focus on the problem of pattern matching on compressed data (strings and graphs) and randomized algorithms/probabilistic analysis for computational problems in graphs.

Knowledge and understanding
The student:
- knows the methodologies for designing and developing computer systems related to Massive Data;
- knows the techniques for evaluating the performance, scalability, and reliability of software and algorithms for analyzing massive data;
- develops his/her skills in the field of programming by learning calculation techniques and knowledge of algorithms, at the state of the art;
- knows programming environments and algorithms for analyzing massive data;

Ability to apply knowledge and understanding
The graduate:
- is able to design and develop systems for storing, managing, and analyzing large-scale data;
- is able to design and evaluate highly scalable systems;
- is able to use advanced programming techniques in the fields of high-performance computing and algorithms for analyzing large amounts of data;
- is able to verify the functional and non-functional requirements (performance) of an algorithm;
- is able to access scientific literature to identify potential solutions to problems with innovative state-of-the-art methods.

Judgment skills:
At the end of the course the student will be able to use the knowledge acquired to:
- Identify the algorithm and the data structure best suited to solve a given problem in the context of massive data.
- Independently read and understand research articles in the field.
- Implement existing algorithms and design new ones.

algorithms and data structures
Basics of information theory

Part 1
+ Introduction to the pattern matching problem and classical solutions
+ Suffix array compression techniques: entropy-based (Compressed Suffix Array) and repetition-aware (r-index, Suffixient Array)
+ Compressed indices on labeled graphs

Part 2
+ Concentration Bounds
+ Random Processes on Networks
- Information Diffusion in Networks
- Random Walks, Cover time
+ Multiplicative Weights Framework
- Prediction with Expert Advice
- Solving Covering/Packing LPs and Fair Information Diffusion
- Boosting, VC dimension and PAC learning

original research articles

The exam consists of an oral examination. During the exam, students may present a research paper chosen from the topics covered in the course. Alternatively, they will be asked questions on the material presented during lectures.

oral

The instructor is responsible for ensuring the authenticity and originality of all examinations and coursework. In cases of suspected academic misconduct, an additional on-site assessment may be required during the exams, which may differ from the standard format.

- knowledge: statements and proofs of the theoretical results (range 40%),
- detail and completeness of the answers (range 40%)
- communication skills, including the use of specific terminology related to algorithms and data structures for massive data (range 20%).

Course topics will be presented using a combination of blackboard (or whiteboard) and lecture slides prepared by the instructor.