Consider arrays a: array 0 .. M 1 of integer and f: array 0 .. N 1 of integer for M 0 and N 0. Write a predicate, P, that states that all elements of a are between 0 and N - 1.

1- Write a predicate, Q, that states that f(i) is the number of occurrences of i in a. Hint: you may use #s for the number of elements of set s and {x a .. b | R} for the set of all x a .. b satisfying predicate R.

2- Write an algorithm that under precondition P establishes postcondition Q without modifying a. You may use auxiliary variables as needed. All variables must be initialized, you cannot assume a particular initial value. Your program has to have a running time proportional to M + N. State all important intermediate annotations, in particular the loop invariants for all loops.