Exercises for the week 6 exercise session¶

Exercise 1¶

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

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

Exercise 2¶

  FindSpike(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 FindSpike(), if normal_trend_length-variable is always between [1,10]? What if it’s range is unrestricted? Can FindSpike be improved in the same way as FindIfOutlier?

Exercise 3¶

What is the performance of the algorithm f below, using O and Ω notation? Binary_search and lower_bound are versions of binary search. Operation “erase” on a vector is linear in the worst case. It is constant time when removing only the last element.

void f(string& s, vector<string>& foo, vector<string>& baar) {
  if(std::binary_search(foo.begin(), foo.end(), s)) {
      auto iter = std::lower_bound( baar.begin(),  baar.end(), s );
      while (iter != baar.end()) {
          // vector::erase returns the next element to the removed one
          iter = baar.erase(iter);
      }
  }
}