title: Expectation of $\langle s,x \rangle^2$

text:
# Question
Title: Expectation of $\langle s,x \rangle^2$
I'm studying dimensionality reduction (SVD in particular), and I saw the following question:

> Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ , where $s$ is a $d$-dimensional random vector with entries drawn uniformly independently from $\[-1,1\]$.

What is the value of $\mathbb E\[F(x)^2\]$?

I'm starting now from zero, so I need to study more. The exercise asks for a formal proof, but I wish to just understand the philosophy.

I see many questions in which valued are drawn uniformly and independently from $\[-1,1\]$. Is this distribution used due to its symmetrical range? Is the expectation in this range often $1/2$?

# Answer
Let us assume that each entry of $s$ is drawn independently from some distribution $\mathcal{D}$ whose expectation is $0$. Then $$ \mathbb{E}\left\[\left(\sum\_{i=1}^d s\_i x\_i\right)^2\right\] = \sum\_{i=1}^d x\_i^2 \mathbb{E}\[s\_i^2\] + \sum\_{i \neq j} x\_i x\_j \mathbb{E}\[s\_i s\_j\] = \\|x\\|^2 \mathbb{V}\[\mathcal{D}\], $$ since $\mathbb{E}\[s\_is\_j\] = \mathbb{E}\[s\_i\]\mathbb{E}\[s\_j\] = 0$ due to independence.

In your particular case, $\mathcal{D}$ is the uniform distribution over $\[-1,1\]$, whose variance is $$ \frac{1}{2} \int\_{-1}^1 x^2 \\, \mathrm{d}x = \left. \frac{x^3}{6} \right|\_{-1}^1 = \frac{1}{3}. $$
> 1 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Is a Turing machine too strong of a model to model physical computation?
I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing thesis is wrong and that a Turing machine does not accurately model any possible real world computation. To me, it seems that not only is the Turing machine not too restrictive, it's actually unrealistically strong. Namely, it has unbounded tape and time in which to perform its computation!

I suppose that the counterargument to this would be that unbounded is not the same as infinite, and in an idealized model of the physical universe we really have unbounded space and time in which to perform computations (neglecting minor details like the expected heat death of the universe and the possibility of finite space). But still, it seems as though we are basing our ideas of what is computable on an unreasonably strong model.

So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature? Or is there some deep inherent reason why unboundness is a requirement of any such model?

Edit: To address the comments so far - I know that a Turing machine with bound tape is equivalent to a DFA, and therefore definitely **does not** capture in any reasonable way the notion of possible real world computations. I was rather referring to models that might not resemble Turing machines at all.

# Answer
> 4 votes
No, it is not too strong. We fundamentally conceive of computation as an activity with unlimited resources.

For instance, take a very popular and simple algorithm such as long division. It takes two *arbitrarily large* numbers and can produce an *arbitrarily large* resulting number. During the computation, an arbitrarily large amount of scrap paper may be needed. The natural numbers are an *infinite* set. This is absolutely fundamental to our notion of mathematics, calculation, and algorithms. Without it, you lose expressive power: you lose the ability to write down many algorithms. With only a fixed amount of numbers, we cannot really say what division is.

Long division is a simple algorithm in that it is *linear*: the amount of scrap paper and time needed to execute it is directly proportional to the size of its input.The only reason it needs an arbitrarily large amount of space and time to execute is that the *input* can be arbitrarily large. What is more, some versions of long division only need *constant* space: with an eraser and paper of infinite quality, we can make do with a fixed amount of paper, if we don't need to write the input and output down on it, but instead, feed them through as streams of digits.

Turing machines do not share this property. Some do: they only use a constant amount of tape or steps, or only a linear amount, as a function of input size; or the amount of time and size they use is limited by some other function of the input size. But for many other Turing machines, it is *not*: the amount of resources their execution may use has no expressible (computable) relationship with the size of the input at all. This is a higher order sense of unboundedness. Can we at least say that *this* amount of unboundedness is excessive and unnecessary?

The answer, once again, is *no*: if we rule this out, we lose calculation power! Certain functions from inputs to outputs can only be computed by algorithms whose resource usage is unbounded by any function of the input size. So there is nothing frivolous or unrealistic about this property of Turing machines: computation *is fundamentally like that*.

In terms of practical imperative programming, what this means is that we fundamentally need dynamic memory allocation. It would be very nice if we could rewrite all C programs such that they first compute how much memory they possibly need, allocate it all, and only then start the computation process. Doing so would completely eliminate the dreaded runtime *Out of memory* error. The theory of computation shows us that this is fundamentally impossible: some algorithms do not have an equivalent of this type that computes the same input-output function.

# Answer
> 4 votes
**Is it too strong?**
The concern should not be that a Turing machine is a too strong model because of the way we construct a Turing machine. Turing machine is essentially a framework for defining a notion of algorithm in its basic, simple steps. Every algorithm executed on a Turing machine can be executed by hand, meaning it is effectively calculable (one direction of Church-Turing thesis). The real question is - is there an effectively calculable function whose computation cannot be encoded in a Turing machine. This all seems that it must hold (and therefore many computer scientists accept Church-Turing thesis as true), but cannot formally be proven just because the term "effectively calculable" is not formally defined.

**Why not bound it?**
I am not sure if this satisfies your quest for "deep inherent reason why unboundness is a requirement", but think about it this way: **What if we bound the tape?** Say, a Turing machine must have tape of length at most $M$, for some $M \in \mathbb{N}$. Let's look at $2$ examples:

1. We can choose/construct a Turing machine $T\_M$ that uses exactly $M$ distinct positions on a tape. Then, we can construct a Turing machine $T\_{M+1}$ that runs exactly as $T\_M$ with additional step - that it writes a symbol after the last symbol on its tape, once it finishes all the running steps of $T\_M$.
This Turing machine (algorithm) $T\_{M+1}$ therefore could not exists if we bounded the tape at $M$, but obviously - this algorithm is effectively computable.
2. Say you want to construct a Turing machine that adds two numbers. What if the length of numbers is more than $M$? We could not add them (nor even write them) with a Turing machine, but can obviously add them (say, by hand) via standard known algorithms for addition (*that also doesn't have restrictions on length/tape*).

Therefore, we must not bound the tape if we want to be able to compute things that we can in theory compute (by hand). The same arguments holds if we would want to bound the number of steps (time).

Computatioal complexity deals with resources required by an algorithm **depending on size of the input**, so you might want to look at that subject.

---

> So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature?

Turing machine **is** a finite model.

---

**Different model**
$\lambda$-calculus is a computational model invented by Turing’s doctoral advisor Alonzo Church. It does not resemble Turing machine and it is based on a concept of definition and application of functions. Turing and Church proved that their models are equal in computational power.

# Answer
> 3 votes
No, the Turing machine isn't unreasonably strong. You could build a physical Turing machine by giving it a finite length of tape and the ability to say "I've run out of tape – please give me more!" and that's something an ordinary computer can do, too, if it has removable media.

After any finite amount of time, a Turing machine will have used only a finite amount of tape, so you'll never need to give it an infinite amount. Yes, there are the limitations of the physical universe, which seems to place a limit on how much tape you can actually make, but we don't have a good model of what can be computed within some fixed but mind-bogglingly large amount of resource. And there doesn't seem to be much point in producing such a model: restricting to computations that can be performed within the universe's physical resources still allows for computations that would take longer than the extinction of the human race, and even that isn't a very practical limitation to place. The Turing machine is a reasonable approximation, which abstracts away all these fiddly details about computations that we can't physically do and simultaneously avoids us having to argue about what is physically possible, anyway.

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?
I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.

Is this reasoning correct or is there more to it?

# Answer
> 2 votes
Let $V\_P(n)$ represent the value of the optimal solution to a problem $P$ with size $n$. According to Bellman equations, this value is computed from the value of the optimal solutions of its subproblems $P'$: $V\_P(n) = \oplus \\{v\_{P'} + V\_{P'}(n')\\}$ where $\oplus$ is an operator such as $\max$, $\min$, +, ... $v\_{P'}$ is an operator which steps from $P$ to $P'$, and $P'$ are the subproblems of $P$ with size $n'$ which is always strictly less than $n$, the size of the original problem.

From here, it seems affordable to create a graph $G(V,E)$ where $V$ are the values of the optimal solutions of different problems, and there is an edge between two vertices $u$ and $v$ if and only if $v$ represents a problem $P'$ which is acknowledged as a subproblem of task $P$ represented by vertex $u$. For example, when using Dynamic Programming for computing the Fibonacci numbers, if $u$ represents $Fib(n)$, then there are two edges from it to other vertices representing $Fib(n-1)$ and $Fib(n-2)$.

If this is the graph you meant in your question then, clearly, the resulting graph is a Directed Acyclic Graph because:

1. Each vertex is directed in only one direction: from $u$ to $v$ as only one problem ($P'$) can be a subproblem of another, $P$.
2. It is impossible to form a loop as $n'\<n$.

All this said, however, I do not think that this characterization is too useful as it also applies to other techniques such as Divide and Conquer and plain recursion. As you are asking whethere there is more about it or not, let me highlight that an important issue to consider when deciding whether to use Dynamic Programming or not, is if the problem $P$ shows *suboptimal structure*, see this definition in the second paragraph.

Hope this helps,

---
Tags: dynamic-programming, dag
---


# Question
Title: Why do mainstream speech models no longer require a personalized training step?
Back in the Windows XP era, when setting up Windows OS-built-in speech/dictation, I had to speak out a bunch of programmed-in text samples to the speech-to-text engine to personalize my voice profile.

Today, with networked speech-to-text engines like Siri or Cortana, I can just start dictating.

The quality of the text-to-speech conversion seems equivalent, though my memory may be faulty on that aspect.

Have speech models advanced past the need for any personalization of the training data? Or, do they just do the personalization under the covers now, without an explicit training wizard? Or, do they not do training, even though it *would* still be beneficial (e.g. because it's inconvenient)?

# Answer
> 4 votes
> Have speech models advanced past the need for any personalization of the training data?

There were two aspects which improved accuracy significantly:

1. Deep learning and neural networks greatly improved the accuracy.
2. Amount of training data that major companies use has grown over years by order of magnitude. Companies collected so much data that effect of adaptation decreased.

> Or, do they just do the personalization under the covers now, without an explicit training wizard?

There is a small adaptation usually going on, but it is very marginal in effect. It is basically matching your voice with some baseline voices and produces a vector of similarities and then this vector is used in realtime and adjust neural network input (so called i-vector adaptation). This kind of adaptation is pretty fast, you can adapt from 2-3 seconds of speech. For technical details you can read

https://www.microsoft.com/en-us/research/uploads/prod/2018/04/ICASSP2018\_CortanaAdapt.pdf

> Or, do they not do training, even though it would still be beneficial (e.g. because it's inconvenient)?

There are some cases where adaptation would be beneficial but again there are multiple aspects here:

1. It works good without adaptation.
2. Neural network recognition does not fit well with adaptation actually. You need many many GPU nodes to train a big neural network, it is very hard to adjust it afterwards. You can adjust a small layer with adaptation data but effect is usually small just because neural network is pretty tightly tied thing and you can't simply modify a bit without retraining.
3. Like I said above the amount of training data is so huge that your custom data is probably already in the training set and adaptation will not help much
4. Adaptation can also harm. Imagine your speech had an unusual crack or beep from background or something like music and system adapted to it. Then it will actually decode your normal clean speech with less accuracy than unadapted system.
5. Adaptation is not very convenient for users. Why do you need to adapt when you can simply start using the system.

So the system design moved to the "it just works" and it is a good direction.

---
Tags: algorithms, machine-learning, speech-recognition
---


# Question
Title: Algorithm to identify contiguous repeated series of lines in a long string
I would like an algorithm that can identify repeated parts of big stack traces like this:

```
java.lang.StackOverflowError
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)

```

With a bit of inspection, it's clear that this segment is being repeated three times:

```
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)

```

The end goal is so I can print out stack traces of recursive functions in a nicer fashion

```
java.lang.StackOverflowError
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
------------------------- Repeated 3x -------------------------
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)
at typechecker.Typers$Typer.silent(Typers.scala:700)
at typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4754)
at typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
at typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
at typechecker.Typers$Typer.typed1(Typers.scala:5603)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5723)
at typechecker.Typers$Typer.typedQualifier(Typers.scala:5731)
at transform.Erasure$Eraser.adaptMember(Erasure.scala:714)
at transform.Erasure$Eraser.typed1(Erasure.scala:789)
-------------------------------------------------------------
at typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
at typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
at typechecker.Typers$Typer.body$2(Typers.scala:5613)
at typechecker.Typers$Typer.typed(Typers.scala:5618)
at typechecker.Typers$Typer.$anonfun$typed1$38(Typers.scala:4752)

```

I'm not sure how feasible this is, but I'd be happy for any and all possible solutions even if they have their own limitations and constraints. Preliminary Googling didn't find me anything, but quite likely I just don't know what to google

# Answer
> 5 votes
Under normal circumstances, JVM fills only the last 1024 calls in a stacktrace, and in Dotty/Scalac most stackoverflows have a repeating fragment of length ≈ 70 or less. A stacktrace T of a StackOverflowException can be decomposed into three parts S · R^N · P, where R is the repeating part of the stacktrace, S is some suffix of R, and P is either some prefix of R or an unrelated sequence of calls. We are interested in a solution such that the total length C = |S · R^N| of the repeating part and N are both maximal, and |S| is minimal.

```
// Scala Pseudocode (beware of for comprehensions)
//
// Stack is assumed to be in reverse order,
// most recent stack frame is last.
val stack: Array[StackTraceElement]
val F: Int // Maximum size of R.

val candidates = for {
  // Enumerate all possible suffixes S.
  S <- ∀ prefix of stack
  if |S| < F

  // Remove the suffix from the stack,
  R <- ∀ non-empty prefix of stack.drop(|S|)
  // Find a fragment that ends with S.
  if R.endsWith(S)

  // Find out how many fragments fit into the stack.
  // (how many times we can remove R from the stack)
  N = coverSize(R, stack.drop(|S|))
  if N >= 2 // Or higher.
} yield (S, R, N)

// Best cover has maximum coverage,
// minimum fragment length,
// and minimum suffix length.
val bestCandidate = candidates.maxBy { (S, R, N) =>
  val C = |S| + |R| * N
  return (C, -|R|, -|S|)
}

```

The entire algorithm can be implemented in a way that does not allocate any memory (to handle OOM). It has complexity O(F^2 |T|), but exceptions are rare enough and this is a small constant (F \<\< 1024, T = 1024).

I have implemented this exact algorithm in my library https://github.com/hobwekiva/tracehash (https://github.com/hobwekiva/tracehash/blob/master/src/main/java/tracehash/internal/SOCoverSolver.java) for the same purpose of simplifying scalac/dotc errors ;)

EDIT: Here is an implementation of the same algorithm in Python:

```
stack = list(reversed([3, 4, 2, 1, 2, 1, 2, 1, 2, 1, 2]))
F = 6

results = []
for slen in range(0, F + 1):
    suffix, stack1 = stack[:slen], stack[slen:]

    for flen in range(1, F + 1):
        fragment = stack1[:flen]

        if fragment[flen - slen:] != suffix:
            continue

        stack2 = stack1[:]
        n = 0
        while stack2[:flen] == fragment:
            stack2 = stack2[flen:]
            n += 1

        if n >= 2: # A heuristic, might want to set it a bit higher.
            results.append((slen, flen, n))

def cost(t):
    s, r, n = t
    c = s + r * n
    return (c, -r, -s)

S, R, N = max(results, key=cost)
print('%s · %s^%d · %s' % (stack[:S], stack[S:S+R], N, stack[S+R*N:]))
# Prints [] · [2, 1]^4 · [2, 4, 3]

```

EDIT2: Following some of the ideas from mukel's answer, here is a function https://gist.github.com/hobwekiva/b041099eb5347d728e2dacd1e8caed8c that solves something along the lines of:

```
stack = a[1]^k[1] · a[2]^k[2] · ...
argmax (sum |a[i]| * k[i] where k[i] >= 2,
        -sum |a[i]| where k[i] >= 2,
        -sum |a[i]| where k[i] == 1)

```

It is greedy so it is not necessarily an optimal solution, but it seems to work reasonably well in simple cases, e.g. given

```
stack = list(reversed([
  3, 4, 2,
  1, 2, 1, 2, 1, 2, 1, 2,
  5,
  4, 5, 4, 5, 4, 5,
  3, 3, 3, 3]))

```

it produces an answer

```
[([3], 4), ([5, 4], 3), ([5], 1), ([2, 1], 4), ([2, 4, 3], 1)]

```

# Answer
> 5 votes
Build suffix tree using Ukkonen's algorithm, this way in $\mathcal O(n)$ you will find all substrings in provided text with indices.

In the case of approximate matching, there is also extended version of Ukkonen's algorithm.

# Answer
> 4 votes
If you consider that “a line of stacktrace” = “a character”, you can use:

http://en.wikipedia.org/wiki/Longest\_repeated\_substring\_problem

One way to solve this problem efficiently is by constructing a Suffix Trie: http://en.wikipedia.org/wiki/Suffix\_tree

Every time you traverse an already estabilished path you are actually discovering a repetition in your string.

Now, simply list all the repetions in a separate data structure and extract the longest one... or all if you want.

# Answer
> 4 votes
An efficient string factorization algorithm may help. Given a string $S$, $n = |S|$ find maximum $p$ such that $S = T^p$ e.g. $T$ concatenated $p$ times, we call $T$ the **seed** and p the **period**. This can be done in $O(n)$ using the prefix function of the (Knuth-)Morris-Pratt algorithm, but don't be scared by the name it's very simple and beautiful algorithm, here's my solution for the corresponding problem SPOJ PERIOD.

Armed with a fast string factorization we can then proceed to decompose a string as the concatenation of factored chunks (dynamic programming) using a custom cost function e.g. minimize the total length of the seeds, minimize the sum of squares of the seeds' lengths...

$S = {T\_1}^{p\_1}{T\_2}^{p\_2}\cdots{T\_k}^{p\_k}$

Total complexity is $O(n^2)$.

If $O(n^2)$ is way too costly you can shift to a greedy like strategy e.g. as soon as you find a factorizable chunk, squeeze it and continue from that point, and also limit the maximum seed size (e.g. $|T|\le 200$) and prune the search if you don't find a period $\ge 2$ in the first e.g. 400 characters.

# Answer
> 0 votes
```
  string contiguous_repeated_string(string A){
    string r(1,A[0]);
    for(int i=0;i<A.size();i++){
      for(int l=2;l<=A.size();l++){
        string s=A.substr(i,l);
        if ((s+s).substr(1,2*s.size()-1).find(s)!=s.size()-1 and s.size()>r.size()){
          r=s;
        }
      }
    }
    return r;
  }

```

Call `contiguous_repeated_string("abcdefgabcdabcdabcd")` you will get `abcdabcdabcd`.

Call `contiguous_repeated_string("ATCGATCGA")` you will get `ATCGATCG`.

And then you can use KMP's `Longest Proper Prefix Postfix array` to fold the resulting string with `O(N)`.

Total time complexity is `O(N^2)`.

---
Tags: algorithms, strings, substrings
---


# Question
Title: is reducing to normal form simply applying beta-reduction?
See example below:

reduce to normal form:

(λ c . (λ a . (λ d . (λ h . (h (d (a (a (λ z y . y))) (d (a (a (λ f x . x))) (a (a (a (λ z x . x)))))) (h (a (a (λ z y . y))) (a (a (a (λ z x . x))))))) (λ n m . n (d m) (λ z y . y))) (λ n m . n a m)) (λ n z . c (n z) z)) (λ z g x . z (g x))

Wikipedia says that to be in normal form: all reductions that can be applied have been).

I used these two calcualtors to try and get the correct reduction: http://lambda.jimpryor.net/code/lambda\_evaluator/ http://lambda.jimpryor.net/code/lambda\_evaluator/

both return: λz x.z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z x)))))))))))))))))))))))))))))))))))))))))

Can I get to this answer by only using beta-reduction? This is the only reduction I am currently trying to understand but from this example there are two more: https://stackoverflow.com/questions/34140819/lambda-calculus-reduction-steps

# Answer
Using only $\beta$-reductions is sufficient to get to a normal form **if** variables are named “correctly”.

**What do we mean by that?**

Let’s take as an example the term $\lambda x y. x\ y$.
Informally, it is a function that takes two arguments - variables $x,y$ and gives us the application of first argument to the second - $x\ y$. Now we want to apply something to this term, say $$(\lambda x y. x\ y)\ a$$

After we perform the $\beta$-reduction, substituting $a$ for $x$ in our term, we get $\lambda y. a\ y$ and we realize that whatever we substitute for $x$, we should be left with a function that applies it to the input variable $y$.

What if we want to substitute a variable named $y$ for $x$? We would be left with $\lambda y. y\ y$ which is a function that takes a variable and applies it to itself! Not at all the function we thought we would have for any $a$.

This example demonstrates that sometimes $\alpha$-*conversion* is necessary as a helper tool, and I emphasize the word “conversion” because it is not per se reduction.

---

You could also check my answer on this question that has computation similar in nature to yours and maybe try pLam interpreter to see all the reduction steps with colored terms that go into reductions.
> 1 votes

---
Tags: lambda-calculus
---


title: Model Checking CTL* algorithm

text:
# Question
Title: Model Checking CTL* algorithm
Currently I'm trying to understand the CTL\* model checking algorithm from this book. The basic idea is clear to that we can use the LTL algorithm to whenever we have a subformular $E\phi$ or $A\phi$ but I have still a question I can't figure out:

Why is there no case for $\phi\_1 U \phi\_2$ in this algorithm? Of course we can write the until modality as a release modality but this case isn't here either. So is this algorithm incomplete or have I missed something?

# Answer
The algorithm is full and correct. If you look back to definition 6.80 in the same book, you will see that the until operator is part of path formulae, which in the CTL\* MC algorithm are checked via a standard LTL model checker as written in the last switch case ($\exists \varphi$). The $\varphi$ stands for any path formula.

The algorithm also states that you take the negation of $\varphi$. So then you need to take the complement of the satisfaction set.
> 1 votes

---
Tags: model-checking
---


title: Is Rice-Shapiro theorem bidirectional?

text:
# Question
Title: Is Rice-Shapiro theorem bidirectional?
Rice-Shapiro theorem states that

> ## version A
>
> Let $\Gamma$ be a set of computably enumerable sets, and $I = \\{e : W\_e \in \Gamma\\}$ its index set in some admissible enumeration of c.e sets. If $I$ is c.e, **then** for all $x$, $x \in I$ if and only if there is $y \in I$ such that $W\_y$ is a finite subset of $W\_x$.
>
> Or equivalently
>
> $I$ is c.e $\Rightarrow$
>
> $~~~~(1):~ \forall x,y ~ (x \in I \land W\_x \subseteq W\_y \rightarrow y \in I)$
>
> $\land ~~(2):~ \forall x ~ (x \in I \rightarrow \exists y~(y \in I \land W\_y ~\text{is finite} \land W\_y \subseteq W\_x))$

My question is if it's converse is also true, that is, if (1) and (2) hold, then $I$ is c.e.

---

So I found another (weaker) formulation of the theorem in H. Rogers *Theory of Recursive Functions and Effective Computability* p. 324, which states:

> ## version B
>
> $I$ is c.e $\iff ~(3):~ \forall x ( x \in I \leftrightarrow \exists u (D\_{f(u)} \subseteq W\_x))$ for some totally computable function $f$

where $D$ is the canonical enumeration of the finite sets (see definition 2.4).

(3) implies that $I$ is c.e, for it is just a $\Sigma\_1$ representation of $I$. On the other hand, if $I$ is c.e, by s-m-n theorem take the totally computable function $g$ to be defined such that $W\_{g(x)} = D\_x$. Now the set $g^{-1}(I) = \\{ x : \exists y (g(x) = y \land y \in I)\\}$ is also c.e, thus there must be a totally computable function $f$ such that $Range(f) = g^{-1}(I)$. So by version A of the theorem, we also have (1) and (2), which imply that this $f$ is the function that satisfies (3).

---

I also found these two answers which state the theorem in bidirectional form, but with an additional condition:

> ## version C
>
> $I$ is c.e $\iff (1) \land (2)$
>
> $~~~~~~~~~~~~~~~~\land (4):~ \\{ e : D\_e \in \Gamma \\}$ is c.e

Now this set in (4) is just the $g^{-1}(I)$ defined above, where we just saw that it is indeed c.e. by the sole fact that $I$ is c.e. So my primitive guess is that (4) is the ingredient for proving the other direction.

---

Considering all the observations above, my question is whether the right to left direction holds generally, i.e. does (1) and (2) imply $I$ is c.e? And is there a counterexample if that fails? Assuming (4), can we deduce that $I$ is c.e? And does that mean the wanted counterexample should refute (4)?

# Answer
> 3 votes
No, the converse direction does not hold:

Pick some non-c.e. set $B \subseteq \mathbb{N}$. Now consider $\Gamma = \\{A \ c.e. \mid A \cap B \neq \emptyset\\}$. By construction, $\Gamma$ satisfies the conclusion of Rice-Shapiro (it suffices to consider singleton sets rather than all finite sets). However, for the resulting index set $I$ we find that $B \leq\_m I$, so $I$ cannot be c.e..

Essentially, Rice-Shapiro says that the Markov-effectively open subsets of the subspace of ce subsets of $P(\omega)$ (with the Scott topology) are open, but for already for cardinality reasons alone, not all open subsets can be Markov-effectively open.

---
Tags: computability, semi-decidability
---


# Question
Title: Is OS mode required for accessing general purpose registers
In which of the following cases a process executing in user model is required to enter into the OS mode?

(a) Decreasing the value of unsigned integer value in a register to less than 0

(b) Accessing general purpose register

(c) Executing printf()

(d) Adding values in two registers using ADD

In my opinion, both (c) and (b) should use OS mode. But my solution manual says only (c) uses OS mode.

I believe that (b) requires the use of OS mode as well, because the processor may have more than one process executing at the same time. As both of them have access to the general purpose register, it is quite possible that one process may overwrite the contents of another process if switching takes place.

The only way it can be avoided is setting up of a semaphore. At the end of the day, it boils down to a critical section problem. So, for accessing and setting up a semaphore, OS mode is required.

So, in my opinion, (b) should be true as well.

Am I correct or where is my reasoning wrong regarding the problem?

Thank you!

# Answer
Computations on general-purpose registers ((a), (b), (d)) doesn't require any privileges.

Input/output requires privileges, to access a peripheral or to communicate with the part of the system that manages files. So (c) does generally require going to kernel mode. It's possible for some `printf` calls to remain entirely within the calling process, for example if output is buffered and the output of this call is going entirely inside the buffer. But in general a `printf` call does need to do actual I/O and thus does need a transition to kernel mode.

A processor does not really “have more than one process executing at the same time”. The processor *alternates* between executing different processes, but at a given point in time, it's only executing one process (or it's in kernel mode). On a multiprocessor machine, each processor¹ executes one process at a given time, but the different processors can be executing different processes. While a process is executing, it can access the general-purpose registers directly. It doesn't need the kernel for that. (And how would it ask the kernel, anyway? A process communicates with the kernel by placing the parameters of a system call in general-purpose registers and then invoking the system call instruction.)

Processes execute code as if the other processes didn't exist. When the kernel decides to switch to another process, it suspends the running process and unsuspends the process that it wants to run next. Part of this suspension mechanism is to save the values of the general-purpose registers into a dedicated memory area that belongs to the process that is being suspended. There is one such register store for each process². Part of the unsuspension mechanism is to restore the registers of the process that is being unsuspended. When a process is unsuspended, it keeps running where it left off, with the same values in registers as when it was suspended. This suspension/unsuspension mechanism is called a context switch.

A process never overwrites the registers used by another process because only the currently running process's register values are in the processor registers. The other processes' register values are in their register store. There has to be a context switch to change which process's register values are in the processor registers.

Switching between processes does not involve semaphores. It's the other way round: in order to use semaphores to synchronize between different processes, the processes need to call the kernel.

¹ <sub> Each core, each thread — whatever you call the single-threaded processing unit. </sub>
² <sub> More generally, for each kernel thread. </sub>
> 1 votes

---
Tags: computer-architecture, operating-systems, os-kernel, critical-section
---


# Question
Title: How long does it take to crack a password by brute force
My computer teacher says that hackers can know any password by simply writing a permutation combination program and it will take around 21 days. Is this true?

# Answer
Perhaps your teacher was talking about some system where the format of passwords is restricted (e.g., where they can't be longer than whatever number of characters allows a typical computer to try all combinations in 21 days). Or perhaps they were talking about some specific kind of password, such as words from the dictionary, maybe with c0mm0n m0d1f1c4t10n5.

In general, it's impossible to give a limit because passwords could be arbitrarily long. Indeed, even without needing crazy-long passwords, there are $62^{10}\approx 10^{18}$ possible ten-character passwords that can be made from numbers and upper-case and lower-case letters. If you can try a billion passwords a second, it'll still take you a billion seconds to try all of these passwords, and that's about 32 years.

Note that the above discussion ignores the fact that, in reality, we don't guess passwords but, instead, guess strings that have the same hashes as passwords. At the level we're talking about here, though, this doesn't make any real difference.
> 3 votes

# Answer
This is possibly true for plaintext passwords of arbitrary length. This question is a little more ambiguous to answer.

There are some factors which can increase the time taken to complete a bruteforce. For example, one factor would be dependent on the algorithm used.

* What algorithm is being used?
* Is this algorithm an encryption algorithm, or is it a hashing algorithm?
* What is the collision rate of this algorithm?

As well as this, algorithmic techniques can be used to improve the speeds at which a bruteforce can perform. For example, the use of a rainbow table can minorly or drastically improve the speed of a bruteforce.

However this result factors into the above the questions. If we use a hashing function, a rainbow table can be produced with a list of all permutations and their corresponding hashes. An adversary would therefore use this pre-determined hash table, and only have to check the hashes against the hashes stored in say; a database leak. Then once a match is found, the adversary can link this directly back to a plaintext password in their hash table.

This is theoretically very simple, but can also be very time consuming. This is, however, only one example of how speeds can be improved.

Another way is by using better hardware, i.e. using powerful GPUs to bruteforce as they are very good at parallelising mathematical operations. (How are GPUs used in bruteforce attacks?)

If we take a look at this link, we can identify that cost of a hash function is another factor we consider when interpreting brute force times.

Agreeing with David Richerby's statement that it's impossible to give a limit because passwords can also be arbitrary long, but there also a number of other things which factor into the bruteforce speed.
> 1 votes

# Answer
> hackers can know any password by simply writing a permutation combination program

This depends what the hackers have access to.

If the hackers can access the password itself, then they don't need any “permutation combination program”. They might have access to your password because, for example:

* They have installed malware on your computer.
* They saw you type the password.
* They have exploited a security hole in the server that you're logging into with this password.
* You're logging into a server using an insecure network connection and they can see the data that you're sending.

If the hackers do not have access to the password, and they instead try to crack it, how would they know when they've found the right one?

They can try to log in to the server using different passwords until one works. This is called an *online attack*. How fast this can go depends on how many password attempts the server allows.

The other way is if the hackers have access to the password's hash. A cryptographic hash function is a function which is easy to calculate, but such that if you have the output of the function, there is no way to find a matching input except by guessing. Cryptographic hash functions also have the property that it's unfeasible to find two inputs with the same hash values (such *collisions* exist in theory, but there's no realistic way to find one). Computers normally store the hash of a password. When you log in, the computer compares the stored hash with the calculated hash of what you type in the password field, and lets you in if the two hash values are equal. This is presumably the case that your teacher was referring to.

How long it takes to find the input corresponding to a hash value depends on several things:

* How fast the hackers' computer is, obviously.
* How hard it is to calculate each hash value. Good password hashing functions are *inherently slow*, to make this kind of attacks harder.
* How long it takes for the hackers' enumeration program to reach *your* password.

So let's take some figures for how fast a computer can be and how slow a hash algorithm is to calculate how many passwords the hackers can try in 21 days ≈ 1.8Ms (Ms = megasecond = 1 million second).

With an awfully bad password hashing algorithm such as MD5, a few years ago, you could do 10 billion hashes per second per computer. (The hackers can go faster by splitting the passwords that they're trying on multiple computers. I'll do the calculations for just one computer.) In 21 days, they can enumerate about $18 \cdot 10^{15}$ passwords. For example, they can enumerate all passwords consisting of 8 printable ASCII characters with time to spare, since there are 94 characters and $94^8 \approx 6 \cdot 10^{15}$.

With an almost equally bad password hashing algorithm such as SHA-512, it might take something like 100 times as long to calculate each hash. Then the hackers don't have time for all 8-character passwords anymore, but they have time for a large fraction of 7-character passwords, or for a large fraction of passwords containing 6 letters, 1 digit and 1 punctuation sign. (Do the math.)

With a good password hashing algorithm, it might take something like 0.1 s to calculate each hash, i.e. the hackers can only make 10 attempts per second. That's *1 billion times* slower than MD5, 10 million times slower than SHA-512. At this rate, the hackers can only try 18 million passwords in 21 days. That's enough to find all passwords consisting of a dictionary word and a punctuation sign, but not quite enough for all passwords consisting of two dictionary words.

Finally another plausible hypothesis about the attack is that the server uses a bad password hash that is unsalted, and the hackers download a table of hashes for common passwords. A good password hash is *salted*, that is, the hash function takes two inputs: the password, and a second value called “salt”. The salt is stored together with the hash, and different for each account. It's generated randomly each time the user changes their password. The point of the salt is that it's impossible to make a table of hashes. Technically speaking, it's possible, but useless, because each salt value would require its own table and each table would only ever be useful for a single account. How many passwords can the hackers try in this case? In this case, table lookup is fast. What matters is the size of the table. Thanks to a technique called rainbow tables, it's possible to pack more hash values than you'd think. For example, a 690GB table lists most alphanumeric passwords of up to 9 characters.
> 1 votes

---
Tags: security
---


title: Distance Vector Routing Example

text:
# Question
Title: Distance Vector Routing Example
Consider a network with five nodes, N1 to N5, as shown as below.

The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are as follows.

N1: (0,1,7,8,4)

N2: (1,0,6,7,3)

N3: (7,6,0,2,6)

N4: (8,7,2,0,4)

N5: (4,3,6,4,0)

Each distance vector is the distance of the best known path at that instance to nodes, N1toN5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

It's a GATE-2011 question.

I have a doubt here.

Suppose when the cost of the link N2-N3 changes to 2, this will be immediately known to N2 and N3 and they will update their routing table entry to reflect this change. Now, this would cause triggered update.

Suppose After receiving the vector from N2, N3 finally changes it's vector to (3,2,0,2,5).

Now my query is whether this vector (3,2,0,2,5) would be communicated to N4 or the old vector of N3(7,6,0,2,6) would be communicated to N4?

# Answer
Let us review the specification of the algorithm.

> In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

Right after the cost of link N2-N3 changes to 2, the distance vectors at different nodes are as follows. The only difference from before is the distance from N2 to N3 and the distance from N3 to N2 has been updated from 6 to 2.

N1: (0,1,7,8,4)
N2: (1,0,2,7,3)
N3: (7,2,0,2,6)
N4: (8,7,2,0,4)
N5: (4,3,6,4,0)

In the next round of exchange, all nodes exchange their distance vectors with their respective neighbors. In particular, N3 sends (7,2,0,2,6) to its neighbor N2 and N4. Right after this round of exchange, the knowledge of each node are as follows besides their knowledge of respective distances to their neighbors.

N1 knows (1,0,2,7,3) from N2.
N2 knows (0,1,7,8,4) from N1 and (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N3 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.
N4 knows (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N5 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.

Discarding current distance vectors, all nodes regenerate their distance vectors at the same time. So after, for example, a fraction of a second, the distance vectors at different nodes becomes the following.

N1: (0,1,3,8,4)
N2: (1,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

If no change of the network happens before the next round of exchange, then in the next round of exchange, each node will send above distance vectors to its neighbors. In particular, **N3 will send (3,2,0,2,5) to its neighbor N2 and N4 in the next round**.

---

However, if before the next round of exchange, it happens that the link between N1 and N2 goes down. Then N1 and N2 will update their distance vector immediately, but only with the distance between N1 and N2. Now the distance vectors at each node are as follows.

N1: (0,infinity,3,8,4)
N2: (infinity,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

After the next round of exchange, N3 knows the distance vector (infinity,0,2,4,3) from N2 and (8,4,2,0,4) from N4. So N3 will update its distance vector to (10,2,0,2,5).
> 5 votes

---
Tags: routing, gate-cs
---


title: Does Deadlock imply Starvation

text:
# Question
Title: Does Deadlock imply Starvation
If there is a deadlock between the processes does that mean that there is starvation also?

My Thinking:
deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock
Is my thinking right?

# Answer
> 12 votes
You should first state the deadlock freedom property and the starvation freedom property more precisely.

I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2.

> **Freedom from Deadlock** If some thread attempts to acquire the lock, then some thread (*not necessarily the thread referred to in the `if` statement*; emphasis added) will succeed in acquiring the lock.
>
> **Freedom from Starvation** Every thread that attempts to acquire the lock eventually succeeds.

Note that *by definition*, starvation freedom implies deadlock freedom. Thus, if a mutual exclusion algorithm suffers from deadlock, it *also* suffers from starvation.

A direct argument is that: deadlock means that some thread attempts to acquire the lock, but no threads succeed. That is *a special kind of* starvation.

# Answer
> 1 votes
**Starvation**, as the name suggested, is when a process **can acquire the lock**, but it is being overlooked. It starves even with resources being available.
There is no deadlock in starvation; each process can acquire the lock and release it successfully.
Let three processes A, B and C, compete for a resource. Processes A and B are being granted that resource interchangeably, and subsequently C starves indefinitely.
Imagine the *lock as the door that is being knocked to get food*, and only one person per a time can enter, lock it, eat, and then exit.
A **deadlock** is when that person died inside, it will never be opened again, and everyone will be dead. Unless a supervisor (OS) intervenes.
A **starvation** is when everyone can take a turn smoothly. However, there is a poor guy who whenever he knocked, someone else was inside. They will starve.
Gruesome, but easy to remember.

# Answer
> 0 votes
A process is in starvation when it is waiting for a resource that is continuously given to other processes. This is different then a deadlock where a resource is not being given to anyone because it is being held by a blocked process. So there is not necessarily starvation in a deadlock situation. There might be, but it would be independent of the deadlocked processes.

# Answer
> 0 votes
In both cases you will have a infinite waiting. The difference's Deadlock is when two or more processess are waiting for each other, like a cicrular waiting. On the other hand, starvation is also a kind of waiting, but proccess is expecting a resource that will never be available. So the difference is deadlock occurs between processess and starvation you'll have a process and a "servant" resource.

# Answer
> -1 votes
Both the cases, CPU needs to wait infinitely, as deadlock definition says:A system is in deadlock if more than one process waiting for a instances that never going to happen. Similarly, in starvation also, the process need to wait infinitely to get their chance to execute.

# Answer
> -1 votes
definitely NO deadlock means infinite waiting time and starvation is not a infinite waiting time the process has to definitely take the opportunity to be execute after the some amount of time.

---
Tags: operating-systems, synchronization, process-scheduling, deadlocks
---


# Question
Title: Why is the number of states for DFA is 3n + 1 for this language
I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here.

Let $S\_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language $L\_n = \\{ S\_i | 1 \leq i \leq n \\}$. For example,

$L\_3 = \\{\\, 011,\\, 001111,\\, 000111111\\; \\}$

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L\_n$?

I know regexes a bit and I can't think of a way of expressing this with regular expression. But I thought even if it's possible it should involve some kind of backreference, and isn't backtracking impossible with DFA?

So the quiz gives the correct answer $3n + 1$ and explain it like so.

> We need states to count how many 0 we meet and how many 1 we meet, so we need 3\*n+1 states including the start state.

And this explanation doesn't explain anything to me. I mean okay the $+1$ part obvious, but why is there $3n$? I mean I agree that we probably need states to count how many 0 and 1 we meet, but exactly how we're gonna do it? If anything we should have 4 states in my opinion. One recognize 0, one to recognize 1 and another two states to count the numbers of them.

Right now I'm reading articles and papers about NFA, DFA, regular expressions and backreference, but maybe the answer is much simpler?

EDIT1. Okay, I've tried my best and constructed kind of obvious DFA for this task.

The total number of states would be $\sum\_{i=1}^{n}i+2i$ which looks like arithmetic progression to me with a difference $d=(i+1)+2(i+1)-(i-2i)=i+1+2i+2-i-2i=3$ So the sum will be equal to $\frac{n(a\_1 + a\_n)}{2}=\frac{n(3 + (n + 2n))}{2}=\frac{n(3+3n)}{2}=\frac{3(n^2+1)}{2}$

I don't see $3n + 1$ here.

Okay, I think I finally got this. The main problem I think was that I haven't tried to actually draw automaton initially and If I would it would be much easier. So once I've noticed that it could be changed into this  And this would give $3n+1$ obviously.

# Answer
This is indeed a curious example. The reason why it works is the following (I show you on the example of $L\_3$, but the argument is generic). Start with the minimal DFA accepting $\\{S\_n\\}$, which clearly has $|S\_n| + 1 = 3n + 1$ states. The states can be encoded by factorisations of $S\_n$ in two factors (the reason of this encoding will appear shortly). Thus for $S\_3$ you get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{0} (000, 111111) \xrightarrow{1} (0001, 11111) \xrightarrow{1} (00011, 1111) \xrightarrow{1} (000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ Now it is possible to accept the words $S\_i$ by adding new transitions (but no new state!). For instance, if you want to accept $011$, you add the transition $(0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1)$ to get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ and to accept $001111$, you add the transition $(00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111)$ to get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ The trick is that you still get a deterministic automaton, due to the choice of the words added to the original automaton.
> 6 votes

# Answer
The explanation just gives some intuition. For a proof, you can use the Myhill-Nerode theorem for a lower bound, and a construction (a DFA for the language) for an upper bound.

In this particular case, the pumping lemma also shows a lower bound of $3n+1$ (once you realize that the pumping constant is the size of the minimal DFA). More generally, if $L$ is a finite language and the largest word in $L$ has length $m$, then the pumping lemma (or the Myhill–Nerode theorem) shows that any DFA for $L$ needs to have at least $m+1$ states.

You mention that you don't know how to express the language $L\_n$ as a regular expression. Every finite language can be expressed as a regular expression by listing all of its word. For example, a regular expression for $L\_3$ is $011+001111+000111111$.
> 1 votes

# Answer
As shown above, the DFA could be constructed like that. Every encountering an addition to the continuous 0 sequences, first traverse the additive 1's transition state, then reuse the previous path which is equally a counter to 0's number.

For the proof to the bound, It is deduced from the path the transition experiences.

To put it ahead, the DFA may not contains a self-cycle, for that the number of 0 or 1 is presumed to be restored. If there exists a self-cycle, it will not be able to figure out how many 0 or 1 there appears. Followed is the detailed proof of 3n + 1 lower bound.

First, for every single digit, it implies a directed path and a state transition. So as the longest number digits in the language, it has 3n digits. Plus the start state, there must be at least 3n + 1 state to traverse. So this gives the lower bound to the DFA. And the picture above shows one of the construction.
> 0 votes

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


title: HyperLogLog leading zeros distribution

text:
# Question
Title: HyperLogLog leading zeros distribution
I'm reading this article.

In particular I'm having some trouble trying to replicate the results of the first image in that article.

For x=9, the graph says that the probability is 0.20 aprox. But from my calculations I get something different. After some thought I think I may be misinterpreting the idea of the calculation.

First attempt: Doing the sum of a X -\> Bin(1024, 1/29), calculating f(X=1)+...+f(X=1024). My calculation equals 0.86 which is not 0.20

Then I thought that maybe he was talking about just having 1 result with 9 leading zeros. This means that from the 1024 numbers, we can have only 1 success in any of the 1024 numbers. Which is 0.27... closer but far from 0.20.

What am doing wrong here?

# Answer
It looks like you could be more careful. "For x=9, the graph says that the probability is 0.20 approx." In fact, the graph says that probability is slightly less than 0.12.

---

Here is the relevant quote from the article on hyperloglog

> This is a plot of probability of having x leading zeros, with 1024 distinct items. You can see that the probability peaks at around x = 10, as expected - but the distribution is quite wide, with x = 9, 11 or 12 being at least half as likely as x = 10. (The distribution peaks 0.5 units higher than expected, so this implies that 2k will overshoot by a factor of 20.5, or about 1.4. This shows up as a correction factor later.)

The probability of having exactly $x$ most leading zeros with 1024 terms is the difference of the probability of have no more than $x$ leading zeros and the probability of have no more than $x-1$ most leading zeros.

$$ P\[x\] = \left(1-\left(\frac12\right)^x\right)^{1024} -\left(1-\left(\frac12\right)^{x-1}\right)^{1024} $$

In particular, the probability of exactly 9 most leading zeros $P\[9\]\approx 0.1169$.

Here is a Python program that computes the probabilities shown in the above graph.

```
P = [0] * 23
for x in range(1, 23):
    P[x] = (1 - 0.5 ** x) ** 1024 - (1 - 0.5 ** (x - 1)) ** 1024
for x in range(4, 23):
    print(x, round(P[x], 4))

```

Here is its output.

```
4 0.0
5 0.0
6 0.0
7 0.0003
8 0.0178
9 0.1169
10 0.2326
11 0.2388
12 0.1723
13 0.1037
14 0.0569
15 0.0298
16 0.0153
17 0.0077
18 0.0039
19 0.0019
20 0.001
21 0.0005
22 0.0002

```

---

By the way, thanks for mentioning such a nice article that explains the hyperloglog algorithm that counts approximately using only $\log\log N$ bits. $\log\log N$ is arguably underestimating, since more powerful hash functions are needed as $N$ grows, which need more space to compute. Even if we add the space used by the has function, hyperloglog algorithm is amazingly ingenious in several ways.
> 1 votes

---
Tags: probability-theory, probabilistic-algorithms
---


# Question
Title: Why are random numbers important to the study and application of computer science?
Why are random numbers important to the study and application of computer science? I am new to computer science. So I am studying random numbers right now.

# Answer
> 4 votes
There are a lot of applications of Random numbers in Computer science, there are full books about it, check **Randomized Algorithms** by *Rajeev Motwani* and *Prabhakar Raghavan*, for instance. There you will find many arguments for the case of random numbers.

Here is a not exhaustive list of applications in sub-fields of CS:

* **Algorithms** (As Yuval pointed, there are many problems where only randomized algorithms are known and you will find that many times randomized algorithms are simpler and more efficient than their deterministic counterpart)
* **Machine Learning** ( Generative algorithms, variational autoencoders, GANS, Bayesian inference, Monte-Carlo algorithms, ...)
* **Cryptography**(randomized prime number testing, ...)
* **Computer graphics and simulation** (Path Tracing, Procedural stuff, games, ...)
* **Big Data** (search for sketching algorithms, probabilistic counting, Bloom filters, ...)
* **Optimization** (stochastic gradient descend, meta-heuristics)
* **Simulation** (random processes, multi-agent, stochastic differential equations,...)

I am sure there are plenty more.

# Answer
> 1 votes
We may agree that **statistics** is important, for instance to test whether a new drug will help cure a disease, or whether a presidential candidate has sufficient support to be elected.

The cornerstone of statistics is the *simple random sample* whereby out of a large population of $N$ individuals we select $n$, a still large but much smaller number, in such a way that any set of $n$ individuals is equally likely.

And randomness is used to **break undesirable patterns** such as doing the same, or similar, things over and over, becoming predictable to our adversaries or to those we try to entertain.

Traditionally this was all done by any number of methods, I suppose, such as **rolling dice or pointing a finger at a page in a book**. Naturally now we want and need computers to do it, and it seems that they can. However, in theory the whole universe may be deterministic, so that any computer method of producing randomness requires careful scrutiny to see whether it might deliver biased results, especially if we're talking about delivering random bits many times a second.

Knowing that adversaries may be using randomness, there's also the question whether randomness can be used to speed up computational tasks, see e.g. the BPP=P question.

---
Tags: random-number-generator
---


# Question
Title: Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed
I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable languages (A and B, say) is not itself RE? I.e. why for A-B = Z, Z is not RE?

The basic set notation and maths I understand, but I've added a more textual description as I'm looking for an intuitive answer: let C = complement of B.

Some of the words C contains in its set would cause a TM for B to reject, others would cause it to never halt. So C is not RE.

Now, A-B = A n C, by basic set operations. The theory I've read now says that the intersection of an RE (A) and a non-RE (C) cannot be RE, which is why the original A-B = a non-RE. I accept this logic, but am struggling to understand intuitively how this is true, in terms of picturing a Turing Machine that halts or loops, given the input of words from A n C.

**My First Attempt at an Intuitive Explanation:**

My guess is that I've missunderstood something fundamental about TMs, and what their acceptance/rejection/looping on words of a language really means, but here we go:

Imagine a TM for the RE lang A. Every word in A will cause TM to accept. Now, isn't A-B just a subset of the words from the language A? Therefore, wouldn't all the words in A-B cause our TM to also accept? By this logic then, wouldn't the difference between two RE's, A-B, be an RE language, too?

---

**My Final Thought:**

I tried to picture this in different ways, with say having the condition be that you test your newly outputted language (A-B in this case), on a TM that accepts on each of the initial languages (A, B), and if the new language accepts on all those TMs, it must be RE? But that didn't hold for things like A u B.

So, I'm stuck as for an intuitive understanding as to why A - B is not RE, when A - B is just a subset of words of A, and A will accept on its TM? Further, what's the rule for how your new language (be it A-B, A u B, A\* n B, etc) should accept in relation to TMs that accept on the initial languages?

Thanks very much for your help.

# Answer
> 2 votes
Given a language $L$, $L$ is RE if there is a TM $M$ such that $L(M) = L$. $L(M)$ is the *set of words which $M$ accepts* and it must be *equal* to $L$; words not in $L$ must cause $M$ either to reject or to never halt. It is not sufficient for $L$ to be a subset of $L(M)$, which is why your reasoning is incorrect.

Given RE languages $A$ and $B$, what makes $A \setminus B$ not RE (in general) is not the problem of knowing whether the input is in $A$; since $A$ is RE, there is a TM $M\_A$ which you can simulate to find out (and if $M\_A$ does not halt, the input is not in $A$ and, hence, not in $A \setminus B$ too; so there is no need to halt at all). The problem is that, to accept an input $w$ which is *not* in $B$, you need to simulate the respective TM $M\_B$ on $w$ and accept if $M\_B$ *does not halt*; hence, you need to solve an instance of the complement of the halting problem, which is (famously) not in RE.

---
Tags: formal-languages, turing-machines, formal-grammars
---


# Question
Title: The role of depth of a circuit in its hardware implementation
The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit \[Reference\]

Question: What is the relation between the depth of a circuit and hardware implementation of the circuit. In fact, I want to ask this question, why the low depth of a circuit results in the circuit has a suitable hardware implementation?

Thanks for all suggestions

# Answer
> 3 votes
In the zeroth order sense, it is correct that the logic depth and the time to execute the logic would be the same. There are nuances to this because you need to do something with the result.

What logic is a medium to do work. In the simplest sense, you have a bounded function with inputs and outputs:

In most actual systems, you need a way to hold the data, which is why we have latches:

and with the latch, we introduce the clock. I will now give you two examples of where logical depth, in a system context, is not representative of speed.

The first assumption that made is "0"s and "1"s are things. Digital is a special case of analog; however, I personally never run anything at a "1" because it is inefficient for power. After you are above threshold, you lose transistor gain. If you are trying to have power performance, you might not make the same choices as for speed performance. You are doing the same electrical work at a high total cost.

The second assumption is that everything is clocked. In a system context, I often add logic to make things go faster. Asynchronous systems give you the average speed as a delay, instead of the worst case delay as a synchronous, clocked system.

Another assumption is that logic doesn't have physical space. Wires are costly even though that they do not add to calculation value. A good example of this is the S-Box used in AES. If you look at the "logic", I have often seen hardware implementations that use a lookup table. This is because it's easy. If you look at the gate depth alone, without the wires, it also would look to be fast. When I make the AES S-Box, the circuit implementation looks like:

This circuit has a much larger depth than the lookup table; however, it requires, less power, takes up less area, and is faster than the lookup table implementation even though the logic depth is deeper.

---
Tags: circuits
---


# Question
Title: Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:

If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?

Now, A is no longer recursive.

This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:

'if (x=1) {return true}'

For TM(A), A is accepted.

Now, let TM(A2) be a program that says 'while (x\>\_1) {x+=1}', and so now A causes TM(A2) to loop forever.

---

Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.

However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.

To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists **at least one** machine (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, **and** it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?

If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?

Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?

If I've missed the point entirely or have been unclear, please do let me know.

# Answer
> 5 votes
A language $\mathcal L$ is recursive if there exists a Turing machine $\mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $\mathcal L$ (i.e. $\forall w, \mathcal M$ accepts $w\iff w\in\mathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.

However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive\*

---

Moreover, classes of languages are often included in each others. By instance, if a language $\mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $\mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $\mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$\mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular **but you shouldn't make the assumption that it is either**. You simply don't know.

---

As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $\mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.

(\*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$\cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability

# Answer
> 4 votes
> a language A that is recursive for some Turing Machine

That's your problem, right there. A language is either recursive or it's not: there's no such thing as "recursive for a specific Turing machine". A language is recursive if there is *some* Turing machine that decides it.

---
Tags: formal-languages, turing-machines, finite-automata, formal-grammars, chomsky-hierarchy
---


title: Max Weight Path in a Graph

text:
# Question
Title: Max Weight Path in a Graph
I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new graph $G' = (V,E')$, and flip the sign of each edge weight, i.e set the weight of each edge $e' \in E'$ to $w(e') = 0-w(e)$ and use an algorithm such as Bellman-Ford to find the minimum weight path on this new graph. I understand that flipping the sign of the edges could create negative cycles, implying there is no shortest path in $G'$, but won't this imply that there is a positive cycle in $G$, meaning there is no longest path? Can someone give a counter-example of when this algorithm would fail?

# Answer
> 1 votes
There's a problem with terminology here. A *walk* in a graph is a sequence $v\_1\dots v\_k$ of vertices such that $v\_1v\_2, v\_2v\_3, \dots, v\_{k-1}v\_k$ are edges. A *path* is a walk that doesn't repeat vertices. So, a graph with a positive-weight cycle contains no longest walk (you can always walk around the cycle one more time to get a longer one) but it does contain a longest path (paths can't go all the way around cycles).

Algorithms such as Bellman–Ford actually compute shortest walks between vertices and use the fact that, as long as the graph has no negative cycles, the shortest walk is also the shortest path. (Any walk that isn't a path must contain a cycle and, if all cycles have positive weight, then the walk without that cycle is shorter.) The graph your algorithm generates contains negative-weight cycles, so Bellman–Ford will fail: it can't use its "the shortest walk is also the shortest path" rule because there is no shortest walk.

---
Tags: algorithms, graphs
---


# Question
Title: How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?
I currently have a problem with the following question:

Let $L = \\{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \\}$. Construct an NTM (non-deterministic Turing machine) that decides $L$.

My idea was to simulate every possible input of length $\le|w|^3$ on a given TM $M$ by using a separate band in my NTM for every single input word. If there is one band where $M$ halts, then the NTM accepts.

Is this the right way to go about it? My problem is that I don't see why I would need a NTM to decide $L$. A standard TM would be able to do the same thing.

# Answer
> 0 votes
$L$ is *semi*-decidable (or, synonymously, recursively enumerable). This can be proven (arguably) more easily by using an NTM which non-deterministically picks an input $w \in \\{ 0, 1 \\}^\ast$, simulates $M$ on it for at most $|w|^3$ steps, and accepts if and only if $M$ does. The NTM accepts exactly the language $L$ because, if there is no accepting branch of the NTM, then there is also no input $w$ for which $M$ halts in at most $|w|^3$ steps. For a properly written proof, it should also be said the semi-decidability of $L$ follows from the equivalence of DTM and NTM acceptors (remember (semi-)decidability is defined in terms of DTMs, *not* NTMs!).

Because of the equivalence of DTM and NTM acceptors, the above reasoning indirectly gives you a DTM which accepts $L$. The explicit construction could be picking an enumeration of inputs (e.g., lexicographical order), simulating $M$ on each input $w$ for at most $|w|^3$ steps, and accepting if and only if $M$ does. (Having to argue about the enumeration of inputs might be perceived as "hard" by some, hence why proving with an NTM could be considered "easier".)

A **warning**, however: $L$ is *not decidable*. This is because its complement is $\\{ \langle M \rangle \mid \forall w: \text{$M$ does not halt for $w$ in at most $|w|^3$ steps} \\}$ and, thus, a variant of the complement of the halting problem, which is notorious for not being semi-decidable.

---
Tags: turing-machines, nondeterminism, semi-decidability
---


# Question
Title: Prove that there exists a machine which decides an infinite subset of halting problem
We already know that $H:=\\{\langle M,w\rangle | M$ halts on $w\\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?

# Answer
> 1 votes
Let $M$ be a TM which accepts all inputs. Then $\\{ \langle M, w \rangle \mid w \in \\{ 0, 1 \\}^\ast \\}$ is an infinite subset of $H$ and (easily) decidable.

Going further, let $M\_w$ be a TM which halts if and only if its input is not equal to $w \in \\{ 0, 1 \\}^\ast$ and let it be such that $\langle M\_w \rangle$ is computable from any $w$ (e.g., $w$ is a substring of the description of $M\_w$). Then the set $\\{ \langle M\_w, w' \rangle \mid w, w' \in \\{ 0, 1 \\}^\ast \\}$ is another infinite subset of $H$ which is decidable. The description for a decider could be, for example: Given $\langle M\_w, w' \rangle$, compute $\langle M\_{w'} \rangle$ and accept if and only if it is equal to $\langle M\_w \rangle$.

**A warning**: in the question text you referred to "a machine that decides any infinite subset of $H$". Indeed, no such machine exists (since $H$ is an infinite subset of itself); however, this is not what the question title (presumably the intended question) is implying.

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


# Question
Title: Is every subset of a RE language also RE, in general?
I'm trying to understand the question in my title in an intuitive way: If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will cause TM(A) to halt in the accept state.

However, is it in general possible to then create a TM for A2, say TM(A2), such that A2 is the max possible set that halts TM(A2) in the accept state. Thus making A2 its language - and would this language be RE?

Thanks

# Answer
No, it is not true that every subset of a recursively enumerable (RE) language is also RE. In fact, it make sense to say that a subset of a RE language is not RE more often than not.

For an example, let us consider the RE language, $\Sigma^\*$ that contains all words. It is the language of the Turing machine which always halts and accepts in its first step. Note that every language is a subset of $\Sigma^\*$. Every language that is not RE is an example.

---

Here are a few exercises for you to check.

Exercise 1. Is every subset of a regular language regular?

Exercise 2. Is every subset of a context-free language context-free?

Exercise 3. Is every subset of a recursive language recursive?
> 2 votes

# Answer
The trick to answering questions like this is to start by considering cases that make the question as simple as possible. If you're lucky, the simplified question will be easy to answer and will give you the answer to the original question.

Here, you're asking "If a language is RE, are all its subsets?" One of the simplest RE languages we can try is $\Sigma^\*$. Not only is this a very simple language, but it also has many, many subsets. So, if any RE language was going to have non-RE subsets, it would have to be this one. Considering this case turns the question into "Is every subset of $\Sigma^\*$ RE?", which is just "Is every language RE?" and we see that the answer is no.

In other cases, it might be more beneficial to consider the empty language. (E.g., if you wanted to know whether every superset of an RE language is RE.)
> 3 votes

---
Tags: formal-languages, formal-grammars, chomsky-hierarchy
---


# Question
Title: When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?
The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. When the traversal is complete all the nodes in the graph are black.

None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.

Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?

# Answer
Your question is, essentiall, "How is this stuff implemented?", to which the answer is "However the implemnter chooses."

Although we talk about nodes of the graph being coloured during the search, implementing that literally as a "visited" field in each node's data record would take up storage space even when no search is in progress. In a concurrent environment, it would also limit you to doing only one search at a time. Instead, it's normal to implement the colouring as a list of visited nodes, or some other structure that is external to the representation of the graph itself; this is typically made explicit in descriptions of, e.g., A\* search. This data structure will simply be deallocated when the search is complete.

If you did have an explicit "visited" field in each node then, yes, you'd need to do a separate pass to clear those after each search.
> 3 votes

# Answer
Hi there and happy new year! :)

Colouring vertices is nothing more and nothing less than a didactic resource to explicitly distinguish among three different states:

1. Nodes that have not been visited yet
2. Nodes that have been visited yet not expanded
3. Nodes that have been both visited and expanded

Since the state of a node does not change once a solution has been found, the notion of "de-colouring" the resulting graph is never used.

I think the above fully answers your question but let me please refer to a closely related but somehow different issue: *duplicate detection*. In spite of using either one strategy or another, it is usually very advantageous to avoid re-expanding nodes when it can be proven that they will not improve the cost of the incumbent solution or that they will not lead to an optimal solution. In the following, I'm covering the basics of mechanisms for duplicate detections under the strategies you mention.

**Depth-First Search**

When traversing a graph in Depth-First order, the only nodes in memory are those in the path from the root node to the current node. Other nodes previously expanded over which the algorithm backtracked are not in memory any more (and this is indeed the reason why this algorithm takes an amount of memory which is linear in the depth of the search tree!). Thus, the basic mechanism for avoiding duplicate detection is just to compare the child of a newly expanded node with all nodes in the current path from the root node ---just to avoid loops!

Of course, this mechanism could be enhanced by storing all nodes previously expanded but this is not trivial and doing so would lead to a much larger usage of the available memory.

**Breadth-First Search**

In contraposition to the previous case, Breadth-First Search has a memory consumption which is exponential in the depth of the search tree. Actually, the number of nodes generated dominate the memory consumption. Hence, it is usually a good idea to use an additional data structure to avoid re-expanding nodes. In general, the preferred data structures here are sets or maps where membership operations can be performed in logarithmic time in the number of nodes previously expanded.

Hope this helps,
> 1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Which of the following problems can be reduced to the Hamiltonian path problem?
I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

> Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems can be solved in polynomial time?
>
> Hint: The Hamiltonian path problem is: given an undirected graph with n vertices, decide whether or not there is a (cycle-free) path with n \- 1 edges that visits every vertex exactly once. You can use the fact that the Hamiltonian path problem is NP-complete. There are relatively simple reductions from the Hamiltonian path problem to 3 of the 4 problems below.
>
> * For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path exists). The path is allowed to contain cycles.
> * Amongst all spanning trees of the graph, compute one with the smallest-possible number of leaves.
> * Amongst all spanning trees of the graph, compute one with the minimum-possible maximum degree. (Recall the degree of a vertex is the number of incident edges.)
> * For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path exists). The path is not allowed to contain cycles.

Notice that a Hamiltonian path is a spanning tree of a graph and only has two leaf nodes, and that any spanning tree of a graph with exactly two leaf nodes must be a Hamiltonian path. That means that the NP-Complete problem of determining whether a Hamiltonian path exists in a graph can be solved by finding the minimum-leaf spanning tree of the graph: the path exists if and only if the minimum-leaf spanning tree has exactly two leaves. Thus, problem 2 is NP-Complete.

Problem 3 is NP-Hard; here is a paper that proves that.

That means, between 1 and 4, one is NP-Complete, another is in P. It seems like problem 4 reduces trivially to the the Hamiltonian path problem, but I'm not able to understand how having a cycle makes it solvable?

# Answer
Problem 1 can be solved in polynomial time. Here is a simple algorithm to compute it in $O(n^2 + nm)$ (it can probably be done faster).

This can be solved in a dynamic programming style. If we find the shortest length $k$ path to all nodes from source $s$, then we can easily find the shortest length $k+1$ path to all nodes from source $s$. Let $d\_k(v)$ be the length of the shortest $k$-length path to node $v$ from source $s$. We have:

$$d\_{k+1}(v) = \min\_{u\ \in\ adj(v)} \ d\_k(u) + w(u,v)$$

Where $d\_0(s) = 0$ and $d\_0(v) = \infty$ if $v \neq s$. Then we must simply iterate over all $k$ and compute the necessary values.

```
set d(s) = 0
set d(v) = infty for all v != s
for k in 1, 2, ..., n-1 do:
  for all nodes v do:
    set dp(v) = infty
    for all nodes u adjacent to v do:
      set dp(v) = min(dp(v), d(u) + w(u,v))
  set d = dp
return d(t)

```

Note that `dp` is just an intermittent variable so that $d\_k$ is correctly computed on $d\_{k-1}$ rather than accidentally overwriting $d\_{k-1}$.

The two inner for loops take $O(n + m)$ and the outer takes $O(n)$. Overall this algorithm takes $O(n^2 + nm)$.

The reason for this speed-up is precisely what Peter said. We do not need to keep track of intermediate nodes in order to prevent cycles, we simply keep going without worry of cycles at all. If we needed to keep track of intermediate nodes then it is not necessarily the case that $d\_{k+1}(v) = \min\_{u\ \in\ adj(v)} \ d\_k(u) + w(u,v)$. It may end up being that case that we would actually not use $d\_k(u)$ to compute $d\_{k+1}(v)$ because there may be a slightly longer path to $u$ that actually allows us to use edge $(u,v)$. This creates a combinatorial explosion in terms of what we must check and remember.
> 2 votes

# Answer
> I'm not able to understand how having a cycle makes it solvable?

The basic intuition is that it reduces the amount of state you need to track. With cycles allowed you just need to build up a table of the shortest length-k path from s to each other vertex. With cycles disallowed you need to track all of the intermediate vertices, so you potentially wind up with a table of all path prefixes.
> 1 votes

# Answer
Problem 1 seems indeed P to me.

What about an algorithm based on Bellman-Ford doing exactly n-1 steps ? The trick would be that on each step you take for every node the minimum incoming path without comparing to the last step value (if there is no incoming path, put a +inf again).
> 0 votes

---
Tags: algorithms, complexity-theory, graphs, np-complete, hamiltonian-path
---


# Question
Title: Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)
I am trying to find a solution to the ex. 4.6-2 of the *Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition)*. It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b \> 1$, $n$ is an exact power of $b$ and $f(n)$ is an asymptotically positive function, to prove that if $f(n) = \Theta(n^{\log\_ba}lg^{k}n)$, where $k\geq0$, then $T(n)=\Theta(n^{\log\_ba}lg^{k+1}n)$.

Since $T(n) = n^{\log\_ba} + g(n)$ where $g(n) = \sum\_{j=0}^{\log\_b n - 1} a^{j}f(n/b^{j})$, I decided to consider the $g(n)$ function at the first. And I have shown $g(n) = O(n^{\log\_ba}lg^{k+1}n)$ already (I think so).

But the doing the proof $g(n) = \Omega(n^{\log\_ba}lg^{k+1}n)$ became a challenge for me.

Below is my research (with the simplified assumption $k$ **is an integer**). By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum\_{j=0}^{\log\_b n - 1} a^{j}(n/b^{j})^{log\_ba}log^{k}(n/b^{j}) =$

$cn^{\log\_ba}\sum\_{j=0}^{\log\_b n - 1} log^{k}(n/b^{j}) =$

$cn^{\log\_ba}\sum\_{j=0}^{\log\_b n - 1}(logn - logb^{j})^{k} =$

$cn^{\log\_ba}\sum\_{j=0}^{\log\_b n - 1}\sum\_{i=0}^{k} {k \choose i}log^{k-i}n(-logb^{j})^{i} =$

$cn^{\log\_ba}log^{k}n\sum\_{j=0}^{\log\_b n - 1}\sum\_{i=0}^{k} {k \choose i}(-logb^{j}/logn)^{i} =$

$cn^{\log\_ba}log^{k}n \biggl(log\_bn + \sum\_{j=0}^{\log\_b n - 1}\sum\_{i=1}^{k} {k \choose i}(-logb^{j}/logn)^{i} \biggr) \geq$

$c'n^{\log\_ba}log^{k+1}n - cn^{\log\_ba}log^{k}n\sum\_{j=0}^{\log\_b n - 1}\sum\_{i=1}^{k} {k \choose i}(logb^{j}/logn)^{i} =$

$A(n) - B(n) = \Theta(n^{\log\_ba}lg^{k+1}n) - B(n)$

Actually I am stuck with it. I can not show that $B(n)$ grows slower than $A(n)$. For instance, since $(logb^{j}/logn)^{i} \le 1$ we are able to enhance our $\geq$ condition by the substitution $B(n)$ to some fucntion $B'(n)$ with the sums of binominal coefficients only. But then finally $B'(n)$ has $n^{\log\_ba}log^{k+1}n$.

So how to prove $g(n) = \Omega(n^{\log\_ba}lg^{k+1}n)$ ?

# Answer
> 1 votes
All we need to prove is the following, where $b\>1, k\ge 0$ and $k$ may or may not be an integer. $$\sum\_{j=0}^{\lfloor\log\_b n\rfloor} \left(\log\_b\left(\frac n{b^{j}}\right)\right)^k=\Omega((\log\_b n)^{k+1})$$

In order to show the idea of the proof clearly, assume that $n = b^m$. The above estimate is $$\sum\_{j=0}^{m} (m-j)^k=\Omega(m^{k+1})$$

Here is the proof.

$$\sum\_{j=0}^{m} (m-j)^k=\sum\_{i=1}^m i^k\ge\sum\_{i=1}^m \int\_{i-1}^{i} u^k du=\int\_{0}^{m} u^k du = \left.\frac{u^{k+1}}{k+1}\right |^m\_0= \frac{m^{k+1}}{k+1} $$

---
Tags: algorithm-analysis, recurrence-relation
---


title: Kiln optimization problem

text:
# Question
Title: Kiln optimization problem
Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings:

102 of A

364 of B

70 of C

I can put 50 molds in the kiln at a time. I can have 75 molds made in any combination.

First, what is the optimal combination of molds to make.

Second, what is the schedule to make the castings in as few firings as possible.

I am trying to wrap my head around this problem. I see that the second part resembles task scheduling problems I've read about, but I have no idea how to tackle the first problem.

Any help/insight very much appreciated.

# Answer
Either there is an additional constraint, either this problem is far more simpler than task scheduling.

Well you have to identify the limiting criterium of your problem which is 50 molds maximum in the kiln.

Let's call S = A+B+C = 536, the total number of molds. So You cannot do better than 11 firings (11\*50=550).

First compute the euclidean division of the required elements to get the quotient and the remainder, that will be the constant molds and the variable molds to use.

```
- x, a = A/11 = 9, 3
- y, b = B/11 = 33, 1
- z, c = C/11 = 6, 4

```

So the constant molds are (x, y, z) = (9, 33, 6), that is to say 48 molds.

You now have 11 firings on the 2 (50-48) variables molds to complete the (a, b, c) = (3, 1, 4) remaining elements. Let's say we want to minimize the number of molds to manipulate. Then just take one extra mold of each A, B, C to have a total of 51 molds.
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: Drawbacks of adding type equality to 1ML
In the 1ML – Core and Modules United (F-ing First-Class Modules) paper, the author gives the following example for why module types do not form a lattice under subtyping:

> ```
>  f1 : {type t a; x : t int} → int
>  f2 : {type t a; x : int} → int
>  g = if condition then f1 else f2
>
> ```
>
> There are at least two possible types for g:
>
> ```
>  g : {type t a = int; x : int} → int
>  g : {type t a = a; x : int} → int
>
> ```
>
> Neither is more specific than the other, so no least upper bound exists. Consequently, annotations are necessary to regain principal types for constructs like conditionals, in order to restore any hope for compositional type checking, let alone inference.

At first glance, it seems like the problem can be remedied by adding in type equalities:

```
g : (t int ~ int) ⇒ {type t a; x : int} → int

```

However, this "solution" isn't discussed in the paper. So it feels like I'm overlooking some obvious drawback of this idea, apart from the one that it might not be possible to encode type equality in System Fω (which is the raison d'être for the paper). Does adding type equalities make type checking/inference even more problematic in other situations?

# Answer
> 9 votes
Your proposal is an instance of a general design pattern for type systems that some would call a design smell: whenever you are stuck on an inference constraint that you cannot solve, or cannot solve in a principal way, include it in the resulting type. "It's not a problem, it's in the solution."

This solution can be made to work, but in general it may run into several practical issues:

* Constraint explosion. If those tricky problems occur more often than you would think, you can end up with many constraints (in particular if you sometimes need to introduce disjunctions of constraints; this is the end). This is problematic for user readability, and type-checking time.
* Loss of abstraction. The collected constraints reveal which unifications were done in the implementation, and sometimes they reveal too much details about the implementation compared to what the user had in mind. (On the other hand, they are usually principal, so what the user has in mind is not more general.)
* Delayed error. If you don't check that those delayed constraints are solvable, then you may delay error: all attempts to use the value will be an error, but there is no error as definition-site. (This gives the same usability issues as C++ templates.)

Not all instances of this "putting constraints in the solution" pattern have all these problems. In your example for example, it may be possible that the specific shape of equality constraints occurring (1) have no need for disjunction of equalities and (2) let you check solvability of constraints when they are introduced. You would have to think carefully about that.

---
Tags: type-theory, type-checking, type-inference
---


# Question
Title: Curiosity on system device nomenclature - Gaussian Mixture Models
Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an hypothesis).

I hold a MSc. in Statistics, and thus have extensively explored Gaussian Mixture Models. That's why, upon buying my brand new Lenovo E580 laptop (Windows 10 Pro x64), I was surprised to find, under the System devices drop down menu in the Device Manager, a reference to GMMs (although I'm not sure what the actual item is pointing to). I have included a picture to clarify the point.

**Questions**

1) What is the highlighted item referring to?

2) How do GMMs have anything to do with this?

# Answer
> 1 votes
These are accelerators for Gaussian Mixture Modelling used for speech recognition and video processing applications. They can be typically accessed via openCL libraries.

GMMs are used for efficient classification of partial or noisy data e.g. speaker voices or people object in videos.

---
Tags: terminology, computer-architecture
---