# Question
Title: A closed form expression for # of inputs of a binary tree and its number of nodes
Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes?

In case that the binary tree is a full tree, it is easy to find the number of input pins. In this case we will have $2^{H-1}$ nodes at the last level of the tree ($H$ is the height of the tree). Thus, the # of input pins will be $2^H$ because each node has 2 input pins.

How can we generalize this for a binary tree which is not a full trees?

# Answer
> 0 votes
There is a known expression linking the number of input pins and the number of nodes in a binary tree. It does not use the height of the tree.

For any binary tree the number of leaves equals the number of internal nodes plus one.

We can prove this by induction. *Basis*. A tree with one node has two leaves. *Induction step*. Whenever I replace a leaf by a new node, both the number of nodes and the number of leaves increase by one (we lose a leaf, and get two new leaves in return).

---
Tags: trees, dynamic-programming, binary-trees
---


# Question
Title: Proof that bin packing is strongly NP-complete?
Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?

# Answer
Such a proof is outlined in Garey and Johnson, 'Strong' NP-Completeness Results: Motivation, Examples, and Implications, mentioned in the Wikipedia article. The proof is by a straightforward reduction from 3-PARTITION. The problem 3-PARTITION one is given $3n$ numbers, and the task is to decide whether they can be split into triples of equal sum. There is a straightforward reduction from 3-PARTITION to BIN-PACKING: if the sum of the numbers is $nB$, ask whether the $3n$ numbers can be packed into $n$ bins of size $B$.

The strong NP-completeness of 3-PARTITION was proved in a different paper of Garey and Johnson, Complexity results for multiprocessor scheduling under resource constraints. The proof is quite long, ultimately a reduction from 3DM (3-dimensional matching), but going through many intermediate steps.
> 7 votes

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


# Question
Title: Does P=NP imply polynomial solutions to #P?
Is it true that $\\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\\#P$-complete, so even if P=NP it may not necessarily be true. My confusion is over how we write the answer to a $\\#P$-complete problem since it may be exponential in the size of the input (for example up to $2^n$ truth assignments to a SAT instance on $n$ variables). Therefore, I cannot understand how, even if we find a fast way for computing something like the permanent of a matrix, we could still expect to write the answer in polynomial time. Am I missing something about the definition of $\\#P$?

# Answer
> 13 votes
Your confusion is that the class **#P** only asks you to *count* the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of satisfying assignments to a formula of $n$ variables, you need $n$ bits, because there are at most $2^n$ solutions (i.e. in the case of a tautology). Another example: the number of isomorphisms between two graphs is at most $n!$, which requires $\log(n!)\approx n\cdot \log(n)$ bits to write down. All these number of bits are polynomial in the size of the input

**#P** can be solved in polynomial time if and only if **P=PP**. This is a stronger statement than **P=NP**, because **P=PP** implies **P=NP** (and hence, it is less likely). If **P=NP**, then all **#P** problems can be approximated to within a constant factor by a deterministic algorithm.

# Answer
> 2 votes
**P$\\,=\\,$NP** does not imply that **P$\\,=\\,$#P** (or, more properly, **FP$\\,=\\,$#P**). We already know that there are decision problems in **P** whose counting versions are **#P**-complete, such as perfect matchings.

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


# Question
Title: How many edges before a random graph is connected?
Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for a given $n\in\mathbb N$?

## Specifics:

When we add an edge to the graph $G$, any edge that can exist would be equally likely to be added. We can not add the same edge twice, so when $k=\frac{n^2+n}2$ (the number of possible edges in a graph with $n$ verticies), then $f(k)=1$.

Definition for connected may be found on wikipedia.

# Answer
A classical result of Erdős and Rényi states that if $k = \frac{n}{2} (\log n + c)$, then as $n\to\infty$, the probability that the graph is connected tends to $e^{-e^{-c}}$. You can find the proof in any textbook on random graphs.
> 3 votes

---
Tags: random-graphs
---


title: Approximate time to execute algorithm

text:
# Question
Title: Approximate time to execute algorithm
Suppose a comparison between elements takes 1ms to execute. If an algorithm is O(logN), for example, deletion in an AVL Tree, and the AVL Tree contains 100 elements. Does that mean that the time to execute the algorithm would be log100 * 1ms? Do I need more information to calculate this or is this enough?

# Answer
If an algorithm is $O(\log n)$, then you can conclude absolutely nothing about the running time of the algorithm. This is due to many factors, one of which is that $O(\log n)$ hides an arbitrary constant factor: both $\log n$ and $100\log n$ are $O(\log n)$ (not to mention functions such as $10^6\log\log n + 10^{15}$). There are also other reasons, but this reason is probably enough.
> 1 votes

---
Tags: algorithms, time-complexity
---


title: Software to hardware

text:
# Question
Title: Software to hardware
I am a layman in computer science. How do the command we input in a computer, which is a software component, changes into a hardware component. For example, if I want to play a song, I will just click the song and the audio starts to emit from the speakers. So how does in general these things happen?

# Answer
> 1 votes
First you move your mouse. Most mice now in days works using a laser, the laser is able to tell it's moving over a surface, inside the mouse the data from the laser is being turned into digital signals, that are then sent through the cord or through Bluetooth or whatever system you use to the computer. The computer meanwhile is expecting to get signals like these, it's constantly checking to see if it's gotten a new signal from the mouse, and when it does it knows how to interpret those signals to move the pointer on your screen.

Now you click on an icon, and that is then the mouse sending a different signal for a click or double click, the computer registers the click and then figures out what do to handle the click, since your mouse was above an icon, lets say a music file you have sitting on your desktop, it knows to try and open or run that file.

To determine what exactly it means to open or run the file it may look at a few different things, you may have some settings for that file that you've set which tell it how to open, but more generally it goes based on the extension. Let's say it's a `.mp3` file, well you probably have a default music player app, and the computer knows to open that app and gives it some information about the file you clicked, I'm not sure on the format, but it probably gives it the name and location of the file you clicked on. The music player app now takes that file and assuming it's correctly formatted as an `mp3` then it will know how to read the data in the file, and it will parse through that data and start to send messages back to the operating system telling it to output sound.

The OS now will send data about what sound needs to be played to whatever the default or current audio device you have, lets say they are speakers. The speakers will receive these signals and know what sort of sounds to put out, and then they have components in them that can vibrate in different ways, and they are told how to vibrate by the singles that were sent and thus sound is emitted.

---
Tags: software-engineering
---


# Question
Title: Proving laws of take and drop functions using structural induction on lists
I'm trying to prove the following laws using structural induction on (finite) lists:

```
take m (drop n xs) = drop n (take (m + n) xs)
drop m (drop n xs) = drop (m + n) xs

```

for all `m`, `n` and every finite list `xs` (code snippets are in Haskell). I'm not sure how to tackle it though, more specifically: afaik when using induction on intervals, the first induction step is for `m > n` and the second for `m ≤ n`. Now in this case the law must also be valid for all finite lists, does that mean the proof involves prooving all the following?

* case `m > n`: `[]` and `(x:xs)`, and in the latter `m + n > length xs` and `m + n ≤ length xs`
* case `m ≤ n`: `[]` and `(x:xs)`, and in the latter `m + n > length xs` and `m + n ≤ length xs`

If yes I can update my question and show exactly where I'm stuck.

(Please don't post the entire solution, I'd just like to have some pointers. Thanks!)

*UPDATE*

If `[]` denotes the empty list and `(x:xs)` a list with at least one element (`x` is the head of the list and `xs` its tail), possible definitions of `take` and `drop` are:

```
take n [] = []
take 0 xs = []
take n (x:xs) = x : take (n - 1) xs

```

if `n` is greater than `l`, where `l` is the length of the input list, then `take` returns a list of length `l`

```
drop n [] = []
drop 0 xs = xs
drop n (x:xs) = drop (n - 1) xs

```

if `n` is greater than `l`, where `l` is the length of the input list, then `drop` returns the empty list

# Answer
> 1 votes
You can prove the second law by induction on `n`:

* Base case:

`drop m (drop 0 xs) = drop m xs` (definition of `drop`, base case)

`= drop (m + 0) xs` (since `m + 0 = m`)

* Inductive step:

We have to consider two cases: when the input list is empty, and when it's not empty. When it's empty, we have

`drop m (drop n []) = drop m [] = [] = drop (m + n) []` (definition of `drop`, base case)

When the input list is not empty, we have

`drop (m + n) (x:xs) = drop (m + n - 1) xs` (definition of `drop`, inductive case)

`= drop m (drop (n - 1) xs)` (inductive hypothesis)

`= drop m (drop n (x:xs))` (definition of `drop`, inductive case)

I imagine that the first law is not much more difficult. Try to prove it by induction on `n`, and if it doesn't work, try induction on `m`. One of them will probably work.

---
Tags: proof-techniques, induction
---


# Question
Title: Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$
In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^\*\_i = \gamma\_i(1)$. But $\gamma\_i(t)$ is the probability of being in state ${\displaystyle i}$ at time ${\displaystyle t}$ given the observed sequence ${\displaystyle Y}$ and the parameters ${\displaystyle \theta }$ (quote wiki)

So, then why does this probability not need to be normalised like so? :

$$\pi^\*\_i = \frac{\gamma\_i(1)}{\sum\_{j = 1}^N \gamma\_j(1)}$$

After all normalizing is what is done for the reestimate of the transition probabilities and the emission probabilities too.

# Answer
It is defined to be a probability. A probability is by definition already normalized. In particular, we are guaranteed that

$$\sum\_{j=1}^N \gamma\_j(1) = 1,$$

as there are only $N$ possibilities for the state that you're in at time $1$, and these $N$ cases have no overlap.
> 4 votes

---
Tags: machine-learning, probability-theory, probabilistic-algorithms, hidden-markov-models
---


# Question
Title: log(n) complexity. Difficulty understanding example
So, I am revisiting complexity analysis.

Here's the example: the instructor reduced an algorithm to:

n\*(1 + 1/2 + 1/3 + ... + 1/n), and I can't seem to grasp why the part in parentheses is log(n).

# Answer
Do you know the Harmonic series (wiki)?

$$1 + \frac{1}{2} + \cdots + \frac{1}{n} = 1 + \sum\_{i=2}^{n} \frac{1}{i} \le 1 + \int\_{1}^{n} \frac{1}{x} \text{d}x = 1 + \ln n = \Theta(\log n).$$

Similarly, we also have $$1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum\_{i=1}^{n} \frac{1}{i} \ge \int\_{1}^{n+1} \frac{1}{x} \text{d}x = \ln (n+1) = \Theta(\log n).$$

---

The formula above follows from

$$\int\_{a}^{b+1} f(x) \text{d}x \le \sum\_{i=a}^{b} f(i) \le \int\_{a-1}^{b} f(x) \text{d}x$$

when $f(x)$ is non-increasing.
> 20 votes

# Answer
$1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}= \sum\_{i=1}^{n} \frac{1}{i}=H\_n$ where $H\_n$ is the $n^{th}$ harmonic number.

So inside the parenthesis you don't have $\log(n)$.

But, what can be proved is that:

* $\ln(n+1) \< H\_n \le 1 + \ln(n)$
* $H\_{n+1} - \ln(n+1) \< H\_n - \ln(n)$

so that the $H\_n - \ln(n) \ge 0$ and the difference **decreases**.

**Example**:

\begin{align\*} H\_1 - \ln(1) &= 1\\ H\_2 - \ln(2) &= 0.80...\\ H\_3 - \ln(3) &= 0.73...\\ &\\;\\;\vdots\\ H\_{10} - \ln(10) &= 0.62..\\ &\\;\\;\vdots\\ H\_{100} - \ln(100) &= 0.58... \end{align\*}

The limit tends to a constant called the Euler-Mascheroni constant $$\lim\_{n\to\infty} (H\_n - \ln(n))=0.577...$$

So, to conclude, $H\_n = \Theta(\log n)$.
> 8 votes

# Answer
"All he said was 'this is the definition of $\log n$'". That's sad. Because it's wrong, and because your instructor should be helping you, and this isn't helpful.

If your maths isn't very strong, here's a simpler method to see what's going on:

You have a sum $1 + 1/2 + 1/3 + \dots + 1/n$. That's one term $= 1$, one term $= 1/2$. Then two terms $1/3$ and $1/4$, both $\geq 1/4$, so their total is $\geq 1/2$. Then four terms $1/5$, $1/6$, $1/7$, $1/8$, all four $\geq 1/8$, so their total is $\geq 1/2$. Then eight terms up to $1/16$ add up with a total $\geq 1/2$, and so on. If you do the sum up to $n = 2^k$ then you added the number $1$, and $k$ times the number $1/2$. The sum is $\geq 1 + k/2$.

On the other hand, $1/3$ and $1/4$ are $\leq 1/2$ so they add to a total $\leq1$. $1/5$ to $1/8$ are each $\leq 1/4$, so they add to a total $\leq 1$. The terms $1/9$ to $1/16$ are $\leq 1/8$, so their total is $\leq 1$. If you sum everything up to $n = 2^k$, the total sum is $\leq 1/2 + k$.

So the sum up to $n = 2^k$ is between $1 + k/2$ and $1/2 + k$, or between $1 + (\log\_2 n) / 2$ and $1/2 + \log\_2 n$, which is $\Theta (\log n)$.
> 1 votes

# Answer
Using Stolz-Cesàro:

$$ \lim\_{n\to\infty}\frac{1 + 1/2 + \cdots + 1/n}{\log n} = \lim\_{n\to\infty}\frac{1/(n + 1)}{\log(n + 1) - \log n} = \lim\_{n\to\infty}\frac{1/(n + 1)}{\log(1 + 1/n)} = \lim\_{n\to\infty}\frac{1/(n + 1)}{1/n} = 1, $$ so $H\_n = \Theta(\log n)$.
> 0 votes

# Answer
The important part to understand is that the time complexity of an algorithm (when expressed using big O notation) **excludes coefficients and lower order terms**.

Other answers have shown where the `log(n)` term comes from, but your instructor is absolutely correct to leave out the constant part of the expression when stating the time complexity of the algorithm.
> 0 votes

---
Tags: algorithms, time-complexity
---


title: Finding the language accepted by a DFA

text:
# Question
Title: Finding the language accepted by a DFA
I've got this DFA and I need to figure out and describe the language that it accepts. I figured that $M= \\{\\{1,2,3,4,5,6\\}, \\{a,b\\},1, \\{1,5\\}, \delta\\}$
Now I don't know how to move forward.

# Answer
> 0 votes
Given a DFA D, $\ L(D)=\\{w \in \Sigma^\* | \ \hat{\delta}(q\_0,w) \in F \\}$ where $\hat{\delta}(q,w)$ is the extended transition function.

In your case:

$L(M)=\\{w \in (a+b)^\* | \ \hat{\delta}(1,w) \in \\{1,5\\} \\}$

In other words your language is the set of all the string such that you can go from the initial state to a final state.

In your case there are just 2 strings for which you can go from State $1$ to a final state.

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


# Question
Title: how to design a Turing machine that could count Unary?
am trying to figure out how to design a unary number Turing Machine. That after reading all the unary number in the tape it would give out a decimal value. how can i approach this problem?

# Answer
> 1 votes
Here is a Turing machine that should accomplish what you are looking for, I don't know how to teach someone how to make it, but I can explain how I made this. Note there is an error, the instruction from $S$ to $H$ of $(0,s,0)$ should be $(\lambda,s,0)$. Also I used $\lambda$ to represent the null character or the empty spot.

The starting state for the machine is $S$ and the halt state is $H$. First I said that if the tape is empty, then we simply write a $1$ and halt. If there is a $1$ then we will put a $\*$ there and write a $1$ to the spot before, then we start our loop if you will.

The loop starts with the state $\text{go to end}$, from there we go to the end of the unary number. When know we got there when we see a $\lambda$ and then we know we've gone one to far. At this point we would move one left (to the last digit in the unary number) and to the state $\text{check if done}$, and here we have an end condition. If we currently see a $\*$ then we have hit the end as there are no more unary numbers, and we move to the $\text{done}$, from where we move to the beginning of our decimal number and then halt.

If we don't see a $\*$ then we would have to see a $1$ as it's a unary number. We delete that number and then go back to the beginning of the unary number (this is done in state $\text{go to start}$. From there we add 1 to the decimal number that is to the left of the $\*$, This is done just using state $\text{add 1 from right}$, followed by $\text{go to \*}$ which puts us back to the $\*$ that separates the unary number from the decimal number. At this point we go to state $\text{go to end}$ again and the machine is already complete.

Here is the entire rules for the machine typed up with $S$ and $H$ as the start and halt state respectively. The rest of the states will be given letters arbitrarily. The form of the following is `(start state, value read, head movement, end state, value write)`. (head movement: `l` is left, `s` is stay, `r` is right). Also `\` will be our empty, and represents $\lambda$

```
(S,0,s,H,0)
(S,1,l,A,*)
(A,\,r,B,1)
(B,1,r,B,1)
(B,*,r,B,1)
(B,\,l,D,\)
(D,*,l,C,\)
(C,0,l,C,0)
(C,1,l,C,1)
(C,2,l,C,2)
(C,3,l,C,3)
(C,4,l,C,4)
(C,5,l,C,5)
(C,6,l,C,6)
(C,7,l,C,7)
(C,8,l,C,8)
(C,9,l,C,9)
(C,0,l,C,0)
(C,\,r,H,\)
(D,1,l,E,\)
(E,1,l,E,1)
(E,*,l,F,*)
(F,9,l,F,0)
(F,0,r,G,1)
(F,1,r,G,2)
(F,2,r,G,3)
(F,3,r,G,4)
(F,4,r,G,5)
(F,5,r,G,6)
(F,6,r,G,7)
(F,7,r,G,8)
(F,8,r,G,9)
(F,\,l,G,1)
(G,0,r,G,0)
(G,1,r,G,1)
(G,2,r,G,2)
(G,3,r,G,3)
(G,4,r,G,4)
(G,5,r,G,5)
(G,6,r,G,6)
(G,7,r,G,7)
(G,8,r,G,8)
(G,9,r,G,9)
(G,*,r,B,*)

```

---
Tags: turing-machines, automata
---


title: How many gates until Turing Complete

text:
# Question
Title: How many gates until Turing Complete
A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone have to put before it can be expected that the "computer" is Turing Complete?

# Answer
A single finite machine is never Turing-complete. (Such a machine with $n$ bits of internal memory has only $2^n$ states, so it can be modelled as a DFA with at most $2^n$ states.) So, strictly speaking, it only makes sense to even ask about Turing-completeness when you have a machine model that is unbounded, or when you have an infinite family of machines $M\_1,M\_2,\dots$ of increasing size.

For similar reasons, strictly speaking, the computer sitting on my desk is not Turing-complete, either, because it is finite. Nonetheless, it is useful to think of it as Turing-complete, in a looser sense: there is a natural abstraction of my machine where we disregard its finiteness (consider an abstract model where instead of being limited to 1TB of disk space, it has an unlimited amount of disk space). For many purposes, the differences between my actual finite machine and the abstract, idealized machine with unlimited storage isn't very important. But for your question, the difference can't be ignored, and to make your question well-specified, you'd have to think about how you plan to address this important distinction.

If you're interested in computing models that are somehow "simple"/"small" yet Turing-complete, you might be interested in rule 110, tag systems, and the lambda calculus. See also Universal binary rewriting system. Do some searches on these terms on this site (and elsewhere) to learn more about these topics.
> 7 votes

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Time complexity of matrix multiplication in Big-Align
I am reading the following paper:

Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).

I'd like to understand one of the paper's claims about the running time of their algorithm. Their algorithm uses matrix multiplication as follows:

>

where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ **diagonal** matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above. $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.

The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.

How can we compute $\bf P$ in $O(nd^2)$ time? I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time. I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,

> 1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.
>
> 2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
>
> 3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.
>
> 4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.
>
> 5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.

I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?

# Answer
> 3 votes
D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity.

The paper is about network alignment, where $\bf A$ and $\bf B$ are adjacency matrices for bipartite networks, and $\bf P$ can be viewed as a matrix indicating alignment. $\bf P$ is dependent on $\bf B$ based on the equation. So it is better to view $\bf P$ as a function $\bf P(B)$ of $\bf B$, and $\bf X$ and $\bf Y$ are representation of function $\bf P$.

I believe the paper means first "pre"-compute $\bf X$ and $\bf Y$, store the results somewhere, and then for any given $\bf B$, they can compute the value of $\bf P$ given $\bf B$ using the pre-computed $\bf X,Y$.

The problem is, eventually one has to compute $\bf P (B)$ in order to determine the alignment result between $\bf A$ and $\bf B$. The complexity of that computation is $O(n^2d)$, since $\bf B$ is $n\times d$ and $\bf X$ is $d\times n$, and there is no guaranteed zero rows or columns in $\bf B$ or $\bf X$ to reduce computation.

Thus, the computation of $\bf P(B)$ requires indeed quadratic time. It is just that computation of the function $\bf P$ is $O(d^2n)$.

# Answer
> 2 votes
The paper is correct, but you need to keep reading to understand why. Often when something in a paper doesn't make sense, it makes sense to keep reading the next few paragraphs, as sometimes the authors will follow a non-obvious claim with information to help you understand why the claim is true.

The subtle point here has to do with the difference between computing a matrix explicitly (i.e., outputting all of its elements) vs implicitly (i.e., computing some compressed form of the matrix where you don't store all elements explicitly, but where the compressed form is good enough for everything you plan to do with the matrix).

$\bf P$ is a $n \times n$ matrix. Therefore you can't compute it explicitly in $O(nd^2)$ time. Merely outputting all of the entries of the matrix $\bf P$ requires $\Omega(n^2)$ time. In other words, there is no algorithm to output the matrix $\bf P$ explicitly in $O(n d^2)$ time.

This doesn't rule out the possibility of an algorithm that outputs some implicit representation of $\bf P$. Indeed, the very next paragraph in the paper discusses representing $\bf P$ implicitly in compressed form as the product of two low-rank matrices. You can view equation (5) as already computing $\bf P$ in such a form. In particular, if we view $\bf 1 \cdot Y$ as the "simpler terms" to be omitted, $\bf B \cdot \bf X$ is already a representation of that matrix as a product of two low-rank matrices: $\bf B$ is a $n \times d$ matrix and $X$ is a $d \times n$ matrix, so both have rank at most $d$.

In that sense, computing $\bf P$ in such a form (omitting "simpler terms") amounts to computing $\bf B$ and computing $\bf X$. That can be done in $O(nd^2)$ time, as follows. $\bf B$ is given, so there's nothing to do to compute it. So, all that remains it to compute $\bf X = A^T U S^{-2} U^T$ in $O(n d^2)$ time, given $\bf A,U,S$. This can be done in three steps:

1. Compute $\bf U S^{-2}$. This can be done in $O(nd^2)$ time, by using the special structure of $\bf S$. In particular, you can view $\bf U S^{-2}$ as a $n \times d$ matrix (strictly speaking, it is a $n \times n$ matrix, but the last $n-d$ columns are all zero, so we're only going to compute its first $d$ columns).
2. Compute $\bf A^T U S^{-2}$. This can be done in $O(nd^2)$ time, as you are basically multiplying a $d \times n$ matrix ($\bf A^T$) by a $n \times d$ matrix ($\bf U S^{-2}$). The result is basically a $d \times d$ matrix (strictly speaking, it is a $d \times n$ matrix, but the last $n-d$ columns are all zero, so we only need to compute its first $d$ columns).
3. Compute $\bf A^T U S^{-2} U^T$. This can also be done in $O(nd^2)$ time, as you are basically multiplying a $d \times d$ matrix by a $d \times n$ matrix. The result is a $d \times n$ matrix. (Strictly speaking, $\bf A^T U S^{-2}$ is a $d \times n$ matrix and $\bf U^T$ is a $n \times n$ matrix, but the last $n-d$ columns of $\bf A^T U S^{-2}$ are all zero, so the last $n-d$ rows of $\bf U^T$ don't matter, and we can view this as multiplying a $d \times d$ matrix by a $d \times n$ matrix.)

Each step can be completed in $O(nd^2)$ time, so the whole computation can be done in $O(nd^2)$ time.

---
Tags: time-complexity, runtime-analysis, linear-algebra
---


# Question
Title: counteracting numerical instability in HMM training
I am training a HMM with Baum Welch for part of speech tagging. I am training the model with 79 hidden variables (part of speech tags) and 80,000 observed variables (words). I am working with log probabilities. To give you an idea, I defined the necessary arithmetic operations like so:

```
struct log_policy
{
    template<class T, class U>
    static auto mul(const T t1, const U t2)
    {
        return t1 + t2;
    }

    template<class T, class U>
    static auto div(const T t1, const U t2)
    {
        return t1 - t2;
    }

    template<class T, class U>
    static auto add(const T t1, const U t2)
    {
        return log(exp(t1) + exp(t2));
    }

    template<class T, class U>
    static auto sub(const T t1, const U t2)
    {
        return log(exp(t1) - exp(t2));
    }

    template<class T>
    static auto linear_scale(const T t)
    {
        return exp(t);
    }

    template<class T>
    static auto native_scale(const T t)
    {
        return log(t);
    }

    template<class T>
    constexpr static auto make_additive_neutral_element()
    {
        return -1 * std::numeric_limits<T>::infinity();
    }

    template<class T>
    constexpr static auto make_multiplicative_neutral_element()
    {
        return static_cast<T>(0);
    }

    template<class T>
    constexpr static auto make_annihilator()
    {
        return -1 * std::numeric_limits<T>::infinity();
    }
};

```

Anyway, besides working with log probabilities I still get numeric instability for longer training sentences. This is primarily due to the size of the set of observed variables. As the size is 80,000, each state in the HMM has an average emission probability of 1/80,000 for each word. I was wondering how to counteract this? Would reducing the number of emissions be a valid option?

To further illustrate: This is a section of a debug representation of the forward trellis after doing the forward algorithm on a training sequence. As you can see the right most fifth of the table is full of `-inf`, and they all appear at the same time... which I don't quite know why yet.

(The format for a cell is `<hidden variable human readable name> <hidden variable internal name and state ID> <probabiliy of cell> <backpointer>`)

```
($$(      (0)   :  -40.3203,  -1)  ($$(      (0)   :  -78.1552,  -1)  ($$(      (0)   :  -115.029,  -1)  ($$(      (0)   :  -151.865,  -1)  ($$(      (0)   :  -188.706,  -1)  ($$(      (0)   :  -225.547,  -1)  ($$(      (0)   :  -262.389,  -1)  ($$(      (0)   :  -299.23,   -1)  ($$(      (0)   :  -336.071,  -1)  ($$(      (0)   :  -372.913,  -1)  ($$(      (0)   :  -409.754,  -1)  ($$(      (0)   :  -446.596,  -1)  ($$(      (0)   :  -483.437,  -1)  ($$(      (0)   :  -520.278,  -1)  ($$(      (0)   :  -557.12,   -1)  ($$(      (0)   :  -593.961,  -1)  ($$(      (0)   :  -630.802,  -1)  ($$(      (0)   :  -667.644,  -1)  ($$(      (0)   :  -704.485,  -1)  ($$(      (0)   :  -741.955,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)  ($$(      (0)   :  -inf,  -1)
($$,      (1)   :  -43.2152,  -1)  ($$,      (1)   :  -77.935,   -1)  ($$,      (1)   :  -114.923,  -1)  ($$,      (1)   :  -151.76,   -1)  ($$,      (1)   :  -188.602,  -1)  ($$,      (1)   :  -225.444,  -1)  ($$,      (1)   :  -262.285,  -1)  ($$,      (1)   :  -299.127,  -1)  ($$,      (1)   :  -335.968,  -1)  ($$,      (1)   :  -372.809,  -1)  ($$,      (1)   :  -409.651,  -1)  ($$,      (1)   :  -446.492,  -1)  ($$,      (1)   :  -483.333,  -1)  ($$,      (1)   :  -520.175,  -1)  ($$,      (1)   :  -557.016,  -1)  ($$,      (1)   :  -593.857,  -1)  ($$,      (1)   :  -630.699,  -1)  ($$,      (1)   :  -667.54,   -1)  ($$,      (1)   :  -704.382,  -1)  ($$,      (1)   :  -741.667,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)  ($$,      (1)   :  -inf,  -1)
($$.      (2)   :  -40.3012,  -1)  ($$.      (2)   :  -77.9027,  -1)  ($$.      (2)   :  -114.861,  -1)  ($$.      (2)   :  -151.692,  -1)  ($$.      (2)   :  -188.534,  -1)  ($$.      (2)   :  -225.375,  -1)  ($$.      (2)   :  -262.217,  -1)  ($$.      (2)   :  -299.058,  -1)  ($$.      (2)   :  -335.899,  -1)  ($$.      (2)   :  -372.741,  -1)  ($$.      (2)   :  -409.582,  -1)  ($$.      (2)   :  -446.423,  -1)  ($$.      (2)   :  -483.265,  -1)  ($$.      (2)   :  -520.106,  -1)  ($$.      (2)   :  -556.948,  -1)  ($$.      (2)   :  -593.789,  -1)  ($$.      (2)   :  -630.63,   -1)  ($$.      (2)   :  -667.472,  -1)  ($$.      (2)   :  -704.313,  -1)  ($$.      (2)   :  -741.444,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)  ($$.      (2)   :  -inf,  -1)
($(       (3)   :  -45.7222,  -1)  ($(       (3)   :  -78.2411,  -1)  ($(       (3)   :  -115.133,  -1)  ($(       (3)   :  -151.978,  -1)  ($(       (3)   :  -188.82,   -1)  ($(       (3)   :  -225.661,  -1)  ($(       (3)   :  -262.502,  -1)  ($(       (3)   :  -299.344,  -1)  ($(       (3)   :  -336.185,  -1)  ($(       (3)   :  -373.026,  -1)  ($(       (3)   :  -409.868,  -1)  ($(       (3)   :  -446.709,  -1)  ($(       (3)   :  -483.551,  -1)  ($(       (3)   :  -520.392,  -1)  ($(       (3)   :  -557.233,  -1)  ($(       (3)   :  -594.075,  -1)  ($(       (3)   :  -630.916,  -1)  ($(       (3)   :  -667.757,  -1)  ($(       (3)   :  -704.599,  -1)  ($(       (3)   :  -742.137,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)  ($(       (3)   :  -inf,  -1)
($,       (4)   :  -43.7637,  -1)  ($,       (4)   :  -78.1276,  -1)  ($,       (4)   :  -115.012,  -1)  ($,       (4)   :  -151.848,  -1)  ($,       (4)   :  -188.689,  -1)  ($,       (4)   :  -225.53,   -1)  ($,       (4)   :  -262.371,  -1)  ($,       (4)   :  -299.213,  -1)  ($,       (4)   :  -336.054,  -1)  ($,       (4)   :  -372.896,  -1)  ($,       (4)   :  -409.737,  -1)  ($,       (4)   :  -446.578,  -1)  ($,       (4)   :  -483.42,   -1)  ($,       (4)   :  -520.261,  -1)  ($,       (4)   :  -557.102,  -1)  ($,       (4)   :  -593.944,  -1)  ($,       (4)   :  -630.785,  -1)  ($,       (4)   :  -667.626,  -1)  ($,       (4)   :  -704.468,  -1)  ($,       (4)   :  -741.732,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)  ($,       (4)   :  -inf,  -1)
($.       (5)   :  -43.5252,  -1)  ($.       (5)   :  -77.9508,  -1)  ($.       (5)   :  -114.713,  -1)  ($.       (5)   :  -151.56,   -1)  ($.       (5)   :  -188.401,  -1)  ($.       (5)   :  -225.243,  -1)  ($.       (5)   :  -262.084,  -1)  ($.       (5)   :  -298.926,  -1)  ($.       (5)   :  -335.767,  -1)  ($.       (5)   :  -372.608,  -1)  ($.       (5)   :  -409.45,   -1)  ($.       (5)   :  -446.291,  -1)  ($.       (5)   :  -483.132,  -1)  ($.       (5)   :  -519.974,  -1)  ($.       (5)   :  -556.815,  -1)  ($.       (5)   :  -593.656,  -1)  ($.       (5)   :  -630.498,  -1)  ($.       (5)   :  -667.339,  -1)  ($.       (5)   :  -704.18,   -1)  ($.       (5)   :  -741.349,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)  ($.       (5)   :  -inf,  -1)

```

When I reduce the number of emissions and thus increase the average emission probability the problem goes away. But I am unsure whether that is the right way to go about this as the more emissions the model is trained with the better it will perform later on.

# Answer
## Avoiding zero probabilities

You probably want to be using additive smoothing when estimating probabilities from count data.

With a dictionary of 80,000 words, most of those words will be very rare: many of them might never appear anywhere in your training data, or will never appear associated with a particular part of speech. Thus, your counts for those words will be zero. That causes you to estimate an emission probability of zero, if you naively estimate the probability as a ratio of counts. However, a zero probability is unlikely to be physically meaningful (I doubt that there is truly *zero* probability of outputting that word; instead, it's probably some small probability that's close to zero but not exactly zero). Additive smoothing is one way to address this.

Lack of additive smoothing probably explains the `-inf`. You are computing with log-probabilities. A probability of zero corresponds to a log-probability of $-\infty$ (i.e., `-inf`). Implement additive smoothing, and your `-inf`'s might largely go away.

## Numerical stability of log probabilities

While computing with log probabilities does generally improve stability compared to computing with probabilities directly, there are some tricky aspects you must be careful of.

For instance, instead of adding probabilities by computing $\log(\exp(x)+\exp(y))$, it's usually better to compute $x + \log(1 + \exp(y-x))$ (assuming $y \ge x$; if $y \<x$, swap $x,y$ before doing this computation). This avoids loss of accuracy when $x,y$ are both small and are close to each other. You might want to use a built-in library for computing the function $u \mapsto \log(1+u)$. Some languages have built-in library functions for computing $\log(\exp(x)+\exp(y))$ in a numerically-stable way: it might be called something like `logsumexp`.

Other relevant references: https://stackoverflow.com/q/7480996/781723, https://math.stackexchange.com/q/2189716/14578, https://stackoverflow.com/q/42355196/781723, https://stackoverflow.com/q/23630277/781723.
> 2 votes

---
Tags: machine-learning, hidden-markov-models
---


# Question
Title: How to express the set of all ternary strings of odd length as regular expression?
I know that the lanuguage of all strings of odd length `{a,b}` can be expressed as: `(a+b)((a+b)(a+b))^*`.

But what about an odd length over `(a,b,c}`?

# Answer
It is actually simple...

> `(a+b+c)((a+b+c)(a+b+c))^*`.

**Explanation**

```
It is trivial since when you can do odd length over a language with 2 symbols, then why can't it be extended??

```
> 1 votes

---
Tags: formal-languages, regular-expressions
---


# Question
Title: Reachability queries on uncertain graphs
We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p\_{(u,v)} \in (0, 1\]$. We want to assign a score in $\[0, 1\]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

# Answer
I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community \[1\].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p\_{uv} \in (0,1\]$. You need to find whether two given vertices are reachable, therefore, lie in the same *connected component* or *disjoint set*. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

\[1\] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." *Proceedings of the VLDB Endowment* 4.9 (2011): 551-562.
> 5 votes

---
Tags: algorithms, graphs, probability-theory, union-find
---


# Question
Title: How does 0 have two values in one's complement?
It is said that in 2's complement 0 has only one value, while in 1's complement both +0 and -0 have separate values. What are they?

# Answer
In **1's complement** you just invert all the bits.

Consider these 2 examples (assuming 8 bits):

* $4 = 00000100$, so $-4= 11111011$
* $0 = 00000000$, so $-0=11111111$.

So you have 2 ways to represent the number 0

In **2's complement** you add 1 to the 1's complement representation of the negative number

* $-4$ that in 1's complement was $11111011$ becomes $11111100$
* $-0$ that in 1's complement was $11111111$ becomes $00000000$ same as 0

So you have just one way to represent the 0 in this case

As you can see from the examples the difference is that:

* in 1's complement, with 8 bits you can just express numbers from $-2^{7}+1$ to $2^7-1$ (from -127 to 127)
* in 2's complement with 8 bits you can express numbers from $-2^{7}$ to $2^{7}-1$ (from -128 to 127), so one more number
> 19 votes

# Answer
In ones' complement, you negate a number by flipping all the bits. Therefore, negating zero, $0\dots 0$ yields $1\dots 1$, which represents $-0$, which is the same thing as zero.
> 3 votes

# Answer
Speaking of two different *values* of 0 in one's complement is misleading. One's complement (and two's complement) are binary *representations* of numbers. They describe a way to represent numbers in binary, and how to do arithmetic operations on them. The number that is represented by the sequence of bits is the value.

When you have some value in one's complement, and want to find the representation of the value with the sign flipped - the additive inverse - you invert every bit. This includes zero, so there is a representation for $0$ and a representation for $-0$. But $0 = -0$: inverting the sign on $0$ doesn't give you a different value, it gives you the same value.

That gives you two representations for $0$ in one's complement: the bit sequence $0\dots 0$ and the bit sequence $1\dots 1$.
> 3 votes

---
Tags: arithmetic
---


# Question
Title: Must you work with all qubits in a circuit when applying a gate?
When looking at this question: How to apply a 1-qubit gate to a single qubit from an entangled pair?

And other questions, it makes it seem like when you have a quantum circuit involving $N$ qubits, that when you want to peform a gate operation on a subset of the qubits, that you must still make a matrix that applies to all qubits.

Is this always true, or is it only true in the case where qubits are entangled?

In other words... is it only entangled qubits that we have to process together, or must all qubits in a circuit be processed together?

# Answer
You can apply a quantum gate on **any** subset of the qubits, not affecting the rest.

This can be formalized as evolving certain qubits via $U$ while the other qubits evolve via $I$, thus the joint unitary is $U \otimes I$.
> 3 votes

# Answer
I think you will need that in the case that your operation is not using qubits in sequence. That is if you have 4 qubits (1, 2, 3 and 4) and you want to apply a 2-qubit quantum operation on qubit 1 and 4, e.g. a CNOT then you should construct a matrix of size $2^4 \times 2^4$.
> 0 votes

---
Tags: quantum-computing
---


# Question
Title: How can primitive recursion in two variables be made to be of only one variable?
Problem 7.16 in The Nature of Computation reads as follows:

> \[...\] show that when defining primitive recursive functions, we really only need to think about functions of a single variable. In particular, show that a function $f(x)$ is primitive recursive if and only if it can be generated from $0$, $S$, $pair$, $left$, and $right$, using composition and *iteration*, where iteration is defined as follows: if $f(x)$ and $g(x)$ are already defined, we can define a new function $h(y)=g^y(f(0))$. In fact, we can simplify this further and just take $h(y)=g^y(0)$.

($S$ is the successor function. $pair$, $left$, and $right$ create a tuple and take it apart again.)

It's easy to see that one can use $pair$, $left$, and $right$ to put multiple arguments into a tuple, pass that to a function and have that function extract the arguments back out. Similarly a recursive function of the form $f(x) = g(x,f(x-1))$ can be replaced by $f(x) = h^x(0)$. ($h$ will have to return a tuple $(x, f(x-1))$).
However I'm unable to deal with the case where multiple parameters and recursion occur simultaneously, i.e. $f(x,y)=g(x,f(x,y-1))$. The trouble occurs before trying to replace the recursion by iteration, at the stage where multiple arguments have to be combined. The problem is that, the way I see it, primitive recursion is only allowed to call the immediately next smaller case. For instance, $f(64)$ can call $f(63)$, but not $f(32)$. But $pair(x,y-1)\neq pair(x,y)-1$. So when calling a recursive function with a tuple, it can't access the corresponding smaller case that it would've had access to in the multi-parameter setting.

For reference: $pair$ is defined similar to how the rationals are put in a one-to-one correspondence to the natural numbers by Cantor's argument. Though instead of snaking back and forth along the diagonals, it always moves along a diagonal in the same direction, starting over when reaching the end of one.

# Answer
> 2 votes
A few facts that should help:

**1 - You can encode lists with primitive recursive functions**

I can expand if needed.

I'll write lists as $\[x\_1, \dots, x\_n\]$, write $x::\[x\_1,\dots ,x\_n\]$ for $\[x,x\_1,\dots,x\_n\]$ and $\operatorname{hd}(\[x\_1,\dots ,x\_n\])$ for $x\_1$.

**2 - You can use any order you want when defining a function by primitive recursion**

Let $b$ be a primitive recursive bijection whose inverse is also primitive recursive. Then you can use recursion with respect to the order $x\<\_by$ defined as $b(x)\<b(y)$ and it will still define primitive recursive functions. Suppose that you have $g(x,b(0))=g\_0(x)$ and $g(x,b(k+1))=h(x,b(k),g(x,b(k)))$. Then you can define $g'(x,0):= g\_0(x)$ and $g'(x,k+1)=h(x,b(k),g'(x,k))$ and you will get $g'(x,k)=g(x,b(k))$ so that you can now define $g(x,y):=g'(x,b^{-1}(y))$.

**3 - Your function can know its value on all smaller inputs when defining a function by primitive recursion**

Let $X$ be the domain of your function $g$ defined by $g(x,0)=g\_0(x)$ and $g(x,k+1)=h(x,k,\[g(x,k),g(x,k-1),\dots,g(x,0)\])$. Then you can define $g'(x,0):=\[g\_0(x)\]$ and $g(x,k+1):=h(x,k,g'(x,k))::g'(x,k)$ and you will have $g'(x,k)=\[g(x,k),g(x,k-1),\dots,g(x,0)\]$. You can therefore define $g(x,k):=\operatorname{hd}(g'(x,k))$.

---
Tags: primitive-recursion
---


# Question
Title: Lower bound on the number of comparisons needed for finding the two largest elements
> Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log\_2(n) - 2 comparisons. Prove that any algorithm will have to perform at least n +log\_2(n) - 2 comparisons in order to find both elements.

What I've done: I tried to compare it to a tennis tournament(sort of a binary tree that compare pairs of competitors in which each game has a winner and a loser - each winner goes up to the next level in the tree). It takes n-1 comparisons and every element is involved in a comparison log n times at most.

The biggest element will be the winner in the tournament. the second biggest element will have to face the winner so he's one of the log n elements the the winner competed against which means logn -1 comparisons. If I sum it all I get what I need to prove.

I got this note from the teacher: the proof is not correct because you assume the algorithm uses a tournament you have to prove any algorithm has an input for which the second largest element is in a group of size logn.

Can someone tell me how the proof should have looked like? I'm really struggling with it. Please be detailed as possible

# Answer
> 4 votes
With impossibility proofs, you don’t control the algorithm; you control the input. For this particular impossibility proof, the input is the outcome of the comparisons that the algorithm performs. Here’s one possible adversary strategy.

This adversary never claims that elements in distinct positions are equal. At each point in the algorithm’s execution, there are two classes of elements: *candidates*, which are the elements that have not compared less than another element; and *non-candidates*, which are the remaining elements. Candidates always compare greater than non-candidates. Non-candidates compare in an arbitrary consistent way. Comparisons between candidates can be resolved arbitrarily (prove this); the adversary declares the candidate involved in more previous comparisons of this sort (“knockout” comparisons) to be greater.

At the end of the execution, there can be only one candidate; otherwise, the algorithm can’t know which of the candidates is the maximum (prove this). The only way to reduce the number of candidates is a knockout comparison, which reduces the number of candidates by one. This implies that there are n - 1 knockout comparisons, forming a tournament tree of some shape. We observe that, for each node of the tree, when an element secures its place there, it has participated in a number of knockout comparisons equal to the height of that node. The root has height at least lg n, so it takes lg n - 1 comparisons to determine which of the lg n elements compared less than the maximum only (otherwise, the second maximum isn’t known). None of these comparisons are knockouts, so the total is at least n + lg n - 2.

---
Tags: complexity-theory, lower-bounds
---


# Question
Title: Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes
TL;DR: There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture:

E.g., look at the diagonal: 15 - 0 = 14 (?). From my point of view there're a lot of off-by-one errors.

# Answer
Those are just typos, as you can confirm by reading the general construction on the previous page ("Intuitively, we construct $G'$ by ...") and applying it to the flow network on the left. Yes, there are multiple off-by-one errors. It happens. Pobody's nerfect.

Incidentally, you might want to read the latest version of his notes, available from http://web.engr.illinois.edu/~jeffe/teaching/algorithms/, rather than the 2009 version you're reading right now (though this particular typo is still present).
> 1 votes

---
Tags: graphs, network-flow, max-cut
---


title: Formal languages - exercise

text:
# Question
Title: Formal languages - exercise
I'm trying to solve this exercise: given $L=\left\\{a^kb^k|k\>0\right\\}$ determine $L^2$ and $L^3$.

So I'm able to solve this kind of exercise if k is given into a defined range but I'm really struggling to solve this exercise.

Any help? Thanks.

# Answer
> 2 votes
Let's consider $L^2$. As stated in the comments you can consider it as $L \cdot L$.

Think to it as the concatenation of two different languages.

$L\_1 = \\{a^{i}b^{i}\ | \ i \> 0\\}$ and $L\_2 = \\{a^{j}b^{j}\ | \ j \> 0\\}$.

$L\_1 \cdot L\_2 = \\{ w\_1\cdot w\_2\ |\ w\_1 \in L\_1, \ w\_2 \in L\_2\\}$

As set $L\_1 = \\{ab, aabb, aaabbb,...\\}$, $L\_2 = \\{ab, aabb, aaabbb,...\\}$

$\color{blue}{L\_1} \cdot \color{red}{L\_2} = \\{ \color{blue}{ab}\color{red}{ab},\ \color{blue}{ab}\color{red}{aabb},\ \color{blue}{ab}\color{red}{aaaabbbb},\ \color{blue}{ab}\color{red}{aaaaabbbbb},\ \color{blue}{ab}\color{red}{aaaaaabbbbbb},..., \color{blue}{aabb}\color{red}{ab},\ \color{blue}{aabb}\color{red}{aabb},... \\}$

Can you express $L^2$ with a compact notation?

---
Tags: formal-languages, regular-expressions
---


# Question
Title: For every context-free grammar, is there an equivalent grammar in Chomsky normal form?
I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?

# Answer
Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement:

> For every CFG $G$ there is a grammar $G'$ in ChNF such that $L(G) = L(G') - \\{\varepsilon\\}$.

So now we have two choices.

Either to accept the loss of the empty string, which in practise is not a big deal. Or we have to adapt the definition to make room for generating the empty string in a special way. This usually means we allow a production $S\to \varepsilon$ where $S$ is the axiom, provided $S$ does not occur as right hand side of productions.

This is a matter of taste: there is no "best" definition. Personally I think having a special production for $\varepsilon$ is not elegant, and prefer a notion of equivalence "upto the empty string".
> 3 votes

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


# Question
Title: Function that cannot be computed by a Boolean circuit of size $2^n/2n$
Show that, for sufficiently large $n$, there is a function $f\colon\\{0,1\\}^n \to \\{0,1\\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a hint.

# Answer
We need counting argument here. First thing is, there are $2^{2^{n}}$ many boolean functions, second thing is to count the number of boolean circuits for $k$ size boolean circuit. There are $2^{k^2} \times 3^{k}$ many boolean circuits of size $k$ (use adjacency matrix ). In your case value of $k =\frac{ 2^n}{2n}$, now you can easily check that

> $$2^{2^{n}} \> 2^{k^2} \times 3^{k} $$

So it means there are more number of functions than the total number of boolean circuits. There has to be at least one function that can not be computed by $k$ size circuit ( pigeonhole principle ). One thing to note here that I have proved the existence of such type of boolean circuit but to come up with such type of boolean circuit is quite hard.
> 4 votes

# Answer
Hint: Estimate from above the number of circuits with $2^n/2n$ gates, and compare it to the number of functions.
> 3 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Interpreting quantum oracles that makes a quantum operation
I am preparing for my master thesis in Quantum Image Processing (QImP), i choose to work with Novel Enhanced Quantum Representation of Digital Images (NEQR).

To convert an image from Classical domain to Quantum domain we need to do a Quantum Image Preparation which in case of NEQR is consists of two steps as shown in the image below:

The second step is the one that set the colors. The paper descripe this step as follow

> It is divided into $2^{2n}$ sub-operations to store the gray-scale information for every pixel. For pixel $(Y,X)$, the quantum sub- operation $ U\_{YX}$ is shown as (8) $$ U\_{YX} = \Biggl(I \otimes \sum\_{j=0}^{2^n -1} \sum\_{i=0,ji \neq YX}^{2^n - 1} \lvert ji \rangle \langle ji \rvert \Biggr) + \Omega\_{YX} \otimes \lvert YX \rangle \langle YX \rvert \tag{8}$$
>
> Where $ \Omega\_{YX} $ is a quantum operation as shown in (9), which is the value setting operation for pixel $ (Y,X)$: $$ \Omega\_{YX} = {\displaystyle \bigotimes\_{i=0}^{q-1} \Omega\_{YX}^{i}} \tag{9}$$ Because $ q $ qubits represent the gray-scale value in NEQR, $ \Omega\_{YX}$ is consisted of $ q $ *quantum oracles* as shown in (10): $$ \Omega\_{YX}^{i} : \rvert 0 \rangle \rightarrow \Bigl\rvert 0 \oplus C\_{YX}^{i} \Bigr\rangle \tag{10}$$ From (10), if $ C\_{YX}^{i}=1, \Omega\_{YX}^i $ is a $ 2n - CNOT $ gate. Otherwise, it is a quantum gate which will do nothing on the quantum state.

My question is, how (10) is a $2n - CNOT $ gate if $ C\_{YX}^{i}$ is $1$?

From my understanding $ C\_{YX}^{i}$ is a computational basis, that is it is either $\rvert 0 \rangle$ or $\rvert 1 \rangle$ and the tensoring of $ C\_{YX}^{i}$ in (9) will produce a column vector.

Also if i interpret $ \Bigl\rvert 0 \oplus C\_{YX}^{i} \Bigr\rangle $ as follow: it is the result of $ 0 \oplus C\_{YX}^i$ this is just $C\_{YX}^i$ because $ 0 \oplus x$ is just $x$. Where $ \oplus $ is XOR. How this will produce a $2n-CNOT$ gate where it is a 3 qubit gate (its matrix is 8 * 8)

# Answer
> 0 votes
I would leave this as a comment, but I don't have enough reputation.

The interpretation of the tensor in (9) is not correct. The quantum states are being represented in the computational basis, meaning, any state will be represented as a mixture of $|0\rangle$ and $|1\rangle$, but this is not particularly important, it could be any basis, in this case is just notationally easier. Further, the tenor in (9) is over the $\Omega\_{YX}^i$, not the $C\_{YX}^i$ (is this a typo?), and each $\Omega\_{YX}^i$ is an operator, and thus the tensor $\Omega\_{YX} = \bigotimes^{q-1}\_{i=0}\Omega\_{YX}^i$ would again be an operator, on the $q$ qubits. It could be easier to think of as a matrix, but this is not particularly beneficial I think.

There is a typo I think. If $C^i\_{YX} = 1$, $\Omega\_{YX}^i$ would be a $2n$-CNOT, and not $\Omega\_{YX}$ as you have written. When $C\_{YX}^i = 1$, $\Omega\_{YX}^i|0\rangle = |1\rangle$.

I don't know what $C\_{YX}^i$ represents, and I'm not familiar with what a $2n$-CNOT gate is, but I think probably it will not always be an $8\times 8$ matrix, especially since it has the variable $n$ in it. Sorry to not fully answer your question, but I hope I helped a bit.

---
Tags: quantum-computing
---


# Question
Title: Is it possible to do multitasking without context switch with just one cpu?
All the article I can find seems to talk about multitasking and context switch as its a two different thing. It seems that multitasking and context switch are the same thing.

# Answer
> 2 votes
Yes, it is possible (depending upon what you mean by "context switch"). See cooperative multi-tasking. In cooperative multi-tasking, the operating system never needs to perform a context switch between tasks -- instead, tasks voluntarily take care of saving their own state and switching between themselves.

# Answer
> 1 votes
There are Superscalar and Vector Processors.

In order to truly multitask you have to be able to do multiple things at the same time. Normally this is done within human perception by context switching, it really only appears to do more than one thing at a time through, really its just like two people sharing a hammer and a bucket of nails, if they do it right, its like having two hammers and two nails as far as productivity, but to really multitask, you need more than one hammer or a hammer that can hit multiple nails at once.

---
Tags: terminology, computer-architecture, operating-systems, concurrency
---


title: New Applications of Network Flow

text:
# Question
Title: New Applications of Network Flow
I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may find Network Flow useful. I want to refrain from using standard problems like Baseball problem, marriage problem, edge disjoint. I need Ideas for such problem which needs to be represented as a graph and then using Network flow we can find the solution.

# Answer
> 5 votes
Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing. For instance, it has been used for image segmentation, image stitching, seam carving, image denoising, stereo image correspondence, and more.

See, e.g., https://en.wikipedia.org/wiki/Graph\_cuts\_in\_computer\_vision, What's the relationship of max-flow-min-cut and Markov Random Fields?, https://cs.stackexchange.com/a/37423/755, https://en.wikipedia.org/wiki/Image\_segmentation#Graph\_partitioning\_methods

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


# Question
Title: Topological sort, but with some fixed values
I'm working on a problem similar to topological sorting, but with an additional constraint: I want to order the nodes by assigning a positive integer index to each, and, in additional to the relative constraints the graph defines, some nodes have a predefined index assigned.

That is, the input is a set of nodes $V$, a set of relative constraints each of the form $X\_a \< X\_b; a \in V, b \in V$, and a set of absolute constraints $X\_a = i, i \in \mathbb{Z}^+$.

The output is a map $X$ such that $X\_a \in \mathbb{Z}^+$ for each $a \in V$, and all relative and absolute constraints specified in the input are satisfied. The values $X\_a$ need not be unique; it's acceptable that $X\_a = X\_b$ given $a \neq b$, so long as all the specified constraints are satisfied. If no such $X$ exists, the output is an error value.

Not sure what to search for; does such an algorithm exist? If not, is there a good way to map this problem to a known problem? I'm working on it, too, but just wanted to see if this set off any lightbulbs for anyone in the community before I go too deep :)

(In case this helps, I'm working on a solver to manage the z-indexes of my web application.)

# Answer
> 2 votes
There's a natural algorithm:

1. Arbitrarily pick any vertex all of whose predecessors have already been labelled; call it $v$.
2. If $v$ is constrained to have a specific index, label $v$ with that integer. Otherwise, pick the *smallest* integer greater than all of the labels on the predecessors of $v$, and label $v$ with that integer.
3. If at least one vertex remains unabelled, go to step 1.

This is an adaptation of Kahn's algorithm for topological sorting, and it can be implemented so it runs in linear time.

The crucial thing that makes your problem feasible is that the labels don't need to be unique. If the labels need to be unique, I suspect the problem becomes much harder; at least, this algorithm doesn't work, and a generalization of the problem becomes NP-hard.

---
Tags: algorithms, graphs
---


# Question
Title: a cut containing exactly one edge in each path
Given a digraph with a source $s$ and target $t$, must there be an edge cut which contains exactly one edge in every path from $s$ to $t$? I'm not interested in a minimum cut; any cut would do.

If not, how close to "exactly one" can we get?

# Answer
It really depends on what do you exactly mean by "path".

**Edge-disjoint paths --** Given a graph $G=(V,E)$, a minimum edge-cut consists of one edge for every edge-disjoint path between $s$ and $t$.

**Vertex-disjoint paths --** Given a graph $G=(V,E)$, a minimum vertex-cut consists of one vertex for every vertex-disjoint path between $s$ and $t$. Therefore, the set of edges incident to the vertices in the cut (out-edges) consist of one edge per vertex-disjoint path between $s$ and $t$.

Having exactly one edge per every simple path between $s$ and $t$ is impossible. The reason is that the number of edges in the cut must be equal to the number of simple paths between $s$ and $t$, however, the number of simple paths between two vertices $s$ and $t$ can be exponential in terms of $n$, while the number of edges is at most $n^2$. Using Pigeonhole principle, it can be shown that it is impossible to find such solution.

The following example shows that the number of paths between $s$ and $t$ is $2^{(n-2)/2}$, while the number of edges between them is $2n-4$.

If you are interested in finding a set of edges that consists of at least one edge from every path between $s$ and $t$, then you can use the minimum edge-cut between $s$ and $t$. If you are considering a case where you need at least one edge from each path, and no more than one edges per path, you can use an approach that is similar to minimum cut algorithm, but I am not sure how efficient it would be in practice.

1. Find the minimum edge-cut between $s$ and $t$;
2. Using a graph traversal algorithm (i.e. DFS), find if there is a path that goes over two of the edges in the cut;
3. If you find a such a path, remove those edges $(u\_1, v\_1), \cdots, (u\_k, v\_k)$ from the cut $C$ and replace them with the minimum cut from each $u\_i$ to $t$ ($1 \leq i \leq k$), and repeat from 2;
4. If there is no such path then output $C$ and terminate;
> 1 votes

---
Tags: graphs, minimum-cuts
---


# Question
Title: (Nontrivial) Algorithms for finding the third largest element of a set
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for finding the third largest in a set of $n$ distinct elements?

Given that the tight lower bound is still unknown, I want to know the algorithms currently published in papers (meaning that they are not trivial, for example, by finding and removing the largest and the second largest elements and finding the third largest one in $(n-1) + (n-2) + (n-3) = 3n - 6$ time) for finding the third largest element.

Searching for "algorithm finding the third largest element" in Google does not bring me useful references.

# Answer
For $n\>5$, this paper proves that the number of comparisons *deterministic* algorithms need is $n  +  \big(2 \cdot \lfloor \log\_{2}(n)\rfloor \big) - \big(\text{an element of } \\{1,2,3\\}\big)$, where that element depends on $n$'s position relative to the nearby powers of $2$.

Furthermore, for $n\>7$, that paper gives a deterministic algorithm which achieves those values.

By pages 330 and 331, the *average* number of comparisons needed is  $n + \Theta(\ln\ln n)$.

Theorem 5 is that the average number of comparisons used by that paper's algorithm is at most $n + 5 \cdot ( 11 + \ln\ln n)$. I have currently not located anything else regarding non-worst-case algorithms for your problem, although I've kept finding more as I go along.
> 7 votes

---
Tags: reference-request, lower-bounds, search-problem, selection-problem
---


title: Determine number of blocks in a cache

text:
# Question
Title: Determine number of blocks in a cache
The question is: We need to design a cache with cache size of 128K bytes, block (line) size of 8 words, and word size of 4 bytes. Consider a computer with 64-bit physical address. The cache is addressed by physical address

I need clarification on this: if we have 128k bytes and each block equals 32 bytes (8\*4), do we have: 1.($128$ x $2^{10}$)/$32$ or 2. $128k/32$. The problem is that the first gives 4096 blocks and the second gives 4000 blocks. Which is the correct one?

# Answer
> 1 votes
The common usage is for KB, MB, GB, TB, and so on to denote powers of 2 rather than powers of 10. There are ways to denote powers of 10, but they are infrequently used. See for example the Wikipedia page on kibibyte.

---
Tags: cpu-cache
---


# Question
Title: Are CPU architectures biased towards procedural runtimes?
Are there any changes that could be made to CPUs to make them perform better for concurrent runtimes like Rust? For instance, are there changes to branch prediction implementations or cache sizes that would help concurrent runtimes?

I have the impression that current CPU designs might be optimized more for procedural runtimes like C. If we were instead going to optimize for concurrent runtimes, how would CPUs look different?

For isntance, branch prediction was implemented based on generalizations drawn in research papers analyzing procedural codes. I'm wondering if the concurrency abstraction will add a significant working-set to the runtime that adversely impacts existing branch prediction algorithms. For example, predicting in a for loop is one thing, but when the target of the branch is always some new portion of memory (graphic, text, etc), it'll always be a cache miss, and there'll never be branch history for it-- because neither have touched it yet.

This is probably a silly question because the content, though it might always be in RAM, will be branched to an order-of-magnitude less than it'll be used (once it's been loaded to cache)...but still, there should be an observable temporal-boundary to the contexts stored in the cache and branch predictors in a procedural runtime, that would be manifest as an abstraction-boundary in a more parallelized environment. So I'm wondering... Have these boundaries been observed? Have any research papers have analyzed this?

Are CPU architectures biased towards procedural code over concurrent code; or are modern CPUs sufficiently general-purpose that a highly concurrent language doesn't suffer?

# Answer
It is probably more the case that modern computer architectures are designed with the goal of improving the quality of code generated by compilers against a budget of cost in die area and power used. Runtime libraries are just a specific instance of compiled code that needs to be executed in an efficient manner.

For a very long time, the target language for most architectures has been the "C" language. This reflects the modest demands that that language makes on its hardware and the fact that it has become an almost universal systems programming language (Sorry Rust and Go, you have a long way to go to beat C).

A consequence of this seems to be that new languages are often defined in terms of their C equivalent semantics just so that they will avoid needing processor facilities that are likely to be absent on current computers.

The payoff for a processor that matches well with modern compilers is that code from those compilers runs well and the processor has at least a chance to be competitive. The cost of failure here dooms the processor before it can get started. Just two examples in the negative include the iAPX-432 and the Itanium, both by Intel. Both had a very poor relationship with their compilers (Ada and C respectively) with the failure of the products turning into a blame game between silicon and software.
> 1 votes

# Answer
Without a doubt, yes.

In particular, the communications model implied by C99 is shared-memory. More advanced concurrent languages have richer communication models, such as message passing channels (as in Rust).

Modern CPU architectures do have explicit hardware support for shared-memory. In particular, cache coherency protocols like MESI are implemented in actual gates and wires. There is no real support for message passing between processes, even though the idea of message passing isn't alien to CPU's. Modern PCI-e buses even emulate shared memory using message passing, whereas CPU processes have to emulate message passing using shared memory!
> 0 votes

---
Tags: computer-architecture, concurrency, functional-programming
---


title: Number of memory accesses

text:
# Question
Title: Number of memory accesses
Im'm studying Instruction Set Architecture using the book "Logic and Computer Design Fundamentals". Studying types of architectures I came up with an example of memory-memory type which is:

```
ADD T1, A, B     ' M[T1] <-M[A] + M[B]

ADD T2, C, D     ' M[T2] <- M[C] + M[D]

MUL X, T1, T2    ' M[X] <- M[T1] * M[T2]

```

Then a it is said and I quote:

> For the previous example, three instructions are required, but if an extra word must appear in the instruction for each memory address, then up to four memory reads are required to fetch each instruction. Including the fetching of operands and storing of results, the program to perform the arithmetic operation would require 21 accesses to memory.

I don't understand how they come up with 21 accesses to memory...

i know that we have at least 9 accesses (one for each operand and each result). If we have an extra word (to specify the address of each operand) then we will have 7 more

9+7=16... How do they come up with the extra 5 accesses? Can someone clarify this to me? Thanks!

# Answer
> 1 votes
The proposed architecture apparently does not use CPU registers. That means all data must be stored in main memory. Instructions will then need to know *where* in main memory their arguments are.

So, `ADD T1, A, B` needs the instruction (one word), the 2 addresses of A and B (2 words), and the two values of A and B (2 words). It will then calculate the result, retrieve the address of T1 (1 word), and store the result at that address (1 word). In total, that's 6 reads (one instruction, 3 addresses, 2 values) and 1 write (the final value).

---
Tags: computer-architecture
---


# Question
Title: How does one go about designing a system that never crashes?
I read somewhere that the Apollo Guidance Computer was designed in such a way, that, although it is hugely less powerful than the average smartphone, it was dependable to the point that it "never crashed". My questions pertaining to this were:

1. Is designing such a digital system possible, even in the '60's ?
2. What are the constraints that one would want to look out for when attempting to design such a digital system that "never crashed", using today's technology?

# Answer
> 2 votes
It wasn't possible back then, in the absolute sense. What you're essentially looking for when you say "never crashes" is a system that always makes progress towards its goals. Today, we can prove that a computer program does that, but the relevant methods to construct such proofs were only developed starting in the 70's - years after the Apollo Guidance Computer was developed.

Practically speaking, today we would formulate the requirements on the guidance computer using a formal specification language. In particular, we'd identify each task of the computer, and specify that each task finishes n a bound number of steps. We also define a task scheduler that never halts and chooses the right tasks for each stage of the mission. With a bit of work, we then prove that every task that needs to be executed is executed on time. We then transform the specification into code, in a way that allows us to verify the proof still holds.

---
Tags: computer-architecture
---


# Question
Title: Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?
I have an example below which seems to lead to a “useless” production.

This is the original grammar:

\begin{align\*} S&\longrightarrow aX\\,|\\,Yb\\ X&\longrightarrow S\\,|\\,\varepsilon\\ Y&\longrightarrow bY\\,|\\,b \end{align\*}

Here is the conversion to CNF:

**Step 1: Make sure the start symbol does not occur on the RHS.** \begin{align\*} S'\\!\\!\\!&\longrightarrow S\\ S&\longrightarrow aX\\,|\\,Yb\\ X&\longrightarrow S\\,|\\,\varepsilon\\ Y&\longrightarrow bY\\,|\\,b \end{align\*} **Step 2: Remove rules that lead to $ \varepsilon $.** \begin{align\*} S'\\!\\!\\!&\longrightarrow S\\ S&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ X&\longrightarrow S\\ Y&\longrightarrow bY\\,|\\,b \end{align\*} **Step 3: Remove all unit productions.** \begin{align\*} S'\\!\\!\\!&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ S&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ X&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ Y&\longrightarrow bY\\,|\\,b \end{align\*} **Step 4: Remove remaining productions which do not conform to CNF.** \begin{align\*} S'\\!\\!\\!&\longrightarrow a\\,|\\,AX\\,|\\,YB\\ S&\longrightarrow a\\,|\\,AX\\,|\\,YB\\ X&\longrightarrow a\\,|\\,AX\\,|\\,YB\\ Y&\longrightarrow BY\\,|\\,b\\ A&\longrightarrow a\\ B&\longrightarrow b\\ \end{align\*}

It seems that following the algorithm has led to a useless production. The second production will never be invoked from the starting symbol.

Is the production really useless and is it right to remove it from the Chomsky Normal Form grammar?

# Answer
> 1 votes
Given a $CFG \ G$, before converting in $CNF$ you need to clean the grammar, that means (**order is important**):

> 1) eliminate $\epsilon$-productions
>
> 2) eliminate unit productions
>
> 3) eliminate variables that do not derive terminal strings
>
> 4) eliminate unreachable variables from the starting symbol

After this you make substitutions/split rules in order to obtain a CNF grammar.

According to these rules, after your step 3 I would eliminate non generating variables (all the variables can reach a terminal string) and unreachable variables (You cannot reach $S'$ from $S$), to end up with the following productions:

\begin{align\*} S'\\!\\!\\!&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ \ X&\longrightarrow a\\,|\\,aX\\,|\\,Yb\\ Y&\longrightarrow bY\\,|\\,b \end{align\*}

I don't know which procedure you are following (*it may vary according to textbooks/instructors*), but if you don't apply steps $3$ and $4$ then yes, you could end up with useless symbols in your grammar in CNF.

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


# Question
Title: A simple Query regarding Modulus Notation?
Aren't these two Modulus equations exactly the same (seems obvious):

1. $ X = 0 \ (mod\ B) $
2. $ X = B \ (mod\ B) $

The reason for the query is the following NP Complete Problem from Garey and Jhonson:

AN2, Simultaneous incongruences.

Given a collection $ \[(a\_1,b\_1),…,(a\_n,b\_n)\]$ of ordered pairs of positive integers with $a\_i≤b\_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a\_i(mod \ b\_i)$?

If both are equivalent why do we require $a\_i≤b\_i$ in the problem definition as its equivalent to $a\_i\<b\_i$ ?

# Answer
> 1 votes
Note that the definition of this problem considers *positive integers* without $0$, which is instead denoted by $B \bmod B$.

---
Tags: discrete-mathematics
---


# Question
Title: Intersection/Union of Language of PDA, CFG and NFA
I stumbled across the following question.

Say I have given an arbitrary PDA $P$, NFA $N$, and CFG $G$. My question is then if the following language ($L(P) \cap L(N)) \cup L(G)$ is context-free.

How can this be determined?

# Answer
$L(P)$ and $L(G)$ are context-free; $L(N)$ is regular. By standard closure properties, the intersection of a context-free language with a regular language is context-free, and the union of two context-free languages is context-free. Therefore, $L(P)\cap L(N)$ is some context-free language $C$ and $C\cup L(G)$ is context free.

The closure properties can be proven without reference to the specific language by using the fact that every context-free language is accepted by a PDA or defined by a context-free grammar. For example, to show that the union of two context-free languages is context free, let those languages be defined by grammars $G\_1$ and $G\_2$ with start symbols $S\_1$ and $S\_2$. We can rename the non-terminals in $G\_1$ and $G\_2$ so that no non-terminal appears in both grammars. Now form the a grammar $G$ with start symbol $S$ consisting of the rule $S\to S\_1|S\_2$, all the rules of $G\_1$ and all the rules of&nbsp:$G\_2$. You should be able to convince yourself that $L(G) = L(G\_1)\cup L(G\_2)$. But proving this didn't require us to know anything about what rules are contained in the grammars.
> 4 votes

---
Tags: regular-languages, automata, context-free
---


title: Decimal to Fixed Point Conversion

text:
# Question
Title: Decimal to Fixed Point Conversion
I am having trouble to get the intuition behind the following approach: We take the fraction point (say: .642) and continuously multiply by 2, taking whatever ends up right of the point as our next number (either 0 or 1) after the fixed point in the binary number. Then we take whatever is left after the decimal point and repeat.

# Answer
> 3 votes
Let $x$ be the real number you wish to convert. We will assume without loss of generality that $0 \le x \< 1$. Form the Dedekind-completeness of the order on $\mathbb{R}$, it follows that $x$ can be (almost) uniquely written as

$$ x = \sum\_{h=1}^{\infty} 2^{-h} \alpha\_h $$

where $a\_h \in \\{ 0, 1\\}$ for all $h$. Now observe that:

$$ 2x = \sum\_{h=1}^{\infty} 2^{-h+1} \alpha\_h = \alpha\_1 +\sum\_{h=1}^{\infty} 2^{-h} \alpha\_{h+1} $$

where the rightmost sum is nonnegative and less than $1$. Multiplying by $2$, therefore, allowed us to discover a single binary digit of $x$, namely $\alpha\_1$. The same procedure can be iterated to yield as many digits as you wish.

# Answer
> 0 votes
Complementing quicksort's answer.

Your implementation will take a decimal number and convert to it's $(0.d\_0d\_1\ldots d\_n \ldots)\_2$ binary representation. Your example would work like this:

**Step 1:** \begin{align\*} x\_0 &= 0.624\\ 2 \times x\_0 &= 1.284 \end{align\*} Is $2 \times x\_0 \geq 1$? If so, $d\_0 = 1$, otherwise $d\_0 = 0$.

**Step 2:** \begin{align\*} x\_{1} &= 2\times x\_0 - d\_0\\ x\_1 &= 0.284\\ 2 \times x\_1 &= 0.568 \end{align\*} Is $2 \times x\_1 \geq 1$? If so, $d\_1 = 1$, otherwise $d\_1 = 0$.

**Step 3:** \begin{align\*} x\_{2} &= 2\times x\_1 - d\_1\\ x\_2 &= 0.568\\ 2 \times x\_2 &= 1.136 \end{align\*} Is $2 \times x\_2 \geq 1$? If so, $d\_2 = 1$, otherwise $d\_2 = 0$.

**And so on...**

As you can see this looks like a loop, you may want to try to implement it in your favorite programming language. Notice, however, that some finite decimal representations may have infinite representation in binary.

---
Tags: fixed-point
---


# Question
Title: How to prove the language as "Recursive"?
How to prove the statement

> "If the strings of a language $L$ can be enumerated in lexicographically(alphabetic) order, then the language is Recursive but not context free" ?

---

Basically, My point is how can the strings of $a^nb^nc^n$ can be lexicographically enumerated as first $n$ has infinite terms .

# Answer
> 3 votes
Your confusion may stem from the interpretation of "lexicographically". It's common to take this to mean "by length and then for strings of the same length, by alphabetic order. If this is the case, then an enumeration of your language would be: $\epsilon, abc, aabbcc, aaabbbccc, \dotsc$.

If your language was $\\{a^ib^jc^k\mid i,j,k\ge 0\\}$ then the enumeration would be $$ \epsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aab, \dotsc $$

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


# Question
Title: Encoding first order formula (or its tree) into binary string?
How to encode a first order formula into binary string, which I could give as input to Turing machine or program to do something with it (deciding is it satisfiable, or is concrete structure model for it, for example)?

I've read that I should first make a tree (which I know how to do) and then encode that tree, which I don't know how to do and I don't understand why I need to make that tree? Why don't just make binary number for every symbol which could appear in formula $( = , \vee, \wedge, \<=\>, =\>, \exists, \forall...)$ and connect them into string for concrete formula?

# Answer
> 2 votes
There is one encoding scheme which is particularly obvious. Under this encoding scheme, the encoding of the formula $a \Rightarrow (b \Rightarrow a)$ is $$ a \Rightarrow (b \Rightarrow a). $$ A C program can parse this string into a tree if it needs to, but it's up to the program.

It is of course possible to think of many other encoding schemes, but unless you are interested in very weak complexity classes, the exact encoding scheme doesn't matter.

There is one fine point here: the alphabet is finite, but there could be formulas with arbitrarily many variables. There are many ways to solve this problem. For example, you can name variables in the form "$v$ + number", for example $v5$, $v107$, and so on. This uses only a finite alphabet (since we encode the number in decimal, using 10 symbols).

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


# Question
Title: Superdense coding - What are the individual qubits A and B?
With reference to this PDF discussing Superdense coding, it is mentioned that there are two qubits A and B whose superposition gives the system $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$. It is said that Alice has A while Bob has B. What are the individual qubits A and B?

Since the system is entangled, can there exist two qubits A and B such that their superposition is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ ? If the answer is no, how is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ actually shared between Alice and Bob (or maybe how is it realized in practise)? Is it just that A and B cannot be written using the standard basis?

# Answer
> Is it just that A and B cannot be written using the standard basis?

Correct. Entangled qubits are not separable. You can't factor them into a form like $(a\_0 |0\rangle + a\_1 |1\rangle) \otimes (b\_0 |0\rangle + b\_1 |1\rangle)$.

You *can* get a per-qubit density matrix by tracing out the other qubit, but the resulting density matrix doesn't capture the correlation between the two qubits. It just looks like a maximally mixed state.
> 0 votes

---
Tags: quantum-computing
---


title: Formalizing self-propagating behaviour

text:
# Question
Title: Formalizing self-propagating behaviour
Since reading Ken Thompson's *Reflections on Trusting Trust* I am trying to formalize the idea of a program which mutates its own behaviour; specifically, a program that would be self-reproducing except that it would reproduce itself with a mutation. With this definition I wish to differentiate this kind of program from self-reproducing programs and will call them *programs with self-propagating behaviour* (due to the nature of propagating its own mutations). I am familiar with Hoare Logic, LTL, CTL, and CTL\*, but am unsure what to use for the formulation since Hoare Logic requires a concrete implementation of a program and I am trying to represent not a program but a *kind* of program, and am also unsure if/how I could express this idea in LTL, CTL, or CTL\*.

# Answer
> 1 votes
I don't have time for an elaborate answer right now, so here is just a quick braindump: Program logic does not restrict to concrete programs. Given e.g. a pair $(A, B)$ of pre/post-conditions, you can think of this pair as defining a set of programs

$$ \\{ P \ |\ P\ \text{is a programs such that}\ \models A\[P\]B \\} $$

Here are a couple other references that might be useful.

* J. Von Neumann, Theory of Self-Reproducing Automata.
* F. Cohen, Computer Viruses - Theory and Experiments.
* S. Kramer, J. C. Bradfield, A general definition of malware.
* G. A. Kavvos, Theories of Computer Viruses: 30 Years Later.
* L. M. Adleman, An abstract theory of computer viruses.
* G. Jacob, E. Filiol, H. Debar, Formalization of viruses and malware through process algebras.
* J. L. England, Statistical physics of self-replication.

As the kind of program you envision is a form of meta-programming, I suggest also to look at this field (which is primarily implementation-driven and lacks substantial theory as of 2017). Here are some references, none of which is likely to be directly relevant, but will eventually lead to research that should be:

* M. Berger, L. Tratt, Program Logics for Homogeneous Meta-Programming
* S. N. Artemov, L. D. Beklemishev, Provability Logic.
* G. Japaridze, D. de Jongh, The logic of provability.
* S. Artemov, Explicit Provability And Constructive Semantics.
* J. Alt, S. Artemov, Reflective λ-Calculus.

# Answer
> 0 votes
My (rather tentative) answer would be that the program "changing its meaning" (being a compiler, and having been written in the language that it translates) is something that has to do no just with syntax and semantics, but with what we call **pragmatics**. The program has to be actually considered a compiler (by its users), i.e., at the pragmatic level.

It is an amazing thing indeed, that these pieces of software can make us dance around them, and that is possibly the reason why Ken Thompson was so impressed by what he found.

As you might expect, *formal pragmatics* is a discipline that has yet to be domesticated, and I am not personally familiar with the research on the subject. All I can give you is this pointer, for your own further investigation.

# Answer
> 0 votes
Perhaps the final word in self-mutation are Jugen Schmidthiber's Goedel Machines, which perform provably optimal self-modification.

---
Tags: logic, formal-methods, modelling
---


# Question
Title: Where I can find example how prove red black tree?
I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction.

I don't understand how apply induction. (((

# Answer
> 2 votes
Here is the obvious thing to try:

1. Prove that if you apply the insertion algorithm twice on an empty tree, then the resulting red-black tree has a red node (this also follows from the invariants of red-black trees).
2. Prove that if a red-black tree has a red node and you insert an element using the insertion algorithm, then the result red-black tree has a red node.

I don't know if this scheme works, but it's the most immediate way to apply induction.

---
Tags: proof-techniques, binary-trees, induction
---


# Question
Title: Transforming 3 SAT to Simultaneous In-Congruence Problem?
Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2):

Given a collection $\[(a\_1,b\_1),…,(a\_n,b\_n)\]$ of ordered pairs of positive integers with $a\_i≤b\_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a\_i(mod\ b\_i)$?

But I am struggling with the transformation and not much clue how to go about it nor can find any literature on it. Thus, needed help with the transformation?

# Answer
Given a SAT instance on $n$ variables, find $n$ relatively prime integers $p\_1,\ldots,p\_n \geq 2$ of polynomial size (for example the first $n$ primes). The idea is to encode the value of variable $x\_i$ as $x \bmod{p\_i}$. The first step is to ensure that the variables are indeed binary. To this end, for each $i$ and for each $2 \leq a \< p\_i$, we add the constraint $x \not\equiv a \pmod{p\_i}$.

Each clause involving $p\_i,p\_j,p\_k$ corresponds to one forbidden value of $x \bmod{p\_ip\_jp\_k}$ via the Chinese reminder theorem. For example, consider the clause $x\_i \lor x\_j \lor \lnot x\_k$. Find the value $0 \leq a \< p\_ip\_jp\_k$ which satisfies $a \equiv 0 \pmod{p\_i}$, $a \equiv 0 \pmod{p\_j}$, and $a \equiv 1 \pmod{p\_k}$. Add the constraint $x \not\equiv a \pmod{p\_ip\_jp\_k}$.

The resulting system is completely equivalent to the original 3SAT instance.
> 2 votes

---
Tags: np-complete
---


# Question
Title: Every state in subset automaton is reachable
I'm currently trying to prove that following NFA $\mathcal{M}\_0 = (Q, \Sigma, \delta\_0,0,\\{0\\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language.

$\mathcal{M} = (2^Q,\Sigma,\delta,\\{0\\},F)$ is constructed using the subset/powerset algorithm and I'd like to show that $\mathcal{M}$ is minimal (i.e. $F = \\{q \in 2^Q \mid 0 \in q\\}$).

My problem is to show that every state $q \in 2^Q$ is reachable. I'm trying to prove this by induction over $|q|$.

It is clear for $|q| = 0$ since $\delta(\\{0\\},b) = \emptyset$. For $|q| = 1$ it follows directly from the NFA: $\Delta(\\{0\\},a^i) = \\{i\\}$ for $1 \leq i \leq n-2$.

The problem starts in the inductive step. Let $q = \\{i\_1,\dots,i\_k\\}$ with $0 \leq i\_1 \< i\_2 \< \cdots \< i\_k \leq n-2$.

For states with $i\_1 = 0, i\_k=n-2$ (using the induction hypothesis) or $i\_1 = 0, i\_2=1$ (using the first case mentioned) it is easy to show but in other cases I have no clue how to do it.

EDIT: Beware that the dotted states also have a $b$ loop to themselves (!), i.e. $\delta\_0(i,b)=\\{0,i\\}$ for $1 \leq i \leq n-3$.

# Answer
I try to wrap up your question and answer the part you are interested in.

I. From @DavidRicherby answer, proving that you have a large number of accessible states is not enough to show lower bounds on the size of DFA for your language. As you said it in a comment, you also need to show that those states are not equivalent.

II. As you have already observed, the states of the DFA $\mathcal{M}$ are not equivalent since if $p,q \subseteq Q$ and $i \in p \setminus q$, then reading $a^{n-i-1}$ from $p$ leads to a final state whereas reading it from $q$ doesn't.

III. Let's show that every state of $\mathcal{M}$ are reachable. We only need to construct a word $w\_q$ for each $q \subseteq Q$ such that the states that can be reached by reading $w\_q$ are exactly $q$ in the initial automaton $\mathcal{M}\_0$. I show you how to do it for $|q| = 2$ and then generalise. Assume $q = \\{i,j\\}$ with $i \< j$. Then we define $w\_q = a^{j-i}ba^i$. The only non-deterministic choice here is when $b$ is read. Either you decide to stay in state $j-i$ and then in the end you reach state $j$. Otherwise, you decide to backtrack to state $0$ and end up in state $i$.

Now let $q = \\{i\_1,\ldots,i\_k\\}$ with $i\_1 \< \ldots \< i\_k$. We define $w\_q = a^{i\_k-i\_{k-1}}ba^{i\_{k-1}-i\_{k-2}}b \ldots ba^{i\_2-i\_1}ba^{i\_1}$. Again, the only non-determinism comes from the letters $b$. You always have two choices: stay or reset to state $0$. If you always decide to stay, then in the end you reach state $i\_1+\sum\_{t=1}^{k-1}(i\_{t+1}-i\_t) = i\_k$.

Now assume the last time you decide to go back to state $0$ was at the $j$th occurrence of $b$ ($j \< k$). You can easily see that you reach state $i\_{k-j}$.

Thus, the exact set of states you can reach in $\mathcal{M}\_0$ by reading $w\_q$ is $q$. Thus, you reach state $q$ in $\mathcal{M}$.
> 1 votes

# Answer
Any regular language is accepted by arbitrarily large automata with no inaccessible states. Let $M = (Q, \Sigma, \delta, q\_0, F)$ be an automaton with no inaccessible states. For any natural number $n$, we can write $\[n\]=\\{0, \dots, n-1\\}$ and define a new automaton

$$M\_n = (Q\times \[n\], \Sigma, \delta\_n, (q\_0,0), F\times \[n\])\\,,$$

where $\delta\_n((q,i),\sigma) = (\delta(q,\sigma), i+1\bmod n)$ for any $q\in Q$, $i\in\[n\]$, $\sigma\in\Sigma$.

The effect is that each state counts modulo $n$ the number of characters that have been seen so far, but this has no effect on the behaviour of the automaton, other than making the state space bigger.

The automaton $M\_n$ might have inaccessible states, so delete them. But note that, after reading any word of length $0\leq \ell\<n$, the automaton is in some state of the form $(q,\ell)$, so at least $n$ states are accessible. Setting $n = 2^{|Q|}$ gives you an exponentially bigger automaton, but why stop there? :-)

Thanks to @holf for the elegant fix to the problem of the disconnected state space.
> 3 votes

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


# Question
Title: How many telescoping constructors will I have?
The Builder Pattern solves the problem of Telescoping Constructors; that is, having a single constructor for every possible parameter combination (including those combinations for which a parameter is omitted).

So for example:

```
  public Food(int id, String name) {
    this(id, name, 0, 0, 0);
  }

  public Food(int id, String name, int calories) {
    this(id, name, calories, 0, 0);
  }

  public Food(int id, String name, int servingSize) {
    this(id, name, 0, servingSize, 0);
  }

  public Food(int id, String name, int fat) {
    this(id, name, 0, 0, fat);
  }

  public Food(int id, String name, int calories, int servingSize) {
    this(id, name, calories, servingSize, 0);
  }
  public Food(int id, String name, int calories, int fat) {
    this(id, name, calories, 0, fat);
  }

  public Food(int id, String name, int servingSize, int fat) {
    this(id, name, 0, servingSize, fat);
  }

  public Food(int id, String name, int calories, int servingSize, int fat) {
    this(id, name, calories, servingSize, fat);
  }

```

If you set the Builder Pattern up properly, using the voluminous amount of code required, you can simply:

```
Food food = new FoodBuilder().SetName("Bananas").SetCalories(120).Build();

```

using any combination of parameters in any order.

Assuming that each parameter in the constructor *will always reside at the same relative location* while still allowing for omitted parameters, how would one calculate the number of constructors required given the number `n` of optional parameters needed?

(in the above example, `id` and `name` are required parameters, while `calories`, `servingSize`, and `fat` are all optional parameters).

# Answer
You'll need $2^n$ constructors. You need one constructor for each possible subset of optional parameters. There are $2^n$ such subsets. You have $n$ things, and there are $2^n$ possible ways to choose a set containing some number of those things.

For each subset of optional parameters, you'll write down a constructor for that subset; the arguments to that constructor will be fully determined (they must include all of the required parameters, and all of the optional parameters in the chosen subset, in the specified order).

---

That said, in Java, the "create many constructors" pattern doesn't *actually* work, for reasons having nothing to do with combinatorics or the number of constructors. You might notice that the type signature of the following two constructors is identical:

```
public Food(int id, String name, int calories, int servingSize) { ... }
public Food(int id, String name, int calories, int fat) { ... }

```

and that's not allowed in Java, because when the compiler sees an attempt to invoke the constructor (to instantiate the object) with a list of 4 parameters of type `int`, `String`, `int`, `int`, it won't know which of those two choices to choose. The approach only works if all of the optional parameters have different, incompatible types.
> 3 votes

---
Tags: software-engineering
---


title: Algorithms to correct misspelled word?

text:
# Question
Title: Algorithms to correct misspelled word?
At present, I am doing a project on *Optical Character Recognition (OCR)*. I am looking forward to improve the results by checking the output words of my OCR code with existing words from a text file. The file contains all English words.
Word is good to go if it exists in the file, but if it doesn't then I want to replace it with a word from the text file. Suppose the word in the image was "horse", and the OCR gives "hurze". Which algorithms should I use for detecting errors and their corrections.
I know that sometimes the correction depends on the context of the sentence. But, the thing is that I am not looking for 100% results. I just want to improve my results for OCR.
Can you suggest me anything else? I am looking forward to ideas.

# Answer
Standard OCR software already incorporates this idea: it has a corpus of words, along with their frequency of occurrence, and uses this to correct errors.

How does it work? OCR doesn't just output a letter at each position; it actually produces a probability distribution on letters. For example, its output might be something like: I'm 99% sure the first letter is a 'h'; I'm 60% sure the second letter is a 'u', but there's is a 20% chance it is a 'o', and a 15% chance it is an 'a', and so on. This lets you consider many possibilities for what the word might be, and combine the probabilities from the OCR with the frequency of occurrence of that possibility in English text to come up with an educated guess about what the actual word is.

For instance, if the OCR says "5% chance this is 'hurze", 2% chance this is 'horse'", and you know that 'horse' occurs 100x more often than 'hurze' in English language, you should guess that the corresponding word is probably 'horse', not 'hurze'.

As Yuval Filmus says, another approach is to look for a dictionary word that is within edit distance 1 or 2 of the raw output from the OCR.

If your OCR software is any good, it might already be doing this sort of correction. Sometimes you can give the OCR software a custom dictionary of words that tend to appear in your documents, to help it do this sort of correction.
> 3 votes

---
Tags: algorithms, strings, image-processing, dictionaries
---