Does two languages being in P imply reduction to each other?

No, in general
As you've already noticed, if $L_2$ is either the full language or the empty language, there can be no reduction from $L_1$ to $L_2$ - the argument is simple enough.
Recall the definition. $L_1$ reduces to $L_2$ iff there exists a function $f: \Sigma^* \rightarrow \Sigma^*$ such that $\forall w \in L_1, f(w) \in L_2$, and $\forall w \notin L_1, f(w) \notin L_2$, and $f$ is computable in polynomial time.
Suppose $L_1 \neq \emptyset$ and $L_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L_1 \implies f(w) \in L_2$. This argument immediately gives us a contradiction. We know that $w \in L_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.
The argument for $L_1\neq\Sigma^{*}$ and $L_2 = \Sigma^{*}$ is similar. For any function $f: \Sigma^* \rightarrow \Sigma^*$, $w \in L_1$ can be false, but $f(w) \in \Sigma^{*}$ is always true.
There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L_1$ and $L_2$ to $\emptyset$, $\Sigma^{*}$ and some non-empty non-"full" language.
This said, with a further assumption, there's a small trick we can apply to make this argument hold:
Yes, if we have that neither $L_1$ nor $L_2$ are empty or "full"
Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time.
Let $w_\top \in L_2$ and $w_\bot \notin L_2$. These words are constant, so are of constant length.
We will define $f$ as follows. If $w \in L_1$, then $f(w)=w_\top$. If $w \notin L_1$, then $f(w)=w_\bot$. Clearly, $f$ represents a reduction from $L_1$ to $L_2$ according to the above definition. Since $L_1$ can be decided in polynomial time, we can compute $f$ in polynomial time.
So $f$ is a poly-time reduction from $L_1$ to $L_2$. This argument can work the other way to provide a reduction from $L_2$ to $L_1$, so the languages reduce to each other.
If exactly one of $L_1$ or $L_2$ is empty or "full", we can reduce from one to the other. Which way? Why?


Is there a name for graphs which contain oriented and non-oriented edges?


In lieu of neural networks and deep learning, what are some approaches to computer vision?

I think you could use some type of probabilistic model to solve this issue. I might be completely wrong, though, as I do not know a lot about probabilistic models.

Some time ago, I made use of Markov chains to generate levels for a game called Mega Man, and I remember that the results were promising, so I looked up "Markov Chains and face recognition" and found the following paper:

http://www.anefian.com/research/nefian98_face.pdf

It deals with the specific problem of face recognition.

Markov Chains also work with Optical Character Recognition, and though I know that comparing a letter to a face is a bit of a stretch, the following paper might give you some insight.

http://www.aclweb.org/anthology/N03-1018

I hope that helps!


Standard or Top Text on Applied Graph Theory

I would take a look at the free book by Bondy and Murty: Graph Theory with Applications. This book is less-algorithmic and more graph-theoretical than other resources recommended here. There is also a newer version of the book, which is not available for free on the net, but is extremely well-written and with updated notation. In comparison to other free books on graph theory (as for example Diestel), Bondy/Murty uses a less formal approach to prove and explain the theory.

The reason I have used it, is because it is the primary text-book in the course on Graph Theory at The Technical University of Denmark, lectured by Carsten Thomassen, in which I have been assistant teacher for 2 years.


How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?

We guess that $T(n) = \Theta(n^{\alpha})$, where $\alpha > 0$ is a constant.

To find $c$, we use the substitution method.

Assume that $T(n) \le cn^{\alpha}$. (The other direction $T(n) \ge cn^{\alpha}$ is similar.)

Then, we have $$T(n) \le c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha}.$$

Letting $$c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha} = cn^{\alpha},$$ we obtain that $$(1/2)^{\alpha} + (1/4)^{\alpha} + (1/8)^{\alpha} = 1.$$

Solving this equation (using Mathematica) yields
$$\alpha = 0.879146.$$


It doesn't, if $f \in O(g)$, it "just" tells us that $g$ is an asypmtotic upper bound for $f$.

This tool (asymptotic notation) can then be used to express relationships between the growth rates of functions in any context you want. One of these contexts happens to be the worst case running time of algorithms, so it's not the big-oh that makes it worst case, it's what it's being applied to.

You can quite happily use big-oh to upper bound best-case running time, average-case, in amortised analysis, space usage, or in things that have nothing to do with algorithmic complexity.


If A is polynomial time reducible to B and B is in NP, then A is in NP

I think both hold too.

Co-NP version:some Problem A reduce to B,

if B is co-NP,$\overline{B}$ is in NP,and no-instance of B has some verify way and certificate bit. and A's no-instance can use it too.

So this A is complement of NP problem $\overline{A}$. this means complexity class of A is co-NP.


How to compare SURF points in two images

You compare the descriptors. The simplest approach is for every descriptor in image 1, you find its nearest neighbor in image 2. There are various strategies for discarding ambiguous matches, ensuring uniqueness of matches, using kd-trees for speed, etc. See the documentation for the matchFeatures function in MATLAB.


What is the relation of complexity class $L^L$ to other complexity classes?

$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.


Yes, and this works for regularity and decidability as well! (not that this is very helpful in any sense)
For example, take any problem $A$ such that $A$ and its complement $\overline{A}$ are not CFLs (the halting problem as an extreme example)
Their union is $\Sigma^*$ which is obviously a CFL.

As a side note, and thanks for @D. Ben Knoble for pointing this out in the comments, that this is only an example. It does not necessarily hold for any two non-CFL languages, and on the contrary also a union of two CFL's may (not always!) end up not being a CFL.


extend ECMAScript by adding new keywords and syntax

I know of two plausible approaches:

One approach is to start with a lexer and parser for ECMAScript and modify them.

Another approach is to build your own preprocessor that takes as input a program with your syntax, and transforms it to EMCAScript which can be accepted by an existing interpreter (by replacing instances of |variable| with something that does fall within the normal ECMAScript syntax).  Since you haven't told us anything about the semantics of the |variable| syntax, I can't make any suggestions for a specific transformation to apply, but you might be able to work one out.


You arrange your 30 batteries in pairs, where each pair consists of either:

2 empty batteries
2 full batteries
1 full and 1 empty battery

If you have a pair with 2 empty batteries it follows, that there is also a pair of 2 full batteries, thus, you have to test at most all of the pairs (15 steps) until you find a pair of two full batteries.

If your walkman isn't working after testing all 15 pairs, you know that each pair consists of a full and an empty battery.
You take the first two pairs with batteries (a,b) and (c,d). You then try the pairings: (a,c), (a,d) and (b,c).
You have now tested 18 combinations and either one of them worked or (b,d) has to be a working pair.

I don't know if this counts as 19 steps for your purposes (you have found 2 full batteries after 18 steps but the walkman is not running yet).


How is the space hierarchy theorem different for non space constructible functions?

Your question is answered on Wikipedia: for any $s(n)$, and $f(n) = O(s(n))$, and any computable $g(n) = o(s(n))$, $\mathsf{DSPACE}(f(n)) \neq \mathsf{DSPACE}(g(n))$. This is a result due to Geffert.


Given the discrete intervals $[a,b]\subset\mathbb{N}$ and $[c,d]\subset\mathbb{N}$, we might be able to do slightly better than binary search using the midpoint without utilizing gradient descent.

Instead, we could use binary search with $x=a+\lfloor\frac{y-c}{d-c}(b-a)\rfloor$, which corresponds to the below intersection of the dotted purple line denoting $y$ and the line from $f(a)=c$ to $f(b)=d$.

The red and blue lines represent the extremes of strictly monotonic functions.
When $f$ is linear, this would immediately find the closest $x$ (which is a big improvement over binary search with the midpoint). Without additional information, I think linearity is the best assumption you can make; there are as many concave functions as convex functions, as well as functions that switch.

One justification for not using gradient descent is if an array $[a,a+1,\dots,b]$ is simply mapped to another array of the same size but different range of data $[c,d]$, which is  randomly chosen (and sorted).

Otherwise, you could use Newton's method as suggested by Dave Clarke or gradient descent as suggested by Raphael, which I just learned are different.


What is the complexity of sum of Logarithm of an arithmetic series

$f(a,b)=\sum_{k=1}^b \log(k*\frac{a}{b})=\log\prod_{k=1}^b \left(k*\frac{a}{b}\right)=\log \frac{b!*a^b}{b^b}=\log(b!)+b\log\frac{a}{b}=b\log a +[\log(b!)-b\log(b)]$

by Stirling's formula, $\log(b!)=b\log b -b +\mathcal{O}(\log{b})$

Therefore $f(a,b)=b\log a +o(b\log a)$ so $f(a,b)\sim b\log a$

NB: all asymptotics ($\sim$, $\mathcal{O}$ and $o$) are taken as $a,b\to\infty$ with $a<b$)

For a more precise evaluation than just an equivalent, replace Stirling's approximation (https://en.wikipedia.org/wiki/Stirling%27s_approximation) with Stirling's bounds (same wikipedia article).


What are some problems which are easily solved by human brain but which would take more time computers?

Language processing.

Every kid learns how to use language within his first 1-3 years. Computers still don't understand simple language structures, not to mention ambiguity, sarcasm, subtleties, etc.


Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT

The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what assignments won't work, and that's the insight you need to do the reduction.

Each clause will be converted into a QUESTION string of length $n$, where $n$ is the number of variables in the 3CNF formula.  Number the variables in the formula from 1 to $n$.  For each clause output a QUESTION string with a 0, 1 or ? in the position of the string corresponding to that variable's number.  Use 1 if the variable is negated in the clause, 0 if it is not negated and ? if it does not appear in the clause at all.

Example: the 3CNF formula has seven variables ($x_1$ ... $x_7$) and there is a clause ($x_1 \lor \lnot x_4 \lor x_7$) you would output the QUESTION string 0??1??0 .

Once all the clauses are converted to QUESTION strings, any $w$ string not covered by the QUESTION strings can be directly converted to a satisfying assignment for the 3CNF formula.  As in the QUESTION strings each position in $w$ corresponds to previously numbered variable.  But in $w$ each 0 represents a variable that should be negated in the satisfying assignment, and each 1 represents a variable that should not be negated.


Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format

I myself have found that DPDA as follows:


Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph

You could try reducing your problem to the directed $s$-$t$ cut problem.

That is, given an instance $G=(V,A)$ of your problem, construct a graph $H$ that is initially a copy of $G$. Then, add to $H$ two new vertices $x$ and $y$, add an arc from $x$ to each $a \in A$ and from $y$ to each $b \in B$; all with a large weight (say $m+1$, where $m = |A|$). The intuition is that an $s$-$t$ cut of $H$ will never use any of the arcs originating from $x$ or $y$ since they are so heavy, but instead only use arcs present in $G$.

You should try to formalize this intuition, i.e., (i) show that the reduction is correct and (ii) show that there is an efficient algorithm for directed $s$-$t$ cut. If both check out, you are done.


maximum coverage version of dominating set

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3].

[1] Lamprou, Ioannis, Ioannis Sigalas, and Vassilis Zissimopoulos. "Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination." arXiv preprint arXiv:1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit, and Kanthi K. Sarpatwar. "Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems." Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

[3] Narayanaswamy, N. S., and R. Vijayaragunathan. "Parameterized Optimization in Uncertain Graphs—A Survey and Some Results." Algorithms 13.1 (2020): 3.


Why is the difference of two NP-complete languages not in NP?

It's a bit artificial, but if we define

$A = \{(G,k):G \text{ has an independent set of size } k \}$

$B = \{(G,k):G \text{ has a clique of size } k \}$

then $A \setminus B$ is $\mathsf{coNP}$-hard because we can reduce $\overline{B}$ to it: given a graph $G$ and a number $k$ we can form $G'$ by adding $k$ isolated vertices to $G$, then $(G',k) \in A\setminus B$ iff $(G,k) \in \overline{B}$.

I claim that

$A \setminus B \in \mathsf{NP} \Leftrightarrow \mathsf{NP}=\mathsf{coNP}$

$(\Rightarrow)$: If a $\mathsf{coNP}$-hard language is in $\mathsf{NP}$, then $\mathsf{NP}=\mathsf{coNP}$.

$(\Leftarrow)$: If $\mathsf{NP}=\mathsf{coNP}$ then $A \setminus B \in \mathsf{NP}$ follows by closure properties of $\mathsf{NP}$.

Since researchers believe that $\mathsf{NP} \neq \mathsf{coNP}$ (this is a stronger version of $\mathsf{P} \neq \mathsf{NP}$), it makes sense to bet on $A \setminus B \notin \mathsf{NP}$. Currently we have no proof though.


How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

There is a $O(nmW)$-time algorithm using dynamic programming.  Let $A[i,j] = $ the cost of the best matching of $[s_1,\dots,s_i]$ to $[t_1,\dots,t_j]$ such that $s_i$ is matched to $t_j$.  Then

$$A[i,j] = \min\{c(s_i,t_j) + A[i-1,j-k] : k=0,1,\dots,W\}.$$

If you consider $W$ a constant, then you obtain a $O(nm)$-time algorithm.

I don't know if the factor of $W$ can be eliminated.

If $W$ is large, this can be improved to $O(nm \lg W)$ time.  The basic primitive we need is:

Given an array $B[1..m]$ and $W$, preprocess $B$ so that we can efficiently answer queries "compute $\min\{B[i],B[i+2],\dots,B[i+W-1]\}$".

Here's how to do that.  Assume first for simplicity that $W$ is a power of two.  You construct secondary arrays $M_2,M_4,M_8,\dots,M_W$ such that $M_w[i] = \min\{B[i],B[i+1],\dots,B[i+w-1]\}$.  You can build them up in $O(m \lg W)$ time, as each $M_{2w}$ can be constructed from $M_w$ in $O(m)$ time.  Thus if $W$ is a power of two you can answer subsequent queries in $O(1)$ time per query.

If $W$ isn't a power of two, you can still express the interval $i,i+1,i+2,\dots,i+W-1$ as the union of at most $\lg W$ intervals each of whose width is a power of two.  Thus, if $W$ isn't a power of 2, you can answer subsequent queries in $O(\lg W)$ time per query.

Finally, apply this to the original problem.  You apply this to each row of $A$, i.e., to $A[i,\cdot]$ for each $i$.  Then the recurrence can be computed using a single query, and it takes $O(\lg W)$ time instead of $O(W)$ time to compute the min.  You'll need to update the secondary arrays each time you update $A[i,j]$, but this takes only $O(\lg W)$ time per update to $A[i,j]$ (as there are only $\lg W$ secondary arrays to update).

In all, you obtain an algorithm whose running time is $O(nm \lg W)$ and with $O(nm \lg W)$ space usage.  (I suspect it's also possible to achieve $O(nm \lg W)$ time and $O(nm)$ space, if necessary, by only storing $M_w[i]$ for values of $i$ that are a multiple of $w$, at the cost of about a 2x increase in running time.)


Self study materials for computational complexity theory

To self-study from Computational Complexity: A Modern Approach, the prerequisites are:

A few courses in algorithms* (you should be comfortable reading and writing pseudocode, using Big-$\mathcal O$ notation, and using abstract data structures like lists, sets and hashmaps)
A course in discrete math
A course which treats Finite State Machines and formal languages** (To the point where you are comfortable drawing and reading finite state machines)
Any course which teaches proofs

Most Bachelor (undergraduate) courses teach all the above. I recommend at least $3$ of the above; the book is written well enough that it remains quite accessible. It does not assume any prior knowledge about complexity classes or Turing Machines.
If you wish to prepare well for a particular course a year in advance, then find out which chapters the course discusses, and read those and then some more, including some exercises (a single-semester course can probably cover less than half the book). Ask the professor which chapters are used, as this changes from one year to the next (Be prepared that the professor has not decided this a year in advance, because she will decide based on what works this year. If she does give an answer, don't treat it as binding or unchanging).
When these requirements are met, my experience is that a big obstacle to overcome is that some students from a CS background have a ``coding mindset" in which, when presented with a problem, they try to solve it with an algorithm. That is not the objective here. Instead, the objective is to understand how different problems relate to each other, and to understand what is the computational power different computational models (e.g. Turing Machines, polynomial-size circuits, FSMs, Turing Machines which use a polynomial amount of memory. And what if they are allowed to flip random coins?). We wish to understand how these two things - problems and computational models - map onto each other. Inevitably, this means proving statements of the form "This problem is too difficult to be solved by that computational model", and "This computational model is more powerful than that one'', and you can't program your way out of that. This is more similar in flavour to abstract algebra, in which one simply tries to comprehend all the groups and rings that are out there; you compare their properties, without trying to code up the multiplication for a particular group.
If you have more time, then read Quantum Computing Since Democritus by Scott Aaronson, because (it is a fun read and) it motivates the questions that are asked in complexity theory.
If you have infinite time, then you can program a SAT Solver; this will help you get familiar with Boolean formulas.
*For example, The Design and Analysis of Algorithms, by Anany Levitin.
**I learned from and recommend Introduction to Languages and the Theory of Computation, by John Martin. It goes all the way from Finite State Machines to Turing Machines. Any book on formal languages should suffice.


How to find left-hand side of tape on a Turing Machine?

for above example before you start your tape is like this ($e$ means empty and right side of $>$ is block of tape that you are reading it)

e>001001e

as you said you should first mark $X$ on the first $1$ and it become like this

e00>X001e

now you should clear two zeros because the number of zeros is twice of the number of ones. you can clear the first two zero of the tape. go to the beginning of the tape like this (when you read $e$ it means you are at the beginning of tape and go one step to the right so that marker be over the first symbol of tape)

e>00X001e

now you can mark two zeros with $X$ or $Y$ it does't matter but for readability it's better to mark it with another symbol

eY>YX001e

now go back to the beginning of tape

e>YYX001e

now it's like a for loop you should do this until there is no $1$ on the tape. when you got end of the tape while searching for $1$ it means that you ran out of ones. you should check two cases

is number of ones less than twice of zeros
is number of ones greater than twice of zeros

if the first case happens while you are searching for zeros you cant find two of them and you got to the end of tape like below

e>00010111e

become

eYYYXYXY1>e

so in this case you should reject the string.

and checking the second case is in the last step when you ran out of ones you should check that is there any zeros one the tape right now. if you found any zero you should reject.

remember never write empty over $0$ or $1$ because when you reach empty it means you are at the end or the beginning of the tape.

based on definition of Turing Machine you can run off the left hand side or not. there are Turing Machines that their tapes are infinite at the right side and finite at the left side so you can run off at the left side. but standard Turing Machine is infinite at both site so you can run off at the left hand side.


You do have a symbol, "$($". A bit more generally though (if I understand the notation you're using), if you're processing an $L$ and you see anything, it must come from an $A$, if it's not an error, so you can recurse to processing an $A$.


Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question shows.

First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours.  For example, if you start your algorithm at $D$, it will go to $B$, then $C$ and then it's stuck because it's already visited both of $D$'s neighbours. The set-up of Hamiltonian cycle avoids this possibility by having an edge between every pair of vertices.

Second, even if your graph contains every possible edge, the algorithm can only produce a path, so it won't produce the minimum spanning tree in any graph where the M.S.T. isn't a path.  For example, take vertices $\{1, \dots, n\}$ with $w(1,i)=1$ for all $i$ and $w(i,j)=2$ for all $i,j\geq 2$. The M.S.T. is all the edges from $1$, and this has weight $n-1$. But your algorithm will find some path that uses only one or two of the weight-$1$ edges, so will have weight $2n-3$ or $2n-4$.


Observe that the expression ${n\choose k}$ may be exponential in $n$ (e.g. if $k=n/2$).

Factorization is surely in NP. We don't know whether it is in P or not. This is a major open question. The fact that factorization is in BQP gives evidence that it might not be NP-complete (as other NP complete problems are not known to be in BQP)


On deterministic weighted graph isomorphism from randomized

Consider first the case of two colors. We can identify with each vertex $x$ its color distribution $a$, which is the number of edges of color 1. The distribution of $a$ is $\mathrm{Bin}(n,1/2)$, and so if we divide the vertices into bins according to their color distribution, the heaviest bin will contain $O(\sqrt{n})$ vertices with high probability. If we repeat the process, we the heaviest will contain $O(\log n)$ vertices with high probability. Once more, and we expect all bins to have size 1.

What this sketch suggests is that even if you have a constant number of colors (in this case, 8) then with high probability, every vertex will have a unique color distribution (histogram of colors of the edges adjacent to it). This makes graph isomorphism very easy for such graphs.

Of course, this sketch isn't rigorous. To know for sure, you will have to make it rigorous, and find whether it indeed works; perhaps a constant number of rounds isn't enough, but $\alpha\log n$ rounds (as in your case) are.


Is there an efficient solution to the travelling salesman problem with binary edge weights?

No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard.  (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)


This answers a previous version of the question, in which the goal was to prove that with high probability, $\max |H_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$ for some constant $C > 0$.

When a particular walker is not at the root, it has a probability of 2/3 to go down a step, and a probability of 1/3 to go up a step. This is where $n/3$ comes from. However, when it is at the root, it always goes down. This suggests comparing $H_i$ to a sum of $n$ i.i.d. variables whose distribution is $+1$ w.p. $2/3$ and $-1$ w.p. $1/3$. Indeed, if $X_i$ is a variable with that distribution, then $H_i$ stochastically dominates $X_i$. Hence it suffices to show that
$$
\mathbb{P}\left(\max_{i \in [m]} X_i \geq \tfrac{n}{3} + C\sqrt{n\ln m}\right) \geq 1-\frac{1}{m}.
$$
(More formally, we can construct a coupling of the $H_i$ and $X_i$ in which $H_i \geq X_i$.)

Up to an affine transformation, the distribution of $X_i$ is binomial, so it should be easy to obtain whatever bound you wish. You can take a look at Lower bounds on binomial and Poisson tails: anapproach via tail conditional expectations by Pelekis, for example.


Informally, you might call this lazy evaluation, or a lazily-evaluated stream.

A $O(f(n))$-time delay algorithm is guaranteed to output a stream of answers, with a delay of at most $O(f(n))$ time between answers.  One consequence is that outputting $k$ answers will take at most $O(k \times f(n))$ time -- but you also know that you won't ever have to wait too long for the next output.  (So, this helps rule out algorithms that return the first $n$ answers very rapidly and then take a really long time to return the $n+1$th answer).

An output-sensitive algorithm is an algorithm that outputs a stream of answers, and where the running time is some function of the length of the output.  Normally we evaluate the running time of an algorithm as a function of the length of the input, but an output-sensitive algorithm is analyzed in terms of the length of the output.  That's potentially relevant here.  Suppose your goal is to enumerate all fidgets in a warbuggle.  If you find an polynomial output-sensitive algorithm for this task, then you have an algorithm that's potentially useful for streaming purposes -- in particular, the average delay between outputs isn't too large (though the worst-case delay could potentially be quite high).

If neither of them captures exactly the concept you have in mind, then I suggest you just describe in text what properties your algorithm has, and don't worry too much about finding a short term for it.


Applying the Pumping Lemma to aspecific string

The empty string is a legitimate string, just like the empty set is a legitimate set. We say that a word $w \in \Sigma^*$ can be pumped with respect to parameter $p \geq 1$ and a language $L$ if there exists a decomposition $w = xyz$, where $x,y,z \in \Sigma^*$ satisfy the following three requirements:

$|xy| \leq p$.
$y \neq \epsilon$.
$xy^iz \in L$ for all $i \geq 0$.

A mathematical definition hides nothing. A word can be pumped if it satisfies the definition as stated. No more, no less.


Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

You can express $p(x,y)$ as a formula that depends on just the number of bits that differ between $x$ and $y$.  Try to see if you can do that.  That will provide a nice clean formula that doesn't require examining $16 \times 16$ cases by hand.


Finding minimum path in a matrix algoritm

A conceptually simple approach is to form an unweighted graph with $(k+1)n^2$ vertices: one copy of the matrix for each possible number of credits remaining.  Each edge represents a way you can travel in a single step.  You start at $(x_1,y_1,k)$ and want to end at $(x_1,y_1,0)$.  Now, look for the shortest path in this graph.  There is a straightforward algorithm to find the shortest unweighted path in such a graph.  Also, any good algorithms textbook will tell you how to justify its correctness.

This should produce an approach where it is very easy to justify its correctness.  Its running time is not the best possible, but it's not too terrible, either.  The running time is something like $O(n^2 k^2 w)$: the degree of each vertex is $O(kw)$, and there are $O(n^2 k)$ vertices, so $O(n^2 k^2 w)$ edges in total.  This is $O(n^3 k^2)$, so not too much slower than your algorithm.  If your primary criterion is ease of justifying correctness, this might be a simple solution.


As discussed in the comments, this question hinges around subtleties of the definitions. NP is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" is automatically excluded. Natural problems come in a number of variants and it's sometimes important to distinguish between them.

To a complexity theorist, the travelling salesman problem (TSP) is exactly the following problem:

Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities, and a target distance $d$.
Question: Is it possible to start at one of the cities, visit every other city exactly once and return to the starting city while travelling total distance at most $d$?  (Equivalently, does the shortest such route have total length at most $d$?)

Then there is the following optimization problem, MIN-TSP:

Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities.
Question: What is the shortest distance it is possible to travel in order to start at some city, visit each of the others exactly once and return to the start city?

There are also other variants:  F-TSP (function-TSP) has the same input as TSP but the output is a route of length at most $d$, if one exists, and "no", otherwise, rather than just yes or no; F-MIN-TSP is the analogous version of MIN-TSP.

These problems are all inter-related but they're not the same problem. In particular, only TSP is a decision problem: MIN-TSP is an optimization problem and the F- problems are function problems.  TSP itself is NP-complete. If you can solve MIN-TSP, you can clearly solve TSP by computing the minimum and comparing it against $d$, so MIN-TSP is NP-hard (but can't be complete because it's not a decision problem so it's not in NP).  Conversely, if you can solve TSP and you're allowed to make multiple TSP queries, then you can solve MIN-TSP by binary search.

For the function versions, being able to solve F-TSP clearly allows you to solve TSP: if F-TSP gives you a route, say "yes"; otherwise, say "no". Similarly for F-MIN-TSP.  On the other hand, it's not clear that being able to solve TSP helps you solve F-TSP: being told that it's possible to visit the capitals of the 48 contiguous states and Washington, D.C., while travelling a total of less than 11,000 miles doesn't seem to give you much of a hint as to what the route would be.

Your other two examples have the same families of variants. The standard Knapsack problem has a tarvet value $v$ and asks if your knapsack can carry items of total value at least $v$; OPT-Knapsack asks what is the greatest value you can carry. ILP asks if the linear inequations have an integer solution; OPT-ILP asks for the maximum solution.  In both cases, the decision version of the problem is NP-complete and the optimization version is NP-hard.


Can this be shown using the space hierarchy theorem?

Yes. By the space hierarchy theorem, there is a language $L\in\mathrm{DSPACE}(2^n)$ that is not in $\mathrm{DSPACE}(f(n))$ for any $f=o(2^n)$.  In particular, this language is not in $\mathrm{DSPACE}(n^k)$ for any $k$, so it is not in $\mathrm{PSPACE}$.

  Is that the most simple and straight-forward way?

It's hard to imagine anything simpler!


How to implement simulation on two LTSs?

If you have doubts about whether a certain type of relation exists, a good place to search is Rob van Glabbeek's extensive catalogue of such relations. That article is a bit dated by now, but still extremely comprehensive.

Linear Time-Branching Time Spectrum II, Robert J. van Glabbeek, 1993.

There are several papers on the algorithmic aspect. I would suggest the one below.

Generalizing the Paige-Tarjan Algorithm by Abstract Interpretation, by Francesco Ranzato and Francesco Tapparo

This paper provides a design-pattern for implementing partition-refinement style algorithms for checking bisimulation and simulation. The later sections of the paper are quite algorithmic. You could contact the authors and ask about their implementation.

Computing Stuttering Simulations by Francesco Ranzato and Francesco Tapparo

You asked about branching and not stuttering, but I think the contents of the above paper are very related to what you want.

There are some implementations that may help your study.

The Edinburgh Concurrency Workbench
The Concurrency Workbench of the New Century
Concurrency Workbench, Aalborg Edition

All the tools above implement checking equivalences of processes with respect to preorders; the third one is more recent and is also offered online.


Computing theory: can a single node be a subgraph?

What about the following argument?

  Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.

  Though this is only valid if a single node can be considered a graph.

That's completely circular. If a single node can be a graph, you can ask about its subgraphs and, sure, every graph is a subgraph of itself. But if a single node can't be a graph, it doesn't make sense to ask about subgraphs of something that isn't a graph.

In general, a single vertex is considered to be a graph, referred to as the "trivial graph".  However, it's something of a special case in that it's often an exception to statements one might wish to make when proving things.  For example, every connected graph contains at least one edge... except for the trivial graph; every graph has a proper subgraph... except for the trivial graph; etc. Because of this, writers often exclude the trivial graph from consideration. So, for example, in the "notation" section of a graph theory paper, you often see a statement such as "Except where stated otherwise, we assume that every graph contains at least one edge".

In this respect, asking whether the trivial graph is a graph is a bit like asking whether zero is a natural number. Some people will jump up and down and insist that it is; some people will jump up and down and insist that it isn't; the best plan is to say that it is or isn't according to what makes your life easiest in any particular situation.


Is there any count-preserving cellular automata which tends do "10101010..."?


Regarding this article every time you expand a node in the AO* algorithm you must go backwards to update all of its predecessors’ estimated cost.

When you use linear data structure to contain the nodes you must traverse the data elements sequentially and only one data element can be directly taken (stack, queue, priority queue …).

In AO* each time a node is taken for expansion based on its estimated cost the algorithm iterates over all of the nodes that are its predecessors(to update their estimated cost). That means that sometimes you should take element based on its estimated cost and sometimes based on its successor. There is no sequence order that can meet both of these conditions in the general case.
Probably there is a way to use "nested" linear data structures, but it should just imitate a tree structure, and it will be better to build the search tree instead.


Minimum sum of two numbers formed from digits of two arrays

This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n_1$ at the end. Observation: after this process is done all remaining digits in both arrays are different (but this is not very relevant).

Brute force the next digit of $n_1$, there are at most 9 possible digits that can be used for $n_1$. Fix a digit $d$ not used yet in the first array. Once $d$ is fixed as the next digit of $n_1$ use the largest digit lower than $d$ for $n_2$ (if no such digit exists continue with next digit for $n_1$).

After we have this prefix for $n_1$ and $n_2$ we already know that the inequality $n_1 > n_2$ holds, whatever order we use for following digits. In order to minimize $n_1 - n_2$ we should order remaining digits from first array in such a way that $n_1$ is minimized and order remaining digits from second array in such a way that $n_2$ is maximized. For the first case we should add remaining digits of $n_1$ in non-decreasing order, and for $n_2$ in non-increasing order.

Next is the pseudo-code for the explained algorithm. Notice that $n_1$ and $n_2$ are treated as string, not like numbers, so addition means concatenation. Also, instead of dealing with array of digits as input, convert them to array of frequency, $F_i(d)$ denotes how many times digit $d$ can be used for number $n_i$.

F1 = Frequency of each digit in first array.
F2 = Frequency of each digit in first array.

n1 = ""
n2 = ""

# Remove common digits in both arrays
for d in [0..9]:
    while F1[d] > 0 and F2[d] > 0:
        n1 += d, n2 += d
        F1[d] -= 1, F2[d] -= 1

# Brute force next digit for number n1
for d1 in [1..9]:
    # Ignore digit if it is not available
    if F1[d1] == 0:
        continue

    d2 = None

    # Iterate backwards and find higher digit available for d2
    for d2_it in [d1 - 1..0]:
         if F2[d2_it] > 0:
             d2 = d2_it
             break

    # If there is no available next digit for n2 continue
    if d2 is None:
        continue

    tmp_n1 = n1 + d1
    tmp_n2 = n2 + d2

    # Add next digits greedily
    for d in [0..9]:
        for i in [0..F1[d]):
             tmp_n1 += d

    for d in [9..0]:
        for i in [0..F2[d]):
             tmp_n2 += d

    # Check difference of this pair
    # and keep better pair accordingly to problem restrictions.
    # This function will be called at most 9 times.
    report tmp_n1, tmp_n2

Notice that report will be called 0 times in case there is no valid answer.


Cross platform apps and programing languages...how is it done?

First word: consistent API across platforms - when programming on different platforms, the same API is presented to programmers.

Second word: layered architecture - this hides the low level differences under a consistent layer.


If I want to go from A to B, that doesn’t get faster by taking a bus. But if I want to take 50 people from A to B that actually will be done much faster.
A simple example: How do you make six boiled eggs? And how do you make 120 boiled eggs if you have an oven with four flames, that will involve some pipelining as well.


Steiner tree problem in graphs of diameter 3

This is an interesting question.

It is not true that $|V'|$ is always less than or equal to $2|T|$. Here is the smallest example of $G$ and $T$ where $|V'|$ must be greater than $2|T|$.

Graph $G$ as depicted above has 9 vertices $A,A_1,A_2,B,B_1,B_2,C,C_1,C_2$ and 12 edges $AA_1, A_1A_2, A_2A,$ $BB_1,B_1B_2,B_2B,$ $CC_1, C_1C_2, C_2C,$ $A_1B_2, B_1C_2, C_2A_1$. It is easy to check the diameter of $G$ is 3.

Let $T=\{A,B,C\}$. Suppose $T'=(V',E')$ is a minimal tree in $G$ that spanns $T$.

If $V'$ contains all 9 vertices, then $|V'|=9$.
Otherwise, WLOG, assume $V'$ does not contain $A_1$. If anyone of $A_2$, $C_1$, $C_2$ and $B_1$ is not in $T'$, then $A$ and $B$ will not be connected in $T'$. Since $A$ and $B$ are connected in $T'$, all of those 4 vertices must be in $T'$. So $|V'|\ge3+4=7$.

So $|T'|\gt 6= 2|T|.$

Exercise 1. Verify that the following two graphs are also examples where $|V'|$ must be greater than $2|T|$ with $T=\{A, B, C\}$

Exercise 2. (less than 1 minute) If $|T|=3$, then $|V'|\le7$.

Exercise 3. Let $n\ge3$. Construct $G$ and $T$ such that $G$ is connected of diameter 3, $|T|=n$ and $|V'|\gt 2|T|$. (Hint, imitate the simpler example in exercise 2.)


sub-optimal but fast partition generation

The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly.

  Imagine that you run a computer center with $p$ identical machines, or a parallel computer with $p$ processors, for some constant $p$. You are given $n$ jobs with running times $t_1,t_2,...,t_n$. Your task is to find a schedule - a function $f:\{1,...,n\}\rightarrow\{1,...,p\}$ that assigns the $j$th job to the $f(j)$th machine.
  The load on the $j$th machine is the total time it takes to run the jobs assigned to it,
  $$
L_j = \sum_{i:f(i)=j} t_i\,.
$$
  Since the machines run in parallel, the time it takes us to finish all the jobs is the maximum load on any machine,
  $$
M=\max_{i\leq j\leq p} L_j\,.
$$
  We call this time the makespan, and your goal is to minimize it. This gives the following problem:

    Makespan
    Input: A set of $n$ running times $t_i\geq0,\,i=1,...,n$
    Output: A function $f: \{1,...,n\}\rightarrow\{1,...,p\}$ that minimizes the makespan
    $$M = \max_{1 \leq j \leq p} \sum_{i:f(i)=j}t_i$$

  Exercise 9.3 Reduce Integer Partitioning to the case of Makespan where $p=2$.

  There is, however, a simple algorithm that comes with a quality guarantee. The idea is to divide tasks into two groups, "large" and "small", and schedule the large tasks first. Let $T_{\text{tot}}=\sum_{j=1}^n t_j$ be the total running time of all the tasks. We choose some constant $\eta > 0$, say $\eta = 1/10$. We call the $j$th task large if its running time is at least a fraction $\eta$ of the total, $t_j \geq \eta\,T_{\text{tot}}$, and small if $t_j < \eta\,T_{\text{tot}}$.
  The algorithm then proceeds in two phases:

  Find a schedule that minimizes the makespan of the large tasks, using exhaustive search.
  Distribute the small tasks by giving each one to the machine with the smallest load so far, regardless of that tasks's running time.

  How long does this algorithm take? Since there are at most $1/\eta$ large tasks, there are $p^{1/\eta}$ ways to schedule them. Since $p$ and $\eta$ are constants, this gives a constant number of possible schedules to explore in phase 1, and we can check all of them in polynomial time using exhaustive search. Phase 2 clearly runs in polynomial time as well.
  Now let $M$ denote the makespan of the schedule produced by this algorithm. How does it compare to $M_{\text{opt}}$? Let $M_{\text{large}}$ denote the maximum load of a machine after phase 1, i.e., the minimum makespan of the large tasks. Since adding the small tasks can only increase the makespan, we have $M_{\text{large}} \leq M_{\text{opt}}$. If the algorithm manages to fit all the small tasks in phase 2 without increasing the makespan, putting them on machines with load less than $M_{\text{large}}$, then $M = M_{\text{large}}$. But since $M_{\text{opt}} \leq M$, in this case $M = M_{\text{opt}}$ and the algorithm performs perfectly.
  So, we will focus on the harder case where the makespan increases in phase 2, so that $M > M_{\text{large}}$ and our schedule for the small tasks might not be optimal. Let $L_j$ denote the load of machine $j$ after phase 2. Without loss of generality, we can assume that $L_1 \geq L_2 \geq ... \geq L_p$. Since $L_1 = M > M_{\text{large}}$, we know that at least one small task was added to machine 1.
  Let $t$ be the running time of the last such task. Since our strategy greedily assigns small tasks to the machines with the smallest load, the load of machine 1 must have been less than or equal to the others just before this task was added. This means that, for all $2 \leq j \leq p$,
  $$
M-t \leq L_j \leq M\,.
$$
  Since $t<\eta\,T_{\text{tot}}$, we also have
  $$
T_{\text{tot}} = M + \sum_{j=2}^p L_j \geq pM-(p-1)t\geq pM-\eta(p-1)T_{\text{tot}}\,.
$$
  Rearranging this gives an upper bound on M,
  $$
M \leq \frac{T_{\text{tot}}}{p}(1+\eta(p-1))\,.
$$
  On the other hand, the best schedule we could hope for would be perfectly balanced, keeping all the machines busy all the time. Thus the optimum makespan is bounded below by
  $$
M_{\text{opt}}\geq\frac{T_{\text{tot}}}{p}\,.
$$
  Combining this lower bound on $M_{\text{opt}}$ with the upper bound we have on $M$ gives an approximation ratio
  $$
\rho \leq \frac{M}{M_{\text{opt}}} \leq 1+\eta(p-1)\,.
$$
  By setting $\eta = \epsilon/(p-1)$, we can approximate $M_{\text{opt}}$ within a factor of $\rho = 1+\epsilon$ for arbitrarily small $\epsilon > 0$. In fact, we can define an algorithm that takes both the problem instance and $\epsilon$ as inputs, and returns a $(1+\epsilon)$-approximation. For each fixed $\epsilon$, this algorithm runs in polynomial time. Such an algorithm is called a polynomial-time approximation scheme or PTAS.
  On the face of it, a PTAS seems to be sufficient for all practical purposes. It allows us to find solutions within 1%, 0.1%, 0.01% ... of the optimum, each in polynomial time. However, improving the quality of the approximation comes at a cost, since the running time increases as $\epsilon$ decreases. Our PTAS for Makespan, for example, has to explore $p^{1/\eta} = p^{(p-1)/\epsilon}$ possible schedules in phase 1, so its running time grows exponentially as a function of $1/\epsilon$. Even for $p=2$ and $\epsilon = 0.01$, this number is $2^{100}$ - hardly a constant that we can ignore.
  We would prefer an algorithm whose running time is polynomial both in $n$ and in $1/\epsilon$. Such an algorithm is called a fully polynomial-time approximation scheme, or FPTAS for short. There is, in fact, an FPTAS for Makespan, which we will not describe here.

The end of chapter notes further recommend the "outstanding" book Approximation Algorithms by Vazirani, from which this algorithm is apparently taken.


Path with least max-weight, in an undirected connected graph

This problem is known as the minimax path problem. A linear time algorithm is given in this note. I quote it here. Note the note solves the bottleneck shortest path problem, and to solve your original minimax path problem, you should reverse the sense of all the weight comparisons performed by the algorithm, or equivalently replace every edge weight by its negation.

  The correctness of Algorithm 1 (for undirected graphs) is rather obvious: If in line 6 it turns out that the graph still is $s$–$t$–connected, than hiding the edges of weights less than $M$ in line 5 did not affect the optimal solution. Otherwise, in each subgraph to be shrunken in line 9, every vertex can be connected to every other one by a path with capacity at least $M$; thus the bottleneck of $t$ (being smaller than $M$) will remain the same in the shrunken graph.

  Furthermore, the algorithm runs in time $O(m)$, where $m = |E|$ denotes the number of edges: The crucial observation is that in every iteration of the loop in lines 3–11 half of the edges are removed from the graph, either by shrinking all "thick" edges (in line 9) or by dropping all "thin" edges (in line 5). As all steps inside that loop can be done in linear time in the size of the current graph, the total running time is bounded by
  $$O(m)+O\left(\frac{m}{2}\right)+O\left(\frac{m}{4}\right)+\cdots=O(m).$$
  This shows the following result.


Unambiguous grammars with different right and left hand derivations

Consider the following simple grammar:
$$
S\to AB \\
A\to a \\
B\to b
$$
Here is a leftmost derivation of $ab$:
$$
S\to AB \to aB \to ab
$$
Here is a rightmost derivation of $ab$:
$$
S \to AB \to Ab \to ab
$$
You can see that they look different. However, they correspond to the same parse tree:

More generally, each leftmost derivation corresponds to a parse tree, and this correspondence is a bijection; and the same holds for rightmost derivations. Therefore each leftmost derivation has a corresponding rightmost derivation, sharing the same parse tree.


Does programming language detection need more input than natural language detection?

Answering knowingly this question would require experiments. I am sure
there is some data for natural languages, where it is a common
problem. I recall from memory that one study gave ridiculously small
figures for natural language, which is not too surprising. If you take
5 consecutive word in a sentence (the figure I recall, without being
sure), there is a good chance that one of them belongs to a single
language, and even more that the fragment can syntactically belong to
only one language (parsing fragments without context is possible with
existing technology). To me the problem is not so much the size of the
input as the size of the recognition program and its data. There is a
compromise there. Actually my guess is that keeping all the relevant
data is far too costly, and that the actual techniques are statistical
ones, such as checking n-grams of letters. (see Wikipedia), which are
extremely effective.

Regarding programming languages, the problem is a bit different. The
size of the vocabulary is ridiculously small, and identifiers do not
give any indication (or very little with the allowed mophology: a
language could forbid to use dask inside identifiers, for example).
Furthermore, what fixed vocabulary there is (keywords) is often the
same in many programming languages.  However, programming languages
have a very strict syntax, which will certainly distinguish them
rather quickly.  It is not so much how long a fragment as the kind of
fragment. A long succession of assignments might look the same in many
programming languages. Buit I would not venture any figure, and I am
not even sure statistics would make sense.

Then there is the issue of parenthood. A fragment of Pascal may look
very much like a fragment of Algol 60 or Simula 67. Is American
English to be distinguished from British or Autralian English?

To conclude, without any hard knowledge on facts:

The problem should be stated with a word regarding the space cost (and
possibly time-cost) of the identification program.

Identification for natural language is essentially morphology or
lexically based, and will use statistical techniques if space costs
are to be acceptable. They can recognize fairly short sequences (a few
words as I recall) with good accuracy.

Identification for programming languages is essentially syntax based,
and probably needs larger fragments in number of tokens, in order to
have enough syntax substance, despite the intentional similarities
between programming languages. But it can probably be 100% accurate,
without excessive size of the identification program. I would however
be more confident if I had actual data to back my guesswork. I do not know of any work on this topic.

Considering only fragments is not an issue. It is obviously not an
issue when only lexical information is used. It is not an issue either
when syntactic information dominates, as the technology to parse
fragments is working well.

Afterthoughts, after the question was completed.

One minor remark concerns the concept of substring size: is it measured in
characters, in bytes, in lexical elements? Size of character encoding
is variable. Characters take diacritical marks. Lexical elements have
different average size in natural and programming languages.

A more important remark concerns the mode of measurement. Natural
language will use statistical methods to avoid the problem of natural
language huge specification. Hence the answer is accordingly accurate
with some probability that may depend on substring length (different
techniques produce different types of mis-detection).

In the case of programming languages, the specifications are small
enough that they can probably be used exactly. Hence the answer could
possibly be always 100% exact at acceptable cost. The problem would
not be with the detection procedure inaccuracies as in natural
language, but in the question itself. If a string does not
discriminate two languages because it can belong to both, no amount of
technology will help you solve the problem. In such a case, the
detection software should not guess, which would be meaningless, but it should just list, with a 100% accuracy, all the
programming languages the substring can belong to.

In other words, the case of natural language and the case of
programming languages are very different technically. I am not sure it
makes sense to compare them.


Can't understand this division algorithm in Computer Architecture

The divisor is the 2 put into the upper 4 bits of the 8 bit divisor register.


The best you can do is keep track of all currently known equivalences using a Union-Find data structure.  Initially, each element is in own group.  Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.


Show that $0^i$ where $i$ is a power of 2 is not context free

If you're still confused, here's the proof. Let $p$ be the integer of the Pumping Lemma and consider the string $0^{2^p}$. If $L$ was a CFL, then (since $2^p\ge p$) the PL would apply to $0^{2^p}$ we'd have $0^{2^p}=uvxyz$ with

$|vxy|\le p$
$|vy| > 0$

So if we let $v=0^k, y = 0^j$, we have from (1), $k + j =|vy| \le |vxy| \le p$ and from (2), $k + j=|vy|>0$. In other words,

  $0<k+j\le p$

Now pump up: The PL assures us that $uv^2xy^2z\in L$, and observe
$$
|uv^2xy^2z| = 2^p+(k+j)\le 2^p+p< 2^p+2^p=2^{p+1}
$$
as long as $p>0$, so the pumped string $uv^2xy^2z$ has length strictly between $2^p$ and $2^{p+1}$. No such string can be in $L$, so we have a contradiction to the PL implication that $uv^2xy^2z\in L$ and so our initial assumption, that $L$ was a CFL, must be false.

You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language $L=\{0^{2^n}\mid n\ge 0\}$ is not regular.


This is a suggested "interpretation" of the IO monad. If you want to take this "interpretation" seriously, then you need to take "RealWorld" seriously. It's irrelevant whether action world gets speculatively evaluated or not, action doesn't have any side-effects, its effects, if any, are handled by returning a new state of the universe where those effects have occurred, e.g. a network packet has been sent. However, the result of the function is ((),world) and therefore the new state of the universe is world. We don't use the new universe that we may have speculatively evaluated on the side. The state of the universe is world.

You probably have a hard time taking that seriously. There are many ways this is at best superficially paradoxical and nonsensical. Concurrency is especially either non-obvious or crazy with this perspective.

"Wait, wait," you say. "RealWorld is just a 'token'. It's not actually the state of the entire universe." Okay, then this "interpretation" explains nothing. Nevertheless, as an implementation detail, this is how GHC models IO.1 However, this means that we do have magical "functions" that actually do have side-effects and this model provides no guidance to their meaning. And, since these functions actually have side-effects, the concern you raise is completely on point. GHC does have to go out of its way to make sure RealWorld and these special functions are not optimized in ways that change the intended behavior of the program.

Personally (as is probably evident by now), I think this "world-passing" model of IO is just useless and confusing as a pedagogical tool. (Whether it's useful for implementation, I don't know. For GHC, I think it is more of a historical artifact.)

One alternative approach is to view IO as a describing requests with response handlers. There are several ways of doing this. Probably the most accessible is to use a free monad construction, specifically we can use:

data IO a = Return a | Request OSRequest (OSResponse -> IO a)

There are many ways to make this more sophisticated and have somewhat better properties, but this is already an improvement. It doesn't require deep philosophical assumptions about the nature of reality to understand. All it states is that IO is either a trivial program Return that does nothing but return a value, or it's a request to the operating system with a handler for the response. OSRequest can be something like:

data OSRequest = OpenFile FilePath | PutStr String | ...

Similarly, OSResponse might be something like:

data OSResponse = Errno Int | OpenSucceeded Handle | ...

(One of the improvements that can be made is to make things more type safe so that you know you won't get OpenSucceeded from a PutStr request.) This models IO as describing requests that get interpreted by some system (for the "real" IO monad this is the Haskell runtime itself), and then, perhaps, that system will call the handler we've provided with a response. This, of course, also doesn't give any indication of how a request like PutStr "hello world" should be handled, but it also doesn't pretend to. It makes explicit that this is being delegated to some other system. This model is also pretty accurate. All user programs in modern OSes need to make requests to the OS to do anything.

This model provides the right intuitions. For example, many beginners view things like the <- operator as "unwrapping" IO, or have (unfortunately reinforced) views that an IO String, say, is a "container" that "contains" Strings (and then <- gets them out). This request-response view makes this perspective clearly wrong. There is no file handle inside of OpenFile "foo" (\r -> ...). A common analogy to emphasize this is that there is no cake inside of a recipe for cake (or maybe "invoice" would be better in this case).

This model also works readily with concurrency. We can easily have a constructor for OSRequest like Fork :: (OSResponse -> IO ()) -> OSRequest and then the runtime can interleave the requests produced by this extra handler with the normal handler however it likes. With some cleverness you can use this (or related techniques) to actually model things like concurrency more directly rather than just saying "we make a request to the OS and things happen." This is how the IOSpec library works.

1 Hugs used a continuation-based implementation of IO which is roughly similar to what I describe albeit with opaque functions instead of an explicit data type. HBC also used a continuation-based implementation layered over the old request-response stream-based IO. NHC (and thus YHC) used thunks, i.e. roughly IO a = () -> a though the () was called World, but it isn't doing state-passing. JHC and UHC used basically the same approach as GHC.


Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

You're right about the second one, but your reasoning for both is sketchy. The definition of $f(n)=O(g(n))$ is that there exist constants $c,N$ both greater than zero such that $f(n)\le c\cdot g(n)$ for all $n\ge N$.

Trying a single value for $n$ won't generally give anything in the way of an answer. Consider, though, the intuition we get from trying $n=4, 8, 16, 32, \dotsc$:
$$\begin{array}{lcccc}
n: & 4 & 8 & 16 & 32 & 64 & 128\\
\log^2 n: & 4 & 9 & 16 & 25 & 36 & 49
\end{array}$$

It seems to be the case that $n$ grows much faster than $\log^2n$. In fact, for this example we have that at least for powers of 2, $\log^2(n)=\log^2(2^k)=k^2\le 1\cdot2^k=1\cdot n$ for all $n \ge 16$, so we might suspect that $\log^2n=O(n)$, which is indeed the case, as it happens.

What is most helpful is to get an intuition of the big-O relationship between frequently-used functions. Here are some examples (all of which should be proved, but that'll be up to you do do or look up). Assuming everything in sight is positive, then:

$\log n = O(n^k)$ for any $k>0$. (polynomials beat logs, eventually)
If $a \le b$, then $n^a=O(n^b)$. (polynomials behave as expected, by degree)
If $a>1$, then $n^k=O(a^n)$. (exponentials beat polynomials)

and so on. The point here is that it's far better to develop your intuition and only use the definition of big-O when faced with a problem where intuition doesn't give you any help. That's what the experts do.


Plugging it into my LL(1) computer, loner gives false:

<S> ::= <E> | <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

(Note there are some duplicate rules here, which become apparent in the formatted version.)

Proving it (e.g., via the set properties or a pumping lemma) is left an exercise.

If / is intended to a be terminal (and not alternation!), then we have

<S> ::= <E> '/' <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

is still not LL(1).

The derivation would be more readable (and more obviously correct) if shown like (e.g.)

S ->  E / S
(with E -> 'S')
-> 'S' / S
(with S -> E / S)
-> 'E / S' / S
(with E -> letter)
-> 'a / S'/ S
(with S -> E / S)
-> 'a / E / S' / S
(with S -> E -> 'S' -> 'E / S') ; note the application of several steps, here
-> 'a / E / 'E / S'' / S
(with S -> E -> letter) ; and again. better to be explicit
-> 'a / e / 'g / s'' / q


Tracing a polynomial algorithm for the problem of maximum-weight independent set

It won't matter which node you select as the root, in the sense that the algorithm will always find a maximum-weight independent set. The actual set of nodes selected by the algorithm might differ, if there are multiple maximum-weight solutions.

Let's say the root is the node with weight 2. Either it is in the optimal solution, or it isn't.

If it is, then 7, 10, and 7 are not; the remaining tree only contains 4. Thus this solution has weight 2 + 4 = 6.
If it is not, then the answer is the maximum-weight independent set on the forest in which the components are the subtrees with weight 7, 10, and (7, 4). Solving the problem recursively on the subtrees gives 7 + 10 + 7 = 24.

Since 24 > 6, the answer is 24.


Showing a problem on a specific graph is NP-hard

There's no such thing as a hard instance. You can always figure out the answer to that one instance and then hard-code that into an algorithm. For example, you can always have an algorithm for SAT that says

if input="(XvY)^(!Xv!YvZ)"
    return SATISFIABLE
else
    [loop through all possible variable assignments]

Incidentally, this is why nobody looks at "best-case complexity", since any algorithm can be adapted to run in best-case constant time in this way.  (Constant because you only have to read a fixed amount of the input to see if it's one of the ones that you have a hard-coded answer for.)

There's a category error in asking if an instance can be NP-complete. Recall the definition of what NP-completeness is:

  A language $L$ is NP-complete if is in NP and every other language in NP is polynomial-time many–one reducible to $L$.

First, that statement doesn't "type-check" if you try to make $L$ be a string rather than a language.  Second, the definition of many–one reductions requires that you have at least one "yes" instance and at least one "no" instance to use as targets for the reduction. One instance isn't enough to make these definitions work.


$r1⋈ r2$ is the natural join of $r1$ and $r2$/ That is inner join on the common attribute $R$, where $R$ is the primary key of $r2$. It is Cartesian product of $r1$ and $r2$ followed by selection.

For each element $(a,b)\in r1⋈ r2$, where $a=(p,q,r)$ and $b=(r', s,t)$, we must have $r=r'$. That is, $b=(r,s,t)$. Since $R$ is the primary key for $r2$, for any $a\in r1$, there is at most one $b$ that can "join" $a$. So we will have at most 2000 tuples.

By the way, I could not see why "Suppose all value of R in r1 are same. Then it should be 4499". It is not even an option in the original problem.


Is the following recurrence for this program's runtime correct?

tl;dr: NO.  Well, okay, maybe.

Translating the pseudocode mechanically into a recurrence gives me
$$
T(n) = \Theta(1) + F(n) + \max \begin{cases}
    \max_{0\le s \le n/4} T(s) \\
\\
    \max_{n/4 < s < n} (T(s) + T(n-s))
\end{cases}
$$
where $F(n)$ is the time for the first "find" step.  Every outcome that is not known in advance is folded into the $\max$; since we're bounding the worst-case running time, we always assume the worst possible outcome.  The initial $\Theta(1)$ includes all the time for bookkeeping, comparisons, stack manipulation, and that union operation in the output.  (Performing a set union in constant time is somewhat magical, but I'll let that slide.)  I'm also assuming here that the variable $s$ always lies between $0$ and $v-1$, since otherwise the algorithm never terminates, although this assumption is never specified in the code.

Under the reasonable assumption that $T(n)$ is monotonically increasing, we have
$$
\max_{0\le s \le n/4} T(s) = T(n/4)
$$
Under the further assumption that $T(n)$ is "nice" and convex, we have
$$
\max_{n/4 < s < n} (T(s) + T(n-s)) =
 \begin{cases}
 T(n-1) + T(1) & \text{if $T$ is convex}\\
 T(n/4+1) + T(3n/4-1) & \text{if $T$ is concave}
 \end{cases}
$$
Here, "convex" means that $(T(a) + T(b))/2 \ge T((a+b)/2)$ for all $a$ and $b$, or less formally, that the function "curves upward".  If $T$ is "nice", this is equivalent to assuming $T(n) = \Omega(n)$.  Symmetrically, $T$ is concave (curves downward) iff $T(n) = O(n)$.

("Nice" means a function whose second derivative is well-defined and doesn't oscillate between positive and negative forever; for example, the product of a polynomial and some logarithms is nice.  Wacky functions like $n^{2 + \sin(2\pi n)}$ are not nice, but I'll bet you a dollar that your algorithm doesn't have that function as a time bound.)

So our recurrence is now
$$
T(n) = \Theta(1) + F(n) + \max\begin{cases}
 T(n/4) \\
 T(n-1) + T(1) \\
 T(n/4 + 1) + T(3n/4 - 1)
\end{cases}
$$
If $T$ is increasing, the first case is smaller than the other two, so we can ignore it.  So we have two possibilities to consider.

First, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n-1)
$$
(I folded the extra $T(1)$ into the $\Theta(1)$ term.)  This recurrence unrolls into a simple summation
$$
  T(n) = \Theta(n) + \sum_{i=1}^n F(i)
$$
which implies that $T(n)$ is convex no matter what function $F(n)$ is.  So this  recurrence seems to work.  (The apparently circular argument about convexity can be unwound into a boring and mechanical proof by induction, if you care.)

On the other hand, suppose
$$
  T(n) = \Theta(1) + F(n) + T(n/4 + 1) + T(3n/4 - 1).
$$
Then even with the very strong assumption that $F(n) = O(1)$, a quick recursion tree argument implies that $T(n) = \Theta(n)$.  The same recursion tree argument implies that if $F(n)$ is grows even slightly faster than a constant, then $T(n)$ is strictly convex, which means this is the wrong recurrence.

So this recurrence only works when $F(n) = O(1)$.  In that case, we can simplify the recurrence further to
$$
  T(n) = \Theta(1) + T(n/4 + 1) + T(3n/4 - 1).
$$
We still have those pesky off-by-ones in the recursive arguments, but whatever.  We've already figured out that $T(n) = \Theta(n)$, so who cares about the recurrence any more?


How to analyze/test a binary search algorithm?

First, of all, the worst-case running time of binary search is $\Theta(\log n)$. What you are looking for is the average running time of binary search under some reasonable random model, for example the element to be looked for is chosen uniformly at random from the (distinct) elements in the array.

Second, the average running time can't be $n + n/2 + n/4 + \cdots$, since the average running time is lower than the worst-case running time. I'm not sure what exactly you're counting here. The average running time is the average number of operations taken by your algorithm, on a random input. In contrast, the worst-case running time is the maximal number of operations taken by your algorithm on any input.

Perhaps the following example will make things clear. Consider the following task: given an array of size $2n$ containing $n$ zeros and $n$ ones, find the index of a zero. The worst-case running time of any algorithm is $\Omega(n)$. In contrast, consider the algorithm which scans the array from left to right, and returns the first zero index. Its worst-case running time is $\Theta(n)$. Under the assumptions that the input array is chosen randomly among all legal arrays, the average running time is $\Theta(1)$ (why?). You can modify the algorithm to one which probes locations randomly, and then the worst-case expected running time is $\Theta(1)$. (If you don't understand the last remark, wait until you learn about randomized algorithms.)

Finally, you're required to empirically demonstrate the claimed average running time $\Theta(f(n))$. The idea is that for large $n$, the average running time will be $\approx C f(n)$ for some constant $C$ whose units are seconds. In other words, $C$ is the constant "hidden" inside the big O notation. Suppose you calculate for several values of $n$ an average $T(n)$ over several runs of the algorithms. Then you expect $T(n)/f(n)$ to be roughly constant, and that would demonstrate your claim concerning the average running time.


Find cell neighbors of a given edge in a 2D grid

There's no need for any special algorithm.  There are only 12 edges, so it's enough to simply use a switch statement with 12 cases.  Or, you can use 12 if statements.  Any of these will have $O(1)$ running time, since there are only finitely many cases, so they are (asymptotically) as good as any other "algorithm".


Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed

Given a language $L$, $L$ is RE if there is a TM $M$ such that $L(M) = L$. $L(M)$ is the set of words which $M$ accepts and it must be equal to $L$; words not in $L$ must cause $M$ either to reject or to never halt. It is not sufficient for $L$ to be a subset of $L(M)$, which is why your reasoning is incorrect.

Given RE languages $A$ and $B$, what makes $A \setminus B$ not RE (in general) is not the problem of knowing whether the input is in $A$; since $A$ is RE, there is a TM $M_A$ which you can simulate to find out (and if $M_A$ does not halt, the input is not in $A$ and, hence, not in $A \setminus B$ too; so there is no need to halt at all). The problem is that, to accept an input $w$ which is not in $B$, you need to simulate the respective TM $M_B$ on $w$ and accept if $M_B$ does not halt; hence, you need to solve an instance of the complement of the halting problem, which is (famously) not in RE.


In this context, "coalescing" means eliminating variable-to-variable move operations in the register allocator by allocating those two variables to the same location, typically the same register.

It may not be obvious why you'd do this in the register allocator, as opposed to in an earlier optimisation like constant folding. The reason is that code generation might introduce loads and stores for convenience or optimisation purposes.

The way that register allocation is often presented, you generate an assignment of "variables" to "locations", where a location could be a register or spilled. That's a good mathematical model of the problem, but it's a bit more complicated than this in practice.

Look at live range splitting as one example. This is an optimisation where a variable is not held in the same place for its lifetime ("spilling" can be thought of as a special case). As a concrete example, consider the case of two nested loops with a variable that is used a lot in the inner loop:

x <- something();
for (outer loop) {
    some_computation();
    for (inner loop) {
        some_other_computation_involving(x);
    }
}
use(x);

It seems like we probably want to store x in a register in the inner loop, but we may not want to store it in a register in the outer loop, because that would tie up a register during some_computation. On the other hand, there may be enough registers to keep x in a register, depending on how allocation for some_computation works out.

One solution is to split the range of variable x into two:

x1 <- something();
for (outer loop) {
    some_computation();
    x2 <- x1;
    for (inner loop) {
        some_other_computation_involving(x2);
    }
    x1 <- x2;
}
use(x1);

That introduces two variable-to-variable moves. If we allocate x1 and x2 to different locations, we are essentially spilling x for some of its lifetime. But using a coalescing-aware allocator, we have the chance that the spill may never happen if the moves are coalesced.

Another interesting case is that of special-purpose registers and calling conventions. Suppose, for example, you are calling a function:

x <- f(p(), q());

We will also suppose that the calling convention for this architecture requires the first argument for the call to f to be in register r1 and the second argument to be in register r2. One way to do this is to generate code like this:

t1 <- p()
r2 <- q()
r1 <- t1
call f

Again we have introduced a variable-to-variable move. A coalescing-aware register allocator can then decide whether to "spill" t1 or to generate it directly in r1:

r1 <- p()
r2 <- q()
call f

I use the word "spill" advisedly here because it might also be appropriate it to "spill" it to another register:

r3 <- p()
r2 <- q()
r1 <- r3
call f

Since r1 plays an important role in the calling convention, it may be needed for computing q().

Callee-save/caller-save registers can also be implemented using this mechanism.


Strategy to create a testbed and gold standard

You can't.  You can't squeeze blood out of a stone.  If you want to evaluate how well your method will work on real documents, you need real documents.  With synthetically/artificially generated documents, you'll never know if they have the same characteristics as real documents.

You don't necessarily need a standard benchmark that others have used -- but you do need to assemble a representative set of real documents to evaluate on.  Basically, if there is no standard benchmark in your field, you'll have to assemble one yourself.

Yes, this is difficult to do.  This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, often we spend 80% of our time (or more!) just assembling data sets, and only 20% on the actual learning algorithms themselves.


Understanding a detail in the proof of bin packing approximation

We have $u = 1 - e$ where $u$ is used space and $e$ is empty space.

Since for at least $FF - 1$ bins we have $e < \delta$ (which you understand why), for those we also have $1- e > 1 - \delta$ or $u > 1-\delta$.

So in at least $FF - 1$ bins we use at least $1 - \delta$ space. Since each bin has maximum size $1$ we can also say that at least $FF - 1$ bins are at least $1 - \delta$ fraction full. In other words, we have at least $(FF - 1)(1 - \delta)$ bins worth of 'stuff', so that must be less than or equal to the optimal amount of bins we need to use (or else we'd have more stuff than that could fit).


How to show that $\log (n!) = \Omega(n\log n)$ using Stirling's approximation?

A function $f(n)$ is said be $\Omega(g(n))$ if there exist $c,n_0\gt 0$ such that $f(n)\ge cg(n)\ge 0$ for all $n\ge n_0$.

A function $f(n)$ is said be $\mathcal O(g(n))$ if there exist $c,n_0\gt 0$ such that $0\le f(n)\le cg(n)$ for all $n\ge n_0$.

Here,
$$\log_2(n!)=n\log_2 n-(\log_2 e)n+\mathcal O(\log_2 n)$$

Let $f(n)=\mathcal O(\log_2 n)$ such that
$$\log_2(n!)=n\log_2 n-(\log_2 e)n+f(n)$$

By definition, $f(n)\ge 0$.

Thus,
$$\begin{align}\log_2(n!)&\ge n\log_2 n-(\log_2 e)n\end{align}$$

We want to find some constants $c,n_0\gt0$ such that
$$n\log_2n-(\log_2e)n\ge cn\log_2 n$$
for all $n\ge n_0$, that is, it must satisfy,
$$(1-c)n\log_2n\ge (\log_2e)n$$
As $n\gt 0$, it must satisfy
$$(1-c)\log_2n\ge (\log_2e)$$
Note that
$$(1-c)\log_2n\ge(1-c)\log_2n_0$$
for all $n\ge n_0$.
So, we need a positive $c$ and a $n_0$ to satisfy
$$(1-c)\log_2n_0\ge (\log_2e)$$
This is easily possible, as the RHS is a constant and the LHS can be made large by choosing $n_0$ and $c$ appropriately. For instance, choosing $c=0.1$ and $n_0=4$ works.

Thus, by definition,
$$\log(n!)=\Omega(n\log n)$$


What is a graceful algorithm to generate this number sequence

I think the below algorithm should be workable. It doubles/triples/quadruples/quintuples/... what we've generated so far to find disallowed sequences. Then it generates all possible sequences by attaching a 0 and a 1 to every sequence found in the previous iteration and removes the disallowed sequences. Then it checks for rotations and removes those too.

First round, generate 1 and 0.

Second round, double these to 11 and 00. These are the strings that are not allowed in this round.

Find possible permutations. (1->{10,11} 0->{00,01}). Remove the disallowed ones we just figured out.

We now have 1, 0, 10, and 01. Find rotations: 10 and 01 are rotations, so remove them but leave one. Which? Let's say 01, as in the example.

Third round, we have 1, 0, 10. We're aiming for a three-digit sequence, and doubling the two-digit sequences would get us a four-digit sequence. Tripling 1 and 0 gets us 111 and 000, which we disallow.

Find possible permutations. (10->{100,101}). Nothing to remove.

We now have 1, 0, 10, 100, 101. Find rotations: no rotations.

Fourth round, we have 1, 0, 10, 100, 101. Aiming for four digits. We do doubling and quadrupling to get the disallowed four-digits sequences: 1111, 0000, 1010.

Find possible permutations. (100->{1000, 1001}, 101->{1010, 1011}). Remove disallowed 1010.

We have 1, 0, 10, 100, 101, 1000, 1001, 1011. Find rotations: no rotations.

One note about when you have to decide which rotations to keep: In the above example we had to decide between "10" and "01". Let's see how these sequences would develop:

10->100, 101

01->010, 011

100->1000, 1001

101->1010, _1011_

011->0110, _0111_

010->0100, 0101

Iterating "rotated sequences" produces rotations of what the other "rotated sequence" would have produced, so I believe it doesn't matter which rotation you keep.

Update: This seems to have something to do with Lyndon words (https://en.wikipedia.org/wiki/Lyndon_word). As I couldn't find a decent list of binary Lyndon words on the internet, I used the Python code I found here: https://gist.github.com/dvberkel/1950267 to generate some more.

I've modified it a bit to make it easier to use (removed one import and changed main function to immediately start generating binary Lyndon words). I've also added a small Perl script to check whether your words are Lyndon words: https://gist.github.com/qiqitori/31175ab58d099ac4ff7573f34e7344d5

Call the Python script using e.g. python lyndon_generator.py | head -n 1010

Call the Perl script using e.g. perl lyndon.pl

Here's what the Perl script outputs:

Found rotation 1 of 1 (1) at index 1
Found rotation 01 of 2 (10) at index 2
Found rotation 001 of 4 (100) at index 3
Found rotation 011 of 5 (101) at index 4
Found rotation 0001 of 8 (1000) at index 5
Found rotation 0011 of 9 (1001) at index 6
Found rotation 0111 of 11 (1011) at index 7
Found rotation 00001 of 16 (10000) at index 8
Found rotation 00011 of 17 (10001) at index 9
Found rotation 00111 of 19 (10011) at index 11
Found rotation 01011 of 21 (10101) at index 12
Found rotation 01111 of 23 (10111) at index 13
Found rotation 000001 of 32 (100000) at index 14
Found rotation 000011 of 33 (100001) at index 15
Found rotation 000111 of 35 (100011) at index 17
Found rotation 001011 of 37 (100101) at index 18
Found rotation 001111 of 39 (100111) at index 20
Found rotation 000101 of 40 (101000) at index 16
Found rotation 010111 of 46 (101110) at index 21

As we can see, index 10 and 19 are missing, but I would bet that the next two numbers in your sequence would be equivalent to index 10 and 19.


Show that the diameter of a MST is sometimes larger by a factor $\Omega(n)$ than the diameter of the graph $G$

You say that you don't understand how to show that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

However, it seems that what you don't understand is what it means that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

It is impossible to prove a theorem if you don't understand its statement.

Here is what you are asked to do. Given a weighted graph $G$, we will use the following notation:

$n(G)$ is the number of vertices in $G$.
$D(G)$ is the diameter of $G$.
$D_{MST}(G)$ is the minimum diameter of a minimum spanning tree of $G$.

  Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and $D_{MST}(G) = \Omega(n(G)) \cdot D(G)$.

It seems that you are not familiar with the notation $\Omega(\cdot)$. It is the counterpart of big O, and described in the answers to this question.

Unpacking the big $\Omega$ notation, we can rephrase the question:

  Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and there exists a constant $C>0$ such that $D_{MST}(G_i) \geq C n(G_i) D(G_i)$.

The question is somewhat ambiguous – it's not clear if you need to provide an example for every $n$ or just for infinitely many $n$. I assumed the latter, but in fact in your case there is a sequence $G_i$ with $n(G_i) = i$, so you can try proving this stronger statement instead.


Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

This answer on CSTheory describes a reduction from 0/1 subset-sum to the unbounded knapsack problem (UKP).  That does exactly what you want.  The intuition is that UKP is basically subset sum with multiplicities, since UKP lets you put as many copies of an item as you want into your knapsack.


Correctness of an algorithm difference between recursive and iteraive

A proof using a loop invariant is also a proof by induction – you prove that the invariant is indeed an invariant by induction. The reason that finding the inductive hypothesis is easier for recursive procedures is that we usually state the semantics of the recursive function – what it is supposed to compute – and this is the "loop invariant" we use to prove its correctness.

Let's consider the following two procedures for summing an array $A[1],\ldots,A[n]$:

  Iterative:

  $sum \gets 0$
  $i \gets 1$
  While $i \leq n$:

  $sum \gets sum + A[i]$
  $i \gets i + 1$

  Return $sum$

  Recursive:

  $Sum(A[1],\ldots,A[n])$

  If $n = 0$, Return $0$
  If $n > 0$, Return $Sum(A[1],\ldots,A[n-1]) + A[n]$

The loop invariant for the iterative algorithm is $sum = A[1] + \cdots + A[i-1]$. This is something we have to come up with. We prove that it holds by induction, and conclude that the function returns $A[1] + \cdots + A[n]$.

In contrast, it is clear what $Sum$ is supposed to compute: the sum of its input. We still need to argue inductively that $Sum$ works correctly, but the inductive hypothesis $$Sum(A[1],\ldots,A[i]) = A[1] + \cdots + A[i]$$ corresponds to the semantics of $Sum$.

We often attach a meaning to recursive procedures, but not so often to loops. If we did attach a semantic meaning to the $i$'th iteration, it would become easy to formulate the loop invariant. An example is the Floyd–Warshall algorithm (or rather, some of its implementations), where the $i$'th iteration computes the shortest path of length at most $i$.


Is there a theorem that says when an array of numbers can be searched faster than linearly?

In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).
However, if you know more about the structure of the array, there are plenty of things you can do.
For example, imagine the array has the following property: its elements are sorted increasingly up to a certain index $i$, and sorted decreasingly after that. Can you do faster than a linear search? Yes! You can still search elements in $O(\lg n)$.
What if I ask you to search in an array $A$ that is sorted increasingly except for $1$ element, which is out of place? (you don't know which element). You can still search in $O(\lg n)$, how :)?
What if the array $A$ holds the following property: when you divide it in chunks of size $\sqrt{n}$, say $A[0..\sqrt{n}-1], A[\sqrt{n}..2\sqrt{n}-1], \ldots, A[n-\sqrt{n}..n-1]$, then each of the chunks is sorted. Can you do faster than a linear search? Yes! if you do a binary search in each chunk, then you get complexity $O(\sqrt{n}\lg n)$.
What if you know the array $A$ has only two elements, $x$ and $y$, and they both appear the same number of times? Can you find an element in less than $n$ comparisons? Yes!
In general, there are many different kinds of informations you can have about an array that speed up search, and different forms of knowledge would have different impacts on how much you can speed up.


Just use a regular dictionary (also dynamic set) and attach a counter to each entry. The insert operation then finds already existing entries and can increase the counter; similarly for delete.

If you want to search the literature, some sources (e.g. Algorithms by R. Sedgewick and K. Wayne (2011, 4th ed)) call the abstract data structure for multi sets a bag. This notion seems to be used in practice as well.

Note that some implementations will assume that you assign data to keys, and that the same key can occur multiple times with different data. In this case, using a counter is not enough, so these may not directly do what you want (since they may not even bother to detect duplicate keys).


Computer networks - Can there be an out of order frames in a noiseless channel?

It depends on the channel and the assumptions you are making.  There may well be some communication channels where messages can be re-ordered but will not be dropped or lost or modified in transit.


Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

How about taking $L_1=L_2$? Then we will have both
$L_1 \cup L_2\leq_m\, L_1\cap L_2$ and $L_1 \cap L_2 \leq_m\, L_1 \cup L_2$.

If you want to have $L_1\not= L_2$, you just try $L_2=L_1\cup\{w\}$, where $w$ is a string not in $L_1$.

If you are determined to have infinity elements in both $L_1\setminus L_2$ and $L_2\setminus L_1$, try $L_1=L\cup aL$ and $L_2=L\cup bL$, where $L$ is an infinite language over $\Sigma$ and $a,b$ are two new symbols not in $\Sigma$.

By now, you should be able to see that there are lots of way to construct examples that satisfy the requirements.


Kolmogorov complexity of prefixes of computable sequences

Let $D$ be a decider for $A$, then in order to determine $\mathcal{X}_{A,n}$ it is enough to specify $n$ and an encoding of $D$. Given $D,n$, you can loop over all integers $i\in [n]$ and check whether or not $i\in A$ by simulating $D(i)$. Thus, the overall description of $\mathcal{X}_{A,n}$ consists of $n$, the encoding of $D$ and the encapsulating machine $M$ (described above) which uses $D,n$ to output $\mathcal{X}_{A,n}$. $n$ contributes at most $\log n$ bits to the description, and $D,M$ have some encoding of length $c$ independent of $n$, bounding the overall description length by $\log n + c$.


Determining if $G$ contains $K_4$ as a minor in polynomial time

I think your best bet would be to implement a treewidth 2 algorithm.  We implemented one for an android app and you can find the source code of this specific implementation here: Treewidth.  You can probably modify it to run in $O(n^4)$ time.


Selection of dates respecting delay constraints

This can be solved in polynomial time using dynamic programming.

We'll build up an array $A$.  The meaning of the array is as follows: if $t$ is a time on day $d$ and $i \in \{1,2,3,4,5\}$, then $A[t,i]=1$ means that it's possible to build a schedule for days $1..d$ that ends at time $t$ and obeys all the constraints (minimum delay $\ge$ 2 hours, maximum delay $\le$ 10 hours, exactly 5 times chosen on days $1..d-1$ and exactly $i$ times chosen on day $d$).

Note that, once you've filled in $A[1..t-1,1..5]$, you can fill in $A[t,1..5]$ via a simple recurrence relationship: e.g.,

$$A[t,1] = \lor_{t'} A[t',5]$$

where $t'$ ranges over all times that are on the day before $t$, and that fall at least 2 hours before and at most 10 hours before $t$; and

$$A[t,i] = \lor_{t''} A[t'',i-1] \text{ for } i=2,3,4,5$$

where $t''$ ranges over all times that are on the same day as $t$ but before $t$, and that fall at least 2 hours before and at most 10 hours before $t$.

Thus, you can fill in the array $A$ entry-by-entry, in order of increasing $t$.  This will give a linear-time algorithm for finding a valid schedule that meets your constraints.


Finding a correct regex for the strings with at least two $0s$

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.


What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$?

Since $c=m^{\frac{1}{m}}$ is a constant, your $T(n) = c^{n-1} \in \Theta(c^n)$ is simply exponential.


There is no decoding done in the fetch stage.  The fetch stage relies on the Branch Target Buffer (BTB) to tell it which instruction addresses have had taken branches in the past.

The BTB is a small highly associative structure.  It performs two functions.  First it tells you which instructions are and are not branches.  If the current program counter (PC) is in the BTB then the instruction pointed to by the PC is a branch, and the BTB will tell us the target of that branch and the branch predictor will give us a guess about whether the branch is taken or not taken.

If the current program counter in not in the BTB then either (a) the current instruction is not a branch or (b) we have never seen this instruction before (and don't know whether or not it is a branch, but we'll assume it is not or (c) the current instruction is a branch, but we've never seen the branch taken, so we've never put it in the BTB.

This last function (branches that are never taken are never put in the BTB) makes the BTB actually a very effective branch predictor.  Branches that have never been taken are unlikely to be taken in the future, and the BTB predicts this correctly.  Branches that have been taken at least once in the recent pass are slightly more likely than not to be taken in the future, and the BTB reflects this as well.

The BTB effect was rarely taken into account in academic branch predictor research done at the end of the 1990s (nor is it taken into account in the statistics in most textbooks).  For most programs on most architectures the BTB actually filters out a significant number of branches (on the order of 25%) because they are never taken or rarely taken.  For those 25% of branches you essentially get a 99% accurate branch prediction for free.  The "real" branch predictor needs focus, then, only on the other 75% of branches.


I don't know if there is a polynomial-time algorithm, but if your matrix is not too large, you could try approaching this with integer linear programming.  Define zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ means $j \in S_i$.  Then you have the constraints

$$\sum_{j} a_{ij} x_{ij} \ge 1.$$

Also, introduce zero-or-one variables $o_{pq}$, with the intended meaning that $o_{pq}=\Delta(S_p,S_q)$, and enforce that

$$o_{pq} = (x_{p1} \land x_{q1}) \lor \dots \lor (x_{pn} \land x_{qn})$$

using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP).  (In other words, you introduce fresh temporary zero-or-one variables $o'_{pqj}$ and add the constraints $o'_{pqj} \ge x_{pj} + x_{qj}-1$, $o'_{pqj} \le x_{pj}$, $o'_{pqj} \le x_{qj}$, $o_{pq} \le o'_{pq1} + \dots + o'_{pqn}$, $o_{pq} \ge o'_{pqj}$.)

Finally, minimize $\sum_{p<q} o_{pq}$, subject to the constraints above.  This is a set of linear inequalities over integer variables, so you can feed it to an off-the-shelf ILP solver and hope it finds you a good solution.  This algorithm will have exponential running time in the worst case, but ILP solvers incorporate many heuristics, so if the matrix is not too large, it's possible this might give you good results in a reasonable amount of time.


Using finite state machines for lexical analysis

The goal of any parser is to verify that a sequence of characters is a string in a specific language [C, Python, whatever].  In principle, the parser can be written to inspect each character in the sequence directly, but the parser will be more comprehensible and efficient if built to inspect higher-level lexical tokens - names, numbers, quoted-strings, miscellaneous operator symbols, parentheses, etc.  This is where the scanner comes in.  The scanner is essentially a subroutine which the parser calls to read the raw character stream and extract & return the next lexical token.

The scanner is implemented as a DFA which recognizes any token.  Each token type has its own structure as a character sub-sequence, representable as a regular expression which in turn is translated to a simple DFA; for example: a name is (in most languages) a sequence of characters consisting of [letter] followed by zero or more [letter or digit].  The scanner combines the simple DFAs for these expressions into a single DFA for their union.  This is (conceptually) implemented as a simple two-dimensional table, where rows are indexed by character values and columns are indexed by DFA state numbers (actually the rows are usually indexed by character classes - e.g 'letter' instead of 'a', 'b', ...).

Each call to the scanner follows this process: Begin in a common start state (e.g 0), looking at the next character [in the I/O buffer].  Using the lookup table, calculate the next state and 'consume' the next character [typically this means copying the character into the next slot in a buffer].  Repeat until a final state is reached, then return an object identifying the type of lexical token and the value from the buffer.  Example: Suppose the scanner is called when the next few characters are 'foo '.  The machine will move from state 0 to state (say) 11 and copy 'f' to the buffer; then move from state 11 back to state 11 and copy 'o' to the buffer - twice (two 'o'-s); then seeing the space it will move to some final state (say) 12, and return from the call, returning the object [type = NAME, value = 'foo'].  The next call to the scanner will begin where the last ended, looking at that space.

Most scanners do a bit more than this, of course.  In languages with reserved words, when the scanner finishes reading the name, it will typically look up the name in a table of reserved words; if found, it will return an object representing that specific reserved word instead of a generic 'name' object.  The scanner will usually 'eat' all contiguous whitespace without returning any token; similarly for comment text.  And so on and so forth....


Should all internal node keys in B+ tree also be in the leaves?

The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node.  Deleting the value from a leaf won't change any internal nodes, unless the leaf becomes underfilled.  With the insertion you list, it would have the property you are thinking of if there were no deletions.

On the other hand, it is possible that the author wasn't thinking of either the property you name, nor the possibility of deletions, when making the question, and just used 10, 20, 30 as easy separators.  For sure, I have written questions with mistakes before, and usually, even with a mistake in the question, it can usually be answered properly to see if the student understands the material (insertion in this case).  If a student then asked me what your post asks?  I would be pleased with their understanding of the material to notice this property.


Is there an implementation of higher kinded types in typed lambda calculus?

I doubt you find mainstream languages with HKTs simpler than Scala and
Haskell. And even those don't implement HKTs fully.
Tim Sheard's Ωmega   and
some interactive proof assistants have HKTs too.

Chapters 29 and 30 of   Types and Programming Languages
show exactly how HKTs are added to a typing-system and how to do type-checking with HKTs. Why not do it yourself, it's instructive!


Number of strings accepted by this regular expression

NOTE: I'm assuming + is the union operation, as used here, rather than the Kleene plus or a terminal symbol.

The first step is breaking this RE into three parts: (x+y)*, y, and (a+ab)*. Now consider, how many ways can we make something with less than four characters from each of these?

(x+y)*: one of length 0, two of length 1, four of length 2, eight of length 3
y: one of length 1
(a+ab)*: one of length 0, one of length 1, two of length 2 (aa, ab), three of length 3 (aaa, aab, aba)

Now, how could you combine these to get length 4?

0 from the first (1), 1 from the second (1), 3 from the third (3)
1 from the first (2), 1 from the second (1), 2 from the third (2)
2 from the first (4), 1 from the second (1), 1 from the third (1)
3 from the first (8), 1 from the second (1), 0 from the third (1)

For each of those, multiply the number of possibilities. Taking 1 from the first, 1 from the second, and 2 from the third, for instance, gives 2×1×2=4 possibilities.

The sum of these is the total number of length-4 strings matched by this RE: (1)(1)(3)+(2)(1)(2)+(4)(1)(1)+(8)(1)(1) = 3+4+4+8 = 19.