Exercises of Algorithm Engineering

This repository contains the exercises (and some of their solutions) of various test exams of the Algorithm Engineering (ALE) course, taught by Prof. Paolo Ferragina.

Topics of the course

The exercises will divided as the chapters in Prof. Ferragina's lecture notes:

1. Prologue: The RAM Model and the EM model.
2. A Warm Up!: The maximum sub-array problem.
3. Random Sampling: Disk model and known sequence length. Streaming model and known sequence length. Streaming model and unknown sequence length.
4. List Ranking: The pointer-jumping technique. Parallel algorithm simulation in a 2-level memory. A Divide&Conquer approach.
5. Sorting Atomic Items: The merge-based sorting paradigm. Lower bounds. The distribution-based sorting paradigm. Sorting with multi-disks.
6. Set Intersection: Mutual partitioning. Doubling search.
7. Sorting Strings: A lower bound. RadixSort. Multi-key Quicksort. Some observations on the I/O-model.
8. The Dictionary Problem: Direct-address tables. Hash Tables. Universal hashing. Perfect hashing, minimal, ordered. A simple perfect hash table. Cuckoo hashing. Bloom filters.
9. Searching Strings by Prefix: Array of string pointers. Interpolation search. Locality-preserving front coding. Compacted Trie. Patricia Trie. Managing Huge Dictionaries.
10. Searching Strings by Substring: Notation and terminology. The Suffix Array. The Suffix Tree. Some interesting problems.
11. Integer Coding: Elias codes: γ and δ. Rice code. PForDelta code. Variable-byte code and (s,c)-dense codes. Interpolative code. Elias-Fano code. Concluding remarks.
12. Statistical Coding: Huffman coding. Arithmetic Coding. Prediction by Partial Matching.
13. Dictionary-Based Compressors: LZ77. LZ78. LZW. On the optimality of compressors.
14. The Borrows-Wheeler Transform: The Burrows-Wheeler Transform. Two other simple transforms. The bzip compressor. On compression boosting. On compressed indexing.

Extras:

1. Minimum Spanning Tree: BFS and DFS visits, Minimum Spanning Tree problem: Kruskal and Prim algorithms and analysis. Algorithms for external and semi-external computation of MST.
2. Randomized Data Structures: Treaps and Skip lists.

Topics covered by the exams

In this table is shown which kind of exercises you may find in a specific test exam (denoted by the date in which it was taken). The numbers describe the topics as in the previous section.

WARNING: The following table is just a stub. Many exercises may be misclassified.
WARNING: Every exam taken before 2016 may contain exercises form a previous programme.

Test Date	1	2	3	4	5	6	7	8	9	10	11	12	13	14	E1	E2	Status
29/10/18				●	●	●	●
04/09/18							●	●	●			●
16/07/18			●		●									●		●
15/06/18			●		●			●				●
15/02/18					●	●		●				●				●
15/01/18					●						●	●				●
18/12/17									●	●	●	●		●
30/10/17			●	●		●	●
05/09/17								●					●	●	●	●
27/07/17			●						●			●		●	●
29/06/17						●				●	●				●
12/06/17								●			●		●	●	●	●
12/01/17					●			●				●			●	●
02/09/16					●	●				●						●
19/07/16			●		●									●		●
27/06/16			●		●			●						●		●
01/02/16			●					●		●				●	●
11/01/16					●		●			●	●
10/09/15					●			●		●			●
20/07/15					●			●							●	●
29/06/15					●							●			●	●
08/04/15					●			●	●							●
09/02/15								●		●					●
16/01/15		●					●	●		●		●				●
29/07/14					●					●				●
30/06/14				●	●		●						●		●
09/06/14					●			●				●			●
29/01/14					●		●	●	●			●
08/01/14			●					●	●			●
12/09/13					●			●		●					●
16/07/13					●					●	●	●
25/06/13							●								●
04/06/13			●		●		●	●
03/09/12					●			●		●		●	●
23/07/12								●		●	●
28/06/12			●				●					●
08/06/12							●	●	●
28/09/11							●		●			●				●
01/09/11					●			●	●				●	●
20/07/11			●						●	●
24/06/11								●	●				●			●
09/06/11					●			●		●				●
28/02/11					●			●				●
01/02/11							●	●					●	●
15/07/10								●		●	●		●
22/06/10					●								●
01/06/10												●
11/02/10								●				●
11/01/10							●	●						●

Solutions file

For the latest PDF file, see the releases page.

You can otherwise build it yourself, using the following commands:

git clone https://github.com/flandolfi/ALE-exercises.git
cd ALE-exercises/
make

How to contribute

Any kind of contribution is welcome! If you wish to add a missing solution, follow these instructions:

1. Fork this repository;
2. Create a .tex file containing:
   • The text of the problem, preceded by the LaTeX macro \exercise;
   • The solution of the problem, preceded by the LaTeX macro \solution;
3. If you need a package, add it in the ALE-exercise.tex file, using \usepackage{<package>};
4. Place the file in the specific folder for the subject of the exercise you have solved;
5. Append your name in the \author{<name>} field in the ALE-exercise.tex file, preceded by \and;
6. Submit a pull request!

Thank you for your contribution! 😊

Links

• Prof. Ferragina's lecture notes (the main reference of the course).
• "Introduction to Algorithms", by T. H. Cormen, C. E. Leiserson and R. L. Rivest.
• Video lectures of Introduction to Algorithms, by E. Demaine and C. E. Leiserson.
• "Compact Data Structures", by Gonzalo Navarro. A beautiful book containing some relevant topics of the course.
• If you are following also the Information Retrieval course at University of Pisa, check out this other exercises repository!