## 2 Materials and Methods
### Deterministic Algorithms
#### 2.2.3 An \(O(n\sqrt{k\log k})\) Time Algorithm for \(K\) Mismatches  
For the \(k\) mismatches problem, without wild cards, a fairly complex \(O(n\sqrt{k\log k})\) time algorithm is given in [11]. The algorithm classifies the inputs into several cases. For each case, it applies a combination of marking followed by a filtering step, the Kangaroo method, or convolutions. The goal is to not exceed \(O(n\sqrt{k\log k})\) time in any of the cases. We now present an algorithm with only two cases that has the same worst case run time. The new algorithm can be thought of as a generalization of the algorithm in [11], as we will discuss later. This generalization not only greatly simplifies the algorithm, but it also reduces the expected run time. This happens because we use information about the frequency of the characters in the text and try to minimize the work done by convolutions and marking. ```
input : \(S\) - set of positions in the text; \(T_{1..n}\) - text; \(P_{1..m}\) -pattern; k - max number of mismatches; output : \(M\) - the positions in \(S\) for which the pattern matches the text with at most \(k\) mismatches; begin  Assume we have a suffix tree/array of the pattern; for\(a\in S\)do\(M[a]=0\); \(i=1\) ; while\(i\leq n\)do  Find the largest \(l\), such that \(T_{i..i+l-1}\) describes a path in the suffix tree;  This means that \(T_{i..i+l-1}=P_{j..j+l-1}\) for some \(j\); for\(a\in S\)where\(a\leq i<a+m\)do \(M[a]=\texttt{countMismatches}\left(M[a],i-a+1,j,l\right)\) ; if\(t_{i+l}\
eq p_{j+l}\)then\(M[a]=M[a]+1\); if\(M[a]>k\)then\(S=S-\{a\}\); \(i=i+l+1\) ; return\(\{a\in S|M[a]\leq k\}\) functioncountMismatches(\(c,s_{1},s_{2},l\)) input : \(c\) - current number of mismatches; \(s_{1},s_{2}\) - starting positions of two suffixes of the pattern; \(l\) - a maximum length; output : compare the two suffixes on their first \(l\) positions and add to \(c\) the number of mismatches found; if \(c\) exceeds \(k\), return \(k+1\), otherwise return the updated \(c\) ; begin while\(l>0\)and\(c\leq k\)do \(d=\texttt{lcp}(s_{1},s_{2})\); // longest common prefix if\(d\geq l\)thenreturn\(c\); \(c=c+1\); \(d=d+1\); \(s_{1}=s_{1}+d\); \(s_{2}=s_{2}+d\); \(l=l-d\); return\(c\)
```  
**Algorithm 2**Subset \(k\) mismatches(\(S,T,P,k\))  
We will now give the intuition for this algorithm. For any character \(\alpha\in\Sigma\), let \(f_{\alpha}\) be its frequency in the pattern and \(F_{\alpha}\) be its frequency in the text. Note that in the marking algorithm, a specific character \(\alpha\) will contribute to the runtime a cost of \(F_{\alpha}\times f_{\alpha}\). On the other hand, in the case of convolution, a character \(\alpha\) costs us one convolution, regardless of how frequent \(\alpha\) is in the text or the pattern. Therefore, we want to use infrequent characters for marking and frequent characters for convolution. The balancing of the two will give us the desired runtime. A position \(j\) in the pattern where \(p_{j}=\alpha\) is called an instance of \(\alpha\). Consider every instance of character \(\alpha\) as an object of size \(1\) and cost \(F_{\alpha}\). We want to fill a knapsack of size \(2k\) at a minimum cost and without exceeding a given budget \(B\). The \(2k\) instances will allow us to filter some of the alignments with more than \(k\) mismatches, as will become clear later. This problem can be optimally solved by a greedy approach, where we include in the knapsack all of the instances of the least expensive character, then all of the instances of the second least expensive character, and so on, until we have \(2k\) items or we have exceeded \(B\). The last character considered may have only a subset of its instances included, but for the ease of explanation, assume that there are no such characters. Note: Even though the above is described as a knapsack problem, the particular formulation can be optimally solved in linear time. This formulation should not be confused with other formulations of the knapsack problem that are NP-complete. Case (1): Assume we can fill the knapsack at a cost \(C\leq B\).