# Question
Title: Does my solution converge to O(N) for worst-case time complexity?
Forgive me if this should be in StackOverflow or Mathematics instead!

I was given the following question at an interview:

```
Given an array of unique integers, find the first missing non-negative integer that is missing to form a consequence sequence of non-negative integers.

For example, the input [3, 4, -1, 0, 1] should give 2.
The input [1, -3, 2, 0] should give -1 (i.e no missing numbers).
The input of [-2, -3, -5] should give 0

```

I came up with a solution that is something akin to here: https://play.golang.org/p/b2pXr9kZYxM:

```
func findMissingNumber(nums []int) int{
    j := 0
    for i, num := range nums {
        if num < 0 {
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
    if j >= len(nums) {
        return 0
    }
    count := 0
    for i:=j ;i < len(nums);{
        count++
        if nums[i] == i-j {
            i++
            continue
        }
        if nums[i]+j >= len(nums) || nums[nums[i]+j]+j >= len(nums) {
            nums[i] = -1
            i++
            continue
        }
        temp := nums[nums[i]+j]
        nums[nums[i]+j]= nums[i]
        nums[i] = temp
    }
    fmt.Println(count)
    for i := j; i < len(nums); i++ {
        if nums[i] == -1 {
            return i - j
        }
    }
    return -1
}

```

Both the interviewer and I agreed that my solution could've been slightly more optimized (GeekForGeek seems to agree) but we were unsure if the worst-case for my solution was $O(N)$ or $O(N^2)$.

It seems like my solution has $$ O(N) + O(N/2) + O(N/4) + O(N/6) +\cdots+ O(1) $$ which becomes essentially: $$\frac{N}{2}\sum\_{n=1}^{N} n^{-1}$$

My calculus is a bit rusty (as are my algorithm skills) but I know this is a series diverges for $N \to \infty$. But can I say that for N sufficiently smaller than infinite (i.e Integer.Max), my worst-case becomes simply $$O(kN) = O(N)?$$

# Answer
$ \sum\_{i=1}^n \frac{i}{n} $ is the harmonic sequence, which goes to $\log(n)$

since in your question you claim the $T =\frac{n}{2} \sum\_{i=1}^n \frac{i}{n}$

$T = \frac{n}{2} \log(n) = O(n\log(n))$
> 2 votes

# Answer
> But can I say that for N sufficiently smaller than infinite (i.e Integer.Max), my worst-case becomes simply

Yeah, for limited N, you have O(N^2)=O(N\*log(N))=O(N)=O(1). Never forget about it! Your question is simply meaningless.
> 0 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis
---


# Question
Title: Can someone explain this formula for calculating Manhattan distance?
This is from a Kickstart problem:

> Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |\*| operator denotes the absolute value.

Then in the analysis:

> Note that the manhattan distance has an equivalent formula:
>
> ```
> dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))
>
> ```
>
> This formula is based on the fact that for any point, the set of points within a manhattan distance of K form a square rotated by 45 degrees. The benefit of this formula is that if we fix (x2, y2), the distance will be maximized when x1 + y1 and x1 - y1 are either maximized or minimized.

Could someone explain in more details how this formula can be derived?

# Answer
> 6 votes
### Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$.

**Proof 1**. $|x|=\max(x, -x)$ for all real number $x$. So $$\begin{aligned} |a|+|b| &=\max(a, -a) + \max(b, -b)\\ &=\max(a+b, a-b, -a+b, -a-b)\\ &=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\ &=\max(|a+b|, |a-b|) \end{aligned}$$

**Proof 2**. There are $2 \times 2 = 4$ cases.

* $a\ge 0$
    + $b\gt 0$. LHS is $a+b$, RHS is $a+b$.
    + $b\le 0$. LHS is $a-b$, RHS is $a-b$.
* $a\lt 0$
    + $b\gt 0$. LHS is $-a+b$, RHS is $-(a-b)$.
    + $b\le 0$. LHS is $-a-b$, RHS is $-(a+b)$.

### One dimensionality of Manhattan-distance.

The Manhattan-distance of two points $(x\_1, y\_1)$ and $(x\_2, y\_2)$ is either $|(x\_1+y\_1)-(x\_2+y\_2)|$ or $|(x\_1-y\_1)-(x\_2-y\_2)|$, whichever is larger. That is, $ d((x\_1, y\_1),(x\_2, y\_2))= \max(|(x\_1+y\_1)-(x\_2+y\_2)|, |(x\_1-y\_1)-(x\_2-y\_2)|)$$

**Proof**: By definition,
$$d((x\_1, y\_1),(x\_2, y\_2))=|x\_1-x\_2| + |y\_1-y\_2|.$$ Now apply the lemma above. QED.

This answer also serves as a complement to another answer of mine.

---
Tags: square-grid
---


# Question
Title: Algorithm for searching in BST with only <
How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $\<$ on the key type. The ones I can easily also requires $=$.

# Answer
If what you mean is that you want to build a BST and you only have the $\<$ operation, and you only know the algorithms with the $\leq$ operation, you can notice that : $$a \leq b \Leftrightarrow \neg (a \> b)$$ $$\Leftrightarrow \neg(b \< a )$$ Hence, using a negation in the right place, you can build your usual algorithm.
> 4 votes

# Answer
You can test whether $a=b$ as follows: if it's not true that $a\<b$ and not true that $b\<a$, then it follows that $a=b$.

(Disclaimer: this requires that it be possible to order all of the elements using $\<$, i.e., $\le$ be a total order. I imagine you were assuming this. But if it's not, you're screwed anyway and the problem is not solvable -- binary search trees require a total order.)
> 4 votes

---
Tags: search-algorithms, binary-search-trees
---


# Question
Title: Finding invariant when detecting a cycle
Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is :

> 1. Create an array : **seen** of size $\mid V \mid$ with **seen\[i\] = false** for all $i$
> 2. Perform a DFS (or BFS) starting at the node $0$.
> 3. When we see a node $i$ : we have two cases : if **seen\[i\] = false** then **seen\[i\] = true** else we found a cycle.

One idea to prove the correction of this algorithm is saying the following : if the algorithm return true it means there two nodes $x$ and $y$ such that when we looked at $y$ we have : **seen\[y\] = false** and **seen\[x\] = true** thus there is a cycle namely the cycle which begin at $x$ and use the only path that connect $x$ and $y$ in the DFS tree and then use the edge $(y,x)$.

The problem is that this is not really rigourous and I am really lokking for an invariant that we help me do the correction of this algorithm rigourously. So is there any invariant I can use here ?

Thank you very much !

# Answer
> 1 votes
Assuming we execute line 3 when you first visit a node, and assuming you are working with directed graphs, this algorithm is incorrect (consider what happens with a cross edge discovered by DFS).

Alternatively, assuming you are working with undirected graphs:

The missing part of your argument is the "thus" part; why does the existence of two such nodes imply the existence of a cycle?

To work out the proof, I suggest categorizing what types of edges can exist in the search tree for an undirected graph: tree edges? forward edges? back edges/ cross edges? Then, categorize what type of edge caused you to visit x when seen\[x\] was true. What does that mean the search tree has to look like?

---
Tags: algorithms, correctness-proof, loop-invariants
---


# Question
Title: How to calculate information gain in ID3?
I am trying to implement a decision tree classifier using ID3 algorithm. According to *Aritificial Intelligence - A Modern Approach*, information gain of attribute `A` is given by:

`Gain(A) = B(p/p+n) - Remainder(A)`

where `B` is the entropy of a Boolean random variable and `p` and `n` are the number of positive and negative examples in the training set.

My question is:

do `p` and `n` always refer to examples in the full dataset, or the remaining examples in current partition of the set?

If the former applied, the value of `B` would remain fixed throughout the training procedure. Is this correct?

# Answer
> 0 votes
It's important to use the current partition. See, e.g., the pseudocode in Wikipedia: https://en.wikipedia.org/wiki/ID3\_algorithm#Pseudocode

Typically, this is implemented as a recursive algorithm. When you recurse, you don't recurse on the entire training set; you recurse on the subset of examples that reach the tree node you're trying to build.

---
Tags: machine-learning, information-theory, entropy, decision-tree
---


# Question
Title: Maximal size of a set of ordered words such that no pair of letters occurs twice
Consider an alphabet $\Sigma=\\{1,\dots,n\\}$. An ordered word is a word $w=w\_1w\_2\dots w\_k\in\Sigma^\*$ such that $w\_1\<w\_2\<\dots\<w\_k$. In other words, an ordered word is a strictly increasing sequence over $\\{1,\dots,n\\}$.

Let us call $O\_{n,k}$ the set of all ordered words over $\\{1,\dots,n\\}$ of length $k$. Clearly, there are $\binom{n}{k}$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $M\subseteq O\_{n,k}$ such that each pair of letters $ij$ ($1\le i\<j\le n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?

Formally, let $\\#\_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then $$m\_{n,k}=\max\\{|M|:M\subseteq O\_{n,k}\text{ and }\\#\_{ij}(M)\le 1\text{ for all }i,j\text{ with }1\le i\<j\le n\\}.$$ **What is $m\_{n,k}$?**

Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.

$ $

*Example*: $\Sigma=\\{1,2,3,4\\}$ and $k=3$.

All ordered words of length $3$ are $$O\_{4,3}=\\{123,124,134,234\\}.$$ A maximal subset such that no pair occurs more than once would be $$M=\\{123,134\\},$$ because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m\_{4,3}=2$.

Thank for any help.

# Answer
There is a simple upper bound of $$\frac{\binom{n}{2}}{k-1},$$ following from the fact that there are $\binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of $$ \frac{\binom{n-k+1}{2}}{k-1}. $$ This shows that for fixed $k$, the answer is asymptotically $$ \frac{n^2}{2(k-1)} \pm O(n). $$

For every $c \geq 1$ and $1 \leq d \leq c$, we can consider the collection of ordered words of the form $$ d,d+c,\ldots,d+(k-1)c \\ d+(k-1)c,d+(k+1)c,\ldots,d+2(k-1)c \\ \ldots $$ These collections for all $c,d$ have disjoint pairs. For a given $m \leq n$ and $c$, there is a word of this type if $m-(k-1)c \geq 1$, that is, if $c \leq \frac{m-1}{k-1}$. Therefore, the total number of words is $$ \sum\_{m=k}^n \left\lfloor \frac{m-1}{k-1} \right\rfloor. $$ We can estimate this sum roughly by $$ \sum\_{m=k}^n \left(\frac{m-1}{k-1}-1\right) = \sum\_{m=k}^n \frac{m-k}{k-1} = \frac{\binom{n-k+1}{2}}{k-1}. $$
> 2 votes

---
Tags: combinatorics, word-combinatorics
---


# Question
Title: How do I do a subtraction question on turing machine
For example, 111-11

I want to have the output as 111-11=1

I am a beginner at TM and am having a hard time trying to solve this question.

# Answer
> 0 votes
It seems that you have unary numbers, so there are three cases to consider: number you subtract from is greater, uqual or smaller, this gives you hint what to handle.

In unary when you subtract 11 from 111 (111 - 11 = 1) you have to delete ones in minuend until subtrahend is 0.
In case these are equal, you have to denote 0 (empty tape might denote this). In the third case, result is negative.

Case 1) 111 - 11 = 11 - 1 = 1 - 0 = 1
Case 2) 111 - 111 = 11 - 11 = 1 - 1 = 0 - 0 = 0
Case 3) 11 - 111 = 1 - 11 = 0 - 1 = - 1

So let us start with first phase: start with scratching from both sides, call it say qS:
'B111-11B' where B is blank, on qS put B at leftmost 1, switch state to qS1, which goes right until it finds B. Moves one to the left, if it is 1, put B and return to the leftmost 1 (say state qSr). After execution:
'BB11-1BB' repeat
'BBB1-BBB' if in state qS1 there is no 1 but -, put B on - and accept.

Case 2 would yield something like 'BB-BB', if you are happy with Blank tape as 0, case 1 solves it already, otherwise put 0 on the tape if there are no 1 left.

Case 3 leaves you with situation like 'B1-11B'. Here only modification is to accept when after - there is Blank. So one step later, there is 'BB-1BB', this is result already.

What could go wrong?
There might be input like 'B11-1-1B', if you are not promised it won't happen. In such case split going right in qS1 into find '-' and then find Blank. If after first '-' there occurs another one, reject on it.

To practice more you could write your code in simulator online, check addition first as Apass.Jack suggested. When you finish, try multiplication, the sooner the better.

To see a working version look at my subtraction code at simulator.

This code has format:
state read\_symbol write\_symbol direction new\_state, everything after semicolon is a comment, halt-accept is accepting state, halt-reject is rejecting state * in direction is not move instruction (you may be familiar with S notation or do not really care how it moves, since machine halts now).

```
qS 1 _ R qS1 ; state to start scratching left to -
qS - - R q2 ; check if there is 1 after 1
qS1 1 1 R qS1 ; pass through 1
qS1 - - R qS2 ; minus found
qS2 1 1 R qS2 ; going for rightmost 1
qS2 _ _ L qSr ; blank found after all 1
qS2 - - * halt-reject ; second minus found, reject bad formatted input
qSr 1 _ L qSr2 ; scratch last 1
qSr - 1 * halt-accept ; scratched 1 at the beginning appears here.
qSr2 1 1 L qSr2 ; leave 1 as is
qSr2 - - L qSr2 ; leave - as is
qSr2 _ _ R qS ; start another pass

q2 1 1 R q2c ; there is a - but still input may be malformed, check it

q2c 1 1 R q2c;
q2c - - * halt-reject ; found second -, reject
q2c _ _ * halt-accept ; there is negative number on tape, accept

q2 _ _ L q2m ; there is only minus left, clean it up
q2 - - * halt-reject ; malformed
q2m - 0 * halt-accept ; accept after cleanup

; tested on accepting -, 1-, -1, 1-1, 11-1, 111-1, 1-11
; testet on rejecting 1--1, 11-11-, --, -1
; to explore it more, maybe -11-11 should give -1111? Not handled now

```

---
Tags: turing-machines
---


# Question
Title: Is there a reasonable and studied concept of reduction between regular languages?
Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?

# Answer
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $\mathsf{NC^1}$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $\mathsf{NC^1}$-complete with respect to $\mathsf{AC^0}$-reductions (these are reductions computed by polynomial size, constant depth circuits with unbounded fan-in). Barrington's theorem implies that all regular languages are in $\mathsf{NC^1}$, and so such regular languages are complete for the set of regular languages under $\mathsf{AC^0}$-reductions.

Since we know that $\mathsf{AC^0} \neq \mathsf{NC^1}$ (for example, the parity function is in the latter but not in the former), regular languages in $\mathsf{AC^0}$ cannot be complete. For example, the language $a^\*b^\*$ isn't complete. Similarly, $\mathsf{AC^0}\[p\] \neq \mathsf{NC^1}$, showing that the language $(aa)^\*$ isn't complete.

The simplest example of a language which satisfies the condition above is the language of all words over $S\_5$ (the symmetric group on 5 elements) which multiply to the identity. The syntactic monoid of this language is $S\_5$, which is a nonsolvable finite group. The slightly smaller alternating group $A\_5$ would also work.
> 8 votes

# Answer
It only makes sense to talk about reductions between languages if the reduction are allowed to use less resources than the languages we're talking about. For example, when we reduce between problems in **NP**, we use (deterministic) polynomial-time reductions, or even log-space reductions. (OK, we don't know that those are less powerful than **NP**, but they seem to be.) If you don't use reductions that are weaker than the class of problems you're interested in, you end up with the boring result that everything except $\emptyset$ and $\Sigma^\*$ is complete.

All regular languages can be decided in linear time and constant space. It's hard to imagine any weaker resource bound that you could use to perform the reductions, so the concept of reductions probably isn't interesting, here.
> 7 votes

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


# Question
Title: Negative lookahead in LR parsing algorithm
Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.):

`Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ;`

It's an ordinary rule, except that it has a restriction: a phrase produced with this rule cannot begin with `Terminal1, ..., TerminalN`. (Surely, this rule can be replaced with a set of usual rules, but it will result in a bigger grammar). This can be useful for resolving conflicts.

The question is, is there a modification of LR table construction algorithm that accepts such restrictions? It seems to me that such a modification is possible (like precedence relations).

Surely, it can be checked in runtime, but I mean compile-time check (a check which is performed while building parsing table, like `%prec`, `%left`, `%right` and `%nonassoc` directives in yacc-compartible generators.)

# Answer
Yes, there is such a modification. A negative lookahead assertion at the END of a production means taking special care in computing FOLLOW sets. Before a terminal makes no sense. Before a nonterminal is a bit more complicated: the optimal strategy depends on the context. Special care while generating the shift relationship is part of the answer. On balance, this is an algorithm design problem more than a theoretical computer science problem.
> 0 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn
> BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn.

As the Title suggests, I'm trying to intuitively understand this problem. Suppose we have a Pawn and a Knight taking turns. Both pieces must move on their turn, and both pieces have a starting position, and suppose the board is sufficiently large enough for the Knight to eventually catch up to and eliminate the Pawn, where the Pawn is avoiding being captured. I want to find the minimum amount of moves the Knight takes to eliminate the Pawn.

I know that we can use a BFS algorithm to find the shortest path between the Knight and a stationary spot on the board, but I'm not sure how to do this for a moving target. What if we do a BFS on every square of the column the Pawn is travelling on and then compare the number of moves that takes and check if one of these sequence of moves ends up on the Pawn's location. But this doesn't seem like it will always work, because finding the minimum amount of moves to where the Pawn will eventually be could be less than the actual minimum amount of moves to catch up to the Pawn because the Knight could "stall" a bit until it's in the right position to eliminate the Pawn.

# Answer
> 1 votes
It's very simple.

A pawn has a choice to move one or two positions forward in its first move, in all following moves it moves one position. A knight moves two squares in one direction, and one step orthogonal.

As a result, the colour of a pawn's square changes on every move, except on the first move, where it has a choice to change the square's colour or not. The knight always changes the colour of its square. So in its first move, the pawn moves to the same colour as the knight, and from then on, the knight can never take the pawn.

(You need to specify what should happen if the knight is in the pawn's way so it cannot move though. If the rule is that the pawn just doesn't move, then the knight can block the pawn's path, and two moves later takes the pawn).

# Answer
> 0 votes
Form a graph where each vertex is a pair $(k,p)$ where $k$ represents the position of the knight and $p$ represents the position of the pawn; each edge represents what happens when the pawn moves and then the knight makes a move. Use BFS to find the shortest path to a vertex where both pieces are on the same square.

---
Tags: graphs
---


# Question
Title: is it possible to reduce $HALT_{TM}$ to $E_{TM}$?
I am wondering, if it is even possible: is it possible to reduce $HALT\_{\text{TM}}$ to $E\_{\text{TM}}$?

$HALT\_{\text{TM}}=\\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }w\\}$

$E\_{\text{TM}} =\\{\langle M\rangle\mid M\text{ is a TM and } L\left(M\right)=\emptyset \\}$

I tried to look online, in summaries and handouts and even in several books (including Sipser's book), but couldn't find any indication on it.

is it possible? if so, how?

# Answer
> 1 votes
Nice question.

No, you cannot reduce $HALT\_{\text{TM}}$ to $E\_{\text{TM}}$, although you can reduce $HALT\_{TM}$ to $\overline{E\_{\text{TM}}}$. Here we are talking about Turing reduction.

### $HALT\_{\text{TM}}$ can be reduced to $\overline{E\_{\text{TM}}}$

Let $\langle M,w\rangle$ be such that $M\text{ is a }TM\text{ and }M\text{ halts on input }w$. Now let us construct a TM $M'$. On an arbitrary input $u$, $M'$ will check whether $u$ is the same as $w$.

* if it is not, $M'$ will run forever.
* if it is, $M'$ will simulate $M$ on input $w$. Then once $M'$ halts, $u$ is considered as accepted.

We can make the transformation from $M$ to $M$ be algorithmic, thanks to the existence of a universal TM machine.

It is routine to verify that $\langle M,w\rangle$ is in $HALT\_{TM}$ if and only if $M'$ is in $\overline{E\_{\text{TM}}}$.

### $HALT\_{\text{TM}}$ cannot be reduced to $E\_{\text{TM}}$

For the sake of contradiction, suppose $HALT\_{\text{TM}}$ is reduced to $E\_{\text{TM}}$ by reduction $f$. Then $\overline{HALT\_{\text{TM}}}$ is reduced to $\overline{E\_{\text{TM}}}$ by reduction $f$ as well. Since $\overline{E\_{\text{TM}}}$ is Turing-recognizable, so is $\overline{HALT\_{\text{TM}}}$. Since $HALT\_{\text{TM}}$ is Turing-recognizable, we have $HALT\_{\text{TM}}$ is decidable, which is known to be false, however. This contradiction shows that $HALT\_{\text{TM}}$ cannot be reduced to $E\_{\text{TM}}$.

---
Tags: complexity-theory, turing-machines, computability, reductions
---


# Question
Title: Finding all solutions to an integer linear programming (ILP) problem
My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this problem near the end, but I'm interested in knowing if there is a proper and efficient algorithm or method for solving this kind of problem.

There is no objective function, but the constraints for this ILP are

$$ \begin{equation} 0 \leq -2x -y \leq 8 \\ 0 \leq 1-x+3y \leq 5 \\ 0 \leq 2+x-y \leq 2 \\ x,y \in \mathbb{Z} \end{equation} $$

Since this ILP has two variables, I can visually inspect the solution region by graphing the lines formed by the constraints, which are

$$ \begin{align} y &\leq -2x \\ y &\geq -2x-8 \\ y &\geq \frac{1}{3}x - \frac{1}{3} \\ y &\leq \frac{1}{3}x + \frac{4}{3} \\ y &\leq x + 2 \\ y &\geq x \end{align} $$

By inspection, there are 6 integer solutions for $(x, y)$: $\\{ (0,0), (-1,1), (-1,0), (-2,0), (-2,-1), (-3,-1) \\}$.

However, my current method is to use linear programming with non-negativity relaxed and integers from branch-and-cut. I've tried using a set of four objective functions: minimize $x$, maximize $x$, minimize $y$, and maximize $y$. These give a smaller search area as

$$ \begin{equation} -3 \leq x \leq 0 \\ -1 \leq y \leq 1 \end{equation} $$

I then iterate over all valid integer tuples in that smaller area and filter it for tuples that satisfy the original constraints. The tuples that remain are all valid integer solutions.

# Answer
"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope.

This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, *An Algorithmic Theory of Lattice Points in Polyhedra*, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)

There are probably more recent developments than I'm aware of, but this will give you a starting point for chasing citations.
> 9 votes

# Answer
Land and Doig (1960) proposed a method for solving discrete programming problems. You may be able to modify his algorithm so that instead of solving an optimization problem you are enumerating every possible feasible integer solution.

## Reference

A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. 28 (3). pp. 497–520. doi:10.2307/1910129.
> 2 votes

# Answer
read this paper: Computing convex hulls and counting integer points with polymake. I think polymake can do it for you.
> 0 votes

---
Tags: linear-programming, integer-programming, counting
---


# Question
Title: When do we use parallel algorithms for enumerating combinations?
I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used?

Here is a famous example of parallel algorithms, *Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations* by S. G. AKL.

# Answer
> 0 votes
I have found one. A parallel algorithm for finding small sets of genes that are enough to distinguish two biological states

But if you found others, I would like to know.

---
Tags: combinatorics, parallel-computing, enumeration
---


# Question
Title: Proof for optimal interval scheduling using a Greedy Approach
> You are given a set of n jobs, where each job j is associated with a size s(how much time it takes to process the job) and a weight w(how important the job is). Suppose you have only one machine that can process one unit of jobs per time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C \> to be the time that job j is completed. The goal is to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * Cj
>
> * Approach 1: Process Jobs according to the highest weight first
> * Approach 2: Process jobs in ascending order of their size
> * Approach 3: Process jobs in descending order of their density (w/s)

So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:

- Approach 1 wouldn't be optimal if the higher weights(w) have a greater size(s).
- Approach 3 wouldn't work if the weight was equal to the size in case of all the jobs. If w=s for all the jobs, you wouldn't be able to determine what to chose first.

Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w\*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?

# Answer
> 1 votes
Let's consider two jobs in the sequence you obtained:

* $A$, of weight $w\_A$ begins at $t\_0$ and finish at $t\_0 + s\_A$
* $B$ coming just after $A$, of weight $w\_B$ begins at $t\_0 + s\_A$ and finish at $t\_0 + s\_A + s\_B$

If we compute only $K\_{A, B}$ the contribution of $A$ and $B$ in $K = \sum\_j w\_j C\_j$:

$K\_{A, B} = w\_A (t\_0 + s\_A) + w\_B (t\_0 + s\_A + s\_B)$

If A and B are inversed in the sequence, we have $K'\_{A, B}$:

$K'\_{A, B} = w\_A (t\_0 + s\_A + s\_B) + w\_B (t\_0 + s\_B)$

The difference is:

$\Delta K\_{A, B} = K'\_{A, B} - K\_{A, B}$

$= w\_A s\_B - w\_B s\_A$

$= (w\_A/s\_A - w\_B/s\_B) \times (s\_A s\_B)$

The switch should be done if and only if $\Delta K\_{A, B}$ is negative in order to minimize $K$. Only the approach 3 provides you a sequence where no more switch is worth.

If two jobs have the same $w/s$ ratio, just take them in any order, the final $K$ would remain unchanged.

---
Tags: greedy-algorithms, intervals
---


# Question
Title: Is substitution done to all occurrences?
In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable.

Then if we apply the first rule, and then the second , do we get $aa$ or either $aA$ or $Aa$ ?

# Answer
> 1 votes
A single substitution is one application of one rule. So the rule $A\to AA$ means "Pick any single $A$ in the string and replace it with $AA$" and "$A\to a$" means "Pick any single $A$ and replace it with $a$." Substitutions are done one at a time, and there's no way to write a rule that says "Replace *every* $X$ with $Y$, or replace them all with $Z$."

If you start with $A$ and apply the first rule, you certainly get $AA$, since there's no other choice. But there are two ways of applying $A\to a$ to $AA$: you could pick the first or second $A$ to replace with $a$.

Indeed, there are two ways to apply $A\to AA$ to the string $AA$. However, replacing either the first or second $A$ with $AA$ gives the string $AAA$.

---
Tags: context-free, formal-grammars
---


# Question
Title: Fastest algorithm to decide whether a (always halting) TM accepts a general string
Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$:

$A$ simply simulates $M$ on $w$ and answer what $M$ answers.

The question here is, can this be proven to be the fastest algorithm to do the job?

(I mean, it's quite clear there could not be a faster one. Or could it?)

And more formally and clear:

Is there an algorithm $A'$, that for every input $\langle M,w\rangle$ satisfies:

1. If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.
2. $A'$ is faster than $A$.

# Answer
> Is there an algorithm $A′$, that for every input $\langle M,w\rangle$ satisfies:
>
> 1) If $M$ is a TM that halts on all inputs, $A′$ will return what $M$ returns with input $w$.
>
> 2) $A′$ is faster than $A$ (In worst case terms)

It's not possible to be asymptotically faster by more than a log factor. By the time hierarchy theorem, for any reasonable function $f$, there are problems that can be solved in $f(n)$ steps that cannot be solved in $o(f(n)/\log n)$ steps.

Other answers point out that you can get faster by any constant factor by the linear speedup theorem which, roughly speaking, simulates a factor of $c$ faster by simulating $c$ steps of the Turing machine's operation at once.
> 3 votes

# Answer
Dkaeae brought up a very useful trick in the comments: the Linear Speedup Theorem. Effectively, it says:

> For any positive $k$, there's a mechanical transformation you can do to any Turing machine, which makes it run $k$ times faster.

(There's a bit more to it than that, but that's not really relevant here. Wikipedia has more details.)

So I propose the following family of algorithms (with hyperparameter $k$):

```
def decide(M, w):
    use the Linear Speedup Theorem to turn M into M', which is k times faster
    run M' on w and return the result

```

You can make this as fast as you want by increasing $k$: there's theoretically no limit on this. No matter how fast it runs, you can always make it faster by just making $k$ bigger.

This is why time complexity is always given in *asymptotic terms* (big-O and all that): constant factors are extremely easy to add and remove, so they don't really tell us anything useful about the algorithm itself. If you have an algorithm that runs in $n^5+C$ time, I can turn that into $\frac{1}{1,000,000} n^5+C$, but it'll still end up slower than $1,000,000n+C$ for large enough $n$.

P.S. You might be wondering, "what's the catch?" The answer is, the Linear Speedup construction makes a machine with more states and a more convoluted instruction set. But that doesn't matter when you're talking about time complexity.
> 4 votes

# Answer
**Of course there is.**

Consider, for instance, a TM $T$ which reads its entire input (of length $n$) $10^{100n}$ times and then accepts. Then the TM $T'$ which instantly accepts any input is at least $10^{100n}$ times faster than any (step for step) simulation of $T$. (You may replace $10^{100n}$ with your favorite largest computable number.)

Hence, the following algorithm $A'$ would do it:

1. Check whether $\langle M \rangle = \langle T \rangle$. If so, then set $\langle M \rangle$ to $\langle T' \rangle$; otherwise, leave $\langle M \rangle$ intact.
2. Do what $A$ does.

It is easy to see $A'$ will now be $10^{100n}$ faster than $A$ if given $\langle T, w \rangle$ as input. This qualifies as a (strict) asymptotic improvement since there are infinitely many values for $w$. $A'$ only needs $O(n)$ extra steps (in step 1) before doing what $A$ does, but $A$ takes $\Omega(n)$ time anyway (because it necessarily reads its entire input at least once), so $A'$ is asymptotically just as fast as $A$ on all other inputs.

The above construction provides an improvement for one particular TM (i.e., $T$) but can be extended to be faster than $A$ for *infinitely* many TMs. This can be done, for instance, by defining a series $T\_k$ of TMs with a parameter $k$ such that $T\_k$ reads its entire input $k^{100n}$ times and accepts. The description of $T\_k$ can be made such that it is recognizable by $A'$ in $O(n)$ time, as above (imagine, for instance, $\langle T\_k \rangle$ being the exact same piece of code where $k$ is declared as a constant).
> 0 votes

---
Tags: turing-machines, time-complexity
---


# Question
Title: Connection between CPU address bus and max amount of RAM
So, i'm stack on the following question \> "A system has a 12 bit address bus. What is the maximum amount of RAM that can be installed on the system?"

First of all, is this question correct? If so, can you explain to me way and how to determine the answer?

Thanks in advance.

# Answer
A 12 bit address bus means the computer can access $2^{12}$ unique blocks of memory. Unstated in the problem is the size of each block, and without that information you cannot determine the maximum amount of ram.

Bulat also points out that there are other tricks that could be played, such as multiplexing the address bus. If the address was sent in 2 cycles rather than 1, then $2^{24}$ blocks could be addressed.

Lacking *any* other information, and recognizing that this is a homework/test question we can make a few assumptions. The first is that we're not doing anything exotic like multiplexing the address bus. In a test-question setting, it is highly likely that they would call a multiplexed 12 bit bus a "24 bit bus" instead *unless* you were on a chapter specifically dedicated to clever address bus tricks.

The second assumption we have to make is the size of the block. Since it isn't specified, there are two common assumptions we could make. The first is that it is byte addressable, meaning each byte can be addressed individually as its own block. In that case, there's a maximum of $2^{12}$ bytes of memory addressable. The other common assumption is that they are addressable by machine word. If you are working in a chapter on 16-bit machines, it might be 16-bit blocks (2 byte), so there'd be a maximum of $2^{12}\cdot 2 = 2^{13}$ bytes.

Given it is a test question, and your teacher is not evil, I would assume the simplest answer is likely correct. I'd assume 1 byte blocks, and no exotic trickery, yielding a best answer of $2^{12}$ bytes. If I was facing this in an industry setting, I'd find the datasheets on the processor to determine the exact answer.
> 1 votes

# Answer
It depends. The system could be set up to always transfer memory in multiple of 16 bytes. So the 28 bit address bus allows you to access $2^{28}$ sets of 16 bytes, for a total of $2^{32}$ bytes. Another system could be set up in a different way.
> 0 votes

# Answer
Since

1. memory can be accessed in large blocks, f.e. 48-bit words
2. address bus can be multiplexed, i.e. address sent in two or more parts
3. MMU hardware can map multiple pages to the same memory address

the right answer depends on your teacher mind :)
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)
Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. Vertices at level 1 and k are called the *roots* and the *leaves*, respectively. The problem is to find all descendant leaves of each root. For instance, for the following graph,

the answer would be: 1: 12, 13 2: 12, 13 3: 12, 13, 14, 15, 16 4: 14, 15, 16

A naive solution can be to run a DFS for each root which will take O(r(n+m)) time where r is #roots, n is #vertices and m is #edges.

Can we do better? Another way to see the same graph is that it is a bipartite DAG.

# Answer
> 1 votes
Define $\ell(v)$ to be the leaves reachable from a node $v$. Note the following:

> **Lemma 1**: For all non-leaf nodes $v$ we have: $$\ell(v) = \cup\_{u \in c(v)} \ell(u)$$ where $c(v)$ is the set of all children of $v$.

We now construct an algorithm around this:

1. Let $A = \\{v\_1, v\_2, \ldots, v\_n\\}$ be the *reverse* topological order of nodes in $G$.
2. For all $v \in A$:
    1. If $v$ is a leaf node, define $\ell(v) = \\{v\\}$.
    2. Otherwise, define $\ell(v)$ as we did in **Lemma 1**.

Now the complexity of this is $O(km + n)$ where $k$ is the average cost of union-ing the $\ell$-sets of the children of a non-leaf node. How you go about union-ing the sets is up to you. Standard merging is easy to implement. You could also try using a disjoint-set data structure, but this becomes tricky because a node might have multiple parents.

# Answer
> 0 votes
Here is an approach that takes advantage of path compression.

1. Let $\ell$ be the set of leaf nodes.
2. Let $G'$ be the same graph as $G$ except every edge is direction the opposite way.
3. For each $v \in \ell$ call $\mathrm{Find}(v)$ and store this as a reverse mapping from all $u \in \mathrm{Find}(v)$ to $v$.

Find with path compression must be implemented a bit differently because there are multiple parents:

```
Find(u):
  if u is a root node:
    return u
  if u is a child of only roots:
    return children of u
  else:
    roots = {}
    for each child v of u that's not a root in G':
      for each node x in Find(v):
        add x to roots
    delete all edges from v to a child u in G'
    for each node x in roots:
      add an edge from u to x in G'

```

Here is how it would work on your example.

### Step 1:

### Step 2: Find(12)

### Step 3: Find(13)

### Step 4, 5, and 6: Find(14), Find(15), Find(16)

Analysis of this is rather tricky because there is a cost for adding all the edges, but a benefit for shortening the distance between a leaf and its root(s). The edges can end up growing quadratically, but then again this will only be the case if the output will end up being quadratic.

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal
---


# Question
Title: Find a path from s to t using as few red nodes as possible
Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and t, that you pass through as few red nodes as possible.

Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.

Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.

I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.

# Answer
> 8 votes
To solve this, you need to use $BFS$. But first, manipulate $G$ so that the path will always favor blue vertices.

The solution has 2 parts:

1. Use $DFS$ on blue vertices only, to find all all-blue connected components. Let's denote each such component by $v'$. Now, each blue $v \in v'$ will be "compressed" to a single vertex $u$, and an edge $(u,x)$ will be added for every $x \in N(v')$. Note any such $x$ is necessarily red. This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.

Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertex.

2. Use $BFS$ from $s$. That length of the path to $t$ will essentially be the shortest path under the constraint of least red vertices in the path.

# Answer
> 1 votes
Convert $G$ to a directed graph $G'$ where we have two edges $(u,v)$ and $(v,u)$ in $G'$ for every edge $\\{u,v\\}$ in $G$. Let the length of $(u,v)$ be 1 if $v$ is a red node and 0 otherwise. Now run Dijkstra's algorithm on $G'$ from the starting node $s$ to the ending node $t$.

It is clear that the shortest path thus found passes as few red nodes as possible.

While we are running Dijkstra's algorithm, we are in one of two kinds of stages alternatively. One kind of stage is when we are exploring towards red nodes. The other kind of stage is when we are exploring towards blue nodes. Since each edge is checked/visited as most twice, the running time is $O(|E|)$.

---
Tags: graphs
---


# Question
Title: Can someone give me the definition of #Monotone-2SAT?
In the decision problem, I set all variables to true and see if the formula is satisfiable.

My question is because I do not understand how there can be multiple solutions, though all variables are true.

# Answer
Satisfiability problems are about making the formula true, not necessarily the variables. Counting satisfiability problems ask how many different assignments to the variables make the formula true.

In $\\#\text{Monotone-2SAT}$, the formula is in 2-CNF (conjunctive normal form with at most two literals per clause) and is monotone (there are no negations). So, certainly, making all the variables true satisfies the formula, but there are plenty of other ways. Just consider the formula $x\lor y$, which is monotone and in 2-CNF. It has three satisfying assignments.
> 3 votes

---
Tags: complexity-theory, satisfiability, counting
---


title: Greedy algorithm Packing problem

text:
# Question
Title: Greedy algorithm Packing problem
Assume that $A$ is the set of objects such that each object $x\_i \in A$ has value $w\_i$. We wish to pack these objects into group, each pack containing **at least** $k$ objects. Our goal is to minimize the maximum difference between the maximum and minimum value of each packs. in other words, our goal is to minimize $L$ with the constraint that all packs should have more than $k$ object in them.

$$L = \max\_{i \in \mathrm{packs}} \left\\{\max\_{j \in \mathrm{pack}(i)}w\_j - \min\_{k \in \mathrm{pack}(i)}w\_k \right\\}.$$

For example for the following packing, $L$ is $\max{(30-20, 120 - 100)} = 20$. $$\[20, 30\] \\;\\; \[100,110,120\]$$

I was wondering if there is a greedy algorithm that can do the job.

# Answer
I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j\_random\_hacker's comment seems the appropriate way to find $L$.

---

Let $n$ be the number of given objects. Assume $k\le n$; otherwise there is no such packing.

First, sort all the weights so that we will have $w\_0\le w\_2\le \cdots\le w\_{n-1}$. Then there is an optimal packing in which each pack consists of consecutive weights. That fact enables dynamic programming, since we can consider only that kind of packing, which has a natural last pack.

Given a packing $P$, let $L(P)$ be the maximum difference between the maximum and minimum value of each pack in $P$. Let $dp\[i\]$ be the minimum of $L(P)$ for all packings of the weights $w\_0, w\_1,\cdots, w\_i$, where $k-1\le i\le n-1$. The final answer for all $n$ weights is $dp\[n-1\]$.

The base case is $dp\[i\] = w\_i-w\_0$ for $k-1\le i\lt 2k-1$, as there can be only one pack that contains all the weights.

What if $i\ge 2k-1$? Note that a packing with its last pack removed is still a packing. That critical observation tells us that $dp\[i\]$ is the minimum of $$\begin{align} &\max(dp\[i-k\],\ w\_i-w\_{(i-k)+1}), \\ &\max(dp\[i-k-1\],\ w\_i-w\_{(i-k-1)+1}), \\ &\max(dp\[i-k-2\],\ w\_i-w\_{(i-k-2)+1}), \\ &\cdots,\\ &\max(dp\[i-k-\ell\],\ w\_i-w\_{(i-k-\ell)+1}), \\ &\cdots, \end{align}$$ where the list stops right before $\ell$ becomes $k$, since we can ignore the packings where the last pack (in fact, any pack) contains at least $2k$ objects. We can always split those objects into 2 valid packs, which will not increase $L(P)$. We can also stop as soon as $w\_i-w\_{(i-k-\ell)+1}$ is no less than the minimum so far.

The time-complexity of algorithm is $O(n\log n + nk)$.
> 1 votes

---
Tags: algorithms, packing
---


# Question
Title: Proof that (x-y)(x+y) is more accurate than x²-y²
I was carrying on my reading of What Every Computer Scientist Should Know About Floating-Point Arithmetic but got stuck on the proof of Theorem 2 (page 34).

At some point it says: \begin{align} (x \otimes x) \ominus (y \otimes y) & = \left\[x^2(1 + \delta\_1) - y^2(1 + \delta\_2)\right\](1 + \delta\_3) \\ & = \left\[(x^2 - y^2)(1 + \delta\_1) + (\delta\_1 - \delta\_2)y^2\right\](1 + \delta\_3) \\ \end{align} I'm ok with the rewriting, but I don't understand the argument that:

> When $x$ and $y$ are nearby, the error term $(\delta\_1 - \delta\_2)y^2$ can be as large as the result $x^2 - y^2$.

This doesn't make much sens to me right now. I understand that if both quantities are close to each other, then the relative error is close to $1$. But not why they should be close to each other.

# Answer
Suppose $y = x + \Delta$. Then $(x^2 - y^2) = x^2 - (x^2 + 2\Delta x + \Delta^2) = - (2\Delta x + \Delta^2)$ with leading term on the order of $2 \Delta x$. Multiply by $1 + \delta\_1$ and that's still the leading term.

Compare to $(\delta\_1 - \delta\_2) y^2$ with leading term $(\delta\_1 - \delta\_2) x^2$.
> 3 votes

# Answer
I'm not 100% sure of everything, but here are some elements that are implicit in the proof. Note that I reuse the notations and common knowledge of the paper, therefore this answer isn't self-contained.

First, let's assume that $x \gt y \ge 0$. It's a safe assumption to make because the sign of the variables doesn't matter and swapping $x$ and $y$ only change the sign of the result.

Let's write the relative error for the formula $(x \otimes x) \ominus (y \otimes y)$.

\begin{align} relerr & = \frac{\left|(x \otimes x) \ominus (y \otimes y) - (x^2 - y^2)\right|}{\left|x^2 - y^2\right|} \\ & = \left|\frac{(x \otimes x) \ominus (y \otimes y) - (x^2 - y^2)}{x^2 - y^2}\right| \\ & = \left|\frac{(x \otimes x) \ominus (y \otimes y)}{x^2 - y^2} - 1\right| \\ & = \left|\frac{\left\[(x^2 - y^2)(1 + \delta\_1) + (\delta\_1 - \delta\_2)y^2\right\](1 + \delta\_3)}{x^2 - y^2} - 1\right| \\ & = \left|\frac{(\delta\_1 - \delta\_2)y^2}{x^2 - y^2}(1 + \delta\_3) + (1 + \delta\_1)(1 + \delta\_3) - 1\right| \\ \end{align}

Since we want to bound this expression by some amount of the machine-$\epsilon$, we need to find when the first term is the largest. Which happen to be when $y$ is large, making the numerator large, and when $x$ is close to $y$, making the denominator small. We could probably stop there (as the paper does), but this doesn't provide an upper bound for the relative error.

Let's assume that $x = (1 + \delta\_x) y$ with $0 \< \delta\_x \ll 1$.

\begin{align} relerr & = \left|\frac{(\delta\_1 - \delta\_2)y^2}{(1 + \delta\_x)^2 y^2 - y^2}(1 + \delta\_3) + (1 + \delta\_1)(1 + \delta\_3) - 1\right| \\ & = \left|\frac{\delta\_1 - \delta\_2}{(1 + \delta\_x)^2 - 1}(1 + \delta\_3) + (1 + \delta\_1)(1 + \delta\_3) - 1\right| \\ & = \left|\frac{\delta\_1 - \delta\_2}{2 \delta\_x + \delta\_x^2}(1 + \delta\_3) + (1 + \delta\_1)(1 + \delta\_3) - 1\right| \\ \end{align}

In order to bound this expression, we will need a lower bound on $\delta\_x$. It needs to be greater than $0$ so that $x \neq y$ and the equations make sens. The smallest non-zero value it can take is $\delta\_x \ge \beta^{-p+1} = 2 \epsilon$.

Moreover we have: $-\epsilon \le \delta\_1 \le \epsilon$ and $-\epsilon \le \delta\_2 \le \epsilon$.

Therefore, we have: \begin{align} \delta\_1 - \delta\_2 & \le 2 \epsilon \\ 2 \delta\_x + \delta\_x^2 & \ge 4 \epsilon + 4 \epsilon^2 \\ \frac{\delta\_1 - \delta\_2}{2 \delta\_x + \delta\_x^2} & \le \frac{2 \epsilon}{4 \epsilon + 4 \epsilon^2} & = \frac{1}{2 + \epsilon} & \lt \frac{1}{2} \\ \end{align}

Hence: \begin{align} relerr & \le \left|\frac{\delta\_1 - \delta\_2}{2 \delta\_x + \delta\_x^2}(1 + \delta\_3)\right| + \left|(1 + \delta\_1)(1 + \delta\_3) - 1\right| \\ & \lt \frac{1 + \delta\_3}{2} + |\delta\_1 + \delta\_3 + \delta\_1 \delta\_3| \\ & \lt \frac{1 + 2 \epsilon}{2} + \epsilon + 2 \epsilon + 2 \epsilon^2 \\ & \lt \frac{1}{2} + 4 \epsilon + 2 \epsilon^2 \\ & \lt \frac{1}{2} + 5 \epsilon \end{align}

Meaning that we could get an answer between 50% and 150% of the true result. I was however unable to find an actual example by exhaustive search in the high numbers. The best I could find (or worse, depending how you look at it ^^) was: $$x = 1.340780783004664349 \times 10^{154}$$ $$y = 1.340780783004664051 \times 10^{154}$$ using 64 bit floats (53 bits mantissa). Which has a relative error of roughly $0.25$.

Given that the binary mantissa of these numbers looks pretty regular, there might be something special about them and my upper bound is not correct.

My guess is that when $x$ is the float right after $y$, then maybe the rounding error of $x^2$ is similar to that of $y^2$. Which would make $\delta\_1 - \delta\_2 \le \epsilon$ instead of $2 \epsilon$. If anyone can prove it, feel free to edit this answer.
> 3 votes

---
Tags: floating-point, numerical-analysis, error-estimation
---


# Question
Title: Rice's Theorem - usage on $DFA$ or $LBA$
I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.

However I am not sure about one question -

Can I use Rice's theorem on languages which are defined on $LBA$ or $DFA$? For example, the following language -

$$ALL\_{LBA} = \left \\{ \langle M \rangle \mid \text{$M$ is an LBA and $L(M) = \Sigma^\*$} \right \\}$$

Since an $LBA$ is a "private case" of a turing machine, I am not sure I can use Rice's theorem here to prove the language is undecidable.

# Answer
If when you say "$M$ is a $LBA$ (or $DFA$ or $PDA$)" you mean that $M$ has a *fixed decidable structure* (i.e. some properties of its internal state/transition structure) that forces its behaviour to be like a $LBA$ (or $DFA$ or $PDA$) then Rice's theorem cannot be applied directly.

For example, if "$M$ is a $DFA$", is formally defined as "$M$ has no left moves and always enters a halting state on the first blank symbol whatever the current state is" then

$ALL\_{DFA} = \left \\{ \langle M \rangle \mid \text{$M$ is a DFA and $L(M) = \Sigma^\*$} \right \\}$ is decidable

Note that even if "$M$ is a $LBA/PDA$" is formally defined using some decidable properties of the structure of $M$, the sets $ALL\_{LBA}$ and $ALL\_{PDA}$ are *undecidable* but the proof cannot rely on Rice's theorem: it must use the LBA/PDA ability to "parse" a valid partial computation trace (tape+state) of an arbitrary Turing machine $M$.
> 3 votes

# Answer
No, you can not.

To use Rice, we need to have an "index set", i.e. a set $A$ satisfying $\langle M\rangle\in A \land L(M)=L(N) \implies \langle N\rangle \in A$ for all TMs $M,N$. In other words, the set membership must only depends on the language of $M$, and nothing else.

$M$ being a DFA is not a property of the language of $M$.

For a concrete counterexample, consider

$$ A = \\{ \langle M\rangle \ |\ M\mbox{ is a DFA and } \epsilon\in L(M)\\} $$ If we could apply Rice, we would conclude that the set above is undecidable. However, we know it is decidable since 1) checking whether $M$ is a DFA is decidable and 2) checking whether an automaton accepts the empty string is decidable (for a DFA, simply check if the initial state is final).
> 2 votes

---
Tags: turing-machines, computability, rice-theorem
---


# Question
Title: Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?
I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.

Given:

$$CF\_{TM} =\\{ \langle M \rangle \mid \text{$M$ is a TM description and $L(M)$ is a context-free language} \\}$$

Are $CF\_{TM}$,$\space $ $\overline{CF\_{TM}}$ Turing-recognizable?

In order for a machine to be turing recognizable, there should exist a Turing machine that will halt and accept only string on that language, and for strings no in that language, it should reject or not halt at all.

So i am truly wondering about the relationship between context free languages and being Turing-recognizable, are $CF\_{TM}$, $\space $ $\overline{CF\_{TM}}$ Turing-recognizable?

# Answer
This question describes a nice situation to introduce a partial version of the generalized Rice's theorem.

### A partial version of the generalized Rice's Theorem

For $S$ be a subset of Turing-recognizable languages, let $L\_S$ be the set of TMs that recognize a language in $S$, that is, $$L\_S = \\{ \langle M \rangle \mid L(M) \in S \\}.$$ Suppose $L\_1 \in S$, $L\_1 \subset L\_2$ and $L\_2 \not\in S$. Then $L\_S$ is not Turing-recognizable.

### $CF\_{\text{TM}}$ is not Turing-recognizable.

$CF\_{\text{TM}}=L\_{\text{CFL}}$, where $\text{CFL}$ is the set of all context-free languages. Let $L\_1=\emptyset$ and $L\_2=\\{a^{n^2}\mid n\in \Bbb N\\}$. Then $L\_1\subset L\_2$, $L\_1\in \text{CFL}$, $L\_2\not\in \text{CFL}$. So, $L\_{\text{CFL}}$ is not Turing-recognizable.

### $\overline{CF\_{TM}}$ is not Turing-recognizable

$\overline{CF\_{\text{TM}}}=\\{ s : s\text{ is a string that does not encode a TM}\\}\sqcup L\_{\overline{\text{CFL}}}$, where $\overline{\text{CFL}}$ is the set of all non-context-free formal languages. Let $L\_1=\\{a^{n^2}\mid n\in \Bbb N\\}$ and $L\_2=\\{a^n\mid n\in \Bbb N\\}$. Then $L\_1\subset L\_2$, $L\_1\in \overline{\text{CFL}}$, $L\_2\not\in \overline{\text{CFL}}$. So, $L\_{\overline{\text{CFL}}}$ is not Turing-recognizable.

### Proof of the partial version of the generalized Rice's Theorem

Suppose $L\_S$ is recognized by a TM $M\_S$. We will construct a TM that recognizes $\overline{HALT\_{\text{TM}}}=\\{\langle M,w\rangle\mid M\text{ does not halt on }w\\}$, which is known as not Turing-recognizable, hence a contradiction. The TM works as follows.

---

On input $\langle M, w\rangle$:

1. Construct a TM $T\_{M,w}$ that works as follows:

On input $x$:

* Run $M\_1$ on $x$, and accept if $M\_1$ accepts. Here $M\_1$ is a TM that recognizes $L\_1$.
    * At the same time, also run $M$ on $w$. If $M$ accepts, run $M\_2$ on $x$, and accept if $M\_2$ accepts. Here $M\_2$ is a TM that recognizes $L\_2$.
2. Run $M\_S$ on $T\_{M,w}$, and accept if $M\_S$ accepts.

---

Note this TM accepts $\langle M,w\rangle$ if and only if $M\_S$ accepts $\langle T\_{M,w}\rangle$, which means $L(T\_{M,w})\in S$. Also note

$$L(T\_{M,w})=\begin{cases} L\_1 & \text{if $M$ does not halt on $w$},\\ L\_2 & \text{otherwise}, \end{cases}$$

so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{HALT\_{\mathrm{TM}}}$.

The above proof is a modified version of xskxzr's nice proof of his lemma in his answer.

### Exercises

**Exercise 1.** Show that a context-free language (that is defined by a context-free grammar) is Turing-recognizable. Show that a non-context-free formal language (that is defined by an unrestricted grammar and that cannot be defined by a context-free grammar) is Turing-recognizable.

**Exercise 2.** (One minutes or two) Check that both the question and this answer remain valid if we replace "context-free" by "regular".

**Exercise 3.** Show that $\overline{\text{CFL}}$, the set of all non-context-free formal languages given by their grammars properly encoded by some fixed scheme, is not Turing-recognizable. Hence, $L\_{\overline{\text{CFL}}}$ cannot be Turing-recognizable either.

**EXercise 3.** Read the full version of generalized Rice's Theorem. Can you prove it? (This might not be easy.)
> 3 votes

# Answer
Both of them are unrecognizable by the following lemma:

> *Lemma.* Let $\mathcal{L}$ be a set of languages. If there exists two language $L\_1$ and $L\_2$ such that:
>
> * $L\_1\subseteq L\_2$,
> * $L\_1\in \mathcal{L},L\_2\notin\mathcal{L}$, and
> * $L\_1$ is decidable by a decider $M\_1$, $L\_2$ is recognizable by a TM $M\_2$,
>
> then the language $L=\\{\langle M\rangle\mid L(M)\in\mathcal{L}\\}$ is unrecognizable.

*Proof.* Suppose $L$ is recognizable by a TM $M\_L$. We will construct a TM that recognizing $\overline{H\_{\mathrm{TM}}}=\\{\langle M,w\rangle\mid M\text{ does not halt on }w\\}$, which is known as unrecognizable, hence a contradiction. The TM works as follows.

```
On input <M, w>:
    1. Construct a TM N (using M and w) working as follows:
        On input x:
            1. Run M_1 on x, and accept if M_1 accepts
            2. Run M on w
            3. Run M_2 on x, and accept/reject if M_2 accepts/rejects
    2. Run M_L on <N>, and accept/reject if M_L accepts/rejects

```

Note this TM accepts $\langle M,w\rangle$ if and only if $M\_L$ accepts $\langle N\rangle$, which means $L(N)\in\mathcal{L}$. Also note

$$L(N)=\begin{cases} L\_2 & \text{if $M$ halts on $w$},\\ L\_1 & \text{otherwise}, \end{cases}$$

so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{H\_{\mathrm{TM}}}$.

---

Now if $\mathcal{L}$ is the set of context free languages, we can choose $L\_1=\emptyset$ and $L\_2=\\{a^nb^nc^n\mid n\ge 0\\}$, and using the lemma to show $CF\_{TM}=\\{\langle M\rangle\mid L(M)\in\mathcal{L}\\}$ is unrecognizable. If $\mathcal{L}$ is the set of non-context free languages, we can choose $L\_1=\\{a^nb^nc^n\mid n\ge 0\\}$ and $L\_2=\Sigma^\*$, and using the lemma to show $\overline{CF\_{TM}}$ is unrecognizable.
> 2 votes

# Answer
We can use Rice-Shapiro to prove that both are not recognizable.

Assume $CF\_{TM}$ is recognizable. Take any $M$ where $L(M)=\emptyset$. By Rice-Shapiro, since $\langle M \rangle \in CF\_{TM}$ we have that every $N$ such that $L(N)\supseteq L(M)=\emptyset$ (which is always true) satisfies $\langle N \rangle \in CF\_{TM}$. We reach a contradiction choosing $N$ so that $L(N)$ is not context-free.

Assume $\overline{CF\_{TM}}$ is recognizable. Take any $M$ where $L(M)=\\{0^n1^n2^n \ | \ n\in\mathbb N\\}$ which is not context-free. By Rice-Shapiro, since $\langle M \rangle \in \overline{CF\_{TM}}$ there must exist some $N$ such that 1) $L(N)\subseteq L(M)$, 2) $L(N)$ is finite, and 3) $\langle N \rangle \in \overline{CF\_{TM}}$. We reach a contradiction since $L(N)$, being finite, is context-free.
> 1 votes

---
Tags: turing-machines, computability, context-free
---


# Question
Title: Ε-R diagram with conditions , is it possible?
I want to create a database and model it with an E-R diagram. This database should be about a library. An entity is the member of the library, where the member can borrow books from the library. However , the member cannot borrow more than 5 books and cannot borrow any more books , if he hasn't returned every book of which the time to return it has expired. Ιs it possible to model this condition with an E-R diagram?

# Answer
> 1 votes
This can be expressed in a one to many relationship with a 0..5 end:

LibraryPatron 1 \<----\> 0..5 BorrowedBook

Using relational algebra they can be expressed using check constraints as Renzo suggested. Some ER tools may also allow you to express this as a constraint.

---
Tags: database-theory
---


# Question
Title: feature selection in decision tree classifier
i want to build decision tree classifier, and i have no idea how to extract feature from text (my file is text) can anyone help me? is BOW, N-gram orTF-IDF useful?

# Answer
This depends on your application but the trend is to use Deep Learning. That is, allow the algorithm to learn the features as opposed to do feature engineering (e.g. choose between BOW, n-gram etc).

See for example this paper (Gender Classification with Deep Learning by Aric Bartle, Jim Zheng) where they compare the performance of BOW/n-gram/vs Deep Learning via Recurrent Convolutional Networks. Deep Learning generally outperforms classic feature engineering.

https://cs224d.stanford.edu/reports/BartleAric.pdf
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Why 'let' can not be reduce to a lambda application in (extended) Calculus of Constructions
I do not understand the difference highlighted in the chapter 2.5 of the book Theorem Proving in Lean:

> Notice that the meaning of the expression let a := t1 in t2 is very similar to the meaning of (λ a, t2) t1, but the two are not the same. In the first expression, you should think of every instance of a in t2 as a syntactic abbreviation for t1. In the second expression, a is a variable, and the expression λ a, t2 has to make sense independently of the value of a. The let construct is a stronger means of abbreviation, and there are expressions of the form let a := t1 in t2 that cannot be expressed as (λ a, t2) t1. As an exercise, try to understand why the definition of foo below type checks, but the definition of bar does not.
>
> ```
> def foo := let a := nat  in λ x : a, x + 2
> def bar := (λ a, λ x : a, x + 2) nat
>
> ```

What is the explanation behind this?

# Answer
In an untyped language, those expressions would be equivalent. When working with types, instead, one might have a type while the other one has no type.

Assume that numbers and arithmetic operators all work on $\sf nat$. Then $e\_0 = 2+2$ can be typed as $\sf nat$. Now, we can try to perform a $\beta$-expansion, i.e. to "apply $\beta$ backwards", and reach $e\_1 = (\lambda x:{\sf nat}.\ x+2)2$.

$$(\lambda x:{\sf nat}.\ x+2)2 \to\_\beta 2+2$$

This new expression $e\_1$ would still have type $\sf nat$. But we could also go further to $e\_2=(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat}$.

$$(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat} \to\_\beta(\lambda x:{\sf nat}.\ x+2)2 \to\_\beta 2+2$$

Now, $e\_2$ can not be typed. If it had a type, every subterm of $e\_2$ would also be typeable, including $e\_2' = (\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2)$, but this subterm can not be typed. The only type we can assign here would be of the form

$$ e\_2' : \prod\_{\tau:{\sf Type}} (\mbox{something}) $$

in which case this would also be typeable:

$$ e\_2' \\, {\sf bool} \to\_\beta (\lambda x:{\sf bool}.\ x+2)2 $$

The above is nonsense, since $2$ is not a $\sf bool$, so it should not be bound to $x$.

Indeed, we just discovered that types are not preserved under $\beta$-expansion.

A first question arises:

> Couldn't we $\beta$-reduce the expression before typing?

Yes, and that's (roughly) what ${\sf let}\ \tau = {\sf nat}\ {\sf in}\ e$ does: it types $e$ *knowing* that what $\tau$ actually is.

And now one might counter with:

> If $\sf let$ works in that way, why don't we use the same technique for lambdas?

We can't do that, since lambdas are not always immediately applied to an argument. The syntax ${\sf let}\ x = t\ {\sf in}\ e$ shows what is the value of $x$, namely $t$. The syntax $(\lambda x. e) t$ also shows the value of $x$ but not all lambdas are used in that way: sometimes we want to use $(\lambda x. e)$ without an argument. Say, we want to pass that to another function $F (\lambda x. e)$, or build a pair of functions $(\lambda x. e, \lambda x. e')$. Here, we don't know what $x$ is. Unlike the $\sf let$ case, here $x$ could even take many values, e.g. if $F = \lambda k. k 0 + k 1$ then $F (\lambda x. e)$ makes $x$ to be $0$ on one call and $1$ in the other call.

So, $\sf let$ is less general than a lambda, and we can have a "special" typing rule for that.
> 5 votes

---
Tags: lambda-calculus, calculus-of-constructions
---


# Question
Title: Why finding the difference between the adjacent elements of the array to find the maximum difference?
I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum array but I don't get the following solution which first find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff\[\] of size n-1. The problems turns into finding the maximum sum subarray of this difference array.

Here is a working example plus my comments showing where I especially don't understand the algorithm.

```
// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;

/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1.
    // The array will hold the difference
    // of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];

    // Now find the maximum sum
    // subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1]; // I especially don't get why we add differences
        if (max_diff < diff[i])
            max_diff = diff[i]; // and why we update the max_diff as the sum of differences
    }
    return max_diff;
}

/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr[0]);

// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);

return 0;
}

```

# Answer
> 0 votes
Suppose that the original array is $a\_1,\ldots,a\_n$. The new array is $b\_i = a\_{i+1} - a\_i$ for $1 \leq i \leq n-1$. Note that $$ a\_j - a\_i = b\_i + \cdots + b\_{j-1}. $$ Hence $$ \max\_{\substack{i \< j \\ a\_i \< a\_j}} |a\_j-a\_i| = \max\_{i\<j} (a\_j-a\_i) = \max\_{i\<j} b\_i + \cdots + b\_{j-1}. $$

---
Tags: algorithms, arrays, maximum-subarray
---


# Question
Title: Counting the number of subsets with positive sum
I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\mathbf{v}\_j\ (0\leq j \< 2^n)$.

I only care about whether $\mathbf{s}\cdot \mathbf{v}\_j \> 0$. I would like to count all of the times this condition holds.

Question: As the naive algorithm has complexity $O(2^n)$, it blows up fast. What are my options for optimizing this for large $n$?

# Answer
Suppose that you could solve this in $T(n)$. Given a list of positive integers $a\_1,\ldots,a\_n$ and a target $T$, consider the two instances $a\_1,\ldots,a\_n,-T$ and $a\_1,\ldots,a\_n,-T+1$. Denoting by $N(\cdots)$ the number of positive sums, we get:

* $N(a\_1,\ldots,a\_n,-T)$ is the number of subsets of $\\{a\_1,\ldots,a\_n\\}$ whose sum is larger than $T$.
* $N(a\_1,\ldots,a\_n,-T+1)$ is the number of subsets of $\\{a\_1,\ldots,a\_n\\}$ whose sum is at least $T$.

By comparing these two numbers, you can solve SUBSET-SUM in time $T(n+1)$.

(There are some potential differences in the computation models, that I leave you to ponder.)

There is a simple $O(2^{n/2})$ algorithm, which proceeds as follows. We break the array $s\_1,\ldots,s\_n$ into two equal halves. We compute an ordered list $A\_1,\ldots,A\_{2^{n/2}}$ of all sums of the first half, and an ordered list $B\_1,\ldots,B\_{2^{n/2}}$ of all sums of the second half. This takes time $O(2^{n/2})$ if done carefully (by iterative merging). We put a pointer $j$ at $B\_{2^{n/2}}$, and decrease it until $A\_1 + B\_j \le 0$. The value of $j$ tells us the number of pairs $(1,j')$ satisfying $A\_1 + B\_j \> 0$. Then we do the same for $A\_2$ — note that we can start the scan at the current value of $j$; and so on. This phase also takes $O(2^{n/2})$.
> 3 votes

---
Tags: algorithms, subset-sum
---


# Question
Title: Decidable problems for which no concrete decision procedure is known
I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.

I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.

# Answer
Here is a trivial example of such a problem: consider any yes-no question with an unknown answer, e.g. $P=NP$. For any $n \in \mathbb{N}$, let $A(n)$ be true iff $P=NP$. Then $A$ is decidable by one of two decision procedures:

1. Always return "true".
2. Always return "false".

But you need to solve $P=NP$ to know which one.
> 2 votes

# Answer
For the record, I found the one in graph theory, which is called `graph minor theorem`, or `Robertson–Seymour theorem`.

https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour\_theorem

Indeed, this theorem is proved non-constructively.
> 1 votes

---
Tags: time-complexity, decision-problem
---


# Question
Title: Time complexity of a tree-based algorithm
I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution.

## Problem Statement

> Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
>
> For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages are decodable. For example, '001' is not allowed.

I made an assumption that my solution should accept any type of mapping, not just the one mentioned in the question. So the running time of the algorithm is parametrized by the encoded message length and the type of mapping used.

## Attempted Solution

```
class Node:

    def __init__(self, val):
        self.val = val
        self.children = []

    def add_child(self, child):
        self.children.append(child)

def count_encodings(cipher, mapping):
    # what is the longest possible map value
    longest_val = max([len(str(x)) for x in mapping.values()])
    root = Node('')
    create_cipher_subtree(root, cipher, longest_val, mapping)
    return count_leaves(root)

def create_cipher_subtree(node, cipher, longest_val, mapping):
    for part_len in range(1, min(longest_val, len(cipher)) + 1):
        curr_part = cipher[:part_len]
        if curr_part in mapping.values():
            child = Node(curr_part)
            node.add_child(child)
            remaining_part = cipher[part_len:]
            if remaining_part:
                create_cipher_subtree(child, remaining_part, longest_val, mapping)

def count_leaves(node):
    if not node.children:
        return 1
    count = 0
    for child in node.children:
        count += count_leaves(child)
    return count

```

We can then reproduce the example solution as follows:

```
from string import ascii_lowercase
mapping = {k: str(v) for v, k in enumerate(ascii_lowercase)}
cipher = '111'
print(count_encodings(cipher, mapping))

```

In short, this solution constructs a tree, like this:

```
            ''
       '1'     '11'
    '1'  '11'     '1'
 '1'

```

Then the number of leaf nodes is counted.

## Explanation

First, the algorithm checks all possible values in the mapping and records the length of the longest value (`longest_val`).

We then create a tree, where each node's `val` field is a part of the encoded message (`cipher`) that corresponds to a single mapping value; the root is the only node which has `val` as empty string. Concatenation of nodes' `val` fields along the path from the root to a leaf is one possible way of encoding.

The tree is created as follows:

1. Check if the first character of `cipher` can be interpreted as a mapping value.
2. If yes, create a node with that value recorded and make it a child of root. Then, pass the rest of the `remaining_part` of the encoded message (everything past the first character) to the child and repeat the process from there.
3. Check if the first two characters of `cipher` can be interpreted as a mapping value.
4. Repeat step 2, but now `val` is two characters. The `remaining_part` would be everything in the encoded message past the first two values. This would create another child node of root.
5. If `longest_val` was 3, we would then check if the first 3 characters of `cipher` can be interpreted as a mapping value.... And so on.

After the tree is created, we count the number of leaf nodes, which corresponds to number of possible messages that can produce the provided encoding.

## Complexity Analysis

I know that creating the tree of all possible ways the message could have been encoded might have been an overkill for this problem (in terms of space use), but doing it this way helped me better reason about the solution.

I am now unsure about the exact relation between a mapping choice and message length, and the answer to the question. What is the time complexity of this solution?

I am more interested in how various mappings affect the complexity. E.g. if some of the values in the mapping were 3-digit numbers, then many nodes in the tree would have 3 children. Does this increase the complexity of the algorithm? How would one capture this fact when writing Big-Oh expression for the algorithm?

# Answer
> 2 votes
You can show a simple exponential lower bound for you algorithm as follows.

1. Assume we have a $d$ digit encoding (2 in your initial example).
2. For any cipher text of length $n$ we can create a worst-case encoding of $n$ 1's.
3. Now we divide the input into $n \ / \ d$ segments of length $d$.
4. For any of these segments, we have $2^{d-1}$ ways of decoding it.
    * Take $d = 4$ for example, with a segment "1111" we have the following decodings:
        1. "1111"
        2. "1", "111"
        3. "1", "1", "11"
        4. "1", "1", "1", "1"
        5. "1", "11", "1"
        6. "11", "11"
        7. "11", "1", "1"
        8. "111", "1"
5. Now we can decode all of these $n \ / \ d$ segments separately so we can multiply this together to get:

$$(2^{d-1})^{n/d} = 2^{(d-1)n/d}$$

---

You can get a tighter bound for this however by noting that the number of decodings for a string of ones is:

$$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ \vdots & \vdots\\ 2^{d-1} & n = d\\ \sum\_{i = 1}^d f(n - i) \end{cases}$$

If we plug in for $d=2$ we actually see something familiar: $$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ f(n-1) + f(n-2) \end{cases}$$ This is the Fibonacci Sequence! This, we know is exponential in $n$. If you try $d=3$ you get the Tribonnaci Sequence. As you increase $d$ you simply get higher order Fibonacci sequences. All of these will be exponential in the worst case.

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


title: Coprimes satisfying a pair

text:
# Question
Title: Coprimes satisfying a pair
We know that number of coprimes less than a number can be found using Euler's totient function. But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ and coprime to $p$, is there any efficient method?

# Answer
No. This is as hard as factoring, and there is no known efficient algorithm for factoring. In particular, there is a standard reduction to show that if you could compute Euler's totient function efficiently, then you could factor efficiently.
> 1 votes

---
Tags: algorithms, time-complexity, number-theory, primes
---


# Question
Title: Given two data feeds, find out if they capture the same information
Say, there are two camera feeds, how can I establish if they were filming the same scene? It seems plausible that there are algorithms that somehow calculate mutual information and detect "causality violations", determining that the other feed is most probably not another perspective of the same source, and that in the presence of noise.

If it is unknown what kind of properties (e.g. dimensionality, physics) the environment that the data feeds capture has, are there algorithms that can construct the transition logic from scratch?

In computer vision, this problem is apparently called 'image registration'.

# Answer
The problem of finding the relationship between two scenes shot from two different angles is known as the correspondence problem and there is a lot of literature on how to approach it; I suggest you start by reviewing the research literature on methods for solving this. In particular, I'd suggest that if you can consistently find a correspondence between the two images, you might conclude that they are from the same feed; and if you can't, you might conclude that they aren't.
> 1 votes

---
Tags: algorithms, information-theory, image-processing
---


# Question
Title: Could neural networks be considered metaheuristics?
A metaheuristic is defined as

> a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem

So my question is if a neural net could be consider in that definition

# Answer
> 1 votes
The notion of a "metaheuristic" is not something with a precise formal definition. Personally, a neural network isn't something *I'd* consider a metaheuristic; it doesn't seem quite like what we have in mind when we talk about metaheuristics. But you can always use language however you like, as long as it is clear to others and doesn't cause confusion.

# Answer
> 1 votes
To add to the other answer(s), you can certainly use neural networks (or machine learning in general) *in conjunction with* metaheuristics. Indeed, there are several such approaches in the literature, for example, in trying to predict "good" initial solutions for some search method.

# Answer
> 0 votes
When you train NN all things you do is considered methaheuristic, if you use search among NNs to pick best it is also metaheuristic.

In this context, simple usage of NN is not considered as such, but people rarely split hair over definition. What is left is usage, when NN is used as screening of solutions or other methods (cascade of nonhomogenous nets) then it is methaheuristic, otherwise it is simply search/classification tool.

---
Tags: neural-networks
---


# Question
Title: Find binary number with max hamming distance wrt given set of binary numbers
Suppose we have a set $A$ of binary numbers with the same length $n$. For example (with $n=8$):

$A = \\{ 10010011, 01011011, 00010010, 11110001\\}$

Now, I want to find the binary number $z$ (also with $n$ bits) such that the minimum hamming distance between $z$ and any of these numbers is maximized.

i.e. $z = \arg \max \\{ d(x,A) \mid x \in X\\}$

with

$d(x,A) := \min \\{ d(x,a) \mid a \in A\\}$

where $X$ is the set of all $n$-bit binary numbers, and $d(x,a)$ the hamming distance between $x$ and $a$.

Is there any efficient algorithm for this?

Obviously, if $n$ is small enough we can brute-force this, but I'm looking for something more efficient when $n$ is large. The size of $A$, on the other hand, can be assumed relatively small, so any algorithm polynomial in $|A|$ is fine. Also, it does not have to be an exact algorithm. Any algorithm that approximates the correct answer is welcome too.

# Answer
> 2 votes
Here is the decision version of the problem, which we can the problem of farthest string.

> Given $m$ length-$n$ binary strings $s\_1, s\_2, \cdots, s\_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s\_i)\ge k$ for all $i$.

There is the problem of closest string.

> Given $m$ length-$n$ binary strings $s\_1, s\_2, \cdots, s\_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s\_i)\le k$ for all $i$.

### Farthest string is dual to closest string.

Let $c$ denote the map that changes a binary string to its 1's complement, i.e., switching 0 and 1 everywhere. For example, $c(010010111)=101101000$. Note that $c\circ c = Id$.

Given an instance of farthest string $(m, n, s\_1, s\_2, \cdots, s\_m, k, s)$, we can construct an instance of closest string $(m, n, c(s\_1), c(s\_2), \cdots, c(s\_m), n-k, s)$. Call this transformation of instances $r$.

For every string $s$ of length $n$, $$d(s,s\_i)+d(s, c(s\_i))=n.$$ Hence $$d(s,s\_i)\ge k\text{ for all }i\ \Longleftrightarrow\ d(s,c(s\_i))\le n-k\text{ for all }i. $$

So $r$ converts a yes-instance of farthest string to a yes-instance of closest string. Symmetrically, $r$ converts a yes-instance of closest string to a yes-instance of furthest string. Furthermore, $r\circ r= Id$.

So $r$ is a linear duality reduction between farthest string and closest string.

### All results about closest string are about farthest string.

That is because of the duality reduction. Now we can dive into the Wikipedia article on closest string to see find what we have about closest string.

In particular, we know that farthest string is NP-complete. We can check approximability, fixed-parameter tractability as well.

---
Tags: algorithms, hamming-distance
---


title: Enumerators and recognizers

text:
# Question
Title: Enumerators and recognizers
I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}\_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ordering of inputs) for all words $w \in L$ (with $L \in \mathcal{L}\_{RE}$) to be printed by $E$.

Now suppose $E$ lists down all words $w \in L$ by taking as input the computation history of a word $w$. The computation history is derived using transitions of a Turing Machine $TM$ that recognizes $L$. $E$ operates by checking if all segments of the computation history are valid given transitions of $TM$. To print $w$, $E$ uses a homomorphism, i.e. by printing the first segment of the computation history. In this case, the set of all words that enumerated by $E$ is equal to $L$.

But if the enumerator $E$ is a Turing Machine itself, call it $TM^E$, is it accurate to say that $TM^E$ recognizes $L$? If true, there seems to be a contradiction since $E$ does not loop - since it can check whether or not a computation history input from a lexicographic ordering follows the transitions of $TM$ and results in $w$.

# Answer
An enumerator has no input. It works as follows:

1. **Generate** the next computation history.
2. Check if the computation history is valid.
3. If the computation history is valid, print the corresponding string.
4. Go to Step 1.

I'm unclear how your $\mathrm{TM}^E$ works. I can image the following possibilities:

1. On input $w$, $\mathrm{TM}^E$ enumerates all computation histories and see if $w$ matches some computation history. In this sense, there is no contradiction. $\mathrm{TM}^E$ has to endlessly enumerate computation histories if $w$ matches no computation history (i.e. $w\notin L$), so it may loop.
2. On input $w$, $\mathrm{TM}^E$ firstly constructs the computation history corresponding to $w$... but wait, how do you construct such a computation history while it may not even exist (i.e. $w\notin L$)?
3. On input $w$, $\mathrm{TM}^E$ checks whether $w$ is a valid computation history, and accepts if it is valid. In this sense, $\mathrm{TM}^E$ does not accept $L$. Instead, it accepts **the language of valid computation histories**. This language is different from $L$.
> 2 votes

---
Tags: turing-machines, computability, enumeration
---


title: Loop-Invariant for a program fragment

text:
# Question
Title: Loop-Invariant for a program fragment
Q) Consider the following program fragment:

```
var x,y:integer;
x:=1; y:=0;
while y < x do
begin
  x:=2∗x;
  y:=y+1;
end;

```

For the above fragment , which of the following is a loop-invariant ?

A) x=y+1
B) x=(y+1)2
C) x=(y+1)2y
D) x=2y
E) None of the above, since the loop does not terminate

Since, Loop-Invariant is something which is true before and after each iteration of a loop. So, according to the definition, I am getting answer as (D) but I have a doubt whether termination of that loop is necessary or not for the given code. **One of the properties of algorithm says :- algorithm should always terminate after finite no. of steps.** So, if the question is about Pseudocode then I will definitely mark answer as (D) but since it is program fragment, So I am confused between options (D) and (E).
So, My Doubt is definition of loop-invariant is also true for the loop in the code which is written in any language like C,C++ etc.
Please help.

# Answer
The question asks for a loop invariant. This has nothing to do with termination. (D) does look reasonable but you may want to check with the usual tools such as Hoare logic, that (D) holds before the loop and is re-established by the loop body if the guard holds.

PS Your idea of an algorithm may need some work.
> 0 votes

---
Tags: algorithms, loop-invariants
---


# Question
Title: How to prove the set of Turing machines that accept a string and its mirror is undecidable?
I'm trying to prove the undecidability of the following language.

$$L=\\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ rejects }w'\\},$$ where $w'$ is the mirrored version of $w$.

I know that my first steps should be to find a reduction from $A\_{\text{TM}}$, which is undecidable but the rejection part of the mirrored string is proving troublesome.

# Answer
> 0 votes
It's the standard reduction from the Halting problem: given a machine $M$ and an input $w$ to it, construct a new machine $M$ that accepts your favourite string and rejects its reverse if $M(w)$ halts, and accepts nothing if $M(w)$ does not halt.

This technique applies to any question of the form "Prove that it's undecidable whether a Turing machine accepts a string or language of some specific kind."

Or just use Rice's theorem, if you've been taught that.

---
Tags: turing-machines, undecidability
---


# Question
Title: Can a TM recognize whether another TM recognizes a non-empty language?
Let $$L\_1 = \\{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\\}.$$ Is $L\_1$ recognizable? If so, can you give me a pseudo-algorithm?

My attempt:

I wanted to study reachability the same way one does with DFA/NFA. However although a transition might be defined between $q\_i$ and $q\_j$ for $ x \in \Gamma $ is no guarantee that the configuration is possible.

# Answer
I will use the following definition of $L(M)$: it is the set of inputs for which $M$ halts.

I will use the following definition of *recognizable*: a language $L$ is recognizable if there exists a Turing machine $M$ such that $L = L(M)$.

In order to recognize $L\_1$, on input $\langle M \rangle$, we simulate $M$ on all possible inputs (using dovetailing), and if $M$ halts on any input, we halt.

In order to simulate $M$ on all possible inputs, we list all possible inputs in a sequence $x\_1,x\_2,\ldots$, and then work as follows:

* Initiate a run of $M$ on $x\_1$, and advance it one step.
* Initiate a run of $M$ on $x\_2$, and advance both existing runs by one step each.
* Initiate a run of $M$ on $x\_3$, and advance all three existing runs by one step each.
* And so on.

If $M$ halts on any input, then we will eventually notice it, and then immediately halt. Conversely, if $M$ never halts, then we will also never halt.
> 1 votes

# Answer
Reachability is unlikely to work. For a DFA/NFA, there are only finitely many states to consider but, for a Turing machine, there are infinitely many possible configurations of the tape and state.

Instead, you need to simulate the machine you're interested in on possible inputs and see if it accepts any of them. In principle, you'd want to try each possible input in order (e.g., $\epsilon$, $0$, $1$, $00$, $01$, $10$, $11$, $000$, ...) but there's a problem with this. If the machine doesn't halt on some input, you'll never begin to consider the next input. You get around this with a technique known as "dovetailing". You simulate your machine running for one step on the first input. If that's enough to work out the answer, you're done. Otherwise, you simulate the machine running for two steps on each of the first two inputs. If that's not enough, three steps on the first three inputs, and so on.

I'll leave it to you to check that this technique really works and to use it to answer your question.
> 1 votes

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


# Question
Title: Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?
To make my question more concrete, here is an example I am stuck on.

I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.

We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c\_1, c\_2, n\_0 \> 0: \forall n \> n\_0 . c\_1 n^3 \log(n) \leq T(n) \leq c\_2 n^3 \log(n)$.

Given that I assume the proof should go somewhat as follows:

**To show**: $\exists c\_1, c\_2, n\_0 \> 0: \forall n \> n\_0 . c\_1 n^3 \log(n) \leq T(n) \leq c\_2 n^3 \log(n)$

To do this we can use strong induction.

Let $P(n)$ be $c\_1 n^3 \log(n) \leq T(n) \leq c\_2 n^3 \log(n)$.

Take $n$ to be an arbitrary natural number.

**Induction hypothesis**: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.

It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n \> n\_0 . T(n) \leq c\_2 n^3 \log(n)$.

It follows that (taking $\log$ to be in base $2$):

$$ \begin{align\*} P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c\_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\ &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c\_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\ & \Leftrightarrow T(n) \leq 8c\_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\ & \Leftrightarrow T(n) \leq c\_2n^3\log(n) + n^3 - c\_2n^3log(2) \\ & \Leftrightarrow T(n) \leq c\_2n^3\log(n) + n^3 - c\_2n^3 \leq c\_2n^3\log(n) \ \text{ (if $c\_2 \geq 1$)} \end{align\*} $$

So we have $P(n)$.

And as such $\exists c\_2, n\_0 \> 0: \forall n \> n\_0 . T(n) \leq c\_2 n^3 \log(n)$.

**My problem:**

So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.

And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c\_2 n^3 \log(n) \leq T(n)$.

Can someone provide some insight into how to approach this?

# Answer
> 1 votes
You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases} 8 & n = 2\\ 8T\left(\tfrac{n}{2}\right) + n^3 & n \> 2\\ \end{cases}$$

Claim: $T(n) = n^3 \log\_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log\_2 2 = 8$

Inductive Case ($n \> 2$):

$$\begin{align\*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = 8\left(\tfrac{n^3}{8} \log\_2 \tfrac{n}{2}\right) + n^3\\ & = n^3 \log\_2 \tfrac{n}{2} + n^3\\ & = n^3 \log\_2 n - n^3 \log\_2 2 + n^3\\ & = n^3 \log\_2 n - n^3 + n^3\\ & = n^3 \log\_2 n & \square \end{align\*}$$

Thus $T(n) = n^3 \log\_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds.

---

However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases} f(b) & n = b\\ aT(n/b) + f(n) & n \> b \end{cases}$$

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align\*} T(n) & = aT(n/b) + f(n)\\ & = a(aT(n/b^2) + f(n/b)) + f(n)\\ & = a^2T(n/b^2) + af(n/b) + f(n)\\ & \vdots\\ & = \sum\_{i = 0}^{\log\_b n - 1} a^{i} f\left( \frac{n}{b^i}\right) \end{align\*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align\*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = \sum\_{i = 0}^{\log\_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\ & = \sum\_{i = 0}^{\log\_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\ & = \sum\_{i = 0}^{\log\_2 n - 1} n^3\\ & = n^3 \log\_2 n\\ \end{align\*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.

---

Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases} 12 & n = 3\\ 5T\left(\tfrac{n}{3}\right) + n^2 + n & n \> 3\\ \end{cases}$$

# Answer
> 0 votes
You can prove a recurrence of the form $$aT(n/b) + f(n)$$ if the constraints for master theorem hold. A bad value for f(n) might invalidate that.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Finding two languages satisfying conditions
> Let $$E\_{TM} = \left \\{ \langle M\rangle \mid L(M) = \emptyset \right\\}$$
>
> Prove that there are two languages $L\_1, L\_2$ such that
>
> 1. $L\_1, L\_2 $ are infinite.
> 2. $L\_1 \cup L\_2 = E\_{TM}$
> 3. $L\_1 \cap L\_2 = \emptyset$
> 4. $L\_1$ is decidable, $L\_2$ is not recognizable.

I'm finding it really hard to find two languages that satisfy these conditions.

Especially the second condition, which two language unify to $E\_{TM}$?

# Answer
> 2 votes
A slight improvement:

$L\_2 = E\_{TM} \backslash L\_1 $ (since we require that $L\_1 \cap L\_2 = \emptyset$).

$L\_1$ must be a language of turing machines, i.e. $L\_1 = \\{\langle M\rangle \mid \dots\\} $, so that $L\_1 \cup L\_2 = E\_{TM}$.

So let's set $L\_1 =$ $\\{\langle M\rangle\mid C\_0\text{ is a reject state}\\}$.

The following holds:

* $L\_1 $ is infinite and decidable (easy to decide given $M$, what the configuration of the first state is).
* $L\_2 $ is infinite and unrecognizable.

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