Are these valid counterexamples to proofs for CF languages with Non-CF complements?

For the first question, $aaabaa$ is generated by the grammar:
$$\begin{align*}
    S&\to AB \\
     &\to aB &&\text{using }A\to a\\
     &\to aaBa &&\text{using }B\to aBa\\
     &\to aaaBaa &&\text{using }B\to aBa\\
     &\to aaabaa &&\text{using }B\to b\,.
\end{align*}$$
Your attempt to prove the converse is incorrect because you assume that, when the string is split as $AB$, the part generated by $A$ must have the same length as the part generated by $B$. As the derivation above shows, this is not true.

For the second, you're correct that the class of deterministic CFLs is not closed under union. However, the class of CFLs is closed under union. That is, the union of two DCFLs is not necessarily a DCFL but it is definitely a CFL. The argument "$\overline{A}$ and $\overline{B}$ are deterministic context-free, so they are context-free, so $\overline{A}\cup\overline{B}$ is context-free" is implicit in the proof you quote.


Measuring the difficulty of a sequence-to-sequence problem using automata theory

Finite-state transducers capture a class of seq2seq problems that correspond to the notion of regular languages, which could be thought of as the "easiest" problems in automata theory.  Your example function $f$ can be implemented by a finite-state transducer.


Is there a name for the class of algorithms that are the most efficient for a particular task?

You can say that an algorithm is asymptotically optimal in such a case.

In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.


The monograph Digraphs: Theory, Algorithms and Applications by Bang-Jensen and Gutin defines a bipartite digraph as a digraph whose vertices can be partitioned into two sets $A,B$ such that every directed edge connects a vertex in $A$ to a vertex in $B$ or vice versa. Alternatively, a bipartite digraph is a digraph which can be obtained from a bipartite graph by replacing each undirected edge by a directed edge or by a pair of directed edges.

In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.


Longest Common subsequence theorem in CLRS

The theorem is used to construct a recurrence relation for computing the LCS of $X$ and $Y$. The first point states that if $x_m = y_n$, then one possible LCS of $X$ and $Y$ is an LCS of $X_{m-1}$ and $Y_{n-1}$ together with $x_m$. This is one of the cases in the recurrence relation.

You ask why we are not considering $Z$ as the LCS of $X$ and $Y$. There is no need to consider this, because this is already assumed to hold in the premise of the theorem. Given that, we want to deduce other information, which will later enable us to compute the LCS recursively.


Intersection of a language with a regular language imply context free

In a nutshell

Using closure with one regular language ($\exists P \text{ regular such
 that }L\cap P$ is context-free)  as apparently envisioned in the
question does not work. Indeed, for any language $L$ there is a
regular language $P$ such that $L\cap P$ is context-free. So there is
no way a family of languages can be characterized by this property,
other than the family of all languages on an alphabet $\Sigma$, i.e.,
$2^{\Sigma^*}$.
Using a more universal closure property with all regular languages
(universal quantification: $\forall P \text{ regular, }L\cap P$ is
context-free) does not work either. But, to prove the context-free (CF)
property for intersection with any regular set, you have to prove it
in particular for the regular set $\Sigma^*$. But $L\cap\Sigma^*=L$,
so that you are back to the initial problem of proving that $L$ is
CF. This is quite simple, and is not further developed below.
The language you are interested in, $A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$, is indeed
context-free. A simple way to establish that is to build a
non-deterministic PDA that recognizes it. Intuitively, such a PDA
could first work as if recognizing  $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$, then switch non-deterministically to the
transitions of a PDA recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$ while keeping the same stack.
Following site policies, I would also suggest you look at
the reference answers to frequently asked questions on this topic,
and in particular to How to prove that a language is context-free?.

Using closure as proposed in the question does not work

This is an answer to the first question, since you are actually asking
two questions, about using the property of clusre of CF languages with
regular sets. You are actually using the property backward, which is
not permissible.

There is a very simple counter-example. If you take any language $L$, and
any finite subset $R\subset L$, the language $R$ is regular, since all finite languages
are regular, and is also context-free since all regular languages are
context-free. But $R\subset L$ implies $R\cap L=R$. There is always such a subset $R$ since the empty language $\emptyset$ is regular and is a subset of any other language.

Hence for any language $L$ there is a regular language $P$ and a CF
language $T$ such that $L\cap P=T$. You only lave to take $P=T=R$ for
some finite subset $R\subset L$ (including the empty one).

Note that this still works when $L=\emptyset$.

The property you are trying to use is a trivial property, in the sense
that is is true of any language, without exception. Hence, you cannot infer from it alone any specific property that is not equally trivial.

I use finite subsets because they always exists, while some languages do not have infinite regular subset. Infinite regular subsets work too, when they exist.

Proving that your language $A$ is Context-free

$A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$

There are various ways a language can be proved to be CF. It is always
possible to do it with closure properties, because of the
Chomsky-Schutzenberger representation theorem ... but that does not
mean it is easy.

My suggestion is to build a PDA, actually a non-deterministic one.  I
have not proved it (so take this with care), but I suspect it cannot
be recognized by a deterministic PDA.

If you had to have as many $a$ and $b$, you would use the stack to
count the extra $a$'s or the extra $b$, so that you can match the
numbers. If you wanted twice as many $b$'s, you would count 2 $b$'s
for one $a$, which you can achieve by pushing two $a$'s on the stack
for each extra $a$, and matching each with a later $b$, or by matching
the $a$ just read with two $b$'s from the stack (I am skipping
details). Since you want something in between, you can arbitrarily decide
for each $a$ whether it matches one $b$ or two $b$'s.

There is however a much simpler solution (at least simpler to explain) which I give in the next section. But I decided to leave this one as it may be instructive too.
So you may choose to skip to the next section.

You also have to be careful that at least one $a$ matches two $b$'s, so
that you have strictly more $b$'s than $a$'s, and that at least one
$a$ matches a single $b$ so that the number of $b$'s is strictly less than
twice the number of $a$'s.

The stack bottom is supposed to be $\$$.
The behavior is the same for all states, which are used only to
remember an $a$ has matched one $b$, and whether another $a$ has matched
two $b$'s.

So you have 4 states: initial $q_0$, then $q_1$ when an $a$ has
matched a single $b$, $q_2$ when an $a$ has matched two $b$'s, and $q_b$
when both have occured, which is a requirement to accept thhe string.

When reading an $a$, you decide non-deterministically whether it must
match one $b$ or two $b$'s, and possibly change the state acordingly.

If you decide for a single $b$:

If the top of stack is $b$, you just pop that $b$
otherwise you push the $a$ on the stack to be matched with a later
$b$.

If you decide for two $b$'s:

If the top of stack is $bb$, you just pop these two $b$
(this can be decomposed into two pops, if your PDA model requires
it, by introducing other states)
if the top of stack is $b$ with no other $b$ in second position,
you pop that $b$ and push an $a$.
if the top of the stack is not a $b$, you just push 2 $a$'s.

When reading a $b$, you just try to match it on the stack:

if the top of the stack is an $a$, just pop it.
otherwise push a $b$ on the stack.

If you reach the end of the input with an empty stack and state $q_b$,
then you accept.

Alternative simpler solution

Actually, you do not need to have a PDA that is non-deterministic
on each input $a$, and you can make a single non-deterministic choice.

The idea is that you start the PDA working as if it were recognizing
 $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$

Then, after reading at least one $a$, you continue recognition as if
you were recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$
and must scan at least one $a$ in that phase.

Of course, this is a single PDA. and you do not change the stack as you switch the recognition mode.

You accept on empty stack.

Note that this does not imply that the string recognized is the concatenation of a string in $A_1$ and a string in $A_2$. The string could be all $a$'s followed by all $b$'s, or the reverse, as long as the number of $a$'s and $b$'s is right.


Associativity vs blocks per set in fixed size caches

The number of sets determines the size of the index, because the index tells you what set to refer to.  If you increase associativity by giving more blocks to each set then you run out of blocks sooner and so you can afford fewer sets.  If you have fewer sets then you have a smaller index.

If half the sets disappear then those addresses have to be handled by the remaining sets.  Because each set now has more addresses that it serves, it needs an extra bit of tag to distinguish them.


A* to find the longest path in a directed cyclic graph

First of all, bear in mind that the Longest Path Problem (LPP) is a NP-complete problem whereas finding the Shortest Path Problem (SPP) is a problem known to be in P. The proof for the NP-completeness of LPP is trivial and consists of a reduction from the Hamiltonian Circuit (HC) problem which is already known to be NP-complete.

In other words, if you could find a simple way (in the sense of the modifications taking only polynomial time) to modify A* to solve the LPP problem you would actually make a nice discovery! :)

This is not to say that A* can not be used, but it should be expected to take longer. I recently co-authored a paper about the "Target Value Search Problem" with other two people. This problem is stated as follows:

Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$.

Obviously, if $T=+\infty$ then you are seeking the longest path between any arbitrary pair of vertices, $s, t$. If, in addition, $s=t$ then you are looking for the longest path that joins both vertices. You can verify in $O(1)$ whether the length equals the number of vertices. If so, you found a Hamiltonian path.

Regarding your questions:

Q1: Can this be done with $A^*$? Certainly yes (indeed, we modified A* to get T*, our implementation of the Target Value Search problem that can be used to solve this variant) but you should not expect for it to be as fast as when solving SPP. As a matter of fact, we provided a simple modification of A$^*$ that can be used to solve the LPP as well (and it is certainly complete but terribly inefficient)
Q2: Is setting the weights negative the right thing to do? Well, the real problem is that you need a heuristic function that returns an upper bound on the path to the goal $t$ instead of a lower bound (as when solving the SPP) and these sort of heuristics seem particularly hard to derive (how would you do it? there is no concept such as "relaxation" here, maybe you should constraint the problem further to derive a heuristic)
Q3: Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it? Well, you can do it but that is just a brute-force approach. Note that this approach forces you to consider all paths. Even if you find a path which seems to be too large you are still forced to expand other nodes in OPEN until you CLOSE them all. In the absence of a heuristic that is all you can do. This is, indeed, what our variant of A* for the Target Value Search problem does if $T=+\infty$ ---however $T^*$ is more efficient even to solve LPP.

Hope this helps,


How to find middle element of doubly linked list using head and tail?

Start with a pointer $x$ at the beginning and a pointer $y$ at the end. Repeatedly execute the following steps:

If $x=y$, stop.
Advance $x$ forward.
If $x=y$, stop.
Advance $y$ backward.

This should work out for both even and odd length.


Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

The smallest formula with $n=10$ can be written as follows:

$(x_1\rightarrow(x_2\rightarrow x_3))\land(x_1\rightarrow(x_3\rightarrow x_4))\land(x_1\rightarrow(x_4\rightarrow\overline{x_2}))\land$
$(x_1\rightarrow(\overline{x_2}\rightarrow x_5))\land(x_1\rightarrow(x_5\rightarrow x_6))\land(x_1\rightarrow(x_6\rightarrow x_2))\land$
$(\overline{x_1}\rightarrow(x_2\rightarrow x_7))\land(\overline{x_1}\rightarrow(x_7\rightarrow x_8))\land(\overline{x_1}\rightarrow(x_8\rightarrow\overline{x_2}))\land$
$(\overline{x_1}\rightarrow(\overline{x_2}\rightarrow x_9))\land(\overline{x_1}\rightarrow(x_9\rightarrow x_{10}))\land(\overline{x_1}\rightarrow(x_{10}\rightarrow x_2))$

It satisfies all of the restrictions.

As you can see, it is just two unsatisfiable 2-SAT formulas one of which is implied by $x_1$ and another by $\overline{x_1}$. We can add arbitrary amount of vertices to any of these implication chains, so, generating such formula for any $n\ge10$ can be done in linear time.


Is there a "natural" example of a total, computable but non-primitive recursive function?

This answer gives us a hint, namely that an interpreter for a language more powerful than primitive recursion, is itself not primitive recursive. For example, System F has no self-interpreter, and thus any interpreter for System F is not self-recursive.

This then extends to Turing-complete languages: JavaScript, Python, Ruby, etc. Any interpreter you run is utilizing functions more powerful than primitive recursion.


Recall the definition of dominators:

$$\hbox{Dom}(n_o) = \{ n_o \}$$
$$\hbox{Dom}(n) = \{ n \} \cup \bigcap_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$

This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.

It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.


Think carefully about the flow.

Your innermost While loop runs through b = 1, 2, each time it hits.

It does this for EACH value of a in the outermost loop.

So when a == 2, we progress inward and run through that loop twice. a == 2 both times.


Benes (Fat Tree) Network for number of inputs/outputs that is not 2^n

Wasting ports to achieve an exact number of terminals is a common attribute of staged networks (butterfly, benes, folded-clos, etc.). The mesh, torus, and flattened butterfly topologies are a bit better because each dimension can have a different width, but this results in having uneven bisection bandwidth along each dimensional cut. The HyperX topology is a generalization of the flattened butterfly that allows each dimension to be configured independently in terms of width and weight (number of links connecting each pair of routers). The paper describes an algorithm to find the "optimal" configuration given a requirement for system size, bisection bandwidth, and router radix. An implementation of this algorithm is here. Given the requirements, it finds a satisfactory topology configuration that minimize cost (like wasted ports).


Tree structure that is like a quadtree/octree but splits a different number of times in each dimension?

You could use a k-d tree.  A k-d tree normally alternates between partitioning horizontally and partitioning vertically, but you could certainly modify it to change that pattern (e.g., partition horizontally twice in a row; or equivalently, partition horizontally into three or four regions rather than just into two regions).

Not everything has a "name".  There are many more possible algorithms and data structures than there are "names".  So don't take it as some kind of negative if you can't find a "name" for it.  "Modified quadtree" or "modified k-d tree" will do fine, if you need a way to refer to it.


What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

This is called the reachability problem -- is it possible for a given system to enter a given state?

Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking.

As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering questions about the runtime behavior of programs from only their source code is almost always undecidable. Nonetheless, there are many attempts to solve these problems that can be fairly effective in "real world" code (e.g., Microsoft's 2002 project SLAM), because human programmers tend to try to make their code easy to understand (for other humans; we hope incidentally also for mechanical analysis)


Student Course Allocation Problem with Many Constraints

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic.

I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and crossover operations that at least try to respect restrictions).


How does the OS know the physical address of a process' first memory page?

The operating system performs a lot of work before executing the first instruction.  The OS must set up at least two data structures, the page table and the region map.  The region map is called different things in different operating systems.  Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a red-black tree) that gives you an efficient way of discovering the region a specific virtual addresses belongs to.

Each memory region has a start address, a length, permissions (can the program read/write/execute from the region), and some information about the "type" of the region, including how the region is supposed to be initialized on first use and how the logical information is supposed to be saved if a mapped page needs to be moved to disk.

The first step is that the operating system creates a new page table with every virtual page marked as "invalid."  Next the OS reads the header of the executable file.  The header describes the region map and also gives the virtual address of the first instruction to be executed.  So the OS creates an in-memory region map to match the structure described in the executable header and then tries to execute the first instruction (it does this by using some kind of "return from interrupt" instruction that sets the root of the page table to the page table for the process we want and then changing the program-counter (instruction-pointer) to the virtual address of the first instruction.

So the processor tries to execute the instruction at the given virtual address.  But every page in the page-table is marked invalid, so when the processor performs the translation from virtual to physical address the processor will invoke an "invalid page" fault, bringing control back to the operating system.  The operating system will look up the virtual address in the region map.  Since this was supposed to be the address of the first instruction, then it should be the case that the virtual address is contained in a region that is marked as being executable, and there should be information about where the instructions are located in the original executable file.  The OS reads a page-worth of date from the original executable file into some physical page in memory, and then modifies the page table to reflect the new virtual-to-physical mapping.  Finally the OS again tries to return-from-interrupt to the instruction address.  This time, although there will be TLB misses and cache misses, the translation will give a mapping from virtual to physical address, the processor will eventually try to fetch the required instruction into the L1 cache and execute it.

In all likelihood the instruction will try to access some not-yet valid data location.  There will be another "invalid page" fault for the data's virtual address.  The OS will look up the data's virtual address in the region map, allocate a physical page, initialize the page, map the page in the page table and then return-from-interrupt a third time.  This time the instruction will get fetched and executed, and after another TLB and cache miss for the data access will actually execute without causing another fault.  Then we move to the next instruction and start all over again.

Hopefully we have some spatial and/or temporal locality so this process doesn't happen with every instruction.


A* without heuristic more efficient than Dijkstra

It depends how you implement Dijkstra.  The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient.  A* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them.

This means that, especially in sparse graphs (such as road maps, which are almost planar), UCS has a much lower memory footprint, which can make it considerably faster.  Also, the various operations on the queue are much faster, since the queue is typically much shorter.

There's more information in Ariel Felner's paper Dijkstra's algorithm versus uniform cost search or a case against Dijkstra's algorithm (Proceedings of 4th International Symposium on Combinatorial Search, SoCS-2011, AAAI, 2011).

By the way, straight-line distance is probably a very good heuristic for A* in your situation.


Creating a Deterministic Push-Down Automaton for the Union of two languages

There is no general algorithm for computing a DPDA $M^*$ as the intersection of two DPDA $M,M'$; that problem is undecidable.  See Undecidable problem intersection of two DCFL languages is DCFL? for a proof.

So, you will have to look for some pattern in this particular problem that makes it easier than the general case.  Hint: what level in the Chomsky hierarchy is $L_1$ at?  what about $L_2$?


It turns out that the problem is eqivalent to the 1-perfect code problem in cubic graphs. Therefore, Deciding the existence of decomposition of a cubic graph into vertex disjoint claws is NP-complete.


Build a regular grammar for a regular language

The expression always starts with 1a. There are two options, the third character in the string is a or not. If it is a, then you don't have the obligation of following 'it contains at least one a'. Otherwise, you need to. Thus the regular expression is:

    1aa(1+a+b)*+1a(1+a+b)*aa(1+a+b)* .

The conversion from regular expression to automata to regular grammar is standard. One possible algorithm is given here: https://math.stackexchange.com/questions/574571/build-regular-grammar-from-regular-expression

Here is an intuitive way to convert a regular expression to a right linear grammar:

Convert the regular expression to an NFA. This is standard (see page 102 of Automata Theory, language and computation, 3rd ed).
To convert the NFA to a right linear grammar, take the states to be non-terminal and the alphabets to be terminal. For a transition of the form S -> S' via a, add the production rule S -> aS'. Please note that you need to take care of the final states and epsilon transitions separately.

You can also convert the NFA to a DFA (again, standard subset construction method, see the aforementioned book) and then the method will be simpler.


How do i prove this language is regular?

Build a finite state machine. Or look up the definition, your definition will either say "there's a finite state machine", or "it's defined by a regular expression".


Find list of tickets with best price sum

If you wanted to solve it in practice, I would recommend that you try using an ILP solver.  You can express this as an instance of integer linear programming, then use an off-the-shelf ILP solver.
Introduce zero-or-one variables $x_i$ (indicates whether the $i$th ticket is bought or not) and $y_{ij}$ (indicates whether the $i$th ticket is used to cover the $j$th trip).  Then you can write linear inequalities to express the requirements; e.g., $\sum_j y_{ij} \le d_i x_i$ where $d_i$ is the max duration of ticket $i$, and so on.  The total price is a linear function of the variables, so you can minimize that objective function, subject to these inequalities.
I don't know whether there is a more efficient algorithm.


Search for numerical solutions of underdetermined systems of quadratic equations

This is a bit late for you, perhaps, but it might be worth looking at cylindrical algebraic decomposition. CAD takes a general statement in the real closed fields (i.e. an arbitrary boolean statement involving equalities and inequalities), and returns a finite set of "solutions", each of which is a "procedure" to find those solutions by assigning the unknown variables.

I haven't tried it on your example (because I don't have any software handy to do it!), but as an example, here is the CAD of $x^2 + y^2 = 1$:

$-1 < x < 1\,\wedge\,y = \sqrt{1-x^2}$
$-1 < x < 1\,\wedge\,y = -\sqrt{1-x^2}$
$x = -1\,\wedge\,y = 0$
$x = 1\,\wedge\,y = 0$

There are four "solutions" in this decomposition, and each one gives you a way to find it, by first determining an assignment to $x$, and using that to get an assignment to $y$.

This would work extremely well if you knew which variables were going to be constrained, because you could specify that they appear first in each "solution". In this case, if you added the constraint that $x = 0$, you would just go through each solution and find that $y=1$ and $y=-1$ are the only solutions, since the last two don't apply.


Hint: There is deadlock in the wait-for graph if the graph has directed cycles (why?). Perhaps topological sort is useful for detecting these.


Algorithm for determining minimal set of covering prefixes

Your algorithm will work. The information you will be looking for can be found in the prefix tree (trie) will hold the information you are looking for.

Despite similarity in names, the set cover and this problem are not similar. The first is NP-Hard. This one is not.

However (in relation to Point 3 of your algorithm), a tree node that is not a leaf may be the end of a word $w$ contained in other words (e.g. "be" contained in "bee" "behavior" etc .. ). You should take into consideration when counting.

Point 4: Now we know each prefix and how many matches it has - I believe complexity is $n \log n$ .. why ? I dont think so. It is $O(n m)$.

Point 6: I dont know though why you want to sort. You can find the max (which is $O(n)$).

If you are going to present the tree in a relational database, then make sure you present it in a good way. For instance, try to make the whole tree in a single page, or close nodes in the tree in the same page. This is to minimize the I/O cost.  How to do that ? I honestly don't know. For me, I would just put it the prefix tree in a single binary file. Or a seriazable data structure.


Which article in front of O(.), Ω(.), ...?

Write it as you pronounce it: "an omega". Or, especially when it can be pronounced with a vowel or consonant, rephrase to avoid the issue: "a bound of..."


How to obtain the camera extrinsic matrix without using chessboard

I think the answer is yes, it is possible to get the extrinsic matrix of hte camera with just a single square, though the error might be higher as there is less redundancy.  Let's look at how much information we obtain:

How many unknowns?  The extrinsic matrix has 5 real-valued parameters (the rotation matrix has 2 angles; the translation matrix has a 3D location).  In other words, there are 5 degrees of freedom or 5 unknowns.
How many equations?  We obtain 8 equations/constraints.  I am assuming we know the 3D location of each corner of the square (in world coordinates).  We also know the 2D location of each corner (in image coordinates).  The camera matrix maps each 3D point to the corresponding 2D point.  So, each point gives us 2 equations (from the known 2D image coordinates), and there are 4 corners, so we get 8 equations.

In short, we have 8 equations in 5 unknowns.  That's enough that it should be possible to recover the extrinsic matrix.  Of course, there's not a lot of redundancy here, so the error might be higher than if you used a chessboard.  A chessboard would provide a lot more equations (each corner inside the chessboard provides an additional point with a known 3D->2D mapping).

How would you recover it?  Follow the guidelines in https://ksimek.github.io/2015/03/29/QA-recovering-pose-of-calibrated-camera/.  In particular, you could solve for the 5 parameters of the extrinsic matrix using some optimization routine, such as gradient descent or L-BFGS.

Given some value for those 5 parameters, you can compute the camera matrix and map the 3D world coordinates of each corner to its corresponding 2D image coordinates; then you can compute the $L_2$ error (sum of squared error) between the inferred 2D coordinates and the known 2D coordinates from the picture.  This gives you an objective function that maps a value for the 5 parameters to an error term (which you want to minimize).  Next, you can apply any off-the-shelf optimization library to try to minimize this objective function.  This sounds pretty doable, with not too many lines of code to implement.


Could an artificial neural network algorithm be expressed in terms of map-reduce operations?

Yes it can, and has been. In the paper Map-Reduce for Machine Learning on Multicore they discuss using the Map-Reduce paradigm for several common ML algorithms including ANNs.


Which one is the correct way to change functional notation while solving recurrence relation?

"Why we can change any recurrence relation like this?"

Answer: by the definition of function. This is about pure algebra.

Let me explain slowly and clearly. (To someone who just learned the definition of function, I should probably explain much slower with more explanation regarding the definition of domain, range, correspondence, change of dumb variables etc. To someone with a master degree in math, there is really nothing needed to explain. The speed of explanation below is somewhat arbitrarily in-between, since I do not know your level. If you think some stuff is too obvious to you, just skip it. Otherwise, comment below to tell me which part is still puzzling to you.)

Suppose we have a function, $T:\Bbb N\to\Bbb N$ defined by $T(2^{n}) = 2T(2^{n/2}) + n$. Let us define a new function, $S: \Bbb N\to\Bbb N$ by $s(m) = T(2^m)$, that is, $s(1) = T(2)$, $s(2) = T(4)$, $s(3) = T(8)$, etc. Since $m$ is an independent variable, we can also substitute $m/2$ for $m$ to obtain $s(m/2)=T(2^{m/2})$. So we will have,
$$s(m) = T(2^m) = 2T(2^{m/2}) + m = 2s(m/2) + m $$

  how will the following relation $T(2^{n}) = T(2^{n-1}) + 1$ be changed? Which change is correct?  $S(n) = S(n/2) + 1$ or $S(n) = S(n-1) + 1$?

If we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(m)$, i.e., $S$ is the same function as $T$, then we have, for any $n\in\Bbb Z$ that is a power of 2, i.e., $n=2^m$ for some $m$,
$$S(n) = S(2^m) = T(2^m) = T(2^{m-1}) + 1 = S(2^{m-1}) + 1 = S(2^m/2)+1 =S(n/2)+1. $$

On the other hand, if we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(2^m)$, then substituting $m-1$ for $m$, we have $S(m-1)=T(2^{m-1})$. So,
$$S(m) = T(2^m) = T(2^{m-1}) + 1 = S(m-1) + 1$$

In summary, either one of $S(n) = S(n/2) + 1$ and $S(n) = S(n-1) + 1$ can be correct. Which one is correct depends on how you define $S$. Once you have write down the definition of $S$, it will be clear which one is correct and which one is wrong. In other words, you have to specify what is $S$ first.


Branch & Bound: Avoiding equivalent solutions

You could impose a canonical ordering on the bags.

For instance, in each bag find the lowest-numbered item in that bag, and  imagine labelling the bag with that number.  Now add the additional constraint that to be a valid solution, the bags must be in sorted order according to their label.  In other words, the label on the $i$th bag must be less than the label on the $i+1$st bag.

If you can express this constraint within your system, it ensures that each equivalent solution will be generated only once.


Time complexity for the 'Restore IP Addresses' problem

The time complexity here is exponential in s or parts, whichever is smaller.

You have a recursive function, and it calls itself three times (after removing 1, 2, or 3 characters from the beginning). Thus, if $n$ is the size of $s$ and $k$ is the number of parts, your time complexity $T(n, k)$ satisfies
$$
T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1)
$$
We can roughly replace this by $T(n, k) = 3 T(n-3, k-1)$ (a lower bound) which leads to
$$
T(n, k) = \min(3^{n/3}, 3^{k}).
$$

For IP addresses, this exponential time complexity is likely not a huge problem. It's exponential in the number of parts, but the number of parts is only $4$, so that is not huge.

However, conceptually, your solution is pretty inefficient. Notice that you are duplicating a lot of work: you might call your breakString function on the tail of the same string several times, in different recursive calls.

To get a more efficient algorithm, try dynamic programming instead of recursion. For instance, can you keep track of, for each prefix and possible # of parts, whether it is a valid IP address or not? What complexity would that give?

NOTE: In the above idea to try dynamic programming, I assumed that the goal was just to return one valid IP address, not return all of them. When we have to return all of them, the time complexity changes somewhat, because the time complexity is now at least the time it takes to output all the answers, and there could be exponentially many answers.

Specifically, the time complexity in the worst case is bounded below by the number of decompositions of s in the following example: let s be a string of length $4n$ 1s, and let parts $= 2n$. Then there are at least $3^n$ decompositions: this is the number of decompositions where there is a . after every block of $4$ characters.

Here is an example: for $n = 2$, 11111111 into $4$ parts has the following $3^2 = 9$ decompositions:

1.111.1.111
1.111.11.11
1.111.111.1
11.11.1.111
11.11.11.11
11.11.111.1
111.1.1.111
111.1.11.11
111.1.111.1

Again, this includes only those decompositions with a . after every block of $4$ characters, so there are actually more than $3^n$ total. But maybe you get the idea of why it blows up exponentially.


Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?

On the Integrality Gap of the Subtour LP for the 1,2-TSP provides some relevant references and discussion in the introduction..


Joining points of polygon in correct order

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate.

Suppose for simplicity that there are no two points that are collinear with $x_0$ (this case can be handled by suitably breaking ties).

Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. Sweep the plane by rotating the ray anticlockwise up to an angle of $\frac{\pi}{2}$ radians. Whenever the ray intersects a vertex, let this vertex be $x_{i+1}$ where $i$ is the number of intersected vertices so far. Connect $x_{i}$ to $x_{i+1}$.
Finally, connect the last encountered vertex back to $x_0$.

In practice this boils down to writing all points in polar coordinates from $x_0$, then sorting them by their angle, and connecting them in order.


What does the set {n | n is an integer and n = n + 1} represent?

But infinity isn't an integer. Since there is no integer $n$ such that $n=n+1$, you're right that the set is empty.


Measuring the information of a document?

Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is $H$, then the expected compressed size of $n$ samples is roughly $nH$. Definitions and proofs appear in Cover and Thomas' Elements of Information Theory, Chapter 13 of the 2nd edition.

The entropy of the source differs from your example. It doesn't make sense to calculate the entropy of a single output – entropy is a function of a random variable (or a distribution), and the entropy of a constant random variable is zero. Instead, we consider your source text as a random variable, and our goal is to estimate the entropy of that random variable from a single sample.

If the source has no memory – that is, the individual symbols of the text are independent – then a good estimate of the entropy of the source is the empirical single-character entropy, which is the function that appears in your question. But general sources – such as a random text – do have memory: if you just sample a random list of characters according to their distribution in the English language, you will get gibberish (a nice example of this appears in Shannon's 1948 paper, p. 7). This is why we need to use a more sophisticated estimator, such as the Lempel–Ziv algorithm.

In practice, you can approximate the information content by just compressing the text using an off-the-shelf program.


Matrix Multiplication Algorithms for Non-Square Matrices

There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha > 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both algorithms are probably impractical. Ryan Williams (Appendix C) explains how to implement Coppersmith's algorithm, which a priori is non-uniform, in the context of a circuit lower bound; later it was shown that Coppersmith's algorithm can be replaced by other ingredients.


Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply the master theorem.

Case 2 states that if $f(n) = O(n^{\log_b a} \log^k n)$ for some $k \geq 0$ then $T(n) = O(n^{\log_b a} \log^{k+1} n)$. In our case we can choose $k = 0$ and obtain the bound $T(n) = O(n\log n)$. If we also had $f(n) = \Omega(n^{\log_b a} \log^k n)$ then $T(n) = \Omega(n^{\log_b a} \log^{k+1} n)$, but this doesn't hold in our case.

Case 1 states that if $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = O(n^{\log_b a})$. In our case $c = 1$ so this case doesn't apply.

Case 3 states that if $f(n) = \Omega(n^c)$ for some $c > \log_b a$ then $T(n) = \Omega(n^c)$. In our case $c < 1$ so this case also doesn't apply.

Summarizing, the master theorem only gives the upper bound $T(n) = O(n\log n)$. We trivially have $T(n) = \Omega(n/\log n)$, but this doesn't match the upper bound.

We can determine the exact asymptotics using the Akra–Bazzi method. In our case $p = 1$ and $g(x) = x/\log x$, so $T(n) = \Theta(n(1+G(n))$ where
$$ G(x) = \int_1^x \frac{g(u)}{u^2} \, du = \int_1^x \frac{du}{u\log u} = \log\log x. $$
(Formally, we have to change the lower bound of the integration from $1$ to $e$.) We conclude that $T(n) = \Theta(n\log\log n)$.


As you observed, to show $S^*=(S^*)^*$ it will suffice to show $S^*\subseteq(S^*)^*$ and $(S^*)^*\subseteq S^*$. Here's a sketch of a proof of both containments.

For a language $A$, define $A^*=\{x_1x_2\dots x_n\mid n\ge 0\text{ and each }x_i\in A\}$. Then (with $n=1$) it's clear that for all $x\in A$ we'll have $x\in A^*$, establishing that $S^*\subseteq(S^*)^*$.

To show containment in the opposite direction, let $x\in (S^*)^*$, then by definition we'll have $x=y_1y_2\dots y_n$ where $y_i\in S^*$ for all $1 \le i\le n$. Then, again by definition, we'll have $y_i=z_{i1}z_{i2}\dots z_{in_i}$ where $z_{ij}\in S$ for all suitable $i$. We'll then have
$$
x=(z_{11}z_{12}\dots z_{1n_1})(z_{21}z_{22}\dots z_{2n_2})\dots(z_{n1}z_{n2}\dots z_{nn_n})
$$
where each $z_{ij}\in S$. Applying the definition of star one more time we see that $x\in S^*$, establishing that $(S^*)^*\subseteq S^*$ and hence the desired equality.


Does there exist an algorithm to generate the production rules of CFG, given a sample production?

Any interesting grammar will generate an infinite language. There is always the trivial grammar with a start symbol that generates each example string on it's own. Checking if two grammars generate the same language, and thus in any sense finding "the smallest" (or whatever other measure you care about) grammar for a language is unsolvable. Inferring the grammar (in any meaningful sense) is probably impossible.


Conditions for bipartite graph to be planar with no edges going around the vertices

Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar.  Caterpillars have two relevant characterizations:

they're the trees in which there is a single path containing every vertex of degree more than $1$;
they're the trees in which every vertex has at most two non-leaf neighbours.

Lemma 1. Every caterpillar is in your class.

Proof. Let $G$ be a caterpillar and let $P=x_1\dots x_\ell$ be a longest path containing every vertex of degree $2$ or more.  Note that, by maximality, $d(x_1)=d(x_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x_i$ between $x_{i-1}$ and $x_{i+1}$. $\Box$

Lemma 2. Every graph $G$ in your class is acyclic.

Proof. Suppose $G$ contains the cycle $x_1y_1x_2y_2\dots x_ky_kx_1$ and suppose it has a drawing of the required form. W.l.o.g., $x_2$ is above $x_1$. But then we must have $y_2$ above $y_1$ since, otherwise, the lines $x_1y_1$ and $x_2y_2$ would cross. By induction, $x_{i+1}$ is above $x_i$ for all $i\in\{1, \dots, k-1\}$ and likewise for the $y$'s. But then any line $y_kx_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$

Lemma 3. Every connected non-caterpillar is not in your class.

Proof. Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree.  If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y_1$, $y_2$ and $y_3$, each of which has degree at least  $2$.

Suppose we have a drawing of $G$ with the required properties.  W.l.o.g., $y_2$ is above $y_1$ and $y_3$ is above $y_2$.  Let $z\neq x$ be a neighbour of $y_2$.  The edge $y_2z$ must cross $xy_1$ or $xy_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$

Theorem. Your class of graphs is exactly the class of forests each of whose components is a caterpillar.

Proof. Let $G$ be a graph.  Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other.  The result now follows by Lemmas $1$ and $3$. $\Box$

Corollary. Your class of graphs is the class of graphs that do not have $K_3$ or the subdivision of $K_{1,3}$ as a minor.

Proof. These are the obstructions for path-width $1$. $\Box$

These are essentially the obstructions you found: you need $K_3$ rather than $K_4$ because the latter would admit $K_3$ into the class; the subdivision of $K_{1,3}$ is exactly your second obstruction.


Membership in 1, 5, 2, 13, 10, ... (recursively defined sequence)

Your sequence contains all positive integers not divisible by 3. Let us prove this by induction.
Suppose first that $x$ is divisible by 3, and $f(n) = x$. Considering the definition, we see that $x = 2f(n/2) + 3$, and so $f(n/2) = \tfrac{x-3}{2}$, which is also divisible by 3. By induction, this is impossible.
Suppose next that $x>0$ is not divisible by 3. If $x=1$ then $x$ appears in the sequence since $f(1) = 1$, so we can assume that $x \geq 2$. We now consider two cases: $x$ even and $x$ odd.
If $x$ is even then $\tfrac{x}{2}<x$ is positive not divisible by 3, and so by induction, $\tfrac{x}{2} = f(m)$ for some $m$. Then $f(2m) = x$.
Similarly, if $x$ is odd then $\tfrac{x-3}{2} < x$ is not divisible by 3. Furthermore, since $x \geq 5$, it is furthermore positive. By induction, $\tfrac{x-3}{2} = f(m)$ for some $m$. Then $f(2m+1) = x$.


What is the the relation between the amount of data transmitted and line distance?

Distance sets lower bounds on latency, the effect on throughput as opposed to data rate depends on protocol.
Raw error rate increases with distance.


Heavy hitters problem linear scan and auxiliary space

Here is the idea, taking as an example the case $k = n/2$ which you mention. Also, let's assume that a word is $\log n$ bits, and that each element consists of $C$ words. In total there are $n^C$ possible elements, forming the universe $U$.

Suppose that an algorithm uses $m$ words of space. For each subset $S$ of $U$ of size $n-1$, let $T(S)$ denote the contents of memory after the algorithm has read the first the elements of $S$ in order. We claim that $T(S_1) \neq T(S_2)$ if $S_1 \neq S_2$. Indeed, suppose without loss of generality that $S_1$ isn't a subset of $S_2$, and let $x \in S_1 \setminus S_2$. If the last element that the algorithm reads is $x$ then it should output $x$ if it had read the elements in $S_1$, and it should output nothing if it has read the elements in $S_2$.

Since there are $\binom{|U|}{n-1} = \binom{n^C}{n-1}$ different sets $S$ and $n^m$ different memory settings, we conclude that $\binom{n^C}{n-1} \leq n^m$. Since $\binom{a}{b} \geq (a/b)^b$, we conclude that $(n^{C-1})^n \lesssim n^m$, and so $(C-1)n \leq m$ or $m = \Omega(n)$ (for $C > 1$).


Generate a random magic square on a large field

Here's a decent algorithm that will quickly generate large magic squares.

First Step: Establish Rows
1. Put all numbers in a bucket.
2. Loop through the rows, 0 to n.
3. Take out n (where n is the size of row) numbers randomly from the bucket.
4. Sum those numbers. If they don't equal the solution sum, goto 3.
5. If they do equal the solution sum, stick them into your grid at the row you are on, remove the numbers used from the bucket, and goto 2.

You'll now -- very quickly -- have a square with each row having the correct sum.

Second Step: Establish Columns
1. Loop through the columns, 0 to n.
2. Shuffle the elements in each row from the beginning of the row + the column you are on, to the end of the row. (That is, if we are working on the first column, shuffle all the elements in each row. If we are working on the second column, shuffle all the elements but those in the first column, etc.)
3. Sum the column. If it doesn't equal solution sum, goto 2.
4. Goto 1 and proceed to the next column.

Now, in this step, you'll need a bail counter... that is, after 1000 tries or so, give up and return to the First Step. The number of attempts needs to increase as n increases... For a 25x25 grid, for example, let it try 100,000 times or so before giving up and creating a new set of rows.

Third Step: Establishing Diagonals
1. Swap any two rows and swap any two columns.
2. Check diagonals sums.
3. If the sum equals solution sum, you're finished. If not, go to 1.

Once again, stick in a bail counter... after 10,000 tries or so, go back to First Step.


The idea is very similar to the way we show that the rational numbers are countable.
Essentially, what you need to do is to find a (bijective) mapping of the 2D tape onto the 1D tape. Of course, you want this mapping to be computable, and it would be helpful if it is computable efficiently.

The illustrative way to think about this is in diagonals: the cell $(1,1)$ is mapped to cell $1$ in the 1D tape. Then the second diagonal, namely cells $(1,2)$ and $(2,1)$ are mapped to cells $2,3$ respectively. Continuing in the same manner, you can map the entire 2D tape to the 1D tape. Of course, any movement of the head needs to be translated to the correct position in the 1D tape, so a single movement in the 2D tape may actually take several operations to simulate in the 1D tape.

There are many explicit functions that compute such a mapping. See for example the Cantor pairing function.


What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable"

This statement means exactly what you have said: if any NP-complete problem is solvable in polynomial time, then all of them are. This follows from the definitions: a problem X is NP-complete if all problems in NP are polynomial time reducible to it, that is, if for any problem Y in NP there is a polynomial time function $f_Y$ such that for all $w$, $w \in Y$ iff $f_Y(w) \in X$. Now suppose that you could solve X in polynomial time using some algorithm A. For any NP problem Y, you can use $f_Y$ in conjunction with A to solve Y in polynomial time.

This is indeed surprising, and it is one reason why most researchers conjecture that NP is different from P: otherwise all these disparate problems will have polynomial time solutions.


Structure of a Pumping Lemma proof: contradiction or counterexample?

this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma

You are missing that in order to construct this counterexample you have to assume that $L$ is regular. Then you apply the Pumping lemma, which yields the Pumping length $p$. Only then do you construct your (counter)example string (using $p$!) and show that it contradicts the Pumping lemma. Hence, the assumption must be false.

So while you can say that you derive the contradiction using a counterexample, the outer-most proof is by contradiction.
With the assumption, you wouldn't have $p$!

Note that proofs can be nested, so you don't need to see only one proof technique. For instance, induction proofs often use a proof by contradiction inside the inductive step.


Compute 'permutation' like problem with modulo

The idea is that $(a + b) \pmod{p} = ((a \pmod{p}) + (b \pmod{p})) \pmod{p}$ and $(ab) \pmod{p} = ((a\pmod{p})(b\pmod{p})\pmod{p}$. In C code, computing $a + bc \pmod{p}$ is accomplished by

  t = (b*c) % p;
  return (a + t) % p;

Regarding inverses, when $p$ is prime and $1 \leq a \leq p-1$ there is an element $1 \leq b \leq p-1$ satisfying $ab = 1 \pmod{p}$, and so $(x/a) \pmod{p} = (xb) \pmod{p}$. To find $b$ use the extended GCD algorithm to find $b,c$ such that $ab + cp = 1$.


What is M referring to when talking about memory size( 4M x 8)

M in this context is just defined to be $2^{20}$, so if you have M items (bits, bytes, whatever), you'll have $2^{20}$ of them. The letter was chosen since it's the first letter in the term mega, meaning a million. Since $2^{10}=1024$ is close to $1000$, we'll have $2^{20}=(2^{10})^2≈(1000)^2=1000000$. M is sometimes called a "binary million".


Case 3 does not apply. Indeed:
$$
f(n) = n \log n \not\in \Omega(n^{\log_9 10}) = \Omega(n^{\log_b a}).
$$
However case $1$ applies since, for $0<c \le 0.01$
$$
f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log_9 10 - 0.01} ) \subseteq O(n^{\log_b a - c} ).
$$
This shows that $T(n) \in \Theta(n^{\log_9 10})$.


Average-case complexity of linear search where half of the elements in the array are duplicates

Let us assume the elements in the array are the multi-set $M=\{1,2,\cdots,n-k, d, d, \cdots, d\}$, where $d$, an element that is different from $1,2,\cdots, n-k$, appears $k\ge 0$ imes. The situation raised by OP is simply the special case when we let $n=2k$.

In order to discuss the average time-complexity of a linear search, we must specify the distribution of the array as well as the element or the distribution of the element we are searching for.

The distribution of the array assumed

The most common distribution discussed in various articles and in people's mindset is probably the following simplest one.
    $$\text{All orderings of the multi-set are equally likely.}$$
That distribution is assumed throughout this answer.

The average number of comparisons needed when we search for $d$

The following answer is given in the wikipedia analysis.

$$\begin{cases}
  n                   & \mbox{if } k = 0 \\
  \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n.
\end{cases}$$

The above answer is easy to prove by induction on $n$.

The average number of comparisons needed

Assume $k\ge 1$ from now on. Two cases will be shown.

the case with one extra element

Let $o$ stands for an element not in the set $S=\{1,2,\cdots,n-k, d\}$.
If we are searching for a specified element in $S\cup\{o\}$, where each element is equally likely to be specified, here is the computation.
$$\begin{align}
E[\text{search for } x] &= \sum_{x!=d \text { and } x!=0}\frac 1{n-k+2}E[\text{search for }x] + \frac1{n-k+2}E[\text{search for }d] + \frac1{n-k+2}E[\text{search for }o]\\
&=\frac{n-k}{n-k+2}\frac{n+1}2 + \frac1{n-k+2}\frac{n + 1}{k + 1} + \frac1{n-k+2}n\\
&=\frac{n+1}2 + \frac1{k+1} - \frac{2}{(k+1)(n-k+2)}
\end{align}$$

In particular, if we let $n=2k$, then
$$E[\text{search for } x] =\frac {n+1}2 + \frac2{n+2}-\frac{8}{(n+2)(n+4)}$$

the case with $M$ alone

What is the average number of comparisons need among the cases when the element we are search for turned out to be an element in $M$, assuming that we are searching for an element in the union of the multi-set $M$ and another multi-set $M'$ that is disjoint with $M$, where all elements in $M$ will be equally likely to be searched? The inclusion of the $M'$ is to ensure that we do NOT know whether the element to be found belongs to $M$ before we start the search.

Here is the computation.
$$\begin{align}
E[\text{search for } x] &= \sum_{x!=d}\frac 1{n}E[\text{search for }x] + \frac k{n}E[\text{search for }d]\\
&=\frac{n-k}n\frac{n+1}2 + \frac k{n}\frac{n + 1}{k + 1}\\
&=\left(1-\frac{k-2}n -\frac2{n(k+1)}\right)\frac {n+1}2
\end{align}$$

In particular, if we let $n=2k$, then
$$E[\text{search for } x] =\frac14\left(n+5-\frac 4{n+2}\right)$$

Please note that we have not computed the situations when we know the element to be searched is an element of array before we start the linear search, which might be the more common situations. Readers are encouraged to dive into those situations.

The wikipedia item is a good place to start your journey of finding, reading, and playing with the many variations and generalization of this question.


Time complexity of a triple nested for loop for ThreeSum problem

The second loop runs only on $j > i$. Only (roughly) half of the pairs $(i,j)$ between $0$ and $N-1$ satisfy $j > i$. Similarly, the third loop runs only on $k > j > i$, and only (roughly) $1/3!$ of the triples $(i,j,k)$ satisfy that condition.

If you want to be more accurate, $B$ runs this many times
$$ \sum_{i=0}^{N-1} (N-i-1) = \sum_{i=0}^{N-1} i = \frac{i(i-1)}{2}. $$
I'll leave you the calculation for $C$.


The distinction you want to make between the key and the algorithm proper is not based on whether most of the operation is contained in one or the other, but on where the complexity lies. I am not talking about algorithmic complexity here, but complexity in its everyday meaning: difficulty to understand and reason about.

The algorithm proper is complex and hard to reason about. It generally does a whole bunch of arbitrary-seeming bit manipulations, logical and arithmetic operations, and general shuffling of the data. It's very hard for a layperson or even for a cryptographer to know how much privacy all those manipulations actually buy you, and what kind of cryptanalysis it might be vulnerable to. So the best way to be confident about the algorithm's security is to put it out in the open and have it reviewed by experts as widely as possible. MAKE IT PUBLIC.

The key, on the other hand, is a simple concept: it's a bunch of bits which need to be random. There is no need to review the key to assure the correctness of the crypto. Any key is supposed to be as strong as any other key (and if this is not true then it can in principle be discovered by review of the algorithm, not the key). We know that the quality of randomness that is available to generate keys is less than perfect, so in practice some keys may be weak due to lack of randomness, but at least everyone can know without needing to be an expert cryptographer and without needing to make a difficult analysis of the key that good randomness WILL lead to a good key. So use the best randomness you've got available then you need not (MUST not!) share the key with everyone in order to have confidence in your crypto.


Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

If a word is not of the form $(a^nb)^n$ for $n > 0$, then one of the following must happen:

The word is not of the form $(a^*b)^+$, i.e., it is either empty or ends in $a$.
The word is of the form $a^ib(a^*b)^*a^jb(a^*b)^*$ for some $i \neq j$.
The word is of the form $a^nb (a^*b)^k$, where $n \neq k+1$.

Each of these can be checked by a PDA or generated by a CFG. It might help to break a condition of the form $i \neq j$ into two alternatives, $i > j$ and $i < j$.
To see why this case distinction holds, let us assume that the word is of the form $(a^*b)^+$. We can write it as
$$
a^{i_1} b a^{i_2} b \cdots a^{i_m} b.
$$
The word is of the form $(a^nb)^n$ if $i_1 = \cdots = i_m = m$, which is equivalent to
$$
i_1 = i_2 \text{ and } i_1 = i_3 \text{ and } \cdots \text{ and } i_1 = i_m \text{ and } i_1 = m.
$$
Hence the word is not of the form $(a^nb)^n$ if
$$
i_1 \neq i_2 \text{ or } i_1 \neq i_3 \text{ or } \cdots \text{ or } i_1 \neq i_m \text{ or } i_1 \neq m.
$$
The case $i_1 \neq i_j$ is handled by the second bullet above, and the case $i_1 \neq m$ is handled by the third bullet.
(Thank you to Hendrik Jan for help with simplifying the cases.)


Could the halting problem in theory be solved for any finite set of Turing Machines?

Your logic is somewhat correct. I will start by discussing the new definition you tried to give for the halting problem, and then move on to explain the finite set of TMs.

Halting problem, with size less than the TM that solves it
This idea is certainly interesting, but it has some inherent problems with it.
First is a syntax problem. What language is here? Since $N$ is not bounded, this cannot be expressed as a usual computational problem with TMs. In order to formalize this you might want to create a new definition.
The second problem, is a bit more subtle: How do you define the "size" of a TM?
For example, if you decide to define it as the running time of the algorithm, then obviously is such a $B$ for every $N$ (just do a loop that does nothing for $N-1$ steps and after that accept). But if you define it as the length of the code plus the length of the inputs, then you can show that there is no such $B$ for big enough $N$. (the formal halting problem gets two inputs $A,X$ where $A$ is a program code and $X$ is some string, and you create a new TM that simulates it with only one input instead of two, reducing the size)
Those examples are obviously two opposite sides of a wide spectrum. You want to formally define the problem and the definition of the size of a TM before you can think of whether or not its possible.

Finite set of TM
The formalization of the halting problem $H$ is as follows: $H=\{\langle M, x \rangle : M \text{ is a TM }\land M(x)\text{ halts}\}$
With this definition, even if you restrict it so $M$ would be in a predefined finite set of TMs, and even if this set contains only one TM, this is an undecidable problem! The counterexample, is $U$ - the universal TM. We will use a slightly different version of it, since we dont need its full power. $U$ (in this context) gets one input, which is a string representing a TM, and $U$ simulates this TM with the input $\epsilon$. Then solving whether $U$ halts on some input or not, is undecidable, since its equivalent to the problem called $H_\epsilon$ which is known to be undecidable.
However, if you would restrict the $H_\epsilon$ problem itself for only a finite set of TMs, the problem becomes decidable, and even more! It becomes a regular language. This is because for each $TM$ in this finite set we know beforehand whether or not it halts, and we dont have to actually do any computation apart from assigning each of those $TM$ the correct label we already know.


Algorithm for a special case of SAT/#SAT

From Solving #SAT using vertex covers, published at SAT'06 by Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider:

  A cluster formula is a variable-disjoint union of so-called hitting formulas; any two
  clauses of a hitting formula clash in at least one literal. The known polynomial time
  algorithm for computing the number of models of a hitting formula can be extended in a straight-forward way to compute the number of models of a cluster formula.

Clash is later clarified/defined as:

  We consider propositional formulas in conjunctive normal form (CNF), represented
  as sets of clauses. That is, a literal is a (propositional) variable $x$
  or a negated variable $\overline{x}$; a clause is a finite set of literals not containing a complementary pair $x$ and $\overline{x}$; a formula is a finite set of clauses. For a literal $ℓ = \overline{x}$ we write $\overline{ℓ} = x$; for a clause $C$ we set $\overline{C} = \{ \overline{ℓ} : ℓ ∈ C \}$. We say that two clauses $C$, $D$ overlap if $C ∩ D \neq ∅$; we say that $C$ and $D$ clash if $C$ and $\overline{D}$ overlap. Note that two clauses can clash and overlap at the same time. [...] A formula is a hitting formula if any two of its clauses clash (see [17]). A cluster
  formula is the variable-disjoint union of hitting formulas [...]

  Lemma 3. #SAT can be solved in polynomial time for cluster formulas.

So their cluster formula seems to be exactly what you have defined.

There's also a journal version that paper, it seems; the result is (not surprisingly) also mentioned in a 2011/2012 survey paper "Backdoors to satisfaction" on which Szeider is a co-author, and which was published in some festschrift My first instinct that this was a more suitable question on cstheory.SE was perhaps not wrong. :-)

Also the notion of hitting formulas is cited to [17]:

H. Kleine Buning and X. Zhao. Satisfiable formulas closed under replacement.
In H. Kautz and B. Selman, editors, Proceedings for the Workshop on Theory
and Applications of Satisfiability, volume 9 of Electronic Notes in Discrete
Mathematics. Elsevier Science Publishers, North-Holland, 2001.

In another paper, the fact that

  It is known that for hitting formulas the satisfiability problem can be solved efficiently [7].

is cited to an even older paper:

K. Iwama "CNF satisfiability test by counting and polynomial average time" SIAM J. Comput., 18 (1989), pp. 385–391


Your question is answered in a blog post of Lance Fortnow. Solutions are given by Fortnow and by Lovász.


What is the time complexity of calling successor $n$ times during tree traversal?

Gist: The time complexity of calling the sucessor function multiple times is not merely the product of the number of calls and the worst-case bound, though that product does encompass the worst case. Rather, if the function going to be called from every node, a more sophisticated analysis can establish a tighter worst-case bound for specific trees and implementations of the successor function.

At best, tree traversal takes at $O(n)$ time: $n-1$ calls are made to the successor function, which takes constant time. One simple example of this is the traversal of a linked list, which has a successor function that immediately returns a pointer to the next node with no additional computation.

The worst "reasonable" tree traversal would take $O(n^2)$ time: $n-1$ calls are made to the successor function, which searches all $n$ nodes before determining the successor. For example, if we have an unsorted tree and the successor is defined to be the next largest element (rather than based on its position in the tree). Of course, we could sort the tree first in time $O(n\log n)$ and in general, if we expect to call the successor function $n$ times, it would be wise to preprocess the tree so that it can be traversed in one of the three canonical ways: inorder, preorder, or postorder.

Ok, time to clear a misconception! Let's ask what's the best-case and worst-case scenarios for the successor function are when we have an inorder traversal of a binary search tree:

Remember that in inorder traversal, the left subtree is visited, then the parent node, then the right subtree. So an inorder traversal on the above tree gives us $[A,B,C,D,E,F,G,H,I]$.
(For contrast, preorder traversal would have given us $[F,B,A,D,C,E,G,I,H]$). We start at the beginning of the tree at $A$. From $A$, the successor function checks to see that it has no right subtree (it doesn't) before finding its closest ancestor for which it is the descendant of the left child. But wait! I didn't tell you that each node had knowledge of its ancestors, so we potentially have to search the entire tree just to determine where $A$ is! So now we split into two cases:

Worst-case: Assuming that our node has no right subtree, if the tree was a binary search tree, we could find the node in $O(\log n)$ time. But worst-case, it's not a binary search tree; in fact, it has no structure, so every call takes $O(n)$ time, but if we're consistent about how we search, the total number of steps to find the node's successor is at least $\sum_{x=1}^{n}x=\frac{(n)(n+1)}{2}=O(n^2)$.
Best-case: Each node has a link to its ancestor, so from $A$ to $B$ takes two steps (check for right subtree; back up to ancestor for which it is the left child). The successor function that takes the most steps is from $E$ to $F$, for which $E$ first checks that it has no right subtree, then checks to see if it is the left child of $D$ (it isn't), or the descendent of the left child of $B$ (it isn't), and finally if it is the descendent of the left child of $F$ (it is). That took $O(h)=O(\log n)$ steps, but most calls to the function won't take that many steps. Quoting the SO post, "observe that each edge in the tree gets visited at most twice (once from parent to child and once from child to the parent)" so the total number of nodes visited is $2n$ and hence $O(n)$ worst-case bound.

Another way to appreciate that the average call to successor is $<\log(n)$ is to consider a balanced tree with $n$ nodes and roughly $n/2$ leaves. Half of all successor function calls will be to an ancestor, half of which are from the left child ($\frac{1}{4}n$) and thus takes only one generation/step, $\frac{1}{8}n$ go back two generations, $\frac{1}{16}n$ go back three. Hopefully you see the pattern: $\sum_{i=1}\frac{i}{2^{i+1}}$ converges to $1$. And the other half does the step-analogous $\min$ function (searching it's right subtree for the leftest child), so it also converges to $1$. The expected time is thus $2$ (if I've done my math carefully). So that's $n-1$ calls to a successor function that on average takes ~$2$ steps $\rightarrow O(n)$ time.


Theory of message complexity analysis of distributed systems

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

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

This chapter also covers lower bound methods: the fooling set method, the tiling method, the rank method, the discrepancy method. It gives also a brief overview of other communication models: randomized protocols, nondeterministic protocols, average case protocols, and asymmetric communication. At the end of the chapter it provides detailed reference to papers relating this topic.


How can the initial "booting" state of a computer be different at different time points?

Can anything change in a computer without the user modifying something, also while not having internet connection?

Yes, definitely - computers update their own states all the time, and some of these changes will be persistent from one boot cycle to the next.

The computer itself is a complex piece of hardware, and the operating system is a complex piece of software. Both the computer (at a hardware level) and the operating system will carry out a series of self tests during the boot process. The results of some of those self tests will be stored in non-volatile memory (e.g. in some form of registry). When the computer is re-booted, the results of the self-tests from the previous boot attempt may affect the route taken through the boot process the next time around. This might avoid a problem encountered in the previous boot cycle (e.g. by loading a previous version of a corrupted driver), but it may also introduce a new problem not seen before.

In short, part of the boot process will be a check to see if the previous boot cycle was successful. If not, there may be logic in the boot process that tries a different sequence of actions, or boots into a restricted "safe" mode.


Matrix chain multiplication and exponentiation

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.

The problem reduces to finding the most efficient ordering when considering the square of the product.

For example, when looking at e.g. $(ABC)^{50}$, we only need to optimally solve $(ABC)^2$ since this expands to $ABCABC$. No useful ordering information is added by concatenating $ABC$ again. The intuition here is that since the problem of optimal ordering can be solved bottom-up, higher orderings consisting of more elements using the same matrices are irrelevant.

Finding the best ordering of $ABCABC$ reduces to the Matrix Chain Multiplication problem. After finding an optimal ordering, apply exponentiation to the triplet (n-tuple generally) in the ordering.

As an e.g., if the optimal ordering for the square is $A(B(CA))BC$, the solution to the initial problem is $A(B(CA))^{49}BC$.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Informal proof
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X < Y$ or $Y ≤ X$.

Assumption 1a): $X < Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving $A$ and $B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

Case study:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)


Can we detect perfect matchings in P? in NP? in coNP?

Edmonds' "blossom algorithm" determines membership in MATCH deterministically in time $O(|E|\,|V|^2)$.

You answer this kind of question by searching for algorithms that solve your problem as efficiently as possible and, if there don't seem to be any, searching for NP-completeness results. If you don't find either, then you need to come up with your own algorithm or your own hardness proof.


Quickly obtaining sums of sets of numbers

I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a_1$, $a_2$, $\dots$, $a_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above).  Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a_1$, $a_2$, $\dots$, $a_{\beta}$.  The second collection consists of the second $\beta$ bits $a_{\beta+1}$, $a_{\beta+2}$, $\dots$, $a_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$.  We then calculate each of these sums exactly.  If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach.  Again, I believe that we can do better.


The best explanation I've heard is this:

When you're doing machine learning, you assume you're trying to learn from data that follows some probabilistic distribution.

This means that in any data set, because of randomness, there will be some noise: data will randomly vary.

When you overfit, you end up learning from your noise, and including it in your model.

Then, when the time comes to make predictions from other data, your accuracy goes down: the noise made its way into your model, but it was specific to your training data, so it hurts the accuracy of your model. Your model doesn't generalize: it is too specific to the data set you happened to choose to train.


Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

All the classes you mention are classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around decision problems is equivalent to formal languages; the decision is always whether a word is in the given language, i.e. the problem is to solve the word problem.

What you need to do is go back to the formal definitions. Summarising:

$\mathrm{RE}$ contains languages which are accepted by any TM.
$\mathrm{REC}$ contains all languages which are decided by any TM.
$\mathrm{NP}$ contains all languages which are accepted by any polynomial-time TM.
$\mathrm{P}$ contains all languages which are decided by any polynomial-time and deterministic TM.

It's already quite clear from the definitions that we have

$\qquad\displaystyle \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{REC} \subseteq \mathrm{RE}$.

So, essentially, computability and complexity theory deal with the same kind of questions: which kinds of problems can I solve with which type of machine?

In fact, the famous Complexity Zoo diagram (via the companion the wiki) displays "computability", "complexity" and "Chomsky" classes in a single inclusion hierarchy -- because they all use the same formalism.

I recommend you check out some of our reference questions on computability and complexity theory; you'll the similarities.


C isn't Part of the grammar recursion. As it expands to Terminals only, it is artificial in the Sense That it is only used for notational convenience while it is unnecessary for expressing the CFG.

The simplified grammar obviously contains a typo, as no words containing b are derivable contradicting S -> aBC -> abC -> ababb which the original grammar allows.

The first rule should probably read S -> aAa | aBabb.


With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.


Can Nondet Rabin Tree automaton be determinized?

The answer is no, nondeterministic Rabin automata are more expressive than deterministic ones.

As an example, consider the language of $\{a,b\}$-labeled binary trees that contain at least one $b$.

It's easy to construct a two-state Büchi tree automaton for this language (and hence a Rabin automaton), but there is no deterministic equivalent.

You can look at Lemma 6.1 here, for a start.


Minimal, "natural" set of operations to manipulate a binary tree

It looks like the following set of four operations is sufficient.  They are also minimal / necessary in the sense that no single operation can be removed from the set.

right rotation at the root:

    .            .
   / \          / \
  .  z    =>   x   .
 / \              / \
x   y            y   z

duplicating the tree
deleting the left branch
flipping the right grandchildren

By way of illustration (and a form of proof outline), I've written up a Haskell implementation.  Given a definition of a Tree structure and a TreeOp tree operation type:

data Tree a = Node (Tree a) (Tree a) | Leaf a
type TreeOp a = Tree a -> Maybe (Tree a)

the primitive operations would be defined as:

rotateR, dup, deleteL, flipR :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

We can define derived operations to flip the root's children (duplicate the tree, flip the right grandchildren, and delete the left branch):

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

Similarly, we can define an operation to duplicate the right branch:

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

as well as the symmetric variants of all the above operations:

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

Finally, it will be helpful to have an operation for "interleaving" the grandchildren like so:

        ..           ..
       /  \         /  \
      .    .       .    .
     / \  / \     / \  / \
     w x  y z     w y  x z

The best implementation I could come up with was:

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

With interleave, it's easy to define operations to rotate the left and right subtrees of the root independently:

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

Using a helper to apply an operation repeatedly until it no longer works:

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

we can turn any tree into an in-order traversal "cons-list-like" normal form:

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRL >>> rotateL)
    >>> untilDone rotateR

meaning that, for any tree t whose in-order traversal of leaves is, say, [1,2,3,4,5], the result of toList t will be:

Node (Leaf 1) (Node (Leaf 2) (Node (Leaf 3) (Node (Leaf 4) (Leaf 5))))

Now, this normal form is just a zipper under the rotateL and rotateR operations -- we can rotateR it to any point in the list, with the "rest" of the list elements on the right branch in normal form, and the preceding elements on the left branch in an "inverted" normal form (with leaves on the right branches instead of the left).

Applying interleave to such a zipper will swap adjacent elements at the zipper's cursor in the general case, though the following function also handles the corner cases where interleave fails because the left or right branch is just a leaf:

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

Here, orTry isn't a separate operation -- it's just a conditional control structure that handles the case where a generalized operation fails because, say, the left branch is only a leaf instead of a larger inverted cons list:

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

We can also duplicate the element to the left of the cursor with:

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLR)
  `orTry` dupL

This doesn't handle two corner cases: we can duplicate the rightmost element (i.e., duplicate an element to the right of the cursor) with a swapLeaves >=> dupLeaf => swapLeaves => rotateR => swapLeaves combination, and if the tree is a lone leaf, we can just duplicate it with dup.

We can delete the element to the left of the cursor with:

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

and the last element with a swapLeaves >=> deleteLeaf combination`.

I think it's clear that with there operations to swap, duplicate, and delete leaves together with rotations through the zipper, we can turn any in-order cons list into any other in-order cons list constructed from a subset of its elements.

And, since toList uses only reversible operations, it follows that we can reconstruct the final tree from its in-order cons list, so I think that probably completes the proof that these operations are sufficient.

To establish that they're "minimal" / necessary, we need to show that dropping any one of the primitive operations would make it impossible to handle some case.  It's easy to see that dup and deleteL are necessary, as they're the only operations that can add or remove leaves, respectively.  With the exception of rotateL, all the other operations preserve the binary tree property of "perfection" or "perfect balance" (i.e., the property of having all leaves at the same level), so rotateR is necessary to create an unbalanced tree from a perfectly balanced one.  And finally, flipR is necessary as no remaining operations can change the in-order traversal of a tree's leaves (oops -- actually, this isn't convincing, since dup and deleteL can do this; I'll need to think about this one).

Anyway, here's the full code to play with:

{-# OPTIONS_GHC -Wall #-}
import Data.Maybe (fromJust)
import Control.Monad
import Control.Applicative
import Control.Arrow ((>>>))
data Tree a = Node (Tree a) (Tree a) | Leaf a
data Side = L | R
type TreeOp a = Tree a -> Maybe (Tree a)

rotateR, dup, deleteL, flipR, interleave :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRR >>> rotateL)
    >>> untilDone rotateR

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLL)
  `orTry` dupL `orTry` dup

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

pprint :: (Show a) => Tree a -> IO ()
pprint = putStrLn . unlines . pshow
pshow :: (Show a) => Tree a -> [String]
pshow t = case t of
  Leaf x -> [center 5 $ show x]
  Node x y -> bar ++ xy'
    where x' = pshow x
          y' = pshow y
          xy' = hjoin x' y'
          lft = width x' `div` 2
          rgt = width y' `div` 2
          rest = width xy' - lft - rgt
          bar = [ justify lft rgt $  '.' : replicate (rest - 2) '-' ++ "."
                , justify lft rgt $  '|' : spaces (rest - 2) ++ "|" ]
  where
    spaces = (`replicate` ' ')
    justify l r str = spaces l ++ str ++ spaces r
    width = length . head
    center n str = justify l (l+u) str
      where (l, u) = (n - length str) `divMod` 2
    hjoin x y = go x y
      where wx = width x
            wy = width y
            go (l:ls) (r:rs) = (l ++ r) : go ls rs
            go [] rs = map (spaces wx ++) rs
            go ls [] = map (++ spaces wy) ls

t1, t2 :: Tree Int
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))
t2 = Node t1 (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)))

main :: IO ()
main = do
  pprint t1
  pprint . fromJust $ interleave t1
  pprint . fromJust $ toList >>> rotateR >=> rotateR $ t1


MIS complexity in cubic triangle-free graphs

The paper "The Vertex-Disjoint Triangles Problem" (http://link.springer.com/chapter/10.1007/10692760_3) by Guruswami et al. has the proof of its NP-completeness as Theorem 3.
Update: As stated in a more recent answer to Complexity of Independent Set on Triangle-Free Planar Cubic Graphs, there is a note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara that contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.


This costs minimization problem, is it solvable in polynomial time?

It's a bad practice to use the same variable for two purposes, so I'll say that you have $C$ conflicts $(c_1, c_2, \dots, c_C)$ and similarly $M$ conflict resolution methods. To simplify, let $r_{ji} = 0$ if $c_i$ and $m_j$ are disconnected.
Suppose $t_j$ is a variable indicating how many times method $m_j$ was used we can phrase your problem as
\begin{align}
\min \quad&\sum_{j}p_jt_j\\
\text{s.t.}\quad&\forall i: \sum_j r_{ji}t_j \geq s_i\,,\\
&\forall j:0\leq t_j \leq u_j\,,\\
& \forall j:t_j \in \mathbb{N}_0\,.
\end{align}
What if instead we assume we always start by using every $m_j$ as much as possible, and $n_j$ represents the number of times we do not use $m_j$ (compared to the maximum allowed). Note that $t_j = u_j - n_j$. Substituting gives us
\begin{align}
\min \quad&\sum_{j}p_j(u_j-n_j)\\
\text{s.t.}\quad&\forall i: \sum_j r_{ji}(u_j-n_j) \geq s_i\,,\\
&\forall j:0\leq(u_j-n_j) \leq u_j\,,\\
& \forall j:n_j \in \mathbb{N}_0\,,
\end{align}
which is equivalent to
\begin{align}
\max \quad& \sum_{j}p_jn_j\\
\text{s.t.}\quad&\forall i:  \sum_j r_{ji}n_j \leq -s_i + \sum_j r_{ji}u_j\,,\\
&\forall j:0 \leq n_j \leq u_j\,,\\
& \forall j:n_j \in \mathbb{N}_0\,.
\end{align}
But this is exactly the $M$-dimensional bounded knapsack problem. Thus your problem is NP-hard, but you also get to benefit from the existing literature that give very good practical solvers.


Machine Learning and Neural Networks for High School Students

For high school kids, I think the most important goal is to make sure they're impressed by what they've accomplished. To do that the task needs to be inherently useful. Classic things like the XOR problem or pixel counting aren't going to do the trick, because you're relying on the students to connect the dots and realize that this means you can build it into something cool. You need them to build a system

that does something cool,
which can't easily be accomplished with a handbuilt algorithm,
that seems to behave intelligently.

A few ideas:

Make an environment where agents play a game. Something like tic-tac-toe or rock-paper-scissors is probably best. At the end of the course, you can let the agents that the students have made battle each other in a tournament.
Create a simple a-life environment with 2D creatures with simple sensors and joints. Let students create the neural network for the creatures, so they learn to walk. You can also let them evolve the network topology when creatures mate.
A car driver. Again, this is best with an artificial environment, but you can probably get a dataset somewhere too. This is an example from Tom Mitchell's machine learning where they did this with an actual car and a human driver for the network to learn from.


It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T[p,i]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I_j$ are consecutive. Since $I_j$ are disjoint, when dealing with $x_i$, we only need to consider  how many items in $I_j$ can be picked. Thus, for each $p$ and $i$, let $D[p,i,q]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.


Could an alternating approach yield a fairer solution to the stable marriage problem?

The idea of the Gale-Shapley algorithm is to consider the graph of possible matchings (i.e. marriages) and trim edges that cannot happen in a stable matching. Eventually, we cannot trim any more edges, and then we can read from the graph a stable matching, indeed both the man-optimal and the woman-optimal stable matchings. For this view, check out for example the beginning of Section 6.3 in this paper. In your algorithm, you haven't specified how the final matching is generated (though perhaps it follows from the proposal terminology), so it's hard to evaluate the result. However, since the graph you'll get in the end is probably the same as in the symmetric Gale-Shapley algorithm, the usual extraction procedures probably wouldn't produce anything other than the two optimal stable matchings. Perhaps it's best if you gave a complete pseudocode of the algorithm, and also tested it on a few sample inputs.

The stable matchings form a lattice structure, so you might think it helps to take the two optimal matchings and generate something "in the middle". However, since they are the top and bottom elements in the lattice, neither the join nor the meet would produce anything new. Instead, there are ways to generate random stable matchings, and these might be fairer to both parties.

For more information, consult Knuth's Marriages Stables (available also in English) and Gusfield and Irving's The Stable Marriage Problem: Structure and Algorithms.


Difference Between Tree Automata and Tree Transducers

A tree automaton accepts trees. A tree transducer maps trees into trees. Although string automata generally work natural from left to right, there is no such natural choice for tree automata: they can process the tree from top to bottom, from bottom to top, and there are even models that walk over trees (like two-way string automata walk over the input).

As far as I understand, you example has the following meaning. Your automaton is working top to bottom.

$q(f(x1,\dots ,x3))\to g(a,q′(x1),h(q′′(x3)))$

To the right of the rule we read $q(f(x1,\dots ,x3))$. This means the input is a tree that has a root labelled with symbol $f$. This root has three children represented by the variables $x1,\dots ,x3$. The transducer is at state $q$ when it visits the root labelled $f$.

To the right we see the tree that is constructed when the rule is applied. The tree has a root labelled $g$ and three children. The first child is a leaf labelled by $a$. The next two subtrees are computed by two copies of the original transducer. The second child (of the output) $q′(x1)$ means a copy of the transducer starts at the first child "$x_1$" of the input tree in state $q'$, and the third child $h(q′′(x3))$ indicates a tree with node labelled $h$ which has a single child computed by another copy of the transducer started at the third child "$x_3$" of the input in state $q''$.


Both "original syntax" and PCRE's syntax is not regular. You need parenthesis to override operator precedence, which puts your syntax language into the territory of context free languages.


How curves are represented in a computer

A curve can be quantized (also known as rasterized) to a certain precision after which it is discrete, and the issue is gone. If you see a picture that contains a curve on a modern computer, there's a good chance it already has been rasterized (e.g. PNG or jpeg).

However, it is possible to represent curves (and other primitives) directly. Then you're looking at vector graphics. In most implementations of vector graphics only a couple specific subsets of curves are supported, most often circles, ellipses and Bézier curves. Especially the latter is the most common powerful generic way of storing curves.

It is possible to describe an arbitrary curve through some mathematical framework and storing the mathematical description of the curve. But such a generalized approach is rarely done for computer graphics.