The order of ε-transitions in NFA I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want to focus on $a$).

But when he demonstrates how to convert the NFA to an equivalent DFA, he says:
state $1$ goes to $\emptyset$ on $a$ because no $a$ arrows exit it. [...] Note that the procedure in Theorem 1.39 [on equivalence of DFAs and NFAs] specifies that we follow the $\epsilon$ arrows after each input is read.

So, if $\epsilon$-transitions happens only after some input (as the author defines), then in the initial state $1$, when $a$ is given, the NFA should 'die' as $\delta(1, a) = \emptyset$. The transition to state $3$ never happens, the NFA doesn't accept $a$. Doesn't the author contradicts himself?

I can think of couple possible explanations: 1) the very first transition of a NFA is $\delta(1, \epsilon)$ just by definition, 2) $a\epsilon=a$, so $\delta(1, a)$ = $\hat{\delta}(1, a\epsilon)$ = $\delta(1, \epsilon)\cup\delta(1, a)$, but then again the author said state $\{1\}$ goes to $\emptyset$ on $a$, not ${3}$

I think the answer is somewhat subtle and lies in Sipser's definition of what it means for an NFA to accept a string.

  Let $N = (Q,\Sigma,\delta,q_0,F)$ be an NFA, and $w$ a string over the alphabet $\Sigma$.
  Then we say that $N$ accepts $w$ if we can write $w$ as $w=y_1y_2\dots y_m$, where each $y_i$ is a member of $\Sigma_\varepsilon$ and ...

Compare this with his definition of what it means for a DFA to accept a string:

  Let $M = (Q,\Sigma,\delta,q_0,F)$ be a DFA and let $w=w_1w_2\dots w_n$ be a string where each $w_i$ is a member of the alphabet $\Sigma$. Then ...

Therefore, by his definitions, his NFA $N_4$ accepts $a$ as it can be written as $a=\varepsilon a$, and $\varepsilon$ and $a$ are both members of $\Sigma_\varepsilon$.


3CF 3-conjunctive form satisfiability I am self studying discrete math and I am going through MIT Mathematics for CS lecture notes but they do not have solutions available. I got stuck at Problem 3.14 (pages 64-65 of this document). The problem is about the construction, given an arbitrary propositional formula $F$, of a proposition $C(F)$ such that:

$C(F)$ is in 3-conjunctive form (3CF), i.e. it is a conjunction of disjunctions of at most literals (a literal is a variable or a negation of a variable);
$C(F)$ has at most 24 times as many occurrences of variables as $F$;
$C(F)$ is satisfiable iff $F$ is.

The idea is to introduce a new variable for each operator that occurs in $F$. For example, given
$$ F_1 = ((P \oplus Q) \oplus R) \vee (\neg P \wedge S)) $$
assign $X_1, X_2, O, A$ to the 4 operators in $F_1$, and define four constraining formulas:
$$ \begin{align*}
 C_1^1 &= X_1 \Leftrightarrow (P \oplus Q) \\
 C_1^2 &= X_2 \Leftrightarrow (X_1 \oplus R) \\
 C_1^3 &= A \Leftrightarrow (\neg P \wedge S) \\
 C_1^4 &= O \Leftrightarrow (X_2 \oplus A) \\
\end{align*} $$
and $C_1 = C_1^1 \wedge C_1^2 \wedge C_1^3 \wedge C_1^4 \wedge O$.

The questions are:

Why is $C_1$ satisfiable iff $F_1$ is satisfiable?
Why is each constraining formula equivalent to a 3CF formula with at most 24 occurrences of variables?
Generalize from the example to construct $C(F)$ for an arbitrary formula $F$.

For question 1, I don't see why $X_1$ is satisfiable.

I think question 2 is wrong, beacuse you can form a 3CF formula with at most 24 occurrences of variables, only if you have a 3-conjunctive normal form but here the author only says 3 conjunctive form.

(For 3CNF, 8 different triple terms can be formed using 3 variables with a total of 24 variables, For 3CF, 26 different single,double and triple terms can be formed with a total of ? variables.)

No idea about question 3.

First of all, I assume that $C_1^4 \equiv O \iff (X_2 \lor A)$ in accordance to $F_1$. Second, note that 3CF as defined in the exercise is equivalent to 3CNF. In the following, I will denote with $\phi_X$ the subformula of the given formula $F$ which has been assigned new variable $X$ by the construction. For example, $\phi_A=(\lnot P \land S)$ and $\phi_O = F_1$.
$\renewcommand{\models}{\mathop{|\!\!\!=}}\newcommand{\rmodels}{\mathop{=\!\!\!|}} \newcommand{\semeq}{\models\!\rmodels}$

Satisfaction equivalence

  I don't see why $X_1$ is satisfiable

$X_1$ is a single variable and thus trivially satisfiable (by setting it to $1$). The $C_1^i$ essentially take apart $F_1$ operator by operator, introducing new variables that have to evaluate to the same truth values as their respective subformulae. Using $\{O\}$ as clause of $C_1$ guarantees the statement, essentially (as "$O \semeq F_1$", given $C_1$).

Proof

Assume $F_1$ is satisfiable and let $\psi$ be a satisfying valuation of the variables. Construct $\psi'$ by extending $\psi$ with $\psi'(X) = \psi(\phi_{X})$ for $X \in \{X_1,X_2,A,O\}$. As a consequence, $\psi'$ satisfies all $C_i^1$. Because $\psi(F_1)=1$ by assumption, we have chosen $\psi'(O)=1$. Therefore, $\psi'(C_1)=1$.

Conversely, assume $C_1$ is satisfiable and let $\psi$ a satisfying valuation. Clearly, $\psi(O)=1$ and $\psi(C_1^4)=1$. Therefore, $\psi(\psi_O)=1$. Because $\psi_O=F_1$, we are done -- $\psi$ satisfies $F_1$. In order to be rigorous, we would have to iterate this argument top-down, following the structure of $F_1$, to unfold $X_2$ and then $X_1$ (in the general case, we would need a structural induction here).

Size restriction

The constraining formulae all have the same form and are small (three literals, two operators). You can transform those into equivalent 3CF formulae locally, i.e. ignoring the others. This conversion always yields formulae with at most 24 literals, that is at most 8 clauses. This can be shown by dull calculation.

Details

The general form of a contraining formula is $A \iff (A \circ B)$ for $\circ$ some logical operator. Let us transform it into 3CF using laws and rules of boolean algebra.

$\qquad \begin{align}
  C^i &\equiv X \iff (A \circ B) \\
      &\semeq\ [X \land (A \circ B)] \lor [\lnot X \land \lnot(A \circ B)] \\
      &\semeq\ [\lnot X \lor (A \circ B)] \land [ X \lor \lnot(A \circ B)]
\end{align}$

Now, for $\circ = \land$, we use both distributive and associative law resp. De Morgan's rule:

$\qquad \begin{align}
  C^i &\semeq\ [\lnot X \lor (A \land B)] \land [ X \lor \lnot(A \land B)] \\
      &\semeq\ [\lnot X \lor A] \land [\lnot X \lor B] \land [ X \lor \lnot A \lor \lnot B]
\end{align}$

This has three clauses (after padding with redundant literals, nine literals). For $\circ \in \{\lor, \to\}$¹ this works exactly the same way. You can proceed similarly for other choices of $\circ$, such as $\oplus$ or $\iff$, depending on which operators are allowed in your setting.

Generalisation

This is just a matter of writing down what the example does in general terms. Let $F$ an arbitrary propositional formula, w.l.o.g. without "negation chains"². Now do the following.

$\quad$ Let $i=0$.
$\quad$ Until $F$ is a literal, do
$\qquad$  Increase $i$ by one.
$\qquad$  Pick a subformula of $F$ of the form $L_1 \circ L_2 = \phi$ with $L_1,L_2$ literals.
$\qquad$  Let $C^i \equiv X_i \iff (L_1 \circ L_2)$.
$\qquad$  Replace $\phi$ with $X_i$ in $F$.
$\quad$ For all $j=1,\dots,i$, convert $C^j$ into 3CF by finite case distinction.
$\quad$ Return $[F \lor F \lor F] \land \bigwedge_{j=1}^{i} C^j$.

Note that $F = X_i$ after the loop. For intuition and implementation purposes, think of a formula as a tree: operators are inner nodes, leaves are literals. Above algorithm iteratively contracts subtrees of height two into leaves, collecting the $C^j$ as "mapping" from new variable to the removed subtree along the way.

Remember $A \to B \semeq \lnot A \lor B$.
We can always use $\lnot \lnot A \semeq A$.


Dividing unequal parts as equaly as possible I'm dividing up an animation project among 20 students. The whole film is 4955 frames long, so each student should have as close to 248 frames as possible. However, the scenes have an unequal number of frames that cannot be changed, and each student must have a whole scene (nobody can have .45 of a scene.) What is the easiest way to divide these scenes up to make sure each student gets as close to 248 frames as possible?

The original number of frames you have is 4955 frames and every student should receive as close to equal amount of frames as possible, the following is a solution I would suggest:

4955 frames / 20 students = 247.75

we take 247 (floor) and 248 (ceiling) as the possible number of frames that each student can get, now to figure out how many of those students should get 248 (the rest will get 247):

4955 mod 20 = 15

15 students will receive 248 frames and 5 will receive 247 frames

This works because .75 is 15/20 which therefore means 15 out of 20 got the ceiling value of the original division and the rest got the floor to equalise to .75


Assuming finite optimal cost of a specific LP, find an optimal solution directly Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$.

Derive a simple test for feasibility of this problem

Assuming the optimal cost is finite, develop a simple method for obtaining an optimal solution directly.

For the first part, I have  $\sum^n_{i=1} a_i x_i = b \iff \text {sgn}(b)=\text{sgn}(a_i)$ for some $i \in \{1,..,n\}$ or $b = 0$.
I have trouble obtaining this simple method for part two. Could someone help me out here?
I know $ -\infty < \sum^n_{i=1} c_i x_i$ and $\sum^n_{i=1} a_i x_i = b$.

Hint: Since there are $n+1$ constraints on $n$ variables, there is a solution in which all but one constraint are tight. You can calculate all these solutions explicitly ("on paper"), and choose the best one.


Underlying language to specify various types of logic There exist several different types of logic -- 1st order, 2nd and higher order with many different sets of inference rules possible.

What I'm having trouble understanding is what's the "underlying logic" we use to talk about the various different types of logic. For instance, if we were limited to thinking in terms of $i$th order logic, then we couldn't talk about $>i$th order logics but we can. Does this mean that the logic we think in terms of is more powerful than any $n$th order logic?

Sorry this is so vague but I'm having a hard time formulating my question exactly.

Edit: Turing machines cannot even decide all statements in first-order logic -- so does this imply some sort of relation between first-order logic and any other logic that we can think of (as humans are no more powerful than TMs)?

One answer is that we use English, but that's not what you're looking for.

To make the question more precise, let us ask what sort of formalism is useful for describing logics. This is still quite broad, because a logic has several parts: syntax, rules of inference, semantics, etc.

Syntax is pretty well understood and we know that the syntax of a language can be described in terms of formal grammar. That is a well developed theory. In any case, concrete syntax is rather boring from the point of view of logic.

It is far more interesting to ask what we need to specify the inference rules for a logic. Because a general logic can be just about any formal system, let us consider only traditional logics: classical first-order, intuitionistic first-order, second order, higher-order, simple type theory, dependent type theory and so on. One answer is that we should use a logical framework (LF). It is a variant of type theory designed in such a way that when we specify a logic in it we have:

  A statement in the logic is provable if, and only if, the corresponding type in the logical framework is inhabited.

This is desirable because it says that the logical framework is neither too weak nor too powerful.

In terms of logical strength LF is very weak: it is a dependent type theory with first-order kinds and $\Pi$'s. Speaking vaguely and in terms of logical connectives, this is a bit like using as our meta-theory a logic which has only $\forall$ and $\Rightarrow$ (and no equality).

There are implementations of logical frameworks, for instance Twelf. Of course, the point of such a tool is not just description of logics, but also the study of their meta-theoretic properties. Among the Twelf case studies you can find formalization in LF of cut elimination, the double negation translation, classical modal logic S5, and a bunch of more programming-language oriented examples.

One may also ask what formalism is necessary to specify semantics of a logic. The semantics of traditional classical first-order logic goes under the name of Tarski model theory and uses set theory, although it is well known that a much weaker system suffices (a fragment of Peano arithmetic). Other kinds of logic require different approaches, but in general it is the case that the meta-theory needed for the description of semantics is much less complicated than the semantics itself. For instance, the models of intuitionistic higher-order logic are elementary toposes. The axioms for an elementary topos are essentially algebraic, i.e., we can express all the axioms of an elementary topos with equations (we do not even need any logical connectives, just equations), see Section II.2 of Lambek and Scott's "Introduction to Higher-Order Categorical Logic".


Is this graph a hamiltonian graph? I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, iteratively. Every node added onto the graph and has 2 connections with the existing nodes (not necessarily with the initial 3 only) in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.

I'm asked, what is the maximum number of nodes in this graph that can be visited exactly once (except for the initial node), i.e., what is the maximum number of nodes contained in the largest Hamiltonian path of the given graph. (Okay, saying largest Hamiltonian path is not a valid phrase, but considering the question's nature, I need to find a max. number of nodes that are visited once and the trip ends at the initial node. I thought it can be considered as a sub-graph which is Hamiltonian, and consists max. number of nodes, thus largest possible Hamiltonian path).

I tried to apply Ore's Theorem but even for a small example graph, the Ore's Theorem might not be sufficient to tell if the graph is Hamiltonian even though it strikes you directly that it is Hamiltonian.

I thought I might use BFS since It's used to detect cycles in a graph: I needed to find the largest cycle which contained all the nodes in that cycle but given a large number of nodes, this approach might be slow and not desirable in my case since the timing will be crucial. For now this option is the last option if I can't come up with a solution.

After some thinking, I thought whatever the number of nodes will be, the graph seems to be Hamiltonian due to node addition criteria. The problem is I can't be sure and I can't prove it. Does adding nodes in that fashion, i.e. adding new nodes with 2 edges which connect the added node to the existing nodes, alter the Hamiltonian property of the graph? If it doesn't alter the Hamiltonian property, how so? If it does alter, again, how so?
Thanks.

EDIT

I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:

1 3
2 3
1 5
1 3

these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .

4th and 7th node are connected to the same nodes, thus lowering the maximum number of nodes that can be visited exactly once, by 1. If i detect these collisions (including an input such as 3 3) and lower the maximum number of nodes, starting from N, I believe I can get the right result.

See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.

I think counting the same connections while building the graph and subtracting it from N will give the right result? Can you confirm this or is there a flaw with this?

Let $k_P$ and $k_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=(1,2,3,4)$ and $P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.


How to make sense of this context-sensitive production in a textbook? (a typo perhaps?) In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach, an example of its production is given to illustrate the nature of context-sensitive grammar (page 3):

<thing> b ::= b <thing>

where <thing> is a non-terminal and b is a terminal.

I cannot see how this fits the form

$$αAβ → αγβ $$
(where $α$ and $β$ are strings, $A$ is a non-terminal and $γ$ is a non-empty string) for context-sensitive grammar unless the right hand side ends with $b$ as well:

<thing> b ::= b <thing> b

in which case we get $α=ε$, $β=b$ and $γ = b\; \text{<thing>}$.

Perhaps I haven't viewed it in the right angle? (Or is this a typo?)

First, they describe noncontracting grammars, and give an example: the one you are quoting.

Next, they write: equivalently, we can use a different restriction on grammars, and describe the context-sensitive grammars.

Chomsky proved the equivalence in 1963.


Name for concept: each pair of sets is either nested or disjoint Does this property have a name?

  Given a collection of sets $\mathcal{P}$, for   all pairs $A, B\in\mathcal{P}$, either $A\cap B=\emptyset$ or $A\subseteq B$ or $B\subseteq A$.

This concept could equally apply to monoids, groups, partial orders or other mathematical structures, with some adjustments to the definitions. For instance, for monoids and groups we would replace $A\cap B=\emptyset$ by $A\cap B=\{\epsilon\}$, where $\epsilon$ is the unit of the monoid/group.


How to generate regular expression for language of regular expressions? Alphabets = $\{0, 1, \epsilon, \emptyset, [, ], \cup, \circ, \star\}$
where $\circ$ stands for concatenation, $\star$ is kleene star, $\epsilon$ is empty string, $[$ and $]$ are brackets to be used for language to be generated.
Only those Regular Expressions to be considered which don't have nested brackets $[[]]$.

How to handle $[ \ ]$ in this problem ?
An expression can be -
$[1\star\star \cup 0] \cup [\epsilon \cup 1 \circ 0] \cup 1\star$

What would be a regular expression that describes the language of such regular expressions?

Edit -

I want to come up with Regular Expression for the Language of Regular Expressions as show in example above. One thing though is that the regular expression should not generate such expressions which contains nested bracket ( we don't want to consider that ) so $[1 \cup [0 \cup \epsilon]]$ is not valid and should not be generated by the Regular Expression.
What I have done and my understanding so far -
For single character Regular Expression would be $(0 \cup 1 \cup \epsilon \cup \phi)$. Be reminded that we are creating regular expression for Language of Regular Expressions. So $(0 \cup 1 \cup \epsilon \cup \phi)$ accepts these regular expressions - $0$ , $1$ , $\epsilon$ , $\phi$.

For $0\star\star$ kind of expressions - $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$ should work.

For $0\star\star \cup 1\star$ types we can have $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star} \bigcup\ (0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$

I am getting feeling that somewhere I need to use recursion. So I how to handle bracket $[ ]$ in this case ? How to accept those expressions which have brackets and they are not nested ?
If anyone can give me logic or direction to solve this problem competely that will also be ok.

Let us consider first a simpler situation, in which you have only one "atom" $a$, only one binary operator $\circ$, and no unary operator. The expressions you are captured by
$$
X (\circ X)^*, \quad X = a+[a(\circ a)^*].
$$
In order to get an actual regular expression, substitute $X$ (surrounded by parentheses) in the left expression.

Adding a postfix operation $\star$ isn't too difficult:
$$
Y (\circ Y)^*, \quad Y = A+[A(\circ A)^*]\star^*, \quad A= a\star^*.
$$

In order to get an actual regular expression, first substitute $A$ into $Y$, then $Y$ into the leftmost expression.

Finally, the expression you are looking for only differs in that there are several "atoms" and several binary operations:
$$
Z (\circ Z)^*, \quad Z = B+[B((\cup + \circ) B)^*]\star^*, \quad B= (0+1+\underline{\epsilon}+\underline{\emptyset})\star^*.
$$
Here $\underline{\epsilon},\underline{\emptyset}$ are the versions in your alphabet.


Raft algorithm: What's the data format of `term`? Time is divided into terms, and each term begins with an election. After a successful election, a single leader manages the cluster until the end of the term. Some elections fail, in which case the term ends without choosing a leader. The transitions between terms may be observed at different times on different servers.

In Raft algorithm, term is a limited period of time, and widely used in leader election, log replication.

What's the data format of term?
Is it composed of Unix timestamp and length ?
How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).

Note that we are focused on Raft algorithm.

What's the data format of term?
A term is just a positive integer.
Is it composed of Unix timestamp and length?
No, it is not. A term is just a positive integer. It is that pure and simple. In practice for reasons such as reporting or auditing, it might be helpful to record the time period when each term is valid. However, that is not an essential part of the algorithm at all.
How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).
Presumably, the question is seeking to confirm that terms can be maintained properly if term is based on time. However, as said above, this term can be considered as having nothing to do with time. So the best answer to this question should be that there is no need to be concerned with that kind of guarantee.

Here is a figure that shows how term is used in the logs in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable
Consensus Algorithm by the creators of Raft algorithm. Those numbers 1,1,1,2,3,3,3,3, etc in each log entry are the terms. Note that actual time is not mentioned anywhere in that figure, although a term does correspond to a limited continuous period of time.


Proving that Turing decidable languages are closed under reversal I need to prove that Turing decidable languages are closed under reversal. I have no idea on how I would prove this. Any suggestions or clues?

Suppose that you have a Turing machine $M$ that accepts a language $L$.
Construct a new Turing machine which, on input $x$, reverses its input and then passes control to $M$. The new Turing machine accepts the reverse of $L$.


Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language? In programming language theory, there are operations which are distinguished between static and dynamic, e.g. static/dynamic scoping, static/dynamic typing, ....

Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language?

Let me explain the above question and my thoughts and confusions about it.

Is it correct that a static operation means the operation is
performed at compilation time, and a dynamic operation means it is
performed at run time?
When an operation is performed by an interpreter, is it at
compilation time or run time?

It seems to me that people often says it is at run time.

But if I am correct, an interpreter first translates and then
executes a program, so to answer the question, do we need to specify
whether the operation is performed when the interpreter translates
or executes a program?
Does a static operation imply that the language under consideration
is implemented by a compiler but not by an interpreter?
Does a dynamic operation imply that the language under consideration
is implemented by an interpreter but not a compiler?

Thanks.

First, as a commenter mentioned, there isn't necessarily a clear general distinction between compilers and interpreters. A compiler is a program that takes source code, and produces a program which takes the input and produces the output. An interpreter is a program that takes source code and an input and produces the output. Under this definition, there are fairly trivial ways of converting an interpreter into a compiler and vice-versa (this is called the curry/uncurry operation in functional programming). There are also some more interesting general ways like partial evaluation.

What is true is that you may define the execution semantics of many programming languages may be defined on an abstract machine which loses much of the information in the original program. Most interpreters do this in some sense.

Second, keep in mind that all the various uses of "static/dynamic" are different things. For example, a static architecture is one where each component may only be connected to a fixed set of other components, while a dynamic architecture is one where some process connects them (e.g.: dependency injection). Most compilers are completely unaware of your application's architecture, so this question is pretty irrelevant for static/dynamic architecture.

In particular, for your question, "static typing" and "dynamic typing" are not really even on the same dimension. "Dynamic typing" is not a type system, although using it typically requires having an Any type. "Static typing" is usually just called "typing."

Anyway, from both a practical and theoretical perspective, anything an interpreter can do a compiler can do, and vice versa.


What problem is to the set packing problem, as the hitting set problem to the set cover problem? Wikipedia says that

  Set covering is equivalent to the hitting set problem

What problem is to the set packing problem, as the hitting set problem is to the set cover problem?

Is it that given the ground set $U$, and a collection of its subsets, $S \subseteq \mathcal P(U)$, find a $H \subseteq U$, so that $|H \cap S_i | \leq 1, \forall S_i \in S$, and maximize $|H|$.

What is the name of a set $H$ that satisfies $|H \cap S_i | \leq 1, \forall S_i \in S$  in this problem? I.e. the counter part of a hitting set in the hitting set problem?

Thanks.

Let $E$ be indicator matrix $e_{ij}=[u_j\in S_i]$ and $w\geq 0$ be boolean vector. What you have written is $Ew\leq 1$ where $(1,w)$ is being maximized. If we relax this to linear programming and get respective dual $E^tv\geq 1,\, v\geq 0$ where $(1,v)$ is minimized. Latter problem under constraints $u\in\{0,1\}^m$ would be Set Cover problem. To get respective Hitting Set consider new sets $S'_j=\{S_i:u_j\in S_i,\,i=1,\ldots,m\}$ and new ground set $U'=\{S_i:i=1,\ldots,m\}.$ The Set Cover reduces to Hitting Set for sets $\{S'_j\}$ over ground set $U'.$ So Set Packing and Set Cover are dual in some way. But  their optimal values do not coincide but they do coincide for their convex relaxations. More on this topic see e.g. in Wlliamson

You could also consider $H$ as being maximum independent families of sets $S_i.$ Let $F_h=\bigcup\limits_{h\in S_i}S_i,\,h\in H.$ These families are non-intersecting. Set Packing optimum is the lower bound for Set Cover.

As for $H$ interpretation. I suppose $S_i$ represents class of some useful things to take. Overall utility is maximized while the only one thing can be taken from each class.


Countability union of all finite and countably infinite sequences over finite alphabet Is the set of all finite and countably infinite sequences over $\{0,1\}$ countable?

From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=\{0,1\}$, hence $\Sigma^*$. (is this a good assumption?).

I later show that I can count each string in the following order: $0$,$1$ (length $1$), $00$, $01$, $10$, $11$ (length $2$) and so on.

However, I am very confused from the initial requirement "finite and countably infinite sequences". Does my method account for the countably infinite strings?

Your solution for proving that $\Sigma^*$ is countable is correct.
However the set $\Sigma^\omega$ of infinite sequences is not countable,
since it is in bijection with the set of subsets of $\mathbb{N}$, which is not countable. See this question.


How can I minimize floating point error when multiplying normal distribution PDFs? If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is

$$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$$

and the new variance is

$$v = \frac{v_1 v_2}{v_1 + v_2}.$$

However, if I use those expressions directly to combine several distributions sequentially, the floating point errors quickly pile up. Is there an algorithm for doing this stably?

While there is an entire subject that studies how to prevent or reduce floating point errors from piling up, it happens we have a shortcut here.

Let $\mathcal N(u, \sigma)=\frac{1}{\sqrt{2\pi\sigma^2} } e^{ -\frac{(x-\mu)^2}{2\sigma^2} }$ , the normal distribution with mean $u$ and standard derivation $\sigma$.
Suppose we are given $n$ Gaussian normal distribution $\mathcal N_i(u_i, \sigma_i)$ . What is the product of $n$ of them? It turns out,

$$\prod_{i=1}^n \mathcal N(\mu_i,\sigma_i)= s\mathcal N (\mu,\sigma)$$
where
$$
\frac1{\sigma^{2}} = \sum_{i=1}^n \frac1{\sigma_i^{2}}\,, \quad
\frac\mu{\sigma^2} = \sum_{i=1}^n \frac{\mu_i}{\sigma_i^{2}}
$$
and
$$
s =  (2\pi)^{\frac{1-n}2} \frac{\sigma}{\prod_{i=1}^n \sigma_i}\exp\left(\frac12 \left(\frac{\mu^2}{\sigma^2} - \sum_{i=1}^n \frac{\mu_i^2}{\sigma_i^2}\right) \right)
$$

If you use the above formula to compute, floating point errors should not be a concern any more.

Please note the reference you used is misleading in the sense the product function is not a probability distribution function.

Exercise. Prove the above formula for the product of $n$ normal distribution.


Does there exist a Reed-Solomon-like code over decimal symbols? A Reed-Solomon error-correcting code consisting of N symbols is guaranteed to detect up to N single-symbol replacements in an arbitrarily long input plus the ECC itself, and is also guaranteed to correct up to floor(N/2) single-symbol replacements in the same.

I can't claim to understand the math behind Reed-Solomon ECC, but I notice that all the implementations I could find operate on symbols in base 16, 64 or 256. This seems to suggest that 1024 etc. are also bases in which this scheme can operate with the right polynomial.

Is it possible to have an ECC scheme with exactly the above properties that operates on decimal symbols? Can Reed-Solomon be trivially adapted for this purpose?

(this question is prompted by my answer to a puzzling.SE question)

The property of Reed–Solomon codes that you mention is known as Maximum Distance Separability, and codes with this property are known as MDS codes. In coding theory the most popular type of code is a linear code, and these are only defined over alphabets which are prime powers. However, in the literature you can find some papers on MDS codes on arbitrary alphabets; I'll let you research that yourself.

For the specific case $N=1$, there is a very simple MDS code, namely checksum: you add to the original data a new digit whose value is the negated sum of the other digits (so that all new digits sum to zero). This code can detect any single error.


Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to $\log W$, where, I believe, $W$ is the size of the knapsack. Why is the size of the input related logarithmically to $W$?

Polynomial time means that the running time is bounded by a polynomial in the length of the input.  The running time here is bounded by $nW$.  $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a number up to $2^\ell$ so $W$ is potentially exponential in the length of the input, not polynomial.


Algorithm for generating heat maps I am looking to generate a heat map from some data. I have a value and a location (longitude and latitude). I understand generating a colour from the value, however I'm not sure how I would go about generating the matrix to use for this.

I figure it's best to place the location points into buckets essentially (so that I have the same number of buckets as pixels in my map) but I'm not sure how to calculate the values for the buckets where I don't have any readings.

Has anyone got any experience with this?

Thanks!

You have to interpolate the missing heat values. There's some mathematics that explains this pretty well (man, it's been a while) but, if I recall correctly, the correct physical way to do this (assuming no heat sources in the area being interpolated) is the following:

For each pixel for which there wasn't original data, assign the value of the pixel to the average value of all surrounding pixels.
Repeat (1) until no pixel changes its value by at least some $\epsilon$

To be safe, you should probably double-buffer this process, so that while doing the first step, changing the value of the first pixel doesn't affect the value for the second pixel. Example:

   5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0
   2.0 --- --- 1.0    2.0 3.0 2.5 1.0    2.0 2.6 2.6 1.0    2.0 2.8 2.5 1.0
   1.0 --- --- 3.0 => 1.0 2.0 2.5 3.0 => 1.0 2.4 2.4 3.0 => 1.0 2.3 2.5 3.0
   3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0

=> 5.0 4.0 4.0 3.0
   2.0 2.7 2.6 1.0
   1.0 2.3 2.5 3.0 ...
   3.0 3.0 2.0 4.0

Already the values are beginning to settle down a bit. This is easy and fast to automate, though naturally, you'll only get an approximation. See here and here for more information on the physics and mathematics behind this (and whether this is even applicable to your situation!!!)


The buckets of water problem Let's consider the following problem (buckets/pails  of water problem) (This problem may be known with different name. If does, please correct me).

Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. Suppose each bucket has a maximum capacity $c_i \in \mathbb{Z}$. This also can be written as a maxium capacity function $f:B \rightarrow \mathbb{Z}$ such that $f(b_i)=c_i$.

Let $g:B \rightarrow \mathbb{Z}$ be a function such that $g(b_i)$ is the current amount of water in bucket $b_i$.

Suppose that we can do the following operations.

1.Fill bucket $b_i$ from tap until its full, i.e. $g(b_i)=f(b_i)$.

2.Move water from bucket $b_i$ to bucket $b_j$ until $b_i$ is empty or $b_j$ is full.

3.Empty bucket $b_i$.

Now, the problem is given a number $m \in \mathbb{Z}$ to find a sequence of operations $s_1,...,s_k$ such that after $s_k$ we have a bucket with $m$ amount of water, i.e. $g(b_i)=m$ for some $i \in \{1,...,n\}$, or return that such sequence doesn't exist.

My questions are :

1.How to solve this problem? Is this problem NP Hard? If it is NP Hard, why? How to prove this?

2.What about the case when we are interested in the optimal $k$, i.e. we want minimum number of steps?

3.Does this is a well known problem? If yes, what is the known name for the problem and what good references exists for this problem?

I want to note that I fully understand the case of $n=2$, and I am interested in the generalization of $n$ buckets instead of just $2$. The $n=2$ case described in https://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle.

Edit: I now know how to prove that this is NP Hard problem. I want to know if there is an efficient algorithm for solving this (maybe some pseudo polynomial algorithm).

The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x_1,\ldots,x_n$ and a target $T$, consider $n$ buckets with capacity $C=x_1+\cdots+x_n$, initially filled with $x_1,\ldots,x_n$, and ask whether you can obtain a bucket filled with exactly $T$. You can prove by induction that all buckets are always with filled either with $C$ or with the sum of some (possibly empty) subset of the $x_i$s.


Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa? Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and language accepted by the PDA is union of these two?

For example, Consider the PDA shown below:-

I was trying to figure out the language accepted by this PDA and I got confused on the point that a string w=b is given as input, that will be popped out and the stack will be empty so would b be an element of language accepted by PDA or if we consider it only as acceptance by final state (considering that acceptance by final stack requires the bottom of stack symbol to be left in the stack ) the language accepted by this PDA will be :

{w| any prefix of w has number of a's more than number of b's}

However a string like "ab" can also be accepted if we allow both acceptance by empty stack and final state (The confusion here is strictly more a's or it can be equal too).

Since it was not explicitly mentioned, I'll assume that the PDA in the question is a PDA $P_s$ that has been defined for acceptance by empty stack. Let the language accepted by $P_s$ be $L_s = N(P_s)$.

There definitely exists another PDA $P_f$ which produces a language $L_f = L_s$  by defining acceptance on final state. This is why we say that:

  A language L has a PDA that accepts it by final state if and only if L has a PDA that accepts it by empty stack.

However, it is wrong to expect that the two PDA $P_s$ and $P_f$ are the same.


Prove that a language is regular I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible
to remove zero or more symbols from w so that just the string x remains. For example, the
following strings can all be obtained from 0110 by deleting symbols:

λ, 0, 1, 00, 01, 10, 11, 010, 011, 110, and 0110.

Let Σ = {0, 1} and let A ⊆ Σ
∗ be an arbitrarily chosen regular language.

Define
B = {x ∈ Σ
∗
| there exists a string w ∈ A such that x is obtained from w by deleting symbols}.

In words, a string is in B if you can obtain that string by first choosing a string from A and
then deleting zero or more symbols from that chosen string. Prove that B is regular.

I'm not able to prove it. Any help would be appreciated.

Hint 1: As $A$ is regular, it is recognized by finite automata. Try to modify this automata to make it recognize $B$.

Hint 2: Skipping "deleted" symbols might be handled by adding $\epsilon$ - transitions to the original automata in a proper way.


What does {a,b}* for DFA's mean? For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ should it reject the actual string $bbb$ because it does not contain an $a$?

$\{a,b\}$ is set notation. The alphabet of a language is the set of all possible symbol used in the language. You can substitute the typical $\Sigma$ for the full set every time.

$\Sigma^*$ (where $^*$ is the kleene star) is the set of all possible strings you can make with that alphabet. That includes strings that happen to not use a certain character.

Therefor $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ is equivalent to $\{w \in \Sigma^* : \Sigma =  \{a,b\} \text{ and } w \text{ contains } bbb\}$. But it skipped defining $\Sigma$ for terseness reasons.


Number of edges required to guarantee $K_3$ as subgraph I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 > \log 7$. In order to solve this I came up with a conjecture: if $m > n^{\log 7}$ then the graph has $K_3$ as a subgraph. This will easily solve the problem if the conjecture is true.

I am trying to argue by contradiction: Let $m > n^{\log 7}$ and assume there does not exist a $K_3$ subgraph. Then for any set of three vertices there are exactly 7 choices for how to connect them. However, I am stuck as to how to progress from here.

Does anyone see a way to prove this, or if the conjecture is even true. I'm also interested to see if the conjecture can be extended, i.e. if $m > n^{\log 2^k -1})$ does there exist a $K_k$ subgraph?

Hint: Matrix multiplication runs in time $O(n^{2.71})$. A relevant matrix is the adjacency matrix of the graph.

Actually, this has been improved several times in the past very. Recently, Le Gall improved this to time $O(n^{2.3728639})$. It is conjectured that matrix multiplication runs in time $O(n^{2+\epsilon})$ for every $\epsilon > 0$.


External consistency vs linearizability In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:

  One subtle thing about Spanner is that it gets serializability from
  locks, but it gets external consistency (similar to linearizability) from TrueTime [emphasis added].

What is the definition of external consistency, and how does it differ from linearizability?

External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document:

  For any two transactions, $T_1$ and $T_2$ (even if on opposite sides of the globe):
  if $T_2$ starts to commit after $T_1$ finishes committing, then the timestamp for $T_2$ is greater than the timestamp for $T_1$.


What is the range of possible IP addresses when expressed as decimal and hexadecimal? I know that there are $2^{32}$ different combinations of IPv4 addresses possible , if expressed in binary.

In decimal notation, they range from $0.0.0.0$ to $255.255.255.255$.

So are there $256^{4}$ possibilities if expressed in decimal?

And $16^{4}$ in hexadecimal?

Thank you.

The number of possible addresses is unaffected by the base you are using to write the addresses. The base is irrelevant to the problem of counting how many possible addresses there are.

Note that the $256^4$ figure you obtained is equal to $2^{32}$. In hexadecimal, the addresses range from $00.00.00.00$ to $\text{FF}.\text{FF}.\text{FF}.\text{FF}$, which gives $16^8 = 2^{32}$ possible addresses. To reiterate: the base only determines how you write the addresses, not the numerical values the address has. There are always $2^{32}$ distinct addresses.


Primitive Recursion and course-of-values recursion - examples? I ran into examples that I not trivially understand on course-of-values recursion,

  In defining a function by primitive recursion, the value of the next
  argument $f(n+1)$ depends only on the value of the current argument
  $f(n)$. Definition of functions by course-of-values recursion,
  $f(n+1)$ depends on value(s) of some or all of the preceding
  arguments $f(n),…,f(0)$. very basic examples of definition by
  course-of-values recursion are Fibonacci numbers...

My examples, from the computation course, wrote following $f_1$ and $f_2$ is Primitive recursive. I reproduce them here:

Let $g$ be a primitive recursive function,

$f_1(0)=c_1, f_1(1)=c_2, f_1(x+2)=g(x,f_1(x),f_1(x+1))$, and
$f_2(x)=c, f_2(x+1)=g(x,[f_2(0),...,f_2(x)])$ are primitive recursive.

I couldn't say how $f_1$ and $f_2$ are Primitive Recursive? any idea
to finding these are P.R.?

Edit 1: after the Yuval Hint the $f_1$ is easy, but for $f_2$ there is a problem, I try more than three days, but not capable to create an easy encode for $f_2$. any hint or idea?

The idea is to use some appropriate coding. A primitive recursive encoding of pairs is an encoding $\mathbb{N}^2 \to \mathbb{N}$, denoted by $\langle x,y \rangle$, such that the following functions are recursive: $e(x,y) = \langle x,y \rangle$, $p_1(\langle x,y \rangle) = x$, $p_2(\langle x,y \rangle) = y$. Coming up with a primitive recursive encoding of pairs is tedious but possible. Using such an encoding you can implement the first type of recursion in your question. The second type uses a more elaborate encoding scheme, which you can figure out on your own.

More explicitly, here is how you would implement a recursion of the first type:
$$
G(x,y) = \langle p_2(y), g(x,p_1(y),p_2(y)) \rangle \\
h(0) = \langle c_1,c_2 \rangle, \quad h(x+1) = G(x,h(x)) \\
f_1(x) = p_1(h(x))
$$
The trick in this case is that instead of computing the function $f_1$ itself, we compute the function $h(x) = \langle f_1(x), f_1(x+1) \rangle$; the value of $h$ at the point $x+1$ only depends on its value at the point $x$.

For the second type, similarly we compute the function $k(x) = [f_2(0),\ldots,f_2(x)]$ instead of $f_2$ itself; the value of $k$ at the point $x+1$ only depends on its value at the point $x$.


Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder? If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary shared by the entire catalog and therefore get much smaller file sizes?  Could this be expanded to work with images in general, i.e. to replace something like JPEG?

Are there existing compression systems that operate like this, where there is a large common set of bits transmitted and loaded before decompression, that has been built by analyzing many images?

For example, is there an existing computer science/machine learning research effort using sparse autoencoding over a large set of images and this concept of distributing a network derived from that encoding with the decompressor?

Note:  Coming back to this question and the answers, I see that it was primarily not understood because those that read it did not understand enough about new types of machine learning.

New techniques in machine learning, particularly deep learning or other advanced neural network systems, do have the potential make many existing data compression techniques outdated.  Or rather, we should expect that some more extensive research will result in these types of powerful encoders.  As of yet this is mainly speculative, and data compression scientists cannot conceive of them without fully understanding the power of the new neural network techniques.

you're focused on images so will construct a scenario that fits your question in the affirmative. imagine certain images that are not compressed via lossy compression eg a non jpeg-like algorithm. imagine the images are not compressed and stored in a straight pixel format. next suppose there are images that are composed of sub images in a vertical fashion. eg imagine a stack of images composing a larger image:

A
B
C
D

in the above crude diagram A,B,C,D are stacked images that compose a larger image, say E. now suppose that one creates a file that is concatenating files/images A,B,C,D,E. on a standard "lossless" dictionary compression algorithm like lempel-ziv, the algorithm will be smart enough to use A,B,C,D as long dictionary strings, and compose E out of those strings. (this depends on specifics like maximal dictionary word size etc, but it could be made to work). so in this admittedly rather contrived scenario, the answer is YES.

however, you are missing something about JPEG, it is typically lossy compression, and also images are generally a 2d format, whereas a lot of compression algorithms take advantage of 1d patterns like long strings. so this lossiness combined with the 2d format will mean that general compression algorithms will not really save much over the cost to store the original images (which generally are already compressed anyway).

therefore this is generally a negative answer overall, the overall idea of "compressing" using a "dictionary of images" is not really valid/possible/plausible and you can get a better idea of why by studying the mechanics/dynamics of compression algorithms in a more detailed way. on the other hand there are a wide variety of image compression algorithms that do in fact take advantage of redundancies in images. in JPEG for example the image is broken into squares and it can reuse common squares!


Is there always a Big Oh complexity strictly between any two others? I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if one can always find complexities between any other two.

Specifically, for any functions f and g with O(f) ⊂ O(g) does there always exist an h such that O(f) ⊂ O(h) ⊂ O(g)?

This isn't homework or anything. I'm just curious if anyone knows.

Yes: take a function in the middle, for some suitable definition of middle. You have a wide choice.

If $O(f) \subset O(g)$ (where the inclusion is strict), then $g \in O(g) \setminus O(f)$ (because if $g \in O(f)$ and $f \in O(g)$ then $\Theta(f) = \Theta(g)$). Take the geometric mean: let $h = \sqrt{f \cdot g}$ (since we're talking about complexity here, I assume the functions are positive).

Then $f \in O(h)$ and $h \in O(g)$ (if this is not immediately obvious, prove it using the definition of $O$), i.e. $O(f) \subseteq O(h) \subseteq O(g)$. If $O(f) = O(h)$ then $g = f \in O(f)$, which is not the case since we assumed $g \notin O(f)$. It remains to prove that $O(h) \ne O(g)$, and we'll have $O(f) \subset O(h) \subset (g)$.

If $O(h) = O(g)$ then $g \in O(h)$, i.e. there exists $A$ and $C \gt 0$ such that $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. Then $g(x) \le C^2 f(x)$ (take the square and divide by $g(x)$; again, I assume positive functions), thus $g \in O(f)$, which goes against our initial assumption. The hypothesis $O(h) = O(g)$ leads to a contradiction, which concludes the proof.


Computing MOD_4 function using MOD_2, OR, AND, NOT gates Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:

Let $x_1,\cdots,x_n$ be the input.  Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.

I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates.  Gate fan-in is unbounded.  Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.

Can this be done?  Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?

My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.

Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we would be able to solve our problem.

How do we "halve" the number of ones? The idea is to consider the running sums
$$ y_i = x_1 \oplus \cdots \oplus x_i. $$
Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.


Summation with floor in upper bound I'm learning about asymptotics and time complexity.
The algorithm I'm analyzing has a for loop that starts at $i = 1$ and ends at $\left \lfloor \sqrt n \right \rfloor$. The body is said to run in $n-i$ steps. I'm trying to do a summation from $i=1$ to $\left \lfloor \sqrt n \right \rfloor$ to come up with a Big Theta, but I am not sure how to deal with the upper bound of the summation. Thank you in advance.

You want to estimate
$$
S := \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} (n-i).
$$
You can start with the formula
$$
S(m) := \sum_{i=1}^m (n-i) = m \left(n - \frac{m+1}{2}\right).
$$
The formula for $S(m)$ is an increasing function for $m \leq n-1/2$ (as you can check by computing the derivative), and so $\sqrt{n} - 1 < \lfloor \sqrt{n} \rfloor \leq \sqrt{n}$ implies (for $n \geq 2$) that
$$
S(\sqrt{n}-1) < S \leq S(\sqrt{n}+1).
$$
Substituting, we get
$$
n^{3/2} - \frac{3}{2}n + \frac{\sqrt{n}}{2} < S \leq n^{3/2} - \frac{n}{2} - \frac{\sqrt{n}}{2}.
$$
Therefore $S = n^{3/2} - O(n)$. In particular, $S = \Theta(n^{3/2})$.

We can also get an exact formula:
$$
S := \lfloor \sqrt{n} \rfloor \left(n - \frac{\lfloor \sqrt{n} \rfloor + 1}{2}\right).
$$


How to prove a set has infinite cardinality? Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set.

I have tried proving set S as one to one corresponding to natural number set in binary form. like a = 0, b = 1. However, I am stuck in proving it since there are more than one "1", "01" = "1", same as other numbers.

A general way of showing this is proof by contradiction.

Assume (towards a contradiction) that the given set $S$ is finite, i.e.

$\qquad S = \{s_1, \dots, s_n\}$.
Show that there is an element $s \in S$ but for which $s \neq s_i$ for all $i \in [1..n]$.

One way to do this is to construct $s$ from $s_1, \dots, s_n$ explicity; that would be an instance of a diagonal argument.
Above step provides a contradiction, hence the assumption must be false: $S$ does not have this form.

Important: This only works if you make no assumptions whatsoever about the $s_i$ and $n$ (beyond what you know about $S$ already). If you do, you have not argued against all finite candidates for $S$.

Example

Show that $\mathbb{N}$ is infinite.

   Assume the opposite. Then, $\mathbb{N} = \{n_1, \dots, n_N\}$ for some $N$. Let $n = \max \mathbb{N}$. Then, by the definition of the natural numbers, $n+1 \in \mathbb{N}$ as well. But that contradicts that $n$ is the largest number in $\mathbb{N}$; the assumption must be false.


Compute the union of two sets between two endpoints minimizing communication complexity I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \{a_1, \ldots, a_{N_A}\}$, and $b$ is storing another set of fixed-length strings $B = \{b_1, \ldots, b_{N_B}\}$, with in general $A \cap B \neq \emptyset$.

Now, I would like to run a procedure that, using the communication channel between $a$ and $b$, results in both $a$ and $b$ storing $A \cup B$.

Both $a$ and $b$ can run an arbitrary amount of precomputation (e.g., sorting their sets, indexing them, organizing their elements in a tree...) but I would like the procedure to be as efficient as possible in terms of communication complexity.

The case I am most interested in is the one where $N_A \simeq N_B \simeq N$ with $N$ large and $|(A \setminus B) \cup (B \setminus A)| \ll N$. In that case, it seems to me like having the endpoints send their whole sets to each other should be an highly inefficient solution.

You can do this with $O(K \log N)$ bits of communication on average, where $K$ is the size of $|(A\setminus B) \cup (B\setminus A)|$, assuming you are willing to use a non-interactive protocol and are willing to accept a randomized protocol.

Let $H(\cdot)$ denote a randomized hash function.  Do binary search on $i$ to find the smallest $i$ such that $H(a_1,\dots,a_i) \ne H(b_1,\dots,b_i)$, i.e., (ignoring hash collisions) such that $a_i \ne b_i$.  Then you know that $a_1=b_1$, ..., $a_{i-1}=b_{i-1}$ and $a_i \ne b_i$.  Thus $a$ can send $a_i$ to $B$.  You can use a $O(\log N)$-bit hash function and the probability of a hash collision can be made exponentially small.  This takes $O(\log N)$ iterations of binary search, and in each iteration of binary search you send a $O(\log N)$-bit hash, so in all you send $O((\log N)^2)$ bits of information.  At the end we have sent one of the $K$ elements from $A$ to $B$.  Now you can repeat on the remaining elements (after discarding $a_1,\dots,a_i$ from both $a$ and $b$'s sets).  You repeat at most $K$ times, so this gives a protocol that requires sending $O(K (\log N)^2)$ bits.

You can reduce this to $O(K \log N)$ bits by using a shorter hash.  First do binary search using a 1-bit hash, to find the smallest $i$ such that $H(a_1,\dots,a_i)_1  \ne H(b_1,\dots,b_i)_1$, where $H(\cdot)_b$ denotes the first $b$ bits of the hash $H(\cdot)$.  This  takes $O(\log N)$ iterations.  Then, by using backtracking, you can find the smallest $i$ such that $H(a_1,\dots,a_i)_2  \ne H(b_1,\dots,b_i)_2$ , using on average $O(1)$ iterations.  Then find the smallest $i$ such that $H(a_1,\dots,a_i)_4  \ne H(b_1,\dots,b_i)_4$, and so on, in each stage doubling the length of the hash.  Each stage uses on average $O(1)$ iterations.  If you sum the series of the number of bits sent, it sums  to $O(\log N)$.

Thus, we get an improved protocol that requires sending $O(K \log N)$ bits on average.  It does require interaction between $a$ and $b$ to enable the binary search, and it is randomized.

I don't know whether there is a non-interactive protocol with similar complexity, or whether the protocol can be derandomized to achieve $O(K \log N)$ bits in the worst case rather than in the average case (or rather than an exponentially small probability of sending more than $O(K \log N)$ bits).


Can two different complexity classes be equal relative to an oracle? Example request Is there a known example of two complexity classes, $A$ and $B$, such that:

$A \neq B$;
there is an oracle $O$ for which $A^O = B^O$?

I strongly believe that there are such examples, as otherwise $P = PSPACE$ (note that $P^{PSPACE} = PSPACE^{PSPACE}$), but I was looking for an example of this.

Let $\mathsf{C}$ be a complexity class of your choice, let $\mathsf{O}$ be an oracle of your choice, and define $\mathsf{D} = \mathsf{C}^\mathsf{O}$. Then $\mathsf{C}^\mathsf{O} = \mathsf{D}^\mathsf{O}$, but it could happen that $\mathsf{C} \neq \mathsf{D}$. For example, you can take $\mathsf{C} = \mathsf{P}$ and $\mathsf{O} = \mathsf{HALT}$, the halting problem.

This might seem like cheating, but it's exactly the same answer as the one by Willard Zhan.


Is there a Zero-Knowledge proof for SAT? I know that SAT can be reduced to (3 vertex) Graph colouring, and there is a Zero-knowlegde protocol (ZKP) for graph colouring. However, I am interested in a ZKP that can be performed directly on a SAT instance, without graph colouring.
Is there a known ZKP for SAT, and if not how would you suggest coming up with one?

Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals.
Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.
Prover chooses a color in $\{1,2,3,4\}$ for each of the following:

Variable literals $V(x_i), V(\lnot x_i)$ ($2n$ colors in total).
Literals appearing in clauses ($3m$ colors in total): for each clause $C_j$ and literal $\ell$ appearing in it, $C_j(\ell)$.
Three additional values $a,b,c$.

Verifier makes one of the following checks:

The colors assigned to $a,b,c$ are all different.
For a variable $x_i$, the colors assigned to $V(x_i),V(\lnot x_i),b,c$ are all different.
For a clause $C_j$ consisting of literals $\ell_1,\ell_2,\ell_3$, the colors assigned to $C_j(\ell_1),C_j(\ell_2),C_j(\ell_3),a$ are all different.
For a clause $C_j$ and a literal $\ell$ appearing in it, the colors assigned to $V(\ell),C_j(\ell)$ are different.

If the formula is satisfiable, the prover acts as follows:

It chooses random colors for $a,b,c$. We call these colors $a,b,c$, and the remaining color $d$.
If $x_i$ is assigned true then we color $V(x_i)$ by $a$ and $V(\lnot x_i)$ by $d$, otherwise we color $V(x_i)$ by $d$ and $V(\lnot x_i)$ by $a$.
For a clause $C_j$, choose a satisfied literal $\ell$, assign $C_j(\ell)$ the color $d$, and assign the other two $C_j(\ell'),C_j(\ell'')$ associated with the clause the colors $b,c$.

It is not hard to check that this satisfies all constraints checked by the verifier. Moreover, since we chose $a,b,c,d$ at random, verifier can simulate the answers on her own, and so this is a zero knowledge protocol.
Finally, suppose that all potential checks of the verifier pass. Let $a,b,c$ be the colors assigned to $a,b,c$, and let $d$ be the remaining color. For each variable $x_i$, the variable literals $V(x_i),V(\lnot x_i)$ are assigned the colors $a,d$. We extract a truth assignment as follows: if $V(x_i)$ is colored $a$ then we let $x_i$ be true, otherwise it is false. Each clause $C_j$ is colored using $b,c,d$, and so some clause literal $C_j(\ell)$ is colored $d$. The corresponding variable literal $V(\ell)$ must be colored $a$, and so it satisfies the clause.


Simulations between Turing machines I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the first machine must be equal to O(1) steps of second machine. Do you have any idea, how to do this?

As I understand your question, the double-sided machine has a tape indexed by $\mathbb{Z}$ and the one-sided has a tape indexed by $\mathbb{N}$.

The question then boils down to finding a bijection f between the two sets st. $\forall z \in \mathbb{Z}: |f(z) - f(z+1)| < k$ for some constant k. Can you find such a bijection:

Hint: k = 3 is sufficient.


Difference between assignment, binding, and substitution? I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration, and citations from computer science wiki/articles/textbooks are welcome.

All three notions are related to variables. You can think of variables as named placeholders for some expression.

When introducing/declaring a new variable, you create a placeholder for an abstract expression (abstract in the sense that the variable does not represent a particular expression). Every variable declaration creates also a scope for that variable. A variable's scope is the part of the program that can refer to that variable. For example, in the line below (written in pseudocode)

add(a, b) = a + b;

variables a and b are being declared and their scope is the body of the add function. This means that any reference to a and b from within the body of add will refer to add's parameters. And any reference to a and b from outside the body of add will be meaningless (so you get a compilation error) or will refer to some other variables (which happen to have the same name, but have been declared outside of the function's body).

Altogether, this behavior is summarized in the sentence "Once a variable is declared, it becomes bound within its scope". Or, specific to this example, add binds the two variables a and b.

There's a third variable being declared in the pseudocode above and that is the add variable. So add is another placeholder, but this time the expression that add represents is not abstract, but a concrete value: it is the function that takes two expressions and returns their sum. Thus,

Assigning a value to a variable means that, while retaining the functionality of a placeholder, the variable does not represent some abstract expression any more, but an actual concrete expression.

The action of assigning an expression to a variable is closely related to substituting an expression for a variable. One difference is that variable assignment happens explicitly by the programmer at design time, while substitution is an internal mechanism of the language and happens at runtime.
Another difference is that, while variable assignment is itself an expression (it is part of the syntax of a language) and keeps the variable in scope, substitution is an action over expressions (it transforms expressions) and it entirely wipes away all occurrences of a variable from that expression. In other words, it eliminates the variable.

The relation between assigned variables and substitution is that all variables that have been assigned a value are internally substituted by their assigned values. This does not mean that substitution is triggered only through variable assignment. Another way is through function application (look up "beta-reduction" for more details).


When does the product automaton of two NFAs A and B not decide L(A) U L(B)? We are given the following task:

Let $\mathcal{A} = {}(Q_A,\Sigma, \delta_A, s_A, F_A)$ and $\mathcal{B} = {}(Q_B,\Sigma, \delta_B, s_B, F_B)$ be two NFAs and let their product automaton be defined as:
$\mathcal{A} \times \mathcal{B} = {}(Q_A \times Q_B,\Sigma, \delta, (s_A,s_B), F)$ with
$\delta = {}\{ ((p,q),\sigma,(p',q')) \mid (p,\sigma,p') \in \delta_A, (q,\sigma,q') \in \delta_B \}$ and
$F= {}(Q_A \times F_B) \space \cup \space (F_A \times Q_B)$

(So the accepting (combined) states are the ones where at least one of the two individual states of $\mathcal{A}$ or $\mathcal{B}$ is accepting.)

Give an example for two NFAs $\mathcal{A}$ and $\mathcal{B}$ so that their product automaton $\mathcal{A} \times \mathcal{B}$ does not decide the language $L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now the one thing that is by far confusing me the most (and what I want to focus on in this question) is the following tip that is given as well:

Tip: There is an example in which $\mathcal{A}$ only has one state.

I can't see how that could be possible, with the following reasoning:
If $\mathcal{A}$ only has one state - let's call it $q$ - this means two things:

$q$ is either accepting or it is not accepting
All of the transitions of $\mathcal{A}$ start at and directly lead back to $q$.

Based on 1. we have two cases.
Let's first consider the case that $q$ is accepting ($q \in F_\mathcal{A}$). Because of 2. it follows that $\mathcal{A}$ accepts every word $w \in \Sigma ^*$ (so $L(\mathcal{A}) = \{w \in \Sigma^*\}$).
Let $\mathcal{B}$ be an arbitrary NFA. Based on the definition of $F$ and the fact that $q$ is accepting it is clear that all of the states of $\mathcal{A} \times \mathcal{B}$ will be accepting as well, which implies that the product automaton also accepts every $w \in \Sigma ^*$.
This means that $\space L(\mathcal{A} \times \mathcal{B}) = \{w \in \Sigma^*\} = L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.
Now let $q$ be non-accepting ($q \notin F_\mathcal{A})$. Again, based on the definition of $F$ we can see that the accepting states of $\mathcal{A} \times \mathcal{B}$ are going exactly correspond to the accepting states of $\mathcal{B}$.
Point 2 implies that the transitions of $\mathcal{A}$ will "not have any impact on the transitions of $\mathcal{A} \times \mathcal{B}$", by which I mean that the product automaton is going to have the same transitions as $\mathcal{B}$ and therefore be isomorphic to $\mathcal{B}$, which again results in
$L(\mathcal{A} \times \mathcal{B}) = L(\mathcal{B}) = L(\mathcal{B}) \space \cup \space \varnothing = L(\mathcal{B}) \space \cup \space L(\mathcal{A})$
(since $\mathcal{A}$ doesn't accept any input, which means $L(\mathcal{A}) = \varnothing$)
This proof is trying to show that if $\mathcal{A}$ only has one state, then $\mathcal{A} \times \mathcal{B}$ will always decide $L(\mathcal{B}) \space \cup \space L(\mathcal{A})$.
Obviously, there has to be a logic fault in my thinking and in the proof above somewhere, which I can't seem to be able to figure out, so I'd really appreciate if anyone could point out what I'm missing.

The culprit is the fact that, in the presence of nondeterminism, automata need not have transitions to other states for the same input symbols.

Consider two NFA over the input alphabet $\{a,b\}$:

$$N_1 = (\{q_1\},\{a,b\},q_1,\delta_1,\{q_1\})$$

where $\delta_{1}(q_1,a) = \{ q_1 \}$ and $\delta_{1}(q_1,b) = \emptyset$

and

$$N_1 = (\{q_2\},\{a,b\},q_2,\delta_2,\{q_2\})$$

where $\delta_{2}(q_2,a) = \emptyset$ and $\delta_{2}(q_2,b) = \{ q_2 \}$

– that is, each of these automata has a single state, which is accepting, and a single transition, which is a loop on $a$ or $b$, respectively.

Clearly, $L(N_1)= \{ a^n \mid n \geq 0 \}$ and $L(N_2)= \{ b^n \mid n \geq 0 \}$. But the product construction will give us an automaton

$$N_{12} = (\{ (q_1,q_2 \}, \{ a,b \}, (q_1,q_2), \delta_{12}, \{ (q_1,q_2)\})$$

where $\delta_{12}((q_1,q_2),a) = \emptyset$ and $\delta_{12}((q_1,q_2),b) = \emptyset$, since there is no symbol $x$ such that both $N_1$ and $N_2$ admit an $x$-transition from their sole state.

Therefore $L(N_{12}) = \{ \varepsilon \} \neq L(N_1) \cup L(N_2)$.


NP-hard problems but only for n≥3 2-SAT is in P; 3-SAT is NP-complete.
Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete
Two-dimensional matching is in P; three-dimensional matching is NP-complete
Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

Are there other well-known or important examples that are similar, in that there is a family of problems with a natural parameter $n$, where the problem is known to be in P when $n<3$ and known to be NP-hard when $n≥3$?

In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) weakly perfect dominating, or (v) total perfect dominating, to name a few. Many of these problems also appear under different shorter names like "domatic number", "total domatic number", and so on. For more details, see e.g., the work of Heggernes and Telle [1, Table 1] (there's quite a bit of follow-up work as well).

Also, graph coloring is naturally linked to the classical and heavily-studied chromatic index (i.e., edge coloring) via the line graph. Further, deciding if a $k$-regular graph can be edge $k$-colored properly is NPC for every $k \geq 3$.

[1] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.


Why is a Tree a concrete data structure and not abstract? It seems to me that a tree or a heap is a concept and not a concrete implementation of some other abstract data structure.

For example a heap can be implemented with a table. Then why it is not considered abstract?

An abstract data type (ADT) is an interface: it describes the operations that can be performed and what their externally visible behavior should be.  There are typically many possible ways to implement that interface.

A data structure is an implementation of such an interface: it provides code or fully specifies the internal behavior.

A binary search tree is not an ADT; it specifies more than a list of supported operations (like insert, find) but also how they can be implemented (by a particular data structure in the shape of a tree).  A heap is not an ADT; it specifies more than a list of supported operations (extract-min, insert), but also how those operations should be implemented (by storing the elements in an array in a particular way and manipulating them in a specific fashion).

See also https://en.wikipedia.org/wiki/Abstract_data_type.


$O(n \log n)$ algorithm for disjoint segment visibility problem Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$ if it has a point which is visible from $P$.

My idea is to use a sweep half-line with one end-point on $P$, sort points clock-wise by degree and start from an end-point on the nearest visible segment (which I don't know how to find), rotate and detect one visible and some possible invisible segments at a time. All I can think of is $O(n^2)$ so far. Can anyone suggest an $O(n \log n)$ algorithm.

W.o.l.g. we could assume $P$ is the origin point $(0,0)$.

List the endpoints of all segments, represent them in polar coordinate $(\theta,\rho) \in [0,2\pi) \times [0,\infty)$ and sort them by their degree.
Imagine there is an ray from $P$ pointing to the right, we sweep it for one round (by gradually changing its direction $\alpha$ from 0 to $2\pi$).  Let $R(\alpha)$ denotes the ray from $P$ to direction $\alpha$.  We wonder what's the segments $R(\alpha)$ hits, and what's their order on $R(\alpha)$.
Find out all segments hit $R(0)$, and sort them by their order on $R(0)$.  Store them in a balanced binary search tree (e.g. red-black tree).
Iterate over the points we found (and sorted) in step 1:
Each point $(\theta,\rho)$ indicates a segment would start/stop hitting the ray $R(\alpha)$ when $\alpha$ increase to $\theta$.  Update the binary search tree accordingly.
The elements that once be the smallest one in the binary search tree are the segments visible from $P$.

It's easy to check that the runtime of above algorithm is $O(n \log n)$.


Regular expression for language with even number of 0's and 1's Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s?

If we only require an even number of $0$'s, the language $(1^*)\mid(1^*01^*01^*)^*$ works. But once there is a requirement on both $0$'s and $1$'s, I'm not sure how to do it.

Constructing regular expressions is usually more complicated than programming finite state automata. The standard way would be to construct a FSA and translate that one into a regular expression using standard techniques.

But if you prefer, it can be done directly, in two steps. Start by making two regular expressions $\alpha$ and $\beta$.

First $\alpha$ specifies strings with even number of $1$'s, and exactly two
$0$'s, one of which is the last symbol of the string.
Similarly $\beta$ specifies strings with odd number of $1$'s, and exactly two $0$'s,
one of which is the last symbol of the string.

Then build an expression for strings that have an even number of $0$ ánd an even number of $1$'s based on  $\alpha$ and $\beta$.


Process Types and names There seems to be a classification of processes in IT. For example, "business process" refers to the collection of tasks done by organization members / software systems to achieve a goal.

If a process is completely automated and carried out by software (no people involved) what is the process called? Say we have a Web service A and service B online and we have a process that automatically uses both in achieving a goal.

I googled for "Software process" but the results are not what I am looking for (e.g waterfall)

My apologies if this is not the correct forum to ask this question.
Thanks in advance

"Business process" can also be applied.  Or you could call it "automated process" or "automated business process" or "software processing" or "service" or any of a number of other things.

In other words: these terms do not have a precise mathematical/technical definition.  So, define your terms, and use them consistently.  This is not a technical question (and this site is better-suited for technical questions, not terminology questions).


Theoretical foundations of Divide and Conquer When it comes to the design of algorithms, one often employs the following techniques:

Dynamic Programming
The Greedy-Strategy
Divide-and-Conquer

While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C.

Firstly, I am aware of something that we (or rather, the prof) introduced  in a functional programming class,  called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows:

Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems.
Then, a D&C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where:

$P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.
$\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem.
$\mathcal{D}$ is a mapping  $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.
$\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution.

Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f_s(p)= \left\{
  \begin{array}{l l}
    \beta(p) & \quad \text{if $p$ is basic}\\
    \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise}
  \end{array} \right.$

where in the second line we use the notation $f(X) := \{f(x)  : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.

Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?

A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak
 (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)


Enumerate all non-isomorphic graphs of a certain size I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class.  In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ vertices.  How can I do this?

More precisely, I want an algorithm that will generate a sequence of undirected graphs $G_1,G_2,\dots,G_k$, with the following property: for every undirected graph $G$ on $n$ vertices, there exists an index $i$ such that $G$ is isomorphic to $G_i$.  I would like the algorithm to be as efficient as possible; in other words, the metric I care about is the running time to generate and iterate through this list of graphs.  A secondary goal is that it would be nice if the algorithm is not too complex to implement.

Notice that I need to have at least one graph from each isomorphism class, but it's OK if the algorithm produces more than one instance.  In particular, it's OK if the output sequence includes two isomorphic graphs, if this helps make it easier to find such an algorithm or enables more efficient algorithms, as long as it covers all possible graphs.

My application is as follows: I have a program that I want to test on all graphs of size $n$.  I know that if two graphs are isomorphic, my program will behave the same on both (it will either be correct on both, or incorrect on both), so it suffices to enumerate at least one representative from each isomorphism class, and then test the program on those inputs.  In my application, $n$ is fairly small.

Some candidate algorithms I have considered:

I could enumerate all possible adjacency matrices, i.e., all symmetric $n\times n$ 0-or-1 matrices that have all 0's on the diagonals.  However, this requires enumerating $2^{n(n-1)/2}$ matrices.  Many of those matrices will represent isomorphic graphs, so this seems like it is wasting a lot of effort.
I could enumerate all possible adjacency matrices, and for each, test whether it is isomorphic to any of the graphs I've previously output; if it is not isomorphic to anything output before, output it.  This would greatly shorten the output list, but it still requires at least $2^{n(n-1)/2}$ steps of computation (even if we assume the graph isomorphism check is super-fast), so it's not much better by my metric.
It's possible to enumerate a subset of adjacency matrices.  In particular, if $G$ is a graph on $n$ vertices $V=\{v_1,\dots,v_n\}$, without loss of generality I can assume that the vertices are arranged so that $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$.  In other words, every graph is isomorphic to one where the vertices are arranged in order of non-decreasing degree.  So, it suffices to enumerate only the adjacency matrices that have this property.  I don't know exactly how many such adjacency matrices there are, but it is many fewer than $2^{n(n-1)/2}$, and they can be enumerated with much fewer than $2^{n(n-1)/2}$ steps of computation.  However, this still leaves a lot of redundancy: many isomorphism classes will still be covered many times, so I doubt this is optimal.

Can we do better?  If I understand correctly, there are approximately $2^{n(n-1)/2}/n!$ equivalence classes of non-isomorphic graphs.  Can we find an algorithm whose running time is better than the above algorithms?  How close can we get to the $\sim 2^{n(n-1)/2}/n!$ lower bound?  I care primarily about tractability for small $n$ (say, $n=5$ or $n=8$ or so; small enough that one could plausibly run such an algorithm to completion), not so much about the asymptotics for large $n$.

Related: Constructing inequivalent binary matrices (though unfortunately that one does not seem to have received a valid answer).

Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's [1] and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as geng in McKay's graph isomorphism checker nauty.

[1]: B. D. McKay, Applications of a technique for labelled enumeration, Congressus Numerantium, 40 (1983) 207-221.


How to count the bits with a 1 bit error correction Hamming code? I've seen both ways of counting the bits when determining where to place the parity bits in a 1 bit error correction Hamming code. Some people count the bits starting from the left, others do it by starting from the right.

When to use one or the other? Does this depends on the Endian ordering?

Yes, it is about what bit-endianness you choose. Just make sure you are using the same interpretation on both ends.

(However if on 'Endian ordering' you meant byte order, that does not really apply here. As most Hamming codes do not transfer a whole number of data bytes, it is far simpler to think about the input as a stream of bits)


Why is using a lexer/parser on binary data so wrong? I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also context sensitive. This basically leads to having only one type of token, a token for byte.

Can someone explain why parsing binary data with a lexer/parser is so wrong with enough clarity for a CS student who hasn't taken a parsing class, but with a footing on theory?

In principle, there is nothing wrong.

In practice,

most non-textual data formats I know are not context-free and are therefore not suitable for common parser generators. The most common reason is that they have length fields giving the number of times a production has to be present.

Obviously, having a non context-free language has never prevented the use of parser generators: we parse a superset of the language and then use semantic rules to reduce it to what we want.  That approach could be used for non-textual formats if the result would be deterministic. The problem is to find something else than counts to synchronize on as most binary formats allow arbitrary data to be embedded; length fields tell you how much it is.

You can then start playing tricks like having a manually writen lexer able to handle that with feedback from the parser (lex/yacc handling of C use that kind of tricks to handle typedef, for instance).  But then we come to the second point.
most non-textual data formats are quite simple (even if they are not context-free).  When the counts mentioned above are ignored, the languages are regular, LL1 at worst, and are thus well suited for manual parsing techniques. And handling counts is easy for manual parsing techniques like recursive descent.


How did early computers handle variable word length? So quoting from the book: A History of Modern Computing (History of Computing)

The introduction of reliable core memory made it practical to fetch data in sets of bits, rather than one bit at a time. That meant a block size or word length, of from 30 to 50 bits.
Business-oriented computers could use shorter word length or a variable word length.
IBM 1401 used an extra bit appended to each coded character to indicate whether or not it was the last one of a word.
The 702 used a special character that signified that the end was reached.

I am not sure if I understand how variable word length works for any of these computers mentioned above.
For the case of IBM1401, what is meant by a 'coded character' and how can a single bit give the information that the end of a word is reached? (Assuming the computer runs on binary..?)
And for 702, what is meant by a 'special character'?

I've recently programmed an IBM 1401, so I can explain how its variable length words work.

For the motivation, remember that the IBM 1401 was a low-cost ($2500/month) 1960's computer for business applications on punched cards, for example payroll processing or inventory processing. The 1401 typically reads a file of punched cards, where each card holds fixed-length fields for one data record. The computer does some processing on each card, and prints out a report on the line printer, with fixed-length fields. Thus, it is convenient if the computer can easily manipulate fields of characters or numbers where each field has an arbitrary but fixed length.

The 1401's variable-width words are how it supports fixed-length fields. The programmer initializes the field lengths at the beginning of the program. Then a single "move" instruction will move a string field, regardless of how long it is. You don't need to loop over each character; the processor does that automatically. And you can add two numbers with a single "add" instruction, whether a 2-digit number or a 40-digit number. This is efficient, saves very expensive program memory, and is a good match for card-based applications.

Now, for the 1401's implementation of variable-length words (or fields). The IBM 1401 uses 6-bit characters (coded in BCDIC, precursor to EBCDIC), holding a text character or a decimal digit. (Note that the 1401 did decimal arithmetic, which worked well for business applications.) Each location in core memory has an additional "word mark" bit, which you can think of as a "metadata" bit. The programmer sets the word mark bit on the leftmost (high-order) character in a field. An instruction will typically process an entire field from right to left, until it hits a word mark, and then stops.

The important thing is that word marks aren't part of the 6-bit character. When you read a card, move a field, or so forth, the word marks are unchanged. Thus, the programmer can initialize the word marks once (with special word mark instructions), and then they stay put while you process the data.

Word marks are also used in the 1401 for variable-length instructions (1 to 7 characters), with a word mark after each instruction. One puzzle is that word marks aren't stored on the punched card, so how can you read in a program from cards? The solution is that when you load a program, you're actually loading and running a loader program that inserts the word marks as necessary for the program you actually want to run.

There is no limit on the size of a 1401 word, other than memory size. As a test, I created two 1000-digit numbers and multiplied them with a single "multiply" instruction. The computer churned away for literally a minute on this one instruction before generating the result.

The 1401 Reference Manual is online and provides more information, in case you didn't get enough here.


Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility? There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a classical computer if the number of operations needed to be performed for solving them is exceeding the total number of atoms in the observable universe. [1]

Now, it's pretty clear that in terms of space you have the total number of atoms in the observable universe as an upper bound, but how is it also an upper bound for computation time or number of instructions?

Update: A computer with memory of X bits can have a total of 2 to the power of X states, so in case X theoretically equals to the total number of atoms in the observable universe, the upper bound for computation time would actually be 2 to the power of the total number of atoms in the observable universe, which is a lot more than the total number of atoms in the observable universe. In fact, a computer can actually count the total number of atoms in the observable universe using only about 266 bits.

Let us assume an explicit range of the number of atoms in the universe to make sure that we are talking about the same thing.  It is estimated that there are between $10^{78}$ to $10^{82}$ atoms in the known, observable universe. In other words, it is a number between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion atoms.

Is the number of atoms in the universe large enough?

The common unit of computing performance is one floating point operation per second (FLOPS, flops or flop/s).

How much is the total computing capacity worldwide today? According to a popular estimate, "computing capacity worldwide was probably around 2 x $10^{20}$ – 1.5 x $10^{21}$ FLOPS, at around the end of 2015".
Extrapolating that by a generous 50% yearly growth rate, the total computing capacity worldwide today, around the end of 2018 is less than 6 x $10^{21}$ FLOPS.
Suppose you can run the total computing capacity worldwide today continuously for 100 billion years (which is much longer the life span of our universe as commonly estimated by physicists), you would have done a whopping 6 x $10^{21}$ (seconds) x 3.1536 x $10^{19}$ (Flop/s) $\approx$ 2 x $10^{41}$ FLOPs.
Suppose everyone of about 7.6 billion people on the earth is enjoying the same computing journey and there are another 100 billion planets like earth, we would have done a total of 2 x $10^{41}$ x 7.6 x $10^9$ x $10^{14}$ $\approx$ 1.5 x $10^{65}$ FLOPs.
However, that number is still much less than a billionth of the number of atoms in the universe! If each FLOP would count as 1, we need much more computing device and time to count the number of atoms in the universe!

Even given the impossibly optimistic yearly doubling of computing capacity worldwide, we would still need tens of years before our total computing ability to be anywhere near the number of the atoms in the universe.

Why choosing the number of atoms in the universe?

As Rick Decker indicated in his comment, that number is about the easiest way to say a big but fathomable number just about right to convey the message of practical un-computability. The vivid image of an immensely large universe filled with one of the smallest particles brings immediate understanding of an otherwise unfathomably big number to all walks of people.

Another nice huge number, Google, $10^{100}$, is sort of void of concrete meaning.

Further Topics

Which project is the largest computing project that has been completed or is going on?

Does FLOP capture all kinds of computing power? For example, quantum computing?

Why is the number of atoms is a really very small number compared to the number of combinations that we have to deal with routinely in many practical computations?


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

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

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

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

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

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


Is this DO LET sugar considered pure Lambda calculus and nullipotent / side-effect-free? I'm thinking these familiar concepts of DO and LET/LET* in the context of Lambda Calculus (LC).

LET is an abbreviation for this LC expression:

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

and LET* is an abbreviation for this LC expression:

(LET* a 1 b 2 e) = (λ a . (λ b . e 2) 1)

where e is the body of the function. LET* just enables to use former variable inside latter variable in the following way:

(LET* a 1 b a e) = (λ a . (λ b . e a) 1)

DO is an abbreviation too and can be used in conjunction with LET's to achieve same than LET*:

(DO (LET a 1) (LET b 2) e) = (λ a . (λ b . e 2) 1)

So I have three different shorthands to construct LC expressions. Now, my questions is that is this syntactic sugar throwing me out from pure LC (or functional programming in general sense) and am I introducing side effects by this syntax?

In a way it looks like it, but on the other hand these three shorthands are only abbreviations and they translate to Lambda Calculus expressions that are well defined and reducible as any LC expressions.

Anything that can be encoded in the pure lambda calculus, as you realize in the last paragraph, can not have side effects. Otherwise, the lambda calculus itself would be able to express those side effects as well.

However, note that your encoding looks a bit weird. For instance,

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

does not bind 1 to a and 2 to b. You probably want instead

(LET a 1 b 2 e) = (((λ a . (λ b . e)) 1) 2)

which does the correct binding. The other encoding should be fixed similarly.

I would suggest you "test" these encoding by performing $\beta$ steps. If you don't reach $e\{1/a,2/b\}$ something looks wrong.