Laboratory of Algorithms and Data Structures

UniFe - 2020/2021

Ex 1

Hybrid Sort: Merge Sort and Inserion Sort combined togheter

• In this experiment, both InsertionSort and MergeSort are implemented.
• We measure the experimental execution time for inputs of increasing length, with multiple repetitions for the same length, on both algorithms.
• We infers the value of k (maximum crossing point between the curves) for our own machine and implementation.

Ex 2

Hash Table VS Red Black Tree

• We conduct an experiment implementing both a hash table with conflicts resolved via chaining and a red-black tree.
• We measure and compare the average time for n operations with n increasing, random greater than zero integer keys, on both structures.
• We perform some comparisons for different values of m (fixed size of the hash table) and different proportions between number of insertions and number of searches.

Ex 3

Dijkstra: Array VS Binary Heap

• We perform an experiment implementing the Dijkstra algorithm using either an array or a binary heap as the priority queue.
• We measure the average execution time as the size of the graph increases for a fixed source and as the density varies in both versions.
• We compare the execution times.