# Question
Title: pumping lemma length restrictions clarification
I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it again. I will put some answers that I have read and their difference in this question.

So my question: For a language $L$ and a string $w\in L$, the pumping lemma is defined as follows: If $|w| \geq m$, then $w$ can be written as $xyz$, satisfying the following conditions:

1. $|y|\geq 1$
2. $|xy|\leq m$
3. $ \forall i\geq 0: xy^iz\in L$

For the second condition, I think that all the answers give the same intuition, namely: The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence (so y also causes the second occurence of a state). By considering the first loop, we can guarantee that $|xy| \leq m$. Since, in the “worst case”, after reading $m$ characters, we have seen $m+1$ states. So if I have a DFA M with 100 states, the loop can be in the first 3 states, but I can guarantee that if a word with length 100 or more is in L(M) then it will cause a loop since 101 or more states will be seen. If I’m not mistaken, this part is completely correct?

For the first condition, I have read multiple answers:

1. It is clearly necessary if you want to say something interesting, since otherwise you would pump an empty string.
2. Because you have a DFA, every transition must contain a symbol, and you can’t have any lambda-transitions, that’s why.

Could someone clearify which one here is the correct explanation?

# Answer
> 4 votes
First, for the sake of preciseness, note that the Lemma says that for every regular language $L$, there exists a constant $m\ge 1$, such that for every word $w\in L$... \[what you wrote\]. That is, the statement of the lemma is not *"after"* you have a language and a word.

As for your questions, basically everything you wrote is correct. To be slightly more specific:

The second condition indeed follows from the fact that we can bound the length of the run before a loop occurs. This follows from the pigeonhole principle. Interestingly, by the way, this condition can be changed to require that we can find a loop from whichever index we start from (as long as there are enough letters remaining). But this is beside the point.

For the first condition: indeed, if we had started with an NFA with $\lambda$ transitions (a.k.a. $\epsilon$ transitions in some textbooks), then we could not immediately assume $|y|\ge 1$ using the same proof. However, we could modify the proof by only looking at states visited after actual letters are read from the word, in an accepting run.

When you ask "which one is correct?" -- we need to start with a DFA (or a $\lambda$-free NFA) in order to obtain that $|y|\ge 1$, and we want $|y|\ge 1$ otherwise the lemma is useless. So both, kind of.

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


# Question
Title: How to compute relative error for the rounding of floating point numbers when the rounded number is 0?
I have asked this question on Stack Overflow, I am asking it here in the hope to get more traction.

The relative rounding error for a floating point number x is defined as

$e\_r = |\frac{(round(x) - x)}{x}| = |\frac{round(x)}{x} - 1|$ (1)

Assuming that the rounding to nearest mode is used for $round(x)$, the absolute rounding error $|round(x) - x|$ is going to be less than `0.5 ulp(E(x))`, where the `ulp` are units in the last place

$ulp(E) = 2^E \cdot \epsilon$

and $E(x)$ is the exponent used for $x$, and $\epsilon$ is the machine epsilon $\epsilon=2^{-(p-1)}$, $p$ is precision (24 for the single precision and 53 for the double precision IEEE formats).

Using this, the relative error can be expressed for any real number $x$

$e\_r = |\frac{(round(x) - x)}{x}| = \frac{|(round(x) - x)|}{|x|} \< |0.5 \cdot 2^E \cdot 2^{-(p-1)}| / |2^E| \< 0.5 \epsilon$

For denormalized numbers $0 \< x \< 2^Em \epsilon$, where `Em` is the minimal exponent (-126 for single precision, -1022 for double):

$0 \< x \le 0.5 \cdot \epsilon \cdot 2^{Em}$

the rounding always goes to $0$!

If the `round(x)` is 0, then by (1)

$e\_r =|\frac{(0 - 1)}{1}| = |1|$ !

How is the relative error computed for such numbers? Should the relative error be even used for the numbers that are rounded to `0`?

# Answer
> 0 votes
If x = 0 and is rounded to 0 then the error is 0, and the relative error is whatever you want it to be.

If x ≠ 0 and is rounded to 0, then the absolute error is x, and the relative error is 1 (or 100% if that is more intuitive).

If x = 0 and is round to y ≠ 0 then the absolute error is y, and the relative error is infinite or undefined, whatever you prefer.

# Answer
> 0 votes
Why answer would be preferable to 1?

Let's try abstracting a little: Say you have any small value $c$ for which 0 is the closest value that can be reliably represented. If rounding occurs, how much error occurs as a fraction of $c$? All of it. 100% of $c$. So the rounding error is 100% = 1.0.

# Answer
> 0 votes
You can't get a relative error on a zero quantity. Only absolute error. Full stop.

---
Tags: floating-point
---


# Question
Title: Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?
Lets say the alphabet is **Σ=∅**,what are the possible languages of this alphabet?

According to my definitions:

* I know that an alphabet is a finite set of symbols **Σ**
* I know words is a set of all finite symbols consisting of letters from the alphabet (**Σ**\*) and an empty string part of all words **ε ∈ Σ***
* I know that a language is a subset of words and an empty set is a subset of the words **∅ ⊆ Σ***

All this is very confusing to me, and I am very unsure about what languages there are when we have an empty set for the alphabet.

# Answer
Actually your list of properties already solves the problem. As $\varepsilon$ is an element of $\Sigma^\*$ and we cannot have any longer word due to the lack of symbols, we have $\varnothing^\*=\\{\varepsilon\\}$.

A language is a subset of $\varnothing^\*$, and as $\varnothing^\*$ has only one element, there are two possible languages.
> 2 votes

---
Tags: formal-languages, automata, sets
---


# Question
Title: Difference between Sequential ,Direct and Random acess with their acess time
I'm stuck on a point while reading about these different accessing methods. As per author.

**Sequential access**

> Memory is organized into units of data, called records.Access must be made in a specific linear sequence.

I understand that it will take variable time to access due to sequential ordering.

**Direct Access**

> individual blocks or records have a unique address based on physical location.Access is accomplished by direct access to reach a general vicinity plus sequential searching,counting,or waiting to reach the final location. Again, access time is variable.

Here I'm Stuck that if we have unique address why it is taking variable time and why we can't directly access data.

**Random Access**

> Each addressable location in memory has a unique,physically wired-in addressing mechanism. The time to access a given location is independent of the sequence of prior accesses and is constant.

What is the difference between this and direct access method.

# Answer
Yeah, me i say, with DIRECT access, only addresses are known and kept, so as you try to read or write, the data contained in those memory addresses the computer is iterating through is never looked at/opened but only the data kept in the address you are trying to read or write to is the one opened.

This differs from RANDOM, as random has a mechanism of storing each memory address independent of the other, therefore, accessing it does not require iterating through the rest of the memory addresses thus the name, random access, e.g. our RAM uses this.

For the SEQUENTIAL, this follows a certain linear format and therefore for you to access data maybe on address 2020, you have to first read the data from 1-2019 before getting to the required data, hence the term sequence(step by step). a good example are the Tapes..
> 0 votes

# Answer
The text says it: direct access works by sequential search from a neighboring location (such as the start of a block known to contain the desired data). Though the search should not be long, the number of searched positions is variable.

As far as I know, this peculiar definition is rarely met, and usually direct and random access are synonymous.

Also, do not confuse with *direct memory access* which is a mechanism by which hardware devices can access the RAM memory without intervention of the CPU.
> 0 votes

# Answer
Although both direct and random access terms can be used interchangeably, based on the definitions mentioned it might give rise to slightly different meanings. This could be one of the possible interpretations of the definitions.

**Direct Access**

> individual blocks or records have a unique address based on physical location.

Here the block size may be dependent on the application/scenario. For example: Different filesystems, RDBMS, etc have different block sizes. So you have a direct access to the base address of the block and then you search sequentially till the desired data is found. As an example, this is how paging works to locate the instruction in main memory. It is evident that you can access only those locations directly which are at the block size boundaries, and after that you will on average have to perform $blockSize/2$ queries to get the required data.

**Random access**

> Each addressable location in memory has a unique, physically wired-in addressing mechanism.

Essentially here it says you can access **any** memory address, so this definition deals with a lower level of abstraction than the definition above. Hypothetically, with these definitions, Random and Direct access would be the same if the block size would be the same as word size for a given system. A possible but bad example, on a 64-bit machine, accessing an array of `int64_t` in C.
> 0 votes

# Answer
Sometimes, depending on the sources,*direct access* and *random access* are used to express the same memory access mode and therefore do not present any substantial difference in the speed of data access.

More in detail, the differences between the two modes can be sought in their implementation: Random Access can be realized directly via RAM memory wiring, while direct access can use secondary storage; in this case is obvious that *random access* is faster than *direct access*.
> -1 votes

---
Tags: data-structures, memory-access, storage
---


# Question
Title: Is every $p$th word in a regular language regular?
### Question

Let $L$ be a regular language. Let's say we sort $L$ by length and then lexicographically; then let $L\_p \subset L$ be every $p$th word in $L$ according to this sort. Is $L\_p$ regular as well?

### Example

For example, let's use $L = a^\*b^\* = \\{\epsilon, a, b, aa, ab, bb, aaa, aab, abb, ...\\}$. Then $L\_2 = \\{\epsilon, b, ab, aaa, abb, aaaa, aabb, bbbb, ...\\}$, which is a regular language: $$L\_2 = (aaaa)^\*((\epsilon + b) + a(b + bb)+aa(bb+bbb)+aaa(bbb+\epsilon))(bbbb)^\*$$

Put another way, $L\_2 = \\{a^mb^n \mid n = m \lor n = m+1 \mod 4\\}$.

# Answer
> 7 votes
The answer is yes: Theorem 4 in "Numeration systems on a regular language" (Leconte and Rigo) shows that any arithmetic progression in a regular language is regular.

---
Tags: regular-languages
---


# Question
Title: Why the APPROX-VERTEX-COVER algorithm is O(V+E)?
In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio:

Where ***G*** is undirected graph. The complexity of this algorithm is ***O(V+E)***. I do not know why. It should be ***O(E)*** since the while loop in line 3 clearly will loop ***|E|*** times (***E*** is the set of edges in ***G***). The cost of line 6 is at most 1?

# Answer
You can use a boolean array of length $|V|$ to check whether a vertex $u$ has already been seen or not. Assuming $V = \\{0, 1, …, n-1\\}$, the algorithm could be re-written as:

```
Input: graph G as an adjacency lists array

Initialize C as an empty set
for each edge e = {u, v} in E do
    if neither u nor v is marked then
       Add e to C
       mark u and v
return C

```

The complexity would indeed be $\mathcal{O}(|V| + |E|)$.
> 1 votes

# Answer
I think the only thing missing in your analysis is the cost of adding the two vertices to the set $C$,which at the very least be $O(1)$ per vertex, if $C$ is implemented as a simple list. With that you will get the $O(V+E) $ bound.
> 0 votes

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


# Question
Title: Dynamic program to solve operation over digits
i have faced this problem that i can not solve.

assume i have a number like n. I want to do m operation over each digit.

in each operation every digit is added by one for example if my number is 1239 my number after one operation is 23410 Or if my number is 9912, my number after operation is 101023

Is there any algorithm of O(n+m) that can tell me the number after m operation?

it seems there is a solution with dynamic programming. However i doubt if such solution exists

# Answer
Well how about you do your operation on all digits first and create a mapping for them.

For example, let's say your operation is "add 2 and multiply by 3" (I guess m here is 2)

You will have :

```
0 -> 6
1 -> 9
2 -> 12
3 -> 15
...
9 -> 33

```

This should be `10 * m` operations, so it is O(m). Then you can go through your digits and get their corresponding mapping, which is another `n` operations.

In addition, if you don't want to do extra work for the digits that don't appear in your code, you can do the operations on demand.

```
loop for each digit in the number:
  if the mapping for the digit doesn't exist:
    create the mapping and use it
  else:
    use the existing mapping

```
> 0 votes

# Answer
After $m$ operations, a single digit becomes a string of about $2^{\log\_{10}\frac m{10}}$ digits, as the number of digits doubles about every ten operations. So just writing the result takes time $\Omega(n\\,m^{0.301\cdots})$ and $O(n+m)$ is not possible.

A possible method is to precompute the expansions of the ten digits after $m$ operations, and concatenate those corresponding to the digits of $n$. The precomputation can be done recursively.
> 0 votes

# Answer
Starting with a digit k, 10-k steps lead to 10. 9 further steps change the 1 to 10 and 10 steps change the 0 to 10. So on average 9.5 steps double the number of digits. 95 steps more than multiply the number of digits by 1000, 95k steps multiply the number of digits by 1000^k. So the number of digits grows exponentially. If I gave you the answer written down, it would take you exponential time just to copy it.
> 0 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$
i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \\{0,1\\}^\*$

exists $L\_1,L\_2\subseteq\\{0,1\\}^\*$ with:

* $L\_1$ is $REG$
* $L\_2$ is $CFL$ and not $REG$
* $L\_1 \subseteq L\_2 $
* $L \subseteq L\_2 $ and $L \neq L\_2$

I struggle at showing it for all $L$.

What I did so far is some kind of a little sketch.

Let $L\_1 = L(01)$ and $L\_2 = \\{0^n1^n | n \geq 0\\}$ then $L\_1$ is obviously $REG$ and $L\_2$ is obviously $CFL$ and not $REG$

Also $L\_1 \subseteq L\_2$ and $L \subseteq L\_2$ and $L\_2 \neq L$

But how do I proceed from here? How do I show it for every $L$?

# Answer
> 1 votes
Your approach is not going to work. If $L=\\{00\\}$ (say) then you will not have $L \subseteq L\_2$.

Hint for a better approach: Could $L$ be $\\{0,1\\}^\*$? Why or why not?

# Answer
> 1 votes
Since $L$ is not regular it is different than $\Sigma^\*$. What would happen if you choose a word $u\notin L$ and consider $L\cup \\{u\\}$?

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


# Question
Title: how to find the depth of a concurrency bug
How to find the depth of a concurrency bug

The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug in it.

Bug: Any time both threads perform a read before they write we loose an update to x.

**Thread 1**

```
 1. t1=x
 2. t1=t1+1
 3. x=t1

```

**Thread 2**

```
 1. t2=x
 2. t2=t2+1
 3. x=t2

```

I am told the depth of the bug is 2. My question is what is the process to find the depth of a concurrency bug?

# Answer
> 1 votes
The depth is the order of constraints (requirements in the order of execution before a bug is found) that a scheduler has to follow to find a bug. The issue that you are trying to solve here is a lost update that happens when you modify the X in both threads. Let suppose the following sequence. Thread 1 executes from line 1 and 2 then it jumps to thread 2 and executes it completely (first jump) then it jumps back to thread 2 (Second Jump) and it overwrite the value of X. It was necessary 2 jumps to trigger the problem, so the depth is 2.

# Answer
> 1 votes
Each time a thread read the shared variable, increments the local variable, and writes back. Note that writing can occur by a thread only after the reading operation. So in the case of 2 threads, x can be incremented only once before writing back by a thread.

---
Tags: algorithm-analysis, concurrency, software-verification
---


# Question
Title: Finding a map between two matrices that minimises distance differences of neighbors
Given two binary matrices of the same size with the same element counts, how can we find a map mapping ones to ones such that the sum of differences of distances of all pairs of neighbors is minimised, where the distance of each cell is the number of steps it needs to walk horizontally, vertically or diagonally to reach where the mapping sent it?

For example, given $A= \begin{bmatrix} 1& 1 & 1\\ 1& 0& 0\\ 0& 0& 0 \end{bmatrix} B= \begin{bmatrix} 0& 0 & 0\\ 0& 0& 1\\ 1& 1& 1 \end{bmatrix} $

The function $\psi$ mapping the ones of $A$ to the ones of $B$ by $\psi(1,1) = (3,1), \psi(1,2) = (3,2),\psi(1,3) = (3,3), \psi(2,1) = (2,3)$ gives all the ones of $A$ the same distance of 2, which gives the sum of all differences of distances of neighbors the minimal value possible of zero.

How can we generally approach this problem efficiently?

The motivation is creating smooth animation between simple binary black and white images of shapes such as circle and square. Combining this approach with also minimising the total distance covered by the pixels will help finding the path each pixel makes along the frames to make the animation smooth. It is for practical usage having typical input size of about $500 \times 500$ with relatively small amount of black pixels (ones) of about 500.

# Answer
I expect that solving the problem exactly might be NP-hard. However, here is an approach that I expect will probably be good enough for practical purposes.

It uses a subroutine to solve the following problem: given an integer range $\[\ell,u\]$, find a mapping $\psi$ such that $\ell \le \text{dist}(p,\psi(p)) \le u$ for all one-pixels $p$, or report that no such mapping exists. You can implement such a subroutine using an algorithm for bipartite matching: build a bipartite graph with one left-vertex for each one-pixel in the left matrix, one right-vertex for each one-pixel in the right matrix, and an edge between two vertices if the distance between their corresponding pixels falls in $\[\ell,u\]$.

Given such a subroutine, you can search over all $O(n^2)$ possible ranges, and call the subroutine for each, and keep the "narrowest" range, i.e., one where $u-\ell$ is minimal. Generally, the smaller the value of $u-\ell$, the better it is likely to be by your metric. (Here I assume each matrix is $n\times n$.)

Or, more efficiently, you can search over all $2n$ possibilities for $\mu$, where $1 \le \mu \le n$ and $\mu$ is an integer or half an integer; then for each $\mu$, use binary search over $s$ to find the smallest $s$ such that there is a mapping for the interval $\[\mu-s,\mu+s\]$. Note that there are only $O(n)$ possibilities for $s$, so this requires only $O(n \log n)$ invocations of the subroutine.

Each invocation of the subroutine can be implemented in $O(n^3)$ time using the Hopcroft-Karp algorithm, for a total running time of $O(n^4 \log n)$.
> 1 votes

---
Tags: algorithms, matrices
---


# Question
Title: What is the time complexity of the following program
The right answer is Theta(n log logn). But, can someone explain why it is the case? I know intuitively that it is because k is k^2 each time, so it couldn't be (logn) for the second loop. However, what is the actual mathematical analysis that makes it (log logn)?

# Answer
> 1 votes
Hint: If $n=2^{16}$, how many times does the inner loop iterate? Try to work out the exact answer -- I'm sure you can figure it out. What about if $n=2^{32}$? $n=2^{64}$?

# Answer
> 0 votes
The number of iterations of the inner loop can be found by solving the recurrence

$$k\_{i+1}=k\_i^2,\\k\_0=2.$$

Taking the $\lg$, we have

$$\lg k\_{i+1}=\lg k\_i^2=2\lg k\_i,\\\lg k\_0=1,$$ which can be readily solved as a geometric progression ($\lg k\_i=2^i$).

Alternatively, taking the $\lg\lg$, the recurrence becomes

$$\lg\lg k\_{i+1}=\lg\lg k\_i^2=\lg(2\lg k\_i)=1+\lg\lg k\_i,\\\lg\lg k\_0=0$$ and the solution is obvisouly

$$\lg\lg k\_i=i.$$

Now set $k\_i=n$.

---
Tags: algorithms, algorithm-analysis
---


title: Quicksort with insertion sort

text:
# Question
Title: Quicksort with insertion sort
Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different algorithims for sorting (quick , merge and quicKInsert). My question is is there a scenario where quickInsert out performs quick sort and merge sort running time for QuickInsert would be O(nK)+O(n log n/݇K) I have to find out a combination of N(number of elements) and K value to outperform other two sorting algos What I have tried is using k = log N did not work I know insertion sort beats quick sort in small numbers but how do I find out combination based on that. Am I missing something here

# Answer
Asymptotic complexity evaluations are not appropriate to decide which implementation is the fastest, and the best you can do is to rely on empirical evaluation.

This said, there will be no absolute answer because the running time of an algorithm is not a deterministic function of the problem size. On the opposite, it is a complete statistical distribution, which is uneasy to catch.

What you can do is

* select running conditions which you think are typical in your use case(s). Usually this information is not available. You can rely on random arrays, which will give you an idea of the expected time. But better measure the standard deviation based on several runs with different data.
* working on the same arrays, try increasing values of k. Compare the times to the standard version, and conclude which is better when the averages are significantly different (say to two sigmas).

Now you can plot the relation between n and k that gives the best results.
> 1 votes

# Answer
The running time (and how it changes) of any algorithm implementation will vary across platforms (hardware, operating system, compiler etc) and the input data. So it looks hard to find a simple relation for the array size up to which insertion sort will perform better than quick sort (and that too for all inputs).

Perhaps what we can do is assume the platform factors would remain fixed and use some representative input arrays. Then test and measure time (avoiding other system noises) to find the threshold array size $K$ below which insertion sort becomes faster. Use this $K$ in the hybrid quick/insert sort to delegate to insertion sort.
> 1 votes

# Answer
Big-O is only relevant for large values. It won't help you at all trying to find the optimal K.

For Quicksort, you obviously would stop recursing for a subrange of 1 number which will be already sorted. You may very well handle subranges of length 2 differently as well like

```
if r ≤ l + 1
    if r > l and a [l] > a [r]
        exchange a[l], a[r]
    return

```

So now you just choose K = 3, 4, 5 etc., measure the time for the combination of quick sort with insertion sort, for a range of typical arrays, and decide depending on your measurements. It is entirely possible and actually likely that for different machines the optimal K is different. If the optimal K is not trivial in size you'd also try insertion sort with binary search to find the position where to insert.
> 0 votes

---
Tags: time-complexity, asymptotics, sorting, big-o-notation
---


# Question
Title: IEEE 754 addition wrong result floating point numbers
I want to add two IEEE 754 numbers. I followed the steps to add two 754 numbers. However the result it not correct. Number 1: S:0 E:01111111 M:11111111111111111111111

Number 2: S:0 E:01111111 M:00000000000000000000000

Here is my calculation:

The site http://weitz.de/ieee/ gives this result: S: 0 E: 10000000 M: 10000000000000000000000

in my calculation the mantissa is 01111... Why?

# Answer
You forgot the implicit leading 1 in the mantissa. The mantissa is not 23 bits, it's 24 bits with a 1 as the leading bit.
> 0 votes

# Answer
$$\begin{align}1&.01111111 \\\+1&.11111111111111111111111\\\=11&.01111110111111111111111\end{align}$$

You obtain the same result with the calculator.
> 0 votes

---
Tags: floating-point
---


# Question
Title: Efficient algorithm/data structure that maps tic-tac-toe boards to floats
I'm implementing a q-learning agent for tic-tac-toe that requires mapping from tic-tac-toe boards to float values. Since certain game states are equivalent and should have the same value, it would be more efficient to store all games that are mirrors or $90^{\circ}$ rotations of each other, only once. Is there an algorithm/data structure to efficiently store/lookup elements with $D\_4$ symmetric group?

# Answer
Assign every cell a ternary digit among cross/dot/empty and encode the games using nine-trits numbers (base-3 digits). Base-4 can also do.

Now every time you want to encode a game, generate all 8 symmetries and compute the 8 corresponding numerical codes. Finally, keep the encoding with the lowest value. That will ensure uniqueness.

E.g.

Is encoded as the smallest of x--oox--o, -ox-o-ox-, o--xoo--x, ... (trits from top to bottom, left to right).
> 1 votes

---
Tags: group-theory
---


# Question
Title: Finding whether a point lies on the boundary of an geometrical object or not?
Suppose I have the mesh of an geometrical object (Interval in 1d, Region in 2d, Volume in 3d). How can I find out whether a point lies on its boundary or not?

I am looking for algorithms with explanations. Any resource would **also** be appreciated.

# Answer
> 1 votes
## Interval

Interval defined as $\[l, r\]$, test point $v$. Compute $|l-v|$ and $|r-v|$ to find distance from boundary. If the smallest of those distances is less than your tolerance, it's on the boundary.

## Region

With region defined as a list of 2d points with say $x\_i, y\_i$, as the $x$ and $y$ coordinates of the $i^{th}$ point, and a test point $v\_x, v\_y$. Compute the 'point segment distance' with every segment and compare with your tolerance. That is, the euclidean distance from each endpoint (use Pythagoras: $\sqrt{(x\_i - v\_x)^2 + (y\_i - v\_y)^2}$, and the point line distance: $\frac{|(x\_{i+1}-x\_i)(y\_i - v\_y) - (x\_i - v\_x)(y\_{i+1}-y\_i)|}{\sqrt{(x\_{i+1} - x\_i)^2 + (y\_{i+1} - y\_i)^2}}$

## Volume

I imagine that your volume is defined as a list of 3-tuples of 3d points which correspond to 3d triangles. Compute the 'point triangle distance' with every triangle and compare with your tolerance. Details are at the link but the usual way is to project the point onto the plane defined by the triangle and use barycentric coordinates.

### Notes

* You may want to consider an 'acceleration structure' to avoid having to look at every segment of a region, or every triangle within the volume. Something like a kd-tree or an r-tree may be appropriate.
* For 2d and 3d cases you *must* use an appropriate tolerance as numerical precision can prevent points being exactly on your segment / triangle.
* Anything better than just checking each segment / each triangle will require doing some work up front - you will need to supply more information in your question if this is desired.
* Essentially any 3d library you use should have a method for this (CGAL, etc.)
* The more general case of 'is my point inside this volume' is trivial for interval, look up winding number for region, and look at ray tracing counting the number of intersections for a closed volume (not practically very easy in 3D!)

---
Tags: computational-geometry, image-processing, python, c++, polygons
---


# Question
Title: Best data structures to store overlapping intervals?
I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.

Sample Input-1: `[1-5, 2-3, 3-5, 3-5, 3-6]`

Sample Output-1: `[(1-2):1, (2-3):2, (3-5):4, (5-6):1]`

The above output informs that, for the interval (1-2), there is only one interval (among given inputs) that overlaps. for the interval (2-3), both inputs 1-5 and 2-3 overlap. and so on.

I did a search and found that an interval tree (with slight modifications) could be the best match to store and produce this output. I am here to hear the other's opinion on which could be the more suitable data structure for my use case.

`PS:`

I don't wish to `update/read/delete` the tree. Just insert the interval and flat that tree similar to the sample output.

Sample Input-2: `[1-2, 3-4, 5-6]`

Sample Output-2: `[(1-2):1, (3-4):1, (5-6):1]`

Sample Input-3: `[1-3, 3-4, 5-6]`

Sample Output-3: `[(1-3):1, (3-4):1, (5-6):1]`

Sample Input-4: `[1-4, 3-4, 5-6]`

Sample Output-4: `[(1-2):1, (3-4):2, (5-6):1]`

# Answer
> 1 votes
Copy all interval endpoints to a single array, together with a start/end flag and sort on increasing times.

Sample Input-1: `[1-5, 2-3, 3-5, 3-5, 3-6]`

Sorted list: `[1+, 2+, 3-, 3+, 3+, 3+, 5-, 5-, 5-, 6-]`

Now by traversing the sorted list, you directly know the numbers of overlapping intervals: `[<1:0,1:1,2:2,3:4,5:1,>=6:0]` (equal values have been merged).

# Answer
> 2 votes
You can compute the desired output in time $O(n \log n)$, where $n$ is the number of intervals, without any advanced data structure.

For the sake of simplicity suppose that there are no intervals of length $0$ and that the set of all endpoints of the intervals is $\\{1,2,\dots,k\\}$ with $k=O(n)$. This can be guaranteed w.l.o.g. by performing coordinate compression (sort the times, remove the duplicates, and replace each occurrence of a time $t$ with the rank $r\_t$ of $t$. This rank $r\_t$ also allows you to recover the original time once you are done) which ensures $k \le 2n$.

Sort the intervals twice, once by their starting time and once by the ending time (this requires time $O(n \log n)$). For each $i \in \\{1,\dots,k\\}$ let $B\_i$ (resp. $E\_i$) be the number of intervals that begin (resp. end) not later than point $i$. All $B\_i$ and $E\_i$ can be found in time $O(n)$ by a linear scan of the sorted intervals.

The output consists of one interval $(i, i+1)$ for each $i \in \\{1,\dots,k-1\\}$ . The number of input intervals that intersect $(i, i+1)$ is exactly the number of intervals that are "alive" at time $i$, i.e., that begin at some time $\le i$ and end at some time $\> i$. Those are exactly $B\_i - E\_i$.

If the times are integers and their absolute value is upper bounded by $n^k$, for some constant $k$, the sorting step can be performed using the Radix Sort algorithm. This lowers the overall running time to $O(n)$, which is optimal.

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


# Question
Title: Constructing a small set of numbers whose differences cover $\{1,\ldots,n\}$
Let $n\in\mathbb N$.

Given a set $S\subset\mathbb N$, let $\Delta(S) = \\{a-b\mid a,b\in S\\}$ denote its set of differences.

I'm interested in finding a small set $S\_n$ such that $\\{1,\ldots,n\\}\subseteq\Delta(S\_n)$.

For example, if $n=8$ we can use

$$S\_8 =\\{1,2,4,8,9\\}. $$

> **How can we construct a small $S\_n$ efficiently? (Efficiently should ideally be $O(|S\_n|)$ time, but any $o(n)$ time would be interesting.)**

> **How does the smallest $|S\_n|$ grow as a function of $n$?** (As a guess, I'd like to say $|S\_n|=O(\sqrt n)$ should be possible?)

# Answer
One example of such a set is $S\_n = \\{0,1,2,\dots,k\\} \cup \\{k,2k,3k,\dots,k^2\\}$ where $k=\lceil \sqrt{n} \rceil$. It follows that $|S\_n|=O(\sqrt{n})$, and $S\_n$ can be constructed in $O(\sqrt{n})$ time.

See also https://math.stackexchange.com/q/168079/14578.
> 4 votes

---
Tags: algorithms, algorithm-analysis, combinatorics, number-theory
---


# Question
Title: Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?
I recently saw this answer on a question in the Quantum Computing SE. The answer demonstrated how we can probabilistically find the answer to the Deutsch Jozsa problem on a PTM in $O(1)$ time, with an error of $\frac{1}{2^k}$, where k is the number of entries we check.

I will provide an algorithm and proof of why (to my understanding it shows this).

Assume that on a deterministic turing machine the runtime is $O(2^N)$.

on a PTM, in order for a problem to be in BPP, you must have an error $\epsilon \< \frac{1}{3}$ for a run of any size.

Deutsch Jozsa problem gives us a function, $f$, which maps inputs of size $N$ to a boolean output $0$ or $1$.

Algorithm:

1. Pick a random sample of $K$ input values, each of length $N$.
2. Run $f$ with inputs from $K$
3. Label outputs $o\_1$, $o\_2$, ..., $o\_3$
4. If there is at least one $o$ that is not equal to the rest, you have a balanced function.
5. Otherwise, you have a constant function

The time complexity of this depends only on the size of the constant $K$ which is contant, so our time complexity is $O(K) \rightarrow O(1)$.

The error in the above function is $\epsilon = 0$ if the output is balanced, and $\epsilon = \frac{1}{2^k}$, where $k$ is the length of $K$, for a constant function.

The error above can be seem by the below proof:

Label the first output as $o\_1$.

If we are given a constant function, we will always output the correct answer. This is because we will never observe an $o$ that does not equal the rest in a constant function.

If we were given a balanced function, the probability of sampling an input that maps to an output equal to $o\_1$ is $\frac{1}{2}$.

Because each call is independent, if we were given a balanced function, the probabilities multiply, and we get $\frac{1}{2^k}$, where $k$ is the number of calls.

If we output constant when given a balanced function, this is because we have not observed any differing value, which has a probability of $\frac{1}{2^k}$.

If $k \> 2$, the error is a maximum of $\frac{1}{4}$. So this should meet the requirements of BPP.

This also does not rely on an oracle, like in the quantum case, but a function. So the original argument of having to create the actual oracle does not work here, I think.

# Answer
One problem is already explained in the answer you link to, in the part starting with "The fallacy is ... It uses an oracle.". In the Deutsch Jozsa problem, $f$ is provided as an oracle, so you have not proved anything about $P$ vs $BPP$, as the latter does not involve any oracles.

A second (but closely related) problem: you have not provided any justification for why a PTM for the Deutsch Jozsa problem implies $P \ne BPP$. That step is omitted in your proof, and in fact, it doesn't follow. Indeed, if you refer to the formal definition of $BPP$, you will discover that the Deutsch Jozsa problem is not in $BPP$. $BPP$ is defined in terms of formal languages, but there is no formal language corresponding to the Deutsch Jozsa problem. In short-hand, theoretical computer scientists say that the Deutsch Jozsa problem is a promise problem, and promise problems are outside the scope of complexity classes like $P$ or $BPP$ (which are concerned with decision problems).

See also, e.g., NP-complete promise problems?.
> 2 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"
Issue: I am having a hard time figuring out how to use the worst case for Rolling Hash, especially if the occurrences are only "a and b" for the string. Not only that but it is a bit of a hassle to figure out the process if the pattern that we tried to find from the given string will only contain one character occurrence, such as "bbbb".

How Rolling Hash is used in our class with a given formula and its process of solution:

Formulas:

Full document: https://drive.google.com/file/d/1vJr2UoFP7w2DFsJF9A5TmvHsoY9Zs3Iy/view?usp=sharing

The exercise problem that I am answering:

```
Given the following string and pattern. Determine the transition of the string comparison and hash value
when rolling hash or Rabin Karp algorithm is applied.

String = aabbaabbabbabababbbbbbaaaa

The following patterns that we need to find are:
1. bbbb
2. baaaa
3. bbab

```

My attempt for pattern "bbbb" by using the "String = aabbaabbabbabababbbbbbaaaa":

Not picture form:

```
String = aabbaabbabbabababbbbbbaaaa
Pattern:
1. bbbb

H(bbbb) = h(2 +2 +2 +2)= 8
                = h(  2*103 +   2*102  +   2*101 + 2*100)
                = 2000 + 200 + 20 + 2 = 2222 mod 113
                  = 75
String = aabbaabbabbabababbbbbbaaaa
H(aabb  ) = h(1 + 1 + 2 + 2) = 6
                = h(1*103 +   1*102  +   2*101 + 2*100)
                = 1000 + 100 + 20 + 2 = 1122
String = aabbaabbabbabababbbbbbaaaa
H(abba) = H(aabb)6-1+1 = 6
               = 1122 – 1*102 *10+ 1*100
                      = 1122 – 100 *10 + 1
               = 1022 *10 + 1
               = 10221

```

I am now quite unsure with the -1 and +1 that I have annotated, in which these values involve the character present from the previous pattern but is now absent from the current pattern( - 1(where a is 1), and +1 where it is the character found from the current pattern but is absent to the previous pattern(still a).

I considered these a's because of their specific position being different, thus for me, they are considered somewhat missing/unique in comparing between two patterns.

Am I doing the process right or should I not consider these conditions? Especially since the string patterns both contain only the occurrences of a and b as we traverse in finding the exact pattern into the given string that we are using.

I decided to stop the process first since I might be doing it wrong, especially since it may take a while to find the exact pattern string.

Your response would indeed help me a lot! Thank you very much!!!

# Answer
> 1 votes
#### A clearer explanation

Let $\beta$ be a positive integer. ($b$ will be used as a character)

Let string $s=c\_1c\_2\cdots c\_m$. Then $$H(s) = c\_1\times \beta^{m-1} + c\_2\times \beta^{m-2} + c\_3\times \beta^{m-3} + \cdots + c\_m\times \beta^0$$ where we abuse $c\_i$ to also denote the number that encodes it. For example, $a=1$, $b=2$, etc.

$$\text{TEXT:}\quad\**********\\, \rlap{\\,\overbrace{\phantom{C\_{\text{prev}}\*********\\,}}^{\text{previous window}}} C\_{\text{prev}}\\,\underbrace{\**********C\_{\text{next}}\\!}\_{\text{next window}}\************* $$

$$H\_{\text{next}}=(H\_{\text{prev}}-C\_{\text{prev}}\times \beta^{m-1})\times \beta + C\_{\text{next}}$$ where $\*$ stands for a character. Each window consists of $m$ characters.

---

Let $m=4, \beta= 10$.
Pattern: $bbbb$

$$\begin{aligned} H(bbbb) &= 2\*10^3 + 2\*10^2 + 2\*10^1 + 2\*10^0\\ &= 2000 + 200 + 20 + 2\\ &= 2222 \end{aligned} $$ String = $aabbaabbabbabababbbbbbaaaa$
$$\begin{aligned} H(aabb) &= 1\*10^3 + 1\*10^2 + 2\*10^1 + 2\*10^0\\ &= 1000 + 100 + 20 + 2\\ &= 1122\\ H(abba) &= H(\not {\\! \color{red}a} abb\color{blue}a)\\ &=(H(\color{red}aabb) - \color{red}a \*10^3) * 10 +\color{blue}a\\ &= (1122 - \color{red}1\*1000) * 10 + \color{blue}1\\ &= 1221 \\ H(bbaa) &= H(\not {\\! \color{red}a} bba\color{blue}a)\\ &=(H(\color{red}abba) - \color{red}a \*10^3) * 10 +\color{blue}a\\ &= (1221 - \color{red}1\*1000) * 10 + \color{blue}1\\ &= 2211 \\ H(baab) &= H(\not {\\! \color{red}b} baa\color{blue}b)\\ &=(H(\color{red}bbba) - \color{red}b \*10^3) * 10 +\color{blue}b\\ &= (2211 - \color{red}2\*1000) * 10 + \color{blue}2\\ &= 2112 \end{aligned}$$

$\newcommand{\m}{\operatorname{\\%}}$

#### Shrink hash by $\m$

When $m$ is as big as 100 or even bigger, the hash can be too large to be operation friendly. We can shrink the hash by taking its remainder after dividing a fixed positive integer, i.e., modulo that fixed number.

Let us run all above again, with $\m d$ inserted, where $d$ is a positive integer.

$$H(c\_1c\_2\cdots c\_m) = (c\_1\times \beta^{m-1} + c\_2\times \beta^{m-2} + c\_3\times \beta^{m-3} + \cdots + c\_m\times \beta^0)\m d$$

$$H\_{\text{next}}=((H\_{\text{prev}}-C\_{\text{prev}}\times \beta^{m-1})\times \beta + C\_{\text{next}})\m d$$ where $\*$ stands for a character. Each window consists of $m$ characters.

---

Let $m=4, \beta= 10, d = 113$.
Pattern: $bbbb$

$$\begin{aligned} H(bbbb) &= (2\*10^3 + 2\*10^2 + 2\*10^1 + 2\*10^0)\m113\\ &= (2000 + 200 + 20 + 2)\m113\\ &= 2222 \m113 \\ &= 75 \end{aligned} $$ String = $aabbaabbabbabababbbbbbaaaa$
$$\begin{aligned} H(aabb) &= (1\*10^3 + 1\*10^2 + 2\*10^1 + 2\*10^0)\m113\\ &= (1000 + 100 + 20 + 2)\m113\\ &= 1122\m113\\ &= 105\\ H(abba) &= H(\not {\\! \color{red}a} abb\color{blue}a)\\ &=((H(\color{red}aabb) - \color{red}a \*10^3) * 10 +\color{blue}a))\m113\\ &= ((105 - \color{red}1\*1000) * 10 + \color{blue}1) )\m113\\ &= -8949\\,\m113 \\ &= 91\\ H(bbaa) &= H(\not {\\! \color{red}a} bba\color{blue}a)\\ &=((H(\color{red}abba) - \color{red}a \*10^3) * 10 +\color{blue}a)\m113\\ &= ((91 - \color{red}1\*1000) * 10 + \color{blue}1))\m113\\ &= -9089\m113 \\ &= 64 \\ H(baab) &= H(\not {\\! \color{red}b} baa\color{blue}b)\\ &=(H(\color{red}bbba) - \color{red}b \*10^3) * 10 +\color{blue}b)\m113\\ &= ((64 - \color{red}2\*1000) * 10 + \color{blue}2)\m113\\ &= -19358 \m113 \\ &= 78 \end{aligned}$$

# Answer
> 1 votes
You can build a quick intuition by considering digit-only string and using the decimal value of the substring as its hash. Let's find substring "345" in string "123456789".

At the first pos, we have hash `1*100+2*10+3 = 123`. At second, 234. And at third, 345.

In the same way, you can find for example "333" in "1233345".

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


# Question
Title: Graph coloring with an efficient running time
Let $G(V,E), |V| = n, $ be a (undirected) graph and a coloring function $f: V\rightarrow \\{1,2,3...s \\}$ which assigns to each vertex a color, such that in total there are $n/s$ vertices of each of the $s$ colors.

Starting from a given vertex $a$, the task is to find out if there is a path in the graph, such that it contains all the s colors which are nevertheless represented only once in the path. I guess one way to handle this is to assign to each vertex a list or eventually a dictionary of all colors it is connected to but it's own color. In that case one would have to consider each vertex starting from $a$ such that in it's list of colors it contains at least one color. But as far as I can see it will lead to a brute force algorithm.

Can one do better than this ? Thanks for any help.

# Answer
> 1 votes
The problem is NP-hard: it is as hard as Hamiltonian path, when $s=n$ and $f$ is a bijection. Therefore, you shouldn't expect any efficient algorithm that always works. You could study algorithms for the Hamiltonian path problem and try generalizing them to your situation (e.g., using a SAT solver).

---
Tags: algorithms, graphs
---


# Question
Title: Is this restatement of one-way functions accurate?
I realize this is sort of a trivial ask, but I want to make sure I understand OWFs and it's usually explained with some jargon that I don't find clarifying. So, I'd just like to know whether or not my understanding of one-way functions is "essentially correct":

> $f$ is a one-way function iff it can convert $n$ input bits to $n$ output bits in poly time, such that an adversary (understanding $f$ completely and knowing the output bits produced) has no better strategy than randomly guessing all possible inputs to $f$ to try to find any particular specific output.

Is that more or less it, or am I missing anything? In particular, it's unclear to me if it's also fine for a OWF for there to exist some better attack than random guessing, just so long as it's not effective enough to take it out of exponential time.

# Answer
It might be close, but I don't think it's 100% right. It's not clear what you mean by "find any particular specific output". Typically there's no requirement that an adversary have to try all possible inputs to $f$: it just has to be computationally infeasible to find a pre-image, on average. You could start from that intuition and you'd probably getting the main gist of things, but it won't be exactly right in situations where the details are important.

The mathematical definition is not jargon so much as a precise definition. If you want to study these subjects it's important to learn how to read these precise definitions, as the details matter.

See also https://en.wikipedia.org/wiki/One-way\_function.
> 1 votes

---
Tags: cryptography, one-way-functions
---


title: What is the main concept of a promise?

text:
# Question
Title: What is the main concept of a promise?
The short question is: is a promise just a way to separate the code into different sections, so that when task 1 is done, do this task 2, 3, and 4. And when task 2 is done, do task 5, and so on? These tasks typically can take a long time, such as a fraction to a second to a few seconds, to even minutes or it may even fail. In other words, when something is done or has failed, how to continue?

The longer details are:

There seems to be an increasing use of promises. Is the main idea of promises about "being able to continue"? Or "continuable"?

It seems that in ES6 JavaScript, the promise is just a value, or a promised value (or a promised task), with a state. And then, a promise is "thenable", meaning that the programmer can specify, "what if the promise succeeded, then do \__" or "what if the promise failed, then do \__". It is mainly about being able to control the continuity of code.

(the `state` of a promise above can be `pending`, `fulfilled`, or `rejected`, but it is somewhat implementation level details that we don't have to be concerned about.)

This seems especially important in a single threaded, single process environment, such as in JavaScript, when we fetch some network resource, and *then* when it is done, do something else. Since we don't have the ability to start a new thread to do that, and have the luxury to have the network data fetching "block" us (wait and wait until the complete data returns), so we need to say, "fetch data", and let me go on, and wake me up, and now, when waking me up, do this action `action1`, and this is exactly what `promise.then(action1)` does. (there really is no "wake me up", but just "do what I told you" but call me as a way to wake me up).

If we can have a thread, then we can do "fetch this data and then fill in table and graph" in a new thread. This thread can be "blocked" when fetching data from the network. And we don't have to worry about the main program being blocked.

Using a promise is almost like some lines of code:

```
if (doTask1() === statusSuccess)
then
  ...
else
  ...

```

except now, with promises, the "then" part and "else" part is like being chopped up into pieces, and they don't continue to run in one shot. They run only when ready.

And the code becomes:

```
new Promise(function(...) {
  // do something
})
.then(function() { ... })
.catch(function() { ... })
.finally(function() { ... });

```

But it also seems it is not strictly "single threaded", because if the network call cannot continue to fetch data, then what good is a promise? There are still extra processes or threads, but it is just system operations. (or perhaps user operations, if it is some kind of workers like Web Worker or Worker thread).

The above is with "chained promises", about do this, let me go on, and when done, let me know and continue with \___. And a series of these. There can also be this: do a few things in parallel, and let me go on, and let me know (1) when everything is done, or (2) when one of them is done.

The (1) above can be to get data from 3 computer servers to get something all needed, and don't wake me up until all tasks are done. The (2) above can be, if 3 computer servers do the same complicated computation, and sometimes server 2 is faster, sometimes server 1 or 3, and they come back with the exact same answer. So if any of them come back, wake me up and continue with what I told you to do.

The (1) above is done by ES6 JS `.all()`:

```
Promise.all([promise1, promise2, promise3]).then(function(values) {
  console.log(values);
  // the values of all promises given as an array of items
});

```

The (2) above is done by `.race()`:

```
Promise.race([promise1, promise2, promise3]).then(function(value) {
  console.log(value);
  // whatever is faster
});

```

And there really is no "wake me up". It merely is "continue with what I told you." (because we merely say: `myPromise.then(task1, task2)`).

There also is a subtle difference between an observable and a promise (or thenable). If we register an observer to watch on something after it has already succeeded, the observer is not notified. However, with a promise, since it is about controlling what to do next, so if we say `myPromise.then(task1)` after `myPromise` has succeeded, the `task1` will still run. It is like, when the original task (the promise) is done, do this `task1`, and it doesn't matter if the original promise took 1 ns or 10 minutes or that it is already done. If it is done, always make sure to run `task1`.

So perhaps in one line, promises is about: fragments of tasks, and the program can specify, do task 1 and do this task 2 next when task 1 is done, etc, quite similar to a master plan on a piece of paper that a boss or a planner would hand to you. (and that many of these tasks can't continue to run and let us wait indefinitely, but is when it is finally done (or fail), then do what's next).

# Answer
> 1 votes
It really is quite simple: a promise is like an observable. It is like the Observer Pattern. (or the Publish / Subscribe Pattern).

It is just a little bit difference: for promises, you can subscribe late. Meaning if the answer is ready and you "subscribe" now, you'd still get notified. Another difference is that, there usually can be many subscribers, but for promises, usually it is just one subscriber. (the handler passed into `.then()`. Also, an observer can be notified many times. For a promise handler, it is called at most once.

The core idea is like a callback: when something is done, we will notify you. (or even if it failed, we will notify you with the error). That's it. It is really simple.

---
Tags: programming-languages
---


# Question
Title: Calculator for time complexity of recursive functions
Is there an online tool that returns the time complexity of recursion functions?

For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$.

I tried using Wolfram Alpha, but it doesn't return the above result I was looking for.

# Answer
Wolfram Alpha is giving you a more accurate estimate, $T(n) \sim 2n$. However, it can also give you the weaker estimate $T(n) = O(n)$ you are after:

Just click on *Show weaker bound*.
> 4 votes

# Answer
You can use my master theorem solver to get tight asymptotic bounds. Using your example:
> 3 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Reconstruction of the universal set from disjoint subsets
Before I even attempt coming up with an efficient algorithm, I tried googling for similar problems but didn't get far, most queries mentioning "sets" in them led to some sort of Multiple subset sum or other subset construction problem. What I'm looking for is quite literally the opposite.

The problem is very straightforward:

Given a subset of a power set, I need to tell if I can reconstruct the universal set only by using disjoint subsets.

---

**Example 1:**

$x = \\{1, 2, 3, 4, 5\\}$

$x\_s = \\{\\{1\\}, \\{2\\}, \\{2, 3\\}, \\{3, 4, 5\\}\\}$

$\longrightarrow$ *Reconstruction **possible** with $\\{1\\}, \\{2\\}, \\{3, 4, 5\\}$.*

---

**Example 2:**

$x = \\{1, 2, 3, 4, 5\\}$

$x\_s = \\{\\{1, 2\\}, \\{2, 3\\}, \\{3, 4\\}, \\{4, 5\\}, \\{1, 3, 5\\}, \\{4\\}\\}$

$\longrightarrow$ *Reconstruction **not possible** with sets such that all sets would be pairwise disjoint.*

---

An optimal algorithm does not seem trivial at all, but I also don't believe that I am the first person to think of this type of problem. Are there any resources regarding such problems? Could it be rephrased to become some special case of Knapsack problem?

Also, since I'm only interested in whether it's **possible** or **not** to reconstruct the universal set, maybe there's some trick I am missing that could let me avoid going through the complete tree of possible unions?

# Answer
> 2 votes
It's not clear to me what your problem is (you haven't defined what you mean by "reconstruct the universal set"), but it sounds like you may be describing the exact cover problem. This problem is NP-hard, but there are (worst-case exponential-time) algorithms for it.

---
Tags: algorithms, sets
---


# Question
Title: How can I smooth thousands of faces in a 3D-mesh so as to end up with 6 faces of a die?
I have a 3D scan of an object with multiple faces, for example a standard 6 face die. The scan is a point cloud file of the die. I am able to convert the point cloud into a mesh and retrieve faces from the mesh.

But what I'm not able to figure out is how to smooth the faces so instead of having thousands of faces I end up with 6. I'm sure this has been done I just can't figure it out. The solution can be in c++, python, c#... I care more about how :)

# Answer
> 2 votes
First things first, there is no perfect answer to your problem. For samples taken from real sensors, what constitutes "flat" must always be understood with respect to some tolerance.

Also remember that a real-world six-sided die probably has rounded edges and corners, otherwise you could injure yourself with it. It also likely has physical pips. You have to make a *lot* of assumptions to get six flat faces from a scan.

I'm going to give you a few options, and this should give you enough information to look through the literature for other options.

Option 1: Search for planes in the raw pointcloud.

You can do this using a technique such as the Hough transform or RANSAC. Using RANSAC as our example, picking three points at random defines a plane, and once you have a candidate plane, you can then test all the other points to see which ones fit the same plane (e.g. using least-squares distance). If enough points are "inliers", you have found a plane.

Option 2: Eigenanalysis of neighbourhoods / tensor voting

Suppose you have some collection of 3D points $\mathbf{p}\_1 = (x\_1,y\_1,z\_1), \ldots, \mathbf{p}\_n = (x\_n,y\_n,z\_n)$. We will assume that these points are a "neighbourhood" in some sense; perhaps they are all points within some radius of a candidate point.

Define the *mean position* $\bar{\mathbf{p}}$ to be:

$$\bar{\mathbf{p}} = (\bar{x}, \bar{y}, \bar{z}) = \frac{1}{n} \sum\_i \mathbf{p}\_i $$

and the *covariance matrix* to be:

$$\begin{eqnarray}\mathrm{\Sigma} & = & \frac{1}{n} \sum\_i \sum\_j (\mathbf{p}\_i - \bar{\mathbf{p}}) (\mathbf{p}\_i - \bar{\mathbf{p}})^{\top} \\ & = & \frac{1}{n} \begin{bmatrix} \sum\_i (x\_i - \bar{x})^2 & \sum\_i (x\_i - \bar{x})(y\_i - \bar{y}) & \sum\_i (x\_i - \bar{x})(z\_i - \bar{z}) \\ \sum\_i (x\_i - \bar{x})(y\_i - \bar{y}) & \sum\_i (y\_i - \bar{y})^2 & \sum\_i (y\_i - \bar{y})(z\_i - \bar{z}) \\ \sum\_i (x\_i - \bar{x})(z\_i - \bar{z}) & \sum\_i (y\_i - \bar{y})(z\_i - \bar{z}) & \sum\_i (z\_i - \bar{z})^2 \end{bmatrix}\end{eqnarray}$$

Intuitively, the covariance matrix plays the same role as the variance in a one-dimensional statistical analysis; note that the diagonal entries exactly are the variances of the three coordinates. But this matrix contains additional information about how the coordinates vary together.

Now let's suppose that we can diagonalise this matrix. That is, suppose there is an invertible matrix $\mathbf{Q}$ and diagonal matrix $\mathbf{\Lambda}$ such that:

$$\mathbf{\Sigma} = \mathbf{Q} \mathbf{\Lambda} \mathbf{Q}^{-1}$$

Because $\mathbf{\Sigma}$ is symmetric, we can further assume that $\mathbf{Q}$ is orthonormal, and so:

$$\mathbf{\Sigma} = \mathbf{Q} \mathbf{\Lambda} \mathbf{Q}^{\top}$$

where:

$$\mathbf{\Lambda} = \begin{bmatrix} \lambda\_1 & 0 & 0 \\ 0 & \lambda\_2 & 0 \\ 0 & 0 & \lambda\_3 \end{bmatrix}$$

and:

$$\mathbf{Q} = \begin{bmatrix} u\_1 & u\_2 & u\_3 \\ v\_1 & v\_2 & v\_3 \\ w\_1 & w\_2 & w\_3 \end{bmatrix}$$

where $\hat{\mathbf{e}}\_1 = (u\_1,v\_1,w\_1)$, $\hat{\mathbf{e}}\_2 = (u\_2,v\_2,w\_2)$, and $\hat{\mathbf{e}}\_3 = (u\_3,v\_3,w\_3)$ are orthonormal vectors.

We will also suppose without loss of generality that $\lambda\_1 \ge \lambda\_2 \ge \lambda\_3 \ge 0$.

This decomposition gives you a lot of information about the shape of the points in the neighbourhood. For example, define the *linearity* to be:

$$\mathrm{linearity} = \frac{\lambda\_1 - \lambda\_2}{\lambda\_1}$$

This number is 1 if the points lie perfectly in a line, and furthermore, $\hat{\mathbf{e}}\_1$ is a vector tangent to the line.

Define the *planarity* to be:

$$\mathrm{planarity} = \frac{\lambda\_2 - \lambda\_3}{\lambda\_1}$$

This number is 1 if the points lie perfectly in a plane, both vectors $\hat{\mathbf{e}}\_1$ and $\hat{\mathbf{e}}\_2$ are tangent to that plane, and $\hat{\mathbf{e}}\_3$ is normal to that plane.

Using these statistics gives you a basic framework to decide whether or not some neighbourhood of points is part of the same plane or not. The basic idea can be extended to detect junctions using a technique called "tensor voting".

Option 3: Mesh simplification.

A third option is to use the mesh that you have, and simplify it. You can simplify meshes by merging faces or merging points.

One example approach is very similar to eigenanalysis (which is why I went through that in some detail), but approximates each vertex in the mesh as a quadric form, which is essentially the same thing as a mean location and covariance matrix, and then updates these matrices as points get merged. For full details, see:

# Answer
> 1 votes
If the corners aren't too rounded, you can try to find vertices close to the eight actual corners.

* compute the centroid;
* find V0, the vertex farthest from the centroid;
* find V1, the vertex farthest from V0 (V0V1 is a long diagonal of the cube);
* find V2, the vertex farthest from the line V0V1;
* find V3, the vertex farthest from V2;
* find V4, the vertex farthest from the plane V0V1V2;
* find V5, the vertex farthest from V4;
* find V6, the vertex farthest from the bisector plane of V0V1V2 and V0V1V4 (choose the plane that bisects the largest angle);
* find V7, the vertex farthest from V6.

Every step takes time O(N) and is robust against inaccurate vertices.

Now you have a quasi-cube formed by these eight vertices. You can use them as such but the faces won't be exactly planar. You can use them to build an exact cube, for instance by taking the average distance to the centroid for the size and form a orthonormal frame based on some of the sides (using Gram-Schmidt or the Kabsch method).

For better accuracy, you can use the eight vertices to create separating planes and define eight octants in space. By assigning the point of the clouds to every octant, you obtain eight plane fitting problems.

# Answer
> 0 votes
Just to share what I ended up doing: First I down sampled my point cloud from 60 million points to 60 thousand points, while keeping the shape of the object as much as possible. This was done using the opend3D function: pcd.voxel\_down\_sample(voxel\_size=0.05)

After that I used the CGAL - shape detection: https://doc.cgal.org/latest/Shape\_detection/index.html. This gave me a set of regions which represents each one of the surfaces of the object.

Now I can average out the normal values of each region in order to achieve a smooth surface. If I'm missing something, please comment! Thanks @"Yves Daoust" and @"Pseudonym" for your help.

---
Tags: computational-geometry, computer-vision
---


# Question
Title: What is the difference between solving and verifying an algorithm in the context of P, NP, NP-complete, NP-hard
I am struggling to understand the difference between the notions $P, NP, NP-$complete, $NP-$hard. Let's take the example of the $NP-$class. We say that these problems are solved in non-polynomial time, i.e. they have an exponential time complexity, while at the same time we say that they are verified in polynomial time. What is the difference between solving and verifying in this context ? Can you give a concrete example of an algorithm in which you would show the difference between the solution and verification? Thanks.

# Answer
> 4 votes
Just to clear things up: these classes contain *problems*, not algorithms. A problem is in $P$ if there exists a deterministic algorithm that solves it in polynomial time (there could also exist one that solves it in exponential time, that's fine).

> Let's take the example of the NP−class. We say that these problems are solved in non-polynomial time, i.e. **they have an exponential time complexity,**

Note that $P \subseteq NP$, every problem solvable in deterministic polynomial time is also solvable in non-deterministic polynomial time. So the highlighted part is wrong.

You are thinking of $NPC$ \- the problems which are, in a sense, the hardest in $NP$. However, it is currently an open question whether there is no polynomial solution to them (this is the "$P$ vs $NP$" problem).

Here's an example to illustrate the difference between solving and verification and why it's plausible that verification of these problems would be faster than solving.

We'll take the classic problem $SAT$ which asks you to determine, given a boolean formula, whether there is an assignment of $true$ or $false$ to each variable that would make it true. E.g.

$(x\_1 \lor x\_2) \land (\neg x\_2 \lor \neg x\_1 \lor x\_3) \land (\neg x\_1 \lor x\_3) $

How would you solve it? The simplest solution (by the metric of how much effort it takes to think of it) is to try all possible assignments and see if one holds; this is exponential in the number of variables. There are many ways to improve this, but we currently know of no method to solve this in polynomial time and most people believe there isn't one.

However, if I gave you an assignment, e.g. $\\{ x\_1 = true, x\_2 = false, x\_3 = true \\}$ you can easily check that it satisfies the formula. Just go through the formula, substitute the variables with the value associated and use truth tables for the logical connectors. This takes linear time.

These concepts ($P$, $NP$, "easily verifiable" etc.) have rigorous definitions; I would strongly advise reading a textbook on the subject, such as:

* Hopcroft & Ullman's "Introduction to Automata Theory, Languages, and Computation"
* Michael Sipser's "Introduction to the Theory of Computation"
* Christos Papadimitriou's "Computational Complexity"

# Answer
> 2 votes
A simple example is integer factorization.

Finding the factors of an integer is notoriously difficult. So difficult that it is used in cryptography applications. This is a "solving" problem.

Checking that number are indeed factors of an integer is easy, by computing the remainder of the division. This is a "verifying" problem.

This concept is orthogonal to the complexity classes.

# Answer
> 2 votes
Consider an $n\times n$ sudoku puzzle $P$ that I give you as input, and you have to decide whether the puzzle $P$ is solvable. Formally, we consider the following language $\text{SUDOKU} = \\{ \langle P\rangle: \text{$\langle P\rangle$ is a description of a solvable sudoku problem} \\}$

Note that the language $\text{SUDOKU}$ contains puzzles $P$ of non-constant size.

Now if I give you a puzzle $P\in \text{SUDOKU}$ and a solution $S$ for it: so I give you a pair $\langle P, S\rangle$, then you can verify in time polynomial in $|\langle P\rangle|$ whether $S$ is a correct solution for the puzzle $P$. The latter shows that we have a polynomial time verifier for $\text{SUDOKU}$ and thus proves that the language $\text{SUDOKU}$ is in NP.

However, solving $\text{SUDOKU}$ means that given any puzzle $P$, you have to decide whether it has a correct solution $S$, which is sounds harder since you have to "prove" whether a correct solution $S$ exists (from an exponential number of candidate solutions).

In other words, on an intuitive level, checking a solution should be easier than suggesting a correct solution (unless P = NP).

---
Tags: time-complexity, np-complete
---


# Question
Title: Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?
I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution.

My approach was that it has infinite because,

lets say we have $x = a^5$ and $y = a^7$.

If we append them with $aa$ then $x = a^7$ and thus $x \notin L$ and $y = a^9$ and thus $y \in L$. Because $9$ is a square number even though it's uneven and 7 is not even nor is it a square number.

So $x$ and $y$ must be in different classes and the infinite many classes could be written as:

$\\{ \[a^k\] =\\{ k \geq 0, \text{ k is uneven and not a square number} \\}\\}$

and

$\\{ \[a^k\] =\\{ k \geq 0, \text{ k is even or a square number} \\}\\}$

So in the end we have both those sets formed as union.

$\ $

My textbook says the solution is $\\{\[w\] \ | \ w \in L(a^\*)\\}$.

Is this also infinite because we take every word out of $L$ or how can I understand the notation?

And if yes, would this be equivalent to my approach even though my set is "separated", but because in the end I formed a union with bot sets?

# Answer
> 0 votes
Change the description to "n is even or an odd square".

For every r, let $k = 4r^2$. $a^k a^j$ is in the language if j is even, or if j is odd and k+j is a square. The smallest odd j is $(4r+1)^2 - 4r^2 = 8r+1$. For every r, the smallest odd j is different, so we have an infinite number of equivalence classes.

(Actually, each exponent k gives a different equivalence class, because the the smallest j and the difference from the smallest to second smallest j will be different).

PS. Some explaining: If you give me a string x, I can determine all strings y such that xy is in the language. So for any string x, the set of strings y is interesting.

If $x\_1$ and $x\_2$ have the same set of y's that can follow, then $x\_1$ and $x\_2$ can be considered equivalent, and we can create equivalence classes for each different set of y's. If we move to a state machine, then $x\_1$ and $x\_2$ can be moved to the same state, but two x with different set of y's must move to different states. So a language is regular if there are only finitely many equivalence classes.

I personally prefer not to look at the x, but at the follow-sets, that is the possible sets of y's. The problem is the same, if the set of follow-sets is finite / infinite then the set of equivalence classes is finite / infinite. But it's often easier to argue that there are infinitely many different follow sets; I first showed that the smallest j so that $a^j$ is in a follow set gives infinitely many different values - enough to show the language is not regular.

Or you don't even need the exact follow sets. For example if you look for all strings that are the shortest string to add to some x to get a string in L, and show there are infinitely many different ones, or the shortest string with some Property P, that's enough to show L is not regular.

---
Tags: formal-languages, regular-languages, notation
---


# Question
Title: Data structure to determine number of values less than an integer
Given an array of N integers, there may be a need to perform q queries. A query could be like determining the number of values that are less than an integer k. Which data structure could be used to minimize Time Complexity?

**My Thoughts:**
One easy way could be to keep the numbers sorted. And then, for each query, we just have to do a binary search. I am not sure if this can be done easily using a prefix array, segment tree or suffix tree in some way

# Answer
This operation is often called "rank", and there are many data structures that can implement it. It is often seen in the combination "rank/select", where "select" is the converse operation: for any k, it returns the kth smallest integer in the set.

These two operations are surprisingly general. For example, you don't strictly need a set membership query if you have a fast $\mathrm{rank}$ query, since $\mathrm{rank}(k+1) - \mathrm{rank}(k)$ is 1 if $k$ is an element of the set and 0 if it is not.

Binary search on a sorted list is certainly an option, and arguably the simplest one to implement. However, you can do much better, both in time usage and in space usage, by implementing an index for performing efficient rank queries.

I'll give one example of how you can do this, and then direct you to a good starting paper for more details.

We will suppose that the integers stored in the set are known to be in the range $\[0,M)$ for some $M$. $M$ could, for example, be the largest element plus one.

Then you could represent the set as an $M$-element bit vector $\mathbf{b}$, with a set bit denoting membership (i.e. $b\_i=1$ means $i$ is in the set).

Set $l$ to be the closest power of 2 to $\log^2 M$ and $s$ to be the closest power of 2 to $\frac{1}{2}\log M$. (All logarithms are base 2.) Using powers of 2 makes many of the following operations bit shifting and masking, and also ensures that $s$ divides evenly into $l$, which simplifies the analysis.

As an example, suppose $M = 2^{32}$, then $l = 1024$ and $s=16$.

The first part of the rank index is an array $R\_l\[0\ldots \frac{M}{l}\]$, where $R\_l\[i\]$ stores the number of elements in the set that are less than $i\cdot l$.

The second part of the rank index is an array $R\_s\[0\ldots \frac{M}{s}\]$, where $R\_s\[i\]$ stores the number of the elements in the set that are less than $i\cdot s$ but greater than or equal to $\left\lfloor \frac{is}{l} \right\rfloor$.

Then you can compute $\mathrm{rank}(k)$ by:

$$\mathrm{rank}(k) = R\_l\[\left\lfloor k / l\right\rfloor\] + R\_s\[\left\lfloor k / s\right\rfloor\] + \mathrm{popcount}(\left\lfloor k / s \right\rfloor \cdot s, k \bmod s)$$

Here, $\mathrm{popcount}(i, c)$ counts the number of set bits in the range $\[i,i+c)$, by inspecting the bit vector. This may seem like it should take $O(l)$ time, but because $c \< s$, and $s \< \log M$, the number of bits you need to inspect is a constant number of machine words, and so it can be done in constant time. Most modern desktop-class CPUs have a popcount instruction built in, or failing that, you could use a small lookup table (say, of $2^8$ entries) and use bit shift/mask operations and a couple of table lookups to handle the example case of $s=16$.

Alternatively, you can implement popcount in $O(\log c) = O(\log \log M)$ time using clever bit arithmetic, but we will assume it takes $O(1)$ time.

In that case, the rank operation overall takes $O(1)$ time.

Now we consider the size of the index. The array $R\_l$ has $M/l$ entries, and each entry uses $O(\log M)$ bits of storage. The array $R\_s$ has $M/s$ entries, but each entry only requires $O(\log \log M)$ bits of storage. In total, the space usage in bits is:

$$O\left(\frac{M}{\log M}\right) + O\left(\frac{M \log \log M}{\log M}\right) = o(M)$$

That's *little*-oh of $M$ bits, compared to the bit vector itself which uses $M$ bits.

Index data structures which have this asymptotic space behaviour are referred to as "succinct". Succinct data structures are an important class of data structures because they get more efficient, in a relative sense, as you store more data.

Suppose that a data structure requires $f(M)$ bits of size; you might know this using an information theoretic argument, for example. Then:

* A representation which uses $f(M) + O(1)$ bits is *implicit*.
* A representation which uses $f(M) + O(f(M)) = (1 + O(1))f(M)$ bits is *compact*. So, for example, a data structure which always imposes a 1% overhead is a compact data structure.
* A representation which uses $f(M) + o(f(M)) = (1 + o(1))f(M)$ bits is *succinct*. The *absolute* size of the overhead might grow quite large, but the *relative* overhead is $o(1)$, and so eventually becomes negligible as $M$ increases.

Now, of course, if $M$ is large but the number of elements in the set $K$ is relatively small (i.e. the bit vector is "sparse"), this may not be a practical implementation. However, an index which implements "rank on a bit vector" is a basic component in fancier variants which handle the sparse case; many of them essentially boil down to compressing the bit vector and then performing rank queries on the compressed form.

For further information, see:

A final word of caution before you go down this rabbit hole.

You defined the rank operation to be the number of elements in the set *less than* k. Some papers define it to be the number of elements *less than or equal to* k, including the paper I cited above. (Some papers also start counting at 1 instead of 0, which is even more confusing.)

The two conventions are equivalent, of course, but I recommend using your "less than" convention. Take it from someone who has implemented rank/select indexes, it makes everything slightly simpler. But it does mean that you may have to mentally translate some of the papers you read.
> 4 votes

# Answer
If the range of the integers is small then you can compute the histogram of the inputs then compute the prefix sum of this histogram. This preprocessing takes $O(n) $ time. Now given the prefix sum, you can now perform each query in $O(1)$ time.

If the range of the integers is large compared to $N$, then your idea of presorting and then binary search for each query should suffice. You will get an $O( n \log n) $ preprocessing and $O(\log n) $ query.
> 1 votes

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


# Question
Title: What is this definition of orthogonality in programming language trying to convey?
My book Sebasta's Concepts of Programming Language (Chapter 1) states:

> Orthogonality in a programming language means that a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language. Furthermore, every possible combination of primitives is legal and meaningful. For example, consider data types. Suppose a language has four primitive data types (integer, float, double, and character) and two type operators (array and pointer). If the two type operators can be applied to themselves and the four primitive data types, a large number of data structures can be defined.

This explanation feels too contrived, can someone boil it down for me? What does "type operators can be applied to themselves" mean and how does that lead to a large number of data structures? I am not sure I undestand the first sentence as well.

# Answer
There's an iceberg of concepts here.

By "type operators", the author roughly means the methods by which arrays or pointers are created. By "applying type operators to themselves", the author basically means that pointers can be created which point to pointers, and arrays can be created which contain arrays.

The notion of "type operators" only really makes sense if you're thinking in terms of an algebra of types.

For example, `int * int` means a structure consisting of a pair of ints (or equivalently said, an array of ints of length 2) - the star is the multiplication operator, but its operands are type literals, rather than variables, meaning that we are operating on the constraints which types impose, rather than upon the values which a variable contains.

And `int + char` means (roughly) a variant containing either an int or a char. The reason the addition operator is used is because if you created a table of *all possible* values a variable with this type can hold, then that table would consist of all possible int values *plus* all possible char values. The variable will be assigned with one value from amongst these combined possibilities.

Becoming more complicated, something like `(int * (int * char))` could mean a structure containing an int, and a sub-structure containing an int and a char.

Also, people familiar with SQL might understand these operators as being (respectively) like 'cross join' and 'union all', as applied to tables of possible values associated with each type literal, although I'm not sure how soundly this analogy will be perceived.
> 2 votes

# Answer
```
double
array of floats
pointer to character
array of pointers to arrays of integers
array of array of pointers to pointers to double
...

```
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Is assembly macros part of operative system / kernel, or lower down and more seen as hardware?
Update: To clarify. MyNOR (http://mynor.org/) stores some combined instructions in ROM to make programs take up less space. It seems very possible that instruction sets for CPUs might do similar, in more normal computers. I was interested if such load as part of some operative system/kernel/whatever it is called, or is at lower level and seen as "hardware" (if it tends to exist. )

I've learnt basic computer architecture over the past years, and now want to learn about the lowest level of software. I've understood from https://nandgame.com that instructions are not only machine instructions in hardware (such as activating a multiplexer or such), but also combinations of instructions that allow for some of the basic OPCODEs (that are really combinations of instructions. ) Nandgame calls these "assembly macros". I was interested in if these are normally loaded in relatively early in a computer, or if low level processes (bootloader, BIOS, kernel, shell) do not make use of "assembly macros" (or whatever they are called. ) In general, there are many standard trends, but I am interested in all of computer science and engineering history too incl. mainframes in 1950s and what not.

# Answer
> 2 votes
Unfortunately the site you have been looking at has confused you by using the word "instructions" to mean two different things.

A machine instruction tells the machine to do something. For instance, on the Intel 8080 the instruction with byte value 3E says "Read the byte after this, and store it in the A register".

In assembly terms this is MVI A,xx – where "xx" is a number. It is convenient to call this "an assembly language instruction", but this is not really an instruction. It is the letter M followed by the letter V followed by the letter I and so on, and it is the job of the assembler (a program) to read those letters and output the byte 3E followed by a byte containing the number "xx".

No machine executes assembly language instructions. Machines execute machine instructions: that is, they look at a byte in memory (identified by the program counter) and perform - in hardware - whatever action the designer have decided should be performed when that byte is seen. In the example I have given this is: add 1 to the program counter, read the byte in memory which is identified by the program counter and store it into the A register, add 1 to the program counter.

An assembly language instruction is generally translated, by the assembler, into a byte or sequence of bytes which make up one single machine instruction. Thus in the example I have given, "MVI A,7" would be translated into "3E 07".

Sometimes it is more convenient for the programmer if one programmer-written instruction performed an operation that takes more than one machine instruction. For instance, the 8080 can only add numbers to the A register and not to any of the others. Suppose that you find yourself wanting to add a number to the C register, not the A register. Then you would have to move C to A (MOV C,A), add the number to A, (ADI xx), and move the result to C (MOV A,C). Moreover, you would not want the value of A to be changed by this, so you might want to save A beforehand (PUSH PSW) and restore it afterwards (POP PSW).

You wouldn't want to be writing such a long sequence of instructions every time. It is not only tedious, it is error-prone. What you would like is to have a new "instruction" which looks something like "ADIC xx" and which gets translated to the sequence of machine instructions which will save A, move C to A, add xx to C, move A to C, and restore A.

That is what a macro invocation is. It is like inventing a new instruction. When you specify it to the assembler you will normally specify it as "When you see this new instruction, process the following assembly instructions" - which in this case would result in emitting the five machine instructions F5, 79, C6 xx, 4F, F1.

The machine does not know that any of this has happened. The machine just executes machine instructions. It doesn't care whether you those instructions come from an assembler translating a built-in code like "MVI", or a macro defined by you - or from a compiler. It doesn't matter. It is all the same. Machine instructions are machine instructions.

Thus to answer, literally, the question you asked: as far as the machine is concerned, executing the program, "assembly macros" do not exist, and do not need to be loaded. But I hope the longer answer has given you a clearer understanding.

# Answer
> 2 votes
You may be referring to the "macros" that can be defined when using a symbolic assembler for development. Such a program is a translator from a human readable representation of the processor opcodes to machine language (see illustration, middle columns and left columns).

In this frame, a macro is just a shorthand to replace a (short) sequence of instructions that are often used. The macros can be defined by the user (in the program itself) or be predefined by the assembler. They can also have arguments, to handle variable parts.

But in all cases, the assembler substitutes them by their definition before translation and they just don't appear in the generated machine code.

To answer your question direcly: macros appear nowhere in binary code (compiled or assembled programs).

---
Tags: computer-architecture
---


# Question
Title: A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity
Why is Solution 1 faster than Solution 2?

The input passed to both solutions:

```
let myArraySortedSquares = Array(stride(from: -100000, through: 100000, by: 1)).shuffled()

```

**Solution 1** with O(nlog(n)) time complexity and O(n) time complexity

Time elapsed: 2.76 s.

```
// Time: O(nlog(n)) | Space O(n)
func sortedSquaredArray_solution1(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)

    for (idx, value) in array.enumerated() {
        sortedSquares[idx] = value * value
    }
    return sortedSquares.sorted()
}

```

**Solution 2** with O(n) time complexity & O(n) time complexity

Time elapsed: 6.67 s.

```
// Time: O(n) | Space O(n)
func sortedSquaredArray_solution2(_ array: [Int]) -> [Int] {
    var sortedSquares = Array(repeating: 0, count: array.count)

    var smallerValueIdx : Int = 0
    var largerValueIdx : Int = array.count - 1

    for idx in stride(from: array.count - 1, through: 0, by: -1) {
        if abs(array[smallerValueIdx]) > abs(array[largerValueIdx]) {
            sortedSquares[idx] = array[smallerValueIdx] * array[smallerValueIdx]
            smallerValueIdx += 1
        } else {
            sortedSquares[idx] = array[largerValueIdx] * array[largerValueIdx]
            largerValueIdx -= 1
        }
    }
    return sortedSquares
}

```

The problem:

> Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

***This is solved.*** the problem I was using has a shuffled array by mistake, not a sorted one...

I also made a blog posting about it: *Algorithms & Data structures, Problem #003*

# Answer
One solution will run in time up to $c\_1 n log n$ for some constant $c\_1$ if n is large enough. The other solution will run in time up to $c\_2 n$ for some $c\_2$ is n is large enough.

So you have three problems: First, you don't know which n is "large enough". This formula might only work if $n \> 10^{30}$. Second, you don't know how close the actual runtime is to that limit. It might be that for solution 1 the time is one 100th of the formula when n is small, and for solution 2 it is ten times larger when n is small, and only for large n they both get close to the formula. Third, you don't know $c\_1$ and $c\_2$. If $c\_1$ is a tenth of $c\_2$, then you would need log n \> 10 or n \> 1024 for the first formula to actually have a larger value. If $c\_1$ is only 1/20th then you would need n \> 1 million and so on.

The likely reason why your first solution is faster is that most work is done inside a highly optimised implementation of sortedArray, and the Swift standard library has an implementation that is linear when you sort either a sorted array or the concatenation of two sorted arrays, in either ascending or descending order. (You can also sort in linear time if your array is created by taking a sorted array of n elements, and inserting and changing at most O (n / log n) array elements).

From a software development point of view, the first version is much preferable because it is simpler and works for arbitrary functions, not only squares. On the other hand it is likely slower if the sorting method doesn't have this optimisation for sorting sorted arrays.
> 5 votes

# Answer
The big O time notation is a way to talk about relative time behavior of different algorithms **as *n* approaches infinity**. Shooting towards infinity is a trick that allows us to ignore the constant parts of the time behavior, and the lower-level factors.

In the real world of course your n will not be anywhere close to infinity, and often its quite small. So yes, you will often find a simpler algorithm with a theoretically worse O() time behavior will outperform a complex one with a better O() on your real-world data with limited n sizes.

Notice how much simpler the code for your nlogn algorithm is? Its 4 lines of code, vs. 10.

Here's an example graph they use on the Big O Wikipedia page to illustrate the concept mathematically. Two functions of different O() levels are plotted in red and blue. After about x=4.5, the y values will forever be lower for the red function, with the gap ever increasing. However, before that point the constants on the lower factors predominate, and the two functions are quite comparable, with the blue function often returning smaller y values.

The proper way to look at these things experimentally of course isn't to just try both out with a single "n" input size. Double your "n" and see what you get. Then double it again. Keep doing that until it takes one algorithm (probably your nlogn one) annoyingly long to complete.
> 3 votes

# Answer
A likely explanation is the hidden constant. We can assume the following empirical formulas for the running times: c.n.log(n) and d.n.

Then it is possible that c.log(200000) \< d, for instance due to the parts of the code that are interpreted and those using precompiled functions.
> 2 votes

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


# Question
Title: Regularity of “middles” of words from regular language
I need some help with the following problem. Let $L \subseteq \Sigma^\*$ be a regular language. I have to prove that the language $P = \\{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^\*\\}$ is regular, where $\Sigma$ is the alphabet. In other words $P$ is the language of all substrings of words from $L$. How do I prove that $P$ is regular?

# Answer
$L$ is a regular language, so you have a DFA $M$ for it. First remove every “dead” state in $M$, i.e. every state that cannot lead to an accepting state. Make every state in $M$ an accepting state, and make a new start state that $\epsilon$-branches to every state in $M$. The resulting NFA $M'$ recognizes $P$, because:

a) If the string $bac$ was accepted by $M$, then there was a sequence from $Start$ through $S1$ that recognizes $b$, a sequence from $S1$ to $S2$ that recognizes $a$, and a sequence from $S2$ to an accepting state $S3$ that recognizes $c$. But $S1$ is now connected to $Start'$ through $\epsilon$-transitions and $S2$ is an accepting state, hence $M'$ accepts $a$.

b) Conversely, because we have removed transitions that cannot lead to an accepting state, every sequence recognized by $M'$ was part of an accepting sequence for $M$. Because we have not added any edges except those that can be used only to skip $b$, this sequence was consecutive in $M$.
> 2 votes

# Answer
Let $R$ be a regular language. Then there is a finite automaton $M$ for which the language, $L(M)$, of $M$ is $R$. Without loss of generality, we may assume that $M$ has no unreachable states. Construct a new FA, $M'$, as follows:

* For each state $q$ of $M$ which has a sequence of transitions to a final state of $M$, make $q$ a final state. Call the set of such states $S$.
* Add a new start state $q\_0$ having $\epsilon$-transitions to each element of $S$.

It's not hard to see that $M'$ will accept any string which is a substring of some string in $R$.
> 8 votes

# Answer
## Proving the language is regular

We can prove the language $P$ is regular by using other closure properties. Middles are actually substrings. They are obtained by taking suffixes of prefixes of the original language. Both operations of taking prefixes and taking suffixes applied to regular languages will result in regular languages.

## Finding an explicit regular expression for it

In one of the comments the question was narrowed down to: *Given a regular expression, can we find a regular expression for the substrings of a language directly, i.e., without intermediate finite state automata?*

Interesting. Yes, it can be done. First observe that substrings are suffixes of prefixes. I will explain how to find an expression for prefixes. Then a similar solution works for suffixes, and we can apply both operations in turn.

The solution works recursively, as regular expressions are defined that way. Let $\alpha, \beta$ be regex's. Your own notation may vary.

$\operatorname{pref}(\alpha + \beta ) = \operatorname{pref}(\alpha)+\operatorname{pref}(\beta )$

$\operatorname{pref}(\alpha \cdot \beta ) = \operatorname{pref}(\alpha)+\alpha\cdot\operatorname{pref}(\beta )$

$\operatorname{pref}(\alpha^\* ) = \alpha^\*\cdot\operatorname{pref}(\alpha )$

Then we should add a base-case.

$\operatorname{pref}(a) = \varepsilon+a$
> 7 votes

# Answer
Given a finite alphabet $\Sigma := \\{a, b, \dots\\}$, consider the so-called "tagged" alphabet $\Sigma' := \\{a', b', \dots\\}$. Consider the monoid morphisms $untag, killTag : \Sigma \cup \Sigma' \to \Sigma$ given by

* $untag(a) := a$ for $a \in \Sigma$, $untag(a') := a$ for $a' \in \Sigma'$.
* $killTag(a) := a$ for $a \in \Sigma$, $killTag(a') := \varepsilon$ for $a' \in \Sigma'$.

We can verify that these are indeed monoid morphisms. We know that the class of regular languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages. With this in mind we see that

$P = killTag\[untag^{-1}\[L\] \cap \Sigma'^\*\Sigma^\*\Sigma'^\*\]$

which is also regular due to the closure properties of regular languages mentioned above.
> 1 votes

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


title: Multithreaded deduplication of sets

text:
# Question
Title: Multithreaded deduplication of sets
Let's say there are four sets containing integers. No set has any duplicates within itself, but duplicates exist across sets.

```
A = [1, 2, 3, 4]
B = [2, 3, 4, 5]
C = [3, 4, 5, 6]
D = [4, 5, 6, 7]

```

The goal is to store each unique element in a resulting set `R`. The naïve single-threaded solution would be to iterate over each set one after the other while keeping track of already seen elements in a separate data structure `S`. If an element was already seen, do nothing. Otherwise, store the element in `R` and update `S`.

For large sets (e.g. 10,000,000 or more total elements) this can get quite slow. Is there a multi-threaded approach for this problem which improves performance?

# Answer
> 1 votes
I will assume that each set is stored as a sorted list/array. You can compute the union of two sets using a merge algorithm. This should run in linear time, and is quite I/O friendly, as you only scan through the list in a forward direction (no random access needed). It is easy to extend this to a four-way merge.

If you have $N$ processors, one approach is to divide the range of integers into $N$ subranges, and have each processor responsible for the portion that falls within that range. In other words, suppose that all integers are in the range $\[0,M-1\]$. Then the $i$th processor can be assigned the range $\[(i-1)M/N,iM/N-1\]$. The $i$th processor is responsible for computing

$$(A \cap \[(i-1)M/N,iM/N-1\]) \cup \cdots \cup (D \cap \[(i-1)M/N,iM/N-1\]).$$

It can do this by using binary search to find the first and last element of A in this range, and the same for each of B, C, D, and then running a four-way merge on the elements of A,B,C,D in that range.

Finally, you concatenate the outputs of all $N$ processors.

---
Tags: algorithms
---


# Question
Title: What is the difference between clock cycle and clock period?
I'm reading Computer Organization and Design Sixth edition by Patterson and they define clock speed as this:

> Almost all computers are constructed using a clock that determines when events take place in the hardware. These discrete time intervals are called clock cycles (or ticks, clock ticks, clock periods, clocks, cycles). Designers refer to the length of a clock period both as the time for a complete clock cycle (e.g., 250 picoseconds, or 250 ps) and as the clock rate (e.g., 4 gigahertz, or 4 GHz), which is the inverse of the clock period.

What is the difference between clock cycle and clock period then?

My book says the clock period is the length of the clock cycle... but it also says the clock cycle to be the time for one clock period. Isn't this circular?

How I understood it was that a clock cycle was a pulse of the CPU, and the clock period was the length of time of that pulse. But this is a well known text so I think I'm the one who doesn't understand.

# Answer
> 1 votes
Both the terms can generally be used for the same meaning however there might be a slight difference in the context of where it is used.

Consider the clock of the cpu which provides timing signals to coordinate all hardware, then while referring to the time interval of the clock after which it takes a transition is called its clock period. This is in general for any clock which provides a timing signal and is not restricted to only clocks providing timing signals to a cpu.(Think of the wall clock, the period of its second hand is 60 seconds)

And when we talk in terms of cpu architecture (like pipelining concepts), we use the term clock cycles to denote the time taken to complete 1 instruction(or 1 microinstruction). It kind of provides a layer of abstraction from the working of the clock(If lets say you change the clock, its clock period might change, but still in cpu terms we would still refer to it as 1 clock cycle).

# Answer
> 0 votes
First of all there is a distinction between clock cycle of a computer and central processing unit frequency. In general frequency and Time (i.e period) is directly related i.e 2 seconds is equivalent to 1/2 Hz. This means it took 2 seconds between two clock ticks or signals and frequency is handy to describe what happen in the context of in one second. In this case, only half of that signal are transmitted. clock speed usually are much more slower than the CPU speed because they are used to coordinate the timing between microchips let say between CPU and RAM. This is because they have different frequency (i.e speed). For example if your CPU want to read data in the memory (for example RAM) it needs to have ideal timing to read in that RAM's address pin otherwise it may read a false data. computer clocks are a different type of entity than the processor itself. It is just like a normal clock to regulate things. If you make a deeper reading, there are many events that happens within one clock cycle, so this gives you as a benchmark tool like when to read data and write data to RAM for example from CPU.

---
Tags: computer-architecture
---


# Question
Title: formal definition for "data type with larger range"
Wikipedia defines `range of data type`:

> *the set of possible values that that variable can hold.*

Suppose we have two data types *A* and *B*. Now, with attention to the definition of *widening* in section `7.4` of Concepts of Programming Languages, we can say:

> *range of B is larger than A* when *range of B* includes at least approximations of all members of *range of A*.

But above definition is informal; because "accuracy" of approximation is not determined. For example we can consider `0` as approximate for `0` of `*int*` and `1` as approximate for all other members of `*int*`. So we give a strange statement:

`range of `*int*` ≤ range of *{0,1}*`

Although we can add the `*|A| ≤ |B|*` as a criteria to avoid some strange statements like above one (`*|A|*` means Cardinal number for set `A`); but the problem of "accuracy" remains again.

Do you know a formal definition for "a data type with larger range"?

# Answer
$$B\_{\text{min}}\le A\_{\text{min}}\land B\_{\text{max}}\ge A\_{\text{max}}$$

should do (with the implicit assumption that the types $A$ and $B$ are appropriate to represent numbers).
> 1 votes

---
Tags: programming-languages, definitions
---