# Question
Title: What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?
What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?

Example:

```
      15
    /    \
   10     5
  /  \   / \
 2    8 1   4

```

# Answer
> 2 votes
It is called a SumTree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.

# Answer
> 0 votes
Like others have pointed out there is no name for it but it looks like a Binary Search Tree or a version of it AVL or WBT that is augmented.

---
Tags: data-structures, trees
---


# Question
Title: Emulating equal operator using multiplication
I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use multiplication at the end.

Basically I want to find $f$ and $g$, such that:

$$ f(A) \cdot g(B) = \begin{cases} 1, & A = B \\ 0, & A \ne B \end{cases} $$

For example, if I use $g(x) = 1/x$ I get something close to what I want $$ A \cdot 1/B = \begin{cases} 1, & A = B \\ A/B, & A \ne B \end{cases} $$ Is it possible to do that? If so, what are the functions $f$ and $g$ that I should use?

# Answer
Suppose that $f,g$ were functions satisfying $f(A) g(A) = 1$ and $f(A) g(B) = 0$ if $A \neq B$. Take any $A \neq B$. Then $f(A) g(B) = 0$, and so either $f(A) = 0$ or $g(B) = 0$. If $f(A) = 0$ then $f(A) g(A) = 0$, and if $g(B) = 0$ then $f(B) g(B) = 0$. So no such functions exist.
> 4 votes

---
Tags: arithmetic, boolean-algebra
---


# Question
Title: What textbooks includes explanations of advanced data structures found commonly in competitive programming?
While looking through some problems on CodeForces, I noticed that there were several problems that required knowledge of techniques that just aren't covered in standard algorithm texts.

Topics that I want to understand include

* segment trees, least common ancestor, range-minimum query
* Fenwick trees
* heavy-light decomposition
* interval trees
* Hopcroft–Karp algorithm
* implementations of tries
* wavelet trees

There doesn't seem to be any book that comprehensively looks at any of those techniques. The only organized resource that I could find was a list of articles on GeeksForGeeks, but much of the site doesn't seem self-contained and linearly ordered the way a textbook would be. It's fine if not all of the techniques I've listed are covered, but I'd prefer a book that covered as much of it as possible. Any help?

# Answer
Here are two books written especially for competitive programming:

* "Guide to Competitive Programming", Antti Laaksonen:

The book is based on the book "Competitive Programmer's Handbook" by the same author, which was already really good. This handbook is still available for free on the author's website. The commercial version is more comprehensive and contains more topics.
* "Competitive Programming 3", by Steven Halim and Felix Halim:

Pretty much the classic book for learning competitive programming. Maybe a little bit dated.
> 4 votes

---
Tags: algorithms, data-structures, books
---


title: What exactly is a "binary file"?

text:
# Question
Title: What exactly is a "binary file"?
I suspect this may be more of a concept / theory question, but, I haven't been able to wrap my brain around what exactly a binary file is.

I've read links such as the below:

https://en.wikipedia.org/wiki/Binary\_file

https://betterexplained.com/articles/a-little-diddy-about-binary-file-formats/

But, the piece of the puzzle that's confusing me, is that ALL files are stored as 1's and 0's on a hard-disk, or, in RAM, etc. (i.e. there's no physical engraving of the hex characters "6F" onto a disk platter for example; it's still a binary format that the data is stored in).

So, if all files are stored as binary, then, presumably it's an operating-system, (& filesystem) concept to refer to something as "binary" file?

# Answer
> -1 votes
A binary file is a file that is simply **not** a text file. It means that a bin file has a **specific format** (mp3, exe, jpg...) and can not be interpreted only as a character sequence. There are many ways data can be formatted and read.

---
Tags: filesystems, storage, binary
---


# Question
Title: Subgraph Isomorphism checking in Multigraphs
I am considering the following problem:

> **Input**: 2 Graphs **G=(V,E), H=(V',E')**. **G** and **H** are directed multigraphs
>
> **Question**: Find a subgraph in **G** which is isomorphic to **H**

1. Is there any algorithm available for checking subgraph isomorphism in Multigraphs (specifically for multiple edge types) ?
2. If yes, what is the complexity?

# Answer
> 3 votes
Submultigraph isomorphism is clearly **NP** complete:

* it's easily seen to be in **NP** (an isomorphism can be specified in space polynomial in the size of the graphs, and it's easy to check that a proposed isomorphism is valid);
* it includes the **NP**-complete subgraph isomorphism problem as a special case.

The more interesting question is what the best known algorithms are; I'm afraid I can't help with that.

---
Tags: graphs, np-complete, graph-isomorphism
---


# Question
Title: Find most stable combination of a vector with itself at different periods
I receive a vector of varying length such as `[0, 1, 2, 3, 2]`. The value corresponds to the yield and its position to a time slot. Hence, at the first time slot the yield is zero, at the second period it is 1, etc.

I need a procedure that can combine this vector with itself at varying periods in order to ensure that the sum of the yields are the "most possibly" stable. Ideally it will be completely but I doubt that it is always possible.

I also need to make sure that it is indeed a periodic solution.

Below 2 examples that I solved by hand and a list of other example I don't know how to solve:

First one:

```
     [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
           [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
                 [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
sum = 0  1  2  4  4  4  4  4  4  4  4  4...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 4

```

Second one:

```
     [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
        [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                       [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                          [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
sum = 0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 1

```

However I could not find a pattern for the following vectors and I am searching for an algorithm that could identify the best pattern for any such one:

```
[0, 0, 2, 3, 2]
[0, 0, 2, 0, 3, 0, 4, 0, 2]

```

**Precision 1**: The vector will always start with at least a zero, but there can be many more, and it will always finish with a value above zero.

**Precision 2**: The solution should be the shortest periodic design that allows a stable sum of yield.

**Retry at the problem specification**: We have a production mean 'A' to grow plants. Each plant has specs as to how it grows, represented by a given vector as presented above. For a given 'A', once a plant production cycle is over, you can start a new one. We want to model a stable plant production with as few 'A' as possible.

# Answer
> 1 votes
**Made up rule nr 1:** Every number has to be part of the sum. Therefore the sum cannot be x, if there is a number b, such that no combination of numbers can add up to x-b.

So for \[0, 0, 2, 3, 2\]:

* the sum cannot be 2 (because 3 cannot be part of that)
* it cannot be 3 (because 3 - 2 = 1 and there is no combination of numbers that add up to 1 (rule 1))
* it cannot be 4 (because 4-3 = 1 again, (rule 1))
* it cannot be 5 (because there are twice as many 2-s as 3-s)
* it cannot be 6 (because in case of 3-s, only two rows in exactly the same place can make up that number, and the 2-s would then form 4-s, which cannot sum up to 6)

Therefore for the specific case of \[0, 0, 2, 3, 2\], the simplest solution is to have the value of 7

Perhaps this complicated reasoning helps to consider the future vectors as well :)

\[0, 0, 2, 0, 3, 0, 4, 0, 2\] is more difficult though. While not considering too thoroughly, it looks like for that as well, there isn't anything better than the trivial solution.

**Trivial solution:**

```
[a, b, c ....]
   [a, b, c ....]
      [a, b, c ....]
      ...

```

---
Tags: algorithms
---


title: Definition of a TM accepting a word

text:
# Question
Title: Definition of a TM accepting a word
The following is a quote from Sipser's "Introduction to the theory of computation"

> A Turing machine $M$ accepts input $w$ if a sequence of configurations $C\_{1}, C\_{1}, \ldots , C\_{k}$ exists, where
>
> 1. $C\_{1}$ is the start configuration of $M$ on input $w$,
> 2. Each $C\_{i}$ yields $C\_{i+1}$ , and
> 3. $C\_{k}$ is an accepting configuration.

The "if a sequence of configurations $C\_{1}, C\_{1}, \ldots , C\_{k}$ exists" is a bit confusing. This is a deterministic TM, so there is only one sequence of configurations for a given machine and word, right? For instance, wouldn't the following do as a definition?

> A Turing machine $M$ accepts input $w$ if the state in the final configuration in $M$'s run on $w$ is an accepting state

Obviously, one has to formally define first what *the run* of a machine on a given word means.

# Answer
There are two reasons to use this kind of definition:

1. It is a formal way to define the run of the machine.
2. It generalizes to the nondeterministic setting.

In the deterministic setting, an equivalent definition would be:

> Define a (possibly finite) sequence $C\_1,C\_2,\ldots$ as follows:
>
> 1. $C\_1$ is the start configuration of $M$ on input $w$,
> 2. For $i \geq 1$, $C\_{i+1}$ is the unique configuration yielded by $C\_i$, if such a configuration exists.
>
> The machine $M$ accepts the input $w$ if the sequence is finite, and the last configuration is accepting.

This is not dramatically better than the quoted definition, and it doesn't generalize to the nondeterministic setting. It is a matter of taste which of the two to prefer.
> 3 votes

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


# Question
Title: How does machine learning relate to artificial intelligence?
For example, is it a subset?

Are they two separate fields in Computer Science?

I have hear conflicting information: one professor said they are synonyms. However, in the courses taught at Stanford CS they are two distinct classes:

CS221 (Artificial Intelligence)

and

CS229 (Machine Learning)

# Answer
Machine Learning is a subset of (the scientific field of) Artificial Intelligence.

## What is ML?

Machine Learning is defined by Tom Mitchel:

> A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

Hence: When you write an algorithm that gets better the more data you give it, then you can call it ML.

## What is AI but not ML?

## See also
> 6 votes

# Answer
**Is it a subset?**

Yes, it's a subset of artificial intelligence and artificial intelligence is a subset of computer science. AI is a simulation of human intelligence that is coupled with processes, i.e.,

*self learning* (neither program nor an agent has the capabilities of acquiring of information and rules for using the information).

*reasoning* (neither program nor an agent uses the rules to reach approximate conclusions or definite conclusion and self correction. Are they two separate fields in Computer Science?

**I have heard conflicting information. One professor said they are the synonyms.**

Today machine learning and artificial intelligence are becoming buzz words all over the media, various applications have been developed, but out of 100%, you find that only 40% is a real application that's considered AI, then the 60% are computational intelligence applications.

*Hint*: artificial intelligence is the mother of machine learning; algorithms which corrects their mistakes and makes decisions without human help.
> 0 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular
We know that $L=\\{0^{m^2}\mid m\geq 3 \\}$ is not a regular language. However $L^\*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can be generated just by concatenating $0^9$. Hence we can represent $L^\*$ using a FSM.

**My Question :**

1. Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?
2. If we consider $m^2$ to be a function such that we get $L^\*$ is regular, will it also be regular for $m^3$?

# Answer
> 6 votes
Consider the language $$ L = \\{ 0^{m^k} : m \geq m\_0 \\}. $$ Since $m\_0$ and $m\_0+1$ are relatively prime, so are $m\_0^k$ and $(m\_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m\_0^k$ and $(m\_0+1)^k$, implying that $$L^\* \supseteq \\{ 0^m : m \geq M\_0 \\}$$ for some $M\_0$, and so $L^\*$ is regular. Using the classical formula of the coin problem applied to $m\_0^k$ and $(m\_0+1)^k$, we can upper bound the optimal value of $M\_0$ by $$ M\_0 \leq (m\_0^k-1)((m\_0+1)^k-1). $$ For example, the case considered in your post has $k=2$ and $m\_0=3$, and this gives the bound $M\_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.

Recently it has been shown that it is $\Sigma\_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\\{ m^k : m \geq m\_0 \\}$ has a lot of structure, and so the problem might be feasible.

# Answer
> 1 votes
If a language contains $(0^n | 0^m)^\*$ with gcd (n, m) = 1, then every integer $k ≥ n \cdot m$ is the sum of multiples of n and m, so the language contains $(0^k)$, $k ≥ n \cdot m$.

This is the case here because gcd ($3^2$, $4^2$) = gcd (9, 16) = 1, so the language contains $0^k$, $k≥144$. And it contains a few more strings $O^k$. And that is a regular language. (In this case, the language actually contains $0^k$, $k≥88$).

If you had a different language L, using terms $m^k$, $m ≥ m\_0$ with large k and $m\_0$ instead of $m^2$ for $m≥3$, then finding the exact grammar that demonstrates L is regular might be quite hard to find, but the argument above shows that it exists.

---
Tags: automata, regular-languages, number-theory
---


# Question
Title: Solving the Path Explosion Problem in Symbolic Execution
Looking at the Symbolic Execution limitations, there are some good solutions to the "Environment interactions" problems. However, the solutions to the path explosion problem are less than ideal.

> Solutions to the path explosion problem generally use either heuristics for path-finding to increase code coverage,\[2\] reduce execution time by parallelizing independent paths,\[3\] or by merging similar paths.\[4\]

The parallelizing is just adding more power to the situation which doesn't really solve it. The first and third suggestions I am not to familiar with. The first sounds like it has similar problems to testing, in that they are just opting into certain paths based on heuristics, which also doesn't seem to solve it. I am wondering if the solutions to the path explosion problem could be explained here a little bit, either the solutions listed above or anything else. Specifically I am interested in the heuristics one, and what kind of things can be done here.

# Answer
The heuristic approach to solving the path explosion problem picks the next branch to explore based on some function. A simple heuristic function, yet pretty effective, would be to assign the score of a branch based on how many times it has been seen before, and then pick the one with the lowest score. This ensures that branches which haven't been seen yet are explored first instead of getting stuck in a path explosion, whose branches would have been seen many times.
> 3 votes

# Answer
There are two major things that cause path explosion: loops and large programs.

There is one clever solution to loops in this paper, *Efficient Loop Navigation for Symbolic Execution*. I don't fully understand it yet, but it transforms complicated nested loops into nested *chains* from which it creates a full sub-*constraint system* to solve within the context of the higher-level symbolic evaluator. They describe it in detail.

Also note that "*dynamic* symbolic execution" combines concrete execution with symbolic execution. Some approaches using dynamic symbolic evaluation interleave concrete inputs occasionally to test for values and perform other heuristics to guide navigation.

In terms of large programs, the problem is that you can have very large path conditions based on a very large number of possible ways to get to a specific state. This is similar in some ways to the problem of looping. The solution to this is to use *compositional* symbolic execution. This provides a *summary* for the input/output behavior of a function. So if the program is a bunch of functions composed together, you can eliminate the need to invoke each function again and again by summarizing its input/output behavior. This abstracts away the problem of having large path conditions and large numbers of paths related to complicated ways of getting to the state through the source code.
> 2 votes

---
Tags: simulation, symbolic-execution
---


# Question
Title: Represent there are infinitely many in FOL
How to represent in first order logic the expression:

> **"there are infinitely many"**

To be honest I'm confused and not even sure whether you can represent them in first order logic.

# Answer
The existing answers provide examples of contexts where "there are infinitely many" can be expressed. However, there is an important sense in which "there are infinitely many" **cannot** be expressed in a first-order way *without* some additional context restrictions:

Specifically, fix your favorite first-order language $\Sigma$. Then it's a consequence of the compactness theorem that there is no $\Sigma$-sentence $\varphi$ which is true in exactly the infinite $\Sigma$-structures:

* If there were, then $\neg\varphi$ would hold in exactly the finite $\Sigma$-structures.
* Then the $\Sigma$-theory $\\{\exists x\_1...x\_n(\bigwedge\_{1\le i\<j\le n}x\_i\not=x\_j): n\in\mathbb{N}\\}\cup\\{\neg\varphi\\}$ would be consistent (since any finite fragment holds of any sufficiently large $\Sigma$-structure), so by compactness has a (presumably non-unique) model $\mathcal{M}$.
* But $\mathcal{M}$ must be infinite, since any structure satisfying $\exists x\_1...x\_n(\bigwedge\_{1\le i\<j\le n}x\_i\not=x\_j)$ has at least $n$ many elements. By assumption on $\varphi$, this means $\mathcal{M}\not\models\neg\varphi$, and we have a contradiction.

Phrased most relevantly to your question, what we've shown is that even the sentence **"There are infinitely many $x$ satisfying $x=x$"** is not expressible in first-order logic.

---

On the other hand, when we restrict attention to specific structures we often have a better situation:

* There are many *natural structures* over which the quantifier "there are infinitely many $x$ such that" is expressible. For example, in $(\mathbb{N}; +,\times,\<)$, we may write "there are infinitely many $z$ such that $\varphi(z)$" as "$\forall x\exists y(x\<y\wedge \varphi(y))$."

The other two answers fall into this category: they exhibit structures over which "there are infinitely many" is a first-order definable generalized quantifier.
> 7 votes

# Answer
You'll need to be a little bit more precise about what "there are infinitely many" means.

But for example, if you want to say that there are infinitely many natural numbers, you could rephrase that as "there is no largest natural number", or "for every natural number there exists a larger natural number". Either of these could be expressed in FOL.

So if you wanted to say that there are infinitely many stars in the universe, you might say "there is no furthest star from the Sun": in other words, for every star, there exists a star further from the Sun. This can also be expressed in FOL.
> 3 votes

# Answer
It depends on how you interpret the logic.

For an example on $\\{x\mid x\subseteq\mathbb{N}\\}$, if a predicate symbol $P(x)$ is interpreted as "the set $x$ have infinite many numbers", then "there are infinitely many numbers in $x$" can be expressed as $P(x)$ directly.

For another example on $\\{x\mid x\subseteq\mathbb{N}\text{ or }x\text{ is a function }\mathbb{N}\rightarrow\mathbb{N}\\}$, assume

* the predicate symbol $I(f)$ is interpreted as "$f$ is an injection", and
* the predicate symbol $R(f,x)$ is interpreted as "$x$ is the range of $f$".

Then "there are infinitely many numbers in $x$" can be expressed as $\exists f( I(f)\wedge R(f, x))$.
> 3 votes

---
Tags: logic, first-order-logic
---


title: Can computers lose information?

text:
# Question
Title: Can computers lose information?
I've heard that computers cannot forget anything, but yesterday my teacher told me that a computer can lose its memory from getting very hot. Is that true that computers can lose information? How and why does this happen? Can the lost information be retrieved back?

# Answer
Beside the physical destruction of hardware, raising temperature has negative impact on computer storage :

* Magnetic material loose magnetisation faster
* Leakage current in DRAM, FLASH. FLASH SSD content will last longer if it is stored in cool environment. DRAM memory, when not properly refreshed, will loose its contents faster.
* Current in static RAM is higher with higher temperature, if memory is battery backed, the battery with keep the charge for a shorter time.

All these components are therefore designed with specific usage conditions, and as long they are respected, data should not be lost.
> 1 votes

# Answer
It depends on what "memory" you are talking about. Basically, nothing in a computer can contain data forever. Random Access Memory in a computer loses its data after it is no longer powered, a hard drive has a data retention of approximatively 10 years (this may be different now because of SSDs/SSHD/etc, but you get the idea). There are also several cases where a memory becomes amnesic, but knowing that there are many types of technology for memory, it can vary greatly. It is sometimes possible de retrieve lost data, but again, it depends on the technology.
> 2 votes

# Answer
Heat your computer up to 2,000 degrees Celsius, and all that is left is a large puddle of molten material, plus some rather noxious gases. All memory will be gone. Actually, most memory will be erased at much lower temperatures.

To erase the memory on a hard drive *completely*, an angle grinder would probably do a good job. (You'd need *very* strong magnets).

But obviously a computer can forget everything if you just tell it to forget it. Everything on your hard drive can be erased, all RAM can be erased, and then things are forgotten.

Another method works when data is stored in an encrypted form: All you need to do is erase the decryption keys. The data is still there, but absolutely inaccessible.
> 2 votes

---
Tags: memory-management
---


# Question
Title: Proving Progress for STLC with Linear and Unrestricted Types
In this paper Walker presents an extension of STLC with linear and unrestricted types. The proof of type soundness is left as an exercise to the reader. I encountered difficulty when attempting to prove progress (in a theorem prover):

$$ \vdash (S\_1,e\_1) ~\Rightarrow~ \textsf{value}{(e\_1)} ~\lor~ \exists S\_2 \exists e\_2.~ (S\_1,e\_1) \rightarrow (S\_2,e\_2)$$

The relevant typing and evaluation relations can be found on pages 6-17 of the linked document. If we attempt to prove progress by induction on the typing derivation, we encounter the following problem: there is a typing rule for variables, but variables are not values and the evaluation relation says nothing about variables.

Now adding a variable rule to the evaluation relation is the wrong solution. For example, we don't want to reduce $(\varnothing,\mathsf{un~true})$ to $(x\mapsto\mathsf{un~true},x)$, and the immediately reduce $x$ to $\mathsf{un~true}$ by looking up its value in the store. The two solutions I am considering are (1) adding variables to the set of values; and (2) requiring that terms reduce to *variables* or can take a step in the statement of the progress lemma. Ideally the correction would reflect the original intention of the author. It is also possible that I am misunderstanding the paper or language.

# Answer
> 3 votes
Variables can be considered as values if the evaluation strategy is call-by-value. Otherwise said, it only makes sense to substitute a variable with a value (in call-by-value). I am unable to check if that is the case in the paper you refer to since I can't access it.

---
Tags: programming-languages, lambda-calculus
---


# Question
Title: Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?
I feel like the answer is **no** but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense **if** the neighbour traversal for any given vertex can be done in arbitrary order.

But I've noticed a commonly suggested DFS behavior is to traverse the neighbors in alphabetical order (i.e. CLRS exercise 22.3-2), and I don't see how this can be done in $O(|V|+|E|)$ time. This became evident to me when actually trying to implement this in runnable code.

I see two ways to do it:

1. I can keep the list of vertices and each vertex's adjacency list sorted as I'm constructing the graph. However this means $O(V)$ insertion time for each new vertex in the graph, which means a total of $O(|V|^2)$ insertion time over $|V|$ nodes. And $O(|E'|)$ insertion time for a new edge where $|E'|$ is the number of neighbours in a particular vertex's adjacency list, meaning $O(|E'|^2)$ time to construct the adjacency list for any given vertex.

OR

2. Construct the graph and insert the vertices and adjacency elements in arbitrary order, but then sort them before running DFS. But comparison-based sorts are $\Omega(n\log n)$ so I'd have $O(|V|\log|V|)$ sort time for the list of vertices, and $O(|E'|\log|E'|)$ for each adjacency list.

In either case it doesn't seem like the runtime is $O(|V| + |E|)$ any more. Can someone confirm or refute? Thanks.

# Answer
> 2 votes
No, there is no linear time algorithm (for worst case).

Note for a list of $n$ positive integers, you can construct a tree with a root and $n$ children encoded by these integers respectively and traverse this tree in alphabetical order to sort these integers. So your problem is at least as hard as sorting.

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


# Question
Title: T(n) = aT(n/b)+f(n), I don't understand the difference between a and b
I was analyzing the time complexity for recursive algorithms like merge sort, but when I came across that recurrence, \[I think that equation is called a recurrence right?\] I couldn't differentiate between a which mean the number of subproblems and b which in my slides it says is the factor by which n is divided by.

# Answer
Here are three examples of algorithms with $b=2$ and $a=1,2,3$.

In all these examples, there is some small-scale cheating involved, which doesn't affect the asymptotic running time. I'll let the reader figure out where I'm cheating.

**Binary search**

In this algorithm, we are looking for an element $x$ in a sorted array $A$ of length $n$.

If $n = 1$, the problem is easy.

Otherwise, let $m$ be the index of the middle element:

* If $x = A\[m\]$, we are done.
* If $x \< A\[m\]$, we recurse with the array $A\[1\],\ldots,A\[m-1\]$.
* If $x \> A\[m\]$, we recurse with the array $A\[m+1\],\ldots,A\[n\]$.

Every time we recurse, the size of the array decreases by a factor of 2. Therefore, the running time of binary search on inputs of length $n$ satisfies the following recurrence:

> $T(n) = T(n/2) + O(1)$.

Here $a = 1$ and $b = 2$. The solution is $T(n) = O(\log n)$.

**Merge sort**

In this algorithm, we are sorting an array $A$ of length $n$.

If $n = 1$, the array is already sorted.

Otherwise, partition $A$ into two arrays $A\_1,A\_2$ of length $n/2$, sort each recursively, and then merge them in $O(n)$ time.

In contrast to binary search, in which we only recursed on one of the half-arrays, in merge sort we recurse on both. Therefore the appropriate recurrence is

> $T(n) = 2T(n/2) + O(n)$.

Here $a = b = 2$. The solution is $T(n) = O(n\log n)$.

**Karatsuba multiplication**

In this algorithm, the goal is to multiply two $n$-bit integers $x,y$.

We first divide $x,y$ into two $n/2$-bit integers: $x = 2^{n/2} x\_1 + x\_2$, $y = 2^{n/2} y\_1 + y\_2$. We then proceed as follows:

1. Compute $z\_1 = x\_1 y\_1$.
2. Compute $z\_2 = x\_2 y\_2$.
3. Compute $w = (x\_1+x\_2)(y\_1+y\_2)$.
4. Return $2^n z\_1 + 2^{n/2} (w - z\_1 - z\_2) + z\_2$.

In steps 1,2,3, we are multiplying $n/2$-bit integers (more or less; in step 3 they are $(n/2+1)$-bit integers). The rest of the algorithm consists of addition and subtraction, which can be done in linear time. Therefore the appropriate recurrence for the running time of this algorithm is $$ T(n) = 3T(n/2) + O(n). $$ Here $a = 3$ and $b = 2$. The solution is $T(n) = O(n^{3/2})$, improving on the trivial $O(n^2)$ algorithm.
> 3 votes

---
Tags: algorithm-analysis
---


# Question
Title: Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free
This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.

> If $A$ and $B$ are languages, define $A \diamond B = \\{xy: x \in A \land y \in B \land |x| = |y|\\}$
>
> Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a $CFL$.

**My try:**

Let us define the following languages:

$$L\_1 = \\{ x\\#y : |x| = |y| \\}$$

$$L\_2 = \\{ x\\#y : x \in A \land x\in B \\}$$ $L\_1$ is context-free, can be proven in a similar way to as done here

$L\_2$ is concatenation of regular languages, and hence regular.

Context-free languages are closed under intersection with regular languages, and hence $L\_1 \cap L\_2 = \\{x\\#y: x \in A \land y \in B \land |x| = |y|\\}$ is context free.

Let us define the homomorphism $h$ such that $h(\\#)=\epsilon$ and as the identity homomorphism for all other symbols.

$h(L\_1 \cap L\_2)=A \diamond B$, and since Context-free languages are closed under homomorphism, we conclude the requested result.

---

Does my proof make sense?

# Answer
> 1 votes
There are many ways to prove this. Here is another one, which proves a stronger result: $A \diamond B$ is linear.

Suppose that both $A,B$ are languages over a common alphabet $\Sigma$. Let $\langle Q\_A,q\_{0A},\delta\_A,F\_A \rangle$ and $\langle Q\_B,q\_{0B},\delta\_B,F\_B \rangle$ be DFAs for $A^R$ (the reverse of $A$) and for $B$. We construct a linear grammar with a nonterminals $\\{S\\} \cup Q\_A \times Q\_B$, with the following rules:

* For every $f\_A \in Q\_A$ and $f\_B \in Q\_B$, the rule $S \to \langle f\_A, f\_B \rangle$.
* For every $q\_A \in Q\_A$, $q\_B \in Q\_B$, and $\sigma\_A,\sigma\_B \in \Sigma$, the rule $\langle \delta\_A(q\_A,\sigma\_A), \delta\_B(q\_B,\sigma\_B) \rangle \to \sigma\_A \langle q\_A, q\_B \rangle \sigma\_B$.
* The rule $\langle q\_{0A},q\_{0B} \rangle \to \epsilon$.

In fact, your proof also shows that $A \diamond B$ is linear, since $\\{a^n \\# b^n : n \geq 0 \\}$ is easily seen to be linear, and all the closure properties you use also hold for linear languages.

# Answer
> 0 votes
$A$ and $B$ are languages, when $A$ and $B$ both are regular

* Now, take $A=a^{n}|n\>=0$
* take $B=b^{n}|n\>=0$

So, $A.B=a^{n}b^{n}|n\>=0$ Here, $A.B$ is CFL

But it may not be case. Say, $A=(a+b)^{n}$ and $B=(a+b)^{n}$ $A.B=(a+b)^{2n}$

-Here it will be regular.Hence we can say , $A.B$ will be regular or CFL.

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


# Question
Title: Bytes from integer using bitwise operators
So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...

```
int i = 512;
i & 0xFF; // this gives me the first byte

```

That must mean `i & 0xFF` gives me the first byte that is stored in memory. In other words, `i & 0xFF` is the first of the four bytes i consists of stored at the lowest memory address. Next, I think that `i << 8 & 0xFF` will then shift everything left by 8 bits and giving me the second byte. However, it is actually the opposite and only `i >> 8 & 0xFF` gives me the next byte. I do not understand why this is true. To me, it makes the most sense to left shift to get the next byte so why do I need to right shift by 8 to get the proceeding byte?

# Answer
Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results).

An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by

```
i & 0xFF
0b 111111111 0101010 01010101 000000000 => 0b 00000000 00000000 00000000 00000000

```

The neighboring byte is made of the eight neighboring bits; you discard the eight least significant bits by shifting (\>\>), then mask out:

```
(i >> 8) & 0xFF
0b 11111111 10101010 01010101 000000000 => 0b 00000000 00000000 00000000 01010101

```

And similarly for the remaining two bytes, with shifts of 16 and 24 (most significant byte).

Notice that I cared not to use the terms left/right and first/last, which are meaningless as they refer to some graphical representation or memory storage order. In the examples, the numbers are understood as binary numbers written with lsb on the right (and spacers for clarity), which is the most common convention.
> 2 votes

---
Tags: binary, bit-manipulation, c++
---


title: MLP and backpropagation limitations?

text:
# Question
Title: MLP and backpropagation limitations?
I have heard a colleague of mine giving the following statements to a student, but I am not quite sure if he is right. The statements were about Multi Layer Perceptron and the Backpropagation algorithm, he said that:

It would be reasonable to check it up if the data to be input to a MLP should be checked first its degree of data normality. It is the first time I heard that and I am not sure about it. I have seen this article: https://www.researchgate.net/publication/256980936\_Assumptions\_of\_Multiple\_Regression\_Correcting\_Two\_Misconceptions

that talks about multiple regression (and I know that a MLP NN can be used for this case) and it says that:

> In this article, we clarify that multiple regression models estimated using ordinary least squares require the assumption of normally distributed errors in order for trustworthy inferences, at least in small samples, but not the assumption of normally distributed response or predictor variables

So a MLP with BP algorithm does it only work when the input data if it has a normal distribution?

Another point that he mentions is that a MLP NN could not work in n-dimensions, but I am pretty sure that is not a limitation, because I have seen in the Andrew Ng course that he talks about data that is in Rn dimensions, and uses MLP and backpropagation to classify it. So both limitations could exist? in which cases a MLP could fail, regarding the data input.

Thanks

# Answer
No. There seem to be multiple misconceptions here.

First, linear regression. Linear regression assumes that the *errors* are normally distributed. It doesn't require that the *inputs* be normally distributed, and normally they won't be.

Second, neural networks. Neural networks certainly don't require that the inputs are normally distributed. I'm not sure where your colleague is getting that from, but it's just not true.

Yes, neural networks work fine in higher dimensions.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: How to prove that if the set and its complement are recursively enumerable, then both are recursive?
How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive?
My idea is that we can make the characteristic function of recursively enumerable set to be a total function using characteristic function of the complement (we can compute both $\chi\_A$ and $\chi\_\overline{A}$ step by step, alternating steps between them, and when either one stops, we can determine if the element belongs to the set $A$ or its complement).
Is it right?

# Answer
Roughly, yes, that's the right idea.

I think there are a few small issues though.

First, you can not compute the characteristic function $\chi\_A$, since this is computable only when the set is recursive. What you can compute is the semi-characteristic function, whose domain is $A$, and is constantly $1$ there.

If we wanted to be more pedantic, "computing a function step by step" is not completely precise. One usually takes a "program" implementing the semi-characteristic (e.g. a Turing machine accepting each element of $A$, and diverging elsewhere) and executes that program step-by-step.

So, given two TMs $M$ and $N$ implementing both semi-characteristics, you can craft a new TM $O$ which runs them "in parallel, step by step" on the same input $w$. Eventually, one (and only one) of them will halt, and $O$ can accept or reject "w" consequently.

A completely computational-model-agnostic way to state "computing step by step" could be to exploit the Kleene's normal form theorem, where a number $x$ plays an equivalent role to the number of steps. While this is arguably the "true mathematical" way to do it, in computer science we often prefer to work with "programs" (TMs,...) since we find those more familiar.
> 1 votes

# Answer
From the Turing machine point of view, $A$ and $\overline{A}$ being R.E. means that there are is a TM $M\_A$ that always halts and accepts when its input is in $A$ and, similarly, a machine $M\_{\overline{A}}$ that always halts and accepts when its input is in&nbsp$\overline{A}$. A set $B$ being recursive means there's a TM $N\_B$ which halts for all inputs, accepting if the input is in $B$ and rejecting if it isn't.

So, to decide $A$, you just need to simulate both of these machines in parallel until one of them accepts, and then accept if it was $M\_A$ that accepted and reject if it was $M\_{\overline{A}}$. One of these two things is guaranteed to happen, so the we're done. $\overline{A}$ is similarly decidable.

Alternatively, a set $A$ is R.E. if, and only if, there is a TM $E\_A$ that, when started with no input, writes out a list of $A$'s elements on its tape, with the guarantee that every element of $A$ appears in the enumeration if you wait long enough. (So, for example, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ... is an enumeration of the natural numbers, but listing all the odd numbers and "then" all the even ones wouldn't be valid, since the evens would never actually appear.)

In this scenario, we can decide whether $x\in A$ by simulating the enumerators $E\_A$ and $E\_{\overline{A}}$ in parallel until one of them says "$x$", which is guaranteed to happen. Then accept or reject as appropriate.
> 0 votes

---
Tags: computability, primitive-recursion
---


# Question
Title: Are there existing extensions to behavior trees that fascilitate node communication?
I've been looking into behavior trees, but I cannot find a lot about them. The Wikipedia page pretty much only mentions sequence and selector nodes.

I have found implementations that also provide memory selector, memory sequence, and parallel sequence, as well as some decorators like inversion and repetition.

I found some papers that discuss some form of a "weighted" selector/sequence that queries its children for their utility/probability. This can also be used in machine learning to dynamically adjust those weights.

What I have not yet found much about is communication between nodes. Some implementations use a shared "blackboard" where nodes can write values, but this seems rather clumsy, as it creates a huge lookup table that tightly couples different nodes.

I've been thinking more in terms of sending messages to the next node. I think the bulk of the shared state is a condition/action providing a specific value to the next action (rather than just success).

Has there been any research in this area? I was not able to find anything. I'm also curious to hear about other useful extensions.

# Answer
The most mathematical paper I have seen on Behavior Trees is *How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture and Decision Trees*. It is the only paper I have seen that defines Behavior Trees as a tuple e.g.

> A BT is a three-tuple $T\_i = \\{f\_i, r\_i, \Delta t\\}$

Since Behavior Trees are related to Finite State Machines (FSMs), they mention Petri Nets which are also related to FSMs. They're a message passing / concurrency system, but weren't mentioned really in relation to message passing on Behavior Trees. Maybe it would provide some inspiration since they are highly developed message passing formalisms.

Other than that, there may be some private work done on message passing in complex Behavior Trees such as in game companies, but there doesn't seem to be any public resources on it. Maybe it is an artifact of the way behavior trees are developed, i.e. it seems to be done through node-based graphic interfaces, so less source-code-centric:

Probably best to just come up with your own system it seems. Maybe even try asking at the gamedev.se, they might have some insight. Hope that helps.
> 1 votes

---
Tags: artificial-intelligence, message-passing
---


title: Marginalise edge weights on graph

text:
# Question
Title: Marginalise edge weights on graph
I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a path divided by the sum of the scores of all paths.

I would like to compute the marginal probability of each edge; i.e., the probability that the edge is present in a path drawn randomly from the above probability distribution on paths. Is there an efficient algorithm to do this?

I know that I could simply calculate the probability of each path through the graph and then for each edge sum the probabilities of the paths on which the edge occurs but this seems a very inefficient way of doing things. Is there some way to use dynamic programming to solve this issue?

# Answer
Yes, this can be solved with dynamic programming. In fact, it can be done in linear time.

I'll assume there is a single source $s$ and a single sink $t$ (if not, add $s$ and edges with score 0 from $s$ to each original source; and similarly for $t$).

Then, let $f(v)$ denote the sum of the scores of all paths from $s$ to $v$, and $f'(v)$ denote the number of such paths. You can compute both of them using dynamic programming. For instance,

$$f(v) = \sum\_u f(u) + s(u,v)$$

where the sum is over all vertices $u$ such that $(u,v)$ is an edge in the graph, and where $s(u,v)$ denotes the score on the edge $(u,v)$. If you topologically sort the graph, then you can fill in the $f(v)$ values using the above recurrence in linear time. Similarly,

$$f'(v) = \sum\_u f'(v)$$

which gives a way to fill in the $f'(v)$ values in linear time as well.

Let $g(v)$ denote the sum of the scores of all paths from $v$ to $t$, and $g'(v)$ the number of such paths. You can fill in these values similarly.

Finally, you can compute the marginal probability of an edge $(u,v)$ as

$$\Pr\[(u,v)\] = {f(u) g(v) + s(u,v) f'(u) g'(v) \over f(t)}.$$

The numerator has the total score of all paths that go through $(u,v)$, and the denominator has the total score of all paths in the graph.
> 1 votes

---
Tags: graphs, dynamic-programming, parsers, weighted-graphs, natural-language-processing
---


# Question
Title: Are there any implementations of computability logic?
I'm currently looking into Japridze's computability logic. It looks great, but I was wondering whether any programming languages or systems implement it.

Does anyone know of any implementation?

Thanks.

# Answer
> 2 votes
There doesn't seem to be any implementations of it in any current programming languages. It is rather new (introduced in 2003), so that may be a factor.

The author does define some "systems" that implement it, which are listed in the Wikipedia references. For example, *Introduction to clarithmetic I*, and a few related articles.

> “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic.

GitHub doesn't reveal anything either.

---
Tags: computability, logic
---


# Question
Title: Double exponentials vs single exponentials
Here are four tenets I cannot reconcile:

I feel I am missing some subtlety relating to the definition of an exponential-time algorithm as running in $O(2^{\mathrm{poly}(n)})$ rather than $O(2^{n})$, but I am not sure precisely where the subtlety lies.

# Answer
The issue comes down to ambiguous terminology.

$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.

Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}$ instead, so we reserve the double exponential notation for the other case.
> 25 votes

# Answer
$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.
> 16 votes

---
Tags: asymptotics, discrete-mathematics, notation
---


title: Does Provable P equal Provable NP?

text:
# Question
Title: Does Provable P equal Provable NP?
My question is a very basic one. It seems feasible to believe that $\mathsf{P = NP}$, because there is some "pathological" good algorithm for SAT, yet it is impossible to prove that the algorithm is actually correct and/or that it runs in polynomial time, in a standard axiomatic system like ZFC.

Let's fix a logic $L$ that is strong enough to encode statements about Turing machines. (Edit: I should have clarified that by this I mean the same requirements as Godel's second incompleteness theorem. For the purposes of this question, assume that **$L$ proves the peano axioms PA**.)

Then define \begin{align\*} \mathsf{ProvableP} &:= \\{A \mid L \text{ proves } \[A \in P\]\\} \\ \mathsf{ProvableNP} &:= \\{A \mid L \text{ proves } \[A \in NP\] \\} \end{align\*}

Now we have that $\mathsf{ProvableP} \subseteq \mathsf{ProvableNP} \subseteq \mathsf{NP}$. But does $\mathsf{ProvableP} = \mathsf{ProvableNP}$? How does this relate to the original P vs NP question?

**Partial answer:** The SAT problem is $\mathsf{ProvableNP}$-complete, but $\mathsf{ProvableNP}$ is closed only under provably polynomial-time reductions, not necessarily all polynomial-time reductions. However, this does seem to show that if $\mathsf{ProvableP} = \mathsf{ProvableNP}$, then since SAT is in $\mathsf{ProvableNP}$, $\mathsf{P} = \mathsf{NP}$.

So what is remaining is the converse: if $\mathsf{P} = \mathsf{NP}$, does $\mathsf{ProvableP} = \mathsf{ProvableNP}$?

I picked the P vs. NP question because it's the "canonical" unsolved problem in complexity. But, a similar question could be asked about any two complexity classes.

# Answer
> 2 votes
One issue that was overlooked in the question is how to encode languages $A$ (of which there are uncountably many) as finite objects in order for the logic $\mathcal{L}$ to have something to say about them (in particular, how to encode formulas for $\[A \in \mathsf{P}\]$ and $\[A \in \mathsf{NP}\]$. Let us assume that languages are subsets of the natural numbers $\mathbb{N}$, and that any $A$ in $\mathsf{ProvableP}$ or $\mathsf{ProvableNP}$ must be given by an arbitrary formula of the symbols of $\mathcal{L}$, i.e. it is any *definable* subset of $\mathbb{N}$. We are also assuming that:

* $\mathcal{L}$ is consistent;
* $\mathcal{L}$ implies the Peano Arithmetic axioms of $\mathbb{N}$ (PA).

With these assumptions, we now argue that $$ \boxed{\mathsf{ProvableP} = \mathsf{ProvableNP} \\;\\;\text{ if and only if }\\;\\;\mathsf{P} = \mathsf{NP}.} $$

For the forward direction, assume $\mathsf{ProvableP} = \mathsf{ProvableNP}$, and now consider any language $A$ in $\mathsf{NP}$. Note that $A$ is accepted by a nondeterministic Turing machine $N$, such that there exists a polynomial $p(n)$ which bounds the longest execution branch of $N$ on input a string of length $n$. Then let $N'$ be a nondeterministic Turing machine with the following description: first, count the input length $n$; second, calculate $p(n)$; and finally, run $N$ for at most $p(n)$ steps nondeterministically. If $N$ doesn't halt (this never actually occurs, but $N'$ doesn't know that for sure), $N'$ rejects.

Now observe that $\mathcal{L}$ (more specifically, PA) proves that $N'$ runs in time $p(n)$. Moreover, $\mathcal{L}$ can describe "the language of strings accepted by $N'$" by a formula (roughly, "there exists an sequence of configurations such that the sequence is a run of $N'$ and ends in an accept state"). Then we have that $\mathcal{L}$ proves $\[L(N') \in \mathsf{NP}\]$. Therefore, $L(N') \in \mathsf{ProvableNP}$. But we know (even if $\mathcal{L}$ doesn't) that $L(N') = L(N) = A$ by construction. So $A \in \mathsf{ProvableNP}$. But $\mathsf{ProvableNP} = \mathsf{ProvableP} \subseteq \mathsf{P}$, so $A \in \mathsf{P}$.

The backward direction is a similar trick. Assume $\mathsf{P} = \mathsf{NP}$ and that $A \in \mathsf{ProvableNP}$. Then $\mathsf{ProvableNP} \subseteq \mathsf{NP} = \mathsf{P}$, so $A \in \mathsf{P}$. From here, we know there is some Turing machine $M$ and polynomial $p(n)$ such that $M$ runs in time $p(n)$ and $L(M) = A$. Let $M'$ be a deterministic Turing machine which, on input of length $n$, first calculates $p(n)$, and then runs $M$ for at most $p(n)$ steps. If $M$ doesn't halt, $M'$ returns a default value, say it rejects.

Then similarly to before, $\mathcal{L}$ proves that $M'$ halts in time $p(n)$ and therefore that $\[L(M') \in \mathsf{P}\].$ It follows that $L(M') \in \mathsf{ProvableP}$, but we know (even if $\mathcal{L}$ doesn't) that $L(M') = L(M) = A$, thus $A \in \mathsf{ProvableP}$. Thus, $\mathsf{ProvableNP} = \mathsf{ProvableP}$. $\quad \square$

# Answer
> 3 votes
You need to define $L$ carefully. Currently, you seem to require only these properties:

1. "$L$ proves $\[A \in \mathsf{P}\]$" implies $A \in \mathsf{P}$
2. "$L$ proves $\[A \in \mathsf{NP}\]$" implies $A \in \mathsf{NP}$
3. "$L$ proves $\[\mathrm{SAT} \in \mathsf{NP}\]$"

Let $L$ be such that it ever proves only these two statements:

1. $\[\mathrm{ONE} \in \mathsf{P}\]$, where $\mathrm{ONE}$ is a dummy problem like "always accept", which is clearly in $\mathsf{P}$.
2. $\[\mathrm{SAT} \in \mathsf{NP}\]$

Then $\mathsf{ProvableP} = \\{\mathrm{ONE}\\}$ and $\mathsf{ProvableNP} = \\{\mathrm{SAT}\\}$, which are different even if $\mathsf{P}=\mathsf{NP}$. Note also that $\mathsf{ProvableP} \nsubseteq \mathsf{ProvableNP}$.

---
Tags: complexity-theory, logic, p-vs-np
---


# Question
Title: Can the foundation of computer science be implemented to include new rules of inference so that computer can do causal reasoning?
The idea I'm thinking of is about a top-down approach for AI. I would like to know if there can be a model for computers so that they can perform causal reasoning. It seems that causal relation can be simplified to be a mathematical structure, as an acyclic directed graph. If using type theory, one builds some "time types" $\\{\sigma\_i,i\in\mathbb{N}\\}$ ($\mathbb{N}$ as an index set denoting time points). The variable inhabit different time types means they are at different time points. The signature can be constructed according to the existing causal relation. The formation rule is such constructed that the rules for formulas with variables from the same time types are the same as usual logic, and the rules for different time types are based on the causal relation.

Can someone comment about this idea and give some general review about the development of top-down approach, also about causal reasoning?

# Answer
> 1 votes
This is a hot topic at the moment. Read this recent paper by Judea Pearl for example. In general, ML and AI are not very good at causal inference at the moment, because it requires a symbolic representation to build causal graphs. Attempts are being made, however, see e.g. https://arxiv.org/abs/1711.08936 or https://arxiv.org/abs/1709.05321.

---
Tags: logic, artificial-intelligence, type-theory, temporal-logic
---


# Question
Title: Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) that given three points returns true if they are non collinear and false otherwise. Is there an efficient algorithm to generate a list of random points such that no 3 points in the list are collinear? The points coordinates x y are integers, the amount of points is N and the grid size is RxC, I know that there is a restriction between N and R C, so I am fine if the algorithm relies in some assumption (e.g RxC is way bigger than N)

# Answer
For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.

Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose is $2N$.

Now consider the set of points $\\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \\}$.

For any set of 3 points to be collinear (Lets call them $(x\_1,y\_1),(x\_2,y\_2),(x\_3,y\_3) , x\_1 \< x\_2 \< x\_3$ ) we must have $\frac{y\_3 - y\_2}{x\_3 - x\_2} = \frac{y\_2 - y\_1}{x\_2 - x\_1}$ , putting in $y\_i = x\_i^2\ mod\ n$ , we obtain $x\_3 + x\_2 \equiv x\_2 + x\_1 \mod n$ and this is only possible when $x\_1 = x\_3$.

Hence we have a set of $N$ points where no 3 points are collinear and it is the best we can obtain upto a constant factor.

Since this is a deterministic construction , to get a random family of points , instead of choosing $i^2$ , we can take any random quadratic polynomial $p$ and take the set of points $\\{(i , p(i)) \ mod\ n \ |\ 0 \leq i \leq n-1 \\}$.
> 6 votes

---
Tags: computational-geometry, probabilistic-algorithms, integers, lists
---


# Question
Title: How a Symbolic Evaluator Generates Test Input for this Example
Say we have some complicated function that determines if a string matches an XSS attack string, and throws an error or does something else in that case.

```
function somethingWithXSSVulnerability(x) {
  var regex = /<script(.*)>(.*)<\/script>/
  if (x.match(regex)) {
    throw new Error('XSS')
  } else {
    return x
  }
}

```

In trying to understand symbolic evaluation in regards to test generation, I am wondering how it would generate a test for this case. How it would generate an `x` such that it matched the regex. It could be a lot more complicated than a regex, a grammar for example. The test case generating the error would be something like:

```
// yes case
somethingWithXSSVulnerability('<script>alert("foo")</script>')
// no case
somethingWithXSSVulnerability('anything else even <script> w/o closing tags')

```

To *really* test it, it might need to generate an alert or try setting a cookie or something, so there it is becoming even more complicated.

But I am trying to get a sense of how the symbolic evaluator generates a test for this case. How it determines the value of the input to the function. It seems like it would have to understand the structure of the regex, then reverse-engineer an input to match it. Wondering if that is so.

# Answer
Tools that solve problems like this often use a SMT (Satisfiability Modulo Theories) solver. This a SAT solver combined with a "theory solver" that can understand operations in some domain.

For example, constraints involving `=` and `!=` can be decided using union find; constraints involving `<` on numbers can be decided using the simplex algorithm.

Operations on strings are trickier. Searching "regex string constraint" on Google Scholar finds many papers discussing approaches.

The abstract of this survey papers gives a very brief preview From An Evaluation of Automata Algorithms for String Analysis but notes there is no consensus on a single algorithm (emphasis mine):

https://doi.org/10.1007/978-3-642-18275-4\_18

> There has been significant recent interest in automated reasoning techniques, in particular constraint solvers, for string variables. These techniques support a wide variety of clients, ranging from static analysis to automated testing. **The majority of string constraint solvers rely on finite automata to support regular expression constraints**. For these approaches, performance depends critically on fast automata operations such as intersection, complementation, and determinization. **Existing work in this area has not yet provided conclusive results as to which core algorithms and data structures work best in practice**.

It seems the best way to algorithmically process regexes is to operate on the NFAs/DFAs that they represent, and, judging by the number of papers on it, there are effective algorithms for making the required decisions.

HAMPI seems to be an important early paper describing how this can be done, which is provided online by one of the authors: https://homes.cs.washington.edu/~mernst/pubs/string-solver-tr004.pdf
> 3 votes

---
Tags: software-verification, software-testing, symbolic-execution
---


# Question
Title: A problem that is computable yet doesn't lie in NP?
I'm trying to find a problem that is computable but not in **NP**.

I checked and I havent found any duplicates(I hope so too). We were asked if there is a problem that exists that is computable yet doesnt lie in **NP** and we should name the problem and explain why is it so?

# Answer
> 1 votes
The time hierarchy theorem says that, if you allow more time, you can solve more problems. It's normally stated for deterministic machines but it applies to nondeterministic ones, too. In particular, nondeterministic Turing machines running in exponential time can solve problems that no polynomial-time NTM can. NTMs running in doubly-exponential time can solve even more, and so on for triply-exponential, quadruply-exponential and so on.

So you need to investigate the class **NEXP**, and find some problems in there that are known not to be in **NP**.

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


# Question
Title: How a SMT / SAT Solver Generates Valuations for this Example
First, an example of a set of constraints which turned out not to be solvable (I don't think):

```
b < 3 && c + a > 5 && a - b > 2 && c > 1 && b - c > 3

```

My procedure for solving this is roughly: Okay b is less than 3, and c \> 1. 1 + a \> 5, so a \> 4 in that case. Try 4 - 2 \> 2, no that doesn't work, so maybe a is 5, 5 - 2 \> 2. Then b - c \> 3. 2 - 2 \> 3. No, so b must b greater than 3, but we know b is less than 3, so it can't be solved.

Then a simpler example that can be solved.

```
b < 3 && c + a > 5 && a - b > 2

```

So say b is 2. Then a - 2 \> 2, so say a is 5. Then c + 5 \> 5, so say c is 1 as well. Then a = 5, b = 2, c = 1 solves the problem.

In that example, I picked numbers that were *close to the boundary*, in that they were "just above" the lower bound in the \> part. But you could say that a is 100 and c is 100. This is a particularly easy example as well.

My question is, how a constraint solver solves this problem. I have been reading about SAT and SMT, and have yet to read *the book* on decision procedures. However, I understand that SAT solvers solve systems of boolean equations in two ways: (1) by returning yes/no that the system can be solved, or (2) by assigning *valuations* to each variable in the system so that it satisfies the constraints. I don't know how they do this though. I also understand that SMT solvers are basically a light layer on top of SAT solvers. They allow you to have richer boolean formulas using different "theories" (such as theory of equality, theory of reals, of integers, of lists, etc.). Then you can optionally define how to merge these theories so you can apply the SAT solver on a complicated expression involving e.g. the reals, integers, equality, booleans, and lists or arrays all at once. To me this seems obvious, why wouldn't the constraint solver just work over arbitrary functions and variables, but I'm probably missing something.

I would like to know how to implement something like z3. I assume that each specific theory (such as the theory of strings) is quite complicated, so I didn't want to ask about how to generically solve all the different kinds of constraints. Instead I wanted to ask a simplified down question using basic integer constraints so I can learn the fundamentals of how an SMT / SAT solver works.

As such, the question is basically just that, how a constraint solver solves the second example above. One or two of the algorithms it might use to do so. Specifically, I would like to know how to give some function a set of constraints, and have it give me back valuations for all of the variables. In that regard, the question also entails how the constraint solver picks or decides on the set of values. I have seen it said that it is random, but I would like to avoid that approach if possible. But either way, when it picks a value, wondering how it knows it got a valid one. If it has to recompute all the constraints every time it makes a guess, or can do some sort of optimization. Basically, just how the SAT / SMT solver works.

To keep it simple, I am not looking for a complete explanation of how all aspects of solving the problem work. Just more a high level introduction to the algorithms and how they go about selecting the values and returning the valuation. Once I understand that then I figure understanding the more complicated theories like the theory of strings will make more sense.

I am asking because I can't tell based on my reading so far if it all really just boils down to apply constraints into a SAT solver, and there are maybe 1 or 2 SAT solving algorithms (DPLL and CDCL I am getting familiar with) for Boolean constraints (plus maybe a few more for generating the test data to solve the constraints). Or am I wrong there, and there is an entire layer of research on top of that (on SMT solvers) where custom decision procedures are the algorithms you want to use, and there are hundreds of them and there's no standard pattern to them. In which case I keep having difficulty imaging how it is possible to solve a constraint system like the one above, or something more complicated with string constraints (matches regex) and other constraints that require complex functions (like something is the reverse or sorted version of something else). If there's that much variability then the idea of solving any constraints seems hard.

Basically what I am looking for is a description of an *implementation*. I have read many papers so far but they have mostly been too high level to apply it.

# Answer
> 3 votes
The Simplex algorithm solves the linear programming problem.

Linear programming is the problem of optimizing a linear function with inputs $x\_1, x\_2, \dots, x\_n$ subject to a system of linear equations:

$$ 0 \leq x\_1, \dots, x\_n $$

$$ a\_{11} x\_1 + \dots + a\_{1n} x\_n \leq b\_1 $$ $$ a\_{21} x\_2 + \dots + a\_{2n} x\_n \leq b\_2 $$ $$ \dots $$ $$ a\_{n1} x\_1 + \dots + a\_{nn} x\_n \leq b\_n $$

The simplex algorithm produces an assignment to the variables that satisfies all of these linear equations, or responds that no assignment is possible. In practice it does this efficiently, but the worst case time complexity is exponential.

Notice that the Simplex algorithm requires each $x\_i$ to be non-negative. If you have signed numbers, you can transform them into two non-negative numbers for the simplex algorithm:

$$ x\_i = x\_i' - x\_i'' \text{ with } 0 \leq x\_i', x\_i'' $$

---

Each problem domain in SMT (each "theory") requires a new algorithm for quickly answering satisfiability. These theories can in fact be combined even if they're implemented entirely separately by the Nelson Oppen technique.

---

If you want to try implementing an SMT solver yourself, I suggest starting with the *theory of equality with uninterpreted functions* (called QF\_UF by SMT-LIB).

This theory involves constraints that look like this:

$$ f(x\_1) = x\_2 \\;\wedge\\; f(f(x\_2)) = x\_3 \\;\wedge\\; x\_1 = x\_2 \\;\wedge\\; x\_1 \neq x\_3 $$

The above is not satisfiable:

$x\_1 = x\_2 \implies f(x\_1) = f(x\_2) = x\_2$

$ \implies f(f(x\_2)) = f(x\_2) = x\_2$

$ \implies x\_1 = x\_2 = x\_3 $

yet $x\_1 \neq x\_3$ is the final constraint.

This can be accomplished using the Union Find data structure with extra bookkeeping to make $f(x) = f(y)$ whenever $x = y$.

---
Tags: satisfiability, sat-solvers, smt-solvers
---


# Question
Title: Equivalence of minimum cost circulation problem and minimum cost max flow problem
In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow:

> ...
>
> The second part of the proof is showing that min-cost circulation reduces to min-cost max-flow.
>
> Consider a network G for which we want to find a min-cost circulation. Add a source `s` and a sink `t` to the network, without any edges to the rest of the network. The maximum flow in this network is `0`, therefore the min-cost max-flow is actually a min-cost circulation.

*In theory*, I don't understand how this works. If we add disconnected source and sink nodes, the maximum flow is trivially `0` as claimed. Does that mean the minimum circulation problem has zero flow on every edge of the original network? This seems to violate the lower bound requirement on the edges of min-cost circulation networks.

*In practice*, I don't know how to implement a min-cost circulation solver using a min-cost max-flow solver such as the one in Boost Graph Library (BGL) here :

```
#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>

#include "../test/min_cost_max_flow_utils.hpp"

int main() {
    boost::SampleGraph::vertex_descriptor s,t;
    boost::SampleGraph::Graph g;
    boost::SampleGraph::getSampleGraph(g, s, t);

    boost::edmonds_karp_max_flow(g, s, t);
    boost::cycle_canceling(g);

    int cost = boost::find_flow_cost(g);
    assert(cost == 29);
    return 0;
}

```

The above BGL example solves a small min-cost max-flow problem. I can't figure out how to change the network to include lower bounds of edges as required in the min-circulation problem. Simply adding additional, disconnected dummy source and sink node gives zero flows on all edges (as expected) and solves nothing.

My questions are:

Am I missing something in the above proof?

How should I adapt the BGL min-cost max-flow solver above to solve min-circulation problems?

I'd really appreciate a concrete example with cycle canceling (or another algorithm) in BGL to verify and illustrate the reduction.

# Answer
> 1 votes
> > Does that mean the minimum circulation problem has zero flow on every edge of the original network?

No, it does not means that, unless the lower bound capacity of every edge is equal to zero.

You need to remove the lower bound capacity. You can use the transformation done in Ahuja, page 39.

---
Tags: algorithms, network-flow
---


# Question
Title: Given n numbers How to find out a set of numbers whose sum equal to a certain given number
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.

```
for example - the given set is [2,8,3] and given integer 9
Then I can tell {3,3,3} or {3,2,2,2} can be the required sets.

```

Unfortunately I cannot figure out the best approach (with best time complexity).. As I tried to do it using nested loops which naturally results into huge time complexity.

Any help is appreciated.

# Answer
> 2 votes
One possible solution is based on knapsack.

Consider the list elements $a\_1$, $a\_2$, $\ldots$, $a\_n$ in any fixed order. Calculate the following boolean function: $f (k, t)$ is true if it is possible to have the sum of exactly $t$ from some subset of $a\_1$, $a\_2$, $\ldots$, $a\_k$, and false otherwise. Here, $k$ spans from $0$ to $n$, inclusive, and $t$ goes from $0$ to $s$: we don't need larger sums.

The calculation can be performed in $O (n \cdot s)$ using dynamic programming. Just observe that $f (k, t) = f (k - 1, t)\mathrm{~or~} f (k, t - a\_k)$: for the element $a\_k$ and for every possible target sum $t$, we either drop the element from consideration, or take it into our sum. In the latter case, we must have the chance to take it again, hence the transition to $(k, t - a\_k)$ instead of $(k - 1, t - a\_k)$.

Now, knowing which $(k, t)$ pairs are possible and which are not, we can recursively construct all possible answers in $O((n + s) \cdot R)$, where $R$ is the number of answers. Indeed, descend from $(n, s)$ down to $(0, 0)$. When we are at $(k, t)$, we can see whether $(k - 1, t)$ and $(k, t - a\_k)$ are possible, and descend only into the possible branches. As every descent takes at most $n + s$ steps, finding $R$ possible answers will happen in $(n + s) \cdot R$ time. Actually, it will be faster since some descent paths share a common start, and some $a\_k$ are greater than $1$.

# Answer
> 2 votes
Finding *all* collections will generally take exponential time since there is an exponential number of solutions. For example, take { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } and sum = 1000: Take any number of tens as long as the sum stays ≤ 1000, add any number of nines as long as the sum stays ≤ 1000, add any numbers of eights, sevens, ..., twos, finally add as many ones as needed.

To find *one* solution I would sort the numbers in ascending order and focus on gcd's. If gcd (x, y) = 1 then every number ≥ (x-1)(y-1) can be produced using these two numbers. In your case, with gcd(2,3) = 1, every number ≥ 1\*2 = 2 can be produced which already solves your problem.

To illustrate why you don't need *all* combinations to find the best one: Take my example, and we define the "best" combination as the one with the smallest number of numbers added. With quadrillions of combinations solving the problem, I tell you out of my head that the optimal one is "100 times the number 10".

---
Tags: algorithms, complexity-theory, combinatorics, sets
---


# Question
Title: Getting ALL negative weight cycles of a graph using Bellman-Ford
I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.

After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle canceling algorithm to minimze the flow's cost. I'm basically using the Bellman-Ford algorithm from the sink of the residual graph with the max flow.

The problem is that Bellman-Ford gives me one negative weight cycle (the one that reduces more the cost), and in a given example, such cycle has a bottleneck capacity of 0, so I cannot send flow around it. However in the very same example, other negative weight cycles exist with a bottleneck capacity strictly greater than 0. Sending the bottleneck flow among these cycles would certainly reduce the cost of my assignment, nevertheless the Bellman-Ford implementation does not seem to be capable of yielding such cycles.

How might I get *all the graph's negative cycles*, to finally get the min cost assignation?

For this university project, the algorithm's performance is not relevant.

# Answer
You can use a brute force over all sequences of vertices, check if the permutation represents a negative cycle, and if so- print the cycle. This is not an efficient algorithm (runs at $O(n^{n+1})$), but a simple one

Suppose all vertices are denoted by $1,2,\ldots,n$. We denote by $C\[i\]$ the $i^{th}$ node in the cycle, for $i=1,2,\ldots,k$, where $3 \leq k\leq n-1$ is the size of the cycle.

A pseudo code of the algorithm goes as follows:

1. Let $k\gets 3$
2. If $k==n$, then terminate the algorithm.
3. Let $C\[i\]\gets 1$ for $i=1,2,\ldots,k$
4. Check if $C=(C\[1\],C\[2\],\ldots,C\[k\],C\[1\])$ is a negative cycle in the graph. If so- print $C$
5. If $C\[1\]=C\[2\]=\ldots=C\[k\]=n$, then $k \gets k+1$ and go to step 2.
6. Otherwise, select $C\[j\]=\min\_i C\[i\]$ (if there are multiple $j$-s with the minimal value, select the one with the minimal index), assign $C\[j\]\gets C\[j\]+1$ and go to step 4.
> 1 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Removing epsilon transition from context-free grammar
I have the following context-free grammar from which I have to remove epsilon transitions:

$S \to 0A0|0$

$A \to BC|2| CCC$

$B \to 1C | 3D | \epsilon$

$C \to AA3 | \epsilon$

$D \to AAB | 2$

---

By algorithm, I create $N\_{0}$ that will hold all non-terminals that contain $\epsilon$ and in next steps add non-terminals that have rule that contains only non-terminals from the previous iteration of N e.g.

1. $N\_{0} = \\{\\}$
2. $N\_{1} = \\{B,C\\}$
3. $N\_{2} = \\{B,C,A\\}$
4. $N\_{3} = \\{B,C,A,D,S\\}$

Now I have to adjust rules, we can remove non-terminals in $N\_{3}$ object from rules, thus we have to create all combinations without it e.g.

$S \to 0A0 | 00 | 0$

$A \to BC | B | C | CCC | CC$

$B \to 1C | 1 | 3D | 3$

$C \to AA3| A3 | 3$

$D \to AAB | AA | A | AB | B | 2$

We see that no non-terminal isn't useless, so is this the final context-free grammar? Or did I make mistake somewhere?

Thanks for answers and help.

# Answer
As described in the algorithm to put a given CFG in Chomsky Normal Form:

To remove the $\varepsilon$-rules: Remove a rule $A \to \varepsilon$ if $A \neq S\_0$ ($S\_0$ being the start-variable). To 'repair' the CFG, add for every occurence of $A$ in the body of a rule, the same rule but with $A$ removed. Example: if you have rules $A \to B | \varepsilon$ and $B \to BAAB$. To remove the $\varepsilon$ for $A$, add for each ocurrence of A a new rule with A removed. In this case: $A\to B$ (remove $\varepsilon$) and $B \to BAAB|BAB|BB$.

Finally, for rules of the form $R \to A$, add $R\to \varepsilon$ if you did not remove $R \to \varepsilon$ in a previous iteration.
> 0 votes

# Answer
1. Remove all useless symbols( all non productive non terminals excluding the production rule)
2. Remove all unreachable ( non terminals that can’t be reached from the production rule or starting rule)
3. Finally apply the removals of the epsilon rule to all rules that contain them.
> 0 votes

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


title: How is space from malloc allocated?

text:
# Question
Title: How is space from malloc allocated?
Whenever we load a process (which consists of object code, static and global variables, stack and heap space) into main memory it would be of fixed size. But, the program doesn't know in advance how much heap memory is it gonna need? Is there some fixed stack and heap space given to each process of some size in advance? But, then wouldn't it be a waste of space to give same amount of stack and heap space for each process ?

There can be other possibility that whenever we execute malloc, operating system gives us free space (basically holes) from main memory which is not the part of process. So, process size can increase at runtime. Then, Why is stack and heap space given to a process in the first place?

# Answer
There are many techniques that can be used by an OS. Still, usually when the OS loads an executable file, it finds inside it how much memory to allocate at the beginning for the "heap".

The "stack" can be set to a minimum amount, and then gradually increased as soon as things are pushed on it.

When the program starts, it will ask for more heap memory using system calls, and the OS will allocate the required physical memory (if available, of course), and map it to the process address space. If the OS uses virtual memory, some of the allocated memory can also be swapped to disk if there's need for that.

> Why is stack and heap space given to a process in the first place?

Usually, that's a small amount, which is needed to perform basic program startup. For instance, suppose that your program was written in C, using a few global variables. In principle, the space for these globals could be allocated on the heap after the program starts, but that's cumbersome to handle. Instead, if the OS preallocates a small amount of memory, that can be used for globals -- those are never going to be deallocated anyway. Even better, doing so can ensure that globals have a fixed address, so the compiler can access then using their known address. Allocating them on the heap after the program starts may (depending on the OS) instead allocate them at unpredictable addresses, possibly requiring an indirection to access them.
> 3 votes

# Answer
`malloc` is a library function that makes use the `sbrk` system call. The manual page of `malloc` on Linux says:

> Normally, malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2).

If we now look at `sbrk` manual page:

> ```
>    brk() and sbrk() change the location of the  program  break,
>    which  defines  the end of the process's data segment (i.e.,
>    the program break is the first location after the end of the
>    uninitialized  data  segment).  Increasing the program break
>    has the effect of allocating memory to the process; decreas
>    ing the break deallocates memory.
>
> ```
> 5 votes

---
Tags: operating-systems
---


# Question
Title: Find 8 numbers whose sum is closest to a defined value
I have a file that has a number (a positive integer) on each row.

Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible.

So, supposing that I have a file that looks like this:

> 345
> 3
> 2
> 3453
> 1234
> 6
> 7
> 34
> 12
> 1111
> 48
> 413

If the given number is 526 I would like to get a solution like: 3+2+6+7+34+12+48+413 = 525. So those are the 8 numbers that best fit our condition.

Is there an efficient algorithm with a low complexity?

The file can have \>1000 rows and the numbers won't be bigger than 10k.

# Answer
> 5 votes
## Dynamic programming

One approach is to use dynamic programming. If you have $n$ numbers ($n$ rows in the file), and each number is in the range $1..m$, then the obvious dynamic programming algorithm has running time about $8mn$. For your parameter size, this might be adequate.

In particular, let $A\[1..n\]$ be an array of your $n$ numbers. Define $T\[x,i,j\] = 1$ if there is a way to write $x$ as a sum of $j$ numbers from among $A\[1..i\]$, or 0 if not. Now we have the relation

$$T\[x,i,j\] = T\[x,i-1,j\] \lor T\[x-A\[i\],i-1,j-1\]$$

(with the convention that $T\[x,i,j\]$ always evaluates to 0 if $x$ is negative). Consequently, you can compute all of the $T\[x,i,j\]$ values iteratively. There are $8mn$ values to compute, so this takes $8mn$ time.

Once you have filled in the $T$ table, now you can answer any query quickly. Suppose you want to find the closest number to $q$ that can be written as a sum of 8 numbers. Then you should scan $T\[q,n,8\]$, $T\[q+1,n,8\]$, $T\[q-1,n,8\]$, $T\[q+2,n,8\]$, $T\[q-2,n,8\]$, etc., until you find the first entry that is one. This takes at most $m$ iterations.

In total, the running time is $O(mn)$, where the constant hidden by the big-O notation is small. The space required is $O(mn)$ as well, but this can be reduced to $O(m)$ if you fill in the $T$ table in the right order and discard entries once they are no longer needed.

## Two-way merge

There's an alternative algorithm that will probably be significantly faster for your specific problem. The basic idea is to first find an algorithm that works for sums of 2 numbers, then apply that repeatedly.

Let $S$ be a set of numbers. Define $S \bowtie S$ to be the set

$$S \bowtie S = \\{s+t : s, t \in T\\}.$$

In other words, $S \bowtie S$ is the set of all possible sums of two values from $S$. In our case, we're going to represent $S$ as a sorted list of numbers.

It turns out you can compute $S \bowtie S$ from $S$, using a FFT-based convolution procedure. Let $N$ be the smallest power of two that is larger than $2m$. Define a $N$-vector $v$ whose $i$th coordinate is 1 if $i\in S$, or 0 otherwise. Compute $v \otimes v$, the convolution of $v$ with itself. It turns out that $v \otimes v$ is the $N$-vector for $S \bowtie S$, so you can recover $S \bowtie S$ from $v \otimes v$. Also, you can compute the convolution $v \otimes v$ using a discrete FFT over the $N$th complex roots of unity: you take the FFT of $v$, square every entry, then take the inverse FFT. The running time of the FFT is $O(N \lg N)$. Since $N=O(m)$, it follows that the running time of this procedure is $O(m \lg m)$.

Now we repeat this recursively three times. In other words, we let $S = $ the set of numbers in the original file, compute $T = S \bowtie S$ (the set of 2-way sums), compute $U = T \bowtie T$ (the set of 4-way sums), and then compute $V = U \bowtie U$ (the set of 8-way sums). This gives us the set of all numbers that can be represented as a 8-way sum.

If you like, a more elegant way to compute the set of 8-way sums is as follows: let $N$ be the smallest power of two that is larger than $8m$, form a $N$-vector $v$ where $v\_i=1$ if and only if $i$ is part of the original file, take the discrete FFT of $v$ (over $N$th complex roots of unity), raise each entry to the 8th power, then take the inverse FFT. This gives you a $N$-vector that has a 1 in its $i$th coordinate if and only if $i$ is an attainable 8-way sum.

Finally, given a query $q$, we can quickly look it up in $V$ (using binary search, say) and find the nearest number to $q$ that's in $V$.

The total running time will be $O(m \lg m)$, and the total space will be $O(m)$. For your parameter settings, this should be extremely fast, given that $m$ is no larger than 10,000. However, the implementation complexity is much higher, since you need to implement a FFT, worry about round-off error and precision for complex numbers, and so on.

# Answer
> 1 votes
For the dynamic programming approach, I would first sort the numbers. Let $s\_1$ be the sum of the largest 8 numbers. If $s\_1 ≤ s$ then the solution is $s\_1$.

Let $s\_2$ be the sum of the smallest 8 numbers. If $s\_2 ≥ s$ then the solution is $s\_2$. (These two steps eliminate some extreme cases, especially when s is very small or very large compared to the other numbers)

Otherwise, replace the 8th smallest number with the next larger one as long as the sum is ≤ s. Then replace the 7th smallest number with the next larger one as long as the sum is ≤ s and the 7th smallest is not the same as the 8th smallest, and so on. Let $s\_3 ≤ s$ be the sum that you obtained this way. If by coincidence $s\_3 = s$ then $s\_3$ is the solution. Otherwise, $s\_3$ may be quite close to $s$. Let $L = r\_3$ and $R = s + (s - r\_3)$; then the solution x of the problem is in the range $L ≤ x ≤ R ≤ 2s$. Having an upper bound for the solution will reduce the amount of work that needs doing. And as long as the sum of the 7 smallest and the largest number exceed R, we remove the largest number from the problem.

(In the example (sorted) 2 3 6 7 12 34 48 345 413 1111 1234 3453 we quickly find that the smallest 7 numbers add up to 112, making s\_3 = 525, so solutions are in the range 525 ≤ x ≤ 527, which removes all numbers greater than 415, leaving only 9 numbers. )

Then I would sort the numbers in order of (distance to s/8), with the ones closest to s/8 coming first. As a result, the dynamic programming approach will from the start find sums of eight numbers close to s. Especially if we have many numbers, this increases our chances that a sum exactly equal to s is found quickly, in which case we are finished early. And whenever we find a sum between L and R, we can improve the bounds L ≤ x ≤ R for solutions.

Once all small numbers (all numbers ≤ s/8) are processed, and the smallest remaining number is X, the dynamic programming doesn't need to find any sums of seven numbers that are greater than R - X (since adding an eighth number gives a result \> R), we don't need to find any sums of six numbers that are greater than R - 2X, and so on, which again will decrease the amount of work needed.

If there are no numbers much larger than s/8, and the largest number is X, then we can ignore all sums of seven numbers less than L - X. If the sum of the largest two numbers is $X\_2$ then we can ignore all sums of six numbers less than L - $X\_2$ and so on.

---
Tags: algorithms, integers, knapsack-problems
---


# Question
Title: Identify objects (bus) on the map based on coordinates (lat, lon)
Let's say I have an android app that frequently sends current GPS location of the user. If person is driving with bus, I can easily get GPS location of the bus and display it on the map and update it accordingly every 30 seconds.

Let's say that instead of one bus there are 3 buses driving along same route. My problem is to display real time location of every bus on the route. In this case there are X users on every bus all having my android application installed on their phones. Here is the picture that could represent the problem:

As you can see, every mobile application will send GPS location of the user to my server. Server receives and saves data.

Based on the server data I should create a web app that should display map whith position of every bus in real time.

One possible way to do this is to to try to cluster GPS data and based on clusters to conclude where is position of every bus. This approach has few problems:

* This algorithm could be slow if there is lot of data (then I can't update position of every bus every 30 seconds)
* Second problem is that I don't know number of clusters (buses). There might be 2, 3, 4 or N buses

Is there any other better approach to this problem?

# Answer
> 1 votes
Have the app record the GPS location once per second, save it, and once every 30 seconds, update that trace of the locations over the past 30 seconds. Or, just upload the location every second. The bandwidth requirements for that are small. Then, if you have multiple users in the same location (within a fixed radius, say within 100 ft of each other), and with a velocity within some fixed range (say, between 20-60 mph), declare them to be on a bus together. That should be fast, and doesn't require knowing the number of buses.

This problem doesn't need a solution with a fancy algorithm; straightforward solutions should suffice.

---
Tags: algorithms, machine-learning, clustering
---


# Question
Title: Halting Problem without self-reference: why does this argument not suffice (or does it)?
I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is precisely the style of treatment I am aiming for. However, the self-reference (in particular, checking if a program halts on itself) is not the most didactic.

What I'm wondering, as a proof sketch, is why we could not simplify even further and say: if we assume a program `H(P,I)` for the Halting Problem that halts with true if `P(I)` halts, and halts with false otherwise, then we could create a program of the form:

```
def Q(J):
  if H(Q,J) then loop forever
  else halt

```

... which is a valid program if and only if the Halting Problem is a valid program. We can then ask: what should `H(Q,J)` return on any arbitrary value for `J`? We see a contradiction in both possibilities, and we conclude that since the existence of `H` allows us to construct the contradictory program `Q`, thus a program of the form `H` cannot exist.

There is still some self-reference here in that the program `Q` checks whether or not it halts on the current input (and does the opposite), but for me, this seems much more intuitive than setting up a situation where we need a call of the form `P(P)` or `H(P,P)`, etc. However, I have not seen this simpler argument used, and I think it would have been were it valid. Hence my questions are:

* Is the above argument sufficient as a proof (sketch) of the Halting Problem?
    + If so, why do so many arguments go with a confusing step of the form `P(P)` or `H(P,P)`? (Is it just to remove the unimportant "input" from the equation?)
    + If not, what's missing?

---

There are a variety of related questions on this topic, such as:

I also found mention of the proof based on Berry's paradox, which is quite appealing. Still, I have not yet managed to convince myself whether or not the specific argument above works (even if just for my own understanding; I feel I am perhaps missing something stupid and would like to know what it is).

# Answer
I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the one you linked. If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video is surprisingly accessible, and remains true to the logic of the standard proof.

On to the difficulties with your proposal. In your proposal, it's not trivial to write down the code for such a `Q`. Think about what it means to have the line

```
  if H(Q,J) then loop forever

```

Recall that the first argument to `H` is a bit-string that contains the code / algorithm / Turing machine -- it's not a pointer to the function, but a string. Naively, this seems to mean that we include a hardcoded string that contains the source code for `Q`, inside the code of `Q`. But that's not possible. Suppose the code for `Q` takes 100 characters. Then we need to hardcode a 100-character string constant inside the definition of `Q`, plus we also need some more characters for the rest of the logic -- and that adds up to more than 100 characters. If you think about it, it's obvious that we can't have a string constant inside the code of `Q` that is the code of `Q`, because it would be too long.

Maybe you're thinking that's not what you had in mind. Maybe you were thinking that the programming language will have some built-in API to get the code of the current function, so actually the code you were thinking of is something like:

```
def Q(J):
  if H(get_source_code_of_current_function(),J) then loop forever
  else halt

```

OK, fine. This proves that the halting problem can't be solved for code written in any programming language that has a `get_source_code_of_current_function()` API. However, my favorite programming language doesn't have such an API. So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows? Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

And that's a major flaw in your proof. And it's a flaw that is subtle and not at all evident. I don't think it's pedagogically a good idea to present a proof that "looks valid" on the surface but is actually, once you dig into it deeper, flawed.

Now, it *is* possible to rescue your proposed proof. It actually *is* possible to construct a function `Q` that works the way you said; you basically need it to be a quine. I suppose in principle you *could* explain the idea of quines, then present your proof and explain how to implement a function `Q` using those ideas. But that seems like a bad idea to me, from a pedagogical perspective. Quines are mind-bending and mysterious and freaking hard to understand. A student who doesn't understand quines won't understand your proof. And it makes the proof of undecidability for the halting problem look a lot more mysterious than it needs to be. So this does not seem to me like a more accessible way to understand the halting problem.
> 21 votes

# Answer
I don't see how self-reference is pedagogically difficult. The Barber Paradox is pretty easy to understand. And your argument has implicit self-reference, and I find it to be more difficult to understand than simple self-reference. On top of that, it's incoherent. To define H(Q,J), you first need to know what Q is, and to define Q, you first need to know what H(Q,J) is. That doesn't work. At best you can assert that Q is a fixed point of this self-referential definition, but then if you try to derive anything from the contradictory nature of Q, you're just showing H doesn't exist OR that no such fixed point exists; you now have to prove that if H did exist, the fixed point would have to exist.
> 1 votes

---
Tags: halting-problem
---


# Question
Title: Minimum number of strings to cover entire space within Hamming distance
Given $(n, k)$:

1. What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
    * Is there an asymptotic expansion or lower bound, at least?
    * A somewhat-trivial lower bound is as follows:
        + There's $\sum\_{i=0}^{k} {n \choose i}$ strings within distance $k$ of a given string.
        + There's $2^{n}$ strings total.
        + Each string can be counted no less than once.
        + So we have a lower bound of: $$x \ge \frac{2^{n}}{\sum\_{i=0}^{k} {n \choose i}}$$
2. Is there an explicit formula that maps an index $1..k$ (or $0..(k-1)$) to these strings? (I am aware that this is likely not unique.)

This is closely related to error-correcting codes, but ultimately distinct. (In an error correcting code you (usually) want to have every string within distance $k$ (or $k/2$, etc, etc) of no more than one codeword, whereas here you want to have every string within distance $k$ of *at least one* codeword.)

# Answer
The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for an exact formula for the minimal size of a covering code.
> 3 votes

---
Tags: strings, discrete-mathematics, coding-theory, hamming-distance
---