ProjectASD

This is the project of Algorithm and Data Structure of UniUd

Part one

Selection algorithms Implement and compare these three algorithms:

• Quick Select
• Median of Medians Select
• Heap Select

ToDo:

• Calculate the resolution of your device
• Write the code of the three algorithms
• Execute them
• Prove their theorical complexity:
  • take time needed for the execution of each algorithm, with different array dimensions
  • re-execute it if 1% relative error is not respected
  • save and store all data about execution time spent and its standard deviation
  • plot data found
  • compare sperimental and asyntotic data
• Write the final relation with graphs of data found

Link for the 1 relation

Part two

Binary Search Trees (BST) Implement and compare these three tyes of BST:

• Generic BST (non balanced)
• Red-Black Tree (RBT)
• Adelson-Velskij e Landis (AVL)

ToDo:

Same as on top, but execution has the scheme:

• generate empty BST
• repeat as follow for n = 1k to n = 1mln:
  • generate randomly n numbers
  • foreach number find it in BST, if not found then insert it in BST
• store all execution time data
• analyze data with log scaled graphs on both axis

At the end of computation will be done:

• number of finds: n
• number of insert: m
• m <= n
• m == n if all generated numbers are different each other (no repetitions)
• so m tends to n if gets harder to generate same number 2 times, which means:
  • random numbers possible range increases
  • array size decreases

Link for the 2 relation