Is every graph with minimum degree $n/2$ connected?

Suppose that $G$ is not connected. Consider the smallest connected component of $G$.

You take it from here.


Mean and median distance in unweighted graph

(This is not a full answer.)

The median distance is necessarily an integer [footnote 1].  Therefore, it might be possible to use an approximation algorithm for the median to compute the exact median, if the approximation is sufficiently precise.

Suppose the true median is $\xi$.  Then if we can efficiently compute a $1+1/3\xi$-approximation to the median, we can reconstruct the exact median from that.

I suspect it is possible to get a $\tau$-approximation to the median efficiently through random sampling.  In particular, consider the following procedure:

Repeat $k$ times: in the $i$th iteration, pick a random vertex $v_i$, compute single-source shortest paths from $v_i$ to every vertex, and find the distribution of these distances.
Aggregate these distributions and output the median of this aggregated distribution.

One might hope to get an approximation whose quality increases rapidly with $k$, and where if we want a constant approximation factor $\tau$, then a constant $k$ suffices.  I have no proof that this is possible, though.

We can consider a simpler situation, where given an integer $x$ we are trying to approximately count the fraction of distances that are at most $x$.  If the fraction of such distances is approximately $1/2$ (e.g., because $x$ is approximately the median), then one approach is random sampling: repeat $k$ times where we pick a random pair of vertices $u,v$ and compute the distance from $u$ to $v$ (say using BFS), then count what fraction of those $k$ distances are at most $x$.  The additive error is typically about $1/2\sqrt{k}$; it exceeds $c/\sqrt{k}$ with probability exponentially small in $c$ (it's basically the probability of a Gaussian being more than $2c$ standard deviations away from the mean).  Thus, we can get a $1+\epsilon$-approximation to this count using $O(1/\epsilon^2)$ iterations.  Each iteration takes at most $O(E)$ time, so with $O(E/\epsilon^2)$ time we can get a $1+\epsilon$-approximation to this count.  The probability that our approximation is wrong can be made exponentially small; an error probability of $1/2^{100}$ is so small as to be negligible in practice (e.g., it is smaller than the probability of a cosmic ray causing a bitflip error that causes an error in your code), and this will increase the running time by only a constant factor (say, 100, or something like that).  In this case it might be sufficient to also take $\epsilon$ to be a small constant.

Intuitively, it feels like if we can get a good approximation to this count, it might be possible to extend this to a good approximation to the median.  For instance, if we hypothesize that the median is $x$, we can count the fraction of distances that are $\le x-1$, the fraction that are $\le x$, and the fraction that are $\le x+1$.  If $x$ is indeed the median, hopefully the first fraction will be noticeably smaller than $1/2$ and the latter fraction will be noticeably larger than $1/2$.  I don't know how to turn this into an algorithm that I can prove will always work on all graphs, but I suspect this might work well enough in practice.

Computing the (exact) mean seems like it might be harder, as the mean isn't necessarily an integer.

Footnote 1: The median is either an integer or halfway between two integers.  In the latter case, the rest of the answer carries through if you divide everything by two.


Cutting equal sticks from different sticks

The first core observation to solving this problem is that the feasibility of a cutting length $l$,

$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl[\, \sum_{i=1}^n \Bigl\lfloor\frac{L_i}{l} \Bigr\rfloor \geq k \,\biggr]$,

is piecewise-constant, left-continuous and non-increasing in $l$. Since the number of necessary cuts behaves similarly, finding the optimal length is just

$\qquad\displaystyle l^{\star} = \max \{ l \mid \operatorname{Feasible}(l) \}$.

Furthermore, as the other answers have proposed, all jump discontinuities have the form $L_i/j$. This leaves us with a discrete, one-dimensional search problem amenable to binary search (after sorting a finite set of candidates).

Note furthermore that we only need to consider the $L_i$ that are shorter than the $k$-largest one, since that one is always feasible.

Then, different bounds on $j$ lead to algorithms of different efficiency.

$1 \leq j \leq k$ results in a search space of quadratic size (in $k$),
$1 \leq j \leq \lceil k/i \rceil$ in a linearithmic one (assuming the $L_i$ are sorted by decreasing size), and
slightly more involved bounds in a linear one.

Using this, we can solve the proposed problem in time $\Theta(n + k \log k)$ and space $\Theta(n + k)$.

One further observation is that the sum in $\mathrm{Feasible}$ grows in $l$ by $1$ for each candidate $L_i/j$ "passed", counting duplicates. Using this, we can use rank selection instead of binar search and obtain an algorithm that runs in time and space $\Theta(n)$, which is optimal.

Find the details in our article Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (by Reitzig and Wild, 2015).


Your intuition is correct in defining the two problems. In fact accepting also means halting but halting does not necessarily mean accepting (it could also reject).
Remember that when a Turing Machine is run on an input it can do three things: Accept, Reject, Loop Forever.
In the first two cases the machine stops, in the third obviously not.

As for decidability, note that both problems are the Halting Problem because the first case  implies a halting, even if it excludes the fact that
the arrest is due to reject, therefore they are both undecidable.


There is no standard definition for the XNOR of more than two inputs (indeed, nor is there a standard definition for less than two inputs). Since XNOR is associative, one possible definition is
$$
A_1 \text{ XNOR } A_2 \text{ XNOR } \cdots \text{ XNOR } A_n = A_1 \text{ XNOR } (A_2 \text{ XNOR } (A_3 \cdots )\cdots).
$$
Another reasonable definition defines the XNOR of $A_1,\ldots,A_n$ as the negation of the XOR of $A_1,\ldots,A_n$. Both definitions agree with the usual definition of XNOR when $n = 2$, or indeed when $n$ is even, but give complementary results when $n$ is odd.

The XOR of a given number of inputs is $1$ if the number of $1$s in the input is odd. Given that you can work out a similar formula for the XNOR of any number of inputs, under both definitions.


Upper bound on size of minimal binary coverage code

So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider $q$-ary binary codes of length $n$, such that $n \to \infty$ with $r/n \to p \in [0,(q-1)/q]$, then the minimal code size has the following asymptotic limit
$$
(1/n)\log_q N_{n,q}(r) \to 1-H_q(p),
$$
where $H_q(p)$ is the $q$-ary entropy of $p$. This answers my specific problem which corresponds to $q=2$.


Why are unbalanced partitions worse than balanced partitions in Quicksort?

for balanced partitions the work actually remains constant on all the steps

That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the current one.

You also seem to be missing that, for the total cost, you need to add up all the steps. Just saying, "the inputs get smaller", doesn't tell you anything besides that the algorithm terminates.

In the worst case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i-1) + i
\end{align*}$

which solves to some $T \in \Theta(n^2)$.

In the average case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= 2T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n \log n)$.

To stress my point from above, consider

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n)$.

Or

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i/2) + 1
\end{align*}$

which solves to some $T \in \Theta(\log n)$.

You see that the specifics of the recurrence matter.


It is not possible: -> is built into the underlying logic of Agda (and most dependently typed languages).

In particular, -> is not a type constructor, because it has binding properties. Because you can define things like (n : Nat) -> Vec A n, the compiler needs to add n to the variables in scope in the right hand side of the arrow, so this can't be done.

There are ways to cheat with bindings. For example, you can define $\exists x : T \ldotp S[x]$ as ex T (\x -> S), i.e. using a lambda to represent the binding. But, that lambda is typed using ->. Having dependent functions built in is the starter that bootstraps the rest of the type system. It's the only way the language can express quantification, so it ends up being critical.


Logic behind choosing the exponent bias as $2^7 -1$ instead of $2^7$ in $32$ bits IEEE-754 floating point representation

Jerome T. Coonen, "An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic," Computer, Vol. 13, No. 1, January 1980, pp. 68-79
provides the following rationale:

Because of the care taken in the treatment of Underflows, the range of
normalized numbers in single, double, and quad formats has been
chosen to diminish slightly the risk of Overflow compared with the
risk of Underflow. This was done by picking the exponent bias and
alignment of the binary point in the significant digit field in such a
way that the product of the largest and smallest positive normalized
numbers is roughly 4 in each of the basic formats.

David Stevenson, "A Proposed Standard for Binary Floating-Point Arithmetic," Computer, Vol. 14, No. 3, March 1981, pp. 51-62
provides a somewhat different but related reasoning:

For the 32-bit format, precision was deemed the most important
criterion, hence the choice of radix 2 instead of octal or
hexadecimal. Other characteristics include not representing the
leading significand bit in normalized numbers, a minimally acceptable
exponent range which uses eight bits, and an exponent bias which
allows the reciprocal of all normalized numbers to be represented
without overflow.

David Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic", ACM Computing Surveys, Vol. 23, No. 1, March 1991, pp. 5-48
combines the above two explanations as follows:

Referring to Table 1, single precision has emax = 127 and
emin= -126. The reason for having |emin| < emax is so that the reciprocal of the smallest number (1/2emin) will not overflow. Although it is
true that the reciprocal of the largest number will underflow,
underflow is usually less serious than overflow.


Symbolic Evaluation for Type Inference in a Dynamic Language

I am not sure you actually understand the terms you use here.

Symbolic execution has nothing to do with type inference

Symbolic execution is used for static analysis of programs, and is a special case of abstract interpretation. The symbolic executor provides an symbolic input value and traces the program execution given that symbolic input value.

Type inference is much simpler: it involves automatically deducing the type of programs. Nowhere is symbolic execution of the program involved.

Type inference is usually undecidable

For a dynamic typed language, type inference is not decidable. Moreover, even we have a static type system, type inference is usually still undecidable.

The only (?) type system we know of that has decidable type inference is the Hindley-Milner type system, i.e. System F with only Rank-1 types (plus a few conservative extensions). It is known that H-M can type imperative programs (such as Standard ML), as long as you can give good typing rules. When I was an undergraduate, we did an exercise in which we implemented H-M type inference for a restricted, strongly-typed version of Scheme (which was imperative). It was a lot of fun, but it also proves that
type inference is possible for imperative programs.

Update: oh, how could I have left out the canonical reference for polymorphic, inferable typing of imperative programs? The canonical reference would be Xavier Leroy's PhD thesis, Typage polymorphe d'un langage algorithmique (translated into English as Polymorphic typing of an algorithmic language).

I suggest that you start reading on Hindley-Milner and Algorithm W, as a first step (see, e.g., Chapter 22 of Types and Programming Languages by Benjamin C. Pierce). I also suggest that you do more basic reading and learning before asking on CS.SE, as that would make this site work much better. The theory of programming languages is not like coding and must be studied systematically if you want to have a solid grasp of it :-)


Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $4^2=2^2+2^2+2^2+2^2$. This is enough to construct a counterexample.

Let $S=\{1,2,3,4,5,6,7\}$ and $C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$.

There is no exact cover (the only way to get $4$ is to take $\{1,3,4,5,6,7\}$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.


One simple way is to fix a point $x$, compute the slope of the line $xy$ and store it in a hash table for every other point $y$. If there is a collision, then we have collinear points involving $x$. This takes $O(n)$ (if we assume hash table operations take $O(1)$). We then do this for every point $x$ in time $O(n^2)$.

Also if you are aware of the point-line duality (please refer to Artium's comment below), this reduces to checking the $n^2$ possible intersections of $n$ lines, but also makes use of hash tables.

Also it is open whether this can be done in sub-quadratic time as this problem is 3-SUM hard, please refer to this answer.


Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

A simple first step.

Consider any language $K \subseteq \{a,b\}^*$, and let $1,2$ be two new symbols. Let $L = 1\cdot \{a,b\}^* \cdot 2 \cup  2 \cdot  K \cdot 1$.

What if $1x2\in A(L)$?


How does RAMDAC get notified about framebuffer write?

It probably depends on the architecture in general, but bear in mind that the phrase "the conversion can be done while writing to the framebuffer" is quite vague. The important point is that generating the video signal is a hard real-time operation, and the graphics hardware is designed to ensure that it always happens, even if someone is trying to write to the framebuffer at the same time.

There are a few ways this could be achieved. Some possibilities include:

Reads and writes to the framebuffer might always happen at different times. If you consider a square wave clock, for example, writes could happen on the leading edge of the clock signal and reads could happen on the trailing edge. This way, the result of the write is always available when the read occurs.
If there is contention between a read and a write, the write could stall or be buffered somewhere.
Reads from the framebuffer to generate the video signal could be buffered in a FIFO or something like that. If a write occurs, it could be allowed to happen as long as the FIFO hasn't drained.

It's possible that there could (as you say) be some kind of bypass circuitry, similar to forwarding logic in CPUs. The input to the RAMDAC could be a multiplexer, with one input directly from framebuffer RAM and another from somewhere else.

I think this is unlikely, because it seems excessive to implement extra circuitry just to ensure that a write that is happening right now appears on this frame. A buffer or stall seems much more likely.


AFAIK, there is no standard with that format.

You can nevertheless try to imitate the old MIL-STD-1750A floating point format, which had two's complement mantissas and exponents.

The two's complement mantissa range is -1.0 to 0.999999....

Something like that :

                     Mantissa Exponent
'   0 =                  0000 0000
'0.25 =  0.5 * 2**-1 =   0100 1111
' 0.5 =   0.5 * 2**0 =   0100 0000
'  +1 =   0.5 * 2**1 =   0100 0001
'  +2 =   0.5 * 2**2 =   0100 0010
'  +4 =   0.5 * 2**3 =   0100 0011
'  -1 =  -1.0 * 2**0 =   1000 0000
'  -2 =  -1.0 * 2**1 =   1000 0001
'  -4 =  -1.0 * 2**2 =   1000 0010

Note the asymmetry between +1 and -1.

etc...


Minimizing the iterative sum of pairs of numbers in a list

I will assume that initially $y=0$, as this makes no difference in your problem.

Look at the very last two elements $a,b$ that you will apply your operation on:
The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$.

Notice that $a$  (resp. $b$) must have been obtained as a sum of some contiguous sequence of elements of your list starting from $x_1$ (resp. ending in $x_n$).

Calling $OPT[i,j]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $([x_1, \dots, x_j], 0)$, we then obtain (for $n > 1$):

$$
OPT[1,n] = \sum_{h=1}^n x_h + min_{h=1,\dots,n-1}  \left\{ OPT[1,h] + OPT[h+1,n] \right\}
$$

and, in general:

$$
OPT[i,j] =
\begin{cases}
\sum_{h=i}^j x_h + min_{h=i,\dots,j-1}  \left\{ OPT[i,h] + OPT[h+1,j] \right\} & \mbox{if } j-i>0 \\
0 & \mbox{if } j-i = 0
\end{cases}.
$$

There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.


Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows:

  The computational complexity of a sequence is to be measured by how fast
  a multitape Turing machine can print out the terms of the sequence.

Their first section, in which they prove (among else) a time-hierarchy theorem, is about "time-limited computations". They explicitly mention their concept of time:

  The machine operation is our basic unit of time.

The reference is to a multitape Turing machine, which they diligently define.

The intention here is to model the running time of algorithms using abstract machines, using number of steps as a proxy for time. Anticipating your criticism, they mention:

  Furthermore,
  the [complexity] classes are independent of time scale or of the speed of the components from
  which the machines could be built, as there is a "speed-up" theorem which
  states that $S_T = S_{kT}$ [i.e., $\mathsf{TIME}(T(n))$ = $\mathsf{TIME}(kT(n))$] for positive numbers $k$.

That is, multitape Turing machines can always be sped up by an arbitrary constant, and so there is no harm in associating number of steps with running time, since time complexity classes are "scale free".


State whether the language is in $R$, $RE$, etc. The intuition for the solution

The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that:

$L(M)^{\geq k} \in \text{RE}$, and
$\overline{HP}^{\geq k} \notin \text{RE}$.

So the language $L = \{ \langle M \rangle: \exists k: \ L(M)^{\geq k} = \overline{HP}^{\geq k}\}$ must be empty.

Formally speaking, we have the following claims:
Claim 1: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A \leq_m A \setminus B$.
Hint for the proof of claim 1: $B$ is finite and thus decidable. Therefore, given input $x$ for the reduction, we can check whether $x\in B$. Then you can proceed easily. Think where to map inputs $x$ from $B$, and where to map inputs $x$ from $\overline{B}$.
We also have the following similar claim which could be useful.
Claim 2: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A\setminus B \leq_m A $.
Given the above claims, we're done. Indeed, $\overline{HP} \notin \text{RE}$, and for every $k$, $\overline{HP}^{\geq k} = \overline{HP}\setminus \{w\in \overline{HP} : |w| < k\}$. That is, $\overline{HP}^{\geq k}$ equals a non-trivial infinite language minus a  finite subset, and so by claim 1, $\overline{HP}^{\geq k} \notin \text{RE}$. Also, it holds that $L(M)^{\geq k} \in RE$ for every machine $M$ (this is easy, you can prove that directly using standard closure properties and the fact that  $L(M)^{\geq k} = L(M)\setminus \{ w\in L(M): |w| < k\}$. Alternatively, you can use claim 2 but you have to be careful regarding the edge cases where $L(M)$ is trivial, etc.). Therefore, it cannot be the case that there is a machine $M$ with $L(M)^{\geq k} = \overline{HP}^{\geq k}$.


How do i make sure i get the correct Bellman Ford path?

From Wikipedia:

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

What is a shortest path? According to Wikipedia:

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Wikipedia isn't always a reliable source, but in this case the definitions are spot on. Suppose that $G=(V,E,w)$ is a weighted undirected graph. A path between two vertices $x,y \in V$ is a list
$$ v_0 = x, v_1, \ldots, v_\ell = y $$
such that $(v_i,v_{i+1}) \in E$ for all $i < \ell$ (possibly $\ell = 0$). The weight of the path is
$$ \sum_{i=0}^{\ell-1} w(v_i,v_{i+1}). $$
A shortest path between $x$ and $y$ is a path with minimum weight.
The Bellman–Ford algorithm finds the lengths of all shortest paths from a given vertex $x$ to all other vertices. It also generates auxiliary information which makes it possible to find the corresponding shortest paths.


prove sufficient number of comparisons for the merge problem

You asked about what approach to take, so I'll explain the general approach to take for this kind of problem.

The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for merging these two sequences, and prove that your algorithm uses no more than 5 comparisons (no matter what the input is).

So, here's the approach I'd suggest for you, as your next step.  Flesh out the algorithm that you have in mind.  You seem to have an idea in mind, but take it the rest of the way: actually write down some pseudocode.  Then, once you've written it down, try to analyze/upper-bound the number of comparisons your algorithm uses.  See if you can prove that it uses at most 5 comparisons.  (Try it on some example inputs if you need, to spot a pattern.)  If you have proven that it correctly merges the two subsequences and you have proven it will never use more than 5 comparisons, you've proven that 5 comparisons are enough.

On the other hand, if you can't prove that (maybe your algorithm might take more than 5 comparisons on some inputs), you can't conclude anything -- you'll need to keep trying to find another algorithm.


Is the intersection of two regular languages regular?

Summarizing the discussion, the intersection of two regular languages is always regular, and so "trivially decidable".


Meaning of topological distance between 2 pixels

Nonlinear Signal and Image Processing: Theory, Methods, and Applications defines topological distance as follows. First, you have to define when two pixels are neighbors. The book offers two possibilities:

The neighbors of a pixel are the 4 "cardinal" pixels around it.
The neighbors of a pixel are the 8 pixels surrounding it.

This defines a graph (two pixels are connected by an edge if they are neighbors). The topological distance between two pixels $p,q$ is then the graph distance between $p$ and $q$.

The first choice above corresponds to $L^1$ ("Manhattan") distance, and the second choice to $L^\infty$ distance. This contrasts with the usual $L^2$ (Euclidean) distance.


Maximizing sum of numbers within a sequence

I'll explain the Dynamic Programming approach to your problem using your sample sequence $[2,1,5,3,4]$. This approach is based on analysis of sub-problems - in your case each sub-problem is simply a task to find the maximal value (in the sense you described in your question) for some sub-sequence. These sub-problems are related to each other - this reducibility relation means that one sub-problem can be reduced to another one in a single step. For example, the sub-problem $[2,1,5,3,4]$ can be reduced to sub-problems $[2,5,3,4]$, $[2,1,3,4]$ and $[2,1,5,4]$ by removing a single number from the sequence.

The graph of sub-problems with this reducibility relationship is below. It's easy to see that our problem is equivalent to a problem of finding a path from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ (or vice versa), which will give us the maximal value for the vertex $[2,1,5,3,4]$ (see the path, marked by red color).

Not every problem can be solved by decomposition into sub-problems - such a problem must have Optimal Substructure for that. In our case it means that all the sub-problems along the optimal reducibility path must also have optimal solution. For example, the value of the vertex $[2,5,3,4]$ can be calculated along two paths, so we need to choose the maximal value (23) along the red path and forget about another path.

This local optimization is the reason why the Dynamic Programming method works so well for large problems. It often allows us to reduce exponential time complexity to polynomial one.

There are two ways to solve our problem using Dynamic Programming - "top-to-bottom" and "bottom-up". In our case they are equivalent to traversing our graph from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ or vice versa.

The top-to-bottom way involves developing a recursive function with two arguments - a sub-problem description (sub-sequence in our case), and mapping from the sub-problem description to the values space. This mapping will gather information about already solved sub-problems, so we will never solve the same problem again. The function will need to reduce (in one step!) the given sub-problem to all the possible sub-sub-problems and find the maximum of calculated values. Using such a mapping is often called Memoization.
The bottom-up way starts from the simplest sub-problem ($[2,4]$ with value = 0) and assigns values to all the sub-problems going up layer by layer, again maximizing the value of each sub-problem, calculated over its sub-sub-problems. Here we don't need recursion, however multiple nested loops will be needed, and it's not easy to program that correctly right away.

Now - it's your job to choose a way you want and solve your problem in general case.

ADDITION. We can make our graph oriented (each arc is oriented from top to bottom) and weighted (each arc weight is equal to the portion of value, given by its beginning) - then the described above "bottom-up" approach becomes equivalent to the Longest Path in Acyclical Digraph Problem.


Efficient way to calculate the maximum curvature of a cubic spline

Step 1: Express the points on the spline parametrically, so the spline is the set of points of the form $(x(t),y(t))$, where $t$ is a parameter.  Here $x(t)$ represents the $x$-coordinate (as a function of the parameter $t$) and $y(t)$ represents the $y$-coordinate.  Since this is a cubic spline, you can find functions $x(t),y(t)$ that are cubic polynomials with known coefficients that provide this parametric expression.

Step 2: Use the formula on Wikipedia for computing the curvature, given a parametric representation of the curve.  This gives you a formula for the curvature as a function of $t$, namely, $\kappa(t)$.  Note that since $x(t)$ and $y(t)$ are cubic polynomials, you can explicitly compute their first and second derivatives, so you can analytically compute an explicit expression for $\kappa(t)$, i.e., for the curvature as a function of $t$.

Step 3: Find the value of $t$ that maximizes $\kappa(t)$.  Note that we are now dealing with a function $\kappa : \mathbb{R} \to \mathbb{R}$, i.e., we are in the one-dimensional case. Thus, we can find the maximum numerically using any of a number of methods: gradient descent, Newton's method, or a number of other methods.

Alternatively, you can analytically compute the derivative of $\kappa(t)$, and then solve the equation $\kappa'(t)=0$ for $t$.  This might allow an analytic solution that identifies a list of candidate maxima of $\kappa(t)$.  Make sure to also check the endpoints (the lower and upper bounds for $t$).  Evaluate $\kappa$ at each candidate and pick the one that makes the value of $\kappa(t)$ as large as possible.


The article shows how to get a FA for the regexp 0 + 1: make a FA, $M_0$, for 0, make a FA, $M_1$, for 1, make a new start state state, $q_0$, and link it to the original start states of $M_0$ and $M_1$ with $\epsilon$-moves.

Then recognize that the regexp 0 + 1 + 2 is (0 + 1) + 2, so do the construction again, using the FA for 0 + 1 and the FA for 2. Rinse and repeat.


Fewest induced subgraphs of order <= k which cover every edge

Your problem is known as $k$-clique cover. Goldschmidt, Hochbaum, Hurkens and Yu describe several approximation algorithms in their paper Approximation algorithms for the $k$-clique covering problem. The paper is from 1995, so there are likely newer works on this topic, which you can find by scanning the papers citing this paper.


Compactly representing integers when allowed a multiplicative error

Storing $x$ to within a $1+\epsilon$ approximation can be done with $\lg \lg n - \lg(\epsilon) + O(1)$ bits.

Given an integer $x$, you can store $z = \text{Round}(\log_{1+\epsilon} x)$.  $z$ is in the range $\{0,1,\dots,\log_{1+\epsilon} n\}$, so requires about $b = \lg \log_{1+\epsilon} n$ bits.  Doing a bit of math, we find

$$b = \lg \frac{\lg n}{\lg(1+\epsilon)} = \lg \lg n - \lg \lg (1+\epsilon).$$

Now $\lg(1+\epsilon) = \log(1+\epsilon)/\log(2) \approx \epsilon/\log(2)$, by a Taylor series approximation.  Plugging in, we get

$$b = \lg \lg n - \lg(\epsilon) + \lg(\log(2)),$$

which yields the claimed answer.


Worst Case Space Complexity of Merge Sort and Bubble Sort

Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part.  This extra space is the reason for the O(n) space complexity.

During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space.

int leftPartition[] = new int[ leftPartitionSize ];
int rightPartition[] = new int[ rightPartitionSize ];

So, merge sort uses auxiliary arrays to sort.  However, quick sort is an in-place sort that uses O(1) space as no auxiliary space is required to sort the data.

Side note:  You might also see the space complexity of merge sort as O(nlog(n)).  Some would argue that because of the way the recursive calls to merge sort work, the space complexly at any given point is at most O(n).  Others might say that adding all the space for all recursive calls requiresO(nlog(n)).  The log(n) is because each repeated call to merge sort cuts the existing array in half.

If you want true O(n) complexity, you can pass an auxiliary array as a parameter into the sort method.  Therefore, each call to merge sort will use the same array without the need to split the array in half with each call.   However, this implementation is quite a bit harder to implement.


Binomial trees in binomial heap with 27 elements

A binomial heap stores a collection of binomial trees whose sizes are powers of two and such that there is at most one tree for each size.

How can you write 27 as a sum of distinct powers of 2? How many powers do you need?


It's open whether $\mathsf{DSPACE}(\log n) = \mathsf{NSPACE}(\log n)$, which is the $\mathsf{L}=\mathsf{NL}$ question. As far as I know, the closest thing we can say are theorems by Savitch $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2)$ and Immerman–Szelepcsényi's ($\mathsf{NSPACE}$ is closed under complement).

Also see AndrewK's answer regarding the subset symbol, I think this is the issue here.


Limited sort: is this a well-known problem?

I think absolutely minimising the number of inversions makes this very hard. If you just say "I want an array that is a bit better sorted, without moving any item by more than n positions": Fill a heap with the first n+1 array elements. Then remove the smallest element in the heap and put it into the first array position, unless there is an array element in the heap that would end up moving too far. Add the next array element to the heap and repeat. Obviously stop adding elements to the heap when you run out of elements.

This will find [0, 1, 4, 2, 3] in your example.


Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable

Here is a proof sketch. We will show that the given formula is unsatisfiable iff there exists a cycle containing both $x$ and $\lnot x$, for some variable $x$.

Suppose first that there exists a cycle containing both $x$ and $\lnot x$. The existence of a path $x \to^* y$ in the implication graph means that in a satisfying assignment, if $x$ holds then so does $y$ (you can prove it by induction on the length of the path). Since there is a cycle containing both $x$ and $\lnot x$, there are paths $x \to^* \lnot x$ and $\lnot x \to^* x$. In any satisfying assignment, either $x$ or $\lnot x$ holds, and both cases lead to contradiction.

Suppose next that there are no cycles containing both $x$ and $\lnot x$. We will construct a satisfying assignment as follows. Choose some variable $x$. If there is a path $x \to^* \lnot x$, assign $x = F$, and for each literal $\ell$ such that $\lnot x \to^* \ell$, assign the value to the underlying variable which makes $\ell$ true. You cannot be assigning the same variable two different truth values, since if $\lnot x \to^* y$ and $\lnot x \to^* \lnot y$ then also $y \to^* x$ and so also $\lnot x \to^* x$, completing a cycle involving $x$ and $\lnot x$.

If there is a path $\lnot x \to^* x$, assign $x = T$, and continue analogously.

If neither of these paths exist, assign $x$ arbitrarily, and continue as before. This cannot lead to a contradiction, for the following reason. Suppose that we assign $x = F$, and that there are paths $x \to^* y$ and $x \to^* \lnot y$. Then there is also a path $y \to^* \lnot x$ and so a path $x \to^* \lnot x$, contradicting the assumption that none of the two paths exists.

If after this process there is some unassigned variable left, choose one of them, and repeat until the assignment covers all variables.


Finding the minimum value of all subsets in a 2D array

In one dimension, looking for the maximum sum, this is solved by Kadane's algorithm. The referenced page does discuss some of the history and gives pointers to efficient solutions for the two-dimensional problem.
Bentley in his seventh "Programming Pearls" column (see e.g. here) discusses the one-dimensional problem in depth, devising ever more efficient algorithms for it's solution. Bentley's columns (and much more) are collected in his book "Programming Pearls" (Addison-Wesley, 2nd edition 1999).


Unknown notation "$e^T$" in a machine learning paper

The superscript $T$ is the transpose operation. The vector $e$ is probably the constant one vector, though this is not standard notation and so it would be mentioned in the definitions part of the paper. Overall, $e^T\alpha = \langle e,\alpha \rangle = \sum_i \alpha_i$.


Given an array of size n, create a sub array with given conditions using dynamic programming

In other words, the procedure produces two subsequences of the given array such that

the only shared element between the two is their first elements
one of them is non-decreasing.
one of them is non-increasing.

Let the given array be $a[0], a[1], \cdots, a[n-1]$. Here are the subproblems. $DP[i][j][[k]$ is the maximal number of elements in any such two subsequences such that their shared element is $a[i]$, the non-decreasing sequence ends at $a[j]$ and the non-increasing sequence ends at $a[k]$. Here $0\le i$, $i\le j\lt n$ , $i\le k\lt n$ and, unless $i=j=k$, $j\not=k$.

The wanted number is the maximum of all $DP[i][j][k]$.

The base cases are $DP[i][i][i]=1$, where $0\le i\lt n$.

What is the recurrence relation? $DP[i][j][k]$ is, basically, the larger of the following two numbers.

the maximum of $DP[i][\ell][k] + 1$ for all $\ell$ such that $i\le\ell\lt j$, $a[\ell]\le a[j]$.
the maximum of $DP[i][j][\ell] + 1$ for all $\ell$ such that $i\le\ell\lt k$, $a[\ell]\ge a[k]$.

How will we fill the 3-dimensional table $DP[i][j][k]$? Roughly, for a fixed $i$, we will find

$DP[i][i][i] = 1$,
then $DP[i][i][i+1]$ and $DP[i][i+1][i]$,
then $DP[i][i][i+2]$, (not including $DP[i][i+1][i+1]$ since $i+1 = i+1$) and $DP[i][i][i+2]$,
$\cdots$,
Finally, $DP[i][n-2][n-1]$ and $DP[i][n-1][n-2]$ (there is no $DP[i][n-1][n-1]$ for $i\not=n-1$ and $DP[n-1][n-1][n-1]=1$ is not helpful.)


Find all substrings that fit the mask with asterisks

Yes, there is a more efficient algorithm.  Your algorithm can take exponential time.

You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the length of mask, and find all matches in $O(n^2m)$ time.  I'll show two solutions, one using dynamic programming and one using graph search.  You can pick whichever you find easier to understand.

I don't know whether you can do even better.

Dynamic programming

Build an array $A[i,j]$, where $A[i,j]$ is true if some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$.  There's a recursive formula for $A[i,j]$:

$$\begin{align*}
A[i,j] &= \text{True} \qquad &&\text{if } j=m+1\\
A[i,j] &= A[i+1,j+1] \qquad &&\text{if } \text{mask}[j]=\text{text}[i]\\
A[i,j] &= A[i,j+1] \lor \cdots \lor A[n,j+1] \qquad &&\text{if } \text{mask}[j]=*\\
A[i,j] &= \text{False} \qquad &&\text{otherwise}
\end{align*}$$

If you fill this in, in the usual way, you get a $O(nm^2)$ time algorithm.  If you additionally keep track of $B[i,j] = A[i,j+1] \lor \cdots \lor A[n,j+1]$ and fill in entries in the right order, you get a $O(nm)$ time algorithm.

Once you have filled in the matrix, you can find all substrings of text that match: each entry $A[i,1]$ that is true corresponds to one or more substrings of text that match (the substring starts at index $i$ of text).  You can adapt the above algorithm to enumerate all those matching substrings by repeating the above computation once per possible ending place of the match.

There may be even faster methods, using ideas from string matching and/or regular expression matching.

Graph search

Build a directed graph on $nm$ vertices.  Each vertex is of the form $\langle i,j \rangle$, which we think of as corresponding to the problem of checking whether some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$.  Now add the following edges:

Add the edge $\langle i,j \rangle \to \langle i+1,j+1 \rangle$ if mask$[j]$ = text$[i]$.
Add the edge $\langle i,j \rangle \to \langle i,j' \rangle$ if mask$[j] = *$ and $j' > j$.

Finally, mark each vertex $\langle i,m+1 \rangle$ as "accepting".

This is a directed acyclic graph; it has no cycles.  Now, for each $i$, find all accepting vertices that are reachable by some path starting at the vertex $\langle i,1 \rangle$.  If $\langle i',m+1 \rangle$ is reachable from $\langle i,1 \rangle$, that means that the substring text$[i..i'-1]$ matches mask, so you can output this substring.   This computation can be done in $O(nm)$ time per starting point using breadth-first search, for a total of $O(n^2m)$ time.


Does a non deterministic Turing machine which is a decider halt on all branches for all inputs?

You can define it either way.  The simple way to  define it is to say that every branch must halt for every input.  Alternatively, you can say that, if the input is in the language, at least one branch must accept, so you don't care if the others reject or just fail to halt; if the input is not in the language, then every branch must reject.

Both in terms of computability and complexity, you can show that the two definitions are completely equivalent.


Why did Apple include dedicated a neural network "processor" in standard consumer products?

Having a powerful machine learning chip in your device allows you to do things that you probably have not thought of. Things like improving the images that your camera is taking. Cutting out the background and replacing it with a boring beige background, very valuable if you are in a video conference and want to show your face to people but not your home.
Or a nice one: Most people in a video conference look at the screen, not at the camera, so when their image is transmitted, it seems that you can't look in the other persons eyes. Very nice if you have an ML chip how can change the image as if you were looking straight into the camera, without taxing your battery.
Something not done (yet) would be improving sound quality, for example removing background noise and filling in gaps when sound transmission fails, and totally cool would be removing people's accents, so that I can understand someone with a strong Scottish or Indian accent without problems.
You are about in the same situation as someone in the early 1980's asking what the advantages of a graphical user interface would be.


How many random walks to start from each node?

If you consider given graph as a Markov chain, you can compute the steady-state distribution. With it, you can compute the mean-reccurence time $M_j$ (expected time to return to the starting node). See Mean recurrence time

$\pi_j=1/M_j$

If for some node $n_j$, the probability of going to each neighbour is equal to $1/out\_deg(n_j)$, then you can compute $\pi_j$ in constant time.

This does not assume, you stop after three steps (why do you actually need this?). From here you could do some experiments with damping factor $d$. Damping factor $d$ is the probability you end the walk at each step. Damping factor You can combine these two aproaches to get to your estimate.

-edit-

So here goes. Given an undirected graph $G=(V,E)$ you can find the stationary distribution of the corresponding Markov chain $M$ with transition matrix $P$ as follows:

$\pi_i=deg(v_i)/|E|$

where $deg(v_i)$ is the degree of vertex $i$, $|E|$ is the number of all edges in graph $G$ and $\pi_i$ is the $i$-th component of vector that satisfies:

$\lim_{k->\infty} P^k=1\pi$

Note that $\pi$ is unique if the Markov chain is irreducible and aperiodic.

Irreducibility essentially means, you can get from every vertex $i$ to every vertex $j$. If the graph is not connected, you can use the same approach on the connected components of the graph.
Aperiodicity means that greatest common divisor of cylce lengths in the Markov chain. This means that if you have at least one paper which was written by three authors (in one component), the condition is trivially satisfied.

Mean recurrence time is the computed by the formula above.


"Greater than AND smaller than" condition in integer linear program with a binary variable

Thanks MrHug, I should have thought of this myself after your first hint.

after using the solution from here twice with the resulting binaries $A_1$ and $A_2$ we can form another problem:
$$A = \begin{cases} 1 & \text{if } A_1+A_2 \geq 2 \\ 0 & \text{otherwise}\end{cases}$$

This one can be solved with a little hint from there:

$$A_1 + A_2 \geq 2 - M * (1-A) \\
2 - \epsilon \geq A_1 + A_2 - M * A$$

where $M$ is a big value and $\epsilon$ is a very small value (above 0, below 1).

It's a bit unfortunate that so many variables are needed as $A$, $A_1$ and $A_2$ are cubic in my case. But I'm glad about this solution.


Selection over combinatorics that satisfies a distribution

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the elements in the ground-set. It is an NP-complete problem and since it is a special case of your problem, your problem is NP-complete as well (it is clearly in NP since an NTM can guess all possible tuples of $l$ subsets and accept if the union of subsets in any of the guessed tuples covers the ground-set). So You should not expect a polynomial answer.

On the other hand, an exponential trivial solution would be to try packing all sets of $l$ subsets which are at most $n \choose l$ and try for each of them if they satisfy all the constraints in $O(l \cdot r)$ where $r$ is the number of the constraints. This totals in an $O(n^{l+1}r)$. There are a lot of improvements on this running time I think but you should not expect something sub-exponential.


Strong Uniform Total Order vs Weak Uniform Total Order

Consider for example two processes $p_1$ and $p_2$, with $p_1$ that delivers in this order $m$ and then $m'$.
In SUTO, $p_2$ will either deliver $m-m'$ as $p_1$ did, or it won't deliver $m'$ at all.
But why?
Because if $p_2$ will deliver, for example, $m - m'' - m'$, then every process can deliver $m'$ only after $m''$.
This means that once $p_1$ and $p_2$ don't deliver the same messages, the  following  messages delivered by $p_1$ and $p_2$ must be disjoint.
In WUTO instead it's possible to have $p_1$ that delivers $m - m'$ and $p_2$ that delivers $m - m'' - m'$.
This example is taken from Baldoni, Cimmino and Marchetti, A classification of total order specifications and its application to fixed sequencer-based implementations.


Sampling maximal shortest paths in a graph?

Non-maximal paths are prefixes or suffixes of shortest paths

So a maximal path is just a path that begins at a vertex $u$ with no in-edge and ends at a vertex $v$ with no out-edge.

It's straightforward to see that if a shortest path $P$ from $u$ to $v$ is a subpath of some shortest path $Q$ from $x$ to $y$, then $P$ is also a subpath of a shortest path $R$ from $x$ to $v$, and a subpath of a shortest path $S$ from $u$ to $y$.  Thus the following statements are equivalent:

$P$ is not maximal;
There exists a shortest path $Q \ne P$ that contains $P$ as a subpath;
There exists a shortest path $X \ne P$ that contains $P$ as a subpath, is longer than $P$ and either begins at $u$ or ends at $v$.

(1) and (2) are equivalent by definition; (2) follows from (3) trivially; (3) follows from (2) by the reasoning above and the fact that, since $Q \ne P$, at least one of $R$ and $S$ must be longer than $P$ and end at one of $P$'s two endpoints; $X$ can be whichever one this is.  We will use (3) to efficiently determine whether a given shortest path is maximal.

Maximality is determined by endpoints and length

If some shortest path from $u$ to $v$ could be extended to a longer shortest path, then all shortest paths from $u$ to $v$ could be so extended -- since the only property we care about is the length, and that doesn't change.  So the question of whether a given path $P$ from $u$ to $v$ is maximal is entirely determined by the length of $P$, and its start and end points $u$ and $v$ -- it is not necessary to know what specific internal vertices $P$ uses.  Thus, for any pair of vertices $(u, v)$, we can determine in a preprocessing step whether this vertex pair is "maxable"; a path $P = (u, \dots, v)$ is then maximal exactly when the pair $(u, v)$ is maxable and $P$ has length equal to the distance between $u$ and $v$.

The idea is to build a complete list of all maxable pairs $(u, v)$ and the number $n_{uv}$ of shortest paths between them.  Once these are known, paths can be uniformly sampled using a simple recursive procedure.

Determining maxable pairs

Let $A$ be the set of all vertex pairs $(u, v)$ such that $v$ is reachable from $u$.  This can easily be determined in $O(n^2+nm)$ time by starting a DFS from each vertex in turn.

We determine the set of maxable pairs by initially declaring that every vertex pair $(u, v)$ such that $v$ is reachable from $u$ is maxable; we then "cross out" all pairs $(u, v)$ for which some shortest path from $u$ to some $x$ has a shortest path from $u$ to $v$ as an initial subpath; finally, we "cross out" all pairs $(u, v)$ for which some shortest path from some $x$ to $v$ has a shortest path from $u$ to $v$ as a final subpath.  By (3) above, all pairs $(u, v)$ that have not been crossed out are maxable.

I'll now describe the first "crossing out" step.  The second is identical, except that we first reverse all edge directions, and when we are about to cross out some pair $(u, v)$, we instead cross out $(v, u)$.  The following assumes an unweighted graph; if the edges are weighted, you can replace the BFS with Dijkstra's algorithm.

From each vertex $u$ in turn, perform BFS on $G$, using $u$ as the root.  For each vertex $v$ visited at level $L$ during a particular BFS, if $v$ is adjacent (in $G$) to any vertex on level $L+1$ of the BFS tree, cross out the pair $(u, v)$.  This is because the paths in $G$ whose vertices start at the root $u$ of a BFS tree and thereafter occupy strictly increasing levels in that tree are exactly the shortest paths starting at $u$, and the "downward" (w.r.t. the BFS tree) edge leaving $v$ indicates that there is some $x$ for which a shortest path from $u$ to $x$ uses a shortest path from $u$ to $v$ as a subpath.  This can be performed in $O(n+m)$ time per root vertex, for $O(n^2+nm)$ time overall.

Let $Z$ be the set of maxable vertex pairs that remain after the above has run.

Counting shortest paths

As a further preprocessing step, we would like to count the number of shortest paths between any pair of vertices $(u, v)$.

For any vertex $u$, the number of shortest paths from $u$ to every other vertex $v$ can be calculated in $O(n+m)$ time with BFS.  This means that the total time needed to compute the number of paths between every pair $(u, v)$ of vertices is $O(n^2+nm)$.  Let $n_{uv}$ be the number of paths from $u$ to $v$.  Discard any pairs $(u, v)$ for which $n_{uv} = 0$, i.e., for which $v$ is not reachable from $u$.

Let $n_z = \Sigma_{(u, v) \in Z} n_{uv}$.

Sampling algorithm

The input is a graph $G$.  If $G$ has no vertices, return an empty path.  (This will arise as a base case later on.)  If it has at least one vertex then it has at least one maximal path (even if that consists of a single vertex).

The next step is to choose a start and an end vertex for the path.  This works differently depending on whether we are at the top level of the call stack or not:

If we are at the top level of the call stack, choose an endpoint pair $(u, v)$ from $Z$ at random with probability $n_{uv}/n_z$; otherwise
Let $n = \Sigma_{(u, v) \in A \cap (V(G)\times V(G))} n_{uv}$.  Choose an endpoint pair $(u, v)$ from $Y$ at random with probability $n_{uv}/n$.

These probabilities ensure that paths are chosen uniformly at random; if you want to weight paths in some other way, you are of course welcome to push these probabilities around.  $u$ will be the first vertex in your random path, and $v$ will be the last.  If $u = v$ then we are done: return the single-vertex path $u$.

Otherwise, construct a subproblem to recurse on: this is the induced subgraph $G'$ of $G$ whose vertex set is the intersection of $X$ and $Y$, where $X$ is all vertices in $G$ that are reachable from a child of $u$, and $Y$ is all vertices in $G$ that $v$ is reachable from, except for $v$ itself.  Recurse on this subproblem; it will produce a (possibly empty) path $P$.  Return the path $u, P, v$.

Note that whenever two vertices $u$ and $v$ still remain in $G'$, the number of paths between them $n_{uv}$ also remains unchanged -- so it's not necessary to recalculate these for each subproblem.  $X$ and $Y$ can each be found using DFS in $O(n+m)$ time, intersected in $O(n\log n)$ time (sort each list, if necessary, then use a $O(n)$ list merge) and the edges of $G$ that remain in $G'$ found in $O(m)$ time.  Each recursion level shrinks the graph by at least 2 vertices, so there are at most $O(n)$ recursive calls.  Thus the overall time complexity for sampling is $O(n(n + m + n\log n)) = O(n^2\log n + mn)$.


Proving that a program is "thread safe" is hard.  It is possible, however, to concretely and formally define the term "data race."   And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace.  This type of analysis goes back at least to 1988:  Barton P. Miller, Jong-Deok Choi, "A Mechanism for Efficient Debugging of Parallel Programs", Conf. on Prog. Lang. Dsgn. and Impl. (PLDI-1988):135-144.

Given a trace of an execution we first define a happens-before partial-order between events in the trace.  Given two events $a$ and $b$ that occur on the same thread then $a < b$ or $b < a$.  (The events on the same thread form a total order given by the sequential semantics of the programming language.)  Synchronization events (these could be mutex acquires and releases, for example), give an additional inter-thread happens-before partial order.  (If thread $S$ releases a mutex and then thread $T$ acquires that mutex we say that the release happens-before the acquire.)

Then given two data accesses (reads or writes to variables that are not synchronization variables) $a$ and $b$ that are to the same memory location, but by different threads and where either $a$ or $b$ is a write operation we say that there is a data-race between $a$ and $b$ if neither $a < b$ nor $b < a$.

The C++11 standard is a good example.  (The relevant section is 1.10 in the draft specs that are available online.)  C++11 distinguishes between synchronization objects (mutexes, and variables declared with an atomic<> type) and all other data.  The C++11 spec says that the programmer can reason about the data accesses on a trace of a multithreaded program as if it were sequentially consistent if the data accesses are all data-race free.

The Helgrind tool (part of Valgrind) performs this kind of happens-before based data-raced detection as do several commercial tools (e.g., Intel Inspector XE.)  The algorithms in modern tools are based on keeping vector clocks associated with every thread and synchronization object.  I think this technique of using vector clocks for data-race detection was pioneered by Michiel Ronsse; Koen De Bosschere: "RecPlay: a fully integrated practical record/replay system", ACM Trans. Comput. Syst. 17(2):133-152, 1999.


Decision problem that can be verified but not run in n^2 time

The answer depends a lot on the model of computation.

On one extreme: in the decision tree model, many lower bounds can be proven.  For instance, consider the 3SUM problem.  You can verify an alleged solution to the 3SUM problem in $O(n)$ time, but it's conjectured that no algorithm can solve the 3SUM problem in $O(n^{2-\epsilon})$ time for any $\epsilon>0$.  One can prove this holds in some version of the algebraic decision tree model; one can prove that any algorithm to solve it in this model must take $\Omega(n^2)$ time.  This provides a gap of $O(n^2)$ vs $O(n)$ for solving vs verifying solutions, if the verifier is limited to the algebraic decision tree model.  This is a pretty limited result; in this case, the model means that we're restricting attention to algorithms of a particular form.  So, it doesn't rule out the possibility of some other algorithm (that does something weird) being faster.

On the other extreme: if we allow arbitrary (non-uniform) boolean circuits, then there is no explicitly stated function $f$ on $n$ bits where we can currently prove that every circuit for computing $f$ needs $\ge 3.1n$ gates.  In other words, this is saying that we have no clue how to prove lower bounds for circuits.  Roughly speaking, we have no known result of a problem where we can prove that solving it requires circuits of size $\omega(n)$.  See, e.g., https://cstheory.stackexchange.com/a/8005/5038 and https://cstheory.stackexchange.com/q/21400/5038.  So, given our current state of knowledge, we have no hope of proving a result like that if the model of computation is unrestricted boolean circuits.


Achieving better than the theoretical False Positive Rate for Bloom Filters

Your question includes the equation

$$
(1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k}
$$

But that is not actually an equation; it is only an approximation.


Proof: Sum of weights of paths in a network

A few hints:

Find out what the entries of $A^2$ mean. How about $A^k$? (Start by a very small adjacency matrix, multiply it with itself and try to think what each entry means).
Lookup and understand the Taylor expansion of $f(x) = 1/(1-x)$.
Realize that the sum of weights of all paths from $s$ to $t$ is the sum of weights of paths of length 0, 1, 2, ...


Prove that the language is not regular through Myhill-Nerode Equivalence

You have to find an infinite set of strings $s_i$ such that for every two strings $s_i ≠ s_j$, there is a string $t_{ij}$ such that exactly one of $s_i t_{ij}$ and $s_j t_{ij}$ is in the language, and the other is not.
Now if you look at $a^n$ and $a^m$, n ≠ m, can you find a string t such that exactly one of $a^n t$ and $a^m t$ is in the language, and the other is not?


Algorithm Request: "Shortest non-existing substring over given alphabet"

Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M*. From that you
build a trie, which may be understood as a tree structured FA that
recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which
there is no arc for a given character in M, you have your answer which
is the string associated with that node concatenated with the missing
character.  Complexity is $O(n^2)$ where $n$ is the length of the
string S, because that is the maximum number of characters you may have to consider while building the trie.

Note regarding complexity: In the trie construction you have to
consider only the longest substring in $M^*$ starting at each position
in $S$, since shorter ones are automatically taken care of. Each state
thus created is an accepting state recognizing one substring. There
are at most $n$ substrings in $M^*$, each having at most $n$ characters. Each is considered in constant time.


Converting decision problems to grammars?

Yes, every decision problem can be converted into a grammar that generates exactly the "yes"-instances of the problem.

And no, even if the problem is decidable, there is not necessarily a context-sensitive (let alone a context-free) grammar. An example would be the equivalence problem for regular expressions with exponentiation. (reference)


No, this proof is not correct.

To prove that a language is non-regular using the pumping lemma, you need to show that:

for all $m>0$, there is a string $w\in L$ of length at least $m$ such that
for all ways of writing $w=xyz$ with $|y|\geq 1$,
there is some $i\geq 0$ such that $xy^iz\notin L$.

You have shown that some way of writing $w=xyz$ makes part 3 true, but that is not enough.

To understand why, it's helpful to consider why the pumping lemma is true. The point is that, if a language is regular, it is accepted by a DFA and that DFA has some number $n$ of states. That means that, if it reads a string $w$ of length more than $n$ then, by the pigeonhole principle, it must enter some state $q$ twice (or more).  Then we can set $w=xyz$ where

$x$ is what is read before entering $q$ for the first time ($x=\varepsilon$ if $q$ is the initial state);
$y$ is what is read after the character that causes the first entry to $q$ up to, but not including, the character that causes the second entry to $q$ (so $y$ contains at least one character, i.e., $|y|\geq 1$);
$z$ is the rest of the string.

Now the point is that the string $xy^iz$ causes the DFA to go around the loop from $q$ to $q$ $i$ times, then carry on to an accepting state by reading $z$, so every string $xy^iz$ must also be accepted. However, the specific partition of $w$ into $x$, $y$ and $z$ depends on which automaton you're considering. To show that no automaton accepts the language, you need to show that every possible automaton fails, which means you need to show that all possible partitions $w=xyz$ fail.


Advantages (from a mathematical perspective) of representing data as symmetric matrices

The main advantages of matrices are in solving linear equations. In fact judging whether there even exists solutions to a system of equations becomes very easy when you represent equations in form of matrices. Matrices form the core of Linear Algebra.

Systems of linear equations pop up everywhere in the real world. Linear Algebra is integral to Machine Learning, Image processing, Computer Graphics, Operations Research.....( the list is inexhaustible).

Using matrices as representation of graphs is in fact one of the less useful facets of Linear Algebra (due to the more space efficient Adjacency List data structures). If we talk about using matrices as datastructures you can look into Bottom Up approach of solving dynamic programming problems.

Importance of Symmetric Matrices

If we have a symmetric matrix, then we immediately know a few things about the concerned system of linear equations:

If each vector is linearly independent, then we have as many pivots as we have rows or columns.
This is a special case where we say that the matrix has a full rank. Hence the matrix is invertible, and there exists a particular unique solution to this system of linear equations.
Eigen Values are defined for square matrices.
This allows us to investigate whether a given matrix is diagonalizable. If the matrix is diagonalizable, then it allows us to perform efficient computations of the powers of A, leading into matrix exponentials.
Diagonalization is a very common mathematical operation in quantum mechanics. The time-independent Schrödinger equation is broadly speaking, an eigenvalue equation.

Since matrices are nothing but representations of linear equations, we cannot force ourselves to represent data symmetrically (actually we can, and often do). If a particular dataset that we are investigating has the same number of vectors as its attributes (which is definitely coincidental) then we can perform an extended analysis on the dataset owing to the properties of the square matrix.


Finding all solutions to an integer linear programming (ILP) problem

"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope.

This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, An Algorithmic Theory of Lattice Points in Polyhedra, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)

There are probably more recent developments than I'm aware of, but this will give you a starting point for chasing citations.


Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.
To answer your question, let's look at a simple example, change-making problem:

Given a set of integer values of coins $C = \{c_1, …, c_n\}$ and an amount $W$, what is the minimum number of coins to add-up to the amount $W$?

The classical greedy approach is the following:
While W > 0
   pick the largest coin c that is <= W
   W <- W - c

For example, with $C = \{1, 2, 5\}$ and $W = 13$, you will pick $5$, $5$, $2$ and $1$, and you can show that the minimum number of coins required is indeed $4$.
However, this algorithm does not always provide an optimal solution. For example, if $C = \{1, 4, 5\}$ and $W = 8$, the greedy algorithm will choose coins $5, 1, 1, 1$ when there is a solution $4, 4$ using less coins.
Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $C$


Defining polynomial hierarchy with oracle machines and quantifiers

The oracles do not play the role of quantifiers, they play the role of everything but the first quantifiers.

First, observe how NP relates to $\exists yR(x,y)$ with $R$ in P. That means that NP allows existential nondeterminism followed by computation in P.

Similarly, $\Pi_1$ "is" $\forall yR(x,y)$ with $R$ in P.
Now for $\Sigma_2$ we have the same with an additional $\exists$ at the front: $\exists y_1\forall y_2R(x,y_1,y_2)$ with $R$ in P. Or, in other words,
$\exists y_1 R'(x,y_1)$ with $R'$ in $\Pi_1$. So we have existential nondeterminism followed by computation in $\Pi_1$. And that is more or less the same as NP with a $\Pi_1$ oracle.

In general, the first quantifier specifies whether we are in the existential or universal case. The rest of the formula then describes a lower level of the hierarchy which we use as an oracle.


What could 'two characters are terminals' mean?

It means that $a$ and $b$ cannot be further decomposed. For example we might consider the language
$$
L_1=\{r^ns^m\mid n, m \ge 0, m\ge n, r\text{ and }s \text{ are 2-character strings over } \{a, b\}\}
$$
In this language, $r$ and $s$ could be any of $aa, ab, ba, bb$, so a string in $L_1$ could be $bababbbbbb$, since with $r=ba, s=bb$ we could write it as $(ba)^2(bb)^3$. In effect, saying "$a$ is terminal" asserts that it's a character in the underlying alphabet.

The original definition of $L$ is reasonable, but rarely used in my experience. An equivalent statement would be
$$
L=\{w\in \{a, b\}^*\mid w=a^nb^m, n, m\ge 0, m\ge n\}
$$
or the alphabet $\{a, b\}$ would be inferred from context and usually wouldn't be stated. On any of my students' work, I'd accept
$$
L=\{a^nb^m\mid n, m\ge 0,m\ge n\}
$$


It all boils down to simulating a $\mathsf{\# P}$ oracle using a $\mathsf{PP}$ oracle. Consider a $\mathsf{\# P}$ oracle call: a polytime non-deterministic Turing machine $T$ and an input $x$. We want to know how many runs of $T$ result in the output $1$. Denote this number by $T_1(x)$, and denote the total number of runs of $T$ on $x$ by $T(x)$.

First, let's show that using a $\mathsf{PP}$ oracle we can decide whether $T(x) \geq y$ for any polysize $y$. We construct a Turing machine $T'$ that acts as follows:

Guess a non-deterministic bit $b$.
If $b = 0$, then simulate $T$ on $x$ in such a way that there are $2T(x)+1$ different paths, and in all of them return $1$.
If $b = 1$, then have $2y$ different paths, all of them returning $0$.

The $\mathsf{PP}$ oracle returns Yes iff $T(x) \geq y$. I'll let you show how to implement steps 2 and 3.

Second, we can use binary search to determine $T(x)$ exactly. We start by determining some upper bound on $T(x)$: ask whether $T(x) \geq 2^k$ for $k=0,1,\ldots$, until you find a value of $k$ such that $T(x) < 2^k$. Since $T$ runs in polytime, $k$ is polynomial, and so this step takes polytime. Next, you do classical binary search (starting from $0 \leq T(x) < 2^k$), and determine $T(x)$ exactly. Again, this takes polytime since $k$ is polynomial.

Third, using our knowledge of $T(x)$, we can decide whether $T_1(x) \geq y$ in a similar way. For example, we could construct a new machine $T'$ with $T'(x) = T(x) + T_1(x)$, and then decide whether $T'(x) \geq T(x) + y$. You fill in the details.

Finally, we calculate $T_1(x)$ using binary search. This time we can skip the first half-step since we already know that $T_1(x) \leq T(x)$.


You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.


Correctness of Algorithm for Computing Diameter of a Graph

It works for trees (although it can be simplified).  However, on general graphs it does not work.

If your arbitrary vertex $v$ is the one on the top (labeled 1), then the Temp={8,9}.  However, the unique diameter path is from 7 to 6.


Count total number of k length paths in a tree

This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store them, instead building the array at every node by "scavenging" the arrays of its children.

To calculate the number of nodes at depth $d$ in the subtree of $i$, calculate the arrays for all children of $i$, then prepend zero to them, and sum them up, then finally add 1 to the number of nodes at depth $0$ (to count node $i$). For fast prepending, we store the arrays as dynamic arrays with inverted indexing. When we add two arrays together, we only care about the result, not about what happens to the orignal arrays, so we can just add the numbers in the smaller array to the numbers in the larger array and return the larger array.

Thus, if node $i$ has children $c_{1}, \dots, c_{m}$ and $T_{i}$ denotes the subtree of node $i$, we do an amount of work proportional to $w_{i} = |T_{i}| - \max_{j} |T_{c_{j}}|$. Therefore the total complexity is $\mathcal{O}(\sum_{i = 1}^{n} w_{i})$. Note that if $p$ is the parent of $i$ and $|T_{p}| < 2|T_{i}|$ then $|T_{i}|$ does not appear in the sum. Therefore, on any path from the root to some node $x$, at most $\log n$ sets we count appear, and those are exactly the sets $x$ appears in. Since every vertex appears in at most $\log n$ sets, their total size is $\mathcal{O}(n \log n)$. This is tight: consider the perfect binary tree of size $n = 2^{h} - 1$.

It remains to show how to calculate the number of paths of length $k$ from the depth information. To do this, when combining two arrays $A$ and $B$ at some node, just add $\sum_{i} A[i] B[k-i]$ to the answer. If $A$ is the sum of the arrays of previous children, and $B$ is the array of the current child we are handling, this corresponds to counting the paths with one endpoint in the current child's subtree, and the other in some earlier child's subtree. This can be done in $\mathcal{O}(\min(|A|, |B|))$ so it does not affect the runtime.

Here is a C++ implementation of the algorithm:

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;

ll combine(deque<int>& a, deque<int>& b, int k) {
    if (a.size() < b.size()) swap(a, b);
    int as = a.size();
    int bs = b.size();

    // Count paths of length k
    ll res = 0;
    for (int i = max(0, (k - bs) + 1); i < min(k + 1, as); ++i) {
        res += a[i] * b[k-i];
    }

    // Combine a and b
    for (int i = 0; i < bs; ++i) a[i] += b[i];
    return res;
}

pair<ll, deque<int>> solve(int i, int k, int p, const vector<vector<int>>& g) {
    pair<ll, deque<int>> res = {(k == 0), {1}};
    for (int t : g[i]) {
        if (t == p) continue;
        auto sub = solve(t, k, i, g);
        sub.second.push_front(0);
        res.first += sub.first + combine(res.second, sub.second, k);
    }
    return res;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ll res = solve(0, k, -1, g).first;
    cout << res << '\n';
}


Originally I was going to give an assurance that something like your extensionality principle must hold, but I decided to puzzle out enough cubical Agda to actually demonstrate the proof.

However, I should say that your all : ∀ i → f (loop i) = f (refl base i) is actually a digression. This is equivalent to a square with arbitrary sides, which looks like this:

$$
\require{AMScd}
\begin{CD}
x @>all(0)>> x \\
@VpVV \Rightarrow @VVreflV \\
x @>>all(1)> x
\end{CD}
$$

but something with type p ≡ refl is actually more uniform than that, because if e has that type, then e i : x ≡ x regardless of i, which is more uniform than the above square (where e i : all i0 i ≡ all i1 i), and is equivalent to a square of the form:

$$
\begin{CD}
x @>refl>> x \\
@VpVV \Rightarrow @VVreflV \\
x @>>refl> x
\end{CD}
$$

But, if we have loop ≡ refl, we already have this sort of square, and applying f point-wise produces a new square of this type. So, the following code is accepted:

module Path
    (S1 Z : Set)
    (base : S1)
    (loop : base ≡ base)
    (f : S1 → Z)
    (x : Z)

    (sq : loop ≡ refl)
  where
  rfl : base ≡ base
  rfl = refl

  z : Z
  z = f base

  p : z ≡ z
  p i = f (loop i)

  zrfl : z ≡ z
  zrfl = refl

  hsq : p ≡ zrfl
  hsq j i = f (sq j i)

So, the bit in the HoTT book is just a consequence of the composition of 'functions'.

The more arbitrary square can be expressed using the PathP type, which is also written _[_≡_] in cubical Agda, and the proof of equivalence to the ∀ type is:

module Square
    (A : Set)
    (x y : A)
    (e₁ e₂ : x ≡ y)
    (lines : ∀ i → e₁ i ≡ e₂ i)
  where
  f₀ : x ≡ x
  f₀ = lines i0

  f₁ : y ≡ y
  f₁ = lines i1

  square : (λ i → e₁ i ≡ e₂ i) [ f₀ ≡ f₁ ]
  square i j = lines i j

If you want to fool around with cubical Agda yourself to try this out interactively, I've been using a recent Agda from the development branch with {-# OPTIONS --cubical #-}, along with this library.


Not a complete answer, but in T. Kloks Treewidth you have the following lemma:

  There always exists a nice tree decomposition of width $k$ and with at most $4n$ bags.

It is NP-complete to determine the minimum number of bags in a tree decomposition of width $k$.


Is the unweighted vertex cover problem equivalent to its weighted version?

If you're talking about determining whether there exists a cover of weight $\le T$, then the problem is obviously in NP and thus reduces to unweighted vc (since $VC$ is NP complete).

If however were talking about whether the minimal cover is of weight $\le T$, then the problem is $\Sigma_2$ complete, and is therefore not reducible to vc unless the hierarchy collapses to the first level.


Overlap between computer science and analytic geometry?

Computer graphics is applied analytic geometry, and showing how games do their computations might be exactly the kind of motivating subject matter you are looking for.


How can I quickly judge whether matrix A is the inverse matrix of B?

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $A$ and $B$ would be the matrices you are given, and the matrix $C$ would be the identity matrix.


Turing machine with semi infinite tape - Prove by construction

You are right. It is possible to shift the contents of the tape when needed.

The two track solution enlarges the alphabet $\Sigma$ to at least an alphabet $\Sigma\times \Sigma$ to store two symbols on each tape cell. That is quadratic. Your solution perhaps is more efficient in the number of symbols, since we merely have to move them into a new position.

A third proof might be to store the left and right cells of the tape (from an imaginary "middle") in the even and odd cells. That means the simulation would usually fins the next cell in two steps rather than one.

It is not always clear how to measure elegance of proofs :) sometimes a solution comes from a certain intuition, making it appealing.


Does big-Oh impose an ordered partition on the set of the "usual" functions?

This was shown by Hardy in his monograph Orders of Infinity.


$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language

This answer assumes that $v_i \in \Sigma$ are individual symbols.

You can prove this using closure properties. The advantage is that any class of languages closed under the requisite closure properties will be closed under this operation. Specifically, we will need closure under homomorphism, reverse homomorphism, and intersection with regular language, which are exactly the so-called "full trio".

Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$ be a copy of $\Sigma$. Define homomorphisms $r,d\colon \Sigma \cup \Sigma' \to \Sigma$ by $r(\sigma) = r(\sigma') = \sigma$ and $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then
$$
\mathcal{G} = d(r^{-1}(\mathcal{L}) \cap (\Sigma' \Sigma)^*).
$$

Some families of languages, for example context-sensitive languages, are closed under the so-called "trio", in which homomorphism is replaced with $\epsilon$-free homomorphism (meaning $h(\sigma) \neq \epsilon$ for all letters $\sigma$). We can accommodate these as well with a slightly more complicated argument.

Let $e\colon \Sigma' \times \Sigma \to \Sigma \cup \Sigma$ be given by $e(\sigma',\sigma) = \sigma' \sigma$, and let $p\colon \Sigma' \times \Sigma \to \Sigma$ be given by $p(\sigma',\sigma) = \sigma$. Then
$$
\mathcal{G} = p(e^{-1}(r^{-1}(\mathcal{L}) \cap (\Sigma'\Sigma)^*)).
$$


Define a list using only the Hindley-Milner type system

Pairs

This encoding is the Church encoding of pairs. Similar techniques can encode booleans, integers, lists, and other data structures.

Under the context x:a; y:b, the term pair x y has the type (a -> b -> t) -> t. The logical interpretation of this type is the following formula (I use standard mathematical notations: $\to$ is implication, $\vee$ is or, $\wedge$ is and, $\neg$ is negation; $\iff$ is equivalence of formulas):
$$ \begin{align}
  (a \to b \to t) \to t
  & \quad\iff\quad \neg (\neg a \vee \neg b \vee t) \vee t \\
  & \quad\iff\quad (a \wedge b \wedge \neg t) \vee t \\
  & \quad\iff\quad (a \wedge b) \vee t \\
\end{align}
$$
Why “a and b or t”? Intuitively, because pair is a function that takes a function as an argument and applies it to the pair. There are two ways this can go: the argument function can make use of the pair, or it can produce a value of type t without using the pair at all.

pair is a constructor for the pair type and first and second are destructors. (These are the same words used in object-oriented programming; here the words have a meaning that is related to the logical interpretation of the types and terms that I won't go into here.) Intuitively, the destructors let you access what is in the object and the constructors pave the way for the destructor by taking as an argument a function that they apply to the parts of the object. This principle can be applied to other types.

Sums

The Church encoding of a discriminated union is essentially dual to the Church encoding of a pair. Where a pair has two parts that must be put together and you can choose to extract one or the other, you can choose to build the union in either of two ways and when you use it you need to allow for both ways. Thus there are two constructors, and there is a single destructor which takes two arguments.

let case w = λf. λg. w f g           case : ((a->t) -> (b->t) -> t) -> (a->t) -> (b->t) -> t
  (* or simply let case w = w *)
let left x = λf. λg. f x             left : a -> ((a->t) -> (b->t) -> t)
let right y = λf. λg. g x            right : b -> ((a->t) -> (b->t) -> t)

Let me abbreviate the type (a->t) -> (b->t) -> t as SUM(a,b)(t). Then the types of the destructors and constructors are:

case : SUM(a,b)(t) -> (a->t) -> (b->t) -> t
left : a -> SUM(a,b)(t)
right : b -> SUM(a,b)(t)

Thus

case (left x) f g → f x
case (rightt y) f g → g y

Lists

For a list, apply again the same principle. A list whose elements have the type a can be built in two ways: it can be an empty list, or it can be an element (the head) plus a list (the tail). Compared with pairs, there's a little twist when it comes to the destructors: you can't have two separate destructors head and tail because they would only work on non-empty lists. You need a single destructor, with two arguments, one of which is a 0-argument function (i.e. a value) for the nil case, and the other a 2-argument function for the cons case. Functions like is_empty, head and tail can be derived from that. Like in the case of sums, the list is directly its own destructor function.

let nil = λn. λc. n
let cons h t = λn. λc. c h t
let is_empty l = l true (λh. λt. false)
let head l default = l default (λh. λt. h)
let tail l default = l default (λh. λt. t)

Each of these functions is polymorphic. If you work the types of these functions, you'll note than cons is not uniform: the type of the result is not the same as the type of the argument. The type of the result is a variable — it is more general than the argument. If you chain cons calls, the successive calls to build a list instantiate cons at different types. This is crucial to make lists work in the absence of recursive types. You can make heterogeneous lists that way. In fact, the types that you can express are not “list of $T$”, but “list whose first elements are of types $T_1,\ldots,T_n$”.

As you surmise, if you want to define a type that only contains homogeneous lists, you need recursive types. Why? Let's look at the type of a list. A list is encoded as a function which takes two arguments: the value to return on empty lists, and the function to compute the value to return on a cons cell. Let a be the element type, b be the type of the list, and c be the type returned by the destructor. The type of a list is

a -> (a -> b -> c) -> c

Making the list homogeneous is saying that if it's a cons cell, the tail has to have the same type as the whole, i.e. it adds the constraint

a -> (a -> b -> c) -> c = b

The Hindley-Milner type system can be extended with such recursive types, and in fact practical programming languages do that. Practical programming languages tend to disallow such “naked” equations and require a data constructor, but this is not an intrinsic requirement of the underlying theory. Requiring a data constructor simplifies type inference, and in practice tends to avoids accepting functions that are actually buggy but happen to be typable with some unintended constraint that causes a difficult-to-understand type error where the function is used. This is why, for example, OCaml accepts unguarded recursive types only with the non-default -rectypes compiler option. Here are the definitions above in OCaml syntax, together with a type definition for homogeneous lists using the notation for aliased recursive types: type_expression as 'a means that the type type_expression is unified with the variable 'a.

# let nil = fun n c -> n;;
val nil : 'a -> 'b -> 'a = <fun>
# let cons h t = fun n c -> c h t;;
val cons : 'a -> 'b -> 'c -> ('a -> 'b -> 'd) -> 'd = <fun>
# let is_empty l = l true (fun h t -> false);;
val is_empty : (bool -> ('a -> 'b -> bool) -> 'c) -> 'c = <fun>
# let head l default = l default (fun h t -> h);;
val head : ('a -> ('b -> 'c -> 'b) -> 'd) -> 'a -> 'd = <fun>
# let tail l default = l default (fun h t -> t);;
val tail : ('a -> ('b -> 'c -> 'c) -> 'd) -> 'a -> 'd = <fun>
# type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c;;
type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c
# is_empty (cons 1 nil);;
- : bool = false
# head (cons 1 nil) 0;;
- : int = 1
# head (tail (cons 1 (cons 2.0 nil)) nil) 0.;;
- : float = 2.

(* -rectypes is required for what follows *)
# type ('a, 'b, 'c) rlist = 'c -> ('a -> 'b -> 'c) -> 'c as 'b;;
type ('a, 'b, 'c) rlist = 'b constraint 'b = 'c -> ('a -> 'b -> 'c) -> 'c
# let rcons = (cons : 'a -> ('a, 'b, 'c) rlist -> ('a, 'b, 'c) rlist);;
val rcons :
  'a ->
  ('a, 'c -> ('a -> 'b -> 'c) -> 'c as 'b, 'c) rlist -> ('a, 'b, 'c) rlist =
  <fun>
# head (rcons 1 (rcons 2 nil)) 0;;
- : int = 1
# tail (rcons 1 (rcons 2 nil)) nil;;
- : 'a -> (int -> 'a -> 'a) -> 'a as 'a = <fun>
# rcons 1 (rcons 2.0 nil);;
Error: This expression has type
         (float, 'b -> (float -> 'a -> 'b) -> 'b as 'a, 'b) rlist = 'a
       but an expression was expected of type
         (int, 'b -> (int -> 'c -> 'b) -> 'b as 'c, 'b) rlist = 'c

Folds

Looking at this a bit more generally, what is the function that represents the data structure?

For a natural number: $n$ is represented as the function which iterates its argument $n$ times.
For a pair: $(x,y)$ is represented as a function which applies its argument to $x$ and $y$.
For a sum: $\mathrm{in}_i(x)$ is represented as a function which applies its $i$th argument to $x$.
For a list: $[x_1,\ldots,x_n]$ is represented as a function that takes two arguments, the value to return for the empty list and the function to apply to cons cells.

In general terms, the data structure is represented as its fold function. This is a general concept for data structures: a fold function is a higher-order function that traverses the data structure. There is a technical sense in which fold is universal: all “generic” data structure traversals can be expressed in terms of fold. That the data structure can be represented as its fold function shows this: all you need to know about a data structure is how to traverse it, the rest is an implementation detail.


Python-specific questions are probably off-topic here, but this question can be seen as a language-agnostic algorithmic task: given two arrays $A$ and $B$, each representing a multi-set, return an array containing the elements in the multiset $C = A \cap B$.
Here an element $x$ that has multiplicity $a$ in $A$ and $b$ in $B$, has multiplicity $\min\{a,b\}$ in $C$.
To solve this problem you can preliminary sort $A$ and $B$. Then, you can keep a pointer $p_A$ to some element of $A$ and a pointer $p_B$ to some element of $B$. Initially $p_A$ (resp. $p_B$) will point to the first element of  $A$ (resp. $B$).
I will use $A[p_A]$ (resp. $B[p_B]$) to denote the element of $A$ (resp. $B$) pointed by $p_A$ (resp. $p_B$). Also, it is convenient to assume that, whenever $p_A$ (resp. $p_B$) points past the end of $A$ (resp. $B$), $A[p_A]$ (resp. $B[p_B]$) has value $+\infty$.
Proceed similarly to the merge step of Mergesort:

Initialize $C$ as an empty array.
While ($p_A$ is not past the end of $A$) or ($p_B$ is not past the end of $B$)

If $A[p_A] = B[p_B]$:

Append $A[p_A]$ to $C$.
Advance $p_A$
Advance $p_B$.

Else if $A[p_A] > B[p_B]$:

Advance $p_B$

Else (in this case $A[p_A] < B[p_B]$):

Advance $p_A$


is little-o notation correct after being powered by a number?

Trivially: $f(n) = 0, g(n) = 1$. Then $lim_{n \to \infty} f(n)/g(n) = lim_{n \to \infty} 0 / 1 = 0$ and $lim_{n \to \infty} 2^{f(n)}/2^{g(n)} = lim_{n \to \infty} 1 / 2 \neq 0$. You may want to think if less trivial cases exist.


Two languages such that their Kleene closures are equal

I had originally assumed that the sets are disjoint, but there's no such requirement in the question. I'll post my solution in case anyone might have the same problem in future.
S = {a, b, ab}
T = {a, b, ba}
S* = T* since the intersection has all the letters of the alphabet plus ab and ba can easily be obtained from a and b.


Algorithm for Estimating Number of Unique Monthly Visitors

After digging into this for a bit, I came across this paper which provides a solution. The paper gives an approach to estimating the number of new species that will be observed given an initial sampling period. It models observing a given species as a Poisson distribution. It gives the following estimator for the number of new species that will be discovered:
$$
\hat{\Psi}(t)=\sum_{k=1}^{k_{m a x}} N_{k} e^{-k}-\sum_{k=1}^{k_{m a x}} N_{k} e^{-k(1+t)}
$$
where $N_{k}$ is the number of species that were observed $k$ times and $t$ is the length of the second sample relative to the initial sample.


Algorithm for this problem on generating all permutations

Suppose that there are $n$ groups, that group $i$ has the $m_i$ elements $x_{ij}$. It is a nice exercise to show that the sum of weights of all valid vectors is
$$ \prod_{i=1}^n \sum_{j=1}^{m_i} x_{ij}. $$
(In you example, you can factor your formula as (Member 1 + Member 2) * Member 3.)


Prove that context free languages are not closed under swapping prefixes and suffixes

Did you try $\{\ a^nb^nc^md^m \mid m,n \ge 1 \}$?

Or, if you insist on alphabet $\{0,1\}$,
consider $\{\ (01)^n(011)^n(0111)^m(01111)^m \mid m,n \ge 1 \}$?

And be shure to intersect with a nice regular language after the operation, but from your question I see that you know how that works.


How to count all integers less than a given integer and having two contigous digits as $y$?

So say you want to count all numbers of the form $x_1\cdot ab\cdot x_2$ less than $n$, where $x_1$ and $x_2$ are numbers with a fixed number of digits, and $ab$ are two contiguous digits.

Cut $n$ in the same positions as your $x_1\cdot ab \cdot x_2$ pattern to get $n_1\cdot pq\cdot n_2$.

Now when is $x_1\cdot ab\cdot x_2 < n_1\cdot pq\cdot n_2$?

Either $x_1 < n_1$, then any choice for $x_2$ goes. I.e., $10^{\text{number-of-digits}(x_2)}$ choices for $x_2$ whenever $x_1<n_1$. In total you get $n_1\times10^{\text{number-of-digits}(x_2)}$ choices for this case, or $(n_1-10^{\text{number-of-digits}(x_1)-1})\times10^{\text{number-of-digits}(x_2)}$ choices if you don't allow for leading zeros.
Or $x_1=n_1$, in which case it depends on $ab$ and $pq$.

If $ab<pq$ then any choice for $x_2$ goes, so you get an additional $10^{\text{number-of-digits}(x_2)}$ choices.
If $ab=pq$ then you have to have $x_2<n_2$ which gives you an additional $n_2$ choices.
If $ab>pq$ then no choice of $x_2$ will work.

In short, with leading zeros allowed:

If $ab<pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)} + 10^{\text{number-of-digits}(x_2)}$$
If $ab=pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)} + n_2$$
If $ab>pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)}$$

For example with $x11xx$ and $54432$ you get:
$$5\times 10^2 + 10^2 = 600$$


How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

Your assumption is wrong; the dynamic programming algorithm does not do that. It computes $m(n,W)$ according to the recurrence

$\qquad\displaystyle
  m(i,w) = \begin{cases}
    0, &i=0 \lor w=0; \\
    m(i-1,w), & w_i > w; \\
    \max \{ m(i-1,w), m(i-1, w - w_i) + v_i \}, &w_i \leq w .
  \end{cases}
$

Here, $(w_1, v_1), \dots, (w_n, v_n)$ are the weight-value pairs and $W$ is the knapsack size. Note how $m(i,w)$ is the maximum value that can be achieved with items $1, \dots, i$ and up to weight $w$; prove that by induction.

You can note two things:

The algorithm does not "move towards" $W$ in a straight fashion; it investigates many "paths" from $0$ to $W$ in an interleaved fashion, optimizing locally.
When it makes a stept, it does not have to be by $1$; all steps correspond to a $w_i$.


Complexity of finding these original parameters

You can compute $m,s$ from the equations: $s = (c-1)/2$ and $m = (b-1)/s$; both must be integral. You can then check that indeed $m(s+1) = a$. If this holds, then you have found the unique solution $m,s$, otherwise there is no solution.
More generally, this method allows you to find the unique real solution to your system of equations, if any exists.

Note that $m = (b-1)/s = 2(b-1)/(c-1)$. Hence $s,m$ are integers if $s$ is odd and $c-1$ divides $2(b-1)$. If they are integers, the final equation is satisfied if
$$
a = ms + m = b-1 + \frac{2(b-1)}{c-1} = (b-1) \frac{c+1}{c-1}.
$$
Another way to state this condition is
$$
a(c-1) = (b-1)(c+1).
$$


How does dynamic memory-allocation exactly work?

Consider the following code:

int a = 8;
a = a+1;

On my system, this snippet compiles to the following code:

movl    $8, -20(%rbp)
movl    -20(%rbp), %edi
addl    $1, %edi
movl    %edi, -20(%rbp)

The register rbp points at the top of stack. The variable a is located 20 bytes below the top of stack.

The first assembly line about implements the C line int a = 8, and the rest implement a = a+1 by first loading a into the register edi, then increasing edi by 1, and then storing edi back at a.

If you want to try it out, use the following command:

cc -O0 -S <progname>.c

The assembly will appear in <progname>.s.


No, your approach will not work

Let $O$ be your chosen origin. Let $A$, $B$ be two of your other points. $OAB$ form a triangle.

The vector you have in mind would contain the distances $\overline{OA}$ and $\overline{OB}$. You can not determine the distance $\overline{AB}$ using only the two other sides of the triangle. You would need at least one of the angles for that.

As for a concrete counter example:

$O = (0,0), A = (0,2), B = (0,5), C = (2,0)$

so your vector would be:

$\overline{OA} = 2, \overline{OC} = 2, \overline{OB} = 5$

The differences are:

$\overline{OA}-\overline{OC} = 0$

$\overline{OC}-\overline{OB} = -3$

$(C, B)$ forms the minimum of but the closest pair is $(A, B)$ with a distance of 3.


How to check if a specific ILP problem can be solved in polynomial time or not?

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a single problem as any single problem can be solved in $O(1)$!

That said, there is a notable class of ILP's that is known to be polynomial time solvable. This class consists of the ILP's that can be described with a totally unimodular matrix (or equivalently, if the solution space is an integral polyhedron). This property guarantees that the relaxed version of the ILP has in fact the same solution as the original ILP!

However, this doesn't mean that there aren't other classes of ILP's for which there exists an algorithm that can solve them in polynomial time (In fact, as it is possible that P=NP, it is possible that the class of all ILP's is solveable in polynomial time!)

So, in general, a complete answer to your question is beyond the current state of science, but there are special cases where can say that it is poly-time solvable. However, we cannot say for sure that there even exist classes that are not.


You correctly pointed out that $\ln n = \frac{\log_2n}{\log_2 e}$. You can rewrite this as $\ln n = \frac{1}{\log_2e}\cdot\log_2n$. Since $\Theta(\cdot) $ allows you to drop constant factors (and as @Pseudonym pointed out, $\frac{1}{\log_2e}$ is constant), it follows that $\ln n = \Theta(\log_2n)$


Here are some tips and pitfalls I've collected after using live coding for a week, and from talking to a colleague.

DOs

Prepare a script to follow and try to stick to it.
Clear the buffers frequently to focus on relevant part.
Start afresh for each new topic.
Use a bigger font.
Master the tool you are using, to avoid wasting too much time on trivialities.
Have background functions precoded. If not particularly relevant, ensure they
can be imported, rather than appearing in the working file.
Ideally work in a language that give you immediate feedback. Languages with an
interactive shell are best in this regard.
When using a typed, give the expected type of the function you are writing. This
provides a guiding light for the students.
Freely make mistakes (though not too many). Step through how these should be fixed.
Don't forget – a picture paints a thousand words: interleave slides and black/whiteboard
work with your coding session.
Have summary slides for the points you've covered
Sometimes, when modifying code, maybe make a copy and modify the copy.
This provides a point of comparison.
Clean up code periodically.
Accept that you will make mistakes and openly allow students to correct you --- this makes
your job easier and empowers them.
Write code in your own style. For example, you may have copied the code from elsewhere.
But this will be hard to reproduce. Better to write it in your own style.
For instance, I always write curried functions, because I program mostly Haskell.
But Standard ML uses the idiom less frequently. Expecting curried functions is
the most common error I make in class.
Physically, make sure you have your space set up well. Good keyboard, at the right height, cables all in the right places, physical obstacles out of the way, etc. Take a minute before you start to get your space working for you, not against you.
One approach is to write whatever students say, even if it is wrong. This get students to do
the coding, and the fixing. It is a good idea to clean the code up at the end. This approach can
create a classroom model of attention and interaction, because students need to pay attention
to follow what is going on.

DON'Ts

Don't optimise your code on the fly and break it in such a way that you
cannot fix it.
Avoid talking to the computer. Talk to the students!
Avoid too much typing, especially of boilerplate code.
Utilise your environment to help you spit out the templates for you.
If you use a text editor, avoid constantly scrolling around. It will cause motion sickness it those trying to follow.
If you use a text editor, before making radical changes to your code, warn students that you are going to do so, so that they can track what is going on.