Algorithm Implementation & Optimization

**First task:** Implementation of the algorithm described in this paper: [[login to view URL]~lorys/IPL/[login to view URL]][1] with time complexity and space complexity defined in the paper. **Second task:** ? There is an array A of size N that stores the integer values. The maximal value of item in the array A is S. We need the algoritm that can query the next position of item I from specified position J. ? For ex.: The array A: 1,2,1,4,3,8 ? Query: ? J = 1, I = 2, result 2 J = 2, I = 4, result 4 J = 4, I = 8, result 6 J = 5, I = 5, result -1 (Not found); ? The time complexity for M random queries must be in this bounds O(M * min(log N, log S)). Space complexity must be O(N) Such algorithm is explained in this paper: ? [[login to view URL]][2] ? page 9, starting from 3rd paragraph. ## Deliverables The implementation language is C++, non STL preferably.? As bidders can see, the first task is an optimization of original algorithm by the same authors. The bidder needs to implement the original algorithm <[login to view URL]> with optimization described in the paper? in the bid request.