Which priority queue implementations are stable?

Here's how I would suggest that you approach the problem.  Try running each data structure by hand on some small examples.  Then, based on those examples, see if you can form any conjecture about which data structures are stable and which ones aren't. For the ones you suspect are stable, try proving it.  For the ones that you suspect are not stable, try to come up with a counterexample to demonstrate that they're not stable.


short text categorization with spelling correction

Could you not just pre-process the text? Simply pass over the corpus and correct errors via edit-distance or lookup tables. Once this has finished you can then run the classifier.

It you really want to incorporate the correction into your model, it would seem that you can re-define edit distance to compute the log-probability of some misspelled word matching another for some mismatch probability $\theta \sim \text{Beta}(\alpha, \beta)$.

The resulting probabilities can then be incorporated into the classifier directly, which would be parameterized by $\theta$. Depending on how complex your internal model is, you could find the ML or MAP estimate $\hat{\theta}$ by some EM algorithm, or if the model allows, analytically.


Why NP is not closed under Turing reduction

The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions.

Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.

Why this notion and not Turing reductions? First - it works well, and it provides a finer distinction in complexity classes (more on that in a bit). Second, it captures the intuition that if you could solve $B$, then given input for $A$ you can convert it to input for $B$, rather than just use $B$ in some complex and clever manner.  So in a way, it makes "very little use" of $B$. This is all philosophical, of course.

In practice, the main benefit of Karp reduction is that it differentiates $coNP$ from $NP$. Indeed, you can show a Turing reduction from $SAT$ to $\overline{SAT}$ (just call the oracle and flip the answer). So you cannot have the notion of coNP-complete v.s. NP-complete if you use Turing reductions.

You can read the discussion here for a more elaborate answer.


Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to "connect" all points

Try polyline simplification.
For heuristics or other simplifications you might want to treat segments as resizeable, but for now objective is not that clear.
Here is demo of RDP.
Try it, merge your answer into question and then explain objective.

There is tradeoff between polyline complexity reduction and number of remaining points. Number of removed points depends on data and $\epsilon$.

If you want to find minimum, you have $N-1$ segments on $N$ points, and exact reduction depends on colinearity of points. Otherwise it is only approximation.


Prove Context Free languages not closed under difference?

Yes I believe it is possible to prove such a non-closure property without pumping a specific example language.

As noted in the comments, complement $\Sigma^* - L$ is a special form of difference. It turns out that complementation is an extremely powerful tool used with context-free languages. One can show that computation histories of Turing machines can be specied as complements of context-free languages. This seems to originated from J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings
of Symposia in Applied Mathematics, Vol. 19, AMS, 1967, 42-51.

A computation history (for a fixed TM $M$) is a string of the form $x\$C_0\$C_1\$\dots\$C_n$ where $x$ is an input string, $C_0$ is the initial configuration of $M$ on $x$, meaning a string of the form $q_0x$ where $q_0$ is the initial state, $C_n$ is a final configuration (with a final state) and each pair of consecutive $C_{i-1}\$C_i$ represents a single step of TM $M$.

The language of those strings is the complement of a context-free language.

What is CFL would be closed under complement? Then the context-free languages would be equal to the languages accepted by Turing Machines: the languages of valid computations would be context-free, and from this we can find their prefixes or the accepted inputs of the TM. I  do think that is a contradiction without the pumping lemma. We know there are more TM accepted languages than CF languages by complexity or decidability arguments.


Karloff's algorithm applied to sparse graphs

I would suggest reading Theorem 5.1 and Lemma 5.1 on the same page in the paper. They answer both your questions.

The proof of Theorem 5.1 in the paper does not use the density of $G$. It will therefore also work for sparse graphs.

You are asking about the motivation behind the assumption of $G$ being dense. In this context the assumption is that a dense graph does not fit into the memory of a single machine. Lemma 5.1 and the conclusions after it show that the input size to the reducers is small enough to fit into the memory.


What's the difference between a type and a kind?

Here, "values", "types", and "kinds" have formal meanings, so considering their common English usage or analogies to classifying automobiles will only get you so far.

My answer pertains to the formal meanings of these terms in the context of Haskell specifically; these meanings are based on (though are not really identical to) the meanings used in mathematical/CS "type theory".  So, this won't be a very good "computer science" answer, but it should serve as a pretty good Haskell answer.

In Haskell (and other languages), it ends up being helpful to assign a type to a program expression that describes the class of values the expression is permitted to have.  I assume here that you've seen enough examples to understand why it would be useful to know that in the expression sqrt (a**2 + b**2), the variables a and b will always be values of type Double and not, say, String and Bool respectively.  Basically, having types assists us in writing expressions/programs that will work correctly over a wide range of values.

Now, something you may not have realized is that Haskell types, like those that appear in type signatures:

fmap :: Functor f => (a -> b) -> f a -> f b

are actually themselves written in a type-level Haskell sublanguage.  The program text Functor f => (a -> b) -> f a -> f b is -- quite literally -- a type expression written in this sublanguage.  The sublanguage includes operators (e.g., -> is a right associative infix operator in this language), variables (e.g., f, a, and b), and "application" of one type expression to another (e.g., f a is f applied to a).

Did I mention how it was helpful in many languages to assign types to program expressions to describe classes of expression values?   Well, in this type-level sublanguage, expressions evaluate to types (rather than values) and it ends up being helpful to assign kinds to type expressions to describe the classes of types they are permitted to represent.  Basically, having kinds assists us in writing type expressions that will work correctly over a wide range of types.

So, values are to types as types are to kinds, and types help us write value-level programs while kinds help us write type-level programs.

What do these kinds look like?  Well, consider the type signature:

id :: a -> a

If the type expression a -> a is to be valid, what kind of types should we permit variable a to be?  Well, the type expressions:

Int -> Int
Bool -> Bool

look valid, so the types Int and Bool are obviously of the right kind.  But even more complicated types like:

[Double] -> [Double]
Maybe [(Double,Int)] -> Maybe [(Double,Int)]

look valid.  In fact, since we ought to be able to call id on functions, even:

(a -> a) -> (a -> a)

looks fine.  So, Int, Bool, [Double], Maybe [(Double,Int)], and a -> a all look like types of the right kind.

In other words, it looks like there's only one kind, let's call it * like a Unix wildcard, and every type has the same kind *, end of story.

Right?

Well, not quite.  It turns out that Maybe, all by itself, is just as valid a type expression as Maybe Int (in much the same way sqrt, all by itself, is just as valid a value expression as sqrt 25).  However, the following type expression is not valid:

Maybe -> Maybe

Because, while Maybe is a type expression, it doesn't represent the kind of type that can have values.  So, that's how we should define * -- it's the kind of types that have values; it includes "complete" types like Double or Maybe [(Double,Int)] but excludes incomplete, valueless types like Either String.  For simplicity, I'll call these complete types of kind * "concrete types", though this terminology isn't universal, and "concrete types" might mean something very different to, say, a C++ programmer.

Now, in the type expression a -> a, as long as type a has kind * (the kind of concrete types), the result of the type expression a -> a will also have kind * (i.e., the kind of concrete types).

So, what kind of type is Maybe?  Well, Maybe can be applied to a concrete type to yield another concrete type.  So, Maybe looks like a little like a type-level function that takes a type of kind * and returns a type of kind *.  If we had a value level function that took a value of type Int and returned a value of type Int, we'd give it a type signature Int -> Int, so by analogy we should give Maybe a kind signature * -> *.  GHCi agrees:

> :kind Maybe
Maybe :: * -> *

Going back to:

fmap :: Functor f => (a -> b) -> f a -> f b

In this type signature, variable f has kind * -> * and variables a and b have kind *; the built-in operator -> has kind * -> * -> * (it takes a type of kind * on the left and one on the right and returns a type also of kind *).  From this and the rules of kind inference, you can deduce that a -> b is a valid type with kind *, f a and f b are also valid types with kind *, and (a -> b) -> f a -> f b is valid type of kind *.

In other words, the compiler can "kind check" the type expression (a -> b) -> f a -> f b to verify it's valid for type variables of the right kind the same way it "type checks" sqrt (a**2 + b**2) to verify it's valid for variables of the right type.

The reason for using separate terms for "types" versus "kinds" (i.e., not talking about the "types of types") is mostly just to avoid confusion.  The kinds above look very different from types and, at least at first, seem to behave quite differently.  (For example, it takes some time to wrap your head around the idea that every "normal" type has the same kind * and the kind of a -> b is * not * -> *.)

Some of this is also historical.  As GHC Haskell has evolved, the distinctions between values, types, and kinds have started to blur.  These days, values can be "promoted" into types, and types and kinds are really the same thing.  So, in modern Haskell, values both have types and ARE types (almost), and the kinds of types are just more types.

@user21820 asked for some additional explanation of "types and kinds are really the same thing".  To be a little clearer, in modern GHC Haskell (since version 8.0.1, I think), types and kinds are treated uniformly in most of the compiler code.  The compiler makes some effort in error messages to distinguish between "types" and "kinds", depending on whether it's complaining about the type of a value or the type of a type, respectively.

Also, if no extensions are enabled, they are easily distinguishable in the surface language.  For example, types (of values) have a representation in the syntax (e.g., in type signatures), but kinds (of types) are -- I think -- completely implicit, and there's no explicit syntax where they appear.

But, if you turn on the appropriate extensions, the distinction between types and kinds largely disappears.  For example:

{-# LANGUAGE GADTs, TypeInType #-}
data Foo where
  Bar :: Bool -> * -> Foo

Here, Bar is (both a value and) a type.  As a type, its kind is Bool -> * -> Foo, which is a type-level function that takes a type of kind Bool (which is a type, but also a kind) and a type of kind * and produces a type of kind Foo.  So:

type MyBar = Bar True Int

correctly kind-checks.

As @AndrejBauer explains in his answer, this failure to distinguish between types and kinds is unsafe -- having a type/kind * whose type/kind is itself (which is the case in modern Haskell) leads to paradoxes.  However, Haskell's type system is already full of paradoxes because of non-termination, so it's not considered a big deal.


Can an operating system without api still work?

No, the other programs sit on top of the operating system(OS) and the OS runs on top of the hardware. The OS provides these programs with basic resources the programs will need to run like CPU, memory and input/output from for e.g. mouse and keyboard. The API is the only way they can get these resources, so normal programs will not be able to work on an OS without API. The new browser analogy is wrong since using IE is just a way to download the new browser files(can do it from command line, without IE). New browser still needs the OS to run.


DFA: Can the set of States Q be empty by definition?

In a DFA - no, because the definition includes a single initial state $q_0$, which means that $q_0\in Q$, and therefore $Q\neq \emptyset$.

In an NFA, however, this is indeed possible.


Automorphism capture a natural notion of symmetry of graphs. As a result, they can be used to speed up algorithms that would otherwise run slowly by chopping down the search space.

For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to keep checking symmetric parts of the tree. We can use graph automorphisms to compute the orbits of variables in the linear programming problem, and then treat parts with the same orbit as identical. A recent application of such techniques to MILP can be read here.


When does the IEEE-754 64-bit float break as a counter

IEEE floating point format has a sign bit,  an 11 bit exponent (ranging from -1022 to 1023) and a 52-bit mantissa with an implicit "1" in the 53rd bit.

Thus, the largest integer that can be represented without rounding is the binary number with 53 "1"s, $2^{53}-1$ = 9,007,199,254,740,991 ~ 9e15 < 1e16.  After that you start having to round off low order bits.  So it looks like your experiment produced the right order of magnitude.


Compress 32 bit integer into a normalized float

You can avoid getting denormals by truncating the number of random bits to ensure that there are none; even if you don't do that, the probability of getting a denormal is extremely small.

The standard way to convert uniform random variables to Gaussians is the Box–Muller transform.


Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?

If the DFA contains a path from the start node to an accepting state that contains a cycle, then the DFA is an infinite language.  The proof is easy: you can go around the cycle as many times as you like.  Depending on how many times you go around the cycle, you get a different word accepted by the DFA; the more times around the cycle, the longer the word (so it has to be different from any word where you went around the cycle a different number of times). There are infinitely many possibilities for how many times you can choose to go around the cycle, so infinitely many words accepted by the DFA.


Yes.  Simulation is straightforward and doesn't require any special ideas: it can be done directly, by just executing the circuit one gate at a time.

The algorithm to simulate a combinational circuit is completely straightforward.  Given a combinational circuit $C$ and an input $x$, it is easy to compute the output $y=C(x)$, simply by simulating each gate, one gate at a time.  Each gate in the combinational circuit is either an AND gate or an inverter.  Both can be implemented in software.  So, to simulate such a circuit, you just iterate through the gates in topologically sorted order, compute the effect of each gate, and store the value of its output wire.  This is a trivial, linear-time algorithm.  There's no need for SAT solvers or anything fancy like that.

Of course, when you compute the output of the circuit on some input, it's straightforward to save the output anywhere you like.  If you only want to test the circuit on certain inputs, just do that.  If you want to compare the output of the circuit to the known-correct output, you can do that: it's just an equality test.

Alternatively: A combinational circuit is a special case of a sequential circuit.  A sequential circuit is allowed to have both combinational logic and memory (e.g., registers).  A combinational circuit is the special case where you have no memory (e.g., no registers).  So, in principle any method for sequential circuit simulation already provides you a way to simulate combinational circuits.


I would assume the fetch_and_store instruction is meant. Look at the footnotes on page 2:

  1) Fetch-and-store exchanges a register with memory.

Keep in mind that this paper is over 20 years old, so the terminology can seem unfamiliar. However, often the semantic of the operations/instructions used in such papers are described in detail somewhere in the text.


What is the fastest way to merge two B trees?

It is great that you have obtained a sorted array, which runs in $O(n)$ time.

Once we have $n$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $O(n)$.   In particular, we can build a $B$-tree in $O(n)$ time.

Here is an example. Suppose the sorted array is $$[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17]$$ and we want to build a $2$-$4$ $B$-tree.  Split the array into groups of $2$ numbers, except that last group that could be $2$ or $3$ numbers.
$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12\}, \{13,14\}, \{15,16, 17\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12, 13\}, \{14,15,16, 17\}.$$

Label the groups successively as $g_1, g_2, \cdots, g_7$. Let $g_1$ be the root of the tree. Let the left child of $g_i$ be $g_{2i}$ if $2i\le n$ and the right child of $g_i$ be $g_{2i+1}$ if $2i+1\le n$. Now we have a complete binary tree where

each node contains at least 2 number, and
each internal node has 2 children.

That means, it is a $2$-$4$ $B$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.


You have to understand that this is a convention. Conjunctions and disjunctions are supposed to be applied to formulas. Sometimes we want to keep things general, so that we may have to allow "empty disjunctions" and "empty conjunctions", and to that purpose we define what they are.

Here is one way to see why this convention is used. Let us consider a binary commutative associative operation $\oplus\colon A\times A\rightarrow A$ on some set $A$. Suppose moreover that there exists an element $e\in A$ such that $\forall a\in A, a\oplus e = e\oplus a = a$.

Since the operation is associative, we can make sense of the expresion $\bigoplus_{i\in I} a_i $ when $I$ is a finite non-empty set, which we define to be $(\dots(a_{i_1}\oplus a_{i_2})\oplus\ldots\oplus a_{i_{n-1}})\oplus a_{i_n}$. Since we don't want to always have to specify what happens when $I$ is empty, we take the convention that $\bigoplus_{i\in I} a_i = e$ when $I=\emptyset$. Why is this convention useful? It allows to write things like $$\left(\bigoplus_{i\in I} a_i\right) \oplus \left(\bigoplus_{i\in J} a_i\right) = \bigoplus_{i\in I\cup J} a_i$$ even if $I,J$ are allowed to be empty sets (where we implicitly replace $J$ by some other enumeration $J'$ that is so that $J'\cap I=\emptyset$). If we were to take some other convention, we would always have to be careful when writing the expression above.

See how this general situation occurs a lot in mathematical writing:

the empty sum $\sum_{i\in I} a_i$ is taken to be $0$ when $I=\emptyset$, as $0$ is a neutral element for the addition of real numbers,
the empty product $\prod_{i\in I} a_i$ is taken to be $1$ when $I=\emptyset$,
in the example of formulas, consider the binary operator $\lor$. A clause is a disjunction of propositional variables, as you say, hence it can be written as $\bigvee_{i\in I} p_i$. When $I$ is empty, we want to define the empty disjunction as the neutral element for $\lor$. This element is $\bot$ (up to logical equivalence), as $p\lor \bot \Leftrightarrow \bot\lor p\Leftrightarrow p$ holds.
in the example of formulas and cubes, we want to give a meaning to $\bigwedge_{i\in I}p_i$. Following the same convention, we use the neutral element for $\land$, which is $\top$: indeed, for any proposition variable it holds that $p\land\top\Leftrightarrow\top\land p\Leftrightarrow p$.


How to partition a set in order to minimize the number of the elements and their interactions?

Consider the following two variants of subset sum problem:
Variant 1

Given a set of $2n$ positive integer elements and a positive integer target $W$, is there a subset with size $n$, whose sum is $W$?

Variant 2

Given a set of $n$ positive integer elements and a positive integer target $W$, where $(\text{the maximum element})< 2\times(\text{the minimum element})$, is there a subset whose sum is $W$?

Variant 1 is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).
Variant 2 is also NP-hard by a reduction from Variant 1. Given an instance of Variant 1, we add a large enough integer $M$ to each element so that the new elements satisfy the constraint in Variant 2. Now the answer to Variant 1 is "yes" if and only if there is a subset of the new elements whose sum is $W+nM$ (since $M$ is large enough, the subset must have size $n$).
Now we show a reduction from Variant 2 to (the decision version of) your problem, so your problem is NP-hard.
Given an instance of Variant 2, we construct $S_1=S_2$ as the same set as the given instance. Let $s$ denote the sum of all elements. We set $R_1=W$ and $R_2=s-W$. The gain of each element is the same as itself.
Now if there is a subset $O\subseteq S_1=S_2$ whose sum is $W$, then we can choose $O_1=O$ and $O_2=S_2\backslash O$, meaning there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$.
On the other hand, if there is a solution to your problem with $|O_1|+|O_2|+|O_1\cap O_2|\le n$, then $2|O_1\cap O_2|\le n-|O_1\cup O_2|$. Let $\min$ and $\max$ be the minimum and maximum elements respectively. We have
$$\sum_{e\in O_1\cap O_2}e\le |O_1\cap O_2|\max\le 2|O_1\cap O_2|\min\le(n-|O_1\cup O_2|)\min\le\sum_{e\notin O_1\cup O_2}e.$$
This means
$$
\sum_{e\notin O_1}e=\sum_{e\in O_2}e-\sum_{e\in O_1\cap O_2}e+\sum_{e\notin O_1\cup O_2}e\ge \sum_{e\in O_2}e\ge s-W.
$$
Note $\sum_{e\in O_1}e\ge W$ and $\sum_{e\notin O_1}e+\sum_{e\in O_1}e=s$, we have $\sum_{e\in O_1}e=W$ and $\sum_{e\notin O_1}e =s-W$, which means there is a subset $O\subseteq S_1=S_2$ whose sum is $W$.


How are lamport clocks implemented in real world distributed systems?

Amazon's Dynamo [1] is a distributed storage system that uses vector clocks "to capture causality between different versions of the same object". Section 4.4 of the paper describes how exactly Lamport clocks are used to manage data versioning.

Some of the open source implementations of Dynamo are Riak [2] and Voldemort [3].

[1] G. DeCandia et al.: Dynamo: amazon's highly available key-value store. SOSP 2007:205-220

[2] http://basho.com/riak

[3] http://www.project-voldemort.com


Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode

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


How do you calculate the training error and validation error of a linear regression model?

Yes. Yes. The test set is used to get an unbiased measure of the performance of your model. This is explained in many sources, better than I can explain here; I won't try to repeat them. See, e.g., https://en.wikipedia.org/wiki/Training,_validation,_and_test_sets, https://stats.stackexchange.com/a/104750/2921, or standard textbooks.


This is an unfortunate inconsistency (or at least a frequent confusion) in terminology. Formally speaking, people usually define big-oh to be an upper bound, so that means running in time $O(n^5)$ just means the running time is bounded by $n^5$ times some constant if $n$ is sufficiently large.

In other words, $n^4$ is $O(n^5)$ (and it's also $O(n^4)$, $O(n^9)$, and $O(n^{1000})$, as well as many other things). In your example, $n + 2n^2 + 10n^4$ is both $O(n^4)$ and $O(n^5)$.

The usual formal notation for an exact asymptotic analysis (i.e. something that is both an upper and lower bound) is big-theta, or $\Theta$. So you would say that $n + 2n^2 + 10n^4$ is $\Theta(n^4)$, but it's not $\Theta(n^5)$.

The reason I call this terminology "unfortunate" is that it confuses many people, including you (as evidenced by you asking this question). The problem is that in informal speech, and often even in papers, people say $O$ when they really mean $\Theta$: when someone refers to a $O(n)$ algorithm, or an $O(n^2)$ algorithm, they often really mean $\Theta(n)$ or $\Theta(n^2)$. While using $O$ is usually not technically incorrect, it is misleading when $\Theta$ would also be correct and more precise. This is something you have to get used to: recognizing whether the writer really means $O$, or whether they could have said $\Theta$.


Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

Since I'm still learning proof techniques, this is a good practice for me too. Please verify the solution yourself. We shall prove this with a series of lemma.

Lemma 1.
A perfectly balanced tree with height $h$ would have $n = 2^{h+1}-1$ nodes.

Proof.
Trivial proof by induction.

Lemma 2.
A perfectly balanced indexed binary search tree have root with value $2^h$.

Proof.
By lemma 1, there are $2^h-1$ nodes on the left subtree of the root. By constraint of binary search tree, the root element will have value $(2^h-1)+1=2^h$.

Lemma 3.
In a perfectly balanced indexed binary search tree, any node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$ and right child with value $k+2^{h-1}$.

Proof.
Due to the properties of the tree, the value of the left child of $A$ is the value of $A$ itself, which is $k$, subtracted by the number of nodes on the right subtree of the left child, which is $2^{h-1}-1$ from lemma 1, added by one. This is trivial upon drawing out such a tree, which I shall not include here. Hence, the value of left child is $k-(2^{h-1}-1)-1=k-2^{h-1}$. A similar proof will suffice for the value of right child.

Theorem.
In a perfectly balanced binary search tree with height $h$, any node $A$ will have exactly $2^i−1$ children on each side, where $i$ is the position of the first $1$-bit in the value of node $A$, starting from $0$, and counting from least significant to most significant.

Proof.
We shall prove by induction from root down to leaves. By lemma 2, the root value is $2^h$, which binary representation is

$$
1\overbrace{0\dots0}^h
$$

The position of the first $1$-bit will therefore be in the $h$ position. Substituting $i=h$, we have $2^h-1$ children on each side, which agree with lemma 1.

Now, we assume any node $A$ satisfy the stated theorem. By lemma 3, the left child of node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$. By lemma 1, we know that $i=h$, so it suffice to show that the position of the first $1$-bit in $k-2^{h-1}$ appears a bit before that in $k$. In other words, we can assume that the first $1$-bit in $k$ appears at position $h$, and we need to show that the first $1$-bit in $k-2^{h-1}$ appears at position $h-1$.

In binary, we can represent $k$ as

$$
1\dots1\overbrace{0\dots0}^{h}
$$

and we are subtracting it from $2^{h-1}$, as represented by

$$
1\overbrace{0\dots0}^{h-1}
$$

Since $k$ is all zeros in the first $h$ bits, subtracting by $2^{h-1}$ will cause bit $h$ to become $0$ and bit $h-1$ to become $1$, which retain the stated proposition. A similar prove can be done for the right child of $A$. In addition, one also need to prove the termination case to complete this prove, which I also leave out here.


NP is a complexity class with constraints on time, whilst PSPACE is a complexity class with constraints on space.
The difference between time and space is (in this case) simple: Space can be reused, whilst Time cannot. A Space-bounded machine can run for as long as it wants (as long as it terminates).

Therefore we can construct a PSPACE-Machine that solves SAT: The machine simply tries every solution.


I'll just answer a) and b) because I don't know the potential method.

About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a structure called "dynamic array", which is very similar to an ArrayList in Java. The way that structure operates is that internally it has an array, and it doubles in size once it's full, copying everything into the new array.

Now what's the worst case cost for an insert operation into that structure? The worst that can happen is that you have to double the array that contains $n$ elements, so you get a worst case cost of 1 operation (!) of $\mathcal{O}(n)$. If you insert $n$ elements, this gives you a worst case running time of $\mathcal{O}(n \cdot n) = \mathcal{O}(n^2)$.

Obviously that is far too pessimistic. We know that we only have to double every $2^k$ steps, because with every time we double the size of the array, it'll take twice as long until we need to double it again. Here is where amortized analysis comes into play: you know that there are some expensive operations, but you also know that they happen comparatively rarely, so you try to see whether the "naive" worst case analysis can be improved with a little bookkeeping. In order to do this reasonably, you don't consider a single operation anymore, you consider a sequence of operations, usually of length $n$.

Maybe you have read about the accounting method: you have an account where you can "save up" time, and every operation is allowed to take "time" out of the account, but no more than is in the account. The idea behind this is that the many cheap operations "help pay" for the few expensive ones, and if we distribute the cost that way, we can get a better analysis (that is still a true upper bound, i.e. the actual complexity is still below the amortized complexity in all cases).

How would that work in the case of the dynamic array? Every "cheap" insert is just one write operation to the array, so that costs us $1$ unit of time. Every "expensive" operation costs us $k$ units where $k$ is the number of elements in the array at that time. Now we would like the cheap inserts to share the cost of the expensive one that they help produce. This can be done if every cheap insert, in addition to paying its own $1$ unit of cost, contributes another $2$ units to the account, because this way, the inserted element pays for the copying of itself and a second one that will be copied when we double. This means that for every expensive insert we have, there will be at least $k$ units of time on our account, and we can pay for it using the money in the account only, so the actual cost of the expensive insert goes down to $k-k = 0$ (because it doesn't actually cause work that hasn't already been paid for, it's paid for with the time that was "saved up" by the cheap inserts using the account savings). How does this help us? Now every cheap insert costs us $1+2=3$ units, and every expensive insert costs us $k-k =0$ units, giving both an amortized cost of $\mathcal{O}(1)$. If we want to calculate the amortized cost of inserting $n$ elements now, we get $\mathcal{O}(1 \cdot n) = \mathcal{O}(n)$, and this is still an upper bound on the actual cost that any input can produce.

About b) While amortized analysis still gives you an upper bound on the actual cost of an algorithm, average case analysis doesn't guarantee that; there may be inputs where the actual cost is above the average case cost. But that's not a problem for average case analysis, because it just tells you what the cost of running your algorithm typically is, meaning as an average of the cost of all possible instances of size $n$.


Applying a 1-qubit gate to entangled qubits

I think you're confusing people talking about what must be done theoretically (to compute operations on qubits on paper) with people talking about what must be done experimentally (to operate on qubits in the real world).

  Do the answers contradict themself?

No. The person who appeared to be saying "you can't apply the operation" just meant that the algebra you do to apply the operation won't start by factoring the state. When doing algebra you can't apply the operation in the simple way that you'd use when the qubits factor.

  Why can't we just do $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$?

You can! $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$ is equivalent to $(A \otimes B) (|00\rangle + |11\rangle)$. To apply a Hadamard operation to one qubit while leaving the other alone, set $A=H$ and $B=I$.

  Alice has only 1 qubit, but U⊗I acts on 2 qubits. How does it work physically?

Alice just does whatever she would do to apply $U$ to her single qubit. That applies the operation $U \otimes I$ to the system of two qubits.


Major edit of my original:

A naive reading of your question seems to be, let $P$ be the problem

  $P=$ Given a language, $L$, is it decidable?

Then you ask

  Is $P$ decidable?

As D.W. and David have noted, the answer is, "yes it is", though we don't know which of the two trivial deciders is the right one. In order to frame your problem so that it's not quite so trivial, I'd suggest this. First, let's restrict things slightly by considering only those languages $L(M)$ which are the languages accepted by some TM $M$. The reason for doing this is that if a language is not accepted by any TM, then it's not r.e. (recognizable) and so can't be recursive (decidable). Then we can recast $P$ as

  $P'=$ Given a description, $\langle M\rangle$ of a TM, $M$ is $L(M)$ decidable?

Now $P'$ is a language of TM descriptions, rather than a language of languages as $P$ seemed to be (under a generous interpretation), and it's now perfectly reasonable to ask whether the language $P'$ is decidable. Under this reading, the language
$$
\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}
$$
consisting of TM descriptions is not decidable. This is an easy consequence of Rice's Theorem. So now we have two answers: my "no" and D.W.'s "yes", depending on the interpretation.


What is the time complexity (upper bound) for this simple recursive function?

Let's say the time of FindMax is $T(n)$ where $n$ is the size of array A. Notice, that FindMax access only the part of array between $i$ and $j$.
Look at the pseudocode step by step. The first if is just comparison, so it's O(1). IF comparison is true, returning is O(1) (exit recursion step). The else step is doing again some arithmetic things which is O(1) and then calling three functions: max with time O(1), FindMax with time $T(n/2)$ and again FindMax. The time is the half, because again those function are "working" on the half of the original array. This gives the recursion $T(n) = O(1) + 2T(n/2)$. Using the master's theorem we get $T(n) = O(n)$ see here. Another proof without using the theorem mentioned above is by induction, pretty straightforward for this relation.


Why does not valiant's reduction show NP=RP?

As you state, Valiant shows how to construct, given a CNF $\varphi$, a polynomial size matrix whose permanent is a (known) multiple of the number of satisfying assignments of $\varphi$. Unfortunately, this matrix is not non-negative.

Given a non-negative matrix, you can determine whether its permanent is zero or not using an algorithm for bipartite perfect matching; and you can efficiently estimate its value. The same doesn't hold for general matrices.

Valiant further shows how to construct, given a CNF $\varphi$, a polynomial size 0/1 matrix, from whose permanent you can deduce the number of satisfying assignments of $\varphi$. However, the formula is not as simple as before, and in particular, neither bipartite perfect matching nor the efficient permanent estimation algorithms can determine whether $\varphi$ is satisfiable or not.

For details of a later version of this last reduction, see Section 5.1 of Ben-Dor and Halevi, Zero-One Permanent is #P-Complete, A Simpler Proof.


Under what kind of oracles are $P$ and $NP$ equivalent?

It's not about strength: the Baker-Gill-Solovay nonrelativization result relativizes (hehehe), in the sense that

for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B\not=\mathsf{NP}^B$, and

for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B=\mathsf{NP}^B$.

What matters more - or at least, what matters more in a way we can understand - is the genericity/randomness properties of the oracle. Specifically, the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ has full measure, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently random." If I recall correctly, the same is true for genericity: the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ is comeager, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently generic." Both of these notions can be made precise. For a concrete example, Chaitin's constant and its relativizations are sufficiently random to separate $\mathsf{P}$ and $\mathsf{NP}$.

So what about the halting problem specifically? Well, the exact structure of the halting problem is rather dependent on the way we choose to enumerate Turing machines, and we can in fact whip up an "appropriate" enumeration whose associated halting problem goes whichever way we desire. So I suspect that it's hard to say anything here.

This leaves open the question of how weak we can make an oracle with respect to which we have $\mathsf{P}=\mathsf{NP}$ (or $\mathsf{P}\not=\mathsf{NP}$ for that matter). The Baker-Gill-Solovay argument gives us the non-highness result that for any non-polytime-computable $A$ we can find $B,C$ to which $A$ is not polytime-reduciblesuch that $\mathsf{P}^B=\mathsf{NP}^B$ and $\mathsf{P}^C\not=\mathsf{NP}^C$. (Incidentally, note that "high" and "low" are technical terms which I'm misusing here. I'm rude like that.)

Now the above isn't as satisfying as one might hope since the $\le_p$-degrees are rather "spread out." We might hope for some results "closer to home." For example, in an earlier edit I suggested examining the behavior of minimal degrees with respect to polynomial-time $m$-reducibility, where "minimal" means "nonzero but not strictly above any nonzero degree" (while this clashes with the standard order-theoretic meaning, it is standard in computability theory). I just realized that this is vacuous: there are no minimal polynomial-time degrees, with respect to either $m$- or $T$-reductions, at all! This was proved by Homer, following a result of Ladner.
Just to wrap up this coda, Homer subsequently observed (and this was followed up by Ambos-Spies) that things are less trivial with respect to so-called honest reductions; honesty is a bit technical, but the basic idea is to rule out situations where disproportionately much of the information about a set is concentrated in a small region of the oracle computing it. It turns out that there is a tentative connection between minimal degrees with respect to honest polynomial reductions and the $\mathsf{P=NP}$-problem. To my understanding this turned out to be a red herring, but it's still very neat!


Undergrad resources for identifying regular languages with Myhill-Nerode matrices

I wanted to make this a comment, but it is too long.

First, your definition of the matrix is poorly written and probably wrong. There is no reason to introduce indices $i, j$. My guess is that the right definition is the following:
$T$ is the infinite matrix $(T_{u,v})_{u, v \in A^*}$ defined by
$$
  T_{u,v} = \begin{cases}
    1 &\text{if $uv \in L$}\\
    0 &\text{otherwise}
            \end{cases}
$$
Next, your claim

  $L$ is non-regular if and only if all rows of $T$ are distinct

is wrong. Take $A = \{a, b\}$ and $L = \{ u \in A^* \mid |u|_a = |u|_b\}^1$. Then
$T_{1,v} = T_{ab,v}$ for all $v \in A^*$, so the rows $T_{1, -}$ and $T_{ab,-}$ are equal although $L$ is not regular. What is true however is that $L$ is regular if and only if $T$ has finitely many distinct rows.
${}_{\text{(1) $|u|_c$ denotes the number of occurrences of the letter $c$ in $u$.}}$

References. The matrix $T$ is used in the larger setting of noncommutative formal power series under the name of Hankel matrix. Here is a good reference, but I am afraid it is not really appropriate for undergraduate students.

[1] J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0


Sure.  That's fine.  Nothing wrong with that.  Transport-layer protocols (such as UDP or TCP) use port numbers so that you can run multiple applications on the same machine without any difficulty.


Are NP problems lower bounded by exponential order of growth?

First of all, every problem in P is in NP, and so we need to change your question to involve NP-complete problems rather than just NP problems.
The Exponential Time Hypothesis states that 3SAT requires exponential time $c^m$ for some constant $c > 1$, where $m$ is the number of variables. The Strong Exponential Time Hypothesis states that $k$SAT requires exponential time $c_k^m$, where $c_k \to 2$.
However, your conjecture is unconditionally false. Consider the language $L$ consisting of all pairs $\langle x,y \rangle$ such that $x$ is a 3SAT instance on $m$ variables (in particular, $m \leq |x|$), and $y = 0^{|x|^{100}}$. The language $L$ is clearly NP-complete, but it can be solved in time $2^m \mathit{poly}(n) = 2^{n^{1/100}} \mathit{poly}(n)$, where $n$ is the input size.
The Exponential Time Hypothesis does imply that every NP-complete problem requires time $c^{n^\alpha}$, for some $c>1$ and $\alpha>0$. This kind of running time is sometimes called subexponential time, but unfortunately this expression has several different interpretations, depending on context.


Why is the graph inside Graham Scan always planar

The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest.

See this for a good visual.


When $X$ is distributed uniformly over a domain of size $n$, then Shannon entropy, collision entropy and min-entropy are all equal to $\log n$. In a sense, all of these parameters measure the amount of uncertainty in $X$.

In contrast, your proposed definition is always between $0$ and $1$, tending to zero as $X$ gets more unpredictable. This is quite different from other notions of entropy, in which zero stands for predictable.


First of all, you are fundamentally confusing the purpose of RAM and hard disk. RAM is the only part of memory that CPU can access. Hard disk exists to expand the capacity of RAM as well as store the data permanently (data on RAM is transient).

How it works -

The computer generates an executable and stores it in the hard disk. It is just a passive program right now.
Another process (already in memory and currently running) calls the program you just created using the access path (full psth + name) in the filesystem. This is a system call; an interrupt is issued and control is transferred to OS.
OS decodes the path to get the actual location(s) on hard disk where the program data blocks are stored. Hard disk is treated as any other I/O device; it vouches for CPU time like any other I/O device. Here, OS has two choices:

either it needs to fetch data from hard disk each time hard disk has some to give (hard disk announces it by issuing interrupts) and store it in RAM. But with ever faster hard disk speeds nowadays, frequency of interrupts can be high enough to be inefficient for CPU.
second option is that CPU, while issuing the read command for program data blocks, also specifies the RAM memory addresses to which hard disk should directly copy its data (Direct Memory Access). Since CPU, I/O devices (including hard disk) and memory all share common bus, data can be transferred one at a time. Moreover, CPU meanwhile also has other processes (in RAM) to run while data is being copied by hard disk to RAM. Thus, both CPU and hard disk take turns when copying data to RAM. Here, DMA would be faster if CPU is idle or requires less memory accesses. When hard disk has completed writing data to RAM as specified by CPU, it issues interrupt to CPU to tell it that it has completed its task.

Take note above that CPU has never accessed the data of hard disk directly. The hard disk works the same way as any other device like keyboard or modem would work (via interrupts etc). Now after hard disk has copied data and interrupt generated, OS assigns stack memory and other resources for this newly created process and inserts it into the queue of active processes.

That is why when creating small beginner programs, we can never save the state of programs. We create some variables while the process is running and modify them, but never explicitly store them on the hard disk (unless engaging with the file handling aspect). When we destroy the program all the memory is lost. and all the read, write operations of a language are merely wrappers around the system calls provided by the OS so as to make the code portable across several operating systems (since system calls of each are different). These read/write/open/close system calls are requests for OS to let us access a file on hard disk, different from the RAM.

As to your question about logical addresses, it is a little ambiguous as to what you want to say. Logical addresses are used in reference to RAM by programs, and usually refer to the program's view of its memory. For a program, its logical addresses may start from 0, but that doesn't translate into the fact that all programs start at physical address 0 of RAM! You are right that CPU has to process data, but it needs some data at all to process, with is stored in RAM. The addresses provided by program code are logical (say, get data stored in location '7 + start of program') and CPU has to calculate its actual physical address to work upon (i.e. replace 'start of program' with the base address of process code blocks in RAM).

Thus, logical addresses have nothing to do with hard disks.


Typically $\bar{1}$ represents the vector of 1s. In this case, $A\bar{x} \ge \bar{1}$ enforces the vertex cover constraint. The two formulations are the same, except the latter uses a more compact matrix notation to represent the inequality for each of the $j$ variables.


Semi-decidable problems with linear bound

For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)


Running time of a nested loop with $\sum i \log i$ term

$$F(n) = \sum\limits_{i = 4}^{n^2} \sum\limits_{j = 5}^{3i\log i}C = C\sum\limits_{i = 4}^{n^2}(3i\log i - 4) = 3C\sum\limits_{i = 4}^{n^2}i \log i - \Theta(n^2)$$

For asymptotic analysis, we can start the summation from $i = 1$ instead of $4$.  Let

$\begin{align}
T(n) &= \sum\limits_{i = 1}^{n^2}i\log i = \sum\limits_{i = 1}^{n^2}\log {i^i} \\
&= \log {1^1} + \log {2^2} + \log {3^3} + \dots + \log {(n^2)^{n^2}} \\
&\le n^2 \cdot \log (n^2)^{n^2} \ \ \text{(there are \(n^2\) terms)}\\
&= 2n^4 \log n \\
&= O(n^4 \log n)
\end{align}
$

Now, since $f(x) = x\log x$ is a continuous increasing function in $x \in [1, \infty)$, you can verify that :
$\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \ \ $ (changing  $i$ to $x$ simply because $x$ looks better when integrating).

According to Wolfram, $\int\limits_{1}^{n^2}x\log x \ dx = \frac{1}{4}\left(n^4 \log \left({\frac{n^4}{e}}\right) + 1\right) = n^4 \log \left({\frac{n}{e}}\right) + \frac{1}{4}$

Therefore, $\sum\limits_{x = 1}^{n^2}x\log x = \Omega(n^4\log n)$.

Combining the upper and lower bounds, we have $T(n) = \Theta(n^4\log n)$

Overall, $F(n) = \Theta(n^4\log n) - \Theta(n^2) = \Theta(n^4 \log n)$.

So, your loops have complexity $\Theta(n^4 \log n)$.

Remarks:
1. You can show the lower and upper bounds in a similar way by observing that:
$\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \le \int\limits_{0}^{n^2}(x+1)\log {(x+1)} \ dx$
2. For the above inequalities, you can use the method of Riemann sum (use the left and the right Riemann sums to see the two bounds). Draw unit-width rectangles on an increasing function to see these bounds.
3. I have done some implicit simplifications, such as just ignoring the constant $3C$ term, or starting the summation from $1$ instead of $4$ since we are dealing with $\Theta$. I have also made the common but slight abuse of notation when equating or subtracting $\Theta$ terms, without affecting the answer.


Why can't we reduce register automata to symbolic automata?

The basic difference is that register automata have a memory while symbolic finite automata do not. Over an infinite alphabet this gives RA a power that can't be replicated in SFAs. Symbolic automata can only recognize unary predicates, and other relations are much harder.

For a simple example, consider the language $L=\{xx\mid x\in\Sigma\}$. That is, the set of all strings of length 2 that repeat a character. There is an easy RA to achieve this: state 0 reads x and stores it in register 1, going to state 1 (i.e. $q_0\to (q_1,0,\mathsf{right})$), and state 1 goes to the accept state 2 if the current value matches (that is $(q_1,0)\to (q_2,\mathsf{stay})$, and $F=\{q_2\}$) and rejects otherwise.

Suppose that a SFA accepts this language, where $\Sigma$ is infinite. Because for all $x\in\Sigma$, $xx\in L$, every character must initially be permitted. That is, for all $x\in\Sigma$ there is a state $q_x$ such that $(q_0,\phi,q_x)\in\Delta$ and $\phi(x)$ is true. Since $\Delta$ (and $Q$) are finite, there are clearly a finite number of such states $q_x$. But they are being tasked with distinguishing an infinite number of possible outcomes, depending on which $x$ was read. More precisely, by the pigeonhole principle there must exist $x\ne y$ such that $q_x=q_y$. Then the SFA must accept the string $x$ starting from $q_x$, since $xx\in L$, but that means it also accepts the string $x$ starting from $q_y$, so $yx\in L$ as well and hence the SFA doesn't correctly recognize $L$.


Doron ZEILBERGER's P = NP computer proof

That paper is a hoax. If you look, it just throws numbers around for a huge polynomial bound, purports to solve a problem by "Laurent polynomials" without any clue on how they relate to the problem, shifts to integrals and estimates them by numerical means "sufficiently precisely" (and that is supposed to give the huge degree polynomial somehow). And nowhere are the 3000 hours of CRAY time to be seen.


Defining function for arithmetic expressions

Hint: Here is one example

$A($ a1 - a2$, s) = minus(A($ a1$,s),A($ a2$,s))$

or alternatively

$A($ a1 - a2$) = \lambda s . minus(A($ a1$,s),A($ a2$,s))$

where $minus$ is the substraction in $\mathbb Z\cup\{\bot\}$


Source and Destination IP of TCP connection

If you consider the format of the TCP-IP datagram.

Source Address: The 32-bit IP address of the originator of the datagram. Note that even though intermediate devices such as routers may handle the datagram, they do not normally put their address into this field—it is always the device that originally sent the datagram.

Destination Address: The 32-bit IP address of the intended recipient of the datagram. Again, even though devices such as routers may be the intermediate targets of the datagram, this field is always for the ultimate destination.

You can get more understanding here.


Why this Turing machine can't be an acceptor for the following language?

You are not considering the fact that $M_1(M_2)$ and/or $M_2(M_1)$ might not halt. When this happens your Turing machine for $L$ will be stuck executing step 1.


The automaton accepts all non-empty strings in which the last symbol $\sigma$ appears at least twice, and all symbols appearing between its penultimate appearance and its last appearance are smaller than $\sigma$.


consistent heuristic - does it always exist?

The zero heuristic is trivially admissible, as you've noted. It's also trivially consistent as long as all step-costs are non-negative: if $h(x)=0$ for all $x$ and $c(x,y)\geq 0$ for all $x$ and $y$, then
$$
h(x)\leq c(x,y) + h(y)
$$
for all $x$, $y$.


Known facets of the Travelling Salesman Problem polytope

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP polytope efficiently representable.

Their paper is follow up to the classical 1988 paper by Yannakakis, who showed the same result but only for polytopes that satisfy a certain symmetry condition.


Asymptotics of the number of words in a regular language of given length

The argument you have sketched appears to be in line with Richard Stanley's treatment of the Transfer-Matrix Method in Enumerative Combinatorics, Volume 1 (link: pp 573; print: pp 500).

He starts with the generating function, and unpacks it by considering digraphs and permissible and prohibited factors. He then abstracts to free monoids, where he uses a refined version of the sums you gave to prove:

  4.7.11 Proposition Let $B$ be a subset of $A^*$ that freely generates $B$. Then $B^*(\lambda)=(I-B(\lambda))^{-1}$

After working through some applications, he likewise closes the section by discussing Hadamard products in relation to horizontally-convex polyominoes.


Why are types and grammar non-terminals so distinct?

About operators and syntax extensions

Dave Clark comment is correct: "types is about semantics, grammar
non-terminals is about syntax." This said, you are perfectly right
that the semantic and syntactic issues could, possibly should, be both in the hands of
the programmer, or at least of the project designer. Indeed, that has
actually been the case for various languages, including older ones from
the early 1970s, when the concept of extensible languages was popular.

But first you should get your concepts rights. Though the addition may
be seen as a built-in function, that is not what characterizes it in
the context of your question. A built-in function is just a function
that happens to be predefined in the standard environment of the
language. For example sqrt (square-root) or abs (absolute value)
may be builtin functions in a language, but they are still defined
implicitly as function sqrt(r:real):real; .... and function
abs(z:real):real; ...., though abs is often overloaded to work also
with integer.

There could also be a built-in function plus, possibly overloaded, that would
perform additions. But who would use it. We prefer to write it with
the operator +.

There are built-in operators such as +, and one might want the programmer to be able to define new ones.

The use of operator has to do with the way we write things. It is a
syntactic issue. Using them does not help you to do more, but it
allows you to say it differently, if you think that makes things
easier to write or read and understand, or simply makes them closer to
standardized notations.

So you should see operators as nothing more than a special notation
for calling some function, which may or may not be extended to new
functions. Defining operators has nothing to do with typing.
Whatever semantic problems it causes can be caused as well with the
simple use of functions. But if it extends the syntax, it may create
syntactic problems such as grammatical ambiguity.

Operators are often overloaded, like + that can be used for both
integer and real, and possibly for boolean disjunction or set
union. But functions can be overloaded as well. It is only a
notational issue. And one constraint, for both functions and
operators, is that you cannot overload them using twice the same type
signature, but that is a semantic problem: finding which fuction is
actually associated with what is written, functionally or with an
operator.

Regarding extensions of a language, there are many ways to do it.  One
way is to allow overloading of existing operators with new function,
having new type signatures. Some languages limit it at that.

Another possibility is to introduce new user defined operators,
possibly written as a sequence of characters, such as >=, or **,
or and, and then associate functions with them.  This can be done
without touching the grammar, by defining for example the
associativity (left or right) and the precedence level of binary
operators, or the position of the argument for unary ones. Analysing
the actual structure of expression could be handled separately from
the context-free parsing of the syntax, thus not be really a parser
issue. but more associated with expressions evaluation.

A third possibility is to allow the introduction of new rules in the
grammars, but that requires appropriate techniques to properly
associate semantics to these rules, which can be very open, and thus
quite complex to handle.

Note also that we tend to see operators as unary prefix and binary
infix, but there are many other forms, such as postfix for factorial $n!$,
or the absolute value notation (endfix?): $|x|$, and more.

A last point is that, though the grammatical structure shoud remain
manageable, mostly for users to understand, the syntactic complexity
is not a major issue for modern syntax analysis techniques. I seems
that there is a tradition of trying to have very efficient parsers,
but it is not clear that the performance bottleneck is still there
(maybe for some programming environments). We can analyze quite
efficiently ambiguous languages.

Ambiguity may be a problem, when too frequent. But frequent ambiguity
can probably be detected statically, event though the problem is not
decidable in general (I do not know whether there has been work in
that direction). Then, ambiguity can be treated by the parser
as a syntax error, requiring the programmer to write things
differently.

Actually, it may well be that the syntax is not ambiguous, but the
typing is. While a big expression is parsed correctly, the overloading
of functions or operators can be such that there is ambiguity as to what
code (function body) should actually be understood.

A very simple example is:

function f(x:S):T1; ....
function f(x:S):T2; ....
function g(z:T1):T; ....
function g(z:T2):T; ....
declare u:S, v:T .....
  .....
  v := g(f(u))

It is not possible to decide which pair of functions f and g is
actually being called, because the typing of the expression is
ambiguous.

A language such as Ada (at least in its first release) allows such
ambiguity that is detected by the compiler. I would consider it a
semantic ambiguity, though some people consider type checking as part
of syntax. Whatever the case, is that any better or any worse than
syntactic ambiguities that would be detected by the parser.

I avoided giving concrete examples (there are many) because my memory
may fail me and I and not sure which language allows what. When I need
to know, I look.

About types

You question is mixing a lot of (I think) unrelated issues. So It is
taking me time to sort it out.

The existence of operators and their properties is not really related
to typing, as I explain above.

I think I finally understand what you are trying to say with the
example using bool as non-terminal.

However I fail to see how it relates to the use of operators, which
comes first in your question.  And I do not see what it is supposed to
bring you in terms of programming power.

This said, there is something like it that is possible, associating
types with non-terminal. It is actually a way to integrate type
checking in the syntax, though I do not know that it has ever been
used for programming languages. It is used for natural languages, and
is called feature structures. For example it can be used to test
number, gender or case agreement in natural language analysis, which
is quite close to type agreement.

The idea is to associate parameters with non-terminal, which then
become some kind of predicate. It can be seen as using an infinite
number of CF rules, all derived from a finite set by instantiating the
parameter to all possible values. But actually it is used by
instantiating the parameters as needed with unification.

This is possible because CF grammars may be seen as a special type of
Horn Clauses with binary predicates (the two arguments are the indices of the ends of the corresponding substring in the program text). Adding a type arguments to the
grammar non-terminals is just adding a third argument to the
corresponding Horn clauses.


How do I get and/or verify a formal Grammar for a given formal Language?

You don't really need the various $X$ nonterminals, just use rules $B_iA_i\to A_iB_i$ instead.

For correctness, use induction to show (1) that you can reach $aB_1(A_1B_1)^k(A_2B_2)^{k+1}$, and from there $a^{k+1}b^{k+1}a^{k+1}b^{k+1}$, for all $k\ge 0$, and (2) that all generated words have the required form. For the second part, try to find some auxiliary conditions (e.g. numbers of $A_i,B_j$ match; if a factor $B_1A_1$ is not rewritten to $A_1B_1$ before the $B_i$ is replaced by $b$, the derivation gets stuck; etc).


Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP?

NP is the set of problems that can be verified in polynomial time, i.e. there is a polynomial-time algorithm that can verify a purported solution. P is the set of problems that can be solved in polynomial time, i.e. there is a polynomial-time algorithm that can find a solution.

“The problems in NP are those not able to be solved in polynomial time” is completely wrong. This is not at all what NP means. The N in NP is for “nondeterministic”, not for “not”. A problem in NP may be solvable in polynomial time — P is a subset of NP. The question “P = NP?” is in fact whether all problems in NP are solvable in polynomial time.

The set of problems that cannot be solved in polynomial time is the complement of P.

Note that “problem” has a specific technical meaning: it's a decision problem, i.e. an function from some input space to $\{\mathrm{yes}, \mathrm{no}\}$.

Counting is not a decision problem, so it doesn't fit in the classification that includes P and NP.

If you found a decision problem that cannot be solved in less than $2^n$ steps where $n$ is the size of the input, then that problem would not be in P. It might not be in NP either: it would only be in NP if there was a way to verify a solution in polynomial time.


Is there an existing algorithm for this type of sorting?

This is called bucket sort: split your data range into $k$ "buckets" ($O(k)$), put the data into the buckets ($O(n)$), sort each bucket (however you like), then concatenate all the buckets ($O(k)$). If the sorting is faster than $O(n \log n)$, then the whole algorithm runs faster than any comparison-based sort possibly could!

The problem is that it depends on the distribution of the data. If 99% of your book titles start with A, this gives no real benefit at all! And it doesn't work on data that can't be divided into buckets.

A variation of this, "radix sort", is basically the same except in binary (and with some extra recursion). It runs in $O(wn)$, where $w$ is the bit length of your data (the "word size").


Decision tree lower bound for finding two array elements summing to zero

You're right that there are only $\binom{n}{2}$ many inequivalent solutions. Fortunately, $\Omega(\log \binom{n}{2}) = \Omega(\log n)$, so there isn't much difference between $\binom{n}{2}$ and $n^2$, in this regard.

However, this is a pretty bad lower bound. You haven't specified which queries are allowed, but assuming you're allowed to compute signs of constant degree polynomials, then I would expect an $\Omega(n\log n)$ lower bound, since the similar problem Element Distinctness has such a lower bound. This also matches the upper bound obtained by sorting (assuming your model supports this).

Indeed, this is just 2SUM (a sibling of the more famous 3SUM problem), and an $\Omega(n\log n)$ lower bound was proved by Chan, Gasarch and Kruskal in their paper Refined Upper and Lower Bounds for 2-SUM.


Doubts about infinite language decided by a turing machine

Some infinite languages are decidable, some are not. The algorithm that you give, however, doesn't work, for two reasons:

When the input is not in a language, you never find out.
It is not always possible to enumerate all the words in $L$. A language $L$ for which this is possible is known as recursively enumerable (r.e.), and by many other terms. An example of a language which is not r.e. is the language of encodings of Turing machines which don't halt on the empty input. That is, $\langle M \rangle$ is in the language if $M$ never halts when running on the empty input.

In your specific example, there is a very simple Turing machine accepting $L$. The Turing machine examines the first symbol, accepts if it is $a$, and rejects otherwise.


Factorial usage within proof using the pumping lemma

Let's choose a different word in step 2, say $s' = 0^a1^b$, where $a$ and $b$ depend on $P$ and $a \geq P$ (to force an $y$ that has the form $y=0^m$).

It's important to show that for any length $m, 1\leq m \leq P$ there is no valid division $s' = xyz, y = 0^m$ (valid means it fulfils the conditions of the pumping lemma).

So for every such $m$, we need an $i$ such that:
$xy^iz = x0^{im}z = 0^{a-m+im}1^b  = 0^{a+(i-1)m}1^b {! \atop =}  0^b1^b$.
This means that $m$ must divide $b-a$ for every $m$. One number $b-a$ that fulfils this, is $P!$, so e.g. $a=P$, $b=P+P!$, the least common multiple of $1,\dots,m$ is another possible choice for $b-a$.


What are some concrete (near-)"worst-case" examples of subset-sum?

The naive dynamic programming complexity is $O(sN)$ where $s$ is the integer bit precision, $N$ is the set cardinality. With some slight tricks in memoization cutting the precision constant in half, an instance with 64 bits precision should be solvable without much optimization in a linearly increasing fashion and as fast as memory access allows.

However, the naive method for small $s$ but large $N$ is dynamic programming which has subjectively large memory requirements. In practice this is the constraint that is prohibative for large instances skewed towards small precision, since many of the non-cryptographic applications I can think of deal with embedded systems having low memory and real-time constraints that limit non-uniform memory access.

At the other end of the spectrum if you have PiB subset-sum instances with small $s$ but very large $N$, the same issues arise as in sorting. These instances are incredibly 'easy' from a theory perspective but the micromanagement constant factor details dominate such as cache usage, memory walls, parallelization, bandwidth saturation, and code/data locality. Many of the techniques for fast solvers become invalidated at that size due to either reliance on a central memoization table or chaotic memory access.

The major applications for subset-sum that I know of are cryptographic in nature, which necessitates that the natural 'real-world' integer precision is far larger than 64 bits. In addition, most of the various manufacturing and finance applications do encounter the need for integer precision much larger than 64 bits as a way to actually encode the problem without blowing up $N$ in a very non-linear manner. This is required even though the original 'real-world' quantities are far less than 64 bits.

So hard subset-sum instances with 64 bit precision don't exist in the manner that I think you want to test. If an analogy helps, this is similar a complexity outcome to finding the prime factorization of a very large number but limited to prime factors with 64 bits of precision rather than the general case.


Not at all correct. For example for the naive Quicksort algorithm, anything close to the worst case is very, very, very rare. If the average time was between best and worst case, nobody in their right mind would use Quicksort.


Can a Turing Machine run for infinitely many steps and halt?

The answer to your question, whether a Turing machine can run for infinitely many steps and subsequently halt, is negative. If a Turing machine runs for an infinite number of steps and never halts, then it just never halts. It runs forever. A Turing machine halts if it at some step, it halts. If this never happens, then it doesn't halt, and instead runs for infinitely many steps.

One can define infinite time Turing machines for which infinite computations do result in an output, but these are different from the ordinary Turing machines taught in your class. In particular, infinite time Turing machines can "compute" uncomputable functions.


Sieving to compute first values of totient function

The complete formula for Euler's totient function is
$$
\varphi(n) = n\prod_{p|n} \left(1-\frac{1}{p}\right),
$$
where the product goes over all prime factors of $n$. Hence you essentially need to factor $n$ in order to compute $\varphi(n)$. You can do it in any way you wish.

Computing $\varphi(n)$ is believed to be as hard as factoring $n$ (and is indeed as hard in some special cases, for example when $n$ is a product of two primes).

You can use a sieve to factor all numbers up to $n$. The idea is to go from $2$ to $n$; whenever encountering an uncircled number $p$ (the initial state), this number must be prime, and we can circle all its multiples. Moreover, we can divide these numbers by $p$, the appropriate numbers by $p^2$, and so on. At the end, the uncircled numbers are all primes, and all other numbers have been factored.

You can easily adapt this algorithm to compute the totient function directly. Every time you encounter a new prime $p$, you divide all its multiples by $(p-1)/p$. After going through all numbers up to $n$, all uncircled numbers are prime, and so their totient function is easy to compute.


How to show that two vertices in a connected component are in the same set? (bi conditional)

Below are two approaches to your problem.

detailed semi-formal proof

Since you've provided a minimal context, I will state my assumptions then provide a solution.
Moreover, I will use very basic loops rather than the fancy for-each loop since they are easier
to prove correctness with ─more accurately, easier for me with my current knowledge.

We are assuming simple undirected graphs: ie., pairs (V, E) of a set V of vertices
and a symmetric relation E ⊆ V × V.
Two vertices are “connected” precisely when there is a path along E between the two:
x ~ y  ∶≡ (∃ n : ℕ • x Eⁿ y) ─where the bullet serves to separate the bound variable
of the quantifier and the body of the quantifier, and exponentiation is iterated relational
product.
A “connected component” is a subgraph in which any two vertices are connected, and which
is connected to no additional vertices in the supergraph. For our needs, we only
consider connected components arising from subsets of vertices.

 connected-component
⇔ (∀ x,y :  • x ~ y) ∧ (∀  : ℙ V •  ⊆  ∧ (∀ x,y :  • x ~ y) ⇒  = )
⇔ (∀  : ℙ V • (∀ x,y :  • x ~ y) ∧  ⊆  ⇔  ⊆ )
⇔  is an ~-equivalence class

Note that ∧ means “and”.
Make-set assigns the emptyset ∅ to each vertex, in some look-up table.
We assume this to be the case at the very beginning and so need not worry about it.

Find-set looks up the set that is associated to a vertex, in the aforementioned look-up table.

Union(x,y) alters the set associated to x by unioning it what the set associated to y,
and does so as well for y. In particular, after this command we have
 Find-set x = old-Find-set x ∪ old-Find-set y.

The post-condition of the program is

∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

i.e.,

∀ x : V • connected-component (Find-set x)

That is, the algorithm assigns the connected components to the associated sets of the vertices.
Alternatively, it is: Find-set x = the ~-equivalence class of x.
From the post-condition,

  ∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

The simplest thing to do is to replace a constant, say E, with a new variable, and relate it
to the constant to obtain an invariant.

P ∷  ⊆ E  ∧
    (∀ x : V •
       Find-set x
       = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))})

So it is obvious that the post-condition is obtained once we've arrived at the conclusion
E ⊆ . So a good idea is to increase  until this condition is true.
Moreover, the invaraint needs to hold before the loop and we can do this by setting
 ≔ ∅: indeed ∅ ⊆ E and intially every vertex is assigned the emptyset which is what
is needed since,

  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁)))}
=⟨ initial value of  ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ ∅ xᵢ₊₁)))}
=⟨ definition of empty set ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • false))}
=⟨ “for all i, we have false  ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ false)}
=⟨ “false ∧ stuff ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • false)}
=⟨ “there is some stuff yielding false ≡ false” ⟩
  {y : V ❙ false }
=⟨ there are no y that make false true ⟩
  ∅
=⟨ initial value of Find-set ⟩
  Find-set x

So, to be very explicit, we assume that before the algorithm is run, we have

∀ x : V • find-set x = ∅.

Anyhow, the previous paragraph informs us that the algorithm we are looking for has the shape

{Pre: (∀ x : V • find-set x = ∅) }
 ≔ ∅
; {Invariant:  ⊆ E  ∧
(∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y           ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
while ¬ E ⊆  : do-stuff
{Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

Note that it is common to place “assert” statements within curly braces.
C♯ for example documents them in the form Contract.Assert.IsTrue(...).
It seems the only thing left to do is find an implementation of do-stuff.
Well, the loop terminates if we make the loop guard ¬ E ⊆  false.

By the invariant, we know ♯ ≤ ♯E and so increasing  will do the job.
We can choose an edge of E, it doesn't matter which one as long as it's one we haven't
considered it, and add that to . What, are there even such edges!?
Well, by the invariant, we have  ⊆ E ∧ E ⊈  within the loop, which implies
E -  ≠ ∅, whence there are such edges.

Hence, one possible candidate for do-stuff is

 (u,v) ≔ choose an edge from E -
 ;  ≔  ∪ {(u,v)}

The candidate is enough and we are done deriving our algorithm, “provided” that this choice
of do-stuff does not ruin the invariant.
It clearly does ruin the invariant since we have not altered the find-set for these two
vertices.

The final result is

 {Pre: (∀ x : V • find-set x = ∅) }
  ≔ ∅
 ; {Invariant:  ⊆ E  ∧
 (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
 while ¬ E ⊆  :
   (u,v) ≔ choose an edge from E -
   ; if find-set u ≠ find set u then union(u,v)
   ;  ≔  ∪ {(u,v)}
 {Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

To relate this to your initial code, consider the following.

 for each i in S : do-stuff
≈
 visited ≔ ∅
 ; while visited ≠ S:
       i ≔ pick an element of S - visited
     ; do-stuff
     ; visited ≔ visited ∪ {i}

Our loop had ¬ E ⊆  and this is tantamount to E ≠ :

  E ≠
=⟨ bi-containment ⟩
  ¬(E ⊆  ∧  ⊆ E)
=⟨ invariant ⟩
  ¬(E ⊆  ∧ true)
=⟨ “stuff ∧ true ≡ true” ⟩
  ¬ E ⊆

We use basic while loops since they are easier to work with is all.
I've never really learned to write correctness proofs for for-each loops.

Hope this helps!

Bi-implication informal argument

The algorithm's post-condition is
find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}.

We show the equality using a bi-implication.

(⊆) ∷

By the construction of find-set, i.e., the way we add elements to the set associated to x,
we know that any added element is connected to x and so
find-set x ⊆ {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}.

(⊇) ∷

We will show by induction that any vertex y at-least n : ℕ edges away from
x must be within find-set x.

Base case: n = 0. Then x = x₀ = xₙ = y and clearly y ∈ find-set x.

Inductive step: if x E x₁ E x₂ E ⋯ E xₙ E xₙ₊₁ = y then by the inductive hypothesis
xₙ ∈ find-set x; moreover, the algorithm ensures find-set x = find-set xₙ.
Now since (xₙ, xₙ+1) is an edge ─a given─, the algorithm ensures
find-set xₙ₊₁ = find-set xₙ but by the previous equalities we then have
y ∈ find-set y = find-set xₙ₊₁ = find-set xₙ = find-set x.

:-)


What is µ A below ~ x in the Fuzzy Logic

Here μ A˜(∙) μA~(∙) membership function of A˜ this assumes values in the range from 0 to 1, i.e.,  μ A ˜ (∙)∈[0,1] μA~(∙)∈[0,1] . The membership function  μ A ˜
(∙)  μA~(∙) maps   U to the membership space M . The dot  (∙) in the membership function described above, represents the element in a fuzzy set; whether it is discrete or continuous.

In classical set theory, it is either 1 or 0.

source:

https://www.tutorialspoint.com/fuzzy_logic/fuzzy_logic_membership_function.htm


Its about pragmatic efficiency.

The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very large N, but instead operate over particular ranges of N.

Heaps

A binary heap can be allocated as a single block of memory if the size of N is known. Even if not known a simple reallocation strategy of doubling the allocation is very efficient. Alternately the blocks can be designed to fit within a memory page having a well-known capacity, and then assembled into balanced block trees.

This has several advantages:

Keeping the data-structure dense and co-located decreases the likely-hood of a cache miss at the processor level, or a page miss at the memory level - both slow overall execution.
Organising the tree to follow a predictable memory addressing pattern permits the index to be calculated within the processor and does not require a memory load.
By minimising the need to reserve memory, memory management book keeping overheads are reduced.

And a few flaws:

A dense structure incurs an all or nothing memory overhead. An entire page/block must be allocated for even a heap of a single element.
Modification necessitates element copying - which may not be cheap. A complex object may have internal bookkeeping that is memory location dependent, and must be updated when moved/copied.
If the capacity of the heap is exceeded a costly re/allocation operation must be performed.

Trees

Conversely a tree is generally constructed of nodes which are individually small in size and the nodes are linked via memory addresses. Removing a node is as simple as redirecting the pointers around the removed node, notifying the memory book keeper that it is no longer needed, and then applying a re-balancing operation that adjusts those addresses to achieve a balanced tree.

This has its advantages:

The tree has exactly the capacity for what is held.
The tree can be allocated in highly fragmented memory spaces.
No elements are copied when modifying the tree (excluding creating the node itself).
Memory bookkeeping is paid as needed.

But has its disadvantages:

Each node must at least identify its two children, and other book keeping state. Usually 3*sizeof(pointer).
Tree traversal requires memory access to read the location, then another memory access to access the next node.
Tree nodes are allocated sparsely increasing the chance of a cache-miss, or a page-miss
Much more memory bookkeeping is required.

Simplifications

Note that I have simplified this significantly, and alternate implementation choices could be made:

I could have used block allocation for the tree, forcing the elements of many nodes other than the one being manipulated to be copied around, while simplifying the rebalancing of the tree, and omitting storage/modification of node addresses.
I could have used single element nodes for the heap, sacrificing memory density for minimal element copying.

These would have changed the trade-offs and the total cost of each. In a given context these changes would pay dividends, but outside of that context they hobble the use case with unnecessary work.

Specification

What is most efficient is situational. Thus it is usually best to specify the exact operations needed, and allow implementations to provide that operation in the most contextually efficient manner it can.

So as before if the operation is over expensive to copy objects, I probably would use a red-black tree to offer Heap operations, or some other similar low-copy data-structure.

Conversely if the data in the heap were single bytes, the block encoded binary heap is a clear winner: N * (1byte + 3*ptrsize bytes) vs. Nbytes.


Short notation for Turing machine configurations

This is just a convention. You can write a configuration as the tuple that has the same information. Eg, a possible way to write a configuration is as the tuple
$$Config= (tape,state,pos)$$

where $tape$ is the non empty tape content, $state$ is the current state, and $pos$ is the position of the head.

This is fully equivalent to the method you use, which makes sense for other succinct description of configurations. Tho only thing to bear in mind, is that people are used to the 1-string-head-inside convention you describe in the question, so if you change it, you need to be very clear and explicit about it.


How do context switches factor into CPU utilization?

What is measured as "CPU utilization" is (time CPU working) / (total time). The overheads (like context switches) are part of the (time CPU working). So you might have 50% CPU utilization, of which 5% is context switch time.


Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

This is a partial answer that proves the NP-completeness of your problem, by a reduction from the EXACT-CUT problem for general graphs1.

Given an instance $(G=(V,E),k)$ of the EXACT-CUT problem (that asks whether there is a cut of size $k$ in the graph $G$), we construct a new graph $G'$ as follows.

For each vertex $v\in V$, construct vertices $v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1$ as well as edges $(v_i^0, v_j^1)$ for all $i,j\in\{0,\ldots,m\}$ (so that they form a biclique). Denote $V_v=\{v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1\}$.
For each edge $(u,v)\in E$, construct two edges $(u_0^0, v_0^1)$ and $(u_0^1, v_0^0)$.

Here $m=2k$. Note $G'$ is a bipartite graph.

Now we can see if $(A,B)$ is a cut of size $k$ in $G$, then $(\cup_{v\in A}V_v,\cup_{v\in B}V_v)$ is a cut of size $2k$ in $G'$.

On the other hand, suppose there is a cut $(A',B')$ of size $2k$ in $G'$. Now consider a vertex $v$. Assume $|A'\cap\{v_0^0,\ldots,v_m^0\}|=a$ and $|A'\cap\{v_0^1,\ldots,v_m^1\}|=b$, then we have
\begin{align}
m=2k&\ge a(m+1-b)+b(m+1-a)\\
&=(m+1)(a+b)+\frac{1}{2}(a-b)^2-\frac{1}{2}(a+b)^2\\
&\ge(m+1)(a+b)-\frac{1}{2}(a+b)^2,
\end{align}
which implies $a+b<1$ or $a+b>2m+1$, i.e. $a=b=0$ or $a=b=m+1$. This means all vertices in $V_v$ must belong to the same cut-set. Hence $(\{v\mid V_v\subseteq A'\}, \{v\mid V_v\subseteq B'\})$ is a cut of size $k$ in $G$.

Now we have shown that there is a cut of size $k$ in $G$ if and only if there is a cut of size $2k$ in $G'$, which concludes the proof of the NP-completeness of the EXACT-CUT problem on bipartite graphs.

1 Your reasoning for the NP-completeness of the EXACT-CUT problem is incorrect because you used a Turing reduction while a many-one reduction is required. However, it is not hard to find such a polynomial-time many-one reduction.


This has been answered on the CS Theory StackExchange site:
https://cstheory.stackexchange.com/a/19833/5038

(I'm posting an answer here, so this question does not get treated as a question-without-an-answer and get periodically rotated back onto the front page by the Community user.  Normally, questions without any upvoted or accepted answer are re-displayed on the front page every so often.  Since this question now has been solved answered elsewhere, there doesn't seem any need for that.  As long as someone upvotes or accepts this answer, that should prevent this question from being rotated back onto the front page.  I'm ticking the community wiki box so I won't get any rep from this answer.)


How do I calculate the Nth result of a context-free grammar?

The problem is likely hard, by reduction from SAT.

Let $\varphi$ be a CNF. For each clause $C$, we can construct a production which generates all truth assignments falsifying $C$. By going over all clauses, we can construct a grammar for all nonsatisfying truth assignments. For example, if the CNF is $(x_1 \lor x_2) \land (\lnot x_1 \lor x_3)$, the grammar is
$$
\begin{align}
&S \to 00B \mid 1B0 \\ &B \to 0 \mid 1
\end{align}
$$
This grammar generates $2^n$ words iff $\varphi$ is unsatisfiable. Therefore, by querying the $2^n$'th word, we will be able to tell whether $\varphi$ is satisfiable or not, and so solve SAT.


Predict language from given expression $(b^* (aaa)^* b^*)^*$

A simple counter example can be found for your answer. Take the string $$ababa$$ Here, the alphabet is $\{a,b\}$ and the number of $a$s is a multiple of $3$, yet it doesn't fit into the regular expression.

In the regular expression, $b^*(aaa)^*b^*$ denotes strings that contain an arbitrary (possibly zero length) sequence of $b$s, a sequence of $a$s that is a multiple of $3$ (possibly zero again), followed by an arbitrary length sequence of $b$s.

So, $(b^*(aaa)^*b^*)^*$ is such a sequence repeated over any number of times, including the empty string.

You could call the language as
$$L=\{x|x\text{ contains sequences of consecutive }\\a\text{s and }b\text{s, where the length of each sequence of }a\text{s is a multiple of }3\}$$

over the alphabet $\Sigma=\{a,b\}$.

In general, a language is just some subset of the set of all strings over a given alphabet. Given a language, there need not be any straightforward way of describing it in English. A regular expression, given the alphabet, completely specifies and describes the language.


Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

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

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


Undecidability of a restricted version of the acceptance problem

The complication forbidding the input from being an encoding of a Turing machine is easy to overcome. All you need to do is tweak $D$ a bit, so that instead of accepting an encoding $\langle M \rangle$ of a Turing machine, it accepts some other input which can be decoded into an encoding of a Turing machine, while at the same time not being an encoding of a Turing machine itself.


One variant of 3-partition is the following distinct 3-partition problem, shown to be NP-complete in [1].

Distinct 3-partition
Input: A set $X = \{a_1,a_2,\ldots,a_{3n}\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma_{i=1}^{3n} a_i = nB$, and $B/4 < a_i < B/2$, where $i \in [3n]$.
Question: Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The problem is also NP-complete when $B$ is bounded above by a polynomial in $n$. For an "application", a reduction from the problem is used in [2] to show a certain graph problem is hard.

[1] H. Hulett, T.G. Will, G.J. Woeginger, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, Operations Research Letters 36 (2008) 594–596.
[2] Bonato, Anthony, Jeannette Janssen, and Elham Roshanbin. "Burning a graph is hard." arXiv preprint arXiv:1511.06774 (2015).


What easy algorithms are there for calculating products of cycle decompositions?

Here is how I would do it manually, taking the example of $(123) \cdot (12)(34)$.

Start with a number appearing on the right permutation, say 1. The right permutation sends it to 2, and the left to 3.

Doing the same with 3, we get 4 and then 4.

Doing the same with 4, we get 3 then 1. We have closed a cycle $(134)$.

Now take another number on the right (or left) permutation not already covered – has to be 2. It gets sent to 1 then 2. We have closed a cycle – 2 is a fixed point.

In total, the result is $(134)$.

Now let's compute $(12)(34) \cdot (123)$.

Let's start with 1. It goes to 2 then 1. So it's a fixed point.

Let's try 2 next. It goes to 3 then 4, which goes to itself then 3, which goes to 1 then 2. We have closed a cycle $(243)$. That's the answer.


Is the outer loop in typical bubble sort algorithm precise?

Let's assume that the input has is a reversed array like  a = 5 4 3 2 1.
every iteration of the outer loop all the 5 - 1 - i smallest elements will be shifted one cell to the right(i is zero in the first iteration) and the 5 - i th element will be moved to the 5 - i th cell. as one can see it takes 4 iteration to sort this.

at every iteration of the outer loop, the n - i th element will be moved to the n - i th cell so it will take at most n - 1 iteration and the worst case (descending array) will always take that many iteration ( the last element will be sorted by itself).


Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Hint: Suppose we are given a word $w$ of length $n$ which is not in $L$, and let $w_1,\ldots,w_n$ be the words of length $n$ which are in $L$. A witness that $w \notin L$ is the list $w_1,\ldots,w_n$ (all different from $w$!) together with witnesses that $w_1,\ldots,w_n \in L$.


Define the run-partition number of a permutation $\pi$, denoted $r(\pi)$, using the following process. Let $k$ be the maximal integer such that the numbers $\min(\pi),\ldots,k$ appear in increasing order in $\pi$. Remove them from $\pi$, and repeat the process. The number of rounds it takes to consume the entire permutation is $r(\pi)$.

For example, let's compute $r(62735814)$. We first set aside $1$, to get $6273584$. Then we set aside $234$, to get $6758$. Then we set aside $5$, to get $678$. Finally, we set aside $678$ to get the empty permutation. This takes four rounds, so $r(62735814) = 4$.

How is this representation useful for sorting $62735814$? Take every second run, i.e. $234,678$, and move these numbers to the right to get $51627384$ (edit: in the order they appear in the permutation, i.e. $627384$). Now there are only two runs, namely $1234,5678$, and we can sort the list by moving $5678$ to the right.

Now let me make the following conjecture: For a permutation $\pi$, let $\Pi$ be the set of all permutations that are reachable from $\pi$ within one move. Then $\min_{\alpha \in \Pi} r(\alpha) = \lceil r(\pi)/2 \rceil$.

Given this conjecture, it is easy to show that the minimal number of moves needed to sort a permutation $\pi$ is $\lceil \log_2 r(\pi) \rceil$, and I have verified this formula for all permutations in $S_n$ for $n \leq 8$.

Edit: Here is a different interpretation of the run-partition number which gives a linear time algorithm for computing it, and allows me to sketch a proof of my conjecture, thus verifying the formula $\lceil \log_2 r(\pi) \rceil$.

Consider the permutation $62735814$ again. The reason that the first run ends in $1$ is that $2$ appears before $1$. Similarly, the second run ends in $4$ since $5$ appears before $4$, and so on. Therefore the run-partition number of a permutation is the number of $i$s such that $i+1$ appears before $i$.

We can state this more succinctly if we look at the inverse of the permutation. Consider again $\pi = 62735814$. Take $\pi^{-1} = 72485136$. This permutation has three descents: $7\mathbf{2}48\mathbf{5}\mathbf{1}36$ (a descent is a position smaller than the preceding one). Each of the descents corresponds to the start of a new run. So $r(\pi)$ is equal to one plus the number of descents in $\pi^{-1}$.

What does the operation look like in terms of $\pi^{-1}$? let $B$ be the set of numbers that we move to the right, and $A$ be the set of numbers that stay to the left. We replace the numbers in $A$ with a permutation on $\{1,\ldots,|A|\}$ representing their relative order, and replace the numbers in $B$ with a permutation on $\{|A|+1,\ldots,|A|+|B|\}$. For example, consider the move $\mathbf{6273}5\mathbf{8}1\mathbf{4} \mapsto 51\mathbf{627384}$. In terms of the inverse permutations, it's $7\mathbf{248}5\mathbf{136} \mapsto 2\mathbf{468}1\mathbf{357}$. So $75$ was mapped to $21$ and $248136$ was mapped to $468357$.

A descent $\ldots xy \ldots$ in $\pi^{-1}$ is lost after the operation only if $x \in A$ and $y \in B$. Conversely, in terms of $\pi^{-1}$, the partition into $A$ and $B$ corresponds to $A$-runs and $B$-runs; every time a $B$-run ends and an $A$-run begins, there is a descent. In order to "kill" a descent, we have to switch from an $A$-run to a $B$-run. If we kill two descents, we will have switched in the middle from a $B$-run to an $A$-run, incurring a descent.

This argument can be formalized to show that if $\alpha$ arises from $\pi$ via an operation, then $d(\alpha^{-1}) \geq \lfloor d(\pi^{-1})/2 \rfloor$, where $d(\cdot)$ is the number of descents. This is equivalent to $r(\alpha) \geq \lceil r(\pi)/2 \rceil$, thus proving one direction of my conjecture. The other direction is easier, and was already outlined above: we simply take every second run and push these runs to the right to get a permutation $\alpha$ satisfying $r(\alpha) = \lceil r(\pi/2) \rceil$.


$\mathcal{O} (3k) = \mathcal{O} (k)$ because $\mathcal{O} (k)$ can be defined like this:
$$
\tag{1}
d = \mathcal{O} (k) \implies d \le Ck ,
$$
for some constant $C>0$ and for all $k$ larger than some threshold, and similarly $\mathcal{O}(3k)$ would be defined as:
$$\tag{2}
d_3 = \mathcal{O}(3k) \implies d_3 \le C_3 (3 k),
$$
for $C_3 > 0$ and for all $k$ larger than some threshold.
Now remember that $C$ and $C_3$ are positive, so $3C_3 > C$, which means that if $d_3 = \mathcal{O}(3k)$ then it must also be $\mathcal{O}(k)$.
Then since $2^k$ is a monotonic function, we also have that $2^{\mathcal{O}(3k)} = 2^{\mathcal{O}(k)}$.
Some will argue that specifying the extra constant of "3" is redundant and formally improper, but you might still find that constant explicitly written in some papers, especially by people that don't know the above definition and tend to use big-O notation with (some would say regrettable) looseness.
The bottom line: If you know the constant hiding under the Big-O is 3, you might as well just say $d \le 3k$ instead of $d=\mathcal{O}(3k)$.

You've added a new question to your post after two of us already answered the first one. For the second question:
$2^{\mathcal{O}(k)}$ gives us everything of the form $2^l$ where $l \le Ck$ under the conditions of Eq. 1.
By monotonicity of the function $2^l$ we have everything smaller than $2^{Ck} = (2^C)^k$ under similar conditions.
Let's consider the example where $C=2$.

Your question becomes whether or not $\mathcal{O}(2^k) = \mathcal{O}(4^k)$, but since there is no constant $C$ such that $4^n \le C  2^n$, it is not true that $\mathcal{O}(2^k) = \mathcal{O}(4^k)$.
Therefore it is also not true that $\mathcal{O}(2^k) = \mathcal{O}(2^{Ck})$ and:
it's also not true that  $\mathcal{O}(2^k) = 2^{\mathcal{O}(k)}$.

Conclusion: $\mathcal{O}(2^k) \ne 2^{\mathcal{O}(k)}$ in general.