minimizing the maximum between a degree of a tree and its height

Yes, it is true that $\dfrac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\dfrac{\log n}{\log \log n}).$ In fact, we have the following more accurate approximation,
$$\frac{\log n}{\log \frac {\log n}{\log \log n}} \sim \frac{\log n}{\log \log n}.\tag{app}$$

Proof. $$\begin{aligned}
\lim_{n\to\infty}\frac{\ \frac{\log n}{\log \frac {\log n}{\log \log n}}\ }{\ \frac{\log n}{\log \log n}\ }&=\lim_{n\to\infty}\frac{\log\log n}{\log \frac {\log n}{\log \log n}}
=\lim_{n\to\infty}\frac{\log\log n}{\log\log n-\log\log \log n}\\
&=\frac{1}{1-\lim_{n\to\infty}\frac{\log\log \log n}{\log\log n}}
=\frac{1}{1-0}=1.
\end{aligned}$$

So, if we set $k = \frac {\log n}{\log \log n}$, then the height of the tree,  $\frac{\log n}{\log \frac {\log n}{\log \log n}}$ is $\frac{\log n}{\log \log n}$ asymptotically and, hence, so is the larger one between the height of the tree and $k$.

Now, the question is what is the asymptotic behavior of the minimum of the larger one between $\log_kn $ and $k$, i.e. $h(n)=\min_k\max(\log_kn,k)$.

Since $k$ is increasing with respect to $k$ while $\log_k n$ is decreasing with respect to $k$, the minimum of the larger one between $k$ and $\log_k n$ for a given $n$ is obtained when $k=\log_k n$, assuming $k,n>1$.

What is the solution to $k=\log_k n$ for a given $n$?
$$k=\log_kn\Leftrightarrow k= \frac{\log n}{\log k}\Leftrightarrow \log k\cdot k= \log n\Leftrightarrow \log k\cdot e^{\log k}= \log n$$
By the definition of the Lambert $W$ function, we should have
$$\log k = W_0(\log n),$$
where $W_0(\cdot)$ is the principal branch of the Lambert $W$ function, as we are only interested in the real positive values. So,
$$k = e^{W_0(\log n)}.$$
Accordingly,
$$h(n)=\left.\max(\log_kn,k)\right|_{k=e^{W_0(\log n)}}=e^{W_0(\log n)}.$$

The same article on Lambert $W$ function tells that
$$ W_0(x) = \log x - \log\log x + o(1).$$
Substituting $\log n$ for $x$, we have
$$ W_0(\log n) = \log\log n - \log\log\log n + o(1).$$
So,
$$ h(n) =e^{W(\log n)}= e^{\log\log n} e^{-\log\log\log n} e^{ o(1)}=\frac{\log n}{\log\log n}\ e^{o(1)},$$
Since $e^{o(1)}$ goes to 1 when $n$ goes to infinity,
$$h(n)\sim{\frac{\log n}{\log\log n}}.$$

Combining the above conclusions, we see that if we set $k = \frac {\log n}{\log \log n}$, then the larger one between the height of the tree and $k$ approaches its minimum $h(n)$ as well as ${\frac{\log n}{\log\log n}}$ asymptotically.

To be nit picky, it should  be pointed out that we have been ignoring the expected requirement that $k$ should be an integer. It would require cumbersome analysis to adapt the above analysis and conclusion for integer $k$. In the end, we have still
$$\min_{1\lt k\le n,\ k\in\mathbb N}\max(k, \log_kn)\sim\frac{\log n}{\log\log n}.$$


While a specific program could be self-delimiting, in this context what we usually mean is a self-delimiting encoding of programs. An encoding of programs is self-delimiting if it forms a prefix code, that is, no program is a prefix of another program. Intuitively, programs are self-delimiting, so there is no ambiguity in where a program ends.
Why do we care? Consider the chain rule in Kolmogorov complexity, which expresses the idea that if there are short programs that generate $x$ and $y$, then there is a short program that generates the concatenation $xy$. If programs are self-delimiting, then a program for generating $xy$ could look as follows:

Run the following two programs in sequence.
Program for generating $x$.
Program for generating $y$.

Denoting the Kolmogorov complexity of a string $w$ by $C(w)$, this shows that $$ C(xy) \leq C(x) + C(y) + O(1). $$
(The $O(1)$ takes care of the first bit.)
In contrast, if programs are not self-delimiting, then it is impossible to tell where the program for generating $x$ ends. Therefore the chain rule for non-self-delimiting Kolmogorov complexity takes the more complicated form $$ K(xy) \leq K(x) + K(y) + O(\log K(x) + 1), $$
where $O(\log K(x))$ is needed to delimit the first program.
Self-delimiting programs are also useful for defining the universal distribution, which is a distribution on programs useful for understanding average-case complexity. The probability that the program $P$ comes up is $2^{-|P|}$. Since the valid programs form a prefix code, Kraft's inequality states that $\sum_P 2^{-|P|} \leq 1$, so this is a (sub-)probability distribution.
So far the advantages of prefix-free Kolmogorov complexity. The disadvantage is that whereas $K(w) \leq |w|$, this no longer holds for $C(w)$; instead we only have $C(w) \leq |w| + O(\log |w|+1)$.
You can read a lot more on these issues in the excellent monograph of Li and Vitanyi on Kolmogorov complexity.


How is it that programs can be identified with partial functions for programming language semantics?

Partial functions from initial program states to final program states are a suitable model for deterministic sequential programs that do not interact with the environment while executing. Such programs just try to compute a result depending on what they find in their starting state. If program $P$'s attempted computation fails when starting from some initial state $\sigma$, then that means that the function describing $P$'s semantics doesn't yield a final state for $\sigma$.

Using functions (of the common type mentioned above) makes sense when the constructs of the programming language under consideration are deterministic. That is the case e.g. for a language made up of assignment statements, sequential composition, conditionals, and while loops.

Partial as opposed to total functions are chosen for two reasons. 1. to allow loops to diverge and 2. to model problems such as division by 0.


On the hardness of satisfying K number of linear constraints

As j_random_hacker suggested, we can reduce MAX-2-SAT to this problem.

Given an instance of MAX-2-SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we can encode it as the following constraints:

For each variable $x_i$, add $m$ identical constraints: $x_i\le 0$ (if identical constraints are not allowed, we can use $x_i\le 0,x_i\le 0.1,x_i\le 0.01,\ldots$ instead) and $m$ identical constraints: $x_i\ge 1$.
For each clause, say $x_i\vee x_j$, add a constraint $x_i+x_j\ge 1$. If a negative literal is involved, for example, $x_i\vee\neg x_j$, then the constraint becomes $x_i+(1-x_j)\ge 1$.

Now we can conclude that there exist $nm+k$ constraints that can be simultaneously satisfied if and only if there exist $k$ clauses that can be simultaneously satisfied in the MAX-2-SAT instance.


Classify the set of all TMs whose languages from the accepting problem

As suggested in the comments, the extended version of Rice's theorem clearly states this language is not in $RE$. Nevertheless, let us prove this claim via a direct reduction from a language known not to be in $RE$, let's say
$$ \overline{HP} = \{\langle M,w\rangle \mid M \text{ doesn't halts on }w \}$$

We will show that $\overline{HP} \le L$ and conclude that $L \notin RE$.

The reduction will assume we have a machine that recognizes $A_{TM}$ (call it $R$) and goes as follow. Given an input $\langle M,w\rangle$ we construct the output string $\langle M_w\rangle$ which is a machine that, on input x, does:

repeat the loop:
1.1 run one step of $M$ on $w$
1.2 run one step of $R$ on $x$
1.3  if 1.1 halts - the machine $M_w$ rejects. If 1.2 accepts - the machine $M_w$ accepts.

It is easy to verify this is a computable reduction. Let's just verify it is valid.

Case I: $\langle M,w\rangle\notin \overline {HP}$, then eventually (say after $T$ steps)  $M$ will halt on $w$ before the computation of 1.2 concludes, thus $L(M_w)$ can be decided in less then $T$ steps and in particular it is decidable. Therefore $A_{TM} \not\le L(M_w)$ and thus $\langle M_w\rangle \notin L$.

Case II: $\langle M,w\rangle\in \overline {HP}$, then $M$ never halts on $w$, which means that only step 1.2 is relevant, which means that $M_w$ behaves in this case just like $R$. So it holds that $L(M_w) = A_{TM}$ and in particular, $A_{TM} \le L(M_w)$. Then, $\langle M_w \rangle \in L$.


Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC

You cannot implement this part in NL:

nondeterministically check something
if yes, return no

Consider the following analogy: the language $K$ of all Turing machines that halt is recursively enumerable but its negation isn't. That is, $K$ is accepted by some nondeterministic Turing machine, but its negation cannot be accepted by any nondeterministic Turing machine. This means that you provably cannot implement the following using nondeterminism:

nondeterministically check if the given Turing machine halts
if yes, return no

Your idea suffers from the same problem.

Here is a different angle. The following algorithm checks nondeterministically that $s$ and $t$ are connected:

guess a path $w$ from $s$ to $t$
verify that $w$ is a path; if so, output yes, otherwise, output no

The semantics of this algorithm are as follows:

If there is some witness that causes the algorithm to output yes, then the input is a yes input.

If all witnesses cause the algorithm to output no, then the input is a no input.

What you are trying to do is as follows:

guess a path $w$ from $s$ to $t$
verify that $w$ is a path; if so, output no, otherwise, output yes

All inputs are yes instances in this case, since there is always some witness $w$ that isn't a path from $s$ to $t$.
In order to check that there is no path, you would have to do the following:

go over all possible paths $w$ from $s$ to $t$
if none of them works, output yes, otherwise, output no

Unfortunately, this doesn't describe a nondeterministic Turing machine.


What kind of language would you suggest for an University compiler project?

I think you are trying to achieve too much in a single exercise. It would, in my opinion, be better to separate the compiler construction part of the exercise from the comparative language part.

Good code generation and optimisation are difficult for some of the additional features you have cited. In my view it is better that students learn to do some decent lexing, parsing, optimisation and code generation before having to handle some of the more complex features of languages.

If you create a portmanteau of a language you end up with lots of examples of rotten and partially functioning compilers which do not help them learn.

It also matters what the target language you are going to use. Are you asking them to generate CIL, Byte Code, C  or some other output format? Each of these has different pedagogic reasons for their choice.

Choosing a language to build an example compiler for is like choosing a first programming language. There is no right choice.

To start building compilers I often recommend compiling something like Pascal or even simpler. (The choice of compiler implementation language depends on the tool set you choose to teach.)


Constructing a directed graph for O(1) queries

Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.


What is a non-ambiguous CFG for generating the set of natural numbers?

"From what I understand, there is not an algorithm to determine whether my guess is correct." It looks like your understanding is wrong.

There is no algorithm that determines whether any given formal language grammar is ambiguous context-free. There is no algorithm that determines whether any given formal language grammar is inherently ambiguous context-free. However, it is possible to decide many particular grammars is (inherently) ambiguous context-free or not by some algorithms.  For example, the trivial algorithm that just outputs "ambiguous context-free" determines the grammar with rules $S\to A|B$, $A\to c$, $B\to c$ as ambiguous context-free. For example, the trivial algorithm that always outputs "not inherently ambiguous context-free" determines all regular grammars as not inherently ambiguous context-free.

As said by rici, your grammar is regular. There is an algorithm that can decide any given regular grammar is ambiguous or not. (Immediately by definition, a regular language is context-free.). As demonstrated by Dmitri Urbanowicz, your grammar is, in fact, not ambiguous.

As said by Dmitri Urbanowicz, your grammar is wrong since it cannot generate number 101. Here is a correct grammar, which can be shown to be non-ambiguous context-free.
$\quad S \to BT|A$
$\quad T \to AT|A$
$\quad A \to B|0$
$\quad B \to 1|2|3|4|5|6|7|8|9$


Optimal algorithm to traverse all paths in the order of shortest path

The goal is to find all paths from $s$ to $t$ in a directed, acyclic graph with edge costs. Let $n$ the number of nodes, $m$ the number of edges and $p$ the number of $s$-$t$-paths. Let's look at what we have.

Naive enumeration

Use any graph traversal from $s$ to find all paths.
Sort them by length.

You can interleave the steps, but you'll end up with runtime $\Omega(n + p \log p)$ if there are $n$ nodes and $p$ paths.

Note that this algorithm is easy to parallelise.

Eppstein's Algorithm [1]

This one has runtime $O(m + n \log n + p)$ (from skimming the paper, I assume the bound is sharp, i.e. $\Theta$ holds). Note that paths are not represented explicitly.

I have no idea how well this algorithm can be parallelised.

Lower bounds

First of all, $p \in \Omega(2^n)$ in the worst case even in DAGs, see for instance this class of graphs:

[source]

Note that all nodes have small out-degree and all paths have the same length.

Therefore, $p$ dominates any algorithm for this problem (in the worst case) if we can not make further assumptions.

When you go for a traversal over all paths, you clearly have runtime $\Omega(p)$.

Conclusion

Eppstein's algorithm is asymptotically optimal even in the setting you describe. However, asymptotic analysis at this level is rough and hides "extra" work that may or may not pay off in practice (since $n$ does not tend to infinity). The naive version may very well be competitive in an application, depending on $n$, $m$ and $p$, and maybe even structural features.

Another thing to keep in mind is that above figures are all worst-case but you are probably after average runtime on some specific input set².

TCS papers are unlikely to contain a rigorous analysis that helps you decide (and it's hard to do, too). Your question reads as if your goal is a real-world application, so I recommend a pragmatic approach. If the naive approach is too slow for you, try parallelising it. If that is still to slow, you can invest the time, implement Eppstein and run some tests.

Finding the k Shortest Paths by D. Eppstein (1998) [preprint]
My group developed a method for semi-automated average-case analysis and a tool to perform it. Have a look, maybe it can help you find out more about performance on your data.


What do I need to study in order to understand and design a programming language?

I do not understand what is your intended meaning in "understand the
specs of an already made programming language". There are always many
things to be understood in a complex entity, and any understanding
must be related to a purpose.

If your purpose is just to understand how to program with this
language, understanding how it is implemented is not, and should not
be your problem. Certainly not at first. What you have to understand
is the high level concepts used in the language, and that may depend
very much on the language. You need to understand the style of
programming the language is promoting. All that comes to some extent
with the manuals and tutorials. But some concepts may require advanced
knowledge, some of which may be general, and some which may be very
specific. What you should learn will be clear from the manuals and
tutorials.

If you want general knowledge on language architecture, on the role of
syntax and semantics, on the main techniques useful to write compilers
and interpreters, you should get a book on compiler writing. Many will
do.  The most popular is probably the Dragon Book in one of its
successive edition.

To design a programming language, there is no specific study, other
than a good understanding of the structure and concepts used generally
in programming languages (see above). A good knowledge of logic and mathematical style cannot hurt. Knowing many programming languages with preferably very different styles is probably a prerequisite. The hard part is knowing why you
want to do it, and what for. A language is a vehicle for
communication. Hence, if you are alone using it you are wasting your
time (unless it is a proof of concept, which is usually related to
some advanced theoretical work). You have to have a purpose for your
language, and an idea that it is better for that purpose than other
languages that may already exist. If you still have to read what is
useful for designing it (other than general knowledge - see above),
you are not ripe for designing one. The needed knowledge must precede
the intent to design a language. It must be the expression of a need,
before it becomes a will. Actually this is often true of creative activity.

Languages are not necessarily general purpose languages. They may be
very useful without having Turing power. A language must be thought to
express some concepts in a given domain of discourse. For example,
languages like HTML, or TeX. are intended to express textual layout of
documents. They can be very sophisticated, but not intended to write
graph algorithms or matrix processing. Other languages may appear like
weak algorithmic languages because they have been designed to posses
specific properties that more general languages will not have, such as
automatic analysis of their computational characteristics. Some
languages may use specific kinds of parallel processing that are
easier to analyze and optimize.`Some of these specific languages, or
some features of more general languages require high mathematical
sophistication in specific domains.  Naming them here would just be
name dropping.

Regarding processor architecture, I cannot help you. It is largely a
different topic, though it does matter for some aspects of compiling,
and I am not competent.

If you want to see an interpreter written in half a page, that
implement a general purpose programming language that was actually
used a lot (in more sophisticated versions, to be honest), look for
the Lisp 1.5 interpreter. It is somewhere in this old book.


Neural network game players and incremental updates

The AlphaGo algorithm does not benefit from this kind of optimization.  It's hard to share an intuition for why without diving into the details of the algorithm, but at a coarse level: a single small change to the board can make a dramatic change to the strategic nature of the position, so it's not clear that one can reuse calculations effectively.  In particular, it sounds like you are assuming that AlphaGo does some computation separately for each square of the board, so we could avoid re-doing the same ones for squares that haven't changed.  However, that's not at all how AlphaGo works, so that kind of optimization is not applicable here.


Suppose there is a machine using $n$ states which, at some point, has $X$ nonzero symbols on the tape. One can build a machine with $O(n)$ states which simulates a run of the original machine with a tape alphabet of three symbols $\{0,1,2\}$, with the following small change: whenever the original machine changes $1$ to $0$, the new machine changes it to $2$; whenever the tape is read, $2$ is interpreted as $0$. The new machine ends up with $Y \in [X,2X]$ nonzero symbols on the tape (we get $\Theta(X)$ instead of $X$ since the simulation requires using two symbols for each original symbol). So your new function, let's call it $F(n)$, satisfies $B(n) \leq F(n) \leq B(O(n))$.


How to move spheres in 3d without collision

Here's how I would do it:
Create an oriented bounding box around the path of each sphere, with dimensions equal to the sphere's diameter. Now perform collision detection on all of those bounding boxes. For the ones which do not collide, their correlating sphere's can travel at max velocity.
For the bounding boxes that DO collide, do they collide at a point equidistant to the spheres' starting points (+/-  radii)? If not then they are free to move at max velocity.
If they DO collide at an equidistant point(+/- radii), then you must slow one sphere down so that it will not collide.

Hope this helps.
Good luck!


What does it mean to be "closed" under beta reduction?

The claim is that after applying β-reduction to an expression in A-normal form you can be left with an expression no longer in A-normal form.

The only explicit definition I can find of A-normal form is not consistent with the definition Kennedy seems to be (implicitly) using in this paper.  Wikipedia defines A-normal form as the subset of lambda calculus expressions where only constants, $\lambda$-terms, and variables can be arguments of function applications, and then (vaguely) says that results of non-trivial expressions must be captured by let-bound variables.

That is: f(g(x)) is not in A-normal form because the argument to the application of f is another application (g(x)) rather than a constant, $\lambda$-term, or variable.  This expression in A-normal form would be something like let y=g(x) in f(y).

Kennedy uses the vague "definition"

  a let construct assigns names to every intermediate computation. (Section 1.1.ANF).

But then in Section 1.2 he gives an example of an A-normal form not being preserved under β-reduction

  Consider the ANF term let x = (λy.let z = a b in c) d in e.  Now naïve β-reduction produces let x = (let z = a b in c) in e which is not in normal form.  The ‘fix’ is to define a more complex
  notion of β-reduction that re-normalizes let constructs (Sabry and
  Wadler 1997), in this case producing the normal form let z = a b in (let x = c in e).

So apparently Kennedy's variant of A-normal form places some kind of restriction on what can be in the assignment part of a let clause, but I can't figure out what (or why) that restriction is.  In addition to Kennedy's paper you linked, I looked in several of his references:

  Amr Sabry; Philip Wadler: A reflection on call-by-value. ACM T. Prog. Lang. and Sys. (TOPLAS), 19(6):916-941, 1997.

  Amr Sabry; Matthias Felleisen: Reasoning about Programs in Continuation-Passing Style. Lisp and Symbolic Computation 6(3-4):289-360, 1993.

  Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.; Felleisen, Matthias: The Essence of Compiling with Continuations. Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation, (PLDI):237-247, 1993.


Integral solutions to circulation problem

Circulation problems are not just a generalization of max-flow, there is a reduction backwards as well. Suppose we have some directed graph $G = (V, E)$ with edge costs, capacities, and lower bounds.
Any edge $u \to v$ in $G$ with we can replace with two nodes $s, t$ and two edges $s \to v$ and $u \to t$ where one of the edges has the original cost, capacities, and lower bounds and the other is free and unlimited. Call this graph $G'(e)$, where $e = u\to v$ is the edge that was replaced.
Then if a flow with a certain cost exists in $G'(\cdot)$, it must also exist as a circulation in $G$ with the same cost. Vice versa, if a circulation exists in $G$ and it uses edge $u \to v$, then that flow also exists in $G'(u\to v)$ with the same cost.
Therefore to solve the circulation problem we can pick an arbitrary edge $e$, calculate $G'(e)$ and use a traditional network flow algorithm to find the optimal flow. By the traditional arguments, this optimal flow is integral. We then pick another edge (avoiding edges that were part of a previous optimal flow) and repeat, keeping the best solution, until no more unknown edges are left.
Since in the worst case this adds a factor of $|E|$ to the complexity of the polynomial complexity, this is still polynomial. And of course the optimum from all integral flows found is itself integral.
To handle the lower bounds on the edges of $G'$, one can either note that the linear programming constraint matrix is unimodular (see these MIT lecture notes), from which it follows that there exists an integral solution if there is any solution; or one can use a standard reduction to eliminate the lower bounds (see, e.g., Ahuja et al, Network Flows, page 39) and then solve with a standard algorithm for network flow.


Conceptual question about entropy and information

Information = Entropy = Surprise = Uncertainty = How Much You Learn By Making an Observation.  They all increase or decrease together.  The entropy of a random variable $X$ is just another number summarizing some quality of that random variable.  Just like the mean of a random variable is the expected value of $X$ or the variance of a random variable is the expected value of $(X - \mu)^2$, the entropy is just the expected value of some function, $f(X)$ of the random variable $X$.  You find expectations of functions by using
$\mathbb{E}[f(X)] = \sum_{x\in X}p(x)f(x).$  In this case the function of $X$ you care about is the log (base 2) of the probability mass function.

$$ H(X) = \mathbb{E}[-\log_2 P(X)] = -\sum_{x \in X} p(x) \log_2 p(x).$$

This particular expectation is useful because it doesn't depend on the actual values that $X$ can take on, just the probabilities of those values.  So you can use it to talk about situations where you aren't sending numbers, or where the numbers are just arbitrarily assigned to particular messages or symbols that you need to send.

What you want for your second question is the conditional entropy of the measurement random variable $X$ given the random variable $Y$ that represents what was sent.  When there is no error the conditional entropy will be 0, when there is error the conditional entropy will be greater than 0.


Efficiently calculating minimum edit distance of a smaller string at each position in a larger one

What you are interested in are semi-global and/or local alignments. The usual way to compute those is to adapt the dynamic programing algorithm for the Levenshtein distance:

Initialise the first row/column with $0$ (instead of $i$/$j$) if free deletions/insertions are allowed at the beginning.
Select the minimum value from the last row/column as result if free deletions/insertions are allowed at the end.

Different combinations are possible. In your case, assume that $r$ is the horizontal word, you initialise the first row with $0$ (the first column with $i$, no change here) and the result is the minimum of the last row. The result is then the smallest Levenshtein distance between $s$ and any substring of $r$, computed in time and space $O(nm)$.

Now, in order to get scores for all starting positions, note that the computation of semi-global alignments with allowed deletions/insertions at the end conveniently provides the wanted array in the last row/column -- well, almost: that gives you the best matches against prefixes up to position $k$. So in order to get best matches against suffixes from position $k$, reverse both $r$ and $s$.


Write down brightness and contrast as functions that act on a single gray-scale pixel. As you said, brightness is $b(x) = x + \alpha$ and contrast is $c(x) = \beta(x - x_\text{mean}) + x_\text{mean}$ or something similar. Now all you need to show is that $b \circ c \neq c \circ b$.


Calculate number of cache lines per set or cache size

You can calculate it with the help of tag, index, and offset bits. Read about it here.


Should I describe automata before describing grammar?

In mathematics, the only thing that you absolutely must do is prove every theorem. Everything else is optional. In this case, you are asking whether every grammar formalism must be accompanied with a corresponding machine model. There is no such requirement, simply because not all grammar formalisms have a corresponding machine model which is natural. It is just a "nice to have" feature. More generally, the definition of a new class of languages is more convincing if the class can be defined in many seemingly different ways.

Another thing which you don't have to do but is "nice to have" is discussing closure properties of your class of languages, discussing the complexity of the classical decision problems for your class, and relating your class to other classes of languages. This is how people have studied language classes in the past, and so you would be expected to do it.


If there is a comparison sort whose running time is $f(n)$ on $g(n)$ of the inputs, then there are at least $g(n)$ leaves at depth at most $f(n)$, and so $g(n) \leq 2^{f(n)}$.


Why do some inference engines need human assistance while others don't?

Validity of higher order formulae is in general not decidable and search spaces are huge, so all you can hope to do is to try to find a proof -- assuming it exists -- by cleverly enumerating the proof space (think sledgehammer, aptly named) but that is rough. Humans can play the oracle, providing the key lemmata to guide proof.

Automated provers, on the other hand, typically deal only with decidable (subsets of) logics, for instance propositional logic or subclasses of first-order logic, so they may run a long time but you know they are going to be successful eventually.

Note that there are approaches to enable proof assisstants to find those important lemmata, e.g. IsaPlanner. The tool guesses (inductive) lemmata by enumeration and random testing and then tries to prove them. By iterating the process, many lemmata of e.g. typical data type definitions can be found automatically.

Small ABC

validity -- a formula is valid it holds whatever you assign to the free variables.
free variables -- those variables that are not bound by quantifiers such as $\forall$ and $\exists$
decidability -- a (boolean) property is (Turing) decidable if there is an algorithm that answers "yes" or "no" (correctly) after a finite amount of time.
propositional logic -- also zero order logic; no quantification allowed.
first order logic -- quantification is only allowed over individuals, i.e. you can do $\forall x. P(x)$ but not $\forall f. f(4) > 0$.
higher order logic -- you may quantify over (and "build") arbitrarily complex objects, e.g. higher order functions (functions that take functions).


Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $

If $j \neq i$ then either $j < i$ or $j > i$. Hence you can write your language as
$$
\{ a^i b^j : j < i \} \cup \{ a^i b^j : i < j < 2i \}.
$$
It suffices to find a grammar for each of these two languages. Such questions have been asked and answered on this site.


What is the relationship between problems and languages?

Decision problems and languages are just the two sides of the same coin: every problem can be rephrased as the membership problem of some language.  The problem of, say, determining whether a number is prime is exactly the membership problem of the language of prime numbers.

Formally, a language is a set of finite strings over some fixed finite alphabet (sometimes, the strings are allowed to be infinite; that's a different but related scenario).  Problems that aren't directly questions about strings will need to be encoded as strings so, for example, it would have been more precise to write the last sentence of the previous paragraph as, "If we fix an alphabet and an encoding of natural numbers as strings over that alphabet, the problem of, say, determining whether a number is prime is exactly the membership problem of the language of strings that encode prime numbers."

To quickly run through your subquestions,

  We know that the set of all languages uncountable. Is the set of problems also uncountable?

Yes, since problems and languages are essentially the same thing.

  Can every problem be defined by a language?

Decision problems, yes. Optimization problems (what's the smallest X with property Y) and counting problems (how many X's have property Y) can be rephrased as decision problems (is the Z the smallest X with property Y?; are there N X's with property Y?), though that's usually not the most natural way of treating them.

  Can a language solve more than one problem and vice versa?

Yes and yes, because you have to use encodings to translate between problems and langauges. For example, the languages $\{10,11,101,111,1011,\dots\}$ and $\{2,3,5,7,11, \dots\}$ both encode the primality problem (in binary and decimal, respectively). Conversely, though perhaps a little artificially, the language $\{0, 10, 110, 1110, \dots\}$ encodes the problem of determining whether a binary number is of the form $2^k-2$ for some $k$ and the problem of determining whether a string of 1's and 0's has exactly one 0, which is its final character. (Perhaps somebody can come up with a better example of a language that naturally encodes two problems without one being such a trivial rephrasing of the other.)

  Is there one-to-one correspondence between problem and languages?

No, since this question is just the complement of the previous one. :-)


Randomized communication complexity of indexing

It is known that the randomized communication complexity of inner product on $m$ bits is $\Omega(m)$. You can compute inner product using a protocol for the indexing function on $\{0,1\}^{2^m} \times [2^m]$ as follows: denoting Alice's input by $x \in \{0,1\}^m$ and Bob's by $y \in \{0,1\}^m$, Alice computes a new vector $X$ by $X_y = \mathsf{IP}(x,y)$, and the parties run the indexing protocol on the inputs $X$ and $y$. This gives an $\Omega(m) = \Omega(\log n)$ lower bound for indexing.


Function that is not Space Constructible

Usually such examples are specifically "tailored", using hard problems.
Perhaps the easiest way is to take the halting problem:
$$HALT=\{\langle M\rangle: M\text{ is a TM that halts on }\epsilon\}$$
and consider the encodings of TMs as numbers, in such a way that no two numbers are encoded to the same TM (e.g. by leading 0s). This can be achieved using unary encoding, for example.

Now, consider the function $f:\mathbb{N}\to \mathbb{N}$ defined as follows:
$f(n)=2n$ if $n$ represents a TM in HALT, and $f(n)=2n+1$ otherwise.

This function is $\theta(n)$, but clearly it is not space constructible, since constructing it would enable you to solve the halting problem.

A similar example can be constructed from a problem which is harder than PSPACE (e.g. a problem complete in EXPSPACE).

However, these example are somewhat "ugly". A more elegant example is the busy beaver function, which is non-computable simply because it "grows too fast".


undecidability proof by using Turing Machines

We have the language (commonly called $A_\text{TM}$):
$$
A_\text{TM}=\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\}
$$
and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.

We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description and as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as both inputs).

Now you've correctly interpreted the action of TM $D$:

  $D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.

In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.

Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ its own description as input? The action of $D$ on its own description is now

  $D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.

This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A_\text{TM}$ must be undecidable.


The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial time whether to accept or reject).
Since $BPP\subseteq \Sigma_2\cap \Pi_2$  it immediately follows that $MA\subseteq \Sigma_2\cap \Pi_2$, which is believed to be a strict subset of PSPACE which contains the entire polynomial hierarchy.


The set of turing machine that stops with input zero is not recursive

Hint: if you want to know whether $M$ accepts $w$, build a machine that replaces its input with $w$ and then does whatever $M$ does.


Let us notice the following:
$$
|\sin(\pi \cdot n/2)| = \begin{cases} 1 & \text{if $n$ is odd}, \\ 0 & \text{if $n$ is even}. \end{cases}
$$
This implies that your function $f(n)$ alternates between $n^2$ (for odd $n$) and $0$ (for even $n$). This means, for example, that $f(n) = O(n^2)$ (since $f(n) \leq n^2$ for all $n$) but $f(n) \neq \Omega(n^2)$ (considering even $n$).


What is the fastest algorithm to solve $k$-path problem?

For FPT algorithms (ignoring the polynomial factors), there is a $2.851^k \cdot n^{O(1)}$ deterministic algorithm and a $1.66^k  \cdot n^{O(1)}$ randomized algorithm.

See Table of FPT races for references.


Your problem is that your trick of representing set membership using arithmetic only applies to sets consisting of numbers only. Say you have a set of colours { red, green } then 1 - sgn (x - red)^2 doesn’t make any sense. Even worse is a set containing other sets as elements.


Precise definition of oracle classes $A^B$

The simplest case is when $C$ has complete problems with respect to $\mathsf{F}B$ reductions (the function class corresponding to $B$). In that case, you can define $B^C$ as $B^L$ for some $C$-complete problem $L$, and everybody will be (mostly) happy, at least if $B$ is not a very weak class. This allows us to define $\mathsf{P}^{\mathsf{NP}}$, for example.

When $C$ doesn't have complete problems, sometimes the following definition is used: $B^C = \bigcup_{L \in C} B^L$, or perhaps $B^C = \bigcup_m \bigcup_{L_1,\ldots,L_m \in C} B^{L_1,\ldots,L_m}$. However, this definition doesn't necessarily have the right properties.

Another option is if you can enumerate all languages in $C$ (for example, $\mathsf{BPP}$ can be enumerated using probabilistic Turing machines with an explicit time bound), say they are $(L_n)_{n \in \mathbb{N}}$. In that case you can define $B^C = B^{L_1,L_2,\ldots}$, where the oracle for $L_1,L_2,\ldots$ accepts an index $i$ and a word $x$, and outputs whether $x \in L_i$. One drawback is that this definition depends on the enumeration; it's best to use a "natural" enumeration. Otherwise, you can "cheat" by putting information into the enumeration. A way out it to define $B^C$ as the intersection of $B^{L_1,L_2,\ldots}$ for all possible enumerations.

Things become even more complicated when $B$ is weak. For some of the issues involved, see Aehlig, Cook, and Nguyen, Relativizing Small Complexity Classes and their Theories. These issues are orthogonal to what we have described above: they cause problems even when trying to define $B^L$ for a language $L$.


Is the language that accepts strings concatenated with their reverse regular?

You're over-thinking it on the $xw^R=ww^R$ thing, that's a red herring. But you're not over-thinking it by looking for a contradiction, you're looking in the wrong place.

First, your proof that the language is irregular is correct. You're aiming to show a contradiction. All you need is one counterexample; just one! And you found it already. This may seem paradoxical, but your understanding of how to operate on languages is a little off. As you noted, regular languages are closed under reversal:

$L^R = \{w^R|w\in L\}$

They are also closed under concatenation:

$L\circ L^R = \{wv|w\in L, v\in L^R\}$

But, you see, that's a little different from $L_{mirrored} = \{ww^R|w\in L\}$. Look:

$L = \{$ cat, dog$\}$

$L^R = \{$ tac, god$\}$

$L\circ L^R = \{$ cattac, catgod, dogtac, doggod$\}$

$L_{mirrored} = \{$ cattac, doggod$\}$

There's your contradiction! You must have thought those last two were the same, when they're not. Rather,

$L_{mirrored} \subseteq L\circ L^R$

And the subset of a regular language is not necessarily regular.

edit: I removed a large chunk of this answer, so the comments below will probably be confusing...


Name of this rearranging/sorting problem?

Note: It is a hardness proof, and I think there are practical algorithms like integer programming, etc.

Given a BIN_PACKING instance where you want to pack $K$ numbers $n_1,\ldots,n_K$ into $L$ bins of size $m_1,\ldots,m_L$, and it is ensured that $\sum n_i=\sum m_j=N$, then we could design a instance of your problem as follows:

There are $K+(N+1)(L-1)$ classes;
The first $K$ classes have size $n_1,\ldots,n_K$ respectively, and each of the rest classes have size $N+1$;;
The array is partitioned into slots of size:
$$m_1,(N+1)^2,m_2,(N+1)^2,m_3,\ldots,(N+1)^2,m_L$$
where each slot of size $(N+1)^2$ is packed with $N+1$ classes, arranged contiguously, and the rest are arbitrarily arranged.

Now a key observation is that it is meaningless to keep at least one class in a $(N+1)^2$ slot unmoved and move other ones (because it won't change the size of a 'bin'). So the original bin packing is available if and only if the minimum number of swaps is no larger than $N$. Since BIN-PACKING is known to be strongly NP-complete, your problem is NP-hard.


Why are computable functions continuous?

There are several ways to explain "computable implies continuous", I shall give here two such explanations.

Turing machines compute continuous maps

Suppose we have a Turing machine which takes possibly infinite amount of input written down on an input tape. It writes the result on an output tape, where the output cells are write-once. There are workign tapes. The machine may run forever, filling up the outputs cells. This is known as a type two machine. (The argument for other kinds of machines is going to be similar but simpler.)

The following should be obvious: when the machine writes into an output cell, its workings up to that point only depends on a finite portion of the input tape, for the simple reason that in finitely many computation steps it could not have moved the input head past some point. Therefore, every input tape that agrees with the given one up to that point would have caused the machine to write the same answer to the same output cell.

But this is a form of continuity, if we put the correct topology on the spaces of input and output tapes.

First we put topology on the set $\Sigma$ of symbols that can be written onto tape cells. For this we just pick the discrete topology. A tape is an infinite sequence of symbols, so an element of $\Sigma^\omega$, which is a product of $\Sigma$'s. Let's put the product topology on it.

Recall that a basic open set on $\Sigma^\omega$ for the product topology is of the form $U(a_0, \ldots, a_{n-1}) = \{\alpha \in \Sigma^\omega \mid \forall i < n . \, \alpha_i = a_i\}$, where $a_0, \ldots, a_i \in \Sigma$. That is, a basic open set fixes an initial portion of the sequence to the given values $a_0, \ldots, a_n$.

Now we may check that the function $f : \Sigma^\omega \to \Sigma^\omega$ computed by the machine is indeed continuous. Take a basic open set $V = U(a_0, \ldots, a_{n-1})$ and let $W = f^{-1}(V)$. We need to verify that $W$ is open. For this purpose, consider any $\alpha \in W$. If we find a basic open set $W'$ such that $\alpha \in W' \subseteq W$, then we're done.

Because $\alpha \in W$, we have $f(\alpha) \in U$. Thus on input $\alpha$ the machine produces an output tape starting with $a_0, a_1, \ldots, a_{n-1}$. By the time it writes out these cells it has inspected at most the first $k$ cells of the input, for some $k \in \mathbb{N}$. We may take $W' := U(\alpha_0, \ldots, \alpha_k)$ and verify that $\alpha \in W' \subseteq W$. It is obvious that $\alpha \in W'$. To prove $W' \subseteq W$ take any $\beta \in W'$ and observe that $f(\alpha)$ and $f(\beta)$ agree on the first $n$ values of the output. This implies that $f(\beta) \in V$ and hence $\beta \in W$, as required.

Computable maps are continuous as maps between algebraic $\omega$CPOs

First, let me note that what you defined is usually called "$\omega$CPO" ($\omega$ in the name indicates we only require suprema of chains).

In denotational semantics datatypes correspond to $\omega$CPOs. In fact, they correspond to algebraic $\omega$CPOs (is this in your thesis?), which are $\omega$CPOs for which the compact elements form a base. Here are some definitions.

Definition: Let $D$ be an $\omega$CPO. An element $d \in D$ is compact if, for every chain $x_0 \leq x_1 \leq \cdots$ such that $d \leq \bigsqcup_i x_i$, there exists $j$ such that $d \leq x_j$.

Definition: An $\omega$CPO is algebraic if every $x \in D$ is the supremum of compact elements below it.

The intuition behind compact elements is that they contain "finite information".
A good example is $\mathcal{P}(\mathbb{N})$, the powerset of natural numbers ordered by $\subseteq$, where the compact elements are precisely the finite subsets of $\mathbb{N}$ (exercise!).
Another example: in the $\omega$CPO of continuous functions $\mathbb{N} \to \mathbb{N}_\bot$ the compact elements are those partial functions that are equal to $\bot$ everywhere, except at finitely many arguments.

To say that an $\omega$CPO is algbraic is to say that every element is completely determined by the finite pieces of information that approximate it. It is a fact that in denotational semantics datatypes correspond to algebraic $\omega$CPOs, unless we are doing something very unusual.

We can now explain why every computable map is continuous. Suppose $D$ and $E$ are $\omega$CPOS and $f : D \to E$ computable. Suppose $x \in D$, $e \in E$, $e$ is compact, and $e \leq f(x)$. Intuitively, this say that "finite piece of information $e$ appears in the output $f(x)$". Because $f$ is computable, it must be the case that it computed the information $e$ by accessing only a finite amount of information about $x$, i.e., there is a compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$. This argument should be compared to the Turing machine argument above. We have established:

Lemma: If $f : D \to E$ is computable and $e \leq f(x)$ for some $x \in D$ and a compact $e \in E$, then there is compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$.

We can usethe lemma to show that a computable $f$ is continuous. Suppose $x_0 \leq x_1 \leq \cdots$ is a chain in $D$. Because $f$ is monotone, we already know that $\bigsqcup_i f(x_i) \leq f(\bigsqcup_i x_i)$, but we also need the inequality $f(\bigsqcup_i x_i) \leq \bigsqcup_i f(x_i)$. Because $E$ is algebraic, it suffices to show that, whenever $e \in E$ is compact and $e \leq f(\bigsqcup_i x_i)$ then $e \leq \bigsqcup_i f(x_i)$. So assume $e \leq f(\bigsqcup_i x_i)$. By the lemma there exists a compact $d \in D$ such that $d \leq \bigsqcup_i x_i$ and $e \leq f(d)$. Because $d$ is compact, there exists $j$ such that $d \leq x_j$, hence by monotonicity of $f$ we have $e \leq f(d) \leq f(x_j) \leq \bigsqcup_i f(x_i)$. We are done.


Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

We would show that $HP \le L$.

Let $f:\Sigma^*\rightarrow \Sigma^*$ be a function such that for any $x\in \Sigma^*$:
$$f(x)=\langle M_x\rangle$$
while $M_x$ is a TM that accepts $x$ and rejects every other word.

$f$ is computable, as it only requires writing the encoding of a very simple TM.

Now, for any $x\in \Sigma^*$:

$L(M_x)=\{x\}$
If $x\in HP$, then $\{x\}\subseteq HP$, and so $\langle M_x\rangle \in L$.
Otherwise, $x\notin HP$, and then $\{x\}\not\subseteq HP$, and so $\langle M_x\rangle \notin L$.

Therefore, indeed $HP \le L$.

Thus, it must be that $L\notin coRE$, because otherwise the reduction would imply that $HP\in coRE$, which is false.


Is the set of surjective recursive functions in RE/coRE?

Rice-Shapiro proves that $L$ is not RE nor coRE.

Let $F$ be the set of computable surjective functions. $L$ is the the index set associated to $F$.

Assume by contradiction $L$ is RE. By Rice-Shapiro (compactness), since the identity function belongs to $F$, some finite restriction of the identity must belong to $L$ as well. But a finite-domain function can not be surjective -- contradiction.

Assume by contradiction $\bar L$ is RE. The always undefined function $g$ belongs to $\bar F$, so by Rice-Shapiro (monotonicity), $\bar F$ contains any computable extension of $g$, including the identity function, which is surjective. Contradiction.


How can Turing complete machines exist theoretically if the halting problem is undecidable

The halting problem is the problem of deciding whether a given Turing machine halts on a given input or not.

This problem is undecidable, meaning that no program running on a Turing machine can solve this problem for all possible inputs. Hence, your assumption that such a program exists is wrong.


Split into parts that you can handle. All strings not of the form $a^*b^*$. All strings of the form $a^ib^j$ with $i< j$. Then all strings ....


Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$

Suppose the set is

$$a = \{2,3,6\} \cup \{5,7,35\} \cup \{11,13,143\} \cup \{17,19,323\} \cup \cdots \cup \{p_{2k-1},p_{2k},p_{2k-1}p_{2k}\}.$$

(Do you see the pattern?  It has $3k$ elements, composed of $k$ groups of three.  The $i$th group contains $p_{2i-1}$, the $2i-1$th prime, and $p_{2i}$, the $2i$-th prime, and their product.)

Also, suppose the product you want to hit is $p=p_1p_2 \cdots p_{2k}$.

Then this set has at least $2^k$ subsets that multiply to this value.  In particular, in each group, you can either pick the first two terms, or you can pick the third term.

So you'll need to output at least $2^k$ sets.  This means the running time on an input of size $3k$ can be as large as $2^k$.  Or, in other words, the running time on an input of size $n$ can be as large as $2^{n/3}$.  This is exponential in the length of the input.  Therefore, the worst-case running time is exponential. When we ask about the complexity, we usually implicitly mean the worst-case running time. Therefore, the complexity is exponential. Even though sometimes you might do much less work than that, sometimes you do fully exponential work, so we call the complexity exponential.

Unfortunately, I'm not aware of any simple rule of thumb that suffices for this case.  Sometimes you have to figure out what's going on, and that might require a more deep analysis.


Any code that gets executed takes time $\Omega(1)$. That's the most you can say if you don't know anything more about the code. For example, if all your know is that your loop has the form while i < n ..., then it could be that $i = n$, so the loop immediately terminates.

Here are some concrete cases in which we can calculate the complexity:

i = 1
while i < n:
  i = i + 1

This runs in time $\Theta(n)$.

i = 1
while i < n:
  i = i + i

This runs in time $\Theta(\log n)$.

i = 1
j = 1
while i < n:
  i = i + j
  j = j + 1

This runs in time $\Theta(\sqrt{n})$.

See if you can prove all these claims.


Differences between SISD, SIMD and MIMD architecture (Flynn classification)

Michael J. Flynn is one of the all-time great computer architects.  He was the design manager of the IBM 360/91, and made numerous foundational contributions in the areas of pipelining, and in computer arithmetic.

But the Flynn Taxonomy has not stood the test of time, and is no longer useful.

The SI/MI part of the taxonomy is easy to differentiate on the surface: how many hardware instruction pointers (sometimes called program counters) does the machine have?  If there is one hardware instruction pointer the machine is "SI" (either SISD or SIMD).  If there is more than one hardware instruction pointer the machine is "MI" (either MISD or MIMD).

If you go a bit deeper, it becomes less clear though.  Does a vector machine with one instruction pointer but vector predicate registers count as SI or MI?  Why is a machine with only one fetch unit that can quickly (just a few cycles) switch back and forth between two different instruction pointers MI, but a machine with only one fetch unit that can context switch once ever few-hundred or thousand cycles considered SI?  Is a machine with two hardware instruction pointers, but that only context switches at long-latency cache misses SI or MI?

The SD vs. MD distinction is just a complete mess.  When Flynn made up the classification I believe he was referring to whether the machine had instructions that could operate on multiple independent pieces of data or not.  That does not mean that the operations happen simultaneously.  It could mean that the machine has instructions that operate on vectors of numbers, one at a time (or maybe pipelined), like the CDC STAR-100. The vector instructions in the CDC STAR-100 were pretty complex, giving two vectors start addresses to load, a start address for storing the result vector back to memory, and an arithmetic operation.  The vector lengths were controllable on the CDC STAR-100.  The CDC STAR-100 designers could have leveraged the implicit independence of the operations in the vector instructions to make some of those operations happen truly simultaneously, but they did not.

It may be more appropriate to talk about whether certain instructions in an instruction set architecture are "SIMD" or not.  The ARM NEON instructions are SIMD instructions, but most of the other ARM instructions are not SIMD.

I don't know whether the Z-80's copy instruction was SIMD or not.  I guess I'd call it SIMD because I can't think of any reason not to call it SIMD.


Does $P \neq NP$ imply $NP \neq PSPACE$?

We know that $\mathrm{L}\subseteq\mathrm{NL}\subseteq\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$ and at least one of those inclusions is strict, since $\mathrm{L}\subsetneq\mathrm{PSPACE}$ by the space hierarchy theorem. As far as I'm aware, any nonempty subset of the inclusions being strict would be consistent with our current state of knowledge so, in particular, it is not known that $\mathrm{P}\neq\mathrm{NP}$ implies $\mathrm{NP}\neq\mathrm{PSPACE}$.


The problem is NP-hard, by reduction from independent set.

If you have an undirected graph, treat the distance between two vertices $v,w$ to be $2$ if there is an edge $(v,w) \in E$, or $1$ if not.  There there is an independent set of size $n$ in this graph iff there is a set of $n$ points whose minimum distance is 2.

So, your best bet is probably to use some algorithm for independent set (maybe a SAT solver, or maybe something else), combined with a binary search on the minimum distance.


Sort an array that contain two sorted array in $O(n)$

Let $a$ is the first element of $A$. Let $A$ is composed of array $B = (b_{1},\dotsc,b_{n})$ and array $C = (c_{1},\dotsc,c_{n})$.
Now, we will partition $A$ into arrays: $B'$ and $C'$ in the increasing and decreasing orders respectively. Following is the process:

Let $p$ be a pointer. Initially, $p$ is pointing to $a$. Let $b$ be the element in $A$ next to $a$.
There are two possibilities:

Case 1: $a<b$. Then, one of them must be an element of $B$. In this case, if $a$ is greater than the last element of $B'$, add $a$ to $B'$. Move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $C'$ and $b$ to $B'$. Move the pointer to the element next to $b$ and go to step $1$.
Case 2: $a>b$. Then, one of them must be an element of $C$. In this case, if $a$ is smaller than the last element of $C'$, add $a$ to $C'$. And, move the pointer to $b$ and go to step $1$.
Otherwise, add $a$ to $B'$ and $b$ to $C'$. Move the pointer to the element next to $b$ and go to step $1$.
The above process produces the array $B'$ in increasing order and $C'$ in decreasing order. However, note that these arrays might not be of the same size.
Correctness: Proof by induction.
Base Step: $A$ is composed of $B$ and $C$. $B'$ and $C'$ are empty right now. In Step $2$, Case 1, we add $a$ to $B'$. If it is indeed an element of $B$ then we are good. If not, then $b \equiv b_{1}$ and we can assume that $A$ is composed of a new array $B' = (a,b_{1},\dotsc,b_{n})$ having elements in the increasing order, and array $C' = C \setminus a$ having elements in the decreasing order. Therefore, adding $a$ to $B'$ is correct.
Similarly, we can prove the correctness of Step $2$, Case $2$.
And, the correctness of the further steps follows from the induction step.

After obtaining $B'$ and $C'$, you can merge them using merge sort like step in $O(n)$ time.


How does computer memory store the file name?

You are right, the computer saves the file name somewhere. But not, it isn't kept in a "stack" or in "memory", files are kept on external memory (disk, flashdrive, perhaps even somewhere else "on the cloud"). This memory in turn is organized to give an efficient map from file names (stored in filesystem proper data structures) to file contents (arranged so it is e.g. possible to extend the file, erase it's contents and reclaim the space, ...). When you ask your operating system for the file size, it answers with the user-visible space (as that is what you presumably are interested in). The space used up in management of the above (file name, references to the pieces used by this file, map of free space on the device, directory structure for managing names, ...) is usually not your concern. You can ask for it if you look at "how full is the device", just that the space used for management usually can't really be associated with a particular file, it is used by many files together.
Get some book on operating systems, and look up "file systems". Or check simple examples like the (MS-DOS) FAT filesystem or the Unix file system design (just concentrate on the Version 7 one, with it's simple layout). File systems in current use are very complex beasts, trying to squeeze out performance of humongous, glacially slow, rotating disks or levelling wear on fast SSDs.


Can the compiler convert recursive algorithm into a dynamic programming

There is an easy way to implement dynamic programming, using a hash table.
The idea is that the recursive procedure stores a huge giant table, containing all values computed so far. Whenever the recursive procedure is called, it first checks whether the value is already in the table, and if so, the value is immediately returned. Otherwise, the body of the procedure is executed, and the result is stored in the table.

This kind of memoization can be enabled, for a specific procedure, using the decorator @memoize in Python, and perhaps similar metaprogramming mechanisms are available in other languages.

Since the table takes up space, it is not clear that this kind of memoization is advantageous in every situation. For example, it might be that the function is easy to compute, and using a hash table would make it significantly slower (since memory access is small). Perhaps a certain code is trying to keep a certain table in cache, and using memoization would interfere with this effort. Perhaps using a table would interfere with security in some way, since it will reveal whether a function is called with the same value as before or not. There are probably many other reasons for the compiler not to perform such an optimization automatically.


What is the name of a rooted tree whose nodes may have edges to their descendants?

I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times in a paper.

But... as Pål GD alludes to in a comment, every DAG on $n$ vertices is a subgraph of the transitive closure of the $n$-vertex directed path. So this answer is a bit of a fail, really.


Using pumping lemma to prove a language is not context free

The pumping lemma claims that if the language is context-free, then there exists a configuration such that you can pump the string. Therefore, to prove that the language isn't context-free, you must show that pumping fails for every possible arrangement.


Can polymorphism be simulated by lazy type operators?

It's not entirely clear to me how your idea is supposed to work, but everything you're doing can just simply be done with a bit of more high-powered type theory. That is, if we allow quantification over types then we can talk about polymorphism. Let's go from easy examples to the ones you're talking about.

A function such as
$$f \, x = (x,x)$$
is polymorphic in the type of $x$: if $x$ has type $A$ then $f$ has type $A \to A \times A$. We can express this sort of dependency by intrducing an extra argument so that $f$ has type $\prod_{A : \mathsf{Type}} A \to A \times A$ and is defined by
$$f \, A \, x = (x, x).$$

Your example is like this, except a bit more complicated. To keep examples simple, let me instead used a simplified class (the whole Num is a bit large)

class Cow a where
  one :: a
  plus :: a -> a -> a

and consider a functio dependent on Cow:

plusOne :: Cow a => a -> a
plusOne x = plus x one

We can express plusOne as before, except that now it takes three extra parameters: a type $A$, an element of $A$, and a function $A \to A \to A$. So its type would be
$$
\prod_{A : \mathsf{Type}} A \to (A \to A \to A) \to A \to A
$$
and it would be defined by
$$\mathtt{plusOne} \; A \; \mathtt{one} \; \mathtt{plus} \; x =
  \mathtt{plus} \; x \; \mathtt{one}.$$
This is a general trick: polymorphism can always be replaced by passing around extra arguments, but the price you pay is that you will have dependent types and there might be many extra arguments.


Basically, the complexity of an algorithm gives the relation of the change in the running time with respect to the change in the input size. You can think it as,

$log_2(1M)$ -> 20 sec

$log_2(2M)$ -> ? sec

$log_2(2M) = log_2(2 *1M) = log_2(2) + log_2(1M) = 1 + 20 = 21 sec$


Is every regular language Turing-decidable, and how can we prove this?

Every regular language is Turing-decidable and therefore Turing acceptable / recognisable (but note that Turing acceptable does not imply Turing decidable).

Suppose you are given a DFA D such that L = L(D). One can construct a Turing Machine T that simulates D. T's states will be similar to D's. On reaching the end of the input, if T is in a state that corresponds to a final state of D, T halts and accepts; otherwise it halts and rejects.


Finding an algorithm to return the $\log n$ largest element in an array

A possibility (don't think it's the simplest way, though) is:

Transform the array into a max-heap;
find (without extracting) the $\log n$ largests elements in the heap.

The first step can be done in $O(n)$. For the second step, let's give a little bit details:

The largest element is found among one element (it's the root);
the second largest must be found among two elements (the two children of the root);
in general, the $k$-th largest element must be found among $k$ elements, because each time you select an element to be the largest, you remove it from the candidates and add its two children.

That means that after having found the $k$ largest elements, finding the $k+1$-th is done by searching the maximum value among $k+1$, so it is done in $O(k)$. Since we want to find at most $\log n$ elements, the total search takes $O((\log n)^2)$ time, and with the property you proved, it is $O(n)$.
That means that the total complexity of the algorithm is $O(n)$ which is obviously optimal since you need to browse all elements of the array.
Edit: Actually, I realize (that confirms what I initially said) that there is a simpler way to do it:
Use a quickselect algorithm to find the $\log n$-th largest element (no plural here) of the array (this is done in $O(n)$). By doing so in place, the $\log n$ largest elements will be placed in consecutive positions at the end of the array. You can then sort those $\log n$ elements in time complexity $O(\log n \log \log n) \subset O((\log n)^2) \subset O(n)$.


I assume the formula is

$$(x \ne 0) \land (y|2 = z) \land (1<3).$$

We can handle each clause of the conjunction separately.  If $x=(b_3,b_4)$, then $x \ne 0$ translates to

$$b_3 \lor b_4.$$

If $y=(b_5,b_6)$ and $z=(b_7,b_8)$, then $y|2$ translates to $(b_5|1,b_6)$, which simplifies to $(1,b_6)$ (if you are doing simplification).  Now $(1,b_6) = (b_7,b_8)$ translates to

$$(b_7=1) \land (b_6 = b_8),$$

which in CNF form is

$$b_7 \land (b_6 \lor \neg b_8) \land (\neg b_6 \lor b_8).$$

Finally, $1<3$ translates to True, if you are doing simplification.  So, the final result is the conjunction of those:

$$(b_3 \lor b_4) \land (b_7) \land (b_6 \lor \neg b_8) \land (\neg b_6 \lor b_8).$$


Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

If all you have is a black-box function to test containment in your shape $S$, then the answer is no in general. For example, take $n=2$, let your rectangle $R$ have corners $(\pm1,\pm1)$ and let $S$ be a disk. Note that $S$ can have exactly 1 point of intersection with our rectangle and this can be any point on the boundary of the rectangle. So, since we work over $\mathbb{R}^2$, we have to test an infinite number of points and hence it is impossible. (obviously, if we have a discretized space, the rectangle has a finite number of points and we can simple test all of those.)

So, if you can have an intersection with only 1 point at an infinite number of places, it is impossible. This can happen for a large class of shapes. The first counter-example I can think of is when $S$ is an axis-parallel rectangle with a minimum side-length $w>0$. $S$ can intersect at one point only in the 4 corners. If $S$ does intersect $R$, but not intersect in a corner $S$ must intersect a segment of length $w$ on the boundary of $R$, so we can test $\approx \frac{4}{w}$ values on the boundary of $R$ to find the intersection.

Note that even in this case, you need $O(\frac{1}{w})$ tests to determine intersections. I think this means that unless you make some strong assumptions about $S$ or relax your condition of intersection, this problem is not solvable.


Is deciding whether or not a graph is bipartite in $L$?

Your construction shows that checking whether an undirected graph is bipartite is logspace reducible to PATH (deciding whether there exists a path between two vertices in an undirected graph).

Recall that if $A$ is logspace reducible to $B$ and $B\in L$, then $A\in L$. To decide $A$ in logspace, you don't actually compute the reduction (as its output can be of polynomial length), but compute a single bit of the reduction whenever it is requested. More concretely, suppose $f$ is a logspace reduction from $A$ to $B$. To decide $A$, given input $x$, execute the logspace machine for $B$ and keep a counter $i$ for the location on its input tape. Whenever $B$ wants to read a symbol from its input, compute the $i$'th bit of $f(x)$, which requires only logarithmic space (as $f$ is a logspace reduction from $A$ to $B$).

This show that you don't actually need to construct $G'$ entirely. You only need to compute a given bit of its adjacency matrix in logarithmic space.


Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

Five rules for RB-Trees:

  Every node is black or red,
  Root is black,
  Every leaf is black,
  If a node is red then both its sons are black,
  All paths from a single node to any leaf must contain an equal amount of black nodes.

A common implementation has a NIL leaf set as a parent of root and son (left and right at the same time) of all leaves - in this case the NIL is black, and so it's parents can be black or red (as NIL is the only leaf.) This is the reason for a common misconception that leaves can be any color.

I am almost sure that any RB-Tree containing at least 2 elements (except NIL) will have at least one red node. This is due to an observation of the Insert algorithm. The inserted node is always coloured red at first, but any later modifiaction (if the colouring needs to be repaired) either does not change the colour of the newly added node (so it remains red) or makes at least one other node red.


You probably misunderstood the question. For starters, the pumping lemma can't be used to prove that a language is regular, it can only be used to prove that a language isn't regular. The Wikipedia page for the pumping lemma gives a counterexample.

Secondly, as already pointed out by @DavidRicherby, this particular language is not regular, and as it turns out, you can use the Pumping Lemma to prove this statement.

Roughly speaking, the proof goes as follows:

Assume for the sake of contradiction that the language is regular, and thus, the Pumping Lemma holds. The "y" can take one of three forms:

y contains all "a"s
y contains all "b"s
y is of the form $a^ib^j$ for some $i,j > 0$.

Now, can you see how to derive the contradiction?


Find a collection of sets where each number from a given list is contained in a different set

You are looking for a perfect matching. Consider the bipartite graph in which the left side consists of $N$ vertices corresponding to the numbers in $S$, and the right side contains a vertex for each set. Connect $x$ on the left to $y$ on the right if $x \in y$. Your problem is solvable if there is a matching that matches all of the left side. This is the classical problem of unweighted maximum matching in bipartite graphs, which has many efficient algorithms.


How to find minimum number of k-input LUTs needed to express a n variable boolean function?

The following decision version of your problem is NP-complete:

  Given a formula $f$, an integer $k$, and an integer $s$ (encoded in unary), determine whether $f$ can be represented using at most $s$ many $k$-input LUT's.

Indeed, you can easily solve SAT by asking whether the instance of SAT can be represented using at most one 0-input LUT. If you disallow $k=0$, you need to work a bit harder: a formula $\phi$ is satisfiable iff $\phi \oplus x$ (where $x$ is a fresh variable) can be represented using at most one 1-input LUT.


Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

This would work, with a minor modification.  In other words, the resulting algorithm would be correct: it would correctly compute distances.

However, it doesn't help much.  It doesn't change the asymptotic running time of the algorithm.  In many graphs, after about $O(\lg n)$ iterations, essentially every vertex is reachable from the starting point.  Therefore, you might save a little bit on the first $O(\lg n)$ iterations, but after that, you still have to relax all edges.  Thus, this makes only a minor improvement -- far too small to show up in the asymptotic running time.  And, in practice, on most graphs, the improvement will probably be small -- perhaps so small as to be outweighed by the extra bookkeeping required.

Finally, this makes the algorithm more complicated.  From a pedagogical perspective, when the purpose is to teach algorithms, unnecessary complications are best avoided, as they just make it harder to understand an already-challenging subject.

The minor modification you need to make is: in the $k$th iteration, relax all edges $(u,v)$ where $u$ is at most $k$ edges from the source [rather than where $u$ is exactly $k$ edges away from the source].  This is important, because the shortest path from $s$ to $u$ (the one where the sum of the distances on the edges in the path) need not be the same as the path from $s$ to $u$ with the fewest edges.


Boolean algebra truths with more than one digit

This notation is usually used for bitwise operations. You compute the operation bit by bit – the $i$th bit of the answer is (in this case) the AND of the $i$th bits of the inputs.

From a more theoretical side of things, this bitwise rule does turn $k$-bit numbers into a Boolean algebra. Boolean algebras are sets together with several operations that satisfy certain axioms (there are several equivalent versions which are easy to find online). Stone's representation theorem states that every Boolean algebra is a field of sets, which in the finite case just means that it consists of $k$-bit numbers for some $k$.

Boolean algebras have found deep applications in set theory, though the relevant Boolean algebras are always infinite. In this application at least, it is certainly possible to think of the values of the Boolean algebra as truth values. One can then obtain a more conventional truth value by using an ultrafilter.


Yes, your understanding is correct.  The theorem is indeed talking about the entropy of the source, in terms of the amount of information in each symbol.  Since entropy is measured in bits, the units are bits per symbol.


Why does appending permutations of servers at the end of hash table avoid bottlenecks?

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server.  Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order.  Suppose you have six tract servers and your tract locator table looks like this

123456

and server 3 is slower than the others.  Since sequential readers walk the table in the same order the slowness of server 3 will cause a convoy of sequential clients to form waiting for server 3.  Once server 3 serves them, they all move on server 4 which may also become overloaded.  Then 5, then 6, and before long the convoy is big enough to hammer each server in turn instead of spreading the load evenly across all of them.

If your tract locator table looks like this

643512623154125364213546

i.e. four permutations of 123456, events transpire differently if there is a slow server.  If server 3 is slow, satisfied sequential readers will move from server 3 to servers 5, 1 or 6 depending on where they are in the table.  This instead of all sequential I/O clients turning their attention to the same server after visiting server 3.  The extra permutations have the effect of breaking up convoys if they form and lessening the likelihood of convoys forming at all.


The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows:
$$
\binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k
$$
Where the equality $\sum_{i=0}^{k} \binom{k}{i} = 2^k$ follows from the fact that the summation on the left is counting the number of possible subsets of a set with $k$ elements, grouped by cardinality: the $i$-th term of the sum (for $i=0, \dots, k$) is the number of subsets with exactly $i$ elements.
Also, using Stirling's approximation and assuming that $k$ is even (this is just for convenience, if it's not you can consider $k+1$ instead to get the same asymptotic bound):
$$
\binom{k}{p-1}  \le \binom{k}{k/2} = O\left( \frac{ (k/e)^k \sqrt{k} }{ k (k/2e)^k } \right) =
O\left(\frac{2^k}{\sqrt{k}} \right).
$$


Minimum Number of People Such That No Two People Know the Same Two People

The comment of Carlos actually gives an upper bound. There is a much better (and almost tight) upper bound for $k+1$ being a prime number: $n=k(k+1)$. The construction is a classical result in extremal graph theory, namely $C_4$-free $k$-regular graphs, which can be found here.

The vertices are labeled with $(a,b)$ where $1\leq a\leq k, 0\leq b\leq k$. Two vertices $(a,b)$ and $(c,d)$ are linked if and only if $ac\equiv b+d\mod (k+1)$.
Notice that for any given pair $(a,b)$ the number of solutions $(c,d)$ is exactly $k$, so the graph is $k$-regular. To see the graph is $C_4$-free, consider the following congruence equations
$$\left\{ \begin{array}{ll}ax\equiv b+y\mod (k+1)\\ cx\equiv d+y\mod (k+1)\end{array} \right.$$
Since these imply $(a-c)x\equiv b-d \mod (k+1)$, and $k+1$ is prime, there is at most one solution whenever $(a,b)\neq (c,d)$, so the graph contains no $4$-cycle.

There are many other constructions among this context, for instance, when $k-1$ is a prime power there is a construction of size $n=2(k^2-k+1)$ with bipartite incidence graph (See, e.g., here).


Recurrence Substitution Method with multiple givens

Let $S(n) = T(n) + 1.5$. Then
$$
S(n) = T(n) + 1.5 = T(n-1) + 2T(n-2) + 4.5 = S(n-1) + 2S(n-2).
$$
The recurrence $S(n) = S(n-1) + 2S(n-2)$ is homogeneous with constant coefficients, so we know how to solve it. We first solve the equation $\lambda^2 = \lambda + 2$, finding that the solutions are $2,-1$. This implies that there exist constants $A,B$ such that
$$
S(n) = A 2^n + B (-1)^n.
$$
Since $S(0) = 4.5$ and $S(1) = 6.5$, we see that $A + B = 4.5$ and $2A - B = 6.5$, from which we find that $A = 11/3$ and $B = 5/6$. Therefore
$$
T(n) = \frac{11}{3} 2^n + \frac{5}{6} (-1)^n - \frac{3}{2}.
$$


In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path)

Kinda.  While it's true that the algorithm should output the optimal path, that's probably not what your notes were referring to.  Rather, it's likely that they were making a claim about the algorithm itself being optimal in terms of performance.
A blog post, "Artificial Intelligence - Uniform Cost Search (UCS)", provides a claim like this:

Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost.

The logic behind this claim seems simple enough: you don't want to search down paths that can't be optimal, since that'd be wasteful, but you don't have any way of knowing which paths might be optimal in advance.  So, by going down each equally, you don't assume any effective bias.
I'm not 100% if this is true in all cases in which this claim's made, but it seems like a useful tidbit to be aware of.

but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops?

There can't be negative costs.  If there are negative nodes, you'd have to modify the algorithm by removing its termination condition, effectively reducing it to a brute force search.
For example, consider using UCS and finding an apparently optimal path without having searched the entire space.  Then, it turns out that there's a node that you didn't search that has a cost of $-{\infty}$.  Presumably an optimal path should've gone through that node, but the search couldn't have found it since it terminated too soon.
Disclaimer about method names
Basic, widely known methods like this often have some variation in exactly how different sources define them or what name the method is given.  For example, below I linked the relevant Wikipedia article, which calls it "Dijkstra's algorithm".  The Wikipedia article discusses several different implementations.
Claims about algorithms with fuzzy definitions and frequently confused names should be taken with a grain of salt as there's plenty of room for miscommunication.
Further reading
Wikipedia's article on Dijkstra's algorithm would likely be helpful:

In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as uniform-cost search and formulated as an instance of the more general idea of best-first search.


I am not aware of whether this problem has a name or not, but it can be shown that it is NP-complete by reduction from the maximum independent subset problem:

Given an undirected graph of $N$ vertices and $M$ edges, we can map the nodes to a set of $M$-tuples $\{x_1,...,x_n\}$ such that any two tuples are "compatible" if and only if the corresponding nodes do not share an edge:

Given $i$-th undirected edge $\{a,b\}$ with $ a\leq b$ we set $x_{a}[i]$ to 1 and $x_{b}[i]$ to 2.
Any element that remains unset by the previous rule is set to #.

Now:

For each pair of nodes that share an edge, the corresponding tuples will not be compatible because they have different values in the position corresponding to the edge.
For each pair of nodes that do not share an edge, for each position in the tuples at least one of them has # assigned in that position. Hence,they will be compatible.

By definition:

An independent subset of the graph is such that it does not contain two nodes that share an edge.
A compatible subset of tuples is such that it does not contain two tuples that are not compatible.

Hence a subset of nodes is independent if and only if the corresponding subset of tuples is compatible. Then, the size of the maximum independent set in the original graph is equal to the size of the maximum set of compatible tuples.


How to prove that a predicate is prefix closed

Your predicate states that $X_p \leq X_{p+1} \leq \cdots \leq X_{q-1}$. If you take any subinterval of $[p,q)$, say $[p',q')$, you will still have $X_{p'} \leq X_{p'+1} \leq \cdots \leq X_{q'}$. In other words, a subinterval of a non-decreasing sequence is also non-decreasing.

Now that you know why what you want to prove is true, it remains to prove it formally. Always remember: the first step is to understand why something is true, and only then should you try to prove it. In fact, most of the time in mathematics and computer science we skip the second step, that of proving things formally, since it obscures the situation.


Defining a new (informal) operator in CTL

You seem to be stuck, so here is the answer:

You want $a$ to hold for at least as long as $b$ does. The alphabet consists of $2^{\{a,b\}}=\{\emptyset, \{a\},\{b\},\{a,b\}\}$.

Rephrasing the condition, it means that $\{b\}$ cannot appear before either $\{a\}$ or $\emptyset$ have appeared. Indeed, this is the only violation of the condition.

So once $\{a\}$ or $\emptyset$ hold, you're in the clear. You just need to make sure that until then (sounds familiar?), $\{a,b\}$ holds.

Thus, you have
$$a\ Wh\ b\equiv (a\wedge b)U(\neg b)$$


Let's suppose you have a spatial data structure that can be built over a set $S$ of points on the plane and expose the functions.

Build(S): Build and return the data structure storing all points in S
ds.Delete(q): Deletes point q from the set S
ds.Search(p): Return the closest point in S to point p

Now let's solve the problem backwards, instead of finding if a point is contained by some circle, lets find points for each circle the points it contains.

C: Set of circles
P: Set of points
ds := Build(P) # Build the data structure using points to be queried

for each circle c in C:
   do
      p = ds.Search(c.center)
      if p is inside circle c:
          ds.Delete(p)
   while (ds is not empty and one point was deleted)

All the deleted points from the data structure are the points that belongs to at least one circle, remaining points are not contained in any circle, otherwise they were being found when processing such circle.

Let $N:=|C|$ and $Q:=|P|$

The overall complexity of this algorithm is $$O(Build(Q) + (N + Q) \cdot Search(Q) + Q \cdot Delete(Q))$$

Here $Build(Q)$ is the complexity of building the set of $Q$ points, $Search(Q)$ is the complexity of searching for a point in a set of at most $Q$ points and $Delete(Q)$ is the complexity of deleting a point in a set of at most $Q$ points.

Notice that this cost is amortized, since after a point is recognized to be inside a circle it is deleted from the set.

One data structure that provides good balance for this operations is kd-tree, but I encourage you to find other spatial data structures that provides better complexity for your case.


Is there a bound on possible Dead state in a minimized DFA

If you allow the DFA to be trimmed, then you can delete ALL dead states. If you want the DFA to be complete, then the minimized DFA will indeed have at most one dead state.
The reason is that minimizing leads you to merge nondistinguishable states, that is equivalent states in the Myhill-Nerode equivalence relation (here the definition is given for words and languages, but it can be extended to automata).
Two states $q_1, q_2$ are distinguishable if there exists a word $u$ such that $\delta^*(q_1, u)$ is final and $\delta^*(q_2, u)$ is not (or the converse). If $q_1, q_2$ are two dead states, then $\delta^*(q_1, u)$ can never be final (and same for $q_2$), so $q_1, q_2$ will never be distinguishable.


A set of cycles $C$ of a graph $G=(V,E)$ is edge-disjoint if the cycles $c_i$, $c_j \in C$ have no edges in common.


Is this graph problem NP-hard / NP-complete?

Turns out this is indeed an NP-complete/NP-hard problem according to wikipedia and Eades et al.


Question on the "Tutorial implementation of dependently typed lambda calculus"

$\mathsf{id}$ and $\mathsf{const}$ are not variables of the calculus, but syntactic sugar for $\lambda x \rightarrow x$ and $\lambda x \rightarrow \lambda y \rightarrow x$ respectively. This is stated at the end of §2.2 and subtly conveyed by the use of a sans-serif font rather than italics (this is a typographic convention of this particular document, not a common convention).
So for example the type judgement
$$
\alpha :: \ast, y :: \alpha \vdash (\mathsf{id} :: \alpha \rightarrow \alpha) \: y :: \rightarrow \alpha
$$
is also the type judgement
$$
\alpha :: \ast, y :: \alpha \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha) \: y :: \rightarrow \alpha
.
$$
It's a different notation for the same mathematical object.


Does interpreter for language L1 have to be written in lower level language L0?

I think the implication of your Tanenbaum quote is that there is no compiler for L1.  In which case yes, the interpreter does have to be written in another language (how else would you run the interpreter?).[1]  It doesn't have to be lower-level; you could write an interpreter for Haskell in ML, say, or vice-versa.  You usually want to use a lower-level language, though, since interpretation is going to impose an order of magnitude speed (and size) overhead you need to win back in the speed of your interpreter for the language to be competitive.

In general, no.  You can write an interpreter for any language L1 in L1, provided you also write a compiler for L1.  Lisps are traditionally bootstrapped by: write an interpreter (a) for Lisp in some other language, then write a compiler (b) for Lisp in Lisp, executed by (a), then write an interpreter (c) for Lisp in Lisp, compiled by (b).  Now you have a Lisp interpreter written in Lisp.

Having said that, a program that takes a program in L1 and produces a program in L0 is a compiler; it compiles to L0.  All compilers compile to some other language[2] which in turn may be compiled some number of additional times, and then is interpreted either by hardware or by another program.

[1] Again, there are techniques for bootstrapping interpreters interpreted by themselves, but they all involve hand-written code in another language (or in the same language but compiled) and are a bit beyond this level.

[2] This is an over-simplification; optimization passes can be written as 'compilers' that compile to their source language and there are other uses for compilers that compile to the same language as the input.  But for your purposes, think of a compiler as compiling to a different language than the source.


Recovering a point embedding from a graph with edges weighted by point distance

One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape.

Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, but this costs energy).  We now want to solve for a set of positions that minimize the total energy.  Suppose each vertex $v$ is placed at point $x_v \in \mathbb{R}^3$.  Then the total energy of this arrangement will be

$$E(x) = \sum_{(v,w) \in E} (\text{distance}(x_v,x_w) - d_{v,w})^2.$$

Here the $d_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x_v$'s (they are the coordinates of the points).

We can solve for an arrangement $x$ that minimizes this total energy.  This arrangement then provides a reasonable candidate for the positions of the points.  This is an optimization problem, and there are standard techniques for solving this kind of optimization problem.  See, e.g., the article Network Solutions by Erica Klarreich.

I don't think there any guarantee this will provide the correct desired solution.  It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for.  However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.

Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances.  Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.

Finally, there's a lot of work on embedding graphs into $\ell_2$ space, while minimizing the distortion of the embedding.  That's very related; you are basically asking for a zero-distortion embedding into $\ell_2$.  Thus, the techniques developed in that context might be useful for your problem, too.  Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem.  However, it's possible that their techniques might be effective in your situation as well.  It's worth a try.


Is the complexity of problems in NP exponential at most?

Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-time algorithms or none of them does.

Your first statement "Since NP-complete problems are in NP, their running time is at most exponential" is NOT a definition of a $\mathsf{NP}$-Complete problem. It is just a property that NP-Complete problems have.

This is equivalent to saying that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. In fact it is conjectured that the containment is proper, i.e., $\mathsf{NP} \subset \mathsf{EXPTIME}$ . This would imply that there are (decision) problems that can be solved in exponential time but are not in $\mathsf{NP}$. We also know that $\mathsf{P} \subset \mathsf{EXPTIME}$, showing that we must have $\mathsf{NP} \subset \mathsf{EXPTIME}$ if $\mathsf{P}=\mathsf{NP}$.


Most cost effective way to traverse a set path

Let us number the destinations from $1$ to $N$ and define an array $c[N]$ where $c[i]$ is the minimum cost to travel to destination $1 \leq i \leq N$. We wish to calculate $c[N]$.

It is clear that $c[1] = D_1 \times r$, because if we find ourselves at destination $1$ we can only have gotten there by travelling one destination at a time, instead of travelling five destinations at a time.

The minimum cost of travelling to destination $2$ must be $c[2] = D_2 \times r + c[1]$ for identical reasons ($2 < 5$) as before. We add the minimum cost of reaching destination $1$ to the minimum cost of reaching destination $2$ because we must have travelled from destination $1$ to $2$.

Now we see that for destinations $i \geq 5$, that we could have reached them by travelling through five destinations at a time instead of the previous one destination at a time. This means
$$c[i] = \min(B + c[i - 5], D_{i} \times r + c[i - 1])$$

Where $c[0] = 0$. From this pattern, we can calculate $c[N]$ in $O(N)$ time complexity.


Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?

Your construction outputs the language
$$ \{ w \in L_1 : \exists z \in L_2 \text{ s.t. } |z|=|w| \}. $$
In words, it outputs those words in $L_1$ whose length matches the length of some word in $L_2$. In general, this could be much smaller than $L_1$.

In particular, if $L_2$ is a finite language, then the result of merging $L_1$ and $L_2$ is finite, and so regular, for every language $L_1$.


transformation between two formulations of the mincost flow problem

I would say that 3. is a special case of 2. instead but it is a point of view.

On 3., you can create a new node "source" which has edges to every supply nodes (b(v) > 0). These edges have cost 0 and capacity b(v).

Then you create a new node "sink" which has edges from every demand node. These edges have cost 0 and capacity -b(v).

All this replaces the b(v) values which are not needed anymore.


Formal proof of language accepted by a specific CFG

Let $L = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}$. The proof consists of two steps:

$L \subseteq L(G)$.
$L(G) \subseteq L$.

The first step proceeds by direct construction: we show how to produce each word in $L$ using the grammar. In order to produce the word $a^i (ab)^j c^j$, we first apply $i$ times the rule $S \to aS$, then once the rule $S \to B$, then $j$ times the rule $B \to abBc$, then once the rule $B \to \epsilon$. Formally, we could prove that this works by induction.
For the second step, we first prove by induction that all words generated by $B$ are of the form $(ab)^jc^j$. We show that by induction on the length of a production starting at $B$. If the first step is $B \Rightarrow \epsilon$ then we generate $\epsilon$. Otherwise, the first step is $B \Rightarrow abBc$. By induction, the $B$ on the right produces a word of the form $(ab)^jc^j$, and overall the produced word is $(ab)^{j+1}c^{j+1}$, which is of the same form.
We can now prove the required claim by induction on the length of a production starting at $S$. If the first step is $S \Rightarrow B$, then the preceding paragraph shows that the generated word is of the form $(ab)^jc^j$. Otherwise, the first step is $S \Rightarrow aS$. By induction, the $S$ on the right generates a word of the form $a^i (ab)^j c^j$, and overall the produced word is $a^{i+1} (ab)^j c^j$, which is of the required form.


Depending on how long the lines are and what the likelihood of intersections is, you could also use a spatial join. I.e. you treat all all lines as rectangles, put them in a spatial index and search for each line with which other lines it overlaps. You can use a standard R-Tree or Quadtree, but I would actually suggest a PH-Tree here, for example this one, because they are very fast for window queries with small result sets (for example if you expect usually only 1 intersection). For all results, you would have to manually calculate whether the lines actually intersect or not, because overlapping rectangles is an indicator for overlap, but obviously not a guarantee.

Also 'Sweep Line' is more of a general approach of tackling a problem, a bit like 'divide and conquer'. It is not an algorithm in itself, you would have to be more specific how you would use it to solve your intersection problem.


What do assemblers translate macros into during assembling?

From a semantic point of view, macros are expanded into assembly code. How macros are actually implemented probably depends on the assembler. One option would be to expand them in a preprocessing step, like in C compilers; another would be to expand them on the go. The end result is the same — it is as if the macros were expanded textually in a preprocessing step.

There are other mechanisms used in assemblers that you might consider macros but are different. For example, the x86 MASM uses db/dw/dd to define data. These are stored in the resulting executable, the exact way depending on the executable format, particularly how the binary is loaded into memory. Usually there is a specific data segment which is loaded into a specific address, the relevant pages being marked non-executable if the processor supports this.


Here is how I would approach it. Yes, dynamic programming is a way to solve this problem efficiently.

A few notations to note before hand :

prefix[k] = sum of all terms from 0 to k ( k included ).
best[k] = max possible XV till term k ( k included )

Algorithm :

 1. prefix[0] = A[i];
 2. best[0] = cubed sum A[i]

 for array A:
    // max ( m,n ) --> max of m and n.
    3. best[i] = max ( cubed sum (prefix[i-1] + A[i]), best[i-1] * A[i]);

 return best[n]. n --> size of array.

In other words, you choose the max value of either including the current strength into sum or by competing.


Find all shortest paths in a graph where path has even number of edges and greater than 6

Hint: Use an appropriate layered graph. If you find the problem difficult, try solving it under only one of the conditions (only an even number of edges, or only at least 6 edges).


Algorithms that are using John's ellipsoid

Rimon and Boyd use Lowner–John ellipsoids in their "...method for estimating the distance between a robot and its surrounding environment".

From the abstract:

  First, approximate the detailed geometry of the robot and its
  environment by minimum-volume enclosing ellipsoids. ... Then
  compute a conservative distance estimate using ... [a] formula for the
  distance of a point from an n-dimensional ellipse.

E. Rimon and S Boyd. Obstacle Collision Detection Using Best Ellipsoid Fit. Journal of Intelligent and Robotic Systems, 1997 - Springer