Cardinality of ordered n-grams and subsets of those n-grams from a given set

Let $|T| = n$. Then

the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.
The total cardinality of all subsets for those $n$-grams is $$\sum_{k=1}^nk(n-k+1) = (n+1)\sum_{k=1}^nk - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

$\frac{3\times 4}{2} = 6$
$\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10 $


How does reducing the Halting problem prove the reduction cannot exist?

First, I think you're confused about some terminology.

You don't "prove the halting problem". In computer science, problems are computational tasks: you don't prove tasks; you perform them. Or, in this case, you you prove that there is no algorithm that decides the halting problem.
You don't "reduce the halting problem". A reduction is a conversion between two problems so, when you talk about reductions, you need to say what you're reducing from and what you're reducing to.

Second, you've confused which way this reduction is going. You're trying to prove that the blank-tape halting problem is undecidable, and you do this by proving that a problem that is known to be undecidable (in this case, the halting problem) reduces to it. That is, you prove that, if you could solve the blank-tape halting problem, you could solve the ordinary halting problem.

The reduction works like this.  Suppose there is an algorithm that decides whether a Turing machine that's given as its input halts when started with a blank tape.  The input to this algorithm is a description of the Turing machine (its "source code", if you like) and it somehow analyzes its input and says either "Yes, that machine halts when started with a blank tape" or "No, it doesn't."  We'll use this machine to determine if a given Turing machine $M$ halts when started with input $w$ (i.e., to solve the ordinary halting problem).  The new algorithm is this: we take the description of $M$ and the string $w$ and we produce a new Turing machine description $N$. The source code for $N$ says, "First, delete your input. Then, write $w$ to the tape, one character at a time. Then, rewind the tape to the start and do exactly what $M$ does (i.e., it then includes a copy of $M$'s source code)." Note that each different value of $M$ and $w$ will give a different machine $N$. Now, we just ask our algorithm for the blank-tape halting problem if $N$ halts when given no input, and that tells us whether $M$ halts when given input $w$.

That is, we've used the blank-tape halting problem to solve the ordinary halting problem. However, we know that the ordinary halting problem is undecidable so something must have gone wrong.  The translation of $M$ and $w$ to $N$ is completely fine: it's just some small edits to a machine's source code. So the impossible thing must have been the assumption that we have an algorithm for the blank-tape halting problem. There must be no such algorithm, which is the very definition of the problem being undecidable.


Here is how I understand your problem. We have a modulus $n$. A generalized interval $[\![a,b]\!]$ consists of $[a,b]$ if $a < b$, and of $[a,n) \cup [0,b]$ if $a > b$ (assume for simplicity that $a != b$). You want to know the size of the intersection of two generalized intervals $[\![a_1,b_1]\!],[\![a_2,b_2]\!]$.

One way to solve this is to decompose each generalized interval into a disjoint union of one or two intervals, and then compute the size of the pairwise intersections (which I will let you work out yourself), and sum them up.


Addition of vectors is commutative, so the order of moves is irrelevant. For example:

$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$

So a simple brute force method is to calculate the distance traveled for all subsets of the set of $n$ possible moves. There are $2^n$ such subsets, but you don't need to consider the empty set. So the size of your search space is actually $2^n-1$.


On graph isomorphism over exponential word sizes

Yes, this is known.  It has been shown that if you allow unlimited word sizes, then programs in the RAM model can compute arbitrary #PSPACE problems in polynomial time.  #PSPACE is a huge complexity class: it includes all of PSPACE and NP, and in particular, it includes graph isomorphism (and factoring).  Therefore, yes, graph isomorphism can be done in polynomial time if you allow unbounded word sizes.

This result was shown in the following research paper:

Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini.  A characterization of the class of functions computable in polynomial time on Random Access Machines.  STOC 1981.  https://dl.acm.org/citation.cfm?doid=800076.802470

The transdichotomous model was invented to eliminate this anomaly.


Undecidable predicate logic is decidable by people?

The author is incorrect. A consequence of Godel's incompleteness is that any sufficiently complex logic has statements that are true, but have no proof of truth.

If every statement had a proof or disproof, then we could iterate through all strings, check if it was a proof or disproof, and eventually we'd find one, making logic decidable. We know that this isn't the case, since this could solve the halting problem.

In the context of your question, this means there are valid formulas with no proofs of validity.

Humans have an excellent set of heuristics for proving things. We are good at seeing patterns and incorporating past knowledge. But ultimately we can't find proofs that don't exist.


Is program analysis part of programming language theory?

"Programming language theory" more or less includes everything you have listed, but of course there is overlap with other areas, such as software engineering, algorithms, security, human-computer interaction, and good old mathematics.

For instance, if you look at last year's programme of the Principles of Programming Languages (POPL) conference you will see not only topics about design, implementation and semantics of programming languages, but also about security, program analysis, papers about resource complexity, and many others.

In general I would say it good to be open about what "belongs" to a "research area". It is a shame to miss opportunities for new discoveries because of narrow-mindedness.


The proof you wrote in the question is faulty, because it uses the wrong definition of the Halting oracle. You tried to fix the proof by inserting the assumption $X(X) = X$, but that is not the way to do it. Here is the correct proof.
Definition: A halting oracle is a machine $H$ which takes as input a pair  $(M,I)$ where $M$ is the (description of) a machine and $I$ an input. $H$ always  halts and outputs:

"yes" if $M(I)$ halts,
"no" if $M(I)$ does not halt.

Theorem: A halting oracle does not exist.
Proof. Suppose $H$ exists. We shall derive a contradiction.
Let $N$ be a machine which does the following upon receiving an input $I$:

if $I$ is "yes" then $N$ loops forever,
otherwise $N$ halts.

Let $X$ be the machine which takes an input $I$ and then acts as $N(H(I, I))$. We now prove two contradictory facts:

$X(X)$ does not halt.
$X(X)$ halts.

To prove the first claim, suppose $X(X)$ halts. Then $H(X,X)$ outputs "yes", therefore $X(X) = N(H(X,X)) = N(\text{yes})$, but $N(\text{yes})$ does not halt. Therefore it is not true that $X(X)$ halts.
To prove the second claim, suppose $X(X)$ does not halt. Then $H(X,X)$ outputs "no", therefore $X(X) = N(H(X,X)) = N(\text{no})$, but $N(\text{no})$ halts. Therefore it is not true that $X(X)$ does not halt, so it halts. $\Box$.


The sum coloring problem can be reduced to this problem by having $n$ possible colors with weights $u_{ij} = n - i$. Sum coloring is NP-hard for interval graphs.

Source: https://en.wikipedia.org/wiki/Sum_coloring


Must $x$ and $y$ be different in a statement of the form $\forall x \forall y \cdots$?

For any formula $\varphi$ in which $x$ and $y$ are free variables, $\forall x \> \forall y \> \varphi$ quantifies over all possible values for $x$ and $y$. As a result, $x$ and $y$ may be different objects or they may be equal; for the statement to hold, $\varphi$ must hold in both cases.

Following this reasoning, a valid interpretation for your formula would be "an Italian is happy regardless of who wins the World Cup" (assuming "WC" stands for "World Cup"), with "Italian" standing for $x$ and "who" for $y$. Thus, $x$ is happy if they win the World Cup ($x = y$) but also happy if someone else does ($x \neq y$); hence "regardless".

The other statement can be expressed in predicate logic as follows:
$$\forall x (\text{italian}(x) \to (\text{winWC}(x) \to \text{happy}(x)))$$

In fact, this evaluates to the same truth value as the first formula precisely when you pick the same values for $x$ and $y$.

Assuming the most reasonable domain (i.e., persons in the world) and interpretation in this setting, you could argue there is an Italian which is happy only if the Italian national team wins the World Cup and is unhappy otherwise. Pick this person as your value for $x$ and an arbitrary non-Italian (e.g., German) person for $y$; then the second formula evaluates to true under this variable assignment (since $\text{italian}(x)$ is true and $x$ is happy if $\text{winWC}(x)$, that is, the Italian national team wins), but the first evaluates to false (since $x$ is unhappy if $y$'s team, that is, the German national team wins).


Recognizer for decidable language and words it doesn't halt on

The question is designed to test your understanding, so it's legitimate regardless of whether the details of $B$ are actually relevant. Maybe you're supposed to understand why they're relevant; maybe you're supposed to understand why they're not.

You've said that "recognize" is defined to mean that the Turing machine accepts all words in the language, and either rejects or loops on words not in the language.  This means that $A$ is some subset of $\overline{B}$ (the complement of $B$). Since $B$ is decidable, we know that $\overline{B}$ is also decidable.  So, $A$ is a subset of some decidable language.  Well, $\Sigma^*$ is a decidable language, so $A$ could be any subset of $\Sigma^*$. So it looks like $A$ could be any language at all! However, we have a little more information: $\overline{A} = \{w\mid M(w)\text{ halts}\}$, so $\overline{A}$ is recognizable.


Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

No. Exponential time is sometimes used to mean running times in $2^{\Theta(n)}$, and other times it is used to mean running times in $2^{\Theta(n^k)}$ for some constant $k>0$.

Your algorithm is exponential w.r.t. the second definition and superexponential w.r.t. the first.
In fact your algorithm takes time $2^{\Theta(n^3)}$, where $n = |S|$ (notice that $\frac{n!}{3! \cdot (n-3)!} = \frac{n(n-1)(n-2)}{6} =\Theta(n^3)$).


Understanding growth function of closed intervals in $\mathbb{R}$

Let the real numbers be $r_1 < \cdots < r_m$. The intersection $H \cap C$ could be of the form $\{r_i,\ldots,r_j\}$ for $1 \leq i \leq j \leq m$, or empty. There are $\binom{m+1}{2}$ of the first type, and $1$ of the second type.
For example, if $m = 1$ then the possible intersections are
$$ \emptyset, \{r_1\}, $$
if $m = 2$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_1,r_2\}, $$
and if $m = 3$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_3\}, \{r_1,r_2\}, \{r_2,r_3\}, \{r_1,r_2,r_3\}. $$


Is there a difference between total-ordering consistency and linearizability?

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

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


Mutable Object Values in a Functional Interpreter

The basic way of implementing state is to explicitly implement the state monad. In fact, if you want a pure interpreter, you will be forced to do so one way or another. Since you have objects, and very likely recursion on those, you probably cannot get away with a stack, you need a heap (beware of memory leaks).

Thus, your interpreter shall carry around three things:

The current runtime environment $\eta$, which assigns values to variables, and acts like a stack. When a new variable is declared, you push its initial value onto the runtime environment, and pop it when it goes out of scope.
The current state $s$, which maps locations to values. Thus a location is a primitive value. Since objects are the only mutable values, a location is the same thing as an object id (but not the object itself!). The state may be implemented in any number of ways, but it has to support lookup : state -> location -> object and update : state -> location -> object -> state, i.e., updates return the new state.
The program $p$ to be evaulated.

Because the run-time environment $\eta$ is like a stack whose discipline reflects the recursive calls of the interpreter to itself, you probably won't have any trouble with it (you called it the "lexical environment"). The main point is that you need to carry around the state s explicitly and thread it through the interpreter so that each interpreted command takes in the current state and return the new state. This way a command like

a.x = 3;

can be interpreted as:

In the runtime environment lookup the value of a, expect it to be a location L.
Modify the object at location L so that its field x is set to 3.

The second step is done with update, i.e., it takes in the current state and returns the new state.

You may wonder why the small-step evaluator should take in the whole program p and return a whole program p' yet to be evaluated (as opposed to taking in just one command). This is not strictly necessary (few things are), but it lets you implemented non-local control (exceptions) and loops. For example, to evaluate

WHILE B DO C DONE
P

we use the fact that this is equivalent to

IF B THEN
   (C ; WHILE B DO C DONE)
ELSE
   P

So you could evaluate a while loop by converting it to the above conditional statement. There are other, more efficient ways of course, but this is the essential insigth about while loops, i.e., they are a form of recursion.

The interpreter for boa in my Programming Languages Zoo is a bit like what you want, but I am cheating because ObjDict in type ob uses mutable references. However, this is the only place where mutable store is used by the interpreter, see lines 149 to 161 of eval.ml where Project dereferences and Assign mutates object attributes. Perhaps it is not too hard to change the source to get what you want.


Approximation factor shorthand clarification

That article, Linear-Time Approximation for Maximum Weight Matching calls "a matching $\delta$-approximate, where $\delta \in [0, 1]$, if its weight is at least a factor $\delta$ of the optimum matching."

That $\delta$-approximate maximum weight is, in fact, similar to the 2-factor approximation that is easy for you to grasp. When the optimization problem is to minimize some (positive) quantity, such as the minimum traveling distance or minimum vertex cover, then a 2-factor approximate might appear. When the optimization problem is to maximize some (positive) quantity, such as the case here, then a $(1-\frac15)$-factor approximate might be expected.

You may want to take a look at the performance guarantees of approximation algorithm or even what is a bicriteria approximation algorithm?


Extreme instancing for computer graphics

Yes, you are correct. What you suggest is a viable approach in 3D games. Popular game engines already do this, and have been doing this for some time. If you choose to do this through the vertex shader, you can improve performance in many situations.

For more information about animation:
How animation works in realtime graphics


Dynamic programming - maximize sum of functions subject to constraints

Let us read the objective again, "maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ where $\sum_{i=1}^{k}x_i\le k$."

The subproblems or the table entries are $DP[a][b]$ for all $0\le a\le k$ and $0\le b\le k$, where $DP[a][b]$ is the maximum value of $\sum_{i=1}^{a}f_i(x_i)$ where $\sum_{i=1}^{a}x_i=b$. The wanted maximum sum is the maximum of $DP[k][0],DP[k][1], \cdots, DP[k][k]$.

The base cases is $DP[1][b]=f_1(b)$ for all $b$.

How to reduce the computation of $DP[a][b]$ to smaller subproblems? The following equality is the critical observation, which is the reason why we have the first dimension "[a]" in the formulation of the subproblems. The other dimension "[b]" comes from the constraint $\sum_{i=1}^{a}x_i=b$.

$$\sum_{i=1}^{a}f_i(x_i) = \sum_{i=1}^{a-1}f_i(x_i) + f_a(x_{a}),$$
i.e., $DP[a][b]$ is the maximum of the following numbers,
$$\begin{aligned}
&DP[a-1][b] + f_a(0),\\
&DP[a-1][b-1] + f_a(1),\\
&\cdots,\\
&DP[a-1][0] + f_a(b).\\
\end{aligned}$$

Exercise 1. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le n$, where $n$ is a given integer.

Exercise 2. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i= n$, where $n$ is a given integer.

Exercise 3. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint that for all $j$, $|x_{j+1}-x_{j}|\le n$, where $n$ is a given integer.


Algorithm to build a "hand" calculation for riichi mahjong game

Pretty much any approach will be fine.  The trick is to focus on generating all possible ways to partition the hand into groups of size 4+4+4+2, then test each candidate to see whether it is valid.  If you've enumerated all possible ways in the first step, then you'll know you've found all possible variants/solutions.

Even a totally dumb, unoptimized brute-force approach will probably be fast enough: enumerate all partitions of the 14 cards into groups of size 4+4+4+2, and for each, check whether it's valid.  There are

$${14 \choose 4} \times {10 \choose 4} \times {6 \times 4} /6 = 525,525$$

different such partitions.  Therefore, you should be able to enumerate all partitions and for each check whether it satisfies the rules.

Of course there are likely much faster algorithms.  For instance, you can enumerate all possibilities for the first card in the first "set", then enumerate all ways to complete the first "set" (usually there won't be that many, given the restrictions on a valid "set"), then enumerate all possibilities for the first card in the second "set" out of the remaining cards, then enumerate all ways to complete the second "set", and so on.  In practice this will probably be even faster.

It's easy to find all variants with this kind of approach.  You just test each possible partition/grouping, and output each one that is valid.

As another optimization, it's easy to figure out the suit that you must use for the "pair".  Count the number of cards you have in each suit. For there to exist a valid combination, two of these numbers must be $0 \bmod 3$ and one must be $2 \bmod 3$.  The latter is the suit that the pair must come from.  Try all possibilities for how to choose the pair (from that set) -- there usually won't be that many possibilities, as there usually won't be many repeated cards in that suit.  For each such possibility, try all ways to divide the remaining 12 cards into 3 "sets".

As another optimization, after you've chosen and removed the pair, if you have a suit that contains exactly 3 cards, you know that if there is any valid combination, those 3 cards must be placed together in a set -- you have no choice (it's forced).  This further cuts down on the number of possible combinations you must examine.  If there's a suit that contains exactly 6 cards, there are only ${6 \choose 3} = 20$ ways to divide it into two groups of 3; you can check each candidate division to see which ones are comprised of two valid "sets".  These two cases will cover most hands.  The only difficult case is where there's a single suit that contains exactly 9 or 12 cards (after removing the pair), and you can fall back to enumerating all partitions for those (rare) hands, or devise alternative strategies for handling those specific cases.


Is possible to prove undecidability of the halting problem in Coq?

You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement.

Suppose decides_halt(M) is a predicate that says that machine M decides if its input is a machine that halts (that is, M is a program that for some machine m and input i, decides if m halts on input i).

Forgetting for a moment about how to prove it, the halting problem is the statement that there is no machine that decides the halting problem. We might state this in Coq as (exists M, decides_halt M) -> False, or maybe we prefer to say any given machine doesn't solve the halting problem forall M, decides_halt M -> False. It turns out that without any axioms these two formalizations are equivalent in Coq. (I've spelled out the proof so you can see how it works, but firstorder will do the entire thing!)

Parameter machine:Type.
Parameter decides_halt : machine -> Prop.

(* Here are two ways to phrase the halting problem: *)

Definition halting_problem : Prop :=
  (exists M, decides_halt M) -> False.

Definition halting_problem' : Prop :=
  forall M, decides_halt M -> False.

Theorem statements_equivalent :
  halting_problem <-> halting_problem'.
Proof.
  unfold halting_problem, halting_problem'; split; intros.
  - exact (H (ex_intro decides_halt M H0)).
  - destruct H0.
    exact (H x H0).
Qed.

I think either statement isn't too difficult to prove as a diagonalization argument, though formalizing machines, computability, and halting is probably reasonably challenging. For a simpler example, it's not too hard to prove Cantor's diagonalization theorem (see https://github.com/bmsherman/finite/blob/master/Iso.v#L277-L291 for a proof that nat -> nat and nat are not isomorphic).

The diagonalization above gives an example of how you might go about deriving a contradiction from an isomorphism between nat -> nat and nat. Here's the essence of that proof inlined as a self-contained example:

Record bijection A B :=
  {  to   : A -> B
  ; from : B -> A
  ; to_from : forall b, to (from b) = b
  ; from_to : forall a, from (to a) = a
  }.

Theorem cantor :
  bijection nat (nat -> nat) ->
  False.
Proof.
  destruct 1 as [seq index ? ?].
  (* define a function which differs from the nth sequence at the nth index *)
  pose (f := fun n => S (seq n n)).
  (* prove f differs from every sequence *)
  assert (forall n, f <> seq n). {
    unfold not; intros.
    assert (f n = seq n n) by congruence.
    subst f; cbn in H0.
    eapply n_Sn; eauto.
  }
  rewrite <- (to_from0 f) in H.
  apply (H (index f)).
  reflexivity.
Qed.

Even without looking at the details, we can see from the statement that this proof takes the mere existence of a bijection and demonstrates it to be impossible. We first give the two sides of the bijection the names seq and index. The key is that the bijection's behavior at the special sequence f := fun n => S (seq n n) and its index index f is contradictory. The halting problem's proof would derive a contradiction in a similar way, instantiating its hypothesis about a machine that solves the halting problem with a carefully chosen machine (and in particular one that actually depends on the assumed machine).


3-Approximation for General position subset

Find any line containing $\geq 3$ points. Delete all points on this line. Repeat.

This is a $3$-approximation, since on any line containing $m\geq 3$ points we must delete at least $m-2\geq 1$ points and we delete at most $2$ points too many. Meanwhile, the objective value decreases by at least $m-2\geq 1$.

If we know that the true objective value is $K$, then the instance obtained by deleting all points on this line will have objective value $\leq K-(m-2)$ and thus the recursive application will, by induction, return a solution removing at most $3(K-(m-2))$ points. Thus, we remove at most $3(K-(m-2))+m=3K-2m+6\leq 3K$ points.


Spacial complexity of an $O(2^N)$ time-complexity algorithm

The number of calls is indeed $O(2^{n})$. However, the memory footprint will be $O(n)$.

I guess the point is to clarify how the memory stack works during a recursion.
Perhaps the easiest way is to draw a recursion tree to follow the recursive calls.
Lets see how the size of the stack changes during these calls through a very small example.

Lets say you want to compute $f(1)$. Your tree will have only three nodes: the root ($f(1)$), a left child ($f(0)$) and a right child ($f(0)$).

Initially the stack is empty. We invoke the function with argument $n=1$.
We store what we need in the stack (e.g., temporary variables of this call).
This takes constant space, and for convenience lets say that stack size is now equal to $1$.

Next, we invoke the left child $f(0)$.
The stack size becomes 2.
But $f(0)$ returns immediately.
So the stack size is back to 1.

Next, we invoke the right child $f(0)$.
The stack size is now 2.
$f(0)$ immediately returns 1.
So the stack size is now back to 1.

Back at the root node, $f(1)$ has computed both the left and right child
and returns its value.
The stack size is now 0.

This was a very small example, but you see the stack size was never $3$ (equal to the size of the recursion tree) because the memory stack grows and shrinks as you traverse the tree.
For a larger example, you will see that when you visit a node (i.e. at some point of the recursion), any memory you used for the left subtree has now been cleared.
You only need memory for the nodes between the root and the current node.
Hence, the maximum size is equal to the depth of the tree which is $O(n)$.


Selection of parameters for genetic algorithm

First of all - the example doesn't seem well suited because you would probably use some regression or classical ML methods to solve this. Secondly - you are referring to a general problem of feature selection (Kira, Rendell, 1992) or attribute selection (Hall, Holmes, 2003) or variable selection (Guyon, Elisseeff, 2003) or variable subset selection (Stecking, Schebesch, 2005) or feature extraction (Hillion, Masson, Roux, 1988) or dimensionality reduction (Roweis, Saul, 200) or state abstraction (Amarel, 1968). This problem is relevant not only to genetic algorithms but for almost all machine learning techniques when dealing with high dimensional data.

Three cases can be distinguished here: the last instance of this problem known as state abstraction is usually related to process modelling (which suits your example, but not the GA context). The first three, i.e. feature selection, attribute selection or variable selection seem to be most relevant when taking your question literally. In this context a common solution is the mRMR approach (Peng, Long, Ding, 2005). From my experience it doesn't always work well with continuous data - however, mutual information can be substituted with other coefficients, like correlation for example. Another possible approach is to use cross-validation (Picard, Cook, 1984) for this. You can have multiple models each using different features, and by means of model selection with cross-validation techniques you choose the best model, which gives you the information on which features work best for the given task.

The feature extraction and dimensionality reduction cases allow to not only select initial features, but also their combinations. A well known example solution for this case is the PCA algorithm (Pearson, 1901), which produces the optimal, in terms of explained variance, set of features being linear combinations of input features.

Also note, that there are many models that handle feature extraction task by themselves. Some examples are: Growing Neural Gas Network (Fritzke, 1995), LASSO (Tibshirani, 2011), RFE SVM (Zeng, Chen, Tao, 2009), Decision Trees (Quinlan, 1986).

References:

Kenji Kira and Larry A. Rendell. 1992. A practical approach to feature selection. In Proceedings of the ninth international workshop on Machine learning (ML92), Derek Sleeman and Peter Edwards (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 249-256.
Hall, M.A.; Holmes, G., "Benchmarking attribute selection techniques for discrete class data mining," Knowledge and Data Engineering, IEEE Transactions on , vol.15, no.6, pp.1437,1447, Nov.-Dec. 2003
Isabelle Guyon and André Elisseeff. 2003. An introduction to variable and feature selection. J. Mach. Learn. Res. 3 (March 2003), 1157-1182.
Ralf Stecking, Klaus B. Schebesch. 2005. Variable Subset Selection for Credit Scoring with Support Vector Machines, Operations Research Proceedings 2005, Springer Berlin Heidelberg, (2005), pp.251-256
Hillion, A.; Masson, P.; Roux, C., "A nonparametric approach to linear feature extraction; application to classification of binary synthetic textures," Pattern Recognition, 1988., 9th International Conference on , vol., no., pp.1036,1039 vol.2, 14-17 Nov 1988
Nonlinear dimensionality reduction by locally linear embedding.
Sam Roweis & Lawrence Saul.
Science, v.290 no.5500 , Dec.22, 2000. pp.2323--2326.
Amarel, S. (1968). On representations of problems of reasoning about actions, Machine Intelligence, (3), 131--171
Peng, H.; Fulmi Long; Ding, C., "Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.27, no.8, pp.1226,1238, Aug. 2005
Richard R. Picard and R. Dennis Cook, Journal of the American Statistical Association Vol. 79, No. 387 (Sep., 1984), pp. 575-583
On lines and planes of closest fit to systems of points in space Philosophical Magazine, Vol. 2, No. 6. (1901), pp. 559-572 by K. Pearson
A Growing Neural Gas Network Learns Topologies, Bernd Fritzke, Conference: Neural Information Processing Systems - NIPS , pp. 625-632, 1994
Regression shrinkage and selection via the lasso: a retrospective, Robert Tibshirani, Journal of the Royal Statistical Society Series B, 2011, vol. 73, issue 3, pages 273-282
Xiangyan Zeng; Yen-wei Chen; Caixia Tao; Van Alphen, D., "Feature Selection Using Recursive Feature Elimination for Handwritten Digit Recognition," Intelligent Information Hiding and Multimedia Signal Processing, 2009. IIH-MSP '09. Fifth International Conference on , vol., no., pp.1205,1208, 12-14 Sept. 2009
J. R. Quinlan. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (March 1986), 81-106.


Corollary 1 in Fredman & Tarjan's paper states:

  A node of rank $k$ in an F-heap has at least $F_{k+2} \ge \phi^k$ descendants,
  including itself; where $F_k$ is the $k$th Fibonacci number ($F_0 = 0$, $F_1 = 1$, $F_k = F_{k-2} + F_{k-1}$ for $k \ge 2$), and $\phi = (1 + \sqrt{5})/2$ is the golden ratio.

Any node of rank 4 must have at least $F_{4+2} = 8$ descendants including itself, but the root node in the example has only 5. Therefore it could not have been created using Fibonacci heap operations.


Hyper parameter and complexity in $K$ nearest neighbors

First let's define what a hyper parameter is. In the context of statistical learning, a hyper parameter is a fixed constant that describes the prior distribution for a model's parameters. For example, if $X \sim \text{Binomial}(n,p)$ and $p \sim \text{Beta}(\alpha, \beta)$, then $\alpha, \beta$ would be hyper parameters where $n, p$ would be the "parameters" (I use quotes because $p$ is a random variable now).

$k$NN is  non-parametric in the sense that you aren't explicitly modeling your data as a function of underlying parameters. $k$ only describes how many neighbors to "learn" from. As $k$ increases the computational complexity can increase; however, it doesn't explicitly control the complexity of the model. An example where model size $k$ acts as a hyper parameter is linear regression. Imagine trying to determine a-priori which $k$ of the $N$ features you would like to select for inclusion in the model.

Given this, I would not say that $k$ describes $k$NN model complexity in the sense that typical Bayesian model selection is and therefore should not be viewed as a hyperparameter.


Why do many developers continue to rely on pseudo-random number generators?

Pseudo-random number generators and "true" random number generators serve different purposes, though there are some areas where they can overlap.

Pseudo-random number generators are useful when you need a large sequence of bits that appear to be uniformly distributed (or sometimes distributed other ways) that can be deterministically generated. "Unpredictability" is usually unimportant in these applications. In fact, it's often useful to use quasi-random number generators which are even more predictable. Being deterministic is often a valuable, if not critical, benefit. It means that you can easily repeat a specific sequence which is good for debugging and replication among other things. For example, if I want to replicate a database query that involves (pseudo-)"random" numbers, I can just ship a seed to the replicas and they can replay the transaction rather than requiring that I ship the entire sequence of numbers generated. It's also nice that pseudo-random number generators don't require any special hardware or anything at all beyond the ability to compute.

"True" random number generators are used when you need unpredictability, usually in an adversarial (and particularly security) context. You need some "secret" that you know that no one else knows even if they know everything about how you think and could predict anything you could do if they knew what you were observing.1 Producing entropy is time-consuming though. Most of the time, if a large number of "random" bits are needed, a source of entropy will be stretched using cryptographic pseudo-random number generators. Even doing this, hardware instructions take on the order of hundreds of cycles and are usually slower than optimized (non-cryptographic) pseudo-random number generators. If you don't need bits that are unpredictable by an adversary, there is usually little reason to use "true" random numbers.

1 Bits of "true randomness" are powerful things. Being able to "flip a coin" provides solutions to problems that are otherwise unsolvable.


I am assuming that you are interested in simple paths only. Otherwise the answer is trivial.

You can solve your problem in time $O(n)$. Let $s$ be your start vertex and $t$ be your target vertex.
Consider the graph as weighted where every edge has weight $0$.

Find any path $P$ from $s$ to $t$ in $G$. This takes time $O(n)$.
If $P$ does not exist then there is no path from $s$ to $t$.
Otherwise set the weight of each edge in $P$ to $1$ and find a shortest path $P'$ in the modified graph. This takes time $O(n)$ using a straightforward modification of Dijkstra's algorithm.

If $P' = P$ then there is a single path from $s$ to $t$ in $G$.
Otherwise there are at least two distinct paths from $s$ to $t$ in $G$.


Understanding the proof of the halting problem

The argument shows that if you can solve the blank tape halting problem then you can solve the halting problem. Since you can't solve the halting problem, it follows that you can't solve the blank tape halting problem. (Here "solve" means "decide with a program that always halts".)

It's true that the same argument shows that many other problems are undecidable. But if you try to prove that a decidable problem is undecidable this way, then something will go wrong. Try it out!


There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

  Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

  road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)


Decidability of equivalence problem with limit

You can still reduce $L_0$ to $EQ_{\lim}$. Given a Turing machine $m$, construct a Turing machine $m'$ which deletes its input and then transfers control to $m$, and let $n'$ denote a (fixed) Turing machine which halts on no input. Then $m \in L_0$ iff $\langle m',n' \rangle \in EQ_{\lim}$.


How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time?

It appears you are asking because you are interested in understanding the famous "PRIMES is in P" paper and why its algorithm runs in polynomial time.  Finding such an $r$ is exactly step 2 of their algorithm.

As was explained to you previously on Math.SE, the paper explains why its algorithm runs in polynomial time.  The explanation is terse and assumes the reader will be able to make the missing connections, but the key ideas are there.  If you keep reading in the paper it presents the crucial fact: the smallest such $r$ has size at most $r \le \max\{3, \lceil \log^5 n \rceil\}$ (see Lemma 4.3, which is just a few paragraphs after the statement of the algorithm).  Consequently, there is a very simple algorithm to find such an $r$: try each $r$ in turn, i.e., try $r=1$, then $r=2$, then $r=3$, checking each candidate value of $r$ to see if it satisfies the condition.  Output the first one you find that satisfies the condition.  Thanks to the fact in the paper, you'll only need to try $O(\log^5 n)$ many such $r$, which is polynomially many.  Moreover, you can check the condition for a given $r$ in polynomial time.  Thus, the total running time is polynomial in $\log n$.

In the future, if you have a question about some aspect of the paper, please tell us in the question what paper you are reading.  More generally, tell us about the context around your question and the motivation. Also, when asking about some aspect of a paper, I encourage you to read the entire paper before asking -- sometimes the answer to your question might be found later in the paper.


Does instruction which control unit fetch contain both what to do and where to do (in which unit of processor)?

In computer architecture (the current tag, but I wonder if it is really adapted), an instruction is whatever the computer architect decide to be.  It is the most basic bit string having a independent meaning.  Some instructions may be quite simple (add two registers and put the result in the first one), some may be strange (provide the most significant bits of a constant value used in the next instruction) and the boundary between being one instruction or several may be not that clear (you could consider the previous example and the instruction which follow it as a single instruction).

I don't know any processor which provides instructions like the one you are describing.  Those seems to me to be at the abstraction level of an operating system, not of a processor architecture.  It could be that mainframes provide such instruction (in the channel control part), but even there my guess is that it would need to be the combination of several more basic instructions.  That guess holds also for operating system.


How to delete a node from BST tree with 2 chidren?

You are right, in BST usually the case where a node has two children is reduced to the case where a node has one child.

Consider a node with two children. Swap this node with its predecessor in the BST (that is the rightmost node in the left subtree), or --totally symmetric-- swap with the successor (the leftmost node in the right subtree).

The node to be removed now has at most one child (in case we went for the predecessor it cannot have a right child).
If it has no children we delete the node, and we are done.

In case the node has a single child, we remove the node and replace it by its subtree. We again obtain a BST.

In your example we want to remove 5 and swap it with its predecessor 4. Now 4 is in the root, and 5 has left child 3. Finally we remove 5 and put its child 3 on its place. Now 3 is the right child of 2.

PS. This method is sometimes called "deletion by copying", because values are copied from one node to another. Some do not approve of this process for two reasons. First copying might be an expensive operation, and second references are lost (if another datastructure points to a node with a certain value). Instead one only changes the pointers.


Highest possible value of combinations of 5

I suggest you solve it with integer programming (you can download gusek for free for not too complicated computations).

Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s_{i,j}$
 for $(i,j) \in E$.

Define, for $i \in V$, $X_i$ the boolean variable equal to 1 iff you take hero $i$

Define additional real positive variables $Y_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.

You want to solve

$\max \sum_{(i,j) \in E} Y_{i,j}s_{i,j}$

such that $\sum_{i \in V}X_i = 5$

$\forall (i,j) \in E, Y_{i,j} \leq X_i $

$\forall (i,j) \in E, Y_{i,j} \leq X_j $

other formulations are possible. I like this one, since it only has $|V|$ boolean variables

If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.

Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.


Complexity classes of undecidable Turing Machines

The correct measure for the complexity of undecidable problems is the arithmetical hierarchy and its extensions. Undecidable problems sit outside all of the complexity classes defined by time or space constraints.


Having problem understanding the formal definition of NP

For Graph colouring problem

Input : A graph $G(V,E)$ and $k$.

Decide : Is $G$ $k$-colourable?

Certificate : A map $\phi : V \mapsto C $, where $C = \{R,B,Y,\cdots ,P\}$ is the set of colours and $|C| = k$.

For example for any $v \in V$, $\phi(v) = Y$ means $v$ has assigned color $Y$.

Example: let complete graph $K_4 (\{v_1,v_2,v_3,v_2\},E)$ is input graph and $k=4$ i.e. is it 4-colorable? A possible certificate in this case is $\{v_1(R),v_2(B),v_3(Y),v_4(P)\}$,($v_1(R)$ means vertex $v_1$ has color $R$),  which is polynomial in input size.

Now you can see that the size of $|\phi| \le p(|G|)$, where $|G|$ is a input graph size. As you have given a map $\phi$, now you can verify in polynomial time whether colouring is valid or not.


What restrictions apply to query and target vector encoding on fast-forward neural networks?

The inputs are not restricted to be 0 or 1.  They can be arbitrary real numbers.  In practice we often normalize or standardize the inputs so that they are in the range $[-1,+1]$ (or most of the input values are in that range), but even that is not required, and even then, they can be any real number in that range.

The outputs are also real numbers, and they can be any real number: not limited to 0 or 1, and not limited to a particular range.  (In some applications we interpret the outputs using the softmax function -- i.e., we postprocess the outputs of the neural network using another function -- which rescales them to get one likelihood value per output that's in the range $[0,1]$, but this is not mandatory and will depend on the specific application setting.)


Smoothed analysis of the Partition problem

Smoothed analysis, as I have seen it, has typically been used for analyzing optimization problems, not decision problems.  The partition problem is a decision problem, which introduces the challenge you mentioned.  Perhaps one could consider the optimization variant of the partition problem: given $n$ numbers with a sum of $2S$, find the subset whose sum is as close to $S$ as possible.  I don't know whether the smoothed complexity of that optimization problem would be interesting or illuminating, but it eliminates the problems you articulate in the question.


First of all let us talk about the cost measure .
The cost C is calculated actually in terms of the number of disk access made in order to compute the join.

A block is defined as the smallest unit of memory which is transferred from disk to main memory during a disk access.

A page is a contiguous block of memory. (set of blocks)

Anther term associated is the blocking factor. which is the number of records which can be present on a single block of memory.

Suppose we need to compute the join of relation RxS
The first method we first bring the relation R in the main memory which take n(R) disk accesses (n(R)= number of records in the relation R). Note that records and tuples mean the same thing. For each record in relation R we make another disk access to bring a single record of relation S to check the join condition this gives another n(r)*n(S) disk accesses.
the total being n(r)+n(R)*n(S)

We can achieve some improvement checking the tuples stored on one page of relation S  for each record in relation R.

In Block nested approach each block in the inner relation S is read once for each block in the relation R
which gives you the desired cost


Sampling Multiple Times From a Markov Chain

One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps.

I don't know whether your first proposal gives the correct distribution in all cases.  You can consider the Markov chain $A \leftarrow B \rightarrow C$ with self-loops $A \to A$ and $C \to C$ and more complicated examples in that vein.

Your second proposal doesn't give the correct distribution.  The $T$th and $T+1$th state are highly correlated: for instance, they will always be adjacent -- something that wouldn't be true of 10 independent samples from the steady state distribution.


Quantification in pumping lemma for regular languages

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

The pumping lemma states that $p\implies q$.

To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

$xy^iz\in L$ for all $i\ge 0$
$|y|\gt 0$
$|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it  implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.


Intuition for Church-Turing thesis for Turing machines

Imagine you are performing a computation by hand with a pencil and a stack of paper. [1] There is a limit on how many pieces of information you can keep in working memory at a time (sometimes claimed to be seven plus or minus two). So when you can't keep everything in your head, you write some of it down on a sheet of paper. And when you fill up a sheet, you put it in a pile for later reference and pull out another sheet. But there is a limit on how many sheets of paper you can look at at a time, too; you will have to flip between sheets as you work.
Turing machines are an abstraction of this idea of local computation. A Turing machine can write down as much auxiliary information as it wants, but it can only look at a finite amount of it at a time. A Turing machine head is like your brain's working memory—it can only store so much stuff before it has to write it down somewhere to avoid forgetting it.
The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations. That is, any physically realizable computation can be broken down into a series of steps, each of which operates on $O(1)$ bits of information; there is no primitive operation that requires, say $O(n)$ arguments and cannot be reduced to operations with fewer arguments. [2] Or: anything you can compute in the real world can be computed given an unlimited stack of pencils and paper.

[1] Recall that the word "computer" in Turing's time referred to a human profession!
[2] A primitive operation that accepts an unbounded number of arguments is exactly what the oracle in an oracle Turing machine provides—hence why oracle machines can be more powerful than Turing machines.


There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics to search more promising moves first.
The eight queens puzzle is the typical example of backtracking in a much simpler setting, the cited page has a sample Pascal program (readable enough for any C-savy person). Dijkstra wrote a highly detailed discussion of the program, see his "EWD316: A Short Introduction to the Art of Programming".


UPD: O$(N \sqrt N)$ solution
Bucketing
Let's split the array into blocks of $\sqrt N$ size.
For each block let's keep all values in it in an array.
Let's also keep pairs $(Number, Count)$, counting the occurrences of each number, present in the block. We will also keep these pairs in an array, sorted by the $Number$. We also keep partial sums for this array, for each $Number$ indicating number of numbers less than this, in this block. (In the beginning this can be precalculated in $O(N log N)$ ).
Let's also keep a value $Mod$, that indicates that in reality all numbers in these block are not as they are saved, but actually bigger by $Mod$.
Last, for each block let's keep a pointer in the array of pairs, pointing to the first $Number$, such that $Number+Mod$ is more than or equal to the current value of the median.
Answering query
Let's count total number of values in all blocks less than the median - simply sum all partial sums for pointers.
Let's also count number of values equal to the median - by summing second components of pairs, at which our pointers point.
This takes $O(1)$ for each block and therefore $O(\sqrt N)$ for each query.
If we found out that total number of values less than or equal to the median is less than ${N \over 2} + 1$, we may need to shift some of the pointers forward, since the value of median then increases by 1.
In total each query we will at most need to shift  $\sqrt N$ pointers by 1, making in total $O(N \sqrt N)$ shift forward.
Updating query $(A,B)$
For blocks fully covered by the interval we can simply increase the $Mod$ values. After that some of the pointers may need to be shifted backward by at most 1, to keep their invariant (pointing at first number more than or equal to the current median). Total number of shifts backwards won't exceed $O(N \sqrt N)$ for one query.
For two blocks half covered by the query let's update values in the array in the naive way:
First, increase each of them by $Mod$ and also increase each value in our sorted array of pairs by $Mod$. Clear $Mod$.
Then let's create a hash map of all values increased by 1 in the query.
Then let's loop through array of pairs and for each $Number$ we decrease it's $Count$ by an appropriate number in the hash map, and create an entry in the second array of pairs, indicating $(Number + 1, Count)$. Once we finish, we will have all numbers in our block presented by 2 array of pairs, both sorted by the first components. Then we can merge these to in the $O(\sqrt N)$.
Finally, recalculate partial sums for this new merged array and naively find the position of the pointer by looping through it.
Seems to be it, $O(\sqrt N)$ per query but I wouldn't want to code it;)
================================================================================
Here is an idea for $O(N \sqrt{N} log N)$ solution.
Observation: (Intuitive, Beautiful, Tested but Unproven):
By increasing the subarray by 1 we can only increase the median

By 0 or 1, if array has odd length
By 0 or 0.5 or 1, if array has even length

I tested this hypothesis extensively locally.
Let's assume $N \approx K$.
Bucketing
Then let's split our queries into $\sqrt N$ groups $\sqrt N$ each. At the beginning of each block we do the following:

Calculate the median. Let it be $M$.
Let's introduce $L=M-\sqrt N$, $R=M+\sqrt N$, $LC$ - number of elements less than $L$ in the array.
For each value $X$ between $L$ and $R$ create a sorted list of all positions, in which value $X$ currently resides. We will keep each list as an implicit cartesian tree (data structure that allows cutting and merging subarray in $O(log Length)$. Example - STL Rope). This is the most computationally expensive step of the above and it takes $O(N log N)$ in the worst case, making overall complexity of these steps for all query groups $O(N \sqrt{N} log N)$.

Answering
When we will want to find the median, we will go through all values of $X$ between $L$ and $R$ and calculate sum $LC + CN(L) + CN(L+1) + CN(L+2)+ \cdots$ until it exceeds ${N \over 2} + 1$ for some value $L+t$ which will be new median. (Or average of two consecutive values). Here $CN(L)$ denotes number of items in the sorted list that corresponds to value $L$.
Updating
When we will want to update our structure after the next query ($A$, $B$), we will do the following:

For each $X$ between $R$ and $L$ find subarray that contains all values between $A$ and $B$ (if we, for example, keep in the node of implicit cartesian tree minimum and maximum values in the corresponding subtree, we can find the appropriate indexes of subarray in $O(log N)$).
Erase the corresponing subarray and insert a subarray, obtained the same way from the previous list.
For list with numbers equal to $L$ we don't insert anything since we know that all values less than $L$ will stay less than $L$ in the scope of next $\sqrt N$ queries so we simply add them during summation as variable $LC$
Splitting and merging implicit cartesian tree requires $O(log N)$ operations, we have $O(\sqrt N)$ cartesian trees, and our actions happen for each of $O(N)$ queries, leaving total complexity at $O(N \sqrt N log N)$.

Finally, we can save all queries in current block and then update our array, for example in $O(N + \sqrt N log \sqrt N)$ time by sorting queries and using scanline.
Afterthoughs:
I wonder if, since median can only increase by 1 or 0.5, we can solve this problem in $O(N log N)$ time somehow.
Also, same as in the answer above, it may be possible that $O(N \sqrt N log N)$ can be optimized to $O(N log^2 N)$, although it is not obvious to me, how.


Space(n) not closed under Karp reductions - what about NTime(n)?

You're not mistaken. The reason NP is different is that it's defined as the union of $NTime(n^k)$ for all $k \geq 0$, so the set of upper bounds on the running time $s(n)$ is closed under substituting polynomials.


Algorithm that finds concise representations of sets of pairs using Cartesian products

For a given set $S$ of points, we construct a bipartite graph $B=(X\cup Y,E)$ such that there is an edge $(x,y)\in E$ iff there is a point $(x,y)\in S$.
The biclique decomposition problem asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edge set $E$ of $B$. Since a biclique in $B$ corresponds to a structure defined in this problem, an algorithm that solves the biclique composition problem also solves this problem.

Conversely, we can also transform the biclique decomposition problem into this problem as follows. Given a bipartite graph $B=(X\cup Y,E)$, where $X=\{x_1,x_2,\ldots x_p\}$ and $Y=\{y_1,y_2,\ldots y_q\}$, we create a set $S$ of points such that $(x_i,y_j)\in E$ iff there is a point $(i,j)\in S$.
Consequently, the problem is equivalent to the biclique decomposition problem. However, the biclique decomposition problem is NP-hard, and therefore it is unlikely to solve it efficiently on general bipartite graphs.
Note that the problem is equivalent to ``biclique cover'' if the structures are allowed to be overlapped, i.e., a point can be in more than one structure.


Complexity of edit distance with block operations

What it looks like you are after is the Block Swap edit distance. Here is a paper outlining a polynomial time solution to this problem, An Edit Distance Algorithm with Block Swap . I cant recall the exact time complexity they give in the paper, however it is outlined in there.


Looking for a formal grammar for $\{ a^{2^n} \mid n \in N\}$

(Answer adapted from an almost identical question on StackOverflow, because it really belongs here.)

It's certainly possible to write a grammar for this language, but it won't be a context-free grammar. That's easy to demonstrate using the pumping lemma.

The pumping lemma states that for any context-free language, there is some integer $p$ such that any string $S$ in the language whose length is at least $p$ can be written as $uvxyz$, where $u$, $v$, $x$, $y$ and $z$ are strings and $vy$ is not empty, and for all integers $k$, the string $uv^kxy^kz$ is also in the language.

It's clear that the lengths of the strings "pumped" by using successively larger values of $k$ form an arithmetic sequence. So we can assert that for any string $S$ in the language whose length is greater than $p$, there is there some $n$ such that for any integer $k$ there is a string in the language whose length is $|S| +nk$. That is not the case for the language $\{ a^{2^n} \mid n \in N\}$, since the lengths of the strings in that language form an exponential sequence. So the language cannot be context-free.

In fact, since the alphabet of the language has only one symbol, Parikh's theorem demonstrates that if the language were context-free, it would also be regular. It's even easier to demonstrate that the set of lengths of strings recognised by a regular language must be eventually periodic (unless the set is finite). A regular language corresponds to a Deterministic Finite State Automaton (DFA), and any DFA which can accept an infinite number of strings must include a cycle in its transition diagram. The cycle cannot have more steps than the automaton has states, so the lengths of the strings accepted must be ultimately periodic.

Constructing a non-context-free grammar for the language is not that difficult, but I don't know how useful it is.

The following is a Type 0 grammar (i.e. it's not context-sensitive either), but only because of the productions used to get rid of the metacharacters. The basic idea here is that there we put start and end markers around the string (${\boldsymbol \langle}$ and ${\boldsymbol \rangle}$) and we have a "duplicator" ($\blacktriangleright$) which moves from left to right doubling the $a$'s; when it hits the end marker, it either turns into a back-shuttle ($\blacktriangleleft$) or it eats the end-marker and turns into a start-marker-destroyer ($\star$)

\begin{align*}
\mathrm{Start}\Rightarrow  &\ {\boldsymbol \langle} {\blacktriangleright} a{\boldsymbol \rangle}\\
{\blacktriangleright} a\Rightarrow &\ aa{\blacktriangleright}\\
{\blacktriangleright}{\boldsymbol \rangle}\Rightarrow  &\ {\blacktriangleleft}{\boldsymbol \rangle}\\
{\blacktriangleright}{\boldsymbol \rangle}\Rightarrow  &\ \star\\
a{\blacktriangleleft}\Rightarrow  &\ {\blacktriangleleft} a\\
a\star\Rightarrow          &\ \star a\\
{\boldsymbol \langle}{\blacktriangleleft}\Rightarrow   &\ {\boldsymbol \langle}{\blacktriangleright}\\
{\boldsymbol \langle}\star\Rightarrow          &\ \varepsilon
\end{align*}


Algorithms that achieve better compression for more data

Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of compression to exploit.

There is a fundamental limit as to how well any particular lossless compression scheme can compress. In particular, if a compression scheme could make every file smaller, you could indeed run it repeatedly and you could keep going until the file you started with had become one bit long. Since there are only two compressed files and the decompression program is deterministic, the decompression program can only have two possible outputs, but it's supposed to be able to produce whatever file was actually compressed.

In fact, you can't even compress all files once. There are $2^n$ $n$-bit files, but only $\sum_{i=0}^{n-1}=2^n-1$ files of length strictly less than $n$.  So, if you had an algorithm that could make every file of length $n$ strictly smaller, there would have to be two different files that compress to the same thing, by the pigeonhole principle. But now the decompresser doesn't know how to decompress that file.

And it gets worse. Any fixed lossless compression scheme can't compress half of the possible files by even one bit. When we talked about compressing $n$-bit files in the previous paragraph, we didn't mention that there are also files of length less than $n$, which need to be compressed, too. There are $2^{n+1}-1$ possible files whose length is in the range $0$–$n$ bits. If we could compress all of those by even one bit, we'd have to be able to write $2^{n+1}-1$ different files of length at most $n-1$ bits, but there are only half that number of $(n-1)$-bit files, so it simply cannot be done.

Note that you can't get around this by saying "If algorithm A compresses the file, I'll use that and, otherwise, I'll use algorithm B." Even if it were guaranteed that every file could be compressed by one of those two algorithms, you'd have to write a header to the file to say which one was used. So, now you need to compress by at least two bits so that the compressed file plus the header is shorter than the original file. But no single algorithm can compress more than a quarter of files by two bits, so your combination of A and B still can't compressed half your files.

You can't get around it by using multiple files because the total length of those files will still obey the same rules that we already discussed. Since, in reality, files on disks are stored in blocks so storing $k$ files means you need to allocate at least $k$ blocks, which isn't efficient when the files are small. Multiple files does allow you to cheat slightly, since it means you don't need any delimiter between your metadata in one file and the data in the second. However, that data still has to be stored in the directory entry so you're not really saving any space.

Note that everything above applies to all possible compression algorithms. It doesn't use any properties of whatever algorithm you could think of: the argument is just about the number of files of different lengths.  The scheme you're thinking of – looking for patterns and representing them using some language – is no different. It cannot win because nothing can win. Taken to the ultimate degree, you're moving towards Kolmogorov complexity, which essentially compresses a file into the shortest program that will output that file when it's run. Still, this doesn't let you get around the fundamental bounds. Indeed, it's the tool that's used to prove a lot of the more interesting fundamental bounds. And it turns out that, for most files, the shortest program is print "[literal string containing the file contents]";, which is, essentially, one bit longer than the file you started with.


Distributed problems in Financial Services?

There is a lots of problems which might be solved by using distributed algorithms. However most of this problems are so specific that there is no existing general purpose tool for all of them.

Banks and some financial institutions keeps their own solutions hidden and i doubt that they would like to share their ideas and code.

For instance let's consider loans, some as far as I know some banks do long term calculations using Markov process. It is possible to compute is on single machine, but those processes are so complicated that I it just wouldn't be effient to calculate them on single machine.

I also found this presentation, you might want to look at it.


Design a DFA that recognizes the following language

As mentioned in the comments, you’ll need 8 states exactly. I like to label my states with semantic meanings, so in this case I’ll use a 3-digit number where each digit represents the number of as, bs, or cs we’ve seen ($\mod 2$).

Then we have all the states from $000$ to $111$ in binary.

You already know that $000$ is the start state and $010$ is the accept state.

All that remains are the transitions, which are independent of the accept rules at this point. From each state, there are 3 transitions: one for each of a, b, and c.

But now notice that for each letter, the corresponding transition is to the state with the corresponding bit flipped! For example, $110 \xrightarrow{a} 010$.

More mathematically, for any state $\alpha\beta\gamma$:

when we see an a, we go to the state $\alpha'\beta\gamma$, where $\alpha'$ is 1 if $\alpha = 0$, and vice versa;
etc., for the remaining letters.


Shortest path in a dynamic tree with vertex updates

One can improve your naive method by augmenting the data structure.  At each node in the tree, store an extra field that contains the distance to the closest descendant of type 1.  Assume each node as a pointer to its parent.  Let the depth of the tree be $d$.

Now Set(X) takes $O(d)$ time: you traverse the parent pointers to visit each of X's ancestors and update their distance field.  Also Dist(X) takes $O(d)$ time: the distance field for X tells you the shortest path to a descendant of X, and by looking at the distance fields for the siblings of the nodes along the path from X to the root, you can find the shortest path to a non-descendant of X.  Thus, both operations can be done in $O(d)$ time.

If the tree is balanced, we'll have $d = O(\lg n)$, so both operations run in $O(\lg n)$ time -- a significant improvement over the naive method you mention.

Of course, in the worst case the depth of the tree could be $\Theta(n)$, so this method won't help for such trees.  But in practice many trees (e.g., random trees) tend to have depth $O(\lg n)$.  And if you need an algorithm that works for all trees, you might be able to take advantage of a heavy-light decomposition to achieve good worst-case running time bounds.


Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:

[12, 0, 0]
[4,  8, 0]
[4,  3, 5]
[9,  3, 0]
[9,  0, 3]
[1,  8, 3]
[1,  6, 5]
[6,  6, 0]  # <-- SOLVED; 7 steps

DETAILS: The problem stated as-is is recoverable, and in a machine learning problem statement, we take the problem as-defined, not how it could be defined. For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.

[0, 0, ..., X,   ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?,   ..., 7] <-- some arbitrary state
...
[0, 0, ..., X,   ..., 0] <-- RECOVERED; empty all other jugs into original jug

Update: the system is also recoverable if starting with any # of jugs filled, as long as they're fully filled. They also don't necessarily have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.

DEFINITIONS: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:

Recoverable: state t0 can be restored from any other state T when starting at t0
Irrecoverable: there exists some state T we can get to from t0, but no longer revert to t0
Ignorable: we don't care, and can solve the problem at hand either way

Irrecoverable example: [0, 1, 2] --> [0, 0, 3]. Goodbye forever, 1 liter & 2 liters.

Ignorable example: goal: two jugs empty. In this case, both the original [12, 0, 0] and the irrecoverable case [0, 1, 2] work.


Data link layer Sliding Window utilization formula query

If it is about how we got to the formula, link utilization is the ratio of the time that the link is active to the total time.

total time being the sum of transmission time and propagation time.
link active time = time taken to transmit N packets = N * TransmissionDelay

Hence, the formula to calculate link utilization(or efficiency) is

N/(1+2a)

However, in practice, the link utilization cannot exceed 1 (ie link cannot be active for more than 100% of the time).
Hence, whenever N>(1+2a), we restrict the value to 1 only.


How to find an algorithm's complexity from actual running times

You can do regression on the whole data to get a better fit.


Machine Learning - Support Vector Machines

There are tons of tutorials for various backgrounds. What is your background?
Here is one list of tutorials: http://www.kernel-machines.org/tutorials


Loading a word from byte-addressable cache

What makes you think that?

If you have a modern high-performance CPU with 256 bit = 32 byte vector registers, then the byte offset determines which group of 1, 2, 4, 8, 16 or 32 consecutive bytes to transfer. Nobody in their right mind would transfer individual bytes. Much too slow.

What will happen and may slow down things a little bit is that if the group of bytes to transfer is not contained in one single cache line, then two accesses are made to two different cache lines. For example, if your cachle lines are 64 bytes and you try to access a 32 bit (four byte) item at byte offset 61, 62 or 63.


How to reduce the original partition problem to one of its variation?

Thanks to D.W.'s generous help, I managed to figure it out. Given an instance of the Partition problem, $S$, we can just scale every element in $S$ by 1000, and the new $S'$ becomes an instance of the variation. Then the reduction mapping holds, because scaling increases the difference between numbers. If $S$ is a YES instance, $S'$ can also be partitioned into two sets with equal sum, but if $S$ is a NO instance, all of the possible partitions of $S'$ must have difference $\geq 1000$. The reduction is clearly polynomial, and the variation is clearly in NP, so proof is complete.


Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

The language is context-free. You can use the pumping lemma for regular languages to show that it is not regular. However, you can construct a context-free grammar to show that the language is context free. For example, the following CFG grammar would generate it

$S \to A\ |\ aS  $

$A \to \epsilon\ |b A cc $


Is there a known algorithm for computing the n-th Turing machine directly?

Generate all strings in order, and keep track of which of them correspond to valid encodings. One you have seen the $n$th one, output it.

There are probably more efficient algorithms, but it depends on your exact encoding. Standard combinatorial enumeration techniques might suffice.


Travelling salesman very rough min and max estimates

It is conjectured (but unproven) that the Held-Karp relaxation (not the Held-Karp algorithm) has an integrality ratio of 4/3 (on metric TSP). Various proofs exists for even better bounds if some assumptions are made.

Practically it performs even better, gaps of ~2% are normal, and there is a lot of literature about adding more cuts that get that gap (typically) a fair way below 1%, but that would not fit with your goal of "fast and easy to implement" anymore. Just the basic degree constraints + lazy sub-tour elimination is, when using an existing LP solver, both fast and easy, and a lot better than taking one of the well known upper bounds and dividing them by their approximation ratio (which tends to be give terrible results, because they typically approximate much better than their worst case, resulting in an overly optimistic lower bound).


Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

Basically, you just write down everything that is necessary to have $t$ evictions and then use the universality of your hash functions to bound the probability.

Assume you want to insert $x$ and your hash functions are $f,g$. Then if you have $t$ probes if $f(x)$ is occupied that is
$$
\begin{align}
\mathbb{P}[t=1]& =\sum_{y \neq x} \mathbb{P}[f(x)=f(y)]\\
&\le n \cdot 1/s \le 1/2.
\end{align}$$
since your hash function are $(1,k)$-universal (I assume).

Now for $t=2$, the place of $f(x)$ have to be occupied by some element $y$ (that is $f(x)=f(y)$), and the alternative for $y$ is blocked by some other element $z$ (that is $g(y)=g(z)$). Summing up over all possible values for $y$ and $z$ gives
$$
\begin{align}
\mathbb{P}[t=2]& =\sum_{y,z \neq x} \mathbb{P}[f(x)=f(y) \text { and } g(y)=g(z) ]]\\
&\le n^2 \cdot 1/s^2 \le 1/4.
\end{align}$$

The summands of the sum are bounded by $1/s^2$ due to the universality of the hash functions, and you have less than $n^2$ summands.

I think from here you can continue by yourself.


Is switching quantifiers allowed in this instance?

The key issue here is whether switching quantifiers is okay. Turn the top-level implication around and see what happens then.

As for this formula, think about what the left- resp. the right-hand side say.

Left: "Every $x$ has a $y$ so that... holds."
Right: "There is a $y$ so that ... holds for all $x$."

In particular, the left-hand side allows different $y$ -- one for each $x$ -- while the right-hand side requires a single $y$.

With this off the table, try to figure out whether

$\qquad \left(\forall x. \exists y. P(x,y)\right) \to \left(\exists y. \forall x. P(x,y)\right)$

holds for all predicates $P$. If so, your original questions is answered, and if not it should be easy to modify a counter-example to have the necessary form of an implication.

   For the simplified formula, there is a simple counter-example: every natural number has a successor, but there is no natural number that is successor to all natural numbers.

Try to utilise this before lifting the next spoiler!

   No luck? Well, that is to be expected. The "simplified" formula was a trap as it is not really a simplified formula, as you have hopefully figured out. It allows you to set $x$ and $y$ in relation which your formula does not: the (inner) implications can be read as disjunction, i.e. $\lnot P(x) \lor Q(y)$, so $P$ and $Q$ can fulfill the disjunction independently of another.

Can you prove that the formula holds now?

   If the left-hand side is fulfilled -- if it is not, the whole formula is trivially fulfilled -- all $x$ fulfill $\lnot P(x)$ or there is (at least) one $y$ that fulfills $Q(y)$ (to rescue the failing $x$). In either case (they can overlap!) the right hand side is fulfilled. In particular, if $\lnot P(x)$ is true for all $x$, $y$ can be chosen arbitrarily (on the right-hand side), else choose one of the rescuers. Be aware that the empty element domain -- if allowed -- is a special case.


If P=NP, then all of the NP problems can be solved deterministically in Polynomial time.

This is because the NP problems are all essentially the same problem, just stated in different terms.

As far as lists go -- many of the NP-Complete problems are enumerated here:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Further implications? Our cryptosystems break down, armchair philosophers argue about what it means, the world changes, and somebody gets a Fields medal or Turing award + a big hunk of cash, etc... but that's a tangent.

For example, one of the classic NP problems is clique. If you could solve clique with a polynomial time algorithm, this would prove that P=NP, and then you could also use your method for solving clique to solve all of the other problems on that wiki-list, as an implication.


What are the differences between parse and decision trees?

A decision tree is an algorithm for computing a function, in your case the truth value of the formula. In your setting, each internal node of the decision tree is labeled by a variable, and it has two children; you go to the left one if the variable is false, and to the right one if it is true. Leaves are labeled by True or False, and this is the returned value.

For example, one decision tree for $a \land b$ is as follows. The root is labeled $a$. Its left child is a leaf labeled False. Its right child $x$ is labeled $b$. The left child of $x$ is a leaf labeled False, and the right child of $x$ is a leaf labeled True.


Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

The problem minimizing maximal lateness is discussed in the algorithm book by Kleinberg and Tardos under greedy algorithms. The solution is like yours, ordering the tasks by their deadline. Indeed the length of the tasks is not relevant.

The main ingredient of the proof is that any optimal solution $O$ can be transformed into this greedy one $G$ by swapping two adjacent tasks that do not agree on the greedy ordering.

Assume we have two tasks $(t_i,d_i)$ and $(t_j,d_j)$ with $d_i\le d_j$ and $O$ has scheduled task $j$ just before $i$, while the greedy algorithm wants it the other way. Assume task $i$ starts at time $t$ in $O$. The lateness in $O$ is the maximum $m$  of $t+t_j-d_j$ and $t+t_j+t_i-d_i$.

After swapping we have the maximum of $t+t_i-d_i$ and $t+t_i+t_j-d_j$. This cannot be worse then the performance of $O$ since both these two numbers are at most $t+t_i+t_j-d_i \le m$ (using $d_i\le d_j$). As $O$ is optimal, so must the swapped version, but it looks more like $G$.

This is not the complete proof. E.g., we have to show that always such a pair $i,j$ can be found, to iterate and obtain $G$ from $O$ by swapping. Also we have to consider 'negative values', when actually $i$ or $j$ meet their deadline, and $m=0$.


Does the following algorithm has amortized constant time per element?

I wouldn't use the word amortized in this context, since there is no change of state between different operations (this is unlike classic examples for amortized analysis such as dynamic arrays). In that case amortized and worst case analysis will agree.

The first case is a randomized algorithm, so you can talk about the expected or worst case complexity (where in the former, the expectation is over the inner randomness of the algorithm). The worst case complexity is unbounded, while the expected number of operations is indeed constant.

In the second case, you have a fixed function $h$ which you use for all inputs, so again there isn't actually a change of state and thus there is no sense in talking about a recurring bad input. Note that the algorithm is not randomized (it does not toss coins after seeing the input), so the question you're looking for now is what is the average case complexity of your algorithm, where the expectation is over the choice of $x$ (relative to some distribution over $U$), and the random choice of  $h$. For a completely random $h$, you will get the same answer as in the first case.


Unless I'm missing something obvious (it is getting late here), the second isn't possible - $BPP = coBPP$, so $NP=BPP \rightarrow NP = coBPP \rightarrow NP = coNP$.

In the first case, some of the consequences would be:

"Feasible" algorithms for $NP$-complete problems, for at least the randomised version of feasible.
$PH \subseteq NP$
Unless $P = NP$, adding randomness adds computational power.
Strong pseudorandom number generators do not exist (nor do one way functions). (we would need $BPP = P$ for them to exist, but that would imply $P=NP$, in which case they don't).


Method of communication in Distributed Systems

Because in a distributed system, nodes do not have access to shared memory that is shared between all nodes.  Shared memory is only typically feasible when the nodes are on a common memory bus, e.g., for multiple core within a parallel processing machine.


algorithm for predicting procces's memory/cpu usage based on other other prior/still running jobs

Here are the broad outlines of one general approach:

Determine what observable attributes of a job might help you predict the resource usage of the job.  You'll have to hypothesize what these might be based on your domain knowledge of the kinds of jobs you run, as well as your knowledge of what attributes of a job can be measured and observed, before the job finishes.
Treat that set of observable attributes as the "feature vector" for the job.  Each job gets assigned a "feature vector", based on the values of those attributes.
Gather training data: gather a data set, from past jobs, where you have measured the attributes of the jobs before they finished running and also measured the actual resource usage of those jobs.
Now use some suitable machine learning algorithm to predict the resource usage of new jobs, based on the training set and the attributes of the new job.  Select some appropriate supervised learning algorithm.  The choice of a specific algorithm will depend on how you expect the resource usage to vary depending on the attributes.  (Is it a linear relationship?  Smooth curve?  Something else?)  You might choose linear regression, or CART trees, or something else entirely.  There's lots of literature on this -- I'll leave you to study it on your own and get up to speed on standard materials on this subject.

You'll have to work out the details on your own and play with it a bit to see how well it works in your particular setting.  I can't tell you whether or not this will work well in the end; that will depend on your particular workload and the types of jobs you are dealing with.


Here is one possible definition of big O (your definition might vary in details):

  Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n) = O(g(n))$ if there exists an integer $N$ and a real $C > 0$ such that for all $n \geq N$, $f(n) \leq Cg(n)$.

Using the rules of logic, we get a definition of the negation of big O:

  Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n)$ is not big $O(g(n))$ if for every integer $N$ and real $C > 0$ there exists $n \geq N$ such that $f(n) > Cg(n)$.

This is what you should prove. For each integer $N$ and real $C > 0$ you should find $n \geq N$ such that $0.1n + 10\sqrt{n} > C\sqrt{n}$.


What happens when sink transition is enabled

Yes. Firing the transition just consumes one token from each of its input places.


Polynomial by the size of the output and the input

I wonder why the complexity of algorithms [does not] depend on the size of  [...] the output.

But it does!

The size of the input is often used as a trivial lower bound on the running time ("you need to write the output"). So trivial, indeed, that it's rarely talked about in introductory courses. There, the output is usally not the dominating factor so it's not interesting to discuss is further.

Think about what that would mean on the intuitive: an algorithm that writes more bits than it takes time to compute them. That doesn't seem very efficient in itself; maybe your output encoding is bad.

That said, you do on occasion encounter runtime analyses where characteristics of the output appear in the determined bounds. Search and enumeration algorithms, for instance, can admit non-trivial bounds the separate them from brute force ("I don't have to check all candidates, but only at most three times the number of those I want to find").


DNA Computing Algorithm to solve the Hamiltonian problem

Yes, of course.  The Hamiltonian path problem is decidable, so it can be solved using a Turing machine.

I recommend you read about the Church-Turing hypothesis, decidability, and undecidability.  I think you'll find those topics of interest.


How to maintain completely dynamic convex hull quickly?

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".


Given a set of points, find the one closest to a given point

If we make no assumptions on input and want an exact answer to the question what the minimum distance is to $p_0$, any algorithm must take at least $\Omega(n)$ time in the worst case. To see this, suppose $p_0$ is in your input points. In the worst case, the final point we see in our list is this point! So we must inspect all our input points and hence take $\Omega(n)$ time.

For the same reason, an approximation algorithm must also use $\Omega(n)$ time, as the difference in distance to $p_0$ between the inspected points in the list and the points we haven't inspected yet may be arbitrarily large.

The only way I see to be faster than linear is to take a random sample from your list to get the right answer with a certain probability. However, I think the running time would heavily depend on the probability you would want in the list.


Rice's theorem applicable to the following language?

Because there may be multiple $M$'s corresponding to the same $f_M$. That is to say, you cannot deduce $\langle M\rangle$ from $f_M$, so you cannot describe $S$ in this way.


It isn't true that every DFA for this language is non-planar:

Here is a language that is truly non-planar:
$$
\left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}.
$$
Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six distinct outgoing edges, which contradicts the known fact that every planar graph has a vertex of degree at most five.


Is repetition the origin of countability?

I assume by countability, you mean a set being countably infinite, like $\mathbb{N}$.

All languages over a finite alphabet are countably infinite, whether they are regular or not.

It's easy enough to show that we can encode any string in $\mathbb{N}$: just take map its letters onto $\{1,2,\ldots\}$ and interpret the string as a base-$(n+1)$ number for an alphabet with $n$ letters. (Starting at $1$ avoids the problems with multiple $0$s on the left side of a number). You can also use Gödel numbering, which is simpler but less efficient.

It's important to distinguish languages themselves from the set of languages:

Any language over a finite alphabet is countably infinite (or finite)
There are an uncountably infinite number of languages over any finite alphabet
Any class of languages we describe with a finite representation (including DFAs, CFGs, Turing Machines, or even logic statements) is countably infinite. So there are more languages than we will ever have ways to talk about or describe.

So no, repetition is not the origin of countability. Even undecidable languages are countably infinite.


Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

The obvious candidate is a persistent balanced binary tree.  All the operations you listed can be performed in $O(1)$ or $O(\lg n)$ time, using path copying.  For more details on how to achieve this runtime, see Chris Okasaki's book referenced below or my answer here.

Of course, as an variant, each leaf of such a tree could itself contain an immutable array (a sequence of consecutive values).  This makes updating a value less efficient, but it might work well for your situation, if you never intend to modify an existing value, just append and prepend.  In this way, your vector is represented as a sequence of immutable sequences, represented as a balanced binary tree with immutable arrays in the leaves.  This allows for fast indexing (logarithmic in the number of leaves), fast append and prepend, and fast iteration.  The worst-case asymptotic complexity is no better, but the performance in practice might be significantly better.

The standard reference is Chris Okasaki's 1998 book "Purely functional data structures".
See also

What classes of data structures can be made persistent?
What's new in purely functional data structures since Okasaki?
What are the outstanding questions in purely functional data structures?
Ten Years of Purely Functional Data Structures


Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.


prove that a language is context free given a regular language

Let $\phi(R) \subseteq 0^*$ result from $R$ by substituting $0$ for $1$. Alternatively, $\phi(R) = \{ 0^{|w|} : w \in R \}$. The previous description makes it clear that $\phi(R)$ is also regular. Now
$$
\operatorname{Sub}(R) = \phi(R) \{ 0^j 1^j \},
$$
the concatenation of the regular language $\phi(R)$ and the context-free language $\{0^j 1^j\}$.


Is the "subset product" problem NP-complete?

A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao.  Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been.
Definitions:

EXACT COVER BY 3-SETS (X3C)
Given a finite set $X$ with $|X|$ a multiple of 3, and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover $C'$ for $X$, where $C' \subseteq C$ and every element in $X$ occurs in exactly once in $C'$?
SUBSET PRODUCT
Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

To reduce an X3C instance to a SUBSET PRODUCT instance:

Establish a bijective mapping between the members of $X$ and the first $|X|$ prime numbers.  Replace the members of $X$ and the $C$ subsets with the mapped primes.

For each subset in $C$, multiply its members together; the resulting list of products is $L$ for the SUBSET PRODUCT instance.  Because prime numbers are used for the mapping in step 1, the products are guaranteed to be equivalent iff the subsets are equivalent by the unique factorization theorem.

Multiply the members of $X$ together; the resulting product is the value $k$ for the SUBSET PRODUCT instance.

The prime factors of $k$ are exactly the members of $X$.  The prime factors of the numbers in $L$ correspond exactly to the members of the $C$ subsets.  Therefore any solution to the new SUBSET PRODUCT instance can be transformed into a X3C solution by mapping the solution members of $L$ back to the subsets in $C$.
Each of the 3 transformation steps involves operations that are polynomial to the size of the input $|X|$ or the size of a member of $X$.  The first $|X|$ primes can be generated in time O($|X|$) using the sieve of Eratosthenes and are guaranteed to fit into $O(|X|^2 \ln |X|)$ space by the prime number theorem.


What we lack to do automatic programming?

We already have the formalization of norms

I don't think we do. Norms are written in natural languages (e.g. English). And truly understanding text written in a natural language (even a subset of it, such as the one used to write norms) is still not something that can be done.

Even if you solved that, business policies and rules usually aren't detailed enough to directly create useful programs out of them. That's another hurdle that's not going to be easy to cross.


What is The correct terminology for expressing *this* notion of complexity

Kolmogorov's complexity is defined relative to a specific representation. It is rather meaningless to ask what is the minimal Kolmogorov complexity of a certain object over all possible representations (obviously, this requires a precise definition for what constitutes a valid representation).

To see why, consider for example the following question: what is the minimal Kolmogorov complexity of the identity function over all admissible numberings? The answer is trivially $1$, since I can encode the identity function as "0" (a single bit string).


Matrix powering shows that directed reachability is in $\mathsf{AC^1}$, and so $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC^1}$. In more detail, suppose that $A$ is the adjacency matrix of a directed graph $G$, with self-loops on all vertices. The matrix $B_{ij} = \bigvee_k A_{ik} \land A_{kj}$, which can be computed in $\mathsf{AC^0}$, is the adjacency matrix of $G^2$. In other words, $B_{ij} = 1$ iff there is a path of length at most 2 from $i$ to $j$ in $G$. Iterating this construction $\log n$ times, we obtain an $\mathsf{AC^1}$ circuit computing the adjacency matrix of $G$, that is, which vertex is reachable from which vertex.

What goes wrong when using DFS to evaluate $\mathsf{AC^1}$ circuits? The same approach works, only it uses $\log^2 n$ space rather than $\log n$ space. The reason is that at each level, you need $\log n$ space to store which child you are currently in. Multiplied by the number of levels, we obtain $\log^2 n$.