# Question
Title: Why sequential consistency model is widely used if it is unsound
From this talk and these lecture notes here and here I learned that sequential consistency does not actually model what really happens in practice. However, it is also pointed out that most of the work in formal methods assumes the sequential consistency model even though there exists other models which correctly characterize what really happens in practice. I'm unable to understand why the sequential consistency model is widely used if it is unsound with respect to what happens in practice. Is there a good reason for doing this? What confused me even further was that in the textbooks on concurrency theory that I could access (e.g. \[1\]. \[2\], \[3\]), I could not find any references to this topic.

1. Roscoe, B. (1998). The theory and practice of concurrency.
2. Bowman, H., & Gomez, R. (2006). Concurrency theory: calculi an automata for modelling untimed and timed concurrent systems. Springer Science & Business Media.
3. Gorrieri, R., & Versari, C. (2015). Introduction to concurrency theory: transition systems and CCS. Springer.

# Answer
The underlying hardware often has more relaxed memory ordering compared to SC. For example, the X86 will allow for older stores to be reordered with newer loads for a different address due to store buffers. So instead of having a total order over all loads and stores (SC), you only get a total order over all store (TSO). ARM is even more relaxed. And apart from the hardware, the compiler can also reorder instructions if this isn't prohibited.

There are also weak memory models. Weak memory models are a relaxation of strong memory models like SC/TSO because a distinction is made between plain loads and stores and synchronizing loads/stores.

For most engineer it is way too difficult to reason about any other model than SC. SC is often the most intuitive model and that is why many API's are SC (e.g. a C++ atomic by default is SC or Java volatile) and why language level memory models like the Java Memory Model are rooted in SC. Only the experts understand how to relax consistency in favor of improved scalability/performance.
> 2 votes

---
Tags: concurrency, formal-methods, shared-memory
---


# Question
Title: Compressing a bit string when I know how many 1s and 0s there are
Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only `256 choose 16` possible strings that satisfy this condition: that's about 2^83.06.

So I know that I *should* be able to compress this bit string down to 84 bits long. But I don't know how to go about doing it. I tried to make a lookup table, but can't, because it's too big.

Is there a way to quickly perform this compression/decompression?

# Answer
> 2 votes
The operation of translating between combinatorial objects and their indices in some enumeration is known as *ranking/unranking* (ranking is to convert an object to a number, unranking is the opposite). In your case, you are interesting in ranking/unranking subsets.

Suppose that you are given a subset $S$ of $\\{1,\ldots,n\\}$ of size $k$, and want to convert it to an integer in $0,\ldots,\binom{n}{k}-1$. If $k = 0$ or $k = n$ then you can just output $0$. Otherwise, we want to put the $\binom{n-1}{k}$ subsets not containing $n$ before the $\binom{n-1}{k-1}$ subsets containing $n$. Therefore:

* If $S$ doesn't contain $n$ then you just output the rank of $S$ as a subset of $\\{1,\ldots,n-1\\}$ of size $k$.
* If $S$ does contain $n$, you compute the rank of $S \setminus \\{n\\}$ as a subset of $\\{1,\ldots,n-1\\}$ of size $k-1$, and add to it $\binom{n-1}{k}$.

The decoding procedure is very similar. If $k = 0$ you output $\emptyset$, if $k = n$ you output $\\{1,\ldots,n\\}$, and otherwise:

* If the index is less than $\binom{n-1}{k}$, decode it as encoding a subset of $\\{1,\ldots,n-1\\}$ of size $k$.
* Otherwise, subtract $\binom{n-1}{k}$ from the index, decode it as encoding a subset of $\\{1,\ldots,n-1\\}$ of size $k-1$, and add the element $n$ to the resulting subset.

You can precompute all relevant binomial coefficients to speed things up. In your case, the index is more than 64-bit long, so you will have to work with 128-bit arithmetic somehow, but the resulting algorithm should be reasonably fast.

---
Tags: combinatorics, data-compression, bit-manipulation
---


title: What is a self-delimiting program?

text:
# Question
Title: What is a self-delimiting program?
I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974.

Unfortunately this paper is not available afaik, and I couldn't find any definition anywhere. What is the definition? or what is a resource stating the definition and explaining the idea?

# Answer
> 5 votes
While a specific program could be self-delimiting, in this context what we usually mean is a *self-delimiting encoding of programs*. An encoding of programs is *self-delimiting* if it forms a *prefix code*, that is, no program is a prefix of another program. Intuitively, programs are self-delimiting, so there is no ambiguity in where a program ends.

Why do we care? Consider the chain rule in Kolmogorov complexity, which expresses the idea that if there are short programs that generate $x$ and $y$, then there is a short program that generates the concatenation $xy$. If programs are self-delimiting, then a program for generating $xy$ could look as follows:

* Run the following two programs in sequence.
* Program for generating $x$.
* Program for generating $y$.

Denoting the Kolmogorov complexity of a string $w$ by $C(w)$, this shows that $$ C(xy) \leq C(x) + C(y) + O(1). $$ (The $O(1)$ takes care of the first bit.)

In contrast, if programs are not self-delimiting, then it is impossible to tell where the program for generating $x$ ends. Therefore the chain rule for non-self-delimiting Kolmogorov complexity takes the more complicated form $$ K(xy) \leq K(x) + K(y) + O(\log K(x) + 1), $$ where $O(\log K(x))$ is needed to delimit the first program.

Self-delimiting programs are also useful for defining the *universal distribution*, which is a distribution on programs useful for understanding average-case complexity. The probability that the program $P$ comes up is $2^{-|P|}$. Since the valid programs form a prefix code, Kraft's inequality states that $\sum\_P 2^{-|P|} \leq 1$, so this is a (sub-)probability distribution.

So far the advantages of prefix-free Kolmogorov complexity. The disadvantage is that whereas $K(w) \leq |w|$, this no longer holds for $C(w)$; instead we only have $C(w) \leq |w| + O(\log |w|+1)$.

You can read a lot more on these issues in the excellent monograph of Li and Vitanyi on Kolmogorov complexity.

---
Tags: turing-machines, reference-request
---


# Question
Title: can a machine generate truly random numbers?
I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However, they tend to be biased somehow. So, is it possible to make devices that can generate unpredictable processes and also unbiased (truly random)? (Please note that I am not asking whether true randomness can be achieved by composing PRNG)

# Answer
What is true randomness, and is it necessary? Algorithms cannot distinguish truly random bits from pseudorandom bits (by definition!), and so in practice we are only interested in generating strongly pseudorandom bits. As indicated above, true randomness ensures that even if we run the same algorithm twice, we get different results.

True randomness is required only in highly classified cryptographic applications, such as one-time pads, used for strategic communication. Although pseudorandom bits are still enough, now the bar is a lot higher, due to the importance of the data being encoded. Nevertheless, by crunching more pseudorandom and truly random (but biased and correlated) bits together, we can create highly secure one-time pads. High-quality randomness is generated by combining physical noise and "bit crushers"; stated differently, by injecting "true" randomness into a pseudorandom number generator.

The idea is to start with a high-quality pseudorandom generator, and stick a "pipe" of low-quality true noise into it. The low-quality true noise is truly random, but not iid: it could be highly biased, there could be significant correlations, and so on. By combining it with a good "bit cruncher", the resulting stream of random bits combines the advantages of both sources: it is more unpredictable than the already highly unpredictable pseudorandom generator, and it does not suffer from the bias and correlations of the actual physical source of noise.

Is this "true randomness"? No. But computers won't be able to distinguish the difference. This is already true for high-quality pseudorandom generators, so what did we gain? Two things. First, we may *think* that the pseudorandom generator is strong, but perhaps it's weak; by injecting true randomness, we strengthen it. Second, even a high-quality stream of pseudorandom bits can be predicted if you know the initial seed. For this reason, when reproducibility is not required, pseudorandom generators are initialized with a seed produced from actual (although low-quality) physical randomness.

The pseudorandom generator used in Unix systems employs this methodology. It keeps an "entropy pool" — a source of true, low-quality randomness — and mixes it into a pseudorandom generator. In practice, it works quite well, although it's not completely bullet-proof. Using a dedicated physical random noise generator would result in a much enhanced stream of random bits which should be difficult to attack.
> 2 votes

---
Tags: programming-languages, randomized-algorithms, random-number-generator
---


# Question
Title: Whats exact definition of 'atomicity' in programming?
the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also mean that a program should not run concurrent when it is supposed to be atomic?

let's say we have 2 program as an example:

example\_program1:

> counts int i = 1 to 100 every second
>
> every number is printed in new line

example\_program2:

> just prints "hi"

and a parent program that includes both of these program and run them once receiving a signal to start a specific program (e.g via sigaction in linux) with 2 version:

version 1:

> runs the program (even concurrent) anytime once receiving the signal
>
> which means program2 can print "hi" while program1 is still printing out the numbers

version 2:

> only run one program at a time
>
> signal for other program is blocked until program in progress has terminated

in this example, can only version 2 be considered atomic or both? Would this program be non-atomic only if e.g program2 would increment i by 1 during its process?

# Answer
If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it.

Obviously if you write code to perform an operation X, and other code can see it half performed, or interfere with it, then your implementation of the operation X is not atomic.

In some contexts, an”atomic” operation can succeed or fail; if such an atomic operation fails then the effect must be exactly the same as if the operation had never been started.
> 5 votes

# Answer
I'm not sure I know of a simple, formal, abstract definition of "atomic" for a programming language. I know of many different ones at various levels of abstraction and with regards to various topics. I also know some that seem fairly abstract but have fairly sophisticated prerequisites (e.g. presheaf models of concurrency). Part of the problem is that there are a lot of different ways of saying two programs "behave" "equivalently" and some definitions may respect different notions of "equivalent".

A sketch (that I'm making up right now) of one approach with respect to an interleaving model of concurrency is: Given an operational semantics, a sequence of statements is **executed atomically** if all transitions (of the operational semantics) involving those statements happen in sequence. A sequence of statements is **atomic** if all possible sequences of transitions executes the sequence of statements atomically. We could loosen this to an "*as if* they were executed atomically" which we might start to formalize by saying that all possible sequences of transitions are equivalent (presumably observationally equivalent) to a sequence of transitions that executes the statements atomically.

Basically, executed atomically means that once we start executing some sequence of statements, we don't interleave the execution any other statement into the execution of the sequence. Implementation-wise, this might mean that we only execute one thread at a time as in a time-slicing implementation of threads, and a sequence of statements executed atomically means there were no context switches during their execution. The above definition has an issue in that it doesn't really handle coordination between threads well. It wouldn't really make sense to say that communication along a channel between two threads, for example, was ever atomic. (Often we talk about operations on a data structure as being atomic, and that would probably be more appropriate for this example. The definition would be specific to the data structure.)

For your example program and assuming an operational semantics where a `print` statement could be handled in a single transition, then Program 2 would always be executed atomically and is (fairly trivially) atomic. Your second execution describes a scenario where Program 1 is executed atomically while your first does not. If there was some mechanism that guaranteed your second execution always happened, then you could say Program 1 (with that mechanism) was atomic, but otherwise it presumably would not be atomic on its own.

As mentioned in my comment, "atomic" is often used in an informal and/or implementation-oriented sense. Therefore what *exactly* is intended is often unclear, though the spirit of what is intended is usually reasonable clear.
> 2 votes

# Answer
The deep dark ancient origin of the word Atomic in programming refers to an assembly language instruction ATOMIC. In the same way that a group of individual particles (proton, neutron, electron) form a single unbreakable unit called an atom, in programming ATOMIC refers to a group of assembly instructions that form a single *uninterruptable* unit instruction. The first assembly instruction is ATOMIC which suspends all interrupts until interrupts are re-initiated with something like UNATOMIC.

Since then the word ATOMIC has been grossly misused by marketing. Calling a single instruction ATOMIC is just silly.

ATOMIC was originally an acronym, I think it might have been "A seT? Of Multiple Instruction Clusters" - sorry, not sure about the T, it's been many years.
> 0 votes

# Answer
In case of memory models it means that loads and stores of the atomic operation can't be interleaved with any other load and store (even not to a different addres). If you have for example a compare-and-swap, you need a load and a store. Then on the memory order, this load and store need to be adjacent.

A Primer on Memory Consistency and Cache Coherence 2e page 28.

You can download the book for free on the Morgan Claypool website.
> 0 votes

---
Tags: concurrency, critical-section
---


# Question
Title: Prove/Disprove: NP is closed under "mixed" complexity
Let $\displaystyle S\_{1} ,S\_{2} \subseteq \\{0,1\\}^{\*}$, we say $\displaystyle x\in S\_{1}°S\_{2}$ if it's of the form $\displaystyle x=x\_{1} x\_{2} ...x\_{n}$, for $\displaystyle n$ even, such that:

1. $\displaystyle x\_{i} \in \\{0,1\\}^{\*}$
2. $\displaystyle x\_{1} x\_{3} ...x\_{n-1} \in S\_{1}$
3. $\displaystyle x\_{2} x\_{4} ...x\_{n} \in S\_{2}$

Prove or disprove: if $\displaystyle S\_{1} ,S\_{2} \in NP$, then $\displaystyle S\_{1}°S\_{2} \in NP$

I have a feeling it is a proof, simply because I wouldn't know how to disprove it. I know it should come down to finding a certificate $\displaystyle c$ such that $\displaystyle V( x,c) =1$ if'f $\displaystyle x\in S\_{1}°S\_{2}$, based on the certificates of $\displaystyle S\_{1} ,S\_{2}$.

The thing is I don't really know what the division of the word $\displaystyle x$ is. So how can I check if part of the word is in $\displaystyle S\_{1}$ and the other in $\displaystyle S\_{2}$? I could maybe define the $\displaystyle c$ in this way, that it gives you the division, but I don't really know how to define it properly.

Any help?

Keep in mind that's the first time for me studying this subject

# Answer
> 1 votes
The language $S = S\_1 \circ S\_2$ (I'm assuming that was the intended notation) is in NP if $S\_1,S\_2$ are in NP. Indeed, given verifiers for $S\_1,S\_2$, we can construct a non-deterministic verifier for $S$ as follows:

> Given an input $x \in \\{0,1\\}^\*$, guess a decomposition $x = x\_1 \ldots x\_n$ for even $n$, and use the verifiers for $S\_1,S\_2$ to verify that $x\_1x\_3 \ldots x\_{n-1} \in S\_1$ and $x\_2x\_4 \ldots x\_n \in S\_2$.

In terms of witnesses, a witness for $x \in S$ has the following form:

1. An even number $n$ and $n$ strings $x\_1,\ldots,x\_n$.
2. A witness $w\_1$ for $S\_1$.
3. A witness $w\_2$ for $S\_2$.

To verify this witness, we check:

1. $x = x\_1 \ldots x\_n$.
2. $w\_1$ is a witness for $x\_1 x\_3 \ldots x\_{n-1} \in S\_1$.
3. $w\_2$ is a witness for $x\_2 x\_4 \ldots x\_n \in S\_2$.

---
Tags: complexity-theory, turing-machines, computability, automata
---


# Question
Title: Number of planar graphs, given an embedding
I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing for every embedding there is $2^{o(n\log(n))}$ planar graphs, or showing that there exists an embedding with $2^{\Omega(n\log(n))}$ different planar graphs.

I know that without fixing embedding there is $2^{\Theta(n\log(n))}$, but my question differs from it since we fix an embedding beforehand.

I believe that still there is an embedding with $2^{\Omega(n\log(n))}$, but I couldn't prove or disprove it. Here is an attempt I made to try and calculate the number of planar graphs for some embedding I believed would be "hard", but it didn't work out as expected.

Thanks in advance!

# Answer
> 3 votes
Pach and Wenger proved in their paper Embedding planar graphs at fixed vertex locations that if $p\_1,\ldots,p\_n$ are $n$ different points on the plane, then every planar graph on $n$ vertices $v\_1,\ldots,v\_n$ has a planar embedding in which $v\_i$ is found at position $p\_i$.

---
Tags: graphs, lower-bounds, upper-bound
---


# Question
Title: Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence
> You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \\{s\\}$. $G$ is guaranteed to have the following additional property: The graph obtained by deleting $t$ from $G$ has exactly one path from $s$ to each other vertex in $V \setminus \\{t\\}$. How can we compute the maximum flow from $s$ to $t$ in $G$ in time $O(|V|+|E|)$?

First, I read this post, and i think start from $s$ then run BFS, when we visit each node then set it to minimum flow that we find from $s$ to that vertex. Do this until we achieve vertices that have edges to $t$ and push each flow inside that vertices to $t$ this way we have an algorithm with linear time. Is argument correct?

# Answer
Construct a new graph $T=(V', E')$ by modifying $G=(V,E)$ as follows: for each edge $(u,t) \in E$ of capacity $c$ add a new vertex $t\_u$ and an edge $(u, t\_u)$ of capacity $c$, then delete $t$ and all its incident edges.

Notice that $T$ is an arborescence and that the maximum flow in $G$ from $s$ to $t$ is equal to the maximum total flow in $T$ from $s$ to the vertices in $L = \\{ t\_u \mid (u,t) \in E \\}$.

We will now find $f^\*$ in time $O(|E'|) = O(|E|)$.

In order to do so, explore $T$ with a postorder DFS from $s$ and, for each visited vertex $v \in V'$ keep track of the maximum amount of flow $f(v)$ that can be sent from $v$ to the vertices in $L$ (so that $f^\* = f(s)$).

When a leaf $v$ of $T$ is visited we have $f(v) = \begin{cases}+\infty &\mbox{if } v \in L \\ 0 &\mbox{otherwise}\end{cases}$.

When an internal vertex $v$ of $T$ is visited, let $u\_1, \dots, u\_k$ be its out-neighbors in $T$, and let $c\_i$ be the capacity of the edge $(v, u\_i)$. We have:

$$ \begin{equation} f(v) = \sum\_{i=1}^k \min\\{f(u\_i), c\_i\\} \tag{1} \end{equation} $$

Of course you don't actually need to construct $T$. A slight modification of a postorder DFS visit from $s$ in $G$ suffices. Here is a possible recursive implementation in pesudocode where $t$ is assumed to be a global variable, $c(u,v)$ is the capacity of $(u,v) \in E$, and the first call is $\mathrm{flow}(s)$.

```
flow(v):
  if v==t:
    return +infinity

  f=0
  for each out-neighbor u of v in G:
      f += min(c(v,u), flow(u))

  return f

```
> 0 votes

---
Tags: algorithms, network-flow
---


# Question
Title: How can computer memory remember after the computer runs out of battery?
According to my fragile knowledge of computer hardware the way computers store information is by electric circuits. If there is current the bit is 1 if there isnt its 0. My question is after a computer runs out of battery the memory stil holds all of the information, how? Wont it be the case that all the bits are 0?

# Answer
There’s permanent storage that doesn’t need any power and lasts forever.

Your computer likely has a tiny battery for important things like clock time which should last for a very long time.

Your computer probably has code that dumps all memory contents to permanent storage just before the battery runs out and reads it back when there is enough battery life.
> 1 votes

---
Tags: memory-hardware
---


# Question
Title: $\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables
I was going through the text : *Compilers: Principles, Techniques and Tools* by *Ullman et. al* where I came across a claim:

> $\text{"The error entries in the goto table are never consulted"}$

I feel that whenever there is a reduce move, the current state pointer moves some states back. Suppose that $A\rightarrow \alpha$ is the production used and for the viable prefix $\gamma\alpha$ the current state pointer moves back those many states (so as to pop the $\alpha$ from the stack) and goes to state say $I\_n$ and there is a move from $I\_n$ on $A$ to some state $I\_{n'}$.

# Answer
> 1 votes
The goto table is only used immediately after a reduction action, which has just restored the parser state to the state in which the reduced non-terminal follows the dot. So the goto table for that state must have a state transition for that non-terminal; it's not an error entry.

So the error entries are never consulted.

---
Tags: compilers, parsers
---


# Question
Title: Find a Cook Reduction from $R_{Clique}$ to its determinist problem
The question is to find Find a Cook Reduction from $R\_{k-Clique}$ to its determinist problem.

Basically:

k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.

Suppose you are allowed to use an algorithm (B) that in $O(1)$, given as input a graph $G$ and a number $k$, returns whether the graph includes a $k-Clique$ or not.

Use B to define an algorithm (A), that in polynomial time, given as input a graph $G$ and a number $k$, returns a $k-Clique$ if it exists, and a symbol if it doesn't.

My idea:

My idea was to define something as follow:

```
1. While the size of the graph is greater than k
    2. Remove from the graph the node with the lowest deg
        1. check the new G with B, if yes, return it
        2. Else, continue

```

Something like that. I wasn't able to disprove it at least. But is it correct? How would I prove it?

# Answer
Your algorithm doesn't return a $k$-clique. Simply consider a connected graph $G$ that is a proper supergraph of a $k$-clique, and an isolated vertex $x$. Your algorithm with input $G+x$ returns $G$.

You can solve your problem as follows:

* While $\exists $ a vertex $v$ of $G$ such that $B(G-v)$ returns true:
    + Delete $v$ from $G$
* Return $G$.

Let $G^\* = (V^\*, E^\*)$ be the graph returned by the algorithm. Since the algorithm preserves the invariant "G contains a $k$-clique", $G^\*$ must also contain a $k$-clique. This means that we only need to prove that $G^\*$ is not a supergraph of a $k$-clique.

Suppose towards a contradiction that there exists a proper subset $C$ of $V^\*$ such that $|C|=k$ and the subgraph of $G^\*$ induced by $C$ is a $k$-clique. Then, for any vertex in $v \in V^\* \setminus C \neq \emptyset$, $G-v$ also contains a $k$-clique. This shows that the algorithm cannot return $G^\*$ and yields the sought contradiction.
> 1 votes

---
Tags: algorithms, reductions, np, clique
---


# Question
Title: Fast algorithm for finding the size of each connected component in a graph of 2D points
I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s\_1, s\_2, \dots, s\_k$, the sizes of all connected components in $G$.

The vertices of the graph are 2-dimensional points and there is an edge between $v\_1$ and $v\_2$ if the Euclidian distance between them is less than a given distance $t$ (the threshold above), otherwise there is no edge between $v\_1$ and $v\_2$.

Up until now, I've tried DFS methods and also attempted to use a QuadTree to group together "close enough" points.

For the attempt at QTs, I subdivide the plane into cells the diameter of which is sufficiently small to guarantee connectedness, then traverse the tree upwards to find all the neighboring cells and check if they make more connected points.

What I'm asking for is a more efficient algorithm (mainly on the time complexity front) (can be completely different or an improvement on the above, I'm open to anything). For context, the size of the samples I'm dealing with is ~100K.

PS: I do realize there are various other answers dealing with how to *determine* the connected components of a generic graph, but I believe that in this case (2D points and the need to "only" find their sizes) could benefit from more efficient methods. I could be wrong but there is no better way to find out.

# Answer
> 2 votes
You can do it in $O(n \log n)$ time by forming an Euclidean minimum spanning tree, and then dropping any edge with length greater than $t$.

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


# Question
Title: Travelling Salesman Problem with Memoization
I coded a solution for the famous Travelling Salesman Problem but my code does not work properly, although it seems okay.

> In a grid of size m x n, you are allowed to move only down/right, and you need to go from the top-left corner to the bottom-right corner. Each sell has a reward value. How much is the maximum reward you can collect?

```
def travellingSalesman(m, n, rewards, memo={}):

  if m == 0 or n == 0:    return 0
  if (m, n) in memo:      return memo[(m, n)]
  if (n, m) in memo:      return memo[(n, m)]

  # Base case
  if m == 1 and n == 1:   return rewards[0][0]

  # maximum rewarding one of the grids m-1 x n - m x n-1 plus reward of the current cell
  memo[(m, n)] = max(travellingSalesman(m-1, n, rewards, memo), travellingSalesman(m, n-1, rewards, memo)) + rewards[m-1][n-1]

  return memo[(m, n)]

if __name__ == '__main__':
  print(travellingSalesman(m=3, n=3, rewards=[[0,4,2],
                                              [3,2,0],
                                              [4,1,0]]))

```

The function below returns 6, but it should return 8 with the path: 0-\> 3 -\> 4 -\> 1 -\> 0

Can you enlighten me about the problematic/missing part of this code? Thanks!

# Answer
> 0 votes
In the 3rd `if` statement your code assumes that the optimal solution when starting from coordinates $(m, n)$ is equal to the optimal solution when starting from coordinates $(n, m)$. This is clearly false in general.

---
Tags: algorithms, python
---


# Question
Title: How to split the array into two subarrays with the smallest sum difference?
Given

* An array of elements, all elements are positive (unsorted, but sorting is not a problem if required)

The objective:

* To create two subarrays, so that `abs(sum(array_1) - sum(array_2))` is the **smallest** possible

The order of elements in the subarrays and the amount of elements don't matter but **all elements should be used**

E.g.

> Input: Starting Array = {5, 8, 13, 27, 14}
> Result: **3** \- smallest possible difference in sums

Explanation:

> First subarray = {5, 13, 14}
> Second subarray = {8, 27}
> Difference in sums: abs((5+13+14)-(8+27)) = 3 = **min**

I have a guess that it's something connected to the binary search but I have no clue what is being "binary seached" and what to connect it to.

# Answer
This problem is the optimization version of the partition problem, and if it was solvable efficiently, that would mean that $P = NP$. That means it is unlikely that there is a polynomial time solution to split an array in two.

There are exact solution algorithms described on the wikipedia page, and some of them are in pseudo-polynomial time.
> 1 votes

---
Tags: sorting, search-algorithms, binary-search
---


title: Show that this language is decidable?

text:
# Question
Title: Show that this language is decidable?
Let A = { | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.

The questions seems simple so I designed the following TM D that decides whether there exists a DFA with this property or not.

D = "On input w:

1. Construct a DFA B that accept any string containing an odd number of 1s.
2. Construct a DFA **C** s. t. $L(C) = L(B) \cap L(M)$
3. Call $E\_{DFA}$ with input C.
4. If T accepts, then reject. If T rejects, then accept."

$E\_{DFA}$ is defined as following: $E\_{DFA} = \\{ \<A\> |$ A is a DFA and L(A) = $\phi \\}$ So assume there is a TM **T** that decides language $E\_{DFA}$. I.e., T accepts if A is empty, otherwise rejects.

Now, my questions is related to the step 4. In Sipser's textbook, he states that if **T** accepts, then accept and if **T** rejects, then reject. I don't understand why it says so. For example, If $L(M) \cap L(B) = \phi$, then this means that there are different. So, this is what I said in step 4 above. But in Sipser's answer for this exercise in page 187, it says that if they are empty, then accept. Can you explain to me where is my mistake?

# Answer
If $E\_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$. In other words, no word containing an odd number of 1s is also in $L(M)$. Then, by definition of $A$ you should accept.

Conversely, if $E\_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B \neq \emptyset$. That is, there is some word $w \in L(M)$ such that $w$ contains an odd number of 1s. Then, by definition of $A$, you should reject.
> 1 votes

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


# Question
Title: Round Robin, confused about how to processes are handled related to arrival order
See this picture, in parentheses are (arrival time, execution time required)

Why doesn't the "p5" process is processed before "p6"? Why do p3 and p4 are finished and p5 is executed only after the processes that arrive at "11" are executed?

# Answer
> 1 votes
In round-robin scheduling, every process is put into a big queue as soon as they arrive. When a process gets to the front of the queue, it is treated for some fixed number of time-steps (in your case 3 steps, as I suppose is also what's meant by the text "Quantum = 3"). If the process is not finished when its time is up, it gets stowed in the back of the queue. So when Process 5 is done at step 12, it gets stowed in the back of the queue, behind all the processes that arrived at step 11.

---
Tags: process-scheduling
---


title: Time complexity a recursive function

text:
# Question
Title: Time complexity a recursive function
> Suppose given recurrence relation
>
> $$T(n)=T(\sqrt{n})+T(n-\sqrt{n})+n$$ $$T(1)=O(1)$$
>
> How we can find an order of above recurrence relation?

My attempt:

I read following post, but get stuck in understanding that solution.

# Answer
You can expand the formula to find a pattern:

$$ T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n = T(n^{\frac{1}{4}}) + T(\sqrt{n} - n^{\frac{1}{4}}) + T(\sqrt{n-\sqrt{n}}) + T(n-\sqrt{n}-\sqrt{n-\sqrt{n}}) + 2n $$

As you can see, in each expansion, the sum of values inside the functions is $n$. Hence, you can show using the mathematical induction that each time one factor of $n$ is added to the non-recursive part. Hence the only thing is showing that what is the height of this tree of expansion.

As the bigger term is $n - \sqrt{n}$, we should find how long it takes to reach to a constant value. As each time a constant factor of $\sqrt{n}$ is subtracted from $n$ (see from expansion), $\Theta(\sqrt{n})$-times recursions are required to reach to a constant value.

Therefore, $T(n) = \Theta(n\sqrt{n})$.
> 0 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Why does my code work: bijecting binary trees to Dyck paths
The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan numbers. Another set of objects that follows the Catalan numbers is the number of binary search trees with $n$ nodes.

This suggests we can biject binary trees to Dyck paths (see here). We get a hint on how to do the bijection based on why the two objects satisfy the same recurrence (for Catalan numbers):

$$C\_{n+1} = \sum\limits\_{j=0}^{n}C\_{j}C\_{n-j}$$

Binary trees satisfy it because you designate one node as the root, then create a binary tree on its left (with $j$ nodes) and another one on its right. Dyck paths satisfy it by conditioning on the first time the path hits the y=0 line (which is what $j$ in the equation above represents). So we first take a mandatory step up, then we make a path of $2j$ steps that doesn't cross the $y=1$ line; then we go down one step to touch $y=0$ for the first time, and finally we make another path of $2(n-j)$ steps that doesn't cross the $y=0$ line.

This suggests we might be able to construct a Dyck path given a binary search tree (with node-keys labelled from $1$ to $n$ and there is just one way to assign them, see here) recursively, starting at the root. When we go to the left node of the tree, we need to consider the sub-path one level above the current level (where we start at level-0) and when we go to the right, we simply stay at the same level. Since the key of the node we're processing tells us where the path first struck the current level from the start, we know that it 2 times the number of steps representing the key from the start must be a step down.

The Python code below demonstrates this idea and works (tested it extensively). If you don't use python, the idea is very simple; I just set the path array to all 1's ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree nodes.

```
import numpy as np

class TreeToDyck():
  def __init__(self, tree_node, n):
    # Initially create an array of 2n ones. All steps are set to "up".
    self.path = np.ones(2*n)
    # Now insert downs at appropriate places.
    self.tree_to_dyck(tree_node, 1)

  def tree_to_dyck(self, tree_node, start):
    if tree_node is None:
        return
    # Go down. Bear in mind the "path" array is 0-indexed.
    self.path[start+2*tree_node.key-2] = -1
    self.tree_to_dyck(tree_node.left, start+1)
    self.tree_to_dyck(tree_node.right, start)

```

Now, the thing to note is that the key of the node we're at gives us many hints about the path. But, I ignore most of them and simply insert a "down" step. I start with all steps in the path array set to go up. Then, based on the keys of the tree nodes, I insert down steps.

Surprisingly, this is enough. Which means the following two statements must be true:

1. The down steps will never collide with each other. So, we'll never insert a "down" step at the same location twice. This will ensure we insert $n$ down steps, as the path must contain.
2. The last step in the Dyck path is always a "down" step. So, we will always end up inserting a "down" at the very last position in the array no matter the tree.

I want help proving the above two statements. And if there is any other requirement needed to prove that the algorithm will work.

# Answer
My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit.

Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T\_\ell$ and $T\_r$. If the root of $T$ has label $k$ this means that $T\_\ell$ has $k-1$ nodes.

A tree with $n$ nodes has a Dyck codes of length $2n$. There are two ways of determining the Dyck code $dyck(T)$ of tree $T$. One is recursively:

$dyck(T) = U \\; dyck(T\_\ell) \\; D \\; dyck(T\_r)$.

In this string we observe exactly one $D$, which is associated to the tree $T$, other $D$'s are written recursively. The position of this single $D$ is exactly at $2k$. We know this because the length of $dyck(T\_\ell)$ equals $2(k-1)$.

Note that the symbols generated by $dyck(T\_\ell)$ are *shifted by one*, because of the $U$ that is written before its code. This is the main observation: it is due to a left branch, and those left branches is what you are counting in your code.

The other way of determining $dyck(T)$ is graphical. Draw the tree and make a traversal around it. Write $D$ for a left child (even when that leads to an empty subtree) and $U$ for a right child. (We visit each node twice: this is both an pre-order and inorder-traversal.) If you try this you will see that each $D$ appears at the number of the node plus the number of times we went left as seen from the root.

The tree below has code (with subscripts that count position in the string and superscript which is the inorder label associated to the root of the corresponding subtree) $U\_1^3 U\_2^1 D\_3^1 U\_4^2 D\_5^2 D\_6^3 U\_7^{10} U\_8^6 U\_9^4 D\_{10}^4 U\_{11}^5 D\_{12}^5 D\_{13}^6 U\_{14}^8 U\_{15}^7 D\_{16}^7 D\_{17}^8 U\_{18}^9 D\_{19}^9 D\_{20}^{10} U\_{21}^{11} D\_{22}^{11}$.
> 3 votes

# Answer
To formally prove my algorithm works, I think it is sufficient to show these three things. I haven't managed to prove all of them, but still leaving this as an incomplete answer and hope to fill in the gaps over time. Would appreciate if people can help fill the blanks of course.

1. In any path created from a valid BST using the algorithm in my question, there will be exactly $n$ tails.
2. Any path produced in this way is a valid Dyck path.
3. No two distinct trees can ever produce the same path.

For #1, its clear that there can't be more than $n$ tails since there are $n$ nodes in the tree and each of them insert one tail. The only way there can be less than $n$ tails is if two of the nodes insert tails into the same position. This is obviously true for all nodes which are reached by going only right from the root since they simply insert a tails at $2k$ where $k$ is their key. Because no two nodes can have the same key, their inserted tails won't collide with each other either.

When we go left, this is less clear; leaving incomplete for now.

For #2, we know that all Dyck paths end with a tails. And if there are $n$ nodes, there will always be a node with key $n$. And this node can only be possibly reached by going right from the root given the BST property. So, it'll always end up inserting a tail at toss # $2n$. Of course, this is not sufficient to prove that the path will be valid Dyck leaving the rest as TODO.

For #3, haven't been able to make progress so far, leaving it as a TODO.
> 0 votes

---
Tags: trees, combinatorics, counting
---


# Question
Title: Artificial Intelligence: theory vs processing power
It is common to see articles praising the advances in AI (here is one example).

There is no doubt that significant progress has occurred on all kinds of automation, hard games like chess, etc.

The question is, how much of that progress is due to conceptual proogress, as opposed to increase in processing power? Or, to phrase it in a different way: if today's best AI would be shown to a computer scientist from the 60s, would they be impressed by the algorithms? Or just by the raw power of the hardware?

# Answer
AI spans many different areas. If you are actually asking about machine learning, the conventional wisdom is probably that it's a combination of new ideas (e.g., neural networks, architectures, methods for training them), computation power (e.g., GPUs), and data (large labelled datasets).

See, e.g., https://qz.com/1307091/the-inside-story-of-how-ai-got-good-enough-to-dominate-silicon-valley/, https://towardsdatascience.com/the-state-of-ai-in-2020-1f95df336eb0, and probably many more (I didn't spend much time looking).
> 2 votes

---
Tags: artificial-intelligence, theory
---


# Question
Title: Can the House Robber problem be solved with a Sliding Window solution?
I was reading an article on how to solve sliding window problems and it said:

> 3. Fast/Lagging This one is a little different, but essentially the slow pointer is simply referencing one or two indices behind the fast pointer and it’s keeping track of some choice you’ve made. In the House Robber problem you are trying to see what the maximum amount of gold you can steal from houses that are not next door to each other. Here the choice is whether or not you should steal from the current house, given that you could instead have stolen from the *previous* house.

So, I tried to solve the House Robber problem using a Sliding Window (fast/lagging) solution. It worked for a lot of test cases, but there were some that it just would not solve.

I came to the conclusion that it wasn't possible as the problem is recursive (*you don't know whether to rob this house and next-door-but-one unless you know whether to rob next-door-but-one and next-door-but-one, unless you know whether... etc. etc.*)

So, I clicked the Solution button on leetcode and the solutions presented were recursion and tabulation.

Is it possible to solve this problem using a 'sliding window'?

# Answer
> 1 votes
Yes you can! It's called dynamic programming, though.

Usually, the sliding window technique stores only information local to the window, but to make this work, you should store also the global solution up until the current window position.

What you store in a window (size 2?) is what the optimal solution is if you pick the last house of the window, and what is the optimal solution when you skip the last house of the window.

We call this technique dynamic programming, and not sliding window, although they have much in common.

*P.S. this problem is also known as Independent Set in Path Graphs.*

---

I don't know if you call this sliding window, but here is one way of solving it:

```
def window(data):
    if not data:
        return 0
    pick, skip = data[0], 0
    for window_idx in range(1, len(data)):
        pick, skip = data[window_idx] + skip, max(skip, pick)
    return max(pick, skip)

data = [14, 7, 11, 8, 13, 9, 10, 12]
print(window(data))  # 14 + 11 + 13 + 12 = 50

```

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


# Question
Title: Why is the address-of operator in C/C++ represented with the "&" symbol?
I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) symbol instead of, say, the "at" symbol (@). Is there some kind of history behind this?

# Answer
> 5 votes
Because B did!

A user on software engineering.sx contacted Ken Thompson:

> **From: Ken Thompson**
>
> c copied from b so & and * are same there.
> b got * from earlier languages - some assembly,
> bcpl and i think pl/1.
> i think that i used & because the name (ampersand)
> sounds like "address." b was designed to be run with
> a teletype model 33 teletype. (5 bit baud-o code)
> so the use of symbols was restricted.

---
Tags: history, c, c++, language-design
---


# Question
Title: Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's
Consider the alphabet {0, 1}. How do I find the regular expression for the set of all strings such that each block of five consecutive symbols contains at least two 0's?

Here, by block I mean a given set of concurrent substrings. For example, for a string "0011010", the first five characters are "00110", which satisfies the above condition. The next block leaves out only the first character of the given string, giving me "01101", which again satisfies the condition.

I also need help in converting the regular expression into an NFA.

# Answer
> 1 votes
Let's try to understand the structure of words in your language.

Consider any word in the language whose length is at least $5$ (we can enumerate over shorter words separately). We can write it as $$ 1^{i\_1} 0 1^{i\_2} 0 \cdots 0 1^{i\_m}. $$ Our assumption on the length implies that $m \geq 2$, since otherwise the word is in $1^\*$, so has to be shorter than $5$ letters. You can check that a word of this form is in the language iff $i\_j + i\_{j+1} \leq 3$ for all $j$.

Let $r$ be a regular expression for all words of the form above (but without the requirements that the length be at least $5$ and that $m \geq 2$) satisfying additionally the condition $i\_j \leq 2$. Then a regular expression for your language is $$ (0+1+\epsilon)^4 + (11100+\epsilon)r(0011100r)^\*(00111+\epsilon). $$ Let $s$ be a regular expression for all words of the form above satisfying additionally the condition $i\_j \leq 1$. A regular expression for $r$ is $$ r = 11 + (110+\epsilon)s(0110s)^\*(011+\epsilon). $$ Finally, a regular expression for $s$ is $$ s = (0+10)^\*(1+\epsilon). $$

# Answer
> 2 votes
The states of your DFA are pairs of integers $(i,j)$ with $1 \le i \le j \le 5$, plus a $\mathrm{REJECT}$ state. Intuitively state $(i,j)$ means that the two most recent $0$s have been encountered when $i$-th to last and $j$-th to last character were read.

The transition function $\delta$ satisfies $\delta(\mathrm{REJECT}, x)=\mathrm{REJECT}$ for $x \in \\{0,1\\}$ while, for any other state $(i,j)$, $\delta$ is defined as follows: $$ \delta( (i,j), x) = \begin{cases} (1, i+1) & \mbox{if } x=0 \mbox{ and } i\<5\\ \mathrm{REJECT} & \mbox{if } x=0 \mbox{ and } i=5\\ (i+1, j+1) & \mbox{if } x=1 \mbox{ and } j\<5\\ \mathrm{REJECT} & \mbox{if } x=1 \mbox{ and }j=5. \end{cases} $$

The initial state is $(1,1)$. All states, except for $\mathrm{REJECT}$, are accepting states.

---
Tags: regular-expressions, nondeterminism
---


# Question
Title: How to group thousand of data points for each user
I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each data point can have 3 states: true, false, unknown.

What could I do to group these data points so that they don't take too much space?

My initial plan is to basically cluster them. Something like:

* unknown: \[1-23, 25, 27\]
* true: \[24, 26\]
* false: \[28-30\]

Where m-n represents number from m to n.

# Answer
The solution was to use run-length encoding.

Let's say that I have:

* The first 10 questions `true`
* The next 24 `false`
* The next 34 `unknown`

I'd transform it in `10T24F34U`. You can find more info on Wikipedia's Run-length encoding as provided by D.W. in the comments.

The main reason for this solution is to send data via an API. I'm not sure if I'm going to use this algorithm or just rely on the typical compression when sending data to a browser. So that is another possible solution.
> 0 votes

---
Tags: algorithms, clustering
---


# Question
Title: Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin
I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin. Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma). The part I'm having a problem with, is about the complement:

*(Note: I've substituted $B^\infty = B^\* \cup B^\omega$ with $B^\*$ which shouldn't cause problems)*

**From the paper:**

*It remains to deal with the complement $\Sigma^\* \setminus L$ of a star-free set. By induction, we have $L \cap B^\* A B^\* = \bigcup\_{1 \leq i \leq n} K\_iAL\_i$. If some $K\_i$ and $K\_j$ are not disjoint then we can rewrite $$K\_iAL\_i \cup K\_jAL\_j = (K\_i \setminus K\_j)AL\_i \cup (K\_j \setminus K\_i)AL\_j \cup (K\_i \cap K\_j)A(L\_i\cup L\_j)$$ We can also add $(B^\* \setminus \bigcup\_{i} K\_i)A \emptyset$ in case $\bigcup\_{i}K\_i$ is strictly contained in $B^\*$. Therefore, we may assume that $\\{K\_i \mid 1 \leq i \leq n\\}$ forms a partition of $B^\*$. This yields: $$(\Sigma^\* \setminus L) \cap B^\*AB^\* = \bigcup\_{1\leq 1 \leq n} K\_iA(B^\* \setminus L\_i)$$*

**Questions:**

1. In the last part of the proof $\bigcup\_{1\leq 1 \leq n} K\_iA(B^\* \setminus L\_i)$, why is it enough to only build the complement for $L\_i$ with $B^\* \setminus L\_i$? Why don't we need $B^\* \setminus K\_i$?
2. Why does $\\{K\_i \mid 1 \leq i \leq n\\}$ form a partition of $B^\*$?

# Answer
2. For the set $\\{K\_i \mid 1 \leq i \leq n\\}$ to form a partition of $B^\*$, it is necessary, that all $K\_i$ are pairwise disjoint and every element in $B^\*$ is cointained in some $K\_i$. You already showed that they are disjoint, as is is possible to split two overlapping $K\_i$ into three disjoint ones by using the parts that don't overlap and the intersection instead. The second condition, that everything is contained, is achieved by adding $(B^\* \setminus \bigcup\_i K\_i)$ to the set $\\{K\_i \mid 1 \leq i \leq n\\}$ so $n$ is incresed by one and still is finite. And this $(B^\* \setminus \bigcup\_i K\_i)$ contains everything that was not previously contained.
3. As $\\{K\_i \mid 1 \leq i \leq n\\}$ forms a partition, everything in $B^\*$ is contained in some $K\_i$ and is, therefore, also contained in the complement of another one, which means, it doesn't change anything to use the complement of the $K\_i$s.
> 1 votes

---
Tags: formal-languages, first-order-logic
---


# Question
Title: Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2
I am not able to solve the following recurrence relation:

$$ T(n) = \begin{cases} T(n-1) + n^2 & \text{if } n \ge 2, \\ 1 & \text{otherwise.}\\ \end{cases} $$

How do I start?

# Answer
> 0 votes
In general, the recursion formula T(n) = T(n-1) + g(n), T(1) = c has the solution T(n) = c + sum of g(k) over 2 \<= k \<= n. No recursion, just a simple summation.

# Answer
> 0 votes
$$T(n)=T(1)+\sum\_{i=2}^{n}i^2$$ $$T(n)=T(1)+\sum\_{i=1}^{n}i^2-\sum\_{i=1}^{1}i^2$$

*So as @plop mentioned in comments, we have:* $$\lim\_{n\to \infty} T(n)=\frac{n(n+1)(2n+1)}{6}=O(n^3)$$

---
Tags: recurrence-relation, discrete-mathematics, mathematical-analysis
---


# Question
Title: matrix multiplication speedup when the matrix elements are 0, 1 and -1
I would like to compute matrix multiplication `A * B` where `A` is Nx3 and `B` is 3x3. We also know that the elements of `B` only contains 0, 1, and -1. The content of `A` is arbitrary floats.

Is there any speedup we can do?

# Answer
Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like

```
ResultX = ax * c00 + bx * c01 + cx * c02
ResultY = ax * c10 + bx * c11 + cx * c12
ResultZ = ax * c20 + bx * c21 + cx * c22

```

Use a switch for the 27 possible values of c00, c10 and c20. Then we need just the fma’s and even replace one of them with a plain multiplication in case one of these numbers is zero.
> 1 votes

---
Tags: algorithms, matrix-multiplication
---


# Question
Title: Combinations (repetition not allowed & order not important)
How to compute a table of numbers (all possibilities), where **repetition is not allowed** and **order is not important**. Example:

I have a set of prime numbers. In this example I have four: {3,5,7,11}, but it can be anything, and I want to choose every pair out of that set. To make things easier, I want to compute the indices to get those pairs of prime numbers. The set of indices is then {0,1,2,3}. We pick 2 out of 4 elements. So how do we compute the permutations or combinations:

```
0,1   (3,5)
0,2   (3,7)
0,3   (3,11)
1,2   (5,7)
1,3   (5,11)
2,3   (7,11)

```

?

It was difficult to find examples on the web, because they either allowed repetitions or were order was important. Pls answer with pseudocode or c/c++ if you can.

# Answer
> 1 votes
You seem interested in just **pairs** of indices. Then, if you have $n$ elements you can just generate all pairs of indices $(i,j)$ with $0 \le i \< j \< n$.

```
For i=0,1,...,n-2:
   For j=i+1, i+2, ..., n-1:
      Output (i,j)

```

---
Tags: combinatorics, c, c++, pseudocode
---


# Question
Title: Problem to understand a Bellman Ford algorithm exercise
I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).

> Exercise 24.1-3 (page 654)
>
> Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, let $m$ be the maximum over all vertices $v \in V$ of the minimum number of edges in a shortest path from source $s$ to $v$. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple change to the Bellman-Ford algorithm that allows it to terminate in $m + 1$ passes, even if $m$ is not known in advances.

So what is $m$ exactly? I am really have the trouble to understand the first sentence.

# Answer
The only way to understand it is to break it down.

> Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, let $m$ be the maximum over all vertices $v \in V$ of the minimum number of edges in a shortest path from source $s$ to $v$. (Here, the shortest path is by weight, not the number of edges.)

Okay, so $s$ is fixed, and let us suppose you have a vertex $v$.

Now we look at *all the cheapest* paths from $s$ to $v$ and we take the path that has the fewest edges; this number of edges we refer to as $m\_v$.

If we repeat this for every vertex $v \in V$, then we get one $m\_v$ for each $v$. The value $m$ is the maximum of all $m\_v$s, or $\max\_{v \neq s}m\_v$.

Or in other words, over all cheapest paths starting in $s$, let us look at the vertex with the longest shortest. It has length $m$.

It is confusing because we want the longest shortest over all the cheapest.
> 1 votes

# Answer
*Suppose our graph be line graph, or path graph, in such a graph $m$ equal to $v-1$ so we can say over algorithm run $m$ times and in iteration $m+1$ no distance of any node updated, so it's sufficient to continue until a iteration that no $d\[v\]$ updated.*

note that in this worst case example, $\max\min\_{m\in V}\ell$ have $V-1$ edges
> 0 votes

---
Tags: graphs, shortest-path, weighted-graphs
---


# Question
Title: NFA: each block of five consecutive characters contains at least two 0's
How can I find an NFA for such a language, considering the alphabet to be {0, 1}. I've tried deriving it from the DFA (@Steven) and the regular expression (@Yuval Filmus), but no luck.

# Answer
> 2 votes
Your DFA *is* already a NFA, so you're done.

---
Tags: finite-automata
---


# Question
Title: Transitions between lexicographical orders
I have six characters: (,),\[,\],{,}. They are stored lexicographically: '(' \< ')' \< '\[' \< '\]' \< '{' \< '}'. So I can store all balanced parenthesis sequences of length $n$ lexicographically and each sequence will have unique number $1 \dots catalan(n)\*3^n$. Than I want to get sequence by its number.

**Problem:** If I have another order, for example '}' \< '\[' \< ')' \< '(' \< '{' \< '\]', then all balanced parenthesis sequences again are stored in lexicographical order, but the same sequences will have different numbers, according to these two orders. If I'm given a number of a sequence in second order, can I efficiently recalculate it to the number of the same sequence but in the first order? *The main problem is that I don't know the sequence which corresponds to given number in second order. (I wish to find it)*

**Example:** First order: '(' \< ')' \< '\[' \< '\]' \< '{' \< '}'

Second order: '}' \< '\[' \< ')' \< '(' \< '{' \< '\]'

I get number 1 for sequences with 1 pair of parthenses, the corresponding sequence is \[\] in the second order. I want to calculate number of \[\] in first order --- it is 2.

*But I don't know how sequence for number 1 in seconds order looks like. I want just by number get the number of the same sequence in first "canonical" order.*

# Answer
> 2 votes
Aside from trivial cases, transforming lexicographic order indices from one ordering to another ordering can can rarely be done more efficiently than unranking the index using the original alphabet ordering, and then ranking the resulting sequence using the new alphabet ordering.

That works fine in this case, because after precomputation of a table of size $O(N^2)$ (which doesn't depend on the chosen ordering), you can rank and unrank an element of the lexicographic sequence with an arbitrary lexical ordering in $O(N)$ time. (The naïve proof-of-concept code I wrote does the ranking and unranking in $O(Nk)$ time, where $k$ is the size of the bracketing algorithm. But it should be possible to get rid of the $k$.)

The algorithm can be found in *Ranking and unranking of a generalized Dyck language and the application to the generation of random trees*, Jens Liebehenschel (1999). Liebehenschel's algorithm uses a fixed ordering but extending it to arbitrary orderings is straight-forward.

Liebehenschel's generalisation of Dyck languages allows the use of an arbitrary many-to-many relation between opening and closing symbols (although it requires that the set of opening symbols and the set of closing symbols not have common elements). Restricting the relationship to an isomorphism doesn't significantly simplify the algorithm.

---
Tags: algorithms, formal-languages, algorithm-analysis, pseudocode, order-theory
---


title: Recurrence $T(n) = T(n - \log n) + 1$

text:
# Question
Title: Recurrence $T(n) = T(n - \log n) + 1$
Given recurrence relation : $$ T(n) = \begin{cases} T(n-\log n) + 1 & \text{if } n \ge 1, \\ 1 & \text{otherwise.}\\ \end{cases} $$

To find asymptotic order of $T(n)$ i do as follow:

Suppose $n=\log m$ now :

$$T(\log m)=T(\log m-\log \log m) +1$$

$$\implies T(\log m)= T(\log \frac{m}{\log m}) +1$$

,but in this step i get stuck and i don't know how we can transfer relation to get easier relation.

# Answer
> 2 votes
Let $n\_0 = n$ and $n\_{i+1} = n\_i - \log n\_i$. Then $T(n)$ is one plust the minimal $t$ such that $n\_t \leq 1$.

Clearly $n\_{i+1} \geq n\_i - \log n$, hence $n\_t \geq n - t\log n$, implying that $T(n) \gtrsim n/\log n$.

In the other direction, as long as $n\_i \geq \sqrt{n}$, the sequence decreases by at least $\tfrac{1}{2} \log n$, hence it takes at most $2n/\log n$ steps to get down from $n$ to $\sqrt{n}$. After at most $4\sqrt{n}\log n$ steps, we get down to $\sqrt\[4\]{n}$; and so on. If we carefully count the steps, we see that $T(n) = O(n/\log n)$. Hence $T(n) = \Theta(n/\log n)$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: How does Command Z work through computer commands?
How does Command Z work through computer commands? What is the step by step computer commands that complete the process?

# Answer
You should really try to implement this yourself, and then it will become quite obvious.

You define a *stack* where you put all the *operations* that the user performs. Here are some examples:

* Close window
* Move file from one directory to another
* Create file
* Move icon on Desktop from $(x\_1,y\_1)$ to $(x\_2, y\_2)$
* Type a character
* Delete a character
* Copy to clipboard

All of these operations have reasonable "inverse" operations.:

* Close window → Reopen window
* Move file from A to B → Move it back to A
* Create file X → Delete file X
* Move icon from pos1 to pos2 → Move it back to pos1
* Type a character → Delete the previous typed character, etc.

When the stack contains "reversable" operations, the undo command simply *pops* the last operation off the stack and performs its inverse operation.

Some operations are not reversable, though, such as posting on the Internet, and permanently deleting a file.
> 1 votes

# Answer
There are two approaches:

1. For each action, implement a reverse action that exactly undoes its effects.
2. Before each action, save the current state and implement a general mechanism to support reverting to a previous state. So basically you keep a FIFO stack of states - or if you also have Redo, a list of states with a pointer to the current state; Undo and Redo move the pointer back and forth.

Approach 1 is infeasible in most cases. It requires actions to be reversible in the first place. So you probably want to go with approach two.

There may be multiple levels of application state. Undo/redo is supposed to apply to the application's subject matter (the work being done), not to the full application state.

A diagram editor I once worked on essentially had four levels of application state that I think most applications have:

1. Persisted work. In my case: what is saved to file; a diagram with some additional information. The application kept an in-memory object model for that and methods to write and read it to/from file. Undo only worked up to the last saved version. So after each save, the undo stack would be emptied.
2. Some extra info saved for undoing purposes. In my case, the editor allow the user to select shapes within the diagram; operations then applied to that selection, and undoing an operation would restore that selection, but it was not being saved to file.
3. Temporary intermediate states that only exist during multi-step operations. For instance, in a diagram editor, while the user is drawing, or moving shapes around, the diagram will pass through intermediate states that are not saved for undoing purposes.
4. Other aspects of the application state that aren't considered part of the subject matter being worked on. For instance, this diagram editor had several modes it could be in besides editing mode. Mode switches were not part of the undo/redo mechanism. It also had a range of configurable user preferences, e.g. for how to display the diagrams and whether to automatically apply certain operations to the diagram after an editing operation. Those preferences are a separate piece of state, saved separately, and undo/redo does not affect them.

In terms of Model-View-Controller:

1. The *model* is the subject matter being operated on; it is what is persisted to file, or to some other persistent medium.
2. The *controller* is what is used to modify the model, e.g. the diagram editor in my case; it defines operations on the model; it may adorn the model with some additional state that operations depend on (in my case, the current set of selected shapes); undo/redo is an operation within the controller, and operates on that adorned model.
3. The *view* defines what the user is currently seeing and is probably stateful, too, but state specific to the view is not subject to undo/redo.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Find the closest point in a point cloud in a near equivalent point cloud
I'm having a hard time wrapping my head around an algorithm, and not really sure if such a problem is known, common and possibly named, or if this is somewhat unique.

I have 2 different clouds of points (2D). I need to generate an index map from one to the other by proximity. Points that are closest should map to each other. This part isn't that hard.

The hard part is that each "to" point should only be used by one "from" point.

For example, let's say these are my "from" points: (`[x, y] // index`)

```
[
  [1, 10],  // 0
  [10, 10], // 1
  [19, 10], // 2
]

```

And these are my "to" points:

```
[
  [11, 10], // 0
  [9, 10],  // 1
  [10, 10], // 2
]

```

Then I would expect the following index mapping (`fromIndex: toIndex`)

```
{
  0: 1, // [1,10] -> [9,10]
  1: 2, // [10,10 -> [10,10]
  2: 0, // [19,10] -> [11,10]
}

```

In this example, all three new points are closest to `[10,10]`, but...

* The new point `[10,10]` (index 2) is zero distance from to old point `[10,10]` (index 1), so it just be assigned that index.
* The new point `[11,10]` (index 0) is 1 distance to the old point `[10,10]` (index 1), and 8 distance from the old point `[19,10]` (index 2). index 1 is closest, but since another point is closer, the second closest point is chosen (index 2).

Finding the closest point is easy, but how would I go about finding the closest point that doesn't also have another point that's even closer, and so it should find the next closest point, which also doesn't have another point closer to that, and if does find the next closest point which... (did I go recursive?)

And obviously this would be run on point clouds of large number (up to about a max of about 50,000 at the moment)

How would I go about developing this algorithm?

# Answer
I was able to come up with a solution, and I don't claim that it is good or fast, but it does seem to work:

1. Find the indices of the closest points in the two clouds, ignoring any invalid solutions. There will be some points that are referenced multiple times in this data.
2. Find all pairs that share the same destination indices and lock in the closest one of those.
3. Add the rest of the pairs to a set of invalid solutions.
4. Find the closest points again, ignoring any pairs previously marked invalid.
5. Repeat until each destination index is only used once.
> 0 votes

# Answer
This problem is known as Euclidean minimum cost perfect matching, I have linked a survey by Sayan Bhattacharya that contains various references to algorithms, both exact and approximations.

If you wish to solve this problem for $n \approx 50000$, I would skip the exact solutions entirely and go straight to the approximations.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Finding a particular path in weighted tree
> I have undirected weighted linear tree (path tree) with $n$ nodes ,and a weight function on edges $\omega: \mathbb{N}\to \mathbb{N}$, additionally given $k\in \mathbb{N}$, How we can find a path with lenght $k$ that have minimum number of edges in $O(n)$?

I think as follow: Run Bellman Ford for each node and then select a path with length $k$ and minimum number of edges. Unfortunately runtime $\omega(n)$.

# Answer
> 1 votes
The idea is to find, for each vertex $i$, the first vertex $j\_i \> i$ such that the distance $d(i, j\_i)$ between $i$ and $j\_i$ is at least $k$. Then, you can return the pair $(i, j\_i)$ such that $d(i,j\_i)=k$ and $j\_i-i$ is minimized.

This takes $O(n)$ time once you notice that, for $i\_1 \< i\_2$, $j\_{i\_1} \le j\_{i\_2}$. In pseudocode, where $w(\ell, \ell+1)$ denotes the weight of edge $(\ell, \ell+1)$:

```
i = j = 1
best_i = 0
best_j = n
d = 0

while i != n:
  if d<k and j!=n:
    d = d + w(j, j+1)
    j=j+1
  else:
    d = d - w(i, i+1)
    i=i+1

  if d == k and j - i < best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j

```

---
Tags: algorithms
---


# Question
Title: Need an adaptive algorithm for participant subgroups that balances repeated pairings
I want to build a utility that helps manage small groups of participants. It is an acting class setting.

For each exercise, the facilitator will usually have some number of participants get up to do a scene. Two is the most common, but sometimes 1 or 3 or 4. More than 4 is not common.

I want the utility to have a list of participants and then the facilitator can just ask it for a specified number of people. E.g. 2.

The utility should do a good job of balancing combinations. For example, let's say there are 5 participants, A, B, C, D, E. If A and B work together, then ideally they should have also worked with C, D, and E before working together again.

I know how to manage this well if it's always just pairs. You can create, in advance an ordered list of all the pairings.

But once you add the possibility of other changeable group sizes, I don't know how to manage it.

My starting point is to keep track of how often each participant has worked with every other participant. So, I could look at A and know how often she has worked with B, C, D, and E, and then if A is due to get up, pair her with the person/people she has worked least often with.

The problem with this, is that it can lead to situations where the last remaining unmatched pair have already worked together.

As a simple counter-example: Say I have 6 participants - A - F. In the first lot of exercises, these are the pairs. AB CD EF. Then next round, I might (if not thinking) do AC, then BD, but now I'm left with E and F again. This is not ideal, and is what I need the algorithm to avoid.

I think part of the solution should be that everyone should get a roughly even number of turns. So, at any given point, we have a group of participants who have had fewer turns that the others, and we need to balance them out so that they don't work with people they've worked with (where possible) or at least with the people they've worked with least, and it needs to anticipate the possible remaining combinations and avoid duplication there too. Part of the complexity is that you don't know in advance what group sizes will be used for the remaining groups.

Does this type of algorithm / problem set have a specific name? Are there known algorithms for solving it?

(As an extra complication, there is the possibility of a participant having to leave unexpectedly, or an extra participant who arrives late, but that might be for later)

This is my first time asking here, so I hope I've posted this appropriately. Thanks for your patience and assistance!

# Answer
It sounds like the stakes are low, so I would suggest something simple and "good enough", rather than looking for fancy algorithms that will be guaranteed to give the optimal solution. One approach is to take the approach you're already considering, but break ties randomly. This seems like it may do well enough in practice: it is possible to get into a bad situation, but the randomness might make that unlikely; and this might occasionally have one student participate a little more than they otherwise would, but that I'd expect that to average out over time and so maybe it isn't a big deal.
> 1 votes

# Answer
For anyone who may be interested, here's what I came up with.

I came up with a way to score a given subset of participants. The scoring is made of 4 parts.

1. scTogS = Togetherness score for the subset.
2. scTogO = Togetherness score for the other participants (those NOT in the subset).
3. scTurns = Score based on how many turns in total the members of the subset have had.
4. scRecent = Score based on how many members of the subset were in the most recent subset.

The "togetherness" score is the sum of how many times each member of a given set has played with other members of that set.

Each part of the score is given a weighting, so that the total score is:

`total = scTogS + k1 x scTogO + k2 x scTurns + k3 * scRecent`

A LOWER total score is a preferable subset.

What this scoring does is to favour combinations that:

1. are more diverse;
2. allow more diversity in the remaining group;
3. give participants a fair number of turns;
4. avoid people being up twice in a row.

Each time I need to provide a subset, I take one of two options depending on the total number of possible combinations.

For \<= 2000 combinations: Consider all combinations.

For \> 2000: Randomly choose 200 subsets, favouring those who have not played recently and who have played less often.

Evaluate the score for all subset combinations. Randomly select a subset from those with the lowest-equal score and return it.

I've run various scenarios and looked at the "fairness" of the results, tweaking the constants to get a good balance of people playing with a good variety of others, and also getting to play roughly an equal number of times.

Not sure how common this sort of problem is, but I thought these ideas might be useful to someone else.

Also open to any improvements to the overall idea! Thanks.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Language equivalency for modified CFG closed over intersection
Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both between CFGs and between other CFG+'s.

Consider non-context-free language: $$ \\{ a^nb^nc^n|n≥0\\} $$

With the addition of intersections, consider the following "CFG+": $$ S\rightarrow AB\ \\&\ CD $$ $$ A\rightarrow aAb\ |\ \epsilon $$ $$ B\rightarrow cB\ |\ \epsilon $$ $$ C\rightarrow aC\ |\ \epsilon $$ $$ D\rightarrow bDc\ |\ \epsilon $$

As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.

It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?

# Answer
It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar.

Here is more quote from that article on Wikipedia.

> The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.

Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.

---

A related problem is the expressive power of intersections of context-free languages.

An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\\{a\_1^{n\_1} a\_2^{n\_2} \cdots a\_{d}^{n\_{d}} b\_1^{n\_1} b\_2^{n\_2} \cdots b\_d^{n\_d} \mid n\_1,n\_2,\ldots ,n\_d\ge 0\\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.
> 4 votes

# Answer
Every such grammar will describe a context-sensitive language: every context-free language is also context-sensitive, and context-sensitive languages are closed under intersection.

I don't know if this describes a proper subset of the context-sensitive languages, or if every context-sensitive language can be formulated in this way.
> 0 votes

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


# Question
Title: Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B
We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the source node $s$ and $v$ belongs to the same side of the cut as the sink node $t$.

My initial idea was to run Ford-Fulkerson to get the residual graph $G\_f$ at the end. Then use that to find all nodes reachable from $s$ in $G\_f$ (call this set $A$) then $B=V-A$ where $V$ is the vertex set. Then $(A,B)$ is a min s-t cut and if $u \in A, v \in B$ output true, else false.

But since there may be more than one min cut I'm a bit stuck.

# Answer
> 1 votes
The easy solution is to add an edge between $s$ and $u$ with infinite weight and $t$ and $v$ with infinite weight.

Note though that this doesn't mean that $s$ and $u$ will be *connected* in $G\[A\]$.

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


# Question
Title: If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences
Question on operating system If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences

# Answer
Assuming a monolithic kernel like Linux, there just are no "kernel programs", every in-kernel thread is just a function running in the kernel's address space. If you copy that and place it in a userland program (given the correct environment in terms of available data structures and functions to call) it will work fine as long as it doesn't invoke any privileged operations. Any of those will give some sort of exception.

Placing a userland program into the kernel would mean to add a lot of infrastructure provided by the operating system: in C's terms, standard input and output, the contents of the standard C library and any others in use. Using a snippet of userland code in the kernel will work just fine, as long as any infrastructure/environment called upon is provided.

Kernel code and userland code are the exact same instructions (but the kernel has access to some privileged operations and registers that userland can't use).
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Problem in understanding big-O notation and similiar
I am trying to understand the concept of big-O notation problem and came through this problem. Can you tell me how could

> $$O(n) = 1 + \Theta(1/n)$$

# Answer
> 3 votes
$O(n)$ is the set of all functions $f(n)$ such that, for sufficiently large $n$ and a positive constant $c$, $f(n) \le cn$.

$1+\Theta(\frac{1}{n})$ is an abuse of notation that denotes the set of all functions $h(n) = 1+g(n)$ such that, for sufficiently large $n$ and a two positive constants $c\_1$, $c\_2$, $\frac{c\_1}{n} \le g(n) \le \frac{c\_2}{n}$.

Then the claim is clearly false since, e.g., the function $h(n)=n$ belongs to $O(n)$ but it does not belong to $1+\Theta\left(\frac{1}{n}\right)$.

# Answer
> 1 votes
The basic way to understand notation like $f(n) = O(g(n))$ is that the equals sign is really wrong, it should be something like $f(n) \in O(g(n))$, the function $f$ belongs to a set of functions. That set is the set of functions $h$ such that for some constants $c \> 0$ and $n\_0$ it is $h(n) \le c g(n)$ whenever $n \ge n\_0$ (this presumes non-negative functions, sprinkle absolute values over all if not). The equals sign is just too entrenched in usage to be changed (not that there haven't been tries).

A rule of thumb is that the right hand side is a less precise statement (in the $f(n) = O(g(n))$ case, a single function as opposed to a set of functions).

A useful extension is to say e.g. $f(n) = n^2 + O(g(n))$ to state that there is a function $h$ so that $f(n) = n^2 + h(n)$ where $h(n) = O(g(n))$. One reason why we use $=$ instead of $\in$ is that it makes sense in sequences like:

$\begin{align\*} 5 n^2 + 3 n + 4 &= 5 n^2 + O(3 n) \\ &= 5 n^2 + O(n) \\ &= O(n^2) \end{align\*}$

Note that $O(n) = O(n^2)$, but **not** $O(n^2) = O(n)$.

The notation $f(n) =\Theta(g(n))$ says $f$ is such that there are constants $n\_0$ and $c\_2 \ge c\_1 \> 0$ so that if $n \ge n\_0$ then $c\_1 g(n) \le f(n) \le c\_2 g(n)$.

Intuitively, $n = 1 + \Theta(1/n)$ means that $n$ doesn't stray too far from $1$, and the difference goes down as $n$ increases. This is clearly nonsense.

Hildebrand's "A Short Course on Asymptotics" elaborates quite a bit on this (and related) notations and their manipulation.

---
Tags: asymptotics
---


# Question
Title: When does kernel accessing virtual memory cause problems
I'm working with the CPU Pintos and have a question that is:

In which situations can the kernel accessing the data in virtual memory via a pointer lead to problems? And how do you avoid them?

I know that the kernel can access the virtual memory via pointers to the stack, but don't understand when errors may occur.

# Answer
Same as with any program that uses pointers: dereferencing one that points nowhere sane **will** give grief. If in the kernel of the system, with little or no protection against accidents (and nobody who can clean up the mess afterwards), it is much worse.
> 1 votes

# Answer
When you try to access data from a user space program, what happens is that the hardware tries to translate your logical address into the physical address of RAM, and then access the data if possible. If the data is not in RAM, then the CPU will switch to code in the OS that tries to load the data into RAM.

Mostly this is possible for code in the kernel as well. However, there is some data that absolutely MUST be in RAM: That is the code for loading virtual memory from disk to the RAM, and all the data that keeps track of what is where in memory. If the code loading data from disk into RAM is on the disk and not in RAM, then obviously you can't execute it.

Many CPUs will produce a fatal error in that situation.
> 1 votes

---
Tags: cpu, stacks, c
---


# Question
Title: Converting along regular expression to NFA
I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):

(0+1+ϵ)4+(11100+ϵ)r(0011100r)\*(00111+ϵ)

r=11+(110+ϵ)s(0110s)\*(011+ϵ)

s=(0+10)\*(1+ϵ)

How should I convert this into an NFA? Please explain the steps behind it as well!

# Answer
What you need is the Berry-Sethi algorithm, constructing the Glushkov's automaton.

However, for your problem, I'd consider constructing directly a DFA with $10 = \begin{pmatrix}5\\2\end{pmatrix}$ states corresponding to words of size 5 containing exactly two zeros, and a sink state (and maybe some other states for the begining of the reading).

The Glushkov's automaton on your regular expression will be very big.
> 2 votes

---
Tags: finite-automata, nondeterminism
---


# Question
Title: Does my "hollow list" structure exist already?
I came up with an implementation in c for arrays which can be extremely large yet only use an amount of memory proportional to how much data you have written to it. What I want to know is if there is a name for this kind of list or structure. Here is my code in C for the structure and example use:

```
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

int main(){
    int a = 221;
    int b = 222;
    int c = 9;
    int d = 89;

    hollow_list h;
    h = hollow_list_create(30);

    hollow_list_write(&h, 221999999, &a);
    hollow_list_write(&h, 9999, &b);
    hollow_list_write(&h, 22999999, &c);
    hollow_list_write(&h, 1, &d);

    printf("%d\n", *((int *) hollow_list_read(&h, 221999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 9999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 1)));
    printf("\n");
    printf("\n");
    printf("\n");
    printf("%d\n", a);
    printf("%d\n", b);
    printf("%d\n", c);
    printf("%d\n", d);

    c = 56;
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
}

```

These lists seem to be really useful alternatives to linked lists, and fast too: the worst case scenario for a read or write to a list is O(log n) for a list of n elements. I'd be surprised if this kind of structure didn't already exist, but I would simply like to know what it is called so I could refer to it by it's proper name haha.

# Answer
> 3 votes
This is a sparse array data structure, but I haven't seen this exact data structure before. It looks like your code builds a balanced binary tree, but with a particularly clever representation in memory.

One difference between other balanced binary trees is that the running time of your approach is $O(\lg m)$ where $m$ is the largest index written, whereas other balanced binary tree data structures (e.g., red-black trees) have a $O(\lg n)$ running time where $n$ is the number of indices written to. Since $m \ge n$, in principle your approach might be slower if $n$ is small (few elements have been written) but the indices are large. However in practice I don't expect this to make much difference, ordinarily.

# Answer
> 2 votes
I think that what you have created is a bitwise trie:

> Bitwise tries are much the same as a normal character-based trie except that individual bits are used to traverse what effectively becomes a form of binary tree. Generally, implementations use a special CPU instruction to very quickly **find the first set bit in a fixed length key** (e.g., GCC's \__builtin\_clz() intrinsic)

Emphasis mine. Your code seems to be doing exactly that:

```
unsigned int bit_checker;
bit_checker = 1<<(l->size - 1);
int i;
for(i = 0; i < l->size; i++){
    if(bit_checker & index){
        if(l->written[i] == true){
            return hollow_list_read(l->children + i, bit_checker ^ index);
        } else {
            return (void *) 0;
        }
    }
    bit_checker >>= 1;
}

```

---
Tags: data-structures
---