Exercise 1a - Efficiency of algorithms - FindIfOutlier¶

Homework exercises had the algorithm FindIfOutlier, pseudocode of which is below. What was the efficiency of the algorithm and how could it be improved?

1
2
3
4
5
6

   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END

Exercise 1b - Efficiency of algorithms - improved version¶

1 2 3 4 5 6

FindSpikes(Vector v, int max_var, int normal_trend_length): FOR index IN v: IF max_var > |v[index] - MeanOfRange(v, index, index+normal_trend_length)|: RETURN v[index] END END

What is the asymptotic efficiency of FindSpikes(), if normal_trend_length-variable is always between [1,10]? What if it’s range is unrestricted? Can FindSpikes be improved in the same way as FindIfOutlier?

Exercise 2a - Customizing STL algorithms¶

In this exercise you are given a vector places that contains items of type struct Place{ int x; int y; string name; }. Your task is to customize available STL algorithms to perform the following:

1. Sort the elements of places according to the following criteria:
   • first in ascending order of the x coordinate
   • then in ascending order of y coordinate, if two elements have equal x coordinates,
   • and finally in dictionary order of the name, if both the x and y coordinates are equal.
2. Sort the elements of places according to the following criteria:
   • first according to their distance from the origin {0,0} in ascending order
   • and then in dictionary order of the name, if the distances from the origin are equal.

Exercise 2b - Customizing STL algorithms - continuation¶

Continuation to Exercise 2a:

1. Create a new vector nearby1, that contains all elements whose distance from the origin is between 10 and 20.
2. Create a new vector nearby2, that contains all elements whose distance from the origin is between low and high, where low and high are parameters provided by the user.
3. Erase all items from vector places, that contain string ”Unlisted” in their names or have an x coordinate or a y coordinate less than 1.

Bonus: How many comparisons are being done for the sorts in a and b?