# Question
Title: Given regular expression construct regex for the complement language
**Disclamer:** this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple. Hints are appreciated (as opposed to direct answers).

> Write an algorithm which accepts a regular expression $r$ and produces a language $\overline{L\[r\]}$.

I think it is reasonable to assume that all operations I need to consider are just the concatenation, union and Kleene star. For simplicity, I assumed the alphabet to be $\\{a,b,c\\}$. I also think that I can invert individual operations as follows:

1. $a^\* \to (a^\*(b+c))^+$.
2. $(a+b) \to (\epsilon+(c(a+b+c)^\*))$.
3. $ab \to \epsilon+((aa+b+c)(a+b+c)^\*)$.

But attempting to combine these operations produces wrong results, for example:

$$ a^\*b^\* \to \\ (a^\*(b+c))^+(b^\*(a+c))^+ \to \\ (\epsilon+((a^\*(b+c))^+(a^\*(b+c))^++b+c)(a+b+c)^\*)(\epsilon+((b^\*(a+c))^++a+c)(a+b+c)^\*)) $$

doesn't seem to do what I expect it to because, for example, it will match the empty string on both sides.

Should I perhaps consider transforming the regexp into DFA and "inverting" the DFA instead?

# Answer
The problem with your attempt is that you've only looked at what happens when the regexp to transform is a simple one. For example, you've looked at what the complement of $a^\*$ looks at. But in order to write a compositional complementation algorithm, you need to figure out how to compute a regular expression that recognizes the complement of the language of $r^\*$, for an arbitrary regular expression $r$.

The bad news is that your approach to build a complement for $a^\*$ does not generalize easily. Consider for example the regular expression $(a + b + c)$. A regular expression that recognizes its complement language is $\epsilon + (a + b + c) (a + b + c) (a + b + c)^\*$ — but this isn't really useful to know if you're looking for the complement of $(a + b + c)^\*$, which is the empty language. You can't reach the complement of $(a+b+c)^\*$ from starring something related to the complement of $(a+b+c)$.

You can approach this problem by adding a complement operator to regular expressions, in which case the algorithm you're looking for is an algorithm to remove the complement operator from such generalized regular expressions. It turns out that this brings you close to an open problem, the generalized star height problem: it's unknown whether you can eliminate nested stars in such generalized regular expressions, which shows that the interaction between the star operator and the complement operator is poorly understood.

Your idea of transforming the regular expression into a DFA and back is a good one. It's perfectly reasonable a different representation of an object where the operation you're interested in is easier. In fact, this *is* the usual algorithm to find a regular expression for the complement language of a regular expression:

1. Build a DFA that recognizes the language of the regular expression.
2. Transform the DFA into one that recognizes the complement language.
3. Build a regular expression whose language is that of the second DFA.

> Step 2 is very easy: just swap accepting and non-accepting states. Note that this doesn't work on an NFA!
> 5 votes

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


# Question
Title: Algorithm to add sum of every possible xor-sum sub-array
I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

**Problem Statement**

XOR-sum of a sub-array is to XOR all the numbers of that sub-array. An array is given to you, you have to add all possible such XOR-sub-array.

**Example**

**Input**

Array :- 1 2

**Output** :- 6

**Explanation**

F(1, 1) = A\[1\] = 1, F(2, 2) = A\[2\] = 2 and F(1, 2) = A\[1\] XOR A\[2\] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

```
for (int i=0, p=1; i<30; i++, p<<=1) {
    int c=0;
    for (int j=0; j<=N; j++) {
        if (A[j]&p) c++;
    }
    ret+=(long long)c*(N-c+1)*p;
}

```

In pseudocode:

* Set $r = 0$
* For $i$ from $0$ to $29$, let $p = 2^i$.
    + Set $c=0$
    + Iterate over the array $A$. For each element $A\[j\]$:
        - If $A\[j\] \mathbin\\& p \ne 0$ then increment $c$. ($\\&$ is bitwise and.)
    + Add $c \times (N-c+1) \times p$ to $r$

# Answer
After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A\[j\]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A\[i-1\]$ is $1$ and the same bit in $A\[j\]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A\[i-1\]$ and $1$ for $A\[j\]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k\[i-1\],A^k\[j\])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.
> 4 votes

# Answer
Just do the OR operations of all numbers and multiply the answer with power(2,N-1) where N is the length of your array.
For array given in question: 1 OR 2 = 3 Now, 3\*(power(2,(2-1))) = 6 which is the answer.
The point here is that, Each set bit of any number occurs exactly in power(2,N-1) sub arrays.
> -1 votes

---
Tags: algorithms, efficiency
---


# Question
Title: Looking for an algorithm to iterate over essentially different solutions
I'll explain my problem with an analogy to Sudoku-grids.

Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However the new grid is essentially equivalent, if that makes sense. One might say, under the operations "swap rows", "exchange labels" etc., both grids are in the same orbit. (https://en.wikipedia.org/wiki/Mathematics\_of\_Sudoku#Enumerating\_essentially\_different\_Sudoku\_solutions)

I want to iterate over all grids, but in a way that the algorithm ignores other solutions in the same orbit. However, this question is not about Sudoku grids! My grids have a different structure, which is a bit simpler:

I want to fill a 4x6 table with the integers 1 to 8 (each three times) such that each row contains each integer at most once. There are a few other more complex conditions, but I think it's easier to check them later after a solution has been generated.

Just like in the Sudoku analogy, there are a few operations that generate other essentially equivalent solutions:

1) Rearranging rows: if one row is

```
1 3 5 6 2 8

```

the solution with that row replaced by

```
1 2 3 5 6 8

```

is of course also valid and consindered essentially equivalent.

2) Swapping rows.

3) Exchanging labels.

E.g. these solutions are essentially equivalent

```
1 3 5 6 2 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First row rearranged:
1 2 3 5 6 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First two rows swapped:
4 1 5 7 8 2
1 3 5 6 2 8
4 7 6 1 2 3
3 4 5 6 8 7

All 1's and 2's exchanged
2 3 5 6 1 8
4 2 5 7 8 1
4 7 6 2 1 3
3 4 5 6 8 7

```

My question is what an efficient (both runtime and memory) algorithm to generate these solutions might be.

The naive approach would be to store all previous solutions and check whether an equivalent solution has already been found. However, this is expensive in both runtime and memory!

I managed to improve this by calculating a hash of each solution in such a way that equivalent solutions generate the same hash. Then we can store the solutions in a map, so that we need to check fewer solutions and thus reduce the runtime. However, the memory cost is still huge.

If the hash has the property that different solutions yield different hashes, then I would only need to store the hashes and reduce the required memory by a large factor.

Can you think of a more elegant algorithm that does not store hashes nor previous solutions?

EDIT:

I simplified my problem too much without realising that I reduced the number of orbits to 1. (Thanks @Klaus Draeger). In fact the numbers 4,6,8 and 3 were made up as an example. I thought I could adapt the algorithm to the more general case later. Actually, my problem is a bit more complex: The number of rows is variable and rows need not have the same length, so rule 2) only applies to rows of equal length. Also the frequency of the numbers is not necessarily constant (e.g numbers 1,2,3,4 might appear four times and 5,6,7,8 three times or whatever), so rule 3) only applies to labels with the same frequency.

EDIT2:

And this is the more complex condition, that I thought doesn't matter for now. Maybe I'm wrong again...

If, in one row, y appears directly to the right of x (or y is in the first column and x in the last), then in a (unique) different row there must be an x to the right of y (above example does not satisfy this). This means that rule 1) only applies to rotations of rows and not any permutation.

I think this can be dealt with at a later point.

# Answer
All solutions are equivalent modulo the equivalence you have given.

Suppose $(a\_{i,j})\_{1\le i\le 4,1\le j\le 6}$ is some solution. Each row misses two labels, and these pairs of labels form a partition of $\\{1,\dots,8\\}$ (otherwise some label would occur too often). But then we can choose an exchange of labels modulo which row $1$ misses $7,8$; row $2$ misses $5,6$; row $3$ misses $3,4$; and row $4$ misses $1,2$.

Each row can then be reordered to arrive at the solution

$A=\begin{pmatrix}1&2&3&4&5&6\\1&2&3&4&7&8\\1&2&5&6&7&8\\3&4&5&6&7&8\end{pmatrix}$

Since every solution is equivalent to $A$, by transitivity, they are all equivalent.
> 1 votes

---
Tags: algorithms, matrices, enumeration
---


# Question
Title: What if block sizes are not equal among caches?
In all the books, packets of slides and similar I read, cache miss is always explained by assuming that blocks of different caches (or cache and RAM) are always of the same size. It's pretty clear how it's works in this case but the question is: what if block dimensions are not equal among caches?

For example, assuming a L1 cache of 8KB and 16B blocks (that implies 2^9 blocks) and a L2 cache of 512KB with 32B block (that implies 2^14 blocks). Assuming that a load have to be executed, i.e. LD R1,(0x0000AFAF) and suppose that there is a cache L1 miss and a cache L2 hit, what happens? What I mean is that i know that a block containing that addressed byte would be stored in L1 cache and i know where. The problem is what i have to save. I mean, have i to save half block of L2 cache (from 0x0000AFA0 to 0x0000AFAF) in a block of L1 cache or have i to save a block of L2 cache (from 0x0000AFA0 to 0x0000AFBf) in two block of L1 cache? Would be the same if i had cache + RAM instead?

# Answer
To begin with, block sizes are usually equal across all levels of the cache hierarchy. I would like to see if someone has an example of a commercial architecture where is is not true. There are multiple reasons for this, all of which involve circuit complexity

Now, to answer your question, one could do either. When the processor requests a SP float (4 bytes), only 4 of the 16 (in your example) bytes from the block of the L1 are sent towards the pipeline. The same logic that selects this subset of bytes can be used to select the subset of 16 bytes (in your example) from the incoming block of 32 bytes.

Alternatively, you could over-write the neighboring block in L1 with data from the block of 32 bytes because spatial locality would imply you are likely to require this data soon.
> 2 votes

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


# Question
Title: The time complexity of finding the diameter of a graph
> What is the time complexity of finding the diameter of a graph $G=(V,E)$?
>
> * ${O}(|V|^2)$
> * ${O}(|V|^2+|V| \cdot |E|)$
> * ${O}(|V|^2\cdot |E|)$
> * ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

# Answer
### Update:

**This solution is not correct.**

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

---

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is *not* directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference *or* to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.
> 8 votes

# Answer
I assume you mean the *diameter* of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.
> 34 votes

# Answer
You can also consider an algebraic graph theoretic approach. The diameter $\text{diam}(G)$ is the least integer $t$ s.t. the matrix $M=I+A$ has the property that all entries of $M^t$ are nonzero. You can find $t$ by $O(\log n)$ iterations of matrix multiplication. The diameter algorithm then requires $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. For example, with the generalization of the Coppersmith-Winograd algorithm by Vassilevska Williams, the diameter algorithm would run in $O(n^{2.3727} \log n)$. For a quick introduction, see Chapter 3 in Fan Chung's book here.

If you restrict your attention to a suitable graph class, you can solve the APSP problem in optimal $O(n^2)$ time. These classes include at least interval graphs, circular arc graphs, permutation graphs, bipartite permutation graphs, strongly chordal graphs, chordal bipartite graphs, distance-hereditary graphs, and dually chordal graphs. For example, see Dragan, F. F. (2005). Estimating all pairs shortest paths in restricted graph families: a unified approach. Journal of Algorithms, 57(1), 1-21 and the references therein.
> 18 votes

# Answer
**Assumptions:
1. Graph is unweighted
2. Graph is directed
**

O(|V||E|) time complexity.

Algorithm:

```
ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

```

Explanation:
We check for cycle. if graph contains cycle then we keep in moving in the loop, so we will be having infinite distance. We check for connected. If graph is not connected that means vertex u from G1 to vertex v in G2. Where G1 and G2 is any two sub graph which are not connected. So we will be having infinite distance again. We will use BFS to compute maximum distance between a given node(u) to all others nodes(v) which are reachable from u. Then we will take maximum of previously computed diameter and the result return by BFS. So we will be having current maximum diameter.

Running time analyzing:

1. O(|E|) using DFS
2. O(|E|) using DFS
3. BFS runs in O(|E|) time.
4. We have to call BFS function for each vertex so total it will take O(|V||E|) time.

Total time = O(|v||E|) + O(|E|) + O(|E|)
Since |V||E| \> |E|
so we have running time as O(|v||E|).

BFS
DFS

**Note: This not an elegant solution to this problem.**
> -2 votes

---
Tags: algorithms, time-complexity, graphs
---


# Question
Title: NUMBER OF WAYS TO GET XOR OF n NUMBERS TO BE 0
Alice and Bob are playing the game of Nim with $n$ piles of stones (p\[0\], p\[1\], ..., p\[n-1\]). If Alice plays first, she loses if and only if the 'xor sum' (or 'Nim sum') of the piles is zero, i.e. $p\[0\] ⊕ p\[1\] ⊕ ... p\[n-1\] = 0$

Bob can remove some stones in some piles before the game starts, but he must keep at least one pile unchanged. Your task is to count the number of ways Bob can remove the stones to force Alice into losing the game. Since the number can be very large, output the number of ways modulo (% operator) 1000000007. Assume that both players will try to optimize their strategy and try to win the game.

**Input**:

The first line of the input contains an integer $n$ denoting the number of piles. The next line contains a space separated list of number of stones $n$ for each pile p\[0\] p\[1\]... p\[n-1\] respectively.

**Output**:

An integer which is the *number of ways* % 1000000007 Bob can force Alice to lose the game.

**Constraints**:

$3 \leq n \leq 100$

$0 \< p\[i\] \< 10^9$

I thought that we can select the piles to be excluded in $2^{n}$-2 ways and depending upon the xor of these excluded piles, I need to find the number of arrangements such that the xor of included piles (piles which are modified) is odd/even accordingly. This has to be done for every bit to get 0. Moreover I cannot change a bit from 0 to 1 if it is to the right of the MSB/ or if MSB is set to 1. Is this the correct way to think? or is there some other way

# Answer
Hints:

1. each bit of xor result depends on all bits on that position only. So each bit can be processed independently, while ignoring the unchanged constraint.
2. process bits from MSB to LSB, the higher bits impact the range of each lower bit.
3. during the processing of last step, you can easily track whether a pile is changed or not.
4. $O(2^n)$ is too slow when $n=100$, try dynamic programming.
> 1 votes

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


# Question
Title: Regular expression in normal (standard) form
Regular expressions can be reduced to a standard form. A **normal form** is either 0 or a term of the form $$ \sum\_{i \in I} a\_i + \sum\_{j \in J} n^\*\_j + \sum\_{k \in K} a\_k \cdot n^\*\_k + \sum\_{l \in L} n^\*\_l \cdot n^{'}\_l + \sum\_{m \in M} E\_m$$ where $E\_m =1$ for all $m$, where $n\_j, m\_k, n\_l,n\_l'$ are normal forms different from 0 and 1 ,and we have $bounded(n^\*\_j)$ and $bounded(n^\*\_l)$.

This definition is from a 1999 paper by Corradini et al. where completeness is proved.

Is it possible to have some references or examples about it?

# Answer
> 1 votes
You're looking for examples.

I would suggest checking whether some very simple expressions like $a^\*$, $abc$, ... are in normal form or not. This helps getting familiar with the definition. For example, what do $0$ and $1$ mean, and what is "bounded"?

Then you can move to more complex expressions like $a.b^\*$ and $(a^\*b)^\*$, ... When one of these is not in normal form, you can try to give an equivalent expression in normal form. Note that it should be possible to put any expression in normal form using the rules given in the Corradini et al. paper. When reading their completeness proof it is good to have a few examples at hand on which you can check the steps of the transformation method.

You're also looking for references.

You can use Google Scholar to find papers that cite the Corradini paper. You can also search for papers concerned with the nondeterminism in regular expressions since this is one of the motivation of the normal form you're interested in.

Hope this helps.

---
Tags: regular-expressions
---


title: How many words are in this sets?

text:
# Question
Title: How many words are in this sets?
I have problems to determine the size of the following sets in dependancy of the parameters $m, n\>0$: $$M\_{m,n}=\\{a^iwa^{m-i}\mid 0\le i \le m,\\;w\in\\{a,b\\}^n\\}$$ It is easy to see that $|M\_{m,n}|\le (m+1)\cdot 2^n$ since there are $m+1$ possibilities for $i$ and $2^n$ possibilities for $w$. If the sets would take the words $w$ from a disjoint alphabet (e.g. $w\in\\{b,c\\}^n$), then the number of elements would be exactly $(m+1)\cdot 2^n$. But for $w\in\\{a,b\\}^n$ each set $M\_{m,n}$ is ambiguous in the sense that the some words could be obtained from different $i$'s and $w$'s. For example $w=a^n$ leads to the same word $a^{n+m}$ for each $i$. By the way, this example yields $|M\_{m,1}|=m+2$ because there is $1$ element for $w=a $ and $m+1$ elements for $w=b$. Another ambigious example for $n=2$ is $$a^i\\;ab\\;a^{m-i}=a^{i+1}\\;ba\\;a^{m-i-1}$$ for $0\le i \le m-1$, which together with the thoughts for unary $w$'s yields $|M\_{m,2}|=2m+4$.

However, for increasing $n$ it becomes more and more difficult and unfortunately I am not able to generalize my approach. What I am hoping for is that $|M\_{m,n}|$ is still in $\Theta(m\cdot 2^n)$. Any help?

# Answer
> 4 votes
Count instead $$ (a+b)^{n+m} - M\_{m,n} = \sum\_{i+j \< m} a^i b (a+b)^{n+m-2-i-j} b a^j. $$ This leads to $$ \begin{align\*} |M\_{m,n}| &= 2^{n+m} - \sum\_{i+j\<m} 2^{n+m-2-i-j} \\ &= 2^{n+m} - \sum\_{k=0}^{m-1} (k+1) 2^{n+m-2-k} \\ &= 2^{n+m} - 2^{n+m-2} (4-2^{-(m-2)}-m2^{-(m-1)}) \\ &= 2^{n+m} (1 - 1 + 2^{-m} + m2^{-m-1}) \\ &= (m+2) 2^{n-1}. \end{align\*} $$

A more direct method follows the decomposition $$ M\_{m,n} = \sum\_{i=0}^{m-1} a^ib(a+b)^{n-1}a^{m-i} + a^m(a+b)^n. $$ This directly gives $$ |M\_{m,n}| = m 2^{n-1} + 2^n = (m+2) 2^{n-1}. $$

---
Tags: formal-languages, combinatorics, word-combinatorics, finite-sets
---


# Question
Title: How to sample random game input that looks similar to human control?
What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this seems really pointless, the computer managed to beat the game that way.

However in this project, buttons are pressed at random, so the behaviour of the character is very far from what you would expect from a human player. What I would like to do is to be able to produce a series of inputs that 'look like' one produced by a human player.

A good way to do that may be to record a sequence of inputs as played by a human player, use this data in order to produce a Markov Chain.

However I think a human player may exhibit a behaviour that is not easily taken into account by a Markov Chain. For example in order to double jump, it is generally a bad idea to have the second jump right after the first. So a typical sequence of inputs would look something like this (where f=forward and j=jump) f-f-f-j-f-f-f-f-f-f-f-f-f-j-f-f-f

This sequence of inputs may be common when the game is played by a human, but in order to have a Markov Chain produce such a sequence of inputs, it means that the states have to correspond to sequences of inputs of length (at least) 10, hence a huge state diagram.

Is there an alternative to (or a variation of) Markov chains that can take this kind of behaviour into account?

NB: English is my 2nd language so I apologize if this question is poorly worded...

# Answer
> 3 votes
A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many different internal states you need, and then you can learn the model from the data.

If you want to model a bunch of different things inside the hidden state (running/not running, has weapon/doesn't have weapon, ...) you can switch to some kind of recurrent neural net (e.g. LSTM)

# Answer
> 0 votes
A Markov chain is a probabilistic generalization of a DFA. There is also a probabilistic generalization of a pushdown automaton. If you like, you can think of this as a probabilistic context-free grammar, where each production in the grammar has a probability associated with it, and out of all possible productions you choose one according to the probabilities. Such things can potentially model longer-range patterns, and there's work in learning them. I'm not sure they'll actually be useful for your specific goal of mimicing English, though.

---
Tags: randomness, sampling, markov-chains, computer-games
---


title: Regular expression: b|b equal to b?

text:
# Question
Title: Regular expression: b|b equal to b?
I am solving some example exercises in preparation of a Computational Theory examination.

In Exercise 2, I am tasked with building an NFA and DFA of the regular expression: $(b|bba)^\*a$

My question is: Can I simplify $b|bba$ inside the parentheses to $bba$? Are they indeed equivalent or will I be breaking some generality?

I am asking this since it is going to be easier for me to construct the automata after the simplification.

# Answer
Usually, concatenation is assumed to bind stronger than alternative, so you have $b \mid (bba)$, not $(b \mid b)ba$.

Then no, you can't drop "$b\ \mid$" since $b^+a \subseteq \mathcal{L}\bigl((b \mid bba)^\*a\bigr)$ but $b^+a \cap \mathcal{L}\bigl((bba)^\*a\bigr) = \emptyset$.

For what it's worth, $\mathcal{L}(b \mid b) = \\{b \\} = \mathcal{L}(b)$, so that simplification would be valid. More generally, if $\mathcal{L}(r\_1) \subseteq \mathcal{L}(r\_2)$, then $\mathcal{L}(r\_1 \mid r\_2) = \mathcal{L}(r\_2)$.
> 6 votes

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


# Question
Title: What can be concluded from a full application of resolution?
I know that resolution is refutation complete, but what can we conclude if a resolution procedure leads to a situation with no more chance to operate the resolution?

Given a propositional formula which we want to check its satisfiability,

( a + b ) ( ¬a + c )

after one resolution the formula become

( a + b ) ( ¬a + c ) ( b + c )

what can we conclude at this point?

# Answer
> 3 votes
By definition if a proof system is refutation-complete then once you've applied it to the maximum extent and not found a contradiction, you have proven that there are no refutations, i.e. the formula is satisfiable. To find a satisfying assignment, add a unit clause that asserts a value for one of the variables, e.g. $(a)$, and use resolution on the resulting formula. If you find a refutation (produce an empty clause), then replace the asserting clause with its negation e.g. $(\lnot{a})$, otherwise leave the original assertion in the formula. Repeat the procedure with a different variable. Eventually you'll have successfully asserted values for all the variables and found a satisfying assignment.

---
Tags: logic, proof-techniques, first-order-logic
---


title: What does this mean $[X]_1^T$?

text:
# Question
Title: What does this mean $[X]_1^T$?
I found this in information theory paper, P.3883*

the authors states the following

> Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact that one can always convert a cyclic network to its acyclic counterpart by taking into account the time index and the causality of information transmission. Nonetheless, when studying Pair Intersession Network Coding on a cyclic network, one cannot rely on this cyclic-to-acyclic conversion since after conversion, there are T symbols in the $(s\_1, d\_1)$ (resp. $(s\_2,d\_2)$) multicast session and network coding allows complete freedom of mixing the $2T$ symbols $\[X\]\_1^T$ and $\[Y\]\_1^T$.

It looks ambiguity because does it mean that we have input from 1 to T; or Is it field = T and size = 1 (since capacity = 1)? so I hope I find answer here.

Thank you ..

\*for those who doesn't have access go to this site Paper

---

Responsing to D.W. (The following information is for reference about the paper.)

C-C. Wang and N. B. Shroff. Pairwise Intersession Network Coding on Directed Networks. IEEE Tran. on Info. Theo., Vol. 56, No. 8, August 2010.

# Answer
This notation is quite common in EE works: If $S=S\_1S\_2S\_3\cdots$ is a string (of some length), then

$S\_i^j$ is the substring between places $i$ and $j$, that is, $S\_i^j=S\_i\cdots S\_j$.

I didn't looks at the paper, but I guess that $\[X\]$ is a string (of expectations? of $X$ directly? this should be defined in the paper), and they just look at a prefix of length $T$ of that string.
> 3 votes

---
Tags: information-theory, network-flow, notation
---


title: Converge to unknown number with oracle

text:
# Question
Title: Converge to unknown number with oracle
I'm playing a game where I'm trying to estimate an unknown real number $x$.

An oracle exists that will answer the question of "Is a number $y$ greater than or equal to $x$?", to which the oracle will reply either **yes** or **no**. The question may be asked an $t$ number of times.

For example, with an unknown $x=9.5$, the oracle will reply **yes** to $15$ and **no** to $9$.

What's the best approach to estimate $x$? It's okay to assume my first guess $y\_1$ will always be answered with **yes** (so I always have some "best" guess available), but now I'm tasked with getting even closer to $x$ with my second guess $y\_2$, third guess $y\_3$, ..., and last guess $y\_t$.

I'm not necessarily looking for a solution to this problem, but at least the established name for it so I may do some research. Concepts like optimization, numerical analysis, and machine learning come to mind, but they are large, deep fields, and I'm not quite sure where to turn.

My use case for this algorithm is to discover the optimal frequency to send requests to a service which is frequency-capped by an unknown amount. When I send too fast, I get error responses (oracle says **no**), and when I'm below the cap, I get success responses (oracle says **yes**). To keep things focused on the important concept, assume the network has no delay.

# Answer
For the game you describe, take a look at binary search. It will find the answer in logarithmically many queries: the logarithm of the search space. In some cases interpolation search can perform even better.

For the application you mention at the end, take a look at TCP's congestion avoidance algorithm (additive increase, multiplicative decrease), as David Richerby suggests.
> 2 votes

---
Tags: algorithms, optimization, machine-learning, numerical-analysis
---


# Question
Title: Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to "connect" all points
I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, allowing for some minimal deviations.

For example, given the points (0,0)-(50,50)-(100,100), the path can be optimized by only specifying (0,0)-(100,100) which will also cover the center point. In case of (0,0)-(49,49)-(100,100) I still want to allow the same line segment of (0,0)-(100,100), as the distance (e.g. euclidian) from the point to the line is small (by a user defined parameter).

What is the minimum number of line segments needed that satisfies the distance condition and how can the segments be determined. Is there a "good" heuristic which is simpler or more efficient while providing comparable results?

# Answer
> 3 votes
Try polyline simplification.
For heuristics or other simplifications you might want to treat segments as resizeable, but for now objective is not that clear.
Here is demo of RDP.
Try it, merge your answer into question and then explain objective.

There is tradeoff between polyline complexity reduction and number of remaining points. Number of removed points depends on data and $\epsilon$.

If you want to find minimum, you have $N-1$ segments on $N$ points, and exact reduction depends on colinearity of points. Otherwise it is only approximation.

# Answer
> 1 votes
You can use dynamic programming. Define $f(i,k)$ to be the "badness" of the best way to cover points $1..i$ using $k$ line segments. Then you can write down a recurrence relation for $f(i,k)$ in terms of $f(i-1,k-1),\dots,f(1,k-1)$, and then apply dynamic programming.

You'll have to fill in the details, because you haven't provided the particular objective function you specified, but I would expect that this approach will work to find an optimal solution.

# Answer
> 0 votes
Thinking some more about this question, I came up with the following recursive algorithm, which might not produce the minimum, but seems to work very well in practice:

Start by taking the first and last point of the path and treating it as a line segment. Now for each point in between, calculate the distance from this point to the line segment and remember which point has the highest distance. If this distance is smaller than the maximum distance allowed, you are done. Otherwise, split the path at this point by connecting the start and end points to this point and execute the algorithm recursively on the two resulting line segments until all points are within the maximum distance.

I'm happy for better algorithms or thoughts on whether the result is a minimum.

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


title: How is the rule 110 Turing complete?

text:
# Question
Title: How is the rule 110 Turing complete?
I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0).

I've just read they're Turing complete, but I can't even fathom how would you 'program' in 'rule 110'?

# Answer
Universality is a somewhat informal notion. What it roughly means is that for each computable function $f$ there is a "program" $P$ in the model so that "running" $P$ on any input $x$ always "halts", and "outputs" the correct answer. (Note that Turing machines don't make an appearance here: they are just one example of a universal computation model.)

The quoted words are those that need to be defined. For Turing machines:

* A *program* is specified as a list of states, a tape alphabet, an initial state, final states, and transitions.
* *Running* a Turing machine $T$ *on an input $x$* means that we initialize the tape with an encoding of $x$ and run the machine $T$ on this tape according to the usual rules.
* A Turing machine *halts* if it reaches a final state. (There are some variants here.)
* What the Turing machine *outputs* (if it halts) is the contents of the tape.

Rule 110, as a computation model, needs to be defined formally in the same way. A definition is reasonable if one can computably simulate the computation model, in the following sense: there is a computable function $S$ such that for every program $P$ and input $x$ (both encoded as natural numbers), $S(P,x)$ halts iff $P$ halts on $x$, and if $S(p,x)$ halts then its output is identical to the output of $P$ on $x$.

If you're curious as to the particular setup of Rule 110 as a computing system, I suggest you take a look at Matthew Cook's paper which proves the universality of Rule 110 (or rather, of a computing system built around Rule 110).

As for other rules, such as Rule 30 and Rule 90, we don't know that they are not universal. There might be convincing computing systems built around them which is universal, but we are just not aware of any.
> 16 votes

# Answer
From Matthew's proof:

> The approach taken here is not to design a new cellular automaton, but to take the very simplest one that naturally exhibits complex behav- ior, and see if we can find within that complex behavior a way to make it do what we want. We will not concern ourselves directly with the lookup table given above, but instead we will look at the behavior that is naturally exhibited by the action of the automaton over time.

The author first starts by proving that a "tag system" that removes 2 symbols at each step is universal by compiling a 2-state turing machine program. After that, he proves that a glider system can indeed implement a tag system. It is a step by step process. Then, he studies the space time of CA-110 to find the gliders and asociate them to the glider system correctly.

Now, for your question: *how would you 'program' in 'rule 110'?*

1. Look for the simplest 2-state turing machine and find the tapes of the basic operations **OR,AND,XOR,NOT**.
2. Compile them to the tag system.
3. Compile the tag-system's implementation into the glider implementation.
4. Adapt it to the CA-110 gliders correctly and you have the basic operations in a cellular automata.

Steps 1 to 4 are performed only once. From there, computing $1+1=2$ reduces to sum numbers using logic gates.

A note aside. Gliders are very special structures. The operations will be seen as particles moving and colliding (the gliders), generating different output depending on how this gliders start from or collide.
> 12 votes

---
Tags: computability, automata, turing-completeness, cellular-automata
---


# Question
Title: Viewing images that compressed using lossless algorithms
I am just trying to understand a few minor details regarding images that are compressed with lossless algorithms such as RLE.

If a bmp image is compressed using RLE, when does the decompression occur when viewing the image? does the image viewer have a built-in library to decompress the image and then view it? or is it using a system library? Is the decompressed image file stored in the RAM temporarily?

Do you any references for this process?

# Answer
Image is decompressed before viewing for the most time.
It is not necessary to decompress it fully if this is very big image and you have preview of the top left cropped area - only needed rows could be decompressed up to visible part.
This is highly implementation dependent, some programs use system built-ins (Windows format BMP) some disregard this and use own (on other systems Windows BMP is not generally built-in).
It may be stored in RAM, on disk, translated to internal format. There is no reason to stick with one scheme.

There are no references as this is implementation specific.
But I can share with my own scheme: I always unpack compressed data, never depend on external libraries, store it on internal format and since I use it in image editor - I store in RAM last three operations used on images.
They can be huge (800k x 600k) so if that is the case I put only visible part to RAM.
Since BMP can come in up side down format and other compress techniques prevent me from mapping coordinates to file, I explicitly store them as small sized decompressed grid (something like Google Maps do).
> 2 votes

---
Tags: image-processing, data-compression, encoding-scheme
---


# Question
Title: Do recursive algorithms generally perform better than their for-loop counterpart?
I'm sure this is not a challenge for you but it remains an open question for me:

**Is it wise to prefer a recursive algorithm over its for-loop counterpart?**

E.g. take the evaluation of the natural logarithm of a number $N + 1$

$$ \ln (N+1) = \ln N + \Delta N, $$

where

$$ \Delta N = 2 \sum\_{k=0}^{\infty} \frac{1}{(2k+1)(2N+1)^{2k+1}}. $$

While one could implement it as a recursive function with an appropriate terminating condition (e.g. relative error tolerance), you could as well put it in a for-loop and break when desired.

# Answer
> 2 votes
I don't think recursive OR for-loop are related to the abstract idea of an algorithm, rather both are a specific strategy to implement an algorithm on a computing system. So your question is basically about which implementation strategy is better for algorithm - recursive or loop based.

The answer (assuming you want to implement the algorithm on general purpose of the shelf CPU) would be for-loop perform better as the recursive call would include the overhead of call stack which will grow for each recursive call.

# Answer
> 5 votes
The answer will depend on the compiler. As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code." In particular, good compilers will do tail-call elimination. In some cases this can effectively transform the code into a for-loop. Your example looks like a good example of an instance where this could happen.

As @vonbrand says, "And unless circumstances are exceptional, your time is much more valuable than the computer's, so think first in terms of ease of writing/understanding the program". Or, to quote Tony Hoare and Donald Knuth: "Premature optimization is the root of all evil." To this I'd add, focus first on algorithm and data structure improvements (where one can often make the biggest improvements) and on user needs: and then if performance of this particular part of the code is really critical, try both a loop and recursion and measure. Don't rely on your intuition; measure.

# Answer
> 2 votes
It is commonly agreed that loops (`for` or `while`) lead to code that is a bit faster than equivalent code based on recursive calls.

However, this speed improvement is small and should only be sought for crucial loops, that is, loops that will be run many millions of times. For the rest of the code (probably 99% of it) clarity, robustness, ease of debugging and modifying should be the priority. Choose recursion when it is clearer, loops when they are clearer. In the long run clearer code will run faster, sooner and for a longer time, than incomprehensible code.

# Answer
> 1 votes
In general a true recursive code will execute slower than a loop based counterpart. That said as others have mentioned many compilers have native capabilities that change recursive code into loop based instructions.

That said I feel another point to bring up is that recursive code can lead to memory leakage in the case that it doesn't terminate whereas its loop based counterpart does not entail this.

# Answer
> 1 votes
In support of the argument that clarity shall be addressed, I only wanted to add to the discussion the fact that some functions are inherently recursive (and they belong to the bottom of the hierarchy of recursive functions known as *primitive recursive functions*). In fact, a good example of such functions are *super-exponential* functions (e.g., $n^{m^u...}$ where $n$, $m$ and $u$ are related to the problem size) where one could not easily imagine a **simple** way to implement them properly in a loop (or a number of nested loops), in particular if they consist of a recursive invocation where at least one argument is also solved recursively.

One of such examples is the Ackerman's function. This function is solved according to three different cases. The third one solves *Ackerman(m,n)* as *Ackerman (m-1, **Ackerman(m, n-1)**)*. This video (*The most difficult program to compute?*) provides an excellent introduction to these concepts and others. Note that the Ackerman's function is decidable and one can easily prove that it necessarily halts provided that its arguments are non-negative. Computing the values of this function takes just an inconceivable amount of time.

Cheers,

---
Tags: algorithms, recursion, performance, loops, numerical-algorithms
---


# Question
Title: Help with understanding Hopcroft's algorithm
So I wrote an implementation of Hopcroft's algorithm. While testing, I discovered that it would sometimes produce an automaton that wasn't equivalent to the original. At first, I figured it must be a bug in my code, but after going over the algorithm by hand with a small example, it seems to be a bug in my understanding of the algorithm. Can someone help me correct my understanding?

Here is the algorithm, copied from the paper "Re-describing and algorithm by Hopcroft" by Knuutila. (This version differs a little from the one on Wikipedia, but I have essentially the same problem with that one too.)

```
let P = {F, F^c}, where F is the set of accepting states
let W = {(F, x) for every x in the alphabet}
while W is non-empty:
    remove an arbitrary element (A, x) from W
    let X be the set of states that move into A on input x
    for every Y in P that intersects non-trivially with X:
        replace Y in P by (Y intersect X) and Y \ X
        for every symbol x:
            if (Y, x) in W:
                replace (Y, x) in W by (Y intersect X, x) and (Y \ X, x)
            else
                add either (Y intersect X, x) or (Y \ X, x) to W
return P

```

Note that there are two sources of non-determinism in this algorithm: we can remove an arbitrary element from W, and if (Y, x) is not in W then we have a choice as to whether to add (Y intersect X, x) or (Y \ X, x). Unless I have misunderstood something, the algorithm is supposed to be correct no matter what choices we make.

Now, here is my example:

The alphabet is {a, b, c} and the only accepting state is 4, so we start the algorithm with P = 0123|4 and W = {(4, a), (4, b), (4, c)}.

In the first round, suppose we choose (4, b) as our arbitrary element of W. Nothing moves to 4 on input b, so the inner loop is empty. We get back to the outer loop with P=0123|4 and W = {(4, a), (4, c)}.

Next, suppose we choose (4, c). Then X = 12, which intersects non-trivially with 0123, splitting it into 03|12. Since no (0123, x) belongs to W, the "if" condition always fails. Suppose that we add (12, a), (12, b) and (12, c) into W. We get back to the outer loop with P=03|12|4 and W = {(4, a), (12, a), (12, b), (12, c)}.

Next, suppose we choose (4, a). Then X = 3, which intersects non-trivially with 03, splitting it into 0|3. Since so (03, x) belongs to W, the "if" condition always fails. Suppose that we add (0, a), (0, b) and (0, c) into W. We get back to the outer loop with P=0|12|3|4 and W = {(12, a), (12, b), (12, c), (0, a), (0, b), (0, c)}.

All of the rest of the main loop iterations leave P alone, since 0 is the only state that leads into any of 0, 1, or 2. So we end up returning 0|12|3|4. This is clearly wrong, though, because the string "aa" is an accepting input for state 1 but not state 2, so states 1 and 2 are not equivalent.

# Answer
Hopcroft's algorithm works well on complete DFA. (ie. for $M=\\{Q,\Sigma,\delta,q\_0,F\\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function).

For incomplete DFA with partial state transition function $\delta$. You can always convert it to complete DFA $M'=\\{Q',\Sigma,\delta',q\_0,F\\}$ where $$Q'=Q\cup\\{q\_{err}\\}$$ and $\delta'$ extends $\delta$ by define $\delta\_a(q)=q\_{err}$ for all undefined $\delta\_a(q), \delta\_a\in\delta,q\in Q\cup\\{q\_{err}\\}$.
> 3 votes

---
Tags: algorithms, optimization, finite-automata
---


# Question
Title: Term clarification: Establishing a domination
In the book "Approximation Algorithms" by Vazirani (legally available online), part of the hint to Exercise 9.6 (on page 77 of the book, page 95 of the PDF) says "Establish a domination". I've never heard this terminology before in the context of computer science/approximation algorithms/bin packing (I'm not so sure what the correct context is).

Perhaps someone here has familiarity with this terminology. If so, I'd love to hear the definition of "Domination" in this context.

# Answer
We say that $A$ *dominates* $B$ if $A \geq B$ (or, more generally, if $A \succeq B$ in some partial order). To establish a domination means to establish that something dominates something else. I'll let you figure out which domination is meant in your context.
> 1 votes

---
Tags: algorithms, terminology, approximation, packing
---


title: Table-Driven Agent Program

text:
# Question
Title: Table-Driven Agent Program
I have two questions regarding a paragraph about table-driven agent programs from Modern Approach to Artificial Intelligence 3rd Edition.

1. "Let $\mathbb{P}$ be the set of possible percepts and let *T* be the lifetime of the agent (the total number of percepts it will receive). The lookup table will contain $\sum\limits\_{t=1}^T |\mathbb{P}|^t$ entries. Consider the automated taxi: the visual input from a single camera comes in at a rate of roughly 27 megabytes per second (30 frames per second, 640 x 480 pixels with 24 bits of color information). *This gives a lookup table with over $10^{250,000,000,000}$ entries for an hour's driving*."

Can someone please show me the step-by-step derivation of the total number of entries based on the given information to arrive at a value over $10^{250,000,000,000}$? I did my math in the following way, but clearly there is something wrong:

---

$\mathbb{P} = 2^{640x480x24}$, since per frame there are 24x640x480 bits, and each frame is a percept. (I'm not entirely sure that my claim that a frame is a percept is accurate.)

Then, the total number of entries (S) for an hour is as follows:

S = $\sum\limits\_{t=1}^{T=3600x30} (2^{640x480x24})^{t}$.

That series can be converted into the following closed form:

S = $\frac{\mathbb{P}^{T+1} - \mathbb{P}}{\mathbb{P} - 1}$.

If I plug in $2^{640x480x24}$ for $\mathbb{P}$, I end up with essentially $10^{240,000,000,000}$ and NOT over $10^{250,000,000,000}$. What am I doing wrong?

---

2. "The daunting size of these tables (the number of atoms in the observable universe is less than $10^{80}$) means that (a)...(d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries." I'm not exactly sure what guidance the designer needs. I'm assuming that the agent function already exists. In that case, all the designer needs to do in constructing their table entries is look up the corresponding action with each percept sequence.

I thank everyone in advance for taking the time to read this and help me out =)!

# Answer
You are asking two questions. The answer to your first question is very simple – the authors used a figure of speech when they wrote *over* $10^{250,000,000,000}$. What they meant was *roughly* $10^{250,000,000,000}$. In any case, the exact number isn't important – it is just supposed to be an impressively large number rather than an exact estimate. For this reason I didn't bother to check your calculation. It is possible that your calculation is right, and the authors either got it wrong or preferred writing a round number rather than a more pedantic one; but it doesn't really matter.

As to your second question, probably the authors meant what they wrote – even when the table is small, it's not clear what its contents should be! For example, consider a speech recognition program. It is possible to convert the high dimensional raw input into a low dimensional representation using a vocoder. However, it is still difficult to parse what the person is saying, for many reasons. (This is just a guess as to what they meant; you aren't supplying enough context.)

If you want to understand the authors' comments mentioned in your second question better, I suggest you keep reading the book. The authors probably offer solutions to these problems, and these solutions will highlight the problems themselves.
> 1 votes

---
Tags: artificial-intelligence
---


# Question
Title: How can a language whose compiler is written in C ever be faster than C?
Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, outperform C code?

**Figure: benchmark times relative to C (smaller is better, C performance = 1.0).**

# Answer
> 290 votes
There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, because *its* code is written in a slow language. (To be more precise, written in a language with a slow implementation. Languages aren't really inherently fast or slow, as Raphael points out in a comment. I expand on this idea below.) The compiled program would be as fast as its own implementation allowed—we could write a compiler in Python that generates the same machine code as a Fortran compiler, and our compiled programs would be as fast as Fortran, even though they would take a long time to compile.

It's a different story if we're talking about an interpreter. Interpreters have to be running while the program they're interpreting is running, so there is a connection between the language in which the interpreter is implemented and the performance of the interpreted code. It takes some clever runtime optimization to make an interpreted language which runs faster than the language in which the interpreter is implemented, and the final performance can depend on how amenable a piece of code is to this kind of optimization. Many languages, such as Java and C#, use runtimes with a hybrid model which combines some of the benefits of interpreters with some of the benefits of compilers.

As a concrete example, let's look more closely at Python. Python has several implementations. The most common is CPython, a bytecode interpreter written in C. There's also PyPy, which is written in a specialized dialect of Python called RPython, and which uses a hybrid compilation model somewhat like the JVM. PyPy is much faster than CPython in most benchmarks; it uses all sorts of amazing tricks to optimize the code at runtime. However, the Python language which PyPy runs is *exactly the same Python language* that CPython runs, barring a few differences which don't affect performance.

Suppose we wrote a compiler in the Python language for Fortran. Our compiler produces the same machine code as GFortran. Now we compile a Fortran program. We can run our compiler on top of CPython, or we can run it on PyPy, since it's written in Python and both of these implementations run the same Python language. What we'll find is that if we run our compiler on CPython, then run it on PyPy, then compile the same Fortran source with GFortran, we'll get exactly the same machine code all three times, so the compiled program will always run at around the same speed. However, the time it takes to produce that compiled program will be different. CPython will most likely take longer than PyPy, and PyPy will most likely take longer than GFortran, even though all of them will output the same machine code at the end.

From scanning the Julia website's benchmark table, it looks like none of the languages running on interpreters (Python, R, Matlab/Octave, Javascript) have any benchmarks where they beat C. This is generally consistent with what I'd expect to see, although I could imagine code written with Python's highly optimized Numpy library (written in C and Fortran) beating some possible C implementations of similar code. The languages which are equal to or better than C are being compiled (Fortran, Julia) or using a hybrid model with partial compilation (Java, and probably LuaJIT). PyPy also uses a hybrid model, so it's entirely possible that if we ran the same Python code on PyPy instead of CPython, we'd actually see it beat C on some benchmarks.

# Answer
> 101 votes
How can a machine built by a man be stronger than a man? This is exactly the same question.

The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not on the langauge used to implement it. You could write a really slow, inefficient compiler that produces very efficient code. There's nothing special about a compiler: it's just a program that takes some input and produces some output.

# Answer
> 94 votes
I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job.

**There is no such thing as a slow or fast language.**¹

On our way to the CPU actually doing something, there are many steps².

1. At least one programmer with certain skillsets.
2. The (formal) language they program in ("source code").
3. The libraries they use.
4. Something that translates source code into machine code (compilers, interpreters).
5. The overall hardware architecture, e.g. number of processing units and layout of the memory hierarchy.
6. The operating system which manages the hardware.
7. On-CPU optimizations.

*Every single item* contributes to the actual runtime you can measure, sometimes heavily. Different "languages" focus on different things³.

Just to give some examples.

* *1 vs 2-4*: an average C programmer is likely to produce far worse code than an average Java programmer, both in terms of correctness and efficiency. That is because the programmer has *more responsibilities* in C.
* *1/4 vs 7*: in low-level language like C, you may be able to exploit certain CPU features *as a programmer*. In higher-level languages, only the compiler/interpreter can do so, and only if they *know* the target CPU.
* *1/4 vs 5*: do you want or have to control the memory layout in order to best use the memory architecture at hand? Some languages give you control over that, some don't.
* *2/4 vs 3*: Interpreted Python itself is horribly slow, but there are popular bindings to *highly* optimized, natively compiled libraries for scientific computing. So doing certain things in Python is *fast* in the end, if most of the work is done by these libraries.
* *2 vs 4*: The standard Ruby interpreter is quite slow. JRuby, on the other hand, can be very fast. That is the same language is fast using another compiler/interpreter.
* *1/2 vs 4*: Using compiler optimisations, simple code can be translated into very efficient machine code.

The bottom line is, the benchmark you found does not make much sense, at least not when boiled down to that table you include. Even if all you are interested in is running time, you need to specify the *whole chain* from programmer to CPU; swapping out any of the elements can change the results dramatically.

To be clear, this answers the question because it shows that the language the compiler (step 4) is written in is but one piece of the puzzle, and probably not relevant at all (see other answers).

---

1. There certainly *are* language features that are more costly to implement than others. But the existence of features does not mean you have to use them, and an expensive feature may save the use of many cheaper ones and thus pay of in the end. (Of have other advantages not measurable in running time.)
2. I skip over the algorithmic level because it does not always apply and is mostly independent of the programming language used. Keep in mind that different algorithms lend themselves better to different hardware, for instance.
3. I deliberately don't go into different success metrics here: running time efficiency, memory efficiency, developer time, security, safety, (provable?) correctness, tool support, platform independency, ...

Comparing languages w.r.t. one metric even though they have been designed for completely different goals is a huge fallacy.

# Answer
> 23 votes
There is one forgotten thing about optimisation here.

There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers thought) and performance was tested based on same data. The problem is, these languages differ, C allows pointers aliasing, while fortran does not.

So the codes were not same, there was no \__restrict in C tested files, which gave differences, after rewriting files to tell compiler that it can optimise pointers, the runtimes become similar.

The point here is, that some optimisation techniques are easier (or starts to be legal) in newly created language.

Also it is possible in long run to VM with JIT outperform C. There are two possibilities:
JIT code can take advantage of machine that it hosts it (for example some SSE $X$ or other exclusive for some CPU vectorised instructions) that were not implemented in compared program.

Secondly VM can perform pressure test while running, so it can take pressured code and optimise it or even precalculate it during runtime. In advance compiled C program does not expect where is the pressure or (the most of the time) there are generic versions of executables for general family of machines.

In this test there is also JS, well there are faster VMs than V8, and it also performs faster than C in some tests.

I have checked it, and there were unique optimising techniques not available yet in C compilers.

C compiler would have to do static analysis of whole code at once, march upon given platform and go around memory alignment problems.

VM just transliterated part of the code to optimised assembly and run it.

About Julia - as I checked it operates on AST of code, for example GCC skipped this step an just recently started to take some info from there. This plus other constraints and VM techniques might explain a bit.

Example: let us take simple loop, that takes starting end ending point from variables and loads part of variables into calculations know at the runtime.

C compiler generates loading variables from registers.
But at the runtime these variables are known and treated as constants through execution.
So instead of loading variables from registers (and not performing caching because it can change, and from static analysis it is not clear) they are treated fully like constants and folded, propagated.

# Answer
> 12 votes
The previous answers give pretty much the explanation, though mostly from a pragmatic angle, *for as much as the question makes sense*, as excellently explained by Raphael's answer.

Adding to this answer, we should note that, nowadays, C compilers are written in C. Of course, as noted by Raphael their output and its performance may depend, among other things, on the CPU it is running on. But it also depends on the amount of optimization done by the compiler. If you write in C a better optimizing compiler for C (which you then compile with the old one to be able to run it), you get a new compiler that makes C a faster language than it was before. So, **what is the speed of C?** Note that you can even compile the new compiler with itself, as a second pass, so that it compiles more efficiently, though still giving the same object code. And the full employment theorem shows that their is no end to such improvements (thanks to Raphael for the pointer).

But I think it may be worthwhile trying to formalize the issue, as it illustrate very well some fundamental concepts, and particularly denotational versus operational view of things.

## What is a compiler?

A compiler $C\_{S\to T}$, abbreviated to $C$ if there is no ambiguity, is a realization of a computable function $\mathcal C\_{S\to T}$ that will translate a program text $P\_{:S}$ computing a function $\mathcal P$, written in a **source language** $S$ into program text $P\_{:T}$ written in a **target language** $T$, that is supposed to compute the same function $\mathcal P$.

From a semantic point of view, i.e. **denotationally**, it does not matter how this compiling function $\mathcal C\_{S\to T}$ is computed, i.e., what realization $C\_{S\to T}$ is chosen. It could even be done by a magic oracle. Mathematically, the function is simply a set of pairs $\\{(P\_{:S},P\_{:T})\mid P\_S\in S \wedge P\_T\in T\\}$.

The semantic compiling function $\mathcal C\_{S\to T}$ is correct if both $P\_S$ and $P\_T$ compute the same function $\mathcal P$. But this formalization applies as well to an incorrect compiler. The only point is that whatever is implemented achieves the same result independently of the implementation means. What matters semantically is what is done by the compiler, not how (and how fast) it is done.

Actually getting $P\_{:T}$ from $P\_{:S}$ is an **operational** issue, that must be solved. This is why the compiling function $\mathcal C\_{S\to T}$ must be a computable function. Then any language with Turing power, no matter how slow, is sure to be able to produce code as efficient as any other language, even if it may do so less efficiently.

Refining the argument, we probably want the compiler to have good efficiency, so that the translation can be performed in reasonable time. So the performance of the compiler program matters for users, but it has no impact on semantics. I am saying performance, because the theoretical complexity of some compilers can be much higher than one would expect.

## About bootstrapping

This will illustrate the distinction, and show a practical application.

It is now common place to first implement a language $S$ with an interpreter $I\_S$, and then write a compiler $C\_{S\to T\\,:S}$ in the language $S$ itself. This compiler $C\_{S\to T\\,:S}$ can be run with the interpreter $I\_S$ to translate any program $P\_{:S}$ into a program $P\_{:T}$. So we do have a running compiler from language $S$ to (machine?) language $T$, but it is very slow, if only because it runs on top of an interpreter.

But you can use this compiling facility to compile the compiler $C\_{S\to T\\,:S}$, since it is written in language $S$, and thus you get a compiler $C\_{S\to T\\,:T}$ written in the target language $T$. If you assume, as often the case, that $T$ is a language that is more efficiently interpreted (machine native, for example), then you get a faster version of your compiler running directly in language $T$. It does exactly the same job (i.e. produces the same target programs), but it does it more efficiently.

# Answer
> 6 votes
By Blum's speedup theorem there are programs which written and run on the very fastest computer/compiler combination will run slower than a program for the same on your first PC running interpreted BASIC. There just isn't a "fastest language". All you can say is that if you write the *same* algorithm in several language (implementations; as noted, there are plenty of different C compilers around, and I even came across a rather capable C interpreter), it will run faster or slower in each.

There can't be a "always slower" hierarchy. This is a phenomenon everybody fluent in several languages is aware of: Each programming language was designed for a specific type of applications, and the more used implementations have been lovingly optimized for that type of programs. I'm pretty sure that e.g. a program for fooling around with strings written in Perl will probably beat the same algorithm written in C, while a program munching on large arrays of integers in C will be faster than Perl.

# Answer
> 5 votes
Let's go back to the original line: **"How can a language whose compiler is written in C ever be faster than C?"** I think this really meant to say: how can a program written in Julia, whose core is written in C, ever be faster than a program written in C? Specifically, how could the "mandel" program as written in Julia run in 87% of the execution time of the equivalent "mandel" program written in C?

Babou's treatise is the only correct answer to this question so far. All the other responses so far are more or less answering other questions. The problem with babou's text is that the many-paragraphs-long theoretical description of "What is a compiler" is written in terms that the original poster will probably have trouble understanding. Anyone who grasps the concepts referred to by the words "semantic", "denotationally", "realization", "computable" and so on will already know the answer to the question.

The simpler answer is that neither C code, nor Julia code, is directly executable by the machine. Both have to be translated, and that translation process introduces a lot of ways that the executable machine code can be slower or faster, but still produce the same end result. Both C and Julia do compilation, which means a series of translations to another form. Commonly, a human-readable text file is translated to some internal representation, and then written out as a sequence of instructions that the computer can understand directly. With some languages, there's more to it than that, and Julia is one of these -- it has a "JIT" compiler, which means the whole translation process doesn't have to happen all at once for the entire program. But the end result for any language is machine code that needs no further translation, code that can be sent directly to the CPU to make it do something. In the end, THIS is the "computation", and there is more than one way to tell a CPU how to get the answer you want.

One could imagine a programming language that has both a "plus" and a "multiply" operator, and another language that has only "plus". If your computation requires multiplication, one language will be "slower" because of course the CPU can do both directly, but if you don't have any way to express the need to multiply 5 * 5, you are left having to write "5 + 5 + 5 + 5 + 5". The latter will take more time to arrive at the same answer. Presumably, there's some of this going on with Julia; perhaps the language allows the programmer to state the desired goal of computing a Mandelbrot set in a way that isn't possible to directly express in C.

The processor used for the benchmark was listed as a Xeon E7-8850 2.00GHz CPU. The C benchmark used the gcc 4.8.2 compiler to produce instructions for that CPU, while Julia uses the LLVM compiler framework. It's possible that gcc's backend (the part that produces machine code for a particular CPU architecture) isn't as advanced in some way as the LLVM backend. That could make a difference in performance. There are also many other things going on -- the compiler can "optimize" by perhaps issuing instructions in a different order than specified by the programmer, or even not doing some things at all if it can analyze the code and determine they're not required to get the right answer. And the programmer might have written part of the C program in a way that make it slow, but didn't make such mistakes in the Julia code -- for example, the order in which elements in a two-dimensional array are accessed might have no bearing on the end result of the computation, but the order might well make a difference in speed (see "Row major versus Column major layout of matrices").

All of these are ways of saying: there are lots of ways to write machine code to compute a Mandelbrot set, and the language you use has a major effect on how that machine code gets written. The more you understand about compilation, instruction sets, caches, and so on, the better equipped you will be to get the results you want. The major takeaway from the benchmark results cited for Julia is that no one language or tool is best at everything. In fact the best speed factor in the entire chart was for Java!

# Answer
> 2 votes
The speed of a compiled program depends on two things:

1. The performance characteristics of the machine executing it
2. The contents of the executable file

The language a compiler is written in is irrelevant to (1). For example, a Java compiler can be written in C or Java or Python, but in all cases the "machine" executing the program is the JVM.

The language a compiler is written in is irrelevant to (2). For example, there is no reason why a C compiler written in Python cannot output exactly the same executable file as a C compiler written in C or Java.

# Answer
> 1 votes
I'll try to offer a shorter answer.

**The core of the question lies in the definition of "speed" of a language**.

Most if not all speed comparison tests don't test what the maximum possible speed is. Instead they write a small program in a language they want to test, to solve a problem. When writing the program the programmer uses what the they assume\* to be best practice and conventions of the language, at the time of the test. Then they measure the speed at which the program was executed.

\*The assumptions are occasionally wrong.

# Answer
> 0 votes
Code written in a language X whose Compiler is written in C, can outperform a code written in C, provided, C compiler does poor optimization compared to that of language X. If we keep optimization out of discussion then if compiler of X could generate better object code than that generated by C compiler, then also code written in X may win the race.

But if language X is an interpreted language, and the interpreter is written in C, and if we assume that interpreter of language X and code written in C is compiled by same C compiler, then in no way code written in X going to outperform code written in C, provided both implementation follow same algorithm and uses equivalent data structures.

---
Tags: programming-languages, compilers, efficiency
---


# Question
Title: Clustering a set of images using keypoint descriptors
I'm trying to cluster around 16000 images into ~200 clusters, using kmeans with metric as euclidean distance or cosine distance. I understand that i need to extract keypoint descriptors to compute features for each image. I'm looking at SIFT as an option but, SIFT outputs different number of keypoints for each image that i have. How can i use these keypoint descriptors generated by SIFT to make a uniform sized feature vector for every image, so that i can feed these vectors to kmeans. Or should i use any other feature descriptor apart from SIFT?

# Answer
I don't know how to do it that way. I would suggest you do it a different way:

1. Define a distance metric that measures the dissimilarity between two metrics. In particular, if $I,J$ are two images, $d(I,J)$ should quantify how dissimilar $I,J$ are -- large values indicate they are very different, small values indicate they are very similar.
2. Use a different clustering algorithm that only needs a distance metric.

For #1, there are many ways of measuring/computing image similarity. If you want to use SIFT as your starting point, you can align the two images and compute some metric based upon the number of keypoints that are well-matched ("inliers") vs the number that aren't ("outliers).

For #2, there are many options. One option is to use hierarchical clustering.

I recommend you spend some time reading through the research literature on measuring image similarity in the computer vision literature. There's *lots* of work, and many methods proposed and evaluated.

See also https://stackoverflow.com/q/843972/781723 and https://stackoverflow.com/q/4196453/781723. You could also use the TinEye API.
> 2 votes

---
Tags: machine-learning, image-processing, computer-vision, cluster
---


# Question
Title: How are alphabetic characters programmed into a computer?
I'm no cs student, I'm a programmer. I have a couple of questions and a few assumptions that I will make here (correct me if I'm wrong please).

From my understanding is that all the sequences of 1 and 0's that computers execute are just representations of actual data or instructions that tell other hardware on a system what to do like telling a graphic card to change a pixels color on the monitor.

01100001 being the representation of the letter "a" and that this sequence of bits has been chosen by the fathers of computing/ascii or what have you to represent that letter, it could just as well have been some other sequence right?

All computer systems have agreed that those bits mean the letter "a" for all of the computers around the globe to be interoperable, if there were no standards in place for this the internet would be a mess.

What I want to know is: where is the information stored on a computer that tells it that these sequences of bits here mean/represent the character "a"? Is it in the OS or directly on the motherboard or am I just completely wrong?

# Answer
It isn't stored anywhere. 01100001 could represent anything. It could be the ASCII character "a" or it could be the integer 97 or it could even be something different entirely. It's up to the programmer to tell the computer what to do with 01100001, for instance by supplying a font file that tells it how to map binary sequences to the instructions to draw a character on the screen. Often this is taken care of in libraries but the OS and motherboard have no idea that 01100001 represents "a".
> 5 votes

# Answer
The computer as is doesn't handle text, just numbers. The interpretation of the numbers computed is up to other pieces of hardware, i.e., your keyboard sends a number into the machine when you press "a", your terminal paints a image on the screen (which is defined by a memory in the terminal) which you read as "a", and so on. Take a look at the assembly language of your preferred machine. You'll see instructions to handle strings of bytes, but nothing as such that "knows" the characters are e.g. letters or say an "\*". If some bits are used in an arithmetic operation, they are a number; if sent to a screen or printer, probably (part of) a character or perhaps some instruction (blank the screen, perhaps). Interpretation is up to the recipient.

In modern machines the input process is more complex, and the image painted on the screen is also the result of a much more complex process, but the basic idea is the same.
> 4 votes

# Answer
There are many places where the semantics of *a* are (implicitly) stored. Here are a few examples:

* Fonts map the ASCII code of *a* to its graphic representation.
* Dictionaries used for spell-checking contain lists of words, in which the ASCII code of *a* is used to represent the letter *a*.
* DNS servers convert domain names to IP addresses. Some domain names include the letter *a*, so the databases maintained by these servers give meaning to the ASCII code of *a*.
* Compilers have rules for identifier names that often mention alphanumeric characters, and in particular *a*. Even more, some reserved words could include the letter *a*.
> 3 votes

# Answer
The mapping between what you type on the keyboard, the ASCII letter A, and the character drawn on the screen, is stored in many places explicitly as code.

* Fundamentally, when you first boot a computer, the BIOS code (or "the motherboard") has code to translate what comes from the keyboard (scancodes) into ASCII, and the Video BIOS (also part of the motherboard or video card) has code the draw that ascii code as the letter 'A' on the screen.
* This mapping is repeated at the OS level, to support additional character sets beyond ASCII and additional keyboard types. For an example, see the Linux keyboard driver, where a scancode for "A" on a standard ATA keyboard is mapped to an OS-internal definition of the letter "A" (called KEY\_A, see http://lxr.free-electrons.com/source/drivers/input/keyboard/atakbd.c#L113), and then the Linux kernel maps that to the ASCII code for A (see http://lxr.free-electrons.com/source/drivers/tty/vt/defkeymap.map#L75)

Only standards define these character mappings; a notable alternative is EBCDIC used on mainframes.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Intrinsic matrices in stereo camera calibration
Suppose I have two cameras, c1 and c2, observing the same scene. I can now

1. Calibrate each camera independently (e.g., with MATLAB's Camera Calibration App)
2. Calibrate both cameras simultaneously (e.g., with MATLAB's Stereo Camera Calibration App).

Interestingly, the values calculated for the intrinsic parameters of both cameras are different using method 1) and method 2). To me it is not clear why this should be the case. The intrinsic parameters of camera 1 are independent of the ones of camera 2 and vice versa, why should they influence each other? I suppose there is some form of optimization aiming to optimize simultaneously in the stereo case, however I would think that the "stereo optimum" is the same as the combined "single optimum".

Any insight?

# Answer
You are correct: during stereo calibration the parameters of both cameras are optimized simultaneously, which is why you get the discrepancy.

When you calibrate a single camera, you are minimizing the reprojection errors from projecting the checkerboard points into that one camera. When you calibrate a stereo pair of cameras, you are minimizing the reprojeciton errors from projecting the checkerboard points into both cameras. Since you are minimizing different functions, the results will not be the same. However, the difference should be small.
> 3 votes

---
Tags: image-processing, computer-vision
---


# Question
Title: graph theory analogue of rectangular matrix
Graphs are usually defined as a set of vertices $V$ together with a set of edges $E$ consisting of elements $V \times V$. I'm interested in a slight generalization of this, where instead one has two sets $V$, $W$ and the edges are taken from $V \times W$. The adjacency matrix of such an object would be rectangular, as opposed to the adjacency matrix of a regular old graph, which is square. Is there a name for this?

I'm interested in this because I'm writing a data structure to represent a graph in terms of its partitioning into sub-graphs for the purposes of parallel computation. For example, given a graph $G$ on a vertex set $V$, we can partition $V$ into disjoint subsets $V\_1$ and $V\_2$; $G$ is then naturally divided into two subgraphs $G\_1$ and $G\_2$ describing connections among $V\_1$ and $V\_2$ respectively, and a "rectangular graph" $H$ describing connections between $V\_1$ and $V\_2$. I'd like to give the class a name that makes sense.

# Answer
> 5 votes
Such a graph is known as a bipartite graph. There is a whole theory about bipartite graphs, including a number of algorithms that are specialized for bipartite graphs.

---
Tags: graphs
---


# Question
Title: The maximum & minimum number of sources that can be multiplexed so that no data loss occurs on TOKEN BUCKET?
A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of on-time to off-time, is 1 : 2. When there is no buffer at the link, the minimum number of sources that can be multiplexed on the link so that link capacity is not wasted and no data loss occurs is S1. Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that no data loss occurs is S2. The values of S1 and S2 are, respectively,

A) 10 and 30

B) 12 and 25

C) 5 and 33

D) 15 and 22

I have solved the part (i) of the problem to find the minimum no. of stations & got 10 as there is no bucket,so for no data loss I equated the incoming traffic rate by S1 stations = Maximum capacity of the channel.In 2nd part I'm having trouble what will happen when a buffer is placed.Please help.Make me correct if 1st part is not correct.

# Answer
A is correct. As 1st part is already described i will explain derivation of S2 only. Let there are N stations. When buffer is added then even when source is off, data will persist so considering duty cycle here we say that the actual data transmitted per unit time during the whole duty cycle is (1/3)*10 \[for 1 unit of on-time data is transmitted and for another 2 unit of off-time it stays in buffer so in 3 unit time 10Mbps data is tranferred\]. This is the case will all other N-1 stations also. So adding all should be = Max capacity of channel. N*(1/3)\*10 = 100 N=30
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Maximum independent nodes subset algorithm with strong constraint
I've a tree with weighed nodes, the problem is to flag a subset of nodes with the following constraints:

* The selected nodes must be the optimal solution (maximal sum of weight).
* If one node is flagged no adjacent nodes can be flagged.
* If a node is flagged it will be called: "directly controlled", the adjacent nodes instead will be called: "indirectly controlled", all nodes must be directly or indirectly controlled.

I think is a dynamic programming problem (a greedy approach didn't find always a optimal solution), the first two constraints are a typical maximum independent subset problems, but i cannot find a solution with the third constraint included. Any idea? Thanks

# Answer
> 1 votes
A set satisfying condition (3) is known as a *dominating set*. The exercise asks for a maximum weight dominating independent set.

If all node weights are positive, then every optimal solution is automatically a dominating set (why?), regardless of whether the graph is a tree or not. In the more general case in which negative weights are allowed, you can use a standard dynamic programming approach. Root the tree at an arbitrary node, and for every subtree rooted at some internal node $v$, compute the maximum weight independent set in the following three cases:

* The independent set is dominating and includes $v$.
* The independent set is dominating and doesn't include $v$.
* The independent set is dominating if $v$ is removed (it is allowed to dominate $v$ as well), and doesn't include $v$.

I'll let you complete the details.

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


# Question
Title: Is there a way of objectively measuring the efficiency or quality of software or code design?
I've been thinking about ways of measuring code, and, quite frankly, I can't think of truly objective, semi-universal ways of evaluating the quality or "strength" of code to say, "Yes, this is better than that based on X, Y, and Z metrics" that are popular or exist. I've looked at SonarQube, and although I think their metrics are important, I feel like there are more fundamental concepts at work than what they have now.

But, of course, it's often said that certain languages are better than others because they have stronger guarantees or abstractions: C++ \> C with abstraction, and Haskell \> C++ with typing and purity and a whole slew of other features. But I was wondering whether it would be possible to actually quantify *how* much better one is than the other.

**Are there existing papers that talk about ways of objective comparing coding paradigms or languages based on objective metrics?**

---

A few of the resources I've found while search have to do with more business-y metrics like cost of quality or coverage of unit tests over development time. Also, measuring by number of lines seems fishy and not truly crucial (imagine if we measured math proofs' qualities by how many pages of paper it takes to print!):

Apparently the list of top 10 papers are also not based on measuring the efficiency of design in code, but are more focused on specific areas:

# Answer
> 3 votes
The abstract conclusion is not really that "some languages are better than others" but that "some languages are better than others *for some purposes*". Different languages are somewhat like species in evolutionary biology. They have evolved to fill certain niches. There are many evolutionary niches. They have strengths and weaknesses in different areas. Sometimes these types of analysis can degenerate into what is known in stackexchange as "gorilla vs shark" debates.

The question seems to mix up certain distinct areas in CS study. Code quality is measured by defects and is more programmer and implementation related than language related. Defects can be high or low in any language. efficiency in CS is generally considered interchangeable with ("execution") complexity and measured with Big-O notation. There is also another notion of code/ programming complexity where some functionally equivalent implementations may have different levels of complexity in their programs. This is studied especially in OOP theory.

However recently there is some research along the lines you mentioned. There is a large database of programs with identical functions written in the Rosetta code database and some comparative/ objective/ scientific/ quantitative analysis has been done by researchers. See eg:

---
Tags: programming-languages, software-engineering, design-patterns
---


# Question
Title: Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard?
Suppose we forget about optimizing and just want to find a feasible solution to a set of equations:

$$\sum\_i w\_{ij} x\_i = W\_j.$$

Here we are given $w\_{ij}$ and $W\_j$, and want to solve for $x\_i$. Also $x\_i$ are restricted to be 0/1 and we're promised that $w\_{ij}$ and $W\_j$ will be non-negative integer constants and we will have $w\_{ij} \leq M$ for some universal constant $M$. The number of variables and equations can be arbitrary.

Is this an NP-complete problem? If we have just one or a universal bounded number of equations then the problem can be solved in polynomial time. Certainly if we can find a solution then we can verify it in polynomial time, so the problem is in NP. I was trying to find a reduction from something like 3-SAT in the general case but to no avail.

# Answer
> 5 votes
This problem is NP-complete, by reduction from 1-in-3 positive 3SAT.

1-in-3 positive 3SAT is a variant of 3SAT, where we require that exactly each clause consists of 3 *positive* literals (no negation), and to satisfy the formula, exactly one literal in each clause must be true (no more, no less). Thus, each 1-in-3 positive 3SAT instance is a formula

$$\varphi(x\_1,\dots,x\_n) = \bigwedge\_i (x\_{c\_{i,1}} \sqcup x\_{c\_{i,2}} \sqcup x\_{c\_{i,3}}),$$

where $x \sqcup y \sqcup z$ is true iff exactly one of $x,y,z$ is true.

You can immediately convert this to an instance of your problem. In particular, the $i$th clause corresponds to an equation

$$x\_{c\_{i,1}} + x\_{c\_{i,2}} + x\_{c\_{i,3}} = 1.$$

For instance, the clause $(x\_3 \sqcup x\_5 \sqcup x\_6)$ corresponds to the equation $x\_3 + x\_5 + x\_6 = 1$. We get one equation per clause. The equations are simultaneously satisfiable iff the formula $\varphi$ is satisfiable. This completes the reduction.

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


# Question
Title: Finding the kth smallest element of an array using DAC
I'm trying to find the $k^{th}$ smallest element of an array by using `Randomized Quicksort`, But below code giving erroneous result can anybody help.

```
from random import randint

lst=[1,3,5,2,4,6]
k=6
n=6

def swap(i,j):
    t=lst[i]
    lst[i]=lst[j]
    lst[j]=t

def rand_partition(p,q):
    # i is the pivot position
    i=randint(p,q)
    while(p<q):
        if(lst[p]>lst[i]):
            swap(p,p+1)
            p+=1
        else:
            p+=1

    swap(p,q)
    return q

def select(p,q,k):
    r = rand_partition(p,q)
    t = r-p+1

    if(k==t):
        return lst[r]
    elif(k<t):
        return select(p,r-1,k)
    else:
        return select(r+1,q,k-t)

res=select(0,n-1,k)

print('%dth Smallest Element = %d' %(k,res))

```

# Answer
The problem is in your `rand_partition(p,q)` function.

I made some changes with comments.

```
def rand_partition(p,q):
    i=randint(p,q)               # get a random index between p and q
    swap(i,q)                    # move the pivot element to the end
                                 # after now, do the same as normal partitioning
    pivot=lst[q]                 # save pivot
    s=p-1
    j=p
    while(j < q):                #keep invariants (this would be better with a for loop):
        if(lst[j] <= pivot):     # lst[p...s] <= pivot,
            s+=1                 # lst[s+1...j-1] > pivot
            swap(s,j)
        j+=1

    swap(s+1,q)                  # put the pivot in the correct place
    return s+1

```

Also, you can set a base case for `select(p,q,k)` (although this is not critical):

```
def select(p,q,k):
    if (p==q):
        return lst[p]
    #...

```

For more info: Introduction to Algorithms (Cormen, Leiserson, Rivest & Stein)
> 1 votes

---
Tags: randomized-algorithms
---


# Question
Title: Origin of the terms "safety" and "liveness" for concurrent algorithm properties?
Properties of concurrent algorithms are usually divided into two categories:

1. **Safety** \- something *must not* happen.

Properties in this category are for example partial correctness and sometimes deadlock-freedom (the latter depending on the author).
2. **Liveness** \- something that *must* happen *eventually*.

Properties in this category are for example termination and starvation-freedom.

Which publication introduced these terms?

---

The oldest reference I was able to find is "Proving the Correctness of Multiprocess Programs" by Leslie Lamport, dated March 1977:

> To prove the correctness of a program, one must prove two essentially different types of properties about it, which we call *safety* and *liveness* properties. \[...\]

It does, however, not claim to introduce these terms.

# Answer
> 4 votes
Lamport commented on his paper "Proving the Correctness of Multiprocess Programs" as follows:

> This paper introduced the concepts of safety and liveness as the proper generalizations of partial correctness and termination to concurrent programs. It also introduced the terms "safety" and "liveness" for those classes of properties. I stole those terms from Petri nets, where they have similar but formally very different meanings. (Safety of a Petri net is a particular safety property; liveness of a Petri net is not a liveness property.)

This can be seen as a claim that he (Lamport) has introduced the terms.

---
Tags: terminology, reference-request, concurrency
---


title: What is meant by polynomially smaller

text:
# Question
Title: What is meant by polynomially smaller
I'm reading CLRS *Section-4.5: The Master method for solving recurrences*. There is a line saying

> $f(n)$ must be polynomially smaller than $n^{\log\_b a}$.

What is meant by polynomially smaller? Can anybody explain it to me with an example?

# Answer
> 2 votes
In this context, the line means $f(n) = O(n^{\log\_b a - \epsilon})$ for some $\epsilon \> 0$.

More generally, there are a few possible interpretations. Under one interpretation, $f(n)$ is *at least* polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon \> 0$; and $f(n)$ is *at most* polynomially smaller than $g(n)$ if $f(n) = \Omega(g(n)/n^\epsilon)$ for some $\epsilon \> 0$.

A different interpretation has $f(n)$ at least polynomially smaller than $g(n)$ if $f(n) \leq g(n)^{1-\epsilon}$ for some $\epsilon \> 0$, and at most polynomially smaller than $g(n)$ if $f(n) \geq g(n)^\epsilon$ for some $\epsilon \> 0$.

---
Tags: asymptotics
---


# Question
Title: Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$
I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\\{x\in(a,b), \\#\_a(x) = 2\\#\_b(x)\\}$, where $x$ is the input string and $\\#\_a(x),\\#\_b(x)$ the number that $a$ or $b$ appears in the $x$ string.

That means that the following sequences should all be accepted:

> aab aba bbaabaaaa baabaa abbaaa

**My problem:** I've found examples of PDAs being constructed for $a^nb^n$ and even $a^{2n}b^n$ which is pretty close to what I'm looking for, but these languages all have a **predetermined sequence** of the $a$s coming first, then the $b$s.

I've been trying for literally hours to build a PDA that circles between how many $a$s and $b$s it has, and how many it still needs, but every attempted solution has been wrong (situations where consequent same letters cause pops on empty stacks, halting the PDA).

Any information or methodical approaches on constructing a PDA out of a language like that? I'm at my wit's end.

# Answer
> 1 votes
# GPDA$\to$PDA Approach

See you have got a solution from chat. But the first thing popped my mind is a Generalized\_pushdown\_automaton(GPDA), which can be constructed pretty straight forward.

## GPDA construction

$M=(Q,\Sigma,\Gamma,\delta,q\_0,Z,\\{q\_f\\})$, where $Q=\\{q\_0,q\_f\\},\Sigma=\\{a,b\\},\Gamma=\\{a,A,Z\\}$,$\delta$ includes following rules:

1. $(q\_0,a,Z)\to(q\_0,aZ)$
2. $(q\_0,b,Z)\to(q\_0,AAZ)$
3. $(q\_0,a,a)\to(q\_0,aa)$
4. $(q\_0,b,A)\to(q\_0,AAA)$
5. $(q\_0,a,A)\to(q\_0,\epsilon)$
6. $(q\_0,b,aa)\to(q\_0,\epsilon)$
7. $(q\_0,b,aZ)\to(q\_0,AZ)$
8. $(q\_0,\epsilon,Z)\to(q\_f,\epsilon)$

## GPDA$\to$PDA convertion

Using the algorithm provided on Wikipedia, we can convert it to PDA easily. Only 6. and 7. need to convert:

6.1 $(q\_0,b,a)\to(p\_0,\epsilon)$

6.2 $(p\_0,\epsilon,a)\to(q\_0,\epsilon)$

7.2 $(p\_0,\epsilon,Z)\to(q\_0,AZ)$

Resulting PDA is $M=(Q',\Sigma,\Gamma,\delta',q\_0,Z,\\{q\_f\\})$ where $Q'=\\{q\_0,p\_0,q\_f\\}$ and $\delta'=(\delta\setminus\\{6,7\\})\cup\\{6.1,6.2,7.2\\}$. The constructed PDA is non-deterministic.

## Convert to DPDA

To convert to DPDA, the only affected transitions are 1. 2. and 8 in above rules:

$M=(Q,\Sigma,\Gamma,\delta,q\_0,Z,\\{q\_f\\})$, where $Q=\\{q\_0,p\_0,q\_f\\},\Sigma=\\{a,b\\},\Gamma=\\{a,A,Z\\}$,$\delta$ includes following rules:

1. $\mathbf{(q\_0,\epsilon,Z)\to(q\_f,Z)}$
2. $(q\_0,a,a)\to(q\_0,aa)$
3. $(q\_0,b,A)\to(q\_0,AAA)$
4. $(q\_0,a,A)\to(q\_0,\epsilon)$
5. $(q\_0,b,a)\to(p\_0,\epsilon)$
6. $(p\_0,\epsilon,a)\to(q\_0,\epsilon)$
7. $(p\_0,\epsilon,Z)\to(q\_0,AZ)$
8. $\mathbf{(q\_f,a,Z)\to(q\_0,aZ)}$
9. $\mathbf{(q\_f,b,Z)\to(q\_0,AAZ)}$

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