title: Are Cellular Automata always computers?

text:
# Question
Title: Are Cellular Automata always computers?
I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.

In the introduction part:

> Cellular automata can be viewed as either computers or logical universes where computers may be embbed.

1. What i am trying to understand is, is it always a given Cellular Automaton is a computer ?

like Elementary Cellular Automata {ECA} rule 110 and rule 90, i know that rule 110 is universal which makes it a computer but what about rule 90 ... what about other ECA rules are they also computers ?
2. Suppose we have a cellular automaton (x), how do we know that it is a logical universe (as stated by the author), how can we know if it is a logical universe where computers can be embedd in or not and how can we know if it is just a computer ?
3. I know that logical universes are Cellular Automata, but what dimensions these universes should be to implement a computer easily, 1D like ECA or 2D like Conway's Game of Life ?

# Answer
> "... is it always a given Cellular Automaton is a computer?"...

I interpret "is a computer" as "being capable of universal computation" or in other words "being capable of simulating an arbitrary Turing machine".

The answer is clearly NO; a trivial example is a CA that doesn't modify the input:

```
0[0]0 -> 0
0[0]1 -> 0
0[1]0 -> 1
0[1]1 -> 1
1[0]0 -> 0
1[0]1 -> 0
1[1]0 -> 1
1[1]1 -> 1

```

(rule 204)

According to Wolfram's (*qualitative*) classification, only type-4 CAs exhibit a behaviour that can potentially be "universal". But it is an *informal statement* (like many others in Wolfram's NKS) ... in order to say that a particular CA is/is not Universal you must prove it formally.

For a more rigorous introduction to the argument I suggest you to read some research articles on the subject, for example: Kristian Lindgren, Mats G. Nordhal. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4 (1990) 299-318

Or - for a good, more general, introduction to computational universality - read *Chapter 7: The Grand Unified Theory of Computation* of the (IMO excellent) book: Cristopher Moore, Stephan Mertens. The Nature Of Computation (2011)
> 5 votes

---
Tags: computation-models, cellular-automata
---


# Question
Title: Is there a problem which can be solved in $O(f_k(n))$ time for any $k$ where $\lim_{k \to \infty} f_k(n) = 0$ but no constant time solution is known?
So Fibonacci heaps can perform insertions in amortized constant time, and I came up with a sequence of heap data structures $H\_k$ such that insertions can be performed in amortized $O((\log n)^{1/k})$ time where $n$ is the size of the heap. If we didn't know insertions could be performed in constant time, then my result would suggest it, since we can get arbitrarily close to constant running time asymptotics with my solution.

This led to me to wonder, is there an example of a family of algorithms or data structure operations, that are all functionally equivalent, and can be performed in $O(f\_k(n))$ time, where $f\_k$ is a sequence of functions such that $\lim\_{k \to \infty} f\_k(n) = 0$ for all $n$, but no constant time alogorithm/data structure operation can be found? Or at least where no constant time solution is currently known? I suspect the answer is yes but probably hard to prove. It would be very surprising if the existence of such family of algorithms with $O(f\_k(n))$ running time would imply a constant time algorithm exists.

# Answer
You can sort numbers in $O(\frac{n\log n}{k})$ for all fixed $k$, and $\lim\_{k\to\infty} \frac{n\log n}{k} = 0$ for all fixed $n$.
> 2 votes

# Answer
There's a somewhat similar problem involving multiplication of $n$-bit numbers. Toom-Cook multiplication is a family of algorithms that (ignoring some minor details) do multiplication in time $O(n^{f\_k})$, where $f\_k = (\log(2k-1))/\log k$. We have $\lim\_{k\to\infty}f\_k=1$ but there is no known way to multiply in time $O(n)$. (In fact, the fastest known multiplication algorithms don't quite attain $O(n\log n)$ time.)
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Delay Constrained Shortest Path in $O(D \cdot |E|)$ time
I have the following homework exercise:

> We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated source node s∈V and target node $t \in V$, where $w\colon E \to Z^+$ and $d\colon E \to Z^+$. The values $w\_{i,j}$ correspond to arc weights, $d\_{i,j}$ correspond to delays, i.e., using the arc $(i,j)$ requires $d\_{i,j}$ time. We are further given a positive number $D \in N$, the delay constraint. Develop an efficient, i.e., $O(D \cdot |E|)$, algorithm to find a shortest path $P$ from some $s$ to $t$, which does not exceed the global delay constraint $D$, i.e., $\sum\_{(i,j) \in P} d\_{i,j}≤D$ (Hint: use a similar approach as the one used in the Bellman Ford algorithm).

I was able to find an algorithm that runs in $O(D \cdot |E| \cdot |V|)$ time. However I'm struggling with finding an algorithm that runs in $O(D \cdot |E|)$ time and I'm starting to think, that such algorithm is not even possible to create (although I don't have a formal proof for this).

Could you give me a clue how would such an algorithm look like?

# Answer
As a hint, a dynamic programming method can be utilized to reach $O (|E| \ . D)$.

---

To elaborate, in this solution, we should consider two items, which can be saved in a two-dimensional array.

The first item holds vertex number, and, the second one maintains delay.

Pseudo-code: $dp \ \[vertex \ i\]\[delay\] = min (dp \ \[vertex \ j\]\[delay - d\_{i,j}\] + w\_{i,j}\ , \ dp \ \[vertex \ i\]\[delay\]);$

Therefore, the total time complexity is $O(|E| D)$.
> 1 votes

# Answer
Hint: For $1 \leq d \leq D$, compute inductively the shortest distance between $s$ and any other node at delay at most $d$. Each such iteration runs in $O(|E|)$, so the total running time is $O(D|E|)$. (This assumes that the graph is connected. Otherwise you have to replace $|E|$ with $|E|+|V|$.)
> 1 votes

---
Tags: algorithms, complexity-theory, optimization, shortest-path
---


# Question
Title: What is the effect of operating systems on execution speed?
I'm using a Raspberry Pi 2 which works with 900MHz. (Asked this question there and they think it belongs to cs)

My question is: since it also runs an operating system in the background, I expect this would take some of the processing power.

So, how significant is the speed reduction due to operating systems? If I run a single code for example, what execution speed should I expect on average? Is it still close to 900MHz, or is it significantly lower?

Furthermore, is there a specific operating system or programming language that I can use to make it run faster?

# Answer
> 5 votes
This question doesn't have a straight forward answer, or rather the answer is very case dependent. (And as some of the comments pointed out, attempting to qualify this as MHz is meaningless, your CPU will run at the same speed regardless {not counting power optimizations}, it's just a case of who's code it's running, yours or the OS's).

An operating system does many things for you so your simple code that does a couple of I/O operations wouldn't be as simple without calls to the operating system. To take the OS out of the equation, you'd have to write more code to replace device driver functionality. Your OS is doing a LOT of work just to accept that letter "A" you typed and display it on a screen.

If your I/O is to a file system, you'd have to write code to replace the file system code provided for you by the OS.

If you expect multiple tasks to run simultaneously or do multithreading, you'll also have to write code to replace the scheduling functionality.

If you allocate and deallocate memory, you'd have to write code to perform those functions.

If you want your program to be notified when an event occurs or keep time or any of a number of other functions, you'll have to supply all that code as well. And that's just PART of what an Operating System is doing.

You also have to consider that all that OS code that you're taking advantage of has been optimized and debugged for you. You're likely to write replacement code that is buggier and slower than the OS code you're replacing.

Then once you've got all that written, you'll have to figure out how to load the program into memory and start execution...

That said, there definitely IS overhead involved in using an operating system. Most OS's are built for a general use case and will have many features and functions that you don't need for your specific program. But most of us are willing to give up a few % of CPU and memory in order to get the convenience that an OS will bring.

As for which OS will make it go faster... again it depends on your application and needs. Some OS's will definitely run some applications faster than others, but which OS runs faster depends on the features being used.

And there are reasons other than speed to choose one over another. Application availability, security, interoperability, device compatibility, availability of programming tools, etc. are all factors to consider.

---
Tags: operating-systems
---


# Question
Title: Ambiguous Grammar and SLR parsing table : No conflicts?
We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-then-else grammar which is pretty much ambiguous.

So I started with the following rules ( as given in Principles of Compiler Design, Aho and Ullman, 2002 Reprint)

$$ S \rightarrow iCtSS' \\ S \rightarrow iCtS \\ S \rightarrow a \\ S' \rightarrow eS \\ S' \rightarrow \epsilon \\ C \rightarrow b \\ $$

S is the statement, and C is the condition. All apart from S', S and C are terminals, and epsilon refers to null.

The given grammar is written in a way that conforms to recursive descent parsing.

Augmented the grammar as

$$ S\prime\prime \rightarrow .S \\ S \rightarrow .iCtSS' \\ S \rightarrow .iCtS \\ S \rightarrow .a \\ S' \rightarrow .eS \\ S' \rightarrow .\epsilon \\ C \rightarrow .b \\ $$

And then generated the instances-set as

$$ I\_{0} \[ S\prime\prime \rightarrow .S, S \rightarrow .iCtSS', S \rightarrow .iCtS, S \rightarrow .a, S' \rightarrow .eS, S' \rightarrow .\epsilon, C \rightarrow .b\]\\ I\_{1} \[S \rightarrow i.CtSS', S \rightarrow i.CtS, C\rightarrow.b\]\\ I\_{2} \[S \rightarrow a.\]\\ I\_{3} \[S'\rightarrow e.S, S \rightarrow .iCtSS\prime, S \rightarrow .iCtS\]\\ I\_{4} \[S \rightarrow \epsilon.\]\\ I\_{5} \[C \rightarrow b.\]\\ I\_{6} \[S \rightarrow iC.tSS\prime, S\rightarrow iC.tS\]\\ I\_{7} \[S\prime \rightarrow eS.\]\\ I\_{8} \[S \rightarrow iCt.SS\prime, S \rightarrow iCt.S, S \rightarrow .iCtSS\prime, S\rightarrow.iCtS, S\rightarrow.a\]\\ I\_{9} \[S \rightarrow iCtS.S', S \rightarrow ICtS., S' \rightarrow .eS, S' \rightarrow .\epsilon\]\\ I\_{10} \[S \rightarrow iCtSS'.\]\\ $$

Based on these sets that I made, I constructed a parsing table

However, as per my derivation of the instance-sets, there were no conflicts in the table (the grammar being ambiguous), I was not sure if I worked it out correctly. One thing that adds to the dilemma that there has been no instance where S was the first non terminal in grammar, and so there are no states that can accept the final variable S during parsing.

Can anyone please help me with this? I checked it further online and they mentioned that the ambiguous grammar tended to have conflicts, but there were none in this case. Where am I going wrong?

Thanks.

# Answer
In state 9, you can reduce either $S$ or $S'$, as well as the possible shift action for $e$. So there are both reduce/reduce and shift/reduce conflicts.

The production $S' \rightarrow \epsilon$ cannot be correct; there is already a production $S \rightarrow iCtS$ for an if without an else, so if $S'$ can derive the empty string, $S \rightarrow iCtSS'$ is ambiguous. Once you remove that, you will still have the shift-reduce conflict with $e$. (Since an SLR parser doesn't use lookahead to restrict reduce actions, the entire row for a state with a reduce action must consist of precisely that reduce action. But this particular grammar is ambiguous, so using LALR(1), for example, won't help.)

Finally, $\epsilon$ is not a symbol; it is simply a way of making an empty symbol sequence visible. So it cannot be the head of a column the action table, and also it cannot be on the right hand side of the dot in an item.
> 2 votes

---
Tags: formal-grammars, compilers, parsers, ambiguity
---


title: Hash-Table in Practice

text:
# Question
Title: Hash-Table in Practice
I have a set of $n$ values,$v\_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number of buckets. Then, I use SHA hash function, $H$, to find the index a bucket in the hash-table and insert the values into the bucket:

$HT \[H(v) \bmod k\]=v\_i$

The **problem** is that the indices do not look uniformly at random, for instance 3 different values may map into a cell whereas an index may not appear at all. And this can lead overflow.

Notice that I need a deterministic way as two different parties encode their values using hash table. Therefore, if the parties use the identical parameters for hash table, the same values should be in the same bucket (of different hash tables). Obviously different party may have different set values.

**Question:** What is the best way of preventing overflow in the above scenario?

# Answer
SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that *random allocation is not as good as deterministic allocation*. If you knew all the values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the number of balls landing into each bin isn't $n/k$ but rather has roughly Poisson distribution with mean $n/k$ (assuming $n/k$ is "small"). Thus you expect there to be a few bins which do get quite a few balls more than their share, and vice versa. A good hash table should be able to handle that – there are several approaches that you are probably aware of.

A similar situation happens when you throw $n$ balls into *two* bins. Rather than each bin getting exactly $n/2$ balls, the number of balls in each bin has roughly normal distribution with mean $n/2$ and standard deviation $\sqrt{n}/2$. Thus you expect one bin to contain roughly $\sqrt{n}$ more balls than the other.

Another similar situation concerns throwing $n$ balls into $n$ bins. Rather than an even allocation, you expect the maximum cell to contain roughly $\log n/\log\log n$ balls. However, if any given ball is given *two* options, and you put it in the lighter bin, then the maximum cell contains only roughly $\log\log n$ balls in expectation. This is one way of coping with your problem.
> 7 votes

---
Tags: data-structures, hash, hash-tables, algorithm-design
---


# Question
Title: What is the algorithm for Shannon-Fano code? am I correct?
I am wondering what is the true algorithm for the Shannon-Fano code? The the result I am getting based on the Algorithm in Wikipedia page contradicts the supposed/expected length of the produced code. According to the proof of Kraft's inequality, $l\_i = \lceil \log\_2{\frac{1}{P\_i}} \rceil= \lceil -\log\_2{P\_i} \rceil$.

> A Shannon–Fano tree is built according to a specification designed to define an effective code table. The actual algorithm is simple:
>
> 1. For a given list of symbols, develop a corresponding list of probabilities or frequency counts so that each symbol’s relative frequency of occurrence is known.
> 2. Sort the lists of symbols according to frequency, with the most frequently occurring symbols at the left and the least common at the right.
> 3. Divide the list into two parts, with the total frequency counts of the left part being as close to the total of the right as possible.
> 4. The left part of the list is assigned the binary digit 0, and the right part is assigned the digit 1. This means that the codes for the symbols in the first part will all start with 0, and the codes in the second part will all start with
> 5. Recursively apply the steps 3 and 4 to each of the two halves, subdividing groups and adding bits to the codes until each symbol has become a corresponding code leaf on the tree.

*For example:*

$S\_1 \rightarrow P\_{S\_1} = \frac{4}{9} \rightarrow Code = 0 \mapsto$ And: $\lceil \log\_2{\frac{9}{4}}\rceil = 2 \neq 1$ Bad!

$S\_2 \rightarrow P\_{S\_2} = \frac{2}{9} \rightarrow Code = 10 \mapsto$ And: $\lceil \log\_2{\frac{9}{2}}\rceil = 3 \neq 2$ Bad!

$S\_3 \rightarrow P\_{S\_3} = \frac{2}{9} \rightarrow Code = 110 \mapsto$ But: $\lceil \log\_2{\frac{9}{2}}\rceil = 3 = 3$

$S\_4 \rightarrow P\_{S\_4} = \frac{1}{9} \rightarrow Code = 111 \mapsto$ And: $\lceil \log\_2{\frac{9}{1}}\rceil = 4 \neq 3$ Bad!

We can see that the length of produced Shannon-Fano code is $1$, but it supposed to be $2$. Which mean this algorithm is not correct. What is correct algorithm then?

**Additional note:** If we look at the example 1 of this document, we can see that the length of $A4$ is supposed to be $3$ not $4$. The same contradiction. Another contradiction in example 1 of this other document. I think it is clear what I am talking about.

**More additional note:** Here is the page 45 of this textbook -Information and Coding Theory (Springer Undergraduate Mathematics Series) 2000th Edition

# Answer
> 4 votes
You are confusing "Shannon coding" from "Shannon–Fano coding" (terminology could vary across sources). Per Wikipedia, Shannon–Fano coding is the algorithm you mention, while Shannon coding is any coding assigning a symbol occurring with probability $p\_i$ a codeword of length $\ell\_i = \lceil \log\_2 \frac{1}{p\_i} \rceil$. Per Wikipedia, Shannon–Fano coding always leads to codewords whose lengths are within one bit of $\log\_2 \frac{1}{p\_i}$. This is also a feature of Shannon coding, but the two need not be the same. In particular, Shannon–Fano coding always saturates the Kraft–McMillan inequality, while Shannon coding doesn't.

---
Tags: algorithms, coding-theory
---


# Question
Title: Is a Petri net without places well-defined?
I'm a bit confused about the definition of a Petri-Net. From Wikipedia (EN) I have this defintion:

> A Petri-Net is a 5-Tupel (P, T, F, W, s)
>
> P and T are disjoint finite sets of places and transitions, respectively.

So the defintion says: $P \cap T = \emptyset $ & $P \cup T \neq \emptyset $

Let's say T is $ \emptyset $ and P = { p } so both prerequisites are given. I think that is okay. We have a system which stays allways in one state and can not change to another so we do not need any other state or transition.

Now think about the other case: T = { t } and P is $ \emptyset $. Now we have a system which does not have a state. The transition can't do anything because we do not have any states and it does not have any meaningful meaning in this case.

So does any Petri-Net which has minimum one transition **need** two places? Or have I missed out something?

# Answer
> 3 votes
A net without place does have "state", or a marking in proper terminilogy; as that is a mapping from the set of places into $\Bbb N$, technically this does exist even when the set of places is empty (as a kind of empty relation).

A net with one place and one transition can even change state. If the transition has an outgoing arrow to the place, the transition can add tokens into the place. (Tokens can be created, they aren't physically moved from one place to another.) Effectively the behaviour will be that of a upward counter.

---
Tags: automata, petri-nets
---


# Question
Title: Difficult Question to Understand (Computer Artitechture)
You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is the minimum number of bits of state in the controller?

Answer: The system has at least five bits of state to represent the 24 floors that the elevator might be on.

**Can someone explain how this comes to be?**

# Answer
Well, as binary typically goes, one bit represents two possible values: 0 and 1. With two bits there are a possible combination of four values: 0, 1, 2, 3 in hex/decimal/octal or 00, 01, 10, 11 in binary. Expand out to three bits you have eight values. 0 to 7 or 000, 001, 010, 011, 100, 101, 110, and 111.

Expand upon this and you'll have your understanding.

For reference (with a nice animation for counting on any base): https://www.mathsisfun.com/binary-number-system.html
> 3 votes

---
Tags: computer-architecture, computer-algebra
---


# Question
Title: Can the processor just turn off the interrupt request line?
I was doing some of the interrupts question online and found this Multiple choice question

How can the processor ignore other interrupts when it is servicing one

a) By turning off the interrupt request line b) By disabling the devices from sending the interrupts c) BY using edge-triggered request lines d) All of the above

The answer was (D) but I wonder how are we allowed to turn off the interrupt request line ?

What if we have a high priority interrupt that comes after ? We just ignore it ? I mean (a) seems counter intuitive for me, because I don't think under any circumstances we should be turning off the interrupt request line ?

# Answer
It depends on the processor arhitecture, but yes, most processors can turn off interrupts. Shutting them completely off is usually only done in special situations like booting or critical error handling.

More commonly, interrupts are blocked until the CPU returns from the interrupt handling routines. These routines should typically do the minimum amount of processing required, then return from interrupt to finish any work (forking down to a lower level for most of the work).

An older system I'm most familiar with, the VAX architecture, allowed for multiple interrupt levels (up to 31) and when an interrupt occurred the CPU would run at an IPL level corresponding to that interrupt. All other interrupts at or below that IPL would be blocked until the IPL was lowered below the level of pending interrupts, then the pending interrupt would be delivered. There was also a SETIPL instruction that allowed critical system code to block certain types of interrupts while critical code executed. On single processor systems this was an effective synchronization technique that prevented multiple streams from changing data structures in an uncontrolled manor (multiprocessor systems required using other techniques like spinlocks). Some problem with blocking interrupts are that multiple pending interrupts would be delivered as a single event and devices with unserviced interrupts sometimes get timeout errors. So running at elevated levels for extended periods is discouraged.
> 2 votes

---
Tags: computer-architecture, operating-systems, process-scheduling
---


title: Determining HD Content

text:
# Question
Title: Determining HD Content
A storage system has 6 hard drives set up as RAID 5, where HD 6 is the parity disk using odd parity. One day, the system crashes due to failure of HD4. During recovery, we find out that HD1 stores 11110000; HD2 contains 10011100; HD3 contains 00011000; HD5 contains 10101010 and the parity disk contains 11110111.

What would be the content of HD4?

# Answer
A parity determines whether the amount of particular occurrences for something is even or odd. In this case, since the parity is odd, that means HD 6 stores a `1` for an odd amount of `1`s in that index for the remaining HDs and a `0` for an even amount of `1`s in that index.

Let's go over the contents again:

```
HD 1: 11110000
HD 2: 10011100
HD 3: 00011000
HD 4: ????????
HD 5: 10101010
HD 6: 11110111

```

This tells us that all indices contain an odd amount of `1`s when summing them from the remaining 5 HDs except the 3rd index (counting from 0 on the right), which has a `0` denoting an even amount of `1`s.

For each index, we can determine whether the remaining HD 4 contained a `0` or a `1` by matching the expected parity:

```
HD 1: 11110000
HD 2: 10011100
HD 3: 00011000
HD 4: 00101001
HD 5: 10101010
HD 6: 11110111

```

You can confirm that this is correct by counting the amount of occurrences of `1` in each column excluding HD 6.
> 2 votes

---
Tags: storage
---


# Question
Title: Is there a difference between total-ordering consistency and linearizability?
By *total-ordering* I mean the following definition\[0\]:

> Total Event Ordering: Controller replicas should process events in the same order and subsequently all controller application instances should reach the same internal state.

If my understanding is correct, there isn't any difference and the two words can be used interchangeably. However, I would like to make sure I am not mistaken.

In the case both concepts are different, could you stress their differences and perhaps provide an example? That would be very much appreciated!

Thank you,

\[0\] - https://www.cs.princeton.edu/~jrex/papers/ravana15.pdf

# Answer
> 4 votes
Total, FIFO and causal are all different sequential approaches for ordering the events. Now, consistency applies to all these types ordering and at different levels: local and global.

Sequential consistency requires that all of the operations appear to have executed atomically in some sequential order that is consistent with the order seen at a local level (individual process). This is similar to serializability used in database theory. Linearizability is another type of consistency, which applies when this order must also preserve the global ordering of non overlapping operations.

---
Tags: distributed-systems, consensus
---


# Question
Title: Number of ways of making change in Big O notation
I have the following algorithm in ML:

```
fun change(till,0,chg,chgs) = chg::chgs
|   change([],amt,chg,chgs) = chgs
|   change(c::till,amt,chg,chgs) = if amt<0 then chgs else change(c::till, amt-c,c::chg, change(till,amt,chg,chgs));

```

The algorithm takes a list of currency denominations as `till` and returns all the combinations of denominations which produce the amount `amt` specified.

And I am trying to show that the number of ways for making change for some value `n` regardless of order with two change values is `O(n)`. And then trying to figure out what it is for more change values.

It's clear that for one change value it is `O(1)` as there is only one possible way to make change but I'm not sure how to progress from there.

Any help would be much appreciated.

# Answer
> 1 votes
Suppose that the two denominations are $a$ and $b$. Every solution to the coin-changing problem is a solution to the equation $\alpha a + \beta b = n$ in non-negative integers $\alpha,\beta$. For every possible value of $\alpha$ there is at most one solution. Since $0 \leq \alpha \leq n/a$, we conclude that there are at most $n/a + 1 = O(n)$ solutions.

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


# Question
Title: What is the time complexity of this atrocious algorithm?
This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it:

```
def sort(list):
    if len(list) < 2:
        return list
    else:
        if list[0] <= minimum(list[1:]):
            return list[0:1] + sort(list[1:])
        else:
            return sort(list[1:] + list[0:1])

def minimum(list):
    return sort(list)[0]

```

I'm interested in working out the worst-case, best-case and average-case time complexity, but I've found myself insufficiently practiced to do so. I originally thought it would be O(n!), which would be equivalent to cycling through all possible permutations of the list, but because the results aren't even memoized I believe it's actually worse than that.

Mitigating that is the fact that not all of the recursive calls can possibly be worst-case, so I'm not even sure what the worst-case input is for the function overall.

However—even a **sorted** input of size 5 results in a total of 64 recursive calls, or $2^{n+1}$. This is best-case time complexity.

What *is* the worst case input for this algorithm, and what is the time complexity for worst case and average case?

# Answer
> 8 votes
We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running `sort` on a list of length $n$. When calling `sort` on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of `minimum`, and so takes $T(n-1) + O(n)$. The final one descends to sorting a list of length $n-1$. In total, we get the recurrence $$ T(n) = n T(n-1) + O(n^2). $$ Opening this recurrence, we get $$ T(n) = O(n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n!) = O(n!). $$ (We get $O(n!)$ since the terms decrease very quickly from $n!$ to $n^2$, faster than a geometric series.)

Of course, without giving a matching lower bound, we don't know whether this analysis is tight.

# Answer
> 2 votes
I was not careful and assumed a standard implementation of `minimum`, not the one given in the question. Hence, the answer below solves a much simpler problem.

---

Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align\*} T(\mathtt{\[\] | \[x\]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@\[x\]}, &\text{else}. \end{cases} \end{align\*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers `minimum`, `head` and `tail`, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the *reversely sorted* list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align\*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align\*}$

Solving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T\_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T\_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

# Answer
> 2 votes
Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align\*} T(\mathtt{\[\] | \[x\]}) &= d, \\ T(\mathtt{x::xs}) &= c + \begin{cases} 2 \cdot T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs}) + T(\mathtt{xs@\[x\]}, &\text{else}. \end{cases} \end{align\*}$

I assume some cost measure that is related to list operations. Note that I introduce $c$ for the toll function, which covers `head` and `tail`, as well as the other operations.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider *almost reversely sorted* lists with $n$ elements, i.e.

$\qquad \mathtt{L(n,i) = \[i, \dots, 1, n, \dots, i+1\]}$.

The recurrence from above then becomes:

$\qquad\begin{align\*} T'(\mathtt{L(\leq 1, \\\_)}) &= d, \\ T'(\mathtt{L(n,i)}) &= c + \begin{cases} 2 \cdot T'(\mathtt{L(n-1,n-1)}), & \mathtt{i} = 1; \\ T'(\mathtt{L(n-1,i-1)}) + T'(\mathtt{L(n,i-1)}), &\text{else}. \end{cases} \end{align\*}$

We see that we can express this in $n$ and $i$ only:

$\qquad\begin{align\*} T'(\leq 1,\\\_) &= d, \\ T'(n, 1) &= c+ 2 \cdot T'(n-1, n-1),\quad n \geq 2, \\ T'(n, i) &= c + T'(n-1,i-1) + T'(n, i-1)\qquad n \geq 2, 2 \leq i \leq n. \end{align\*}$

So we have $T\_{\mathrm{WC}}(n) \geq T'(n,n)$ (the running time on the reversely ordered list).

*To do:* solve the recurrence

Scribbles:

* $T'(n,n) = c(n-1) + \sum\_{i=1}^{n-1} T'(i+1,i)$
(by succesively unfolding the terms with smallest first parameter)

Note: bounding summands from below by $T'(i,i)$ yields a useless $2^n$ lower bound.

---

I *think* that the index of the smallest element is indeed the crucial quantity here. That would imply the following.

* $\mathtt{L(n,n)}$ is indeed a worst-case instance.

*Intuition:* There is no way you can enforce more rotations.
* Not much changes on the average, assuming the random permutation model. The rank of the minimum is $n/2$ in expectation, and removing the minimum maintains the distributive properties from one rotation phase to the next.

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


# Question
Title: benchmark data set for Metareasoning problem
I am developing algorithm for solving following problem:

Given a set of items with unknown feature(s) (but know distribution of feature(s)). Algorithm must choose what items to measure(every measure has some cost)). I use Value of information theory to find this measurements.

After measurements are done algorithm choose K best items from the set, using some utility function that depends on feature values of items.

I crafted few synthetic data sets, but perhaps there are some benchmark data sets that are used for this kind of problems?

Regards.

# Answer
> 1 votes
In this sort of situation, two standard answers are:

1. Figure out what the practical applications of your algorithm are. Find a dataset associated with that particular application, and try your algorithm on it and see how well it works. Measure success using some metric that is appropriate for that particular application.
2. Look through the research literature to find previously published papers that try to solve the same problem. Look at what benchmarks they used. Use the same benchmarks, so that you can compare how well your algorithm does to previously published algorithms.

---
Tags: machine-learning, data-sets
---


# Question
Title: Find the index of the next greatest element in the array
I know there is a stack based approach with O(N) complexity and O(N) space. Can B be created using O(1) space? Such as in place using a single loop or even some sorting algorithm ? If so, can you please provide a high level description of the algorithm ? I've been working on a solution for some time now and am unable to come up with anything.

# Answer
> 3 votes
It's not hard to work from right to left:

```
B[n] = n+1
for i = n-1 to 1
  j = i+1
  while A[i] >= A[j] and j < n+1
    j=B[j]
  end
  B[i]=j
end

```

I think that's similar to the stack-based algorithm.

Edit: This is listed in Wikipedia as also found by Barbay, Fischer and Navarro (https://en.wikipedia.org/wiki/All\_nearest\_smaller\_values):

Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations", Theoretical Computer Science 459: 26–41,

# Answer
> 1 votes
The output has size $n$. That gives you immediate $\Omega(n)$ lower bounds on space and time.

---
Tags: algorithms, arrays
---


title: How do threads decide when to 'go'?

text:
# Question
Title: How do threads decide when to 'go'?
I have written some code that animates two boxes using HTML5 and JavaScript threads. I set them up to move at a fixed rate, which is the same:

```
executeEvery(box1.animate(), 10);
executeEvery(box2.animate(), 10);

```

The result is weird for reasons not important here. This to me seems to be the two `executeEvery` calls not working in unison - probably some asynchronous issue. Because `animate()` is a complex function call, the threads behaviour is seemingly erratic.

I am asking here because I think this problem is deeper than a JavaScript issue. Why does this not work as intended?

# Answer
> 2 votes
There are (at least) four reasons.

1. They do not start at the same time. Before the second `executeEvery` is even found by the interpreter, the first one may already have executed some steps!
2. You don't even know if the platform supports parallelism. So you can only expect one move to be computed after the other; you *may* be able to control the relative speed (see below).
3. The threads themselves don't have any control over this (on most machines). Either a virtual or the actual machine runs a scheduler that decides which process or thread runs when. For the programmer, the only robust way to deal with this is by assuming non-determinism (i.e. arbitrary order).
4. `wait(10)` won't wait for exactly 10ms. Even active waiting can get you only so close to the exact time frame.

If you want to execute the updates simultaneously -- in the sense that both boxes make their $i$th move before they do their respective $(i+1)$th -- you will have to use means of *synchronisation*, e.g. a barrier.

---
Tags: algorithms, concurrency, threads
---


# Question
Title: Can someone give a simple but non-toy example of a context-sensitive grammar?
I'm trying to understand context-sensitive grammars.

I understand why languages like

> 1. $\\{ww \mid w \in A^\*\\}$
> 2. $\\{a^n b^n c^n \mid n\in\mathbb{N}\\}$

are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.

I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).

Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?

# Answer
Yes, I would believe this to be possible, but no I am not willing to explicitly construct that context-sensitive grammar. I will explain my answer, by splitting the question in two different parts.

(1) What would the non-toy example be? It should reflect declaration of variables. My proposal of such a language, abstracted from real programming would be something like this. The alphabet is $\\{a,b,;,(,)\\}$. $$\\{ w\_1;w\_2;\dots;w\_n(x\_1;x\_2;\dots;x\_m) \mid w\_i,x\_j\in\\{a,b\\}^\*, \mbox{ each }x\_j\mbox{ is equal to some }w\_i \\} $$ That language is context-sensitive.

(2) To show it actually *is* context-sensitive I would use another formalism. That of a Turing machine with linear use of its tape: a linear bounded automaton LBA. I can program it to do the pattern matching/ I would consecutively consider each $x\_j$ and try to match it with a proper $w\_j$, letter by letter. LBA's are equivalent to context-sensitive grammars, but much easier to program.
> 8 votes

# Answer
My favourite example of a context-sensitive language (CSL) is SAT. The Landweber-Kuroda Theorem says that CSL = NSPACE$\[n\]$. Any SAT instance has a linear-size certificate, so SAT is a CSL. See my question *Context-sensitive grammar for SAT?* for references and discussion.

Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.

There are also fairly natural languages in CSL that are even harder.

However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper. In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL. Productions of the CSG describe how a particular state of the machine results from one possible move. Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.

If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.
> 16 votes

# Answer
Yes, context-sensitive grammars (CSG) are powerful enough to make undefined/undeclared/unbound variables check, but unfortunately we don't know any efficient algorithm to parse strings of CSG.

A real example of a context-sensitive language is the C programming language. A feature like declare variables first and then use them later make C-language a context-sensitive language (CSL). (*I don't know about untyped lambda calculus*).

And because we don't know any linear parsing algorithm for CSL (or CSG). That is the reason in compiler design, we use CFG (and its parsing algoritm only) for syntax checking since we know efficient algorithms to parse CFG (if it's in restricted form). Compilers first parse a context free feature and then later handle context-sensitive features in a problematically way (for example, checks any used variable in the symbol table if it's defined. Otherwise, it generates an error).

Also context-sensitive grammar is used in natural-language processing (NLP). And most natural languages are examples of context-sensitive languages. (I am not sure for the Sanskrit language).

I will try to explain it with a *silly* but simple example (it's just an idea, you can refine it):

```
NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

```

Now, using this grammar, we can generate some correct statements, but some are wrong too. For example,

```
SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

```

But

```
             Grijesh    am       working       [wrong statement]

```

Reason: the value of \<TENSE\> depends on value \<NOUN\> (for example, `I <TENNSE> --> I am`) and hence the grammar doesn't generate correct statements in the English language.

Actually we can't write a context-free grammar for complete English!

 You might have noticed, any natural language translator or grammar checker doesn't works correctly (try with long statements). Because this problem comes under the context-sensitive parsing algorithm.

---

**REFERENCE**: You can watch Dr. Arun Kumar's lectures. In some lecture he explains exactly what you are interested in.
> 11 votes

# Answer
(extending comments into answer)

Not sure this is an example you would like, anyway.

Almost all real programming languages are context-sensitive (in the general sense, i.e conflating both Chomsky type-0 and type-I grammars under "context-sensitive", which is true of course since *unrestricted grammars* are *even more context-sensitive* than *context-sensitive* grammars).

For example, "variables need declared before used", "identifiers should be unique", all these require context (sometimes refered as semantic context, but that can be misleading, since it involves syntactic features anyway) see for example https://www.cs.purdue.edu/homes/hosking/502/notes/04-semantics.pdf

The sense that the above examples are *context-sensitive* (in the grammar/syntactic sense as well as semantic one) is because they talk about their context (what precedes or comes after).

A "variable already defined", is about *context preceding*, a variable use. A "unique identifier", is *context both to what preceded or comes after* an identifier declaration, and so on..

see also Is JavaScript a Context Free Language? on SO
> 1 votes

---
Tags: formal-grammars, programming-languages, lambda-calculus, context-sensitive
---


# Question
Title: Maximising a particular colour in a vertex colouring
I'm looking for a paper that discusses the maximising of one colour in a vertex colouring.

Suppose that for an unweighted, undirected graph $G=(V,E)$ we define a vertex colouring as a function $c : V\to\mathbb N$ (where we use $\mathbb N$ for the colours). I would then like to maximise $\\#\\{v\in V\mid c(v)=n\\}$ for particular $n\in\mathbb N$. The algorithm should return the size of the largest set of vertices that can be coloured with the same colour.

Has there been any literature on this topic?

# Answer
> 4 votes
Your problem is just the (maximum) independent set problem.

---
Tags: algorithms, graphs, reference-request, graph-algorithms
---


# Question
Title: Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?
Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?

# Answer
Multiplication can inherently be computed faster than division because it parallelizes better.

If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.

ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.

In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.

---

If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta\_y}{\Delta\_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$). More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,

$$y=\left\lfloor\frac{\Delta\_y}{\Delta\_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta\_yx+\Delta\_x\epsilon}{\Delta\_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.

The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta\_y$ to the remainder, or increment the quotient and add $\Delta\_y-\Delta\_x$ to the remainder).

When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in **fixed-point** arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.

$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=\[2^n\Delta\_y/\Delta\_x\]$ and $e=\[2^n\epsilon\]$. The "division" is implemented with a fast shift.
> 5 votes

---
Tags: algorithms, efficiency, graphics
---


# Question
Title: Is word size, the size of a memory location? the size of the data bus? or the cpu register size?
Is word size, the size of a memory location? the size of the data bus? or the cpu register size?

Suppose you have a computer,

memory address #0 has byte AB memory address #1 has byte F3 memory address #2 has byte EA So each memory address stores one byte.

And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3 And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4

And Case A, say the CPU register size is 64bit. (would that require two fetches? i'm not sure if that'd work). So alternatively, Case B, Let's say the CPU register size is 32bit

What is the word size? Is it the data bus size, the memory location size, or the cpu register size?

# Answer
This is one of those terms that can mean different things depending upon who you ask and the context in which it is asked.

Usually a processor's word size is defined as the largest size integer which it can operate on with a single arithmetic instruction. For example, 64 bit computer can add or subtract 64 bits with a single instruction. But that same computer may be able to operate on bytes, 16 bit words, and 32 bit longwords.

Don't equate the memory path with the computer's word size. Often data is moved into and out of cache in a fixed size block that is a multiple of the computer's word size. A 64 bit CPU has 8, 8 bit bytes per word but might use a 64 byte cache line and move data into and out of memory in cache block chunks, even if the CPU is only accessing 1 byte of the cache block. OR conversely, the data path to memory could be smaller, as the case with the old 8088 CPU. It used 16 bit CPU registers and did 16 bit arithmetic, but had an 8 bit data bus. It had to do 2 memory transfers to load or store a register.

And then there are fixed definitions for a word size, for example...

DEC had a problem with just saying WORD especially on VAX architecture, mostly because the company had built so many different computers with different natural word sizes (9, 18, 36, 12, 16, 32 and 64 that I can think of) and the VAX was capable of working with a large variety of data sizes. So they decided to define terms like WORD to have more definite meanings.
Byte = 8 bits, Word = 16 bits, Longword = 32 bits, Quadword = 64 bits, Octaword = 128 bits

This took much of the confusion out of discussions when a processor was capable of handling multiple different data sizes.

---

edit - I didn't really address this part of the question: "And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3 And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4"

Not usually.
IF a 64 bit computer is capable of addressing Longwords on a byte boundary, normally the system would load the cache block containing the address 0 from memory into cache. Often that will be on a multiple word cache size. So in the example I gave with a 64 byte cache line, the hardware would move the first 64 bytes into cache as a chunk. The CPU would then access the bytes from cache as you describe (well sort of, it may have to shift bytes to get them loaded correctly). If the longword you attempted to load spanned 2 cache blocks, the hardware would have to load 2 cache blocks (128 bytes) to access the 4 you were interested in. Or in the example you gave with a 32 bit data bus, it would have to load 64 bits (2 lines) to get the 32 that you want. If possible, it's best to align data on its natural boundary to avoid this and other data manipulations required to deal with unaligned data.
> 7 votes

# Answer
This is just an answer where I present things in my own words as I understand them.

Of the different factors - Address bus size, External Data bus size, size of memory location, size of cpu register.. Internal data bus size. Where any of those count, the only thing that counts is size of CPU register.

And regarding CPU registers.. you may get some specialised ones.. but it's the size of general purpose CPU registers. Word size being, the largest unit , or the unit, that an instruction can work/ works, on. So the size of a memory location is irrelevant, as multiple ones can be collected at a time, and the data bus size is irrelevant as multiple trips can be made back and forth, it doesn't affect word size. It's just the general purpose CPU registers that count.

That's one definition of word size.

Another definition is the case of DEC who made different computers with different word sizes and defined their terms word, and also longword and others. as set numbers of bits e.g word 16 bit.

And another definition, is for "compatibility"(assembly language?)**see**, an earlier parent architecture had a word size of e.g. 16bit and child architectures are said to have that word size. This is apparently the case with x86 processors.
> 1 votes

---
Tags: terminology, computer-architecture, cpu
---


# Question
Title: What is the complexity of the emptiness problem for 2-way DFAs?
I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.

According to Wikipedia, they are equivalent to DFAs, though the equivalent DFA might be exponentially larger. I've found state complexity for their complements and intersections, but not for their emptiness-testing.

Does anyone know of a paper where I could find this?

# Answer
Friend Google suggests the following "*The PSPACE-completeness of the emptiness problem for two-way deterministic finite-state automata in Exercise 5.5.4 is due to Hunt (1973).*" (An Introduction to the Theory of Computation, Eitan Gurari, Computer Science Press, 1989, online)

Hunt, H. (1973). "On the time and tape complexity of languages," Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 10-19.

(*I have now looked at the reference*) The paper is written in an abstract way as you note. The crucial part for us is the proof of Thm 3.7, where it is suggested that one can construct a 2FSA $\cal A$ that accepts valid computations of a linear bounded automaton $\cal M$ on a fixed(!) string $x$ (which is close to the definition of PSPACE). The 2FSA $\cal A$ is constructable in polynomial time (in the size of $\cal M$ and $x$). A computation of a LBA can be written as $x\\$x\_1\\$\dots\\$x\_n$ where the $x\_i$ are all of the same length as $x$ and are consecutive steps of $\cal M$. How does $\cal A$ check that $x\_i$ and $x\_{i+1}$ are equal (up to a very local change of a state and a single symbol as the operation of a LBA)? By checking letter by letter, going both ways on the tape. For that we need a counter of size $|x|$ implemented in the finite state control of $\cal A$.

It turns out that the problem is mentioned in the appendix of the classic reference by Garey & Johnson, *Computers and Intractability*, problem \[AL2\] "Two-way finite state automaton non-emptiness" with the explicit remark "PSPACE-complete even if $\cal A$ is deterministic". Reference again Hunt, with the clarification "Transformation from Linear Bounded Automaton Acceptance" (Given LBA $\cal A$ and input $x$, does $\cal A$ accept $x$?). The latter problem is \[AL3\] with reference to the famous Karp (1972) paper "Reducibility Among Combinatorial Problems" (where LBA Acceptance is mentioned as Context-Sensitive Recognition).
> 10 votes

# Answer
Intersection Non-Emptiness for DFA's is as follows:

**Input:** A finite list of DFA's $D\_1$, $D\_2$, ..., $D\_k$.

**Question:** Does there exist a string $w$ such that for every $i \in \[k\]$, $D\_i$ accepts $w$? In other words, is the intersection of their associated regular languages non-empty?

Intersection Non-Emptiness is a classic PSPACE-complete problem (Kozen 1977 - "Lower bounds for natural proof systems")

**Relevance:** There is a nice and simple parameterized reduction from intersection non-emptiness for one-way DFA's to non-emptiness for two-way DFA's.

Pick the number of DFA's to be the parameter for Intersection Non-Emptiness and the number of turns (switches from moving left to right or right to left) as the parameter for Non-Emptiness for two-way DFA's.

**Claim:** Intersection Non-Emptiness for $k$ DFA's is reducible to Non-Emptiness for $(2k-2)$-turn two-way DFA's. (I believe that there is a related reduction for the other direction too.)

Given DFA's $D\_1$, $D\_2$, ..., $D\_k$, we can construct a $(2k-2)$-turn two-way DFA that evaluates each of the DFA's on the input string one at a time.

First, it evaluates $D\_1$ on the input. Then, it moves the tape head back to the beginning and evaluates $D\_2$ on the input. Then, it moves the tape head back to the beginning and evaluates $D\_3$ on the input. ... Finally, it moves the tape head back to the beginning and evaluates $D\_k$ on the input.

If all of them accept, then it does the evaluation on all of them and then accepts. If one of them rejects, then it stops (doesn't finish evaluating on all of them) and immediately rejects.

**Hardness:** If you can solve Intersection Non-Emptiness for $k$ DFA's in less than $n^k$ time, then the strong exponential time hypothesis is false.

Related link: https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166

Therefore, by the reduction, if you can solve non-emptiness for $(2k-2)$-turn two-way DFA's in less than $n^k$ time, then the strong exponential time hypothesis is false as well.

**Conclusion:** If you were to find a faster algorithm for non-emptiness for two-way DFA's, then that would lead to a more efficient simulation of non-deterministic machines. Let me know if you have any thoughts to share. Thank you for asking the question! :)
> 7 votes

---
Tags: complexity-theory, formal-languages, reference-request, automata, finite-automata
---


# Question
Title: Finding a Regular Expression for an Intersection of Two Regular Expressions
Finding a Regular Expression for an Intersection of Two Regular Expressions

PAIR of regular expressions is ((ss\*)t\*) and ((ss\*) + (tt\*)).

How do I find a regular expression that represents the intersection of the languages defined by the pair?

# Answer
I believe, you can convert both expressions to NFAs, then construct a NFA that is the intersection of both NFAs. From this NFA, convert it into a GNFA and from the GNFA convert it on the regular expression, the result is the intersection of both expressions.
> 2 votes

---
Tags: regular-expressions, closure-properties
---


# Question
Title: Why do non regular languages have infinitely many equivalence classes?
For example, for the language $L = \\{a^nb^m|n \neq m\\}$, why does it have infinitely many equivalence classes? How do I show/see that?

# Answer
> 2 votes
There are at least two ways. The first way is to give infinitely many pairwise inequivalent words. In the case of your language, you can take $\\{ a^n : n \geq 0 \\}$, for example (exercise).

The second way is to prove that the language is not regular. The Myhill–Nerode theorem then implies that it has infinitely many equivalence classes. The reason is that for any language, we can construct a DFA (finite or infinite!) for the language whose states are the equivalence classes. If there are finitely many then this is a bona fide DFA, and we get that the language is regular. Conversely, for every regular language, the states of the minimal DFA correspond to the equivalence classes.

---
Tags: regular-languages
---


# Question
Title: Is modulus capable of universal computation?
I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers?

It was a long while ago though and don't remember where I heard it.

Is this true or does it ring any bells?

# Answer
You have to distinguish between two meanings of computation:

1. Computation of functions on a finite domain (e.g. circuits).
2. Computation of functions on an infinite domain (e.g. Turing machines).

A single division operation cannot be universal in terms of the second meaning, since division is *total*: it always halts (even division by zero halts). However, it could possibly be universal in terms of the first meaning. For example, if we encode the input using different primes, then the Chinese Remainder Theorem shows that $x \mapsto n \pmod{x}$ is universal, that is, for every Boolean function $f$ on some set $S$ of finite primes there is a number $n$ such that for every $x \in S$, $n \mod{x} = f(x)$.
> 6 votes

---
Tags: computation-models
---


# Question
Title: Looking for interesting unanswered questions within complexity theory for a project
I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial hierarchy, and the study of probabilistic classes like RP, co-RP, ZPP, BPP, and also their logarithmic counterparts. I also have some interest in quantum computing complexity theory, but I'm afraid my knowledge of quantum isn't that strong. (Only the basics from my modern physics class, which included some quantum). Important: must be new research or new expansion on previous research, a question that either hasn't been asked or hasn't been answered successfully that I might be able to say something interesting about, even if I don't ultimately solve it. I'm willing to learn any necessary programming languages/programs/methods/etc to the end of answering this question (or trying to)!

Note: this is for a senior year undergraduate thesis in math / comp sci.

Thanks for any suggestions!

Edit: An example might be to analyze the complexity of a particular problem that hasn't been (formally) analyzed yet but may yield interesting results.

# Answer
> 2 votes
Do something interesting with visibly languages. They are a relatively recent topic with many useful practical applications. For example, I would find it interesting to better understand the role of synchronization here, compared to the role of synchronization for the theory of codes. Already the simplest case could be interesting, where the visibly language just distinguishes between inner symbols and separator symbols, and the considered codes are just bifix code.

David Richerby is right that this questions allows opinion biased answers. The origins of the opinions voiced in this answer can be found here.

# Answer
> 1 votes
P = NP problem is a major unsolved problem in computer science (in complexity theory ). Details can be found https://en.wikipedia.org/wiki/P\_versus\_NP\_problem

---
Tags: algorithms, complexity-theory, algorithm-analysis, quantum-computing
---


title: Non-integer $a$ in Master method

text:
# Question
Title: Non-integer $a$ in Master method
According to CLRS the master method requires the recurrence to be of form $T(n) = aT(n/b) + f(n)$ where $a \ge 1 $ and $b \> 1$ are constants and $f(n)$ is asymptotically positive.

This makes it sound like even $a \not\in \mathbb{Z}\_+$ is a legitimate value of $a$ as long as $a \ge 1$.

I have trouble visualising what kind of an algorithm would have, say, $a = 1.5$. Can anyone provide an example of an algorithm with non-integer $a$?

# Answer
> 2 votes
The first thing that comes to mind would be a divide-and-conquer method where, for some reason, 50% of the time you only need to do one subproblem, and the other 50% of the time you need to do both subproblems.

The recursion for the average case runtime would be

$$ T(n) = 0.5 \cdot T(n/2) + 0.5 \cdot (2 \cdot T(n/2)) + f(n) = 1.5 \cdot T(n/2) + f(n) $$

(the fine print: this require some assumption of independence between the probability you have to do both problems and the runtime of the subproblems)

---

That said, the master theorem is for asymptotically solving recurrences. Not every recurrence solving problem is about the runtime of an algorithm.

Furthermore, there is no point in going out of your way to excluding cases. Insisting that $a$ is an integer doesn't simplify anything at all, so all it achieves is to make the statement (and proof too, probably) more complicated, and to frustrate those people who find a use for those cases anyways.

# Answer
> 0 votes
It makes no sense for $a$ to be non-integer, at least in the context of algorithms. This is because $a$ refers to the number of recursive calls, which clearly must be integer (unless you are doing something like average case analysis, but then it is not clear that the master method applies at all).

---
Tags: master-theorem
---


title: What does x-bit binary number means?

text:
# Question
Title: What does x-bit binary number means?
What does x-bit binary number mean? for example:

if **x = 8**

is **8-bit** means: any number consists of **8** bits, like : **10101110**

or it has another meaning??

# Answer
That is correct. An x-bit binary number can be expanded as "A number in the binary system that consists of x binary digits".
> 4 votes

---
Tags: memory-management
---


# Question
Title: Book reference: Programming Languages are for humans
Currently I'm writing my thesis and I made the assumption that all programming languages are made for humans and humans alone. There's no reason to make compromises to fit the machine needs. Developers should care about readability for humans, not for machines.

I don't want to discuss whether I'm right or not, because the main topic is about REST (just an architecture for web services) and not about programming languages.

Even though I would like to add a book reference for this assumption. I know that some blogs and articles agree with my opinion, but it's hard to find a serious source or even a book for this point.

All I found is:

> "Underlying this fact is that all of these languages serve the same purpose: to turn human thoughts into the 1’s and 0’s that the computer understands."

To clearify, this is what I wrote exactly (translated to english):

> Source code written by developers will only be read by humans. That's said it's clear that maintainabilty is directly related to readabilty. (talking about why refactoring is needed)

# Answer
> "Underlying this fact is that all \[programming\] languages serve the same purpose: to turn human thoughts into the 1’s and 0’s that the computer understands."

That statement is clearly wrong. Malbolge, for instance, was specifically designed to be counter-intuitive.

> The purpose of all soucre code written by developers is, that other human beings are able to read it easily.

That is also wrong. There are many other possible goals, including

* to "just work",
* to result in especially efficient machine code (given a certain compiler),
* to teach the reader something, or even
* to be *hard* to understand.

The lesson here is to be very careful with unconditional, universal statements: they are rarely true. Stick to a statement that you *can* prove and is just strong enough to support your narrative.

The question of whether there is one that fits both criteria in your case, I can not answer; I suspect there isn't, though.

If readability were the dominant goal in the software industry, many things would be better than they are. But that's just my layman opinion; you should go to programmers.SE for this.
> 5 votes

# Answer
I would check out this book: Refactoring by Martin Fowler. Even though your question isn't specifically about refactoring, this should be a good resource making an argument for why readability is important since the beginning chapters talk about why refactoring is important. If readability to a human wasn't important, then refactoring wouldn't be important. So the arguments he makes for the importance of refactoring should support your argument as well.
> 2 votes

# Answer
From the preface to *Structure and Interpretation of Computer Programs*:

> First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute.

https://mitpress.mit.edu/sicp/front/node3.html
> 2 votes

---
Tags: reference-request, programming-languages, software-engineering
---


# Question
Title: Mutual exclusion algorithm using only atomic reads and writes for unknown number of processes and robust to process abortion
I am trying to come up with a mutual exclusion algorithm that is based only on atomic reads and atomic writes of shared memory (i.e. no compare-and-swap or similar).

Apart from mutual exclusion and deadlock freedom, it needs to fulfill the following properties:

* It needs to be robust in the face of processes dying at **any** point
* It needs to handle an ex-ante unknown number of processes competing for the lock
* Every few seconds I need one of the processes to enter the critical section (I don't care which)
* It should be as memory-efficient as possible
* All my processes share a reasonably synchronized clock-source (sub-second accuracy)

I have come up with a way that looks to me like it could work, but I wanted to run it by you guys to see if I made a mistake somewhere or if there is a more elegant solution.

The idea is to combine a modified version of Szymanski's Three-Bit Linear Wait Algorithm (Figure 1 on page 4 of "Mutual Exclusion Revisited") with a process-naming-scheme based loosely on Moir and Anderson's "Wait-Free Algorithms for Fast, Long-Lived Renaming" *(M&A)*.

**As a first step, I define an "order" for incoming processes by assigning them an ID like *M&A*:**

*M&A* use the following mutex primitive (see Figure 2 on page 5):
where out of **n** processes entering the block, at most **1** will stop there, at most **n - 1** will *move right*, and at most **n - 1** will *move down*.

These primitives can be linked together into a grid, where I decided to number the boxes differently from *M&A*, to allow me to calculate the box number without knowing the total number of boxes:
The box number can be calculated using `box = (m*(m-1))/2 + r`, where **m** is the number of total moves made (including the move into the top-left box, i.e. **m** ≥ 1) and **r** is the number of moves to the right (**r** ≥ 0).

Any new process will initially be assigned a large, globally unique ID (e.g. timestamp + huge random number), which it will use as the value for **p** in the mutex primitive algorithm above. It will then start traversing the grid following the rules of the primitive, starting in the top-left corner, until it stops in some box. The number of the box in which it stopped will now be its new process ID.

To keep the number of process IDs smaller (processes might disappear; and also: boxes can be locked forever without being used if all entering processes move either right or down and none stop there), I will replace the boolean variable **Y** in the primitive above with a time-stamp.

The line `Y := true` will then be replaced with `Y := now`, where **now** is the current time. Similarly, the condition `if Y then ...` will be replaced with `if (now - Y < timeout) then ...`, where **timeout** is the time after which a box will be returned to the available pool.

While a process is still running, it needs to keep setting the **Y**-value of its box to **now** to never allow its ID to expire. While smaller values of **timeout** will lead to smaller IDs and less memory use, it can theoretically be chosen arbitrarily large and thus it should always be possible to find a value for **timeout** that will guarantee that processes will never lose their ID unless they actually quit or died. Values of minutes, hours, or even days should do the trick.

**Now, we can use this process order to implement Szymanski's algorithm:**

```
communication variables:: a, w, s: boolean = false
private variables:: j: 0..n

p1      ai=true;
p2      for(j=0;j<n;j++)
            while(sj);
p3      wi=true;
        ai=false;
p4      while(!si) {
p5          for (j=0;j<n & !aj;j++);
p6          if (j==n) {
                si=true;
p6.1            for (j=0;j<n & !aj;j++);
p6.2            if (j<n)
                    si=false;
p6.3            else {
                    wi=false;
p6.4                for(j=0;j<n;j++)
                        while(wj);
                }
            }
p7          if (j<n)
                for (j=0;j<n & (wj | !sj);j++);
p8          if (j!=i & j<n) {
p8.1            si=true;
                wi=false;
            }
        }
p9      for(j=0;j<i;j++)
            while(wj | sj);

Critical Section

e1      si=false;

```

The idea behind this algorithm is a little involved and for brevity (if that isn't already a lost cause at this point), I will not try to paraphrase it again here (Wikipedia also discusses a variant of this algorithm).

To make this algorithm work as needed (i.e. in the face of process aborts and an unknown total number of processes) the following changes can be made:

Just like **Y** above, the booleans **ai**, **wi**, and **si** will be replaced with timestamps. Except, this time the timeouts need to be short enough to still allow the critical section to be entered as often as needed, in my case every few seconds, so a timeout of 5s might work. At the same time, the timeout needs to be long enough so that it never expires unless a process dies, i.e. it needs to be longer than the worst-case time it takes processes to keep updating the timestamps for flags that need to remain set.

The loops over processes (e.g. `for(j=0;j<n;j++)`) will be turned into traversals of the process-ID grid from above in the order of the box-numbers. Each box can have 3 states: Never visited by anyone, a process has stopped in it, or all processes moved on and the box is currently blocked. No distinction needs to be made between the latter two, since a blocked box will simply correspond to a process that is currently not trying to enter the critical section (i.e. **ai**, **wi**, and **si** are ***false***/expired). The loop starts in box 0. If it comes across a box that has been visited (i.e. has its **X**-value set), it adds the adjacent boxes to its "to-check-list" (i.e. if box 8 was seen, box 12 and 13 will be added to the list). The loop terminates when the "to-check-list" has been processed completely (unless, of course, there is another stopping condition present that fires first (e.g. `j < i` or `& !aj`)).

**Now to my questions:**

1. **Does this look like it would work reliably?**
I've never done a formal proof of a framework like this. My gut (and intense pondering) tell me that it should be solid, but I wouldn't mind something a bit more rigorous than that. I'm most worried about the effects of a process dying between p3 and e1 of Szymanski's algorithm and the flags expiring randomly while other processes are in that part of the code.
2. **Is there a better solution (simpler/less resource use)?**
One point of attack for an optimization might be the fact that I don't need **all** processes to eventually make it to the critical section, I just need one (and I don't care which one either).

Sorry for the length of this post and thank you for your endurance reading it! Suggestions for shortening welcome... :)

# Answer
> 2 votes
Since I don't really care about fairness or starvation (it doesn't matter which process enters the critical section), I don't really need to use an algorithm as complex as Szymanski's (also pointed out by @WanderingLogic in a comment above).

I found a quite beautiful alternative: An algorithm by Burns and Lynch:

```
program Process_i;
    type flag = (down, up);
    shared var F : array [1..N] of flag;
    var j : 1..N;
begin
    while true do begin
        1: F[i] := down;
        2: remainder;     (* remainder region *)
        3: F[i] := down;
        4: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        5: F[i] := up;
        6: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        7: for j := i+1 to N do
               if F[j] = up then goto 7;
        8: critical;      (* critical region *)
    end
end.

```

You can find it on page 4 (836) of their paper "Mutual Exclusion Using Indivisible Reads and Writes".

It has a couple of major advantages:

* It is **much** simpler
* It uses less memory (In fact, they state that their algorithm is optimal in that respect)
* All shared memory has only a single writer (but multiple readers, of course)
* It is easy to turn the busy-waits into delayed retries (see here)

***Aside: The idea of this algorithm can be visualized as follows:***

*I'm a process and I'm standing somewhere in a row with other people (all other processes).
When I want to enter the critical section, I do the following:*

* *3/4: I look to my left and keep my hand down as long as I see someone with their hand up.*
* *5: If no-one to my left has their hand up, I put mine up.*
* *6: I check again if anyone to my left has meanwhile put their hand up. If so, I put mine back down and start over. Otherwise, I keep my hand up.*
* *7: Everyone to my right goes first, so I look to my right and wait until I don't see any hands up.*
* *8: Once all hands to my right are down, I can enter the critical section.*
* *1: When I'm done, I put my hand back down.*

I implemented the whole idea from above (including M&A) with this algorithm and am currently testing the heck out of it and so far it seems very stable.

The implementation is very straight forward. There were really only two additional caveats I had to consider (unless, of course, I missed something (pointers welcome)):

* If a process makes it to line 7 in the algorithm, it might end up hitting the `goto`, in which case, in my implementation (see here), the entry to the critical section is denied and the process tries again later. When the retry happens (possibly with a big delay), I need to refresh the process's flag in such a way that it didn't have even the tiniest moment during which the flag was expired, or, if it did, I need to detect that and jump back to line 3 in the algorithm instead of continuing at line 7.
* I added a check whether the critical section needs to be entered at all (i.e. a statement that limits the rate at which the critical section is entered). It is most efficient to perform this check right before a process even tries to enter the critical section. To make 100% sure that no thread can ever exceed the rate limit, though, a second check will need to be performed when a process successfully entered the critical section.

Due to the shared data-structures that my code uses, it's currently not really in a state that makes it meaningful to post here, but with a little bit of work, I could put together a self-contained version. If anyone is interested, please leave a comment and I will do so.

---
Tags: algorithms, mutual-exclusion
---


title: Regular language subsets

text:
# Question
Title: Regular language subsets
If $L\_{1} \subseteq L\_{2}$ and $ L\_{2}$ is regular, does it follow that $L\_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we make?

# Answer
No, $L\_1$ is not necessarily regular. We could have $L\_2 = \Sigma^\*$, in which case $L\_1$ could be anything at all.
> 2 votes

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


title: What this subnetting restriction means

text:
# Question
Title: What this subnetting restriction means
I was reading Data Communication book by Forouzan in which there is a one restriction put on CIDR subnetting by Internet authorities:

> First IP address in the block should be evenly divisible by the number of addresses. For example, below, the first address, when converted to a decimal number, is 3440387360, which when divided by 16 (block size) results in 215024210.

Since this did not clear the practical significance behind this restriction I went on exploring and came across the video where it is explained as follows:

> Whenever we divide any number by $k^{th}$ power of 2 (another restriction being that the block size should be $2^k$), the reminder is least significant k bits. So evenly divisible by $2^k$ means that least significant $k$ bits should all be 0. This way the first address of the allocated address block can be used as a block ID since it has all 0s in the host ID part.

Now that seems more logical despite the fact that I dont understand how

***evenly divisible*** *by the number of addresses $2^k$*

translates to

*least significant $k$ bits **should all be 0***

Can't it be just that the decimal equivalent of least significant $k$ bits should be divisible by 2. I mean if least significant 4 bits (for a block of $2^4$ addresses) is $(1010)\_2$, then it translates to $(10)\_{10}$ which is divisible by 2.

So in short why is ***evenly divisible*** translates to ***all 0 LSBs***?

# Answer
Since each place in a binary number is a power of two, the binary expansion of $2^k$ for any $k$ will be a 1 followed by $k$ zeroes. Examples:

$$1 = 2^0 = 1$$ $$16 = 2^4 = 1\underbrace{0000}\_{4\ zeroes}$$ $$512 = 2^9 = 1\underbrace{000000000}\_{9\ zeroes}$$

Multiplying a number that ends in zeroes by another number (integer) produces at least that many trailing zeroes. So any number divisible by a number ending in $k$ zeroes has to end in at least $k$ zeroes.
> 1 votes

---
Tags: computer-networks, arithmetic
---


# Question
Title: An intuitive explanation for LR grammars?
With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR grammars however such an explanation seems to be difficult. Of course you could go through the entire construction of the DFA and so on. But is there a general principle or a few of them, that can give an intuitive understanding of LR grammars as a whole?? What is the intuition behind the item sets??

# Answer
A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively easy (hah!) to grasp. In particular, it explains why $LR$ grammars are a much richer set than the $LL$ ones.

In practice, it is probably much more relevant to be able to understand the format in which your preferred LR parser generator spits out item sets when tickled the right way, and in particular how to track down the origin of conflicts and alternative ways to solve them (and their consecuences). I like the bison manual a lot in this regard.
> 2 votes

---
Tags: formal-languages, formal-grammars, parsers, intuition, lr-k
---


# Question
Title: Minimum Spanning Tree over Vertices Proof
This is the problem:

$d\_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.

The goal is an algorithm that finds a spanning tree which minimizes the value $\sum\_{v \in V}{d\_{T}(v)\*w(v)}$.

My idea is to define a new weight function on edges in the following way: $m(e\_{ij})=w(v\_i)+w(v\_j)$, i.e. the weight of each edge is the weight of both of its vertices.

Then we run Kruskal on a graph with the given $m$ weight function. The problem is that I have no idea how to prove that it works.

I thought about starting with the expression $min \sum\_{e \in E}{m(e)}$ which Kruskal yields, and then somehow change the summation to be over vertices. How can it be done?

Thanks!

# Answer
> 3 votes
It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$, $$ \begin{align\*} \sum\_{(i,j) \in T} m(e\_{ij}) &= \sum\_{(i,j) \in T} w(v\_i) + w(v\_j) \\ &= \sum\_i \sum\_{(i,j) \in T} w(v\_i) + \sum\_j \sum\_{(i,j) \in T} w(v\_j) \\ &= 2 \sum\_i d\_T(i) w(v\_i). \end{align\*} $$ You take it from here.

---
Tags: algorithms, algorithm-analysis, spanning-trees
---


# Question
Title: What does $\alpha_r\supset\beta_r$ mean in the tolerance definition of System Z?
I'm reading up on System Z introduced by Judea Pearl (in System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning). A central definition is that of *tolerance* of a subset $R'$ of a rule set $R$ for a rule $r = \alpha\_r\to\beta\_r$ (denoted by $T(r\ \vert\ R')$). Tolerance of $R'$ for $r$ is defined to be the set of satisfiable formulas $$(\alpha\_r\land\beta\_r)\bigcup\_{r'\in R'}(\alpha\_{r'}\supset\beta\_{r'})$$ (see page 2 of the article by Pearl).

I don't understand what $\alpha\_{r'}\supset\beta\_{r'}$ is supposed to mean. Can anyone explain?

# Answer
> 2 votes
In elementary logic, $A \supset B$ is notation for the formula $\neg A \lor B$ (for the implication "$A$ implies $B$"). In other words, $A \supset B$ is a formula; it is true if $A$ is false or if $B$ is true, and false otherwise. https://math.stackexchange.com/q/1106001/14578

How you could have figured this out on your own: Read the entire paper. For instance, a useful place would be to start would be reading the examples in Section 3, where from the examples one can reverse-engineer the probable meaning of the symbol.

---
Tags: logic, notation, reasoning
---


# Question
Title: Travelling Salesman which can repeat cities
In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is easy to accomplish as if there is no straight path between A and B, we can simply assign a new edge whose length is the shortest path between A and B.

However, if we have a sparse graph, maybe we can benefit from not having a complete graph. In this case, we might be forced to repeat vertices. If our graph is only 3 cities, and only two edges, connecting (1, 2) and (2, 3), then the solution must repeat city 2: 1 - 2 - 3 - 2 - 1.

I am struggling to find examples of TSP in the scientific literature which assume a non complete directed graph. Any known references? Any keywords I may be missing? In this case, cycles are allowed.

I am especially interested in how we could separate subtour inequalities when cycles are present. I am hoping for a solution based on integer linear programming and branch-and-bound, and am wondering how to add subtour elimination inequalities. Any ideas?

# Answer
> 4 votes
I actually found this solution some time ago, but here we go. This is a formulation in a directed graph that can repeat vertices and does not repeat arcs. It requires that for every arc $(i,j)$ there exists an arc $(j,i)$, and that the distance $d\_{ij} = d\_{ji} \geq 0$.

We deal with a directed graph $G = (V, A)$. For $W \subseteq V$, we define $\delta^-(W) = \\{ (i,j) \in A: i \not \in W, j \in W\\}$, $\delta^+(W) = \\{ (i,j) \in A: i \in W, j \not \in W\\}$ and $A(W) = \\{ (i,j) \in A: i \in W, j \in W\\}$.

We are looking for, in graph terminology, a closed walk that covers all vertices (a walk may contain cycles).

The decision variables are:

$x\_{ij} = 1$ if arc $a\_{ij}$ is in the walk, $0$ otherwise (binary variable)

$g\_{i} = $ the outdegree of vertex $i$ (continuous variable)

The formulation is given by:

$$ \min \sum\_{(i,j) \in A} d\_{ij} x\_{ij} $$

subject to:

$$ \sum\_{(i,j) \in \delta^+(i)} x\_{ij} = g\_i, \\;\\;\\;\\;\forall i \in V $$ $$ \sum\_{(i,j) \in \delta^+(i)} x\_{ij} = \sum\_{(j,i) \in \delta^-(i)} x\_{ji}, , \\;\\;\\;\\;\forall i \in V $$ $$ \sum\_{(i,j) \in \delta^+(i)} x\_{ij} \geq 1, \\;\\;\\;\\;\forall i \in V $$ $$ \sum\_{i \in W} g\_{i} \geq 1 + \sum\_{(i,j) \in A(W)} x\_{ij} , \\;\\;\\;\\; \forall W \subsetneq V, |W| \> 1 $$

These last constraints are subtour elimination constraints, which can be expressed in a nice manner thanks to the $g\_i$ linear variables. The separation of these constraints is actually polynomial, as it can be solved using a maxflow algorithm.

Notice that for every subset of vertices $W$, $\sum\_{i \in W} g\_{i} - \sum\_{(i,j) \in A(W)} x\_{ij} \geq 1$. The 1 in this constraint means that at least one vertex must leave $W$.

Given a solution to a linear relaxation represented by $\overline{g}\_i$ and $\overline{x}\_{ij}$, we need to find $W$ that minimises the expression $\sum\_{i \in W} \overline{g}\_{i} - \sum\_{(i,j) \in A(W)} \overline{x}\_{ij}$.

Solving this problem is equivalent to finding $W$ which is separated from the rest of the graph (given any vertex being source and sink) by a minimum cut, which is equivalent to the max flow. If the max flow value is less than 1, we found a violated cut and we can add it to the model.

# Answer
> 4 votes
This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and $C$, the distance from $A$ to $B$ is no greater than the distance from $A$ to $C$ to $B$.

As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the distance from $A$ to $B$ to be the length of the shortest $A$–$B$ path in the original graph. This shows that your problem is no harder than metric TSP. But, conversely, every instance of metric TSP is already an instance of your problem. This is because, in metric TSP, the triangle inequality guarantees that it's never necessary to revisit a vertex so allowing revisiting doesn't change the optimal solution.

---
Tags: graphs, reference-request, traveling-salesman
---


title: How is clock syncing implemented?

text:
# Question
Title: How is clock syncing implemented?
I'm looking for an explanation or reference on the implementation of computer clock. To keep the question at the level of logical abstractions: say, we put together some combinational and sequential logic from basic gates. The role of the clock (an oscillator of some sort, but that's going into more detail than needed for my abstraction) is to synchronise the unorderly chorus of inputs and outputs passing through the gates. Exactly how does the clock synchronize the signals?

To render things more concrete... Take a two-way NAND gate. Say, I set the two inputs (`U1`) to high signal, and obtain (after some inherent delay) a stable low signal at the other end (`U2`). Now, to add basic sequential logic to this inverter, let's add a Data Flip-Flop (DFF). The effect is that we can be certain that the `Q` end of the DFF will broadcast the low signal "definitively" at the start of the next clock cycle. What happens within the cycle is not to be trusted. The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?

The metaphor in my mind is that the clock acts as a sluice. But the comparison is misleading, in that the signal entering and exiting the DFF is *not* truncated at any point. We could physically measure the signal within the tick-tock cycle of the clock at the `Q` end of the DFF. Another high-flown metaphor would be the warm-up motions of an orchestra before the rehearsal gradually transforming into an attuned performance, with the conductor setting the beat.

How is the *proper* signal (attuned to the clock's oscillations) distinguished from the *noise* propagating through gate circuitry at all times? I realize, there may be missing parts in my picture, so that question should be framed in constructive terms: **How can one implement this basic circuit to allow the logic to distinguish between signal and noise?**

---

**Edit:** Judging by responses to this question, my original question must be poorly phrased. I understand the reasons behind the choice of frequency for the system clock to ensure the circuit is stable on the tick of the clock. The responses from @Ran G. and @slebetman emphasize the "contractual" side of things. My question is really about why the contract holds. In retrospect, what I was getting at is the trivial fact that measuring instruments (system clock) must be selected based on the degree of precision required -- in a typical case discussed here, for our human sluggish attention span.

To illustrate, here's a graph of the clock pulse against data-in and Qa output for a DFF.

Say, in the 2nd clock cycle, Captain Marvel sends a pulse on the data-in line and -- oblivious to the clock period -- expects to read it off immediately (mid-phase). With his lightning speed, there's no way he can make sense of the output of this circuit because the clock cycle is geological time to him. Billy Watson, on the other hand, can read it just fine. Neither Captain M. nor Billy W. is synchronized with the system clock. Not in the sense that the gate circuitry is. But for Billy's experience of time, the clock's time scale is sufficiently precise.

# Answer
> 3 votes
You have a good understanding of clocking mechanism and how flip-flops (registers really, can be implemented using any clocked memory, not just flip-flops) are used to get a "final" reading after all propagation of signals have stabilized. But your question:

> The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?

Perhaps is overthinking it. It is never achieved. Rather, it is specified. Basically you read the user manual (or in engineering it's usually the data sheet). If the user manual says the maximum clock is 100MHz then you don't supply it with a 200MHz clock.

That's the basic mechanism of how it's "achieved".

So, I can already see the next question forming: How do the designers know to specify 100MHz? It can't be arbitrary can it?

The basic way it's done is to calculate the timing of all propagation. Say you have this circuit:

```
output = A && (B || C || (D && E))

```

Lets say all OR and AND gates have the same propagation time: 1ns. Lets also re-arrange the circuit above to make things clearer:

```
            A
           /
output = &&    B     D
           \  /     /
            ||    &&
              \  /  \
               ||    E
                 \
                  C

```

So, in the above circuit, the longest path to output is the input from D and E. It passes through four gates (assuming gates can only have two inputs, you can do three levels if you use a three input OR gate). Since each gate takes 1ns to stabilize, the circuit above can be sampled at a rate of every 4ns or 250MHz.

The calculations above are simplified of course. It assumes wires have zero propagation time and also assume that inputs are simultaneous. Real-world CAD software can calculate propagation time of wires/traces and can even lengthen traces if necessary to ensure signals arrive at the same time. As for the simultaneity of the inputs, that's the user's (the engineer using your component) problem. If the outputs from his circuit take time to stabilize before going in to your circuit he has to take that into account and use a slower clock to allow the signals to stabilize.

There is also the dirty way to do the above calculations: overclocking. You keep increasing the clock frequency to your system until it fails then back off a bit until it works again then back off a bit more to allow for some overhead.

There's also a third question and it is part of the assumption of almost every digital designer: When we clock, how are we SURE the inputs have stabilized? We've only accounted for the outputs of our gates, not the inputs to them?

The answer is that inputs to our circuit comes form another circuit in our system. They synchronize by using the same clock. Since they were clocked at the end of the previous clock cycle, we assume they're stable at the beginning of this clock cycle. Which is why we only consider the propagation of the gates as the limiting factor for the stability of signals.

All non-internal signals or all signals that don't share our clock must be sampled. That's part of the reason that external signals can never be as fast as our internal clock - it's to allow for them to be stable in a register somewhere before signaling to the internal circuits that they're ready to enter our system.

So in general, in terms of signal stability, we assume noise only exists between clock pulses and all the signals in our entire system should stabilize before the next clock pulse. That effectively defines our maximum clock rate.

# Answer
> 2 votes
I feel there are multiple questions in your post. I will attempt to answer the first -

*"...The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?*

Shown below is a transistor level circuit of the D flip-flop shown in the picture in your post.

If you replace your D-ff schematic with the above picture, you can see how the signal propagates from the D input to the Q output.

Your second question is

*How can one implement this basic circuit to allow the logic to distinguish between signal and noise?*

Logic does not distinguish signal from noise. Noise **is** a signal. It is an (usually) unwanted signal, but a signal all the same. It is the job of the designer to ensure that noise from various sources does not pollute the actual signal so much that it results in an incorrect reading at the Q output.

Circuits have some amount of noise immunity. Chips and cell libraries are designed such that the noise does not cross the specified noise immunity of the circuit.

# Answer
> 1 votes
From your question, it seems you already have the answer, but you are not acknowledging it as "the answer".

It is exactly as you describe it: The logic circuit takes time $t$ to stabilize. This $t$ is given by the low-level description of the circuit (adding all the $t\_{\text{high-low}}$ and $t\_{\text{low-high}}$ in the longest path (the *critical* path). There are additional delays here, but I'll not discuss them here.)

Once we know this $t$, we can set the clock oscillation to be $\ge t$. That is, there will be a gap of at least $t$ time between one clock tick (which causes changes in the logic circuit), to the next clock tick (that samples the new output). By that second click, the outputs are already stable.

This second click now triggers a change in the inputs, which again changes the output: after time $t$, the output is stable again and another clock tick is allowed.

So the basic idea here is:

1. you **first** determine the time $t$ it takes the output to be stable
2. **then** you set the clock period to be larger than $t$.

---
Tags: computer-architecture, clocks
---