# Question
Title: Where does the CPU get its first instructions from?
In order for the BIOS code to matter, it must be evaluated by the processor. However, the processor itself needs to do work to actually get access to the BIOS code, since the CPU only performs instructions that are given, something must give the instructions to the CPU (since I can't imagine a way for instructions to just "flow" from BIOS to the CPU without anything in between).

Where are the instructions for loading BIOS and passing control to it stored, and who passes these instructions to CPU so that CPU can preform them?

# Answer
## 1. (A summary of the answer-in-comments by Jukka)

Startup code is stored in ROM (non-volatile memory) at a fixed address X.

When you activate the "reset" signal in the CPU, the CPU will initialise its registers to certain hard-coded values. The instruction pointer is one of these registers that are initialised to certain hard-coded values. In essence, the CPU manufacturer picks this hard-coded address X. Hence, when you reset your CPU, the instruction pointer is reset to the same fixed address X. The CPU starts to execute instructions as usual: fetch the next instruction from address X, decode it, execute it, etc

Then whoever puts together a complete computer has to make sure that there is something useful at address X (e.g., a ROM memory chip with meaningful startup code).

## 2. Elaboration

The CPU has a very simple way of working, known as the FETCH-EXECUTE cycle:

(a) **FETCH**: It goes to the memory and brings the instruction that is at address \[PC\]. (PC is a name of an internal CPU register; it holds the address of the instruction we need to perform next..).
(b) **Execute**: The PC executes the instruction it has just retrieved from the memory
(c) PC $\gets$ PC+1.(\*)
(d) Go back to (a).

This fetch-execute loop happens all the time, regardless of the program you are running. In particular, when the CPU boots up (say, when its power goes from 0 to Vcc) the CPU simply begins to perform the above loop.

The initial value of PC depends on the specific CPU. It can be that the CPU wakes up with PC=0, or it can be that PC=0xFFF0 (as happens with Intel's X86 family), or with any other value PC=$PC\_{init}$. If you press the reset button, or turn the power off and on, the CPU restores the PC to its initial value $PC\_{init}$ and the CPU begins running the program that is in the memory at address $PC\_{init}$, through the fetch-execute loop.

Now it is the computer designer task to make sure that the BIOS sits in the memory at address $PC\_{init}$. The BIOS usually resides in a non-volatile memory so there is always a program to run in that address, even if you just turned the power off and on (this deletes the RAM but not the BIOS. It is more difficult to delete/change the BIOS, although possible and happens, e.g., when your device updates its "firmware").

(\*) Advancing the PC by **+1** assumes that each instruction takes 1 address of the memory space. The is rarely the case. In real systems we may see here PC+4 (as in the 32b MIPS) or PC+x (with $x\in\\{1,...,7\\}$ which depends on the instruction itself) as in the X86 family, etc.
> 9 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Finding the best poker hand in a connected grid structure where order matters
I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation.

This grid has 12 random cards, in random positions. Each card is connected to the vertically, horizontally and diagonally adjacent cards.

The hands are standard poker hands but no extra cards are allowed – only the cards which constitute the hand. So, a pair is only two cards connected, four of a kind is just four cards connected, etc.

The best hand for this grid highlighted:

Order matters, so a straight must be in the correct order (e.g. 10, J, Q, K, A is valid but 10, A, J, Q K is not). There is no straight in this particular grid, the 10s are not connected to the Jack directly.

I am looking for an algorithm that finds the best hand for a random grid. The grid isn’t ever going to be much larger than this grid of 12.

I am also looking for an algorithm that finds out if there are no moves at all – this would alert the player to this fact to save them searching for too long…

# Answer
I recommend you use breadth-first search (BFS) through the state space.

Start by trying to find (partial) straights that are ascending. For each possible starting position (there are 12 possibilities), use BFS to search for a path that starts at that position and makes an ascending straight (i.e., the numbers increment by one each time you move forward). This will find you the longest ascending straight.

Next search for descending (partial) straights in the same way. This will find you the longest descending straight.

You can also search for straight flushes in this way, too.

Next for x-of-a-kinds in the same way. This will find you the longest sequence that are all of the same rank (e.g., two-of-a-kind, three-of-a-kind, four-of-a-kind, five-of-a-kind).

Next search for flushes in the same way. This will find you the longest sequence that are all of the same suit.

You can look for two-pair and full-house separately, with a different method tailored to that problem. Enumerate all pairs (i.e., all pairs of adjacent positions where the two cards have the same rank). Now check whether any two of those pairs are adjacent; if so, you have found a two-pair. Similarly, enumerate all three-of-a-kinds (i.e., paths of length 3 where the three cards have the same rank). Now check whether any pair is adjacent to any three-of-a-kind; if so, you have found a full-house.

In this way you can find the best poker hand in the grid. I expect that this will be very efficient.
> 0 votes

---
Tags: algorithms, search-algorithms, square-grid
---


# Question
Title: Ackerman hierarchy for higher order primitive recursion in System T
Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he mentions that once we use more types in the recursor we gain more expressive power with the system.

I don't understand how exactly this happens. Is it possible to come up with sort of Ackermann hierarchy with the higher order primitive recursion, i.e. a hierarchy of faster and faster growing functions where each function is expressible in System T but the diagonal is not? I guess so, but the construction does not seem evident to me and I would be interested seeing how one would construct it, or receive pointers to literature.

I'm after something concrete. I'm aware of the general diagonal argument that proves existence of a function not in T, but I would like to see how one would really "step up in the type hierarchy".

# Answer
> 1 votes
(This is a very partial answer, only addressing the first point, and not the main question about the hierarchy.)

I don't have a proof to point out to you, but the idea is that a single first-order recursor on naturals such as $$ \begin{array}{l} rec: (nat \to nat) \to nat \to nat \to nat \\ rec\ f\\; z\\; n = f(f(\ldots f(z))) \qquad \mbox{($n$ times $f$)} \end{array} $$

would be much less powerful than having the full (primitive) recursion scheme

$$ rec\_U: (U \to U) \to U \to nat \to U $$

since the latter roughly resembles a polymorphic term in System F, which can be used at many types $U$.

Indeed, the basic $rec$ only gives us access to the first order primitive recursion scheme, as we can find in a computability / recursion theory book. With only that, we know functions like Ackermann's are not definable. (Well, this is not that obvious since here we also have higher-order lambdas, it's only recursion which is constrained. But the point should stand anyway, I think.)

With the $rec\_U$ scheme, instead, we can choose $U = nat \to nat$, which allows us to define Ackermann's function, as Girard shows in the book mentioned by the OP. Hence, the scheme is strictly more powerful.

# Answer
> 1 votes
This is an interesting question, whose answer is absolutely not trivial.

I'll give the short answer first: There is a hierarchy of systems, call them $T\_k$, where the only recursors allowed are $\mathrm{rec}\_U$ with the *order* of $U\leq k$, where the order of a type is defined as:

$$ \mathrm{ord}(\mathrm{nat})=0$$ $$ \mathrm{ord}(U\rightarrow V)= \max(\mathrm{ord}(V),\mathrm{ord}(U)+1)$$

Then the theorem is:

> **Theorem**: for every $k$, there is a term $t\_k:\mathrm{nat}\rightarrow\mathrm{nat}$, such that
>
> * $T\_{k}\vdash t\_k:\mathrm{nat}\rightarrow\mathrm{nat}$
> * $T\_{k-1}\not\vdash t\_k:\mathrm{nat}\rightarrow\mathrm{nat}$
>
> $t\_k$ grows faster (as a function from $\mathbb{N}\rightarrow\mathbb{N}$) than any function definable in $T\_l$, with $l\<k$.

Note that $T=\bigcup\_k T\_k$.

As a first step, it's probably useful to note that the Ackermann function can be defined like this (as hinted by chi's answer): $$ \mathrm{ack}(n,m) = \mathrm{rec}\_{\mathrm{nat}\rightarrow\mathrm{nat}}(\lambda f.\mathrm{rec}\_{\mathrm{nat}}\ f\ 0\ m)\ (\lambda p.S\ p)\ n$$ modulo a mistake on my part.

This indeed suggests that $\mathrm{rec}\_{\mathrm{nat}\rightarrow\mathrm{nat}}$ had additional "power".

---

But how do we go all the way up the tower to arbitrary $T\_k$?

The trick is to consider a triple correspondence between:

1) Ordinals below $\varepsilon\_0$

2) Fragments of $\mathrm{HA}\_k$ of Heyting arithmetic where induction is restricted to statements with less than $k$ quantifier alternations.

3) Functions definable in $T\_k$

For each ordinal $\lambda\_k=\omega^{\omega^{{\dots}^\omega}}$ where the tower is of height $k$, it is possible to consider a *proof* in Heyting arithmetic that such an ordinal is well-founded, and to *extract* from it a term $t\_k$ typeable in system $T\_k$ which corresponds to the function $g\_{\lambda\_k}$ in the Grzegorczyk hierarchy.

Such a term *cannot* be well-typed in $T\_{k-1}$ due to the correspondence outlined above, and the fact that $\mathrm{HA}\_{k-1}$ does not prove the well-foundedness of $\lambda\_k$.

**Lies and references**:

The correspondence between $T\_k$, $\mathrm{HA\_k}$ and $\lambda\_k$ is not quite as clean as I suggested, there should actually be $k$, $k'$ and $k''$, each related by some concrete constant.

An explicit construction for the $t\_k$ along the path outlined above is given by Ulrich Berger in *Program Extraction from Gentzen’s Proof of Transfinite Induction up to $\varepsilon\_0$*

I'm afraid I don't have a reference for the triple correspondence better than *Proofs and Types*, though I would be very happy to hear of one.

---
Tags: computability, lambda-calculus, recursion, type-theory
---


# Question
Title: Maximum sum of depths of all external nodes in a Binary Tree
Let $T$ be a (possibly improper) binary tree with $n$ nodes, and let $E(T)$ be the sum of the depths of all the external nodes of $T$. (In a proper binary tree each node have 0 or 2 children. An external node is a leaf, i.e., any node that is not an internal node.)

Is there a configuration for $T$ such that $E(T)$ is $\Omega(n^2)$? Is there an infinite sequence of trees $T\_1,T\_2,T\_3,\dots$ such that $T\_n$ has $n$ nodes and $E(T\_n) = \Omega(n^2)$?

---

I have found 2 extreme cases for $E(T)$:

* each internal node has 1 child (then $E(T)$ is $O(n)$), or
* each internal node has 2 children (then $E(T)$ is $O(n \log\_2 (n))$).

I have tried shaping the tree like this:

but as you can see it grows asymptoticly similar to Arithmetic Series and $E(T)$ is $O(n)$. I even showed it algebraically.

---

Internal nodes are just arithmetic sum, and leafs are the last term of this sum times 2.

$x$ - level of a tree $$\sum\_{i=1}^{x}i=\frac{x(x+1)}{2}$$ $$\frac{x(x+1)}{2} + 2x = n$$ solving for x gives $$x = \sqrt{2n+\frac{25}{4}} - \frac{5}{2}$$
$x$ is $\Omega (\sqrt{n})$.
Now lets try calculation $E(T)$: There are $2x$ leafs each with depth $x$ $$E(T) = 2x \cdot x $$ $$E(T) \text{ is } \Omega (2\sqrt{n} \cdot \sqrt{n}) = \Omega(n) $$ So my question is how this tree should look like?

# Answer
> 1 votes
Consider a tree that has a chain of length $n/2$ at the top, where each node has exactly one child. Then, the remaining $n/2$ nodes are attached at the bottom of the chain, as a complete tree of depth $\log\_2 (n/2)$.

With this shape, every leaf is at depth $n/2 + \log\_2 (n/2) = \Theta(n)$. There are about $n/4=\Theta(n)$ leaves. So, the sum of the depths of the leaves is $E(T) = \Theta(n^2)$.

This is asymptotically optimal; no tree can have $E(T) = \omega(n^2)$, as the maximum possible depth is $n$, and the maximum number of leaves is $n$, so we have $E(T) \le n^2 = O(n^2)$.

---
Tags: binary-trees
---


# Question
Title: Calculating mod of n^k mod p in O(log k)
> Given $n\>0$, $k\>0$, and a prime number $p$, compute: $$n^k\mod p$$ in $O(\log k)$ time. Here $x \mod y$ means the remainder for $x$ being divided by $y$. For example, $2^3\mod 7 = 1$. You assume that all of $n$, $k$, and $p$ can fit in a single word in your computer. Moreover, if $x$ and $y$ are numbers with sizes bounded by $O(1)$ words, then the computer can carry out each arithmetic operation ($+$, $-$, $\times$, $/$, $\mathrm{mod}$) on $x$ and $y$ in $O(1)$ time.

We want to achieve $T(k) = 2T(k/2) + O(1)$ since by the master theorem, this will give me $O(\log k)$. Now I'm assuming that I have to do $k/2$ every step with divide and conquer. If the number is even, it'll eventually get to $k=1$. Then how do I turn this to the correct number?

I know that $(n^k/2 \mod p \cdot 2) \mod p$ will give the same answer.

# Answer
> 1 votes
Forget the master theorem. Your formula T(k) = 2T(k/2) + O(1) is total nonsense, it would give you O(k), not O(log k). And (n^k/2 mod p * 2) mod p makes no sense.

To calculate $n^k$ for k ≥ 2, you check if k is even or odd, that is either k = 2m or k = 2m + 1. You calculate $n^m$ recursively, multiply by itself, and if k is odd then you multiply by n once more. And what if k = 1? I hope you know how to calculate n^1?

That's for powers. Powers modulo p work exactly the same, except you do every multiplication involved modulo p.

Why your formula T(k) = 2T(k/2) + O(1) was totally wrong: Because you don't calculate $2^m$ twice. You calculate it once, then square it. So the formula is T(k) = T(k/2) + O(1).

---
Tags: algorithms, number-theory, modular-arithmetic
---


title: Best way we know search for an integer

text:
# Question
Title: Best way we know search for an integer
Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?"

My question is about the best way we know in terms of time/space to answer this query. Ultimately, the time should be guaranteed (not randomized) and the space must be polynomial of $n$.

Firstly, one can use let's say 2-3 Trees or another type of search trees to do this in $O(log n)$ time and $O(n)$ space.

Secondly, one might say that it can be done in $O(1)$ with hashing, however I should note that this time is *random* and we are looking only for deterministic algorithms. Universal hashing requires a lot of space.

So, one way to approach the main question is to answer if there is a perfect hashing constructable in poly-time and poly-space?

Another approaches are also appreciated. Thanks.

# Answer
A very simple solution if your integers are not too big, let's say biggest integer is $U-1$ and there are $U$ different integers (between 0 and $U-1$), is to build a table T (bit matrix) of size $U$ with all bits set to $0$. Upon occurrence of item $k$ set $T(k)\leftarrow 1$.

If you want to search for an item $k$ you simply check if $T(k)$ is $1$ or $0$. This solution takes $\Theta(U)$ space and $\Theta(1)$ time per inserted item, or per search. If $U$ is much less than $n$ and you don't make deletions then I think this solution is ideal in your case. If you make deletions of $U \> n$ then more sophisticated solutions are needed
> 2 votes

# Answer
You probably want to look into the field of succinct rank/select data structures. Assuming that the set is static or semi-static, there is a good collection of data structures in Okanohara and Sadakane's paper, Practical Entropy-Compressed Rank/Select Dictionary.

We will suppose you want to represent a subset $S \subset \\{0\ldots n-1\\}$, where $\left| S \right| = m$. There are ${n \choose m}$ such subsets, so we need at least $\log\_2 {n \choose m}$ bits to represent any subset. What you want is a data structure which uses about that much space, and which supports a membership test in close to constant time.

First, a quick note on measuring time vs space requirements. In the case of time, we customarily measure in big-oh (e.g. $O(1)$) because what we're really interested in, the time measured on a clock, depends on the language, compiler, hardware, etc.

In the case of space requirements, however, we can measure the space usage in bits, because we customarily measure space in bits, not in physical units (e.g. cubic metres of RAM).

If information theory tells us that we need at least $f(n)$ bits to store some data structure. Then:

* If we have a data structure which uses $f(n) + O(1)$ bits, we call it *implicit*.
* If we have a data structure which uses $f(n) + O(f(n)) = f(n) (1 + O(1))$ bits, we call it *compact*. Intuitively, the $O(1)$ means "constant relative overhead".
* If we have a data structure which uses $f(n) + o(f(n)) = f(n) (1 + o(1))$ bits, we call it *succinct*. Intuitively this means that as the data structure gets bigger, the relative overhead eventually becomes negligible.

Additionally, we will use the word RAM model and assume that the machine word size is $\Theta(\log n)$, that is, that an "integer" can be stored in a constant number of words.

If the subset is "dense", that is if $m \approx \frac{n}{2}$, then $\log\_2 {n \choose m} \approx n$, so in that case you can't do better than a bit vector.

Things get more interesting when the set is sparse or almost full. If $m \> \frac{n}{2}$, you can always store the complement of the subset instead. So we can just consider the case of a sparse subset where $m \< \frac{n}{2}$.

The **esp** variant from that paper uses $n H\_0(S) + o(n)$ bits of storage, and supports both rank and select queries in $O(1)$ time assuming the word-RAM model. Since a membership test can be trivially implemented with two rank queries, this supports membership tests in $O(1)$ time, and the space requirement is essentially a zero-order entropy compressed representation of the subset plus some overhead. This is pretty good, but if $m \ll n$, the $o(n)$ overhead term dominates the space requirement.

Because of this, the **sdarray** variant is more practical for sparse sets. The space requirement for **sdarray** is $m \log\_2 \frac{n}{m} + 2m + o(m)$ bits, although if you only need membership tests, this can be reduced to $m \log\_2 \frac{n}{m} + m + o(m)$ bits. Note if $m\ll n$, $\log\_2 {n \choose m} \approx m \log\_2 \frac{n}{m}$ and so this data structure is succinct. A membership test query takes $O(\log \frac{n}{m}) + O(\log^4 m/\log n)$ time in the worst case, but is typically constant in practice.
> 2 votes

---
Tags: data-structures, time-complexity, search-algorithms, space-complexity
---


# Question
Title: Is finite abelian group isomorphism in Log Space?
**Definition :** An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written

**Input :** Two finite abelian groups $|G| =n$ and $|H|=n$ by their table representation

**Find :** Is $G \cong H$?

There is an $O(n)$ running time algorithm for this problem, due to Kavitha \[1\].

**Question :** Is this problem known to be in Log Space?

I tried to google but did not get anything related to log space.

---

\[1\] T. Kavitha, *Linear time algorithms for Abelian group isomorphism and related problems*. *Journal of Computer and System Sciences* 73(6):986–996. (Science Direct)

# Answer
The finite abelian group-isomorphism when groups are given in the form of multiplication tables known to be in $L$ and in $TC^0 (FOLL)$. For more detail you can see the thesis of the Dr. Fabian.

PhD Thesis of Dr. Fabian ( see page number 180 and 185 )
> 2 votes

---
Tags: algorithms, complexity-theory, group-theory
---


# Question
Title: Probability that a leaf with 1 will be selected in game tree evaluation
I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar).

```
                          (OR) = 1
                          /  \
                         /    \
  Possible inputs:      1      1
                        0      1
                        1      0

```

You can find detailed description of the problem in this lecture notes or in *Randomized Algorithms*, pg. 29, by Motwani&Raghavan. Basically, given the OR-node and inputs $0$ or $1$ we evaluate the value of the OR-node by inspecting the input values (leaves). For example if the input is $1$ and $0$ then after reading the first value, $1$, we do not need to read the second value, and hence only one read will need to be done. On the other hand, if the input is $0$ and $1$ then after the reading the first value we still need to read the second value (since it may be equal to $1$).

Randomized version of evaluation tosses an unbiased coin and with probability $0.5$ reads the first input value or the second. So, the problem is, given that the OR-gate has output $1$, to compute the expected number of reads.

Both the lecture notes and the book computes it as following

> If the node is to return a $1$, then at least one of the leaves must return a $1$. With probability $1/2$ this leaf will be selected first and only one evaluation will need to be done. The other possibility (also occurring with probability $1/2$) is that both leaves will need to be evaluated. The expected number of evaluations, $E^{OR}\_1$, is given by $$ E^{OR}\_1 = \left(\frac{1}{2} \times 1\right) + \left(\frac{1}{2} \times 2\right) = \frac{3}{2}$$

However, I compute it differently. The probability that a certain leaf is selected is $1/2$, but since we have three possible inputs the probability that the selected leaf has value $0$ is different from the probability that it is $1$. In particular $P(value=1)=2/3$ and $P(value=0)=1/3$. In other words, the probability that a leaf with $1$ will be selected is slightly greater than $1/2$. I'm probably missing something. Could someone explain what is wrong with my approach?

# Answer
When you talk about probabilities, you should first decide what is actually random. Note that there are two possible sources of randomness here, the value of the leaves (i.e. were talking about some distribution over the possible inputs), and the random choice of what leaf to evaluate first (i.e. inner randomness of your algorithm).

When we say our algorithm is randomized, we usually mean the latter. The complexity of such an algorithm is considered with respect to the worst possible input. More formally, saying that the algorithm runs in expected time $T$, means that $T=\max\limits\_{i\in I}\mathbb{E}\left\[T(i)\right\]$, where $I$ is the set of possible inputs and $T(i)$ is the running time on input $i$ (which is a random variable, since we have a coin-tossing algorithm). This is a worst case complexity measure, as the probabilistic analysis is done relative to the worst possible input. Here the worst case (conditioning on the output being $1$) is that exactly one leaf evaluates to $0$, and in this case the expected number of evaluations is indeed $\frac{3}{2}$.

The analysis you described corresponds to the former option, i.e. we are interested in average-case complexity, relative to the uniform distribution over possible inputs (so we actually have two sources of randomness here). In this case, conditioning on the output being $1$, you are right to say that the value of a leaf is $1$ with probability $\frac{2}{3}$, which makes the expected running time $\frac{4}{3}$ (where the expectation is taken over the leaves values and the coin outcome).
> 1 votes

---
Tags: randomized-algorithms, probabilistic-algorithms, game-theory
---


# Question
Title: Number of paths of length N inside a graph
Number of different paths (length N) between vertices x and y inside of a clique Kn or a bipartite graph Kn,n?

I am looking for simple paths. Therefore, in case I have n vertices N can be maximum n-1. For example, if n=4, we have maximum M = 3. For 3 we have 8 different paths, for 2 also 8 and for 1 only 6. I have done the calculations for bigger n as well, but I don't seem to catch a pattern.

# Answer
The following considers the number of paths of any length.

The case of the complete graph $K\_n$ is simpler, so start with that. Fix the endpoints $x$ and $y$ of the path. Starting from the other end, how many ways do you have of choosing the next vertex to traverse to? What about the next one after that, how many choices do you have? Keep going, and you have it. To check your answer, you can see A000522.

For the complete bipartite case $K\_{n,n}$, you need to consider two cases: either $x$ and $y$ are in the same independent set (i.e., on the same side of the graph), or they are not. For these cases, it should be helpful to look at A006041 and A006040.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged
Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ?

It seems obvious by Kruskal's algorithm if the weight of all edges are different, if the weights are same, or some of them are same, how to prove it?

# Answer
There is no necessarily a unique MST for a given G. So reducing an edge might trigger an MST finding algorithm to find a alternative MST. The question is if given MST remains an MST after the change.

Let's make some definitions:

* $e$ is the edge we reduce its weight
* $w(e)$ is the weight of the edge e
* $w(T)$ is the weight of tree T (sum of all edges)

I will prove it by contradiction Let's suppose that after decreasing the weight of of edge $e$ from $w(e)$ to $w'(e)$ T is no more a minimal spanning tree, and $T'$ is a minimal spanning tree.

* First we consider the case where $e \in T'$

After the decrease of w(e)-\> w'(e) the new graph is $G'$. In $G'$ we have:

$w(T') \< w(T)$ by assumption

$w'(e) + w(T' - {e}) \< w'(e) + w(T-{e})$

$w(T'-{e}) \< w(T-{e})$ and that is true both in G and G', since $\\{T'-e\\}$ and $\\{T-{e}\\}$ are same in both graphs

Then subsequently in $G$ we have $w(T'-{e}) \< w(T-{e})$

$w(e) + w(T'-{e}) \< w(e)+ w(T-{e})$

$w(T') \< w(T)$ which means that in G T is not a minimal spanning tree which is not true.

* Now we consider the case where $e \notin T'$

Then in G' $w(T')\< w(T)$ and by the same sequence

$w(T'-{e}) \< w(T-e)$ in both $G$ and $G'$

In $G$ we have consequently $w(T'-{e}) + w(e) \< w(T-{e}) + w(e)$ and if $T'' \equiv \\{T'+e\\}$ then

$w(T'') \< w(T)$ which again contradicts the truth that T is MST in G.
> 2 votes

# Answer
Note that there isn't necessarily a unique MST, so we shouldn't talk about "the" MST of a graph. It's possible that any particular algorithm for finding an MST will come up with a different tree when you change the graph.

Let $G=(V,E,w)$ be the original weighted graph and let $G'=(V,E,w')$ be the graph made by decreasing the weight of edge $e$ by $d\>0$. Because $G$ and $G'$ have the same edges, any spanning tree of one is a spanning tree of the other. Further, an spanning tree $T\subseteq G$ has weight $w'(T) = w(T)-d$ in $G'$ if $e\in T$ and weight $w'(T)=w(T)$ if $e\notin T$. Let $m$ be the weight of an MST in $G$.

If $T$ is a spanning tree of $G$, there are three cases:

1. if it is an MST of $G$ and $e\in T$, then $w'(T)=m-d$;
2. if it is an MST of $G$ and $e\notin T$, then $w'(T)=m\>m-d$, so $T$ is not an MST of $G'$;
3. if it is not an MST of $G$, then $w'(T)\geq w(T)-d \> m-d$, so $T$ is not an MST of $G'$.

Therefore, $T$ is an MST of $G'$ if, and only if, $T$ is an MST of $G$ and $e\in T$.
> 1 votes

# Answer
If the edge weights are same, and you reduce weight of an edge which was already there in the MST, then since the total weight of the *old MST* has even reduced than it's previous value, therefore the MST will remain the same.
But in case you reduce the edge weight of such an edge which was not there in the *old MST*, then the algo will be triggered to find the *new MST*, following which the *new MST* will include the modified edge.
> 0 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree
---


# Question
Title: What is the instruction format for an accumulator machine?
I need to learn about accumulator machines, but there is next to nothing written about them. Computer architecture channels seem to be flooded with general-purpose register ISAs (like MIPS, x86, etc).

I know that accumulator machines only have one register (called the Accumulator Register) that is implicit and not specified in any of the operations. In general, an instruction for an accumulator architecture is supposed to look something like: `add memaddress`.

However, I need to get more specfic. I need to know exactly how many bits are in the various instruction fields (i.e. opcode) for an instruction of an accumulator machine.

I have the following accumulator machine:

* $2^{24}$ words of memory (words are 32-bits wide)
* Fixed format instruction (but how many bits??)
* A 32-bit accumulator register
* An index register X
* Index addressing mode: address field + X when indexing is indicated in the instruction
* Capable of performing a total of 128 operations

The last bullet tells me that the opcode of an instruction would be 7 bits since $2^{7}=128$.

What would the instruction format be for a load/store instruction vs. an arithmetic instruction like `add`? It would help greatly if I knew how many bits the fixed format instruction should be.

# Answer
> 3 votes
Fixed format instruction means that all instructions have the same size of $k$ bits. You ask to learn what $k$ is.

* As you say, the opcode takes 7 bits. So $k \ge 7$
* In order to support memory operations (such as `add mem` or `load mem` etc) we need to be able to give an address (=`mem`). If the dressing mode is direct, and given there are 24 bits address, we have that $k \ge 7+24$.
* But the description of your CPU suggests that there is other addressing modes. Specifically, there is another register, *index register* that allows accessing the memory of \[X+mem\] where X is the content of the indexing register and $mem$ is the 24 bits of address we already counted for. Now, do we need to state X in the instruction itself? - No. we just need to be able to mention the addressing mode is different = a different opcode.
* what about load immeidate (i.e., loading an immediate value directly into the accumulator)?

I don't know.

Your description doesn't give any information or constraints on this issue and there are many different ways to implement the same action. In particular, one can think of "load-byte" instruction which will update the (LSByte of the) accumulator with some fixed value. The current $k$ is enough for such instruction as long as the immediate value is at most 24bits. If you wish to have a way to update the entire 32bits of the accumulator using a single instruction you will have to increase $k$ to support this operation as well.

So unless there are other demands or clarifications to the description you gave, we get that $k \ge 31$.

---
Tags: computer-architecture
---


title: Show that graph is planar or not?

text:
# Question
Title: Show that graph is planar or not?
Show that the following graph is planar or not.

My first assumption is that this graph is not planar, but could not find a reasonable prove (except saying that I tried drawing it in different ways in plane, but couldn't).

We know that a graph is non-planar if it contains either K5 or K3,3 as minors. I tried getting I subdivision of this graph (by contracting some edges), but failed to get a K5 (which I think should be possible).

Any ideas anyone?

# Answer
Contract edges $(C,D)$ and $(G,H)$ - and you'll get $K\_{3,3}$.
> 2 votes

---
Tags: graphs, planar-graphs
---


# Question
Title: Not quite-infinitely expandable human-friendly naming system?
This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line. One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:

* Names must be stable, no-renaming after initial assignment
* Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
* The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting. Starting with 'b' only delays the issue. Same for z on the other end.
    + Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features. This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass. The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information. The set sizes of interest encompass 10^5 -10^7 items.

# Answer
As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme `x_N_M` where `N` and `M` are numbers. Think of this as indexing a point with the *fraction* `N/M`. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point `x_N_M`, name the new point `x_N_2M`. To insert on the right of the rightmost point `x_U_V` name the new point `x_2U_V`. And to insert between adjacent points `x_A_B` and `x_C_D`, name the new point `x_E_F` where `E/F` is the average of `A/B` and `C/D`.
> 3 votes

# Answer
No way.

Let's say you have n possible names. I insert the first point into the list, and you name it. However you name it, either there are only $n/2$ possible names larger or only $n/2$ possible names smaller than the name you chose.

I insert the second point so that it is in the range with fewer names. You name it. Now you have at least one range with only $n/4$ possible names. I insert the third point into the range with fewer possible names, and so on. After inserting k points, there will be a range where you have only $n/2^k$ possible names, and I can make you fail when $k ≥ \log n$.

(I actually ran into an implementation of this in some widely shipping software a few years ago, and users did systematically create this situation where it failed, so I had to add some rather horrid code that would at some point rename everything).
> -1 votes

---
Tags: algorithms, terminology
---


title: Applying BNF rules to themselves?

text:
# Question
Title: Applying BNF rules to themselves?
Say we have some BNF rules for example:

$$A ::= B C$$ $$Dx ::= ExFx$$ $$x ::= y$$

So we might start with $Dx$ and apply rule 2 to get $Ex Fx$ and then apply rule 3 to get $Ey Fy$. But starting with $Dy$ we can't get anything. Unless...

What if we extend the BNF rules to let the rules apply to other rules. Then we could take rule 3 and apply it to rule 2 (interpreted as a string) to get a new rule:

$$Dy ::= EyFy$$

My question is, if we allow such creation of new rules like this. What kind of grammar do we end up with? What is the name of it? Is it equivalent to church lambda calculus?

Using these rules we could express the grammar where the quantity matches the noun and determiner like this:

$$amount ::= singular|plural \\ NP(amount) ::= det(amount)\ \ noun(amount) \\ det(singular) ::= a | one \\ det(plural) ::= some | two | three \\ noun(singular) ::= cat | dog \\ noun(plural) ::= cats| dogs $$

From which we would get $some\ cats$ and $one\ dog$ for example.

# Answer
> 1 votes
There seem to be several levels of such grammars.

If the number of possible $y$ is finite, then each $By$ can be coded as a separate variable (like $B\_y$) and your grammar is basically a "compressed" context-free grammar.

In case of an infinite number of values the $y$ can behave like stacks of symbols (which can be pushed, popped and copied to other variables) a possible formalism is that of indexed grammars.

Even more is possible with attribute grammars, where the attributes can be operated on (you can add for instance the attributes of children). Moreover the values can be passed either up or down the derivation tree (synthesized or inherited).

---
Tags: formal-grammars
---


# Question
Title: Why do modern processors need a runtime stack?
Professor said that modern processor needs runtime stack.

But he didn't explain the reason.

Why is the runtime stack required in the modern processors?

# Answer
I would say that "required" is a bit of strong word. Processors provide hardware support for stacks to help implement the call stack abstraction. Having special instructions to do so can improve performance. Note however that some processors like ARM (except in Thumb mode) do not really have special instruction to do so, the ldm/stm instructions with pre/post inc/dec are flexible enough to do so.
> 6 votes

# Answer
Stacks are quite useful for running software. There is no reason why stacks would *need* to be part of processor. For example, the POWER architecture does not have a call stack as part of the processor. All it has is an architecture that jumps to one address while storing the address following the branch instruction in a special purpose register. ONE special purpose register. No stack.
> 2 votes

# Answer
There are several aspects.

* Processors meant to execute most common languages (such as C) need to implement efficiently stacks for parameters passing and call/return addresses. Some of that stack is usually replaced by registers, for efficiency (using registers for passing parameters to subroutines, link register ...), but when registers are not sufficient, processors typically feature instructions for pushing and popping parameters from the stack (x86 PUSH/POP, auto increment/decrement memory access instructions, ...)
* From a software point of view, the stack is a place in memory. Accessing memory (typically in cache) for all these data transfers can induce latency and power draw. Some advanced CPUs have special memories and bypassing to avoid cache accesses for parameters and return addresses.
> 2 votes

---
Tags: computer-architecture, memory-management
---


title: Efficient bucketing of numbers

text:
# Question
Title: Efficient bucketing of numbers
Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a mapping, so that the difference between those cluster averages and the original numbers is minimal.

Example:
List: \[1, 2, 3, 4\], desired number of buckets: 2
Optimal Solution:
Bucket 0: \[1, 2\], Average: 1.5, Difference: abs(2 - 1.5) + abs(1 - 1.5) = 1
Bucket 1: \[3, 4\], Average: 3.5, Difference: abs(4 - 3.5) + abs(3 - 3.5) = 1
Overall Difference: 2

I know how to create a mapping by brute force, but I would need a more efficient algorithm.

# Answer
Polynomial time is not too difficult.

A "cluster" contains a sequence of 1 or more consecutive numbers from your list. The "badness" of a cluster is defined as the sum of absolute differences between the numbers, and the average of the numbers in the cluster. A sequence of clusters is a list of clusters, containing consecutive numbers from the list starting with the first one. And the "badness" of a sequence of clusters is the sum of badnesses of the individual clusters.

First get a reasonable upper bound for the best clustering to avoid unnecessary work: Just cluster the n numbers into m buckets of equal or almost equal size, then calculate the badness of this sequence of clusters. Call the result B. You might also calculate the badness of a sequence of clusters created by splitting where the largest gaps between consecutive numbers are.

Now for 1 ≤ m' ≤ m, and for 1 ≤ n' ≤ n - (m - m'), calculate the best sequence of m' clusters covering exactly the first n' numbers, and its badness. For m' = 1 that's trivial, because the cluster consists of the numbers 1 to n'. For m' \> 1 it is more difficult: The best clustering using m' clusters to cover 1 to n' consists of the best clustering using m'-1 clusters covering 1 to n'' for some n'' \< n', plus the cluster n''+1 .. n'. You calculate the badness of this for n'' = n'-1 down to m'-1. All these badnesses can be calculated in O (n), so the best badness for m' and n' can be found in O (n).

In total, you find the optimal badness for m clusters covering 1 to n in $O (n^3)$. If you take advantage of the upper bound B found earlier, and consider that any result that leads to a badness \> B can be ignored, you can probably save significant amount of time.

PS. How to find the badness for different clusters each in constant time: Let's say you want to find the badness of a cluster covering the numbers from l to r, for l = r, r-1, r-2, ..., 1. Start with l = r. The sum of items in the cluster is $C = a\_l$. The badness is 0. Let s = l. Then the sum of items at indices \< s is $S = 0$.

Now replace l with l-1. Increase C and S by $a\_l$. The average A of items in the cluster is C / (r - l + 1). As long as $a\_{s-1} ≥ A$ replace s with s-1, and subtract $a\_s$ from S. The badness in the cluster is C - 2S + ((2s - l - n - 1)A (unless I made some mistake).
> 1 votes

---
Tags: optimization, efficiency
---


# Question
Title: Is this a reduction from decision problem to non-decision problem?
Notations :

AUT$(X)$ (where $X$ is a graph) is the group of automorphisms of the graph $X$

$G=\langle A \rangle $ means group $G$ is generated by set $A$.

$G\_{\\{\Delta\\}}$ is the set-wise stabiliser of $\Delta$

---

**STAB**

**Input :** $A \subseteq \text{Sym}(\Omega)$ and $\Delta \subseteq \Omega$

**Find :** Generator of $\langle A \rangle\_{\\{\Delta\\}} = \\{g \in \langle A \rangle \mid \Delta ^ g = \Delta\\}$

**ISO**

**Given :** $X\_1 = (V,E\_1)$ and $X\_2 = (V,E\_2)$

**Find :** Is $X\_1$ isomorphic to $X\_2$?

---

**Claim :** ISO $\le\_{P}$ STAB ( polynomial time reduction )

1. Proof : Take disjoint union $X=X\_1 \cup X\_2$ and note that AUT$(X) \le \text{Sym}(V) =G$
2. $G$ acts on the set $V \choose 2$ i.e. set of all unordered pair of vertices. Clearly $E \le$ $V \choose 2$ and AUT$(X) = G\_{\\{E\\}}$ under the above group action.

> Question : Is this a polynomial time reduction from decision problem to non-decision problem? Please note that It is possible that I may have misunderstood the reduction

Reference : Poly time computation in groups by E.M Luks See Page no 3

# Answer
It seems that the author uses the notation $A\le\_p B$, where $A,B$ can be either function or decision problems, for saying that given an oracle for $B$, one can solve $A$ in polynomial time.

It is then shown that the isomorphism problem is reducible to finding the generators of a setwise stabilizer group (STAB) by showing that it is reducible to finding the generators of the automorphism group (AUT), and that $AUT\le\_p STAB$. The latter is shown by viewing vertex permutations as an operation over vertex pairs, and seeking the generators of the corresponding stabilizing group relative to $E$.
> 2 votes

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


# Question
Title: Find Number of even subarrays $O(n)$ [explanation needed]
So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must be even or even + even or odd + odd. However, I am not sure how this person manages to take into account the fact that these subarrays need to be contiguous and how just tracking the number of cumulative sums that are even/odd as you iterate through the array is good enough

Outlining his algorithm:

* initialize `sum`, `odds` to `0` and `evens` to 1.
* iterate through the array.
    + at each index `i`, do `sum = (sum + A[i]) % 2`
        - if `sum` is 0, increment `evens`, else increment `odds`
* Lastly, return `(evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)`

The algorithm works... I just have no idea how.

# Answer
Let $S\_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x\_i, x\_{i+1}, ..., x\_{j}$ using the expression $S\_j - S\_{i-1}$. This subarray will have even sum only if $S\_{i-1}$ and $S\_j$ are both even or both odd.

With this in mind, we can count how many even and odd $S\_i$ we have and then calculate the number of possible pairs of $S\_i$ and $S\_j$ that yield an even number. So if we have $e$ even $S\_i$ then there are $e \choose 2$ possible pairs. Each pair, corresponds to a different contiguous subarray.

$$ {e \choose 2} = \frac{e!}{(e-2)!2!} = \frac{e * (e-1)}{2} $$

Same holds for the pair of odds.
> 5 votes

---
Tags: algorithms, loops, iteration
---


# Question
Title: Access a tree by level without traversing
I need a tree structure that works roughly like the following

* for each new child I need to match it (with some criteria) with a parent from the previous level only
* when the tree is completely initialized, for each leaf I need to find the first ~~parent~~ *ancestor* that has siblings, i.e. the node just after the branching point.

While the latter is pretty easy with a tipical tree structure, for the first I'd like to just access all nodes of a layer without traversing the whole tree (even with BFS). Does this have a name?

I'm thinking to just keep track of level number for each node and build a second structure to represent levels.

# Answer
> 2 votes
To support the operations mentioned - especially *level-order traversal* (or *walk*) - in time bounded by the depth, you don't need an extra attribute for each node.

For a "semi-static" tree¹, you could use an array of *node*s to store it:
For every *level*, keep the index just beyond.
For every node, keep *parent*, for non-*leaf nodes*, *children* ("first" child), too:
*siblings* are successive nodes with same parent.

For a "dynamic" tree, modify the `[typical] tree structure` keeping children, siblings and optionally parent to support level-order traversal:
Change sibling to *next in same level* \- not a sibling iff different parent.
You may need support for *first in level*, or "the list of nodes in the same level" to be circular to be able to access all of them starting from any-one thereof.

\[1\]: *semi-static tree*: only structural change is addition of nodes.
(The task sketched *may* have another restriction: no node with children will get another child once a different node gets one.)
(or even *static*: `[once] the tree is completely initialized`)

# Answer
> 0 votes
If it’s a complete tree, you could use an array to store it. Accessing parents, siblings, and children would be quite simple and you wouldn’t have to traverse the tree.

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


# Question
Title: How Turing recognizer accepts any string?
I've got a basic doubt for such I'm not getting convicting argument. See,

We say a TM $M$ is Turing recognizer if it accepts a string belonging to the language $L(M)$ & says $yes$ if the string belongs to it. But how it will know when it should stop to arrive at decision? For e.g, suppose there is a string $w$ which belongs to $L$ but it is extremely long so that it will take some 1000 years for TM $M$ to recognize the string. So how TM $M$ will accept the string now & affirm it belongs to the language? If it can't affirm now then why it is even a Turing recognizer.

# Answer
First, Turing machines don't "recognize" strings: they either reject or accept them. "Recognize" is a word we apply to languages, i.e., sets of strings. I think that might be an important point because the way you write suggests that you think that a Turing machine recognizing a string means that it looks at it for a bit and then says, "Oh, yes, I see. That's a string I'll accept if I'm given it as input." That's not what happens at all.

You can think of a Turing machine as a computer program. It's given a string as its input and it starts running. It just follows its instructions and does whatever it's supposed to do. It might eventually stop and accept; it might eventually stop and reject; it might never stop at all. It stops when its programming tells it to stop, just like any other computer program.

A Turing machine recognizes a language $L$ if, for each string $w\in L$, it eventually stops and accepts and, for each string $w\notin L$ it either never stops or it stops and rejects. This isn't any normal English-language use of the word "recognize", which might be what has confused you.

Note that, in general, there's no way to predict whether or not a Turing machine will stop: this is the famous undecidability of the halting problem. So, if you had a real-life physical Turing machine (or any other computer program) and it had been running for an hour and still hasn't finished, there's no general technique that will tell you if it will ever finish. So, if you were using your real-life Turing machine to recognize some language, there would be three possibilities for any input: "The Turing machine ran to completion and said yes", "The Turing machine ran to completion and said no" and "The Turing machine is still running, so I don't know." Mathematically, this isn't a problem – we define the string to be in the language if it would accept if we waited long enough, even though that might not be physically possible.
> 5 votes

# Answer
There is no restriction on how long a recognizer $M$ takes to accept as long as for any $w \in L(M)$, $M$ eventually accepts in some finite amount of time, even if it's horribly inefficient. That is, there is no notion of "affirm now" because computability theory (recognizability, decidability, etc.) doesn't take into consideration how long computations will take and is just interested in "What problems can we solve/verify at all with computers?"

There's a separate question of "What problems can we solve/verify *efficiently*?" This is the field of complexity theory, in which computation time is one possible way of measuring efficiency.
> 2 votes

---
Tags: turing-machines, undecidability, computation-models
---


# Question
Title: Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)
I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different.

All I managed to think of was the example of the knapsack problem, when the sum of all the weights were less than W (max weight). However, in this solution x=x', and I was looking for an example in which they are different.

I am a computer science undergraduate so if you have something I may understand it would be much appreciated.

Thank you

# Answer
> 1 votes
Consider any problem in which there are several different solutions, for example MAX-CLIQUE on a graph in which there are several cliques of maximum size. Any convex combination of optimal solutions in another optimal solution which isn't integral.

If the optimum value of the integer program is the same as its linear programming relaxation, then any optimal solution to the integer program is also an optimal solution of the linear program. The problem is that there could be *other* optimal solutions to the linear program, and an LP solver might find one of them instead of an integral optimal solution. It would be, however, inaccurate to say that the LP and ILP have the same value but not the same solution. Rather, all optimal solutions of the ILP are also optimal solutions of the LP. It's just that the LP has *more* optimal solutions.

---
Tags: algorithms, optimization, linear-programming, integer-programming
---


# Question
Title: number of connected subgraphs of $G$ with at most $ k>0$ vertices
Suppose we have an undirected graph $G=(V,E)$ with $n$ vertices and with max degree of $d\>0$.

I need to prove that number of connected subgraphs of $G$ with at most $n\geq k\>0$ vertices is $M\leq n\cdot d^{2k}$

My approach was by induction.

For $k=1$ it is true

Suppose we want to prove it for $k=n$ .

let's take any vertice $v\in V$ and run $DFS(v)$ So we will get at most $ d\cdot d^{k-1} \le d^k$ connected commponents.

And because we can take any $ v \in V$ we get that the number of connected subgraphs of $G$ with at most $ k\>0$ vertices is $n\cdot d^{k}\< n\cdot d^{2k}$

Now my question is: Am I right with my approach? Is there any other solution for this problem?

I really didn't understand why they gave me this upper bound...

# Answer
> 3 votes
Your argument doesn't really constitute a proof, so it is hard to evaluate it. It's not really clear where the maximum degree comes in. You write the inequality $d \cdot d^{k-1} \leq d^k$, but it isn't clear why we're multiply $d$ by $d^{k-1}$. It's not clear why DFS is relevant here (and why you mention connected components when you're interested in connected sub graphs), and it's not clear how you use the inductive hypothesis.

Here is a different argument which hopefully functions better as a proof. Before we can start the proof, we need to understand what we are trying to prove.

**Definition.** Let $G = (V,E)$ be a graph. An *induced subgraph* of $G$ is a graph of the form $(U, E \cap U \times U)$ for any non-empty $U \subseteq V$. A *connected subgraph* of $G$ is an induced subgraph of $G$ which is a connected graph.

Instead of connecting connected subgraphs directly, it is better to count trees instead. We can do this because every connected graph has a spanning tree. This is embodied in the following lemma.

**Lemma 1.** Let $G$ be a graph on $n$ vertices, and let $1 \leq k \leq n$. The number of connected subgraphs of $G$ having $k$ vertices is at most the number of trees of $k$ vertices contained in $G$. (A tree is *contained* in $G$ if all the edges of the tree are edges of $G$.)

**Proof.** Let $C\_k$ be the set of connected subgraphs of $G$ having $k$ vertices, and let $T\_k$ be the set of trees of $k$ vertices contained in $G$. Since each connected graph has a spanning tree, we can identify a tree of $k$ vertices inside each subgraph in $C\_k$. This gives an *injective* function $f\colon C\_k \to T\_k$: if $f(c) = t$ and $t$ is a tree on the vertex set $U$, then $c$ is the subgraph induced by $U$. Therefore $|C\_k| \leq |T\_k|$. $\quad \square$

We can estimate the number of trees of size $k$ contained in $G$ using an appropriate encoding scheme. The basic idea is to pick a starting vertex inside the tree, describe the vertices adjacent to it in the tree, and so on. Each time we describe the adjacent vertices, we can use the fact that every vertex has at most $d$ neighbors.

**Lemma 2.** Let $G$ be a graph on $n$ vertices of maximum degree $d$. The number of trees of $k$ vertices contained in $G$ is at most $nd^{2k-2}$.

**Proof.** The lemma clearly holds for $k=1$, so suppose that $k \geq 2$. Fix an arbitrary ordering on the vertices of $G$. We describe a procedure that receives as input a tree $T$ and a leaf $v$, and outputs a succinct numerical encoding of $T$. The procedure, *Encode*, uses a subroutine, *Encode-child*, which accepts $T$, a vertex $u \in T$, and another vertex $p$ which is adjacent to $u$ in the tree $T$.

```
Encode(T, v):
  Let u be the unique neighbor of v in T.
  Suppose that u is the i'th smallest neighbor of v in G.
  Output v, i, and run Encode-child(T, u, v).

Encode-child(T, u, p):
  Let u_1, ..., u_m be the neighbors of u in T other than p.
  Output the degree of u in T, i.e., m+1.
  For i = 1, ..., m:
    Suppose that u_i is the j'th smallest neighbor of u in G.
    Output j, and run Encode-child(T, u_i, u).

```

(We assume that $i$ in *Encode* and $j$ in *Encode-child* run from $1$ to $d$.)

What does the output look like? The first item in the sequence is a vertex, which we can identify as a number from $1$ to $n$ (using the order of the vertices of $G$). All other items are numbers from $1$ to $d$. Thinking of $T$ as rooted at the starting leaf $v$, for each non-root vertex we encode both its degree and its index as a child of its parent, for a total of $2(d-1)$ numbers.

We can reconstruct the tree from this encoding. Indeed, it is not difficult to explicitly spell out a decoding procedure which gets as input the sequence of $1+2(d-1)$ numbers, and outputs a tree. It is more challenging to prove that if we encode a tree $T$ and run the decoding procedure, then we get back the tree $T$; however, the challenge is mostly technical rather than conceptual, since intuitively it is clear that the decoding algorithm works. We therefore leave these steps to the curious reader.

We conclude that the encoding procedure described above is an injective mapping from the set of pairs $(T,v)$, where $T$ is a tree of $k$ vertices contained in $G$ and $v$ is a leaf of $T$, to the set of sequences lying in $\[n\] \times \[d\]^{2k-2}$ (where $\[m\] := \\{1,\ldots,m\\}$). Since every tree contains a leaf, this shows that the number of trees is at most $nd^{2k-2}$ (in fact, since every tree contains at least two leaves, we can improve this to $nd^{2k-2}/2$). $\quad\square$

As a conclusion, we can estimate from above the number of trees having *at most* $k$ vertices by $$ \sum\_{\ell=1}^k nd^{2\ell-2} = \frac{nd^{2k}-n}{d^2-1} \leq nd^{2k}. $$ According to Lemma 1, this is also an upper bound on the number of connected subgraphs having $k$ vertices.

Is this bound tight? Probably not. Our encoding scheme is quite wasteful. For example, when encoding $j$ in *Encode-child*, we can use a number from $1$ to $d-1$, since we know that $u\_i \neq p$. This improves the exponent to $d(d-1)$ from $d^2$.

In order to determine the optimal exponent, we can take as our graph $G$ the infinite $d$-ary tree, and count the number of trees of $k$ vertices rooted at a fixed vertex of $G$. This is worked out in this math.se question, which shows that the optimal exponent is $(d-1)^{d-1}/(d-2)^{d-2}$. For example, when $d=3$ the optimal exponent is $4$ rather than $6$ (the well-known asymptotic of Catalan numbers), and when $d=4$ it is $6.75$ rather than $12$.

---
Tags: algorithms, graphs, connected
---


title: What does the $O^*$ notation mean?

text:
# Question
Title: What does the $O^*$ notation mean?
I'm recently reading some papers on the *maximum independent set problem*, all the algorithms' time complexity is donated by $O^\*()$ notation, like $O^\*(1.0836^n)$. One paper says "*the $O^\*$notation suppresses polynomial factors in the input size.*" I'm a little bit confused and couldn't find helpful materials on the Internet. Could you guys clarify it for me? Any related literature or links will be appreciated.

Thanks in advance!

# Answer
Similarly as $O$ notation which "ignores constant factor", $O^\*$ notation "ignores polynomial factor" that is: $f(n) = O^\*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ for $n$ large enough. This is mainly used to compare functions which are growing exponentially, in which case polynomial factors are less important.

This notation is not as standard as $O,o,\Omega, \omega$. Sometimes, this notation or $\tilde{O}$, as observed by @Raphael, is used to ignore polylogarithmic factor when people focus on ptime algorithms.
> 7 votes

# Answer
If you want an authoritative source for the definition, you can see \[1, pp. 1-2\]:

> In this book we use a modified big-O notation that suppresses all polynomially bounded factors. For functions $f$ and $g$ we write $f(n) = O^\*(g(n))$ if $f(n) = O(g(n) \text{poly}(n))$, where $\text{poly}(n)$ is a polynomial. For example, for $f(n) = 2^n n^2$ and $g(n) = 2^n$, $f(n) = O^\*(g(n))$.

---

\[1\] Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms. Springer-Verlag Berlin Heidelberg, 2010. ISSN 1862-4499.
> 5 votes

---
Tags: asymptotics, landau-notation, notation
---


# Question
Title: Why is "accepted by Turing Machine with even number of states" a trivial property?
$$ L = \left\\{ \left\< M \right\>~\middle|~ \small{ \begin{array}{l} L(M)\text{ is recognized by a Turing Machine} \\ \text{having even number of states} \end{array} } \right\\}. $$

Isn't $L$ same as asking if $L\left(M\right)$ is recursively enumerable (RE)? How is it trivial?

I know what it means for a property to be trivial, but I don't understand how the above property is trivial and decidable.

# Answer
> 14 votes
All recognisable languages are recognised by a TM with an even number of states, so the property is trivial.

If a language is recognisable, there is (by definition) a TM that recognises it. If it happens to have an even number of states, then you're done. If it has an odd number of states, add another state that doesn't do anything (or duplicates an existing state), then you have a new TM with an even number of states, and are done.

# Answer
> 7 votes
In the context of Rice's theorem, a class of languages is trivial if either

* it contains all RE languages;
* it contains no RE languages.

In your case, the language is trivial for the first reason, as Luke explains.

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


# Question
Title: Convolutional Neural Network for Insects
I've recently started learning CNN's. I need a CNN that is specialized for insects detection. Dead insects will be put on a piece of paper / container, then images will be taken from a same distance, and are at same pixels.

I am expecting to prepare my own training datasets: \- Thousands of images of a particular insect, let's say a housefly \- Each image contains only one housefly \- Consistent lighting for the photos taken

Then, I will start to train the CNN, save the model and so on. I'm not sure about the following:

1. During operation of the model, will it still be able to detect the housefly if there are other insects in the image? (not covering the housefly of course)
2. If I want my model to recognize housefly only, so the training datasets contain housefly only, true or false?
3. If later I want my model to recognize 2 types of insects, housefly and ant, what type of datasets I need to prepare?
4. I will eventually need to count the amount of houseflies in an image. Can anyone direct me to a correct path towards feasible methods?
5. Does anyone has useful resources that explain on how to determine the suitable amount of convolutional layers (CL) and fully-connected layers (FCL)? The default seems to be 2 CL and 2 FCL, but I am wondering why not more than that?

# Answer
The training set needs to have the same distribution of images as whatever you will be applying your classifier to. So, if you'll be running the classifier on some images of houseflies and some images of other insects (not house-flies), your training set needs to contain both kinds of images. If there are many other kinds of non-housefly images you'll be running the classifier on, the training set should contain images of those same kinds of insects, in a similar frequency to the frequency they'll occur when you use the classifier.

I encourage you to read about object classification vs object recognition vs object detection. See, e.g., https://stackoverflow.com/q/31750076/781723. The simplest kind of classifier takes an image of a single insect and outputs "housefly" or "not housefly". That kind of classifier will be trained on images of single insects -- and should only be expected to work correctly if you apply it to images of a single insect. However, you can also find techniques in the computer vision literature for recognizing the location of the insect in the image and dealing with multiple insects; read about object recognition and detection.

I'm not sure where you got the idea that the default is 2 convolutional layers followed by 2 fully connected layers, but there is no such default and no such rule. I'm not saying that's an unreasonable starting point, but there are no hard-and-fast rules that tell you how many layers to pick. Instead, you'll probably need to try several different possibilities and see how well they work. If you can find papers in the research literature that solve a similar problem, you can sometimes use them as guidance for a good network architecture, but if you're not aware of anything like that, you'll just have to experiment on your own.
> 0 votes

---
Tags: artificial-intelligence, neural-networks, computer-vision
---


title: Asymptotic notation?

text:
# Question
Title: Asymptotic notation?
can someone pls help

How do I prove

> 2⌊lg n⌋ = Θ(2⌈lg n⌉)
>
> 2 ⌈lg n⌉+⌊lg n⌋ = Θ(n2)

I'm not too good at maths. I know,

lim ( n -\> infinty) = f(x)/g(x) if we get a real constant the statement is true.

# Answer
> 1 votes
First, observe that $\lfloor \log N \rfloor \< 2\lceil \log N \rceil$ holds for all $N \geq 2$.
Let $n\_0 = 2$, $c\_1=2$, $f(N)=2\lfloor \log N \rfloor$, $g(N) = 2\lceil \log N \rceil$.
So $$f(N) \leq c\_1 \cdot g(N)$$ holds for all $N \geq n\_0$.
Next, observe that $\lfloor \log N \rfloor \> \frac{1}{2}\lceil \log N \rceil$ is true for all $N \geq 2$.
Let $c\_2 = \frac{1}{2}$.
Thus, $$f(N) \geq c\_2 \cdot g(N)$$ Therefore, $$f(N) \in \Theta(g(N))$$ But the second question, it is obvious that the statement is incorrect, so I'll not be proving here.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Converting nested absolute value into linear programming
I am having trouble writing the following optimization problem as a linear program (LP)

$$\min\_{x \in \mathbb R^2} \big| | x\_{1} - a\_{1} | - | x\_{2} - a\_{2} | \big|$$

where $a \in \mathbb Z^2$ is given. I tried adding the following constraints and replacing objective function to min $U$, but it did not work out.

$$x\_{i}-a\_{i}\le y\_{i}$$

$$a\_{i}-x\_{i}\le y\_{i}$$

$$y\_{1}-y\_{2}\le U\_{}$$

$$y\_{2}-y\_{1}\le U\_{}$$

# Answer
> 2 votes
This sounds like a homework problem, so just hints here.

We'd usually just transform $x\_1$ and $x\_2$ into two new variables, $$ \begin{array}{ccccc} x\_1^{'}~{\equiv}~x\_1-a\_1 & & \text{and} & & x\_2^{'}~{\equiv}~x\_2-a\_2 \end{array} , $$such that the new problem is$$ \min{\left| \begin{array}{c} {\left|x\_1^{'}\right|}-{\left|x\_2^{'}\right|} \end{array} \right|}. $$ Then, the absolute values imply symmetries such that we don't need to consider some parts of the domain.

We may ignore:

1. $x\_1^{'}\<0$, because it's degenerate with $x\_1^{'}\>0$ under $\left|x\_1^{'}\right|$.
2. $x\_2^{'}\<0$, because it's degenerate with $x\_2^{'}\>0$ under $\left|x\_2^{'}\right|$.
3. $\left|x\_1^{'}\right|\<\left|x\_2^{'}\right|$, because it's degenerate with $\left|x\_1^{'}\right|\>\left|x\_2^{'}\right|$ under $\left|\left|x\_1^{'}\right|-\left|x\_2^{'}\right|\right|$.

Typically you can specify these sorts of domains to ignore in terms of constraints.

Then, since the degenerate cases have been removed, the objective function's just$$ \min{ \left( {x\_1^{'}}-{x\_2^{'}} \right) }. $$

---
Tags: optimization, linear-programming
---


# Question
Title: Equivalence between two definitions of Tree width
**Treewidth** :

1) *By chordal graphs* : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$.

2) By tree decomposition :

A tree decomposition of $G = (V , E)$ consists of a tree $T$ (on a different node set from $G$), and a subset $V\_t ⊆ V$ associated with each node $t$ of $T$. (We will call these subsets $V\_t$ the “pieces” of the tree decomposition.) We will sometimes write this as the ordered pair $(T , {V\_t : t ∈ T })$. The tree T and the collection of pieces $\\{V\_t : t ∈ T \\}$ must satisfy the following three properties

**(Node Coverage)** Every node of $G$ belongs to at least one piece $V\_t$.

**(Edge Coverage)** For every edge $e$ of $G$, there is some piece $V\_t$ containing both ends of $e$.

**(Coherence)** Let $t\_1, t\_2,$ and $t\_3$ be three nodes of $T$ such that $t\_2$ lies on the path from $t\_1$ to $t\_3$. Then, if a node $v$ of $G$ belongs to both $V\_{t\_{1}}$ and $V\_{t\_{3}}$, it also belongs to $V\_{t\_2}$

So we define the width of a tree decomposition $(T , {V\_t })$ to be one less than the maximum size of any piece $V\_t$ (over all $t$): $$width (T , {V\_t}) = max |V\_t| − 1$$

Claim 1: If size of largest clique in a chordal decomposition of graph is say $k$ then by tree decomposition we will get tree width $k$

**Proof :** let us assume that largest clique size in chordal completion graph is $k$, so there exist a bag (subset of vertices of graph) that contain the clique ( due to edge coverage ). so we are done.

**claim 2** : If tree width is $k$ by tree decomposition method then by chordal completion method also is $k$

> Question : How to prove the claim 2 ?High level proof will be welcomed.

# Answer
> 2 votes
First, let me note that the claim, as stated in the question, is false: Consider the following graph:

> $\begin{matrix} & & 2& - & 3\\ & \diagup\\ 1 & & | & & |\\ & \diagdown \\ & &4 &-& 5 \end{matrix} $

The complete graph on $5$ vertices is a chordal completion of this graph. However, this graph has treewidth $2$. (A decomposition is $\\{1,2,4\\}$, $\\{2,3,4\\}$, $\\{3,4,5\\}$ )

---

The correct claim is

> The treewidth of $G$ of is the size of the largest clique $\omega(G) - 1$ in a chordal completion *with the minimum largest clique* of the graph $G$.

Now, a proof is as follows: if the treewidth of $G$ by tree decomposition is $k$, then every tree decomposition has a bag of size at least $k$. We use the concept of a *separator graph* from a paper by Parra and Scheffler, in particular the fact that every maximal clique in the separator graph of $G$ is a tree decomposition of $G$ (This can be seen by comparing the definition of tree decompositions with those in the paper)

Then, by Theorem 4.7$^\*$ from the same paper, every minimal chordal completion of $G$ has all the bags of some tree decomposition as a clique. This means every minimal chordal completion of $G$ has a clique of size $k$, so the chordal completion method also gives a tree-width of $k$. $\square$

---

\*: Paraphrased in our notation, Theorem 4.7 states:

> A graph $H$ is a minimal chordal completion of $G$ if and only if $H$ is the graph $G$ with exactly the edges added such that all vertex sets in $\mathcal{S}$ are cliques. Here $\mathcal{S}$ is a maximal clique in the separator graph, which consists of minimal separators of $G$.

I attempted to find a proof using only elementary techniques, but I don't think an easy proof without any deeper theory would be easy to find.

---
Tags: graphs, parameterized-complexity
---


title: What $O$ -symbol supresses?

text:
# Question
Title: What $O$ -symbol supresses?
I am reading this book Asymptotic Methods in Analysis by N. G. de Bruijn. It describes the definition of $O$ symbol as

> A weaker form of suppression of information is given by the Bachmann-Landau O-notation. It does not suppress a function, but only a number. That is to say, it replaces the knowledge of a number with certain properties by the knowledge that such a number exists. The O-notation suppresses much less information than the limit notation, and yet it is easy enough to handle. Assume that we have the following explicit information

I don't under what does this means...

```
...That is to say, it replaces the knowledge of a
number with certain properties by the knowledge that such a
number exists...

```

Can anyone throw light on this passage of definition? It will be a great help. Thanks in Advance!

# Answer
It’s trying to give an intuition and nothing more so, if the passage is not helpful to you, just skip it. Look at the actual definition instead.

Honestly, I think it’s a very bad and unhelpful attempt at giving intuition. In some ways, $\lim$ gives more information; in some ways, it gives less. In some senses, $\lim$ is more specific in that it gives a single value that the function asymptotically approaches, and the notion of limit makes sense approaching points other than $\pm\infty$. If the limit is a real number, then saying $\lim\_{n\to\infty}f(n)=c$ gives more information than $f(n)=O(1)$, which suppresses $c$.

On the other hand, for many functions we're interested in, $\lim\_{n\to\infty}f(n)=\infty$ so $\lim$ gives almost no information. In those cases, big-$O$ allows you to give more information.

I wouldn’t worry about the “suppressing a number” stuff. Saying $3x=O(x)$ suppresses the number three but $3x+1=O(x)$ suppresses two numbers, $3x=O(3x)$ suppresses nothing and $x=O(3x+1)$, er, un-suppresses stuff. Somethingl ike $x=O(x^2)$ is even less clear. It's hard to tell what de Bruijn really intended.
> 3 votes

# Answer
Let's look at the expression $E=x+x^2+x^3+\cdots$, having in mind that $x\rightarrow 0$.Then this number can be written as $x(1+x+x^2+x^3+\cdots)$. So, $E$ has the property that it is a product of $x$ and $(1+x+x^2+x^3+\cdots)$ where the latter is bounded by some constant $C$ for all $x$ small enough. Also, $E= O(x)$, in other words it informs us of the existence of a constant $\tilde{C}$ such that $E\leq \tilde{C}x$ without telling what this constant is.

So, whenever we don't care about the exact value of $\tilde{C}$, then the big $O$ notation gives a more compact, easier to work with, expression.

Example: \begin{align\*} \lim\_{x\rightarrow 0} \frac{\cos(x)-1+\frac{x^2}{2}}{x^4}&=\lim\_{x\rightarrow 0} \frac{\sum\_{n\geq 0}(-1)^n\frac{x^{2n}}{(2n)!}-1+\frac{x^2}{2}}{x^4}\\ &=\lim\_{x\rightarrow 0} \frac{(1-\frac{x^2}{2}+\frac{x^4}{4!}+O(x^6))-1+\frac{x^2}{2}}{x^4}\\ &=\lim\_{x\rightarrow 0} \frac{\frac{x^4}{4!}+O(x^6)}{x^4}\\ &=\lim\_{x\rightarrow 0} \frac{1}{4!}+O(x^2)\\ &=\frac{1}{4!} \end{align\*} The big $O$ notation supresses knowledge in the sense what whenever you have an expression $E$, then $E=O(E)$ is always correct. In other words the big $O$ of $E$ is always possible to be represented by at most the same amount of terms.

It also supresses less information than the limit in the sense that any limit$=c$ can be rewritten as $c+O(a\_n)$ where $a\_n\rightarrow 0$. In other words, the big O notation can not only tell you what the limit is, but also how fast you converge there.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Amount of classes for a semantic segmentation neural network
I am currently working on implementation of semantic segmentation of images neural network, and try to implement one of the already existing solution such as Fully Convolutional Neural Network .

Data that I am using is based on Pascal-Context dataset \[2\], which has additional labeling to original 20-class PASCAL VOC dataset. This results in a dataset with over 450-classes.

***Problem***

Initial 20-classes do not not match classes that I would like to achieve for indoor scenes. Therefore, I have created a short list of 12-classes that I would like to capture, which are in Pascal Context 450-classes dataset.

I managed to convert the data and now trying to start training. I am following this tutorial \[3\] on Matlab, which provides an example of an Image with classes overlay and all pixels colored.

However, in my scenario, I only want to be able to distinguish elements such as tvmonitor, sofa, wall and ignoring all other elements, which might be there. Matlab tutorial states: ***"Areas with no color overlay do not have pixel labels and are not used during training."***\[

As you can see above, I have two classes present in the picture, but I am not sure whether I should also include class Background, which would put overlay on everything that is not within my list of classes, and include that as an additional class in my training or not.

In summary, I am wondering whether Background needs to be provided as an additional class to my list of the classes that I would like to classify or not, even if this background class usually takes majority of each of images. Would that result in everything being classified as background?

**References:**

https://github.com/shelhamer/fcn.berkeleyvision.org

\[2\] https://www.cs.stanford.edu/~roozbeh/pascal-context/

\[3\] https://uk.mathworks.com/help/vision/examples/semantic-segmentation-using-deep-learning.html#d119e321

# Answer
> 0 votes
It's hard to tell whether you are planning on doing image classification or object recognition/detection.

If you're doing image classification, you need each image to have only a single object, and the object needs to be in approximately the same position every time. You train a neural network to output the label (which object it is).

If you're doing object recognition/detection, in the training set it's not enough to have a label for each image. Rather, for each image you should have a list of the objects (labels) and the bounding box of each. Then, you train a neural network to output the label (which object) and location (bounding box) of the object. That requires a different architecture than object classification.

I suggest you spend some time reading up on object recognition/detection and how to do that with a neural network, since it sounds like you might not be familiar with that yet.

As far as the background class: I'm assuming you mean a "none-of-the-above" class. If you are doing image classification and you expect to have some images that aren't of any of the 12 labels, then yes, you should have a 13th label for "none of the above" (i.e., background), and your training set should contain examples of all 13 classes. If you're doing object recognition/detection, that isn't necessary; instead, typically the training set needs to have realistic images that contain zero, one, or more objects, though that might depend on the specific architecture and approach for object recognition/detection you are using.

---
Tags: neural-networks
---


# Question
Title: Algorithm to find number of covering sets
**UPD**: The following problem comes from error correction codes, to be precise -- either maximum-likelihood or belief-propagation decoding when the spectrum of special failing subsets is known (to some extent). Then the failure probability can be formulated as follows.

Let us say the universe set is $\mathcal U = \\{1,2,\dotsc,N\\}$ and we have $M$ subsets of it: $S\_1, S\_2, \dotsc, S\_M$ ($S\_i \subseteq \mathcal U$ for each $i$). Given $W$, find number of $W$-subsets of $\mathcal U$ that cover at least one of $S\_1, S\_2, \dotsc, S\_M$. Mathematically speaking -- find cardinality of the following set: $$ \\{S \subseteq \mathcal U : |S|=W, \exists i \text{ s.t. } S\_i \subseteq S\\} \\,. $$

NB: union of the sets $S\_1, S\_2, \dotsc, S\_M$ is not necessarily $\mathcal U$.

The algorithm does **not** need to be the most efficient, as I just need to find these numbers for my other problem. Hence, say, running time of 1 hour is acceptable. (Well, in the worst case, even 1 day might be okay if there is nothing better). The order of parameters I am interested in: $N \approx 200$, $M \leq 50$, $|S\_i| \leq 8$, $W \leq 30$.

**UPD**: It seems that to find exact answer is very hard, therefore I am also interested in good bounds and/or approximations.

**Example**. $N=4, M=2, S\_1=\\{1,2\\}, S\_2=\\{2,3\\}$.

If $W=1$, the answer is 0: there are no 1-subsets that cover either $S\_1$ or $S\_2$.

If $W=2$, the answer is 2: $S\_1$ and $S\_2$ themselves.

If $W=3$, the answer is 3: $\\{1,2,3\\}$ (covers both $S\_1$ and $S\_2$), $\\{1,2,4\\}$ (covers $S\_1$), $\\{2,3,4\\}$ (covers $S\_2$).

If $W=4$, the answer is 1: $\mathcal U = \\{1,2,3,4\\}$ covers anything.

**UPD**: $M$ is now much smaller.

# Answer
I can suggest two possible methods.

# #SAT

This is closely related to #SAT, and one approach might be to try applying an off-the-shelf #SAT (or approximate-#SAT) solver.

Let $t\_k$ denote the number of $W$-sets that contain $S\_k$ but not any of $S\_1,\dots,S\_{k-1}$, i.e., $t\_k$ is the cardinality of the set

$$\\{S \subseteq \mathcal{U} : |S|=W, S\_k \subseteq S, S\_1 \not\subseteq S, \dots, S\_{k-1} \not\subseteq S\\}.$$

It is easy to see that you want to compute $t\_1+t\_2+\dots+t\_M$, so if we can figure out how to compute $t\_k$, we are done.

How shall we compute $t\_k$? Well, any set $S$ that meets the conditions must cover $S\_k$, so all of the elements of $S\_k$ are in $S$, and the only question is the remaining elements. Set $\mathcal{U}' = \mathcal{U} \setminus S\_k$, $S'\_i = S\_i \setminus S\_k$, and $W' = W-|S\_k|$. Then $t\_k$ is the number of $W'$-sets (over universe $\mathcal{U}'$) that don't cover any of $S'\_1,\dots,S'\_{k-1}$, i.e., the cardinality of the set

$$\\{S' \subseteq \mathcal{U}' : |S'|=W', S'\_1 \not\subseteq S', \dots, S'\_{k-1} \not\subseteq S'\\}.$$

As you stare at this, the condition on $S'$ turns out to be expressible as a boolean formula in CNF form. Let $x\_1,\dots,x\_{N'}$ (where $N'=|\mathcal{U}'|$) be boolean variables; the idea is that $x\_i$ is true iff $i \in S$. Then the condition $S'\_1 \not\subseteq S', \dots, S'\_{k-1} \not\subseteq S'$ is equivalent to a CNF formula on $x\_1,\dots,x\_{N'}$ with $k-1$ clauses and $N'$ variables; each constraint $S'\_i \not\subseteq S'$ induces a clause $\lor\_{j \in S'\_i} \neg x\_j$. Then, $t\_k$ is the number of satisfying assignments of weight $k$ for this formula. You can easily conjoin clauses to this formula that require the assignment to have weight $k$.

In this way, we have reduced the problem of computing $t\_k$ to the problem of counting the number of satisfying assignments of a boolean formula in CNF form. This is exactly the #SAT problem. The problem is known to be hard, but there are off-the-shelf solvers you could try. There are also solvers that yield an approximation to the number, which are worth trying as well. See, e.g., Is there a sometimes-efficient algorithm to solve #SAT? and https://cstheory.stackexchange.com/q/18135/5038.

I don't know whether this will be fast enough for your needs, but it is a possible approach you could consider.

# Inclusion-Exclusion

If $I \subseteq \\{1,2,\dots,M\\}$ is a set of indices, let $u\_I$ denote number of $W$-sets that contain $S\_i$ for each $i \in I$, i.e., the cardinality of the set

$$\\{S \subseteq \mathcal{U} : |S|=W, \forall i \in I . S\_i \subseteq S\\}.$$

You can express the number you want using the inclusion-exclusion formula. In particular, you want to compute

$$u = \sum\_I (-1)^{|I|} \cdot u\_I$$

where $I$ ranges over all non-empty subsets of $\\{1,2,\dots,M\\}$.

Heuristically, we can expect that the larger $I$ is, the smaller $u\_I$ will be, so we can approximate the above sum as follows:

$$u \approx \sum\_{|I| \le 8} (-1)^{|I|} \cdot u\_I.$$

Note that you can compute $u\_I$ easily for any given $I$; in particular,

$$u\_I = {N-|S\_I| \choose W-|S\_I|}$$

where we define $S\_I = \cup\_{i \in U} S\_i$. Now since ${50 \choose 8} \approx 2^{29}$, for your particular parameters it is easy enough to enumerate all index sets $I$ such that $|I|\le 8$ and compute $u\_I$ for each, then use the approximate inclusion-exclusion formula above. You can adjust the parameter 8 to trade off computation time vs quality of the approximation.

The disadvantage is that there is no a priori guarantee on how good the approximation will be -- but this might be useful nonetheless.

It might be possible to refine and improve this approach further. While it's true that on average we expect larger sets $I$ correspond to smaller values of $u\_I$, this isn't necessarily true. Therefore, it's possible that you might get a better approximation by picking a threshold $\tau$ and then using

$$u \approx \sum\_{u\_I \ge \tau} (-1)^{|I|} \cdot u\_I.$$

This requires you to iterate through sets $I$ in order of decreasing $u\_I$, and then stop once you reach the threshold $\tau$. How do you do this? The key insight is that as you add elements to $I$, the value of $u\_I$ gets monotonically smaller. Therefore, you can use breadth-first search to explore which elements to add to the set. You start out with all sets $I$ of size 1 and push them onto a priority queue. The elements of the priority queue are ordered by the value of $u\_I$. In each step, you pop from the priority queue a set $I$ with the largest value of $u\_I$ out of all on the queue; and assuming you haven't processed $I$ before, you add $(-1)^{|I|} \cdot u\_I$ to your running total and then push the sets $I \cup \\{j\\}$ onto the queue for each $j \notin I$.

I suggest trying both variants on inclusion-exclusion to see which gives a better approximation.
> 2 votes

# Answer
Is using the Inclusion-Exclusion-Principle (also called Sieve-formula) too inefficient? According to the principle, if the union of any $L+1$ sets out of $S\_{1}, S\_{2}, \ldots S\_{M}$ is bigger than $W$ then the number you are looking for is $$ \sum\_{n=1}^{L}{(-1)^n \sum\_{i\_{1},\ldots,i\_{n}} \binom{N - |S\_{i\_{1}} \cup \ldots \cup S\_{i\_{n}}|}{W - |S\_{i\_{1}} \cup \ldots \cup S\_{i\_{n}}|}} $$ Edit: The complexity is around $M^{\frac{W}{|S\_{i}|}}$ if the $S\_{i}$s are close to being disjoint and around $2^M$ if the $S\_{i}$s are close to being equal, so probably to big indeed.
> 2 votes

---
Tags: algorithms, coding-theory
---


# Question
Title: Why are Oracle call instances bounded in the definition of FPT Turing reductions?
Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.

Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $F$ and $|x|$ for the size of $x$. For any instance $y$ of $G$, write $l(y)$ for the parameter of $y$. An FPT Turing reduction from $F$ to $G$ is an algorithm with an oracle for $G$ that, for some computable functions $f, g : \mathbb{N} → \mathbb{N}$ and for some constant $c \in \mathbb{N}$, solves any instance $x$ of $F$ in time at most $f (k(x)) · |x|^c$ in such a way that for all oracle queries the instances $y$ of $G$ satisfy $l(y) ≤ g(k(x))$.

If we go through the definition in high-level terms I understand:

* We have an algorithm for $F$ that is allowed to call an oracle for the problem $G$ (this is done in constant time).
* The Algorithm must run in a time that is a computable function of the size of the *parameter* of our instance of $F$ multiplied by a polynomial function of the size of the instance of $F$.

I understand things thus far. However the final restriction that instances of the problem $y$ for which we make an oracle query must satisfy $l(y) ≤ g(k(x))$ for a computable function $g$ I do not understand. What does this say in high-level terms and why is it important? Thanks.

# Answer
As Pål GD mentions, the requirement that $l(y)\leq g(k(x))$ is necessary to obtain reductions with the proper result. In particular, the property 'If $X$ is FPT, and there is an FPT-reduction from $Y$ to $X$ then $Y$ is FPT'.

An example to see why this requirement is necessary is to consider reductions between $k$-Clique and $k$-Vertex cover. Recall that we can construct polynomial time reductions both ways between Clique and Vertex cover (without the parameters), using the fact that if $X\subseteq V$ is a maximum clique in the graph $G$, then $V\setminus X$ is a minimum vertex cover in the complement of $G$.

However, this doesn't give a FPT reduction from $k$-clique to vertex cover: If we try to solve $k$-clique by finding a vertex cover in the complement of $G$, we need to find one of size $k'=|V|-k$. As $k$-vertex cover is FPT, applying the reduction and solving $k$-vertex cover can be done in $O(f(k')\cdot|G|^{O(1)})= O(f(|V|-k)\cdot|G^{O(1)}|)$. So, we don't get an FPT algorithm for $k$-clique from this 'reduction', as the 'non-polynomial' part of the running time depends on $|V|$! In fact, we shouldn't expect $k$-clique to have an FPT reduction to $k$-vertex cover, as $k$-vertex cover is FPT, but $k$-clique is $W\[1\]$-hard.

---

Additionally, I agree with Pål GD that the definition of parameterized Turing reductions you give is a bit difficult to read. I've looked at Flum & Grohe's book and their presentation of this definition is in fact a lot clearer than than one you provide (from a different book/edition?):

> **Definition 2.8.** Let $(Q,\kappa)$ and $(Q' ,\kappa' )$ be parameterized problems over the alphabets $Σ$ and $Σ'$, respectively. An *fpt Turing reduction* from $(Q,\kappa)$ to $(Q' ,\kappa' )$ is an algorithm $\mathbb{A}$ with an oracle to $Q'$ such that:
>
> 1. $\mathbb{A}$ decides $(Q,\kappa)$.
> 2. $\mathbb{A}$ is an fpt-algorithm, that is, there is a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ and a polynomial $p(X)$ such that the running time of $\mathbb{A}$ on input $x \in \Sigma^\*$ is bounded by $f(\kappa(x))\cdot p(|x|)$.
> 3. There is a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for all oracle queries “$y \in Q'$?” posed by $\mathbb{A}$ on input $x$ we have $κ'(y) \leq g(κ(x))$.
> 2 votes

---
Tags: algorithms, complexity-theory, graphs, computability, parameterized-complexity
---


# Question
Title: Closure of Turing-recognizable languages under homomorphism
I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism.

But what's really the difference? Doesn't closure under concatenation imply homomorphism as well? Or perhaps I misunderstand what homomorphism means when talking about Turing-Recognizable languges?

# Answer
> 4 votes
A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L\_1, L\_2 \in \mathcal{L}$ we also have $L\_1 \cdot L\_2 \in \mathcal{L}$.

Here, $A \cdot B = \\{ v \cdot w \mid v \in A, w \in B \\}$.

A class of languages $\mathcal{L}$ is closed against homomorphism if for every language $L \in \mathcal{L}$ and every (word) homomorphism $f$ we also have that $f(L) \in \mathcal{L}$.

Here, $f : \Sigma \to \Sigma^\*$ is lifted to words and sets in the natural way, i.e.

$\qquad\displaystyle f(w) = f(w\_1) \dots f(w\_n)$ for $w = w\_1 \dots w\_n$,

and

$\qquad\displaystyle f(A) = \\{ f(w) \mid w \in A\\}$.

(Note that can make a difference if you require $f : \Sigma \to \Sigma^+$.)

It's easy to see that the two are not the same.

> Let $A = \\{ w \in \\{a, b\\}^\* \mid |w|\_a \in 2\mathbb{N} \\}$. Clearly, $\mathcal{A} = 2^A$ is closed against concatenation but not against homomorphism.
> Let $B = \\{ ww \mid w \in \\{a,b\\}^\* \\}$. Then, $\mathcal{B} = 2^B$ is closed against homomorphism but not against concatenation.
> (mentioned by chi in a comment)
> For completeness, $2^{\Sigma^\*}$ is closed against both, and $\mathcal{A}\cdot\mathcal{B}$ against neither.

---
Tags: formal-languages, computability, closure-properties, semi-decidability
---


# Question
Title: Does XNOR of three variable equals XOR of same three variables
I came across following excerpt:

> $(x'y'+xy)'z'+(x'y'+xy)z=x\oplus y\oplus z$

What I see is left hand side is XNOR of $x,y$ and on right, $z$ and I get XOR of of $x,y$ and $z$ !!! In other word,

> $XNOR(XNOR(x,y),z)=XOR(XOR(x,y),z)$

Somehow I am surprised by the result, as I didnt came across this earlier, no text stated this explicitly and was unexpected. It was unexpected because, I knew some other equalities and inequalities stated below, so was never thought of existence of above equality.

> $XNOR(x,y)=NOT(XOR(x,y))$ $NAND(NAND(x,y),z)\neq AND(AND(x,y),z)$ $NOR(NOR(x,y),z)\neq AND(OR(x,y),z)$

**Q1.** Am I interpreting it correct as XNORs of three variables equals XOR of same three variables?
**Q2.** If yes, can someone shed more light about why such relationship is not true for other gates? Is just that their definition does not permit such relationship? Or Is it beacause ExOR is not basic gate, while AND and OR are?

**PS:** Sorry for naive, possibly stupid question.

The full excerpt:

> $(x'y'+xy)'z'+(x'y'+xy)z$
> $(x'y')'(xy)'z'+x'y'z+xyz$
> $(x+y)(x'+y')z'+x'y'z+xyz$
> $xy'z'+x'yz'+x'y'z+xyz$
> $=x\oplus y\oplus z$

# Answer
XOR is addition modulo 2, and XNOR computes the sum modulo 2 of its inputs and 1. Since $$ (x+y+1)+z+1 \equiv x+y+z \pmod{2}, $$ We see that XORing three variables is the same as XNORing them. The same holds for any *odd* number of variables. When XNORing an even number of variables, you get the negation of their XOR.

Nothing of this sort happens for AND or OR. There isn't any particular reason. You should think of it the other way around: XOR satisfies this surprising property, but other gates do not. XOR is special. It has absolutely nothing to do with AND and OR being "basic gates", whatever that means (mathematically, probably not much).
> 1 votes

---
Tags: boolean-algebra
---


title: Suggestions on Point Cloud fusion

text:
# Question
Title: Suggestions on Point Cloud fusion
I am trying to fuse point clouds into one. These Point clouds are acquired from multiple cameras. Below is the detailed information about setup-

Three Kinect v2 sensors are mounted on tripods in such a way that they are making 120 degree angle from each other in a horizontal plane. Hence one can assume that these Kinect sensors are kept in the circumference of a sphere and pointing towards the center of the sphere. All three Kinect sensors are tilted vertically downwards approximately 30 degrees. The object which is being scanned is kept inside the sphere and visible from all Kinect sensors.

I am able to acquire three point clouds simultaneously from these sensors. Now I want to fuse three clouds to make 1 compete cloud.

What algorithm would I use for this?

# Answer
> 1 votes
You'll probably want to use a method for point cloud registration, also known as point set registration or point cloud alignment. See, e.g., https://en.wikipedia.org/wiki/Point\_set\_registration. RANSAC-like methods may also be useful.

---
Tags: algorithms
---


# Question
Title: How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?
Every function problem has a corresponding decision problem, which is simply the graph of the function problem, according to

https://en.wikipedia.org/wiki/Decision\_problem#Function\_problems

which reads that the time complexity of a function problem and decision problem underlying decision problem "...may not be considered equivalent in some typical models of computation". This seems to be the case with the Greatest Common Divisor decision problem, according to

https://en.wikipedia.org/wiki/Greatest\_common\_divisor#Complexity

So I'd like to use this as an example. I am having a difficult time understanding why the complexity of the GCD function problem is different than its corresponding decision. If the Decision Problem is simply the graph of the Function problem, which is solvable in under quadratic time, how could the decision problem be solvable only in polynomial time?

# Answer
The Wikipedia article is confusing.

There are two things going on here.

Here's first thing: the complexity class P is *defined* to be a class of decision problems. Thus, by definition, no function problem is in P. So it's correct that the decision problem for gcd is in P, but the function problem for gcd is not. Of course, this is pretty trivial. So the first thing is not very interesting -- but it does explain why the Wikipedia article makes that odd comment about the decision problem for gcd being in P.

The second thing is more interesting: is there a difference in the running time between the decision problem and function problem? Sometimes there is. For instance, consider factoring. A function problem is: given a number $t$, factor $t$ into a product of primes. A decision problem is: given a number $t$ and primes $p\_1,\dots,p\_k$, check whether $t = p\_1 \times \dots \times p\_k$. There is no known polynomial-time algorithm for the function problem, but there is an easy polynomial-time algorithm for the decision problem. So, it's apparently easier to check whether the answer is correct than to find the answer. Indeed, for any NP-complete problem, we believe it is easier to check the answer than to compute it, so the function problem appears to be harder than one plausible formulation of the decision problem. (For that reason, when we turn function problems into decision problems, we usually do it in a different way than the one you mention.)

What about for gcd? The function problem is: given $x,y$, compute $\gcd(x,y)$. The fastest algorithm known for this takes $O(T(n) \log n)$ time, where $n$ is the number of bits of $x,y$ and $T(n)$ is the time to multiply two $n$-bit numbers. It is an open question whether this can be done faster than that, or exactly how fast this is. A plausible decision problem is: given $x,y,d$, check whether $\gcd(x,y)=d$. Here it is not known what the fastest possible running time is. You can check whether $d$ divides $x$ and $y$ in $O(T(n))$ time, so you can check whether $d | \gcd(x,y)$ in $O(T(n))$ time -- faster than we know how to compute the gcd in the first place. But I don't know of any algorithm to turn this into a way to check whether $d = \gcd(x,y)$ asymptotically faster than computing the gcd from scratch in the first place. So we just don't know in this case whether the decision problem can be solved faster than the function problem.
> 1 votes

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