# Question
Title: algorithms, number of instructions in the code
How many instructions as a function of the input size N?

```
int count=0;
for (int i=0; i<N; i++)
  for(int j=i+1; j<N; j++)
    if(a[i] + a[j] ==0)
       count++;

```

\# of "less than" compare instructions = 1/2(N+1)(N+2) Can someone pl. explain why there is 1/2 multiplier?

\# of "equal to" compare instructions = 1/2 * N * (N-1). The same here why is there 1/2 * (N-1). Shouldn't it be just N?

also when do we increment j++?, after count++ or after we increment i?

Thank you!

# Answer
Number of "equal to" compare instructions :

```
It is equal to the no of times inner for loop(with j variable) is executing.
For i=0: it is executing (N-1) times
For i=1: (N-2) times
For i=(N-1) : (N-(N-1+1))=0 time.

So, total execution= (N-1)+(N-2)+.....+3+2+1+0=1/2 * N * (N-1)

```

Number of "less than" compare instructions:

```
There will be (N+1) number of comparison for outer for loop.
For inner loop:
  for i=0: N comparison
  for i=1: (N-1) comparison
  for i=N-2: 2 comparison
  for i=N-1: 1 comparison

Total number of comparisons= (N+1)+N+(N-1)+.....+2+1=1/2(N+1)(N+2)

```
> 0 votes

# Answer
The factors of $\tfrac12$ come from the fact that $1 + \dots + N = \tfrac12N(N+1)$.

`j` is incremented at the end of the loop. This is standard syntax for languages such as C and Java.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Is 2-SAT with XOR-relations NP-complete?
I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination?

Example Input:

* 2-SAT part: `(a or !b) and (b or c) and (b or d)`
* XOR part : `(a xor b xor c xor 1) and (b xor c xor d)`

In other words, the input is the following boolean formula:

$$(a \lor \neg b) \land (b \lor c) \land (b \lor d) \land (a \oplus b \oplus \neg c) \land (b \oplus c \oplus d).$$

Example Output: Satisfiable: a=1, b=1, c=0, d=0.

Both the number of 2-SAT clauses and the number of XOR clauses in the input are $O(n)$, where $n$ is the number of boolean variables.

# Answer
> 12 votes
2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x\_1 \lor x\_2 \lor x\_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $$(x\_1 \lor \overline{y}) \land (y \oplus x\_2 \oplus z) \land (\overline{z} \lor x\_3)$$ with $y$ and $z$ as new variables.

# Answer
> 7 votes
You haven't specified the arity of your XOR relations, but like in the usual SAT-to-3SAT reduction, you can always arrange that their arity be at most 3. Now you are in great position to apply Schaefer's dichotomy theorem, which will tell you whether your problem is in P or NP-complete (these are the only two options). If it turns out to be in P, the next step could be looking at Allender et al., which will let you know how easy your problem is.

# Answer
> 5 votes
By Schaefer's dichotomy theorem, this is NP-complete.

Consider the case where all clauses have 2 or 3 literals in them; then we can consider this as a constraint satisfaction problem over a set $\Gamma$ of relations of arity 3. In particular, the relations $R(x,y,z)$ are the following: $x \lor y$, $x \lor \neg y$, $\neg x \lor \neg y$, $x \oplus y \oplus z$, $x \oplus y \oplus \neg z$.

Now apply Schaefer's dichotomy theorem, in its modern form. Check each of the six operations to see if they are a polymorphism:

* Unary 0: Not a polymorphism of $x \lor y$.
* Unary 1: Not a polymorphism of $\neg x \lor \neg y$.
* Binary AND: Not a polymorphism of $x \lor y$. (Consider $(0,1,0)$ and $(1,0,0)$; they both satisfy the relation, but their pointwise-AND $(0,0,0)$ doesn't.)
* Binary OR: Not a polymorphism of $\neg x \lor \neg y$. (Consider $(0,1,0)$ and $(1,0,0)$; they satisfy the relation, but $(1,1,0)$ doesn't.)
* Ternary majority: Not a polymorphism of $x \oplus y \oplus z$. (Consider $(0,0,1)$ and $(0,1,0)$ and $(1,0,0)$; they satisfy the relation, but their majority $(0,0,0)$ doesn't.)
* Ternary minority: Not a polymorphism of $x \lor y$. (Consider $(0,1,0)$, $(1,0,0)$, and $(1,1,0)$; they satisfy the relation, but their minority $(0,0,0)$ doesn't.)

It follows that this problem is NP-complete, even if you restrict all the XOR clauses to be of length at most 3.

---

On the other hand, if all the XOR clauses are restricted to be of length at most 2, then this is in P. In particular $(x \oplus y)$ is equivalent to $(x \lor y) \land (\neg x \lor \neg y)$, so any such formula is equivalent to a 2SAT formula, whose satisfiability can be determined in polynomial time.

---
Tags: np-complete, satisfiability, xor, 2-sat
---


# Question
Title: What is difference between Buffering and Spooling with respect to Operating System
I have googled a lot to find the answer and found some links like this, this and this and even in a book `Understanding Computers Today and Tomorrow (13th edition)` couple of paragraphs are written as given below:

> Some input and output devices are exceedingly slow, compared to today’s CPUs. If the CPU had to wait for these slower devices to finish their work, the computer system would experience a horrendous bottleneck. For example, suppose a user sends a 100-page document to the printer. Assuming the printer can output 20 pages per minute, it would take 5 minutes for the document to finish printing. If the CPU had to wait for the print job to be completed before performing other tasks, the computer would be tied up for 5 minutes. To avoid this problem, most operating systems use two techniques—buffering and spooling. A buffer is an area in RAM or on the hard drive designated to hold input and output on their way in or out of the system. For instance, a keyboard buffer stores characters as they are entered via the keyboard, and a print buffer stores documents that are waiting to be printed. The process of placing items in a buffer so they can be retrieved by the appropriate device when needed is called spooling. The most common use of buffering and spooling is print spooling. Print spooling allows multiple documents to be sent to the printer at one time and to print, one after the other, in the background while the computer and user are performing other tasks. The documents waiting to be printed are said to be in a print queue, which designates the order the documents will be printed.

but I cannot clearly understand the difference between `Buffering` and `Spooling`.

Can anyone explain the difference between them in simple and easily understandable terms.

Also in couple of the links mentioned above, it is written as :

> The main difference between buffering and spooling is that the latter allows the I/O of one job to overlap the computation of another. Buffering only allows the I/O of a job to overlap with its own computation.

so what is meant by `overlapping the computation of own or other job`?

\[I don't know whether this is a proper place to ask this question or not, if not, then kindly tell where should I post this to get the answer\]

# Answer
There's not really a significant difference. Spooling uses buffering. Buffering can be used for other purposes, too.

The second quote you include in your question (I/O overlap, etc.) looks to me like it's not very helpful. The key question is whether you have one buffer per process (job) or a shared buffer that is common to all jobs. If you have one buffer per job, obviously they can overlap. If you have a single buffer for all the jobs, then if one job starts writing to it, other jobs might need to be locked out (depending upon how you implement the buffer).

Don't worry about these words. Memorizing the names and the terms "buffering" and "spooling" is not important. What's important is the concept: the idea of storing some data in a temporary space in memory, so that when the recipient is finally ready to use it, it's all there for them in one spot.
> 3 votes

---
Tags: operating-systems
---


title: RAM Machine and FSM

text:
# Question
Title: RAM Machine and FSM
I heard that it's possible to model a bounded-memory RAM as a Finite State Machine.
I'm curious about the method of how we would do that.

How would you model a bounded-memory RAM as a Finite State Machine?

Thanks in advance

# Answer
> 3 votes
Consider a RAM machine with $n$ memory cells, and suppose each cell contains a bit. In addition, you have a control with $k$ states.

A configuration of this machine consists of the state of the control, and the contents of the memory. Thus, there are $k\cdot 2^n$ configurations.

You can view each configuration as a state of a FSM, and the transitions between configurations are determined by the state of the control and the effect it has on the memory.

---
Tags: finite-automata, computation-models
---


title: Infinite Memory

text:
# Question
Title: Infinite Memory
It seems to me that any problem whose solution requires finite memory can be emulated on a Finite State Machine . This would make those problems that can't be solved by a Finite State Machine to require infinite memory ( like general multiplication of integers ).
My question is what "infinite memory" really means if "infinite" is used in some "completed sense" ( its the negation of finite ). To me the notion of "infinite memory" seems to me so weird and well-defined. How can a problem that requires infinite memory be computable ?

Can anyone help me clarify that ?

Thanks a lot in advance .

# Answer
The correct distinction is between *bounded memory* and *unbounded memory*. For example, consider the regular language consisting of all strings of even length. The length of the input is unbounded, but always finite. The memory used by the machine is bounded. In contrast, a machine that accepts the non-regular language $\\{ a^n b^n \\}$ has unbounded input and also unbounded memory, but its memory usage is still much smaller than the input size, and in particular it only uses a finite amount of memory.

Any machine which always halts on every input is guaranteed to use a finite amount of memory. Only machines that never halt can use infinite memory, and even in their case, at every step they are only using finite memory; only in the limit are they using infinite memory. For example, consider a Turing machine that (ignoring its input) writes 0 on its work tape, moves right, and repeats. The machine never halts, and after $2t$ steps has accessed $t$ tape cells. If you consider the entire infinite computation as a whole, then this computation uses infinitely many memory cells; but at each finite time, only finitely many cells are used.
> 8 votes

---
Tags: turing-machines, finite-automata
---


# Question
Title: If in all satisfying assignments all pair of variables can take all possible values is this tautology?
I suppose this is both easy and false.

Let $\phi$ be propositional boolean formula on variables $x\_1 \ldots x\_n$.

Suppose in all satisfying assignments of $\phi$, all pairs of variables $(x\_i,x\_j),i \ne j$ can take all possible values, i.e. any of $\\{(F,F),(F,T),(T,F),(T,T)\\}$.

> Is $\phi$ tautology?

In case the answer is negative, is there simple characterization of those $\phi$ which are not tautologies?

# Answer
The *VC dimension* of a set $S \in \\{0,1\\}^n$ is the maximal $d$ such that for all $i\_1 \< \cdots \< i\_d \in \\{1,\ldots,n\\}$ and all $b\_1,\ldots,b\_d \in \\{0,1\\}$, there is a point $x \in S$ such that $x\_{i\_1} = b\_1,\ldots,x\_{i\_d} = b\_d$. Your condition states that the VC dimension of the set of satisfying assignment of a formula is at least $2$. The formula is a tautology if the VC dimension is $n$. There are sets of arbitrary VC dimension, so even if you replace pairs by larger tuples, your conclusion would still be wrong.
> 4 votes

---
Tags: logic, satisfiability
---


# Question
Title: How many Turing machines are there with $c$ characters and $n$ states?
By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept.

We can assume every $n$-state Turing machine has $(c+1)n$ transitions going to either another non-accepting state, reject, or accept, that is that it has a transition for every state and character on the tape. It can either move to the left, right or not shift each transition. I tried some myself to figure out how many Turing machines there were and got the two following incompatible results.

We have $(c+1)n$ transitions and each transition has $3(n+2)(c+1)$ different options. Encoding it as a 5 tuple I get $3n(n+2)(c+1)^2$, but taking from options for transitions for each transition gives me $((c+1)n)^{3(n+2)(c+1)}$

Is either of these correct and if so why?

# Answer
The answer is $(3(c+1)(n+2))^{(c+1)n}$. You get this by considering all functions of the type $(Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R, N\\}$. Where $Q$ is the set of states, $F$ is the set of final states, $\Gamma$ is the alphabet including the blank character, and $L$, $R$, $N$ are the left shift, right shift, and no shift respectively. You can view this as a problem of picking $|(Q \setminus F) \times \Gamma| = (c+1)n$ elements from a set of cardinality $|Q \times \Gamma \times \\{L, R, N\\}| = 3(c+1)(n+2)$ with replacement.
> 4 votes

---
Tags: turing-machines
---


title: SCC of a Directed Acyclic Graph

text:
# Question
Title: SCC of a Directed Acyclic Graph
My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same time?

Consider a graph on two vertices "u" and "v" and assume that it is strongly connected as well as a DAG. A path from u to v exists as well as a path from v to u which creates a cycle. No?

# Answer
> 2 votes
This is difficult to answer because in part we have to guess what your instructor actually meant, but that said, I can't see a way to reconcile the statement.

You could ask if the components that are strongly connected *in the underlying undirected graph* are DAGs, but this is trivial, any subgraph of a DAG is also a DAG - we're not adding any edges, so we can't introduce a cycle.

Alternatively, we could ask for strongly connected components of a DAG, but here your observation is correct, there are no non-trivial strongly connected components in a DAG. The trivial ones are just each vertex by itself, which is trivially a DAG too, so that kind of works, if your instructor is looking to test your understanding of the definitions.

The last thing I can think of is that if you take a directed graph (not necessarily acyclic), and shrink each strongly connected component to a single vertex, the resulting graph is a DAG (called the "condensation" of the original graph). The condensation of a DAG is the DAG itself (we're back to the trivial strongly connected components again).

---
Tags: graphs, dag
---


# Question
Title: Can the concatenation of two non-regular languages be regular?
Can anyone give an example of two non-regular languages $A, B \subseteq \\{0, 1\\}^∗$ for which the language $AB$ is regular?

# Answer
Hint: Let $C$ be the language of words that have the same number of 1's as 0's. Is $C$ regular? Let $A = \\{0,1\\}^\* \setminus C$. Is $A$ regular? Now, can you find a non-regular language $B$ that will make $AB$ regular?
> 4 votes

---
Tags: regular-languages
---


# Question
Title: Minimum Length Hamiltonian Path Pair in O(n^2) or better
A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to the following subproblem:

Let $A,B,P,$ and $Q$ be a group of 4 nodes, with coordinates $(x\_A,y\_A),(x\_B,y\_B)$,etc... such that:

* $x\_A$ and $x\_P$ are less than both $x\_B$ and $x\_Q$
* $y\_A$ and $y\_B$ are greater than $y\_P$ and $y\_Q$.

Let there be an arbitrary cluster of nodes contained within the quadrilateral formed by $A,B,P,$ and $Q$. Find a pair of paths $A\rightarrow B$ and $P\rightarrow Q$ such that:

* Every node in the cluster is hit by exactly one of the two paths
* The two paths have the minimum possible total (Euclidean) length
* The two paths do not intersect
* The paths always increase in $x$. That is, if we enumerate path $A\rightarrow B$ as $\\{A,(x\_1,y\_1),(x\_2,y\_2), ...(x\_n,y\_n),B\\}$, then $x\_i\<x\_j$ for $0\<i\<j\leq n$. Also, $x\_A\<x\_1$ and $x\_n\<x\_B$. This property must hold for the $P\rightarrow Q$ path as well.

It is also worth mentioning that no two nodes in the entire problem will have the same $x$ coordinate.

I'm positive some geometric trick will play a huge role in finding the solution. Keep in mind this is just a subproblem and a solution to this in $O(n^2)$ will still be helpful - though I'm hoping for $O(n\log n)$.

Here's an example problem for clarity:

Any solutions or even helpful ideas are always appreciated. Diagrams are also very much appreciated.

Finally, for added clarity, here is what a sample solution might look like:

# Answer
Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$.

In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$. To solve each subproblem, you only have to look at the solution to two subproblems: in particular, to $(Z,P')$ and $(A',Z)$, where $Z$ is the point immediately to the left of the rightmost of $A',P'$. Therefore, each subproblem can be solved in $O(1)$ time. As there are $O(n^2)$ subproblems, the $O(n^2)$ running time follows immediately.
> 2 votes

---
Tags: algorithms, graphs, computational-geometry, search-algorithms, hamiltonian-path
---


# Question
Title: Is the weighted transitive reduction problem NP-hard?
The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$.

When $E^t \subseteq E$ it is NP-complete. When $E^t \subseteq V\times V$ but not necessarily of $E$, this problem is polynomial time solvable. I am wondering about the edge-weighted version without the subset requirement.

My initial feeling was that with weights, the problem is very similar to TSP. The greedy approach seems to be invalid when adding weights. But several articles (http://bioinformatics.oxfordjournals.org/content/26/17/2160.short for instance) seems to imply that the problem is solvable in polynomial time.

If it was easy, then you could just add arbitrarily large edge weights to each edge not in the original edge set and keep the weights at unity for the others. Then you would have a polynomial time algorithm for the subset constrained problem.

So this should mean it HAS to be NP, right?

edit: Are there immidiate examples that come to mind of problems whose unweighted version is easy, but gets hard when weights are added?

edit: by edge-weighted, I mean we are interested in finding the graph with the smallest total edge cost

# Answer
> 0 votes
Consider $G=(V,E)$. Let $w\_{ij} = 1$ if $e\_{ij} \in E$ and let $w\_{ij} \gg 1$ if $e\_{ij} \notin E$. This choice of weights correspond exactly to the constraint $E' \subseteq E$. Thus, if the weighted transitive reduction is polynomial time solvable, then so is the minimum equivalent graph problem.

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


# Question
Title: Lower bounding the minimum equivalent graph
The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$.

The minimum equivalent graph $G' = (V,E')$ is the smallest graph with the same reachability as $G$ with the property $E' \subseteq E$.

Consider the case when $G$ is strongly connected.

The transitive reduction is formed by an arbitrary Hamiltonian cycle, so $|E^t| \equiv |V|$ and so we must have $|E'| \geq |V|$. We want to find a polynomial time algorithm which finds a tighter lower bound than $|V|$ for $|E'|$. I'm wondering if this is possible at all, assuming $P \neq NP$.

If $|E'|\>|V|$, then $G$ can not contain a Hamiltonian cycle . So if we can find a tighter bound in polynomial time, then we have determined the existence of a Hamiltonian cycle in polynomial time.

I think this means that efficiently lower bounding this problem is a wild goose chase. The best bound we can consistently hope for is $|V|$.

Is this a too pessimistic interpretation?

# Answer
Yes it's too pessimistic. If by 'consistently', we mean we will deduce the existance/non-existance of a hamilatonian cycle a $1-\epsilon$ fraction of the time but will get an incorrect answer the rest of the time, we STILL haven't found a polynomial time algorithm that guarantees coming to the correct conclusion. So it isn't theoretically impossible to 'consistently' lower bound this problem.
> 0 votes

---
Tags: graphs, np-complete, np-hard, hamiltonian-path
---


title: Entropy based progress bar

text:
# Question
Title: Entropy based progress bar
Would it be possible to build a progress bar that estimates progress using entropy?

Consider a web browser that is downloading a large file (for instance), which displays a progress bar indicating the amount of progress in the download. Let $X$ denote the value of the complete file; it is not known until the download completes. At time $t$, we have downloaded part of the time, so let $Y\_t$ denote the information/data received by time $t$. Initially, at $t=0$, we do not know $X$ (there is some prior distribution on $X$). The observed data narrows down the set of possible values of $X$. The more we observe, the less uncertainty there is about $X$; once we've finished downloading the entire thing, the value of $X$ is known and there is no more uncertainty.

Could we use the entropy $H(X | Y\_t)$, or something like that, to estimate progress so far and build the progress bar? Would this work theoretically? Would it work in practice? Would it be useful?

Would something similar work for software installation or other uses of progress bars?

# Answer
> 2 votes
For downloading a file, yes, this would work.

For a file download, there is a much simpler method: let $n$ be the total number of bytes of the file to be downloaded, and $k$ the number of bytes we have downloaded so far; then $k/n$ is a good estimate of our progress (the fraction of the file we've downloaded so far).

This turns out to be equivalent to your entropy-based notion, if we assume that the file contents are iid bits (i.e., uniform distribution over all possible files of that length).

So why count bytes instead of use entropy? Well, if they're equivalent, they are just two different ways of describing the same thing. However, it's much simpler to just count bytes. Also, counting bytes has the advantage of being something that can be implemented. Calculating the entropy of the file requires some way to measure entropy, which requires a formula -- and in this case, the formula is to count bytes, so we reduce back to the standard metric.

---

A progress bar for a software update isn't nearly as easy, because it often involves multiple different kinds of operations, which progress at different speeds. Also, there is often no uncertainty: the installer knows exactly what files it is writing. The purpose of the installation is to have a side effect. We want to measure how long it will take until that side effect is completed. It's not clear that this will fit into the entropy framework, because an entropy framework doesn't take into account how long it will take for those side effects to complete. For instance, how long will it take to write one 100MB file and 1000 1KB files? Hard to say, but I can tell you it's not simply proportional to the number of bits in the files, or the number of bits of entropy -- short files may require a seek, so the time to write a file is not proportional to the length of the file.

---
Tags: information-theory
---


# Question
Title: m-functions in Turing's paper "On Computable Numbers and applications..."
I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem".

I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing uses a new way of writing a computation table for a machine. I am totally lost here. I don not understand the examples he gives (starting from page 236) to explain the idea of *skeleton tables*.

I need help with understanding how skeleton tables are to be read, and what they mean.

# Answer
> 2 votes
m-functions are quite similar to what we call today "macros". $f(\dots)$ is just the name of a supplementary m-configuration, that can be parameterized (like a macro). The trick is to not overthink it.

---
Tags: computability, turing-machines, logic, decision-problem
---


# Question
Title: Is it possible to "unshift" onto a queue using this theoretical "queue automaton"?
I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. The production line can test/modify a robot by popping colors off the start of its tape, by moving the robot to different lines depending on the color popped off, and by pushing more colors onto the end of its tape. The tape is effectively a queue.

One level ("Robostilts") asks you, the designer, to build a production line that modifies each robot's tape to put a "green" at the start, and a "yellow" at the end. It turns out this challenge is easily completed because all robots start with only red and blue colors on the tape, and no green or yellows.

However, I initially misinterpreted the challenge, thinking that the input tapes were completely arbitrary. This seemed challenging, and now I think it's impossible. However, I don't know how to show this precisely, but I thought someone here might be able to. I have formalized the problem below.

$A$ is the four-letter alphabet $\\{ R, G, B, Y \\}$.

An automaton is $(S,sInit,sTerm,d)$ where

* $S$ is a set of states
* $sInit \in S$ is the initial state
* $sTerm \in S$ is the terminal state
* $d$ is a transition function $: (S \times A) \rightarrow (S \times A\star)$. (Note: $A\star$ denotes lists of $A$ elements.)

The automaton steps through a series of configurations $(s, x) \in (S \times A\star)$.

For a given "input string" $i \in A\star$, the initial configuration is $(sInit, i)$.

The function $step : (S \times A\star) \rightarrow (S \times A\star)$ is given by

$ step (s, \[x\] \mathbin{+\mkern-10mu+} xs) =\\ \qquad\mathbf{let}\quad(s', new) = d(s,x)\\ \qquad\mathbf{in}\quad(s', xs \mathbin{+\mkern-10mu+} new) $

The task is to define such a machine which, starting with configuration $(sInit, i)$ for an arbitrary $i$, after a finite number of applications of the step function, reaches configuration $(sTerm, \[G\] \mathbin{+\mkern-10mu+} i \mathbin{+\mkern-10mu+} \[Y\])$.

Is this possible? If yes, how? If no, why not?

# Answer
> 1 votes
Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.)

Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(s\_0,x\_0),\dots,(s\_n,x\_n)$ with $s\_0=sInit$, $x\_0=i$, $s\_n=sTerm$, and $(s\_{j+1},x\_{j+1}) = step((s\_j,x\_j))$. In iteration $j$, we read and remove the first letter $a\_j$ of $x\_{j-1}$ and append a word $u\_j$; these first letters form a word $w=a\_1\dots a\_n$.

It is not hard to see that any input word which starts with $w$, i.e. $wv$ for some $v$, is indistinguishable from $i$ to our automaton: it reads the same letters as it would on $i$, and as a result goes through the same states and appends the same $u\_j$, so that the resulting word at the end is $vu\_1\dots u\_n$. This will fail to have the required form for any $v$ not starting with $G$ (and many others as well).

# Answer
> 0 votes
Try to "rotate" the contents of the tape, moving colors from one end to the other. (I did not *really* read the full formalization in your question, so I might be completely off here).

This seems related to the question "How can one simulate a PDA with a FIFO queue PDA?", the simulation of a LIFO (stack) by a FIFO (queue).

---
Tags: automata, computer-games
---


# Question
Title: Handling dead state in NFA to DFA conversion
I want to convert below NFA into DFA:

I prepared below tables and finally the NFA:

**NFA**

However I feel I am wrong here, since original NFA does not have any transitions defined for state C and my final DFA does not have any dead state. However I dont understand where I am going wrong.

# Answer
Your DFA actually looks correct. Why do you need a dead state?

A dead state means the automaton was given a prefix of an input that will never lead to an accepting state. But the language of the NFA has no such prefixes - whatever the prefix is, if you add "10" or "11" you will get to an accepting state.

Anyways, the right thing to do now is to verify that the DFA works fine for several sample inputs. More generally, to prove it actually does decide the language generated by $(0+1)^\*1(0+1)$.
> 2 votes

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


title: worst case of insertion sort

text:
# Question
Title: worst case of insertion sort
what is the worst case of insertion sort ?

# Answer
> 1 votes
Wiki it:

It is O(n^2) or quadratic running time. It is more efficient in practice than selection sort and bubble sort despite the same time complexity as them.

The idea is that you need to take any element and shift elements over so that the sequence of element gradually start to look like it is in order.

You need to iterate n times in the array but do (n-1) shift per iteration.

---
Tags: algorithms
---


# Question
Title: Counting the nodes in a network in a distributed way
There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters).

One of the nodes, say $s$, wants to know $n$. How can it do this?

Each node has $O(\log n)$ memory bits, so it can hold a counter, but not a list of all nodes.

If the network is a tree, I think the following (inefficient) protocol should work:

1. $s$ sends a "Count" message to itself.
2. When a node $v$ receives a "Count" message from node $u$, it acts in the following way:

* Send every neighbour except $u$ a "Count" message and wait for the result.
    * Send $u$ a "Result" message containing the sum of all results (0 if there are no neighbours).

The problem with general graphs is that we may not remember which nodes we already counted, so we might count the same node twice. What to do?

# Answer
> 2 votes
For constant node degrees, the following simple algorithm seems to work: The source node $s$ can initiate a BFS tree construction and then we simply accumulate the count upwards along the tree edges starting from the leafs and ending at $s$. Each node locally keeps track of its parent/children in the tree; note that we can do this using $O(\log n)$ space as the degree is constant and therefore each node knows if it is a leaf.

For arbitrary degree, there's also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds. (In each round, every node can reliably exchange $O(\log n)$ bits with each of its neighbors.)

Suppose that I have a network $G$ with diameter $Diam(G)$.

1. Each node $u$ generates a random value $x\_u$ according to the exponential distribution with rate 1; we round $x\_u$ to $\Theta(\log n)$ bits.
2. Node $u$ also has a local variable $minval\_u$ where it keeps track of the minimum value encountered so far. Initially, $minval\_u = x\_u$.
3. For the next $Diam(G)$ many rounds, node $u$ sends $minval\_u$ to its neighbors. Also, upon receiving $minval\_v$ from some neighbor $v$, node $u$ sets $minval\_u = \min(minval\_u,minval\_v)$.
4. After round $Diam(G)$, node $u$ computes its estimate of the number of nodes as $1/minval\_u$.

**Why does this algorithm work?**

Our algorithm exploits the following nice property of the exponential distribution (see here): If we have $n$ exponential random variables $X\_1,\dots,X\_n$ each of rate $1$, then the random variable $X = \min(X\_1,\dots,X\_n)$ is also exponentially distributed of rate $n$ and therefore has expected value $1/n$. At the end of the algorithm, the $minval\_u$ variable corresponds to a sample of this random variable $X$. Therefore, to get the sought value $n$ (i.e. the number of nodes), we simply compute $1/minval\_u$. To get a high probability bound, we can repeat the above $\Theta(\log n)$ many times and take the average of the produced estimates.

---
Tags: algorithms, graphs, reference-request, distributed-systems
---


# Question
Title: Algorithm to search substring in a circular string?
I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt.

However, as far as I understand, these operate on "regular" strings, but what I need is a substring search on a **circular string**.

A circular string as a string characterized only by its size and the order of the elements, i.e. `ABCD` is the same as `BCDA`, `CDAB` and `DABC`

An source/query example that should succeed:

```
Source string: EFxxxABCxxxxxD
Query string:  DEF

```

Do you know of any references on substring search on circular strings? Any advice on how to do this?

(Possibly) related:

# Answer
Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at least once.

Then perform a simple (non-circular) search on that temporary string.
> 10 votes

---
Tags: algorithms, search-algorithms, strings, substrings
---


# Question
Title: Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?
Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched literals in the clause. This prevents checking every clause for every newly assigned literal.

The correctness of the scheme comes from the fact that clauses are disjunctions and will only be false if *all* literals in it are false. So we know it is not false until at least the watched literal is false, and we only need to check when that happens.

I am wondering why the dual idea of a "watched clause" is not used as well. This is how it would work: the overall formula is a CNF, that is, a conjunction of clauses. The watched literal scheme already checks very fast whether the CNF has become false. However, it would also be useful to detect when it becomes *true*: no further search would be needed then. A conjunction is only true if all clauses in it are true. So we choose one "watched clause" $C$ and, if a literal in $C$ is assigned a value, we check to see if $C$ has turned true. If so, we mark that clause as now irrelevant, and pick another clause not yet satisfied. If we cannot find a not-yet-satisfied clause, all clauses are satisfied and the problem is satisfiable.

I realize this would require keeping track of more information; assigning to literals would now not only require checking if they are watched literals, but also if they are in the watched clause. More importantly, looking for a new watched clause requires checking if other clauses are not yet satisfied, which means checking all their literals. Depending on the structure of the problem instance, this could be much slower. However, for some instances (for example, problems with small clauses) this would be much faster because satisfaction would be detected much sooner.

So my question is whether this is not used simply for empirical reasons (say, it would be slower for most benchmarks), or if there is a deeper flaw about it that I am missing.

A secondary question is: if this is a merely empirical issue, then is there some simple argument predicting this from the description of the technique alone, or is it something that would need to be observed in practice? Or, in other words, if this is a bad idea, is it so in *principle*, or just empirically?

Addendum:

It has been suggested by an answer that the notion of watched literals implies the use of DPLL which implies tracking which clauses have been satisfied, and that therefore the question does not make sense. It is true that watched literals are used in the context of DPLL, but it is not true that this means tracking satisfied clauses.

The paper on Chaff, which defined watched literals, describes DPLL in pseudo-code as

```
while (true) {
    if (!decide()) // if no unassigned vars
        return(satisifiable);
    while (!bcp()) {
        if (!resolveConflict())
            return(not satisfiable);
    }
}

```

This shows that satisfiability is decided as positive only when all variables are assigned, not when all clauses are satisfied (which could happen much earlier). Chaff and zChaff have been the basis for many of modern SAT solvers, including the very prominent MiniSAT.

The same idea is described in detail in Filip Maric's paper "Formalization and Implementation of Modern SAT Solvers", which describes this approach as the basis for many of the most prominent SAT solvers today.

# Answer
A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign. So the only time that a SAT solver would save by early notification is the time it would take to assign values to any remaining unassigned variables. This is a one-time cost linear in the number of variables in the formula. It's linear because there can be no backtracking once the formula is solved.

Meanwhile, to maintain your watched clause pointer you must do a search to find a new unsatisfied clause each time your watched clause is satisfied. That search is linear in the number of clauses in the formula. These searches will be triggered during the exponential part of the search and so you will probably do many of them on your way to finding a satisfying assignment.

The net result is that you will waste more time than you will save trying to immediately notice when all clauses are satisfied.

Note that if you're adapting a traditional SAT solver to *count* solutions, then your idea has more merit. Noticing that all clauses are satisfied while there are still unassigned variables means you have found $2^n$ solutions to the formula, where $n$ is the number of unassigned variables. This provides an exponential speedup over finding these solutions one by one, so the lazy clause tracking could potentially pay for itself. However, an alternative would be to notice a satisfying assignment in the usual way and then undo assignments in reverse order until a clause is left unsatisfied. You would have the same $2^n$ speedup without the clause tracking overhead.
> 12 votes

# Answer
the question/ setup/ premise does not seem to describe the "watched literals" concept accurately/ correctly. here is a summary from a SAT survey paper 2008, Satisfiability Solvers Gomes, Kautz, Sabharwal, Selman p94

> The watched literals scheme of Moskewicz et al. \[170\], introduced in their solver zChaff, is now a standard method used by most SAT solvers for efficient constraint propagation. This technique falls in the category of lazy data structures introduced earlier by Zhang \[236\] in the solver Sato. The key idea behind the watched literals scheme, as the name suggests, is to maintain and “watch” two special literals for each active (i.e., not yet satisfied) clause that are not FALSE under the current partial assignment; these literals could either be set to TRUE or be as yet unassigned. Recall that empty clauses halt the DPLL process and unit clauses are immediately satisfied. Hence, one can always find such watched literals in all active clauses.

the description earlier of DPLL in the chapter has the same mechanism/ terminology; "active" clauses are those not yet satisfied. (afaik) virtually every SAT technique keeps track of "active" clauses vs those that are currently unsatisfied under the current partial assignment. the "watched literal" concept is already tightly coupled with keeping track of active clauses as the question seems to wonder about.
> -2 votes

---
Tags: satisfiability, sat-solvers, constraint-satisfaction
---


# Question
Title: Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization
I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear.

Given the following constraints:

* Two sets, each with 'n' elements: 'donors' and 'recipients'. $|D| = |R| = n $
* Each donor has a maximal number of times they are able to be matched with a recipient: "max donations". $ maxd: D \to \mathbb{Z}\_{+}$
* A distance function, returning a real number representing the suitability of match between a donor and a recipient, given the number of times a donor has already "donated" / been matched with a recipient. $ distance: D \times R \times \mathbb{Z}\_{+} \to \mathbb{R}\_{+} $

Devise a parallel algorithm to determine the list of optimal matching. i.e. find functions $m: D \to \mathcal{P}(R)$ which defines a partition of $R$ and $l: D \times R \to \mathbb{Z}\_{+} $ such that $\forall d \in D$ $ | m(d) | \leq maxd(d)$

which minimize the following cost:

$$ \sum\_{d \in D} \sum\_{r \in m(d)} distance(d, r, l(d, r)) $$

Intuitively, I think this is NP-hard. So I was satisfied with my solution - using BSP treat the donations per donor in phases, where each iteration is a graph matching problem.

Is this the best I can do? Any suggestions?

# Answer
> 1 votes
This can be reduced to an instance of the minimum-cost flow problem.

Build a flow network from your graph, with an edge from each donor to each recipient whose maximum flow is $1$ and whose cost is the negation of the value of that matching. Add a source vertex $s$, with an edge of weight $\text{maxd}(d)$ and cost $0$ to each donor $d \in D$. Add a sink vertex $t$ with an edge of cost $0$ and maximum weight $\infty$ from each recipient to $t$. Now compute the minimum-cost flow. This can be done in polynomial time, so your problem can be solved in polynomial time.

So your question boils down to asking whether there are parallel algorithms for min-cost flow. Searching the literature will turn up a bunch of algorithms for that. If you use Google Scholar, you can find a number of papers on that subject.

---
Tags: algorithms, graphs, optimization, parallel-computing
---


# Question
Title: Integer Knapsack Problem - No duplicates Allowed
In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given capacity C, provided we cannot use an already used item twice.

In their book, Introduction to Algorithms, the authors have mentioned that for Dynamic programming to be applicable we MUST have "independent" subproblems. That is, the solution to one subproblem should not affect another subproblem. They have illustrated this through the "Longest-Path-Problem" in which they mention that once we solve a subproblem of finding the longest path from 'A' to 'B', for solving another subproblem, we would not be able to use the vertices used in the longest path from 'A' to 'B' and hence the subproblems are not independent.

Doesn't the same argument apply here as well - If we solve a subproblem of filling a smaller knapsack of capacity c \< C, we cannot use the items used in filling 'c', in solving other subproblems.

I am new to dynamic programming - apologies if my question appears to be stupid.

Thanks.

# Answer
> 1 votes
You are right about "independence" between subproblems. Therefore, you use the new subproblems (wiki) by introducing another variable $i$, meaning using the items up to $i$:

> Define $V\[i,s\]$ to be the maximum value ($V$) that can be attained with size less than or equal to $s$ using items up to $i$ (the first $i$ items).

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


title: Worst case bisection of binary tree

text:
# Question
Title: Worst case bisection of binary tree
My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.

# Answer
Consider a simple binary tree $T$ with only 4 nodes: The root of $T$ is $A$. $A$ has a left child $B$ which has two children $C$ and $D$.
> 1 votes

# Answer
Nobody said that $3/4$ was the optimal number. In fact, it seems like $2/3$ might be achievable. Starting at the root, consider a walk which always chooses the child with the larger subtree. Consider the first time that you reach a node whose subtree contains less than $2/3$ of the nodes. Its parent's subtree contains more than $2/3$ of the nodes, so the subtree rooted at its larger child contains at least $1/3$ of the nodes. So we have found a node whose subtree contains between $1/3$ and $2/3$ of the nodes.

Considering the tree with one root and two children, we see that we can't in general obtain a better balanced partition.
> 1 votes

---
Tags: binary-trees
---


title: Paxos: Instances, Rounds, Phases

text:
# Question
Title: Paxos: Instances, Rounds, Phases
In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

In addition, I found a number of sources which indicate there are three phases in Paxos: an $accept$ phase, $propose$ phase and a $learning$ phase, in which a distinguished learner informs all other participants of the chosen value. For example: http://pdos.csail.mit.edu/6.824-2007/labs/lab-8.html

Which is true?

If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?

# Answer
**Q1:** *Lamport describes a round of Paxos as two phases: a prepare phase, and an accept phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?*

I don't think Lamport uses the term "round" to organize the two phases, at least it is not the case in the "Paxos Made Simple" paper. Actually, the word "round" only occurs once in that paper and it is used to refer to the *communication* round.

The term "round" is used in James Aspnes' lecture notes to refer to

> the collection of all messages labeled with some particular proposal $n$.

It is important to distinguish between the definition of "round" here and the "communication round". In this sense, a round is dedicated to a single proposal (and belongs to a single proposer), because different proposals have globally unique timestamps.

---

**Q2:** *I found a number of sources which indicate there are three phases in Paxos. Which is true?*

As explained in James Aspnes' lecture notes,

> Note that acceptance is a purely local phenomenon; additional messages are needed to detect which if any proposals have been accepted by a majority of acceptors. Typically this involves a fourth round, where acceptors send accepted(n, v) to all learners.

In the "Paxos Made Simple" paper, Lamport mentions the "learning" phase in Section 2.3 (see Page 6). Notice that it is a fourth phase in Aspnes' lecture note.

---

**Q3:** *If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?*

In the classic formalization of Paxos, there are three roles which are *proposers, acceptors, and learners*. Learners are required to learn the chosen value. So the "learning" algorithm in Section 2.3 is (there are other variants):

> We can have the *acceptors* respond with their *acceptances* to a distinguished *learner*, which in turn informs the other *learners* when a value has been *chosen*.

In this approach, all acceptors send every proposal they have accepted to the distinguished learner. The distinguished learner (locally) regards a value to be *chosen* only when it is accepted by a majority of acceptors. Then, the chosen value is propagated to other learners.
> 2 votes

---
Tags: distributed-systems
---


title: The initial NP-complete problem

text:
# Question
Title: The initial NP-complete problem
It is always claimed that Cook and Levin gives the very first NP-complete problem and proof of it.

But when I look at the actual proof I think what Cook and Levin did was reduced (or transformed) SAT to "P-bound NTM acceptance" problem.

Formally, we define

> A P-bound NTM is a non-deterministic Turing machine that was given a polynomial expression `p(n)` associate with it, such that if `n` is the size of the input string, and it accepts the string iff there is an execution sequence the NTM halt at an final state within `p(n)` steps.

The "P-bound NTM acceptance" problem is:

> For given input string `s`, and a P-bound NTM `T`, is that `T` accepts `s`?

So if I understand right, what Cook presented in his proof is

> Given an instance of **P-bound NTM acceptance**, there is a polynomial reduction/translation that convert this instance into an instance of **SAT**. (**P-bound NTM acceptance** reduce to **SAT**)

with this and an easier fact that

> Every instance of NP problems can be reduced into an instance of **P-bound NTM acceptance**. (**P-bound NTM acceptance** is NP-hard)

lead us to the conclusion : SAT is both NP-hard and in NP, so it is NP-complete

But in addition to that we can also see

> **P-bound NTM acceptance** can be resolved with an NTM within polynomial time. (**P-bound NTM acceptance** is in NP)

This should be straight forward. The only thing to worry about is we are simulating an NTM so we need to think about the guessing staff. Fortunately we are also defining an NTM, so what we actually need is a non-deterministic universal Turing machine.

Running this machine would not require more than polynomial additional time.

According to this we have

> **P-bound NTM acceptance** is NP-complete.

I am not to disregard Cook/Levin's work, instead, their work is still very important and historical as they finished the first NP-complete proof.

However if I were right would it open some another view of the NP-complete problems? If we use other computation model for example, the "P-bound NTM acceptance" will be different, and if some clever computation model was invented we could be able to use this result to solve `P=?NP` problem.

Also I think if we see **P-bound NTM acceptance** instead of SAT as the first (or zeroth?) NP-complete problem it would help people understand the proof of Cook-Levin's proof.

**Question**

Given that every existing proof of NP-complete results is actually through it (yes, they are going through SAT, and SAT going through it), is this a natural, intuitive view that "P-bound NTM acceptance" is the ultimate initial NP-complete problem?

**Is this only a matter of defintion**

A comment suggests this is "P-bound NTM acceptance" is the definition of NP.

The definition of NP is (Skudkamp, Languages and Machines edition 3, Def 15.2.2)

> A language L is said to be accepted in nondeterministic polynomial time if there is a nondeterministic Turing machine $M$ that accepts L within $tc\_M \in O(n^r)$, where $r$ is a natural number independent of $n$. The family of languages accepted in nondeterministic polynomial time is denoted $NP$.

So the problem "Is language $L \in NP$"? is defined as

> Is there a nondeterministic Turing machine $M$ that accepts L within $tc\_M \in O(n^r)$, where $r$ is a natural number independent of $n$?

This is not exactly the same as "P-bound NTM acceptance".

In general, the `f(n)` bound TM acceptance problem is not in complexity `O(f(n))`. Although it is true that you can always simulate the TM within `f(n)` steps, but the simulation will introduce additional work, not just to decode the machine and simulation its action, but also the need to check the simulation steps is actually within the bound.

This increases the time complexity, and it is not trivial in general. See time hierachy theorems, there is a proof of "there are languages can be accepted in O(n^2) but not in O(n)" based on this argument.

It is true that "P-bound NTM acceptance" is in NP simply because those additional work can be done in P time.

It is to know that this "P-bound NTM acceptance is in NP" is also implied by Cook's theorem because SAT is in NP and PNA reduces to it. However, a direct proof is also straight forward.

# Answer
> 3 votes
The definition of $\mathcal{NP}$ essentially immediately gives an $\mathcal{NP}$-complete problem (P-bounded NTM acceptance), what Cook and Levin gave was a proof that this automata theoretic problem could be turned into a *"natural"* problem (for a certain definition of natural). So mostly people are being lazy when they refer to $SAT$ as the "first" $\mathcal{NP}$-complete problem. What they mean is that it is the first *not-completely-obvious* $\mathcal{NP}$-complete problem.

More importantly, along with Karp's work very soon thereafter, it helped show that the class $\mathcal{NP}$ had a useful, important meaning; that it somehow "tightly" characterised a certain level of hardness of a whole raft of well known computational problems.

Some other things worth noting:

1. Cook doesn't mention $\mathcal{NP}$ at all - it had only just been invented at the time he was writing "The complexity of theorem-proving procedures". So it's only in retrospect that we recognise it as an $\mathcal{NP}$-completeness proof (admittedly, this realization took very little time - it was an exciting period for this foundational work).
2. Levin, in a strict sense, didn't even give a proof of $\mathcal{NP}$-completeness, he was working with search problems (Russians always have to show off and do it the hard way).

---
Tags: np-complete, satisfiability
---


# Question
Title: Why is $\emptyset L = L\emptyset = \emptyset$ correct?
I am taking a course on Automaton where I faced the algebraic laws of regular expressions.

First two were ok:

> 1. $\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language gives the language $L$ itself.
> 2. $\epsilon L = L\epsilon = L$: Concatenation of empty string with strings belonging to certain language $L$ gives back the set of string of language $L$

But the third one is confusing me:

> 3. $\emptyset L = L\emptyset = \emptyset$

I felt it should be $\emptyset L = L\emptyset = L$, since concatenation of strings of language L with string of empty language which is essentially no strings at all (which essentially means nothing to concatenate), should give back the language $L$ itself. Where I am thinking wrong?

# Answer
> 13 votes
$L\_1L\_2$ means the set of all strings you can make by choosing one from $L\_1$ and one from $L\_2$ and concatenating the two strings. So how many ways can you choose a string from the empty set of strings and one from $L$? None at all! So there are no such concatenations and $\emptyset L = \emptyset$.

The key point is that $\emptyset$ is the language that contains no strings at all. The empty string is a string (it's the string with no letters at all) so the empty string is not a member of the empty language: $\\{\epsilon\\}\neq\emptyset$.

# Answer
> 8 votes
Just to complete David's nice answer with a simple observation:

Since $$ L\_1L\_2 =\\{ uv \mid u\in L\_1, v\in L\_2\\},$$

then, the size of this new language admits $$ |L\_1L\_2| \le |L\_1|\cdot|L\_2|$$ because, for each word in $L\_1$ we add $|L\_2|$ words to $L\_1L\_2$. Maybe some of the new words were already added before, which causes the inequality.

Then, it is immediate that $|\emptyset L| \le 0\cdot |L| \le 0$, thus $\emptyset L$ must be the empty language.

---
Tags: formal-languages
---


# Question
Title: Hamiltonian circuit for a family of graphs
For $\Sigma = \\{a,b\\}$, let $S\_n = \\{w\mid w \in \Sigma^{\*} \land |w| = n\\}$.

Let $C\_n \subset \Sigma^{\*}$ be the language of circular strings that contain as substrings all elements of $S\_n$. For instance, $bbaaaababaabbbba \in C\_4$

I have formulated the problem of finding the subset of $C\_n$, formed by the circular strings with the **smallest size** ($=2^n$), as the problem of finding all hamiltonian circuits on the graph that has the elements of $S\_n$ as vertices, and edges connecting all pairs of vertices $s\_i$ and $s\_j$ such that $s\_i = xw$ and $s\_j = wy$, with $w \in \Sigma^{n-1}$ and $x,y \in \Sigma$.

For the example above, the graph could look like this:

My question:

> Would there be a polynomial-time solution for the hamilton circuit problem restricted to this family of graphs?

# Answer
This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).
> 4 votes

---
Tags: search-algorithms, strings, hamiltonian-path, hamiltonian-circuit
---


# Question
Title: It is possible to implement insertion sort for sorting linked list ?
it is possible to implement insertion sort for sorting linked lists ? will it have the same O(n^2) efficiency as the array version ?

# Answer
> 2 votes
This question is fully answered by the Wikipedia page on insertion sort. In summary, yes, you can implement insertion sort on a linked list with the same efficiency as for an array because insertion sort only makes sequential accesses to the data being sorted. Every time it accesses the data, it's looking at "this element", "the next/previous element" or "that element I was looking at a few moments ago and whose index/position in the list I already stored."

---
Tags: algorithms, algorithm-analysis, sorting
---


title: Mergesort with $O(n^2 \log n)$ runtime

text:
# Question
Title: Mergesort with $O(n^2 \log n)$ runtime
I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is $O(1)$. I think that I have to work with comparison-complexity but I dont know how to create a runtime of $O(n^2 \log n)$ since mergesort has best and worst-case complexity of $O(n \log n)$. Could anybody help me out creating a problem to achieve a runtime of $O(n^2 \log n)$ ?

# Answer
> 3 votes
Remember what $O(\cdot)$ means. You don't need to do anything. Mergesort has a running time of $O(n\log n)$ which is already $O(n^2 \log n)$, $O(2^n)$ and $O(\text{any larger function you want})$.

---
Tags: algorithms, asymptotics, runtime-analysis
---


# Question
Title: Is it possible that low-resource Turing Machines can always "usually" agree with high-resource Turing Machines
Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs.

It is known that there are problems in $TIME(n^{3})$ that are not in $TIME(n^2)$. But is it possible that, for every language $L \in TIME(n^{3})$, there is a $.99$ approximation in $TIME(n^2)$?

I'm also curious about this question with respect to other computational resources: Nondeterminstic Time, Space, and Randomness (although I'm not even sure if there is a BPTIME hierarchy theorem, so it might be hard to answer for randomness).

# Answer
Okay, I realized there's an uninteresting answer to this question via a "slow" diagonalization argument. Let ${M\_k}$ be an enumeration of the machines that run in $TIME(n^2)$. Define $\bar{M}$ to be the machine that does the opposite of $M\_k$ on all inputs of length $k$. Then $\bar{M}$ is in $TIME(n^{2 + \epsilon})$, but there is no machine in $TIME(n^2)$ that is a $0.001$ approximation of $\bar{M}$, because there is some input length on which the two machines disagree everywhere.

I don't feel like this really captures the spirit of the question, though, and I'm going to try to think about how to re-formalize it. Maybe I want to say something about circuits? Like: is it possible that for all circuits on $n$ input wires, $SIZE(c)$ has a $.99$ approximation of $SIZE(c+1)$?
> 1 votes

---
Tags: complexity-theory, time-complexity, approximation
---


# Question
Title: Use Rice's theorem to prove the following is undecidable
Given the language $L=\\{\alpha \mid M\_{\alpha}(x)=x^3$ for all $x\in\\{0,1\\}^\*\\}$. Prove using Rice's theorem that $L$ is undecidable.

Rice's theorem: Let $P$ be a set of all computable functions $f:\\{0,1\\}^\*\rightarrow \\{0,1\\}^\*$(i.e all functions which have a corresponding turing machine $M$, such that $M(x)=f(x)$). Let $C\subseteq P$, where $C\neq\emptyset$. Then deciding if a turing machine $M$corresponds to a function $f\in C$, is an undecidable problem.

So I need to show that deciding if a string $x$ is in $L$, is equivalent to deciding if a function $f\in C$, where $C\subseteq P$. But I don't even know where to begin with showing this.

# Answer
I believe Rice's Theorem also needs $C$ to be actually different from $P$, otherwise, it is also a trivial property.

In your case, you have a property of recursively enumerable languages, and you need to show it is not trivial. To do so, you just need to find a Turing Machine that doesn't belong to $L$, and one that does.
> -1 votes

---
Tags: complexity-theory, undecidability, rice-theorem
---


title: What makes an MILP problem solvable?

text:
# Question
Title: What makes an MILP problem solvable?
Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic programming and 0-1 assignment problem can be solved using Hungarian algorithm in polynomial time. So what makes a MILP problem solvable? Is there any reference? Thanks

# Answer
> 3 votes
You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains the tractability of assignment and maximum flow problems.

I'm not aware of any "reason" why knapsack is pseudopolynomial time solvable.

---
Tags: algorithms, optimization, discrete-mathematics, knapsack-problems, assignment-problem
---


# Question
Title: How is electricity brought to the transistors?
I feel like my knowledge of computer science is being hindered by this one concept. I understand the concepts of transistors and how a flow of electricity can turn a transistor on or off, and with the power of logic gates, this can form the foundation of programming. What I do not understand is how these microscopic transistors are turned on or off, and how electricity gets there in the first place. Thanks.

# Answer
> 2 votes
Electrictiy is brought by wires as usual. But electricity involves 2 kinds of characteristics: voltage (in Volts: V) and current (in Amperes: A). Transitors and other similar devices come in various types. The basic idea is that there are three connectors. A reference connector (ground), and two others. One correspond to a control circuit and the other to a controlled circuit. The transistor can have a high or low resistance to current produced by some source, thus controlling the flow of electricity and the voltage between the ground and the controlled circuit connector. The state high or low resistance is fixed by a small current (bipolar transistor) or by a voltage (triode vacuum tube, field-effect transistor) between the control connector and the ground.

The ground connector is called the emitter, source or cathode, for respectively the bipolar transistor, field-effect transistor and triode. The controlling connector is the base, gate, or grid, and the controlled connector is the collector, drain or anode.

The idea is that the controlling circuit uses little energy to transmit a logical signal to a circuit that can carry much more energy (the product of voltage and intensity). This can regenerate a distorted signal, and also make it powerful enough to be sent to several other circuits, or actuate other devices. With appropriate circuitry it makes for the various logical gates.

The simplest device to understand may the triode, though it is not a transistor, strictly speaking, but its vacuum tube ancestor. There is a voltage between cathode and anode, and by heating the cathode, the (negatively charged) electrons are freed and can be attacted by the anode that has a positive charge. However, there is the grid in between: if the grid has a positive voltage, it will atract the electrons even more, and they will speed through it with enough momentum to go through (most of them) and reach the anode. But if the grid is charged negatively, it will create an obstacle that electrons cross with difficulty and little current will atually go through. The working of the field-effect transistor (FET) has some similarity to that, but I am no specialist.

---
Tags: memory-hardware
---


title: Studying Programming Language Theory

text:
# Question
Title: Studying Programming Language Theory
I have recently become extremely interested in understanding and proving aspects of (functional) programming languages.

However as I dive deeper in, things like $\lambda$ calculus, category theory, and denotational semantics are a little difficult to grok without proper explanation.

I read SICP (quite an enlightening book) but I'm looking to dive deeper into the theory of functional programming. Are there any books/blogs/sites/you-name-it that would discuss the theory of functional programming languages from the ground up?

# Answer
> 10 votes
It is not easy to come by books that consider the denotational semantics of $\lambda$-calculus. One possibility is:

1. Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi

Type-theoretic accounts are easier to get hold of:

1. Bob Harper, Practical Foundations of Programming Languages (there is also a printed version).
2. Benjamin Pierce, Types and Programming Languages.
3. Frank Pfenning's course on Computation and Deduction, I think he also published a book with the same title.

# Answer
> 2 votes
**A new answer to an old question**. You might be interested in Category Theory for Programmers by Bartosz Milewski. More generally, you can look at Bartosz Milewski's Programming Cafe blog.

# Answer
> -3 votes
These books have high ratings and come up on different scientific communities:

Type Theory and Functional Programming by Simon Thompson.

Structure and Interpretation of Computer Programs

---
Tags: reference-request, lambda-calculus, functional-programming, books
---


title: Identity productions in regular grammar

text:
# Question
Title: Identity productions in regular grammar
If a grammar is of the following form (i.e. all its productions are), is its language regular?

1. $B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$
2. $B → aC$ - where $B$ and $C$ are in $N$ and $a$ is in $Σ$
3. $B → ε$ - where $B$ is in $N$ and $ε$ denotes the empty string, i.e. the string of length 0.
4. $B → A$ - where $A$ and $B$ are non-terminals in $N$

(1. - 3. quoted from wikipedia)

I only added the 4th rule and I assume that the language **is** regular. However, I cannot find any reference that supports this intuition.

# Answer
> 2 votes
Yes the language is regular.

Productions 2 and 3 are like transitions in a finite state automaton: $B \to aC$ is like moving from state $B$ to state $C$ while reading $a$; $B\to \varepsilon$ indicates that $B$ is like a final state where we can stop the computation (i.e., end the dirivation in grammar terminology).

The production $A\to B$ is like an $\varepsilon$-transition in finite state automata. This may be practical, but does not change the language generating capabilities of the grammars.

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


title: What's a trivial property?

text:
# Question
Title: What's a trivial property?
I have to show a property P is trivial.

This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?

# Answer
> 13 votes
A "trivial" property is one that holds either for all languages or for none.

# Answer
> 4 votes
A "property" is simply a subset of languages in $RE$ -- the set of all the languages that "satisfy" that property. A *non-trivial* property $P$ is a non-empty set $P$ which is strictly contained in $RE$, that is $\emptyset \subset P\subset RE$. It means there is at least one RE language that doesn't satisfy $P$, and at least one RE language that does satisfy it.

Examples:

The property: "the language is finite." Formal definition: $P = \\{ L \mid |L|\<\infty\\}$. This property is non-trivial.

The property: "The language can be recognized by a TM". Formally: $P=\\{ L \mid \exists M \text{ s.t. } L=L(M)\\}$. This property is trivial: in fact $P=RE$, that is, ALL **RE** languages satisfy it.

The property: "The language has a reduction from the non-halting problem". Formally: $P = \\{ L \mid \overline{HP} \le L\\} \cap RE$. This property is trivial: in fact, $P=\emptyset$.

---
Tags: terminology, computability, rice-theorem
---


title: What is known about this TSP variant?

text:
# Question
Title: What is known about this TSP variant?
> This question was cross-posted to cstheory.SE here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

**Problem: How should your fly your helicopter to minimize travel distance?**

More precisely, given a real number $R\>0$ and $N$ distinct points $\\{p\_1, p\_2, \ldots, p\_N\\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.

# Answer
> 1 votes
Huck Bennett has answered this question on cstheory.SE here.

> This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.
>
> A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).
>
> As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.

---
Tags: approximation, traveling-salesman
---


# Question
Title: How can there be stop and wait protocol for a simplex channel?
Doesn't the receiver have to send back an acknowledgement frame? So how can it send back a frame, since a simplex channel only allows transmission in one direction?

# Answer
> 2 votes
Some writers use the term "simplex" to mean that communication is only possible in one direction. Others use it to mean that communication is possible in both directions but not at the same time; this is also called "half-duplex". I suspect that the protocol you're talking about is for a half-duplex channel: the sender transmits for a while and then pauses to allow the receiver to use the channel in the opposite direction for acknowledgments.

---
Tags: computer-networks
---


title: Database normalization impractical

text:
# Question
Title: Database normalization impractical
After third form normalization, extra tables shall be created. And the functional determinant are used as primary key in the new table, as foreign key in the modified old table. My question is that following this strategy, the referential integrity enforces that when attributes have to be added to the new table before attributes can be added to the "old" table. one can't add attributes to the "Old" table first. However, in my application, it is more intuitive to add attributes in the old table first. It appears to me the normalization rule is not very applicable in such situation.

# Answer
> 1 votes
Database tables are not just files. In a way, they are also abstract entities. During the process of normalization of an existing dataset, a foreign key must coexist with the table to which it refers, so that referential integrity is never relaxed. In practice, this is not possible, but any intermediate steps should be considered only as implementation level issues.

That said, I can't see why creating the secondary table before updating the "old" table would be counterintuitive.

For the sake of intuitiveness, you can say that the "old" table will disappear, after the normalization process has been finished. Only new tables will be there, including a new *version* of the old table, with the foreign key already in place, and filled with data.

---
Tags: database-theory, databases, normal-forms
---


# Question
Title: Formalizing basic category theory in Coq
I'm a total beginner in Coq and I'm trying to implement some category theory stuff as an exercise.

I surfed a little among git repos of the many avaible such implementations (HoTT, Awodey's Coq companion, etc.) it seems that every single project implements something like that

```
Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : ob -> ob -> Type ;
    compose : forall x y z : ob,
                mor x y -> mor y z -> mor x z ;
    identity : forall x, mor x x ;
    (* ... axioms ... *)
  }.

```

It is kind of natural, considering most definition of categories in modern book. However, I feel that it would be easier to implement it *internally* (if not mistaken, it was the common definition at Grothendieck's time) :

> **Definition.** A category is the data of
>
> * a set/class $\rm Ob$ of objects,
> * a set/class $\rm Mor$ of morphisms,
> * functions $s,t \colon {\rm Mor} \to {\rm Ob}$, and $i \colon {\rm Ob} \to {\rm Mor}$ ($s$ stands for *source*, $t$ for *target*, and $i$ for *identity*)
> * a function $\circ \colon {\rm Mor} \times\_{s,t} {\rm Mor} \to {\rm Mor}$ whose domain is the fiber product of $${\rm Mor} \stackrel s \to {\rm Ob} \stackrel t \leftarrow {\rm Mor}$$
>
> satisfying some axioms...

The advantage of such a definition is that it generalizes directly by replacing "set/class" by "objects of some category" and "functions" by "morphisms of this category", leading to the concept of *internal category*. (Then you can talk of topological/differential categories, or categories inside a topos, etc.)

My problem is to formalize the fiber product in Coq. My first attemp would be to do something like

```
Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : Type ;
    s : mor -> ob ;
    t : mor -> ob ;
    compose : mor -> mor -> option mor ;
    i : ob -> mor ;

    adequacy : forall f g : mor,
                 (exists h, (compose f g) = (some h)) -> (t f = s g) ;
    (* ... axioms ... *)
  }.

```

But I feel that could lead to some curbersome later code. For example, chained compositions would be difficult to read.

Is there a project with an implementation based on the internal definition? Is there a quick way to define the fiber product I need in Coq?

**Edit.** By the way, I see a lot of

```
Ob :> Type

```

rather of

```
Ob : Type

```

What is the meaning of the extra "\>"? From the doc, it seems it is some kind of *coercion*. What exactly does this mean?

# Answer
A natural way to write down what you want is to *restrict* the type of composition to only the "composable" morphisms:

$$ \mathrm{compose}:\forall f\ g: \mathrm{mor}, t(f) = s(g)\rightarrow \mathrm{mor}$$

adding, of course, the conditions: $$ s(\mathrm{compose}\ f\ g\ e)=s(f)$$ $$ t(\mathrm{compose}\ f\ g\ e)=t(g)$$

This works, as it now only allows composing functions that are provably composable. This roughly corresponds to the fibered product in category theory you were mentioning.

However is somewhat awkward as it adds *proof obligations* to every application of `compose`, which can quickly become unmanageable (even expressing associativity is hard!). Also it somewhat precludes adding the notation $\circ=\mathrm{compose}$, since `compose` takes 3 arguments.

This is a somewhat common problem in type theory, which results from the fundamental tension of having **partial functions** in a total language.

Another, less elegant solution, is to define composition to be *everywhere defined*: $$ \mathrm{compose} :\mathrm{mor}\rightarrow\mathrm{mor}\rightarrow\mathrm{mor}$$ and guard every theorem involving composition with *well-definedness* conditions:

$$\mathrm{assoc}:\forall f g h:\mathrm{mor}, t(f)=s(g)\wedge t(g)=s(h)\Rightarrow\\ \mathrm{compose}\ f\ (\mathrm{compose}\ g\ h) = \mathrm{compose}\ (\mathrm{compose}\ f\ g)\ h $$ This essentially means:

> `compose` is defined everywhere, but the definition is only **meaningful** if applied to composable morphisms.

This approach also has drawbacks, mostly the gargantuan quantity of proof obligations that follow every application of the basic axioms.

I'm afraid you have to choose your poison in this case, or come up with a clever way to do better...
> 4 votes

# Answer
After some struggling, I think the best way to do what I want is to actually encode the fiber product of type through its universal property.

It goes along that kind of lines:

```
Class FiberProduct (A B C : Type) (f : A -> C) (g : B -> C) : Type :=
  {
    FiberProductCarrier : Type ;
    FiberProductProj_1 : FiberProductCarrier -> A ;
    FiberProductProj_2 : FiberProductCarrier -> B ;
    FiberProductCommutativity :
      forall x : FiberProductCarrier,
        f (FiberProductProj_1 x) = g (FiberProductProj_2 x) ;
    FiberProductUniversalExistence :
      forall X : Type, forall (p_1 : X -> A) (p_2 : X -> B),
        (forall x : X, f (p_1 x) = g (p_2 x)) ->
        (exists h : X -> FiberProductCarrier,
           (forall x : X, FiberProductProj_1 (h x) = p_1 x
                          /\ FiberProductProj_2 (h x) = p_2 x)) ;
    FiberProductUniversalUniqueness :
      forall X : Type, forall (p_1 : X -> A) (p_2 : X -> B),
        (forall x : X, f (p_1 x) = g (p_2 x)) ->
        (forall k l : X -> FiberProductCarrier,
           (forall x : X, FiberProductProj_1 (k x) = p_1 x
                          /\ FiberProductProj_2 (k x) = p_2 x
                          /\ FiberProductProj_1 (l x) = p_1 x
                          /\ FiberProductProj_2 (l x) = p_2 x)
           -> k = l)
  }.

```

Then the internal version of the notion of category is given by:

```
Class InternalCategory : Type :=
  {
    ob : Type ;
    mor : Type ;
    s : mor -> ob ;
    t : mor -> ob ;
    i : ob -> mor ;
    comp_domain : FiberProduct mor mor ob s t ;
    comp : FiberProductCarrier  -> mor  ;
    (* axioms *)
    asso :
      forall fg_h f_gh : FiberProductCarrier,
        (exists fg gh : FiberProductCarrier,
           FiberProductProj_1 fg_h = comp fg /\
           FiberProductProj_2 f_gh = comp gh /\
           FiberProductProj_1 fg = FiberProductProj_1 f_gh /\
           FiberProductProj_2 fg = FiberProductProj_1 gh /\
           FiberProductProj_2 gh = FiberProductProj_2 fg_h) ->
        (comp fg_h = comp f_gh) ;
    id_right :
      forall fid : FiberProductCarrier,
      forall f : mor,
        (FiberProductProj_1 fid = f) ->
        (exists x : ob, FiberProductProj_2 fid = i x) ->
        (comp fid = f) ;
    id_left :
      forall idf : FiberProductCarrier,
      forall f : mor,
        (FiberProductProj_2 idf = f) ->
        (exists x : ob, FiberProductProj_1 idf = i x) ->
        (comp idf = f) ;
    id_s :
      forall x, s (i x) = x ;
    id_t :
      forall x, t (i x) = x
  }.

```
> 0 votes

---
Tags: reference-request, category-theory, coq
---


# Question
Title: Why can't edit distance be solved as L1 distance?
Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to transform $x$ into $y$.

If $m = \max ( \text{len}(x),\text{len}(y) )$ then padding with appropriate zeroes on the smaller string one can define $x$ and $y$ as both being elements of $\Sigma^m$. Now both $x$ and $y$ are vertices of the cube $\Sigma^m$.

Now isn't $\text{ed}(x,y)$ the shortest distance between $x$ and $y$ in this cube graph? Why isn't edit distance found by finding shortest paths in this cube?

# Answer
> 4 votes
Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.

---
Tags: shortest-path, edit-distance
---


# Question
Title: How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?
The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$.

The wikipedia article on $LOGCFL$ says that it is situated between $NL$ and $AC^1$. I read this as $NL\subset LOGCFL\subset LOGCFL/poly=SAC^1\subset AC^1$, hence $NL\subset SAC^1$.

Obviously $L\subset NL$, so we get the nice summary $$NC^1\subset L \subset NL \subset SAC^1$$

But the statement $SAC^1=LOGCFL/poly$ makes me wonder, whether $NC^1\subset L$ or rather $$NC^1\subset L/poly \subset NL/poly \subset SAC^1$$

---

Honestly, I'm really unsure now. So I googled a bit, and found lecture notes introducing Boolean circuits with even more doubtful statements

> The usual convention is not to count "not" gates in either of the above: one can show that all the "not" gates of a circuit can be pushed to immediately follow the input gates; thus, ignoring "not" gates affects the size by at most $n$ and the depth by at most $1$.

I heavily doubt that this statement is "exactly" true. I feel reminded of the wikipedia article on Fagin's lemma, and similar "sloppy CS statements". But how am I supposed to read such sloppy statements, and how can I guess what they are intended to mean?

# Answer
The source of the confusion is probably *uniformity*. A circuit class like $\mathsf{NC}^1$ can be defined in two different ways:

1. Languages computed by bounded fan-in circuits of polynomial size and logarithmic depth.
2. Same as 1, only the circuits are *uniform*: there is an efficient Turing machine that on input $1^n$ generates the $n$th circuit.

The definition of uniformity is vague since there are several different definitions, many of them fitting the above description (with different definitions of *efficient*). The classic paper On uniformity within $\mathsf{NC}^1$ shows that many of these definition are in fact equivalent, and as far as I know, their common definition remains popular today. It often goes by the name "$\mathsf{AC}^0$-uniform".

If you want $\mathsf{NC}^1 \subseteq \mathsf{L}$ then you need the uniform version of $\mathsf{NC}^1$. If you want $\mathsf{NL}/poly \subseteq \mathsf{SAC}^1$ then you need the non-uniform version of $\mathsf{SAC}^1$.
> 3 votes

---
Tags: complexity-theory, circuits
---


title: Complexity terminology

text:
# Question
Title: Complexity terminology
What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ?

Thank you

# Answer
One common keyword that denotes this concept in contradistinction to asymptotic complexity is *concrete complexity*.
> 3 votes

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: NFA: Regular Language that starts with ab but does not end with ab?
$L = \\{x \in \\{a,b\\}^\* \mid \text{$x$ starts with $ab$ but does not end with $ab$}\\}$

I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them onto an image site if necessary. However if you choose to help, you can always put them in a table.

I get the main part, but for some reason I cannot construct this particular NFA.

# Answer
If you have managed to produce an automaton that accepts all words starting $ab$ and an automaton accepting all words that don't end with $ab$, you're most of the way there. You can then either use the product construction to take their intersection or use the same ideas you used to produce each individual automaton to produce a single automaton that performs both tasks.

For strings that don't end $ab$, mouse-over the hint below if you need it.

> Use the state of the automaton to "remember" the last two characters you saw. If they were $a$ and $b$ in that order, the state should be rejecting; otherwise, it should be accepting. That way, when you get to the end of the input, you're in an accepting state iff the last two things you saw were not $a$ and $b$, in that order.
> 2 votes

# Answer
If you can´t draw a NFA from the definition of a language $L$ but you are convinced that $L$ is regular then you can try to write a regular grammar $G$ that denotes $L$.

For this example $G= \\{N,\Sigma,S,P\\}$ with:

$N= \\{S,X,F\\}$

$\Sigma= \\{a,b\\}$

$S=S$

$P= \\{$

$\quad S\to abX | abb$

$\quad X\to aX | bX | F$

$\quad F\to a | bb$

$\\}$

Now you can build a NFA from this grammar. The non-terminals are the states of the NFA. The initial state is the start symbol of the grammar. The transitions are obtained from the production rules of the grammar. We add auxiliar states as they are needed. The production rules of the type: $\alpha -\> \beta$ with $\alpha \in N$ and $\beta \in \Sigma^\*$ will lead you to a final state. Finally the NFA is:
> 1 votes

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$
Is this a CFL? $$\\{a^n b^m c^k\\; : \\;k\>m \\; \\; k\>n\\}$$

When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop them so when my $TOS$ of stack is empty and input is$ c $,I do not make any changes in the stack and that clearly implies that i have no of $c$'s to be greater than both $a$ and $b$.

But its supoosedly not a CFL. Need help where I'm going wrong in constructing the PDA. Because supposedly a PDA can be made for this which makes it a CFL.

# Answer
Are you really sure your PDA recognizes that language. You state that the "number of c's to be greater than both a and b", but it is supposed to be no greater than each, separately, not together. Maybe you could try the pumping lemma on this language.
> 1 votes

---
Tags: context-free, automata, pushdown-automata, context-sensitive
---


# Question
Title: In what sense is the Mandelbrot set "computable"?
The Mandelbrot set is a beautiful creature in Mathematics.

There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense.

However, what concerns me is the fact that it is not even recursively enumerable - simply because the set is uncountable. This could be resolved by requiring some sort of finite representation of the points.

Furthermore, although we know for sure that a lot of points belong to the set and others do not, there are also a lot of points whose membership in the set we don't know. All the images we've seen so far may include a lot of points that "up to n iterations kept in bound," but those points may not actually belong to the set.

So, for a given point with a finite presentation, the problem "Does this point belong to the set?" has not been proved to be decidable yet, if I am right.

Now, in what sense (by which definition) can we say the Mandelbrot set is "computable"?

# Answer
> 17 votes
There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine similar to a RAM machine, whose access to real numbers is restricted to basic arithmetic and comparisons. Blum and Smale showed that the Mandelbrot set is uncomputable in this model, though its complement can be recursively enumerated using the traditional algorithm used for drawing them.

Another model is computable analysis, in which the Mandelbrot set is probably computable, as shown by Hertling (conditional on a widely believed conjecture, the hyperbolicity conjecture). In this model, computing the Mandelbrot set means being able to compute an approximation to the Mandelbrot set, within any desired accuracy (for the exact definition, see the reference on computable analysis).

Why is it, then, that the computer seems to be able to draw the Mandelbrot set? The main difficulty in showing that the traditional algorithm works is that it is difficult to tell in advance how many iterations to run before we decide that the point belongs to the set. Hertling shows that if the widely believed hyperbolicity conjecture holds, then there is a reasonable such bound. Presumably, the programs simply wait long enough; or they don't wait long enough, but only get a small fraction of the points wrong.

# Answer
> 11 votes
Basically, the Mandelbrot set is not computable (as far as we know). The fact that you see images does not mean it is computable. Those images are computing using an approximation: if the process runs longer than a set threshold, as a heuristic, the code assumes that it will never terminate. This heuristic can be wrong, and as a result those images might not be 100% accurate. In other words, those pictures are not an image of "the" Mandelbrot set; they are of an approximation to the Mandelbrot set.

---
Tags: computability
---


# Question
Title: How to improve my these specific math skills?
I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I know how to code I can't solve it. For example, if I don't know the formula for area of circle, I can't find it no matter how good I am at coding.

Have a look at this problem from a programming competition, I did not know how to solve it until `Tad` posted that it was `Assignment Problem` and it can be solved with `Hungarian Algorithm`.After knowing `Hungarian Algorithm` it was pretty easy to solve. Now you can see problem is with my math skills. I am looking for some resources where I can find such `ALL`(if not `ALL` then `MOST`) algorithms which a programmer/software engineer is supposed to know.

# Answer
I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without math, won't be able to solve really interesting problems.

Unfortunately there is no "Learn all algorithms you'll ever need in 21 days for dummies" book. There are hundreds, possibly thousands, of algorithms—even more if you also consider data structures—and it just isn't possible for anyone to know them all. There are no shortcuts to algorithms and math, something which has frustrated me numerous times too. All you can do is throw yourself in and let the knowledge slowly build up.

I would recommend getting yourself a good book on algorithms—my choice would probably be Steve Skiena's The Algorithm Design Manual since it assumes less math background than the more popular Introduction to Algorithms—and a good book on discrete math, of which there are several. I've heard good reviews of *Concrete Mathematics* but haven't read it as it's a little pricey. Sometimes books use the term "discrete math" in confusing ways; make sure the one you get covers at least graph theory, recurrence relations, Boolean algebra, basic set theory, basic combinatorics, and basic probablity, as those are the most vital topics for a software developer. A book on statistics and probablity, like this one, freely available online and written by a professor from my university, wouldn't go amiss either. And both linear algebra and abstract algebra are useful surprisingly often; I like Gilbert Strang's *Linear Algebra and its Applications* and Charles Pinter's *A Book of Abstract Algebra* for these topics.

Of course, just buying these books isn't enough, even if you then proceed to read them. Doing every exercise is a decent start, though probably too dry. I would do exercises until I had drilled down the basics. To really get into these topics, you have to work on problems that use them, which aren't really as hard to find as they might seem. A simple spell checker might calculate Levenshtein distance to suggest corrections for a misspelled word, which allows you to practice dynamic programming. Games and simulations have all sorts of uses for graph algorithms; I implemented the Floyd-Warshall Algorithm in Javascript for a game once, and Dijkstra's Shortest Path algorithm and A\* are widely used in games. Project Euler is a great source for number theoretic and combinatorial algorithms. Also make sure not to neglect data structures; try solving some problems that revolve around sets or maps in a lower level language (C, C++, or Java) and implementing your own skip list or red-black tree or hash set. Although these data structures are often available in libraries, the concepts you learn by implementing them are widely applicable (e.g. I never would have understood the Rabin-Karp Algorithm without knowing about hash tables, because it uses hashing, in addition to number theory).

The great thing about this is that not only will you learn algorithms, you'll also get better at coding, and get more familiar with your chosen programming language, by being forced to solve unfamiliar problems. If there's some feature of your language that you've always wanted to use and never been able to, these kinds of exercises are a great way to do that too; I first really dug into Java generics while working on a problem about binary trees.

Finally, just remember that you don't have to know every algorithm off the top of your head. The Hungarian Algorithm in the question you linked is a special purpose algorithm for linear algebra. It's not something most programmers ever have to deal with. Contests do not reflect reality in that way. A contest might expect you to have memorized obscure algorithms and be able to implement them from scratch without any references in a short period of time. When you encounter problems in the wild, it's much more vital that you can clearly state the problem, identify what kind of technique or approach might be helpful, and do research to find something that can solve your problem. In my opinion, it's much more important to look at a problem about matrices, be able to think "This problem is about matrices. I should look at some linear algebra algorithms. Those are probably in a book about numerical algorithms", and then be able to find the Hungarian Algorithm and implement it, than it is to memorize that algorithm and be able to code it off the top of your head.
> 6 votes

---
Tags: algorithms, complexity-theory, terminology, data-structures, discrete-mathematics
---