Deriving the average number of inversions across all permutations

You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".

A boring proof using induction is here.

For a constructive proof, you can follow the idea from here:

Show that the maximum number of inversions is $\binom{n}{2}$.
Observe that every permutation and its reverse pair up: their respective
sets of inversions are complement to each other, so both together add $\binom{n}{2}$ inversions to the sum.
Since this pairing neatly and uniquely covers all permutations, we get that the total number of inversions across all permutations is $\frac{n!}{2} \cdot \binom{n}{2}$.

The claim follows immediately.


Computer Architecture, cache hit and misses

You may wish to ask your TA/Prof. what they mean by "0.5% global miss rate". The way I read it is the following:

  Out of $x$ accesses to the L2 cache, $0.005x$ accesses are a miss.

This interpretation makes more sense than assuming the miss rate is out of all the store/load instruction.

So each miss of the L1 cache becomes an access to the L2 cache, and out of these, 0.5% are a miss at the L2 cache. From here, it seems you can fill out the details by yourself, building on your own attempts.


How to prove the outcome of both segment of code are equal

Proof idea: first of all note that the version A is a recursive version of B.
Both A and B halts when $y$ is 0, so in both cases computation lasts until $y$ reaches zero. In both versions the return value is $x$. Also note that each recursive call corresponds to a single step in the while loop. So you can prove that after each recursive call and after each step of the while-loop values of $x$ and $y$ are equals. Induction on the number of steps where we assume $x, y > 0$.

Base step: step 1. In the recursive call (version A) $y$ value is passed as an argument and assigned to $x$ (stored in $x$), but new $y$ takes $x\%y$. In other words, ($x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$). Similarly, in the version B the following assignments

int t = y;
y = x % y;
x = t;

implies that $x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$. So after the first step in both segments  new $x$ and new $y$ values are equal.

Induction: assume that after $n$ steps of recursive call and while-loop $x$ and $y$ values are equal. Then by the same argument as in the Base step for step $n+1$ $x_{new}$ and $y_{new}$ in both codes are equal. Thus, when we $y = 0$ both segments return $x$s which are equal.

Alternatively, you could separately prove that both functions compute gcd of two integers $x$ and $y$ and deduce that they must give the same output for same inputs $x$ and $y$. You can do it yourself. Please look here.


Are there any countable sets that are not computably enumerable?

Are there any examples of countable sets that are not enumerable?

Yes.  All subsets of the natural numbers are countable but not all of them are enumerable.  (Proof: there are uncountably many different subsets of $\mathbb{N}$ but only countably many Turing machines that could act as enumerators.)  So any subset of $\mathbb{N}$ that you already know is not recursively enumerable is an example – such as the set of all numbers coding Turing machines that halt for every input.


So you have a bunch of functions $f_1, \dots, f_k$ from $\mathbb{N} \to [0,1]$ and want to combine them to a new one. There is a myriad of possibilities, e.g.

$f(n) = \prod_{i=1}^k f_i(n)$,
$f(n) = \frac{1}{k} \cdot \sum_{i=1}^k f_i(n)$,
$f(n) = \sum_{i=1}^k c_if_i(n)$ for $\sum_{i=1}^k c_i = 1$ and $c_i \geq 0$,
$f(n) = \min\{f_1(n), \dots, f_k(n)\}$,
$f(n) = \max\{f_1(n), \dots, f_k(n)\}$,
$f(n) = \operatorname{median}\{f_1(n), \dots, f_k(n)\}$,
$f(n) = f_1( \lceil 1000 \cdot f_2 ( \lceil 1000 \cdot f_3( \dots )\rceil)\rceil)$,

or any other of infinitely many choices. Without context, it is impossible to know which one yields something meaningful in your context.


I want to design a context free grammar for the following

Since this seems very much like homework, i will give you a little Hint, taking as example a sub-case of your language:

The GFC for the string $a^3b^3$ is the following:

$S ⇒ aSb$

$aSb ⇒ aaSbb$

$aaSbb ⇒ aaaSbbb$

$aaaSbbb ⇒ aaabbb$

You can take the above as a starting point from which to adapt the grammar to your case.


How many states when converting CFG to PDA

When converting CFG to NPDA ,then to simplify the process, first convert the CFG to Greibach Normal Form(GNF). Now using three states: Qstart, Qloop and Qaccept, you can generate all transition rules for the NPDA.

To start the process add the transition: $ δ(Qstart,λ,z)=\{(Qloop,Sz)\}$ where S start variable and z is stack start symbol.

And add the following transition to get the NPDA into a final state:$ δ(Qloop,λ,z)=\{(Qaccept,z)\}$.

Now using the production rules of the CFG you can easily generate all the other transitions which includes only $Qloop$. And here the number of transitions depend on the number of production rules.


Are process-safe mutexes shared between OSes?

For most implementations of a mutex it won't work, but in principle it depends on how the mutex is implemented.  If the mutex was implemented using files, perhaps it could be made to work.  Usually the mutex is managed by the operating system, and the operating system keeps track of the state of the mutex, so both processes have to be running in the same operating system to be able to share a mutex.


Question about NP problem certificates and P=NP

Your problem is in the black box or oracle setting, that is, you are given access to the input as a black box rather than explicitly. You can contrast your problem with 3SAT, in which the input is a formula. One way to solve 3SAT is to try plugging in solutions at random (or systematically) and checking whether they satisfy the formula. However, better approaches are known, and these approaches use the explicit description of the formula.

The P vs NP question is in the white box setting – concretely, $\mathsf{P} \neq \mathsf{NP}$ is equivalent to the conjecture that no polynomial time algorithm solves 3SAT. Results in black box settings are irrelevant (at least directly) to the P vs NP question.

In the black box model we can also separate P from BPP (at least for promise problems), by considering the problem of finding a zero input for a balanced Boolean function. However, for explicit inputs, it is considered likely that P=BPP. This shows that the black box setting exhibits different behavior than the white box setting.

Black box settings are common in optimization, where often we are looking for algorithms which do not rely on the exact form of the input function. For example, in submodular optimization we are given a submodular function as a black box. One method for proving lower bounds in this area is the indistinguishability method, in which we construct two black boxes which are identical on most inputs but have a very different optimal solution. This method is technically much easier than similar results in the white box setting (for example, in the special case of set coverage functions or cut functions), which rely on PCP theory.


Characterizing the range of a polytime function

Your statement (with length increasing replaced with length non-decreasing and with functions allowed to return $\bot$, i.e. nothing) is equivalent to $\mathsf{P}=\mathsf{NP}$.

We start with two observations:

Every language in $\mathsf{P}$ is trivially the image of a length non-decreasing function (that's why we allow returning $\bot$).
If $f$ is a length non-decreasing polytime function then $y$ is in the range of $f$ iff there exists $x$ of length at most $|y|$ such that $f(x) = y$, and so the range of a length non-decreasing polytime function is always an $\mathsf{NP}$ set.

If $\mathsf{P}=\mathsf{NP}$ then the range of a length non-decreasing polytime function is always in $\mathsf{P}$, and so your (modified) statement is correct.

Suppose now that $\mathsf{P} \neq \mathsf{NP}$. Consider the language $\mathsf{SAT'}$, obtained from $\mathsf{SAT}$ by padding a formula of length $n$ with $n$ zeroes. The language $\mathsf{SAT'}$ is still $\mathsf{NP}$-complete and so not in $\mathsf{P}$. On the other hand, it is in the range of a length non-decreasing polytime function: the polytime function accepts a formula $\varphi$ and an assignment $x$, and if $x$ satisfies $\varphi$ it outputs the padded version of $\varphi$.

As I mentioned, you to allow the function to not decrease the length if you want $\Sigma^*$ to be the range of some function. On the other hand, the reasoning above works as long as the function doesn't decrease the length by too much: any polynomial amount (which could depend on the function!) would work.

You can also get rid of $\bot$ if you assume that the languages you consider are not too (efficiently) sparse, that is, given a length $n$, one can find in polytime some word in the language of length at least $n$. This is the correct counterpart of the condition of being infinite.


If $a,b$ are both positive integers, then we can always write $a = kb+\ell$ where $0 \leq \ell < b$. We call $\ell$ the remainder and $k$ the quotient. In your first example, $5 = 2 \cdot 2 + 1$ so 5 % 2 == 1. In your second example, $2 = 0 \cdot 9 + 2$, so 2 % 9 == 2. More generally, if $a < b$ then a % b == a.

There is also a rule for signed integers, but unfortunately I can't remember it. Also, 0 % x == 0 whenever $x \neq 0$, and x % 0 will cause an exception ("division by zero").


If a language is contained in other langauge, is it of the same complexity?

No. $\Sigma^*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.


A function computable using a circuit of size $10s$ but not of size $s$

One possible approach is as follows. A counting argument shows that there are function on $n$ bits that require circuits of size $\Omega(2^n/n)$, and on the other hand a non-trivial construction that you probably saw in class shows that every function on $n$ bits can be computed using a circuit of size $O(2^n/n)$. This takes care of the case $s(n) = 2^n/{100n}$.

For general values of $s(n)$, you can use functions depending on $m \leq n$ variables, making sure that the resulting lower bound $\Omega(2^m/m)$ and upper bound $O(2^m/m)$ fit snugly around $s(n)$.


How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

If the statement you're trying to prove by induction is

  For all positive integers $n$, a complete binary tree with $n$ nodes has $\lceil{n/2}\rceil$ leaves.

then the induction hypothesis must be

  For all positive integers $k<n$, a complete binary tree with $k$ nodes has $\lceil{k/2}\rceil$ leaves.

Similarly, if the statement you're trying to prove by induction is

  For all positive integers $n$, a hoosegow with $n$ whatsits has $2^{\lfloor\sqrt{n}\rceil!}\cdot n^\pi$ nubbleframets.

then the induction hypothesis must be

  For all positive integers $k<n$, a hoosegow with $k$ whatsits has $2^{\lfloor\sqrt{k}\rceil!}\cdot k^\pi$ nubbleframets.


Splicing squares on a Turing Machine finite tape

Yes, it has the same computing power as an ordinary TM.

It's a standard exercise in computation theory/complexity theory textbooks that the ability to insert characters into the tape (and delete them from it) can be simulated by a standard Turing machine with a quadratic loss of efficiency. For example, this is Exercise 2.8.8 of Papadimitriou's book (Computational Complexity, Addison Wesley, 1994); he doesn't give a name to this extension of the standard Turing machine or attribute it to anyone which suggests to me that it's folklore – he's pretty good at citing and attributing.
Since you can insert characters at will, reaching the end of the initially finite tape makes no difference: you can just use insertion to extend the tape. A halting computation will only need to do this a finite number of times.
The infinite tape of an ordinary TM is just a definitional convenience: it suffices to have a finite tape that gets extended any time the head reaches the end.


Non-deterministic Turing machine that halts on at least one branches of computation

The strings accepted by a NTM M is the language of M, noted L(M)

Let us say that M for any input is not guaranteed to halt on all branches.
Then M clearly cannot be a decider, and is thus only a recognizer. M recognizes the language of all strings, for which any branch of M ends in an accepting state.

Since M is a recognizer, it is only guaranteed to accept a string if the string is in L(M).
Given a string, that is not in L(M), it may reject the string, or loop forever.
Any NTM can be simulated by a DTM, but if NTM only recognizes a language L, its equivalent DTM will also only recognize L.

If the NTM halts on all branches for any input it is a decider, then the equivalent DTM will do the same and thus be a decider as well.

A verifier is not the thing you are looking for. In Sipsers book, Introduction to the Theory of Computation, the verifier is introduced when talking about complexity of algorithms and complexity classes, because any language L is in NP if and only if it has a polynomial time verifier.

A verifier for a language L will take as input a string w in L and a certificate c (think of the certificate as a solution to the problem w) and verify that the certificate is in fact a correct solution, which makes w lie in L.

Example:

For the language

L = { w | w is an integer for which the product of some of the digits equals 12000 }

You can make a verifier V, that takes a string w in L, a certificate c, and verifies that w is in fact in L using the certificate c. c could be a binary string indicating the integers in w for which the product of equals 12000.

For example, V must reject the input 1923423343, 0010111011, because 2*4*2*3*4*3 = 576 != 12000

For many problems, we only know an algorithm that can solve them running in exponential time of the input size. This is why verifiers are interesting, because it is often the case, that we given a solution quickly can determine if that solution is correct or wrong.


Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma

Take a larger $i$. The concept is that gaps between $|2^n|$ get bigger than $|y|$.


Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

It's obviously wrong. As an example take f(n) = 2, g(n) = $1 + e^{-n}$.

log f(n) = 1, log g(n) ≈ $e^{-n} / \log e$.


Is type-checking "syntactic" or "semantic"?

Although I personally would describe type analysis as semantic, this question seems to start with the assumption that there is a clear, formally-definable dividing line between "syntax" and "semantics".

I don't think that is the case; even if most of us would put type-correctness  into one category and missing parentheses into the other one, there is a fuzzy area in the middle where the answer is much less clear.

Consider, for example, the common case of a language which requires identifiers to be declared in the scope in which they are used. Clearly, then, the following is an error: (leaving aside the precise syntax of the language)

function ilog2(a:int) => int
  if a > 0 then
    let log:int = 0
    while a > 1
      a = a / 2
      log = log + 1
    end
  end
  return log
end

Many people would argue that the use of log in the return statement is a semantic error, since it has to do with the set of definitions in the outer scope of the function. On the other hand, it is quite feasible to construct a grammar (not a context-free grammar, but a grammar nonetheless) which rejects this program. It's not a coincidence that this scoping rule is called "lexical scoping" rather than, for example, nested semantic scoping.

A context-sensitive grammar can accomplish that in a straight-forward fashion by scanning backwards (and forwards, if declarations are allowed to follow use) skipping over inner scopes until it finds a declaration for the used identifier. Of course, that's not a very efficient algorithm but it's reasonable to assume that there are more efficient ways to implement such a grammar.

Even more generally, in the lengthy discussions which lead to the formalism of Algol 68, Adriaan van Wijngaarden proposed a syntactic formalism (link taken from this Wikipedia article) powerful enough to not just encompass declarations, but also to encompass static type checking. Although not everyone will agree with the judgement, van Wijngaarden's proposal was considered readable enough that it was eventually used in the formal definition of Algol 68. In that definition, type agreement (other than discriminated unions) is guaranteed by the grammar, while semantics is reserved for questions like the precise meaning of the + operator.

In retrospect, Van Wijngaarden's formalism turned out to be far too powerful to allow for automated parser generation, but it did spawn a number of simplified and less powerful formalisms, collectively called "attribute grammars", which have the potential to expand the formal power of syntactic descriptions while remaining practical tools for compiler writers. (There are few practical demonstrations, but there is still hope. :-) )

In short, if you consider "syntax" to be intimately linked to a particular syntax formalism (and hence to a particular parsing algorithm), then you will probably be able to make a clear distinction between syntax and semantics, but it might turn out to be a different distinction made by someone using a different parsing algorithm. So it's hard to see how write universal and non-overlapping definitions of syntax and semantics.


Let's assume the user needs to enter a password and then press OK. Let's assume the password is 42:

But let's say the user makes a mistake, how can we allow three tries? By adding failure states, waiting for OK, and if we're in a failure state when OK gets pressed we get another try. Let $*$ notate 'anything else' - any character that wasn't handled by another arrow.


Generally, does the time it takes to compute (n mod m) depend on the size of n?

Yes. You are doing long division. Whatever method you use, you will lose you a roughly constant number of digits per step, so there will be twice as many (well, about $\frac{190}{90}$ times as many) steps for $b$ as for $a$.


I think I solved my problem...

Just as a simple numerical example: $2^6 = 2^{2\cdot3} = (2^{2})^3 = (2^{3})^2$

So if we have $2^{ct(n)}$ for some positive integer $c$ (as in the definition of O-notation) then we can choose a different base s.t. it is a power of two to the $t(n)$ power:
\begin{equation}
  2^{ct(n)} = (2^{c})^{t(n)}
\end{equation}

Then clearly, we can choose $c$ s.t. $2^c \geq b$. Hence:
\begin{equation}
  b^{t(n)} \leq (2^c)^{t(n)}
\end{equation}

Now multiplying the LHS by $t(n)$ does not matter because I can still easily choose $c$ s.t:
\begin{equation}
  t(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

Finally, we see that: \begin{equation}
ct(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

because we can still easily choose $c$.

EDIT I made a mistake with thinking of the $t(n)$ term in front of $b^{t(n)}$ as a coefficient... Anyway, here is a revised solution:

\begin{align*}
O(t(n)b^{t(n)}) =& 2^{O(t(n))} \\
ct(n)b^{t(n)} =& 2^{ct(n)} \\
ct(n)b^{t(n)} =& (2^c)^{t(n)} \\
2^{\log_2(ct(n))}b^{t(n)} =& (2^c)^{t(n)}
\end{align*}
Now suppose $b=2$. Then we can see that the term $2^{\log_2(ct(n))}$ is dominated by $2^{t(n)}$. i.e.
\begin{equation}
  2^{\log_2(ct(n))}2^{t(n)} = 2^{\log_2(ct(n)) + t(n)} = 2^{O(t(n))}
\end{equation}
Now, for $b\geq 2$ we know the $2^{\log_2(ct(n))}$ is negligible and so we are left with:
\begin{align*}
 O(b^{t(n)}) =& 2^{O(t(n))} \\
 cb^{t(n)} =& (2^c)^{t(n)}
\end{align*}
I think these two are asymptotically equivalent in the sense that $b$ is fixed and then we can choose some $c$ to satisfy the above, but what happens to the $\leq$ in the definition of $O$-notation?

Is this revision correct?
How does one read the original expression intuitively? Usually if you have $f(n) = O(g(n))$, we can think that $f$ is "bounded by" or "at most" $g$. In this scenario we have another $O$-notation as an exponent.


Best solutions to 6 degrees of separation

You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether each element belongs to the first list.

To determine whether the lists intersect, you have two options: either sort the first list, or put it into a hash table. The second uses more space but it's faster. (You will need counterparts of these, a balanced binary tree or a hash table, to generate the lists in the first place.)

Practically speaking, you would apply the following optimization: first determine all nodes at distance 1 from A and all nodes at distance 1 from B, and check whether the lists intersect. Then check all nodes at distance 2 from A against all nodes at distance 1 from B. Then check all nodes at distance 2 from A against all nodes at distance 2 from B. And so on. If the distance is less than 6, then you potentially save a lot of time and space.


What is the sequence of numbers for N = 6?

Here is one possible algorithm:

If $N = 0$, output the empty string.
If $N = 1$, output "0 1".
If $N = 2$, output "0 2 2 3".
If $N = 3$, output "0 2 4 3 4 5".
If $N = 4$, output "0 2 4 6 4 5 6 7".
If $N = 5$, output "0 2 4 6 8 5 6 7 8 9".
Otherwise, output the empty string.

Now, this is probably not the answer they were expecting, but it's perfectly valid.

(The answer they expected was: output the first $N$ even integers starting with zero, and then the first $N$ integers starting with $N$.)


Recurrence relations that do not have a closed form solution

Yes, there are. Consider the recurrence $a_{n+1}=(7a_n/4 + 1/2) - (5a_n/4 + 1/2)(-1)^{a_n}$ where $a_0$ is a given integer value. It is well known that this gives the Collatz sequence. There is no "known" closed form solution to the recurrence (and if you find it, you would be quite famous in mathematical circles). Furthermore, it is also well known that there are recurrent sequences that can't be solved in closed form. For instance, Conway shows that a natural generalization of the Collatz problem is undecidable. On the other hand, there are large classes of recurrence relations for which methods are known to determine closed form solutions in terms of sometimes multiple finite or infinite sums. Hypergeometric functions can be used to solve large classes of them. For instance, in theory, all linear recurrences with polynomial coefficients can be solved. More information can be found in Solving Linear Recurrence Equations with
Polynomial Coefficients by Petkovsek and Zakrajsek (PDF).


Deciding whether the head of a TM remains in K slots?

Hint: Given a Turing machine $M$, you can construct another Turing machine $M'$ with the following properties:

If $M$ halts then $M'$ halts.
If $M$ doesn't halt then the head of $M'$ eventually reaches the $K$th square from the right for every $K$.

This construction can be used to show that the halting problem reduces to your problem.

As you mention, given $K$, your property is decidable. This shows that your problem is $\Sigma_1$-complete.


Which is easier for human perception: type of variable before or after its name?

I don't think there is any research (with good methodology) on this. The language I'd most expect to have actually thought about this and made an empirically-based decision is the Quorum programming language. It uses a "type before variable name" approach (though it does put the return type of a method declaration after the parameter list). However, what I believe is the primary source for the language design decisions, An Empirical Investigation into Programming Language Syntax (available via the first author's web site), does not mention this aspect or suggest that it was studied in the research reported on in that paper. There is other research by that group and research by others that was used to design Quorum, so it's possible it is covered in that other research. I haven't read it all. You can try contacting one of the creators of Quorum and asking them if they made that decision based on empirical research. If you do and you get a positive response, I would highly recommend self-answering this question with a reference to the research.


Is it viable to use an HMM to evaluate how well a catalogue is used?

Ad Question 1: Assuming that your assumptions on how the catalogue is used -- that is the choice of the next cell only depends on the current (or constantly many preceeding) cell(s), not the (full) history -- then yes, you can use a Markov Chain to model it.

However, you do not seem to need the "Hidden" part; this is only useful if you have (probabilistic) output in the states which you observe. In contrast, you want to observe the students' cell states directly.

Imagine you can not observe which cells students are in but only how much they like the current cell; this could be implemented by notorious "Was this useful to you?" buttons; in general, assume every students gives feedback from $\{1, \dots, k\}$ in every cell but you do not know which cell they are in. Then you can use a HMM to estimate their cell sequence given their feedback sequence.

Ad Question 2: Let me illustrate the use continuing above train of thought. For $n=k=3$, we have the following Markov chain:

[source]

$p_{i,j}$ is the probability to transition from state $i$ to state $j$; note that $p_{i,0}=0$ for all $i$ and those edges have been left out¹. Let $p_{i,\bot}$ the probability of terminating in state $i$ (we leave out another dummy state for clarity). $q_{i,l}$ is the probability to emit $l$ when entering (or, equivalently, leaving) state $i$; this models our feedback. Of course, we require $\sum_j p_{i,j} + p_{i,\bot} = \sum_l q_{i,l} = 1$ for all $i$.

Note that the state sequence $0,1,2$ has probability $p_{0,1} \cdot p_{1,2}$ -- that is a central property of Markov chains. The output sequence $1,2$, on the other hand, has probability $q_{0,1}\cdot p_{0,1}\cdot q_{1,2} + q_{0,1}\cdot p_{0,2}\cdot q_{2,2} + q_{0,1}\cdot p_{0,3}\cdot q_{3,2}$.

In a real world scenario, we would have to train our Markov chain. Let us assume we have some sequences of both state and output²:

$\qquad \begin{align} &(0,1), (1,1), (2,1), (3,1) \\
                      &(0,2), (1,3), (3,1) \\
                      &(0,1), (3,3), (1,2)
\end{align}$

Now we just count how often each transition and output happened and set our probabilities to the relative frequencies³:

[source]

Now you can do the interesting stuff. Ignoring the output, you can determine the path with highest probability, you can determine the output sequence with highest probability but most importantly, and here the hidden part comes into play, you can find the most likely state sequence given an output sequence with Viterbi algorithm.

Bottom line: yes, you can use Markov chains resp. hidden Markov models (depending on your needs) to model your scenario. Wether the fundamental assumption -- the probability for the next cell only depends on the current cell -- makes sense is another question entirely.

We need a starting state, but we can make it a dummy by never going back. We can ignore its output or introduce a dummy output that is only and always emitted in state $0$.
If we have only output sequences, we can use the forward-backward algorithm.
Due to our low number of observations, we have a number of impossible transitions/emissions. Usually you assume that everything is possible and has just not been observed due to low probability. We can compensate for this by adding $1$ to all counts; this way, all sequences have probability $\gt 0$.


Do real world computers use the Turing Machine mechanism?

Turing machines were invented by Turing in his 1936 paper on computable numbers and the halting problem. It was one of a few models floating around at that time (like Church's $\lambda$ calculus, which had been defined earlier). All these models have later been shown equivalent, so if you're only interested in computability, then the Turing machine model is as good as any other model.

Modern computers are not based on the Turing machine model. Turing machines are very slow, and don't represent the capabilities of hardware. From the software side, a modern computer is similar to the RAM machine, which allows indirect addressing and has an unlimited "alphabet" (its registers hold arbitrarily large integers), though actual machines have limited registers, and this sometimes makes a big difference (for example, when doing arithmetic on large numbers). I don't know of a good model for the hardware side; Boolean circuits, popular in theoretical computer science, model neither memory nor iterative computation.

Turing machines are polynomially equivalent to RAM machines with polynomially bounded registers. That means that both machines provide the same notion of efficient computation (polynomial time computation), a theoretical notion whose usefulness in practice is doubtful. In contrast, (bounded) RAM machines form a reasonable model for actual computation, and so complexity results for RAM machines have practical relevance. However, even this model ignores some important complexities of modern computers, such as the speed of access to different kinds of memory (disk, main memory, different caches).


Check if a NFA accepts a string of non-prime length

The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.
We can check whether the language accepted by an NFA is infinite as follows:

Remove all states which are unreachable form an initial state, or from which a final state cannot be reached.
Check whether the remaining graph contains a cycle.

If the language is infinite, you can immediately answer "Yes". Otherwise, the NFA only accepts words of length at most $n-1$ (where $n$ is the number of states), and you can use the algorithm that you suggest. Your algorithm can be slightly optimized by identifying all letters in the alphabet.


Can the mind be a finite automata and still invent the Turing machine?

Some Turing Machine Details

A Turing Machine does not have infinite tape, it has unbounded tape. There is no limit to how many symbols can be stored on it, but at any given time, only a finite number of symbols are ever on the tape. So while we cannot conceive of all runs of a machine, we can always conceive at least some states of the machine.
In a sense, Turing Machines carve out the "finite" portion of all languages, in the sense that it carves out the portion that can be finitely represented (by a Turing Machine). There are uncountably many languages, but countably many Turing Machines, so there's a bunch of stuff we will never understand because it is truly infinite, in too big of an infinity.
Most problems that we can conceive of don't actually require the power of a Turing Machine. Many can be written using primitive recursion or other well-founded recursion schemes. So most algorithms don't actually require the infinite-ness of Turing Machines.
For a Turing Machine that halts, there is always a function describing the max amount of memory used in relation to the input size. So we don't need to understand infinity, we simply need to understand the relationship.

Can a weak system invent a stronger one?

The answer here, I think, is yes, depending on your definition. For example, the language of all valid Turing Machines can be described using a context-free grammar, a computationally weaker formalization. You can even describe a regular language that describes what a valid Turing Machine looks like, and they're finite. (Spoiler alert, this doesn't say much, because you can map each integer onto a Turing Machine, so the regular language $\{0,1\}^*$ can be the set of all valid Turing Machines).

And, it's important to distinguish recognizing a thing, or inventing a description of something, and inventing all the things. We can recognize what a Turing machine is, but we can't see all of them, and because of things like the Halting problem, we certainly can't even understand all of them.

Other Infinite Things

This question is ultimately no different than asking how a finite mind could understand the natural numbers, or the function $y=x$ in $\mathbb{R}^2$. Both are infinite, but can be described in finite ways.

But, there are functions and sets and real number and such that are truly infinite, that can never be described by any possible spoken or written formula (because there are uncountably many reals, but countably many finite sentences in any human language.) And there are more true theorems than there are proofs, a la Gödel.

So we can describe infinity, and speak of its properties, perhaps without truly understanding it, at least without understanding every facet of it.


Clarification of definition of class $DisNP$

A disjoint NP pair consists of two NP languages $A,B$ which are disjoint. For example, $A$ could consist of all graphs which are $k(n)$-colorable (where $n$ is the number of vertices and $k$ is an arbitrary function), and $B$ could consist of all graphs having a clique of size $k(n)+1$.

Disjoint pairs of NP languages are used in proof complexity. For example, the disjoint pair discussed above (for $k(n) = n^c$) is used to prove exponential lower bounds on the size of proofs in the cutting planes proof system. See for example these notes. (For the state-of-the-art regarding cutting planes, see the recent paper Random CNFs are Hard for Cutting Planes.)


Genetic algorithm - fit max circles inside box - what chromossomes?

You can define chromosome as array - coordinates of the center of a circle - [(x1,y1), (x2, y2),..,(xn,yn)]
One required condition for every circle- no intersection between sides of rectangle and circle - the circle must be inside the rectangle.

Start from one circle (n=1) and create population with chromosomes of size 1 [(x1,y1)].

Your fitness function - number of intersections between circles - for n=1 fitness function always return 0.

You continue with 2 circles: and generate population of chromosomes [(x1,y1), (x2,y2)]. For every chromosome you calculate fitness - number of intersection between circles.

Crossover:

You can use different algorithm to generate new population:

1) Single point.

First point - from first chromosome, second point from second chromosome.

For example, two chromosomes with coordinates:

[(x11,y11), (x12, y12)]

[(x21,y21), (x22, y22)]

Crossover - two chromosomes:

[(x21,y21),(x12,y12)],

[(x11,y11),(x22,y22)]

For n>2:

[(x11,y11),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x21,y21),(x22,y22), (x23,y23),..,(x2n,y2n)]

Crossover:

[(x21,y21),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x11,y11),(x22,y22), (x23,y23),..,(x2n,y2n)]

etc.

See https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) about crossover algorithms.

Mutation:

For every chromosome from population choose randomly some circle and change coordinates.

New population:

select chromosomes with minimal fitness value.

If you found out chromosome with fitness value is 0 - increment n (number of circles) and repeat this procedure: create population with chromosomes with size n, etc.


For $L_1:$
It's not decidable.
Define $C=\{A_TM\}$.
Now, by Rice's theorem we have that the language $L=\{<M>|L(M)\in C\}$ is undecidable. (By the extended theorem it's not even semi-decidable.)
But notice $L_1=L$ and therefore $L_1$ is undecidable.

For $L_2:$
It's decidable, although your solution is not correct.
Notice that $\overline{A_TM}$ is not semi-decidable, and therefore there is no TM $M$ where $L(M)=\overline{A_TM}$.
Thus, $L_2=\{<M>|L(M)=\overline{A_TM}\}=\emptyset$ and thus a TM that always rejects will decide $L_2$.


Why does the recurrence equation for QuickSort consider all the elements in the array?

When you're looking at the behaviour of the algorithm as $n\to\infty$, the difference between $n$ and $n-1$ becomes negligible. The simpler form is easier to deal with and it gives the same answer.


Partition partition with constraint of equal size

The idea of Colin's algorithm is to try to force a multiset that has partitions where the cardinality of the subset is different, to have only partitions where the resulting subsets have the same size. So that the problem can only be solved if we can divide the multiset into two subsets with the same cardinality

For instance, think in the multiset

{1,1,1,2,2,3}.

This set has more than one way of partitioning it:

We can partition it into {3,1,1} and {2,2,1}

Or we can partition it into {1,1,1,2} and {3,2}

In the variant they talk about, only the first way to partition this multiset is valid.

So, what he does is adding to each number the following quantity:

Number + (number with highest value * cardinality of the set we want to divide)

In our example this results in:

{19,19,19,20,20,21}

And we can only partition this multiset of numbers only if we can partition it into two subsets with the same cardinality, in this case:

{19,20,20} and {19,19,21}

Why does it work?

It works because you add to each number the same quantity, so in a partition where the two subsets have the same cardinality, we add the number the same number of times to each subset, in a partition with subsets of different cardinality, we add the number to each subset a number of times that is not equal, so the subsets can't have the same sum.

For instance

We keep with the previous example

1 + 18 + 2 + 18 + 2 + 18

and

1 + 18 + 1 +18 + 3 +18

This partition has the same sum because we add the number eighteen three times to each subset.

But

1 + 18 + 1 +18 + 1 +18 + 2 + 18

and

3 + 18 + 2 +18

don't give the same result because we add eighteen to the first subset four times and only two to the other subset, as the two had the same sum before the transformation, by adding a number to each subset a number of times that is not equal, the two don't have the same sum anymore

Hope this is helpful


You're correct that there is always an ordering of the vertices for which this algorithm will converge in one iteration, namely the topological ordering given by the shortest-path spanning tree. However, in general the vertices won't be given to us in that order.

Consider for example a path $(C,A),(A,B)$, where $C$ is the source. The algorithm will go through the edges in the order $(A,B),(C,A)$, and will need two iterations to converge.

Here is another example, in which the source it the first vertex: a path $(A,C),(C,B),(B,D)$, where $A$ is the source. The algorithm will go through the edges in the order $(A,C),(B,D),(C,B)$, and will need two iterations to converge.


If f(n) = Θ(g(n)) then what all can one say about f(h(n)) and Θ(g(h(n))

In general, you can prove nothing. You know $f(n) = \Theta(g(n))$. Now assume f (n) = g (n) = n for all n except g (n) = 0 if n ≤ 1000. And h (n) = 1000 for all n.

So we now have f (h (n)) = 1000 and g (h (n)) = 0.

The problem is that $O (n)$ and $\Theta (n)$ only work for large n. You are fine if h (n) -> inf, or if you look specifically at f (n) and h (n).

If the limit of h (n) is infinity, then you overcome the problem that $\Theta(g(n))$ only gives you information for n ≥ N for some possibly large N, because h (n) will eventually be greater than that N.


What is the meaning of 'breadth' in breadth first search?

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here


Pumping lemma for Context-Free Languages

Let me rephrase property 3 of the pumping lemma: for every $l \geq 0$, $uv^lwx^ly \in L$. Now let's consider the seven different cases:

Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Case 2: $vx = a^ib^j$ where $i,j > 0$. Like case 1 or case 3.

Case 3: $vx = b^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1-i} c^{n+1} d^n \notin L$.

Case 4: $vx = b^ic^j$ where $i,j > 0$. Like case 3 or case 5.

Case 5: $vx = c^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1} c^{n+1-i} d^n \notin L$.

Case 6: $vx = c^id^j$ where $i,j > 0$. Like case 5 or case 7.

Case 7: $vx = d^i$ where $i > 0$. Choose $l = 2$ to get $a^n b^{n+1} c^{n+1} d^{n+i} \notin L$.


Distance to $k$th nearest neighbor efficiently for arbitrary $k$

For a general metric, you can't.  For instance, one can prove it takes at least quadratic time to answer $\Theta(n)$ queries, in the worst case.
For instance, suppose we have $n/2$ query points that are all very far from each other, and $n/2$ target points.  We'll ask for the $n/4$-th closest neighbor of each query point.  Then each $d(q,t)$ can be set to any distance in $[1/2,1]$ for each of the $n^2/4$ pairs of a query point $q$ and a target point $t$, and each can be chosen independently, and you'll have a valid metric.  Thus you can imagine the distance being specified by a $n/2 \times n/2$ matrix of distances $d(q,t)$.  In $o(n^2)$ time, you can only read $o(n^2)$ of the entries in that matrix, which isn't sufficient to answer all of the queries.  You can prove this with an adversarial argument: consider any $q$ where the algorithm has read $d(q,t)$ for fewer than $n/4$ different values of $t$; then whatever the algorithm outputs as the $n/4$-th nearest neighbor to $q$, we can arrange the other unread distances so that the algorithm's output was incorrect.


Difference between multi-tape Turing machine and single tape machine

The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.


If you google for Integer Linear Programming, you'll find that the problem is in general NP-complete. However, your subproblem with just one restriction and two variables isn't difficult to solve.

Have a look at https://en.wikipedia.org/wiki/Cutting-plane_method and especially Gomory's method: You first use the Simplex algorithm to find the optimal solution without considering that the solution should be integers. If by coincidence your optimal solution is integer, you solved the integer linear programming problem. Otherwise, you use Gomory's method to find another restriction which isn't fulfilled by the non-integer solution you found, but by every integer solution of the original problem. You solve the system with the new equation, and repeat until you have an integer solution.


How do I simplify this boolean expression?

$
\begin{align}
ABC + ABC' + AB'C + A'BC = \\
ABC + ABC + ABC + ABC' + AB'C + A'BC =  & & & \text{(2x Idempotency)}\\
AB(C + C') + ABC + ABC + AB'C + A'BC = & & &\text{(Distribution)}\\
AB + ABC + ABC + AB'C + A'BC = & & & \text{(Negation)}\\
AB + (AB + AB')C + (AB + A'B)C = & & & \text{(2x Distribution)} \\
AB + (A(B+B'))C + ((A+A')B)C = & & & \text {(2x Distribution)} \\
AB + AC + BC & & & \text{(2x Negation)}
\end{align}
$

I'm not proficient at this kind of derivations so please correct any notation/terminology


Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes.

The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily binary), the algorithm would still run in linear time.


Will a Greedy algorithm give a correct result for minimum partition?

This does not always lead to the optimal solution. For example for input $\{1,11,16,19,20,30,36,40,41\}$ it gives $\{1,11,16,19,20,36\}$ and $\{30,40,41\}$ with a difference of 8, while a difference of 0 is possible: $\{1,40,36,30\}$ and $\{41,20,16,11,19\}$


Is the union of finite and infinite sequences over alphabet of length 1 countable?

You haven't defined what you mean by "finite or countably infinite sequence" over an alphabet $\Sigma$, so let me assume that a "finite sequence" is a word over $\Sigma$, while a "countably infinite sequence" is an $\omega$-word over $\Sigma$, that is, a mapping from $\omega$ (the set of natural numbers) to $\Sigma$.

In your case, there is exactly one word of each length $0,1,2,\ldots,\omega$, so the set of "finite and countably infinite sequences" is countable, since the set $\omega + 1 = \omega \cup \{\omega\}$ of possible lengths (which is in one-to-one correspondence with the possible "finite and countable infinite sequences") is countable.

If you want to be very formal, you can show that $\omega + 1$ is countable by giving an explicit bijection between $\omega$ and $\omega + 1$, such as
$$
0 \mapsto \omega, \quad n+1 \mapsto n \text{ for all } n \geq 0.
$$


How to determine minimum word length of regular language

First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, which define an operator $E$ on regular expressions:

$E[\sigma] = \sigma$, $E[\epsilon] = \epsilon$, $E[\emptyset] = \emptyset$.
$E[r_1 r_2]$ is $\emptyset$ if one of $E[r_1],E[r_2]$ is $\emptyset$, and $E[r_1]E[r_2]$ otherwise.
$E[r_1 + r_2]$ is $E[r_1]$ if $E[r_2] = \emptyset$, $E[r_2]$ if $E[r_1] = \emptyset$, and $E[r_1] + E[r_2]$ otherwise.
$E[r^*] = \epsilon$ if $E[r] = \emptyset$, and $E[r]^*$ otherwise.

You can prove inductively that $E[r]$ either doesn't contain $\emptyset$, or is equal to $\emptyset$.

Applying these rewriting rules, we have either determined that the denotation of the regular expression is empty, or are given a regular expression without $\emptyset$. Now we define an operator $m$ which determines the length of the minimal word in an $\emptyset$-free regular expression:

$m(\sigma) = 1$, $m(\epsilon) = 0$.
$m(r_1r_2) = m(r_1) + m(r_2)$.
$m(r_1 + r_2) = \min(m(r_1),m(r_2))$.
$m(r^*) = 0$.

You can also implement both operators at once, by allowing $m$ to output $\infty$ (meaning that the language defined by the regular expression is empty):

$m(\sigma) = 1$, $m(\epsilon) = 0$, $m(\emptyset) = \infty$.
$m(r_1r_2) = m(r_1)+m(r_2)$, where $\infty + \ell = \ell + \infty = \infty$.
$m(r_1+r_2) = \min(m(r_1),m(r_2))$, where $\min(\infty,\ell) = \min(\ell,\infty) = \ell$.
$m(r^*) = 0$.


Constructing a random Hamiltonian Cycle (Secret Santa)

I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem.

If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.


What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?

It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all three languages.

The While language is also good for an intuition of Turing completeness. You need

Potentially infinite loops, because Turing complete computations may not terminate.
Condition-dependend behaviour, so that you can break out of loops (important: in contrast to for loops, the time after which the loop ends is not be known in advance).
A data type with an infinite domain.

In both examples I gave above, the third ingredient is the type of integers of unbounded size. Arguably, it is not natively supported in C++ (I do not know about JavaScript or C#. A "normal" programming that has it is Python 3.)
You promised not to nitpick, but if you did one would have to either

replace your languages by "conceptual" variants thereof where integers are unbounded, or
implement unbounded integers in a library (like GNU MP). When you do that, you inevitably use the "true" third ingredient of your languages: They achieve infinite-domain data through dynamic allocation.

All of the above would as well hold for C. Yet your question, at least the title, is specifically about OOP languages. Basically, your three languages are extensions of C by objects. My Turing-complete subsets then discard these extensions. At the moment I cannot come up with natural subsets of any of these languages where some OOP feature is essential for Turing completeness.

As for simple, natural, polynomial time reductions to Turing machines: Polynomial time is possible, natural in a sense, simple I do not think (such a reduction is a full-feature compiler for the language, so it cannot be any simpler than the language is).
Let there be three tapes. One for the heap, one for the stack and one for indexing. The heap and the stack would contain sequences of substrings like [1010011] which encode unbounded integers (83 in this case). When used as pointers, these integers are somehow mapped to positions in the heap or the stack. Indexing an element of the heap or the stack works by copying the pointer to the indexing tape and then moving to the respective part of the tape by using the indexing tape as a counter.


This is just VERTEX-COVER in disguise. The reduction from CLIQUE is also simple – a set is disconnected iff its complement is a clique.


Proving that a language defined by a regular expression is equivalent to a right linear grammar

Let's try to simplify your grammar. First, notice that $A$ generates $(00)^*11S$, and so we can get rid of $A$, obtaining
$$
S \to 1(00)^*11S \mid 01S \mid \lambda
$$
Similar reasoning shows that your grammar generates the language
$$
(1(00)^*11+01)^* = ((1(00)^*1+0)1)^*,
$$
which is identical to your regular expression.
While the reasoning above is informal, it can be made formal with some work.


Turing reducibility of 2 versions of the satisfiability problem

Any algorithm that decides the satisfiability of a formula can also be used to find an assignment for a satisfiable formula:

While not all variables are assigned:

Pick a variable and choose value 0.
If formula is no longer satisfiable, replace value with 1.


Why is automated theorem proving impossible?

We have to be carful here. I think you mean that a program given a formula could not, in general, produce a proof of it or its negation. I can write a program that, given a theorem, will produce it's proof as long as the set of proofs is recursively enumerable. This is not possible in general because of Godel's incompleteness theorem (well that was the first case we knew of). If everything that was true could be proved then we could write a program that enumerated all the proofs until it found the proof of the formula or its negation. However this is not the case as the incompleteness theorem points out. While Godel was the first to prove this was the case the halting problem gives us a nice simple proof that some things are not provable.

The argument goes like this:

Say you have a sound and complete logic for proving the termination of computer programs. The rules of the logic make the proofs recursively enumerable as well. If the logic wasn't sound we wouldn't have to worry about proving anything because false things are already provable; everything falls apart. If it wasn't complete (generally the case) then there would be a true thing that wasn't provable and thus neither you nor the computer could ever prove it. If The proofs were not recursively enumerable then there would be a proof that the program couldn't check to be valid or even reach and thus it couldn't prove the corresponding formula. Now consider the following program:

Given a program called pgrm
foreach p in set of proofs //remember, proofs are recursively enumerable
  if p is a proof that pgrm halts
    output that pgrm halts
  if p is a proof that pgrm loops
    output that pgrm loops

This program would solve the halting program however so one of our 3 assumptions must be wrong. In practice we work with what we think are sound systems of logic and we work with recursively enumerable sets of proofs as well.


For a language $L' \in \mathsf{coNP}$, there are certificates for all NO instances, which is to say inputs $x \notin L'$, which could be efficiently verified and used as proof that $x \notin L$. Suppose that $L \subset L'$: the fact that there are certificates for all NO instances $x \notin L'$ isn't enough to allow us to determine decisively if $x \notin L$, because we could have an input $x \in L' \smallsetminus L$.

Thus, the certificates for $L'$ are not sufficient to provide certificates for $L$, and we cannot conclude that $L \in \mathsf{coNP}$. Indeed, as @G.Bach indicates in the comments, there are examples where $L' \in \mathsf{coNP}$ and $L$ is not even a decideable language. Modifying his example, consider $$ L' = \Bigl\{ x \in \{0,1\}^\ast \;\Big|\; |x| \text{ is prime} \Bigr\}$$
which has certificates for NO instances simply by giving a non-trivial factor for $|x|$ on any input $x \notin L'$. Then $L' \in \mathsf{coNP}$, and indeed $L' \in \mathsf P$: not only because the AKS algorithm puts primality testing in $\mathsf P$, but because (the input being expressed in unary) even trial division would represent an efficient algorithm. However, the language
$$ L = \left\{ x \in L' \;\left| \begin{array}{c} x \text{ encodes a Turing machine} \\ \text{and an input on which it halts,} \\ \text{padded with 0s} \end{array} \right\}\right.$$
using whichever encoding of Turing machines that you like will not even be a decideable language in general, and so it will definitely not be in $\mathsf{coNP}$.


Dynamic programming gives you a way to think about algorithm design.  This is often very helpful.

Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code.  Memoization is a relatively simple idea, but the best ideas often are!

Dynamic programming gives you a structured way to think about the running time of your algorithm.  The running time is basically determined by two numbers: the number of subproblems you have to solve, and the time it takes to solve each subproblem.  This provides a convenient easy way to think about the algorithm design problem.  When you have a candidate recurrence relation, you can look at it and very quickly get a sense of what the running time might be (for instance, you can often very quickly tell how many subproblems there will be, which is a lower bound on the running time; if there are exponentially many subproblems you have to solve, then the recurrence probably won't be a good approach).  This also helps you rule out candidate subproblem decompositions.  For instance, if we have a string $S[1..n]$, defining a subproblem by a prefix $S[1..i]$ or suffix $S[j..n]$ or substring $S[i..j]$ might be reasonable (the number of subproblems is polynomial in $n$), but defining a subproblem by a subsequence of $S$ is not likely to be a good approach (the number of subproblems is exponential in $n$).  This lets you prune the "search space" of possible recurrences.

Dynamic programming gives you a structured approach to look for candidate recurrence relations.  Empirically, this approach is often effective.  In particular, there are some heuristics/common patterns you can recognize for common ways to define subproblems, depending on the type of the input.  For instance:

If the input is a positive integer $n$, one candidate way to define a subproblem is by replacing $n$ with a smaller integer $n'$ (s.t. $0 \le n' \le n$).
If the input is a string $S[1..n]$, some candidate ways to define a subproblem include: replace $S[1..n]$ with a prefix $S[1..i]$; replace $S[1..n]$ with a suffix $S[j..n]$; replace $S[1..n]$ with a substring $S[i..j]$.  (Here the subproblem is determined by the choice of $i,j$.)
If the input is a list, do the same as you'd do for a string.
If the input is a tree $T$, one candidate way to define a subproblem is to replace $T$ with any subtree of $T$ (i.e., pick a node $x$ and replace $T$ with the subtree rooted at $x$; the subproblem is determined by the choice of $x$).
If the input is a pair $(x,y)$, then recursively look at the type of $x$ and the type of $y$ to identify a way to choose a subproblem for each.  In other words, one candidate way to define a subproblem is to replace $(x,y)$ by $(x',y')$ where $x'$ is a subproblem for $x$ and $y'$ is a subproblem for $y$.  (You can also consider subproblems of the form $(x,y')$ or $(x',y)$.)

And so on.  This gives you a very useful heuristic: just by looking at the type signature of the method, you can come up with a list of candidate ways to define subproblems.  In other words, just by looking at the problem statement -- looking only at the types of the inputs -- you can come up with a handful of candidate ways to define a subproblem.

This is often very helpful.  It doesn't tell you what the recurrence relation is, but when you have a particular choice for how to define the subproblem, often it's not too hard to work out a corresponding recurrence relation.  So, it often turns design of a dynamic programming algorithm into a structured experience.  You write down on scrap paper a list of candidate ways to define subproblems (using the heuristic above).  Then, for each candidate, you try to write down a recurrence relation, and evaluate its running time by counting the number of subproblems and the time spent per subproblem.  After trying each candidate, you keep the best one that you were able to find.  Providing some structure to the algorithm design process is a major help, as otherwise algorithm design can be intimidating (there's such a huge space of possible approaches, without some structure it can be unclear how to even get started).


Why is f(n) of class O(g(n)) in this graph?

I think you're confused about the notion of upper bounds for a function. We're not trying to compute an upper bound for the function $f$ in the sense of saying that, e.g., $f(n) \leq 45$ for all $n$ (or all $n$ greater than some $n_0$). Rather, we're trying to say that, for all $n>n_0$, the value (number) $c\,g(n)$ is an upper bound for the value $f(n)$. The graph indicates this informally (since it only shows what happens for some unstated but limited range of values of $n$).


Playing the game of life on an infinite grid

If you want to do better than iterating over each cell, or at least the range of live cells, use Hashlife.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478?pgno=1

https://www.youtube.com/watch?v=l228ARRYkNE


How to conceptually represent attributes (characteristics) of an object in logics?

For this discussion, I'll use classical first-order logic. I'll interpret your term "first-class citizens" to mean those objects which can be quantified over or passed as arguments to predicates and functions. The examples provided below are toy examples, purely for expository purposes. Have a look at the leading AI textbook which gives a much more extensive, proper introduction to this subject.

There are often many ways to formalize a given statement in logic. Let's consider your example 'An apple #1 has price 1$'. There are some naive ways that come to mind:

price(apple1)               this is a function which yields the price
Price(apple1,80)            this is a predicate

As for your question, "Is my representation of attributes by whole-part-relationships acceptable?", it at least raises eyebrows. Generally, whole-part relationships should reflect the notion that the part is part of the object structure itself, not some attribute of the object. So while has-part(apple,stem), has-part(apple,skin), has-part(apple,seed) seem reasonable, has-part(apple,price) does not.

Now for your main question, "how to represent attributes in the logics in which attributes are not first class citizens?" you can use either functions or predicates. Examples are given under the paragraph above describing some ways one can formalize a given statement in logic.


It is said that the intuitive meaning of μ is finite looping where as the intuitive meaning of ν is infinite looping in μ calculus

Here's a better phrasing: µ is about looping with a known bound on the number of iteration. For ν we do not necessarily know the bound, and there may in fact not even be one.

  Is there any theorem which proves this ?

Theorems can not prove how apt an intuition is. The property you have in mind follows from the definitions and can be illustrated by some examples.


Context-free grammar for $\{a^x b^y : x \neq y\}$

Let $L = \{a^n b^n : n \in \mathbb N\}$. Your language can be written as $a^+L \cup Lb^+$, and this leads to the following grammar:
$$
\begin{align}
&S \to AT \mid TB \\
&T \to aTb \mid \epsilon \\
&A \to aA \mid a \\
&B \to bB \mid b
\end{align}
$$
We can save a nonterminal by factoring $L$ differently:
$$
L = \{a^na^mb^n : n \geq 0, m \geq 1\} \cup \{a^nb^mb^n : n \geq 0, m \geq 1\}.
$$
This leads to the following grammar:
$$
\begin{align}
&S \to aSb \mid A \mid B \\
&A \to aA \mid a \\
&B \to bB \mid b
\end{align}
$$
There are many other possible variants, for example:
$$
\begin{align}
&S \to A \mid B \\
&A \to aAb \mid aA \mid a \\
&B \to aBb \mid Bb \mid b
\end{align}
$$


What is the difference between computational model, model of computation and a computer?

A model of computation is an abstract device used to perform computation.

For example, Turing machines are a model of computation.
They allow operations such as reading a symbol on the tape, writing a symbol on the tape, move left/right...
Minsky machines are another model of computation.
They allow operations such as increment a counter, decrement a counter, test a counter for zero.
Models of computation are used to reason about algorithms, to answer questions like: is problem X realizable with the model of computation Y? If so, how many operations would be needed?

Those models are abstract because they do not describe what the available operations are, not how they are realized.
A computer is a realization, an implementation of an abstract model of computation.
To ease their daily use, and to get efficiency from various technologies, computers have various sets of operations, and it is hard to describe an abstract model of computation for them.
Yet, all the operations they perform can be expressed in terms of e.g. Turing machines or Minsky machines operations.

Note that a Turing machine cannot exist for real: a Turing machine has an unbounded tape, so it would not fit in our Universe.
Similarly, the counters of a Minsky machine are supposed to be able to store arbitrarily high numbers.

From a strict theoretical point of view, since a computer has a finite fixed amount of memory, it is nothing more than a finite state automaton (with a large, yet fixed, number of states).
In practice, a computer is rather considered as a Turing machine, with a tape (memory) large enough not to run out.

To conclude, a computational model is a mathematical description of a complex system, often a physical one.
Computational models are mostly intended for simulation, to be run on real computers.


Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

Let us count operations line by line. You construct the heap in linear time. Then, you execute the loop and perform a logarithmic time operation $n-1$ times. Other operations take constant time. Hence, your running time is

$\qquad \begin{align}
& n + (n-1) \log n + O(1) \\
&= n + n \log n - \log n + O(1) \\
&= \Theta(n \log n).
\end{align}$

In other words, as $n$ grows the $n \log n$ term dominates. That is, the cost of building the heap on line 1 is negligible compared to the cost of executing the loop.


What is the adjunct of the evaluation morphism in a closed monodical category?

Adjuncts are morphisms related by the natural isomorphism:

$$Hom(FA, B) \cong Hom(A, GB)$$

defining the adjunction. The adjuncts of (co)units are identities:

$$
(ε_A : FGA → A)  \longleftrightarrow (1_{GA} : GA → GA) \\
(η_A : A → GFA) \longleftrightarrow (1_{FA} : FA → FA)
$$

This correspondence is basically what connects the $Hom$ definition of adjunctions with the (co)unit definition.

In this case, $FA = A \otimes X$ and $GA = [X,A]$.


To prove coNP-hardness, you don't need a certificate (that would be needed only if you wanted to show coNP-completeness). We just need some coNP-hard problem that reduces to UniqueSAT. UniqueSAT is indeed likely not in coNP.
You can ask an oracle multiple queries. You could begin by asking if the formula has a satisfying assignment (and, using self-reduction, find a solution if one exists). Perhaps you can then use further queries to determine if another solution exists?


Dynamic All Pairs Shortest Paths algorithm

You maintain a table $d$ where $d(i,j)$ represents the length of the shortest path from vertex $i$ to vertex $j$, so query 2 can be done in $O(1)$.

For query 1, when a new vertex $u$ is added, for each old vertex $v$, calculate the length of the shortest path from $u$ to $v$ by

$$d(u,v),d(v,u)\leftarrow\min_s(w(u,s)+d(s,v)).$$

where $s$ varies among all neighbors of $u$, and $w(u,s)$ represents the weight of edge $(u,s)$. This process takes $O(n^2)$. Now if there is no negative cycle, for each old vertex $v$, $d(u,v)$ and $d(v,u)$ correctly record the length of the shortest path from $u$ to $v$. It's also not hard to detect if there is a negative cycle.

Then, for any old vertices $s,t$, update $d(s,t)$ to

$$d(s,t)\leftarrow\min\{d(s,t),d(s,u)+d(u,t)\}.$$

This can also be done in $O(n^2)$.

Now after the two steps above, if there is no negative cycle, for each pair of vertices $x,y$, $d(x,y)$ correctly records the length of the shortest path from $x$ to $y$.


Given an algorithm $A$ (on inputs from some set $X$), we define the runtime function to be
$T_A(x) : X \to \mathbb{N} \cup \{\infty\}$ so that

$\qquad T_A(x) = \begin{cases}
    \text{number steps } A(x) \text{ takes},\ \ &A(x)\!\downarrow \\
    \infty, &A(x)\!\uparrow
  \end{cases}$

for all $x \in X$. I denote with $A(x)\!\downarrow$ that $A$ terminates on $A$,
and with $A(x)\!\uparrow$ the opposite.
Note that the number of steps an algorithm takes on an input depends on the
computational model you choose, but we can leave that abstract here.

Now, the common way to define worst-case runtime is

$\qquad\displaystyle T_A^{\mathrm{WC}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n\}$

which of course yields $\infty$ if there is any input of the given size for which $A$ loops.
You want

$\qquad\displaystyle T_A^{\mathrm{WC\downarrow}}(n) = \max \{ T_A(x) \mid x \in X, |x| = n, A(x)\!\downarrow\}$.

I don't know an established name for that one, but if I were to need one I'd go with
terminating-worst-case runtime¹. That said, you probably use only one
notion of runtime most of the time, so you can do as most authors do and say something
along the lines of:

  From here on out, we always mean $T_A^{\mathrm{WC\downarrow}}$
    when we write "runtime" unless otherwise specified.

So yes, just use runtime but make very clear what you mean by that.

You notice that the definition of $T_A^{\mathrm{WC\downarrow}}$ assumes
that there is at least one input of every size for which $A$ terminates.
You should handle the case if that fails.


Importance of space constructability in time space relation in complexity

To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably some of these inclusions do hold regardless of space-constructibility.

Regarding the second question, suppose that you computed $S(n)$ (in binary), and are interested to compute $2^{CS(n)}$. First, multiply $S(n)$ by $C$; this uses $O(\log S(n))$ space. Second, count $CS(n)$ spaces, fill them with zeroes, and add a one to the left. You have computed the binary representation of $2^{CS(n)}$, using additional $S(n)+1$ space.


Understanding arguments in Haskell type classes and instances

Question 1
Does the bracketed "(v o)" in the Vehicles context refer a type constructor and its argument, rather than two independent types?

In the constraint Surfaces v o, v and o are two separate type arguments to class Surfaces. Constraint Paths a b (v o) has three arguments: a, b, (v o). The third is v applied to o, so we can infer parameter v to class Vehicles is a type constructor, kind * -> *.
I'm not sure what you're trying to say by "independent types": v, o, are distinct parameters to Vehicles. The constraints are telling us we can't freely choose just any types for a, b, v, o, so they're all inter-dependent.

Question 2:
Is the instance OK? Why do I need FlexibleInstances
   instance Vehicles Boat Person Route (Water Source)

Firstly, class Vehicles needs FlexibleContexts. That's because not all of the constraints are of the form class name followed by bare type variables. Argument (v o) is the culprit.
Similarly for that instance, not all the type arguments are plain type constructors or constructors followed by bare type vars. Argument (Water Source) is the culprit. If it were (Water b), that wouldn't need FlexibleInstances.


How can I reduce a product of transpositions?

I suspect your problem is NP-hard, but if you need to solve it in practice, I recommend using a SAT solver to help you.

Algorithms

I suggest you solve this using a SAT solver.  The problem can be expressed in a fairly straightforward way as an instance of SAT, and then you can apply an off-the-shelf SAT solver.

Let's solve the following problem:

Input: $\ell \in \mathbb{N}$; a set $T$ of $m$ transpositions; a permutation $\pi$
Question: Does there exist a way to express $\pi$ as a product of $\le \ell$ transpositions?

We'll construct a way to solve this problem using SAT, then apply binary search over $\ell$ to find the optimal solution.

For simplicity, add the identity element to $T$.  Then we can replace "$\le \ell$" with "exactly $\ell$".  Now the question can be expressed in a rather straightforward way as a CNF formula.

In particular, introduce boolean unknowns $x_{i,\tau}$ (for each $i=1,2,\dots,\ell$ and each $\tau \in T$), with the intended meaning that $x_{i,\tau}=1$ means that $\tau$ is the $i$th transposition in the output sequence.  Also, introduce boolean unknowns $y_{i,j,k}$, where $y_{i,j,k}=1$ is intended to mean that the first $i$ transpositions in the output sequence map $j$ to $k$.  We add constraints:

For each $i$, we require that exactly one of the $x_{i,\tau}$ is 1.
We require that the product of the transpositions yields $\pi$, i.e., $y_{\ell,j,\pi(j)}=1$ for all $j$.
We require that the $x$'s and $y$'s are consistent, e.g.,

$$y_{i+1,j,k} = \bigvee_{\tau} y_{i,j,\tau^{-1}(k)} \land x_{i,\tau}.$$
We require that $y_{0,j,j}=1$ for all $j$ and $y_{0,j,k}=0$ for $j \ne k$.

Now feed this to a SAT solver.  This should be satisfiable if and only if there's a way to express $\pi$ as a product of $\ell$ transpositions from $T$.

Finally, use binary search on $\ell$, as mentioned above, to find the shortest possible way to express $\pi$ as a product of transpositions from $T$.

(There are many different ways to express this problem as SAT, and those choices might affect the performance of the SAT solver.  So, if you need to solve this in practice, you might experiment with different ways of encoding the constraints into SAT.)

Hardness

I suspect your problem is NP-hard.

Researchers have studied a natural generalization of this problem where the set $T$ is allowed to contain arbitrary permutations, rather than just transpositions:

Inputs: $\ell \in \mathbb{N}$; a set $S$ of permutations; a permutation $\pi$
Question: Is there a way to express $\pi$ as a product of $\le \ell$ permutations from $S$?

This problem is NP-hard, as proven in the following paper:

The Minimum-Length Generator Sequence Problem is NP-Hard.  S. Even, O. Goldreich.  Journal of Algorithms, vol 2, pp.311-313, 1981.

This problem remains NP-hard even if \ell is specified in unary (i.e., there is not likely to be an algorithm that is polynomial in the length of the output).  Subsequent work showed that the problem is PSPACE-complete if $\ell$ is specified in binary.  That's not the same problem as yours, because you have the extra condition that $T$ contains only transpositions, but it is related.

A subsequent paper showed that if $T$ generates a transitive group, then the problem is NP-hard.  In your case, this corresponds to the condition that the underlying graph be connected.  I suspect you're dealing with a connected graph (otherwise you can trivially decompose into connected components and the complexity will depend on the size of the largest connected component).  As a result, this appears to imply that your problem is NP-hard.

This hardness result is mentioned in Section 4 of the following paper:

The complexity of finding minimum-length generator sequences.  Mark R. Jerrum.  Theoretical Computer Science, vol 36, pp.265--289, 1985.

Assuming this is right, your options are to either look for a heuristic that will be always-efficient but not-always-optimal, or look for an always-optimal algorithm whose running time is not guaranteed to be always-efficient (e.g., by using a SAT solver).

Caveat: I don't have 100% confidence in my reasoning here.  If I understand things correctly, it seems to contradict another claim in the same paper (namely, the one mentioned below about adjacent transpositions; those generate a transitive group, yet the corresponding problem isn't NP-hard).  So I don't have full confidence that the problem is NP-hard.  It's entirely possible I've misunderstood something or mis-applied the paper's results.

Other resources

Subsequent work has also shown that certain special cases can be solved in polynomial time, e.g., where $T$ contains all transpositions, or where $T$ contains all adjacent transpositions $(i,i+1)$, or where $T$ contains all cyclicly adjacent transpositions (i.e., all transpositions of the form $(i,i+1)$ together with $(n,1)$).  However, that's probably not useful to you, as those correspond to rather trivial graphs (the complete graph, a line graph, or a $n$-cycle $C_n$).

You might also be interested in https://cstheory.stackexchange.com/q/21899/5038


0-1 knapsack problem with minimum and maximum weight capacity

We can change the definition of the traditional Knapsack to "the maximum value we can get from the first n items using exactly W weight" instead of "the maximum value we can get from the first n using at most W weight". The easiest way to do this by replacing the following code:

for j from 0 to W do:
    m[0, j] := 0

from the Wikipedia article dynamic program pseudo code with

m[0, 0] := 0

Then we simply need to check for the maximum value of the range m[n, M] , ... , m[n, W].


Consequence of NP=coNP to some hierarchy problems

To the best of my knowledge, no such implications are known.


is a while loop always an indefinite loop?

Yes, this is definite loop, as long as you (or your compiler for that matter) can infer number of passes.
In some languages (like C), 'for' is a transformation that expands during compilation to 'while' construction like you have shown. Compiler would infer number of steps during optimisation phase, when you have provided constant expression loops of any kind, but will not infer that from variable expressions.


There are many strategies, and which is best will  likely depend on a number of details not listed in the question.

For short words, the most efficient solution is to precompute everything.  For each word in the dictionary, compute all possible words that can be obtained from it.  Store these in a giant hashtable.  If a word can be obtained in multiple ways, keep only the way with highest frequency.  Then, finding the correction for a new word is as simple as looking it up in the hashtable.

For long words, one approach would be to consider only the first K letters of the word (for some K) and ignore the remaining letters, and then use the precomputation method above.  The hash table will have to list all ways to complete the first K letters to a full word.  You would choose K to balance off the space needed for the hashtable and time needed for the precomputation, vs the time to correct a word.

Other strategies you could consider: (1) iterate through the dictionary in decreasing order of frequency, check whether it matches the input word; (2) generate all possible variants of the input word (by all possible combinations of replacing each letter by some adjacent letter or leaving it unchanged), look each up in the dictionary, and keep the highest-frequency match; (3) use locality-sensitive hashing to find all matches in the dictionary, and keep the highest-frequency one.  I suspect precomputation may be better than all of these in practice, though.


Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

The answer is really up to the definition of equivalent. The common definition is that two automata/grammars are equivalent if they define the same language. If your class uses the common definition, then both statements are entirely equivalent.


Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

Assume $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$. Let $\Pi$ be a NP-complete problem, by assumption, this problem can be solved by some circuit family. It is true that the problem $\hat{\Pi}$ where the input is a pair consisting of input to $\Pi$ and a circuit making an appropriate computation, is in $\mathsf{P}$. However, from this fact you cannot conclude that the original problem $\Pi$ is in $\mathsf{P}$. To obtain a solution to $\Pi$ using $\hat{\Pi}$ you have to guess the circuit - and this is not a priori possible in $\mathsf{P}$. You could guess the circuit nondeterministically, but then the argument would prove that $\mathsf{NP} = \mathsf{NP}$. However, if you start with a $\Sigma_2$ set instead, it is possible to fix this reasoning and obtain $\Sigma_2=\Pi_2$ (Karp-Lipton theorem).


All pairwise shortest paths in a graph: does knowing the path weights help?

Yes, given the lengths of the shortest paths it is easy to actually find these paths. Suppose for example that you want to find the shortest path from $s$ to $t$. Let $d(s,t)$ be the length of the shortest path, and $w(s,t)$ the length of the edge from $s$ to $t$, or $\infty$ if there is none.

If $d(s,t) = w(s,t)$ then the shortest path is simply $s,t$. Otherwise, there must be a vertex $x$ such that $d(s,t) = w(s,x) + d(x,t)$ (why?). The shortest path then starts $s,x$ and continues with the shortest path from $x$ to $t$, which you can find recursively.

You can also go from $t$ back to $s$ if you prefer. You can also make progress by finding some point $u$ such that $d(s,t) = d(s,u) + d(u,t)$.


Efficiently determine relative ordering between two elements in a PO-set

This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion).  It's sometimes known as incremental reachability or incremental DAG reachability.

There's lots written in the research literature on the subject.  Here are some pointers to get you started:

https://cstheory.stackexchange.com/q/18787/5038
https://cstheory.stackexchange.com/q/14343/5038
https://cstheory.stackexchange.com/q/5176/5038
https://cstheory.stackexchange.com/q/29/5038
https://en.wikipedia.org/wiki/Dynamic_problem_(algorithms)
https://en.wikipedia.org/wiki/Dynamic_connectivity (though this seems to talk about undirected graphs, rather than directed graphs)


Substitution-based Operational Semantics of algebraic datatypes

I found the solution to my answer: ADTs can be represented by a combination of sum-types and tuples enter link description here. In that representation, every construction takes exactly one argument (possibly the unit value).

Two special tagging forms, inl and inr for "inject left" and "inject right" are introduced. These forms allow the encoding of arbitrary tags. So every constructor is a one-argument function that applies the corresponding tag.

Hence, any data structure definition is operationally defined by the constructing operations:

data A | B | C

=>

let A = \\x. inl x in
let B = \\x. inr (inl x) in
let C = \\x. inr (inr x) in

The corresponding pattern can be substituted similarly.


Is thread in operating system = thread function in programming languages?

because there is only one main function, usually the program would just run from top of the main function to down.

That's a long way from being the case. Loops, conditional statements and function calls mean that the control flow of any non-trivial program is much more complex than just running from the top of main() to the bottom.

  Is thread in operating system = function in programming language?

No. A thread is, essentially, a subprocess. A process may have several threads, and each of these threads executes semi-independently while sharing some common information. A function, on the other hand, is typically a somewhat self-contained unit of work.

An analogy might be that a process is like a company (there can be many different processes, they're kept separate from each other but they can arrange to cooperate with each other in various ways, governed by the law of the country they're in), a thread is like an employee of a company (employees share access to the company's resources and cooperate closely under rules defined by the company) and a function is a specific task that might be performed by an employee (making coffee, typing a letter, attaching a door to a car, etc.)

  Is function in programming language = thread function in programming language?
  Is thread in operating system = thread function in programming language?

The things you're calling "thread functions" are just programming language libraries that access the operating system's interface for creating and managing threads

  Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

Well, threads allow multiple functions to be performed simultaneously. main() is just the entry point to the program as a whole: it's the place where execution starts.

  Where is thread written in operating system/ programming language?

I'm not sure what you mean by this but it's going to depend on the OS and programming language in question.

  Will the program not be able to do multithreading if it doesn't include these thread functions?

A program will need some way of telling the operating system to make a new thread. In practical terms, using a library that somebody has already written is going to be more convenient than trying to manage the interaction with the operating system yourself.


How to extract parent, child and grandchild from a treeview fomatted string?

Don't use regexes.  A tree is a recursively defined structure, and regexes don't do recursion (they can't match nested parens for the exact same reason).

You can easily build a tree structure by using a LIFO stack of nodes and maintaining an integer currentDepth, initially 0.  For each line, pop nTabsAtStartOfLine - currentDepth - 1 nodes off the stack, create a new node, make it the child of the current top-of-stack, push it on the stack, and set currentDepth = nTabsAtStartOfLine.


O(f(n)) means the family of function of f(n), a family of function for example could be {n^2, 3*n^2, 6*n^2, ...k*n^2}, for g(n) to be in the O(f(n)), it means that g(n) is less than all elements of f(n) in the long run. In the above example, it could be g(n) = n, versus O(f(n)) = O(n^2), obviously, n^2 is bigger than n for all n in the long run.

Absolute value sign compares the absolute values of these two functions so that even if g(n) is negative, we can compare which negative grows faster i.e. -n^2 grows faster than -n is equivalent to n^2 grows faster than n

n>N means in the long run

Bubble sort runs O(n^2) in the worst case means that Bubble sort can run much faster than O(n^2), but it does not exceed O(n^2). For example, we want to sort two elements {2,1} using bubble sort, obviously this takes 1 operation and that's it, 1 is smaller than n^2.


Size of order-preserving minimal perfect hash family

Reference [1] defines order-preserving as follows:

  A hash function is order preserving if it puts entries into the hash table in a prespecified order.

In your case, this means that given any three elements $x,y,z \in \{1,\ldots,8\}$, you want there to be a hash function which maps $x$ to $1$, $y$ to $2$, $z$ to $3$.

In particular, it need not be the case that $x < y < z$.

If you add the assumption that $x < y < z$, then you can remove the $m!$ factor in the lower bound on $H$. The new lower bound states $H \geq 2.95$, that is, $H \geq 3$, which is not tight.


The correct SQL would be :

select co.name, cu.name
from consultant co join project pr on co.id = pr.ConsultantID
                   join CustomerCompany cu on cu.id = pr.CustomerId
                   join Invoice i on i.Customer = pr.CustomerId
where i.amount between 100 and 200

Converting to relation algebra is straightforward...


Fastest algorithm for finding the longest palindrome subsequence

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

See Wikipedia's reference

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

Edit

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good:
\begin{align*}
f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad j<k\\
f_{k,k}&=1\\
f_{j,k}&=0,\qquad j>k\\
\end{align*}
where $f_{j,k}$ denotes the length of the longgest palindrome subsequence of $S_{j..k}$, and $[P]$ is Iverson bracket I think it's just like LCS.


Problem understanding DFA & NFA equivalence in Theory of Computation

Motivation. In this construction, the intent is to make a DFA equivalent to a given NFA. In the original NFA, look at what happens when we're in state 2 and we see input $a$: we could either stay in state 2 or make a transition to state 3. If we want to eliminate nondeterminism, we could say that from state 2 looking at input $a$ we move to the single new state $\{2,3\}$, meaning that in this case, we're either in state 2 or state 3. In other words, in the constructed DFA we'll have the transition $\delta'(\{2\}, a)=\{2, 3\}$. The important thing to notice is that this transition in the new FA is deterministic: from the state $\{2\}$ on reading $a$ we move to the single state denoted by $\{2, 3\}$. Guided by this convention, we will build the DFA by defining the states to be all possible sets over 1, 2, 3, namely
$$
\emptyset, \{1\}, \{2\},\{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}
$$

Final States. Let's start with an example: what does the NFA do on input $baa$? We'll have, in order

In state 1, looking at $b$. Go to state 2.
In state 2, looking at $a$. Go to state 2 or state 3.
Looking at the last input, $a$ we could be in either state 2 or state 3. If we're in state 2, go to state 2 or state 3 as before. If we're in state 3, go to state 1.

In other words, at this stage, after having read $baa$ we could find ourself in states 2, 3, or 1.

In the DFA, we have, equivalently, the transitions $\delta'$ defined as

$\delta'(\{1\}, b) = \{2\}$.
$\delta'(\{2\},a) = \{2, 3\}$.
$\delta'(\{2, 3\}, a) = \delta'(\{2\},a)\cup\delta'(\{3\},a) = \{2, 3\}\cup\{1\}=\{1, 2, 3\}$.

Now the question is, should state $\{1, 2, 3\}$ be considered as a final state? Sure, since the NFA, reading $baa$ has at lest one possible collection of transitions that leads to the accepting state 1. In a similar way, any state of the DFA containing 1 will be a final state, so in the DFA there will be four final states:
$$
\{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\}
$$
Now it turns out that in the DFA the state $\{1,2\}$ is never used, but that doesn't negate the fact that it's a final state (since it contains 1). All it means is that there is no transition that takes you there. It's what we call an unreachable state. This, I hope, answers your first question.

Start State. This answer to your first question has little to do with the answer to your second question. The answer for your second question is: just as we did to determine the final states of $D$, we also need to know what the start state of $D$ is, and in this case it will be the set of states containing the start state of $N_4$, along with any other states that can be reached from that start state via $\epsilon$-moves, namely $\{1, 3\}$ (which of course will also be a final state, though that's not important here).


How to calculate IV, EV and optimal k for K-means?

$C$ is a cluster, $c$ is centroid, $d$ is provided distance function, $\delta$ is Dirac measure, $x$ is element.
$IV = \sum \limits_C \sum \limits_{x \in C} d(x, c)$ meaning for each cluster calculate the sum of distances from it's centroid, and sum the results.

$EV = \frac{1}{N} \sum \limits_i \sum \limits_j\delta(C(x_i) \ne C(x_j))d(x_i, x_j)$ meaning sum the distances between elements from different clusters and divide the result by number of elements.
One possibility for optimal $k$ is to minimize $\frac{IV}{EV}$. But there are some other techniques of determining optimal number of clusters or referenced from there eight methods of finding $k$. In fact I would not state that any given method is better, preferable or can be determined blindly in advance, this is the part where you should define your optimum that makes sense to you, your data and outcome of what you use clusters for.


What is known about the sets enumerated by primitive recursive functions?

In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets:

  Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.

Note that the crux here is repetitions. Since you constructed sets, and comparing them with other sets, any repetitions do not violate their equality.


How to apply Operational Semantics to this function

You are looking for Hoare logic. Writing out the answer to the question would pretty much amount to copying the introduction to Hoare logic from Wikipedia. I suggest that you have a look at proving program correctness using Hoare logic, and try to apply it to your problem. It's actually an easy case because there are no loops. If you get stuck, come back and ask a specific question about Hoare logic.

I would break up the problem into proving several properties about hex:

The length of hex is 7 at the end.
The first character of hex is #.
All characters, except the first one, are hexadecimal digits.

Also not that the proof does not require you to write out any operational semantics. You can just use the Hoare logic to argue about your program, and there is a theorem which guarantees that Hoare logic is correct with respect to the standard operational semantics.


Complexity of membership testing for finite-regular languages

Finite-regular languages need not even be decidable. Indeed, if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\{ 1^n : \text{ the $n$th Turing machine halts on the empty input} \}$ is finite-regular but not decidable.


Finding a Hamiltonian path in this graph family

The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.

As an example, every 2-connected $(P_6,K_{1,3})$-free graph is Hamiltonian (see e.g., [1]). Further, [1] also cites some conjectures which claim that every 2-tough graph is Hamiltonian, or that every 4-connected $K_{1,3}$-free graph is Hamiltonian.

On the algorithmic side, even recognizing Hamiltonian graphs is of course well-known to be NP-complete. That is, recognition means the problem of deciding whether a given graph is Hamiltonian or not. Also, because many structural parameters remain unbounded, many classical problems also remain hard for Hamiltonian graphs (as there is no clear algorithmic foothold to exploit).

You might also enjoy Hypohamiltonian graphs, which are "almost Hamiltonian".

[1] R. Faudree, E. Flandrin, Z. Ryjacek. Claw-free graphs - a survey. Discrete Math. 164 87-147 (1997)


Let us denote by $\sigma(T)$ the sum of tags of a tree $T$. As you notice in your worked out examples, $\sigma(T)$ in general depends on the tree structure and not only on the number of nodes. What you are looking for is a tight upper bound on $\sigma(T)$ in terms of the number of nodes.

What is this tight upper bound? For each $n$, we want to know what is the maximal $\sigma$ for a tree having $n$ nodes. Denoting this by $\tau(n)$, this quantity satisfies $\sigma(T) \leq \tau(n)$ for all trees $T$ on $n$ nodes, and furthermore $\tau(n)$ cannot be replaced by any smaller value.

In fact, in practice we often don't care about finding the tight upper bound to this degree of accuracy. It is often enough to find a function $f(n)$ such that for some constant $C>0$, $\sigma(T) \leq Cf(n)$ for all trees $T$ on $n$ nodes, and furthermore for some constant $c>0$, $\sigma(T) \geq cf(n)$ for some tree $T$ on $n$ nodes.

You can prove by induction on $n$ that $\sigma(T) = O(n\log n)$ for all trees on $n$ nodes. Conversely, by taking a nearly complete binary tree $T_n$ on $n$ nodes (that is, a binary tree all of whose leaves are at heights $h,h+1$ for some $h$), you can check that $\sigma(T) = \Omega(n\log n)$. Hence $O(n\log n)$ is a tight upper bound for the sum of tags of binary trees on $n$ nodes.


Are type variables really only used in mathematical conversation about types?

I am not sure I understand your question, but I believe the answer is "yes".  When describing monomorphic languages, an expression such as

let id x = x : τ

(where τ is understood as a type meta-variable) does not mean that you can write τ in the program text.  Rather, it means an arbitrary expression of that shape, where the meta-variable is replaced by any type of the language:

let id x = x : int

let id x = x : string

etc.  The "meta" in "meta-variable" means that the "variable" in question is not part of the syntax of programs, but a device we use to talk about types abstractly -- or, as you put it, in "mathematical conversation about types."


If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if a solution $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution which whose representation grows at an exponential rate $2^n$.


Hash function orders ships from closest to furthest from the origin

You can't.  This problem is as hard as sorting, so it'll need $\Omega(n \log n)$ time (in the comparison-based model); it's not reasonable to expect a linear-time algorithm for sorting.

The obvious solution is to sort the points by their distance from the origin.  If the hash function computes the distance from the origin, well, then you're just sorting hash values.


Solve longest common subsequence in a non dynamic programming way?

Your approach is correct in the sense that you produce the correct results.

The book's approach has a time complexity of $O(mn)$. Since your solution doesn't use memoization and recomputes the same results repeatedly, the time complexity is much worse. In fact, your approach is functionally equivalent to the brute force method, which has a time complexity of $O(2^n)$.

Note that with

String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);

You recompute a subset of the problem on every single iteration without saving any of the results. The purpose of memoization is to save the results of the sub problems (so you don't have to recompute them) and then use those results to construct a solution to your original problem.