# Question
Title: Consistent Simulation of Cellular Automata on Infinite Grid
Let's say that you have an infinite grid of cells.

A program is run per cell, where you have read access to some finite number of cells (for the previous state in time), but you only have write access to the specific cell you being run on (for the next state in time).

The program reads cell data about the LAST state of the infinite grid, and writes that happen are for the NEXT state of the infinite grid.

In that setup, let's say that each cell has a cell type, and there is a set of logic for how cells behave based on their immediate neighbors (the 8 neighbors in the 8 cardinal directions).

Giving some real world properties to these abstract cells, lets say that cell types include...

* empty space
* stone
* sand
* water
* many others

Then, let's say you have logic like this:

* empty space does nothing
* stone does nothing
* if the cell below sand is empty, it will move there. Else it will try moving down left and down right.
* water has the same rules as sand, but if it wasn't able to make a move using that logic, it will try to flow to the left (simplification of the actual logic)
* more complex logic, like a seed might absorb neighboring water cells, and sprout a plant after absorbing 3 water cells.

Is there a way to craft the per-cell program that runs such that you get a simulation consistent with a rule set like the above?

A problem I'm hitting is in the case below, where black is empty space, stone is white, and water is blue. The water on the left wants to go to the lower right, and the water on the right wants to go to the lower left.

The program running for the water on the left says "I'm moving down and to the right, so I'm erasing my cell" and clears out it's cell.

The program running for the water on the right says "I'm moving down and to the left, so I'm erasing my cell" and clears out it's cell.

The program running for the destination cell that they both want to move to runs and checks both up and left for a water cell and up and right for a water cell, but ultimately has to pick one as the winner (whichever if statement comes first).

It clones that cell and since both cells were cleared when their program runs, one water "cell" has vanished.

The problem is, that the water cell on the right has to know what the water cell on the left is going to choose, but doesn't have all the information the left water cell has when making it's decision. It could get THAT information, but this is recursive, so you then need to have knowledge of the entire previous state of the infinite grid to make a decision about how to act.

Is there a way to constrain this problem to give reasonable results (no particle destruction / cloning for example) while only having limited knowledge of the rest of the grid?

As a practical requirement for such a solution, each cell effectively has the storage of 4 real numbers, so you couldn't just do something like store how much of each particle type is present per cell by having a real number per particle type, since there are numerous particle types. This is being implemented within a pixel shader for what it's worth.

Thanks!

Edit: Here's a diagram referring to what I think makes Yuval's answer not work. It would be nice to be wrong though!

Yuval's proposition is that water can move down, and down right, without needing any extra protection. If moving down left, it would look at the information for it's nearby neighbors and determine if something else wanted to move to that spot too (looking in the upper left quadrant I'd guess!), and if there was a conflict, don't do the move.

The problem is that in this case, if we are considering what way water particle $A$ wanted to move, we would have to figure out how particle $B$ wanted to move to know if there was a conflict. In this case, the way particle $B$ wants to move is based on how particle $C$ moved which is based on the particle to the left. It continues possibly infinitely to the left, so I'm saying you'd need to possibly do an infinite number of reads to figure out whether there was a conflict or not.

(Note, i have read access to the previous state of the grid, and write access to the next state of the grid, but not read access to what other cells have written so far. If that is where the misunderstanding is, sorry for not making that clearer)

# Answer
As your example shows, the specific rules you gave aren't self-consistent.

Is it possible to modify the rules to come up with some other set of rules that will be self-consistent? Yes. There will be multiple ways to do it; there's not a single correct answer. For instance, one possible approach is to artificially impose an order in which you apply the rules. For your set of rules, something like "scan the cells from bottom to top, right to left, and determine the new value of each cell as you scan over it" might suffice, though there's no guarantee that will always work. Another possible approach is to impose some order on the "particles", and process each particle in that order (figuring out where it will move); this essentially resolves any conflicts in favor of particles that appear earlier in the order.

---

As a side note, this isn't a cellular automaton (CA). For a CA, the contents of a cell $c$ at time $t$ are a function of the contents of the cells in a small neighborhood around $c$ at time $t-1$. Notice that there is not necessarily any meaningful notion of "particles" in such a system.
> 2 votes

# Answer
One way to solve your problem is as follows:

* Each water cell is aware of its immediate neighbors.
* Each water cell tries to propagate downwards. If it wants to propagate down left and there is a conflict, then it stays put. (If it wants to propagate down right then there is no problem.)

This symmetry breaking rule ensures that there are no conflicts, and can be implemented locally.

One thing missing in this solution is which way a water cell chooses to propagate if it has several options. There are many possible choices, and it's up to you to decide which one to use.
> 2 votes

---
Tags: cellular-automata
---


# Question
Title: primitive recursion in the lambda calculus
I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/Primitive\_recursive\_function".

These are the three base axioms:

* Constant function: The 0-ary constant function 0 is primitive recursive.
* Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. That is, S(k) = k + 1.
* Projection function: For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive.

Here is my confusion. In the LC zero is represented as `(λfx. x)`. Next the successor functions is defined as `(λnfx. f (n f x))`. Because they are both axioms both of these functions can be classified as primitive. But when I apply the function suc to zero I get the encoding of the number one. Which is represented as the function `(λf.(λx.(f x)))`. Now this number is neither zero or the suc function but the result of application. As such I do not see how this result function (value of 1) fits into the rule set. But very clearly a program with the number 1 in it is still primitive recursive. What am I not understanding here? While 1 is the suc to zero, once suc is applied it is neither suc, nor zero.

# Answer
As you mention, $1$ is primitive recursive according to the following proof:

* $0$ is primitive recursive (axiom)
* $\operatorname{suc}$ is primitive recursive (axiom)
* $1=\operatorname{suc}(0)$ is primitive recursive (composition)

Using this you can show that $1$ is *admissible*, that is if you add $1$ as an axiom, the resulting set of functions is still the primitive recursive functions.

Note that lambda calculus has absolutely nothing to do with the answer.
> 2 votes

---
Tags: recursion, lambda-calculus, primitive-recursion
---


# Question
Title: Why are most (or all?) polynomial time algorithms practical?
I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{999999999999999999999})$ is polynomial time, but not efficient). Yet, isn't it the case that all algorithms in polynomial time also happen to be realistic, like at most $O(n^4)$ or something? I guess my questions are:

1. Is this surprising?
2. Are there any examples of algorithms that are polynomial time but not practical?

# Answer
The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all:

1. The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice.
2. The AKS primality testing algorithm runs in polynomial time but is too slow to be practical. Instead, randomized polynomial time algorithms are used. We sacrifice certainty for performance.
3. Fast matrix multiplication algorithms run asymptotically faster than high-school matrix multiplication (both are polynomial), but are too slow to be practical. The high-school algorithm is used in practice.
4. A similar issue occurs in fast integer multiplication algorithms. The algorithm with the best asymptotic complexity, Fürer's algorithm, is too slow to be used in practice. Instead, relatively simple algorithms are used even for quite large integers.
5. Big data algorithms need to run in linearithmic time (which is $O(n \log^{O(1)}n)$) to be practical.

These examples show that the identification of *polynomial time* with *practical* is not accurate, and might depend on the circumstances. Researchers in theoretical algorithms feel a need to justify their field of research, and so they ideologically believe in the sentiments expressed in the comment you mention. You shouldn't take such comments too literally.

In fact, many algorithms used in practice are *heuristic* and we don't have any estimates on their running time other than empirical results. Such algorithm don't fit into the theoretical framework at all, yet there are very useful in practice. Several (but not all) machine learning algorithms belong to this class *just in terms of running time* (not to mention in terms of *performance*), as do search algorithms such as A\* and alpha-beta, and SAT solving algorithms.
> 10 votes

# Answer
Question (1) is a tricky one that I have never seen a good reason for. One suggestion may be that we're much more likely to comprehend and find the answers for simpler problems, the harder ones take special skills, so the chance the right person works on it and comes up with the answer is low. This is all very hand-waving though.

For (2) there's definitely examples, in fact, this question has already been asked and answered! Note also that there's a chain of links to a cstheory.se question and a math.se question in there that have other examples.
> 6 votes

# Answer
I have seen the following explanation regarding your question (1):

The powers of $n$ in the running time usually arise out of *for* loops or similar constructs. Each *for* loop in turn is needed, because we, as solvers, had an idea how to break up the problem or index over something useful. Since we usually use only a small number of ideas, the powers tend to be small. It's hard to imagine an algorithm with 20 nested *for* loops, where inside the very last *for* loop we actually do something that depends on all 20 indices.

This argument is appealing to me, but it is quite weak because it only deals with *for* loops. For instance, one can easily create any number of nested *for* loops with recursion, but then one can find good reasons against doing such a bizarre construction. In any case, I think this argument can be strengthened with an analysis of a lot of different cases, but I present just the high-level idea.
> 5 votes

---
Tags: algorithms, complexity-theory, polynomial-time
---


# Question
Title: DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$
We can form DFA accepting binary numbers divisible by $n$.

For example DFA accepting binary numbers divisible by 2 can be formed as follows:

Similarly DFA accepting binary numbers divisible by 3 can be formed as follows:

We can follow a well defined procedure to form these types of DFAs. However can there be any well defined procedure or better to say logic for forming DFAs accepting numbers of of the form $n^k$?

For example, let us consider DFA accepting all numbers of the form $2^k$. This language will be $\\{1,10,100,1000,...\\}$, thus have regex $10^\*$. We can form DFA as follows:

I tried forming DFA for $3^k$ and similar ones? But was not able to do so. Or is it just that its pattern of $2^n$ binary equivalents which was making it possible to create DFA and **we cannot form DFA accepting all binary numbers of the form $n^k$ for specific $n$?**

# Answer
Here is a quick and dirty proof using Pumping Lemma that language $L$ consisting of $3^n$ in binary is not regular (note: it is regular if represented in ternary, so representation is important).

I will use the notation from Wikipedia article re Pumping Lemma. Assume for contradiction that $L$ is regular. Let $w \in L$ be any string with $|w| \ge p$ (pumping length). By Pumping Lemma, write $w = x y z$ with $|y| \ge 1, |xy| \le p$ and for all $i \ge 0$ $xy^i z \in L$. I will write $x$, $y$, and $z$ also for numerical values of corresponding parts, and $|x|, |y|, |z|$ for their lengths in $w$. Numerically we have $w = 3^{k\_0}$ for some $k\_0 \in \mathbb{N}$. At the same time we have numerically $w = z + 2^{|z|} y + 2^{|z|+|y|}x$. Thus, we have

$$ z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k\_0}$$

Now, let's pump $w$ to get for all $i \ge 0$

$$ z + 2^{|z|} y \left( \sum\_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k\_i}, $$

where $k\_0 \< k\_1 \< k\_2 \< \ldots$. Simplifying we get for $i \ge 1$

$$ z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k\_i}.$$

Let $C = z - 2^{|z|} y / (2^{|y|}-1)$. Then we have

$$ 3^{k\_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C. $$

Now, observe that

$$ 3^{k\_i} - 3^{k\_{i-1}} = (2^{|y|}-1)(3^{k\_{i-1}} - C). $$

Therefore, we have $C (2^{|y|}-1) = 3^{k\_{i-1}} (2^{|y|} - 3^{k\_i - k\_{i-1}}).$ Note that $|2^{|y|} - 3^{k\_i - k\_{i-1}}| \ge 1$. Thus, on one hand, the absolute value of the right hand side grows at least as $3^{k\_{i-1}}$, which goes to infinity with $i$. On the other hand $C(2^{|y|}-1)$ is independent of $i$ and is a constant. This gives a contradiction.
> 10 votes

# Answer
One way of seeing that this is not possible for (e.g.) the language $L$ of powers of $3$ in binary expansion is by considering the generating function

$\sum\_{k=0}^{\infty}n\_kz^k$,

where $n\_k$ is the number of words of length $k$ in $L$. This function is known to be rational, i.e. a quotient $p(x)/q(x)$ polynomials, for any regular $L$. In particular, the numbers $n\_k$ satisfy a linear recurrence $n\_{k+p+1}=a\_0n\_k+\dots+a\_{p}n\_{k+p}$ for some $p\in\mathbb{N}$ and $a\_1,\dots,a\_p\in\mathbb{Z}$.

On the other hand, since $\log\_2(3)$ is an irrational number in $(1,2)$, we get that $n\_k\in\\{0,1\\}$ for all $k$, and the sequence $(n\_k)\_{k\ge 1}$ is not periodic. This gives a contradiction, since after at most $2^p$ steps, the values of $n\_k,\dots,n\_{k+p}$ have to repeat, and the recurrence would then lead to periodic behaviour.
> 10 votes

# Answer
A complete answer to your question is provided by a (difficult) result of Cobham \[2\].

Given a numeration base $b$, a set of natural numbers is said to be $b$-recognizable if the representations in base $b$ of its elements form a regular language on the alphabet $\\{0, 1, \dotsm, b-1\\}$. Thus, as you observed, the set of powers of $2$ is $2$-recognizable since it is represented by the regular set $10^\*$ on the alphabet $\\{0,1\\}$. Similarly, the set of powers of $4$ is $2$-recognizable -- it corresponds to the regular set $1(00)^\*$ -- and the set of powers of $3$ is $3$-recognizable -- it corresponds to the regular set $10^\*$ over the alphabet $\\{0,1,2\\}$.

A set of natural numbers is said to be *ultimately periodic* if it is a finite union of arithmetic progressions.

Two bases $b, c \> 1$ are said to be *multiplicatively dependent* if there is an $r \> 1$ such that both $b$ and $c$ are powers of $r$: for instance $8$ and $32$ are multiplicatively dependent since $8 = 2^3$ and $8 = 2^5$.

**Theorem** \[Cobham\] Let $b$ and $c$ two multiplicatively independent bases. If a set is $b$-recognizable and $c$-recognizable, then it is ultimately periodic.

In particular let $S$ be the set of powers of $3$. We have seen that it is $3$-recognizable. If it was also $2$-recognizable, it would be ultimately periodic, which is certainly not the case for $S$.

Cobham's theorem led to many surprising generalisations and developments. I recommend the survey \[1\] if you are interested.

\[1\] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers, Journées Montoises (Mons, 1992). *Bull. Belg. Math. Soc.* Simon Stevin 1 (1994), no. 2, 191--238. Correction in no. 4, 577.

\[2\] A. Cobham, Uniform tag sequences, *Math. Systems Theory* **6** (1972), 164--192.
> 8 votes

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


# Question
Title: What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I can say that complement of CFL is included in P(right?). There is still a question whether complement of CFL is proper subset of P or the whole P. I would appreciate any ideas on how to show that complement of CFL is the whole P(if that's the case of course).

# Answer
> 19 votes
One can understand your question in two ways, according to the definition of "the complement of CFL".

**case A:** Complement of CFL is the class of all the languages that are not in CFL. Formally, $$\overline{CFL} = \\{ L \mid L\notin CFL\\}.$$ In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc. But maybe that's not what you meant.

**case B:** Define the complement-CFL class as $$co{CFL} = \\{ \bar{L} \mid L \in CFL\\},$$ in words, the set of all languages $L$, such that $L$'s complement is context free.

In that case, what you wrote makes sense: $CFL \subsetneq P$ (by the CYK algorithm), and also $co{CFL} \subseteq P$ (run the same algorithm, output the opposite answer), and since $CFL \neq co{CFL}$, then it should be immediate that $co{CFL}\subsetneq P$, right?

# Answer
> 3 votes
A robust class that contains both CFL and coCFL is LOGCFL, which contains all languages logspace-reducible to a context-free language. This class is intermediate between NL and AC1, and has some natural complete problems. It can also be defined in terms of restricted AC1 circuits. LOGCFL is closed under complement (this is an extension of the argument used to show that NL=coNL).

# Answer
> -1 votes
Complement of CFL could possibly be CFL but not necessarily is. Complement of CFL is both recursive (R) and recursively enumerable (RE). Why? All CFLs are both R and RE. R languages are closed under complement (but RE are not). In that context, complement of CFL is R which is inherently RE.

---
Tags: complexity-theory, formal-languages, context-free, closure-properties, sets
---


# Question
Title: Are these three subset sum problems hard? How to solve them?
After asking this question I was thinking about some variants of subset sum problem (SSP).

The usual subset problem is the following.

* *Instance:* Given a set of $n$ integers and an integer $\sigma$.
* *Question:* Is there a non-empty subset that sums to $\sigma$?

The three variants of subset sum that I thought about are (I assume that all integers are positive):

1. SSP1:
    * *Instance:* Given a set of $n$ integers $\\{a\_1,\ldots,a\_n\\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    * *Question:* Is there a non-empty subset of cardinality at most $k$ that sums to $\sigma$? That is a subset $S$ for which $\sum\_{i\in S}a\_i=\sigma$ and $|S|\leqslant k$?
2. SSP2:
    * *Instance:* Given a set of $n$ integers $\\{a\_1,\ldots,a\_n\\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    * *Question:* Is there a non-empty subset of cardinality at most $k$ that sums to at most $\sigma$? That is a subset $S$ for which $\sum\_{i\in S}a\_i\leqslant\sigma$ and $|S|\leqslant k$?
3. SSP3:
    * *Instance:* Given a set of $n$ integers $\\{a\_1,\ldots,a\_n\\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    * *Question:* Is there a non-empty subset of cardinality at most $k$ that sums to at least $\sigma$? That is a subset $S$ for which $\sum\_{i\in S}a\_i\geqslant\sigma$ and and $|S|\leqslant k$?

My question is: Are these problems (SSP1, SSP2 and SSP3) hard?

**My claim is the following:** SSP1 is NP-complete but SSP2 and SSP3 are polynomial-time solvable.

*My Proof (intuitive and incomplete):*

* For SSP1, if I can find a subset $S$ of cardinality at most $k$, then $S\neq\emptyset$ and hence I have solved SSP.
* For SSP2, sort $\\{a\_1,\ldots,a\_n\\}$ in the ascending order. Select the first $k$ elements. If their sum is less than $\sigma$ then we are done. Else remove the biggest elements of the selected $k$ elements and see. Continue.
* For SSP3, sort $\\{a\_1,\ldots,a\_n\\}$ in the descending order. Select the first $k$ elements. If their sum is greater than $\sigma$ then we are done. Else output no.

Is my work correct?

# Answer
> 3 votes
Your work is mostly correct:

* SSP1 is clearly in NP. Moreover, it is NP-hard by reduction from SUBSET-SUM: given an instance of SUBSET-SUM, reduce it to the corresponding instance of SSP1 with $k = n$.
* SSP2: Let $m$ be the number of negative elements in $\\{a\_1,\ldots,a\_n\\}$, and let $S$ be the sum of the $\min(m,k)$ smallest of them. Check whether $S \leq \sigma$. This is a polynomial time algorithm.
* SSP3: Can be reduced to SSP2 by negating the set and $\sigma$. (We can also solve it directly just like SSP2.)

---
Tags: algorithms, np-complete
---


# Question
Title: In the Data Link Layer, is it better to use large or small frames?
I understand how the layer works to an extent, but cannot seem to figure out if the data link handles big frames more efficiently due to error detection or small frames better.

I am assuming from my understanding that the data link works better with small frames as it can save time by not having to keep retransmitting larger frames when an error is detected.

Is this reasoning correct?

*Havent used stackexchange in a long while so apologies if these type of questions are no longer permitted*

# Answer
Bigger frames mean a higher useful data fraction (same header size, more payload). But bigger frames mean a higher probability of the frame getting corrupted by random errors (thus getting lost). Larger frames mean higher latencies (need to wait for all of it to arrive, be checked, and handed to the application to be able to use any data in it). They also mean larger buffers might be a problem in limited devices).

As you can see, frame size is an exercise in compromise among a host of conflicting desirable measures.
> 1 votes

---
Tags: computer-networks, network-topology
---


# Question
Title: Prove correctness of recursive algorithm
I have this java function:

```
public int foo(ArrayList l, int n)
{
  if(n <= 1)
    return l.get(0);

  if(l.get(0) < l.get(1))
    l.remove(1);
  else
    l.remove(0);

  foo(l, n-1);
}

```

So I figure to show that the algorithm is correct I would use an induction proof. However what I am not so sure about is how to go about doing the proof. Will I fist need to derive some sort of mathematical formula for this function and prove that?

# Answer
> 4 votes
Generally, you should follow the instructions given by @vonbrand to carry out a mathematical induction proof for a recursive algorithm. Now I would like to show you more hints.

---

Playing with a small test case, we know that we should prove the following theorem:

> Theorem: The function `foo` always returns the minimum value of the original list $l$.

---

To carry out a mathematical induction *on the size $n$ of list*, we go through the following three steps:

* *Base Case:* $n = 1$. In this case, you obtain $l\[0\]$ which is trivially the minimum. (Note that `foo` throws an exception for case $n = 0$.)
* *Inductive Hypothesis:* Suppose that the theorem holds for $2 \le n \le k$.
* *Inductive Step:* Consider $n = k + 1$. You should prove that (***This is left as an exercise***) $$\min(\text{modified list } l' \text{ by the \`if/else\` statement and of size } k ) = \min(\text{original list } l \text{ of size } k+1).$$

# Answer
> 1 votes
The way to *understand* a recursive program is by the following steps:

* Find some measure by which the recursive calls are for "smaller" instances of the problem.
* Show that when it reaches the smallest instances, it gives the correct result (directly)
* Assuming the recursive calls do their job correctly, their results are combined to get the correct solution for the overall problem.

You should try some (small) cases by hand, to see what is going on (and find clues on the above points). When writing a recursive program, you'll have to think about the above items exactly the same way.

A correctness proof will have to consider essentially the same points, just more formally. No "mathematical formulas" are needed, just clear reasoning.

In your case, $n$ is an obvious measure of "size", that gets reduced each call. The rest is left as an exercise. ;-)

---
Tags: algorithms, algorithm-analysis, proof-techniques, induction
---


title: Indexing billion domain names / strings

text:
# Question
Title: Indexing billion domain names / strings
I am trying to find any datastructure/algorithm suitable to index & retrieve domain names & its associated documents.

The records that need indexing will typically be like:

```
www.facebook.com, 123
stackoverflow.com, 1231
www.facebook.com, 124
stackoverflow.com, 3456
cdn.facebook.com, 4566
google.com, 903002
google.co.nz, 2342
google.co.in, 84992
google.com, 902002

```

The retrieval will involve getting all the document ids(not top K but all of them) for a given search. Since it is content with a structure, people can query using part of domain names.

```
e.g. search for 'google' will lead to matching of all documents that have
google.co.nz,google.co.in & google.com associated with them.

```

# Assumptions

* As far as the distribution goes, less than 30% of the domain names will point to 80% of the documents.
* The number of records being indexed will be in hundreds of billions
* The index will most likely not fit into memory and will have to be stored in file-system

# Initial thoughts

* I thought of a solution where the domain names are tokenised(e.g. www.facebook.com gets tokenised into www,facebook,com,facebook.com,www.facebook.com) and hashed.
* The hash value lookup leads to all the documents that are part of the hash
* Some of the problems I see with this approach are
    + The values(document ids) are stored multiple times and some of the TLDs/commonly used subdomains(www) will have almost all the entries in them
    + Removing 1 entry will lead to updating multiple entries & their lists.
    + Hash collisions can affect the quality of results & hence hash function is quite vital to it
    + It won't be possible to address mis-spellings or substring search e.g. \*goog\*
    + The hash key will have to be 64-bit or more depending on the function

The question is what datastructure/algorithm to use to store & search for documents matching a given domain name.

Alternatively, if the above proposed solution is suitable, what can be a good hashing function given this context.

# Answer
> 0 votes
The standard solution is to build an *index*: a data structure that maps from search term to all of the records that match that search term. Your index could be a hashmap or a B-tree, for instance. In this case, the search terms are things like "google" or "facebook" or "facebook.com", and each one maps to a list of all records that match it. Thus, facebook.com would be associated with two search terms ("facebook.com" and "facebook") and would be present in two of these lists.

You raised some concerns about this approach, but they are all manageable:

* Yes, search terms like "com" will match many records. You should decide whether searching for "com" is useful or not. If it's not useful, don't include that in the index: build a list of "stopwords" (e.g., com, org, etc.), and don't include any of them in the index. For instance, you might decide that the TLD part of a domain name is not one of its matching search terms.
* Yes, inserting or removing one record will require updating multiple entries in the index. But this just isn't that big a deal. Most domain names have very few components: e.g., "www.google.com" will require changing 2 entries in the index (assuming you have blacklisted "com"), which just isn't that big a deal.
* Hash collisions are dealt with using standard methods for building hash tables and just aren't that big a deal. Or, you can use any other data structure, like a B-tree.
* No, this can't handle mis-spellings. Mis-spellings are an entirely different problem, which require a range of different solutions, and you should ask a separate question about that (but first, study Levenstein distance, metric trees, and data structures for spelling correction and answering nearest-neighbor search in the Levenstein distance metric -- there are a bunch of questions on this site that are relevant).
* No, there is no reason that the hash key needs to be 64 bits. The hash key needs to be at least the number of buckets in your hashtable.

I suggest you read some standard resources on building indices, e.g., in database textbooks, and read about how search engines work. Those topics are well-studied and those techniques will be applicable to your problem.

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


# Question
Title: recursively enumerable sets closed under concatenation
I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I must consider the Cartesian product $S\_1\times S\_2$ of two recursively enumerable sets $S\_1$ and $S\_2$. Then I construct the function $f':S\_1\times S\_2\rightarrow \lbrace 1\rbrace\cup\lbrace\perp \rbrace$ (where $\perp$ is undefined) such that: $$f'(x,y)=\begin{cases} 1 &\text{ if } x\in S\_1 \text{ and } y\in S\_2\\ \perp&\text{ otherwise} \end{cases}$$ Does the mere existence of this function $f'$ show that $S\_1S\_2$ is recursively enumerable? I'm still new to these proofs, so any help would be appreciated.

# Answer
> 1 votes
What you need to show is that given an algorithm that enumerates a (possibly finite) sequence $a\_1,a\_2,a\_3,\ldots$, and another algorithm that enumerates a (possibly finite) sequence $b\_1,b\_2,b\_3,\ldots$, then you can come up with another algorithm which enumerates all words of the form $a\_i b\_j$.

The simplest approach is to use the same idea that Cantor used to prove that the rationals are equinumerous with the integers, namely to come up with an algorithm that enumerates $a\_i b\_j$ in the following order: $$ a\_1 b\_1, a\_1 b\_2, a\_2 b\_1, a\_1 b\_3, a\_2 b\_2, a\_3 b\_1, \ldots $$ I'll let you to fill in the details.

---
Tags: computability
---


# Question
Title: NLP Classification: rule-based approach providing high precision but low recall
In NLP, rule-based/linguistic approaches are usually said to provide relatively high precision but low recall compared to for example machine learning approaches. I think this is often true for almost any classification task in NLP. However, I couldn't find a paper which specifically examines this phenomena. Can someone please name one? Alternatively, I'd be interested in a paper which generally compares different approaches in NLP classification tasks.

I did quite some googling but all I found is a very vague statement in here: http://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-15-285

# Answer
> 1 votes
I dont have enough reputation to add this as comment. Maybe this survey of text classification algorithms (including rule-based approach) could help you http://www.time.mk/trajkovski/thesis/text-class.pdf

---
Tags: natural-language-processing, classification
---


# Question
Title: Ways to implement a decision making process involving complex rules
I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with an example of online shopping cart.

Suppose you have a shopping cart like you have in every online retailer but this one checks some criteria and allow you to proceed only if the cart conforms to some **criteria**. Those criteria can depend on:

* a property of the item you add to your cart (ex: minimum quantity allowed for the item you add)
* combinations of the items you add (ex: if you have in your cart an item from sports category, you need to add an item from nutrition category)
* properties of the cart itself (ex: option to give multiple orders from the same cart but only if certain type of items are in the cart)
* and many other rules with exceptions...

So at a given time, your cart is in one of two states: **valid** or **invalid**. It starts with the state invalid: An empty cart. And at each action you take the state changes.

Some of the actions that change the state of the cart are:

* adding an item to cart
* changing a property of the item added, like color, size, quantity, etc
* changing a property of the cart, like applying a discount code.

What I'm trying to achieve is to find a clean way to decide after every action, whether the cart is in a valid state or not.

The current code base for this is a mess. A method of hundreds lines of code, taking 15 arguments and filled with ifs and fors.

I wonder what are the possible solution patterns I can use to refactor this into a cleaner and maintainable implementation.

I've investigated finite state machines but couldn't figure out how to represent this into states and actions. Decision making trees I've seen are for pretty simple flows when you can answer yes or no easily. And they were implemented with nested `if`s and `else`s which is quite similar to the current (messy) solution. My investigation lead me to AI and expert systems but I stopped there. As you can guess, I have no previous experience dealing with these kind of problems. Maybe what I'm trying to solve is a complex one and it's ok to have complex solutions to complex problems. But maybe this is a generic problem where you can give some direction to focus my research.

# Answer
> 0 votes
It sounds to me like the techniques here are not a matter of science (e.g., clever algorithms) so much as engineering (e.g., program structuring).

The approach I would suggest is to have a list of validators. Each validator is a function or object that, when passed a shopping cart, checks whether the cart satisfies a particular criterion. You have one validator per criterion in your business rules. Then, to check whether a shopping cart is valid, you can simply iterate over all the registered validator.

This lets you structure the program logic in a cleaner way. Each criterion is separated out into its own function or subclass. Thus, while you still might have hundreds of lines of code in general, this way there is some structure, and if you're lucky, most or all validators can be written in a fairly concise way, as each one deals with only a single concern/criterion.

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


# Question
Title: An online algorithm to find the Pareto frontier elements
I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements).

For instance. Given the following inputs, the retained Pareto frontier set would evolved as follows:

* `(3,7)`
    + insert element b/c it's the first element
    + pareto set now includes `{(3,7)}`
* `(7,3)`
    + insert element b/c it's not dominated in the first
    + pareto set now includes `{(3,7), (7,3)}`
* `(8,4)`
    + insert element b/c it's not dominated; remove `(7,3)` which it is dominated in both dimensions
    + pareto set now includes `{(3,7), (8,4)}`
* `(1,1)`
    + do not insert because it's dominate in both dimensions
    + pareto set now includes `{(3,7), (8,4)}`
* `(9,9)`
    + insert element b/c it's not dominated; remove all other elements because this dominates them in both dimensions
    + pareto set now includes `{(9,9)}`

In my example I'm using 2-tuples, but I'm looking for an algorithm that could handle N-tuples for "small" N (say \<10).

The naive solution is to just to compare each element with all elements currently in the set. In practice the naive approach might not be so bad (e.g. sub $O(n^2)$) because elements will regularly be expelled by the comparison set. But I was wondering if there was a known efficient algorithm for this. I'm interested in efficiency in memory and in computational complexity. (Ha! And as a matter of fact, I'm looking for the set of algorithms that are Pareto optimal with respect to memory and computational complexity.)

My current application of this is in building a Lucene search-document `Collector` that doesn't collect the most relevant documents (the typical use case for a search engine), but collects the Pareto optimal documents along specified dimensions.

# Answer
In two dimensions, each update can be done in $O(\lg n)$ time, by using a balanced binary tree data structure. But when you are working in a high-dimensional space, I don't know of any efficient solution.

Let me describe an efficient algorithm for the 2D case. Let $F$ denote the set of points in the Pareto frontier. Store $F$ in a balanced binary tree, using the $x$-coordinate of each point as its key. Note that when you sort $F$ by increasing $x$-coordinate, they'll also be sorted by decreasing $y$-coordinate.

Now, given a new point $(x\_q,y\_q)$, you can check efficiently whether it is Pareto-dominated by any element of $F$. Find the first element of $F$ to the right of $(x\_q,y\_q)$ (i.e., the element $(x,y) \in F$ such that $x \ge x\_q$ and $x$ is minimal); then checking whether it dominates $(x\_q,y\_q)$.

Also, given a new point $(x\_q,y\_q)$, you can efficiently find whether it Pareto-dominates any element of $F$. In particular, you can find indices $i,j$ such that the points $(x\_i,y\_i),(x\_{i+1},y\_{i+1}),\dots,(x\_j,y\_j)$ of $F$ are all Pareto-dominated by $(x\_q,y\_q)$ (assuming that the points of $F$ have been ordered by $x$-coordinate, Pareto-dominated points will be in a consecutive interval). Here's how. Find the first element of $F$ to the left of $(x\_q,y\_q)$ (i.e., the element $(x\_j,y\_j) \in F$ such that $x\_j \le x\_q$ and $x\_j$ is as large as possible), and check whether $(x\_q,y\_q)$ dominates it. If yes, find the smallest index $i$ such that $i\<j$ (so $x\_i\<x\_j$) and $y\_i \le y\_q$. Both of these steps can be done in $O(\lg n)$ time. (Finding $i$ can be done in $O(\lg n)$ time by treating the tree as branching on the $y$-coordinate of points, and taking advantage of the fact that the points of $F$ are sorted by decreasing $y$-coordinate.)

Now this tell us what to do. If $(x\_q,y\_q)$ is dominated by some point of $F$, then don't add it to $F$; you're done. Alternatively, if $(x\_q,y\_q)$ dominate points $i..j$ of $F$, then you need to delete those points from $F$ and add $(x\_q,y\_q)$ into $F$. This can be done in $O(\lg n)$ time, by noting that any interval of consecutive indices can be expressed as the union of $O(\lg n)$ subtrees of the binary tree (roughly speaking, you work with the siblings of the nodes along the path from $i$ to the root, and the same for the path from $j$ to the root); you can delete each subtree in $O(1)$ time. This lets us delete an entire range of consecutive points in $F$ in $O(\lg n)$ time, no matter how large the range is. For details, see Delete a consecutive range of leaves from a binary tree.

All of this can be done in $O(\lg n)$ time, using a balanced binary tree data structure.

This works in 2 dimensions (i.e., 2-tuples). In higher dimensions, the problem gets much harder. You can find references to the literature, with techniques for higher dimensions, at How to find a subset of potentially maximal vectors (of numbers) in a set of vectors; but I'm afraid that in high dimensions, all the known algorithms are likely to be fairly slow (they have a factor that is something like $O((\lg n)^{d-1})$ where $d$ is the number of dimensions).
> 4 votes

---
Tags: algorithms, search-algorithms
---


# Question
Title: Solving the recurrence $T(n)=T(n-1)*T(n-2)$
I have been trying to solve the following recurrence:

$$T(n)=T(n-1)\*T(n-2)$$ The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$.

I started by taking the $\log\_{2}$ of both sides to get

$$\log(T(n)) = \log(T(n-1)) + \log(T(n-2))$$

which looks an awful lot like a Fibonacci recurrence.

So if I set $S(k) = \log(T(n))$, then I have a recurrence of the form $$S(k) = S(k-1) + S(k-2)$$ with $S(0) = 1$ and $S(1) = 2$.

I can solve this easily using a characteristic polynomial and get

$$S(k) = A\*(0.5\*(1+\sqrt{5}))^k + B\*(0.5\*(1-\sqrt{5}))^k$$ where $A$ and $B$ are constants. To get $A$ and $B$ I use the initial conditions for $S$, namely $S(0) = 1$ and $S(1) = 2$.

The problematic part is that I think to get $T(n)$ I just simply raise $2$ to the power of the entire bunch above to get

$$T(n) = 2^{n\*A\*0.5\*(1+\sqrt{5})+n\*B\*0.5(1-\sqrt{5})}$$.

However, when I plug in some values for n to check I get some different integer values from the original recurrence.

Is my reasoning flawed somewhere in the process or am I just making an algebraic mistake somewhere?

Thanks!

# Answer
Your reasoning is perfect. To wit, here is what you get if you don't make any mistakes in your algebra. As you mention, $S(n)$ satisfies the Fibonacci recurrence, and furthermore $S(1) = 2 = F\_3$, $S(0) = 1 = F\_2$. We conclude that $S(n) = F\_{n+2}$. Therefore $T(n) = 2^{F\_{n+2}}$. The first few values are $$ 2, 4, 8, 32, 256, \ldots $$ To get a closed formula, note that $$ F\_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n. $$ Therefore $$ \begin{align\*} S(n) &= \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \\ &= \frac{3+\sqrt{5}}{2\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{3-\sqrt{5}}{2\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &= \frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n, \end{align\*} $$ using the fact that $(1\pm\sqrt{5})/2$ are roots of $x^2=x+1$.
> 4 votes

---
Tags: recurrence-relation
---


# Question
Title: How to prove the following language is not in R
Let $c\in \mathbb{N}$. Denote: $L \_c= \\{ \langle M \rangle \mid \exists \_{U \subseteq \Sigma ^\* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps $\\} $.

I would like to prove that for any given $c$ the language $L\_c \notin R $.

I would like to find a language $L \notin R$ and find a reduction $L \leq L\_c$, but Im having trouble as to which $L$ should I aim for.

I tried with $L\_{acc}$, $L\_{\Sigma^\*}$ , but could not find what my reduction should be.

Im not necessarily looking for a complete solution, but even a hint from which language and how my reduction should look like (an idea behind the reduction) would be also great, sonce I feel Im at a loss here and dont know whre to start from.

# Answer
Hint: This language is actually computable for every $c$. If $M$ terminates within $c$ steps, then it only gets to see at most $c$ symbols of its input, so in some sense its domain is finite.

There are some subtleties here. For example, it might be that there are also infinitely many inputs on which $M$ doesn't stop within $c$ steps. Perhaps it's better to first prove that the following language is computable for every $c$: $$ L'\_c = \\{ \langle M \rangle \mid \text{$M$ stops within $c$ steps on all inputs}\\}. $$
> 4 votes

---
Tags: computability, reductions, undecidability
---


# Question
Title: Minimum variable size if the information are coded in non-binary system
A typical HDD would represent information as either 1 (e.g. spin up) or 0 (e.g. spin down). Let's assume you want to represent the information physically in a hex system with 16 states, and assume this is possible with using some physical form (maybe the same spin).

What is the minimum physical size of a memory element in this new system in units of binary bits? It seems to me that the minimum is 8 bits = 1 byte. Therefore, going from a binary representation to a higher representation will, everything else equal, make the minimum variable size equal 1 byte instead of 1 bit. Is this logic correct?

# Answer
One hexadecimal digit contains 4 binary digits. You can compute this as follows: $\log\_2 16 = 4$. Alternatively, $2^4 = 16$. So the minimal memory element will contain 4 bits' worth of information.

This also works when the number of states is not a power of 2, but you have to be more flexible in your interpretation.
> 2 votes

---
Tags: knowledge-representation
---


title: Print Binary Tree Diameter Path

text:
# Question
Title: Print Binary Tree Diameter Path
Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT.

Print the Longest leaf to leaf path in a binary tree and its length

I worth an algorithm that calculates the diameter in Swift:

```
func diameter() -> Int {
 return diameterHelper(root).Diameter
}

typealias HeightAndDiameter = (Height: Int, Diameter: Int)

private func diameterHelper(node: TreeNode<T>?) -> HeightAndDiameter {

   guard let node = node else {
     return HeightAndDiameter(Height:0, Diameter:0)
   }

   let left  = diameterHelper(node.left)
   let right = diameterHelper(node.right)

   let height   = max(left.Height, right.Height) + 1
   let diameter = max(left.Height + right.Height + 1, max(left.Diameter, right.Diameter))

   return HeightAndDiameter(Height: height, Diameter: diameter)
}

```

I have tried to adapt this algorithm, but it doesn't work for all the cases.

```
  func diameterPath() -> [T] {
    return diameterPathHelper(root).Path
  }

  typealias HeightAndDiameterAndPath = (Height: Int, Diameter: Int, Path: [T])

  private func diameterPathHelper(node: TreeNode<T>?) -> HeightAndDiameterAndPath {

    guard let node = node else {
      return HeightAndDiameterAndPath(0, 0, [])
    }

    let left  = diameterPathHelper(node.left)
    let right = diameterPathHelper(node.right)

    let height = max(left.Height, right.Height) + 1

    if left.Height + right.Height + 1 > max(left.Diameter, right.Diameter) {
      let currentDiameter = left.Height + right.Height + 1
      let path = left.Path + [node.data] + right.Path
      return HeightAndDiameterAndPath(height, currentDiameter, path)

    } else {
      if left.Diameter > right.Diameter {
        return HeightAndDiameterAndPath(height, left.Diameter, left.Path)
      } else {
        return HeightAndDiameterAndPath(height, right.Diameter, right.Path)
      }
    }
  }

```

# Answer
> 0 votes
One natural approach goes as follows. Compute recursively for each node both the longest leaf-to-leaf path in the subtree rooted at the node, and the depth of the deepest leaf. From this information for the two children of a node you can compute the same information for the node itself. Once you have reached the root, you have obtained your answer.

The above only computes the *length* of the longest path, but you can actually extract the longest path itself from the data for each node. Details left to you.

---
Tags: binary-trees, recursion
---


# Question
Title: Computing farthest pair of points in d dimensions
Question: Given $n$ points in metric space, find a pair of points with the largest distance between them.

If we restrict ourselves to $d$-dimensional Euclidean space then, a naive algorithm of finding distances between all pairs of points in a space of dimension $d$ and selecting the maximum requires $O(dn^2)$ time.

However, finding a farthest pair for points in a plane can be done in time $O(n\log n)$. This is done by restricting our search to pairs of antipodal points on the convex hull. But, this approach does not scale well with higher dimensions.

Is there any solution better than the naive one either for the case $d=\Omega(n)$ (i.e., high dimensions) or for the case $d=O(\log \log n)$ (i.e., low dimensions)?

# Answer
> 3 votes
For the case $d = 3$, there exist $O(n\log n)$ algorithms due to Clarkson and Shor (randomized) and Ramos (deterministic). For higher dimensions there seem to exist only approximation algorithms, see for example a presentation of Vigneron. You can use the Johnson–Lindenstrauss lemma to reduce the problem (approximately) to dimension $O(\log n)$, in time $\tilde{O}(dn)$ (see for example Ailon and Chazelle).

---
Tags: algorithms, computational-geometry
---


# Question
Title: In this example of determinising an NFA, isn't there an edge missing in the result?
I am reading a computer theory book and came across the following example converting a NFA to a DFA:

My question is, would you not need an edge labeled $b$ going from the $x\_4$ node on the right to the null collection state?

# Answer
The standard definition of DFAs involves a transition function, that is total. That means that, from every state, there should be an arrow for each symbol. So, yes, there is a missing $b$ arrow from $q\_4$ to $\emptyset$ and also, missing $a$ and $b$ arrows from $\emptyset$ to itself. While we're at it, the diagram also has no indicated start state.

Note, though, that some authors use the convention that, if there's no transition given for some symbol from some state then, when the automaton reads that symbol in that state, it goes to a "dead" state. The dead state is non-accepting and the automaton cannot leave it (reading any character keeps it in that state). The author of your book might be using that convention inconsistently: the dead state is $\emptyset$ but they've only shown some of the transitions that lead to it. I think that's bad style: in my opinion, it's clearest to either show all the transitions to the dead state, or none of them.
> 2 votes

# Answer
Indeed, if you really insist on the $\emptyset$ node, then you definitively need an edge labeled 'b' going from the x(sub 4) node to the $\emptyset$ node. In addition, the $\emptyset$ node also needs edges labeled 'a' and 'b' going back to itself.

In my opinion, the insistence on the $\emptyset$ node is misguided anyway, especially if the task is to draw the DFA.
> 0 votes

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


title: Find Big O using Iteration

text:
# Question
Title: Find Big O using Iteration
I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step.

$T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ which then I got $T(n)=T(n-2)+2(n-1)+2n$. $T(n-2)$ gives $T(n-3)+2(n-3)$ which plugging it back in gives $T(n)=T(n-3)+2(n-3)+2(n-1)+2n$. I substituted the following $2(n-3)+2(n-1)+2n$ into a summation that gave me $\sum\_{i=0}^k 2(n-i)$$=-(k+1)(k-2n)$. I am not too sure how I should continue.

# Answer
> 2 votes
You're almost there. You correctly have $$\begin{align} T(n) &= T(n-1)+2n\\ &= \[T(n-2)+2(n-1)\] + 2n = T(n-2)+2(n-1)+2n\\ &= T(n-3)+2(n-2)+2(n-1)+2n\\ &= T(n-4)+2(n-3)+2(n-2)+2(n-1)+2n \end{align}$$ and in general, $$ T(n)=T(n-j)+2(n-j+1)+2(n-j+2)+2(n-j+3)+\dotsm+2n $$ Now all you need is the base value for the recurrence. Let's suppose that it was $T(0)=0$ (for the big-O estimate it really wouldn't matter if we had had, say $T(1)=3$ as our base).

To get to the base case, $T(0)$, we'd then need $n-j=0$. In that case, we'd have $$ T(n)=T(0)+2(1)+2(2)+2(3)+\dotsm+2n= \sum\_{k=1}^n2k=2\cdot\frac{n(n+1)}{2} = O(n^2) $$

# Answer
> 0 votes
You need to find the value of $k$. What's the last possible value for $i$? If you substitute $n$ by $1$ in the original formula, what form does the term $2n$ take? You get $2\*1$, which must equal $2(n-k)$. Thus, $k = n-1$.

---
Tags: recurrence-relation, landau-notation
---


title: XOR of one-way function

text:
# Question
Title: XOR of one-way function
Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”…

> The function is no longer one-way.
>
> we build a counter example in the following way. Assume $g$ is a one-way function that preserves size, and define $f$ on input $w=bx\_1x\_2$ in the following way, $$f(bx\_1x\_2) = \begin{cases} g(x\_1)\\,x\_2 & b=0 \\ x\_1\\, g(x\_2) & b=1 \end{cases}$$ (assuming $b\in\\{0,1\\}$ and $|x\_1|=|x\_2|$.) It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.
>
> Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z\_1z\_2$ with $|z\_1|=|z\_2|=n$. Then a possible preimage of $Z$ is $$u=0 \\,0^n \\,\langle g(0^n)\oplus z\_2\rangle$$ $$v=1 \\, \langle g(0^n)\oplus z\_1\rangle \\, 0^n$$
>
> because $f(u) = g(0^n)\\, \langle g(0^n)\oplus z\_2\rangle$ and $f(v) = \langle g(0^n)\oplus z\_1\rangle \\, g(0^n)$ thus their XOR gives exactly $z\_1\\,z\_2$ as required.

Wouldn't this counter-example imply that we've inverted $f$?

Consider the reduction where we take in $f(x\_1)$ and $f(x\_2)$: then we could compute $f(x\_1) \oplus f(x\_2)$, invert this to $x\_1x\_2$, and then we have inverted $f$ as well.

Is the quoted answer correct? If so, *why*, given my considerations outlined above?

# Answer
There are two reasons that counter-example wouldn't "imply that we've inverted".

(a)

Despite that answer's (probably-not-necessarily-correct) opening sentence,
it's only a counterexample to "$h$ is *necessarily* one-way", not to "$h$ is one-way".
(b)

That answer's attack does not require inverting  $\hspace{.04 in}f(x\_1) \oplus f(x\_2)$  "to $x\_1x\_2$",
it just involves finding a preimage of  $\hspace{.04 in}f(x\_1) \oplus f(x\_2)$  under $h$.
> 1 votes

# Answer
The question there asks:

> "If $f()$ is one way, is it true that $h(x\_1,x\_2)=f(x\_1)\oplus f(x\_2)$ is also one way."

This claim is incorrect. There exists some $f$ whose respective $h$ is not one way anymore.

However, the above doesn't apply to *all* $f$'s. It is possible that there exists *some* one-way $f$ whose respective $h$ remains one-way. But it needs not happen, as the example in that answer proves.

moreover, inverting $h$ means finding two inputs $x'\_1, x'\_2$ whose XOR after $f$ is given. this doesn't mean you get the same $x\_1$ you started with.

In better words: say you are given $y=f(x)$. now you try to invert it. So you pick some value $x'$ compute $y'=f(x')$ and invert $y \oplus y'$. Say after inverting, you get values $u,v$. All you know is that $f(u) \oplus f(v) = f(x) \oplus f(x')$, but there needs not be any relation between $f(x)$ and $f(u)$. Specifically, it is possible that $u\ne x$ and even $f(u) \ne f(x)$, etc.
> 1 votes

---
Tags: cryptography, one-way-functions, xor
---


# Question
Title: How to argue about semi-decidability of a problem?
I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it.

I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a program $\Pi$, such that $\Pi$ takes as input instance $I$ of $\mathcal{P}$, and if we have a positive instance, then $\Pi$ returns true, and on negative instance, $\Pi$ either returns false, or does not terminate.

Now, I tried to write a simple procedure like this:

Then, I tried to argue like this:

We can write a procedure $\Pi'$ that takes as input $(S,n)$, and simulates a run of $\Pi\_1$ on $S$, and a run of $\Pi\_2$ on $n$. We can show that such procedure $\Pi'$ is a semi-decision procedure, and we can distinguish the following cases:

1. Case 1. Suppose that $(S,n)$ is a positive instance, meaning $\Pi\_1$ outputs $I$ on input $S$, and $\Pi\_2$ outputs $I$ on input $n$. Then the simulation $\Pi'$ will encounter that $OUT1 = OUT2$, and output return true by its construction.
2. Case 2.1. Suppose that $(S,n)$ is a negative instance and it halts. Then, we have that $\Pi\_1$ outputs $I\_1$ on input $S$, and $\Pi\_2$ outputs $I\_2$ on input $n$, such that $I\_1 \neq I\_2$. Thus, $\Pi'$ does not halt due to its construction.

My problem is that, I cover just two cases, I believe I need one more case, where we have as output false, and terminate. Also, from the definition of semi-decidable program, I believe instead of using the pair $(S,n)$, I need to use the pair $(\Pi\_1, \Pi\_2)$, which is the actual instance of the problem. But, then how will I choose $S$ and $n$? If someone can help me with those questions, I would be glad.

# Answer
We know that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same cardinality, so there exists a bijection $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $s\_n$ be the $n$-th string in some enumeration, like $s\_1=\epsilon, s\_2=0, s\_3=1, s\_4=00, s\_5=01,\dotsc$ then consider the following semi-decider, where I leave it to you to fill in the missing parts: $$\begin{align} &\Pi'(\Pi\_1, \Pi\_2)=\\ &\quad\text{for }n=1,2,3,\dotsc\\ &\quad\quad\text{compute }f(n)=(i,j)\\ &\quad\quad\text{run }\Pi\_1(s\_i)\\ &\quad\quad\text{run }\Pi\_2(j)\\ &\quad\quad\text{... }\\ &\quad\quad\text{... }\\ &\quad\quad\quad\text{return accept} \end{align}$$

There are lots of bijections between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, here are a few to get you started.
> 1 votes

# Answer
Your solution doesn't make too much sense. What you want is a procedure that takes $\Pi\_1,\Pi\_2$ as input, not a string $S$ and an integer $n$. Also, in your proof you don't explain what values of $S$ and $n$ you are going to use.

Finally, you are not required to enter an infinite loop - you can always just return false. Think about it from a programmer's perspective - why would you ever enter an infinite loop on purpose? Infinite loops are there only since we can't avoid them in some cases. When we can, we do.

Try to think how you, as a human, would try to solve the problem. You would probably make two lists, one consisting of outputs of $\Pi\_1$, the other consisting of outputs of $\Pi\_2$, and constantly compare the two lists to see if there is any intersection. Formalize this method and you have answered your question.

Please spend a few hours thinking about this answer before commenting here. If things are still not clear, contact your TA, or read your textbook again, or find another textbook or lecture notes and read them instead.
> 1 votes

---
Tags: complexity-theory, semi-decidability
---


# Question
Title: Are there any papers published proving how University Time Table Scheduling Problem is NP-Complete?
I have been researching on finding optimal solutions to generating University Time Table using Genetic Algorithm. I am searching for a Academic Paper, that properly defines the University Time Table design problem and proves it is NPC.

# Answer
Simple Google search reveals a thesis from 2010 that defines and proves the complexity of scheduling university courses as NP-Complete. See Fig. 42 towards the end.

Lovelace, April L. "On the complexity of scheduling university courses." (2010).

There is also a technical report dating back to 1995 that does the same thing:

Cooper, Tim B., and Jeffrey H. Kingston. The complexity of timetable construction problems. Springer Berlin Heidelberg, 1996.
> 3 votes

---
Tags: np-complete, scheduling, research
---


# Question
Title: Using the Master theorem on a recurrence with non-constant a
I am trying to solve the following equation using master's theorem.

$T(n) = 3^n T(\frac{n} 3) + O(1)$

Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what my $a$ value is I don't think its just 3.

# Answer
This is not solvable using (only) the Master Theorem. It's not in the correct form. The Master Theorem only applies when there's a constant in front of the $T(n/b)$, and $3^n$ is definitely not a constant.

You should try calculating a bound for $\log(T(n))$ instead. Even though that won't give a tight bound it will get you on the right track.
> 6 votes

# Answer
Let's say that $T(n) = 3^n T(n/3) + C$. Then $T(n) \geq 3^n T(n/3)$ and $T(n) - C \geq 3^n (T(n/3) - C)$. This shows that in order to estimate the rate of growth of $T(n)$, it is enough to solve the recurrence $S(n) = 3^n S(n/3)$ with appropriate initial values (different for the lower and upper bounds). You haven't specified what the interpretation of $n/3$ is for $n$ which are not divisible by 3, but for powers of 3 we definitely have $$ \begin{align\*} S(n) &= 3^n S(n/3) = 3^{n+n/3} S(n/9) = \cdots = 3^{n+n/3+n/9+\cdots+3} S(1) \\ &= 3^{n(1 + 1/3 + 1/9 + \cdots + 1/(n/3))} S(1) \\ &= 3^{(3/2)n - (3/2)} S(1) \\ &= \Theta(3^{(3/2)n}). \end{align\*} $$ We conclude that, at least for powers of 3, $T(n) = \Theta(3^{(3/2)n})$.
> 1 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Number of submatrices, of a base matrix derived from an array, with a particular sum
Given an **N** sized array **A** of unsorted integers and an integer **K**, derive a square matrix **M** of order **N** where $ M\_{ij} = A\_i * A\_j $, and return the number of sub matrices of **M** where the sum of all of its elements is **K**.

Example:

$A = \begin{Bmatrix}1&-1\end{Bmatrix}$
$K = 0$

Thus:
$M = \begin{Bmatrix}1 & -1\\\-1 & 1\\\end{Bmatrix}$

So, there are **5** submatrices where the sum of its elements is 0:
$ M\_{00}...M\_{01} = 1 + (-1) = 0$
$ M\_{10}...M\_{11} = (-1) + 1 = 0$
$ M\_{00}...M\_{10} = 1 + (-1) = 0$
$ M\_{01}...M\_{11} = (-1) + 1 = 0$
$ M\_{00}...M\_{11} = (-1) + 1 + (-1) + 1 = 0$

Brute force is obvious and it costs $O(n^4)$, but I'm looking for a less naive solution. The first thing that comes to mind (at least mine) is two pointer algorithm, but it works only when there are no negative members, which is not the case. If it were it would make this question a duplicate of this one.

I believe there is a smarter way to solve this because of the correlation between **M** and **A**, but I can't figure out how.

# Answer
Try writing a small example (e.g., where $N=3$), then pick a submatrix (say, $2 \times 2$) and write an expression for the sum of the elements of that submatrix in terms of the entries of $A$. By doing some algebraic manipulations, you should be able to get a nice expression for this sum.

This will then let you characterize which submatrices sum to $K$, in terms of the entries of $A$. Working on this a bit, you should be able to get a $O(N^2)$ time algorithm \[assuming a submatrix is defined by a consecutive range of rows and a consecutive range of columns\].

Since this is your exercise/programming contest problem, I'll let you work out the details.
> 1 votes

---
Tags: algorithms, dynamic-programming, arrays, matrices
---


# Question
Title: How does DFS produce MST and All pairs shortest paths in unweighted graphs?
I was reading *Application of DFS* from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me.

> For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

*My doubt*: Is there anything "Minimum spanning tree" for unweighted graph. I mean after all it is unweighted so what is sense of MST here? And I completely don't understand how DFS produces all pair shortest path. Would anybody mind elaborating this a bit.

# Answer
There are two claims here.

> For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.

This is true; in unweighted graphs, *every* spanning tree is minimal since they all have the same number of edges, $n-1$.

A nitpick I'd have is "the"; they should write "*a* minimum spanning tree".

> For an unweighted graph, DFS traversal of the graph produces the all pair shortest path tree.

This is false, it doesn't even produce a single-source shortest path tree. See here.

In general, an APSP tree *may not even exist*. There are $n(n-1)$ shortest paths to encode, and it would be quite the coincidence if they shared only $n-1$ edges. Which *can* happen, e.g. in acyclic graphs, but it is certainly not always true. I'll leave it to you to come up with a small counter example.
> 4 votes

# Answer
*Unweighted* in your blog post is probably a typo for *undirected*. However, even under this interpretation the blog post is wrong. See this question regarding DFS and minimum spanning tree, for example.

Don't take blog posts too seriously.
> 2 votes

---
Tags: graphs, data-structures, graph-traversal
---


# Question
Title: What do you call a function from symbols of alphabet to languages?
Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows:

Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, where $L'$ is some language. I also met this definition: $f:\Sigma \to 2^{\Delta^\*}$.

The reason I'm asking this is because I study in a language which is even more foreign to me than English, and it's hard to find what the terminology in the book means. I've only encountered this in connection to context-free languages, but since I don't really know what I'm looking at, I can't tell if that's something specific to them (my guess though is that it's not).

---

In the book I'm reading from, (which also happens to be in Hebrew) the word used to describe this concept is "הצבה", literally meaning "substitution" or "positioning", "fixing something in place".

# Answer
> 5 votes
It looks like it refers to a *substitution*, but that the given definition is incomplete.

Anyway, in formal language theory, people often use monoid morphisms between free monoids. To avoid overloading the term "morphism", a monoid morphism from a free monoid $A^\*$ into the monoid $2^{B^\*}$ of languages of $B^\*$ (under concatenation product of languages) is often called a *substitution*.

Now, since a morphism from $A^\*$ into any monoid is entirely defined by the image of its letters, a substitution from $A^\*$ to $B^\*$ might be given as a map $\sigma: A \to 2^{B^\*}$. But then it is extended to a map $A^\* \to 2^{B^\*}$ by setting $\sigma(1) = \\{1\\}$ and $\sigma(a\_1 \dotsm a\_n) = \sigma(a\_1) \dotsm \sigma(a\_1)$.

**Reference**. Page 5 in First four chapters of Berstel's book Transductions and Context-Free Languages, Teubner (1979). (Page 13 in the printed version)

---
Tags: formal-languages, terminology, strings
---


# Question
Title: Creating a DFA that only accepts number of a's that are multiples of 3
I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my understanding something like "aaabbaaa" would work but "aabbb" would not. Any help or hints would be greatly appreciated

# Answer
> 3 votes
The key idea here is to make a ring of three states, $q\_0, q\_1, q\_2$ with $a$ transitions $$\begin{align} q\_0 & \stackrel{a}{\rightarrow}q\_1\\ q\_1 & \stackrel{a}{\rightarrow}q\_2\\ q\_2 & \stackrel{a}{\rightarrow}q\_0 \end{align}$$ On input $aaa$, for example, you'll start in state $q\_0$ and pass to state $q\_1$ on the first $a$, $q\_2$ on the second, and back to $q\_0$ on the third $a$. Clearly, any multiple of three $a$s will leave you in state $q\_0$, so we make that a final state.

What to do about $b$s in the input? They don't have any effect on the number of $a$s, so include transitions $$\begin{align} q\_0 & \stackrel{b}{\rightarrow}q\_0\\ q\_1 & \stackrel{b}{\rightarrow}q\_1\\ q\_2 & \stackrel{b}{\rightarrow}q\_2 \end{align}$$ and you're done. In fancier terms, we're $q\_n$ to "remember" whether the number of $a$s seen so far was congruent to $n\pmod{3}$. This idiom, using the states to remember certain situations, is fundamental when designing FAs.

# Answer
> 1 votes
We need that the number of $a$'s will be only multiple of $3$, e.g words like $aaa,baaab,bababa,bbbbaaaaaa,\dots$ ets, so we will put the accept state on place such that the number of $a$'s $\mod(3)=0$ e.g $0\mod(3)=0,3\mod(3)=0,6\mod(3)=0,\dots$

Try this DFA:

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


# Question
Title: Is the set of TMs that does not reach most cells to the right computable?
Let $L\_{NTF} = \\{ \langle M \rangle \mid $ for every $x\in\Sigma^\* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \\}$.

I would like to prove or disprove $L\_{NTF} \in RE$.

I know how to easily prove that $L\_{NTF} \in Co$-$RE$, because it is enough to find one word $x$ such that $M$ will reach the $|x|+10$'th cell during its calculation on $x$. There is a finite number of configurations as long as the machine does not reach the $|x|+10$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $|x|+10$'th cell it is fine by me. That is to say, for a given input $x$ I can decide whether or not it reaches the $|x|+10$'th cell during $M$'s calculation on $x$.

So this tells me that $\overline{L\_{NTF}}\in RE$, that is $L\_{NTF}\in Co$-$RE$.

But this idea will not assist me in proving $L\_{NTF}\in RE$ because I may accept a TM $\langle M\rangle$ **only** after I will iterate over all possible $x\in \Sigma^\* $, and since $\Sigma^\*$ is $\aleph\_0$ I will never accept a TM $\langle M\rangle$. This is my intuition for why $L\_{NTF} \notin RE$.

So for proving this I have 2 options:

1. Showing a reduction $L\leq L\_{NTF}$ where $L\notin RE$. I've tried using $\overline{L\_{acc}}, L\_d$ and $L\_{\Sigma^\*}$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $L\leq L\_{NTF}$ where $L\notin R$. This will also be sufficient because it will prove me that $L\_{NTF}\notin R$, and since I know $L\_{NTF}\in Co$-$RE$ having $L\_{NTF}\in RE$ will lead to a contradiction, thus we can deduce $L\_{NTF}\notin RE$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

# Answer
> 3 votes
Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

* Given $x$, $M'$ overwrites $x$ with $\langle M\rangle$ up to length $|x|$ or end of $\langle M\rangle$, whichever comes first. Writes blanks on the rest of $x$, and puts an end marker on cell $|x|+1$.
* $M'$ returns to the beginning of input and simulates $M$.
* If $M$ accesses end marker at any point, $M'$ enters an infinite loop without moving any further to the right.
* If $M$ accepts, $M'$ goes infinitely to the right.

Note this $M'$ has the following properties:

* If $M$ halts on $\langle M\rangle$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
* If $M$ does not halt on $\langle M\rangle$ then $M'$ will never access $|x|+10$th cell.

# Answer
> 1 votes
Hints:

1. Show that every Turing machine can be simulated by another Turing machine that never reaches the $|x|+10$th cell.
2. If a Turing machine halts, you can modify it so that it *does* reach the $|x|+10$th cell.
3. Reduce the halting problem to your language.

---
Tags: computability, reductions, semi-decidability
---


title: How to show that a problem is easy?

text:
# Question
Title: How to show that a problem is easy?
Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc.

> My question is: If I reduce a known polynomial time problem (say, maximum matching in bipartite graph) to $P$, why I can say that $P$ is an easy problem?

---

> My guess is: No, we cannot say that.
>
> Why? Because from an instance of maximum matching problem, $I\_{ MM }$, I create an instance of $P$, $I\_{ P }$, and then I show that maximum matching is solved with $I\_{ MM }\iff P$ is solved with $I\_{ P }$.
>
> But what if from another instance of maximum matching problem, $I\_{ MM }'$ , I create another instance of $P$, $I\_{ P }'$, which is hard to solve?

I have read that the reduction is correct and works, for example from sorting to convex hull, but I do not why.

I do not know what I am missing here.

# Answer
> 3 votes
You are right. Any problem in $\mathsf{P}$ can be (polytime) reduced to the halting problem, for example. (In fact, any problem in $\mathsf{P}$ can be polytime reduced to *any* non-trivial language, that is any language other than $\emptyset$ or $\Sigma^\*$.)

What is true is that if A reduces to B and B is easy, then so is A. In particular, if A polytime reduces to B and B is in $\mathsf{P}$, then A is also in $\mathsf{P}$.

---
Tags: complexity-theory, reductions
---


# Question
Title: Does exponentiation reduce to multiplication or the other way around?
Is is more accurate to say that in complexity theory:

$$\text{exponentiation} \leq\_p \text{multiplication}$$

or

$$\text{multiplication} \leq\_p \text{exponentiation}$$

I understand that if we know how to do multiplication, then we can run multiplication in a loop in polynomial time to get the answer to the exponentiation problem.

But which of the two reflects this? Do we say exponentiation reduces to multiplication (the first one), or the other way around (the second one)?

# Answer
> 3 votes
*Both* statements are accurate, assuming $\le\_p$ refers to polynomial-time Turing reductions (i.e., Cook reductions), and assuming that in the exponentiation problem, the exponent is specified in unary (otherwise you can't exponentiate in polynomial time). Given an algorithm to multiply in polynomial time, you can use it to exponentiate in polynomial-time via a Turing reduction, since $a^k = a \times a \times \cdots \times a$. Also, given an algorithm to exponentiate in polynomial time, you can use it to multiply in polynomial time via a Turing reduction, since $ab = \[(a+b)^2 - a^2 - b^2\]/2$. That said, since both multiplication and exponentiation can be computed in polynomial time directly, there's really no need for such a fancy reduction: it's immediate from the definitions that any problem in P reduces to any other problem in P.

You might want to refresh your understanding of the definition of the reductions.

Note that we usually apply reductions to languages, i.e., to decision problems. So, to really understand how to apply the formal theory to your question, you'd first need to re-cast it as a question about a formal language or about a decision problem. "Multiplication" is not a decision problem. Re-casting as a decision problem will complicate things a little bit, and change the nature of the reductions (for instance, the reductions I hinted at above might no longer work), but the bottom line will still remain true: since you can reduce any problem in P to any other problem in P, there will be a reduction in both directions.

See also What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, What is the difference between an algorithm, a language and a problem?, and NP-completeness: Reduce to or reduce from?

---
Tags: complexity-theory, reductions
---


title: Recognizing primitive recursion

text:
# Question
Title: Recognizing primitive recursion
I am trying to write a program to recognize if a given lambda calculus expression is primitive recursive. I believe that a general algorithm to do this does not exist, but I am interested in the most general algorithm. This is a subset of the primitive recursive functions in the LC.

Primitive recursion is built up from the following rules: "http://safalra.com/lambda-calculus/partial-recursive-functions"

To outline some of these rules

* `(λfx. x)` is zero
* `(λnfx. f (n f x))` is successor
* etc...

Now in my program I can just recognize these axioms directly. My confusion is what happens when I get to things derived from them. Take the number 5 for example encoded as `(λs.(λz.(s (s (s (s (s z)))))))`. This is the result of applying the the successor function to zero 5 times. But the above expression is not one of the axioms. I believe that the rule set says that the result of primitive recursive functions are also primitive recursive, but I do not see how given one of these results the result can be shown primitive recursive.

What I mean is that given just the encoding of the number 5 how can I show that it is primitive recursive? That is without brute force search building up from the axioms. Also is my method of representing the primitive recursion axioms correct (for suc and zero) or are the axioms not that literal? Thanks!

# Answer
> 0 votes
I found this post on stack exchanges CS theory section:

https://cstheory.stackexchange.com/questions/20364/how-to-make-the-lambda-calculus-strong-normalizing-without-a-type-system

It is very similar to what I was looking for.

---
Tags: lambda-calculus, primitive-recursion, church-numerals, static-analysis
---


# Question
Title: What is a proper way of solving a multibody nonlinear problem?
I encountered some system of ~5000 random nodes connected by ~8000 non-hookean springs, with ~1300 nodes at the boundary fixed as the "wall", the potential of the springs are of the form $dx\*e^{(dx/a)}$ where $a$ is a constant and $dx$ the strain (displacement/original length) of the spring, I am using Monte Carlo method to find the energy-minimized configuration after I performed some "perturbation", say, a simple shear or a isotropic expansion of the whole system.

It seems that the conventional energy minimization schemes such as "steepest Descent", or "simulated annealing" is not working as efficiently here as the case of linear situations, it always fail to converge to a satisfactorily balanced state.

Could someone share your experiences in dealing with such non-linear situations?

Thank you so much!

# Answer
OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty efficiently.

Thanks for everyone who gave me suggestions and guidance to the right path!

Have fun (mixed with a lot of frustrations) with modeling!
> 2 votes

---
Tags: monte-carlo
---


# Question
Title: How can we find the channel capacity from a BSC? (information theory)
I'm struggling to find how to calculate the channel capacity from a binary symmetric channel, given

> alpha(mean error) = 0.25
> p(x1) = 0.25,
> p(x2) = 0.75
> r = 1.25MBits/sec

I found this in the course:

> C = r . { 1 - omega(alpha) }

So I'd have

```
C = 1.25Mbits/sec * { 1 - omega(0.25) }

```

However, I'm stuck on how to calculate the omega(0.25) (binary entropy of the mean error).

We've never seen how to solve these exercises during the course, so any help would be very appreciated.

# Answer
> 1 votes
I'm fairly confused by your question / terminology.

In any case, for a BSC channel with error probability $p$
(i.e., the channel $$P\_{Y\mid X} (y \mid x) = \begin{cases} p & y\ne x \\ 1-p & y=x \end{cases}$$),

it is known that the capacity of the channel is $1-H(p)$ where $H()$ is the binary entropy function, $H(x) = x \log\_2 (\frac1x) + (1-x)\log\_2 (\frac1{1-x})$.

That is, for a BSC with $p=0.25$, the capacity is $1-H(0.25)=1-0.811=0.188$. This is per channel instantiation, so multiply by $r$ to get what it seems you want.

---
Tags: information-theory
---


# Question
Title: Greedy strategy for computing the minimum number of rays that hit all balloons
The *minimum zap problem* below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm".

> The *minimum zap problem* can be stated more formally as follows. Given a set $C$ of $n$ circles in the plane, each specified by its radius and the $(x, y)$ coordinates of its center, compute the minimum number of rays from the origin that intersect every circle in $C$. Your goal is to find an efficient algorithm for this problem. (See a "9-balloons-with-4-rays" example in the figure below)

> *Question:* Suppose it is possible to shoot a ray that does not intersect any balloons. Describe and analyze a greedy algorithm that solves the minimum zap problem in this special case.

---

I'm having trouble approaching this problem. I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

And what is the point of the fact that there is a ray that does not intersect any balloons? Am I supposed to prove that some optimal solution uses this fact?

Any help would be appreciated! I just recently started learning algorithms :)

---

Algorithm based off of hengxin's answer: https://cs.stackexchange.com/a/52293/42816

**Proof by mathematical induction**

Note: Did not use O( n log n) implementation

Now we will prove the correctness of this algorithm using mathematical induction. We will show that our greedy algorithm cannot do worse than the optimal solution.

Let $S'$ be the set of rays shot by our greedy algorithm. Let $S$ be the set of rays shot by another optimal solution.

Our base case is when $n = 1$. There is only one object to destroy, and our greedy algorithm uses 1 ray, which also happens to be optimal. So this checks out.

Now for our induction hypothesis, we will assume that our greedy algorithm is optimal for up to $n$ objects.

We now claim that the first ray from $\alpha$ of $S'$ cannot do worse than that of $S$.

Now let's consider an $n+1$ object situation. Then, we sort $S'$ and $S$ according to $\alpha$, clockwise. Now let's examine the first ray that occurs from $\alpha$ clockwise. In $S'$, this first ray, call it $R'$, cannot possibly do worse than that of $S$, call it $R$, because our greedy algorithm says that this ray will intersect the most objects, including the first one from $\alpha$. Therefore, $R$ either intersects just as much or fewer objects than $R'$. Thus, we can replace $R$ with $R'$ in the optimal solution $S$.

Now, we have to figure out if the rest of $S'$ is optimal, cutting out $R'$, which we'll call $T'$. However, since there are now at most $n$ objects, our induction hypothesis says that our greedy algorithm finds an optimal solution to $T'$. As such, the $R' + T'$ problem has an optimal solution from our greedy algorithm. Q.E.D.

# Answer
> 2 votes
***Principle:*** You need to shoot the rays in some order and choose carefully the proper direction/angle for the first ray.

> $Q\_1:$ I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

See the figure in the problem. Suppose there are only 4 balloons: the two green ones and the two blue ones. If you shoot your first ray along the x-axis (this is allowed by your greedy strategy. note that I suppose that the three bigger balloons cannot be hit by a single ray; otherwise, move them around slightly), you will leave the two other balloons far apart. As a result, it costs you 3 rays, but the optimal is 2.

> $Q\_2:$ What is the point of the fact that there is a ray that does not intersect any balloons?

So the key point is to shoot the first ray along the right direction. Here comes the fact that "there is a ray that does not intersect any balloons".

The basic idea is as follows:

* first find the direction/angle $\alpha$ along which a ray does not intersect any balloons;
* then identify the first balloon (say, clockwise) $b$ with respect to this direction/angle $\alpha$; Here $b$ is defined to be the first balloon you leave when you sweep a line starting from the direction/angle $\alpha$ clockwise.
* shoot a ray which is $b$'s rightmost (clockwise) tangent line $l$， remote all balloons hit by $l$,
* and then recurse.

> $Q\_3:$ Am I supposed to prove that some optimal solution uses this fact?

It is not easy to prove a greedy strategy is correct. You can try to prove the idea above by applying mathematical induction and exchange argument (*or maybe show it is wrong!*). A hint is to consider the set of rays shot by an arbitrary algorithm, sort them by angles with respect to $\alpha$ (clockwise), then compare it to the optimal solution one by one.

---

***Implementation:*** In the comments, OP asks for an $n \log n$ algorithm. Well, $n \lg n$ often means that you can sort some things first. Maybe sort all the balloons by the angles of their right (clockwise again) tangle lines. Then it is easy to apply the greedy strategy above. This is a rough idea. How to implement it efficiently by choosing/designing good data structures is left as an exercise.

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Can you explain this exercise solution to me?
A process running on CTSS (Compatible Time Sharing System) needs 30 quanta to complete. How many times must it be swapped in, including the very first time (before it has run at all)?

• Answer : The first time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped in 5 times.

why does it get 2,4,8,15 on the succeeding runs?

# Answer
> 3 votes
According to this article: F. J. Corbató, M. M. Daggett, R. C. Daley, An Experimental Time-Sharing System (IFIPS 1962), CTSS uses a "multi-level scheduling algorithm":

> The basis of the multi-level scheduling algorithm is to assign each user program as it enters the system to be run (or completes a response to a user) to an $\text{ell}$-th level priority queue. The process starts with the time-sharing supervisor operating the program at the head of the lowest level occupied queue, $\text{ell}$, for up to $2^\text{ell}$ quanta of time and then if the program is not completed (i.e. has not made a response to the user) placing it at the end of the $\text{ell}+1$ level queue. Programs are initially entered into a level $\text{ell} = 0$.

A program at the ell-th level is assigned $2^{\text{ell}}$ quanta.

Now you know how to solve your exercise.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: NP-Completeness: A question about reduction and hardness
I am trying to understand the definition / meaning of reduction.

1. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq\_{x} B$? For example $\text{SAT} \leq\_{polynomial} \text{3-SAT}$.
2. If we are reducing problem $A$ to $B$ in $x$-time, does it mean that you take an instance in problem $A$, and modify it such that it becomes a valid input for problem $B$, such that the modification is done with $x$ time complexity?

# Answer
> 0 votes
As far as I know, the first point is correct. For the second point you missed the fact that "solve $A$ with the given instance iff solve $B$ with the created instance".

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


# Question
Title: What happens to uninterpreted predicates in Ackermann's reduction?
I know the procedure to apply the Ackermann's reduction to a formula that doesn't involve uninterpreted predicates. But, how do we treat the uninterpreted boolean predicates? Nearly all the examples I have seen, usually just assume there are no uninterpreted predicates, and give examples of simpler reductions, but if we have something like this:

$$p(z, F(x\_1)) \wedge F(F(x\_1)) = G(x\_2,G(x\_1,x\_3,x\_4),F(x\_2)) \rightarrow p(x\_1,y)$$

How will I get rid of the uninterpreted predicate, so that I can apply the usual reduction?

# Answer
> 4 votes
Essentially, you can treat uninterpreted predicates as boolean-valued functions (adding a new boolean sort if necessary) and replace them with boolean variables as you would other functions. For the given example:

Getting rid of $F$ and $G$ first:

$$\begin{align\*} p(z,f\_1)&\wedge f\_2=g\_1\to p(x\_1,y)\wedge x\_1=f\_1\to f\_1=f\_2\\ &\wedge x\_1=x\_2\to f\_1=f\_3\wedge f\_1=x\_2\to f\_2=f\_3\\ &\wedge (x\_1=x\_2\wedge g\_2=x\_3\wedge f\_3=x\_4)\to g\_1=g\_2 \end{align\*}$$

Introduce boolean variables $b\_1,b\_2$ for $p(z,f\_1)$ and $p(x\_1,y)$, respectively, and add a condition that they are equivalent when the arguments agree:

$$\begin{align\*} b\_1 &\wedge f\_2=g\_1\to b\_2\wedge x\_1=f\_1\to f\_1=f\_2\\ &\wedge x\_1=x\_2\to f\_1=f\_3\wedge f\_1=x\_2\to f\_2=f\_3\\ &\wedge (x\_1=x\_2\wedge g\_2=x\_3\wedge f\_3=x\_4)\to g\_1=g\_2\wedge (z=x\_1\wedge f\_1=y)\to(b\_1\leftrightarrow b\_2) \end{align\*}$$

---
Tags: satisfiability, boolean-algebra, automated-theorem-proving
---


# Question
Title: Reconstruction of drawing sequence from video
I have a video that record the drawing sequence with a pencil by a painter.  I want to reconstruction the sequence from the video. And I have google some keywords like "drawing sequence reconstruction", "sketch reconstruction", and have searched like "moving object detection" but cannot found what I want to find.

I want to know how to detect and recognize the drawing between different frames. I have thought the "line detect" algorithm may work but fail. And pixel comparison seems to be bad idea. Because that the new drawing may overlap the old ones.

Could you give me some information that I can read or some keywords to search? Sorry about that because I am not familiar with Computer Image Processing.

# Answer
> 1 votes
You should have a look at background segmentation algorithms. The hand is moving over the rather static drawing. One very simple approach would be to store the last N images and compute the variance of the color for each pixel. The pixels with a low variance will be your painting (and the canvas you draw an) so a subsequent thresholding should seperate the drawing from the canvas.

# Answer
> 1 votes
I assume you have clean background like in the picture:
0) you take first frame - this is your initial data.
1) take next frame, then subtract previous from it - here white pixels are freshly drawn and black are unchanged.
If your frames are from compressed video - threshold them to avoid taking blurred parts.

You have not stated if stylus (pencil) is there - probably pixels are to be erased - in such case pixels under stylus should be flagged as overlapped and the drawn pixels are to be retreived from last nit overlapped frames.

After this operations you have pure pixels - 8-connected flood fill from changed pixels (if drawing was not continous - one per component).
Line detection is computationally expensive and works for lines / segments, but hand drawing gives poor results.

---
Tags: algorithms, graphs, image-processing, computer-vision
---


# Question
Title: Solving a recurrence relation with √n as parameter
Consider the recurrence

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\\,n$

for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.

I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?

# Answer
We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get

$$ \begin{align\*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align\*}. $$ where $\beta(n)$ is how many times you have to take the square root to start with n, and reach 2. It turns out that $\beta(n) = \log \log n$. How can you see that? Consider: $$ \begin{align\*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align\*} $$ So the number of times you need to take the square root in order to reach 2 is the solution to $\frac{1}{2^t} \log n \approx 1$, which is $\log \log n$. So the solution to the recursion is $c n \log \log n + \frac{1}{2}n$. To make this absolutely rigorous, we should use the substitution method and be very careful about how things get rounded off. When I have time, I will try to add this calculation to my answer.
> 11 votes

# Answer
In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:

$$\begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align}$$ Now let's simplify things even further, by changing to logs (since $\lg \sqrt{n} = (1/2)\lg{n}$). Let $$\begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align}$$ Aha! This is a well-known recurrence with solution $$ S(m)=\Theta(\lg m) $$ Returning to $T(\\,)$, we then have, with $n=2^m$ (and so $m=\lg n$), $$ \frac{T(n)}{n} = \Theta(\lg\\,\lg n) $$ So $T(n) =\Theta(n\\,\lg\\,\lg n)$.
> 16 votes

# Answer
If you write $m=\log n \space$ you have $T(m) = {m \over 2}\cdot T({m\over 2}) + c\cdot 2^m\space$.

Now you know the recursion tree has hight of order $O(\log m)$, and again it's not hard to see it's $O(2^m)\space$ in each level, so total running time is in: $O((\log m) \cdot 2^m)\space$, which concludes $O(n \cdot \log \log n)\space$ for $n$.

In all when you see $\sqrt n $ or $n^{a \over b}, a\<b \space$, is good to check logarithm.

<sub> P.S: Sure proof should include more details by I skipped them. </sub>
> 6 votes

# Answer
Let's follow Raphael's suggestion, for $n = 2^{2^k}$: $$ \begin{align\*} T(n) = T(2^{2^k}) &= 2^{2^{k-1}} T(2^{2^{k-1}}) + c2^{2^k} \\ &= 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) + c(2^{2^k} + 2^{2^k}) \\ &= \cdots \\ &= 2^{2^{k-1}+2^{k-2}+\cdots+2^0} T(2^{2^0}) + c(2^{2^k} + 2^{2^k} + \cdots + 2^{2^k}) \\ &= 2^{2^k-1} + ck2^{2^k} \\ &= (c\log\log n + 1/2)n. \end{align\*} $$

Edit: Thanks Peter Shor for the correction!
> 2 votes

# Answer
Unravel the recurrence once as follows: \begin{align} T(n) &=& \sqrt{n}~ T(\sqrt{n}) + n \\ &=& n^{1/2} \big ( n^{1/4} ~ T(n^{1/4}) + n^{1/2}\big) + n \\ &=& n^{1-1/4}~ T(n^{1/4}) + 2n. \end{align}

Continuing the unraveling for $k$ steps, we have that: \begin{align} \label{eqn:unrav} T(n) &=& n^{1-1/2^k} T(n^{1/2^k}) + kn. \end{align}

These steps will continue until the base case of $n^{1/2^k} = 2$. Solving for $k$ we have:

\begin{align} &&n^{1/2^k} = 2 \\ &\implies& \log n= 2^k \\ &\implies& k= \log \log n. \label{eqn:ksol} \end{align}

Substituting $k=\log \log n$ into the unraveled recurrence, we have \begin{align} T(n) = \frac{n}{2} T(2) + n \log \log n. \end{align}
> 1 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


title: Proving that if A⊕B ∈ NP then NP = coNP

text:
# Question
Title: Proving that if A⊕B ∈ NP then NP = coNP
I got this question:

> Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$.
>
> Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$.

But I don't know how to proof the direction that if $A,B\in NP$ and $A \oplus B\in NP$ then $NP = coNP$.

I have tried to build the non-deterministic machines for $\bar{A}$ and $\bar B$, but I don't know how.

What that I tried: Say I want to build the non-deterministic machine for $\bar{A}$. I know that if $w\in A \oplus B$ and $w\in B$, then for sure $w \in \bar A$. My problem is with the condition if $w\notin A \oplus B$ and $w\notin B$ then $w \in \bar A$, because I don't know if $w\notin A \oplus B$ and $w\notin B$ since I don't know that $NP = coNP$.

So how can I show non deterministic machines for $\bar{A}$ and $\bar B$ when I don't know how to decide if "word is not in ..."?

# Answer
> 2 votes
Thanks to G. Bach and Yuval Filmus.

If every $A, B \in NP$ and $A \oplus B \in NP$, then let $E$ to be some language $E\in NP$. Since $\Sigma^\*\in NP$ then $E \oplus \Sigma^\* \in NP$. But $ E \oplus \Sigma^\* = \bar E$, so $\bar E \in NP$, and we got that $NP \subseteq coNP$.

Let $D$ to be some language $D\in coNP$ ($\bar D \in NP$). Since $\Sigma^\*\in NP$ then $\bar D \oplus \Sigma^\* \in NP$. But $ \bar D \oplus \Sigma^\* = D$, so $\bar D \in NP$, and we got that $coNP \subseteq NP$.

And then $NP = coNP$.

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


title: Reduction from ATM to ATM-complement

text:
# Question
Title: Reduction from ATM to ATM-complement
Is there a reduction from ATM to ATM-complement?

(ATM denotes the language $\\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\\}$)

I have been thinking about it too much and couldn't find the answer.

I know that reduction from ATM-complement to ATM is not possible becouse if it was, ATM would not be in RE. But how can I proove/profe the other way around?

# Answer
By the very same reason you have mentioned there cannot be such a (many-one) reduction.

Note that if you have two problems, say $A$ and $B$, and $A\le\_m B$ then also $\bar A \le\_m \bar B$. In fact the same reduction can be used for both statements. So a reduction from ATM to ATM-complement, would also be a reduction from ATM-complement to ATM. And you already know that such a thing does not exist.

If you are however ask for Turing reduction, then the answer is yes. We can ask an ATM oracle and invert the answer to get a Turing machine that decides ATM-complement.
> 4 votes

---
Tags: computability, turing-machines, reductions, semi-decidability
---