# Question
Title: Which computational model is used to analyse the runtime of matrix multiplication algorithms?
Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory reference to a model of computation, which is used to measure this complexity. In fact, I have found three possible answers, neither of which seems to me as absolutely satisfactory:

* Wikipedia says that the model used here is the Multitape Turing Machine. This does not seem to make much sense to me, since in the analysis of matrix multiplication, scalar multiplication is supposed to have a constant time complexity. This is not the case on Turing Machines.
* Some texts describe the complexity only vaguely as the number of arithmetic operations used. However, what *exactly* are arithmetic operations in this context? I suppose that addition, multiplication, and probably subtraction. But what about division, integer division, remainder, etc.? And what about bitwise operations - how do they fit into this setting?
* Finally, I have recently discovered an article, which uses the BSS machine as the model of computation. However, this also seems little bit strange to me, since for, e.g., integer matrices, it does not make much sense to me to disallow operations such as, e.g., integer division.

I would be grateful to anyone, who could help me to sort these things out.

# Answer
> 8 votes
Matrix multiplication algorithms are analyzed in terms of *arithmetic complexity*. The computation model is straight-line programs with instructions of the form $a \gets b \circ c$, where $\circ \in \\{ +,-,\times,\div \\}$, $a$ is a variable, and $b,c$ could be either variables, inputs or constants. Additionally, certain variables are distinguished as *outputs*. For example, here is how to multiply two $2\times 2$ matrices using the usual algorithm, with input matrices $a\_{ij},b\_{ij}$ and output matrix $c\_{ij}$:

$$ \begin{align\*} x\_{11} &\gets a\_{11} \times b\_{11} & y\_{11} &\gets a\_{12} \times b\_{21} & c\_{11} &\gets x\_{11} + y\_{11} \\ x\_{12} &\gets a\_{11} \times b\_{12} & y\_{12} &\gets a\_{12} \times b\_{22} & c\_{12} &\gets x\_{12} + y\_{12} \\ x\_{21} &\gets a\_{21} \times b\_{11} & y\_{21} &\gets a\_{22} \times b\_{21} & c\_{21} &\gets x\_{21} + y\_{21} \\ x\_{22} &\gets a\_{21} \times b\_{12} & y\_{22} &\gets a\_{22} \times b\_{22} & c\_{22} &\gets x\_{22} + y\_{22} \end{align\*} $$ The complexity measure is the number of lines in the program.

For matrix multiplication, one can prove a *normal form* for all algorithms. Every algorithm can be converted into an algorithm of the following form, at the cost of only a constant multiplicative increase in complexity:

1. Certain linear combinations $\alpha\_i$ of the input matrix $a\_{jk}$ are calculated.
2. Certain linear combinations $\beta\_i$ of the input matrix $b\_{jk}$ are calculated.
3. $\gamma\_i \to \alpha\_i \times \beta\_i$.
4. Each entry in the output matrix is a linear combination of $\gamma\_i$s.

This is known as *bilinear normal form*. In the matrix multiplication algorithm shown above, $x\_{jk},y\_{jk}$ function as the $\gamma\_i$, but in Strassen's algorithm the linear combinations are more interesting; they are the $M\_i$'s in Wikipedia's description.

Using a tensoring approach (i.e. recursively applying the same algorithm), similar to the asymptotic analysis of Strassen's algorithm, one can show that given such an algorithm for multiplying $n\times n$ matrix with $r$ products (i.e. $r$ variables $\gamma\_i$), then arbitrary $N\times N$ matrices can be multiplied in complexity $O(N^{\log\_n r})$; thus only the number of products matters asymptotically. In Strassen's algorithm, $n = 2$ and $r = 7$, and so the bound is $O(N^{\log\_2 7})$.

The problem of finding the minimal number of products needed to compute matrix multiplication can be phrased as finding the *rank* of a third-order tensor (a "matrix" with three indices rather than two), and this forms the connection to algebraic complexity theory. You can find more information in this book or these lecture notes (continued here).

---

The reason this model is used is twofold: first, it is very simple and amenable to analysis; second, it is closely related to the more common RAM model.

Straight-line programs can be implemented in the RAM model, and the complexity in both models is strongly related: arithmetic operations have unit cost in several variants of the model (for example, the RAM model with real numbers), and are otherwise related polynomially to the size of the numbers. In the case of modular matrix multiplication, therefore, arithmetic complexity provides an upper bound on complexity in the RAM model. In the case of integer or rational matrix multiplication, one can show that for bilinear algorithms resulting from tensorization, the size of the numbers doesn't grow too much, and so arithmetic complexity provides an upper bound for the RAM model, up to logarithmic factors.

It could a priori be the case that a RAM machine can pull some tricks that the arithmetic model is oblivious to. But often we want matrix multiplication algorithms to work for matrices over arbitrary fields (or even rings), and in that case uniform algorithm should only use the arithmetic operations specified by the model. So this model is a formalization of "field-independent" algorithms.

---
Tags: algorithm-analysis, runtime-analysis, matrices, machine-models
---


# Question
Title: Counterexample that B-A can be NOT context free
Given that `A` is a context free language and `B` is a regular language, `B-A` can be not context free as it is equal to `B ∩ A'`, and context free languages are not closed under complement. Could you give me a counterexample?

# Answer
Consider the languages

* B = { a*b*c* } -- an obviously regular language.
* A1 = { aibjc* | i \> j }
* A2 = { aibjc* | i \< j }
* A3 = { a*bicj | i \> j }
* A4 = { a*bicj | i \< j }
* A = A1 ∪ A2 ∪ A3 ∪ A4

The An langauges are all context-free, so their union is also context free, but the language B-A is the non-context free language { aibici }
> 4 votes

# Answer
Just because the CFLs aren't closed under complement doesn't mean that the complement of a CFL is *never* a CFL.

As a hint: Σ\* and ∅ are regular and therefore context-free.

Hope this helps!
> 3 votes

---
Tags: formal-languages
---


# Question
Title: A heuristic for finding a maximum disjoint set
**Background**

I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares.

This problem is NP-complete. Many papers suggest approximation algorithms (see Maximum Disjoint Set in Wikipedia), but I need an exact algorithm.

My current solution uses the following divide-and-conquer strategy:

* Calculate all horizontal and vertical lines that pass through corners of the candidate squares. Each such line separates the candidates into three groups: candidates that are entirely at one side of the line, candidates that are entirely at the other side of the line, and candidates that are intersected by the line. Now there are two cases:
    + *Easy Case*: There is a separator line $L$ that does not intersect any candidate square. Then, recursively calculate the maximum-disjoint-set among the squares on one side of $L$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$, and return the union of these two sets. The separator line guarantees that the union is still a disjoint set.
    + *Hard Case*: All separator lines intersect one or more candidate squares. Select one of the separator lines, $L$; suppose that $L$ intersects $k$ squares. Calculate all $2^k$ subsets of these intersected squares. For each subset $X$ that is in itself a disjoint set, calculate the maximum-disjoint-set recursively as in the Easy Case, under the assumption that $X$ is in the set. I.e., recursively calculate the maximum-disjoint-set among the squares on one side of $L$ that do not intersect $X$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$ that do not intersect $X$, and calculate the union of these two sets with $X$. Out of all $2^k$ unions, return the largest one.

**Question**

My question is: *What is the best way to select the separator line $L$*?

There are two conflicting considerations: On one hand, we want $L$ to intersect as few squares as possible, so that the power set is not too large. On the other hand, we want $L$ to separate the candidate squares to subsets of balanced size, preferrably equal size, so that the recursion ends as fast as possible. What is the best way to balance these conflicting considerations?

EDIT: **Additional details**

My current heuristic is to pick the separator line that intersects the least number of squares. This heuristic allows the algorithm to process input sets with up to $n=30$ candidates, in several seconds. The optimal solution in these cases has about 10 squares. In general, the number of squares in the optimal solution is near $2\cdot\sqrt{n}$.

When the input grows beyond 30 candidates, the running time becomes much slower (several minutes and more). My goal is to find a heuristic that will allow me to process larger sets of candidates.

# Answer
Rather than your approach, I suggest you formulate this as an integer linear program and feeding it to an off-the-shelf ILP solver. Alternatively, formulate it as a SAT problem and feed it to a SAT solver: you'll probably need to take the decision problem version, where you ask whether there exists a subset of $k$ non-overlapping squares, and then use binary search on $k$. Those would be the first approaches I would try, personally.

---

If you definitely want to try your approach based upon a "separating line", then I think the best way to answer your question is going to be to pick a representative set of problem instances, and try some different heuristics on them to see which seems to work best.

My intuition suggests that the best way to select the separator line may be to pick the line $L$ that intersects as few squares as possible, without worrying about how balanced the division is (though if there is a tie among multiple lines that each intersect the same number of squares, you could always use "how balanced the division is" as a tie-breaker). The reason is that you are getting an exponential multiplicative increase in the running time each time you enumerate all subsets of the squares that intersect the line $L$. I think your prime consideration is going to be keeping that blowup down. But that's just my intuition, and my intuition might be wrong. I think you need to do the experiment to find out empirically what works best.

If you do apply your separating line approach, you might consider using a branch-and-bound approach. Keep track of the best solution you've found so far (i.e., the largest set of non-overlapping squares you've been able to find so far); say that it is of size $s$ at any point in time. Now anytime your search tree enters a subtree where you can prove that all solutions below the subtree will have size $\le s$, there is no need to explore that subtree. For instance, if you have a line $L$ and a subset $X$ where you know that the size of $X$ plus the size of the largest sub collection of non-intersecting squares above $L$ plus the total number of squares below $L$ is $\le s$, then there is no need to recursively compute the largest sub collection of non-intersecting squares below $L$, which saves you one recursive call. But, if you use an off-the-shelf ILP solver, it will already implement these sort of branch-and-bound heuristics for you -- hence my advice to start by formulating this as an ILP problem and applying an off-the-shelf ILP solver.

---

Finally, the following paper apparently describes an $O(2^{\sqrt{n}})$ time algorithm to compute the exact solution to your problem. This is an improvement over the obvious algorithm that enumerates all possible subsets of squares, which takes $O(2^n)$ time.

An application of the planar separator theorem to counting problems. S.S. Ravi and H.B. Hunt III. Information Processing Letters, Volume 25, Issue 5, 10 July 1987, Pages 317–321. http://www.sciencedirect.com/science/article/pii/0020019087902067
> 5 votes

# Answer
Here is my attempt:

Assume that we have $n$ candidate squares, and we divide them such that that $m$ squares are in one side of the line, $k$ squares are intersected by the line, and $n-m-k$ are in the other side of the line. Then the run time is:

$$T(n) = 2^k(T(m)+T(n-m-k))$$

Assuming $k$ and $m$ are constants, and $m\<n-m-k$, the solution to this recurrence relation is approximately:

$$T(n) = O({2^k}^{\frac{n}{k+m}}) = O(2^{\frac{n}{1+m/k}})$$

To make the run time as small as possible, we should make $\frac{m}{k}$ as large as possible.

This calculation is *very* inaccurate, since $m$ and $k$ are not really the same in each step. However, surprisingly, it gives very good results in practice.

I experimented with random samples of about 30 candidate squares. In all cases I used the branch-and-bound heuristic suggested by D.W., which improved the statistics by 30-50%:

* When selecting a cut with a minimum number of intersected rects (minimum $k$), the number of recursive calls is between 15,000 and 110,000 with an average of about 40,000, and total time of about 600 ms.
* When selecting a cut with a maximally balanced partition (maximum $m$) - the number of recursive calls is between 400 and 1300 with an average of 700, and total time of about 16 ms.
* When selecting a cut with a maximum $m/k$ - the number of recursive calls was between 300 and 1100 with an average of 500, and total time of about 12 ms.

Selecting a cut with a maximum $m/k$ is 50-80 times faster than with minimum $k$, and about 20% faster than with maximum $m$.
> 3 votes

---
Tags: algorithms, computational-geometry, efficiency, heuristics
---


# Question
Title: Complexity of keeping track of $K$ smallest integers in a stream
I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is

* Suppose the $i$th number in the stream is $S\_i$.
* Keep a max heap of size $K$.
* If the heap contains fewer than $K$ elements, add $S\_i$ to the heap.
* Otherwise: if $S\_i$ is smaller than the maximum element in the heap (i.e., the root of the heap), replace the root of the heap with $S\_i$ and apply Max-Heapify to the heap; if $S\_i$ is greater than or equal to the max element, do nothing.

The problem now is to find the expected number of times the Max Heapify operation will be called, when the stream of integers is of length $R$ and each element of the stream is (iid) uniformly distributed on $\[1,N\]$.

If the stream were guaranteed to contain only distinct elements, then the answer is easy:

$$E\[X\] = E\[X\_1\] + E\[X\_2\] + \dots + E\[X\_R\],$$

where $X\_i$ is the random indicator variable for occurrence of the Max Heapify operation at the $i$th number in the stream. Now

$$E\[X\_i\] = \Pr\[\text{$S\_i$ is ranked $\le K$ among first $i$ elements}\] = \min(K/i, 1).$$

Hence,

$$E\[X\] = K + K/(K+1) + \cdots + K/R.$$

That case is relatively easy. But how do we handle the case where the elements are iid uniformly distributed?

\[This was actually a Google interview question.\]

# Answer
If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j \< K$ of the previous $i-1$ elements are smaller than $x$. This gives

$$E\[X\_i\] = \frac{1}{N^i} \sum\_{x=1}^N \sum\_{j=0}^{K-1} c\_{j,x},$$

where $c\_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$.

Now, to determine $c\_{j,x}$, note that there are $\binom{i-1}{j}$ possibilities for the positions of the smaller elements in the sequence. For each of the smaller elements there are $x-1$ possibilities for its value, while for the larger or equal elements there are $N-x+1$ possibilities. This yields
$c\_{j,x} = \binom{i-1}{j} (x-1)^j (N-x+1)^{i-1-j}$, and thus overall (after shifting $i$ and $x$ by $1$)

$$E\[X\] = \sum\_{i=0}^{R-1}\frac{1}{N^{i+1}} \sum\_{x=0}^{N-1} \sum\_{j=0}^{K-1} \binom{i}{j} x^j (N-x)^{i-j}.$$

Unfortunately, all my attempts at bringing this formula into a simpler/closed form have been unsuccessful.
> 5 votes

# Answer
It depends on the histogram of the elements. Consider for example the other extreme case, in which all the elements are the same. Instead of $K\log \tfrac{R}{K}$ (*not* $K+K\log \tfrac{R}{K}$ like you wrote) you get $0$. (The additive discrepancy of $K$ results from the fact that according to your description of the algorithm, in the first $K$ steps there is no heapifying.)
> 2 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, average-case
---


# Question
Title: Efficiently pick a largest set of non-intersecting line segments
Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting?

Brute force we would get $2^n$ sets to check where $n$ is the number of line segments, so that isn't viable. Anyone got a bright idea how the do this efficiently? I tried doing it this way: remove a line segment that intersects with the most other line segments, iterate until no line segments intersect anymore; but that didn't work.

---

Here is a "ready to help me" place, where you can test your solution; it visualizes the set of line segments.

To try it out, please implement your attempt in the following function on the linked site:

```
function showAnalysis() {
    debug("Just do it");
}

```

and then click on the top canvas. The fiddle generates randoms segments in the top canvas, and the bottom canvas is the place where an optimal subset will be displayed.

# Answer
> 2 votes
EDIT: Falk Hüffner gave a reduction in his comment to the question, the problem is in fact NP hard. What follows is pretty useless for that reason. I'll leave it up anyway so the answer doesn't look butchered.

---

This might be an NP-hard problem (as Teepeemm rightly pointed out, I did the reduction in the wrong direction, and I can't come up with one in the right direction), which would mean no one knows a subexponential algorithm. Brute force approach: check all sets whether some segments in them intersect, pick the largest one. This will cost you exponential time.

You can speed it up somewhat. Let `n` be the number of segments you have, then you can do a binary search like this: start out with checking whether there is a set with k1 `:= n/2` segments. If there is, check k2 `:= n*3/4`, if there isn't, check k2 `:= n*1/4`. Always remember all sets of the largest size for which you know that there exists something, because going up only supersets of those can work.

But to be completely honest, your best bet is to reduce this to SAT and use a SAT-solver. Anything you whip up yourself will pale in comparison to the finely tuned tools that SAT-solvers are nowadays. I don't know whether there is a SAT-solver you can easily use in Javascript though, you might have to use one on your server and let Javascript deal with the interpretation of results. Another option would be to look into the algrithms mentioned on the sites that @MvG linked to in his comment to your question.

---
Tags: algorithms, optimization, np-hard, efficiency
---


title: How to prove that $2^{n+3} = O(2^n)$?

text:
# Question
Title: How to prove that $2^{n+3} = O(2^n)$?
I am a little confused on how to prove/disprove Big O.

For the problem, $2^{n+3}= O(2^n)$, I did the following:

$$2^{n+3} \leq K \times 2^n$$

Set $K = 1$

$$2^{n+3} \leq 2^n$$

Test for large values of n (so I plugged in n = 100)

$2^{103} \leq 2^{100}$ --- which is false therefore Big O is disproven

Is this process correct?

# Answer
> 1 votes
Just, replace the constant $K = 2^3$, and you have to use this constant for your proof.

$$ 2^{n+3} = K\times 2^n$$

So, $O(2^{n+3}) = O(2^n)$.

---
Tags: asymptotics
---


title: Which of $e^n$ and $2n^2$ grows faster?

text:
# Question
Title: Which of $e^n$ and $2n^2$ grows faster?
How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.

# Answer
> 4 votes
Try plotting them. You can also notice that as $n$ increases by one, $e^n$ increases by a multiplicative factor of $e^{n+1}/e^n=e$, while $2n^2$ increases by a multiplicative factor of $\frac{2(n+1)^2}{2n^2} \longrightarrow 1$.

# Answer
> 2 votes
You can avoid $O(2n^2)$ by $O(n^2)$. On the other hand, you have:

$$ \lim\_{n\to\infty} \frac{n^2}{e^n} = \lim\_{n\to\infty} \frac{2n}{e^n} = \lim\_{n\to\infty} \frac{2}{e^n} = 0 $$ So, $\lim\_{n\to\infty} \frac{n^2}{e^n} = 0$ say us that $O(n^2) \subset O(e^n)$. Therefore, $O(2n^2) = O(n^2) \subset O(e^n)$.

---
Tags: asymptotics
---


# Question
Title: Does "standard" Dijkstra's algorithm work with bi-directional edges and zero cost edges?
I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder:

1. If my graph is bi-directional and I add each edge to my graph *twice* (once "forwards", once "backwards"), will the "standard" Dijkstra's algorithm work?
2. Is it ok that some of my edges are zero cost? (the rest are all positive - none are negative)

And finally, what is a Dijkstra "heap" algorithm? Is it the same as Dijkstra's algorithm using a PriorityQueue?

# Answer
Yes, both of these cases work. You can even have zero-cost loops.
> 2 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?
There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met:

1. For each $i \geq 0$, $x(y^i)z \in A$
2. $|y| \> 0$
3. $|xy| \leq p$

But if $i = 0$ then $|y|$ cannot be strictly greater than $0$. Isn't condition 1 contradicting condition 2? Isn't $y^0 = \varepsilon$?

# Answer
Sure, $y^0$ is $\epsilon$, but that does not make $|y|=0$.
Consider $y=\mathit{foo}$. Here, $|y|=|\mathit{foo}|=3$, yet $(\mathit{foo})^0=\epsilon$.
No contradiction – $y$ is unchanged.
> 5 votes

# Answer
The pumping lemma is effectively finding a loop in your DFA for you. You can think of the string $xy^iz$ as saying:

1. follow $x$ from the initial vertex,
2. now you are at the start of the loop, follow $y$ to go around the loop and return to the same spot.
3. now follow $z$ to an accept state.

Now, the condition \[2\] in your question says that the loop in point 2. of my explanation has to actually exist (i.e. have non-zero length). Condition \[1\] in your question says that since this is a loop you don't necessarily have to follow it (since it returns to the same spot) and can just follow $x$ to the start of the loop, follow the loop zero times (i.e. $y^0 = \epsilon$) and continue to follow $z$ to the accept state.
> 2 votes

# Answer
The above answers sums it up pretty good, but I wanted to add something from my understanding of this topic.

For the pumping lemma to apply you must have a substring $y$ within your string $s$ that can be *pumped*, but that requires that $y$ is effectively some string other than the empty string, or else you couldn't be able to pump it in the first place.

Recall that $y$ represents a loop inside the finite deterministic automaton that accepts the language, so if for your initial string $s$ you have $|y| = 0$ then there is no loop at all, which is not the same as avoiding the loop and going straight to the accept state (when $i=0$).

Maybe the order the conditions are given is misleading, because you first gotta check for conditions 2 and 3 in order to pump $y$, i.e. check condition 1.
> 1 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Why is the PageRank vector also the eigenvector of the web adjacency matrix?
From wikipedia:

> The PageRank values are the entries of the dominant eigenvector of the modified adjacency matrix. This makes PageRank a particularly elegant metric

Can anyone please elaborate on the connection between the eigenvector and the PR vector? Why are they related?

# Answer
> 4 votes
PageRank is the stationary probability (i.e. dominant eigenvector) of the following random walk: with probability 0.85, choose a random outgoing link; with probability 0.15, choose a random web page. The "modified adjacency matrix" that Wikipedia talks about is obtained from the actual adjacency matrix $A$ by computing $0.85 A + 0.15 J$, where $J$ is the all-ones matrix. See this talk (page 13).

---
Tags: graphs, search-algorithms
---


title: Error detection/correction algorithm

text:
# Question
Title: Error detection/correction algorithm
We have 2 stations that communicate with each other, but we need to detect (or even correct) when something is wrong.

We use 8 binary words: each consisting of 3 bits and to send it we code it as where is the complement of and is the even parity check bit of .

We need to find the capabilities of this code (up to how many can we detect and how many can we correct). BUT, a **proof** is required.

This is how far I've reached so far:

First we find the hamming distance: If changes then changes, also changes. So we have a hamming distance of 3.

This means that we can detect two bit errors **or** correct a single error.

Can you help me write the proof for that?

(also the tags may need some refinement - comments about the downvote are welcome)

# Answer
> 1 votes
Consider any two codewords based on $b\_2b\_1b\_0$ and $c\_2c\_1c\_0$. The Hamming distance between the two codewords is at least twice the Hamming distance between $b\_2b\_1b\_0$ and $c\_2c\_1c\_0$ (why?). Furthermore, if the Hamming distance between $b\_2b\_1b\_0$ and $c\_2c\_1c\_0$ is exactly $1$, then your argument shows that the Hamming distance between the codewords is $3$. We can conclude that the Hamming distance is always at least $3$.

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Sequential numbers to unique-looking numbers
I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common.

Basically, I've got members signing up for our website, and each one is assigned a normal sequential ID (a MySQL auto\_increment ID), i.e. `1`, `2`, `3`, ....

The client wants these users to have a "member number" -- something around 8 digits long. It doesn't matter if the algorithm is predictable, I just want to generate an 8-digit number that I know won't repeat and isn't *totally* obvious that it's sequential, e.g. I don't want to use `10000001`, `10000002`, `10000003`....

Is there a simple algorithm for generating "member numbers" in a case like this? Like I said, I don't care if it's reverse-engineerable, just as long as I know it will always be unique.

For instance, I considered just taking a hash and truncating it, e.g. `md5(1)`, `md5(2)`, md5(3)\` in base 10 and taking the first 8 characters -- but there's always a chance of conflict, where two IDs produce a similar hash.

Any thoughts?

# Answer
Not sure what you mean by "totally obvious". Technically, every permutation of $\\{1,\dots,10^8\\}$ would work here. You can randomly generate such a permutation, store it in an array, and use this array as an index.

If you want a specific example, which may look at first glance non-sequential, take some big number $p$ such that $\gcd(p,10^8)=1$ (e.g. $p= 19683$), then the id of user $i$ will be $i \cdot p \pmod{10^8}$. This is guaranteed to be unique for each user (up to $10^8$ users).

It may look random only at a glance, but anyone who takes enough time can figure out this is not random.
> 3 votes

---
Tags: hash
---


# Question
Title: How strong is equivalence of lambda expressions?
Consider two lambda expressions $\mu$, $\nu$ representing computable functions $f\_{\mu,\nu}:\mathbb{N} \rightarrow \mathbb{N}$. If $\mu$ and $\nu$ are equivalent under the combination of $\beta$-reductions, $\alpha$-conversions and $\eta$-conversions then $f\_\mu=f\_\nu$.

> Under what conditions does the converse hold? In particular, if it is possible to prove in Peano arithmetic that $f\_\mu=f\_\nu$, does it follow $\mu$, $\nu$ are equivalent in the above sense?

# Answer
In general, there is always an infinite number of "computationally different" functions that are extensionally equal: take for instance the "$3n+1$-function" $g$, and for any function $f$ define $G\_f$ to be:

$$ G\_f(n)=\begin{cases} f(n) & \mbox{if }g(n)\mbox{ cycles at }1 \\ 0 & \mbox{otherwise}\end{cases}$$

This function is (probably) *extensionally* equal to $f$ for every $f$, but this is (possibly) not provable in $\mathrm{PA}$, or indeed in the weak framework of $\beta\eta\alpha$-conversion.

More pragmatically, the identity function $\lambda x.x$ and the "stupid identity" $$ \lambda n.n\ (\lambda x\ f.x)\ (\lambda m\ x\ f.f(m\ x \ f))$$

Denote the same function $\mathrm{id}:\mathbb{N}\rightarrow \mathbb{N}$, under the usual church encoding, but are not $\beta\eta$-equal, as can easily be seen (they are both in normal form).
> 3 votes

# Answer
It is false, because of lot of different lambda terms (not reducible to each other) define the same partial function $\mathbb N\to\mathbb N$ with empty domain.
> 0 votes

---
Tags: logic, lambda-calculus
---


# Question
Title: Runtime analysis of a recursive algorithm with a tricky amount of work per recursive call
I want to analyze the runtime of this algorithm:

```
int fun (int arr[], int n) {
    int result = 1;
    int i, j;

    if (n == 1)
        return 1;

    else {
            result = fun(arr, 2n/3);
            for (i = 1; i <= sqrt(n); i=i*2);
                for (j=0; j<sqrt(n)/i; j++)
                    result += arr[j];

            return result;
    }
}

```

I can see that the runtime recurrence should be something like

$\qquad\displaystyle T(n) = T\left(\frac{2n}{3}\right) + \Theta(X)$

where $X$ is the time of the extra operations per recursion.

I can also see that the extra operations are:

$\qquad\begin{align\*} \sum\_{i=1}^{\log(\sqrt{n})} \sum\_{j=0}^{\frac{\sqrt{n}}{i}}1 &= \sum\_{i=1}^{\log(\sqrt{n})}\frac{\sqrt{n}}{i} \\ &= \sqrt{n} \cdot \sum\_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \\ &= \sqrt{n}\cdot \log(\log(\sqrt{n})) \end{align\*}$

So all in all:

$\qquad\begin{align\*} T(1) &= 1 \\ T(n) &= T\left(\frac{2n}{3}\right) + \sqrt{n}\cdot \log(\log(\sqrt{n})) \end{align\*}$

But I could not continue from here to solve this recursion.

# Answer
I can see three issues with what you have.

1. There are some inaccurracies in your sums. The outer one needs rounding of the upper boundary, the inner needs a $-1$.
2. $\displaystyle \sum\_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \neq \log(\log(\sqrt{n}))$

The true value of the sum is $H\_{\log(\sqrt{n})}$ (will change slightly if you fix the sums). It's true that the difference vanishes in $\Theta$ if you go that route, but better not write equality where it does not hold.
3. You dropped the recursion at the end! You should have

$\qquad \displaystyle T(n) = T(2/3 \cdot n) + \dots$

From there, unfold the recurrence:

$\qquad\begin{align\*} T(n) &= T(2/3 \cdot n) + f(n) \\ &= T(4/9 \cdot n) + f(2/3 \cdot n) + f(n) \\ &\dots \end{align\*}$

Spot a pattern, guess the solution and prove it correct by induction! This part is well covered by our reference question in case you have trouble.
> 1 votes

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


title: Is this grammar LL(1)?

text:
# Question
Title: Is this grammar LL(1)?
Consider following grammar:

$$X\to Yc|ZY$$

$$Y\to ab|cX$$

$$Z\to d|\epsilon$$

Can this be converted to LL(1)?

Cleary, its not LL(1) because of First/First conflict at first production. Can anyone suggest something to make it LL1?

# Answer
I would do it the following way:

First remove the Z production:

```
X-> Yc | dY | Y

```

and leave the others intact. Now you still have the First/First conflict, but you don't need to descent to the epsilon.

Next step, introduce a new symbol Y' for deciding wether to read a c or not.

```
 X-> YY' | dY
 Y' -> c | epsilon
 Y -> ab|cX

```

now you have a first/follow conflict. How to solve that:

Let's take a look at the produced language(Assuming X is the Start symbol) and transform the grammar:

L(G) = abc or c^n ab d ab..

X-\> cX| ab |abY |dX

this should be LL(1).
> 1 votes

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


# Question
Title: What's the dual problem of stable matching?
So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?

# Answer
From http://kuznets.fas.harvard.edu/~aroth/papers/1993\_MOR\_StableMatchingsOptimal.pdf :

> Shapley and Shubik (1972) observed that \[the dual\] formulates the problem of finding payoff vectors in the core of the above assignment game.

The assignment game described is that two agents who choose to match get a total "value" equal to the edge weight between them, and they can split this value between them in some way; these are the "payoffs".

It might be nice for future readers if you put the LP and dual in your question....
> 1 votes

---
Tags: linear-programming, matching, duality
---


# Question
Title: Can parameters be contra- or covariant in Python?
I've just now studied about covariance and contravariance in static languages (more specifically C#). This concept is rather clear to me, however I'm in doubt on how this applies to dynamic languages like Python.

Since Python is duck typed (or structural typed) it seems to me that there is not even a notion of variance and covariance in this language?

If I'm not mistaking, things like contravariance and covariance are checked at compile-time in a language like C#, this is possible because a variable has a type, and the value it is bound to has a type as well and these have to match or be co(ntra)- or invariant. However, since there is no notion of typing at compile-time with a language like Python I don't know how to apply this concept.

Any thoughts?

My thoughts: The concept of covariance means that whenever we expect a type of X, any subclass of X will do as well. So, in Python this doesn't come up, because there is no type check to do this. The only check that happens is wether or not the object has the necessary implementations by means of methods and attributes.

In C# for example where we have a method:

```
void DoStuff(Person p)
{
    p.Dance();
};

```

We could very well call this method with an instance of a Student (if this is a subclass of Person).

Now, in Python, we could very well pass in a Bird object that would not be related to Person in any way in the inheritance hierarchy(except it would also inherit from object), as long as this bird implements `Dance()`.

This is why I'm asking about this concept. From what I understand Python is covariant and contravariant in.. well, everything?

# Answer
Here are some general thoughts on how contra- and co-variance issues affect programming in dynamically typed languages.

**Covariance**: If B is a subtype of B' then functions A $\rightarrow$ B form a subtype of A $\rightarrow$ B'.

**Contrvariance**: If A is a subtype of A' then functions A' $\rightarrow$ B form a subtype of A $\rightarrow$ B.

For example, if *Auto* is a subtype of *Vehicle*, then the contravariance rule says that a function that takes a *Vehicle* argument can be regarded as a function taking an *Auto* argument (because the *Auto* can be regarded as a *Vehicle*). However, a function taking an *Auto* argument cannot be treated as a function that takes a *Vehicle* argument. If you do, then sooner or later, you might pass it a non-Auto argument, say a *Bicycle*, and you would get a run-time error.

Whether the language is statically typed or dynamically typed makes little difference to the logic you use to design programs. If the language is statically typed, the type checker would complain about the design flaws in your program that show up as type-mismatches. If it is dynamically typed, you are likely to get a run-time type error such as "message not understood". That is if you are lucky. If you are unlucky, the problem would go unnoticed during testing, and the program would crash in the hands of the end-user.
> 6 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: How to find a Deterministic PDA for an intersection of languages
There are two languages,

$\qquad L\_1 = \\{w\in\\{a,b\\}^\*: N\_a\leq N\_b\\}$ and
$\qquad L\_2=\\{w\in\\{a,b\\}^\*: N\_b\leq 2N\_a\\}$

where $N\_a$ means the number of occurrences of $a$ in the string $w$. Same for $N\_b$.

I've proved that $L\_1$ has a DPDA (hope this is right).

Now I want to know whether $L=L\_1\cap L\_2$ has a DPDA or not.

I applied the Pumping lemma but it seems like there is no contradiction. I tried to draw the DPDA but failed. Maybe $L$ has a nondeterministic PDA but not a DPDA. However I cannot prove this.

Could anyone give me some hints?

# Answer
Your conjecture is right. $L$ is context-free, but not deterministic context-free.

To see that it is context-free, take a repaired verion of the grammar from @Raphael's comment: $S \rightarrow aSbS ~|~ bSaS ~|~ aSbSbS ~|~ bSaSbS ~|~ bSbSaS ~|~ \epsilon$.

Now, assume there is a DPDA $A$ that accepts $L$, and consider words of the form $b^na^m$.

Since the set of suffixes that complete $b^n$ to a word in $L$ differs for each $n$ and $A$ is a DPDA, we can conclude that after reading $b^n$, $n$ larger than some threshold $n\_0$, $A$ will be in a state $q\_n$ with stack contents of the form $\gamma' \gamma^{i\_n} \gamma\_n$ and the size of all $\gamma\_n$ is bounded by a constant.

Now we group the numbers $n\>n\_0$ into equivalence classes, based on $q\_n$ and $\gamma\_n$. Since there are only finitely many equivalence classes, at least one of the equivalence classes wil contain infinitely many values. In the following, we only consider values from this equivalence class $C$.

Now assume, there is $n\_1 \in C$, so that when reading $a^{n\_1}$ $A$ will go from stack $\gamma'\gamma^{i\_{n\_1}}\gamma\_{n}$ and state $q\_n$ to stack $\gamma'\gamma\gamma\_{n\_1}'$ and state $q\_{n\_1}'$ without looking at $\gamma'$. Since $b^{n\_1}a^{n\_1}\in L$, $q\_{n\_1}$ is accepting. However, since $A$ did not look at $\gamma'$, it will perform the same computation, if it starts reading $a^{n\_1}$ with stack contents $\gamma'\gamma^{i\_{n\_2}}\gamma\_n$, $i\_{n\_2}\>i\_{n\_1}$. By the infiniteness of $C$, it contains $n\_2\>n\_1$ with $i\_{n\_2}\>i\_{n\_1}$. Thus $A$ would accept $b^{n\_2}a^{n\_1} \notin L$. So, such an $n\_1$ can not be in $C$.

From the previous observation, we can conclude that for each $n\_i\in C$ there is a value $n\_i'\<n\_i$, so that after reading $b^{n\_i}a^{n\_i'}$, $A$ is in a state $q\_{n\_i}'$ and $A$'s stack contains $\gamma'$. Since $C$ contains infinitely many values $n\_i$, we can find $n\_1\<n\_2\in C$ so that $q\_{n\_1}' = q\_{n\_2}'$. Now we distinguish 2 cases:

* If $n\_1-n\_1' \> n\_2-n\_2'$, $b^{n\_1}a^{n\_1'+(n\_2-n\_2')} \notin L$, but since $A$ can not distinguish, if it has read $b^{n\_1}a^{n\_1'}$ or $b^{n\_2}a^{n\_2'}$ and $b^{n\_2}a^{n\_2'+(n\_2-n\_2')} \in L$, $A$ can not handle both words correctly.
* If $n\_1-n\_1' \leq n\_2-n\_2'$, $b^{n\_1}a^{n\_1'+(n\_2-n\_2')+n\_2} \notin L$, while $b^{n\_2}a^{n\_2'+(n\_2-n\_2')+n\_2} \in L$, and as in the other case $A$ can not distinguish them.

Thus, such an $A$ can not exist.
> 3 votes

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


# Question
Title: How is a type system related to a progam?
In another question about Lambda Calculus, Andrej Bauer made the comment:

> Lambda calculi of various forms are formal systems. They consist of abstract syntax (for terms and for types, if present), judgments (typing judgments and equations), and rules of inference. They are not programming languages (unless we prescribe operational semantics) and neither is it the case that a type system equals a program that checks types. So I think this whole question is a bit misdirected, still. Of course, an important aspect of a type system is how to implement it on a computer, which brings in questions about algorithms, etc. But a priori, the type system has none of that.

I understand most of this, but I cannot wrap a logical understanding around:

> neither is it the case that a type system equals a program that checks types.

My understanding of a type system is that it is a set of rules in a formal system used to determine if a type is valid in a context and that those rules, via implementation, are used to establish the validity of a use of a type in a context in a programming language.

However the statement has me thinking there is no connection, or that there is more meaning to the statement but I don't see the details to separate a type system from a program or make a logical connection between the two so that the statement makes sense.

What is the relation between a type system and a program?

# Answer
Your understanding that a type system is a set of rules in a formal system is right, but the rest is a bit garbled. The purpose of the type system is to delineate which terms or programs make sense. It is up to the language designer to decide which programs "make sense". There is no claim that the language specifies all programs that make sense. When somebody proposes a new type system, they are saying, "here are more programs that make sense and our type system captures them."

Andrej is saying one shouldn't equate the type system with the type checker (which is a program).

There is nothing too deep about it. Merely that the type system, i.e., the set of rules, stand independently of any particular implementation. One could even devise type systems that are undecidable, i.e., no possible type checking program exists. Admittedly such type systems may not be of much practical use, but nobody denies that they are type systems in the first place!
> 3 votes

# Answer
The relation between a type system and a program: A type system determines which programs are well-typed.

If that's not the answer you were looking for, you'll need to do a better job of posing the precise question that you want answered.
> 0 votes

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


# Question
Title: Are references of any use without updating?
Almost all type-theoretical treatments of references that I've studied introduce references as accompanied with at least three operations (sometimes including the fourth):

1. Construction (allocation): $ \text{ref } e $
2. Elimination (dereferencing): $ !e $
3. Updating: $ e\_1 := e\_2 $
4. (not as common) Destruction (deallocation): $ \text{free } e $

My question is this: Would references be of any use without updating (construct #3 above)? If so, what would be a common use? Does the ability to use updates with references lend any more "power" to a language? You can answer assuming either the presence or absence of construct #4 above; if it affects your answer, please explain how.

# Answer
> 3 votes
References are useful even if you don't update the object, since copying objects takes memory and time. When passing a reference, only a pointer is passed. But suppose that you were passing a string - it could take far longer to copy the entire string. This is why language like C++ support *constant references*, which are references that cannot be updated.

# Answer
> 2 votes
Another thought, it's very easy to implement parametric polymorphism if all objects are boxed. Indeed that's how data in Haskell, \*ML, and most other languages are stored.

Sure the operations are not explicit, but

```
case Just 1 {- Allocation -} of
  Just x {- dereferencing/fetching -} -> x + 1

```

and then garbage collection ~~ deallocation.

This is important since if things are really pointers, they can be treated as all having the same size on the stack.

It also has the benefit of simplifying optimizations you'd expect like sharing which fall out almost naturally of having data be pointers under the covers.

# Answer
> 1 votes
For a new object to be useful, it must be possible to keep the reference at least long enough to dereference it once. In many cases, that will require some means of copying the return from the object-construction method to the input parameter of the dereferencing method. There are a number of situations in which objects could be useful even if no other means of copying the reference were possible. Indeed, there are a number of situations where objects would be made *more* useful if the system could guarantee that particular object references were unique (meaning that no other reference could possibly identify the same object). Code which encapsulates state by holding the only reference to a mutable object may modify the state encapsulated by the reference by modifying the object identified thereby. If other references to the same object might exist for the purpose of encapsulating its state, however, changing the state encapsulated by a reference without changing the state encapsulated by those other references would require constructing a new object, modifying it, and holding a reference to that. When the former style of update is possible, it's often more efficient than the latter. Unfortunately, the only way to know it's safe is to know that one holds the only reference to the object in question--an invariant which many languages provide little if any help in enforcing.

# Answer
> 1 votes
I think there is a confusion between two separate notions of "reference".

When C or C++ talk about "references" in the sense of call-by-reference, they are talking about pointers to data objects.

When ML or Glasgow Haskell talk about "references", they are talking about mutable cells.

These are two completely different concepts, but the same terminology is used. There is *absolutely no connection* between the two concepts.

I personally prefer the C/C++ sense of "reference", which was originally introduced by Tony Hoare in Algol W. The ML terminology comes from Algol 68, designed by a group of European Computer Scientists with perhaps a questionable grasp of the English language. They should have just called them "mutable cells" instead of "references". Whenever you read the term "reference" in a type theory paper, best to translate it mentally as "mutable cell". That is what they are.

---
Tags: programming-languages, type-theory
---


# Question
Title: Is Wadler's 'Theorems for Free' as general as Design By Contract for establishing correctness?
Philip Wadler has written a brilliant paper called 'Theorems for Free'. The big idea is that you can use types to reason about your program, and even prove simple theorems about your program.

We see these ideas about types applied in the Haskell language.

At very roughly the same time period - we have an idea from Betrand Meyer called 'Design By Contract'\- which is most notably implemented in the Eiffel Language. This has the following features:

* routine preconditions
* routine postconditions
* class invariants
* check instructions (like assert)
* loop invariants

The idea behind Design by Contract is *software designers should define formal, precise and verifiable interface specifications for software components, which extend the ordinary definition of abstract data types with preconditions, postconditions and invariants.*

Now many claim that using 'Types' in your programs leads to 'more correct programs' (via the Howard Curry Correspondence). From what I can see - even the most advanced use of Dependent Typing in Idris and Scala is limited to Sum Types and list lengths (correct me if I'm wrong).

By contrast - the power of 'Design By Contract' in establishing the correctness of my program is more general and more powerful. (Albeit not necessarily at compile-time - but at test time). I can for example establish in my banking program that all deposits are positive, and all reported account balances are positive.

The point being - types have a fascinating future of possibilities, and are enormously powerful and compile time - but right now their practical application seems limited.

My question is: **is design by contract of more general application than using theorems from types to reason about the correctness of my program at present?** (Or are we just talking about two different things)

# Answer
> 3 votes
"Theorems for free" are so-called because they follow from the type of the program, *without* looking at the the program code!

"Contracts" are clearly *not* free theorems, because they depend on the *code* of the program, not merely the type.

However, the connection you do want to make is between types and specifications. Specifications are in a way "more detailed" types. Or, state the other way, types are more basic specifications. Martin-Lof type theory is precisely about fusing the two ideas into one.

# Answer
> 1 votes
The power of "theorems for free" depends upon the type system you choose to use. But as it is typically used, yes, "design by contract" is more expressive than "theorems for free": "design by contract" lets you specify some properties that cannot easily be proven using the "theorems for free" approach. Of course that does not mean that the "theorems for free" idea is useless or uninteresting.

I think maybe you are thinking about this in not quite the right way. It sounds almost like you are looking for a silver bullet or The One True Path to program correctness. Personally, I doubt that there will be any one-size-fits-all answer that is a perfect solution. Instead, I suggest that you focus more on understanding the space of available techniques and getting a better grip on their strengths and weaknesses -- I think you'll find that more informative than trying to set up a "gorilla vs shark" dichotomy ("theorems for free vs design by contract -- in a fight between the two, who would win?").

---
Tags: type-theory, curry-howard
---


# Question
Title: Calculating Floating point Operations Per Second(FLOPS) and Integer Operations Per Second(IOPS)
I am trying to learn some basic benchmarking. I have a loop in my Java program like,

```
float a=6.5f;
int b=3;
for(long j=0; j<999999999; j++){
       var = a*b+(a/b);
    }//end of for

```

My processor takes around 0.431635 second to process this. How would I calculate processor speed in terms of Flops(Floating point Operations Per Second) and Iops(Integer Operations Per Second)? Can you provide explanations with some steps?

PS:I have already asked this question in StackExchange but did not get any answer.

# Answer
It really depends on the optimizer. If you compile it with optimization, it might get rid of the loop, and then it will take rather less than 0.431635 seconds. Otherwise, it seems like you have four to five floating point instructions per iteration (including int to float conversion, once or twice, depending on the optimizer), so $4\cdot10^9$ or $5\cdot10^9$ in total. Divide this by 0.431635 to get your FLOPS, which will be around $10^{10}$, or 10 GFLOPS.
> 2 votes

# Answer
Our approach depends somewhat on which floating point operations we will be counting. I think it makes sense to include additions, multiplications, divisions, and casts. We will count each as one floating point operation.

In each loop, we have one add, one multiply, one divide, and two casts. (Perhaps the casting will be optimized--I'll assume not.) So each loop has $5$ floating point operations. The loop executes $999999999$ times, so we are performing $5\*999999999$ floating point operations.

Since the program takes $0.431635$ seconds to execute, we have

$$\frac{\frac{5 flop}{iteration} * 999999999 iterations}{0.431635s} = 11583861352.8 \frac{flop}{s} = 11.58 \frac{Gflop}{s}$$
> 2 votes

# Answer
For C, Bentley's "Programming pearls" discusses some pitfalls and gives an (oldish) program to measure costs of several operations. For Java and other JITed languages it's more of a challenge, as the first run of the operation will get it compiled to native code and run that way.

In general, the only really relevant benchmark is running your program with a set of representative data and measure.

Grab a copy of Bentley's book (or start looking over it's webpage). You'll learn more about programming than you'd believe possible.
> 1 votes

---
Tags: benchmarking
---


title: Blum's speedup theorem in big-O format?

text:
# Question
Title: Blum's speedup theorem in big-O format?
Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?

# Answer
Blum's speedup theorem implies that for any computable function $f(n,T)$ there is a computable predicate $\Pi$ such that for every program $P\_1$ for $\Pi$ there is another program $P\_2$ for $\Pi$ whose running time satisfies $f(n,T(P\_2)) \leq T(P\_1)$. In particular, there exists a computable predicate $\Pi$ such that for every program $P\_1$ computing it there is another program $P\_2$ computing it and running in time $T(P\_2) = o(T(P\_1))$.

But the theorem is much stronger: for example, for some other predicate $\Pi$, the guarantee is $T(P\_2) = O(\log T(P\_1))$; and for another predicate $\Pi$, the guarantee is $T(P\_2) = O(T(P\_1)/n)$; and so on.
> 2 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: CPU bit, its cache line, the bus between memory and CPU, and its registers?
Should the size of its cache line, the width of bus between memory and CPU, and the size of its registers be all equal to the CPU bit?

Is CPU bit determined by the size of its cache line, the width of bus between memory and CPU, or the size of its registers, something else?

Thanks!

# Answer
The nominal bit width is typically the size of the general purpose registers (see the answer pointed to in Wandering Logic's comment for some of the details), so the width of *general purpose* registers would typically equal the nominal bit width. However, other internal storage might use a different size. (Perhaps the most common modern examples would be 32-bit processors with 64-bit floating-point registers and many architectures with 128-bit or larger SIMD registers.)

The size of a cache line is typically four or more times larger than the size of general purpose registers in order to reduce tag overhead, to exploit spatial locality, and to exploit higher burst bandwidth (even communicating with an on-chip L2 cache has per-request overhead, since the days of fast page DRAM \[and possibly before\] burst accesses have provided more bandwidth than random access).

(A processor with multiple levels of cache may choose different line sizes for the different levels. Having a smaller L1 cache line size increases the number of cache lines; when combined with prefetching this can reduce the number of cache misses by reducing internal fragmentation \[where only part of the cache line will be used while it is resident\]. With on-chip interfaces, the access overhead is lower \[on-chip wires are "cheaper" and lower latency means less buffering\], so smaller L1 cache lines are not as expensive as for a last level cache. An instruction cache may also choose to use a different line size than a data cache since code often has greater spatial locality.)

The width of a memory interface is often tied to the size of cache lines in the last level cache and the efficient burst length of the memory. E.g., a 64-bit DDR3 memory interface is suitable for 64-byte last level cache lines (DDR3 uses a burst length of 8). This makes efficient use of memory bandwidth. However, using a narrower interface may be attractive in some embedded systems where cost and power are more important than performance and using a wider interface may be attractive in some systems to increase per-access bandwidth or to support DRAM chip redundancy (with mechanisms like ChipKill) with commodity DRAMs which have limited width choice.

Since the width of memory modules is standardized and cache line sizes are not, cache lines have more flexibility in terms of size. It is not unusual for the line size of a last level cache to be twice the size of a single burst access to a standard memory module.

Note that this applies to a single memory interface with an on-chip memory controller and no buffer chips (like FB-DIMM and Intel's Scalable Memory Buffer). The width of an interface to an off-chip memory controller or buffer chip is less tied to DRAM behavior. With a buffer chip, the interface is usually narrower to reduce the cost of having more connections (pins or solder balls) on the processor. Since such interfaces are specialized, their width is more driven by the electrical characteristics of the connection and less by DRAM characteristics or cache line size.

Also note, that a single processor chip can have multiple memory interfaces. These interfaces can also be bound together to provide greater per-access bandwidth (which may be attractive if last level cache lines are larger than a burst from a single interface).
> 3 votes

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


# Question
Title: Blum's speedup theorem showing unclassifiable complexity languages?
Do any of Blum's theorems prove that there exist decidable languages that are unclassifiable anywhere in the time hierarchy? In other words, asserting they (mentioned in the proofs) are computable within any time $O(f(n))$ for some time-constructable function $f(n)$ leads to a contradiction?

# Answer
> 2 votes
If a language is decidable then it is accepted by some Turing machine. The running time of that Turing machine is by definition time-constructible. So any computable function has a time-constructible upper bound by definition.

---
Tags: complexity-theory
---


# Question
Title: Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular
In general, how can we go about proving that union of two languages as non regular. In this case, the individual languages can be proved as non regular using pumping lemma. How can we apply pumping lemma to union of two languages ?

# Answer
Regular languages are closed under finite intersection, use that to your advantage. In this case, the reason the language isn't regular is because it has a $K = \\{a^n b^n | n \geq 0 \\}$ hidden inside it, pull it out using a regular language as a filter. More explicitly, notice that $K = L \cap a^\*b^\*$.
> 1 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Gap between the average length of a Huffman code and its entropy
Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and entropy is 0.72: (1- 0.72) = 0.28 -\> 28% worse than optimal.

If both “average length” and “entropy” are 1, the compression is optimal.

But what does it mean if the result is negative value?

Note: entropy : -(pr\*lg(pr)). Average length: probability\*number of bit

# Answer
> 3 votes
Shannon's source coding theorem shows that you cannot compress data more than its entropy, even if you encode chunks at a time. For the specific case of prefix-free codes (even uniquely-decodable codes), this follows from Kraft's inequality, which for a uniquely-decodable code with codeword lengths $\ell\_i$ states that $$ \sum\_i 2^{-\ell\_i} \leq 1, $$ and furthermore every code can be "improved" (by only decreasing its codeword lengths) so that equality holds. Suppose that the probability of the $i$th symbol is $p\_i$. The average codeword length is $E = \sum\_i p\_i \ell\_i$. We want to minimize $E$ given the constraint $\sum\_i 2^{-\ell\_i} = 1$, and furthermore $\ell\_i \geq 0$ are integers. Relaxing integrality, we can find the optimum using Lagrange multipliers: it satisfies $p\_i = \lambda 2^{-\ell\_i} \log\_e 2$ for some $\lambda$. Kraft's inequality forces the solution $2^{-\ell\_i} = p\_i$, and so $$ E \geq \sum\_i p\_i (-\log\_2 p\_i). $$ The right-hand side is simply the entropy of the distribution.

This argument immediately gives a criterion for when Huffman's code reaches the entropy: this happens if $-\log\_2 p\_i$ is always an integer, that is, all probabilities are of the form $1/2^k$ (for integer $k$).

---
Tags: information-theory
---


title: Quantum computer code cracking

text:
# Question
Title: Quantum computer code cracking
everyone! I don't know a whole lot about the fields of encryption or quantum computing, but I've read a lot of articles on the subjects and that is prescisley what caused this question. I've been a little scared about the whole NSA quantum computer that is build for the sole purpose of cracking encryption codes. I am fairly certain that they wouldn't use that power to get into random civilians' information, but if they did how hard would it be to block them out?

According to the numbers I've seen this computer could crack a typical encryption code within a little more than a week. And I recall seeing that a typical encryption key used in a consumer application is either 64 or 128 bits (or bytes?) long. I'm sorry if I'm getting these numbers wrong. Now, a week is an awful long time to to wait to crack a code (but wickedly better than with conventional computers), so they wouldn't waste their time on the password hash for your Facebook account. But say they did, wouldn't it be easy to overwhelm that system? According to mathematics the total number of time it would take to break the code would double with every bit longer the code is, and multiply by 256 with every byte. So, assuming a computer that could crack a 64bit code in up to a week, it would take 3.54^17 years to crack a 128 bit one.

Is this true? And if it is, then wouldn't this make the NSA computer useless? Because anyone that the angency would want to hack into could simply just increase the length of their encryption keys.

Thanks for any insight on the matter, and sorry if I have my facts wrong.

# Answer
> 2 votes
First of all, I seriously doubt that anyone would have a working quantum computer capable of doing anything useful in the foreseeable future (let's say 10 years). Even if someone does construct a "quantum computer", it will probably be quite useless, and it will take several years more until it can be used to, say, crack codes.

The quantum speedup for breaking symmetric encryption is quadratic: if a single decryption takes time $T$ and there are $N$ bits in the key (usually $N\geq128$ nowadays, unless you're using DES which has $N=56$), then a classical computer will take $2^NT\_{\text{classic}}$ time while a quantum computer will take $O(2^{N/2}T\_{\text{quantum}})$ time using Grover's algorithm (as far as I understand). In terms of real-world time, we expect $T\_{\text{quantum}}$ to be several orders of magnitude larger than $T\_{\text{classic}}$, at least at first. Decrypting $2^{64}$ blocks in "quantum speed" will take a lot of time, so quantum computing doesn't seem to break symmetric encryption, barring any weaknesses which enable one to use a smarter algorithm than the naive one.

The story is different for public-key encryption, though again, quantum computers capable of doing anything interesting are still far into the future. Shor's algorithm can be used to factor integers, thus breaking RSA. The algorithm also applies for the discrete log problem, even on elliptic curves. This is problematic for other public-key cryptosystems. You can check out this survey for some quantum-resistant protocols.

# Answer
> 1 votes
working QM computers with superior performance over classical computers are nowhere near reality even for three-letter multibillion-dollar secret government agencies and probably wont be for many years (despite large sums of research funding spent over more than a decade). this relatively recent highly-researched paper by an expert in the field serves as a useful & very cold/harsh "reality check" in the area.

> This is a brief review of the experimental and theoretical quantum computing. The hopes for eventually building a useful quantum computer rely entirely on the so-called "threshold theorem". In turn, this theorem is based on a number of assumptions, treated as axioms, i.e. as being satisfied exactly. Since in reality this is not possible, the prospects of scalable quantum computing will remain uncertain until the required precision, with which these assumptions should be approached, is established. Some related sociological aspects are also discussed. .

---
Tags: quantum-computing
---


title: Does reachability belong to P?

text:
# Question
Title: Does reachability belong to P?
Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?

Is it possible to write a polynomial time algorithm for it?

I asked this question on mathematics and got no answer by far.

# Answer
Although you already know from the other answers that the question is solvable in polynomial time, I thought I would expand on the computational complexity of reachability since you used complexity terminology in your question.

Reachability (or st-connectivity) in digraphs is the prototypical $NL$-complete problem where $NL$ stands for non-deterministic log space and we use deterministic log-space reductions (although I think it remains complete for $NC^1$ reductions, too).

* To see why it is in $NL$, notice that you can guess a next vertex at every step and verify that it is connected to the previous vertex. A series of correct guesses exists if and only if there is a path from $s$ to $t$.
* To see why is $NL$-hard, notice that the behavior of a non-deterministic Turing machine can be represented by a configuration graph. The nondeterministic machine accepts only if there exists a path from the start configuration to an accept configuration, and if the machine only uses $S(n)$ tape entries then the configuration graph is of size $O(|\Gamma|^{S(n)})$ where $\Gamma$ is the tape alphabet. If $S(n)$ is logarithmic, then the resulting graph is of polynomial size and the result follows.

But I don't have access to a non-deterministic machine, so why should I care? Well, we know lots of things about $NL$; one of those is that is in $P$, which you know from the other answers. However, here are tighter facts that can be useful:

* From Savitch's theorem we know that $NL \subseteq \text{DSPACE}((\log n)^2)$: even on a deterministic machine you don't need that much space to solve the question.
* We know that $NL \subseteq NC^2$: this means that in the circuit model, your question can be solved by a polynomial sized circuit of depth $O((\log n)^2)$. In a more "heuristic" sense, this means that the problem is parallelizable since Nick's Class captures the idea of quick solutions on a parallel computer.
* We know that $NL \subseteq \text{LOGCFL}$ which means that it is not harder (up to log-space reductions) than membership checking in context-free languages which can be a good source of intuition.

Finally, the directed nature of the graph is essential. If the graph is undirected then we believe the question is significantly easier. In particular, undirected st-connectivity is complete for $L$ (deterministic log space) under first-order reductions (Reingold 2004; pdf).
> 6 votes

# Answer
Yes, this problem is solveable in linear time, $O(|V|+|E|)$ to be precise.

The two classic solutions to this are Breadth-First search and Depth-First search.

The algorithms basically look like this:

```
current = v
while (current has an edge to an unmarked vertex)
    if current == w
        return true
    mark current as visited
    for each u where (v,u) is in E
        add u to the Open List
    current = a vertex from the Open List
return false

```

BFS uses a queue as the open list, adding to the back and taking from the front. DFS uses a stack. In any implementation like this, each node and each edge are visited at most once, so the algorithm runs in linear time.
> 5 votes

# Answer
Yes, it is in P.

The natural algorithm for is very simple, so simple it doesn't really serve as a learning experience to state it here (it's readily available in almost any text or on the web).

To put you on the right path:

1. What algorithms do you know for exploring a graph?
2. If you were at the start vertex $v$, what's the obvious way of trying to find $w$?
> 3 votes

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


# Question
Title: Can reversing the final and non-final states of a DFA produce the complement of the original language?
Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of the language that was accepted by the original automata?

What if we talk about a Non deterministic finite automata instead of a DFA?

# Answer
> 1 votes
In DFAs, the path taken in the automaton are deterministic and reach one specific state, so all the strings in the language reach one accepted state and all the other strings on this alphabet reach non-accepting states. Switching the accepting and non-accepting path is equivalent to saying "accept every string that doesn't reach an accepting state in the original automaton, don't accept any string that reach an accepting state in the original automaton", in short, "Not in the language L of the original automaton", which is the complement of L.

In NFAs, it is quite easy to find contradiction to show that this statement is incorrect.

Consider the following 2-state NFA with the alphabet {a, b}:

```
state 1 (starting state, accepting state):
  input a -> go to state 1
  input b -> go to state 2

state 2:
  input a -> go to state 1 and 2
  input b -> go to state 2

```

The string "aaba" is accepted by this automaton. If we switch the accepting states, this string is still accepted by the automaton, and thus the two languages can't be the complement of each other.

---
Tags: formal-languages, automata, finite-automata
---


title: How to name documents in windows?

text:
# Question
Title: How to name documents in windows?
What is the best way to name documents and folders in windows? Im thinging about maybe there will be some conflict in some programs? Or when searching in terminal

This\_Is\_Best.doc

ThisIsBest.doc

This Is Best.doc

# Answer
u can try: http://msdn.microsoft.com/en-us/library/aa365247(VS.85).aspx

i hope this'll help.
> 0 votes

---
Tags: filesystems
---


# Question
Title: Can a DFA have two symbols on one arrow?
I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q\_0$ and $q\_1$, can I have one arrow from $q\_0$ to $q\_1$ with both $a$ and $b$?

This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).

# Answer
> 6 votes
The transition graph (as a drawing) is merely a representation of an Automaton, which is a well-defined model.

Formally, an DFA is a tuple $(Q,\Sigma,\delta,q\_0,F)$, where the "type" of the transition function is $\delta:Q\times \Sigma\to Q$.

Thus, if you have $\delta(q\_0,a)=\delta(q\_0,b)=q\_1$, that's fine. In the graphic representation, you will either have two arrows from $q\_0$ to $q\_1$, labeled $a$ and $b$, or you can just put both letters on the same arrow, it's not a formal thing anyway.

# Answer
> -1 votes
As long as the starting and ending of respective states are same you can add as many symbols.

---
Tags: terminology, automata, finite-automata
---


# Question
Title: Help in understanding exactly how lattices used as one way functions for hashing
(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers and videos in an attempt to build my understanding of the subject, but due to the intensely technical manner in which information on the subject is presented, I have not been able to answer many questions in my mind. Due to the structure of my long distance course I have no access to professors or extensive libraries so my question is one which merely seeks to increase my understanding, please bear with me.

Thus far I have understood that: \- Lattices are a collection of regularly ordered points in euclidean space (its terms like this which have caused me to be searching for answers for days)

* A lattice may be defined through n vectors called a basis where n = the dimension (for now I am working in dimension 2), and any other basis can be found by applying positive or negative multiples of each vector in the basis to another vector in the basis
* Defining a lattice L1 as a set of points allows one to multiply the whole set by some co-efficient which will essentially transform it into a new lattice L2
* The determinant of the vectors of the basis essentially tells us the volume (area in 2 dimensions) of the parallelpiped which will be repeated to form the lattice, the lattice points being the vertices.

Having said this, I am now stuck in understanding how I move all of this to cryptography. I am on a question which asks me to compute the output for 3 inputs to a function:

'We will see that q-ary lattices give provably collision-resistent hashing. We choose integers q; a and b. Our hash function (presented by Mikl´os Ajtai in a breakthrough paper in 1996) is a 2-variable function: h(x, y) = ax + by mod q. (a) For q = 5; a = 14; b = 13; compute h(17, 8), h(21, 16) and h((17, 8) - (21, 16))'

Having found the answers, h(17, 8) = 14\*17 + 13\*8 = 342 mod 5 = 2; h(21, 16) = 14\*21 + 13\*16 = 502 mod 5 = 2; h((17, 8)-(21, 16)) -\> (h(-4, -8) = 14\*-4 + 13\*-8 = 160 mod 5 = 0

I believe this means that with the first two points the lattice has been moved by some multiple of 5 plus two, which has displaced it by two and thus formed a new lattice. While in the last case, the lattice has been moved by a multiple of its determinant and thus is the same lattice.

However, I just cannot understand the link to hashing. In an application would the points be the cleartext and the 'answer modulo 5' the output of the hash function? If so would'nt there be too many collisions as we have already seen two examples of which give the answer 2? How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing? Are q-ary lattices only an attempt to store the basic pattern needed to reproduce the lattice? and if so wouldn't the lattice itself be the cleartext and the basic pattern (given by the basis and the determinant) the answer from the hash function??? How exactly would you *encrypt* a message using a lattice???

I just wish I could find some text which explained this in English rather than symbols.. like this http://www.wisdom.weizmann.ac.il/~odedg/COL/cfh.pdf . I really hope I have not repeated any questions through my lack of understanding. Thanks in advance.

# Answer
> 0 votes
You have several confusions regarding cryptography. First, the nature of hash functions. The non-cryptographic use of hash functions is to hash long messages into shorter ones in a "uniform" fashion. So we expect there to be many collisions, by design. Cryptographic hash functions have the additional properties that collisions are hard to find (there are several, inequivalent ways of stating this). Therefore, while it is possible to find collisions even for cryptographic hash functions (simply because the range is smaller than the domain), this should be difficult. Such hash functions can be used in various ways in cryptography, for example in digital signatures: you sign on the (small) hash rather than the (large) message.

Second, encryption is a different primitive from hash functions. Encryption itself comes in two main kinds, symmetric and public key, which are rather different, and there are many other cryptographic constructions out there. There are reductions between some of the cryptographic "primitives" (hash functions, one-way functions and the like), for example you can use them to construct HMACs (message authentication codes) and PRNGs (pseudorandom number generators), but perhaps not encryption schemes.

Regarding the matter at hand: the idea of Ajtai's hash function is to use a random lattice $A$, the hash function being $x \mapsto Ax \pmod{q}$, for some prime $q$. Here $x$ is a *binary* vector in $\\{0,1\\}^m$, embedded into $\mathbb{Z}\_q^m$. The parameters here are important — the size of $A$ and $q$ — but I'll ignore them here. In order to show that this is cryptographically secure, under one definition we need to show that it is difficult to find a collision, that is two messages $x,y$ with the same hash. Such messages would satisfy $A(x-y) \equiv 0 \pmod{q}$, and so $x-y$ would be in the dual lattice $A^{\perp}$. Now $x-y \in \\{-1,0,1\\}^m$, so (for the correct choice of parameters) it is "short", and finding it is conjectured to be difficult. This shows the (conditional) security of the scheme.

Lattice-based encryption can also be used for public-key encryption (Regev's scheme) and for homomorphic encryption. These schemes rely on a different problem, LWE (learning with errors), which is similar to CVP (closest vector problem). The details are more complicated &mdash you can have a look at Regev's scheme in Section 5.4 of his survey with Micciancio, though it could be hard to glean from there why exactly the scheme works. Perhaps this is explained later in your course, and if you need more explanations, you can ask another question here.

---
Tags: cryptography, hash, lattices
---


# Question
Title: Error estimates of piecewise-linear curve approximations
In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about this functionality:

```
The FPLOT function begins with a minimum step of size (XMAX-XMIN)*TOL.
The step size is subsequently doubled whenever the relative error
between the linearly predicted value and the actual function value is
less than TOL.

```

So, if I plot a curve based on some expression and with some predefined tolerance TOL, is the error of the line segment approximation between any two calculated points always lower than TOL? Unfortunately, this is not obvious for me.

If not, how could one achieve a guaranteed (small) error of a piecewise-linear curve approximation (compared with the "exact" curve).

# Answer
> 0 votes
It is impossible to achieve a guaranteed small error for general functions. If the function is given to you as a black box, for all you know it could be the constant zero other than some specific point in $\[0,1\]$ in which it is very large. If you have bounds on the first two derivatives, however, then you should be able to use Taylor's formula to accomplish your guaranteed approximation.

Matlab's function probably uses some heuristic, which works for reasonable functions. The idea of this heuristic is to empirically estimate the derivative of a function at a point by computing $\[f(x+\epsilon)-f(x-\epsilon)\]/(2\epsilon)$ for some small $\epsilon \> 0$. When the derivative is large, the step size is small, and vice versa. Your worries are justified: in order to get a bound on the distance from the function, you need to have a global bound on the derivative in the entire interval being plotted, and then you can choose the tolerance accordingly. FPLOT is therefore just an optimization, choosing a larger step size when tolerable. From the description you gave it is not clear whether the step size is doubled once or keeps getting doubled — in the first case this optimization saves you at most half the time, and in the second case you could get large errors. (The first interpretation seems more reasonable.)

---
Tags: approximation, approximation-algorithms, error-estimation
---


# Question
Title: Decidability of fullness of intersection of a CSL with a regular language
Let $L\_r$ be a regular language with alphabet $\Sigma$ and $L\_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable?

1. $L\_r \cap L\_\text{csl} \stackrel{?}{=} L\_r$
2. $\Sigma^\* \cap L\_\text{csl} \stackrel{?}{=} L\_r$
3. $L\_r \cap L\_\text{csl} \stackrel{?}{=} \Sigma^\*$
4. $\Sigma^\* \cap L\_\text{csl} \stackrel{?}{=} \Sigma^\*$

I understand that (1) implies the others. I am also looking for any "near variants" that might be decidable.

# Answer
It is well-known that universality of context-free language is undecidable, making all your items undecidable already for context-free languages, so a fortiori for context sensitive languages (the particular case $L\_r=\Sigma^\*$ is already undecidable in all items).
> 7 votes

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Understanding expected time bound for unsuccessful search in R-way tries
As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log\_R N)$. Can someone please explain how this number can be derived?

# Answer
> 0 votes
search in a binary search tree is log base 2 of N. Now you have a R-nary tree, so the running time would be log base R of N.

---
Tags: data-structures, runtime-analysis, search-trees
---


# Question
Title: Classes and Algebras: Which begat which?
Way back in the day I took a course on discrete structures and learned about how the mathematical notion of an algebra is akin to the class data type.

But I didn't know enough at the time to ask whether algebras are used to model classes or whether classes are actually derived from algebras (historically, technically...in whatever sense of 'derived' you like).

Wikipedia and Google weren't much help. Anyone have any idea?

# Answer
> 2 votes
I'm not sure I fully understand your question, but I think you noticed that algebras (or more precisely algebraic signatures) and classes share a feature, namely that they both can be seen as specifying a bunch of operations. For example the algebraic construct *group* has three operations: multiplication, inverse and the constant $1$. Now you ask if algebras can be used to model classes.

The answer is negative at this point. Classes in the sense of OO programming are complicated beasts. They have features that algebras don't have, in particular computational dynamics. There are other features like inheritance, method overriding, mutable private members that also don't lend themselves to easy algebraic description. For this reason, purely algebraic sematics of OO languages don't exist.

As to the historic question, I don't know. The development of types goes back to the end of the 19th century, a time when abstract algebra was in nascent form too

# Answer
> 2 votes
The answer to your question is that both begat both.

Garret Birkhoff defined single-sorted universal algebras in 1935, but it was only in the 1960's that the field came into its own. Automata theorists picked up the ideas to develop algebraic automata theory and Birkhoff was inspired by automata theory to formulate many-sorted universal algebras \[Birkhoff and Lipson: Heterogeneous algebras, 1970\]. Simula 67 report was published in the same year!

Algebraic automata theory inspired Milner to develop simulation relations for programs, which in turn inspired Hoare to develop simulation relations for O-O classes \[Hoare: Correctness of Data Representations, 1972\]. This in turn inspired Guttag and Horning to apply universal algebra techniques for specifying abstract data types (which are basically a functional programming version of classes).

So, in my view, universal algebra and the theory of data types developed in tandem, borrowing ideas and inspiration from each other.

---
Tags: object-oriented
---


# Question
Title: Finding all paths with lengths in a fixed interval in sparse graphs
What is the most efficient way to find all paths of length M to N in a large sparse graph?

Some general information:

* Graph has 30,000 to 50,000 nodes
* Average number of edges per node ~ 10
* M=4, N=7
* Graph has cycles

# Answer
> 1 votes
Assuming a directed graph.

Paths of length $1$ are simply the edges.

paths of length $i+1$:

Unite on all nodes $v \in V$ {concatenate all paths of length $i$ that end with $v$ with all paths of length $1$ that start with $v$}.

repeat for $i=1$ to $7$.

Note that this method avoids redundancies, so you don't need to check for them.

# Answer
> 0 votes
this sounds something like the "K shortest path routing problem"

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Determining if a context-free grammar produces even-length strings
Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?

# Answer
Of course there is a meta-algorithm via automata and intersection constructions. Here is an algorithm that works out of the box, no tools needed.

We mark any variable in the grammar as "even" and/or "odd". Variables can have either no, one or zero marks. For simplicity we assume the grammar is in Chomsky normal form, but the trick can be reformulated for general grammars.

* For any $A\to a$ mark $A$ as "odd"

Repeat as long as variables get new marks:

* For $A\to BC$, if $B$ and $C$ are marked, carry the mark over to $A$ according to parity ("odd"+"odd"="even", etc.)

Yes, I know that is an implementation of "CFG emptiness" and "intersection with even length strings" merged, but still I like it.
> 1 votes

# Answer
There is an algorithm:

Recall that given a CFL $L$ and a regular language $K$, the language $L\cap K$ is also CFL (and a CFG for it is computable given a CFG for $L$ and a DFA for $K$).

Now, observe that the language $K=\\{w: |w| \text{ is even}\\}$ is regular.

From this we conclude that given a CFG $G$, we can construct a CFG for the language $\\{w: |w|\text{ is even and }w\in L(G)\\}$, and we observe that this language is nonempty iff $G$ generates a word of even length.

Since checking emptiness of CFG can be done in polynomial time, we can solve the problem in polynomial time.
> 2 votes

# Answer
1. The language of all even-length strings is regular, and you can construct a DFA that recognizes it.
2. The intersection of a regular language and a context-free language is context-free, and you can construct a CFG for it.
3. Given a CFG, it's decidable whether the language it generates is empty.
4. The language from (2) is empty as in (3) iff your context-free language generates no even-length strings.

See this for details.
> 2 votes

---
Tags: computability, context-free, formal-grammars, undecidability
---


# Question
Title: What do assemblers translate macros into during assembling?
I have dug in simple binaries, such as though like x86 bootloaders, sega video game binaries, etc. I know that these files tend to use assembler macros to define data, etc. What I am having trouble figuring out is what assemblers tend to translate macros into exactly (are they instructions, custom formatted data entries used statically, addressing mode/special opcodes, etc.).

I do not know if this is the wrong place to ask. If so, I am saving time by double-posting on reverse engineering 's SE.

# Answer
From a semantic point of view, macros are expanded into assembly code. How macros are actually implemented probably depends on the assembler. One option would be to expand them in a preprocessing step, like in C compilers; another would be to expand them on the go. The end result is the same — it is as if the macros were expanded textually in a preprocessing step.

There are other mechanisms used in assemblers that you might consider macros but are different. For example, the x86 MASM uses db/dw/dd to define data. These are stored in the resulting executable, the exact way depending on the executable format, particularly how the binary is loaded into memory. Usually there is a specific data segment which is loaded into a specific address, the relevant pages being marked non-executable if the processor supports this.
> 0 votes

# Answer
A macro is (by definition) a text to text translation. So you can define NUMBER to be 100, and use NUMBER each time, and change the definition once if NUMBER ever has to be 99. Some macro processors can handle macros with arguments, and expand to different text depending on them.

In assembly, macros are used to expand to stereotyped stretches of code (on VAX VMS there was a set of I/O routines that were implemented as hairy macros), to "fake" instructions by combining several others, ...

For a (gentle) introduction to macros in general, see the C (or C++) preprocessor. To go overboard, the Unix `m4(1)` macro processor (the 4 is because it was the fourth complete redesign) is something to behold. For examples specifically in assembler, look at NASM and/or GNU's gas (if on Linux, it's info should be installed).
> 0 votes

# Answer
Do you mean macros or directives? An assembler directive doesn't actually compile/assemble to any code; it just tells the assembler what to do with a single-pass phase before the assembling actually begins.

For example, the x86 `db` is not a macro, but a directive. It's a directive that gets translated in to the binary equivalent of that textually and stored as cumberless data somewhere in the binary(to which can be specified).

The directive known as `times` is a directive used to fill the binary file released with 0s and 1s, or one or the other, or any combination thereof, etc. This is done in x86 bootloaders because, on x86, all bootloaders must be 512 bytes or BIOS won't read it. However, the directive doesn't assemble to any "useful" code/data.

Macros are, as mentioned, data that can be referenced by name rather than value. Assemblers can use both, but it sounds to me like you're confusing these two terms.

While the data directives can also be used like macros along the source, the actual directives can not, and are usually "pre-assembler" steps much like C's preprocessor.
> 0 votes

---
Tags: compilers
---


# Question
Title: Is there a designation for this not-quite-exponential time?
I've been working and experimenting with an algorithm that *may* take time $O^\*(2^\sqrt{n})$. Here $O^\*(f(n))$ simply neglects all polynomial terms. I've seen a comment on Scott Aaronson's blog that mentions graph isomorphism algorithms run in this time, too. Actually, $O(2^\sqrt{n})$. Is there a designation for this time?

I thought perhaps quasi-exponential may describe it, but I'm wondering if there is already a name/designation for it.

# Answer
> 4 votes
Two useful classes are sub-exponential, $c^{n^\epsilon}$ for $\epsilon \in (0,1)$, and quasi-polynomial, $c^{\log^k n}$ for $k \> 1$. (In both cases, $c \> 1$.)

The terms themselves sometimes have different meanings. For example, in some contexts "sub-exponential" means $2^{(1-\epsilon)n}$ for some $\epsilon \> 0$, and in others it means $2^{o(n)}$.

Since the term "sub-exponential" is loaded, it is better to mention what you mean by it whenever you use it.

---
Tags: terminology, landau-notation
---


# Question
Title: Reduction to complement of Accept Problem
I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A\_{TM}) = \\{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \\}$$

To this Turing Machine, known as SPARSE TM: $$ SPARSE\_{TM} = \\{ \langle M \rangle \mid M \text{ is 1-tape TM}, |L(M)| \leq 1000\\} $$

Here is what I have so far, but I think I need help because one of the statements I make seems fishy.

Assume there is a TM `S` that decides the complement of the accept TM and a TM `R` that decides SPARSE. Then `S` looks like:

```
S = "On input `<M,w>`:
    Construct M':
        M' = "On input x:
            if x in L(M):  #Fishy statement
                accept
            else: reject
     Run R on <M'>
     if R accepts: accept; if R rejects: reject

```

This (if right) would then reduce the SPARSE TM and prove that it is undeciable, right? Any help would be appreciated.

# Answer
When reducing $L\_1$ to $L\_2$, we need to come up with a computable mapping $f$ such that $x \in L\_1$ iff $f(x) \in L\_2$. We don't start with a Turing machine deciding $L\_2$ and then construct one for deciding $L\_1$, although this construction can easily be accomplished using the mapping $f$. The reason we refrain from doing so is that sometimes we already know that $L\_2$ is undecidable, and yet there is merit in saying that $L\_1$ reduces to $L\_2$, since $L\_1$ might have an even strong guarantee of "hardness"; this sort of thinking leads to classical recursion theory.

Regarding your construction, there are two problems: (1) it doesn't involve $w$, (2) when you write "if $x \in L(M)$", you actually mean "simulate $M$ on $x$"; this simulation could halt, or it could never halt. Generally speaking, when a Turing machine never halts, then we say that it rejects. See if this fits with what you were trying to accomplish.
> 2 votes

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


title: Axiomatic Semantics and Postconditions

text:
# Question
Title: Axiomatic Semantics and Postconditions
I'll preface this by saying that this IS a homework question.

However, when asked about how to solve it in class, (I believe) my professor was unable to complete it.

The question is:

> Compute the weakest precondition for each of the following assignment statements and postconditions: $$a = a + 2b - 1\ \\{a \> 1\\}$$ (where a \> 1 is the postcondition)

His answer was: "$a \> 2 - 2b$." Is this correct? It seems that he broke the rules of equivalents, by using the "\>" as "="

I believe the answer is: $$\\{a\>1\\;\wedge\\; b\<\tfrac12\\}\quad\text{or}\quad \\{a \> 0\\;\wedge\\;2b-1 +a \>1\\},$$ where the "$\wedge$" symbol means "and"

We're using *Concepts of Programming Languages*, by Sebesta, 10th Edition, so any references from that material would be excellent :)

Thanks!

# Answer
A condition $P$ is *weaker* than $Q$ if $Q\Rightarrow P$; that is, whenever $Q$ holds, $P$ also holds or, if you prefer, $Q$ guarantees that $P$ holds. $P$ is *strictly weaker* than $Q$ if $Q\Rightarrow P$ but $P\not\Rightarrow Q$. Let's look at the three conditions included in the question:

1. $a\>2-2b$
2. $a\>1 \\;\wedge\\;b\>\tfrac12$
3. $a\>0 \\;\wedge\\; a\>2-2b$

(2) $\Rightarrow$ (3) since, if $a\>1$ then certianly $a\>0$ and, if $b\>\tfrac12$, then $2-2b\<1\<a$. (3) $\Rightarrow$ (1) since if $X$ and something else are both true, then certainly $X$ is true. None of the reverse implications holds: (1) is satisfied by $a=-1$, $b=2$ but (3) is not; (3) is satisfied by $a=\tfrac12$, $b=1$ but (2) is not. Therefore, (1) is strictly weaker than (3) which, in turn, is strictly weaker than (2).

So $a\>2-2b$ is the weakest of the preconditions on the table. But is it the weakest possible? Suppose $P$ is any precondition that implies that $a+2b-1\>1$. Rearranging, we see that $P\Rightarrow a\>2-2b$, i.e., $P\Rightarrow$ (1). This tells us that no other precondition can be strictly weaker than (1). Therefore, (1) is the weakest precondition.

I don't understand what you mean by \`It seems that he broke the rules of equivalents, by using the "\>" as "="' since, surely, if (1) breaks that rule, (3) does too? I don't know that rule so maybe somebody else can address that part of the question.
> 2 votes

---
Tags: semantics, hoare-logic
---


title: Proving iff statement with reductions

text:
# Question
Title: Proving iff statement with reductions
I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages.

**Question:** Let $ A = \\{ ww \ | \ w \ \epsilon \ \Sigma^{\*} \\} $.

Show that any language $L$ is Turing-decidable if and only if $L$ is many-one reducible to $A$.

Where I am so far:

1. Language $A$ is not context-free, but the complement of $A$ is context-free.
2. Both $A$ and the complement of $A$ are decidable.

So, that means I can prove one direction of the *iff* statement fairly easily:

If $L$ is many-one reducible to $A$ then since $A$ is decidable from statement (2) above, also $L$ is decidable.

The other direction is giving me problems. This is all I have gleaned so far:

If $L$ is Turing-decidable, then $L$ is a regular language.

Is there some relation between regular and context-free languages with respect to reductions that I am missing? Or should I be making a different logic jump in this part of the proof?

# Answer
> 2 votes
There is a more general theorem which says that if $A$ is a decidable language and $B$ is a decidable language that is not trivial (in the sense that $B\ne\Sigma^\*$ and $B\ne\emptyset\\, $), then $A\le\_m B$. Roughly speaking, this says that all non-trivial decidable languages are many-to-one reducible to each other, meaning that $\le\_m$ is too coarse a metric to distinguish between decidable languges.

In your problem, suppose that $L\subseteq \Gamma^\*$ and define a mapping $f:\Gamma^\*\rightarrow\Sigma^\*$ defined by: $$ f(x) = \begin{cases} \mathtt{aa} & \text{if $x\in L$}\\ \mathtt{a} & \text{if $x\notin L$} \end{cases} $$ for some $\mathtt{a}\in\Sigma^\*$. This is a total computable function (since by definition, we can use the computable decider program to determine $x$'s membership in $L\\, $) and it's easy to verify that $x\in L$ iff $f(x)\in A$, which is all you need to show $L\le\_m A$. As Yuval noted, you don't need any results about regular or context-free languages to answer this question.

# Answer
> 1 votes
First of all, not every decidable language is regular. For example, $A$ is decidable but not regular.

Here is a hint: this question doesn't have anything to do with either regular languages or context-free languages. While we certainly need $A$ to be decidable, for the other direction we only need some really simple properties of $A$. Try to think for which $A$ it is *not* true that if $L$ is decidable then $L$ can be many-one reduced to $A$.

---
Tags: turing-machines, reductions
---