Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0} how would you  prove if this language is regular/irregular?

question given:

Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, give a formal proof(based on the Pumping Lemma).

i) {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0 are three integers};

I have constructed a DFA which I believe proves the language is regular however, using the pumping lemma i.e. where the pumping length (p) = 4:
aaaabbbbcccc, and say this is split into xyz where x = aa, y = aa and z = bbbbcccc
then x(y^i)z where i = 2 -> aaaaaabbbbcccc

satisfy the conditions of the pumping lemma:

for each i >= 0, x(y^i)z ∈ A
|y| > 0
|xy| <= p

so:

when i = 2, x = aa, y = aa, z = bbbbcccc then A = aa aaaa bbbbcccc is satisfied
|y| = aa so |y| = 2 which satisfies the condition
x = aa + y = aa so |xy| = 4 which satisfies the condition

meaning the language is regular BUT if:

x = aaa, y = ab, z = bbbcccc

when i = 2, x = aaa, y = ab, z = bbbccc then A = aaa abab bbbccc which doesn't satisfy the condition as they're not in order (a then b then c) anymore.
|y| = ab so |y| = 2 which satisfies the condition.
x = aaa + y = ab so |xy| = 5 which doesn't satisfy the condition.

I could be using the Pumping Lemma completely wrong I'm confused as initially (and from my DFA) I assumed this language is regular as the number of a's doesn't depend on the number of b's and the number of c's doesn't depend on the number of b's or a's etc.

basically: I think I have proven that the language is regular with a DFA but irregular with the pumping lemma and don't know how to give a definitive answer.

You're using the lemma completely wrong. It states that

If language $L$ is regular, then there is $p$ such that for every string $s$ in $L$ where $|s|>p$ there is a decomposition $xyz$ with $|y|>0$ and $|xy|\le p$ for which $xy^i z \in L$ for all $i \ge 0$.

When you want to use it to prove language not to be regualr, you use contrapositive implication (making $\neg B \implies \neg A$ from $A \implies B$ ).

You get if for every $p$ there is a string $s$ with $|s| > p$ where for every decomposition $xyz$ with $|y|>0$ and $|xy| \le p$ there is a $i \ge 0$ such that $xy^i z \notin L$ then $L$ is not regular.

Now for your actual question, what you seemed to be doing is trying to prove the first implication, which would tell you nothing. It's important to note that the lemma is implication not equivalence, thus proving that a language has the pumping property does not mean it is regular. Conversely you cannot prove such languages to not be regular by pumping lemma.

If you wanted to prove that the language is not regular, you would need to make a string $s$ longer than $p$ for every $p$ from the language $L$ (for example by taking string $a^p b$ or $a^{p+1}$ or similar strings) and then you would have to make sure that there is an $i$ for all of the decompositions $xyz$ such that $xy^i z \notin L$. You can find many examples both on this site and on the Internet, but it is impossible here because the language is in fact regular.

To take your example more closely, if you wanted to prove the language to not be regular with the pumping lemma, your first mistake was chosing $p$, because you need to prove the statement for every $p$.


State Transition Diagrams for XOR I have found two different versions for State Transition Diagrams for XOR.

I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please?

Are they both functionally equivalent? Are there situations where one is more appropriate than the other?

On the left you have a DFA that accepts the language of all strings over $\{0,1\}$ in which the XOR equals 1.

On the right you have a Mealy machine in which each output is the XOR of the two recent inputs (the first output is always zero).


Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2 I stumbled upon the following problem during my research.

I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting graph is 2.

Is this problem NP-hard? I was trying to come up with a polynomial time algorithm (and failed) and also tried to prove its NP-hardness, but also having a hard time.

Figured out this is indeed NP-hard. This is equivalent to finding the maximum spanning star forest in a bipartite graph, which in turn is as hard as finding the minimum dominating set in a bipartite graph, which is NP-hard.


Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven" I was reading CLRS and is said:

  If factoring large integers is easy, then breaking the RSA
  cryptosystem is easy.

Which makes sense to me because with the knowledge of $p$ and $q$, it is easy to create the secret key which the knowledge of the public key. Though, it explains the converse statement, which I don't quite understand:

  The converse statement, that if factoring large integers is hard, then
  breaking RSA is hard, is unproven.

What does the statement above formally mean? If we assume factoring is hard (in some formal way), why does that not imply that breaking the RSA crypto system is hard?

Now consider that if we assumed that factoring is hard...and that we discovered that it meant that the RSA cryptosystem is hard to break. What would that formally mean?

The easiest way to think about it is to think of the contrapositive.

The statement:

  if factoring large integers is hard, then breaking RSA is hard

is equivalent to the following:

  if breaking RSA is easy, then factoring large integers is easy

This statement has not been proven.

What they're saying is, assume we have an algorithm that solves factoring in polynomial time. Then we can use it to construct an algorithm that solves RSA in polynomial time.

But, there could be some other way to crack RSA that doesn't involve factoring integers. It's possible that we will find we can crack RSA in a way that doesn't let us factor integers in polynomial time.

In short, we know that RSA is at least as easy as factoring. There are two possible outcomes: RSA and factoring are of equivalent difficulty, or RSA is a strictly easier problem than factoring. We don't know which is the case.


Compare regex in programming languages with regular expression from automata/formal language? I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages.

These two differ not just in "syntax" (the union + in regular expressions means | in regex, and there's no such meta-character as . in regular expressions, etc.), but also in "semantics", e.g. the regular expression (a+b)*c describes the regular language, L={a,b}*{c}, which the string abcd is not a member of, but the equivalent regex (a|b)*c would actually find a "match" in the string abcd (unless I do (a|b)*c$). Not to mention that "regex" can describe some non-regular languages as well.

Is there a good resource/summary that compares regular expression with "regex"?

In programming, "regular expressions" are used for searching (if a match happens in the string), not for simple accepting. I.e., it is as if what is written is .*your-re-here.*.

It is often of interest to know not only if it matched, but exactly where. And so the above isn't all the story, most RE machines also look for the longest match. For simplicity, many RE libraries don't handle alternation (e.g. ed(1) in Unix of yore didn't), as characters, character classes, star applied to the last character, and anchors (beginning/end of line) were enough to handle 90% or more of the "text editing" requirements. And that can be written in simple, short code.

Furthermore, depending on the exact machinery used, it is more or less easy to extend the "regular expressions" with non-regular constructs, like "match what matched between parenteses before", like ([a-z]*) \1 to mean "the same word twice, separated by a space". Such constructs are handled e.g. in vi(1), as tasks like the mentioned are useful to catch typos (a common error is to to write the same word twice).


How broad is the meaning of "algorithm"? This is a purely terminological question.

The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative statements giving roughly the same idea.

But for some computer systems, such as neural networks, it is somewhat stretching it (for me) to say that they are "algorithms".  e.g. neural networks are very "approximate" compared to traditional software algorithms.

Would people in general say that a particular neural network with a particular parameterization (i.e. not the learning algorithm, but the resulting neural net itself) is an "algorithm")?
If not, what other word is there to refer to the more general class that contains such networks as well?

No.  A specific neural network is just the (weights) parameters of an algorithm for function approximation.

A neural network in general yes, is the algorithm for classifying a given x into a class, given a probabilistic distribution (weights).

This is like asking weather a specific VAT rate is an algorithm.  The calculation of VAT is an algorithm but the VAT rate is not.


Process scheduling confusion I've got a confusion in the following section of a book. Here we taking about FCFS Scheduling. I feel that calculation table is incorrect in the book. Because P3 got completed at time 7, it's turnaround time should be 7-3 because third process arrival time is 3 so why they take 1? Remember turn around time = t(process completed)-t(process submitted)

For P4 it's 11-4 which I feel wrong again. Further for P5. So I want to know whether I'm wrong in understanding this all or the following is really a wrong calculation. Can someone please explain. Thanks!
Check the fallowing links for book scan:
http://i.stack.imgur.com/oGtva.jpg
http://i.stack.imgur.com/mVP03.jpg

Converting Vor's comment into an answer:

the table looks incorrect.

Specifically: for P3, P4, P5 the table wrongly reports (completion time - processing time) instead of (completion time - arrival time).


Would Schmidhuber's theories of everything be capable of performing hypercomputation? Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of computable physical laws. His work was based on Zuse's thesis.

This hypothesis would be inside the domain of Digital Physics, a group of hypothetical models that propose that the universe is analogous to a computer or an automata.

(https://en.wikipedia.org/wiki/Digital_physics)

In 2000, he expanded this work by combining Ray Solomonoff's theory of inductive inference with the assumption that quickly computable universes are more likely than others. This work on digital physics also led to limit-computable generalizations of algorithmic information or Kolmogorov complexity and the concept of Super Omegas, which are limit-computable numbers that are even more random (in a certain sense) than Gregory Chaitin's number of wisdom Omega.

So since Chaitin's constant (https://en.wikipedia.org/wiki/Chaitin%27s_constant) would allow hypercomputation if it existed in the pysics of the universe, would then Schmidhuber's hypothesis be able to perform hypercomputation?
Also, in the hytpercomputation wikipedia entry (https://en.wikipedia.org/wiki/Hypercomputation) it says (In "eventually correct" systems):

  A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other computable real, but still excludes all noncomputable reals. Traditional Turing machines cannot edit their previous outputs; generalized Turing machines, as defined by Jürgen Schmidhuber, can. He defines the constructively describable symbol sequences as those that have a finite, non-halting program running on a generalized Turing machine, such that any output symbol eventually converges; that is, it does not change any more after some finite initial time interval. Due to limitations first exhibited by Kurt Gödel (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. Schmidhuber uses this approach to define the set of formally describable or constructively computable universes or constructive theories of everything. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a Specker sequence.

And also, Super-recursive algorithms are closely related to hypercomputation, and super recursive algorithm is just one way of defining hypercomputation. In super-recursive algorithms wikipedia entry (https://en.wikipedia.org/wiki/Super-recursive_algorithm), Schmidhuber's model is included as a super-recursive algorithm-based model

So, knowing all of this, then, would Schmidhuber's hypothetical universes be based on hypercomputation?

If the hypothesis is that we live in a universe whose physics are computed by a Turing machine, then hypercomputation is trivially impossible in our universe.

The constants you're taking about are limits of computable numbers.  If all you have is a computer you can't produce such a number in finite time.

It sounds like you're taking two different things named after the same mathematician and assuming they're somehow connected when they're not.

(Disclaimer: I'm going off the information in the question alone.)


MGU and Variable Standardization - CNF I have been reading on converting first order logic sentences to conjunctive normal form, and then performing resolution.

One of the steps of converting to CNF, is to Standardize variables: rename all variables so that each quantifier has its own unique variable name.

Most general Unifier is the least specialized unification of two clauses.

Question 1: I have been searching to find an example that shows what are the potential problems if I don't standardize variables, but all the online resources I found only explain the "How" and not the "Why". Could you provide me with an example of a potential problem?

Question 2: The same problem as the first question. What if we don't use MGU, and use a more specialized unifier? What are the potential problems? Could you provide me with an example?

My sincere thanks.
Felipe

See this answer - it's an example of a contradictory set of clauses where we cannot derive a contradiction without renaming variables. Note that it's not sufficient to only rename variables after the conversion to CNF, we have to rename variables to be distinct before every application of the resolution rule. You can view it as follows: A variable appearing in two distinct clauses has different meaning in each of them as they're implicitly universally quantified. If we don't rename the variable in one of the clauses, we make a false assumption that the variable means the same in both clauses.
By using MGU, we derive the most general clause in a resolution step. If we use any unifier that is more specialized than their MGU, the resulting clause is weaker. This means, that we didn't infer all the knowledge we could, and we can miss a derivation of an empty clause even if it exists. For example:
\begin{array}{c}
P(x,y) \lor Q(y) \\
\lnot Q(d) \\
\lnot P(c,d)
\end{array}
If we make a resolvent from the first two clauses using MGU which sends $y\to d$, we get $P(x,d)$ and we can proceed with the third clause. If we take a weaker unifier, like one that also sends $x\to d$, we get $P(d,d)$ and we're not able to make a resolvent with the third clause. This means the method is no longer complete.


context-free grammar for comma-separated list with comments I'm trying to write a context-free grammar for a comma-separated list of statements with comments.  It is trivial if the comma appears at the end of a statement.  It is trivial if the comment is ignored.  But I don't know how to include a comma in the middle of a statement (before the comment).

This Python / Lark CFG:

start: def+

def: "{" statement ("," statement)* "}"

!statement: NAME "=" (
    | "Foo"
    | "Bar" "(" NAME ")"
    | "Tomato"
    | )

NAME: /[A-Z][a-z-]{0,15}/

COMMENT: "//" /.*/

%import common.WS
%ignore WS

parses this text:

{
    Mike = Foo,
    Fred = Bar(Chocolate),
    Joe = Tomato
}

producing this AST:

start
  def
    statement
      Mike
      =
      Foo
    statement
      Fred
      =
      Bar
      (
      Chocolate
      )
    statement
      Joe
      =
      Tomato

I want to parse the content of comments into the AST, not just ignore it:

{
    Mike = Foo,
    Fred = Bar(Chocolate),      // Yummy!
    Joe = Tomato
}

======= EDIT =========

The problem from which the question was distilled requires an optional description tied to each assignment.  Arbitrary comments (such as on the lines with braces) aren't needed.  So Yuval's answer (with the addition of a trailing comment) works like a charm.  For completeness, the working grammar is:

start: def+
def: "{" statement ("," COMMENT? statement)* COMMENT? "}"

statement: NAME "=" (foo | bar | tomato)
foo:    "Foo"
bar:    "Bar" "(" NAME ")"
tomato: "Tomato"

and produces the AST:

start
  def
    statement
      Mike
      foo
    // Stuff
    statement
      Fred
      bar   Chocolate
    // Yummy!
    statement
      Joe
      tomato
    // aaaargh

Define a non-terminal COMMENT which generates comments (in your case, // followed by arbitrary non-newline characters and then newline), as well as the empty string. In the definition of def, add COMMENT after ,.


Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$? Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O.

My idea is that since $B$ is usually much smaller than $M$ we can have

$O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{N}{M}\right) = O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{NB}{MB}\right)$

so $\frac{B}{M} <1$

but I'm new to complexity theory so I'm not sure if it's the correct reasoning.

Your construction will work just fine:
$$\begin{align}
\log_{M/B}\frac{N}{M}&=\log_{M/B}\frac{NB}{BM}=\log_{M/B}\frac{N}{B}\cdot\frac{B}{M}\\
 &= \log_{M/B}\frac{N}{B}+\log_{M/B}\frac{B}{M}\\
 &= \log_{M/B}\frac{N}{B}-1
\end{align}$$
Since the two terms differ by 1, they're asymptotically equal.


How to do amortized analysis for an expanding array? If you have an array that expands when it is completely filled and the new size is
N = N + 1 + ceiling(log2(N)) (N is the current size, and then N becomes the new size)
(log2 is log base 2).

How can you do an amortized analysis for this? It is confusing because the size of the expansion of the array increases as N increases.

This looks like a homework problem, so I will try to highlight the skeleton of the proof.

The cost of inserting and taking an element out of an array is 1
The cost of resizing an array is equal to the number of elements moved to the new/bigger array.
As a simple case, consider you increase the size of array by 1. Calculate the total cost of resizing?

Repeat the above analysis by doubling the size of array and check which one is better i.e. doubling the size OR increasing by 1? Calculate the amortized cost for both cases? Then you should be good to answer your own question...


Reducing Independent Set to a problem to prove that it is NP complete Given:

A set of available customers $c_1, c_2, \dots, c_n$.
A set of available foods $f_1, f_2, \dots, f_m$.
Each customer will choose a subset of the available food.

Problem:

Find the maximum number of customers that can be chosen, such that no two customers share the same food.

Question:

How to reduce the independent set problem to this problem, in order to prove that this is an NP-Complete problem ?

Hint: try to reduce each vertex to a customer and each edge to an available food.


Flow graph that requires pushing back flow in Ford Fulkerson Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?

Let's assume we use the standard procedure of repeating this step:

Find an augmenting path $p$ in residual graph $G_R$ of $G$.
Let $c$ be the minimum capacity edge in $p$.
Increase the flow on every edge in $p$ by $c$.
Update $G_R$.

The key here is step 1, where select augmenting paths. For many graphs, if we had an oracle to tell us which augmenting paths to use, we would never need to push flow back. I'm am curious if there is a case for which, regardless of augmenting paths and their orders, we will always be required to "push flow back". To clarify what I mean:

  To push flow back in $G$, means to increase the flow on an edge $(u,v)$ in $G_R$ such that edge $(v,u)$ exists in $G$.

If this is not possible, I would also be interested in a proof that such ordering of augmenting paths always exists? If it is possible, does it generalize to any number of nodes $n$? This question is alluded at in the ending sentences of this answer, but provides no proof.

My initial thoughts were that this would be a trivial proof. However, there are many times when the optimal flow along an augmenting path may not be equivalent to its minimum capacity edge. Since (by step 3) we require paths to be filled to their minimum capacity, we cannot easily meet this. My next thought would be that there should exist at least one augmenting path such that its max flow is equivalent to its minimum capacity edge. This is obvious by the Max flow min cut Theorem, but I am not sure how this would apply to the proof. With this, we may be able to get an inductive proof that it is always possible, but I am really unsure of this strategy as well. Any help would be appreciated.

I think it is possible to reason backwards from an optimal solution$^1$ to the order in which the paths have to be augmented to not have any pushing-back:

In the solution, for any path from the source to the sink, where the flow is larger than zero, there is at least one edge, that constrains that flow, i.e: its flow is at capacity.
If it were not, there would have been an augmenting path along that path, i.e. the solution would not be optimal.
Also, of the edges that are at capacity, there has to be one (or multiple) with the lowest possible capacity. Furthermore, this edge has to be part of some path between source and sink where each edge has a flow at least as high.
We take such a path, call it $P_1$ and remove its 'flow capacity' from the initial graph (i.e. reduce the capacity of the edges along the path).
We repeat this with the remaining graph (resulting in $P_2, P_3, \ldots, P_n$) until there is no path between source and sink remaining, where all edges have a non-zero capacity.

Then, $P_1, P_2, \ldots, P_n$ is the order in which the paths have to be chosen s.t. there is never any pushing back necessary.

$1$: This only holds for optimal solutions that have been found with the FF algorithm. E.g. in a graph where 5 edges with capacity 2 go into node X and only one edge leaves it with capacity 5, there would be a max flow where each of the 5 edges has a flow of 1/2 and the outgoing has a flow of 5/5. Then the 5/5 edge would be the lowest edge at capacity but there is no path from source to sink in that graph where each edge has a flow of 5 or more. This is no problem for the algorithm outlined above because such a max-flow solution would not be found with FF.


How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, "how big is each page"? etc No more information required. I would just like to know how to use the information provided.

4 bits page number + 8 bits offset = 12 address bits : A[11:0]

A[7:0] selects an offset within a page
A[11:8] selects the page
1792 = 7*256 : A=0111_00000000
2304 = 9*256 : A=1001_00000000
2814 =11*256 : A=1011_00000000
1024 = 4*256 : A=0100_00000000

What is the problem? You get 8 address bits within each page. So what is the page size?


Time complexity for this simple loop This is the code:

j=2
while j<(n*n)
     j=j*j

At first my approach was to treat this like this loop

i=1
while (i<n)
    i=i*2

Which generates on $i$ various powers of $2$  ($i=2^0, 2^1, 2^2....2^k$).

At a certain $k$ iteration, $i$ is equal to or exceeds $n$.
So $2^k=n$ is the time when the while stops.

We find $k=log_2(n)$ which is the number of times the entire while loop has been executed, so $T(n)=\theta(log_2n)$.

So my idea for the first algorithm was this:
j=j*j generates on $j$ different powers of himself, so you can describe it as $j^2$. The problem is that I can't shove in a $k$ iterations in the counting.

The solution for this is actually $log(log(n))$.

Why is this? Can I improve my logic?

You're on the right track.  For the simpler code, you correctly wrote down the sequence of values that are produced: $2^0,2^1,2^2,\dots$.  In particular, the $t$th output is $2^t$.  Then you were able to find where the loop stops by setting $2^t=n$ and solving for $t$.  That's a great approach.

Try doing the same thing for your actual example.  Hint: the first two outputs are $j$ and $j^2$.  What's next?  Can you generalize What is the $t$th output?  Can you write an equation that represents where the loop stops and solve for $t$?


Turing machines and their computational power Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the machine which could solve the problems that T.M cannot?Are quantum computers also the T.M or are they more powerful than T.M?

Your question is closely related to the Church–Turing thesis, which says that Turing machines can compute anything that can reasonably be described as an algorithm (i.e., a sequence of discrete steps). Variants, such as the physical Church–Turing thesis state that Turing machines can compute anything that can be computed by any physical mechanism. Note that these are described as "theses", rather than theorems. They're not formal claims about mathematics so they're not possible to prove.

We don't know how to build any physical device that could compute a non-Turing-computable function. This includes quantum computers, which can be simulated (though inefficiently) to arbitrary accuracy by non-quantum devices such as Turing machines.

We can certainly consider more powerful devices, though, even though we don't know of any way to build them. A typical construction is to take something that Turing machines can't do, and then imagine that we have a subroutine that instantly solves that problem. These are known as oracle machines, and they are provably more powerful than Turing machines. Indeed, one can define a whole infinite hierarchy of successively more powerful machines using this idea, with the caveat that we have no clue how to physically build such a thing.


What is the Big-Ω of the following function? For the following function:

$$
\sum_{n=1}^{2n}x+x^2
$$

It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt:

$$
\sum_{n=1}^{2n}x+x^2
$$
$$
\geq \sum_{n=1}^{2n}x^2
$$

But not sure how to continue. Also, does tightest Big-Ω always equal tightest Big-Oh?

EDIT: The way I worked out the Big-Oh is shown below:

$$
\sum_{n=1}^{2n}x+x^2
$$
$$
\leq \sum_{n=1}^{2n}x^2+x^2
$$
$$
= \sum_{n=1}^{2n}2x^2
$$
$$
\leq 2n ( 2(2n)^2)
$$
$$
= 8n^3
$$

Therefore the Big-Oh is $O(n^3)$.

$$\begin{align}
\sum_{x=1}^{2n}(x+x^2) \gt \sum_{x=1}^{2n}x^2 \gt \sum_{x=n+1}^{2n}x^2\gt\sum_{x=n+1}^{2n}n^2= n^3
\end{align}
$$

So the function is $\Omega(n^3)$. You have shown it is $O(n^3)$. So the function is $\Theta(n^3)$.

Although $n^3$, the asymptotic lower bound ignoring a constant factor is the same as the asymptotic upper bound ignoring a constant factor in the current case, it is not always true because some functions fluctuate. For example,
$$f(n)=\begin{cases}1 \quad \text {when }n\text{ is odd,}\\ n \quad \text{when }n\text{ is even.}\end{cases}$$ $f(n)=O(n)$ and $f(n)=\Omega(1)$. Both bounds are tightest.

Exercise. Show that $$\sum_{x=1}^{m}(x+x^2)=\frac{m(m+1)(m+2)}{3}$$


Quasigroups, congruences and recognizable subsets My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:

Let $M,N$ be monoids and $\varphi: M \rightarrow N $ a monoid morphism. We say that a subset $L$ of $M$ is recognizable by $\varphi$ if there is a subset $P$ of $N$ such that $L = \varphi^{-1}(P)$. As is known, the rational languages are precisely the recognizable subsets of $\Sigma^\ast$.

Furthermore, we define an equivalence relation $R_\varphi$ by $u R_\varphi v :\Leftrightarrow \varphi(u)=\varphi(v)$.
This relation is a congruence relation, that is $\forall s,t,u,v \in M:s R_\varphi t \Rightarrow usv~R_\varphi~utv$.

We say that a congruence relation $R$ saturates $L$ if for all $u \in L$, $uRv$ implies $v \in L$.
Then in the above document, the following proposition (IV.2.2, page 90) is stated:

Let $\varphi : M \rightarrow N$ be a monoid morphism and let
$L$ be a subset of $M$. The following conditions are equivalent:

(1) $L$ is recognised by $\varphi$

(2) $L$ is saturated by $R_\varphi$

(3) $\varphi^{-1}(\varphi(L))=L$

Proof. (1) implies (2). If $L$ is recognised by $\varphi$, then $L=\varphi^{-1}(P)$ for some subset $P$ of $N$. Thus if $x \in L$ and $x R_\varphi y$, one has $\varphi(x) \in P$ and since $\varphi(x)=\varphi(y), y \in \varphi^{-1}(P)=L$.

(2) implies (3). If $x \in \varphi^{-1}(\varphi(L))$, there is $y \in L$ such that $\varphi(x) = \varphi(y)$, that is $x R_\varphi y$. Thus, $x \in L$, and $\varphi^{-1}(\varphi(L)) \subseteq L$ follows. "$\supseteq$" is trivial.

(3) implies (1). Let $P:=\varphi(L)$, then $\varphi^{-1}(P)=L$.

I want to weaken the assumptions made in the proposition. Namely, assume tgat the  $N$ in the above definitions is a proper groupoid (in fact, I need to deal with loops), that is, associativity and identity are lost. Further, $\varphi$ need not be a morphism (the relation $R_\varphi$, defined in the same way as above, a priori need not be a congruence anymore) and we restate (1) accordingly (as formally, the notion of a "recognable subset" is not defined for groupoids).
Then my questions are

  (1) Is $R_\varphi$ still a congruence if we demand $\varphi$
  to be a morphism of groupoids (loops)?

  (2) Does the proposition still hold? Does it if we assume that $R_\varphi$ is  not a congruence?

  (3) What other sources (preferably monographs) are there that you recommend as comprehensive introductions to algebraic automata theory, esp. concerned with the role of monoids, semigroups (and maybe more general structures as groupoids) and their connection with automata and languages?

Personally, I think they are both true, as for (2), neither the morphism properties, nor associativity nor congruences seem to be used in the proof. And for (1), I don't see where one would need associativity to prove it.
But it may well be that I overlooked something (which is why I ask...).

(1) for any function $\varphi:E\to F$, the relation $R_\varphi$ as you define it is always an equivalence relation on elements of $E$. But the notion of congruence depends of the laws you have on your sets, and $R_\varphi$ will be a congruence for the operations that are preserved by $\varphi$. Notice that your formulation with $usv$ is not anymore well-defined without associativity: you have to state it separately for $us$ and $sv$.

(2) Let us weaken even more the hypotheseses. Let $\varphi:E\to F$ be any function, without any structure assumed on $E$ and $F$.
Then if we take the definitions you wrote for "recognised" and "saturated", the 3 propositions are still equivalent, as your proofs still work.

The thing you will lose by considering arbitrary sets (or groupoids or loops) is that you won't carry out the nice monoid structure of $\Sigma^*$, so you lose almost all the tools of regular languages theory, like Myhill-Nerode equivalence, Green relations, and so on...

For (3), I think Jean-Eric Pin's webpage (including the document you mention) contains good surveys of this field.


Terms and definitions for regular language and NFA let's say L is a regular language,what term does L should uphold so that there is an NFA without  epsilon moves,in which for every accepting state δ(q,σ)=Ø?I can think of some terms like that the last letters can't hold a power,but I was wandering if there is a formal definition?

Let $L$ be a regular language. There exists a NFA for $L$ in which $\delta(q,\sigma)=\varnothing$ (for every final state $q$ and every symbol $\sigma$) if $\lambda\notin L$.

We can make this into a characterization: iff $\lambda\notin L$ or $L = \{ \lambda\}$.


Is this a well-known NP-hard problem? Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in \{1, \ldots, m\} \, .$$

Then, I want to know the subset—or subsets, since there may be more than one valid solution—$T$ with minimum cardinality such that every $S_i$ has at least one element in $T$. I suspect this is an NP-hard problem (or NP-complete in its decision version), but I don't know if it's one that has a name.

As an example, consider $R = \{1, 2, 3, 4, 5\}$ and $S = \{S_1, \ldots, S_9\}$, where

$S_1 = \{1, 2, 3\} \, , \enspace S_4 = \{1, 4, 5\} \, , \enspace S_7 = \{1, 2, 3, 4\} \, ,$
$S_2 = \{1, 2, 4\} \, , \enspace S_5 = \{2, 3, 5\} \, , \enspace S_8 = \{1, 3, 4, 5\} \, ,$
$S_3 = \{1, 2, 5\} \, , \enspace S_6 = \{3, 4, 5\} \, , \enspace S_9 = \{2, 3, 4, 5\} \, .$

Here, the solutions are $T = \{\{1, 3\}, \{1, 5\}, \{2, 4\}, \{2, 5\}\}$. (I'd be happy even if I knew just one of them.)

Note that I'm not asking for an algorithm to solve the problem. I just want to know where this is or reduces to a well-known problem.

3-Hitting Set problem is known in parameterized complexity theory. The requirement $\cup S_i=R$ can always be assumed without loss of generality. See e.g. An efficient fixed-parameter algorithm for 3-Hitting Set. According to this link it is NP-hard in its usual (not parameterized) form. Proving NP-completeness of your problem we give reduction FROM 3-Hitting Set to your problem not vica versa. Therefore your problem is NP-complete (in its decision form).


Looking for Methods in Computer Vision for Distinguishing Disappearing and Fading Objects Suppose I have a video in which there are two objects $A$ and $B$. Object $A$ appears suddenly at time $Ta1$, and then disappears suddenly at time $Ta2$. Object $B$ appears suddenly at time $Tb1$, and then starts to fade gradually at time $Tb2$, and at $Tb3$ the object $B$ completely fades away. The background intensity is nearly constant, but is changing at a slope $s$ ($s$ can be a very small positive, zero or very small negative) in the long run. For simplicity, we can assume the objects never move. Also, the time $Ta1$, $Ta2$, $Tb1$, $Tb2$ and $Tb3$ are not known beforehand, they can only be inferred from the data or the graphs.

In the graphs below, (a) shows the intensity of a pixel where object $A$ appears against time, (b) shows the intensity of a pixel where object $B$ appears against time, and (c) shows the intensity of a background pixel against time. The graph on the left hand side is the theoretical plot, while the graph on the right hand side is the actual plot from my data. In all graphs, the slope $s$ is a very small positive number.

I tried to use the Running Gaussian Average with Selective Background Update method. It is quite successful in segmenting the background from the objects $A$ and $B$, except that a slight amount of background may be wrongly regarded as foreground at a late time (when the intensity of the background increases by a certain amount). But leaving this issue aside, I would like to do one step further, that is, to distinguish between objects $A$ and $B$. Surely if $Ta1=Tb1$ and $Ta2=Tb2$, the distinction can only be made after $Tb2$ (or even $Tb3$). But what methods can be applied to perform the distinction?

There are probably many possible approaches, but I'll suggest one candidate step-by-step approach that I think might work well, given the information shown in your question:

1. Find the times

As a first step, I suggest that you estimate $Ta1,Ta2,Tb1,Tb2,Tb3$.

The good thing is that $Ta1,Ta2$ will be the same for all pixels of object A, and $Tb1,Tb2,Tb3$ will be the same for all pixels of object B.  This means you only need to estimate 5 numbers, and you have an entire video to work with -- so you should have more than enough data to infer these 5 times.

One reasonable way to do this would be to do foreground-background segmentation to identify the foreground pixels, using the Running Gaussian Average with Selective Background Update method you already tried; as you said, this is already fairly accurate.  It won't need to be perfect -- just getting it approximately right should be enough for what I'm going to suggest.

When you've done that, pixels inferred to be foreground pixels will be a mixture of object A and object B (plus a little bit of error).  Now looking at just the inferred foreground pixels, you should be able to deduce $Ta1$, $Ta2$, $Tb1$, $Tb2$, $Tb3$.  For instance, at each time, compute the average pixel intensity over all foreground pixels, and graph this as a function of time.  You should find that this time series is roughly constant until $Ta1$, then has a large increase at $Ta1$, another large increase at $Tb1$, a big decrease at $Ta2$, and a smooth decrease from $Tb2$ to $Tb3$.  Each of those increases/decreases should be easily detectable in the signal.

For instance, you could take the first derivative of this time series (the average intensity of the foreground pixels) and look at its peaks.  You should find large positive peaks at $Ta1$ and $Tb1$ and a large negative peak at $Ta2$.  Apart from those three times, the first derivative should be close to zero for all time periods, except that it is a significant negative value from $Tb2$ and $Tb3$.  I suspect these two characteristics should be enough to identify $Ta1,Ta2,Tb1,Tb2,Tb3$.

If that's not accurate enough, there are alternative approaches; ask if you need them.  But I expect it will be relatively easy to implement this step and find the times $Ta1,Ta2,Tb1,Tb2,Tb3$.

2. Build a three-class classifier

Now that you know the times $Ta1,Ta2,Tb1,Tb2,Tb3$,
I suggest that as your next step you build a classifier that takes the time series for a particular pixel and classifies it as one of three classes: A (object A), B (object B), or Bg (background).

It will probably suffice to build a simple classifier by hand.  My guess is you probably won't need terribly sophisticated methods.  I'd suggest you identify a few features, and for each pixel, compute a feature vector (the values of those features, for that particular pixel).  There are some natural features you could use, for instance:

$\text{avg}([Ta1+\varepsilon,Ta1+2\varepsilon])-\text{avg}([Ta1-2\varepsilon,Ta1-\varepsilon])$, where $\text{avg}([t_1,t_2])$ is the average intensity of the pixel taken over times in the interval $[t_1,t_2]$.  This basically tells you how large a "jump" in the signal there is, at time $Ta1$; for A you expect it to be large, whereas it should be approximately zero for B and Bg.
$\text{avg}([Ta2+\varepsilon,Ta2+2\varepsilon])-\text{avg}([Ta2-2\varepsilon,Ta2-\varepsilon])$.  For $A$ you expect this to be very negative, whereas it should be approximately zero for B and Bg.
$\text{avg}([Tb1+\varepsilon,Tb1+2\varepsilon])-\text{avg}([Tb1-2\varepsilon,Tb1-\varepsilon])$.  For B you expect it to be large, whereas it should be approximately zero for A and Bg.
$\text{avg}([Tb3+\varepsilon,Tb1+3\varepsilon])-\text{avg}([Tb2-2\varepsilon,Tb2-\varepsilon])$.  For B you expect it to be very negative, whereas it should be approximately zero for A and Bg.  (unless $Ta1$ or $Ta2$ falls within the interval $[Tb2,Tb3]$, in which case you can also figure out what you expect it to be: very positive for A if $Ta1$ is in the interval but $Ta2$ isn't; very negative if $Ta2$ is in the interval but $Ta1$ isn't; or zero if they're both in the interval)
The fraction of the time points that your Running Gaussian Average with Selective Background Update method classifies the pixel as background.  For A and B we expect it to be small; for Bg we expect it to be large.

You might be able to build a classifier simply by setting thresholds for each of these features and using the result to select which object you have.

If that's not accurate enough, you could imagine training a classifier using some machine learning method (e.g., logistic regression, linear SVM, etc.).

Now apply this classifier to each pixel separately, to classify it as belonging to object A, object B, or the background.

3. Optional: Clean up the results

You could optionally clean up the results by using spatial locality: we expect object A to be a connected region in the image, and same for object B.  For instance, if a pixel belongs to object A, then that makes it incrementally a bit more likely that the neighboring pixels belong to object A.  Or, a more sophisticated version of this is: if two adjacent pixels have approximately the same color, then they're a bit more likely to belong to the same class; if they have very different colors, there are no restrictions (they might belong to the same class, or might belong to a different class; each is equally plausible).

There are methods to take this information into account.  For instance, suppose your classifier outputs not just its predicted class, but also a probability for each of the three classes (e.g., 90% chance this particular pixel is object A, 8% chance it is object B, 2% chance it is background).  Then you can combine this with a graph cut method to take into account spatial locality, i.e., to find a segmentation that both takes into account your classifier's predictions and also takes into account spatial locality.

This kind of post-processing might further enhance the accuracy of your method, by cleaning up the boundaries of the objects.


computably defined function with non computable range Are there examples of functions that can be defined computably, though the existence of their range is not computable?

Your question is a bit unclear, but you're probably looking for this example:
$$
A(x,n) =
\begin{cases}
x & \text{ if program $x$ halts within $n$ steps}, \\
\bot & \text{ otherwise}.
\end{cases}
$$
This is a computable function whose image is the set of halting problems (together with $\bot$).


Finding closest line segment intersecting rays Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint.
A query would look like this; given a query point $q$ shoot 4 rays from $q$ (both sides horizontally and both sides vertically) and report the line segment in $S$ closest to $q$ intersecting any on these rays.
Is there a way to do this faster than $O(n)$ by preprocessing the data and storing it in some data structure? Or do we have to check for intersections with all segments for each ray and then compute the distances from the intersected line segments to $q$?

You'll need two data structures - for vertical rays and for horizontal rays. I'll describe a data structure for vertical rays. Draw a vertical line through each segment end - you'll get a set of vertical slabs. Each of these slabs will be divided by pieces of original segments into trapezoids (possibly infinite ones).

Number of these slabs will not exceed $2n$, and number of trapezoids in each slab will not exceed $n$. In order to find a segment, closest to the query point along a vertical ray (going up or down), you need to use binary search to find a slab at first, and then - another binary search to find a trapezoid inside the found slab. Upper and lower boundary of this trapezoid will give you the answer. These two binary searches will take $O(log(n))$ time.
The data structure for horizontal rays is similar - the only difference is that slabs should be horizontal.


What is the complexity of this prime trial division algorithms? I have two algorithms. What are their time complexities?
The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$.
The second algorithm generates a list of prime from $2,3...,\sqrt{n}$ and divides the input, $Num$ by these primes.

Algorithm 1 needs $\sqrt{Num}/2$ modulo divisions in the worst case, and Algorithm 2 needs just $\sqrt{Num}/\log{n}$ modulo divisions.
Algorithm 1:

        bool IsPrime(BigInteger Num)
        {
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else if (Num % 2 == 0) return false;
            else for (BigInteger u = 3; u * u <= Num; u += 2)
                    if (Num % u == 0) return false;
            return true;
        }

Algorithm 2:

        bool IsPrimeBetter(BigInteger Num)
        {
            ulong arrayLe = (ulong)Isqrt((long)Num);//Sqrt of Num
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else foreach (var prime in new Atkin(arrayLe))//Atkin sieve which generate list of primes from 2 to √Num
                    if (Num % prime == 0) return false;
            return true;
        }

I don't really know how to check complexity of them.

The first one is easy: Figure out how often you will iterate through the loop in the worst case.

The second one is harder: Again, you need to figure out how often you will iterate through the loop. However, you also need to figure out how long it takes to calculate the list of primes, and how long it takes to enumerate all those primes.

In practice, you would likely check many numbers for primality, so you wouldn't create a complete new sieve every time, but keep the previous sieve, and extend it when checking a larger prime number.


Many-one reductions between the set of true sentences and a particular arithmetical set Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic.

Let TH(N) = {ϕ : ϕ is a first order sentence in the language of arithmetic and N |= ϕ} (Where N is the standard model of arithmetic - , x, <, +, 0, and the successor; S)

Let γ(x) be some formula with exactly one free variable, namely x. Then assume X = {n : γ(n)} to be the arithmetical subset of the natural numbers defined by γ(x).

My question is: Is there a way to show either of X or TH(N) many one-reduce to each other?

For any such $X$ we have $X\le_mTh(\mathbb{N})$ but not conversely (and in fact $Th(\mathbb{N})$ is vastly more complicated than $X$).
To see that $X\le_mTh(\mathbb{N})$, we want to translate a question of the form "Is $n\in X$?" into one of the form "Is $\psi_n$ a true sentence?" for some appropriate sentence $\psi_n$. Now "$n\in X$" is equivalent to "$\gamma(n)$," and that's almost a sentence in the language of arithmetic - the only issue is that "$n$" isn't a symbol in the language of arithmetic (which consists only of $0,1,+,\times,<$). Do you see a quick way around this?

 Each natural number $n$ has a corresponding numeral, usually denoted "$\underline{n}$," which is just an appropriate string of the symbols $0$," "$1$," "$($," and "$)$" (or is the symbol "$0$" if $n$ is $0$): e.g. $\underline{4}$ is the string $((1+1)+1)+1$. Then if we let $\psi_n=\gamma(\underline{n})$, we have that $\psi_n\in Th(\mathbb{N})$ iff $n\in X$.

Note that here I'm conflating e.g. the number $0$ and the constant symbol $0$; this is annoying, but standard.

The other direction is a consequence of Tarski's undefinability theorem: just show that anything many-one reducible (or even Turing-reducible) to an arithmetically definable set is itself arithmetically definable. This will show that we never have $Th(\mathbb{N})\le_mX$ (or even $\le_TX$) for such an $X$. The key here is to show that the basic notions of computability theory are arithmetically definable:

 Use Kleene's $T$-predicate to talk about computable reductions.


Asymptotic notation for summations I am struggling to understand why this property of asymptotic notation is true

In general, it is not: see Summation of asymptotic notation, Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?.
But if each $O(f(k))$ term uses the same hidden constant, then it follows by expanding the sum: see  https://en.wikipedia.org/wiki/Big_O_notation#Sum, Summing big-O-notation, and then apply them repeatedly.


In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$ I have to prove that
 $$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$
The functions are non-negative.

Clarification:
$$\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$
it means
$$\mathcal{O}(f(n)+g(n))\subseteq\mathcal{O}(f(n))\land\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n)+g(n))$$

I try to explain my argument, i want to get on one side $f(n)+g(n)\in\mathcal{O}(f(n))$ and on the other: $f(n)\in\mathcal{O}(f(n)+g(n))$ in order to conclude that $\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$ true.

I start with the hypothesis:

$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\iff g(n)\in\mathcal{O}(f(n))$
$\iff(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)\leq c_1f(n),\forall n\geq n_0) \implies$
$\{$adding $f(n)$ to both members of the inequality$\}$ $(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1f(n)+f(n),\forall n\geq n_0)\implies\quad(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq (c_1+1)f(n),\forall n\geq n_0)\implies \{\textrm{taking}\quad c_1^{'}=(c_1+1)\}\quad  (\exists c_1^{'}\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1^{'}f(n),\forall n\geq n_0)\iff \{by\quad definition\quad of \quad Oh-big \quad order\}\quad f(n)+g(n)\in\mathcal{O}(f(n))$

Now to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ start from the trivial proposition: $\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))$:

$\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))\iff f(n)\in\mathcal{O}(f(n))\iff(\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n),\forall n\geq n_0)\implies$ $\{$adding $g(n)$ to right member of inequality$\}\quad (\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n)+g(n),\forall n\geq n_0)$

At this point I'm stuck I don't know how to continue in order to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ to finish then the proof...

Thanks to everyone who read this :)

I think you are pretty much done.

$$
g(n) \ge 0 \implies f(n) \le f(n) + g(n), \quad \forall n \in \mathbb{N}
$$

So pick $c = 1 \in \mathbb{R}^+$ and $n_0 = 1 \in \mathbb{N}$, then
$$
f(n) \le c\cdot(f(n) + g(n)), \quad \forall n\ge n_0
$$


Show that the following construction is not a correct proof for Context Free Grammars Give a counterexample to show that the following constructions are not correct proofs for the star operation:
Given a CFG $G = (V,Σ,R,S)$, add the new rule  i) $ S → SS$ or ii) $S → SS|ε$.

For i), I basically said that this rule is an infinite loop and doesn't contain an epsilon, so can't be the star operation.
For ii) I'm stuck and can't see why it's not equivalent to the star operation
I know the real star operation is $S'→SS'|ε$ but cant seem to see find out why ii) is not the case. I can't find a counterexample.
Any help is hugely appreciated.

$ S\to aSb \mid \varepsilon $.

Hint (due to Klaus Draeger): Consider what happens when you apply transformation (ii) to this grammar. Does the resulting grammar $G'$ satisfy $L(G')=L(G)^*$?

Explanation: The point is that the $S\to SS$ production can be used "inside" the grammar, not just on the "top-level" where it is intended. We can derive $S\to^* aSSb \to^* aababb$ which is of the wrong form. (And the grammar has $S\to\varepsilon$ anyhow.)


Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval? This question is related to my previous question:

Looking for a set implementation with small memory footprint

I'm looking for information about combined data structures, which can efficiently represent a set S of non-intersecting sub-intervals of the given integer interval [0, MAX) with the single operation:

testAndInsert(min, max) - test if the interval [min, max] intersects with any of already existing intervals in the S; if no intersections are found, then insert the interval [min, max] into the set S, potentially merging it with one or two neighbor intervals; return success, if and only if the insertion was done.

I'm asking about combined data structures, because it looks like we have two evident choices - linked data structures (for example, various binary trees) and array-based data structures (bitmaps). However, both of them have their own shortages:

Balanced binary trees will have O(log(n)) time complexity and look good, when number of intervals in the S is much less than the MAX. However each node of the tree will take at least 16 bytes (for links) on 64-bit machine. For example, if we represent all   odd integers in the interval [0, 1000), then we'll need 8000 bytes only for links.
Bitmaps will have O(1) time complexity, but take constant memory, which depends only on   the MAX. Representation of all the odd integers in the interval [0, 1000) needs only 125 bytes. However, when the MAX is large and the number of existing intervals is much less than the MAX, then most of the memory, taken by the bitmap, will be wasted.

I'm not actually focused on the time complexity - something between O(1) and O(log(n)) is acceptable, but in real situations the memory footprint of the data structure plays a very important role. If machine begins swapping because of lack of memory, then even O(1) data structure will work for ages.

Are there any data structures, which could automatically adapt themselves to the size of the S in this problem? For example, when we start with the empty S (no intervals at all), the data structure is linked, then it becomes array-based (piece by piece?), then it probably switches to storage of the S complement (free space is small) and becomes linked again?

P.S.: I know about the Boost ICL interval set and use it now, but I'm interested in other possible approaches.

Here is one space-efficient memory-hierarchy-aware in-memory data structure that might be a reasonable choice.  The data structure is a binary search tree with 16-byte nodes.
Each node is either an internal node or a leaf node:

An internal node points to two children.  It has a value $v$, a left child $\ell$, and a right child $r$.  All integers $\le v$ are in the left child; integers $>v$ are in the right child.

A leaf node holds a run-length encoding of a bitmap.  Notice that an interval has a very short run-length encoding, so this is slightly more general than storing an interval in each leaf (it is a hybrid somewhere between a binary tree of intervals and a binary tree of bitmaps).

Each node of the tree is responsible for some interval of integer values $[s..t]$.  The root is responsible for $[0..\text{MAX}-1]$.  For an internal node containing the value $v$, its left child is responsible for $[s..v]$ and its right child is responsible for $[v+1..t]$.  A leaf that is responsible for $[s..t]$ has a run-length encoding of the bitmap for the integers in the interval $[s..t]$.
How do we pack each node into 16 bytes?

I'll assume the tree contains at most $2^{32}$ nodes in the tree.  Therefore, each node can be referred to by a 32-bit label.  We'll have an array $A$ of nodes, and the node with label $i$ will be stored at $A[i]$.  With this optimization, each child pointer can be stored in 32 bits (rather than 8 bytes for a 64-bit pointer).  Note that the restriction to $2^{32}$ nodes is not very restrictive; unless your machine has more than 64 GB of RAM, you couldn't fit anything larger in memory anyway.

I'll assume that $\text{MAX} \le 2^{64}$.

The first bit of the node will indicate whether it is an internal node or a leaf node, leaving 127 bits for the rest.

Internal nodes: We need 64 bits for the two child pointers.  That leaves us 63 bits for the value $v$.  We'll store the value $v$ as an offset within the interval for that node.  In other words, if the internal node is responsible for the interval $[s..t]$, then we'll store $v$ as the value $v-s$.  (We know $v \in [s..t]$, so it follows that $v-s$ is a non-negative integer.)  A 63-bit unsigned int is plenty for this offset.  (If we wanted to use an offset that is larger than will fit in a 63-bit unsigned int, then we just split the range artificially.  Since $\text{MAX} \le 2^{64}$, this will impose at most one or two extra splits at/near the root.)

Leaf nodes: We have 127 bits for the run-length encoding of the bitmap corresponding to the interval $[s..t]$.  We can use any convenient run-length encoding.  If the run-length encoding of the bitmap does not fit within 127 bits, we split the interval: we turn it into an internal node with two children.
If you know something about the typical distribution of lengths of runs (i.e., the lengths of intervals, the lengths of the gaps between intervals), you can choose a run-length encoding that is optimized for that distribution.  Otherwise, you can use any convenient generic run-length encoding scheme (e.g., recursive Rice-Golomb encoding); see also this Wikipedia page on compressed bitmaps.

Notice that we don't store $s$ or $t$ in each node, but that's OK.  The interval $[s..t]$ for a particular node is determined by the path that we took to reach that node.  As we traverse down from the root, we can keep track of the interval $[s..t]$ and update it each time we follow a child pointer.
If you wanted, you could combine with this with some sort of self-balancing binary tree scheme )or a self-optimizing binary tree, such as a splay tree), but it might not be necessary in practice, depending upon the access pattern in your application, and it definitely adds complexity.


Sorting algorithms which accept a random comparator Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the algorithm is a sorted list/array.

I am wondering though which sort algorithms would actually work with a comparator that is not an order relation (in particular one which returns a random result on each comparison). By "work" I mean here that they continue return a permutation of their input and run at their typically quoted time complexity (as opposed to degrading to the worst case scenario always, or going into an infinite loop, or missing elements). The ordering of the results would be undefined however. Even better, the resulting ordering would be a uniform distribution when the comparator is a coin flip.

From my rough mental calculation it appears that a merge sort would be fine with this and maintain the same runtime cost and produce a fair random ordering. I think that something like a quick sort would however degenerate,  possibly not finish, and not be fair.

What other sorting algorithms (other than merge sort) would work as described with a random comparator?

For reference, a comparator is an order relation if it is a proper function (deterministic) and satisfies the axioms of an order relation:

it is deterministic: compare(a,b) for a particular a and b always returns the same result.
it is transitive: compare(a,b) and compare(b,c) implies compare( a,c )
it is antisymmetric compare(a,b) and compare(b,a) implies a == b

(Assume that all input elements are distinct, so reflexivity is not an issue.)

A random comparator violates all of these rules. There are however comparators that are not order relations yet are not random (for example they might violate perhaps only one rule, and only for particular elements in the set).

So basically, you want to know if there is any sorting algorithm which wouldn't degrade from its average case if given a compare function similar to:

int Compare(object a, object b) { return Random.Next(-1,1); }

... where Random.Next() is some method that will produce a randomly-generated integer between a specified inclusive lower and upper bound.

The answer is actually that most basic sorting algorithms will perform according to their average case, because they obey at least one of the following two conditions:

A comparison between two unique elements is never made twice in the sort, and/or
In each iteration of the sort, the correct position of at least one element is determined and so that element is never compared again.

For instance, SelectionSort iterates through the sub-list of unsorted elements, finds the "least" and/or "greatest" element (by comparing each one to the greatest so far), places it in its correct position and repeats. As a result, even with a non-deterministic comparator, at the end of every iteration the algorithm will have found a value that it thinks is least or greatest, swaps it with the element in the position it is trying to determine, and never considers that element again, thus it obeys Condition 2. However, an A and B can be compared multiple times during this process (as the most extreme example, consider several passes of SelectionSort on an array that's sorted in reverse order) so it violates Condition 1.

MergeSort obeys Condition 1 but not 2; as sub-arrays are merged, elements in the same sub-array (on the left or right side) are not compared to each other because it has already been determined that the elements on that side of the array are in order among themselves; the algorithm only compares the least unmerged element of each subarray to the other to determine which is lesser and should go next in the merged list. This means that any two unique objects A and B will be compared to each other a maximum of one time, but any given element's "final" index in the full collection is not known until the algorithm is complete.

InsertionSort obeys only Condition 1 as well even though its overall strategy and complexity looks more like SelectionSort. Each unsorted element is compared with sorted elements, greatest-first, until one is found that is less than the element under inspection. the element is inserted at that point, and then the next element is considered. The result is that the relative order of any A and B is determined by one comparison, and further comparisons between that A and B are never performed, but the final position of any element cannot be known until all elements are considered.

QuickSort obeys both Conditions. At each level, a pivot is chosen and arranged such that the "left" side contains elements less than the pivot and the "right" side contains elements greater than the pivot. The result of that level is QuickSort(left) + pivot + QuickSort(right) which basically means the position of the pivot element is known (one index greater than the length of the left side), the pivot is never compared to any other element after it has been chosen as a pivot (it may have been compared with previous pivot elements, but those elements are also known and are not included in any subarrays), AND any A and B that end up on opposite sides of the pivot are never compared. In most implementations of pure QuickSort, the base case is one element, at which point its current index is its final index and no further comparisons are made.

The only comparative sort I can think of that wouldn't obey either condition is a non-optimized BubbleSort. If the sort does not accept that the X greatest elements are in their proper place after running X passes, and/or uses a "double-check" pass to verify the list is sorted, the sort will only be considered "done" when the random comparator has returned -1 or 0 for every two adjacent elements in the list during a pass and thus no swaps were performed (an event which, if truly random, would occur with probability $(2/3)^{N-1}$; for a relatively small list of 25 elements, that's a one in 2000 chance, while for 100 elements the probability is 3.7*10-18). As the maximum absolute value of the result of the comparator increases, the probability for any one comparison to return negative or zero decreases towards .5, making the chance to end the algorithm that much less likely (the chance of 99 coin flips all landing heads, which is basically what this boils down to, is 1 in 1.2*1030)

EDIT A LONG TIME LATER: There are a few "sorts" designed specifically as examples of what not to do which incorporate a random comparator; perhaps the most famous is BogoSort. "Given a list, if the list is not in order, shuffle the list and check again". Theoretically it will eventually hit on the right permutation of values, just like the "non-optimized BubbleSort" above, but the average case is factorial-time (N!/2), and because of the birthday problem (after enough random permutations you become more likely to encounter duplicate permutations than unique ones) there is a nonzero possibility of the algorithm never completing to officially the algorithm is time-unbounded.


SMO, Random forest and Bayes net algorithms: why does Random forest perform better? I analyzed a dataset using those 3 different algorithms.
As I can see, Random forest performs better in most cases.
My dataset is composed of 4000 instances of two classes (class A 2000 elements, class B 2000 elements).
I use 207 metrics to classify the instances, but I also use the first 20 or 10 best metrics for InformationGain.
My question is: why sometimes an algorithm performs better than another one (in this case I'm only comparing this 3).
I read about them but I would like to have a complete scenario of why in some case RF is better than Bayes net and why sometimes is the opposite. And why SMO is always worst than the other two, in my experiences. Thank you so much!

In machine learning, there's often no clear "why" or "reason" we can point to.  These are different methods, which implicitly embed different biases or different priors or different assumptions, and thus will work better in different situations.


Checking acceptance of a word vs finding an accepted word We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM?

Are these two problems related in some way, i.e. undecidability of one implies the undecidability of other (in any structure, like FA, LBA, PDA etc)?

My hunch is that they are not related but I am not able to argue why?

The two problems are Turing equivalent: one is undecidable for Turing machines iff the other is.

Deciding whether a Turing machine (TM) $M$ halts on a specific input $x$ is the Halting problem for Turing machines.

Given a TM $M$, we want to know whether it halts on some word. From
$M$ we build a TM $M^*$ that, independently of its input, dovetails the computation of $M$ over all
inputs (i.e. it mimics the computation of $M$ on all possible inputs in
parallel), and halts iff one of these computations halts.
If we had an oracle $H$ that decided the halting problem, it could
decide whether $M*$ halts or not, hence whether the TM $M$ halts on
some input. This is only for the decision on the existence of that
input, but the same dovetailing construction could then be used to
compute the halting input when it is known to exist. Hence we could build a TM that always halts, either with a word on which $M$ halts if there is one, or with failure when there is none.

Hence, if the halting problem were decidable, the problem of deciding
whether a TM halts on some input, and determining that input wold be
decidable too.

Conversely, let us assume that it is decidable whether a TM halt on
some input. Then given a Turing machine $M$ and and input $x$ we want
to decide whether $M(x)$ halts (the halting problem for $M$ on input
$x$).  For this we build a machine $M'$ that, independently of its
input, will simply mimic the machine $M$ running on input $x$. Hence
the machine $M'$ halts on some input (thus on any input) iff $M$ halts
on input $x$. Hence we have a decision procedure for the halting
problem if we have a decision procedure for halting on some input.

Both problems are Turing reducible to each other. Hence they are
Turing equivalent. If one were to be decidable, the other would be too. Or, to take the contrapositive, the undecidability of one implies the undecidability of the other.


Is the existence of an oracle such that $P^O = NP^O$ nontrivial? This famous paper proves the existence of both oracles $A$ and $B$ such that $\textbf{P}^A = \textbf{NP}^A$ and $\textbf{P}^B \neq \textbf{NP}^B$, therefore proving that any resolution to the P versus NP problem must be nontrivial in the sense that it cannot relativize.

I understand the significance of the oracle separation given by the latter oracle $B$: it shows that it certainly isn't trivially true that P = NP (of course, this result is incredibly obvious anyway!). But while I'm sure I'm wrong, the existence of the former oracle seems kind of obvious to me.

I would naively expect that for any complexity classes A and B, there would exist some oracle $O$ such that $\textbf{A}^O = \textbf{B}^O$. Just let $O$ be any oracle for a language that is complete for any complexity class C that is "sufficiently larger" than $\mathbf{A} \cup \mathbf{B}$ (in some sense which I suspect could be made precise). Then the oracle $O$ would be so much more powerful than the abstract machines whose capabilities define A and B that the most efficient solution to any tractable problem would simply be to consult the oracle and call it a day. In this case the oracle would "eat up" the original abstract machines and we would simply have $\mathbf{A}^O = \mathbf{B}^O = \mathbf{C}$. As a rather overpowered example, isn't it trivially true that $\mathbf{P}^\mathbf{R} = \mathbf{NP}^\mathbf{R} = \mathbf{R}$?

(Sorry, this question probably shows that I lack a basic conceptual understanding of how relativization works.)

The existence of an oracle with respect to which $\mathsf{P} = \mathsf{NP}$ shows that $\mathsf{P} \neq \mathsf{NP}$ cannot be proved using techniques that relativize such as diagonalization. In contrast, the time and space hierarchy theorems do relativize, disproving your claim that any two complexity classes are equal relative to some oracle.

The easy observation that $\mathsf{P}^\mathsf{R} = \mathsf{EXP}^\mathsf{R}$ seems to contradict the fact that the time hierarchy theorem relativizes. Tthe definition of $\mathsf{X}^\mathsf{R}$ that you use is $$ \mathsf{X}^\mathsf{R} = \bigcup_{A \in \mathsf{R}} \mathsf{X}^A.$$
The time hierarchy theorem shows that $\mathsf{P}^A \neq \mathsf{EXP}^A$ for every language $A$, but not for every family of languages.

The oracle with respect to which $\mathsf{P} = \mathsf{NP}$ is a single language. One possible choice is any $\mathsf{PSPACE}$-complete language. This is very similar to using an arbitrary recursive language, with a crucial difference – there are languages in $\mathsf{PSPACE}$ which are complete with respect to polynomial time reductions.


What are HP and MP in this context? From Kozen's Automata and Computability, 3ed, lecture 32 p. 328:

What are HP and MP in this context?  I tried looking around and this text says:

How did the halting problem and membership problem become regular expression?  I am so loss here.

Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example,

HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ eventually halts when started on input $x$,

and, similarly

MP is a collection of pairs $M, x$ as above and an instance of MP is in the set MP if the machine described by $M$ eventually halts in an accept state when started on input $x$.

In simple terms, HP is about programs and inputs and answers "Does this program halt on this input?" and MP answers "Does this program accept this input?"

The octothorpe (the # symbol) is just a separator so we know where $M$ ends and $x$ starts.


What is the property of a PL that extracting a subroutine should not change the meaning? What is the name of the property of a Programming Language that says that extracting a subprogram into a subroutine and using that subroutine instead of the subprogram should not change the meaning of the program?

I could swear that this exists and that it has a well-known name, but I can't for the life of me remember it. My efforts to search for the name have been thwarted by being swamped with results for the Liskov Substitution Principle or Referential Transparency.

What I am looking for is the property that I should be able to replace

printf("Hello");

with

void hello() {
    printf("Hello");
}

hello();

without changing the meaning of the program.

I think it is named after the person who coined it, but I am not sure. Something like XYZ Equivalence or XYZ Principle where XYZ is the name of a well-known Computer Scientist. I want to say Strachey, but I couldn't find a mention of anything similar in Fundamental Concepts in Programming Languages.

I believe you are looking for Morris style Contextual Equivalence. Which says that the meaning of
a term (in your case a subroutine) should not change in any context.

If, $⟦ \cdot ⟧ : term \to \mathcal{D}$, is the meaning function then
$$\forall C. ⟦C[t]⟧ = ⟦ C ⟧ \circ ⟦ t ⟧ $$
Where $C[\cdot]$ is a context with a hole in it.


Reducing MAX-2SAT to Vertex Cover? In A simplified NP-complete MAXSAT problem, a reduction is given from Min Vertex Cover to MAX-2SAT by replacing each each vertex $x_i$ by a single-variable clause, and each edge by a two-variable clause:

\begin{align}
 \Phi = \left(\bigwedge_{i=1}^n x_i\right) \wedge \left(\bigwedge_{\lbrace i,j\rbrace \in E} (\overline{x}_i \vee \overline{x}_j)\right)
\end{align}

This basically makes sense to me, because the QUBO version of Vertex Cover is to maximize:
\begin{align}
L = \sum_{i=1}^N x_i -  \sum_{\lbrace i,j\rbrace \in E} x_ix_i
\end{align}
and QUBO can be converted to MAX-2SAT quite simply.

However, I would to know how the reverse transformation works.

How do you go from MAX-2SAT to Vertex Cover?

I don't actually know if this is an unsolved problem or not, but I figure it shouldn't be since they are both NP-Complete. Would it be as simple/tedious as trying to force an arbitrary MAX-2SAT instance into the same form as $\Phi$? I don't know if that can be done though.

You can reduce MAX-2SAT to Satisfiability (using Cook-Levin), which can then be reduced to Vertex Cover (Folklore).


Complexity class (P/NP) variants of Hamiltonian paths problems I know that the following problems related to Hamiltonian paths in graph are NP-complete:

Undirected Hamiltonian circuit:
Given an undirected graph, does it has a cycle that passes through
each node exactly once?
Undirected Hamiltonian path:
Given an undirected graph, does it has a path that passes through each node exactly once?
Directed Hamiltonian circuit:
Given a directed graph, does it has a directed cycle that passes through each node exactly once?

But then my textbook says following problems are NP-Hard but not NP-complete:

Problem A: Finding a Hamiltonian circuit in a graph with number of vertices $|V|$ divisible by 3
Problem B: Determining if Hamiltonian circuit exists in the graphs as given problem A.

Why is this so?

Problem A is not a decision problem. This means that by definition it is not NP-complete.

Problem B is NP-complete. But every NP-complete problem is NP-hard.

Let me remind you the definitions.

NP-complete problem. Problem P is said to be NP-complete if it is in NP and every problem in NP can be reduced in polynomial time to P.

NP-hard problem. Problem P is said to be NP-hard if every problem in NP can be reduced in polynomial time into P.


What can be said in general about a homomorphism between two regular languages? In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can find a homomorphisms? And if not that, are there maybe a finite number of families of homomorphisms which divide all regular languages into classes?

My motivation for asking this question is from taking an undergrad course in group theory, and wanting to see if the treatment of polynomials by group theory can be applied to regular languages.

Some examples, to get the discussion going:

For an infinite family of languages with no homomorphisms between them, consider the languages $L_k=\{a,a^k\}\subseteq\{a\}^*$ for $k\ge 2$. If $f:L_i\to L_j$ were a homomorphism for $i\neq j$, then $f(a)$ would be either $a$ or $a^j$, and $f(a^i)$ would be $a^i$ or $a^{ij}$, neither of which is in $L_j$.
On the other hand, it is easy to find infinite chains of languages with homomorphisms between them, just consider $L_i=\{a^k\ |\ 1\le k\le i\}\subseteq\{a\}^*$ and the inclusion $L_i\to L_j$ for $i<j$.


alphabet of a single tape turing machine that simulates a multitape TM First of all sorry, if this question already exists, in that case, pointing to the right direction will be appreciated.

Secondly, sorry, if the question is below the expected level of Niveau, but all help appreciated.

In the textbook by J. Hromkovic, named "Theoretical Computer Science, Introduction to Automata, Computability, Complexity, Algorithmics", in Page 110, in the 2003 edition, i note that the alphabet of a single tape TM which simulates a multitape TM is given by

$$
\Gamma_{single\ tape} = (\Sigma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k} \cup \Sigma_{multi\ tape} \cup \{¢\}
$$

should that not be, instead:

$$
(\Gamma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k}  \cup \{¢\} ?
$$

according to the book, the single tape TM splits its tape in "tracks" , see image i scanned from the book: http://imgur.com/CwnyS

because, the last $¢$ is the primary left end marker, the first two terms of the Cartesian product series is responsible for the top two track, the rest $k$ tracks are constructed by the term which has k in exponent.

all help is appreciated. sorry for the dummy question. i am a meteorologist, who takes his past time in computer programming.

ps, i can neither embed (is that the correct term?) the ¢ character by \cent nor the ␣ by \textvisiblespace in a post like this. does stackexchange use a different command for those? thank you

(I successfully downloaded the image).

It is not clear in the picture what is the difference between $\Sigma$ and $\Sigma_A$, however looking at the definition of Exercise 4.12 I think that the author simply distinguishes the input alphabet $\Sigma_A$ from the working alphabet $\Gamma_A$ (tape alphabet); so in order to simulate:

the input tape of A (with symbols from $\Sigma_A$) plus the $k$ tapes of A (with symbols from $\Gamma_A$)

it uses $\Sigma_A$ in the first term of the Cartesian product.

Be careful that you didn't copy exactly the $\Gamma_B$ of the book (you wrongly put a $\cup$ where the book puts a $\times$):

$\Gamma_{B} = (\Sigma_{A} \cup \{¢,␣ , \$ \})\times \{\uparrow, ␣ \} \times (\Gamma_{A}\times \{\uparrow, ␣\})^{k} \cup \Sigma_{A} \cup \{¢\}$

The final $\Sigma_A$ is probably used to represent the initial input of the multitape machine A "as-is" (and satisfies the requirement that the input alphabet must be a subset of the working alphabet); but I think it is a little bit confusing (and perhaps the $ symbol should also be included with the final ¢)

The first steps of the simulation of B should be: copy the input to the  "hypotethetical" track 0 of B, initializing the head pointers of the "hypothetical" tracks 1,..,k of B.


What does Sigma notation mean, in the context of computability of functions? I was reading a paper on the computability of AIXI [1] and came across the notion of $\Sigma^0_n$-computability for real-valued functions in section 2.3.

I'd like to read about this in more detail.
Unfortunately I couldn't find this definition anywhere else in the literature. I already checked the references given at the end of the paper.

Could somebody point me to some book/article I can take a look at?

On the Computability of AIXI by J. Leike and M. Hutter (2015)

Section 2.1 of that paper defines such computability for sets of natural numbers, and Section 2.3 of that paper then extends the notion to real-valued functions.


Machine Learning - Data Pre-Processing I'm trying to do some non-linear predictions and am going to use a random forest with Sk-learn. However my question has to do with data pre-processing.

I'm planning on using minmaxscaler to normalize the temperature, wind, and humidity data...however I have two other variables class, and month. Class is a category data feature which I'm going to use OneHotEncoder to pre-process. However do I want to normalize or do anything with the month data? (Normalize on scale of 0 to 1? Or leave 1-12?) What might be the best approach?

Thanks!

No.  You can leave the month as is.  It shouldn't matter.  For a random forest, there's no value in normalizing it; it won't make the classifier any more or less accurate.

(The same is actually true for temperature, wind, and humidity data, too: there's no harm in normalizing them, but also no benefit, if you're using a random forest classifier.)


What does "cavallier extension claim" in The Algorithm Design Manual mean I have been reading the Algorithm Design Manual by Steven S. Skienna and on page 15 it mentions a term called "cavallier extension claim" and I have been desperately trying to find a definition for this. A search in Google just returns quotes of the same book.

Possibly my confusion lies in the misspelling of the word "cavallier", which seems like it should be spelled "cavalier", unless it was the name of some French mathematician or some other concept that I am missing.

Update

As requested here is the context. First he talks about boundary errors in inductive proofs and then this:

  The second and more common class of inductive proof errors concerns cavallier extension claims. Adding an extra item to a given problem instance might cause the entire optimal solution to change.

The phrase means "cavalier" in the ordinary English sense of the word, i.e., it is talking about a claim in a proof that is made carelessly.  Without more context or examples I'm not sure exactly what pattern of flawed proof it is referring to, but it has something to do with making an assumption/claim (without justifying it) that the solution for $n+1$ is related to the solution for $n$ in a particular way.

"Cavallier extension claim" is not a technical phrase.  It's just some English that the author is using.


Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language?

I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ contains both $0$ and $1$.

If $v x y$ is just 0s or 1s, pumping does unbalance the 0s and 1s.

If $v$ is $0^a$ and $y = 1^b$, pumping once gives $0^{N + a} 1^{N^2 + b}$, now prove that that can't possibly work out as $a + b \le N$ (in particular, $N^2 + b$ can't be a perfect square).


If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$? The following is an excerpt from CLRS:

  $\Theta(g(n))= \{ f(n) \mid  \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$.

Assuming $n \in \mathbb{N}$, I was unable to find $f(n)$ and $g(n)$ such that the bound does not apply for all $n$.

Note: This question was asked with the flawed assumption that $f(n)$ and $g(n)$ necessarily have natural domains.

If we restrict consideration to $\mathbb{N}$ and both functions are strictly positive on every $n \in \mathbb{N}$, then it is true that, if $f(n) \in \Theta(g(n))$, then there exists a $c$ such that $f(n) \leq cg(n)$ for all $n$, and vice versa.

(As pointed out in the comments, if the functions can be negative, then the answer is clearly "no", since we could take $f(1) = -1$ and $g(1) = 1$.)

The proof is straightforward. If $f(n) \in O(g(n))$, then there is an $N$ and a $C$ so that, whenever $n \geq N$, $f(n) \leq C g(n)$.

Now consider $n = 0,1,2,\dots,N-1$. For each $n$, if $g(n) > f(n)$, pick some $c_n$ so that $f(n) \leq c_n g(n)$. We can easily do this because there's only $N$ of these numbers to check.

Now pick $K = \max\{C,c_0,c_1,\dots,c_{N-1}\}$. By construction, $f(n) \leq K g(n)$ for all $n$. So we're done.

The intuition here is not tricky: We know that, if we go far enough out, $C g(x)$ bounds $f(x)$. So we just check all the cases up to that point and pick the biggest bound.

If we consider strictly positive functions defined on the reals, it is not much different to prove that, if $f$ and $g$ are both continuous and bounded below by some $\delta > 0$, we get the same result.


How many "compressible" strings are there? Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $N$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $N$ are compressible?

In particular, let's assume that $K(S)$ is the Kolmogorov complexity of binary string $S$, which is of length $N$. Then I have the following three questions:

Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N-1$?
Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N/2$?
Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq \log N$?

All of the above are for sufficiently large $N$.

A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.

Conversely, considering the program $\Pi$ that gets an integer $r$ and a string $x$, and outputs $x$ together with $r$ many zeroes. Going over all strings of length $\ell$, this gives us $2^\ell$ many strings whose complexity is at most $\ell + O(\log N)$. Choosing $\ell = M - O(\log N)$, this shows that the number of strings of length $N$ such that $K(S) \leq M$ is at least $2^M/N^{O(1)}$.

This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $N$.


Leaf nodes of B+ Tree I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists in the table and we can return the record associated with Ki.

Since the leaf nodes have the same structure of internal nodes, how can the algorithm know if a node is a leaf node ?

There are two common ways that the implementation of any B-tree variant decides if you're at a leaf node or not.

Most B-tree implementations include a tiny header in each node (e.g. to store the number of elements/pointers in the node). It might only be a word in size, but even then, it's usually not hard to find one spare bit to mark leaf nodes vs internal nodes.
Unless you are in the middle of a difficult rebalance operation, all leaf nodes are at a fixed depth in any B-tree. So knowing this fixed depth means you can just keep track of how "deep" you are in the tree while searching and you will know when you reach a leaf.


Tighter analysis of modified Borůvka's algorithm Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.

The pseudo-code is:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

We call each iteration of the outer loop a round. In each round, the inner loop cuts the number of components at least in half. Therefore there are at most $O(\log n)$ rounds. In each round, the inner loop looks at each edge at most twice (once from each component). Therefore the running time is at most $O(m \log n)$.

Now suppose after each round, we remove all the edges which only connect vertices within the same component and also remove duplicate edges between components, so that the inner loop only looks at some number of edges m' < m which are the minimum weight edges which connect two previously disconnected components.

How does this optimization affect the running time?

If we somehow knew that in each round, it would cut the number of edges in half, then the running time would be significantly improved:
$T(m) = T(m /2) + O(m) = O(m)$.

However, while the optimization will dramatically reduce the number of edges examined, (only 1 edge by the final round, and at most # of components choose 2 in general), it's not clear how/if we can use this fact to tighten the analysis of the run-time.

It is possible to craft test cases for general graphs where your Borůvka's step wouldn't
halve the number of edges in each step, even though it halves the number of vertices.
An interesting note is that the optimization that you suggest works for planar graphs. This is because
for planar graphs $|E| \leq 3*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads to a
speed up for the class of minor closed families of graphs.

Reference:

Masters thesis, Claude Anderson (on page 100 the worst case input for Borůvka's algorithm
is described). [link]
"Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320, 2004. [link]


Can someone explain in a simple way what "reducible" mean in complexity theory? I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value.

What does it exactly mean by problem A reducible to B?

Does it mean that A can be reworded into B?
i.e. Finding Vertex Set is actually the same as finding an independent set?
Does it mean that an algorithm that solves problem B will solve A?
i.e. An algorithm that finds longest path will in fact also find the shortest path?
Does it mean that A can be proved to be in the same complexity class
as B?
i.e. A is NP-Hard, B is NPC, then if A is reducible to B, A is in fact NPC?

In other words, A is reducible to B, what can we say about A or B?

As you can see my understanding is quite flaw at the moment, can someone please clarify the application of the word for me maybe even rephrase it into something more intuitive?

The most common notion of reducibility is many-one polynomial time reducibility.

A problem $A$ is many-one polynomial time reducible to a problem $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$.

This definition implies that if $B$ is solvable in polynomial time, then so is $A$.

Other notions also exist, but at this stage you're probably better off concentrating just on this one, since it is the one used to define NP-completeness.


What happens to uninterpreted predicates in Ackermann's reduction? I know the procedure to apply the Ackermann's reduction to a formula that doesn't involve uninterpreted predicates. But, how do we treat the uninterpreted boolean predicates? Nearly all the examples I have seen, usually just assume there are no uninterpreted predicates, and give examples of simpler reductions, but if we have something like this:

$$p(z, F(x_1)) \wedge F(F(x_1)) = G(x_2,G(x_1,x_3,x_4),F(x_2)) \rightarrow p(x_1,y)$$

How will I get rid of the uninterpreted predicate, so that I can apply the usual reduction?

Essentially, you can treat uninterpreted predicates as boolean-valued functions (adding a new boolean sort if necessary) and replace them with boolean variables as you would other functions. For the given example:

Getting rid of $F$ and $G$ first:

$$\begin{align*}
p(z,f_1)&\wedge f_2=g_1\to p(x_1,y)\wedge x_1=f_1\to f_1=f_2\\
  &\wedge x_1=x_2\to f_1=f_3\wedge f_1=x_2\to f_2=f_3\\
  &\wedge (x_1=x_2\wedge g_2=x_3\wedge f_3=x_4)\to g_1=g_2
\end{align*}$$

Introduce boolean variables $b_1,b_2$ for $p(z,f_1)$ and $p(x_1,y)$, respectively, and add a condition that they are equivalent when the arguments agree:

$$\begin{align*}
b_1 &\wedge f_2=g_1\to b_2\wedge x_1=f_1\to f_1=f_2\\
  &\wedge x_1=x_2\to f_1=f_3\wedge f_1=x_2\to f_2=f_3\\
  &\wedge (x_1=x_2\wedge g_2=x_3\wedge f_3=x_4)\to g_1=g_2\wedge (z=x_1\wedge f_1=y)\to(b_1\leftrightarrow b_2)
\end{align*}$$


Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$

In my opinion complement of the L language is

$L^{C} = \{ w : |w|_{a} \neq  |w|_{b} \wedge |w|_{c} \neq  |w|_{d} \}$

I choose to Ogden pummping lemma word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p > n$

I would like to distinguish $c ^ {p}$. And then I have to have at least one distinguished symbol and the rest not distinguished and in my opinion it can't be pumped in any case because i can $c^{p}$ pumped to $c^{p + p!}$  so it isn't context-free

Do I think right?

I choose to Ogden pumping word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p > n$.

I am afraid you could not show that Ogden's pumping lemma cannot be applied to $s$ since $s$ belongs to the context-free language, $P_1=\{a^{k}b^lc^md^n\mid k\not=l\wedge m\not=n\}$, which is a subset of $L^C$.

Although your approach does not work, your conclusion that $L^C$ isn't context-free is correct.

Well, you are quite near the right approach.

Let $P_2=L^C\cap L(a^*c^*b^*d^*)=\{a^{k}c^mb^ld^n\mid k\not=l\wedge m\not=n\}$. We can show word $a^{p}c^{p}b^{p+p!}d^{p + p!}$ cannot be pumped as described in Ogden's lemma for $P_2$ when all of its $a$'s are distinguished. Hence $P_2$ is not context-free. Since $L(a^*c^*b^*d^*)$ is regular, $L^C$ cannot be context-free.

Exercise 1. Show $P_1$ is context-free. Show $P_3$ is context-free, too where $P_3=\{a^{k}c^md^nb^l\mid k\not=l\wedge m\not=n\}$.

Exercise 2. Show $P_2$ is not context-free following the approach given above.

Exercise 3. Show the complement of the following language is not context-free, $\{ w : |w|_{a} = |w|_{b} \vee |w|_{c} \not= |w|_{d} \}$.


DFA for w|w has a length multiple of 2 or 3 I am trying to create a DFA and a regex for this kind of exercise:

$A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine them, but it didn't seem to work cause I miss some cases for example $6,7$ or so. Any help would be gratefully received :D

Creating a state machine for each and combining the two is not a bad idea. To create a state machine accepting words having length N you can have each state represent the current length mod N.

After creating the two machines you can add a state having two epsilon transitions to the starting states of both machines. This gives a NFA accepting your language.

In a final stage you use the subset construction algorithm to convert the NFA you got into a DFA.


Dependency graph with general (AND/OR) dependencies This is similar to Is there such a thing as an "or" case in a dependency graph?

I am trying to represent a dependency graph where the dependencies for an individual node may be a general boolean function of other nodes.

For example, node A may be reachable from node B or node C.

I can't see how to represent this with a DAG. Is there way to represent general boolean dependencies in a DAG? If there isn't, what other sort of structure should I use?

Sorry for the crappy mspaint, but you could make an intermediate layer where the nodes in the middle represent each of the combinations of (A,B), like in a truth table:

~ABB~


Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode Consider the alphabet $Σ = \{1, +, =\}$ and the following language, $PLUS = \{ 1^m + 1^n = 1^{m+n} \mid m, n ∈ ℕ \}$. Prove with Myhill-Nerode that PLUS is not a regular language.

I know how I should use Myhill-Nerode here and how I should show that any two strings in the infinite set $S$ are distinguishable, but I am stuck at defining my infinite set S for this language. I tried $S = \{1^n \mid \text{$n$ is a natural number} \}$ but I don't think it works.

If $n \neq m$ then $1^m+1=1^{m+1} \in PLUS$ but $1^n+1=1^{m+1} \notin PLUS$.