Ford Fulkerson maximum flow for all vertices

"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $O(nm \log(n^2/m))$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm.

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.


This problem can be solved by means of dynamic programming. One of the best known dynamic programming algorithms is for the knapsack problem. It may be instructive to compare the two problems.

Let $C(n,m)$ denote the solution to the maximal weighted sum problem
for the sequence $a_1, a_2, \ldots a_n$ with a subsequence of length $m$ where $1\leq n\leq N$ and $1\leq m\leq M$.

Then $C(n,m+1) = \mathop{max}(C(n-1,m+1), C(n-1,m) + (m+1) \cdot a_n)$.

To compute $C(N,M)$ this algorithm can be implemented in $O(N M)$ time and $O(N)$ space.


Nowadays, all computers are built following certain conventions. One of those conventions is the use of zero and one (i.e. low voltage and high voltage): it's perfectly possible to make computers that don't use zeroes and ones, and in fact the Soviets did so (look into the Setun project). Another of those conventions is that text-based data comes in units of eight bits each, called "bytes".

Each byte holds a number from zero to 255, and more conventions define what each number means. The ASCII standard, for example, says that 65 means "A", while the UTF-8 standard says that 195 followed by 184 means "ø". But there's nothing intrinsically "A"-like about the number 65: it's just a convention people have agreed to follow, to make it easier for programs to work together.

(P.S. When two programs are using different conventions, you get a garbled mess called "mojibake". Nowadays most text data is stored in UTF-8, which helps avoid this, but there are still some holdouts (cough Windows API) who insist on using other conventions instead. It's a headache when you have to deal with that.)


Shortest continuous path between shapes without passing thru other shapes, in a specific order?

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$.  For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*.  The vertices are the grid points labelled "0".  You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0).  You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.

If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$.  Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path).  Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$.  Finally, you can compute the shortest path in this directed graph.


Decision version of the traveling salesman problem and NP-hardness

When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard. In this particular case, according to Wikipedia more is true: the function version (finding an optimal solution) is complete for $\mathsf{FP}^\mathsf{NP}$.


Are there decision problems outside of NP?

The nondeterministic time hierarchy theorem shows that, e.g., $\mathrm{NP}\subsetneq\mathrm{NEXP}$, so any $\mathrm{NEXP}$-complete problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.  For a more extreme example, the halting problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.


Maximizing product of list of integers whose sum equals n

Intuitively the function $(n/x)^x$ is maximized at $x=\frac{n}{e}$ and 3 is closest to $e$.


How many structurally different trees can be formed with n nodes?

Check out A000055. Even if this is not what you want, it is probable that the OEIS has your sequence. The easiest way to look for a sequence in the OEIS is by calculating the first few numbers.


Can a process run if there's not enough space for minimum pages?

There's no set answer; it will come down to what the OS is implemented to do in that situation.  I suppose if you implement the OS poorly, arbitrarily bad things could happen.

But in practice, with modern OS's, there's no such thing as "minimum pages the process needs".  The way virtual memory works is that the process has no idea what pages are actually mapped into physical memory at any times and which ones aren't; the OS transparently pages in pages as needed.  So, that notion doesn't exist.

Thrashing is not a black-and-white phenomenom.  For instance, thrashing can happen if 98% of the CPU time is spend paging pages in and out of memory, and only 2% on running the process itself.  In that case, forward progress is still being made -- just very slowly.


Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

No, it is not possible to prove that all $NP$ problems which are not $P$ are $NP$-complete. In fact, the opposite has been shown: unless $P=NP$, there are $NP$ intermediate problems, neither in $P$, nor $NP$-complete. See https://en.wikipedia.org/wiki/NP-intermediate

So if you reduce an $NP$-complete problem to another $NP$ problem, all you've done is proved that that problem is also $NP$-complete.


Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

It is well known that NFA universality (given an NFA, does it accept all words?) is PSPACE-complete. This easily implies that the following problem is PSPACE-complete:

  Given an NFA, is there an equivalent DFA with exactly one state?

To show that the problem is in PSPACE, note that in order to show that an NFA isn't equivalent to a DFA with exactly one space, it suffices to show that its language is not universal (known to be in PSPACE) and non-empty (can be checked in P).

To show that the problem is PSPACE-hard, we reduce from NFA universality. Given an NFA $A$ over the alphabet $\Sigma = \{0,1\}$, we construct an NFA for the language $L = \epsilon + 0\Sigma^* + 1L(A)$; this requires adding a constant number of states. The language $L$ is never empty, and it is universal iff $L(A)$ is, hence $L(A)$ is universal iff $L$ is accepted by a DFA having a single state.


Does a polynomial-time reduction from A to B imply that B is in NP if A is?

For your proof to work correctly, $f$ must be surjective:

\begin{align}
f: \Sigma_A^\star \to \Sigma_B^\star \\
\forall y \in \Sigma_B^\star \quad \exists x \in \Sigma_A^\star: f(x) = y
\end{align}

Otherwise, you cannot guess a $x$ for each $y \in \Sigma_B^\star$, with $f(x) = y$ in step 1.

Alghough some polynomial reductions are bijective (e.g. CLIQUE $\le_p$ INDEPENDENTSET), a polynomial reductions is not required to be either injective or surjective. This is why your proof fails. There are even proofs that use reductions, whose image only consist of two words.

Example for such an extreme case: Proove that $L_1, L_2 \subseteq \Sigma^\star$, where $L_2 \ne \emptyset$ and $L_2 \ne \Sigma^\star$, both $L_1$ and $L_2$ are in $P$ implies that there exists a polynomial reduction from $L_1$ to $L_2$.

Let $w_t \in L_2$ and $w_f \in \Sigma^\star \setminus L_2$. Construct $f: \Sigma^\star \to \Sigma^\star$, such that
\begin{align}
f(x) = \begin{cases}
w_t  & \mbox{if } x \in L_1\\
w_f  & \mbox{if } x \notin L_1
\end{cases}
\end{align}
Since $L_1$ is in $P$, $f$ simply calls a TM that decides $L_1$ and then outputs the corresponding words. Therefore, $L_1 \le_p L_2$.


As Yuval Filmus states in the comments, any TM (with one tape and one read-write head) whose time complexity is bounded by a function $t$ also has its space complexity bounded by $t$ since, in $t$ steps, the TM can only scan as most as $t$ many tape positions. In terms of complexity classes:
$$\textsf{TIME}(t) \subseteq \textsf{SPACE}(t)$$
$\textsf{P} \subseteq \textsf{PSPACE}$ and $\textsf{EXPTIME} \subseteq \textsf{EXPSPACE}$ is immediate from this. One of the greatest concerns of complexity theory (most of which are yet unsolved questions) is determining under which conditions this is a proper inclusion or not.


Why updating only a part of all neural network weights does not work?

If you're only changing the weights in the last layer, then effectively you have a neural network with a single layer, preceded by some preprocessing step. Single-layer neural networks (also known as perceptrons) aren't so powerful.

Why isn't the network learning anything?  It doesn't learn much because it can't -- a single-layer network can't learn complicated functions.


What do we benefit from using ternary search trees rather than binary search trees?

I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not?

The problem with your data structure is that we cannot tell the difference between searching and selecting a letter. This is what the middle child of the ternary tree is used for: when you've found the letter you're looking for, you step to its middle child.

Here's what a ternary tree for your set of words might look like. I've marked word ends with *.

    K
    | \
    A  S
    |  |
    R  A
    |  |
    I  R
  / |  |
 A  M* A
 |     |
 S*    S*

Querying for "SARAS", for example, would look like this:

[Looking for "SARAS", at node K] S > K, so go right.
[Looking for "SARAS", at node S] S = S, so go down and advance to next character.
[Looking for "ARAS", at node A] A = A, so go down and advance to next character.
etc... (eventually returns true)

Querying for "KSARAS", however, would look like this:

[Looking for "KSARAS", at node K] K = K, so go down and advance to next character.
[Looking for "SARAS", at node A] S > A, so go right.
[Looking for "SARAS", fell off tree] return false.


The idea is to mark a read/write page as read-only when loading it into memory (or after writing it out). If it is written to, a fault will occur. When handling the fault, the operating system looks at it's tables, and notices it should be writeable. So it can record it as "written to" (modified) in it's tables, make it read/write, and allow the operation to proceed. Later writes just add insult to injury, no need to keep track of them.


Understanding kQBF: changing order of quantification?

$\exists x\forall y \hspace{1mm}\varphi$ is not equivalent to $\forall y \exists x \hspace{1mm} \varphi$.

Consider for example the formula "for all $x$ there exists $y$ such that $y=x^2$". When evaluated over the reals, this is true (every real number has a square). However, if you switch the quantifiers you get the statement "there exists $y$ such that for all $x$ it holds that $y=x^2$". Note that this has an entirely different meaning, since now the statement reads "there exists a real number which is the square of all real numbers", and this is obviously false.

The order of quantifiers is important, so you can't trivially reduce $kQBF$ to $(k-1)QBF$.


How can you determine what set of boxes will maximize nesting?

Let $\le_B$ denote the inclusion relation between boxes, i.e. $b_i\le_B b_j$ if we can put the box $b_i$ inside $b_j$. Obviously $\le_B$ is a partial ordering of $B=\left\{b_1,...,b_n\right\}$.

Your question translates to finding the maximal linearly ordered subset of $B$ relative to $\le_B$. A linearly ordered subset is a path in the acyclic directed graph $G$ representing $\le_B$, i.e. $V_G=B$ and $(b_i,b_j)\in E_G\iff b_i\le_B b_j$. We can now reduce your problem into finding the longest path in the DAG $G$. This can be done in linear time with topological sorting. Overall, the time consuming part is constructing $G$, which requires $O(n^2)$ time.


This problem looks like the problem of single stack sorting. "Single" because onle your stack B is used to sort, the stack A is only for input. Donald Knuth has analysed this, and characterized it as the 231-avoiding permutations, and has shown their number equals the Catalan numbers.

Now if my observation is correct, you must have counted wrong (original number you gave was 28). The Catalan numbers are 1, 2, 5, 14, 42, 132,

(added, after you recomputed)
Thus, we get a formula, the number of "single-stack sortable permutations of length n" is the $n$-th Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. That does not yet explain the connection. There is a lot to learn about Catalan numbers, see the wiki-page for a lot of situations where they arise! Also the page to the online encyclopedia of integer sequence I referred to has more than enough links to keep you busy for a long time.


This is an explanation for the Gaussian sum formula (funfact: in German it is called "little Gauss"). Hence, as you recognized, the even here is not correct.

The equality of these sums can be shown inductively or simply by putting them into Wolframalpha

The "even" case works like Raphael stated, but doesn't seem to have any intellectual value.


First row indicates the optimal knapsack for each weight using only that item. Then each subproblem in that row asks what is the maximal value one can reach with using only first item and maximum weight indicated by the columns. Then because your first item would have a weight of 3, there is no way for you to include an item for any total knapsack of weight less than 3. Therefore the optimal knapsack for each weight less than 3 would be 0.

Then the first row would look like:
0 0 0 25 25 25 25 25


How to determine maximum stack size of LL(1) parser?

OK.  So you have a pushdown automaton, and out of all reachable stack configurations, you want to know the stack depth (length) of the longest such configuration.

I have two answers: a simple, practical answer that might suffice for your specific situation but doesn't scale, and a general answer that will apply more broadly.

Simple answer

Enumerate all possible stack configurations. This should be easy.  Just think of this as a giant graph, with one vertex per reachable stack configuration, and an edge from each such stack configuration to every other configuration that is reachable in a single step.  Now use any graph exploration algorithm, such as DFS, to explore the graph.  Out of all the configurations you visit, keep track of which one had the largest stack depth.

You have 5 nonterminals.  If the maximum stack depth is $9$, there will be at most $5^9$ reachable stack configurations, i.e., about 2 million of them.  It's easy to explore all such configurations and store them all in a simple data structure.

Of course this would not scale to larger cases, as the complexity is exponential.

General solution

The set of reachable stack configurations of a pushdown automaton is regular.  Therefore, you can build a DFA that concisely represents all such reachable stack configurations.  This DFA is not too large (linear in the size of the PDA, I think) and can be built efficiently (in quadratic or cubic time, I think).  Then, you can check whether the DFA has any cycles and the length of the longest path in the DFA, and that will tell you the stack depth of the deepest reachable stack configuration.

This will give you an efficient, polynomial-time algorithm that scales even to large, non-trivial grammars.  The cost is that it takes more work to understand the algorithms and implement them correctly, so I'd try the simple solution above first, and only fall back to this if necessary.


"Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations

The number of solutions can easily be huge, so just writing out the solutions will take a long time. But this is not the knapsack problem, which gives you a budget (knapsack capacity) and values of the items, and ask for maximal value (or if some value is atainable).
One way to generate them all is to use backtracking: List all solutions that don't include object 1, then all that do include object 1 once, twice, ... Recursively check for solutions without/with object 2, ... I don't think there can be any more efficient way, and it does prune off combinations that are doomed (can't be extended).
Look if you can narrow the search somehow. Say order the objects so that you get promising combinations early, and cut off the search when you get enough of those.


A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of $2.1$, which is greater than using a code of fixed length $2$, so it can't be correct.

If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 and 4 you get one supernode of priority 0.4. Now your queue would have three elements of priorities $0.3, 0.3,$ and $0.4$. Thus, you would next merge elements corresponding to priorities $0.3$ and $0.3$ (the algorithm works by merging two nodes with lowest priorities), which happen to be nodes 1 and 2.


What are the vertical and horizontal focal lengths?

Note that they assume a pinhole camera model. The term 'focal length' means something different here than it does with a lens camera.

All you ever really need to know about the pinhole camera model can be expressed as:
$$x_\mbox{imageplane} := x_\mbox{world}/z_\mbox{world}$$
$$y_\mbox{imageplane} := y_\mbox{world}/z_\mbox{world}$$
This describes how points in the scene project to an image plane 1 unit in front of the camera origin (center of projection & center of world coordinate system), with the optical axis along the z direction.

All the other values usually discussed in connection with pinhole cameras 'just' describe which rectangular part of the image plane is mapped to the rectangle of pixels that is your image. Or, conversely, how pixel coordinates can be transformed back into points on the image plane (and from there, can be transformed to directions in the scene).

Of course this rectangle-on-a-2d-plane can be defined by a 2d point
$b$ and two 2d vectors $v_1, v_2$ such that:

$$\begin{bmatrix}x_\mbox{image}\\y_\mbox{image}\end{bmatrix} :=
\begin{bmatrix}\vec{v_1}&\vec{v_2}\end{bmatrix}
\begin{bmatrix}x_\mbox{imageplane}\\y_\mbox{imageplane}\end{bmatrix} + b$$
If we abbreviate this as $(x_\mbox{image},y_\mbox{image}) = f(x_\mbox{imageplane},y_\mbox{imageplane})$ the part of the imageplane that your image depicts is the set $f^{-1}([0,\mbox{width}]\times[0,\mbox{height}])$ which, as I said, is a rectangle1.

The 'other values', for example:

optical center: $c_x, c_y$ or $c_u, c_v$
horizontal and vertical 'focal length': $f_x, f_y$ or $f_u, f_v$
aspect ratio
field of view angle $\alpha$
shear (you don't usually want that)

are just used to describe special cases of the above formula.

In your case, $b = (c_u, c_v)$ and $v_1 = (f_u,0), v_2 = (0,f_v)$ such that

$$\begin{bmatrix}x_\mbox{image}\\y_\mbox{image}\end{bmatrix} :=
\begin{bmatrix}f_u x_\mbox{imageplane} + c_u\\f_v y_\mbox{imageplane} + c_v\end{bmatrix} $$

1 Note that it is not the rectangle with corners $b, b+v_1,b+v_2,b+v_1+v_2$. To find it you'd have to compute the inverse of the function $f$.


How to apply a 1-qubit gate to a single qubit from an entangled pair?

I came to a conclusion that we do not actually take away a single qubit from an entangled pair and operate it, but operate on both qubits with Identity operator on the one we do not want to change.

So basically to apply Pauli X gate to the first qubit from an entangled pair, we apply X tensored with $I$ to the entangled pair to get the result.
That is, to operate a not on the first qubit, we evolve the system by
$$ \sigma_x \otimes I =
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}
\otimes
\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}
=
\begin{pmatrix}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0&  0
\end{pmatrix}
$$

Intuitively it is like applying a single operation to the first qubit and identity to the second one (effectively not changing its state).

Thus if we start with the entangled state $|\psi\rangle \frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ we end up with
$$ (\sigma_x \otimes I)|\psi\rangle =
\begin{pmatrix}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0&  0
\end{pmatrix}
\cdot \frac1{\sqrt{2}}
\begin{pmatrix}1 \\0 \\0 \\1 \end{pmatrix} =
\frac1{\sqrt{2}}
\begin{pmatrix}0 \\1 \\1 \\0 \end{pmatrix} =
\frac1{\sqrt{2}}(|01\rangle+|10\rangle)
$$


My preference is for Coq, but I imagine that others prefer Isabelle. One of the strange things I found about Isabelle is that there is a two-level syntax, where some of your definitions need to be inside double quote. No such nonsense is present in Coq.

Ultimately, the one that is most suitable for you may depend on what you want to prove. Both languages have a lot of library support and active communities doing all sorts of development and example theories. If one language provides  adequate library (or other) support for the kinds of theory you wish to develop, then I'd select that language.

One strategy is to do a simple tutorial in both languages and follow up the one that feels the best. For example,

Coq in a Hurry by Yves Bertot, or
the first part of A Proof Assistant for Higher-Order Logic by Tobias Nipkow, Lawrence C. Paulson and Markus Wenzel.

Here is a blog post briefly comparing the two by someone who ultimately prefers Isabelle.

Make sure you use a proper IDE (such as ProofGeneral), rather than doing things on the command line.

Another way to to get into Coq is to try the online book Software Foundations by Benjamin Pierce et al. It provides an excellent tutorial with loads of details provided. The focus is mostly on programming language semantics, but a lot of the basics (and beyond) of Coq and semi-automated theorem proving are covered along the way.


I think your "possible way" is a known variant of "locality sensitive hashing", which is what you're looking for, I suspect.


Neural network diverging instead of converging

With neural networks, you always need to randomly initialize your weights to break symmetry.
If you don't use a non-linear activation function in the hidden units, then you might as well have stayed with a single layer. Your network is now just a composition of two linear functions, which is of course just another linear function.
That learning rate seems excessively small. If I'm using a fixed learning rate I normally find a value somewhere between 0.1 and 0.0001 to work well for most problems. This is obviously problem dependent so take my experience for what it is.
In addition to checking your code against the math you've learned, when doing gradient based optimization it can be very helpful to analytically calculate the gradients required using finite differences and compare them to the values you're computing in your code. See here for a discussion of how you can do this. I've caught many errors this way and seeing these types of tests pass always helps me feel much more sure of code correctness.


How can I understand a hint for finding the lowest height of the last bulb in a Garland?

Short answer

Let $d=h_1-h_2$. Do a binary search for the largest value of $d$ in interval $[0,A]$ so that none of $n$ bulbs in the garland will be lower than the ground. The wanted minimum value of the second endpoint $B$ corresponds to the case when $d$ is that largest value.

Explanation

The question is how to understand the hint "you can use binary search".

Before understanding the hint, we are supposed to have understood what is binary search. Binary search is a search algorithm that finds the position of a target value within a sorted array or an interval.

So, what could be that target value we are supposed to search? Within which sorted array or which interval?

The most obvious target value to search is $m$, the minimal value of $B$. We could search $m$ within the interval $[0, \text{FM}]$, where $\text{FM}$ is the maximum value of a floating-point number.
Another obvious target to search is about that lowest bulb. In case there are two lowest bulbs, the lowest bulb will mean the one to the left. The further to the right the lowest bulb is, the lower value $B$ is. We could search $\ell$, the rightmost possible position of the lowest bulb within the interval $[0,n]$.

Whenever we started to compute, we find we have to understand clearly the given equality, $\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1.$ If $h_1=A$ and $h_2$ are known, the height of every bulb is fixed, since
$$h_{3}=2\times h_{2}-h_{1}+2$$
$$h_{4}=2\times h_{3}-h_{2}+2$$
$$\cdots$$

The only requirement is that no bulb can be lower than the ground. Note that

$$\displaystyle h_{i+1}-h_i=h_{i}-h_{i-1}+2.$$

As we visit the bulb from left to right, the bulb is dropping less and less between each pair of successive bulbs initially. Once the bulb have reached the lowest level, it will climb more and more between each pair of success bulbs.   The larger the first drop $h_1-h_2$ is, the more likely one of the $n$ bulbs will hit the ground and the lower the last $B$ will be. Aha, we can also search the largest value of $h_1-h_2$ within interval $[0, A]$.

How to binary search a real number?

How can we search for the largest value of $d$, which is a real number in an interval?

Since there are infinitely many real number in an interval, checking equality is not likely to work as the stopping condition. That is why we are given the requirement for the "the minimal height of the second endpoint" that it differs from the right one by at most $10^{−6}$". The pseudocode looks like the following.

'''A=h_1, n are given.'''

'''10^(-7) instead of 10^(-6) to guard against rounding errors in computation of floating-point numbers'''
precision = 10^(-7)

function get_largest_first_drop_by_binary_search():
    L = 0
    R = A
    B_L = last_height(L)
    B_R = last_height(R)
    while ( B_L - B_R > precision):
        m = (L + R) / 2.0
        if hit_ground(m):
           R = m
           B_R = last_height(R)
        else:
           L = m
           B_L = last_height(L)
    return B_L

function last_height(d):
    ''' Given first drop h_2 - h_1 = d, return h_n, the height of last bulb'''
    return A + ((-d)+(-d+2(n-2)))(n-1) / 2

function hit_ground(d):
    ''' Given first drop h_2 - h_1 = d, return true iff the garland will hit the ground '''
    k = floor(d/2) + 2
    if k >= n return last_height(d) < 0
    if k < n return A + ((-d)+(-d+2(k-2)))(k-1) / 2 < 0
    return false

Implementation

Here is an implementation in Java. Click the run button to see the result.

Exercise

Show that the minimum value of the second endpoint $B$ is 0 if and only if $A \ge (n-1)(n-2)$.


If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

Yes.

The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.

Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.

But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.

Thus, there's a contradiction, and such a tree cannot exist.

(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)


STCON in L using matrix multipication algorithm?

A machine runs in logarithmic space if the working space it requires (excluding the read-only input and the write-only output) is at most logarithmic in the number of bits required to represent the input.

For matrix multiplication, the input is the two matrices, and the output is their product. The only working space is, as you say, the "loop counters" for stepping through the current row and column to compute the next bit of the output.

For graph connectivity, the input is the adjacency matrix of the graph, along with the two vertices of interest, and the output is the single bit "yes" or "no". Your proposed algorithm requires remembering the matrix of paths you've discovered so far, which has size $n^2$, and that's not logarithmic.


There's no such thing as a "valid" or "invalid" codeword. If a string of bits is a codeword in a particular code such as a Hamming code, it's "valid"; if it's not a codeword, it's "invalid".


Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

Your algorithm is from the paper Problems complete for deterministic logspace by Cook and McKenzie, where it is used to perform DFS on trees, as well as for related problems such as cycle detection. Presumably it doesn't work on graphs with cycles.


What is the intuition behind Strassen's Algorithm?

The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a certain sense: it is known that all such algorithms are equivalent, as shown by de Groote in his 1978 paper, On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for 2 × 2-matrix multiplication.
There are many attempts in the literature to explain how one could come up with such an algorithm, for example:

Gideon Yuval, A simple proof of Strassen’s result, 1978. We explain this approach below.
Ann Q. Gates, Vladik Kreinovich, Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark, 2001. The idea is to use symmetries to guess the linear combinations corresponding to one of the matrices being multiplied, and then to pair them intelligently with linear combinations of the other matrix.
Jacob Minz, Derivation of Strassen's Algorithm for the multiplication of 2×2 matrices, 2015. The idea is to apply linear transformations to obtain a simpler looking problem, and then to solve it by hand.
Christian Ikenmeyer, Vladimir Lysikov, Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective, 2017. The idea is to consider a basis for the $2\times 2$ traceless matrices, and use its multiplication table to construct Strassen's algorithm.
Joshua A. Grochow, Christopher Moore, Designing Strassen’s Algorithm, 2017. The idea is to start with vectors which form the vertices of an equilateral triangle in the plane, and use elementary properties of these vectors to come up with an algorithm.

Gideon Yuval shows how you could come up with Strassen's algorithm. The starting point is to convert matrix multiplication to the problem of computing a matrix-vector product: computing
$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \end{pmatrix} $$
is the same as computing
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & c & 0 \\
0 & d & 0 & d
\end{pmatrix}
\times
\begin{pmatrix} e \\ f \\ g \\ h \end{pmatrix}
$$
Suppose that we could write the matrix on the left as a sum $\ell_1 M_1 + \cdots + \ell_7 M_7$, where $\ell_i$ is a linear combination of $a,b,c,d$ and $M_i$ is a rank one matrix, say $M_i = x_i y_i^T$. The product we are after is thus
$$
\sum_{i=1}^7 \ell_i M_i \begin{pmatrix} c\\d\\e\\f \end{pmatrix} =
\sum_{i=1}^7 \ell_i x_i y_i^T \begin{pmatrix} c\\d\\e\\f \end{pmatrix} =
\sum_{i=1}^7 \ell_i r_i x_i,
$$
where $r_i$ is a linear combination of $e,f,g,h$. This shows that each entry of the product matrix is some linear combination of the products $\ell_i,r_i$.
Let us now show how one could find the decomposition. We start by cancelling the top left and bottom right entries, in a way which avoids hitting zero entries:
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & d & 0 \\
0 & c & 0 & d
\end{pmatrix} =
\begin{pmatrix}
a & 0 & a & 0 \\
0 & 0 & 0 & 0 \\
a & 0 & a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & d & 0 & d \\
0 & 0 & 0 & 0 \\
0 & d & 0 & d
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & a-d & 0 & b-d \\
c-a & 0 & d-a & 0 \\
0 & c-d & 0 & 0
\end{pmatrix}
$$
This results in a mess, which we try to fix by "flipping" the inner square:
$$
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & a-d & 0 & b-d \\
c-a & 0 & d-a & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} =
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & a-d & a-d & 0 \\
0 & d-a & d-a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & d-a & b-d \\
c-a & a-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix}
$$
Since $d-a = (b-a)-(b-d)$ and $a-d = (c-d)-(c-a)$, it is easy to represent the last matrix as a sum of four rank one matrices:
$$
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & d-a & b-d \\
c-a & a-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} =
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & b-a & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & d-b & b-d \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & c-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
c-a & a-c & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix}
$$
In total, we obtain the following representation:
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & d & 0 \\
0 & c & 0 & d
\end{pmatrix} =
\begin{pmatrix}
a & 0 & a & 0 \\
0 & 0 & 0 & 0 \\
a & 0 & a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & d & 0 & d \\
0 & 0 & 0 & 0 \\
0 & d & 0 & d
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & a-d & a-d & 0 \\
0 & d-a & d-a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & b-a & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & d-b & b-d \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & c-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
c-a & a-c & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix}
$$


Language of words that begin and end with same symbol and have equal numbers of a's and b's

Here is the thought process I would use.  I would notice that your language $L$ can be written as $L= L_1 \cap L_2$, where $L_1$ is the set of words that begin and end with the same symbol, and $L_2$ is the set of words that have equal quantities of a's and b's.

Then, I would note that $L_1$ is regular and so can be expressed by a simple DFA (with 5 states).  Also, I would note that $L_2$ is context-free and can be expressed by a simple CFG: e.g., $S \to \varepsilon \mid aSb \mid bSa \mid SS$.

Finally, I would recall the standard closure property: the intersection of a regular language and a context-free language is context-free.  It follows that $L_2$.  The proof of this standard closure property includes a construction that shows how to construct a CFG for $L_2$, given a DFA for $L_1$ and a CFG for $L_2$.  This gives a CFG for your language.  The resulting CFG will have $5^2=25$ non-terminals; some of them are unreachable and can be pruned, but the result is still quite messy.

The resulting CFG isn't the simplest or smallest CFG for your language.  Whether it is the most natural is open for debate.  But since you asked for the thought process behind coming up with a grammar, this illustrates one general technique for constructing CFG's: separate out the part that requires something more than finite state (equal quantities of a's and b's) from the part that can be handled with a finite-state automaton.


Matching schedules between users and providers

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.

For instance, considring only one day for user from 8h to 14h:

provider 1: 7h-10h
provider 2: 6h-9h
provider 3: 10h-16h

The cut-off is:

6h-7h
7h-9h
9h-10h
10h-16h

and your problem is solving the minimum set cover of {2, 3, 4} with:

provider 1: {2, 3}
provider 2: {1, 2}
provider 3: {3, 4}

with evident solutions providers 1&3 or 2&3.

Nevertheless, this is a NP-problem and you likely have to test most of combinatoric if you really want to get optimal solutions. Sometimes this type of application contain some constraints or patterns that may help you to reduce the problem.


Finding median of 2 sorted arrays in O(log n)

There are two arrays: $A, B$ with lengths $n, m$. Finding median in the sorted array takes constant time (just access middle element or take a mean of two center elements).

To find the median of all elements in $\mathcal O(min(\log n, \log m))$ perform the following steps:

If $(length(A) \le 2$ or $length(B) \le 2)$ or $(A _{last} \le B_{first}$ or $B_{last} \le A_{first})$ calculate median and return.
Set $A_m = median(A), B_m = median(B)$ and compare them. If $A_m = B_m$ return result. If $A_m < B_m$ then discard first half of $A$ and the same amount of elements from the second half of $B$. else if $A_m > B_m$ then discard second half of $A$ and the same amount of elements from the first half of $B$.
Goto 1

This algorithm runs in logarithmic time. Minimum in the complexity reflects the fact that when the smaller array has length $\le 2$ the procedure terminates. At step 2 the both arrays get halved (or procedure is terminated) so it will be performed at most $\log_2(min(n, m))$ times.

By calculate median there are two cases: at least one arrays length was $\le 2$, so shift the median of the second array accordingly, or arrays do not overlap (or share the boundary element) then the median is the center element of two arrays concatenated in ascending order. In fact only index is calculated, no actual concatenation takes place.

Why the procedure stops when at least one of lengths is $\le 2$? Consider the corner case, e.g. A = [2, 9], B = [3, 11], the median is 6, but taking them separately yields 5.5 and 7, which in turn yields incorrect result 6.25.

For example:
$A = [1, 2, 6, 8, 12, 15], B = [2, 5, 8, 15]$  to keep an overview, the whole sorted array $C = [1, 2, 2, 5, 6, 8, 8, 12, 15, 15], C_m = 7$.
$A_m = 7, B_m = 6.5$ now $A_m > B_m$ so we drop [12, 15] from $A$ and we drop [2, 5] from $B$. Why $8$ is not dropped from $A$? Bacause we cannot drop $8$ from $B$, and in order to preserve median we can only drop the same number of elements ftom the both arrays at the opposite sites of the mean.
So $A = [1, 2, 6, 8], B = [8, 15]$. Now back to step 1, the arrays do overlap by common element at the end so we take $AB$, the lengths are 4, 2, so it is a mean of 3rd and 4th element $\frac{6 + 8}{2} = 7$.


If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$

Yes. Actually, it is even true that for every language $L_1$ there is a language $L_2 \supseteq L_1$ such that $L_2$ is regular.

Proof: Pick $L_2 = \Sigma^*. \square$


Problem with derivative of sigmoid activation function

The derivative of a sigmoid is always positive.  Here's my math: Sigmoid(1.13) = 0.7558

I computed this on Wolfram Alpha

The derivative of a sigmoid y=S(x) is y * (1-y), so 0.7558 * 0.2442 = 0.0451


Is the graph symbol used in dask a general notation?

It's... a visualization. Don't read too much into it. Graphs in computer science are formalized, but unless specifically mentioned a visualization of a graph doesn't have a formal underpinning. They're generally self-explanatory, there are objects (nodes) and arrows (edges).

UML is more of the exception than the rule, being a graphical language with a formal interpretation. Most visualizations in computer science aren't that strict in meaning.

Here it seems that the round nodes are functions, the square nodes are (temporary) variables, and the arrows indicate data flow.


Algorithm to determine which neighborhoods of a graph contain a given set of vertices S

In fact, the set of the vertices whose neighborhoods contain S is exactly

$$\bigcap_{j=1}^mN(v_{i_j})$$

Proof:

since it's an undirected graph, $v\in N(u) \Leftrightarrow u\in N(v)$. A vertices $v$ whose neighborhoods contain S means that $\forall u\in S, u\in N(v) $, which is equivalent to $\forall u\in S,v\in N(u)$, thus $\bigcap_{j=1}^mN(v_{i_j})$ is the desire set.

So the problem is equivalent to that:

  Given m (unordered?) lists, get the intersection of them

One can solve it in $O(n\log n)$ easily by maintain a balanced BST like a std::set.

Or just solve it in $O(n)$ by hashing.


how does $PATH$ being $NL$-complete help to prove $NL = coNL$

$\mathsf{NL}$ consists of all languages accepted by nondeterministic Turing machines using logarithmic space. One way to think of such machines is as follows:

The input is written on a read-only input tape.
There are one or more work tapes of logarithmic size.
There is a read-only oracle tape on which the head is constrained to only move to the right.

We can think of each such machine as computing a Boolean function on two arguments: $x$, which is the actual input, and $y$, which is the initial contents of the oracle tape. Such a machine $M$ nondeterministically computes the language $L(M)$ given by:
$$
x \in L(M) \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}.
$$
In other words, a language $L$ is in $\mathsf{NL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that
$$
x \in L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ accepts}.
$$

A language is in $\mathsf{coNL}$ if its complement is in $\mathsf{NL}$. Equivalently, a language $L$ is in $\mathsf{coNL}$ if there exists a logspace Turing machine $M$ with an auxiliary oracle input such that
$$
x \notin L \Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}.
$$
Equivalently,
$$
x \in L \Longleftrightarrow \forall y \text{ $M(x,y)$ accepts}.
$$

Suppose now that $L$ is in $\mathsf{NL}$, say $L = L(M)$, and let $M'$ be obtained from $M$ by complementing the output. Then
$$
x \in L(M') \Longleftrightarrow \exists y \text{ s.t. $M'(x,y)$ accepts}
\Longleftrightarrow \exists y \text{ s.t. $M(x,y)$ rejects}.
$$
As you can see, $L(M')$ isn't necessarily the complement of $L(M)$. Indeed, given any machine $M$, we can come up with another machine $\tilde{M}$ such that $L(M) = L(\tilde{M})$, but $\tilde{M}(x,y_0)$ always rejects, for some fixed $y_0$ (for example, $\tilde{M}(x,0\Sigma^*)$ always rejects, and $\tilde{M}(x,1y) = M(x,y)$). In this case, $L(\tilde{M}') = \Sigma^*$.

Now I can answer your questions:

$\overline{\mathsf{PATH}} \in \mathsf{coNL}$ since $\mathsf{PATH} \in \mathsf{NL}$ and by definition $\mathsf{coNL}$ consists of the complements of all languages in $\mathsf{NL}$.
Furthermore, $\overline{\mathsf{PATH}}$ is $\mathsf{coNL}$-hard because $\mathsf{PATH}$ is $\mathsf{NL}$-hard. Indeed, suppose that $L \in \mathsf{coNL}$. Then $\overline{L} \in \mathsf{NL}$. Since $\mathsf{PATH}$ is $\mathsf{NL}$-hard, there is a logspace reduction $f$ such that $x \in \overline{L}$ iff $f(x) \in \mathsf{PATH}$. Thus $x \in L$ iff $f(x) \in \overline{\mathsf{PATH}}$, and so $f$ also reduces $L$ to $\overline{\mathsf{PATH}}$.
Flipping the output value of a nondeterministic machine does not result in complementing the accepted language.

Elaborating on the second point, for some nondeterministic complexity classes $\mathsf{X}$, it is known that $\mathsf{X} \neq \mathsf{coX}$. The simplest example is $\mathsf{RE} \neq \mathsf{coRE}$: the halting problem is in $\mathsf{RE}$ but not in $\mathsf{coRE}$. Therefore $\mathsf{NL} = \mathsf{coNL}$ is a nontrivial statement.


Why are processes on the internet not required to use TCP or UDP?

In this context, a process is a normal computer application process, e.g., as defined in wikipedia:

a process is the instance of a computer program that is being executed by one or many threads. It contains the program code and its activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently

So, as Tanenbaum points out, a process that wishes to communicate over the Internet, need not use TCP or UDP. In fact, there are other transport protocols besides TCP or UDP, although those two are the most common. See wikipedia on transport protocols for other transport protocols like SCTP and DCCP. NAT boxes that need a TCP source port to work, would not be able to properly work with other transport protocols. I think Tanenbaum gives the example of a multimedia application, because the requirements can be quite different, e.g., for real-time multimedia, where there is yet another transport protocol combination, RTP/UDP/IP (Realtime Transport Protocol over UDP, then over IP) that is better suited for multimedia traffic than TCP/IP.
Why do we hear the phrase TCP/IP so often? Because we hear that, we may get confused and think like you thought, that TCP was "part of" IP. Actually, TCP and IP are separately protocols on different layers of the protocol stack (transport layer and network layer, respectively). However, in the Internet, TCP is so commonly used, that people started saying TCP/IP, for communications using TCP over IP.


Quantum computers, if they ever get built, will be asymptotically faster than existing computers in certain tasks. Limited quantum computers might already exist, though this is a contentious issue.


Are two non-Turing-recognizable languages closed under union?

Let $U\subseteq \mathbb{N}$ be any unrecognizable set. Let $L_1 = \{0, 2, 4, \dots\} \cup \{2n+1\mid n\in U\}$ and $L_2 = \{1,3,5, \dots\} \cup \{2n\mid n\in U\}$. $L_1$ and $L_2$ are both unrecognizable but their union is $\mathbb{N}$.


Leveling array values with the smallest move

Your problem seems to be the same as that of calculating the Earth mover distance between the starting and target distributions. Wikipedia suggests using the Hungarian algorithm to calculate the distance.


I doubt that AC0 can be captured by constant depth threshold circuits, but this hasn't been proved. In the case of small weights, perhaps existing methods suffice to rule out all of AC0 being captured by depth 2 threshold circuits. See Razborov's survey for several pointers, include exponential lower bounds for functions which, unfortunately, are beyond AC0

In the case of unbounded weights, we don't have any superpolynomial lower bounds. The best known lower bound for unrestricted depth two threshold circuits due to Kane and Williams, is $\Omega(n^{3/2})$.


LCA from children using bottom up approach?

Here is one approach. Given leaves $\alpha,\beta$, first compute the depths $d(\alpha),d(\beta)$ of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent operation until you reach the root). Suppose without loss of generality that $d(\alpha) \geq d(\beta)$. Replace $\alpha$ with $\alpha$'s $(d(\alpha) - d(\beta))$'th parent. The least common ancestor doesn't change, and so we can assume without loss of generality that $\alpha$ and $\beta$ are at the same depth.

If $\alpha = \beta$, then $\alpha$ is the least common ancestor. Otherwise, replace both $\alpha$ and $\beta$ with their parents. This doesn't change the least common ancestor. Continue like that, and eventually you will find the least common ancestor.


Expert systems are called "Experts" for a reason. They are cable of doing a particular job at up most perfection. Not 100% but 99%. Now I am no expert on these systems (pun intended) but as far as these two algorithms go my answer would be to try to boil down to the exact purpose of your system. These two algorithms do two different things. All in all what I am saying is to find an concrete job that your expert system will do. Using the Stable Marriage algorithm you will be ranking and connecting vertices with edges accordingly to their respective weights. As for the Maximum Matching algorithm you will be trying to find the lone vertices and edges. At this point according to your needs I would try to find something in between or edit the Stable Marriage algorithm to fits your needs.

Good luck! You have chosen to tackle a very strong problem ;)


How to prove transitivity of < (Software Foundations exercise)?

Not all relations are transitive, so you're going to need to use the definition of lt and le, or some lemma that you've already proved about them.

Intuitively speaking, there are two cases: either $m = o'$ or $m \lt o'$. In the first case, Hnm says that $S(n) \le o'$, from which the conclusion is one application of le_S away. In the second case, you can apply IHo'.

This form of reasoning assumes some very well-known facts about arithmetic. (It's usually hard to formally prove something if you don't already have some intuition about the topic.) But you haven't proved them yet, so you can't directly use them. Instead, you have to make these cases appear via the construction of the data or the proof. It's very common to reason about the structure of a proof hypothesis: such-and-such hypothesis is of this form, and therefore it can only have been constructed in a certain way.

An important tactic for reasoning about the structure of a hypotheses in a non-recursive way is inversion. Roughly speaking, inversion does case analysis on a hypothesis and works out how these cases can be possible, unlike destruct which does case analysis but loses information on how the hypothesis could be possible. We want to reason about how $m \le o'$ can be possible, and there's a hypothesis that's very cloes to this: Hmo. So apply the tactic inversion Hmo.

I'll let you work out the details of the proof. If you don't care about the details, Coq will fill them in for you, but as a learning exercise you should complete these auto steps by hand.

Theorem lt_trans'' :
  forall n m o, n < m -> m < o -> n < o.
Proof.
  unfold lt.
  intros n m o Hnm Hmo.
  induction o; inversion Hmo; subst; auto.
Qed.


What does "bounded above" mean in Family of Bachmann–Landau notations?

A quantity $a$ is bounded above by a quantity $b$ if $a \leq b$.

A quantity $a$ is bounded above (up to constant factor) by a quantity $b$ if there exists a constant $C>0$ such that $a \leq Cb$. (This makes sense when $a,b$ depend on some other variable).

A quantity $a(n)$ is bounded above (up to constant factor) asymptotically by a quantity $b(n)$ if there exist constants $N,C>0$ such that $a(n) \leq Cb(n)$ for all $n \geq N$. This is usually expressed as $a(n) = O(b(n))$.


Is every language with a finite number of strings regular?

Yes. Assume the language is $L=\{w_1,w_2,\ldots, w_n\}$. then you can form the regular  expression $w_1 + w_2 + \cdots + w_n$, which describes $L$.
You can also argue with finite automata or regular grammars.

Yes, if your alphabet is $\Sigma=(a_1,\ldots,a_k)$ then the regular expression $(a_1+a_2+\cdots +a_k)^*$ describes the languages of all possible strings over $\Sigma$.


Is there a greedy algorithm to solve the assignment problem?

The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem.

The commonly used solution is the Hungarian algorithm, see

Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955

for the original paper.

Otherwise your solution seems correct to me, and as usually with greedy algorithms, it will provide you a feasible solution which you may hope to not be "too far" from the global optimal solution.


Is safety-critical software a subset of real-time software?

I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

A good example of a safety critical program which does not itself have to meet real time constraints is a compiler.

If a compiler has code generation bugs, then even if the programmer wrote a safe program, the emitted machine code may still fail to meet some necessary guarantees. As a result, the standard practice at many development teams developing safety-critical software is to generate code with compiler optimizations turned off, and then to manually review the generated machine code.

The Compcert C compiler has a machine-checked formal proof showing that it never  generates incorrect assembly programs for any input program. As a result, it is possible to (a) limit code review to the C source code, and (b) permit the compiler to do optimization passes, without compromising the safety of the overall system. (See for example Towards Formally Verified Optimizing Compilation in Flight Control Software...)

Obviously, if you are trusting the compiler to generate code for flight control software, it is safety-critical. Equally obviously, a compiler is not real time software.


Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

It depends on the numbers in the array. For example if all array elements are positive integers, and the requested sum is S, then O(nS) is easy.


Given two Turing machines $M_1$ and $M_2$, assume that their state sets are disjoint, i.e, $Q_1 \cap Q_2 = \emptyset$. Define $\Sigma_3 = \Sigma_1 \cup \Sigma_2, Q_3=Q_1\cup Q_2, F_3=F_2$.

Modify $M_1$ so that it prints its output starting from the first (leftmost) tape cell, then move the tape head to the leftmost cell and enter the $M_2$'s start state. This makes sure that $M_2$'s input is the $M_1$'s output. You may also need to add new states to $Q_3$ .


Complexity analysis of recurrence with multiple variables

Since you know only $O$-bounds for the basic operations, you can not derive more precise bounds for $f$, nor $T$. Furthermore, if you had exact cost functions for the basic operations, solving divide-and-conquer recurrences exactly is very hard.

So, what the exercise authors probably want you to do is to say,

$f \in \Theta(m^2)$ (assuming that the bound for multiplication is tight, which they probably wanted to imply but didn't express properly) in either case, and
solve the schematic recurrence using the Master theorem (e.g. by substituting $f(m)$ with $m^2$).

You'll get out the correct $\Theta$ bound that way.


An algorithm to efficiently insert a list of elements into a binary heap ("bulk insertion")

Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time.

It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \log n)$.

Altogether, we can add $k$ elements to a heap of length $n$ in time $O(k + \log k \log n)$: first build a heap containing $k$ elements to be inserted (takes $O(k)$ time), then merge that with the heap of size $n$ (takes $O(k+ \log k \log n)$ time).

Compare this to repeated insertion, which would run in time $O(k\log n)$.


Is it decidable if a TM takes at least 2016 steps on all inputs?

A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This gives an algorithm for deciding $L_1$: run the input machine $M$ on all inputs of length at most 2015, and check whether any of them stops within 2015 steps. If so, reject. Otherwise, accept.


Let's take a simple example, Counting word into a distributed set of documents:

each mapper takes in input a list of document, and returns a list of pairs word and how many times this word occurs. There is an intermediate layer that takes the outputs of all the mapper and groups values by key. After that the reducer will sum each of this value.
This is a practical example:

Output of 3 mappers

Mapper1
(house,4)
(dog,2)
(cat,1)
Mapper2
(dog,3)
Mapper3
(cat,5)
(house,6)

before give these data to the reducer the intermediate layer will group them by key.
obtaining :

(house, (6,4))
(dog,(3,2))
(cat,(5,1))

After that reducers take in input these pairs and sum values:

Reducer 1
(house ,(6,4))-> (house,10)
Reducer 2
(dog,(3,2)) -> (dog,5)
(cat,(5,1)) -> (cat,6)

The MapReduce idea comes from a paper by google that you can find here:
http://research.google.com/archive/mapreduce.html

reading this article you will notice that the mapper gives in output a list of pairs, but the reducer takes in input a pair of (key , list(value)) this implies that there is something in between that "lists" all values with the same keys. This task is done on the output of ALL the mappers, this task is optimized , sorting values ecc.. but as i say is in practice done on all the mapper.

If you know a little of java i suggest you to try something using the Hadoop framework by Apache

as you can see in the linked example the CombinerFunction(the intermediate layer that i've mentioned) works on the same input of the reducers.


This appears to be the maximum subgraph isomorphism problem: given graphs $G,H$, you want to find the largest pairs of subgraphs $G',H'$ that are isomorphic (where $G'$ is a subgraph of $G$ and $H'$ is a subgraph of $H'$ and $G'$ is isomorphic to $H'$).  Then the edges of $G',H'$ are common to both $G$ and $H$.  Apparently, this problem has been applied in chemistry, which might be of interest to you given the diagram you showed.

In the comments you asked about the case $G$ and $H$ both have two common subgraphs which are not connected to each other.  The maximum subgraph isomorphism solution will automatically find those.  Nothing requires $G'$ or $H'$ to be connected.  Thus, in your case, the optimal solution will have $G'$ consist of two disconnected components, and $H'$ consisting of the same two components.  So, this problem already does what you want.

This problem is NP-hard for general graphs, so the general expectation is that there's not likely to be any efficient algorithm that can handle large, general graphs.  However, you have two aspects that offer room for hope.  First, it appears that your graphs are relatively small, so there might algorithms that are acceptable for graphs that are about the size of the examples in your diagram: even exponential-time algorithms might be practical.  Second, and more importantly, it looks like you aren't dealing with arbitrary graphs.  As Tom van der Zanden accurately explains:

  The graphs shown in the example are both trees and they appear to be models of molecules. While of course molecules (like benzene) can have cycles, depending on what molecules the OP is interested in the problem may not be NP-hard.

So, I suggest you search the research literature to see if there's been work done on the maximum subgraph isomorphism problem for trees.  There might be algorithms that have been described in the algorithms literature that you could use.


Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign.  So the only time that a SAT solver would save by early notification is the time it would take to assign values to any remaining unassigned variables.  This is a one-time cost linear in the number of variables in the formula.  It's linear because there can be no backtracking once the formula is solved.

Meanwhile, to maintain your watched clause pointer you must do a search to find a new unsatisfied clause each time your watched clause is satisfied.  That search is linear in the number of clauses in the formula.  These searches will be triggered during the exponential part of the search and so you will probably do many of them on your way to finding a satisfying assignment.

The net result is that you will waste more time than you will save trying to immediately notice when all clauses are satisfied.

Note that if you're adapting a traditional SAT solver to count solutions, then your idea has more merit.  Noticing that all clauses are satisfied while there are still unassigned variables means you have found $2^n$ solutions to the formula, where $n$ is the number of unassigned variables.  This provides an exponential speedup over finding these solutions one by one, so the lazy clause tracking could potentially pay for itself.  However, an alternative would be to notice a satisfying assignment in the usual way and then undo assignments in reverse order until a clause is left unsatisfied.  You would have the same $2^n$ speedup without the clause tracking overhead.


You can show that it is not the case that every two languages are reducible to each other using a counting argument. Consider the class of all  languages $ 2^{\Sigma^*}$. If by contradiction every two languages are reducible to each other, then every language is an $2^{\Sigma^*}$-hard language (in particular, there is a language that all languages reduce to). One can show that there are more languages than reductions. Thus, an $2^{\Sigma^*}$-hard language
must have two different languages that reduce to it using the same reduction, but this is impossible.
More formally, assume by contradiction that there is an $2^{\Sigma^*}$-hard language $L$. We know that there are $2^{\aleph_0}$ languages, yet, as there are only $\aleph_0$ TMs, there are also only $\aleph_0$ reductions. Then, it follows that there are distinct languages $A$ and $B$ such that
$A \leq_m L$ and $B \leq_m L$, but the reductions from $A$ and $B$ to $L$ coincide. Denote this reduction
by $f$. Since $A\neq B$, there exists w.l.o.g a word $x\in A\setminus B$. Since $f$ is a reduction from $A$ to
$L$, we get that $f(x) ∈ L$. But $f$ is also a reduction from $B$ to $L$, and thus we get that $f(x) \notin L$, and we
reached a contradiction.


Invariant on "Find K Closest Elements" problem

If x - arr[mid] <= arr[mid+k] - x, then for any l that l > mid, we have

x - arr[l-1] <= x - a[mid] <= arr[mid+k] - x <= arr[l+k] - x,
arr[l-1] - x <= arr[l+k] - x,

which means |arr[l-1] - x| <= |arr[l+k] - x|. So for any range [l, l+k] where l > mid, we can move it to left until l == mid while the elements contained are no farther from x, therefore it is safe to set right = mid.

Otherwise, the proof is similar.


Can you get O(n) with a word frequency algorithm?

If the size of the alphabet is constant and $n$ denotes the length of the document (i.e. the total number of characters), you can indeed use Tries to get $O(n)$ running time - regardless of the length of the words.

In a Trie, you can search for (or insert) a word in time linear in the length of the word. You can use a Trie to keep track of the words as you encounter them in the text, and in each Trie node corresponding to a word you can store that word's frequency (which is updated each time you encounter it).

The running time of this algorithm is indeed $O(n)$: the sum of all the lengths of the words in the documents is precisely the length of the document. Note that you can also traverse the Trie (and list the words it contains to generate the desired output) in $O(n)$ (since the number of nodes in the Trie is at most $n$).


Evolutionary algorithm in stochastic environment

I'd go with option 1.

A dynamic training environment is a good way to produce a robust solution (after all natural evolution, which is the inspiration for EA, is always dynamic).

Moreover "take some statistics over the solutions" can be a very hard problem (you shouldn't take for granted that there is a meaningful way to combine / extract information from multiple solutions).

Indeed there are some important aspects to consider:

population diversity have to be carefully monitored. Often EAs are designed for a static optimization problem and the quick loss of diversity can be a problem in a dynamic environment;
it seems that you have a system in which environmental change occurs rapidly. Try to slow down the environment: do not draw a new interaction environment after every mutation but wait for a sequence of mutations (in Genetic Programming this is the approach taken in Dynamic Training Subset Selection{1}). I'm not sure this will work, but it's worth a try;
supply the EA with an explicit memory (sometimes called Valhalla) so that the EA can recall useful information from past generations (e.g {5}).

This is small compendium of interesting papers.

Looking for further resources, consider that there are many kinds of dynamic environments: e.g. noisy fitness functions, environments with optimum changing over time... they are somewhat different problems but share many interesting techniques.

Also it seems to me that you're describing a so called co-adaptive environment (each individual's evolution drives other individuals evolution and individuals change their fitness landscape evermore). You may find interesting techniques in papers about co-evolution.

Dynamic Training Subset Selection for Supervised Learning in Genetic Programming by Chris Gathercole, Peter Ross (1994).
Genetic Algorithm for Adaptation to Dynamic Environments - A survey by Naoki Mori, Hajime Kita (2000).
Evolutionary Dynamic Optimization - A survey of the state of the art by Juergen Branke, Trung Thanh Nguyen, Shengxiang Yang (2012).
An evolutionary approach for time dependant optimization by Philippe Collard, Cathy Escazut, Alessio Gaspar (1997).
"Memory enhanced evolutionary algorithms for changing optimization problems" by Juergen Branke (1999).
Evolutionary Algorithms and Dynamic Optimization Problems by Karsten Weicker (2003).


How to solve the following recurrence? $T(n) = 4T(\frac{n}{2})+n!$

"... the masters theorem would not work with the above equation" is not right. From the master theorem, as we know $n! = \Omega(n^3)$, and $4\left(\frac{n}{2}\right)! < 0.9 n!$ ($k = 0.9$) for large enough $n$, so $T(n) = \Theta(n!)$.

To know more about this case, follow this link and find third case of the master theorem.


Unbounded, 2-dimensional knapsack problem

Just the special case of (in your terms) 1-dimensional knapsack is NP-complete, and that is a special case of your 2-dimensional one (just take a strip of width one to be filled with strips of width one). It is very unlikely that an efficient algorithm exists for your problem.

Similar problems are handled e.g. by newspapers (need to fill pages with rectangles for ads, for instance), when cutting up sheets into custom sizes and similar applications. Search for those, there must be publications on approximation algorithms.


Can you say anything interesting about a language knowing only that it is prefix-closed?

If $P$ and $Q$ are languages closed under prefix, then
$P\cup Q$, $P\cap Q$, $P \cdot Q$, $P/Q$ are also closed under prefix. Also you can think of such a language $L$ as a directed tree. Define the graph/tree $G = (V,E)$ where $V = L$ and
$$E = \{(\mathit{prefix}(w),w) \mid w\in L \}$$
(the words are the nodes and the parent of every word is its prefix).
Note that I assume that $\mathit{prefix}(x) = \varepsilon$ for all $x\in\Sigma$, meaning that the prefix of a single symbol is the empty word. Thus the root of the tree constructed above is the empty word. The constructed tree can be easily transformed to a DFA recognizing the language (I think you can see how).


Where can I find good study material on Role Mining?

The paper The Role Mining Problem: Finding a Minimal Descriptive
Set of Roles by Jaideep Vaidya, Vijayalakshmi Atluri and Qi Guo covers the basic definitions and some variants and includes a mapping to the minimum tiling problem. This is explored in more detail in the third author's PhD thesis (found by Googling "A formal approach to the role mining problem.)

An alternative formal definition of the Role Mining problem is found in the paper On the Deﬁnition of Role Mining by
Mario Frank, Joachim M. Buhmann, and David Basin. This is another good starting point;  it also contains references to much of the earlier work.

These tutorial slides cover many of the topics you mention. They also contain a load of references for you to follow up. The author of these slides has a small page describing the basics of role mining.

Optimal Boolean Matrix Decomposition: Application to Role Engineering by Haibing Lu, Jaideep Vaidya and Vijayalakshmi Atluri covers basic RMP along with min-noise RMP, $\delta$-approximate RMP and edge-RMP using boolean matrix decomposition as the basic formalism.


One way this can be performed in a single cycle is through register renaming.  If the processor supports register renaming, no data needs to be moved: one simply renames which register is called R1 and which one is called R2.

If the processor doesn't support register renaming, the other option is that the data can simply be swapped between the two registers.


DFA for the set of strings of 0’s and 1’s such that there are two 0’s separated by a number of positions that is a multiple of 4

Your interpretation is correct. It looks to me like the "solution" is wrong (and the solution isn't strictly a DFA).

Assuming you don't mind an NFA (getting a DFA is a bit fiddly, but obviously doable), you can fix the solution by removing the $(q_{4},0) \rightarrow q_{5}$ transition, and adding $(q_{5}, 0) \rightarrow q_{5}$ and $(q_{5}, 1) \rightarrow q_{5}$ transitions.

After some fiddling, it seems like a minimal DFA for this has 23 states... not so much fun.


Proving equality between foldl recursive and iterative fold

The two definitions are not equal. Consider $h$ defined by
\begin{align*}
h(c, a) = 10 \cdot c + a
\end{align*}
and $c = 0$. Then
$$\mathsf{foldl} \, (c,h) \, [1,2,3] = 321$$
but
$$\mathsf{fold}_{itr} \, (c,h) \, [1,2,3] = 123.$$


To prove that the algorithm is correct, we assume that the loop invariant  $x_n + by_n = a$  is true per induction.

we have the following two cases:

case 1:

If MUL(a,b) returns true, then $x_n = 0$ and $y_n = n$,

so

$x_n + by_n =a \rightarrow bn = a \rightarrow a$ is a multiplum of b

case 2:

if MUL(a,b) returns false, then $x_n \not= 0$, so we have

$x_n + by_n = a \rightarrow bn \not= a \rightarrow a$ is not a divisor of b.


How to determine if a black-box is polynomial or exponential

Theoretically speaking, this is impossible to accomplish, basically because "polynomial" and "exponential" are asymptotic concepts, and no prefix of the data guarantees anything about the behavior at infinity.

Practically speaking, you can try to compute $t(n)^{1/n}$ and so if it approaches a constant bounded away from 1. If so, it is exponential. To test whether it's polynomial, you see whether $\log t/\log n$ approaches a constant. These are only rough tests, of course, but they could be useful in practice.


Question regarding Hoare's partitioning scheme and a slight modification to it

Why not use while a[i] <= pivot ?

You could.  It's arbitrary.  Either way will work fine.  We just have to choose one of those two choices.  They both have the same asymptotic running time.


Unable to understand a definition of an instruction in a compiler schedule

I lent my copy of Cooper and Torczon to someone and never got it back, so I can't look up the context.  (It's a good book in general (which is why I didn't get it back)).

The definition of instruction here is unusual.  It corresponds more closely to what you might expect in a Very Long Instruction Word (VLIW) computer or in horizontal microcode.

In a VLIW machine, each instruction is made up of a small fixed number of independent operations.  A typical example would be something like: at most one branch instruction, at most two memory operations, and at most two arithmetic operations.  So you'd expect each instruction to be made up of five operations (some of which might be "no-ops").  So there are going to be two constraints here, and the definition of instruction given by Cooper and Torczon has not yet taken into account those constraints.  (I suspect that they will start discussing the constraints in the pages just after page 645).

To be more specific: a VLIW instruction is a set of operations that can be executed simultaneously/concurrently.  The operations must be (1) independent of each other and (2) the hardware must have sufficient function units to execute all the operations in the set simultaneously.

Cooper and Torczon are probably about to introduce some list scheduling heuristics.  In list scheduling you assign a non-negative integer to each operation such that (1) the dependence dag $D$ is "satisfied" (for all directed edges $x \rightarrow y$, $S(x) \lt S(y)$).  And (2) the set of operations scheduled on each cycle is feasible given the available hardware.  For example, in a greedy list scheduling heuristic you would traverse the dependence DAG in some topological order placing each instruction at the earliest cycle which satisfies both conditions.


Testing the property of being a union of three disjoint cliques

I will explain how to solve a similar question:

  Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of two disjoint cliques.

I assume that a clique is also considered a union of two disjoint cliques (one of them empty).

The natural test to try is

  Sample three vertices $x,y,z$, and check that the graph $G[x,y,z]$ induced by $x,y,z$ is either a triangle or an edge.

If a graph is a union of two disjoint cliques, then this test always passes. Conversely, suppose that this test always passes. Fix some vertex $x$, and let $V_1$ be the set of vertices connected to $x$, $V_2$ be the set of vertices not connected to $x$. If $y,z \in V_1$ then $G[x,y,z]$ includes the edges $(x,y),(x,z)$, and so must be a triangle, that is, $(y,z) \in E$. If $y,z \in V_2$ then $G[x,y,z]$ doesn't contain the edges $(x,y),(x,z)$, and so must be the edge $(y,z) \in E$. Finally, if $y \in V_1$ and $z \in V_2$ then $G[x,y,z]$ contains $(x,y)$ but not $(x,z)$. It must be an edge, so that $(y,z) \notin E$. We conclude that $G$ is indeed a union of two disjoint cliques.

Now suppose that the test passes with probability $1-\epsilon$. In particular, there must be a vertex $x_0$ such that conditioned on $x = x_0$, the test passes with probability at least $1-\epsilon$ (why?). Define $V_1,V_2$ as before. The argument above shows that $H$, the union of the cliques on $V_1$ and on $V_2$, is $\epsilon$-close to $G$ (in fact, slightly closer). Indeed, for every pair of vertices $y,z \neq x_0$, the test passes on $x_0,y,z$ if and only if the edge $(y,z)$ exists on both or neither $G$ and $H$. Thus $G$ and $H$ agree on all edges involving $x$, and agree on a $1-\epsilon$ fraction of the rest of the edges.

What about the actual question? Again, the natural test to try is

  Sample four vertices $x,y,z,w$, and check that the graph $G[x,y,z,w]$ induced by $x,y,z,w$ is a union of three disjoint cliques.

This time the analysis is slightly more complicated. Suppose that the test passes with probability $1 - \epsilon$. We consider two cases.

Case 1. $G$ contains at least a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, $G$ is $\sqrt{\epsilon}$-close to a clique.

Case 2. $G$ contains at most a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, we can find two unconnected vertices $x_0,y_0$ such that conditioned on $x=x_0,y=y_0$, the test passes with probability at least $1-\sqrt{\epsilon}$. We can now define $V_1,V_2,V_3$ analogously to how we defined $V_1,V_2$ in the preceding case, and show that $G$ is $\sqrt{\epsilon}$-close to the union of the cliques on $V_1,V_2,V_3$. Details left to the reader.


Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

Here is a solution in time $O((Q+n)\log^2 n)$ and space $O(n\log n)$. For simplicity, assume that $n$ is a power of $2$, and that the array is zero-based.

A dyadic interval is an interval of the form $[c \cdot 2^k,(c+1) \cdot 2^k)$ (that is, $c\cdot 2^k,\ldots,(c+1)\cdot 2^k-1$). For example, when $n = 8$ we have the following dyadic intervals:
$$
[0,8),[0,4),[4,8),[0,2),[2,4),[4,6),[6,8), \\
[0,1),[1,2),[2,3),[3,4),[4,5),[5,6),[6,7),[7,8).
$$
Each interval of the form $[0,x)$ is the disjoint union of at most $\log_2 n$ slices. For example, for $n = 8$ we have (for $x \neq 1,2,4,8$):
$$
[0,3) = [0,2) \cup [2,3),  \\
[0,5) = [0,4) \cup [4,5), \\
[0,6) = [0,4) \cup [4,6), \\
[0,7) = [0,4) \cup [4,6) \cup [6,7).
$$

A dyadic slice of the array $a$ consists of the elements $a[s],\ldots,a[t]$ for some dyadic interval $s,\ldots,t$.

As preprocessing, we sort (separately) each dyadic slice of $a$. This takes time $O(n\log^2 n)$ and consumes space $O(n\log n)$ (since each index participates in $\log_2 n$ slices).

As mentioned in the question, it is enough to handle the following type of query:

  Given $i,R$, count the number of indices $j <R$ such that $a[j] \leq a[i]$.

Given $i,R$, we retrieve $a[i]$, and present $[0,R)$ as a union of $O(\log n)$ dyadic intervals $I_1,\ldots,I_m$. Using binary search, for each $k$ we determine the number of indices $j \in I_k$ such that $a[j] \leq a[i]$. This takes time $O(\log^2 n)$ (altogether). Summing these numbers, we arrive at the answer to the query.


Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, that is to say when the size of the training data is to small in comparison with the model complexity.

Examples:

if your data is in two dimensions, you have 10000 points in the training set and the model is a line, you are likely to under-fit.
if your data is in two dimensions, you have 10 points in the training set and the model is 100-degree polynomial, you are likely to over-fit.

From a theoretical standpoint, the amount of data you need to properly train your model is a crucial yet far-to-be-answered question in machine learning. One such approach to answer this question is the VC dimension. Another is the bias-variance tradeoff.

From an empirical standpoint, people typically plot the training error and the test error on the same plot and make sure that they don't reduce the training error at the expense of the test error:

I would advise to watch Coursera' Machine Learning course, section "10: Advice for applying Machine Learning".


Max-Flow: Detect if a given edge is found in some Min-Cut

Here is a solution for the first question: Suppose $w(e)$ is the weight of $e$, calculate min-cut value for $G$, suppose is $C$. Then we remove $e$ from $G$ to make $G'$; again we calculate the min-cut value for $G'$, suppose is $C'$, if $C-C'\ge w(e)$, then this concludes that $e$, participating in at least one min-cut (that you already know it), otherwise $e$ does not belong to any min-cut.

Link to SO answer.


I don't know what is the proper name for what you're seeing, but it is the standard way to lexically analyze text. You divide it into tokens of specific types. For the sake of context-free parsing (the next step in the parsing chain), you only need the type of each lexeme; but further steps down the road will need to know the semantic content (sometimes called annotation) of each lexeme. For example, the context-free parser doesn't care which number $2$ is; it only needs to know that it's a number. Further down the road, it will suffice to know that this number is an integer. Even further, you would need to know that this integer is specifically $2$.

Some lexemes are atomic, for example the various operators (though in principle we could group, say, + and - together). We need to separate them because syntactically = is different from +, and + is different from * (due to operator precedence). These don't need any annotation.


Access control matrices: who are the subjects: users or processes?

Short answer: both.

My answer is based on knowledge of Unix, but as far as I know the same principle applies to Multics and Windows.

Runtime permission checks are performed by the kernel in system calls (such as the call to open a file). They are based on a matrix where the subjects are processes — the kernel determines the content of the cell for the calling process and for the object under concern (e.g. the file whose opening is requested).

The row for each process in that matrix is computed from data that is stored in a kernel data structure for that process. It is inherited from parent process to child process, all the way from login time. At login time, this data is initialized from the user database; it includes the information of which user the process is running as.

A file's access control list is stored on disk (if the file is a disk file). It could not reference processes: these have a too short lifetime — on a reboot, not information about processes would be meaningful. In access control lists stored on the filesystem, the subjects are users (and groups).

You can draw a cube, but that cube doesn't correspond to anything tangible in the operating system design. The user/object matrix corresponds to file ACLs, and the process/object matrix corresponds to runtime checks in the kernel.


Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

There is a simple proof using automata. Suppose the original language is $L$, and we are substituting $R_a$ for $a$ (for each $a \in \Sigma$). Starting with an automaton for $L$, replace each edge $(x,y)$ annotated $a$ with a copy of an automaton $A_a$ for $R_a$, connecting $x$ to the starting state of $A_a$ with an $\epsilon$-edge, and connecting each accepting state of $A_a$ (which is not accepting any more in the new automaton) to $y$ with an $\epsilon$-edge.


How to convert a non-embedding context free grammar to regular grammar?

Check out this link.
This is a simpler version of a proof by Chomsky that NSE grammars represent regular languages. Fortunately, the proof technique illustrates how to construct a left-regular grammar from a given NSE grammar. Here's my explanation:

For each of the $\lvert V \rvert (\lvert V \rvert +1)/2$ pairs $(v_1, v_2)$ of elements of $V$, decide whether $v_1 \le v_2$ based on the definition given: $v_1 \le v_2$ if $v_2 *:= V^* v_1 V^*$.
Construct equivalence classes such that if $v_1 \le v_2$ and $v_2 \le v_1$, $v_1$ and $v_2$ are in the same equivalence class. This will be a partition of all elements of $V$ into one or more equivalence classes.
Now, for each pair $(VE_1, VE_2)$ of equivalence classes of $V$ as described above, determine whether $VE_1 \le VE_2$ by checking whether $v_1$ in $VE_1 \le v_2$ in $VE_2$.
Construct sets $UE$ corresponding to equivalence classes $VE$ such that if $VE_i \le VE_k$, $VE_i$ is a subset of $UE_k$. Each $UE_k$ must also contain the alphabet set $E$. You will have one $UE$ for each $VE$, and each $UE$ will contain variables in equivalence classes "less than" the corresponding $VE$, in addition to all the alphabet symbols.
Determine $P(v)$ for each variable $v$ as follows: $P(v)$ is the set of all productions in $P$ whose left-hand-sides belong to the equivalence class containing variable $v$.
For each variable $v$, construct a grammar as follows: $G(v) = (VE \cup UE, UE, P(v), v)$, where $VE$ is the equivalence class containing $v$ and the $UE$ is the one corresponding to the $VE$.
The authors have proven a lemma which claims that $G(v)$ is a linear grammar. From this, we can write regular expressions over $UE$ for each variable $v$. Note that for the $UE$ corresponding to the "smallest" $VE$, this regular expression will contain only symbols from the original alphabet $E$.
Iteratively substitute regular expressions containing only alphabet symbols into more complicated regular expressions obtained from step 7. Eventually, you will have a regular expression corresponding to the language generated from the original start symbol $S$, and this regular expression will contain only alphabet symbols from the original alphabet.
You now have a regular expression for the NSE grammar, and can obtain a minimal DFA using Kleene's theorem, the subset construction, and a DFA minimization algorithm.

If you would like an example, I can try to provide one later. Try to do a few yourself, read the paper (it's short), and we can talk about complexity later on.


Is there a variant of Dijkstra’s algorithm for partial recalculation?

Yes. A search algorithm that is able to quickly recompute the fastest path when small changes are made is known as an incremental algorithm.  For your case specifically, you'll want to use D*-Lite, the algorithm used by the Mars Rovers.

See here for more information.

(Note: D*-Lite is decently complex.  If this is for a video game, there are better ways to obtain speed-ups using off-the-shelf A* implementations)


Algorithm for optimal rule-based arrangements?

As @Steven wrote, this problem is NP-hard. However that doesn't mean that you can't solve the problem for small instances.

You can solve such a problem by simply iterating over all $n!$ different permutations, and checking each if any of the arrangements is allowed and how good it is. This has complexity $O(n \cdot n!)$.

Much faster (but still exponential complexity) will be a variation to the Bellman–Held–Karp algorithm. Compute for each pair $(V, v)$ with $V$ being a subset of all vegetables and and $v \in V$, if it is possible to arrange the vegetables $V$ in a way such that $v$ is the last one and what it's best value is. You can define a recursive formula for this function, and apply dynamic programming, like in the BHK algorithm. That should run in $O(n^2 \cdot 2^n)$.


P, Q, ((P→Q)→R) ⊢ R using only modus ponens

Given $P$, $Q$ and $(P \to Q) \to R$, there is no way to apply modus ponens. You would need to have $(P \to Q)$. If you had $P$, $Q$ and $P \to (Q \to R)$, then you could apply modus ponens twice the way you did, but $P \to (Q \to R)$ and $(P \to Q) \to R$ are different.

$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.

It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).

There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.


Are there any existing problems that wouldn't be solvable with a halting oracle?

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th computably enumerable set):

$\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ is $\Sigma^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ is $\Pi^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ is $\Sigma^0_3$-complete.

None of these can be solved even if you have a Halting Oracle. For instance, consider the second example, "is $\varphi_n$ total?" Given $n$ how would the Halting Oracle help us decide whether the Turing machine encoded by $n$ halts on every input?

[Added 2014-06-03] For a "practical" aspect of all of this, consider the problem: a programmer has written a function void charge_credit_card(int card_number, int amount) and we would like to know whether the function terminates on all inputs. It is impossible to write a compiler which can automatically check this in general. Moreover, even if we allow the compiler to ask us questions of the form "does charge_credit_card terminate when given input (k,m)?", it is still impossible.


Data structure/aglorithm for strings to see if there exists two strings you can concatenate to get a target?

Store the strings in a trie.  Build a second trie that stores the reverse of the strings.  Now you can quickly check whether the target string T is a concatenation of some pair of strings: start walking the first trie, using the left-most characters of T (walking left to right), and simultaneously start walking the second trie, using the right-most characters of T (walking right to left).  By walking the first trie, you find all prefixes of T that are in the dataset; by walking the second trie, you find all suffices of T that are in the dataset; and then you can look for a pair of a prefix and a suffix of the right length to cover all of T (without overlap).

Your approach of storing the strings in sorted order is also reasonable, but you'll need two sorted arrays: one to store the strings; another to store the reverse of the strings.  Given a target string T of length n, for each i, you look up T[1..i] in the first sorted array (using binary search) and look up reverse(T[i+1..n]) in the second sorted array (using binary search).  As an optimization, start each binary search from where the previous search left off (i.e., once you've found T[1..i] in the first sorted array, that helps you find T[1..i+1]; you shouldn't need to start over from scratch.)

So yeah, your idea based on sorted arrays works too, though two tries might be somewhat more efficient.


Is DFA and Regular Expression equivalent?

According to Wikipedia:

Given a finite alphabet $\Sigma$, the following constants are defined as regular expressions:

(empty set) $\emptyset$ denoting the set $\emptyset$.

...

... a string that contains only an empty-set symbol is a regular expression, which represents the empty language.


After reading further, I found the answer. The answer is that the $x$ given in the question is not in $\mathbb{R}(5, 3)$. The way I figured this out is as follows:

On the next page, the author states that
$$\min_{x \in \mathbb{R}(t, s)} |x| = 2^{-2^s}$$
This is consistent with $(.100 \cdots 0) \cdot2^{-(11\cdots 1)}$ being the least positive number in $\mathbb{R}(t, s)$, and not $(.000 \cdots 01) \cdot2^{-(11\cdots 1)}.$


What is the best algorithm to match a student's schedule with a tutor's schedule?

This sounds like an instance of the assignment problem (see also our tag).  You can also view it as a bipartite matching problem.  There are standard algorithms for these problems; I suggest you use one of them.  Hopcroft-Karp is one of those standard algorithms.  I suggest that you either look for an existing implementation of one of those algorithms, or study them and implement themselves.

Expressing this as a network flow algorithm or as an instance of linear programming might provide extra flexibility to deal with additional constraints.

The specifics of how to express your problem as an instance of these problems will depend on the specific constraints you want to impose (e.g., is there a limit on the number of students you want to assign each tutor to?  is it ok to limit things to a set of non-overlapping 90-minute time slots?), which you haven't specified in the question, so it's hard for us to say much more.

I suggest you try applying one of those approaches to your specific problem, study one of the standard algorithms, and if you get stuck understanding some specific aspect of the problem, ask a new question where you ask about that specific difficulty.


How prefix property of language affects the PDA

The root of your problem is in the second statement:

  Language accepted by both of these modes in PDA (NPDA) are equal.

I'm not sure what you mean by that. You might mean the following false statement:

  The language accepted by a PDA using the empty state acceptance condition is the same as the language accepted by the same PDA using the final state acceptance condition.

The true statement is the following:

  If a language is accepted by some PDA using the empty stack acceptance condition, then it is accepted by a different PDA using the final state acceptance condition; and vice versa.

This involves two conversions: from an "empty stack" PDA to a "final state" PDA, and vice versa. The first conversion preserves determinism, the second doesn't. In other words, if we apply the first conversion to an "empty stack" DPDA, then we get a "final state" DPDA. But if we apply the second conversion to a "final state" DPDA, we get an "empty stack" NPDA which is in general not deterministic.

The same statement can be stated differently:

  The set of languages accepted by "empty stack" PDAs is the same as the set of languages accepted by "final state" PDAs.

The same doesn't hold for DPDAs, though it is true that the set of languages accepted by "empty stack" DPDAs is a subset of the set of languages accepted by "final state" PDAs.


What is the language feature which allows a variable to be associated with values of different types?

Allow me to address the misconceptions in your question one by one.

In Python, I can change the types of values associated with a variable:
>>> x=1
>>> x="abc"

In type theory, types classify expressions, i.e., syntactic objects, i.e., program fragments. From this point of view, Python has exactly one type. Confusingly, what Python calls “types” are what type theory calls classes of a single type.

I was wondering if the following language features have to do with the observation in Python:

no explicit type annotations,instead of explicit type annotations

Annotations have nothing to do with this. There exist languages, such as ML and Haskell, that allow the programmer to omit most type annotations, yet the type of a variable binding is never allowed to change throughout its scope.
This is not to say that it is impossible to design a programming language in which the type of a variable could change within its scope, but Python is by no means such a language.

dynamic typing, instead of static typing

What I said above about the meaning of “type” in type theory.

or reference model of variable, instead of value model of variables?

There is no such thing as “reference model of variable”. A variable always stands for a value. It just so happens that Python has no values other than object references. For example, the Python expression 2 << 1000 does not evaluate to the number $2^{1000}$. It evaluates to an object that represents the number $2^{1000}$. There can be two different objects that represent the same number, as this snippet illustrates:
>>> x = 2 << 1000
>>> y = 2 << 1000
>>> x is y
False

Of course, in mathematics, it makes no sense whatsoever to distinguish between “this $2^{1000}$” and “that $2^{1000}$”. Since Python's ints do not behave like mathematical integers, Python simply does not have integer values.
Confusingly enough, against established tradition, Python's equality testing operator is called is rather than ==.


How to compare two approximation algorithms

I would write something like this: whereas Alg 1 is a $\log(N)$-approximation algorithms, there are instances on which the approximation ratio of Alg 2 is only $N/2$. So Alg 1 is much better (in the worst case) than Alg 2.


What TSP variant doesn't return to start point?

You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.)

Edit: it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add two dummy cities $v$ and $w$ such that:

$v$ is only connected to the starting point and to $w$,
$w$ is connected to everything.


Example of a language that is neither recognizable nor co-recognizable?

The language TOT of all Turing machines halting on all inputs is $\Pi_2$-complete, and so is neither recognizable nor co-recognizable. You can find more examples if you search for material on the arithmetical hierarchy. Anything beyond $\Sigma_1$ and $\Pi_1$ will fit your bill.


Could all CPU instructions get fundamentally faster if a better multiplication method was developed

I don't see the relevance.

New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with numbers with thousands or even millions of bits. For an extreme example, Fürer's algorithm, which runs in time $O(n\log n\, 2^{O(\log^*n)})$ will only become competitive with Schönhage and Strassen's $O(n\log n\log\log n)$ algorithm for $n>2^{64}$ bits and, let's be honest, whatever it is that you're multiplying, it doesn't have $2^{64}$ bits. In contrast, CPUs operate on fixed-length words with a few tens of bits.
Most of what a CPU does isn't multiplying numbers, anyway.
Also, note that Harvey and van der Hoeven "make no attempt to... exhibit a practical multiplication algorithm" (page 2 of their preprint).