Proving $\log (N)$ mistake bound is "tight" for a learner when learning thresholds

I am assuming the learning model described in Wikipedia. The environment will maintain a set of hypothesis forming an interval $S = [h_\alpha,h_\beta]$ consistent with its current answers, and will ensure that the first $\log N$ answers by the algorithm are wrong. In the beginning, $S = H$. At each step, the environment presents the middle point of the interval (we're identifying hypotheses with points in the domain in a natural way). Depending on the learner's answer, the interval $S$ is halved so that the learner is wrong. This process can go on for $\log N$ steps, in each of which the learner is mistaken, so that in total the learner makes at least $\log N$ mistakes.


Algorithm for automatic/optimal database joins?

This is the minimum Steiner tree problem for general graphs.  It is known to be NP-hard.  Here you have the special case where every edge has weight 1, but that special case is still NP-hard.

However, there are approximation algorithms, which you could use to get somewhat close to the optimum.  Alternatively, if you want the exact optimal solution and your graph is not too large, you could express your problem as an instance of integer linear programming (ILP) and try using an off-the-shelf ILP solver, though the worst-case running time will still be exponential.


What are practical applications of AI Planning?

[In the following, I am providing links to some events in 2011/2013, but you can find much more looking for previous years]

By AI Planning I assume that you mean Automated Planning (STRIPS, SAS$^+$ and so on) instead of path-planning and other problems more tightly related to robot navigation. If this is the case, SPARK is the right forum to look at.

Other practical applications are often discussed at the main track of the conference ICAPS. A couple of examples:

Maria Fox, Derek Long, Daniele Magazzeni: Automatic Construction of Efficient Multiple Battery Usage Policies. ICAPS 2011
José E. Flórez, Álvaro Torralba Arias de Reyna, Javier García, Carlos Linares López, Angel García Olaya, Daniel Borrajo: Planning Multi-Modal Transportation Problems. ICAPS 2011 (admittedly, I am adding here a reference of my own, beg your pardon, I did just because it was easier for me to locate the reference).

Hope this helps,


What is the basic idea behind the usage of TLBs?

A TLB is useful for the same reason any other cache is useful: because it's very common to access the same data multiple times in quick succession. Many algorithms use the same value more than once. For example, searching requires accessing the search pattern a lot of times. Sorting a list requires comparing the same element multiple times for any (comparison-based) algorithm.

The nature of the TLB amplifies this effect because it doesn't only kick in when accessing the same data, but more generally when accessing data in the same page. This happens even when each individual bit is only accessed once. For example, consider a simple array traversal, that accesses the array elements in order. Assume that elements are smaller than one page, say $k$ elements fit in a page. Then a single MMU lookup is needed for the first element in a page, and the next $k-1$ only require a TLB lookup.


This problem is called the Minimum Linear Arrangement of a Directed Graph and it is indeed NP-hard.

See the reduction from the MLA to MLAD on page 11 of this (old) technical report: S. Even and Y. Shiloah, NP-completeness of several arrangement problems, Technical Report no. 43 of the Department of Computer Science, Israel Institute of Technology (Technion), 1975 (PDF).


Relation between CLR Grammar and Ambiguity

A grammar may be may unambiguous, but not parsable by a LR(k) parser.
It is actually possible that a language has an unambiguous grammar,
but cannot be parsed deterministically by any PDA, hence has no LR(k)
parser.

For example the language $\{a^nb^n\mid n>0\}\cup\{a^nb^{2n}\mid n>0\}$.
It is clearly unambiguous (it is easy to write an unambiguous grammar for it). But, informally, there is just no way you
can decide which way you want to parse before you have read all the
$a$ and as many $b$.

An ambiguous grammar may define a language that has another grammar
that is not ambiguous, and may even be CLR(1) or LR(0). Actually, you
can just take an LR(0) grammar and add a few useless rule to make it
ambiguous without changing the language.

However, there are context-free languages that are inherently
ambiguous, i.e. that can only be defined by an ambiguous grammar.
And of course, there is no way an inherently ambiguous language can be
parsed deterministically.


LP formulation and integer solution existance

I don't know why you added this in your second constraint:

  ..., and which is a maximal set with that property, ...

I would model it simply as: "For every two agents $x_i$ and $x_j$, if their sets $S_i$ and $S_j$ intersect, then $x_i + x_j \leq 1$"
$$
x_i + x_j \leq 1 \quad \forall (i,j): i \lt j \text{ and } S_i \cap S_j \neq \emptyset$$

Notice that every row in the constraint matrix has exactly two ones, and we can think of it as a bipartite graph, which is TUM.

This matrix is not TUM, and there is no guarantee that it will provide Integer Solutions, as we can see in the counter-example:
$$ S_1 \cap S_2 \neq \emptyset, S_1 \cap S_3 \neq \emptyset, S_2 \cap S_3 \neq \emptyset $$
\begin{bmatrix}
1 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 1\\
\end{bmatrix}

That doesn't mean that your problem does not have an integer optimal solution, simply that this Linear Formulation will not always yield an integer solution. For example, the solution of your LP might be $x_1 = 0.23848$, which satisfies all the constraints and is the optimal solution, but it is not integer.

If your goal is to solve this problem, and get the Integer Optimal Solution, you can use an Integer Linear Formulation and use any ILP solver to get to that solution.

The Integer Linear Formulation allows constraints like $ x_1 \in \{0, 1\}$, that will ensure that this variable will be either 0 or 1.

The purpose of proving that it is TUM, is to avoid using Integer Linear Formulations, since they are slower to solve than Linear Programs.


Reduction from Vertex Cover to Polygon Cover

Let $(G,k)$ be an instance of Dominating Set where $G$ is drawn on the plane with any drawing.  Construct for each vertex $v$ a polygon $S_v$ which covers all of $N[v]$ and no other vertices, where $N[v]$ is the set containing $v$ and all its neighbors.  Let $S = \bigcup_{v \in V(G)} S_v$ and the points $P$ be the points where the vertices are drawn.  The instance for Polygon Cover is $P, S, k$.  This reduction is a Karp-reduction from Dominating Set which is NP-complete, and hence Polygon Cover is NP-complete as well.

To formally prove that the above reduction works, you need to prove that selecting a set of $k$ polygons $S' \subseteq S$ which covers all the points corresponds to picking a set of vertices whose neighborhoods contain all the vertices of the graph.

If you want to prove it for convex polygons, you can use the fact that Dominating Set is NP-complete on planar graphs and that planar graphs are equivalent to kissing graphs.


Prove that A is non-regular using K-Complexity Non regularity theorem

Suppose that $A$ is regular. Then there exists a constant $c$ such that for all $x \in \Sigma^*$ and for all $n$ such that $Y^A_{x,n}$ exists, $C(Y^A_{x,n}) \leq \log n + c$.

Let us take $x = 0^{2m}1$. Then $Y^A_{x,n}$ exists as long as $n \leq 2^m$ – in fact, $Y^A_{x,n}$ is just the $n$th binary string of length $m$. Therefore
$$
C(\text{$n$th binary string of length $m$}) \leq \log n + c.
$$
In particular, choosing $n=1$, we get
$$
C(0^m) \leq c.
$$
Clearly this fails for large enough $m$. This contradiction shows that $A$ is not regular.


Break and Continue in Structured Programming?

That of course depends on how exactly we define structured programming. We can look to the research papers that coined the phrase, such as the 1966 Structured Programming Theorem. Structured programming, as defined in these papers, would not permit partial execution of a loop body, and therefore neither a break, continue, return or throw statement (nor any exceptions thrown by the JVM).

All of these language features were invented after structured programming, and to address perceived deficiencies of structured programming (in its original definition). Whether these amendments comply with the spirit of structured programming (or equivalently, whether a modern definition of structured programming should encompass these features) has been the topic of some debate, see for instance the 1995 paper Loop Exits and Structured Programming: Reopening the Debate.

Personally, I find applying this 1966 programming technique, ground breaking as it was at the time, verbatim to a modern programming language such as Java an undertaking of very questionable benefit, not the least because structured programming (in its original definition) does not permit exceptions, but exceptions are an integral part of the Java language.


Minimum spanning tree of a connected induced subgraph

Suppose that $G$ is the triangle on $\{1,2,3\}$ (with arbitrary edge weights), that $T$ is $\{\{1,2\},\{1,3\}\}$ (without loss of generality), and consider $H = \{\{2,3\}\}$, which is induced by $S = \{2,3\}$. No edges of $T$ lie in $H$, and in particular these edges do not constitute a spanning tree of $H$.


I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique).

For the number of maximal cliques, take the complement of a disjoint union of triangles.  Since the number of maximal independent sets is exactly the same (in the complement), you can count the number of maximal independent set in a graph that is a disjoint union of triangles.  This number is $3^{n/3}$ (Moon and Moser, 1965).

See also: The number of cliques in a graph: the Moon and Moser 1965 result.


Ensure groups of four 3-tuples have 9 unique numbers

I suspect finding the optimal assignment will be NP-hard in theory and possibly hard in practice, but it might be possible to find a near-optimal solution.

One approach is to express this as an instance of integer linear programming, and use an off-the-shelf ILP solver.  Let $x_{i,j}$ be a zero-or-one integer variable, with the intended meaning that $x_{i,j}=1$ implies the $i$th tuple is assigned to the $j$th bin, and $y_{j,d}$ another zero-or-one variable, with the intended meaning that $y_{j,d}=1$ means that digit $d$ is covered in bin $j$.  Then you can write down a set of linear inequalities on the $x$'s and $y$'s that captures what constitutes a consistent and valid solution.

For instance, the constraints might be: $\sum_j x_{i,j} = 1$ (each tuple is assigned to one bin), $\sum_i x_{i,j}=4$ (each bin receives 4 tuples), $y_{j,d} \ge x_{i,j}$ if the $i$th tuple contains digit $d$, and $y_{j,d} \le \sum_i x_{i,j}$ where the sum is over all tuples $i$ that contain digit $d$.  Now you want to maximize the linear objective function $\sum_{j,d} y_{j,d}$.  Then, you could use an off-the-shelf ILP solver to try to find an optimal solution to this linear program, or ask it to report the best solution it can find within a given time bound.

I don't know if there is a better approach.  You could look at algorithms for exact cover to see if any of them can be adapted to your setting.


How to find a cut in a graph with additional constraints?

The problem can be solved in polynomial time.  Here is one algorithm:

For each $s \in C$ and each $t \in V \setminus C$ such that $s \neq t$:

Find the minimum-cost $(s,t)$-cut.   By the max-flow min-cut theorem, this can be done in polynomial time using any maximum flow algorithm.

If the cost of this cut is < 2, output it and halt.

For each $s_0 \in C$ and each $s_1 \in V \setminus C$ and each $t \in V \setminus \{s_0,s_1\}$:

Find the minimum-cost cut that contains both $s_0$ and $s_1$ in the left part and $t$ in the right part.  This can be done in polynomial time by modifying the graph to merge the two vertices $s_0,s_1$ into a new vertex $s'$, then finding a minimum $(s',t)$-cut in the modified graph.

If the cost of this cut is < 2, output it (replacing $s'$ with $s_0,s_1$) and halt.

If you reach this point without halting, output that no such cut exists.

There may be more efficient algorithms by modifying algorithms for min-cut instead of min $(s,t)$-cut.  I don't know.  However, this suffices to show that the problem can be solved in polynomial time.

Proof of correctness: Suppose a cut $(S,V \setminus S)$ of the desired form exists.  Then there are only two ways we can have $S \ne C$:

Case 1: $C \setminus S \ne \emptyset$: In this case, pick any vertex in $C \cap S$ and call it $s^*$ (this can be done since $C \cap S \ne \emptyset$) and pick any vertex in $C \setminus S$ and call it $t^*$ (this can be done since $C \setminus S \ne \emptyset$).  Consider the minimum-cost $(s^*,t^*)$-cut, $(S^*,T^*)$.  By construction, $S^*$ has at least one element of $C$ (since $s^* \in S^*$) and $S^* \ne C$ (since $t^* \notin S^*$) and $\delta(S^*) \le \delta(S) < 2$, so $(S^*,T^*)$ is a valid solution to your problem.  Moreover, it will be found by one of the iterations of the first for-loop, namely, when $s=s^*$ and $t=t^*$, so the algorithm will correctly find a solution.

Case 2: $S \setminus C \ne \emptyset$: In this case pick any vertex in $S \setminus C$ and call it $s^*_1$ (this can be done since $S \setminus C \ne \emptyset$), pick any vertex in $S \cap C$ and call it $s^*_0$ (this can be done since $S \cap C \ne \emptyset$), and pick any vertex in $V \setminus S$ and call it $t^*$ (this can be done since $S \ne V$).  Consider the minimum-cost cut $(S^*,T^*)$ such that $s^*_0 \in S^*$, $s^*_1 \in S^*$, and $t^* \in T^*$.  By construction, $S^*$ has at least one element of $C$ (since $s^*_0 \in S^*$) and $S^* \ne C$ (since $s^*_1 \in S^*$) and $\delta(S^*) \le \delta(S) < 2$, so $(S^*,T^*)$ is a valid solution to your problem.  Moreover, it will be found by one of the iterations of the second for-loop, namely, when $s_0=s^*_0$ and $s_1=s^*_1$ and $t=t^*$, so the algorithm will correctly find a solution.

We see that in either case, if a solution exists, the algorithm will successfully output a valid solution; and those are the only two cases that can occur if a solution exists.
Conversely, if no valid solution exists, it is easy to see that the algorithm will correctly output that no cut exists.


No, that's not a valid argument.  You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.


Are there any exponential-time iterative algorithms?

Yes. Given an input of length $n$, overwrite it and use the space to count to $2^n$ in binary.

Once you've done that, you could write out $2^n$ zeroes and then count to $2^{2^n}$ and so on, ad infinitum.


Computing farthest pair of points in d dimensions

For the case $d = 3$, there exist $O(n\log n)$ algorithms due to Clarkson and Shor (randomized) and Ramos (deterministic). For higher dimensions there seem to exist only approximation algorithms, see for example a presentation of Vigneron. You can use the Johnson–Lindenstrauss lemma to reduce the problem (approximately) to dimension $O(\log n)$, in time $\tilde{O}(dn)$ (see for example Ailon and Chazelle).


Does a do-while loop suffice for Turing-completeness?

I don't know Brainfuck so you'll have to do some translation from my pseudocode.  But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.

do-while is equivalent to while-do.  do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y).

Life is a bit harder if you don't have conditionals.  If you have while-do, you can simulate if Y then X using something like this:

B := true
while (Y and B) do
    X
    B := false
endwhile

But what if you only have do-while?  I claim that the following simulates if Y then X, assuming that X terminates given the current value of the variables.  (This isn't guaranteed: the program if y=0 then loopforever terminates if y != 0, even though X loops for any value of the variables).  Let V1, ..., Vn be the variables modified by X and let X' be X modified so that it uses Vi' instead of Vi for each of those variables. swap(A,B) denotes the obvious code that swaps the variables A and B.

V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

The idea is the following. First, suppose that Y is false.  We simulate doing X once, and store the results in V1'', ..., Vn''; V1', ..., Vn' hold the original values of V1, ..., Vn. Then, we assign V1 := V1'; ...; Vn := Vn', which does nothing. So, if Y is false, we've done nothing.  Now, suppose that Y is true.  We'll now simulate X twice, storing the results in both the "primed" and "double-primed" variables. So, now, the assignments at the end of the loop have the effect that X was computed once. Note that Y only depends on the "unprimed" variables, so its value is not affected by running the loop repeatedly.

OK, so what if X might not terminate for the current value of the variables? (Thanks to Martin Ender for pointing out this possibility.)
In that case, we need to simulate X instruction-by-instruction, using similar ideas to those above. Each instruction definitely terminates so we can use the if simulation above to do instruction decoding, along the lines of "If the opcode is foo, do this; if it's bar, do that; ...". So, now, we use a loop to iterate through the instructions of X, using an instruction pointer and so on so that we know which instruction to execute next. At the end of each iteration of the loop, check Y and check whether X has halted yet. If Y is false, the swapping technique allows us to undo the effects of X's first instruction.


I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}

The pumping lemma for context-free languages says the following:
For every context-free-language $L$ there exists a constant $p$ such that for every word $s \in L$ of length at least $p$, we can write $s = uvwxy$ and:

$|vx| \ge 1$
$|vwx| \le p$
$uv^nwx^ny \in L$ for $n \ge 0$

To prove that $L = \{a^xb^yc^z: x < y \land x = z \}$ is not context-free we will do the following:
Assume language $L$ i context-free and let $p$ be the constant from the pumping lemma.
Take the word $s = a^pb^{p+1}c^p$, which is clearly in $L$, and express it as $s = uvwxy$ as is stated in the lemma.
We know that $|uvw| \le p$ so $v$ consists only of $a$'s.
Denote $s_n = uv^nwx^ny$
Now consider the possible cases:

If either $v$ or $x$ contain more than one letter, than $s_2$ will not be of the form $a^*b^*c^*$, so we know that $v$ and $x$ will consist of at most one letter.
If $v$ is empty and $x$ consists of $b$'s then $s_0$ will not have more $a$'s than $b$'s. If $x$ consists of $c$'s then $s_2$ will have more $c$'s than $a$'s.
If both $v$ and $x$ are non-empty then if $v$ consists of $a$'s and $x$ of $b$'s then we in $s_2$ we will have more $a$'s than $c$'s. If $v$ consists of $a$'s and $x$ of $c$'s than for large enough $m$ in $s_m$ we will have more $a$'s than $b$'s. If $v$ consists of $b$'s and $x$ of $c$'s then in $s_2$ we will have more $c$'s than $a$'s.
If $v$ and $x$ consist of the same letter (i.e $w$ is empty) then following the same type of reasoning we will also reach a contradiction.

Thus we have reached a contradiction for every possible case and so $L$ is not context-free.


Why don't nodes carry as many pointers as possible in a skip list?

In the usual way, where each node carries $i$ pointers with probability $2^{-i}$, the average node has size $O(1)$, so the total space used by the skip list is $O(n)$. If each node carried pointers at every level, then each node would have $\theta(\log n)$ pointers in it, since that is the expected height of a skip list with $n$ nodes. The total space used would thus be $\theta(n \log n)$.

A skip list of one million nodes would thus be using roughly 10 times as much space.


Expected number of comparisons in a merge step?

I will answer your first question about the expected number of comparisons from a statistics/probability standpoint because I think it's rather interesting and non-obvious. Let's assume the input is random, both arrays to be merged are the same length ($n/2$), and the merging algorithm is the generic step by step compare and insert method.

Let $C(i)$ be the number of ways to merge the two arrays of length $n/2$ in $n/2 + i$ comparisons.

Clearly $C(0) = 2$ because this means we are doing exactly $n/2$ comparisons then appending the rest of one list to the end of the other. If we have two lists $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2, \ldots\}$, then these merges would look like:
$$[a_1, a_2, \ldots, a_{n/2}, b_1, b_2, \ldots, b_{n/2}]$$
or
$$[b_1, b_2, \ldots, b_{n/2}, a_1, a_2, \ldots, a_{n/2}]$$

We then have $C(1)$ is the number of ways we can nest $b_1$ within $[a_1, a_2, \ldots a_{n/2}]$ (and the mirror of this, nesting $a_1$ into $b_{1\ldots n/2}$). This can be expressed similarly to the number of integer solutions to equations. We can insert $b_1$ into $a_{1\ldots n/2}$ in the following locations represented by the symbol $\diamond$:
$$[\diamond a_1 \diamond a_2 \diamond \ldots \diamond a_{n/2 - 1} \diamond
 a_{n/2}]$$
It is important to note that we can not place $b_1$ immediately after $a_{n/2}$ as that will create a redundant count to what we already counted in $C(0)$. So this reduces our number of locations from $n/2$ to $n/2-1$ which we can choose from.

Let $n/2 = k$ for simplicity. We can express $C(i)$ as a combinatorial expression:
$$C(i) = 2\binom{(k-1) + (i + 1) - 1}{(i+1) - 1} = 2\binom{k + i - 1}{i} = \frac{2(k+i - 1)!}{i!(k-1)!}$$

So we now have the total number ($N$) of possible merges is the total number of ways of choosing $n/2$ elements from a set of $n$. This can be seen easily if you imagine a skeleton array of length $n$, we then must select $n/2$ spots in this array to put one of our arrays being merged (and symmetrically the other array would be placed in the holes). We then have:
$$N = \binom{n}{n/2} = \binom{2k}{k}$$
This is again clear to see when we sum the $C(i)$s:
$$\begin{align}
\sum_{i=0}^{k-1} C(i) & = \sum_{i = 0}^{k-1} 2 \binom{k + i - 1}{i}\\[0.5em]
& = 2\binom{2k - 1}{k - 1}\\[0.5em]
& = \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em]
& = \frac{2k}{2k}\cdot \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em]
& = \frac{(2k)!}{k!k!}\\[0.5em]
& = \binom{2k}{k} = \binom{n}{n/2} = N
\end{align}$$

We then can find the probability of $k + i$ comparisons as:
$$\begin{align}
P[X = k + i] & = \frac{C(i)}{N}\\[0.5em]
& = 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}
\end{align}$$
Then it's easy to get the expected value:
$$\begin{align}
E[X] & = \sum_{i = 0}^{k-1} (k + i) \cdot 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}\\[0.5em]
& = \frac{2k^2}{k + 1}\\[0.5em]
& = \frac{n^2}{n + 2} \approx n -2
\end{align}$$
From this it's clear to see that the expected number of comparisons is pretty close to $n - 2$. In fact we can pull up a table to see how they compare:
$$\begin{array}{|r|r|r|}
  \hline n & \lfloor n^2/(n+2) \rceil & n - 2\\
  \hline 2 & 1 & 0\\
  \hline 4 & 3 & 2\\
  \hline 8 & 6 & 6\\
  \hline 16 & 14 & 14\\
  \hline 32 & 30 & 30\\
  \hline 64 & 62 & 62\\
  \hline 128 & 126 & 126\\
  \hline 256 & 254 & 254\\
  \hline 512 & 510 & 510\\
  \hline 1024 & 1022 & 1022\\
  \hline
\end{array}$$
Another visual, here is the probability mass function of $x$ comparisons for merging into an array of size $1024$ (e.g. merging two arrays of size $512$):


The more accurate time complexity analysis for  Radixsort gives time complexity as $O(kn)$-time where $k$ is number of digits, or keys (radix is defined as the base by which digits or keys are formed, hence the name radix sort).

So, radixsort can be $\Omega(n\log n)$ if you have $\Omega(\log n)$ digits in the numbers you are sorting. For example, if you are given numbers 1 to $n$ in an unsorted list, then radix-sort will do the sorting in $O(n\log n)$ time.

See https://en.wikipedia.org/wiki/Radix_sort.


Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs?

I'm not entirely sure that this question is on topic, but nonetheless, I suspect it has a simple answer.
Physical write protection mechanisms predate floppy disks. At my school holiday job in the 1980s, my desk had a drawer full of write rings for reels of 9 track tape. If the ring is in place, you can write to the tape.

There are certainly flash devices with physical write protection mechanisms. Many older USB drives have them. Memory Stick and SD both have a write protection lock. You can see it on the left-hand side of an SD card.

Micro SD cards don't have them because there's no way to effectively make them "micro". And I suspect that's the main reason why they went out of vogue. Once it became unimportant for one removable medium, many of the rest followerd.
The history of storage is about maximising speed, and minimising size and price. Adding a write protection lock adds to both size and price when devices are very small.
In addition, moving parts wear out faster than devices with no moving parts. Unlike disks or tape, flash memory has no moving parts by default. Adding a write protection lock means adding a moving part, which effectively shortens its usable life.


The first question you need to ask yourself, is when does it happen that there is no such vertex. For undirected graphs the answer is easy: such a vertex exists if and only if the graph is connected. DFS/BFS allow us to decompose the graph into connected components, and in particular we can find out whether there is more than one.

For directed graphs, it could happen that the underlying undirected graph is connected, yet the directed graph itself has no vertex from which you can reach all others. An example is a path with two edges directed toward the center. The corresponding refinement of the concept of connected components is strongly connected components, in which each vertex is reachable from any other. We can contract each strongly connected component to a single vertex, and then what we are left with is a DAG (directed acyclic graph; can you see why?). The question you should be asking yourself now is:

  Given a DAG, when is there a vertex from which all other vertices are reachable?

Once you answer this question, all you need is an algorithm for finding strongly connected components. There are several DFS-based algorithms for that available on the web.

(Note: while this may not be the simplest solution, that is, there might be "shortcuts", the concept of strongly connected components is inherently useful and good to be aware of.)


Is the complement of a Max Prefix Sum a Min Suffix Sum?

It depends on whether the maximum prefix and minimum suffix are unique. Consider for example the array $0$ — you can easily find a counterexample to your claim. Suppose therefore that $\sum_{i \leq j \leq k} A[j] \neq 0$ for all $i \leq k$. Let now $j$ maximize $\sum_{i=1}^j A[i]$, and let $k$ minimize $\sum_{i=k+1}^n A[i]$. We want to show that $j=k$. Otherwise, there are two cases:

If $j < k$, let $S = \sum_{i=j}^{k-1} A[i]$. By assumption $S \neq 0$. If $S > 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i]$, and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.
If $j > k$, let $S = \sum_{i=k}^{j-1} A[i]$. By assumption $S \neq 0$. If $S < 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i]$, and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.


Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

What you might have heard could have been a formulation of a No Free Lunch Theorem. Loosely, those results say that you can either have an optimization algorithm that does fairly well on many problems, or really well on some problems, but not both.

Genetic Algorithms are rather broad classes of optimizers, so you can typically apply them to many types of problems with decent results, but for specific problems there will typically be more efficient algorithms that only work for this type of problem.


I think that's often called a "variable assignment", since it assigns to each variable a value (a vertex in the graph, in your case).

If the graph is equipped with a set of such tuples, these might be considered to be hyperedges, i.e. edges connected to an arbitrary number of vertices (not necessarily two of them).


This is an instance of the identity $(xy)^*x = x(yx)^*$ with $x = a$ and $y = 1 + b$:
$$
(a + ab)^* a = (a(1+b))^*a = a((1+b)a)^* = a(a +ba)^*
$$


How to practically measure entropy of a file?

Entropy is a feature of a random variable. A given file has zero entropy, since it is constant. Entropy makes sense in many situation in which there is no channel, and you can apply it to a random ensemble of, say, WAV files, generated from a given source. In this case, your $x$ is the entire WAV file.

The actual WAV file (excluding the header) can be thought of being generated by some Markovian source. This source produces sounds amplitudes ("samples") in a sequence, each one depending on the ones preceding it. After running the process for very long, the entropy of each sample (more accurately, the conditional entropy given the preceding samples) gets very close to some limiting value, which we define to be the entropy of the source. The entropy of $N$ samples is $N$ times that number (in the limit; again, more accurately, we are measuring the conditional entropy). Lempel and Ziv showed that if the sample entropy is $H$ bits, then their algorithm compresses $N$ samples to $HN + o(N)$ bits, with high probability (the probability is over the samples). Lempel–Ziv compression is quite popular in practice, used for example in the popular gzip format.

Due to this result of Lempel and Ziv, the entropy of a source can be approximated by compressing a long sequence of samples using the Lempel–Ziv algorithm. This doesn't estimate the entropy of the specific samples, which is not a well-defined concept (a constant sequence has zero entropy), but rather the entropy of the source generating it.

A related concept is algorithmic entropy, also known as Kolmogorov complexity. It is the length of the shortest program generating your file. This quantity does make sense for an individual file. In the case of a file generated by a random source, the Lempel–Ziv theorem shows that the algorithmic entropy of a file is bounded, with high probability, by its Shannon entropy. Unfortunately, algorithmic entropy isn't computable, so it's more of a theoretical concept.

To complete the picture, I suggest reading Shannon's paper on Prediction and entropy of printed English for a different approach to estimating the entropy of a source.


What machine learning training algorithm to use for this kind of string dataset?

You want to perform supervised learning, i.e., you have set of training examples (in this case, a set of 4-vectors with a label that corresponds to one of the 100 songs). So in particular, you want to do classification: given a 4-vector, predict a song. It might feel silly to call the songs a "category", but when you look past the naming in this particular case it should make sense: given an "activity vector", what is the song out of the 100 possible songs that will be chosen?

A fair starting point is scikit-learn's flowchart for choosing an estimator. Assuming the vector entries come from a predefined set of possibilities, you can simply map the strings to integers. For example, replace "walking" by 0, driving by "1", or replace "nothing" by 0, reading by "1", and so on. So for concreteness, your training data might be a file, where each line is something like "{0,1,0,8},47" meaning that activity 0, mob act 1, session 0, and mood 8 corresponds to song 47.

Now, assuming you have less than 100k samples, a good starting point is a linear support vector machine as per the flowchart. Depending on your results, the flowchart guides you towards other choices.


Shortest path from starting cell to all cells in the grid

You have an unweighted, undirected graph with $N$ vertices, and where each vertex has degree $K$.  Then the problem of computing shortest paths can be solved in $O(KN)$ time using simple breadth-first search.

Why is this faster than Floyd-Warshall etc.?  Because Floyd-Warshall has to handle weighted graphs.  In your case you have an unweighted graph: every edge has weight 1 (the length of a path is just the number of edges in it).  There are faster algorithms for computing shortest paths in unweighted graphs than in weighted graphs; unsurprisingly, the problem is harder if you have a weighted graph.  If you have an unweighted graph, you don't need the fancier algorithms, like Floyd-Warshall; breadth-first search is enough.


Need help finding/writing an algorithm to reassign items to groups with minimal changes

Every user either remains in their initial group, or moves to some other group for a cost of 1. So it suffices to look for a matching between new groups and old groups that maximises the number of users who don't need to move; subtracting the number of stationary people from the total number of people gives the number of people who need to move.
To do this, create an instance of the Assignment Problem, a.k.a. Maximum-weight Bipartite Matching, in which you have a vertex in A for every current group, a vertex in B for every new group, and an edge between every pair of vertices with weight equal to the number of users shared by the two groups (edges with weight 0 can be omitted). The goal is to find a matching -- a subset of edges, no two of which share an endpoint -- of maximum weight. To solve problem instances the size of your examples, trying all possibilities with brute force would be fine, but they can be solved more efficiently using the Hungarian Algorithm or linear programming, as described on the linked page.


Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$?

A function that is $O(n^{1/2}) = O(\sqrt{n})$ is a polynomial, not an exponential, function of $n$. However, when analyzing the run-time of algorithms, we need to be clear about what $n$ actually is.

Here, $n$ is the (value of the) number whose primality is being tested. However, we measure the run-time of the algorithm in terms of the length of its input in bits. The number $n$ can be represented in $\log n$ bits, which means that the running time of $O(n^{1/2})$ is actually exponential in the length of the input.


The link for position $i$ is not determined by the letter at position $i$  but instead by the letter $b$ at position $i-1$ (and the failure link at $i-1$).

For the rest you correctly describe the algorithm: follow the failure links until we find a position $j$ such that the letter at that position equals $b$.

Usually the failure link at the last letter is not computed. The reason is that one does not need it: when we have reached the last position we have found the pattern! However, if we want to find the next match, a failure link at the end would be helpful.


Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

Consider the language
$$
L = \{ 0^{m^k} : m \geq m_0 \}.
$$
Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that
$$L^* \supseteq \{ 0^m : m \geq M_0 \}$$
for some $M_0$, and so $L^*$ is regular. Using the classical formula of the coin problem applied to $m_0^k$ and $(m_0+1)^k$, we can upper bound the optimal value of $M_0$ by
$$
M_0 \leq (m_0^k-1)((m_0+1)^k-1).
$$
For example, the case considered in your post has $k=2$ and $m_0=3$, and this gives the bound $M_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.

Recently it has been shown that it is $\Sigma_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\{ m^k : m \geq m_0 \}$ has a lot of structure, and so the problem might be feasible.


An intuitive approach towards the difference is understanding that the productions of syntax #1 add new material to the left of existing symbols whereas those of syntax #2 do so on the right-hand side.

syntax #1:

derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ n ] [n-1] [n-2]     [ 2 ] [ 1 ]`

syntax #2 (step #n is the application of rule 3 and produces no terminal) :

derived string of terminals: `  T    + T   + T  ...  + T   + T `
derivation step:             `[ 1 ] [ 2 ] [ 3 ]     [n-2] [n-1]`

for a rigorous proof note that under both syntaxes, each derivation leads to an initial T followed by sequence of  + T. for the grammars at hand this can be proven by induction over the number of rule applications.


Strassen's matrix multiplication algorithm when $n$ is not a power of 2

The solution is to pad the matrices with zeroes, using the block matrix identity
$$
\begin{bmatrix}
A & 0 \\
0 & 0
\end{bmatrix}
\begin{bmatrix}
B & 0 \\
0 & 0
\end{bmatrix}
=
\begin{bmatrix}
AB & 0 \\
0 & 0
\end{bmatrix}
.
$$

Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N > n$. In other words, we add $N-n$ rows and $N-n$ columns of zeroes.

You can do this in two ways:

Pad the original $n \times n$ matrices to $N \times N$ matrices, where $N$ is the closest power of 2. Note that $N < 2n$, so this doesn't affect the asymptotic complexity.
Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m > 1$ odd, we pad them to $(m+1) \times (m+1)$ matrices by adding a single row and a single column of zeroes. This also doesn't affect the asymptotic complexity.

A third option is to make use of, say, a 3x3 matrix multiplication algorithm if the dimension is odd but divisible by 3. Laderman found such an algorithm which uses 23 multiplications (instead of the trivial 27).


Turing machine which diverges on its own code

The language $K^c$ is clearly co-RE: given an input $M$, simulate $M(M)$ until it halts and then reject; if it doesn't halt, the simulation doesn't halt.  Now, any language that is both recursively enumerable and co-RE is actually recursive (exercise: prove this).  Since $K^c$ is not recursive (exercise: prove this), it cannot be recursively enumerable, either.

Your idea of reducing to the complement of the halting problem doesn't work.  Firstly, that's the wrong way around: you'd want to reduce the complement of the halting problem to $K^c$ to prove that $K^c$ is hard.  Second, it's possible for a set to be neither RE nor co-RE. (Why?  There are countably many RE languages and countably many co-RE languages, since each such set corresponds to a Turing machine and there are only countably many Turing machines. But there are uncountably many languages over any finite alphabet.) However, from your description, it sounds like you weren't trying to do a reduction but a diagonalization, similar to the proof of the undecidability of the halting problem.  That sounds like it could work but the method I give above is much easier.


Understanding Expected Running Time of Randomized Algorithms

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. This quantity depends on the length of the input $n$.
Given either a randomized or a deterministic algorithm, one can also talk about its expected running time on a random input from some fixed distribution. For example, deterministic quicksort (with a fixed pivot) has expected running time $\Theta(n\log n)$ on a randomly distributed input of length $n$. This is known as average-case analysis. Your example of linear search fits this category.
A related concept is smoothed analysis, in which we are interested in the expected running time of an algorithm in the neighborhood of a particular input. For example, while the simplex algorithm has exponential running time on some inputs, in the "vicinity" of each input it runs in polynomial time in expectation.


Simple path in a graph, within a given range of lengths

A special case of your problem is to determine whether there is a path of length between $n-1$ and $n-1$ (sic) in an $n$-vertex graph. This is the Hamiltonian path problem, which is well known to be NP-complete, so your problem is also NP-complete. More generally, it's also NP-complete to determine if a graph has a path of length at least $k$ (i.e., between $k$ and $n-1$) between two given vertices.


$\epsilon$ - Nash Equilibrium exceeds Nash Equilibrium

It is quite simple: if you enlarge the set of possibilities you can get better values.

Here, in place of requiring the possibilities to be equilibrium we require them to be almost equilibrium, a larger set of possibilities, therefore a higher possible value.

Here is a simple example:

$$\left[\begin{array}{cc}
5/5 & 0/6 \\
6/0 & 1/1 \\
\end{array}\right]$$

Let $\epsilon = 2$. Now $5/5$ on the top left corner is an $\epsilon$-equilibrium where as the equilibrium is $1/1$.


m-functions in Turing's paper "On Computable Numbers and applications..."

m-functions are quite similar to what we call today "macros". $f(\dots)$ is just the name of a supplementary m-configuration, that can be parameterized (like a macro). The trick is to not overthink it.


Under the assumptions you've stated, yes, the code runs in constant time.  The running time for any string can't be longer than the running time for a 128-character string, which is some constant number of steps.


benchmark data set for Metareasoning problem

In this sort of situation, two standard answers are:

Figure out what the practical applications of your algorithm are.  Find a dataset associated with that particular application, and try your algorithm on it and see how well it works.  Measure success using some metric that is appropriate for that particular application.
Look through the research literature to find previously published papers that try to solve the same problem.  Look at what benchmarks they used.  Use the same benchmarks, so that you can compare how well your algorithm does to previously published algorithms.


Notation for expressing function call count during a program run

Based on your desired usage and the fact that there likely isn't a widely-known notation for this, I think that, whatever notation your use, you should formally simply consider it a name. As you want to use the actual value, a variable (or function if you wish to distinguish among parameters for the call) would suffice.
What I mean by considering the notation a name is that you give your notation no syntactic status: it is simply a naming convention for some function or variable. This requires that you must define the name for each different method call number you wish to describe. I advise you to do this, as number of function calls is something that is context-dependent (calls by whom? calls made when?), so defining this for every function call separately gives a natural place to specify this.

So, for your particular example, a name like $\#\mathrm{function1}(\bullet)$ could work.
Then, we can write something like

Let $\#\mathrm{itersearch}(a)$ be the number of calls to the function $\mathrm{itersearch}()$ in the execution of algorithm A with parameter $a$.
(...)
Most of the time less than $\#\mathrm{iterSearch}(searchState)/3$ child nodes were searched during experiments.


For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?

The statement is false. Consider the directed graph $G=(V,E)$ where $V=\{1,2\}$ and $E=\{(1,2), (2,1)\}$.
The graph only contains a single strongly connected component, namely $G$ itself. However no vertex in $V$ is a sink.


Returning random integer from interval based on last result and a seed

I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$.  Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and then increment $i$ (wrapping around so that $b+1$ becomes $a$).
There are standard methods for generating such a random permutation in the cryptography literature: look up format-preserving encryption.  The seed is the cryptographic key.  You will be able to compute $\pi(i)$ in $O(1)$ time and $O(1)$ space, so this should be very efficient and avoid the need for a lot of storage.
If you insist that the next output should be a function of the previous output, you can let $g(i)=i+1$ (except that $g(b)=a$), then let $f(i)=\pi^{-1}(g(\pi(i))$, where $\pi$ is a random permutation chosen as above.   This will then give you a random cycle that iterates through the elements of $[a,b]$ in a random order.  The outputs are the sequence $f(a),f(f(a)),f(f(f(a))),\dots$.


Search for minimum in an array of $k$ monotonic subarrays

Here are algorithms and matching lower bounds, which fully resolve the situation:

For $k=1$, you can find the minimum in $O(1)$ time: just examine the two endpoints of the array, $A[0]$ and $A[n-1]$.
For $k=2$, you can find the minimum in $O(m + \lg (n/m))$ time, as was mentioned in the question.  I prove below that you can't do any faster than this (up to a constant factor).
For $k\ge 3$, I prove below that finding the minimum takes $\Theta(n)$ time, regardless of $m$ (it takes $\Omega(n)$ time even if you are guaranteed that $m=0$).  The trivial algorithm takes $O(n)$ time, so if $k\ge 3$ it is not possible to do better (up to a constant factor) than the trivial algorithm.

Moreover, randomization doesn't help.

Lower bounds.  For $k=2$, consider an array $A$ that is positive and strictly decreasing on $A[0\ldots r-1]$, then $A[r]=A[r+1]=\cdots=A[r+m-1]=0$, then is positive and strictly increasing on $A[r+m\ldots n-1]$.  Now pick an index $i$ satisfying $r \le i \le r+m-1$, and replace $A[i]$ with $-1$.  Notice that this is an array with $k=2$ monotonic sub-arrays (decreasing-then-increasing).  However, even if you were given the value of $r$, you would still have to examine every element of $A[r\ldots r+m-1]$ to find the minimum, so any algorithm has to take $\Omega(m)$ time.  Moreover, it's easy to show that any algorithm will need $\Omega(\lg n)$ time, so we get a $\Omega(\max(m,\lg n))$ lower bound on the running time.  This implies a $\Omega(m + \lg(n/m))$ lower bound as well.

For $k=3$, consider an array that is positive and strictly increasing on $A[0\ldots n-1]$, then pick an index $i$ and modify $A$ by replacing $A[i]$ with $-1$.  This is an array with $k=3$ monotonic sub-arrays, and to find the minimum, you have to scan every element of $A$, so the running time is $\Omega(n)$.  Notice that in this example, $m=0$, so knowing (an upper bound on) the value of $m$ does not help you speed things up.

If you want a heuristic algorithm for $k=2$ (with no guarantees about worst-case running time), the following randomized algorithm might work well in practice, even though its asymptotic worst-case running time is not any better.

We'll assume the array is decreasing-then-increasing (until you find any evidence to the contrary; if you find evidence that it is decreasing-then-increasing, you can just look at the two endpoints and terminate immediately).  We're going to search for the changeover point (which will be the minimum we're looking for).  To do that, we'll use ternary search with random selection of the two midpoints.

In particular, we'll use random probing to find two indices $i<j$ such that $A[i],A[j]$ are different from each other and from $A[0],A[n-1]$.  Once we have these indices, we can do a case analysis on the relative order of $A[0],A[i],A[j],A[n-1]$ and recurse on either $A[i\ldots n-1]$ or $A[0\ldots j]$.  This is a smaller sub-array of expected size $2n/3$.

How long does it take to find two indices $i,j$ that are acceptable?  We can start by randomly choosing values for $i$ until $A[i]$ is different from $A[0]$ and $A[n-1]$; then we randomly choose values for $j$ until $A[j]$ is different from $A[0],A[i],A[n-1]$.  If there are $m$ repeats, then $n-m$ of the entries are unique; thus, each random choice of $i$ (or $j$) has at least a $(n-m)/n$ probability of finding an acceptable value.  Consequently, the expected number of random probes done is $O(n/(n-m))$.

Also, we recurse on an array whose expected size is a constant fraction smaller, so we expect to do only $\lg n$ recursions.

Of course, the total running time could still be bad (e.g., with the example I gave above), but it might often be OK if you have some reason to think the absolute worst-case inputs are unlikely.


Insertion of n consecutive keys in an initially empty B-Tree

We know that every node except the root must have at least t−1=1 keys, and at most 2t−1=3 keys. The final tree can have at most n−1 nodes when n≥2. Unless n=1 there cannot ever be n nodes since we only ever insert a key into a non-empty node, so there will always be at least one node with 2 keys. Next observe that we will never have more than one key in a node which is not a right spine of our B-tree. This is because every key we insert is larger than all keys stored in the tree, so it will be inserted into the right spine of the tree. The fewest possible number of nodes occurs when every node except the deepest node in the right spine has 2 keys and the deepest node in the right spline has 3 keys. So at height 1, 1 nodes, at height 2, 3 nodes, …, at level h, 2h−1 nodes. In this case, n =2^(h+1)−1 where h is the height of the B-tree, and the number of nodes in B-Tree is #nodes = 2^(h+1)−2−h = n−lg(n+1). So for any n, the final B-Tree must have n−⌊lg(n+1)⌋≤#nodes≤n−1 (if n≥2).


Well, since this upper bound is not nearly tight, you can just use basic transformations to get

$$(n+1)!< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$


ε-greedy is just a way to promote exploration in Reinforcement Learning. I would not classify SARSA or Q-Learning as ε-greedy algorithms.

The latter are very common reinforcement learning algorithms and you can definitely can find lots of material about them.

I would suggest to have a look at this classic book (the draft for the second edition is available for free)

https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Another shorter and excellent resource is (have a look at chapter 21):

Russell SJ, Norvig P, Davis E. Artificial intelligence: a modern approach. Upper Saddle River, NJ: Prentice Hall; 2010.

EDIT:

The paper you posted is using SARSA(λ), it is not the same as SARSA. You will need to go through a few Sutton chapters for that to make sense. You won't find it in Russell.

The link to SARSA(λ) in Sutton (1998) HTML version is here: webdocs.cs.ualberta.ca/~sutton/book/ebook/node77.html

However, I think you will need to read at least chapter 6 before jumping into eligibility traces


Difference between graph-partitioning and graph-clustering

Graph partitioning and graph clustering are informal concepts, which (usually) mean partitioning the vertex set under some constraints (for example, the number of parts) such that some objective function is maximized (or minimized). We usually have some specific constraints and objective function in mind. However graph partitioning and graph clustering, as vague informal concepts, are pretty much the same.


Is maximum-leaves spanning tree np-complete?

The maximum leaf spanning tree(MLSPT) is equivalent to the minimum connected dominating set(MCDS), see here. So we just need to prove MCDS is NP-complete. It's easy to verify that the decision version of MCDS is in NP. Similar to proof of NP completeness of dominating set, we perform a reduction from vertex cover(VC), i.e., we prove that $VC \le_p MCDS$:

Given an instance $(G(V,E),k)$ of VC we construct an instance $(G'(V',E'),k)$ of MCDS as follows: $G'$ contains the complete graph on $V$, and for each edge $(u,v)\in E$, an edge vertex $x_{uv}$ is introduced, along with two extra edges $(x_{uv},u)$ and $(x_{uv},v)$. Formally. we have $V'=V\cup\{x_{uv}:(u,v)\in E\}$, $E' = E\cup\{(x_{u,v},u):(u,v)\in E\}$. The reduction can obviously be done in polynomial time. Note that any induced subgraph in $G'$ is a connected graph.

Let $S$ be a vertex cover of $G$. For any $v\in V'\setminus S$, if $v\in V$ then by the definition of vertex cover we know that $v$ dominated by $S$. If $v = v_{xy}$ is an edge vertex of some edge $(x,y)\in E$, because $(x,y)$ is covered by $S$, then $x\in S$ or $y\in S$, $v_{xy}$ is dominated by $S$. Thus $S$ is a connected dominating set of $G'$.

Suppose that $S$ is a connected dominating set in $G'$. We first observe that for any edge vertex $v_{xy}$ in, it can only be dominated by $x$ or $y$. For any edge vertex $v_{xy}\in S$, we replace it with $x$. The replacement does not increase the cardinality of $S$ and mantains $S$'s property of being a dominating set. Now $S$ contains no edge vertex, so every edge vertex is dominated by $S$, that is to say, every edge in $G$ has at least one endpoint in $S$. Therefore, $S$ is a vertex cover for $G$. $\square$


It principle it could depend on the processor. However, I imagine that comparison are done using the same circuitry as subtraction, so the complexity should be comparable. I'm assuming that by comparison you mean an instruction comparing two registers and setting some flags (or another register). A conditional jump might interfere with pipelining and so would be costlier.


The use of binary search when determining whether a point lies inside a given convex hull

So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ lies you have to find out on which side of a line connecting $\mathbf{O}$ and a given vertex $\mathbf{v}$ the point is.

Consider $\mathbf{r}_v$ to be the connecting vector from $\mathbf{O}$ to vertex $\mathbf{v}$. A normal vector $\mathbf{n}_v$ to $\mathbf{r}_v$ is simply given by

$\mathbf{n}_v = \left(\matrix{-{\mathbf{r}_v}_y \\ {\mathbf{r}_v}_x}\right)$.

Let us now project the vector $\mathbf{r}_z$ connecting $\mathbf{O}$ and $\mathbf{z}$ on the normalized $\mathbf{n}_v$:

$d_z = \frac{\mathbf{n}_v \mathbf{r}_{z}}{|\mathbf{n}_v|}$.

With the sign of $d_z$ we can now decide on which side of the line z lies.

Just draw down the situation and this construction and this will become obvious. There may be a more elegant way to do this but this approach will work.

You probably have to construct some more logic because the vertices actually are in a cyclic arrangement but that should not be too difficult.


Why are Complexity Notations Called Asymptotic?

I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes.

The word asymptotic stems from a Greek root meaning "not falling together". When ancient Greek mathematicians studied conic sections, they considered hyperbolas like the graph of $y = \sqrt{1 + x^2}$ which has the lines $y = x$ and $y = -x$  as "asymptotes". The curve approaches but never quite touches these asymptotes, when $x \to \infty$.
Nowadays we use "asymptotic" in a broader sense to mean any approximate value that gets closer and closer to the truth, when some parameter approaches a limiting value [emphasis added]. For us, asymptotics means "almost falling together".


An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence

Here is the rough idea, for determining the probability that $x$ appears before $y$:

Construct a DFA that accepts the language of all binary strings in which $x$ appears before $y$.
Take the adjacency matrix of the DFA, replace the edges by $1/2$ entries.
Relate the probability that you're after to this matrix, and using this, calculate the probability.

I'll let you sort out the remaining details.


What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?

A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and increments it when the process no longer needs the resource. When n reaches zero, the access of the resource is denied.

A real life example will make things clear: imagine a public toilet with 5 toilets (n=5). At the entrance there is a guard (the semaphore). If some one wants to enter the guard looks at n. if n > 0 the guard let the visitor in and decrements n. If someone comes out n is incremented. Only if n=0 the guard will block the entrance until someone leaves.

Consider a binary semaphore, where n = 1. This semaphore works as a flag which is activated when the resource is in use or not, and can be used to protect a critical section. When a process wants to enter the critical section, it first looks at the ‘flag’ to find out if the critical section is being used by another process. If not, the process enters and raises the flag, preventing the other processes to enter. The flag is unset when the process leaves, and therefore ensures mutual exclusion.


Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

There will be ${64 \choose n} \cdot {64-n \choose n}$ such combinations, since there are ${64 \choose n}$ ways to choose a subset of $n$ of the 64 variables to be -1, and then ${64-n \choose n}$ ways to choose a subset of $n$ of the $64-n$ remaining variables to be 1.  Equivalently, this is ${64! \over n!^2 (64-2n)!}$.

You probably won't want to explicitly generate all of those combinations, as it would take exponentially long to do so (as there are exponentially many such combinations).

But if you really wanted to explicitly enumerate all combinations, this formula also highlights the way to do that.  First, enumerate all possible ways to choose $n$ of the 64 variables; there are standard algorithms for how to do that (e.g., https://stackoverflow.com/q/127704/781723, https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations).  Then, for each such, enumerate all possible ways to choose $n$ of the remaining $64-n$ variables (again, using the same algorithm).  That will give you all ways to choose a combination of the sort you desire.

Still, any time you are enumerating exponentially many possibilities and then doing something to each, you should check whether maybe there's a better way to achieve your ultimate goal without enumerating all of them.  If you want to find the combination that minimizes some cost function, there might be a better way to do that, depending on the cost function.


What is the difference between Coding and Programming?

They are mostly synonymous. In that profession you can be called, or call yourself, a coder, a programmer, a software developer, or a software engineer. They all do the same job. If you call yourself an "engineer", then in many jurisdictions you would have to have training, pass some stringent exams, and may have legal responsibilities for the results - people calling themselves "software engineers" usually ignore that.

The name used usually goes with some expectations. Someone called a "coder" or "programmer" is usually expected to write code (also called programming), with no expectations of the actual outcome. A "software developer" is someone who is expected to produce complete, working, usable software as the result of his work. A "software engineer" is usually someone who fancies a nice title.

"Coder" is often used as a pejorative. Usually by people who couldn't do it themselves if their life depended on it.


Skew arithmetic circuits are usually defined a bit differently: in every multiplication gate, one of the inputs of the gate is a constant or an input of the circuit (we assume that multiplication gates are binary).
This is very similar to your definition, if linear is interpreted as syntactically linear. That is, one of the inputs of any multiplication gate is either a constant, an input of the circuit, or the output of an addition gate whose inputs are inputs of the circuit or constants. Using the distributive rule, we can take a circuit satisfying this definition and turn it into a circuit satisfying the usual definition.
Another interpretation would be that one of the inputs of any multiplication gate is a linear function of the inputs, that is, it is semantically linear. For example, $(a+b)^2-(a-b)^2$ is semantically linear but not syntactically linear. This is probably not the interpretation which is meant here.


Proof of undecideability that one state is reached before another

Let us follow the hint given by Yuval.

What is the halting problem?

It is the problem of accepting the following language.

$$\text{HALT}= \{⟨M, w⟩ : M \text{ is a TM and }M\text{ will halt on input } w\}$$

What is the current problem?

It is the problem of accepting the following language.

$$\begin{align}
\text{One}&\text{StateBeforeAnother}
= \{⟨M, q, q',w⟩: M\text{ is a TM} \\&\wedge q\text{ and } q'\text{ are two states of }M \\
&\wedge \left(M \text{ will reach } q' \text{ on input } w\right.\\
&\vee M \left.\text{ will reach } q \text{ before reaching } q' \text{ on input } w \right)\}
\end{align}$$

How to define $\text{HALT}$ in a way similar to how $\text{OneStateBeforeAnother}$ is defined?

The idea is that if we can formulate $\text{HALT}$ in a way similar to the way $\text{OneStateBeforeAnother}$ is defined, then we might reduce the former to the latter.

$M$ halts on input $w$ means $M$ reaches a halt state on input $w$. $\text{OneStateBeforeAnother}$ is about $M$ reaches $q$ and then $q'$.

Let us try brute pattern matching.

Let $q$ be a halt state. $M$ reaches $q$, the halt state and then reaches $q'$. That cannot happen since the halt state is the last state. Sigh!
Let $q'$ be a halt state. $M$ reaches $q$ and then reaches $q'$, the halt state. That makes sense. What is $q$ then? How about letting $q$ be the initial state of $M$?

Great, we have just found the following reduction, where $q_0$ is the initial state of $M$ and $q'$ is the halt state of $M$ on input $w$.

$$⟨M, w⟩\in\text{HALT} \to
⟨M, q_0, q',w⟩\in\text{OneStateBeforeAnother}$$

Wait, this is not a well-defined reduction as $q'$ cannot be known at the time of reduction since it depends on how $M$ runs on input $w$, the undecidable halting problem!

I will leave you to conquer the problem above, how to require $q'$ to be a halt state without dependence to $M$ and $w$.


Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Let $p$ be the integer in Ogden's lemma, and consider the word $a^q b^{2^q} \in L$ for $q$ satisfying $2^q > p$, marking its $b$ part. According to the lemma, we can write $a^q b^{2^q} = uxyzv$ where $xz$ contains between one and $p$ letters $b$. Since $uyv \in L$ and $xz$ contains at least one $b$, it follows that it also contains at least one $a$. For $ux^2yz^2v$ to be in $L$, we need $xz$ to contain at least $2^{q+1}-2^q = 2^q$ letters $b$, contradicting our choice of $2^q > p$.

More generally, this works for any language of the form $\{a^nb^m : m \geq f(n)\}$ for any $f(n) = \omega(n)$, or even whenever $\limsup f(n)/n = \infty$.


Determine whether removing a node on a graph will disconnect the graph

Yes, if we know something about the given graph. For example, if we know that graph is a tree or a cycle or a star graph. Or we might be able to terminate the algorithm early, for example, if we can determine the neighborhood of that node is still connected after that node is removed.

However, an algorithm to determine whether an arbitrary node is an articulation point or not in a general graph has to visit every node in the worse case.

Suppose a clever algorithm claims a given node is an articulation point without visiting all nodes. Suppose node $\mathcal U$ is not visited. Well, it could happen that $\mathcal U$ is connected to every node. Or there might be an edge that connects $\mathcal U$ to a point in the other connected component. That is a contradiction.

To be slightly more precise, any such algorithm should visit every remaining edge in the worst case.

Any way, a DFS that goes through all edges runs in $O(|E|)$ time is pretty fast for graph without too many edges.  It should not be a big performance concern usually. If a series of node will be removed one by one and you want to determine the first one that disconnects the graph, it might help to do some precomputation to decompose the graph in certain way or other kinds of tricks to reduce the amortized cost. That is another story, though.


Can all programs with mutable state be refactored in programs without?

There is no general notion of "mutable state" for a generic language. I believe we need to restrict this question to some specific language.

For instance, consider a basic imperative language with arithmetic expressions ($*,+,-$), read input, write output, assignment, composition, conditional ($e=0$ guards), and while loop. No user-defined functions, hence no recursion. Unbounded-precision integer variables. Forbidding mutability would greatly affect the computational power. Unrestricted, it is Turing powerful, but after restriction becomes a very weak language which is able (I believe) to compute only piecewise polynomials / divergence.

If the language is instead a higher order functional language with recursion and assignment (e.g. Scheme), forbidding mutability will not affect its computational power: it was and remains Turing powerful. Mutable state can still be simulated without mutability. A way to do it is to encode state-mutating functions $f$ as pure functions $f({\sf input},{\sf old\_ state})=({\sf output},{\sf new\_state})$ (see the so-called "state monad" in functional programming).

Further, Turing & Church proved that the (pure) $\lambda$-calculus has the same power of the Turing machine. So this is a pretty established result! It is one of the very first discoveries that started computer science in the 30s.


Is it correct to say that CPU's only compute threads?

Take a step back. In most operating systems, a process is an entity that owns resources, like memory areas, open files, and such. A thread is an entity that can be scheduled (i.e., get a CPU core assigned, has its own contents of registers and local variables). Several threads can exist within the same process, sharing it's resources.

Switching between threads that share memory means that the table pages and cache entries don't have to be flushed, and that is a major cost in current processors (today to access a word in memory can take the same time than hundreds of instructions!).

Note that some systems (like Linux) have a non-standard view of threads, in that you can create a new thread from an existing one and specify in detail exactly what they are to share.

Is using threads or processes a win? No way to answer in full generality. If different threads of execution don't use the same data, it won't matter much (see above), and it can be advantageous for them not to be able to trample on each other's work. Use processes. If they share data intimately, threads are a better match (and will be more efficient). But then again, having several cores accessing the same data gives rise to cache ping-pong and bad performance. Also, taking such a program and rewrite to run on a distributed system (note that current massive machines are NUMA, essentially separate machines connected by an insanely fast network, but still much slower than direct access to memory) will be much harder.


Your problem specification is incomplete. What do you mean by optimal? Do you want to, say, minimize transactions costs? Do you want to make sure you do not cross the spread?

The original portfolio was worth \$800. The new portfolio is worth \$804. Assuming your actions do not change the market price, and assuming no transactions costs, that is a given.

You had \$200 allocated to each security. Now, you want \$201 allocated to each security:

| Name   | Price | Amount | Notional |
|--------|-------|--------|----------|
| Item 1 | 220   | 1      |  $220    |
| Item 2 | 130   | 2      |  $260    |
| Item 3 | 17    | 4      |   $68    |
| Item 4 | 32    | 8      |  $256    |

For every security whose notional is above the desired amount, sell that many units:

Item 1: Sell 19/220 = 0.0863636363636364 units
Item 2: Sell 59/130 = 0.453846153846154 units
Item 4: Sell 55/32 = 1.71875 units

With the money you made from those sales, i.e. \$19 + \$59 + \$55 = \$133, buy 7.82352941176471 units of Item 3.

Now, you will have \$201 worth of each security, exactly 25% of the new portfolio size of of \$804.

The only time the extra \$100 would come in to play is if you are trying to minimize your transaction costs and/or if you are worried about not being able to trade at the spot etc.

With the extra \$100, you want to allocate \$226 to each security. So, buy 6/220 units of Item 1, buy 158/17 units of Item 3, and sell 34/130 units of Item 2 and 30/32 units of Item 4.

However, as far as I can see, you have not specified an optimization problem.

Let $c_i$ denote current units of security $i$ in your portfolio. Let's say you pay a percentage commission of $k$ per transaction. The amount you buy of security $i$ is denoted $x_i$ (negative $x_i$ mean selling). Your objective function is to minimize $\sum_i k p_i |x_i|$.

Since $k$ is a constant, this is equivalent to minimizing $\sum_i p_i|x_i|$ where $|x_i|$ is the absolute value of $x_i$.

This objective is subject to the portfolio allocation constraints:

$p_1(c_1 + x_1) = p_2(c_2 + x_2)$
$p_2(c_2 + x_2) = p_3(c_3 + x_3)$
$p_3(c_3 + x_3) = p_4(c_4 + x_4)$.

Further, the new value of your portfolio, $\sum_ip_i(c_i + x_i)$, plus the amount you spend, $k\sum_ip_i|x_i|$, must be affordable, i.e, must be less than or equal to $B + \sum_ip_ic_i$ which is the current value of your portfolio and the additional balance you have available.

This, of course, ignores borrowing money to finance the rebalancing which might be worthwhile depending on borrowing costs.

I am assuming there is going to be no short selling in a portfolio rebalancing, so $x_i>-c_i$ must also hold.

You might be able to simplify the problem, and possibly save some money, by first spending $B$ on underbought items.

You might be able to drop the absolute values by first deciding which stocks are overbought.

I did not prove the last two statements.

When I get a chance, I will post the solution to the applicable linear program.


Solve the online unweighted 0-1 knapsack problem efficiently

Well as you already noticed, or at least didn't mention, it is easy to see that there is no deterministic competitive Algorithm for your problem. (Counterexamples only need two items, and you can use the fact that the algorithm is deterministic.)
Your approach taking randomization actually isn't enough as some difficulties cannot be overcome by randomization. But there are a few relaxation models of your problem.
Some of those, and a few details to my answer can be found in the paper by Susanne Albers, Arindam Khan and Leon Ladewig named "Improved Online Algorithms for Knapsack and GAP in the Random Order Mode" (see section 1.1).


The DP-hardness of SAT-UNSAT is a direct consequence of the fact that SAT is NP-hard.

Suppose that $L \in \mathrm{DP}$. Then there exist languages $A \in \mathrm{NP}$ and $B \in \mathrm{coNP}$ such that $L = A \cap B$. Since SAT is NP-complete, there exists a polytime reduction $f$ such that $x \in A$ iff $f(x) \in \mathrm{SAT}$. Since UNSAT is coNP-complete, there exists a polytime reduction $g$ such that $x \in B$ iff $g(x) \in \mathrm{coSAT}$. You can check that the polytime reduction $h(x) = (f(x),g(x))$ satisfies $x \in L$ iff $h(x) \in \mathrm{SAT\text{-}UNSAT}$. This shows that SAT-UNSAT is DP-hard.

To complete the proof that SAT-UNSAT is DP-complete, you have to show that SAT-UNSAT is in DP. Presumably you already know how to do that.

Note that DP contains both SAT and UNSAT, and in particular differs from NP unless NP=coNP.


Can all $O(n)$ problems be solved without nested loops?

You can write an interpreter for any reasonable instruction set usin a single loop with a very, very long if/ else if / else if... statement. That should cover about all solvable problems. You can calculate the Ackerman function with one loop without recursion (not in the lifetime of the universe for n >= 4, but in principle).


Reduce set partition search to decision?

The standard approach works fine to reduce the problem size.  Given a "true" instance, $n$ elements which can be partitioned, you want to be able to reduce it to a smaller sized problem.  Grab any 2 elements, and combine them into one (having their sum as its size), and now you have an instance with $n-1$ elements.  If the answer to that instance is yes, great.  If it is no?  They must go into different partitions, which (effectively) adds their difference to whichever partition got the larger one.  Get rid of both, but add the difference as a new element.  In either case, you have $n-1$ elements in your new instance.


What is the meaning of idiosyncratic when refering to multiprocess abstractions?

Let me rephrase your quote:

  Implementations of multiprocessing in various systems tend to be rather different. Each system uses its own peculiar "vocabulary". When we port each such system to new hardware, we need to code afresh the entire multiprocessing subsystem. One way to address this difficulty is to come up with a small set of multiprocessing primitives which, on the one hand, can be used to implement all the multiprocessing mechanisms in known systems, and on the other hand, is simple enough to code for each particular hardware. This will drastically reduce the effort required in porting operating systems.


Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?

Try to combine the following two definitions:

A problem $\Pi$ is NP-hard if $\Pi' \propto_{\mathit{poly}} \Pi$ for every $\Pi'$ in NP.
A problem $\Pi$ is NP-complete if $\Pi$ is NP-hard and $\Pi$ is in NP.


Image registration algorithms for images with varying distances

Since you need to implement image registration for real-time your should have fast registration algorithm, such as differential total variation (DTV) or binary gradient angle descriptor. However, these methods implement for challenge dataset or multimodal in consideration of your images are mono-modal meanwhile these methods should work perfectly in your case.

Your algorithm should include these steps:

Image descriptor to extract the images features.
Feature selection: find the most similar features (this step is important to remove outliers which is common)
Minimise the distance between the related image features to get the optimal transformation.
Apply image transformation on the floating image.


Ordering the tasks to minimize penalties

Note the minimum penalty for a task is always $p_i d_i$.
If I choose at a point in time to do task $i$, then all other tasks $j$ will incur an extra penalty of $p_j d_i$.
Therefore, you need to do the most expensive task first (i.e., having the largest $p_i$). If there are multiple such tasks, then the one with the shortest $d_i$ needs to be performed first.


Define a grammar to emmulate chess rules

"The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid."

No, no, no, no, that's not how you check if a move is valid.

If you want all possible moves, then you generate all possible moves. If you want to check if a move is valid, then you check if that move is valid, and nothing else. There's no reason to know anything about all the other moves if all you want to know is to check if one move is valid.


No FSM/Regex exists for this language right?

Expanding on Daniel Martin's answer.
None of the following interpretations yields a regular language:

$L = \{ w \in \{a,b\}^*  : \exists n \ge 0,  \; w = a^n b^n \}$
$L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$.
$L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is equal than the number of $b$s in $w$.
$L$ contains all the words $w \in \{a,b\}^*$ such that there is a injective/bijective mapping that maps each a $a$ that appears in a generic position $i$ in $w$ with a $b$ in $w$ that appears in a position $j>i$.

The proof is the same for all cases: if $L$ was regular then,
for a sufficiently large $n$, the word $w = a^n b^n \in L$ could be written as $w = a^{n-k} a^k b^n$ (with $1 \le k \le n)$ in such a way that $a^{n-k}a^{k \cdot h} b^n \in L$ for all choices of $h \in \mathbb{N}$ (see pumping lemma for regular languages).
This is a contradiction since $a^{n-k}a^{2k} b^n = a^{n+k}b^{n} \not\in L$.


First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number of paths. In fact, it is likely way larger because each edge can be visited more than once.
However, there is another algorithm that can be applied to this non-negative edge-weight graph: Dijkstra's Algorithm.
To deal with the turbo charger, simply expand the graph such that each each state in your heap stores both the current weight and wether the charger has been used.


Find original array from array with pairs of adjacent elements

Use indegree or DFS:
    unordered_map<int, int> indegree;
    unordered_map<int, bool> visited;
    unordered_map<int, vector<int>> mp;
    for (auto& vect: adjacentPairs) {
        mp[vect[0]].push_back(vect[1]);
        mp[vect[1]].push_back(vect[0]);
        indegree[vect[0]]++;
        indegree[vect[1]]++;
    }
    int start = 0;
    for (auto& in : indegree)
        if (in.second == 1) {
            start = in.first;
            break;
        }
    }
    int n = indegree.size();
    vector<int> result;
    result.push_back(start);
    visited[start] = true;
    while (result.size() != n) {
        for (auto& val : mp[start]) {
            if (!visited[val]) {
                result.push_back(val);
                visited[val] = true;
                start = val;
            }
        }
    }

    return result;


Pierce's Types and Programming Languages : circular definition of terms?

Part of your intuition is correct: "terms" really means "the collection of terms generated thus far". I think you will also find in Pierce a definition that makes this explicit on the next page (Definition 3.2.3).

What Pierce is actually doing is giving three equivalent and common ways of presenting syntax. In fact, the first one (page 24) is what you often see in papers and programming language specifications. Definition 3.2.2 is a way of understanding this as an inductive set of rules. And Definition 3.2.3 is a way of understanding the inductive set of rules by explicitly building larger terms from smaller terms.


In a DAG, does there exist a sink for all vertices in the DAG?

A sink is a vertex with an out degree of zero. The leaf nodes of a binary search tree are the sinks. This is the trivial case of the statement as a path always exists from a node to itself, this path contains no edges, however the statement never said for vertex $v$, the sink $s$ could not be itself. Without this not only is the statment not true, but for every graph it is untrue since all DAGS have at least one sink and that sink could not be paired with another sink since that defeats the nature of a sinc.


Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B?

In order to explain this, you need to understand what is meant by "diagonalization argument".

In this context, we mean a proof that  only treats Turing machines as black boxes, i.e. only uses the fact that we can encode Turing machines as strings and treat them as inputs to other machines. This gives rise to the possibility of simulation, a machine $M$ can simulate some machine $M'$ without paying too much in space/time.

You can now observe that such proofs immediately generalize to the oracle model (encoding and simulation are possible), so if you could write such a proof for $A\neq B$, it would also work in the oracle model, showing $A^\mathcal{O}\neq B^{\mathcal{O}}$.

For further reading you could go to "Computational Complexity: A Modern Approach", by Arora & Barak. They have a section on limits of diagonalization.


Hint: Suppose $x$ is a leaf and $y$ is the unique neighbor of $x$. Show that there is always a minimum vertex cover which contains $y$. (Every vertex cover contains either $x$ or $y$; if it contains $x$, then replacing $x$ with $y$ we still get a vertex cover.)


The most obvious intuition comes from the notion of well pointed categories. A well pointed category is simply a category $\cal C$ in which the final object $1$ exists and is a generator for $\cal C$. This means that for every $f,g:A \rightarrow B$,
$$ f = g \ \Leftrightarrow \forall p:1\rightarrow A, f\circ p = g\circ p$$

Note that $\circ$ is composition and not application! In haskell you would define:

f `comp` g = \x -> f (g x)

In programmatic notation the definition of well-pointedness gives

f == g iff for all p : () -> A, f `comp` p == g `comp` p

or unfolding the definitions

f == g iff for all p : () -> A, \x:() -> f (p x) == \x:() -> g (p x)

if we assume that the only inhabitant of () is in fact () (which is not the case in haskell, btw), then we get

f == g iff for all p : () -> A, \_ -> f (p ()) == \_ -> g (p ())

assuming extentionality (functions are equal if they are equal on all arguments)

f == g iff for all p, f (p ()) == g (p ())

Now the crucial observation, is that in "reasonable" categories, like $\mathrm{Set}$, morphisms $1\rightarrow A$ can be identified with elements of $A$ which gives

f == g iff for all x : A, f x == g x

which is obviously true in $\mathrm{Set}$ (this is exactly extentionality). Now note that "elements of an object of $\cal C$" doesn't even make sense in a general category, where objects are just "things" that can have morphisms into or out of them.

So the notion of well-pointedness says 2 things:

It's reasonable to treat morphisms $1\rightarrow A$ as "elements" of the object $A$
Extensionality holds.

It's reasonable to generalize this notion by replacing the terminal object $1$ by some arbitrary object $K$.

Now it might be useful to see a category where this doesn't hold (i.e. a category that is not well-pointed) just to see where this intuition can fail.

The simplest example I know of is the category of groups and group morphisms $\mathrm{Grp}$. Here the terminal (and initial) object $1$ is the group $\{e\}$ with a single element $e$, which is the unit for that group, and the operation $e*e=e$.

Because group morphisms must send $e$ to $e_G$ (the unit of $G$), there is always exactly 1 morphism $1\rightarrow G$ for any group $G$, namely, $\phi(e)=e_G$.

But now take any 2 distinct morphisms $f,g:\mathbb{Z}\rightarrow \mathbb{Z}$, for example $f(n) = n$ and $g(n) = 2\cdot n$.

It's not true that $f = g$ iff $\forall p : 1\rightarrow \mathbb{Z}, f\circ p = g\circ p$. Indeed there is only one $p$, namely $\phi$ from above, and $f\circ \phi(e) = g\circ \phi(e) = e_{\mathbb{Z}} = 0$. But $f \neq g$!

So $\mathrm{Grp}$ is not well-pointed, and it's not useful to treat morphisms $1\rightarrow G$ as points of $G$. However, in this case, there happens to be a generating object $K\neq 1$, so the generalization is useful after all! I'll leave it as an exercise to figure out what $K$ is...

I'll try to answer the questions more directly.

  A morphism can be thought of as a a mapping from one type to another?

Sort of. It's a good intuition, but you shouldn't think that it always makes sense to talk about elements of type $A$, unless you're working in a well-pointed category as explained above..

  Morphism f is equivalent to morphism g if and only if for the morphism type K to type A

It's equal rather than equivalent (though computer scientists tend to define equality in a much stricter sense than category theorists, e.g. by syntactic equality).

Also, it's "if and only if for every morphism from K to A", in general you can have many morphisms in K -> A

  e applied to f is equivalent to e applied to g

Composition (written $\circ$) is not application! I've tried to break it down above.

  The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?

Category theory often offers very abstract definitions, and it's useful to work through examples and basic lemmas yourself to gain intuition.

However, if this helps, in the $\mathrm{Hask}$ category with types as objects and total programs of type A -> B as morphisms between A and B, the unit type () is a generator, as I tried to explain above.


I assume there are k piles and each pile can have stones in the range [0,n]. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of n be b. We take a 2-D array called dp of size $kx2^b$, where dp[i][j] denotes number of ways of assigning no. of stones to first $i$ piles such that xor of no. of stones in these first $i$ piles is $j$. It is easy to see that no. of losing positions is dp[k][0]. Now what's left is to come up with the recurrence relation ( I leave the base cases for you to come up with ).

           // take care of the base case
           for i in range 1 to k:
               for j in range 0 to 2^b:
                   dp[i][j] = 0
                   for m in range 0 to 2^b:
                       // first i piles have nim-sum j
                       // ... if first i-1 piles have nim-sum m in the last
                       // ... pile we keep (m xor j) stones
                       dp[i][j] = dp[i][j] + dp[i-1][m]

EDIT
If $k$ piles in total have $n$ stones , you can again solve it by dynamic programming , but this time keeping a 3-D dp array of size $k$x$2^b$x$n$, where dp[x][y][z] means number of arrangements of first x piles having in total z stones and the nim-sum being y. Although I point it out that this method would be feasible only for small values of $k$ and $n$ ( in the order of few  hundreds ). Following is a pseudo code ( again take care of base cases, if you have problem with them you could comment )

            // take care of base cases
            // our answer would be ( no. of losing ) positions = dp[k][0][n]

            for i in range 1 to k:
                for j in range 0 to 2^b:
                   for l in range 0 to n:
                      dp[i][j][l] = 0
                      for m in range 0 to l:
                            dp[i][j][l] = dp[i][j][l] + dp[i-1][m^j][l-m]

Clearly the above method works for small $k$ and $n$ ( you can reduce the memory, which I leave up to you to figure out ).


Computer Vision Techniques to find Slope of beach in the 2D Images?

As far as I understand you are trying to infer 3D position of the various points (i.e. height) on the beach using single monocular RGB camera.

I will try to give the best answer that with the CV knowledge that I have.

This is a difficult problem because you do not have the depth (distance from the camera) information, so you cannot infer full 3D structure from 2D image, i.e. the problem is ill-posed. Usually there are several other approaches that people do in order to extract 3D information:
1) having several cameras (e.g. stereo camera), then knowing the geometry of rig (its baseline), camera matrix one and doing disparity calculation one can find depth.
2) lidar, radar or other sensors that give depth directly. This information can either be fused to RGB camera or projected onto image space.
3) single monocular moving camera (can infer depth from structure-from-motion methods).

Additionally, one can perform monocular depth estimation but one would need:
1) to know camera matrix. In specific cases one can infer camera matrix (or some camera parameters) from parallel lines, circles or even from variability in focus, however in your case I don't see such artifacts.
2) depth map prediction algorithm (usually neural networks these days). There is lots of work on this, here's a sample paper one could start with. However, these methods do not understand the full 3d structure, they implicitly learn the relative size of objects and geometry of the scene, and of course you would need to devise a dataset for you task and train a neural net for that. And of course its depth accuracy will be much lower than the methods that I have described above.


Sort already sorted array - after changing several elements

Note the length of $S_1$ is no more than $\log_2n$, so the time you need to sort $S_x$ is $O(\log n\log\log n)$, which is $O(n)$.


3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^*\leq |E|$, hence this is a $\frac{3}{2}$ approximation.


The most efficient algorithm for computing cardinality of sumset

Use the FFT.  The characteristic vector of $A+B$ is the convolution of the characteristic vectors for $A$ and for $B$.  Convolutions can be computed efficiently using a FFT.  As long as every element of $A,B$ is not too large, this will be efficient: the running time will be approximately $O(n \lg n)$ if $A,B \subseteq \{1,2,\dots,n\}$.


What is the state of the art in encapsulated search in functional logic programming?

The reasons for using the IO monad appear to be described in Braßel and Huch and Hanus, 2004, but I cannot find a clear reason given for using a list instead of a set. I guess it is so the list can be elaborated lazily.

It seems that the approach described in the 2007 paper was unsatisfactory for some reason (I don't know why), because KiCS2 has gone back to the "API" described in the 2004 paper, i.e. using the IO monad. (There is an unsafe version which does not use the IO monad, but that is not referentially transparent!)


Yes, and with many different algorithms.

See https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

One important thing to notice is that the size of the input is the number of digits in the numbers, rather than the magnitude of the numbers (e.g. the "size" of the number 657 is 3, rather than 657, because it has 3 digits).


In this answer I assume given scores are pairwise didtinct. Note that the probability of two scores being equal is 0 since we have continuous probability. I think the same proof can be tweaked to span the case where two probabilities are equal but it will make it more complicated.

Let $p_1, \dots p_n$ be the set of employees sorted in descending order according to the outcome of the first task. Let $X_i$ be an indicator random variable, that the employee $p_i$ wins a prize. This means
$$X_i =
\begin{cases}
1&;\text{$p_i$ wins a prize,}\\
0&;\text{Otherwise.}
\end{cases}$$
Let $C$ be a random variable equals to the number of employees who win a prize. Note that $C = \sum\limits_{i=1}^{n} X_i$ and by linearity of expectation we get $E[C] = \sum\limits_{i=1}^{n}E[X_i]$. Moreover, note that the variables $X_i$ are mutually independent, since an employee $p_i$ wins a prize if and only if the score of $p_i$ in the second task is greater than the score of $p_j$ in the same task for all $j < i$.

It is easy to see that $$E[X_i] = Pr[X_i] = \frac{1}{i}$$ (think about the values of the scores the first $i$ employees get and the probability that the $i$th gets the highest of them). Now we can compute
 $$E[C] = \sum\limits_{i=1}^{n}E[X_i]= \sum\limits_{i=1}^n\frac{1}{i} = H_n \leq \ln n,$$
where $H_n$is the $n$th term of the harmonic series.

Now since we already discussed that the variables are independent, we can apply Chernoff bounds to prove that the probability, that the expected value is higher than a constant factor of $\ln n$ is very small and hence, with  high probability the expected value is not greater than a constant factor of $\ln n$.

Here is the extension about Chernoff bounds.

Chernoff bound: Let $\mu := E[C]$ and let $\delta < 2e - 1$ be a positive constant, the bound can be written as follows (see link):
$$Pr[C > (1+\delta)\mu] <
e^{-\mu\delta^2/4}.$$
Now set $\delta = 4$. We get
$$Pr[C > 5\lg n] < e^{-16/4\ln n} = \frac{1}{n^{4}}$$


Is there any relation between Global minimum cut problem and Maximal independent set?

Minimum cut can be computed efficiently (you haven't explained what global minimum cut is, but presumably it reduces to minimum $s$-$t$ cut). Minimum vertex cover (probably) cannot. So any connection would be rather indirect. Minimum cut is related to another quantity, maximum flow, which is defined more generally for weighted directed graphs. Both quantities are equal due to the fundamental max-flow min-cut theorem (sometimes known as the min-cut max-flow theorem).


Prove that $H$ reduces to $H\varepsilon$

This can be done by hard-coding a pre-processing stage to paste down $x$ to the input tape, before actually running $M$ on $x$ as input.

So given an instance $<M,x>$ of HALTING, you transform $M$ to $M_x$ that submerges the input $x$ into its initial stage. This can be done efficiently.

For example, if $x=010$, then start from the starting state $q$ of $M_x$ at left-marker $\$$, it moves one step to the right, and changes to state $q_0$. Then, $M_x$ prints out $0$, moves the head one step to the right and changes to state $q_1$. Then, $M_x$ prints out $1$, moves the head one step to the right and changes to state $q_2$. Then, $M_x$ prints out $0$, moves the head one step to the right and changes to state $q_3$. Then, $M_x$ moves all the way left back to the left-marker $\$$. Then, $M_x$ changes to the very starting state $q_M$ of $M$ and passes the control to $M$. Now, $M$ receives $x$ as input on the tape.

The above behavior of $M_x$ should be coded as its transition table. The description of $M_x$ is the produced instance of $H_\varepsilon$.

Finally, $M$ halts on $x$ iff. $M_x$ halts on $\varepsilon$.


Seeking "gold standard" to evaluate accuracy of network clustering algorithm

There are a couple of test sets mentioned in Stochastic blockmodels and community structure in networks by Karrer and Newman. One of them is the Karate Club Network, which is rather small, and the other is the Political Blog Network which is bigger. As far as I know, there is no gold-standard for testing clustering algorithms.


How to reduce the number of crossing edges in a diagram?

Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that.
The problem posed in the question is actually harder and more involved than the above. You are considering graph nodes of a certain size and shape while also bounding the size (area) of the result. In addition, a not yet determined notion of aesthetics is desired. Obviously we want a heuristic for this, which does not use the absolute minimum in the general case. The number of nodes encountered in such an application are likely not huge in the average case. Drawing the minimal edge crossing version of the graph may be feasible for small sizes.
Resources:
You may be interested in the following resources, particularly with the first:

The documentation for a feature of the Graphviz package presents an algorithm that generates nice looking directed graphs: http://www.graphviz.org/Documentation/TSE93.pdf
It has multiple other features that may prove useful. The source code is located on their website under EPL. It also includes a page dedicate to the theory behind graph visualization.
For a fixed-parameter algorithm check a paper by Martin Grohe:
Computing Crossing Numbers in Quadratic Time
A tech talk given by Amina Shabbeer at RPI:
Preserving Proximity Relations and Minimizing Edge-crossings in Graph Embeddings
An example of an efficient probabilistic algorithm can be found in this paper by Julia Chuzhoy:
An Algorithm for the Graph Crossing Number Problem

There are plenty of other resources, too. These should help you get started.
Additional Thoughts & Observations:
Here is an idea to get around the issues concerning the shape and size of nodes. Given the graph (infinitely small nodes), expand each node while "pushing" or bending edges out of the way (ex. using splines while enforcing a limit on proximity). You need to do this with other edges and nodes that get in the way of it, which can start a chain reaction. Look into how an equilibriums can be efficiently computed (ex. molecular structures). If you cant get the shape of a node to the desired size, then scale the whole diagram.
A user might enjoy the results of a randomized algorithm. They could use your feature multiple times until they got something they liked. Avoid redundant computation in this case (no need to compute a crossing number again).


Decidability of a set containing first symbols of elements of a decidable set

You probably have to twist your head a couple of times but $B$ is decidable and it does not depend on the decidability of $A$. Note that $B \subseteq \Sigma$, i.e. a subset of your finite alphabet. Thus, $B$ is finite and hence, it is decidable.

However, this reasoning is not constructive: It is just enumerating all functions $\Sigma \to \{0, 1\}$ (that are $2^{|\Sigma|}$, i.e. finitely many), which are all computable, and one of them is the correct function although you do not know which one.