title: Neither Left nor Rightmost Derivations

text:
# Question
Title: Neither Left nor Rightmost Derivations
Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the language generated by a grammar.

Apart from practical considerations, such as implementation difficulty and orderliness of derivations, is there any other reason why we usually do not discuss about arbitrary derivations (not rightmost or leftmost)?

# Answer
The main reason is that context-free grammars, once introduced, were quickly adapted to provide a theoretical basis for program language compilation. For this usage, the goal is to parse as quickly as possible using as little storage as possible. For that the best approach is to scan the input source once from 'left-to-right' *\[we interpret the source as a sequence of characters all on a single line\]*, and be done with the parse exactly when done scanning the source. Two derivation patterns naturally fit into this protocol: leftmost-first derivations performed top-down in forward order, and rightmost-first derivations performed bottom-up in reverse order.
> 2 votes

---
Tags: formal-grammars, parsers, syntax-trees
---


# Question
Title: Find minimum distance match in sub-linear time in a data base
The title seems a little vague. So let me explain the question in detail.

Suppose you have a data base. Each record in the data base is $\<\mathbf{x},data\>$, where $\mathbf{x}$ is an $n$-dimensional index vector.

A query is also an $n$-dimensional vector $\mathbf{y}$. So given the query $\mathbf{y}$, the data base will return the record $i$ such that $\mathbf{x}\_i$ and $\mathbf{y}$ have minimum distance. (It can be any distance. But let's focus on Euclidean distance here).

The trivial solution is to scan every record in the data base and compute the distance. This will introduce linear complexity with regard to the number of total records in the data base.

So is there any sub-linear algorithms to solve this problem (approximately)? For example, if the dimension $n=1$, we can organize the index in data structure such as binary search tree. But for dimension $n\>1$, can we also organize the index into some special data structure?

Thanks for you time.

# Answer
> 1 votes
This problem is exactly solved by the k-d tree, which organizes points in $k$ dimensions with logarithmic lookup time.

---
Tags: complexity-theory, data-structures, search-algorithms
---


# Question
Title: Is there an Algorithm that can code itself?
Suppose there is algorithm that has a strong NLP module. Could it use the NLP module to read text books such as http://www.amazon.in/Artificial-Intelligence-Modern-Approach-Prentice/dp/0136042597 in text form, parse it, understand the semantics and then use the knowledge to *improve the very code it's written in* ? Like a virtual computer scientist? Is any research group working on it or even thought of that idea?

# Answer
While there are no program synthesizers that can synthesize themselves in their entirety, plenty of synthesizers can synthesize pieces of themselves. Rohit Singh, for instance, has a project using the Sketch synthesizer to optimize many logical solvers, including that of Sketch itself.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, natural-language-processing
---


# Question
Title: 2-SAT Problem with additional constraints on variable?
Given a 2-SAT problem that is satisfiable. The solution to the problem can be found in polynomial time.

Adding an additional constraint:

1. The maximum number of positive literals that can have the boolean Value 1 is N. (i.e. a=positive literal, ~a=negative literal)

Is the problem still solvable in Polynomial time?

My assumption is it should be but I am unclear now to modify the original solution? Or are we looking at something similar to the Vertex Cover Problem?

# Answer
That is NP-hard by reduction from vertex cover, even when there are no negative literals.
If you meant to count by occurrences rather than just bounding the number of
distinct variables which are true, then use this paper's result and this paper's result.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Understanding constants in big-O notation
I am having a difficult time understanding big-O notation for the growth of functions. My textbook says the following.

> Example 2 shows that $7x^2$ is $O(x^3)$. Is it also true that $x^3$ is $O(7x^2)$?
>
> *Solution:* To detemine whether $x^3$ is $O(7x^2)$, we need to determine whether witnesses $C$ and $k$ exist, so that $x^3\leq C(7x^2)$ whenever $x\>k$. We will show that no such witnesses exist using a proof by contradiction.
>
> If $C$ and $k$ are witnesses, the inequality $x^3\leq C(7x^2)$ holds for all $x\>k$. Observe that the inequality $x^3\leq C(7x^2)$ is equivalent to the inequality $x\leq 7C$, which follows by dividing both sides by the positive quantity $x^2$. However, no matter what $C$ is, it is not the case that $x\leq 7C$ for all $x\>k$, no matter what $k$ is, because $x$ can be made arbitrarily large. It follows that no witnesses $C$ and $k$ exist for this proposed big-$O$ relationship. Hence, $x^3$ is *not* $O(7x^2)$. $\quad\Box$

I don't understand the part that says, ".... no matter what $C$ is because $x$ can be arbitrary large." Making $x$ large, can't we also assign larger number for $C$?

What are the purpose of $C$ and $k$?

Are there any rules regarding assigning values to them?

# Answer
> 1 votes
It is supposed there exists constant C and constant k such that the inequality holds. Constant C doesnt depend on x. Thus if x is greater than 7\*C the inequality doesnt hold.

# Answer
> 1 votes
To prove that a function $f(n)$ is in $O(g(n))$ we must find two constants $c$ and $k$ so that $0 \leq f(n) \leq cg(n)$ for all $n \> k$.

An example of this applied towards a function could be $f(n) = 7n^2$. We can prove this function is in $O(n^2)$ by selecting $c = 8$ and $k = 2$. Then, through substitution we can see that $0 \leq 7n^2 \leq 8n^2$ whenever $n \> 2$ (of course, we could select other $c$'s or $k$'s, but we only need to find one set).

To prove that $f(n) = n^3$ is not in $O(7n^2)$, we must demonstrate that there is no possible combination of $c$ and $k$ for the inequality $0 \leq n^3 \leq c * 7n^2$ to hold for *all* $n \> k$.

Suppose there is a combination to fulfill the inequality, we will call these numbers $c\_0$ and $k\_0$. If $f(n) \in O(7n^2)$, we know that $0 \leq n^3 \leq c\_0 * 7n^2$. Working with the inequality, we can see that $n$ *should* be less than or equal to $c\_0 * 7$ for all $n \> k\_0$, but we can select $n = \text{max}(\\{k\_0 + 1, c\_0 * 7 + 1\\})$ and the inequality wouldn't hold.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Confusion related to this algorithm about finding the orientation given 3 points
I have a confusion related to an algorithm for finding the orientation given three points, i.e., determining whether one line is clockwise or counter-clockwise of another.

Let's say the points are $P\_1=(x\_1,y\_1)$, $P\_2=(x\_2,y\_2)$, $P\_3(x\_3,y\_3)$. The algorithm says

* Let the slope of line $P\_1P\_2$ be $m\_1$ and slope of $P\_2P\_3$ be $m\_2$.
* If $m\_2 \> m\_1$, the orientation is counterclockwise and if $m\_1 \> m\_2$ it is clockwise.

However lets say the points are $(0,0)$, $(4,4)$ and $(2,4)$. This give $m\_1=1$, $m\_2=0$. The orientation is counter clockwise but $m\_2 \< m\_1$. So I am wondering if there is any issue with the algorithm.

Any suggestions?

# Answer
> 3 votes
The orientation of three points in the plane is classically done with a determinant. In the linked article the approach is done on a polygon thus they use a 3x3 determinant. For only three points, i.e., a triangle, a 2x2 determinat is sufficient.

Let $p\_1=(x\_1,y\_1), p\_2=(x\_2,y\_2)$, and $p\_3=(x\_3,y\_3)$ be three points in the plane. Then we compute the orientation vectors at $p\_1$, that is $p\_{1,2}=p\_2-p\_1$ and $p\_{1,3}=p\_3-p\_1$. Now we use the determinant to find the orientation: $$\mathrm{det}\begin{bmatrix}x\_2-x\_1&y\_2-y\_1\\x\_3-x\_1&y\_3-y\_1\end{bmatrix}=(x\_2-x\_1)(y\_3-y\_1)-(y\_2-y\_1)(x\_3-x\_1).$$

If the result is smaller than zero then $(p\_1,p\_2,p\_3)$ are in counter-clockwise order, if larger than zero in clockwise order, and if zero then they are collinear.

---
Tags: algorithms, computational-geometry
---


title: Shunting-yard algorithm - proof

text:
# Question
Title: Shunting-yard algorithm - proof
How can one prove that a shunting-yard algorithm always returns a correct expression in RPN? I cannot find any proof in the internet.

# Answer
The shunting-yard algorithm was introduced in Dijkstra's article *Making a Translator for ALGOL-60* (APIC Bulletin no7, 1961; see this PDF, from p.22; also published in *Annual Review in Automatic Programming*, 7:3–11, 1963 and available from Science Direct if your institution has a subscription). Pages 7–9 of the article (pp.28–30 of the PDF) explain how the algorithm works and argue its correctness. It's not a formal proof but it looks like it contains everything you should need to produce one.
> 4 votes

---
Tags: algorithms, correctness-proof
---


title: NP and finite automata

text:
# Question
Title: NP and finite automata
A language $L$ is in NP if and only if there exist polynomial $q$, and a deterministic polynomial Turing machine $M$ such that, for all $x\in L$, there is a string $y$ such that $|y|\leq q(|x|)$ and $M(x,y) = 1$.

My question is is it possible to exchange $M$ for a finite automaton?

Thank you

# Answer
What you have given is a definition. You can define anything you want. The class of languages defined as

> A language $L$ is in **UC** (user71565's class1) if there are a polynomial $q$ and a DFA $A$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $A$ accepts $xy$

is a perfectly legitimate class of languages. For example, it includes all regular langauges (take $y=\varepsilon$ for every $x$).

However, because this is not the same definition as the definition of **NP** that you quoted in your question, you shouldn't expect that **UC$\\,=\\,$NP**. In fact, we can quickly see that **UC$\\,\neq\\,$NP**, using the pumping lemma and a language such as $\\{0^n1^n\mid n\geq 0\\}$, which is in **NP** but cannot be recognized by any DFA.

Interestingly, though, the following definition *is* equivalent to the normal definition of **NP**:

> A language $L$ is in **NP2** if there are a polynomial $q$ and a deterministic logspace Turing machine $M$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $M(x,y)=1$.

That is, we can weaken from a deterministic polynomial-time verifier to a deterministic logspace one, without changing the class of languages defined. This is a consequence of Fagin's theorem, which says that the verifier can actually be a formula of first-order logic. The expressive power of first-order formulas is strictly weaker than deterministic logspace Turing machines.

---

1 There's something of a tradition of naming language classes in this way. For example, the class **NC** of languages decidable in polylog time with polynomially many processors stands for "Nick's class", after Nick Pippenger.
> 2 votes

# Answer
No it is not possible because finite automata is not equivalent to Turing machine. Turing machine is a powerful model of computation as compared to finite automata. For example

> $$ L= \\{0^n1^{2n} \mid n \ge 0\\}$$

It is not a regular language but it is verifiable in polynomial time by Turing machine. If you use finite automata as a verifier instead of Turing machine you will be able to verify only regular languages but not all the problems in the complexity class $ \mathsf{\text{}NP}$.
> 0 votes

---
Tags: complexity-theory, np
---


# Question
Title: Divide and Conquer Algorithm for Hidden Line Removal
You are given n nonvertical lines in the plane, labeled $L\_1, ..., L\_n$, with the $i^{th}$ line specified by the equation $y = a\_i x + b\_i$.

We will make the assumption that no three of the lines all meet at a single point. We say line $L\_i$ is uppermost at a given $x$-coordinate $x\_0$ if its $y$-coordinate at $x\_0$ is greater than the $y$-coordinates of all the other lines at $x\_0$: $a\_i x\_0 + b\_i \> a\_j x\_0 b\_j$ for all $j \neq i$.

We say line $L\_i$ is visible if there is some $x$-coordinate at which it is uppermost-intuitively, some portion of it can be seen if you look down from "$y = \infty$".

> Give an algorithm that takes $n$ lines as input and in $O(n\log n)$ time returns all of the ones that are visible.

Hint: Use divide-and-conquer approach.

Note: This question is taken from Here. Also, The answer is available as a code in java. But i can't understand what it does.

# Answer
> 1 votes
The solution you linked to makes use of two simple yet important observations: Let two lines $L\_1, L\_2$ of slope $m\_1, m\_2$ and intercept $b\_1, b\_2$.

* If $m\_1 = m\_2$ then only the line of greater intercept is visible, otherwise they're both visible.
* Their intersection is characterized by the relation $|(b\_1 - b\_2)| / |(m\_1 - m\_2)|$.

Given a set of $0, 1$ or $2$ lines, the solution is then computed in $O(1)$ time ; those will be our base cases.

Given a set `S` of $n$ lines, the solution is computed using the following algorithm :

```
HLR(S)
  Let S1, S2 sets of line
  S1 = HLR(FirstHalf(S))
  S2 = HLR(SecondHalf(S))
  Return Merge(S1, S2)
End

```

With `FirstHalf(S)` and `SecondHalf(S)` being exclusive subsets of `S` of cardinality $n/2$ (or sometimes $1$).

To merge the intermediate results, you need to set an order relation on the lines (based on their slope and intersect of course) and compare lines 2 by 2. If one *hides* another, then you can assume that the later will never be visible and thus can safely be removed from the set of solutions. The method is properly explained in the comments of the program you linked, and makes use of the intersection relation I mentioned. As described there, there are about $2n$ treatments.

We're dividing the problem in $2$ subproblems of size $n/2$ each. The master theorem gives the following relation: $T(n) = 2 * T(n/2) + f(n)$. Here, $f(n) = 2n = \Theta(n^1 \log^0 n)$. As $\log\_2 2 = 1$, it follows that $T(n) = \Theta(n^{\log\_2 2} \log^{0+1} n) = \Theta(n \log n)$, which implies that it is also in $O(n \log n)$.

---
Tags: algorithms, computational-geometry, divide-and-conquer
---


title: Why is 0-BPP equal to P

text:
# Question
Title: Why is 0-BPP equal to P
Sorry if it is an obvious question, since all my searches lead to "clearly 0-BPP=P" (like Papadimitriou text book or Complexity Zoo). I understand that any P machine can be seen as a 0-BPP machine with a 0-assignment function that assigns exactly 0 or 1 to any non deterministic choice, which makes P a subset of 0-BPP. But what about the converse?

# Answer
$\delta-\mathsf{BPP}$ is the set of all languages $L$ such that there exists a polynomial Turing machine $M(x,r)$, and some polynomial $p(n)$ such that:

$\forall x\in\Sigma^\* : \Pr\limits\_{r\sim\mathcal{D}\_\delta\left(\\{0,1\\}^{p(n)}\right)}\left\[M(x,r)=L(x)\right\]\ge\frac{2}{3}$

For all $\delta$-semi random distributions $D\_\delta$ on strings $\\{0,1\\}^{p(n)}$. $D\_\delta$ is said to be $\delta$ semi random if $\Pr\left\[x\_i = 1 | x\_1,...,x\_{i-1}\right\]\in\left\[\delta,1-\delta\right\]$.

Note that $M$ is guaranteed to agree with $L$ with probability $\ge\frac{2}{3}$ for all distributions $D\_\delta$ which are $\delta$ semi random (meaning that $M$ can handle "adversarial distributions").

If $\delta=0$, you have a complete freedom in the choice $D\_\delta$, so you can choose the deterministic one which always outputs 0, and you are guaranteed that $M$ knows how to handle it and still agrees with $L$ with high probability. However, if the distribution is fixed at 0, $M$ accepts any input with probability $1$ or $0$, hence it always outputs the correct answer.
> 4 votes

# Answer
It's a polynomial-time Turing machine with access to "random" bits that are guaranteed to have value zero. Since the random bits are completely deterministic, the machine is just a deterministic polynomial-time TM.
> 0 votes

---
Tags: complexity-classes, randomized-algorithms
---


# Question
Title: Why do we need optimal substructure for dynamic programming?
Cormen and others in their book on algorithms in chapter "15 Dynamic Programming" repeat again and again that we need to prove that "a problem exhibits optimal substructure". A problem exhibits optimal substructure iff (if a solution to a problem is optimal, then each of its subsolutions to a corresponding subproblem is optimal). I guess that we need this optimal substructure property to prove that the algorithm of dynamic programming is correct. I fail to see how this property helps.

Here is the algorithm of dynamic programming. Given a problem, for every choice, combine optimal subsolutions to each subproblem. In order to prove that the algorithm is correct, we need to prove that the combination of optimal subsolutions is optimal. This is **the converse** of the optimal substructure property.

Though my question seems abstract, it can be applied to any specific problem that Cormen and others present. For all problems, correctness is proved via the optimal substructure property, hence all these proofs are incorrect. (Of course, the algorithms are correct.)

I have searched for similar questions and found one (common keywords). However, the question does not make sense to me: proofs are not machines, proofs do not "work". So I can't use those answers.

# Answer
> 2 votes
We do not need the property just to prove the algorithm is correct, we need the property for the algorithm to actually work. This is clearly stated in the Bellman Equation which is the entire basis for dynamic programming. We are combining the results of optimal subproblems to get an optimal result. If we can not show that our combination of optimal subproblems gives an optimal result then the algorithm simply doesn't work. This is the principal of optimal substructure.

---
Tags: algorithms, dynamic-programming, correctness-proof
---


# Question
Title: Languages with infinitely many but finite Myhill-Nerode equivalence classes
I'm kind of new to automata theory and I'm dealing with the equivalence classes used for example in the Myhill-Nerode theorem right now; in other words aba\* / a = ba\*; aba\* / b = ⌀, and such.

In an exercise I'm asked to find a language defined by an infinite set of equivalence classes, but where each class is actually finite. Unfortunately this seems a bit counterintuitive to me, and I can only manage to find languages with an infinite set of equivalence classes where the classes are infinite.

If someone could help me out with the reasoning, and what I'm missing here, I'd really appreciate it.

# Answer
A random language would do. If $L$ is chosen by putting every word in $\Sigma^\*$ in $L$ with probability $1/2$, then for every two given words $x \neq y$ and any third word $z$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$. Hence almost surely $x$ and $y$ are not equivalent (since we can choose an infinite sequence $z\_i$ so that the words $xz\_1,yz\_1,xz\_2,yz\_2,\ldots$ are all distinct). Since there are only countably many pairs of words, we find that almost surely, every word is its own equivalence class.

It is also not too difficult to explicitly construct such a language. It suffices to find a subset $A$ of the natural numbers such that for every $x,y \in \mathbb{N}$ there exists $z \in \mathbb{N}$ such that $x+z \in A \not\Leftrightarrow y+z \in A$ (why?). Let $$ A = \bigcup\_{i=0}^\infty \\{4^i+1,\ldots,2\cdot 4^i\\}. $$ Given $x \< y$, let $z = 4^y + 1 - y$. Then $z + y = 4^y + 1 \in A$, while $x + z \< 4^y + 1$ and $x + z \geq z = 4^y + 1 - y \> 2 \cdot 4^{y-1}$ (check!), showing that $x + z \notin A$.
> 4 votes

---
Tags: formal-languages
---


# Question
Title: How can union-find algorithm be used with "real" data
In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described:

> The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning “p is connected to q.” We assume that “is connected to” is an equivalence relation, which means that it is
>
> * Reflexive : p is connected to p.
> * Symmetric : If p is connected to q, then q is connected to p.
> * Transitive : If p is connected to q and q is connected to r, then p is connected to r.

And it has one simple implementation called `quick-find`:

> One approach is to maintain the invariant that p and q are connected if and only if id\[p\] is equal to id\[q\]. In other words, all sites in a component must have the same value in id\[\].This method is called quick-find because find(p) just returns id\[p\], which immediately implies that connected(p, q) reduces to just the test id\[p\] == id\[q\] and returns true if and only if p and q are in the same component...To combine the two components into one, we have to make all of the id\[\] entries corresponding to both sets of sites the same value, as shown in the example at right.

My question is how can this be used for real objects? It works for integers, but what if I need to know whether the object `A` is connected to the object `B`, not if `3` is connected to `5`? One solution I can think of is to have an array of objects where each object's index in the array corresponds to the index of the array used for connectivity. For example:

```
   1   2   3   4   5
[ { } { } {A} { } {B} ]   <---- real data

   1   2   3   4   5
[  1   2   3   4   3 ]    <---- connections (3 and 5 have the same group id 3)

```

Is that how it's applied?

# Answer
> 3 votes
Short answer: indirection.

For instance, each object could have a field that contains an index into the `id` array.

Or, you could use pointers. Standard union-find data structures often use pointers instead of integers/indices/arrays. Thus, each object has a pointer to another object in the same equivalence class. See, e.g., https://en.wikipedia.org/wiki/Disjoint-set\_data\_structure or other standard presentations of union-find data structures.

# Answer
> 2 votes
You don't say which union-find implementation you are talking about. On the abstract level, all is good; in the first quote, the authors already state that integers represent arbitrary objects!

In OOP-speak, as long as your objects have unique integer identifiers, you can immediately apply the material. In many languages, object identity will suffice.

In implementations, a union-find data structure may define an internal element wrapper (as lists and trees do as well), that is something like:

```
struct Element<T> {
    id: Int
    value: T
}

```

You would use `id` for managing the union-find business, and all `get`-style operations would return (sets of) `value`s.

That all said, none if this changes the *concepts*; they carry over to all countable (well, recursively enumerable, I guess) sets/types. That's why algorithms textbooks typically only deal with integers: it makes for simpler notation (and code).

---
Tags: data-structures, modelling, union-find
---


# Question
Title: Difference between the Cartesian product in set theory and in relational algebra
What's the difference between the Cartesian product in set theory and in relational algebra?

The Cartesian product in set theory is defined as:

$$A \times B = \\{(a, b) \mid (a \in A) \land (b \in B)\\}$$

I think this is exactly how it works in relational databases, but Wikipedia tries to make a difference that I don't understand:

$$ R \times S := \\{ (r\_1,r\_2,\dots,r\_n,s\_1,s\_2,\dots,s\_m) \mid (r\_1,r\_2,\dots,r\_n) \in R, (s\_1,s\_2,\dots,s\_m) \in S \\} $$

# Answer
> 2 votes
The Wikipedia definition merely "opens the parentheses". Using the pure set-theoretic definition, we would expect $$ ((r\_1,r\_2,\dots,r\_n),(s\_1,s\_2,\dots,s\_m)) $$ instead of $$ (r\_1,r\_2,\dots,r\_n,s\_1,s\_2,\dots,s\_m). $$ Assuming $R,S$ are both relations over the same universe $U$, the Wikipedia definition ensures that $R \times S$ is an $(n+m)$-ary relation over $U$. Under the set-theoretic definition, we get a binary relation over $U^n$ when $n = m$, and a unary relation over $U^n \times U^m$ in general.

We often write $U^n \times U^m = U^{n+m}$, but this isn't in general an equality of sets (it might be in some special cases, depending on the exact definition of $U^n$). Rather, we *identify* $U^n \times U^m$ with $U^{n+m}$, that is, we ignore the difference (this informal notion can be formalized). The difference between $R \times S$ as sets and as relations is similar – we identify the two objects although they are "physically" different.

---
Tags: database-theory, relational-algebra
---


# Question
Title: create a ANN with more than one neuron output
I start to learn artificial neural network and all introduction that I have found on internet present architecture with a number of input variable, so the input layer has the same number of "neurons" as number of variable. Then a number of neurons in hidden layers and only one output neurons.

Does it make sense to have several output neurons ? Is it the same method but with more neurons at the end ?

I have try to do some tests in fortran90, starting from a basic example, but I start to get confused to make it with more than one output neurons

Thanks

**EDIT**

To be more clear : is there a way to create an ANN with various output neurons that can take different states ? (without making a correspondence between K class corresponding to each possible output)

I would like to have 3 output neurons that will take the following states :

```
Inputs X  |  Outputs Y
----------------------
0 0 0 1 0 |   0 0 0
1 0 0 1 1 |   1 1 0
1 1 0 1 1 |   0 1 1
1 0 0 0 1 |   1 1 1
0 0 0 0 0 |   1 0 0

```

if yes what is the methods ?

# Answer
> 2 votes
It's possible to have more than one neuron in the output. The softmax function is used for that purpose. With this function, the output may have $K$ classes. If we have a network with $K = 3$ output classes, and some input shall belong to class $k = 1$, for example, the desired output would be: $\[1 0 0\]$. If another input shall belong to class $k = 2$, then the desired output would be $\[0 1 0\]$. And so on.

---
Tags: machine-learning, neural-networks
---


title: What are Lambda productions

text:
# Question
Title: What are Lambda productions
I'm taking a computational structures course and we just started going over context free grammars. I was confused when I started seeing lambda productions. What are they? Can't seem to find an answer anywhere.

# Answer
$\lambda$ (lambda) is sometimes used to denote the empty string. Thus, a "lambda production" is a production like $A \to \lambda$, i.e., a production that allows a non-terminal to generate the empty string.

Other sources will use $\epsilon$ (epsilon) to denote the empty string. They might refer to them as epsilon productions. They're the same thing. It's just a difference in notation.
> 2 votes

---
Tags: context-free, programming-languages
---


# Question
Title: Select largest subset, subject to a separate weighting constraint
Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that: $$ maximize\sum\_{i=1}^k c\_i \\ \sum\_{i=1}^k w\_i \ge W $$ It seems pretty simple at first. Without the weighting constraint, you can use any selection algorithm to select the $k$ elements with largest $c$. But with the weighting, it seems there's no special structure to exploit. Seems like you'd have to search all subsets?

# Answer
Use dynamic programming.

Let the $(c,w)$ pairs be $(c\_1,w\_1),\dots,(c\_n,w\_n)$. Define $A\[k^\*,n^\*,W^\*\]$ to be the largest possible sum of $c$-values obtainable by selecting $k^\*$ pairs from $(c\_1,w\_1),\dots,(c\_{n^\*},w\_{n^\*})$ such that the sum of their $w$-values is at least $W^\*$. Then you can write down a recursive definition of $A\[k^\*,n^\*,W^\*\]$:

$$A\[k^\*,n^\*,W^\*\] = \max(A\[k^\*,n^\*-1,W^\*\], A\[k^\*-1,n^\*-1,W^\*-w\_{n^\*}\]+c\_{n^\*}).$$

Now fill in this table using dynamic programming. The running time will be $O(nkW)$, where $n$ is the number of $(c,w)$-pairs in the input.

This is basically an adaptation of the dynamic programming algorithm for the knapsack problem: https://en.wikipedia.org/wiki/Knapsack\_problem#0.2F1\_knapsack\_problem
> 1 votes

---
Tags: optimization, selection-problem
---


# Question
Title: Can a regular expression based "grammatic" be programatically minimized?
I have a list of pairs like (regex, substitute) that take quite long to apply to some input text so I was thinking about optimizing them a bit.

From my knowledge for each regular expression there is a deterministic finite automaton that accepts the same language, and as its possible to merge DFAs merging two regex should be possible...

My question is now how does this interact with the fact that I want to replace something and not just match it.

---

Basically: given two pairs of a regex and its replacement in a specific order:

```
1. /\./    -> "Found #DOT#"
2. /#DOT#/ -> "something"

```

Is it programmatically possible to create a new pair:

```
   /\./    -> "Found something"

```

that applied to some input creates the same result?

---

Note: are e.g. Python regex even regular in the sense of theoretical informatic? (I mean would I get problems with e.g. look-arounds?)

My reason for asking: there are some regex-chains in my collection that just replace things with other things so that other regex can replace these things but that's only to keep it simple enough for a human to understand, a computer doesn't need to comprehend the regex.

# Answer
> 1 votes
I will describe a way that you could optimize the operation "find the first pattern that matches the input". Given a way to do that, you can repeatedly apply that operation: i.e., repeatedly find the first pattern that matches the input, apply the substitution, then repeat.

However, I'm not sure that this will be any better in practice, so this might be useless (unless the number of regexps is quite small).

## Union of NFAs

Any (language-theoretic) regular expression can be converted to a nondeterministic finite automaton (NFA) that recognizes the set of strings matched by the regexp (e.g., via Thompson's algorithm).

So, you can build a NFA for each pattern; and there are standard ways to build a NFA to represent the union of two or more NFAs, i.e., a NFA that accepts any input that is accepted by at least one of the NFAs. In particular, you use the product construction.

You can modify the product construction to find the first NFA that accepts an input. Let $N\_1,\dots,N\_k$ be $k$ NFAs. Each state of the new NFA is of the form $(q\_1,\dots,q\_k)$ where $q\_i$ is a state in $N\_i$. A state $(q\_1,\dots,q\_k)$ is accepting if any of the $q\_i$ are an accepting state in $i$. Also transitions are defined following the product construction, except that all transitions out of an accepting state go back to itself. If $(q\_1,\dots,q\_k)$ is accepting, then find the smallest $i$ such that $q\_i$ is accepting in $N\_i$; this indicates that the $i$th regexp was the first match.

In principle you can use standard algorithms to run this NFA on the input, or convert the NFA to a DFA via the powerset construction and then run this DFA on the input. In principle this provides a way to find the first matching pattern. In practice you might run into problems: running this NFA on the input might be no faster than running all regexps; and converting to a DFA might cause you to run out of available memory.

---
Tags: regular-expressions
---


# Question
Title: Data structures for annotations in large-scale text editor
I need to create a specialized text editor capable of handling text up to billions of characters long, with no line breaks.

I've read of multiple data structures to manage the text itself, including ropes, zippers, piece tables, gap buffers, and more.

However, I also need to support **annotations** on the text. Like comments in MS Word, each annotation lies over a range of positions. (Unlike MS Word comments, each annotation may lie over multiple non-intersecting ranges.)

Annotations can cover a single character or the whole text. Annotations may be created before, in between, or after text edits.

There can be tens to hundreds of thousands of annotations. Reacting to each edit by adjusting the coordinates of every single feature would incur a large, linear cost.

**What are data structures that would support the following, even as coordinates change due to text editing, whose complexity does not include the number of annotations as a factor?**

1. Finding the coordinates of features discovered by text search, in the current coordinate system resulting from text edits made after the annotations.
2. Finding annotations that intersect a range presented to the user, in the current coordinate system resulting from text edits made after the annotations.

For 1, one idea I've had is to store a history of coordinate-system changes, and apply all of those made after the feature's creation. However, the cost of this grows linearly with the number of edits.

For 2, one idea I've had is to create a custom R-tree of annotations which reacts to text edits by modifying its own coordinate system but not its clustering. But not sure how to handle new features, which don't necessarily lie anywhere in the original coordinate system. And again, the cost of this could grow linearly with the number of edits.

# Answer
There are many possible data structures you could use. I will list one.

## Augmented balanced binary tree

Stores the string in a balanced binary tree. Each leaf of the tree holds one character of the document, and you store them in a balanced binary tree data structure: e.g., a red-black tree or AVL tree. In other words, you think of the tree as representing a map $i \mapsto S\[i\]$ that maps from an index $i$ to the $i$th character in the document.

This data structure will avoid the need to update the coordinate system by the simple expedient of not using any coordinate system at all. No indices or offsets are used explicitly. Instead, everything is represented implicitly in the shape of the tree.

Note that each internal node of the tree implicitly corresponds to a substring of the tree: namely, it is the substring obtained by concatenating all leaves that are descendants of that node. Equivalently, it corresponds to an interval of indices: namely, the interval $\[\ell,r\]$ where $\ell$ is the index of the leftmost leaf under that internal node and $r$ is the index of the rightmost leaf under that node.

Also any substring of the document can be expressed into a disjoint union of $\le \lg n$ substrings obtained in this way. Thus, if $T$ is a substring of the document, it can be viewed as corresponding to a set of $\le \lg n$ internal nodes of the tree (so that concatenating all of the leaves under those nodes yields exactly $T$).

Now you have a list of annotation objects, one per annotation. The annotation object stores the set of internal nodes that correspond to the substring it is attached to. Also, each internal node in the tree has a list of backpointers to annotation objects that it is associated with.

Now to attach an annotation to some substring $T$, you simply find the corresponding set of internal nodes, create an annotation object, and add backpointers to that object from each of those internal nodes. This can be done in $O(\lg n)$ time.

Similarly, to delete or insert into the document, you insert or delete into the balanced binary tree data structure. You can quickly identify which annotations this affects, by looking at the range of leaves affected, finding a list of $\le lg n$ internal nodes whose disjoint union is exactly that range, and following the backpointers in those nodes and all of their descendants. Then you can update those annotation objects if needed. Insertion and deletion doesn't disturb any of the annotations on the rest of the document, so there is no need to update any coordinate system.

What if you want to do random-access into the middle of document, i.e., given an index $i$, you want to quickly find the $i$th character in the document? You can augment the data structure to make this efficient, by storing in each node the number of leaves it has under it. If you insert or delete something somewhere in the document, then you update one or more leaves and all of the nodes on the path from those leaves to the root.

In this way, all operations can be performed in basically $O(\log n)$ time.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Finding short readable representation of words
I am looking for Input/Literature on

1. a readable way to represent words (which are accepted by automata)
2. an Algorithm, that constructs the Representation

For example, a word $w$ might contain a subsequence $v$ which is repeated $m$ times, i.e. $w= u \\, \underbrace{v\cdots v}\_{100} \\,x$ where $u,v,w,x \in \Sigma^\*$

In a readable representation, I would expect this subsequence to occur only once, together with the information about the 100 repetitions.

---

**Motivation:**

I am working on an interactive input interface for a tool, that works with words that are accepted by automata. It requires the user to interact with possibly long words

* generated by the system
* or select words interactively himself

---

**My Approach:**

The representation I currently use structurally can be understood is an ordered tree, where

* the leaves are symbols $a \in \Sigma$
* the inner nodes are repetition counters $i \in \mathbb{N}$

Example:

$w = ABABAC \\, ABABACAC \\,ABABACAC \\,ABABACAC$

Representations

1. $\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
2. $\overbrace{\overbrace{AB}^{2}AC}^{2}\overbrace{AC\overbrace{AB}^{2}AC}^{2}AC$

I have implemented an algorithm which, given $w$, finds the 2. representation. I would consider 1. more appealing, and I assume, that I would generally prefer representations that are minimal with respect to length (where length is the total amounts of symbols/tree-leaves)

---

**My Questions:**

1. Is there a good algorithm to find representations minimal with respect to length?
2. Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
3. Can someone think of an alternative/better approach?

# Answer
> 2 votes
Given a string $S$ of length $n$, one can find the minimal representation in $O(n^3)$ time using dynamic programming.

Let's consider a representation as a binary tree. Each node of the tree generates a string (a substring of $S$). Each leaf generates to a single letter. The tree has two types of internal nodes: a *concatenation node*, which generates the concatenation of the strings generated by its two children; and a *repetition node*, which takes the string generated by its only child and repeats it $r$ times, where $r$ is an integer stored in the node. Your diagrams can all be represented in this form.

Now given a string $S$, we can find the minimal binary tree that generates it, using dynamic programming. We'll let $A\[i,j\]$ denote the minimal binary tree that generates the substring $S\[i..j-1\]$.

We can derive a recursive expression for $A\[i,k\]$. In particular, consider all of the following trees:

* a tree with a concatenation node at the root, and a left child $A\[i,j\]$ and a right child $A\[j,k\]$ (one such tree for each $j$)
* a tree with a repetition node at the root, holding the integer $r$, and a single child $A\[i,i+(j-i)/r\]$ (one such tree for each divisor $r$ of $j-i$)

We will find the smallest of these trees, and store the result in $A\[i,k\]$.

By evaluating this recursive relation in a bottom-up fashion (i.e., fill in entries of $A\[i,j\]$ in order of increasing value of $j-i$), we can fill in the entire table. There are $O(n^2)$ entries in the table, and each entry takes $O(n)$ time to fill in, so the total running time is $O(n^3)$.

---

As far as related concepts, your idea is similar to a context-free grammar, augmented with the notion of repetition (e.g., we add a production $A \to r \otimes B$, which means that if a word $w$ that can be produced by $B$, then $w^r$ can be produced by $A$). I haven't seen that particular notion explored, but context-free grammars *are* well-explored.

If you want heuristics to find a relatively small representation, but not necessarily the minimal one, you might be interested in the Sequitur algorithm and other uses of context-free grammars for data compression. I think that the Sequitur algorithm can be modified to work in your setting: i.e., given a string, find a (hopefully small) representation of that string.

---
Tags: formal-languages, automata, data-compression
---


# Question
Title: Cut costly functions in inter-procedural abstract interpretation
I am performing some inter-procedural abstract interpretation to capture certain program properties. Following the standard way, what I am doing is to maintain a work list of to-be-analyzed functions, and pick one from the work list to perform intra-procedural analysis until the work list is empty.

Currently, I observed that the ***intra-procedural*** analysis of certain functions would not terminate. Basically, it is just taking too much memory and become too slow to reason for even one more statement.

Of course, I can optimize my code base and improve the memory efficiency, but fundamentally that shouldn't help too much.

Now I am seeking for some strategies to bypass such obstacle. Intuitively, what I can do is to **cut a intra-procedural analysis off** whenever the memory usage grows too high, return a **Top** as the return value, and switch to the next function in my work list for analysis.

This seems very naturally, and should be **sound** as well! However, after some quick review of some abstract interpretation work, I don't see any related work performing such cut off.

So here is my question:

1. What is the standard approach in abstract interpretation if a intra-procedural analysis becomes too costly to finish?
2. I assume the cut off and return **Top** approach is sound. Then why shouldn't I find any related literature employing such approach? Is it too ad-hoc and naive?

# Answer
> 3 votes
Sure. "Cut off and return Top" is sound. It's valid. It seems like a reasonable thing to do.

I don't know if it has been studied or used before in the literature. I wouldn't be surprised if it has. It feels to me like a variant on widening, even though it's not identical to the usual widening operator. I've seen similar methods applied before (if you get stuck, give up and return Top) in other situations.

I don't think there's a single standard approach to this problem. My impression is that there are multiple techniques. You can memoize analysis of a function (so you lazily generate a transfer function that summarizes the effect of the function, in terms of its arguments, and then reuse that information when you need it again in the future). You can use widening operators. You can use counter-example guided refinement to start with a coarse abstraction (which is efficient for static analysis), and then make the abstraction more precise as needed. I imagine you could also do the converse: start with a fine-grained abstraction, and if it is taking too long, switch to a more coarse abstraction and restart the analysis with that coarser abstraction. There are probably many other possible techniques, and the best one might depend on the specifics of your particular analysis.

---
Tags: programming-languages, formal-methods, data-flow-analysis, static-analysis
---


title: prove CLIQUE is NP

text:
# Question
Title: prove CLIQUE is NP
I am reading a proof on CLIQUE is NP-Complete. The first step is of course to show that CLIQUE is NP.

> c is the clique certificate
>
> V = “On input $\langle\langle G, k\rangle, c\rangle$:
>
> 1. Test whether c is a set of k different nodes in G.
> 2. Test whether G contains all edges connecting nodes in c.
> 3. If both tests pass, accept; otherwise, reject.”

Is `c` just some arbitrary chosen set of k nodes? How would complexity analysis for **1** and **2** give polynomial time?

# Answer
To test whether $c$ is a set of $k$ different nodes in $G$ will going to take $O(c^2)$ time (just check for every possible pair). Now you want to check whether $c$ forms a clique, to do so you need to check every possible edge i.e. $O(c^2)$ into time to check edge is present between a pair or not. So time taken for step 1 and 2 is $O(c^2)$ + $O(c^2)$ i.e $O(c^2)$ polynomial in the input size.

You don't need to worry about $c$, it is a part of input or particularly certificate.
> 3 votes

# Answer
This is a very basic question, which suggests you should review some earlier material from your course.

* $c$ isn't chosen: it's the input that's given to you. It's the thing you're trying to verify. Note that the question doesn't specify the format of $c$, so you can choose anything reasonable. For example, if the vertices of the graph are $1, \dots, v$, then $c$ could be a list of numbers written in unary or binary, or it could be a string of $v$ bits, where the $i$th bit is $1$ iff the $i$th vertex is in the set.
* To test whether $c$ has the desired properties, you just need to loop through the elements of $c$ and check that they're all different, that there are at least $k$ of them and that they meet the definition of a clique. Think about how you'd do that with a pencil and paper, and that will give you an algorithm. Analyze how many steps that will take in terms of the size of $c$ and that will give you your polynomial bound.
> 0 votes

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


# Question
Title: Type Theory and Principia Mathematica Part IV "Relation Arithmetic"
As

* type theory is a principle focus of modern computer science,
* its origins are in Bertrand Russel's theory of types,
* Principia Mathematica is both the origin of and is expressed in the theory of types, and
* relational databases are among the highest value, most researched applications of computer science

it seems Russell's "Relation Arithmetic"\* (developed in Principia Mathematica Part IV "Relation Arithmetic") would be an active field of study in modern computer science.

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments:

> "I think relation-arithmetic important, not only as an interesting generalization, but because it supplies a symbolic technique required for dealing with structure. It has seemed to me that those who are not familiar with mathematical logic find great difficulty in understanding what is meant by 'structure', and, owing to this difficulty, are apt to go astray in attempting to **understand the empirical world**\[emphasis JAB\]. For this reason, if for no other, I am sorry that the theory of relation-arithmetic has been largely unnoticed."

Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use? If so, why?

\*A good, informal, introduction to relation-arithmetic is in Introduction to Mathematical Philosophy, by Bertrand Russell. One must first understand Russell's abstract definition of "number", drawn from Frege (Chapter II "DEFINITION OF NUMBER"). Then one can proceed to Chapter VI "SIMILARITY OF RELATIONS" where he defines relation-arithmetic.

Briefly, there are no "sets" in the sense we think of "set theory" -- there are only "relations" which may be "similar" to one another. All relations that are "similar" to one another comprise a "relation number". Similarity between two relations, P and Q, obtains if there is a one-to-one correspondence between the relata of P and the relata of Q such that if a relationship holds in P, the relationship also holds in Q between its corresponding relata. One can even think of ordinary numbers as relation numbers if one restricts the relations to one place relations (monadic/unary/property/etc.). I emphasize this because although Russell uses the word "class similarity" rather than "relation similarity" in Chapter II, it is apparent that he considers "class" to be a degenerate case of "relation" when one carefully reads Chapter IV. Because of this, and the fact that type theory is considered an alternate foundation for mathematics used in computer science, it may be incorrect to dismiss relation-arithmetic as a degenerate case of category theory or some other more complex mathematical structure in which it may be encoded or modeled. Such modeling or encoding should be the other way around.

"Relation numbers", thus defined, are then defined to have the ordinary arithmetic operators, addition, multiplication and even exponentiation.

# Answer
> 5 votes
> * relational databases are among the highest value, most researched applications of computer science

James, what do relational databases have to do with the question? And why have you tagged this q with 'relational-algebra'? It seems to me entirely gratuitous.

Just because databases are 'relational' does not mean they have much to do with whatever Russell meant by 'relation-arithmetic'.

Relational database theory sticks to simple set theory and FOPL. Precisely because it wants to avoid getting into higher-order complications (and type theory).

Similarly just because historically Russell's theory of types kicked off an area of research, does not mean that everything these days to do with type theory must therefore derive from Russell, or that his later musings would necessarily help.

> Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use? If so, why?

I'd say yes, entirely unnoticed.

Again what relevance does the "critical role computers play" have wrt Russell?

On looking at a few of the standard early works in programming language type theory, I see no citations of Russell: Landin 1965 on the semantics for ALGOL; Strachey 1967; Reynolds 1983.

The Reynolds paper has the word "relations" in the abstract. And cites a paper Morris 1973 'Types are not Sets'. And mentions \[Dana\] "Scott's discovery of how to construct sufficiently rich universes without encountering Russell's paradox".

Modern type theory derives mostly from typing models for Lambda Calculus; of which Russell had no inkling. That could be why.

BTW your opening link to the answer on type theory, which mentions "Russell's paradox occasionally shows up" then points to some results in Haskell I think is again drawing a very long bow. Also those results back in 2010 are for some early developments of then-new type-level features. I'd classify them as bugs. They rely essentially on Impredicativity about which the compiler's user guide says "GHC has extremely flaky support for impredicative polymorphism, ..."; indeed I think the feature is to be blocked as a 'very hard problem to get right'.

---
Tags: type-theory, relational-algebra, coq, calculus-of-constructions
---


title: how os can calculate cpu cache size?

text:
# Question
Title: how os can calculate cpu cache size?
There's an interview question.

In my opinion, os can calculate cache hit rate and miss rate(with the total running time of process and the number of transfer of block of memory to cache). But how can know the size of cache? Is it possible to calculate with os's certain information? (such as size of transfer size to cache)

We can assume anyting we need to calculate easily(like only one cache-no l1 l2 and so on, cache is fully associative or set associative or directed mapped and so on)

# Answer
> 3 votes
It's not clear to me what you want.

An OS can query the processor about its cache structure as long as the processor have the feature (for instance, X86 has this possibility tied with the CPUID instruction).

An OS could deduce the information from any mean of identifying the processor (nowadays something like CPUID, but in a given processor family there always had been more or less precise means to deduce which member your were running on, especially if you have access to privileged instructions as an OS does) and having hardcoded tables giving the sizes for each model.

Any program can try to measure the number of cache levels, their size, associativity, line size and latency. What you have to do is measure the latency of memory accesses using well-thought-out patterns and plotting the the latency versus the total memory touched by the pattern. You get some plateaus giving the latency of the cache, and the jumps positions give the cache sizes. Comparing the results of different patterns give the associativity and the line sizes. The more the cache is advanced (eviction buffers, pre-loading, ...) the more you have to be careful in the way the patterns are computed (a common technique is implementing the pattern as a pointer chase so that it is more difficult for the processor to guess the next address to be loaded) or you'll measure something different from what you want. Other factors to take into account is the effect of TLB, the presence of shared cache between cores and processors the load on the other cores, the effect of process migrations between cores by the OS, the effect of throttle by the OS or the hardware due to temperature or battery load. In conclusion such measurements are pretty technical, and although you can deduce a lot of things it is better to have a preconceived notion of the memory structure and of the external factors which may have an influence.

# Answer
> 2 votes
When your computer is started, and the first bit of software starts running on it, that software knows what class of processor it is running on - it knows that because it has been compiled for a certain class of processor, and if your computer had a different kind of processor the software would immediately crash, so the fact that the software is running proves what kind of processor it is running on.

Each class of processor comes with concrete processors that each behave slightly different. These differences are documented and can be used to determine what exact kind of processor there is. For example, the documention for x86 processors might say "on this group of processors, bit 12 of some condition code register is always zero, so after trying to set this bit to one it, will still be read as zero. On this other group of processor, the bit will be read as one after setting it to one". With that knowledge, the software can determine exactly which kind of processor there is.

And then, the software developers check their manuals again, and they read things like "this kind of processor always has 16KB of L1 data cache. For that kind of processor, you execute a certain instruction, and after that instruction, register two will contain the size of the L1 data cache in bytes". That's just an example, but these things *will* be documented, and the software developers use them to find out anything they want to know.

Now when you say "cache size", things are more complicated nowadays (they always are). As an example, an Intel server might have two sockets containing two separate physical chips, each chip might contain 8 cores, and each core might support two virtual cores. In that case, you might get the knowledge "there is 64 Kbyte of L1 cache, shared between two virtual cores, 256 KByte of L2 cache, shared between two real cores, and 12 MB of L3 cache, shared between all cores in one physical chip". So your computer would have a total of 64 x 8 x 2 KByte of L1 cache, 256 x 4 x 2 KByte of L2 cache, and 12 MByte x 2 of L3 cache, but each processor thread only sees a limited amount of that, and may have to share that cache with other processor threads.

---
Tags: operating-systems, cpu-cache
---


title: Finding the perimeter of a simplex

text:
# Question
Title: Finding the perimeter of a simplex
I hope this question is close enough to CS to be posted here. I need to write a method that will compute the perimeter of a simplex https://en.wikipedia.org/wiki/Simplex in any dimension given only the coordinates of its vertices. Is such a function even possible? I have tried going for it, but ended up with loads of nested loops and nothing functional. Right now I have a class named Point and a class named Simplex which constructs a Simplex from an array of these points. Any help is appreciated.

# Answer
> 0 votes
Solved it, my question was badly formulated, I had only coordinates of points not the vertices themselves, I have calculated the perimeter using the euclidean distance formula.

---
Tags: computational-geometry
---


# Question
Title: What information needs to be saved in a Lamport clock system to deduce message causality?
By using Lamport timestamps, we can determine the causality of messages. It is however unclear to me how one would deduce this simply from the lamport timestamp of the message.

Take the following model situation: there is a casuality break when it comes to process 2:

Now, we add Lamport clocks (hopefully I have done that correctly)

I'm at loss when it comes to understanding how I can read out the correct casuality of received messages by process 2 from just the timestamps. Unless I haven't determined the timestamps properly.

It looks like there's some additional information needed to do that. Maybe to save the timestamp of the message itself, and the id of the sending process?

# Answer
Lamport clocks are not designed to allow you to infer all causality. No one ever claimed that knowing the Lamport timestamp is enough to read out the causality of all messages.

Rather, Lamport clocks provide a partial ordering that is consistent with causality: if event $a$ happens before event $b$ (causally), then $a$'s timestamp will be smaller than event $b$. The converse does not necessarily hold.

See https://en.wikipedia.org/wiki/Lamport\_timestamps and https://en.wikipedia.org/wiki/Lamport\_timestamps#Implications.

If you want to read out the full causality, use vector clocks or other methods that are designed for that.
> 1 votes

---
Tags: parallel-computing, clocks
---


# Question
Title: On $1$-way functions and formalizing my intuitions about them
Let $a: \\{0, 1\\}^\* \to \\{0, 1\\}^\*$ be a $1$-way function and $b: \\{0, 1\\}^\* \to \\{0, 1\\}^\*$ be a $1$-way permutation.

Now, it makes intuitive sense to me that $a \circ b$ should be a $1$-way function, but I am having problems formalizing this. What would a rigorous proof of this look like? Or are my intuitions wrong and this is simply not a true statement?

# Answer
What would a rigorous proof look like? It would start with the assumptions that are given, and derive the conclusion you want to derive, with each step being logically and rigorously justified.

How should you approach this? Start with the definitions. If you know what the definition of a 1-way function is, then you know what you have to prove, to prove that $a \circ b$ is a 1-way function. Start by trying to prove that, using the assumptions you are given. You'll probably use a reduction at some point: if there exists an adversary against $a \circ b$, then....

This is a basic question, which suggests to me you should either review the material in your textbook on reduction-based proofs of security, or check whether you have the mathematical maturity for this topic.
> 1 votes

---
Tags: complexity-theory, cryptography
---


title: Reduce Clique to Set Cover

text:
# Question
Title: Reduce Clique to Set Cover
Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to know if the is a way to reduce clique to set cover directly without the use of the transitive rule.

# Answer
Both problems are **NP**-complete and, by definition, there is a direct reduction between any pair of **NP**-complete problems.
> 1 votes

---
Tags: set-cover, clique
---


# Question
Title: Prove that a model of infinite tapes is stronger then turing machine model
I want to prove that if we have a model, $A$, with unbound number of tapes, then $A$ is stronger then Turing Machine model. Can you help me with example of such a language that $M$ will fail but $A$ will give an output? thanks.

# Answer
> 4 votes
It is a standard proof that Turing machines with any finite number of tapes are equivalent to single-tape Turing machines, since you can code any fixed number of tapes on a single tape.

If you allow a Turing machine to have an infinite number of tapes, then you can decide any language $L$. To do this, first copy the input $x\_1\dots x\_\ell$ so that the $i$th tape contains the symbol $x\_i$ in its first cell. Now move all the tape heads back to position $1$ and enter some special state $q\_\mathrm{decide}$. Recall that the transition function decides what to do based on the state the machine is in at the moment, and what is under each of the infinitely many heads. So just define it to accept from state $q\_{\mathrm{decide}}$ if there is some $k$ such that it sees $w\_1, \dots, w\_k$ under the first $k$ heads and $w\_1\dots w\_k\in L$, and every other head sees the blank character; otherwise, it rejects.

Note that there is a philosophical problems with write down the transition function if $L$ is undecidable, but the function certainly exists.

---
Tags: turing-machines
---


# Question
Title: Find the central point in a metric-space point set, in less than $O(n^2)$?
I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I define as the point with the minimum sum of distances to all other points. The metric computation is slow, so needs to be avoided where possible.

The obvious way to find this point uses $n^2$ metric distance calculations, as it simply (a) calculates for each point the sum of distances to all other points and then (b) takes the minimum point.

Is there a way to do this in less than $O(n^2)$ distance comparisons? (Probably making use of the triangle inequality in some way, which should hold with my metric.)

A good approximation might suffice if an exact method doesn't exist.

# Answer
> 6 votes
No. You can't do better than $\Theta(n^2)$ in the worst case.

Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of that edge to be either $0.9$, $1.0$, or $1.1$; all of those choices are consistent with all of the other observations you've made and with the requirements of a metric (e.g., with the triangle inequality), so all three are possible; but they require different outputs. Thus, if your algorithm doesn't examine that edge and then outputs something, an adversary can always choose a length for the unexamined edge that will make your algorithm's output wrong.

---

However, if you know that all the points live in $\mathbb{R}^d$ (even though you are not given their coordinates), then the problem can be solved by measuring $O((d+1)n)$ distances, assuming no degeneracies (no subset of $d+1$ points are co-planar).

In particular, pick $d+1$ points randomly. These will be anchor points. Given their pairwise distances, you can compute coordinates for them that are consistent with their pairwise distances. Now, for every other point $P$, compute the distance from $P$ to each of the anchor points. Using triangulation and these distances, you can compute the location of $P$ relative to the anchor points and thus the coordinates for $P$. Do this for every non-anchor point $P$. Now you have coordinates for every point, and you can use those coordinates to find the central point without asking the oracle to give you any more pairwise distances. I don't know whether this last step can be done faster than $O(n^2)$ *time*, but it can be done without measuring any more pairwise distances.

# Answer
> 0 votes
Check out Piotr Indyk's work on fast algorithms for metric spaces. (*Sublinear Algorithms for Metric Space Problems*, in *Proceedings of STOC '99*, pp.428–434. ACM, 1999; PS) Section 3 gives a linear-time approximate 1-median algorithm.

---
Tags: complexity-theory, computational-geometry, lower-bounds, search-problem
---


title: Pumping Theorem and K

text:
# Question
Title: Pumping Theorem and K
I have an example from a textbook using a language $L = \\{ a^nb^ma^n : m, n \ge 0, n \ge m \\}$.

> We can use pumping theorem to show that $L$ is not context-free. If it were, then there would exist some $k$ such that any string $w$, where $|w| \ge k$, must satisfy the conditions of the theorem. We show one string $w$ that does not. Let $w =a^kb^ka^k$ where $k$ is the constant from the pumping theorem \[...\]

* Why have they chosen to use $k$? My understanding from the pumping theorem definition is that $k$ is an arbitrary integer $\>1$
* What is the relation of $k$ to $n$ and $m$ in the original language definition?
* Members of $L$ can have more $a$'s than $b$'s, but $a^kb^ka^k$ will result in an equal number of $a, b$. Is it not necessary in this case because an equal number of $a$'s and $b$'s is still a member of L? What happens when $L = \\{ a^nb^ma^n : m, n \ge 0, n \> m \\}$ and $a^kb^ka^k$ is not part of $L$?

I think this is holding me back from understanding how to prove my homework question of:

> Prove whether the language $\\{a^xb^yc^xd^y: x, y \ge 0\\}$ is context free or not

Apologies if these are basic. I've been racking my brain for days on these kinds of questions and I'm so lost. Thanks for any assistance.

# Answer
> 1 votes
Definition from Wikipedia:

> If a language L is context-free, then there exists some integer p ≥ 1 (called a "pumping length"\[1\]) such that every string s in L that has a length of p or more symbols (i.e. with |s| ≥ p) can be written as
>
> s = uvwxy
>
> with substrings u, v, w, x and y, such that
>
> 1. |vwx| ≤ p,
> 2. |vx| ≥ 1, and
> 3. $uv^nwx^ny$ is in L for all n ≥ 0.

k is called the pumping length and it's a positive integer. (it can be equal to 1).

k is NOT an arbitrary integer and every CFL is guaranteed to have one.

They chose the string w, since it's a contradicting example. (it's not a unique contradicting example)

I advise you to separate the string w (s in the definition) to different cases for-each position of v and x might be (which satisfy (!) the properties in the definition) and see if choosing some n (0 ... inf) creates a word that is not in L.

If w is in L and don't satisfy the pumping lemma (all the possible cases resolved in contradictions) -\> L is not a CFL.

\[Note that n=0 will remove x and v from the string, which sometimes help\]

\[Notice that w (in your example) is $\geq$ k, that's why you can use the pumping lemma. For strings that are shorter, you can't use it.\]

For example (1 case): if v and x consists only of 'b', choosing n = 2 will create a string with number of 'b' strictly larger than 'a' which is not satisfying L properties.

k has no relation to n and m, it's a constant. For each CFL you are guaranteed to have one.

Hint for your homework : a possible contradicting example choice is very similar to your example.

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Relational division

text:
# Question
Title: Relational division
I try to understand how the relational division can be expressed by primitive operations of the relational algebra. So, I found this formula (I writed it such as I found it in the same format):
$A \DIVIDEBY B = A\[X\] \MINUS ((A\[X\] \TIMES B) \MINUS A)\[X\]$
But I can't get this. If we use $\TIMES$ (the Cartesian product) then A and B relations can't have same attributes, so we need to rename these attributes, i.e.:
If we have $A \\{A\_1, A\_2, A\_3\\};B \\{A\_1, A\_2, A\_4\\}$
then the header of the result relation will be
$\\{A\_{11},A\_{21},A\_3,A\_{12},A\_{22},A\_4\\}$,
it's okay... But next I need to apply $\MINUS$ but I can't make it because my relation header diffs from $A$.
It means that it requires yet operations (i.e. $\PROJECT$ and $\RENAME$), it isn't? Can anyone explain me more details by this expression?

# Answer
> 1 votes
The usual form of Division requires that the attributes in `B` are a subset of the attributes in `A`. And the result of the Division has just the attributes particular to `A` -- that is `A[X]` in your formulation.

I'm not sure if you understand that `A[X]` **is** a projection. So the Heading of `A[X] TIMES B` is exactly the Heading of `A`. So the inner MINUS is dealing with the same Headings -- that is, Heading of `A`. Then the `[X]` at the end of the formula is again a projection; so the outer MINUS is also dealing with the same Headings -- this time `[X]`.

This answers much the same question (using a different notation): Expressing division in relational algebra in terms of other operations See my comments about the various different forms of 'Relational Division'.

And please note: relations have *Headings*, not 'Headers'.

---
Tags: relational-algebra
---


# Question
Title: how one memory can be accessed simultaneously in instruction fetch and data read?
In modern computer architecture, pipeline has stage that access memory for normal data and instruction in parallel.

But datas and instructions are usually in same memory, and their access address is different.

But how pipelined cpu can access them in parallel? Are the memory has two address port for read data and instruction respectively?

If they are in separate memory, they can be accessed simultaneously. But what if there are only one memory for them? one of them is just stalled?

# Answer
Modern CPUs usually feature separate instruction and data caches, so effectively, even if from a software PoV, everything is coming from a single memory space, there are physically separate busses and memories for instructions and data ("harvard", which is used for all reasonably fast CPUs nowadays).

There are also multi-port memories able to sustain several accesses simultanously. There is a great variety of architectures, for example DSPs or GPUs may have different memory organization than traditional CPUs.

In computers, with something like an x86 or an ARM, with an OS and applications, code memory is separate from data memory (there are attributes in MMU mappings), code is read-only. Except during on-the-fly dynamic compilation, or some library linkage, code is never modified through data accesses, there is no self-modifying code. It is nowadays far more efficient to have separate code and data memories for first level caches.

Many years ago, when one couldn't put billions of transistors on a die, there were shared or off-chip caches, and sometimes data accesses could effectively stall instruction fetches.
> 3 votes

---
Tags: computer-architecture, memory-hardware, cpu-pipelines
---


# Question
Title: Satisfiability of at least k linear equations over Z2 is NP-hard
Given a system of $m$ equations in $n$ boolean variables:

$$\begin{align} a\_{11}x\_1 + a\_{12}x\_2 + \dots +a\_{1n}x\_n &= b\_1\pmod2\\ a\_{21}x\_1 + a\_{22}x\_2 + \dots +a\_{2n}x\_n &= b\_2\pmod2\\ &\\;\vdots\\ a\_{m1}{x\_1} + a\_{m2}x\_2 + \dots +a\_{mn}x\_n &= b\_m\pmod2 \end{align}$$

Where all $a\_{ij}, x\_i$ and $b\_i$ are $0$ or $1$, I want to prove that the decision problem of finding if there is a vector $x$ that satisfies at least $k$ equation, is NP hard.

I was given a hint to reduce from 3-SAT, so I am trying to build from each clause in the 3-SAT formula several equations, such that **a constant number** of them is satisfied iff the clause is satisfied. But I am not sure how to impose this restriction of a constant number of equations satisfied (for all different truth assignments that satisfy the given clause).

# Answer
> 1 votes
Consider any clause $x \lor y \lor z$, and the following table: $$ \begin{array}{c|c|c|c} \text{satisfied literals} & \[x\]+\[y\]+\[z\] & \[x\oplus y\] + \[x\oplus z\] + \[y\oplus z\] & \[x\oplus y\oplus z\] \\\hline 0 & 0 & 0 & 0 \\\hline 1 & 1 & 2 & 1 \\\hline 2 & 2 & 2 & 0 \\\hline 3 & 3 & 0 & 1 \end{array} $$ Here $\[x\]$ is 1 if $x$ is satisfied and 0 otherwise.

The first row sums to 0, and the rest sum to 4 (ignoring the column labeled "satisfied literals"). Can you use this to your advantage?

---
Tags: np-complete, reductions, satisfiability
---


# Question
Title: Upper bound for the time complexity of a TM in P on input x?
I am trying to show that the following problem is P-complete with respect to LOGSPACE reductions: given a Turing machine $M^\*$, an input $x$ for that machine, and a number $t$ in unary, does $M^\*$ accept $x$ in $t$ steps?

To do that I want to compute an upper bound on the time complexity of some TM $M$ in P on input $x$. I tried to use the maximum number of configurations, but failed because I don't know the space complexity either - I only know that space and time complexities are polynomial.

# Answer
> 1 votes
The complexity class P is a set of *languages*, not a set of *Turing machines*. A language is in P if it is accepted by some Turing machine running in polynomial time. So for every language $L$ in P, there is a Turing machine $M$ that accepts $L$ and runs in time $p(n)$ for some polynomial $p$, where $n$ is the input length. This is exactly the time bound you're after — its existence is guaranteed by the definition of P.

To show that the problem you were given is P-complete, you need to show that every language in P reduces to your problem. In other words, you need to show that *for all* languages $L \in P$ *there exists* a polytime reduction from $L$ to your problem. The reduction accepts an instance of $L$, and can depend on $L$ arbitrarily.

What you seem to be trying to construct is a function with two inputs: a language $L \in P$ (given as a polytime Turing machine) and an instance $x$ of $L$. There is absolutely no need to construct such a function.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Prove a network is a feedforward network if and only if the numbering of its cells satisfy these conditions
Undergraduate math student here attempting to understand neural networks. Picked up a text on sale, "Neural Network Learning and Expert Systems" (Gallant), and I'm just starting on the exercises for chapter 1.

The full question is:

Prove that a network is a feedforward network if and only if its cells are numbered in a way such that:

* all $p$ input cells are numbered from $1$ to $p$.
* whenever cell $u\_j$ is connected to cell $u\_i$, then $j \< i$.

The definition of a feedforward network, according to Gallant, is a directed network such that there are no cycles between any nodes.

I'm confused for a few reasons.

1. This sounds like I'll need at least a basic understanding of graph theory, which I don't have. Any quick and dirty resources that should cover what I need for this kind of material? I don't even know how to represent a network like this mathematically.
2. I'm used to the numbering of things being pretty arbitrary, for example, numbering basis vectors in a set just to differentiate between them. I don't really have an intuitive idea for why the numbering of input cells is a factor in deciding if a network has directed cycles or not.

Thanks in advance.

# Answer
Let $G = (V, E)$ with $E \subseteq V \times V$ be a directed graph. A *cycle* is a path of edges $e\_1 = (v\_1, v\_2), e\_2=(v\_2, v\_3), ..., v\_n = (e\_n, e\_1)$ with $e\_i \in E$.

Hence, by definition, the second condition means that the graph has no cycles.

The first condition is necessary because otherwise there could be hidden nodes receiving input from the input nodes (and not vice versa). One could, of course, simply define input nodes as the nodes of a network which don't have incoming edges. But this might cause problems in the definition of recurrent networks.
> 0 votes

# Answer
One direction (given such a numbering, there are no cycles) is elementary, and I encourage you to work it out on your own. The other direction is topological sorting.
> 3 votes

# Answer
I think the question is not very clear; it should mention that when the network is activated, *first number `1` is activated, then `2`, etc. (chronological)*.

Say we have the following network:

* Inputs `1` and `2`
* Hidden cells `3`
* Output cells `4`
* connections `1>3`, `2>3`, `3>4`

This is a feed forward network, because all input cells are activated before the other cells and because every connection is pointing to a higher number than its origin number.

If the the network would look like this:

* Inputs `2` and `3`
* Hidden cells `1`
* output cells `4`
* connections `1>3`, `2>3`, `3>4`

You would see that the hidden cell gets activated BEFORE the input cells get activated, so the hidden cell is actually getting activated with the values of an input that is not given yet (so the previous input, because connections remain).
> 0 votes

---
Tags: graphs, machine-learning, neural-networks
---


# Question
Title: Asymptotics of a recurrence defined with two variables
What is the asymptotic behaviour, in Θ notation, of the smallest function that for any $n\_1$ and $n\_2$ satisfies the following:

$$t(n\_1+n\_2)≥t(n\_1)+t(n\_2)+c·\log\_2(1+n\_2)$$ where $n\_1≥n\_2≥1$ and $t(1)=1$

I tried to see what happens if $n\_1 = n\_2$:

$$t(2n)≥t(n)+t(n)+c·\log\_2(1+n)$$ $$t(n)≥2t(n/2)+c·\log\_2(1+n/2)$$

Also if $n\_2=1$:

$$t(n+1)≥t(n)+t(1)+c·\log\_2(2)$$ $$t(n)≥t(n-1)+1+c$$

But I am not sure where to go next, or if this is a correct approach.

# Answer
> 1 votes
The function $t$ is given by $t(n) = 1$ and for $n\>1$, $$ t(n) = \min\_{1 \leq k \leq n/2} t(n-k) + t(k) + c\log\_2(1+k). $$ You can prove by induction that $$ t(n) = n + c(n-1). $$ This holds when $n=1$. For the inductive step, $$ \begin{align\*} t(n-k) + t(k) + c\log\_2(1+k) &= \[n-k + c(n-k-1)\] + \[k + c(k-1)\] + c\log\_2(1+k) \\ &= n + c(n-2) + c\log\_2 (1+k) \\ &\geq n+c(n-2)+c \\ &= n + c(n-1). \end{align\*} $$

# Answer
> 2 votes
Interesting recurrence. Let's take a crack at this. Just a heads up, this answer is a bit wordy/explicit.

Clearly the first issue/difficulty is that we're trying to define this in terms of two variables ($n\_1, n\_2$). This *seems* hard so let's go ahead and redefine this relation:

$$t(n\_1 + n\_2) \geq t(n\_1) + t(n\_2) + c \log\_2(1 + n\_2)$$

Let $\alpha$ be a constant such that $0 \< \alpha \leq \frac{1}{2}$. We can then define $n$ and $n'$ as:

$$n = n\_1 + n\_2$$ $$n' = \lceil \alpha n \rceil$$

You also asked for the *smallest* function that satisfies this. I'm taking this to mean when the left side if smallest, so we will redefine $t(n\_1 + n\_2)$ as:

$$t(n) = t(n') + t(n - n') + c \log\_2(1 + n - n')$$

or possibly:

$$t(n) = t(n') + t(n - n') + c \log\_2(1 + n')$$

If we were just looking for the upper bound of $t(n\_1 + n\_2)$ then we would only need the first case because it is the *worst* case, but we are looking for the tight bound. In any case, we now have a more manageable form of our recurrence.

You can prove by induction that:

$$an \leq t(n) \leq bn - c\log\_2 n + d$$

for some constants $a,b,c \> 0$. Constant $d$ will be defined momentarily.

*Induction step for Lower Bound*

$$ \begin{align} t(n) & = t(n') + t(n - n') + c \log\_2(1 + n - n')\\ & \geq t(n') + t(n - n') + c \log\_2(1)\\ & = an' + an - an' + 0\\ & = an \end{align} $$

*Induction step for Upper Bound*

$$ \begin{align} t(n) &= t(n') + t(n - n') + c \log\_2(1 + n - n')\\ &\leq t(n') + t(n - n') + c \log\_2 n\\ &= bn' - c\log\_2n' + d + b(n-n') - c\log\_2(n-n') + d + c \log\_2 n\\ &= bn + 2d - c\log\_2n' - c\log\_2(n-n') + c \log\_2 n\\ &= bn + 2d - c\log\_2(n'(n-n')) + c \log\_2 n\\ &= bn + 2d - c\log\_2(\alpha n(n- \alpha n)) + c \log\_2 n\\ &= bn + 2d - c\log\_2(n^2 \alpha (1- \alpha )) + c \log\_2 n\\ &= bn + 2d - 2c\log\_2 n - c\log\_2( \alpha (1- \alpha )) + c \log\_2 n\\ &= bn - c \log\_2 n + 2d - c\log\_2( \alpha (1- \alpha )) \end{align} $$

Now we can define $d$ in terms of constants $c$ and $\alpha$.

$$ d = c\log\_2( \alpha (1- \alpha ))$$

Therefore

$$t(n) \leq bn - c \log\_2 n + d$$

Clearly $an \leq t(n) \leq bn$. It's worth noting this is because $d$ will always be negative.

Now we can conclude

$$t(n\_1 + n\_2) = \Theta(n\_1 + n\_2)$$

---
Tags: asymptotics
---


# Question
Title: CPU Scheduling - Round Robin order on ready queue
I am attempting the question below:

> Assume a set of processes $P\_1, P\_2, P\_3$ and $P\_4$ arrive at different times in the ready queue. The table below shows the burst time, the priority (smallest priority number implies highest priority) and arrival time for each of the processes. \begin{array}{|c|c|c|c|} \hline Process & Burst ~ time & Priority & Arrival ~ Time \\ \hline P\_1 & 8& 2& 0\\ \hline P\_2 & 2 & 3 & 1 \\ \hline P\_3 & 4 & 1 & 3 \\ \hline P\_4 & 6 & 2 & 5 \\ \hline \end{array} Draw a Gant chart, illustrating the execution of the processes, to demonstrate each of the following algorithms.
>
> 1. First-Come, First-Served (FCFS)
> 2. Round Robin(RR) with time slice of 3 time units.

Problem I am having is that my answer is not matching what I am getting form the simulator here.

The problem might be with the way I am handling my ready Queue. My workings and answer is below. The simulator shows that after first time P3 appears in the chart that P4 should start. But P1 was pre-empted and still had more execution hence I put P1 in there. Where am I going wrong?

Ready Queue (as I was working it out): P1,P2,P3,P1,P4,P3,P1,P4

GANT CHART:

# Answer
With round-robin, the scheduler always selects the process that's had the most time since it was last run, and *new processes coming in are always assigned a last run time of 1 time unit before the oldest last run time in the current list*. (There are other equivalent ways to state this, but this is the simplest one for me. One other way to phrase this that works for many people is "processes that haven't had a chance to run yet have priority".)

So at t=8, we have:

```
Process Last-run Time-left
P1      0        5
P3      3        1
P4      -1*      6

```

Note the -1 for P4. The oldest last run time is P1, with 0. So P4 gets assigned -1, and hence gets selected.
> 1 votes

---
Tags: scheduling
---


# Question
Title: I built a mechanical computer powered by marbles. What are its theoretical limitations?
Over the last couple years, I built a mechanical computer powered by marbles and made a game out of it. It's similar to the old Digi-Comp II, except for two key differences:

1. Parts are repositionable on the board.
2. You can connect multiple 'bits' together using gears. When one of these bits is flipped, it flips the other bits connected to it.

The above link describes how it works. My question is, what are its theoretical limitations? My theoretical computing background is weak, so please ELI5.

**edit:** I'm not interested in the obvious limitations: speed (not going to win any races there...), board size, or # of marbles. I'm more interested in its theoretical limitations. Maybe it would help to split it into two questions:

1. How can it be proven (or disproven) to be Turing-complete?
2. If more than 3 gear bits are connected together, the friction becomes too great for a marble to turn all of them at once. Does that create additional limitations?

Thanks - I'm really excited to read your answers! I've been thinking about this for a long time.

# Answer
What you have right now is a concrete computer. We cannot compare it to a computational model until it is properly formalized.

My intuition is that the board could be modeled as a dataflow architecture. Computational models conceived according to this paradigm can be Turing-complete, but (as was said in the comments) no concrete computer will ever be Turing-equivalent, and I don't think you should worry about this. All real computers are just (imperfect) working metaphors of formal computational models.

Should you come around to the idea of more closely imitating a Turing-equivalent dataflow machine, there are a few issues that could be addressed in order to "strengthen the metaphor", so to speak. Introducing **cycles** and **composition** of machines would be the two most important things, in my opinion, but I think your machine is already pretty amazing. It serves its purpose very well, and these "improvements" could sacrifice its usability.
> 4 votes

---
Tags: complexity-theory, turing-machines, computer-architecture, computation-models
---


# Question
Title: Calculate Miss rate of L2 cache given global and L1 miss rates
If I have a Global miss rate of all caches of a total of **5.41%** and the miss rate of a single level cache of **9.13%**, how can I effectively calculate how much the second level cache miss rate need to be?

I found this where it says that the Local miss rate equals misses in a cache divided by the total number of memory accesses to this cache (Miss rate L2) and Global miss rate equals misses in a cache divided by the total number of memory accesses generated by the CPU (Miss Rate L1 x Miss Rate L2).

So if I divide 5.41% / 9.13% it equals **0.5926%** for my second level cache. Is this assumption correct?

# Answer
You would only access the next level cache, only if its misses on the current one. Therefore the global miss rate is equal to multiplication of all the local miss rates.

```
0.0541    = L2 misses * 0.0913
L2 misses = 0.0541/0.0913 = 0.5926
L2 miss rate = 59.26%

```

In your answer you got the % in the wrong place.
> 1 votes

---
Tags: computer-architecture, cpu-cache, cpu
---


# Question
Title: Construct a TM for checking if a set of parentheses are well formed
This was a solved example given in my textbook. When I tried to solve this, I got a different TM that was given as the solution. I tried running a sample string through my TM, and somehow got the correct answer. Still the answers dont match. Please let me know if there isvsomething I've missed. This may sound a simple school homework but I would be grateful for any help

The one in ink is my solution (https://i.stack.imgur.com/PiJX6.jpg)

This is the textbook answer. (https://i.stack.imgur.com/p6HY7.jpg)

# Answer
A very important fact about Turing machines is that there may be many *equivalent* Turing machines for the same language. In other words, just because your answer and the book's answer are different *Turing machines*, they may both be correct answers. There is not just one Turing machine for any given task.

I am not sure if your Turing machine is actually correct (building a Turing machine without any errors is hard!), but if you answer the questions in my comments I can probably figure it out and update this answer. We can also try a few more input strings to check.
> 2 votes

---
Tags: turing-machines
---


title: Boolean expression to logic gates

text:
# Question
Title: Boolean expression to logic gates
Hello I need help with xy xor z, do I do the logic AND first or the XOR, no parenthesis. Thank You

# Answer
Usually, an operator that's written implicitly by just putting the operands next to each other (e.g., "$xy$" for $x\land y$ in logic or $x\times y$ in arithmetic) has precedence over binary operators that are written out explicitly (e.g., $\lor$ or $\oplus$ in logic, or $+$ in arithmetic). Indeed, any author who uses a different convention to that needs a good stern talking to. But note that it is only a convention.

So the expression in the question means $(xy)\oplus z$, unless the person who wrote it hates us. This view is reinforced by the fact that logical and is multiplication modulo 2, and xor is addition modulo 2 and we'd expect multiplication to have precedence over addition.
> 1 votes

---
Tags: boolean-algebra
---


# Question
Title: What are the differences between search problems, optimization problems, and decision problems?
How do we differentiate these classes of problems?

# Answer
A *decision problem* has this form:

* Input: $x$
* Output: "Yes" if $\phi(x)$ holds, "No" otherwise

A *search problem* has this form:

* Input $x$
* Output: $y$ such that $\psi(x,y)$ holds, if such a $y$ exists. "No" otherwise.

Finally, an *optimization problem* has this form:

* Input $x$
* Output: $y$ such that $f(x,y)$ is the minimum possible, i.e. $f(x,y) = \min\_{y'} f(x,y')$

Here $\phi$ and $\psi$ are some boolean properties, and $f$ is some natural number function of $x$ and $y$.
> 8 votes

# Answer
In a **search problem** you are looking for something.
In an **optimization problem** you want to find the best way to do something.
In a **decision problem** you are trying to decide whether something is true.

I suspect the reason you asked this question is that optimization or decision problems might be implementable in terms of a search problem. For example, if you are trying to decide whether a graph has some property, you might have to traverse (search) it.
> 1 votes

# Answer
**Decision problem**

Input is a question where the output is yes or no. Output is yes or no from the algorithm.

**Search problem**

This problem usually has several parts: Building a corpus, doing inserts and doing lookups. A common problem is to organize the data so that lookups can be done fast.

**Optimization problem**

Provided a constraint, for example x + y \< 10, optimize some formula for example x\*y and find its maximum or minimum value.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Intersection between language and regular set
This is tangentially related to a question I asked on the math stackexchange.

I read in a proof that if

$$ \begin{align\*} L\_1 &= \\{w ∈ \\{a, b, c\\}^\* : \text{$w$ has the same number of $a$, $b$, and $c$} \\}, \\ R &= L(a^\* b^\* c^\*), \end{align\*} $$

then $L ∩ R = \\{a^nb^nc^n: n ≥ 0\\}$.

Now unless I'm fundamentally misunderstanding intersection, why is the intersection between this language and the regular set is $a^nb^nc^n$ and not something like $a^ib^jc^k$ where $i,j,k \geq 0$? Is $R$ not the set including strings like abbccc or aaabbc?

# Answer
> 0 votes
Because $A\cap B = \\{x\mid x\in A\text{ and }x\in B\\}$.

---
Tags: regular-languages
---


# Question
Title: Do deterministic context free grammars always have corresponding deterministic push down automata?
> A language $L$ is deterministic context-free if and only if there is a deterministic push-down automaton M such that $L = L(M)$.

According to the answer key of this quiz, the above statement is false. Which is odd to me, if a context free language is one that can be defined by a pushdown automata, would a deterministic context free language not also be defined by a deterministic pushdown automata? Perhaps it's the "if and only if" that is at issue here.

I'm also referencing information from this post Are there inherently ambiguous and deterministic context-free languages?, which does imply that the above statement should be true.

# Answer
> 1 votes
I would agree with you, but local definitions may differ.

One point might be the definition of $L(M)$. What is the acceptance type of the PDA? That might be "empty stack" or "final state". For deterministic PDA the two modes of acceptance are not equivalent. But also here wikipedia agrees that $L$ indicates final state, which is commonly used for DCFL.

---
Tags: context-free, pushdown-automata
---


# Question
Title: How to find a good saw function for PRNG?
As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with about equal distribution?

This is what it is supposed to look like:

There are two functions I've got now,

y=(seed/1000\*state\*49) mod 101 and

z=(y-1 % 10) / 10)

and distribution looks like this (I'm not fine with that 1 and 0 distribution):

# Answer
I think this is an effect of the rounding in your implementation or in the histogram.

Let's say your histogram contains 100 columns. Each represents a width of 0.01. The column at 10 shows how many items fall between 9.995 and 10.005. The column at 0 shows how many items fall between -0.005 and 0.005. However, there are no items below 0, so there is nothing between -0.005 and 0. This column will only show halve of the items in the other columns.
> 1 votes

---
Tags: randomness, statistics, numerical-algorithms, random-number-generator
---


# Question
Title: ANN with communication between nodes of same layer
I starting to learn about artificial neural network.

I already did some simple things for classification, with different hidden layer.

I would like to know :

Is there a way to create "communication" (synapse) between neurons of the same layer ? If yes how will work the back-propagation ?

Thanks a lot

# Answer
> 2 votes
Yes! That is definitely possible. You should know that not all network topologies are layered. You could also have a network which consists of loose neurons which are connected to one another in a more liquid way:

The reason we have 'layers' in networks is not because they add functionality, but because they make coding easier and more overseeable. When you have for example this network:

```
input: [neuron1, neuron2]
hiddenlayer: [neuron3, neuron4, neuron5]
output: [neuron6]

```

that is exactly the same as:

`[neuron1, neuron2, neuron3, neuron4, neuron5, neuron6]`

Because all neurons get activated sequentially.

So what kind of synapses do you want to create inside a layer? Recurrent or feedforward?

# Answer
> 2 votes
Keep in mind that the training is about optimizing your cost function given the weights of your connections and the activation functions chosen. As long as you calculate the derivatives correctly(depending on your architecture, coding may become hard) taking care with your weights, everything may work. Depending on the architecture there may be changes in performance, which you would need to compare with other architectures.

---
Tags: neural-networks
---


# Question
Title: Are Petri Nets actually used in the industry
I'm having a hard time finding any prominent applications of Petri nets in the industry. Can you name some, or are Petri nets still just an academic curiosity?

# Answer
Petri-nets are e.g. used for Businees Process Modeling with BPMN. Of course Petri Nets are an abstract idea that lends itself to modelling a wide variety of dynamic and/or distributed systems - but especially for business processes, the provable reachability, liveness and boundedness are useful properties.
> 1 votes

---
Tags: applied-theory, petri-nets
---


# Question
Title: Efficient Algorithm to determine highly composited numbers
Im writing an algorithm to determine highly composited numbers. But it's very unefficient with $\Omega(f(n)) = n³$. Does someone know how i can make my code more efficient. Is my approach ok?

Here is my code:

```
import tools.Tools;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.TreeMap;

public class HighCompositeNumbers {

ArrayList<Long> hcnList = new ArrayList<>();

public HighCompositeNumbers(){
    hcnList.add(1L);
}

public TreeMap<Long, Long> primeFac(long n){
    final long limit = n;
    TreeMap<Long, Long> map = new TreeMap<>();
    for (long i=2; i<=limit/2+1; i+=1){
        long counter = 0;
        if (n % i == 0) map.put(i, 0L);
        while (n % i == 0) {
            n /= i;
            counter++;
        }
        if (counter != 0) map.put(i, counter);
    }
    return map;
}

public long numberOfDivisors(long n){
    TreeMap<Long, Long> map = primeFac(n);
    long divisors = 1;
    for (Long l : map.values()){
        divisors *= (l + 1);
    }
    return divisors;
}

public boolean isHighlyComposite(long n){
    long numOfDiv = numberOfDivisors(n);
    for (long i = n-1; i>=hcnList.get(hcnList.size()-1); i--){
        if (numberOfDivisors(i) >= numOfDiv) return false;
    }
    return true;
}

public static void main(String[] args) {
    long max = Tools.nextLong("max: ");
    HighCompositeNumbers hcn = new HighCompositeNumbers();
    //Tools.printHashMap(hcn.primeFac(max));

    for (long i=2L; i<= max; i++){
        if (hcn.isHighlyComposite(i)) hcn.hcnList.add(i);
    }

    System.out.println(hcn.hcnList);

}
}

```

# Answer
As in many cases, read the problem carefully first. The problem asks for all numbers that have more divisors than any small numbers. Nobody asks you to determine the number of divisors of lots of numbers.

First write down the formula how to calculate the number of divisors of n, given its factorisation into prime numbers. Then figure out rules that say what kinds of prime factors a highly composite number might have. Quite obviously a highly composite number must be a product $2^a·3^b·5^c·7^d...$ where a ≥ b ≥ c ≥ d and so on. That's because if for example a \< b, then $2^b·3^a$ would be smaller than $2^a·3^b$ but have the same number of prime factors.

That's just the start of it, but this should already help you to find highly composite numbers up to n a lot, lot faster than O (n).
> 2 votes

# Answer
You could create something similar to the Sieve of Eratosthenes, except instead of only iterating up to $\sqrt{n}$ you would need to iterate all the way up to $n$. Each iteration you would tally up the amount of divisors a particular number has.

```
arr = list of length n
for i = 1 to n:
  for j = i to n by i:
    arr[j] += 1

curr = arr[0]
for i = 1 to n:
  if arr[i] > curr:
    // i is highly composite!!!
    curr = arr[i]

```

The complexity can be represented by a summation:

$$ \begin{align} f(n) & = cn + \frac{cn}{2} + \frac{cn}{3} + \dots + c\\ & = cn \sum\_{i = 1}^n \frac{1}{i}\\ & = cn \cdot H\_n \end{align}$$ where $H\_n$ is the $n$th Harmonic Number. $H\_n$ is $\Theta(\log n)$, proof here.

It follows that this algorithm runs in $\Theta(n \log n)$.
> 0 votes

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


# Question
Title: Example of a non-regular language that is a subset of a regular language?
How can this be? I don't think it is actually possible for a non-regular language to be a subset of a regular language. What examples are there where this is true?

# Answer
> 5 votes
Every language over an alphabet $\Sigma$ is, by definition, a subset of $\Sigma^\*$, which is regular. If you want a less trivial example,

$$\\{a^nb^n\mid n\geq 0\\}\subseteq L(a^\*b^\*)\\,.$$

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