Binary Heap, Heap-sort, Counting-sort, Chained Hash Table, Open Hash Table, RB-Tree (no delete), Dynamic Programming, Huffman Code, Shortest Path Algorithms for Graph (Belman-Ford, Dijkstra, Floyd-Warshall).

Students will use the exercise platform Coding Contest to take a practical exam. Alternatively, students can apply for a project. Send an email to professor Simone Faro (faro at dmi dot unict dot it) to request credentials. Without such an account, students cannot take the exam. Due to the pandemic emergency, learning assessments and exams may also or exclusively be carried out on line, should the conditions require it.

Projects are no more available. Students may apply for a project at any time of the academic year. The following guidelines must be observed in order to correctly carry out the exam:

1. The topic of the project must be agreed with the teacher.
2. A topic can be assigned only to one student per academic year.
3. The project must be carried out individually.
4. Students are supposed to inform the teacher about the progress of the project, in order to avoid frustaing refactoring and modifications (and waste teacher's time).
5. A report must be written before the software.
6. LateX and the OverLeaf platform are strongly suggested to write the report.
7. The report must contain at least:
   1. Both a brief theoretical and informal introduction to the data-structure/algorithm.
   2. An explanation of the methods togheter with the related pseudo-code and computational costs.
   3. An example for each method.
   4. Proofs, if they are short, otherwise a citation to the paper/book presenting the proof.
   5. Approaches to the possible implementations with related pros and cons.
   6. A motivation of the choosen approach.
   7. The UML describing the modelling choices (and related motivations).
   8. A clear description of how to use the provided implementation.
8. The teacher will provide comments only to the alpha version of the documentation. From such point on, the student is supposed to move autonomously.
9. The software must be delivered with the report, the latter both as PDF and source format.
10. The software must be compilable both with g++ and MC++.
11. If the source code is available as multiple files, a make file for g++ and a VS project are required.
12. The software should be shared with the teacher through a github/gitlab repository.
13. The software must be accompanied by a main file showing how the principal methods work.
14. High quality of the software is mandatory to consider the exam passed.
15. These instructions must be considered as a check-list for the evaluaiton of the project.

The following topics have already been choosen:

1. Radix Tree.
2. Splay Tree.
3. Dynamic Disjoint Sets.
4. B-Tree.
5. Fibonacci Heap.
6. Binomial Heap.
7. Trie.
8. Rabin-Karp algorithm.
9. Skip List.
10. Ford-Fulkerson algorithm.
11. Kruskal-Prim algorithm.
12. Self-Organizing List.
13. KD-Tree.
14. AVL Tree.
15. Double Hashing.
16. Treap.
17. Rope.
18. Suffix Tree.
19. Dynamic Hash Table.
20. Van Emde-Boas Tree.
21. Benchmark among string matching algorithms.
22. The Road Cutting problem.
23. The simplex algorithm.
24. Point QuadTree.
25. Knuth-Morris-Pratt algorithm.
26. Optimal Binary Search Tree.
27. Boyer-Moore Algorithm.
28. ASM for string matching algorithms.