Course topic 10 exercises¶

In these following exercises you are supposed modify the provided code to and to optimize the given functions to make them more performant. Your code is then run and compared to the reference implementation made by the course staff.

The comparison is done by calculating the number of instructions your code runs during the execution compared to the number of instructions run by the reference implementation. Note that this includes also the instructions run by any SLT algorithms you choose to use.

Grading is done as follows:

if your code performs within 15% of the reference information you will receive full 5/5 points
if your code performs at least 10% better than the original template code but still over 15% slower than the reference implementation you receive 3/5 points
if your code performs slower than the original template code or within 10% of its performance you receive 0/5 points

Attention

You are allowed to use all STL algorithms and other methods you can think of. However, the function must still be callable in the grader. This means that you not allowed to change the return type or the number and the types of the arguments of the function with the one exception of making the arguments const references if you so choose. You are also allowed to create helper functions if you need to.

However, using std::sort is NOT allowed in the last exercise where you need to optimize a sorting algorithm.

NOTE: Your code will be tested with vectors as large as 1,000,000 (one million) elements. Make sure you test your functions with large vectors with the provided program.

These exercises are returned with git URL. First, pull the latest updates from course-upstream, implement the missing algorithms/functions in the four files wk05_graphs/improving_functions/improve1.cc through wk05_graphs/improving_functions/improve4.cc one file for each function.

You can use cplusplus.com’s algorithm pages or similar resources to help you.

Return a vector of integers with ascending numbers from 0 to n-1

Your answer should be in the file wk05_graphs/improving_functions/improve1.cc

Gets the smallest value from the vector passed as a parameter or 0 (zero) if the vector is empty.

Your answer should be in the file wk05_graphs/improving_functions/improve2.cc

Sums up the values of a vector cumulatively, storing cumulative sum of the vector in a map, where the keys are the unique vector items, and the value is the last cumulative sum at the time when that value was last encountered.

Example:

assume vector [4, 5, 4, 6]
function returns the following map: {{4, 13}, {5, 9}, {6, 19}}
1. Start from the beginning of the vector and assign the value 4 under the key 4 in the map
2. Take the cumulative sum (4 + 5) and save that under the key 5
3. Take the cumulative sum (4 + 5 + 4) and save that under the key 4
4. Take the cumulative sum (4 + 5 + 4 + 6) and save that under the key 6

Your answer should be in the file wk05_graphs/improving_functions/improve3.cc

Sort a given vector using a 3 part randomized quicksort algorithm. Randomization is used to avoid worst case (where the pivot value is chosen poorly).

NOTE!! Using std::sort is forbidden in this exercise!

Your answer should be in the file wk05_graphs/improving_functions/improve4.cc