Question

For any sequence, S[1…n], of length n, a basement is defined as a contiguous subsequence of S, which we denote by S[ i, i + 1, ..., j – 1, j ], with 1 £ i < i + 1 <   j – 1 < j £ n, satisfying the following conditions:

• S[ i ] > S[ i + 1]
• S[ j – 1] < S[ j ]
• 1 £ i < i + 1 <   j – 1 < j £ n
• S[ r ] = S[ t ] for all i < r, t < j

The length of a basement is defined as the count of the elements that make up the basement sequence. As an example, for the sequence

S = [3, 2, 0, 0, 0, 0, 4, 4, 6, 5, 5, 5, 3, 7, 7, 7, 7]

We note that [2, 0, 0, 0, 0, 4,] is a basement (which you can verify, using the definition of a basement), and the length of the basement [2, 0, 0, 0, 0, 4,] is 6. The starting index for this basement is 2 and the ending index for this basement is 7. We also note that [6, 5, 5, 5, 3] is NOT a basement.

1. Explain why [6, 5, 5, 5, 3] is NOT a basement by clearly pointing out the criteria that holds, as well as the criteria that fails to hold. Circle your choice, or highlight it.      (2 points)

S[ i ] > S[ i + 1]	HOLDS / FAILS	1 £ i < i + 1 <   j – 1 < j £ n	HOLDS / FAILS
S[ j – 1] < S[ j ]	HOLDS / FAILS	S[ r ] = S[ t ] for all i < r, t < j	HOLDS / FAILS

2. Explain why [7, 7, 7, 7] is NOT a basement by clearly pointing out the criteria that holds, as well as the criteria that fails to hold. Circle your choice, or highlight it.      (2 points)

S[ i ] > S[ i + 1]	HOLDS / FAILS	1 £ i < i + 1 <   j – 1 < j £ n	HOLDS / FAILS
S[ j – 1] < S[ j ]	HOLDS / FAILS	S[ r ] = S[ t ] for all i < r, t < j	HOLDS / FAILS

3. Identify ALL of the basements of the following sequence: (2 points)

S = [2, 1, 4, 1, 1, 0, 6, 6, 6, 5, 5, 5, 10, 3, 3, 3, 3, 3, 3, 6, 6, 4, 0, 10, 0]

Determine an efficient algorithm to find the starting and ending indices of a basement in a sequence, S, whose length is maximal (in the event that there are multiple basements whose length is maximal, return the starting and indices of ONE of them).   (10 points total: Full points given for a linear algorithm).

Answer 1

[6, 5, 5, 5, 3] is NOT a basement.

Conditions it is holding are:

S[ i ] > S[ i + 1] because 6>5

1 £ i < i + 1 <   j – 1 < j £ n

S[ r ] = S[ t ] for all i < r, t < j (all are having values 5)

Conditions it is not holding(FAILING) is:

S[ j – 1] < S[ j ] Because 5 is not less than 3

[7,7,7,7] is NOT a basement.

Conditions it is holding:

1 £ i < i + 1 <   j – 1 < j £ n

S[ r ] = S[ t ] for all i < r, t < j (all have value 7)

Conditions it is failing are:

S[ i ] > S[ i + 1] because 7 is not greater than 7

S[ j – 1] < S[ j ] because 7 is not lesser than 7

S = [2, 1, 4, 1, 1, 0, 6, 6, 6, 5, 5, 5, 10, 3, 3, 3, 3, 3, 3, 6, 6, 4, 0, 10, 0]

All the basements of S are:

[2,1,4]

[1,0,6]

[6,5,5,5,10]

[10,3,3,3,3,3,3,6]

[4,0,10]

Algorithm to find maximal Basement:

1. Let S be sequence with length of S be n.

2. start= -1, end= -1, curr_start = -1, curr_end = -1. Initialize start, end, current start and current end to -1. Start and end represent the final maximal start and end index whereas current start and current end represent the temporary start and end values.

3. Assign from index(i) 2 and loop till i = n-1

4. If S[i-1]<S[i] or S[i+1]<S[i] then set cur_start = -1, cur_end = -1

5. else if S[i-1]>S[i] and S[i+1]>S[i] then set cur_start = i-1 and cur_end = i+1 and if end - start +1 <= cur_end-cur_start+1 then set start = cur_start and end = cur_end and cur_start = -1 and cur_end = -1.

6. else if S[i-1]>S[i] and S[i]=S[i+1] then set cur_start = i-1, cur_end = -1

7. else if S[i-1] = S[i] and cur_start is not -1 and S[i] < S[i+1] then set cur_end = i+!. If end-start+1 <= cur_end - cur_start+1 then set start = cur_start, end = cur_end and cur_start = -1, cur_end = -1.

8. The start and end are the maximal basement starting and ending indices.

Time complexity of this algorithm = O(n) = Linear time complexity