# Question
Title: Maximize enclosed area of given figures on 2d grid
I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area they enclose is maximal.

Staying with our Tetromino example, the optimal solution would be:

Bruteforcing the problem becomes unfeaseable very quickly, especially since my check with bfs search alone that an area is even enclosed at all must be performed countless times. I tried to implement systems to recognize when it won't be possible to close the circle with the remaining polyominoes, but didn't achieve a significant speed-up with them.

I also researched into strategies for the related polyomino tiling problem to see if I can adapt them, but had no success so far. The most promising approach I found was to translate it into Mixed-Integer Linear Programming like here or in this variation. But to apply this approach to my problem I need to both add the restriction of the enclosed area and then formulate its size as a linear objective function, whereby especially the encoding of the latter may not be possible at all.

Are there other algorithms to find the global maximum for this type of optimization problem that I've overlooked? Or are there data structures or strategies for branch elimination to drastically speed up the search of all possibilities?

# Answer
Here is one possible approach. Introduce boolean variables $x\_\ell,y\_\ell,z\_{\ell,p,r}$, where $\ell$ ranges over locations in the grid, $p$ ranges over polyominoes, and $r$ over rotation amounts (0, 90, 180, 270), with the following meaning:

* $x\_\ell$ is true means that $\ell$ is part of the interior region that is enclosed (not including the boundary/perimeter)
* $y\_\ell$ is true means that $\ell$ is part of the boundary/perimeter (it is covered by a polyomino)
* $z\_{\ell,p,r}$ means that polyomino $p$ is rotated by $r$ degrees and then placed at location $\ell$

Now you can write down some boolean constraints regarding the relationships between these. For instance:

* $x\_\ell \land \neg y\_{\ell'} \implies x\_{\ell'}$, for all pairs of adjacent locations $\ell,\ell'$
* $z\_{\ell,p,r} \implies y\_{\ell+t}$ for all offsets $t$ that are part of $p$ after being rotated by $r$ degrees
* $y\_{\ell} \implies \bigvee\_{p,r,t} z\_{\ell-t,p,r}$ where the logical-OR ranges over all $p,r$ and all offsets $t$ that are part of $p$ after being rotated by $r$ degrees
* no two polyominoes overlap, which can be expressed in terms of $\neg (z\_{\ell,p,r} \land z\_{\ell',p',r'})$ where $p,p',r,r'$ range over all possibilities and then $\ell,\ell'$ have an appropriate relationship given $p,p',r,r'$
* For each $p$, exactly one of $z\_{\ell,p,r}$ is true (ranging over all $\ell,r$) - this is a one-out-of-$n$ constraint, which can be encoded in standard ways
* $\neg x\_\ell$, for each location $\ell$ along the four outermost edges of the grid of cells - this forces them to be on on the outside of the shape
* $\neg y\_\ell$, for each location $\ell$ along the four outermost edges of the grid of cells - this forces them to not be covered by any polyomino

Finally the goal is to find a satisfying assignment that maximizes the number of $x\_\ell$ that are true. This could be solved using ILP (each variable can be treated as a 0-or-1 integer variable, each boolean constraint can be expressed as one or more linear inequalities, and the objective function is $\sum\_\ell x\_\ell$) or using SAT (use binary search on the number of cells the region encloses, add a pseudo-boolean constraint that requires at least that many of the $x\_\ell$ are true). I don't know whether this will be efficient enough to work well in practice, but you could give it a try. That would let you benefit from all of the heuristics and algorithms that have been developed over the years for ILP and/or SAT.
> 1 votes

# Answer
In case anyone is interested, this is the solution implemented with https://github.com/afish/MilpManager

It's inspired by https://cs.stackexchange.com/a/153823/79175 (including the discussions we had in the comments). Source code:

```
var integerWidth = 15;
var epsilon = 0.001;
var storeDebugExpressions = false;
var cacheConstants = false;
var storeDebugConstraints = false;
var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
    IntegerWidth = integerWidth,
    Epsilon = epsilon,
    StoreDebugExpressions = storeDebugExpressions,
    CacheConstants = cacheConstants,
    StoreDebugConstraints = storeDebugConstraints
});
solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, 0.000000000001);

var pieces = new []{
    new []{
        "XX",
        "X ",
        "X "
    },
    new[]{
        " XX",
        "XX "
    },
    new[]{
        "XX ",
        " XX"
    },
    new[]{
        "X ",
        "XX",
        "X "
    },
    new[]{
        "XX",
        "XX"
    },
    new[]{
        "XXXX"
    },
    new[]{
        "X ",
        "X ",
        "XX"
    }
};

var totalLength = pieces.Select(p => (int)Math.Max(p.Length, p[0].Length)).Sum();
var maxLength = pieces.Max(p => (int)Math.Max(p.Length, p[0].Length));
var width = 11; // Or totalLength + 2 to make sure it's big enough for any shapes
var height = 9; // Or totalLength + 2 to make sure it's big enough for any shapes
var piecesCount = pieces.Length;
// Right, down, left, up
var directions = 4;

var heads = Enumerable.Range(0, height).Select(h =>
    Enumerable.Range(0, width).Select(w =>
        Enumerable.Range(0, piecesCount).Select(p =>
            Enumerable.Range(0, directions).Select(d =>
                solver.CreateAnonymous(Domain.BinaryInteger)
            ).ToArray()
        ).ToArray()
    ).ToArray()
).ToArray();

var isInterior = Enumerable.Range(0, height).Select(h =>
    Enumerable.Range(0, width).Select(w =>
        solver.CreateAnonymous(Domain.BinaryInteger)
    ).ToArray()
).ToArray();

var isBoundary = Enumerable.Range(0, height).Select(h =>
    Enumerable.Range(0, width).Select(w =>
        solver.CreateAnonymous(Domain.BinaryInteger)
    ).ToArray()
).ToArray();

Func<string[], int, string[]> rotatePiece = (piece, direction) => {
    if(direction == 0){
        return piece;
    }else if(direction == 2){
        return piece.Select(l => string.Join("", l.Reverse())).Reverse().ToArray();
    }else if(direction == 1){
        return Enumerable.Range(0, piece[0].Length)
            .Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[piece.Length - 1 - w][c])))
            .ToArray();
    }else {
        return Enumerable.Range(0, piece[0].Length)
            .Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[w][piece[0].Length - 1 - c])))
            .ToArray();
    }
};

// Put pieces on the board
for(int p=0;p<piecesCount;++p){
    solver.Set<Equal>(
        solver.FromConstant(1),
        solver.Operation<Addition>(
            Enumerable.Range(0, height).SelectMany(h =>
                Enumerable.Range(0, width).SelectMany(w =>
                    Enumerable.Range(0, directions).Select(d =>
                        heads[h][w][p][d]
                    )
                )
            ).ToArray()
        )
    );
}

// Make sure pieces don't fall off the board
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        for(int p=0;p<piecesCount;++p){
            for(int d = 0; d < directions;++d){
                var piece = rotatePiece(pieces[p], d);
                if(d == 0){
                    if(w + piece[0].Length - 1 >= width){
                        heads[h][w][p][d].Set<Equal>(solver.FromConstant(0));
                    }
                }else if(d == 1){
                    if(h + piece.Length - 1 >= height){
                        heads[h][w][p][d].Set<Equal>(solver.FromConstant(0));
                    }
                }else if(d == 2){
                    if(w - piece[0].Length + 1 < 0){
                        heads[h][w][p][d].Set<Equal>(solver.FromConstant(0));
                    }
                }else if(d == 3){
                    if(h - piece.Length + 1 < 0){
                        heads[h][w][p][d].Set<Equal>(solver.FromConstant(0));
                    }
                }
            }
        }
    }
}

// Set impacts
IList<Tuple<int, int, int, int>>[][] allImpacts = Enumerable.Range(0, height).Select(h =>
    Enumerable.Range(0, width).Select(w =>
        new List<Tuple<int, int, int, int>>()
    ).ToArray()
).ToArray();

for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        for(int p=0;p<piecesCount;++p){
            for(int d = 0; d < directions;++d){
                var piece = rotatePiece(pieces[p], d);
                var pieceWidth = piece[0].Length;
                var pieceHeight = piece.Length;
                for(int y=0;y<pieceHeight;++y){
                    for(int x=0;x<pieceWidth;++x){
                        var isPieceX = piece[y][x] == 'X';
                        if(!isPieceX) continue;

                        var finalY = d == 0 || d == 1 ? h + y : y - pieceHeight + 1 + y;
                        var finalX = d == 0 || d == 1 ? w + x : x - pieceWidth + 1 + x;

                        if(finalY >= 0 && finalY < height && finalX >=0 && finalX < width){
                            allImpacts[finalY][finalX].Add(Tuple.Create(h, w, p, d));
                        }
                    }
                }
            }
        }
    }
}

// Set the boundary
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        isBoundary[h][w].Set<Equal>(
            solver.Operation<Addition>(
                allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
            )
        );
    }
}

// Make sure pieces do not overlap
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        solver.Set<LessOrEqual>(
            solver.Operation<Addition>(
                allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
            ),
            solver.FromConstant(1)
        );
    }
}

// Extend interior
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        for(int y=-1;y<=1;++y){
            for(int x=-1;x<=1;++x){
                if(y == 0 && x == 0){
                    continue;
                }

                if(h + y < 0 || h + y >= height){
                    continue;
                }

                if(w + x < 0 || w + x >= width){
                    continue;
                }

                solver.Set<Equal>(
                    solver.FromConstant(1),
                    solver.Operation<MaterialImplication>(
                        solver.Operation<Conjunction>(
                            isInterior[h][w],
                            isBoundary[h + y][w + x].Operation<BinaryNegation>()
                        ),
                        isInterior[h + y][w + x]
                    )
                );
            }
        }
    }
}

// Make sure there is some exterior
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        if(h == 0 || h == height - 1 || w == 0 || w == width - 1){
            solver.Set<Equal>(
                solver.FromConstant(0),
                isInterior[h][w]
            );
            solver.Set<Equal>(
                solver.FromConstant(0),
                isBoundary[h][w]
            );
        }
    }
}

// Make sure a field cannot be both exterior and boundary
for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        solver.Set<LessOrEqual>(
            solver.Operation<Addition>(
                isInterior[h][w],
                isBoundary[h][w]
            ),
            solver.FromConstant(1)
        );
    }
}

var goal = solver.Operation<Addition>(isInterior.SelectMany(x => x).ToArray());
solver.AddGoal("goal", goal);
solver.Solve();

Console.WriteLine(solver.GetValue(goal));

var board = Enumerable.Range(0, height).Select(h => new String(' ', width).ToCharArray()).ToArray();

for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        for(int p=0;p<piecesCount;++p){
            for(int d = 0; d < directions;++d){
                var piece = rotatePiece(pieces[p], d);
                var pieceWidth = piece[0].Length;
                var pieceHeight = piece.Length;
                if(solver.GetValue(heads[h][w][p][d]) > 0.5){
                    for(int y=0;y<pieceHeight;++y){
                        for(int x=0;x<pieceWidth;++x){
                            var finalY = d == 0 || d == 1 ? h + y : y - pieceHeight + 1 + y;
                            var finalX = d == 0 || d == 1 ? w + x : x - pieceWidth + 1 + x;

                            if(finalY >= 0 && finalY < height && finalX >=0 && finalX < width){
                                board[finalY][finalX] = piece[y][x];
                            }else {
                                Console.WriteLine("Error in " + h + " " + w + " " + p  + " " + d  + " " + y + " " + x);
                            }
                        }
                    }
                }
            }
        }
    }
}

foreach(var l in board){
    Console.WriteLine(string.Join("", l));
}
Console.WriteLine();

for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        Console.Write(Math.Round(solver.GetValue(isInterior[h][w])));
    }
    Console.WriteLine();
}
Console.WriteLine();

for(int h = 0; h < height; ++h){
    for(int w = 0; w < width; ++ w){
        Console.Write(Math.Round(solver.GetValue(isBoundary[h][w])));
    }
    Console.WriteLine();
}
Console.WriteLine();

```

It should generalize to any polyominoes you have (just replace the array at the beginning). This can be easily translated to SAT if you need, so you have plenty of solvers out there to play with it.

CPLEX output for the sample above:

```
Tried aggregator 2 times.
MIP Presolve eliminated 4659 rows and 4747 columns.
MIP Presolve modified 688 coefficients.
Aggregator did 1432 substitutions.
Reduced MIP has 809 rows, 847 columns, and 4647 nonzeros.
Reduced MIP has 847 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (10.92 ticks)
Found incumbent of value 0.000000 after 0.06 sec. (33.44 ticks)
Probing time = 0.00 sec. (2.70 ticks)
Tried aggregator 1 time.
Reduced MIP has 809 rows, 847 columns, and 4647 nonzeros.
Reduced MIP has 847 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (2.75 ticks)
Probing time = 0.02 sec. (2.69 ticks)
Clique table members: 1918.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.02 sec. (17.35 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                            0.0000       35.0000      565     ---
      0     0       29.7678   243        0.0000       29.7678      565     ---
*     0+    0                            2.0000       29.7678      657     ---
      0     0       29.2337   242        2.0000      Cuts: 36      657     ---
*     0+    0                            3.0000       29.2337      657  874.46%
      0     0       28.7133   242        3.0000      Cuts: 99      816  857.11%
      0     0       28.5944   248        3.0000      Cuts: 26      881  853.15%
      0     0       28.3575   243        3.0000      Cuts: 21      958  845.25%
      0     0       28.1942   256        3.0000      Cuts: 27     1036  839.81%
      0     0       28.1076   244        3.0000      Cuts: 25     1120  836.92%
*     0+    0                            4.0000       28.1076     1120  602.69%
      0     0       28.1076   245        4.0000      Cuts: 12     1130  602.69%
      0     0       28.0851   255        4.0000       Cuts: 9     1150  597.76%
      0     0       27.9794   239        4.0000      Cuts: 28     1229  597.76%
      0     0       27.8878   280        4.0000      Cuts: 25     1330  597.20%
      0     0       27.8093   275        4.0000      Cuts: 23     1402  595.23%
      0     0       27.6921   275        4.0000      Cuts: 40     1520  592.30%
      0     0       27.6921   276        4.0000       Cuts: 7     1525  592.30%
*     0+    0                           20.0000       27.6921     1525   38.46%
      0     2       27.6921   276       20.0000       27.6060     1525   38.03%
Elapsed time = 0.97 sec. (335.52 ticks, tree = 0.01 MB, solutions = 5)
*     5+    5                           21.0000       27.5336     1944   31.11%
*    56    40      integral     0       22.0000       27.4817     5646   24.92%
*    63+   38                           25.0000       27.4817     5959    9.93%

Clique cuts applied:  15
Cover cuts applied:  19
Implied bound cuts applied:  63
Mixed integer rounding cuts applied:  35
Zero-half cuts applied:  53
Gomory fractional cuts applied:  1

Root node processing (before b&c):
  Real time             =    0.97 sec. (335.26 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.52 sec. (250.13 ticks)
  Sync time (average)   =    0.26 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    1.49 sec. (585.39 ticks)
25

   XXXXXX
  XX    X
 XX     X
 X      XX
 X      X
 XX    XX
  XXXXXXX

00000000000
00000000000
00001111000
00011111000
00111111000
00111111000
00011110000
00000000000
00000000000

00000000000
00011111100
00110000100
01100000100
01000000110
01000000100
01100001100
00111111100
00000000000

```
> 2 votes

---
Tags: algorithms, optimization, linear-programming, square-grid, tiling
---


# Question
Title: Comparing source code and compiled code for ("topological") equivalence
Assume that I have a program `Login.c` that I have compiled with `cc` and generated the executable `a.out`. Now, along the questions posed from "Reflections of Trusting Trust", I want to check that `a.out` is the intended executable and nothing else, e.g. that there is no malfunction injected by the build system. There are techniques such as diverse double-compiling and reproducible builds that I can utilize. However, I see in several texts that say "

comparing source code and compiled code for equivalence is an undeciable problem

and, similarly, "This is an undecidable problem in general" but: Where is the reference or proof that this problem is undecidable?

# Answer
> 1 votes
"Comparing source code and compiled code for equivalence is an undecidable problem". What does that statement mean?

It means there is no algorithm that, given arbitrary (source) code in programming language $A$ and arbitrary (compiled) code in another programming language $B$, can decide whether both code always behave the same if given the same input. Here we assume both programming languages are arbitrarily fixed and Turing-complete. "behave the same" means either both loop forever or both return the same string.

---

Here is a simple proof.

Suppose there is such an algorithm $M$. Let us solve the halting problem in language $A$ using $M$.

Let $S\_A$ be some arbitrary source code in $A$ and $w$ be some arbitrary string.

Since $B$ is Turing complete, we can write $S\_B$, a program in $B$ that behaves the same as $S\_A$.

Write code $S'\_B$ in language $B$ so that it is the same as $S\_B$ except when it halts. At the time when it halts before returning the result, it will check whether the given input is $w$ first. If it is, $S'\_B$ will loop forever. Otherwise, it will return the result as usual. That is, $S'\_B$ is the same as $S\_B$ except possibly that $S'\_B$ always loop forever if the input is $w$.

Now we use $M$ to check whether $S\_A$ and $S'\_B$ always behave the same if given the same input.

If $M$'s verdict is yes, then $S\_A$ on $w$ does not halt. Otherwise, $S\_A$ on $w$ halts. We have solved the halting problem in language $A$.

However, it is known that the halting problem in a Turing-complete language is undecidable. This contradiction implies that $M$ does not exist.

---

In fact, any nontrivial behavior property of a program in a Turing-complete language is undecidable. That is Rice's theorem.

What are the nontrivial behavior properties?

A property of a program is a behavior property if for any two programs that behaves the same, either both has that property or neither does.

A behavior property is nontrivial if at least one program has it while at least one program does not.

Here are some nontrivial behavior properties.
Will the program output "Niklas" if it runs without any input?
Is there an input that the program does not return the string as specified in a specification?
Will the program make a internet connection, assuming the program is allowed to?

---
Tags: undecidability, compilers, security
---


title: Extended transition function in NFA

text:
# Question
Title: Extended transition function in NFA
The following statement seems trivial, but how can it be formally proven/argued?

$$\bigcup\_{s \in \delta\_{N}^{\*}\left(q\_{0}, w\right)} \delta\_{N}^{\*}(s, a) \\;\equiv\\; \delta\_{N}^{\*}\left(q\_{0}, w a\right)$$

In words: taking the union of the states when reading a symbol ‘a’ from all the possible states in a NFA having read the string ‘w’ from the start state, is the same as taking all the possible states we can get after reading the string ‘wa’ from the start state of the NFA.

# Answer
> 1 votes
You can show that all states in the set on the left hand side are included in the set on the right hand side, and vice-versa.

$s \in \delta\_N^\*(q, w)$ if and only if there is some path $\pi(q,s,w)$ from state $q$ to state $s$ in $N$ such that the concatenation of the edge labels (which might be $\varepsilon$) is equal to $w$.

If $q$ is in the left hand union then there is some state $s \in \delta^\*\_N(q\_0, w)$ such that $q \in \delta^\*\_N(s,a)$. Then $\pi(q\_0,s,w) \circ \pi(s,q,a)$ is a path from $q\_0$ to $q$ that matches $wa$, showing that $q \in \delta^\*\_N(q\_0, wa)$.

On the other hand, if $q \in \delta^\*\_N(q\_0, wa)$, let $s$ be the last occurrence of a state in $\pi(q\_0, q, wa)$ such that the edge leaving $s$ is labelled $a$. The subpath of $\pi(q\_0, q, wa)$ from $q\_0$ to $s$ is such that the concatenation of its edge labels equals $w$. This shows that $s \in \delta^\*\_N(q\_0, w)$. Moreover the subpath of $\pi(q\_0, q, wa)$ from $s$ to $q$ is such that the concatenation of its edge labels equals $a$. This shows that $q \in \delta^\*\_N(s, a)$. Therefore $q$ belongs to the union in the left hand side.

---
Tags: formal-languages, regular-languages, finite-automata, transition-systems
---


# Question
Title: Is it computable to find the cardinality of intersection of two recursively enumerable sets?
I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is computable/decidable?

That is, given two recursively enumerable sets $A$, $B$, is $|A \cap B|$ always decidable/computable (provided we know what $|A|$ and $|B|$ are, even if they are infinite)?

My first hunch is that this is equivalent to the halting problem for Turing Machines, but how would I show this?

# Answer
> 1 votes
Interesting question.

Claim: A finite recursively-enumerable set is decidable.
Proof: In fact, a finite set is decidable.

Claim: It is computable to find $|A\cap B|$ given two finite sets $A$ and $B$.
Proof: List all elements in $A$. For each one of them, check whether it is in $B$. Return the number of all elements that are found in $B$.

Claim: It is not computable to find $|A\cap B|$ given two recursively-enumerable sets $A$ and $B$ such that $|A|$ is finite and $|B|$ is infinite.
Proof: For the sake of contradiction suppose algorithm $M$ finds $|A\cap B|$ given such $A$ and $B$. Let us solve the halting problem, as you expected.
Let $X$ be an arbitrary Turing machine and $w$ be an arbitrary input.
Let $M\_1$ be a Turing machine that halts only when the input is $w$. Let $M\_\infty$ be a Turing machine that always halts except when the input is $w$, at which time $X$ behaves the same as $X$ upon input $w$. Note that $|L(M\_1)|=1$ is finite and $|L(M\_\infty)|$ is infinite.
Apply $M$ to $L(M\_1)$ and $L(M\_\infty)$. If $|L(M\_1)\cap L(M\infty)|=1$, then $X$ halts upon $w$. Otherwise, $|L(M\_1)\cap L(M\_\infty)|=0$, and $X$ loops forever upon $w$. $\quad\checkmark$

Corollary: It is not computable to find $|A\cap B|$ given two recursively-enumerable sets $A$ and $B$ with known cardinalities.

---
Tags: computability, undecidability, decidability
---


title: How to deal with a very big hash table?

text:
# Question
Title: How to deal with a very big hash table?
I'm building an implementation of the dynamo paper, yottastore. Given a key, I need to find which NVMe block stores the data. To do that I hash the key to find the shard where I have an in memory array in which at position \[hash\] I can find a struct with:

* 32 bit hash (needed for resizing)
* 64 bit pointer to NVMe block
* 32 bit of metadata

The random storage node is: 48 core cpu, 1 tb ram, 24\*16 tb SSD

At 128 bit per key-value, it's 64 GB of ram per 16 TB disk, or 1.5 TB of ram in total, way too much.

How could I deal with this?

Options I envisioned:

* Using a btree, but it will make access much slower, and I still have 96 bit of records to deal with
* Pointer compression: I could divide the disks in zones of 256 mb, so for each record I will only need a 16 bit offsets instead of 64 bits. I would also need to store a a 64 bit start for each zone in a separate hash table
* I could mix the approaches, storing a btree to find the zone, and then having an hashmap with offsets

Any other ideas? The array already persists on disk with a LSM tree, I would like to have an in memory copy for fast access.

# Answer
> 2 votes
I am not familiar with yottastore or how NVMEs work. However, let's assume the following (correct me if I am wrong):

You have:

* 64 bit pointer
* 32 bit of metadata

You don't need the hash, I assume, that was only part of your proposed solution?

Instead of a normal btree you could use a critbit tree.

Critbit trees are like btree but the key (= 64bit pointer) is not stored in full. Instead, for all entries whose keys share a common prefix, this prefix is stored only once in memory. E.g. with 8 bit keys, k1=0100010 and k2 = 01000100 there would be one node that stores the common 5 bit prefix 01000 and that has two children k1=010 and k2=100. That way you store only 5 + 2x3 = 11 bits instead of 2x8=16.

As a result you have to store probably only 16-32 bit per pointer + 32bit metadata.

Another big advantage is that you never need rehashing or rebalancing of any sort, that means lookup times and insert/delete times are very predictable. Concurrency can be implemented with a copy-on-write scheme that copyies only one node.

**Variant: \>2 children per node** I think a classic critbit tree has only two children per node. As an optimization (faster & less memory overhead) you can try to split with 2 or more bits per node, i.e. 4 children (or 8 children for 3 bits).

**Variant: Prefix sharing btree** Just like a normal btree with "n" entries per (leaf) node, but for each leaf node you determine the longest common prefix dynamically and store the for each entry only a 32bit or 16bit value (assuming that all entries in a node typically have a common 32bit or 48bit prefix).

I have an critbit implementation in Java available here.

# Answer
> 1 votes
For each 16 TB ssd, you have 40 GB of RAM. I don't know the prices of server-grade hardware, but with consumer-grade one, 40 GB RAM is about \\$100, while 16 TB SSD is about \\$1000.

Maybe you just need to make a more balanced system instead of spending money on developers in order to make a small economy on hardware?

---
Tags: trees, hash-tables
---


# Question
Title: Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))
How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?

# Answer
> 2 votes
The result is false. For example, consider the following functions:

* $f(n) = \left\\{\begin{array}{ll}n&\text{if }n\text{ is even}\\ n^2&\text{otherwise}\end{array}\right.$;
* $g(n) = n^2$.

Then $f \in \mathcal{O}(g)$ and $f\notin \Theta(g)$, but $f\notin o(g)$ either.

---
Tags: complexity-theory, asymptotics, big-o-notation
---


title: Proof sketch of Blum's Speedup Theorem

text:
# Question
Title: Proof sketch of Blum's Speedup Theorem
In his Quantum Computing Since Democritus, Scott Aaronson outlined a proof sketch of Blum's Speedup Theorem which roughly looks like the following.

Given an enumeration of Turing Machines $\\{M\\}\_{i \in \mathbb{N}}$. Let $S\_i = \\{M\_1, ..., M\_i\\}$. We can construct a computable function $f(n)$ such that if $f(n)$ can be computed in $O(2^n)$ steps then it can also be computed in $O(2^{n-1})$ in the following manner (Python pseudocode):

```
canceled = set()
for i in range(n):
    for Mj in Si:
        if Mj not in canceled and Mj halts in 2 ** (n-i) steps:
            f(i) = 1 - output of Mj
        canceled.add(Mj)
        break
     f(i) = 0
return f(n)

```

Aaronson claims we can "hardwire" the canceled Turing Machines from iteration 1 to i and skip to iteration i+1. The complexity goes from $O(n^2 2^n)$ to $O(n^2 2^{n-i})$.

Why is this a valid argument? Wouldn't a similar argument "we can cache all the results" turn every computable function into $O(1)$?

Reference: https://www.scottaaronson.com/democritus/lec5.html

# Answer
You cannot "cache all the results" because your program (or description of Turing machine) would need to be infinite. You can only cache a fixed number of results. In your example $i$ needs to be fixed. You cannot pick, e.g., $i=\frac{n}{2}$ and lower the complexity from $O(n^2 2^n)$ to $O(n^2 2^{n/2})$.

On an unrelated note $O(2^n)$ and $O(2^{n-1})$ are exactly the same set of functions so it is trivially true that a function that can be computed in time $O(2^n)$ can also be computed in time $O(2^{n-1})$ (or in time $O(2^{n-i})$ for any constant $i$).

The claim in the linked notes is stronger as it work for any complexity bound $t$. You need to pick a $t$ that grows quick enough to get something useful. In the notes $t$ is defined recursively as $t(n)= 2^{t(n-1)}$ which (assuming $t(0)=0$) corresponds to the power tower function that grows as $1, 2, 2^2,2^{2^2}, 2^{2^{2^2}}$, etc.
> 2 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Are there algorithms that can find the most repeated values in a very large array in a millisecond?
As the title says, I've developed my own algorithm that can do so, however mine would take 1-2 seconds searching through an array with 1 million length, however I am very curious if this can be made so much faster like 0.01s or even 0.001 is this mathematically impossible? I've used C++ with vectors and jsons to create mine, were these the right way to build such algorithms? or are there algorithms already out there?

Also there is a limit on how many values there would be, for my example I've calculated there would be atleast 100k-1M unique values in a single array with a length of 1 million. I've also tried threading but since you have to sync the variables you need to count the repetitions I find this not a "good" way of implementing things

# Answer
> 3 votes
If you can define by yourself what “most repeated” values means, then you can use the Space Saving algorithm. See the paper available here for the details.

The Space Saving algorithm allows you to determine all of the frequent items, also known as heavy hitters, without incurring in false negative (i.e. it’s recall is always equal to 1); however, there can be false positives (it’s precision may not be necessarily 1, but it is usually quite close to 1).

In this context, letting $n$ be the length of your dataset, frequent items are defined by a threshold $0 \< \phi \< 1$ so that an item is frequent if it appears in your dataset at least $\phi n$ times.

You can find C/C++ implementations which implement correctly the summary data structure (i.e. they are capable of processing in constant time an item when the item must be inserted into the summary: the implementation is really tricky when done correctly, since it requires, along with other things, to determine the minimum of $k$ counters in constant time; here $k$ is the size of the summary, its number of counters. It’s easy of course to implement the algorithm so that finding the minimum is done in $O(k)$, but the algorithm is fast only if the summary data structure is implemented correctly as described in the paper) and are fast enough to process tens of millions of items per second.

# Answer
> 1 votes
One approach is to sort the list, which brings duplicated together. Then you can count the number of duplicates of each item with a simple linear scan. Good sorting algorithms should be extremely fast.

Another approach is to use a hashtable: store each item in a hashtable, along with a count, and when you see an item that you've already seen before, increment the count. Then a linear scan through the hashtable suffices to find the item whose count is the largest.

# Answer
> 1 votes
Milliseconds for a million elements means nanoseconds per elements. One nanosecond may be half a dozen instructions. That’s difficult. Let’s set a goal of few (less than ten) milliseconds.

For a generic algorithm that handles all kind of data this is tough. But let’s say your million numbers were picked at random from 0 to M-1, with M = ten million or 50 million, “at random” means some numbers but not many turn up repeatedly.

We create a bitset with M elements, then process the numbers in sequence. If a number X is not in the bit set, then we set bit X. With M = 10 million that’s what happens in 90% of all cases. If X is already set, then we do two things: We add X to a hash set if not present yet, and either initialise a counter to 2 if X wasn’t present, or increase the counter. We also maintain an array that tells us how often each count \>= 2 happened.

This is all more time consuming than just checking and setting one bit, but is much more rare, so instead of nanoseconds we can spend tens of nanoseconds.

After processing all numbers, we determine how many numbers with “largest count” we want and extract them.

If we have more than say 200 million numbers, we set a bit for x % 100,000,000 do only one in 100 would get a count of 2. If M is smaller, the number of different X occurring twice or more often will still be much less than a million.

So the idea is to remove numbers occurring 0 or 1 times very quickly, and hoping the number of duplicates is much less (it’s less than 500,000 in the worst case, but likely less).

---
Tags: algorithms
---


# Question
Title: Shamos algorithm , cannot understand the Area part
I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia:

```
GetAllAntiPodalPairs(p[1..n])
    i0 = n
    i = 1
    j = i + 1
    while (Area(i, i + 1, j + 1) > Area(i, i + 1, j))
        j = j + 1
        j0 = j
    while (j != i0)
        i = i + 1
        yield i, j
        while (Area(i, i + 1, j + 1) > Area(i, i + 1, j)
            j = j + 1
            if ((i, j) != (j0, i0))
                yield i, j
            else
                return
        if (Area(j, i + 1, j + 1) = Area(i, i + 1, j))
            if ((i, j) != (j0, i0))
                yield i, j + 1
            else
                yield i + 1, j

```

And this is a gif to visualize the algorithm:

I cannot understand the **Area** in the code . how it will be calculated given i , i+1 and j+1? And what's exactly the p\[1..n\] ? Is it the given points or that's different? I've created a shape for solving that using this algorithm.I know that's not easy but can someone trace the algorithm for this shape? Anybody like me will enjoy it:

# Answer
Notice that *for a fixed side*, the distances to the vertices are a multiple of the area formed by the side and the vertices. So comparing the areas is in fact a means to compare the distances.

In the figure, you see all antipodal pairs. You can obtain them efficiently by following the polygon edges in clockwise order, every time finding the opposite-most vertex by revolving clockwise and comparing the distances (this is what guarantees linear time complexity).

The opposite corner advances as many times as there are vertices (because it follows the polygon), at the expense of one extra test per side, to detect when the distance decreases.
> 1 votes

---
Tags: algorithms, algorithm-analysis, convex-hull
---


# Question
Title: Select signals for memory mapped into common address space
I just got a hobby of studying this topic and it is quite intriguing. In one of the books, I came up with the following question:

> A computing hardware is to be designed with a processor generating 32bit address for memory. It requires 2GB of RAM, 128MB of EPROM and 1MB of EEPROM, and these are mapped in the memory address space as follows.
>
> EEPROM: 0 to (1M–1) EPROM: 128M to (256M–1) RAM: 2G to (4G–1).
>
> Write the Boolean expressions for the signals EEPROM Select, EPROM Select, RAM Select.

I couldn't find any solution to this and there is hardly any resource on the internet too.

So can anyone explain me, how we write the Boolean expression for such questions? I am aware of boolean logic to logic gates, but I am unable to make anything out of this question.

# Answer
Let's call the memory address $x$. Thus $x$ is composed of bits $x\_0,\ldots,x\_{31}$, where $x\_0$ is the LSB and $x\_{31}$ is the MSB.

A memory address belongs to the EEPROM mapped area if it is in the range $0,\ldots,2^{20}-1$. You can check that this is equivalent to the condition $x\_{20} = \cdots = x\_{31} = 0$, which you can translate into a Boolean expression for "EEPROM Select".

The other signals can be handled similarly.
> 0 votes

# Answer
In binary, the EEPROM addresses are

```
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000010
...
00000000 00001111 11111111 11111110
00000000 00001111 11111111 11111111

```

What is common to all ?
> 0 votes

---
Tags: memory-access
---


# Question
Title: What is the difference between directed graph and bidirectional graph?
Is the graph above bidirectional? The image in wikipedia confused me a lot, before I heard about something called as bidirectional graph, I would say the above one a directed graph, but I am not sure now.

# Answer
As stated in the Wikipedia article, a bidirected graph is a graph where all edges have an orientation at both edges of the edge. The orientation is an arrow head. So in your example, it is not a bidirected graph because the edges only have orientation on one end.

The following would be an example of a bidirected graph. Notice there is an arrow head on both sides of each edge of the graph.

There are three types of edges of a bidirected graph.

1. Extroverted edge: arrow heads oriented outwards or towards vertices (e.g. $\\{a,b\\}$)
2. Introvert edge: arrow heads oriented inwards or away from vertices (e.g. $\\{b,c\\}$)
3. Directed edge: arrow heads oriented in one direction or away from one vertex and towards the other (e.g. $\\{a,c\\}$)

There are also loose edges (which have no orientation on either end) and half edges (which have orientation on one end).

Another use of bidirected graph is a directed graph where each edge has a matching edge going the opposite direction. Your example would not be a bidirected graph in this context either since there are edges that do not have the reverse direction (e.g. $(1,3)$ exists but $(3,1)$ does not). The following is an example of bidirected graph in this context.

Bidirected graphs are not common in my experience. This is just from a quick read of the Wiki article.

1. Bidirected graphs: https://en.wikipedia.org/wiki/Bidirected\_graph
2. Directed graphs: https://en.wikipedia.org/wiki/Directed\_graph
> 4 votes

# Answer
I would suggest you look at the wikipedia article for bidirected graphs. It states that directed graphs is a special kind of bidirected graph. There are introverted edges, extraverted edges, and directed. They aren’t different but one is a subset of the other.
> 0 votes

# Answer
You can think of a directed edge as a one way street while a uni/bi directed is a 2 way street. A uni/bi directed graph is basically a graph with only two way streets while a directed graph can have one way streets too.
> 0 votes

# Answer
there are some mathematic concepts i think may useful for you. first, the picture you show above is a directed graph. the difference between bidirected graph and directed graph is that each node in bidirected graph have two side: VdX{left,right}, and each edge on bidirected graph is pair of two side, and every endpoint the edge will have information about which side of the node it connected to.

picture A is a directed graph. each edge only have one direction. picture B is a bidirected graph, each endpoint of edge is connected to a specific side of node. reference doi: 10.1089/cmb.2017.0251
> 0 votes

# Answer
Arrows are there to indicate which is the traversal direction. \[Directed\]

No arrows implicitly mean that both directions can be taken. \[Bidirectional or undirected\]

IMO, a graph where every arrow has the reverse counterpart could be considered both as a directed or undirected graph (depending on context).
> 0 votes

---
Tags: graphs, data-structures
---


# Question
Title: Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?
i have seen this question where someone was asking if $\\{a,b,c\\}^\* \setminus \\{a^nb^mc^k \mid n \leq m \leq k\\}$ is context free.

Then there was an answer that says that it is context free because:

The language, in turn, is context-free. This is because we can write it as a union of context-free languages:

* Words not of the form $a^\*c^\*b^\*$
* Words of the form $a^nb^mc^k$ where \>
* Words of the form $a^nb^mc^k$ where \>.

So my question is, why can't i take the language $\\{a^nb^nc^k | n \> m \> k\\}$?

Isn't that also the complement of the language?

If so, that would be pumpable with the word z = $a^{n+2}b^{n+1}c^n$ right?

I am a little bit confused and feel like i missed something.

# Answer
No. $\\{a^nb^mc^k\mid n\>m\>k\\}$ is not the complement of $\\{a^nb^mc^k\mid n\le m\le k\\}$, for two reasons.

(1) The negation of the logical statement "$P\land Q$" is not "$\lnot P\land \lnot Q$", it is "$\lnot P\lor \lnot Q$".

(2) The original language consists of only strings in the language $a^\*b^\*c^\*$, so the complement must include all strings where the order of symbols is not alphabetical.

As a consequence the complement of "$n\le m\le k$" is then the union of three languages "$n\>m$", "$m\>k$", "not alphabetical", each of which is context-free. Occasionally the "not alphabetical" part $\\{a,b,c\\}^\*\setminus a^\*b^\*c^\*$ is overlooked, but as that is a regular language it is the least problematic part.
> 1 votes

# Answer
You ask:

```
Isn't that also the complement of the language?

```

Here *that* refers to $L' = \\{a^n b^m c^k \mid n \> m \> k\\}$ but I'm not sure what *the language* refers to. It could be $L=\\{a^n b^m c^k \mid n \le m \le k\\}$ or $L'' = \\{a,b,c\\}^\* \setminus L$. In any case:

* $L'$ is not the complement of $L$. As (one of the many possible choices for a) witness, notice that $b$ belongs to neither $L$ nor $L'$.
* $L'$ is not the complement of $L''$. A witness is $aab$ since it belongs to both $L'$ and $L''$.
> 1 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: How to recognize all halting states of a turing machine?
Given a turing machine with some states, how can I recognize all halting states of that machine?

I think that I should go over each state and check if there is a transition that is not defined for that state with one (or more) of the tape alphabet symbols (also containing the blank symbol).

Would this be a good approach?

# Answer
> 2 votes
A turing machine is defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q\_0, F \rangle$. The set $F$ in the tuple is the set of *final states* or accepting states. So any other states other than the ones in $F$ are the rejecting states. You can consider the language that $M$ covers as $L$. So $L'$ will be the language (set of phrases) that $M$ never accepts. If you create another Turing machine $M'$ for $L'$, then the set of *final states* for $M'$ in combination with $F$ is the answer you are looking for.

But determining whether or not your Turing machine *ever reaches* these states is another question overall. It is generally impossible to know whether or not a Turing machine will halt beforehand. So if you could count the number of ways that a Turing machine *will* halt (not *could* halt), you are basically raising a serious contradiction with the halting problem.

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: What is the advantage of this checksum method in NHS numbers?
All British citizens are provided with a National Health Service (NHS) number either at birth or when they first register with an NHS doctor. According to the NHS Number wikipedia page, the 10 digit number contains a checksum digit, which is calculated using the following algorithm:

> The current system uses a ten-digit number in '3 3 4' format with the final digit being an error-detecting checksum. Examples given include 987 654 4321.\[4\]

> The checksum is calculated by multiplying each of the first nine digits by 11 minus its position. Using the number 943 476 5919 as an example:

> The first digit is 9. This is multiplied by 10.

> The second digit is 4. This is multiplied by 9.

> And so on until the ninth digit (1) is multiplied by 2.

> The result of this calculation is summed. In this example: \>9*10+4*9+3*8+4*7+7*6+6*5+5*4+9*3+1\*2 = 299.

> The remainder when dividing this number by 11 is calculated, yielding a number in the range 0–10, which would be 2 in this case.

> Finally, this number is subtracted from 11 to give the checksum in the range 1–11, in this case 9, which becomes the last digit of the NHS number.

> A checksum of 11 is represented by 0 in the final NHS number. If the checksum is 10 then the number is not valid.

This seems to be a rather complicated method of acquiring a checksum, so my question is: what is the advantage of using this particular checksum method for these numbers?

# Answer
> 4 votes
The general purpose of checksums is to allow errors in transcription to be detected by means of a simple algorithm applied to the number itself, and without access to any other information (such as access to central records).

Error-detection methods require a certain amount of redundancy in the data, and there is generally a desire to economise on the amount of redundancy, because handling additional data increases the clerical workload, and increases the very risk of transcription errors whose occurrence you are trying to detect and prevent. You wouldn't want to double the number of digits, for example, as the price of including a checksum.

Therefore, most checksums are tailored to detecting certain kinds of the most common transcription errors whilst introducing the smallest possible amount of redundancy into the data.

If I remember correctly, the most common transcription error is getting a single digit in a single position wrong, followed in second place by the swapping of two adjacent digits (i.e. getting two digits in two positions wrong, but in a specific pattern).

Many trivial algorithms can detect the first kind of error - the change of one digit in one place. The most trivial is just adding up all the digits - hence the name, "checksum".

But the algorithm you describe is specifically designed to detect the second kind of error *as well as the first*, and without introducing any extra checksum digits.

The general tradeoff with complicated algorithms is that more-commonly-encountered kinds of error are detected, at the expense of the algorithm detecting fewer more-rarely-encourered kinds of error. But more complicated algorithms therefore detect more errors overall, because they are better at detecting the errors that clerks frequently make, and the errors they cannot detect are errors of the kind that clerks rarely make anyway.

A particular feature of the algorithm you describe is that when applied to any possible input number, it produces a result between 0 and 10 for the checksum, the last of which requires two digits to represent (in decimal numbers, which run 0-9).

Since it is undesirable to introduce additional digits, and because the designers probably didn't want to introduce an alphanumeric aspect (such as how hexadecimal numbers are represented by 0-9 then A-F, or how the ISBN checksum scheme represents 10 using the letter 'X', which corresponds to the Roman numeral for 10), they simply don't allocate base numbers which cause a checksum of 10.

Because no valid base number then has a checksum of 10, any calculated checksum of 10 always indicates a transcription error.

As to why they chose to disallow a checksum of 10 specifically (when they could have chosen any in the range 1 to 11), I cannot say offhand, but there is almost certainly some additional statistical or computational rationale, that either makes the algorithm more straightforward to apply (by hand or by computer), or which maximises the overall number of transcription errors detected.

# Answer
> 2 votes
This is the same idea that is in the Varshamov-Tenengolts code with some modifications as explained in the answer above by @Steve.

Since $p=11$ is prime, the set of integers modulo 11, denoted $GF(11),$ is a field (nonzero elements are invertible, you have distributive law, etc). If we have a parity check of the form $$ C=\sum\_{k=1}^n k x\_k \pmod{11} $$ or its negative (we are subtracting from 11 which is taking a negative in the field $GF(11)$ which is the case here: $$ C=-\sum\_{k=1}^n k x\_k \pmod{11} $$ One can observe the digits and re-compute the parity check digit. This would be $C\_{correct}$ and is equal to $C\_{printed} if there are no errors.

If there is a symbol error printed in position $k,$ we can recalculate what the check should be, and solve $$ C\_{printed}-C\_{correct} = k \delta \pmod{11} $$ uniquely for $k$ and $\delta$ since a linear map $$ k\mapsto k \delta $$ is a permutation in $GF(11)$ (It is one to one and hence invertible). If the digit in location $k$ did not get printed, then you know $k$ and you can solve and get the correct digit by the same method.

---
Tags: algorithms
---


# Question
Title: Free description of the Kameda-Weiner algorithm?
I found the paper "On the State Minimization of Nondeterministic Finite Automata" which, I assume, contains the Kameda-Weiner algorithm that I've been searching for. It's behind a paywall though. I'm just a hobbyist. Can someone explain it, or point me to another source?

# Answer
> 1 votes
I've implemented it here: https://github.com/coder0xff/parlex\_legacy/blob/132e4a23a599140d22b18ead832626f0c607340f/Automata/NFA.cs#L641

I've never gotten around to describing it, but to be brief, it's very involved. The only way to gain a useful understanding of the algorithm is to read the paper start to finish.

# Answer
> 2 votes
Brzozowski's paper on arXiv might have a full account of the algorithm. He's one of the pioneers in what I've termed the "algebraic approach" for formal language and automata theory - best known for invoking the "Brzozowski derivative" (aka left-quotient) to describe the state transition of a regular language in algebraic terms. It's the same operation that we used in producing a dramatically simpler proof of Parikh's theorem in 1999. For commutative Kleene algebras, the operator actually *is* a derivative operator complete with its own version of Taylor's Theorem.

In the paper, https://arxiv.org/abs/1301.5585, Brzozowski brings the derivative/quotient infrastructure to bear; but from a casual reading of the paper, I can't tell if he's described the Kameda-Weiner method in full generality or not.

# Answer
> 2 votes
Here is a succinct but somewhat abstract description of the technique based on \[1\]. Also reading \[2\] to understand the universal automaton before approaching this description is recommended.

I am also assuming that you are familiar with quotients and some basic properties of them (e.g, Myhill-Nerode Theorem). These topics can be found in an (slightly less) introductory book on automata theory.

Alternately, you can look at link for paper \[3\] (accessible for free)

---

Let $L \subseteq \Sigma^\*$. If $L$ is regular, one can find finitely many words $U = \\{ u\_1, u\_2, \cdots u\_n \\}$ such that (1) each quotient $u\_i^{-1}L$ is distinct from $u\_j^{-1}L$ and (2) for all $w \in \Sigma^\*$, there exists some $i$ such that $w^{-1}L = u\_i^{-1}L$.

Similarly, there are words $V = \\{v\_1, v\_2, \cdots v\_m\\}$ such that similar conditions are true for the right quotients $Lv\_i^{-1}$.

A factorization of $L$ is a pair $(X, Y)$ (where $X$ is the left factor and $Y$ is the right factor) such that $XY \subseteq L$ which is maximal, i.e, there does not exist $(X', Y')$ satisfying the same property such that $X \subset X'$, $Y \subset Y'$ (with strict containments).

Observe that the left factor of a factorization determines the right factor uniquely and vice-versa. Furthermore, note that any interesection of left quotients is a right factor and any intersection of right quotients is a left factor. This is, in fact, a characterization of left (resp, right) factors, in the sense that any left (resp, right) factor is an intersection of right (resp., left) quotients.

It follows that there are finitely many factorizations of a regular language $L$. Further, any right (resp., left) factor can be described using a subset of $U$ (resp., $V$).

Factorizations can be used to define an automaton that recognize $L$. The states of this automaton are factorizations. Suppose $(X, Y)$ and $(X', Y')$ are factorizations and $a \in \Sigma$. The transition $(X, Y) \rightarrow^a (X', Y')$ exists iff $XaY' \subseteq L$. The initial states of this automaton consist of all those $(X, Y)$ such that $\varepsilon \in X$ and the final states contain all those $(X, Y)$ such that $\varepsilon \in Y$.

A grid is a pair $(U', V')$ with $U' \subseteq U$ and $V' \subseteq V$ such that for any $u \in U'$ and $v \in V'$, $uv \in L$. Corresponding to a grid, we have factorizations $(X\_{V'}, Y\_{U'})$ which consist of intersections of the corresponding quotients.

A grid cover is a collection of grids $\\{ (U\_\alpha, V\_\alpha)\\}\_{\alpha \in I}$ with the following property: If $u \in U \setminus (\cup\_\alpha U\_\alpha)$ and $v \in V \setminus (\cup\_\alpha V\_\alpha)$, then $u v \not \in L$. Again, if the language $L$ is finite, a finite grid cover always exists.

Corresponding to a finite grid cover, a set of factorizations are associated. Consider the subautomaton induced in the Universal Automaton by this exact set of factorizations. This is the Kameda-Weiner Automaton.

You can find a small KW automaton by choosing your grids appropriately.

---

\[1\] Minimalizations of NFA Using the Universal Automaton, by L. Polak (2005) \[IJFCS\]

\[2\] The Universal Automaton, by S. Lombardy & J. Sakarovitch (2008) \[Logic and Automata\]

\[3\] New Interpretation and Generalization of the Kameda-Weiner Method, by H. Tamm (2016) \[ICALP\]

---
Tags: algorithms, automata, finite-automata
---


# Question
Title: Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word
Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word accepts if and only if there are **exactly 2 accepted paths and all the others reject or no stop.**

I know that need at least 1 accepted path to accepting a word in a nondeterministic turning machine. At first glance, I think this is a disprove. Cannot build a deterministic Turing Machine with exactly 2 accepted paths and all the others rejects or no stop.

I have no idea how to disprove this claim any help will be appreciated

Thanks.

# Answer
Take a look at *Micheal Sipser* **Introduction to the Theory of Computation** 3rd edition pages 178 and 179.

In short, the proof uses a three-tape turning machine $D$ (which is equivalent to an ordinary turning machine) to *simulate* a nondeterministic TM $N$ with a deterministic one. Then, $D$ will try all the possible branches of the original nondeterministic TM. If $D$ finds a branch with an accept state, $N$ will accept too.

For the specific, two paths of your problem, I suppose you can use the accept paths in series to each other. Suppose you have a turning machine $M$, which is determinstic and derived from $N$. Now for a given input on the tape you can run $M$ to reach *a* accept state. Suppose that you found the accept state in branch $q\_i \rightarrow q\_j$. Now you feed the output of $M$ to another turning machine $M\_1$ which doesn't have the mentioned accept branch. If $M\_1$ reaches an accept state *too*, then you will know that there are exactly (or at least) two branches that accept a given input.
> 2 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Algorithm to return all possible ways to divide n unique elements into groups of size k
If I have as set N of n unique elements, is there a known algorithm that can return every possible way in which they can form groups of size k?

Eg: If N = { A, B, C, D} and k = 2, then the algorithm should return

```
[[(A, B), (C, D)],
 [(A, C), (B, D)],
 [(A, D), (B, C)]]

```

Here it's safe for me to assume that n is always divisible by k! :D

Sorry if this has already been asked, I couldn't find it.

Bonus: Is there a library to do this in Python?

# Answer
> 1 votes
The algorithm is straight-forward once you decide on the order of the subsets in the partitions. A simple algorithm produces partitions where:

* each subset in the partition is generated in order
* the subsets themselves are in order by their first element

These partitions can be produced recursively, adding each element of the set in turn to a partition of the initial elements where the partition components have at most $k$ elements. Such a partition can be extended with a new element by:

* adding the new element to one of the existing components, if that component has fewer than $k$ elements, or
* adding a new component at the end of the partition, if the partition doesn't already have $n/k$ components.

The same algorithm, without the check for the size of the partition element, could be used to generate all partitions.

You're unlikely to find this in a standard Python library, but I'm sure other implementations exist. In any event, this is not the right place to ask about software libraries in existing languages.

Here's the above algorithm written in Python. Unlike a functional version, this uses a state variable containing a mutable partial partition; each modification is undone after the recursive call, and the partitions finally produced are copied in order to avoid surprises.

```
def part(s, k):
    """Yields each partition of s into subsets of size k, which must be a
       divisor of len(s).
    """

    def step(i):
        if i == len(s):
            # Deep copy the current partition
            yield list(list(p) for p in part)
        else:
            for p in part:
                if len(p) < k:
                    p.append(s[i])
                    yield from step(i + 1)
                    p.pop()
            if len(part) * k < len(s):
                part.append(list(s[i]))
                yield from step(i + 1)
                part.pop()

    part = []
    yield from step(0)

```

In theory you could do this using a combinations generator, such as the one in the `itertools`:

```
(Pseudocode)
partitions(Seq, K) is
   if length(Seq) == K:
      return a single partition with Seq as its only component.
   otherwise:
       # Length must be > K; otherwise it wasn't a multiple of K to start with
       for each combination C of Seq of length K which includes Seq[0]:
           for each Partition in partitions(Seq - C, K):  (***)
               prepend C to Partition and add it to the list to result

```

Note the line (\***) which requires both a combination C and the list of other elements of Seq, ideally in order. There's no particularly easy way to get that out of `itertools.combinations`,

# Answer
> 0 votes
Here's Python code to do what you want fairly efficiently. It seems similar to rici's answer, but I didn't read through their answer to write this.

```
from typing import Set, List
from itertools import combinations

def group_iterator(s: Set, k: int) -> List[Set]:
    assert len(s) % k == 0, f"Set of size {len(s)} cannot be evenly split into groups of size {k}"
    # how many groups there are
    t = len(s) // k
    if t == 1:
        yield [s]
        return
    # get a random item from the set
    first_item = next(iter(s))
    # take out that first item so we don't use it again
    rest_of_elements = s - {first_item}
    # go through all the possible ways of getting the other items for this group
    for rest_of_group in combinations(rest_of_elements, k - 1):
        # go from the default tuple back into a set
        rest_of_group = set(rest_of_group)
        # add the first item back into the group
        group = {first_item} | rest_of_group
        # repeat recursively for the other groups
        # there will be no overlap with this group, because this is the only group that has this particular first item
        for other_groups in group_iterator(rest_of_elements - rest_of_group, k):
            yield [group] + other_groups

```

You can test it with:

```
for thing in group_iterator(set(["A", "B", "C", "D"]), 2):
        print(thing)

```

Output:

```
[{'C', 'A'}, {'B', 'D'}]
[{'C', 'D'}, {'A', 'B'}]
[{'C', 'B'}, {'A', 'D'}]

```

Please note that my type hinting is not 100% correct, but it doesn't really matter; it's just there to help people see the general form of the input and output. Fairly certain Mypy would not be happy with this in many different ways.

---
Tags: algorithms, combinatorics, python
---


# Question
Title: Are there already Neural Network AIs that can play object-finding games?
Neural networks are good at image analysis. They are also being used in video games which could outperform professional human players. I wonder if they can also play a purely object-finding game where a player needs to find objects in a photo as shown in the picture.

# Answer
As is often the case in ML, the only way to find out is to try it (or find someone else who has already tried it). You might be interested in methods for object detection, which basically do what you are asking for. The dataset they are trained on has a critical impact on their performance; they need to be trained on a large set of images that is "similar" to the ones they will be used on.
> 1 votes

---
Tags: artificial-intelligence, neural-networks, computer-games
---


# Question
Title: Are there any guidelines on how to decide algorithm strategy when approaching a problem?
There are many different general strategies when designing algorithms for a problem like divide and conquer, greedy, dynamic programming, etc. I understand that it is not always obvious which to use for a problem. However, I am at a complete loss as to how to even begin to make educated guesses. I assume intuition plays a huge part in this, but is there a reasonably concise summary anywhere of characteristics of problems that make them suitable for certain algorithm strategies?

I am having trouble parsing the many often super verbose and lengthy books on the subject.

Thanks in advance!

# Answer
> 0 votes
My rules of thumb and advice are:

1. When you have a problem and you're not sure which paradigm might be applicable, try them all.
2. Practice, practice, practice. As you get more practice with algorithm design questions, you'll start to get a "sixth sense" (an intuition) for when a particular paradigm might be worth a try or not. It might be hard to articulate the exact criteria, but as you practice, you'll get better at learning when a problem "smells like" it might be suitable for dynamic programming, or for divide-and-conquer, or some other paradigm.
3. Know the systematic approach for each paradigm, and try each one.

* For greedy algorithms, there are usually only a few plausible greedy algorithms. It's usually pretty quick to try them all and rule them all out by finding small counterexamples or trying random testing. See How to prove greedy algorithm is correct. If you can't quickly prove that some strategy doesn't work by searching for small counterexamples and random testing, then it's worth spending serious effort to try to prove it correct. Basically, greedy algorithms almost never work; and when greedy algorithms are applicable, it's usually pretty easy to come up with a candidate greedy strategy that will work if anything does.
    * For dynamic programming algorithms, use the "follow your nose" approach articulated at https://cs.stackexchange.com/tags/dynamic-programming/info. Dynamic programming is likely to be a good bet if you can identify subproblems, and when solutions to the subproblems might help you solve the original problem. Dynamic programming is often worth a try when the inputs are strings or lists or trees. There might be multiple ways you can define simpler subproblems, and it may take some cleverness to figure out how to use solutions to the simpler subproblems to solve the original problem. Here it helps if you've practiced a lot with using recursion to solve problems, as dynamic programming is in some sense a sped-up form of a naive recursive algorithm.
    * For divide-and-conquer algorithms, usually it's pretty obvious if divide-and-conquer might be applicable. Is there a way you can split up the original problem into two pieces, so that if you knew the solution for each piece, you could combine those solutions into a solution for the original problem? In some sense you can view divide-and-conquer algorithms as an easy special case of dynamic programming.
    * There's one more very common paradigm, which is to reduce the problem to some other task you've already learned how to solve. For instance, reduce the problem to graph reachability, to linear programming, to max flow, to bipartite matching, or any of a number of other standard algorithmic problems.

# Answer
> 0 votes
The design of algorithms essentially rests on the properties of the problem addressed. These range from elementary to highly sophisticated.

Examples:

* Computing the sum of a sequence exploits associativity of addition, so that accumulation to a single variable is possible (this can be seen as an elementary greedy process).
* Sorting an array can rely on different facts:

+ you can sort an array by exchanging pairs made of a large element followed by a small element. Any exchange brings you closer to the sorted array, and exchanges can be done in any order. A possible implementation is by brute force (BubbleSort f.i.).
    + you can sort an array by partitioning it so that the small elements precede the large ones and sorting every partition independently. The partition sizes are free. The partitioning process can be simpler than sorting. This leads to QuickSort but also StraightSelectionSort.
    + you can sort an array by sorting subarrays then merging them. The subarray sizes are free. The merging process is easier than sorting. This leads to MergeSort, but also StraightInsertionSort.
    + A heap data structure can be useful for sorting, as it allow to implement a priority queue. You get a sorted sequence by popping all elements from the queue (HeapSort).
* Solving a nonlinear equation can be done by successive approximations:

+ If the function is continuous and a change of sign is known in an interval, then if you split the interval one of the subintervals will certainly exhibit a change of sign. The fastest way to subdivide intervals is by halving (Dichotomic method).
    + If the function is smooth, the tangent to the curve can be a good approximation and the intercept with the X axis is an approximation of a root.

And so on...

---
Tags: algorithms, algorithm-design
---


# Question
Title: minimal DFA transition function clearification
**Statement:**

Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense that there is no other dfa with a smaller number of states that also accepts $L(M)$

**First some background information:**

The 'reduce' procedure:

Given a dfa $M=\left(Q, \Sigma, \delta, q\_{0}, F\right)$, we construct a reduced dfa $\widehat{M}=(\widehat{Q}, \Sigma, \widehat{\delta}, \widehat{q}, \widehat{F})$ as follows.

1. Use procedure mark to generate the equivalence classes, say $\left\\{q\_{i}, q\_{j}, \ldots, q\_{k}\right\\}$, as described.
2. For each set $\left\\{q\_{i}, q\_{j}, \ldots, q\_{k}\right\\}$ of such indistinguishable states, create a state labeled $i j \ldots k$ for $\widehat{M}$.
3. For each transition rule of $M$ of the form $$ \delta\left(q\_{r}, a\right)=q\_{p}, $$ find the sets to which $q\_{r}$ and $q\_{p}$ belong. If $q\_{r} \in\left\\{q\_{i}, q\_{j}, \ldots, q\_{k}\right\\}$ and $q\_{p} \in\left\\{q\_{l}, q\_{m}, \ldots, q\_{n}\right\\}$, add to $\widehat{\delta}$ a rule $$ \widehat{\delta}(i j \cdots k, a)=l m \cdots n . $$
4. The initial state $\widehat{q}\_{0}$ is that state of $\widehat{M}\_{\text {}}$ whose label includes the 0 .
5. $\widehat{F}$ is the set of all the states whose label contains $i$ such that $q\_{i} \in F$.

**A claim in order to prove the statement:**

Take any state $q \in Q$ and let $\hat{q}$ denote its equivalence class. For any word $w \in \Sigma^{\*}$, it holds that $\delta^{\*}(q, w) \in \hat{\delta}^{\*}(\hat{q}, w)$. The proof is by induction on the length $n$ of $w$. base case If $n=0$, then $w=\lambda$ and the claim is trivial since $$ \delta^{\*}(q, \lambda)=q \in \hat{q}=\hat{\delta}^{\*}(\hat{q}, \lambda) . $$ For the induction step assume our claim holds for all strings of length $n-1$ we show that it shows for strings of length $n$. In this case $w=a v$ for some $v$. We know that $$ \begin{array}{rlr} \delta^{\*}(q, w) & =\delta^{\*}(q, a v) \\ & =\delta^{\*}(\delta(q, a), v) & \text { definition of } \delta^{\*} \\ & \in \hat{\delta}^{\*}(\widehat{\delta(q, a)}, v) & \text { induction hypothesis } \\ & =\hat{\delta}^{\*}\left(\hat{\delta}^{}(\hat{q}, a), v\right) \\ & =\hat{\delta}^{\*}(\hat{q}, w) \\ \end{array} $$

**My question:**

In the proof of the claim above, I do not know how we can be sure that

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

It seems trivial, but shouldn't it be proven?

Source: *Formal languages and automata* by Peter Linz, 5th edition (Jones & Bartlett Learning), p. 75

# Answer
> $ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

The equality above is the definition of $\hat\delta$, given $\delta$. Let us paraphrase item 3.

> 3. For each transition rule of $M$ of the form $$ \delta(q, a)=\delta(q, a), $$ find the sets to which $q$ and $\delta(q, a)$ belong. If $q \in\hat q$ and $\delta(q, a)\in\widehat{\delta(q, a)} $, add to $\widehat{\delta}$ a rule $$ \hat{\delta}(\hat q, a)= \widehat{\delta(q, a)}. $$

---

On the other hand, there is an important question: why is $\delta$ well-defined? Suppose $q\_i\in \hat q$ and $q\_j\in \hat q$, then $\hat{\delta}(\hat q, a)$ is defined as $\widehat{\delta(q\_i,a)}$ as well as $\widehat{\delta(q\_j,a)}$. Are $\widehat{\delta(q\_i,a)}$ and $\widehat{\delta(q\_j,a)}$ the same equivalence class?

This well-defined-ness is a key step in the 'reduce' procedure. I will leave it for you to verify.
> 2 votes

---
Tags: formal-languages, regular-languages, finite-automata
---


# Question
Title: Is it possible to decrypt a string given part of the original string
Suppose I have an encrypted string of bytes. "T37mQkZosCsrcbqf/rvSWbd67qH3sXMggKdVd8fzMdg="

Suppose I know that somewhere in the original plain text string I know there is a string of numbers in ascii: "1234567"

Is is realistically possible to figure out the encryption key, or the rest of the string with just this information?

# Answer
Assuming that the encryption mechanism is not completely broken, having partial knowledge about the plaintext does not help figure out the rest of the plaintext. A property of an encryption mechanism is ciphertext indistinguishability under chosen plaintext attacks (IND-CPA) and under chosen ciphertext attacks (IND-CCA).

In plain English, a consequence of this is that if you have two guesses for the plaintext, and you're given a corresponding ciphertext for each plaintext, you can't yell which ciphertext matches each ciphertext. So, for example, even if you know that the plaintext is either `1234567a` or `1234567b`, there's no way to tell which one it is.

A further consequence is that even if you know many plaintext-ciphertext pairs, you still can't figure out the encryption key, since otherwise you'd be able to decrypt additional ciphertexts.

The only thing for which you can have partial information is the length of the plaintext. Since the ciphertext is 32 bytes long, unless the encoding is extremely bizarre, the plaintext would have to be 16 bytes or less (assuming a modern cipher with a 16-byte IV/nonce — even with some broken scheme such as ECB, it would have to be 32 bytes or less).

P.S. If the string is actually a hash rather than a ciphertext, it's possible to find the original input, but only by brute force, trying all plausible guesses until you find the right one.
> 2 votes

# Answer
Before having to figure out the encryption key, you would have to figure out the cryptosystem, which could be anything.

Also, be aware that many modern cryptosystems use a different key for encrypting (public key) and decrypting (private key).
> -1 votes

---
Tags: security, encryption
---


# Question
Title: Good Practice : Which VAE latent variable to use in dimensionality reduction
I'm trying to use a VAE (CNN-VAE to be exact) to reduce the dimension of some images I have in a dataset.

I successfully trained my VAE, but now I'm not sure of the latent variable to return.

Should I use $\mu$, $\sigma^2$, or $z$ (which is sampled from $\mu$ and $\sigma^2$) ?

Thank you in advance for the advice.

Liam

# Answer
> 1 votes
The simplest is to use $\mu$ as the output. You could also use $z$ as the output, but that will make your dimension reduction randomized, which in some settings might be undesirable (and others might be desirable).

---
Tags: machine-learning, data-compression, digital-image-processing
---


# Question
Title: Data Structure to Support Max Value of Keys Greater than Given Value
I want to support two operations:

1. Insert a (key, value) pair into the data structure in $O(\log n)$ time. The key can be assumed to be a unique integer.
2. Given an integer query value $v$, I want to return the (key, value) pair $P$ such that the value of $P$ is as great as possible amongst all (key, value) pairs with key greater than $v$ in $O(\log n)$ time. (Return NULL if no key is greater than $v$.)

Can this be done? My motivation comes from the longest increasing subsequence problem, which we know can be solved in $O(n \log n)$ time, with $n$ denoting the length of the input array. If we had a data structure like the one I described above, then it would lend itself to another $O(n \log n)$ solution to this problem: Iterate through the array in reverse order, performing operation 2 with $v$ equal to the $array\[i\]$ (the current array element). If no key in the data structure is greater than $v$, insert $(array\[i\], 1)$. Else insert $(array\[i\], max\\\_val + 1)$, where $max\\\_val$ is the result of the query. The answer is just the element of maximum value after traversing the entire array.

And as a bonus, what if we want to support finding the maximum value amongst keys in a two-sided range (i.e. one where there is an upper and lower bound)?

# Answer
Yes. Store the pairs in a self-balancing binary search tree, keyed on "key", with each pair stored in a leaf of the tree, with the pairs in sorted order by their key ("from left to right" as you walk over the leaves).

Augment the tree, as follows: each internal node in the tree stores the maximum value of "value", among all leaves under that node. Note that you can maintain and update these augmented values as you do every operation, with no increase in the asymptotic running time. (In particular, the max-value in any node is always the larger of the max-values of its two children.)

Every operation on this tree can be done in $O(\log n)$ time.

Now, suppose you're given a pair $P$. In $O(\log n)$ time, you can find the leaf where this pair lives in the tree (or where it would live). Next, follow the path from this leaf to the root of the tree. Look at the set of right-children of each node on the path to the root. The subtrees rooted at these right-children cover all pairs that have a larger "key" than $P$, and only those pairs. So, you can take the largest of the max-values in those right-children. The path to the root will have $O(\log n)$ length, so you can traverse it and check all the right-children in $O(\log n)$ time. Thus your second operation can also be done in $O(\log n)$ time.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Why do computers become slow over time (HW PoV)?
I'm a SW engineer. I'm just curious why computers become slow over time.

"Slow" here I mean from a usual user PoV:

* It takes more time to launch an application.
* Application UI takes longer to respond user interactions. Sometimes even freeze and unresponsive.
* Playing video files on local HDD becomes noncontinuous.
* Sometimes I type some text in "Notepad" program, when I finish pressing the keyboard, the characters have not shown up completely.
* etc.

Of course, I googled. I know Wintel alliance. But I have downgraded Windows to an old version. That does not mitigate. As a SW engineer, I'm not satisfied about the sayings that SW needs more HW resources, malware, etc. That does not explain my confusion.

I'd rather believe that it is HW performance degrading. But I cannot explain why.

I have an old PC which was bought at the same time as Windows 7 released, i.e., late 2009:

* HW: Intel Pentium T4200 CPU, 2GB DDR2 RAM, HDD.
* SW: Windows 7. Lots of application SW.
* Performance: Can play 1080p x264-encoded mp4 videos smoonly.

Now, year 2022:

* HW: Added 2GB more DDR2 RAM, replaced the HDD with an SSD.
* SW: Reinstalled a fresh Windows 7 and disabled Windows Update. Only necessary SW (web broswer and video player).
* Performance: stuck when playing 720p x264-encoded mp4 videos.

Why? Same SW, even "improved" HW, but degraded performance.

Possible factors:

* Heat. Lots of dust cover the fans. That degrades cooling capability.
* Power supply. The well-known "peak performance" issue on iPhone: Apple deliberately lower CPU frequency if battery health is \< 80%.

PS:

Same situation with another computer (a mainstream model) bought in 2018. One and (almost) the only difference is that Windows 10 keeps updating over time. Its slowness can be perceived conspicuously by a human.

# Answer
As mentioned in the comments, this has many open ends but there are certain major aspects which could contribute to slowing down.

1. It comes down to physics. As you said heat. Heat does a lot more than degrade cooling, motherboards are designed to detect temperatures, which on detecting a high temperature the motherboard will signal the components to slow down, which one experiences as **throttling**. Heat will also cause the components to expand slightly which can cause further degradation. Then there are semiconductor issues to consider like silicon degradation, electromigration, corrosion and even the operating environment of the computer could effect its performance. And if you have moving parts in your computer, they are bound to get slower over time.
2. Your benchmarking the performance is a bit dodgy. Why you might ask, because of point 1 and also because as hardware improves over time, software engineers make modifications in software to take advantage of hardware. It might very well be the case that Windows 7 wasn't optimized for being used with an SSD. Also just playing .mp4 at a resolution makes no sense, as the encoding used for the files matters as well, which would demand extra cpu juice. Even if you browse the web with an old pc, newer websites use a lot more javascript than what they used a decade ago, even if the page looks the same, it will demand a lot more processing power.
3. The underlying design and manufacturing of the cpu and motherboard. Again a broad point but to give some pointers, newer cpus support more instructions out of the box, so for an older cpu might have to simulate an instruction which could affect the performance a bit.
4. The operating system could also be a contributor to degrading the performance. I won't say Windows is bad but it definitely isn't good when it comes to performance(from my personal experience and opinion, comparing the same on a Linux based OS seems more relevant).
5. Other miscellaneous issues, like a damaged PSU, dust accumulation, worn out thermal grease and others, which only you can figure out.
> 3 votes

---
Tags: computer-architecture, performance
---


# Question
Title: Solve the recurrence $T(n)=T(\frac{n}{2})+\frac{n}{\log n}$ without master theorem
Suppose given the recurrence $$T(n)=T(\frac{n}{2})+\frac{n}{\log n}.$$ I think the answer is $$T(n)=O\left(\frac{n}{\log n}\right).$$ because $$T(n)=T(1)+\sum\_{i=0}^{\log n-1} \frac{n}{2^i(\log n-i)}$$ but how we can show that $\sum\_{i=0}^{\log n-1} \frac{n}{2^i(\log n-i}=O\left(\frac{n}{\log n}\right)$?

# Answer
> 1 votes
With $n:=2^m$, the recurrence turns to

$$S(m)=S(m-1)+\frac{2^m}m$$

and

$$S(m)=S\_0+\sum\_{k=1}^m\frac{2^k}k.$$

Splitting the sum and keeping the smallest denominators, we get $$S\_0+\sum\_{k=1}^{m/2-1}\frac{2^k}k+\sum\_{k=m/2}^m\frac{2^k}k\le S\_0+\sum\_{k=1}^{m/2-1}2^k+\frac 2m\sum\_{k=m/2}^m2^k\\\=O\left(2^{m/2}+\dfrac{2^m}m\right)=O\left(\frac{2^m}m\right).$$

Then indeed

$$T(n)=O\left(\frac n{\log n}\right).$$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks
I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are **not sorting networks**. In his paper "Smallest Compact Formulation for the Permutahedron" (An online version is available here http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf), he shows that any sorting network can be used to obtain an extended formulation for the permutahedron. This is done by expressing each comparator in the network by a set of linear constraints.

In another paper, "Extended Formulations in Combinatorial Optimization," Conforti et al. discuss this formulation and show that it can also be applied to any comparator network, sorting networks being a special case (It's Theorem 6.8 in Section 6.5 in the version of the paper shown here http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf). I am interested in using this extended formulation to look at a specific class of comparator networks.

My question is this (basically a sanity check to make sure I understood the proof correctly and that it is valid).

Can the extended formulation developed by Michael Goemans be applied to comparator networks that are not sorting networks such that in every vertex the input to the network will be a permutation of {1, 2, ... n} that the comparator network will sort? I believe that's what the proof in Conforti et al says but I just wanted to be sure.

Thank you,

# Answer
> 0 votes
Yes, if you are looking for an extension of P=Conv(x\_{sigma}, sigma \in G) where G is some given subset of permutations of \[n\],

then Goemans' construction works for any network which sorts all of your sigma \in G.

If (i\_1, j\_1), ... , (i\_k, j\_k) is the sequence defining your network, you will obtain a lift defined with 2k inequalities, and k+1 equalities (after projecting to a subspace of dimension n+2k exactly) The (k+1)-th equality is the one saying that you end up with the vertex (1,2, ..., n).

It might not be obvious from Goemans' paper, since in the proof of the correctness of his construction, he uses Edmonds' characterization of the permutaedron, which you loose when passing to a proper subset G...

But there are other proofs of correctness of his construction, with simple geometric arguments and no combinatorics involved. Thanks to such arguments, Goemans' construction extends to your setting, with no harm.

---
Tags: algorithms, optimization, sorting, linear-programming, comparison
---


# Question
Title: Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$
Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log\_2n}$ using iterative method.

# Answer
Assuming that $n$ is a power of $2$ and that $T(1)=1$.

$$ \begin{align\*} T(n) &= 4 T(n/2) + \frac{n^3}{\log n} \\ &= 4 \left(4 T(n/4) + \frac{(n/2)^3}{ \log (n/2)}\right) + \frac{n^3}{\log n} \\ &= 16 T(n/4) + \frac{n^3}{2 \log(n/2)} + \frac{n^3}{\log n} \\ &=16 \left(4 T(n/8) + \frac{(n/4)^3}{ \log (n/4)}\right) + \frac{n^3}{2 \log (n/2)} + \frac{n^3}{\log n} \\ &=64T(n/8) +\frac{n^3}{4\log(n/4)} + \frac{n^3}{2 \log (n/2)} + \frac{n^3}{\log n} \\ &= \dots \\ & = 4^i T(n/2^i) + \sum\_{j=0}^{i-1} \frac{n^3}{2^j \log(n/2^j)} \end{align\*}. $$

Choosing $i=\log n$: $$ T(n) = n^2 + \sum\_{j=0}^{\log n - 1} \frac{n^3}{2^j \log(n/2^j)}. $$

We can now obtain a lower bound by only considering the first term of the sum (i.e., $j=0$): $$ T(n) \ge n^2 + \frac{n^3}{\log n} = \Omega\left(\frac{n^3}{\log n}\right). $$

For the upper bound observe that, for $t \ge 4$: $$\frac{t^3}{\log t} = \frac{(2t)^3}{8 (\log 2t - 1)} = \frac{(2t)^3}{8 \cdot \log 2t \cdot \frac{\log 2t - 1}{\log 2t}} \le \frac{3}{16} \cdot \frac{(2t)^3}{\log 2t} $$ Showing that, for $0 \le j \le \log n -2$: $$ \frac{n^3}{2^j \log(n/2^j)} \le \left(\frac{3}{16}\right)^j \frac{n^3}{\log n}. $$

Then: $$ \begin{align\*} T(n) &= n^2 + 2n^2 + \sum\_{j=0}^{\log n - 2} \frac{n^3}{2^j \log(n/2^j)} \\ &\le 3n^2 \+ \frac{n^3}{\log n} \sum\_{j=0}^{\log n - 2} \left(\frac{3}{16}\right)^j \le 3n^2 + \frac{n^3}{\log n} \cdot \frac{16}{13} = O\left(\frac{n^3}{\log n}\right). \end{align\*} $$

If you are fine with using the Master theorem instead of iteration then you can check that, for any $0 \<\varepsilon \< 1$, $\frac{n^3}{\log n} = \Omega(n^{\log\_2 4 + \varepsilon})$ and that the regularity condition holds, implying that $T(n) = \Theta(\frac{n^3}{\log n})$.
> 0 votes

# Answer
With $n=2^m$, let $S(m):=4^{-m}T(2^m)$. The recurrence turns to

$$4^mS(m)=4^{m-1}4S(m-1)+\frac{8^m}{m}$$

or $$S(m)=S(m-1)+\frac{2^m}{m}.$$

Then refer to this answer: https://cs.stackexchange.com/a/153922/16034
> 0 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Design an algorithm to calculate stock prices on a given day
Given a list of lists containing tuples in sorted(by day) order find and print the total number of stock units owned for every day that occurs at least once.

```
#first  number in each tuple represents a day, second number represents how many units of that stock is owned.
#if a day is missing, you can assume the stock value didn't change from the previous entry.
#example number of msft stocks owned on day 1 is 300 and there is no input for day 2, so day 2 is 300
#notice that the stock number can decrease, google went down from its last reported day (2) to (5) by 300 units

#print the total number of stocks owned on every day that occurs in the stock_input

#expected values for the example input:
1 - 400
2 - 1000
3 - 1400
5 - 1100

stock_input = []

msft = [(1,300),(3,500)]
amzn = [(1,100),(2,300),(3,500)]
goog = [(2,400),(5,100)]

stock_input.append(msft)
stock_input.append(amzn)
stock_input.append(goog)

```

I'm not sure how exactly to attack this problem. I think it would involve some sort of flood fill type algorithm, but the gap in dates makes it a bit harder than a standard DFS because you have to know which day to search for.

# Answer
```
def calculateTotalStocks(stock_data):
    min_day = float("inf")  # minimum day in all stocks
    max_day = float("-inf") # maximum day in all stocks
    for i in stock_data:    # loop through all stocks
        for j in i:       # loop through all days in a stock
            min_day = min(min_day, j[0])    # find minimum day
            max_day = max(max_day, j[0])    # find maximum day
    stock_dict = dict().fromkeys(range(min_day, max_day+1), 0)  # create a dictionary with all days as keys and 0 as values
    for stock in stock_data:                                 # loop through all stocks
        counts = dict().fromkeys(range(stock[0][0], max_day+1), 0)  # create a dictionary with starting day as in stock and max day as ending day
        for idx, count in stock:                             # loop through all days in a stock
            counts[idx] = count                             # add count to dictionary
        prev = stock[0][0]                                 # set previous day to starting day of stock
        for key in range(stock[0][0]+1, max_day+1):       # loop through all days in dictionary after starting day
            if counts[key] == 0:                    # if count is 0
                counts[key] = counts[prev]       # set count to previous count
                prev = key                     # set previous day to current day
            else:                             # if count is not 0
                prev = key                   # set previous day to current day
        for key in counts:               # loop through all days in dictionary
            stock_dict[key] += counts[key]  # add count to total count
    return stock_dict           # return dictionary

def main(): # main function
    stock_input = []    # create empty list

    msft = [(1,300),(3,500)]    # create list for Microsoft
    amzn = [(1,100),(2,300),(3,500)]    # create list for Amazon
    goog = [(2,400),(5,100)]    # create list for Google

    stock_input.append(msft)    # add Microsoft to list
    stock_input.append(amzn)    # add Amazon to list
    stock_input.append(goog)    # add Google to list

    ans = calculateTotalStocks(stock_input)   # calculate total stocks
    for k, val in ans.items():              # loop through all days in dictionary
        print(f"{k} - {val}")            # print day and count

# Entry point of program
if __name__ == "__main__":
    main()  # call main function

```
> -1 votes

---
Tags: graphs, python
---


title: Is $n=\Theta(n^{1+o(1)})$?

text:
# Question
Title: Is $n=\Theta(n^{1+o(1)})$?
Is $n=\Theta(n^{1+o(1)})$?

To me it appears to be true as $n$ tends to infinity $n^{o(1)} =0$.

# Answer
> 3 votes
Let me rephrase the question by getting rid of the double asymptotic notation in the formula: If you are asking whether there **exists** a function $f(n) \in o(1)$ such that $n \in \Theta(n^{1+f(n)})$, then the answer is yes.

Take $f(n) = \frac{1}{\log n}$ and notice that $f(n) \in o(1)$. Then: $$ n^{1+\frac{1}{\log n}} = n \cdot n^{\frac{1}{\log n}} = n \cdot (2^{\log n})^{\frac{1}{\log n}} = 2n = \Theta(n). $$

However the same is not true **for all** $f(n) \in o(1)$ as it can be seen by choosing $f(n) = \frac{1}{\sqrt{\log n}}$. $$ n^{1+\frac{1}{\sqrt{\log n}}} = n \cdot n^{\frac{1}{\sqrt{\log n}}} = n \cdot (2^{\log n})^{\frac{1}{\sqrt{\log n}}} = n \cdot 2^{\sqrt{\log n}} = \omega(n). $$

This also shows that, in general, it false that $n^{o(1)}$ approaches $0$. Indeed, $n^{\frac{1}{\sqrt{\log n}}} = 2^{\sqrt{ \log n}}$ approaches infinity (and grows faster that any polylogarithm).

# Answer
> 3 votes
This amounts to proving

$$1=\Theta(n^{o(1)})=\Theta(e^{\log(n)\\,o(1)})$$ (not $0$ as you wrote). But the $o(1)$ factor could decrease to zero slower than $\dfrac1{\log(n)}$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: What's the difference between computation and symbolic manipulation?
I have lived my academic career thinking these two terms were interchangeable but something arose in me that said they're distinct. Are there any logical, formal definitions distinguishing between the two?

# Answer
I can only speak for me (and maybe my interpretation is also caused by a different understanding of the English language), but I would say

1. Computation: That's numerical. Solving a problem by calculation with numbers.
2. Symbolic manipulation: That's like analysis. Solving the problem by e.g. term transformation, if I say, I get the solution b, by transforming a + b = c to b = c - a.
> 1 votes

---
Tags: definitions
---


# Question
Title: How to show invariance under additive and multiplicative illumination changes
The task is to "Show that the transformation f -\> ((ln fx)x, (ln fy)y) is invariant under additive and multiplicative illumination changes."

From my lecture notes, for ((ln f)x, (ln f)y), I have:

ln (c\*f(x,y)) = ln c + ln f(x,y)x = (ln c)x \+ (ln f(x, y))x with the note that the first term is 0 if c is global and therefore doesn't depend on x and y. The same can be done for the y-derivative: making the product a summation by taking the log, and then taking the derivative.

Can this also be applied to the function from the task description or do the subscripts change something? Can someone explain it to me? Does this show invariance under multiplicative change? Would this also be sufficient to show invariance under additive change?

# Answer
> 0 votes
$$g:=af+b\to g'=af'\to\log g'=\log a+\log f'\to(\log g')'=(\log f')'.$$

The first differentiation kills the additive constant. The second *logarithmic* differentiation kills the multiplicative constant.

Notice that nothing prevents the first derivative to be negative, causing the logarithm to be undefined.

---
Tags: computer-vision, mathematical-foundations, digital-image-processing
---


title: Is LR(1) closed under union?

text:
# Question
Title: Is LR(1) closed under union?
Suppose I have two LR(1) languages $L\_1$, $L\_2$. Is $L\_1 \cup L\_2$ also LR(1)? References to proofs would be very helpful.

# Answer
> 4 votes
A simple example is $$L\_1 = \\{a^i b^i c^j \mid i,j\ge 0\\}$$ $$L\_2 = \\{a^i b^j c^j \mid i,j\ge 0\\}$$

Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ambiguous, so not $LR(k)$ for any $k$.

This is also the usual example for non-closure of context-free languages over intersection. $L\_1 \cap L\_2$ is $\\{a^i b^i c^i \mid i\ge 0\\}$, the classic non-context-free language.

---
Tags: formal-languages, context-free, closure-properties, lr-k
---


# Question
Title: All possible cycles passing through a vertex "v" containing a particular label
For any directed/undirected labelled graph `G := (V,E,L)`, where L is the finite set of labels, and every edge has a label. For simplicity, let us assume that `L = {a,b}`. Is there a P-time algorithm to determine whether all possible cycles passing through a vertex "v" has at least one edge (every cycle) with label "a"? We can assume that G is simple with self-loops.

The naive approach would be to enumerate all possible cycles passing through "v" and then check every edge label. I was thinking of a more efficient approach, to eliminate traversing some repeated paths based on whether "a" was encountered/not, and reduce the complexity to that of DFS - I cannot decisively conclude for now that this will be P-time.

# Answer
The question is equivalent to asking whether there exists a cycle that goes through $v$ and uses only b-edges. This can be tested by deleting all a-edges, then testing whether the resulting graph has a cycle that goes through $v$ using any standard algorithm. This gives an algorithm that runs in polynomial time -- in fact, in linear time.
> 0 votes

---
Tags: graphs, graph-traversal
---


title: Complexity for optimized k-sum problem

text:
# Question
Title: Complexity for optimized k-sum problem
Following up on these two posts Generalised 3SUM (k-SUM) problem? https://people.csail.mit.edu/virgi/6.s078/lecture9.pdf

The claim is that k-sum in the general case can be solved in $O(n^{k/2}log(n))$

However, I don't follow this claim. The quote reads

> For even : Compute a sorted list of all sums of /2 input elements. Check whether contains both some number and its negation −. The algorithm runs in (/2log) time.

Compute a list of all sums of k/2 input elements. $O(n^{k/2})$

Sort this list: $O(n^{k/2}log(n^{k/2})=O(k/2\*n^{k/2}log(n))$

Sandwich with two pointers to find s and -s. We have a valid answer iff the indices of elements that make up s and -s are nonoverlapping. However, because we have to check each instance of -s in order to validate whether the indices are non-overlapping, we end up having a computation that is $O(n^{k/2})$. This means that this step is $O(n^{k/2} * n^{k/2})$.

Am I misunderstanding an optimization?

# Answer
> 0 votes
In case we desire that all indices are distinct one can use balanced BSTs such as an AVL-Tree to check if indices overlap. For each of the $O(n^{k/2})$ sums you also store the set of indices (using a balanced BST as Data structure). Now creating all these sets takes $O(n^{k/2}k/2\log(k/2))$, because we need to insert $k/2$ elements in every set. Now when check if there exists $-n$ for any $n$ we need to check if their sets overlap. This again takes $O(k/2\log(k/2))$ or for every number $O(n^{k/2}k/2\log(k/2))$. Thus for constant $k$ we still maintain the runtime $O(n^{k/2}\log(n))$

---
Tags: complexity-theory, combinatorics
---