The Repeat loop is not strictly necessary.  The algorithm would still be correct without it.  In fact, the Repeat loop actually has no effect, though proving this takes a little bit of work.

If the graph $G$ has no $K$-clique, then this procedure correctly halts.  So assume the graph $G$ has at least one $K$-clique.  The interesting case is where it has multiple $K$-cliques.

Associate each $K$-clique with a vector $(x_1,x_2,\dots,x_K)$ representing the vertices of the clique, in increasing order.  Now order these cliques by lexicographic order on the vectors.  Let's focus on the $K$-clique whose corresponding vector is lexicographically largest; call this the "golden" $K$-clique.  It is possible to prove that For loop removes everything but the "golden" $K$-clique: when the For loop terminates, all that remains is a subgraph containing exactly $K$ vertices, namely, the golden $K$-clique.  Therefore, the Repeat loop does nothing.

In other words, you can remove the Repeat loop, and this procedure will always produce the same output.  (In particular, you were worired that the Repeat loop might remove a vertex from an actual clique -- but the above reasoning shows that this can never happen.)

So, the Repeat loop is unnecessary.  Why is it there?  Maybe to make the proof of correctness for this algorithm a bit easier.  But if you find the algorithm easier to understand if you omit the Repeat loop, go ahead and pretend it's been removed -- that will work, too.


How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$?

One possibility to get conditional hardness is to give a (fine-grained) reduction from a problem that is known to be hard in some sense. The result will then something along the lines of "if problem X admits an algorithm running in time $O(n^{1/2-\epsilon})$, then problem Y can be solved within some specific time bound". The "specific time bound" should be something we don't know how or believe that can be achieved.

The survey of Williams [1] you refer to contains several examples. As you can see in Figure 1, there are several problems in computational geometry, graph theory, and logic that could be or have been reduced from. Now, for some problems, there is theoretical evidence and belief in the community that the conjectures indeed hold (like ETH). Other ones are less often believed like SETH.

It is an open problem to draw more connections between these problems (see Section 2.6 in [1]), i.e., to find more evidence for hardness other than "here's an isolated problem nobody has been able to find a faster algorithm for decades". For more in this direction, see e.g., this question on CSTheory.

[1] Virginia V. Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. IPEC 2015 invited talk.


Given a language L what can we say about the decidability of whether this language is regular or not?

As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines.

So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.

Unfortunately, even for context-free grammars it is undecidable whether their language is regular.

Bar-Hillel, Perles, Shamir.  On formal properties of
simple phrase structure grammars. (1961)
doi 10.1524/stuf.1961.14.14.143


What is the name of this sorting algorithm?

What is the name of that sort?

There is no existing name for it, I would believe.

If I had to name it, its name could be "caching and counting insertion sort". Here are the considerations.

It is a kind of insertion sort since it maintains a single ordered linked-list all the way by inserting elements one by one into that ordered linked-list.
"Caching" and "counting" are the basic two features of that insertion sort. Caching tries to make it faster to find the right location to insert by taking advantage of possible locality coherence. Counting is a common strategy to deal with the situation when duplicates happen often. Both caching and counting are standard terms that are easily recognizable.
It happens that both words start with "c", which is helpful for reading and memorizing.
"caching" is put before "counting" since "caching" is a more distinguishing feature of the algorithm. It is better to make the name less similar to the existing counting sort.
This is not a very cohesive name, since there is no strong coupling between the two techniques used in that sort. The technique of caching could be applied to almost all kinds of sort. The technique of counting could be applied to almost all kinds of sort as well independently. The only meaningful connection between them is that if this caching technique improves the speed a lot, it is more likely that there are lots of duplicates, then the counting technique might be even more useful.
"Caching and counting insertion sort" or "caching-counting insertion sort" is, in fact, more like a description instead of a proper name.

I would not recommend a name like "curve sort" unless you can show me some direct or obvious connection between "curve" and that sort.

Should we name that sort?

Is that sort distinctive and cohesive enough to deserve a distinctive short name?

The combination of caching and counting might be distinctive enough. However, those two optimizations are not cohesive. In fact, it is reasonable to see the two as independent. Caching deals with locality while counting deals with duplicates. Each one of them can be removed or applied without affecting the other's usefulness or functionality. It is preferable to study either one of them separately. It is not preferred to give a name to a simple combination of two abstract features.

As said by Bulat, there could be dozens of variations we can make to each of the algorithms listed on this page or this Wikipedia article. In particular, the counting technique can be applied to most if not all of them. In most cases the variations don't get individual names. To be clear, not every variation get individual names that have become established or standardized. Of course, if you write an article to expound that sort, you can certainly give it a fancy cool name such as "curve sort" or "Rodionsort".

What else could be done?

In fact, it looks like more interesting to name a simplified version of your algorithm that does not use the counting technique "caching insertion sort" or simply "caching sort", since caching makes sense mostly with insertion sort.

There have been many discussions/articles about whether or how much certain sorting algorithms are cache-friendly. However, I have not seen a simple sorting algorithm that takes an explicit separate step in order to take advantage of the "smoothness" of the data, although it might be a simple step. The most similar step I have seen is the checking whether the given data have been sorted before or during sorting. Some complex sorting algorithms such as Timsort search for ascending or descending subarrays during sorting, which also use many other techniques. A simple algorithm called "caching sort" sounds attractive and pedagogical to me.

A slight generalization could be caching two elements instead of just one element. When a new element comes along, we could start searching the position for the new element from the cached element that is nearer to the new element. Then the sorting would be efficient for data stream that comes from two "smooth" sources that are mixed irregularly.

A further generalization could be caching even more elements with more involved caching policy. Or even layers of caches. Let me stop my brainstorming here.


Regular Languages and Separating Suffixes

For $\sigma \in \Sigma$, let $f_\sigma$ be the indicator function of $L_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma_1 \ldots \sigma_n$ then
$$
f(w) = f_{\sigma_1}(\sigma_2 \ldots \sigma_n) \oplus f_{\sigma_2}(\sigma_3 \ldots \sigma_n) \oplus \cdots \oplus f_{\sigma_n}(\epsilon) \oplus b.
$$
Imagine a finite automaton reading the word in reverse (we know that regular languages are closed under reversal). The finite automaton maintains an accumulator $a$ initialized by $b$, and states of DFAs for the reverses of $L_{\epsilon,\sigma}$ for all $\sigma \in \Sigma$. When reading $\sigma_i$, it updates $a$ by $a \oplus f_{\sigma_i}(\sigma_{i+1} \ldots \sigma_n)$, and then updates the states of all DFAs. Finally, it accepts if $a = 1$.


"Which complexity represents a majority of algorithms?"

My answer would be that there is no running time that represents the majority of algorithms. Some common algorithms (for example, BFS and DFS) run in linear time; some run in loglinear time (for example, sorting); dynamic programming algorithms run in superlinear polynomial time (for example, the standard algorithm for edit distance runs in quadratic time); algorithms involving matrix multiplication run (practically) in cubic time, and theoretically faster; SAT solvers have worst case exponential running time; and some algorithms involved in verification have even faster growing worst case running time, or are not guaranteed to terminate at all.


Equality is a syntactic notion, equivalence is a semantic notion. Two expressions are equal if they are the same expression — in other words, an expression is only equal to itself. Two logical expressions are equivalent if they have the same truth value in every interpretation.

Two equal expressions are always equivalent, but the converse doesn't hold. For example, $A \equiv \lnot\lnot A$ but $A \neq \lnot\lnot A$.


Strictly speaking, this is a category confusion: it's an apples-vs-pears comparison.  You can't compare SAT to #SAT; SAT is a decision problem (determine whether a formula $\varphi$ has a satisfying instance), #SAT is a counting problem (count the number of satisfying assignments to $\varphi$).  They have a different API: they both take a formula $\varphi$ as input, but SAT outputs either "satisfiable" or "not satisfiable", while #SAT outputs a number.  They're not the same, and you can't encode a #SAT instance as a SAT instance.

The same is true for counting the number of values of $x$ that satisfy a formula $\varphi(x)$, where $\varphi$ contains nested quantifiers (e.g., $\varphi(x) = \exists y . \forall z . \psi(x,y,z)$ or something).  It's a category error: one is a decision problem, the other is a counting problem.

However, you might be interested in the following paper:

Richard E. Ladner.  Polynomial Space Counting Problems.  SIAM Journal of Computing, vol 18 no 6, pp.1087--1097, December 1989.

See, for instance, the discussion of $\natural$QBF, $\natural$PSPACE, and FPSPACE(poly).

Definitions:

$\natural$QBF is the following problem: given a QBF instance like $\varphi(x,y,z) = \exists x \forall y \exists z \psi(x,y,z)$, count the number of values $x$ such that $\forall y \exists z \psi(x,y,z)$ is true (except that is for an arbitrary number of quantifiers, not limited to just 3).
A function $f:\{0,1\}^* \to \mathbb{N}$ is in $\natural$PSPACE if there's a polynomial-space nondeterministic Turing machine $x$ such that $f(x)$ counts the number of accepting computations of $M$ on input $x$, and $M$ makes only a polynomial number of nondeterministic choices.
A function $f:\{0,1\}^* \to \mathbb{N}$ is in FPSPACE(poly) if $f(x)$ is bounded by a polynomial in the length of $x$ and there's a deterministic polynomial-space algorithm (Turing machine) that computes $f$.

The paper proves that $\natural$PSPACE = FPSPACE(poly) and that $\natural$QBF is complete for $\natural$PSPACE and that there is a polynomial-space algorithm for computing $\natural$QBF.

We could consider the following problem:

BIT_OF_COUNT:
Input: an index $i$ and a QBF instance $\varphi$
Desired output: the $i$th bit of the solution to this QBF instance.

This is one way to build a decision problem associated with a $\natural$QBF instance.

By the above remarks, BIT_OF_COUNT is in FPSPACE(poly) (since $\natural$QBF is).  Since its output is in 0 or 1, that means BIT_OF_COUNT is actually in PSPACE.  Since QBF is complete for PSPACE, that it must be possible to reduce BIT_OF_COUNT to QBF, i.e., to translate an instance for BIT_OF_COUNT into an instance for QBF, by chaining all the reductions.

It sounds like this might be what you want.  So, if you study that paper and chain all the reductions together, you might get what you want.  It looks a bit intimidating on first glance, but perhaps if you understand the meat of the reductions you'll be able to simplify somehow.  The key trick in the paper seems to be the one used on pages 1091--1092, using ann algorithm to compute the product or sum of two $b$-bit numbers in $O(\lg b)$ space as a subroutine.

I hope someone will be able to give you a better answer.


CTL vs LTL - when a formula satisfy a model

For what it concerns LTL, your understanding is almost correct except that there may be more than one initial states in a transition system.

An LTL formula $\varphi$ holds in state $s$ of a transition system $TS$ if all paths starting in $s$ satisfy $\varphi$.

  The transition system $TS$ satisfies an LTL formula $\varphi$ if if all initial paths of $TS$, paths starting in an initial state $s_0 \in I$, satisfy $\varphi$.

For what it concerns CTL, we have

  The transition system $TS$ satisfies an CTL formula $\Phi$ if and only if $\Phi$ holds in all initial states of $TS$.

Note that, similar to the case in LTL, we are only concerned with the initial states of $TS$ in the semantics of CTL. However, this does not imply that you don't need to check other states of $TS$ against a specific CTL formula $\Phi$. This is both $\Phi$-dependent and checking algorithm-dependent.

For example, the well-known checking algorithm (see the lecture note) is a global model-checking procedure, meaning that it does check for any state $s$ in $TS$ whether $s \models \Phi$, and not just for the initial states. This is because the algorithm is computing fixed points recursively: The result of $s \models \Phi$ may rely on each of $s' \models \Phi$, where $s' \in \text{Post}(s)$ is a direct successor of $s$ in $TS$.

Furthermore, it also checks for any state $s$ whether $s \models \Phi_{sub}$, where $\Phi_{sub}$ is any subformula of $\Phi$, by backward search.


How to show that f(x) is primitive recursive?

Goldbach's conjecture is either true or false. Do a case analysis on the two possibilities. In one case, $f(x)=x$, which is primitive recursive. In the other case, $f(x)=0$, which is also primitive recursive. Therefore $f$ is primitive recursive.


Is it necessary for NP problems to be decision problems?

Indeed problems in NP are decision problems which output 0 or 1 for a given input string. Prof Roughgarden is referring to the fact that problems in NP have short polynomially bounded proof (in the input length) of membership that can be verified efficiently (by polynomial time algorithm).


Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$

There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.

Let's start with function over the natural numbers, as they can be continuously completed to the reals.

A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to alternate between their orders of magnitude. For example, we could define

$f(n)=\begin{cases}
n & n \text{ is odd}\\
n^2 & n \text{ is even}\\
\end{cases}$

Then, we could have $g$ behave the opposite on the odds and evens. However, this doesn't work for you, because these functions are not monotonically increasing.

However, the choice of $n,n^2$ was somewhat arbitrary, and we could simply increase the magnitudes so as to have monotonicity. This way, we may come up with:

$f(n)=\begin{cases}
n^{2n} & n \text{ is odd}\\
n^{2n-1} & n \text{ is even}\\
\end{cases}$, and
$g(n)=\begin{cases}
n^{2n-1} & n \text{ is odd}\\
n^{2n} & n \text{ is even}\\
\end{cases}$

Clearly these are monotone functions. Also, $f(n)\neq O(g(n))$, since on the odd integers, $f$ behaves like $n^{2n}$ while $g$ behaves like $n^{2n-1}=n^{2n}/n=o(n^{2n})$, and vice-versa  on the evens.

Now all you need is to complete them to the reals (e.g. by adding linear parts between the integers, but this is really beside the point).

Also, now that you have this idea, you could use the trigonometric functions in order to construct ``closed formulas'' for such functions, since $\sin$ and $\cos$ are oscillating, and peak on alternating points.


Is O(n log n) exponential speedup over O(n^2)?

$O(n \log n)$ is a polynomial speedup over $O(n^2)$, in particular almost a quadratic speedup. $O(n \log n)$ is big-O of $O(n^k$) for all $k > 1$. Its runtime is therefore between linear and any powerfunction whose exponent is strictly greater than 1.

Let $f(n)=n \log n$. Raise it to a power of some value slightly less than 2 to approximate the original runtime. We conclude $f(n) \approx n^{2-\varepsilon} (\log n)^{2-\varepsilon}$ and in $O(n^2)$. If we square $f(n)$, we have $n^2 (\log n)^2$, slightly less efficient than the original $n^2$, hence it is basically a quadratic speedup.

Instead, $O(\log n^2) = O(\log n)$ is an exponential speedup over $O(n^2)$. If $g(n) = 2\log(n)$, then $e^{g(n)} = n^2$.


You can also prove this using automata theory. For a set $S = \{s_1,\ldots,s_k\}$ of strings over $\Sigma$, consider the following language over $\Sigma \cup \{1,\ldots,k\}$:
$$ L_S = (1s_1+2s_2+\cdots+ks_k)^+. $$
This language is accepted by a DFA of size roughly $\|S\| := |s_1|+\cdots+|s_k|$. The exact size depends on the model of DFA - in our case it makes sense to ask for at most one transition out of each state with a given label (rather than exactly one transition, as is usually the case).

Now we want to do the same, but for two sets of strings $A = \{a_1,\ldots,a_m\}$, $B = \{b_1,\ldots,b_n\}$. To this end, we consider languages $L_A,L_B$ which are defined as before, but with two differences:

$1,\ldots,k$ are replaced with $A_1,\ldots,A_m$ for $L_A$ and $B_1,\ldots,B_n$ for $L_B$.
The symbols $A_1,\ldots,A_m$ are ignored in $L_B$, and the symbols $B_1,\ldots,B_n$ are ignored in $L_A$.

As an example, suppose that $A = \{a,ba\}$ and that $B = \{ab,a\}$. Then the following word will be in our language: $A_1B_1aA_2bB_2a$.

As before, we can construct DFAs for $L_A,L_B$ having roughly $\|A\|,\|B|$ states, respectively. Using the product construction, we get a DFA of size roughly $\|A\|\cdot\|B\|$ for the intersection. It is well-known (and can be proved using the pigeonhole principle) that if a DFA having $N$ states accepts any word, then it accepts some word of size less than $N$. This implies your claim.

In terms of lower bounds, it is easy to refute your conjecture that $2nL$ is enough. Consider $A = \{ 0^L \}$ and $B = \{ 0^{L-1} \}$. It is not hard to check that the minimal solution has length $L(L-1) \approx L^2$.

It's less clear what is the correct dependence on $n$.


How to calculate or estimate how long it takes to solve a recurrence relation?

There are at least three questions here:

How does one solve a recurrence relation on paper?
How does one efficiently calculate a sequence given by a recurrence relation, say using memoization?
Given a recurrence relation, can one predict the running time of the best method for computing it?

Let me answer them one by one. For the first question, this is a particular instance of the classical question, how to solve problems. Consider the (finite!) recurrence relation given by
$$
\gamma_0 = 1, \quad \gamma_{m+1} = E, \quad \ell\gamma_{\ell+1} = (2\ell-m+c-1)\gamma_\ell + (m-\ell+1)\gamma_{\ell-1} (1 \leq \ell \leq m).
$$
(The sequence is $\gamma_0,\ldots,\gamma_{m+1}$, and $E,c$ are parameters.)
What is the solution of this recurrence? If you're interested, have a look at the top of page 7 in this paper, which unfortunately doesn't explain how the authors found the explicit formula; Mathematica manages to solve this recurrence somehow. For some general methods useful for solving recurrence relations, consult our reference question.

For the second question, we can consider a very general class of recurrence relations which produce a sequence $(\gamma_i)_{i \in \mathbb{N}}$ by giving each $\gamma_i$ in terms of values $\gamma_j$ for $j < i$. Such recurrences can be efficiently computed using memoization. The time required to compute $\gamma_n$ is upper-bounded by $n$ multiplied the time it takes to calculate the defining formula of $\gamma_i$. This bound can be tricky to evaluate, since the time needed to carry arithmetic operations depends on the size of the operands, which could grow rather fast depending on the recurrence (consider for example $\gamma_0 = 1$, $\gamma_n = n\gamma_{n-1}$).

For the third question, it is easy to artificially reduce the halting problem to my statement of the problem, so in general it is hard to predict the best running time. But one can probably predict (or at least upper-bound) the running time of memoization. Given my answer to the previous question, all you need is to somehow bound the size of the elements of the sequence. In many cases one can get reasonable bounds, for example this is probably possible for recurrence relations in which $\gamma_n$ depends polynomially on $n$ and $\gamma_{n-1},\ldots,\gamma_{n-c}$ for some finite $c$. While you shouldn't expect to get tight bounds this way, for a "generic" recurrence relations, one can probably predict the order of growth.


The short answer is because of RFC 791 which reads "All hosts must be prepared to accept datagrams of up to 576 octets (whether they arrive whole or in fragments)."

If you take 20 octets for IP and 20 octets for TCP then you're left with 536 for MSS.

Now why is 576 chosen? Mostly likely the fact that machine at that time wasn't that powerful and some reasonable minimum number had to be agreed that would be supported across all of the devices regardless how low-fi they are.


Are "of the order of n" and "Big O" the same thing?

"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g., $10n \in O(n)$, despite $10n$ being 10 times as larger as $n$). They can hardly be considered the same things. What the lecturer is trying to do here is supposedly give you some (hand-wavy) intuition as to how Big O notation works, but that should not replace you actually sitting down and learning the precise definitions.

As for your request regarding further reading on Big O notation, (in addition to the linked Wikipedia article) I suggest you take a look at our reference question.

An addendum: After listening to the video again, you can make out the lecturer say "of the order of $n$". This is the British English version of American English "on the order of" and carries the same meaning.


Distribute a number of tasks into multiple days (scheduling)

Suppose that you have 200 tasks to be scheduled in 100 days. The capacity of each day is 4. Task 1 has capacity 1, task 200 has capacity 3, and tasks 2 to 199 have capacity 2.

In any solution, task 1 and task 200 have to be assigned to the same day. That means that there is a big violation of the ordering of the tasks. So even if you could solve your problem effectively, the best solution (which is indeed hard to compute) might still be very bad.

Even worse, even if we totally disregard the ordering constraint, there could still be no solution. Consider two days of capacity 7 and four tasks of length 2, 3, 3, 6, respectively. The total length is 14 = 2 $\times$ 7, yet there is no way to separate the tasks into two days of capacity 7.
This problem (in which the precedences are not taken into account) is called the Partition problem, so that is one keyword you might want to search for. Unfortunately,  checking if a solution to the Partition problem exists is a strongly NP-complete problem whenever you have 3 days or more.


Since FSM's can't count identical sequences, I don't think both of your answers would be correct. You can take a look here, (pumping lemma) to prove why $L= \{a^nb^n | n \ge 0 \}$ is not regular, thus you can't write a FSM for it. Also a good example here shows the proof. On the other hand it would be different if you are meaning $a^*b^*a$ which can be written as a FSM.


Good Question. It looks like some kind of ripple counter.  It repeats after 15 steps. Values (consider the outputs to be 8,4,2,1) as 8,4,2,9,12,6,11,5,10,13,14,15,7,3,1.
Zero only for one step after reset, not repeated.


Bubble sort: average number of total key comparisons

I'm assuming that all elements in the array you're sorting are distinct.
The average number of comparisons over all permutations of the array is equal to the expected value of the number of comparisons, so let's calculate that instead.
The total number of comparisons done to sort some array $A$ (length $N$) is equal to $N - 1 + (\text{Number of inversions in } A)$, where an inversion is a pair of indices $i < j$ where $A_i > A_j$. By linearity of expectation, the expected number of comparisons is thus
$$
N - 1 + \sum_{i < j}P(A_i > A_j) = N - 1 + \frac{N(N - 1)}{4}
$$


How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?

Even the decision version of this problem, in which we try to determine simply if there exists any feasible solution, is NP-hard by reduction from Exact Cover.  (The optimisation version, where we seek a feasible solution that minimises $|S|$, is clearly at least as hard as this.)

The single-row, single-column matrix containing the value 0.5 is an example of an input for which there is no feasible solution.  Here's another:

$$
\begin{bmatrix}
0.2 & 4\\
3.1 & 3\\
5 & 0.6
\end{bmatrix}.
$$

Building a "Choose at most one" gadget

First, notice that if the maximum value in some row $a_i$ is $x > 0$, and this row contains (at least) two copies of $x$, say at $a_{ij}$ and $a_{ij'}$, $j' \ne j$, then $S$ cannot contain both $j$ and $j'$, since if it did then one of the following two cases must arise, each of which leads to a contradiction:

$i \in K_j \cup K_{j'}$: Suppose w.l.o.g. that $i \in K_j$.  But then $\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$, contradicting the requirement that $\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$.
$i \notin K_j \cup K_{j'}$: Then suppose $i \in K_p, p \notin \{j, j'\}$.  But then $\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$, and since $x$ is maximal in row $i$, the highest that $a_{ip}$ could be is clearly $x$, so we must be violating the same inequality as before.

Thus we can choose some maximum value that is safely higher than the sum of all non-maximum values in the row, and use copies of this maximum value to enforce that at most one of those columns is included in $S$.

We can turn this "choose at most one" constraint into a "choose exactly one" constraint by using any positive value less than 1 as the "non-maximum" value.  That's because every row $i$ belongs to some part $K_j$ of the row partition, and if $a_{ij} < 1$ then the RHS of the inequality becomes negative for row $i$, so there is no way to satisfy it: thus at least one $j$ must be forced into $S$ such that $a_{ij} \ge 1$.

So, to ensure that exactly one of the columns in some set $T \subseteq N$ is forced into $S$, create a row $a_i$ as follows:

Set $a_{ij} = n+1$ for each $j \in T$.
Set $a_{ij} = 0.5$ for every other $j$.

Thus the reduction from Exact Cover is straightforward: there is a row for each element, a column for each set, with $a_{ij} = n+1$ whenever set $j$ includes element $i$ and $a_{ij} = 0.5$ otherwise.  Both directions ("Input EC instance is a YES-instance $\implies$ constructed instance of OP's problem is a YES-instance", and "Constructed instance of OP's problem is a YES-instance $\implies$ input EC instance is a YES-instance") are clear.


How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large?

It's possible to answer such queries in time $O(M^{1 - S/N})$, where $S$ is the size of the subset in the query, using a data structure from Ron Rivest:

Partial-Match Retrieval Algorithms.  Ronald L. Rivest.  SIAM Journal Computing, vol 5 no 1, March 1976.

Basically, you convert each set to a bitvector of length $N$, then use Rivest's partial-match queries.  This is ever so slightly faster than the naive algorithm, whose running time will be about $O(M)$ (or a bit more).

Your idea using indices is another approach that might be faster in practice, especially if most sets are much smaller than $N$.  Note that it's possible to optimize this a bit.  Your index will have, for each string $x$, a list of indices of sets that contain $x$ and the length of that list.  Now, given a set $A$, you can check for each $x \in A$ the length of the corresponding list in the index, and find the shortest such list, and enumerate all entries in that list to see if any of them are a superset of $A$.  See  also https://cstheory.stackexchange.com/q/19526/5038.  I think the worst-case running time is no better than the naive algorithm, but in practice it might perform significantly better.


The empty word belongs to the language, since on all its odd positions -- all zero of them -- we find a $b$.

$eb$ does not belong to $\{a,b\}^*$, hence it does not belong to the language.


How can average queuing delay exceed 1 if the $La/R \leq 1$?

It depends on the r.v's of the arrival  the service process.

For example, suppose the arrival and service process are all deterministic  process. For example, a packet of one bit ($L=1$) arrives in every second ($a=1$), and the router transmits  a bit in every second ($R=1$). Of course that in such case the average queuing delay equals to 1.

However, if for example in a system where the packet arrivals are determined by a Poisson process with parameter of $\lambda=a$ seconds  and job service times have an exponential distribution (M/M/1) with average of $1/\mu=\frac{L}{R}$ seconds (which describes a system with packet length $L$ and average transmission rate of $R$), i.e., $\mu=\frac{R}{L}$ the service time equals to $\frac{1}{\mu-\lambda}- \frac{1}{\mu}$. As $\frac{La}{R}$ approaches $1$, then $\mu-\lambda$ approaches $\infty$ the service time approaches infinity.

Now for the strange behavior of  $\frac{La}{R}=1$ for M/M/1 queue: When $\frac{La}{R}=1$ that means that the probability a packet enters the router equals the probability that a packet exits the router. That means, the probability that the router contains $i$ packets equals  the probability that the router contains $j$ packets, for every $i$ and $j$. Thus, the number of packets in router approaches $\infty$,  as well as the queuing delay.


Given snapshot and boolean circuit how to compute coNP formula?

You want to know how, given a circuit $C$, one can express the statement "given $i$, $C$ correctly computes $z_i$, the i'th snapshot in the computation of $M$ on some fixed input $x$", by a coNP predicate. Note that if this can be done, say using the predicate $\varphi (C,x)$, then
$$\psi(x)=\exists C: \varphi(C,x)\land C\left(2^{|x|^c}\right) \text{ is accepting}$$

is exactly the $\Sigma_2$ formula you're looking for. To see why, note that $x\in L$ iff the last snapshot is accepting, or equivalently if $C\left(2^{|x|^c}\right)$ is accepting, and $C(i)$ correctly computes $z_i$. So if $\varphi(C,x)$ indeed expresses "C correctly computes $M$'s snapshots on input $x$", then $x\in L \iff \psi(x)$. If you have a guarantee that polynomial circuits for $L$ exist, then you can bound the existential quantifier, and only look for poly-size circuits.

So how do we write $\varphi(C,x)$ as a coNP predicate? Using locality, you know that the $i'th$ snapshot depends on some $k$ previous ones (where $k$ is a constant depending on the number of tapes). $C$ correctly computes the snapshots if for all $i,i_1,...,i_k$ (this gives you the universal quantifier) it holds that
$T\left(x, C(i), C(i_1),...,C(i_k)\right)$, where $T$ depends on $M$'s transition function. Intuitively, $T$ checks whether $i_1,...,i_k$ are the previous indicies of snapshots who determine $z_i$, and if so verifies that the transition was indeed according to $M$'s rules.


$\Sigma$ is a finite set of elements called letters. A word is a sequence of 0 or more letters. For every alphabet, there is a unique 0-letter word called the empty word, denoted $\epsilon$. By definition, $\epsilon\notin \Sigma$, for eny $\Sigma$.

Thus, $\Sigma^*$ and $\Sigma^+$ are both well defined, and are used for different purposes.

Mathematically, $\Sigma^*$ with the concatenation operation is a monoid, with $\epsilon$ being the identity element. $\Sigma^+$ is thus a semi-group, with the concatenation operation, as it doesn't have an identity element.


Conflict Driven Clause Learning backtracking clarification

Here's the relevant paragraph from the MiniSAT paper:

  The decision phase will continue until either all variables have been assigned, in which case we have a model, or a conflict has occurred.  On conflicts, the learning procedure will be invoked and a conflict clause producted.  The trail will be used to undo decision, one level at a time, until precisely one of the literals of the learnt clause becomes unbound (they are all $False$ at the point of conflict).  By construction, the conflict clause cannot go directly from conflict to a clause with two or more unbound literals.  If the clause remains unit for several decision levels, it is advantageous to chose [sic] the lowest level (referred to as backjumping or non-chronological backtracking).

A point you seem to have missed is that once the learned clause becomes unit due to undone assignments (backtracking), the solver doesn't stop there.  There could be other assignments before this one that have no bearing on the current conflict and experimentally it has been shown that it is better to undo these unrelated assignments also.  So the solver continues to undo assignments until the next undo would make the learned clause non-unit, i.e. it would contain more than one unassigned variable.  The solver stops here, runs unit propagation to satisfy the unit clause and then resumes the search, assigning variables normally.

Note also that the current decision variable may not be present in the learned clause.  A common strategy for a CDCL solver is to find the first unique implication point and use that variable in the learned clause.  In some cases the first UIP is the decision variable, but often it is not.


For Turing machines I/O corresponds to using the tapes:

a disk is a tape which has been rolled up
keyboard is the input tape
display is the output tape

A more interesting question is how to model interaction between machines using communications channels (that's a form of I/O), especially asynchronous communication. You can look up communicating sequential processes and $\pi$-calculus to learn about computational models that account for communication (and these are not the only ones).

The $\lambda$-calculus is a bit different because it does not have a direct notion of I/O. However, in any programming language we may simulate an input or an output stream by passing around extra lists of chacarters (or bits) which represent input and output streams. Here is an example in Haskell (but using only purely functional part if Haskell without any real I/O):

    -- Simulated IO in a purely functional way in Haskell

    -- A dataype of programs which perform simulated IO and return
    -- results of type a
    data SimulatedIO a =
        Result a
      | Output String (SimulatedIO a)
      | Input (String -> SimulatedIO a)

    -- Run a simulated IO calculation on the given input stream.
    -- Return the result, the remaining (unused) input, and output.
    run :: [String] -> SimulatedIO a -> (a, [String], [String])
    run input (Result a) = (a, input, [])
    run input (Output s c) =
      let (x, input', output) = run input c
      in (x, input', s : output)
    run (s:input') (Input c) = run input' (c s)

    -- Example
    greeter :: SimulatedIO Int
    greeter =
      Output "What is your name?" -- ask the user for his name
             (Input (\name -> -- read the name
                Output ("Hello " ++ name) -- greet the user
                       (Result (length name)))) -- return the length of user's name

    -- Execute the example with simulated input ["John", "Banana", "Orange"]
    example = run ["John", "Banana", "Orange"] greeter

    -- the result is
    --
    --    (4, ["Banana","Orange"], ["What is your name?","Hello John"])
    --
    -- 4 because "John" has four characters
    -- ["Banana","Orange"] is the unused input
    -- ["What is your name?","Hello John"] is the output


Is traversing an unconnected graph possible?

That's a question only your professor can answer. There are at least two possible solutions:

Each "chain" involves a single connected component.
Some links will be among non-friends.

In the latter case, you would like to minimize the number of unfriendly links. If there are $c$ connected components, then you only need $c-1$ of these.


Let $A$ be a DFA accepting $L_1$, and let $Q$ be its set of states. Denote by $L_A(q)$ the set of words which cause $A$ to move from its initial state to state $q$. For each state $q$ and word $w$, one of the following holds (exercise):

For every $x \in L_A(q)$, $xw \in L_1$.
For every $x \in L_A(q)$, $xw \notin L_1$.

We now modify $A$ by determining its accepting states as follows. A state $q$ is accepting if for some word $w \in L_2$, $xw \in L_1$ for all $x \in L_A(q)$. It is not too hard to show that the modified automaton accepts $L_1/L_2$ (exercise).


Selection Sort runtime in terms of Big O

Remember what $O(n^2)$ means: it means that there is a constant $c$ such that, for large enough $n$, the number of steps is at most $cn^2$.  The constant doesn't have to be $1$; in this case, it looks like the constant is about $\tfrac12$.

Why is $(n-1) + (n-2) + \dots + 2+1$ equal to $O(n^2)$?  Because you're adding up $n-1$ numbers and the average of those numbers is half-way between the first one and the last one, i.e., $\tfrac12(1 + (n-1))$.  So the total is $$(n-1)\times \tfrac12(1 + (n-1)) = \tfrac12(n^2-n).$$Plug in $n=5000$ and you get... *drumroll*... $12497500$.


Can NFAs determinization be efficient given that the statespace is exponential?

Let me mention a variant of the powerset construction. In this variant, we are going to construct only states reachable from the initial state. The way it works is as follows:

Create a list of states to-be-processed, and populate it initially with $\{q_0\}$, where $q_0$ is the initial state of the NFA.
While the to-be-processed list is non-empty, remove a state $S$, and compute all states reachable from $S$ by reading one character. Put any of these which hasn't been encountered yet in the to-be-processed list.

This variant (which I haven't quite specified in full) constructs the powerset automaton restricted to states reachable from the (new) initial state, and runs in time proportional to the resulting number of states (and the alphabet size).

The same construction, and indeed the vanilla powerset construction, also works for NFAs with several initial states. The only difference is that we start with the set $Q_0$ of initial states (which is also going to be the initial state of the resulting DFA) rather than with $\{q_0\}$.


Try plotting them. You can also notice that as $n$ increases by one, $e^n$ increases by a multiplicative factor of $e^{n+1}/e^n=e$, while $2n^2$ increases by a multiplicative factor of $\frac{2(n+1)^2}{2n^2} \longrightarrow 1$.


If an arbitrary language $L$ is closed under reversal ($L=L^R$), then $L^*$ is also closed under reversal, since

$$
\begin{array}{ll}
  L^R &= \{ w_1 \ldots w_n \ |\ \forall i.\ w_i \in L \}^R \\
      &= \{ (w_1 \ldots w_n)^R \ |\ \forall i.\ w_i \in L \} \\
      &= \{ w_n^R \ldots w_1^R \ |\ \forall i.\ w_i \in L \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i^R \in L \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i \in L^R \} \\
      &= \{ x_1 \ldots x_n \ |\ \forall i.\ x_i \in L \} \\
\end{array}
$$

So, being $\{a,b\}$ trivially closed under reversal (provided $a,b$ are letters, not words), $\{a,b\}^*$ is such.


How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

A solution in the TSP problem is a sequence of $n$ vertices.
Consider a labeling $1,\dots, n$ of the $n$ vertices.
We need $O(\log{n})$ bits to encode the label of each vertex.
Then, any sequence of $n$ vertices can be described by $O(n\log{n})$ bits; the concatenation of $n$ vertex labels.
Hence, any solution $s$ of the TSP can be described by a number of bits that is polynomial in $n$.

The size of the instance $I$ is also polynomial in the number of vertices $n$, as noted in the original question.


Equivalence of Kolmogorov-Complexity definitions

I apologize in advance for that I give way too many details, but I'm about to contradict people.

About $K(x)≤K'(x)+c$

The fact that $K_1(x)≤K_2(x)+c$ usually comes from an interpreter of the description language #2 into the description language #1 and not from a translation from programs of #2 into programs of #1.

For example $K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$ and you get this inequality as simply as this:

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Then your constant $c_\mathtt{py2c}$ will be something like $528+490240688$ where $528$ is the number of bits for this code and $490240688$ bits is the size the official Python interpreter written in C. Of course you only need to interpret what is possible in your description language for Python so you can do better than 69 MB :-)

What is important is that you can write your Python program linearly in your C code. For example, a language where you need to put "BANANA" between every character is not a very good description program and the property is then false. (But if the description language authorizes you to write data in a separate file or in a block, this problem disappear)

Why your $K_1(x)=q$ is flawed

The problem with your definition of $K_1$ is that you may need more than $q$ bits to describe a Turing machine with $q$ states because you need to encode transitions.

So no $K_1$ and $K_2$ are probably not equivalent, but that's mainly $K_1$'s fault. I think that we can prove that for all $a>0$ there is a $c_a$ such that $K_1(x)≤a|x|+c_a$. Of course any $a<1$ is enough to disprove the fact that $K_1$ is not a valid function, since it would mean that we can encode more all $2^n$ possible strings of length $n$ into $an+c_a$ bits.

But the size is an incredibly tight bound when building Turing machines. The idea is that in a block of $b$ states there are $b^{2b}$ ways to find transitions for each state and that's better than the usual $2^b$ ways you can fill $b$ bits. Then you can store in each block $\log_2 b$ bits of information. (not $2\log_2 b$ because you have to go in and out the block one way or another)

So yeah... With blocks of size $2^{1/a}$ you could probably prove $K_1(x)≤a|x|+c_a$. But I already written way too much about why the number of states is not a valid Kolmogorov complexity function. If you want me to elaborate, I will.

Now about $K_2$

The naive descriptive language corresponds roughly to $K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$ (i.e. $\log_2q$ for each next state and details about write and termination).

As you seem to be, I'm convinced that a better/cheater way would be to authorize to encode "data" into Turing machine, maybe by adding a binary tag in the description language that says whether if a state is a data state (that just writes a bit and go to the next state) or if it does something else. That way you could store one bit of your $x$ in one bit of your descriptive language.

However if you keep the same $K_2$ you could use the same technique I used in the previous part to save a few bits, but I seem to be stuck at $K_2(x)≤a|x|\log|x|+c$ (for any $a>0$) .. maybe less than $\log|x|$, even, but obtaining $O(|x|)$ seems hard. (And I expect it should be $|x|$, not even $O(|x|)$.)


It's really hard to say, what kind recursion you mean. There are different variants I can think of. For what you have written, I guess it is something like this.

function findOT(int l,r)

if ((r-l)==2) return perimeter(l,l+1,r)

min= infinity
for a=(l+1)..(r-1)
    T=findOT(l,a)+perimeter(l,a,r)+findOT(a,r)
    if T<min then min=T
    endfor
return(min)


Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all!

(The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make do with constant additional space, by implementing the pointers as spaces.)


Is there a search engine over Artificial Intelligence and Machine Learning -related sites?

I was not able to find a mentioned search engine, but I was able to make it myself with a help of Google Custom Search. I made a custom search engine with *.edu, *.ac.uk, *.edu.au and so on sites and domain zones, 145 in a total at this moment. From my point of view that search engine gives much better result pages, than an ordinary search. Also, the search index is almost spam-free and paid content -free.

There is a feature, that allows one to inspect what sites are included in the index, to comment them and to vote for or against them (to purge unrelevant site from the index, for example). Also, everyone is welcome to suggest new sites using a special form on the site. In short, it has all very basic machinery needed to make such scoped search engine to be community driven.

Try it at http://neatserpent.com/

Give me your feedback, please.
Do you find it helpful and better than ordinary search engine?
Would you use it?

Please, spread the word, if you like it.


Find a path that contains specific nodes without back and forward edges

This is the Hamiltonian path problem.  No efficient algorithm is known, and it is widely suspected that no efficient algorithm exists.  You can read the linked article for references that suggest a variety of algorithms for this problem.


Uncapacitated facility location problem using local search

Not clear what is "open the additional facility $i^*$".
Isn't $i^* \in S^*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?

As the proof explicitly says, $i^* \in S^* - S$. In words, it is a facility which is open in the optimal solution but not in the locally optimal solution.
The phrase "open the additional facility $i^*$" indicates modifying the locally optimal solution $S$ by opening the additional facility $i^*$. This is clear from context, sine as you write, $i^*$ is already open in $S^*$, but is closed in $S$.
The facility $i^*$ is marked with a star since that's how the author chose to name this variable. The name of the variable isn't important. That said, $i^*$ is chosen by taking some facility which is open in $S^*$ but not in $S$. That is, it is part of the optimal solution but not of the locally optimal one. So the notation makes sense to me. It is using the convention that stars denote parts of the optimal solution.

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)

The set $R$ consists of all facilities in $S^*$ whose closest facility in $S$ is $i$. If $S = \{i\}$, then $R = S^*$, and in particular, $R$ could contain more than one facility. Out of all facilities in $R$, we choose the one closest to $i$, and denote it $i'$.

What is $i^*$ in the second paragraph?

As the proof explicitly says, $i^*$ is an arbitrary element of $R$ different from $i'$.


Algorithm to find out the number of times a number occurs consecutively in an array in a range specified

Define a sub problem solution as the range of longest sub series.
If there are more than one we solution is 2 at most. The once at the tips of the range.
and there are exactly (n^2-n)/2 sub problems here.
You can solve each sub problem in o(n).

If you were to remember the results of problems you solved.
You can remember all in o(n*(n^2-n)/2) and it's fine.

But, If you consider Dynamic programming.
There is a bottom up series to solve each sub problem in o(1) time.

when trying to solve(i,j) two cases are to consider:

the range is at the tip. so consider increasing the result.
the range is at the tip. just return the longest. again up to 2 ranges.


Problem using the Arden's Lemma on one automata

The mistake is in the equation for $L_3$: it should be $0^*$ instead of $\epsilon$.


A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary.

The short answer is that hash tables are faster in most cases, but can be very bad at their worst. Search trees have many advantages, including tame worst-case behavior, but are somewhat slower in typical cases.

Balanced binary search trees have a fairly uniform complexity: each element takes one node in the tree (typically 4 words of memory), and the basic operations (lookup, insertion, deletion) take $O(\mathrm{lg}(n))$ time (guaranteed asymptotic upper bound). More precisely, an access in the tree takes about $\mathrm{log}_2(n)$ comparisons.

Hash tables are a bit more variable. They require an array of around $2n$ pointers. Access to one element depends on the quality of the hash function. The purpose of a hash function is to disperse the elements. A hash table “works” if all the elements you want to store in it have different hashes. If this is the case, then the basic operations (lookup, insertion, deletion) take $O(1)$ time, with a fairly small constant (one hash calculation plus one pointer lookup). This makes hash tables very fast in many typical cases.

A general problem with hash tables is that the $O(1)$ complexity is not guaranteed.

For addition, there's a point where the table becomes full; when that happens (or, better, a little before that happens), the table needs to be enlarged, which requires moving all of its elements, for an $O(n)$ cost. This can introduce “jerky” behavior when a lot of elements are added.
It's possible for the input to collide over a few hash values. This rarely happens naturally, but it can be a security problem if the inputs are chosen by an attacker: it's a way to considerably slow down some servers. This issue has led some programming language implementations (such as Perl and Python) to switch from a plain old hash table to a hash function involving a random number chosen when the hash table is built, together with a hash function that spreads this random datum well (which increases the multiplicative constant in the $O(1)$), or to a binary search tree. While you can avoid collisions by using a cryptographic hash, this is not done in practice because cryptographic hashes are comparatively very slow to compute.

When you throw data locality into the mix, hash tables do poorly. They work precisely because they store related elements far apart, which means that if the application looks up elements sharing a prefix in sequence, it will not benefit from cache effects. This is not relevant if the application makes essentially random lookups.

Another factor in favor of search trees is that they're an immutable data structure: if you need to take a copy of a tree and change a few elements in it, you can share most of the data structure. If you take a copy of a hash table, you need to copy the whole array of pointers. Also, if you're working in a purely functional languages, hash tables are often not an option.

When you go beyond strings, hash tables and binary search trees make different requirements on the data type of the key: hash tables require a hash function (a function from the keys to the integers such that $k_1 \equiv k_2 \implies h(k_1) = h(k_2)$, while binary search trees require a total order. Hashes can sometimes be cached, if there is enough room in the data structure where the key is stored; caching the result of comparisons (a binary operation) is often impractical. On the other hand, comparisons can benefit from shortcutting: if keys often differ within the first few bytes, a negative comparison can be very fast.

In particular, if you're going to need the order on the keys, for example if you want to be able to list the keys in alphabetical order, then hash tables are no help (you'll need to sort them), whereas you can straightforwardly traverse a search tree in order.

You can combine binary search trees and hash tables in the form of hash trees. A hash tree stores keys in a search tree according to their hash. This is useful, for example, in a purely functional programming language where you want to work on data that does not have an easy-to-compute order relation.

When the keys are strings (or integers), a trie can be another option. A trie is a tree, but indexed differently from a search tree: you write the key in binary, and go left for a 0 and right for a 1. The cost of an access is thus proportional to the length of the key. Tries can be compressed to remove intermediate nodes; this is known as a patricia trie or radix tree. Radix trees can outperform balanced trees, particularly when many keys share a common prefix.


Let us start with the subroutine PARTITION. The loop maintains the following invariant:

  $A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$.

If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq j$. In particular, if $k \leq j$ and $\ell > j$ then $A[k] \leq A[\ell]$. This is what PARTITION promises:

  If PARTITION$(A,p,r)$ returns $q$, then $x \leq y$ for all $x \in A[p],\ldots,A[q]$ and $y \in A[q+1],\ldots,A[r]$.

Furthermore, the particular choice $x=A[p]$ guarantees that PARTITION terminates — I'll let you work out this detail yourself.

This promise given by PARTITION guarantees the correctness of QUICKSORT: PARTITION partitions the array into two halves such that in the sorted array, all elements in the first half precede all those in the second half. In order to complete the sort, it remains to sort each half separately.

What might be throwing you off is a different variant of quicksort, in which PARTITION gives a stronger promise: all elements in $A[p],\ldots,A[q-1]$ are at most the pivot $A[q]$, and all elements in $A[q+1],\ldots,A[r]$ are at least the pivot $A[q]$. The version you describe doesn't have this promise, but otherwise is very similar to the version that you are familiar with.


Time complexity and upper and lower bounds

Ever heard of Stirling's approximation? :) Well, it implies that $(\frac{n}{e})^{n} \leq n! \leq e^2 \cdot (\frac{n}{e})^{n+1}$. We will use it get a nice upper and lower bound on your function:
Upper Bound:
$$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \leq n + \log \frac{n^n}{n!} \leq n + \log (e^n)  = O(n)$$
Lower Bound:
$$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \geq \log \frac{n^n}{n!} \geq \log \Big(\frac{e^{n-1}}{n} \Big) = \log(e^{n-1}) - \log n= \Omega(n) $$

Thus, we get $\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil = \Theta(n) $


From my understanding of the 2-processor, if you want to do the same thing you would delete the statement (I truly dont know why you had it. There could be something interesting behind this statement of yours).

 i = turn

and instead, let each of the $n$ processors have an id from $\{1, \dots, n\}$. Then, you would let the processors go in sequence to the critical code. That is, assume a processor $i$ takes the token and left it. Then, it has to wait the other $n- 1$ to take the token if it want to take it again. The problem in this solution is the sequential method of taking the token.

If you want to have something more efficient, then have a look at the Lamport's bakery algorithm. The pseudocode of the algorithm is available in the site you provided, and it is explained in wikipedia. The idea of this algorithm is very simple in fact. There is a queue of processors that want to get the token. These processors enter the queue, and the first come is first served.

In regard to the link you included in your question, this is done by these lines:

number[i] = max(number) + 1;   // enter the queue !
...
...
while (number[j] != 0 && (number[j] < number[i] ||
                         number[j] == number[i] && j < i) )
// wait until your turn comes.
...
Do your critical section ! ...
...
 number[i] = 0;     // go out of the queue ..

Obviously, you can play around with this. But it is a neat way of implementing FIFO requests.


How to find whether a grammar is ambiguous?

Since you are trying to prove that the grammar is ambiguous, you must simply provide an example of a string where that grammar results in more than one parse tree or derivation. (Note that this is an entirely different ordeal than trying to prove that a grammar is unambiguous.) Since the string abbbb indeed has two distinct leftmost  derivations, you have shown that the grammar is ambiguous. This proves that the grammar is not unambiguous since it is not the case that each string has at most one parse tree or derivation.


Suppose that the tree has depth $D$. Then all leaves are at distance at least $D/5$ from the root, which means that the tree contains the full binary tree of depth $D/5$ as a subtree. This implies that $n \geq 2^{D/5}$, and so $D = O(\log n)$.

Note that this argument doesn't use the recursive part of the definition.


How do you go about designing a vector processor architecture for the sum of matrix products?

From talking to the OP, algorithms that handle parallel matrix multiplication are apparently acceptable answers. Matrix multiplication and parallel algorithms for it are a highly studied problem in CS partly because of its widespread application e.g. in scientific computing. There are other ways to parallelize the problem given in the question, e.g. an obvious "map-reduce" that maps the separate matrices to separate processors and the reduce step does the addition.

There is some discussion on Wikipedia, Matrix multiplication, "Communication-avoiding and distributed algorithms."
Here is a somewhat recent survey of performance of standard algorithms.
Performance Analysis and Evaluation of Parallel Matrix Multiplication Algorithms
Ziad A.A. Alqadi, Musbah Aqel, and Ibrahiem M. M. El Emary.
The standard (scientific computing) matrix libraries BLAS and LAPACK have standard parallel matrix multiplication algorithms built in.
The problem as stated is also readily computed by a GPU e.g. via standard CUDA programming. This subject is increasingly studied in undergraduate classes e.g. at CalTech.

Note also the new "scicomp" stackexchange for questions on scientific computing.


Algorithm for finding the best “route” of tasks

If you have just one person to complete the tasks, this is the (in)famous Travelling Salesman Problem (TSP), which is NP-complete, so an efficient exact algorithm is a very remote possibility. Unless your problem is quite small, you'd have to settle for approximate solutions. There are algorithms that can solve enormous instances of TSP in (somewhat) reasonable time, but I have no pointers at hand.


Using Data Compression on the output of Data Compression

When we compress something the output is smaller than input (that is the purpose of compression, otherwise we do not use it or cope with bigger file). This can be achieved by various methods including (but not limited to) matching of substrings (dictionary compression) or frequency of characters (entropy compression, like Huffman encoding) or arithmetic coding (like MTF, Elias etc.).
Some methods like (Bijective) Burrows Wheeler Transform does not compress, just change the order of characters so other methods might benefit from local similarity of characters, so it is used in conjunction with other techniques.

If we try to apply dictionary method or entropy method twice (or more times) there are no benefits at all, we already exploited the redundancy of data. Using methods with chunks of data twice will give us the issue of compressing the packed data and the header (dictionary, frame, characters etc.), so it is harder task than one we started with and the most benefitial would be changing frame size or make it addaptive (but not applying the same method more times).

Encryption is not concerned about file size - it secures data with key so that any person obtaining the file without the key will have very hard time opening it. If the quality of encryption is useable the resulting file has no obvious dependencies or visible redundancy. Encrypted files are not compressible. Now encrypting chunks several times will not add any security and will not compress file.

Please keep in mind that methods like Cezar, Rot13 and xor of key (cyclic) with data are not encryption methods, and even if they were, cyclic shift of characters (mod 256) will not change compression.

About limits - when we compress something then we have to encode header, dictionary etc., so our output file is transformed input plus additional information about it, which is commonly short and not compressible, so every time we put output of compression into input of another one we have a bit more to deal with and some redundancies were already used, this is one limit.
The second limit is that we cannot compress anything in the mean sense, taking all possible inputs of given size, compressing and calculating the mean shows that we in fact ended with more data than we started with. At the best (unlikely) case we end up with the same amount of data. This comes from the fact that contraction of data with better result is not unique anymore so we cannot decompress it uniquely to original.


Minimisatiom using Myhill-Nerode Theorem

In the first automaton, you can see that every accepting state has a transition with 0 to an accepting state, while a transition with 1 goes to either a sink or is just non-existing. But this means that reading a 1 from an accepting state leads always to rejecting the input. Thus, all accepting states are equivalent.

In the second automaton, you can see that $q_2$ has a 0-transition to $q_5$, a non-accepting state, while the other two accepting states have 0-transitions to accepting states. Thus, $q_2$ cannot be equivalent to both $q_4$, and $q_3$. Moreover, $q_3$ and $q_4$ cannot be equivalent because reading 00 from both states leads to different behavior (one run is accepting, th other rejecting). Thus, in this case you cannot merge any of the accepting states.


Should one limit the maximum level of a skip list node?

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance.

The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a demoted item.

Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)

The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.

Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:

$$\mathscr{E}'(l) \in [\mathscr{E}(l)-l-1, \mathscr{E}(l)+1]$$

Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate

$$\mathscr{P}'(l) \in [\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}]$$

But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.

In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.


Proving that the set of grammars generating L or L complement is undecidable

Suppose that given a context-free grammar $G$, you could decide whether $L(G) = X$ and whether $L(G) = \overline{X}$. You can use it to decide UNIVERSALITY as follows:

Create a grammar $G_1$ such that $L(G_1) = L(G) \cap X$.
Create a grammar $G_2$ such that $L(G_2) = L(G) \cap \overline{X}$.
Accept if $L(G_1) = X$ and $L(G_2) = \overline{X}$.

The point is that we can construct the grammars $G_1,G_2$ algorithmically.

Note that for some $X$, deciding whether $L(G) = X$ could be decidable. The simplest example is when $X = \emptyset$. A more sophisticated example is $X = w^*$ (this follows from Parikh's theorem, for example).


Why deadlock in cigarette smokers problem

Agent A consumes agentSem, and produces tobacco and paper.

That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco.

Now, all the smokers are stuck, and the agents as well.


Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle

Some hints:

Could you solve the problem if the function was of the form $f : GF_p \to GF_p$, i.e., a univariate polynomial?  I suggest solving that special case first.  The below are some hints on how to do that:

If the error was zero, would you know what to do?  Could you devise a strategy that would always work in that situation?  How many queries would your strategy need?

Now suppose you applied your strategy, in the situation where there could be errors (but with the error probability bounded as you've described).  What's the probability that your strategy gives the wrong answer?  What's the probability that your strategy gives the right answer?

You might find it useful to use a union bound.

Can you think of any way to check whether a possible solution is correct?

Finally, once you can solve the univariate case, can you think of any way to repeat that procedure multiple times to handle the situation of a polynomial in two variables?


Is the number of shortest paths between every two vertices at most 4*n^3?

Consider the following graph, where we have $3\times 4+1=13$ nodes, $a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4, a5$ and $4\times4=16$ edges $a1b1, a1c1, b1a2, c1a2, \cdots, a4b4, a4c4, b4a5, c4a5$ with weights $1,1,1,1,\cdots, 4,4,4,4$ respectively.

Every path from $a1$ to $a5$ is a shortest path between them since all of them have the same weight (length). There are $2^4=16$ of them.

Consider extending this graph to a much larger graph, following the same pattern. For example, suppose we will have $100\times3+1=301$ nodes and $100\times4+1=400$ edges. Now compute how many shortest paths there are between $a1$ and $a301$.

Exercise 1. Construct a graph with the same constraint such that there are more than $4n^3$ paths of the same weight between every two vertices.


Undecidability of the language of PDAs that accept some ww

Your proposed idea doesn't work, because after you have checked the first half of the input with your PDA, you have popped them all so you cannot reaccess them for comparing with the second half.
The correct idea should be making a PDA that checks if odd number configurations leads to even numbered configurations in the first half and vice versa in the second half. Also, make sure the PDA handles the start and accepting state. Then convert the PDA to CFG and pass it to the decider for the language $\{ww\}$. Accepts if it accept and rejects otherwise.
This will work as you can show that the PDA as constructed above will recognize string of form $ww$ iff $M$ accepts $w$. This is because the parity checks of configurations only gives incomplete information, but when supplied with the fact that you have two equal computation history in some string, it tells you each half of that string is actually an accepting computation history of $M$ on $w$.


Regular expression for string with substring 010 and ending with 01

The regular expression would be like $(0 + 1)^*010(0 + 1)^*01 + (0 + 1)^*0101$.
Transformation of a regular expression to a DFA has a well-defined algorihtms, and you can find them in the resources.


Matching Algorithm - How to maximize matched quantity with unique matching rules?

The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1

Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.

This special case seems easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type conflict-free. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.

More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.

For example, on the input $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, the graph will look like the following:

Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but only influences the weight of the two edges between types A and D. So the approach works for this case.

However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1]$. We now get the following graph:

The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.

I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.

1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.


Is my recursive algorithm for Equivalent Words correct?

Your algorithm is not correct.
Here is a counterexample: $D$ contains the words $aa,bb,ac,bc$; $v=aa$; and $w=bb$.
A transformation is possible $(aa \to ac \to bc \to bb)$ but your algorithm won't find it.


What questions can denotational semantics answer that operational semantics can't?

There is no real agreement what characterises denotational semantics (see also this article), except that it must be compositional. That means that if $\newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack} \SEMB{\cdot}$ is the semantic function, mapping programs to their meaning, something like the following must be the case for all $n$-ary program constructors $f$ and all programs $M_1$, ..., $M_n$ (implicitly assuming well-typedness):

$$
 \SEMB{f(M_1, ..., M_n)} = trans(f) (\SEMB{M_1}, ..., \SEMB{M_n})
$$

Here $trans(f)$ is the constructor corresponding to $f$ in the semantic domain.
Compositionality is similar to the concept of homomorphism in algebra.

Operational semantics is not compositional in this sense. Historically, denotational semantics was developed partly because operational semantics wasn't compositional. Following D. Scott's breakthrough order-theoretic denotational semantics of $\lambda$-calculus, most denotational semantics used to be order-theoretic. I imagine that -- apart from pure intellectual interest -- denotational semantics was mostly invented because at the time (1960s):

It used to be difficult to reason about operational semantics.
It used to be difficult to give axiomatic semantics to non-trivial languages.

Part of the problem was that the notion of equality of programs was not as well-understood as it is now. I'd argue that both problems have been
ameliorated to a substantial degree, (1) for example by bisimilation
based techniques coming from process theory (which can be seen as a
specific form of operational semantics) or e.g Pitts work on
operational semantics and program equivalence, and (2) by the
developments of e.g. separation logic or Hoare logics derived as typed
versions of Hennessy-Milner logics via programming language embeddings
  in typed π-calculi. Note that program logics (= axiomatic semantics)
are compositional, too.

Another way of looking at denotational semantics is that there are many programming languages and they all look kind-of similar, so maybe we can find a simple, yet universal meta-language, and map all programming languages in a compositional manner to that meta-language. In the 1960s, it was thought that some typed $\lambda$-calculus is that meta-language. A picture might say more than 1000 words:

What is the advantage of this approach? Maybe it makes sense to look
  at it from an economic POV.  If we want to prove something
  interesting about a class of object program  we have two options.

Prove it directly on the object level.
Prove that the translation to the meta-level (and back) 'preserves' the
property, and then prove it for the meta-level, and then push the result back to the object level.

The combined cost of the latter is probably higher than the cost of
  the former, but the cost of proving the translation can be
  amortised over all future uses, while the cost proving the property
  for the meta-level is much smaller than that of the proof on the
  object level.

The original order-theoretic approach to denotational semantics has so far not lived up to this promise, because complicated language features such as object orientation, concurrency and distributed computation have not yet been given precise order-theoretic semantics. By "precise" I mean semantics that matches the natural operational semantics of such languages.

Is it worth learning denotational semantics? If you mean order-theoretic approaches to denotational semantics, then probably not, unless you want to
work in the theory of programming languages and need to understand older papers. Another reason for learning order-theoretic approaches to denotational semantics is the beauty of this approach.


Who coined the term "artificial intelligence"?

Based on my research, there is no conclusive answer as to who coined the term, although McCarthy can be credited with helping the term to find widespread acceptance within the computer science community. See "AI: The Tumultuous History of the Search for Artificial Intelligence" by Daniel Crevier (Published in 1993 by BasicBooks):

"Overcoming the resistance of some participants (Samuel felt that "artificial" sounded phony, and Newell and Simon persisted in calling their work "complex information processing" for years afterward), McCarthy persuaded the majority to go for "artificial intelligence." He lays no claim to having coined the phrase, and admits it may have been used casually beforehand. Yet nobody denies him the achievement of getting it widely accepted."

-- Daniel Crevier, p.50


The only way to know is to try it and see.  There is no general theory that allows us to reliably predict the outcome of such experiments.

That said, I question the motivation.  You say that it feels "a bit heavy", but it's not entirely clear to me what that concretely means or why it would matter.  Perhaps it is worth mentioning that even with dozens of layers, neural networks can be surprisingly fast.  Remember the warning about premature optimization: don't let a general fear or assumption that the simple solution might be slow tie you up in knots and lead you to overly complex solutions.  Instead, in this case I suggest you try the simplest solution first, and measure how well it performs.  Only if you have evidence that it fails in some concrete, measurable way would you then consider more complex approaches.  This will help you avoid unnecessarily complicating your life.

Finally, remember that there are other approaches to computer vision other than deep neural networks.  People were doing object detection before neural networks became popular, and there are other methods that might be effective for detecting simple geometric shapes (e.g., morphological operators, Hough transform, shape descriptors, and more).  But try the simple things first, and measure.


Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.)

If $\mathrm{P}=\mathrm{NP}$, Wikipedia claims that every problem in $\mathrm{P}$ is $\mathrm{NP}$-complete. However, this is not true: in fact, every problem in $\mathrm{P}$ would be $\mathrm{NP}$-complete, except for the trivial languages $\emptyset$ and $\Sigma^*$.

You can't many-one reduce any nonempty language $L$ to $\emptyset$, because a many-one reduction must map "yes" instances of $L$ to "yes" instances of $\emptyset$, but $\emptyset$ has no "yes" instances. Similarly, you can't reduce to $\Sigma^*$ because there's nothing to map the "no" instances to.  However, if $\mathrm{P}=\mathrm{NP}$, then every other language in $\mathrm{P}$ is $\mathrm{NP}$-complete, since you can solve the language in the reduction.

So, just to make it explicit:

your diagram is correct;
Wikipedia's isn't (unless you read the tiny disclaimer);
the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$" contains the two languages $\emptyset$ and $\Sigma^*$, and nothing else;
the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$-complete" contains every other language in $\mathrm{P}$ and nothing else.


Addition of a number of size $n$ takes time $O(n)$. Don't confuse a number and its encoding size, which is logarithmically smaller.

When multiplying an $n$-bit integer $a$ by an $n$-bit integer $b$ using the iterative addition algorithm, you are adding up to $n$ shifted copies of $a$. Each addition costs you $O(n)$ rather than $O(\log n)$. The numbers $a,b$ itself could be as large as $2^n$.


Clarification of the proof involving the regularity condition in Master Theorem

Let's start with the issue of iteration. Suppose that a function $f$ satisfies
$$ f(n/b) \leq (c/a)f(n). $$
Then it also satisfies
$$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$
You can prove by induction that for all integer $t \geq 0$,
$$ f(n/b^t) \leq (c/a)^t f(n). $$
As for your second question, about assuming that $n$ is large enough: the proof is just sloppy. You cannot assume that $f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n$ is a power of $b$.
They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for $n \ge b + b/(b-1)$. Using the idea of the proof of the special case where $n$ is a power of $b$, you can complete the proof of the general case. I would, however, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and you can trust the authors that it works out. Nothing interesting is hidden under the rug.


Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books.

One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point.

Another approach might be to use an ensemble classifier: you learn multiple weak classifiers, each of which outputs its own prediction at the label, and then to classify any point you run all of the weak classifiers and you take a majority vote of their predictions.

One simplistic method would be to periodically train a new weak classifier and add it to your ensemble.  For instance, suppose you have storage for $n$ points.  You could add each point to storage as you receive it, then when your storage gets full, train a weak classifier on all $n$ of those points, add it to the ensemble, and clear out your storage.

It might be better to bias your storage strategy towards remembering points that you have classified wrong.  For instance, as a simple example, you could reserve $n/3$ storage slots for remembering past points that were misclassified and $2/3$ storage slots for storing the last $2n/3$ points you received.  When the latter gets full, you could train a new weak classifier on all of those $n$ points, add it to the ensemble, then classify all $n$ of those points with the ensemble classifier, discard all the ones that were correctly classified by the ensemble classifier, and keep a random sample of size $n/3$ chosen from the remaining points (moving them into the $n/3$ slots for misclassified points and emptying out the $2n/3$ slots for new points).

Finally, you might also be able to adapt boosting methods to an online setting.  Boosting methods assign a weight to each training point; the higher the weight, the harder the weak classifier tries to classify that point correctly (i.e., the greater the penalty for misclassifying that point).  The idea is that points which have been classified wrong in the past will receive a higher weight, and so future weak classifiers will be biased towards trying to classify those points correctly.  Rather than trying to store all training points you've ever seen, I could imagine trying to store a random sample of the training points, where each point is selected with probability proportional to its weight.  Thus, you could store $n$ training points and their weights; after you train each new weak classifier, you can update the weights of all $n$ remembered points and then sample $n/2$ of them (say, the $n/2$ with highest weights, or take a random sample with distribution given by the weights).

I don't know how well these methods would work, but you could give them a try in your setting and see.  But start by exploring the literature.  You know what they say: a week in the computer lab can save you a day in the library.


The problem is NP-hard.

We show this by reducing vertex cover:

  Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?

We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:

All columns, except for the first, correspond to an edge. They get a regex $0^*1(0|1)^*$.

All rows correspond to a vertex. They get a regex that allows to write either

a $1$ in the first column and each column corresponding to an edge incident to that node and zeroes in all other columns, or
$0^*$

Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones.

The correspondence between solutions to the regex crossword and vertex covers should be obvious.

Example:

Find a vertex cover of size 2 for the following graph:

$V_A = 0^* \big| 10110$

$V_B = 0^* \big| 11101$

$V_C = 0^* \big| 10011$

$V_D = 0^* \big| 11000$

$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$

$E_1 = 0^*1(0|1)^*$

$E_2 = 0^*1(0|1)^*$

$E_3 = 0^*1(0|1)^*$

$E_4 = 0^*1(0|1)^*$

Lastly, you can set up the "crossword" so that $V_A$ through $V_D$ are the top regexes and $Counter$ and $E_1$ through $E_4$ are the left side regexes.

Solving this regex crossword give you a vertex cover of size 2 for nodes $V_A,V_B$ or $V_C,V_B$.

If we change k to be 1 and $Counter$ to be $0^* \big| 0^*10^*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.


Your loss function is proportional to the $\gamma n$ smallest square differences with respect to $\mu$.

This is minimized by sorting your $x_i$ and choosing the mean of the contiguous substring $x_k, x_{k+1}, \dots, x_{k+\gamma n-1}$with the smallest variance.


Is it a good idea to determine coordinates of object on images with regression algorithms?

It is possible to train a neural network to solve a regression problem.
See facial keypoints challenge
You should note that training a network for regression is harder then training towards a classification problem.
The network is more prone to unnormalised, different deviation values per feature, weight initialisation etc.
Try following the tutorial and then you'll have a better grasp on using ConvNets for regression.

Good luck!


A voting scheme where votes are scriptable

Broad context
First off, the field in which this sort of research would be carried out is called computational social choice (theory). Searching for papers or books in that field will give you exactly what you ask for: literature on mathematical models of (political) voting schemes, and related topics like resource allocation and judgement aggregation. As for a reference, I'd recommend the Handbook of Computational Social Choice. As a sidenote, if you want to ask questions about these things, the tag social-choice-theory on math.stackexchange.com might be a good idea.
Your voting rule
Now, as for your specific idea, there are some unclear parts. You consider probabilities, but are unclear on what exactly those probabilities mean. You imply that they're based on the proportion of votes any candidate gets, but the voters don't simply vote for a candidate. I'd recommend trying to really formalize your idea and see if it has some interesting properties. I'm not aware of any serious research effort in this sort of direction.
One thing to consider is the reason for such a system. That is, why would a voter want to vote for X only with a certain level of support, and Y otherwise? Is it 1.) because they prefer X but are scared that a vote for a minor candidate might be a waste, or is it 2.) because the level of support somehow changes the desirability of the candidate? In the case of 1.), the voter really just supports X, and has Y as their second favorite candidate. A solution might not involve a complicated ballot, as you propose, but perhaps just a good voting rule that fits in the existing mathematical frameworks. In the case of 2.), where a voter's true preferences might rely on other's preferences, making such a complicated ballot might indeed be a good idea.
Importantly, you must consider that every voter can submit such a ballot, and therefore changes in outcome might beget changes in preference which beget changes in outcome and so on and so forth. It might not be possible to make any decent voting rule within this system that is guaranteed to converge to some outcome. You'll even have to be careful that the outcome is not just well-defined, but computable.
Regardless of all this, we might already be able to answer one of your research questions. Unless I misunderstand things, there is not always an admissable outcome. Consider a single voter who votes X only if X has less than half of the votes, and Y otherwise. Now, if X would win, they would prefer Y, and vice versa. I don't have any direct ideas on how to relax admissibility to guarantee one exists.


Proof of contention of the wait-free consensus algorithm

This is the classical "critical-state argument", also called "bivalence argument", used by Fischer, Lynch, and Paterson to prove the impossibility of consensus in an asynchronous message-passing system where one processor may fail.

For (wait-free) binary consensus, the critical-state argument says that there must exist a state S of the system such that both decisions are still possible starting from S, but for every immediate successor S' of S the decision is determined. Thus we can partition the processors into two teams $\Pi_0$ and $\Pi_1$ such that a step of a processor from team $\Pi_0$ from S eventually results in decision 0 while a step of a processor from team $\Pi_1$ from S eventually results in the decision 1.

Now suppose that, in S, the next step of processor $p_0$ is to modify object $O_1$, and the next step of processor $p_1$ is to modify object $O_2\neq O_1$. Wlog we can assume $p_0\in\Pi_0$ and $p_1\in\Pi_1$. Since $O_2\neq O_1$, the steps of $p_0$ and $p_1$ commute and lead to the same state S'' regardless of their order. Moreover, since $p_0\in\Pi_0$, the consensus decision from S'' is 0. However, since $p_1\in\Pi_1$, the consensus decision from S'' is also 1, which is a contradiction.

The case in which some processors are about to perform a pure read operation similarly leads to a contradiction.

We conclude that in state S, all processors are about to modify the same object. Thus in any consensus algorithm there is at least one system state in which all processors are about to modify the same object.


Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?

There is some ambiguity in how to define these new machines, essentially based on the question whether we can nest the "bursts of doing infinitely many steps in some finite time" or not. In the weakest interpretation, we essentially just get an oracle Turing machine with access to the Halting problem. In the strongest, we get the Infinite Time Turing Machines (ITTM).

Both machines can easily decide the ordinary Halting problem. However, the proof of non-computability of the Halting problem uses very little prerequisites. In particular, it shows that none of our machines can solve their own Halting problems.

So while an ITTM can decide truth of all basic arithmetic formulas (by just searching through the natural numbers whenever required), they cannot decide all $\Sigma^1_2$-formulas. And to properly define and work with ITTMs, we need $\Sigma^1_2$-formulas. So we have just pushed undecidability further out, but we have not removed it.

A $\Sigma^1_2$-formula is one of the form
$$\exists A \subseteq \mathbb{N} \ \ \forall B \subseteq \mathbb{N} \ \ \phi(A,B)$$
where $\phi$ is a formula which contains only quantification over numbers, but not over sets of numbers.


There are parsimonious reductions between all NP-Complete problems: Well-known conjecture?

Yes, it is well known conjecture. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).


Who was the first to define Flow Shop / Job Shop problem?

Coffman and Demming's famous Operating Systems Theory, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" of Job Shop scheduling.  In the next paragraph, they introduce Flow Shop scheduling as a specialization of Job Shop, and cite

Johnson, S.M.; "Optimal two- and three-stage production schedules with set-up times included."  Naval Research Logistics Quarterly, 1(1):61-68, 1954.

Naval Research Logistics Quarterly seems to be a Wiley pay-walled journal, but my library has a subscription to it.  Johnson's paper begins:

Let us consider a typical multistage problem formulated in the following terms by R. Bellman:
"There are n items which must go through one production stage or machine and then a second one.  There is only one machine for each stage.  At most one item can be on a machine at a given time.
"Consider $2n$ constants $A_i, B_i, i = 1, 2, \cdots, n$.  These are positive but otherwise arbitrary.  Let $A_i$ be the setup time plus work time of the $i$th item on the first machine, and $B_i$ the corresponding time on the second machine.  We seek the optimal schedule of items in order to minimize the total elapsed time."

He doesn't give the full reference to Bellman. Johnson's paper extends the definition in the obvious way to 3 machines.


Is this combinatorial optimisation problem similar to any known problem?

You could formulate this as a gigantic integer linear programming (ILP) instance, and then apply an off-the-shelf ILP solver (lp_solve, CPLEX, etc.).  They will give you the best solution they can find.  Given the size of your problem instance, I don't know whether this will be efficient enough, but it would be easy to try.

Here's the ILP formulation.  We have a zero-or-one variable $x_r$ for each possible rectangle $r$, with the intended interpretation that $x_r=1$ means you include rectangle $r$ in your set and $x_r=0$ means you don't include it.  You want to maximize the objective function $\sum_r c_r x_r$ (where $c_r$ is the profit of rectangle $r$), subject to the restriction that $\sum_r x_r = n$ and that no two rectangles overlap.  The latter restriction can be expressed as a linear inequality by requiring $x_r + x_s \le 1$ for all pairs of rectangles $r,s$ that overlap.  So, in this way you get a ILP.


Fermat's last theorem: How to (partially) solve by programs

See for example Sophie Germain.
Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem.  She used her theorem to prove that all primes up to 100 would work. Apparently checking her theorem was quite a lot of work because later her theorem was used to check first the primes up to 187 and then up to about 1700. Having a computer and being able to check primes using software would have been very helpful. The "intelligent" work was done by Sophie Germain, a lot more boring work could have very well done by a (then non-existing computer).

Kummer proved an improved theorem, which unfortunately was even harder to verify. There were further improvements made, and this was used to check all primes up to 125,000 and later up to 4,000,000. Checking one prime took about 80 minutes on a 1970's computer - that would have been absolutely impossible to do by hand.

So there is a combination: Mathematicians find a way to decide for certain primes p that $a^p + b^p \neq c^p$ for all $a, b, c \geq 1$. The actual method to decide is too much work for a human to do in any reasonable time, so a computer comes very useful.

Wiles' theorem was completely different, all done by hand. However, if you follow the discussion at Wikipedia, you'll find there was mathematics beyond the reach of most mortals, based on more mathematics beyond the reach of most mortals, etc. quite a few levels deep.


taking the contrapositive, another stronger way of stating your question is "a SAT formula f is satisfiable iff either the sub-formulas f1, f2 from the assignment of a variable x or not x are satisfiable". but this is exactly the idea behind the DPLL algorithm (originating as the simpler DP algorithm) provably guaranteed to find a SAT solution. your basic idea also shows the similarity of the method with Gaussian reduction; ie this is not usually remarked but DPLL algorithm appears to be like/ an analog of "boolean Gaussian reduction".


Proving undecidability of the language composed of LBAs where their language is empty

Consider the reduction that shows that LBA-emptiness is undecidable: you reduce from $\overline{A_{TM}}=\{<M,w>: M $ does not accept $w\}$.

So the reduction takes as input $<M,w>$, and outputs an LBA $T$ such that $L(T)\neq \emptyset$ iff $M$ accepts $w$.

Now, recall that an LBA is in particular a TM. So this same reduction actually outputs a TM, and actually shows that $E_{TM}$ is undecidable as well.

The reason this works is that the relationship between $E_{LBA}$ and $E_{TM}$ is such that if $M$ is an LBA, then $M\in E_{LBA}$ iff $M\in E_{TM}$. Since the reduction above always outputs an LBA, then you can just plug it in.