What techniques can I use to hand-write a parser for an ambiguous grammar?

I did not read in detail your grammar which is far too large for my
available time, and short of an example that you should provide (since you
assert it is ambiguous) I will not not attempt to check whether it is,
which is in general undecidable.

This said, as already remarked by user rici there are general
context-free (GCF) parsers that will parse any CF grammar, whether
ambiguous ot not. (I am ignoring very old depth first, recursive
decent parser). GCF parsing takes in general a time $O(n^3)$ where
$n$ is the size of the input sentence. However, it will be only
$O(n^2)$ for unambiguous, but possibly non-deterministic grammars.
And they are usually linear for many grammars, or for a significant
subset of the language defined by the grammars (see below).

I think it would be abusive to qualify these parsers as using unbounded
lookahead. Actually they try simultaneously all parsing possibilities
in parallel, and abandon some when further information from the input
becomes incompatible with the attempted parse. This is not the same as
not attempting a parse using some known facts about the rest of the
string, which is what lookahead is about. Indeed, several of these
algorithm may try not to attempt some parses, based on bounded
lookahead information: this is true of Earley's, GLL and GLR.
Furthermore, the concept of lookahead is meaningful for on-line algorithms, which is not really the case for GCF parsers.

The best way to survey this technology is probably a fast historical overview.

The (almost) oldest of GCF parser is the well known CYK algorithm. It
is pure dynamic programming constructed directly on the grammar. It is
extremely simple, but not best in performance.

The next one is Earley's algorithm (1968). Contrary to what is often said, it
is not simple, at least in its general form, and there is no standard
reference that I know regarding the format of the produced parse-trees
(parse-forest). It is not clear that its performances are the best one
might expect.  Earley's algorithm is actually derived in a somewhat ad hoc
fashion from Knuth's LR(k) parser construction. This of course diminishes in no way the importance of its contribution to introducing new parsing concepts.

This was generalized by Lang (1974), who proposed a general dynamic
programming interpretation of any PDA, that could be combined with any
PDA construction technique, such as LR, LL or precedence, giving
techniques known as GLR or GLL parsing. When the technique an yield a
derterministic automaton, the GCF parser works in linear time.

Tomita realized the first implementation of this technique, applied to
LR(k) PDA construction in 1984, thus implementing the first GLR parser. Then it was also used for LL(k) PDA
construction, in this millenium.

Regarding performance, people have often tried to improve it by using
sophisticated PDA construction techniques that have been designed to
increase the number of grammars that can be parsed
deterministically. This folk wisdom is apparently ill-advised, as
analyzed by Billot and Lang (1989). That suggests that efficient GCF parsers can have a fairly simple structure.

All of these parser can work fast enough on modern computers. They
produce all possible parse-trees, in a condensed form called
parse-forest. One issue may be the representation of the
parse-forest which may be more or less convenient depending on the
implementation. Of course, if the CF grammar is unambiguous, there is
only a single parse-tree, which may do away with this parse-forest problem.

A major difference with traditional deterministic parsers is that the
production of the parses is online for deterministic parsers,
producing the left part of the parse-tree in synchronization with
the reading of the corresponding left part of the sentene being
parsed. With the GCF parsers, it is more an offline behavior, as  you may have to wait the very end of the
parsing process before you know what parsing structure is relevant.

Another issue is that I do not know how well parsing errors can be
handled by current implementation. I do know that some very
interesting work has been done on that by the Natural Language
community.

Regarding your own grammar, I think that trying to use these
techniques in a hand written parser is just looking for trouble.  You
woud have to have an excellent mastery of the technology.  There is
just nothing to be gained. But, given the way you state your question, if you want a simple implementation
that you can master, for testing purposes, you may try the CYK
algorithm. It main advantage is that, like Earley's algorithm, it works directly on the grammar, which you may find more intuitive.

Many parser generation system now propose some form of GCF parsing,
but I have no personnal experience with any of them, thus no
recommendations.


P=NP when number of inputs that give 1 is bounded by polynomial

The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes.

The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.


Short answer:

There isn't a run-function for all monads, and its use is evaluating data structures.

Medium answer:

Certain monads build data structures that will be evaluated afterwards. Let's say we want to build our own IO monad (I'll need to use GADT notation, basically I just talk about inhabitants and their specific types):

data SimpleIO a where
  PutStr :: String -> SimpleIO ()
  GetLine :: SimpleIO String
  Bind :: SimpleIO a -> (a -> SimpleIO b) -> SimpleIO b
  Return :: a -> SimpleIO a

Like this, we can build a few IO actions, like one that just reads a string and prints it: Bind GetLine PutStrdoes exactly that.
However, our monad doesn't do anything: We don't know how to execute those actions, so we need some kind of conversion function:

runSimpleIO :: SimpleIO a -> IO a
runSimpleIO (PutStr x) = putStrLn x
runSimpleIO GetLine = getLine
runSimpleIO (Bind x f) = x >>= f
runSimpleIO (Return x) = return x

This is some kind of run function, it uses the monad-made structure to make use of it. It definitely isn't unique though: You might as well write a run function SimpleIO a -> Maybe a. That's nothing defined within the monad, but more of an interpretation.


Why is this true: “There are countably many Turing Machines”

A quick informal answer:

a Turing Machine (states, transitions, ecc.) can be encoded using a string of $0$'s and $1$'s;
so you can pick all the binary strings in lexicographic order (0,1,00,01,10,11,000,001,...) and enumerate the Turing machines (i.e. build a one to one corrispondence between natural numbers and Turing machines) repeating the following steps:

1) start with $i=1$, $m=1$
2) generate the next binary string $s_i$ in lexicographic order
3.1) if $s_i$ is a valid encoding of a Turing machine then output $s_i$ as the $m$-th Turing machine and set $m = m+1$;
3.2) if $s_i$ is not a valid encoding of a Turing machine then ignore it
4) set $i = i+1$ and goto step 2

In this way each natural number ($m= 1,2,3,...$) corresponds to a Turing machine, and each Turing machine has a corresponding $m$, because you scan all possible binary strings. So the set of Turing machines is countable.

On the other side consider all possible strings $S$ over alphabet $\{0,1\}$:
$S =\{0,1\}^* = \{\epsilon,0,1,00,01,10,11,000,001,...\}$

A language $L$ is a subset (possible infinite) of $S$: $L \subseteq S$.

So the set of all languages is exactly the power set of $S$:
$2^S = \{ \{\epsilon\}, \{0\}, \{1\}, \{0,1\}, ... \}$

But the power set of a countably infinite set is uncountable (it can be easily proved using the diagonalization method).

You can also apply the diagonalization method directly to the set of languages: suppose that the languages are countable, then we can arrange all of them in a table in which every (infinte) row $i$ represents the elements of the language $L_i$ and the columns represent the string over the alphabet $\{0,1\}$ ($(i,j)=1$ if and only if string $j$ is in $L_i$):

    0 1 00 01 10 11 ...
L1  0 0  1  0  1  0
L2  1 1  0  1  0  1
L3  0 1  0  0  1  0
...

Then define a new language changing the "membership flag" of the elements $(i,i)$:

    0  1 00 01 10 11 ...
L1 [1] 0  1  0  1  0
L2  1 [0] 0  1  0  1
L3  0  1 [1] 0  1  0
...

The new language $L_{new} = \{0,00,...\}$ built from the modified diagonal is different from every language $L_i$: $0 \notin L_1, 0 \in L_{new}$, $1 \in L_2, 1 \notin L_{new}$, $00 \notin L_3, 00 \in L_{new}$, .... But this is a contraddiction because by hypothesis the above table should be an enumeration of all languages.


Rather than going to talk about algorithms and more about SAT, this answer tries to show that there is more than just one kind of logic and that there are also different kinds of approaches.

I won't go into detail much but rather provide a list with some topics and keywords that should form a good basis to do some research:

Higher order logic

There are many ways of extending the propositional logic as you know it, for example (first order logic) with the quantifiers $\forall$ and $\exists$ quantifiers.

Keywords: First/second order logic (with equality), free/bound variables, Skolem normal form

Type theory

This is basically just another higher order logic, but it's a very rich topic and in my opinion deserves its own category since it plays a special role in CS.

Keywords: $\Pi$-/$\Sigma$-types, subtypes, quotient types, Curry-Howard correspondence, (un)typed $\lambda$-calculus, System F, Martin-Löf type theory, $\lambda$-cube

Proof systems

These can vary from classical logic as you know, but can be more abstract working with other syntactical objects than Boolean values or predicates. Generally they define some set $\mathcal{X}$ of objects (formulas/syntax), a truth-assigning function $t: \mathcal{X} \to \{\texttt{false},\texttt{true}\}$ (defines semantics), some notion of proofs and a way to (efficiently) check whether a proof is valid.

Keywords: Completeness & soundness, Gentzen/Hilbert style proofs, resolution calculus, Sequent calculus, Intuitionistic logic, Formal verification, temporal logic etc.

If this was not specific enough, here is one thing I found fascinating when I first learned about logic:

$$
\lnot \exists x . \forall y . \bigl ( F(x,y) \longleftrightarrow \lnot F(y,y) \bigr )
$$

The above formula is a tautology (ie. always true) for any domain $\mathcal{U}$ and predicate $F$. Now usually this is not very interesting, but

define $\mathcal{U}$ as the set of all sets, $F(x,y) = y \in x$ and we get Russell's paradox, or
define $\mathcal{U}$ some fixed enumeration of $\{0,1\}^\infty$, $F(x,y) = \text{$x$th bit of $y$}$ (now interpreting $\longleftrightarrow$ as equality on $\{0,1\}$) and we get Cantor's diagonalisation argument

which I find quite interesting.


Optimal assignment of +-1 values to vertices in a graph

This is the maximum cut problem.

The function $g$ can be given explicitly as $g(\{u, v\}) = H_{\{u, v\}} f(u) f(v)$ for some $H \in \mathbb{R}^{E}$. Each choice of $f$ divides the vertices into two sets $V_+ = \{x \in V : f(x) = +1\}$ and $V_- = \{x \in V : f(x) = -1\}$. The  set of edges connecting $V_+$ and $V_-$ is the cut-set $C = \{\{v_+, v_-\} \in E: v_+ \in V_+ \text{ and } v_- \in V_-\}$. The term to maximize is

$\sum_{e \in E} g(e) = \sum_{e \in C} g(e) + \sum_{e \in E \setminus C} g(e) = \sum_{e \in E} H_e + 2 \sum_{e \in C} (-H_e)$

This is maximized by a maximum cut $C$ under edge-weight $-H_e$ for each edge $e$.

When there are both negative and positive weights, it is known that max-cut is NP-hard in general (min-cut is equivalent to max-cut with weights negated). In contrast, max-cut (min-cut) problem with non-positive (non-negative) weights has an efficient general algorithm.

Using knowledge of the structure of the graph may provide an efficient algorithm. It is easy to come up with an $O(n)$ algorithm when the graph is a tree, where $n$ is the number of vertices. For planar graphs, there are algorithms which solve max-cut in $O(n^{3/2} \log(n))$ time.

Useful search terms include submodular function and Ising spin glass model.


Two definitions of universal hash functions

The two definitions are not equivalent.  The second definition does not imply the first.  You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.


Is set cover still NP-complete if you have a given k?

No.

Like many $NP$-complete problems, fixing the solution size gives a polynomial-time algorithm. In this case, we're looking for a group of at most $(k=)3$ sets $s_{1}$, $s_{2}$ and $s_{3}$  from $S$ such that $s_{1}\cup s_{2} \cup s_{3} = U$, so we can simply try every set of 3, which gives a $O(|S|^{3})$ algorithm because there's only $\binom{|S|}{3}$ groups of three sets taken from $S$, and in general, for every fixed $k$, an $O(|S|^{k})$ algorithm.

This is true for many other problems, like Dominating Set, Vertex Cover, Independent Set, $k$-Clique etc. etc. These all have $O(n^{k})$ brute force algorithms. Expressed in Parameterized Complexity terms, they're all in the class $XP$ (in fact, for all of these, they're in $W[P]$) when the parameter is the solution size1.

Note the contrast with problems like k-Coloring, which is $NP$-complete for every fixed $k \geq 3$. The best algorithms for problems like these have running times more like $O(k^{n})$ - the relationship between $k$ and $n$ is reversed to what we had before. Again in Parameterized Complexity terminology, such things are $para$-$NP$-complete, and don't have (non-uniform $XP$ algorithms unless $P = NP$.

Footnotes

$XP$ is the class of all parameterized problems that have a polynomial time algorithm for every fixed value of the parameter, also called "slicewise polynomial". $W[P]$ is the class of problems that have a nondeterministic algorithm that runs in $f(k)n^{O(1)}$ time with at most $h(k)\log n$ nondeterministic steps for some $h$, where $k$ is the parameter - we can remove the nondeterminism and get a $O(n^{O(h(k))})$ algorithm for some function $g$, through the same approach of trying all possible solution certificates.


Converting context-free grammar to chomsky normal form

You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.

Consider the grammar

S → TU
S → UT
T → a
U → a

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is.  Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form!  A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it.  Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form.  But nobody asked it to.  Except you.

Just let the poor algorithm go about its ways.  You know what to do once it's finished :-)


Question about non recursively enumerable language

Definition: a string over an alphabet $A$ (of finitely many symbols) is a finite sequence of symbols in $A$.
Definition: a language over an alphabet $A$ is a set of strings over $A$.

Is every language which is not recursively enumerable, uncountable?

No. Any language is a subset of the complete language $A_*$, the set of strings over $A$, which is a countable set. So, in fact, any language is a countable set of strings.

Is there any language which is recursively enumerable and uncountable?

No. The reason is the same as above.

The answers and the reasons behind them remain the same even if we allow $A$ to be a countably infinite set.

These two questions are not the same as the questions in Is there a non-recursive and uncountable language L?. However, the answer with its the reasoning are the same as [the answer to that question](https://cs.stackexchange.com/a/55855/91753.

OP just updated the question. So the only case left unanswered is when $A$ is an uncountably infinite set.

In that case, the definition of a language being recursively enumerable such as the one at wikipedia becomes inapplicable since all (common) models of Turing machines require the number of symbols to be finite (or at most countably infinite). To continue the discussion, we will need to make a new list of definitions for the Turing machines of the extraordinary kinds(which is not the Turing machines we usually talk about) or even other kinds of machines for hypercomputation and what is means by a recursively enumerable language with respect to those machines. That would be too large a scope that I would prefer not to go into in this answer.


Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

Maybe the surreal numbers will work as dyadic intervals.
Surreal numbers have a reduced form containing a left and right surreal which is like a range.
I think these ranges match the description of "dyadic intervals" in the link you provided.
Nan (the empty set) is considered to be positive or negative infinity depending on whether it is on the left or right side of the reduce surreal form.
The bit form of these dyadic intervals will be the right/left path down the surreal tree diagram (https://en.wikipedia.org/wiki/Surreal_number)
They start like this:
Surreal No.  Tree path  Binary Form   Reduced Form    Interval
   0            nan
   1            ""            1           {0|0}      {-inf,+inf}
   2           "L"           10           {0|1}      {-inf,0}
   3           "R"           11           {1|0}      {0,+inf}
   4           "LL"         100           {0|2}      {-inf,-1}
   5           "LR"         101           {2|1}      {-1,0}
   6           "RL"         110           {1|3}      {0,1}
   7           "RR"         111           {3|0}      {1,+inf}

You would also have to imagine that half way between + and - infinity is zero. Then half way between zero and +inf is 1. Then half way between 1 and +inf is 2. etc for all integers. Maybe that makes it unsuitable.
I am unsure whether surreal numbers are related to your question. I had already noticed that the surreal numbers have a quality of half ranges when I read your post.
Edit:

a "1" bit is prefixed to the L/R path of the given surreal. Where L=0 and R=1. Ex:-1/2 is LR on the surreal tree diagram. LR converts to 01 and then we prefix a "1" to get "101". 101 is the binary form of the LR path.
Surreal numbers are listed as their birth number. Not their value number. Their values of their left/right reduced sides are used to determine the ranges they represent.
I can provide python code which produces these list if you want to see how these numbers and ranges are created.
the example provided above was made by hand and certainly contains mistakes.


Is stack based memory allocation memory allocated at run time or compile time?

The amount of stack space allocated to a process (or a thread, if you are talking about multithreading) is decided at run time, when it starts - usually by the system, which just allocates a fixed amount without regard to what the program might actually need: "allocate a megabyte and keep your fingers crossed". Alternatively, when creating a thread within a program, it is sometimes (depending on the system) possible for the programmer to specify the size of the stack required by the thread - but this, too, is done before knowing what the thread's real requirements might be.

With virtual memory, of course, what is really allocated is address space rather than actual memory, so in principle one could just increase the address space allocated to each thread and cross one's fingers a little less. But the same point remains: a fixed limit is being imposed, in advance, without knowing what is actually going to be needed.

Ultimately no reliable computer system can have both unlimited recursion and stack-based storage. Mainframes such as the IBM 360 did not use stacks for return addresses or for local storage. There are "stackless" implementations of various programming languages - any programming language could be implemented stacklessly if people really wanted to do it.

This Stack Exchange answer goes into much greater detail, more rigorously.


Reccurence of recursive function with unequal sizes of subproblems

Your timing function is $T(n)=2T(n/3)+1$, namely two recursive calls to one-third size problems plus a constant amount of time for the if test and the assignments. If you know the Master Theorem, the answer is immediate, namely $T(n)=\Theta(n^{\log_32})$. If you don't know the MT, it's not too difficult to see the answer by expansion:

$$\begin{align}
T(n) &= 2T\left(\frac{n}{3}\right)+1\\
 &= 2\left(2T(\frac{n}{3^2})+1\right)+1=2^2\ T\left(\frac{n}{3^2}\right)+2+1\\
 &=2^3\ T\left(\frac{n}{3^3}\right)+4+2+1 &\text{and, in general, we have}\\
&\dotsc\\
&=2^k\ T\left(\frac{n}{3^k}\right)+\left(2^{k-1}+\dotsm +4+2+1\right)
\end{align}$$
Now let $n=3^k$ and the result follows with a little algebra.


Which could be a possible time complexity?

$n=|V|$, and $\sum_{v\in V}deg(v) = 2\cdot |E| = 2m$ (each edge is counted exactly twice).
Take a look here for a proof why ${n \choose k} = \Theta(n^k)$ for a fixed $k$. Substitute everything, and get that also $O(n^k*m)$ is a valid estimate (again, only if $k$ is a fixed number!).
c) Is clearly not a tight bound, since it doesn't even depend on $k$ (although, this statement is by no means a proof).


Minimum number of rotations of a binary tree to convert it into another

First rotate 9 right around 11 to make a linear tree.


Is $\Gamma \vdash x x : T$ possible in the simply typed lambda calculus?

You are on the right track. The argument you would use is on the lines of
size of types defined below: (I am assuming you are in the world of simply typed $\lambda$-calculus)

$size(T) = 1$

$size(T \to T') = size(T) + size(T')$

Unification will only work if the size of types is equal, and in this case
$size(T \to T') > size(T)$ hence there cannot be such a term.

However, if you add recursion/non-termination in the type system.
You can indeed have such a term.
$ \vdash (\lambda x. x x) (\lambda x. x x):\bot$

$\bot$ is the type that represents non-termination.


Updating connections weights in neural networks

You actually can increase it by an arbitrary amount. The reason you are increasing it by the sum of all weighted inputs is so that the number you increment by is actually related to the neural network and the input. At least in that case, what you are incrementing by something that is related to what's going on. Otherwise, the behavior may be more random.

There are several functions you could choose to increment by instead. You could also choose to create new neurons (mitosis) where a neuron exceeds an arbitrary threshold. The method you're following is just another method that is being tested in trying to properly represent neural networks.


What is the complexity of the emptiness problem for 2-way DFAs?

Friend Google suggests the following "The PSPACE-completeness of the emptiness problem for two-way deterministic finite-state automata in Exercise 5.5.4 is due to Hunt (1973)."
(An Introduction to the Theory of Computation, Eitan Gurari, Computer Science Press, 1989, online)

Hunt, H. (1973). "On the time and tape complexity of languages," Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 10-19.

(I have now looked at the reference) The paper is written in an abstract way as you note. The crucial part for us is the proof of Thm 3.7, where it is suggested that one can construct a 2FSA $\cal A$ that accepts valid computations of a linear bounded automaton $\cal M$ on a fixed(!) string $x$ (which is close to the definition of PSPACE). The 2FSA $\cal A$ is constructable in polynomial time (in the size of $\cal M$ and $x$). A computation of a LBA can be written as $x\$x_1\$\dots\$x_n$ where the $x_i$ are all of the same length as $x$ and are consecutive steps of $\cal M$. How does $\cal A$ check that $x_i$ and $x_{i+1}$ are equal (up to a very local change of a state and a single symbol as the operation of a LBA)? By checking letter by letter, going both ways on the tape. For that we need a counter of size $|x|$ implemented in the finite state control of $\cal A$.

It turns out that the problem is mentioned in the appendix of the classic reference by Garey & Johnson, Computers and Intractability, problem [AL2] "Two-way finite state automaton non-emptiness" with the explicit remark "PSPACE-complete even if $\cal A$ is deterministic". Reference again Hunt, with the clarification "Transformation from Linear Bounded Automaton Acceptance" (Given LBA $\cal A$ and input $x$, does $\cal A$ accept $x$?). The latter problem is [AL3] with reference to the famous Karp (1972) paper "Reducibility Among Combinatorial Problems" (where LBA Acceptance is mentioned as Context-Sensitive Recognition).


Can the sorting of a list be verified without comparing neighbors?

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases:
$$
1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\
1,2,\ldots,i-1,i+1,i,i+2,\ldots,n
$$


2 does not hold as stated. All you know is that if you flip the all bits in a given block $B_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about flipping any individual bit within $B_i$.

EDIT: In fact, if $B_1, B_2, \ldots, B_i, \ldots$ represents a maximal set of blocks, then for any $B_i$, there cannot be more than one index within $B_i$ such that flipping the bit at that index will flip the output. Suppose that within $B_i$ there are two indices, say $j$ and $k$, such that flipping either $x_j$ or $x_k$ will flip the output. Then $B_i$ can be replaced by the two singletons $j$ and $k$, thus contradicting the assumption that the set of blocks was maximal.

Meanwhile, the first function found to have a quadratic gap between $BS(f)$ and $S(f)$ is due to Rubinstein (1995). You can find a quick summary of the construction in this blog post by Scott Aaronson. A function with slightly bigger separation was found later by Virza (2011).


Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method

Your "General Formula" is incorrect.  The third term (with the sum) is incorrect.  It should be $n$ rather than $n/4^k$.

Make the suitable correction through the rest of your answer, and use the fact that

$$\sum_{k=0}^{\log_4 n} n \log_{10}(n/4^k) \le \sum_{k=0}^{\log_4 n} n \log_{10} n$$

and you should be able to get an upper bound from there.  (The final sum is easy to evaluate as every term is the same.)


BST - Sufficient condition for connecting a node to a parent

Due to the lack of definitions in the question, let us pick up a couple of definitions that are needed for a formal proof.

  A binary rooted tree is a BST if its nodes are visited in its natural order by the inorder traversal. Inserting a new node into a BST means adding a new edge so that the new node becomes the child of some old node and the tree remains a BST.

Let us prove a useful lemma.
(Uniqueness of insertion into BST) Let $T$ be a BST. Let node $X$ be a new node that is not equal to any node in $T$. Then there exists a unique way to insert $X$ into $T$ so that $T$ remains a BST with the same root, where the insertion must add one edge to $T$ (without modifying the existing edges).

Proof by mathematical induction on $n$, the number of vertices in $T$.

The base case when $n=1$. If the new node is less than the root node, it has to inserted as the left child of the root node; otherwise, it has to be inserted as the right child of the root node.
Assume the lemma is true for BST whose number of vertices is smaller than $n$. Suppose $T$ is a BST of $n$ vertices with node $R$ as its root node. Suppose $X$ is a new node that is not equal to any node of $T$. There are two cases.

$X$ is less than $R$. If $R$ has no left child, then $X$ has to be inserted as the left child of $R$. Otherwise, $R$'s left subtree is a BST (because of the recursive nature of the inorder traversal). $T$ has to be inserted into $R$'s left subtree. By induction hypothesis, there exists a unique way to insert $X$ into $R$'s left subtree.
$X$ is greater than $R$. Just switch every "left" to "right" in the above case.

Proof is done. As you have indicated, this is intuitively so obvious!

Now let us prove a proposition that is slightly more general than what you want to prove.
(Right child insertion) Let $T$ be a BST with node $Y$ that does not have a right child. Let node $X$ be a new node larger than $Y$ such that any node that is larger than $Y$, if exists, must be larger than $X$. Then node $X$, if inserted, will be inserted as the right child of $Y$.

Proof. Let $T'$ be the binary tree obtained from $T$ when $X$ is added as the right child of $Y$. Compare the inorder traversal on $T$ and that on $T'$. By the definition of inorder traversal, the difference between them can happen only when each traverses the subtree rooted at $Y$.

Both traversals will visit the same left subtree of $Y$ first. Then both will visit $Y$.  When it is time to visit the right subtree of $Y$, the former traversal has nothing to do since $Y$ has no right child in $T$ while the latter traversal will visit one more node, $X$ since $Y$ has $X$ as its right child in $T'$.

Since the nodes in $T$ is visited in its natural order by the former traversal, the nodes in $T'$ is visited in its natural order by the latter traversal as $X$ is the very next node that is larger than $Y$. By definition, $T'$ is a BST. According to the above uniqueness lemma, $X$ must be inserted as the right child of $Y$. Q.E.D.


Work-stealing: where and how many to steal

I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It means that you can get items more than once but at least once. There are then three operations defined $put()$, $take()$, and $steal()$. The idea is that $put()$ and $take()$ are free of synchronisation only $take()$ uses atomics. When a thread has finished its queue (or stack) it uses $steal()$ on some other threads stack.


If you say

$\forall x, x': ran\  routes . x<>x'$

You're only saying that the sequences are different.  For example

$<London, Berlin, Paris>$ would be different to $<London, Paris, Berlin>$

Instead, you need two quantifiers

$\forall x: ran\  routes . \#x>20$

and

$\forall p,p': Place • p \in ran\ (ran\ routes) \land p' \in ran\ (ran\ routes)  \implies p<>p'$

One for the length as you had and one for the condition that all elements must be unique.  Note the double $ran$ expression since a sequence is defined as a function between its indexes and its values (the range).


An implicant of $F$ is a partial assignment to the variables of $F$ which guarantees that $F$ is satisfied. A prime implicant is a minimal implicant, that is, an implicant that is no longer an implicant if we remove any single variable.

Let us start by finding all the implicants of $F$. Let $\alpha$ be any partial assignment to the variables of $F$, and suppose that $\alpha$ assigns $k$ variables to true. We can complete $\alpha$ to an assignment by assigning the rest of the variables to false, in which case we get an assignment containing $k$ true variables. Hence $\alpha$ can only be an implicant if $k \geq 3$. Conversely, it is not hard to check that if $\alpha$ assigns at least 3 variables to true then it is an implicant of $F$.

When is an implicant a prime implicant? It must be a partial assignment with at least 3 true variables, such that if we remove any single variable, there are at most 2 true variables. Can you figure out how all such implicants look like? Give it a try.

As an aside, your function is monotone, and so its prime implicants are also known as minterms. Minterms have a special structure – they cannot be arbitrary partial assignments. I'll let you figure out the special property that minterms have.


Does the undecidability of the halting problem require Turing Machines to be enumerable?

No, being able to enumerate Turing machines is not directly relevant.

Let us consider some abstract notion of algorithm. The ingredients for the undecidability are as follows:

The Halting problem makes sense. This means that

a) Algorithms can "halt" on some inputs, and fail to "halt" on others. Halting allows the algorithm to output something, eg "Yes" and "No".

b) Algorithms can take algorithms as input.
Algorithms allow if-then-else branching
There is an algorithm that takes an algorithm as input, and simulates how the input-algorithm would act.

The code snippet in the question is essentially how you do it, and the criteria above are essentially saying "this code snippet is valid pseudoc-code for our abstract notion of algorithm".

To see that the fact that TMs can be enumerated really does not factor in, one can look at models of computation such as the BSS-machines. These can have arbitary real numbers as parameters in the code, so there are uncountably many machines. However, they still meet all criteria above, and thus the standard argument shows that BSS-machines cannot decide the BSS-Halting problem.


Converting a regular expression to a context-free grammar

This CFG is indeed correct, but can be greatly simplified.

First, there is no need to create a new variable that would derive only a terminal value, that is - $s_1,s_2,s_5,s_6$ are not required.
For a similar reason, we don't need $s_9$.
Another simplification is that $(a\cup b)^*$ was already generated by $s_4$. There is no need to create $s_7$ and $s_8$ for this usage

Considering those things, the CFG will be reduced to:

$S\rightarrow A\space|\space abA$
$A \rightarrow AB\space|\space\epsilon$
$B \rightarrow a\space |\space b$

Notice also that $L(ab(a\cup b)^*)\subseteq L((a\cup b)^*)$, and thus:
$L((a\cup b)^*\cup ab(a\cup b)^*) = L((a\cup b)^*) \cup L(ab(a\cup b)^*) = L((a\cup b)^*)$
And thus an even smaller CFG will be:

$S \rightarrow A$
$A \rightarrow AB \space | \space \epsilon$
$B \rightarrow a\space | \space b$

Essentially we removed one unnecessary derivation rule. This can be simplified a bit further, go ahead and give it a try :)


Computational equivalences between a calculus and an automaton model

As I said, I am not sure how to answer your question.

However, given the current rephrasing of it, it finally rung a memory
bell. I think that, starting sometime in the 1970's, people have been
studying what they called program schemes.

A set of slides (in French) I found on the web seems to give a
historical perspective on the subject.

Slide 14 is about Iterative program schemes, corresponding to Regular
sets. They correspond to computational structures of the form X=f(X,Y) and Y=a, which are only a functional version of iteration loops.

Slide 15 is about Recursive program schemes, corresponding to
Algebraic (also known as Context-Free) languages. They correspond to more complex recursive computation structure, using a stack memory as in early recursive programming langages.

I am not certain that is the kind of correspondance you are looking
for, as it correspond (as much as I remember) to the computing power of uninterpreted programs, i.e. the structural aspects of the computationq. But it may be worth reading.

There are many more references, including fairly recent ones, if you
serach the web with: "program schemes".


What are the sufficient conditions for a grammar to be unambiguous?

If you can construct a deterministic parser corresponding to a grammar, then the grammar is clearly the unambiguous. (If it were ambiguous, there would need to be a point in some parse which admitted more than one parse action, violating the presumption of determinism.)

All of the algorithms you mention for constructing a parser either produce a deterministic parser for a grammar or report conflicts. So the absence of conflicts implies unambiguity.

Note that there might exist parsing algorithms which produce parsers which do not precisely correspond to the grammar. For example, yacc/bison use an algorithm which resolves conflicts, either using precedence declarations or through some default resolution rules. The resulting parser is then unambiguous, but it is no longer capable of producing the same set of derivations as the original grammar. Indeed, it might not even be able to recognise the same sentences.


Hint: A player loses if they are presented with a pile of size 1. If presented with a larger pile, what should you do if it's the first move of the game?

Here is a more general solution, which will be applicable in other cases.

You can find the winner (and even the Sprague-Grundy function) using dynamic programming. Each state of your game consists of a pair $(n,B)$, where $n$ is the number of chips, and $B$ is an upper bound on how many chips you're allowed to remove. I'll let you figure out the edges of this dag and the starting state. Now you scan the graph from the sinks up: a sink (state with no outgoing edges) is a LOSE state (from the point of view of the player whose turn it is to play). A state leading only to WIN states is a LOSE state, otherwise it's a WIN state, and any edge pointing at a LOSE state is a winning move.

It's probably more challenging to find a general formula for which player wins the game given $n$, but one way would be to compute it empirically for several values of $n$ (or more generally, of $n$ and $B$), figure out a formula, and prove your formula.


Your problem is not so trivial, though classical. See the proof of Corollary 11.9 in lecture notes of Kevin T. Kelly.


Are generational garbage collectors inherently cache-friendly?

Here are a few papers that talk about the cache implications of generational garbage collectors:

Caching Considerations for Generational Garbage Collection
The Effect of Garbage Collection on Cache Performance

From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing applies to cache memory. As you suggested, the things in the first generation are most likely going to be sitting in cache, and so their allocation and collection will be much faster than something in main memory, or paged out to disk. The main issue is the size of the first generation with respect to the size of your cache. If your cache fills up before the first generation does, then you start to lose those benefits as the misses start piling up.


What is the practical relevance of textbook mutual exclusion algorithms?

Answer: none.  That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about.  In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the pthread library, they are showing you how it is implement the equivalent of the pthread library.

Chapter 2 of Herlihy and Shavit is titled "Mutual Exclusion." It gives a variety of classic algorithms for implementing the equivalent of pthread_mutex_lock() with only sequentially consistent shared memory.  My answers https://cs.stackexchange.com/a/12632/7459 and https://cs.stackexchange.com/a/30249/7459 discuss the importance of these implementations, and have a pointer to one that is practical for use on machines that have no built-in hardware synchronization operations.  (Lamport's 1987 paper in ACM Trans. on Computer Systems).

Chapter 7 of Herlihy and Shavit gives a variety of spin and queue lock implementations of the equivalent of pthread_mutex_lock(), and Chapter 8 expands to discuss pthread_cond_t (condition variables), pthread_rwlock_t (reader/writer locks), and briefly touches on semaphores.  There may be situations in which pthread_rwlock_t could be used as an alternative to pthread_lock_t for performance reasons (but usually not) and in Posix you need to use semaphores for inter-process synchronization.

Chapters 9 through 16 are mostly discussing applications (various kinds of concurrent containers).  Chapter 17 briefly discusses the equivalent of pthread_barrier_t.

All that said, Herlihy and Shavit are two of the most vocal proponents of transactional memory and a variety of kinds of non-blocking (and wait-free) synchronization.  These techniques are intended as alternatives to mutual exclusion in certain cases.  Herlihy and Shavit sprinkle various non-blocking implementations throughout Chapters 9 through 16, and then go into detail on transactional memory in Chapter 18.

Transactional memory and other non-blocking synchronization techniques are intended to deal with the problem that some poorly designed algorithms require threads to hold their critical sections for a very long time.  Transactional memory and truly non-blocking synchronization are not currently practical alternatives in any real situation, but the techniques for transforming blocking data structures into non-blocking data structures are useful in practice for minimizing the amount of time a blocking data structure stays in its critical section.  (Often you can reduce the size of the critical section down to just a couple of machine instructions.)


What are the minimum requirements for a language to be considered Turing Complete?

The machine you describe would be turing complete with the addition of an assignment operator (you need this to take advantage of memory), and at least one comparison operator (which could be folded into the jump, like a jump-if-(not)-zero). (Note that an increment operator is necessary - either as a primitive, or appropriate representations need to be available such that one can roll ones own).

However, there are many turing-complete models of computation with completely different primitive operations, such as lambda calculus, or petri nets.


How can I examine the subnetworks of a nearly fully connected graph?

It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their pairwise weight matrix). This is more a statistical clustering problem than a graph clustering problem.
Here are some python functions to accomplish these:
https://scikit-learn.org/stable/modules/clustering.html


All automaton models you'll typically encounter are finitely represented; otherwise there would be uncountably many, which means they are not captured by Turing-complete models. Or, in CS-think, they'd be useless¹.

"Finite automata" are called finite because they only have a finite set of configurations (the input string aside). Pushdown automata, for instance, have a stack that can have arbitrary content -- there are infinitely many possible configurations.

Nota bene: Configurations of PDAs are still finitely represented! In fact, any computational model that falls inside Turing-computability has to have finitely representable configurations, otherwise TMs wouldn't be able to simulate them.

I consciously disregard hypercomputation here for the purpose of this question.


Eliminating ambiguity when referring to complexity in cases of multiple parameters and/or multiple results

You can report:

The running time (e.g., $O(k)$ vs $O(n)$),
The space requirements (e.g., $O(1)$, $O(k)$, etc.), and
Whether the algorithm is a streaming (online) algorithm or a batch algorithm.   A batch algorithm returns the entire answer at once.  A streaming or online algorithm returns numbers one at a time.  You might also be interested in the notion of "delay"; for instance, a $O(\log n)$ delay algorithm returns algorithms one at a time, taking at most $O(\log n)$ steps (running time) to output each number.

Since there are two variables here, $n$ and $k$, if you report a running time like $O(k)$, it may be helpful to mention explicitly that the constant is independent of $n$.

Formal papers aren't always as formal as you might think.  They'll use standard notation and terminology where they exist, but if standard notions don't cover it, they'll just use the English language to describe the situation, or they may introduce some new terminology and provide a definition for it.  That's the great thing about human language: it provides a way to express arbitrary new concepts, even ones we don't already have a pre-existing standard name for.


Yes, it's exactly the same class. You can take any constant size list of parameters and combine them just using addition. This is particularly obvious in Flum and Grohe's formulation of $FPT$ where problems are equipped with a parameterization $\kappa : x \rightarrow \mathbb{N}$.

So for example, you can take a problem with two parameters $k$ and $r$, and produce a combined parameter $k+r$ (or indeed using any moderately sane function), as if the running time is bounded by some function $f(k,r)$ (we can ignore the $|x|^{O*(1)}$ part for the moment)), then it is bounded by the function $f(g(k+r),h(k+r)) = f'(k+r)$, where $g$ and $h$ do whatever is necessary to turn $k+r$ into a sufficiently usable form (in most cases, this is nothing).

Note that this produces the intuition you expect. If $(\Pi,\kappa) \in FPT$, then it is still in $FPT$ when you add a new parameter, however it is not necessarily true that if $(\Pi,\kappa_{1} + \kappa_{2}) \in FPT$ then either $(\Pi,\kappa_{1}) \in FPT$ or $(\Pi,\kappa_{2}) \in FPT$.

As an example, deleting $k$ vertices to obtain an $r$-regular graph is $W[1]$-hard with parameter $k$, $paraNP$-complete with parameter $r$ but in $FPT$ with parameter $k+r$.


Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that.  So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it.  For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.


How to work out if an IEEE 754 floating point number is normalized?

For single-precision floating-point numbers you need to check if the following condition holds for the exponent $e$: $0 < e < 255$. The exponent occupies bits $30 .. 23$ (including both ends) of a floating-point number.

For double-precision floating-point numbers you need to check if $0 < e < 2047$. The exponent occupies bits $62 .. 52$ in this case.

Essentially, for IEEE 754 floating-point numbers one has to check that the bits of the exponent are not all 1's and not all 0's. All zero bits correspond either to subnormal numbers or to signed zero. And when all bits of the exponent are ones it corresponds to $+\infty, -\infty$ or NaN (not a number).


Verifier for A_tm in polynomial time - how to formally prove it does not exist?

Suppose by contradiction $A_\mathrm{TM}$ has polytime verifier $\Longrightarrow$ $A_\mathrm{TM}$ is in NP $\Longrightarrow$ $A_\mathrm{TM}$ is decideable by some non-deterministic TM in polytime $\Longrightarrow$ $A_\mathrm{TM}$ is dcidiable by some deterministic $2^{\mathrm{polytime}}$ TM $\Longrightarrow$ $A_\mathrm{TM}$ is decidable $\Longrightarrow$ contradiction.


2D random walk. Should both dimensions be independent?

The usual 2D random walk goes one step in one of the cardinal directions (up, down, left, or right). If you rotate the plane by 45 degrees, you get a random walk which moves up or down and left or right on each step. So both these distributions are the same (up to scaling), at least for a fixed step size.


In general matching with dependent types can be quite subtle! You'll note that in the Coq documentation that the extended pattern-matching syntax is

match t as x in T1 return T2 with
    | C1 a1 ... an
    ...

In particular, ommiting any of the as, in or return clauses can prevent type inference of the statement.

Intuitively, if the type of (say) constructor $C_1$ is
$$ \Pi(x_1:A_1)\ldots(x_k:A_k).I\ \vec{p}$$
and the type of the matched term $t$ is
$$ I\ \vec{v}$$
then you get the constraint
$$ \vec{p}[\vec{a}/\vec{x}]\simeq \vec{v}$$
which may lead to an undecidable problem, as explained in Goguen et al.

Then all you need is for each right hand side to correspond to the appropriate instance of the return type. This return type may depend on $t$, so the return clause specifies the pattern of the return type as a function of $x$ (which represents $t$ through the as clause).

More formally, each $e_i$ must have type:

$$ T_2[C_i\ \vec{a}/x]$$

and the type of the whole match expression is
$$ T_2[t/x]$$

More details can be found here.


Why say that breadth-first search runs in time $O(|V|+|E|)$?

BFS is usually described something like the following (from Wikipedia).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

The issue is a somewhat subtle one: it's hiding in line 3!  The question is, what data structure are we going to use to store which vertices have been discovered?

The simplest solution is to use a Boolean array with one entry per vertex.  In this case, we must initialize every element of the array to false and this takes time $\Theta(|V|)$. This applies for every graph, even if there are no edges at all, so we can't assume any relationship between $|V|$ and $|E|$ and we get a running time of $O(|V|+|E|)$.

Can we avoid having a data structure with $\Theta(|V|)$ initialization time?  Our first attempt might be to use a linked list.  However, now testing if a vertex has been discovered (line 10) takes time linear in the number of vertices visited, instead of constant time as before.  This means that the running time becomes $O(|V|\,|E|)$, which is much worse in the worst case.  (Note that we don't want to rewrite that as $O(|E|^2)$ since that's even worse: it could be as bad as $|V|^4$, whereas $|V|\,|E|\leq |V|^3$.)

Using a dynamically resized array would allow us to keep the list sorted, so now look-ups would only take time $O(\log|V|)$ but that still gives a running time of only $O(|E|\log|V|)$, which is still worse than standard.

Finally, we could use a dynamically sized hash table: start with a table of constant size $c$ and double it every time it gets half-full.  This means that the final size of the table is at most twice the number of vertices that are discovered before the algorithm terminates, and this is at most $|E|+1$ because we never discover anything outside the component of the start vertex. Furthermore, the total amount of work done copying the hash table to expand it is at most $c + 2c + 4c + \dots + 2|E|\leq 4|E|$.  Lookups and insertions to the hash table are amortized $O(1)$ so we do indeed obtain a running time of $O(|E|)$.

So $O(|E|)$ is possible, but would want to do that in a real implementation?  I would say probably not.  Unless you have reason to believe that your input graphs will have many small components, the overhead of maintaining the hash table is going to add a noticeable constant factor to the running time.  Growing the hash table could take time $4|E|$ and lookups will require you to compute the hash function and, on average, look at more than one slot in the table. The poor cache performance of hash tables might also hurt you on a real computer.  In most cases with the standard array implementation, the $O(|E|)$ part is the dominant term of the $O(|V|+|E|)$ running time so it's not worth using a hash table to remove the dominated term, given the practical cost of doing this.


Could anyone prove that this is a context free language or not?

This must be a classic in formal language theory. The Pumping Lemma will not help, because, unexpectedly, it is context-free. (I did not see the answer here, but it might be overlooked)

The $w_1$ and $w_2$ parts must have a position where they differ. Unfortunately, we cannot distinguish the middle and the two matching positions at the same time. However, we can find matching positions without knowing the middle.

With some effort you can convince yourself that your language $L$ equals
$$\{ x_1 a x_2 b x_3 \mid a,b \in \Sigma, a\neq b, |x_1|+|x_3| = |x_2| \}.$$
Once you have shown that, write a grammar using that formulation.


What you want is to find the 2-edge-connected components of your graph.
When you have a simple graph, you can do that by finding all bridges in your graph in linear time, delete them and find the connected components in the resulting graph (every connected component corresponds to a vertex in the final graph).

Now to ensure that this works also in your case where you can have multiple edges between two vertices you can simply ignore when the above algorithm finds an incorrect bridge (u,v), where u and v are connected by multiple edges. Don't delete this edge from your graph when this happens. To detect when this happens you can first find all duplicate edges (either by sorting all edges first or using some hashing method), store those edges in a container where they can efficiently be searched (hashing or binary search) and then for every detected bridge, test if it is in that container.


Take a look at Appendix A in the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
Besides you say that you'd like to know how to handle summations besides arithmetic and geometric series (and others) but the two examples you provide are (essentially) an arithmetic and a geometric series.


As you see, in each iteration i is increased by 1. Hence, value of s would be $1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, \ldots,  \sum_{i=1}^{k}= n$

Hence, $k$ is the time complexity of this code. As we know that $\sum_{i=1}^{k} = \frac{k(k+1)}{2} = \Theta(k^2)$, and $\Theta(k^2) = n$, we can conclude that $k = \Theta(\sqrt{n})$.


Normal colorings of cubic graphs (part 1)

Some old results by Vladimir Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165-176, imply that Question 3 has an affirmative answer. Although the auxiliary graph is not assured to be in some way as elegant or natural as in the case of line graphs or their squares. The easiest example that I can come up with has 13 times the order of the line graph.
This construction also gives an affirmative answer to Question 2.


What happens to quantum algorithms such as BB84 if P=NP

BB84 is simply a key exchange procedure. This procedure remains secure unless someone can figure out how to observe a quantum phenomenon without changing it, whether or not $P=NP$ will not change this. If the vulnerability of the algorithm was in key transmission, then it is safe if it uses BB84. If it is however somewhere else in the algorithm, then no matter how the key is transmitted it will be vulnerable. So really it depends on the algorithm and the exposed vulnerability. Most algorithms that could be broken by a drastic reduction in run time however are public key algorithms, private key algorithms are much more secure, however the key exchange is the risky part and usually uses some form of public key based encryption. With BB84 however the key exchange becomes relatively safe. So for the most part, the algorithms that would use BB84 are not vulnerable unless the key can be discovered, which requires breaking BB84 and therefor changing the modern understanding of physics. Unfortunately  the infrastructure is not yet in place for BB84 to be realistically implemented.


I think one solution is to do a single DFS (from any node) to determine the longest path, in "divide and conquer" fashion. Apologies in advance for the clumsiness of the description - I'm not sure what's the proper notation for these things.

First, some background: at each step of the DFS we're exploring a subtree T, with the current vertex R considered to be the root of that subtree. All the neighbors of the root (excluding the "parent" in the DFS sense, which is not part of T) form subtrees T1, T2 ... Tk of T.
At each step, we determine both the longest path in T, let's call it p(T), and the longest root path in T (root path = path starting from R), let's call that rp(T).
To do that, we find the same for each subtree T1, T2 ... Tk, then
rp(T) = R--longest(rp(Ti)), i=1...k (I'm using "--" to symbolize joining the vertex R to the path), and
p(T) = longest(rp(T), longest(p(Ti)), rp(T)--2ndlongest(rp(Ti)))
Some explanation about the last term: it only appears if k>1 (at least 2 subtrees), and it joins the 2 longest root paths in the subtrees, through R.
If k=0, then both p(T) and rp(T) are the 0-length path R.

I think a rigorous proof is not necessary - it is quite obvious that for each subtree T, p(T) is either in one of its subtrees Ti, or starts from R going into a subtree (this is rp(T)), or passes through R, going into 2 subtrees. And all the path parts going into subtrees must be the longest root paths in those subtrees. All the cases are handled.

As far as I can tell, the complexity is O(n) since this is a tree.

Implementation note: for each vertex we can store the lengths of p(T) and rp(T), a flag indicating which of the 3 situations we're in for p(T), references to (up to) 2 neighbors that contain a piece of p(T), and the next neighbor vertex for rp(T). At the end, we can reconstruct the longest path from this information.


Why are both caller-save registers and callee save registers needed?

Let's see. CPU have, f.e., 16 registers. If subroutine modifies them, they should be saved before that and restored later. Now, who should do that?

All 16 registers can be saved by caller, or all 16 registers can be saved by callee, or mixed scheme may be used. In this schema, 8 registers is considered as transient - caller don't expect that their contents will be left intact after a call. Thus callers usually use these registers only for temporary data, i.e. computations between calls. But in a few cases when these registers contains non-transient data, caller has to save their contents.

Other registers are considered as permanent, so caller expects that they are left untouched by callee. But in the cases when callee really needs to use more registers, it needs to save/restore their contents.

Why hybrid scheme is advantageous - because usually each procedure needs a few registers for transient data, so by having convention that these registers can be modified by callee, you can reduce calling sequence and therefore make procedure calls a bit faster and more compact.

OTOH, if we consider some registers as "permanent", we can try to avoid using these registers in leaf procedures (i.e. those not calling other procedures) and avoid saving/restoring these registers in leaf procedures. Since cpu usually spends most of time in leaf procedures, this also means quite substantial speed improvement.

So, by splitting registers into two classes, we can make program faster and shorter - leaf subroutines try to not use "permanent" registers and as result don't need to save/restore any. OTOH, other procedures try to don't use "transient" registers to hold values through calls, thus avoiding need to save/restore them.

So, hybrid scheme makes program more efficient compared to any of two pure schemes.


This is not NP-Complete as far as I know. Below is a way to solve it.

You can convert the problem to finding the minimal path cover of your graph by making all the weights negative. The minimal path cover is a collection of disjoint paths covering all vertices.

One way of solving this is to convert your graph into a bipartite graph by doubling the vertices and making sure every edge goes from one side to the other. You then find the maximum bipartite matching, which will give you all the edges used in the disjoint path covers, and you can then find the paths from this set.

To get the maximum bipartite matching you can convert the graph into a flow network with unit weights on edges and use Ford-Fulkerson algorithm. All edges in the max flow will be in the maximum bipartite matching. You can then stitch the edges together as there will be only one way to assemble it with minimum number of paths.


String searching, where we allow characters to almost-match

You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching).

This particular problem can be solved efficiently using convolution methods.  The running time will be something like $O(n \lg n)$, times some small factors.  Let me outline the algorithm, and then explain why it works.

The algorithm

Step 1: We will construct binary strings $T' \in \{0,1\}^{6n}$, $Q' \in \{0,1\}^{6k}$, with a special property:

If index $i$ is good-for-all, then there are $\ge k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.
If index $i$ is not good-for-all, then with probability at least $1/2$, there are $< k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.

Let me outline how to construct $T',Q'$.  First, pick a random hash function $h:\Sigma \to \{1,2,\dots,6\}$.  Next, define a code $C_T:\Sigma \to \{0,1\}^6$ like this: $C_T(x)$ is a 6-bit string that is 1 at index $h(x)$ and 0 at all other positions.  Also, define a code $C_Q:\Sigma \to \{0,1\}^6$ as follows: $C_Q(x)$ is a 6-bit string that is 1 at indices $h(x)$, $h(x-1)$, and $h(x+1)$, and 0 at all other positions.

Finally, define the binary string $T'$ to be the concatenation of codewords

$$T' = C_T(T[0]) C_T(T[1]) \cdots C_T(T[n-1]),$$

and similarly $Q'$ to be the concatenation of codewords

$$Q' = C_Q(Q[0]) C_Q(Q[1]) \cdots C_Q(Q[k-1]).$$

You can check that these two strings satisfy the properties above.

Step 2: We will use convolution (polynomial multiplication) to find all indices that are good-for-all.  Define polynomials $T(x),Q(x)$ from the binary strings $T',Q'$ as follows:

$$\begin{align*}
T(x) &= \sum_j T'_j x^j\\
Q(x) &= \sum_j Q'_j x^{6k-1-j}
\end{align*}$$

Multiply these two polynomials to get the polynomial $P(x) = T(x) Q(x)$.  Let $p_i$ be the coefficient of $x^i$ in $P(x)$, so that $P(x) = \sum_i p_i x^i$.

We have the following nifty property: $p_{6k-1-6i}$ counts the number of indices $j$ where both $T'_{j}$ and $Q'_{j+6i}$ are 1.  Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all".  Every index that is actually good-for-all will appear in that set, and every non-good-for-all index has at most a probability $1/2$ of appearing in the set of "suggested" indices.

Step 3: Repeat Steps 1 and 2 80 times, and keep only those indices that are suggested in every iteration.  Output that list.

Correctness

All of the good-for-all indices will remain and appear in the output.  Also, there's at most a $n/2^{80}$ probability that any non-good-for-all index survives all 80 iterations.  This probability is small enough as to be negligible.

Running time

The running time of this algorithm is dominated by the time to multiply two polynomials of degree $6n,6k$.  Assuming $n \ge k$, this running time is basically $O(n \lg n)$ (ignoring log-log factors) using standard techniques.

In practice there are a number of ways one could optimize this further.  For instance, we can often stop early without doing all 80 iterations: once the set of surviving suggested indices is small enough, we can just check each one directly and output only the correct ones.

Other approaches

Since your problem is a generalization of string matching, you could also look at other algorithms for string matching and see if any of those techniques can be generalized to your situation.  For instance:

It would be straightforward to adapt finite automaton based search methods: you can build an automaton based on $Q$ that accepts all strings that would match $Q$ as a substring (where "match" allows two similar characters to be treated as matching).  Building such a DFA might be very slow, but once you have the DFA, testing whether $T$ is a match can be done very fast -- in linear time.
It might be possible to adapt the Knuth-Morris-Pratt algorithm to your situation.  It might take some thought to work out the details, but if it works out, you might get a linear-time algorithm, i.e., $O(n)$ running time.
Also, take a look at Boyer-Moore.

I would especially suggest you take a look at KMP -- it looks plausible to me that this might yield a viable algorithm.


First use Yuval's advice: With p = 2^32 - 5, remove all N ≥ p (the result is 0), then sort the rest, so now you have up to 1,000 numbers in sorted order from 0 to p-1. This is trivial to do by multiplying up to almost 2^32 numbers modulo p and recording results at the right moment; that's not much above a second worth of work but more than a second.

Let's say you have r processors, and you want to use them simultaneously. The largest number is t < p. You make each processor responsible for multiplying s = ceil (t / r) numbers. For example if r = 8 and t = 2^32 - 6, then s = 2^29. Processor 0 multiplies numbers from 1 to s, processor 1 multiplies numbers from s+1 to 2s and so on. Let's say one of your N's is 3s + 15900: Processor 3 multiplies 3s+1 to 4s. At some point you record the product of numbers 3s+1 to 3s+15,900. And when all the processors are done, you multiply with the final results of processors 0, 1 and 2.

You may have vector units being able to do for example 4 operations in parallel. In that case, you would multiply r by 4, and have 8 processors calculating 4 results simultaneously.

Say you have calculated x (x+1) modulo p, the product of two numbers. How can you get (x+2)(x+3) modulo p, the next product? (x+2)(x+3)-x(x+1) = 4x + 6, so the product modulo p changes by (4x + 6) modulo p. Let d(x) = (4x + 6) modulo p. As you increase x by 2, d(x) changes by 8 (modulo p), so the products x(x+1) modulo p, (x+2)(x+3) modulo p, (x+4)(x+5) modulo p etc. can be calculated very quickly. I think that should be enough to get you below one second.

Some additions: One, if p = $2^{32}-5$ is not prime, that makes the problem just faster to solve. If all prime factors are ≤ $p^{1/2}$ then the problem is trivial because N! = 0 (modulo p) if N ≥ $2^{17}$ (must be careful in case p is the square of a prime). Otherwise let p = a·q, where a ≥ 2 and q is a prime q ≥ $p^{1/2}$, then we can calculate N! modulo p easily from N! modulo a and N! modulo q. Since $a ≤ 2^{16}$ and N! modulo a = 0 if N ≥ a, calculating N! modulo a is trivial (only 65535 products needed). b would be at most half as large as p, making the problem at least twice as fast to solve. After applying this, we can assume p is prime.

Two, Wilson's Theorem lets you cut the time in half. We now assume p is prime (having cut down the time earlier if the original p wasn't). Wilson's Theorem says (p-1)! = -1 (modulo p). Now say we want to calculate (p-k)! modulo p. We have obviously (p-k)! · ((p-k+1)·(p-k+2)· ... · (p-1)) = (p-1)!. This product is equal to (p-k)! · (-(k-1))·(-(k-2))· ... · (-1)) = (p-k)! · (k-1)! · (-1)^(k-1). The result modulo p is -1, so (p-k)!·(k-1)! = (-1)^k modulo p. So if p/2 ≤ N < p, then we let k = p - N, calculate (k-1)! modulo p, and solve N! · (k-1)! = (-1)^k modulo p. The problem is now mostly reduced to the problem of calculating N! modulo p for about 1,000 values 0 ≤ N ≤ p/2 ≤ $2^{31}$.

Three, Yuval's idea using a table with pre-calculated values N! modulo p will work if the task is to solve the problem for fixed p and different sets of 1,000 values N. If there are 1,000 values N you need 1,000k precalculated values to save a factor k. It doesn't work if p is variable.
And if it is possible to use multiple processors or vector units to do k calculations in parallel, then a factor k in time can be saved. Without these savings, it's 2 billion products modulo p in 1 second.

One idea is factoring N! into a product of powers primes. There are less than 100 million primes < $2^{31}$. However, since we have 1,000 values $N < 2^{31}$, I think many primes will have to be multiplied multiple times. Doing this in one second is tough.


YES if $\mathrm{P}\neq \mathrm{NP}$ and the $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones). In short, this is the equivalent statement of your conjecture.

Unconditionally, every $\mathrm{NP}$ problem not necessarily complete can be reduced to $3$-$\mathrm{SAT}$ by a reduction $f$ which is poly-time invertible. And composition $f \circ g$ of efficiently invertible $f$ and $g$ is also efficiently invertible. Therefore, if somehow we prove that $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones), then your conjecture holds.

When reducing to $3$-$\mathrm{SAT}$, simply append dummy clauses to the $3$-$\mathrm{SAT}$ instance. These dummy clauses just encodes the original instance. And of course, these are trivially satisfiable with brand-new dummy variables.

For example: suppose $x=x_1x_2\dots x_n$ is the original instance and your $3$-$\mathrm{SAT}$ instance already has $k$ variables, do the following:

for each original bit $x_i$:

if $x_i=0$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is even, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$
if $x_i=1$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is odd, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$
$k$ := $k + 1$

NO if $\mathrm{P} = \mathrm{NP}$. This is because if so, a sparse language can be $\mathrm{NP}$-complete rendering hopeless a poly-time injective reduction (from a non-spare language to it).
Your conjecture is impied by the much stronger isomorphism conjecture. That is why many attempts to partially resolve that conjecture (e.g. by deduce it from weaker statements like yours) all fail up to now.


Algorithm for detection of overlaping between vectors

If you have two line segments and you want to know if they intersect, see https://en.wikipedia.org/wiki/Line_intersection and https://en.wikipedia.org/wiki/Line_segment_intersection.

For next time, I'd expect you to do more research on your own.  See especially "computational geometry", e.g., a textbook that covers that area.


Denotational semantics of expressions with side effects

Since the question does not fully describe the language, I assume the simpler case when
 the $\texttt{++}$ operator applies only to variables given by an identifier, for
 example: $\texttt{foo++}$.  Short of having more examples of the way you write denotational semantic, I
 have to improvise a bit. In particular, I avoid lambda notation since I do not know whether
 you are using it, but I would prefer using it.

Other arithmetic binary operators (substraction, multiplication) are
similar to the $\texttt{E1+E2}$ case described in the question, and are explained similarly.

The simplest case is that of an expression which is only a lone variable $\texttt V$:

$[\![\texttt{V}]\!]_\mathrm{Exp}(S)=  (S(\texttt V), S)$

What it says is to get the value $S(\texttt V)$ associated to the variable $\texttt V$ in the state $S$ and to return that value, of course, but associated with the state $S$ unchanged, since the type of the denotation function requires such a pair as result.

Then we complement as follow for the prefix and postfix $\texttt{++}$ operator the
definition of the semantic function $Exp$ for expression $\texttt E$, when $\texttt E$ has
the form $\texttt{V++}$ or $\texttt{++V}$, i.e., when it is a variable.

$[\![\texttt{V++}]\!]_\mathrm{Exp}(S)=  (S(\texttt V), S1)$
  where $S1(v_1)=\;\; \text{ if } v_1=\texttt V \;\text{ then } S(\texttt V)+1 \;\text{ else } S(v1)$

The value returned is the same as in the case of the variable $\texttt
V$ alone. However, the state $S$ has to be changed to a new state $S1$
where the value corresponding to $\texttt V$ is incremented by $1$,
the rest of the state being unchanged.

$[\![\texttt{++V}]\!]_\mathrm{Exp}(S)=  (S(\texttt V)+1, S1)$
  where $S1(v_1)=\;\;\text{ if }v_1=\texttt V \;\text{ then }S(\texttt V)+1\;\text{ else }S(v_1)$

This case is identical to the previous one, except for the fact that
the value returned is also incremented by one, i.e. is the value
provided by the state $S$ for  $\texttt V$, but incremented by $1$.
But the state $S1$ returned is the same as in the previous case.

For the assignment statement, it would be easier if the question included the definition of $[\![\texttt{V:=E}]\!]_\mathrm{Pgm}$ that is
supposed to be modified. I am guessing, trying to be in accordance with what little information you give.

I suppose the result should be something like:

$\mathrm{[\![\texttt P]\!]_{Pgm} : State \to State}$

$[\![\texttt{V:=E}]\!]_\mathrm{Pgm}(S)= S2$
   where $S2(v_1)=\;\; \text{ if } v_1=\texttt V \;\text{ then } n \;\text{ else } S1(v_1)$
   and $(n,S1)= [\![\texttt E]\!]_\mathrm{Exp}(S)$

What this says in the first line is that the denotation of a statement
is a function that takes a state as argument, and returns another
state. The role of a statement is to modify the state.

Then the denotation function for the assignment statement
$\texttt{V:=E}$ will first evaluate the expression $\texttt E$ in the
environment $S$ provided as argument. This returns a value $n$ and a
new environment $S1$ which may be different from $S$ if there have
been side-effects while evaluating $\texttt E$. Then this environment
$S1$ is modified into an environment $S2$ which associate the value
$n$ to the variable $\texttt V$, and is otherwise identical to $S1$.
This environment $S2$ is the one produced by execution of the
assignment statement.

Other changes are probably necessary to fully account for side-effects
in the language. But I cannot know exactly what because the question
does not provide enough details about other language features.
There are many ways to write denotational semantics, and it depends on the whole of the language and the way features interact.

The version given above is a bit simplified, assuming that $\texttt V$
is the actual variable name. I chose this simpler version because you
do not provide examples of denotational semantics without
side-effects, and I was not sure what presentation to choose. But
there are other ways to present that.


Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1

I do not understand what you are trying to say after "--", but here is what you need to do:

Hopefully you understand the idea of turing machine encoding: i.e. you can assign a unique identifier (i.e. "label") $\alpha$ to each turing machine. So by $M_\alpha$ we mean the Turing machine labeled by $\alpha$. So you need to design a single turing machine $SU$ which takes three inputs $\alpha$, $t$ and $x$ ($\alpha$ is a turing machine label, $t$ is a space bound, and $x$ is an input string) and:

if $M_\alpha$ uses more than $t$ bits of workspace on input $x$ before it halts, then we have no requirement for $SU$
if $M_\alpha$ uses at most $t$ bits of workspace on input $x$ we have two requirements for $SU$:

$SU$ uses at most $Ct$ units of workspace where $C$ is a function of $\alpha$ but not $t$ or $x$
$SU$ outputs $M_\alpha(x)$

The idea is that for any machine and any input, $SU$ can simulate that machine while using only slightly more space than the original machine. Note that $t$ is a bound on the space that $M_\alpha$ uses, not the space that $SU$ uses. $SU$ cannot be exactly as space efficient as the original machine because simulation requires some overhead, but the point is that the overhead is small as $C$ is fixed for every $\alpha$, no matter how large $x$ is in size.

Theorem 1.9. also has some overhead: a machine which stops in $T$ time steps is simulated in $CT\log T$ time steps where $C$ is again some constant independent of $T$ or of the input string.


Are there any estimated, imperfect or fuzzy sorting algorithms?

The term you're looking for is approximate sorting. This is a topic that, as greybeard mentions in a comment, was more popular back in the 90s. But it's quite helpful for presorting (e.g. getting an array a little bit sorted to ensure that Quicksort doesn't get stuck in its worst case), and this is what's led to most of the research in the area.

You can, in fact, make it somewhat faster than full sorting. Giesen, Schuberth, and Stojaković showed that you can get $n$ elements sorted to a Spearman distance (*) of $\frac{n^2}{\nu(n)}$ in $O(n \min(\log n, \log \nu(n)))$. So the more you're willing to sacrifice accuracy (the smaller you make $\nu(n)$), the faster the algorithm can run.

Giesen, Schuberth, and Stojaković also present a very simple algorithm to do this approximate sorting, either deterministically or with a bit of randomness mixed in. The full details are in the linked paper, but basically they use Quicksort's partitioning a limited number of times and don't care about the order of the elements between the partitions, as long as they end up in the right "bin". If you pick your partitions well, this is in fact equivalent to running Quicksort and limiting the recursion depth.

(*) The Spearman footrule distance between two sequences is the sum of the distance between each element's intended position and its actual position. So if you swap two elements, that leads to a Spearman distance of 2: those two elements are each one position away from their intended place.


Your measure is known as the density of the graph, and is given by the formula $$ \frac{|E|}{\binom{|V|}{2}}, $$
where the graph is $G = (V,E)$.


As stated, $\log (n) = O (2^n)$ is trivially true.

All that it says is that $\log n$, in the end, grows no faster than $2^n$. For $2^n$, you can substitute $n$, $\sqrt n$, indeed any root of $n$.

However carelessly stated, I think this really refers to the following:

To represent a number of size $2^n$, you need $n$ bits.
So, to represent a number of size $n$, you need $\log n$ bits.

Bits are a measure of space.

I made heavy weather of this before, as I thought it was referring to the time it takes to calculate $2^n$. In case it is, I'll leave this in:

For $n$ a non-negative integer, and $f(n) = 2^n$

$$
f(n) =
\begin{cases}
1 &\text{for }\, n = 0 \\
(f (n \div 2))^2\times 2^{(n \mod 2)} &\text{for}\; n \gt 0
\end{cases}$$

The implied algorithm is clearly $\Theta (log \, n)$. But this is time complexity. In space complexity, it is $\Theta(1)$.

$\Theta (f)$ are the functions that, adapting the words of Wolfram
Mathworld, are no worse but also no better than $f$.
$O (f)$ are the functions that are no worse than $f$.


Token Scanner for programming Language(Lexical Analysis)

There's a common misunderstanding about why many construction algorithms (and most notably Thompson's) use ε-NFAs. It's not because it's necessary to do so, and it's not because it's efficient to do so.

Thompson's construction has the following advantages:

It's recursive on the structure of the regular expression.
It's easy to convince yourself that the construction is correct.
It's straightforward to incorporate certain extensions (e.g. the LEX lookahead operator "/").

Real-world implementations of regular expressions, even if they are based on Thompson's construction, typically optimise a dozen or so common base cases (e.g. Kleene closure of a character set; [a-zA-Z0-9_]* expands to something much bigger than it needs to be), saving Thompson's rules for higher levels.


Lower bound of disjointness by discrepancy?

You asked two questions.  I'll answer the second.  A rectangle is a set $R$ of the form

$$R = \{(x_1,\dots,x_n) : \ell_1 \le x_1 \le u_1, \dots, \ell_n \le x_n \le u_n\}$$

for some $\ell_1,\dots,\ell_n,u_1,\dots,u_n$.


It is a good question, certainly not trivial.

This problem is essentially counting the number of topological orderings. A topological ordering/sort is basically a valid ordering of completing the tasks in a dependency graph.

According to the link that @AndrásSalamon put into his comment, it is #P-complete: this means it is very hard to actually compute for a large number of tasks and dependencies.

They are expecting you to write a program that does it for just the small number of tasks that they give you. You probably need to do brute-force; i.e. try all possible orders, check if it is valid, and count them.

Alternatively, some smart variation of brute force, such as enumerating all possible topological orderings, and counting them.

Frequently this is the type of question asked by a competition:

An impossibly difficult question if extended to large input size,
Therefore, some sort of brute-force must be used,
But a smart variation of brute-force,
That can depend on the specific characteristics and limitations of the input they give you; if you don't take advantage of these limitations, and/or if you don't figure out the variation they want you to do, then your program will over-run its time limits.

You can also take a look at On Computing the Number of Topological Orderings of a Directed Acyclic Graph. To run this, you would make a dependency graph of the input tasks, then count the topological orderings using the algorithm(s) in this paper. I am not sure if this would finish in time on the input data you have; but one way to know would be to try it.


Why is `map insertionsort` not to equal to`map mergesort`?

It has to do with the axiom of extensionality, i.e. whether you accept it for functions or not.

The statement of this axiom with regard to functions is
$$\forall f,g:A \to B,\ ((\forall x:A ,\ f\ x = g\ x) \Leftrightarrow f = g).$$
Informally it means that if two functions are equal point-wise, then we consider them equal.

Syntactically merge-sort and insertion-sort are not equal, but if we don't care about their time and memory complexities (I mean if care only about their results) we can accept the axiom of extensionality and consider them equal. That means we can substitute one for another in every expression under consideration without actually changing anything. In this case $\text{map}\ f = \text{map}\ g$.

On the contrary, if we reject the aforementioned axiom, then we can only prove a statement like this:
$$(\forall x:A,\ f\ x = g\ x) \implies \forall xs:\text{list}\ A,\ \text{map}\ f\ xs = \text{map}\ g\ xs.$$
Notice that the conclusion is not the same as $\text{map}\ f = \text{map}\ g$.


Consider the example of the dependent type of number sequences of length $n$. It might be defined like this in Coq:

  Inductive Sequence : nat -> Type :=
  | nil : Sequence O
  | cons : forall (n : nat), nat -> Sequence n -> Sequence (S n).

For every n : nat we have a type Sequence n. We say that Sequence is indexed by nat or that Sequence depends on nat. We could also say that Sequence n depends on the index n.

In any case, we are just discussing terminology here. The following are equiavalent ways of saying the same thing:

Type $B$ depends on type $A$
$B$ is a type family indexed by type $A$
$B$ is a dependent type indexed by type $A$
$B : A \to \mathsf{Type}$
for $x : A$, $B(x)$ is a type
$x : A \vdash B(x) \ \mathsf{type}$

The reason we use the word family is that in mathematics a collection of sets indexed by a set, $\lbrace A_i \rbrace_{i \in I}$, is called a family of sets. It corresponds to a dependent type $A$ indexed by a type $I$.


It seems that the authors refer to "functions as first-class variables". In functional languages you have variables which store functions. You can think of them as program variables since they store programs. On the other hand, if you look at how the programs are stored physically, then you get unstructured variable data.

Let's be more concrete. The (somewhat functional) programming language Python has a function eval which takes as argument a Python program. Consider the following code:

prog = "sum([x for x in range(5)])"
print eval(prog)

This prints $10$ (since in Python range(5) = [0,1,2,3,4]). Here prog is a program variable since it stores a program. On the other hand, prog is also just a mundane string (variable data). From the point of view of Python, unless you try to evaluate it ("cast" it into a program), prog is basically just a string.

If we use an enumeration of programs like in recursion theory, then program variables really are unstructured — they are just integers. If Python supported this convention then prog would be just some number with no apparent structure.

In the same way, a set-theoretic function is just another set, unless you treat it as a function. Given two sets $A,B$, we can construct the set which contains all mappings from $A$ to $B$; I don't quite understand why only the "size" (i.e., cardinality) of this set matters, but I guess you'll have to wait until Chapter 5. Perhaps they mean that with the correct encoding function, every set of the correct cardinality can be used as an index set for all mappings from $A$ to $B$, just like the enumeration of programs mentioned above.


If L1 ∪ L2 and L1 are regular, is L2 also regular?

No, since $\Sigma^* \cup L$ and $\Sigma^*$ are regular languages, for any $L$ and there are non-regular languages, we cannot conclude anything about $L$.


$ACC^{0}$ vs Poly-size circuits of bounded degree

$ACC^0$ and $SIZE(n^k)$ are probably incomparable for all $k$.

$ACC^0$ is conjectured not to contain $Maj(x_1,..,x_n)$, which has linear size circuits (think about the naive Turing machine for majority and transform it into a circuit, things are much easier when you don't have a depth restriction). This shows that it probably holds that $SIZE(n)\not\subseteq ACC^0$.

On the other hand, $ACC^0$ does allow you to use polynomially many gates (with no degree restriction). We will show that under a certain assumption, for every $k\in\mathbb{N}$ it holds that $ACC^0\not\subseteq SIZE(n^k)$. Consider the problem of deciding whether a graph contains a $c$-size clique (where $c$ is a constant independent of the input).

This problem is obviously in $AC^0$ (for all $c\in\mathbb{N}$), since you can, in the first level, link all subsets of $c$ vertices into AND gates to check whether they form a clique, and in the second level link all the results from the previous level into an OR gate.

If this can be done using $SIZE(n^k)$ circuits, then $\mathsf{NP\subseteq P/Poly}$, since we can construct polynomial size circuits for CLIQUE. The circuit for $n$ vertices graph needs to be able to check the existence of an $1,2,...,n$ clique. Since finding $c$-cliques is in $AC^0$ for all $c$, and we assumed $AC^0\subseteq SIZE(n^k)$, we have an $n^k$ size circuit for each possible clique size, combining those will result in an $n^{k+1}$ size circuit for clique on $n$ vertices graphs, which puts $\mathsf{NP}$ in $\mathsf{P/Poly}$.


Helping prove this notation for Big-O(n!)

Remember that $\Theta(5n \log n^5) = \Theta(n \log n)$, since constant factors don't matter.

Then $\Theta(n \log n) = \Omega(n \log n)$, by the definition of big theta.

$\Omega(n \log n) = \Omega(n)$, because log is monotonic increasing (so we can remove it and still have a valid lower bound).

Finally, $\Omega(n) = \Omega(n^{2/3})$, by the properties of power functions.


How the kernel works in a LCF theorem prover

If I recall correctly, this was chapter 5 or 6 of John Harrison's Handbook of Practical Logic and Automated Reasoning.

Jon Sterling wrote some notes for a recitation a year or two back, specifically for an LCF prover using sequent calculus.


Is determining if there is a prime in an interval known to be in P or NP-complete?

So your problem is as follows:
Input: integers $\ell,u$
Question: does there exist a prime in $[\ell,u]$?
As far as I know, it is not known whether that problem is in P or not.
Here's what I do know:

Primality testing (given a single number, test whether it is prime) is in P, so if the range is small enough, you can exhaustively test each number in the range to see whether it is prime -- but this does not lead to a general algorithm.

If Cramer's conjecture is true, then the problem is in P.  Cramer's conjecture says that the gap between consecutive primes near $n$ is $O((\log n)^2)$, so the following algorithm will be in P: iterate through the numbers $\ell,\ell+1,\ell+2,\ell+3,\dots$, testing each whether it is prime; if you find one that is prime, stop immediately with a yes answer; if you hit $u$, stop with a no answer.  Cramer's conjecture tells us that you'll stop after most $O((\log \ell)^2)$ primality-tests, so that algorithm will run in polynomial time.
Unfortunately, the known results on prime gaps don't seem strong enough to prove unconditionally that the problem is in P.

Here is another simple algorithm: repeatedly pick a random integer $r$ from $[\ell,u]$, and test whether it is prime.  Stop if you find a prime, or if you've tried every integer in $[\ell,u]$ and none were prime.  Heuristically, we should expect this to be efficient in practice.  The prime number theorem tells us that if you randomly choose number in the vicinity of $u$, the probability it is prime will be about $1/\log n$.  Thus, heuristically, we should expect that after about $O(\log u)$ iterations, you'll typically find a prime and stop, if one exists.  On the other hand, due to the coupon collector's problem, if there is no prime in the range $[\ell,u]$, you'll stop after about $O((u-l) \log(u-l))$ iterations.  So, if we had a good upper bound on the size of the longest gap between prime numbers, this would imply that the problem is in BPP.  Even without such an upper bound, it follows that random problem instances are easy.

Probably one can apply sieving methods to improve the running time in practice (e.g., to avoid doing any primality testing on numbers that are divisible by a small prime).  I don't know whether this can be shown to lead to any asymptotic improvement.

Due to these techniques, the problem is probably easy in practice.

Due to the above remarks, I personally doubt that the problem is NP-complete.


Is the set partitioning problem NP-complete?

Karmarkar and Karp do not claim that the second problem is NP-complete.  It can't be, because it is not in NP. Remember that NP is a class of decision problems, i.e., problems where the answer is either "yes" or "no".  Because the problem is not in NP, it's not required that the answer be efficiently checkable.  The same thing happens with TSP: sure, if I give you a route around the cities and claim that it's less than 50 miles, you can check that easily; but if I give you a route and claim that it's the shortest, there's (probably) no way to check that in polynomial time.

Rather, the second problem is what is known as an NP optimization problem. It asks us to minimize a certain function $f$ and the decision problem, "Given $S$ and $k$, is $f(S)\leq k$?" is in NP.  Now, if this decision problem is NP-complete, the optimization problem is NP-hard: there's a trivial reduction from the decision version to the optimization problem.  Going the other way around, if you had an efficient algorithm for the decision problem, you could find out the optimum by binary search.


Query regarding the structure of Graph over All (known/unknown) NPC Problems?

The definition of NP-complete is that the problem is in NP and every problem in NP (including every other NP-complete problem) is reducible to that problem. So the graph you describe is not only strongly connected: it is a complete graph.
By the above, the distance between any two problems is 1. But, even if you follow a longer path of $k$ reductions, where the $i$th has polynomial blow-up $p_i$, the total blow-up for an input of size $n$ is $p_k(p_{k-1}(\cdots p_1(n)\cdots))$, which is still a polynomial.


Is it allowed to do a binary search with an oracle when proving NP-completeness?

Well, nowhere does the answer claim the reduction "implies that the original problem is in NP".  So, that explains your confusion.  You read something into the answer that isn't actually there.

Also, the answer says "Cook reduction".  This was a heads-up about the fact that it's not the Karp-style reduction you might be used to.  You might like to learn about the difference between a Cook reduction vs a Karp reduction.  Read https://en.wikipedia.org/wiki/Turing_reduction.  As you suspected, a Karp reduction is part of what is used in the definition of NP-completeness, but this answer isn't trying to prove NP-completeness, so the Cook reduction is "allowed".


Showing strong connectivity is in DSPACE((logn)^2)

You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.


Calculating a polynomial's coefficients from its roots

For every integer $i$, $0\le i\le n$, let
$$P_i(X) = (X-x_1)(X-x_2)\cdots(X-x_i)=a_{i,i}X^i+a_{i,i-1}X^{i-1}+\cdots+...+a_{i,0}$$
for some $a_{i,k}$, $0\le k\le i$. In particular, $a_{i,i}=1$. Expanding $P$ on both sides of the following equation and comparing the coefficients,
$$P_{i+1}(X) = P_i(X)(X-x_{i+1})$$
we see that for $1\le k\le i\lt n$,
$$a_{i+1,k}=-a_{i,k}x_{i+1}+a_{i,k-1}$$
and
$$a_{i+1,0} = -a_{i,0}x_{i+1}$$
So for fixed $i$, we can compute all coefficients of $P_{i+1}(X)$ from the coefficients of $P_i(X)$ with $O(i)$ steps. Now you should be able to see that your professor's suggestion on the minimum asymptotic complexity makes a lot of sense.


Proof that complement of HAMPATH is not in NP

The complement of HAMPATH is the following problem:

  Given an undirected graph, determine whether it doesn't contain a Hamiltonian path.

A YES instance for the complement of HAMPATH is a graph which doesn't contain a Hamiltonian path. It is not clear what a witness for this property would be. Contrast that with HAMPATH itself, in which the witness for having a Hamiltonian path is simply a Hamiltonian path.

It is not known whether the complement of HAMPATH is in NP, or equivalently, whether HAMPATH is in coNP.

However, it is considered unlikely that HAMPATH is in coNP, since this would imply that NP=coNP, which is considered unlikely by most researchers in the area.


Any algorithm for computing strongly connected components must examine at least $\binom{|V|}{2}$ entries in the worst case (proof below). In particular, since Kosaraju's algorithm is correct, its (worst-case) complexity is $\Omega(|V|^2)$, and so also $\Theta(|V|^2)$. There is no particular reason why Wikipedia used big O for one and bit $\Theta$ for the reader – probably a different author.

Edit: One possible reason for using big O rather than big $\Theta$ is that sometimes the algorithm is lucky and runs faster. Whether this happens or not could depend on the particular implementation of DFS.

Suppose $A$ is an algorithm examining less than $\binom{|V|}{2}$ entries. We will show that the algorithm cannot always know what the strongly connected components are. Run the algorithm, and for each entry of the adjacency matrix queried by the algorithm, return $0$. When the argument terminates, there are more than $\binom{|V|}{2}$ off-diagonal entries not queried, and in particular there exist vertices $i \neq j$ so that neither the $(i,j)$ nor the $(j,i)$ entry are queried. We could complete the adjacency matrix in two different ways: the all zeroes matrix, or the one in which both these entires are $1$. In the former case, there are $n$ connected components, in the latter, only $n-1$.


Just an idea that might work. Let original image be $I_0$. Erode just enough to remove the thin lines, then dilate back to obtain $I_1$. Afterwards, obtain the difference of the $I_0$ and $I_1$.


Calculate Stages in Non-Pipelined Processor

That processor should come with a manual. If yes, you can use the information in the manual. If no, you can google for the manual, like "8085 manual". The number of cycles and states for each instruction are in chapter 3, for example CPI = 7 states. Then you add up the numbers.


PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

This seems impossible if the translator has to be deterministic.
Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of two ways: either it reaches the end of input, or it reads $a^n b^n$ (which must also be the end of input).
Now let us modify your PDA so that instead of outputting $x^m y^n$, it checks that the rest of the input has the form $x^m y^n$. We obtain a deterministic PDA accepting the language of all words of the form $a^{n+m} b^n x^m y^n$, yet this language is not context-free (you can see this by intersecting with $a^*b^*y^*$ to get the language of all words of the form $a^nb^ny^n$).


Looking for a simple example of Transition Semantics

What do you mean by "transitional semantics"? If you mean structural operational semantics using transition systems, then maybe a good place to start is a good text on the semantics of programming languages, Examples:

Winskel's Formal Semantics of Programming Languages.
Hennessy's Semantics of Programming Languages.
Nielson & Nielson's Semantics with Applications.

I recommend ignoring denotational semantics for your task.

Since the semantics of programming languages is really well-understood, most of the work in formalising DSLs usually comes from the domain-specific part of the language.


You'll probably want to use a method for point cloud registration, also known as point set registration or point cloud alignment.  See, e.g., https://en.wikipedia.org/wiki/Point_set_registration.  RANSAC-like methods may also be useful.