Expected Behavior of FFT I am debugging an FFT.  My FFT uses complex numbers in polar form, $(r,\theta)$.

I am trying to establish that it works, with a unit test.  My real values are all correct, after a polynomial multiplication...

However, I pad out my polynomials to a power of two with complex zeros, and when the multiplication is complete, I have random angle values in the polar form of the complex numbers.

For instance, I multiply the following polynomials, listed in standard form by their coefficients:

$$
A = \lbrace1,2,3\rbrace\\
B = \lbrace4,5,6\rbrace\\
$$

And I am expecting the answer to be:
$$
C = \lbrace (4,0),(13,0),(28,0),(27,0),(18,0),(0,0),(0,0),(0,0)\rbrace
$$

However, my FFT returns this exactly (ignoring floating point errors), except the last three terms are:

$$
C = \lbrace \ldots,(0,4.518),(0,0.4769),(0,2.2877)\rbrace
$$

My question is whether these angle values in the extra terms are expected, or whether this is a sign of something going wrong in my FFT code?

(this is tricky for me, because it seems like everything is calculating correctly; and shouldn't it not work at all in a d&c if something is wrong?)

Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones).

The zero-padding does not introduce new data, does not change sampling frequency of the original signal, it just interpolates the values. In your example there are 5 points, padding them to 8 introduces additional result bins that are closer to each other - this makes particular frequency bin shift, which is stored in the phase component of the result.

So the most probably your FFT is fine, just the test changes the distance between frequency bins, but this step is not included in reading phase, so the test is faulty.


in refutation (resolution) can we use a clause that have been resolved In resolution if we have a set S composed of three clause C1, C2 and C3 and we want to proof that C4 is derivable from S using refutation:

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C3 or C4 or C2 cause even it has been resolved?

and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from or initial set I= {S, ¬C4} and add the resolvent instead?

and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

thank you for claryfing things.

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C2?

No, not really. If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies. And if C1 can be resolved with C5, then it can also be resolved with C2 in a second way (assuming C1 is not a tautology, and hence cannot be resolved with itself).

  can we resolve C1 with C3 or C4 cause even it has been resolved?

We can (and often must) resolve C1 with C3, even so it has already been resolved with C2. We don't need to resolve any clause with C4 itself, rather the negation of C4 must be brought into a conjunctive normal form. The clauses of that normal for have to be added to our set S.

  and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from our initial set I= {S, ¬C4} and add the resolvent instead?

No, that would be too simple. What you actually do is to select a variable that you want to eliminate from the clauses in the set S, and then:

for every clause C containing the variable and every clause N containing the negation of the variable

resolve C and N and add the resolvent to the set S

remove all original clauses containing the variable or its negation from the set S

Of course, you could also eliminate a variable by considering both possible assignments separately. It is said that those two approaches are equivalent in a certain sense, yet the approach to consider the assignments separately allows for backtracking, which keeps the memory consumption low by removing the need for explicit representation of the resolvents.

  and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

We stop once we find ⊥.

  thank you for claryfing things.

The question is tagged first-order-logic, but none of your questions even touched unification. Your questions also indicate that the resolution rule somehow seems to feel like magic to you. But the resolution rule itself is basically just the cut rule, which is an inference rule of sequent calculus:
$\cfrac{\Gamma \vdash \Delta, A \qquad A, \Gamma' \vdash \Delta'} {\Gamma, \Gamma' \vdash \Delta, \Delta'}$

The cut rule itself is just the appropriate formulation of transitivity of implication
$\cfrac{A \vdash B \qquad B \vdash C} {A \vdash C}$
in the context of sequent calculus (where you can have both a left ($\Gamma$) and a right ($\Delta$) context). A sequent $A_1,\dots,A_r \vdash B_1,\dots,B_s$ can be read as $(A_1\land\dots\land A_r) \to (B_1\lor\dots\lor B_s)$, which is equivalent to the clause $\lnot A_1\lor\dots\lor \lnot A_r \lor B_1\lor\dots\lor B_s$.

Whether this is helpful or not is of course a matter of taste. By getting rid of negation, one can write down deductions more symmetrically (and the sequent calculus has established conventions avoiding all those dots when writing things down). You could verify the assertion that "If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies." for example by checking that the deductions
$\cfrac{\Gamma \vdash B, \Delta, A \qquad A, \Gamma', B \vdash \Delta'} {\Gamma, \Gamma', B \vdash B, \Delta, \Delta'}$
and
$\cfrac{\Gamma, B \vdash \Delta, A \qquad A, \Gamma' \vdash B, \Delta'} {\Gamma, B, \Gamma' \vdash \Delta, B, \Delta'}$
cover all relevant cases.


Set combination data structure (And storage complexity) I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place.

I have a problem where I am required to associate unique combinations from a set (unique subsets) to a given value. e.g.: Let S={a, b, c, d}, the required data structure should perform the following:

Key -> value

{a,b} -> value1
{a,c} -> value2
{c,d} -> value3

Property 1: The length of the set in the key is fixed (In this
example it's fixed to 2).
Property 2: The data structure does not
hold all possible subsets of S.

Question 1: What is the storage complexity of a simple Map holding these values? O(N!)? (given that |S| = N and it's not fixed)

Question 2: Is there any efficient data structure that could store such elements? (The most important efficiency would be required in storage complexity)

Question 1:  The storage complexity of a map for holding these values is $\Theta(m)$, where $m$ is the number of entries in the map, assuming we don't count the space to store the sets themselves, and assuming we store them in a hash table (or similar data structure).

This doesn't include the space to store the sets in the keys, as those presumably already exist.  If you want to include that space as well in your estimate of the space complexity, then we need at most $\Theta(m)$ space for the map, plus $\Theta(mk)$ space to hold the sets (assuming each set contains $k$ elements), for a total of $\Theta(mk)$ space.  I am assuming that each element of $S$ can be stored in a single word ($\Theta(1)$ space), e.g., that $n \le 2^{64}$.  If $n$ is huge, so that an element of $S$ cannot be stored in a single word, a better estimate of the total space usage is $\Theta(mk \lg n)$, since it takes $\Theta(\lg n)$ bits to store a single element of $S$, each subset of $k$ elements takes $\Theta(k \lg n)$ bits, and there are $m$ entries in the map, each of which requires $\Theta(k \lg n)$ bits to store it.

The number of unique subsets of size $k$, out of a universe of $n$ items, is ${n \choose k}$.  Therefore, if you know that the keys are subsets of size $k$, you know that $m \le {n \choose k}$.  But you mentioned in the question that the number of entries in the map is less than all possible subsets of size $k$, so this isn't helpful.

Question 2: Yes, a hash table would be an efficient data structure to store these elements.  There's a straightforward way to define a hash function on subsets of $S$, so you can use that to build a hash table.  A hash table achieves the space complexities listed above.


Why absence of surjection with the power set is not enough to prove the existence of an undecidable language? From this statement

  As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language.

I would like to understand why similar reasoning does not work with a finite set $B$ which also has no surjection onto $\mathcal{P}(B)$!  (with $|B|=K$ and $K \in \mathbb{N}$)

Why is there a minimum need for the infinite set?

EDIT Note:

Although I chose an answer, many answers and all comments are important.

Let us first recapitulate in which context the cited statement makes sense.

Let us restrict ourselves to the domain of (decision) functions in $\mathbb{N} \to \{0,1\}$ (a subset of all functions).
Every such function corresponds to one element of $\mathcal{P}(\mathbb{N})$ (see characteristic function).
There are countably many Turing machines (simple encoding).

By 1. and 2., there are uncountably many functions. Therefore, there are functions that have no corresponding Turing machine, that is they are not computable. There are simply too many functions; this is what is meant by "there is no surjection".

Now, there are only countably many finite sets in $\mathcal{P}(\mathbb{N})$(extension of Cantor's pairing function). Therefore, the same contradiction can not be derived when only considering finite sets.

If you add some infinite sets to your base set so it becomes uncountable, there is no reason to believe some of the finite sets were undecidable; you only know that there are some undecidable sets. In fact, all finite sets are decidable, so the culprits are always infinite sets.


variable in turing machine Here is a simple turing machine, that accepts only $0$.

For this, it read $0$, write it with $x$, then move to right and checks end, if it is end it accepts.

With that logic, I can also add this 1->x,R, then it accepts all strings of length 1, {'0','1'}.

What I want to do is, instead of writing to logic I want to write one, $anything$ -> $another_thing$,R.

Can I do it?

A Turing machine diagram is a form of communication. Its goal is to describe a Turing machine — usually defined as a tuple with a specific format — in a form which is easier to grasp. As such, you can use whatever shortcut you want, as long as everybody understands what you mean. This might entail your explaining some non-standard notation which you invented as shorthand.

Your professor might have different ideas about this, but the answer I gave is valid for the working mathematician.


From $P=NP$ to $NP=NL$ Does $P=NP$ implies $3SAT$ reduces to $2SAT$?

If so then from $2SAT$ is $NL$-complete can we conclude $NP=NL$?

Yes and no.

If P=NP, then every problem in NP, in particular 3SAT, can be solved in polynomial time. Hence it reduces to every nontrivial problem (and 2SAT is nontrivial) using polynomial time reductions. Which are the reductions in the definition of NP-hardness.

NL, on the other hand, is not closed under polynomial time reductions (unless NL=P), as these can use polynomial space (exceeding logarithmic space). That is why for the definition of NL-hardness, logspace reductions are used. Hence neither can we conclude that 3SAT is in NL, nor that NL=NP.


Algorithm for getting symetric vertex sets of undirected graph For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph.

My definition of symmetric vertex set is:
Let $G$ be a graph with vertex set $V$ and edge set $E = \{u,v\}, u,v \in V$. If $S \subseteq V$ and there exits an isomorphism $f$ on this graph such that for every $v\in S$, we have $f(v) \in S$, then $S$ is called a symmetric vertex set.

I have searched some graph matching algorithms, but have gotten no clue so far. I am wondering if any one can give me a hint, I will work on it.

You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from which you can easily compute the orbits of its action on the vertices.

Solving GI using your task. Given connected graphs $G_1,G_2$, we want to know whether they are isomorphic. Compute the orbits, and check whether any of them mixes vertices from $G_1$ and $G_2$.

Solving your task using GI. Given a graph $G$ and two vertices $x,y$, create two copies of $G$ and attach a long path to $x$ in one of them and to $y$ in the other. The two vertices belong to the same orbit if these graphs are isomorphic.

The second reduction involves $n^2$ invocations of GI, whereas $\log B_n \approx n\log n$ (here $B_n$, the $n$th Bell number, is the number of partitions of $\{1,\ldots,n\}$). This means that any reduction needs $\Omega(n\log n)$ invocations of GI, and suggests that my reduction can be improved.


Is relative regularity distinct from regularity? Let $L$ and $G$ be languages over a finite alphabet $\Sigma$.
$L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input in $G \setminus L$; the behaviour of the automaton on inputs in $\Sigma^{*}\setminus G$ is not specified.
Here are some simple facts about relative regularity.

If $G$ is regular, then so is any $L$ that is regular relative to $G$.
If $L$ is regular then it is also regular relative to any $G \subseteq \Sigma^{*}$ in which it is contained.
If $L \subseteq G$ and $G \setminus L$ is regular then $L$ is regular relative to $G$.
It is possible that $L$ is regular and regular relative to $G$, but $G$ is not regular.  (Let $\Sigma = \{0,1\}$, $L = \emptyset$ and take $G$ to be some non-regular language such as the palindromes.)
It is possible that $L$ and $G$ are not regular but $L$ is regular relative to $G$.  (Just take $G=L$.)
$L$ is regular relative to $G$ iff $L \subseteq G$ and there is some language $S \subseteq \Sigma^{*}\setminus G$ such that $L \cup S$ is regular.

  If $L$ is regular relative to some $G \subseteq \Sigma^{*}$, and $G \setminus L$ is not a regular language, is $L$ always regular?

That last fact suggests that the answer should be no, but I can't think of a counterexample.

If this is a standard exercise or the concept has a name then I would appreciate a pointer.


Can terms "interpreter" and "processor" be used interchangably? I do not ask you to respect that the processor is a physical black box whereas interpreter implementation is not that clear. As CS, you must look at the functionality aspect -- both processor (physical machine?) and interpreter (virtual machine?) execute a program (a stream of commands).

Isn't to interpret the code just means to evaluate/to execute/to process it?

There is a long article on interpretation in Wikipedia. It uses a lot of words to explain what is interpretation and it even says that it is execution of instruction stream. But nobody stood up and stated that it is just what the processor does (like the child in the "Emperor new clothes")! Why should we think that these are two different things? Processors even invented JIT-compilation (called microcoding) earlier than virtual machines.

Also, bytecode interpretation should give additional clue. It looks like machine code absolutely (to be executed by virtual machines). So, are interpreters just virtual processors?

The self-checking questions are:

What if vendor of your favorite processor discloses you a terrible secret that your instructions are not executed directly but converted into a true machine language beneath, before submitted to the real processor, is you language interpreted or machine?
What if instruction stream for a real processor is executed by emulator (virtual machine) then is it executed by the processor or interpreted?
Can the processor that executes an interpreted language (bytecode or script) is not a processor anymore but an interpreter?

Usually, an interpreter is defined in computing terms: it executes instructions by issuing instructions to some lower level of processing. A processor is defined in physical terms: it executes instructions in electronic circuits. It's an interpreter if its behavior is ultimately defined by computer scientists, and a processor if its behavior is ultimately defined by physicists.

There's an exception: if the interpreter is defined in terms of emulating something that would normally be a physical processor, it's called a processor.

But it's only a matter of terminology. There's no profound distinction here. Just go with the flow.

Mu. It's an interpreted machine language. Many processors work that way anyway (where do you draw the line between instruction decoding and interpretation? why would you want to draw a line?).
Mu. It's a processor, and the processor is interpreted.
Mu. If you posit that the language is interpreted then by definition it's interpreted by an interpreter. The interpreter may be a processor.


Regular expression for words longer than 2 containing at most two x-s I want to make a regular expression for the language consisting of words whose length is at least 3 and which contain at most two $x$'s, that is,
$$\{w\in \{x,y\}^* \mid |w|\geq3\text{ and the number of }x\text{'s in }w \text{ is at most } 2\}$$
I wrote:
$$
x^+(x+y)^+y^+
$$

Your regular expression accepts the word $xxxy$, which contains too many $x$s.
We can break down words in your language into three different kinds:

No $x$s, and so at least three many $y$s.
One $x$. In that case, the word is of the form $y^ixy^j$, with $i+j \geq 2$. This means that either $i = 0$ and $j \geq 2$, or $i = 1$ and $j \geq 1$, or $i \geq 2$.
0 Two $x$s. In that case, the word is of the form $y^ixy^jxy^k$, with $i+j+k \geq 1$. This means that either $i=j=0$ and $k \geq 1$, or $i=0$ and $j \geq 1$, or $i \geq 1$.

Putting everything together, we reach
$$
yyy^+ + xyy^+ + yxy^+ + yy^+xy^* + xxy^+ + xy^+xy^* + y^+xy^*xy^*.
$$
As a bonus, this regular expression is "unambiguous", in the sense that each word belongs to exactly one summand.
We can shorten this expression in many ways. For example, notice that if we consider only words with exactly two $x$s, we can obtain all words in the language by optionally replacing an $x$ with a $y$. This gives us the simpler expression
$$
(x+y)^2y^+ + (x+y)y^+(x+y)y^* + y^+(x+y)y^*(x+y)y^*.
$$
If we want something more symmetric, we can take
$$
y^+(x+y)y^*(x+y)y^* + y^*(x+y)y^+(x+y)y^* + y^*(x+y)y^*(x+y)y^+.
$$


Ant colony optimization algorithm if i have an equation like
            $$f_n = x + y + z + a + b$$
and each variable has a discrete answer like $a = 0, 1 , 3$ . $b = 2 ,4,5$ etc.
i want to find the global optimum minimization point. I used Ant colony optimization (ACO) to solve the equation but i am stuck in the heuristic information and how to compute these parameters, as I saw in the traveling sale's man problem eta = one over distance between two cities. But here there is no relation between $x$ and $y$ .

Second i want to make sure that when computing $\delta_\tau$ pheromone updating trail , its equal to $$f_n(\text{best answer in iteration k})\over f_n(\text{worth answer in iteration k})$$ as i saw another equations in papers and got distracted.
I built a matlab model but it didn't give me the optimum point at each run time .
Thank you

There is no simple answer for how to choose parameters.  This is a heuristic, so there are no guarantees.

Here are a few strategies that are widely used:

Random search: Try many different parameters.  In each trial, you randomly choose all parameters, solve the optimization problem using those parameters, and then remember the solution.  Take the best solution found.
Grid search: Systematically search over the space of possible parameters.  For instance, if there are two parameters $\alpha$ and $\beta$, you might let $\alpha$ range over values $0.1$, $1$, $10$, and $100$, and let $\beta range over a similar set, and try all combinations; then take the best solution found.
Try smaller problems: Construct a smaller problem (e.g., synthetically).  Find the best parameter settings for it (by applying one of the prior two methods).  Then, use those parameter settings on your larger problem, and hope they'll be good for your larger problem, too.


How can follow this this guide to construct a graph with matrix/reachability Let's we have k matrices. For example we have 3 now,  where first one is 8x5  ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out if possible to multiply within any given matrices and reach a matrix of dimension x and y, when x and y is given ahead of time. In this example, (8x5) x (5x6) x (6x8), end up a 8x8 matrix.   The hints is given, but I cannot visualize. Any more help is appreciated. can understand the first step, but have not idea about the second one.

First, we can define nodes in the graph as the values of each $a_i$
and each $b_i$, and put an edge from $a_i$ to $b_i$.
Second, Whenever there is a chain of matrices $M_{i1},...M_{ik}$, we
can multiply, then x=$a_{i1}$ has an edge to $b_{i1} =a_{i2}$, and
$a_{i2}$ has an edge to $b_{i2}$ =$a_{i3}$, and so on, up until
$b_{ik}$ =y. So there could be a path from x to y in this
graph.
Third, Inversely, for any path from x to y, the edges form a chain of
matrices that we can multiply, which create a x x y matrix.
therefore, x is reachable from y in the graph iff there is a
chain of matrices which from the x x y matrix.

The first step create something like this ?
>  x-->
> n8-->n5
> n5-->n6
> n6-->n8
>   -->y

What is $M_{i1}$, $a_{i1}$ and $b_{i1}$? How does that differ to $a_{1}$ ?

Okay let's say you got $n$ matrices $M_1,M_2,...,M_n$ with dimensions $a_1\times b_1,...,a_n\times b_n$.
Now we look at what happens to the dimension when we multiply two matrices $M_i, M_j, i\neq j$:
$$(a_i\times b_i)(a_j\times b_j) = a_i \times b_j$$
Notice that you can only multiply the two matrices iff $b_i = a_j = p$:
$$(a_i\times p)(p\times b_j) = a_i \times b_j$$
You might spot the pattern here: only the first dimension of the first matrix and the last dimension of the last matrix matter. Thus in order to get a matrix with dimensions $(x\ times y)$ you need a chain of matrices looking like that:
$$(x \times e_1)(e_1 \times e_2)(e_2 \times e_3)...(e_n\times y) = (x\times y)$$
where $e_i$ are just arbitrary numbers. This looks similar to a path in a graph, where you are walking from the node labeled with x to a node labeled with y.
Notice that for every node in the graph if it represents the first component of the dimension ($a_i$) of a matrix $M_i$ it's connected to the second component of the dimension ($b_i$).
Meaning $a_i$ and $b_i$ are connected. Secondly the second component of a dimension $b_i$ of a matrix $M_i$ is connected to all first components $a_j, i\neq j$ that have the same value ($b_i = a_j$). Now if  there is a path from $x$ to $y$ in a graph you can build an equation as shown above.
The graph in your particular example looks like this:
8(a1) -> 5(b1)
5(b1) -> 5(a2)
5(a2) -> 6(b2)
6(b2) -> 6(a3)
6(a3) -> 8(b3)

Now $8 = a_1 = x$ is your starting point and $8 = b_3 = y$ is your end point.
EDIT: Construction algorithm:
Input: arrays a,b with n elements
Output: adjacency list A of size 2*n
A = new array of 2*n lists
for i = 1 to n: A[i].add(i+n)
for i = 1 to n:
   for j = 1 to n:
      if b[i] == a[j]:
          A[i+n].add(j)

Notice that $A[i\leq n]$ corresponds to the node for $a_i$ and $A[n+i\leq 2n]$ corresponds to the node for $b_{i}$. Now if you want to check if you can build a matrix with a certain dimension $(x,y)$ you search through $a$ to find $i$ such that $a[i] = x$ and start a dfs or bfs from node $i$ which has the neighbors $A[i]$ and you stop your search when you arrive at node $n+j$ such that $b[j] == y$.


How does FDS (flat datacenter storage) make optimizations around locality unnecessary? I was reading the following computer systems paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

And I was trying to understand why it claims that it does not need data locality for it be perform well.

Basically, in the abstract it says:

"...FDS multiplexes an application's large scale I/O across the available throughput and latency budget of every disk in a closer. FDS therefore makes many optimizations around data locality unnecessary."

What I was not sure was, why does multiplexing an applications I/O across the servers in the datacenter, make it unnecessary to have to optimize in terms of data locality?

Basically, as I read the paper they make a big deal that locality is something they don't need and that they can achieve the benefits of it without having servers being close to the clients they provide data access. The part I am not sure is, what is the crux of what makes them not depend on data locality? Is it the CLOS network? Is it because they don't serve clients around the world? Is it because their servers are all in one data center anyways and not scattered around the world? What is it that makes their performance be so amazing?

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

The paper you cited is exploring the consequences of the question "what if datacenter network bandwidth was free?"  There are two reasons you might care about data locality.  One is latency and the other is bandwidth.  The workloads they are looking at (mostly) don't care about latency, and they've made bandwidth irrelevant, hence locality doesn't matter.  (Note however that at the end of Section 6.2 (on Page 12) they discuss how the inefficiency of non-local accesses forced them to use more compute nodes for their sorting algorithm.)

They also aren't completely eliminating locality optimizations.  Each compute node is still caching/buffering reads and writes in its local DRAM.  The rule of "avoid unnecessary I/O" still stands.  It's just that you don't make a distinction when you do a disk access of whether the disk is near or far from your compute node.  All disk accesses are assumed to include the extra latency of a round-trip network traversal.

Here's a picture to show the difference. The authors' "flat" storage model is on the left, the traditional "distributed" storage model is on the right:

In the distributed model (on the right) data is either on a local disk or a remote disk.  In the flat model (on the left) data is all remote.  But since the network bandwidth is (effectively) infinite, this doesn't reduce your maximum data bandwidth.


Create NOT gate from other gates If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?

Consider a circuit having a single NOT gate, computing some function $f(x)$. We can write $f(x) = g(x,\lnot h(x))$, where $g,h$ are monotone functions.

Consider now a sequence of inputs $x_0 < x_1 < \cdots < x_n$ (i.e., $x_0$ is the zero input, and $x_i$ is obtained from $x_{i-1}$ by changing one bit from 0 to 1). Since $h$ is monotone, it is either constant on $x_0,\ldots,x_n$, or $h(x_0) = \cdots = h(x_i) = 0$ and $h(x_{i+1}) = \cdots = h(x_n) = 1$ for some $i$. In the former case, $f(x_0) \leq \cdots \leq f(x_n)$. In the latter case, $f(x_0) \leq \cdots \leq f(x_i)$ and $f(x_{i+1}) \leq \cdots \leq f(x_n)$. This means that the sequence $f(x_0),\ldots,f(x_n)$ flips from 1 to 0 at most once.

It follows that the complement of the parity function on three bits cannot be computed using a single NOT gate. Indeed, if it could, then consider $x_0=000$, $x_1=001$, $x_2=011$, $x_3=111$. Then $f(x_0),f(x_1),f(x_2),f(x_3)=1,0,1,0$ flips twice from 1 to 0.

This shows that you cannot simulate an arbitrary number of NOT gates using a single NOT gate.


Ball Break Point Problem I came across following question:

There is a building with N floors. We have a balls of same property and have a breaking point of X floor. i.e, If ball dropped from X+1 floor then the ball will break. if ball is dropped from X or less than X then it wont break. Now design an algorithm to find X if N is given.

My Solution:

Drop the ball from N/2 floor. If ball breaks then X < N/2. Else X > N/2. Repeat this process till X is found.
but If X is N/2+1 or N/2-1 the number of steps to find X are high.

Is there a better way to Find X?

This is the best way to Find $X$. Your algorithm is basically binary search, which is optimal in terms of comparisons.

Let $T(N)$ be the number of ball-drops required in a building with $N$ floors to find $X$.
\begin{align}
T(1) = & 0 & \text{(no balldrop with one floor)}\\
T(N) = & T(\frac{N}{2}) + 1& \text{(drop ball once, repeat on upper/lower half)} \\
      = & T(0) + 1 + \ldots + 1 \in \mathcal{O}(\log n)
\end{align}

Each floor $i$ of the $N$ floors can be represented as binary number with $\lceil \log_2N\rceil$ bits. To identify one number out of a set of $N$ numbers, you have to look at each single bit, hence this takes you $\lceil\log_2 N\rceil \in \mathcal{O}(\log n)$ comparsons. So in terms of complexity, there is no better way to find $X$.

Of course, you could check one floor above as well as one floor under the current floor, which covers the cases $X=\frac{N}{2}+1$ and $X=\frac{N}{2}-1$, respectively. But you this does not improve your algorithm in terms of $\mathcal{O}$ complexity. Furthermore, you can always construct another worst case for you algorithm, since $N$ is unbounded: The improved algorithm performs poorly when $X=\frac{N}{2}-2$ or $X=\frac{N}{2}+2$. So you could add those cases as well. But then $X=\frac{N}{2}-3$ and $X=\frac{N}{2}+3$ becomes a problem ...


Finding a method to classify pixels according to how drastic their intensity change I am looking for a method to classify pixels into three groups: (1) Pixels which does not change their intensity much in general (the slight changes may be due to noise only), (2) Pixels which change their intensity very slowly, in general monotonically and gradually, and (3) Pixels which change their intensity drastically over a certain threshold.

I tried using the Running Gaussian Average Method, such as checking how many standard deviations the current pixel is away from the running mean. The pixel is classified as group (1) when the result is very small, as group (3) when the result is very large, and (2) otherwise. But it does not seem to work very well, especially for group (2) because by definition, this group contains pixels which change their intensity moderately instead.

I expect I may need to build 2 or more models, because background subtraction methods normally result in classifying the pixels into 2 groups only, but here I need to classify pixels into 3 groups. Any ideas will be welcome. Thanks!

One approach to distinguish between (1) vs (2)-or-(3) is to use a statistical hypothesis test.  A statistical hypothesis test can tell you whether the amount of change is too large to be explained by random chance.  One reasonable approach might be to use linear regression: try to model intensity as a linear function of time $y = at+b$, and then use a statistical hypothesis test to see whether the coefficient $a$ is positive (i.e., $a>0$ and the null hypothesis $a=0$ can be rejected at a 99% significance level).

Once you've identified all the type-(1) pixels, it's not clear how to distinguish between (2) vs (3), because you haven't given us a precise definition of what counts as drastic vs slow.  One reasonable approach would be to again use linear regression, and then use a threshold $\alpha$: if it's not a type-(1) pixel and $0<a\le \alpha$, then classify it as type (2), else if if it's not a type-(1) pixel and $a \ge \alpha$, then classify it as type (3).  You'd have to set the threshold $\alpha$ in some way that's appropriate for your application.  You could of course consider variations on this, e.g., where the linear regression only considers observations from the last 10 seconds of time (or whatever), or weights more recent observations more highly, etc.


Proof of composition of one way function is not one way in general In this How to show composition of one way function is not such? question, the accepted answer uses g(x,y) as a one way function.
But, for a given output of g(x,y) = 0|x| of length l (say), isn't the output of g(any x of length l, 0l) the same as the earlier output? Isn't this a possible preimage of 0|x|?

"for a given output of g(x,y) = 0|x| of length l (say)," "the output of g(any x of length l, 0l)"

is "the same as the earlier output", which means that is "a possible preimage of 0|x|".

Accordingly, for  $g\hspace{-0.04 in}\circ \hspace{-0.03 in}f$  to be one-way, it had better be the case that

$\operatorname{Prob}_{\langle \hspace{.02 in}x,y\rangle \hspace{.02 in}\leftarrow \hspace{.02 in}\left(\hspace{-0.03 in}\{\hspace{-0.02 in}0,1\hspace{-0.02 in}\}^{\hspace{.02 in}L}\hspace{-0.03 in}\right)^{\hspace{.05 in}2}}\hspace{-0.1 in}\left[g(x,\hspace{-0.04 in}y) = 0^{\hspace{.03 in}L}\hspace{-0.0 in}\right] \;\;\;$ is negligible.


What is a formula for the number of strings with no repeats? I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ in $s$.  For exapmle, let $A=\{a,b\}$.  Then $aaa$ is one of the strings I want to count, since for the substring $aa$, there are no disjoint copies.  However, $abab$ contains such a repeat.

If someone's already figured out a useful formula, please link.  Otherwise, I will refer back to this post in any article I write, if I use someone's answer.

Here is another example.  Let's try to construct a long string over $\{a,b\}$, that contains no repeats:

aaa (can't be a)
   aaab (a or b)
     aaabbb (can't be b)
       aaabbba (can't be b or a)
   aaaba (can't be a or b)

If we built a tree, we could count the number of nodes, but I want a formula.

Edit:
Well, it's not as daunting as I first thought if we convert this to a bin-choosing problem.  A set of strings of length k with at least one repeat is equal to the set that is the union of all permutations of the cartesian product:
$A \times A \times \cdots\times A \text{(k-4 times)} \times R \times R$ where $R$ is the required repeat.  I don't know if that's helpful, but it sounded pro :)  Anyway, let their be |A| bins, choose any two (even if the same one) to be the repeat, then choose $k-4$ more and multiply (the first 4 are already chosen, see?).  Now I just need to find that formula from discrete math.

This answers the question after the number of repeat-free words per size, implying that the desired quantity even exists.

Definition: Call $w \in \Sigma$ repeat-free if and only if it does not contain a factor $xyx$ with $x \in \Sigma^{\geq 2}$ and $y \in \Sigma^*$.

Claim: For given finite alphabet $\Sigma$ with $|\Sigma| = k$, there are no repeat-free words of length greater than $2k^2 + 1$.

Proof Idea: By pigeon-hole principle. Take a word $w$ of length $2k^2 + 2$ (or a longer word and consider its prefix of this length), i.e. $w = a_0a_0' \dots a_{k^2}a_{k^2}'$. Assume $w$ is repeat-free; that means that $a_ia_i' \neq a_ja_j'$ for all $i \neq j$ (otherwise we had a repeat). Therefore, there are $k^2 + 1$ many pairs of symbols; this contradicts $|\Sigma^2| = k^2$. So $w$ is not repeat-free. $\square$

Note that this is a rough proof: factors $a_i'a_{i+1}$ might create a repeat even sooner.

Notation:

$\Sigma^{\geq k} = \bigcup_{i=k}^\infty \Sigma^i = \Sigma^* \setminus \bigcup_{i=0}^{k-1} \Sigma^i$
"factor" = "subword" = "substring"


Comparing the closed behaviors corresponding to finite state automata Let $G$ be a finite state automaton (FSA) with transfer function $\delta(\cdot,\cdot)$ and initial state $q_0$. Suppose also $\Sigma_{G}$ represents its alphabet. Assume that its closed behavior is a set of strings defined as:

$L(G) := \{s \in \Sigma_{G}|\delta(q_0,s) \text{ is defined in }G\}$

Now, consider two particular FSA $G_1$ and $G_2$ such that $\Sigma_{G_{1}} \subseteq \Sigma_{G_{2}}$. Clearly, then we clearly have $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$. I'm wondering whether or not we necessarily conclude that $L(G_{1}) \subseteq L(G_{2})$.

To me, it's not always true. Am I right?

Here is a simple example to contradict it:

in which $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$, but $L(G_{1}) \supseteq L(G_{2})$.

Your claim implies that $L(G)$ depends only on the alphabet of $G$, but this is clearly false. So the claim itself must be false.


Find the minimal number of runs to visit every edge of a directed graph I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several runs; each run is a path from the start vertex to the terminating vertex. A run may visit a node more than once. The length of a traversal is the total number of vertices traversed by the runs, with multiplicity; in other words, the length of a traversal is the number of runs plus the sum of the lengths of the runs.

If there are edges that are not reachable (i.e. the origin of the edge is not reachable from the start vertex, or the terminating vertex is not reachable from the target of the edge), they are ignored.

To illustrate my needs, I give a simple graph and post the result, I would like to receive by the algorithm (start vertex $1$, terminating vertex $4$):

Graph edges:

$1 \to 2,3$
$2 \to 1,3,4$
$3 \to 4$

Result:

Run A: $1, 2, 1, 3, 4$
Run B: $1, 2, 4$
Run C: $1, 2, 3, 4$

Each edge (also each direction) has been covered. Each run begins with vertex $1$ and ends with vertex $4$. The minimum total number of visited vertices is searched. In the given example, the minimum number is $5+3+4=12$. There is no unreachable edge in this example.

This looks like a minimum-cost flow problem, but with demands instead of capacities.

A flow in a directed graph $G = (V,E)$ is a function $\phi: E\to \mathbb{R}_{\ge 0}$ that assigns a non-negative real value to every edge, such that for every vertex $v$ except $s$ and $t$, the total flow into $v$ is equal to the total flow out of $v$, or more formally,
$
    \sum_u \phi(u\mathord\to v) = \sum_w \phi(v\mathord\to w).
$
(This equality is usually called the conservation constraint.)

It's useful to think of a flow as a weighted sum of paths from $s$ to $t$.  In particular, suppose $P$ is a set of simple $(s,t)$-paths, and for any edge $e$, let $\#P(e)$ denote the number of paths in $P$ that use edge $e$.  Then the function $\#P$ is a flow.

In most traditional flow problems, each edge $e$ also has a capacity $c(e)$, and a flow is feasible if and only if $\phi(e) \le c(e)$ for every edge.  However, in your case, you want to force the flow to use every edge; so instead, you have a demand constraint $\phi(e) \ge 1$ at each edge.

Finally, we can define the cost of a flow $\phi$ to be the sum of the flow values: $\$(\phi) = \sum_{e\in E} \phi(e)$.  Possibly up to some off-by-one errors, your goal is to find a flow $\phi$ of minimum cost that satisfies all the conservation and demand constraints.

This problem can be solved in polynomial time using textbook flow algorithms.  Your specific problem is unlikely to appear in any textbook, but all the necessary components are described in Kleinberg and Tardos' Algorithm Design.  You may also find my lecture notes on flow algorithms (groundwork, basic algorithms, and extensions) helpful.


How do I find an upper bound on this recurrence $f(n)=f(n-\sqrt{n})$

I believe $f(n)\in O(\sqrt{n})$

However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks then does anything change?

For definiteness, let's assume that the recurrence is
$$
f(n) = \begin{cases}
f(\lfloor n-\sqrt{n} \rfloor) + 1 & n > 0 \\
0 & n = 0.
\end{cases}
$$
(We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor > n-\sqrt{n}-1$, we see that
$$
f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}).
$$
In the other direction, let us note that $f(n)$ is monotone and that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}.
$$
This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1.
$$
Iterating this $\log_2 n+1$ times, we get
$$
\begin{align*}
f(n) &\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &\leq
f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &\leq \cdots \\ &\leq
f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log_2 n + 1}} + \log_2n + 1 \\ &\leq
\sqrt{n} \sum_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &= O(\sqrt{n}).
\end{align*}
$$
We conclude that $f(n) = \Theta(\sqrt{n})$.


If the universe were predetermined, would non-deterministic automata still make sense? If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense?  Or would it not, but we wouldn't know it?

It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them.

For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form "as long as the set is not empty, take out an element and compare it with the current max value". This algorithm is non-deterministic because I did not explain how one chooses what element to pick. I did not explain it because it is not important for the correctness of the method (and because deciding in advance how to pick an element would blur the issues and limit the scope of my algorithm).

Note that, in all likelihood, all actual implementations of the algorithm will run deterministic code. But it is useful for me to think in term of the more abstract, more generic, non-deterministic algorithms. You may give it a different name but non-determinism is an essential concept.

Here is another way to see that non-determinism in mathematical models is not related to non-determinism in the actual world : your question is similar to me asking if the universe is governed by predeterminism, does the $P\not=NP$ question make sense?


Modifications to speed up the AKS primality proving It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one.

When I try the 9 digits long prime number it consume about 6 minutes to give you the result.

Are there any modifications to make it faster for large random primes in size above 200 digits?

The problems in the AKS are:

Euler phi function
Binomial congruence

There are a number of modifications, but none of the improvements I'm aware of will get it remotely close to the speed of ECPP or APR-CL.  For random 100-digit primes, the times for the fastest codes I'm aware of are:

246 days (estimated)  AKS v6 paper
45 hours (estimated)  AKS Bernstein + Voloch + Bornemann
2.6 hours  AKS Bernstein theorem 4.1
0.042 seconds  APR-CL (WraithX 1.1)
0.04 seconds  APR-CL (Pari/GP 2.7.0)
0.029 seconds  ECPP (ecpp-dj 1.03)
0.20 seconds ECPP (Primo 4.1.0 single thread)

At 500 digits, ECPP and APR-CL are in the 9-15 second range.  AKS would take years, albeit we could trivially parallelize or distribute it.

I haven't seen anything that gives better improvements than Bernstein's 2003 paper while not being a complete rework such as adding randomization.  The growth rate in practice comes out to $O(\log^{6.03} n)$ (there's almost certainly more than 0.03 variance in measurements, but the point is that it's very close to the ideal exponent of 6).  Ricky points out that Lenstra Jr. and Pomerance are still actively publishing theoretical improvements, tightening the proven exponent.

The time taken at more than very small input sizes is almost entirely in the congruence test.  There really should be very little time spent selecting the 'r' and 's' parameters, though it's possible to see it be non-trivial.  For the congruence tests, Bernstein has a paper describing some of the methods that can be used to speed this up, and the implementations shown above use binary segmentation in GMP, as he suggests.  You can see the implementation I used for timing at https://github.com/danaj/Math-Prime-Util-GMP/blob/master/aks.c, with various algorithms available.

There isn't any reason to use AKS in practice at any input size, given open source implementations of more efficient algorithms, not to mention Primo for use on large inputs.  ECPP gives certificates as well, which is a huge advantage.


Why companies that create native mobile apps are forced to make duplicate versions on other platforms? I am not computer savvy, so forgive me for asking why companies that create native mobile apps are forced to make duplicate versions on other platforms. "Duplicate" means the "same", so it means those companies don't have to modify the original version of the native mobile app for other platforms. I am guessing "other platforms" refer to other types of smartphones ... The question is based on the following statement. Please let me know if I have posted on the wrong forum. Thank you!

"However, this type of app is expensive to develop because it is tied to one type of operating system, forcing the company that creates the app to make duplicate versions that work on other platforms."

Duplicate here refers to the functionality only.

Imagine you were making a row boat out of oak, or out of pine... not quite the same thing.

Android and iOS platforms in particular encourage you to program in different languages, Java or Swift, which can be very different for highly complex apps.


Schedule each entree so that all entrees are completed in the shortest amount of time Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E_i$, takes $c_i$ time to cook and $d_i$ time to "dress up". The dressing up of entrees can occur while other entrees are being cooked and dressed up, but we can only cook one entree at a time. How would you go about creating an algorithm to schedule each entree $E_i$ in a manner that they all get finished in the shortest amount of time?

The link suggested by @D.W. above put into words exactly what I was looking for, an "exchange lemma" that proves the optimality of the greedy strategy. Here it is:

Suppose we cook in the order $1,2,\ldots, n$. Let $i \in \{1,2,\ldots,n-1\}$ be the smallest integer such that $d_i<d_{i+1}$. We claim that altering the order of the cooking of dishes $i$ and $i+1$, and changing nothing else, results in an equally good or better finishing time. Let us denote $ft(k)$ as the time when dish $k$ is finished under the original ordering (and all dishes are finished at time $\max\limits_{1\leq k\leq n} ft(k)$). We also denote by $ft'(k)$ the time when dish $k$ is finished under the altered ordering.

In general, we have
$$
ft(k) = \sum\limits_{j=1}^k c_j + d_k
$$ since we need to finish cooking dish $k$, which happens after $1,2,\ldots, k-1$, and then finally we dress it.

For the altered ordering we have
\begin{align*}
ft'(i+1) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} + d_{i+1}\\
ft'(i) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} +c_i + d_{i}
\end{align*}
(the funny ordering is just to emphasize the order in which the dishes are cooked).

The following three facts are easy to prove:

$ft(k)=ft'(k)$ for all $k \neq i, i+1$
$ft'(i)\leq ft(i+1)$
$ft'(i+1)\leq ft(i+1)$

These three together imply that $\max\{ft'(i),ft'(i+1) \} \leq \max\{ ft(i),ft(i+1)\}$ and hence $\max ft'(k) \leq \max ft(k)$ which proves the greedy strategy.


Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n Here is a question from Computational Complexity by Arora and Barak:

Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$.
(This is Exercise 6 in the chapter on circuit lower bounds.)

How do I approach this problem?

Let $AND:\{0,1\}^n\mapsto\{0,1\}$ be a polynomial in $GF(q), q\geq 2$.
Notice that the polynomial can't have a constant term (the constant term is zero), because
$AND(0,...,0) = 0$.
Meaning we can write the polynomial as:
$$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$
We now claim that every non-zero summand in $AND$ contains $x_i$.
Suppose that there are a set of summands not containing $x_i$. Choose the smallest (by amount of different parameters contained) of them. Notice that this  term is uniquely identified by a set $U \subset [1,n]\backslash\{i\}$. Now set $x_u = 1, u\in U$ and $x_v = 0, v\notin U$ and that there is no proper subsets of $U$ whose associated term is non-zero, because $|U|$ was chosen to be minimal.
$$AND(x_1,...,x_n) = a_U$$
This implies $a_U = 0$, because $i\notin U \land x_i = 0$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $x_i$. This applies to all $i\in[1,n]$, hence the degree of $AND$ is $n$.
We can denote $OR$ as $OR(x_1,...,x_n) = 1-AND(1-x_1,...,1-x_n)$ and likewise $AND(x_1,...,x_n) = 1-OR(1-x_1,...,1-x_n)$ by De Morgan's Law. Thus $AND$ and $OR$ must have the same degree.


How to collect all states of a behavior in TLA+? Description of the problem:

I am modeling checking a distributed protocol against a global property with TLA+ developed by Leslie Lamport. The global property is defined on all states of a behavior (more details can be found below). However, by the nature of exhaustive enumeration of model checking, the state transition graph explored consists of all states of all behaviors. How should I collect all states of each behavior against which the global property can be checked?

More on the global property:

Consider an implementation of a replicated list object. The property requires that for any two list states, e.g., $l_1$ and $l_2$, across the whole system, if they contain two common elements such as $a$ and $b$, then $a$ precedes $b$ in $l_1$ if and only if $a$ precedes $b$ in $l_2$.

My solution is to check this property against each behavior. This requires to collect all states of a behavior. Is this feasible? Are there better solutions?

Note: This is a re-post.

An answer from Stephan Merz at tlaplus-googlegroup:

In a linear-time framework such as TLA+, a system satisfies a property if the property holds of all system behaviors, and from your description it appears to me that this is what you want. TLC will compute all states that are reachable in your system and evaluate the property over all behaviors: there is nothing that you need to do explicitly.

The potential problem with this is that your system may have a lot of states, and TLC may not finish computing the entire state graph (or at least not in a reasonable amount of time). The TLA+ literature and resources give much advice for working around this problem, in short, you will want to choose small parameters and perhaps constrain the set of states considered by TLC using a state constraint (in the advanced options pane of the Toolbox interface).


Determining Number of States in a Turing Machine I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The example (Example 28.1, page 211) reads as follows:

  Here is a TM that accepts the non-context free set $\{a^nb^nc^n \mid
 n\geq 0\}$.

  Informally, the machine starts in its start state s,
  then scans to the right over the input string, checking that it is of
  the form $a^* b^* c^*$. It doesn't write anything on the way across
  (formally, it writes the same symbol it reads). When it sees the first
  blank symbol _, it overwrites it with a right endmarker ].

  Now it scans left, erasing the first c it sees, then the first b it sees,
  then the first a it sees, until it comes to the [. It then scans
  right, erasing one a, one b, and one c. It continues to sweep
  left and right over the input, erasing one occurrence of each letter
  in each pass.

  If on some pass it sees at least one occurrence of one
  of the letters and no occurrences of another, it rejects.
  Otherwise, it eventually erases all the letters and makes one pass
  between [ and ] seeing only blanks, at which point it accepts.

  Formally, this machine has $Q = \{s, q_1, ... , q_{10}, q_a, q_r\}, Σ
= \{a,b, c\}, Γ = \Sigma ∪ \{[, \_, ]\}$

Are they simply creating states based on their informal definition? Or is there some methodology they are implementing that determines the number of states? If there is some sort of methodology, is it a general methodology that can be applied to other Turing machines?

I am afraid you cannot tell the number of states from an informal description. There may be states needed to handle trivial details or limit cases that are not obvious from that description. So the answer is usually: as many states as needed to actually implement the behavior described informally.

Better precision may be required when analyzing some complexity issues, though even then it may be up to some constant.

For simpler problems, people may give a detailed description of the TM where you can count the states. This may also happen when you study techniques for combining 2 TMs in some way. Then you may want a formula that gives you (a bound for) the number of states of the combination from the number of states of the 2 initial TM (and possibly some other parameters of the twp TM)

But describing TM in details is like programming in machine language: very tedious and highly prone to errors and bugs of all kinds. And usually you do not have a testing environent.

If there is a methodology, it is probably in combining TM that can perform some specific tasks. It is like library functions in programming languages, which implement specific algorithms that you combine to solve a problem.

So the informal description may also, to some extent, be understood as a high-level language that does not yet have a compiler. So you do not really know what machine code you will get. But do not take this last sentence too seriously.


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

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

Sources of confusion:

..mainly wikipedia

http://en.wikipedia.org/wiki/Fiber_%28computer_science%29

  A disadvantage is that fibers cannot utilize multiprocessor machines without also using preemptive threads

http://en.wikipedia.org/wiki/Computer_multitasking#Multithreading

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

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

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

x = x + y
y = 2 * x

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

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

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

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

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


Greedy algorithm proof There are 2n product and their prices: P={p_1, p_2, ..., p_2n}.
When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

Sort P from high to low.
Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.

Let's assume that optimal answer is $A = \{(free_1, paid_1), ..., (free_n, paid_n)\}$ where $\forall i: free_i \le paid_i$, also sort this pairs by $paid$, i.e. $paid_1 \le paid_2 \le ... \le paid_n$.

I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.

If there is such $i$ that $paid_{i-1} > free_i$, take 2 pairs
$(free_{i-1}, paid_{i-1}), (free_i, paid_i)$ (in this case we need to pay $paid_{i-1} + paid_{i}$) and swap prices:

In case $free_{i-1} \le free_i$ we got $(free_{i-1}, free_i), (paid_{i-1}, paid_i)$ (need to pay $free_i + paid_i$);
In case $free_{i-1} > free_i$ we got $(free_{i}, free_{i-1}), (paid_{i-1}, paid_i)$ (need to pay $free_{i-1} + paid_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free_i < free_{i-1} = paid_{i-1} < paid_i$).

We have:

$paid_1 \le paid_2 \le ... \le paid_n$, that gives sorted sequence:
$\{paid_1, paid_2, ..., paid_n\}$
$\forall i: paid_{i-1} \le free_i \le paid_i$ (more intuition: in sequence from p.1 we insert $free_i$ on appropriate places), that gives sorted sequence: $\{free_1, paid_1, free_2, paid_2, ..., free_n, paid_n\}$

So we show that optimal answer can be expressed in form of sorted array.


SVM with different length features I need to train SVM with 2 different features..the problem is one feature is the HOG with length 144 and other an RGB value with length 3.. Can i combine these two features to train SVM  and test using the same? the code iam using is

X1=xlsread('train1.xlsx');
Y1=xlsread('CLASS1.xlsx');
svmStruct1=svmtrain(X1,Y1);
 classes=svmclassify(svmStruct1,test);

the test data contains both RGB and HOG values..

Yes, you can do it.  Concatenate the two feature vectors to get a single feature vector of length 147; the first 144 components are from the HOG, and the last 3 components are from the RGB.  Then apply the SVM on the feature vector of length 147.  SVM doesn't care where the individual numbers came from.

Code is off-topic on this site.


Does Dijkstra's Algorithm actually check nodes marked as visited? I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works.

So, most ways the algorithm has been explained to me involve going from a source vertex to another vertex so on and so forth. Will any edges going back to the source vertex or any already visited vertex actually get looked at, or does the algorithm ignore those because they already have their shortest path set up.

It depends on the implementation, but generally those edges are considered, but the algorithm immediately notices the target node is already visited or the new distance is greater than the old one, and doesn't process the edge further.


Lazy lists with call-by-value reduction strategy I am currently writing lists with lazy semantics in the pure
lambda-calculus with call-by-value reduction strategy.

I tried to construct pleasant to use and relatively efficient "lazy" functions on lists. As in the Church encoding I identify list with its right fold function, but with some differences. Here is nil and cons:

nil       = \_ _ z. z
cons x xs = \_ f z. f (\_. x) (\f' _. force xs f' z)

This representation of cons gives a simple way to get the tail of a list, which is O(1):

tail xs = \_ f z. force xs (\_ r. force (r f)) z

You just discard the first argument of f in cons and force the second after applying it to function f, which the tail function receives. But it brings some problems with foldr. Consider

cons (s z) (cons (s (s z)) nil)

After call-by-value and full beta-reduction (it reduces a term to a readable form) it becomes

\_ f z. f (\_ s z. s z) (\f' _. f' (\_ s z. s (s z)) (\'f' _. z))

To fold this term with one function, e.g. plus, you need to wrap and replicate it a little:

(\x r. plus (force x) (force (r
(\x r. plus (force x) (force (r _))))))

'_' means "there is no difference, what term to choose". Then you add a default value z and after call-by-value and full beta-reduction the whole term

force (cons (s z) (cons (s (s z)) nil))
    (\x r. plus (force x) (force (r
    (\x r. plus (force x) (force (r _)))))) z

reduces to

\s z. s (s (s z))

foldr is the generalization of this idea and defined as

foldr f z xs = force xs (fix (\rec x r. f x (r rec))) z

For example

sum = foldr (\x r. plus (force x) (force r) z

"Wrapping and replicating" is defined by fix, which is Z-combinator:

fix f = (\x. f (\y. x x y)) (\x. f (\y. x x y))

Having the head and tail functions it's easy to define take:

take = fix (\take n xs. if (eq0 n) nil (ifNullNil xs
    (\xs. consC (\_. head xs) (take (pred n) (tail xs)))))

ifNullNil returns nil, if the null function (an emptiness test) returns true for its first argument, or applies the second to the first and wraps the result into the thunk otherwise:

ifNull    = \xs z f. if (null xs) z (\_. force (f xs))
ifNullNil = \xs. ifNull xs nil

consC receives a thunk instead of a value and defined as

consC = \x xs _ f z. f x (\f' _. force xs f' z);

Finally you can define infinite lists:

nats = fix (\rec n _. force (cons n (rec (s n)))) z

And compose them with usual functions on lists:

sum (take (s (s (s z))) (cons (s (s (s z))) nats))

It reduces to

\s z. s (s (s (s z)))

and equals to Haskell's

sum $ take 3 $ 3:[0..] -- 3 + 0 + 1 + 0 = 4

Edit2

You need an extra '_' in the arguments of cons because it allows you to compose ordinary functions with functions, that generate infinite lists. Consider

nats = fix (\rec n _. force (cons n (rec (s n)))) z

It reduces to

nats = \_. force (cons z (fix (\rec n _. force (cons n (rec (s n)))) (s z)))

So list, which cons receives, should be "forceable". So list, which cons produces, should be "forceable" too, because you want to compose conses.

So my question is: are there some sources, from where I can learn more about such a representation or a better representations, that allow you to write programms with lazy semantics in languages with eager evaluation, especially in the pure lambda-calculus?

Have a look at Wadler et al's How to add laziness to a strict language without even being odd. It presents a number of techniques (for Standard ML) and provides a good survey of the literature of the time.

The most naive way is to delay the evaluation of term $t$ by making it, using a term such as $\text{delay }t=\lambda ().t$, and to force the evaluation of such a term by applying it, using a term such as $\text{force }t=t~()$.  For less naive/more systematic approaches, integrated into programming languages, read the paper.


In Breadth-first search and depth-first search what is the purpose of visited flag In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932

public void bfs()
    {
        // BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        printNode(this.rootNode);
        rootNode.visited = true;
        while(!queue.isEmpty()) {
            Node node = (Node)queue.remove();
            Node child=null;
            while((child=getUnvisitedChildNode(node))!=null) {
                child.visited=true;
                printNode(child);
                queue.add(child);
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

    public void dfs() {
        // DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!stack.isEmpty()) {
            Node node = (Node)s.peek();
            Node child = getUnvisitedChildNode(n);
            if(child != null) {
                child.visited = true;
                printNode(child);
                s.push(child);
            }
            else {
                s.pop();
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

what is the purpose of visited flag? as I can see it is not used especially if we will use Queue and\or Stack

The gist of code in Java you see is NOT complete in the sense that it fails compilation miserably. In that sense, you are looking at an example that is incorrect, not pedagogical and misleading to beginners.

With that having been said, let me explain. The visited flag is used to prevent the function to visit the same node again. It is used in the calls to method getUnvisitedChildNode(Node myNode), whose definition is missing from the gist. Supposedly, that method will return a child node of myNode that is not visited whenever there is at least one such node. Otherwise that method will return null.

I recommend you to read ntroduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA, where BFS and DFS are explained clearly. It also has the complete code that contains the partial source code in your question.


Proving that a specific language is a CFL, and that another language is not a CFL I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:

$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$

I want to show that $C_1$ is a CFL, while $C_2$ is not a CFL.  I'm trying to create a grammar / pushdown automata that accepts $L(C_1)$, but the $|x|=|z| \geq |y|$ part is throwing me off.  I plan on using the pumping lemma for $C_2$, but I'm not sure which string to pump.

First you have to realize that the extremes of the strings are of the form $0^n10^{2n-1}$ and $0^{2n-1}10^n$. You can get a language similar to that by the grammar $S \to 1 \mid 0S00 \mid 00S0$. From this some fine-tuning is needed. First to get $1$'s at the places where now only $0$'s are. Then to get the boundary conditions exactly right.

For the non-context-free other language I would also consider an "extreme" string, similar to $0^n10^n10^n$. That is not exactly one from the language, but close enough for a start.

(Nice exercise, that problem 2.48a in Sipser)


Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node For this I came up with a DFS recursion.

Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.

The element with the highest post number or the last element you visit should be the first element in your topological ordering.

Now do another DFS recursion that executes on every node called DFS_find:

DFS_find(Node):
    if (node has no neighbors):
        return 1;
    otherwise:
        return 1 + the maximum of DFS_find(Node) for all neighboring nodes

Execute DFS_find(Node) on the first node in your topological ordering. If it returns a number equal to the number of vertices, then a directed path that crosses every node once, exists. Otherwise it does not.

How can I prove whether or not this algorithm is correct?

I think this may be a little less time efficient than the classical way to just do a topological sort and then check if each consecutive pair has an edge between them.

Assume the graph is a directed acyclic graph throughout.
The algorithm is correct
In the first recursion, the algorithm finds a node $u$ that has no incoming edges.
In the second recursion, the algorithm checks whether $p(u)=n$, where for each node $v$, $p(v)$ is 1 plus the length of the longest path starting from that node.
There is a path that reaches all nodes if and only if $p(v)=n$ for some node $v$. Since the graph is acyclic, a path cannot revisit any node. Since the graph is acyclic, if $p(v)=n$ for some node $v$, that node must be the unique node that have no incoming edges. Hence, there is path that reaches all nodes without revisiting a node if and only if $p(v)=n$ for some node that has no incoming edges.
Combining the three paragraphs above, we see that the algorithm is correct.
Two easy exercises

Show that DFS_find(Node) returns $p(\text{Node})$.
Show that there is a path that reaches all nodes if and only if $p(v)=n$ for some node $v$.


Measuring Complexity of Boolean Satisfiability Problem How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. If the formula can contain duplicate sub-expressions, e.g., $(A \land B) \lor (A \land B)$, then the formula's maximum size is unbounded. In this case, wouldn't the complexity be better measured in terms of how complex the formula is, rather than how many variables it takes?

The boolean satisfiability problem (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\{v_1, v_2, ..., v_n\}$ so that each clause in $C$ contains at least one true literal. Since $V$ contains $n$ variables and each of these variables can only have $2$ different values (i.e., true or false), the total number of possibilities to be tested is $2^n$. We don't know how to solve SAT in polynomial time (since SAT is NP-complete); therefore, all solvers take exponential time in the worst case. Fortunately, however, there exist several ways to prune the search space.

  Wouldn't the complexity be better measured in terms of how complex the formula is?

The importance of the SAT problem lies in that every decision problem in NP can be reduced to SAT for CNF formulas. Other restricted versions of SAT exist (such as 3-SAT, Horn-SAT, and XOR-SAT); these restricted versions can be either in P or NP depending on the restriction (see Schaefer's dichotomy theorem). Regardless of this, note that problems in NP (such as SAT) are characterized by solutions (in the case of SAT, truth assignments) that can be verified in polynomial time.


nerode equivalence classes q - prefix? Lets consider the following language : $L = \{1w |w \in \Sigma^*\}$ (Alphabet is 0 and 1).

I know this language is regular, I just have to prove it now, the Problem here is the number of equivalence classes, I thought it would be:
$[1] = \{x|x $ starts with 1$\}$ and $[\epsilon] = \{x| x$ doesn't start 1$\}$.
But now I am dubious, isn't it possible for L to have 3 equivalence classes one containing words that start with 1 and one class that has epsilon as its only element?

Thanks in advance

There are three equivalence classes, and this can be seen from the minimal DFA, which has three states. The equivalence classes are $\epsilon,0\Sigma^*,1\Sigma^*$. Indeed:

$\epsilon$ and $0$ are in different classes since $\epsilon 1 \in L$ whereas $01 \notin L$.
$\epsilon$ and $1$ are in different classes since $\epsilon \epsilon \notin L$ and $1\epsilon \in L$.
$0$ and $1$ are in different classes since $0\epsilon \notin L$ whereas $1\epsilon \in L$.
All words in $\{\epsilon\}$ are clearly equivalent.
All words in $0\Sigma^*$ are equivalent since $wz \notin L$ for all words $w \in 0\Sigma^*$ and all words $z$.
All words in $1\Sigma^*$ are equivalent since $wz \in L$ for all words $w \in 1\Sigma^*$ and all words $z$.


Byte/word addressing I am confused on byte addressable/word addressable architecture.

I have studied MIPS implementation and I came to know that when the data is retrieved from main memory, it is shifted accordingly to convert it into a byte. But if this is the case, why do we need byte addressable? We can simply fetch a word shift it and operate on its 8 bits.

Or is it that the byte addressable architecture requires multiplexers to select a byte from a 32/64 word fetched from memory?

Please help me out.

In simple implementations, byte addressable is more important for writes than for read.
Because, with RAM, you read all 32 or 64 bits then steer data with a multiplexer. For writes, you need to be able to selectively update each part. (An alternative, in early DEC Alpha processors, was not to provide any byte wide access instructions, they eventually added these 8/16 bits accesses in later models)

In a less ideal world, several issues may need to be considered:

Some I/O ports may have side effects on reads, so that it is important to know whether each individual byte is read.
With EDC memory (error detection and correction), you cannot read or write only a byte, as error detection and correction is only efficient when handling at least 32 or 64 bits at once.


Algorithm of Communication with Failures I am interested in Distributed Algorithms especially in communication in network with failures.

I look for the proof of the following randomized algorithm of communication in network with failures. For me it seems like very general result in the communication, nevertheless I haven’t found the proof yet.

Algorithm: Initially only vertex $v_0$ has the message, at the end of the algorithm every vertex of the network should have the message.

On every round every vertex that has the message choice the neighbour randomly and sends it the message.

Assumptions: only $f$ failures might happen on the edges between the vertices.
$T = O(\log n)$ - time complexity and the entire network will know the message with high probability, when $f<n/3$, where n - number of vertices.

I will appreciate for link or reference to the paper.

The problem you state is very close to the problem of Byzantine Agreement with faulty links. Yet, it is not clear to me what is the guarantees you seek out of your algorithm.

The algorithm you give does not solve the Byzantine-agreement problem. Specifically, if the party that holds the message is corrupt, and it begins by sending $v_0$ to some player but also $v'$ to other player, then your algorithm will not converge (that is, maybe everyone will have $v_0$, but they will also have $v'$ and will not know what is the message that was originally sent). If you don't care about the parties having $v'$ as well, then why not just sending the message to all the parties (then repeated by each node)?

Note that when links fail, there is a question of connectivity. For instance, if one of the nodes is not connected to any other nodes (all the edges between are faulty), then that node will never get the message. Of course, if the number of faulty edges $f$ is less than $n/3$, and assuming each two nodes are connected, there is no problem at all.

The following paper might be at your help:
Vassos Hadzilacos, Connectivity requirements for Byzantine agreement under restricted types of failures, Distributed Computing, Volume 2, Issue 2, pp. 95-103, 1987. That paper deals with Byzantine agreement with $t$ faulty nodes and $k$ faulty links, and it holds for any architecture of the underlying graph (as long as some connectivity condition holds).

You might also want to take a look at the case where only nodes are faulty.
See for instance, K. Perry, Randomized Byzantine Agreement,
IEEE Trans. on Software Engineering, Vol SE-11, Issue 6, pp. 539-546, 1985.


Analysis of a recursive algorithm, where running time strongly depends on input I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where

$T(x, i, y) = \begin{cases}
1 & \textrm{if $(x=0)$ or $(y=0)$ or $(i > n)$} \\
    x+y+ T(x-a,\quad i+1, \qquad b)\\
    \ \qquad+ T(x-a,\quad i+1,\ y-b)\\
    \ \qquad+ T(\quad\ \ \ a,\quad i+1,\ y-b) & \textrm{otherwise}
\end{cases}$

where $a \in \{0, ..., x\}, b \in \{0, ..., y\}$, and $a,b$ can be different in each recursion step, dependent on the input.

(Note: $x$ and $y$ represent the sizes of two lists $|L_1|=x, |L_2|=y$, and in each recursion step, each list is split into two, i.e. into lists of size $a$ and $x-a$ (for $L_1$), and $b$ and $y-b$ respectively (for $L_2$).)

How can I analyze such a recurrence equation, i.e. determine $f$ s.t. $T(n, 2, n)\in O(f)$?
In particular, I do not know how to deal with $a, b$, especially since they are completely dependent on the input of the algorithm.

(I can solve the recurrence equation for special cases of $a,b$, e.g. $a=\frac{x}{2}, b=\frac{y}{2}$ for all recursion steps, or $a=x, b=0$ for all recursion steps etc., but not in general.)

In order to determine an upper bound on $T(x,i,y)$, consider instead the recurrence
$$ T'(x,i,y) = \begin{cases} 1 & \text{if $x = 0$ or $y = 0$ or $i > n$} \\ x + y + \max_{\substack{0 \leq a \leq x\\ 0 \leq b \leq y}} S'(x,i,y,a,b) & \text{otherwise,} \end{cases} $$
where $S'$ is given by
$$ S'(x,i,y,a,b) = T'(x-a,i+1,b) + T'(x-a,i+1,y-b) + T'(a,i+1,y-b). $$
If you have more constraints on $a,b$, you should adjust the bounds in the definition of $T'$ accordingly.


When to pump up and down? When I'm solving a question I usually spent too much time testing whether I should pump or down? Is there any formula to know when to use which?

Also, on proofing non context free grammar we use three pumping lemma, and one that's confused me is $|uvy| \le p$. I mean in the example given in the book I read, it is not even used. Can someone please tell on which situation this is will be useful?

Any help will be very appreciated.

To fix symbols, let us choose the decomposition $z = uvwxy$.

One of the examples where $|vwx|\le p$ comes in, is the language $L =\{ a^mb^na^mb^n\mid m,n\ge 1\}$.

Start with the "generic" string $a^pb^pa^pb^p$ where $p$ is the pumping constant. To have any chance of finding a pumping pair $v,x$ such that $uv^iwx^iy$ is within the language is by choosing $v$ in the first set of $a$'s and $x$ in the second set of $a$'s (or similarly for the $b$'s). Now the length of $vwx$ will be more than $p$ as it contains all $b$'s between the two sets of $a$'s.

Without that restriction $L$ can be pumped, and the pumping lemma is no longer suited for proving $L$ is not context-free.


Scheduling of process manufacturing with setup times Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

Problem Formulation

The problem consists of

Sequence of consecutive time intervals $t\in\{1,\dots,n_t\}$, each with start and end $(s_t,e_t)$ and length $l_t=e_t-s_t$. Consecutive means $e_{t}=s_{t+1}$ for all $t\in\{1,\dots,n_t-1\}$.
List of type of goods that are being produced: $j\in \{1,...,n_j\}$
Demand of each type of good per time interval $d_{j,t}$.
List of production lines $i\in{1,\dots,n_i}$
Availability of production lines per time interval $a_{i,t}$. $a_{i,t}$ is binary - whether available or not.
Manufacturing speed per production line per type goods $v_{i,j}$.
Setup time from one type of goods to another one $u_{j,j'}$.
Price for using a production line (leasing based), counted per minute $c_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

The setup time can be shorter or longer or equal to the length of the intervals
It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

Example

There are two production lines, i.e., $n_i = 2$ and there are two types of goods, i.e. $n_j=2$.

We have two intervals, i.e. $n_t=2$, each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

$d_{1,1}=1.1$
$d_{1,2}=1$
$d_{2,1}=1$
$d_{2,2}=0.5$

The of running the production lines are:

$c_{1} =c_{2} = 1$ USD/minute

All possible setup times are 30 minutes, i.e.:

$u_{j,j'}=0.5$ for all $j,j'$ where $j\neq j'$.

The speeds are:

$v_{1,1}=1.1$
$v_{1,2}=1.5$
$v_{2,1}=1$
$v_{2,2}=1$

Obviously, the demand is met if the first line is producing the first type of goods at both intervals and the second line is producing the second type. The cost is 204.55. See the solution here:

However, it might be tempting to switch them. Line 1 is much more efficient for the second type of goods (1.5). If there would be no setup time, we would have the cost 180 USD. However, this is not possible.

Question

What is the algorithm to schedule this manufacturing process optimally?

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,...).

Ideas fo far

If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).

We use the index $k$ for time such that $k \in [s_1, e_{n_t}]$

We introduce the following variables:

$\ell^{i,k}$ - line $i$ is leased at line $k$

$\alpha^{i,k}_{j,j'}$ - binary indicator for line $i$ is switching from $j$ to $j'$ at time $k$.

$p^{i,k}_j$ - binary indicator for line $i$ is producing good $j$ at time $k$.

$h^{i,j}_j$ - binary indicator that line $i$ is waiting to produce good $j$ at time $k$

$g^{i,k}_j$ - generated amount for line $i$ for good $j$ at time $k$ (either $v_{i,j}$ or $0$)

Then goal is to minimize $\sum_{i,k} c_i \ell^{i,k}$ subject to constraints:

Constraints for every $i,k$:

can only switch to 1 good at a time: $\textrm{at-most-1} \alpha^{i,k}_{j,j'}$
can only make 1 good at a time: $\textrm{at-most-1}  p^{i,k}_j$
can only hold for 1 good at a time: $\textrm{at-most-1}  h^{i,k}_j$
if producing, not switching: $\bigvee_j p^{i,k}_j \rightarrow \neg \bigwedge_{j,j'} \alpha^{i,k}_{j,j'}$
leasing iff producing or switching: $\ell^{i,k} \leftrightarrow \bigvee_{j,j'} \alpha^{i,k}_{j,j'} \vee \bigvee_j p^{i,k}_j$
not leasing implies holding for some good: $ \neg \ell^{i,k} \Rightarrow \bigvee_j h^{i,k}_j$

Constaints for every $i,k,j$:

Generating only if producing:
$$p^{i,k}_j \rightarrow g^{i,k}_j = v_{i,j}$$
$$\neg p^{i,k}_j \rightarrow g^{i,k}_j = 0$$
when stopping producing, it must immediately hold for same good or switch to another good (for $k < e_{n_t}$):
$p^{i,k}_j \wedge \neg p^{i,k+1}_j \Rightarrow h^{i,k+1}_j \vee \bigvee_{j'} \alpha^{i,k+1}_{j,j'}$
if producing or holding at $k+1$ must have been producing, holding, or switching at $k < e_{n_t}$:
$p^{i,k+1}_j \vee h^{i,k+1}_j \Rightarrow p^{i,k}_j \vee h^{i,k}_j \vee \bigvee_{j'} \alpha^{i,k}_{j',j}$

Constraints for every $i,k < e_{n_t},j,j'$:

when switching, it must switch long enough:
$(p^{i,k}_j \vee h^{i,k}_j) \wedge \alpha^{i,k+1}_{j,j'} \Rightarrow \bigwedge_{k'=k+2}^{\min(k+u_{j,j'}, e_{n,t})} \alpha^{i,k'}_{j,j'}$

Constraints for every $d_{j,t}$:

$\sum_{k=s_t}^{e_t} \sum_i g^{i,k}_j \geq d_{j,t}$


Maximum weighted disjoint set union I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this problem the Maximum Weighted Disjoint Set Union, which is obviously not the name by which the problem is known (if it is known).

In this post, the problem (stated slightly differently) is related to Weighted Independent Set. However, I will show below that this problem is simpler than independent set and, even if it possesses the same time complexity, it may allow for a solution with smaller run-time requirements.

The problem is as follows. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S=\{S_1,S_2,\ldots,S_n\}$, where $\forall_iS_i\subseteq U$. Furthermore, each set $S_i$ is assigned a weight $w_i$. The task is to find a set $S'\subseteq S$, such that the sets in $S'$ are disjoint and the sum of their weights is maximal.

One might think that this problem corresponds to weighted independent set. Namely, the vertices in the graph correspond to the sets in $S$ and there is an edge between two vertices if the corresponding sets have non-empty intersection.

Note, however, that important information is lost in the process of translation. For an example of such a loss, suppose $S_1=\{1,2\}$ with $w_1=1$, $S_2=\{3,4\}$ with $w_2=1$, $S_3=\{1,2,3\}$ with $w_3=3$. Note that we do not need to consider a cover $S'$ that contains both $S_1$ and $S_2$. This is because $S_3\subseteq S_1\cup S_2$ and $w_3>w_1+w_2$. The information needed to perform this cut-off is not present in the corresponding instance of the weighted independent set problem.

If I am correct in this reasoning, then this problem deserves attention and I am wondering whether it received any. In addition, I am hoping to get an off-the-shelf implementation in C++ which I can use (this problem happens to be a sub-problem of the research problem in a different field that I am trying to solve).

This is a weighted version of Set Packing, which was one of the 21 classic problems proven NP-hard by Richard Karp:

  Richard M. Karp (1972). "Reducibility Among Combinatorial Problems"
  (PDF). In
  R. E. Miller and J. W. Thatcher (editors). Complexity of Computer
  Computations. New York: Plenum. pp. 85–103.

As the unweighted version is already NP-hard, your weighted version is too, so it's unlikely that any algorithm will solve every instance of it in polynomial time.


Compression of non-adjacent structure using grammar I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string and use recursive substitution with non-terminal symbols to achieve compression.

What I'm wondering is whether there are classes of grammar and inference methods that are able to exploit sequential patterns that are based on non-adjacent co occurrence.

Take the following input sequence:

  XaXbXcYaYbYcZaZbZc

No two adjacent symbols co-occur more than once anywhere here, so the sequential compression techniques I mention will not compress this string any further, however there is a clear pattern to the sequence and it must be compressible. How is it possible to do so?

Grammar-based compression (context-free)  is alwasy looking for repetitions and is blind for other "patterns"..
In your example "XaXbXcYaYbYcZaZbZc" a position based compression should be more senseful.
For example the following "position rules" are generating your string..

  i=0,1,2:
  pos(X)=1+2i
  pos(Y)=pos(X)+6
  pos(Z)=pos(Y)+6
  pos(a)=2+6i
  pos(b)=pos(a)+2
  pos(c)=pos(b)+2

Rules like that can be stored efficiently and they are easy to decompress.
(In general the best compression is not computable since the so-called Kolmogorov-complexity is not computable. It is always a question of the type of compression..)


Difference between NFA and NBA NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages).
I think the example automata accepts finite word like $A,B,A,B$. But it also accepts infinite words like $A,B,A,B,...$.
How can i know if the example-automata accepts the finite language $(AB)^*$ or the infinite language $(AB)^{\omega}$(is the automata an NFA or NBA)?
Can it be differed and if yes how?

It's impossible to tell if all you have is the pictorial representation, since these look the same for both types of automata. Even if you're given a formal specification you won't necessarily be able to tell the difference (it depends on how these automata are encoded).

This kind of ambiguity is similar to linguistic ambiguity that can occur in real life. For example, suppose you see the word "impossible" written on the wall. Can you tell whether it's English or French?

Sometimes this kind of ambiguity is purposeful. For example, the pictorial representation of a DFA doubles as the pictorial representation of an equivalent NFA. The only difference in your case is that the two interpretations are inequivalent.


Problems in P with provably faster randomized algorithms Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$? Here $\mathsf{PTIME}(f(n))$ means the set of languages decidable by a randomized TM with constant-bounded (one or two-sided) error in $f(n)$ steps.

  Does randomness buy us anything inside $\mathsf{P}$?

To be clear, I am looking for something where the difference is asymptotic (preferably polynomial, but I would settle for polylogarithmic), not just a constant.

I am looking for algorithms asymptotically better in the worst case. Algorithms with better expected complexity are not what I am looking for. I mean randomized algorithms as in RP or BPP not ZPP.

Polynomial identity testing admits a randomised polynomial time algorithm (see the
Schwartz-Zippel lemma), and we currently don't have a deterministic
polynomial time or even a sub-exponential time algorithm for it.

Game tree evaluation Consider a complete binary tree with $n$ leaf nodes each
storing a 0/1 value. The internal nodes contain OR/AND gates in alternate levels.
It can be proved using adversary argument that every deterministic algorithm
would have to examine $\Omega{(n)}$ leaf nodes in the worst case. However there is
a simple randomised algorithm which takes has expected running time of $O(n^{0.793})$
Look at slides 14-27 of the talk.

Oblivious routing on a hypercube Consider a cube in $n$-dimensions containing
$N=2^n$ vertices. Each vertex has a packet of data and a destination that it
wants to eventually deliver the packet to. The destination of all the packets
are different. Even for this, It has been proved that any deterministic routing strategy would take $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ steps. However, there is a simple
randomised strategy which will finish in expected $O(n)$ steps with high probability.

Note that in randomised algorithms, the expected cost $E(F(n))$ with high probability (like for eg. $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$) is
equivalent to worst case in practice.


Algorithm to match numbers with minimum number of moves This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.

Given a series of numbers, e.g.

[3, 1, 1, 1]

How would one most efficiently turn all of the numbers into the same number, with the minimum number of "moves"? By "move" is meant adding or removing one from a number.

In the above example, the most efficient moves would be:

[1, 1, 1, 1]

This would require 2 moves, reducing the first number twice.

I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.

I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.

I suppose I could figure:

The average,
The mode,
The median

and get the edit distance of each of them, choosing the minimum distance. However, I am not sure that this would be correct in every single instance. How can I know?

The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).

This is the algorithm which solves the problem (originally written by dc2):

function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2