title: Are device drivers state machines?

text:
# Question
Title: Are device drivers state machines?
I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- i.e. do they read and write to memory, or not?

# Answer
Many device drivers do read/write to memory. For instance, consider a network device; it reads the packets to be sent from memory and writes the packets it receives to memory. Or think of a hard disk driver; it does something analogous. So, ultimately, it will depend on the driver.

That said, device drivers often do have a portion of their internal state that can be thought of a state machine. For instance, the states could be something like UNINITIALIZED, ACTIVE, SUSPENDED, where it is initially in UNINITIALIZED state on boot; after it initializes the device registers, it could transition to ACTIVE state; on suspend, it might put the device into suspend mode and switch to the SUSPENDED state, and so on. This only accounts for part of the behavior of the device driver, but it can still be a helpful way to organize the driver. Or, in other words: often, some important aspects of the driver's behavior or state can be thought of as DFAs even though that's only approximately true.
> 3 votes

# Answer
In software engineering, the "state machine" is more of a design tool than anything else. But yes, many device drivers are designed as state machines. This is because many hardware devices, or the protocols by which you speak to them, have distinct states.

Take the SCSI command protocol as an example. You can do SCSI over many devices (parallel, serial, USB, fibre, etc). However, the idea is the same: Send a command, wait for a response, send another command, wait for another response, and so on.

So we have two logical "states":

* State 1: The driver is not waiting for a response from the device.
* State 2: The driver is waiting for a response from the device.

There are also two kinds of "event":

* Event 1: The operating system asks for some operation to be performed.
* Event 2: The device sends a response.

In state 1, event 1 causes the driver to issue a command, and enter state 2. If event 2 happens, then something went wrong.

In state 2, event 1 might cause the driver to buffer the operation (say). Event 2 causes the driver to issue a response to the operating system, and then see if any operations are buffered. If so, issue a new command. If not, enter state 1.

This is a fairly simple device, and already we have something that looks pretty much like a state machine. Moreover, this device is fairly "smart", and doesn't require very much intelligence on the part of the driver. A dumber device, such as a floppy drive (which requires low-level commands like "raise the read/write head" and "move the read/write head 5 tracks that way") might require a lot of states simply because of all the moving parts that it's the responsibility of the driver to keep track of.

In general, a driver needs to keep track of the state of the device, and so state machines are often a very good way to design them.
> 2 votes

---
Tags: finite-automata, operating-systems, computation-models, applied-theory
---


# Question
Title: Checking whether all integers appear exactly once
Let $\texttt{a\[\]}$ be a finite array. We want to check whether every number between $\texttt {min(a\[\])}$ and $\texttt {max(a\[\])}$ appears exactly once.

An obvious solution is sorting the array in time $O(n\log(n))$ and go through the sorted array in linear time and check that $\texttt{a\[k+1\] == a\[k\]+1}$ for $0\leq\texttt{k} \< \texttt{length(a)-1}$.

The total complexity of this would be again $O(n\log(n))$. Is there a better way to do this?

# Answer
Let $A$ contain $n$ elements. Scan $A$ to determine the maximum value $m$ in $A$. Then, initialize a bit vector $B$ of size $m$ to all zeros. Then scan $A$ and use $B$ for bookkeeping: when you encounter $i$ in $A$, set $B\[i\]$ to one (if $B\[i\]$ is already set, return false). In the end, return true if and only if $B$ contains exactly $n$ ones. This algorithm runs in $\Theta(n+m)$ time, or even in $\Theta(n)$ time if we assume $m = O(n)$.

We can also be a little bit more clever with David Richerby's idea. Let us scan $A$ to find its minimum value $s$. Then initialize an array $B$, this time of size $n$, to all zeros. Go through $A$ again, and when you encounter the value $i$ in $A$: if $i - s \> n$ or $B\[i-s\]=1$, return false. Otherwise, set $B\[i-s\]=1$. Obviously, this algorithm runs in $\Theta(n)$ time (independent of $m$).

In both cases we assume reading the index of an array is done in unit time, and also that arbitrary width arithmetic is performed in unit time.
> 7 votes

---
Tags: algorithm-analysis
---


title: Analysis of very simple algorithm

text:
# Question
Title: Analysis of very simple algorithm
I need to find the time complexity of the following simple algorithm.

> Calculate the time complexity of the following algorithm:
>
> ```
> void f(int n) {
>   int i, x;
>
>   for (i = 1; i <= n; i++)
>     if (i % 2 == 1)
>       x++
> }
>
> ```

It obvious that the time complexity of this algorithm is $\Theta(N)$, but how I prove it formally?

I know that the loop will do $N$ iterations, so the total number of operations will be $N \times \text{(number of operations inside the loop)}$.

Here the tricky part, I know that for each iteration will be one operation for the comparison and one operation only if $i$ is odd.

So it's something like this: $\sum\_{i=1}^{n}(1+\frac{1}{2})$? I'm not sure, it's seems too strange and I'm not sure how to continue.

What is the best way to write it formally?

Also, I would like to ask if there are books with many examples of analysis of simple algorithms like this and proofs of their complexity. The most recommended book seems to be CLRS, but I didn't found many examples of this kind there and from what I understand it can be very complex topic (depending on the series you need to calculate in the end).

Thank you.

# Answer
You're doing the right thing. There's no magic that you're missing.

$$ \begin{aligned} \sum\_{i=1}^n (1 + \frac{1}{2}) &=\\ &= \sum\_{i=1}^n \frac{3}{2}\\ &= \underbrace{\frac{3}{2} + \dots + \frac{3}{2}}\_{n \text{ times}}\\ &= \frac{3}{2}n \in O(n) \end{aligned} $$
> 1 votes

# Answer
One important thing to understand here is that the asymptotic analysis happens with respect to the parameters that are of interest to you. Here, for example, we are interested in the complexity with respect to the input $n$.

Typically, we assume that arithmetic operations (like the modulo or addition, etc) take a constant number of time. In a *real system*, one operation might indeed be more expensive than another. But, the important detail is that the time required by these operations *does not depend* on the input parameter $n$: it could be $1$, $100$, or $10^{\\#\text{stars}}$, but it is still a constant as long as it does not scale with the parameter of interest. So again, in summary, when we compute the asymptotic complexity of the function with respect to $n$, we can consider that all these operations take a constant time.

Based on the above, the code inside the for-loop also takes a constant time. Whether the condition is true or not is irrelevant. If it is false it will take some constant time, and if it is true it will take again some constant time (maybe more than before, but still constant). Hence, overall, the time for one iteration is $\Theta(1)$.

Then, as you said, the overall complexity will be $\Theta(n) \cdot \Theta(1) = \Theta(n)$.
> 3 votes

# Answer
The thing to remember with Big-O is that it's an upper bound. So there are times you can assume things are worse than they actually are.

You know that inside the loop, at most two operations are performed each time. So forget about $\sum\_{i=1}^{n}(1+\frac{1}{2})$. You know that $\sum\_{i=1}^{n}(1+\frac{1}{2}) \leq \sum\_{i=1}^{n}(2)$, and you can apply sum rules to see that $\sum\_{i=1}^{n}(2) = 2n$.

So now you know the number of operations performed inside the loop is less-than or equal to $2n$ operations, and we evaluate the loop condition $n+1$ times (it fails on the last time).

$2n$ is in the set $O(n)$, that is, when you remove the constants, you can see that the overall running time is $O(n)$.

If you wanted to be picky, you could do the opposite to get a lower bound on the running time by assuming you only ever do one operation inside the loop, thus showing that the running time is $\Theta(n)$ i.e. $n$ $O(n)$ is a tight upper bound.
> 1 votes

---
Tags: algorithm-analysis, time-complexity
---


title: How many permutations in a trainset?

text:
# Question
Title: How many permutations in a trainset?
If I have the following pieces to a train set:

* (12) Curve
* (4) Straight

Such as this train set.

I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. It's not as simple as just creating a list , such as the following, where s=straight and c=curve, and creating all permutations, since the pieces are reversible:

sssscccccccccccc

For example, a Curve piece can either curve left or curve right. I thought about doubling the number of curve pieces and calling them 'cr' and 'cl' and then doing permutations on a list such as:

ssssclclclclclclclclclclclclcrcrcrcrcrcrcrcr

However, I think that is introducing more problems, so I'm thinking of creating a tree structure as such:

Each level of tree represents adding a new piece, where cl=Curve Left, s = Straight, cr = Curve Right.

I would then traverse each path in tree structure and determine if it forms a 'solution'. A solution would be defined as starting point = ending point, however, that is a different problem/algorithm as it requires knowing the lengths and arcs of the pieces. The algorithm would need to account for solutions that consist of all pieces (16 in this case), 15, 14 ... down to 8 (as that would be the smallest number to make a circle from the trainset in the picture). To solve those solutions, I would just create paths to all the nodes at a given level. Does this seem reasonable or other thoughts?

# Answer
> 3 votes
I bought that set for my grand son (nice and cheap Ikea product, kids love it from 18 month to 80 years, though not rcommended before 3 years of age), so I am very experienced with the problem.

For the uninitiated, the tracks are oriented because they connect with a hole on one end and a hooking tongue on the other end. So curved tracks have to be placed with one side or the other up, depending on which way you want to turn. The Ikea picture does not make it obvious: the little plastic pieces are actually glued as tongue on one end of a track, but the curves track have grooves for the wheels on both sides.

## Counting the configurations

I will use the word configuration for a way of putting the track elements together. It seems more appropriate than the word "*permutation*" which has a precise technical meaning.

The first analysis, described in this section, consist in evaluating the total number of possible configurations. This will help us to actually enumerate them in the next part.

You have 16 track elements, including 4 straight and 12 curved.

If you consider your 16 elements in succession, you have $\binom {16} 4 =\frac{16!}{4!\times 12!} $ ways of choosing a combination of positions for the 4 straights tracks, among 16.

Now, if you consider the curved tracks, they can be placed either as left curve or as right curve. For 12 tracks that makes $2^{12}$ possibilities (using train tracks to implement binary numbers makes for heavy duty computers).

So the total number of "permutations" (that use of the word does not seem too appropriate) is the product of the two numbers, since they correspond to independent choices, i.e., $$\frac{2^{12}\times 16!}{4!\times 12!} $$

But this answer may not be quite correct: if you have a closed circuit, you can consider it to start with any of the track elements, so that it counts for 16 "permutations", though one might consider it should count for 1. Hence, it might be appropriate to substract 15 from the result for each closed circuit that can be constructed. Geometric analysis of the shape of track elements shows that there are several closed circuits that can be constructed. Note that, except for the eight shape with crossing tracks, circuits are oriented, and each shape must me counted twice.

Other closed circuits are possible with with less track elements, in particular with exactly 8 curves, and 0, 2, or 4 straight. But we now ignore the issue of closed curves.

If you consider $n$ elements, $8\leq n\leq 16$, of which $m$ are straight, with $0\leq m\leq 4$, the number of circuits is $$\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Thus, for all possible values of $m$, with a number $n$ of elements, including at most 12 curved, the total number of circuits is: $$\sum\_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Finally, considering all possible values of $n$ in $\[8,16\]$, we get the number of circuits: $$\sum\_{n=8}^{n=16} \sum\_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Then there is the small number of cases when the circuit is closed, which one can analyse to count all their starting element variants as the same circuit. Note that when the track does not cross itself, each closed shape comes in two variants: clockwise and counter-clockwise. But should I go in so many details.

## Enumerating the configurations

The analysis used for counting configurationscan be repeated identically to enumerate them.

We consider $n$ track elements, of which $m$ are straight and $p$ are curved: $n=m+p$. We want to enumerate all the circuits that use all these elements.

First, we want to place the $m$ straight track in the sequence of $n$ track element position. For this you must enumerate all combinations of $m$ integers among the first $n$ integers. Algorithms already exists to enumerate these conbinations, available in wikipedia, or fromn other sources, so there is no point in developing that further here.

Then, for each such combination, you simply try all possible combinations of left or right positionning of curved track elements, which you can do by enumerating all possible sequences of$0$ and $1$, hence simply using a counter to enumerate in binary all integers from $0$ to $2^p-1$. It is advisable to use the fast changing bits in the enumeration on the end side of the configuration, in order to factor the beginning of computations that might be used to check whether the configurations give a closed circuit.

Of course, this can be repeated for other values of $m$ and $p$. But configurations for smaller values are just prefixes of the configurations for the maximum values of $n$ and $m$. So, doing it only for the maximum values should be enough to observe on the fly whatever we are interested in regarding smaller configurations. THis is detailed regarding closed circuits in the next section.

## Checking a configuration

Given a configuration for a sequence of track elements, and starting from porition (0,0), and direction angle 0, one can compute the position and direction at the end of the first track element, then propagate to the end of the second, and so on till the last. The circuit is closed if the end of the last track element is in position (0,0) with direction angle 0.

The shape of the track elements is determined by the fact that 8 curves make a full circle, and 12 cuves and 4 straight make an eight shaped curve. One can use the radius of the circle as distance unit, Then the staight track elements have a length of 1 radius.

For simplification, one can also take$45^o$ as the angle unit, so that each curved track changes the orientation by plus (left) or minus (right) one unit, and 8 units make a full circle. Hence orientation can be represented byrf an integer modulo 8.

Positions of track elements ends should not be computed as real numbers, but as expression using integers and $\sqrt 2/2$, of the form $a+b\sqrt 2/2$, a bit like complex numbers where $i$ is replaced by $\sqrt 2/2$. That makes the computations much cheaper, based on integer arithmetics on pairs $(a,b)$, and the $\sqrt 2/2$ ultimately cancel each other for closed circuits.

Actually, to explain it formally, plane coordinates reachable from the origin with straight and curved track elements are all expressible as $a+b\sqrt 2/2$. Hence, since 2 coordinates are used on the plane, and since $1$ is incommensurable with $\sqrt 2$, plane coordinates can be seen as a 4-dimensional vector space over the field $\mathbb Q$ of rationals, or better, since we use only integer coordinates in that vector space, as a 4-dimensional module over the ring $\mathbb Z$ of integer. See this mathematics question which is a followup to the question answered here. Hence following track element by track element the configuration of a circuit, for the purpose of checking whether it is closed, can be done using only integer addition and substraction.

A circuit starts at the origin with orientation $0$. The circuit is closed when it ends also at the origin with orientation $0$. In the four dimensional space, the coordinates of the origine are $(0,0,0,0)$

I guess any reader can further develop the computation details, for each type of track element. (this answer is already very long).

As explained in the previous section, doing the enumeration for maximum values of $n$ and $m$ will include smaller configurations as prefixes. In particular, if you are looking for closed circuits of all sizes, the simplest is to compute all configurations with the maximum values of $n$ and $m$, and check closure not just at the end, but at every step of the computation of track elements positions. However, there is a possibility for some optimization in performing these checks, as no closed circuit can be found with less than eight curved track elements.

---
Tags: combinatorics, permutations
---


title: Construction of fair teams

text:
# Question
Title: Construction of fair teams
let's say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team.

Each team consists of two players. One player is taking a defense position, another player is taking an offense position. The teams can decide for themself which of the players if playing at what position. We can assume that the teams try to win and will take the best possible combination of defense/offense player.

Each player has an offense rating (e.g. discrete number between 0 and 10) and a defense rating (same scale) that describes how strong the player is in the offense or defense position.

The strength of a team is determined by the defense strength of the player in the defense position and the offense strength of the player in the offense position. So we can assume:

```
TeamStrength = max(PlayerADefense + PlayerBOffense, PlayerAOffense + PlayerBDefense)

```

The question is, what is a good algorithm to find teams of similar strength using above metric.

My thinking is that I can easily evaluate a single result by calculating an average team strength and build the sum of difference (square).

Based on this it is obvious that I can just create random matches and then choose a "good" solution. However I'm curious if there is a way to find an optimal solution without brute forcing of all variants.

Any ideas?

**Edit:** There seems to be some confusion about the metric of optimal strength / average strength.

The goal is to have teams of similar strength, nothing more nothing less. Specifically I don't care if there are other combinations where the total strength of all teams is higher.

I can imagine various metrics to achieve this goal. One idea I presented was to use the following metric:

```
For each team t calculate its strength by calculating:
    strength_t = max(PlayerADefense_t + PlayerBOffense_t, PlayerAOffense_t + PlayerBDefense_t)
Calculate the average team strength: avgStrength = sum(strength_t) / teamCount
For each team t calculate its deviation from the average squared and sum it:
    m = m + (avgStrength - strength_t) ^ 2
m should be minimal

```

I want to minimize the value $m$. I want to emphazize that I'm open to other metrics if they provide comparable results.

# Answer
This can be expressed as a weighted maximum matching problem.

Suppose we want the average team strength to be $x$. If the actual team strength is $s$, we apply a penalty of $(x-s)^2$. In this way, for any proposed partitioning of the players into teams, we obtain a total penalty (the sum of the penalties for each of the teams). The goal is to find an assignment of teams that minimize the total penalty. I think this is what you are asking for.

So, here is how we express this as a maximum matching problem. If you have $n$ players, form a graph with $n$ vertices, one vertex per player. For each pair of players $v,w$, add an edge from $v$ to $w$ whose weight is $-(x-s\_{v,w})^2$, where $s\_{v,w}$ is the strength of the team obtained by putting $v$ and $w$ onto the same team. Now any division of the people into $n/2$ teams is a matching in this graph. By maximizing the total weight of the matching, we are minimizing the total penalty of the corresponding teams, so the maximum matching gives us a solution to your problem. Finally, there are polynomial-time algorithms for finding a maximum matching in a weighted graph, so you can just use one of them.

How do we find $x$? I initially interpreted your comments to imply that $x$ should be the optimal team strength, by which I assume you mean the average strength of the teams in the assignment that maximizes this average (without trying to make the team strengths as similar as possible). This too can be computed by solving a maximum matching problem, where now the weight on the edge from $v$ to $w$ is simply $s\_{v,w}$. So, the total algorithm is: first find $x$, using an algorithm for maximum matching, then find the best partitioning of teams according to your original matching, by applying the maximum matching algorithm a second time.

However, after reading megas' comments, I now suspect that interpretation was incorrect. As megas correctly explains, a more reasonable interpretation would be to make $x$ be the average strength of the teams *in the partitioning selected to make team strength as close as possible*. That's a harder problem.

However, here's an approach that might work reasonably well in practice. Sweep $x$ over a range of candidate values, say, over 100 candidate values. (You can probably get some reasonable guess for a range $\[\ell,u\]$ that is likely to contain the optimal value for $x$; now try a bunch of different values of $x$ in that range, say the values $\ell, \ell+0.01(u-\ell), \ell+0.02(u-\ell), \dots,u$.) For each such hypothesized value of $x$, solve the maximum matching problem (with weights $-(x-s\_{v,w})^2$ on the edges) to get an assignment of players to teams. In this way, we get 100 candidate assignments. Now for each we can calculate the average team strength and the total penalty, and see which assignment is best.

Why do I expect this will give close to an optimal answer? Well, there is some real optimum. Let $x\_\text{opt}$ be the average team strength for this actual optimum. When we use a candidate value for $x$ that is sufficiently close to $x\_\text{opt}$, we can expect to get an assignment that matches the optimum (or is close to it). So, if the step size for the candidate values of $x$ is small enough, this procedure seems like it should find the optimum. In practice, this is only a heuristic, and it might or might not find the actual optimum, but I suspect it will enable you to find an assignment that's pretty close to optimal, even if it's not exactly the optimum.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Lower bound the difference between distinct values of a function over a discrete domain?
I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap \[-10,10\]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose coordinates are in the range $-10..10$, inclusive).

I'm interested in computing a non-trivial lower bound on the value of

$$\min\_{\substack{x\_1 \neq x\_2 \\ x\_1,x\_2 \in X}} \big|~f(x\_1) - f(x\_2)~\big|$$

One possible approach is exhaustive search. Say there are $N = |X|$ distinct elements in the domain. Then I would compute $f(x)$ for each $x \in X$, and then calculate the difference between the $f(x\_1)-f(x\_2)$ for each pair of distinct values $(x\_1,x\_2) \in X$. This would require $N$ evaluations of $f$ and $N(N-1)$ operations between the values.

My questions are:

1. Has someone has seen this type of problem before. I'd like to find out more about related problems, but I just don't know what are the right terms to look for in the literature.
2. Is it possible to do better by exploiting properties of $f$? I'm looking to compute the "minimum difference in function values" for a functions such as $\log(1+\exp(-s^Tx))$ (i.e., convex, continuous, monotonically decreasing in $s^Tx$ where $s \in \mathbb{R}^d$; this is the logistic loss function that is optimized in machine learning applications).

# Answer
> 3 votes
You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time. Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values. The smallest such gap is exactly the value of $\min |f(x\_1)-f(x\_2)|$.

As Raphael says, without any information about $f$, it seems unlikely that you can do any better than to evaluate $f$ on every possible input. Indeed, it seems possible to prove this using an adversarial argument, in a black-box setting: if there is a single value $x^\*$ where you haven't evaluated $f(x^\*)$, then any answer your algorithm outputs can be made to be wrong by choosing the value of $f(x^\*)$ appropriately.

Since the notion of "monotonically non-decreasing" is not defined when the domain is not totally ordered (as in your example for $X$), and the notion of continuous is not defined when the domain is discrete (i.e., not continuous, as in your example for $X$), your second question isn't well-formed and can't be answered in its current state.

---
Tags: algorithms, optimization, discrete-mathematics, finite-sets
---


# Question
Title: Why do all non-empty ω-regular languages have periodic members?
I was learning about Büchi Automata and couldn't understand a part where they were describing "Non-empty $\omega$-regular languages contain periodic strings"

> Let $A$ be a Büchi automaton and $s ∈ L^\omega(A)$. There is an accepting run $r$ of $A$ on $s$ such that $q ∈ \text{Inf}(r)$, for some $q$. **Then, there exist finite strings $s\_0$ and $s\_1$ such that $s\_0s\_1$ is a prefix of $s$, and such that $A$, after processing $s\_0$ is in $q$, and after processing $s\_0s\_1$ is also in $q$**. Then, the periodic string $s' = s\_0s\_1s\_1s\_1 \dotsm$ is accepted by $A$ since there is a run on $s'$ that contains $q$ infinitely many times.

I bolded the part I'm having trouble understanding. Why is it that we can say after running a prefix like $s\_0$ we are in an accept state $q$? It seems to me a prefix could easily end in some not accepting state (i.e not in $\text{Inf}(r)$).

# Answer
Actually, it *doesn't* say that $q$ is an accepting state, though it should do! $\mathrm{Inf}(r)$ is the set of states visited infinitely often during the run $r$. The acceptance condition of Büchi automata is that $\mathrm{Inf}(r)$ contains an accepting state.

The correct proof is as follows, with explanation added. Note also that, while your title says that the automaton is deterministic, the proof applies to nondeterministic automata, too, since it talks about the existence of a run with a particular property, rather than saying that the unique run has that property.

Let $A$ be a Büchi automaton and let $s\in L^\omega(A)$. Since $A$ accepts $s$, there must be a run $r$ of $a$ on $s$ that has an accepting state $q\in \mathrm{Inf(r)}$ because a Büchi automaton accepts if, and only if, some accepting state is visited infintely often. Let $s\_0$ be any prefix of $s$ such that $A$ is in state $q$ after reading $s\_0$. Since $r$ visits $q$ infinitely often, it must return to $q$ when processing $s$, say after processing the prefix $s\_0s\_1$. In particular, if the automaton is in state $q$ and reads string $s\_1$, there is a run in which it returns to $q$. Therefore, the automaton has a run that visits $q$ infinitely often when processing the string $s\_0\\,{s\_1}^\omega = s\_0s\_1s\_1s\_1\dots$.
> 5 votes

# Answer
It may be worth noting that referring to any particular automaton is not really needed to prove the statement in the title. The standard definition of an $\omega$-regular language is as a finite union

$L=A\_1B\_1^\omega\cup\dots\cup A\_nB\_n^\omega$,

where all $A\_i$ and $B\_i$ are regular. If $L$ is nonempty, then there is at least one $i$ with $A\_i,B\_i$ nonempty; picking any $u\in A\_i,v\in B\_i$, it is clear that $uv^\omega\in L$.
> 2 votes

# Answer
By definition, a run $r$ is **accepting** if there is a **final state** such that $q \in \text{Inf}(r)$.

**EDIT** (to please david-richerby).

The **standard definition** of an accepting run says that a run $r$ is **accepting** if there is a **final state** such that $q \in \text{Inf}(r)$.
> 0 votes

---
Tags: automata, buchi-automata
---


title: The relation between 2SAT and 3SAT

text:
# Question
Title: The relation between 2SAT and 3SAT
> Show that proving 2SAT is **not** NP-Complete would prove that 3SAT is **not** in P.

Or eqivalently -

> Show that proving 3SAT is in P would prove that 2SAT is NP-Complete.

I can see there is an easy reduction from 2SAT to 3SAT and it seems like it is the key here, but I can't quite prove the statement above. Can anyone help?

# Answer
> 7 votes
This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false instance becomes NP-complete! Let's imagine that we are in a world where 3SAT is in P.

Now consider the simple problem 1-VAR-SAT, which is SAT where we have one variable, and at most two clauses. There are 3 1-VAR-SAT problems, $x$, $!x$, and $x \vee !x$. The last is the only unsolvable one.

Turns out, if 3SAT is in P, then 1-VAR-SAT is NP-complete! Here is the model.

Take a 3SAT instance, and solve it (that's polynomial time, 3SAT is in P). If the problem is solvable, output $x$. If it is unsolvable, output $x \vee !x$. We have turned a 3SAT instance into a 1-VAR-SAT problem, which is solvable if and only if the original is solvable, in polynomial time!

# Answer
> 7 votes
Another way to put it:

* 2-SAT is in P and in NP.
* if any problem in P (or in NP) is not NP complete, then P!=NP.
* so if 2-SAT is not NP-complete, then P!=NP.
* if P!=NP, then NP-complete problems are not in P.
* so if 2-SAT is not NP-complete, then P!=NP and 3-SAT (being NP-complete) is not in P

equivalently (easier):

* 3-SAT is NP-complete.
* if an NP-complete problem is in P, then P=NP.
* if P=NP, then every problem in P is NP-complete.
* 2-SAT is in P (and in NP).
* so if 3-SAT is in P, then P=NP and every P (and NP) problem is NP-complete, including 2-SAT.

# Answer
> 2 votes
Hint: If 3SAT is in P then P=NP and so every non-trivial problem in NP is NP-complete. (Non-trivial means that it's not the empty language nor the complete language.)

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


# Question
Title: What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples
I was reading the documentation for Julia's Dataframe package, and the package implements Dataframe by a series of a columns each of a single type. From reading the docs, it looks like that's how R implements Dataframes as well. Is there any reason this is a better way than having a Dataframe being a collection of tuples with elements of different types? The later seems more natural to me.

What are the trade-offs or reasons one would implement Dataframes as a list of columns vs a list of rows?

# Answer
At the level of an actual implementation, Array of structures versus structure of arrays makes an enormous performance difference; particularly when SIMD parallelism is involved. If you want to add together all of the values of one field, then all of those values are sitting next to each other.

SIMD instructions add/mul entire arrays all at once, rather than looping over each struct member. If you need to jump around memory to add all of these, you will invalidate memory caches. Also, suppose that only one column has non-default values, and the other dozen columns have zero values. The implementation can simply not bring over columns that are all zero. Run-length coding can be used on columns, or differential encoding.

In the BigData world, there are different serialization standards in use. Parquet is one option, picked because it has these characteristics due to being a columnar format. These kinds of formats are oriented towards doing stream processing. For example: you can get the next 1024 rows as a batch out of a cursor, but as an implementation detail they are packed in a columnar format.
> 1 votes

---
Tags: data-structures, statistics
---


# Question
Title: Do comparison sorts have to start at the beginning of the input?
Say I had an input $\langle3,17,15,9,1\rangle$, could I for example begin by comparing 1 with 3 so that 1 appeared at the start of the sorted sequence straight away or would I first have to compare 3 and 17 and then continue working from left to right with consecutive numbers? If the latter is correct, do I then have to keep returning to the start to continue comparing elements until I reach the fully sorted array? If this is the case, how is it possible to sort the input in $n-1$ (4) steps?

# Answer
You can make the comparisons in any order you want. If there was only one possible sequence of comparisons, there'd be only one possible sorting algorithm!

But note that, to specify an algorithm, you have to specify it in terms of operations that your model of computation supports. For example, althouh you as an intelligent human can say "compare 1 with 3", to specify an algorithm, you'd need to be able to describe how to choose the elements to be compared next. Of course, you could try to say "compare the smallest with the second-smallest" but, then, you'd have to give an algorithm for finding those two elements which would, itself, probably use further comparisons. And, of course, if you already knew which were the smallest two, you wouldn't need to compare them anyway.
> 3 votes

---
Tags: algorithms, sorting
---


# Question
Title: How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?
How can TSP be an NP-optimization problem ?

The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S\_\Pi(I)$ is non-empty and that the size of each $s \in S\_\Pi(I)$ is polynomial bounded in $|I|$, where $|I|$ denote the size of $I$.

However, in the case of TSP an instance will be encoded using $n^2$ bits, where $n$ is the number of vertices in the instance graph, using the adjacency matrix representation.

But there are $n!$ feasible solutions ? In order to encode these one must use $n! \setminus 2^n$ bits. This number increase as $n$ increase, but $p(|I|)$ is fixed ?

How I overseen something ?

# Answer
A solution in the TSP problem is a sequence of $n$ vertices. Consider a labeling $1,\dots, n$ of the $n$ vertices. We need $O(\log{n})$ bits to encode the label of each vertex. Then, any sequence of $n$ vertices can be described by $O(n\log{n})$ bits; the concatenation of $n$ vertex labels. Hence, any solution $s$ of the TSP can be described by a number of bits that is polynomial in $n$.

The size of the instance $I$ is also polynomial in the number of vertices $n$, as noted in the original question.
> 2 votes

---
Tags: complexity-theory, optimization, np, traveling-salesman
---


# Question
Title: Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$
I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment.

I need to prove a language $L$ is not Turing-recognizable by giving a reduction from the following language:

$$D = \\{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\\}\\,,$$

where $M$ is a Turing machine, and $\langle M\rangle$ is a binary encoding of $M$, and it is already assumed $M$ is neither decidable nor recognizable.

Most of the things I've read show how to prove a language is undecidable, but not unrecognizable. How would it be different?

I've encountered the following that I feel I can modify for my problem:

$$\mathrm{A\_{TM}} = \\{\langle M,w\rangle \mid M \text{ accepts }w\\}\\,.$$

$D$ reduces to $\mathrm{A\_{TM}}$. Consider the computable function that maps $\langle M\rangle$ to $\langle M',w\rangle$, where $w=\langle M\rangle$ and $M'$ is a machine that accepts if and only if $M$ rejects. Therefore, $\mathrm{A\_{TM}}$ is undecidable.

But I'm not really sure how to understand it, in plain English. Could someone explain it? Plus, how could I change this to show $\mathrm{A\_{TM}}$ is unrecognizable (even if it is recognizable)?

# Answer
Like any claim, you have more than one way to prove a language $L$ is unrecognisable.

In case your language is in $Co-RE$ you can do one of the following:

1. Show $\overline{L}$ is in $RE$ by describing a TM that accepts $\overline{L}$.
2. Show $\overline{L}$ is in $RE$ by reduction $\overline{L}\le\_m Some-Language-In-RE$.
3. Show $\overline{H\_{TM}} \le\_m L$ or $\overline{A\_{TM}} \le\_m L$ or some other language you know is in $Co-RE$

Note that you must show that $L\notin R$ in order to deduce $L\notin RE$.

If $A\notin Co-RE$, you can show a reduction to your language

4. $A\le\_m L$ where $A\notin RE$ so if $L\in RE$ you have a contradiction.

There is more than one way. I'm not sure I understand your question, but if your task is to show $D\notin RE$. I would show $\overline{D}\in RE$, and than show $D\notin R$.
> 3 votes

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


# Question
Title: Can sampling remove the limitations in greedy algorithm?
Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of greedy algorithm?

I understand the answer to this is problem-specific, but given a problem that shows the limitation of greedy algorithm can sampling be used in any way in order to guide the greedy algorithm to generate an optimal solution?

# Answer
> 6 votes
It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as *myopic algorithms*) being only one of them. That said, I have a positive answer and a negative answer for you.

**Positive answer.** Consider the problem of maximizing a non-negative submodular function under a cardinality constraint. In this problem, you are given a submodular function $f$ over a domain $U$, and a bound $k$. Your task is to find a subset $S \subset U$ of size at most $k$ such that $f(S)$ is as large as possible. This problem is hard (more on that below), and so we make do with approximation algorithms. The greedy algorithm has no guarantees in this regard, but a simple modification of it gives a (probably non-optimal) $1/e$ guarantee. See Buchbinder–Feldman–Naor–Schwartz.

**Negative answer.** In what sense is the problem of maximizing a non-negative submodular function under a cardinality constraint hard? One such sense is *hardness in the value oracle model*. Suppose that an approximation algorithm is given oracle access to the function $f$. Then if $f$ always produces a $1/2+\epsilon$ approximation, there must be some $f$ and $k$ for which it calls the oracle exponentially many times (in $n = |U|$), a result due to Vondrák. This hardness result holds even for randomized algorithms (with any constant success probability). So randomization has its limits as an ingredient.

**Does randomness help?** Take the closely related problem of unconstrained submodular maximization – the case $k = n$ (recall $n = |U|$) of the problem considered above. The algorithm of Buchbinder–Feldman–Naor–Schwartz yields the optimal 1/2 approximation, but is randomized. They also give a 1/3 approximation algorithm which is deterministic, matching previous guarantees of Feige–Mirrokni–Vondrák. Can deterministic algorithms achieve the randomized guarantee? (Rumour has it that the answer is: Yes.)

**Can randomization help?** Under the widely held belief that P=BPP, there cannot be any discrepancy between randomized and deterministic polytime algorithms. However, this holds only in the model in which the input is given explicitly. In the value oracle model, the input is given implicitly as an oracle, and so it could be that randomized algorithms outperform deterministic ones. Indeed, it is easy to come up with specific tasks which are much easier for randomized algorithms. The question is whether unconstrained submodular maximization is one of these examples.

---
Tags: algorithms, greedy-algorithms, sampling
---


# Question
Title: Why can't fibers utilize multiple processors?
It seems that the distinction between fibers and threads is that fibers are cooperatively scheduled, whereas threads are preemptively scheduled. The point of the scheduler seems like a way to make an otherwise serial processor resource act in a parallel way, by "time-sharing" the CPU. However, on a dual-core processor with each core running its own thread, I assume there's no need to pause the execution of one thread for the other to continue because they're not "time-sharing" a single processor.

So, if the difference between threads and fibers is the way they are interrupted by the scheduler, and interrupting is not necessary when running on physically separate cores, **why can't fibers take advantage of multiple processor cores when threads can?**

Sources of confusion:

..mainly wikipedia

1. http://en.wikipedia.org/wiki/Fiber\_%28computer\_science%29

> A disadvantage is that fibers cannot utilize multiprocessor machines without also using preemptive threads
2. http://en.wikipedia.org/wiki/Computer\_multitasking#Multithreading

> ...\[fibers\] tend to lose some or all of the benefits of threads on machines with multiple processors.

# Answer
> 9 votes
The main distinction, as you point out in your question, is whether or not the scheduler will ever preempt a thread. The way a programmer thinks about sharing data structures or about synchronizing between "threads" is very different in preemptive and cooperative systems.

In a cooperative system (which goes by many names, *cooperative multi-tasking*, *nonpreemptive multi-tasking*, *user-level threads*, *green threads*, and *fibers* are five common ones currently) the programmer is guaranteed that their code will run *atomically* as long as they don't make any system calls or call `yield()`. This makes it particularly easy to deal with data structures shared between multiple fibers. Unless you need to make a system call as part of a critical section, critical sections don't need to be marked (with mutex `lock` and `unlock` calls, for example). So in code like:

```
x = x + y
y = 2 * x

```

the programmer needn't worry that some other fiber could be working with the `x` and `y` variables at the same time. `x` and `y` will be updated together atomically from the perspective of all the other fibers. Similarly, all the fibers could share some more complicated structure, like a tree and a call like `tree.insert(key, value)` would not need to be protected by any mutex or critical section.

In contrast, in a preemptive multithreading system, as with truly parallel/multicore threads, *every possible interleaving of instructions between threads is possible* unless there are explicit critical sections. An interrupt and preemption could become between any two instructions. In the above example:

```
 thread 0                thread 1
                         < thread 1 could read or modify x or y at this point
 read x
                         < thread 1 could read or modify x or y at this point
 read y
                         < thread 1 could read or modify x or y at this point
 add x and y
                         < thread 1 could read or modify x or y at this point
 write the result back into x
                         < thread 1 could read or modify x or y at this point
 read x
                         < thread 1 could read or modify x or y at this point
 multiply by 2
                         < thread 1 could read or modify x or y at this point
 write the result back into y
                         < thread 1 could read or modify x or y at this point

```

So to be correct on a preemptive system, or on a system with truly parallel threads, you need to surround every critical section with some kind of synchronization, like a mutex `lock` at the beginning and a mutex `unlock` at the end.

Fibers are thus more similar to *asynchronous i/o* libraries than they are to preemptive threads or truly parallel threads. The fiber scheduler is invoked and can switch fibers during long latency i/o operations. This can give the benefit of multiple simultaneous i/o operations without requiring synchronization operations around critical sections. Thus using fibers can, perhaps, have less programming complexity than preemptive or truly parallel threads, but the lack of synchronization around critical sections would lead to disastrous results if you tried to run the fibers truly simultaneously or preemptively.

# Answer
> 6 votes
The answer is actually that they could, but there is a desire not to.

Fibers are used because they let you *control* how scheduling occurs. Accordingly, it is much simpler to design some algorithms using fibers because the programmer has say in which fiber is being executed at any one time. However, if you want two fibers to be executed on two different cores at the same time, you have to manually schedule them to do so.

Threads give control of which code is being executed to the OS. In exchange, the OS takes care of many ugly tasks for you. Some algorithms get more difficult, because the programmer has less say in which code is executed at a given time, so more unexpected cases can surface. Tools like mutexes and semaphores are added to an OS to give the programmer just enough control to make threads useful and beat down some of the uncertainty, without bogging the programmer down.

**This leads to something which is even more important than cooperative vs. preemptive: fibers are controlled by the programmer, while threads are controlled by the OS.**

You don't want to have to spawn a fiber on another processor. The assembly level commands to do so are atrociously complicated, and they are often processor specific. You don't want to have to write 15 different versions of your code to handle these processors, so you turn to the OS. The OS's job is to abstract these differences away. The result is "threads."

Fibers run on top of threads. They don't run on their own. Accordingly, if you want to run two fibers on different cores, you can simply spawn two threads, and run a fiber on each of them. In many implementations of fibers, you can do this easily. The multi-core support is not coming from the fibers, but the threads.

It becomes easy to show that, unless you want to write your own processor specific code, there is nothing you could do by assigning fibers to multiple cores that you couldn't do by creating threads and assigning fibers to each. One of my favorite rules for API design is **"An API is not done when you have finished adding everything to it, but rather when you can no longer find anything else to take out."** Given that multi-core is handled perfectly by hosting fibers on threads, there's no reason to complicate the fiber API by adding multi-core at that level.

---
Tags: parallel-computing, threads, multi-tasking
---


# Question
Title: Efficient (sublinear) approximation algorithms for matrix-vector multiplication?
Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the *mean* matrix-vector product:

$$v = \frac{1}{n} Ax$$

If I did this using standard matrix-vector multiplication, then it would take $O(np)$ operations. I am wondering if there exists an approximate approach that can do better (that is sublinear in $n$ or $p$).

# Answer
> 2 votes
One approach is to treat each component of the result as a separate approximation problem. In this case, we can assume that $A$ is a row vector, so really the problem is to approximate a dot product $\sum\_{i=1}^p a\_ix\_i$, or equivalently, to approximate the mean of the terms, $\frac1p\sum\_{i=1}^p a\_ix\_i$.

This can be done by selecting a random sample of the indices $1,\dots,p$, and taking the mean of $a\_ix\_i$ over the sample, and constructing the $z$ confidence interval, a standard statistical procedure. In order to apply a Central Limit Theorem type of result to show that this gives asymptotically correct confidence intervals, we would need some mild assumptions on the entries of $A$ and $x$ to ensure that, roughly speaking, the mean cannot be dominated by outliers in a small proportion of entries. If you had upper and lower bounds on the entries of $A$ and $x$, for instance, then you could use Hoeffding's inequality to bound the probability of the estimate exceeding a given margin of error.

Of course, this approach gives only a probabilistic approximation method; it cannot guarantee accuracy with 100% certainty. But this is not of practical significance, as long as the error probabilities can be made sufficiently low. And in any case, it's not too hard to show that there cannot exist a deterministic approximation algorithm running in sublinear time, so probabilistic approximation is all that we could ask for in this case.

If a separate confidence interval for each component is not a desirable form for the output, then the approach could probably be adapted to instead give a margin of error for the norm of the error vector (e.g., with respect to the $\ell^1$, $\ell^2$, or $\ell^\infty$ norms).

---
Tags: algorithms, matrices, multiplication, numerical-algorithms
---


title: Some inference about NP

text:
# Question
Title: Some inference about NP
this is my first question on this site.

I recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me.

> I) each NP problem can be solved in Exponential Time.
>
> II) if P=NP then NP=NP-Complete.
>
> III) The following problem is in NP: given a natural number, determine whether it is the product of two prime factors.
>
> IV) if problem X can reduce to a known NP-Hard problem, then X must be NP-HARD.

anyone can verify my inference and learn me?

# Answer
If you define exponential time as $O(2^{n^k})$ for some $k$, then (i) is correct.

(ii) is almost correct – you have to exclude trivial problems (those in which all instances are yes instances or all instances are no instances).

What you describe (iii) is not quite a decision problem, so as stated it is not strictly true. The language consisting of all tuples $(n,k,i,b)$ such that the $k$th smallest prime factor of $n$ has $i$th bit equal to $b$ is in NP.

(iv) is incorrect – the empty language, for example, reduces to all NP-hard problems, but is not NP-hard itself. If some NP-hard problem Q reduces to a problem X then X is NP-hard: indeed any problem in NP reduces to Q (by definition of NP-hard), and through your reduction to X, and so by definition X is NP-hard.
> 6 votes

# Answer
> I) each NP problem can be solved in Exponential Time.

Correct. This is covered by an answer to our reference question (search for the heading "Brute-Force/Exhaustive-Search Algorithms for NP and NP$\\,\subseteq\\,$ExpTime").

> II) if P=NP then NP=NP-Complete.

Aaaaaaaalmost true. But false. The problems $\emptyset$ and $\Sigma^\*$ are the only two that would not be **NP**-complete if **P**$\\,=\\,$**NP**. These two are the problem where the answer is always "no" and the problem where the answer is always "yes". These two problems can't be **NP**-complete because a reduction from $X$ to $Y$ is required by definition to map "yes" instances of $X$ to "yes" instances of $Y$, and map "no" instances to "no" instances. But $\emptyset$ has no "yes" instances and $\Sigma^\*$ has no "no" instances so you can't define a reduction from any other problem to one of those.

> III) The following problem is in NP: given a natural number, determine whether it is the product of two prime factors.

True. This can be shown using the certificate definition of **NP**: a problem is in **NP** if there is a polynomial $p$ such that every "yes instance" $x$ of the problem has a certificate $y$ with $|y|\leq p(|x|)$ and there's a deterministic polynomial-time algorithm that, given an instance and a certificate, checks that the instance really is a "yes" instance.

In this case, the certificate is the two prime numbers. Given $x$ and prime numbers $y\_1$ and $y\_2$, we can check in polynomial time that $y\_1$ and $y\_2$ really are prime (using the AKS algorithm) and that $x$ really is $y\_1y\_2$.

> IV) if problem X can reduce to a known NP-Hard problem, then X must be NP-HARD.

False. Informally, "$X$ reduces to $Y$" means "If I can solve $Y$, then I can solve $X$." However, if $Y$ is hard and solving $Y$ lets you solve $X$, that doesn't necessarily mean that solving $X$ was hard: going via $Y$ might have been a really dumb move. (Practical example: suppose you're hungry and have no food. If you had a Ferrari, you could sell the Ferrari and use the money to buy food. This is a reduction from the problem of getting food to the problem of getting a Ferrari. But that doesn't mean that getting food is as hard as getting a Ferrari.)
> 7 votes

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


title: Constructing Epsilon-closures

text:
# Question
Title: Constructing Epsilon-closures
I am recently learning about automaton and I was confused at an exercise that was given to me.

In the lecture, we were given this exercise: Given a FA with transitions $$\begin{array}{c|ccc} & a & b & \epsilon \\ \hline q\_1 & \varnothing & \varnothing & \\{q\_2\\} \\ q\_2 & \\{q\_3, q\_4\\} & \varnothing & \varnothing \\ q\_3 & \varnothing & \\{q\_4\\} & \\{q\_2\\} \\ q\_4 & \\{q\_5\\} & \varnothing & \\{q\_3,q\_5\\} \\ q\_5 & \varnothing & \varnothing & \varnothing \end{array}$$ With $E(\\{q\_1\\}) = \\{q\_1, q\_2\\},E(\\{q\_2\\}) = \\{q\_2\\},E(\\{q\_3\\}) = \\{q\_2, q\_3\\},E(\\{q\_4\\}) = \\{q\_2, q\_3,q\_4, q\_5\\},$

how do you construct something as $E(\\{q\_1, q\_3, q\_5\\}) = \\{q\_1, q\_2, q\_3, q\_5\\}$?

# Answer
> 3 votes
If $s\_i$ are states in the original FA, then the $\epsilon$-closure, $$ E(\\{s\_1, \dotsc, s\_n\\})=\bigcup\_{i=1}^nE(\\{s\_i\\}) $$ so in your example we'll have $$\begin{align} E(\\{q\_1,q\_3,q\_5\\})&=E(\\{q\_1\\})\cup E(\\{q\_3\\})\cup E(\\{q\_5\\})\\ &= \\{q\_1, q\_2\\}\cup \\{q\_2, q\_3\\}\cup\\{q\_5\\}\\ &= \\{q\_1, q\_2, q\_3, q\_5\\} \end{align}$$ It's the set of all states reachable from $q\_1$ or $q\_3$ or $q\_5$ by either staying where you are or by following $\epsilon$-moves.

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


# Question
Title: Is there a theory/abstraction behind OOP?
Functional programming has the very elegant Lambda Calculus and its variants as a backup theory. Is there such a thing for OOP? What is an abstraction for the object oriented model?

# Answer
> 16 votes
There are four main approaches, though these only scratch the surface of what is available:

* via lambdas and records: the idea is to encode objects, classes and methods in terms of more traditional constructs. Benjamin Pierce's work from the mid 90s is representative of this approach.
* Abadi and Cardelli's object calculi (see Abadi and Cardelli's book *A Theory of Objects*: their main abstraction is a record of methods, and the approach is closer to the prototype-based realisation of object-oriented programming, though classes and inheritance can be encoded in terms of the more primitive elements.
* Castagna's multimethod calculus (see Castagna's book *Object-Oriented Programming A Unified Foundation*): his approach takes multimethods are the key abstraction.
* Class-based calculi (such as in Kim Bruce's book *Foundations of Object-oriented Languages: Types and Semantics* or Featherweight Java): these approaches aim to capture the essence of class based programming and focus on classes and inheritance.

# Answer
> 12 votes
The connection between object model core and set theory is described in the following documents:

The documents present the structure of instance and inheritance relations between objects. Such a structure can be considered the highest possible abstraction of OOP. It is shown how the structure applies to particular programming languages (Ruby, Python, Java, Scala, Smalltalk-80, Objective-C, CLOS, Perl, Dylan, JavaScript) and also to ontology languages (RDF Schema and OWL 2 Full).

In the documents, the *classes are objects* approach is taken so that the core structure is single-sorted. In the main form, the structure can be expressed as *(O,* ϵ*, ≤, .ec)* where

* *O* is the set of *objects*,
* ϵ is the *(object) membership* relation, a refinement of the *instance-of* relation,
* ≤ is the *inheritance relation*, and
* *.ec* is the *powerclass map* which is a distinguished, possibly empty, subrelation of ϵ.

A sample core structure according to the Ruby object model is shown by the following diagram. Green links show the inheritance relation in the reflexive transitive reduction, blue links show the membership relation in the "subsumption reduction" – a blue link from *x* points to the least container of *x*. The powerclass map *.ec* is formed by horizontal blue links. Objects from the image of this map are *powerclasses* (in gray). In Ruby they are called *eigenclasses* or also *singleton classes* (the latter term being rather deprecated). Objects *s*, *u* and *v* (in pink) are *terminal*, the remaining objects are descendants of the *inheritance root* *r*.

`r = BasicObject; c = Class; A = c.new(r); B = c.new(A); s = A.new; u = B.new; v = B.new; class << s; end; class << v; end`

Core parts of the object model of all the above languages can be seen as specializations of the structure, with no or just a few additional constituents. From the theoretical point of view, the most significant case of an additional constituent is the *singleton map* (denoted *.ɛϲ*) introduced by Dylan. This makes Dylan the only programming language (from the above mentioned) thas is not subject to the monotonicity condition (≤) ○ (ϵ) ⊆ (ϵ) where the composition symbol ○ is interpreted left-to-right.

One way to formalize the connection between object model core and set theory is via the family of structures *(O, ≤, r, .ec, .ɛϲ)* called *metaobject structures* in the referenced documents since *x.ec* or *x.ɛϲ* can be considered as metaobjects of *x*. In these structures *x.ec* is defined for every object *x* and *x.ɛϲ* is defined for every *bounded* ("small") object *x*. The structures are subject to the nine axioms below. The axiomatization uses a definitional extension which is quite simple for the first eight axioms (*T* denotes the set of terminal objects – those which are not descendants of *r*, and *.ec* is the reflexive transitive closure of *.ec*) but rather involved for the last axiom.

1. Inheritance, , is a partial order.
2. The powerclass map, *.ec*, is an order-embedding of *(O, ≤)* into itself.
3. Objects from *T.ec* are minimal.
4. Every powerclass is a descendant of *r*.
5. The set *r.ec* has no lower bound.
6. The singleton map, *.ɛϲ*, is injective.
7. Objects from *O.ɛϲ.ec* are minimal.
8. For every objects *x*, *y* such that *x.ɛϲ* is defined, *x.ɛϲ ≤ y.ec ↔ x ≤ y*.
9. For every object *x*, *x.ɛϲ* is defined ↔ *x.d \< ϖ*.

In the last axiom, *ϖ* is a fixed limit ordinal, and *.d* is the *rank* function derived by the definitional extension. The object membership relation, ϵ, is obtained as ((*.ɛϲ*) ∪ (*.ec*)) ○ (≤). According to the last axiom, the domain-restriction of ϵ to the set of bounded objects equals (*.ɛϲ*) ○ (≤). In the referenced documents, this relation is called *bounded membership* and denoted ∊. As a significant characteristics, this relation is well-founded. This is in contrast to ϵ which is non-well-founded since *r* ϵ *r*. It turns out that the main correspondence between (the core part of) object technology and set theory can be expressed as

**∊ ↔ ∈**

i.e. bounded membership corresponds to set membership between well-founded sets. As a special case, the partial von Neumann universe of rank *ϖ+1* is a metaobject structure by definitional extension. In general, every abstract (*ϖ+1*)-*superstructure* *(O,**)* is definitionally equivalent to a *complete* metaobject structure. Every metaobject structure can be faithfully embedded into a complete metaobject structure which in turn can be faithfully embedded into the von Neumann universe.

The term *basic structure* is used for a generalization of metaobject structures. In this generalization, *.ec* and *.ɛϲ* are allowed to be (arbitrarily) partial, possibly empty. In particular, finite basic structures are possible, with the minimum structure containing just the inheritance root *r*. Every basic structure can be extended to a metaobject structure by a powerclass completion followed by a singleton completion which in turn makes basic structures faithfully embeddable into the von Neumann universe.

---
Tags: terminology, lambda-calculus, functional-programming, object-oriented
---


# Question
Title: Priority queue with unique elements and sublinear time merge?
Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.

I am looking for a priority queue that merges in (expected|average|amortized|worst-case) *sub-linear* time, but also has the following properties:

* Elements are unique
* `peek` and `pop` should work in (expected|average|amortized|worst-case) *sub-linear* time

Is this impossible?

# Answer
> 4 votes
Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked list should be sorted by the size of the buckets, though not their key values.

To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.

Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.

The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a\>1$. We split into two cases depending on whether $a \< \lg^2 n$.

If $a \< \lg^2 n$, then we join the lists by merging them like in merge sort, so that the buckets stay sorted by size. Since the buckets have size $O(\lg^2 n)$, the linked lists have length $O(n/\lg^2 n)$ and $O(an/\lg^2 an)$, so merging them takes time $O(an/\lg^2 an)$ which is $o(an)$, and so is sublinear.

It also may increase the potential. Each bucket gets at most $O(\lg^2 (1+a)n - \lg^2 n) = O(\lg^2 (1+a) + \lg n \lg (1+a))$ closer to criticality. This is $O(\lg n \lg \lg n)$, and there are $O(an/\lg^2 an)$ buckets, so the increase in potential is at most $O(an \lg n \lg \lg n/\lg^2 an)$, which is $o(an)$ and thus sublinear.

Finally, we traverse the head and tail of the list, splitting and joining supercritical buckets until no supercritical buckets are left. This is "free", paid for by the potential we release. (To place them properly, we need to maintain a finger to the point in the list where buckets are exactly the right size. This is $O(1)$ extra work on each operation.)

If $a \> \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.

Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.

extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.

Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.

# Answer
> 0 votes
How about using a Strict Fibonacci Heap? - Here are the **worst-case** complexities:

$$\mathcal{O}(1) \text{ find-min}$$ $$\mathcal{O}(\log\_2 n) \text{ delete-min}$$ $$\mathcal{O}(1) \text{ insert}$$ $$\mathcal{O}(1) \text{ decrease-key}$$ $$\mathcal{O}(1) \text{ merge}$$

Brodal, Gerth Stølting, George Lagogiannis, and Robert E. Tarjan. “Strict Fibonacci Heaps.” In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 1177–84. STOC ’12. New York, NY, USA: ACM, 2012. doi:10.1145/2213977.2214082.

PS: I am not 100% sure how it works with unique elements, but I'd imagine that if it's unsupported it'd be trivial to add onto the delete-min step; at $\mathcal{O}(k \log\_2 n)$. Or maintain a hashtable also, to remove the $k$ term at the insert step.

---
Tags: algorithms, data-structures, trees, priority-queues
---


# Question
Title: Could an NP-Hard problem be in P in after a basis transform?
I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked.

So here goes:

Take the following problem for example:

Let $x\[n\]$ be a real valued discrete signal of length $N$.

It is known that the signal is of the form $$x\[n\] = sin(an) + sin(bn) + sin(cn)$$ where $a,b,c$ are some real valued constants.

We want to find $a,b,c$ , the 3 frequencies composing $x\[n\]$.

Now lets assume a parallel universe which somehow doesn't know of the Fourier transform. The only way they could propose to solve the problem (that I can think of) would be some form of grid search over $a,b,c$ which would seem to be exponentially hard.

Given the Fourier transform, one could solve the problem in poly-time.

So my question is: could some problems we think are NP-hard just seem that way because we haven't yet found the "magic" transform to change them into a basis which bring the problem to be solvable in poly-time?

I know that I haven't given the full formal formulation of the problem, and probably the catch is that even without Fourier the problem isn't NP hard.. but I'm still curious about how to refute the claim that there *could* exist a basis transform which would make an NP-hard problem solvable in poly time.

# Answer
> 5 votes
> The only way they could propose to solve the problem (that I can think of) ... would seem to be exponentially hard."

That's your core fallacy, and "that I can think of" is the answer. The complexity of the problem did not change, but the transformation made finding an efficient algorithm easier (as a tool).

Yes, it's certainly possible that we have yet to find a similar tool that, once we have it, allows even our feeble minds to easily find efficient algorithms for NP-hard problems. That would be a constructive and generalisable proof for P=NP, that is something like a holy grail.

# Answer
> 2 votes
An efficient change of basis doesn't change the hardness of a problem. Consider some decision problem $Q\_1$, which consists of all objects $x$ of some type that satisfy some property. Now let $f$ be an efficient (polytime) transformation whose inverse $f^{-1}$ is also efficient, and consider the decision problem $Q\_2$ = { f(x) : x \in Q\_1 }$. Then:

1. $Q\_1$ is in P iff $Q\_2$ is in P.
2. $Q\_1$ is in NP iff $Q\_2$ is in NP.
3. $Q\_1$ is NP-hard iff $Q\_2$ is NP-hard.
4. $Q\_1$ is NP-complete iff $Q\_2$ is NP-complete.

The proofs are not too difficult and left as an exercise.

As a concrete example, (undirected) graphs can be represented either as adjacency matrices or as adjacency lists. Assuming the graphs in question are not abysmally sparse, there are efficient transformations going both ways, so that from the point of view of graph problems, both representations result in the same complexity (in the sense discussed above).

# Answer
> 1 votes
Could a problem we think is NP-hard actually be solvable in polytime? Sure. We could be wrong (we suspected/guessed it was NP-hard, but our suspicion/guess was wrong). Or, it could be NP-hard *and* solvable in polytime, if P = NP.

I think the root problem is that you're confusing "a NP-hard problem" with "a problem we think is NP-hard". Those two are not the same. We routinely think all sorts of things that later turn out not to be true. Hey, that's life.

This is one reason why theoretical computer science is so focused on proofs: to avoid (or minimize) the situation where we thought/guessed/suspected/assumed something was true, and then later discover it actually wasn't.

---
Tags: complexity-theory, time-complexity, np-complete, p-vs-np, fourier-transform
---


title: Markov Chain w/ non-stochastic matrix

text:
# Question
Title: Markov Chain w/ non-stochastic matrix
I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges *leaving* a node do not sum to 1. However,the probabilities on edges *entering* the node do sum to 1. Therefore the transpose of the transition matrix IS stochastic.

I've built up a model in excel and noticed a few properties of this "transpose markovian process":

1. all nodes reach the same steady state value.
2. the steady state \*is\* dependent on the initial state (unlike a markov process).
3. the steady state value can be computed as S0 x MT (the initial state vector times the transpose of the markovian steady state vector... obtained by transposing the transition matrix and solving as a markov process).

My question is this: **Is there a name for such a process?** In searching for it I've found it to be beyond obscure, so my hope is some well-informed human can catalyze me with some search terms.

# Answer
No, there's no standard name for a process where the transpose of the transition matrix is stochastic (at least, to my knowledge).

However, this process is the time-reversal of a Markov process. That's a remarkable and descriptive property that just about completely characterizes this process. In particular, it seems likely that many things we'd want to know about such a process can be derived from the fact that it's the time-reversal of a Markov process, plus known facts about Markov processes.

Anyway, if you need to describe the process, "time-reversal of a Markov process process" is probably about as good as you're going to get.
> 1 votes

---
Tags: probability-theory, markov-chains
---


title: P-Completeness and Reducibility

text:
# Question
Title: P-Completeness and Reducibility
I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance.

The problem I'm stuck on is proving that the empty language and $\\{0, 1\\}^\*$ are the only languages in **P** that are not complete for **P** with respect to polynomial-time reductions (problem 34.3-6 in CLRS 3rd edition). The first part of the problem seems fairly straightforward enough (proving the empty language criteria). However, I'm not sure where to even begin when I have to prove the criteria for $\\{0, 1\\}^\*$. I'm NOT looking for the answer, however I would appreciate some guidance on how I can begin to think about this problem.

# Answer
**Hint.** The definition of reduction from $X$ to $Y$ requires that "yes" instances of $X$ be mapped to "yes" instances of $Y$ and "no" instances to "no" instances.
> 4 votes

---
Tags: complexity-theory, reductions, polynomial-time
---


# Question
Title: Kleene star property: proving $(A^+)^* = A^*$
I should prove that $(A^+)^\* = A^\*$ in a very formal way, any hints?

# Answer
When proving $L\_1 = L\_2$, one common pattern is proving $L\_1 \subseteq L\_2$ and $L\_2 \subseteq L\_1$. For proving $L\_1 \subseteq L\_2$, one common pattern is showing that if $x \in L\_1$ then $x \in L\_2$. In your case, this means you need to prove two things:

1. If $x \in (A^+)^\*$ then $x \in A^\*$.
2. If $x \in A^\*$ then $x \in (A^+)^\*$.

Try to use the definitions of $A^\*,A^+,(A^+)^\*$.
> 2 votes

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


title: Prove A² is regular

text:
# Question
Title: Prove A² is regular
Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?

# Answer
This holds more generally:

*Theorem*. If $X$ and $Y$ are regular languages, then their concatenation $$ X\cdot Y = \\{xy\mid x\in X, y\in Y\\} $$ is regular. This is a standard result that can be found in almost any introduction to regular languages. The idea (it's Theorem 1.4.7 in the linked notes) is to have finite automata $M\_X, M\_Y$ for languages $X$ and $Y$ and then construct a new FA for $X\cdot Y$ by "gluing" the final states of $M\_X$ to the start state of $M\_Y$ by $\epsilon$-moves.

The intuition here is that unlike the language $$ 2A=\\{aa \mid a\in A\\} $$ where a machine to recognize a word in $2A$ would have to "remember" $a$ and somehow determine that the first half matches the second half, no such burden holds for $A\cdot A$: all a recognizer has to do is nondeterministically guess where the split occurs and then check that the first part of the word is in $A$ and the second part is also in $A$. In this situation, there's no need to remember the first part and then match it to the second.
> 5 votes

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


# Question
Title: Finding stabbing numbers for lines for a set of segments in the plane
So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the plane \*(not necessarily axis aligned). The set of segments is fixed but the number of query lines could be large. I was thinking about maybe dualizing the problem: Each line segment turns into either an infinite "bow tie" or a horizontal band, and then we can compute the overlay of this arrangement, counting the number of intersecting regions inside each cell. But even though this becomes a pretty nice data structure, query time is still an issue. Any thoughts on how to make preprocessing time and stabbing query time low, assuming there will be a "somewhat large" number of queries (the tradeoff between preprocessing time and total query time is somewhat a parameter in this).

# Answer
> 2 votes
Are you familiar with

> H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl, D. Wood. "Stabbing line segments." *BIT Numerical Mathematics*. 1982, Volume 22, Issue 3, pp 274-281. (Springer link.)

Google Scholar finds more than 100 papers that cite it.

One can use a segment tree data structure, or an interval tree. Segment trees offer $O(\log n + k)$ query time, where $k$ is the number of segments intersected. Space complexity is $O(n \log n)$.

---
Tags: computational-geometry
---


# Question
Title: Existence of functions that only tests memberships without revealing any information about the members
Given a set of strings $\\{s\_1, s\_2, \cdots, s\_n\\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically or probabilistically), BUT no adversary can ever learn/extract any (member) strings from the program (in polynomial time)?

Can we have such functions with computational assumptions (such that they are secure even in the post quantum regime)?

---

Note: We can also entertain a program that takes, as input, a valid $s$ that is a member of P, to verify the membership of $s'$.

# Answer
> 3 votes
Yes. This is known as the problem of obfuscating a point function. There are standard schemes. See, e.g., the following papers:

On Obfuscating Point Functions. Hoeteck Wee. STOC 2005.

Technically, a point function is a function $f\_s(x)$ given by $f\_s(x)=1$ if $x=s$ and $f\_s(x)=0$ for all $x \ne s$. There are standard schemes for obfuscating point functions. This corresponds to the special case of your problem where $n=1$ (hiding a single value $s$). However, the techniques all generalize to arbitrary $n$, as long as the number $n$ of values is exponentially small compared to the size of the domain of the function.

# Answer
> 0 votes
You can use a one-way permutation. Pad all strings to the same length. Let $f$ be a one-way permutation. Store $S = \\{f(s\_1),\ldots,f(s\_n)\\}$. You can test whether $x \in \\{s\_1,\ldots,s\_n\\}$ by checking whether $f(x) \in S$. However, depending on the security properties of $f$, you shouldn't be able to learn anything about $S$ without a lot of effort.

# Answer
> 0 votes
One way to do this is to compute and store a secure hash of the each of the strings (e.g., using SHA). Then the program $P$, given a string, checks to see if its hash is among the stored list of hashes. A one-way permutation could be used, instead of a hash, but this would require more time and space (especially if the strings are long, relative to the secure hash size). However, the drawback of using a hash, rather than a one-way permutation, is that it is theoretically possible that the program can give a false positive output, i.e. incorrectly say a string was in the list when it in fact was not; but such false positive cases in practice will never be observed (barring some major algorithmic/technological breakthrough), provided the hash size is chosen large enough.

Of course, there is a potential attack of simply trying the possible strings by brute force; this will be a problem if some of the strings are short or are formed in a predictable way.

In any case, it would not be easy to mathematically prove that an attacker with a classical computer can never extract any strings from $P$ in polynomial time (much less could we prove that the scheme is secure even against attacks from a quantum computer). Such a proof would give a proof that $P \neq NP$, since if an attacker could solve NP-complete problems in polynomial time then they could extract the strings in polynomial time as well.

---
Tags: data-structures, reference-request, strings, security, dictionaries
---


# Question
Title: Rearranging linear tree with right rotates
I ran into a fun interview question, yesterday. Can anyone help me?

> Suppose a binary tree with six nodes is given, such that each node has only a left child. With how many "right rotate" operations (without any left rotates), we can convert this tree to a tree in which each node has only a right child?

# Answer
Just so we're on the same page, here's what a right rotation about node $x$ will do:

Where $T, U, V$ are the subtrees of nodes $x$ and $y$. It's easy to see that if you start with a left-child chain consisting of nodes $x$ and $y$ as above (with $T,U,V$ empty), a right rotation about $x$ will yield the right-child chain in the right figure.

Now do the same thing, starting with a left-child chain of three nodes, $x,y,z$, reading from the top. If you do a right rotation about $y$ and then another about $x$, you'll have the following transformations:

and now if you recursively transform the $x,y$ left-child branch (since we know how to do that), you'll wind up with a right-child tree, $z,y,x$, reading from the top. It shouldn't be hard to see that this process will work for left-child chains of arbitrary length $n$, and will require $n(n-1)$ rotations, so no more than that number of right rotations will change a left-child tree to a right-child tree.

It's worth noting that, although the question didn't require it, this process will maintain the binary search tree property, giving the nodes in the reverse order of the original.
> 1 votes

# Answer
If the chain has $n$ nodes, $n-1$ right rotations around the root will do the trick.
> 1 votes

---
Tags: algorithms, data-structures, trees, binary-trees
---


# Question
Title: Standard constructive definitions of integers, rationals, and reals?
Natural numbers are defined inductively as (using Coq syntax as an example)

```
Inductive nat: Set :=
| O: nat
| S: nat -> nat.

```

Is there a standard way to define integers (and maybe other sets like rationals and reals) constructively?

# Answer
There are multiple ways to define a mathematical structure, depending on what properties you consider to be the definition. Between equivalent characterizations, which one you take to be the definition and which one you take to be an alternative characterization is not important.

In constructive mathematics, it is preferable to pick a definition that makes constructive reasoning easy. For natural numbers, the basic form of reasoning is induction, which makes the traditional zero-or-successor definition very much suitable. Other sets of numbers don't have such a preference.

When reasoning on quotients, in non-constructive settings, it is common to say “pick a member of the equivalence class”. In a constructive setting, it is necessary to describe how to pick a member. This makes it easier to go with definitions that construct one object for each member of the type, rather than constructing equivalence classes.

For example, to define $\mathbb{Z}$, a mathematician might be happy with equating differences of natural numbers: $$\mathbb{Z} := \mathbb{N}^2 / \\{((x,y),(x',y')) \mid x + y' = x' + y\\}$$ While this has a tidy feeling to it (no “this or that”), for constructive reasoning, it's simpler if equality of objects coincides with equality of representations, so we might define the relative integers as either a natural number or the negative of a natural number minus one:

```
Inductive Z1 :=
  | Nonnegative : nat -> Z1   (* ⟦Nonnegative x⟧ = ⟦x⟧ *)
  | Negative : nat -> Z1.     (* ⟦Negative x⟧ = -⟦x⟧-1 *)

```

However, this definition is oddly asymmetric, which can make it preferable to admit two different representations for zero:

```
Inductive Z2 :=
  | Nonnegative : nat -> Z2   (* ⟦Nonnegative x⟧ = ⟦x⟧ *)
  | Nonpositive : nat -> Z2.  (* ⟦Nonpostitive x⟧ = -⟦x⟧ *)

```

Or we can build the relative integers without using the naturals as a building block:

```
Inductive Pos3 :=
  | I : Pos3                  (* ⟦I⟧ = 1 *)
  | S3 : Pos3 -> Pos3         (* ⟦S3 x⟧ = ⟦x⟧+1 *)
Inductive Z3 :=
  | N3 : Pos3 -> Z3           (* ⟦N3 x⟧ = -⟦x⟧ *)
  | O3 : Z3                   (* ⟦O3⟧ = 0 *)
  | P3 : Pos3 -> Z3           (* ⟦P3 x⟧ = ⟦x⟧ *)

```

The Coq standard library uses yet another definition: it constructs positive integers from their notation is base 2, as the digit 1 followed by a sequence of digits 0 or 1. It then constructs `Z` like `Z3` from `Pos3` above. This definition also has a unique representation for each integer. The choice of using binary notation is not for easier reasoning, but to produce more efficient code when programs are extracted from proofs.

Ease of reasoning is a motivation in picking a definition, but it is never an insurmountable factor. If some construction makes a particular proof easier, one can use that definition in that particular proof, and prove that the construction is equivalent to the other construction that was chosen as the definition originally.

For rational numbers, it's difficult to escape quotients, unless we start from a representation of integers as a product of factors (which makes some fundamental operations such as addition and the total ordering on $\mathbb{N}$ difficult to define). The Coq standard library defines `Q` as $\mathbb{N} \times \mathbb{N}^\*$ (numerator and denominator), and defines an operator `=?=` to test the equivalence of two elements of `Q`. This definition is pretty common because that's as simple as it gets.

Real numbers are a whole different kettle of fish because they are not constructible. It is impossible to define the real numbers as an inductive type (all inductive types are denumerable). Instead, any definition of the real numbers has to be axiomatic, i.e. non-constructive. It is possible to construct denumerable subsets of the real numbers; the way to do that depends on what subset you want to construct.
> 13 votes

# Answer
Gilles answer is a good one, except for the paragraph on the real numbers, which is completely false, except for the fact that the real numbers are indeed a different kettle of fish. Because this sort of misinformation seems to be quite widespread, I would like to record here a detailed rebuttal.

It is not true that all inductive types are denumerable. For example, the inductive type

```
Inductive cow :=
   | nose : cow
   | horn : (nat -> cow) -> cow.

```

is not denumerable, for given any sequence `c : nat -> cow` we may form `horn c` which is not in the sequence by well-foundedness of cattle. If you want a correct statement of the form "all inductive types are countable" you have to severely limit the allowed constructions.

The real numbers cannot be easily constructed as an inductive type, except that in homotopy type theory they can be constructed as a *higher inductive-inductive type*, see Chapter 11 of the HoTT book. It could be argued that this is cheating.

There are a number of *constructive* definitions and constructions of the reals, contrary to Gilles claim. They can be broadly divided into two classes:

1. **Cauchy-type constructions** in which the reals as seen as a metric completion of the rational numbers. This sort of construction often requires quotients, although one may be able to get away with a coiunductive definition, dependig on how one treats equality. A naive construction typically requires countable choice as well, but Fred Richman gave a completion procedure which works constructively without choice, see his Real numbers and other completions.
2. **Dedekind-type construction** in which the reals are seen as (two-sided) cuts of rationals. This sort of construction usually requires powersets or a similar device, although it is possible to do it just with some basic $\lambda$-calculus and the axiomatization of the Sierpinski space $\Sigma$, see Dedekind reals in Abstract Stone Duality.

On the implementation side, we have various constructive formalizations of reals (but not the one in the Coq standard library which is just awful), for instance Robbert Krebbers's and Bas Spitters's Computer certified efficient exact reals in Coq.

For an actual implementation of *exact* real numbers I point you to Norbert Müller's iRRAM.

Lastly, Gilles remark about denumerable subsets of reals is off the mark. It is perfectly possible to construct or define uncountable sets, in whatever constructive setting you live. For example, the Baire space $\mathbb{N} \to \mathbb{N}$ of all sequences of numbers is *alway* uncountable, even if you think that every function is Turing-computable -- see my blog post for an explanation.
> 16 votes

---
Tags: arithmetic, dependent-types, coq
---


# Question
Title: Shortcut for "in the worst-case, with high probability"?
I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after time, the following sentence:

> "With high probability, in the worst case, the performance of phase A is at most X".

The worst-case is with relation to the inputs; the high probability is with relation to the randomization of the algorithm. I.e, there is an adversary that choose the worst possible inputs, but then I do a lottery on which the adversary has no effect.

Since there are many phases, this sentence appears many times throughout the paper and it looks cumbersome. I tried to make it shorter by writing:

> "In the worst case (WHP), the performance of phase A is at most... "

This still looks cumbersome... Is there a more common way to express this meaning?

# Answer
> 1 votes
Your second example looks fine to me. "In the worst case, phase A takes time/space X whp" is even shorter.

---
Tags: terminology
---


# Question
Title: Christofides algorithm: why must an MST have even number of odd-degree vertices?
This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it.

I assume that a minimum spanning tree must have an even number of odd-degree vertices, since Christofides algorithm uses this fact to find a perfect matching between "the set of vertices with odd degree in $T$" - an impossible mission for a graph with odd number of vertices...

I couldn't convince myself why this is true, can someone please convince me? Either by a formal proof or with an informal explanation.

# Answer
> 5 votes
Every edge in a graph is incident with exactly two vertices. The degree of a vertex is the number of edges incident with it. From this you get the standard fact that the sum of all the vertex degrees in a graph equals twice the number of edges; in particular, it is even. A minimum spanning tree is a graph in its own right. If it had an odd number of odd-degree vertices, the sum of degrees would be odd, which is impossible.

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


# Question
Title: Memory cells (addresses) read into a cache
How does one determine what memory cells (addresses) are being read into a cache?

For example if we read at adress "C000EAFCH", which memory cells will be read into the cache if the cache is 64 byte and each cacheline is 8 byte?

If we use direct mapping, would one say that there are the 4 previous bytes and the 4 next bytes from the address that are being read?

In that case I would say that addresses C00EAF8H to C00EAFFH are being read. That would mean 4 bytes before the address, then the byte on the address and 3 more addresses are read.

However the one who asked this question wrote that the correct answer is C00EAF8 to C00EAFFH. I don't know why the 'H' disappeared in C00EAF8 but maybe it's a typo. To be honest I don't even know what the 'H' stands for, as it is not a hexadecimal character. Maybe someone can clarify this?

I also wonder, why doesn't one read the byte on the address, and then the next 7 bytes? Does this reading 4 bytes before and 3 bytes after have to do with direct mapping?

# Answer
> 2 votes
Cache lines are *aligned*. That means that the bottom-most bits of the start address of the cache line are always 0s.

If you have 8-byte cache lines they will always be read in address ranges $\[8i, 8(i+1) - 1\]$. For example, if you read address 117 (decimal) = 1110101 (binary) then the 8 byte cache block that gets read in is the set of bytes in the range 112 (decimal) = 1110000 (binary) through 119 (decimal) = 1110111 (binary).

---
Tags: cpu-cache
---


title: Running time of partial algorithms

text:
# Question
Title: Running time of partial algorithms
What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem of the given algorithm is decidable (with unknown complexity).

How is this time function of $n$ called? Is it studied in complexity theory, or does one only consider the running time of universally halting algorithms?

# Answer
> 1 votes
Given an algorithm $A$ (on inputs from some set $X$), we define the *runtime function* to be $T\_A(x) : X \to \mathbb{N} \cup \\{\infty\\}$ so that

$\qquad T\_A(x) = \begin{cases} \text{number steps } A(x) \text{ takes},\ \ &A(x)\\!\downarrow \\ \infty, &A(x)\\!\uparrow \end{cases}$

for all $x \in X$. I denote with $A(x)\\!\downarrow$ that $A$ terminates on $A$, and with $A(x)\\!\uparrow$ the opposite. Note that the number of steps an algorithm takes on an input depends on the computational model you choose, but we can leave that abstract here.

Now, the common way to define *worst-case* runtime is

$\qquad\displaystyle T\_A^{\mathrm{WC}}(n) = \max \\{ T\_A(x) \mid x \in X, |x| = n\\}$

which of course yields $\infty$ if there is any input of the given size for which $A$ loops. You want

$\qquad\displaystyle T\_A^{\mathrm{WC\downarrow}}(n) = \max \\{ T\_A(x) \mid x \in X, |x| = n, A(x)\\!\downarrow\\}$.

I don't know an established name for that one, but if I were to need one I'd go with *terminating-worst-case runtime*¹. That said, you probably use only one notion of runtime most of the time, so you can do as most authors do and say something along the lines of:

> From here on out, we always mean $T\_A^{\mathrm{WC\downarrow}}$ when we write "runtime" unless otherwise specified.

So yes, just use runtime but make very clear what you mean by that.

---

1. You notice that the definition of $T\_A^{\mathrm{WC\downarrow}}$ assumes that there is at least one input of every size for which $A$ terminates. You should handle the case if that fails.

---
Tags: complexity-theory, terminology, reference-request, time-complexity
---


title: Crossover method for genetic algorithm

text:
# Question
Title: Crossover method for genetic algorithm
I got an amount of numbers, they are shuffled and represent the individuals. For example (3,1,3,2,5,22,5) is one individual or (22,3,1,3,5,5,2).

Mutation is done quite easy by permutation within an individual.

The problem is to find a crossover method between 2 individuals, in which the quantity of the values stay the same(for the above example 2 times 3, 2 times 5, 1 time 22 and so on).
I searched a lot on it but only found crossover methods for either unordered / ordered lists. Those for ordered lists seemed promising but they require that every value only occur ones.

Do you know a method to solve this problem or got an idea for altering an crossover for ordered list method like PMX?

# Answer
You can choose a random threshold $t \leq n$ such that the first $t$ of the first individual is taken and then you take the rest from the other individual, so in your case, if $t = 4$, your new individual is $(3,1,3,2,22,5,5)$. As Richerby clarifies below, you take the first $t$ elements from the first individual and put the remaining $n-t$ elements in the order they appear in the second individual.

Making sure that you take the correct number is done by simply counting using a hashmap. Below, `correct_count` is a map from an element in an individual to the number of times it occurs, `ind1` and `ind2` are the two individuals you're trying to crossover.

```
correct_count = {}
for x in ind1:
    correct_count{x} += 1

t = random(n)
new_ind = ind1[0:t]
count = {}
for a in new_ind:
    count{a} += 1
for x in ind2:
    if count{x} != correct_count{x}:
        new_ind.append(x)
        count{x} += 1

```
> 1 votes

# Answer
I had the same problem as you and it took me a damn while to figure out the answer to this.

You need to look at keeping the same quantity of values as a separate objective (if you only had one objective before this will make it a multi-objective GA).

So if crossover produces a combination that changes one of the value quantities then give it a score of 0 for the keeping stuff the same objective; and if it has the same value quantities then give it a score of 1. You can then score your other objectives as you have been.

As for choosing the actual crossover method, see my other answer here. The crossover methods I talk about at the end are all crossover methods that are specific to ordered chromosomes.
> 0 votes

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: What is the optimal solution of the 1962 Procter and Gamble's TSP Contest?
In 1962, you could win a prize of \\$ 10 000 (about \\$ 80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Looking at the picture, the problem seems pretty easy. However I failed to find more detailed resources on the problem.

Does anybody know some more details, such as the exact distances and an optimal solution?

# Answer
Full details are in Robert L. Karg and James L. Thompson, *A Heuristic Approach to Solving Traveling Salesman Problems* (*Management Science*, **10**(2):225–248, 1964). The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not reproduce that here as it's way too much typing.

The solution is also illustrated on page 15 of *The Traveling Salesman Problem* by David L. Applegate, Robert E. Bixby, Vasek Chvátal and William J. Cook (Princeton University Press, 2007). The introduction to that book, which includes the relevant page, is freely available from the publisher.
> 17 votes

---
Tags: optimization, traveling-salesman
---


# Question
Title: DFA that recognizes 0 in every odd position
I had a question that asked for the DFA that accepts the following language:

```
{w | every odd position of w is a 0 }

```

Should this DFA accept the empty string, since it doesn't have an odd position?

# Answer
> 2 votes
Yes, since $|\epsilon| = 0$, there are no odd positions; therefore, that DFA would accept $\epsilon$.

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