ALGORITHMS FOR MODERN HARDWARE

In the modern computing landscape, we are constantly faced with a fundamental challenge: how do we efficiently store, retrieve, and process volumes of data that push the limits of our hardware? This course delves into the advanced algorithmic techniques and data structures required to answer this question. Moving beyond standard undergraduate algorithms, this course explores the intersection of time efficiency, space efficiency, and hardware-aware computing.

The techniques taught in this course are not just theoretical curiosities; they are the foundational building blocks of the systems that power the digital world. Traditional algorithms often assume that memory is uniform and infinite. However, in reality, cache misses are expensive, disk I/O is a massive bottleneck, and memory constraints dictate system design. This course bridges the gap between theoretical algorithm design and real-world system performance. You will learn to think critically about the space-time tradeoff and how to design algorithms that are both cache-friendly and space-efficient.

The expertise gained in this course is in high demand across software engineering, data science, and systems programming. The concepts directly apply to several domains, such as:

- Search Engines & Information Retrieval: Compressing of inverted indexes and fast query resolution.
- Databases: Using external memory sorting for massive tables, and probabilistic filters to avoid costly disk reads.
- Bioinformatics: Using succinct data structures and minimal perfect hashing to index massive DNA sequences in RAM.
- Networks: Employing fast, compact probabilistic filters (XOR/Fuse) for high-speed packet routing and caching decisions.

By the end of this course, you will have a deep understanding of how to engineer algorithms that gracefully and efficiently handle the massive datasets of tomorrow.

Knowledge and understanding

The student:
- knows the methodologies for designing and developing computer systems related to Data Engineering;
- 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 student:
- is able to design and develop systems for storing, managing, and analyzing large-scale data;
- 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.
- Rigorously analyze the performance of algorithms (runtime, used space, cache-misses).
- Independently read and understand research articles in the field.
- Implement existing algorithms and design new ones.

Proficiency in the following prerequisites is recommended for the successful completion of the course. Students who are not familiar with these topics are strongly encouraged to review them in advance to ensure they can fully engage with the lectures.
The teacher will review the necessary prerequisites.

- Probability theory (topics covered in CT0675)
- Algorithms and data structures (topics covered in CT0667)
- Programming, preferably in C/C++ (topics covered in CT0665 and CT0442)
- Discrete mathematics (topics covered in CT0434)

Array queries
- Prefix sums: Fenwick trees, segment trees, and wide segment trees.
- Range min/max queries with sparse tables.
- Rank and Select succinct indexes.

Data compression algorithms
- Integer codes: unary, Elias’ gamma and delta, Golomb-Rice, exponential Golomb, Fibonacci, variable-byte, information content and entropy, Kraft-McMillan inequality.
- Sequence encodings: folklore strategies (blocking, patching, simple codes), Elias–Fano, binary Interpolative coding, directly-addressable codes.
- Statistical compressors: Shannon–Fano, Huffman, Arithmetic coding.
- Dictionary-based compressors: LZ77, LZSS, LZ78, LZW.

External memory algorithms
- I/O model and fundamental I/O bounds.
- Sorting by merging.
- Sorting by distribution.
- Lower bound on I/Os for sorting.
- String sorting in external memory.

Hashing
- Dynamic hashing: sparse/dense hash tables, Robin Hood hashing, Swiss table design, cuckoo hashing.
- Minimal perfect hash functions: bucket placement, fingerprinting, random hypergraphs.
- Probabilistic filters beyond Bloom: cuckoo, XOR, Fuse filters.

Notes and slides by the professor.

The exam consists in two parts:
1. Coding of solutions to problems assigned during lectures: up to 12 points. Students are asked to individually solve exercises/challenges on the topics of the course.
2. Oral exam: up to 18 points. The oral examination begins with discussion of the solution to the exercises. Students are then asked some questions on the topics of the course.

Extra: up to 3 points will be given to students who participate in ICPC contests, like SWERC.

oral

The lecturer has a duty to ensure that the rules regarding the authenticity and originality of exam tests and papers are respected. Therefore, if there is suspicion of irregular conduct, an additional assessment may be conducted, which could differ from the original exam description.

Coding exercises (maximum 12 points):
- accuracy of the solution, use of computational resources, quality of the report (range 80%)
- originality of the solution (range 20%).

Oral exam (maximum 18 points):
- 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%).

The topics are presented using slides and blackboard.