# Question
Title: Are mathematical functions used in computer science?
Well, I know the difference between functions used in math and C language. But what are those specific areas where mathematical functions are used?

# Answer
Strictly speaking, "functions" in computer science are actually the *computable* functions (i.e. the morphisms in the category of computable objects).

This is important, because Cantor's theorem states that there is no set $X$ such that there is a bijection between $X$ and its powerset. However, it is possible in many programming languages to define a type which has this property. For example, this type in Haskell:

```
newtype X = X (X -> Bool)

```

defines a type $X$ such that $X \cong 2^X$. This is not an isomorphism in the category of sets-with-functions, but it is an isomorphism in the category of computable sets-with-computable functions. Hence, it doesn't contradict Cantor's theorem.

In a comment, it seems like you're actually asking a numeric analysis question. Of course, we *use* elementary and special functions in scientific computing, engineering computing, computer graphics, etc. Anything that involves geometry, physics, simulation, statistics, etc involves the evaluation of elementary functions and special functions.

There is also a whole subfield of numeric analysis devoted to how to calculate functions of this kind. See, for example, all of the software that falls into GAMS Class C. Any introductory book on numeric analysis will have at least a chapter on this topic.

Just as a final note: For some special functions, it's sometimes not immediately obvious what convention to use, the most famous example of which is the gamma function. As an industry, we appear to have settled on the NIST Digital Library of Mathematical Functions (the companion and successor to the classic Abramowitz and Stegun) as the authoritative source.
> 2 votes

# Answer
You *can* write mathematical functions in computer science. The OCaml function `id (x: int): int = x`, for example, is a mathematical function $id : \mathbb{Z} \rightarrow \mathbb{Z}$, where $id = n \mapsto n$ (OK, if we ignore the fact that OCaml `int`s are machine integers and not bignums, just for a second.

However, not all programming functions are mathematical functions (i.e. many-to-one relations between two sets $S$ and $R$). Specifically, by this definition, a function is also a set; however, the "domain" of programming functions can contain the function itself. Consider, for example, the OCaml function `id x = x`, which has the type `'a -> 'a` (or, mathematically, $\forall \alpha \ . \ \alpha$). Note that `id` can be applied to itself. This violate the Axiom of Regularity in Zermelo-Fraenkel set theory; however, `id` is a real mathematical construct that concretely exists. It's a *thing* that is not a mathematical function!

Instead, programming language researchers interpret functions either inside domain theory as functions in complete partial orders (cpo's) \[note: in this approach they're interpreted a bit differently so that it doesn't violate the Axiom of Regularity anymore\], or alternatively inside category theory as functors between categories (which I don't claim to fully understand). This approach of understanding computational constructs is called **denotational semantics**.
> 0 votes

---
Tags: functional-programming, generating-functions
---


# Question
Title: Linear-time algorithm to check monotonicity of polygonal chain
A polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once.

I want to design a linear-time algorithm to check whether there exists a line $L$ such that a given chain $C$ with $n$ vertices is monotone relative to $L$, and find such a line.

My idea is to take an angel of monotone chain and transfer it to the unit circle and suppose there is a line L ! like this

But I don't know how to find a good solution that the L exist

# Answer
> 1 votes
This answer is related to the remarkable answer for a similar problem. The only difference is that the OP asked about monotonicity of a polygonal chain, but not about monotonicity of a polygon.

The algorithm idea is the same - we need to determine ranges of "authorized" angles for normals to $L$ looking at the adjacent chain segments. An angle is considered *authorized* if a normal with this angle defines such a straight line $L$, that all the straight lines, orthogonal to $L$, intersect the chain not more than once. In case of a polygon it was enough to look at concave vertices only, but in our case we must look at **all the internal vertices**.

The picture below shows a polygonal chain with four segments. Authorized angles at each internal vertex are marked by green color.

If an intersection of all the $(n-1)$ ranges of authorized angles isn't empty, then the polygonal chain is monotone, and the line $L$ exists. This algorithm apparently will take $O(n)$ steps.

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


# Question
Title: Adding edges to a graph that satisfy logical expressions
Easy question. I have a homework problem with its answer that i am unable to interpret.

An explanation on how to arrive at the answer is what I'm looking for.
Please let me know what the palette is too. I'm having a difficult time finding information on this problem.

# Answer
> 0 votes
I think I understand the graph now. The graph should be colored with three colors, T, F and N, standing for True, False and Neither. The three form a clique (hence the black edges), so that they have to be assigned a different color each. The assigned color should then be interpreted as the respective boolean value assignement. The four literals have an edge to Neither, so that they have to be assgined another value (i.e. True or False). Each literal also has an edge to its negation, so that it has to be assigned another value than its negation. The three nodes on the right can be seen as "helper" nodes. They are needed to ensure that any assignment to A and B will result in A xor B = true.

---
Tags: graphs, colorings
---


title: What is “Oracle Access”?

text:
# Question
Title: What is “Oracle Access”?
I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a data structure of sublinear size".

Searching for information on what Oracle Access is has given me nothing but stuff about Oracle Databases, which is obviously not what I'm looking for. I can't really wrap my head around what this means.

Can anyone point me in the right direction?

# Answer
> 12 votes
An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. *How* the oracle does this is abstracted away from (and sometimes an oracle might even do something impossible like solve the halting problem). It's just a way of saying "presume we had these computational abilities, then ...".

# Answer
> 0 votes
An oracle machine is an abstract machine which is assumed to solve a problem that might be undecidable or not yet solved.

For instance, "if we know how to solve problem A we can also solve problem B". Then we assume an "oracle" solving problem A even though we don't have a solution.

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


# Question
Title: Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime
In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.

I have not been able to solve this one:

> The set of strings of 0s and 1s, beginning with a 1, and interpreted as an integer, that integer is prime.

My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).

# Answer
> 2 votes
I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$.

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\\{0,1,2\\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that $N = 20\cdot 100^{28} + \sum\limits\_{0\leq i\< 28}30\cdot 100^i + 9 = 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem. Here, we also use that $29$ does not divide $100-1$.

I hope from this you are able to solve the exercise.

# Answer
> 1 votes
One way to show that this language isn’t regular is to use the following theorem:

> Let $L$ be a regular language over $\Sigma$, and let $c\_n = |L \cap \Sigma^n|$. There exists a modulus $m \geq 1$ such that for all $0 \leq r \< m$ there exist real $C,\lambda \geq 0$ and integer $k \geq 0$ such that the following asymptotic estimate holds for $n \equiv r \pmod{m}$: $$ c\_n \sim Cn^k \lambda^n. $$

In your case, $c\_n$ is the number of primes between $2^{n-1}$ and $2^n-1$. According to the prime number theorem, the number of primes up to $2^n$ is asymptotic to $2^n/n \log 2$, and so $$ c\_n \sim \frac{1}{\log 2} \left( \frac{2^n}{n} - \frac{2^{n-1}}{n-1} \right) \sim \frac{1}{2\log 2} \frac{2^n}{n}. $$ This contradicts the theorem above.

---
Tags: formal-languages, pumping-lemma, number-theory
---


# Question
Title: Term rewrite system for terms of lambda calculus?
Are there term rewrite systems, that can rewrite complex lambda term (with nested function application) into some other lambda terms, I.e. reorde function application and, possibly, introduce new variables and add some additional functions into the final term? Google is no help here, because it says, that lamda calculi itself is term rewriting system? Maybe I should use lamda calculus on the lambda calculus? Any reference would be great, some pointers. I can study the field further myself.

E.g I would like start by complex termi with nested functions Sentence(vp(John, walks)) and end with another complex term walks#(John). There may be or may not be some kind of semantic correspondence between input and output. I am just seek i ng framework and scientific tradition that allows to specify such transformations and execute them.

# Answer
I think that what you are looking for is called higher-order rewriting. There are systems in which you can define rewrite rules of the form $F\\;(\lambda x.\lambda y.C\\;X\[x,y\]) \longrightarrow X\[X\[t,u\],v\]$ for example, where $F$ and $C$ denote a function symbol and a constant symbols respectively. Note that here, $X$ denotes a higher-order variable (or meta-variable) of arity $2$. In the left-hand side (or pattern), it can be matched against any term containing only variables of $\\{x,y\\}$. The matched term is then used to replace the occurrences of $X$ in the right-hand side to apply the rewriting rule.

Note that the only terms that match the rewriting rule above are of the form $F\\;(\lambda x.\lambda y.C\\;A)$, with $FV(A) \subseteq \\{x,y\\}$. In this case, the variable $X$ is instantiated with $\hat{A}\[-,-\]$, which is a kind of context such that $A = \hat{A}\[x,y\]$.
> 4 votes

# Answer
It's hard to understand what you are looking for, but perhaps you are looking for *program transformations*.

A famous one is the CPS transform (continuation-passing style), which transforms any lambda term $t$ into a quite different one $t'$, which has a semantics related to that of $t$. E.g., $t'$ might follow the call-by-name evaluation of $t$ (CBN CPS transform) or the call-by-value evaluation (CBV CPS transform).

In the implementation of compilers for functional languages (which usually extend the lambda calculus), you may find many other transformations, usually used to optimize code. "Lambda floating", for instance. Essentially, one can rewrite $\lambda x. g (h y) x$ as ${\sf let}\ z=h y\ {\sf in}\ \lambda x. g z x$ so that $hy$ is only evaluated once, even if the function is called many times. CSE (common subexpression elimination) is another well known program transformation.
> 3 votes

---
Tags: lambda-calculus, term-rewriting
---


# Question
Title: Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P
The question and its answer is given in the following picture:

But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that the algorithm runs in $O(n^4)$ time not $O(n^3)$ as written, am I right?

# Answer
> 5 votes
Step 2 causes at most $n$ repetitions since each repetition other than the last one marks a node which wasn't previously marked. Since there are only $n$ nodes and one of them is marked in Step 1, there are at most $n-1$ repetitions which mark a new node, and one more which doesn't (and so moves to Step 4).

In Step 3, we go over all nodes in $G$ ($n$ nodes), and check all its neighbors ($n-1$ neighbors), so there are at most $n(n-1)$ repetitions of the inner part.

As for how many steps does this take when implemented on a Turing machine, this depends on the implementation. Outside of introductory courses on theory of computation, we almost never consider Turing machines, preferring instead to work with more intuitive models such as the RAM machine. Therefore mastering the intricacies of Turing machine behavior is not so important.

---
Tags: complexity-theory, turing-machines, computability, time-complexity, p-vs-np
---


# Question
Title: Is there a difference between computational graphs and neural networks?
According to this post, "neural networks are a special form \[of a computational graph\]". I think that one can infer from that that all neural networks are computational graphs.

My question then would be: **are there computational graphs that aren't neural networks?**

# Answer
> 2 votes
a computational graph is made of node where is done "operation" on incoming variables. (see first paragraph from the link done in OP)

A neural network use perceptron or "neuron" model for each node. a generic example of neuron model is : Each incoming value is multiply by a "synaptic" weight, then are sum and the result will be pass to an activation function. Which will give an output result that could be project to next nodes. Neural Network can "learn" by adapting synaptic weights thanks to methods such as backpropagation or direct feedback alignment.

Any computational graph where nodes are not a kind of neuron/perceptron model are not neural network.

# Answer
> 0 votes
Any computational graph that does not yield neural network functionality is a computational graph but not a neural network.

Such as this image from the link you have provided:

If you consider this directed graph as it is, then you have a computational graph. Being a neural network requires a goal that the network has to reach gradually.

---
Tags: graphs, neural-networks
---


# Question
Title: Find the maximizing row-column matches in a matrix
I have a set of R x C matrices similar to the following (can be much longer):

```
    C1      C2      C3      C4      C5      C6
R1  0.32    0.81    NA      NA      NA      NA
R2  0.90    -0.44   0.95    NA      NA      NA
R3  NA      0.93    0.86    0.24    NA      NA
R4  NA      NA      0.70    0.74    0.15    0.05
R5  NA      NA      NA      NA      NA      NA

```

I need to find the sequence of row-columns matchings that provides the overall maximum values (when summed). Each row can be associated to one and only one column, and "cross" matchings are not allowed, i.e. if R2 was matched with C4, a following row R\>2 cannot be matched with a previous column C\<4.

Given the limit on crossed matching, and as the number of rows and column can be unequal, obviously not all rows and/or columns will be matched

The solution in this example would be:

```
[R2:C1 = 0.90] + [R3:C2 = 0.93] + [R4:C4 = 0.74] = 2.57
```

which is higher than alternative solutions that may contain the highest values in the matrix, such as:

```
[R2:C2 = 0.81] + [R2:C3 = 0.95] + [R4:C4 = 0.74] = 2.50
```

The only solution I came up with is to create all possible RxC matrices populated by 1 and 0 where the marginal of each row and each column is not greater than 1, and where the no-crossing rule is respected. Then by multiplying such matrices with the original ones, I obtain new matrices containing ONLY the values in the solution, which can be easily summed.

Example of the solution above:

```
    C1  C2  C3  C4  C5  C6  |   row
R1  0   0   0   0   0   0   |   0
R2  1   0   0   0   0   0   |   1
R3  0   1   0   0   0   0   |   1
R4  0   0   0   1   0   0   |   1
R5  0   0   0   0   0   0   |   0
_______________________________
col 1   1   0   1   0   0

```

This is a valid matrix as all the marginals are \<= 1 and the positioning is ordered by column = 1,2,4 and by row = 2,3,4

The problem with this solution is that as R or C grows the number of possible permutations becomes extreme.

I need to implement a general and fast solution in a software, and I can't compute millions of table each time.

Any hint will be useful, thanks!!!!

---

EDIT: This is my implementation of D.W.'s answer in pseudo code

```
result = matrix(R, C, 0) //allocate response matrix RxC with all elements = 0
for (i from 1 to R){
  for (j from 1 to C){
    part1 = A[i-1,j]
    part2 = array[j] //allocates array of length j
    for(jPrime in 1:j){
      part2[jPrime] = M[i,jPrime] + A[i-1,jPrime-1]
    }
    A[i,j] = max(part1, max(part2))
 }
}

```

This returns the following A matrix:

```
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,] 0.32 0.81 0.81 0.81 0.81 0.81
[2,] 0.90 0.90 1.76 1.76 1.76 1.76
[3,] 0.90 1.83 1.83 2.00 2.00 2.00
[4,] 0.90 1.83 2.53 2.57 2.57 2.57
[5,] 0.90 1.83 2.53 2.57 2.57 2.57

```

# Answer
The problem can be solved with dynamic programming in $O(RC)$ time.

I'll start by showing how to solve it in $O(RC^2)$ time. Let $M\[\cdot,\cdot\]$ denote the input matrix. Let $A\[i,j\]$ denote the total value of the best matching using only rows $1..i$ and columns $1..j$. We will compute the entries of $A\[\cdot,\cdot\]$. There is a recursive relation for $A\[\cdot,\cdot\]$:

$$A\[i,j\] = \max(A\[i-1,j\],\max\\{M\[i,j'\] + A\[i-1,j'-1\] : 1 \le j' \le j\\}).$$

Here the $A\[i-1,j\]$ term corresponds to not including any match for row $i$, and the $\max\\{M\[i,j'\] + A\[i-1,j'-1\] : 1 \le j' \le j\\}$ corresponds to matching row $i$ to column $j'$.

You can fill in the entries of the $A$ array in a straightforward way in $O(RC^2)$ time, and the value of the best matching is given by $A\[R,C\]$. So, this gives an $O(RC^2)$ time algorithm.

You can speed this up to $O(RC)$ time by simultaneously computing another array $B\[\cdot,\cdot\]$, with entries defined as

$$B\[i,j\] = \max(A\[i,1\],A\[i,2\],\dots,A\[i,j\]).$$

Then all of the entries of $A$ and $B$ can be filled in, if you do it in the right order, in a total of $O(RC)$ time. This is linear in the size of the matrix, i.e., proportional to the number of entries in the input matrix. Since any algorithm will presumably have to examine all entries in the matrix, I think that means this algorithm is asymptotically optimal: no algorithm can run faster by more than a constant factor.
> 4 votes

---
Tags: combinatorics, matrices
---


title: What is Control ROM and Decision ROM?

text:
# Question
Title: What is Control ROM and Decision ROM?
I have done some research but I cannot answer this question. Please Help.

# Answer
> 3 votes
This terminology is some 30 or more years old coming from the times when Read-only memory (ROM) was a way to implement functions as a cheaper alternative than a general purpose processor. In 1980s hardware many functions would be implemented as ROM modules.

For example, below is a diagram from a 1991 patent US US5072291.

Here one can see different components representing different types of circuits: adders, delay circuits, line memories and ROM circuits. For instance the large upright rectangle at the bottom right part of the image represents an image type detection circuit implemented using ROM technology. This module can be called a Decision ROM.

Nowadays this terminology is rarely used.

---
Tags: logic, digital-circuits
---


title: Could a directed graph be bipartite?

text:
# Question
Title: Could a directed graph be bipartite?
I check for the symmetric directed graph and it's impossible to be bipartite , because we can't divide the vertices into two sets since all will have in - and out arrow but in general it could be right ? if I draw a graph with one direction

# Answer
> 9 votes
The monograph Digraphs: Theory, Algorithms and Applications by Bang-Jensen and Gutin defines a bipartite digraph as a digraph whose vertices can be partitioned into two sets $A,B$ such that every directed edge connects a vertex in $A$ to a vertex in $B$ or vice versa. Alternatively, a bipartite digraph is a digraph which can be obtained from a bipartite graph by replacing each undirected edge by a directed edge or by a pair of directed edges.

In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.

---
Tags: algorithms, graphs
---


# Question
Title: How to Add IEEE 754 Floating Point Numbers
I'm trying to add two 16 bit numbers that use a similar format as IEEE 754. The format is in the image below:

I can't figure out how to add together two numbers for the life of me.

Specifically, 0x82A3 + 0x0B98. In my attempt to solve this, I got 0x0B98 as the final sum, but that doesn't seem right to me.

# Answer
> 4 votes
It is difficult, and there are lots of special cases to handle.

Step 1: Determine if any of the operands is an Infinity or a Not-A-Number. In this case, look up the IEEE 754 standard and determine the result accordingly.

Step 2: Extract the sign, the biased exponent, and the mantissa. Add any implicit leading bit to the mantissa. Check whatever special rules there are: In the IEEE 754 32 and 64 bit format, a biased exponent of 0 means that there is no implicit leading bit in the mantissa, but the exponent should be treated as if it was 1. Add three extra bits containing zeroes to the mantissa.

Step 3: Make sure the exponents are the same. If one number has an exponent that is smaller by k, then shift that numbers mantissa to the right by k bit positions. If k is greater than 3, then set the last bit of the mantissa to 1 if any non-zero bits were shifted out. If k is so large that *all* mantissa bits would be shifted out then set the mantissa to zero, and don't try to shift by some huge amount.

Step 4: If the operands have different signs and the second mantissa is larger then exchange the operands. Add or subtract the mantissas, depending on the sign bits.

Step 5: If you added the mantissas and there was a carry, then increase the exponent, and shift the mantissa one bit position to the right. If the bit that is shifted out is non-zero, then set the last bit of the mantissa.

Step 6: If you subtracted the mantissas then count the number of leading zero bits in the mantissa. If all mantissa bits are zero then set the biased exponent to 1. Otherwise, shift the mantissa to the left and decrease the exponent, making sure that the biased exponent doesn't get smaller than 1.

Step 7: Perform rounding according to IEEE 754 rules. That's where the three extra mantissa bits are used. Remove the extra 3 mantissa bits. Due to the "round to even" rule, you round up (increase the mantissa by 1) if the last bit is 0 and the bits removed are 101 or larger, or the last bit is 1 and the bits removed are 100 or larger.

Step 8: If you rounded up and there is a carry then shift the mantissa one bit to the right and increase the exponent. If the biased exponent is too large then the result is infinity. If the biased exponent is 1 and the highest mantissa bit is zero then the biased exponent is changed to 0.

Step 9: Drop the highest bit of the mantissa, and pack sign, biased exponent, and mantissa together.

---
Tags: floating-point
---


# Question
Title: Why is the intersection of these two Languages Recursively Enumerable, not Recursive?
I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language L3, L3 ∩ L1 is recursively enumerable. But I thought it would be recursive?

Now, the text and I came to the same first conclusion - that it is important to deduce that L1 is a recursive language, since it is regular, and go from there - but my understanding is that if a recursive language had an undecideable intersected, you'll either get the empty set (which is recursive) or you'll get a set of elements common to both. Since all elements in a recursive must lead to halting, then the elements of the intersection all must lead to halting.

Hence '(recursive) ∩ (rec enu but not recursive)' and so 'L1 ∩ L3' should be recursive?

I must have gone wrong somewhere because the text, without explanation, just says it's recursively enumerable - where have I gone wrong? Thanks for your insight.

# Answer
Let $L\_1$ be the full language. Certainly, $L\_3 \cap L\_1 = L\_3$, which by assumption is not recursive.

I didn’t fully follow your reasoning in the second paragraph, but you might want to think some more about which Turing machine “must lead to halting” refers to. In particular, a Turing machine for our $L\_1$ will halt on every string, but this does not tell you that any subset of the full language is recursive.

---

**Edit:** I’ll try to address your comments here where I have more space.

We are dealing with a double set structure: At the lowermost level, we have words. Languages are set of words, but we are also talking about sets of languages, i.e., sets of sets of words, such as the set of regular languages. The relationship between regular, recursively enumerable and recursive languages happens on the upper level: Let $L$ be any regular language, which means that it is accepted by a finite automaton $\mathcal{A}$. Because every finite automaton $\mathcal{A}$ can be implemented as a Turing machine $\mathcal{M}$, we know that $L$ must also be a recursive language. Since every such element $L$ of the set of regular languages is an element of the set of recursive languages, the former is a subset of the latter.

This does not mean much on the level of individual words. Let’s again take the language $L\_1 := \Sigma^\*$ of all words. This language is decided by the Turing Machine $\mathcal{M}\_1$ that always accepts. Thus, $L\_1$ is in the set of recursive languages and every word “leads to halting” for the specific machine $\mathcal{M}\_1$. Now let us consider the language $L\_3$ of Turing machines that terminate on the empty input. It can be accepted by a universal Turing Machine $\mathcal{M}\_3$, so the language is recursively enumerable (and we know that it is not recursive). Sure, every word in the intersection of $L\_1$ and $L\_3$ will make both $\mathcal{M}\_1$ and $\mathcal{M}\_3$ terminate and accept.

But how do you build a single Turing machine from that that still accepts the intersection and will reject everything else? The first attempt would be to simulate both Turing machines and accept if both accept. As soon as one rejects, you reject. Indeed, this machine accepts the intersection and proves that the intersection is recursively enumerable. But if $\mathcal{M}\_1$ accepts and $\mathcal{M}\_3$ diverges, your machine will also diverge. To reject, you would have to figure out in finite time whether $\mathcal{M}\_3$ is diverging on the current input or just takes a long time to accept. This is not possible to do for all inputs.
> 1 votes

---
Tags: computability, closure-properties, semi-decidability
---


# Question
Title: Why is adding log probabilities considered "numerically stable"?
Every once in a while, I come across the term *numerical stability*, which I don't really understand. In particular, I have seen a description of the practice of "adding logs rather than multiplying numbers" as "numerically stable." I would like to know why this is considered numerically stable.

By "adding logs rather than multiplying numbers" I mean that if you have several numbers, for example 0.01, 0.001, 0.0001, and you want to get their product, you can instead add the logs of each term. In this case assuming log base 10, the result would be -2 -3 -4 = -9. This doesn't give you the same output as multiplying, but it's a good way to get something like the product so that you don't experience numerical underflow.

My question is that I'm a bit confused because the definitions of numerical stability I've found on the Internet don't seem to apply to this case. The definitions of "numerical stability" I've found are that it occurs when a "malformed input" doesn't affect the performance of an algorithm, see for example here. In this case I don't really see how we would consider the numbers 0.01 etc "malformed," they are what they are. It would be more accurate to say that the **algorithm (of multiplying them) is bad** in this context since the computer can't handle it, so we choose a better algorithm. So why do people say this is "numerically stable"?

# Answer
> 6 votes
A "numerically stable" method calculates a result in a way that will not produce excessive rounding errors.

Given a small number x, let's say x = 0.00079, it is possible to calculate log (1 + x) with much higher precision than 1 + x. (Of course calculating log (1 + x) avoids adding 1 + x). In both cases the relative error will be small and about equal size, but since the logarithm is very small, it's absolute error is much smaller.

So if you want to calculate the product of values $1 + x\_i$ for many small i, then you use a clever method to calculate $log (1 + x\_i)$, add those values, and calculate the exponential. With probabilities, it is possible that you have say 1,000,000 events each with small probability $p\_i$, and the probability that none of the events happens is the product of $1 - p\_i$, and calculating that probability is more precisely done by adding logarithms (you would also keep the rounding errors down by always adding the two smallest values).

In other situations, using logarithms can be less precise. For multiplication, the relative error is independent of the size of the numbers. But if you add logarithms, and say their sum is around 100, then each addition loses precision because 7 bits of the mantissa are used to store the 100. The precision of your result will be much less. So it's quite the opposite of numerically stable.

Start with x = 1, y = 0. Then for i = 1 to 100, multiply x by i, and add log i to y. Then for i = 1 to 100, divide x by i, and subtract log i from y. Except for rounding errors, you should end up with x = 1 and y = 0. Check how much the difference is.

PS. How do we calculate log (1 + x) without calculating 1 + x? There is the power series around 1, $ln (x) = (x-1) / 1 - (x-1)^2 / 2 + (x-1)^3 / 3 ...$. If we substitute 1 + x, then $ln(1 + x) = x / 1 - x^2 / 2 + x^3 / 3 ...$, which is obviously calculated without ever calculating 1 + x.

That's an important lesson: Given a problem that suggests an obvious sequence of steps to solve it, you will very often find a better and less obvious solution. To calculate log (1+x), the obvious sequence of steps is to calculate y = 1+x, z = log (y), but there is a much better solution that completely avoids the first step.

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$
Suppose I have a directed graph with edge weights drawn from range $\[1,\dots, K\]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the algorithm / data structure and improve the time complexity to $O(|V|+|E|)$?

# Answer
If edge weights are integers in $\\{0,1,\ldots,K\\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation.

At any time, the (finite) keys in the priority queue are in some range $\\{D,D+1,\ldots,D+K\\}$, where $D$ is the value of the last key removed from the priority queue. (Every key is at least $D$, because the sequence of keys removed by Dijkstra's algorithm is non-decreasing, and every key is at most $D+K$, because every key has value $d\[u\] + wt(u,w)$ for some edge $(u,w)$ where $d\[u\]$ is the distance from the source to some vertex $u$ that has already been removed, so $d\[u\]\le D$.)

Because of this, you can implement the priority queue with a circular array $A\[0..K\]$ of size $K+1$, with each cell containing a bucket. Store each vertex with key $k$ in the bucket in cell $A\[h(k)\]$ where $h(k)=k \bmod (K+1)$. Keep track of $D$. Do operations as follows:

* **delete-min**: While $A\[h(D)\]$ is empty, increment $D$. Then delete and return a vertex from $A\[h(D)\]$.
* **insert** with key $k$: Add the vertex to the bucket of $A\[h(k)\]$.
* **decrease-key** $k$ to $k'$: Move the vertex from $A\[h(k)\]$ to $A\[h(k')\]$.

Insert and decrease-key are constant-time operations, so the total time spent in those operations will be $O(|V|+|E|)$. The total time spent in delete-min will be $O(|V|)$ plus the final value of $D$. The final value of $D$ is the maximum (finite) distance from the source to any vertex (because a delete-min that takes $i$ iterations increases $D$ by $i$). The maximum distance is at most $K(|V|-1)$ because each path has at most $|V|-1$ edges. Thus, the total time spent by the algorithm is $O(K|V|+|E|)$.
> 19 votes

# Answer
I assume here that $K$ is an integer and the edge weights are integral. Otherwise it doesn't really buy you anything, you can always rescale weights so that the min edge has cost $1$ and the max has cost $K$, so the problem is identical to the standard shortest path problem.

Algorithm/proof sketch: Implement the priority queue in this kind of crazy way as an array of $K\times |V|$ lists keyed by cost and otherwise use the standard Dijkstra's algorithm. Keep a counter that tracks the cost of the minimum item in the heap. Resolve the dequeue call after items are deleted by *linear scanning*. Yes, this sort of sounds insane, but constant $K$ let's you cheat and fool your algorithmic intuition against linear scans. You only need to scan up from the last min marker because Disjkstra's algorithm is nice to your queue implementation. By the time it requests a dequeue, the items inserted into queue are always greater or equal to the previous minimum. The longest shortest path possible has length $K\times |V|$, so your amortized scanning cost is $K\times |V| = O(|V|)$ if K is constant.
> 5 votes

# Answer
you can use topological sort to find the solution, let the source to have degree 0 then, go from each edge from the source, if another vertex has 0 degree then put it into the queue and keep doing that. in this case(without cycle inside the graph) it can achieve V + E as it would go through every vertex and edges once and only once.
> -2 votes

---
Tags: algorithms, data-structures, shortest-path, weighted-graphs
---


# Question
Title: How to find the distance between two nodes in an undirected graph, from a neighborhood matrix?
Given a distance-1 neighborhood matrix representing an undirected graph, I'm trying to calculate the distances between two nodes so I can work out the distance-2 matrix, then the distance-3 matrix, and so on...

How to find this distance?

Any help would be appreciated.

# Answer
> 1 votes
I assume that by distance-$2$ matrix you mean the matrix $A$ such that $A\_{ij}=1$ if there is a path of length exactly $2$ between node $i$ and node $j$.

Let us call $B$ the distance-$1$ matrix, then remember that $B^2$ is such that $(B^2)\_{ij}$ is the number of paths of legth $2$ between $i$ and $j$. So all you have to do is to check whether an entry of $B^2$ is $0$ or not.

---
Tags: graphs
---


# Question
Title: How to calculate complexity of an algorithm which calls a subroutine?
Consider the following example:

Algorithm $A$ has Algorithm $B$ as its subroutine. The running time of algorithm $A$ without counting the time spent running the algorithm $B$ subroutine is $O(n^4)$. One call of algorithm $B$ takes $O(n^3)$ time. In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times.

What is the running time of algorithm $A$ including subroutines?

a. $O(n^4)$

b. $O(n^9)$

c. $O(n^7)$

d. $O(n^6)$

# Answer
This sentence: "In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times" is vague. If it means in each iteration of $A$, then as each time the calling $B$ takes $10n^2\times O(n^3) = O(n^5)$, we can say $A$ will be run in $n^4 \times O(n^5) = O(n^9)$.

On the other hand, if it means in all round of $A$, it calls $10n^2$ times $B$, as you said the time complexity would be $O(n^5)$.
> 1 votes

---
Tags: algorithms, time-complexity, runtime-analysis
---


# Question
Title: Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$
I just didn't understand the second part of the prove

**"G has twice as many edges as vertices only "**... what do I actually have to prove ?

I understand it like $n=2e$ , is it right ?

then isn't it's just similar to the degree equation ??

# Answer
When $n \leq 4$, the possible number of edges is less than twice the number of vertices. For example, when $n = 4$, there are 4 vertices but only 6 edges. In contrast, the complete graph on 5 vertices contains 10 edges.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is It Possible For a Data Structure to Have Constant Time Access/Insertion/Deletion?
I'm trying to come up with a data structure that could access, insert, and delete **any** element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and understanding about computer science. However, I'm starting to question whether it is even possible.

My theory is: For access to be in constant time, the data would need to be stored in a static location (like an array). And for insertion/deletion to be in constant time, the data would need to be stored dynamically using pointers or some sort of lookup table (like a linked list). Therefore, no data structure can have all three operations run in constant time.

Is this reasoning correct?

EDIT:

`access(index): returns element at given index`

`insert(element, index): Inserts element into 'index' and shifts everything after 'index' right one index`

`delete(index): Removes element at 'index' and corrects indexes so that there are no gaps (i.e. shifts everything after 'index' left one index)`

# Answer
## How do we get lower bounds?

As D.W. noted, lower bounds are hard. But that doesn't mean that no progress can be made. To get a lower bound, it is required (well, not strictly, but you won't get very far without one) that you make a (possible restrictive) model of all algorithms or data-structures that can solve your problem.

For example, the $\Omega(n\log n)$ lower bound for sorting holds only for the restrictive 'comparison based sorting' algorithms. (this is why counting sort can 'beat' this time in some cases: it isn't comparison based)

## Lower bounds for data structures

For the case of data-structures, the *cell-probe model* seems a good place to start. This model is similar to the more common RAM-model, but can be useful for lower bounds as it 'only counts' the number of accesses to stored data (i.e. the number of 'probes' to a cell).

For example, in the paper by Yao that introduces this model, lower bounds are calculated for the data structure supporting INSERT, DELETE and MEMBER (test for membership) queries. I think that a similar technique could work for your data-structure as well.

Do note that the paper by Yao is a bit outdated. I mostly mentioned it because the problem it considered is relatively simple and similar to yours. More modern techniques are covered in the dissertation of Kasper Green Larsen.
> 2 votes

# Answer
I don't find the reasoning convincing. Perhaps there is some other way to do it you haven't imagined yet. Proving lower bounds is hard.

That said, I doubt that it's possible to support all three operations in $O(1)$ time, though I don't have a proof.
> 0 votes

# Answer
It have been prooven, that what you expect is not possible, the lower bound is somewhere like $\Omega{\left( \frac{\log n}{\log \log n} \right)} $ (see here, like TillmanZ already pointed out).

However, hashing gives very fast lookup (somewhere like $\mathcal{O} (1) $ in general). The so-called Cuckoo-hashing guarantees constant lookup and *expected* constant insert time (amortized). Deletion normally is not considered but it can be done really simply by lookup and clearing the value, resulting also in $\mathcal{O} (1) $.
> 0 votes

---
Tags: data-structures, constant-time
---


# Question
Title: Is it immediately true that the class of P is a subset of the class NP?
Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the basics.

My question is, is it immediately true that class P is a subset of the class NP? That is, do we need to prove that the set of problems for which a solution may be obtained in polynomial time, is a subset of the class of problems for which a potential solution may be verified in polynomial time?

For example, consider a problem has multiple solutions and suppose that at least one of these solutions can be found by a program that runs in polynomial time. Then this problem is clearly in the class of P, since **a** solution can be found in polynomial time.

However, this does not tell us that **all** solutions are verifyable in polynomial time. Could it not be the case that some other solution to the problem is very difficult to verify?

# Answer
> 1 votes
P problems are a subset of NP problems. For a problem to be in P it must be decidable in polynomial time. For a problem to be in NP, it must be verifiable in polynomial time. If a problem is decidable in polynomial time, it is clearly verifiable in polynomial time as it can simply be verified by deciding it a second time. Therefore, all P problems are in NP.

I think that the fundamental component that you may not be remembering is that P and NP refer to specific time complexity classes of *decision problems*. Decision problems can't return general solutions. They can return yes (accept), no (reject), or never return.

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


title: Is every problem in NP?

text:
# Question
Title: Is every problem in NP?
My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt.

To show that a given problem is in NP, we have to verify a solution to a given instance of the problem can be solved in polynomial time. We get this. What we wanted to know is that is by default then every existing problem is in NP until a solution for the problem is derived in polynomial time? Or is it that we have completely missed the concept?

# Answer
There are plenty of problems where there is likely no way to verify a solution in polynomial time.

Amazingly, the problem "is p a prime number" is in NP due to some deep mathematical theorem that shows that for every prime number, there is a polynomial time proof that it is a prime number. (For many, many NP complete problems the part that there is a polynomial time proof is quite trivial).

A simple problem: Given an integer n, how many prime numbers p \<= n are there? There are ways to calculate this in $O(n^{2/3})$ and possibly a bit faster (which is exponential in the problem size). But there seems to be no possible proof that is less time consuming then finding the solution from scratch. so no proof that doesn't take exponential time.

Here's a simple problem that I believe has an absurdly high time complexity: On the UK TV show "Countdown", the contestants are given six slightly random numbers, and another larger number, and are asked to form the larger number by combining any or all of the six random numbers using + - * and /. That's the simplest problem. The next, harder problem: Given six integers and some larger n, can all integers 1 ≤ i ≤ n be formed that way? The next, harder problem: Given n, are there six numbers a1 to a6 so that all integers ≤ n can be formed by combing a1 to a6?

And the final problem (as a decision problem): Given an integer k ≥ 1, and a larger integer n ≥ 1, are there k integers $a\_1$ to $a\_k$ such that all integers 1 ≤ k ≤ n can be formed by combining any or all of $a\_1$ to $a\_k$ using +, -, \*, / ?
> 4 votes

# Answer
By the time hierarchy theorem, there are problems in NEXPTIME and EXPSPACE which are not in NP.

One famous example of a problem which is not in NP is deciding whether two regular expressions represent the same language. If the regular expressions are built from union, concatenation, and squaring, then the problem is NEXPTIME-complete. If we add Kleene star, the problem is EXPSPACE-complete. Either way, the problem is not in NP.

A large and important class of problems which are generally not in NP is the class of satsifiability modulo theories (SMT) decision problems.

Take, for example, Presburger arithmetic, which is the theory of natural numbers with addition. This is known to be decidable. (Adding multiplication gives you Peano arithmetic, which Gödel showed was not decidable.)

This is a problem that is built on top of boolean logic, in the sense that statements in Presburger arithmetic are statements in logic where some of those statements are statements about natural numbers.

So the decision problem for Presburger arithmetic includes SAT as a subproblem. SAT is NP-hard, so we might expect the Presburger arithmetic problem to be more complex than that. And, indeed, it is known to be in 2EXPTIME and not in NP.

It's a similar story with the decision problem for real closed fields.
> 3 votes

---
Tags: complexity-theory, np-hard, np, p-vs-np
---


# Question
Title: Counting solutions of a particular type in HORN SAT
I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same.

1. Suppose we have a HORN SAT -: $(x\_1) \land (x\_2 \implies x\_1)$, then the solutions are $(1, 0)$ and $(1,1)$. For solutions of type #, I would like to eliminate $(1,1)$ as after negating $x\_2$ we will still have a valid solution. In some sense $(1,1)$ is not a minimal solution. Do solutions of type # have a formal name? It seems natural that SAT solvers must strive to obtain solutions of type # and use those to generate other solutions.
2. Since the problem of HORN satisfiability is easy, are there efficient algorithms for counting HORN sat solutions? If so, could someone please point me to a good reference.

# Answer
Finding the minimal solution can be done in polynomial time (in fact, linear time), using the standard algorithm. There is always only a single minimal solution, and the standard algorithm for testing satisfiability of a HornSAT instance will also give you the minimal solution.

Counting the number of solutions is #P-complete and thus seems to be quite hard; see Is #HORNSAT polynomial?.
> 1 votes

---
Tags: satisfiability, counting, sat-solvers
---


# Question
Title: On FPTAS and many one parsimonious reductions
We have two $NP$ complete problems $\Pi\_1$ and $\Pi\_2$. Suppose $\Pi\_1\rightarrow\Pi\_2$ be a many one parsimonious reduction.

1. If $\Pi\_1$ has an FPTAS then does $\Pi\_2$ also have?
2. If $\Pi\_2$ has an FPTAS then does $\Pi\_1$ also have?

# Answer
Regarding number 1: The reduction to 3-SAT in the Cook-Levin theorem is many-one and parsimonious. There's no FPTAS for 3-SAT unless $\mathcal{P=NP}$, yet any problem in $\mathcal{NP}$, including those with a FPTAS, reduce to it in the fashion you describe.
With respect to number 2: I don't know many problems with FPTAS's but I strongly suspect that, if you look through a few and the reductions that prove them to be $\mathcal{NP}$-complete, you'll quickly find a counterexample. That's because I don't see any connection between being able to count solutions and being able to approximate them.
> 0 votes

---
Tags: complexity-theory, np-complete, reductions, approximation, counting
---


# Question
Title: Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular
I believe this statement to be true. And here's my reasoning:

> Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ must also be regular.

Do you think my reasoning is valid?

# Answer
> 13 votes
The statement is false. Consider the language $L = \\{a^n b : n \geq 0\\}$. Then $L' = \\{ a^n b a^n b : n \geq 0 \\}$ is not regular (exercise).

The invalid point in your reasoning is a confusion between the following two languages: $L' = \\{ ww : w \in L \\}$ and $L'' = \\{ w\_1w\_2 : w\_1,w\_2 \in L \\}$. It is $L''$ which is the concatenation of $L$ with itself. Whereas $L'$ need not be regular, $L''$ is always regular when $L$ is.

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


# Question
Title: How is memory address applied to address pins in RAM chips
I'm reading this book about assembly however I got stuck on one part, I can't seem to comprehend how memory address is 'applied' to the address pins

This is the image from the book

What I know here is the data pin applies voltage on the memory cell's input or output pin. And for the select pin the book explained that a binary code address is applied to the address pins, I imagined this part where there is only 1 address pin and 'something' is encoding the address to it, however looking at the diagram there are a lot of address pins for a few memory locations and they are connected to each other.

So my question here is how is the address "applied" to the address pins? Which part of the chip applies the address to the address pings because the book only said "You apply this address to the address pins"

btw, the book is titled "Assembly Language Step-by-Step - Programming with Linux 3rd edition" in case somebody who might've read it before can explain it to me.. Thanks in advance!

# Answer
Actually those 4 dots mean repeat. This means there are $2^{20} = 0x0FFFFF = 1,048,576$ memory cells, each with a line from the decoder. A few too many to draw them all.

Each of the lines from the decoder to a cell is an enable line. If not enabled the memory cell will do nothing (and have any output lines set to the data bus high impedance). If enabled the memory cell will read and write as you would expect.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n)
> Prove that for every computable function $f \colon \mathbb N \to \mathbb N$, there exists a computable function $g \colon \mathbb N \to \mathbb N$ such that for every $n$ we have $f(n) ≤ g(n)$.

Can anyone please explain me, why my proof below is not correct?

* > Lets assume, for the sake of arriving at a contradiction, that there exists a computable function $f$ such that for every computable function $g$, there
> exists an $n$ such that $f(n) \> g(n)$.
* > For each computable function $g$, let $n(g)$ be the smallest $n$ such that $f(n) \> g(n)$. Let $n\_0$ be the maximum of $n(g)$ over all computable functions $g$, and assume that this maximum is achieved for $g\_0$, that is, $n(g\_0) = n\_0$.
* > Define a function $g\_1$ that is equal to $g\_0$ for all values except for $n\_0$, and for $n\_0$ we have $g\_1(n\_0) = f(n\_0)$. This function $g\_1$ is computable because $g\_0$ is computable and $g\_1$ differs from $g\_0$ in only one point. By definition, $n(g\_1) ≥ n(g\_0) + 1$, and this contradicts the fact that $n(g)$ was maximized at $g\_0$.

# Answer
> 2 votes
The problem with your proof is in the definition of $n\_0$. The function $n(g)$ can be unbounded (as a function of $g$).

A much simpler proof would be to take $g = f$.

---
Tags: computability
---


# Question
Title: Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?
> If r and s are any two regular expressions, then (r ∪ s)\* = r\* ∪ s\* ∪ (rs)\*.

I think this is not true. And I believe this would always be true :

> (r ∪ s)\* = r\* ∪ s\*

I wanted to clarify this because of `(rs)*`. What do you think the right hand side would be if `r* ∪ s* ∪ (rs)*` ?

# Answer
> 1 votes
Consider the alphabet $\Sigma = \\{a,b\\}$, and the regular expressions $r = a$ and $s = b$. Then $(r+s)^\* = \Sigma^\*$ whereas $a^\*+b^\*$ and $a^\*+b^\*+(ab)^\*$ are both smaller.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: The equational theory of regular languages has no finite set of axioms for general alphabets
According to Redko the equational theory of regular languages with operations $+, \cdot, \*$ over a single letter has no finite set of axioms.

> Why does this imply that it has no finite set of axioms over an arbitrary alphabet?

Suppose I have a finite set of axioms for the equational theory of an alphabet with more than one letter, how would this give a finite set of axioms for the single letter case? I mean in the single letter case we have additional equations which did not hold in the arbitrary case, for examle $AB = BA$ for two languages $A,B$, and therefore which could not be derived from the axioms, hence these axioms do not axiomatize the single letter case.

Some clarification as asked for in the comments: Given a fixed alphabet $\Sigma$ and a set of variables $X = \\{A,B,C,\ldots\\}$, the terms are inductively defined:

1) Every $a \in \Sigma$ is a term,

2) Every variable $X$ is a term,

3) If $s,t$ are terms, then $s + t, s\cdot t, t^{\ast}$ are terms.

The interpretation of the regular sets $\mathcal{Reg}(\Sigma)\subseteq \mathcal P(\Sigma^{\ast})$ is as usual. As written in the comments, as set of terms $\Gamma$ axiomises $\mathcal{Reg}(\Sigma)$, the regular languages over a given alphabet $\Sigma$, if $$ \Gamma \vdash t\_1 = t\_2 \mbox{ iff } \mathcal{Reg}(\Sigma) \models t\_1 = t\_2. $$ Where $t\_1, t\_2$ are terms with alphabet letters from $\Sigma$, and variables are interpreted as universally quantified. The only rule of interference being substitution, that I mean by equational logic.

# Answer
For each $k \> 0$, the equation $$ A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}) $$ holds for regular languages over every alphabet, hence if for some alphabet we have a finite axiomatization, this equation is provable from it. Now as shown in A. Ginsburg, *Algebraic Theory of Automata*, the following infinite system of axioms is complete for unary regular languages. \begin{align\*} A + B & = B + A \\ A + (B + C) & = (A + B) + C \\ A + A & = A \\ A + \emptyset & = A \\ AB &= BA \\ (AB)C & = A(BC) \\ A1 & = A \\ A \emptyset & = \emptyset \\ (A+B)C & = AC + BC \\ 1^{\ast} & = 1, \emptyset^{\ast} = 1 \\ (AB^{\ast})^{\ast} & = 1 + AA^{\ast}B^{\ast} \\ (A + B)^{\ast} & = A^{\ast} B^{\ast} \\ A^{\ast} & = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}), \quad k \> 0 \end{align\*} So we get a finite axiomatisation for unary languages, if we take but the last family of axioms, and all axioms from the finite axiom system for some alphabet that prove $$ A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}) $$ for each $k \> 0$. Then all of the above equations are derivable by this finite axiom system, and as the above one is complete, this finite axiom system would be complete, which is not possible. Hence there is no finite system of axioms for any alphabet.
> 4 votes

---
Tags: formal-languages, regular-languages, finite-automata, first-order-logic
---


title: Language Decidability

text:
# Question
Title: Language Decidability
What is the easiest and the most straightforward way to find whether a given language is decidable?

For example, how do we know if the following languages are decidable or not?

```
`Binary representation of all prime numbers`
`{ empty string(eps) }`

```

# Answer
> 1 votes
A language $L$ is decidable if there is an algorithm that halts on every input, says Yes if the input belongs to $L$, and says No if the input doesn't belong to $L$.

The language of all binary representations of prime numbers is decidable since there is an algorithm that decides whether an integer is prime. You can probably code such an algorithm yourself in your favorite programming language. There are a few added complications - you need to parse the input, and you need to handle arbitrarily large integers - but intuitively these are not hard to address.

Similarly, the language consisting of only the empty string is decidable, since an algorithm can examine the string and check whether it is empty or not.

The real challenge is proving that some problem *ins't* decidable. The main techniques are are *diagonalization* and *reduction*. Roughly speaking, proofs by diagonalization construct an input that every potential algorithm fails to address, using some kind of self-reference. A good example is the halting problem, much information on which is available online. Proofs by reduction show that if you could decide your problem X then you would be able to decide some other problem Y which is already known to be undecidable.

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: Why do I get really different results with my benchmarking code I made?
I'm doing research work for my last year in high school. My work is about processors and for the experimental part i've coded an app that can mesure how many Floating Point Operation can a processor do in one second. My problem is that i get really different results depending when I execute my benchmark, I can get 5,6 GFlops and then 5 seconds later I can get 1,6 GFlops. How is this possible? Isn't measuring a processor aproximate speed with how many floating point operations per second can do useful? If not, what ways are useful to get an aproximate result of how fast is a CPU.

# Answer
While benchmarking metal is mostly outside of the realms of computer science -- we usually don't want to worry about issues of materials and physics -- there are some general remarks here.

Tl;dr: benchmarks are inherently fickle.

1. Your benchmark process is not alone on the machine. Other processes and interrupts can cause your process to be stalled non-deterministically¹.

Therefore, if your benchmark is only a few seconds long (or less?), random events can dominate the measurement. You want to measure for long periods of time (so you get "average noise") on a machine where almost nothing else is running (so there's little noise) and compare with exactly the same system *but* the CPU (so the noise is the same).
2. Flops figures in the literature (or ad leaflets) are often theoretical peak figures. They just look at the CPU construction and say, okay, ideally (no pipeline stalls, no context switches, no memory delay, ...) at this frequency (which a store-bought, flawed chip may not be able to attain) the FP-ALU can compute this many operations per second.

This number is never attained. You can of course try to determine a "real" peak number by running different benchmarks and taking the maximum. Averages probably depend heavily on the benchmark.
3. Flops are only one type of operation. What about all the others?
4. Real computation performance depends on many factors that range from the architecture of the CPU to the design of the program being run on it. One notable example would be the length of the pipeline. All else being equal, a chip with a longer pipeline will outperform one with a shorter pipeline on long chains of operations without any conditional jumps -- and exactly the other way around if there *are* (many) such jumps!
5. > If not, what ways are useful to get an aproximate result of how fast is a CPU.

I am not sure that there is a general measure for "CPU speed". Different CPUs excel at different things. Also, relative measures like "computation power" per Watt become increasingly relevant.

That said, I'm sure books have been written about all these issues. I can't recommend one, but doing some literature research may pay off -- especially at your level, since it'll point you towards many other great things to learn!

---

1. It's not really non-deterministally or random, of course. But when looking at a CPU as a black box, it might as well be.
> 3 votes

---
Tags: computer-architecture, floating-point, benchmarking
---


# Question
Title: Find all substrings that fit the mask with asterisks
There is a problem.

Given string $text$ containing only letters and string $mask$ containing letters and asterisks (\*), where asterisk means substitution of zero or more letters, find all substrings of $text$ that fit $mask$.

There is an example: let's $text=cabccbacbacab$, $mask=\textbf{ab}\*\textbf{ba}\*\textbf{c}$. The algorithm should give substrings $abccbac$, $abccbacbac$, because $abccbac = \textbf{ab} + cc + \textbf{ba} + \textbf{c}$, $abccbacbac = \textbf{ab} + ccbac + \textbf{ba} + \textbf{c}$.

I have tried to split mask into tokens (for above example $\textbf{ab},\textbf{ba},\textbf{c}$) then find all occurrences of every token in $text$ then make cartesian product of all relevant occurrences and check every token for condition.

Is there more efficient solution for this problem?

# Answer
Yes, there is a more efficient algorithm. Your algorithm can take exponential time.

You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the length of mask, and find all matches in $O(n^2m)$ time. I'll show two solutions, one using dynamic programming and one using graph search. You can pick whichever you find easier to understand.

I don't know whether you can do even better.

# Dynamic programming

Build an array $A\[i,j\]$, where $A\[i,j\]$ is true if some prefix of $\text{text}\[i..n\]$ matches $\text{mask}\[j..m\]$. There's a recursive formula for $A\[i,j\]$:

$$\begin{align\*} A\[i,j\] &= \text{True} \qquad &&\text{if } j=m+1\\ A\[i,j\] &= A\[i+1,j+1\] \qquad &&\text{if } \text{mask}\[j\]=\text{text}\[i\]\\ A\[i,j\] &= A\[i,j+1\] \lor \cdots \lor A\[n,j+1\] \qquad &&\text{if } \text{mask}\[j\]=\*\\ A\[i,j\] &= \text{False} \qquad &&\text{otherwise} \end{align\*}$$

If you fill this in, in the usual way, you get a $O(nm^2)$ time algorithm. If you additionally keep track of $B\[i,j\] = A\[i,j+1\] \lor \cdots \lor A\[n,j+1\]$ and fill in entries in the right order, you get a $O(nm)$ time algorithm.

Once you have filled in the matrix, you can find all substrings of text that match: each entry $A\[i,1\]$ that is true corresponds to one or more substrings of text that match (the substring starts at index $i$ of text). You can adapt the above algorithm to enumerate all those matching substrings by repeating the above computation once per possible ending place of the match.

There may be even faster methods, using ideas from string matching and/or regular expression matching.

# Graph search

Build a directed graph on $nm$ vertices. Each vertex is of the form $\langle i,j \rangle$, which we think of as corresponding to the problem of checking whether some prefix of $\text{text}\[i..n\]$ matches $\text{mask}\[j..m\]$. Now add the following edges:

* Add the edge $\langle i,j \rangle \to \langle i+1,j+1 \rangle$ if mask$\[j\]$ = text$\[i\]$.
* Add the edge $\langle i,j \rangle \to \langle i,j' \rangle$ if mask$\[j\] = \*$ and $j' \> j$.

Finally, mark each vertex $\langle i,m+1 \rangle$ as "accepting".

This is a directed acyclic graph; it has no cycles. Now, for each $i$, find all accepting vertices that are reachable by some path starting at the vertex $\langle i,1 \rangle$. If $\langle i',m+1 \rangle$ is reachable from $\langle i,1 \rangle$, that means that the substring text$\[i..i'-1\]$ matches mask, so you can output this substring. This computation can be done in $O(nm)$ time per starting point using breadth-first search, for a total of $O(n^2m)$ time.
> 8 votes

---
Tags: algorithms, strings, substrings, string-matching
---


# Question
Title: What is the most efficient way to compute factorials modulo a prime?
Do you know any algorithm that calculates the factorial after modulus efficiently?

For example, I want to program:

```
for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

```

But, `p` is a big number (prime) for applying factorial directly $(p \leq 10^ 8)$.

In Python, this task is really easy, but i really want to know how to optimize.

# Answer
> 14 votes
*(This answer was initially posted by the asker jonaprieto inside the question.)*

I remember Wilson's theorem, and I noticed little things:

In the above program, it is better if I write: $$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\ (p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\ \ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}} &\pmod p\\ \end{align}$$

And you can find $(p-i)^{-1}$ because $\operatorname{gcd}(p, p-i) = 1$, so with the extended Euclidian algorithm you can find the value of $(p-i)^{-1}$, that is the inverse modulus.

You can view the same congruences too, like to: $$\begin{align\*} (p-5)! &\equiv (p-24)^{-1}&\pmod p\\ (p-4)! &\equiv (p+6)^{-1}&\pmod p\\ (p-3)! &\equiv (p-2)^{-1} &\pmod p\\ (p-2)! &\equiv 1&\pmod p\\ (p-1)! &\equiv -1&\pmod p\\ \end{align\*} $$ so, the sum is equal: $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ and if you factorize in the beginning the factorials you get $$ 8\cdot (-24)^{-1} \pmod p$$ And, voila, inverse modulus is more efficient than factorials.

# Answer
> 2 votes
The example that you are posting is very closely related to Euler problem #381. So I will post an answer that doesn't solve the Euler problem. I will post how you can calculate factorials modulo a prime.

So: How to calculate n! modulo p?

Quick observation: If n ≥ p, then n! has a factor p, so the result is 0. Very quick. And if we ignore the requirement that p should be a prime then let q be the smallest prime factor of p, and n! modulo p is 0 if n ≥ q. There's also not much reason to require that p is a prime to answer your question.

Now in your example (n - i)! for 1 ≤ i ≤ 5 came up. You don't have to calculate five factorials: You calculate (n - 5)!, multiply by (n - 4) go get (n - 4)!, multiply by (n - 3) to get (n - 3)! etc. This reduces the work by almost a factor 5. Don't solve the problem literally.

The question is how to calculate n! modulo m. The obvious way is to calculate n!, a number with roughly n log n decimal digits, and calculate the remainder modulo p. That's hard work. Question: How can we get this result quicker? By not doing the obvious thing.

We know that ((a * b * c) modulo p = (((a * b) modulo p) * c) modulo p.

To calculate n!, we would normally start with x = 1, then multiply x by 1, 2, 3, ... n. Using the modulo formula, we calculate n! modulo p without calculating n!, by starting with x = 1, and then for i = 1, 2, 3, .., n we replace x with (x * i) modulo p.

We always have x \< p and i \< n, so we only need enough precision to calculate x * p, not the much higher precision to calculate n!. So to calculate n! modulo p for p ≥ 2 we take the following steps:

```
Step 1: Find the smallest prime factor q of p. If n ≥ q then the result is 0.
Step 2: Let x = 1, then for 1 ≤ i ≤ n replace x with (x * i) modulo p, and x is the result.

```

(Some answers mention Wilson's theorem, which only answers the question in the very special case of the example given, and is very useful to solve Euler problem #381, but in general isn't useful to solve the question that was asked).

# Answer
> -1 votes
This is my implementation use of the wilson's theorem:

The factMOD function is the one to call to compute (n!) % MOD when MOD-n is little against n.

Do someone know an other efficient approach when it's not the case (e.g: n=1e6 and MOD=1e9+7) ?

```
ll powmod(ll a, ll b){//a^b % MOD
  ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
}
ll InverseEuler(ll n){//modular inverse of n
  return powmod(n,MOD-2);
}
ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
   ll res=1,i;
   for(i=1; i<MOD-n; i++){
     res*=i;
     if(res>=MOD)res%=MOD;
   }
   res=InverseEuler(res);
    if(!(n&1))
      res= -res +MOD;
  }
  return res%MOD;
}

```

---
Tags: algorithms, efficiency, integers
---


# Question
Title: Can Turing machines simulate the unbounded minization operator applied to a partial function?
I am a little bit confused with the unbounded minimization ($\mu$ operator of the $\mu$ recursive functions).

The $\mu$ operator is $\mu(f)(x) = \min(n | f(x, n) \> 0)$ and the operator is said *safe* if we only apply it to functions such that for every $x$, $f(x, n) \> 0$ for some $n$. In that case, every recursive function is total and every such function is computable with a Turing machine. The proof simulates every initial function and every operator with a Turing machine. Particularly, for $\mu$, the machine applies $f(x, n)$ for each $n \in \mathbb{N}$ until $f(x, n)$ is not 0.

This can be done because the operator is safe. The machine halts on every input.

When the operator is not safe, we can create partial functions as $\mu(f)(x)$ may be infinite (and thus undefined). Considering Turing machine, partial functions is not a problem as we can state that the machine does not stop if the input is not defined for the fonction. However, I cannot prove that the unbounded and unsafe minimization operator can be simulated by a Turing machine.

Indeed, if $f$ is partial, we can define $\mu$ as $\mu(f)(x) = \min(n | f(x, n)$ is defined and $f(x, n) \> 0)$. In that case, there may exist $n = \mu(f)(x)$ and $m \< n$ such that $f(x, m)$ is not defined. And, in that case, the machine that was used on the safe case does not halt anymore. Due to the halting problem indecidability, it is not possible to determine if $f(x, n)$ is defined or not.

So, my question is : Are the partial recursive functions (with unsafe operator $\mu$) equivalent to partial functions computable by Turing machines?

# Answer
> 2 votes
Unsafe $\mu$ is strictly stronger than partial TMs.

Indeed, define $f$ such that $f(x,0)=1$ if the $x$-th Turing machine halts on empty input, let $f(x,0)$ be undefined otherwise, and let $f(x,n)=1$ for all $n\>0$. Then $f$ is a computable partial function. Let $g:=\mu(f)$. Then $g(x)=0$ if the $x$-th Turing machine halts and $g(x)=1$ otherwise. Hence $\mu(f)$ is not computable.

\[EDIT\]

The closure of partial recursive functions under unsafe $\mu$ seems to be the arithmetical hierarchy. (In order to make that statement precise, we have to translate between partial functions and subsets of $\mathbb N$.)

# Answer
> 0 votes
No, your definition of $\mu$ makes $\mu f$ not partial recursive, in general, even when we assume that $f$ is partial recursive, as @kne shows above.

If you want a minimization operator such that $\mu f$ is always partial recursive when $f$ is, you can take

$$ \mu f(x) = \min\\{n | f(x, n) \> 0 \mbox{ and $\forall m\<n.\ f(x, m)$ is defined} \\} $$

---
Tags: turing-machines, mu-recursion
---


title: Restriction and re-labeling on CCS

text:
# Question
Title: Restriction and re-labeling on CCS
In a process like $$ R \stackrel{def}=((a.\bar{b}.0)\setminus\\{b\\})\[a\to b\]\mid(\bar{b}.b.0)+\bar{b}.c.0 $$

$b$ is restricted to perform on the inner process of RHS $(a.\bar{b}.0)\setminus\\{b\\}$, thereafter the $a$ is relabeled to $b$. What I am confused is in drawing the LTS of it, the $a$ action occur at first process (we can have a transition with label $a$ in the LTS) and it is the next process that renaming takes place? can the following LTS be valid as first actions transitions? (the bar is replaced by underline)

# Answer
I am not completely sure about what is causing your confusion, but perhaps this can help:

$a.\bar{b}.0$ can only perform $a$.

$(a.\bar{b}.0)\setminus\\{b\\}$ can only perform $a$.

$((a.\bar{b}.0)\setminus\\{b\\})\[a\to b\]$ can only perform $b$ (i.e. $a$ after substitution).

The full process $((a.\bar{b}.0)\setminus\\{b\\})\[a\to b\]\mid(\bar{b}.b.0)+\bar{b}.c.0$ can perform $b$, $\bar b$ (two distinct ways), and $\tau$ (two distinct ways).

Also note that the *unrelated* process $((a.\bar{b}.0)\[a\to b\])\setminus\\{b\\}$ would instead be stuck.
> 2 votes

---
Tags: process-algebras, transition-systems, ccs
---


# Question
Title: Theoretical speed gain of quad core vs. single core
I first asked this question at cstheory, but they suggested to ask my question here, so here it goes ...

I'm working on my masters thesis and I need to have theoretical value of the (average) speed gain that a quadcore processor brings compared to a singlecore processor, when they both use the same frequency. So for example the speed gain of a 2 GHz singlecore vs. 2 Ghz quadcore.

Somewhere on the internet I've read that a quadcore is 2.6 times faster than singlecore, but the author didn't mention any source so I cannot use that in my thesis.

I've been trying to calculate some things myself, but didn't come to a conclusion. I tried like this:

```
threads | quad core | single core | ratio
--------|-----------|-------------|-------
1       | 1         | 1           | 1
2       | 2         | 1/2         | 4
3       | 3         | 1/3         | 9
4       | 4         | 1/4         | 16
5       | 3+1/2     | 1/5         | 17.5
6       | 2+2(1/2)  | 1/5         | 15
7       | 1+3(1/2)  | 1/5         | 12.5
...

```

This table represents the timeslices available to execute a task (I've taken a fair 50/50 usage for each thread). For example when using a singlecore and a application uses 3 threads, each thread can work 1/3 of the time, while with a quadcore each thread can work 100% of the time, because 3 threads can be spread accross a separate core. After playing with some calculations in Excel, I could not come to any conclusion.

I'm a bit stuck and need some fresh ideas on how to get a theoretical number that represents how much faster a quad core is (on average) compared to a single core. Maybe some of you know some empirical numbers with a good reference to the source? Anyway, all the help is welcome, because I'm a bit stuck and this is the last part I need to cover in my thesis.

Thanks!

# Answer
There is no absolute value of how much faster a quad-core would be compared to a single-core. As the comments have said, it very much depends on exactly what you are doing whether it will be faster or slower. Even live performance testing may not give a fair answer since it won't model exact runtime behaviour.

In any case, if you are looking for a theoretical model it certainly is possible, though, as you can quickly see, not practically possible.

First you need to understand the architecure of the chips of the involved. When you move from single-core to quad-core not all resources are actually quadrupled. In particular the memory is still a shared resource. This memory is then split between a series of caches, some of which are shared, and some of which are not shared. Each cache is connected to the other caches either by a dedicated bus, or a shared data bus. Each of these caches, and buses, has a real bandwidth and latency number. This is not likely published, but with some very focused tests can be obtained.

Second you need to understand how the application will be using memory. How this memory is shared and the order in which it is accessed. For a single thread you could, in theory, calculate the amount of time it spends loading data from the various cache levels. For a multi-core case a key value is how often you attempt to write to the same memory. In this case you will invoke the chips cache-coherency algorithm. This algorithm is usually documented (to some degree) and the time to synchronize can be reasonably well measured.

Combine these together and you'll see that with perfect knowledge of how the program behaves and how the processor behaves you would be able to calculate the theoretical gains of increasing the number of cores. In pratice this simply won't be possible for all but the simplest of programs (but even then the way the chips manage memory is complex enough to make the problem too difficult).

What you should get from this description is primarily that processor speed alone is not the only problem. Memory is often the key bottleneck. When svick says *perfectly parallelized* he means they don't share memory. In this case your threads will approach the maximum 4x speed gain as the memory contention is low. However, they still share some memory cache for reading (L3 and main memory on Intel) and thus could still be limited by the total memory bandwidth.

If you wish to look at a degenerate example lookup "false sharing". In such cases the total speed goes down as more processors are added.
> 6 votes

# Answer
In addition to the other answer: Today, the speed of a processor is to a large degree limited by *heat*. Processing produces heat, too much heat would destroy the processor or dramatically shorten its life, so when the processor gets close to being too hot, it's speed is slowed down so that it produces less heat.

For example, one curent Intel processor can be purchased with 4, 8, 10, 14, or 18 cores. The official clock speed is 4.3, 3.6, 3.3, 3.1 and 2.6 GHz. Because 18 cores produce more heat than 4, the clock speed must be reduced (if the 18 core processor only uses 4 cores, at can run at the same speed as the 4 core processor). Using a single core only, the processor can run at an even higher speed.

There is the consideration whether the code is aware of running on multiple processors or not. Lots of performance critical code is written to be aware of what caches are available. For example, if there is 2 MB of cache, you would try to cut up the work into chunks of 2 MB at a time. But if there are four threads on four CPUs, you may have only 0.5 MB per CPU, which may reduce performance somewhat if the code is aware of it, and may reduce performance dramatically if the code is not aware, and four cores try to access 8MB.

(In a comment, Raphael correctly suggested that you can gain more speed by sheer luck. If the code isn't aware of caches, but splits the work into four parts so that every core can do some work, it may happen by sheer luck that the code is now more cache friendly and runs more than four times faster).

There is the question which resources are duplicated. There are processors which are optimised for integer performance, and a floating-point or especially vector unit may be shared between cores. In that case, your gain will be a lot less if your code uses the resources that are not duplicated. (On such a processor, integer code would get the expected speedup).
> 1 votes

---
Tags: computer-architecture, performance
---


title: terminology: half adders, full adders

text:
# Question
Title: terminology: half adders, full adders
I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders'

I've read before that 'half adders' are called so, because two of them make up a 'full adder', and a 'full adder' is 'full' because you can get all the values $(0,0), (0,1), (1,0), (1,1)$.

But what irks me is that adding two bits would never get you $(1,1)$ in the first place, so why not call it a 2-bit adder, since that's exactly what it does. By extension, a 'full adder', in my mind, should be called a 3-bit adder.

If i think of full adders as '3 bit adders', would I ever run into any conceptual troubles? Same goes with '2 bit adders' and half-adders. Are there any historical insights as to why they are called such?

Cheers.

# Answer
> 1 votes
A "half adder" only does half the job: It adds two inputs x and y.

A "full adder" does the full job: Most of the time, you need to process two inputs, plus a carry from another (half or full adder). A "full adder" adds three inputs x, y and z.

You will also find the terms 2-2 or 3-2 adders: A 3-2 adder adds 3 input bits with value 1 each, and produces two output bits with values 1 and 2. In practice you may see a 7-3 adder which takes seven inputs and produces 3 output bits with values 1, 2 and 4.

---
Tags: terminology, circuits
---


# Question
Title: UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?
I have a struct like this:

```
struct UInt128 {
    UInt64 s1;
    UInt64 s2;
}

```

In this struct, `s1` represents the highest 64-bits of my 128 bit integer, and `s2` represents the lowest 64-bits of my 128 bit integer.

I'm attempting to implement a method that produces the product of two `UInt128`'s.

My current thought process is that the solution is similar to FOIL, the technique used to expand brackets in algebra e.g. $(a+b)(c+d)$ where we give the result as $ac + ad + bc + ad$, but my issue comes from the fact that I don't understand how to break the result back into two `UInt64`'s.

How can I compute the product of two `UInt128`'s as defined by the struct above?

# Answer
It depends what operations are available to you for 64 bit integers.

The product of two 64 bit integers is a 128 bit integer. Many programming languages don't provide such a product, for example in C you will likely have an operation that produces the 64 bit (x * y) modulo $2^{64}$, but not an operation that produces the 128 bit number x * y.

On the other hand, given two 64 bit numbers x, y, many processors have instructions that produce 64 bit integers a and b such that mathematically x * y = a * $2^{64}$ + b.

If such an operation is available to you, you would calculate the 128 bit product x.s2 * y.s2, and the two 64 bit products x.s1 * y.s2 and x.s2 * y.s1 and use these to calculate the 128 bit product. If you want a 256 bit product, then you need to calculate four 128 bit products.

If you have no easy means to calculate the 128 bit product of two 64 bit numbers, then hopefully you can calculate the 64 bit product of two 32 bit integers, so you can use the same operations with half the number of bits.
> 1 votes

# Answer
The numbers are $s1\times f+s2$ where $f = 2^{64}$

This means that the product is:

$(a\times f+b)(c\times f+d) = ac\times f^2+(ad+bc)\times f+bd$

So if you don't mind dropping all the overflowing high bits then all you need to do is split up $bd$ into 2 64 bit parts using divide and remainder (or shift and mask because $f$ is a power of 2) and you'll get the result:

$$( (ad+bc \mod f )+\lfloor \frac{bd}{f}\rfloor)f+(bd \mod f)$$
> 0 votes

---
Tags: algorithms, numerical-algorithms, bit-manipulation
---


# Question
Title: Size of address spaces (logical and physical)
Suppose a system in which addresses (physical and logical) occupy 32 bits, page size is 1024 bytes (210), and physical memory is of size 32MB. How many frames are in physical memory? Is the logical address space larger than physical memory? Explain.

The solution given is:

232 byte logical address space (assuming byte-addressable machine)

225 byte physical memory

210 byte pages

At one page per frame, there are 225/210 = 215 pages in physical memory. The logical memory address space is larger than physical memory.

Can someone explain how to arrive at this solution?

# Answer
> 5 votes
The size of a frame is the same as that of a page, so the size of a frame is 1024 bytes (210 bytes).

If the physical memory is 32MB (225 bytes), the number of frames is 225 / 210 = 215 and this is also the maximum number of pages that can be present in memory at the same time.

The logical address space is larger than the physical address space, a process can address 232 memory locations that is 232 / 210 = 222 pages.

# Answer
> 4 votes
Since the page size is 2^10 , in the virtual address, 10 bits are allocated as offset bits. Since it has 32 bits total, the remaining 22 bits represents the Frame number. So there are 2^22 logical address frames.

The physical memory is 2^25 bytes and the frame size is 2^10 bytes. So the number of frames in the physical address space is (2^25)/(2^10) = 2^15.

Each process has its own logical address space. That may be smaller than the physical address space. But at a given time there are more than one process running. So altogether the logical address space exceeds the physical address space.

---
Tags: operating-systems, memory-management
---


# Question
Title: Write a grammar for a language $L=\{ba^{2^n}b |n\ge 1\}$
Write a grammar for a language $$L=\\{ba^{2^n}b | n\ge 1\\}.$$ It's not even context-free as I think. I just can't produce it, although I've tried a lot. Now my best attempt is: \begin{aligned} S &\to RLM \\ M &\to AM | A \\ LA &\to aa \\ aA &\to Aaa \\ RA &\to \varepsilon \end{aligned} But I've found example with deadlock $S→RLM→RLAAA→RaaAA→RaAaaA→RAaaaaA→aaaaA$

# Answer
> 2 votes
When designing a grammar you must have some idea what the productions are meant to do. You seem to have some good productions, but glued tegether in a unexplained way. What is $M$ doing in your grammar? It might generate any number of $a$'s if I am not mistaken.

The basic idea when generating stings of the form $a^{2^n}$ is indeed to have a symbol that moves over the string that duplicates every $a$. So

$aA \to Aaa$

is good as a basis for the grammar. Now add a starting production, that gives end-markers, which can be made to disappear and turn into $b$'s.

$S \to LaaR$

Now you finish. Make the $A$ appear so that it can move over the string to double the number of $a$'s, to get $La^4R$ etcetera.

Don't worry about "deadlock". That is sometimes hard to avoid if the grammar is not completely "synchronized". For instance if one side of the string wants to finish the derivation process, and the other side doesn't. Those derivations are discarded. What matters is that the strings that do have proper derivations are exactly those in $L$.

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


# Question
Title: How to solve this very complicated assignment problem
A set of m items need to be placed into n stacks, where m \> n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends only on the position within the stack but not on which stack it is placed in. The width of a stack is the maximum of the widths of z items placed in it. The objective is to place the items in the stacks so that the sum of the widths of the stacks is minimum. No position in the stacks could be left unassigned. That means we have to choose z x n items out of m items to be placed in the stacks.

I tried to map this problem to different types of assignment problem but could not find one that exactly matches the constraints and objectives. What would be a good approach to solve this problem?

**Edited based on D.W. s comment:** I am looking for a practical solution. The number of stacks n is not large..it would be around 10. The number of positions within a stack, z is at most 36, but 9 is the most frequent number of positions. The number of items m on average is around 100-200. The widths are NOT integers, but floating point values (precision of 0.01 is good enough). I have not tried the integer linear programming approach...I need a very fast solution that can work for online calculation of some scheduling in an embedded system.

# Answer
I don't see a way to solve this using standard algorithms for the assignment problem.

If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP). You can introduce zero-or-one variables $x\_{i,j,k}$, where $x\_{i,j,k}=1$ means that item $i$ is placed in stack $j$ position $k$, and continuous variables $w\_j$, where $w\_j$ represents the width of stack $j$.

It's then not too hard to write down linear inequalities that capture all your requirements. For instance, we have $\sum\_{j,k} x\_{i,j,k} = 1$ (each item is placed in one location) and $\sum\_i x\_{i,j,k} = 1$ (two items can't be placed in the same location; every position must be full) and $c\_{i,k} - w\_j \le M (1-x\_{i,j,k})$ where $c\_{i,k}$ is the width of item $i$ if placed in position $k$ and $M$ is a sufficiently large constant (this ensures that the $w$'s represent the stack widths correctly). Then, you can minimize $\sum\_j w\_j$ with an off-the-shelf ILP solver.

I don't know how efficient it will be, or whether it will be adequate for online realtime calculation, but I suggest you give it a try and find out.

If it is too slow, there are some options. One option is that some ILP solvers come with a way to impose a time limit; the solver tries to find the best solution it can within the time limit, with no guarantee that it will find the optimal solution. Another option would be to try to craft some heuristic that doesn't necessarily yield the optimal solution, but is fast; maybe a greedy algorithm or something. For instance, here is an off-the-cuff idea. Associate with each item the smallest possible width it could have, among all the possible places it can be placed (out of the positions that remain open). Pick the item with the largest associated value, and place it in the position that minimizes its width. Update the associated values for all items, and repeat. No guarantees about the quality of the solution, but this will be fast. One could also use the smallest amount that it increases the total cost of the solution, out of all possible placements, rather than the smallest width, as the value associated with a particular item.
> 2 votes

# Answer
In the single-stack case, you can find an exact solution using a kind of binary search on the minimum stack width, in which an assignment problem is solved at each step of the binary search. Although this doesn't directly yield an optimal solution for the multi-stack case, it can be used as a subroutine for solving it heuristically: e.g., after randomly or heuristically partitioning the objects into stacks in a first step, each stack can be optimised independently; repeating this with many random partitions should give a good-quality solution.

## Solving the single-stack case optimally

Because the cost is determined by the *maximum* width of any object contained in the stack, we have to work around the "true nature" of the assignment problem, which is to minimise (or maximise) a *sum* of costs. Instead of directly searching for the optimum width, we can choose a particular test width $w$, and then see if we can fit $z$ objects in the stack such that none of the objects exceeds this test width. This can be accomplished by creating $m$ "agent" vertices $u\_1, \dots, u\_m$ and $z$ "job" vertices $v\_1, \dots, v\_z$, and an edge of weight 1 for each pair $(u\_i, v\_j)$ such that the width of item $i$, when placed in slot $j$, is at most $w$. We then solve the resulting assignment problem, looking to maximise the total score. **If and only if the solution has score exactly equal to $z$, then there is a selection of $z$ items that can be arranged in the stack so that no item has width exceeding $w$.** The edges in the solution describe exactly which items go to which slots. Call such an instance *solvable*; an instance which produces a lower score is *unsolvable*.

With that step in place, it should be clear that we can find the smallest achievable width $w^\*$ in $O(\log w^\*)$ steps by binary-searching on $w$: Whenever the problem turns out to be solvable, we try a smaller value of $w$, while whenever it is not, we try a larger value. (To initially find a range of widths containing the minimum, start out with $w=1$, and keep doubling $w$ until we get a solvable assignment problem instance.)

## A different heuristic

If we constrain the problem so that we use the same width threshold $w$ for each of the $n$ stacks, this problem can be optimally solved using the same technique: Just make $n$ copies of each of the "job" vertices, and replace the score threshold $z$ with $nz$, then proceed as before. Unfortunately this could miss optimal solutions to the original (less constrained) problem in which we allow some stacks to get very wide but keep others narrow -- but it could perhaps be useful in finding "difficult" items (items that remain unassigned when the test width $w \< w^\*$), so that extra effort can be focussed on dealing with them.
> 1 votes

---
Tags: algorithms, knapsack-problems, assignment-problem
---


# Question
Title: O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?
I need to build a TM with exactly 1 tape for the language L = {w| w is a word with same number of a's and b's in it, for example: abba, aababb}

The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).

If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...

Help ? any ideas ?

# Answer
The idea is to repeatedly apply the following algorithm:

1. Determine the parity of the number of $a$'s, deleting every second $a$ on the way.
2. Determine the parity of the number of $b$'s, deleting every second $b$ on the way.
3. Accept if there were no $a$'s or $b$'s.
4. Reject if the parities are different.
5. Jump back to Step 1.

Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.

As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.
> 5 votes

---
Tags: algorithms, turing-machines, time-complexity
---


# Question
Title: Is a perfect matching's weight less than MST of a metric graph?
This is part of a bigger proof I'm trying to solve, which eventually came down to one thing:

Let $G=(V,E)$ an un-directed, complete, **metric** graph (maintains the triangle inequality) with an even number of vertices. Let $PM$ denote a *minimum-weight*-perfect matching on $E$ and let $MST$ denote a minimum-spanning-tree of $G$.

Is it true that $w(PM) \leq w(MST)$ ?

I'm not sure if the fact that the graph is metric is useful, but I have pointed that out any way.

I know $PM$ and $MST$ do not necessarily share all edges, but maybe some of them? I was trying and couldn't find a counter-example to disprove this.

My gut says it's true, but I cannot find a definitive way to prove it.

# Answer
> 2 votes
Given any spanning tree, here is how to construct a perfect matching with weight no larger. We consider two cases.

**Case 1.** The tree has some leaf $\ell$ which is an only child of its "parent" $x$. In this case we add $(\ell,x)$ to the matching, delete the vertices $\ell,x$, and continue.

**Case 2.** The tree has some leaf $\ell\_1$ which has a sibling $\ell\_2$. Let the common "parent" be $x$. The triangle inequality shows that $w(\ell\_1,\ell\_2) \leq w(\ell\_1,x) + w(\ell\_2,x)$. Accordingly, we add $(\ell\_1,\ell\_2)$ to the matching, delete the vertices $\ell\_1,\ell\_2$, and continue.

At each point in time, the remaining graph is always a tree, and the removed vertices are covered by a matching. Furthermore, the cost of the matching is always at most the cost of the edges removed from the tree. Eventually all the vertices will be exhausted, and we will be left with a perfect matching whose cost is at most the cost of the tree.

---
Tags: graphs, matching, minimum-spanning-tree
---


# Question
Title: clustering with uncertain number of clusters
I detect a unmanned aerial vehicle(UAV) in a picture using template matching. The template library only contains targets with different scales, rotations and other differences.I want to simplify the template library using clustering. I learned the k-means and Gaussian mixture model（GMM）but they all need determine the value of k.Are there any approaches which can solve my problem?

# Answer
> 3 votes
Several algorithms allow doing this. First one is the hierarchical clustering. When creating your dendrogram, the key is to cut the "longest branches." DBSCAN is also a good alternative. Finally, you can use K-means or GMM and optimize your number of cluster against a metrics (see sklearn pages on the subject) (be aware of overfitting)

---
Tags: clustering
---