# Question
Title: How to create RGB-colors with equal vector norm?
I am trying to do the following:

1. Interprete RGB color values as a 3-D vektor
2. Transform the RGB color into polar coordinates L, teta and phi
3. Create colors with constant L

The math behind this is the standard transformation into spherical coordinates:

```
b = L * Sin(teta) * Cos(phi)
r = L * Sin(teta) * Sin(phi)
g = L * Cos(teta)

```

With `L` beeing the norm of the RGB vektor I want to create.

```
L=(r^2+b^2+g^2)^0.5 'between 0 and 441.67 = sqrt(3)*255

```

So far so good. Onto the first issue: **r,g and b need to be between 0 and 255**

This means that this holds true (I calculated that myself, it's possible that it has errors in it):

```
If L>255 Then
   arccos(255/L) < teta < pi/2 - arccos(255/L)
   arccos(255/L) < phi < pi/2 - arccos(255/L)
End If

```

Here my calculations:

The idea is that teta goes from `(pi/4 - delta)` to `(pi/4 + delta)` where Which basically means that teta and phi are restricted in what they can be according to the ratio of `255/L`. This restriction gets upto a point were L=441.67 the maximum length. Here phi and teta can only be `pi/4`.

I think upto this points my conclusions are valid, but there is a problem I cannot figure out.

If `phi = teta = pi/4` and `L = 441.67` the RGB value should be `(255,255,255)` and the forumlas above yield: `RGB= (221,255,221)`

Which is what the forumlas for r,g and b above yield if `phi = teta = pi/4` and `L = 441.67` are inserted.

**So how would one generate RGB vektors with a constant norm that are still valid RGB values? (`0 < r,g,b < 255`)**

# Answer
> So how would one generate RGB vectors with a constant norm that are still valid RGB values? ($0 \le r,g,b \le 255$)

There is **a simpler algorithm**. Let $L$ be the given norm.

* Verify that $0\le L\le 255\sqrt3$.
* Let r be a random number between $\sqrt{L^2-\min(2\cdot255^2, L^2)}$ and $\min(255, L)$.
* Let $M=\sqrt{L^2-r^2}$. Let g be a random number between $\sqrt{M^2-\min(255^2, M^2)}$ and $\min(255,M)$.
* Let $b =\sqrt{L^2-r^2-g^2}$.

Some minor adjustment is needed if $r,g,b$ should be integers, in which case only approximate solutions can be found in general.

---

Here is the right computation if we want to find the range of $\theta$ and $\phi$.

* If $0\le L\le 255$, then $0\le\theta,\phi\le\pi/2$
* If $255\lt L\le 255\sqrt3$, let $M=\sqrt{\max(0, L^2-2\cdot255^2})$. we have $$\begin{align} &\quad\quad\begin{cases}b = L \sin(\theta) \cos(\phi)\\ r = L \sin(\theta) \sin(\phi)\\ g = L \cos(\theta)\\ 0\le b,r,g\le 255\\ 0\le\theta,\phi\le\pi/2 \end{cases}\\ &\Longleftrightarrow \begin{cases}b = L \sin(\theta) \cos(\phi)\\ r = L \sin(\theta) \sin(\phi)\\ g = L \cos(\theta)\\ \sqrt{\max\left(0,(L\sin(\theta))^2-255^2\right)}\le b,r\le \min(255,L\sin(\theta)) \\ M\le g\le 255\\ 0\le\theta,\phi\le\pi/2,\\, \theta\not=0 \end{cases}\\ &\Longleftrightarrow \begin{cases} \sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \cos(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\ \sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \sin(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\ \dfrac{M}{L}\le \cos(\theta)\le \dfrac{255}L\\ 0\le\theta,\phi\le\pi/2,\\, \theta\not=0 \end{cases}\\ &(\text{the inequalities on}\cos\phi\text{ put on the same restrictions on }\phi\\ &\text { as the inequalities on }\sin\phi)\\ &\Longleftrightarrow \begin{cases} \arccos\left(\min\left(1, \dfrac{255}{L\sin(\theta)}\right)\right)\le \phi\\ \phi\le\arccos\left(\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta)}\right)^2\right)}\right)\\ \arccos(\dfrac{255}L)\le\theta\le\arccos(\dfrac{M}{L}) \end{cases} \end{align} $$

The formula above tells a way to generate RGB vectors with a given norm $L$. Select $\theta$ and $\phi$ in the range given by the inequalities. Compute $r,g,b$ accordingly.

In particular, if you take $L=255\sqrt3=441.67$, then $\dfrac{255}L=\dfrac{M}L=\dfrac3{\sqrt3}$. $\theta=\arccos(255/L)=0.9553$. Since $\dfrac{255}{L\sin(\theta)}=0.7071$, we will get $\arccos(0.7071)\le \phi\le\arccos(0.7171)$. So $\phi=\pi/4$ and we will arrive at $b=255$, $g=255$ and $r=255$, which is the only possible combination of RGB vector for that value of $L$, as expected.

---

There have been several computational mistakes in the question. There has been a few in the previous versions of this answer as well. The comments below this answer might have become irrelevant.
> 5 votes

# Answer
Generate a random three-dimensional vector $v$ with non-negative components (you can generate each of the three components at random). Then, fix up the norm to be $L$ by setting

$$w = L \cdot {v \over \\|v\\|}.$$

Now $w$ will have norm $L$. Interpret $w$ as a RGB color.

Next, check that all three components of $w$ are in the range 0..255. If yes, you've got your RGB color. If not, throw it away and go back to the beginning and generate a new $v$, and repeat. (This is called rejection sampling.)
> 4 votes

---
Tags: colorings
---


# Question
Title: Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?
Is the following true or false? Why?

Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are of form $A \to BCD$ or $A\to a$ with $A, B, C, D \in V$ and $a\in$ $\Sigma$.

I don't know normal forms for context-free languages. Just the CNF for regular ones. Trying a few small examples don't gives me a generally valid response, if there are really always production rules of this form.

# Answer
Hint, can the production rules of that form generate a word of length 2? Is there a context-free language that contains a word of length 2?
> 2 votes

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


# Question
Title: Reducing the vertex cover problem to a variation of the vertex cover problem
The following variation on the vertex cover problem was given:

> Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$?

I was asked to prove that this problem is also $\mathsf{NP}$-hard. I am pretty sure that this can be done by using **Karp-reduction** from the original **vertex cover problem** to this variation.

That means that I would need some transformation function $f$ that would transform an instance of the vertex cover problem, $I = (V, E, k)$, to an instance of the above described problem, $f(I) = (V', E')$.

---

I am not sure how to come up with the proper transformation function, but this is what I think have figured out:

* Let $V = \\{v\_1, v\_2, ..., v\_n\\}$.
* Let $V' = V \cup V^+$, where $V^+ = \\{v\_{n+1}, v\_{n+2}, ..., v\_{4n}\\}$, because this would mean that the total size $|V'| = 4 \cdot |V|$.
* Let $E' = E \cup E^+$, where $E^+ = \\{\\{v\_i, v\_j\\} \mid v\_i \in V, v\_j \in V^+, j \in \\{n +i, 2n+i, 3n+i\\}\\}$. Basically, this means that each vertex in $V$ is connected to three different vertices in $V^+$ such that all vertices in $V^+$ are connected to exactly one vertex in $V$.

However, I am having a hard time proving the correctness of this reduction. I think I messed up the generation of $E'$, which would make the transformation function wrong. Anyone have an idea what the actual transformation function could be?

# Answer
> 2 votes
One note is that you'll have to use $k$ in your transformation.

---

Here's one approach that I think works:

We want some $G' = (V', E')$ that has a vertex cover of size $\le \frac{|V'|}{4}$ iff $G$ has a vertex cover of size $\le k$.

If $k = \frac{|V|}{4}$, just set $G' = G$.

When $k \neq \frac{|V|}{4}$, one idea is to add a disconnected graph $H$ to $G$, where we know the vertex cover size of $H$.

**Case 1**: $k \> \frac{|V|}{4}$. Then we want to add a graph with a small vertex cover. A star graph should do it. A star graph $H$ with $m$ vertices has vertex cover size $1$.

Set $G' = G \cup H$, a graph with $|V| + m$ vertices. It has vertex cover of size $\le k+1$ iff $G$ has a vertex cover of size $\le k$.

What should $m$ be? Let's solve

$$\frac{k + 1}{|V| + m} = \frac{1}{4}$$

This gives $m = 4(k+1)-|V|$. So when $k \> \frac{|V|}{4}$, add a disconnected $\[4(k+1)-|V|\]$-vertex star graph to $G$, and call the $\frac{|V|}{4}$ vertex cover algorithm on that. $\square$

**Case 2**: $k \< \frac{|V|}{4}$, we can add a complete graph with some properly chosen number $m$ vertices\*. Will leave it at that.

\*In this case when you solve for $m$, $m$ may not always be an integer; this can be dealt with by adding a $\lceil m \rceil$-vertex complete graph, which "overshoots" a bit, and then adding a small star graph

\[Let me know for further clarification/etc\]

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


title: Is this language L context-free?

text:
# Question
Title: Is this language L context-free?
The language

$$L = \\{x^r \\# y | x, y \in \\{a, b, c\\}^\*\\ \text{ and }x\text{ is a contiguous sub-string of }y\\}$$

where $x ^ r$ denotes the backward written word x, is context-free.

Can someone explain, if this statement is true? I am not able to construct a PDA, so I think the language is not context-free. Does anyone have an idea how to prove it?

# Answer
A more precise expression of the condition "$x$ is a contiguous substring of $y$" produces

$$L = \\{x^r \\# wxz | x, w, z\in \\{a, b, c\\}^\*\\}$$

That should make it clear that the language is context-free.
> 1 votes

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


# Question
Title: Does an optimal path imply the heuristic is admissible?
If we are given an A$^\*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?

# Answer
> 3 votes
No.

Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1.

We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)\>1$.

However, using $A^\*$ search algorithm, we will end up with the path $s, t$, the unique and, hence, optimal path.

---

**Exercise.** Construct a counterexample where there are more than one path.

# Answer
> 2 votes
The solution provided by Apass Jack is absolutely correct but beyond simple examples proving that the answer is "definitely no", let me add another consideration (which actually provides a solution to the exercise suggested by Apass Jack):

*A heuristic which is inadmissible does not necessarily mean that paths found by A$^\*$ with that heuristic should be sub-optimal*

The reason is that **heuristics serve for the purpose of ranking nodes**. Admissibility simply implies that if two nodes are wrongly ranked (so that one node gets expanded before the correct one) this will have a limited effect in the number of subsequent expansions as A$^\*$ will never expand nodes beyond the $f$-layer that contains the optimal solution (provided that the heuristic is admissible, which is the hypothesis in this paragraph).

Consider now the case where one heuristic is inadmissible but always (always!) ranks nodes perfectly. Then, certainly nodes will get sorted in the open list in their optimal order and the optimal solution is necessarily found.

To see this consider a perfect heuristic function, $h^\*(n)$ and now and inadmissible heuristic function which adds a large constant $M$ to $h^\*(n)$, $h(n)=h^\*(n)+M$. Well, $h(n)$ is clearly inadmissible for values of $M$ arbitrarily large, but if one node $n$ has an $h^\*$-value strictly less than another $n'$, then it will be perfectly ranked by the perfect heuristic function, $h^\*$, so does $h()$ because adding the same constant $M$ does not alter the ordering.

So far, the solution to the exercise suggested in the other reply is simply the following: take *any* graph $G(V, E)$ and compute $h^\*(n), \forall n\in V$. Construct now a new heuristic function $h(n)=h^\*(n)+M$ for all $n\in V$ with a constant $M$ arbitrarily large, run A$^\*$ ... and smile! :)

Hope this helps,

---
Tags: artificial-intelligence, heuristics, a-star-search
---


# Question
Title: Is there a way a proving a language regular/non-regular that works for every possible language?
In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-regular, while proving languages regular revolves around building a DFA, or using the Myhill-Nerode theorem. All of these approaches fail for some language. Is there some approach that will work for all regular/non-regular languages?

# Answer
> 4 votes
No, there isn't. It is undecidable, even for context-free languages. It is decidable for *deterministic* context-free languages.

References are easy to find with Google; for instance,

# Answer
> 1 votes
Yes. Myhill–Nerode works for every language: every regular language has a finite number of equivalence classes, and every non-regular language has an infinite number.

However, there is no general method for actually using Myhill–Nerode. Like all mathematical proofs, creativity is needed to find the equivalence classes. As reinierpost says, there is no algorithm you can use to determine whether a context-free grammar produces a regular language (i.e., one with a finite number of Myhill–Nerode classes).

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


# Question
Title: Behavior of specific PDA for a certain input
Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push $b$ to the stack, but when we read $a$ I get confused. My assumption is that we fork into two new branches - one in which $b$ was popped and one in which $a$ was pushed. Is this correct? If not, can you tell me where I go wrong?

Thank you very much!

# Answer
> 0 votes
This PDA is non deterministic. So just like in non-deterministic Finite State Machines you fork.

A string is only accepted by the PDA if one of the forks ends in an accepting state.

---
Tags: complexity-theory, finite-automata, pushdown-automata
---


# Question
Title: Maximum number of nodes connected when the link has a large buffer
A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream;when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle,which is the ratio of on-time to off-time, is 1 : 2Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that there is no data loss is\_____.

My solution manual claims that the max. no of nodes connected can be found out by dividing total link capacity from expected bandwidth utilization.

I dont understand why we need to take the expected bandwidth. Why can't we simply use the maximum bandwidth utilization?

Thanks in advance!

# Answer
> 1 votes
You can have ten of them going at once. If they're on a third of the time and you decree that, for instance, ten operate for twenty seconds, then the next ten, then the next ten, then you can have thirty of them total.

If you just focused on the max you'd think that you could only have ten (which would be the case if you weren't able to synchronize them, and thus couldn't rule out that they might all try to talk at once.)

By averaging over the available time you can get the same result without having to speculate about how exactly to schedule them. Over its uptime, each node transmits at an average of 3+1/3 Mbps. Dividing 100 MBps by this number gives 30.

---
Tags: computer-architecture, computer-networks
---


# Question
Title: Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C\_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$. In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $\mathcal C\_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a $\\{0,1,\\}$-sequence could be considered a subset of $\mathbb N$, and going from to $\mathbb N$ to $\Sigma^\*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $\mathcal C\_T$ some machine is enumerated for it.

But I noticed that also the complement of $C\_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:

Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $\Sigma^{\ast} = \\{w\_1, w\_2, w\_3, \ldots \\}$ and $c : \mathbb N \to \mathbb N \times \mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, \ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w\_j$ for $k$ steps, if $k \> T(|w\_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.

A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).

Hence it accepts the complement of $\mathcal C\_T$. So both sets are recursively enumerable, hence the set $C\_T$ is recursive/decidable.

Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...

# Answer
> 3 votes
This is a situation where coding is non-trivial. $\mathcal{C}\_T$ is a class of decidable languages. To make sense of $\mathcal{C}\_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.

So what does it mean for $\mathcal{C}\_T$ to be recursively enumerable? It means that we can effectively produce a list $(M\_i)$ of TMs such that $\\{L(M\_i) \mid i \in \mathbb{N}\\} = \mathcal{C}\_T$. Note that this does not give us that $\mathcal{C}\_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $\mathcal{C}\_T$.

The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.

Furthermore, the complement of $\mathcal{C}\_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.

# Answer
> 1 votes
Just let me add some additional insights after thinking about it. Let $T(n)$ be some computable function.

Define $$ \mathcal A = \\{ M \mid \mbox{ $M$ is a TM which halts in $T(n)$ steps for each input of size $n$}\\}. $$ Then $\mathcal C\_T = \\{ L(M) : M \in \mathcal A \\}$. As shown in my post the complement of the set $\mathcal A$ is recursively enumerable (and by the way we are working with strings, hence have decidable equality between elements). But here we do not have recursive enumerability of the set $\mathcal A$ itself (where for $\mathcal C\_L$ we have). This follows from Rice's Theorem as here the non-trivial property mentioned in the article is $\mathcal C\_L$ (strictly we have to show that $\mathcal C\_L$ is non-trivial first, but this I take for granted now).

Note by the way that the complement of $\mathcal C\_T$ is not even enumerable. But what we mean when we say $\mathcal C\_T$ is recursively enumerable is that we can enumerate some representation in terms of machines for it. Then Rice's Theorem talks about the complement in terms of these codes, i.e. the relative complement with respect to the set $\\{ L(M) \mid M \mbox{ is some TM } \\}$.

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


# Question
Title: Simple algorithm for IEEE-754 division on 8-bit CPU?
IEEE Std 754-2008 is the modern definition of Floating-Point Arithmetic. It requires that division (among other operations) performs

> as if it first produced an intermediate result correct to infinite precision (..), and then rounded that intermediate result, if necessary, to fit in the destination’s format.

I ask for a ***simple*** algorithm performing that operation, tailored to 8-bit CPUs with 8x8-\>16 bit multiplier; speed is a second(ary) criteria.

For simplicity I restrict to binary32 type

Image credit: wikipedia

and positive "normal" input with exponents such that no overflow or underflow occurs (so that we can ignore any sign or exponent consideration beyond some limited final exponent adjustment according to the result of the division), and rounding to nearest even:

> the floating-point number nearest to the infinitely precise result shall be delivered; if the two nearest floating-point numbers bracketing an unrepresentable infinitely precise result are equally near, the one with an even least significant digit shall be delivered.

I ask because I strongly suspect that the AVR libc implementation of `float` division (typically used on the Arduino Uno) deviates from the standard beyond being locked to roundTiesToEven, and I wonder how hard it would be to fix that. The current code seems to be divsf3, which invokes divsf3x to perform the division to apparently 40-bit mantissa, then rounding with fp\_round. Isn't that very sketch doomed, BTW?

# Answer
> 5 votes
When using properly-rounded higher-precision floating-point arithmetic to compute operations in lower-precision arithmetic, there is the potential issue of *double rounding*: The result is first rounded to the higher precision, then rounded again during conversion to the lower precision. This *can* lead to incorrect results, but that is not always the case.

Samuel Figueroa, "When is double rounding innocuous?", *ACM SIGNUM Newsletter*, Vol. 30, No. 3, July 1995, pp. 21-26

shows that in the case of floating-point division, the higher-precision format needs to have twice the precision of the lower-precision format to avoid issues due to double rounding. This conditions is satisfied were we to use IEEE-754 `binary64` to perform the division, then round the result to IEEE-754 `binary32`. On the other hand, if the higher precision uses 40 mantissa bits, its precision is less than twice that of `binary32`, so some incorrect results due to double rounding would be expected.

However, from the description in the question it doesn't sound like this is the case. Rather, it seems that there is an internal computation that computes many more quotient bits than are strictly necessary, and this *un-rounded* result is rounded *once* to get the `binary32` result. After normalization of dividend and divisor a correctly rounded `binary32` division requires a total of 25 quotient bits (24 bits for the significand including the integer bit that is implicit in the stored format, plus a *round* bit), plus a *sticky* bit that is the OR of all other potential quotient bits.

Note that we don't have to compute the potentially infinite number of quotient bits in order to determine the value of the sticky bit. It suffices to know whether the remainder after computation of 25 quotient bits is zero or not. A zero remainder means the sticky bit is zero, a non-zero remainder means the sticky bit is one. The rounding in nearest-or-even mode requires three pieces of information: the least significant bit of the significand, the round bit, and the sticky bit. The significand needs to be increased when either (1) the round bit is set and the sticky bit is set or (2; *tie case*) the round bit is set, the sticky bit is clear, but the LSB of the significand is set (meaning it is odd).

Conceptually, for division in a semi-logarithmic floating-point format one needs to subtract the exponents and divide the significand. The conceptually simplest way to perform the latter operation is to perform binary long-hand division. In each step, one compares the current remainder with the divisor. If it is greater than or equal to the divisor, the next quotient bits is one and one can subtract the divisor from the remainder. Then double the remainder for the next step.

Using a small 8x8-\>16 bit multiply would conceptually be much more involved. One would either build a narrow division operation from this building block and perform a high-radix long-hand division (e.g. base 256), or build a much wider multiplication operation with is then used to compute the quotient with a Newton-Raphson iteration for the reciprocal, using fixed-point computation. In the latter case, the rounding is more involved as an accurate remainder does not fall naturally out of the computation. In addition, a table of starting approximations, say 8 bits, for the reciprocal is typically needed. The following research report discusses relevant trade-offs in the context of the 8-bit Kestrel processor:

Eric Rice and Richard Hughey, "Multiprecision division on small-word parallel processors: Expanded Version". University of California Santa Cruz, April 1998 (online)

I incorporated the above algorithmic sketch into the (tested) ISO-C code below. This code is written for clarity and does not incorporate various obvious optimizations, however I have tried to minimize the size of variables under the assumption that the asker's platform has support for 8-bit operations and limited support for 16-bit operations, similar to a Z80.

```
#include <stdint.h>

#define SIGN_MASK     (0x80000000)  /* sign bit of IEEE-754 binary32 format */
#define EXPO_MASK     (0x7f800000)  /* exponent bits of IEEE-754 binary32 */
#define MANT_MASK     (0x007fffff)  /* significand bits of IEEE-754 binary32 */
#define MANT_INTBIT   (0x00800000)  /* where integer bit would be if stored */
#define QNAN_BIT      (0x00400000)  /* distinguishes QNaN from SNaN */
#define INFTY         (0x7f800000)  /* infinity */
#define INDEFINITE    (0xffc00000)  /* special QNaN */
#define MAX_NORM_EXPO (254)         /* maximum biased exponent for normals */
#define MIN_NORM_EXPO (1)           /* minimum biased exponent for normals */
#define EXPO_BIAS     (127)         /* exponent bias IEEE-754 binary32 */
#define MANT_BITS     (24)          /* effective # of mantissa bits binary32 */
#define QUOT_BITS     (MANT_BITS+1) /* one extra bit for rounding */
#define EXPO_SHFT     (MANT_BITS-1) /* integer bit is implicit */
#define ROUND_BIT     (1)           /* mask for round bit in 25-bit quotient */
#define MANT_LSB      (2)           /* mask for significand lsb in quotient */

uint32_t fp32_div_kernel (uint32_t a, uint32_t b)
{
    uint32_t r, x, y, sign;
    uint16_t expo_x, expo_y, expo_res;
    uint8_t i, odd, rnd, sticky;

    /* extract biased exponents and sign bits */
    expo_x = (a & EXPO_MASK) >> EXPO_SHFT;
    expo_y = (b & EXPO_MASK) >> EXPO_SHFT;
    sign = (a ^ b) & SIGN_MASK;

    if ((expo_x >= MIN_NORM_EXPO) && (expo_x <= MAX_NORM_EXPO) &&
        (expo_y >= MIN_NORM_EXPO) && (expo_y <= MIN_NORM_EXPO)) { /* fast path */
divide:
        /* extract significands */
        x = (a & MANT_MASK) | MANT_INTBIT;
        y = (b & MANT_MASK) | MANT_INTBIT;
        /* compute exponent of result */
        expo_res = expo_x - expo_y + EXPO_BIAS;
        /* dividend may not be smaller than divisor: normalize */
        if (x < y) {
            x = x << 1;
            expo_res--;
        }
        /* generate quotient one bit at at time */
        r = 0;
        for (i = 0; i < QUOT_BITS; i++) {
            r = r << 1;
            if (x >= y) {
                x = x - y;
                r = r | 1;
            }
            x = x << 1;
        }
        /* OR remainder bits into sticky bit */
        sticky = (x != 0);
        if ((expo_res >= MIN_NORM_EXPO) &&
            (expo_res <= MAX_NORM_EXPO)) { /* normal, may overflow to infinity*/
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
            /* combine exponent and significand */
            r = ((uint32_t)expo_res << EXPO_SHFT) + (r - MANT_INTBIT);
        } else if ((int16_t)expo_res > MAX_NORM_EXPO) { // overflow: infinity
            r = INFTY;
        } else { /* underflow: result is zero, subnormal, or smallest normal */
            uint8_t shift = (uint8_t)(1 - expo_res);
            /* clamp shift count */
            if (shift > QUOT_BITS) shift = QUOT_BITS;
            /* OR shifted-off bits of significand into sticky bit */
            sticky = sticky | ((r & ~(~0 << shift)) != 0);
            /* denormalize significand */
            r = r >> shift;
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
        }
        /* combine sign bit with combo of exponent and significand */
        r = r | sign;
    } else { /* slow path */
        /* take absolute value of arguments */
        x = a & ~SIGN_MASK;
        y = b & ~SIGN_MASK;
        /* if dividend is a NaN, convert that NaN into a QNaN and return it */
        if (x > INFTY) return a | QNAN_BIT;
        /* if divisor is a NaN, convert that NaN into a QNaN and return it */
        if (y > INFTY) return b | QNAN_BIT;
        /* dividend and divisor are both zero or infinity: invalid operation */
        if (((x == 0) && (y == 0)) ||
            ((x == INFTY) && (y == INFTY))) return INDEFINITE;
        /* 0/y or x/INF -> 0 */
        if ((x == 0) || (y == INFTY)) return sign;
        /* x/0 or INF/y -> INF */
        if ((y == 0) || (x == INFTY)) return sign | INFTY;
        /* if dividend is a subnormal, normalize it */
        if (expo_x == 0) {
            expo_x++;
            do {
                a = a + a;
                expo_x--;
            } while (!(a & MANT_INTBIT));
        }
        /* if divisor is a subnormal, normalize it */
        if (expo_y == 0) {
            expo_y++;
            do {
                b = b + b;
                expo_y--;
            } while (!(b & MANT_INTBIT));
        }
        /* now that dividend and divisor are normalized, do the division */
        goto divide;
    }
    return r;
}

```

---
Tags: arithmetic, floating-point
---


# Question
Title: Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?
Prove: $\left \\{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \\}$ is regular.

Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?

# Answer
> 6 votes
$(n-m)\bmod 5$ can only be $0,1,2,3,4$. So intuitively, the language in the question is a regular language. We can show that conclusion rigorously in the following two ways.

### Regular expression

The simplest way is to verify that the language is described by the following regular expression.

$$(00000)^\*(\epsilon+01+0011+000111+00001111)(11111)^\*.$$

Intuitively, the language consists of words each of which is zero or more five 0s, followed by some number of 0s, followed by the same number of 1s, followed by zero of more five 1s.

---

### Minimal DFA

Here are the states of the minimal DFA for this language.

* $Z\_{0}$, which represents words each of which is zero or more five 0s.
* $Z\_{1}$, which represents words each of which is zero or more five 0s, followed by 0.
* $Z\_{2}$, which represents words each of which is zero or more five 0s, followed by 00.
* $Z\_{3}$, which represents words each of which is zero or more five 0s, followed by 000.
* $Z\_{4}$, which represents words each of which is zero or more five 0s, followed by 0000.
* $S\_{0}$, which represents words each of which is zero or more five 0s, followed by nothing or 01 or 0011 or 000111 or 00001111, followed by zero or more five 1s, ending with 1.
* $S\_{1}$, which represents words each of which is zero or more five 0s, followed by 0 or 001, or 00011 or 0000111 or 1111, followed by zero or more five 1s, ending with 1.
* $S\_{2}$, which represents words each of which is zero or more five 0s, followed by 00 or 0001 or 000011 or 111 or 01111, followed by zero or more five 1s, ending with 1.
* $S\_{3}$, which represents words each of which is zero or more five 0s, followed by 000 or 00001 or 11 or 0111 or 0001111, followed by zero or more five 1s, ending with 1.
* $S\_{4}$, which represents words each of which is zero or more five 0s, followed by 0000 or 1 or 011 or 00111 or 0001111, followed by zero or more five 1s, ending with 1.
* $R$, which represents all other words, which are words that are not of the form $0^\*1^\*$.

In other words, besides the "rejecting" state $R$ that behaves as a black hole, we have, for $i=0,1,2,3,4$,

* a state $Z\_i$ which represents words of the form $0^\*$ whose number of 0s is the same as $i$ modulo 5.
* a state $S\_i$ which represents words of the form $0^\*1^\*1$ whose number of 0s is the same as $i$ plus its number of 1s modulo 5.

It should be not be difficult for you to figure out the initial state, the accepting states and the transitions between the states.

---

> Is it reasonable to get a DFA with at least 30 states for this language?

It is totally fine if you can construct a DFA with 30 states or 2019 states for this language. That will show the language is regular.

On the other hand, it is sometimes interesting or helpful or challenging to find the DFA with the minimal number of states. For this language, 11 states is the minimum.

---

Here are two related exercises.

**Exercise 1.** Show $\left \\{ 0^m1^n \mid (n-m) \bmod 5=2 \right \\}$ is a regular language. How many states are there in the minimal DFA for it?

**Exercise 2.** Show $\left \\{ 0^k1^m2^n \mid (k+m-n) \bmod 2=0 \right \\}$ is a regular language. How many states are there in the minimal DFA for it?

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


title: D - Latch or D Flip Flop?

text:
# Question
Title: D - Latch or D Flip Flop?
I have a diagram (https://i.stack.imgur.com/UK16E.jpg) where it is either a D Latch or D Flip Flop. I am trying to figure out which one it is and why. If it is a D Flip Flip, I also need to know which input is the clock. Can someone help me out ?

# Answer
This feels like a homework question, but I'll at least try to point you in the right direction.

The difference between a latch and a flip-flop is that a flip-flop is clocked. At first glance, I thought it was a latch since there was no clock labelled as such, but this might not actually be the case. The clock is an input that will determine when the state of the flip-flop can change, so take a look at both of your inputs and figure out what will happen to the main RS latch (the two gates on the right) in each case. In particular, your A input catches my eye since it's directly tied to the two gates directly tied to your main RS latch.

Keeping these in mind may help:

NAND RS latch truth table:

D flip-flop excitation table:

$$\begin{matrix} Q & Q(t+1) & D \\ 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{matrix}$$
> 2 votes

# Answer
A D flip-flop has a clock input (else it would not be a flip=flop) and a data input D. There are also gated D flip-flops which have a a gate input--the clock and data inputs are ignored unless the gate is enabled.
> 0 votes

---
Tags: computer-architecture, digital-circuits, sequential-circuit
---


# Question
Title: Can memoization be applied to any recursive algorithm?
I am new to the concepts of recursion, backtracking and dynamic programming.

I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there is a relation between memoization being applicable ONLY to top down recursive algorithms. Any explanation on the same would be greatly appreciated.

**The Background to this question:**

I have a naive inefficient recursive solution(below) a and wish to incorporate memoization but don't know if it is possible.

**Problem Statement: Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, Print the number of ways (non-distinct sets) this can be achieved.**

```
Ex: Ex: N = 4 , S = {1, 2, 3}

1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

```

My code:

```
public static int change(int n, int count, int sum) {

        if(sum == n) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        for(int i = 1; i <=3; i++) {
            sum = sum + i;
            count += change(n, 0, sum);
            sum = sum - i;
        }
        return count;
    }

```

# Answer
> 1 votes
Memoization can be applied to any function. Whether it helps with a given program or not depends on how often the function is called with the same parameters.

You don't specify what your recursive solution is. Typically for this problem is imagine something like

```
change(total, denominations) = sum of change(total - k m, denominations \ m) where m = max(denominations) over k m <= total

```

Can `change` be called with the same arguments more than once? Yes. For instance if you're trying to make change for $1 you might take two quarters and one dime or you might take no quarters and six dimes. In either case you'll next be asking for the numbers of ways to make forty cents with a dime and a nickel. So you can save something by calculating this once and storing the result.

---
Tags: algorithms, recursion, backtracking, memoization
---


title: Camera calibration without grid

text:
# Question
Title: Camera calibration without grid
Ususally a grid pattern (circles or squares) is used for camera calibration. Features (circles or corners) are detected in a function (e.g. findCirclesGrid in OpenCV) and passed to the a camera calibration function (e.g. calibrateCamera in OpenCV) together with corresponding object points (object coordinates).

1. Is it possible to calibrate a camera with circles which are "randomly" spread on a plane (object coordinates known)?
2. If yes, how does it affect the feature detection, i.e. findCirclesGrid? Is it less accurate?
3. If yes, how does it affect the calibrateCamera function? Can all parameters such as distortion for example still be computed?

# Answer
> 1 votes
Yes. Any known pattern can be used for camera calibration, if you know the ground-truth shape. You just need to have a number of points where you know (a) their location in the image and (b) their location in the physical world. The procedure is simplest with a grid, so if you're choosing a pattern, might as well stick to that standard (why not?).

Questions about implementation and OpenCV are off-topic here, though.

---
Tags: computer-vision
---


# Question
Title: Fine-grained complexity of 3-CNF formula evaluation
It's well known that 3-SAT is in NP, which means that one can evaluate a 3-CNF formula in polynomial time. However, I was wondering what the tightest upper bound is for formula verification, expressed in big-O notation or some other way.

My best guess is that 3-CNF formulas can be verified in linear time in the number of clauses. Each clause has two disjunctions and up to three negations, which should each require one step to evaluate. If you count replacing a literal with its assigned value as a step, that gives you at most 8 steps per clause. Then, once all the clauses are evaluated, you should need \[# of clauses\] - 1 steps to compute all the conjunctions between them. So with $x$ clauses, that's at most $8x + x - 1 = 9x - 1$ steps total, which is $O(x)$.

Obviously, if I'm wrong about that, please let me know, and if there are even better time bounds (either theoretical or practical), I would love to hear about those as well.

# Answer
> 2 votes
Yes, you are correct. Your analysis is fine. It takes linear time.

It's also easy to see that it's not possible to do better than linear time: any algorithm will have to read the entire input (in the worst case), which itself takes linear time.

---
Tags: time-complexity, satisfiability, decision-problem, 3-sat, sat-solvers
---


# Question
Title: What would show a human mind is/is not reducible to a Turing machine?
In computer science it is often assumed that a human mind can be reduced to a Turing machine. This is the assumption that underlies the field of artificial intelligence.

However, it is an assumption, one that has neither been proven or disproven.

Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

If not, is there any evidence that would suggest one way or another?

Here is a similar question I asked awhile back on theoretical computer science:

https://cstheory.stackexchange.com/questions/3170/human-intelligence-and-algorithms

# Answer
> -2 votes
If we identify a certain task that is non-computable, but the human mind perform, then this proves the human mind is not a Turing machine.

As an example, Turing machines cannot make the distinction between proof and truth. Yet, we humans can, as with the statement "this statement is unprovable," which is true but unprovable.

# Answer
> 1 votes
To answer your question:

> Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

The Turing test was conceived as a way to test a particular special case of this assumption: it gives us a way to test whether a *particular* AI system is successful at behaving indistinguishably from a human. Thus, this would give a plausible way to prove the assumption -- *if* we could come up with an AI system that is good enough to pass the Turing test. Unfortunately, that's something we haven't been able to do, yet.

# Answer
> 1 votes
> In computer science it is often assumed that a human mind can be reduced to a Turing machine.

Since when? I've read a lot of computer science papers and never once encountered this assumption.

> This is the assumption that underlies the field of artificial intelligence.

Not really. I think artificial intelligence can exist independently of the ability to emulate human intelligence. Deep Blue beat Kasparov, and we're pretty sure it didn't do it by emulating human thought processes.

> However, it is an assumption, one that has neither been proven or disproven. Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

I personally suspect the assumption is true. I think it could only be proven by constructing a computer simulation of a particular human's brain and asking a series of questions, both of the human and of the simulated version, and seeing if the answers are indicative of a similar level of skill and knowledge. I would not expect the answers to be identical, even if the simulation is highly accurate. Constructing a computer simulation of a human brain is not remotely feasible at present.

> If not, is there any evidence that would suggest one way or another?

With accurate equations, we expect a TM to be, in principle, capable of simulating any physical system, including in particular a human brain. The hard parts are (1) having correct quantum mechanics equations and (2) data acquisition of the initial state of a human brain. While these are not feasible today, there's no reason to believe they cannot be done in principle. Note we assume human thought is "reducible" to a TM even if the simulated brain is way slower than a real brain.

# Answer
> 0 votes
The trivial answer is "no" because the Turing machine has infinite memory and no human can.

Since a computer can be made entirely of NAND gates, and the human neurology can implement NAND gates, it is theoretically possible that a Turing-machine-with-limited-memory could be built from neurons.

It may be that *being conscious* is what it is like to be the on-board computer implemented by neurology.

# Answer
> -3 votes
IF (a big "if" here) consciousness is based on quantum-level phenomena, (as researched by Roger Penrose, et al), then the mind is not deterministic as is a digital computer. What is the phenomena of how multiple simultaneous states collapse? Is it mechanistic?

---
Tags: turing-machines, artificial-intelligence, computer-vs-human
---


# Question
Title: Examples of logic gates using non-standard models
These are the only ones I have been able to find online:

I would like to find some more discrete models like these (as opposed to say, *water* logic gates or things like that). Not sure if there is a library of different techniques to build logic gates outside of electronics, or if not, what some other good examples are like these above, that perhaps demonstrate further their functionality.

# Answer
> 3 votes
Picture hanging can realize any monotonone boolean function.

I.e., you can hang a picture using two pins so that it falls IFF both pins are removed. This is trivial to achieve, and realizes an AND gate.

However, you can also hang it so that it falls IFF either pin is removed. Implementing this OR gate is not so trivial at first.

See the linked paper for nice pictures.

---
Tags: computer-architecture, logic, computation-models
---


title: Terminology First-Order Logic

text:
# Question
Title: Terminology First-Order Logic
A graph $G$ is said to be a model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x\_1,...,x\_r)$ be a first order formula with free variables $x\_1,...,x\_r$. What is the standard terminology for a tuple of vertices $(v\_1,...,v\_r)$ of $G$ such that $G$ satisfies the formula $\varphi(v\_1,...,v\_r)$ obtained by substituting $x\_i$ with $v\_i$?

What I'm having trouble is to find the right terminology to connect $G$ to the assignment. The only thing I can think now is the following.

"$(v\_1,...,v\_r)$ is a satisfying assignment for $\varphi$ in $G$."

But maybe there is a shorter way.

# Answer
I think that's often called a "variable assignment", since it assigns to each variable a value (a vertex in the graph, in your case).

If the graph is equipped with a set of such tuples, these might be considered to be *hyperedges*, i.e. edges connected to an arbitrary number of vertices (not necessarily two of them).
> 3 votes

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


title: Infinite Huffman Tree

text:
# Question
Title: Infinite Huffman Tree
We have to derive an optimal binary encoding for the infinite set of symbols $\\{s\_1, s\_2, \dots \\}$. Their distribution is given by $$p(s\_i) = 9 \cdot 10^{-i}$$

My intuition was to use a Huffman encoding. Obviously the Huffman encoding algorithm needs to first find the smallest two elements, which we can't do. But, if we imagine the last step of the Huffman algorithm, it would have the two elements $s\_1$ and the supersymbol $s\_2s\_3s\_4\dots$ with probabilities $0.9$ and $0.1$ respectively. Thus, (if left is $0$ and right is $1$) symbol $s\_1$ would get codeword $0$. The other symbols would all get a codeword starting with $1$. This tree is clearly self similar. If we represent binary trees as tuples with an empty tree as the nullset $\varnothing$, we have that this tree is given by

$$ T = (\varnothing, T) $$

That is, a left branch which is empty an the right branch which is identical to the whole tree. Thus, we get the codewords

$$ s\_1 \mapsto 0, s\_2 \mapsto 10, s\_3 \mapsto 110, s\_4 \mapsto 1110, \dots $$

Now, I know that these are optimal. You can do a proof by contradiction showing that changing any of these codewords and still satisfying the Kraft inequality will cause the expected length to increase.

My question is, is the fact that this infinite Huffman tree arrived at the answer a coincidence or is there a way to formalize Huffman encoding for an infinite set of symbols.

# Answer
> 4 votes
I don't think there is an algorithm that works for any infinite probability distribution. However, you have taken the case of a geometric distribution for which there happens to be a neat answer. It was proposed by Gallager in this paper \[1\]. So if you apply his algorithm, you will see that you obtain exactly the same answer you proposed.

---

\[1\] Gallager, R., & Van Voorhis, D. (1975). Optimal source codes for geometrically distributed integer alphabets (corresp.). *IEEE Transactions on Information theory, 21*(2), 228-230.

# Answer
> 1 votes
You already have an infinite sequence for the infinite Huffman encoding.

What is the average codeword length? Does that tell you anything more?

---
Tags: information-theory, huffman-coding
---


# Question
Title: Why more and more handcraft lex do not use regular expression any more?
Recently I read the source code of Clang, and found that it just do the lex thing by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "Compilers Principles, Techniques, and Tools" take lots time to illustrate how to build a regular expression state machine, and I remember the tool Flex also build a state machine (correct me if I'm wrong). I think it's easy to lost in the manually matching code and if there's something changed in a language, it is a little difficult to update the matching code.

So why nowadays people prefer to manually do the matching rather than use regular expression? Is this because the table generated by the regex tool too big if the token table is complicated? Or is this an efficiency trade-off?

p.s. Evidence for "more and more":

* Clang
* Gcc (as long as they abandoned flex/bison)
* OpenJDK
* Python
* Protobuf

What interesting is, the author of protobuf wants to use regular expression, but give up due to open source project get better keep independent, I think this counts a reason.

# Answer
> 4 votes
While I cannot give you a definitive answer, but I think there are a couple of reasons for handcrafting lexers and parsers:

* Good error reporting and recovery: most of tools such as Lex that provide a declarative way of defining regular expressions are hard to customize for error reporting or recovery. When you hand-craft your lexer or parser, you have more control when you encounter an error.
* Performance: while Lex is using Finite State Automata in their lexers, and they are efficient (assuming the automata can be loaded in memory) it may pay off to handcraft your lexer to have a tight control on both runtime and memory usage. Most regular expression engines in programming languages use backtracking and may have exponential worst case runtime.
* Infrequent changes: the token definitions (and even syntax) of programming languages doesn't change that often. So I think in the prototyping phase it makes sense to use a tool to automate the process, but when the syntax became stable, it will pay off to handcraft the lexer and parser, both in terms of error reporting and performance.

---
Tags: compilers
---


# Question
Title: Boolean variable that captures whether an inequality holds
I have an integer linear program with variables $x\_1,\dots,x\_n$. I have an inequality $a\_1 x\_1 + \dots + a\_n x\_n \ge b$ that I care about; it may or may or not hold.

I want to introduce a boolean variable $y$, with the intent that $y=1$ if this inequality holds or $y=0$ if it doesn't. How can I write linear inequalities to constrain $y$ to take this value?

All of $a\_1,\dots,a\_n,b$ are constants. I know upper and lower bounds for all of the $x\_i$'s.

# Answer
Add the inequalities

$$\begin{align\*} a\_1 x\_1 + \dots + a\_n x\_n &\ge b - M (1-y)\\ a\_1 x\_1 + \dots + a\_n x\_n &\< b + M y, \end{align\*}$$

where $M$ is chosen sufficiently large.

Why does this work? If $y=1$, then the first inequality forces $a\_1 x\_1 + \dots + a\_n x\_n \ge b$ to hold. If $y=0$, then the second inequality forces $a\_1 x\_1 + \dots + a\_n x\_n \< b$ to hold, i.e., $a\_1 x\_1 + \dots + a\_n x\_n \ge b$ to be false.

How large does $M$ need to be? If the $x\_i$'s are zero-or-one variables, then it suffices to take $M$ to be at least $\max(b,a\_1+\dots+a\_n-b+1)$. In general, if you have upper and lower bounds for each $x\_i$, you can derive how large $M$ needs to be.
> 4 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: How to model a logical indicator when two inequalities hold in Integer Programming?
I have an IP program where $\forall i \in I, j \in J$ my decision variables are $x\_{i,j}$. I have two sets of inequalities (one inequality for every $i,j$ pair) that are of interest which are $$a\_{i,j} x\_{i,j} \geq 1 \ \ \ \ \forall i \in I, j\in J$$ and $$ \sum\_{j \in J} b\_{i,j}x\_{i,j} \leq b\_{i,j}- 1 \ \ \ \ \forall i \in I, j\in J$$

I now want to introduce a logical indicator variable $\delta\_{i,j}$ which equals 1 if and only if both of the inequalities are true and 0 else. How could I implement this idea by introducing appropriate constraints for my Integer Progamming model? I was thinking about defining a variable $\delta^1\_{i,j}$ and $\delta^2\_{i,j}$ which equals 1 iff the first and second inequality are true respectively and then maybe combine these two auxiliry logical variables into a single variable $\delta\_{i,j}$, but I couldn't figure out exactly how to make this work.

# Answer
Your general approach is a good one. Use Boolean variable that captures whether an inequality holds to define $\delta\_{i,j}^1$ and $\delta\_{i,j}^2$. Then, use Express boolean logic operations in zero-one integer linear programming (ILP) to define $\delta\_{i,j}$ in terms of $\delta\_{i,j}^1$ and $\delta\_{i,j}^2$ (via a logical-AND operation).
> 1 votes

---
Tags: integer-programming, constraint-programming
---


# Question
Title: Don’t understanding argument on words of a certain form
In my book they use the following argument which I don’t understand :

> Let $L$ be a langage such that there is $m\_1, ..., m\_k \in \Sigma^\*$ such that $ L \subset m\_1^\*...m\_k^\*$. Now choose the minimum $n$ such that there exists $l\_1,..., l\_n$ such that every word of $L$ is a prefix of a word in $l\_1^\*...l\_n^\*$. Hence by the minimality of $n$ there exist a word $u \in L$ such that $u$ is not a prefix of a word in $l\_1^\*...l\_{n-1}^\*$.

What I don’t understand is why such an $u$ exist. I don’t see why the minimality of $n$ prove the existence of such an $u$... For example if I take $L = ab^\*c^\*d$ then I think the minimal $n$ is $4$ with the words $l\_1 = a, l\_2 = b, l\_3 = c, l\_4 = d$ and in this case such an $u$ clearly does not exist.

So is my book wrong or I am completely missing something here ?

Thank you !

# Answer
I think the book is right. In your example, the word $u=abcd$ satisfies the conditions: it is not a prefix of a word in $a^\* b^\* c^\*$.

In general, I think that proof is valid. I'll try to explain why the minimality of $n$ proves the existence of such a word $u \in L$. If there did *not* exist such a word $u \in L$, then that would mean that every word $u \in L$ *is* a prefix of $l\_1^\* \cdots l\_{n-1}^\*$, which in turn would mean that $n$ wasn't the minimum possible (we could have used $n-1$), which contradicts how $n$ was chosen in the second sentence. That's a contradiction. If you start from an assumption and derive a contradiction, then you can conclude that the assumption must have been wrong. In particular, the only alternative that remains possible is that there *does* exist such a word $u \in L$.

Put another way, there are only two possibilities: either there *does* exist such a word $u \in L$, or there *doesn't*. I've shown why the second choice is always impossible. That means the first choice must actually always be true.
> 2 votes

---
Tags: automata, word-combinatorics
---


title: Why is $\binom{n}{f}^g=O(n^{fg})$ true?

text:
# Question
Title: Why is $\binom{n}{f}^g=O(n^{fg})$ true?
Why is it true? I understand why $n^g$ but how does the $f$ get there in the power?? I believe from the context that it's not just that $\binom{n}{f}^g$ is strictly smaller than $n^{f g}$, but rather that it really belongs to this class, which means it's also tightly bounded by it or very close. But why is it?

# Answer
This reduces to showing $\binom{n}{f} = O(n^f)$.

In one variable the idea of an approximation being tight is pretty simple; you just see if the limit of the quotient goes to one.

In multiple variables there's no such thing as "the" limit. There are limits along different curves. Some may be tight and some may not be, but as long as the limit along one curve is tight there's no way of improving things across the board.

In situation at hand we have $$\binom{n}{f} = \frac{1}{f!}n(n-1)\ldots(n-f+1)$$. For f small compared to n, the $(n-i) \approx n$. If n grows a lot faster than k!, then it also blows out the k! term in the denominator as well. So along a curve like this the bound is tight.

(It's also possible we're considering fixed k and just considering the growth as a function of n, in which case the $1/k!$ is just a constant factor.)
> 3 votes

# Answer
$$\binom{n}{f} = \frac{n!}{f!\\,(n-f)!} = \frac{n(n-1)\cdots (n-f+1)}{f!} \leq \frac{n^f}{f!}\leq n^f\\,,$$ and you can raise the whole thing to the power of $g$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Check a variable within a range with a binary variable
I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 or not.

Thanks

# Answer
If I understand corectly, you want to formulate a system of linear constraints on a real variable $a$ and a $\\{0,1\\}$-variable $y$ such that the solutions are given by $$\[0,1\]\times\\{1\\} \bigcup \[1,\infty)\times \\{0\\}.$$

This is impossible. No linear constraint can put an upper bound on $a$ for some values of $y$ without putting an upper bound on $a$ for *all* values of $y$.

You can, however, just split the problem into two pieces and solve each one separately.
> 1 votes

---
Tags: linear-programming, integer-programming, constraint-satisfaction
---


# Question
Title: Count the number of subsets with product less than or equal to k
You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$.

Is there an efficient algorithm to solve the above problem. We can assume $1\le n \le 10^5$ and $1\le A\_i \lt k \le 10^9$ for each element $A\_i$ in $A$.

# Answer
As Apass.Jack suggested in the comment, there is an $O\left(n\left(\log n+\sqrt{k}\right)\right)$ solution based on dynamic programming.

First we sort the array to get $a\_{11},a\_{12},\ldots,a\_{1n\_1},\ldots,a\_{2n\_2},\ldots,a\_{tn\_1},\ldots,a\_{tn\_t}$ where $a\_{11}=\cdots=a\_{1n\_1}\<a\_{21}=\cdots=a\_{2n\_2}\<\cdots\<a\_{t1}=\cdots=a\_{tn\_t}$.

Let $c(m,p)$ be the number of subsets with product less than or equal to $p$ when only considering the elements from $a\_{11}$ to $a\_{mn\_m}$. By counting separately the subsets containing how many $a\_{m1}$'s, we have the following recurrence:

$$ c(m,p)=\sum\_{i=0}^{n\_m} c\left(m-1,\left\lfloor \frac{p}{a\_{m1}^i}\right\rfloor\right). $$

Note for positive integers $p,x,y$,

$$ \left\lfloor \frac{\left\lfloor \frac{p}{x}\right\rfloor}{y}\right\rfloor=\left\lfloor\frac{p}{xy}\right\rfloor, $$

to calculate $c(t,k)$, we only need to calculate $c(m,p)$ for all $m=1,2,\ldots,t$ and $p=\lfloor k/i\rfloor$ for $i=1,2,\ldots,k$. Note if $i\> \sqrt{k}$, then $\lfloor k/i\rfloor\le \left\lfloor \sqrt{k}\right\rfloor$, so all possible values of $p$ are $$ 1,2,\ldots,\left\lfloor \sqrt{k}\right\rfloor,\left\lfloor \frac{k}{\left\lfloor\sqrt{k}\right\rfloor}\right\rfloor,\left\lfloor \frac{k}{\left\lfloor\sqrt{k}\right\rfloor-1}\right\rfloor,\ldots,\left\lfloor \frac{k}{1}\right\rfloor, $$ i.e., only $O(\sqrt{k})$ values. So we can calculate $c(t,k)$ in $O\left(n\sqrt{k}\right)$ time (why? It's left as an exercise), plus the time for sorting.

Denote the possible values of $p$'s by $p\_1,p\_2,\ldots$. Another notable thing is that to achieve the time complexity above, given $p$, we must find $i$ such that $p=p\_i$ in constant time. This is easy. If $p\le \left\lfloor \sqrt{k}\right\rfloor$, then $i=p$. Otherwise assume $p=\lfloor k/x\rfloor$ for some integer $x\le \left\lfloor\sqrt{k}\right\rfloor\<p$, then we have $x=\lfloor k/p\rfloor$, so we can assert $i=2\left\lfloor \sqrt{k}\right\rfloor+1-\lfloor k/p\rfloor$.
> 3 votes

---
Tags: algorithms, arrays, sets
---


title: Question regarding languages and P

text:
# Question
Title: Question regarding languages and P
According to this Wikipedia article on unary language every unary language has a binary variant. My question is that given a unary language is there an equivalent binary language in P that is P-Complete.

# Answer
> 3 votes
As said Yuval Filmus in the comment, some unary languages are undecidable, so they don't even have an equivalent binary language in P.

---
Tags: complexity-theory, regular-languages
---


# Question
Title: What does flow denotes in the minimum-cost network?
What is **flow** in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to send **d amount of flow** from source to terminal node so that the total cost is minimized. My question is: what does flow denotes?

# Answer
> 1 votes
Flow is an abstraction of how much "stuff" you want to move through the network. Exactly what the stuff is depends on what you're modelling with the network - water pipes, transport networks, computer networks, etc.

The problem (or something close to it) can also be used to model other problems, in which case flow could be all kinds of things.

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


title: How to perform measurement of a qubit?

text:
# Question
Title: How to perform measurement of a qubit?
I am trying to implement the Deutsch algorithm. My steps were:

1. Write down $|01\rangle$ in a matrix form $A$;
2. Apply $H^{\oplus2}$ gate to $A$ matrix;
3. Multiply it with $U\_f$ matrix;
4. Apply $H$ to the first qubit;

After the above steps, I got a matrix:

```
array([[ 0.        ],
       [ 0.        ],
       [-0.70710678],
       [ 0.70710678]])

```

How should I perform a measurent step on the first qubit to get the answer?

# Answer
You haven’t specified the order of entries in your vector. In general, the $i$’th entry is obtained with probability $|x\_i|^2$.

Let’s consider two examples. In the first, the order of entries is $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. The two final entries will be obtained with probability $1/2$ each, and so the first qubit will be measured as $|1\rangle$. If you measure only the first qubit, then you will still always get $|1\rangle$, and the other qubit will remain in the superposition $\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)$.

If the order of entries is instead $|00\rangle, |10\rangle, |01\rangle, |11\rangle$, then once again the two final entries will be obtained with probability $1/2$ each. This means that the first qubit will be measured as $|0\rangle$ or $|1\rangle$ with equal probability.
> 2 votes

---
Tags: quantum-computing
---


# Question
Title: If NP is a subset of DTIME[n^O(log n)] then what happens?
If $\mathsf{NP}\subseteq \mathsf{DTIME}\[n^{O(\log n)}\]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does it also give $\mathsf{PSPACE}\subseteq \mathsf{DTIME}\[n^{O(\log n)}\]$?

# Answer
If $\textbf{NP} \subseteq \textbf{DTIME}(n^{O(\log n)})$, then we get $\textbf{P}^\textbf{NP} \subseteq \textbf{P}^{\textbf{DTIME}(n^{O(\log n)})} = \textbf{DTIME}(n^{O (\log n)})$. Continuing this reasoning, the entire polynomial hierarchy $\textbf{PH}$ is contained in $\textbf{DTIME}(n^{O(\log n)})$. By the time hierarchy theorem, $\textbf{DTIME}(n^{O(\log n)})$ is a proper subset of $\textbf{EXP}$ (and even of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$), so $\textbf{PH} \neq \textbf{EXP}$. In particular, we also get $\textbf{NP} \neq \textbf{EXP}$ and $\textbf{BPP} \neq \textbf{EXP}$ because both $\textbf{NP}$ and $\textbf{BPP}$ are in the polynomial hierarchy. For $\textbf{BPP}$ this is not that surprising since we already suspect it is contained in subexponential time.

What happens for $\textbf{PSPACE}$? Not much, as long as I'm aware of. We have $\textbf{PH} \subseteq \textbf{PP}$ and $\textbf{PH} \subseteq \textbf{P}^\textbf{#P}$ (by Toda's theorem), but I don't see any direct consequence for $\textbf{PP}$, let alone $\textbf{PSPACE}$.
> 3 votes

---
Tags: complexity-theory, time-complexity, np, complexity-classes, nondeterminism
---


# Question
Title: Bottom up chart parser adding active arc step
I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is

I couldn't understand the 3rd step. I thought that when active arc is added the dot is advanced. But dot is indroduced in the third step. The example says that

This example shows dot is advanced. But step 3 says otherwise

# Answer
You have spotted a typo in that book.

The dot $\circ$ in step 3 of figure 3.11 should be after constituency C. To be explicit and precise, step 3 should be stated as the following.

> 3. For each rule in the grammar of form X $\to$ C X$\_1$ ... X$\_n$, add an active arc of form X $\to$ C $\circ$ X $\_1$ ... X$\_n$ from position P$\_1$ to P$\_2$.

As you have observed, all examples following figure 3.11 show clearly that the dot $\circ$ are placed after constituency C.

This can also be verified by the statement a few lines below.

> Notice that active arcs are never removed from the chart.

We can check that we cannot, indeed, find any instance of an active arc in all of section 3, chapter 3 of the book that starts with a $\circ$.

There is also a rule that for each active arc from position $a$ to $b$, the symbols before the $\circ$ should correspond to the terminals between those positions inclusively. That rule also implies that a dot $\circ$ cannot be at the very front of an active arc.

By the way, that books is written so clearly that I have to say that glaring typo is an almost reverse testimonial.
> 2 votes

---
Tags: parsers, natural-language-processing
---


# Question
Title: Which unit (control unite or logic unit) issue instructions of load/store?
I learned that the CPU is composed of two units

and the machine’s instructions can be categorized into three groupings: (1) the data transfer group, (2) the arithmetic/logic group, and (3) the control group.

It could be concluded that Control Unit for the control group and Arithmetic/logic for the corresponding groups

How about the data transfer group? the data reside in register, which of the two units issue store/load command?

# Answer
You definitely cannot associate a part of the architecture with an instruction class.

* All instructions are concerned by the control unit as it fetches instructions and decode them.
* Control instruction mostly concern the controller, but some computations may be done by the ALU. For instance, in branches, addresses are generally given by adding an offset to the program counter and that requires an adder that may be in the ALU. It is the same if a branch instruction has to perform a comparison to decide if branch must be taken or not.
* once decoded, arithmetic/logic or data transfer instructions mostly concern the ALU part.

By the schematic that you gave (and my explanations) were true 40 years ago. Modern computers are much more complex. Control is somehow decentralized to allow execution of several concurrent instructions, instruction reordering, branch prediction, register renaming, etc. And the ALU is no longer a monolithic bloc but formed of several functional units dealing with specific computation, memory access, etc. You can find here the microarchitecture of a recent pentium (broadwell) and it is difficult to really identify the two units in your schematic.

So even more than in your question, it is impossible to associate an hardware unit with an instruction type.
> 2 votes

---
Tags: cpu
---


title: Proof of correctness of algorithm

text:
# Question
Title: Proof of correctness of algorithm
Can someone help me prove the correctness of this algorithm:

```
MUL(a,b)
   x=a
   y=b
   WHILE x≥b DO
      x=x-b
      y=y+1
   IF x=0 THEN
      RETURN(true)
   ELSE
      RETURN(false)

```

I had to prove that $x\_n + b\cdot y\_n = a$ by induction, where $x\_n$ and $y\_n$ are the values of the variable x and y after the loop has iterated n times.

I have done that, but I am not sure how to prove the correctness of the algorithm.

# Answer
> 1 votes
To prove that the algorithm is correct, we assume that the loop invariant $x\_n + by\_n = a$ is true per induction.

we have the following two cases:

case 1:

If MUL(a,b) returns true, then $x\_n = 0$ and $y\_n = n$,

so

$x\_n + by\_n =a \rightarrow bn = a \rightarrow a$ is a multiplum of b

case 2:

if MUL(a,b) returns false, then $x\_n \not= 0$, so we have

$x\_n + by\_n = a \rightarrow bn \not= a \rightarrow a$ is not a divisor of b.

---
Tags: algorithm-analysis, proof-techniques, correctness-proof
---


title: Storage in computers?

text:
# Question
Title: Storage in computers?
If i want to save something in a computer such as a number 1 that would be 001 but if i save 001 in a computer how would the computer know that 001 is 1. Should we first save the number 1 in memory and tell the computer that hey this is 1 and it is 001 in your language. Basically if we want to save something, how would a computer know what are we saving to determine its output. Like if i say the computer hey i wanna save 10011 and i actually intended it to be The letter A how would the computer know 10011 is A?

# Answer
Nowadays, all computers are built following certain conventions. One of those conventions is the use of zero and one (i.e. low voltage and high voltage): it's perfectly possible to make computers that *don't* use zeroes and ones, and in fact the Soviets did so (look into the Setun project). Another of those conventions is that text-based data comes in units of eight bits each, called "bytes".

Each byte holds a number from zero to 255, and more conventions define what each number means. The ASCII standard, for example, says that 65 means "A", while the UTF-8 standard says that 195 followed by 184 means "ø". But there's nothing intrinsically "A"-like about the number 65: it's just a convention people have agreed to follow, to make it easier for programs to work together.

(P.S. When two programs are using different conventions, you get a garbled mess called "mojibake". Nowadays most text data is stored in UTF-8, which helps avoid this, but there are still some holdouts (*cough* Windows API) who insist on using other conventions instead. It's a headache when you have to deal with that.)
> 1 votes

---
Tags: binary
---


# Question
Title: What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?
I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:

* enqueueing at the back
* dequeueing at the head

and it also says

> Note that although adding an element to the tail is constant time, removing an element from the tail is O(n) as we have to find the new tail

I know that adding a new node to my queue at the head (enqueue) takes O(1) since I have the head pointer. Similarly, removing a node at the head (dequeue) will take O(1) as well. But I don’t understand why adding an element at the back (enqueue) takes O(1), while removing it (dequeue) takes O(n). It would make more sense to me if enqueueing at the back took O(n) rather than O(1), since in both cases (adding/removing at the back) would need to find the tail pointer and therefore it would need to traverse the entire list.

# Answer
> 17 votes
### Enqueueing

You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail.

Pseudocode (assuming that `head != null` and `tail != null`):

```
function enqueue(value) {
    node = new Node(value)     // O(1)
    tail.next = node           // O(1)
    tail = node                // O(1)
    size++                     // O(1)
}

```

From which we can conclude that the time complexity is $O(1)$.

### Dequeueing

For dequeueing, we only need to set the next node of the current head as the new head and return the value of the old head.

**Note**: Don't forget that if the new head is set to `null`, the tail should be set to `null` as well:

Pseudocode (assuming that `head != null` and `tail != null`):

```
function dequeue() {
    value = head.value         // O(1)
    head = head.next           // O(1)
    size--                     // O(1)

    if (head == null) {        // O(1)
        tail = null            // O(1)
    }

    return value               // O(1)
}

```

All these operations have $O(1)$ time complexity, which makes the time complexity of the dequeue function $O(1)$ as well.

### Searching

Searching for a value is done by traversing through all the items, starting from the head. In the worst case scenario, you would need to traverse the entire queue, which makes the worst-case time complexity $O(n)$.

For example, if you want to remove the tail, the time complexity would be $O(n)$. This is because you would need to find the new tail for the queue and since the tail does *not* have access to the previous element in a singly linked list, you would need to search the entire queue for the new tail.

Pseudocode (assuming that `head != null` and `tail != null`):

```
function removeLast() {

    // Edge case when there is only 1 element in the queue.
    if (head == tail) {                   // O(1)
        value = head.value                // O(1)
        head = null                       // O(1)
        tail = null                       // O(1)

        return value                      // O(1)
    }

    // Searching for the new tail.
    newTail = head                        // O(1)
    while (newTail.next != tail) {        // O(n)
        newTail = newTail.next            // O(1)
    }

    value = tail.value                    // O(1)
    newTail.next = null                   // O(1)
    tail = newTail                        // O(1)

    return tail                           // O(1)
}

```

From which can be seen that the time complexity is indeed $O(n)$.

# Answer
> 3 votes
The comment in the book apparently assumes that your linked list implementation maintains two pointers, `head` that points to the first node in the list, and `last` that points to the last node.

With this design, appending to the list is simply:

```
list.last.next = newNode;
list.last = newNode;

```

But removing the last node requires finding the 2nd to last node, so you can clear its `next` link, and change the `last` pointer to point to it. This requires scanning the list to find the node where `node.next == list.last`.

You could conceivably also have a `list.secondToLast` pointer, but that doesn't solve the problem, because when you remove the last node you need to change this to point to the previous *third* to last node, and this problem recurses to the entire list.

---
Tags: algorithms, time-complexity, linked-lists, queues
---


# Question
Title: Ant Colony optimisation for finding subsets with ~0 sum
I have a set A = \[x1, x2...xn\] where xi in R (real). I need to find all non intersecting subsets with **subset sum ~0 (approximately equal to zero)**.

Since the set can have non zero real numbers, I have opted to use Ant Colony Optimisation for this problem. I have implemented this in python and the program tends to be a bit slow (python dictionaries for the graph). It takes around 60 seconds for 100 ants for single iteration. The algorithm goes like this:

* Create a graph with the whole list of real numbers (fully connected)
* Initialise the graph edges with w0
* Each vertex has an associated value
* Initialise the position of ants at random nodes
* Ants select next nodes based on edge weights
* Once an ant completes tour - the sum of all vertex values \> threshold 1 (1000000) or \< threshold 2 (~0.1), the path weights are updated based on path sum and global path updates (pheromone evaporation) after this

The questions I have:

1. Is the usage of ACO relevant here?
2. How can I improve the speed of the implementation?

# Answer
Your problem is no harder and no easier than the approximate subset-sum problem. There is a natural approach for your problem:

1. Find any subset that sums to something close to zero, and output it. Remove those numbers from the set $A$.
2. Go back to step 1 and repeat, until the set $A$ is empty.

This requires a way to find a subset that sums to approximately zero, i.e., an approximation algorithm for the subset-sum problem. That problem is well-studied and can be solved in polynomial time using an approach based on rounding and dynamic programming.

I don't see any reason to expect ant colony programming to be better than the standard approaches; and I wouldn't be surprised if it is worse.
> 1 votes

---
Tags: graphs, heuristics, python
---


title: What is an optimal algorithm?

text:
# Question
Title: What is an optimal algorithm?
I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are two separate concepts, so now I came up with this assertion which I think is correct, but I want to sanity check it:

> An algorithm can be said to be optimal if the function that describes its time complexity in the worst case is a lower bound of the function that describes the time complexity in the worst case of a problem that the algorithm in question solves.

As of now what I understand is that the so called bounds are "interactions" between functions and that the "cases" are just particular functions arising from particular situations regarding an algorithm's performance or the number of operations needed to solve a problem. Would that definition of an optimal algorithm be correct?

EDIT: the question is more aimed towards the proper theoretical understanding of cases and bounds than the real life properties of an optimal algorithm that extend to other concepts.

# Answer
> 6 votes
There are various notions of optimality one can think of. One popular notion of optimality is *worst-case running time*, which is what you describe:

> An algorithm for solving a problem $P$ is *asymptotically optimal with respect to worst-case running time* if it runs in time $T(n)$, and any algorithm for $P$ runs in time $\Omega(T(n))$.

In fact, this notion is ambiguous, since it's not clear what the parameter $n$ is. Indeed, in some cases there are several relevant parameters, which we sometimes want to consider at the same time. This is the case with graph algorithms, in which there are two natural parameters: the number of vertices and the number of edges.

An additional point of ambiguity is the *computation model* against which everything is measured. In theoretical work, we usually consider the word RAM as our computation model, but other models are possible.

The definition above is about the *asymptotic* running time. This manifests itself in two ways. First, we only care about the time complexity of the algorithm *up to constant factors*. Second, we only care about the behavior for large $n$. In practice, sometimes $n$ is fixed, and then the definition above doesn't make any sense.

Whereas worst-case running time is a popular parameter, other parameters are also relevant. Some examples include average-case running time (whenever there is a natural input distribution) and memory consumption. Only *you* can say which notion of optimality is most relevant for you.

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


title: Preconditions and postconditions

text:
# Question
Title: Preconditions and postconditions
What are preconditions and postconditions in this C++ function?

I have this example in my slides but still didn't get the idea!

```
*Comment function declaration:
    void showInterest(double balance, double rate);
    //Precondition: balance is nonnegative account balance
    //      rate is interest rate as percentage
    //Postcondition: amount of interest on given balance,
   //       at given rate …
*Often called Inputs & Outputs

```

# Answer
> 2 votes
*Preconditions* and *postconditions* are just ways to describe a function in more detail, and give some hints on how you can use this function or what to expect from it.

*Preconditions* are conditions that have to hold *before* (*pre* is Latin for *before*) the function gets called by a user. These are usually conditions about the parameter. E.g. a simple precondition for the function `square_root(x)` might be: `x` has to be non-negative. Because the function cannot handle negative numbers, maybe even crashes, or just return wrong values. But there are even other preconditions. Other preconditions could involve global states, or the state of objects. E.g. before you call this function you need to call another. So the user has to make sure, that all the conditions are satisfied, before he calls the method.

*Postconditions* are about *after* the call (again, Latin). That can mean the return value of the function, or the global state of the program or object after calling the function. This are conditions a user can expect from the program. It is kinda like a guarantee, if a user calls the function in a way that satisfies all preconditions, then he will get something that is described in the postconditions.

# Answer
> 1 votes
Preconditions and postconditions specify the semantics of the function; a contract which the function fulfills.

Using your function as an example, here is what the preconditions and postconditions mean:

> **If** `balance` is a non-negative account balance and `rate` is an interest rate given as percentage, **then** `showInterest` will show the amount of interest on the given balance at the given rate.

The author of the slides is being a bit sloppy, since the postconditions mentions "amount of interest" without mentioning its relevance. Given the name of the procedure, it is probably being shown; but otherwise, I would have guessed that it is a value being returned (though your function returns no value).

If `balance` is negative, then the behavior of the procedure is undefined. A function is only promised to fulfill its postconditions if the preconditions are fulfilled when the function is called.

---
Tags: programming-languages
---


# Question
Title: How the operating system allocated to dual-channels memory?
I learned that the boot loader transmit the operating system from Hard Disk to Main Memory during the booting process.

I wonder, today's computers are equipped with multiple slice of memory of dual-channels.

How the Operating System is allocated to each channel?

I guess it should not clone twice.

# Answer
You are completely misunderstanding what dual channel memory means; it is an implementation detail that is supposed to make memory access faster but completely invisible during operation.

Let's say you have (simplified) a computer with two RAM chips. The computer could have *one* connection to both chips, or *two* connections, one to each chip. The CPU issues a command to read say 256 bit. With single channel memory, one command to transfer 256 bit is sent to the two RAM chips, and it takes some time to transfer 256 bit. With dual channel memory, the CPU automatically (without the OS doing \_anything) sends two commands, one to each RAM chip, and each chip transmits 128 bits through its channel. Both commands run in parallel, so the time for memory transfer will be half the time.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Why every rational langage is the image of a local automaton
I have seen this result but I don’t understand why it’s true :

> Every rational language is the image of a local language by a morphism : $\phi : \Sigma^{\*’} \to \Sigma^\*$

I know what a local automaton is. It’s just an automaton that recognizes a local language. A local language is basically a language where all factors of size two are not in a certain set $S$. Now if I take a morphism from this language then it will still give me a local language right ? (i.e. the image of local language by a morphism is a local language). So I didn’t understand this result, I mean every rational language is not local...

Thank you !

# Answer
> 1 votes
(1) Indeed. Every regular \[=rational\]language is the morphic image of a local \[=2-testable\] language.

This is seen as follows. A finite state automaton can be "encoded" by a 2-testable language by using the transitions as letters. So we consider symbols $(p,a,q)$. The corresponding language is 2-testable: basically test whether the transitions are consecutive which is clear from letter pairs: $(p,a,\underline q)(\underline q,b,r)$. We find the original language by applying a coding: $(p,a,q)$ maps to $a$.

(2) No. Local languages are not closed under codings. $(ab)^\*$ is a local language. Initial letter $a$, final letter $b$, two letter substrings $ab, ba$. The image $(aa)^\*$ is not local. There is no way to distinguish odd length strings from even length strings by just looking at substrings.

---
Tags: finite-automata, word-combinatorics
---


# Question
Title: Number of FLOPs (floating point operations) for exponentiation
What is the number of floating point operations needed to perform exponentiation (power of)?

Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this? How does it work if $n$ isn't an integer?

# Answer
> Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...

There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.

* Convert the non-negative integer power to base 2.
* Count the number of ones in this representation.
* Add the power of two corresponding to the most significant non-zero bit in this representation.
* Subtract one.

This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.

> ... and how does it work if $n$ isn't an integer?

There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $\exp(n\ln(x))$.)
> 8 votes

# Answer
Using n-1 multiplications would be rather daft. For example, if n = 1024, you just square x ten times. Worst case is 2 * log\_2 (n). You can look up Donald Knuth, Art of Computer Programming, for some details how to do it faster. There are some situations, like n = 1023, where you would square x ten times giving x^1024, then divide by x.
> 6 votes

# Answer
You can use the formula $$ x^y = \exp (y \ln x). $$

If you want to use only multiplications, when $n$ is a natural number you can use *repeated squaring*, that uses $O(\log n)$ multiplications. For other $n$, multiplication alone doesn’t suffice.
> 5 votes

# Answer
People told you what happens when $n$ is an integer.

Regarding when it isn't, there may not even **exist** a way to do floating-point exponentiation at all.

It's called the Table-Maker's Dilemma, which says the amount of memory you'd need is unbounded:

> No general way exists to predict how many extra digits will have to be carried to compute a transcendental expression and round it *correctly* to some preassigned number of digits.
> **Even the fact (if true) that a finite number of extra digits will ultimately suffice may be a deep theorem.**
> 3 votes

# Answer
If you are serious about the problem, you may not try to find a solution with the lowest number of multiplications, but with the lowest execution time.

Consider a model where you can start a multiplication in every cycle, but each multiplication takes a fixed number of cycles, say 3 cycles. A method calculating x^n with k multiplications might take 3k cycles (if each multiplication depends on a result that was calculated just before), while a a method using more multiplications might run quicker.

For example: To calculate x^15, you might calculate in that order x^2 = x\*x, x^3 = (x^2)\*x, x^6 = (x^3)^2, x^7 = x^6 * x, x^14 = (x^7)^2, x^15 = x^14 * x. Six multiplications, but each dependent on the previous one.

Or you calculate x^2, x^4 = (x^2)^2, x^3 = x^2 * x, x^5 = (x^4)\*x, x^15 = x^5 * x^3, so you have only four multiplications depending on previous results.
> 0 votes

---
Tags: algorithms, arithmetic, floating-point
---


# Question
Title: How is Pure Maths utilized in Computer Science research?
How can People with a background in Mathematics pursue PhD in Computer Science"

Although I have a Postgraduate degree in Mathematics with basic programming knowledge,it sounded quite interesting how knowledge in Mathematics can help to solve Computer Science Research Problems.

Since this site is for researchers in Computer Science,Can someone kindly tell:

* What type of problems can a Mathematics postgraduate take up in Computer Science?
* What is the current scenario of research in Computer Science where Mathematicians like us can make a significant impact?
* What are the other skills needed apart from a sound Programming knowlegde to work here?

Any links/references would suffice too.

I have done courses on Linear Algebra,Abstract Algebra,Functional Analysis,Topology,Number Theory and have enjoyed them.

I really dont know how to use the concepts learnt in these courses can be used to solve research questions on Computer Science.

If someone can kindly comment how concepts in the above Mathematical facts can be used to do research in CS,I can understand why a reputed instititution in our country is asking for postgraduate in Mathematics for a PhD in CS.

# Answer
> 9 votes
Let's do these in the order you listed. I will not be comprehensive, I will just try to impress you by pointing out cool applications of mathematics in CS. Others may know of even cooler applications.

1. **Linear algebra** is used to compute the Page rank of web pages, which is the basis of Google engine ordering pages from more relevant to less relevant.
2. **Abstract algebra** is used to model computational effects, such as exceptions, input/output, memory, parallel computation etc.
3. **Functional analysis** is used in the JPEG image format which uses Fourier analysis to achieve lossy compression.
4. **Topology** is used in domain theory to give mathematical models of programming languages. Algebraic topology is used in topological data analysis, and homotopy theory is used in homotopy type theory to study equivalence of datatypes (I am oversimplifying) and how to convert between them.
5. **Number theory** is used in cryptography to provide public key protocols, such as the RSA algorithm. These are used every time you buy anything on the Internet.

So, is that convincing enough?

---
Tags: research
---


title: DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

text:
# Question
Title: DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the **Regular Expression**(RE) of that language but we still didn't make its DFA.

I am trying to make **Deterministic Finite Automata** (DFA) of this lang which is defined on **alphabet={a,b}** and all strings present in this language are either **start or end on double letter i.e aa or bb**. The RE is given in title.

I made a DFA by using **Kleene Theorems** but its pretty complex. How i can directly make a DFA.

# Answer
The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the word being read, being in an accepting state whenever they are the same.

Instead of writing a state diagram, here are the Myhill–Nerode equivalence classes of your language (given as regular expressions), which can be converted into a DFA with the same number of states as the number of equivalence classes:

* $q\_0$: $\epsilon$.
* $q\_1$: $a$.
* $q\_2$: $b$.
* $q\_3$: $(aa+bb)(a+b)^\*$.
* $q\_4$: $(a+b)^\*aa \setminus (aa+bb)(a+b)^\*$.
* $q\_5$: $(a+b)^\*ab \setminus (aa+bb)(a+b)^\*$.
* $q\_6$: $(a+b)^\*ba \setminus (aa+bb)(a+b)^\*$.
* $q\_7$: $(a+b)^\*bb \setminus (aa+bb)(a+b)^\*$.

The initial state is $q\_0$, and the accepting states are $q\_3,q\_4,q\_7$.

Here is the transition function: $$ \begin{array}{c|cccccccc} & q\_0 & q\_1 & q\_2 & q\_3 & q\_4 & q\_5 & q\_6 & q\_7 \\\hline a & q\_1 & q\_3 & q\_6 & q\_3 & q\_4 & q\_6 & q\_4 & q\_6 \\ b & q\_2 & q\_5 & q\_3 & q\_3 & q\_5 & q\_7 & q\_5 & q\_7 \end{array} $$
> 2 votes

# Answer
Taking apart the regex we notice that any word starting with $\texttt{aa}$ or $\texttt{bb}$ is accepted which can be expressed with the following (incomplete) FS:

The remaining accepted words must have to end with either $\texttt{aa}$ or $\texttt{bb}$, so you need to "store" a read $\texttt{a}$ (or $\texttt{b}$) and distinguish between the next symbol if it's the same or another one:

* if it's the same, then we accept the word
* if not we transition to the state where we already read the other character

Finally, if we have read a symbol twice then we can read as many symbols of the same type again and the word is still accepted. If we read another one, we restart in the state where we already read one symbol of that type:

We are now ready to assemble the final, finite state machine:
> 1 votes

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


# Question
Title: Reading elements of a countable set with Turing machine
I have a basic question about the behavior of a potential Turing machine.

Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s\_i)\_{n\in \mathbb{N}}$.

Suppose that we want to construct a Turing machine $M$ that, on any input, simply writes each element of $S$ on a tape in order $s\_1, s\_2, \ldots$. (I realize that $M$ will never halt.)

> But we can construct such an $M$ if and only if our particular bijection $\mathbb{N} \to S$ is computable, correct? Or is knowing that $S$ is countable somehow enough?

# Answer
By definition, a set $S$ is *recursively enumerable* if there is a Turing machine that enumerates it.
> 0 votes

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