Some Boolean retrieval systems (e.g.,Westlaw) support the proximity operator /S, which

restricts the occurrences matches to be within the same sentence.

Assume that we have created an additional positional list for $, which records the posi-

tions of the end of the sentences. E.g., for the document A B C. D E.

the position list for $ is [4, 7].

You are required to engine an algorithm to support the query A /S B. To make the task

easier, we further constrain the semantics of the query to satisfy both conditions:

the occurrences of A and B must be within the same sentence.

the occurrence of A must precede that of B.

For example, the above example document matches the query A /S C, but not C /S A.

You need to

make simple modications to the pseudocode shown in Algorithm 1, which is ex-

actly the algorithm in Figure 2.12 in the textbook. Note that we modify the

algorithm slightly so that array indexes start from 1 instead of 0. Specically,

{ you need to insert some code between Lines 6 and 7, and perform some mod-

ications to some lines afterwards.

{ In your submitted algorithm pseudocode (named Q1(p1; p2; p$)), clearly mark

the modications using color or boxes.

You can assume that there is a function skipTo(p; docID; pos), which move the

cursor of list p to the rst position such that (1) the position belongs to a document

docID, and (2) the position is no smaller than pos.