M1103 Problem Set 1

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.

Problem 1 — Duplicate Detection

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:

1. if the current element is already in the collection, stop the algorithm and return false
2. 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.

a — Searching an Element in a Vector

bool contains(const vector<int> &vec, int n)
{
// TODO
return false;
}

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.

b — Function unique

bool unique(const vector<int> &vec)
{
// TODO
return true;
}

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.

Problem 2 — Merging Two Ordered Vectors

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

a — Checking Order

bool increasing(const vector<int> &vec)
{
// TODO
return true;
}

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.

b — Merge

vector<int> merge(const vector<int> &vec1,
const vector<int> &vec2)
{
// TODO
return ret;
}

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.

Problem 3 — Sieve of Eratosthenes

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:

1. generate the list of integers between $$2$$ and $$n$$

2. 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 4 5 6 7 8 9 10

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 9

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.

a — Modified Function range

vector<int> range(int m, int n)
{
vector<int> ret;

// TODO
return ret;
}

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.

b — Delete the Multiples of an Integer

void delete_multiples_from(vector<int> &vec,
int from, int k)
{
// TODO
}

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

c — Prime Numbers

vector<int> primes(int n)
{
vector<int> ret;

// TODO
return ret;
}

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.

Problem 4 (Bonus) — Mean and Median of a Vector

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.

a — Mean Value

double mean(const vector<int> &vec)
{
// TODO
return 0.0;
}

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.

b — Rank of an Integer in a Vector

int rank_of(const vector<int> &vec, int n)
{
// TODO
return 0;
}

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.

c — Median

double median(const vector<int> &vec)
{
// TODO
return 0.0;
}

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}$$.

back to the course web site