# Question
Title: Designing a DFA with nth character condition for any integer n
Let n be an integer. How can I write finite automata for the language L?
L = {W∈{$0,1,2$}\*| The $n\_{th}$ from last letter in w is $0$}.
(Please suggest answers; not hints.)

**Attempt**
Using Regex, I could write it as $\[012\]\*0\[012\](n - 1)$ \- replacing n - 1 with the actual integer value. But I'm not sure of a good program to diagram it with.

# Answer
It is possible to prove that such a DFA would always have at least $2^n$ states (the idea of the proof is given here, but for a two-letters alphabet).

This bound can be reached: consider $A = (Q, \delta, q\_0, F)$ where:

* $Q = \\{0,1\\}^n$: to each state corresponds a word of length $n$ over the alphabet $\\{0,1\\}$;
* $q\_0 = 1^n$;
* $F = \\{0u\mid u\in \\{0,1\\}^{n-1}\\}$: states that begin with $0$;
* for $u\in \\{0,1\\}^n$, $u = u\_1…u\_n$, $\delta(u, 0) = u\_2…u\_n0$ and $\delta(u,1) = \delta(u, 2) = u\_2…u\_n1$.

The idea is that each state tells you what are the last $n$ letters you read (at least for words of length $\geqslant n$), with $2$'s being associated with $1$'s (we just need to know the positions of $0$'s).

Proof left to you that $L(A) = \\{w\in\\{0,1,2\\}^\*\mid w = u0v, \text{ with }|v| = n-1\\}$.
> 2 votes

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


# Question
Title: Workers with certain strength carrying boxes. (Greedy)
I just had an algorithms exam and had the following problem: Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s\_i$ and each object has a weight $w\_i$. Each worker needs to be assigned to an object, and they can only be assigned to a specific object $w\_i$ if $s\_i \ge w\_i$. There are also $k$ pills. Each worker has the ability to take a pill and increase there strength by 20.

For example: s = \[10, 30, 30\] w = \[30, 20, 20\] k = 1

The solution would be to give $s\_1$ the pill and assign $w\_1$ to $s\_1$, $w\_2$ to $s\_2$ and $w\_3$ to $s\_3$.

The solution needs to be $O(nlogn)$

My solution is as follows:

```
algorithm(workers, objects, k):
    pills = k
    workers = workers.sort()
    objects = objects.sort()
    for i = 1 to n:
        if w[i] >= s[i]:
            assign(w[i], s[i])
        else if w[i] + 20 >= s[i]:
            pills -= 1
            assign(w[i], s[i])
        else:
            return False
    return True

```

I'm wondering if my algorithm works and if it is the optimal solution. If not could someone explain what is? Thank you!

# Answer
I won’t answer your question but tell you about one thing you need to check: Every time you assign a worker or a worker + pill, you waste some amount. Is it possible to get a better outcome by assigning a worker + pill to a task requiring 20 or 19 more strength so nothing of strength is wasted? If yes give an example. If not give a reason why.

I expect things might be interesting if a worker can take more than one pill.
> 1 votes

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


# Question
Title: Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?
While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \\{L\_1 \cap L\_2 \mid L\_1 \in NP \text{ and } L\_2 \in coNP\\}$$

I am interested in a different (and much shorter form) of describing this exact operation on class-level, rather than language-level $$coNP\\; ? \\; NP = DP$$

Since this is different than just cutting both classes, I was wondering what symbol is commonly used for this operation?

# Answer
> 2 votes
In the theory of "abstract families of languages" one uses the notation $\mathcal K \land \mathcal L$ to denote the pairwise intersection of languages in $\mathcal K$ and $\mathcal L$, thus $\\{\\;K\cap L\mid K\in\mathcal K \text{ and } L\in\mathcal L\\;\\}$.

That theory is probably half a century old with work of Greibach, Ginsberg and others. A rather recent occurrence of this notation is Semilinearity of Families of Languages, by Ibarra and McQuillan, arXiv:2212.01301. See top of page 5.

This agrees with the suggestion you propose in your comment.

# Answer
> 0 votes
I am not aware of any standard notation to represent this operation. You could invent your own notation, but make sure you define it in a self-contained way, so that readers understand what you mean by it.

---
Tags: complexity-theory, notation
---


# Question
Title: How do you stop an algorithm at a specific run time?
so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my code to run at a higher depth. However, my code is only given 1 second to run and generate a move and I'm worrying that my ai would not be able to check all the relevant nodes in the designated time. My thought is that I could implement iterative deepening, but I have no idea how to do that (so I really need some inspiration). And also how could I stop my code at a specific time? I want to push my code to the maximum depth if possible.

# Answer
As far as I know, it is not possible to achieve that exactly unless you are running a hard-real-time operating system (which neither Windows nor Linux are).

Anyway, you can obtain close to this behavior by one of two methods:

1. internal timing: choose one or more check points in your algorithms, that are frequently passed through and where you read the wall-clock time\*. When the desired delay is reached, or a little before, let the algorithm terminate. The difficulty is to find a point where the algorithms passes frequently enough. The maximum running time between two passings should not exceed the desired time accuracy. This may pose a challenge if the algorithm behaves irregularly or at a pace that depends on the input data.
2. external timing: you can launch the algorithm in an auxiliary thread and start a timer synchronously (waiting call). Upon timer expiry, kill the auxiliary thread. There are two technicalities involved:

* you must make sure that the algorithm can be interrupted at any time; in case the algorithm updates a list of results, the update must be made atomically, i.e. cannot be interrupted in the middle of a sequence of modifications that temporarily breaks data coherence.
* you must make sure to regain control when the auxiliary thread is effectively killed, so that it won't change the results after the fact.

With all solutions, the system load may cause extra latencies; they cannot be avoided.

---

\*Alternatively you can start a timer *asynchronously* (non-waiting call) and periodically check whether it has elapsed or not.
> 2 votes

# Answer
When you implement alpha-beta pruning, it is important to try the best moves first. To do this, you evaluate one move and sort the moves from best to worst. Then you evaluate two moves, trying moves in the order you found by one move, and sort again. Then three moves and so on.

In C or C++ you can use the clock() function which returns the time spent in the current thread, in multiples of CLOCKS\_PER\_SEC. So after evaluating a move, you check the time and estimate how likely it is to finish in the time you have.

If you absolutely need to finish in the given time, you run the calculation in a separate thread which updates the best result so far, and set a timer to display the best result after one second.

Note that clock() stops counting when the thread is not running, so if your computer is very busy it might take longer until clock() increases by more than a second. clock\_gettime() might help.
> 2 votes

# Answer
> check all the relevant nodes in the designated time.

You will never be able to check all the nodes. The whole point of iterative deepening is that you search just a part of the tree, and return the best answer you have so far once time runs out. There are therefore two different problems to consider:

1. Making sure the program runs within the given time.
2. Having the program return the best solution found so far.

To address 1, you need an if-statement at the start of your loop that simply measures the time that has elapsed so far and if the program has less than 0.001s remaining to make a move, then it will return immediately. You can adjust the 0.001s threshold as needed.

To address 2, you use iterative deepening. In iterative deepening, you first search the game tree up to depth 1. The heuristic will be evaluated at depth 1 nodes. The best result for depth 1 is stored somewhere. Then you do the same thing for depth 2. Replace the depth 1 result with depth 2's result. And so on, you keep raising the depth by 1 and exploring the game tree only up to that depth and saving the best solution. If you are running out of time, you immediately return the best solution found so far.
> 2 votes

---
Tags: algorithms, runtime-analysis, pruning
---


# Question
Title: Making Candies - HackerRank question - proof of optimality of a greedy approach
I stumbled across this question in HackerRank:

> Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a level in which he must accumulate $n$ candies starting with $m$ machines and $w$ workers. In a single pass, he can make $m \times w$ candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers. Buying a machine or hiring a worker costs $p$ units, and there is no limit to the number of machines he can own or workers he can employ.
>
> Karl wants to minimize the number of passes to obtain the required number of candies at the end of a day. **Determine that number of passes.**
>
> *For example, Karl starts with $m=1$ machine and $w=2$ workers. The cost to purchase or hire, $p=1$ and he needs to accumulate $60$ candies. He executes the following strategy:*
>
> Make $m \times w = 2$ candies. Purchase two machines.
>
> Make $3 \times 2 = 6$ candies. Purchase $3$ machines and hire $3$ workers.
>
> Make $6 \times 5 = 30$ candies. Retain all $30$ candies.
>
> Make $30$ candies. With yesterday's production, Karl has $60$ candies. It took $4$ passes to make enough candies.

The hypothesis is that the greedy approach, where we always spend as much money as possible to purchase workers/machines (until the last pass where we wait one more time to gather enough candies) is the optimal one. If this is the case - why?

# Answer
The hypothesis is correct, and the greedy approach is indeed optimal. Here's why:

Let's say Karl has m machines and w workers, and in one pass he can make m\*w candies. Now, assume Karl decides to spend some of his candies to either buy a new machine or hire a new worker. Let's consider two cases:

Case 1: Karl buys a new machine

If Karl buys a new machine, then he spends p candies, and his total number of candies now becomes (total candies - p). But now, his number of machines becomes (m + 1) and the number of workers remains the same (w). Therefore, in the next pass, he can make (m+1)\*w candies.

Case 2: Karl hires a new worker

If Karl hires a new worker, then he spends p candies, and his total number of candies now becomes (total candies - p). But now, his number of workers becomes (w + 1) and the number of machines remains the same (m). Therefore, in the next pass, he can make m\*(w+1) candies.

Now, let's consider two scenarios:

Scenario 1: Karl spends p candies to buy a new machine

In this case, Karl spends p candies, and his total number of candies now becomes (total candies - p). He now has (m+1) machines and w workers. Therefore, in the next pass, he can make (m+1)\*w candies.

Scenario 2: Karl spends p candies to hire a new worker

In this case, Karl spends p candies, and his total number of candies now becomes (total candies - p). He now has m machines and (w+1) workers. Therefore, in the next pass, he can make m\*(w+1) candies.

Now, we need to decide which of these scenarios is better for Karl. We can compare the two scenarios by looking at the difference in the number of candies he can make in the next pass.

For scenario 1, the number of candies he can make in the next pass is (m+1)w - mw = w candies.

For scenario 2, the number of candies he can make in the next pass is m\*(w+1) - m\*w = m candies.

Therefore, if w \>= m, scenario 1 is better, and if w \< m, scenario 2 is better.

Now, we can see that the greedy approach (i.e., always spending as much money as possible to purchase workers/machines) is optimal. In each pass, we choose the scenario that gives us the maximum increase in the number of candies, which is always the scenario where we spend our candies to purchase a new machine or hire a new worker, depending on whether w \>= m or w \< m. We keep doing this until we have enough candies to complete the level. The intuition behind this is that the more machines/workers we have, the more candies we can produce in each pass, which will lead to fewer passes required to complete the level.
> 0 votes

---
Tags: algorithms, optimization, proof-techniques, greedy-algorithms
---


# Question
Title: Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph
Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side.

This is a conceptually simple problem, but I suspect it is actually quite difficult.

# Answer
> 5 votes
Let $A,B$ be the two sides of the bipartite graph, we are looking for a subuset of $A$. Hall's characterization of perfect matchings states that $G$ admits a perfect matching saturating $A$ if and only if for each subset $X\subseteq A$ it holds that $|N(X)|\geq |X|$.

If the graph admits a perfect matching, then according to this theorem, no such set exists. On the other hand, if the graph does not admit a perfect matching, then a set exists, and the proof of the theorem is constructive, so you can follow it to construct such set (in linear time after finding a maximum matching). You can see a simple version of the proof here. A summary of the steps:

* Find a maximum matching $M$.
* If $M$ saturates $A$ we are done.
* Find an $M$-free vertex $v\in A$.
* Let $S$ be the set of all vertices in $A$ reachable from $v$ using $M$-alternating paths.
* $S$ is the set we are looking for.

The correctness follows fron the fact that each vertex in $N(S)$ is matched to a different vertex of $S$ (we cant visit $M$-free vertices along this process assuming $M$ is maximum, since this would imply an augmenting path from $v$). Since $S$ contains $v$ as well, it is strictly larger than $N(S)$.

For the running time you can find a maximum matching using Hopcroft and Karp‘s algorithm in time $O(\sqrt n m)$ and then build $S$ in linear time.

---
Tags: algorithms, graphs, bipartite-graph
---


# Question
Title: Deterministic infinite automaton equals a normal DFA?
Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q\_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA.

**Attempt**
I tried to disprove it using the language L = {$a^nb^n|0 \< n ∈ N$}, but I am not sure if this is enough to disprove it.

# Answer
That approach indeed works. It is well known that $L = \\{a^n b^n \mid n \in \mathbb N\\}$ is not regular and hence not recognized by any "normal" DFA, so it suffices to show that $L$ can be recognized by a DIA. I'll leave the details to you, but using infinite states we can remember the number of $a$ we read so far and then count down when reading $b$.

Indeed, one can show that *every* language can be recognized by a DIA: Let $L$ be some language and consider the DIA $\mathcal A\_L$ with state set $Q = \\{q\_w \mid w \in \\{0, 1\\}^\ast\\}$, initial state $q\_\varepsilon$, transitions $\delta(q\_w, 0) = q\_{w0}$ and $\delta(q\_w, 1) = q\_{w1}$ for all $w \in \\{0, 1\\}^\ast$ and accepting state set $F = \\{q\_w \mid w \in L\\}$. This implies that even undecidable languages can be recognized by DIAs.
> 1 votes

# Answer
Yes, since we already know that $L = \\{a^n b^n\\}$ is not regular (using the pumping lemma), and that a language is regular if and only if it admits a DFA, it suffices indeed to show the inequivalency by definining a $DIA$ for $L$. Intuitively, $L$ is able to keep arbitrary amount of information about history using additional states when needed, and DFAs can keep only constant memory.

A way to achieve this $M=(\\{a,b\\}\times\mathbb{Z} \cup \\{F\\}, \delta, (a,0), \\{(a,0),(b,0)\\})$, where the first symbol in the tuple indicates whether a $b$ has been read so far, and the second counts $\\#\_a(x\_0\dots x\_i) - \\#\_b(x\_0\dots x\_i)$. So the transitions are $$\delta: ((a,i),a)\mapsto (a,i+1)\\ ((a,i),b)\mapsto (b, i-1)\\ ((b,i),b)\mapsto(b, i-1)\\ ((b,i),a)\mapsto F $$
> 1 votes

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


# Question
Title: How to prove that we can study the complexity of Recurrence Relations by always giving in input a power of how many children each node creates?
Let's say we have the following Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ 3T(\frac{n}{3}) + \Theta(n) & \text{otherwise} \end{cases} $$ I've been taught I can study its complexity by giving into input a power of 3 to calculate its height and consequently its total cost.

I'd like a proof of why this can be done, despite the fact the tree can receive a number which is not power of three, thus making it taller or shorter than what initially studied. Thank you.

# Answer
**When does it work?** This trick would work if $T(n)$ satisfies $$T(3 n) = \Theta(T(3n)) \qquad \qquad (Cond.)$$ which holds if it belongs to polynomial family, which is the case when $T(n)=O(a T(n/b)) +O(n)$ for constants $a,b=O(1),b\>1$. Observe that for all numbers $n$ there is $k$ such that $3^k\le n\< 3^{k+1}$ and we have $$3^k\le n\< 3^{k+1}\implies T(3^k)\lesssim T(n)\lesssim T(3^{k+1})\lesssim T(3^{k+1}) \overset{(Cond.)}{ \implies } T(n)=\Theta(3^k) $$ where $f \lesssim g$ denotes $f=O(g)$.

**When it doesn't work?** Note that $(Cond.)$ *can be violated*, notably when $T(n)$ grows exponentially. If for constant $\alpha$ we have $$T(n)=\Theta(\alpha^{3n})\implies T(n)=o(T(3n))$$
> 0 votes

# Answer
Let us consider the recurrence

$$T(n)=3T\left(\left\lfloor\frac n3\right\rfloor\right)+n.$$

We can show that the function $T$ is strictly growing because by complete induction, if $T$ is increasing up to $3m$,

$$T(3m)=3T(m)+3m\\ \<T(3m+1)=3T(m)+3m+1\\ \<T(3m+2)=3T(m)+3m+2\\ \<T(3m+3)=3T(m+1)+3m+3$$

so that $T$ is increasing up to $3m+3$.

Given that $T$ is growing, when $n$ is comprised between two powers of $3$, $T(n)$ is comprised between $T$ for these two powers. So the order of growth between powers is the same as on powers.
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: What recurrence describes the time complexity of this algorithm?
The problem is as follows:

> The input is an array $A$ of $n$ natural numbers such that:
>
> (1) if the maximum occurs in $A\[p\]$ for an index $p$, then $$A\[1\] \leq \ldots \leq A\[p-1\] \leq A\[p\]$$ and $$A\[p\] \geq A\[p+1\] \ldots \geq A\[n\];$$
>
> (2) if $A\[i\]=A\[j\]=x$ then $A\[k\]=x$ for $i \leq k \leq j$.

The goal is to find the maximum element of $A$. Restriction (2) imposes the additional difficulty that $A$ might contain plateaus, and hence a simple binary search does not work. I came up with the following algorithm, but I'm having a hard time analyzing its time complexity.

```
// p is start index and q the ending index (inclusive)
FindPeak(A, p, q)
1    if q - p = 0 then return p
2    m = (p + q) / 2               // assume that the division applies the floor
3    i = FindPeak(A, p, m)
4    j = FindPeak(A, m + 1, q)
5    if A[i] = A[j] then           // A[i..j] is a plateau
6        i = FindPeak(A, p, i)
7        j = FindPeak(A, j, q)
8    if A[i] < A[j] then return FindPeak(A, j, q)
9    else return FindPeak(A, p, i)

```

Let $n=q-p$ and $T(n)$ be the function describing the running time of `FindPeak`. I know that lines 3 and 4 are $T(n/2)$ each, but I'm not sure about lines 6 through 9. Could you help me constructing the recurrence relation for $T(n)$? (And any eventual bug that might be lurking there.)

PS 1. If the entire array is a plateau (all the elements are equal), then is it correct to say that the worst-case running time of `FindPeak` is $\Omega(n)$?

PS 2. After reading a comment, I realized that I didn't understand the problem properly. The simplified algorithm is as follows:

```
// p is start index and q the ending index (inclusive)
FindPeak(A, p, q)
1    if q - p = 0 or A[p] = A[q] then
2        return p
2    m = (p + q) / 2               // assume that the division applies the floor
3    i = FindPeak(A, p, m)
4    j = FindPeak(A, m + 1, q)
5    if A[i] < A[j] then
6        return FindPeak(A, j, q)
7    else
8        return FindPeak(A, p, i)

```

I still have trouble to analyze the time complexity because of lines 5 through 8. Nevertheless, due to lines 3 and 4, I think the running time in the worst-case is at least $\Omega(n)$, right? Is it possible to devise a $O(\log n)$ algorithm?

# Answer
> 2 votes
Partial answer: The problem admits an $O(n^{\log\_3(2)}) \leq O(n^{0.631})$ algorithm.

The algorithm $\mathcal A$ works as follows:

1. Query $x = A\[n/3\]$ and $y = A\[2n/3\]$.
2. If $x = y$, return $\max \\{x, \mathcal A(A\[1, n/3\]), \mathcal A(A\[2n/3, n\])\\}$
3. If $x \< y$, return $\max \\{\mathcal A(A\[n/3, 2n/3\]), \mathcal A(A\[2n/3, n\])\\}$
4. If $x \> y$, return $\max \\{\mathcal A(A\[1, n/3\]), \mathcal A(A\[n/3, 2n/3\])\\}$

($A\[p, q\]$ denotes the sub-array of $A$ starting at index $p$ and ending at index $q$.)

It should be easy to see that $\mathcal A$ works correctly. The running time $T(n)$ of $\mathcal A$ is given by $T(n) = O(1) + 2 \cdot T(n / 3)$, which solves to $T(n) = O(n^{\log\_3(2)})$.

---
Tags: algorithm-analysis, recurrence-relation, divide-and-conquer
---


# Question
Title: How does Decimal to Binary conversion algorithm work?
I'm reading a book which says that to transform a number from decimal representation to binary representation you have to follow these steps:

1. Take the integer part (the one before the point) of the number and transform it in binary like you normally do with integer numbers: that is the integer part of the binary representation of the number we are trying to convert.
2. Take the decimal part (the one after the point) of the original number and multiply it by 2, the integer part of the obtained number is a digit (the current one) of the decimal part of the binary number.
3. Repeat step 2 until:
    * You got 0 as the decimal part of the obtained number.
    * Obtained numbers start to repeat, in that case the number is periodic.

At the end you should get the binary transformation of the original number.

I tried to apply the algorithm to the number: **0,264** and got:

* 0,264 (dec part) -\> 0,264 * 2 = **0**,528
* 0,528 (dec part) -\> 0,528 * 2 = **1**,056
* 1,056 (dec part) -\> 0,056 * 2 = **0**,112
* 0,112 (dec part) -\> 0,112 * 2 = **0**,224
* 0,224 (dec part) -\> 0,224 * 2 = **0**,448
* 0,448 (dec part) -\> 0,448 * 2 = **0**,896
* 0,896 (dec part) -\> 0,896 * 2 = **1**,792
* 1,792 (dec part) -\> 0,792 * 2 = **1**,584
* 1,584 (dec part) -\> 0,584 * 2 = **1**,168
* 1,168 (dec part) -\> 0,168 * 2 = **0**,336
* 0,336 (dec part) -\> 0,336 * 2 = **0**,672
* 0,672 (dec part) -\> 0,672 * 2 = **1**,344
* 1,344 (dec part) -\> 0,344 * 2 = **0**,688
* 0,688 (dec part) -\> 0,688 * 2 = **1**,376
* 1,376 (dec part) -\> 0,376 * 2 = **0**,752
* 0,752 (dec part) -\> 0,752 * 2 = **1**,504
* 1,504 (dec part) -\> 0,504 * 2 = **1**,008
* 1,008 (dec part) -\> 0,008 * 2 = **0**,016

......

... And so on.

As you can see neither we found just 0 as the decimal part of the numbers we got, neither these numbers started to repeat.

Nevertheless, trying to convert 0,264 using this online converter gets the following: **0,01000011100101011**, which stops one step before where I stopped in the algorithm calculation I showed in this question.

So I was wondering:

* Why does it stop there? Are there other criteria for stopping in the algorithm?
* Am I getting the algorithm wrong?

I think it may have something to do with precision you want to get, but then what should be the correct criteria for stopping?

# Answer
> 2 votes
No, you have not done anything wrong.

However, you have not done enough. You have done step 2 for 18 times. You will have to repeat step 2 for another 82 times. Then you will observe that the "obtained numbers start to repeat".

The binary representation of $0.264$ is $$0.\underline{0100001110010101100000010000011000100100110111010010111100011010100111111011111001110110110010001011}$$ where I use the underline to indicate the first shortest period, which turns out to be the first 100 binary digits right after the decimal separator.

This large value of period length is more of a norm than an outlier. Here is a list of the lengths of the periods in the binary representations of a few decimal factions.

| decimal fraction | length of periods in its binary representation |
| --- | --- |
| 0.6 | 4 |
| 0.06 | 20 |
| 0.006 | 100 |
| 0.0006 | 500 |
| 0.0006 | 2500 |

You might have noticed a few patterns in the table above. I will leave them for you to explore, discover, verify and extend.

---

> Why does it stop there?

That website cuts off the computation of the binary digits at some arbitrary length. Or that is what appears to me. A different website or tool may choose a different cut-off point, such as this one.

You can stop the algorithm at any time you prefer. If you would like to run the algorithm entirely, follow step 3. It is an *algorithm* after all.

# Answer
> 0 votes
If you want IEEE 64 bit floating point numbers, you need 53 mantissa bits. If the integer part is non-zero and has k bits, you need 53-k bits from the fractional part. If the integer part is zero, then you ignore the initial zero bits from the fractional part, and you need 53 bits starting with the first non-zero bit.

When you are done, the remaining fractional part is used to round the result correctly. Less than 0.5 means unchanged, greater than 0.5 means you round up, and exactly 0.5 means you round so that the last bit becomes zero.

You need to handle numbers \>= 2^53, and the number zero. If you have number like 1.2345678901234567890e-300 this will take ages; you can convert the fractional part to base 10^9 and do 30 steps at a time by multiplying by 2^30, making the operation 270 times faster. For large numbers like 1.2345678901234567890e300 you can convert the whole digit string to base 10^9 and divide by 2^30 as often as needed.

PS. The pattern *must* repeat. You had three digits. There are only 1000 possibilities to have three digits. So after 1001 iterations you *must* have repeated one combination, and from then in the pattern repeats. If you had 20 digits it might take a very long time until it repeats.

For conversion to binary floating point the pattern is actually not relevant.

---
Tags: binary, number-formats, base-conversion
---


# Question
Title: Why is selection sort faster than bubble sort?
It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort even though both of them have:

1. **Worst case time complexity**: $\mathcal O(n^2)$
2. **Number of comparisons**: $\mathcal O(n^2)$
3. **Best case time complexity** :

* Bubble sort: $\mathcal O(n)$
    * Selection sort: $\mathcal O(n^2)$
4. **Average case time complexity** :

* Bubble sort: $\mathcal O(n^2)$
    * Selection sort: $\mathcal O(n^2)$

# Answer
All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted.

To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books. I'll use results from Knuth's Art of Computer Programming.

Average number of comparisons:

* **Bubble sort**: $\frac{1}{2}(N^2-N\ln N -(\gamma+\ln2 -1)N) +\mathcal O(\sqrt N)$
* **Insertion sort**: $\frac{1}{4}(N^2-N) + N - H\_N$
* **Selection sort**: $(N+1)H\_N - 2N$

Now, if you plot those functions you get something like this:

As you can see, bubble sort is much worse as the number of elements increases, even though both sorting methods have the same asymptotic complexity.

This analysis is based on the assumption that the input is random - which might not be true all the time. However, before we start sorting we can randomly permute the input sequence (using any method) to obtain the average case.

I omitted time complexity analysis because it depends on implementation, but similar methods can be used.
> 43 votes

# Answer
The asymptotic cost, or $\mathcal O$-notation, describes the limiting behaviour of a function as its argument tends to infinity, i.e. its growth rate.

The function itself, e.g. the number of comparisons and/or swaps, may be different for two algorithms with the same asymptotic cost, provided they grow with the same rate.

More specifically, Bubble sort requires, on average, $n/4$ swaps per entry (each entry is moved element-wise from its initial position to its final position, and each swap involves two entries), while Selection sort requires only $1$ (once the minimum/maximum has been found, it is swapped once to the end of the array).

In terms of the number of comparisons, Bubble sort requires $k\times n$ comparisons, where $k$ is the maximum distance between an entry's initial position and its final position, which is usually larger than $n/2$ for uniformly distributed initial values. Selection sort, however, always requires $(n-1)\times(n-2)/2$ comparisons.

In summary, the asymptotic limit gives you a good feel for how the costs of an algorithm grow with respect to the input size, but says nothing about the relative performance of different algorithms within the same set.
> 13 votes

# Answer
Bubble sort uses more swap times, while selection sort avoids this.

When using selecting sort it swaps `n` times at most. but when using bubble sort, it swaps almost `n*(n-1)`. And obviously reading time is less than writing time even in memory. The compare time and other running time can be ignored. So swap times is the critical bottleneck of the problem.
> 6 votes

# Answer
$T(n)=O(n^2)$ means that for all $n\ge N$,

$$T(n)\le cn^2$$ for some $N$ and $c$.

In no way does

$$T\_a(n)\le c\_a n^2$$ and $$T\_b(n)\le c\_b n^2$$

allow you to draw conclusions on which of $T\_a$ and $T\_b$ is smaller.
> 0 votes

# Answer
I'm surprised that no one mentioned it, but there is a very good metric to measure the running time of the insertion sort: it's the number of inversions, i.e. the pairs $(i,j)$ such that $i\<j$ and $a\_i \> a\_j$. Denoting the number of inversions as $I$, insertion sort does $I$ swaps and $O(n) + I$ comparisons.

On the other hand, $I$ is the lower bound on the number of swaps for any algorithm which swaps adjacent elements, so bubble sort can't do better than that. Also, it's easy to construct an example when any implementation of bubble sort will require $n (n-1) / 2$ comparisons (e.g. swap the smallest and the largest elements in the smallest arrays), while the number of inversions is $O(n)$.

Finally, there are some optimizations that you can do in the insertion sort:

* You can implement swaps more efficiently. When you want to insert $k$ into the sorted prefix of the array, you just need to store $k$, shift all elements that are greater than $k$ to the right, and place $k$ in the freed-up position.
* You can guarantee that there are at most $O(n \log n)$ comparisons by using binary search.
> 0 votes

# Answer
Compare bubblesort with a selection sort that looks for the largest element and moves it to the end.

You will see that both actually make the exact same comparisons, finding the largest array element. Bubblesort also moves elements around so the indices it compares constantly change, but the values compared are the same. This extra movement after most comparisons makes bubblesort slower. Most of its n^2/2 comparisons are followed by a swap, and selection sort doesn’t need to do that. Selection sort can manage with one single exchange per element.

So: n^2/2 compare + swap operations vs n2/2 compare operations plus a tiny number of swaps.
> 0 votes

# Answer
It is very informal, but intuitively in case of bubble sort on each step you do a smallest possible step towards the goal (swap elements next to each other) while in selection sort you can do long jumps towards the goal.
> -1 votes

---
Tags: algorithms, runtime-analysis, efficiency, sorting
---


# Question
Title: How can one byte hold 256 possibilities?
Forgive this seemingly "troll-ish" question, but I must lack the ability to understand how one byte (two nibbles, eight bits, however you wish to describe it) can hold **256 different states, possibilities, values or such.**

First of all, one bit would look like this:

Any way of being able to input two states (in the poor example above, two separate circuits at different voltages can be treated logically as "yes" or "no").

So if one bit is two possible states, multiplication factors yield that by two:

Bit = 2 values

Two bits = 4 values

Three bits = 6 values

Four bits = 8 values

Five bits = 10 values

Six bits = 12 values

Seven bits = 14 values

Eight bits = 16 values

In total, I get a sum of sixteen values multiplying the factors by two for every increasing bit. How would it make sense that one byte can hold 256 different values in a circuit?

In a four bit adder, we'd have something like this:

This also yields 8 possible values. How would it get 128? Could anyone clarify this confusion??

NOTE: This doesn't have to just apply to adders circuits with transistors and logic gates, but to the pits and lands on an optic disc, the platter representation of data on a disk drive, flash drive binary storage, RAM, anything. I just want to know how increasing factors of two is multiplied by (seemingly) powers thereof.

# Answer
> 36 votes
I just did a quick animation to convince you. Yellow is one, blue is zero.

# Answer
> 10 votes
You said you were going to multiply by two each time but you added.

The simplest way to see it is just to count them.

One bit: 0 or 1 -- two values.
Two bits: 00, 01, 10 or 11 -- four values.
Three bits: 000, 001, 010, 011, 100, 101, 110, 111 -- eight values.
Four bits: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 -- sixteen values.

etc.

# Answer
> 4 votes
Forgive this seemingly "troll-ish" answer, but I think that perhaps you should learn how to count — in binary, that is, and using eight-bit strings to represent the numbers.

Follow after me.

```
Zero:   00000000
One:    00000001
Two:    00000010
Three:  00000011
Four:   00000100
Five:   00000101
Six:    00000110
Seven:  00000111
Eight:  00001000
Nine:   00001001
Ten:    00001010
Eleven: 00001011

```

and so on. Take the time to actually carry on this process, *at least* to one hundred. It won't take long, and it will help to build into you the visceral understanding of exactly how it is that eight bits can represent two hundred and fifty six possibilities — you will not merely *know* it, you will *grok* it.

# Answer
> 2 votes
I thought a simpler way to understand this is to think of how we count numbers. If each unit of 10s were considered a bit with 10 possible states, then 2 bits would have 100 possible states, or 10\*10. 3 bits would thus have 1000 states or 100\*10, which is also expressed as 10\*10\*10 10^3. In the case of binary, each unit or bit has only 2 possible states, thus 1 bit = 2, 2 bits=2\*2=4, 3 bits=4\*2 or 2\*2\*2 or 2^3=8 and so on and so forth. So if 8 units (bits) of 10 yields a hundred million of states, it should be quite easy to fathom how 8 bits of binary could yield 256 (if you count the first 0 as a state).

# Answer
> 1 votes
Your misunderstanding and confusion comes from very basic point that you should not multiply 2 into the number of bits. Instead you should use power function.

So your calculations should become like these:

> 1 Bit = 2 values -\> 1^2 =2, Your answer is correct
>
> Two bits = 4 values - \> 2^2=4. Your answer is correct
>
> Three bits = 6 values -\> 2^3=8\*, Your answer is incorrect. You have multiplied 2\*3 which is incorrect.
>
> Four bits = 8 values - \> 2^4 = 16 Your answer is incorrect. You have multiplied 2\*4 which is incorrect.
>
> Five bits = 10 values -\> 2^5=32, Your answer is incorrect. You have multiplied 2\*5 which is incorrect.
>
> Six bits = 12 values -\> 2^6=64, Your answer is incorrect. You have multiplied 2\*6 which is incorrect.
>
> Seven bits = 14 values -\> 2^7=128, Your answer is incorrect. You have multiplied 2\*7 which is incorrect.
>
> Eight bits = 16 values -\> 2^8=256, Your answer is incorrect. You have multiplied 2\*8 which is incorrect.

* Let me explain why do you need to use power function (2^3) instead of multiply (2\*3) to find the number of values to show using 3 bits. Using various combination of each bit you can show the following values

> 000 ----\> 0
>
> 001 ----\> 1
>
> 010 ----\> 2
>
> 011 ----\> 3
>
> 100 ----\> 4
>
> 101 ----\> 5
>
> 110 ----\> 6
>
> 111 ----\> 7

From 0 to 7, there are 8 numbers.

Similarly for 4 bits, you can replicate the same rule.

> 0000 ----\> 0
>
> 0001 ----\> 1
>
> 0010 ----\> 2
>
> 0011 ----\> 3
>
> 0100 ----\> 4
>
> 0101 ----\> 5
>
> 0110 ----\> 6
>
> 0111 ----\> 7
>
> 1000 ----\> 8
>
> 1001 ----\> 9
>
> 1010 ----\> 10
>
> 1011 ----\> 11
>
> 1100 ----\> 12
>
> 1101 ----\> 13
>
> 1110 ----\> 14
>
> 1111 ----\> 15

Which are 16 numbers. So we need to say 2^4 = 14. Using multiplication is incorrect. So, for 8 bits, you can repeat it from

> 00000000 ---\>0
>
> .
>
> .
>
> .
>
> 11111111 ----\> 255

One more point, I can guess you have one more confusion. Let me tell you that If you want to know the ***largest*** number you can store in a byte, it is good to know that it is 255! not 256 not even 512.

# Answer
> 1 votes
The calculation is not x\*2. It is in fact, the number of states one bit can hold (2) to the power of however many bits there are. This means it is exponential. The formula would also work for tertiary systems. Going back to binary, 2^8 = 256. 2^1 = 2, and 2^4 = 8. These are just a few examples but this makes more sense if I explain it properly, so, to represent a number with binary didgits, the computer uses the first column for "1", The second for "2", the third for "4" and the fourth for "8". You may not have noticed the trend here, the number of states possible is going to be the highest number possible to present with the given bits, plus one for "000000"etc., therefore shifting the 111111111etc. To the next column, 10000000etc. Because 10000 is 1 more than 1111 in binary.

# Answer
> 1 votes
I am afraid that you did not think much about this issue.

Clearly, a single bit encodes two states, $0$ and $1$.

Then for two bits, if you claim that the number of states is four, then they must be $00, 01, 10, 11$ (another option would be just two states, $00$ and $11$, or - why not - setting the bits from left to right, $00,10,11$, for three states.)

Now for three bits: the trivial option is $000, 111$ (two states), the "setting" option is $000,100,110,111$ (four states) and the fully symmetric option can only be $000,001,010,011,100,101,110,111$ (eight states). I can't think of another enumeration that makes sense.

It is up to you, as an exercise, to generalize to eight bits.

---

There are at least two ways to count the number of states:

* all $b$ bits states can be obtained by concatenating either a $0$ or a $1$ to all $b-1$ bits states; this way all states are different, and no possibility is missed. E.g., there are four two-bits states, hence twice as many three-bits states, which is eight.
* you can write separately all states with no one, with a single one, with two ones, and so on, and all these can be permuted a certain number of times. E.g.

+ $000$, a single permutation.
    + $001$, three permutations (move the $1$ to any place).
    + $011$, three permutations (move the $0$ to any place).
    + $111$, a single permutation.

Again, the total is eight. Note that the numbers of permutations are known from combinatorial analysis as the Binomial numbers.

Finally, ponder the identities

$$2^b=2^{b-1}\cdot2,\\\sum\_{k=0}^b\binom bk=2^b.$$

# Answer
> 0 votes
Visualizing the possibilities of a coin toss (instead of bits) helped me wrap my head around this issue, perhaps it might help you as well: (A = heads, B = tails)

One coin (2 possibilities = 2 x 1; head or tail shown as A B):

```
A   B

```

Two coins (4 possibilities = 2 x 2; AA = head & head, AB = head & tail, etc.):

```
AA   BB
_
AB   BA

```

Three coins: (8 possibilities = 2 x 2 x 2)

```
AAA   BBB
ABA   BAB
_
AAB   BBA
ABB   BAA

```

Four coins: (16 possibilities = 2 x 2 x 2 x 2)

```
AAAA   BBBB
ABAA   BABB
AABA   BBAB
AAAB   BBBA
_
ABBA   BAAB
ABAB   BABA
AABB   BBAA
ABBB   BAAA

```

Each new coin added, the possibilities get larger exponentially.

# Answer
> 0 votes
Let’s say with k bits we have n values.

If we add a bit, then we have n values where the added bit is set, and n values where the added bit is not set. Total 2n values. Every bit doubles the number of possible values.

0 bits: one possible value of nothing.
1 bit: twice as many values, that is two.
2 bits: twice as many values, that is four.
3 bits: twice as many values, that is eight (not six).

Since we know decimal better: One digit = ten possible values 0 to 9. Two of three digits don’t give 20 or 30 possible values, but 100 two digit values from 0 to 99 and thousand three digit values from 0 to 999.

---
Tags: combinatorics
---


# Question
Title: How reversing the edges of the graph not altering the original conditions?
I was going through the main idea of solution to this problem. I could not assimilate the idea of reversing the edges and then using that graph to check if node 1 is reachable from all others.

How come reversing the graph not affect the original conditions and is applicable to be used for the intended purpose? Is this graph not entirely different?

Is there some explaination which is **obvious** with respect to the problem? What exactly is happening here? Any explaination would be helpful. TIA.

# Answer
> 1 votes
Fix some vertex $u$. Consider the following observations:

* A path that ends at vertex $u$, which originates from some other vertex $v$ will be a path that originates from $u$ and ends at $v$ in the reversed graph.
* You can test if a vertex $u$ reaches all other vertices $v$ via DFS starting at $u$ in the original graph.
* You can test if all other vertices $v$ can reach $u$ via DFS starting at $u$ in the reversed graph
* If all vertices can be reached by $u$ and all vertices can reach $u$ then all pairs of vertices are reachable from each other since any vertex can reach any other vertex by passing through $u$.

---
Tags: algorithms, graphs, data-structures, connected-components
---


title: Deleting in Bloom Filters

text:
# Question
Title: Deleting in Bloom Filters
I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete operation--for example: counting Bloom filters. I heard also about another method, which uses a second filter. If I want to remove an element I have to 'insert' it into this second filter. I can't find how this proposed structure operates, any article about it, or even the name of the originator. Maybe someone can share with me with a link to any interesting articles about this method? I found a lot of articles about counting Bloom filters and other methods, but I can't find any description of this one.

# Answer
I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions.

As this is a very simple solution, it might be considered as a folklore.

Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems):

http://www.dca.fee.unicamp.br/~chesteve/pubs/bloom-filter-ieee-survey-preprint.pdf

Search for:

> Removal of an element can be implemented by using a second Bloom ﬁlter that contains elements that have been removed

In the third section of this paper, you can read about many techniques to deal with deletion. Maybe you will find there some reference (again - I'm not sure there is some paper about it, as it is a simple idea).
> 8 votes

# Answer
Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when inserting. When removing an element, you can then decrement all of its related integers.
> 3 votes

# Answer
You can use the concept of invertible bloom filters. See here for a nice explanation. Invertible bloom filters allow you to retrieve and delete key/value pairs from the filter.
> 0 votes

# Answer
You can use a "counting bloom filter" which uses integers instead of bits for each item stored. Increase integer when adding, decrease integer when deleting. Uses more storage, of course.

https://en.wikipedia.org/wiki/Counting\_Bloom\_filter
> 0 votes

---
Tags: reference-request, data-structures, probabilistic-algorithms, bloom-filters, dictionaries
---


title: Number of islands

text:
# Question
Title: Number of islands
In the counting number of islands problem, I noticed that one of the solution from internet is as follows

```
def visitIslandDFS(grid,  i,  j):
    if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0])):
        return  # return, if it is not a valid cell
    if (grid[i][j] == '0'):
        return  # return, if it is a water cell

    grid[i][j] = '0'  # mark the cell visited by making it a water cell

    visitIslandDFS(grid, i + 1, j)  # lower cell
    visitIslandDFS(grid, i - 1, j)  # upper cell
    visitIslandDFS(grid, i, j + 1)  # right cell
    visitIslandDFS(grid, i, j - 1)  # left cell

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:
        numIsland = 0
        depth, width = len(grid), len(grid[0])
        for i in range(depth):
            for j in range(width):
                if(grid[i][j] == '1'):
                    numIsland += 1
                    visitIslandDFS(grid, i, j)
        return numIsland

```

My question is if we are traversing left to right and top to bottom and flagging off cells to zero, may I know the reason why we are checking left and top cells as well for checks? In other words, I am trying to understand why these two lines are needed?

```
visitIslandDFS(grid, i - 1, j)  # upper cell
visitIslandDFS(grid, i, j - 1)  # left cell

```

# Answer
> 2 votes
If you avoid the up and left displacements, the algorithm will only fill down and right of the seed pixel and can fail to cover whole blobs.

E.g. from the top left pixel

```
. x . x
x x x x

```

will be filled as

```
. o . x
x o o o

```

# Answer
> 2 votes
Imagine having an island of the form:

```
..X
X.X
XXX

```

The solution starts looking at the island in the top right cell (smallest $i$).

If you never go left or up, you would only visit the three right cells during the first DFS and count them as the first island, and later when you do a second DFS you find a second island.

However there should only be one single island here.

```
..1
2.1
221

```

# Answer
> -2 votes
The above two cases are redundant if one try to solve the problem by looping over all possible grids and running dfs . Another approach to solve the problem is by storing all the unvisited grids into a queue, iteratively running a dfs until the queue is empty, in this case we can't be sure about the order in which the grids are visited thus visiting all the cardinal directions are suited.

---
Tags: algorithms, python
---


title: Merge two binary search trees

text:
# Question
Title: Merge two binary search trees
Consider two binary search trees T1 and T2, each with height h, with all values in T1 less than all values in T2. I want to merge these both trees to get a new binary search tree of height at most h+1

**My Thoughts:**
The first thought was to put T1 as the left child of the leftmost node in T2. But the resulting bst will have height \> h+1 I am not sure if there is a clever way to achieve this

# Answer
Take the smallest element from $T\_2$ (it will be the left-most leaf) and call it $r$. Note that you may have to "fix" $r$'s right child by putting it in place of where $r$ was.

Make the new tree such that $r$ is the root, $T\_1$ is the left-child of $r$ and $T\_2$ (with $r$ removed) is the right-child of $r$
> 1 votes

# Answer
Either the rightmost node of the left tree or the leftmost node of the right tree can be used as a common root.
> 1 votes

---
Tags: binary-search-trees
---


# Question
Title: How to recover path, given unordered set of non-repeating arcs for directed graph?
Let's say I have a set of non-repeating arcs, e.g. `(0,1), (3,0), (0,3), (1,2), (2,3)`, ("set" because they don't repeat).
Here's an example of a graph for which this series of arcs would form a valid path:

And a valid path would be `(0,1), (1,2), (2,3), (3,0), (0,3)`.

Note that the path might not be unique (and that's fine). And I don't care where we start in the path, as long as all arcs in the set are traversed.

Given a directed adjacency matrix, how to put together a path describing this set of arcs? Seems to me like there should always be a way to do this. Having trouble putting together an algorithm to do so.

This question is related, but I'm trying to generalize from this: https://stackoverflow.com/questions/53761877/get-route-from-unordered-set-of-tuples

# Answer
Let $E$ be the set of your edges, and let $V$ be the set of all the edge's endpoints. Consider the graph $G=(V,E)$. You're asking for a Directed Eulerian trail of $G$.

One possible way to so so, is the following: assume that each vertex has the same in- and out-degree (more on how this assumption can be removed later) and look for an Eulerian cycle of $G$. Start from any vertex $u$, pick any outgoing edge $(u,v)$, walk to $v$, delete $(u,v)$, and repeat until encounter $v$ again. At the end of this process either you have followed an Eulerian cycle (i.e., you deleted all edges), or you followed a cycle $C$ and are left with a graph $G'$ containing some vertex $w$ that is in $C$ and has non-zero in/out-degree in $G'$. You can then repeat the above procedure from $w$ on $G'$ and merge the resulting cycle $C'$ with $C$ (on the shared vertex $w$). Continue repeating the above until you have a cycle that traverse all edges.

If not all vertices have the same in- and out-degree, then for an Eulerian trail to exist there must be exactly two distinct vertices $u,v$ that violate this property (these are exactly the endpoints of the trail). Find an Eulerian cycle $C$ of the graph $(V, E \cup \\{ (u,v)\\})$ or $(V, E \cup \\{ (v,u)\\})$ (whichever satisfies the property, if any) and then delete $(u,v)$ from $C$.
> 2 votes

---
Tags: graphs
---


# Question
Title: Multiplication of subnormal and normal numbers under IEEE 754
As far as I understand, when doing this operation, we first need to identify the subnormal value, normalise it, adjust the exponent, and then multiply the significands. Wouldn't it be advantageous to just multiply the significands and use a leading-zero counter on the result? It seems like removing some steps could speed things up. And I understand that a leading-zero counter could be expensive, but I have the impression that today there are many fast implementations that could be used instead.

# Answer
> 3 votes
Above all, hardware floating-point units are optimised for normalised numbers.

Multipliers, and even more dividers, can be a bit simpler if the two inputs are already normalised :

* there is the implicit leading 1 always in the same place.
* rounding as well always occurs on same digits, which can allow some simplifications for bits that will discarded.
* most division algorithms (Newton, SRT, ...) only really work with normalised numbers.

Floating point Adder/subtractors need to re-aling mantissas before doing the addition/subtraction, even for normalised numbers, sometimes this shifter can be reused for re-normalisation before multiplication.

# Answer
> 2 votes
You have to check not only for denormalised numbers but also for zeroes because inf x denormalised = inf, but inf x 0 = NaN. And you can use the usual method for division as well, where it is extra valuable. Much better to use the exact same first part of the hardware, you need to design it only once.

Someone might have tried this and rejected it. Someone might actually be implementing it and tells nobody. You’d have to talk to some engineers at Intel, AMD, Arm, ibm, apple to find out.

But please write down the complete steps to do a fused multiply-add. With no hand waving. Complete. Removing one case at the very start to remove complexity is usually helpful.

---
Tags: floating-point
---


title: Context free Grammar for x1#x2#...#xn

text:
# Question
Title: Context free Grammar for x1#x2#...#xn
Design a Context-free grammar **(CFG)** for this language

# Answer
> 0 votes
To understand the idea behind the grammar first consider the **Pushdown Automata** for this langugage: Non-deterministically choose either the beginning or any $\\#$, push the string between the chosen position and the next $\\#$ symbol. Again non-deterministically choose another $\\#$ and start popping out the symbols in the stack if they match with the current symbol being read. If we reach the next $\\#$ and the stack becomes empty, then we have found two positions $\exists i,j : x\_i = x\_j^R$, and hence the word is in the language.

*(I'll suggest you now to stop reading the answer and try writing the grammar on your own)*

**Grammar** (let $\Sigma = \\{a,b\\}$: \begin{equation} S \rightarrow A\\#B|A\\#B\\#A\\ A \rightarrow aA | bA|\\#A|\epsilon\\ B \rightarrow \\#\\#|aB'a|bB'b\\ B' \rightarrow aB'a|bB'b|\\#A\\#|\\# \end{equation}

\*It might be written more succinctly perhaps. You can try that.

# Answer
> 0 votes
Consider the following grammar:

```
S → A | B
A → aA | bA | ɛ
B → C | B#B
C → aCa | bCb | aDa | bDb
D → # | #B#

```

The first rule (S) basically says that our string can be anything (rule A) without any delimiting #'s, or will follow the ...$\\#x\\#...\\#x^R\\#$... pattern (rule B).

For rules B, C, and D, think about how some strings in the $L\_1$ are derived, and how these derivations will eventually terminate.

---
Tags: context-free
---


# Question
Title: Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $\[-1,1\]$. The function is accessible via *queries*: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)\<0$ and $f(1)\>0$, then by the intermediate value theorem, $f$ has a *zero* --- an $x \in \[-1,1\]$ for which $f(x)=0$. Suppose we want to find a zero approximately, that is: given $\delta\>0$, find an interval of length at most $\delta$, that contains a zero. This can be done using binary search: start with the entire interval $\[-1,1\]$; let $c$ be the middle of the interval; if $f(c)=0$ we are done; if $f(c)\>0$ then recursively search between the leftmost end of the current interval and $c$; if $f(c)\<0$ then recursively search between $c$ and the rightmost end. After $O(\log(1/\delta))$ steps, the interval length is at most $\delta$. So the run-time is polynomial in the length of the binary representation of $\delta$.

Now, suppose we have *two* continuous functions, $f$ and $g$, both defined on $\[-1,1\]\times\[-1,1\]$. Suppose $f(-1,y)\<0$ for all $y$ and $f(1,y)\>0$ for all $y$, and $g(x,-1)\<0$ for all $x$ and $g(x,1)\>0$ for all $x$. By the Poincare-Miranda theorem, there exists a *double-zero*, that is, a point $(x,y)\in\[-1,1\]\times\[-1,1\]$ such that $f(x,y)=g(x,y)=0$. We want to find a double-zero approximately, that is: given $\delta\>0$, find a square of side-length at most $\delta$, that contains a double-zero. Is it possible to do in time $O(poly(\log(1/\delta))$?

I tried to apply binary search, but it did not work. If I could know, for example, that for some $c\in\[-1,1\]$, $f(c,y)\<0$ for all $y$, then I could recursively search the rectangle $\[c,1\]\times\[-1,1\]$. But there is no reason to think that such a $c$ exists.

**Can this problems be solved using $O(poly(\log(1/\delta))$ queries?**

# Answer
> 3 votes
This paper studies a similar problem: finding an approximate fixed-point of a two-dimensional function from the unit square to itself, which is accessible via value queries. The authors prove that computing a fixed point with $p$ decimal digits requires $\Omega(2^p)$ queries. Equivalently, computing a square of side-length at most $\delta$ that contains a fixed point requires $\Omega(1/\delta)$ queries.

---

I claim that the same is true for finding a double-zero with *general* functions. The proof is by reduction from the fixed-point problem. Let $h$ be a continuous function for which we want to find a fixed point, and suppose it is a function on the square $\[-1,1\]^2$. Define two functions $f$ and $g$ as follows:

$$ f(x,y) := x - h(x,y)\_1 \\ g(x,y) := y-h(x,y)\_2 $$

Note that $$ f(-1,y) \leq (-1) - (-1) = 0 ~~~~ f(1,y) \geq 1 - 1 = 0 \\ g(x,-1) \leq (-1) - (-1) = 0 ~~~~ g(x,1) \geq 1 - 1 = 0, $$ so the pair $(f,g)$ has a double-zero. Moreover, $(x,y)$ is a double-zero of $(f,g)$ if and only if it is a fixed point of $h$. Therefore, finding an approximate double-zero requires $\Omega(1/\delta)$ queries.

---

For the case of *monotone* functions, I asked a separate question in cstheory.SE.

---
Tags: algorithms, search-algorithms, binary-search, mathematical-analysis, real-numbers
---


# Question
Title: Chaitin’s version of Gödel’s theorem and pseudorandomness
Chaitin’s version of Gödel’s theorem roughly states that there exists a constant c such that for each string of one’s and zeroes x, the sentence “the algorithmic information complexity (Kolmogorov complexity) of x is greater than c” is unprovable, even though there are an infinite number of x’s in which the sentence is true.

I am wondering if it were possible to prove an analogous statement in computational complexity theory with respect to pseudorandomness - that for each function f, the sentence “f is a pseudorandomn number generator” is unprovable, even though there are maybe many such functions f in which the sentence is true.

Is there anything in the literature that addresses this question?

# Answer
> 2 votes
It's unlikely you're going to prove anything like that. There are plenty of candidates that are believed to be likely to be pseudorandom generators (PRGs). It would be surprising if they aren't PRGs, and it would be surprising if they are PRGs but that fact is unprovable.

---
Tags: complexity-theory, pseudo-random-generators, kolmogorov-complexity
---


# Question
Title: How do you convert a string representing a finite set of strings into a regulair expression without using lots of vertical bars?
Consider the following string:

```
stryng = "{\"Jordi\", \"Jordy\", \"Jorde\", \"Jordie\", \"Jordee\", \"Joardi\", \"Joardy\", \"Joarde\", \"Joardie\", \"Joardee\"}"

```

That string represents a mathematical set of strings.

$\begin{Bmatrix} \mathtt{Jordi}, \mathtt{Jordy}, \mathtt{Jorde}, \mathtt{Jordie}, \mathtt{Jordee}, \mathtt{Joardi}, \mathtt{Joardy}, \mathtt{Joarde}, \mathtt{Joardie}, \mathtt{Joardee}\end{Bmatrix}$

If you have a string representation for a set of strings, such as `{"i", "y", "ee"}`, how do you convert that set of strings into a regular expression without the logical-disjunction vertical bar `|`?

I was hoping to have something like a character class except that instead of characters we used strings such that some of the strings were longer than one letter each.

For example, something close to a regular expression might be:

```
Joa?r{"i", "y", "ee"}

```

That fake regex was intended to represent the set of all strings **σ** such that...

> 1. The leftmost part of **σ** is `J`
> 2. The part of **σ** second from the left is `o`
> 3. The part of **σ** third from the left is zero or one instance of the letter `a`
> 4. The fourth part of **σ** is the letter `r`
> 5. The fifth part of **σ** is exactly one of the strings `i`, or `y`, or `ee`.

There is a regular expression `[iye]e?` which is somewhat like the following set:

> `{"i", "y", "e", "ie", "ye", "ee"}`

We want to forbid the string `ye`.

In a python-flavored regex used in the library named `re`, can we write a set of strings, or do we have to write something else?

# Answer
> 1 votes
If `Jordye` was in the set too, then `Joa+rd[iye]e+` would work, where:

* `[iye]` means "one character which can be `i, y` or `e`";
* `a+` means "zero or one `a`".

But without `Jordye` in the set I'm afraid you have to content with either

```
Joa+rd(i|y|e|ie|ee)

```

or

```
Joa+rd([iye]|[ie]e)

```

or

```
Joar+rd(y|[ie]e+)

```

The last one translated directly to a deterministic automaton:

```
                           >O
                        y /
      J    o    r    d   /
--->o--->o--->o--->o--->o--->O
             /^          ie /^
             \/a            \/e

```

---
Tags: regular-expressions, compilers, parsers
---


title: Numerical Approximation in Java

text:
# Question
Title: Numerical Approximation in Java
I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is: $$\frac{2\*\sqrt{\pi}\*h\*s\*e^{m^{2}/(2\*s^2)}}{\sqrt{2}} = a$$ where $h, m,$ and $a$ are given constants. This is for a project that I'm writing in Java, and it would be infeasible to grab the solution output from another program such as Matlab, Mathematica, or some other scientific computing language for a couple reasons, one of which is that I will have to solve this equation hundreds of times with different values. Basically I am wondering if anybody knows of a library I can easily import and use for this kind of problem, and to possibly spell out how I would go about doing that. So far I have been looking through math libraries such as Apache Commons Math but cannot find out if they are appropriate. Thanks!

# Answer
With $p:=\dfrac ms$, squaring and collecting all the constants to avoid the mess, the equation reads

$$e^{p^2}=\lambda p^2$$ or $$-p^2e^{-p^2}=-\lambda^{-1}.$$

Hence using the Lambert function,

$$s=\frac m{\sqrt{-W(-\lambda^{-1})}}.$$

The positive square root must be taken, and the two branches of $W$ yield two real solutions (provided $\lambda\>e$).

You can probably find ready-made implementations of that function in Java, or adapt from a C/C++ version.
> 1 votes

# Answer
You are asking how to solve $e^{ax^2}=b$ for $x$, given constants $a,b$. The solution is $x=\sqrt{\frac{1}{a} \log b}$, which can be computed (approximately) using standard algorithms for computing the log and the square root.

In particular, your specific equation has the solution

$$m = \sqrt{2s^2 \log (a/(\sqrt{2\pi} hs))}.$$

You can verify the correctness of this solution by plugging into the equation and verifying it works.
> 0 votes

# Answer
Quote: "I don't think it's that simple. I am fairly certain that you cannot find a symbolic solution for x with the equation I provided above. "

$$\frac{2\*\sqrt{\pi}\*h\*s\*e^{m^{2}/(2\*s^2)}}{\sqrt{2}} = a$$

Multiply both sides by sqrt (2).

Divide both sides by 2 sqrt(pi) h s.

Take the natural logarithm.

Multiply by 2 s^2.

Take the square root.

Now m is alone on the left side, and the right side is the solution:

$$m = \sqrt {\ln (\frac {a \cdot \sqrt{2}}{2\*\sqrt{\pi}\*h\*s}) \cdot (2\cdot s^2)}$$

(Of course it would help if you posted the problem you have, and not a different problem).
> 0 votes

---
Tags: approximation, numerical-analysis, java
---


# Question
Title: What's the relation between DPLL and BDDs?
BDDs are a way of representing Boolean formulas.

DPLL is an algorithm to determine satisfiability of Boolean formulas.

My understanding is that the two are used for SAT solving.

How are they combined?

# Answer
> 1 votes
They're not combined. They are two separate techniques.

DPLL is used with a Boolean formula represented in CNF form. BDD algorithms represent the Boolean formula as a BDD.

Generally, if you want to test satisfiability, DPLL-based SAT solvers are likely to be more effective. BDDs do allow performing other operations that go beyond satisfiability, which might be useful in some settings.

As a rough rule of thumb, BDDs are older technology and SAT solvers are newer technology, and for many tasks we're trying to automate, solutions that build on SAT solvers tend to outperform solutions that build on BDDs. But it all depends on the specific problem you're dealing with, and there are no hard-and-fast rules.

---
Tags: algorithms, satisfiability, sat-solvers, bdd
---


# Question
Title: Is there a algorithm to determine if a regular language (expression) is subset of another?
Given two regular languages (fx given by it's accepting regular expression), is there an algorithm to determine if one is a subset of the other?

# Answer
Yes, there is an algorithm for it, but there is unlikely to be an efficient algorithm.

Notice that you can convert between a regular expression and a NFA in polynomial time. Moreover, determining whether one regular language is a subset of another, if both are represented as NFAs, is PSPACE-complete. Therefore, there is unlikely to be a polynomial-time algorithm for this, unless there is a huge surprise in complexity theory.

See Is there an efficient test for if an NFA accepts a subset of another NFA?. Related: Is language decideable (subset)?.
> 1 votes

---
Tags: computability, regular-languages, regular-expressions
---


# Question
Title: Given the 300k words -> find all words with given letters present (in any order)? Any Data structure for this?
Does anyone know of the data structure/algorithm for this use case? Given 300k words, -\> find all words with some letters present (letters could be in any order)?

For example find all words with letters a,a,d? (so for example "academics" and "captained" are some of the matches)

I initially looked into GADDAG, but it's not really a good fit here as gaddag is designed more for use cases with sequential substrings.

# Answer
I agree with D.W. that there likely isn't a good general solution, and as long as we don't know exactly what the expected sequence of input is, and how the dictionary looks like, it's hard to give good answers.

I would (for lack of better information) simply cache all possible combinations of queries. Say that the user input is always three letters, then I would go through the dictionary and simply map every possible collection of three letters to the respective words:

```
S = collections.defaultdict(set)
for word in dictionary:
  for comb in itertools.combinations(word, 3):
    S["".join(sorted(comb))].add(word)

```

Now, a query is simply:

```
query = input("Enter query (three letters): ")
print(S[''.join(sorted(query))])

```

Attached below is a small program that I wrote, just for fun.

Usage:

```
(e39) [~]$ python query.py /etc/dictionaries-common/words
19969 combinations cached
Enter string (Q or ctrl-d for exit): kebx
jukebox
textbook
2 words matched bekx

```

```
Enter string (Q or ctrl-d for exit): aabcd
abdicate
bacardi
backdate
backhand
backward
backyard
balanced
cambodia
carlsbad
drawback
hardback
scabbard
12 words matched aabcd

```

You can also find the most esoteric words (for some definition):

* buzzword
* flapjack
* jacquard
* jaxartes
* jukebox
* qiqihar
* squawked
* vanquish
* zyuganov

```

import sys
from itertools import combinations as choose
from collections import defaultdict as D

def add_choose(S, word, k):
    choose_k = ["".join(sorted(w)) for w in choose(word, k)]
    for w in choose_k:
        S[w].add(word)

ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def isalpha(w):
    for c in w:
        if c not in ALPHABET:
            return False
    return True

def read_file_to_cache(fname):
    S = D(set)
    with open(fname, "r") as fin:
        for l in fin:
            word = l.strip().lower()
            if isalpha(word) and 3 <= len(word) <= 8:
                for i in range(1, 6 + 1):
                    add_choose(S, word, i)
    return S

def run(S):
    while True:
        q = input("Enter string (Q or ctrl-d for exit): ")
        if q == "Q":
            break
        q = "".join(sorted(q.strip().lower()))
        res = sorted(S[q])
        print("\n".join(res))
        print(f"{len(res)} words matched {q}")

if __name__ == "__main__":
    if len(sys.argv) != 2:
        exit("Usage python query.py dictionary_file")

    S = read_file_to_cache(sys.argv[1])
    print(f"{len(S)} combinations cached")
    run(S)

```
> 2 votes

# Answer
There's unlikely to be any really good solution, but here is an approach.

For each word in your dictionary, sort the letters in alphabetic order. For instance, "smile" becomes "eilms" and "honolulu" becomes "hllnoouu". Store these words in a trie.

Next, given a query (a set of required letters), you can traverse this trie in any order (say, depth-first), pruning the traversal at any node that fails to contain one of the required letters.

The effectiveness of this is likely to depend on the distribution of queries you get. There are many other approaches possible, and to optimize to the greatest extent possible, we'd probably need to know some information about the expected workload (typical number of required letters, any structure in the queries or are they basically random, etc.).
> 0 votes

---
Tags: data-structures
---


# Question
Title: Ford-Fulkerson algorithm running in pseudo-polynomial time
Consider a graph with $n$ nodes and $m = \mathcal{O}(n^2)$ edges. The maximum capacity among all edges is denoted by $C$. The running time is given by: $\mathcal{O}(nmC)$

If I consider the input size in bits, it can be stated as: $\mathcal{O}(n \log n + m \log n + m \log C)$

Denote $v:= \log n, b:= \log C $.

Then it holds: $\mathcal{O}(nv+ m (v+b))$

Why can I rewrite the running time in the following way: $\mathcal{O}(mn2^b)$

Why does $2^v \leq C2^b$ hold?

# Answer
Note that the L.H.S. is $\mathcal{O}(n \log n + m \log n + m \log C)$.

It is easy to see the following three inequalities:

1. $n \log n \in \mathcal{O}(mn2^b)$
2. $m \log n \in \mathcal{O}(mn2^b)$
3. $m \log C \in \mathcal{O}(mn2^b)$

Therefore, $\mathcal{O}(n \log n + m \log n + m \log C) \in \mathcal{O}(mn2^b)$.
> 1 votes

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


title: Is Quantum Computer analog?

text:
# Question
Title: Is Quantum Computer analog?
We used to have analog computers several decades ago. Modern days computers are Digital. What about Quantum computers? Is it analog or digital? I am asking this since qubit can be many things at the same time.

# Answer
> 9 votes
No, quantum computers are not the same as analog computers (at least in principle).

Analog computers simulate the (mathematical) problem to be solved by building a physical system that obeys the same constraints/laws as the mathematical problem. The answers are obtained by observing and measuring the behavior of the physical simulation. Its accuracy is that of the simulation (there may be parasitic effects), the accuracy of the initial conditions, the setting of problem parameters in particular, and the measurement on the result.

Accuracy may also be limited by the scale range of applicability of the phenomena used for the simulation. For example, if the answer is given by a level of water in some container, you may be limited by capillarity effects (which can be accounted for to some extent) and by the fact that measuring water level with more accurcy that the diameter of a molecule may not be very meaningful.

I used to think that a major difference is that analog computing is in principle based on the simulation of continuous laws, involving reals, while digital computing operates exclusively on countable sets. But, in the light of current knowledge in computing theory, this distinction is probably naive because I suspect that physics could be formalized as well using only computable reals, of which there is only a countable number.

Quantum computing will mainly allow you to do several digital computations in parallel (to state it simply). It is always a finite cross product of several computations, and hence stays in the countable realm. You may think of it as the cross-product construction of an automaton that simulates two or more computations of simpler automata (though it is even less general than that from what I understand of it). These finite cross product constructions never leave the countable realm.

# Answer
> 7 votes
In general, a quantum computation is thought of as a digital computation, however there is a variant of quantum computer called a "continuous variable quantum computer" or CVQC, that can be considered an analog computer. I believe they are primarily used in quantum simulation, but they are not something I have studied, so I don't know much more about them than the acronym.

With that said, there are things about "digital" quantum computers that seem very analog. For example, say you start with a quantum register in the ground state, and then you evolve the state unitarily, and finally measure the state.

In some sense, you started with a zeroed out array of classical bits, and ended with an array of classical bits which were the result of the computation, but the unitary evolutions in-between seem very analog. They must be modeled with complex matrices, and the states resulting from the unitary transformations have real amplitudes, etc. But because the output is clearly digital, we consider it a digital computation.

If we could "measure" electron spin wrt an axis (for instance) and get an arbitrary real value, then quantum computing would be analog... But then we would be living in some other universe, with even weirder physics :P

# Answer
> 3 votes
While most schemes for making quantum computers involve digital techniques, there are indeed some analog devices called adiabatic quantum computers (AQC). See Going digital may make analog quantum computer scaleable | Ars Technica for more details.

See also Colloquium: Quantum annealing and analog quantum computation

# Answer
> 2 votes
I believe I understand the basis of your question: The information encoded in one bit in an ordinary modern computer can be described by two (binary) values, commonly written as 0 or 1 or (better for the point at issue) as +1 or -1. However, if you wish, this can be depicted graphically as something being at the north pole or the south pole of an Earth-like sphere. This would be a needlessly elaborate way of depicting how a bit holds information, but it is legitimate. Would navigators bother to use an analog globe if they existed only on the two poles?

The information encoded in a quantum computer cannot be written as either a +1 or -1, fundamentally because the information encoded in a qubit (the quantum-computer equivalent of a bit) can have any value between +1 and -1. One way of depicting this is on a sphere that, like a globe, has analog latitude and longitude markings.

Such a sphere can be the Bloch sphere, a unit sphere borrowed from solid spherical geometry and trigonometry. We can give such a sphere lines of latitude and longitude. The bad new is that encoding a point between the poles now entails less familiar trig and complex numbers. The good news is that any such point can be clearly evaluated, including for describing the information encoded in a qubit. Yes, in effect this Bloch sphere resembles an obviously analog globe! In this sense I agree; quantum computers can be envisioned as relying on analog mathematical tools.

# Answer
> 2 votes
This is an interesting question. I partially agree and partially disagree with previous answers so maybe it is worth adding mine.

Of course, a QC is different from old-time analog computers, but only because of its "quantumness", which has little to do with its being analog vs digital. A QC is definitely **not a digital system**, in any meaningful way. It lacks all the fundamental characteristics that I would say characterize a digital system:

1. Differently from an analog system, a digital one partitions the continuum of possible configurations in a set of discrete ranges (or logic levels if you like to think about 0s and 1s);
2. The computing system continuously projects its configuration on one of the conventional discrete ones. This happens at every single logic gate. Take the NOT gate, whenever the input voltage is above V\_IH, the gate interprets the input as "1" and projects the output to the conventional "0";
3. The crucial benefit (why do digital systems exist, in the end?) of this whole procedure is noise immunity, and one cost is dissipation.

A QC does not fit well in any of these points. Forget about the existence of qubits: this is about irrelevant. The fact that the wavefunction of a QC is given by the product of the wavefunction of many qubits simply sets the basis of the Hilbert space, but a quantum memory can (and has to be able to) exist in an uncountable number of configurations represented by all the complex amplitudes that describe its wavefunction. Take even a one-qubit memory: it can exist in an infinite number of superpositions of 0 and 1, that are on a one-to-one correspondence with the points of the surface of the Bloch sphere... which are definitely uncountable. This is very different from a bit, which can only have two configurations.

In addition, there is no projection at every quantum gate, and surely no dissipation. Quantum computing is even reversible, in principle: this is the opposite of a dissipative system. A QC indeed **needs** to preserve the full quantum information of its qubits, all the amplitudes, entanglements, and so on, which are pretty much continuous. It only projects its configuration on one of the classic states at the end of the calculation, at the read-out stage.

In short, a QC is a (quantum) analog computing system.

---

EDIT - About quantum parallelism.

This is sometimes brought up, and summarized as "a QC somehow is performing many (digital?) computations in parallel". This is a compelling and very communicative view, but I think it easily leans toward the misconception. This is a tricky concept. A QC performs its computation on a "superposition" of configurations of a digital classic computer. First of all, this is not the superposition most people think about: this is a quantum superposition and one has no access to the results of the individual calculation... actually, the result of the individual calculation *does not even exist*, since during the calculation intermediate and final results will be in quantum superposition and give rise to interference... One can only interrogate (statistically) the final result, which depends on the coefficients that describe the superposition.

In my view, the only important question in the analog vs digital discussion is "how information is encoded?". In a standard computer, it is encoded in the state of the memory, which is definitely digital. My DNA also encodes information in a digital form. A QC does not. To be direct, consider an 8-qubit quantum memory. The qubits just set the basis of the Hilbert space, which will be 00000000, 00000001, and so on: a 256-dimensional Hilber space. The information contained in the memory is encoded in the density matrix, which is a 256x256 hermitian matrix, with a very large number of *analog* amplitudes. Not digital, those amplitudes are not segmented in any way in a discrete set of conventional intervals.

In the end, if a QC were digital, people would not fight so much with error correction. Noise immunity is the main reason for the existence of digital systems.

# Answer
> 0 votes
Yes and No. Dictionary Definitions from Oxford Languages · Learn more an·a·log adjective adjective: analogue; adjective: analog

```
relating to or using signals or information represented by a continuously variable physical quantity such as spatial position, voltage, etc.
"analog signals"
    (of a clock or watch) showing the time by means of hands rather than displayed digits.
    not involving or relating to the use of computer technology, as a contrast to a digital counterpart.
    "old-school analog paper map skills"

```

noun noun: analogue; plural noun: analogues; noun: analog; plural noun: analogs

```
a person or thing seen as comparable to another.
"an interior analogue of the exterior world"
    Chemistry
    a compound with a molecular structure closely similar to that of another.
    "thioacids are sulfur analogues of oxyacids"

```

When we look at the meaning of analog, then when we apply it to computing, it just means using something analogous to the real world. Or a model. And as many have said, the model may have flaws, or not account for certain unknown aspects of reality.

That being said, I recall reading in a magazine called Analog Computing in the 80's, that a true analog computer would be able to make use of the entire EM spectrum as inputs and outputs. I don't think we are there yet by that definition, but that may be a pipe dream.

---
Tags: quantum-computing
---


# Question
Title: Find orthogonal (integer) vectors in set
I have very large sets $A,B$ of 4-tuples of integers, and I would like to find $(x\_1,y\_1,z\_1,w\_1)\in A,(x\_2,y\_2,z\_2,w\_2)\in B$ such that $$x\_1x\_2 + y\_1y\_2 + z\_1z\_2 + w\_1w\_2 = 0.$$

Of course the naive $|A||B|$-time algorithm is too slow for me. Is there a better algorithm?

In 2D you can normalize all the vectors then for any $a\in A$, there are only two possible unit vectors orthogonal to $a$ so it can be done in something like $|A|\log|B|$ time.

But in 4D, for any vector $a\in A$, there is a whole 3D subspace of vectors orthogonal to $a$, and I don't see an easy way of quickly (i.e. faster than linear time) determining which vectors in $B$ lie in that subspace.

# Answer
> 2 votes
Thank you to @InuyashaYagami for pointing out that paper in the comment above. It cites "Cutting Hyperplanes for Divide-and-Conquer" (Chazelle, 1993) which gives an $O(n^{2d/(d+1)}(\log n)^{1/(d+1)})$ algorithm for determining intersections between $n$ hyperplanes and $n$ points in $d$-space (note: this is equivalent to determining whether there are vectors $a\in A,b\in B$ for $A,B\subset \mathbb R^{d+1}$ such that $a\_1b\_1+\cdots+a\_{d+1}b\_{d+1} = 0$, since we can rearrange to get $a\_1(b\_1/b\_{d+1}) +\cdots + a\_d(b\_d/b\_{d+1}) = -a\_{d+1}$). In my case ($d = 3$) this is $O(n^{3/2}(\log n)^{1/4})$ which is quite close to the lower bound of $\Omega(n^{4/3})$ established in "New Lower Bounds for Hopcroft's Problem" (Erickson, 1995).

Unfortunately the algorithm given by Chazelle seems quite complicated to say the least. Here is a simpler, $O(n^{5/3})$ (average-case) algorithm I came up with for the integer version of this problem, which might perhaps be faster in practice (I will have to try implementing Chazelle's algorithm to be sure...):

First, find a prime $p$ close to $\sqrt\[3\]{cn}$ for some choice of constant $c$ which can be adjusted to improve performance.

Now we know that for any solution $x\in A,y\in B$, we will have $$x\_1y\_1 + x\_2 y\_2 + x\_3y\_3 + x\_4 y\_4 \equiv 0~~~\text{(mod $p$})$$ So then $$y\_1 + Py\_2 + Qy\_3 + Ry\_4 \equiv 0~~~\text{(\*)}$$ where $P=x\_2x\_1^{-1}$, $Q=x\_3x\_1^{-1}$, $R=x\_4x\_1^{-1}$ (the case of $x\_1\equiv 0$ will have to be handled separately).

So split $A$ into $p^3$ "buckets" depending on $(P,Q,R)$.

Now for each $(y\_1,y\_2,y\_3,y\_4)\in B$, figure out which $P,Q,R$ satisfy (\*) and just check those buckets, instead of all of $A$ (the values of $P,Q,R$ can be found, at least for most $y$'s, by going through each $P,Q$ and solving for $R$ — in total $p^2$ buckets will need to be searched).

I would be interested to know whether there are reasonably simple algorithms (including perhaps randomized algorithms) which can do better than this.

---
Tags: algorithms, number-theory, linear-algebra
---


# Question
Title: What algorithm accepts a set of strings as input and outputs a regex of minimal size?
We seek an algorithm.

Inputs to the algorithm are a set of strings $A$ and the output of the algorithm $A$ is a regular expression $r$ such that:

> 1. The ***size*** of regular expression $r$ is minimized.
> 2. If $A^{\prime}$ is set of strings described by regular expression $r$, then $A \subseteq A^{\prime}$. In other words, the set of strings described by $r$ is a super-set of set $A$.

---

# Example of Input and Output for the Algorithm

The following list of email addresses would represent the input to our algorithm:

> * `Leelloo@joesbasement.net`
> * `Gadisse@joesbasement.net`
> * `Saaran@joesbasement.net`
> * `Jaallee@joesbasement.net`
> * `Feenet@joesbasement.net`
> * `john.doe@stackexchange.com@joesbasement.net`
> * `Jairo-Botín@fedcoseeds.com`
> * `IsidoroAguay@notepad-plus-plus.org`
> * `Dabalee@joesbasement.net`
> * `Garaatoo@joesbasement.net`
> * `EduardoParí@notepad-plus-plus.org`
> * `AnthonyArna@notepad-plus-plus.org`
> * `EmilioIllesca@notepad-plus-plus.org`
> * `IkerGarcí@notepad-plus-plus.org`
> * `Bilisee@joesbasement.net`
> * `SebastiánMin@notepad-plus-plus.org`
> * `PabloCazall@notepad-plus-plus.org`
> * `Qananii@joesbasement.net`
> * `maria-castellon@stackoverflow.com`
> * `Bikel-tu@joesbasement.net`
> * `DanielSantánge@notepad-plus-plus.org`

The output from the algorithm might be something similar to the following regular expression, but (and only if you want to) feel free to edit this question to correct the following regex:

```
[A-Za-z\-]+@[A-Za-z\-]+\.((com)|(org)|(net))

```

---

# How to quantify the size of the regex `a|b`

For regex $\mathtt{a|b}$ the associated tree has $3$ nodes.

Our algorithm accepts a set of strings as input and outputs a regex for which the corresponding tree has as few nodes as possible.

---

# How to quantify the size of the regex `[A-Z]`

For the character class $\mathtt{\[A-Z\]}$ the size of the associated tree is $27$.

Our algorithm accepts a set of strings as input and outputs a regex for which the corresponding tree has as few nodes as possible.

---

In general, for a regular expression character class containing $n$ characters, the number of nodes in the tree associated with the character class is $n + 1$.

> * There are $n$ children of the root node
> * The root node represents logical-disjuction and/or the union of sets. In regular expressions logical-disjuction is usually written as `|` or `or`.

---

Given that there are many different flavors of regex, please assume that we the flavor of regular expressions used in the Java SE 19 standard.

---

Generating a regex from a large set of examples is an important problem because writing regular expressions for practical applications by hand is difficult.

The following is a popular standard for email addresses. Most people would have more difficulty writing the following regex by hand than they would amassing large lists of valid email addresses.

```
\A(?:[a-z0-9!#$%&'*+/=?^_‘{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_‘{|}~-]+)*
 |  "(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]
      |  \\[\x01-\x09\x0b\x0c\x0e-\x7f])*")
@ (?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?
  |  \[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}
       (?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:
          (?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]
          |  \\[\x01-\x09\x0b\x0c\x0e-\x7f])+)
     \])\z

```

# Answer
The minimal regular expression is `[abcd...]*`, where `abcd...` is the list of characters that appear in the input. This always accepts a superset of the specified strings.
> 1 votes

---
Tags: optimization, trees, regular-expressions
---


# Question
Title: Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\\&} B)$ where $\\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is bitwise XOR. (It is reasonable to assume that the bit representation of integers is two's complements.)

The statement above appears as item 23 of *HAKMEM* but it is given without proof. Its significance lies in the fact that it connects arithmetic operators on integers with bitwise operators.

Following definitions in The Art of Computer Programming, Volume 4A, Part 1, define bitwise operations on nonnegative integers as follow:

Let $A = (...A\_3A\_2A\_1)$, $B = (...B\_3B\_2B\_1)$, and $C = (...C\_3C\_2C\_1)$. We have

$$ \begin{gather} A \operatorname{\\&} B = C \iff A\_k \wedge B\_k = C\_k; \text{ for all } k \geq 0\\ A \mid B = C \iff A\_k \vee B\_k = C\_k; \text{ for all } k \geq 0\\ A \oplus B = C \iff A\_k \oplus B\_k = C\_k; \text{ for all } k \geq 0 \end{gather} $$

Our goal then is using the definitions above together with the definition of addition on bit strings to prove item 23 of HAKMEM; if possible.

**Note:** as stated earlier, there are other relations between bitwise operators and arithmetic operators from which the statement above can be deduced (and vice-versa), see subsection $2{-}2$ of Hacker's delight for such relations. That's not what we want. We want to prove the statement from "first principles", not from equivalent relations; if possible.

*I'm unable to construct a proof, as in the starting point is not obvious (to me). And everywhere I have looked online it is stated without proof.*

# Answer
> 6 votes
#### Bitlength and bound needed for two's complement

> Prove that for $A, B \in \mathbb{Z}$, $A + B$ $= (A\operatorname{\\&}B) + (A \mid B)$ $= (A \oplus B) + 2(A\operatorname{\\&}B)$ where $\operatorname{\\&}$ is bitwise AND, $\mid$ is bitwise OR and $\oplus$ is bitwise XOR. (It is reasonable to assume that the bit representation of integers is two's complement.)

You have interpreted item 23 so that it is almost correct.

If we allow $A$ or $B$ to be negative, however, it is hard/impossible to assign/determine the sign of $A\operatorname{\\&}B$, $A\mid B$ or $A\oplus B$ if we use the natural/standard representation of a number in base $2$. A different method that can represent signed integers without using the sign $\pm$ has to come into play. You selected two's complement. Then means you should also specify the length of a binary representation as well as restrict the magnitude of $A$ and $B$ to avoid overflow. That kind of specification and restriction is unlikely to be the intention of Rich Schroeppel, the author of this standalone item.

---

On the other hand, the equalities hold for all integers if integers are represented by two's complement with infinite length, as mentioned by hobbs and the Wikipedia article Two's complement and 2-adic numbers.

#### Let $A$ and $B$ be nonnegative integers

Here is a simpler way to interpret item 23. The only change is $A$ and $B$ are natural numbers (including $0$) instead.

> For all $A, B \in \Bbb N$, $\ A + B$ $= (A\operatorname{\\&}B) + (A\mid B)$ $= (A \oplus B) + 2(A\operatorname{\\&}B)$ where $\operatorname{\\&}$ is bitwise AND, $\mid $ is bitwise OR and $\oplus$ is bitwise XOR.

---

Let us prove the proposition above.

Suppose the usual binary representation $A$ and $B$ are $\cdots A\_2A\_1A\_0$ and $\cdots B\_2B\_1B\_0$ respectively, where all $A\_k$'s and $B\_k$'s are either $0$ or $1$. By the definition of bitwise operations as given in the question (or everywhere else), $$\begin{aligned} &\qquad(A\operatorname{\\&}B) + (A \mid B)\\ &= \left(\cdots + (A\_2 \\& B\_2)2^2+(A\_1 \\& B\_1)2^1+(A\_0 \\& B\_0)\right)\\ &\quad + \left(\cdots + (A\_2 | B\_2)2^2+ (A\_1 | B\_1)2^1+(A\_0 | B\_0)\right)\\ &= \cdots \\ &\quad+ ((A\_2 \\& B\_2)+(A\_2 | B\_2))2^2\\ &\quad+ ((A\_1 \\& B\_1)+(A\_1 | B\_1))2^1 \\ &\quad+ ((A\_0 \\& B\_0)+(A\_0 | B\_0))\\ \end{aligned}$$

We have a similar identity for $(A\oplus B) + 2(A\operatorname{\\&}B)$.

Note that $A+B$ also means doing addition place-wise as shown in the following identity.

$$\begin{aligned} A+B&=\cdots\\ &+(A\_2 + B\_2)2^2\\ &+(A\_1 + B\_1)2^1\\ &+(A\_0 + B\_0)\\ \end{aligned}$$

So it is enough to prove the following identities. $$\begin{aligned} &\ \ \vdots\\ A\_2+B\_2 &=(A\_2 \\& B\_2)+(A\_2 | B\_2)\\ A\_1+B\_1 &=(A\_1 \\& B\_1)+(A\_1 | B\_1)\\ A\_0+B\_0 &=(A\_0 \\& B\_0)+(A\_0 | B\_0)\\ \end{aligned}$$

That is, it is enough to show the proposition is true when both $A$ and $B$ are either $0$ or $1$.

There are $4$ cases.

* $A=B=1$. Then
$A+B=2$
$(A\operatorname{\\&}B) + (A\mid B) = 1+1=2$
$(A \oplus B) + 2(A\operatorname{\\&}B)=0+2\cdot1=2$
* I am sure you will be able to verify the other three cases.

#### Another interpretation, $A$ and $B$ are integers in programming languages

Consider Java. If `A` and `B` are of type `int` or `long`, then `(A & B) + (A | B)` and `(A ^ B) + 2 * (A ^ B)` are all equal. It does not matter whether `A` and/or `B` is negative and whether there is overflow. For example, if `int A = (1 << 30) + (1 << 29); int B = A - 1;`, then `A + B`, `(A & B) + (A | B)` and `(A ^ B) + 2 * (A ^ B)` are all equal to `-1342177280`.

Consider Python. If $A$ and $B$ are of type `<class 'int'>` in Python, then those three expressions are also equal. It does not matter whether `A` and/or `B` is negative.

I would believe the same happens for most programming languages.

It is easy to expect/understand the expressions are equal when none of `A` and `B` are negative and there is no overflow. To understand why they remain equal without exception otherwise, it may require some digging into the specification/implementation of Java/Python. Or, where is an existing proof?

# Answer
> 5 votes
This answer isn't rigorous or starting from first principles, but I thought this was elegant so here it is anyway.

Given that addition is commutative and associative and bit-shifting all summands left also bit-shifts the result by the same amount, and that $(...A\_3A\_2A\_1) = ... + A\_300 + A\_20 + A\_1$, we have that $(...C\_3C\_2C\_1) = ...+(A\_3+B\_3)00+(A\_2+B\_2)0+(A\_1+B\_1)$. To prove that $X+Y=A+B$ we only have to prove that for all $n$, $X\_n+Y\_n=A\_n+B\_n$.

We can brute-force that by drawing a truth table and we are done, but it's more interesting to observe that $A\_n+B\_n$ counts the number of 1 bits among $A\_n$ and $B\_n$ \- that is 0, 1 or 2 (10). This is invariant to permutations of the summand bits.

*Therefore, any bitwise transformation that preserves the number of 1 bits in each position $n$ will also preserve the sum $C$.*

Example:

```
    10101010
  + 00110011 = 11011101
    ^^^^^^^^
    10211021 <- number of bits in each column above and below
    vvvvvvvv
    00110010
  + 10101011 = 11011101
    ^  ^^ ^
    bits swapped in columns, same answer

```

This also works for addition of 3 or more numbers.

The transformation $(A\_n, B\_n) \Longrightarrow (A\_n\land B\_n, A\_n\lor B\_n)$ preserves the total number of 1s, but shifts them preferentially towards the right half (10 becomes 01, everything else is unchanged).

The transformation $A\_n\lor B\_n \Longrightarrow (A\_n\land B\_n,A\_n\oplus B\_n)$ also preserves the total number of 1s, since both halves can't be 1 at the same time.

# Answer
> 1 votes
Consider the addition of two random binary numbers like these: $$ \begin{matrix} &00101011& (A)\\ \+ &01100101& (B)\\\hline = &10010000& (A+B) \end{matrix} $$

Ignore the signed vs unsigned problem for now.

Now, $1$s are heavier than $0$s, so if a $1$ in $A$ is on top of a $0$ in $B$, they swap places:

$$ \begin{matrix} &00100001& (C)\\ \+ &01101111& (D)\\\hline = &10010000& (C+D) \end{matrix} $$

You should agree that swapping digits like this doesn't affect the final sum, so $A+B=C+D$. But what are $C$ and $D$?

The only way there can be a $1$ in $C$ is if there are $1$s in that position in both $A$ **and** $B$. In other words $C=(A \\& B)$.

In $D$, on the other hand, there can be a $1$ if there a $1$ already in $B$ **or** if one is swapped in from $A$ above. In other words $D=(A|B)$

Adding it all up, $$A+B = (A\\&B) + (A|B)$$

First half is done. The second half is harder to picture, but I will try.

Returning to our original addition above, start by adding the digits without carry: $$ \begin{matrix} &00101011& (A)\\ +? &01100101& (B)\\\hline = &01201112& A+B ? \end{matrix} $$

What we have here is an non-normalized number, where digits can have values that are larger than the base. Think of it as having one dollar bill and 231 one-cent coins. Perfectly valid, but you will feel more comfortable if you can get more bills and fewer coins. The point here is that the sum *is* $A+B$, only written in an unusual way.

So, lets make change. For every 2, we write 0 and 1 in carry.

$$ \begin{matrix} &\centerdot 01201112&(nonnormal) A+B\\\hline &00100001\centerdot& carries\\ \+ &\centerdot 01100101& values\\\hline = &010010000& (normalized) A+B \end{matrix} $$ (Please pretend that aligns properly)

The $carries$ line contain a $1$ if there was a $2$ in the non-normalized number in the column to the right, which means there must have been $1$s in both $A$ **and** $B$. The shift to the left is the same as multiplying by two.

The $values$ line contain a $1$ if the non-normalized number has a $1$ in that column, which means that either $A$ **or** $B$ has a $1$ there, **but not both**.

Adding it all up gives us $$A+B = 2(A\\&B) + (A\oplus B)$$

Shuffle the terms and put it together with the first half and you have the statement you wanted to prove.

# Answer
> 1 votes
It is an easy matter to check these identity that are true for single bits (the case $1+0$ follows by commutativity).

$$0+0=0\land0+0\lor0=0\oplus0+2\\,(0\land0)\\ 0+1=0\land1+0\lor1=0\oplus1+2\\,(0\land1)\\ 1+1=1\land1+1\lor1=1\oplus1+2\\,(1\land1)$$

And these results immediately generalize to bitwise operations by linearity, as the value of a binary number is a linear combination of its bits (with coefficients equal to powers of $2$).

# Answer
> -2 votes
Prove it for the cases that A and B are both true, that exactly one of them is true, and that none of them is true.

---
Tags: arithmetic, boolean-algebra, integers
---