**Before you begin : activate C++14**

Vectors are only one of the data structures that exist in C++. The choice of the right data structure is fundamental to the solution of every algorithmic problem. You will learn the advantages and disadvantages of the most common data structures in other courses. In this introductory course, however, we stick to vectors, which are often a reasonable choice.

The problems of this problem set are intended to deepen your understanding with the class `vector`

of C++. This correct use of vectors is key to their solution.

Download the file `code.zip`

and add its content (the files `unique.cpp`

, `unique.h`

, `merge.cpp`

, `merge.h`

, `sieve.cpp`

, `sieve.h`

, `median.cpp`

, `median.h`

, `test.cpp`

, `asserts.h`

) to a new Code::Blocks project.

You can test your functions by executing the program whose `main`

function is defined in the file `test.cpp`

.

A naïve approach to solve this problem is a double loop that compares all pairs of elements of the vector and returns

`true`

as soon as we find two equal elements at different indices. Here, we will rather prefer an algorithm that separates the two loops into two different functions to have a cleaner conceptual architecture of our algorithm.

In this first problem we want to solve the following basic question: For a given vector of integers, we want to know whether it contains a *duplicate*, i.e., an element that occurs at least twice.

We will traverse the vector from start to end while updating a collection of integers, which is empty initially. For every element of the vector, we do two things:

- if the current element is already in the collection, stop the algorithm and return
`false`

- add the current element to the collection

We note that the collection of integers in every iteration contains all elements of previous iterations. If the vector contains a duplicate, our algorithm thus returns `false`

at the second occurrence of the duplicate.

Finish the function `contains`

in the file `unique.cpp`

. This function takes as parameters (a constant reference to) a vector of integers `vec`

and an integer `n`

. It returns `true`

if the integer `n`

is contained in the vector `vec`

, and `false`

if not.

We will use this function to look for the current element in the collection of integers (which will be implemented by a vector) in the above step 1.

`unique`

Finish the function `unique`

in the file `unique.cpp`

. This function takes as a parameter (a constant reference to) a vector of integers and returns `true`

if and only if all elements of the vector are unique, i.e., the vector does not contain any duplicates.

In this problem we want to merge two ordered vectors such that the resulting vector is ordered as well. For example, if the two to-be-merged vectors are

2 | 4 | 5 | 7 | 8 |

and

1 | 3 | 6 | 9 | 10 |

then the merged vector is:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

We start by checking whether a given vector of integers is in strictly increasing order. For that, we need to traverse the vector only once, comparing all pairs of adjacent elements,

Finish the function `increasing`

in the file `merge.cpp`

. This function takes as a parameter (a constant reference to) a vector of integers and returns `true`

if and only if the elements are in strictly increasing order.

We will now implement the function that does the merge. One possibility to construct the merged vector is to keep an index `i1`

into the first vector and an index `i2`

into the second vector. In every iteration of the main loop, we compare the elements corresponding to the two indices. We then add the smaller of the two elements to the to-be-returned vector and increment the corresponding index . If one of the indices reaches the end of the vector, we exit the main loop and then add all remaining elements of the other vector.

Finish the function `merge`

in the file `merge.cpp`

. This function takes as parameters two (constant references to) vectors of integers and returns a vector of integers. The returned vector should contain all elements of the two input vectors in increasing order. You can assume that all elements in the two vectors are different.

We now want to write a function that returns all prime numbers up to a given upper bound \(n\). For that, we use the Sieve of Eratosthenes. It does the following steps:

generate the list of integers between \(2\) and \(n\)

for every integer in the list, beginning at the left: delete all multiples of this integer to the right of the current element

An example with \(n=10\). After step 1, the list is:

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

The first iteration of step 2 deletes all multiples of \(2\) to the right of entry \(2\):

2 |
3 | 5 | 7 | 9 |

The remaining list after the first iteration thus is:

2 | 3 | 5 | 7 | 9 |

The second iteration of step 2 now looks at the element following \(2\), i.e., \(3\). We hence delete all multiples of \(3\) to the right of entry \(3\):

2 | 3 |
5 | 7 |

This gives us the following list after the second iteration of step 2:

2 | 3 | 5 | 7 |

The algorithm does two more iterations with \(5\) and \(7\) without finding any multiples to delete. The last list is thus the final result of the Sieve of Eratosthenes with the parameter \(n=10\). We check that the prime numbers smaller or equal to \(10\) are indeed \(2\), \(3\), \(5\), and \(7\), The output is hence correct.

`range`

We begin by implementing step 1:

Finish the function `range`

in the file `sieve.cpp`

. This function takes as parameters two integers `m`

and `n`

. It returns the vector of integers between `m`

(included) and `n`

(excluded).

For `m`

\(=2\) and `n`

\(=11\), the function returns the vector whose elements are \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), \(10\). If `m`

\(\geq\)`n`

, then the returned vector is empty.

You can take and modify your implementation of the function `range`

of Mini-Set 1.

We will now implement a single iteration of step 2.

Finish the function `delete_multiples_from`

in the file `sieve.cpp`

. This function takes as parameters (a reference to) a vector of integers `vec`

and two integers `from`

and `k`

. It deletes all multiples of `k`

in the vector `vec`

at indices larger or equal to `from`

.

A call to this function with the vector `vec`

equal to

6 | 3 | 2 | 4 | 3 | 8 |

and the integers `from`

\(=3\) and `k`

\(=2\) deletes the elements \(4\) and \(8\). While \(2\) is indeed multiples of `k`

\(=2\), the element \(2\) is not deleted because it is at index \(2\), which is not larger or equal to `from`

\(=3\). The vector `vec`

after the call hence is:

6 | 3 | 2 | 3 |

We now have all the tools to implement to Sieve of Eratosthenes using the two steps described earlier, using the functions `range`

and `delete_multiples_from`

.

Finish the function `primes`

in the file `sieve.cpp`

. This function takes as a parameter an integer `n`

. It returns the vector of prime numbers smaller or equal to `n`

.

In this problem, we will calculate the mean and the median of a vector of integers. The mean of a vector with the elements \(x_0,x_1,\dots,x_{n-1}\) is given by the formula \[\bar{x} = \frac{x_0+x_1+\cdots+x_{n-1}}{n}.\] The median of an ordered vector \(x_0 \leq x_1 \leq \cdots \leq x_{n-1}\) is is a value for which half of the elements are smaller and the other halt is larger. more precisely, the median is given by:

- \(x_{(n-1)/2}\) if \(n\) is odd
- \(\frac{1}{2} x_{(n-2)/2} + \frac{1}{2} x_{n/2}\) if \(n\) is even

For example, the median of the vector

1 | 2 | 3 | 4 | 5 |

is the element at index \(\frac{n-1}{2} = \frac{5-1}{2} = \frac{4}{2} = 2\), i.e., \(x_2 = 3\). The median of the vector

1 | 2 | 3 | 4 |

is the average of the elements at indices \(\frac{n-2}{2} = \frac{4-2}{2} = \frac{2}{2} = 1\) and \(\frac{n}{2} = \frac{4}{2} = 2\), i.e., \(\frac{1}{2} x_1 + \frac{1}{2} x_2 = \frac{1}{2} 2 + \frac{1}{2} 3 = 2,5\).

Later in the course we will learn how to sort a vector to directly reduce the case of a non-ordered vector to that of an ordered vector.

The preceding definition of the median assumes the vector to be ordered. For a non-ordered vector, we define its median as that of its ordered version. It will be necessary to calculate, for every element of a non-ordered vector, the number of elements that are smaller or equal to the given element.

The type

`invalid_argument`

is part of the C++ standard library. It describes the general situation of a function called with an invalid parameter. We can throw an exception of type`invalid_argument`

via`throw invalid_argument("message")`

. Instead of the string`message`

, we can give a more precise description of the thrown exception.

For an empty vector, neither the mean nor the median is well-defined. In that case, we will hence throw an exception. We choose the type `invalid_argument`

for the exception.

Before dealing with the more difficult problem of calculating the median, we begin by calculating the mean.

Finish the function `mean`

in the file `median.cpp`

. This function takes as a parameter (a constant reference to) a vector of integers and returns the mean value of its elements. If the vector is empty, then it throws an exception of type `invalid_argument`

.

Finish the function `rank_of`

in the file `median.cpp`

. This function takes as parameters (a constant reference to) a vector of integers `vec`

and an integer `n`

. It returns the number of elements of `vec`

that are smaller or equal to `n`

.

Finish the function `median`

in the file `median.cpp`

. This function takes as a parameters (a constant reference to) a vector of integers and returns its median. If the vector is empty, then it throws an exception of type `invalid_argument`

.

Hint: Start with the case of an odd number of elements and use the function `rank_of`

to find an element whose rank is minimal among the ranks strictly larger than \(\frac{n-1}{2}\).