Mapping reducibility from recursive to recursively enumerable language

If $L_1 \le_m L_2$, that is, $L_1$ is many-one (i.e., mapping) reducible to $L_2$ and $L_2$ is recursively enumerable (r.e.), then $L_1$ must also be r.e. This is because an acceptor for $L_1$ can be derived by reducing any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ and then simulating the acceptor for $L_2$ (which exists on grounds of $L_2$ being r.e.) on $w'$.

However, in general, $L_1$ does not have to be recursive (which is strictly stronger than r.e.). In fact, any language $L$ is (trivially) many-one reducible to itself, so just take your favorite r.e. but not recursive language $L$ and note that $L \le_m L$ holds despite $L$ not being recursive.

Honestly, I believe your confusion arises from your unnecessarily complex view of many-one reducibility (i.e, on the basis of $L_1$, $L_2$, and their complements). Note that you can think of a reduction of $L_1$ to $L_2$ instead as mapping any instance $w$ of $L_1$ to an instance $w'$ of $L_2$ under the condition $w \in L_1 \iff w' \in L_2$. Stating this based on the equivalence sign "$\iff$" avoids having to think about the complements of $L_1$ and $L_2$, thus avoiding unnecessary "clutter" in your thought process.


Often control-flow graphs don't include call's or other interprocedural control-flow in the graph.  So, a call node does not lead to an edge from the call site to the callee, and in this case, that means there would be no edge from 13 to 2.


Relative order of values and weights in Knapsack

The weights and values can be arbitrary. In particular, if you sort the items by their weight, then they need not be sorted by their value.

More generally, if you look at a formal definition of the Knapsack problem, you will see that nothing is mentioned about the possible weights and values of the items (beyond their being positive integers). Every instance which conforms to the definition is valid.

In other words, you should be able to answer such questions by looking at the formal definition of the problem. There is no hidden information which can only be obtained by asking questions on forums. Indeed, it is exactly the opposite — the problem statement defines the problem completely.


$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma

Suppose $L$ is context free. Then, by pumping lemma, there exist two integers $h \ge 1$ and $1 \le x \le \min\{h!, c_L\}$, where $c_L$ is a constant depending on $L$, that satisfy the following:

$a^{h!} \in L$
$a^{h!-x} a^{xn} \in L$ for every $n \ge 0$.1

Now you only need to show that, for some value of $n$, $a^{h!-x} a^{xn} \not\in L$.
Equivalently, you want to find a value of $n$ (possibly depending on $h$) such that
$h! + (n-1)x$ cannot be written as $j!$ for any integer $j \ge 1$.

For example, if $h = 1$ then $x=1$ so you can pick $n=0$ to obtain $h! + (n-1)x = 0$.

When $h \ge 2$, you can pick $n=2$ so that $h! + (n-1)x = h! + x$, which is not a factorial of an integer as the following inequalities show:
$$
h! < h! + x \le 2 \cdot h! < (h+1)!
$$

1. This is a consequence of the general form of the pumping lemma and of the fact that all the words in your language contain only the character a.


How to prove "The power set of a countable set must be uncountable"?

This is Cantor's diagonalization lemma:

Let $S$ be a countable set and suppose that there is a bijective function $\phi: S \to 2^S$.  Let $U = \{x \in S \mid x \notin \phi(x)\}$.  (Notice that our only assumption is the existence of the bijective function.)

Since $U \in 2^S$, and $\phi$ is bijective, there must be a $u \in S$ s.t. $\phi(u) = U$.

Now I ask you:  Is $u \in U$?

If you answer that question, you have the answer: $\phi$ cannot exist!  Hence $2^S$ cannot be countable.  You should also show that there is an injective function $\psi: S \to 2^S$, but this is trivial: $\psi(x) = \{x\}$, so $|S| \leq |2^S|$.

To complete the argument you must also show that there cannot be a bijective function from $\mathbb{N}$ to $2^S$ but this is immediate since there is one from $\mathbb{N}$ to $S$.


Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem

There are a few good books on the TSP problem where you are likely to find some relevant information:

Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985.

G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994.

G. Gutin and A. P. Punnen, eds. The traveling salesman problem and its variations. Kluwer, 2004.

Good luck with your research!


The time hierarchy theorem gives, for every $k$, a function in P with a runtime lower bound of $\Omega(n^k)$. Unfortunately, this is not enough to separate P from NP: to do this, we need a function in NP with a superpolynomial runtime lower bound.

One popular approach for tackling the P vs NP question is via circuits. The best lower bounds for explicit functions are only linear. Perhaps this is the context in which you heard of superlinear lower bounds as a seeming barrier.


Yes, $A$ is a CFL.  Use the context free language (with the notation $|x|_0$ meaning what you have as #0's in $x$):

$B=\{x\in \{0,1\}^*:3\cdot|x|_0=|x|_1\}$

and the morphism $f:\{a,b,c\}^*\rightarrow\{0,1\}^*:$ $ f(a)=0, f(b)=00, f(c)=1$

so that

$A=f^{-1}(B)$.

Since the CFL's are closed under inverse morphism, $A$ is a CFL.

The proof that $B$ is a CFL is a bit tricky.  Let's do it for the simpler case $C=\{x:|x|_0=|x|_1\}$, which can fairly easily be generalized to work for $B$ (or use another morphism).

Design a PDA which keeps track of $|x|_0-|x|_1$ at all points of the input, using the stack to keep track of the difference, having read $x$. The PDA accepts only when that difference is zero, that is, the stack is empty. The idea is to push a $0$ on seeing a $0$ on the input string, and pop a $0$ when seeing a $1$ in the input. The problem is that difference might go negative at times, and you can't pop an empty stack. In that case, however, the PDA goes into another mode (a different set of states) where it pushes a $1$ on seeing an input of $1$ and pops a $1$ on seeing an input of $0$.  So the second mode handles the negative case. It alternates between the two modes, accepting only if the stack if totally empty, that is, in-between the modes.

Or, you can do it with the grammar: $S\rightarrow 0S1|1S0|SS|\epsilon$.  That clearly generates only strings of C, but proving that it generates all of $C$ is a bit involved, but here's a sketch, by induction on string length.

An isosymbolic string $x$ (that is $|x|_0 = |x|_1$) could be null, in which case the $\epsilon$ production applies giving the basis of the induction.  Otherwise $x$ either starts and ends in different symbols (one end $0$ and the other end $1$), or the same symbol (both $0$ or both $1$). In the not-equal case, the last production to apply is either the $0S1$ or the $1S0$ production, allowing us to strip off the first and last symbols, getting a shorter isosymbolic string, so the induction applies.

In the equal case, as with the PDA, we keep track of $|y|_0-|y|_1$ as we move from left to right through prefixes $y$ of $x$. If the first and last symbols of $x$ are the same, it's fairly easy to see that that expression must be zero somewhere in the interior of the string. For example, if $x$ starts and ends with $0$, then after the first symbol the difference is $+1$ and before the last symbol it is $-1$, so it must have crossed zero in the interior. Split the string in two at that spot (reversing the $SS$ production) and the two halves, both shorter than $x$, are both isosymbolic.  So the induction works there too, and we are done.


Calibration and overlay of RGBD with a thermal camera

I suggest that you obtain both the intrinsic and extrinsic parameters for both cameras.  The extrinsic parameters will include information like the offset/distance between the two cameras and the relationship between their two headings, which is needed to relate their images.  (If only the relative position and orientation/heading of the two cameras is known, that will be enough.)

Once you have these parameters, you'll be able to map each pixel in the RGBD image to its corresponding pixel in the thermal image.  This will let you align those two images.  Then, depending upon the specific setup, you might need to do fine-grained image stabilization (e.g., if they are not on tripods).

It's not clear why the different wavelengths would have any impact on alignment of the two images.

See also https://en.wikipedia.org/wiki/Camera_resectioning.


Turing machine with possible transitions to the final state

I would define F(set of final states)={$q_4,q_5,q_6$} then:

$ q_4-q_5:b,b,R$

$q_4-q_7:X,X,R$ for X=a,c

$q_5-q_6:b,b,R$

$q_5-q_7:X,X,R$ for X=a,c

$q_6-q_7:X,X,R$ for X=a,b,c


How can it be detected that a number generator is not really random?

Computers Being Really Random:

True randomness is impossible for Turing Machines in a theoretical sense, and most computers can't generate truly random output.  Therefore, some modern computers include hardware that allows the computer to access an outside source which will hopefully include some randomness.   One example of how this can be accomplished is to track small fluctuations in temperature inside the computer.  Randomness can be obtained from an outside source as well.  But from the tone of your post I don't think that outside sources of randomness are what you're interested in.

Seeds:

Without an outside addition, everything a computer does is deterministic.  This leads to a big issue: if you call a random number generation program, it will give you the same result every time if you give it the same input.  Clearly, we need a program that outputs a random number to change its behavior each time it's run (otherwise we'll keep getting the same "random" number, which is not particularly helpful).  One idea is to give the program some input, which changes each time the program is run, so that a different number will be output.  We call this input a "seed."  The random number generator needs to take in a seed, perform some operations, and give us a random number.

The current system time is a classic example of a seed.  This gives a long string with high entropy, and if the time is kept track of in a sufficiently granular fashion (i.e. if your system clock uses hours then "time" is a pretty poor seed), you're unlikely to feed the pseudorandom number generator the same number twice.

Algorithms that are Random Enough:

Now we have an algorithm that at least has some way to be different each time it's run.  We give it a seed, and while the algorithm gives the same number when prompted with the same seed, we want the numbers it generates to be random otherwise.  This acts like the above--you take in some input, and it produces some (hopefully different enough from the input to be "random") output.

Now let's say you came up with your own algorithm to do this, and you claim that the numbers you come up with are pretty close to random when you gave it a bunch of different seeds.  How would we test how good it is?

Now we want some algorithm that will take in a seed, do some operations, and produce a random number.  At the simplest, the algorithm could just output the seed--it's not giving us the same number each time, and random seeds give us random outputs.  But clearly that's not what we want.  On the other hand, an algorithm can be fairly complicated, like many actual pseudorandom generators.  How can we tell which algorithms give us "random" numbers  from our not-necessarily-random seeds?  If we can't get it exactly, how can we tell which are best?

It's hard to tell which of those tests are ideal, but it's easy to come up with some minimum requirements these algorithms should meet before we say they give us "random" numbers.  Maybe we want to make sure that your algorithm gives even numbers half the time.  Maybe  we want to make sure that if I ask for a random number between $1$ and $n$, all numbers in that range will be output for some input to your function.  Clearly there are a lot of tests we can run; if your algorithm passes some suite of tests it's a pseudorandom generator.  Which tests to use is a very interesting and well used/studied area of computer science.

Random Enough to Fool an Attacker:

Now what you MAY be referring to is Cryptographially Secure Pseudorandom Generators.  I think the best way to explain this is in the context of the above--here, we're using our randomness for cryptography, so when we're designing tests what we really care about is that someone won't be able to break our security by predicting what random number we picked.   I don't know your level of familiarity with cryptography, but imagine we're doing a simple replacement cypher---each letter is replaced with some other letter.  We want to pick these replacements randomly, so they're hard for an attacker to guess.  But if he can figure out how my random number generator works, he'll be able to solve the whole cipher!  Therefore, cryptographic algorithms require random number generators that are specifically hard to guess.  Specific cryptographic algorithms may require additional tests (like for some sort of nice-enough distribution as mentioned above).

For this reason, CSPRGs are defined in terms of how well other algorithms solve them (which is where we finally come to your question).  Specifically, let's say I have a CSPRG which I'll call R.  R is a CSPRG if and only if there is NO feasible algorithm that can guess which bit it will output next.  This is true even if you know all the previous bits it output!

So let's say that the first five bits my CSPRG has output are 10100.  You don't know the input I used to the program, but you have access to the code I used to write my CSPRG.   Then the claim is that it's impossible for you to write a program to decide if the next bit output will be 101000 or 101001.

So for reasons of cryptography, sometimes how well a pseudorandom number generator does is defined in terms of how predictable it is to other programs.  Note that this still gives much of the intuition of "randomness," as (say) if you know all of the random outputs will be odd it is neither cryptographically secure nor does it pass a common-sense randomness test.


Constraint propagation using Projection rule

You apply the propagation rule to a single constraint.

The rules are defined in such a way that they can be applied efficiently.
Otherwise, by applying the "generalized propagation rule" you could declare that a SAT instance is unsatisfiable in a single step.


These arguments are not really related, on several levels.

The first is that existence and computability are not the same thing. That is, even if there exists some object (e.g. a TM), it does not mean that finding (or computing) such an object can be done using a TM.

However, there is a more basic difference between the two statements. The first says that for every TM $M_1$, there exists some equivalent machine $M_2$. The second statement is that deciding, given $M_1$ and $M_2$, whether these two specific machines are equivalent, is undecidable.

Just to emphasize the difference, consider the following problem: given a TM $M_1$, is there some TM $M_2$, that is different from $M_1$, which is equivalent to $M_1$? This problem is trivial - the answer is always "yes" (e.g. just add a redundant state to $M_1$).


Amortized analysis for doubling resizing array is ~3n

Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power less than $n$. That means $2^i < n \le 2^{i+1}$.

As $2^i < n$ we have that the sum $2\cdot 2^i -1$ is less than $2n-1$.

I am a little confused as the text states "at most" rather than "less than".


One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones.  This might work acceptably if you only want very small graphs.

Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly.  There are about 16 million different planar graphs of size up to 11, so if you're lucky you might not need to consider anything larger and that collection will be adequate.


Need solution for infinite right recursive grammar in Predictive parsing?

You don't get infinite recursion with right recursive rules if the prediction sets for the rules are different.

In the example T -> E + T | t, if the first set of E does not contain t (I am presuming t is a terminal), you are fine. The parsing procedure will be:

def T
  if look_ahead is in first(E)
    E
    match ('+')
    T
  else if look_ahead == t
    advance_lookahead
  else syntax_error

With this, the recursion will stop when the look ahead contains t.

With left recursion T -> T + E | t, you are in trouble because first(T) always contains t.

Conversion of left- to right recursion solves one problem but creates another. Right-recursive rules have the disadvantage that parsing lists requires stack space proportional to list length.  Ideally you'd like the space a parser takes to be limited by a constant.  So what to do?

The practical way to prevent many cases of right-recursion is to extend grammars to allow for iteration.  In your case

T -> E + T | t

would become

T -> E + { E + } t

The curly braces denote "0 or more".

When the parser is implemented, the curly braces would become a while loop that uses the look ahead to decide whether to parse another instance of what's in the braces.  With your example, you'd need first(E) not to contain terminal t.

A more common example is the standard expression grammar:

Expr -> Term { '+' Term }
Term -> Factor { '*' Factor }
Factor -> '0' | '(' Expr ')'

In this case, the recursive descent procedure for Expr would be

def Expr
  Term
  while look_ahead == '+'
    advance_lookahead
    Term

If we didn't have the curly braces, the grammar would have to be:

Expr -> Term ExprTail
ExprTail -> '+' Term ExprTail | \eps
Term -> Factor TermTail
TermTail -> '*' Factor TermTail | \eps
Factor -> '0' | '(' Expr ')'

To parse Exprs we now need two procedures:

def Expr
  Term
  ExprTail

def ExprTail
  if look_ahead == '+'
    advance_lookahead
    Term
    ExprTail

Interestingly, if you use a good compiler to compile both versions with optimizations turned on, it will detect tail recursion in ExprTail, convert it into a loop, and then in-line the loop in Expr.  The resulting compiled codes will be exactly the same.


How to understand the solution to Task Scheduler problem on LeetCode?

When idleSpot (or, as in the code, idleState) is zero or negative, it means we have enough tasks other than A to fill the required minimum cooldown periods between A tasks.
Well, suppose BB are the overflowing tasks. Instead of appending them to the end of scheduling queue, we can just insert them, one right after each A.  So instead of
$\quad$A X X A X X A B _ _ B _ _
we will have
$\quad$A B X X A B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Bs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.
If we have addition overflowing tasks, such as CC, then we can do the same thing, inserting them one right after each A. So we would have
$\quad$A C B X X A C B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Cs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.
And so on.


Can we generate random numbers using irrational numbers like π and e?

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator.

Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else.
We don't actually know if every digit occurs equally often in the decimal expansion of $\pi$ or $\mathrm{e}$ (though we suspect they do).
In many situations, we require random numbers to be unpredictable (indeed, if you asked a random person what "random" means, they'd probably say something about unpredictability). The digits of well-known constants are totally predictable.
We usually want to generate random numbers reasonably quickly, but generating successive digits of mathematical constants tends to be quite expensive.
It is, however, true that the digits of $\pi$ and $\mathrm{e}$ look statistically random, in the sense that every possible sequence of digits seems to occur about as often as it should. So, for example, each digit does occur very close to one time in ten; each two-digit sequence very close to one in a hundred, and so on.


Find minimum number of points which intersect overlapping arcs

A little abstraction would help both reasoning about and solving the problem efficiently, I think.
For every point $x$ on the circle, there is some set $S_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S_x \subseteq S_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can therefore focus on a set of representative points $x_1,\ldots,x_m$ such that each set $S_{x_1},\ldots,S_{x_m}$ is maximal. There are at most $n$ such points (the proof of which I will leave as an excercise) and you should be well able to find this set in $O(n^2)$ time.
Now, if the arcs don't wrap all around the circle, i.e. there is some point on the circle that doesn't touch any arcs, then you can look at the arcs as intervals on a straight line. Given the right infrastructure (you should sort the arcs both by starting and ending angle, again easily doable in $O(n^2)$ time) you can solve this problem greedily in $O(n)$ time (cf. this post).
Finally, to solve the problem, you do as follows: For each $1\leq i\leq m$, you ask the following question: "If i use $x_i$, how many other points must I use in order to cover the arcs that are not in $S_{x_i}$?" These arcs naturally do not wrap around the circle. You can therefore calculate this in linear time, and return the minimum set of points over all tries. Since $m\leq n$, this will only take $n^2$ time in total.


Is the following Subset Sum variant NP-complete?

It is NP-hard.

Consider the following two variants:

Variant 1:

Input: $A\subset\mathbb N$, $s\in\mathbb N$.
Question: is there a set of indices $I$, $\sum_{i\in I} a_i=s$?

Variant 2:

Input: $A\subset\mathbb N$, $k\in\mathbb N$, $s\in\mathbb N$.
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=s$?

It is easy to see variant 1 is NP-hard. It is also easy to reduce variant 2 to your variant in polynomial time by transforming each element $e$ in an instance of variant 2 to $ke-s$. So if we can prove there is a polynomial-time reduction from variant 1 to variant 2, the proof is completed.

The reduction from variant 1 to variant 2 is exactly the same as the one posted by Kristoffer Arnsfelt Hansen in this answer. I rewrite it here for consistency of symbols.

Given an instance of variant 1, assume that $a_i < B$ for all $i$. We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $a_i$ we get two new elements $a^1_i = (2^{n+1} + 2^i)nB + a_i$ and $a^0_i = (2^{n+1} + 2^i)nB$. The new target sum is defined as $s' = (n2^{n+1} + 2^n + \dots + 2^1)nB + s$. The number of elements required in a solution is set to be $n$.

Note in a valid solution of the new instance, for each $i$, the number of $a_i^1$ and that of $a_i^0$ must be exactly $1$ in total, so there is exactly $n$ elements in a valid solution. This is indeed a polynomial-time reduction from variant 1 to variant 2.


The compiler can optimize exponentiation with monoids. Let $\oplus$ be a binary operator calculateable in constant time such that $\oplus$ and $a_1, a_2, ... \in A$ form a monoid. Then the operation

$$\bigoplus_{[1..n]} a_k = \underbrace{a_k \oplus a_k \oplus \dots \oplus a_k}_{\text{$n$ times}}$$

which usually takes $\cal O(n)$ time can be evaluated with the square and multiply algorithm in only $\cal O(\log n)$ time if the compiler knows that $\oplus$ obeys the monoid laws.


One approach is outlined in Tucker Balch's Machine Learning for Trading course on Udacity:

Learning T
Learning R

In a nutshell: create a $T_c$ table ("T count") that counts the number of times each subsequent state is reached after taking an action in a given state. Initialize all values to 0.00001 to avoid division by 0 errors. While executing QLearning, observe $s,a,s^\prime$ and increment $T_c[s,a,s^\prime]$.

Formula for calculating the probability of each s' from [s,a]

$$ \frac{T_c[s,a,s^\prime]}{\sum_i T_c[s,a,i]}$$

The numerator is the count of times s,a lead to each s'.
The denominator is the sum of $T_c[s,a,:]$ (normalizes each s' to its probability)

Dyna-Q then updates a state's expected reward as the weighted sum of the reward in each s' weighted by their relative probability.


It doesn't. You're biased to results you find interesting.

If we measure a particular algorithm's space $s$ and time $t$ complexity, and then improve the algorithm. One of the following things can and does happen:

We reduce $s$ and leave $t$ unchanged.
We reduce $t$ and leave $s$ unchanged.
We reduce both $s$ and $t$.
We reduce $s$ and $t$ increases. WOW!
We reduce $t$ and $s$ increases. WOW!

Now 1, 2 and 3 happen all the time. Why are you not asking for a "mathematical principle" for them?

Because they are boring. Since we strictly improved the algorithm it must mean the previous algorithm was suboptimal, and is immediately forgotten. Only in cases 4 and 5 we suddenly have two algorithms which do not have a clear winner, and only then do you start comparing them and wondering about a "mathematical principle" behind this difference.

What's happening is that given two objectives, you get a plot of possible solutions:

Anything above and to the right of the critical red line is immediately forgotten as non-interesting, as there are algorithms that are strictly better in both $s$ and $t$. Your mind only looks at the red line (also known as the Pareto frontier), ignoring the rest of the plot.


Is there a tool that can check whether m |= p holds, where m and p are both ltl formula

Yes, you can use an LTL-to-Büchi-automaton translator for this.
Let's assume that you want to check if $\psi \rightarrow \psi'$ is a valid LTL formula, i.e., every word satisfying the LTL property $\psi$ also satisfies the LTL property $\psi'$. This case is equivalent to finding out if $\psi \wedge \neg \psi'$ is satisfiable. Your $\psi \models \psi'$ notation is another way of writing this, but I would avoid it since the $\models$ relation is often defined differently in current research papers on the topic.
If we translate $\psi \wedge \neg \psi'$ to a Büchi automaton, we can easily check if its language is empty. In fact, optimizing LTL-to-Büchi translators remove states with an empty language, and hence you only need to check if the resulting automaton has no accepting state.
On example LTL-to-Büchi translator is ltl3ba. For instance, if you want to check if $\mathsf{F G }\,a$ implies $\mathsf{G F}\,a$, you can do that as follows:
./ltl3ba -f "(F G a) && !(G F a)"

Here, "-f" stands for "translate this formula that is given as a parameter".
The result is given in SPIN never claim form:
never {    /* (F G a) && !(G F a) */
T0_init:
    false;
}

There is no state ending with "_accept" in the name, which means in the SPIN never claim notation that there is no accepting state. So $(\mathsf{F G }\,a) \wedge \neg (\mathsf{G F}\,a)$ is not satisfiable.
There is also at least one LTL-to-Büchi translator with a web interface, namely the one from the SPOT framework.


How to count near circular objects in image

A simple approach to start with is to extract just the red channel, do some binary thresholding (e.g., Otsu's method), and then use standard morphology operators to find the blobs. You could try applying a closing operation.  Then, you could apply the watershed transformation or region flooding to identify the blobs where the tomatoes are.

A possibly better approach could be to convert to HSV representation, then generate a binary image as follows: every pixel whose hue matches the hue of a tomato (from some range you manually determine) is colored white, the rest are colored black.  Then you could continue with morphology operators and watershed/region flooding.

How well this will work will depend upon your requirements (e.g., whether you need to deal with occlusion) and on application-specific details (e.g., how constant in color the tomatoes are).

Take a look at the following questions on StackOverflow; they are quite relevant and will be helpful to you:

https://stackoverflow.com/q/11631188/781723
https://stackoverflow.com/q/4063965/781723
https://stackoverflow.com/q/5298884/781723
https://stackoverflow.com/q/4387488/781723
https://stackoverflow.com/q/10480609/781723
https://stackoverflow.com/q/6416117/781723
https://stackoverflow.com/q/10313602/781723
https://stackoverflow.com/q/18972932/781723
https://stackoverflow.com/q/10168686/781723
https://stackoverflow.com/q/8593091/781723
https://stackoverflow.com/q/16100708/781723

and also these resources:

http://blogs.mathworks.com/steve/2006/06/02/cell-segmentation/
http://www.mathworks.com/products/image/examples.html?file=%2Fproducts%2Fdemos%2Fshipping%2Fimages%2Fipexcell.html
https://en.wikipedia.org/wiki/Blob_detection


Recognizing waterways in an aerial photo -- polygons from edge detection images

This is hard to do with color information alone. Color variations between (or even within) aerial and satellite imagery can be huge. Ideally you will want hyperspectral or at least infrared imagery (see this paper).

Assuming your edge detection can snap to pixel boundaries, you can take each pixel's borders as a closed polygon and union them together to form a polygon (depending on your union implementation you may end up with a polygon with inner rings or holes) or a collection of polygons. The Java Topology Suite and other computational geometry implementations can make this much easier for you. If you want to use sub-pixel boundaries you will need to be very careful that you have a good epsilon value set so you can snap edges that are very close but not exactly touching.

If you want to take the edges and combine them yourself you will want to build a graph of intersecting edges and implement code that traverses the graph (e.g. counter-clockwise) to find where it closes in on itself to form a polygon. This is how some of the union implementations of polygons works.


Overflow of integer counter in distributed systems

In general:

  Paxos algorithm uses unbounded integers to tag data. In practice,
  however, every integer handled by the processors is bounded by some
  constant $2^b$ where $b$ is the integer memory size. Yet, if every integer
  variable is initialized to a very low value, the time needed for
  any such variable to reach the maximum value $2^b$ is actually way
  larger than any reasonable system’s timescale. For instance,
  counting from $0$ to $2^{64}$ by incrementing every nanosecond takes roughly
  500 years to complete. Such a long sequence is said to be practically
  infinite.

Self-stabilizing systems:

  One particular aspect of self-stabilizing systems is the need to
  re-examine the assumption concerning the use of (practically)
  unbounded time-stamps. While in practice it is reasonable for Paxos to
  assume that a bounded value, represented by 64 bits, is a natural
  (unbounded) number, for all practical considerations, in the scope of
  self-stabilization the 64 bits value may be corrupted by a transient
  fault to its maximal value at once, and still recovery following such
  a transient fault must be guaranteed.

Source: Self-Stabilizing Paxos


Those kinds of aliens presumably wouldn't use a GUI.  A GUI is a graphical user interface, i.e., directed at the visual senses.  Your aliens have no sight, and wouldn't use such a user interface.  They'd use something else.

The user interface is programmed as part of the software application.  So, you wouldn't necessarily need to change the programming language or the hardware or the OS -- just the application (and its libraries).  (Of course, you would need additional peripherals to emit smells etc., but you say you're counting that out -- apart from that, there would be no changes to hardware needed.)


What does it mean when its said that most Turing Machines are not programmable?

I think the point being made is that, as you say, the transition rules of any Turing machine are fixed in advance, so every Turing machine computes a fixed function of its input. Since the machine computes a fixed function of its input ("Count the number of 1s", "Determine if the graph represented has a perfect matching", etc.), it can't really be called programmable.

However, for some Turing machines (e.g., universal Turing machines), we treat one part of the input as being a program that should be executed using the rest of the input as input. These machines would be described as programmable in the context of the article you link.

I hereby declare actors to be programmable human beings.


How do we adjust a model to fit our own dataset?

Is this really suitable?

Well, it works.  At least, in some situations.  And in machine learning, there's a sense in which that is the bottom line: is it useful?  And yes, this approach does appear to be useful, in at least some situations.

Beyond that, I'm not sure what you mean by "suitable".

  What if the custom dataset had a lot more images than the original or is detecting completely different classes?

Sure.  There will cases where fine-tuning probably isn't what I'd recommend you try first.  Look at it this way.  Fine-tuning is one thing you can try.  It's not a silver bullet.  It may work well in some situations.  No one is claiming it will work well in all situations.  There are plenty of situations where it might work poorly.

Fine-tuning is probably most useful if your training set is small (or, at least, not very large), and if there is a pre-trained network that solves a task that is somehow similar to the task you're trying to solve.  The classes don't have to be identical -- for instance, if you are solving some kind of object detection task, but your classes aren't identical to ImageNet, then starting with a pre-trained network that was trained on ImageNet can still be useful, as the image features learned for ImageNet are likely to be useful for other object detection tasks as well -- but the task probably needs to be somehow similar.

If your training set is very large, then fine-tuning might not be the best answer.  You might do better to train a network from scratch, yourself.

Finally: Machine learning is ultimately a pragmatic field.  Don't try to look for the one right answer that works in all situations, and don't expect there to be some theory that can predict what the most effective approach to your problem will be.  Instead, understand that it's a bit of an art; trial and error is often needed; and the ultimate metric is whether it works well enough for the particular problem you are facing right now.


Optimizing neural network on small training set

This is a bad idea.  For many tasks, you'll likely get poor performance.  For many machine learning tasks, having a lot of data is essential to getting good results.

Instead, I recommend you set yourself up with software and hardware that can train your network on the full training set efficiently: buy a fast GPU, use software that can use the GPU for training, use stochastic gradient descent with mini-batches and other standard techniques.

You'll likely need to optimize all of your hyper-parameters on the full training set.  I don't think optimizing the hyper-parameters on a small training set is likely to work well.  If there's any past research on similar machine learning tasks, you might look at what network architecture and hyper-parameters they used as use that as a starting point for your exploration.


SAT solvers for use in $P^{NP}$ and $NP^{NP}$

We don't know that PH doesn't collapse to NP. We don't even know that PH doesn't collapse all the way to P.
The best you can say is that you can use SAT solvers to solve problems in one of these classes iff PH collapses to NP.


How to generate response variable during machine learning?

No.  You can't.  You need ground truth.  You're asking "if I don't know which claims are fraudulent, can an algorithm somehow determine that for me?"  The answer of course is no: the algorithm doesn't know anything more than you do about insurance fraud -- if anything, it knows even less.

This is one of the challenges with using machine learning.  You typically need a lot of labelled data: data that has been labelled with ground truth (e.g., whether the insurance claim is legit or fraudulent).  Supervised learning is data-driven: given some instances where we know the correct answer, it tries to figure out some rules to use to classify other instances where we don't know the answer.  For this to work, it needs a training set of instances where we do know the correct answer.

Now there are some techniques that can be helpful.  You might be able to use active learning to try to figure out claims to manually label, to try to reduce the number of examples you need to label.  You might be able to use clustering to cluster the instances, and then hand-label a few instances from each cluster.  But ultimately, you'll need some labelled instances to train on and evaluate the accuracy of your method.

See also How to identify labels in unsupervised learning? and Why is automatically labeling data in unsupervised learning hard? and
What exactly is the difference between supervised and unsupervised learning? and
What would be a decent threshold for classification problem?


What is the importance of c in big O notation?

Let's suppose the constant $c$ wasn't there: let's say that $f(n)=O'(g(n))$ if $f(n)\leq g(n)$ for all large enoun $n$. So, for example, $n=O'(n^2)$ and $\log n = O'(n)$, as you'd expect. But let's look at some functions whose growth rates are closer. First, let $f(n)=n+1$ and $g(n)=n$: well, $f(n)\neq O'(g(n))$ because $n+1 \not\leq n$ for all $n$.  Similarly, $2n\neq O'(n)$. SO, we see that the  constant $c$ is absolutely essential to the definition of $O(-)$: it just doesn't do what we want it to do if we remove it.

$O(-)$ measures the growth rate of functions ignoring constant factors. It gives you notation to say things like "$f$ is linear" or "$f$ is quadratic".  When we say "$f$ is linear", we don't distinguish between, say, $f(n)=n$ or $f(n)=4n$ or $f(n)=2n+12$: we ignore the constants. The constant $c$ in the definition of $O(-)$ allows it to ignore multiplicative constants and additive terms.


Very nice question!

You are twice right:

Propagating the number of items in the knapsack does not lead to optimal solutions.
One solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative

In the following, I am assuming that you are familiar with the solution based in dynamic programming. In particular, I will not discuss how to traverse the table backwards to determine the solution.

Let us first focus on the typical case: the number of items is unrestricted. In this case, you just build a table $T$ where $T_{i,j}$ contains the optimal value when the overall capacity of the knapsack equals $i$ and only the first $j$ items are considered. From here:

$T_{i,j} =\max\{T_{i,j-1}, T_{i-w_j,j-1}+v_j\}$

where $w_j$ and $v_j$ stand for the weight and value of the $j$-th item respectively. If $C$ is the overall capacity of your knapsack and there are in total $N$ items the optimal solution is given by $T_{C, N}$. This algorithm is known to run in pseudo-polynomial time and one of its beauties is that it only considers those combinations that fit the maximum capacity.

However, this is not enough when adding your constraint: a maximum number of items $p$. The reason is that the previous recurrence formula does not take into account different combinations of items:

First, if $T_{i,j-1}<(T_{i-w_j,j-1}+v_j)$ then $T_{i,j}=(T_{i-w_j,j-1}+v_j)$ so that the $j$-th item is added to the knapsack in spite of the maximum number of items considered, $p$ ---so that you might be violating your constraint. Well, you might be tempted here to apply the preceding formula keeping track of the number of items inserted at each step and do not add others if the number of items currently in the knapsack exceeds $p$ but,
Second, if $T_{i,j-1}>(T_{i-w_j,j-1}+v_j)$ then $T_{i,j}=T_{i,j-1}$ so that this item is not added but that might be a big mistake in case the optimal solution $T_{i,j-1}$ already consists of the maximum number of items to insert into the knapsack. The reason is that we are not properly comparing: on one hand, to preserve the optimal solution consisting of $p$ items selected among the previous $(j-1)$; on the other hand, to insert the $j$-th item and, additionally consider the best subset with $(p-1)$ items among the previous $(j-1)$.

So that a first solution consists of adding a third dimension. For your case, let $T_{i, j, k}$ be the optimal solution when the capacity of the knapsack is $i$, only the first $j$ items are considered and it is not allowed to put more than $k$ items in the knapsack. Now,

If you are computing $T_{i, j, k}$ for a number of items strictly less or equal than the number of items that can be inserted ($j\leq k$) then proceed as usual but using the same value of $k$: $T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k}+v_j\}$
Now, if you have to compute $T_{i, j, k}$ for a number of items strictly larger than the number of items that can be inserted ($j> k$) then: $T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k-1}+v_j\}$

The first expression should be clear. The second works since the $(k-1)$-th layer of the table $T$ keeps track of the best combination of $(k-1)$ items among the first $(j-1)$ as required above.

An efficient implementation of this algorithm does not need to compute $T_{i, j, k}$ for all $k$. Note that the preceding recurrence relationships relate layer $k$ with $(k-1)$ and thus, it is possible to alternate between two successive layers (e.g., if you are interested in the optimal solution with $k=4$ you just use two consecutive layers: 0 and 1, 1 and 2, 2 and 3, 3 and 4 and you're done). In other words, this algorithm takes twice the memory required by the traditional approach based on dynamic programming and thus, it can be still run in pseudo-polynomial time.

Be aware, however, that this is not the only solution! And there is another you might find more elegant. In the preceding formulae, we retrieved the optimal solution which consisted of no more than $(k-1)$ items among the first $(j-1)$ as $T_{i, j-1, k-1}$. However, it should be clear that this is precisely equal to $\max\limits_{p=0,j-1}\{T_{i, p}\}$ just by using the original table!! ie., the optimal solution with no more than $k$ items can be also retrieved by considering the optimal solutions with 1 item, 2 items, 3 items, ... $(j-1)$ items ... To make this formulation work you should also keep track of the number of items considered in every partial solution so that you will need two integers per cell. This memory occupation results in precisely the same memory requirements of the algorithm shown above (using a third dimension in the form of layers $k$).

Hope this helps,


Is the system of measuring length in the US Turing complete?

The post you're referring to is a joke: the US (and similar British Imperial) measurement systems are not Turing complete and the claim is an example of hyperbole.

A key feature that's necessary for a system to be Turing complete is that the system must include computations that do not terminate ("infinite loops").  Although it's not clear exactly what computations can be modeled by unit conversions (or what that even means!), any unit conversion within the diagram takes a finite number of steps.


Extracting features for texture classification

If it is important for you to get a high accuracy, then use a convolutional neural network (ConvNet). These ConvNets hold the state of the art for most visual recognition tasks. If your training set size is small, you should use a pretrained ConvNet as a feature extractor and then apply a support vector machine (SVM) on top of the extracted features.

I can recommend Keras as a good toolbox for ConvNets that is simple to use. You should be able to find a pretrained ConvNet for Keras by searching Google. VGG or ImageNet are names of well-performing ConvNets (particularly the former) so that is worth searching for.


Can the complement of a non-recursive language be RE

From your question I believe there is some confusion of the terms being used here. A recognizable language L is one such that a turing machine exists accepting it,  halting on every yes instance. There are also co-recognizable languages, those are languages whose complements are recognizable. Now, if a language happens to be both recognizable and co-recognizable, it is recursive, or decidable (why?). So a language can be non-recursive, but it may still be recognizable or co-recognizable. What can you say about the emptiness problem for turing machines $E_{TM} = \{\left < M \right >\ :\ \mathcal L(M) = \varnothing\}$ ?


It is necessary to minimize the functional

This problem is exactly the problem of finding the minimum $(s,t)$ cut in a directed graph, where $s$ is the upper-left corner and $t$ is the lower-right corner.  All the vertices on the $s$ side of the cut will be assigned height 0; all the vertices on the $t$ side of the cut will be assigned height 1; and the capacity of the cut is equal to the sum of the counts on the edges that cross the cut in the $s\to t$ direction.  You want to minimize this sum, so you want to find the minimum $(s,t)$ cut. There are many standard algorithms for doing that, based on finding a maximum flow and then applying the min-cut max-flow theorem.


You can do it in linear time, using an efficient selection algorithm.

Find the median, and partition the array into numbers below the median and numbers above the median.  Check whether the number you're looking for is above or below the median.  Then, recurse on the appropriate partition.

The running time satisfies the recurrence $T(n)=T(n/2)+O(n)$, since you can find the median and partition the array in $O(n)$ time.  The solution to this recurrence is $T(n)=O(n)$, so the total running time is $O(n)$.  This is faster than your $O(n \log n)$ time algorithm.


Has the concept of using a hand checked simple theorem prover to validate more complex theorem provers been explored before?

Not that I know of.  A more typical architecture is to decompose the theorem prover into a prover plus a proof checker.  Then only the proof checker needs to be validated.  If proofs are expressed in a simple enough language, then the proof checker might be extremely simple.  All of the smarts can go into the prover (which tries various strategies to try to find a valid proof), but it doesn't need to be validated, since its output will always be checked by the proof checker.


Please trace the following code.

Integer[] a = {2, 4, 6, 8,  1, 3, 5, 7}; // an array of 8 elements.
Integer[] aux = new Integer[a.length];
merge(a, aux, 0, 3, 7);

You will find the number of compares is $7= 8-1$.

Here is a fact about general situations.

(Number of compares) Let a be an array of distinct elements. The elements from a[lo] to a[mid] is sorted increasingly. The elements from a[mid+1] to a[hi] is sorted increasingly. Then the compare less(a[j], a[i]) will be run at most hi-lo times in the call merge(a, aux, lo, mid, hi). In particular, if there is $n$ elements in a, there will be at most $n-1$ compares. If we assume lo < mid and mid + 1 < hi, it will be run hi-lo times if and only if a[mid - 1] < a[hi] < a[mid] or a[hi - 1] < a[mid] < a[hi].

Proof of "only if ": Note that after each comparison, either j is increased by 1 or i is increased by 1. The value (j-(mid+1)) + (i-lo) is increased always increased by 1.

Consider the point of time when the last comparison less(a[j], a[i]) happens. The value (j-(mid+1) + (i-lo) = hi - lo - 1. Since j <= hi and i <= mid, we must have j=hi and i = mid.

Now consider the point of time when the second last comparison happens. After that comparison, if i will be increased by 1 and we will find that a[mid - 1] < a[hi] < a[mid]. Otherwise, j will be increased by 1 and we will find that a[hi - 1] < a[mid] < a[hi].

Proof of "if" is skipped.

Exercise 1. What if lo = mid or mid + 1 = hi?

Exercise 2. What if there are repeated elements in a?


(operationalizable) Cost measure for small problems

When we talk about complexity in computer science we are usually talking about asymptotic complexity. We are interested in characterizing the complexity of a process as the size of its inputs increase. This is useful because it abstracts away implementation-specific characteristics, such as processor speed or architecture or available memory. So while asymptotic analysis does, in this sense, concern itself with "large problems," its intent is not so much to treat large problems as it is to provide a meaningful metric for comparing algorithms in terms of time and space efficiency.

Kolmogorov complexity does not, to my knowledge, find applications in the practical analysis of programs or computational processes. It is an information-theoretic measure concerned with the minimal length of data as represented in a computational system. In so far as using it in any sort of "operational" analysis like those you've proposed, the big roadblock is that the Kolmogorov complexity of an arbitrary string is not, in general, computable!

It's difficult to pin down exactly what you're asking for, but it sounds more akin to counting CPU cycles required to execute a series of instructions. Back in the old days, when assembly language on punch-cards was the state-of-the-art, this was a fairly common technique used for optimization.

As it applies to your example, adding two numbers would involve loading them, bitwise, into registers, performing the addition, and storing the result. If the addends required more bits to represent than the size of the registers, you'd have to do it piecewise, loading and storing intermediate results as needed. You can count the cycles needed to execute tasks of varying 'difficulties' (adding two 1-byte numbers vs. adding two 2-byte numbers, for example) and compare them to give some sense of how much more or less 'complicated' the execution of a given sequence of instructions is.

It's not complexity in the traditional CS sense, but it would be a quantifiable, implementable metric. Donald Knuth has a program here that counts the cycles required to execute MMIX programs, as an example of such an implementation.


Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables

As a very general heuristic, it's likely true that bigger problems are harder than smaller ones and benefit from more searching. Bigger populations, longer runs, etc. can be beneficial in that case.

The real question is whether your algorithm is converging or not. If you're converging before you find a good answer, more generations isn't going to help.


Show that the string $( [ ) ]$ is not in a Dyck language

Consider producing a leftmost derivation of ( [ ) ]. We can begin with
$$
S\Rightarrow SS\stackrel{*}{\Rightarrow}SS\dotsc S
$$
and to get the ( on the left we must eventually use the production $S\rightarrow(S)$ on the leftmost $S$, giving
$$
S\stackrel{*}{\Rightarrow}(S)S\dotsc S
$$
and then we'll have
$$
S\stackrel{*}{\Rightarrow}(SS\dotsc S)S\dotsc S
$$
and to get the [ as the second terminal on the left we must eventually use the production $S\rightarrow[S]$, giving
$$
S\stackrel{*}{\Rightarrow}([S]SS\dotsc S)S\dotsc S\stackrel{*}{\Rightarrow}([SS\dotsc S]SS\dotsc S)S\dotsc S
$$
and now we're stuck, since no production will give us the ) terminal we need on the left without introducing a ( first.

For a slightly different take, consider that $S$ can only derive strings in $D_2$, so to  derive ( ]  ) ] we must use the production $S\rightarrow (S)$, where the $S$ in the right term of the production must also derive a string in $D_2$, but that would imply $S$ derives ], which cannot be, since $]\notin D_2$.


Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.


Calculating decimal digits of pi, using something similar to a Bailey–Borwein–Plouffe formula

The Bailey–Borwein–Plouffe formula only works in hexadecimal. There might be other formulas for other bases, but I'm not aware of a decimal-based formula. If you want to obtain the $N$th decimal digit, you have to compute enough hexadecimal digits, there are no shortcuts.


When can the coinduction hypothesis be used?

First, let me recall least and greatest fixed points for $\subseteq$. We are working relative to some set $U$, the universe. In the case of (co)inductive definitions, $U$ is the set of all terms. A function $f:2^U\to2^U$ (from subsets of $U$ to subsets of $U$) is monotone, if $A\subseteq B$ always implies $f(A)\subseteq f(B)$. A fixed point of $f$ is a set $A$ such that $f(A)=A$.

For monotone $f$ there always is a least fixed point $\mu f$, namely the intersection of all $A\subseteq U$ such that $f(A)\subseteq A$. Least means that for arbitrary fixed points $F$ we always have $\mu f\subseteq F$.

For an example, let $f_{\tt nat}$ be defined by $f_{\tt nat}(A)=\{0\}\cup\{n+1\mid n\in A\}$. The function $f_{\tt nat}$ is the one-step closure function under the constructors $0$ and $+1$. The condition $f_{\tt nat}(A)\subseteq A$ means that $A$ is closed under the constructors $0$ and $+1$. The intersection means that the $\mu f_{\tt nat}$ contains only those elements which are in every set closed under the constructors. These happen to be the natural numbers.
The example shows how the inductive definition of natural numbers is the least fixed point of closure under the natural numbers' constructors. Generally, inductively defined sets are least fixed points of closure under constructors.

Dually, for monotone $f$ there also is a greatest fixed point $\nu f$, namely the union of all $A\subseteq U$, such that $f(A)\supseteq A$. Greatest means that for  arbitrary fixed points $F$ we always have $\nu f\supseteq F$. To make the duality complete, let us note that intersection is the $\subseteq$-infimum and union the $\subseteq$-supremum and thus the $\supseteq$-infimum. So, in fact, greatest fixed points for $\subseteq$ are just least fixed points for $\supseteq$ and vice versa.
(Also, observe that the requirement of monotonicity is the same for $\subseteq$ as for $\supseteq$.)

Now, for proof techniques. Let us begin with the example of induction on natural numbers. To show that some property $P$ holds for all natural numbers, we show that $P(0)$ and that $P(n)$ implies $P(n+1)$. Viewing $P$ as a subset of $U$ (the set of all elements where the property holds), the proof obligation for natural induction is that $P$ is closed under $f_{\tt nat}$. Correctness of the proof technique of natural induction then follows from the definition of least fixed point: If $f_{\tt nat}(P)\subseteq P$, then $P$ is part of the intersection that forms $\mu f_{\tt nat}$, so the property holds throughout $\mu f_{\tt nat}$, that is $\mu f_{\tt nat}\subseteq P$.

Induction is just the generalization of the previous paragraph to arbitrary monotone $f$ instead of $f_{\tt nat}$. Coinduction is the dual of induction: The proof obligation is $f(P)\supseteq P$. This means that if $P$ holds on some element $x$, then $x$ is constructed using only base elements on which $P$ also holds.
So, instead of showing that the property survives application of constructors, we have to show that it survives deconstruction. Once the proof obiligation is satisfied, we obtain $\nu f\supseteq P$.

What good is the conclusion $\nu f\supseteq P$? Let us reconsider $P$ not as a property but as a subset of $U$. The conclusion of coinduction establishes that all elements of $P$ are well-formed members of the coinductivly defined set $\nu f$.
This is what happens in the example in What is coinduction? showing forall n, Infinite (from n). Here, $f$ is closure under the constructors of Infinite (not of colist!) and $P$ is the set of all terms of the form from n for some n.


Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $\langle M,w \rangle$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in $L$. Then using a universal Turing machine start to run/simulate $M_L$ on both inputs $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$, simultaneously, say one step at a time for each input. After each step check if $M_L$ halts on at least one input. Since $L$ is r.e. and exactly one of $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ belongs to $L$, $M_L$ must eventually halt on one of them. Depending on which input $M_L$ halts, you can tell if $M$ halts on $w$. This decides the Halting problem and hence $L$ is not r.e.


Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

The Proof is on Theorem 2.5 of the section 2.3. If you consider the polyhedron with artificial variables and redundant equality constraints as P and original with no artificial variables and no redundant equality constraints as Q. As you may see, they assumes that the l(th) basic variable is an artificial variable, so remove it will not affect original polyhedron. On the Example 3.8, the last tableau with artificial variables shows a case where a row becomes zero. If this happens with non artificial variable we have a degeneracy case.


Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta

Since $f(n) \in \Theta(n^2)$ there exist two constants $n_0$ and $c>0$ such that $f(n) \ge c n^2$ for all $n \ge n_0$.
Suppose then that $f(n) \in O(n)$. For some $n'_0$ and $c'>0$, we have
$f(n) \le c'n$ for all $n \ge n'_0$.
Selecting $n = \max\left\{ n_0, n'_0, 1+\left\lfloor \frac{c'}{c} \right\rfloor \right\}$ leads to the following contradiction:
$$
c' n\ge f(n) \ge c n^2 \ge c \cdot \left(1+\left\lfloor \frac{c'}{c}\right\rfloor\right) \cdot  n > c \cdot \frac{c'}{c} \cdot n = c'n.
$$


Simple elementary cellular automata with high period?

Used symbols will be $0, 1$, table $T$ with $18$ elements ($L=18$), and one element for register $B$.
Initialize table with any configuration with at least one element set to $1$.

At generation step do:
B = T[0] Xor T[7]
T[i] = T[i - 1]
T[0] = B

The array bounds act like wall, if you read from outside you get $0$. This is simple rewrite system, with minimal number of operations without any fancy operations, only rewrite by one calculate xor of two cells  (hey, Rule 90 takes three), and has period $262143$ giving all $18 bit$ numbers excluding $0$.

How to get such system? This is Linear feedback shift register which fits your description of PRNG, has the highest possible period ($2^L-1$) for given number of bits (cells?) minus 1, the best one would have $2^L$.


Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.


Correctness proof of greedy algorithm for 0-1 knapsack problem

Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.


If you think about this program, you will realize pretty quickly that the vectors you're pushing onto the stack iterate over the values [a^3 + b^3, a, b] for all $1\leq a, b\leq N$  This means you're pushing $N^2$ items onto the stack over the course of the program.

Since each removal (and push, depending on the implementation of the PQ) takes $\Theta (\lg N)$ time, your algorithm would run in $\Theta (N^2\lg N)$ time.  There's a straightforward $\Theta (N^2)$ solution, so you're not optimal yet.


How might I express a sequence of operations in formal terms?

Take a look at Gurevich's abstract state machines. See also the abstract state machine homepage. A key paper is Gurevich's Sequential Abstract State Machines Capture Sequential Algorithms.


Minimum sub-tree of a graph that covers each color at least once

The OP has noticed that "for k=3, it becomes tricky". Indeed, the problem with variable $k$ with respect to $|V|$ is NP-complete and, hence, NP-hard.

Let us formalize the problem so as to able to prove it rigorously. This colored nodes covering problem, called for brevity CNC, is defined in decisional form as follows:

Instance:

a connected graph $G = (V, E)$;
a positive integer $k\le|V|$ and a map $C:V\to\{1, 2, \cdots, k\} $, called coloring map with $|C(V)|=k$;
a positive integer $m$

Question: Is there a subtree $T=(V', E')$ of $G$ that $|E'|\le m$ and $|C(V')|= k$?

Claim: Colored nodes covering problem (CNC) is NP-complete with respect to $|V|$.

Proof of the Claim.

It is easy to see that CNC is in NP. Let us reduce the Steiner tree problem, called for brevity ST, one of the NP-complete problems in Karp's original paper to CNC.

Let us recall ST can be defined in decisional form as follows:

Instance:

a connected graph $G = (V, E)$;
a subset of the nodes $R\subseteq V$ , called terminal nodes;
a positive integer $m$.

Question: is there a subtree of $G$ that includes all the nodes of $R$ and that contains at most $m$ edges?

Let us show a polynomial-time reduction from ST to CNC by building an instance of CNC starting from a generic instance of ST. Given a generic instance $s$ of ST, defined by a graph $g=(V,E)$, the set of terminals $R=\{v_1, v_2, \cdots, v_k\}\subseteq V$, and the
upper-bound $m$, define an instance $c$ of CNC as the following.

the same graph $G=(V,E)$.
the coloring $C: V\to\{1,\,2,\,\cdots,k,\,k+1\}$, $C(v_i)=i$ for $1\le i\le k$ and $C(v)=k+1$ otherwise.
the same upper bound $m$.

If the induced graph $G[R]$ is connected, then both $s$ and $c$ can be determined in polynomial time in $|V|$ (in fact, constant time), since the spanning tree of $G[R]$ is a tree with the minimal number, $k-1$ of edges that can include all vertices of $R$.

Otherwise let us assume $G[R]$ is not connected. Then any subtree of $G$ that contains all nodes of $R$ must contain at least one node that is not in $R$, which must be colored $k+1$. For any subtree $H$ of $G$, $H$ includes all the nodes of $R$ and contains at most $m$ edges if and only if $H$ includes nodes of every possible color under $C$ and contains at most $m$ edges. That is, $s$ has a yes answer if and only if $c$ has a yes answer.

It is easy to see that the transformation from $s$ to $c$ can be done in polynomial time (in fact, constant time). So we have reduced ST to CNC by a polynomial-time reduction.

Bonus exercise: is the colored nodes covering problem with fixed $k$ NP-hard? This is not an easy exercise. Here is a hint.

   No. My first step toward demonstrating the existence of a polynomial algorithm is noticing that there will be at most $|V|^k$ choices of the nodes in the subtree that will be mapped to all colors. ($|V|^k$  can be lowered to $(|V|/k + 1)^k$, which does not affect the logic though). It will take some time to reach a full proof.


How to prove Halting problem is solvable by oracle machine

An oracle machine is a regular machine, such as a Turing machine, with an attached device that is an oracle.  This oracle, often called a black box to signify that it is not constructible in the real world, answers questions about some set.

For instance if the oracle is a $K$ oracle then it can answer yes or no whether numbers are in the set $K$ (I'm taking $K$ to be the name of the set of natural numbers $e$ such that Turing machine $e$ halts on input $e$).  So obviously the Halting Problem can be solved by a machine that has access to this oracle.


What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$

We can split the sum:

$$S \;=\; \sum_{i=1}^n \left(1 + \lfloor \log_2 i \rfloor\right) \;=\; \sum_{i=1}^{n/2} \left(1 + \lfloor \log_2 i \rfloor\right) + \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 i \rfloor\right)$$

Then as a lower bound it is allowed to drop the first sum and only look at the second sum. Furthermore, we are allowed to replace $i$ in the loop body with just $n/2$, as $i \geq n/2$ in the second sum.

$$S \;\geq\; \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 n/2 \rfloor\right) \;\geq\; (n/2)\cdot\lfloor \log_2 n/2 \rfloor$$

$$S \;\geq\; (n/2)\cdot(\log_2 n - \log_2 2 - 1) \;\geq\; \frac{1}{2}n\log_2 n - n $$

$$S \in \Omega(n \log n)$$

As an upper bound we can replace $i$ in every term by $n$ and similarly to above we get:

$$S \;\geq\; n(1 + \log_2 n)$$

$$S \in O(n \log n)$$

Therefore we can conclude that asymptotically $S \in \Theta(n \log n)$.


How come $REC$ languages are included in $NRE$

I've never seen "NRE" defined to mean "not recursively enumerable", which is the short way of saying what you've defined.  If you take it to mean "not recursively enumerable" then no recursive language is in NRE because every recursive language is recursively enumerable.

The only definition of "NRE" that I've seen is that people in the field of DNA and membrane computing seem to use it for the set of Turing-computable sets of natural numbers, i.e., the sets that can be written as $\{|x|\mid x\in L\}$ for some RE language $L$.


Does mutual exclusion hold in this case?

Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.

You state that you feel that this interpretation is wrong, but you have not been able to prove your intuition. You cannot prove a definition! What you are really saying is that the concept of mutual exclusion is vacuous if no process is ever in a critical section. To some extent you are correct—this agrees with colloquial usage. The same colloquial usage also states that "A or B" has the connotation of "A or B, but not both". When dealing with formal concepts you have to forgo the colloquial point of view, trading it with the mathematical point of view.


The question is asking you to find a suitable group $\Gamma$ and a subset $S$, so that $CG(\Gamma,S)$ is the n-cube.

Since by definition of $CG$, the nodes are the elements of $\Gamma$, you don't have a choice here, leaving the group operation and $S$.

$xy$ and the inverse of $y$ are then understood with respect to the group operation you choose.

Also be aware that the identity element being in $\Gamma$ does not imply that all other vertices are connected with it, since the edges are determined by $S$, not $\Gamma$.


Is the set of TMs that does not reach most cells to the right computable?

Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

Given $x$, $M'$ overwrites $x$ with $\langle M\rangle$ up to length $|x|$ or end of $\langle M\rangle$, whichever comes first. Writes blanks on the rest of $x$, and puts an end marker on cell $|x|+1$.
$M'$ returns to the beginning of input and simulates $M$.
If $M$ accesses end marker at any point, $M'$ enters an infinite loop without moving any further to the right.
If $M$ accepts, $M'$ goes infinitely to the right.

Note this $M'$ has the following properties:

If $M$ halts on $\langle M\rangle$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
If $M$ does not halt on $\langle M\rangle$ then $M'$ will never access $|x|+10$th cell.


Proving that the conversion from CNF to DNF is NP-Hard

Informally:

In DNF, you can pick any clause to be true, to make the formula true. This means that a DNF that is equivalent to a certain CNF, is basically an enumeration of all the solutions to boolean sat on the CNF. Note, there can be an exponential number of solutions. Since solving boolean sat for CNF for a single solution is NP-complete, converting to DNF essentially means solving for every solution. So it is at least as hard as Boolean SAT, and is thus NP-hard.


Dynamic testing of down casts as explained in TAPL

The first rule T-Typetest is a type-checking rule. Let's read it together. Firstly, $\Gamma$ is not important (on a first reading at least). We have the following premises:

$t_1$ has type $S$
if $x$ has type $T$ then $T_2$ has type $U$
$t_3$ has type $U$

The conclusions is, that we get an expression of type $U$ (I think your transcription should have "$: U$" instead of $\to t_3$ the conclusion):
$$\mathrm{if}\; t_1 \;\mathrm{in}\; T \;\mathrm{then}\; x \to t_2 \;\mathrm{else}\; t_3 \tag{1}$$
The meaning of this expression can be undrstood by looking at the other two rules, which are small-step operational semantics. Here is an incorrect explanation, which we will make correct in a moment:

If $t_1$ has type $T$ then (1) evaluates to $t_2$ with $x$ replaced by $t_1$. This is the case of "downcast", i.e., $t_1$ is downcast from $S$ to $T$, the downcast value is bound to $x$ and then $t_2$ is executed.
If $t_2$ does not have type $T$ then (1) evaluates to $t_3$. This is the "default" which we use when the downcast is not possible.

The above explanation is incorrect because we should use $v_1$ instead of $t_1$, by which the author is telling you: first evaluate $t_1$ to $v_1$, and then perform the downcast.

In an imaginary OO language the same thing might be written somewhat like this:

S t1 = ...;
...
if (t1 instanceof T) {
  T x = (T)t1;
  t2;
} else {
  t3;
}


I'd check what happens for some small(ish) values of initial $n$, working up. If you know who wins if there are at most $n$ on the table, working out what happens with $n + 1$ is easy.


Finding Minimum Weight Subgraph Spanning Tree

No, it's highly unlikely there is a polynomial time algorithm for this problem. The problem you describe is known as Steiner tree, and it is NP-hard. Moreover, it is computationally quite difficult from many other viewpoints as well.

A classical dynamic programming approach is the Dreyfus-Wagner algorithm running in $O^*(3^k)$ time, where $k$ is the number of terminals (i.e., the size of the set of pairs $S$ in your terminology). There is a lot of literature on the problem, so you might want to look at it from a particular viewpoint.


Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

Yes, you need up to $n$ stack frames for the recursion.  Therefore, you'll need $\Theta(n)$ space for these stack frames.


I modern architectures the peripheral has direct access to the system RAM independent of the CPU and what it is executing. This is called a DMA (direct memory access) transfer.

In other words when the interrupt is raised the entire transfer is already completed and you can read the data transferred.


Understanding depth-limited BFS time complexity

There are two cases.

First. $V-1 \leq E$. Then $O(V \cdot (V + E))$ and $O(V \cdot E)$ are equivalent.

Second. $E < V-1$. Then graph is disconnected and the biggest component has size at most $E + 1$. The whole algorithm will consist of $V$ BFS runs each on the component which has at most $E + 1$ vertices and at most $E$ edges. So each BFS run will take $O(E)$ time and the whole algorithm - $O(VE)$.

Note: this reasoning does not depend on $k$.


Is the power of a regular language regular? Is the root of a regular language regular?

The language $L_2$ is not necessarily regular. Indeed, consider $A = a^*b$. If $L_2$ were regular, then so would the following language be:
$$L_2 \cap a^*ba^*b = \{ a^nba^nb : n \geq 0 \}.$$
However, this language is not regular (exercise).

In contrast, the language $L_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L_1$ have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. The states of the new DFA are labeled by functions $Q \to Q$. The idea is that the new DFA is at state $f\colon Q \to Q$ if the original DFA moves from state $q \in Q$ to state $f(q)$ after reading $w$ (i.e., if $\delta(q,w) = f(q)$ for all $q \in Q$). The initial state is the identity function. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) = \delta(f(q),\sigma)$. A state is accepting if $f^{(n)}(q_0) \in F$ for some $n \geq 0$.


How many thresholds and distance matrix are in Eigenface?

I'll begin with an apology since I will probably not answer your question as you expect (mostly because I don't understand exactly what you are asking).

Let's recap the process of face recognition using Eigenfaces.

take each image of $d_1$ by $d_2$ and treat it as a $d_1\cdot d_2$ vector (images should be in greyscale).
compute the mean of the vectors in hand, i.e. if you have m images, $X_{mean}=\frac{1}{m}\sum_{i=1}^mX_i$ and move your samples such that the a-prior mean is is zero, (this is an important step that is commonly forgotten).
compute the covariance matrix, $X^TX$. I assume in your scenario $d_1\cdot d_2>>m$, so you obtain the same information by finding $XX^T$ eigenvalues, this could improve your running time significantly.
project the $m$ images over the $p$ eigenvectors corresponding to the largest eigenvalues.
Given a new image, project it using the matrix $[u_1,...,u_p]$ and run K-Nearest-Neighbour (it should be more than sufficient for your purpose).

I think your original question is regarding the classification process after you have projected the images over the principal components.
I the algorithm above, I suggest using KNN.

A few notes:

Eigenfaces don't work so well in reality, you must use images with very similar orientation, otherwise you won't achieve good results.
How to choose the k in the nearest neighbour algorithm? it depends on the number of training examples you have, obviously, there is no point of choosing k to be larger then the number of examples per person.
regarding point 3 above, $X^TX\in M_{(d_1\cdot d_2)\ x\ (d_1\cdot d_2)}, XX^T\in M_{mxm}$, so if your images are over 100 by 100, it's practically a must.
a couple of useful links:

http://docs.opencv.org/modules/contrib/doc/facerec/facerec_tutorial.html
http://vision.ucsd.edu/content/yale-face-database

Good Luck!

Addition:

http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
After obtaining the first p Eigenfaces (which are the first p eigenvectors of $X^TX$), you have a matrix $O\in M_{(d_1\cdot d_2)\cdot p}$, given a new image $x\in \mathbb{R}^{d_1\cdot d_2}$, project $O^Tx$, this is a vector in $\mathbb{R}^p$.
Now you have your samples in $\mathbb{R}^p$, your original training samples, and a new image that was projected over $O$, you know want to ask yourself how to classify the new image, one way is to decide by finding the closest vector using $L_2$ or $L_1$ this is the same as using KNN with k=1.
I suggest you read about KNN from the link above.

to sum it up:

compute the projection matrix $O$
project your training data $z_i=O^Tx_i$.
given a new sample, $\overline{x}$, compute $\overline{z}=O^T\cdot\overline{x}$
now you have vectors in $\mathbb{R}^p$, you run the KNN which is an iterative way to find the k closest vectors, and classify your new vector as the majority of the k vectors.


$L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

Some people (including more than one moderators) complained to me for posting an answer based on a comment, and I am tired of defending me from them.  I asked them to delete this answer.


How can I complete my derivation of an algorithm to solve Sudoku puzzles from my formalisation of the rules?

One method of dealing with these, somewhat, emergent rules is constraint solving. You can iterate through each cell and place constraints on other squares based on that cell.

For example, if a square is 3, you can place a "cannot be 3" constraint on all other squares in its row, column, and 3x3 box. The two examples you provided can be solved once you place all the constraints, and look at what options are available.

This sort of method is very similar to what you would do when solving a sudoku puzzle when you write down the possible numbers in each square, and fill a box in when there is only one possibility.


Show that P is closed against the Kleene star

Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial time.


Number of double wedges containing a point

The set of $2n$ lines on the plane form a well studied Arrangement of lines, which is a type of planar subdivision, composed of vertices, edges and faces. This planar subdivision used to be represented by DCEL. There are two types of algorithms, which can convert a bare set of lines into the DCEL - plane sweeping algorithm with time complexity $O(n^2log(n))$, and incremental one with time complexity $O(n^2)$. Both these types are described in this book (Item 8.3). The resulting subdivision will have $O(n^2)$ faces.
Given a planar subdivision with $O(n^2)$ faces we can convert it further into a hierarchical data structure, which can be used to locate a face, containing any query point, in $O(log(n))$ time. This is a topic with long history - please see the Point location page for more information.
So, if we assign a number of double wedges, containing a point, to each face of the planar subdivision - we'll solve the exercise. Let's find out how we can do just that.
Each double wedge defines four parts of the plane, and we need to define clearly, what parts are inside the wedge. In order to do that we'll split each boundary line into two rays - one pair of "incoming" rays and one pair of "outcoming" rays. We'll consider a part of the plane, lying to the left of each such ray, to be inside the double wedge.

The direction of these rays can be used to calculate the number of intersecting double wedges (called below an intersection number), corresponding to each face of the planar subdivision. It's easy to see, that these numbers for adjacent faces differ by one. Even more, if we jump from some face to another face over a boundary edge, directed from the left to the right, we'll need to increment this number. If the boundary edge is directed from the right to the left, then this number needs to be decremented. An example of two double wedges $w1$ and $w2$ with assigned intersection numbers (in red) is below.

So, the algorithm to assign intersection numbers to faces comprises of two steps:
Step 1. Take an arbitrary initial face and calculate its intersection number, using all the $n$ double wedges - it can be done in $O(n)$ time.
Step 2. Traverse all the faces of the planar subdivision, starting from the initial face and assigning the intersection number using boundary edges direction as described above - it can be done by the DFS in $O(n^2)$ time.


It's still in NP by using a truth assignment as a proof.

You can reduce 1-in-3 SAT to 1-in-$k$ SAT to show hardness as follows. Let $\phi$ be an instance of 1-in-3 SAT with clauses $C_i$ for $1 \le i \le m$. For each $C_i$ we define $C_i'$ by adding $k - 3$ instances of the literal $y$ (where $y$ is a new variable that does not appear in any $C_i$). We also construct the new clause $C_{m+1}'$ which has $k-1$ occurences of the literal $y$, and one occurence of the literal $\neg y$. Let $\phi'$ be the instance of 1-in-$k$ SAT with clauses $C_i'$ for $1 \le i \le m+1$. I claim $\phi'$ is a YES-instance of 1-in-$k$ sat if and only if $\phi$ is a YES-instance of 1-in-3 SAT.

First, assume $\phi'$ is a YES-instance, and choose a satisfying assignment. $C_{m+1}'$ is satisfied only when $y$ is false, so this assignment has $y$ false. Therefore, the literals $x$ are not satisfied, and so exactly one of the first 3 literals of $C_i'$ is satisfied for each $i$. These are exactly the literals of $C_i$, so exactly one of the literals of $C_i$ is satisfied for each $C_i$ and so $\phi$ is a YES-instance.

In the other direction, suppose $\phi$ is a YES-instance, and choose a satisfying assignment. Extend this assignment to give $y$ the value falsehood. This assignment shows that $\phi'$ is a YES-instance.

To illustrate the reduction, here is an example (going to 1-in-5 SAT):

$\phi = (x_1 \vee \neg x_1 \vee x_2) \wedge (x_3 \vee \neg x_2 \vee \neg x_2)$

$\phi' = (x_1 \vee \neg x_1 \vee x_2 \vee y \vee y) \wedge (x_3 \vee \neg x_2 \vee \neg x_2 \vee y \vee y) \wedge (y \vee y \vee y \vee y \vee \neg y) $


If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?

NP-hardness is a property of decision problems. It doesn't matter whether you define it using Karp reductions or Cook reductions.

NP-hardness and NP-completeness are defined using Karp reductions. If you prove that a problem is Cook-NP-hard, then it doesn't imply that it is Karp-NP-hard. Indeed, coSAT (the collection of unsatisfiable CNFs) is Cook-NP-hard but probably not Karp-NP-hard. Under reasonable hardness assumptions, there are even problems in NP which are Cook-NP-hard but not Karp-NP-hard. See for example Mandal, Pavan, and Venugopalan, Separating Cook Completeness from Karp-Levin
Completeness under a Worst-Case Hardness
Hypothesis.


Computing maximum-cost subtree that uses at most k edges

Say our tree is $T = (V, E)$ with weight function $w : E \to \mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges.
There is a $\Theta(nk^2)$-time and $\Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming.
Idea: Store in every node $v$ the maximum weight obtainable using $i \in 1, \dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b_l, k_l)$ and $(b_r, k_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b_l + k_l + b_r + k_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes.
Details:
for v ∈ V {
  for i ∈ [1..k] {
    v.maxWeight[i]   = 0
    v.chooseLeft[i]  = 0
    v.edgesLeft[i]   = 0
    v.chooseRight[i] = 0
    v.edgesRight[i]  = 0
  }
}

globalMax = [null, 0, -1]

def annotate(v) {
  if v is not a leaf {
    annotate(v.left)
    annotate(v.right)

    for i ∈ [1..k] {
      for j ∈ [0..i] {
        w  =   [j > 0]   * w((v, v.left))  + v.left.maxWeight[max(0,j-1)]
             + [i-j > 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)]

        if w > v.maxWeight[i] {
          v.maxWeight[i]   = w
          v.chooseLeft[i]  = min(j,1)
          v.edgesLeft[i]   = max(0,j-1)
          v.chooseRight[i] = min(i-j,1)
          v.edgesRight[i]  = max(0,i-j-1)
        }
      }

      if v.maxWeight[i] > globalMax[2] {
        globalMax = [v, i, v.maxWeight[i]]
      }
    }
  }
}

annotate(T.root)

What remains then is to move top-down from globalMax[0] and follow the chooseX[_] links with edgesX[_] to construct the optimal subtree with globalMax[1] edges and weight globalMax[2].
Proof of correctness (by induction) and analysis are elementary.
The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{\operatorname{deg}(v)}$ then, if implemented naively.


Designing a context free grammar for a language; When to use the empty string

You can use the empty string, $\epsilon$ liberally. It could help you conceptualize the grammar easier and faster. For example, as you said, because $v\in\{a,b\}^∗$ that v can be one of $a,b$ or $\epsilon$, therefore using $\epsilon$ will help you to isolate non-terminal symbol $v$ as generating all words over the alphabet $\{a,b\}$ using just three rules.

On the other hand, language $L$ in the question, $L= \{a^{2i}b^{j}vc^{j}(ac)^{i} |  i,j \ge 0, v \in \{a,b\}^*\}$ can be generated by a context-free grammar without $\epsilon$ except one rule, $S\to\epsilon$. Here it is.

$S \rightarrow aaSac|B|aaac|\epsilon$
$B \rightarrow bBc|B|bc$
$C \rightarrow aC|bC|a|b$

You can obtain the above grammar by following the procedure to eliminate ε-rules, which can change any context-free grammar to an equivalent grammar that either does not use $\epsilon$ or just uses it once in the rule $S\to\epsilon$.  Note that if the language includes the empty string, at least one usage of $\epsilon$ is inevitable; otherwise, it can only generate non-empty words. Finally, a grammar in Chomsky Normal form is designed to be such a grammar.

Just in case you might think every context-free grammar will use $\epsilon$ at least once, here is a grammar that does not use $\epsilon$.

$S\to a$.

In fact, for every grammar in Chomsky Normal form that uses $\epsilon$, you can remove that single rule, $S\to\epsilon$ to obtain a new grammar that does not use $\epsilon$. The languages generated by these two grammars are the same except the former one contains the empty string while the latter one does not.


A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

Since both $A$ and $\overline A$ are recognizable, you know that for any input $x$, either

$x \in A$, which means that $T_A$ will halt on input $x$, or
$x \notin A$, which means that $x \in \overline A$ which means that $T_{\overline A}$ will halt on input $x$.

The "trick" here is to run $T_A$ and $T_{\overline A}$ "simultaneously", which means that if any of $T_A$ or $T_{\overline A}$ halts after $k$ steps, then your new machine will halt after $2k$ steps.

If you don't like "simultaneously", you can for each integer $i$ from 0 and up, run $T_A(x)$ for $i$ steps, then run $T_{\overline A}(x)$ for $i$ steps.
The latter is simpler to "program" on a single-taped Turing machine, but the former is quite okay to implement on a two-taped Turing machine.


How to tackle Big O proofs that involve multiple parameters

That isn't true. As you say, it implies there are $c_2$ and $N$ so that for all $n \ge N$ you have $a^n \le c_2 \log n$. Consider:

$\begin{align*}
  \lim_{n \to \infty} \frac{a^n}{\log n}
      &= \lim_{n \to \infty}
                \frac{a^n \log a}{1 / n}
      = \infty
\end{align*}$

Here we used l'Hôpital. But that the limit is infinite means that eventually the ratio is larger than any given $c_2$. In fact, it proves $a^n = \Omega(\log n)$.


Are problems that are fractions of constraints of NP-complete problems also NP-complete?

There is no general rule that they necessarily need to be NP-complete in general.
For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.


creditcard validation - why does nit not fail for 7 digits?

Luhn's algorithm, as described in Wikipedia, works for any number of digits. It will detect any single digit change and most swaps.

As for an internet website which accepts credit card numbers of the wrong length - the blame should be on the designers of the website who neglected to enforce this restriction, not on Luhn's algorithm, which performs as advertized.


Equivalence relations with $\cap$, $\cup$ and $\circ$

Here are some hints:

a) If $E_1,E_2$ are equivalence relations then so is $E_1 \cap E_2$. The proof is just by "unpacking" the definitions. (More generally, every class defined by universal statements – those of the form $\forall x_1,\ldots,x_n \phi(x_1,\ldots,x_n)$ – is closed under intersection.)

b) When trying to prove that $E_1 \cup E_2$ is transitive, we get stuck in the following case: if $a E_1 b$ and $b E_2 c$ then we have to show that $a E_1 c$ or $a E_2 c$, though there is no reason to believe that this must be the case. This helps you construct a counterexample.

c) When trying to prove that $E_1 \circ E_2$ is symmetric, we get stuck: if $a E_1 x E_2 b$ then there is no particular reason that $b E_1 y E_2 a$ for some $y$. This helps you construct a counterexample.


How to devise an algorithm that suggests feasible cooking recipes?

Hmm, using Bayes Theorem to make new recipes out of old recipes. I imagine you first would want the algorithm to pull apart the ingredients into a form it understands (not sure if we are using NLP for that, or if you manually enter the data in yourself, that's neither here nor there.) From there...

I envision something like this.

Test Data analyzed. Now we have a list of recipes and the probabilities that each ingredient will take place alongside another ingredient, and in what quantities. After we have this data then you would have the program randomly make the new recipes. First it cycles through a list of all the known ingredients, then randomly selects a main ingredient, from there it uses the probabilities of an ingredient given another ingredient to start throwing in more random ingredients, all the while matching appropriate trained data for quantities and compatible ingredients.

Might I suggest that when creating a new recipe the program be given information like, I want something sweet, or something sour, or for instance something mostly made up of wheat.

Hopefully this helps a bit.


What is meant by a preemptive algorithm?

An arbitrary algorithm can't be preemptive or non-preemptive. Preemption is a mode of multitasking, used by an operating system to control user processes. From the Preemption Wiki page:

  In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time.

The opposite of Preemption is Cooperative Multitasking.


Given a total recursive function, can you always compute its fixed-point?

The proof of the recursion theorem is constructive: it gives you an algorithm to compute $n$ from $f$. See for example these notes of Rebecca Weber.


Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of

a read-only input tape, surrounded by endmarkers,
a finite state control,
a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
a stack

In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, and Computation (1st ed.) we find:

Theorem 14.1 The following are equivalent for $S(n)\geq\log n$.

$L$ is accepted by a deterministic $S(n)$-AuxPDA
$L$ is accepted by a nondeterministic $S(n)$-AuxPDA
$L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

Corollary $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking.

The above is a copy of large parts of an answer to another question. So in which sense does it answers the current question? It is not the smallest imaginable class that contains $\mathsf{CFL}$ and is closed under nondeterminism. But it is a very well known class (i.e. $\mathsf P$) and a natural machine model, which has been studied thoroughly in the past, and is still studied today (with an additional runtime restriction) in the context of LogCFL. Indeed, LogCFL is also closed under nondeterminism and is closer than $\mathsf P$ to $\mathsf{CFL}$, proving my point that the above (i.e. $\mathsf P$ = $\log n$-AuxPDA) is not the smallest imaginable class of this kind.


Finding a non-boundary, local optimum of a non-convex function over a convex feasible region

Your question is not well-defined yet.  You have described two criteria you want to optimize over: minimize the function, and be away from the boundary.  You often can't simultaneously optimize both; the way to minimize the function might be near the boundary, and points away from the boundary might not minimize the function.

So, before you can solve this problem, you first must figure out how to formulate it in a well-posed way.  Basically, you will have to decide how to trade off between your two goals.  One way would be to define an objective function $\Psi(x)$ that is a sum of your function and some penalty term, where the penalty is larger the closer to the boundary you are.  e.g.,

$$\Psi(x) = f(x) + 1/d(x),$$

where $f$ is your function and $d(x)$ is the distance from $x$ to the nearest point on the boundary of the feasible region.  Then, you could try to minimize $\Psi(x)$.  That's one possibility, but there are of course others.  (This particular approach is sometimes known as a barrier method.)

Once you have formulated the problem, then you can select an optimization algorithm.  Gradient descent would be a good starting point if the problem is high-dimensional and you can compute gradients.  If the number of dimensions is not too large, you can also consider second-order methods, like Newton's method, trust region methods, and many others.  The choice of method will depend on the properties of the function, and might also require some experimentation.

Alternatively, rather than treating both goals as soft goals to be balanced, you might decide that the "away from the boundary" is a hard requirement that absolutely must not be violated.  Then you would define the region $\mathcal{R}$ of points that are away from the boundary (e.g., distance at least $D$ from the boundary, for some constant $D$ of your choice), and then your problem becomes to minimize $f$ over the region $\mathcal{R}$.  There are a number of methods for doing that; you might start by trying projected gradient descent.

If you want to detect whether all minimizers are near the boundary, you can first find the absolute minimum within the feasible region (e.g., using gradient descent or projected gradient descent), then find the minimum within the region $\mathcal{R}$ of points that are away from the boundary (e.g., using projected gradient descent); if the latter is larger than the former, you know that all the minima are near the boundary (at least, up to the optimality of your optimization routine).

We can't tell you how to formulate your problem, because that depends on what you want to achieve, and only you know that.  You will have to decide what your goals and requirements are, and then choose a formulation that matches your needs and goals.


An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.


How many times do we access memory with a TLB?

Many systems use more than one level of page tables, so you may need to access memory more than two times.

With a TLB and assuming you have a cache hit, then you will only need to access memory once since TLBs are usually implemented in hardware. Otherwise, you will have to access memory the same amount of times you would if you didn't have a TLB (such as if the TLB is empty).


This is called the subset sum problem.  There's lots written about the problem; go read about it.

How you could have figured this out on your own: you already know it is a variant of the knapsack problem, so if you had read the Wikipedia page on the knapsack problem, you would have encountered a description of the subset sum problem in the section of that page on variations of the knapsack problem.  In the future, I encourage you to do  research before posting, to make sure your question isn't already answered in the obvious places (e.g., Wikipedia, textbooks).


L-attributed definitions are definition whose attributes can be evaluated in depth-first order (as they say in the first sentence).
The statement "L-attributed definitions include all syntax-directed definitions based on LL(1) grammars" is perhaps a bit subtle. It's not saying that the two sets of definitions are the same; rather, that syntax-directed definitions "based on LL(1) grammars" are a subset of L-attributed definitions.
That's true because the predictive parser based on the LL(1) grammar visits the parse tree in strictly depth-first order. This was already noted in Designing a Predictive Parser in Section 2.4 of the text book, which goes on to build a recursive-descent parser illustrating how this works.