# Question
Title: How does a File System handle an internal edit to a file?
When you edit information in a file, but you add in more information than was already present, how does the file system handle it without an overflow into the next section of the file?

Here's an example. Consider having statements 1-12 in a 512-byte block, and you had statements 13-24 in the next 512-byte block. \[Image 1\] These blocks are both part of the same file. If you edited the first block, so you add another few New Statements \[Image 2\] past statement 12, this would overflow into the next block (statements 13-24). How would this condition be handled? Through shifting all the statements ahead of the added statement forward, or putting the new edit in a completely separate new block?

(sorry if the pictures or wording are a bit improper; this is my first time)

# Answer
Filesystems typically don't handle internal edits to files as you describe them. When you edit a program file, a text editor will pull the whole file into memory, allow you to make modifications to a buffer and then write the whole thing back out to disk. Actual file I/O operations are usually quite limited by the operating system, e.g. overwrite existing file contents, truncate the file to a smaller size discarding what's beyond EOF, and appending to the file.

*Text editors* manage the business of allowing arbitrary insertion and deletion of lines and blocks of text. These programs use an assortment of data structures, from arrays of lines to gap buffers to more elaborate structures, depending on the editor. An old Blogspot article describes how a few popular text editors work internally; I commend you to it and to the source code of the many open-source text editors available if you wish to learn more.
> 1 votes

# Answer
In principle this might depend on the filesystem, but I'll give the practical answer for every filesystem I've seen:

Filesystems store bytes, not statements.

If you insert some bytes into the middle of a file, it's like overwriting (so some of the data gets shifted forward) -- it doesn't add a new block with just the inserted data, because that would require variable-size blocks. Filesystems typically use fixed-size blocks.
> 0 votes

---
Tags: filesystems
---


# Question
Title: Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not
It is known that the halting problem is decidable for every fixed $M\_0$ Turing machine and every fixed $w\_0$ input.

My related question would be the following: is it true that for every fixed $M\_0$ Turing machine and every fixed $w\_0$ input, an $M\_{M\_0,w\_0}$ Turing machine can be constructed for which the possible inputs are $(M, w)$ machine-input pairs, and for the $(M\_0, w\_0)$ pair, the output is "1" if $M\_0$ will halt on $w\_0$ and "0" if $M\_0$ will not halt on $w\_0$? ($M\_{M\_0, w\_0}$ can give false answers for other pairs, it is not demanded that it has to run correctly for every $(M, w)$ pair.)

# Answer
Since $M\_0$ and $w\_0$ are fixed parameters of the problem, the answer is yes: for every fixed $M\_0$ and $w\_0$, there exists a Turing machine $M\_{M\_0, w\_0}$ (depending on $M\_0$ and $w\_0$) such that, for the input $(M\_0, w\_0)$, $M\_{M\_0, w\_0}$ returns $1$ if $M\_0(w\_0)$ halts and 0 otherwise.

In particular one such Turing machine $M\_{M\_0, w\_0}$ must be one of the following two machines:

* $M'\_1$: Write $1$. Halt.
* $M'\_0$: Write $0$. Halt.

If, instead, you are looking for an algorithm that takes $M\_0$ and $w\_0$ as input and outputs a machine $M\_{M\_0, w\_0}$ with the above property, then you are out of luck: there is not such algorithm in general (it might exist if you restrict the set of input machines $M\_0$). Suppose that such an algorithm (i.e., Turing machine) $A$ existed, then it would allow to solve the halting problem:

* Given $M\_0$ and $w\_0$, compute $M\_{M\_0, w\_0}$ by simulating $A$ on input $(M\_0, w\_0)$.
* Simulate $M\_{M\_0, w\_0}$ on input $(M\_0, w\_0)$. By definition of $M\_{M\_0, w\_0}$ this step requires finite time.
* Return "yes" if the output of $M\_{M\_0, w\_0}( (M\_0, w\_0) )$ was $1$, otherwise return "no".
> 1 votes

---
Tags: turing-machines, computability, halting-problem
---


# Question
Title: Static type analysis with dynamic scoping?
Both in school and out, I have only ever encountered dynamic scoping paired with dynamic typing. Is there any published work (even if just academic, not yet implemented in a "real" programming language) on doing static type verification with dynamic scoping?

It seems to me that it should be possible if the type checker can build a static call graph for the program, and then check that all accessed variables are defined somehow in all possible traversals, and unify types between different traversals that lead to the same access point. While doable, though, that's potentially a very expensive operation, so I'd be interested to see if there is any way to significantly optimize it.

For reference, Scala seems like a decent proof-of-concept for some first steps towards such a dynamically-scoped type system with its concept of "implicit arguments"; it just requires that all usable edges in the dynamic call graph through which dynamically-scoped values can pass be manually type-annotated by the programmer, rather than assuming that all edges in the call graph are usable and having the compiler figure out the types automatically.

# Answer
> 3 votes
There is a paper titled Implicit Parameters: Dynamic Scoping with Static Types that discusses just such a system.

The implement a slightly different system from Scala under the name "implicit parameters". By having compiler automatically generate implicit parameters in any function that calls other functions with implicit parameters the problem becomes nearly identical to standard type inference. Additionally, since these implicit parameters are still part of each functions type signature they propose a syntax for declaring most of a functions signature, while still allowing the compiler to determine the types of any implicit parameters.

---
Tags: programming-languages, type-checking
---


# Question
Title: Worst-case expected running time for Randomized Permutation Algorithm
I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a random integer between the numbers x and y, provided they are positive integers and y \>= x.

The algorithm is given by the following pseudo-code:

```
1.  if (N <= 0) {
2.     return null
3.  } else {
4.     A := new int[] w/ size N and all cells initialized to 0
5.     a[0] := randInt(1,N)
6.     for (i := 1 to length(A)-1) do
7.        boolean rInA := True
8.        while (rInA) {
9.           rInA := False
10.          int r := randInt(1,N)
11.          for (j := 0 to (i-1)) do
12.             if (r = A[j]) {
13.                rInA := True
14.             }
15.          }
16.       }
17.       A[i] := r
18.    }
19. }
20. return A

```

My understanding of the algorithm is as follows:

The outermost for-loop will run N-1 times and for each of those iterations a random number is generated and then compared to all the previous cells of A that have been visited in previous iterations. If any of the those cells contain that randomly generated number then that number cannot be used and a new number is randomly generated (in the next iteration of that nested while-loop). This new randomly generated number is then, like before, compared to all the previously visited cells in A to check for duplication. This continues until randInt(x,y) generates a random number that is not already in the first i cells of A.

This leads me to believe that the Worst-case expected running time of the algorithm is something like: $\sum\_{i=1}^{N-1}(\alpha i)$

Now the $\alpha$ here represents the effect the while-loop has on the running time and is the point of uncertainty for me. I know that in the first iteration of the outermost for loop its unlikely that randInt will generate the one integer that A already contains (1/N I believe) so that inner-most for-loop is likely to only execute once. However, by the last iteration (of outer-most for-loop) the probability that randInt generates one of the N-1 integers already in A is $\frac{N-1}{N}$ so because of the while-loop its likely that the inner-most for-loop for **that** iteration (of the outer-most for-loop) will execute more like n times.

How can I use the probability introduced into the algorithm by randInt to calculate the algorithms run-time?

# Answer
> 1 votes
Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$. You could do this by initializing a (1-indexed) boolean array $used\[\cdot\]$ of length $n$, and setting $used\[x\]$ equals true whenever you set some $A\[i\]=x$.

Now the question is how many times may $rand()$ be called in the worst case. Actually, the way the algorithm is set up right now, the *worst* case is $+\infty$; this is because it's not learning from any of its bad choices of $r$. For instance, if it selects $5$, when $5$ was already in $A$, then the smart thing to do would be never to guess $5$ again. There are ways to achieve this; so if you had some method that never repeated guesses, then you can get $O(n^2)$ worst case runtime.

If you are interested in *expected* runtime, then you can calculate the expected number of times $r$ is recalculated in any given step: at step $i$, there are $n-i$ good choices, for a success probability of $\frac{n-i}{n}$. The expectation for number of tries to get a first success in a bernoulli variable with probability $p$, is $\frac{1}{p}$. Then if you sum $\frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+\cdots \frac{n}{1}$ you have asymptotic $O(n\log n)$. This is basically the coupon collector's problem.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, probability-theory
---


# Question
Title: exponentially different running times random-access machine (RAM) vs Turing machine
I propose a simple polynomial algorithm for the following problem. Given $m$ integers each one stored on $n$ bits, output the integer that appears the most often.

1. Reserve a memory area with $2^n$ slots/registers/locations/cells, each cell being long enough to store the number $m$. This requires constant time because we do not initialize/touch the cells. If you agree with this, skip to step 2. Otherwise, check the following four points.
    * One could easily be tempted to read "reserve a memory area" as "allocate a memory area". Actually, the memory allocation operation is an invention/complication of real multi-tasking machines where programs can "fight" for memory. If I consider some (Random Access Machine) RAM machine that only knows running my algorithm, I can state that the algorithm can simply use the whole memory. Thus, it is enough to reserve (read "put aside" not "allocate") the first $2^n$ cells for a an array with $2^n$ elements. The next memory cells are simply used for other variables.
    * To be more precise, I consider running my algorithm on a RAM-TM (Random Access Memory-Turing Machine) that is multi-tape TM with a memory and an index tape. Given a number written on the index tape, the RAM-TM takes constant time to move the head of the memory tape to the location indicated on the index tape. We also allow the RAM-TM to have a few other tapes for easily doing arithmetics. The RAM-TM has no notion of memory allocation. This seems to be a simplification of the various (Transdichotomous or word) RAM machines out there.
    * Even if I must confess I do not really know the exact technical details of all theoretical machines RAM (or RASP), it **is** possible to work with an exponentially-large memory area and yet use only a polynomially large number of cells and my algorithm is **not the first** doing this. This also happens in the binary search algorithm over a sorted array: $n$ cells but only $O(log(n))$ time complexity. This scientific paper introduced a data structure that uses a large memory area but has constant time access, see also the answer of *zotachidil* to this question. My algorithm could work with this data structure instead of explicitly reserving space.
    * see Ps 1.
2. Go through the $m$ numbers in the input and for each one of them $x$ assign $\[x\]=0$, where $\[x\]$ is the memory slot/location number $x$ in the above reserved memory area.
3. Go through the $m$ numbers in the input and for each one of them $x$ assign $\[x\]=\[x\]+1$.
4. Take the first number $x$ in the input and assign $outVal=x$ and $maxFreq=\[x\]$.
5. Scan again the $m$ numbers and for each number $x$ perform: if $\[x\]\>maxFreq$, set $outVal=x$ and $maxFreq=\[x\]$.
6. Output $outVal$.

The algorithm has time complexity $O(mn)$ assuming $n\hskip 0.7mm \not \hskip -0.7mm \ll m$ at least on the RAM-TM (see ps 2.), i.e., linear. It is certainly not the only algorithm to solve the problem, but I do not know any other linear algorithm using polynomial memory.

However, the **big problem** is that the algorithm would require exponential time in a Turing machine, no? Does this contradict one of the Extended/Complexity-Theoretic Church–Turing Theses? The section "Variations" of the Wikipedia article on the Church–Turing thesis states that "polynomial-time overhead and constant-space overhead could be simultaneously achieved for a simulation of a Random Access Machine on a Turing machine \[55\]", where \[55\] is "C. Slot, P. van Emde Boas, On tape versus core: an application of space efficient perfect hash functions to the invariance of space, STOC, December 1984". Something seems inconsistent. Any help would be **greatly** appreciated.

ps 1. A real-machine argument for the fact one can allocate $O(2^n)$ bits in constant time. Notice I did not say the $2^n$ cells are initialized to some zero values. In a programming language like C this should be achieved by an instruction *malloc* instead of *calloc*. In my comment to D.W.'s answer, I provide a reference for a real-life memory allocator that "performs the allocation/deallocation in constant time". However, D.W. seem to reject this argument, claiming the above "constant time" is calculated by ignoring the fact that we can have $n\to \infty$ since in practice $n$ does no go to $\infty$, if I understood the response. As for me, it is hard to believe this "constant time" is actually $O(2^n)$, constant time is really far from $O(2^n)$. I would be surprised to see such large approximations in a paper published by Real-Time Systems.

ps 2. Not really essential, but a technical edit: because of Step 5, the complexity of the algorithm should be $O(nm+m\cdot log(m))$ on a RAM-TM and not $O(nm)$, which is relevant only if $n$ is very very small compared to $m$.

# Answer
> 4 votes
Your algorithm involves an array of length $2^n$. Allocating an array of length $2^n$ takes $\Theta(2^n)$ time. Consequently, the running time will be $O(m+2^n)$.

Alternatively, you can represent the array in a sparse way using a self-balancing binary tree data structure. Then each access to the array takes $O(\log m)$ time, so the total running time of your algorithm is $O(m \log m)$ (assuming we can treat $n$ as a constant).

Alternatively, you could use a hash table to replace the array. Then the expected time per access is $O(1)$ if you use a suitable hash function, so your algorithm will have expected running time $O(m)$ (again, treating $n$ as a small constant). However, this is the expected running time, not the worst-case running time; the worst case could be as bad as $O(m^2)$.

You seem to have the idea that you can allocate and work with an array of exponential in constant time. I don't think that's correct. What *is* true is that you can *simulate* such an array, at the cost of a logarithmic increase in the running time (using the methods I described above). If you care only about whether the algorithm is polynomial-time or not, you can ignore the logarithmic increase, but if you care about the concrete running time, you can't ignore it.

And if you really care about the precise running time, you should probably specify the model of computation (e.g., transdichotomous model, etc.). For instance, in the transdichotomous model, if $n$ is guaranteed to be at most the word size (i.e., all of your integers fit within a word), then yes, your algorithm works and runs in linear time -- you can allocate/reserve memory for $2^n$ cells without difficulties. However if $n$ is larger than the word size, you can't. So, giving a precise answer to your question requires specifying a particular model of computation.

Related: Saving on array initialization.

# Answer
> 2 votes
I would argue that this is not an exponential algorithm on either Random Access Memory or a Turing Machine. On a Turing Machine you could compute as follows (assuming you have a symbol set and state set large enough to cover all of the integers. If not, you are going to have to do a more complex comparison, but that will only be a linear slowdown): Along the tape, alternate cells are the integers, and then counters next to them.

```
For each integer in the list:
    Iterate along the tape, and compare each cell with the current integer
    If it is the same, increment the relevant counter, otherwise move along the tape.
Once you have completed this for all of the integers, iterate along the tape again, and look for the highest counter. Output the integer next to the highest counter

```

This algorithm will take $4m$ steps per integer (two out and two back for each integer currently on the tape), multiplied by $m$ integers. It will then take $2m$ time to compare all of the counters, and $2m$ to return to the start to output the answer. This is a total of $4m^2+4m$, which is $O(n^2)$ By using RAM, either a hashtable or an exponential amount of memory can be used. For a hashtable, it is a worst case $O(n^2)$ algorithm, and best case $O(n)$, and with exponential memory it is $O(n)$.

Therefore, in answer to your question, no, it does not have to take exponential time on a Deterministic Turing Machine. Your implementation does, but only because you opted to use an exponential amount of memory. By using RAM, the algorithm can be reduced to $O(n)$ given sufficient memory, or $O(n^2)$ with reasonable limits.

Edited to answer both the comments and the edited question:

While the algorithm you use allocates an exponential amount of memory, as you correctly point out it does not write to it. Because of this, the TM can simulate the algorithm without needing the same number of memory locations. Where I have above written the integer to the tape, that is effectively a pointer to your exponential amount of memory. In the interests of simplicity I did not have my array in order, however had I inserted into the middle of the array, rather than appending new values. (at a cost of $O(n)$), then my algorithm would exactly simulate yours.

To demonstrate this difference, consider the following algorithm:

```
For an input of length n:
    write a 1 to the 2^nth cell
end

```

By your definition, this algorithm is exponential, because the TM would have to move out $2^n$ cells to write. When running this in RAM, it would take constant time. Crucially however, ONLY the $2^n$th cell has been written to, and the rest are undefined. For this reason, the TM could simulate it by writing a 1 to the first cell and ending. I would argue therefore, that this algorithm is constant time.

Based on the above logic, although your algorithm reserves an exponential amount of memory, it only ever uses a linear amount of it (the total amount required to transcribe the input). For this reason, it is not required for the TM to allocate an exponential amount of memory, it can also use a linear amount. This will take either $O(n^2)$ or $O(n^3)$ depending on whether or not you want the array in order.

In answer to your second point, yes, I sidestepped the issue of the amount of time taken to compare integers. I did this by assuming that the symbol and state set was large enough to accomodate the integers. If you ignore this assumption, there is a further $n^2$ slowdown. (I would note however that it's $n^2$ on the length of a single integer, not on the length of the input as a whole.)

In conclusion, depending on precisely how you simulate the algorithm, and what you define to be part of the machine vs variable with the input, the TM algorithm can range from $O(n^2)$ to $O(n^5)$, but is definitely polynomial.

# Answer
> 1 votes
So this is what I consider as the pitfalls of abstracting physical computation into a purely mathematical theory. First, to answer your question, by extended Church-Turing, when you implement your algorithm on a *physical* RAM machine, it will run in exponential time.

There are some subtle points here.

1. To access a uniformly random memory cell among all $2^n$ cells (of constant size, say, of bits), assuming general relativity and quantum mechanics, there is no way you can do this in $o(2^{n/3})$ time (proof left as exercise, hint: use concentration of volume).
2. There are no contradictions because when you reduce a RAM program with time $T$ and space $S$ into a Turing machine, the running time of the Turing machine will be ${\sf poly}(S, T)$. So extended Church-Turing thesis is robust as long as you don't use superpolynomial space. See also: Strongly polynomial time v.s. weakly polynomial time, although this particular example is not a typical example of weakly polynomial time.

To conclude, extended Church-Turing thesis really considers *reasonable* computational models, and the seeming contradiction really stems from the fact that you are making an *unreasonable* assumption that RAM access only costs constant time.

P.S. You can also consider similar "speed-ups" in the circuit model, in fact, you can prove that circuits can decide everything (including undecidable problems) in as much time as one needs to read the input.

# Answer
> 0 votes
Thanking everybody for the responses, I come myself with a solution that satisfies me at 99.99%, using arguments from your replies. The main idea is that the Turing Machine (TM) **can** simulate my RAM machine in polynomial time, provided an initialization axiom.

To be very clear, I can run my algorithm in $O(nm+m\log(m))$ time on a RAM-TM (Random Access Memory-Turing Machine). The RAM-TM is multi-tape TM with a memory and an index tape. Given a number written on the index tape, the RAM-TM takes constant time to jump the head of the memory tape to the location indicated on the index tape. We also allow the RAM-TM to have a few other tapes for easily doing arithmetics, and an input tape. We consider an additional program tape that represent instructions. For instance, `scan, $+1$` could mean ''scan the input tape and for each number increment the memory content pointed by the number''. Incidentally, my algorithm also runs in polynomial time on a Transdichotomous RAM machine with word size $w=n+1$. I think D.W. agrees on this (last paragraph of the response).

A Turing Machine (TM) can simulate my RAM-TM in polynomial time, circumventing the fact that my RAM-TM has *infinite* memory, since the memory tape is infinite. Consider a *whole execution* of the RAM-TM consisting of running algorithms/programs $A\_1$, $A\_2$, $\dots$, $A\_p$, where $A\_p$ is my algorithm. If the total time complexity of all these runs is polynomial in $p$ and in the total input size of $A\_1$, $A\_2$, $\dots$, $A\_p$, then the TM can simulate the whole execution in polynomial time.

We simulate the whole RAM-TM execution using a 2-tape TM, knowing that a 2-tape TM can be simulated in quadratic (hence polynomial) time by a TM. We use the second tape to store the accessed memory cells of the infinite RAM-TM memory. Since the RAM-TM execution is polynomial, the number of accessed cells is polynomial. We can simply use the second tape of the TM to store all accessed memory locations, each location together with its content. Whenever any of the algorithms accesses memory content $\[x\]$ on the RAM-TM, the 2-tape TM can scan the second tape in polynomial time and search for index $x$ and retrieve the associated content $\[x\]$.

I said I am satisfied at 99.9%, because I think we still need an **initialization axiom**. It is not clear what the 2-tape TM should do when it finds no content associated to some index $x$, i.e., if the RAM-TM asks to retrieve an uninitialized memory cell. We use the following axiom: when the RAM-TM is first turned on, the memory tape contains only zeros. This does not mean that my algorithm $A\_p$ can rely on the fact that all uninitialized cells are 0. From the viewpoint of $A\_p$, uninitialized cells have an undetermined value, due to the previous programs $A\_1$, $A\_2$, $\dots$, $A\_{p-1}$.

*Without this axiom, the RAM-TM can not be simulated* as far as I can see. Imagine a RAM-TM that has the following memory state when first turned on: the infinitely many bits of the memory tape contain the binary digits of $\pi$. It can solve the following problem: given an integer $n$ as input, return the $n^\text{th}$ digit of $\pi$. It can do this by simply returning $\[n\]$ in $O(\log(n))$ time, where it needs $O(\log(n))$ to write $n$ on the index tape. If we try to simulate this using some multi-tape TM with $\pi$ on one of the tapes, it would need $O(n)$ time to go to the $n^\text{th}$ location on that tape. $O(n)$ is exponential compared to the input size $log(n)$.

---
Tags: complexity-theory, algorithm-analysis
---


# Question
Title: If there is any research on Goal Based Programming (GBP)?
The more I think about programming and optimization, the more I think "why not just specify a goal and have the program figure out the optimal solution to it".

I am familiar with basic "optimization problems" such as finding the best fit line to a curve, or gradient descent sorts of things. What I'm talking about is way more complicated than that.

What I'm imagining is to say something like "An HTTPS server exists", and for the system to figure out how to build one. Obviously given *just* that info, it's not enough. It would require human-level training in programming and understanding concepts and everything.

But my question is, what could you do to build a system to support such a "goal statement"? What would the key parts be?

It seems at first, the simplest goal is "Action x is performed". This is required to change the current world into the desired (goal) world. For example, `"Add" is performed on 1 and 2` is a goal stating that the "add" function is applied to the two arguments. It seems that from this foundation, you can build up higher and higher levels of abstraction to the point where you could then say "An HTTPS server exists". But this HTTPS server is a *structure*, not an *action*. So you need some way to have some intermediate goals that transcribe goals into (not actions, but) structures. Perhaps, `The result of x operation exists` is a simple transformation between the two.

But then I'm stuck haha. What do the goals look like in the intermediate realm? Has anyone done any research into this area? Searching doesn't yield much, though it brings up a book Goal programming and extensions which I might have to purchase.

# Answer
Yes. The research area is known as program synthesis. You can find hundreds or thousands of papers on the subject. (You might also be interested in declarative programming.)

What you're describing is *way* beyond the state of the art. It'd be really cool if we could do something like that -- but we're a long long way away from knowing how to build that.
> 2 votes

---
Tags: mathematical-programming, domain-specific-languages
---


# Question
Title: Is there any correspondence between SUM type in type theory and arithmetical summation?
Is there any correspondence between the coproduct(sum) type in type theory and arithmetical summation?

For example what does 3+4 or x+6 mean in type theory?

# Answer
The arithmetic notation in type theory is motivated by the behaviour on sets, where the disjoint union $A + B$ has $|A| + |B|$ elements; the cartesian product has $|A| \times |B|$ elements; and the set of functions $B^A$ has $|B|^{|A|}$ elements. Sum, product and function types satisfy many of the usual identities you expect of arithmetic (although typically up to isomorphism, rather than equality).

The paper Objects of Categories as Complex Numbers by Marcelo Fiore and Tom Leinster explores this in some detail, though it helps to have a little experience with algebra or category theory.

Sometimes a natural number $n$ will denote a type with exactly $n$ terms in any context (analogous to a set with $n$ elements). In this setting, $3 + 4 \cong 7$ as types. $x + 6$ isn't well-formed without placing $x$ in some context.
> 3 votes

---
Tags: type-theory, category-theory
---


# Question
Title: Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci
In a series graph, each edge $e\_i$ exists with probability $p\_i$. And if you want to examine the existence of edge $e\_i$, it will cost you $c\_i$. I want to test the connectivity between source $s$ and destination $d$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $e\_1, e\_2, \cdots e\_n$:

$$E(cost) = c\_1 + p\_1 * (c\_2 + p\_2 * (c\_3 + p\_3 * (\cdots (c\_{n-1} + p\_{n-1} * c\_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?

# Answer
> 2 votes
Suppose that you test the edges in order. The expected cost is thus $$ \sum\_{i=1}^n c\_i \prod\_{j=1}^{i-1} p\_j. $$ Now suppose that we switch the order of $k$ and $k+1$. The two relevant terms are $$ c\_k \prod\_{j=1}^{k-1} p\_j + c\_{k+1} \prod\_{j=1}^k p\_j. $$ After switching $k$ and $k+1$, these two terms become $$ c\_{k+1} \prod\_{j=1}^{k-1} p\_j + c\_k p\_{k+1} \prod\_{j=1}^{k-1} p\_j. $$ Dividing by $\prod\_{j=1}^{k-1} p\_j$, these two expressions become $$ c\_k + p\_k c\_{k+1} \\ c\_{k+1} + p\_{k+1} c\_k $$ The switch leads to an improvement if $$ c\_k + p\_k c\_{k+1} \> c\_{k+1} + p\_{k+1} c\_k \\ \Longleftrightarrow \\ c\_k (1-p\_{k+1}) \> (1-p\_k) c\_{k+1} \\ \Longleftrightarrow \\ \frac{c\_k}{1-p\_k} \> \frac{c\_{k+1}}{1-p\_{k+1}}. $$ This suggests testing the edges in increasing order of $$ \frac{c\_i}{1-p\_i}. $$

---
Tags: graphs, connected
---


title: Complexity of ODD-SMALLER-SAT

text:
# Question
Title: Complexity of ODD-SMALLER-SAT
While familiarizing myself with polynomial hierarchy, I used this book which is written by Ingo Wegener. Now I'm practicing, and on page 132 I met this exercise:

Let us consider a Boolean formula $\phi$ on the variables $x\_1, ...,x\_n$. Each $n$ bit vector $\overline x \in \\{0,1\\}^n$ is a possible assignment to variables and these vectors can be naturally classified in alphabetical order. The ODD-SMALLER-SAT-DECISION problem is to determine, being given $\phi$, if the smallest assignment $x$ which is satisfactory is such that $x\_n = 1$.

How to prove that this problem is part of the complexity class $\Delta\_2$?

# Answer
> 2 votes
Given $\phi$ and an assignment $\overline{y}$, the problem of deciding if there exists a satisfying assignment $\overline{x} \le \overline{y}$ (w.r.t. the lexicographical order) is in NP. This can be seen by either designing a nondeterministic Turing machine that solves the problem in polynomial time (nondeterministically guess $\overline{x}$, then deterministically check if $\overline{x} \le \overline{y}$ and $\phi(\overline{x}) = \top$, if so accept, otherwise reject), or by noticing that $\overline{x}$ itself is a yes-certificate for the instance (that can be deterministically checked in polynomial-time).

Then your original problem is in $\Delta\_2 = P^{NP}$: perform a binary search on the space of the $2^n$ possible assignments to find the smallest satisfying assignment $\overline{x}^\*$ for $\phi$. This can be done by repeatedly solving the above problem, each time halving the search space. After $O(\log 2^n) = O(n)$ iterations you are left with $\overline{x}^\*$. Check whether $\overline{x}^\*\_n = 1$ and answer accordingly.

---
Tags: complexity-theory
---


# Question
Title: Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$
> Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B\_1,B\_2,\dots,B\_t$ such that each $B\_i$ contains at most $t$ elements, FastMerge will produce a sorted array $B$ that contains all elements of $B\_1,\dots,B\_t$ in sorted order. My algorithm works in time $O(t^2)$ for any integer $t$. FastMerge is a comparison-based algorithm.” Prove that the claim of Dr. John is not correct.
>
> Hint: You can use the following fact without proof. If the function $T(n)$ is specified by a recursion $$ T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + cn & \text{if } n \> d, \\ O(1) & \text{if } n \leq d, \end{cases} $$ for some constants $c,d$, then $T(n) = O(n\log\log n)$.

How would I go about doing this?

# Answer
> 0 votes
Using Dr. John's algorithm, you could sort arrays in time $O(n\log\log n)$ (use the hint, choosing the value of $t$ which allows you to apply the hint), and this is a problem (why?).

---
Tags: algorithms, time-complexity, sorting, proof-techniques, recursion
---


# Question
Title: Big O of rational function using the definition
I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$.

I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction.

How would I go about doing this?

# Answer
> 1 votes
Rewrite $\frac{3x^3+2x^2+x+1}{4x^2+1} = \frac{3}{4}x \cdot \frac{12x^3+8x^2+4x+4}{12x^3+3x} = \frac{3}{4}x (1 + \frac{8x^2+x+4}{12x^3+3x})$.

Clearly, the limit of $f(x) = \frac{8x^2+x+4}{12x^3+3x}$ for $x \to +\infty$ is $0$ and hence, for any constant $c'\>0$, there is a constant $x'\_0$ such that $f(x) \le c'$ for all $x \ge x'\_0$. Pick your favorite constant $c'$, for example $c'=1$. You want to figure out any value of $x'\_0$ for which $f(x) \le 1$ or, equivalently:

$$ 12x^3+2x - 4 \ge 8x^2. $$

This is clearly true for $x'\_0=1$. Indeed, if $x \ge 1$: $$ 12x^3+2x - 4 \> 12x^2 - 4 \ge 8x^2 + 4x^2 - 4 \ge 8x^2. $$

Going back to the original formula we can conclude that, for every $x \ge 1$, $$ \frac{3}{4} x \cdot \left(1 + \frac{8x^2+x+4}{12x^3+3x} \right) \le \frac{3}{4} x \cdot (1 + 1) = \frac{3}{2} x. $$

Which satisfies the definition of $O(x)$ once you pick $c = \frac{3}{2}$ and $x\_0=1$.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Algorithm to split bipartite graph into subgraphs
I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint. I'm not sure if any existing algorithms solve my problem or not.

I have an undirected bipartite graph where the nodes are customers ($C$) and services ($S$). I want to split this into several smaller subgraphs, limiting the amount of services in each subgraph to some maximum number $N$. Unfortunately, looking for disconnected subgraphs is not sufficient because the graph connectivity is too high, so I think I will need to duplicate services.

Formally, I want a set of subgraphs such that:

* Each customer $c \in C$ appears in exactly one subgraph
* All edges appear in exactly one subgraph (the one in which their customer appears)
* Each service $s \in S$ can appear in any number of subgraphs (it's okay to duplicate services to help the split)
* Each subgraph should have at most $N$ services (where $N$ is a given constant that is guaranteed to be larger than the highest number of services connected to any single customer)
* The subgraphs should have as many customers as possible (without this restriction, it's trivially solvable by putting each customer in their own subgraph with a copy of their services). That can be a heuristic rather than formally proven.

Can anyone suggest an algorithm for doing this? The number of nodes is not huge (roughly 1000 customers, 100 services, with each customer connecting to 5 or less services) so brute force approaches or those with bad big-O scaling may be suitable.

# Answer
> 0 votes
It smells like it might be NP-hard.

One plausible approach is to use a SAT solver or ILP solver. Suppose you decide you want to have at most $m$ subgraphs. Then you can have boolean variables $x\_{i,k},y\_{j,k}$ indicating that customer $i$ goes into subgraph $k$ and service $j$ goes into subgraph $k$. You can obtain a bunch of constraints (clauses) based on your requirements and then ask the SAT solver or ILP solver to find a feasible solution. The worst-case running time is exponential. This might or might not work well enough in your situation.

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


# Question
Title: If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?
Deciding bipartite hypergraph coloring is NP-hard:

> While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz \[10\] that the problem to decide whether a given k-uniform hypergraph is bipartite is NP-complete for all `k≥3`.

Bipartite hypergraphs are colorable in expected (average) polynomial time:

> The purpose of this note is to present an algorithm that colors a hyper-graph chosen uniformly at random from the family of all labeled, 3-uniform, bipartite hypergraphs on `n` vertices in `O(n^5 * log (2n))` expected time.

Does this imply that P is approximately NP?

Source: https://www.math.uni-hamburg.de/home/schacht/abstracts/09eurocomb.pdf

# Answer
> 1 votes
No, it doesn't prove that P = NP.

This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness. The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard. Presumably, choosing a hypergraph at random is very unlikely to give you one that's hard, but they do exist.

NP-completeness is about worst-case hardness: even if a problem is easy on average, it can still be NP-complete.

I have no idea what "P is approximately NP" would mean in any precise sense.

---
Tags: complexity-theory, time-complexity, np-complete, np, p-vs-np
---


# Question
Title: CRC computation speed vs polynomials features
I tried to find information about how features of a CRC polynomials influence computation speed of implementations.

It is obvious that (depending from the CPU architecture the algorithm runs on) algorithms can be optimized for special CRC widths.

However, even when comparing CRC polynomials of the same width there still seems to exist differences in computation speed:

1. I read a statement that low polynomial weights would increase computation speed.
2. Also Prof. Koopman wrote on his 6sub8 CRC page: "Consider only polynomials with bits set in the bottom 8 bits (in addition to the topmost bit). This can help speed up computation and reduce lookup table sizes for CRC calculations in application programs."

I can see why pre-calculated CRC tables can be more compact using a sub8 polynomial. But I could not wrap my mind around the speed related statements. All implementations I had a look at (various C implementation of bit-wise and table-based algorithms) seem not to benefit from low-weight or sub8 polynomials. Maybe I missed the point or there are environments (like other algorithms, hardware implementations, special CPU architectures) that would benefit.

My question: Given a certain CRC width, in which way and under which circumstances does a low polynomial weight and/or a sub8 polynomial speed-up the computation of a CRC?

# Answer
The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 for X86 processors (pclmulqdq using xmm registers) the multiply time is fixed. For a typical hardware implementation, since the multiply is carryless, there's no propagation delay related to carry operations and all the XOR operations occur in parallel.

For standard multiplies (with carry), old processor multiply times were affected by the weight of the multiplier, but multiply times on processors since around 2010 or a bit before have fixed multiply times (for X86, it's 3 clocks). I'm not aware of a carryless multiply that isn't fixed in time, but it could exist on some processor I'm not aware of.
> 2 votes

---
Tags: time-complexity, computer-architecture, polynomial-time, polynomials, crc
---


title: Grid Puzzle Split Algorithm

text:
# Question
Title: Grid Puzzle Split Algorithm
I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.

# Answer
> 0 votes
A possible technique to generate random tilings is:

* Represent all possible solutions as a Zero Suppressed BDD (see for example The Art of Computer Programming volume 4, chapter 7.1.4, or this page). Every way to place any piece on the board corresponds to a variable in the ZDD. The constraints are that every tile is covered exactly once, which can be done by making an "exactly once"-ZDD for every tile, and then intersecting all those ZDDs. An "exactly once"-ZDD is easy to make, it's a single chain of nodes where a constrained variable (a piece-placement that covers this tile) corresponds to a node with a HI branch to TOP and a LO branch to the next node, and an unconstrained variable has both LO and HI going to the next node.
* For each node in the ZDD, count how many solutions it leads to. Runs in time proportional to the size of the ZDD (not the number of solutions) if memoization is used.
* Then, top down, randomly choose between the two children of a node using the ratio of solution counts as threshold. That would uniformly choose a random solution from the space of solutions. Runs in time proportional to the number of variables (depth of the ZDD).

# Answer
> 0 votes
One approach is to write a SAT formula to represent valid solutions, and then find a random satisfying assignment to this formula.

Introduce boolean variables $x\_{i,j}$, if cell $i$ is covered by tile $j$. Then you can write boolean constraints (clauses) on these variables that express that they correspond to a valid solution. Let $\varphi(x)$ denote the formula that contains the conjunction of these clauses.

Now we want to find a random satisfying assignment to $\varphi(x)$. One standard method is to choose a simple hash function $h$, and a random value $y$, and then use a SAT solver find a satisfying assignment to the formula $\varphi(x) \land (h(x)=r)$. (If there is no satisfying assignment, choose a new $h,r$ and try again until you find one.) One concrete way to do this that might suffice is to choose $h$ so that each bit of $h(x)$ is the xor of three randomly chosen variables $x\_{i,j}$. Ideally, you want to choose the size of the output of $h$ to be approximately $\log\_2 N$ where $N$ is the number of satisfying assignments of $\varphi(x)$. Since you might not know that number, it's reasonable to use binary search to choose a length of $h$ so that a randomly chosen $r$ often makes $\varphi(x) \land (h(x)=r)$ satisfiable.

---
Tags: algorithms, graphs, randomness, square-grid
---


# Question
Title: Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time
The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce the recurrence relations in context of a branching algorithm:

$T(n) \leq T(n-t\_1) + T(n-t\_2) + \dots T(n-t\_r)$

To solve this equation we assume $T(n) = c^n$, then $c$ should be a (complex) root of $x^n - x^{n-t\_1}-x^{n-t\_2}-\dots-x^{n-t\_r}=0$ ⇾ the running time of this branching algorithm is thus governed by the largest (real) root of this equation. We call $\tau(t\_1,t\_2,\dots,t\_r)$ the branching factor of these $t\_r$ numbers which is thus the largest positive real root of the corresponding equation. The branching vector is defined as $t = (t\_1,t\_2,\dots,t\_r)$

I am mainly interested in editing such branching algorithms in order to reduce the running time. Often, I get in a situation where I can either do:

(1) Remove a branch entirely (i.e. make the number of arguments in the branching factor lower)

(2) Have a choice between two branching vectors, say $x$ and $y$. The branching vectors are equal except for two elements: we have $x\_i \< y\_i$ and $x\_j \> y\_j$ with $i \neq j$. ($x\_i$ is thus element at position $i$ of branching vector $x$).

I have two questions:

(1) Intuitively, it seems to me that if I remove a branch entirely, this lowers the running time of the algorithm. We essentially try to find the number of leaves of the branching algorithm; per definition if we remove an entire branch the number of leaves should lower, hence should the running time. However, I can find no such theorem/proof in the literature.

Mathematically, you essentially have a equation of the form $\sum a\_i x^{n - c\_i} = 0$, where we only care of the largest positive real root. Now if I create the same equation, but now lower one of the $a\_i$ values, does my positive real root decrease? I assume this is some fundamental/elementary theorem somewhere but cannot seem to find it.

(2) The book has a Lemma (2.3): $\tau(i,j) \ge \tau(i + \epsilon, j - \epsilon)$ for all $0 \le i \le j$ and all $0 \le \epsilon \le \frac{j-i}{2}$. I cannot use this lemma in most cases of this problem. I am going to assume that I will just have to calculate the roots for each branch, right? And then take the minimum? Or is there some more fundamental theorem to this?

# Answer
> 2 votes
Let's start with your first question. You are considering two polynomials, $$ P(x) = x^n - a\_r x^{n-t\_r} - a\_{r-1} x^{n-t\_{r-1}} - \cdots - a\_1 x^{n-t\_1}, \\ Q(x) = x^n - a\_r x^{n-t\_r} - \cdots - b\_i x^{n-t\_i} - \cdots - a\_1 x^{n-t\_1}, $$ where all $a\_i$ are positive, and $0 \< b\_i \< a\_i$. Thus $Q$ results from replacing the term $-a\_i x^{n-t\_i}$ with $-b\_i x^{n-t\_i}$.

Let $\tau$ be the largest real root of $Q(x)$; note that $\tau \> 0$. Thus $$ P(\tau) = Q(\tau) + (b\_i - a\_i) \tau^{n-t\_i} \< 0. $$ On the other hand, $\lim\_{x\to\infty} P(x) = \infty$. Therefore $P$ must have another root beyond $\tau$.

You can try attacking your second question using similar reasoning.

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


title: rolling around running numbers

text:
# Question
Title: rolling around running numbers
I'm numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I'm about to save and which of the previous files to remove.

If I scale it down to a toy version with one digits, here's how I want it to behave.

1. As long as there are fewer than 5 files, we can just add files. This is represented in the first block below.
2. Once there are 5 previous files, the oldest one should be deleted. This is trivial as long as we haven't reached the maximum number, here 9. This is represented in the second block below.
3. Once the highest numbers has been reached, the numbering should roll around, and here is where things get tricky. See the third block below.

```
__prev__    __curr__   __drop__
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

0 1 2 3 4      5          0
1 2 3 4 5      6          1
2 3 4 5 6      7          2
3 4 5 6 7      8          3
4 5 6 7 8      9          4

5 6 7 8 9      0          5
6 7 8 9 0      1          6
7 8 9 0 1      2          7
8 9 0 1 2      3          8
9 0 1 2 3      4          9

```

Some pseudocode to illustrate my progress:

```
if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

```

... and this is where I'm stuck. I've experimented with subtracting 10 from each element in `prev`.

I'm sure it's trivial and that It'll hit me when I least expect it. I also have a nagging feeling I'll find an expression that generalizes both cases (with and without `max` in `prev`).

# Answer
> 2 votes
What you have been trying to implement is a first-in-first-out(FIFO) fixed-sized data structure, which is commonly called a circular queue, circular buffer, cyclic buffer or ring buffer.

In addition to the requirement of circular queue, you want the numbers rolling around an interval such as from 0 to 99. Since all the numbers in use are contiguous, it is enough to use just two numbers, the smallest of them and the largest of them to represent them.

In fact, since the number of files is a constant once the maximum number of files have been reached, it is enough if we keep track of the count of all numbers ever used. So we can construct a much simplified special implementation of the circular queue.

Similarly to your code, we should use the modulo technique. Here is a simple and fully-working Javascript implementation. Both get operation and update operation runs in $O(1)$.

```
// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

```

---

The above implementation works for all possible integer pairs limit \>= maximumKept. In particular, it works even if limit is maximumKept.

Here is a sample usage:

```
function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());

```

# Answer
> 1 votes
It's funny how explaining a problem makes you approach it differently (rubber duck, anyone?).

I think I've managed to cobble together the behaviour that I'm looking for. The idea is that if the list contains the last number (i.e. `n-1`, here 9), `n` is added to every number greater than `n/2`.

Now, Javascript is definately not my first language, so please be kind and try to see the idea rather than the mess that is my js ...

Play with it here or just take in the view below. Of course I'd be grateful for a better solution.

```
function roll(n) {
  const half = n/2 ;
  const last = n-1 ;
  var iter = half * 3 ;
  var prev = [] ;
  var curr = null ;
  var drop = n ;
  var temp ;

  while(iter--) {
    console.log(prev) ;
    curr = prev.length ;
    if (curr < half) {
      prev = update(prev,curr,drop) ;
      continue ;
    }
    temp = [].concat(prev) ;
    if (temp.includes(last)) {
      for (var t=0 ; t<temp.length ; t++) {
        if (temp[t] < half)
          temp[t] += n ;
      }
    }
    drop = Math.min.apply(null, temp) % n ;
    curr = Math.max.apply(null, temp) + 1 ;
    curr %= n ;
    prev = update(prev,curr,drop) ;
  }
}

function update(p,c,d) {
  for (var i=0 ; i<p.length ; i++) {
    if (p[i] == d)
      p.splice(i,1) ;
  }
  p.push(c) ;
  return p ;
}

roll(10) ;

```

# Answer
> 1 votes
The behavior of the modulo function in many programming languages is a bit quirky, and might depend on the sign of the argument. However, if you compute $a \bmod b$ for positive $a,b$, you will get an answer in the range $0,\ldots,b-1$.

Now suppose we want to compute a difference $x-y \pmod{b}$, and our goal is to obtain an answer in the range $0,\ldots,b-1$. We can assume that $x,y$ are in the same range. If $y \> x$, then $x - y$ would be negative, and so we might get a negative answer. To prevent that, we can compute $x + (b-y)$ instead. This will always give the correct answer.

---
Tags: algorithms, modular-arithmetic
---


# Question
Title: What is the relation between parsing languages and checking languages?
I have looked at a number of textbooks on computability theory. They typically have the following form:

* Define a language class (regular, context-free, context-sensitive, recursively enumerable)
* Define an automaton that **recognizes** the class (finite automaton, pushdown automaton, linear-bounded automaton, turing machine)

However, another fundamental question is how to **parse** a language. I have not found an treatment of parsing as a computational problem in these textbooks.

**Is there a simple relation between an automaton that recognizes a language, and an automaton that parses the language (and outputs a parse tree)?**

# Answer
There is a simple relation between the two problems, but it goes in only one side: if you can parse, then you can recognize. Indeed, if you run the parser and it outputs failure, then the input is not in the language; if the parser produces a parse tree, the input is in the language.

Note, however, that a parser and a recognizer are not only solving different problems, but are also given different specs. A recognizer is given a language in some abstract form. In contrast, a parser is given a grammar, which not only implicitly defines a language, but also instructs the parser how to convert a valid input into a parse tree. Since the same language can have many equivalent grammars, it's not clear what it even means to convert a recognizer to a parser – what grammar should the parser use?

Why are recognizers interesting, then? Precisely because of the one-sided connection, which states that a parser can be converted to a recognizer. This relation implies that if your language is hard to recognize, then you won't be able to parse it (using a certain class of algorithms).
> 4 votes

---
Tags: formal-languages, formal-grammars, parsers
---


# Question
Title: Generate all combinations of a set/array with specific conditions
Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions:

* Element values range between 0-11
* Set length is between 1-12
* All sets must begin with 0 (\[ 0 \])
* Value of element n must be greater than value of element n-1

I want to generate every possible combination of sets with those conditions. So here's a few examples:

\[ 0 \], \[ 0, 1 \], \[ 0, 2 \], \[ 0, 3, 5 \], \[ 0, 8, 9, 11 \]

All the way to:

\[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \]

The main language I'm using is Javascript, but if you're use to dealing with C/C++/Python examples in those languages work too. Just no ASM or Perl please. :)

# Answer
Let $k = 11$ in your problem, so we want to generate all sets with values in the range $0$ to $k$ and with between $1$ and $12$ elements. Then you can do the following:

* First generate all sets for $k-1$ (recursively)
* Then, for each set, make *two* copies, one with a $k$ on the end and one without a $k$ on the end.

If you prefer doing it iteratively, here is this described in an iterative fashion (pseudocode):

```
generate_all_subsets(k):
    let sets = [[0]]
    for i from 1 to k:
        for each set in sets:
            add sets + [k] to sets
            # (now there are two copies: sets, and sets + [k],
            #  so the size of 'sets' has doubled)
    return sets

```
> 1 votes

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


title: Working of the GHS algorithm

text:
# Question
Title: Working of the GHS algorithm
Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found here https://en.wikipedia.org/wiki/Distributed\_minimum\_spanning\_tree

What I think is that the fragments(the nodes in a fragment are shown within curly braces) will be formed as follows:
Step 1: {1, 2}
{5, 6}
{3}
{4}

Step 2: {1, 2, 3, 4}
{5, 6}

Step 3: {1, 2, 3, 4, 5, 6} //as 1 and 5 get connected.

But what my professor said is that 4 will become a part of the MST at the end. These are the steps that he told us.

Step 1: {1, 2}
{5,6}// this step is the same
{3}
{4}

Step 2: {1, 2, 3}
{5,6}
{4}

Step 3: {1, 2, 3, 5, 6}
{4}

Step 4: {1, 2, 3, 4, 5, 6}

Can you please tell me which version is correct? The graph -\>

# Answer
Indeed.

Let the fragment at a particular stage be : {1,2},{5,6},{3},{4}.

Now the fragment {1,2} will connect with the least weight outgoing edge which is 1-3 and fragment {5,6} will connect with the least weight outgoing edge which is 1-5 to create the fragment {1,2,3,5,6} and {4} and finally it connects to {4} with edge {2-4}.

Hope this helped.
> 1 votes

---
Tags: algorithms, distributed-systems, minimum-spanning-tree
---


title: Bridges and Edge Disjoint Paths

text:
# Question
Title: Bridges and Edge Disjoint Paths
So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?

---

$\text{My Attempt at the Proof}$:-

Suppose there isn't , then there must be at-least one edge common in both the paths , and if we remove it then it disconnects $G$ and thus is a bridge. As there are no Bridges , Hence Proved !

---

$\text{Why I feel this Proof is incorrect }$:-

Suppose the exits three paths from u to v.

Path 1 :- $u$ ----\> $E\_1$ -----\> $E\_2$ -----\> $v$

Path 2 :- $u$ ----\> $E\_2$ -----\> $E\_3$ -----\> $v$

Path 3 :- $u$ ----\> $E\_1$ -----\> $E\_3$ -----\> $v$

(here -----\> represents some path and $E\_1 , E\_2 , E\_3$ represent Edges.

This is an example which violates the above property. It has no bridges as well as no edge disjoint paths.

Can someone either Prove or disprove this Property ? I am really confused.

# Answer
> 1 votes
Yes, it is true that there exist two edge-disjoint paths between any two vertices in a connected bridgeless graph.

Define a closed trail as a trail whose last vertex is its first vertex. Note, a trail contains two edge-disjoint paths between any two of its vertices.

**Trail combining lemma.** Let $G$ be a graph. Suppose a closed trail passes vertex $v$. Another closed trail passes vertex $u$. If those two trails share one vertex, there is a closed trail that passes both $u$ and $v$.

**Proof**. You can convince yourself easily by drawing a few situations. Done.

---

Let us prove the following proposition.

**A graph is connect and bridgeless if and only if any two vertices are included in a closed trail.**

**Proof.**

"$\Leftarrow$": Obvious.

"$\Rightarrow$": Suppose $G$ is connected and bridgeless. $v$ and $w$ are two vertices.

Let $$T\_v=\\{u : u \text{ is a vertex of } G \text{ such that there is closed trail that passes }v\text{ and } u\\}.$$ Suppose $u\in T\_v$ and $s$ be a neighboring vertex of $u$, i.e., $\\{u,s\\}$ is an edge.

* There is a closed trail that passes $v$ and $u$ by the definition of $T\_v$.
* There is a closed trail that passes $u$ and $s$, since edge $\\{u,s\\}$ is not a bridge.

Thanks to the lemma, we have a closed trail that passes $v$ and $s$. In other words, $T\_v$ contains all neighborhoods of all its vertices. That means $T\_v$ (with all edges between its points) is a connected component, which must be $G$ itself. In particular, there is a closed trail that passes $v$ and $w$. Proof is complete.

---

A very similar characterization of bridgeless connected graphs is Robbins' theorem. If $G$ is connected and bridgeless, that theorem says we can choose a direction for each edge of $G$, turning it into a directed graph that has a path from every vertex to every other vertex.

---
Tags: graphs, graph-traversal, connected-components
---


# Question
Title: on-the-fly decompress a flat-file database
I'm facing the following problem. I have a flat-file database (e.g. CSV). Since it's relatively large to store in memory, I'd like to compress it.

Given a key, I need to return the uncompressed text (record of values).

So one naive idea is to tokenize the text into **words** and to have the mapping $\text{word} \mapsto \text{codeword}$

Of course, this naive idea lacks of understanding of statistical properties in the data, that other compression algorithms exploits.

So the next thing I thought about is Huffman code. The problem I'm facing is that I'd like to find the optimal tokenization for the text. Let's say that one column in the CSV file contains only the text "the fox jumped over the lazy dog", it reasonable to want that the algorithm would tokenize this string as one token.

but then again, going over all possibilities isn't a feasible task. Are there any algorithms that deals with this problem?

So to summarize, I need to:

1. Compress my data once and to decompress on demand
2. Return the requested value (a record) for a given key
3. Decompression should be "fast enough"

Which algorithms fit my problem?

In particular, I'd like to know if Huffman code is a good option, and if so, how to tokenize the text.

Thanks!

# Answer
What is "too large to fit in memory"? Current operating systems can handle processes with GiB of memory, if you use e.g. mmap(3) on Unix/Linux, you can work as if you had the whole file in memory and access it at random. That might be much faster than compressing/uncompressing on the fly. And (if I understand your question correctly) you want to access individual records (i.e., rows) by key, so you will have to compress only the remaining row and keep the key, working one row at a time (you don't want to have to uncompress from the start to be able to access row 102354 each time, don't you?). That will severely limit the compression gain.

If you can preprocess the data (a given, since you talk about compressing it), perhaps an even better bet is to use a simple(ish) database to store it, like Berkeley DB, the Unix standard DBM or it's GNU take GDBM or other, more modern, for performance tuned ones like Lightning Memory-Mapped Database LMDB.
> 1 votes

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


# Question
Title: Logspace algorithm for balanced parentheses problem
Currently I want to learn the complexity of space, I read a few of the books on it. On this I encountered this example problem. I would just like to know how to show that the following problem $\in L $ (deterministic logarithmic space).

Input: series of open or closed parentheses

Question: Are these parentheses properly balanced?

Example: $((() ()) (()))$ should be accepted but $()) ()$ should be rejected.

# Answer
Initialize a counter at zero. Whenever you see "(", increase it by one, and whenever you see ")", decrease it by one. Accept if the counter was always nonnegative and ended up at zero. The counter only takes logarithmic space to store.
> 6 votes

# Answer
This amounts to reading the input string and keeping track of the difference $\delta$ between the number of open and closed parenthesis.

If $\delta$ ever becomes negative, then the input is not properly balanced (at some point there is one more closed parenthesis than open ones). Similarly, if $\delta \>0$ at the end of the string, then there are unclosed parentheses and the input is unbalanced.

Otherwise the input is balanced.

Since $\delta$ is always between $-1$ and $n$, only $O(\log n)$ bits are needed to store it. The same applies for the other auxiliary variables you'll need to implement the above algorithm (for example an index to the current character of the input). Hence the problem is in logspace.
> 3 votes

---
Tags: space-complexity
---


# Question
Title: How to find all the contiguous subsequence of an array is less than O(N^2) time complexity?
I am unable to find product of every contiguous subsequence of an array in less than O(N^2) time complexity.

What actually i want to do is find the number of contagious subsequence whose product of elements is either odd or multiple of 4. The problem here is time i want an algorithm which can make it happen in O(N).

```

public class PrintAllSubArrays {

    public void printSubArrays(int [] arrA){

        int arrSize = arrA.length;
        //start point
        for (int startPoint = 0; startPoint <arrSize ; startPoint++) {
            //group sizes
            for (int grps = startPoint; grps <=arrSize ; grps++) {
                //if start point = 1 then
                //grp size = 1 , print 1
                //grp size = 2, print 1 2
                //grp size = 3, print 1 2 3 ans so on
                for (int j = startPoint ; j < grps ; j++) {
                    System.out.print(arrA[j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        int [] arrA = {1,2,3, 4};
        new PrintAllSubArrays().printSubArrays(arrA);
    }

}

```

---

This question is part of a problem from a finished programming contest: "Squared Subsequences" (April 2020)

# Answer
A contiguous subsequence satisfies your conditions if either it consists only of odd elements, or it contains one number which is a multiple or 4, or it contains two numbers which are multiples of 2. This suggests computing the following quantities:

* $X$: Number of contiguous subsequences consisting only of odd elements.
* $Y$: Number of contiguous subsequences containing an even element.
* $Z$: Number of contiguous subsequences containing no element which is a multiple of 4, and exactly one even element which is not a multiple of 4.

You are interested in $X+Y-Z$.

To determine $X,Y$, it suffices to partition the elements into odd (O) and even (E). If your sequence is of the form $$ O^{\ell\_1} E O^{\ell\_2} E \cdots O^{\ell\_r} E O^{\ell\_{r+1}}, $$ then $$ X = \sum\_{i=1}^{r+1} \binom{\ell\_i+1}{2}, \\ Y = \sum\_{1 \leq i \< j \leq r+1} (\ell\_i+1) (\ell\_j+1). $$ In order to compute $Y$ quickly, note that $$ 2Y = \left(\sum\_{i=1}^{r+1} (\ell\_i+1)\right)^2 - \sum\_{i=1}^{r+1} (\ell\_i+1)^2. $$

In order to compute $Z$, we first separate our sequence by breaking at every element which is a multiple of 4. If $Z\_j$ is the number of $Z$-type contiguous subsequences in the $j$th subsequence, then $Z = Z\_j$. We can write the $j$th subsequence as $$ O^{\ell\_1} E O^{\ell\_2} E \cdots O^{\ell\_r} E O^{\ell\_{r+1}}, $$ just as before. We then have $$ Z\_j = \sum\_{i=1}^r (\ell\_i+1) (\ell\_{i+1}+1). $$ In total, the algorithm runs in linear time.

Disclaimer: Verify that the formulas work – they might be slightly off, but the general idea should work.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Build LL(1) parsing table for grammar S -> iSeS | iS | a
**Task**

1. Bulid parsing table for grammar `S -> iSeS | iS | a`
2. Resolve conflicts in this table and simulate parser work for word `iiaea`

**Problem**

I know how to make a parsing table for unambiguous grammar, and how to simulate parser. However this grammar is an example of **dangling else problem**.

**What I tried**

I was tought that I should remove left recursion and left factoring. Then make a table using first and follow. Whatever I tried I got two grammar expressions in the same row of table. Please provide me some hint what to do in this situation.

After left factorization

```
S ->  iSS' |a
S'-> e S | ε

```

Because we will never use `S' -> ε` (there are no other values which can give us `e` in the `Table` except `Table[S'][e]` ) we can remove this production from parsing table.

**Final solution**

# Answer
Eventually you will end up with having to choose between $S'\to\epsilon$ and $S'\to eS$.

The grammar says that's a conflict. But can't we deduce which is correct? What if we choose $S\to\epsilon$? Will we ever be able to match the `e`?
> 0 votes

---
Tags: formal-grammars, parsers
---


title: Linear programming over a finite field

text:
# Question
Title: Linear programming over a finite field
I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}\_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the subject. Does this problem have a name? What is known about the computational complexity of this problem?

# Answer
Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields.

Note that linear programming is more general, allowing also inequalities. It is not entirely clear, however, how the order should be defined over a finite field.
> 4 votes

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


title: Prove a TM problem is NP-complete

text:
# Question
Title: Prove a TM problem is NP-complete
> Question: Show that $T\_{NP}$ is NP-complete, where $$T\_{NP} = \\{m\\#w\\#^c\mid M\_m\text{ is an NTM};M\_m(w)\text{ has an accepting computation of $\leq$ c steps}\\}$$

This question looks weird to me because itself is a TM. In general, when we say a problem is in NP, we can give an instance of that problem and using NTM to guess and verify. However, since $T\_{NP}$ is a NTM, can we simply say using $T\_{NP}$ itself to guess and verify in polynomial time?

Also, for the reduction part, I'm not sure but I think 3SAT is reducible to $T\_{NP}$ because each clauses in 3SAT formula $\phi$ is true iff each step in $T\_{NP}$ is valid.But I'm still stuck on the detail proof and argue the correctness at this moment. Any suggestion?

# Answer
> 1 votes
Let us first show that $T\_{NP}$ is indeed in NP. Given an input, $m\\#w\\#^c$, nondeterministically guess a sequence $r$ of nondeterministic choices for $M\_m$ of length $c$, simulate $M\_m$ on $w$ for $c$ steps using $r$, and accept if $M\_m$ accepts. This nondeterministic algorithm accepts iff $m\\#w\\#^c \in T\_{NP}$. Furthermore, it runs in polynomial time in the input size (here it is crucial that the input contains $\\#^c$ rather than $c$ encoded in binary).

To show that $T\_{NP}$ is NP-hard, you can just use the definition. Suppose that $M$ is an NP machine. Then $M = M\_m$ for some $m$, and $M$ runs in time $P(n)$ on an input of length $n$. Given an input $w$, map it to $m\\#w\\#^{P(|w|)}$. It is clear that $M\_m$ accepts $w$ iff $m\\#w\\#^{P(|w|)} \in T\_{NP}$. The reduction is polynomial since $P(n)$ is a polynomial.

---
Tags: turing-machines, np-complete, reductions, np-hard, np
---


# Question
Title: Do all recursive problems have optimal substructure?
I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved recursively that do not have an optimal substructure?

# Answer
I think there is some confusion in terminology here. Part of the problem is what we mean by **problem** and **algorithm**. But there is more to it:

1. Textbooks like CLRS introduce the notion of **optimal substructure** as a property of **problems** (and not algorithms directly). That's because an **algorithm** often transforms a problem statement into other **problem/s** and, as a result, **an algorithm** may establish a link between **problem solutions** with **subproblem solutions**. Indeed, CLRS defines **optimal substructure** as follows: *`"A problem exhibits optimal substructure if a solution to the problem contains solutions to its sub-problems"`*. While it doesn't say this directly, the term *"**contains**"* implies *through* an **algorithm**.
2. Just because a **problem** (and actually all problems) may accept **a** recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed **recursive** (this is in relation to Yuval Filmus's answer). For a particular algorithm to be **recursive**, it must call itself recursively.
3. Similarly, just because an algorithm may involve some form of **iteration** or even **recursion** (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem **recursively**.
4. Last but not least, just because an algorithm is **recursive**, it does **not** mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and *then* once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does **not** mean that the algorithm is *actually* **building** the **sorted sequence** (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the **problem**.
> 5 votes

# Answer
Every problem can be solved recursively. Recall first that every problem can be solved using an algorithm which uses a WHILE loop and conditionals. Indeed, the operation of a CPU can be described in this way. We can adapt this solution to a (tail) recursive procedure as follows.

The parameters are the instruction pointer, the content of the registers, and the content of memory. The procedure performs the instruction that the instruction pointer is pointing at, modifying the instruction pointer, the registers, and the memory. Then (unless the instruction was HALT), it calls itself recursively with the updated instruction pointer, register contents, and memory contents.
> 2 votes

# Answer
The article you were reading might not be not good enough for educational purpose, especially for a beginner in dynamic programming. It is not accurate enough, either.

It is apparent, as noticed by Marcus Ritt that article copies from the Wikipedia article on dynamic programming, a lot.

However, that article is not up to date with the following statement at the latest version of Wikipedia,

> Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

We can compare the statement above with the following statement in the article, where "recursively" instead of "optimally" is used to define optimal substructure, which is not correct.

> Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure."

---

> Are there problems that can be solved recursively that do not have an optimal substructure?

This question is more or less off the point in the sense that being recursive is not related to being optimal. Not directly.

The truism would be that problems that can be solved recursively should have recursive substructures. Likewise, if an optimization problem can be solved by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

If we have to answer that question head-on, then the answer is, of course, yes and plenty of them. We can compute Fibonacci numbers recursively, but there is no apparent optimal substructure in Fibonacci numbers. We can compute recursively the factorials which does not have substructure that can be called optimal reasonably.

In fact, Yuval's answer presents a common view that explained why most programs can be considered or adapted as solving problems recursively.

---

It might have been better had you followed an excellent textbook, such as the most popular textbook *Introduction to Algorithm* by CLRS, in case you have not read it yet. Its chapter 15, *Dynamic Programming* explains the basic concepts and techniques about dynamic programming clearly. Section 3 of that chapter, *elements of dynamic programming*, elaborates on the components of dynamic programming, "Optimal substructure", "Overlapping subproblems", "Reconstructing an optimal solution" and "Memoization".
> 2 votes

# Answer
When solving an optimization problem recursively, optimal substructure is the requirement that the optimal solution of a problem can be obtained by extending the optimal solution of a subproblem (see for example, Cormen et al. 3ed, ch. 15.3).

Consider for example the problem of finding a simple shortest $s$-$t$ path in a directed graph with non-negative distances. Such a path must visit a predecessor $u$ of $t$. So if you are able to recursively find the shortest $s$-$u$ path for all predecessors $u$ of $t$, you can find a shortest $s$-$t$ path. In this case you have an optimal substructure.

Contrast this with finding a simple longest $s$-$t$ path. Such a path must also visit a predecessor $u$ of $t$. However, it isn't true that the longest $s$-$t$ path can be obtained by extending some longest $s$-$u$ path for a predecessor $u$ of $t$, since such a path may already visit $t$, and so its extension may not be a simple path, and you cannot remove the resulting cycle to make the path simple, since this can make it shorter. In this case you don't have an optimal substructure.

The longest $s$-$t$ path can be found by choosing a different kind of subproblem that has optimal substructure. If you define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$, you get \begin{align\*} C(s,t,V)= \begin{cases} \max\_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\\{t\\})+d\_{ut}, & \text{if $s\neq t$ and $N^{-}(t)\setminus V\neq \emptyset$},\\ -\infty, & \text{if $s\neq t$ and $N^{-}(t)\setminus V=\emptyset$},\\ 0, & \text{if $s=t$}, \end{cases} \end{align\*} where $N^-(t)$ is the set of predecessors of vertex $t$, and $d\_{uv}$ is the distance between $u$ and $v$.
> 2 votes

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


# Question
Title: Algorithm to create dense style crossword puzzles
I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of all varying lengths. The current algorithm I'm using takes some inspiration from this paper:

https://www.aaai.org/Papers/AAAI/1990/AAAI90-032.pdf

Search Lessons Learned from Crossword Puzzles by Matthew L. Ginsberg Michael Frank Michael P. Halpin Mark C. Torrance

as well as several others who have written about the topic:

https://www.cs.rpi.edu/~dhulena/CS44FinalProjectReport.pdf

http://www.cs.columbia.edu/~evs/ais/finalprojs/steinthal/

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.501.1743&rep=rep1&type=pdf

The basic setup of the algorithm is this:

1. Find the most constrained word i.e. the current word (which is not currently a valid word from the dictionary) which has the fewest possibilites. EX: J--Z has significantly fewer possibilites for fill than T--S so I'd expand J--Z and not T--S.
2. Once selecting the word with the fewest potential candidates. Iterate through the word's potential candidates. Continuously check if playing the current candidate allows for all of this word's intersecting words to have candidates. EX: if the grid was

\# H A S
\- E - -
\- A - -
\- T - #

and I was currently examining A--- then "AZIZ" is a potential fill but there are no words -TZ (intersecting word) and thus "AZIZ" would not be considered. Depending on how long the word is the algorithm will generate several different potential candidates before moving on to the next most constrained word. In the example above, perhaps ATIS, ARTS, ARFS all allow the words intersecting words to have candidates. The geometric mean of the intersecting words potential candidates is taken and the next word played is the candidate which maximizes this mean. I consider this be one level of "look ahead".

3. If at any point we arrive to a word where no potential candidates can be generated then we backtrack (actually back jump). And the algorithm will move back to the point where the most recently played intersecting word's content is different. EX: in the grid below if we are examining ST- and zero potential candidates are found, the most recently played word is "PEET" and thus it will be removed and more potential candidates will be explored

\# H A S
P E E T
\- A - -
\- T - #

would maybe become:

\# H A S
P E T S
\- A- -
\- T - #

and we'd then be able to play:

\# H A S
P E T S
\- A - O
\- T - #

This algorithm works great for simple grids (grids with shorter words on average and fewer total word intersections). For example this algorithm can solve a grid like this in 10-20 seconds

but as soon as I introduce a grid with the same dimensions but longer words with a larger number of intersections:

this algorithm becomes totally useless. It will never move past filling the 5-6 initially most constrained words (typically the central longest words as you would expect). I've never let the algorithm run for more than 59 minutes but it's never been able to find a solution (or even come close) to an open style grid like the one above.

So I am looking for ideas/solutions/heuristics to attempt to solve these more open (harder) grids. Some ideas/things I have already tried:

1. I added a "second level" of look ahead. When examining a word, find the geometric mean of the number of potential candidates for intersecting words, and then go one level deeper and find the geometric mean of the intersecting word (with all of its own potential candidates) intersecting words. I implemented this and the computation time was enormous and this drastically slowed down the solve time for the easier style puzzles. It also appeared to have 0 benefit when solving the harder grids.
2. When playing the first few long and highly intersected words have a preference for words which have "easier letters" (think of scrabble tiles which have lower point values) so have a preference for words which contain many R/S/T/L/M and very few J/Q/Z/X etc. I realize this might aid in solving but I'm not convinced it will work because letter position within each word matters more than general word contents. I did a quick and dirty test of this by only allowing dictionary words of 22/26 letters (no words with J/Q/Z/X) and this had no effect.
3. Use some sort of letter by letter approach instead of a word by word approach which I am currently using. Compute the potential words for every word in the grid, map each of those words specific letters to each cell, and then try a greedy approach which maximizes the size of set intersection of cells.
4. Parallelize the solving algorithm. Not convinced this will work either. I believe I'll just compute more solutions with a dead end in less time and not make any actual headway.

In my reading I've learned that this problem is NP-HARD (perhaps NP-complete reduced from vertex cover? Just a proof I saw, not really concerned with this). Additionally, I've learned this problem is characterized as a CSP. Any sort of input you may have in terms of improving the current algorithm (perhaps more or better heuristics) or an entirely different approach relating to CSPs I would love to hear your thoughts.

Thank you.

ps I could post videos of the algorithm in action or other examples of grids the algorithm can solve easily/fails to solve. Willing to provide any info needed.

Update: by increasing the amount of pre-processing at each successive step I am able to solve the above grid. In step 1 when calculating the most **constrained** word I find all possible candidate words for each remaining unfilled word, and map the possible candidates word's letter to each cell and do an intersection at each cell. This is beneficial because it better indicates the most constrained word and additionally eliminates more possible solution paths. However, this pre-processing makes the backjumping essentially useless. Using my dictionary of ~290K words I am able to solve the above grid but have still not cracked the upper echelon of the most constrained grids.

# Answer
> 3 votes
There may simply be no solution to some of these problem instances. And the fact that the problem is NP-hard means that you cannot expect to find any efficient algorithm to find solutions for large instances, even if they do exist.

That said, I suggest the following relaxation:

## Idea: Map down to a smaller alphabet

Choose some $k \< 26$, and map each of the 26 letters to one of the integers $1, \dots, k$. This mapping can work however you want -- you could try to keep roughly the same number of letters in each group, or not. These $k$ integers are a new, smaller "alphabet", in which each "letter" corresponds to the set of possible original letters A-Z that are mapped to it.

Map the dictionary words into this new alphabet. Try to solve the problem instance with your existing algorithm: You can do this without modifying your program, since it suffices to use some subset of the 26 letters to represent the integers in the new alphabet. If there is no solution to this "relaxed" problem, there is certainly no solution to your original problem.

OTOH, if there is a solution to this problem (and there will be if $k$ is small enough -- e.g., there definitely will be for $k=1$), then there is no guarantee that it can be converted back into solutions to your original problem, but it may be possible. Provided that $k$ is not too small, you now have a much more strongly constrained space for a recursive search to explore exhaustively, since in each position on the grid you are restricted to one of the letters mapped to that integer -- this should result in earlier cutoffs and a much faster search.

Note that it may be that the relaxed problem has multiple solutions, and the solution you initially find cannot be extended to a solution for the original problem -- but some other solution to the same relaxed problem can. So it may be worth exploring multiple solutions to the relaxed problem, if your program can do so.

One nice property of this approach is that it is very flexible: Since any mapping works, you can simply try again with a different one if extending a solution of the relaxed problem to the original problem fails. (If the relaxed problem itself has no solution, then you can stop: The original definitely has no solution.) Many different mappings can be tried independently in parallel.

I would initially try $k=2$ just to get a lower bound on how quickly a relaxed problem can be solved -- this may even be enough to get a useful speedup in the subsequent extension (assuming a solution is found!) Then I would try to choose $k$ as large as possible such that solving the relaxed problem completes in reasonable time. It's not obvious to me what kinds of mappings are best -- it might turn out to be helpful to group certain letters together, or to "preserve" some letters by making them the unique preimage of some integers.

---
Tags: algorithms, np-hard, heuristics, search-problem, constraint-satisfaction
---


# Question
Title: Line-Breaking algorithm (minimum raggedness) where spaces can have width different than 1.0
The ***Divide & Conquer Algorithm for Line-Breaking*** described here is given below, both in Python and in Dart (which is similar to Java/C#).

Line-breaking is also known as "line wrap", "word wrap", or "paragraph formation", and this algorithm is used for achieving minimum raggedness.

This algorithm works, but it considers each space as having exactly `width = 1.0` .

My Question:

**How can I modify this algorithm so that it ignores spaces? In other words, make it consider spaces as having width `0.0`? (or it would also work for me if I could define any width I wanted for the spaces, including `0.0`).**

*Python Implementation:*

```
def divide(text, width):
    words = text.split()
    count = len(words)
    offsets = [0]
    for w in words:
        offsets.append(offsets[-1] + len(w))

    minima = [0] + [10 ** 20] * count
    breaks = [0] * (count + 1)

    def cost(i, j):
        w = offsets[j] - offsets[i] + j - i - 1
        if w > width:
            return 10 ** 10
        return minima[i] + (width - w) ** 2

    def search(i0, j0, i1, j1):
        stack = [(i0, j0, i1, j1)]
        while stack:
            i0, j0, i1, j1 = stack.pop()
            if j0 < j1:
                j = (j0 + j1) // 2
                for i in range(i0, i1):
                    c = cost(i, j)
                    if c <= minima[j]:
                        minima[j] = c
                        breaks[j] = i
                stack.append((breaks[j], j+1, i1, j1))
                stack.append((i0, j0, breaks[j]+1, j))

    n = count + 1
    i = 0
    offset = 0
    while True:
        r = min(n, 2 ** (i + 1))
        edge = 2 ** i + offset
        search(0 + offset, edge, edge, r + offset)
        x = minima[r - 1 + offset]
        for j in range(2 ** i, r - 1):
            y = cost(j + offset, r - 1 + offset)
            if y <= x:
                n -= j
                i = 0
                offset += j
                break
        else:
            if r == n:
                break
            i = i + 1

    lines = []
    j = count
    while j > 0:
        i = breaks[j]
        lines.append(' '.join(words[i:j]))
        j = i
    lines.reverse()
    return lines

```

*Dart implementation:*

```
class MinimumRaggedness {

  /// Given some [boxWidths], break it into the smallest possible number
  /// of lines such as each line has width not larger than [maxWidth].
  /// It also minimizes the difference between width of each line,
  /// achieving a "balanced" result.
  /// Spacing between boxes is 1.0.
  static List<List<int>> divide(List<num> boxWidths, num maxWidth) {

    int count = boxWidths.length;
    List<num> offsets = [0];

    for (num boxWidth in boxWidths) {
      offsets.add(offsets.last + min(boxWidth, maxWidth));
    }

    List<num> minimum = [0]..addAll(List<num>.filled(count, 9223372036854775807));
    List<int> breaks = List<int>.filled(count + 1, 0);

    num cost(int i, int j) {
      num width = offsets[j] - offsets[i] + j - i - 1;
      if (width > maxWidth)
        return 9223372036854775806;
      else
        return minimum[i] + pow(maxWidth - width, 2);
    }

    void search(int i0, int j0, int i1, int j1) {
      Queue<List<int>> stack = Queue()..add([i0, j0, i1, j1]);

      while (stack.isNotEmpty) {
        List<int> info = stack.removeLast();
        i0 = info[0];
        j0 = info[1];
        i1 = info[2];
        j1 = info[3];

        if (j0 < j1) {
          int j = (j0 + j1) ~/ 2;

          for (int i = i0; i < i1; i++) {
            num c = cost(i, j);
            if (c <= minimum[j]) {
              minimum[j] = c;
              breaks[j] = i;
            }
          }

          stack.add([breaks[j], j + 1, i1, j1]);
          stack.add([i0, j0, breaks[j] + 1, j]);
        }
      }
    }

    int n = count + 1;
    int i = 0;
    int offset = 0;

    while (true) {
      int r = min(n, pow(2, i + 1));
      int edge = pow(2, i) + offset;
      search(0 + offset, edge, edge, r + offset);
      num x = minimum[r - 1 + offset];

      bool flag = true;
      for (int j = pow(2, i); j < r - 1; j++) {
        num y = cost(j + offset, r - 1 + offset);
        if (y <= x) {
          n -= j;
          i = 0;
          offset += j;
          flag = false;
          break;
        }
      }

      if (flag) {
        if (r == n) break;
        i = i + 1;
      }
    }

    int j = count;

    List<List<int>> indexes = [];

    while (j > 0) {
      int i = breaks[j];
      indexes.add(List<int>.generate(j - i, (index) => index + i));
      j = i;
    }

    return indexes.reversed.toList();
  }
}

```

# Answer
Suppose the gap between any two words in the same line spans a length of $k$, instead of 1. The only change needed in the Python code would be to change the line in `def cost(i, j)` from

```
w = offsets[j] - offsets[i] + j - i - 1

```

to

```
w = offsets[j] - offsets[i] + k * (j - i - 1)

```

`def cost(i, j)` returns the minimum cost needed for placing the first $j$ words, if the last line contains the words $i + 1$ to $j$. $w$ represents the length of that last line, and `offsets[j] - offsets[i]` gives the sum of the length of the words in that line. The last term $j - i - 1$ adds the contribution of the spaces between those words. So all you have to do is tweak this last term as you need.

Hope this answers your question.
> 3 votes

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


# Question
Title: Probability of data loss for mirrored,3 disk system
I am reading the book Database Systems the Complete Book 2nd Edition. A slightly modified Question 13.4.5 states:

> Suppose we use three disks as a mirrored group; i.e., all three hold identical data. If the yearly probability of failure for one disk is F, and it takes H hours to restore a disk, what is the yearly probability data loss?

My answer is $(F\*(F\*H/365\*24)^2)\*6$

I would like to know if I am right. I will explain the reasoning behind my answer:

In order for data loss to occur, all 3 disks must fail within a time period of H hours.

The probability that the first disk fails is $F$. The probability that the second and third disks fail within $H$ hours of the first disk failing is $(F\*H/365\*24)^2$.

Thus the probability of all disks failing within a time period of H hours is $F\*((F\*H/365\*24)^2)\*6$.

The reason we multiply by 6 is because there are 6 ways in which this event could happen:

123 132 213 231 312 321

I have trouble with probability when dealing with events that can occur in multiple ways. So the only part of the reasoning that I am unsure about is the part where I multiply by 6. Are all 3 disks failing one event, or are they 6 different events?

# Answer
Let us look at the probability of the "123" event happening. That is, Disk 1 fails, and then Disk 2, and then Disk 3, and all of these happen within a span on $H$ hours. Your claim is that the probability of this is $F ∗ (\frac{FH}{365∗24})^2$. But the $\frac{FH}{365∗24}$ term only denotes the probability of a disk failing in the $H$ hours after the first disk fails. In particular, it does not consider the ordering constraint of "Disk 2 fails before Disk 3 fails".

Instead, what $F ∗ (\frac{FH}{365∗24})^2$ denotes is the probability that Disk 1 fails, and in the ensuing $H$ hours, both Disk 2 and Disk 3 fail. So this captures both the events "123" and "132".

Similarly, the probability of either the event "213" or "231" happening would be $F ∗ (\frac{FH}{365∗24})^2$. And similarly for the events "312" and "321" combined.

So the final answer should be $(F ∗ (\frac{FH}{365∗24})^2) * 3$, and not $(F ∗ (\frac{FH}{365∗24})^2) * 6$.
> 1 votes

---
Tags: probability-theory, database-theory
---


# Question
Title: In a NPDA if the stack is empty, where the start/end state are the same can you go again
***Thoughts***

I am wondering if you get a string that goes through the NPDA and arrives back at **q0** can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I am back in **q0** and the **$** is removed from the stack I stop

# Answer
> 2 votes
There are several alternatives for the definition of a PDA, all of which are equivalent, in the sense that computationally they specify the same class of languages. To answer your question, you can perhaps take a look at the precise definition of PDAs you are working with.

For the following, with $X\_\varepsilon$ I mean $X\cup\\{\varepsilon\\}$.

Some definitions use the signature $$\delta : Q\times\Sigma\_\varepsilon\times\Gamma\to \mathcal{P}(Q\times\Gamma^\*)$$ for the transition function, where $\Gamma$ is the stack alphabet. From this signature, it is evident that you need to have a symbol in the stack in order to move on. Of course, with this definition all PDAs are initialized with some initial symbol in the stack, *before* they start running. Otherwise, the PDA will never be able to make its first transition.

There are definitions, though, that use the signature $$\delta : Q\times\Sigma\_\varepsilon\times\Gamma\_\varepsilon\to \mathcal{P}(Q\times\Gamma^\*)$$ or $$\delta : Q\times\Sigma\_\varepsilon\times\Gamma\_\varepsilon\to \mathcal{P}(Q\times\Gamma\_\varepsilon)$$ The difference of the two last signatures is in the number of stack symbols they are allowed to push with each transition. But both definitions allow no symbol $(\varepsilon)$ to be popped from the stack. So with these signatures, moves are allowed under empty stacks and the PDA is usually initialized with an empty stack.

From the PDA in the picture, it looks like you are using one of the two latter definitions or something similar, where a PDA is allowed to pop nothing from the stack. So, when you arrive again in $q\_0$ with an empty stack (because you removed the last symbol $(\\$)$ in it) you are allowed to move to state $q\_1$ by reading nothing from the input string, *popping nothing from the stack* and pushing again the dollar symbol.

# Answer
> 1 votes
A PDA (including a NPDA) can only move if there is a symbol on the top of the stack, the possible moves depend on the current state, the symbol on the top of the stack and the input symbol (or $\epsilon$). No stack, no further moves possible.

---
Tags: pushdown-automata, nondeterminism
---