For instance, in spellcheck, you are more likely to confuse say \(a\) and \(e\) than \(a\) and \(b\). Therefore, sometimes we want to weight our edit distance with DP to account for these “common” paths to make certain corrections more “jarring”.

For two strings, let’s define:

• \(X\) of length \(n\)
• \(Y\) of length \(m\)

we define some \(D(i,j)\) as the edit distance between substring \(X[1:i]\) and \(Y[1:j]\).

Let:

• \(D(i,0) = i, \forall i\)
• \(D(0,j) = j, \forall j\)

for i in range(1,M):
    for j in range(1,N):
        # deletion: ignoring one char of previous string
        d1 = D(i-1,j) + 1 # (cost)
        # insertion: insertion into string before using rest of j
        d2 = D(i,j-1) + 1 # (cost)
        # keep same if char is same or substitute current
        d3 = D(i-1,j-1) + (0 if X[i] == Y[j] else 2)

        # cache
        D(i,j) = min(d1, d2, d3)

Fireside a series of articles that I’m writing to consolidate my learning.

I have always dreamed of blogging. I have even tried once called 20MinuteRants. They worked quite well as a basic format whereby I can write about things in a fairly efficient manner (hence the 20 minutes), and be able to reflect about the things I’m up to.

The problem with the project is that I rarely had the motivation to do one. Once I was too busy, or out of ideas to write about, I stop. If there’s not anything to rant about, why is there a 20MinuteRant?

in set theory, well-founded means…

1. there’s no set of all sets
2. instead, there’s an infinite hierarchy of stratified sets
   • “small” sets at stratum \(0\)
   • the set of all stratum \(0\) sets is a stratum \(1\) set
   • the set of all stratum \(1\) sets is a stratum \(2\) set
   • …

when eigenvalues of the problem setup is well-posed, eigenvalues should have a negative real part (because they are convergent); otherwise, if the eigenvalues have a positive real part, they are divergent and hence ill-posed

…what can we solve efficiently?

the “easy” cases

by definition all NP/NP Complete problems…

• SAT
• 3COL
• Hamiltonian path problem
• and also anything in coNP because if \(\text{P}= \text{NP}\), then \(\text{NP} = \text{coNP}\)
  • UNSAT
  • NOT-3COL
  • …

review: certificates definition of NP, coNP

\(L \in \text{NP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \exists w \in \qty {0,1}^{\text{poly}\qty(|x|)}, V\qty(x,w) = 1\)

\(L \in \text{coNP}\) IFF \(\exists\) polytime verifier \(V\) such that \(x \in L \Leftrightarrow \forall w \in \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x,w) = 1\)