## 3 Algorithm I: Basic Algorithm
### Conflict Resolution
In fact, from the definition above, we see that the size of the neighborhood is at most 6. For \(CP(i,j)\), the neighbors will be the conflict pairs in the set \(CP(i^{\prime},j^{\prime})\), with \((i^{\prime}=i-2^{h},j^{\prime}=j-2^{h})\); \((i^{\prime}=i+2^{h},j^{\prime}=j+2^{h})\); \((i^{\prime}=i-2^{h-1},j^{\prime}=j-2^{h-1})\); \((i^{\prime}=i+2^{h-1},j^{\prime}=j+2^{h-1})\); \((i^{\prime}=i-2^{h-2},j^{\prime}=j-2^{h-2})\); and \((i^{\prime}=i+2^{h-2},j^{\prime}=j+2^{h-2})\). Some of these pair of indices may not be valid indices for a conflict pair. For example, using the previous example, \(R_{6}=CP(2,14)\) has only one valid neighbor, \(\{R_{2}=CP(0,12)\}\). Also, given that we resolve the conflicts based on the depth first traversal order, neighbors of \(CP(i,j)\) that are located on a node to the right of \(CP(i,j)\) in the conflict tree cannot be used to resolve conflict \(CP(i,j)\). Therefore, in some cases, less than six probes may be needed. Let \(CP(i,j)\) be the current conflict. Let \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) be a previously resolved neighboring conflict. We determine whether \(CP(i,j)\) can be resolved based on \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) using a simple check: Let \(\Delta=(i^{\prime}-i)=(j^{\prime}-j)\). If \(\Delta\) is negative, then \(CP(i,j)\) can be resolved with \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) iff: \(|\Delta|\leq l^{\prime}_{k}-1\) Conversely, if \(\Delta\) is positive, then \(CP(i,j)\) can be resolved with \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) iff: \(l^{\prime}_{k}\geq 0\) If any of the two conditions holds, we say that \(CP(i,j)\) is resolved by \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\), after \(\Delta\) steps. Essentially, this means that after \(\Delta\) comparison steps, \(CP(i,j)\) becomes equivalent to \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\). We denote this equivalence using the notation: \(CP(i,j)\mapsto CP(i^{\prime},j^{\prime},l^{\prime}_{k})\). The following algorithm shows how we can resolve a given conflict pair, \(CP(i,j)\). ```
ResolveConflict(\(i,j\)) Generate neighbors for \(CP(i,j)\) Remove invalid neighbors Probe the valid neighbors for previously resolved conflict pairs for each valid neighbor, compute the quantity \(d=(l^{\prime}_{k}-|\Delta|)\); endfor Select the neighbor \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) with maximum value for \(d\) if (\(\Delta<0\) and \(|\Delta|\leq l^{\prime}_{k}\)), then /* no extra work is needed */  Compute \(l_{k}=l^{\prime}_{k}+\Delta-1\). elseif (\(\Delta>0\) and \(l^{\prime}_{k}\geq 0\)), then  Perform at most (\(\Delta-1\)) extra comparison steps if (conflict is not resolved after the \(\Delta-1\) comparisons), then /*Resolve conflict using \(CP(i^{\prime},j^{\prime},l^{\prime}_{k})\) */  Compute \(l_{k}=l^{\prime}_{k}+\Delta\) endif endif else /* conflict cannot be resolved using earlier conflicts */  Resolve conflict using direct symbol-wise comparisons endif
```  
**Algorithm 10**  
The complexity of conflict resolution (when it can be resolved using previous conflicts) thus depends on the parameter \(\Delta\). Table 1 shows the conflict pairs for the example sequence used to generate the conflict tree of Figure 2. That table includes the corresponding \(\Delta\) value where a conflict can be resolved based on a previous conflict. The final consideration is how to store the conflict tree to ensure constant-time access to the resolved conflict pairs. Since for a given \(CP(i,j)\), the \((i,j)\) pair is unique, we can use these for direct access to the conflict tree. We can store the conflict tree as a simple linear array, where the positions in the array are determined based on the \((i,j)\) values, and hence the height in the tree. To avoid the sorting that may be needed for fast access using the \((i,j)\) indices, we use a simple hash function, where each hash value can be computed in constant time. The size of this array will be \(O(n\log n)\) in the worst case, since there are at most \(n\log n\) conflicts (see analysis below).