Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that.

The results are not general in terms of machines. Run your benchmark on another computer and you get different results for sure, quantitatively, and maybe even qualitatively.
The results are not general in terms of programming languages. Different languages may cause very different results.
The results are not general in terms of implementation details. You literally compare programs, not algorithms; small changes in the implementation can cause huge differences in performance.
If the worst-case is rare, a random input sample may not contain a bad instance. That is fair if you are concerned with average case performance, but some environments require worst-case guarantees.
In practice, input sets change. Typically, inputs become larger over time. If you don't to repeat your benchmark every six months (yes, some data grow that fast), your results are worthless soon¹.

That said, ignoring all kinds of effects and constants in the analysis is typical, but can be called lazy (with respect to practice). It serves to compare algorithmic ideas more than to pinpoint the performance of a given (even pseudocode) implementation. It is well known to the community that this is coarse and that a closer look is often necessary; for example, Quicksort is less efficient than Insertion sort for (very) small inputs. To be fair, more precise analysis is usually hard².

Another, a posteriori justification for the formal, abstract viewpoint is that on this level, things are often clearer. Thus, decades of theoretic study have brought forth a host of algorithmic ideas and data structures which are of use in practice. The theoretically optimal algorithm is not always the one you want to use in practice -- there are other considerations but performance to make; think Fibonacci heaps -- and this label may not even be unique. It is hard for a typical programmer concerned with optimising arithmetic expressions would come up with a new idea on this level (not to say it does not happen); she can (and should) perform those optimisations on the assimilated idea, though.

There are formal, theoretic tools to close the gap to practice to some extent. Examples are

considering memory hierarchy (and other I/O),
analysing the average case (where appropriate),
analysing numbers of individual statements (instead of abstract cost measures) and
determining constant factors.

For example, Knuth is known for literally counting the numbers of different statements (for a given implementation in a given model), allowing for precise comparison of algorithms. That approach is impossible on an abstract level, and hard to do in more complex models (think Java). See [4] for a modern example.

There will always be a gap between theory and practice. We are currently working on a tool³ with the goal to combine the best of both worlds to make sound predictions for both algorithmic costs and runtime (on average), but so far we have not been able to do away with scenarios where one algorithm has higher costs but smaller runtime (on some machines) than an equivalent one (although we can detect that, and support finding the reason).

I recommend for practictioners to use theory to filter the space of algorithms before running benchmarks:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

There can be crazy changes in absolute and relative performance once the number of cache misses increases, which typically happens when inputs grow but the machine stays the same.
As in, leading researchers in the field are not able to do it.
Find the tool here. An example use has been published in Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al. (2012) [preprint]
Average Case Analysis of Java 7’s Dual Pivot Quicksort by S. Wild and M. Nebel (2012) -- [preprint]


Looking for a dictionary of math/CS notation

You can use this sheet. It has a lot of handy formulas and some definitions.

You can also use Wikipedia's list of mathematical symbols propsed by Kyle Jones in comments.

There is also Worfram MathWorld which is a great resource, but you need to know what are you looking for.

When it comes to printed resources, each volume of The Art of Computer Programming has a great reference of mathematical notations, especially volume 1.


Complement of a DFA without final states

It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (There are many other such algorithms. For example, Hopcroft's state minimization algorithm doesn't work on incomplete automata, at least without some adjustment.)

If the DFA you are referring to is complete and has no non-accepting states, then it must be the case that it recognises $\Sigma^*$ so that its complement is the empty set. But I have a hunch that's not the case.

You can always convert an incomplete DFA into a complete DFA by adding a single non-accepting state with a looping transition on every symbol. (This is usually called the "sink" state, because there is no way out.) Then for every other state which has no transition on one or more symbols, you add all the missing transitions with the sink state as a destination. Since the sink state is non-accepting and non-escapable, this operation does not in any way alter the language recognised by the DFA.

Once you've done that, it is (probably) no longer the case that every state in the DFA is accepting; there is now one non-accepting state. And the complement algorithm will make that non-accepting state accepting, and all the other states non-accepting, which will produce the complement of the language.


Are files download times actually unknowable due to the halting problem?

Not at all.
The halting problem says it is impossible to decide whether an arbitrary turing machine with arbitrary input will halt. But there are many, many specific turing machines where we can prove that they halt for every input, or where we can look at the input and decide if the turing machine will halt or not.
And since the people writing the download code surely wrote it in such a way that it is guaranteed to finish for every import, there will be a proof that it is guaranteed to finish.


Find a subsequence with fastest time for specific distance

You cannot generally get time for exactly $100$ meters with this data. The better approach would be to search for the longest run within some multiple of $2$ seconds.

Find the longest distance run in $2\cdot k$ seconds:

Set desired k.
Set i = 0 and j = k-1.
Set currentSum = maxSum = totalMeters[j].
While j < totalMeters.length - 1 do

i++; j++;
currentSum = totalMeters[j] - totalMeters[i]
if currentSum > maxSum then maxSum = currentSum

This should also give you an idea how to build other similar algorithms for this problem, if you don't change your approach.


proving that if graph has perfect elimination order than the graph is perfect

Here's a route you can take.
Prove (or use the fact) that a graph is chordal iff it has a perfect elimination order. Now, it will suffice to show that a chordal graph is perfect. For that, you can take the strong perfect graph theorem stating that a graph is perfect iff it contains no odd hole and no odd antihole. Proceed by contradiction.


How does the memory of a 64bit and 32bit processor work

No, the author is wrong.

I have used 32 bit processors that could address 64 GB of RAM. Memory is restricted by the number of address lines, multiplied by the number of bytes addressed by each individual value of address lines.

Address space of one application was limited to 4GB, but you could have a dozen applications running at the same time, each using several GB.

The author also seems to be quite ignorant of what processors and operating systems exist.


Hit/Miss in a 2-way set associative cache with offset

No, you don't need to have a match for the offset. When you 'miss' some address (= when its not in the cache) , the whole block is copied from the memory to the cache. i.e for address $001111$ , we will copy the 4 word block: $001100$ , $001101$ , $001110$, $001111$  to the cache. Therefore, for example, in line 4 you get a 'hit', not a miss.

So a hit is encountered as soon as the Index and the Tag match. The offset tells you which word from the block you want to read, as there are 4, and you want only 1. for example, for $001111$ it will skip the first 3 words and read the fourth.

EDIT: if I remember correctly, in a 2-way you need 3 offset bits and not 2. 1 bit is 'block offset' so you know in which block of the 2 has your word (because there are 2 blocks with same tag and index).


How to efficiently specify a MILP constraint with nested AND and ORs

It can be done with two auxiliary variables, y1,y2:

x1 >= y1
x1 >= y2
x1 <= y1 + y2

x2 + x3 + x4 >= 3*(y2 - y1)
x2 + x3 + x4 <= 2 + y1 + y2

x5 + x6 >= 2*(y1 - y2)
x5 + x6 <= 1 + y1 + y2

x7 >= y1 + y2 - 1
x7 <= y1 + y2

The idea here is that if (y1,y2) = (0,1), then the first and-clause is forced to be true; if (y1,y2) = (1,0), then the second and-clause is forced to be true; if (y1,y2) = (1,1), then the third and-clause is forced to be true; and if (y1,y2) = 0, then all three and-clauses are forced to be false.

In other words, (y1,y2) represents the index (in binary) of which of the three and-clauses is true; or (0,0) if none of them are true.

I would be surprised if it is possible to encode your constraint using only a single auxiliary variable.

This trick can be generalized: if you have an OR of $2^k-1$ AND-clauses, then you can find an encoding that uses $k$ auxiliary variables.


What is the time complexity of this аlgorithm? O(n * r)

Investigating worst-case cost is rarely useful for randomized algorithms. Here, the worst case is indeed that the loop never stops -- but this event has probability zero!

Instead, perform average-case analysis. What is the probability of the loop running $k$ times?

   That means it misses the interval $k-1$ times, and then hits it. Assuming that rand7 has indeed uniform distribution, the probability of the former is $\frac{2}{7}$, and of the latter $\frac{5}{7}$. The result is, assuming that separate calls of rand7 are stochastically independent, $\bigl(\frac{2}{7}\bigr)^{k-1} \cdot \frac{5}{7}$.

Now you compute the expected number of iterations using basic facts from stochastics.

   The above weights are those of a geometric distribution. Looking up its properties, we learn that its expected value is $\frac{7}{5}$.

As it turns out, this is not too bad. You can also investigate the standard deviation or compute some probabilities to get a feeling for how unlikely high iteration counts are.


Given an CFG determine if $\varepsilon \in L(G)$

You can transform the CFG to Greibach normal form, and then simply check whether the rule $S\rightarrow \varepsilon$ exists.

In fact, you are asking whether there is a parsing algorithm for CFG.


Complexity of algorithm inserting an element in a circular linked list at the front end

The method used in practical scenarios depends on the scenario (and on the programmer). There are several possible issues influencing the choice of implementation:

Whether the algorithm is known to the programmer.
Ease of coding (it's easiest if it's already implemented in some library you can use).
Speed - that depends on how the data structure is used.
Space overhead taken by the data structure.

An intelligent programmer should take all of these into account, and try to make themselves more knowledgeable of various algorithms and data structures.


Independent set where two vertices need to have distance >= c

Yes, this is called ruling set.
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in [1] but there might be prior references.)

[1] Korman et al. Toward more localized local algorithms: removing assumptions concerning global knowledge. PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing
Pages 49-58


Can Deterministic Context free Grammars be ambiguous?

No, there is no deterministic context-free grammar that is ambiguous since any deterministic context free grammar (DCFG) must be unambiguous.

Here is definition 2.47 of the book introduction to the theory of computation, third edition, by Michael Sipser.

  A deterministic context-free grammar is a context-free grammar such that every valid string has a forced handle.

Furthermore, here is definition 2.62.

  An LR($k$) grammar is a context-free grammar such that the handle of every valid string is forced by lookahead $k$.

A DCFG is the same as an LR(0) grammar. All LR($k$) grammars are unambiguous, by definition.


what does activation function become in spiking neural network?

The activation function would be inherent to the spiking model used.

Each model  have a different dynamic which will depend on the proper model and parameters used.


Here is the algorithm for $n=10$.

Throw the dice twice to get $(x,y)$.
Compute $r=x + 6(y-1)$. If $r\le10$, return $r$ and stop.
If we have reached here, go back to step 1.

Here is the algorithm for general $n$.

Compute $n=\lceil \log_6k\rceil$.
Throw the dice $n$ times to get $(x_1, x_2, \cdots, x_n)$.
Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+\cdots+6^{n-1}(x_n-1)$. If $r\le k$, return $r$ and stop.
If we have reached here, go back to step 2.

There are many variations, of course.

For example, in step 2 for $n=10$, we can return $r=10 - (x + 6(y-1))\%10$ and stop  when $x+6(y-1)\le30$ instead. This will reduce the chance to go to step 2. Here % is the remainder operator.

For example, here is gnasher729's algorithm for $n=10$. Throw a dice until we get a number $x\not=6$. Throw the dice once more to get another number $y$. Return ((x - 1) * 6 + (y - 1))%10+1$.

(Exercise 1.) (One minute or less) Devise an algorithm for $n=3$.

(Exercise 2.) Devise an algorithm for $n=7$. Try making its expected number of rolls as small as possible.

(Exercise 3.) Prove that the expected number of rolls in gnasher729's algorithm is the minimum among all algorithms.

(Exercise 4.) Given any $n>1$, devise an algorithm with the least expected number of rolls.


Is a compiler a kind of Gödel numbering program?

No. Consider the following two C functions:
int f(int a) {
    return a * 2;
}

int g(int a) {
    return a + a;
}

If we're being a bit liberal here, both are "well-formed formula of some formal language". Yet most C compilers with optimization turned on will compile these two functions to the exact same code. This violates the uniqueness of a Gödel numbering.


O(n) Palindromic Substring: Why is O(n^2) needed here?

Consider the following string
$$ dabacabac $$
When you go to compute $T(9)$ (using one indexing), you have $T(8) = 7$. But since
$$ T(1) = d \neq c = T(9) $$
You will put $T(9) = 1$, when it should be $T(9) = 5$.


There is a relatively straightforward solution where each query and each update can be done in $O(\log^2 n)$ time.  The data structure uses $O(n^2)$ space.

We will have $\lg n$ "granularities" of data structure, one for each power of two $2^m$ such that $1 \le 2^m \le n$.  The data structure for granularity $2^m$ stores the sums

$$\sum_{i=k_0 \cdot 2^m}^{(k_0+1) \cdot 2^m -1} \sum_{j=0}^{l-1} M[i,j]$$

for each $k_0,l$.  This data structure for granularity $2^m$ can in turn be represented using $n/2^m$ balanced trees (one for each possible value of $k_0$) to store prefix sums.

Now to look up the prefix sum for $k,l$, we break up the interval $[0,k-1]$ into a union of intervals of power-of-two length; at most $\lg n$ intervals are needed.  For each such interval of length $2^m$, we do a lookup into the data structure of granularity $2^m$.  Thus queries can be answered by doing $O(\log n)$ lookups into a balanced tree, each of which takes $O(\log n)$ time, for a total time of $O(\log^2 n)$ per query.

Updates can also be done in $O(\log^2 n)$ time.  To update $M[i,j]$, for each granularity $2^m$, you update the appropriate balanced tree in the data structure of granularity $2^m$.  This is $O(\log n)$ updates oin $O(\log n)$ balanced trees; each such takes $O(\log n)$ time, so the total time is $O(\log^2 n)$ time.

Finally, the data structure of granularity $2^m$ contains $n/2^m$ trees, each taking up $O(n)$ space, so the total space usage is $O(n^2 \cdot (1 + 1/2 + 1/4 + \cdots)) = O(n^2)$.


The same outgoing and incoming degree in graph

If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.


Why does a polynomial-time language have a polynomial-sized circuit?

Cook-Levin gives one circuit for all inputs of a given size. So although the circuit depends on the input $x$, it only depends on the size of the input. So given TM $M$ with running time $t$, and a number $n$ (the size of input), Cook-Levin gives a circuit $C_n$ of size roughly $t^2$ that solves the problem on all inputs of size $n$. The circuit $C_n$ does not depend on what are the bits of the input for $M$, however we need to know the numbers of input bits as that is going to be the number of input bits for the circuit.


Determining asymptotic notation of a complex function

If you check the definitions, big-O means "bounded from above" (with a fudging constant $c$ multiplying it all, starting at a high enough $n$), you can disregard "constants multiplying" and "slower growing terms"; so you can say:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = O(n^2 \log n)
\end{equation*}$

(could also say $O(n^3)$, or $O(n^4 \log^{10} n)$ for that matter, bound from above).

For a lower bound, the same works fine:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = \Omega(n^2 \log n)
\end{equation*}$

For a lower bound, $\Omega(1)$ or $\Omega(n \log n)$ work fine too.

As you have the same upper/lower bound:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = \Theta(n^2 \log n)
\end{equation*}$

Finding values of $c$ and $N_0$ I leave to you. They can be different for $O$ and $\Omega$!


Prove $\varphi(x)$ to be primitive recursive

To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as programming asignments (in a rather cruel programming language).


$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ has been proved in Strengths and Weaknesses of Quantum Computing Bennett et al. (arXiv).

According to the complexity zoo, $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$.


Let the given string be $S$.  For a string $T$ that appears as a subsequence of $S$, we say that the list of positions $(x_1, \dots, x_{|T|})$ is an appearance of $T$ in $S$ if $S[x_1]S[x_2]\dots S[x_{|T|}] = T$.  The leftmost appearance of $T$ in $S$ is the unique one for which each position is minimal over corresponding positions in all appearances -- that is, $X$ is the leftmost appearance of $T$ in $S$ iff for all $1 \le i \le |T|$ and all appearances $Y$ of $T$ in $S$, $X[i] \le Y[i]$.  This leftmost appearance can be calculated with a simple greedy algorithm in which we loop through the characters of $T$, pairing each with the next available matching character in $S$.  Define $L(T)$ to be the last (rightmost) position in the leftmost appearance of $T$ in $S$.

Example: $S = abbaba$, $T = ba$.  The appearances of $T$ in $S$ are $(2, 4), (2, 6), (3, 4), (3, 6)$ and $(5, 6)$.  The unique leftmost appearance is $(2, 4)$, so $L(T) = 4$.

We say a subsequence $T$ of $S$ requires position $i$ of $S$ iff $L(T) = i$.  What this means is that $T$ is not a subsequence of $S[1 \dots i-1]$ -- the only ways to produce $T$ from $S$ involve including either the character at position $i$ in $S$, or some identical character further to the right.  The important thing to notice is that any subsequence $T$ of $S$ requires a unique position: the one given by by $L(T)$.  So if for each $1 \le i \le |S|$ we can count the number of subsequences of $T$ that require $i$, we can add these all up to obtain the total number of unique subsequences of $S$.

Let $r(i)$ be the number of subsequences of $S$ that require position $i$.  We can compute $r(i)$ by counting the total number of subsequences of $S$ that include position $i$ and end there, and then subtracting off the number of these subsequences that don't require $i$.  Calculating the number of subsequences that end at $i$ but don't require it is surprisingly easy to do, thanks to the following observation:

For every $1 \le j < i$ such that $S[j] = S[i]$, every subsequence that requires $j$ can be turned into an appearance of the same subsequence that ends at $i$ but doesn't require $i$ -- and there are no other subsequences that end at $i$ but don't require it.  (Specifically, we could remove the final character (taken from position $j$ of $S$) and append position $i$, and the appearance formed this way yields the same subsequence.)

So we have $r(i) = \sum_{1\le k<i} r(k) - \sum_{1\le j<i, S[j]=S[i]} r(j)$.

(The first summation is the number of subsequences we get by appending $S[i]$ to each of the unique subsequences we have already seen; the second subtracts off subsequences we have seen before.)

The first summation is easy to optimise: It's just a running total.  The second summation can also be optimised further by tracking, for each distinct character, the sum so far of unique subsequences ending with that character:

$r(0) \gets 1$
For $i$ from 1 to $|S|$:

$r(i) \gets t - u[S[i]]$
$t \gets t + r(i)$
$u[S[i]] \gets u[S[i]] + r(i)$

Summing $r(i)$ values as they are computed allows the answer to be computed in linear time.


What is the evidence that P could equal NP?

This is a rather strange question to ask, given that a large majority of complexity theorists believe that P is different from NP. All the evidence we have points at P being different from NP, which is why most people believe that P doesn't equal NP.

It's like asking a climate scientist for the evidence that there is no connection between global warming and greenhouse gasses. The main difference is the standard of proof involved. The climate scientist is content with trying to convince you that there is strong evidence for anthropogenic global warming. The complexity theorist's goal is a proof, and she would not settle for less.

That said, much of complexity theory tacitly relies upon P being different from NP: if P were to equal NP, many of the results would be meaningless. Officially, such results are stated as "if P$\neq$NP then X" (such results are known as conditional results). However, the perceived semantics is simply "X holds".

Sometimes the results need a strong assumption, "if A then X", for various different As. The weaker the A, the stronger the result. Some of the assumptions A don't enjoy widespread acceptance, for example the Unique Games Conjecture. Others are considered pretty likely, such as the (Strong) Exponential Time Hypothesis. All of these are stronger assumption than P$\neq$NP (that is, they imply that P$\neq$NP).


Is this a proper Max Heap Data Structure

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest.

Min Heap has the property:for every node i (except root node) Array[parent(i)]<=Array[i]. So the smallest element in a min-heap is at the root.

Max Heap is organized in opposite way, i,e. it has the property: for every node i (except root node) Array[parent(i)]>=Array[i]. So the largest element in a Max-heap is at the root.

You can check if the array is maintaining the heap property by the following algorithms.

Algorithm 1

Parent(i)
    return floor(i/2)

Algorithm 2

Left(i)
    return 2*i

Algorithm 3

Right(i)
   return 2*i+1

Now you can check on your own that if your array maintaining Max heap property or not.

It is not mandatory that two heaps with same elements have same arrangement.The thing you have to be conform that if all elements are maintaining the heap property or not.


Star-free decomposition of regular language given by regular expression

No.  If the regular expression encodes an infinite language, then there is no way to decompose it that way.  Without the Kleene star, regular expressions can only express finite languages.

I realize this is a rather trivial answer, and it begs the next question: what if we are promised that the language is finite?  In that case, the answer is yes.  Here are two ways to see that the answer is yes:

Approach #1: Since the language is regular, we can find a DFA that recognizes it -- let's choose the minimal DFA.  Since the language is finite, this DFA will not have any loops in it.  Now if you apply the standard algorithm for converting a DFA to a regular expression, the result is a star-free regular expression.  In fact, you get out only a single regular expression.

Approach #2: If the language is finite, then you can enumerate all of the words in the language, say $L=\{w_1,w_2,\dots,w_n\}$.  Therefore $w_1 + w_2 + \dots + w_n$ is a regular expression for $L$.

Credit: The answer for the case where the language is finite is due to @J.E. Pin.


Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?

It is not possible to have an algorithm that is faster than $O(n^2)$ as the output can be $O(n^2)$ — all pairs. This can happen when all numbers are divisible by 10, or all are returning 5 when taken modulo 10.


Complexity of calculating average across distributed network?

You could rely on the fact that, as @polygeric alluded to, the average of a set of numbers is the average of the averages over any partition of the original numbers. In other words, have each node compute the average of its $D$ numbers, send those $N$ averages somewhere and compute their averages.

How you do that efficiently will depend on the network topology and the communication protocol.


Prove that the language of squares is not regular using homomorphism

As illustrated by other answer and comments there seems to be no easy way just using morphisms. Still it is a good observation that simple closure properties can be of help.
In your case I would suggest intersection with regular languages as a tool: $L\cap 0^*10^*1 = \{0^n10^n1 \mid n\ge 0\}$ whch some recognize immediately as non-regular.

Alternatively one could include morphisms, inverse morphisms and intersection with regular languages (or, equivalently, finite state transductions). With these regularity preserving operations $L$ can be transformed in to $ \{a^nb^n \mid n\ge 0\}$, mother of all non-regular examples.


Is this a correct way to thing about asymptotic notations?

The answers and comments by other users here do a good job of explaining how the notation works, so I figure I'll explain why the notation is used this way. The reason for the notation is already evident in your question: writing out the set inclusion explicitly makes it way more verbose.

When you are learning asymptotic notation for the first time, it is helpful to clearly state that $O$, $\Theta$, etc. are not functions and that "equality" does not behave like equality in statements involving these symbols. But when you are an expert in a field reading a hundred-page paper written by other experts in the same field to communicate with their kin, you really don't want to have to read this kind of boilerplate over and over again if you can avoid it.

The purpose of asymptotic notation is to allow the author to state theorems and intermediate steps in an extremely compact fashion. When you read something like $f(n) = 5n^3 + 3n^2 + o(n^2)$, what you are really reading is, "$f(n)$ is equal to $5n^3 + 3n^2$ plus a bunch of junk that neither you nor I have time to care about because it is sufficiently small that its exact value is irrelevant to the correctness of the rest of the argument I am about to present". Writing everything out in terms of statements about sets would obscure the point the author is trying to communicate.


The physical implementation of quantum annealing algorithm

The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be implemented in any universal model of quantum computation.

In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.

The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.

The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.

The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H_0 + (t/T)H_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H_1$.

It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H_0$ and $H_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.


Are fully connected layers required for convnets?

There are no rules.  You can do whatever you like.  The ultimate test is how well it works; you'll have to try it and see.

But the short answer is: no, fully connected layers are not required.  You can build a network that is purely convolutional, with no fully connected layers.  It's hard to know how well it will work, without trying it.


How does the halting theorem interact with the recursion theorem?

The recursion theorem states that for every two-place partially computable function $t$ there is a program $R$ which computes a partial function $r$ satisfying
$$ r(w) = t(\langle R \rangle, w) $$
for all $w$. The function $t$ is given by a program that doesn't necessarily halt, and so we can think of it as a function from $\mathbb{N}^2$ to $\mathbb{N} \cup \{ \bot \}$, where $\bot$ means that the program doesn't halt. We call such a function a partial function, since a different way of specifying such a function is as a function from some subset $S \subseteq \mathbb{N}^2$ to $\mathbb{N}$; the function doesn't halt on inputs outside $S$.

The equality $r(w) = t(\langle R \rangle, w)$ is an equality of partial functions: the functions have the same domain (or the same set of inputs on which the output is a natural number rather than $\bot$), and they agree on their domain.


Briefly, lexical analyzer reads source code character by character and generates tokens. It does not care about in what order tokens are generated. Relationship between tokens are checked by syntax analyzer and specified by a context free grammar. Let me give you a simple example. Consider the following piece of code

 int while = 5

Lexical analyzer emmits the following tokens:

KEYWORD (INT)
KEYWORD (WHILE)
ASSIGN (=)
NUMBER (5)

Then then syntax analyzer checks these tokens, detects (based on the corresponding CFG) that the keyword WHILE cannot be lvalue, and reports the syntax error. In fact the syntax analyzer expects IDENTIFIER after the token KEYWORD (INT).


Why do we need Kleene Star when there is concatenation?

Regular expressions without Kleene star define finite languages. You can prove this by induction on the structure of the regular expression. In contrast, $a^*$ is a regular expression which defines an infinite language.
We could try to define $a^*$ using concatenation and union:
$$ a^* = \epsilon + a + a^2 + a^3 + \cdots $$
Unfortunately, the required regular expression is infinite, which we do not allow (infinite expressions do make sense in some contexts, for example in infinitary logic, but not here).


Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?

Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.


Slowest growing upper bound for the minimum length of a complementary prefix regular expression

Wikipedia says that taking the complement "can cause a double exponentially blow-up of its length" and cites the following paper:

Succinctness of the Complement and Intersection of Regular Expressions.  Wouter Gelade and Frank Neven.  STAC 2008.

In particular, they give a concrete language that triggers the doubly exponential blowup.  See Theorem 4.1 in the paper.

That paper considers the normal representation for regexps rather than postfix, but I don't see any reason to expect that to change the bottom line.  You could work through their example and their proof if you want to be sure.


On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

The quadratic knapsack problem is NP-hard.  Therefore, the cardinality-constrained quadratic knapsack problem is NP-hard, too (as Yuval says, just don't use any cardinality constraints).

If problem X is a special case of problem Y, and problem X is NP-hard, then so is problem Y.  Now let X = CCQKP and Y = QKP.


Maximum value of LOOP-Program turing-computable


XOR is an associative operation, so $x_i \oplus x_j \oplus x_k$ is unambiguous. There are in fact four satisfying assignments, given by
$$ (x_i,x_j,x_k) \in \{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\}. $$

XOR satisfies the useful property
$$ (-1)^{x \oplus y} = (-1)^x (-1)^y. $$
Therefore $x_i \oplus x_j \oplus x_k = 1$ is the same as
$$ (-1)^{x_i} (-1)^{x_j} (-1)^{x_k} = (-1)^1.$$
If we think of our variables as $X_i = (-1)^{x_i}$, then the equation $x_i \oplus x_j \oplus x_k = 1$ is completely equivalent to $X_i X_j X_k = -1$. Since XOR is really just addition in the group $\mathbb{Z}_2$, you can think of both formulations as linear equations.

Yet another interpretation of XOR is in terms of sets. Just as AND corresponds to intersection and OR to union, the XOR operation corresponds to symmetric difference, sometimes denoted $\triangle$ or $\Delta$. You can easily check that $x_S x_T = x_{S \triangle T}$, essentially using $x_i^2 = 1$.


Coverage problem (transmitter and receiver)

You can use the Voronoi diagram, together with Kirkpatrick's data structure to solve this problem.

Like Raphael and Syzygy suggested, you can use Fortune's (sweepline) algorithm to create the Voronoi diagram. Worst case time: $\mathcal{O}(n \log n)$.

The Voronoi diagram will have a bunch of polygons, each one containing a transmitter. Any point within the polygon is closest to that transmitter. Thus, if you can find out which polygon contains the receiver, you can find the closest transmitter to it by somehow finding out which polygon it is in. After that, you check if that transmitter is within $1\ \text{km}$.

To determine which Voronoi polygon contains the receiver, you first triangulate each polygon in the diagram. Now you have a triangle mesh. Next you use Kirkpatrick's data structure to locate any triangle containing a given point in $\mathcal{O}(\log n)$ time, worst case. Constructing Kirkpatrick's data structure takes $\mathcal{O}(n\log n)$ worst case. Once you know the triangle, you will know the polygon that contains it, and thus the closest transmitter. Doing this for all the receivers will be $\mathcal{O}(n\log n)$, worst case.

  Each cell in a Voronoi
  diagram is a convex polygon, possibly
  unbounded.

  ...

  The number of vertices [of a Voronoi diagram of n sites] V ≤ 2n-5

  ― www.cs.arizona.edu

Each polygon in a Voronoi diagram is a convex polygon. Therefore, since triangulation of a convex polygon takes $\Theta(v)$ time, $v$ being the number of of sides, we can triangulate each cell efficiently. If you fear that triangulation can be pathological (that we might have $n$ cells, each with $n$ sides), then consider this. The Voronoi diagram has $\mathcal{O}(n)$ vertices (see quote above). The triangulation of the Voronoi diagram is planar, and so is a sparse graph, and thus has $\mathcal{O}(n)$ edges and faces. Thus triangulation of a particular cell might take $\mathcal{O}(n)$, but the overall triangulation also takes $\mathcal{O}(n)$. (Basically, we will not encounter many cells with $\mathcal{O}(n)$ sides, this would result too many triangles for a planar graph).

Great explanation/implementation of Fortune's algorithm
Illustration of Kirkpatrick's data structure
Psuedocode for Kirkpatrick's algorithm


What would "sum types with functions" look like in OOP?

The key to remember is that there's a sort of dualism between functional sum types, and OOP implementations of a superclass or interface:

Sum types require the variants for a type to  be specified up front, and for every operation, requires that we specify the operation for each variant. Adding a new operation is easy, adding a variant requires refactoring all functions.
OOP requires that we specify the operations for a type up front, and each implementation/subclass specifies its own implementation for each operation. Adding a new variant is easy, but adding a new operation requires refactoring in each subclass.

In each case, we have all possible pairs of variants and operations, but we differ on how we group them: all the implementations for variants in an operation together, or all the operations for a variant together.

  It's fair to summarize classes in OOP as "product types with functions."

At its most barebones version, maybe.  But this ignores any subtyping structure. Many versions of OOP are much richer, with interfaces being analogous to existential types.

As for the question of "what if we just did sum-types with functions", this would be pretty boring. You would specify a bunch of variants for your type, and then a bunch of operations your type, which would have to specify an implementation for each variant.

This is basically just a normal OOP type with a single member variable that's a sum-type, and a bunch of functions operating on that variable.


Explanation of Heavy light decomposition

I am taking this from http://wcipeg.com/wiki/Heavy-light_decomposition

Essentially the decomposition tells you which, if any, subtrees at a node N take up more than half the weight of the tree rooted at N.  Such a subtree gets an edge coloured with the word "Heavy" the rest get coloured "Light".  Note that there can be at most one heavy subtree at any given node.

Here is an implementation in Haskell.

module HLDecom where

{- |
  This data type has data in the leaves and nodes
  that collect a list of subtrees each of which is
  paired with b-type data.  The b should be thought
  of as information on the edge connecting the node
  to the subtree.
-}
data Tree a b = Leaf a | Node [(b,Tree a b)]

data Color = Heavy | Light

size :: Tree a b -> Integer
size (Leaf x) = 1
size (Node ns) = 1 + sum (map (\(a,b) -> size b) ns)

{- |
  The Heavy-Light decomposition of a tree is a
  colouring of the tree's edges with
  either Heavy or Light.

  If the size of a subtree at a node is more
  than half the size of the tree at the node,
  then the edge connecting the node to that
  subtree is heavy otherwise it is light.

  It should be obvious that at any given node,
  there can only be one such heavy subtree
  (there can only be one subtree that
  has > 1/2 the weight), and further we can find
  this subtree by finding the maximum size subtree.
  If this size is more than half the size of
  the whole tree, then it is colored Heavy.

  The implementation below could certainly be
  improved for efficiency; however, the focus
  on being direct and clear.
-}
--hlDecomp :: Tree a b -> Tree a Color
hlDecomp (Leaf x) = (Leaf x)
hlDecomp (Node ns) =
  let
    sizeOfNode = size (Node ns)
    heavyLight = map (\(b,tree) ->
       if size tree >
          sizeOfNode `div` 2
          then (Heavy,tree)
          else (Light,tree)) ns
  in
    Node heavyLight


Does this loop invariant guarantee that the variable never changes?

The loop invariant doesn't "guarantee" anything. It is a summary of relevant information you know about the state of the program when it reaches that point. If your loop is e.g.:

k = 5;
...
for(int i = 0; i < N; i++) {
   /* Invariant: k = 5 */
   ...
   k = 207;
   ...
   frob_very_hard(&k);
   ...
   k *= 3;
   ...
   k = 5;
}

at the marked point k == 5, but not all over the program.


How to show that a function is not computable?

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist?

[notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$]

Undecidable languages do exist

There are some languages that no Turing machine can decide. The argument is simple: there are "only" countably many $(\aleph_0)$ different TMs, but uncountably many $(\aleph)$ different languages. Thus there are at most $\aleph_0$ decidable languages, and the rest (infinitely many) are undecidable. Further reading:

"Why are there more non-computable functions than computable ones?" and
"Why are the total functions not enumerable?".

In order to put our hand on a specific undecidable language, the idea is to use a technique named diagonalization (Georg Cantor, 1873) which was originally used to show that there are more real numbers than integers, or in other words, that $\aleph > \aleph_0$.

The idea for constructing the first undecidable language is simple: we list all Turing machines (which is possible since they are recusively enumerable!), and create a language that disagrees with each TM on at least one input.

$$
\begin{array}{c|ccccc}
    & \varepsilon & 0 & 1& 00 & \cdots \\ \hline
M_1 & \color{red}{1} & 0 & 1 & 0 & 1 \\
M_2 & 0 & \color{red}{1} & 0 & 0 & 0 \\
M_3 & 0 & 0 & \color{red}{0} & 1 & 0 \\
\vdots & & & & \ddots &
\end{array}
$$

In the above, each row is one TM and each column is one input. The value of the cell is 0 if the TM rejects or never halts, and 1 if the TM accept that input.
We define the language $D$ to be such that $D$ contains the $i$-th input if and only if the $i$-th TM does not accept that input.

Following the table above, $\varepsilon \notin D$ since $M_1$ accepts $\varepsilon$. Similarly, $0\notin D$, but $1\in D$ since $M_3$ does not accept $1$.

Now, assume $M_k$ decides $D$ and look up line $k$ in the table: if there is $1$ in the $k$-th column, then $M_k$ accepts that input but it is not in $D$, and if there is a $0$ there, the input is in $D$ but $M_k$ does not accept it. Therefore, $M_k$ doesn't decide $D$, and we reached contradiction.

Now for your question. There are several ways to prove that a language is undecidable. I'll try to touch the most common ones.

1. Direct proof

The first method, is to directly show that a language is undecidable, by showing that no TM can decide it. This ususally follows the diagonalization method shown above.

Example.

  Show that the (complement of the) diagonal language
  $$\overline {L_D} = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}$$
  is undecidable.

Proof.
Assume $\overline {L_D}$ is decidable, and let $M_D$ be its decider. There are two cases:

$M_D$ accepts $\langle M_D \rangle$: but then, $\langle M_D \rangle \in L(M_D)$ so $\langle M \rangle \notin \overline {L_D}$. So this can't happen if $M_D$ decides $\overline {L_D}$.
$M_D$ does not accept $\langle M_D \rangle$: so
$\langle M_D \rangle \notin L(M_D)$ and thus $\langle M \rangle \in \overline {L_D}$. But if it is in $L_D$, $M_D$ should have accepted it, and we reached contradiction again.

2. Closure properties

Sometimes we can use closure properties to show some language is not decidable, based on other languages we already know not to be decidable.

Specifically,
if $L$ is not decidable (we write $L\notin R$), then also its complement $\overline{L}$ is undecidable: if there is decider $M$ for $\overline{L}$ we could just use it to decide $L$ by accepting whenever $M$ rejects and vice versa. Since $M$ always halts with an answer (it is a decider), we can always invert its answer.

Conclusion: The diagonal language ${L_D} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \}$ is undecidable, $L_D \notin R$.

A similar argument can be applied by noting that if both $L$ and its complement $\overline{L}$ are recursively enumerable, both are decidable. This is particular useful if we want to prove that a language is not recursively enumerable, a strong property than undecidability.

3. Reducing from an undecidable problem

Usually, it's quite difficult to directly prove that a language is undecidable (unless it is already constructed in a "diagonal" fashion). The last and most common method for proving undecidability is to use another language which we already know to be undecidable. The idea is to reduce one language to another: to show that if one is decidable, then the other must also be decidable, but one of them is already known to be undecidable which leads to the conclusion that the first one is also undecidable. Read more about reductions in  "What are common techniques for reducing problems to each other?".

Example.

  Show that the diagonal language
  $$HP = \{ \langle M,x \rangle \mid M \text{ halts on } x \}$$
  is undecidable.

Proof.
We know that $L_D$ is undecidable. We reduce $L_D$ to $HP$ (this is denoted $L_D \le HP$), that is, we show that if $HP$ was decidable we could use its decider to decide $L_D$, which is a contradiction.

The reduction works by converting a candidate $w$ for $L_D$ (i.e. an input for any potential decider/acceptor for $L_D$) to a candidate $w'$ for $HP$ such that $w\in L_D$ if and only if $w' \in HP$. We make sure that this conversion is computable. Thus, deciding $w'$ tells us whether or not $w\in L_D$, so if we can decide HP we would be also able to decide $L_D$.¹

The conversion is as follows. Take some $w=\langle M \rangle$, and output $w'=\langle M' , \langle M \rangle\rangle$,² where $M'$ is a TM that behaves just like $M$, but if $M$ rejects, then $M'$ goes into an infinite loop.

Let's see that $w,w'$ satisfy the requirements.
If $w\in L_D$, it means that $M$ halts and accepts the input $\langle M\rangle$. Therefore, $M'$ also halts and accepts the input $\langle M\rangle$.
Thus, $\langle M', \langle M\rangle \rangle \in HP$.
On the other hand, if $w\notin L_D$ then $M$ either rejects or never halts on $\langle M\rangle$. In both cases $M'$ will go into an infinite loop on $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \notin HP$, and we are done showing that $w\in L_D$ if and only if $w'\in HP$, and have thus shown that $HP\notin R$.

Further reading: many examples for reductions and proving undecidablility of languages can be found via the reductions tag.

There are some more restriction on the reduction to be valid. The conversion itself must be computable, and well defined for any input.
An input of $HP$ looks like $\langle M,x\rangle$, where $M$ is a TM and $x$ is some string. So here we choose the string $x$ to be an encoding of the machine $M$, which is just some string..

4. Rice's Theorem

"So every time we wish to prove $L$ is undecidable, we need to reduce $L_D$ (or $HP$) to it? Isn't there any shortcut?"

Well, in fact, there is. This is Rice's Theorem.

The theorem says that many languages that have a certain structure, are undecidable. Because all these languages have this certain structure, we can do the reduction once and apply it to any language that admits a similar structure.

The theorem is formally stated in the following way,

  Theorem (Rice).  Given a property $\emptyset \subsetneq S \subsetneq RE$, the following language $L_S$ is undecidable
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$

The set $S$ is a subset of languages in $RE$; we call it a property because it describes a property of the accepted language $L(M)$. All the TMs whose language satisfies this property belong to $L_S$.

For instance, $S$ can be the property that the accepted language $L(M)$ contains exactly two words:

  $$S_2 = \{ L \mid |L| =2 , L \in RE\}.$$
  In this case $L_{S_2}$ is the set of all TMs whose language consists of exactly two words:
  $$L_{S_2} = \{\langle M \rangle \mid L(M) \in S\} = \{\langle M \rangle \mid |L(M)|=2\}.$$

The property can be very simple, but it cannot be all the RE languages, or none of the RE languages. If $S=\emptyset$ or $S=RE$ then the property is said to be trivial, and the induced $L_S$ is computable. An example for a simple $S$ is one the contains only a single language, say $S_{complete}=\{ \Sigma^*\}$. Note that although $S$ contains only a single language, there are infinitely many machines $M$ whose language is $\Sigma^*$, so $L_{S_{compete}}$ is infinite, and undecidable.

The theorem is very powerful to prove undecidability of many languages.

Example.

  The language $L_\emptyset = \{ \langle M \rangle \mid M \text{ never reaches the accepting state} \}$, is undecidable

Proof.
We can write $L_\emptyset$ as $\{ \langle M \rangle \mid L(M)=0 \}$, that is $L_\emptyset=L_S$ for the property $S=\{ L \in RE, |L|=0\}$. This is a non-trivial property (it includes the language $L=\emptyset$, but does not include, for instance, the language $L=\{1, 11, 111,\ldots\}$. Therefore, by Rice's Theorem, $L_\emptyset$ is undecidable.

We now prove the theorem. As mentioned above, we are going to show a reduction from $HP$ to $L_S$ (for any arbitrary non-trivial $S$).

Proof.
Let $S$ be a non-trivial property, $\emptyset \subsetneq S \subsetneq RE$. We show $HP \le L_S$, that is, we reduce $HP$ to $L_S$ so that if we can decide $L_S$ we will be able to decide $HP$ (which we know to be impossible, therefore, $L_S$ cannot be decidable). In the proof below we assume that the empty language is not part of $S$, that is $\emptyset \notin S$. (if the empty language is in $S$, an equivalent proof works on the complement property $\overline S = RE \setminus S$, I'll omit the details). Since $S$ is nontrivial, it includes at least one language; let's call that language $L_0$ and assume $M_0$ is a machine that accepts $L_0$ (such machine exists, since $S$  includes only languages in RE).

Recall that in such a reduction (See section 3 above), we need to show how to convert an input $w$ for $HP$ into an input $w'$ for $L_S$ so that
$$ w\in HP \quad \text{ if and only if }\quad w' \in L_S$$

Let $w=(\langle M \rangle, x)$, we convert it into $w'=\langle M' \rangle$ where the description of the machine $M'$ (on an input $x'$) is the following:

Run $M$ on $x$.
If Step 1 above halts, run $M_0$ on $x'$ and accept/reject accordingly.

We see that this conversion is valid. First note that it is simple to construct the description of $M'$ given $w=(\langle M \rangle, x)$.

If $w\in HP$, then $M$ halts on $x$. In this case, $M'$ proceeds to step 2, and behaves just like $M_0$. Therefore its accepted language is $L(M')=M_0\in S$. Therefore, $w'=\langle M' \rangle \in L_S$.
If $w\notin HP$ then $M$ loops on $x$. This case, $M'$ loops on any input $x'$ — it gets stuck in step 1. The language accepted by $M'$ in this case  is empty, $L(M')=\emptyset \notin S$. Therefore, $w'=\langle M' \rangle \notin L_S$.

4.1 The Extended Rice Theorem

Rice's theorem gives us an easy way to show that a certain language $L$ that satisfies certain properties is undecidable, that is, $L \notin R$. The extended version of Rice's theorem allows us to determine whether the language is  recursively-enumerable or not, that is, determines whether $L \notin RE$, by checking if $L$ satisfies some additional properties.

  Theorem (Rice, extended).  Given a property $S \subseteq RE$, the  language
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$
  is recursively-enumerable ($L_S \in RE$) if and only if all the following three statements jointly hold

  For any two $L_1, L_2 \in RE$, if $L_1 \in S$ and also $L_1 \subseteq L_2$ then also $L_2 \in S$.
  If $L_1\in S$ then there exists a finite subset $L_2 \subseteq L_1$ so that $L_2 \in S$.
  The set of all finite languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L\in S$).

Proof.
This is an "if and only if" theorem, and we should prove both its directions. First, we show that if one of the conditions (1,2,3) does not hold, then $L_S \notin RE$. After that we will show that if all three conditions hold simultaneously, then $L_S \in RE$.

If (1,2) hold, but (3) does not, then $L_S \notin RE$.
Let's assume that $L_S \in RE$, and we'll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M_L$ that accepts only the words in $L$, and now we run the machine of $L_S$ on $M_L$ (remember - we assumed $L_S\in RE$, so there is a machine that accepts $L_S$!). If $L\in S$ then $\langle M_L \rangle \in L_S$ and since $L_S\in RE$, its machine will say yes on the input $\langle M_L \rangle$, and we are done.

If (2,3) hold, but (1) does not, then $L_S \notin RE$.
We assume that $L_S \in RE$ and we'll show that we have a way to decide $HP$, leading to a contradiction.

Because condition (1)  doesn't hold, there is a language $L_1 \in S$ and a superset of it, $L_2 \supseteq L_1$ so that $L_2 \notin S$. Now we are going to repeat the argument used in Section 4 to decide $HP$: given an input $(\langle M \rangle,x)$ for $HP$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ or otherwise, its language is $L_2$. Then, we can decide $HP$: either $M$ halts on $x$, or the RE-machine for $L_S$ accepts $M'$; we can run both in parallel and are guaranteed that at least one will halt.

Let's give the details of constructing $M'$ (on input $x'$):

Do the following in parallel:
1.1 run $M$ on $x$.
1.2 run the machine of $L_1$ on $x'$
If 1.2 halts and accepts - accept.
If 1.1 halts: run the machine of $L_2$ on $x'$.

Why does this work?
If $(\langle M \rangle,x)\notin HP$ then 1.1 never halts, and $M'$ accepts exactly all the inputs that are being accepted at step 1.2, so $L(M')=L_1$.
On the other hand, if $(\langle M \rangle,x)\in HP$ then, at some point step 1.1 halts and $M'$ accepts exactly $L_2$. It may happen that $1.2$ accepts beforehand, but since $L_1 \subseteq L_2$, this doesn't change the language of $M'$ in this case.

If (1,3) hold, but (2) does not, then $L_S \notin RE$.
Again, we will assume $L_S\in RE$ and show that $HP$ becomes decidable, which is a contradiction.

If condition (2) doesn't hold, then for any $L_1\in S$, all its finite subsets $L_2 \subseteq L_1$ satisfy $L_2 \notin S$ (note that $L_1$ must be infinite, since $L_1\subseteq L_1$).
As in the above, in order to decide $HP$ for a given input $(\langle M \rangle,x)$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ and some finite $L_2$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M'$ we constructed. The machine $M'$ (on input $x'$) does:

Runs $M$ on $x$ for $|x'|$ steps.
If $M$ halts during step 1 – reject
Otherwise, run the machine of $L_1$ on $x'$.

It holds that, if $(\langle M \rangle,x)\in HP$, then at some point, say after 1000 steps, $M$ halts on $x$. Therefore, step 1 will halt on (and reject) any input $x'$ of length $>1000$. Therefore, in this case, $L(M')$ is finite. Also note that $L(M') \subseteq L_1$, and in particular, by our assumptions on the invalidity of condition (2), we have that $L(M) \notin S$.

On the other hand, if $(\langle M \rangle,x)\notin HP$, then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L(M)=L_1$ and in particular, $L(M)\in S$.

We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L_S$, that is, $L_S \in RE$. In other words, we need to show a machine $M_S$ so that for any input $\langle M \rangle$ for which $L(M) \in S$, the machine accepts this input, $M_S(\langle M \rangle) \to \textsf{accept}$.

Here is how the machine $M_S$ behaves (on input $\langle M \rangle$):

Let $M_{\text{enum }S}$ be the machine that enumerates all the finite languages in $S$, guaranteed by condition (3).
Run the following in parallel (by dovetailing, see e.g., this and this) for $i=1,2,...$
2.1 Run $M_{\text{enum }S}$ until it outputs the language $L_i$
2.2. Check if $M$ accepts all the words of $L_i$ (run $M$ on these words, again in parallel).
2.3. If for some $i$, $M$ accepts all the words of $L_i$ – accept.

Why does it work?
If $L(M) \in S$ then it has a finite subset $L_j \in S$, and once $M_{\text{enum }S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L(M) \notin S$ it cannot be accepting all the words in $L_i$ for any $i=1,2,...$. Indeed, by condition (1), any $L' \supseteq L_i$ is also in $S$, so if $M$ accepts all the words in $L_i$ for some $i$, then $L(M)\supseteq L_i$ and thus $L(M) \in S$, in contradiction.

Finally, note that the following is a simple (and very useful) corollary of the above:

  Corollary (Rice, extended).  Given a non trivial property $S \subsetneq RE$, so that $\emptyset \in S$, the  language
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$
  is not recursively-enumerable, that is, $L_S \notin RE$.


Algorithm to partially sort list into equal-sized buckets

Assuming you want to create $k$ buckets, to the following.

Obtain elements of rank $\lceil n/k \rceil, 2 \cdot \lceil n/k \rceil \dots, (k-1) \cdot \lceil n/k \rceil$.
Perform multi-way partitioning (cf. Quicksort) with these elements as pivot.

Both steps take time $\Theta(kn)$. All buckets are within $\pm 1$ of the same size.

In the case of duplicate elements, you can "uniquify" them in a $\Theta(n)$ preprocessing run; otherwise bucket sizes might differ more.

Essentially, this is performing only the top-level call of a $k$-way Quicksort with perfect pivots. All variants regarding pivot selection and partitioning apply and will lead to different runtime and bucket size characteristics.


I think the answer is somewhat subtle and lies in Sipser's definition of what it means for an NFA to accept a string.

  Let $N = (Q,\Sigma,\delta,q_0,F)$ be an NFA, and $w$ a string over the alphabet $\Sigma$.
  Then we say that $N$ accepts $w$ if we can write $w$ as $w=y_1y_2\dots y_m$, where each $y_i$ is a member of $\Sigma_\varepsilon$ and ...

Compare this with his definition of what it means for a DFA to accept a string:

  Let $M = (Q,\Sigma,\delta,q_0,F)$ be a DFA and let $w=w_1w_2\dots w_n$ be a string where each $w_i$ is a member of the alphabet $\Sigma$. Then ...

Therefore, by his definitions, his NFA $N_4$ accepts $a$ as it can be written as $a=\varepsilon a$, and $\varepsilon$ and $a$ are both members of $\Sigma_\varepsilon$.


Is there a name for this graph transformation (remove a 'thru' node)

You're contracting the edge $(A,B)$ (or, equivalently, $(B,C)$).

To contract an edge $(x,y)$ is to delete the vertex $y$ and make all its neighbours except $x$ itself be neighbours of $x$ instead.


How to prove that language is decidable?

If you want to prove that a language is decidable, it is sufficient to construct a Turing Machine that accepts if the input is in the language. It MUST reject if the input is not in the language.

Additionally, you are required to argue/prove that the Turing Machine constructed does that. Here's a hint: M must just halt on x, for it to be in L. Consider all possibilities of halting.


Why are most mutex implementations unfair?

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run.

However, there's a little-discussed secret of operating system implementation which you should be aware of, which is that occasionally operating systems run code as the user by hijacking a user thread. For safety reasons, most operating systems that do this only do it while a thread is blocked. When the operating system is done, the thread is re-suspended, and this typically has the effect of moving the thread to the back of the wait queue.

A typical example is a signal handler in Unix, an asynchronous system trap in VMS, or an asynchronous procedure call in Windows NT. These are all essentially the same thing: The operating system needs to notify the user process that some event happened, and this is is handled by running code in user space.

Many operating system services such as asynchronous I/O are often implemented on top of this facility.

Another example is if the process is under the control of a debugger. In that case, the debugging system may execute code as the user task for various reasons.


What's the average number of clauses modern SAT solvers can handle?

You're asking two questions.  I'll answer your first question.

There's no simple answer.  It depends on the structure of the problem.  There are problems with millions of clauses that can be handled by a SAT solver.  There are also problems with only tens of thousands of clauses (perhaps fewer) that can't be handled by SAT solvers.

The number of clauses isn't a great predictor of whether a SAT solver will be able to solve the problem in a reasonable amount of time.

Rick Decker has answered your other question.


Prove that every CFL has at least one infinite equivalence class

The language of palindromes over $\{0,1\}$ is context-free, but every Myhill–Nerode class is a singleton. So your claim is wrong for context-free languages (unless the alphabet is unary). In contrast, regular languages have a finite number of Myhill–Nerode classes, so at least one of them has to be infinite. The same is true for context-free languages over a unary alphabet, since all of them are regular.


When should I move beyond k nearest neighbour

kNN is useful for large data samples

However it's disadvantages are:

Biased by value of k.
Computation Complexity
Memory Limitation
Being a supervised learning lazy algorithm
Easily fooled by irrelevant attributes.
Prediction accuracy can quickly degrade when number of attributes increase.

It's usually only effective if the training data is large, and training is very fast.


Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

In order to apply Case 3, you have to show that $\frac{n^4}{\log n} = \Omega(n^c)$ for some $c > \log_2 10$, as well as the regularity condition (which holds for functions of the form $n^\alpha \log^\beta n$).

You take it from here. Hint: $4 > \log_2 10$.


How to treat ϵ-productions in table-driven predictive parsing?

It will predict $A\rightarrow B$ if the look-ahead is in $FIRST(B)$, it will predict $A\rightarrow c$ if the look-ahead is $c$, it will predict $A\rightarrow\epsilon$ is the look-ahead is in $FOLLOW(A)$.

If the prediction is ambiguous, the construction of the tables should either have failed or used another way to resolve the conflict (for instance you could get a generator which allow ambiguity in the productions and resolve them using precedence -- using associativity to solve conflicts in a predictive parser is harder).


This is known as the $k$-center problem or the planar minmax Euclidean facility location problem.  It is a special case of the minimax facility location problem for the Euclidean metric.

The $k$-center problem is known to be NP-hard.  Wikipedia has references to the literature, where you should be able to find an explicit reduction.

The special case where $k=1$ can be solved in polynomial time.


Removing $\epsilon$ transitions:

Consider the rule $B\to \epsilon$. We want to remove it. To do so, we look for occurrences of $B$ in the grammar, and whenever we see on (e.g. in $S\to aB$), we add the option of choosing $B\to \epsilon$. So the rule $S\to aB$ becomes $S\to a$. Similarly, $A\to B$ becomes $A\to \epsilon$ (which we will have to remove in the next step).

Since $A\to \epsilon$ was introduced when removing $B\to \epsilon$, we now add rules where $A$ appears. For example, the rule $S\to ASA$ becomes $S\to ASA|SA|AS|S$, according to the different options of using $A\to \epsilon$ after $S\to ASA$.

In step 4 - for every rule that yields more than a pair of variables (e.g. in this case $S\to ASA$) we split this into pairs as follows. Introduce a new variable $T$, we add the rules $S\to TA$ and $T\to AS$. Then, applying these forces us to actually have $S\to ASA$.


Understanding reductions for NP-completeness

Assume you can find a $vertex-cover$ of size $k$, in polynomial time.

Actually, this step is not correct. When we show that $A \le_p B$, where $A$ and $B$ are languages (also known as decision problems), we do not assume that either $A$ or $B$ can be solved in polynomial time. What we do is "reduce" problem $A$ to problem $B$: that means that we take an instance of problem A, and return an instance of problem $B$. The part that has to be polynomial time is this "reduce" function.

In other words, it's possible that $A$ and $B$ are both really "hard" -- they can't be done in polynomial time, or maybe they aren't even decidable. But what we show is that the reduction is polynomial time.

So what is this "reduction" that we have to show is polynomial time? You mentioned part of it:

  Building a new graph, in which I say that if a $vertex-cover$ exists of size $k$, then in the original graph, a $clique$ of size $k$ exists?

That's half. You also have to show that if a vertex-cover doesn't exist of size $k$, then in the original graph, a clique of size $k$ doesn't exist.

To summarize: when doing a reduction from $A$ to $B$ ($A \le_p B$), here are the three things you should show:

If the output of the reduction is in $B$, then the input is in $A$. (For example, if a vertex-cover exists in the output, then in the original graph, a clique exists.)
If the output of the reduction is not in $B$, then the input is not in $A$. (For example, if a vertex-cover does not exist in the output, then in the original graph, a clique does not exist).
The whole reduction -- which takes instances of problem $A$ to instances of problem $B$ -- runs in polynomial time.


Selecting k-1 items that divide a sorted array to k equal parts

I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$.

Here is a recursive (divide-and-conquer) algorithm:

Select the median of the array $A$ and use it to partition the array into $A_l$ and $A_r$
Do the same thing above recursively on $A_l$ and $A_r$.

It is easy to see that the depth of the recursive is $O(\lg k)$. Unfolding the recursive tree, you will find that at each depth (i.e., recursion), the non-recursive cost is $O(n)$ for median-selection and partition.

Note that if $k = n$, the algorithm above is the QuickSort algorithm with medians as pivots.


How does topic or tag suggestion algorithms work?

Read about topic modeling in natural language processing.  There are many techniques; e.g., LDA is one simple standard approach.


Is it possible to create a CFG with succesive palindromes?

A reference to $j$ is missing. My guess is that it should read $x_i=x_j^{\mathcal R}$. This means that some pair $x_i$, $x_j$ should be each others reverse, or one string should be a palindrome. This can be done with a CFG.

(after correction)
It does not say that for each $i$ there should be a $j$, it just states that some $i,j$ exist. One pair will do.  If the word "any" would have been used then this would probably change the meaning, although "any" sometimes is ambiguous.


In which reference can I find a definition for the equivalence of DFAs?

You can find a definition in Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman, in the fourth chapter.

Here's a link : HMU, the section begins at page 171 of the pdf

Two DFA are said to be equivalent if they accept the same language, and (an equivalent proposition) if they have the same minimal automaton (which is unique).


Is there any K-means analog for regression, not culstering?

You could use $k$-nearest neighbors regression.  It's not based on $k$-means, but it is based on estimating the price of a new house by averaging $k$ neighbors (in particular, the $k$ most "similar" houses in the training set, for some measure of similarity that you define).  $k$-nearest neighbors is supported in many machine learning toolkits.

See https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm.


Data Analysis: Have 70 data parameters, how many different classes of 3 are possible?

That probably isn't the most effective way to figure out which parameters (features) are most informative.  Instead, I suggest looking at methods for feature selection or feature ranking.  There are many methods out there; it's a well-studied topic.


In a typical cache design an entire block is loaded (in your example 4 words). While it is possible to include separate valid bits for smaller chunks (sometimes called sectors, though Intel uses sector to designate the larger group and line for the smaller unit), making it unnecessary to load the entire block, even in that case typically the entire block is loaded on a miss.


A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle.

In contrast, a result relativizes by definition if it still holds relative to an arbitrary oracle. Hence, to show that a result doesn't relativize, all you have to do is give an oracle with respect to which it fails.

If we're interested in some specific statement, whose truth value we are not sure of, and there are both an oracle relative to which the statement holds and an oracle relative to which the statement doesn't hold, then we can conclude that no relativizing proof can either prove or refute the statement.


Does $f(n) + g(n) = O(g(n) \cdot f(n))$ hold?

I don't get what you do with your choice of $f$ and $g$ but they don't work as a counter-example.

Here is how you see that:

$\qquad f(n) + g(n) = 3n^2 + n \in \Theta(n^2) \subseteq O(n^3) = O(f \cdot g)$.

See our reference question on how to show this.

It is easy to see that the same happens for all pairs of increasing functions:

$\qquad f+g \in \Theta(\max(f,g)) \subseteq O(f \cdot g)$.

So if you want to have a chance at disproving the claim, you'll have to look for decreasing functions -- if your definition of Landau symbols admits such.


Why do programming languages use call-by-value over call-by-name?

There's a couple of factors which come into place. There can be performance costs to call-by-name, as well as difficulty with understandability in the presence of effects.
First of all, call-by-name can use exponentially more time than call-by-value, since it may have to evaluate an expression multiple times. Imagine calling f(x) = x + x when x takes a while to compute. In true call-by-name, the entire expression for x needs to be evaluated twice inside the body of f.
So in practice, instead of call-by-name, we likely would prefer call-by-need. We can instead cache the result of evaluating x, so that we don't have to compute it multiple times. This is what the programming language Haskell does (preceded by Miranda, Lazy ML). This solves the time complexity problem (as you may have intuited above, the time complexity is no worse than call-by-value), but it can also use much more space. This is because it may need large closures in order to delay evaluation. A machine integer uses a finite amount of space, but a Haskell Int could use arbitrarily large amounts, by accumulating a closure of computation that needs to be run. In the Glasgow Haskell Compiler, the garbage collector has special rules to specifically find and eliminate certain kinds of "space leaks" where we use excessive space via closures.
Even putting the theoretical aside, there are practical difficulties for implementing a call-by-name or call-by-need language on a traditional machine. Many programmers are used to using side effects in their program, such as input and output, and having their expressions run sequentially. In a call-by-name programming language, this is no longer the case, effects could be latent anywhere within an unevaluated expression, and only take effect when that data is examined. It took many years for the discovery that mathematical monads could be used as a sequencing interface. Prior methods for controlling input/output were difficult to use.
Call-by-value languages tend to also be able to be performant much more easily than call-by-name/call-by-need. Haskell has taken extensive optimization effort to run quickly, largely by being able to carefully introduce strictness to eliminate overhead of laziness. With laziness, a value of any type could be a closure: a complex allocated object and a pointer to remote code to run. This can require more allocations and more indirection to manipulate than machine integers and simple objects.
So, while we can't answer definitively why such languages aren't more popular, we can see that there has been plenty of complexity and research necessary to tackle, and so languages which used call-by-value have long had a head start.


Applicative order: The leftmost, innermost redex is always reduced first.

Normal order: The leftmost, outermost redex is always reduced first.

Applicative order: $(λx.((λy.(∗2y))(+xy)))y$, the leftmost innermost redex is $(λy.(∗2y))(+xy)$. It is reduced first. Then we get $(λx.(∗2(+xy)))y$. Here $y$ is a free variable, renaming is not needed. Then the result is $(∗2(+yy))$.

Normal order:  $(λx.((λy.(∗2y))(+xy)))y \rightarrow ((λy.(∗2y))(+yy)) \rightarrow *2(+yy)$.
Applicative order: $$\begin{align*}(λx.λy.(xy))(λz.(zy)) &\rightarrow_\alpha (λx.λw.(xw))(λz.(zy))\\ &\rightarrow_{\phantom{\alpha}} λw.((λz.(zy))w) \\ &\rightarrow_{\phantom{\alpha}} λw.wy\end{align*}$$
The first $y$ is bound, the second $y$ is free. When $x$ is substituted by $(λz.(zy))$, name capture occurs, so the bound y is renamed by $w$.

Normal order reduction is same as the applicative order.


Is there a possibility to develop an analog-based ASIC for neural
  networks?

This had been already implemented a long time ago.

I guess, no one ever seriously supposes that this is impossible. There're many implementations in papers since 70th. They're still not of industry-standard quality, and with some limitations. However, they're real prototypes among them.

  error-proneness of analog circuits shouldn't be a problem

Unfortunately, it's and it's just one of a bunch of issues.

A general view of this field. Analog ASICs is one of the existed hardware bases for implementing neural networks along with digital ASICs, FPGAs, custom on-chip implementations, massive-parallel computers, general-purpose CPUs and GPUs. Moreover, it's not the most popular approach, currently, because of its limitations in precision and storing data overhead. Also, the analog computations aren't the mainstream, so, there's a lack of development and specialists. Analog computational elements are a kind of different world with specific problems for engineers. Hence, their cost-efficient parameters are far behind even common general purpose CPUs and they are in a narrow use.

However, the analog ASICs have positive sides - yes, on a hardware components level, they are immensely close to the neural networks (biological) which have deeper parallelism than mainstream implementations.

A lot of references for further reading can be found here: Omondi, Amos R., eds. FPGA implementations of neural networks. Vol. 365., Springer, 2006.


How binary search works in real world scenario?

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.

At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.

You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.

Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.

Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.

I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?

Hope this helps!

EDIT: Edited to say "Prof. Filmus..." as that is more formal.


Does the Y combinator contradict the Curry-Howard correspondence?

The original Curry-Howard correspondence is an isomorphism between intuitionistic propositional logic and the simply-typed lambda calculus.

There are, of course, other Curry-Howard-like isomorphisms; Phil Wadler famously pointed out that the double-barrelled name "Curry-Howard" predicts other double-barrelled names like "Hindley-Milner" and "Girard-Reynolds". It would be funny if "Martin-Löf" was one of them, but it isn't. But I digress.

The Y combinator does not contradict this, for one key reason: it is not expressible in the simply-typed lambda calculus.

In fact, that was the whole point. Haskell Curry discovered the fixpoint combinator in the untyped lambda calculus, and used it to prove that the untyped lambda calculus is not a sound deduction system.

Interestingly, the type of Y corresponds to a logical paradox which isn't as well-known as it should be, called Curry's paradox. Consider this sentence:

  If this sentence is true, then Santa Claus exists.

Suppose the sentence were true. Then, clearly, Santa Claus would exist. But this is precisely what the sentence says, so the sentence is true. Therefore, Santa Claus exists. QED


Calculate the number of combinations of a sequence of numbers in a particular order

Can you solve the problem for $n=1$?
Can you deduce the answer for $k+1$, if you know the answer for $k$?
(hint: you need an $n\times 10$ table, the $k$-th row devoted for problem size $k$, the columns for partial answers...)

ps: I think that the answer is $9+0+1+1+2+1+3+1+3+2=23$ for n=2 (and 125 for $n=3$)

0: 10,...,90
1: -
2: 22
3: 33
4: 24,44
5: 55
6: 26,36,66
7: 77
8: 28,48,88
9: 39,99


DFA for exactly two of a and one or more of b

Since it's for class, I won't actually build the DFA for you, but I will give you a way to look at it that'll help.

As far as $b$s go, you really only care about whether or not you've seen a $b$ so far in the string.
As for $a$s, you care about whether you've seen 0, 1, 2, or more.

Each combination of scenarios for both letters (like "seen none of either" or "seen one of each" or "seen one $a$ and no $b$s") changes in its own way depending on whether you read another $a$ or $b$. How might you express that in a DFA?


What is the point of selection step in a genetic algorithm?

I think the confusion can be isolated in this sentence: "From what I understood till now we [...] [choose] $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration?"

Selection plays the role of the hand of death. Unselected organisms correspond to those that died without reproducing. Far from being left "untouched for the next iteration", unselected organisms are discarded. Now, to maintain the population size, we need to create new organisms to replace the discarded ones. This is done by applying mutation and cross-over to the chromosomes of the selected organisms. The next generation will contain a mix of the selected organisms that are left untouched, and mutants of those selected organisms. Biologically, the idea is that the next generation is the organisms that survived and their children. As an optimization technique, the idea is to cull out bad solutions and consider only variations of the "best" current solutions.


Calculating the number of multiplications necessary to evaluate a polynomial

I am not sure what the slide was intended for, so I just gave a
straight answer to your question in a comment, viz that the slide
really intended 3 multiplications for $4x^3=4\times x\times x\times
x$, and 4 additions to add the five terms.

Now of course, there are better ways to do that. Various powers of $x$
can be obtained in multiplying other powers of $x$ together using the
rule $x^m\times x^n=x^{m+n}$.

The method of repeated squaring presente by David Richerby in his
answer is a systematic way to get high powers of $x$ as fast as
possible. However, when you need a few specific powers, you can try to
adapt it to compute just these powers with as few multiplications as
possible.

So you can compute, for example:

$\begin{align}
x^2&=x\times x \\
x^3&=x^2\times x \\
x^6&=x^3\times x^3 \\
x^{12}&=x^6\times x^6 \\
x^{24}&=x^{12}\times x^{12} \\
x^{25}&=x^{24}\times x \\
x^{49}&=x^{24}\times x^{25} \\
x^{50}&=x^{25}\times x^{25} \\
x^{99}&=x^{49}\times x^{50}
\end{align}$

Hence you get all needed powers of $x$ with only 9 multiplications of
powers of $x$, to which you have to add 4 multiplications for the
coefficients, which makes a total of 13 multiplications. The number of
additions remains at 4.

But you can do a bit better using a technique that is most
efficient when all powers of $x$ are being used, rather than having a sparse
polynomial. The technique, known as Horner's method, consists in
factorizing some powers of the variable, when it helps the
computation.

In the case of your sparse polynomial, you may notice that
$7x^{25}+6x^{99}=x^{25}(7+6x^{74})$. Hence rather than computing
$x^{50}$ and $x^{99}$, you compute only

$x^{74}=x^{49}\times x^{25}$ and then $x^{25}(7+6x^{74})$.

This saves one multiplication, because both $7x^{25}+6x^{99}$ and
$x^{25}(7+6x^{74})$ take exactly 2 multiplications and one addition,
assuming the powers of $x$ are already computed, but computing the
needed powers takes one less multiplication.

So you are down to a total of 12 multiplications and 4 additions.

I do not see any way to do better on this example, but I have no
systematic algorithm to check that. However, I am rather confident
that someone must have worked on it.

BTW, what was the theme of the set of slides?


Your solution is almost there: I do not think it is necessary to construct a machine that always halts. The problem running $M$ on input $w$ does not always halt either.

Running $M_1$ and $M_2$ over all input strings $x$ is tricky: indeed,if one of the machines does not halt on a particular input, then the new machine $M$ will not consider the next input. The solution for that is usually called dove tiling, where more and more inputs are simulated step by step.

This can be avoided (or better: hidden) by assuming non-deterministic machines. $M$ guesses an input $x$ and simulates both $M_1$ and $M_2$ on that input $x$. Now $M$ halts (on the empty input) whenever the languages of $M_1$ and $M_2$ intersect.


Algorithm to test whether a binary tree is a search tree and count complete branches

As others have already indicated in comments, you really have two unrelated functions here: testing whether the tree is a search tree, and counting the complete branches. Unless the assignment specifically calls for it, I would write two separate functions.

Let's see abount counting the complete branches first. That means counting the nodes that have both a left child and a right child. Then you need to increment the counter (count = count + 1) when both T.left and T.right are non-null (not T.left.data and T.right.data: the data doesn't matter for this task).

if (T.left and T.right) {
    count = count + 1

Furthermore, you need to explore the left subtree even if the right subtree is empty, and you need to explore the right subtree even if the left subtree is empty. So watch where you put the recursive calls.

To test whether the tree is a search tree, you need to inspect the data values. You've already got something close to the right comparison; not quite right. Write a few example trees with various shapes (not very big, 2 to 5 nodes) and run your algorithm on them to see what happens.

You still need to find some place to put the result of the validity check. Again, watch where you put the recursive calls (if you only do this part, there are several solutions, but at this stage don't worry if you only see one).

Finally, once you've managed to write both functions separately, and you've tested them on a few examples, put them together carefully (if required by the assignment).


Construct a Deterministic Pushdown Automaton for unequal number of elements

The answer in that image is actually not a deterministic PDA, because in the definition of DPDA, the transition functions need to satisfy the following rules: 1. $\delta(q, a, b)$ contains at most one element; 2. if $\delta(q,\lambda,b)$ is not empty, then $\delta(q,c,b)$ must be empty for every $c\in\Sigma$. These two rules prevent multiple paths for same input symbol and stack symbol (to make it deterministic). From the PDA in the question, there are some transitions like $\delta(q_0,a,b)$ and $\delta(q_0,\lambda,b)$, which does not satisfy the second rule.
There is one way to get the DPDA for this language $L=\{w: n_a(w)\neq n_b(w)\}$, which is to get the DPDA of the complement of $L$ first, and that is $\bar{L}=\{w: n_a(w)=n_b(w)\}$. Then you can simply convert the final states to non-final states and vice versa. The DPDA for $\bar{L}$ is very similar to the one in the question, except that the transitions from $q_0$ to $q_1$ should be changed to $ \delta(q_0,\lambda,＄)=(q_1,＄). $ After that, changing $q_0$ to a final state and $q_1$ to a non-final state and you will get the correct answer. This method is based on the closure property for DCFL that DCFL is closed under complementation.


Efficiently computing the smallest integer with n divisors

Here's a solution, based on my comments above.  I make no claims this is optimal.

The idea is to consider $T(n,m)$, which we defines as "the smallest positive integer with exactly $n$ divisors and $m$ distinct prime factors". We make the easy observations:

\begin{align}
T(n, 1) &= 2^{n-1}\\
T(2^m, m) &= p_1p_2\cdots p_m
\end{align}

And we also have the recurrence:

\begin{equation}
T(n,m) = \min_{d|n} [T\left(\frac{n}{d}, m-1\right)\cdot p_m^{d-1}]
\end{equation}

Finally, the quantity you're looking for is
\begin{equation}
\min_{1\le i\le\lceil\log(n)\rceil} T(n, i)
\end{equation}

To that end, here is some Python code, which agrees with all the numbers you gave above.  Note that it works with the logarithms to keep the numbers smaller: so the actual integer you seek is round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r)
                                       for r in range(1, len(lst)+1))


What is a good example of an NL-complete context free language?

In other words, you are asked to find an $\rm NL$-complete language $A$ and a context-free language $B$ such that $A \equiv_{\rm{L}} B$. We choose $A = \it{PATH}$ and $\{{\tt{0}, \tt{1}， \tt{\#}}\}^* \supseteq  B = f(A)$, in which $f: A \to B$ is defined as follows.
    $$
\newcommand{\Bra}[1]{\langle #1 \rangle}
  f(\Bra{G, s, t}) = \Bra{s}^{\mathcal{R}}({\tt{\#}} \Bra{e_1} \Bra{e_2} \cdots \Bra{e_m} {\tt{\#}} )^n\Bra{t},
 $$
    where $G = (V, E)$, $|V| = n$, $E = \{e_1, \dots, e_m\}$, $\Bra{e_i} = {\tt{\#}}\Bra{u_i}{\tt{\#}}\Bra{v_i}^{\mathcal{R}{}}{\tt{\#}}$ if $e_i = (u_i, v_i)$.


Negation of the semantics of the Until operator in LTL

First, note that you did not really get the "first part the the expression correct". The first formula is, roughly, of the form

$$
\forall i, (p(i) \lor q(i))
$$
while the second one is of the form
$$
r \lor (\forall k, p(k))
$$
Note the different bracketing.

That being said, you have two definitions for the semantics of the release operator, and you want to prove them equivalent. So far, you tried to manipulate those formulae according to standard logical rules (a correct approach), but failed to do so. Indeed, as far as I can see, that approach can not succeed. The nice news is that you do not need to use that approach: in order to prove that definition $A$ and $B$ are equivalent, you can also write two distinct proofs, one for $A \implies B$ and one for $B \implies A$. In writing such proofs, you can leverage all the known results from mathematics, not just those allowing formula manipulation.

In your specific case, you will need to use the well-ordering property of natural numbers, stating that any non-empty set of naturals must have a least element. Let me sketch a part of the proof.

Assume your first definition, and let's prove the second one.
We consider two cases.

If $\pi[k] \models \psi$ for all $k$, then the second definition is trivially true.
Otherwise, $\pi[k] \not\models \psi$ for some $k$. This means that the set of natural numbers $\{k|\pi[k] \not\models \psi\}$ is not empty, hence has a least element -- let $m$ be that element. This means that $m$ satisfies $\pi[m] \not\models \psi$, and that (minimality) $\forall n<m, \pi[n] \models \psi$. Now, using the hypothesis, we can obtain that $\exists j<m, \pi[j]\models\phi$. From this and minimality we obtain the thesis.

Note that you still need to prove the other direction.


How much data could I store on a Rubik's Cube?

If you consider the cube as living in a physical space, then you can get an extra factor of 24 from its orientation: assume it's sitting on a table and note the uppermost face (six options) and the face that's facing north (four more options). That gives you $\lfloor \log_2 (24\times 43\ 252\,...)\rfloor = 69\,\text{bits}$, and you could get even more by considering more fine-grained notions of orientation, at the risk of losing information by somebody jostling the cube.


NP-completeness of the exact distance problem

Yes.  Keep in mind exactly what the inputs to each problem are.


Formula for returning the size of a circular array

I've not checked if your formula is correct but the point appears to be that $x\%y$ can only give answers in the range $\{0, \dots, y-1\}$, whereas you're performing a calculation where the answer could be anything in the range $\{0, \dots, y\}$, including $y$. This means that any formula of the form blah%capacity is necessarily wrong.


The image of a recursive language under a computable function

Inspired by this question, I have come up with the following.

Assume that $\langle\cdot\rangle$ is an encoding for TM's, for which the encoding of one Turing machine is never a prefix of the encoding of another.

Let $f$ be defined as the identity on an input which does not contain a TM enconding as a prefix. If the input contains such a prefix, $f$ returns this prefix.

$f$ is computable and it is well defined due to the encoding property.

Let $L=\left\{ \langle M\rangle n \mid \text{$M$ halts on the empty input after $n$ steps} \right\}$.

Then $L$ is recursive but $f(L)=\left\{ \langle M\rangle \mid \text{ $M$ halts on the blank tape} \right\}$ which is not recursive.


Divide numbers into fewest groups with each group's sum bounded

As comments suggested it is called the Bin Packing Problem.


Can the decision version of an optimization problem in NP, be in P?

Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of decision problems, and NP-hardness is a property of decision problems. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the corresponding decision problem is in NP or is NP-hard.


Is the class NP closed under complement?

First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.

If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. Notice that $\sf NP = coNP$ implies that the polynomial hierarchy collapses to the first level. However this would not imply that $\sf P= NP$.