## 2 Materials and Methods
### Deterministic Algorithms
#### 2.2.3 An \(O(n\sqrt{k\log k})\) Time Algorithm for \(K\) Mismatches
We apply the marking algorithm for the characters whose instances are included in the knapsack. It is easy to see that the marking takes time \(O(C)\) and creates \(C\) marks. For alignment \(i\), if the pattern and the text match for all of the \(2k\) positions in the knapsack, we will obtain exactly \(2k\) marks at position \(i\). Conversely, any position that has less than \(k\) marks must have more than \(k\) mismatches, so we can filter it out. Therefore, there will be at most \(C/k\) positions with \(k\) marks or more. For such positions, we run subset \(k\) mismatches to confirm which of them have less than \(k\) mismatches. The total runtime of the algorithm in this case is \(O(C)\). Case (2): If we cannot fill the knapsack within the given budget \(B\), we do the following: for the characters we could fit in the knapsack, we use the marking algorithm to count the number of matches that they contribute to each alignment. For characters not in the knapsack, we use convolutions to count the number of matches that they contribute to each alignment. We add the two counts and get the exact number of matches for every alignment. Note that at least one of the instances in the knapsack has a cost larger than \(B/(2k)\) (if all of the instances in the knapsack had a cost less or equal to \(B/(2k)\), then we would have at least \(2k\) instances in the knapsack). Furthermore, note that all of the instances not in the knapsack have a cost at least as high as any instance in the knapsack, because we greedily fill the knapsack starting with the least costly instances. This means that every character not in the knapsack appears in the text at least \(B/(2k)\) times. This means that the number of characters not in the knapsack does not exceed \(n/(B/(2k))\). Therefore, the total cost of convolutions is \(O(nk/B\log m)\). Since the cost of marking was \(O(B)\), we can see that the best value of \(B\) is the one that equalizes the two costs. This gives \(B=O(n\sqrt{k\log m})\). Therefore, the algorithm takes \(O(n\sqrt{k\log m})\) time. If \(k<m^{1/3}\), we can employ a different algorithm that solves the problem in linear time, as in [11]. For larger \(k\), \(O(\log m)=O(\log k)\), so the run time becomes \(O(n\sqrt{k\log k})\). We call this algorithm knapsack \(k\) mismatches. The pseudocode is given in Algorithm 3. The following theorem results. **Theorem 3**. : _Knapsack \(k\) mismatches has worst case run time \(O(n\sqrt{k\log k})\).\(\square\)_  
```
input : \(T_{1..n}\) - text; \(P_{1..m}\) -pattern; k - max number of mismatches; output : \(S\) - set of positions in the text where the pattern matches with at most \(k\) mismatches; begin  Compute \(F_{i}\) and \(f_{i}\) for every \(i\in\Sigma\) ;  Sort \(\Sigma\) with respect to \(F_{i}\) ; \(s=0\); \(c=0\); \(i=1\); \(B=n\sqrt{k\log k}\) ; while\(s<2k\)and \(c<B\)do \(t=\min(f_{i},2k-s)\) ; \(s=s+t\) ; \(c=c+t\times F_{i}\) ; \(i=i+1\) ; \(\Gamma=\Sigma[1..i]\) ; \(M=\texttt{Mark}(T,n,\Gamma)\); // \(M\) counts matches if\(s=2k\)then \(S=\{i|M[i]\geq k\}\) ; returnSubset \(k\) mismatches (\(S,T,P,k\)); else for\(\alpha\in\Sigma-\Gamma\)do \(C=\texttt{convolution}(T^{\alpha},P^{\alpha})\) ; for\(i\gets 1\)to\(n\)do \(M[i]=M[i]+C[i]\) ; \(S=\{i|M[i]\geq m-k\}\); return\(S\);
```  
**Algorithm 3**Knapsack \(k\) mismatches(\(T,P,k\))  
We can think of the algorithm in [11] as a special case of our algorithm where, instead of trying to minimize the cost of the \(2k\) items in the knapsack, we just try to find \(2k\) items for which the cost is less than \(O(n\sqrt{k\log m})\). As a result, it is easy to verify the following:  
**Theorem 4**. : _Knapsack \(k\) mismatches spends at most as much time as the algorithm in [11] to do convolutions and marking._  
Proof. : Observation: In all of the cases presented below, knapsack \(k\) mismatches can have a run time as low as \(O(n)\), for example if there exists one character \(\alpha\) with \(f_{\alpha}=O(k)\) and \(F_{\alpha}=O(n/k)\). Case 1: \(|\Sigma|\geq 2k\).