Quick note, I allow parametric polymorphism (System F) in this system so that S, K and I can work over all types.

Notice that without pattern matching, we can't write an if no matter what we do. We have absolutely no operations on booleans. There is no way to distinguish True from False. Instead try

true : a -> a -> a
true = \t -> \f -> t

false : a -> a -> a
false = \t -> \f -> f

Let's let Bool = a -> a -> a for clarity.

 if : Bool -> a -> a -> a
 if = \bool -> \a -> \b -> bool a b

Now it's just a matter of compiling some lambda calculus expressions to combinators, which is pretty trivial.

if : Bool -> a -> a -> a -- Or just Bool -> Bool
if    = I

true : a -> a -> a
true  = K

false : a -> a -> a
false = K I


Optimal Selection of Non-Overlapping Jobs

If you consider each task as a node of a graph, and each conflict as an edge, this is a weighted maximum independent set problem.
It is NP-hard, but you should get good results with a mixed integer programming solver, such as CBC.


Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

"Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching". Your graph is NOT a tree as it has a cycle $0, 1, 2, 0$.

Furthermore, your graph does have a perfect matching. In fact, the edges $(2,3)$ and $(0,1)$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our original graph was not a perfect matching as all the nodes were of degree 3". Plenty of graphs whose nodes are all of degree 3 have a perfect matching.


Some system is Turing complete if you can simulate every Turing machine inside of it. Powerpoint is Turing complete because its animation features can be used to simulate a Turing machine. This video explains the proof for Powerpoint. You can read the proceedings from the 2017 SIGBOVIK for a written explanation.


As stated in the question, this recognizes only context-free languages.

Lexical analysis is actually a GSM mapping, i.e. a finite state
transduction. Since CF languages are a full Abstract Family of Languages (full AFL), they are closed under
inverse GSM mapping. Hence, if the sequences of lexemes parsed by the second phase belong to a  context-free language, the original texts as a sequence of characters also belong to a
context-free language.  This 2 levels organization does not change the CF
characters of syntax, assuming the second level is indeed context-free.

One point is worth noting, though it is a minor technical issue. To
have this CF character of the second phase, it is necessary that identifiers be replaced
by a finite set of standard categories represented each by a unique
symbol. The same is true for literals such as strings or numbers. The
point is that many languages do not in principle put any limit on the
size of identifiers, or some literals, so that there is in principle an infinite number
of them. But the context free grammar of the second phase must have a
finite alphabet, like any CF grammar.  Hence the lexical elements
returned by the first phase cannot actually distinguish all
identifiers, or all literals, for the second phase.

However the information is kept by other means for the more semantical
phases of the compiling process.

It is true that any given program does have a finite number of
identifiers and literals, but the point is that we are considering the language of all possible programs.

Another point is of course that texts of compiler accepted programs do
not form a context free language as other constraints (such as
declarations of identifiers) are imposed on programs, in parallel to
the strictly syntaxic parsing process.

But, ignoring those more "semantics" constraints, some parsers also
use a variety of parsing "tricks", such as prioritization of reduction
rules to avoid ambiguities or non-determinism. As long as this is done
with a finite memory and a pushdown stack that is used only within a
fixed finite distance from its top, this does not get the syntax out
of the context-free realm. However, what extra parsing rules may exist
for the parser also have to be known to the users of the language,
thus making the understanding of the syntax more complex to users, and
giving more ground for misunderstanding. TANSTAAFL. Supposing this is
used to reduce ambiguity, it could then happen that the user will read
his program one way, while the parser reads it another way.

My own preference is for general CF parsers, that will detect
ambiguity (which is, of course, decidable for a given string of an
ambiguous language), and reject it as a programming error. But that is
much a matter of taste in design.

Including the lexical phase into the context-free syntax may possibly
make those extra rules more complex, as reasonning can no longer
isolate lexical issues fron CF syntactic ones. It can also make the
automaton underlysing the parser more complex, or call for more extra
rules. Typically, if parsing the CF part of the syntax requires a
lookahead that may include an identifier, the look-ahead becomes
unbounded when identifiers are not reduced to one symbol by a lexical
phase. Much depends also on the chosen parser generation technology.

Though there are some scannerless parsers used, I would think this applies more to languages with specific lexical and syntactic characteristics. But I am no expert on this, and the wikipedia page seems a bit weak on the general presentation side.

Finally, another interesting point, close to the initial question is
error recovery. It is used by compilers so as to be able to catch many
errors at each run, and was important when compiling was done in batch
mode, rather than interactively. Many syntactic error recovery
techniques are based on a formal model of finite state generation of
errors, such as missing or extra symbol, or local garbling of the strings
(this is also true for natural language processing). This can also be
modeled by a GSM. Hence, ignoring again semantical aspects, the larger
language of programs with syntactic errors accepted by a parser with
error correction is also context-free.

There is more in the comments, but how long should an answer be?


Why are these (lossless) compression methods of many similar png images ineffective?

Have a look at how compression algorithms work. At least those in the Lempel-Ziv family (gzip uses LZ77, zip apparently mostly does as well, and xz uses LZMA) compress somewhat locally: Similarities that lie far away from each other can not be identified.

The details differ between the methods, but the bottom line is that by the time the algorithm reaches the second image, it has already "forgotten" the beginning of the first. And so on.

You can try and manually change the parameters of the compression method; if window size (LZ77) resp. block/chunk size (later methods) are at least as large as two images, you will probably see further compression.

Note that the above only really applies if you have identical images or almost identical uncompressed images. If there are differences, compressed images may not look anything alike in memory. I don't know how the PNG compression works; you may want to check the hex representations of the images you have for shared substrings manually.

Also note that even with changed parameters and redundancy to exploit, you won't get down to the size of one image. Larger dictionaries mean larger code-word size, and even if two images are exactly identical you may have to encode the second one using multiple code-words (which point into the first).


What does flow denotes in the minimum-cost network?

Flow is an abstraction of how much "stuff" you want to move through the network. Exactly what the stuff is depends on what you're modelling with the network - water pipes, transport networks, computer networks, etc.

The problem (or something close to it) can also be used to model other problems, in which case flow could be all kinds of things.


Nondeterministic Logarithmic-space in directed graph

To show that the problem is in NL: guess a directed edge $(u,v)$ of the graph that is part of a cycle, and check (using the connectivity algorithm as a black-box, or by guessing each step of a walk) whether $v$ is connected to $u$ in $G$.

To show that the problem is NL-Hard create a new graph $G'$ as follows:

For each  vertex $v$ of $G$ add $n$ vertices $v^{(0)},\dots,v^{(n-1)}$ to $G'$.
For each edge $(u,v)$ of $G$, and for each $i=0,\dots,n-2$, add the edge $(u^{(i)}, v^{(i+1)})$ to $G'$.
For each $i=0,\dots,n-2$, add the edge $(t^{(i)}, t^{(i+1)})$ to $G'$.

It is easy to see that $G'$ is acyclic and that $s^{(0)}$ and $t^{(n-1)}$ are connected in $G'$ iff $s$ and $t$ are connected in $G$.

Now, consider the graph $G''$ obtained by adding the edge $e=(t^{(n-1)}, s^{(0)})$ to $G'$.

If $s^{(0)}$ and $t^{(n-1)}$ were connected by a path $P$ in $G'$, $G''$ contains the cycle $C = P + e$. The opposite direction is also true: if there is a cycle $C$ in $G''$ then $C$ must include $e$ and this means that of $C-e$ is a path between $s^{(0)}$ and $t^{(n-1)}$ in $G'$.


Can expected "depth" of an element and expected "height" differ significantly?

In chained hash tables with uniform hashing a similar question arises. Given a table with $n$ elements hashed into $m$ buckets, the expected number of elements per bucket is $n/m$, but what is the expected length of the longest chain?

I found a Stackoverflow question about chained hash tables. The answer by btilly argues that for fixed ratio $n/m$ the expected worst case longest chain is $\Theta(\log n/ \log\log n)$.  (Since $n/m$ is fixed, $m$ doesn't need to come into the answer.)

And the answer by templatetypedef references the following paper for a more detailed analysis:
Gaston H. Gonnet: Expected Length of the Longest Probe Sequence in Hash Code Searching.
J. ACM_ 28(2):289-304, 1981.
[Free techreport version at University of Waterloo]

Slightly more generally I found a math.stackexchange question about the balls and bins problem.  The answer by Yuval Filmus cites the following paper, which gives even tighter bounds:
Martin Raab; Angelika Steger: Balls into Bins - A Simple and Tight Analysis. 2nd Intl Wkshp on Randomization and Approximation Techniques in Computer Science, pp. 159-170, 1998.

Finally, there is apparently a branch of statistics called extreme value theory culminating in the Fisher-Tippett-Gnedenko theorem, which, I think, gives expected maxima for a huge variety of distributions.


How can we use the FPTAS for problem B to solve problem A

You need a stronger guarantee on the reduction, that it be approximation preserving. Not all reductions are approximation preserving. An extreme example is given by Min Vertex Cover and Max Independent Set. The complement of a vertex cover is an independent set, and so there are simple NP-hardness reductions between these problems. However, while Min Vertex Cover has a 2-approximation algorithm, Max Independent Set cannot be approximated to within $n^{1-\epsilon}$ for any $\epsilon > 0$ unless $\mathsf{P=NP}$.


Minimal basis for set of binary vectors using XOR

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)


What is the relation between syntax and type theory?

The division line between syntax and additional type checking can indeed be blurred, if so desired, but usually we make a distinction as follows:

the syntax is described using a formal grammar, preferrably one that is not very complex, such as a context-free gramar, or one that is even simpler than that.
the typing rules are described using inference rules whose complexity tyically exceeds that of a context-free formal grammar.

In general, a programming language might stratify the task of getting from the source code to the compiled code as follows:

Parsing converts the input string to an abstract syntax which represents the input as a tree.
Elaboration performs certain simple transformation of input syntax, such as getting rid of syntactic sugar.
Type-checking and inference verifies that the program is well-typed, thereby guaranteeing that later stages will not get stuck. It may also augment the input source with extra information about types.
Several phases of compilation may follow, each translating from its input to a simpler language. The final language may be machine code, or byte code, or in general some intermediate code.
The program is executed.

While you may consider merging some of these phases together, and sometimes that is a good idea, it is in general better to keep them separate. From a conceptual point of view parsing is very different from type checking. After all, these two phases serve different purposes: one is just a translation from strings to trees, while the other one statically analyzes the structure of the program in order to detect possible errors and to aid further compilation.

An example of merging different phases is "just in time" compilation: we run a program in an "interpreted" mode so that there is no delay because of compilation, and at the same time we perform on-the-fly compilation of those parts of the code in which the program is spending most of the time. I believe some browsers do that with Javascript.


Algorithm to generate self-avoiding random walk on a lattice

A procedure is described in A combinatorial algorithm for effective generation of long maximally compact lattice chains.


Are co-semidecidable languages separated by decidable ones?

This is a classical exercise in computability.
Since $A,B\in coRE$, there exist TMs $M,N$ that recognize $\overline{A}$ and $\overline{B}$ respectively.

Consider the following TM $K$:
Given a word $w$, run in parallel $M$ and $N$ on $w$. That is, simulate $M$ for a single step, and then $N$ for a single step, and repeat.

If $M$ accepts at any point, reject.
If $N$ accepts at any point, accept.
(if both accept, reject, so we first check $M$ for acceptance).

Define $C=L(K)$.

If $A\cap B=\emptyset$, then $\overline{A}\cup\overline{B}=\Sigma^*$, so either $M$ or $N$ eventually accepts, so $K$ always halts. Thus, $C$ is decidable.

We claim that $C$ satisfies the requirements: if $x\in A$, then $M$ never accepts $x$, so $N$ accepts $x$, so $K$ accepts, so $x\in C$. Thus, $A\subseteq C$.

If, by way of contradiction, $x\in B\cap C$, then $K$ accepts $x$, which means $N$ accepts $x$, so $x\notin B$ - contradiction. So $B\cap C=\emptyset$.

We conclude that $C$ satisfies the requirements.


Analysis of and references for Koch-snowflake-like (and other exotic) network topologies

Not really a straight answer, but I don't have the ability to comment yet. I think you are confusing the Koch snowflake with the Sierpinski gasket/triangle. A Koch topology would just be equivalent to a path. The Sierpinski triangle has the properties you describe.

A quick google shows a wealth of papers and webpages on Sierpinski networks, although there is little agreement on the exact topology.


Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

Yes. Since the complement of a regular language is also a regular language, then it follows that the complement of a non-regular language must also be non-regular. Strictly speaking, this works since the complement is its own inverse.


Finding libraries of formalized mathematics

Metamath has a HUGE chapter-organized archive of formal theorems:

http://us.metamath.org/mpeuni/mmtheorems.html

Besides that, Freek Wiedijk's QED manifesto is always a good starter for future formalizers. And his list of top 100 formalized theorem is an ever-encouraging source of formalized ideas:

http://www.cs.ru.nl/~freek/100/

At the end of that page, he provides another list of desired but-still-missing formalized theorems. The one that I personally desire, is $\mathrm{IP=PSPACE}$.


Measures of performance in machine learning

Precision and recall are the two basic measures and most of the other measures can be written in terms of them. If a model has both better precision and better recall, then it can be seen as strictly better than another model. If two models are incomparable in the sense that another has better precision and another has better recall, then it depends on the application which one is better. For some applications it is essential to avoid false positives, and for some applications it is essential to avoid false negatives.


Binary Indexed Trees: Why does i & -i work?

Assuming that your tree is storing cumulative sums, one query you would like to make is "what is the cumulative sum to index n".  Suppose the tree is as shown in the OP, and n is 5.  The answer to the question would be found by adding the sum in node 4 and the sum in node 5.  This is because each node is storing the cumulative sum of itself plus its left subtree (if any).  Thus, node 4 has the cumulative sum of indices 1-4 and node 5 has the cumulative sum of index 5 (just itself).  Because of the way the tree is built, you basically need to visit one node for each 1 bit in the binary representation of your index.

So the algorithm to compute the cumulative sum is to start at the given index, in this case 5.  Note that 5 is 101 in binary.  Add its sum to the total.  Then, to get to the next node needed, we want to remove the least significant bit (we want to get from 101 to 100).  The least significant bit of i is i & -i.  To remove the least significant bit, i -= (i & -i).  That gets us to node 4.  We add node 4's sum to the total.  Then we remove the next significant bit, leaving 0 which means we are at the end.

If the tree were bigger, and the starting index were 50 (which is 110010 in binary), we'd have to visit node 50 (110010), node 48 (110000), and node 32 (100000).  In this example, node 32 contains the sums of 1-32, node 48 has the sums of 33-48, and node 50 has the sums of 49-50.


How do confluently persistent data structures handle merge conflicts?

Typically, confluently persistent data structures are built so that they will never have a merge conflict.  The details differ for each such data structure, but here are the broad outlines.  Basically, you define a semantics for what you want to happen during a merge, then devise a data structure with those semantics.  (The desired semantics depends on the kind of data stored in the data structure; there's no single answer.)

So what's a merge conflict?  A merge conflict arises when your semantics for the merge throws up its hands and says "I don't know what to do".  But normally, when we design confluently persistent data structures, we typically define merge semantics where that will never happen.  In other words, the semantics are well-defined for all possible cases.   Merge conflicts are only necessary when there are situations where the semantics aren't well-defined.

Why does git have merge conflicts?  Because it is a general-purpose tool used to store arbitrary data with unknown meaning/semantics.  Therefore, we can't know what the "right" semantics for merging is, in general.  But confluently data structures are typically designed for a narrower, more specific purpose.  Think, for instance, of a set; that has a well-defined semantics, and we can define a merge operator that fully specifies what the result of merging two sets should be for all possible cases.  So, it's feasible to define merge semantics that are well-defined for all possible cases, when the data structure handles such a specific, well-defined kind of data. Git has to deal with a harder problem, where it might not be possible to define a useful, sensible merge operator that is defined for all possible cases.


How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

Work In progress.
Feel free to contribute filling up the arguments that are incomplete.

Definitions:
Before proving anything we need to make it precise what is it what we are trying to prove.

Planar graph: A graph that can be embedded in $\mathbb{R}^2$.(1)
Plane graph: A planar graph together with a particular embedding $G\hookrightarrow\mathbb{R}^2$. I will call a plane graph just by the name $G$ of the graph itself. We call faces of a plane graph to the connected components of the complement $\mathbb{R}^2\setminus G$. We can also assume the plane graph embedded in the two dimensional sphere $S^2$. That way we don't need to distinguish one of the faces which will be unbounded in the plane.
Polygon: A simple closed path in a graph without a proper closed subpath.
Cut-set: A minimal set of edges of a graph that, if removed, would increase the number of connected components of the graph.
Combinatorial dual: A graph $G^*$ is said to be a combinatorial dual (sometimes also called algebraic dual) of another graph $G$ if there is a bijection between their edges such that the polygons of one of them correspond to the cut-sets of the other, and vice versa. A graph can have no combinatorial duals, or it can have multiple non-isomorphic combinatorial duals.
Geometric dual: A geometric dual $G^*$ of a plane graph $G$ is a graph obtained by placing a vertex on each face of $G$. There is going to be an edge of $G^*$ for each triple $(f_1,f_2,e)$ where $f_1,f_2$ are faces of $G$ such that their closures contain the edge $e$ of $G$. The edge corresponding to this triple will be embedded in such a ways that it connects the vertices of $G^*$ inside $f_1$ and $f_2$. It will be contained in $f_1\cup f_2\cup e$ and intersects $e$ only at one point that it is not a vertex of $G$. For this definition to make sense a couple of results from topology are needed. In particular, two results that are quite intuitive, but very hard to prove. These are Jordan curve theorem and Jordan-Shoenflies theorem. Using these results it can also be proven that the geometric duals of a plane graph are isomorphic. So, we can talk about the geometric dual of a plane graph.

It is a theorem of Whitney that a graph is planar if and only if it has a combinatorial dual. Moreover, each combinatorial dual of a planar graph arises as a geometric dual of an embedding of the graph in the plane.

$G^{**}=G$
As you see above, this statement can mean different things. It could mean that $G$ is a connected plane graph and we are taking geometric dual a couple of times. It could also mean that $G$ is a planar graph and we are taking geometric dual a couple of times after fixing an embedding. Finally it could mean that we are taking combinatorial dual a couple of times of a connected planar graph.
Note: We also need to use the modern definition of connected in which the empty graph $0$ is not connected. Note that the dual of the empty graph is $K_1$ and the dual of $K_1$ is itself. So, $0^{**}=K_1\not\cong 0$. I am making the clarification because although it is becoming more widespread defining the empty graph as not connected, still not everyone does that.

Geometric double dual.
I think this one is the simplest, assuming that we leave the topological results as known.
Assume that $G$ is a plane graph and $G^*$ is its geometric dual. We assume $G^*$ to be a plane graph, which embedding satisfies the properties that we mentioned in the definition above. Let's do induction.
If $G=K_1$ we have that $G^*=K_1$, just another point of the plane, and therefore $G^{**}\cong G$. Then $G^{**}\cong G$.
We want to assume that the theorem is true for all graphs that have smaller number of vertices or edges than $G$. The following two lemmas allow use to construct the isomorphism by removing vertices of $G$ of degree $1$ or edges that are not cut edges. Then we just extend or modify the isomorphism that we have from the inductive assumption on the smaller graph. The lemmas below are quite intuitive, but they make use of Jordan's curve theorem. So, the main annoying thing to write down the arguments is to make it as explicit as possible the point in which this big theorem is used.
Lemma 1: Assume $G$ is connected plane graph with an edge $e$ that is not a cut edge of $G$. Assume that $(G\setminus e)^{**}\cong G\setminus e$. Then $G^{**}\cong G$.
Proof: Since $e$ is not a cut edge, the two faces2 of $G$ incident with $e$ are different. Call those faces $f_1$ and $f_2$. Deleting $e$ from $G$ fuses $f_1$ and $f_2$ into a single face $f$. Faces of $G$ that are adjacent to $f_1$ or $f_2$ become adjacent to $f$ in $G\setminus e$. In the dual, the vertices $f_1^*$ and $f_2^*$ of $G^*$ get replaced by a single vertex $f^*$ of $(G\setminus e)^*$. Any vertex of $G^*$ that is adjacent to $f_1^*$ or $f_2^*$ is adjacent to $(G\setminus e)^*$. Therefore, the function sending $f^*$ to the identification of $f_1^*$ and $f_2^*$ in $G^*/e^*$ and that is the identity on all other vertices is an isomorphism. ... $\square$
Lemma 2: Assume that $G$ is a plane graph that has a vertex $v$ of degree $1$ and that $(G\setminus v)^{**}\cong G\setminus v$. Then $G^{**}\cong G$.
Proof: Since $v$ has degree $1$, then it is adjacent to only one face $f$ of $G$. If $e$ is the edge of $G$ incident on $v$ and $f^*$ is the vertex in $G^*$ that is in $f$, then there is a loop $e^*$ incident on $f^*$ that contains in its interior $v$ and no other vertex of $G$. Here we are implicitly using Jordan's curve theorem. By assumption $(G\setminus v)^{**}\cong G\setminus v$. By jordan's curve theorem the interior of $e^*$ is a face $v^*$ of $G^*$ and this face is adjacent to exactly another face. Therefore, extending the isomorphism of $(G\setminus v)^{**}$ and $G\setminus v$ by sending $v$ to $v^*$ and $v^*$ to $v$ give us an isomorphism of $G^{**}$ and $G$. ... $\square$
To complete the induction observe that we can apply Lemma 1, if the graph has some non cut-edge. If $G$ has no non cut-edges, then it must be a tree. So, we can apply Lemma 2, as long as $G$ has more than one vertex. If it is a tree and has one vertex, then it is $K_1$, which is the base case.

Combinatorial double dual
For this we use Whitney's theorem. If $G$ is a connected planar graph and $G^*$ a combinatorial dual, then there is an embedding of $G$ and $G^{*}$ such that $G^*$ is the
geometric dual of $G$. From the proof above it follows that $G$ is a geometric dual of $G^*$ and therefore a combinatorial dual of $G^*$. Now assume that $G^{**}$ is a combinatorial dual of $G^*$. Consider an embedding of $G^*$ and $G^{**}$ such that $G^{**}$ is a geometric dual of $G^*$. Using Jordan-Shoenflies theorem we can extend ... [This one seems harder. I don't have a complete plan yet. We probably need to extend the new embedding of $G^{*}$ (in which $G^{**}$ is a geometric dual) to embed also $G$ and show that it is also a geometric dual of $G^{*}$ in this embedding.]
Footnotes:

The topology on the graph is that of a CW-complex.
There are at most two faces incident on an edge. This follows from Jordan-Shoenflies theorem.


Cover interval with minimum sum intervals - DP recursion depth problem

You can always convert any recursive algorithm (that uses the call stack) into a iterative algorithm where you explicitly push and pop onto a stack that you manage.  This should eliminate recursion depth exceeded errors.


Optimal upper bound on the number of states in the complement of an NFA

In the paper State Complexity of Concatenation and
Complementation of Regular Languages by Jirásek, Jirásková, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of
$n$ states such that any NFA for the complement of the language $L(M)$ needs at
least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.


algorithm time analysis "input size" vs "input elements"

In the most formal sense, the size of the input is measured in reference to a Turing Machine implementation of the algorithm, and it is the number of alphabet symbols needed to encode the input.

This is of course rather abstract, and is very difficult to work with in practice, or at least very annoying - we would need to consider how we're going specify delimeters etc. etc. What happens normally in practice then is that we look for a proxy measurement of the size of the input - something more convenient and accessible, but that does not cause any mathematical problems in our analysis.

Using your "abcde" example, it would normally be the case that the alphabet we use for the input is small, so even using the proxy measurement of $5$ characters, we known that even on a Turing Machine, we can, if we bothered, specify an input encoding that would convert "abcde" to some encoded form that had length at most $5\times c$ for some constant $c$. This expansion by a constant would typically make no difference in our asymptotic analysis, as we routinely discard constant factors.

In a different case, we often measure the size of an input graph by the number of vertices $n$. Clearly if we want to specify arbitrarily large graphs, the size of the encoded input is not simply $n$ - what happened to the edges, for example? What we do know is that we can use a reasonable encoding scheme that represents the graph in $N = c\cdot n^{2}\log n$ bits. This is a bit more of an expansion than constant, but in a lot of interesting cases, we're only dealing with things at a granularity of polynomials, and polynomials compose nicely in a lot of ways - in particular, as an example, if we determine that our running time is $O(p(n))$ where $p$ is a polynomial, then we know that there is some polynomial $p'$ such that $O(p(n)) = O(p'(N))$, so when we move back to the formal measure of the input, we're still in polynomial time.

A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n = O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^{n})$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

So while there's no stated rule for picking a proxy measure for the input size, the requirement is that the expansion or contraction of the proxy size compared to the input size should be compatible with what you're trying to prove. As a rule of thumb, constant factor changes almost never matter, small polynomial factors are normally fine and work for most of the basic theory that you see, large polynomial factors might still work in for theory, but can be a nasty surprise in practice, and exponential amounts of change are normally way too extreme.


Richard Karp's 21 NP-Hard problems, the meaning of his research?

The short way to say it is that these problems are $\mathcal{NP}$-complete.

Of course this only has meaning to those who understand what $\mathcal{NP}$-complete means.

Not only does this say these problems are all somehow equivalent (polynomial-time equivalent to be marginally more precise), but that you can use them to solve any problem in $\mathcal{NP}$, not just each other, with only a polynomial blow-up in the time cost. This immediately gives us that if any of them have a polynomial-time algorithm, then everything in $\mathcal{NP}$ does, and hence we would have $\mathcal{P} = \mathcal{NP}$ (summed up in Theorem 3 from the paper).

To see what Karp's paper in particular represents however, we have to pay attention to a touch of history (not all that usual for most computer scientists I know, but bear with me ;) ). This paper was published in 1972, it was only the year before that Cook proved that $\mathsf{Satisfiability}$ was $\mathcal{NP}$-complete , this was the first "natural" problem proven $\mathcal{NP}$-complete1, but Cook doesn't mention $\mathcal{NP}$, let alone $\mathcal{NP}$-completeness (and he used a weaker type of reduction than Karp, but that's another story). So what you see in Karp's paper is the first codification some of the ideas that have formed one of the central parts of complexity theory, not only does he get these ideas out into the literature, he also says "hey, there's a lot of problems that we're interested that are $\mathcal{NP}$-complete".

So in one go, he coherently defines $\mathcal{NP}$-completeness, shows what it means for solving problems efficiently2, and gives a bunch of (interesting) problems that are $\mathcal{NP}$-complete.

In some sense it is the founding document of complexity theory. It took a lot of ideas that were starting to gain currency, and put them together in a (relatively3) clear statement of how all this complexity stuff can work.

Footnotes

The definition of $\mathcal{NP}$ almost immediately gives complete problems - anything along the lines of "Does this non-deterministic Turing Machine halt in a polynomial number of steps?" or similar, but these are not the most interesting problems in the world (to most people).
Using Edmonds' idea of deterministic polynomial-time as a working definition of "efficient".
Though the reductions are fairly cursor and opaque by modern standards. On the other hand, he crams 21 in there.


Physical layer services & hardware protocols

Just a quick answer:

Hardware protocols are at the lowest level of the Open System Interconnection (OSI) model and are usually a mix of

hardware specifications (cables, connectors,  signals, ...)
how data is exchanged between the hardware devices (start of communication, end of communication, data exchange, flow of control, timings, error handling, ...)

Typical examples of hardware protocols are: serial port RS-232, Parallel port IEEE 1284, USB , Ethernet, bus protocols, ...

Physical layer services are those functions used to correctly implement and manage the communication between devices at the physical layer: e.g. open a port, convert bits to timed signals, change the bit-rate, close a port, send data, multiplexing, flush data,  ...


For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

Either you mixed up two algorithms or you misinterpreted an upper bound. One level of a BFS with priority queue is enough, but during this one round a neighbor of the root may be updated $|V|-1$ times, therefore the update operation needs to be efficient.


Number of processes needed to maximize CPU utilization under I/O wait conditions

You want all processes to fit in memory. If there are $N$ processes, then together with the OS they take up $256+128N$ megabytes. Since there is only room for $2048$ megabytes, we need $256+128N \leq 2048$. Dividing by $128$, this is $N+2 \leq 16$.


TRNG by hamming distance of processor tics

You are talking about using the relative jitter of 2 timers to source entropy.

That is indeed an option for entropy generation.

However in terms of cryptographically secure RNGs (the reason you would go to such length to create randomness) this jitter can be influenced by the load on the processor and electrical noise. This provides a side channel to try and influence or predict the entropy used for the generator.


Parity check and magnitude comparison in Residue Number Systems

The "parity check" of a number $X$ is 0 or 1 according to whether $X$ is even or odd.  In other words, the parity of $X$ is $X \bmod 2$.  We are assuming that you have a way to compute the parity of $X$, from the RNS representation of $X$.  Let $p(X)$ denote the parity of $X$, i.e., $p(X) = X \bmod 2$.

Now let's suppose $X,Y$ are integers in $[0,M-1]$ that we have stored in RNS representation, and let's look at what happens when we subtract the RNS representations.  If $X$ is represented as $(x_1,\dots,x_t)$ and $Y$ is represented as $(y_1,\dots,y_t)$, the result of the subtraction operation will be the RNS representation $(z_1,\dots,z_t)$ where $z_i = x_i-y_i \bmod m_i$.

What number $Z$ is $(z_1,\dots,z_t)$ the representation of?  Well, if $X\ge Y$, then $Z$ will be $X-Y$.  But -- and here is the key point -- if $X<Y$, then $Z$ will not be $X-Y$, as $X-Y$ is negative and RNS can only represent numbers in the range $[0,M-1]$.  Instead, what will happen is that we'll have $Z \equiv X-Y \pmod M$.  Therefore, if $X<Y$, we'll have $Z = X-Y+M$... which is not the same as $X-Y$.

If $X\ge Y$, then $X-Y \ge 0$ and we say that the subtraction $X-Y$ doesn't underflow; in this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ modulo 2.  In other words, if $X \ge Y$, we will have $Z=X-Y$ and therefore using the properties of modulo-2 arithmetic we have

$$p(Z) = p(X-Y) \equiv X-Y \equiv p(X)-p(Y) \pmod 2.$$

In contrast, if $X < Y$, then $X-Y < 0$ and we say that the subtraction $X-Y$ underflows.  In this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ plus 1 modulo 2.  In other words, if $X<Y$, we will have $Z=X-Y+M$ and therefore

$$p(Z) = p(X-Y+M) \equiv X-Y+M \equiv p(X)-p(Y)+1 \pmod 2.$$

Here I have used the fact that $M$ will always be odd, so $p(M)=1$.

This gives you a way to check whether $X\le Y$, given RNS representations for $X,Y$: you subtract them to get a RNS representation of some integer $Z$, and then test whether $p(Z) \stackrel{?}{\equiv} p(X)-p(Y) \pmod 2$.

The key observation is that "subtraction" of RNS representations is not actually computing the subtraction (of integers).   Rather, it is computing the subtraction modulo $M$.  If the result of the subtraction is in the range $[0,M-1]$, that's equivalent to subtraction in the integers.  But if subtraction underflows, it's different.

This might look mysterious, but it's not as unfamiliar as it might feel.  If you use twos-complement arithmetic on 32-bit integers, that is basically doing modulo $2^{32}$ arithmetic: addition of 32-bit ints is not actually addition (of integers), but addition modulo $2^{32}$.  In other words, with twos-complement addition of 32-bit integers, the results of arithmetic operations "wrap around" modulo $2^{32}$.  RNS is just like that, except that it "wraps around" modulo $M$ instead of modulo $2^{32}$.

"parity is off" means "parity is wrong", i.e., the parity doesn't match what you'd expect to get, if subtraction of RNS representations behaved like subtraction of integers.


left/right derivations of grammars and parse trees

A non-terminal is something with a production rule. You're correct that words aren't non-terminals. They are terminal precisely because there is no production which expands the word.
In a leftmost derivation, every step must expand the leftmost non-terminal. The leftmost non-terminal is the non-terminal which is closest to the left :-). In $\text{the N V NP}$ , the leftmost non-terminal is $\text{N}$. So if you choose a derivation step which expands $\text{NP}$, that's not a leftmost derivation.
In a parse tree, the root is whatever the root of the grammar is ($\text{S}$ in this case) and each node has as its children the symbols on the right-hand side of the production which is used the expand that particular non-terminal. Terminals are leaf nodes; they have no children.


Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).

In case your TMs are only defined as acceptors (i.e., a word not in the language will not necessarily be explicitly rejected, just not accepted), things are a bit more complex. In fact, we must then require more of $f$, namely that it is space-constructible; that is, given $n$ (unary encoded), we should be able to compute $f(n)$ (binary encoded) in space not greater than the value $f(n)$ itself. This property holds for practically all "standard" functions you know.

If that is the case, then, given a TM $A$ which accepts a language in space bounded by $f$, we proceed as follows:

Compute $f(n)$ (using $f(n)$ space).
Initialize a counter with the value $f(n)$. This counter need not use more space than what was already used in step 1; for example, we store it in a separate track of the TM tape.
Simulate $A$. For every step $A$ takes, decrement the counter. If the counter reaches zero, then enter the reject state (or loop without ever accepting).

This takes at most $f(n)$ space in steps 1 and 3 (and we reuse the tape in step 3), while step 2 does not take any additional space at all since representing the counter uses space on the order of $\log f(n)$, which is smaller than $f(n)$ (which is necessarily an integer), and we use a separate track for it.


Description logics with decision problems within NP

Can see here https://www.w3.org/TR/owl2-profiles/#Computational_Properties  for OWL-EL, OWL-QL and OWL-RL


Efficient algorithm for edit distance for short sequences

One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here).  Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\le D$ from $x$.  Thus, you can test whether a string is close to $x$ in $O(n)$ time, where $n$ is the length of the string.  I'm not sure what the space requirements are to store the DFA (they are linear in $m,n$, but might be exponential in $D$).

Alternatively, you could use an "early-out" algorithm for computing the edit distance.  You mentioned that you are only interested in the edit distance if it is less than some threshold $D$.  There is an "early-out" algorithm for computing the edit distance whose running time is $O(\max(n,m) \times D)$, which computes the edit distance if it is $\le D$ or else outputs "too big" if it is $>D$.  Basically, you do the standard dynamic programming algorithm for the edit distance, but only compute the elements of the matrix that are $\le D$ away from the diagonal.  In your case this might or might not be better than the other alternatives.


Loop-invariant code motion with unsafe operations

This kind of optimization is more difficult than typical data-flow based transformations, because you need to actually change the branching structure of the control flow graph.

You need something more than SSA (or something more than the dataflow graph you get from reaching definitions.)  That "something" is the control dependence graph (which relies on the same (post)dominator analysis that you use to construct the SSA graph.  (Google for "program dependence graph" (which is the combination of the control-dependence graph and the SSA data-flow graph).)  Loop invariants (including loop invariant conditionals) are "obvious" in the program dependence graph.  A loop invariant is any node all of whose data and control dependences come from outside the loop.

Unfortunately, in the general case, rebuilding a control-flow graph from the program-dependence graph is somewhat involved.  (Google for "percolation scheduling" and "gated SSA form" if you are interested.  Also (self promotion) my dissertation gives a (terse) overview of a method for converting from PDG back to CFG.)  You can, luckily, do something substantially simpler if you are willing to restrict your transformation to specific structured control flow (in your case, an if-else block inside a do-while block.)  This is the same simplification that loop unswitching makes.

So working through the steps.  First convert while and for loops to if-do-while

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then (as with loop unswitching) you see that a != 0 is loop invariant, so the if statement is loop invariant, so any statements inside the if block that are loop invariant (c = 5/a) can be moved out of the loop (along with the conditional that protects those statements.)  Essentially what you are doing is breaking each invariant conditional block into the parts that are and are not loop invariant:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then you can move the entirety of the blocks that are completely loop-invariant out of the loop:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  if (a != 0):
    c = 5 / a
  do:
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)


Assigning a unique representation to equivalent circular queues

Enumerate all possible rotations of the queue.  Take the lexicographically first of them.  Use this as your representative.  If you want a short index into a hash table, take the hash of that.  Then any two equivalent queues will get the same representative / same index.

If the queue has $n$ items, implementing this naively takes $O(n^2)$ time.  However, it can be done more efficiently.  When the contents of the queue are random, sorting the rotations lexicographically, using a string comparison operator that only compares as much of a prefix as necessary to find the first mismatch, will have running time $O(n \log^2 n)$.  If you want to get more fancy, you can do it in $O(n)$ time, using a suffix tree or suffix array; though the constant factors and implementation complexity probably won't make this worthwhile unless your queues are extremely large.


Are there established complexity classes with real numbers?

The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes.

Some interesting problems in this domain are the classes $P_R$, $NP_R$, and of course the question of whether $P_R$ = $NP_R$. By $P_R$ we mean the problem is polynomially decidable, $NP_R$ is the problem is polynomially verifiable. There are hardness/completeness questions about the class $NP_R$. An example of an $NP_R$ complete problem is the the problem of $QPS$, Quadratic Polynomial System, where the input is real polynomials in $m$ variables, and $p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$ of degree at most 2, and each polynomial has at most 3 variables. The question whether there is a common real solution  $R^n$, such that $p_1(a), p_2(a), ... p_n(a) = 0$. This is an $NP_R$ complete problem.

But more interestingly there has been some work on the relationship between $PCP$,(Probalistically Checkable Proofs), over the Reals, ie the class $PCP_R$, and how it relates to the algebraic computation models. The BSS model pans to all of $NP$ over reals. This is standard in literature, and what we know today is that $NP_R$ has "transparent long proofs", and "transparent short proofs". By "transparent long proofs" the following is implied: $NP_R$ is contained in $PCP_R(poly, O(1))$. There is also an extension which says, the the  "Almost (approximated) Short Version" is true too. Can we stabilize the proof and detect faults by inspecting considerably less many (real) components than $n$? This leads to questions about existence of zeros for (system of) univariate polynomials given by straight line program. Also, by "transparent long proofs" we mean

"transparent" - Only, $O(1)$ to be read,
long - superpolynomial number of real components.

The proof is tied to $3SAT$, and sure one way to look at real valued problems is how it might be related to Subset Sum - even approximation algorithms for the real valued problems would be interesting -as for optimization - Linear Programming we know is in the class $FP$,but yes it would be interesting to see how approximatability might impact the completeness/ hardness for the case of $NP_R$ problems. Also, another question would be the $NP_R$ $=$ $co\text{-}NP_R$?

While thinking of the class $NP_R$, there are counting classes also defined to allow for reasoning about polynomial arithmetic. While $\#P$ is the class of functions $f$ defined over $\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$ for which there exists a polynomial time Turing machine $M$ and a polynomial $p$ with the property that $\forall n $$\in$$ \mathbb{N}$, and $x$$\in$$\{0,1\}^{n}$, $f(x)$ counts the number of strings $y \in$$\{0,1\}^{p(n)}$that the Turing Machine $M$ accepts $\{x,y\}$. For reals we  extend this idea there are additive BSS machines - BSS machines that do only addition, and multiplications (no divisions, no subtractions). With additive BSS machines(nodes in computation only allow addition, and multiplication) the model for $\# P$ becomes one in which the count is over the vectors that the additive BSS  machines accepts. So, the counting class is $\#P_{add}$ this class is useful in the study of Betti numbers, and also the Euler characteristic.


Huffman's algorithm is actually an "algorithm scheme", that is, a specification for an entire class of algorithms. Roughly speaking, Huffman's algorithm is any instantiation of the following scheme:

  While there is more than one symbol, choose (in an unspecified way) two leaves of minimum total probability, and merge then (in an unspecified order).

Any particular instantiation will include a tie-breaking rule for choosing the two leaves, and will order them in some specific way.

In your case, there is only one choice for the two leaves, but there are several choices for the order (two at each of the three iterations of the algorithm). Hence your distribution supports 8 different "Huffman codes". It might be that the one you chose is not the canonical one which is produced by the specific implementation you were taught in class. The 8 Huffman codes for your distribution are:
$$
\begin{array}{c|l|l|l|l|l|l|l|l}
A & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001 \\\hline
B & 10 & 10 & 11 & 11 & 00 & 00 & 01 & 01\\\hline
C & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\hline
D & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\
\end{array}
$$

An important fact to be aware of is that not while Huffman's algorithm is guaranteed to produce a minimum redundancy code, not all minimum redundancy codes can be produced by Huffman's algorithm. See Gallager's classic paper Variations on a Theme by Huffman.


How to prove transitivity in small-o of asymptotic analysis?

Comment on your proof:
You write
"Let $c = {c_1}^2$." Strictly speaking, this doesn't make sense, since you haven't set $c_1$ to any value yet at this point. To be formally correct, you need to start with some given $c$, and then set $c_1$ to $\sqrt{c}$ and proceed from there (which is what I've done below where $\epsilon = c$).

To show that $f(n) \in o(h(n))$, you need to show that $\lim_{n\rightarrow\infty}\frac{f(n)}{h(n)}=0$. Or, in other words, for any constant $\epsilon$, there exists $N>0$ such that
$$
\forall n \geq N\colon |f(n)| \leq \epsilon|h(n)|. \qquad \text{(A)}
$$
Before proving (A), let's write out our assumptions explicitly:
Since we have assumed $f(n) \in o(g(n))$, we know that for any $\epsilon$, there exists an $N_f$ such that
$$\forall n \geq N_f\colon |f(n)| \leq \epsilon |g(n)|. \qquad\text{(1)}$$
Analogously, by $g(n) \in o(h(n))$, we know that there is $N_g$ such that
$$
\forall n \geq N_g\colon |g(n)| \leq \epsilon |h(n)|, \quad\text{(2)}
$$
for any given $\epsilon$.

Proof of (A): Suppose we are given some $\epsilon$. Let $$N = \max\left(N_f(\sqrt{\epsilon}),N_g(\sqrt{\epsilon})\right),$$
where $N_f(\sqrt{\epsilon})$ and $N_g(\sqrt{\epsilon})$ are constants that make (1) and (2) true for $\sqrt{\epsilon}$.
It follows that
$$
\sqrt{\epsilon} > \frac{|g(n)|}{|h(n)|} > \frac{(1/\sqrt{\epsilon})|f(n)|}{|h(n)|},
$$
and therefore $|f(n)| \leq \epsilon |h(n)|$, as required.


Complex property of sparse horner polynomials by induction

You need to use induction on some complexity measure $\mu(x,y)$ (on some well-ordered domain) which has the following property:

  When running the addition procedure on $x,y$, all recursive calls are on pairs $z,w$ for which $\mu(z,w) < \mu(x,y)$.

A complexity measure satisfying this property shows that the addition procedure terminates, and will also allow you to do a proof by induction. Note that you are not splitting into cases according to the coarse structure of $x,y$.

It is often the case that you can take $\mu(x,y)$ to be the total description length of $x,y$, so you might start by checking whether this works here. Another possibility is to take the sum of the total degrees of all monomials in $x,y$.

Finally, how should you approach the problem? I suggest forgetting about the formalism (in particular, ignoring POP completely) and writing out the simplification steps in their barest forms. Using $N(p,q)$ for the normal form of $p+q$ (themselves already in normal form), the rules are:

$N(c_1,c_2) = c_1+c_2$.
$N(c,x_i^jp+q) = x_i^jp+N(c,q)$.
$N(x_i^{j_1}p_1+q_1,x_i^{j_2}p_2+q_2) = x_i^{j_2}N(x_i^{j_1-j_2}p_1+0,p_2)+N(q_1,q_2)$, where $j_1 > j_2$.
$N(x_i^jp_1+q_1,x_i^jp_2+q_2) = x_i^jN(p_1,p_2)+N(q_1,q_2)$.
$N(x_{i_1}^{j_1}p_1+q_1,x_{i_2}^{j_2}p_2+q_2) = x_{i_1}^{j_1}p_1+N(q_1,x_{i_2}^{j_2}p_2+q_2)$, where $i_1 < i_2$.

Here we are conflating POP and POW, which makes things a littler more concrete.

We want to prove that these rules are correct, namely:

  If $p,q$ are in normal form then $N(p,q)$ terminates, is in normal form, and agrees as a function with $p+q$.

This can be split into several tasks. First, assuming that $p,q$ are in normal form, show that they match exactly one rule. Second, show that in each recursive invocation $N(r,s)$ on the right-hand side, (i) $\mu(r,s) < \mu(p,q)$, and (ii) $r,s$ are in normal form. Third, show that the right-hand side agrees with $p+q$ as a polynomials (using the inductive hypothesis). Fourth, show that the right-hand side is in normal form (again using the inductive hypothesis).

Proving that the addition procedure as given is valid is similar, only we need to take into account the different encoding which separates POW and POP.


Regex for at least three 1's and at most four 0's

Here is a solution for at least $a$ 1’s and at most $b$ 0’s:
$$
\sum_{a_0+\cdots+a_b=a} 1^{a_0}1^*\prod_{i=1}^b (\epsilon+0)1^{a_i}1^*,
$$
where $a_0,\ldots,a_b \geq 0$ are integers. For example, when $a=b=2$ we get
$$
\begin{align*}
&111^*(\epsilon+0)1^*(\epsilon+0)1^*+\\
&1^*(\epsilon+0)111^*(\epsilon+0)1^*+\\
&1^*(\epsilon+0)1^*(\epsilon+0)111^*+\\
&11^*(\epsilon+0)11^*(\epsilon+0)1^*+\\
&11^*(\epsilon+0)1^*(\epsilon+0)11^*+\\
&1^*(\epsilon+0)11^*(\epsilon+0)11^*.
\end{align*}
$$
With more effort, you can even create an unambiguous regular expression, that is, one which corresponds to a UFA rather than an NFA; in other words, whenever there is a sum, the corresponding languages are disjoint. As an example, here is an unambiguous regular expression corresponding to $a=b=1$:
$$
1^*+11^*01^*+011^*.
$$
Compare this to the ambiguous one constructed above:
$$
11^*(\epsilon+0)1^*+1^*(\epsilon+0)11^*.
$$
The words $1,101$ are both captured in both summands above, but in only a single summand in the unambiguous regular expression.


Quicksort Partitioning: Hoare vs. Lomuto

Pedagogical Dimension

Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:

  “Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”

Performance Dimension

For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.

As shown below, the algorithms behave very similar on random permutations except for the number of swaps. There Lomuto needs thrice as many as Hoare!

Number of Comparisons

Both methods can be implemented using $n-1$ comparisons to partition an array of length $n$. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.

Number of Swaps

The number of swaps is random for both algorithms, depending on the elements in the array. If we assume random permutations, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the expected number of swaps.

As only relative order counts, we assume that the elements are the numbers $1,\ldots,n$. That makes the discussion below easier since the rank of an element and its value coincide.

Lomuto's Method

The index variable $j$ scans the whole array and whenever we find an element $A[j]$ smaller than pivot $x$, we do a swap. Among the elements $1,\ldots,n$, exactly $x-1$ ones are smaller than $x$, so we get $x-1$ swaps if the pivot is $x$.

The overall expectation then results by averaging over all pivots. Each value in $\{1,\ldots,n\}$ is equally likely to become pivot (namely with prob. $\frac1n$), so we have

$$
\frac1n \sum_{x=1}^n (x-1) = \frac n2 - \frac12\;.
$$

swaps on average to partition an array of length $n$ with Lomuto's  method.

Hoare's Method

Here, the analysis is slightly more tricky: Even fixing pivot $x$, the number of swaps remains random.

More precisely: The indices $i$ and $j$ run towards each other until they cross, which always happens at $x$ (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by $i$ and a right part scanned by $j$.

Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than $x$, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part.
Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically $\mathrm{Hyp}(n-1,n-x,x-1)$ distributed: For the $n-x$ large elements we randomly draw their positions in the array and have $x-1$ positions in the left part.
Accordingly, the expected number of pairs is $(n-x)(x-1)/(n-1)$ given that the pivot is $x$.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:

$$
\frac1n \sum_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\;.
$$

(A more detailed description can be found in my master's thesis, page 29.)

Memory Access Pattern

Both algorithms use two pointers into the array that scan it sequentially. Therefore both behave almost optimal w.r.t. caching.

Equal Elements and Already Sorted Lists

As already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.

On an array that is already sorted, Hoare's method never swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly $n/2$ swaps!

The presence of equal elements requires special care in Quicksort.
(I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”)
Consider as extreme example an array which filled with $0$s. On such an array, Hoare's method performs a swap for every pair of elements - which is the worst case for Hoare's partitioning - but $i$ and $j$ always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in $\mathcal O(n\log n)$.

Lomuto's method behaves much more stupidly on the all $0$ array: The comparison A[j] <= x will always be true, so we do a swap for every single element! But even worse: After the loop, we always have $i=n$, so we observe the worst case partitioning, making the overall performance degrade to $\Theta(n^2)$!

Conclusion

Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.


Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$,
$$
a(n/b)^k < cn^k.
$$
We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.

If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take
$$
f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)}
$$
Then
$$
f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}).
$$
On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.


How to find $L_q = \emptyset$, a state that is not reachable for any given string?

You're right. There is no such state with $L_q = \emptyset$

The first step in the minimization algorithm is: "delete all nonreachable states".


Is model theory useful for computer scientists

A special case of model theory is finite model theory which is closely related to complexity theory and database theory. However the methods being used in classical model theory (e.g. types, stability theory, forcing, large cardinals etc) are geared towards infinite models and assume compactness. Hence they don't appear to be useful in computer science.

A second connection that is not well-known is with program verification and program logics. Model theoretic techniques like  quantifier elimination and skolemisation come from model theory, but are now at heart of verification tools. Questions of importance in program logics like Hennessy-Milner theorems are in the language of model theory simply model-theoretic characterisations of the elementary equivalence (a model theoretic concept) on models of the logic. In many logics coming from program verification, the elementary equivalence is some variant of bisimulation, a concept invented independently in computer science. More examples along those lines could be given.

In summary, there is a lot of overlap, but the communities have been developing separately, use different terminology and have different focus (model theory: infinite, CS: finite and efficient), so currently both communities don't have much to say to each other.


To decide if a particular diophantine equation (i.e., an expression in integers using multiplication and addition/subtraction equated to zero) has any solutions is undecidable. This is essentially the answer to the negative to Hilbert's tenth problem, which asks for an algorithm to determine if a diophantine equation has a solution.


Running time of this recursive relation: T(n) = (n/2)T(n/2) + O(n^2)

You can solve the first recurrence for powers of $2$. The recurrence (without the big O and with an arbitrary base case) reads
$$ T(2^k) = 2^{k-1} T(2^{k-1}) + 4^k, \quad T(2^0) = 4^0. $$
Opening the recurrence, we get
$$
T(2^k) = 4^k + 2^{k-1} \cdot 4^{k-1} + 2^{k-1+k-2} \cdot 4^{k-2} + \cdots + 2^{k-2+\cdots+1} 4^0.
$$
Denote these by $T(2^k) = \alpha_0 + \cdots + \alpha_\ell$. We have
$$
\frac{\alpha_\ell}{\alpha_{\ell-1}} = 2^{k-\ell-1}.
$$
Therefore the largest term is $\alpha_{k-1} = \alpha_{k-2}$, and the rest of the terms decrease geometrically. This shows that
$$ T(2^k) = \Theta(\alpha_{k-1}) = \Theta(2^{k-1+\cdots+1} 4^1) = \Theta(2^{k(k-1)/2}). $$
As you can see, the term $O(n^2)$ in the recurrence isn't important, and you will get similar result for any term $O(n^c)$.

One could guess that the general solution to the first recurrence (with $\lfloor n/2 \rfloor$ replacing $n/2$) is $T(n) \Theta(2^{\log_2 n(\log_2 n - 1)/2})$, and one could further guess that the second recurrence has the same solution (though that's a wilder guess). I'm not sure these guesses are correct. At the very least, the first recurrence should have the solution $T(n) = 2^{\Theta(\log^2 n)}$.


A problem is a search problem if there's an algorithmic way to verify the answer.  In particular, let $V$ be any algorithm that takes two inputs and always terminates.  Then the following is a search problem:

Input: $x$
Goal: find and output any $y$ such that $V(x,y)=1$, or report that no such $y$ exists

Every search problem can be written in this form.  In particular, you can take the above as the definition of a search problem: a problem is a search problem if there exists an always-terminating algorithm $V$ that has the above form.


Are Perceptrons the neural network equivalence of Linear and Logistic Regression?

Yes, logistic regression can be viewed as a simple neural network with multiple inputs, a single neuron, a single output, and using the logistic function as the activation function.

No, linear regression is not a form of a neural network (a neural network would have a activation function; but there's nothing like that present in linear regression).


Infinite recognizable not decidable subsets

Let $K$ be the set of indices of Turing machines which halt on the empty input. Consider the following language:
$$X = \{ 0 w : |w| \in K \} \cup \{ 1 w : |w| \notin K \}. $$
You can check that neither $X$ nor its complement are recognizable.
Therefore your proof idea doesn't work. Here is a different idea. Let $w_1,w_2,w_3,\ldots$ be the words in $L$, enumerated according length and then lexicographically (so if $L = \Sigma^*$, the order would be $\epsilon,0,1,00,01,10,11,\ldots$). The language
$$ Y = \{ w_i : i \in K \} $$
is recognizable but not decidable.


What are the sufficient conditions for weighted binary code to be self compliementary?

You haven't defined your terms, so let me quickly define them:

A weighted binary code $abcd$ is the mapping $C\colon \{0,1\}^4 \to \mathbb{N}$ given by $$C(xyzw) = ax + by + cz + dw.$$
A code $C$ is legal (my term) if $0,\ldots,9$ are all in the range of $C$.
A code $C$ is self-complementing if whenever $C(xyzw) \in \{0,\ldots,9\}$, we have
$$ C(\bar{x}\bar{y}\bar{z}\bar{w}) = 9-C(xyzw), $$
where $\bar{x}$ is the negation of $x$.

Since $\bar{x} = 1-x$, we have
$$
C(\bar{x}\bar{y}\bar{z}\bar{w}) = a(1-x)+b(1-y)+c(1-z)+d(1-w) = a+b+c+d - C(xyzw).
$$
Therefore a legal code is self-complementing iff $a+b+c+d=9$.


Are there current benchmarks for algorithms solving Travelling Salesman?

TSP has many variants under study eg Euclidean vs noneuclidean, exact vs approximations, interrelated but also at times separate threads of research. heres a recent nontechnical survey from early 2013 on TSP by an expert mathematical writer Klarreich, Computer Scientists Take Road Less Traveled that sheds some insight on recent improvements/ theoretical advances & can be mined for some refs. an old approximation algorithm by 1976 Christofides has been unrivalled for decades but some minor theoretical improvements have been made recently. as indicated in the article some theoretical TSP research that is not nec (practically) implemented veers into what is referred to as Galactic algorithm territory by expert RJ Lipton.

as a more applied resource/ angle, also a leading group/ site for benchmarking is DIMACS, NSF center for discrete math & CS, which also has a TSP page with algorithms/ benchmarks updated 2013.


Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.

Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special case of it when all trees are segments.

The new statement will be proved by downward induction on the number of trees. When we have only one tree, we are done. To make an induction step, it's enough to connect two trees without intersecting or touching other trees.

Define distance between different trees $S$ and $T$ as $d(S, T) = min_{s\in P(S), t\in P(T)}d(s, t)$, where $P(X)$ is a set of all points belonging to tree $X$ (not necessarily vertices), $d(s, t)$ is a usual Euclidean distance.

Then take $(S, T) = argmin_{R, W \hbox{ are trees}, R \ne W} d(R, W)$. Let $d_0 = d(S,T)$. Also define $s$ and $t$ as the points which deliver us the minimum distance.

WLOG $s$ is a vertex. This statement requires some geometrical analysis. The most complicated case is when $s$ and $t$ lie strictly inside some segments. But if so, these segments must be parallel to each other, otherwise we can draw a height from some point to the opposite segment and get a distance smaller than $d_0$. And if they are parallel, the segment $st$ is perpendicular to them both, and we can simply move it to the one of the ends of the segments, so one of points actually becomes a vertex.

First, prove that the segment $st$ doesn't intersect or touch other existing segments. We do it by contradiction. If such segment exists, set the intersection point to $u$. It lies strictly inside $st$, because the tree set is disjoint and not self-intersecting. There is a tree $U$ such that $u\in U$. But either $U \ne T$ or $U \ne S$, thus $d(U, T)$ or $d(U, S)$ is well-defined and is smaller than $d(s, t) = d_0$. Contradiction.

Second, if $t$ is already a vertex, we are done, because we can draw a new segment connecting vertices $s$ and $t$. Otherwise define the segment which $t$ belongs to as $K$.

Third, let's continuously move $t$ on $K$ to one of the ends of $K$. If we reach the end without $st$ touching any other points, we are done. If not, assume that we got a segment $st'$ for $t'\in T$, and also $st'$ contains some other vertex $v \in V$. If there are more than one such vertex, take closest to $s$.

Let's look what happens if $V \ne T$. Geometry says that $st$ is perpendicular to $K$. So, if we draw a height from $v$ to $K$, we get a segment shorter than $st$, and it will deliver a distance from $V$ to $T$ smaller than $d_0$.

And if $V = T$, we can just forget about $t$ and connect $S$ and $T$ using segment $sv$.


Solving Recurrences via Characteristic Polynomial with Imaginary Roots

Yes, the solution is in fact $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$ determined by the base cases.  If the bases cases are real, then (by induction) all the complex terms in $T(n)$ will cancel, for all integer $n$.

For example, consider the recurrence $T(n) = 2T(n-1) - 2T(n-2)$, with base cases $T(0)=0$ and $T(1)=2$.  The characteristic polynomial of this recurrence is $x^2-2x+2$, so the solution is $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$.  Plugging in base cases gives us
$$
T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\
T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2
$$
which implies
$$
\alpha + \beta = 0 \\
\alpha - \beta = -2i
$$
which implies
$\alpha = -i$ and $\beta = i$.  So the solution is
$$
T(n) = i\cdot ((1-i)^n - (1+i)^n).
$$

This function oscillates between $\sqrt{2}^n$ and $-\sqrt{2}^n$ with a "period" of 4.  In particular, we have $T(4n) = 0$ for all $n$, because $(1-i)^4 = (1+i)^4 = -4$ (and because I chose the base case $T(0)$ carefully).


Doubt in understanding the time complexities of algorithms to recognize regular expressions

The authors are describing the time complexity to determine whether the input string $x$ is in $L(r)$ in the table and not including construction time, that is they list the per-string cost of using the DFA or NFA, and not the one-time construction cost to build it. In many cases the construction will be done once, and used to recognize strings many times, so it may be worthwhile to sacrifice some time upfront to gain more efficient string recognition afterwards.
You are right to consider the construction cost though. If the automaton will be constructed and used only once, or a small number of times, then the savings in string recognition efficiency may not justify the higher construction time costs.


Starvation Condition in CPU/Process Scheduling?

The first line in the wikipedia states
"In computer science, starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to proceeds its work."

https://en.wikipedia.org/wiki/Starvation_%28computer_science%29

so the condition you stated is starvation because P1 is perpetually denied necessary resources to proceeds its work.


Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input

The asymptotic expected running time of quicksort is $\Theta(n \log n)$: this is true for all three pivot methods you mention.

Wikipedia says that the expected number of comparisons is approximately $1.386 n \log n$ when using a random pivot, and approximately $1.188 n \log n$ when using median-of-three pivot.  There's some experimental evidence that the number of comparisons might be about $1.094n \log n$ when using a ninther pivot for large arrays, median-of-three for medium-sized arrays, and single element for small arrays.  See the following research paper:

Jon L. Bentley, M. Douglas McIlroy, "Engineering a Sort Function".  Software Practice and Experience, 23(11):1249-1265, Nov 1993.

(This paper is cited in the Wikipedia article I mentioned above.)

I'm not familiar with the "uniform shuffle" pivot selection method.  It sounds equivalent to choosing a random element and using that as the pivot.


Why linear transformation can improve classification accuracy when the dimensionality of data is high?

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set.  Think of this as projecting the highly dimensional space into a smaller dimensional space.  For example, you could do principle component analysis and project it into a small space.  This way things that are correlated together are projected into the same dimension and if one of those correlated dimensions is off because of noise, then it would be cancelled out by the values in the other correlated dimensions.

You have to choose your matrix $R$ in a way that essentially averages together things that reinforce each other and reduce noise.  Principle component analysis is one way of choosing such a matrix.


More complicated resources than time and space complexity

It is interesting that claim, "many more complicated resources have been defined" has been present since the very first version of that Wikipedia page created in 2006, whose accompanying comment is "start article (will have to finish later, lightning storm)". That page is created by Wikipedia user Creidieki. That claim has never been explained on that page.

What are these more complicated resources that have been defined?

Here are some computation resources that may or may not be more complicated. Some of them may seen as variations of the computation time and memory space.

Oracles. How many queries will be answered by an oracle? For example, in quantum query complexity.
Entropy. How much entropy is needed to run a randomized algorithm or cryptographic algorithm?
Messages. How many bits are needed to be exchanged so that Alice and Bob can compute a value together?
Comparisons used in sorting in the comparison sorting model or branching in simple decision tree.
Memory accesses. How many memory accesses are used in cell probe mode?
Network bandwidth. This is critical to everyone who is reading this page or using the internet or any network.
Parallel processes. How many processes are used in the computation?
Steps of proof. How many steps does it take to prove or refute statements?
Cache hits. How many cache hits on average will happen when an algorithm runs?

We could also think of some more outlandish ones. How can we measure the complexity of lambda calculus reasonably? Could priority be considered as computation resource as well?

In addition to the resources that are needed to run algorithms to solve problems, We can also examine the resources or even techniques that are needed to build the computation machines.

Characters in source program or bytes in machine code. How long is the source code? I love code golf.
States. How many states are needed in a finite automaton to describe a regular language? From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity. Or what is the least number of states for a Turing machine to be Turing complete? Small universal Turing machines.
Boolean circuits. How large or how deep of of Boolean circuits are used to compute boolean functions?
Non-primitive recursion. When do we need non-primitive recursion to compute large growing functions?

In summary, we can check the list of complexity classes in Wikipedia or Complexity Zoo to find various computation resources that are considered in complexity analysis. Hopefully, this answer have given you a rough idea how diverse and interesting the computation resources and the complexity classes are.


Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2.  Make a bunch of X flash cards, number them 1--X, and shuffle it.  Then here's the explanation:

  OK, we've got this deck of (let's say 20) cards here.  We want to put
  them in order, so 1 is first, then 2, then 3, and so on.  Here's a
  very quick way to do it.

  First, let's go through this deck and make two piles out of it.  Half
  of 20 is 10, so anything bigger than 10 goes in this pile on the
  right, and anything smaller goes in this pile on the left.  (Make sure
  to demonstrate as you go.)

  Now, let's do the same thing with the smaller piles.  What's half of
  10?  (Someone says "five!") That's right!  So anything bigger than 5
  goes in this pile on the right, and anything smaller goes in this pile
  on the left.

  And over here, we've got the group that's bigger than 10.  So half of
  10 is 5, and what's 10 plus 5? (Someone says "fifteen!") That's right!
  So anything bigger than 15 goes in this pile on the right, and
  anything smaller than 15 goes in this pile on the left.

  And now the piles are getting small enough that you can easily look at
  them and put them in order.  Look, here we've got 2, 4, 5, 3, 1.  So
  we just switch them around like this, and you can see 1, 2, 3, 4, 5.
  So let's do the same thing with the other piles, and then we just put
  the piles in order, and look!  They're in order from 1 to 20!

Congratulations.  You've just taught a bunch of children the basic principles of an adaptive quicksort algorithm!  You can go a bit deeper than that depending on mental maturity, but going much further beyond this point requires some understanding of formal logic.

As for proving its complexity, that's trickier.  It's one of the things that requires formal logic, and they'll have to understand the basic principles of big-O notation in the first place.  You might want to hold off on that part at first.


Complexity of forming a min heap out of a given array with k inversions

We remove the inversions by beginning from the bottom (furthest level from the root) and going breadth-first up.

Start at the bottom level.  We have a set of leaves, each satisfying the heap property.
Move one level up. If there is an inversion at this level, we fix it by sifting down. Now all sub-heaps from the bottom up to and including this level satisfy the heap property.
Continue applying 2. until finishing at the root level.

Suppose in the worst case that the $k$ inversions fill the top levels of a heap of height $h = \lfloor log(n) \rfloor + 1$. We have at most $\Sigma^{\lfloor log(k) \rfloor + 1}_{i = 0} 2^i \cdot (h - (i + 1))$ swaps for sifting down, where $2^i$ represents the number of inversions at a given depth from the root. This is $O(n)$.


Convert A = 1, B = 2, ..., Z = 26. Take the difference of (cipher text - key) modulo 26. Extend "EZRA" with itself. The third row is the difference between the first and second rows. There might be an error on 'B' and 'G'.

 M  E  D  M  T  B  J  B  M  A  E
13  5  4 13 20  2 10  2 13  1  5

 H  E  L  L  O  G  R  A  H  A  M
 8  5 12 12 15  7 18  1  8  1 13

 5 26 18  1  5 21 18  1  5 26 18

 E  Z  R  A  E  Z  R  A  E  Z  R
 5 26 18  1  5 26 18  1  5 26 18


The maximum & minimum number of sources that can be multiplexed so that no data loss occurs on TOKEN BUCKET?

A is correct. As 1st part is already described i will explain derivation of S2 only.
Let there are N stations. When buffer is added then even when source is off, data will persist so considering duty cycle here we say that the actual data transmitted per unit time during the whole duty cycle is (1/3)10 [for 1 unit of on-time data is transmitted and for another 2 unit of off-time it stays in buffer so in 3 unit time 10Mbps data is tranferred]. This is the case will all other N-1 stations also. So adding all should be = Max capacity of channel.
N(1/3)*10 = 100
N=30


Variance of MAXSAT clause satisfiability

Suppose that the MAXSAT instance consists of clauses $C_1,\ldots,C_m$. Denote by $X$ the expected number of clauses satisfied by a random assignment. Then
$$
\mathbb{E}\left[\binom{X}{d}\right] = \sum_{\substack{S \subseteq [m] \\ |S|=d}} \Pr[C_i \text{ is satisfied for all } i \in S].
$$
This gives a roughly $O(m^d)$ algorithm for computing the $d$th moment.


Can we apply binary search for finding key 'x' in unsorted array?

We can find the break point (where the type of sequence changes) in theta(log n). Then we can search individually on both sides of the break point (each of which is a sorted sequence). So overall theta(log n) only.


Time complexity of 8-queen, by placeing one by one without attack

Let's tackle your questions one by one:

State space: I have no idea where you got this number from. The state space is ostensibly $\binom{64}{8} \approx 2^{48}/8! \approx 2^{32}$.
Your approach: What backtracking is involved here? Your algorithm as stated could either succeed or not, but it will do so very fast.
Time complexity: It is in general difficult to estimate the time it takes a backtracking algorithm to find a solution. You can try to estimate the total time it takes to go over the entire space in various ways, for example you can estimate the branching factor at each step.
Space complexity: Backtracking algorithms have very small space complexity. You're basically keeping track of one partial solution.
The estimate $O(8^8)$: Actually $8^8 = 2^{24}$ is very small. You can probably go over this search space in under a second on a modern computer.


Interval scheduling scheduling problem with minimal workers

This is called Interval Partitioning Problem or Interval Coloring Problem in this lecture note, as well as in Section 4.1 of the book [1].

  Given intervals $(s_i, f_i)$, assign them to processors/workers so that you
  schedule every interval and use the smallest number of processors/workers.

The greedy algorithm is a simple one-pass strategy that orders intervals by their starting times, goes through the intervals in this order, and tries to assign to each interval it encounters a processor/worker that has not already been assigned to any previous interval that overlaps it.

[1] Algorithm Design. By Jon Kleinberg and Eva Tardos.


Why doesn't decision tree work in case find minimum

There is more than one technique to prove a lower bound on the depth of decision trees. One technique you have seen is bounding the depth of a decision tree by the logarithm of the number of its leaves. As you comment, this technique doesn't give the correct lower bound for the case of computing the minimum. However, we can lower bound the depth of a decision tree computing minimum directly.

Take any reachable leaf $\ell$ in a decision tree for minimum, and consider the entire path $p$ leading to it. Construct a graph whose vertices are the input elements $x_1,\ldots,x_n$, two elements $(x_i,x_j)$ being connected if they are compared in $p$. I claim that this graph must be connected, and I show this below. A connected graph on $n$ vertices must have at least $n-1$ edges, and this shows that the leaf must have depth at least $n-1$. In particular, the depth of the decision tree is at least $n-1$.

Now to the proof of the claim. Suppose that the graph contains more than one connected component, say it contains the components $C_1,\ldots,C_m$. Since the leaf $\ell$ is reachable, there is a linear ordering compatible with the results of the comparisons in each connected component $C_i$. We can put together these linear orderings into a linear ordering of all elements in $m!$ different ways. In particular, we can have $C_1 > C_2 > \cdots > C_m$, and we can have $C_1 < C_2 < \cdots < C_m$. This means that it is consistent with the comparisons in $p$ that the minimum is in $C_m$, and it is also consistent that the minimum is in $C_1$. Hence whatever the tree outputs at $\ell$ will be wrong in at least one linear ordering consistent with the comparisons in $p$, showing that the tree doesn't compute the minimum.


What is With High Probability on Probabilistic Algorithms?

An event happens with high probability with respect to a parameter $n$ if it happens with probability $p_n$ and $\lim_{n\to\infty} p_n = 1$. Usually the parameter $n$ is clear from the context. In this case, for example, it is probably the number of elements in the list.

The definition of "with high probability" in the lecture notes is even more specific, specifying how fast $p_n$ should converge to $1$: an event happens with high probability if it happens with probability $p_n \geq C/n^\alpha$ for some $C,\alpha>0$. For example, if you choose a random number from $\{0,\ldots,n\}$ then it is non-zero with high probability since the probability that it is non-zero is $1-1/(n+1) \geq 1-1/n$ (so in this case $C=\alpha=1$).


Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$?

No, thanks for Ariel's correction, since for every $L$ it holds that $\epsilon \not\in \overline{(L^*)}$  and $\epsilon \in (\overline{L})^*$ and therefore $ \overline{(L^*)}\neq (\overline{L})^*$


Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

The desired output from your algorithm might be exponentially large.  (There could be exponentially many set covers).  Therefore, you can't possibly expect to have an efficient algorithm in general.

One approach could be to code this up as a SAT (or ILP) problem, and add blocking clauses, so that in each iteration it gives you a new set cover that you haven't seen before.  Whether this will be effective in practice will depend upon many factors, such as how many set covers exist.

To help us help you, I suggest you tell us more about the parameters and structure of your particular problem.  What would be a typical size of $|U|$ and of $|S|$?  What would be a typical number for the total number of set covers (the size of the output that you're hoping to produce)?  Is there any structure in $S$ that might be helpful?  The best algorithm for your particular situation is likely to depend upon these factors.

Edit: Thank you for the additional details!  That helped.  So, it sounds like your goal could be described: given $k$, test whether there exist $k$ disjoint set covers from $S$ (i.e., test whether there exists $C_1,C_2,\dots,C_k$ where $C_i \subseteq S$, $C_i$ is a set cover, and $C_i \cap C_j = \emptyset$ for all $i,j$).  This is the decision problem version of your problem; if we can solve the decision problem, then we can use binary search on $k$ to find the maximum number you're looking for.

Given your problem size, the first thing I'd try would be using a SAT solver.  Here's how you could formulate your problem in a way that would let you apply an off-the-shelf SAT solver.  Suppose $S=\{s_1,s_2,\dots,s_{50}\}$, where each $s_i$ is a subset of the universe $U$.  Introduce boolean variables $x_{i,j}$ (where $1 \le i \le 50$ and $1 \le j \le k$), with the intent that if $x_{i,j}$ is true, then the $j$-th cover $C_j$ will include $s_i$ (in other words, the $j$-th cover contains the subsets $\{s_i : x_{i,j} \text{ is true}\}$).  We obtain the following constraints, which can each be expresses as CNF clauses:

For each $i$, at most one of $x_{i,1},x_{i,2},\dots,x_{i,k}$ is true.  One way to express this is as the conjunction of clauses $(\neg x_{i,j_1} \lor \neg x_{i,j_2})$ over all $j_1 \ne j_2$, i.e.,

$$\bigwedge_{1 \le j_1 < j_2 \le k} (\neg x_{i,j_1} \lor \neg x_{i,j_2}).$$

(Other ways of encoding this constraint are described here.)  This expresses the constraint that the $k$ set-covers are disjoint.
For each $j$, $\{s_i : x_{i,j} \text{ is true}\}$ is a set cover.  In other words, for each $j$ and each $u \in U$, there exists $i$ such that $u \in s_i$ and $x_{i,j}$ is true.  This can be expressed as the following conjunction of clauses:

$$\bigwedge_{j,u} \bigvee_{i : u \in s_i} x_{i,j}.$$
Optionally, you could break the symmetry here by imposing a lexicographic order on the set-covers.  For instance, you could require that when $1 \le j_1 < j_2 \le k$, then $(x_{1,j_1},x_{2,j_1},\dots,x_{50,j_1}) < (x_{1,j_2},x_{2,j_2},\dots,x_{50,j_2})$ (using the lexicographic ordering on bit-strings of length 50).

You could then try using an off-the-shelf SAT solver and see if it is able to complete on this problem in a reasonable amount of time.


To show that the language is $\Pi^0_2$ complete you have to show two things:

The language is $\Pi^0_2$
Every $\Pi^0_2$ language is many-one reducible to your language

To show that your language is $\Pi^0_2$, informally, you need to know two things: (1) quantifiers over strings count the same as quantifiers over numbers, and (2) the predicate $P(M,\sigma)$ = "machine $M$ accepts string $\sigma$" is $\Sigma^0_1$. Your language is a universal quantifier in front of that $\Sigma^0_1$ relation, so it is $\Pi^0_2$.

To show that an arbitrary $\Pi^0_2$ language is many-one reducible to yours, it's easiest to show that some other language that you know is $\Pi^0_2$ complete is many-one reducible to your language. The details of that will depend on what languages you already know to be $\Pi^0_2$ complete. If you don't know any, then it helps to know that every $\Pi^0_2$ language is definable by a formula of the form $(\forall \sigma)(\exists \tau) R(\sigma,\tau)$ where $R$ is computable.


Why does cpu benchmark increases faster than cpu frequency?

Part of the benchmark might be limited by CPU time; other parts might be limited by IO or memory latency or other factors.  Speeding up the clock frequency will speed up the first parts but not the second parts.  As a result, doubling the clock frequency won't necessarily double the speed at which the benchmark is executed.  So, the two ratios aren't necessarily equal.


Is there a way to determine if a collection is a palindrome within a time bound?

If n is the number of words, it's impossible. It would mean that any roblem with just two words could be solved in constant time. But you could have two words of arbitrary equal length, and the time to confirm that one is the other reversed is unlimited if the length of the words is unlimited.

PS. Your edit changed this from a rather interesting problem to one that is really boring and trivial. You take an array with 26 counters, one for each letter, initialised to all zeroes. You go through the letters, and for each letter you increase the corresponding counter. When you are done, you check that there is at most one odd counter.

When you ask a question, it's only polite to take your time to state the question properly. Your original question has nothing whatsoever to do with the edited one.

And if you haven't figured it out: In a palindrome, the first and last letter, the second and second to last letter, and so on, are equal. Which means you have even numbers of each letter. There may be one letter in the middle (like in oxo) that doesn't have a match, or there may be none (like in otto). Which means at most one letter has an odd count. So to figure if a palindrome can be formed, just count the letters.


does cpu time reflect BigO time complexity

There are really two questions here:

How does CPU time relate to time complexity?
Can you use a plot of CPU time to understand time complexity?

Let me answer each in turn.

Time complexity

Time complexity refers to the total time it takes for the algorithm to finish.

If by "CPU time" you just mean the time it took for this particular program to run, excluding the time for other programs or the operating system, then yes, these are the same.

If by "CPU time" you meant the time spent on computation but not time spent on I/O, then it might or might not match what is meant by time complexity.  In practice, I/O is often slower than computation -- maybe by a significant factor.  Normally, in theoretical work where we measure time complexity, we don't try to account for that distinction, as it's "only a constant factor".

The plot heuristic

Plotting the running time as a function of the size of the input can definitely be a useful heuristic to form an informed guess about what the asymptotic time complexity of the an algorithm is.  It's often a good guide.  However, be warned that it is not 100% reliable: there are some cases where it can be misleading.

I'd like to refer you to the following three questions for more on this topic:

how to understand time complexity from a plot?
How to fool the plot inspection heuristic?
How does the automatic complexity analysis of Codility work?

Bottom line

In summary: yes, basically, plotting CPU time  as a function of input size can be a helpful way to assess asymptotic time complexity, as long as you keep in mind the caveats.


Prove the recursive enumerability of the class of NP-hard context-free languages

You should distinguish between two cases. If $\mathsf{P} \neq \mathsf{NP}$ then $L(G)$ cannot be $\mathsf{NP}$-hard since $L(G) \in \mathsf{P}$. In this case, $L = \emptyset$.

Conversely, if $\mathsf{P} = \mathsf{NP}$, then all non-trivial languages in $\mathsf{P}$ are $\mathsf{NP}$-hard. In this case, $L = \{ \langle G \rangle : L(G) \neq \emptyset, \Sigma^* \}$. It is possible to decide whether $L(G) \neq \emptyset$, and the problem of determining whether $L(G) \neq \Sigma^*$ is clearly r.e. (in fact, it is $\Sigma_1$-complete), and so $L$ is r.e. (in fact, $\Sigma_1$-complete).


What exactly can finite-state machines not do?

The answer depends on what you mean by FSM.

If by FSM you mean finite automaton, then there's a lot that it can't do. As others have pointed out, you can't remember more than a constant amount of information using a finite automaton; the memory must be encoded in the state. This means you can't do things like recognize $a^nb^n$, since you'd need to remember how many $a$ symbols you've seen, which is not possible unless you have an arbitrary amount of memory. The pumping lemma for regular languages and, especially, the Myhill-Nerode theorem offer insight into the kinds of things that can and cannot be done.

If by FSM you mean any automaton formalism which is limited to using finitely many states, then Turing machines are among the most computationally capable FSM models available. Indeed, anything which is effectively computable is computable by a Turing machine, according to the Church-Turing thesis. However, there are still limitations to what a Turing machine can decide: there are problems it cannot answer, such as the halting problem.

Models which aren't limited to a finite number of states aren't particularly interesting for a few reasons, most prominent of which are the following: they are of limited practical importance since we cannot construct real computers with infinitely many configurations; any language can be recognized in such a model by mapping strings in the language to unique accepting states, and strings not in the language to unique non-accepting states.


No, quantum computers are not the same as analog computers (at least in principle).

Analog computers simulate the (mathematical) problem to be solved by
building a physical system that obeys the same constraints/laws as the
mathematical problem. The answers are obtained by observing and
measuring the behavior of the physical simulation. Its accuracy is
that of the simulation (there may be parasitic effects), the accuracy
of the initial conditions, the setting of problem parameters in
particular, and the measurement on the result.

Accuracy may also be limited by the scale range of applicability of
the phenomena used for the simulation. For example, if the answer is
given by a level of water in some container, you may be limited by
capillarity effects (which can be accounted for to some extent) and by
the fact that measuring water level with more accurcy that the
diameter of a molecule may not be very meaningful.

I used to think that a major difference is that analog computing is in principle
based on the simulation of continuous laws, involving reals, while
digital computing operates exclusively on countable sets. But, in the light of current knowledge in computing theory, this
distinction is probably naive because I suspect that physics could be
formalized as well using only computable reals, of which there is only
a countable number.

Quantum computing will mainly allow you to do several digital computations in
parallel (to state it simply). It is always a finite cross product of
several computations, and hence stays in the countable realm. You may
think of it as the cross-product construction of an automaton that
simulates two or more computations of simpler automata (though it is
even less general than that from what I understand of it). These
finite cross product constructions never leave the countable realm.