582484 Algorithm Libraries

Exercise 1

  1. Implement an iterator that iterates over a sequence that contains all values of int in increasing order. This sequence does not actually exist but the iterator behaves as it was there. An iterator is iniatialized by giving the value it points to as an argument to the constructor. For example, the sequence [-1,0,1,2] would be represent as an iterator range with [int_range_iterator(-1),int_range_iterator(3)). Implement enough functionality to make it work with the find algorithm from the lectures. Write a small test program to verify this.
  2. Write a class smooth_iterator that iterates over an array of floats. The dereference operator (operator*) returns the average of the pointed to value and its two immediate neighbours. For the first and the last position, the average is over two instead of over three. For example, [1.0,5.0,3.0,1.0] would turn into [3.0,3.0,3.0,2.0] when seen through the smooth_iterator. Implement enough functionality to make it work with the find algorithm from the lectures.
  3. In the find algorithm given on the lectures, the type of third argument is a template parameter T that is independent of the input sequence. It could be of different type than the elements of the sequence.
    1. What happens if T is different? Describe the different possibilities and give examples. Test the examples in actual code.
    2. The value type of the sequence (the type of the elements) can be determined at compile time using iterator traits. Then we could have the true value type as the type of the third argument. Discuss the advantages and disadvantages of this alternative to the current one.
    1. Implement an algorithm count_equal that compares two sequences and counts how many times they have an equal value in the same position. For example, given the sequences [1,2,3,4] and [2,2,3,3], the algorithm would return 2 (the middle two positions). The algorithm should be as generic as possible.
    2. The algorithm takes two sequences as an input. If each sequence is represented by a pair of iterators, the algorithm has four arguments. Instead, the second sequence could be represented by just the begin iterator. The end is implicit if we assume that the two sequences have the same length. Discuss the advantages and disadvantages of the two alternatives.