Improving Time Bound of this Algorithm past $O(n^2)$

Here is a hint. Suppose the sequence contains $n-1$ Xs and $n+1$ Ys, so that you need to change some Y to X. You can compute for each position $k \in [1,\ldots,2n]$ the number of Xs minus the number of Ys; let's call that a "report". Changing a Y to an X affects the report in a certain, easy to describe, way. On the other hand, whether a sequence is good corresponds to a very simple property of the report.

Putting everything together, you should get an $O(n)$ algorithm.


Modeling an inequality problem to a graph

You’re on the right track with your response to $c$. There’s a bunch of algorithms that solve $c$ and $d$ simultaneously. If you’re familiar with depth-first search, you can use that to solve the problem.

Another approach is what’s called “topological sort.” The key idea here is that if a directed graph has no cycles, then you can put the vertices in a line such that there are only edges that go from start vertex to an end vertex such that the end vertex is to the right of the start vertex. This is actually really easy to write an algorithm to do, give it some thought and see if you can’t come up with a clever trick.

The best case time for solving this problem is $O(|V|+|E|)$, and off the top of my head I can think of four algorithms that achieve that timing.


Help with proof involving weighted full binary tree

There are two basic induction patterns for (non-empty) full binary trees:

A tree is either a leaf or consists of a root and two full binary subtrees.
A tree is either a leaf or can be obtained from a smaller full binary tree by adding two children to a leaf.

Your first question can be proved in both ways. In both cases, the base case is clear: if a tree is a leaf then it has $n=1$ leaves and $n-1=0$ internal nodes.

According to the first way, if the tree $T$ is not a leaf then it has a root and two subtree $T_1,T_2$. By induction we know that if $T_1,T_2$ have $n_1,n_2$ leaves (respectively) then they have $n_1-1,n_2-1$ internal nodes (respectively), and together with the root, this gives $n_1+n_2-1$ internal nodes for $T$, which is exactly one less than the total number of leaves.

According to the second way, the tree $T$ is obtained from a smaller tree $T'$ by adding two children to a leaf. If $T'$ has $n'$ leaves and $n'-1$ internal nodes, then $T$ has $n'-1+2 = n'+1$ leaves and $n'-1+1 = n'$ internal nodes, exactly one less than the number of leaves.

Your other statement can also be proved in both ways. I leave you the details.


Advantage of MTZ problem formulation of TSP

The MTZ is not an algorithm.   Miller-Tucker-Zemlin formulation is a method of formulating the Travelling Salesman Problem as an instance of integer linear programming.  This lets you feed the resulting integer linear programming instance into an off-the-shelf solver for integer linear programming, and let the solver solve it for you.

Remember that an instance of integer linear programming is a set of variables and linear inequalities.  Lookup tables are not allowed; the inequalities have to be linear (e.g., $5x_1 + x_2 \le 7$, but not $T[x_1] \le 5$).  Therefore, using lookup tables are simply not an option, if you want to use integer linear programming.

Alternatively, you could skip using an integer linear programming solver at all, and try to solve the Travelling Salesman Problem from scratch.  But good luck with that.  It's an NP-complete problem, so it is unlikely you'll be able to find an efficient algorithm to solve the problem.  (And just saying "use lookup tables" is not an algorithm.)

Bottom line: I think you have a confusion about how integer linear programming works, and what MTZ is.  MTZ is not an algorithm for the TSP.  Rather, MTZ is a way of describing the TSP in a format that you can give to an integer linear programming solver.  Lookup tables aren't an option, if you're using an integer linear programming solver.


If you can find a PDA for the language $L_0 = \{ 0^i 1^j : i < j \}$, then you can probably find a PDA for your language as well, which is just $L_0^2$. Hence I suggest the following plan:

Figure out a PDA for $L_0$.
Figure out a general construction that, given PDAs for languages $L_1,L_2$, outputs a PDA for their concatenation $L_1 L_2$.
Apply the construction to the PDA you found in the first step.


How to write stack programs for arithmetic terms?

What you want to do is; either first translate the expression into something that is easier for a stack machine to handle (like reverse polish).

The other is to use a modified shunting yard algorithm which can handle parenthesis.

You have 2 stacks: a result stack that holds the numbers where you push the numbers as you encounter them;

and an operator stack that holds operators in decreasing priority order.

When you need to add a operator that is of lower precedence you pop from the operator stack. Then apply that operator to the top 2 values on the result stack and replace them with the result. A parenthesis is of lowest priority but is the only one that can go on top of a higher priority operator.

When you encounter a closing parenthesis you pop from the operator stack and apply to the result stack until you find a closing parenthesis which you pop.


Decidability of empty intersection of two languages accepted by Turing machines

It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M_1$ that accepts all inputs. $L(M_1)\cap L(M_2) = L(M_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.


Non-recursive (iterative) DFS with $O(n)$ size stack

You can keep only the topmost copy of a node on the stack:

dfs(source):
   s <- empty stack
   visited <- {}
   on_stack <- map<node,stack element>
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element <- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())

If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.


What is the name of this size method calculating the size of a node?

Remember that to get the actual value of size(t.left), you have to evaluate the method size at the node t.left, i.e. assuming t.left has left and right children the algorithm with call size((t.left).left) and size((t.left).right).


How to random-generate a graph with Pareto-Lognormal degree nodes?

To generate a graph from a prescribed degree sequence (regardless of the degree sequence), one can use an algorithm by Blitzstein and Diaconis:

"A sequential importance sampling algorithm for generating random graphs with prescribed degrees" by J. Blitzstein and P. Diaconis

Unfortunately their algorithm is potentially  $O(n^2 \bar{d})$, for $n$ vertices with average degree $\bar{d}$, so this might not be fast enough depending on the size of your graph and the application involved.

Molloy and Reed introduced the "Erased Configuration Model" which pairs vertices based on a degree sequence chosen proportional to the remaining free slots.

"A critical point for random graphs with a given degree sequence" by M. Molloy and B. Reed

A paper by Britton, Deijfen and Martin-Lof show that the Erased Configuration Model asymptotically approaches the prescribed degree distribution chosen.
While not guaranteeing the exact degree sequence input, I would recommend the erased configuration model for its simplicity and speed.

"Generating simple random graphs with prescribed degree distribution" by T. Britton, M. Deijfen and A. Martin-Lof

Briefly, the erased configuration model graph generation algorithm creates "hooks" for each vertex, where the number of hooks for each vertex is initially given by the degree sequence.  Going from the vertex with the most hooks first, another hook is chosen uniformly at random from the pool still unattached.  A connection is made for this pairing.  Once the pool of hooks is exhausted, self loops are removed and multi-edges are collapsed into one.

Since self loops are allowed and multi-edges collapsed, the resulting degree sequence could potentially be different than the input sequence, so this method is not exact.  If exactness is preferred, the algorithm by Blitzstein and Diaconus can be used at a higher computational cost.  Note that the algorithm of Blitzstein and Diaconus checks whether a prescribed degree sequence is feasible (or "graphical" in their parlance), so degree sequences might need to be regenerated should they not be realizable.

Degree sequences can be chosen under any distribution you want.  In your case, you would want to choose them based on a Pareto-Lognormal distribution.

I would also like to briefly note that generating graphs with prescribed degree sequences that follow a particular distribution, the Pareto-Lognormal distribution say, might not generate the type of "knowledge" graphs you want.  The degree distribution is just a profile of a graph and says nothing about other features which might be present in the original graph ensemble you would be trying to model.  As Raphael points out in the comments, Wikipedia's page on scale-free networks is a good starting point for some review.


You got the definition of $L^+$ wrong. It is not $L^* \setminus \{\epsilon\}$. Rather, it is
$$
L^+ = \bigcup_{n=1}^* L^n.
$$
You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore:

If $\epsilon \notin L$ then $L^+ = L^*\setminus\{\epsilon\}$.
If $\epsilon \in L$ then $L^+ = L^*$.


Algorithm to test a graph for $t$-transitivity

If you had an oracle from Graph Isomorphism, then for constant $t$ you can check whether a graph is $t$-transitive. For example, to check if a graph is $1$-transitive, for every vertex $i$ create a variant $G_i$ of your original graph by attaching an "appendage" at vertex $i$, say a very long path or a very large star. The graph is transitive if all $G_i,G_j$ are isomorphic.


Is it possible to design a Turing Machine without extra symbols for this language?

Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following:

If the current symbol is $\varepsilon$: accept
If the current symbol is $1$: reject
Delete the current symbol (by writing $\varepsilon$)
Move right until you find the next $\varepsilon$ symbol
Move left (the head is now on the last non-blank symbol, if any)
If the current symbol is $\varepsilon$: reject
If the current symbol is $0$: reject
Delete the current symbol (by writing $\varepsilon$)
Move left until you find the previous $\varepsilon$ symbol
Move right (the head is now on the first non-blank symbol, if any)
Repeat


The obvious algorithm is the greedy algorithm.  Each time you see a new element that's not part of an existing flow, you identify which output stream currently has lowest occupancy, and route that element to that output stream.  When you see an element that is part of an existing flow, you obviously have no freedom about where to route it; it has to go to the same output stream as the rest of the flow.

In an online setting where you must decide immediately where to route each element and where you have no information about the distribution of flow sizes or other domain knowledge, this is the natural strategy.  When you see the first element of a flow, you have no information about how large the flow will be, and you must decide immediately where to route it based only upon the current state of the output streams.  It's not clear whether there is any theoretical sense in which one can provably do better, if we have zero knowledge.

Now in practice I suspect you will typically have some a priori knowledge about the distribution of flow sizes.  In this case, you can do bit better.

For instance, suppose you knew that all flows were either mice (they have 1 element) or elephants (they have 1000 elements).  Then it would be easy to do better.  When you get a new element that's not part of an existing flow, look at the existing flows in the output streams.  For each existing flow in an output stream that has more than 1 element, you know exactly how many more elements are yet to be received in that flow, so you get a lower bound on how full that output stream will become once all of the remaining packets in the existing flows arrive (it is a lower bound since for the flows where you've only seen one packet you don't know yet whether they are mice or elephants).  Call this the degree to which that output stream is "committed".  Now you can use these lower bounds to pick which output stream is least committed, and route the new element to that output stream.

If you additionally know what fraction of flows are mice and what fraction are mice, instead of computing a lower bound you can compute an expected value and choose which output stream to route to by going for the choice where the expected value of the imbalance is minimized.

In general, you can use a greedy algorithm that uses expected output stream commitment as the basis for choosing an output stream.  Let the random variable $X$ be distributed according to the distribution on flow sizes, i.e., $X$ is a random variable that counts the number of elements in a randomly chosen flow.  Suppose you have seen $k$ elements in a particular flow, so far.  Then the conditional expectation $\mathbb{E}(X | X\ge k)$ is in some sense your "best guess" at what the total flow size will be; it is the expected flow size, given that the flow contains at least $k$ elements.  Thus, you can compute this for each active flow, and compute the sum of these values for each output stream, and route the new flow to the least-committed output stream.  If you know the distribution of $X$, you should be able to compute $\mathbb{E}(X | X\ge k)$ easily.

This algorithm is fairly simple and should be pretty efficient: it requires $O(1)$ state per active flow (a counter to keep track of the number of elements seen in that flow so far).  Assuming you can compute the conditional expectation in $O(1)$ time, the algorithm requires $O(1)$ time per element.

Whether this algorithm is sufficiently better than the simple greedy (choose the lightest output stream, based only upon its current size, not its expected commitment) in practice can only be answered by experimenting on some realistic data sets.


Are there well-specified formal languages that are not regular?

There are indeed well-specified formal languages that cannot be represented by regular expressions, even on a one-letter alphabet. Examples include $\{a^{n^2} \mid n > 0\}$ and $\{a^p \mid p \text{ is a prime number}\}$.


a) what are the advantages/disadvantages over each other?

According to the lecture note: Sections 17.4.1 and 17.4.3, we can summarize as follows:

The original Peterson’s Algorithm works with only 2 processes.
The Peterson's algorithm requires multi-writer registers while the Bakery algorithm uses only single-writer registers.
Both algorithms are starvation-free. Furthermore, the Bakery algorithm offers a strong near-FIFO guarantee.
Both algorithms work with atomic registers. However, the Bakery algorithm works with even weaker registers (safe registers actually, see here).
The Bakery algorithm uses unbounded registers. Nevertheless, this problem can be fixed.

  b)  If they already solve the critical section problem, why do we need semaphores?

A Semaphore is a generalization of mutual exclusion locks. Each Semaphore has a capacity, denoted by $c$ for brevity. Instead of allowing only one thread at a time into the critical section, a Semaphore allows at most $c$
threads, where the capacity $c$ is determined when the semaphore is initialized. (See the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit; Section 8.5).


There are actually two main types of approximation algorithms: those that return an approximate solution, and those that return the approximate value. In order to explain the difference, let me define the problem more formally. Below everything is stated for minimization problems. It is a simple exercise to generalize everything for maximization problems.

Let me stress that the definitions below are not standard; in fact, there is no standard agreed-upon definition. However, it can be taken as a formal definition without too many complaints from the community, if you find this kind of definition enlightening.

Definition: A minimization problem consists of a tuple $\mathcal{O},\mathcal{S},v$ such that:

$\mathcal{O}$ is the set of instances.
$\mathcal{S}$ is the set of solutions.
$v$ is a function from $\mathcal{O} \times \mathcal{S}$ to $\mathbb{R}_+ \cup \{\infty\}$ (the non-negative reals together with positive infinity) such that for every $o \in \mathcal{O}$ there exists $s \in \mathcal{S}$ such that $v(o,s) < \infty$.

We define $v^*(o) = \inf_{s \in \mathcal{S}} v(o,s)$.

The function $v$ is the value of the given solution for a given instance. The optimal value for the instance is $v^*(o)$. If $v(o,s) = \infty$ then we say that the solution is infeasible for the instance.

(Alternatively, we could have a function $f\colon \mathcal{O} \to 2^{\mathcal{S}} \setminus \{\emptyset\}$ giving the (non-empty) set of feasible solutions, and then $v$ is a partial function $\mathcal{O} \times \mathcal{S} \to \mathbb{R}_+$ such that $v(o,s)$ is defined iff $s \in f(o)$.)

Definition: An $\alpha$-approximation algorithm is an algorithm $A\colon \mathcal{O} \to \mathcal{S}$ that satisfies the following property:

  For all $o \in \mathcal{O}$, $v(o,A(o)) \leq \alpha v^*(o)$.

If $\alpha = 1$, then the algorithm finds an optimal solution.

We are usually interested in polynomial time approximation algorithms. In this case we have to fix an encoding for $\mathcal{O}$ and $\mathcal{S}$, that is, we should treat $\mathcal{O},\mathcal{S}$ not as abstract sets but rather as sets of strings.

Definition: A weak $\alpha$-approximation algorithm (non-standard terminology) is an algorithm $B\colon \mathcal{O} \to \mathbb{R}_+$ such that:

  For all $o \in \mathcal{O}$, $v^*(o) \leq B(o) \leq \alpha v^*(o)$.

Once again, we are usually interested in polynomial time algorithms. Given an $\alpha$-approximation algorithm $A$, we can construct a weak $\alpha$-approximation algorithm $B$ using $B(o) = v(o,A(o))$ (this works assuming $v$ is computable). In many specific case we can also go in the other direction.

In some cases (especially hardness of approximation proofs), when the phrase "$\alpha$-approximation algorithm" has the weaker meaning given in the latter definition.


How will broadcast behave with a certain capacity?

I assume you want to broadcast from A.

The fastest is probably to broadcast at 80 Mbps and the end of the broadcast is then at 200 seconds (3.33 minutes) for both B and C.

Broadcasting at 100 Mbps will prevent C for receiving your file, since your switch can't store the exceeding 400 MB.

But I don't understand where do your constraints come from? Would it be possible to make C and B communicate? Also I don't quite understand how you did your calculations.


It's the first one. Function application is left-associative.
$$FGa = (F G) a$$


Big O - Equivalence: "Standard" definition vs Limit definition

If $f = O(g)$ then there exists $C>0$ such that for large enough $n$, we have $f(n)/g(n) \leq C$. Hence under mild assumptions,
$$
f = O(g) \Longleftrightarrow \limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty.
$$
As Raphael mentions in a comment to your post, your definition is symmetric in $f,g$ and so is more appropriate for $\Theta$.


In Breadth-first search and depth-first search what is the purpose of visited flag

The gist of code in Java you see is NOT complete in the sense that it fails compilation miserably. In that sense, you are looking at an example that is incorrect, not pedagogical and misleading to beginners.

With that having been said, let me explain. The visited flag is used to prevent the function to visit the same node again. It is used in the calls to method getUnvisitedChildNode(Node myNode), whose definition is missing from the gist. Supposedly, that method will return a child node of myNode that is not visited whenever there is at least one such node. Otherwise that method will return null.

I recommend you to read ntroduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA, where BFS and DFS are explained clearly. It also has the complete code that contains the partial source code in your question.


Why do all non-empty ω-regular languages have periodic members?

Actually, it doesn't say that $q$ is an accepting state, though it should do!  $\mathrm{Inf}(r)$ is the set of states visited infinitely often during the run $r$.  The acceptance condition of Büchi automata is that $\mathrm{Inf}(r)$ contains an accepting state.

The correct proof is as follows, with explanation added. Note also that, while your title says that the automaton is deterministic, the proof applies to nondeterministic automata, too, since it talks about the existence of a run with a particular property, rather than saying that the unique run has that property.

Let $A$ be a Büchi automaton and let $s\in L^\omega(A)$. Since $A$ accepts $s$, there must be a run $r$ of $a$ on $s$ that has an accepting state $q\in \mathrm{Inf(r)}$ because a Büchi automaton accepts if, and only if, some accepting state is visited infintely often. Let $s_0$ be any prefix of $s$ such that $A$ is in state $q$ after reading $s_0$.  Since $r$ visits $q$ infinitely often, it must return to $q$ when processing $s$, say after processing the prefix $s_0s_1$.  In particular, if the automaton is in state $q$ and reads string $s_1$, there is a run in which it returns to $q$. Therefore, the automaton has a run that visits $q$ infinitely often when processing the string $s_0\,{s_1}^\omega = s_0s_1s_1s_1\dots$.


The term that I was taught (thanks, Dragon Book!) is "induction variable". It refers to any variable which is a linear function of the number of iterations in a loop.

I don't know the term "loop variable", but if I had to guess, it would refer to a variable whose value changes inside the loop, and which is tested to decide the loop termination condition.

But to be honest, it would depend what you were trying to use it for. Pick whatever definition helps your analysis.


In computational complexity, we usually think of SAT as a decision problem: given a CNF, decide whether there is a truth assignment that satisfies it. There is also a search version of SAT: given a CNF, either find a satisfying assignment, or state that the formula is unsatisfiable. SAT solvers consider a third version: given a CNF, either find a satisfying assignment, or a proof that the formula is unsatisfiable.

There are several relations between the various versions. First, if you solve the decision version, you can also solve the search version. The idea is to find the lexicographically smallest satisfying assignment. Assuming that the variables are $x_1,\ldots,x_n$, we first substitute $x_1=0$ and check whether the resulting formula is still satisfiable. If so, we continue on to $x_2$. Otherwise, we substitute $x_1 = 1$ (the formula must remain satisfiable) and continue on to $x_2$. After $n-1$ more such steps we uncover a satisfying assignment.

Another relation is that if you can solve the search version that you can also solve the SAT solver version. The idea is that if the algorithm for the search version states that the CNF is unsatisfiable, then the transcript of the algorithm serves as proof that the CNF is indeed unsatisfiable. So these two versions are essentially equivalent.


All prefixes with same length as their suffix is a regular language

Given a DFA $A$ for $L$, construct an NFA which operates as follows:

The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
The NFA will maintain two states, $q_1,q_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ (which corresponds to a symbol in $y$), and advance $q_1$ using $\sigma$ and $q_2$ using $\tau$.
The NFA is at an accepting case if $q_1 = q$ and $q_2$ is an accepting state of $A$.


Why are complex numbers needed to define qubits?

You can run any standard quantum algorithm on a real-amplitude quantum computer with one additional qubit and only constant-factor slowdown (or perhaps linear-factor slowdown considering loss of parallelism) by replacing each $a{+}bi$ in your unitary matrices by $\big(\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}\big)$. Likewise, you can simulate a quaternionic quantum computer on a standard quantum computer with one additional qubit by replacing $a{+}bi{+}cj{+}dk$ with $\big(\begin{smallmatrix}a+bi&-c+di\\c+di&a-bi\end{smallmatrix}\big)$. So these models are all polynomially equivalent.
I doubt that there's a good non-physical argument for the appearance of complex numbers. In physics they're related to the duality between zeroth and first derivatives of position in harmonic oscillation (the same reason that complex numbers are used in modeling AC circuits), and that duality doesn't exist in the discrete quantum circuit model. Another argument from physics is that in Lagrangian QM the amplitude of a transition is $\int e^{iS(γ)} \, \mathrm dγ$ (where $γ$ ranges over "histories"), and there doesn't seem to be anything you can sensibly replace $i$ with in the real case. But this model, where each history contributes an amplitude with the same absolute value but a different phase, only works because of cancellation of nearby histories, and there aren't any "nearby" histories in the quantum circuit model.


Proof that fast broadcasts have to target larger cycles first

Let $b_0$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_0$ and $b_1$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_1$.

Remark that since $C_0$ and $C_1$ are cycles the fastest way to broad cast is for $v$ to broadcast first one of his neighbor and then the other.

Since $C_0$ and $C_1$ are only connected by $v$ and $v$ already have the information we know that spreading the information through $C_i$ will not improve the minimal broadcasting time for $C_{1-i}$.

3 cases (first one developed the others just ideas):

$b_0>=b_1+2$ (hence $|C_1|>|C_2|+3$) if $v$ start broadcasting his two neighbor in $C_0$ and then those of $C_1$. The time the information reach the last vertex in $C_0$ will be $b_0$ and the last vertex in $C_1$ $b_1+2$ hence $b_0$ in total. And you can't do better by definition of $b_0$
$b_0=b_1+1$ if you start twice by $1$ you will do at best $b_0+2$ and you do better by choosing $0$
$b_0=b_1$ it doesn't really matter but if the parity of the two cycle is different you may want to start by the odd one (or even not sure :D)


Equivalence of machine $M$ in $BPP$ and $EXP$

You are confused about the definition of when a language is in a class. You show that a language $L\subseteq \{0,1\}^\ast$ is in $P$, for example, by describing a Turing Machine with the following properties:

It is deterministic
It runs in polynomial time
It solves $L$

The classes $BPP$ and $EXP$ have similar definitions. The Complexity Zoo has a (very long) list of all the complexity classes.

The proof you cite works by following the definition of $EXP$ very closely: to show that $L\in EXP$, it describes a Turing Machine which (1) is deterministic, (2) runs in exponential time and (3) solves $L$. Showing this is relatively straightforward: it simulates the random machine for all possible random seeds, counts how many of those computations accept and how many reject, and then acts accordingly. This new algorithm satisfies the three properties above: we now know that there is a Turing Machine which is deterministic, runs in exponential time, and solves $L$. Now the proof is done. $\square$

The confusion may be that you do not need an equivalent machine (one that is also random, or that also sometimes errs, etc.), you only need to look closely at the definition of $EXP$ (which again, you can find in The Zoo), and then show that $L$ satisfies all the requirements. Also, $BPP$ is a class of languages, not of machines. Consider for example the complexity class $Sparse$, which consists of all languages that have a certain density, but which are not necessarily computable by any Turing Machine; the definition is not at all tied to the notion of computation.


Find distinct groups with no common parents

arr[] can be considered a partial order, and the groups you're looking for are then called antichains. So, you're looking for a decomposition into a minimum number of antichains of the partial order represented by arr[]. According to Mirsky's theorem, the smallest achievable number of antichains is equal to the length of the longest chain -- that is, the longest path of descendants in the forest (set of trees) represented by arr[]. (It's impossible to do better than this, since every element in this longest chain needs to be assigned to a distinct antichain.)
That Wikipedia page also describes a neat way to actually construct an optimal set of antichains, based on the idea that if two elements have the same number of ancestors, neither of them can be an ancestor of the other. In short: Perform BFS on the forest defined by arr[], starting from all root elements (you can do this by initially inserting all such elements into the queue); every layer (set of nodes at the same depth) constitutes one antichain.


How can I prove the correctness of this exponentiation algorithm using induction?

$Exp(0) = 1 = 2^0$ is trivially correct (hard coded) by the algorithm.
Assume the algorithm holds for values of $n$ up to $k$. Now consider the algorithm for input $n = k+1$. We compute $Exp(n) = Exp(k+1)$ using the algorithm:
In the case that $n = k+1$ is even:
The algorithm computes $temp = Exp(\frac{k+1}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k+1}{2}}$ because we assumed the algorithm is correct for values up to $k$ [1]. The algorithm correctly returns $temp*temp = 2^{\frac{k+1}{2}}*2^{\frac{k+1}{2}} = 2^{k+1}$.
In the case that $n = k+1$ is uneven:
The algorithm computes $temp = Exp(\frac{n-1}{2}) = Exp(\frac{k+1-1}{2}) = Exp(\frac{k}{2})$. After this step $temp$ holds the correct value for $2^{\frac{k}{2}}$ because we assumed the algorithm is correct for values up to $k$ [1]. The algorithm correctly returns $temp*temp*2 = 2^{\frac{k}{2}}*2^{\frac{k}{2}}*2 = 2^{k+1}$.
i.e. since $Exp(0) = 1$ is trivially correct by the algorithm and we showed that the algorithm is correct for $Exp(n+1)$ if $Exp(n)$ is correct; it follows that the algorithm is correct for every $n \geq 0$.
[1] Technically you also have to show that $\frac{k+1}{2} \leq k$ and $\frac{k}{2} \leq k$ for every $k > 0$ but that seems easy enough to prove.


You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants.

Consider the following example: $f_i(n) = i\cdot n$ for all integers $i$ and $n$. Then, for any integer $i$, $f_i(n) \in O(n)$.

If you are not careful, you could end up writing something like:
$$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n O(n) = O(\sum_{i=1}^n n) = O(n^2).$$
And get $O(n^2)$. But this is totally wrong!

If you do the computation without the asymptotic notation, you get:
$$\sum_{i=1}^n f_i(n) = \sum_{i=1}^n i\cdot n = n\sum_{i=1}^n i = n\frac{n(n+1)}{2} = \frac{n^2(n+1)}{2}.$$
And this is not in $O(n^2)$, as it is in $\Theta(n^3)$.

Now some authors define $\sum_{i=1}^n O(n)$ as meaning that the hidden constants are the same for every $O$ and in this case you can sum things together. But this is not always the case so I recommend not using $O$ notation with variable-length sums (as well as when doing induction, where similar problems appear).


Relationship between formal system and formal languages

Generally speaking, a formal system is comprised of

a language distinguishing its well-formed formulas from those strings over that are not well-formed
some kind of semantics that says which formulas are true and which are not
axioms and inference rules which attempt to generate, computationally, exactly those formulas which are true given the semantics.

We can specify the language of well-formed formulas using a grammar, but a grammar is not itself a formal system.


Examples of logic gates using non-standard models

Picture hanging can realize any monotonone boolean function.

I.e., you can hang a picture using two pins so that it falls IFF both pins are removed. This is trivial to achieve, and realizes an AND gate.

However, you can also hang it so that it falls IFF either pin is removed. Implementing this OR gate is not so trivial at first.

See the linked paper for nice pictures.


Examples for incomparable semi-decidable but undecidable languages

Some undecidable r.e. sets are isomorphic to the halting problem, for example the halting problem itself. Others are not, for example the one constructed by Friedberg and Muchnik using the priority method, a complicated kind of diagonalization. This set is not easy to describe, though one could argue that its description is "explicit". For some references, check out the Wikipedia article on simple sets, or any lecture notes on recursion theory.


Language whose intersection with a CFL is always a CFL (2)

Just a few notes (I'll try to add the proofs later).

Intersection-resilience seems closed under homomorphism.

A necessary condition for intersection-resilience is that for all homomorphisms $\varphi : \Sigma \to \Sigma \cup\ \{\epsilon \}$; $\varphi(L) \cap x^*y^*x^*$ must be a regular language (where $x$ and $y$ are any two distinct symbols of $\Sigma$).

So the result of Ginsburg and Spanier seems "tight" (if we use the same homomorphism trick).


Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$, Show that $L\notin RE$

Hint: Let $L_{\Sigma^*}$ the language of descriptions of Turing machines halting on all inputs. Choose some computable surjective mapping from $\Sigma^+$ to $\Sigma^*$, and use it to reduce $L_{\Sigma^*}$ to $L$. Since $L_{\Sigma^*}$ is neither RE nor coRE, it follows that the same holds for $L$.


What are the main ideas used in a Fenwick tree?

A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array.

Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on top of the array. Furthermore, label all the left edges in this tree with a "0" and all the right edges with a "1". We get something like this:

This is the so called Fenwick tree (or binary indexed tree). As can be seen, all the leaf nodes are indexed by a 4-digit binary number from 0000 till 1111 (left to right). Don't worry about this indexing for the time being. Now suppose that every leaf node contains the numeric value of its mapped array element and that every non-leaf node contains the sum of its two children. This means that the root node of the tree will contain the sum of the whole array. Also the left(right) child of the root will contain the sum of the left(right) half of the array and so on and so forth.

Up till this point we haven't really done anything special apart from storing partial sums. What we really want to do is to use these partial sums to compute cumulative sums in the array. We can do this for example by carefully selecting some nodes and returning their sum. This poses the question: Is there a strategic way to mark some nodes of the index tree that allows efficient cumulative sum calculations? It turns out that there is and this is the main idea behind Fenwick trees.

Before describing this marking, we first elaborate on the concept of uniform arcs. A uniform arc in a binary indexed tree is a directed path from any leaf to any other leaf situated to its left such that the labels on this path have the form: "00...011...1" (read from left to right). We can also assume the existence of a uniform arc from every leaf node to itself (with a length of 0). For example, the uniform arc connecting the fourth leaf to the first has a label of "0011". See the following figure for some illustrative examples of uniform arcs.

Now comes the crucial idea of Fenwick trees. The marking that allows us efficient computation of cumulative sums is obtained by coloring the middle node of the largest uniform arc emanating from every leaf node. This marking is illustrated in the following figure:

The nodes coloured in red are the so called responsibility nodes. This is due to the fact that each red node is responsible for maintaining the sum of values of all leaf nodes beneath it. Note that there are 16 responsible nodes and the whole tree can be implemented using a single array of the same size of the original array and here is when the binary indexing becomes handy. The yellow nodes are not needed and are used here only for pedagogical purposes. Note that all non-leaf responsible nodes have indexes length < 4 bits. We can restore the 4 bit length by padding successive "1"s to the right of the corresponding index. After applying the padding, the indexes of all responsible nodes fit nicely into a single array. See the following figure:

All we have to do now is figure out a way to compute (or update) the cumulative sum for every leaf node as follows:

A- To read the cumulative sum at a leaf, we first prepend a "0" and append a "1" to its index then we use the "flipping" technique as follows. Starting from the right most bit we first note the first "1" to "0" transition then flip all "1"s to "0"s one at a time. The sum of the found responsible nodes is then returned. The following examples illustrate this technique: (note: node "" is the root)

leaf "1010", becomes "010101" =>  responsible nodes: {"1010", "100", "0"}

leaf "1011", becomes "010111" =>  responsible nodes: {"10", "0"}

leaf "0111", becomes "001111" =>  responsible nodes: {"0"}

leaf "1111", becomes "011111" =>  responsible nodes: {""}

B- To update a value, trace all responsible nodes from the leaf to the root and update them accordingly. The tracing is done by prepending and appending a "0" to the index of the leaf and then successively noting all "0" to "0" and "1" to "0" transitions in the resulting index starting from rightmost bit. The following examples illustrate this technique: (note: node "" is the root)

leaf "1000", becomes "010000" =>  responsible nodes: {"1000", "100", "10", ""}

leaf "1111", becomes "011110" =>  responsible nodes: {""}

leaf "0100", becomes "001000" =>  responsible nodes: {"0100", "010", "0", ""}

leaf "0000", becomes "000000" =>  responsible nodes: {"0000", "000", "00", "0", ""}

You can verify the above examples by direct visual inspection of the third figure. A detailed explanation of Fenwick trees can be found at BIT: What is the intuition behind a binary indexed tree and how was it thought about? and https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/. Hopefully by now reading the mentioned sources will be much easier.


Asymptotically, $\log n$ and $\lfloor \log n \rfloor$ (or $\lceil \log n \rceil$) are the same: a function is $\Theta(\log n)$ iff it is $\Theta(\lfloor \log n \rfloor)$. Therefore there is no need for floor or ceiling.


find the minimum number of vertices in a directed graph from which the other vertices are reachable

The problem can be reduced to finding "sources" (opposite of "sinks", nodes with in-degree zero) in the graph. Suppose there is an optimal solution in which $B$ is one of the chosen nodes and there is an edge $A\rightarrow B$. Then we can put $A$ instead of $B$ in the solution and still cover the whole graph ($A$ can reach $B$, so it can reach all the nodes reachable from $B$). On the other hand, "sources" have to be chosen because they are not reachable from any other node. Then we should repeatedly find "source" nodes, chose them and mark all the vertices reachable from them as covered.

If there are no "source" nodes, then the graph must have cycles. All the nodes in a cycle are equivalent in terms of the nodes they can reach. Thus, they can be simplified into a "supernode". If eventually the supernode becomes a "source" and hence chosen by the algorithm, that means an arbitrary node of the cycle can be chosen.

So the algorithm repeatedly performs iterations of "finding source nodes" and "simplification" until the whole graph is covered.


Finding MST for connected graph with $|E|=|V|+87$

The "Cycle Property" helps (If you don't know it before, try to prove it first):

  Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$.

You are encouraged to answer the following questions:

How to identify a cycle and then a heaviest edge $e$ in it?
What to do with the edge $e$?
How many times should you apply the cycle property?
When to stop?

Then analyze the time complexity.


Subset of numbers whose XOR has least Hamming weight

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.


Does the Kleene star distribute over each element? (0+1)* = 0* + 1*?


Counting the number of permutations of string with given repeated interwoven subsequence

It's possible to count the number of such strings in something like $O(2^{n})$ time.  This is faster than generating all permutations (as $n! \sim 2^{n \log n + O(n)}$), but it's still not polynomial time.  I don't know if the number of such strings can be counted in polynomial time.
Here's how to do it.  You can build a NFA that accepts all such strings of length $2n$, and only such strings.  The NFA will have $O(n^2)$ states and be acyclic: it has $2n$ levels, and each level has $\le n$ states in it, and each transition goes from one level to the next level.  Each state in the NFA is of the form $(i,j)$, representing that we've already consumed the first $i$ characters of the first copy of $S$ and the first $j$ characters of the second copy of $S$.
So now the task reduces to counting the number of strings accepted by this (acyclic) NFA.  Unfortunately, counting the number of strings accepted by an (acyclic) NFA is #P-complete in the general case, so there's no polynomial-time algorithm that works for all (acyclic) NFAs.  (This doesn't rule out the possibility of a specialized algorithm that somehow takes advantage of the special structure of this particular NFA, but personally, I don't see any way to construct such an algorithm.)
That said, there are two techniques that are available here:

We can count the number of strings accepted by this NFA in exponential time.  First, convert the NFA to a DFA via the product construction.  You obtain an acyclic DFA with at most $2n \times 2^n$ states.  Since this DFA is acyclic, you can then count the number of words accepted by it in time linear in the number of states using dynamic programming.  Therefore, the total running time will be something like $O(n \cdot 2^n)$.
See also https://cstheory.stackexchange.com/q/8200/5038.

Alternatively, you can compute an approximation to the number of such strings, much more efficiently -- but the approximation will be rather inexact.  See Counting the number of words accepted by an acyclic NFA for details of how to do that.

I don't know if there are better techniques for your problem, or if there's any method to solve your problem in polynomial time.


Algorithm to test whether a language is context-free

By Rice's theorem, to see if the language accepted by a Turing machine has any non-trivial property (here: being context free) is not decidable. So you would have to restrict the power of your recognizing machinery (or description) to make it not Turing complete to hope for an answer.

For some language descriptions the answer is trivial: If it is by regular expressions, it is regular, thus context free. If it is by context free grammars, ditto.


Does location transparency imply access transparency?

There is certainly a strong dependency between these two properties and many examples will point to this conclusion. Think about an API that needs to use the same operations to access both local and remote files. If you already have a list of files, you are unaware of their physical location (e.g., some URL) since you retrieved these files or how they were retrieved (e.g., ftp?). It should imply that you used the same means to retrieve that list of files. But this is not entirely true. Let's simplify Wikipedia's definition:

Access transparency - enables resources to be accessed using identical operations.

Location transparency - enables resources to be accessed without knowledge of their physical or network location.

This 2 forms of transparency are necessary since they refer to 2 different architectural layers. The access transparency refers to the application layer, whereas location transparency refers to the physical layer.
Returning to the initial example, you access the list of files using the API, but you are not entirely sure how that list was retrieved or where those files were located before they were retrieved.


Given a maze, check if set of points is forming some-type of closed shape

Label open space in same way you label the x's, if a set of x's touches more than one label it contains a closed space.


Is this adjustment to an rms calculation valid?

You're looking to compute the rolling standard deviation (i.e., a streaming/online algorithm for the standard deviation).  The standard method is to use Welford's method, or a variation.
For the standard deviation, see https://jonisalonen.com/2014/efficient-and-accurate-rolling-standard-deviation/.  This is a minor adjustment to Welford's method (which computes the running variance) to reflect that you want the standard deviation rather than the variance.  See also https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance.


Is it NP-hard to fill up bins with minimum moves?

Some background.  The above problem is the knapsack problem with restrictions.  The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard.  For some variations, see https://en.wikipedia.org/wiki/Knapsack_problem#Definition.  The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter.  The problem is then restricted to the amount of time it takes to put the items in the knapsack.  The original problem requires the most valuable items to be placed in as short amount of time possible.  Another restriction with this version is that the weights and all other arguments are integers.  And the restriction of interest is that the weights $w_j$ divide $w_{j+1}$ for all $j$.  Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem.  This problem uses integers that divide evenly (no rational solutions).  Perhaps see What's the big deal with the knapsack problem?.

The main question perhaps should be "is this problem still NP-Hard when $w_j$ is unbounded by a polynomial corresponding to $i$, as the problem is less complex (in P) when it is bounded?  The reason I say this is because the problem can be shown to be in P when $w_j$ is bounded and NP-Hard when $w_j$ does not necessarily divide $w_{j+1}$ evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions.  These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below).  Additionally, because $w_j$ divides $w_{j+1}$, $w_j$ increases in size exponentially for each $j$.  This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of $w_j$, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when $w_j$ divides $w_{j+1}$ for all $j$.  And this is easily observed.

Example 1: let $n = 1$ and $w_p$ be powers of two.  Because of constant two, the entire problem is solved in quadratic time, as your example shows.  The weights are not random and therefore the calculation is solved efficiently.

Example 2: let $w_{j+1}$ be defined as $w_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$.  This is applicable, as $w_j$ divides $w_{j+1}$ for all $j$.  We get each $w_j$ is the product of all the primes up to $j$.  The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$.  Since there is a bound ($p_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let $w_{j+1}$ be defined as $w_j * R_p$, where $R_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$.  This is applicable to this problem, as $w_j$ divides $w_{j+1}$ for all $j$.  We get the first 5 quotients (randomly falling from two to infinity), as $101, 2657, 7, 3169, 2$.  We see that even at the 5th ball, the weight has eleven digits.  Fortunately, the fifth quotient was two and not a prime in the order of $10^{100}$ or larger.

Example three above is what happens when $w_j$ is not bounded (random weights) by a polynomial corresponding to $i$.  The time complexity is exponential, NP-Hard.  For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.


Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

Insufficient mixing between incorporating blocks of the key radically increases the possibility of collisions - as an example, imagine a hash like the following -

uint32_t badHash(std::vector<uint8_t> key) {
  uint32_t hash = 0;
  for (size_t i = 0; i < key.size(); i++) {
    hash += key[i];
  }
  hash = SomeFunctionWithPerfectAvalanche(hash);
  return hash;
}

Despite the final avalanche, this function is no better than a checksum at producing a good distribution - it is trivially easy for adjacent blocks to cancel each other out. The situation isn't much improved by multiplying the key block by a prime, or performing any other mix to the key block - I can instantly generate collisions by taking two keys that collide under a simple checksum and then applying the inverse of the per-key-block mix to each block of the colliding pair.

A strong hash function has to perform enough mixing between adjacent blocks to ensure that small changes in the key are overwhelmingly unlikely to cancel each other out. Balancing the amount of work done in mixing each key block and in mixing the hash between key blocks is the tricky part of making a fast and robust hash function.

-Austin, author of MurmurHash


Your problem is NP-hard. Given an instance $T_1,\ldots,T_n$ of Maximum Coverage, let $x_1,\ldots,x_n$ be new variables, and create an instance $S_1,\ldots,S_n$ of your problem, where $S_i = T_i \cup \{x_i\}$. We have
$$
\left| \bigcup_{i \in I} S_i \right| -|I| = \left| \bigcup_{i \in I} T_i \right|.
$$
On the positive side, consider the following greedy algorithm: $I_0 = \emptyset$, and for $k = 1,\ldots,n$, $I_k$ is obtained from $I_{k-1}$ by adding the set which maximizes the total number of elements covered by sets in $I_k$. It is known that for $k \in \{0,\ldots,n\}$, the set $I_k$ found by the greedy algorithm has the following property: for all sets $J_k$ of size $k$ we have
$$
\left| \bigcup_{i \in I_k} S_i \right|  \geq
(1-1/e) \left| \bigcup_{i \in J_k} S_i \right|.
$$
In particular, if the optimal solution to your problem has size $k$ and objective value $O$, then
$$
\left| \bigcup_{i \in I_k} S_i \right| \geq (1-1/e)(O + k),
$$
and so
$$
\left| \bigcup_{i \in I_k} S_i \right| - k \geq (1-1/e) O - k/e.
$$
The minimal optimal $k$ satisfies $O \geq k$ (each set adds at least one new element), and so $(1-1/e) O - k/e \geq (1-2/e) O$. This shows that the greedy algorithm (more explicitly, finding $k$ which maximizes $|I_k|-k$) gives a $1-2/e$ approximation to your problem (this can probably be improved).


Meaning of the constants that appear in the Master Theorem

That is not the general formula for time complexity. There is no "general formula  for time complexity", any more than there is a "general formula for the answer."

Rather, the formula you give is a recurrence relation that can be used to compute the running time of certain divide-and-conquer–style recursive algorithms.  Specifically, it corresponds to a recursive function which, when given an input of size $n$, makes $a$ recursive calls, each on inputs of size $n/c$. If you pretended that the recursive calls were "free" (i.e., that they returned their answer in one computation step), then the algorithm would take $bn^k$ steps.


Procedure to automatically solve field theorems in a SMT solver

All of the theorems you want to prove (except uniqueAddNeutral) are of the form $\forall x . \phi(x)$ where $\phi(x)$ is quantifier-free.  Herbrandization is typically the first step towards proving those theorems: replace $x$ with an arbitrary constant $c$, with no assumptions made about $x$, and prove $\phi(c)$ holds without making any assumptions about $c$.

The theorems you want to prove are simple enough that exhaustive search over candidate proof trees might suffice to find a proof.  At each step, you apply one of the axioms, instantiating the universally-quantified variables in the axiom with appropriately chosen values.  You have to choose which axiom to apply and how to instantiate the variables; typically you instantiate each variable in the axiom with one of the subexpressions in the current expression/goal, so there are only finitely many choices at each step, and you can simply exhaustively search over all possibilities (up to a given size/depth).


Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

Your question is easy to answer. Take your grammar, and add the following rules:
$$
\begin{align*}
&S \to T \mid \mathit{Expr} \\
&T \to \mathit{Expr}
\end{align*}
$$

Your particular grammar, however, does seem unambiguous.

Here is how I would try to prove it. First, show the expressions are self-delimiting: no expression is a prefix of another one.

Now, when trying to parse an expression, you can determine which rule should be applied first by looking at the first symbol. In the interesting cases, you then have to partition the input into two expressions. The self-delimiting property should make this possible in a unique way.


Such a tree would be 2-colored.

Note that all trees are 2-colorable; a 2-colored tree is just one where the coloring's already happened.


Time Complexity analysis for Map-Reduce model

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

  Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.


Difference between fixed-to-variable length codes and variable-to-fixed length codes?

A fixed-to-variable length code is a code that takes a string in $\cal X^*$, partitions it into chunks of fixed length $n$, and replaces each chunk $w$ by some codeword $C(w)$ whose length isn't fixed. The classical example is prefix codes. A prefix code such as Huffman's code replaces each symbol $\sigma \in \cal X$ by a codeword $C(\sigma)$, with the aim of minimizing $\mathbb{E}[|C(\sigma)|]$ with respect to some distribution on $\cal X$. We can obtain a better rate by applying Huffman coding on $k$-tuples of inputs. This corresponds to a fixed-to-variable length code that encodes each word $w$ of fixed length $k$ by a codeword $C(k)$.

A variable-to-fixed length code is a code that takes a string in $\cal X^*$, breaks it into pieces of variable length, and replaces each piece into a word of fixed length. The classical example is Lempel-Ziv encoding with fixed dictionary size. Lempel-Ziv breaks its input into chunks, where each chunk extends a word in the dictionary by one symbol. Each chunk is then encoded as an index into the dictionary together with the new symbol. The encoding thus has fixed length, but the chunks vary in length.


Unrecognizability of functional variant of halting problem

A Turing machine $T$ decides the halting problem if on input $\langle M,w \rangle$:

If $M$ halts on $w$, then $T$ halts and outputs "Yes".
If $M$ does not halt on $w$, then $T$ halts and outputs "No".

In order to show that $L$ is not recognizable, you assume that $L$ is recognizable, and use that to construct a Turing machine $T$ which decides the halting problem. This is not quite what you are doing:

You are assuming that $L_0,L_1$ are recognizable, but you don't explain how this follows from $L$ being recognizable.
You don't explain why $M_{\cup}$ always halts. This is only the case if you run $M_0$ and $M_1$ in parallel, and halt whenever one of them halts.
You state that $M_{\cup}$ always accepts and halts whether $M$ halts on $w$ or not. However, such a machine is easy to construct: all you need to do is to immediately halt, without even reading the input. What we need is that $M_{\cup}$ halts with a different answer depending on whether $M$ halts on $w$ or not.

Moving forward, for $\overline{L}$, you express $\overline{L}$ as the intersection of a non-recognizable language and a recognizable language, and conclude that $\overline{L}$ is not recognizable. Unfortunately, this step is invalid. For example, the empty language is the intersection of a non-recognizable language of your choice and the empty language, which is recognizable; yet the empty language is recognizable.
Instead, you need an argument very similar to the one you use for $L$ itself.


Your language is not regular, since
$$
L \cap a^*bc^* = \{ a^n b c^m : n \neq m \}.
$$
I'll let you figure out why.


Counterexample to this modified Dijkstra's

Your algorithm makes the wrong choice between the following two paths:

5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.
A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.


I'll start with an intuitive explanation as to why $B$ is decidable. Given input $x$, we can start trying every possible witness $y$ and check whether the verifier $V$ accepts $(x,y)$. This is a semi-algorithm, since it doesn't necessarily halt.

However, we note that since $V$ has exponential running time, then considering witnesses that are "too long", i.e. so long that $V$ won't be able to read all the witness, is irrelevant. So we can in fact stop after a bounded number of witnesses, which makes our procedure a halting algorithm.

Now let's formalize this.

Let's assume that the language $B$ has a verifier $V$ that runs in time $f(n)$ for some function $f$ (in your question, $f$ is an exponential function, but this is not important). A crucial property of $f$ is that it's computable. That is, given $n$ we can compute $f(n)$. It is easy to see that functions such as polynomials and exponentials are computable.

Since $V$ is a verifier for $B$, then we have can write the following:
$$B=\{x: \exists y \text{ such that } (x,y)\in L(V)\}$$
where $V$ has the property that given input $(x,y)$, $V$ halts in time at most $f(|x|)$.

We now make the following key observation: if $V$ accepts $(x,y)$ for some $y$, then there exists $y'$ such that $|y'|\le f(|x|)$ such that $V$ accepts $(x,y')$. That is, if there is a witness, then there is also a "short" witness.

This observation is correct since if $y>f(|x|)$ then $V$ cannot read more than $f(|x|)$ letters of $y$, so it's enough to consider a prefix of $y$.

From this it is easy to see why the procedure we described above works.


In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

You cannot force the guesses in any way.

That said, in your case you can emulate a witness of this form. Let’s first replace your $n$ with $m$, reserving $n$ for the input length. Suppose that your algorithm runs in time $t(n)$. Then you can only go through the first $t(n)$ guesses, so without loss of generality you can assume that $m \leq t(n)$. Since $t(n)$ is polynomial, $\log t(n) = O(\log n)$, and so you have enough space on the tape to store $m$. You therefore proceed as follows:

Guess $m$ (by guessing $\log t(n)$ bits).
Simulate the guesses $a^mb^mc^md^m$ using a counter that goes up to $m$ and another one that goes up to 4.


How can we prove that an enumerable/decidable group of languages is closed under an operation?

Here is a similar example, with the minority operator: the minority of three languages $A,B,C$ consists of words belonging to at most 1 of $A,B,C$.

If $A,B,C$ are decidable then so is their minority. Indeed, given a word $w$, first determine whether $w$ belongs to $A$, to $B$, and to $C$. You can do this since $A,B,C$ are decidable. Depending on this data, either accept or reject $w$. This is an algorithm deciding the minority.

If $A,B,C$ are enumerable, then their minority need not be so. Indeed, let $A$ be a language which is enumerable but not co-enumerable (for example, the set of halting programs). The minority of $A,A,A$ consists of all words not in $A$, i.e., the complement of $A$. By assumption $A$ is not co-enumerable, so the minority of $A,A,A$ is not enumerable.


Numerical stability of linear interpolation

"Numerical stability" is a much vaguer term than most people realise. We typically use it when referring to an approximation method, such as some kind of linear analysis, or numeric quadrature, or solving (possibly partial) differential equations. It refers to the property that given some appropriate assumptions (e.g. the inputs are reasonable), the algorithms converges to the ideal solution reasonably, even in the presence of floating-point error.

That's actually not what you're referring to here. However, there is a good answer to the question that you are trying to ask. If x is between 0 and 1 inclusive (and this is an important proviso; it's called "interpolate" but could be used to extrapolate), then interpolate_b is better.

In any sensible system of floating point (e.g. IEEE-754), you can assume several things:

Multiplying a finite number by zero returns a zero.
Multiplying a finite number by one returns that number.
Adding zero to any finite number returns that number.
For any finite number x, x - x returns a zero.

Standard provisos: Inf is not a finite number. NaN is not a number at all. Negative zero is a thing.

The negative zero thing is occasionally relevant, so when I say "returns a zero", or "returns that number" when that number happens to be zero, do be aware that you may get a zero of the opposite sign that you might expect under some circumstances. The exact rules are complicated, and we won't go into them here.

Still, it's more correct to say, for example, that if x is a finite number which is not zero, then x+0 and x+(-0) are both identical to x. If x is zero, then x+0 and x+(-0) may not be identical, and may not be identical to x, but they will differ from x by at most a sign bit.

First, consider the case where x is zero (and neither y nor z are negative zero). Then both interpolate_a and interpolate_b return exactly y. So far, so good.

Now consider the case where x is exactly 1. Then interpolate_a returns y + (z - y), because the multiply by x is a no-op. This may not be exactly equal to z due to round-off error. (Exercise: Find two single-precision IEEE-754 numbers which have this property in the default rounding mode.)

However, if you follow through the logic above, you can see that if x is exactly 1 (and neither y nor z are negative zero) then interpolate_b returns exactly z.

It's almost always considered a desirable property of any interpolate function that they return exact values at the endpoints. It's this property that makes interpolate_b a better choice.


References are highly appreciated.

An author is expected to address the question of the context and relevance of his results at the begin of his publication. I just skimmed over the introduction of "L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984." again, and found out that Valiant indeed well covered your question.

The original paper by Valiant is both freely available and not too difficult to read. (Except section 7, which only proves that the author can also tackle challenging mathematical problems, but doesn't contribute much to the real content of the paper.) Reading at least its introduction will be more rewarding than reading my overly long answer to this question, so I suggest to really try it.

The rest of this answer tries to cite some passages from the introduction which should indicate whether reading this introduction might answer the question about the historical context. Note however that an author has the natural prerogative to be biased with respect to such questions.

  ... such a system would, at least, be a very good start. First, when one examines the most famous examples of systems that embody preprogrammed knowledge, namely, expert systems such as DENDRAL and MYCIN, essentially no logical notation beyond the propositional calculus is used.

This is interesting information for the context, because propositional calculus is significantly weaker than predicative calculus or the various systems of type theory sometimes used today. (Strange enough though, Prolog (1972) and ML (1973) were among others intended as meta-languages for "such" expert systems, and seem to go beyond simple propositional logic as far as I can see. Also, the relational model (1969) for database management is claimed to be based on predicate logic.)

  Perhaps the main technical discovery contained in the paper is that with this probabilistic notion of learning highly convergent learning is possible for whole classes of Boolean functions. This appears to distinguish this approach from more traditional ones where learning is seen as a process of "inducing" some general rule from information that is insufficient for a reliable deduction to be made.

I fully agree here. It is important to be able to explain how your solution is able to solve a given problem, and in which sense it is a solution. Otherwise, you just end up with "no-free lunch" theorems which don't allow you to distinguish a buggy implementation of a dubious heuristic from a correct implementation of an appropriate heuristic.

  In summary, this paper attempts to explore the limits of what is learnable as allowed by algorithmic complexity. The results are distinguishable from the diverse body of previous work on learning because they attempt to reconcile the three properties ((1)-(3)) mentioned earlier. Closest in rigor to our approach is the inductive inference literature [...]. There is a large body of work on pattern recognition and classification, using statistical and other tools [...]. Learning, in various less formal senses, has been studied widely as a branch of artificial intelligence.

The properties ((1)-(3)) were that (1) "the machines can provably learn whole characterizable classes of concepts" which are (2) "appropriate and nontrivial for general-purpose knowledge" and (3) "the computational process requires only a feasible (i.e., polynomial) number of steps".


If the numbers are all integers at most $k$, then you can apply a fast algorithm for substring matching with don't-care symbols (see below) to solve the problem in $O(kn(\log m + \log k))$ time by applying the following transformation:

Map each text character $t$ to $t-1$ zeros followed by a 1.
Map each pattern character $p$ to $p-1$ don't-care symbols followed by a 1, and also prepend a 1 to the overall pattern.

Basically, 1s represent "boundaries" in both strings, and we look for a way to make each boundary in the pattern line up with some boundary in the text.

This paper describes an $O(n+m+\alpha)$-time algorithm, where $\alpha$ is "the total number of occurrences of the subpatterns" (I didn't read the full paper, so I'm not sure exactly what that means).  In any case it mentions the 1974 algorithm of Fischer and Paterson, "String matching and other products", which solves the problem in $O(n\log m\log \Sigma)$ time -- though that link is behind a paywall, googling should find other information on it.


Is this case of weighted 2SAT NP-complete?

You can express the predicate "$x = y$" using one occurrence of each polarity:
$$
(x \lor \lnot y) \land (\lnot x \lor y).
$$
Consider now an instance of weighted 2SAT, in which each variable appears at most $M$ times. Duplicate each variable $M$ times, and enforce that all copies are the same using the gadget above. Replace each occurrence of each variable by a distinct copy of the variable. If the original instance asks for an assignment with at most $k$ positive variables, ask for at most $Mk$ positive variables. We obtain an instance of your problem which is equivalent to the original problem.

This shows that your problem is also NP-complete.


Online algorithms and changing past decisions

Every problem where the online algorithm is optimal, i.e. has competitive ratio 1, is a (trivial) example. Such algorithms exist, for example for some scheduling problems.


Classification accuracy based on top 3 most likely classifications

This is called top-3 accuracy.  See https://stats.stackexchange.com/q/95391/2921, https://stackoverflow.com/q/37668902/781723, https://stats.stackexchange.com/q/156471/2921.  Sure, you can use it.  Whether top-1 accuracy or top-3 accuracy is better correlated with user satisfaction will depend on your particular application and on your users.


Is it possible that $\mathsf{L} = \mathsf{NP}$?

$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$

From space hierarchy and time hierarchy theorems we can prove that

$L \subsetneq PSPACE$

$NL \subsetneq NPSPACE$

Note that we know $PSPACE = NPSPACE$.

$P \subsetneq EXP$

$NP \subsetneq NEXP$

Note that we don't know if $EXP \subsetneq NEXP$.

Whether the other inclusions are strict, are still open problems. Even though there are no proofs, many, but not all, believe most of the inclusions to be strict.


Prove the following language is regular using closures

To get you started, consider a restricted version of your languge:
$$
L'=\{ab\mid a\in L_1, b\in L_2\}
$$
Notice that $L$ is the concatenation $L'=L_1\circ L_2$. Can you carry on from there?


Why finding the difference between the adjacent elements of the array to find the maximum difference?

Suppose that the original array is $a_1,\ldots,a_n$. The new array is $b_i = a_{i+1} - a_i$ for $1 \leq i \leq n-1$. Note that
$$
a_j - a_i = b_i + \cdots + b_{j-1}.
$$
Hence
$$
\max_{\substack{i < j \\ a_i < a_j}} |a_j-a_i| = \max_{i<j} (a_j-a_i) = \max_{i<j} b_i + \cdots + b_{j-1}.
$$


Can I find a clique with more than 2 nodes in a bipartite graph?

A graph is bipartite if and only if it is 2-colorable. A clique of size at least 3 contains a triangle, and a triangle $K_3$ clearly cannot be colored with 2 colors. It follows we can't find a triangle in a bipartite graph, so the corresponding decision problem is very easy for a bipartite graph.


Let me answer your questions in order:

By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for any $C$.  An algorithm whose running time is $O((n/\epsilon)^C)$ is better than an algorithm whose running time is only guaranteed to be $O(n^C e^{D/\epsilon})$, since the dependency on $\epsilon$ is better for the first algorithm. Furthermore, for any $E$, we can find an $1+1/n^E$-approximation in polynomial time using the first algorithm but not using the second (at least not with the given guarantee).
A problem in which an $1+\epsilon$-approximation can be found in time $(n+1/\epsilon)^3$ is definitely in PTAS, since for every $\epsilon$ this is $O(n^3)$ (exercise) and so polynomial in $n$.
What the authors meant here is that since an NP-hard optimization problem can't be solved exactly in polynomial time, the best we can hope for is for it to be $\epsilon$-approximable in polynomial time, and furthermore with a good dependence on $\epsilon$. Among the common complexity classes, FPTAS gives the strongest guarantee on the dependence on $\epsilon$. But in practice we sometimes get an even better guarantee: the running time is polynomial in $n$ and in $\log(1/\epsilon)$. So it's not strictly true that FPTAS is the strongest possible result; it's only the strongest possible result among the options PTAS,FPTAS,P. If we made up a new class LPTAS (corresponding to time polynomial in $n$ and in $\log(1/\epsilon)$), then that would be a stronger guarantee.
Given an NP-hard optimization problem, it can't be solved exactly in polynomial time; the best one can hope for is to approximate it efficiently. Some problems are NP-hard to approximate to some constant $C>1$. For others, it is possible to approximate the problem arbitrarily well in polynomial time, and these problems have a PTAS and so belong to the class PTAS. It might be that a $1+\epsilon$-approximation takes time proportional to $e^{1/\epsilon}$, and so we can only apply this efficiently for constant $\epsilon$. If the problem has an FPTAS (and so belongs to the class FPTAS), then we know that the dependency on $\epsilon$ is only polynomial, and so we can approximate efficiently to within $1+1/n^C$ for any $C$.


Overflow rule in two's complement arithmetic

Yes, if we are talking about integers. In two's complement representation with length $n$ you can only represent the integers between $-2^{n-1}$ and $2^{n-1} - 1$ (both bounds inclusive). Thus, the addition operation is not the same as the one over the integers—it is not even a proper operation because of overflows, which are left undefined; since it is a completely different operation, other rules apply (as I expect to have been previously mentioned in the book's text).
Do not mistake "overflow" for the result having a 1 carry at the left end. In example (b), for instance, the result of addition has such a carry, but it is truncated back to 4 bits, hence producing a correct result; the same happens in (d). However, an overflow occurs in both (e) and (f) because then the result is outside the representation range for 4-bit two's complement, that is, between $-2^{4-1} = -8$ and $2^{4-1} - 1 = 7$.


Counting permutations whose elements are not exactly their index ± M

The first thing I would ask when given this question would be

  Do you want a polynomial time algorithm?

and then I'd hope the answer is 'no'. I suspect that this problem is NP-hard, for the following reason:

The natural approach to this problem is to consider the placement of the first number and derive a recursive formula to place the others. This works nicely for the $M=0$ case (i.e. counting the number of derangements), as it doesn't matter on what position you have placed the first number, since there is only one 'illegal' position of every number. In other words, this approach leads to independent subproblems.

For $M>0$, this is not so simple, as we now can have $2$ illegal positions for some numbers. Which of these positions remain in the subproblem is now relevant to the solution of the subproblem. Only considering the number of 'illegal' positions is not sufficient, as the 'chains' of numbers that share an illegal position are required to determine the structure of the subproblems of that subproblem. So, this approach essentially leads to the following subproblem:

  Given a set $A \subseteq \mathbb{N}$, a set $B \subseteq \mathbb{N}$ both of size at most $N$ and a natural number $M$, count the number of perfect matchings on the bipartite graph $(A,B,E)$, where $(a,b)\in E$ if and only if $|a-b|\neq M$.

This problem looks hard. The only approach to this problem I see is inclusion/exclusion, which will not lead to a polynomial time algorithm.

We can consider approaches that do not rely on the iterative placement of the numbers, but I have no clue how you would do this. (especially during an interview!)

Of course, all this is mere speculation and it is still possible that a clever trick can give a polynomial time solution, but I hope I have made convincing argument that this trick has to be very clever indeed.

Perhaps it is possible to show NP-hardness by reducing this problem to #2-SAT (the 'chains' of numbers that share illegal positions seem a non-trivial choice that could be matched with the selection of a truth-value), but I haven't seen an obvious way to do that as of now.

In case the interviewer would actually be satisfied with an exponential time algorithm, I'd simply generate all possible solutions by adapting a recursive backtracking algorithm to generate a permutation to exclude this particular case.


is there an example of an algorithm that has O(1/n)?

As the complexity of an algorithm is a measure of the number of operations (in a sense to be defined in each context) needed to do some computation in function of the size of some input, sub-constant complexity does not make any sense. With your exemple, $O(\frac1n)$, it means that for a sufficiently large input, the algorithm does strictly less than one operation, which in terms of Turing machines means that the initial state is accepting, which means that the corresponding Turing machine does not output anything.

Edit: I had not seen the quantum computing reference, so my answer might not be total, although I doubt it makes sense even in that context.


We can model the transition of one move to another using the following discrete dynamics:

\begin{align}
m_{n+1} &= u_{n}
\end{align}

where $m_{n}$ is the $n^{th}$ move you performed and $u_{n}$ is the $n^{th}$ choice of the next move you will make. Note that both $m_n$ and $u_n$ are members of the move set, $\mathcal{M}$. The cost function you wish to maximize might then be of the form:

\begin{align}
V &= P_{M}(m_{K+1}) + \sum_{j=1}^{K} P_{M}(m_j) + P_{T}(m_j,u_j)
\end{align}

where $P_{M}(\cdot)$ gives you points for your current move and $P_{T}(\cdot, \cdot)$ gives you points from the transition from $m_j$ to $u_j$. Given this formulation, you can then recursively find an optimal policy, $\mu^{*}_{j}(m)$, that will generate optimal sequences given some move at step $n$ of the sequence. This can be found via:

\begin{align}
V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\end{align}

Once you have found the optimal policy $\mu^{*}_{j}(m)$, you can obtain an optimal dance move sequence from some dummy starting move using the following:

\begin{align}
m_{n+1} &= \mu^{*}_{n}(m_{n})
\end{align}

In this case, $\lbrace m_2, m_3, \cdots, m_{K+1}\rbrace$ would be your optimal set of $K$ moves. Now as we can tell from the recursive algorithm, we would essentially have three nested loops to obtain the optimal policy. These nested loops together are $O(KN^2)$ because we loop through all $m$ and $u$ (both of size $\left| \mathcal{M}\right| = N$) at a given step for $K$ steps. Generating the optimal sequence is then just $K$ steps, but the recursive algorithm is the dominant part of the algorithm computationally.

Simplified Explanation

So in the explanation above, we defined the dynamics to obtain the next move $m_{n+1}$ based on information we know, like the current move $m_n$ and the choice of what move to make next, $u_n$. We also defined a cost function to maximize, $V$.

To solve this problem using Dynamic Programming, we treat the cost function as a reward for a discrete trajectory and try to find optimal sub-trajectories, starting from the end of the sequence. The logic behind this is we can incrementally solve the optimal trajectory by using previously found optimal sub-trajectories.

We can define the final cost trajectory term as:

\begin{align}
V^{*}_{K+1}(m_{K+1}) &= P_{M}(m_{K+1})
\end{align}

where $m_{K+1}$ is within the set of moves, $\mathcal{M}$. We can define this term because it is independent of the decision variable, $u$, which is what we are trying to find an optimal algorithmic strategy to choose. Now the recursive relationship for the next piece of the cost trajectory is:

\begin{align}
V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(m_{K+1})
\end{align}

where $u$ can be any move within $\mathcal{M}$. Note how this equation depends on the value for $m_{K+1}$. This dependence is where you incorporate your knowledge of the dynamics. We know based on the discrete dynamics that this cost term can be redefined as:

\begin{align}
V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(u)
\end{align}

Our goal now is to find the optimal value of $V_{K}(m_K)$, for each value of $m_K$ within $\mathcal{M}$, with respect to $u$. This is simply written as:

\begin{align}
V^{*}_{K}(m_K) &= \min_{u \in \mathcal{M}} V_{K}(m_K, u)
\end{align}

Note that we also define the optimal value of $u$ for a given step $j$ and a given state $m$ as the optimal policy $\mu^{*}_j(m)$. We can use the above findings to thus define a recursive formulation to find the optimal cost:

\begin{align}
V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\
\end{align}

Note that $j$ should start at $K$ and be decremented down to $1$. Implementing this algorithm becomes a series of nested loops. This can be shown in pseudo-code to be the following:

for m in {Set of Moves}
  V_opt(K+1,m) = P_m(m)
end

for j going from K to 1, increment -1
  for m in {Set of Moves}
    // initialize V_opt(j,m)
    V_opt(j,m) = -Infinity

    for u in {Set of Moves}
      points = P_m(m) + P_t(m,u) + V_opt(j+1,u)
      if( V_opt(j,m) < points )
        V_opt(j,m) = points
        policy_opt(j,m) = u
      end
    end // end for loop u
  end // end for loop m
end // end for loop j

After finding the optimal policy $\mu^{*}_j(m)$ (policy_opt(j,m) in code), you can generate the optimal moves using the dynamics as noted previously. As you can see looking at the pseudo-code, the algorithm uses 3 nested loops, two of size $N$ and one of size $K$. This makes the problem dominated by a computational complexity of $O(KN^2)$.


What advantages does Block Programming Environment have over High Level Programming Language

Developing complex software is completely different from writing small programs.

Complex individual systems are usually elements of complex ecosystems of software and hardware platforms, interfaces, languages, and even extra-computational factors. In creating those kinds of systems the choice of languages that use visual metaphors would probably be detrimental, not beneficial, and that is why professional software developers are happy that the languages they use are "spartan".

On the other hand, if your intention is to reduce the learning curve for begginers that are not going to be professional developers of any kind, then you can begin to talk about the benefits of those "soft" languages.


Can polynomial many-to-one reduction be done to a specific problem instance?

The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if the original problem was an accepting instance, or the rejecting instance if the original problem was a rejecting instance.

That said, the Berman–Hartmanis conjecture states that all NP-complete problems are polynomial time isomorphic, meaning that there is a bijective polynomial-time many-one reduction between them with a polynomial-time inverse. This is currently an unproven conjecture, and only refers to NP-complete problems.


How to find middle element of linked list in one pass?

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.

Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.


Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

The paper A New Approach to
Dynamic All Pairs Shortest Paths by Camil Demetrescu and Giuseppe F. Italiano gives a solution to the directed version of the problem.

It involves saving two priority queues at each position on the matrix and updating and extracting information from these queues as edges are added. The psuedocode for the algorithm is on page 9 of the link.

For undirected graphs like this one, you could add 2 edges for each edge, one in each direction. This will not affect the time complexity of the algorithm.


Why are floats converted from different integers sometimes equal?

"float" and "int" in Java both use 32 bits. "float" can represent some numbers that "int" can't, like 0.5. Since 32 bits let you store exactly $2^{32}$ different values, it should be obvious that there must be "int" values that you cannot store in a "float".

"float" in Java, and "float" in many other language implementations, uses one bit for the sign, 8 bits for an exponent, and 23 bits plus one implicit bit for the mantissa. As numbers get bigger, the distance from one "float" to the next gets bigger. The 23 bit mantissa lets you store exactly the integers in the range $2^{23}≤x<2^{24}$, all the even integers in the range $2^{24}≤x<2^{25}$, all multiples of four in the range $2^{25}≤x<2^{26}$ etc.


Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$

Let $A = \sum_{i=1}^n A_i$. We have
$$
\begin{align*}
A^3 &= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i < j < k} A_i A_j A_k \\ &=
\sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i < j < k} A_i A_j A_k.
\end{align*}
$$
This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that every symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B_d := \sum_{i=1}^n A_i^d$. For example,
$$
\sum_{i<j<k} A_i A_j A_k = \frac{B_1^3+2B_3-3B_1B_2}{6}.
$$


Does the amount of symbols a turing machine has affect what computations it can perform?

Hint: can you express more integers by writing them in a bigger base?

I'll go with the definition where the blank is counted as a symbol. A Turing machine must have at least one non-blank symbol, i.e. at least two symbols. With 0 symbols there's no way to build a tape, and with only the blank symbol there's a single possible tape so the machine is effectively a finite automaton.

Any $n$-symbol Turing machine can be translated to a Turing machine with the symbols $\{0,1\}$ where $0$ is the blank symbol. Let $k$ be an integer such as $2^k \ge n$, and number the symbols from $0$ to $n-1$, with the blank symbol numbered $0$. Translate the tape by mapping each symbol to the sequence of $k$ symbols that is the representation of its number in base $2$.

The state set increases. For each original state $q$, we define several types of states in the new machine:

Forward read states $(\mathsf{R},q,i,x)$ where $0 \le i \le k-2$ and $x \le 2^i$: read the bits that represent one original input symbol, remembering the position $i$ and the partial accumulated number. These states have a right transition to either $(\mathsf{R},q,i+1,2x)$ or $(\mathsf{R},q,i+1,2x+1)$ depending on the symbol read from the new tape.
Decision states $(\mathsf{R},q,k-1,x)$: if there is a transition $\delta(q,x) = (q',x',d)$ in the original machine, then transition to a write state $(\mathsf{W},q',d,k-1,x')$. If the state $q$ is final in the original machine, this state is final in the new machine.
Write states $(\mathsf{W},q',d,i,x')$ where $1 \le i \le k-1$ and $x' \le 2^i$: write the low-order bit of $x'$ to the tape and move left to $(\mathsf{W},q',d,i-1,\lfloor x'/2 \rfloor)$.
Last-bit write states $(\mathsf{W},q',d,0,x')$ where $x' \in \{0,1\}$: write $x'$ to the tape, and move to a fast-forward state or a fast-backward state depending on $d$.
Fast-forward and fast-backward states $(\mathsf{F},q',d,i)$ where $0 \le i \le k-1$: keep moving in the same direction and decrement $i$ until it reaches $0$, at which point, switch to the corresponding forward read state. These states are used to either skip forward to the beginning of the part of the tape that represents the next original symbol after a right transition in the original tape, or to skip backward to the beginning of the part of the tape that represents the previous original symbol after a left transition in the original tape.

In summary, we make three passes over each symbol: one to read it, one to write the new symbol, and one to reposition the tape.

The details are tedious but not difficult.


More a tip than an answer, but it should get you to the solution:

Try to produce a word with 3 terminal symbols. Can you find more than one syntax tree for the same word?


Complexity class (P/NP) variants of Hamiltonian paths problems

Problem A is not a decision problem. This means that by definition it is not NP-complete.

Problem B is NP-complete. But every NP-complete problem is NP-hard.

Let me remind you the definitions.

NP-complete problem. Problem P is said to be NP-complete if it is in NP and every problem in NP can be reduced in polynomial time to P.

NP-hard problem. Problem P is said to be NP-hard if every problem in NP can be reduced in polynomial time into P.


What would be the practical consequences of ZPP=exptime

If ZPP = EXPTIME then NP $\subseteq$ ZPP, which implies NP $\subseteq$ BPP.  As described in Russell Impagliazzo's informal paper "A personal view of average-case complexity", we would be living in a world he calls Algorithmica.

Algorithmica is the world in which $P = NP$ or some moral equivalent, e.g. $NP \subseteq BPP$. [...]
Such a method of automatically producing a solution for a problem from the method of recognizing a valid solution would revolutionize computer science. Seemingly intractable algorithmic problems would become trivial. Almost any type of optimization problem would be easy and automatic; for example, VLSI design would no longer use heuristics, but could instead produce exactly optimal layouts for problems once a criterion for optimality was given. Programming languages would not need to involve instructions on how the computation should be performed. Instead, one would just specify the properties that a desired output should have in relation to the input.

And so on.  Read the paper for more extrapolation on this topic, along with the consequences of less fantastic algorithmic complexity conjectures being true.  And observe @Dmitry's caveat: Knowing a problem is in a tractable complexity class isn't the same as having an efficient algorithm for the problem that takes advantage of that fact.
Theoretically, ZPP = EXPTIME implies EXPTIME $\subseteq$ BPP.  Since we already know P $\subset$ EXPTIME we have P $\subset$ BPP as well, which means there are some polynomial-time randomized algorithms that cannot be derandomized.  This is another way of saying that pseudo-random number generators will never be as effective as true randomness, algorithmically, which would be a very interesting result.
We know that BPP is low for itself, i.e. BPP$^{BPP}$ = BPP.  Therefore an EXPTIME no more powerful than BPP must be low for itself as well, which removes the separation between some exponential classes, e.g. EXPTIME = EEXP = EE = EEE.  This in turn makes some decidable but intractable problems simply decidable. For example, deciding the truth of first-order mathematical statements expressed in Presburger arithmetic would now be in BPP.
We also know that BPP $\subseteq \Sigma^P_2 \cap \Pi^P_2$.  Together with EXPTIME $\subseteq$ BPP this means that the polynomial hierarchy collapses to the second level; the oracle calls above that level do not offer any more computational power, as EXPTIME is powerful enough to capture all the rest of PH.  Since P is strictly a subset of BPP and P = NP would collapse PH completely, bringing P and BPP together, ZPP = EXPTIME would imply P $\neq$ NP.  Interestingly, I think NP = co-NP would still be an open problem.  But with the proof writing power you'd get from EXPTIME being tractable, I doubt the problem would be open for long.


graph theory analogue of rectangular matrix

Such a graph is known as a bipartite graph.  There is a whole theory about bipartite graphs, including a number of algorithms that are specialized for bipartite graphs.


Why cannot match $ Bool \equiv Bool $ with $ refl $ while $1 \equiv 1$ can?

From the perspective of Homotopy Type Theory (HoTT), i.e. if we have the Univalence Axiom, there are definitely values of Bool ≡ Bool that are distinct from refl. Because Agda without Axiom K is compatible with univalence, it can't then assume that refl is the only value of type Bool ≡ Bool.

ℕ, on the other hand, is an h-set in HoTT (see Section 2.13 of the HoTT book). This is to say that Axiom K restricted to ℕ does hold. This is related to the fact that ℕ is inductively defined (with no parameters or indices) while Set is not.

I don't know the exact logic Agda uses. Presumably, it is something like it knows that nullary constructors of an inductive type are identified with themselves in only one way (which wouldn't be true for higher inductive types), and it knows suc is injective.


Distribution algorithm according to weighted parameters (with a min-max constraint)

Let me repeat my understanding of the problem (as I understand it), then sketch a candidate solution approach.  If I've misunderstood the problem, you might need to revise the question to clarify.

The problem: You have $n$ items, and want to divide them into $n/B$ batches of $B$ items.  Presumably, $n$ is a multiple of $B$.  Each item has some set of tags (a subset of $\mathcal{T}$, where $\mathcal{T}$ denotes the set of all possible tags).  For each batch, we're given a function $f:\mathcal{T}\to \mathbb{N}$; we want to ensure that, for each candidate tag $t \in \mathcal{T}$, there are at least $f(t)$ items in the batch with tag $t$.  The question is to identify a valid division into batches, if one exists.

One candidate solution: we can formulate this as an integer linear programming problem.  Let $x_{i,j}$ denote a 0/1-valued variable that is $1$ if item $i$ is placed into batch $j$, and 0 otherwise.  Now we can write down some constraints on the $x$'s that correspond to the problem description.  We get

$$0 \le x_{i,j} \le 1$$

$$\sum_j x_{i,j} = 1$$

$$\sum_i x_{i,j} = B$$

$$\sum_{i \in S_t} x_{i,j} \ge f(t)$$

for all $i,j,t$.  Here $S_t$ denotes the set of items with tag $t$.  You can now use an off-the-shelf integer linear programming solver to search for a solution to this problem.

If I didn't understand your problem quite right, I hope you see the basic idea of my solution and hopefully you'll be able to come up with the appropriate tweaks to address any misunderstandings I might have had about what problem you were looking to solve.


How can I prove or disprove that the following function is bijection?

Originally, the hash function was defined as follows:

Input: a 64-bit unsigned integer $x$.
Calculate $(9E3779B185EBCB87)_{16} \cdot x = 2^{64} x_h + x_l$, where $x_l,x_h$ are 64-bit unsigned integers.
Output $x_l \oplus \lfloor (x_h + 2x_l)/8 \rfloor$.

Under this definition, there is a collision: both $(2DCE4F983BBEB685)_{16}$ and $(72E04DBED1540FE1)_{16}$ map to $(A5C53FE6E277BD92)_{16}$.
You can find such collisions using a cycle detection algorithm.