Allocation of many students to many schools based on capacity

This can be expressed as the problem of finding a maximum matching in a bipartite graph: each kid is one left-vertex, each slot in a school is a right-vertex, and there is an edge between two vertices if they can be matched.

In your case, you can solve it more efficiently using max flow.  I'll let work out the details.


What happens to multi-qubit quantum state after one of qubits is measured?

The amplitudes are scaled so that their norm is 1. In your case, if the original amplitudes are $\alpha_{000},\ldots,\alpha_{111}$, then after measuring the second bit to be 1, which happens with probability $p = \alpha_{010}^2 + \alpha_{011}^2 + \alpha_{110}^2 + \alpha_{111}^2$, the quantum state is
$$
\frac{\alpha_{010} \left|010\right\rangle + \alpha_{011} \left|011\right\rangle + \alpha_{110} \left|110\right\rangle + \alpha_{111} \left|111\right\rangle}{\sqrt{\alpha_{010}^2 + \alpha_{011}^2 + \alpha_{110}^2 + \alpha_{111}^2}}.
$$


How to output all longest decreasing sequences

Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a > b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.


It is called contraposition :
$f(x) \in B \Rightarrow x \in A$
is equivalent to
$x \notin A \Rightarrow f(x) \notin B$.
So, the two statements that you have seen are equivalent as well.


is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

The first thing we have to do is define a decision version of your problem, like for example:

Is it possible to swap the elements inside the rows of the matrix so that in at least one column the number of distinct elements is less or equal than $\rho$?

Well, the first thing to take into account is that this problem is just asking if we can swap elements inside the rows in order to find a column where the number of distinct elements is less or equal than $\rho$.

We are going to reduce the decision version of 3HITTING SET to the decision version of your problem. 3HITTING SET is an np-complete variant of minimum hitting set where all subsets have only three elements. Hitting set is like the inverse of set cover. In minimum set cover you cover members of the universe with subsets and in miminum hitting set you cover subsets with members of the universe. That means that if an element appears in a subset, that subset is covered by the element. The objective is to find the minimum number of elements inside the universe that are enough to cover all subsets.

A decision version of 3HITTING SET will be:

Is it possible to cover all subsets with at most $\rho$ elements of the universe?

Now with the reduction:

We simply convert each subset of the hitting set problem into a row of your problem. That is we create a matrix $A$ .Then, for each subset $i$ that belongs to the hitting set instance, we create a row $i$ inside the matrix $A$. And then for each element $j$ that belongs to the universe in the hitting set instance being reduced, we create a number inside the matrix, this number will be inside row $A_i$ if the element $j$ that belong to the universe appears inside the subset $i$ in the hitting set instance.

If there is a hitting set of size $\rho$, then we will have a matrix where we can form a column by swapping with at most $\rho$ distinct elements.

The reason for this is that if we can cover the sets of the hitting set instance with $\rho$ elements then we can form a column with $\rho$ or less distinct elements inside the matrix by picking the numbers that were mapped to elements of the universe in the hitting set instance and swapping them inside the rows of the matrix so that they are all in the same column.

For the other direction, that is, for the cases in which there is no minimum hitting set instance with at most $\rho$ distinct elements we have to show that those cases are converted in our reduction into matrices where we can´t form a column with at most $\rho$ elements by swapping numbers inside rows.

If on those instances we could, by swapping numbers inside rows, create a column with at most  $\rho$ elements inside the matrix; that would mean that there exists $\rho$ elements that can cover the subsets in the hitting set instance. This is a contradiction

The reason is that we have mapped every element of the universe in the hitting set instance to a different number inside the matrix and also we have mapped every subset into a different row inside the matrix. So if we could form a column with at most $\rho$ distinct elements by swapping elements inside the rows, that will mean that there is at least one of those numbers inside each row. Because each subset of the hitting set instance was mapped to a different row and each element of the universe is mapped to a different number inside the matrix, that will mean that we can cover the subsets with those $\rho$ elements in the hitting set instance.


Does register renaming remove all kinds of WAR hazard?

Write-after-read (WAR) hazards are pervasive throughout all of computer systems, although different subfields call it different things.  Renaming of one kind or another (and called one thing or another) is the most general method I can think of for working around these kinds of problems.

Register renaming is the form of renaming used in CPUs that want to expose more instruction-level parallelism.  It can be made relatively efficient because the number of programmer-visible register names on most architectures is bounded and small.

From a computer architecture point of view, an additional problem for write-after-read hazards is dealing with load and store operations to main memory.  Register renaming won't help with this problem, because the space of visible memory locations is enormous compared to the number of available registers.  For this problem a different kind of "renaming" is done where store operations are buffered in a store queue for a period of time.  The store queue can be made relatively small because on most CPUs the number of stores that we want to have "in-flight" simultaneously is relatively small.  Thus the store-queue can be relatively small and we can afford to have every load operation perform an associative search of the store queue.

But the renaming concept is fundamental outside of computer architecture too.  An analogous situation occurs in the implementation of any programming language with automatic local variables (which is most programming languages.)  You can view the locally declared variables in the source code as analogous to register names and activation records (stack frames) as analogous to renamings of the registers.  This concept is leveraged in several parallel programming languages, for example in the Id programming language (one of the precursors to Haskell) and the Cilk programming language (an extension to C) the fact that each procedure writes its local variables in a different activation record is used to allow procedure calls to execute in parallel.

In transaction processing systems used in large databases multiversion concurrency control is analogous to renaming.  Each transaction sees, and modifies, its own "snapshot" of the entire memory and the snapshots are committed atomically.  The snapshots are generally implemented using techniques that are more similar to store queues than to register renaming.

Renaming is also a fundamental technique used in non-blocking synchronization.  Suppose you have some container data type (like a map) where you have a unique pointer to the root of the implementation.  You can implement lock-free atomic operations by copying the pointer, allocating a new data structure, copying the entire data structure from the old copy to the new, modifying the new version and then trying to compare-and-swap the pointer to the new copy for the pointer to the old copy.  Copying an entire data structure would be ridiculously expensive, so in general if you want to do this you would use purely functional data structures.

If you couldn't already tell, this is my favorite topic, and I could go on for hours.  So I'll stop here since I've probably written way more than you wanted.


Djikstra's algorithm to compute shortest paths using at least k edges

Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice.

Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in polynomial time for $k=n-1$ and thus find a path that visits eeach vertex in $V$ exactly once. In other words, we can "solve" Hamiltonian Path.

If you know in advance that $k \leq 20$ then you can exhaustive search all paths of length at most 20, and therefore solve for small $k$.

An exhaustive search, at worst, is to search every vertex order starting from $s$ that ends in $t$ (corresponding to existing edges), so in total you will search:
 $$(n-1)(n-2)(n-3)...(n-20) = O(n^{20})$$


Can the test set of attributes be a subset of the training set's attributes?

Well, if the test data would be the same from training data, your machine learning algorithm may overfit. Because you test your model with your training data it may perform very well, as it may see the pattern even in noise. And then it won't generalize on new data.

You should separate the test data (with which you see the accuracy) to the training data.


It's just AND gates.  So, assuming $in$ is the input, $sel$ is your selector bit, and $out_1$ and $out_2$ are your two possible outputs, you would get:

$out_1 = in \land \lnot sel$

$out_2 = in \land sel$

The idea is that, if $in$ is $0$, out must always be $0$.  If $in$ is $1$, then we have to output it to the proper gate.   If you had a larger demux, you would simply have more selector bits.  So, for a demux with 16 outputs, we would need 4 selector bits: $sel1$, $sel2$, $sel4$, and $sel8$.  Output 10 would thus be a 5-input AND gate:

$out_{10} = in \land (sel_8 \land \lnot sel_4 \land sel_2 \land \lnot sel_1)$

The other outputs would be blocked because they would have different combinations of $sel1$, $sel2$, $sel4$, and $sel8$ ANDed into their outputs.


Show that a language with union is not regular by using pumping lemma

If $L$ was regular, so would be $L \cap c^+\Sigma^* = \{c^{2k}w\mid k\geq 1, w\in\{a,b,c\}^* \text{ and }|w|_a = |w|_b\}$.
That means that if you prove that this language is not regular, then $L$ cannot be regular too (that way, we got rid of the union).
Now you can take it from here with pumping lemma, starting from $c^2a^nb^n$!


Proof of decidability of determining whether a DFA accepts a string

I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). The problem $A_{DFA}$ essentially is the following: given a DFA $D$ and a string $w$, determine whether $D$ accepts $w$. In software, you could imagine that you'd want to write a method

bool accepts(DFA D, string w)

that takes as input a DFA $D$ and a string $w$, then returns the answer. Notice that we're given the DFA as a parameter, since if we don't have it, then there's no way that we can answer the question. It would be like someone saying "I'm hiding a DFA behind my back - can you guess whether it accepts a given string?"

The pseudocode for this function might look something like this:

bool accepts(DFA D, string w) {
    currState = D.startState;
    for (char ch: w) {
        currState = D.transitionTable[currState][ch];
    }
    return D.isAcceptingState(currState);
}

Since this is something that we can do with a computer, it's certainly something that we can do with a TM.

Given this code, it's probably clearer what the TM you described above would do. It doesn't take in infinitely many DFAs or strings - it just takes in a single DFA and a single string at a time. There are infinitely many possible choices for what that DFA could look like or what that string could be, but at any one point in time the TM works on just a single string and a single DFA. The fact that the TM (or this code) correctly works on every possible DFA and every possible string is why $A_{DFA}$ is decidable: there's a TM that, given an arbitrary string, decides whether it's in the language.


Local search to find minimum degree spanning tree

No, we cannot always find an edge $e$ to add when $\Delta(T) > \Delta^*$.

The graph above was drawn at https://graphonline.ru/en

Here is an counterexample. Let $G$ be the 3-regular graph on the right side that has 14 vertices and 21 edges. Let $T$ be the spanning tree that consists of all the edges in bold. That is, $T$ has all the edges in $G$ except the innermost 7 edges and the edge at the top right. The graph on the left side shows a hamiltonian path of $G$. That is, $\Delta(T)=3$ and $\Delta^*=2$.

Let $e$ be an edge not in $T$. If we add $e$ to $T$, the resulting cycle $C$ contains at least two non-adjacent vertices of degree 3 in $T$. If we further delete any edge in $C$ incident to a vertex in $C$ with the highest degree 3, we obtain graph $T'$.  There is at least one vertex of degree 3 in $T'$. That is, the maximum degree of vertices in $V(C)$ in $T'$ is 3.


1) Both two unbelieved scenarios that $\mathrm{NP}=\mathrm{P}$ and $\mathrm{NP}=\mathrm{EXP}$ implies that $\mathrm{EXP}^\mathrm{NP} = \mathrm{NEXP}$ and $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$. So we cannot refute these two claims at present.

On the other hand,

assuming $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$ would imply $\mathrm{BPP}\neq\mathrm{NEXP}$, since $\mathrm{BPP}\subseteq\Sigma_2^{p}$ and $\Sigma_2^p\subsetneq\mathrm{\Sigma_2^{exp}\subseteq\mathrm{EXP}^\mathrm{PH}}$
assuming $\mathrm{EXP}^\mathrm{NP}=\mathrm{NEXP}$ would imply $\mathrm{P}^\mathrm{NP}\neq\mathrm{NEXP}\cap\mathrm{co}-\mathrm{NEXP}$

2) First of all, your implication that $\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}\implies\Delta_2^{exp}=\Sigma_1^{exp}$  is not known since exponential-time hierarchy does not possess the upward collapsing property like polynomial-time hierarchy (some inner collapse at some level does not necessarily imply the collapsion of all the exponential-time hierarchy to that level).

Beside from that, $\mathrm{NP}=\mathrm{co}-\mathrm{NP}\implies\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}$ is true by standard translation technique, but the opposite implication is not known due to the difficulty in achieving the downward closure theorems for non-determinism and co-non-determinism. It has been done for probabilistic classes (zero-sided, one-sided, bounded-error all done, but general probabilistic $\mathrm{PrTime}$ still open). For more details on downward closure theorems, see the reference in this answer.


Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?

The answer—as with many such applied numerical problems—is, "sure, but you have to decide which of the published heuristics you want to use". Your real problem will be the embarrassment of riches as you try to choose a paper to implement or find an existing library implementation.

Using a quick Google search on estimating step size from accelerometer, I was able to find multiple articles proposing different methods for doing this. Apparently the research area is called Pedestrian Dead Reckoning (PDR), which makes sense since dead reckoning is the general term for estimating positioning using only velocity and acceleration data.

Some articles that attempt to estimate stride length as part of a PDR algorithm include:

Ngoc-Huynh Ho, Phuc Huu Truong, and Gu-Min Jeong (2016). Step-Detection and Adaptive Step-Length Estimation for Pedestrian Dead-Reckoning at Various Walking Speeds Using a Smartphone.
Haifeng Xing et al. (2017). Pedestrian Stride Length Estimation from IMU Measurements and ANN Based Algorithm.
Ahmad Abadleh et al. (2018). Step Detection Algorithm For Accurate Distance Estimation Using Dynamic Step Length.
etc.


Many better techniques for enforcing cardinality constraints are described in this answer.  For the special case $y=1$, see also Encoding 1-out-of-n constraint for SAT solvers.  Read those links; they suggest more efficient conversions, though I'm not aware of any reason to expect that they are necessarily optimal, so they don't answer your question about the most efficient conversion.


Parallel merge sort using hypercube connection template

They write

  The $i$-th parallel merge takes two sequences, each distributed over $2^{i-1}$ tasks, and generates a sorted sequence distributed over $2^i$ tasks.

For $i=1$, that reads

  The first parallel merge takes two sequences, each stored locally on one task, and generates a sorted sequence distributed over two tasks.

That is, every node performs one compare-merge. Similarly, for higher $i$, each node performs $i$ such operations.

They use it to derive "per-processor communication cost" $T_{comm}$ which clarifies that they do indeed count processor-wise in the prequel. That makes sense, too: communication happens in parallel, so in order to derive bounds on overall runtime you can bound every (abstract) step from above with the longest processing time found among all processors in that step.


Could someone explain Fagin's theorem on the equivalence between NP and existential quantifier

You can check out these lecture notes, as well as countless more. The proof of Fagin's theorem is divided into two parts: showing that every language expressible in existential second-order language is in NP, and showing that every language in NP is expressible in existential second-order language. The first part is easy – we just have to guess the quantified relations. The second part is more complicated, but resembles the proof of Cook's theorem. The idea is that the quantified relations encode the computation of an NP machine.

For more details, you can consult Neil Immerman's book Descriptive Complexity.


Hardness of approximating 0-1 integer programs

One-in-three 3SAT is NP-complete. Looking at the reduction, it inherits the APX-hardness of 3SAT. You can formulate one-in-three 3SAT as a binary integer program with binary entries, so you problem is APX-hard.


Finding a regular expression of a language

You have to put your triplets, and use Kleene star: $$(aaa)^*(bbb)^*$$

Now, add cases where number of $a$ is not divisible by 3, say aabbbb, as alternative.
$$ (aaa)^*(bbb)^* + (aaa)^*aab(bbb)^* + (aaa)^*abb(bbb)^*$$


Can POSIX BRE express all regular languages?

Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.

For example, $\{ab, ba\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:

It can't be one of the single-character forms since the language has words of length $\gt 1$.
It can't be $R^*$ because that would match the empty string.
It can't be $R^{\{m,n\}}$ except with $m=n=1$ (in which case we're back to the original problem) because that would match strings of different lengths or the empty string.
So it has to be concatenation: $R_1 R_2$. Now consider how $ab$ is recognized:

If $R_1$ recognizes $ab$ then $R_2$ must not recognize anything anything other than the empty string. So $R_1$ must recognize $\{ab,ba\}$ and we're back to the original problem.
If $R_1$ recognizes $a$ but not $ab$ then $R_2$ must recognize $b$. But then $R_1R_2$ recognizes all words of the form $u b$ where $R_1$ recognizes $u$, so $R_1$ must not recognize anything other than $a$. There's no way to recognize $ba$.
If $R_1$ recognizes neither $ab$ nor $a$ then the only way for $R$ to recognize $ab$ is if $R_1$ recognizes the empty string, in which case we're back to the original problem as above, but for $R_2$ this time.

When “we're back to the original problem”, that means that the only solution to find a BRE recognizes the language is to find a smaller BRE that has the same property. This is an infinite descent, so there's no BRE that has the desired property.

I don't think there's a “nice” characterization of BRE-recognizable languages, for example as languages recognizable by a “nice” class of automata.

Note that BRE-recognizable languages are actually not a subclass of regular languages, since backreferences add expressive power. For example $\{w w \mid w \in \{a,b\}^*\}$ is recognized by the BRE \(.*\)\1 but is famously not regular. BRE without backreferences are just syntactic sugar over regular expressions so the languages they can recognize are a subclass of the regular languages.


How to define the languages of the implicit set system problems?

There are different notions of complexity used for various computational problems, not all tasks fit naturally to the standard model of decision/search problems. The "classic" analysis of complexity talks about how many resources we need to compute $f(x)$ given $x$, but this misses a lot of interesting questions we can ask. Consider communication complexity, where we want to compute $f(x,y)$ where one sides holds $x$ and the other holds $y$, while minimizing the number of bits exchanged between the parties. This requires a new definition of complexity. Same goes for query complexity, where we are given a black box access to some function $f$ and we want to know how many evaluations of $f$ are required to determine if it satisfies some property $P$.
The seemingly natural way (this of course depends on the context) to determine hardness of set system problems would be in terms of standard complexity and the number of queries to the membership oracle. As the set system is given, I don't want to involve hardness of deciding whether some set is in the system, so I'll only charge one operation for querying the membership oracle. This allows, in a sense, to isolate the hardness of evaluating the property from the hardness of the system's description.


Aren’t most constraining variable and least constraining value the exact opposite?

Yes, these two heuristics does sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least Constraining Values tries to enlarge the size of the next branch to branch.
However, if you take a close a look, they both serve the same goal, which is, given a Constraint Satisfaction Problem (CSP), to find a solution as fast as possible and, if there is no solution, declare that fact as fast as possible.
Firstly, these two heuristics are applied in different stages of the search. MCV is about choosing which variable to assign value to and then, given a variable, LCV is about choosing which value to assign.
Here is a quote from a lecture note on Constraint Satisfaction
Problems by Max Welling, slighted edited.

In all stages of the searching for one solution, we want to enter the most promising branch, but we also want to detect inevitable failure sooner.
MCV: the variable that is most likely to cause failure in a branch is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon.
LCV: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables. We want our search to succeed as soon as possible, so given some ordering, we want to find the branch that is more likely to succeed.

In term of the search tree, MCV help pruning bigger branches more often and earlier, thus makes the searching end faster, whether it ends with a solution or no solution possible. LCV help make backtracking less often in case there is a solution, but it does not help when there is no solution since every value has to be searched. In other words, if the goal is to find all solutions instead of one solution, then MCV still help effectively while LCV does not help at all.
I would like to use planning a party as an example. The variables are who should attend, when to hold it, where to hold it and how much to spend (why and what is another question). The object is to see if there is a party plan that is viable.
Suppose you are almost running out of money. Then the first thing to check is to set a tight limit on spending. You do not want to plan all the other parts in great beautiful detail only to find there is not enough money to support them later. Then within your budget you want to set a limit as high as possible so that there is more room to make the party plan attractive enough to be held. Note that you are applying the principle of MCV and LCV.
Consider another situation. You are planning a birthday party for one of your friends and you are not so constrained much by the money. Then you probably do not want to consider your budget first. The first thing you want to decide is probably when to hold the party since there are usually not many choices. It is expected usually to be held just before that birthday. Then in order to have most of remaining choices you want to pick a time such as the night on the birthday instead of in the afternoon when many people are still working or having classes. Only in case the night on the birthday does not work, for example because some people cannot attend, will you backtrack to the less likely choice of the afternoon on the birthday. Note again that you are using the approach of MCV and LCV.
We can see that MCV and LCV are working together to enable you to find a viable party plan faster. You can also imagine what might happen if you use the opposite approaches, the approach of least constrained variable first and maximum constraining values first
Although far from rigorous, this example of party planning might aid your conceptual understanding of MCV and LCV working together. (You can also view the example as an application of principles of artificial intelligence to guide our decision making process in real life.)
For more related material, you can check chapter 6, "Constraint Satisfaction Problems" in the leading AI book Artificial Intelligence: A Modern Approach (3rd Edition) by by Stuart Russell and Peter Norvig.


Is there a DFA that accepts no string, but has at least one final state?

Consider a 2-state DFA over the alphabet $\{a\}$ (single character alphabet) that accepts only the empty string:

In this DFA, state 0 is the start state, and also the only accepting state. Now, if state 1 were the start state (but state 0 still the only accepting state), what strings would this machine accept?


Do any two spanning trees of a simple graph always have some common edges?

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:


I don't really understand your problem, so here is how you can solve a similar problem: instead of removing duplicated, we want each element to appear at most twice. In other words, if an element appears in a run of length $\ell$, we replace it with a run of length $\min(\ell,2)$. Suppose that the array is $A_1,\ldots,A_n$.

Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:

If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell \leq 2$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.

Return $A_1,\ldots,A_\nu$.

You can prove by induction that $\nu \leq i$, and so information is erased only after it is read.

A more challenging task is: "If an element appears in a run of length $\ell \geq m$, replace it with a run of length $2$". In other words, we replace a run of length $\ell$ with a run of length $2$ whenever $\ell \geq m$ (assuming $m \geq 2$). We can accomplish this using a similar strategy:

Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:

If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell < m$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.
If $\ell = m$, remove $m-2$ occurrences of $\mathrm{curr}$: decrease $\nu$ by $m-2$.

Return $A_1,\ldots,A_\nu$.


Variant of an approximation algorithm for vertex cover

Consider a star consisting of a center $x$ connected to the vertices $y_1,\ldots,y_n$.
Your modified algorithm could act as follows:

Choose the edge $(x,y_1)$; add $x,y_1$ to the vertex cover; remove all edges incident to $y_1$.
Choose the edge $(x,y_2)$; add $x,y_2$ to the vertex cover; remove all edges incident to $y_2$.
...

I'll let you take it from here.


Is $\lceil\log n\rceil!$ polynomially bounded?

Don't trust plots.

By Stirling's approximation (and dropping the ceilings to avoid notational overload),

$$\begin{align*}
(\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\
  &= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\
  &= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,,
\end{align*}$$

which grows faster than any polynomial.  But you're not going to see that by plotting versus $n^{100}$ unless you consider values of $n$ big enough that $\log\log n$ is more than about $99$, i.e., roughly $n\geq e^{e^{99}}\approx 10^{10^{42}}$, and you probably didn't consider values of $n$ quite that big, because no plotting software is going to display values like $(10^{10^{42}})^{100}$.


Subset-sum approximation algorithm running time

Both $z$ and $z'$ belong to the same trimmed list, after trimming. The point is that after trimming, two adjacent elements are at a multiplicative distance of at least $1+\epsilon/(2n)$, by construction. This is why the trimmed lists are small, and so the running time is reasonable. If there is no trimming then there is no problem – the original list already satisfies this condition.

Here is a concrete example. Suppose we want our elements to be at multiplicative distance at least $2$, and suppose that the original list is $1,2,3,4,5,6,7,8$. After trimming we are left with $1,2,4,8$, and any two adjacent elements are at multiplicative distance at least $2$ (in this case, exactly $2$). Had we started with, say, $1,4,9,16$, no trimming would be necessary, but still adjacent elements are at multiplicative distance at least $2$.


How does a CPU differentiate between 1-operand instructions and 2-operand instructions?

Normally the opcode encoding is designed to make it easy to tell.  The details of exactly how that works will depend on the particular architecture.  For instance, in your example, the first 4 bits might be enough to determine which category the instruction is in.  This decoding is performed by the instruction decoder.

As Ran G. explains,

  usually, either all instructions have the same length -- and then different OPCODEs signify different operations, or the instructions have variable length, and then there is some sort of prefix-coding that allows the CPU to determine which instruction it is (and what it length is) by its prefix.


deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

Couple 1 tries to start and is waiting on A, couple 4 tries to start but is also waiting on A.

After couple 5 finishes one of the waiting couples will be able to lock A. If it is couple 1 then it will need to lock B before it can continue, however that is held by couple 2 and that is waiting on couple 2 which is waiting on couple 3 etc. until couple 4 which is now waiting on couple 1. There is no way to make progress $\implies$ deadlock.

It's important to keep in mind that between locking one word and locking the next a process can be interrupted or another can simple be faster and lock the second word.

You can avoid the lock by always locking the words in alphabetical order, that way couple 4 will lock A before it will try to lock D and couple 3 is then able to make forward progress and a deadlock is impossible.


Divide and Conquer Algorithm to calculate $a^n$

I think you are looking for something along these lines.

public double exp(float a, int n) {
    if(n<=0) return 1; // just for safety saying <= instead of == to allow
    if(n==1) return a;
    float floor_exp = exp(a,floor(n/2))
    if(floor(n/2) < ceil(n/2)){
        return floor_exp * floor_exp * a;
    }
    else{
        return floor_exp * floor_exp;
    }
}

Note that floor and ceil are not functions in Java but in Python. Use these for Java. Also this will only work for n >= 0. The result is incorrect for the other case.


How can image processing neural networks be effectively trained?

Yes.  Typically a very large data set is required: tens or hundreds of thousands of labelled images, or perhaps even more.  No, 100 images almost certainly won't be enough.

Just running over the same 100 images won't help.  Doing that won't provide the machine learning algorithm any new information that it doesn't already have.

Where do we get these large data sets from?  Basically, through tedious human effort.  There are many variants of this:

Sometimes it involves people manually, tediously labelling images one by one.
Sometimes one can find an existing data set that someone else has already labelled for you (e.g., ImageNet).
Sometimes you can pay other people to do the labelling for you (e.g., crowdsourcing on Mechnical Turk or something like that).
Sometimes you can find images that are already labelled: for instance, if you do a Google Image search on "cat" it will find many, many images of cats for you.  Well, most of them will be cats; there may be a few other images in there (e.g., a picture of a tiger, a picture of someone named Cat), but the overwhelming majority will be cats.  How does Google Image search know to return these images, when you search for "cat"?  Google might be looking at the keywords on the same page where the photo is found.  So, basically, this is a case where we already have images on the Internet that have already been labelled by whoever made them available, so it's a particularly interesting special case of the above.

That's the basic idea.  There are variations, of course, but I hope it gives you the basic idea.  As you can see, coming up with the training set can be extremely tedious and/or expensive, and the availability of labelled data to use for training a machine learning classifier can be one of the main limiting factors on our ability to build better classifiers.  This is one of the reasons behind the current hype around "big data": labelled data is valuable (because it can be used to train interesting classifiers), so companies that already have lots of (labelled) data have a valuable asset.


If M is recognizing L in polynomial time, is it also deciding it in polynomial time?

It is indeed possible. Simulate $M$ for $n^k$ steps. If it has accepted so far, accept. Otherwise, reject. You can simulate $M$ for $n^k$ steps in polynomial time (perhaps $O(n^{2k})$), hence this is a polynomial time algorithm.


Fixed base exponentiation with precomputations

Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary:
$$
n=\sum_{i=0}^m e_i2^i\qquad e_i\in\{0,1\}
$$
so
$$
g^n=g^{e_02^0+e_12^1+e_22^2+\dotsm}=(g^{2^0})^{e_0}(g^{2^1})^{e_1}(g^{2^2})^{e_2}\dotsm
$$
and observe that $g^{2^k}=(g^{2^{k-1}})^2$ so computation of the $g$ terms can be accomplished by repeated squaring, either in the body of the loop or by precomputation.
The paper simply generalizes this using a base, $b$, other than $2$. If we keep with your example of $b=3$, then we're doing the same thing as the usual algorithm, only using repeated cubing, rather than repeated squaring, so if we have, in general
$$
n=\sum_{i=0}^m e_ib^i\qquad e_i\in\{0,1,\dotsc,b-1\}
$$
then we can write
$$
g^n=(g^{b^0})^{e_0}(g^{b^1})^{e_1}(g^{b^2})^{e_2}\dotsm
$$
and do the usual algorithm, forming the product seriatim, from $0$ up to the limit $m$, using repeated exponentiation of the terms, since $g^{b^k}=(g^{b^{k-1}})^b$ as above. This is your proposal and it will work just fine.

The key idea in the paper relies on the observation that the $e_i$ are now not just $0$ or $1$, so we often have another exponentiation step for each term. Rather than do several of those, the paper just does it once, for each possible value of $e_i$.

Here's your example, with $n=142$ and $b=3$. Since $142_{10}=12021_3$ we'll have $e_4=1$, $e_3=2$, $e_2=0$, $e_1=2$, $e_0=1$. Looping from $i=0$ to $4$ you could successively form the product
$$
g^{142}=(g^{3^0})^1(g^{3^1})^{2}(g^{3^2})^{0}(g^{3^3})^{2}(g^{3^4})^{1}
$$
The paper instead loops first by the nonzero values of the $e_i$, effectively grouping several exponentiations into one, doing this:
$$
g^{142}=\left [(g^{3^1})(g^{3^3})\right ]^2\left [(g^{3^0})(g^{3^4})\right ]^1
$$
obviously saving some multiplications.


Sum of heights in a complete binary tree (induction)

A complete binary tree of height $h$ has exactly $2^{h-k}$ nodes of height $k$ for $k=0,\ldots,h$, and $n=2^0+\cdots+2^h = 2^{h+1}-1$ nodes in total. The total sum of heights is thus
$$
\sum_{k=0}^h 2^{h-k}k = 2^h \sum_{k=0}^h \frac{k}{2^k} = 2^h \left(2 - \frac{h+2}{2^h}\right) = 2^{h+1} - (h+2) = n - \log_2 (n+1).
$$

The answer below refers to full binary trees.

I'm assuming the following definition of height. The height of a tree is the length of the longest root-to-leaf path. The height of a vertex in a tree is the height of the subtree rooted at this vertex. Denote the height of a tree $T$ by $h(T)$ and the sum of all heights by $S(T)$.

Here are two proofs for the lower bound. The first proof is by induction on $n$. We prove that for all $n \geq 3$, the sum of heights is at least $n/3$. The base case is clear since there is only one complete binary tree on $3$ vertices, and the sum of heights is $1$. Now take a tree $T$ with $n$ leaves, and consider the two subtrees $T_1,T_2$ rooted at the children of the root, containing $n_1,n_2$ vertices, respectively. Suppose first that $n_1,n_2 \geq 3$. Then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + n_1/3 + n_2/3 = n/3 + 2/3 > n/3.
$$
If (say) $n_2 = 1$ then
$$
S(T) = h(T) + S(T_1) + S(T_2) \geq 1 + (n-2)/3 = n/3 + 1/3 > n/3.
$$
This completes the proof.

The second proof proceeds by bounding the number of leaves in a complete binary tree. Order the children of every node so that it has a left child and a right child. Exactly half of the leaves are left children. Each left child has a different parent, and in particular each left leaf has a different parent. So a tree $T$ with $f$ leaves has at least $f/2$ non-leaves. In particular, the total number of vertices $n$ satisfies $n \geq f + f/2 = (3/2)f$, so that $(2/3)n \geq f$ and so $n-f \geq n/3$. We conclude that
$S(T) \geq n-f \geq n/3$.

The upper bound can be proved along the lines of the second proof. Suppose that there are $f$ leaves. Thus there are at most $f/2$ vertices at height $1$, at most $f/4$ vertices at height $2$, and generally speaking, at most $f/2^h$ vertices at height $h$. Therefore the total height of vertices is at most
$$
\sum_{h=0}^\infty h \frac{f}{2^h} = f \sum_{h=0}^\infty \frac{h}{2^h} = 2f \leq 2n.
$$


Can every state in a DFA be an accepting state?

Yes, every state can be accepting.  Assuming the transition function is total (complete), so every state has a transition out on every possible letter in the alphabet, then yes, this would recognize all strings in the DFA's alphabet: the DFA would recognize $\Sigma^*$.

If the transition function is not complete -- in other words, if there is some state $q$ and some letter $a$ where there is no transition out of $q$ on letter $a$ -- then the DFA doesn't necessarily recognize all of $\Sigma^*$.

See In a DFA, does every state have a transition on every symbol of the alphabet? for more on that distinction.  To avoid confusion, I generally recommend sticking to DFAs whose transition function is complete (total), at least until you understand the concepts well.


Here is the original refutation:

From $a'+c$ and $a'+c'$ deduce $a'$.
From $a$ and $a'$ deduce $\square$.

When you add $b'$ back, you get:

From $a'+c$ and $a'+c'$ deduce $a'$.
From $a+b'$ and $a'$ deduce $b'$.

More generally, since the only difference between $\Gamma$ and $\Gamma'$ is the addition of $b'$, it is not hard to prove by induction that for every line $\ell$ proved in the refutation of $\Gamma$, the corresponding line in the corresponding $\Gamma'$ proof is either $\ell$ or $\ell+b'$. Hence the $\Gamma'$ proof proves either $\square$ or $b'$. It can happen that it indeed proves $\square$, in which case we can deduce $b'$ by weakening, which is an admissible rule for resolution space (we can get rid of it without increasing the space).


Lambda Calculus - free vs. bound variables

Iterated abstraction uses abstraction to the right:

\begin{align}
LHS
&= (\quad \lambda wx.wx \space\space\space)\space(\lambda wx.wx) \\
&= (\lambda w.(\lambda x.wx))\space(\lambda wx.wx)
\end{align}

The beta reduction axiom is $(\lambda x. M[x])N = M[x := N]$.

To satisfy your original equation, replace all occurences of $x$ in the beta reduction axiom, with $w$. Then, substitute the following values into the beta reduction axiom: $$M[w] = (\lambda x.wx)$$ $$N = (\lambda wx.wx)$$

The beta reduction axiom with substituted values is $$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = M[w:=(\lambda wx.wx)]$$

where $M[w:=(\lambda wx.wx)]$ means "substitute all occurences of $w$ in $M$ with $(\lambda wx.wx)$". So we get:

$$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = (\lambda x.(\lambda wx.wx)x)$$

as expected.

For the $(\lambda y.a)b \rightarrow a$ equation, $y$ is a bound variable, while $a$ is a free variable. We apply $b$ to all occurences of $y$, but there are none so our expression doesn't change (no $y$ is converted to $b$). The result is still $a$, unchanged.

Source, really well written and accessible if you give it enough time.


Why do floating point additions sometimes produce equal results?

Floating point numbers have limited accuracy. They are stored in the following way: $\pm 1.x_0\ldots x_{n-1} \times 2^y$ (here $x_0,\ldots,x_{n-1}$ are binary digits) for an appropriate $n$; the value of the exponent $y$ is also bounded. The value of $n$ and the bounds on $y$ depend on the exact type of the floating point number.

When you add $2$ and $10^{-18}$, the answer is rounded to $2$ since the contribution of $10^{-18}$ is too small to store in the number (i.e., $n$ is too small). When you add $2^{-55}$ and $2^{-57}$ there is no such problem: this is stored as $1.01 \times 2^{-55}$.

For more, check out one of the multitudinous resources on floating point numbers.


Independent set is NP-complete, so it's unlikely to be in coNP.

Moreover, the complement problem would sound like "all independent sets have size at most $s$".


How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it.

Let's consider the three languages

$\qquad\begin{align*}
  &L_=     &\!\!\!\!\!\!\!\!\!
       &= \{ xy   \mid |x| = |y|, x \neq y \}, \\
  &L_{\#}  &\!\!\!\!\!\!\!\!\!
       &= \{ x\#y \mid  x \neq y \},\ \text{and} \\
  &L_{=\#} &\!\!\!\!\!\!\!\!\!
       &= \{ x\#y \mid |x| = |y|, x \neq y \}.
\end{align*}$

As we have seen here, $L_=$ is context-free. The trick is, in the grammar, to generate symbols "on the right" but count them "on the left" later (or the other way around), making sure mismatching symbols appear at matching positions. The length condition is trivial since it reduces to even length.
You can construct an NPDA with a similar idea, using the stack to match the position.

$L_\#$ is also context-free. The proof is even simpler: the mismatching symbols appear the same distance away from the beginning resp. the separator. Unequal lengths can be checked separately; non-determinism "chooses" between the two options.

Now, as you show, $L_{=\#}$ is not context-free. Here is why the proofs for the other two languages break down.

In the grammar for $L_=$, if we have to generate a separator in the middle we can not "reassign" symbols from "left" to "right".
Instead of "accept if lengths unequal or mismatch" we have to "accept if lengths equal and mismatch". Non-determinism can not help us with the and!

So what it boils down to, intuitively, is that conditions of the form "$x \neq y$" and "$|x| = |y|$" are both "context-free" in the sense that they can be checked with a stack, but not using finite control. Therefore, a PDA can do one but not both.

The PDA for $L_=$ "cheats" since it does not really check these conditions for $x$ and $y$; it splits the word up in a different way. That's no longer possible if you have the separator.

Addendum: I boldly claimed that $L_= \in \mathrm{CFL} \implies L_{=\#} \in \mathrm{CFL}$ because CFL is closed against inverse homomorphism. While it's true that $f(L_{=\#}) = L_=$ with $f$ the identity except it deletes $\#$, that is not relevant. $f^{-1}(L_=) = L_\#$; nothing can be said about $L_{=\#}$.

Addendum II: Note that $L = \{ x\#y \mid |x| = |y| \}$ is trivially context-free. Hence, with $L \cap L_\# = L_{=\#}$ we have a nice example for CFL not being closed against intersection.


What does "effective enumeration" in Turing machines mean?

One way to approach EFFECTIVE ENUMERATION is as following. Let $L=\{a_1, a_2, \dots\}$ be a set/language. Then we (effectively) enumerate $A$ if we can construct a TM $M$ which prints out (enumerates) all elements of $L$ on the tape, say in the following way: $a_1$#$a_2$#$a_3$#$\dots$. The order of the elements is not important. What is important is that any element of $L$ will eventually be printed on the tape, meaning it must not be a  LEXICOGRAPHIC order.


I'm interested in whether merging relational data has been researched, and what the findings have been.

Here are several papers mainly on the tree-to-tree editing problem. A lot of good stuff is related to XML documents.

Diffing, Patching and Merging XML Documents
The tree-to-tree editing problem
The Tree-to-Tree Correction Problem
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Change Detection in Hierarchically Structured Information
Efficient Snapshot Differential Algorithms for Data Warehousing
Detecting Changes in XML Documents
Meaningful Change Detection in Structured Data

A record in a database can be considered a simple tree of just a single row of children (the fields) or perhaps extending to the relations the record points to. With that you can do tree diffing/merging using the techniques outlined in these papers, and adding to it any column-specific string diffing techniques.

You could then add extra database-specific heuristics to the diffing system to make it more useful. For example, you have the extra metadata of the schema of the database, which provides a lot of information.


Convert NURBS curve into Cubic Bezier Curve

I assume that your cubic spline is non-rational, meaning $w$ = 1, then this is in general true that exact conversion is not possible. NURBS are rational, so you can model conics, say circle whereas Bézier cannot. There is special case: rational Bézier curve, which could be used in place of NURBS.

This simply means that you can draw circle, and only approximate it with Bézier.

To approximate, it depends on degree of curve: least squares method is stable and fast for low degrees, but fails (error is not equal along curve and huge) for higher degrees. Another idea is like in de Casteljau, recursively subdivide curve and use piecewise approximation. This idea generates lots of points and is numerically less stable than least squares.

For general NURBS of order 6+, approximation technique must be of order at least 6+, but it converges slowly.

In any case, finding Bézier curve through points from NURBS is way to go.

Another option is lossless conversion from NURBS to piecewise Rational B-Splines (URBS) (after conversion these are uniform, but no precision is lost), then via Boehm algorithm or Greville points convert B-spline to R-Bézier (here again, nothing is lost) and then project it to NR-Bézier (approximation, i.e. https://ieeexplore.ieee.org/document/6658158 or https://arxiv.org/pdf/1212.3385.pdf, here conics are lost).

Errors are seen about five-six places after decimal point for nasty splines (these that cannot be exactly recovered, as oposed to nice, which are wxact), so for any drawing purpose it is not visible, unless this is for milling machine, but hey, CNC supports (G-code G02) arcs anyway.


Let's assume the definition under which $\log^* 2 = 1$, $\log^* 2^2 = 2$, $\log^* 2^{2^2} = 3$, and so on. In order to show that $\log^* n = \omega(1)$, all you have to do is show that $\log^* n \to \infty$. Since $\log^*$ is increasing, it is enough to give a sequence of values $n_1,n_2,\ldots$ such that $\log^* n_i \to \infty$. Can you think of such a sequence?

In order to show that $\log^* n = o(\log^k n)$ for any fixed $k > 0$, find numbers $n_\ell$ such that $n \leq n_\ell$ implies $\log^* n \leq \ell$, and notice that for $n_{\ell-1} < n \leq n_\ell$, $\log^* n/ \log^k n \leq \ell/(\log^k n_{\ell-1})$. Perhaps you can show that $\log^k n_{\ell-1}$ is much larger than $\ell$ for large enough $\ell$. More concretely, you can try to show that $\log^k n_{\ell-1} \geq \ell^2$ (for example) for large enough $\ell$.


Confluence to show equivalent terms have one common reduct

$S \leftrightarrow^* T$ does not mean that $S \rightarrow^* T$ and $T \rightarrow^* S$! It means that there is a chain of reductions $S = S_0 \rightleftharpoons_1 S_1 \rightleftharpoons_2 S_2 \rightleftharpoons_3 \cdots \rightleftharpoons_n S_n = T$ where each of the $\rightleftharpoons_i$ might be either $\rightarrow$ or $\leftarrow$. The directions can alternate any number of times.

The confluence property does imply generically that if $S \leftrightarrow^* T$ then there exists $W$ such that $S \rightarrow^* W \leftarrow^* T$, but it takes a bit more work to show it. You can combine reductions in $S \leftrightarrow^* T$ to group consecutive reductions in the same direction together: $S = T_0 \leftarrow^* U_1 \rightarrow^* T_1 \leftarrow^* U_2 \rightarrow^* T_2 \leftarrow^* \cdots \leftarrow^* U_n \rightarrow^* T_n = T$. By confluence on $T_{n-1} \leftarrow^* U_n \rightarrow^* T_n$, there exists $V_n$ such that $T_{n-1} \rightarrow^* V_n \leftarrow^* T_n$. So we have $T_{n-2} \leftarrow^* U_{n-1} \rightarrow^* T_{n-1} \rightarrow^* V_n \leftarrow^* T_n$.

$$
\begin{matrix}
    &            & U_1 &            &     &        &         &            & U_{n-1} &            &     &            & U_n &            &     \\
    & _*\swarrow &     & \searrow^* &     & \cdots &         & _*\swarrow &     & \searrow^* &     & _*\swarrow &     & \searrow^* &     \\
T_0 &            &     &            & T_1 &        & T_{n-2} &            &     &            & T_{n-1} &            &     &            & T_n \\
    &            &     &            &     &        &         &            &     &
           &     & \color{green}{\searrow^*} &     & \color{green}{_*\swarrow} &     \\
    &            &     &            &     &        &         &            &         &            &     &            & \color{green}{V_n} &            &     \\
\end{matrix}
$$

Now apply the confluence property again to $T_{n-2} \leftarrow^* U_{n-1} \rightarrow^* V_n$, getting $V_{n-1}$ such that $T_{n-2} \rightarrow^* V_{n-1} \leftarrow^* V_n \leftarrow^* T_n$. Repeat until you get $W = V_1$ such that $T_0 \rightarrow^* V_1 \leftarrow^* T_n$. Formally, this is a proof by induction on the number of alternations of directions in the chain $S \leftrightarrow^* T$. Confluence lets you remove one alternation at a time. In more colorful language, confluence lets you “pop a crease”; each time you pop a crease, you join two depressions together, and if you keep doing that, you eventually get a single depression.


How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?

P is in big-endian format.
  P0 —0111011011010011001011010010011001011001010010001011011010000001,

The first bit, 0, means 2*0 + 1 = 1 is not a prime.
The second bit, 1, means 2*1 + 1 = 3 is a prime.
The third bit, 1, means 2*2 + 1 = 5 is a prime.
The fourth bit, 1, means 2*3 + 1 = 7 is a prime.
The fifth bit, 0, means 2*4 + 1 = 9 is not a prime.
The sixth bit, 1, means 2*5 + 1 = 11 is a prime.
The seventh bit, 1, means 2*6 + 1 = 13 is a prime.
The eighth bit, 0, means 2*7 + 1 = 15 is not a prime.
The ninth bit, 1, means 2*8 + 1 = 17 is a prime.
And so on.

  P1 —0100110000110010010100100110000110110000010000010110100110000100,

The first bit, 0, means 2*64 + 1 = 129 is not a prime.
The second bit, 1, means 2*65 + 1 = 131 is a prime.
The third bit, 0, means 2*66 + 1 = 133 is not a prime.
The fourth bit, 0, means 2*67 + 1 = 135 is not a prime.
The fifth bit, 1, means 2*68 + 1 = 137 is a prime.
The sixth bit, 1, means 2*69 + 1 = 139 is a prime.
The seventh bit, 0, means 2*70 + 1 = 141 is not a prime.
The eighth bit, 0, means 2*71 + 1 = 143 is not a prime.
The ninth bit, 0, means 2*72 + 1 = 145 is not a prime.
And so on.

  P2 -1001001100101100001000000101101000000100100001101001000100100101,

The first bit, 1, means 2*128 + 1 = 257 is a prime.
And so on.

  P3 -0010001010001000011000011001010010001011010000010001010001010010,

The first bit, 0, means 2*192 + 1 = 385 is not a prime.
And so on.

And so on.

  P7 -0000010100010000100010100100100000010100100100010010000010100110.

The first bit, 0, means 2*448 + 1 = 897 is not a prime.
And so on.
The last bit, 0, means 2*511+1 = 1023 is not a prime.

  Could somebody please help me understand what is going on here (in plain English)? I think that (k&63) has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?

If you have read the above explanation for many bits in P0, P1, ..., P7, the answer to your questions should be obvious now. For a number $2k+1$, $\lfloor k/64\rfloor$, the quotient of $k$ divided by 64, is which $P$ should be used. $k \mathbin{\&} 63$, the remainder of $k$ divided by 64 is how many bits you should move to the right to find its primeness-indicator bit.


Backpropagation in multiple output neural networks

You have to pick a loss function before you can apply backpropagation or train your network.  Once you do, you can apply backpropagation.  Backpropagation doesn't tell you how to pick a loss function; that's something you have to do, based on what you're trying to achieve.

Neural networks don't have binary outputs.  Rather, they have continuous outputs.  You might want to use a logistic loss on each of the 21 outputs, and sum up those 21 losses and use that as your overall loss function.  The logistic loss is effectively a generalization of the 0-or-1 loss to the case where you have a continuous output and you want to predict either 0 or 1.


In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles. Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.

It is tough to be a plumber.
Král, Daniel; Majerech, Vladan; Sgall, Jirí; Tichy, Tomass; Woeginger, Gerhard.
In: Theoretical computer science, Vol. 313, No. 3, 2004, p. 474-484.
https://doi.org/10.1016/j.tcs.2002.12.002


Trying to find a substitution to solve a recurrence

You don't need to try that hard. Instead, you can notice that on the one hand clearly $B(n) = \Omega(n)$, and on the other hand
$$
\begin{align*}
B(n) &= \Theta\left(n + \frac{n}{\log n} + \frac{n}{\log n \log(n/\log n)} + \cdots\right) \\ &=
O\left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) = O(n).
\end{align*}
$$
The first inequality holds since for $n$ larger than some constant, $\log_2 n \geq 2$ (you just need to stop the recursion once $n$ gets too small, at the cost of additional $O(1)$ which gets swallowed in the big Theta). The second inequality holds since $n+n/2+n/4+\cdots = 2n$.

Formally speaking, you can argue that $B(n) = B(n/2) + \Theta(n)$ grows faster than $B(n) = B(n/\log_2 n) + \Theta(n)$.


Smallest length such that all substrings of that length contain at least 1 common character

An equivalent formulation of your problem is:

  Given a string $S$ of length $n$, what is the minimal $k$ such that there exists an character $s\in S$ such that for all $i\in\{1,\ldots,n\}$, there exists a $j$ s.t. $|i-j|\leq k$ and $S[j]=s$. Report $k+1$.

Your approach seems to take $O(n^4)$ time in the worst case. If you try to see if the above formulation holds for all characters $s\in S$, you should be able to do it in $O(n)$:

Do a single linear scan trough $S$, while maintaining the last index you've seen each of the characters present in $S$ and the maximum gap size for each of those characters. After that, pick the character $s\in S$ with the smallest maximum gap size, this size is the value $k$. (Improved to a single pass thanks to @j_random_hacker's remark)

So, you can solve this problem in $O(n)$ time, which is a lot better than your initial approach. This approach is even asymptotically optimal, as we have to at least scan the entire string in the worst case, so we require at least $\Omega(n)$ time.


Sorting an "almost sorted" array in sub linear time

It is correct, but you should be careful to stipulate that the swaps are performed in a non overlapping fashion; if the swaps overlap then one element can be carried across the array breaking the guarantee.


How post correspondence problem is undecidable?

Post correspondence problem can be solved using a brute force approach.

No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm.
 But the PCP allows us to use each domino as many time as we want, which makes the number of possible configurations infinite.

Proof of undecidability:
We will prove this by reducing "Acceptance problem of Turing Machine" to an instance of PCP. We already know that, acceptance problem of Turing Machine: $$ L^A = \{ <M,w> | M \:is \:a \:TM \:and \:M \:accepts \:w \} $$
is undecidable. Hence, if our instance of PCP is decidable, acceptance problem of Turing Machine will also be decidable, A contradiction.
The reduction involves making dominoes for all possible configurations of a TM when run on the input string. A full reduction can be found here. Let me know in the comments, if you need any clarifications on the reduction.


Why can't OSes swap out processes that are waiting for I/O?

One scenario that can explain this more obviously is as follow: Suppose that a process wanted to read a disk block to a buffer in its address space (An I/O buffer is just a portion of the processe's memory. eg. char[1024]). The process will make a system call to ask the OS to issue an I/O to read the corresponding disk block into that buffer in the memory of the process and then the process sleeps waiting for this I/O operation to complete (Because it may take some time before the operation is completed by the device and at that time we can schedule another process for execution instead of letting the CPU idle). Now, to execute that I/O, the OS will probably program some kind of DMA (Direct Memory Access) device to automatically copy the data from the disk controller to the the buffer in the memory of the process without having to interrupt the CPU (Hence, the name direct access to memory). Now, if it happens that the process is swapped out, its physical memory will be freed (the memory where the buffer that receives the disk block content from the DMA is situated) and it will probably be allocated for another process. Which means that, when the DMA starts to copy the disk block content to the initially provided memory buffer (Initial buffer that was later freed and given to another process while the disk block was being read), that content is not actually being copied to the sleeping process's memory but some other process memory. And that's why the OS should not swap a process waiting for I/O. Otherwise, don't program the DMA to copy the disk content directly to the process's memory buffer but instead copy everything into some kernel buffer (Kernel memory) and then copy that content into the process memory again once it's ready (Swapped in) but this is a double duty and may incur some overhead.

Hence:-
So we can say that resources generated after the i/o processing for the original requesting process might be swapped with some other process, due to swapping of memory spaces between the processes.


You can't.  You can't infer big-O complexity from a finite set of data points, as big-O complexity is about asymptotics.  See, e.g., How to fool the plot inspection heuristic?.


How to determine letter boundaries in Huffman encoded strings?

Huffman codes are prefix-free codes (no codeword is a prefix of another), and so they are uniquely decodable. That means that if you encode a message using a Huffman code, then there is no other message that results in the same encoding.

Here is why. Suppose that $w$ is some binary string. We will show that $w$ encodes at most one message, in the Huffman code $\{c_1,\ldots,c_n\}$. Let's try to factor $w$ as $w = c_i w'$. I claim that this can be done in at most one way. Otherwise, we would have $w = c_i w' = c_j w''$, and so either $c_i$ is a prefix of $c_j$ or the other way around. If there is no such factorization, then $w$ encodes no message. Otherwise, suppose $w = c_i w'$. Then the first character of the message (if there is any) is $i$, and the rest is encoded by $w'$.

Prefix-free codes can be decoded very efficiently: to find the prefix $c_i$ alluded to in the preceding paragraph, just follow the Huffman tree until you get to a leaf. There is no look-ahead. There is a more general class of codes, uniquely decodable codes, which are codes satisfying what we proved in the last paragraph: every string is the encoding of at most one message. Such codes could require arbitrary large look ahead: consider for example $\{00,10,1\}$ and a word $1 w^n$. If $n$ is even then this is broken up $1(00)^{n/2}$, if $n$ is odd then $10(00)^{(n-1)/2}$. In order to tell which is which, we need to look ahead to the end of the string.

Given that prefix-free codes are easier to decode, but uniquely decodable codes are more general, you could ask: do we gain something by allowing uniquely decodable codes which are not prefix-free? This is answered by the Kraft–McMillan inequality: every uniquely decodable code $\{c_1,\ldots,c_n\}$ satisfies
$$ \sum_{i=1}^n 2^{-|c_i|} \leq 1, $$
and conversely every set of codeword lengths satisfying this inequality correspond to some prefix-free code. So prefix-free codes are as general as it gets.

The proof is not too difficult. Suppose $c_1,\ldots,c_n$ is uniquely decodable, with maximum codeword length $M$. Consider the encodings of all words of length $\ell$. Weight each encoding $x$ by $2^{-|x|}$, and sum. You get
$$ \left(\sum_{i=1}^n 2^{-c_i}\right)^\ell. $$
On the other hand, since the code is uniquely decodable, for each possible length, $2^{-|x|}$ must sum to at most $1$. Since words of length $\ell$ are encoded by strings of length at most $M\ell$, we conclude
$$ \left(\sum_{i=1}^n 2^{-c_i}\right)^\ell \leq M\ell. $$
Taking $\ell$th roots and letting $\ell \to \infty$, we recover the inequality.

For the other direction, suppose that the integers $\ell_1,\ldots,\ell_n$ satisfy $\sum_{i=1}^n 2^{-\ell_i} \leq 1$. Without loss of generality, we can assume that the sum is exactly $1$: otherwise, suppose that the sum is $A/2^B$ (for integer $A$), and add $2^B-A$ new integers equal to $B$.

I claim that either $n = 1$ or there must be a subset of these summing to exactly $1/2$. Indeed, suppose $n > 1$, and arrange all weights in non-decreasing order $\ell_1 \leq \dots \leq \ell_n$, and look at the running sums $2^{-\ell_1} + \dots + 2^{-\ell_i}$. There must be a first index at which they cross $1/2$, say $2^{-\ell_1} + \dots + 2^{-\ell_i} \geq 1/2$ but $2^{-\ell_1} + \dots + 2^{-\ell_{i-1}} < 1/2$. Write the latter sum as $S = A/2^B$, where $B \leq \ell_{i-1} \leq \ell_i$ and $A < 2^{B-1}$. Then $S + 2^{-\ell_i} = (A + 2^{B-\ell_i})/2^B \geq 1/2$, so $A + 2^{B-\ell_i} \geq 2^{B-1}$. Since $2^{B-\ell_i} \leq 1$, we must have $2^{B-\ell_i} = 1$ and $A + 2^{B-\ell_i} = 2^{B-1}$, so $S + 2^{-\ell_i} = 1/2$.

When $n = 1$, the code $\{\epsilon\}$ is a prefix-free code with codeword lengths $0$. For $n > 1$, divide the weights into two sets $L_0,L_1$ such that $\sum_{i \in L_0} 2^{-\ell_i} = \sum_{i \in L_1} 2^{-\ell_i}$. Construct two prefix-free codes $C_0,C_1$ from the lengths obtained by subtracting $1$ from all weights in $L_0,L_1$, respectively. Now glue these codes together by prefixing $C_0$ by $0$ and $C_1$ by $1$.


Yes, this is true. The direct implication ($\Rightarrow$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J.
9 (1962) 289-298.  Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.


If a thread containing main terminates, can another thread do anything?

While the details will depend on the actual thread model of your thread library (eg. pthreads, the POSIX thread library), some general observations hold.

Without explicit or implied syncing you have no guarantees about the serialization of threaded code. The platform running your code might execute some of the thread's code first before resuming the spawning (main) thread of the process.
The thread-creating code of your program itself is just a thread - it does not need to be distinguished from any thread it creates.
Automatic program termination after a thread ends will be most inconvenient in most settings (Imagine a multi-threaded program where one thread enters a non-recoverable error state while another thread performs a backup job). So while the code/language may lack overt syncing primitives, usually there still exist mechanisms to allow for a controlled thread termination.


Maximizing the sum from m stacks using k pop's

You can use dynamic programming to solve this problem in polynomial time.
Create a table $A[i,l]$ with $0\le i \le m$ and $0\le l\le k$, where $A[i,l]$ reprensents the optimal allocation using at most $l$ pops among the first $i$ stacks. We initiate by $A[.,0]=A[0,.]=0$ and we have the following inductive step :
$$
A[i+1,l]=\max\left\{A[i,l-t]+(t \text{ pops from stack } i+1), 0\le t \le l\right\}
$$
We can compute $A[m,k]$ in time $O(k^2m)$.


Fibonacci Heap / Binomial Heap - Decrease Key

The call takes a specific node because that's what you typically want to do. Since you're given a pointer to the node you're supposed to be changing, you don't need to find it.

Your heap is storing a set of objects ordered by priority, and you're much more likely to want to adjust the priority of a specific object ("Crap, my algorithms homework is due tomorrow – I thought it wasn't until Thursday!") than you are to want to adjust the priority of whatever object has some given priority. In any case, there might be multiple objects with the same priority. Would your version of decrease_key adjust the priority of all of them?

I'm not familiar with Fibonacci heaps but certainly with ordinary heaps, an operation of "adjust the priority of the items that have priority $k$" would, in the worst case, involve a linear search through the whole heap. The ordering of the heap items isn't strong enough to let you do better than that: for example, the largest item in the heap could be at any leaf.

In ordinary heaps, increase_key and set_key aren't a problem: just adjust the key value and then filter up or down as appropriate.


Proof of Minsky Papert Symmetrization technique

Over $0/1$ inputs we have
$$
\begin{align*}
(y_1+\cdots+y_N)^0 &= 1 \\
(y_1+\cdots+y_N)^1 &= \sum_i y_i \\
(y_1+\cdots+y_N)^2 &= \sum_i y_i+2\sum_{i<j} y_iy_j \\
(y_1+\cdots+y_N)^3 &= \sum_i y_i+6\sum_{i<j} y_iy_j + 6\sum_{i<j<k} y_iy_jy_k
\end{align*}
$$
And so on. It follows that for $0/1$ inputs, $p_{sym}$ can be written as a linear combination of $(y_1+\cdots+y_n)^0,\ldots,(y_1+\cdots+y_n)^d$, where $d$ is its degree. This linear combination can also be viewed as a polynomial $\tilde{p}$ in $y_1+\cdots+y_n$, which is equal to $p_{sym}$ for $0/1$ inputs.


Can an optimization algorithm be "universal"?

There is no heuristic that is "universal" in practice.  Which heuristic works best in practice often depends on the specific problem you're dealing with.  There's no one "silver bullet" heuristic that works great on every optimization problem.


Seeking Efficient Approximation Algorithm for Adaptation of TSP

Since this is your exercise, it sounds like you are only looking for a hint or an approach.  So, here is a hint/approach.

Let $M$ be a DFA (deterministic finite-state automaton) that recognizes all legal sequences of colors, where a sequence is legal if it doesn't contain the same color three times in a row.

Construct a new, bigger graph $G'$, formed by a "product construction" of $G$ and $M$.  The number of vertices in $G'$ will be at most the number of vertices of $G$ times the number of states of $M$, so $G'$ will be bigger but not too much bigger.

Now think about what you can do with this $G'$.  Try translating your original problem into some question about $G'$.


No. There's no algorithm to analyze the asymptotic complexity of a piece of code given as input. Being able to do that would tell you whether the code halted and that's undecidable.


It's rarely possible to prove that an algorithm is optimal. You would have to show that your algorithm takes n steps, and for some reason solving the problem in less than n steps is impossible. Even for someone who is 100 times more intelligent than you and me together.

An example is finding the maximum of n random numbers, which can done in n steps, and n steps are required because if you read n-1 or fewer array elements, then you can't know whether the last one is greater than all other elements or not.


Length of mid part of the string in Pumping Lemma

Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state $q$ to state $q$ consuming word $y$ – that is, $y$ is the word based on the symbols on the transitions going from $q$ back to $q$.

The pumping lemma says, more or less, that you can get to such a state $q$ from the initial state by consuming the word $x$ and that you can get to the final state from state $q$ by consuming the word $z$. In the middle you can go through the loop as many times as you like. Thus making the complete word $xy^iz$, where $i$ is the number of times you chose to go through the loop.


k-armed bandit - index policies vs. Q-learning

The difference between your formula and the index methods is that your formula gives more weight to recent data. If there's a lever that has large but infrequent rewards then your formula won't converge.

On the other hand, your formula will perform better than index methods if the reward distribution for some of the levers changes across time.

The next state is actually not the terminal state unless there are no more trials, so simplifying out $g * max_{a'}Q_{t}(s',a')$ is only valid if $g = 0$. But in this case $g = 0$ should work quite well.


Are universal types a sub-type, or special case, of existential types?

First, from a mathematical point of view, $\forall x:T, P(x)$ does not imply $\exists x:T,P(x)$. The implication holds if and only if $T$ is not empty. However, in programming languages, it is uncommon to deal with empty types (though it happens).

Still from a mathematical point of view, even when $(\forall x:T, P(x)) ⇒ (\exists x:T, P(x))$, the two are not the same. If you give types a set semantics, then $T_a$ is a superset of $T_e$, not the same type. (Actually it's not a superset; it's close to isomorphic to a superset.)

Let's get closer to programming language theory and see what these types actually mean. $T_a = ∀X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ is a universal type: if you have a value $A$ of that type, you can construct $A(M)$ for any $M:X$. In particular, if you have $M_1$ and $M_2$ both of type $X$, you can construct $A(M_1)$ and $A(M_2)$. In essence (and possibly in effect, depending on the language) $T_a$ is a function from types to terms. As such, the universal type provides type parametrization: one value working for all types. Universal types are at the heart of polymorphism.

The existential type $T_e = \exists X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ is quite a different beast. Given a value $B$ of type $T_e$, there is only one term $N: X$ such that $\pi_1(B) = N$, and for this term $\pi_2(B) = \{a:N, f:N\rightarrow\mathsf{bool}\}$. The existential type provides a way to hide the nature of $N$; it's saying, “There exists a type! But I won't tell you which!”. As such, the existential type provides type abstraction: one specific hidden value. Existential types are at the heart of module systems.

Don't get mislead by Haskell's forall: despite its name, it's a form of existential quantifier.

For background, I strongly recommend Types and Programming Languages (chapters 23 and 24 discuss universal types and existential types respectively). It's will provide useful background to understand research articles.


Turing Machine Decidable: What right does the definition have to say what's not in language L?

(I'll convert the comment into an answer)

First, definitions:

$L$ is a language, that is, a set of words where each word has a finite length. If all the words that ever exist are denoted as $\Sigma^*$ then any language is $L\subseteq \Sigma^*$. Words that are not in $L$ are in a different subset we denote $\overline L=\Sigma^*\setminus L$. Both $L$ and $\overline L$ can be infinite (i.e., have infinite many words). Still, each word in $L$ or in$\overline L$ is of finite length.

Now, assume that we have a TM that never goes into an infinite loop (such TMs are called deciders). If it never goes into a loop, it means that for any input word, it will either halt and accept or halt and reject.

If we used your second definition, then any $L$ will be $L=\Sigma^*$, since all the words are either accepted or rejected.

So the answer is that the first definition is correct. A decider $M$ (a TM that always halt!) splits the space of all the possible words $\Sigma^*$ into two disjoint subsets, the words that are accepted by $M$, denoted $L(M)$ and the ones rejected by $M$, denoted $\overline{L(M)}$. Again, $\Sigma^*=L(M) \cup \overline{L(M)}$, since every word is either accepted or rejected.


Given the worst-case for $n$, we can construct the worst-case for $n+1$ as follows: we do a 'swap cycle' as follows: we take $n+1$, put it in $a[0]$, and we swap $a[0]$ with the maximal element of its children, which is $a[1]$ or $a[2]$, which we again swap with the maximum element of its children and so on, until we leave the $n$-element heap, at which point we put that last element at the $n+1$-th position.

An example: the worst-case for $n=5$ is $[5, 4, 3, 2, 1]$. We swap in 6 which creates the heap $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$, after which we end up with 2, which we insert at the end: $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$.

The above method works by induction: we start from the worst result for $n-1$ elements and perform a sift-down operation in reverse, maximizing the number of swaps it has to do ($\lfloor\log(n)\rfloor$ swaps). You can't do more swaps than this, so you maximize the number of swaps after the first extract-min operation, after which you are left with exactly the worst-case for $n-1$ elements for the next extract-min operation. This implies that the number of swaps is indeed maximal.

Note that this method gives different results than you have gotten:

[1]
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 1, 3, 2]
[6, 5, 1, 4, 2, 3]
[7, 6, 1, 5, 2, 4, 3]
[8, 7, 1, 6, 2, 4, 3, 5]
[9, 8, 1, 7, 2, 4, 3, 6, 5]
[10, 9, 1, 8, 2, 4, 3, 7, 5 ,6]

However, both solutions are correct:

[5, 4, 1, 3, 2]
[2, 4, 1, 3| 5]
[4, 2, 1, 3| 5]
[4, 3, 1, 2| 5]
[2, 3, 1| 4, 5]
[3, 2, 1| 4, 5]

[5, 4, 3, 2, 1]
[1, 4, 3, 2| 5]
[4, 1, 3, 2| 5]
[4, 2, 3, 1| 5]
[1, 2, 3| 4, 5]
[3, 2, 1| 4, 5]

[6, 5, 1, 4, 2, 3]
[3, 5, 1, 4, 2| 6]
[5, 3, 1, 4, 2| 6]
[5, 4, 1, 3, 2| 6]
[2, 4, 1, 3| 5, 6]
[4, 2, 1, 3| 5, 6]
[4, 3, 1, 2| 5, 6]
[2, 3, 1| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

[6, 5, 3, 4, 1, 2]
[2, 5, 3, 4, 1| 6]
[5, 2, 3, 4, 1| 6]
[5, 4, 3, 2, 1| 6]
[1, 4, 3, 2| 5, 6]
[4, 1, 3, 2| 5, 6]
[4, 2, 3, 1| 5, 6]
[1, 2, 3| 4, 5, 6]
[3, 2, 1| 4, 5, 6]


Why is the time complexity of insertion sort not brought down even if we use binary search for the comparisons?

For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts.

Summing over $j$, you get

$$
\sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2)
$$

The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a linear amount of work per iteration. So the complexity does not change.


Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$

Derivation
Lets consider $n = 2^{(5/4)^k}$. Now we can evaluate step by step:
$$ S(n) = S(2^{(5/4)^{k-1}}) + 5/4 = S(2^{(5/4)^{k-2}}) + 5/4 + 5/4$$
Notice that every time $k$ is reduced by one since:
$$\left(2^{(5/4)^{k}}\right)^{4/5} = 2^{(5/4)^{k}\cdot(4/5)} = 2^{(5/4)^{k-1}}$$
Thus we can denote $S(n)$ as (assuming $S(2) = 0$ as base case):
$$\sum_{i=1}^k 5/4 = (5/4)k $$
Now lets solve $n = 2^{(5/4)^k}$ for $n$. Apply $\log_2$ and then $\log_{5/4}$ on both sides: $k = \log_{5/4}(\log_2(n))$ and thus $S(n) = (5/4)\log_{5/4}(\log_2(n))$.

Test by plugging it in
You can simply plug your solution in to test it.
For $S(n) = S(n^{4/5}) + 5/4$ you can obtain $S(n) = (5/4)\log_{5/4}(\log_2(n))$ by the recursion tree method (as described above). Lets plug this into our recurrence:
$$S(n) = (5/4)\log_{5/4}(\log_2(n^{4/5}))+5/4 = (5/4)\log_{5/4}((4/5)\log_2(n))+5/4$$
And by the rules of logaritm:
$$S(n) = (5/4)\log_{5/4}(\log_2(n))+(5/4)\log_{5/4}(4/5)+5/4$$
Notice $\log_{5/4}(4/5) = -1$ and things cancel out:
$$S(n) = (5/4)\log_{5/4}(\log_2(n))-(5/4)+5/4 = (5/4)\log_{5/4}(\log_2(n))$$
Our expression for $S(n)$ fulfills the recurrence. Hence $$T(n)/n = S(n) \Rightarrow T(n) = (5/4)n\log_{5/4}\log_2(n)$$
A double logarithm looks scary but if often occurs when recurrences have the form $T(n) = aT(n^\alpha) +b$.


The rule s->ct can only be done once, becuase after that there is no more s left, and from t you cannot generate more s. Thus at most one c can be generated, because no other rule generates c.

Also the rest of the grammar looks fine.


Can the House Robber problem be solved with a Sliding Window solution?

Yes you can! It's called dynamic programming, though.
Usually, the sliding window technique stores only information local to the window, but to make this work, you should store also the global solution up until the current window position.
What you store in a window (size 2?) is what the optimal solution is if you pick the last house of the window, and what is the optimal solution when you skip the last house of the window.
We call this technique dynamic programming, and not sliding window, although they have much in common.
P.S. this problem is also known as Independent Set in Path Graphs.

I don't know if you call this sliding window, but here is one way of solving it:
def window(data):
    if not data:
        return 0
    pick, skip = data[0], 0
    for window_idx in range(1, len(data)):
        pick, skip = data[window_idx] + skip, max(skip, pick)
    return max(pick, skip)

data = [14, 7, 11, 8, 13, 9, 10, 12]
print(window(data))  # 14 + 11 + 13 + 12 = 50


Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

For your problem with the array: No, there is no better algorithm.  That's the best you can do.  Any deterministic algorithm will in the worst case have to look at every array element (technically: at least $n-1$ of the $n$ elements).

This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at $n-2$ elements and hasn't found the black element yet.  Then I claim a correct algorithm has to examine at least one more array element.  If it doesn't, then look at what output it produces, and see which of those two elements it blames; you can now construct an array that puts the black element at the other element (the one it didn't blame and hasn't looked at yet).  That array will be entirely consistent with everything the algorithm has seen so far, so the algorithm will produce the wrong output on that array.

For your problem with the camera video: In real life, there are much better techniques available.  For instance, you can do "change detection" to find the frames in the video that are different (show a change from the previous frame) and look only at those.  There are more sophisticated things you can do, but this illustrates that in practice you can often do much better, by taking advantage of domain-specific information about video surveillance.


How to solve cubing, batching, and routing problem together?

First, you need to understand how you are going to pick. That means, in one tote, do you want only one order or multiple items of different orders can end up into one tote. If it is latter, is there any sorting or consolidation area to separate out?
Is it like one order must go into one carton?
After we have those answers, I would always prefer first cubing and then, according to our strategy, pick them, and for the optimal path, obviously use VRP.
Prefer using https://or.stackexchange.com/


Giving a regular expression for a situation of a question

Here's a rough sketch: let $S_a, S_b, S_c$ be the set of valid strings of the language starting with $a, b, c$ respectively. Observe that:

$\qquad S_b = ((a^* + c^*)b)^*$

Furthermore:

$\qquad S_a = aS_a + bS_b$

and symmetrically for $S_c$. Therefore we may replace $S_b$ in the latter, obtaining a "recursive" equation solvable by Arden's lemma.


You are given algorithm $ALG$ for optimization problem $\mathcal{P}$ and and cost function $\mathcal C$.

You can define cost of optimal algorithm $OPT$ as:

$C(OPT(I))=\min_{O\in F(I)}\mathcal C(I,O)$, where $I$ is valid input, $F$ is a feasible solution on input $I$ and $O$ is the output associated with that feasible solution.
Then you can define cost of c-competitive algorithm as:

$\mathcal C(ALG(I))\le c\cdot \mathcal C(OPT(I)) + \alpha$,

Where $\alpha$ arbitrary is constant, if $\alpha = 0$ then we are talking about strictly c-competitive algorithm


Finding all solutions to subset sum for integers with bounded weights

The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A_{k,w}$ contains enough information to enumerate all subsets of $\{w_1,\ldots,w_k\}$ summing to $w$. When $k = 0$, this is trivial. Given $A_{k-1,\cdot}$, $A_{k,w}$ points at the two cells $A_{k-1,w},A_{k-1,w-w_k}$ (if they exist). The second pointer is also annotated with $w_k$. If you look at $A_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A_{0,0}$. This can be done using a simple recursive procedure.


The problem must have said that there is at most one node such that, if its value is $x$, "there is at least one value less than $x$ on its right branch or at least one value greater than $x$ on its left branch". Otherwise, any binary tree could be "a slightly broken BST tree". It is not possible to construct a BST in $O(n)$ from random $n$ values in general.

Here is the explanation for an $O(n)$ algorithm.

First, as you should have observed, we can concentrate on the subtree with the broken node as the root. Let us assume that the root of the tree is the broken node.

Perform in-order traversal on the left subtree to list all values in the left subtree. Perform in-order traversal on the right subtree to list all values in the right subtree. Merge these two ordered list. Insert the value of broken node. Now we get all values in an ordered list.

Now traverse the whole tree in-order. In other usual situations we will print its value when we visit a node. Instead, we will  replace the values of nodes using the successive values in that ordered list when we visit the nodes.

It is clear that each step above takes $O(n)$ time.


For two sets of points find if second one is result of linear transformation of the first

In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters.  Thus, the transformation is uniquely determined if you have two points $p_1,p_2$ from the first set and two points $q_1,q_2$ and if you know that $p_1$ transforms to $q_1$ and $p_2$ to $q_2$.  You can find this linear transformation explicitly by solving a system of linear equations.
Consequently, the following algorithms works:

Pick two points $p_1,p_2$ arbitrarily from the first set.
For each possible way to pick two points $q_1,q_2$ from the second set:

Find the unique linear transformation $T$ that maps $p_1$ to $q_1$ and $p_2$ to $q_2$.
Check whether applying $T$ to the first set gives you exactly the second set.  If so, output $T$ and halt.

If you reach this point, output that no such linear transformation exists and halt.

This algorithm is guaranteed to be correct: it will find the linear transformation, if any exists, because we have tried all possible pair of points that $p_1,p_2$ could match with.
The worst-case running time is $O(n^3)$, if $n$ is the number of points in each set.  That's because you loop over ${n \choose 2} = O(n^2)$ pairs of points in step 2.  Each iteration of the loop involves solving a system of four linear equations (takes $O(1)$ time) and checking whether it is a valid solution (could take $O(n)$ time in the worst case, since you might have to apply $T$ to each point in the first set).
However, heuristically, I expect the running time will typically be $O(n^2)$.  That's because typically you can reject most candidate transformations $T$ immediately: if you apply $T$ to one point in the first set, and get a result that is not in the second set, you can reject $T$ without applying it to any other points in the first set.  Thus, heuristically, I expect that typically each iteration of the loop will usually complete in $O(1)$ time.  That said, there do exist arrangements of the points where this is not correct.
The generalization of this algorithm is RANSAC, which can handle the situation where most points of the first set can be matched to the second set but some cannot.


Analysis of Dijkstra algorithm's (Lazy) running time

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s.
The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges).
Same with the log factors, although in that case it doesn't matter as much since $O(\log |V|) = O(\log |E|)$ (if the graph is connected).
Via simple multiplication this gives you $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.
In a dense graph, this is already the desired complexity. Since a dense graph has $O(|V|^2) = O(|E|)$.

However in a sparse graph, e.g. when $O(|E|) = O(|V|)$, then you can still do a lot better.

The problem you are facing is that multiplying the upper bounds can lead to overestimation. Look at the following example:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

The outer loop clearly runs $O(N)$ times, and the inner loop runs also $O(N)$ times (because in the worst case it does).
You can say that in total the complexity is $O(N^2)$ times. But this is just an upper bound.

Most of the time the inner function actually does almost no work.
In reality if you count the number of times you run the function constant_work(), you will get
$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$
$N$ iterations for i == 1 and otherwise only $1$ iteration.
So the code runs in $O(N)$ time.

The same effect happens when you loop over edges next to a node: for (Edge edge : graph.adj(min)).
Yes, in the worst case you have $O(|V|)$ edges, but in a sparse graph, most of the time you have a lot less.

You can count them from a different angle. If you fixate an edge $(u, v)$, how often will you touch that edge, and move into the body of the loop?
Only twice! Once when min == u, and once when min == v.
Therefore the inner part of the loop, with runtime $O(\log |V|)$, will run only $O(2 |E|) = O(|E|)$ times. Which means that the whole thing runs in $O(|E| \log |V|)$.


Lambda calculus simplification excercise

It is better to remind ourselves the Lambda calculus precedence rules first. See https://stackoverflow.com/q/4794330/9939883 for better details about precedence.
Application has higher precedence than Abstraction. Application is left associateive and Abstraction is right associative.
(λx.λy.y x) z (λw.w)

Since application has higher precedence,
(λx.λy.(y x)) z (λw.w)

Since application is left associative
= ((λx.λy.(y x)) z) (λw.w)

Applying repeated abstractions
= (λy.(y z)) (λw.w)

= (λw.w) z

= z


The correct analogy for higher levels of the polynomial hierarchy is that of a game between two players, the $\exists$ player and the $\forall$ player. The $\exists$ player wants to prove that the input is in the language, and the $\forall$ player wants to disprove it.

For a language $L \in \Sigma_k^P$, the game is as follows. On input $x$, the $\exists$ and $\forall$ players alternate in presenting strings $y_1,y_2,\ldots,y_k$ (the $\exists$ player starts). After $k$ rounds, the referee runs a polynomial time procedure $f$ (set in advance) on $x,y_1,\ldots,y_k$, and declares $\exists$ to be the winner if $f$ returns YES, and $\forall$ to be the winner if $f$ returns NO. Since $L \in \Sigma_k^P$, when $x \in L$, $\exists$ has a winning strategy, and when $x \notin L$, $\forall$ has a winning strategy.

For a language $L \in \Pi_k^P$, the only difference is that $\forall$ starts.

When $k = 1$, there is no communication, and so we can talk in terms of witnesses. For larger $k$, we can still use the witness terminology, but with different semantics. Consider again $\Sigma_k^P$, for $k = 2r$ or $k = 2r+1$. The witness of $\exists$ consists of $r$ functions $Y_1,Y_2,\ldots,Y_r$ which are used to generate the strings produced by $\exists$ as follows: $y_1 = Y_1(x)$; $y_3 = Y_2(x,y_1,y_2)$ (or $y_3 = Y_2(x,y_2)$, since $y_1$ is known); and so on. You can think of these functions as implicit witnesses, since $\exists$ doesn't reveal the entire functions $Y_2,\ldots,Y_r$, but only the relevant values.

For $x \in L$, the property that these witnesses satisfy is that for any reply by the $\forall$ player, the referee declares $\exists$ to be the winner. For $x \notin L$, the $\forall$ player has a similar kind of witness. Thus "witness" here is really the same as a winning strategy.


Proving correctness of a loop that calculates the sum of array

I think your postcondition is wrong. Since index i is initialized at 0, you're actually summing from 0 to n, not from 1 to n. The postcondition, lets call it $P$, should be:

$$ j = \sum_{k=0}^{n} a[k] $$

Or:

j = sum(a[0] ... a[n])

Usually you would write $B$ as $i \neq n+1$ instead of $i \le n$, because it makes the proof easier. In that case, you would choose $Q$ as (assuming array indexing starts at 0):

$$ j = \sum_{k=0}^{i-1} a[k] $$

Or in your notation:

j = sum(a[0] ... a[i-1])

Then $ Q \land \lnot B \implies P$ is true because you can substitute $i$ by $n+1$. Of course, you would have to prove that $Q$ is a valid invariant, but I'll leave that to you.

In your case,$\lnot B$ is $i>n$ instead of $i = n + 1$, so you can't use substitution. You can deal with the inequality by adding information to the invariant and then proving $i = n +1$ using this new information. Our new invariant $Q'$ could be:

$$Q \land i \le n+1$$

This new condition holds before the loop starts because $i$ starts at 0 and $n+1$ must be at least $1$.To prove that $Q'$ is a valid invariant, we have to show that it also holds after every iteration. Each time the loop executes $i$ changes to $i+1$, so we must prove that $ i+1 \le n+1$, which is true because the loop condition states that $i \le n$ was true when the iteration started.

Now we know that $Q \land i \le n + 1 \land i > n$ holds after the loop ends. And since $i \le n + 1 \land i > n \implies i = n + 1$ and $Q \land i = n + 1 \implies P$, the program is correct.


I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

This would fall under something called black box optimization. In general, there are several methods you could try in practice such as (stochastic) hill climbing or say a genetic algorithm. Such methods might seem "random", but they take some care in moving in a smart way but also use some "randomness" to escape local optimums.


Is the time complexity of the Fibonacci sequence O(fib(n))?

$\DeclareMathOperator{\fib}{fib}$If you choose to calculate $\fib(n)$ by using the naive recursion
formula, then you need $\Theta (\fib(n))$ additions, and since the
numbers involved grow to $c\cdot n$ bits for a not very large constant
$c$, it will take $\Theta(n \cdot \fib(n))$ operations.  (I may be wrong
here because most of the numbers involved may be much smaller than $c
\cdot n$ bits).
If you are reasonably clever and calculate
$$\fib(0), \fib(1), \fib(2), \dots, \fib(n),$$
then you have $n$ additions of $c \cdot n$ bit numbers, which takes
$\Theta(n^2))$ operations.
You can use matrix exponentiation to calculate $\fib(n)$ faster for
large $n$, I'd estimate something like $M(n)$ where $M(n)$ is the time
for an $n$-bit multiplication.
Most important is that for maybe $n = 100$ or $n = 200$, your computer
has not a chance to calculate $\fib(n)$ using the naive recursive
algorithm within your lifetime, while the simple method of calculating
consecutive values will find the same result within microseconds on a
newish smartphone.


What is the difference between RAM and TM?

Turing machines are not as efficient as RAM machines. A RAM machine can access an arbitrary tape location in $O(1)$. A Turing machine can't. A RAM machine can do arithmetic in $O(1)$ (under certain restrictions). A Turing machine can't.

Turing machines polynomially simulate RAM machines, that is, for some constant $c$, any RAM machine running in time $O(n^k)$ can be simulated by a Turing machine running in time $O(n^{ck})$. (The constant is pretty reasonable, about $2$, depending on the Turing machine model.)


Linear optimization or Constraint Satisfaction Problem with food

I suggest you use integer linear programming.

Suppose you have $n$ recipes.  Introduce zero-or-one variables $x_1,x_2,\dots,x_n$, with the idea that $x_i=1$ represents including the $i$th recipe and $x_i=0$ represents omitting it.  Now you can obtain a bunch of linear equations, one per macronutrient requirement.  For instance, in your example, we get something like $c_1 x_1 + \dots + c_n x_n = 30$, where $c_i$ is the number of grams of protein contributed by the $i$th recipe.  Feed this to an off-the-shelf ILP solver, and hopefully it will find a solution for you.

If you're willing to eat multiple servings of a single recipe, you can relax the constraint on each $x_i$ and require it to be an arbitrary non-negative integer ($x_i \ge 0$), instead of requiring that it be 0 or 1.

Your problem is basically a multi-dimensional subset sum problem.  That's a special case of the multi-dimensional knapsack problem, which is NP-hard.  There  have been people who have studied algorithms for the multi-dimensional knapsack problem, but my guess is that the pragmatic solution is to start by trying an off-the-shelf ILP solver, and studying the literature only if that doesn't work.

Related: 2 Dimensional Subset Sum: looking for information.  Also, your problem has been proved to be NP-hard if we allow the requirements to include large numbers: What algorithms exist for solving natural number linear systems?. (In technical terms, the problem is NP-hard when the macro-nutrient requirements and properties are provided in binary.  I don't know if it remains NP-hard when they're provided in unary -- and the latter seems more relevant for practical situations.)