title: Static prediction of branch prediction

text:
# Question
Title: Static prediction of branch prediction
If we have a static implementation of branch prediction and we always fetch the next sequential instruction isn't inefficient to do that if we, at a future point verify if the prediction was correctly done? We just evaluate the branch in future... Why don't we just simply verify this thing every time we encounter a branch and not just execute what we think it's correct? I see here a delay because we double check the incorrect situations. 10 predictions, 4 wrong =\> 14 evaluations instead of 10. I know I'm wrong but I can't figure it why.

# Answer
> 3 votes
You are missing a fundamental detail: modern processors are pipelined. What it means in a nutshell is that instruction $I\_{n+1}$ is fetched from memory and begins being processed way before instruction $I\_n$ has been executed completely. But if $I\_n$ is a conditional branch, we have no way to *know for sure* whether or not the jump will happen: we would have to stop fetching instructions until we finish evaluating $I\_n$.

Branch prediction doesn't come from theory but from a strictly practical observation: *it is better to be sometimes wrong, but decide quickly than to be always correct but slowly*.

A classical example is the following:

```
for (i <-- 0 to 1,000,000) do {
    ...
}

```

If we just take the "loop continues" branch every time, we will be wrong once but correct the other $999,999$ times, yielding a better average running time in practice.

---
Tags: cpu
---


# Question
Title: Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes
I was reading about CRC coding from two books:

They use following notations:

* $d(x)$: dataword to be sent (as a polynomial)
* $c(x)$: codeword sent (as a polynomial)
* $e(x)$: error (as a polynomial)
* $c(x)+e(x)$: codeword sent with error introduced (if any)
* $g(x)$: generator polynomial to be used at CRC encoder (for creating c(x)) and decoder (for checking if error is introduced or not during transmission)

Forouzan then states following:

> A single-bit error is $e(x)=x^i$, where i is the position of the bit. If a single-bit error is caught, then $e(x)=x^i$ is not divisible by $g(x)$. (Note that when we say not divisible, we mean that there is a remainder.) If $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero (the rightmost bit is 1), then $e(x)$ cannot be divided by $g(x)$ and all single bits errors can be caught.

He then gives example of generator:

* $g(x)=x+1$ saying that it can catch all single bit error (with which I have some doubts)
* $g(x)=x^3$ saying that all single-bit errors in positions 1 to 3 are caught rest are left uncaught (with which I dont have any confusion).

For example, consider the below example for generator $g(x)=x+1$:

Tanenbaum says:

> If $g(x)$ contains two or more terms, $e(x)$ will never divide into $g(x)$, so all single-bit errors will be detected.

My doubts:

**Q1.** Forouzan states additional requirement to Tanenbaum that "the coefficient of $x^0$ is not zero (the rightmost bit is 1)". Whats correct? and why? Will generator $g(x)=x^3+x^2$ (which satisfies Tanenbaum's statement) capture all single bit errors? Do we always need "$+1$" in $g(x)$ for capturing any single bit error?

**Q2.** I feel I dont understand the reason/logic behind statements made by both authors, thats why I am not able to decide on myself whether "$+1$" should be there in $g(x)$ or not. Whats the logic then behind both of statements (whichever is correct)? More precisely: why $e(x)$ with single bit error will not be dividable by $g(x)$ if

> $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero

as Forouzan says or if

> $g(x)$ contains two or more terms

as Tanenbaum says (whichever is correct).

I must be missing something very very basic stuff here.

# Answer
> 1 votes
You just need to concentrate on the polynomial division here. First consider the case where we need to detect ***one - bit error*** . For this case

$ e(x) = x^k $

we can choose any polynomial with terms \>=2 , since it will not divide the error polynomial completely .

Next let us see the case of odd number of errors. Notice how this is different from one bit error. This is a burst error. Consider the polynomial

$ g(x) = (x+1) $

If we multiply this polynomial with any other polynomial the number of terms we get as a result is always even. This result in general is true you can try this for assurance.

Consider any error polynomial with odd number of errors . This polynomial will have odd number of terms in the polynomial. example :

$e(X) = x^3 + x^2 + x $

Now

$\nexists p(x) \quad such\quad that \quad p(x) * g(x) = e(x) $

In other words no polynomial could be fund which gives odd number of terms when multiplied by x+1 . This observation suggests x+1 should be a factor of our generator function in order to catch odd- number of errors. As 1 - bit error is an odd-bit error x+1 also detects one - bit errors. Both books are correct in their reasoning.

---
Tags: computer-networks, polynomials, hamming-code, crc, hamming-distance
---


# Question
Title: How to solve variable sized bin packing when the items have equal weights, or is it still NP-hard?
Consider the variable sized bin packing

$$ \begin{align\*}\tag{P1a}\label{P1a} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum\_{j=1}^nf\_jy\_j\\\\[3pt\] & \text{subject to} & & \sum\_{i=1}^{m} w\_{i}x\_{ij} \leqslant C\_{j}y\_j,\forall\\,j\in\\{1,\dots,n\\}\tag{P1b}\label{P1b}\\\\[3pt\] & & & \sum\_{j=1}^n x\_{ij}=1, \forall\\, i \in\\{1,\dots,m\\}\tag{P1c}\\\\[3pt\] & & & x\_{ij}, y\_j \in\\{0, 1\\}, \forall\\, i\in\\{1,\dots,m\\}, j\in\\{1,\dots,n\\}\tag{P1d}. \end{align\*} $$

The problem \eqref{P1a} can be found for example in variable sized bin packing problem.

The problem \eqref{P1a} can be seen as:

* We have set of bins $\\{1,\dots,n\\}$ each with a weight $f\_j$, a set of items $\\{1,\dots,m\\}$ each with a weight $w\_i$. For each bin $j$, there is a capacity $C\_{j}$.
* We would like to assign all items to the bins such that every item is assigned to exactly one bin and the weights of items assigned to bin $j$ does not exceed the capacity $C\_{j}$.

I am curious about the case where the weights of the items are all equal, say $w\_i=1$ for all $i$. Can we derive an optimal algorithm in this case or it is still NP-hard?

I can't find an NP-hardness reduction but I think that we can do this algorithm:

* sort the bins by $C\_j$ in decreasing order;
* start with bin 1, fill it with items until $C\_1$ is reached;
* go to the next bin and loop.

I have tried this algorithm with few examples but I cannot prove its optimality though.

Could you help please?

# Answer
I'll change the description to avoid artificial sums.

We have n bins $bin\_i$. Each bin has a capacity $C\_i$ and a weight $f\_i$. We have m items $item\_i$. Each item has a weight $w\_j$. We want to pick a set B of bins, and for each $bin\_i$ in B a set $I\_i$ such that the weights of all items in $I\_i$ is at most $C\_i$, and the sum of the weights $f\_i$ of the bins in B is minimised. Each item must be in exactly one of the bins $bin\_i$ in B. We assume $f\_i \> 0$ and $w\_i \> 0$.

If all $w\_i = w$ are the same, then we can divide each $C\_i$ by w and replace $w\_i$ by 1 without changing the problem. Now the number of items in $I\_i$ must be ≤ $C\_i$. Since the number of items in $I\_i$ is an integer, we can round each $C\_i$ down to the nearest integer without changing the problem.

There are m items, and each item is exactly in one bin, so the sum of the $C\_i$ for bins $bin\_i$ in B is ≥ m for a solution. On the other hand, if the sum of $C\_i$ for bins in B is ≥ m, then we can fit the m items into those bins (because the $C\_i$ are integers). So now we can completely ignore the items, and the problem is: Find a set B of bins so that the sum of $C\_i$ for bins in B is ≥ m, while the sum of $f\_i$ for those bins is minimised. If we find the set B, then putting items into the bins is trivial.

Let B' be the set of bins not in B, and let C be the sum of *all* $C\_i$. Instead of finding B, we can find B' such that the sum of $C\_i$ for bins in B' is ≤ C - m, and the sum of $f\_i$ for bins in B' is maximised. We rename "bin" to "item" and call B' a "knapsack", and voila - a knapsack problem. Very much easier to solve than the original problem if the number of bins is significantly smaller than the number of items, but still NP-complete.
> 3 votes

# Answer
I would first simplify the problem: If the $w\_i$ are equal, you can assume that all the $c\_{ij}$ are integers. It then doesn't matter item you put into every bin, just how many. So you pick $y\_i = 0$ or $y\_i = 1$, such that the sum of $C\_i y\_i ≥ n$ and the sum of $f\_i y\_i$ is minimal.

Looks very similar to the knapsack problem to me. Actually, instead of trying to find the bins that you are using, you could find the bins that you are not using, and then it is *exactly* the knapsack problem (which is NP-complete).

Your algorithm cannot be optimal because you want to minimize the sum of $f\_i y\_i$ but the algorithm doesn't even consider the $f\_i$ at all.
> 1 votes

---
Tags: algorithms, np-hard
---


# Question
Title: Can any non-halting Turing Machines with blank tape input print out any irrational number?
The fact that square root of 2, pi etc are computable numbers only means they can be approximated to arbitrary nth decimal, so these TM that approximate them do not count since they halt after printing out the nth digits. I would appreciate a definitive answer and reasoning. If the answer is NO, which I suspect, is the following statement equivalent? Any TM with blank tape input can only print rational numbers, assuming its alphabets are coded in integers.

# Answer
I choose to represent numbers in base $\pi$. My machine prints $10$ and terminates, that's exactly $\pi$.

A Turing machine performs meaningless operations on meaningless objects, *you* provide the semantics, *you* find meaning in the computation. The answer to your question is a direct consequence of how you decide to represent numbers with the finite alphabet of the machine. It is certainly true that not all real numbers can be exactly computed under an unified semantics by Turing machines: there are uncountably many real numbers but countably many Turing machines.

But you might be able to represent some of them. For instance, with enough symbols to write integers, fractions, square roots and the imaginary unit, you can represent exactly the segments constructible with straightedge and compass, each of them in a finite amount of space.
> 1 votes

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


title: Term for number of edges in a graph

text:
# Question
Title: Term for number of edges in a graph
Is there a single-word term for "the number of edges in a graph"? Something along the lines of "arity" for function parameters.

# Answer
I'd probably call this the "Edge-cardinality" of the graph, and it's denoted $|E|$, where your graph $G = (V,E)$. Similarly, the "vertex-cardinality" is the number of vertices, denoted $|V|$, though $|G|$ is sometimes also used to denote $|V|$.

The edge count isn't always considered that important, because you (almost) always have at least $|V|$ edges, and you can't have more than $|V|(|V|-1)$ edges in a digraph. So for issues of complexity, the node count tends to matter more.
> 2 votes

# Answer
I don't believe there is a single word term for this. *Edge count* seems to be the closest thing to what you are after. Mathematically it can be expressed as **E(g)**.

http://mathworld.wolfram.com/EdgeCount.html
> 2 votes

---
Tags: graphs
---


# Question
Title: Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?
For example:

S -\> Sa

Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free grammar, but not a regular one ?

As far as I can think... a grammar tree built on it will never end, it will never have only leaves so there is NO string that is accepted or generated by this grammar so it should not be considered a valid grammar.

However I did not see in the definition of grammar this specific constraint of a grammar, that it necessarily should have a production rule with ONLY terminal symbols on the right hand side of a production rule.

# Answer
> 1 votes
Back to the definition. According to Wikipedia, a context-free grammar $G$ is a 4-tuple $(V, \Sigma, R, S)$. In this case, $G = (V, \Sigma, R, S)$ can be defined as

* $V$, nonterminals, is $\\{S\\}$,
* $\Sigma$, terminals, is $\\{a\\}$,
* $R$, production rules, is $\\{ S \mapsto Sa \\}$, and
* $S$ is the start symbol and an element of $V$.

So this is a context-free grammar although the language recognized by $G$ is empty as you noticed.

You can also verify whether this is a regular CFG by going back to the definition.

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


# Question
Title: Bellman-Ford: Find all nodes that have minus infinite distance to source
Given a weighted, directed graph (V, E) may contains some negative cycles and a source node `s`, I would like to know for all node `u`, if there is a path from `s` to `u` but there is no shortest path from `s` to `u` (the distance from `s` to `u` is minus infinite). To do this I implemented a version of the Bellman-Ford algorithm:

```
Do V iterations of Bellman-Ford, save all nodes relaxed on Vth iteration to a queue `Q`
Do BFS with `Q` and find all nodes reachable from `Q`
All those nodes and only those can have infinite distance from `s`

```

Here is BFS:

```
visited(Q.first) = true
while Q not empty:
    u <- Q.deQueue()
    shortest[u] = 0 // there is no shortest path from `s` to `u`
    for all (u, v) in E:
        if not visited(v):
            visited(v) = true
            Q.push(v)

```

This algorithm is the best I can come up with and sadly it fails some test cases. I would be greatly appreciated if you guys can help, thanks.

# Answer
Well after a morning of testing, I just figured out that my solution is RIGHT, the problem I had before is because of overflow (I use `10^19` to declare `infinity` for all vertices at the beginning and it can leads to overflow for some test cases).
> 0 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Is function with finite amount of $\Phi_x(x+1)$ occurrences Turing computable?
I'm studying for my exam from Logic and Computability and we have to face following kind of examples:

$$f(x) = \begin{cases} \ 1 &\text{if }\Phi\_x(x+1)\\!\downarrow\text{ and }x\leq50\\ \ 0 &\text{otherwise.} \end{cases}$$

Unfortunatelly I'm not really clear on how to tackle those. $\Phi\_x$ is the $x$-th computable function, thus it's also Turing computable. This implies, there exists a TM (we have $N$ of them) which halts and returns the output.

The task is to determine whether it's computable. In order to prove it we either provide an informal algorithm to show it's computable or a formal proof that it's not. Can any of you solve this example?

If $f(x)$ is computable, then $\Phi\_x$ needs to halt for every $x \in\\{1, \dots, 51\\}$. However $\Phi\_x$ could be undefined on one of the elements from $\\{1, \dots, 51\\}$ and keep looping forever.

At the other hand, there is an upper bound on $x$, which indicates its computability.

Please, can you show me the right direction?

Thanks!

# Answer
> 1 votes
You can compute this function using a table of size 51. More generally, if $f$ is a function which differs from a computable function $g$ on a finite number of inputs, then $f$ is computable as well. In our case, $g$ is the constant zero function, which is trivially computable.

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


# Question
Title: Pre-requisite knowledge before diving into algorithms
I'm having some difficulty trying to follow what the authors of some of the more highly recommended books on algorithms. I ran into the same problem when trying out some online courses. My goal is to prepare myself to start learning fundamental algorithms for use in low-level languages by means of understanding them mathematically. So far, a guide on wiki is a good resource to decipher the symbols, but I'm not sure that will suffice.

Is there anything besides this page that a person would need before learning algorithms besides basic algebra concepts?

# Answer
> 2 votes
To learn algorithms mathematically you will need to have a basic understanding of

* Proofs(basically using induction)
* summations and
* asymptotic notations(like Big-O , Big-Omega)

To learn the above subjects I recommend this course from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/

---
Tags: algorithms, education, mathematical-foundations
---


# Question
Title: Showing a problem on a specific graph is NP-hard
Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.

My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?

# Answer
There's no such thing as a hard instance. You can always figure out the answer to that one instance and then hard-code that into an algorithm. For example, you can always have an algorithm for SAT that says

```
if input="(XvY)^(!Xv!YvZ)"
    return SATISFIABLE
else
    [loop through all possible variable assignments]

```

Incidentally, this is why nobody looks at "best-case complexity", since any algorithm can be adapted to run in best-case constant time in this way. (Constant because you only have to read a fixed amount of the input to see if it's one of the ones that you have a hard-coded answer for.)

There's a category error in asking if an instance can be **NP**-complete. Recall the definition of what **NP**-completeness is:

> A language $L$ is **NP**-complete if is in **NP** and every other language in **NP** is polynomial-time many–one reducible to $L$.

First, that statement doesn't "type-check" if you try to make $L$ be a string rather than a language. Second, the definition of many–one reductions requires that you have at least one "yes" instance and at least one "no" instance to use as targets for the reduction. One instance isn't enough to make these definitions work.
> 7 votes

# Answer
A problem cannot be NP-hard for a particular graph (unless P=NP). This is because for every particular instance, there is a zero-time algorithm that solves the problem on that instance perfectly. The concept of NP-hardness only makes sense for an infinite family of instances.

In fact, much more is true. Even an uncomputable problem is computable on any given instance. Both computability and complexity are notions that only make sense in the number of instances is infinite.

We can say even more. Suppose that some problem is, indeed, NP-hard. For every particular instance we can find a constant time algorithm that solves the problem on that instance in constant time. This is because we can hardwire the solution for that particular instance.
> 3 votes

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


# Question
Title: To which character or characters does a Kleene star apply?
If you have a Kleene star applying to a set of characters not in any closure, does it apply to that whole string, or just the one character it belongs to? Any examples I search don't specify.

For example:

(A)BB\*

Does this mean 1: one A followed by zero to an infinite number of BB's, or does it mean 2: one A followed by at least one B and zero to infinite number of B's?

# Answer
Kleene stars applies to the character(s) it belongs, so in your example the correct option is the 2° one.

ABB\* = {AB, ABB, ABBB, ABBBB, ..}

A(BB)\* = {A, ABB, ABBBB, ABBBBBB, ..}
> 2 votes

# Answer
Conventionally, the Kleene star applies only to the character immediately before it, so $ABB^\*$ is $AB$ followed by some number of $B$s. Parentheses are used to make it apply to a sequence of characters; e.g., $A(BB)^\*$ is $A$ followed by some number of pairs of $B$s.
> 1 votes

---
Tags: regular-expressions, kleene-star
---


title: Max flow not min cut?

text:
# Question
Title: Max flow not min cut?
I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking something simple, but I've been staring at this for 10 minutes now... Can anyone explain what Im missing?

# Answer
The edge from $2$ to $3$ isn't part of the minimum cut. It's oriented in the wrong direction, from the sink side to the source side, so you can delete it from your cut and there's still no path from $s$ to $t$.
> 1 votes

---
Tags: network-flow, minimum-cuts
---


title: Branch wrong prediction pipeline

text:
# Question
Title: Branch wrong prediction pipeline
Let's say we have a pipeline with 20 stages. If the testing for the jump condition is done at stage 14 and we have a wrong prediction, then the instructions processed in those 14 stages, that shouldn't have been processed due to the wrong prediction made the processor lose 14 cycles. We know that the jump instruction entered the pipeline 14 stages back, therefore from this behaviour I deduced that 14 cycles were lost. Am I correct? If no, why?

# Answer
It's not correct. The instruction that would determine the result of the condition is read at cycle x. The conditional branch is read at cycle x + k. k can be any value, depending on the code. For example I can have a comparison "compare x and 0", then half a dozen unrelated instructions, then an instruction "branch if the comparison result is 'greater'". You are saying the correct condition is determined at cycle x + 14. You lose 14 - k cycles.

You may find out 14 cycles later that the branch was predicted wrongly, or 8 cycles later, or in the next cycle. What is lost is the cycles between branch prediction and the point where the correct way became known, which is variable. In this situation, compilers will often try to issue the comparison as early as possible before the branch instruction, to minimise the penalty for an incorrect branch.

To clarify: If a compare instruction is read at cycle x, and the result of the comparison is available at cycle x+14, and a conditional branch instruction is read at cycle x + k, then it doesn't matter at which stage in the pipeline the incorrect branch is detected. What matters is the time from the start of the conditional branch, to the time of detection of the incorrect branch, and that time is variable. If the compare instruction is issued early enough then the branch isn't even predicted because the result of the compare instruction is known.
> 2 votes

---
Tags: cpu, cpu-pipelines
---


# Question
Title: How to calculate time complexity of this problem?
The problem statement: **Append the length of the string to the string while the length is less than or equal to 10**

Input: "a" -\> Output: "a12345678910"

Input: "abcde" -\> Output: "abcde5678910"

The solution of the problem would require lesser time for a larger input. What should be the time complexity of this?

# Answer
Given any reasonable computational model, we can provide an algorithm to solve your problem that reads the input (stopping at $10$ symbols should it be longer), stores the length, and while such length is less than $10$, appends the needed symbols and updates the total length.

This algorithm performs a constant amount of work at most $10$ times, which means that there exists a constant $c$ that bounds the running time for any size of input. By definition, such an algorithm has complexity $\Theta(1)$.

Observe that if you require the output to be a copy of the input for strings longer than $10$, then, depending on your computational model, you might need to physically copy the string, which takes time $\Theta(n)$.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: How can Karger's algorithm (and other randomized algorithms) be used in practice?
Suppose I am given the following problem (the source is here):

> Disconnect two nodes in a graph by removing minimum number of edges.

I would apply Karger's min-cut algorithm. But how can I guarantee that I'll finally find the min-cut? Karger's algorithm is a *randomized* algorithm. If the probability of success is *1/p*, I could run it *p* times to get the answer, right? Not necessarily! What if I am extremely unlucky, so I will never (or too much time will pass) get the answer?

# Answer
Karger's algorithm is a randomized algorithm. It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.

If we do one round of the algorithm, it has a probability of success of $p$. If you repeat it $100/p$ times and take the best cut found in any of those iterations, then the probability of success is incredibly high: the algorithm fails only if all $100/p$ iterations fail, so the probability of failure is

$$(1-p)^{100/p} \approx e^{-100} \< 2^{-128},$$

and the probability of success is larger than $1 - 2^{-128}$. For Karger's algorithm, $p=1/{n \choose 2}$, so we repeat it $100 {n \choose 2}$ times, and we obtain a probability of success that is larger than $1 - 2^{-128}$.

For all engineering purposes this is equivalent to a guarantee of success. For instance, the probability that a cosmic ray hits your computer and causes a bitflip error that causes the algorithm to produce the wrong result is far higher than $2^{-128}$, but we're apparently willing to accept that -- so we should be glad to accept Karger's algorithm too, as long as we repeat it enough times.

See the Wikipedia article for more explanation: https://en.wikipedia.org/wiki/Karger%27s\_algorithm
> 7 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Calculate how much segements the system can handle
I am a bit lost calculating how much segments will the system handle in a memory segmented system (without virtual memory). The problem says that the system has a word length of 32 bits and the address are 6 hexadecimal numbers, 3 of them are the segment identifier. We have a segment size of 4KiB

I tought this:

If the address are of 24 bits wide, we could address $2^{24}$ bytes of data and our segment size is $2^{12}$ bytes. So divide them and we have the maximum number of segments our system can handle.

But I was told this isn't the way to solve this problem. Here is the way it's supposedly correct:

We have $2^{24}$ address in our system, with a length of 32 bits so we have $2 ^ {29}$ bits of addressable memory, $2 ^{16}$ KiB of addressable memory. So dividing between our segment size we have $2^{14}$ segments.

But I don't find this answer correct, because if it says that the 3 hex digits identifies the segment we have 12 bits to identify every segment, with a maximum of $2^{12}$ segments, so I don't know how the second solution manage to add 4 times more segments than my solution.

So what answer is correct?

Thanks

# Answer
> 0 votes
I think neither of those is a good solution, but yours is better than the one you were given.

Here's how I'd reason through it: there are 3 hex digits to represent the segment identifier. That's 12 bits for the segment identifier. 12 bits can identify up to $2^{12}$ possibilities. So the system can have at most $2^{12}$ possible segments. The rest of the information is irrelevant.

---
Tags: memory-management
---


title: Convert DFA to Regular Expression

text:
# Question
Title: Convert DFA to Regular Expression
In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q\_2$ state is eliminated first. The provided solution to eliminate $q\_2$ is:

If we first eliminate $q\_2$ we obtain an intermediate automata with $3$ states $(q\_0$,$q\_1,q\_3)$ such that:

> 1. We go from $q\_0$ to $q\_1$ with RE $a+ba$
> 2. We go from $q\_0$ to $q\_3$ with RE $bb$
> 3. We go from $q\_1$ to $q\_1$ with RE $ba$
> 4. We go from $q\_1$ to $q\_3$ with RE $a+bb$

I don't understand nr2. $q\_3$ can also be reached using RE $aa$. Why is this left out?

:

:

# Answer
The conversion in each step forms REs that describe

* The previous direct edge from one state to another and
* the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q\_1$, which is not removed in this step. Thus it is not added to the RE.
> 8 votes

# Answer
The RE "aa" is not left out. First "a" in transaction between $q\_0$ and $q\_1$, second "a" between q1 and q3. Since this pair of transitions doesn't involve $q\_2$ we don't consider it in the first stage of the algorithm, where we're eliminating $q\_2$.
> 2 votes

# Answer
it is not left out , see q3 cn still be reachable using "aa" from intial state q1 , just **tk 2nd term from unioned terms** and then pick **'a'** from **(a+ba)** , tk **(ba)\*** as **NULL String** and then take **2nd 'a'** from **(a+bb)** : so by concatenation we got "aa" and we reached final state q3
> -2 votes

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


# Question
Title: Direct encoding of the solution into the chromosomes in a Random-Key Genetic Algorithm
In a random key genetic algorithm, the chromosomes consist in a sequence of real numbers (initially randomly generated) in the interval $\[0,1\]$.

I've been told by my teacher that in these kinds of genetic algorithms, one cannot encode the solution directly into the chromosomes, as that would generate "infinitely large" convergence times. Instead, the proposed solution from my teacher is to use the weights in the chromosomes to modullate the construction of a solution through a greedy algorithm. Let me clarify that further with the classical example of the Travelling Salesman Problem:

In a direct encoding (my proposal), with $N=4$ cities, a chromosome with values $\[0.1, 0.7, 0.4, 0.9\]$ could be decoded in order to determine the order in which to visit the cities, which would become $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$.

The other approach consists in constructing a solution by means of a regular greedy algorithm. For example, starting from the initial location, a simple greedy algorithm for the TSP would select, at each iteration, the closest city for its next step. In order to fit the chromosomes in this schema, when considering going to the next city, one would multiply the distance to the considered location by the value of the allele for that city, essentially changing the values of the greedy function with the chromosome's genes.

So my question would be:

* Is this kind of "modullating a greedy" chromosome encoding widespread in the literature? I couldn't find any examples. I find it surprising that it works well, because when using a greedy there's no way to explore the whole solution space, and the variations in the chromosomes arising from crossover are probably going to end up generating the same greedy solutions all the time.
* Is the first kind of encoding (the direct one) something unacceptable for a random-key genetic algorithm? Would something similar be unacceptable as well for a regular (as in, more generic) genetic algorithm?

# Answer
As said elsewhere. Genetic algorithms are more art than science. The encoding and evaluating of chromosomes can be anything you like. The only "unacceptable" techniques are the ones that don't work.
> 2 votes

---
Tags: optimization, genetic-algorithms
---


# Question
Title: What's the purpose of Karger's algorithm?
Suppose I'm given an undirected graph and two nodes: ***v*** and ***u***.

If I understand Karger's algorithm correctly, it's used to find a minimum cut of a graph, not the ("the" because there is only one for any given graph) minimum cut such that ***v*** is in one part of graph and ***u*** is in the other part.

Why don't we simply find the vertex with the minimum number of edges and remove those edges. Thus, we "partition" the graph into two subgraphs: the node which had the minimum number of edges and the rest of the original graph. What am I missing?

# Answer
Even in an unweighted graph, your suggested algorithm doesn't work: take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d. Vertices a, b, e, and f each have minimal degrees of 2, but cutting the graph between the two triangles gives a cut of 1.
> 5 votes

---
Tags: algorithms, graphs, partitions
---


# Question
Title: Is the union between a regular language and a random language also a regular language?
If not can we draw any conclusion about the newly fromed language, the language that represents the union between a regular language and a non regular language (not context free but a truly random language ).

# Answer
> 7 votes
The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?

# Answer
> 4 votes
Suppose L1 = a\* (regular language) and L2=anbn, where n is a natural number (L2 is not regular).

L = L1 U L2 = {ε, a, aa, aaa, ..., ab, aabb, aaabbb, ... } but there is no DFA able to recognize words in the form anbn, so L is not regular.

---
Tags: formal-languages, context-free, regular-languages, closure-properties
---


title: Boolean Algebra: Operation Linkage Laws

text:
# Question
Title: Boolean Algebra: Operation Linkage Laws
Im studying some properties of Boolean Algebra and found the Operation Linkage Laws.

Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can any one show me the proofs of this laws or share any resources where I can find a more detailed proof of the laws?

# Answer
> 2 votes
The proposition states that if any of the four statements holds, then the other three also holds. This gives in total 12 different theorems. For the proof, you can use truth tables or the axioms of Boolean algebra.

What the comment is trying to explain is that, say, $xy=x$ isn't universally true (consider $x=0,y=1$). However, if $xy=x$ then also $x+y=y$, and vice versa. This is in contrast to identities such as $x+x=x$, which always hold (for all values of $x$).

---
Tags: boolean-algebra
---


# Question
Title: Question about handwritten numbers recognition with limited data set
I have a an assignment to make a classifier for hand-written numbers with a limited data set of 500 samples. I am currently using python, I tried sklearn SVC with linear classifier and I got an accuracy of about 80%. I also tried KNN with 13 neighbors and got a max of 81% accuracy. I need to get to at least 90% accuracy. What are your suggestions that would help with training (adding noise? what distribution? / tilting the pictures with 90 degrees? Maybe cross validating over different parameters... etc).

Edit: To clarify the main challenge: I have to reach an accuracy of more that 90% with only using 500 samples, I can play around with the samples however I want to extend the data but I am not allowed to use external samples.

# Answer
> 1 votes
I suggest you the following:

1. Adding a little bit of noise such as blurring
2. Transforming the images. You can rotate or stretch a bit, but make sure you don't change too much to change 6 to 9 or o to 0.

You can look at the following tutorials:

---
Tags: machine-learning, classification
---


# Question
Title: Is potential causality relation equals to set of consistent happens before relations?
In a book dedicated to distributed algorithms, I found the following definition - potential causality diagram is consistent with happens before diagram if potential causality relation between system events is a subset of happens-before relation. So far so good.

But then I have read following claim potential causality diagram equals to the set of happens before diagram to which it consistent with. But how that is possible? I mean that cardinality of potential causality relation is less than the cardinality of happens before relation to which it consistent with. How may potential causality relation be composed of union of such happens-before relations? I agree that potential causality relation may be composed of a set of happens-before relations, but from my point of view happens before relations in such case should be subsets of potential causality relations? Could you explain what I missed?

Update: Quotation from the book. "Given a potential causality diagram $(E, \xrightarrow{p})$, a happened before diagram $(E, \rightarrow)$ is consistent with it if $\xrightarrow{p}\subset \rightarrow$.

is consistent with

Observe that $e\_2 -\>f\_4$ but $\neg(e\_2 \xrightarrow{p} f\_4)$. A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it.

Vijay K. Garg. Elements of Distributed Computing (Kindle Locations 301-302). Kindle Edition.

# Answer
The book says "A potential causality diagram is *equivalent to the set* of happened before diagrams that are consistent with it." (emphasis added)

You seem to have interpreted that as "A potential causality diagram is *equal to the union* of happened before diagrams that are consistent with it." But that's not the same statement. I would suspect that this might be the cause of your confusion. Go back to the original statement and disregard the idea of taking the union, and see if you can make sense of the original statement.

Perhaps there is additional explanation or context after that sentence.

If not, perhaps the book is claiming there is a bijection between (a causality diagram C) and (the set of happens-before relations that are consistent with C). That claim sounds accurate. To construct the inverse map: given such a set of happens-before relations, take the smallest element in the set, and that's C.
> 0 votes

---
Tags: algorithms, distributed-systems, clocks
---


# Question
Title: Connecting The Informal and Formal Definitions of Decidable With Each Other
From pg. 64 of *Lambda Calculus and Combinators*, the author formally and informally defines the notion of "decidability":

### 1 Formal Definition

> **Definition 5.4** A pair of sets $\mathcal{A}$, $\mathcal{B}$ of natural numbers is called *recursively separable* iff there is a recursive total function $\phi$ whose only output-values are $0$ and $1$, such that
>
> $$ n \in \mathcal{A} \implies \phi(n) = 0, $$ $$ n \in \mathcal{B} \implies \phi(n) = 1 $$
>
> A pair of *sets of terms* is called *recursively separable* iff the corresponding sets of Godel numbers are recursively separable. A set $\mathcal{A}$ (of numbers or terms) is called *recursive* or *decidable* iff $\mathcal{A}$ and its complement are recursively separable.

### 2 Informal Definition

Shortly thereafter, the author states

> Informally speaking, a pair $\mathcal{A}$, $\mathcal{B}$ is recursively separable iff $\mathcal{A} \cap \mathcal{B}$ is empty and there is an algorithm which decides whether a number or term is in $\mathcal{A}$ or in $\mathcal{B}$.

### 3 How to Connect These Definitions

Why is the existence of a recursive total function $\phi$ satisfying the properties of (1) logically equivalent to the notion that "there is an algorithm which decides whether a number or term is in the disjoint $\mathcal{A}$ or $\mathcal{B}$"?

# Answer
> 2 votes
The author himself wrote *informally speaking*, the second is not a definition in the same sense of the first.

Intuitively, since a recursive function is defined by either $\mu$-recursion or composition of simpler functions, the existence of a total recursive function provides an effective method to compute the answer.

The informal part of the above reasoning is that we didn't really define what we mean by "effective method".

The usual formalization involves the definition of a *computational model*, which provides a rigorous framework for the notion of algorithm. Once you have done that, you can prove the equivalence in a mathematical sense.

---
Tags: logic, undecidability, lambda-calculus
---


title: Motion Prediction Problem

text:
# Question
Title: Motion Prediction Problem
**Setup:** Suppose you have a dog running around in a fenced yard (2D). Every *x* seconds, you mark down the coordinates of the dog. This dog is a puppy - easily distracted, full of energy, and very speedy :) Expect quick, jagged motions, running in circles, and periods where he needs to catch his breath :)

**Problem**: At any point, you would like to predict where the dog is going to be *kx* seconds into the future (k being an integer).

I would like to know what types of techniques may be most suitable for solving this? My knowledge breadth in this subject matter is very limited. I'd like to identify a few candidates that I could then deep-dive into

* My original thought was to use Langrange-form polynomials to interpolate the latest *n* points, then extrapolate. The dog's path is continuous, and smooth, so a polynomial approximation seems reasonable; however, the danger lies in forcing the polynomial through the available data. It seems like we want *the polynomial that best approximates the data*, rather then the lowest degree polynomial that exactly fits the available data - especially if *x* is substantial.
* Ideally, since every prediction can be measured against what actually occurred, there should be some method of learning on-the-fly. However, since the data isn't static, I don't know how I would apply techniques of somewhat aware of like SVMs or linear regression.

I apologize if I didn't use terms correctly, this is not my area of expertise.

# Answer
I would try to train a Recurrent Neural Network for this problem, the LSTM architecture is particularly interesting for time series prediction.

Sources:

* karpathy.github.io/2015/05/21/rnn-effectiveness/
* colah.github.io/posts/2015-08-Understanding-LSTMs/

You would of course need a training dataset consisting of a sequence of events. Let's say $x$ and $y$ coordinates for every timestamp $t$, (possibly $z$ as well to predict a jumping puppy).

Both the network input layer and the output layer would consist of 2 units. Then you would train your model to predict $(x\_{t+1}, y\_{t+1})$ given $(x\_{t}, y\_{t})$. Once the network is trained, you can predict the position of the dog at any point in the future.

Let $M$ be our trained model and let's say you want to predict the position of the dog at time $k$ and you know the current position of the dog at time $t$.

$M(x\_{t}, y\_{t}) = (x\_{t+1}, y\_{t+1})$

$t = t+1$

$M(x\_{t}, y\_{t}) = (x\_{t+1}, y\_{t+1})$

$...$ increment $t$ and keep predicting until $t+1 = k-1$

$M(x\_{t+1}, y\_{t+1}) = (x\_{k}, y\_{k})$

Put in pictures this corresponds to:  (picture from Udacity lecture about Deep Learning)
> 4 votes

# Answer
As someone who works on tracking and predicting algorithms for missiles to track targets, this type of problem is commonly tackled using things such as Kalman Filters. Typically for a tracking problem, one would assume dynamics of the object you want to track similar to the following:

\begin{align} \dot{p}\_{x} &= v\_{x} \\ \dot{p}\_{y} &= v\_{y} \\ \dot{v}\_{x} &= \eta\_{x} \\ \dot{v}\_{y} &= \eta\_{y} \\ \end{align}

where $p\_{x}$ is the $x$ position, $p\_{y}$ is the $y$ position, $v\_{x}$ is the $x$ velocity component, $v\_{y}$ is the $y$ velocity component and $\eta\_i \forall i$ are random variables from a zero mean Gaussian distributions with some variance you may or may not know.

The goal of the Kalman Filter is to use Bayesian estimation to estimate the state variables, which include the position and velocity in this case. Once you have estimates of these states, you can use them to predict where targets will be in the future using closed form solutions to the differential equations.

The nice thing about Bayesian filters, like the Kalman Filter, is they continually refine their estimates as they get more data (assuming you have covariances and other terms tuned appropriately), work for an online stream of measurements, and are fairly efficient.

Also, it is feasible to include acceleration terms you wish to estimate instead of using random noise variables. The problem of tracking an accelerating object, whether a dog or something else, can be a challenge due to compiled noise from sensors and whatnot. But it is still a feasible thing to tackle.
> 2 votes

# Answer
My guess is that nothing is going to work, but the only way to know is to try it on some real data.

As a first cut, I imagine that periodically the dog makes a random change to its running, in such a way that past history before that change won't help you predict its movement afterwards. For instance, the dog might change direction, or suddenly stop to rest, or suddenly take off, or notice his tail and start chasing it, or whatever. A critical parameter will be how often this happens.

Suppose it happens on average about every $y$ seconds. Then one plausible approach is: using the last $y/x$ data points, try to fit multiple models to the data, and see which provides the best fit. One model might be a straight line (the dog running in a straight line, or sitting still for a rest), another model might be a circle (the dog running around in circles), another model might be a low-degree polynomial or spline (the dog running in a curved path). See which model provides the best fit to those data points, and use that to predict the next data points. This requires that $y/x$ be larger than the number of "degrees of freedom" of each model, to avoid overfitting.

But overall, my expectation is that probably you aren't going to get very good results.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Finding path that minimizes largest of the sum of weights of each group in a directed multigraph
Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group? All weights are non-negative integers in the range 0..30,000.

Let me put an example for $n=2$ groups to understand it better:

If we were to find the shortest path from s to t of this multigraph, that would be easy. Just run a Floyd-Warshall algorithm and in case there is more than 1 edge for a pair of vertices, get the one with lowest weight. The shortest path in this case would be getting all the red edges (s-1-2-t)

This would give us 2 groups with following weights:

* Blue: 0
* Red: 5+5+5 = 15

So the largest of this groups is max(0,15) = **15**

---

But in this problem, we want to minimize the largest of the sum of weights of the two groups, so the path that minimizes this in this example is s-1-2-t (red-red-blue).

This would give us 2 groups with following weights:

* Blue: 10
* Red: 5+5 = 10

So the largest of this groups is max(10,10) = **10**

---

I guess this problem is NP-hard, because the partition problem can be reduced to this problem. Given an instance of partition, i.e., a multiset $S$ with $k$ elements, just build a graph with $k+1$ vertices and two edges between each pair of consecutive vertices (both edges having weight equal to the corresponding element of $S$; one red, and one blue). Or, you can reduce $n$-way multi-way partition to this problem. Again, build a graph with $k+1$ vertices, and between each pair of consecutive vertices add $n$ edges (one for each group in the partition problem) with weights equal to the numbers in the multiset. Here is a diagram that tries to explain this reduction:

But just like there is an easy greedy approximation for the partition problem, there might be something *simple* for this problem aswell. To be honest, I don't even know how to approach this problem. Any ideas?

And even though it would be great to have a general case approximation, an approximation for the case where n=2 groups would be enough for me right now.

# Answer
> 2 votes
At least for the case $k=2$, there is an efficient algorithm to solve your problem. Suppose all weights are integers in the range $0..\alpha$. Then there is an algorithm whose running time is $O(\alpha VE \log^2(\alpha V))$. In your case, $\alpha=30,000$.

How does this algorithm work? I'll show that, when $k=2$ and when the solution is known to be at most $\beta$, there is an algorithm with running time $O(\beta E \log (\beta V) \log \beta)$. It's easy to see that we must have $\beta \le \alpha V$, so this will imply the claimed result (using the fact that $\log(\alpha V^2) \le 2 \log(\alpha V) = O(\log (\alpha V))$.

The algorithm works by reducing to the decision version of the problem. Given an instance of the problem and a proposed $\gamma$, we test whether there exists a solution that is at most $\gamma$ (i.e., a path from $s$ to $t$ using red edges that total at most $\gamma$ and blue edges that total at most $\gamma$). Then we do binary search on $\gamma$. This will require $O(\log \beta)$ solutions of the decision problem, so it suffices to solve the decision problem in $O(\beta E \log (\beta V))$ time.

How do we do that? We make $\gamma+1$ copies of each vertex $v$; call these copies $(v,0)$, $(v,1)$, ..., $(v,\gamma)$. Intuitively, the new vertex $(v,i)$ corresponds to a state that can be reached if you can reach vertex $v$ from the starting point along a path where the sum of the blue edges is at most $i$. Now we'll construct a new graph on these $(\gamma+1)V$ vertices as follows. For each blue edge $u \to v$ with weight $w$ in the original graph, we add edges $(u,i) \to (v,i+w)$ for each $i$. For each red edge $u \to v$ in the original graph, we add edges $(u,i) \to (v,i)$ for each $i$.

Once this larger graph is constructed, we check whether there exists a path from $(s,0)$ to any $(t,i)$ with length at most $\gamma$. This can be done using Dijkstra's algorithm. Since the larger graph has $O(\gamma V)$ vertices and $O(\gamma E)$ edges, the running time of Dijkstra's algorithm in this graph will be $O(\gamma E \log (\gamma V))$. Since $\gamma \le \beta$, the claimed result follows.

This doesn't contradict your NP-hardness result, as your NP-hardness result uses very large integer weights, while the running time of this algorithm is proportional to the weights themselves (rather than to the number of bits needed to represent the weights). Or, to put it another way, this algorithm is a pseudopolynomial time algorithm, but not a fully polynomial time algorithm.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: How to represent text for a program to add punctuation to a block of text?
I want to try and make a program where I remove the punctuation from a block of text and it then inputs it in the correct places. I have started with a simpler element of just using text and spaces, no commas, full stops etc. The first angle I have been taking this is with machine learning, neural networks and simpler word count probabilities. However the thing I am struggling with is the representation of the block of text. At the moment I give it a block of text and it reads say 20 letters then breaks it into test based on where it thinks a word is. This is ineffective though because it may just cut off half a word at the start/end of the block. Just wondering if anyone had an idea of a way to use the block of text in this way in a better way to do this task! Many thanks

# Answer
> 2 votes
I am making two assumptions here about things that, to me, are not quite clear from your question

* When you say you removed punctuation, you actually meant whitespaces as well.
* You tried neural networks, but not in a sequence-to-sequence fashion.

What's nice about your problem is that you can generate training data as much as you want just by taking a proper piece of text and removing all the punctuation.

This being said, I suggest you engage your problem as a machine translation task where you want to predict the proper text given the one without punctuation.

Today, the best way to do this is by sequence-to-sequence learning with deep neural network (just pick a few machine translation papers from last ACL (= Annual Meeting of the Association for Computational Linguistics) conference to learn more about that.

Concerning you actual question, how to represent the input, I'm not quite sure if you have to limit the size of your input beforehand or not. In any way, you could choose the size of your input window so that any block of text that you possibly want to put in would fit (if you know beforehand how long your paragraphs will be). Or it might be that you can just cut your input sequence at an arbitrary letter and your model will learn to make sense of it anyway (I am not an expert in neural machine translation).

So, as you can see, my answer is maybe not completely on the spot but I hope it is helpful to you anyway.

# Answer
> 1 votes
Before each space, you have a decision to make: do you add some punctuation or not? And if yes, what kind of punctuation? (comma? period? semicolon?)

I suggest you treat *that* decision as the machine learning task. Build one boolean classifier per type of punctuation. Classifier #1 answers: "should I insert a comma before this space?" Classifier #2 answers: "should I insert a period before this space?" etc.

Next, choose some features that you think might be helpful in making this prediction/decision. Here are some candidates to get you started and get you thinking:

* Is the next letter after the space capitalized or not?
* Is the previous word before the space capitalized or not?
* Is the previous word before the space an abbreviation of a title? (Mr, Mrs, Dr, etc.; you can pretty easily build a small list/dictionary of such words)
* Is the next word after the space part of a proper noun? (a part-of-speech tagger might be useful here; see also entity resolution)
* Is the next word after the space one of the set of words that are always capitalized no matter where they appear in the sentence? (`grep '^[A-Z]' /usr/share/dict/words` will get you a list/dictionary of candidate such words; this is a boolean feature that tests whether the next word is in that list or not)
* What is the next word after the space? (word vector via some word embedding)
* What was the previous word before the space? (word vector)
* If you ran a NLP part-of-speech tagger and grammar parser on the part of the sentence up to this point, does it appear to be a complete sentence? (this gives a hint whether, if we were to put a period here, everything up to this point would be a complete sentence)

As you can see, I am suggesting you use a richer feature set, and one crafted for your particular task, rather than just using the previous 20 letters as the input -- and I am suggesting you use the spaces to help you identify potential insertion points, rather than potentially trying to insert punctuation between every pair of characters.

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: Comparison Procedure in Robinson's Unification Algorithm
I'm studying the Principal Type (PT) Algorithm in Basic Simple Type Theory by J. Roger Hindley. One step to find the PT of a term is the Unification of types. The Robinson's Unification Algorithm uses a comparison procedure like as follow:

Comparison Procedure

Given a pair $(u, v)$ of types, write $u$ and $v$ as symbol-strings, say

$u \equiv s\_1 ... s\_m$ and $v \equiv t\_1 ... t\_n$ $(m, n \>1)$

where each o f $s\_1,... , s\_m$, $t\_1, ... , t\_n$ is an occurrence of a parenthesis, arrow or variable.

If $u \equiv v$, state that $u \equiv v$ and stop.

If $u \not \equiv v$, choose the least $p \< \min(m, n)$ such that $s\_p \not \equiv t\_p$; it is not hard to show that one of $s\_p$, $t\_p$, must be a variable and the other must be a left parenthesis or a different variable. Further, $s\_p$ can be shown to be the leftmost symbol of a unique subtype $u^\*$ of $u$. (If $s\_p$ is a variable, $u^\* \equiv s\_p$.) Similarly $t\_p$ is the leftmost symbol of a unique subtype $v^\*$ of $v$. Choose one of $u^\*, v^\*$ that is a variable and call it $a$. (If both are variables, choose the one that is first in the sequence given in Definition 2A1.) Then call the remaining member of $(u^\*, v^\*)$ $\alpha$; the pair $(a, \alpha)$ is called the disagreement pair for $(u, v)$.

My issue is with the Note bellow:

3D5.1 Note To prove that $p$ exists in the case that $u \not \equiv v$ in the comparison procedure we must show that it is not possible to have

$t\_1 ... t\_n \equiv s\_1....s\_m t\_{m + 1} ... t\_n$

with $n \> m$. This is left as a (rather dull) exercise for the reader.

I disagree with this note. I can image, say, $u \equiv a \rightarrow b$ and $v \equiv a \rightarrow b \rightarrow c$, where no $p$ is possible.

Maybe I'm missing something! How $p$ is always possible?

---

As asked, the definition of types is given as follow:

2A1 Definition (Types) An infinite sequence of type-variables is assumed to be given, distinct from the term-variables. Types are linguistic expressions defined thus:

i. each type-variable is a type (called an atom);

ii. if $\delta$ and $\rho$ are types then $(\delta \rightarrow \rho)$ is a type (called composite type).

2A1.1 Notation Type-variables are denoted by "a", "b", "c", "d", "e", "f", "g", with or without number-subscripts, and distinct letters denote distinct variables unless otherwise stated.

Arbitrary types are denoted by lower-case Greek letters except $\lambda$.

Parentheses will often (but not always) be omitted from types, and the reader should restore omitted ones in such a way that, for example,

$\rho \rightarrow \sigma \rightarrow \tau \equiv (\rho \rightarrow (\sigma \rightarrow \tau))$

This restoration rule is called association to the right.

# Answer
> 1 votes
It looks like the answer is that, to be syntactically valid, composite types must be fully parenthesized.

In particular, $a \to b \to c$ is not a syntactically valid type (per definition 2A1). 2A1.1 introduces "syntactic shorthand": when they write something like $a \to b \to c$, it should be understand that they actually mean $(a \to (b \to c))$.

The Note appears to be valid when we restrict to syntactically valid types. Thus, your example is not actually a counterexample.

---
Tags: lambda-calculus, type-inference, unification
---


# Question
Title: Repeated fingerprinting after array updates
I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time.

So I was going to compute a **32-bit hash from the few kbytes**, but I am not sure which algorithm to use. It doesn't need to be cryptographically secure, but it should be fast and not need some large lookup tables. And most importantly, **whenever one of the settings (bytes) changes I need to recompute the hash**, which I want to do efficiently.

I guessed I could use any regular hashing algorithm and modify it so that it stores intermediate results in a tree-like structure which trades some memory for a logarithmic benefit in recomputation complexity. (As I found in my research, this concept seems to be called merkle tree). But surely there's an even better way to do it.

I then found about rolling hashes which employ some recursive algorithms, generalised to

$H(arr) = f\_r(\ldots f\_r(f\_r(f\_r(f\_0 \oplus arr\_0) \oplus arr\_1) \oplus arr\_2) \ldots \oplus arr\_n)$

that can be expanded to

$H(arr) = f\_0 \oplus f^0(arr\_0) \oplus f^1(arr\_1) \oplus f^2(arr\_2) \oplus \ldots \oplus f^n(arr\_n)$

This appears perfect for my use case if $\oplus$ is associative, commutative and reversible, which allows to do the recomputation for updating the array at index $i$ by

$H(arr\_{new}) = H(arr\_{old}) \ominus f^i(arr\_{old,i}) \oplus f^i(arr\_{new,i})$

The natural choices for $\oplus$ are bitwise XOR and modular addition, but **which hash algorithms employ them, use a both simple and fast $f^i$ implementation, and still have good hashing characteristics?**

---

I found some but am not totally satisfied.

* CRC32 is known to be fast, and although all descriptions of the algorithm are iterative, I'm confident to be able to derive a non-recursive $f$ function (knowing that crcs have the property $\operatorname{crc}(x \oplus y \oplus z) = \operatorname{crc}(x) \oplus \operatorname{crc}(y) \oplus \operatorname{crc}(z)$). Still, CRC is used and designed for error detection, not fingerprinting, so maybe it's not suitable at all. Am I missing something there?
* Rabin fingerprint appears to be suited better, but I only found iterative implementations with explicit polynom division. Not sure how to derive $f^i$ for this (is it even possible?). Also I'm not certain how it does differ from CRC computation.
* Rabin-Karp rolling hash appears to be a good choice, but I have concerns. Does "modulo $n$" imply I won't get all 32 bit values? Isn't the exponentiation $f^i(x) = x \cdot a^i$ relatively slow? And what constants $a$/$n$ should I use?
* Cyclic polynomial / Buzhash looks easy and efficiently to implement at first. But what about the $h$ in $f^i(x) = rotate(h(x), i)$, wouldn't this need to be a function that generates a 32-bit value from my 8-bit bytes? (I read a lookup table with random data works fine, but 256\*4 bytes is too large for me). And isn't this rotation susceptible for swapping two settings that happen to be 32 bytes apart? Could the upper bytes of $i$, which is effectively used modulo 32, be utilised for something?

Can you dispel my doubts about any of these? Or is there some other algorithm that I missed entirely?

# Answer
> 3 votes
Any of the first three options you list are likely to be fine for what you want.

The CRC provides a good fingerprint (indeed, there's some theory to back that up, based on the theory of Carter-Wegman hashing, 2-universal hashes, etc.).

The Rabin fingerprint is also fine, and is essentially equivalent to the CRC (modulo small technical details that are unimportant). $f^i(m\_i) = m\_i x^i \bmod p(x)$, which can be readily computed even for very large values of $i$ using fast modular exponentiation.

The Rabin-Karp hash is also fine, as long as you choose a good modulus $m$. Don't pick a power of two; use a prime number. Exponentiation is again fast if you use standard algorithms for fast modular exponentiation. If possible, use a constant $a$ that is larger than the largest possible value of any single array element (single byte), i.e., larger than 256. (Alternatively, it might be possible to pick $m$ to be a power of two if you also choose the constant $a$ to be a large random number modulo $m$; I haven't thought about that too carefully, so if that sounds attractive, please post a separate question asking about that specific scenario.)

Buzhash is a little weaker than the other hash functions, though I suppose it's possible it might be good enough in practice. Yes, Buzhash is susceptible to swapping of two values that are a multiple of 32 positions apart. There might be ways to fix this, but given the large lookup tables required, that seems moot. As you say, Buzhash requires a lookup table that maps from 8-bit values to 32-bit values (i.e., 256 entries, where each entry is a 32-bit word), so it sounds like Buzhash is not going to be feasible in your situation.

---
Tags: algorithms, information-theory, hash, rolling-hash
---


# Question
Title: How to show the function is not Turing computable?
Having the function:

$$f(y) = \begin{cases} \ 1 &\text{if }\forall n \Phi\_y(n)=n\lor \Phi\_y(n) \\!\uparrow\\ \ 0 &\text{otherwise.} \end{cases}$$

By the rule of thumb it should not be computable. How to prove it formally? If it's computable, I assumed a function like this exists: $$g(y) = \begin{cases} \ 1 &\text{if $f$(y) = 1 }\\ \ 0 &\text{if $f$(y) = 0} \end{cases}$$

I assumed $g(y)$ is computable. Now there exists a function $\Phi\_{x\_0}(x\_0)$ which simulates $g(y)$. This means: $\Phi\_{x\_0}(x\_0) \downarrow$ iff $\Phi\_{x\_0} (x\_0) \uparrow$, which is a contradiction. Is this sufficient as a proof?

# Answer
> 3 votes
Since I assume this is a homework question, I won't give a fully detailed proof but rather a sketch with some gaps to fill.

Consider the function $$g(x)= \begin{cases} x+1 & \text{ if } \varphi\_x(x)\downarrow\\ \uparrow & \text{ otherwise}.\end{cases}$$ This function is computable (convince yourself of that!), so it has an index $e$.

Now consider the function $f$ on $e$, then computing $f(e)$ comes down to verifying whether $\forall n\ \varphi\_e(n)\uparrow$. Can you see why this contradicts that the halting problem is not computable?

# Answer
> 3 votes
Here's how to solve the halting problem using $f$. Suppose that we are given a Turing machine $T$, and we want to know whether it halts on the empty input. Construct a Turing machine $T'$ which on input $n$ runs $T$, and if it ever halts, it outputs $n+1$. So $T$ halts on the empty input iff $f(\langle T' \rangle) = 0$.

Conversely, we can calculate $f$ using an oracle for the halting problem. Given a Turing machine $T$, construct a Turing machine $T'$ which runs $T$ on all possible inputs in parallel, and stops if it finds out that $T(n) \neq n$ for some $n$. Then $f(\langle T \rangle) = 0$ iff $T'$ halts.

What we have shown is that $f$ (more exactly, the set of 1-inputs of $f$) is $\Pi\_1$-complete.

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


# Question
Title: What is the regular expression to match these conditions: there is atleast one (0), one (1), one (2) and does not end in (0)
I am lost on this and we a restricted to using **flex/lex** regular expression. I can easily do this with a lookahead predicate but i'm not allowed to use those. The does not end in (0) part is simple enough to do, it the other part(must contain at least one (0), one (1) and one (2) is stumping me. Any help would be greatly appreciated.

# Answer
> 1 votes
Here is an expression for all strings which contain both 0 and 1: $$ \Sigma^\*0\Sigma^\*1\Sigma^\* + \Sigma^\*1\Sigma^\*0\Sigma^\*. $$ If we also insist that the string not end in 0, we can modify the expression as follows: $$ \Sigma^\*0\Sigma^\*1. $$ I'll leave you the generalization to your particular case.

---
Tags: regular-expressions
---


# Question
Title: What these simple rules of logical implications mean
Their are many rules of logics, predicate calculus, inferences and syllogisms which haunt me always. It feels better when I find some sensible name to particular rule which also gives me intuition about the meaning of the rule. Recently I came across some simple tautologies:

1. $((x \rightarrow y)\wedge(x \rightarrow \neg y))\rightarrow \neg x$
2. $((x \rightarrow y)\vee(x \rightarrow \neg y))$

I am struggling to find intuition or reasonable interpretation of their meaning:

1. Interpreting rule 1:
If a first variable $x$ implies both: second variable $y$ and its negation $\neg y$, then why the negation of first variable $\neg x$ should always hold? Does it mean to imply that no such variable can exist which can imply both: another variable and its negation?
2. Interpreting rule 2:
Why should a first variable $x$ should always imply either (any given) second variable or its negation?
3. Finally are there any formal names used to refer these rules?

I must be missing something very basic.

# Answer
1. Contradictions can't happen. If $x$ implies a contradiction, then $x$ can't be true.
2. Either $y$ is true, or it isn't. That's still the case even if I first tell you that $x$ is true.
> 2 votes

# Answer
As a terminological issue, "variables" don't imply things, propositions do. Nor is it a good idea of thinking in terms of whether these propositions ("variables") can "exist" or not. In this case you could say that $x$ and $y$ are meta-variables that stand for propositions. The rules you provided are rules that allow us to make inferences. You can instantiate them with whatever propositions you like and they will be valid. It can even be the case that you use the first rule to show that $\neg x$ but $x$ also holds. In this case (assuming the logic is consistent), one of the assumptions must have been false which, incidentally, is exactly what the first rule is saying.

These two rules are slight variations of non-contradiction $\neg(P\land\neg P)$ and the law of excluded middle $P\lor\neg P$. You are probably considering a Hilbert-style proof system where it is common to formulate the rules as applying to implications to make up for the lack of the notion of context that other proof systems have. In this case, these rules would likely just be called "non-contradiction" and "law of excluded middle" rather than having special names of their own. There are many possible equivalent expressions and many possible equivalent axiomatizations, so most formulas won't have specific names. I'm not aware of names that would refer to these specific propositional formulas. It's possible they exist, but it wouldn't be very valuable to know them.

For 1, first note that $(P\to Q)\land(P \to R)$ is logically equivalent to $P \to (Q\land R)$1. So the first interprets to "if $x$ implies a contradiction, then $x$ is false". To connect it to my earlier statement, it says that if we assume $x$ and we can prove both $y$ and $\neg y$, i.e. a contradiction, then our assumption, namely $x$, must not hold. In particular, non-contradiction, i.e. $\neg(P\land\neg P)$, intuitively states that a proposition can't be both true and false.

For 2, the underlying principle, the law of excluded middle, intuitively states that every proposition must be either true or false, there is no third2 or "middle" option. Like 1 you can show that $(P \to Q)\lor(P\to R)$ logically entails $P\to(Q\lor R)$3. This latter statement instantiated to the your second axiom then interprets as "any $x$ implies that either $y$ or $\neg y$ holds". The former statement is a bit stronger and interprets as "either $y$ is true if $x$ is, or $y$ is false if $x$ is true". Ultimately, $Q\lor R$ logically entails both of the earlier formulas, and if they hold for any proposition $P$, then they hold for a true proposition, e.g. $P\to P$, letting us derive $Q\lor R$ from that instance. So as axiom *schemas* $(P\to Q)\lor(P \to\neg Q)$ and $P\to(Q\lor\neg Q)$ are equivalent assuming we have rules for manipulating implications and disjunctions. It's not unusual, though, in classical logic to choose a minimalistic set of axiom schemes that, while typically nicely symmetrical, are tightly interwoven which is why the stronger form may be necessary.

1 This holds constructively.
2 *tertium non datur* "there is no third"
3 Classically this is a logical equivalence, but constructively the converse doesn't hold.
> 2 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Random forests on monotone training set yields a monotone classifier?
Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function?

Suppose I apply the ID3 algorithm (the greedy algorithm) to learn a decision tree on a monotone training set. Is the resulting decision tree guaranteed to be a monotone function?

---

I can formalize this a bit more precisely. Recall that a function is *monotone* if $x \le y$ implies $f(x) \le f(y)$, where we define $\le$ on $\\{0,1\\}^n$ by pointwise comparison ($x \le y$ if $x\_i \le y\_i$ for all $i=1,2,\dots,n$).

Suppose we have a monotone boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$, and suppose that we build a training set as some set of pairs $(x\_i,y\_i)$ where $y\_i=f(x\_i)$. In other words, the training set is consistent with some monotone function, with no errors.

Now train a random forests classifier on a training set of this form. This will learn a classifier that can be thought of as a map $g:\\{0,1\\}^n \to \\{0,1\\}$. Is it guaranteed that the learned classifier will be a monotone function? Alternatively, suppose we apply the ID3 algorithm on this training set. (The ID3 algorithm is the obvious greedy algorithm for recursively building a decision tree that is consistent with the training set.) Is it guaranteed that the learned decision tree will form a monotone function?

# Answer
No, it's not guaranteed. You can end up with a decision tree or classifier that is non-monotone.

Here is an explicit counterexample, i.e., a training set of 5 samples on 5 attributes:

$$\begin{align\*} &(01011, 0)\\ &(01101, 0)\\ &(00111, 1)\\ &(10110, 0)\\ &(11000, 1) \end{align\*}$$

This training set is monotone: it is consistent with the monotone function

$$f(x\_0,x\_1,x\_2,x\_3,x\_4) = (x\_0 \land x\_1) \lor (x\_2 \land x\_3 \land x\_4).$$

However, if you run the ID3 algorithm on this training set, you may end up with a decision tree that computes the function

$$g(x\_0,x\_1,x\_2,x\_3,x\_4) = (\neg x\_0 \land \neg x\_1) \lor (x\_0 \land x\_1),$$

which is also consistent with the training set yet is not monotone. In other words, ID3 might produce the following decision tree:

```
       x0
     /    \
    /      \
  x1        x1
 /  \      /  \
1    0    0    1

```

which is quite evidently non-monotone (there's an obvious violation of monotonicity in the lower-left part of the tree, where the tree says that the output should be the negation of $x\_1$ -- clearly non-monotonic).

Why can ID3 produce this decision tree? Starting with the entire training set, splitting on $x\_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute. Then we recursively run ID3 on the subset of training samples where $x\_0=0$ and recursively run ID3 on the subset of training samples where $x\_0=1$, and on each recursive run we discover an attribute that provides perfect prediction. Try running the ID3 algorithm by hand to see what I mean.

Now at this point perhaps you are going to object: the ID3 algorithm made a choice that is obviously stupid. When the training set contained $(01011,0)$, $(01101,0)$, and $(00111,1)$, the algorithm noticed that $x\_1$ provides perfect prediction of $y$, via the rule $y = \neg x\_1$ -- but this is a stupid choice if we want to end up with a monotone classifier, since even without looking into the future we can immediately see that this is going to yield a non-monotonic result.

So it is natural to try to rescue the ID3 algorithm with a local pruning rule that, at each stage, only considers attributes that aren't obviously dumb -- that aren't obviously going to lead to a violation of monotonicity. Here is one way we could try to operationalize that idea. Let's adjust the ID3 algorithm to be *locally monotone*. Normally, the ID3 algorithm chooses an attribute $x\_i$ that reduces the information gain as much as possible. We could adjust this to also require that we pick an $x\_i$ that is locally monotone, i.e., the fraction of training set pairs with $x\_i=0 \land y=1$ is at most the fraction of training set pairs with $x\_i=1 \land y=1$. (If $x\_i$ is not locally monotone, then splitting on $x\_i$ seems likely to yield a decision tree where we predict an output of 1 more often when $x\_i=0$ than when $x\_i=1$, which is a violation of monotonicity.) Out of all locally monotone choices, we'll pick the attribute with the best information gain (or the lowest Gini impurity, if you prefer).

Unfortunately, even with this modification to enforce local monotonicity, ID3 can still fail to yield a monotonic decision tree. When we run the ID3 algorithm on the above data set, we obtain a decision tree that computes the function

$$g'(x\_0,x\_1,x\_2,x\_3,x\_4) = (\neg x\_0 \land x\_2 \land x\_3) \lor (x\_0 \land x\_1),$$

which is consistent with the training set yet is not monotonic. In particular, we might obtain the following decision tree:

```
       x0
     /    \
    /      \
  x2        x1
 /  \      /  \
0    x3   0    1
    /  \
   0    1

```

This decision tree achieves 100% accuracy on the training set, yet it isn't monotone, even though there exists another decision tree (of the same depth) that *is* monotone and also achieves 100% accuracy.

Why can ID3 produce this decision tree? Starting with the entire training set, splitting on $x\_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute. Then we recursively run ID3 on the subset of training samples where $x\_0=0$ and recursively run ID3 on the subset of training samples where $x\_0=1$, and similar comments apply at each stage of the algorithm. I'll let you run ID3 by hand and see that there is a way to resolve ties at each step that yields the decision tree above.

In short, we can potentially lose either way, whether or not we apply the "locally monotone" constraint. We might get lucky and end up with a monotone decision tree, but there is no guarantee of that -- we also might unlucky and end up with a non-monotone decision tree, even though there exists a monotone decision tree that would be at least as good.

Similar comments apply to the random forests algorithm, as it merely applies the ID3 algorithm multiple times. (Each tree is learned on a different subset of the training set, and with different subsets of the features at each node of the tree, but the same kind of anomaly can still occur.)

This proves that it is at least *possible* to end up with a non-monotonic classifier, even when starting from a monotone data set. I don't know how *likely* it is that this will happen in practice, though, when taking the probability over the random choices made in the ID3 algorithm (to resolve ties) and in the random forests algorithm (for bagging and feature subsetting).

In other words, this demonstrates that if our goal is to learn a monotonic classifier, it's not enough to simply apply the standard random forests or ID3 training procedure on a (monotone) training set; something more sophisticated is needed.
> 3 votes

---
Tags: machine-learning, boolean-algebra, learning-theory
---


title: Is learned RNN still universal?

text:
# Question
Title: Is learned RNN still universal?
I know it has been shown that RNNs are Turing complete. So for any Turing machine, there exists a configuration of a RNN that is equivalent to it.

But I'm wondering, is all those configuration reachable through learning/training? i.e. For any Turing machine, does there exist a data set and a training process, which will finish in finite time and generate an equivalent RNN?

# Answer
The RNN construction of the paper is independent of training, because the weights are fixed and no learning occurs. The proof is based on how the encoding of the input output mechanism should be translated into an RNN so that it behaves the same as a Turing machine given the same input. They construct an RNN equivalent to a two-stack push-down automata, which can simulate any Turing machine. They also end up with a Turing complete universal processor net with 1058 units.

Training process is an approximation for a function, thus accuracy is always a parameter to decide on the computation time. Theoretically speaking, for a network with finite number of processors, and with weights and states represented with rational numbers (computable numbers), which is also a translation of a computable function (i.e. not a real random number generator for each sample), it should converge. Thus, the answer is yes.
> 1 votes

---
Tags: neural-networks, turing-completeness
---


# Question
Title: Featurizing images of different dimensions
I'm building a non linear svm for images to solve a classification problem with domain {0, 1} and I'm currently doing featurization. What I want to do is create 3 features for each pixel representing the rgb value. However, my input images have different dimensions meaning that they are of different widths and heights. So doing just this would result in images having a different number of featurizations.

For example: If i have one image of (10, 2) dimension {(width, height)} then it has 10 * 2 pixels, each with a rgb value. So there would be 10 * 2 * 3 features for this image. If i have a (11, 2) image, then it has 11 * 2 * 3 features.

I am ordering the pixels by first moving horizontally and then verticall. So if I have a (2, 2) dimension image then F1, F2, F3 would be the first three features of pixel (0, 0) wheras F10, F11, F12 would be the features of pixel (1, 1)

One way I thought about solving this is by just extending each image to the maxwidth and maxheight over all images, filling values with -1's for rgb pixels where the image has been extended. For example if i have and image of dimension (2, 2) and the max width and height is (3, 3), then the new image would be of dimension (3, 3) and the with new pixels (2, 2), (0, 2) (1, 2) (2, 0) (2, 1). All of these new pixels would have -1 for all rgb values.

However, will this affect my classifiers ability to recognize patterns? I'm planning on using a svm with radial kernal to start. Is there a better way to fix this?

# Answer
> 1 votes
**Option 1:** You can crop the images to the smallest sizes in all dimensions. However, blindly cropping images will cause you to lose important information, if you don't have a region of interest. For example, if you are focusing on faces, it is fine to define a ROI and crop around the face. On the other hand, for example if you are doing pure color-wise comparison of images, you will not know if you are cropping all red pixels from an image, that actually contain valuable information.

**Option 2:** You can scale them to the largest sizes in all dimensions. However, blindly resizing images might cause you to lose important structural information. For example, if you are doing color-wise comparison, you can upsample the images and the mean of the pixels will not change much. On the other hand, for example if you are looking for faces in an image, your faces will not be circular but elliptical.

**Option 3:** You can extend the images to the largest sizes in all dimensions. This introduces additional information if you don't filter it in the following steps. For example, for color comparison, you can fill with value nan and later neglect features which has value nan. You can fill with nan, or -1, or mean, etc.

**Option 4:** You can define a window to process the images. Imagine that you have an n\*n window (say 3\*3), and you slide that window on the image and extract features from each window (F1 is from \[1:3,1:3\] of the image, F2 is from \[2:4,1:3\] of the image, ...). Thus, the features are independent of the image size. However in this case you need to have a clever way to combine those features, because you will have different number of features from each image.

---
Tags: algorithms, machine-learning, computer-vision, svm, features
---


# Question
Title: Extracting intersecting objects of the same colour from an image
What is the good way to extract the objects(circles) from image as shown in picture below?

respectively create two images one with lines and one with circles from source image.

I started with detecting contours in image to filter everything that may be circle from image which gives me results like this:

I'm new to computer vision and dealing with this specific task, so want thank you for any help and guidance.

Thank you all, here are some answers to questions from comments:

> Define "best"

a good way to do it

> Which techniques do you know that have something like that?

Today I looked at template matching, created a template for the black and white circle and localised them in an original image. Once I have this extracting lines is straightforward (just subtracting circles from the original image). This seems working well in the simplest scenario when circles are the same size as templates.

The more robust way I think will be to use Haar Cascade classifier, train it on different size circles, and continue as with results from template matching.

Correct me if there maybe a better way?

The main idea is to digitalize diagrams consisting of black and white circles connected by lines, The size of diagrams and quality of images may vary. Also, the circles may contain numbers (Extracting those is something for future)

The lines connecting circles are axis aligned, they define position of circles in diagram (similar to cartesian plane)

I mentioned Python (js) and OpenCV languages in case there are some specific implementation details I should be aware of. I'm also learning Python while doing this :).

I don't expect the solution or code, rather pushing to right direction and strategy to deal with this kind of problems.

# Answer
> 1 votes
First, I would suggest you to take a look at morphological operations on images, especially dilation and erosion. Dilation grows the boundary of foreground pixels (gets rid of holes), and erosion shrinks the boundary of foreground pixels (gets rid of bridges). In your case, erosion with an appropriate kernel might get rid of those unwanted lines. Then you apply dilation with the same kernel to preserve the circles. The two of them applied together in this order is called opening. Those functions are predefined in OpenCV, check out `morphologyEx` function.

Second, I would suggest you to take a look at convexity of shapes. The output circles in your images are convex, but the ones with lines are now. Thus, you can find the non-convex points of the contours (that you already found), and connect the contours from those points, so that you have convex shapes, i.e. desired output circles. To accomplish this, you can find the convex hull and convexity defects using related OpenCV functions.

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


# Question
Title: Counting Total Number of Non-Equivalent Configurations in a 2-D Grid
This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.

Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ thru $12$ inclusive. Each cell in this grid can be in any of $k$ states (where $k$ ranges from $2$ thru $20$).

The problem is to find the total number of distinct (non-equivalent) state configurations of this grid.

Definition: Two configurations of a grid, $c\_1$ and $c\_2$, are deemed "equivalent" if it is possible to change $c\_1$ to $c\_2$ by swapping any pair of rows and/or any pair of columns (you can perform the swap operation as many times as you want).

To take an example, let's consider a grid with $w=2$, $h=2$, and $k=2$. We will represent each of the two states as $0$ and $1$ respectively.

One possible configuration of the grid is one where all the cells are in state $0$:

00
00

You could swap any rows and/or columns without changing anything. So the above counts as 1 configuration.

Another configuration is where only 1 cell is in state $1$. There are 4 possible arrangements:

01 10 00 00
00 00 01 10

But note that all of the 4 arrangements are "equivalent", because you can get any of the arrangements by swapping rows and/or columns. So the above counts as 1 configuration.

Next, exactly 2 cells are in state $1$:

11 00
00 11

Another (non-equivalent) way in which 2 cells are in state $1$:

10 01
10 01

And yet another:

10 01
01 10

So there are 3 non-equivalent configurations in which exactly 2 cells are in state $1$.

Next, exactly 3 cells are in state $1$:

10 01 11 11
11 11 10 01

1 configuration, just as in the case where only 1 cell was in state $1$.

Finally, all 4 cells are in state $1$:

11
11

1 configuration, just as in the case where all 4 cells were in state $0$.

So, counting them up, there are exactly $7$ distinct configurations for the case where $w=2, h=2, k=2$.

For reference, here are some brute-force test cases I ran on some additional examples (where the w,h,k values are fairly small):

w=2,h=1,k=1 Answer: 1
w=2,h=1,k=2 Answer: 3
w=2,h=1,k=3 Answer: 6
w=2,h=1,k=4 Answer: 10
w=2,h=1,k=5 Answer: 15
w=2,h=1,k=6 Answer: 21
...
So at least when w, h are fixed at 1,2 (or at 2,1), the pattern seems pretty obvious as k increases. Here is another suite of test cases for w=2, h=2:

w=2,h=2,k=1 Answer: 1
w=2,h=2,k=2 Answer: 7
w=2,h=2,k=3 Answer: 27
w=2,h=2,k=4 Answer: 76
w=2,h=2,k=5 Answer: 175
w=2,h=2,k=6 Answer: 351
...
This is much less obvious to me. If there is a pattern, I'm unsure how to find it.

One more suite of test cases for good measure:

w=2,h=3,k=1 Answer: 1
w=2,h=3,k=2 Answer: 13
w=2,h=3,k=3 Answer: 92
w=2,h=3,k=4 Answer: 430
w=2,h=3,k=5 Answer: 1505
...
yep I'm lost as to what insight if any can be gained.

So, for some arbitrary $w,h,k$, I'm wondering whether there is some type of closed-form formula or perhaps a way to get the answer via dynamic programming/recursion or perhaps divide-and-conquer? I've tried a few of these approaches and didn't really see any obvious breakthrough. The answers get very large very quickly (for example, for $w=2,h=3,k=4$, the answer is 430). I can only imagine how large the answer would be for, say, $w=12,h=12,k=20$.

I would appreciate any help on this. Thanks!

# Answer
We will use Burnside's lemma, plus some additional optimizations.

Note that row swaps and column swaps commute, so the group of allowable transformations to the grid is exactly $G = S\_w \times S\_h$, where $S\_n$ is the symmetric group on $n$ symbols. Note that $G$ embeds in $S\_{wh}$ via a canonical embedding $\varphi : G \to S\_{wh}$, given by $\varphi(\pi,\sigma) = \tau$ where $\tau$ is defined by $\tau(i,j) = (\pi(i), \sigma(j))$. Therefore, we will think of $G$ simultaneously as the direct product $S\_w \times S\_h$ and also as a subgroup of $S\_{wh}$.

Now let's count the number of grids that are fixed by a group element $g=(\pi,\sigma) \in G$. Define the *cycle type* of a permutation $\pi$ to be the multiset of lengths of the cycles in the cycle decomposition of $\pi$. If $\pi \in S\_n$, the cycle type of $\pi$ is a partition of $n$. With this in mind, we will let $\ell(\pi)$ denote the cycle type of $\pi \in S\_w$ and $\ell(\sigma)$ the cycle type of $\sigma \in S\_h$. Finally, let $\ell((\pi,\sigma))$ denote the cycle type of $(\pi,\sigma)$, thinking of $(\pi,\sigma)$ as an element of $S\_{wh}$.

We can express $\ell((\pi,\sigma))$ in terms of $\ell(\pi)$ and $\ell(\sigma)$. Let $x,y$ range over all $x \in \ell(\pi), y \in \ell(\sigma)$. For each $x,y$, $\ell((\pi,\sigma))$ has $\gcd(x,y)$ copies of $\operatorname{lcm}(x,y)$. It follows that

$$|\ell((\pi,\sigma))| = \sum\_{x \in \ell(\pi)} \sum\_{y \in \ell(\sigma)} m\_x n\_y \gcd(x,y),$$

where $x,y$ range over all distinct values (without repetition), and $m\_x$ is the multiplicity of $x$ in $\ell(\pi)$ (the number of times $x$ appears in $\ell(\pi)$) and $n\_y$ is the multiplicity of $y$ in $\ell(\sigma)$.

Now the number of grids that are fixed by $(\pi,\sigma)$ is

$$f(\pi,\sigma) = k^{|\ell((\pi,\sigma))|},$$

where $|\ell((\pi,\sigma))|$ counts the number of cycles in $(\pi,\sigma) \in G$ (multiplicities are counted). By the above formula for $|\ell((\pi,\sigma))|$, we see that

$$f(\pi,\sigma) = k^{\sum\_{x \in \ell(\pi)} \sum\_{y \in \ell(\sigma)} m\_x n\_y \gcd(x,y)}.$$

To apply Burnside's lemma, it remains to sum $f(g)$ over all elements $g \in G$, as Burnside's lemma tells us that the total number of non-equivalent grids is

$$N = {1 \over |G|} \sum\_{g \in G} f(g) = {1 \over w! h!} \sum\_{g \in G} f(g).$$

In principle, we could compute this sum by enumerating all $w! h!$ elements in $G$, then evaluating $f$ on each, and summing the result.

It turns out this can be optimized further, as $f(\pi,\sigma)$ depends only on $\ell(\pi)$ and $\ell(\sigma)$, but not on any other aspect of $\pi$ or $\sigma$. Thus, we can more efficiently evaluate the sum using the formula

$$\sum\_{g \in G} f(g) = \sum\_{P,Q} N(P,Q) \times k^{\sum\_{x \in P} \sum\_{y \in Q} \gcd(x,y)},$$

where the inner sum ranges over all partitions $P$ of $w$ and all partitions $Q$ of $h$, and where we define

$$N(P,Q) = |\\{(\pi,\sigma) \in G : \ell(\pi)=P, \ell(\sigma)=Q\\}|$$

to count the number of group elements of $G$ whose cycle types are $P,Q$. Now we have

$$N(P,Q) = N\_w(P) \times N\_h(Q),$$

where $N\_w(P) = |\\{\pi \in S\_w : \ell(\pi)=P\\}|$ is the number of permutations in $S\_w$ with cycle type $P$, and similarly $N\_h(Q)$ is the number of permutations in $S\_h$ with cycle type $Q$. Finally, there is a known formula to compute $n\_w(P)$ for any desired partition $P$; it is

$$N\_w(P) = {w! \over \prod\_{x \in P} m\_x! x^{m\_x}},$$

where $x$ ranges over the distinct elements of $P$ and $m\_x$ is the multiplicity of $x$ in $P$ (the number of times $x$ appears in $P$).

Plugging in, we find that the total number of non-equivalent grids is given by

$$N = \sum\_{P,Q} {k^{\sum\_{x \in P} \sum\_{y \in Q} m\_x n\_y \gcd(x,y)} \over \prod\_{x \in P} m\_x! x^{m\_x} \prod\_{y \in Q} n\_y! y^{n\_y}}.$$

As before, in this formula $x,y$ range over distinct values, $m\_x$ is the multiplicity of $x$ in $P$, and $n\_y$ is the multiplicity of $y$ in $Q$.

This can be computed by two nested for-loops that iterate over all partitions $P$ of $w$ and all partitions $Q$ of $h$.

What is the running time of this algorithm? The asymptotic running time is approximately $O(p(w) p(h))$, where $p(n)$ is the number of partitions of the integer $n$. It is known that asymptotically $p(n) = O(\exp\\{\pi \sqrt{2n/3} \\})$, so it follows that the asymptotic running time of this algorithm is approximately $O(\exp\\{\pi \sqrt{2/3} (\sqrt{w}+\sqrt{h})\\})$, or equivalently, approximately $O(2^{3.7(\sqrt{w}+\sqrt{h})})$. This should allow you to handle the full range of values $1 \le w,h \le 12$, as for that range we have $\sqrt{w}+\sqrt{h} \< 7$ and $2^{3.7 \times 7} \approx 2^{26}$ is not too large.
> 5 votes

---
Tags: combinatorics, dynamic-programming, recursion, divide-and-conquer
---


# Question
Title: Is it proven that quantum computation is no better at solving NP complete problems than classical computation?
Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?

# Answer
It is suspected that NP-complete problems cannot be solved in quantum polynomial time (i.e., that they are not in BQP), but this hasn't been proved. We don't expect a proof in the near future, since this would imply that P is different from NP.
> 11 votes

---
Tags: np-complete, quantum-computing
---


# Question
Title: Can there be 'dead states' in a context-free grammar?
Can a context-free grammar include "dead states" from an automaton, such as

$$G = \big(\\{a, b, c\\}, \\{A, B, C\\}, \\{A\to aB, B\to b, B\to C, C\to cC\\}, A\big)\\,?$$

The production rules $B\to C$ and $C\to cC$ will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at some point?

# Answer
Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty string productions, and no cycles; so it is safe to assume that a CFG is proper without loss of generality.
> 24 votes

# Answer
Yes of course. Every NFA can be written as a CFG. And building a DFA with a 'dead state' (the term I was taught, is 'sink') is trivial.

Example: $$G = (\\{a\\}, \\{A\\}, \\{A\to A\\},A)$$ is a CFG that describes the empty language over the alphabet $\\{a\\}$.

Analogous to the NFA with only one non-accepting starting state and only a self-transition with $\epsilon$.
> 3 votes

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


# Question
Title: Understanding sequential solution for the TAOCP 3 Million Men problem
The problem and solution of interest is described here: What does \> mean in this TAOCP solution?

Can anyone explain following points in that solution:

1. How exactly we can build (x\[i\], x\[i+2\]) for 1 \<= i \<= N-2 ?
2. What exactly means "merge G with it"? Provide exact algorithm for merging these two files.
3. How steps 1-4 are executed? Is it:

```
if (condition 1) {
    ....
}
if (condition 2) {
    ....
}
if (condition 3) {
    ....
}
if (condition 4) {
    ....
}

```

or

```
if (condition 1) {
    ....
}
else if (condition 2) {
    ....
}
else if (condition 3) {
    ....
}
else if (condition 4) {
    ....
}

```

?

# Answer
> 1 votes
1. With a `for` loop that steps through the array and creates a new pair from the $i$th and $(i+2)$th elements, for each $i$.
2. The same as the merge step in merge sort.
3. There are no "otherwise"s in the statement in English, so there should be no `else` statements.

---
Tags: algorithms, sorting
---


# Question
Title: How to prove an polynomial run time is faster than exponential using definition of big O
This is for homework so feel free to not give me an answer but steer me in the right direction.

The problem states:

> Prove that $n^{1000000} = O(1.000001^n)$ using the formal definition of Big-O.

The definition of Big-O is:

$\hspace{2cm}T(n)=O(f(n)):\\,\exists\\;c\gt0\\;$ and $\\;n\_0\ge0,\\;$ such that $\\;T(n)\le c\cdot f(n)$

Now, I know that there is also the definition that

$\hspace{4cm}$For every $\\;r\gt0\\;$ and $\\;d\gt0,\\; n^d = O(r^n)$

But how exactly am I supposed to prove this without using induction or a limit equation? Any guidance on where to start?

This is what I have so far:

$\hspace{7.6cm}\frac{T(n)}{f(n)}\le c$

$\hspace{6.8cm}\frac{n^{1000000}}{1.000001^n}\le c$

$\hspace{6cm}\frac{1.000001^{1000000n}}{1.000001^n}\gt\frac{n^{1000000}}{1.000001^n}$

EDIT: I continued simplifying.

$\hspace{5.4cm}1.000001^{999999n}\gt\frac{n^{1000000}}{1.000001^n}$

Do I stop here?

$\hspace{5.3cm}1.000001^{1000000n}\gt n^{1000000}$

$\hspace{3.4cm}1000000n\cdot log(1.000001)\gt 1000000\cdot log(n)$

$\hspace{5.8cm}log(1.000001)\gt \frac{1}{n}\cdot log(n)$

$\hspace{6.8cm}1.000001\gt n^{1/n}$

What would the above even tell me?

# Answer
> 4 votes
In order to prove that $f(n) = o(g(n))$ (and so $f(n) = O(g(n))$) for two positive functions $f(n),g(n)$, it is enough to prove that $$ \lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0. $$ In your case, you can use L'Hôpital's rule, together with induction on $k$. We will show that for all integer $k \geq 0$ and all $c \> 1$, $$ \lim\_{n\to\infty} \frac{n^k}{c^n} = 0. $$ This is clear for $k = 0$. Given that it holds for $k-1$, it holds for $k$ since $$ \lim\_{n\to\infty} \frac{n^k}{c^n} = \lim\_{n\to\infty} \frac{k}{\ln c} \frac{n^{k-1}}{c^n} = 0, $$ by the induction hypothesis.

If $k$ is not integral, the result still holds, since $n^k \leq n^{\lceil k \rceil}$.

---
Tags: asymptotics, runtime-analysis, polynomial-time
---