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.

Loading assignment...