The purpose of this assignment is to introduce students to the experimental analysis of algorithms. In this assignment, we will study the behavior of two types of fundamental data structures in real$-$world situations: linked lists and dynamic arrays. Additionally, we will compare and contrast these results with the expected theoretical outcomes.

Specifically, we will utilize the data structures implemented in the C$++$ standard library for the classes std::vector and the sorting algorithms, as well as their growth orders. In this initial part, we will focus on three aspects:

std::vector

std::vector $($with pre$-$reserved memory$)$

std::list In this part, you will test the delete operations of elements and access by index to the elements of the container $($linear search vs random access$).$ For this specific experiment, if desired, you do not have to extract all elements from the array, but a fixed number if you wish.

An explanation of the above procedure would be as follows:

$-$ Create an array of N elements and element size K $($e$.$g$.,1,000,000$ elements N$,$ each of $64$ bytes K$).$

$-$ These elements do not have to be in random order.

$-$ Remove $1,000$ elements from this container of N elements:

$-$ Generate a random index of the element to be removed.

$-$ Use the container's functionality to remove the element at the obtained index.

As a runtime measure, only consider the runtime of removing the $1,000$ elements and not the creation of the container.

Note that the container size decreases slightly with each removal, so you must adjust the selection of the random index for each removal to avoid issues with out$-$of$-$range indices.

Except for the specific conditions of this experiment, the conditions of the experiment in Part $4$ remain unchanged. The applicable conditions are:

$-$ Combinations $($container$,$ container size, element size$).$

$-$ Repeat the runs several times to obtain measurements that can be averaged.

$-$ Presentation format of the data.