Q2:

A SKIP array S[0..n 1] is an array of n integers, where n > 1, in which S[0] = 0 and S[n 1] = n. i is a SKIP index in a SKIP array S if n > i > 0 and S[i] > S[i 1] + 1.

(a) Explain why every SKIP array has at least one SKIP index.

Example: The SKIP array {0,2,3,0,4,6} has 3 SKIP indices: 1,4, and 5.