# Question
Title: Having a 2D matrix with three typed elements, how to efficiently cover one of the types and NOT cover the other one?
I have a matrix with three possible elements: A, B and C. The size of the matrix could be a maximum of 15x16.

$$ \begin{bmatrix} A & A & C & A\\ A & C & B & C\\ A & C & B & C\\ A & A & C & A \end{bmatrix} $$

I need create a second matrix with the same size but different types. I need to cover all Cs with a "group", but NOT cover all Bs. As from the matrix could be covered, but dont need to be. The coverage needs to be done with groupes. Cells in a group are all connected. Each group can't be bigger than 12. The first example could be covered with only one group.

0 - empty 1 - first group $$ \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 \end{bmatrix} $$

I need an efficient algortihm that can produce legal groups (\<= 12 cells) that cover all the Cs. The goal is to have as less as possible groups. If first goal is achived, the second goal is to use less material for coverage.

How to tackle this? This seems to be a very complex problem.

Second example: $$ \begin{bmatrix} A & A & C & C & A & A\\ A & C & B & B & C & A\\ A & C & B & C & A & A\\ A & C & B & C & C & A\\ A & A & C & C & B & C\\ A & A & A & A & C & A \end{bmatrix} $$ One of the solutions to example 2: 0 - empty 1 - first group 2 - second group $$ \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 2 & 0 & 0\\ 0 & 1 & 0 & 2 & 2 & 0\\ 0 & 1 & 1 & 2 & 0 & 2\\ 0 & 0 & 0 & 2 & 2 & 2 \end{bmatrix} $$

# Answer
> 1 votes
This looks very hard to me. I wouldn't be surprised if it is NP-hard.

If I had to solve it in practice, my first thought would be to try to solve it using a SAT solver or an ILP solver. I outline below how you could do that.

Given $k$, let's figure out whether there is a way to solve this using $k$ groups. If we can do that, we can use binary search over $k$ to find the smallest $k$ for which a solution exists (e.g., try $k=1,2,4,8,\cdots$ to find the first power of two for which a solution exists, then use binary search to narrow down exactly the minimum workable value of $k$).

# Solving with a SAT solver

To solve this with a SAT solver, we need to formulate the problem in terms of boolean variables. I suggest introducing boolean variables $x\_{c,i,j}$, where $c$ ranges over cells (locations) in the original matrix, $1 \le i \le 12$, and $1 \le j \le k$. The intent is that $x\_{\cdot,12,j}$ should represent the $j$th group, i.e., $x\_{c,12,j}$ should be true iff the $j$th group puts a 1 in cell $c$.

We need to ensure that the groups cover all C's. This can be done with the following constraints (clauses):

* For each cell $c$ that contains a C, $x\_{c,12,1} \lor \cdots \lor x\_{c,12,k}$

We need to ensure that the groups don't cover any B. This can be done with the following constraints:

* For each cell $c$ that contains a B and each $i,j$, $\neg x\_{c,i,j}$

We need to ensure that each group has at most 12 1's. This can be done as follows:

Finally, we need to ensure that each group is connected. This is the hardest, but can be done as follows. The idea is that we'll grow a group, starting from a single cell (say $c\_0$) and then expanding it; then $x\_{\cdot,i,j}$ will be true for all cells with a 1 that are at most Manhattan distance $\le i$ from cell $c\_0$. This can be expressed in SAT as follows:

* For each $j$, exactly one of $x\_{\cdot,1,j}$ is true. This is a cardinality/pseudo-boolean constraint; see above for how to enforce it.
* $x\_{\cdot,i,j}$ contains at least as many cells as $x\_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i\>1$, $x\_{c,i-1,j} \implies x\_{c,i,j}$.
* $x\_{\cdot,i,j}$ is grown from $x\_{\cdot,i-1,j}$ by adding only neighbors of cells in $x\_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i\>1$, we have $$x\_{c,i,j} \implies (x\_{c,i-1,j} \lor x\_{c\_L,i-1,j} \lor x\_{c\_R,i-1,j} \lor x\_{c\_U,i-1,j} \lor x\_{c\_D,i-1,j})$$ where $c\_L,c\_R,c\_U,c\_D$ are the four cells that are adjacent to $c$.
* It may be helpful to add the extra constraint that $x\_{\cdot,i,j}$ has at most 12 true values, for each $i,j$.

Finally, take the conjunction of all of these constraints, hand them to an off-the-shelf SAT solver (I like Z3Py), and ask it whether it can find any satisfying assignment. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.

# Solving with an ILP solver

Another option is to use an ILP solver. Cardinality constraints are easier to express in an ILP solver, and boolean constraints are slightly messier but can all be done (see Express boolean logic operations in zero-one integer linear programming (ILP)), so you could do this with ILP instead of SAT. I don't know which will be more effective. You could try both if necessary.

Here's how this looks, for your particular case. We have 0-or-1 integer variables $x\_{c,i,j}$, i.e., they are all marked integer and we add inequalities $0 \le x\_{c,i,j} \le 1$. Now let's walk through the constraints (linear inequalities).

We need to ensure that the groups cover all C's. This can be done with the following inequalities:

* For each cell $c$ that contains a C, $x\_{c,12,1} + \cdots + x\_{c,12,k} \ge 1$.

We need to ensure that the groups don't cover any B. This can be done with the following constraints:

* For each cell $c$ that contains a B and each $i,j$, $x\_{c,i,j} = 0$.

We need to ensure that each group has at most 12 1's. This can be done as follows:

* $\sum\_c x\_{c,12,j} \le 12$

Finally, we need to ensure that each group is connected. Following a similar idea as before, this can be expressed as an ILP as follows:

* For each $j$, $\sum\_c x\_{c,1,j} = 1$.
* For each $i,j,c$ with $i\>1$, $x\_{c,i-1,j} \le x\_{c,i,j}$.
* For each $i,j,c$ with $i\>1$, we have $$x\_{c,i,j} \le x\_{c,i-1,j} + x\_{c\_L,i-1,j} + x\_{c\_R,i-1,j} + x\_{c\_U,i-1,j} + x\_{c\_D,i-1,j}$$ where $c\_L,c\_R,c\_U,c\_D$ are the four cells that are adjacent to $c$.
* It may be helpful to add the extra constraint that $\sum\_c x\_{c,i,j} \le 12$, for each $i,j$.

Finally, take all of these linear inequalities, hand them to an off-the-shelf ILP solver (Gurobi?), and ask it whether it can find any solution. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.

---
Tags: algorithms, matrices, python
---


# Question
Title: Storing game traces (e.g. Chess, Othello) in a minimal number of bits
I am thinking about the problem of storing traces of games like Chess and Othello in an information-theoretic minimal number of bits. My idea was to think of a game as an ordered tree of possible moves that could be taken.

Let's say in one game there are 20 moves available initially, then 8 on the second turn, then 5 on the third move, then 10 on the fourth turn. In this game, the moves 4/20, 1/8, 3/5 and 3/10 are played.

The idea would be to store the entire game as a single number that is calculated as follows:

```
4     +   (1 * 20) + (3 * 20 * 8) + (3 * 20 * 8 * 5)
^          ^          ^              ^
turn 1     turn 2     turn 3         turn 4

```

This sums to 2904 so you could store it in 12 bits.

To recover the game from this number, you'd initially look at the start position and see that 20 moves are available on the first turn. To calculate the move for the first turn, you'd do (2904 % 20) which is 4.

After simulating move 4 in your model of the game, you'd then realise that 8 moves are available for the second turn. To calculate the move for the second turn you'd (integer) divide 2904 by 20 which is 145 and then do (145 % 8) which is 1.

After simulating move 1 in your model of the game, you'd then realise that 5 moves are available for the third turn. To calculate the move for the third turn you'd (integer) divide 145 by 8 which is 18 and then do (18 % 5) which is 3.

... and so on to recover the rest of the moves.

Is this an information-theoretic minimal way to store game traces? It seems like it should be because every number can be mapped to a unique game trace and vice-versa. Is this already known? Is there literature on this approach?

We're essentially using the branching factor of the game tree as the base of a number system. This creates a Gödel numbering system for all possible game traces.

The downside of this approach is that we don't know in advance how many bits are needed to store any possible game unless we exhaust the entire search space of possible games.

# Answer
If the number of possible moves does not depend on the game history (say, at the third move there are always 5 possibilities), then the "mixed-radix" scheme you describe is optimal, as it encodes all integers in the range of the number of possible games.

But it is difficult to encode/decode because you need to trace the game history, and on every move simulate the possibilities in a predefined order to find the Nth one.

If the number of possibilities does depend on the game history (which is the case for chess and Othello), then your encoding has variable length, so that it isn't the shortest possible in the worst case.

To truly achieve the shortest codes, you may enumerate all games in a canonical order and assign them a sequence number, but this makes encoding and decoding much harder, if not impossible.
> 2 votes

---
Tags: information-theory, number-theory, board-games
---


title: Recursive DFS Problem

text:
# Question
Title: Recursive DFS Problem
I have been struggling with this contest problem for awhile now which is found at this link: https://people.eecs.berkeley.edu/~hilfingr/programming-contest/pacific-northwest/2009/b.pdf

Short summary of problem: Given an n×m board (3 ≤ n≤6, 5≤m≤50) move a Blenjeel sand worm (of length n) from the left column to the right column, ensuring the worm never simultaneously occupies two squares of the same color.

It's acceptable for the worm to reach the right column in either orientation. The worm can move either from its head or tail, meaning that if the head moves (at any particular time) to a new valid position on the grid, the tail would now be located at the "second to last" square of where the tail was previously located. The same idea occurs if the tail were to be moved instead.

Given an input of ints which represents a board such as:

12324

31312

41431

output the minimum number of moves needed to move the worm from the left column to the right column, or -1 if there is no such solution.

My current train of thought is a recursive DFS that calculates the min path the worm can take from the left column to the right column. This is done by keeping track of the number of moves at each recursive call, as well as making sure we don't have duplicate colors in the worm at anytime, and avoiding cycles by not letting the worm visit a configuration that was already visited (provided the repeated visit happens in the same recursive path). This solution semmed good to me initially but it does not seem to pass some of the test cases.

I have been stumped for awhile now and I was wondering if anyone has any idea on how to correctly approach this problem? Any hints/ideas are appreciated.

# Answer
> 1 votes
You can use BFS to find a shortest path as long as you specify what "vertices" and "edges" are in this graph. One way is the following:

A *vertex* is an ordered list (call it $L$) of $n$ ordered pairs (representing locations in the grid) such that

1. consecutive pairs are "neighbors",
2. $n$ unique locations are present,
3. $n$ unique colors are present.

But because the worm is reversible, this set of vertices is further subject to the relation that any vertex represented by $L$ can also be represented by $L^{rev}$.

Next we define *edges*: $v\_1$ is joined to vertex $v\_2$ if they can be represented by lists $L\_1$ and $L\_2$ such that the first $n-1$ pairs of $L\_2$ equal the last $n-1$ pairs of $L\_1$.

During your implementation you might choose canonical (1 of the 2 possible) representatives of each vertex so that you can mark which vertices have been traversed. You might also define a subroutine to generate all neighboring vertices from a given vertex. To sum up, the vertices are all valid "states" that the worm can be in. And the problem becomes finding the distance between the vertex represented by $\[(0,0), (1,0), \ldots, (m-1,0)\]$ to the vertex represented by $\[(0, n-1), (1, n-1), \ldots, (m-1,n-1)\]$ .If the latter is not a vertex then you can just return false.

---
Tags: recursion, depth-first-search
---


# Question
Title: Update a property of all objects in a List/Collection/Array when at least one object satisfies a criteria using a single loop
Here is the puzzle I was asked in an interview

There's a List of Employee objects. Update all the objects in the list to be eligibleForHike if at least one employee exists whose salary is less than x; otherwise update all of them in-eligibleForHike in a single iteration/loop

**Requirements/Restrictions**:

1. Streams should not be used
2. Only one pass/iteration/loop
3. Not allowed to used two loops (even though not nested and even though the time complexity would still be O(n)). Not sure why, but may be because it's a puzzle

Employee class

```
public class Employee {
   private String name;
   private Double salary;
   private Boolean eligibleForHike;
   //all getters and setters defined
}

```

My solution (not elegant) because of space complexity

```
public List<Employee> checkEligibility(List<Employee> employees, Double salary) {
   List<Employee> eligible = new ArrayList<>();
   List<Employee> inEligible = new ArrayList<>();
   boolean isEligibleForHike = false;
   employees.forEach(employee -> {
      Employee e1 = employee.clone();
      e1.setEligibleForHike(true);
      Employee e2 = employee.clone();
      e2.setEligibleForHike(false);
      eligible.add(e1);
      inEligible.add(e2);
      if(!isEligibleForHike && employee.getSalary() < salary) {
         isEligibleForHike = true;
      }
   });
   return isEligibleForHike ? eligible : inEligible;
}

```

Another solution I proposed is

```
public List<Employee> checkEligibility(List<Employee> employees, Double salary) {
    int i = 0;
    boolean isEligibleForHike = false;
    for(i = 0; i < employees.size(); i++) {
        if(!isEligibleForHike) {
            employees.get(i).setEligibleForHike(false);
            if(employees.get(i).getSalary() > salary) {
                i = 0;
                isEligibleForHike = true;
                employees.get(i).setEligibleForHike(true);
            }
        } else {
            employees.get(i).setEligibleForHike(true);
        }
    }
    return employees;
}

```

The interviewer was not satisfied with this solution either because I am resetting the index to 0, said the time is not O(n). I explained in determining the complexity, k (constant) doesn't matter. In worst case, it would be O(2\*n) where 2 is k/constant, and the complexity still remains O(n)

But their explanation was if 500K records take 2 sec to process in O(n) case, in worst case, it would be 4 sec (i.e twice the original time taken)

Posting here to find a better solution to this problem, where the same List of objects can be updated in place and still use only one loop and order still O(n) not a factor of k (constant)

# Answer
> 0 votes
**Solution**: Have a reference which dictates the `hikeEligibility` which can be `false` by default. Iterate and assign the same reference to all the objects in the collection. If at least one item in the collection meets the criteria, set the value of `hikeEligibility` to `true`

```
 public List<Employee> checkAndUpdateHikeEligibility(List<Employee> employees, Double salary) {
     List<Employee> result = new ArrayList<>();
     Boolean isEligibleForHike = false;
     for(int i = 0; i < employees.size(); i++) {
         Employee e = employees.get(i);
         if(e.getSalary() < salary) {
             isEligibleForHike = true;
         }
         e.setEligibleForHike(isEligibleForHike);
         result.add(e);
     }
     return result;
 }

```

---
Tags: algorithms, data-structures, optimization, java, program-optimization
---


title: Grammar where tokens can be transmuted

text:
# Question
Title: Grammar where tokens can be transmuted
I have a grammar which is mostly `LL(1)`, save for the fact that some tokens may be promoted to larger integer types.

For example, let take the following grammar

```
S ::= terminal1 S1
S1 ::= integer_16 S2 | integer_32 S3

```

where `S2` and `S3` can share a common prefix but we assume the above grammar can be rewritten as `LL(1)`, save for the integer promotion and that the narrowest numbers have precedence over the the wider numbers.

Let's assume that I read an `integer_16` but fail to match `S2`, I'll backtrack and promote `integer_16` to `integer_32`. This can be easily done when doing error-recovery by adding a case for non-fatal error if the token can be promoted.

This is a special case of `LL(k)` grammar, but my question is does such grammars (`LL(1)`+some dirty error-recovery tricks) have a standard name?

# Answer
The type of a literal integer is semantic, not syntactic, and should not be part of syntactic analysis. In other words, the program text can be *parsed* -- broken into syntactic parts with known relationships -- without knowing the magnitude of each integer literal. The magnitude of the literal does not affect the literal's syntactic role; the operand of an multiplication does not transform itself into an operand of an adjacent addition if it becomes greater. In other words, `x + y * z always means the sum of` x`and the product of`y`and`z\`, no matter what the magnitudes of the three values might be. (At least, I hope that's true of your language. If it isn't, composing correct code would be a difficult undertaking.)

You might argue that some choices of value lead to invalid code, for example in a language without automatic widening conversions. Certainly, some semantic errors can be statically detected; others cannot. But that's not the goal of the parser. Type analysis and validation (or rejection) of type conversions are semantic operations, whether done in a semantic action or in a post-parse walk over the parse tree.

The key to writing a maintainable parser is to respect the principle of separation of concerns. A lexical analyser splits the input into tokens; nothing else. A parser creates the hierarchical structure of the program as a graph (usually a tree, at least in the first instance), and nothing else. A type-checker discovers and validates the semantic type of each component of an expression. And so on. Separation of concerns makes your programs easier to read, easier to debug, and easier to maintain.

Of course, nothing is totally pure. Your lexical analyser might convert each numeric literal into some internal representation of a number, and there might be different possible representations: different widths, different precisions, and so on. That might turn out to be a useful optimisation, instead of keeping them as character strings, for any of a number of reasons. But it's a trade-off: you will also have to deal with literals not using the representation which program semantics require, which I think is the basis of your question. Coping with that might complicate your code (or not, depending on the language your compiler is written in), in which case you might reasonably consider whether the optimisation justifies the complication. Sometimes, it turns out that it doesn't. Particularly at the beginning, it's often good to always choose the simplest implementation over the most efficient.

Regardless, it has nothing to do with parsing theory; LL(1) is LL(1), no matter what the semantics might be.
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: Improving an algorithm involving two pairs of sums
Suppose $l=\[a\[0\],a\[1\],a\[2\],,a\[n\]\]$ be a list of numbers. I need to calculate $$ \sum a\[j\]a\[k\]a\[j'\]a\[k'\] $$ such that $j+k=j'+k'$ .Obviously we can implement it in $O(n^4)$ time complexity by the exhaustive search method.Can we do it better?It is pertinent to mention the number of tuples satisfying $j+k=j'+k'$ are approximately $n^3.$Any help/hints are highly appreciated

# Answer
It's trivial to do in $O(n^3)$ time, by enumerating all $O(n^3)$ tuples $(j,k,j',k')$ such that $j+k=j'+k'$, computing the appropriate product, and summing those products. I'll let you discover how to enumerate those tuples. I am confident you can figure that out: if you spend a little time thinking about it and/or working through some small examples with $n=1$, $n=2$, $n=3$ by hand, I'm sure you'll be able to come up with an algorithm.

You can compute this sum in $O(n^2)$ time using the following identity:

$$\begin{align\*} \sum a\[j\]a\[k\]a\[j'\]a\[k'\] &= \sum\_s \sum\_{j,j'} a\[j\] a\[s-j\] a\[j'\] a\[s-j'\]\\ &= \sum\_s \left(\sum\_j a\[j\] a\[s-j\] \right)^2. \end{align\*}$$

where $s$ ranges over $0,1,2,\dots,2n$ and $j,j'$ range over $0 \le j \le \min(n,s)$ and $0 \le j' \le \min(n,s)$.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Optimal algorithmic complexity of "a nonrepetitive stack"?
I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'.

A nonrepetitive stack is like an ordinary stack, except that a push that would result in a repeated subsequence fails, not updating the stack but instead returning the location of the subsequence that would be repeated. (To disambiguate, because "repeated subsequence" can mean multiple things: I mean multiple contiguous copies of contiguous subsequences. If you treat the stack as a string, something matching `.*(.+)\1.*`.)

(Assume the usual model, e.g. comparing two individual items for equality is $O(1)$.)

The completely naive approach would be to check the entire stack for any repeated subsequences after each push, and undo the push and fail if one is found. Each check, and thus push, appears to be $O(n^3)$ in the current size of the stack, worst-case.

We can do somewhat better by instead noting that the stack can never actually include any repeated substrings (as you cannot introduce a repeated substring by popping from a stack, and pushes that would introduce a repeated substring instead fail), and so a push only needs to check potential repeats that include the top of stack. This gets us down to $O(n^2)$ in the size of the stack per push.

Some (terrible) Python pseudocode for this approach, to illustrate (again: this code is just to illustrate. Please don't focus on the exact code.)

```
def push(s, x):
    s.append(x)
    for i in range(1, len(s)//2 + 1):
        # this comparison is _not_ O(1) time.
        if s[-2*i:-i] == s[-i:]:
            ret = s[-i:], len(s)-2*i, len(s)-i
            s.pop()
            return True, *ret
    return False, None

def pop(s):
    return s.pop()

def check(act, exp):
    assert act == exp, (act, exp)

s = []
check(push(s, "A"), (False, None))
check(push(s, "B"), (False, None))
check(push(s, "A"), (False, None))
check(s, ["A", "B", "A"])
# ABAB would have a repeated subsequence AB AB
check(push(s, "B"), (True, ["A", "B"], 0, 2))
check(pop(s), "A")
# ABB would have a repeated subsequence B B
check(push(s, "B"), (True, ["B"], 1, 2))

```

(Worst-case complexity here is $\sum\_{i=1}^{n/2 + 1}i$, which is $O(n^2)$. Best-case for a successful push is if each array comparison compares one element and then short-circuits, which works out to $O(n)$. \[n.b. I know that CPython's array comparison with slices I showed doesn't actually work that way.\] Best-case for an unsuccessful push is, of course, $O(1)$.)

Is there a way of doing better here? In particular, is it possible to achieve (amortized) worst-case complexity for pushes that is sublinear in the size of the stack?

# Answer
> 4 votes
Kosolobov \[1\] solved this exact problem. The first algorithm in the paper supports stack operations on a string while detecting a repeated substring, and each operation takes amortized $O(\log m)$ time where $m$ is the maximum string length so far.

The algorithm works for unordered alphabets (only equality comparison between characters are allowed), and the time complexity is essentially optimal in this setting because detecting a repeated substring requires $\Omega(n \log n)$ time for unordered alphabets \[2\].

* \[1\]: Kosolobov, Dmitry. "Online detection of repetitions with backtracking." Annual Symposium on Combinatorial Pattern Matching. Springer, Cham, 2015. https://arxiv.org/abs/1412.4471
* \[2\]: Main, Michael G., and Richard J. Lorentz. "An O(n log n) algorithm for finding all repetitions in a string." Journal of Algorithms 5.3 (1984): 422-432.

---
Tags: time-complexity, data-structures, asymptotics
---


# Question
Title: Sieve of Eratosthenes for factorization: bitwise complexity?
As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum\_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, whether one uses it for finding the primes up to $N$ or for factoring the numbers up to $N$. It is also well-known that the number of bit operations required by the sieve of Eratosthenes to find the primes up to $N$ is $O(N \log N \log \log N)$, assuming, that is, that accessing a bit in an array of size $N$ takes time $O(\log N)$.

It seems to me that the number of bit operations required by the sieve of Eratosthenes to factor the integers from $1$ to $N$ is also $O(N \log N \log \log N)$ (unless one goes about things in a deliberately stupid way - doing the multiplication at the end by multiplying by your large primes before multiplying by your small primes, say; but nobody would do that).

(Here I am assuming something that was long suspected and recently proved, viz., that two $n$-bit numbers can be multiplied in time $O(n \log n)$ (Harvey-van der Hoeven).)

Am I right, or have I overlooked something? Is there a standard reference (or is this too obvious to be written down)?

# Answer
> 1 votes
Newer multiplication algorithms aren't needed to show such a time bound in this model.

Given a precomputed multiplication table of size $O(p)$, multiplication $a \times b$ of $a, b \leq p^{O(1)}$ takes a constant number of additions and table accesses. For example, let $p = \Theta(N^{1/3})$ then the pre-computation step takes $o(N)$ time and a multiplication takes $O(\log N)$ time.

The division is similar and can be assumed to take $O(\log N)$ time after a precomputation. Therefore, even using a naive repeated division like `while x != 1: x := x / factor[x]`, it is possible to factor all integers up to $N$ in $O(N \log N \log \log N)$ time.

---
Tags: time-complexity, runtime-analysis, reference-request, number-theory
---


# Question
Title: How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?
I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example Bubblesort, and then optimize parts of the code to end up with Quicksort or MergeSort… Is it even possible?

Or it’s the case that going from Bubblesort to Quicksort such a large conceptual leap that there isn’t really a way to “meta-explain” what is the thinking process to go from one to the other?

Another way to put this is: Is there an meta-algorithm to make an algorithm like Bubblesort become an algorithm like Quicksort? Or this still understood so poorly that all we can say is: give the problem to a planet full of human neural networks and wait some years?

I wonder if the way to find out would be to start with the slowest possible algorithm: reorder the list in all possible arrangements, select the one that is ordered and from there look for ways to add constraints to be more efficient… perhaps using something like miniKanren relational programming…

# Answer
Algorithm design is known to be an art. There is no magical recipe. It all depends on the mathematical properties of the problems addressed.

In the case of sorting, the designers were helped by a few theoretical considerations:

* there are $n!$ ways to permute an array, so any sort that relies on comparisons (each time one bit of information) must perform at least $\lg(n!)\sim n\lg(n)$ comparisons. So there is no point searching for faster algorithms.
* finding the rank (sorted position) of every element allows you to identify the permutation; this can be done by comparing every element to every other, which takes $\sim n^2$ comparisons.
* among the $n^2$ comparisons, many are redundant due to the transitivity property ($a\<b\land b\<c$$\implies a\<c$). This gives hope for $o(n^2)$ solutions.

These a priori complexity results serve as guides for algorithm design and tell you how close you are from a good solution.

Now two general techniques can be tried:

* *incremental processing*: assuming you sorted the $m$ first elements, what does it take to sort the $m+1$ first elements ? (insert the new element at the right place $\to$ StraightInsertionSort); or assuming you sorted the $m$ *smallest* elements, which comes next ? (take the smallest of the remaining elements $\to$ StraightSelectionSort).
* *divide & conquer*: assuming you can sort independently the first halve and second halve of the array, what does it take to obtain the fully sorted array ? (perform a merge operation $\to$ MergeSort); or, assuming that you can presort the array in such a way that the first elements are smaller than the last elements, what does it take to get the fully sorted array ? (the first operation is called a partition; after the partition, it suffices to concatene the sorted subsequences).

It turns out that incremental processing yields simple but $O(n^2)$ algorithms, while D&C results in $O(n\log(n))$ for MergeSort (but requires an extra array), and $\Omega(n\log(n))/O(n^2)$ for Quicksort (so is not optimal, but fast in practice anyway).

None of these algorithms are perfect. There is another, which does not fall in the above categories and relies on an unexpected concept: the heap. This is a special data structure which consists in an implicit binary tree with an order relation between the keys. And it turns out that building a heap takes $O(n)$ time, and extracting the smallest element $\lg(n)$ time at worst. This gives birth to HeapSort, a good algorithm with guaranteed $O(n\lg(n))$ behavior.

There is much more to say about sorting and algorithm design. The morale is that there are general principles, but creativity is still required.
> 5 votes

# Answer
No matter how much one optimizes its code, a bad algorithm will always be bad. The key to great software is starting with a great algorithm.

What distinguishes an algorithm is something that makes it fundamentally different from other algorithms. Iteratively improving an algorithm will never result in something that is fundamentally different.

Consider an extreme example.
The best theoretically possible algorithm will require *n*×log(*n*) comparisons. But if the comparison keys are dense enough (or if they can hash to numbers that are dense enough), they can be sorted with a *linear* order algorithm (radix sort), which is significantly better than *n*×log(*n*).
There is no way anyone can start with a comparison sort and gradually improve it into a radix sort; the two algorithms are so fundamentally different.
> 2 votes

# Answer
Bubblesort to Quicksort requires some cleverness, but is a quite natural progression.

First, you implement Bubblesort, and you find that for 100,000 random items it is indeed very slow. 100,000^2 operations. You'll find easily that if you split the array into two groups of 50,000, sort both and merge the results, you only need 50,000^2 * 2 + 100,000 or so operations which is almost twice as fast. And then obviously you sort a 50,000 item array by splitting it into two parts of 25,000. And if you follow this down and measure, you'll find that for some rather small n the bubble sort is actually faster. Now we've got merge sort.

Mergesort is actually already optimal in Big-O notation, but making an algorithm twice or three times as fast is still worthwhile. So we would analyse what's bad about merge sort, and it is mostly the fact that we need additional memory. Swapping elements doesn't require more than constant additional memory. Figuring out the Quicksort partition algorithm is difficult, but possible enough.

When you examine Quicksort more closely, two annoying things are the worst case which you fix by randomising the pivot, and the fact that it doesn't take advantage if the data is already sorted or mostly sorted.

Some implementations now check how many initial elements are in either ascending or descending order, and how many elements at the end are in either ascending or descending order. And if the numbers are significantly high compared to the total number of items (say large compared to n / log n) we can sort the unsorted items and then do one or two merges. This will be linear if we combine two sorted arrays, or if we take a sorted array with just one change, or a sorted array with O (n / log n) items appended, and usually be an improvement if we take a sorted array with two or three changes. (And the check is very fast if it doesn't gain anything).

Another implementation assumes that your array was created by starting with a sorted array, and adding / removing / appending / changing a few values, fewer than O (n / log n). Here we can remove all the items that are not in sorted order, sort them separately, then merge. This also works well if you take an array containing a million names, sorted correctly according to one of the official German sorting orders, and sorting it according to the official Swedish sorting order.

The last two changes are both quite natural.
> 2 votes

# Answer
I agree that there is no recipe and others provided insight on how matters evolved or can evolve. A key aspect hindering the design of your "meta-algorithm" is a lack of "modularity" in Computer Science. The theory of algorithm design (and analysis) is not on par with say civil engineering, for which automation is more advanced. Newton's calculus supports the prediction of properties of a bridge from the blue-prints. Hence such projects can be designed and analysed in a modular fashion (properties of the materials lead to a prediction of properties of the end product).

In CS, design and analysis techniques are tailored to particular algorithms/problems as opposed to being based on a single foundational theory. In many cases there are infinitely many inputs, each of which could change the execution behaviour in a different way. Modularity is not guaranteed (i.e. the design and analysis of parts of the code does not guarantee control/predictability of the design and analysis of the whole).

Computer science faces a hurdle on that front since all parts interact in a multitude of ways (input-dependency) and is not yet at the stage where your question can be fully answered. The field is less than 100 years old (as a science). Other fields, in comparison, have been developed for millennia (though of course computation has been around for a lot longer than the advent of computers).
> 1 votes

# Answer
The other answers here explain very well the mathematical idea and thought process to come up with a sorting algorithm, there might be cases where even the "most optimal" algorithm you have, may not deliver the performance you expect. Of course they all sort so they are correct, but in practical scenarios, lower execution times(time and space complexities)are desirable. Often, algorithms are "combined" resulting in a hybrid implementation, which performs better than any algorithm alone. The choice of algorithms to pick depends on the nature of data and empirical results.

An example: Combining merge sort and insertion sort is helpful as for fewer values and completely/nearly sorted data, insertion sort performs better than merge sort. So you can perform merge sort, and once the sub problem size becomes reasonably small, you can use insertion sort.

Notable examples implementing these ideas are Timsort and Introsort.
> 0 votes

# Answer
And here is my meta-algorithm for creating fast algorithms and fast implementations of algorithms:

Step 1: Create a working algorithm.

Step 2: Run the algorithm and figure out what bits run slower than you think they should. At this point you also understand the problem better.

Step 3: With your better understanding of the problem, and your knowledge what makes your current algorithm slower than it should be, create a new algorithm and go back to Step 3.

You stop when you think your benefits from a faster algorithm don't outweigh the cost of creating a faster algorithm anymore. You may continue if you find common situations that you might be able to solve much faster than the general case. It's pointless to optimise for the worst case if the worst case never happens for problems that people actually try to solve.
> 0 votes

# Answer
I'm going to pull my answer from the book *Introduction to the Design and Analysis of Algorithms* by Anany Levitin. Anything in blockquotes is directly from the book. Here's the steps he gives in the book:

**1. Understanding the Problem**

> Read the problem’s description carefully and ask questions if you have any doubts about the problem, do a few small examples by hand, think about special cases, and ask questions again if needed.

**2. Choosing between Exact and Approximate Problem Solving**

> The next principal decision is to choose between solving the problem exactly or solving it approximately. In the former case, an algorithm is called an exact algorithm; in the latter case, an algorithm is called an approximation algorithm. Why would one opt for an approximation algorithm? First, there are important problems that simply cannot be solved exactly for most of their instances; examples include extracting square roots, solving nonlinear equations, and evaluating definite integrals. Second, available algorithms for solving a problem exactly can be unacceptably slow because of the problem’s intrinsic complexity. This happens, in particular, for many problems involving a very large number of choices...

**3. Design an algorithm**

Describe the algorithm, usually using pseudocode.

**4. Proving an Algorithm's Correctness**

> Once an algorithm has been speciﬁed, you have to prove its correctness. That is, you have to prove that the algorithm yields a required result for every legitimate input in a ﬁnite amount of time. For example, the correctness of Euclid’s algorithm for computing the greatest common divisor stems from the correctness of the equality gcd(m, n) = gcd(n, m mod n)

**5. Analyze the Algorithm**

Measure how well the algorithm performs. There are several qualities to keep in mind:

* **Time efficiency** (how fast the algorithm runs)
* **Space efficiency** (how much extra memory it uses)
* **Simplicity** (how simple it is; simple algorithms tend to have less errors)
* **Generality** (how general the algorithm is and the set of inputs it accepts)

> If you are not satisﬁed with the algorithm’s efﬁciency, simplicity, or generality, you must return to the drawing board and redesign the algorithm. In fact, even if your evaluation is positive, it is still worth searching for other algorithmic solutions.

**6. Code the algorithm**

Finally code the algorithm. Make sure to test to make sure it's working properly.

*"Okay this is fine and dandy, but that still doesn't answer the question about how we got from Bubble Sort to something like Quicksort"*

It's a fact that an array grows, the time to sort doesn't grow linearly, but *exponentially*. What we realized was that partitioning the array into smaller sub-arrays, sorting those sub-arrays, then recombining them resulted in a massive speedup. This is basically what algorithms like Merge Sort and Quicksort is doing.
> 0 votes

---
Tags: algorithm-analysis, logic, sorting, constraint-satisfaction, program-optimization
---


# Question
Title: Why does the order of the nested loops matter when solving the Coin Change problem?
The Coin Change problem is stated as:

> Given an integer array coins\[ \] of size N representing different denominations of currency and an integer sum, find the number of ways you can make sum by using different combinations from coins\[ \].
> Note: Assume that you have an infinite supply of each type of coin.

So for example using coins {1, 2, 3} and a desired sums of 3, yields combinations (1,1,1), (1,2) and (3).

This problem can be solved using dynamic programming where the idea is to iteratively count the the number of combinations that can amount to a partial sum:

```
    std::vector<int> combinations_to_consume_sum(sum + 1, 0);
    combinations_to_consume_sum[0] = 1; // if we got here, we consumed everything using a single coin

    for (int i = 0; i < N; ++i) // go through each coin
    {
        int coin = coins[i];

        for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)
        {
            int leftover_sum = partial_sum - coin;

            if (leftover_sum >= 0)
            {
                combinations_to_consume_sum[partial_sum] += combinations_to_consume_sum[leftover_sum];
            }
        }
    }
    return combinations_to_consume_sum[sum];

```

This is a working solution. However, if I swap the order of the 2 nested loops, the algorithm is no longer correct:

```
    for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)
    {
        for (int i = 0; i < N; ++i)
        {
            int coin = coins[i];

            int leftover_sum = partial_sum - coin;

            if (leftover_sum >= 0)
            {
                combinations_to_consume_sum[partial_sum] += combinations_to_consume_sum[leftover_sum];
            }
        }
    }
    return combinations_to_consume_sum[sum];

```

Can someone offer an explanation as to why this approach only works when using a 'coins first' approach?

# Answer
> 11 votes
In the second solution you are overcounting the number of combinations. In fact you are counting the of ways to choose an **ordered** list of coins that sums to `sum`.

For example suppose that you have coins of values $1$ and $2$.

* There is only one way to obtain a sum of $0$, namely using no coins and the algorithm computes this correctly.
* There is only one way to obtain a sum of $1$, and the algorithm computes this correctly (by "using" coin $1$ and looking at the number of ways to use $0$ coins to obtain a sum of $0$).
* There are two ways to obtain a sum of $2$, namely using two $1$ coins or a single $2$ coin. The algorithm also happens to compute this correctly by summing the $1$ way to obtain a sum of $1$ (when the $1$ coins is used) with the $1$ way to obtain a sum of $0$ (when the two coin is used).
* There are two ways to obtain a sum of $3$, namely using three $1$ coins or a $1$ coin and a $2$ coin. The algorithm fails here as it considers:
    + The **two** ways to obtain a sum of $2$ (after the $1$ coin is used). These are $(1,1)$ and $(2)$. This case accounts for the following ways to obtain a sum of $3$: $(1,1,1)$, and $(1,2)$.
    + The **one** way to obtain a sum of $1$ (after the $2$ coin is used). This is $(1)$. This case accounts for the following way to obtain a sum of $3$: $(2,1)$.

As you can see, the option of using a $2$ coin and a $1$ coin is counted twice (in the two different possible orders).

# Answer
> 6 votes
#### Why is the working solution correct?

First things first. Important things first. Let us understand why the working solution is correct first instead of finding where the wrong solution goes wrong.

Here is a solution that is easier to understand.

Introduce a 2-dimensional variable `combinations` so that `combinations[i+1][s]` will be the number of combinations of coins with values in `coins[0..i]` that sum up to `s`.

```
 1    std::vector<vector<int>> combinations(N, vector<int> (sum + 1, 0));
 2    combinations[0][0] = 1; //no coin. zero sum. This is one combination.
 3
 4    for (int i = 0; i < N; ++i) // go through each coin
 5    {
 7        int coin = coins[i];
 8
 9        for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)
10        {
11            int leftover_sum = partial_sum - coin;
12
13            if (leftover_sum >= 0)
14            {
15                combinations[i + 1][partial_sum] =
                          combinations[i][partial_sum]
                          + combinations[i + 1][leftover_sum];
16            }
17        }
18    }
19    return combinations_to_consume_sum[sum];

```

A combination of coins from `coins[0..i]` that sum to `partial_sum`

* either does not contain `coins[i]`, which means it is a combination of coins with values in `coins[0..(i-1)]` that sum to `partial_sum`
* or contain `coins[i]`, which means it is
    + a coin with value `coins[i]`
    + together with a combination of coins with values in `coins[0..i]` that sum to `partial_sum - coins[i]`, which is stored in `leftover_sum`.

Hence we have the recurrence relation on line 15 of the code above. Also note that at the moment when we run line 15, all terms on the right-hand side has been settled:

* the term `combinations[i][partial_sum]` is settled since `i < i + 1`
* the term `combinations[i + 1][leftover_sum]` is settled since `0 <= leftover_sum < partial_sum`.

Hence after line 15, `combinations[i + 1][partial_sum]` is settled.

The working solution in the question is the condensed version of the solution above. Instead of a two-dimensional `combinations`, we use a one-dimensional vector `combinations_to_consume_sum`, which functions exactly the same.

#### What is computed by the incorrect solution?

Steven's answer explains why the incorrect solution is wrong. Basically, it can count the same combination more than once. For example, when `coins` is `{2, 3}` and `sum` is 5, it will count $(2, 3)$ once and $(3,2)$ once, although they are the same combination.

In fact, the incorrect solution computes the number of different sequences of coins whose values are in `coins` and whose sum is `sum`. When there is at least one combination of different values that sum to `sum`, the incorrect solution will return a number that is larger than the number of combinations wanted.

#### Two exercises

1. If the values in `coins` are not necessarily different, explain what is computed by the first solution in the question. What is computed by the second solution?

2. What is computed by the first solution in the question if `for (int partial_sum = 1; partial_sum <= sum; ++partial_sum)` is replaced by `for (int partial_sum = sum; partial_sum >= 1; --partial_sum)`? What about the second solution?

---
Tags: algorithms, dynamic-programming, arrays, coin-change
---


# Question
Title: Count substrings with same first and last characters
We are given a string S, we need to find count of all contiguous substrings starting and ending with same character.

Examples :

Input : S = "abcab"
Output : 7
There are 15 substrings of "abcab"
a, ab, abc, abca, abcab, b, bc, bca
bcab, c, ca, cab, a, ab, b
Out of the above substrings, there
are 7 substrings : a, abca, b, bcab,
c, a and b.

Input : S = "aba"
Output : 4
The substrings are a, b, a and aba

a) One approach would be to use brute force, (O(n^2)) approach where check for each substring and increment count
Please suggest optimal solutions

# Answer
You can do it in linear time. Loop over the characters of the string and count the frequency (how many times it appears in the string) of each distinct character. Then if a character has a frequency $n$ then the count of all contiguous substrings starting and ending with same character is $\frac{(n+1)n}{2}$ and finally sum up all counts.

Example 1: $abcab$.
Frequencies: $f(a)=2, f(b)=2, f(c)=1$.
Counts: $3,3,1$ which gives $7$.

Example 2: $aba$.
Frequencies: $f(a)=2, f(b)=1$.
Counts: $3,1$ which gives $4$.

Example 3: $aaa$.
Frequencies: $f(a)=3$.
Counts: $6$ which gives $6$.

Example 4: $abc$.
Frequencies: $f(a)=1, f(b)=1, f(c)=1$.
Counts: $1,1,1$ which gives $3$.

NOTE: $n\*(n+1)/2$ is deduced this way:

Suppose you have this string $abcaba$ where first $a$ can be matched with second a at index 3 (0 indexed array) and also third $a$ at index 5.

frequency of $a$ is 3 so for first $a$ we will get 3-1 = 2 continuous substrings.

for second a we get 2-1 = 1 continuous substring

We are seeing a pattern as this: n,n-1, n-2.....0

This leads to the formula n\*(n+1)/2 as we also need to consider individual $a$'s.

2 + 1 + 3 times $a$ = 6

Same is true for other characters in the string.
> 3 votes

# Answer
Create a dictionary for storing number of substrings starting and ending with this character. Iterate through the string and calculate the result accordingly — for each character you know how many substrings are there already starting (and ending) with this character so you can calculate next state. Finally, you just need to sum the values.

This gives $O(n)$ if using dictionary with $O(1)$ inserts and updates.
> 0 votes

# Answer
public static int countSubstrs (String str, int i, int j, int n) {

```
if (n == 1) {

return 1;
}

if (n <= 0) {

return 0;

}
int res =   countSubstrs (str, i + 1, j, n -1) +

              countSubstrs(str, i, j-1, n-1) -

               countSubstrs (str, i + 1, j-1, n-2);

if (str.charAt(i) == str.charAt(j)) {

res++;
}
return res;

```

}
> 0 votes

---
Tags: algorithms, strings
---


# Question
Title: Is there a possibility to convert the following problem into divide and connquer
$A$ is a $m\*n$ matrix
$B$ is an $n\*n$ matrix

I want to return matrix C of size m\*n such that:
$C\_{ij} = \sum\_{k=1}^{n} max(0, a\_{ij} - b\_{jk}) $

In pseudocode it could be like below

```
for i = 1 to m:
   for j = 1 to n:
      C[i,j] = 0
      for k = 1 to n:
         C[i,j] += max(0, a[i,j] - b[j,k])

```

this runs on $O(m\*n^2)$ but it is possible to lower that.

# Answer
> 1 votes
We can note that to compute $C\_{ij}$, it is enough to know the sum, and the count of $\\{b\_{jk}\\}\_{k=1}^n$ such that $b\_{jk} \< a\_{ij}$. This can be done after a simple preprocessing and the final time complexity will be $O(mn\log{n})$

---
Tags: algorithms, time-complexity
---


# Question
Title: Name of a packing problem similar to this?
I couldn't search much about a problem I have.

There is a 1D array of zeros and ones. The objective is to pack all ones with the least number of containers. Each container is variable in length but has a maximum length limit. Items in array cannot be moved.

For example, if the max length limit is 5, I would pack ones like:

I could only come up with a greedy solution, but I would like to know if there's an always-optimal one. I would appreciate your comments.

# Answer
I don't know what your greedy solution is, but there is an easy greedy solution (here I denote $L$ the max length of a container):

```
Input: array of length n

i ← index of the first 1
while i < n do
   create a container starting at i of length max(L, n - i)
   i ← next 1 after index i + max(L, n - i)

```

Its complexity is linear in $n$, the length of the array. It is not quite difficult to see that it is optimal (the first 1 must be in a container, and we lose nothing to make that container the largest possible; that way the next created container can only be farther than in another solution, and so on).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Construct an objective function that favors the sorted permutation
I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (ones that have a binary answer). I know that any optimization problem can be turned into a decision problem by imposing a threshold on the objective function (and asking if it is greater than the threshold). So, I'm trying to find a way to convert the sorting problem into an optimization problem. Ideally, the best way to get the answer to this optimization problem should be to just sort the array.

It becomes like a mathematical problem of constructing an objective function that favors one particular permutation.

My attempts: One objective function might involve looping through the array and adding $1$ to the objective function if the successive element is larger than the current one. This does have the largest value when the array is sorted. However, one doesn't have to sort the array to get the best value of this function (simply count the entries in the array). The possibility of the array having duplicate entries can make it a little interesting, but one can still just store the distinct entries and their counts in a dictionary and get the objective function without sorting the array.

Another possibility is to loop through the array and add the difference between the next element and current one to the objective function. This seems more promising and coming up with the best objective function should require us to sort the array. But I don't have a proof for this.

# Answer
> 2 votes
I don't understand why you seem to want that computing the best value of the objective function must require sorting the array. In optimization problems (look for example at the class $\mathsf{NPO}$), the problem is that of computing an optimal solution (and not just the optimal value of the objective function).

That said, it is easy to build a trivial "artificial" objective function $f$. A feasible solution a permutation $\pi$ of the sequence $S$ of input elements. Define $f(\pi)$ to be $1$ if permuting $S$ according to $\pi$ yields a sorted sequence, and $0$ otherwise.

Perhaps a more natural objective function (to minimize) would be the number of inversions in the permuted version $\pi(S)$ of $S$. Here an inversions is a pair of distinct indices $i,j$ with $i\<j$ such that the $i$-th element in $\pi(S)$ is larger than the $j$-th element in $\pi(S)$. Informally, an inversion is an unordered pair of (not necessarily adjacent) elements in the wrong order. This is also known as the Kendall tau rank distance (between $\pi(S)$ and the sorted version of $S$).

Regarding your proposed objective function, notice that it is a telescopic sum and hence its value depends only on the first and last elements of the sequence. To know its optimal value you only need to compute the minimum and the maximum in $S$.

---
Tags: np, arrays, permutations
---


title: Show that $TIME(\sqrt{n})$ = $TIME(1)$

text:
# Question
Title: Show that $TIME(\sqrt{n})$ = $TIME(1)$
Also known as CMU 15-455, Spring 2017, Homework 2.4.

Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n))$.

* **Definition:** Let $f$ and $g$ be functions $f$, $g$: $\mathbb{N}$ $\rightarrow$ $\mathbb{R}^+$. Say that $f(n)$ = $O(g(n))$ if $\lim\_{n \to \infty}\dfrac{f(n)}{g(n)}$ = 0. In other words, $f(n) = O(g(n))$ means that for any real number $c$ \> 0, a number $n\_0$ exists, where $f(n)$ $\leq$ $cg(n)$ for all $n \geq n\_0$.
* **Definition:** Let $t: \mathbb{N} \rightarrow \mathbb{R}^+$ be a function. Define the time complexity class, $TIME(t(n))$, to be the collection of all languages that are decidable by an $O(t(n))$ time Turing machine.

By definition, $TIME(\sqrt{n})$ and $TIME(1)$ are the collection of all languages that are decidable by a $O(\sqrt{n})$ and a $O(1)$ time TM respectively. My approach is the following:

**Proposition:** $TIME(1)$ is the collection of all languages that are decidable by an $O(\sqrt{n})$ time Turing machine.

If the above proposition is true, it should be sufficient to prove that $TIME(\sqrt{n})$ = $TIME(1)$. If the runtime is a constant $c$, then we can use the runtime $O(1)$ to represent $c$. Let $c = 1$ as an example. Obviously, $1$ = $O(1)$. We wish to show that $1$ = $O(\sqrt{n})$ as well.

By the definition of big-$O$, we have to prove that $\lim\_{n\to\infty} \dfrac{1}{\sqrt{n}} = 0$, which is true. As such, $1$ = $O(1)$ = $O(\sqrt{n})$. As $TIME(1)$ is the collection of all languages that are decidable by an $O(1)$ time TM, and $O(1)$ = $O(\sqrt{n})$, the above proposition is proved. Hence $TIME(\sqrt{n})$ = $TIME(1)$.

The proof looks sound to me. However, upon further inspection, I have some problems with it:

1. The reverse approach, $TIME(\sqrt{n})$ is the collection of all languages decidable by an $O(1)$ time TM does not seem to work. Because if I understand the definition of big-$O$ correctly, are we trying to assert that $\sqrt{n}$ = $O(\sqrt{n})$ = $O(1)$? Then $\sqrt{n}$ = $1$, which is not true? What did I get wrong?
2. How can we show that $1 = O(1)$ with the definition of big-$O$ above? $\lim\_{n\to\infty} \dfrac{1}{1} = 1 \neq 0$. And if we use the second version of the definition, what if $0 \leq c \leq 1$?

Those are my main question. In the case my approach is wrong, how will you approach it?

# Answer
> 1 votes
Suppose that a Turing machine runs in time at most $T(n)$ on inputs of length $n$, where $T(n) = o(n)$. Therefore $\lim\_{n\to\infty} T(n)/n = 0$, and so we can find $N$ such that $T(n) \< n$ for $n \geq N$.

Let $x$ be an input of size at least $N$, and let $y$ be the first $N$ symbols of $x$. If we run the Turing machine on $y$ then it halts in fewer than $N$ steps, and in particular, it doesn't reach end of the input. Therefore the Turing machine behaves exactly the same on $x$ and on $y$, and consequently, the running time on $x$ is also at most $T(N)$. Therefore the Turing machine halts on all inputs in time at most $\max(T(1),\ldots,T(N))$.

If instead of a Turing machine we had a random-access machine, then running times smaller than the input length do make sense. In such a setting, machines running in time $O(\sqrt{n})$ are indeed more powerful than those running in constant time.

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: Examples of problems in NP but not in P which we haven't proved NP complete
If we find a problem we know for sure is in NP but not in NP-complete or P, we'll have proved P!=NP. One approach then is to identify problems in NP (but not P) we haven't been able to show to be NP-complete so far and try to prove they aren't in that set. Any examples of such problems? Preferably one problem per answer?

# Answer
The language constructed in the proof of Ladner's Theorem.

See also the Wikipedia page on the NP-intermediate class, which contains a list of problems that might be in NP-intermediate.
> 2 votes

---
Tags: complexity-theory, np-complete, np
---


# Question
Title: Best known deterministic algorithm for generation of any (non random) n-bit prime?
Sometimes we need some prime number with certain minimum size for modular algorithm.

For practical purposes we can precompute (using fast randomized algorithms) table of some primes for range which makes sense in application.

However I'm interested how fast *theoretically* (in terms of time complexity on $n$) we can find some prime with at least $n$ bits? It shouldn't be random, just any prime which we deterministically can find.

Just checking all numbers above $2^n$ with AKS test will do the job, but I feel better can be done, but using numbers of specific form, for which fast deterministic test is known.

# Answer
In practice, you should absolutely use a randomized algorithm. There is no reason in practice to use a deterministic algorithm, or to care about the complexity of deterministic algorithms.

So I will assume that you are asking only out of theoretical interest. In that case, a reasonable approach is to start with the minimum number $m$, and then search over $m+1,m+2,m+3,\cdots$ until you find the first prime number, using a deterministic primality test. If you are willing to make certain number-theoretic conjectures (e.g., Cramer's conjecture, generalized Riemann hypothesis), then this runs in $O((\log m)^6)$ time (ignoring log log factors), as you only need to explore $O((\log m)^2)$ many values until you find the first prime, and you can test for primality using the deterministic Miller's test in $O((\log m)^4)$ time per test.

If you're not willing to make any number-theoretic conjectures, and you want a deterministic algorithm with provable worst-case running time, I'm not aware of any result that proves the problem can be solved in polynomial time (i.e., polynomial in $\log m$).

Again, I emphasize that if you actually want to implement this, don't use any of those deterministic algorithms. Instead, use a randomized primality test.
> 1 votes

---
Tags: time-complexity, reference-request, primes
---


title: Complete Binary Tree

text:
# Question
Title: Complete Binary Tree
R C Lacher's definition:

> A binary tree is complete iff the only vertices with less than two children are in the bottom two layers.

Paul E. Black's definition:

> A binary tree in which every level (depth), except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

Which one is more accurate?

I know these definitions can vary from author to author, but what could be the underlying philosophy for this variation?

# Answer
> 1 votes
Let's consider Paul E. Black's definition. As per that,

```
              This is a complete binary tree                 This is not
                            2     ---------depth 0---------       2
                          /   \                                 /   \
                         1     3  ---------depth 1---------    1     3
                       /  \   /                              /  \     \
                      4    5 8    ---------depth 2--------- 4    5     8
                        tree 1                                tree 2

```

but as per R C Lacher's definition, they both are valid. If a definition is to be followed, I'd say follow the one which is more strict, as it leaves less room for ambiguity in understanding it. When you say the elements are a filled as left as possible you get only $1$ tree(in terms of positions of nodes) but if you allow freedom at the last level, where you have $n$ positions and $k$ nodes, you have $\binom{n}{k}$ complete binary trees.

As for the philosophy, I believe Paul's definition seems more relevant to suit to the array representation of a binary tree. Where you perform the level order traversal of the tree and store the elements sequentially in an array. If you try to store a tree following Lacher's definition, chances are you'll end up having empty slots in the array representation, which isn't a good thing for arrays.

---
Tags: binary-trees
---


# Question
Title: In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?
Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?

# Answer
Let $c \in (0, \frac{1}{2}\]$ be any constant. In your case $c = \frac{1}{4}$.

If, at a generic recursive call, you partition the $n$ elements in your input array into a subarray of size $cn$ and another of size $(1-c)n$ (floors and ceilings are omitted for simplicity here), you can describe the running time of mergesort with the following recurrence equation:

$$ T(n) = T(cn) + T((1-c)n) + O(n). $$

The solution to this recurrence is $T(n)=O(n \log n)$.

To see this, consider the recursion tree. If $n$ is the size of the original input, then the largest input size of a call at depth $d$ is at most $(1-c)^d n$. By solving $(1-c)^d n \ge 1$ for $d$, we see that there can be at most $\log\_{1-c} \frac{1}{n} = \dfrac{\log \frac{1}{n}}{\log (1-c)} = \dfrac{\log n}{\log \frac{1}{1-c}}$ levels of recursion.

Notice now that the input sizes on each level of recursion cannot sum to more than $n$, therefore the overall time spent on each level is at most $O(n)$, and the running time of the algorithm is at most $O(n) \cdot \dfrac{\log n}{\log \frac{1}{1-c}} = O(n \log n)$.
> 1 votes

---
Tags: algorithms, time-complexity, recurrence-relation, divide-and-conquer, mergesort
---


# Question
Title: BNF and EBNF Syntax for while loops in C#
Given the programming language C#, how would I be able to write the BNF and EBNF grammar syntax of its while loop?

After trying to search and understand more, I got this as my BNF grammar for while loops

\< while-statement \> :: = \< do-statement \>\< while-statement \> | \< do-statement \>

though I don't think it's quite right

# Answer
The common element in "while statements" and "do statements" is the continuation condition, which is an expression inside parentheses, always indicated with the keyword `while`. If you wanted to, you could capture this commonality with something like:

```
<while-clause> ::= "while" "(" <expression> ")"
<while-statement> ::= <while-clause> <embedded-statement>
<do-statement> ::= "do" <embedded-statement> <while-clause> ";"

```

I'm not sure whether that adds any readability to the grammar. The actual C# grammar doesn't bother; it just uses

```
<while-statement> ::= "while" "(" <expression> ")" <embedded-statement>
<do-statement> ::= "do" <embedded-statement> "while" "(" <expression> ")" ";"

```

Thanks to @JörgWMittag for the above link, in which you have to search for `while_statement` because the productions aren't tagged. Also see the specification text.

Either way, the productions simply reflect the evident syntax. At a high level, you can get surprisingly far into the writing of a grammar by just explaining the construct in your own language. ("A *while statement* starts with the keyword `while`, followed by the continuation expression surrounded by parentheses, and then the statement to be iterated.")

The only subtlety here is the use of `<embedded-statement>` instead of, say, `<statement>`. That's because C#, like C and other C-derivatives, doesn't permit embedded statements to be declarations or to have labels. (If you want to do that, you'd need to embed a "block" (that is, a list of statements inside `{``}`).
> 1 votes

---
Tags: formal-grammars, c
---


# Question
Title: i am solving a question related to bfs traversal and there i got this doubt so can anyone plz solves this doubt?
if a BFS is applied on a graph is it necessary that the resultant BFS tree contains all the edges that are in the original graph ?

# Answer
> 1 votes
No, you can check how the BFS algorithm works: if an edge $(u,v)$ is examined and $v$ has already been discovered, then $(u,v)$ won't be in the BFS tree.

Besides, as the name suggests, a BFS tree is a tree (and hence acyclic). This means that a BFS on a graph that is cyclic cannot possibly contain all graph edges. Try running a BFS by hand on a triangle graph (i.e., a cycle on $3$ vertices).

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


# Question
Title: Uniformly random connected minimally cyclic graph algorithm
# Background

I'm looking to replicate (as closely as possible) the graphs depicted in this question (in MetaPost).

# Overview

The green edges and large green nodes in the following image depict a graph (the grid and small nodes are irrelevant):

The graph's properties include:

* Connected
* Uniformly random (or nearly so)
* Multiple leaf nodes

Here's another graph, with the same properties, showing a possible cycle, but still looks like it could be directed:

# Requirements

From the graphs, the requirements appear to be:

* There exists one path between any two nodes, with a very low probability of two paths (i.e., few cycles).
* The nodes are randomly and uniformly distributed (i.e., evenly spread over a grid).
* Each node has a maximum of four directly connected nodes.
* Multiple sinks and multiple sources.
* Every node is connected to the graph.

It looks like a uniformly random, connected, acyclic graph. All the algorithms I've looked up, and two that I've implemented, don't generate the vertices and edges necessary to replicate the same properties.

# Questions

What is the full technical name for this type of graph?

What algorithms would be needed to implement it?

---

Here's an example implementation of a connected graph:

```
import java.io.PrintStream;
import java.util.*;

public class ConnectedGraph {
  private final static Random sRandom = new Random();

  private static final class Vertex {
    private final int mId;
    private final int mPosition;
    private final Set<Vertex> mAdjacent = new HashSet<>();

    private Vertex( final int id, final int position ) {
      assert id >= 0;
      assert position >= 0;

      mId = id;
      mPosition = position;
    }

    public void join( final Vertex other ) {
      assert other != null;

      if( mAdjacent.size() < 4 && !equals( other ) ) {
        mAdjacent.add( other );
      }
    }

    @Override
    public boolean equals( final Object o ) {
      if( this == o ) {return true;}
      if( o == null || getClass() != o.getClass() ) {return false;}

      final Vertex vertex = (Vertex) o;

      if( mId == vertex.mId ) {return false;}
      return mPosition == vertex.mPosition;
    }

    @Override
    public int hashCode() {
      int result = mId;
      result = 31 * result + mPosition;
      return result;
    }

    @Override
    public String toString() {
      var sep = "";
      final var sb = new StringBuilder( 32 );

      sb.append( mId );
      sb.append( " -> {" );

      for( final var adjacent : mAdjacent ) {
        sb.append( sep );
        sb.append( ' ' );
        sb.append( adjacent.mPosition );
        sep = ",";
      }

      sb.append( " }" );
      return sb.toString();
    }
  }

  /**
   * Sets the given array to a contiguous sequence of numbers, from 0 to the
   * number of elements in the array.
   *
   * @param a The array to initialize.
   */
  private static void initialize( final int[] a ) {
    assert a != null;
    assert a.length > 0;

    for( var i = a.length - 1; i > 0; i-- ) {
      a[ i ] = i;
    }
  }

  /**
   * Randomly rearranges the values in the given array, based on Richard
   * Durstenfeld's random permutation algorithm. This modifies the array
   * directly.
   *
   * @param a The array to reorder, randomly.
   */
  private static void randomize( final int[] a ) {
    assert a != null;
    assert a.length > 0;

    for( var i = a.length - 1; i > 0; i-- ) {
      final var j = sRandom.nextInt( i + 1 );

      a[ j ] ^= a[ i ];
      a[ i ] ^= a[ j ];
      a[ j ] ^= a[ i ];
    }
  }

  private static List<Vertex> connectize( final int[] positions ) {
    assert positions != null;
    assert positions.length > 1;

    final var vertices = new ArrayList<Vertex>();
    var id = 0;

    for( final var position : positions ) {
      final var vertex = new Vertex( id++, position );
      vertices.add( vertex );

      if( id > 0 ) {
        final var index = sRandom.nextInt( vertices.size() );
        final var adjacent = vertices.get( index );

        vertex.join( adjacent );
        adjacent.join( vertex );
      }
    }

    return vertices;
  }

  public ConnectedGraph() {}

  /**
   * @param n Number of vertices in the graph.
   * @param m Number of edges in the graph.
   * @return Randomly selected vertices.
   */
  public List<Vertex> generate( final int n, final int m ) {
    final var positions = new int[ n ];

    initialize( positions );
    randomize( positions );
    return connectize( positions );
  }

  public void print( final Collection<Vertex> edges, final PrintStream out ) {
    for( final var edge : edges ) {
      out.println( edge );
    }
  }

  public static void main( final String[] args ) {
    final var graph = new ConnectedGraph();
    final var edges = graph.generate( 20, 9 );

    graph.print( edges, System.out );
  }
}

```

Sample output:

```
0 -> { 6, 14, 0 }
1 -> { 4 }
2 -> { 4, 12, 1 }
3 -> { 2, 3, 0 }
4 -> { 0, 9, 0, 19 }
5 -> { 11, 1, 10 }
6 -> { 16 }
7 -> { 12 }
8 -> { 1 }
9 -> { 5, 19 }
10 -> { 17, 12 }
11 -> { 7, 19 }
12 -> { 2 }
13 -> { 13 }
14 -> { }
15 -> { 10 }
16 -> { 1 }
17 -> { 1 }
18 -> { 11 }
19 -> { 4 }

```

Rather, for the first image, the algorithm would produce:

```
(2, 7) -> {(1, 5)}
(1, 5) -> {(6, 7)}
(6, 7) -> {(5, 5), (5, 9), (8, 7)}
(5, 5) -> {(7, 1)}
(8, 7) -> {(9, 9)}
(5, 9) -> {}
etc.

```

Note: The coordinate system doesn't matter.

# Answer
As far as I can tell, if we ignore the cycle, the images are of minimum spanning trees (a weighted, connected, undirected graph). One way to create them follows:

1. Create a uniformly random set of connected edges.
2. Let the weight for each edge be the distance between its vertices.
3. Apply Borůvka's Algorithm to find the minimum spanning tree.
4. Trace the path between connections, applying the grid constraints.

The first three steps can be accomplished in Java as follows:

```
import java.util.*;

import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
import static java.lang.String.format;
import static java.util.Comparator.naturalOrder;

public final class BoruvkaGraph {
  private static final Random sRandom = new Random();

  public record Vertex( int x, int y ) {
    private double distance( final Vertex v ) {
      return sqrt( pow( v.x() - x(), 2 ) + pow( v.y() - y(), 2 ) );
    }

    @Override
    public String toString() {
      return format( "(%2d, %2d)", x(), y() );
    }
  }

  public static final class Edge implements Comparable<Edge> {
    private boolean mVisited;

    private final Vertex mU;
    private final Vertex mV;
    private final double mW;
    private final Queue<Edge> mAdjoined = new PriorityQueue<>( naturalOrder() );

    public Edge( final Vertex u, final Vertex v ) {
      mU = u;
      mV = v;
      mW = u.distance( v );
    }

    public Vertex u() { return mU; }

    public Vertex v() { return mV; }

    public double w() { return mW; }

    public void adjoin( final Edge edge ) {
      if( edge != null ) {
        mAdjoined.add( edge );
      }
    }

    public Queue<Edge> adjoined() { return mAdjoined; }

    public void visited( final boolean visited ) { mVisited = visited; }
    public boolean visited() { return mVisited; }

    @Override
    public int compareTo( final Edge o ) {
      return (int) (w() - o.w());
    }

    @Override
    public String toString() {
      return format( "%s -> %s [%5.2f]", u(), v(), w() );
    }
  }

  public static List<Edge> connected( final int r, final int c, final int m ) {
    final var edges = new ArrayList<Edge>( m );
    Edge prev = null;

    for( var i = m - 1; i >= 0; i-- ) {
      Vertex a = new Vertex( sRandom.nextInt( r ), sRandom.nextInt( c ) );
      Vertex b = new Vertex( sRandom.nextInt( r ), sRandom.nextInt( c ) );

      if( prev != null ) {
        final var v = sRandom.nextBoolean() ? prev.u() : prev.v();

        if( sRandom.nextBoolean() ) {
          a = v;
        }
        else {
          b = v;
        }
      }

      final var edge = new Edge( a, b );

      edges.add( edge );
      edge.adjoin( prev );

      prev = edge;
    }

    return edges;
  }

  private final List<Edge> mEdges;

  /**
   * @param edges A connected graph.
   */
  public BoruvkaGraph( final List<Edge> edges ) {
    mEdges = edges;
  }

  public Collection<Edge> compute( final Edge source ) {
    final var tree = new ArrayList<Edge>();

    source.visited( true );

    for( final var outer : mEdges ) {
      final var inner = outer.adjoined();

      while( !inner.isEmpty() ) {
        final var edge = inner.poll();

        if( !edge.visited() ) {
          tree.add( edge );
          edge.visited( true );
          break;
        }
      }
    }

    return tree;
  }

  public static void main( final String[] args ) {
    final var edges = connected( 20, 20, 40 );
    final var graph = new BoruvkaGraph( edges );
    final var source = edges.get( sRandom.nextInt( edges.size() ) );

    edges.forEach( edge -> edge.adjoined().forEach( System.out::println ) );
    System.out.println( "------------------------" );
    graph.compute( source ).forEach( System.out::println );
  }
}

```

Example output of the minimally spanning tree:

```
( 2,  6) -> (11,  2) [ 9.85]
( 2,  6) -> (11,  7) [ 9.06]
( 2,  6) -> ( 3,  2) [ 4.12]
(18,  2) -> ( 3,  2) [15.00]
(18,  2) -> ( 4, 12) [17.20]
(18,  2) -> (10, 14) [14.42]
(18,  2) -> ( 8,  0) [10.20]
(18,  2) -> ( 6,  8) [13.42]
(17, 10) -> (18,  2) [ 8.06]
(18,  2) -> (19,  7) [ 5.10]
(18,  2) -> (18,  9) [ 7.00]
(18,  9) -> (13,  4) [ 7.07]
( 3, 15) -> (18,  9) [16.16]
( 1,  1) -> ( 3, 15) [14.14]
( 3, 15) -> ( 5, 16) [ 2.24]
( 5, 16) -> (19, 19) [14.32]
( 5, 16) -> (10,  0) [16.76]
( 5, 16) -> (15,  3) [16.40]
( 0, 19) -> (15,  3) [21.93]
(15,  3) -> ( 7,  3) [ 8.00]
( 3,  0) -> ( 7,  3) [ 5.00]
(11, 15) -> ( 7,  3) [12.65]
( 8,  7) -> ( 7,  3) [ 4.12]
( 7,  3) -> (18,  6) [11.40]
(11,  7) -> (18,  6) [ 7.07]
(13, 15) -> (18,  6) [10.30]
(18,  6) -> ( 9,  0) [10.82]
( 3, 11) -> ( 9,  0) [12.53]
( 3, 11) -> (13,  8) [10.44]
(16, 15) -> (13,  8) [ 7.62]
(13,  8) -> ( 3, 14) [11.66]
( 3, 14) -> ( 5, 14) [ 2.00]
( 3, 14) -> ( 1,  7) [ 7.28]
( 1,  7) -> (14,  4) [13.34]
( 6,  5) -> (14,  4) [ 8.06]
( 6,  5) -> ( 6, 19) [14.00]
( 6, 19) -> (18,  1) [21.63]
(18,  1) -> (10,  7) [10.00]

```
> 1 votes

---
Tags: algorithms, graphs, randomness
---


# Question
Title: What is the (intuitive) relation of NP-hard and #P-complete problems?
From Wikipedia on $\mathrm{NP}$-completenes: *"a \[decision\] problem is NP-complete if it is both in NP and NP-hard."* \[link\] I think we can paraphrase this as the first statement:

* An $\mathrm{NP}$-hard (decision) problem $\Pi$ is $\mathrm{NP}$-complete if and only if $\Pi \in \mathrm{NP}$.
* $\\#\mathrm P$-complete (counting) problems are at least as hard as $\mathrm{NP}$-complete problems.

The second statement is from Wikipedia on $\\#\mathrm P$-completeness \[link\].

I think it is fair to conclude that: The two classes of $\mathrm{NP}$-hard and $\\#\mathrm P$-complete cannot intersect, since they are defined for fundamentally different types of problems (counting vs decision). However, the second statements suggests that there *is* a relation between the two. Can this relation be expressed intuitively, like in terms of intersection?

---

After further reading on the $\\#\mathrm P$ class, for which Wikipedia says that it is *"the set of the counting problems associated with the decision problems in the set NP,"* I suspect that the following taxonomy can be established:

Is this correct?

# Answer
The theory of NP-completeness studies *decision problems* and (indirectly) *optimization problems*. In contrast, the theory of #P-completeness studies *counting problems*. In particular, NP is a class of *decision problems* while #P is a class of *counting problems*. The elements of these two classes are different, so you cannot compare them directly as your Venn diagram suggests.

Instead of giving precise definitions of the various types of problems, here are some examples:

* **Decision problem (SAT):** Given a CNF, determine whether it is satisfiable.
* **Counting problem (#SAT):** Given a CNF, determine the number of satisfying assignment.
* **Optimization problem (MAX-SAT):** Given a CNF, determine the maximum number of clauses which can be satisfied simultaneously.

If you can solve #SAT efficiently then you can solve SAT efficiently. This is not an isolated case. Recall that a decision problem $L$ is in NP if there is a polynomial time verifier $V$ and a constant $C$ such that $$ L = \\{ x : V(x,y) = 1 \text{ for some } y \text{ of length at most } C|x|^C \\}. $$ A counting problem $f$ (which maps instances to natural numbers) is in #P if there is a polynomial time verifier $V$ and a constant $C$ such that $$ f(x) = |\\{ y \text{ of length at most } C|x|^C : V(x,y) = 1\\}|. $$ That is, $f(x)$ counts the number of witnesses for $x$. For a given verifier $V$, computing $f(x)$ is harder than deciding whether $x \in L$, since $x \in L$ iff $f(x) \geq 1$.

This suggests that if a decision problem is hard, then its counting version is also hard. The converse is not true. For example, 2SAT (the special case of SAT in which all clauses contain at most two literals) is in P, but its counting version #2SAT is #P-complete.

---

Where do optimization problem fit in? We can think of an optimization problem as given by a verifier $V(x,y)$ which checks whether $y$ is a feasible solution for $x$, together with a function $O(x,y)$ which computes the objective value of $y$. For example, in MAX-SAT, $V(x,y)$ checks that $y$ is a truth assignment for the variables appearing in the CNF $x$, and $O(x,y)$ counts the number of clauses of $x$ satisfied by $y$. We can associate with each maximization problem the following decision version: $$ \\{ (x,o) : V(x,y) = 1 \text{ and } O(x,y) \geq o \text{ for some } y \text{ of length at most } C|x|^C \\}. $$ In the case of MAX-SAT, we are given a CNF $x$ and a target $o$, and we need to determine whether some truth assignment satisfies at least $o$ clauses of $x$.

We say that an optimization problem is NP-hard if its decision version is NP-hard. In the case of MAX-SAT, the problem is obviously NP-hard, since choosing $o$ to be the number of clauses reduces the problem to SAT. (In fact, even MAX-2SAT is NP-hard, although 2SAT itself is in P.) In many other cases (for example, Vertex Cover, Max Cut and so on), there is no natural decision problem (no analog of SAT) other than the one obtained from the optimization problem.
> 4 votes

---
Tags: complexity-theory, np-complete, np-hard, complexity-classes, counting
---


# Question
Title: Are memcomputing and neuromorphic computing the same thing?
As the title reads, I’m just trying to understand if there is any difference between memcomputing and neuromorphic computing. If so, what are they?

Memcomputing: https://www.popularmechanics.com/technology/a16308/memcomputer-quantum-computing-alternative/

# Answer
> 1 votes
No, they are not the same thing. They share similarities, in that they are both brain inspired approaches. But this is where the similarities end.

To avoid going into too much detail, I'll explain it with this analogy:

Imagine you're a civilization trying to figure out flight and you're presented with an airplane (analogous to the brain) that you know can fly. The neuromorphic computing people are doing something akin to dismembering the airplane and trying out individual components of it to see if it can make you fly. A bit like taking a wing of the airplane and throwing it down a cliff to see how well it flies. Eventually you might figure out that the wing is able to generate some lift, provided some other things are present (like thrust and a second wing), but it'll take some trial and error and you're not really seeing the big picture until you've solved the puzzle of "what are the essential components and how to they contribute to flight?"

MemComputing takes a bit of a different approach. It's more like getting a working theory of flight first, using that to figure out some potentially essential components, and trying to use that to fly even if it doesn't reproduce that working airplane exactly.

The way to do this is to try to understand computation from a physics perspective. In doing so, we can develop a new computational paradigm separate from the Turing paradigm. We can understand why some problems are exponentially difficult to solve by mapping the problem onto physical systems that need to be simulated and realize that the origin of the difficulty in computation can be understood as long range correlations within the problem statement.

Take for instance the 3SAT problem, which can be generalized quite nicely from. For 3SAT, you're given a number $N$ of Boolean variables, $v\_i$, as well as a problem statement with clauses containing these $v\_i$ which need to be satisfied. The difficulty here is that each variable in a clause could appear in some distant other clause, meaning that flipping it to try and satisfy a clause would have immediate consequences at long "distances" in a completely different clause. So you can think of 3SAT as being difficult precisely because of such long range correlations.

This is a bit of an issue because Turing based computation has a fundamental bottleneck in the processing operation, since a processing step is completely blind to the operations of other processing units during the processing step. So there is no way to have information transfer during the computational step. Yet it would clearly be helpful from an information flow point of view to have such correlations that allow the more frustrating operations to be suppressed and the less frustrating operations to be less suppressed. This would then hopefully lead to a more efficient exploration of the decision tree.

It turns our that physical systems with memory have the kind of long-range correlation that can be useful here. This is why it would be appropriate to call MemComputing a computation **in and with memory**, because information isn't just stored in the same location where the processing occurs, but memory is also essential in driving the system towards a solution efficiently.

In the interest of brevity, I've glossed over some really important and interesting details in my answer here. For more details I would recommend the textbook MemComputing: Fundamentals and Applications by Max Di Ventra (full disclosure: I work in Di Ventra's research group).

---
Tags: memory-hardware
---


# Question
Title: Can you find a counter example for this sketch of a solution to the halting problem?
if we define halting problem as follows

$ \begin{align\*} h(m,n) &= \begin{cases} 1 & \text{if program $m$ halts on input $n$} \\ 0 & \text{otherwise} \\ \end{cases} \end{align\*} $

and we have two sometimes correct solutions $f$ and $g$ for $h$ that are always correct if they agree but fails to agree if the input is a counter example

then we can compute $h$ as follows

$ \begin{align\*} h(m,n) &= \begin{cases} f(m,n) & \text{if $f(m,n)=g(m,n)$} \\ h(t(m),n) & \text{otherwise} \\ \end{cases} \end{align\*} $

```
def h(m,n):
  if f(m,n)==g(m,n):
    print(f(m,n))
    while True:
      continue
  print(0)
  h(t(m),n)

```

where $t(m)\>m$ has the same behavior as $m$

now the question is: can you find a counter example? if not can we find $f$ and $g$?

# Answer
> 1 votes
Please recheck definitions in Turing's paper.

1. Circular machines *never* halt, and they get *stuck*, hence the term "circular". In a sense, the algorithm being executed by the machine (machines and algorithm are same) is *not applicable*. Which is why, as Turing remarks, they either enter into a state from which there is no possible move, or they keep doing rough calculation but never print symbols 0,1 (which constitute the computed number).
2. Circle-free machines will successfully print any number of digits of decimal (i.e. can halt). Here halting is the point. A circle-free machine never gets stuck, and therefore, *can* halt. Turing proves that there cannot be a universal halt tester.

---
Tags: turing-machines, halting-problem
---


title: Minimising maximum sum algorithm

text:
# Question
Title: Minimising maximum sum algorithm
Given a list of integers ***NUMS*** and an integer ***k*** (buckets), we must allocate every integer from NUMS to some bucket such that *maximum* of sum of integers across all buckets is minimised.

A simple algorithm which first sorts **NUMS** and then allocates integer to smallest bucket so far doesn't work. Eg. 5,5,4,4,4 for k=2. Output is 13 : {5,4}, {5,4,4}, where as correct output is 12 : {5,5}, {4,4,4}.

However, if the input integer array consists of *distinct* integers, will the above algorithm produce correct output? Looking for rigours analysis to understand why/why not.

# Answer
> 2 votes
No. Here is a counterexample (you seem to be sorting integers in decreasing order): $60, 50, 40, 29, 20$ and $2$ buckets. Your algorithm creates one bucket with sum $109$ and one bucket with sum $90$, while there exists a solution having a bucket with sum $99$ and the other with sum $100$.

Besides, if you algorithm worked then it could be used to solve the partition problem in polynomial-time, showing that $\mathsf{P}=\mathsf{NP}$. Indeed, given a set of integers $S$, there is a way to bucket the numbers in $S$ into $2$ buckets with maximum sum $\frac{1}{2} \sum\_{x \in S} S$ if and only if the answer to the corresponding partition instance is "yes". Notice that partition remains NP-hard when the integers in $S$ are distinct.

For constant $k$ you can solve your problem in pseudopolynomial time using dynamic programming. Let $x\_1, \dots, x\_n$ be the integers in your instance, let $M = \max\_{i=1,\dots, n} x\_i$, and $\vec{s} = (s\_1, s\_2, \dots, s\_{k-1}) \in \\{0, 1, \dots, M\\}^{k-1}$. Call $OPT\[i, \vec{s}\]$ the minimum possible sum of the elements in the $k$-th bucket when only the first $i$ elements are considered and the sum of the elements in $j$-th bucket with $j \< k$ can be at most $s\_j$.

Also let $(\vec{s}\_{-j}, s'\_j)$ denote the vector $\vec{s}$ in which the $j$-th component has been replaced by $s'\_j$.

For $i = 0$ and all $\vec{s}$, $OPT\[i, \vec{s}\] = 0$.

For $i \ge 1$: $$ OPT\[i, \vec{s}\] = \min\left\\{OPT\[i-1, \vec{s}\] + x\_i, \min\_{\substack{j=1,\dots,k-1 \\ x\_i \le s\_j}} OPT\[i-1, (\vec{s}\_{-j}, s\_j - x\_i) \] \right\\}, $$ where the minimum over an empty set is $+\infty$.

The value of the optimal solution is: $$ \min \\{ x \mid x \in \\{ 0, 1, \dots, M \\} \wedge OPT\[n, (x, x, \dots, x)\] \le x \\}. $$

The optimal solution itself can be recovered by retracing the optimal choices of the minimum backwards.

# Answer
> 1 votes
Consider `NUMS = [9, 7, 5, 4, 3]` and `k=2`.

Greedy algorithm would return `[9, 4]` and `[7, 5, 3]` which is not optimal, as `[9, 5]` and `[7, 4, 3]` is an optimal solution.

# Answer
> 0 votes
I think that this is equivalent to the problem of scheduling jobs on multiple identical processors in a way that minimizes makespan (when the last job finishes).

This has been shown to be an NP-Hard problem:

> Minimizing the maximum completion time ($P||{\displaystyle C\_{\max }}C\_{\max }$) is NP-hard even for identical machines, by reduction from the partition problem.
> Many exact and approximation algorithms are known. …
> Identical-machines scheduling — Minimizing the maximum completion time

That means that many of the greatest mathematicians in the world have, for many decades, failed to find a good algorithm for your problem.

You might look at some of the suggested algorithms.

---
Tags: algorithms, correctness-proof, optimal-strategy
---


# Question
Title: What is an explanation of the replace operator in the Pie language?
This is the first concept in *The Little Typer* to give me quite a bit of trouble, and it appears I am not alone ( ), so perhaps it would be beneficial to ask here. Hopefully this can be connected with more general concepts to expand the audience for this question beyond people reading the book.

The textbook *The Little Typer* is an introduction to dependent types using the Pie language. Chapter 8 introduces the concept of expressing statements with types, and constructing a value of that type being a proof of that statement being true.

In Pie, the type statement that two expressions are equal is `(= X from to)` \[docs\], where `=` is the type constructor, `X` is a type, and both `from` and `to` are values of type `X`. For example `(= Nat (+ 6 6) (+ 8 4))`.

The value constructor of `=` is `same`, where `(same e)` has type `(= X e e)` if `e` is an `X`. So the value `(same 12)` is a proof & instance of type `(= Nat (+ 6 6) (+ 8 4))` (that doesn't require induction to construct).

The `=` type also has an eliminator called `cong` (short for congruent) where `(cong target f)` transforms a `target` of type `(= X from to)` to type `(= Y (f from) (f to))`, where `f` is of type `(→ X Y)`. For example `(λ(n) (cong (same n) (+ 1)))` evaluates to `(λ(n) same (+ 1 n)`.

Here's where I have trouble: chapter 9 introduces a more general eliminator for `=` called `replace` and claims `replace` can do anything `cong` can do, and more. The definition of `replace` is:

```
(replace target motive base) → (motive to)
  target : (= X from to)
  motive : (→ X U)
  base : (motive from)

```

Frankly I can't make heads nor tails of this operator. How would I parameterize it to mimic `cong`? What is an example of something it can do that `cong` cannot? The only clue I have to its workings is its name and the context in which it's presented, where I assume what we're doing is transforming one expression to look like something else.

# Answer
> 2 votes
I'll rewrite `cong` in terms of `replace`. This should also explain how replace works along the way.

We have `(= X a b)` and want to produce `(= Y f(a) f(b))`. But notice that we already have `(= Y f(a) f(a))` from `(same f(a))`. So ideally we want to replace the second `a` in `(= Y f(a) f(a))` with a `b`. `replace` allows us do exactly that.

Here `target` is what we want to use to replace. We choose:

`target` is `(= X a b)`, `from` is `a`, `to` is `b`

Now base is the expression in which we want to replace something.

`base` as `(= Y f(a) f(a))`

How should we choose motive such that `motive to` is `(= Y f(a) f(b))` and `motive from` is `(= Y f(a) f(a))`?

```
motive x ->  (= Y f(a) f(x))

```

works! Thus we have implemented cong as:

```
cong target f -> replace target (lambda x -> (= Y f(a) f(x))) (same f(a))
target : (= X a b)
f : (-> X Y)

```

Sorry for the abuse of notation, I'm familiar with type theory but not Pie specifically. So all in all we have `(= Y f(a) f(a))` and used `(= X a b)` to replace one of the `a`s with a `b`.

Another simpler version of replace (if that helps):

```
simple_replace target from -> to
target : (= X from to)
from: X

```

---
Tags: dependent-types
---


# Question
Title: How does the SMT solver Z3 handle conditional statements in a constraint?
I have a constraint system which I seek to find solutions for. The constraints consist of lesser/equal inequalities which have a difference of two minimum expressions on their right side, for example:

$x\_1 \leq min((x\_2),(x\_5 + x\_6)) - min((x\_3),(x\_7 + x\_8 + x\_9))$

$x\_2 \leq min((x\_3 + x\_4), (x\_7)) - min((x\_5 + x\_8), (x\_5 + x\_9))$

Lacking an in-built minimum function, Z3 forces me to use pairwise comparisons in nested conditional statements. That works well and I either receive solutions or unsatisfiability results which are correct.

In order to formalize my approach, I would like to understand how Z3 deals with the conditional statements inside the inequalities. As there is no upper bound on the variables and as far as I can tell from Z3‘s verbose output, the SAT solver is not involved.

Does Z3 use a linearization method like the „big M“ approach and subsequent application of „cuts and branch“ or another technique?

# Answer
I can't answer how Z3 works. I can only speculate on some possible ways one could build a solver for this type of constraints, if one wanted.

It appears all of your inequalities have the form

$$A \le \min(B,C) - \min(D,E)$$

where $A,B,C,D,E$ are linear expressions of the variables, i.e., each has the form $a\_1x\_1 + \dots + a\_nx\_n + b$, for some constants $a\_1,\dots,a\_n,b$. This is equivalent to

$$\min(F,G) \le \min(H,I)$$

(take $F=D+A$, $G=E+A$, $H=B+A$, $I=C+A$). This is equivalent to the two inequalities

$$\min(F,G) \le H, \min(F,G) \le I,$$

which in turn is equivalent to the two inequalities

$$\min(F-H,G-H) \le 0, \min(F-I,G-I) \le 0.$$

So, without loss of generality, we can assume you have a system of inequalities of the form

$$\min(U,V) \le 0$$

where each $U,V$ are linear expressions of the variables (with different constants).

I don't know how Z3 solves such a system of inequalities, but one approach is to use integer linear programming (ILP). In particular, for each such inequality, we can introduce a new variable $t$, constrain $t$ to be an integer, and add the following inequalities:

$$\begin{align\*} t(U) + (1-t)V &\le 0\\ V &\le U + tM\\ U &\le V + (1-t)M\\ 0 &\le t \le 1 \end{align\*}$$

where $M$ is a large constant (larger than the largest possible value of $|U-V|$). This is a big-M method, as you mention in your question, and as you indicate in the question, it's not guaranteed to work correctly if we don't have an upper bound on the value of $|U-V|$.

I don't know whether Z3 uses this technique, or if it does, how it deals with the lack of any known upper bound on $|U-V|$. One possible heuristic would be to guess at a large value of $M$; try to solve the corresponding ILP instance. If there is no feasible solution, then we know there is no feasible solution to the original problem. If there a feasible solution to the ILP instance, we can check whether it solves the original problem. If it solves the original problem, we can output it. If it doesn't, we can double $M$ and try again. I don't know whether there are any guarantees that this will ever terminate, but it is a possible heuristic.

Another possibility is that Z3 might internally use a SMT solver, specifically, SMT with linear inequalities over real variables. It is easy to express your problem as an instance of such a SMT formula, and there are sophisticated SMT solvers for testing satisfiability of such formulas. I suspect this might be the most likely possibility, but I don't have a basis for this suspicion.
> 1 votes

# Answer
A minimum expression $min(x\_1, x\_2)$ can be transformed by introducing a new variable $m$ replacing the expression and adding the following formula to the set of boolean combinations of (in/dis)equalities:

$(m \leq x\_1) \land (m \leq x\_2) \land ((m \geq x\_1) \vee (m \geq x\_2))$

The resulting problem is solved by the algorithm described in the paper https://yices.csl.sri.com/papers/cav06.pdf.
> 1 votes

---
Tags: optimization, linear-programming, constraint-satisfaction, smt-solvers
---