4. Linear Probing Iterator The class slides mention that it is possible to iterate through (visit) each of the n keys in a linear probing hash table in O(n)total time. In this problem you will prove that each step of this iteration process takes O (1) amortized time. We will analyze an iterator interface similar to the ones in the C++ programming language. An iterator starts out located at the first key, and can move to a subsequent key. Eventually an iterator moves past the end, at which point the iteration is over. First, give pseudocode definitions for the following operations. We expect each to be simple and only a few lines long. 1/ Given a linear probing hash table T, initialize the iterator // to be located at the first key of T. If T is empty, the iterator // is past the end. ITER.BEGIN(T) // Return true if the iterator is past the end, or false otherwise. ITER_PAST_ENDO // Return the key at the iterator's current location. // The iterator must not be past the end; this function throws // an exception if ITER_PAST_ENDO is true. ITER_KEYO // Move the iterator to the next location. // If the iterator is past the end, this operation has no effect. ITER_NEXTO After you have designed these operations, analyze them and prove that each takes 0 (1) amortized time. As in question 1, you should define your potential function $; then for each operation, state its actual time, the change in potential, and the amortized time. Your analysis will probably need to use the fact that linear probing hash tables maintain a moderate load factor. Recall that, for a hash table storing n keys with table size N, the load factor is defined as a = f. You may assume that the table you are iterating through maintains