Is there a formal difference between $f:X \to X$ and $f\in X \to X$?

No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things. Also, sometimes they are used in a particular context for different (but usually related) things. You'll, of course, have to see how it has been defined in that context.

Any use of $\in$ usually strongly suggests a set-theoretic context (though you occasionally see it in a type-theoretic context). The $f:X\to Y$ notation was, I believe, popularized in mathematics by category theory. In this case, it means $f\in\mathsf{Hom}(X,Y)$. This is compatible with $f\in Y^X$ in the case that the category is the category of sets and functions. In a general categorical context, $Y^X$ is usually reserved for exponential objects for which it makes no sense to ask if $f\in Y^X$, though you (usually) can ask if there is an arrow $1 \to Y^X$.

In logic, when $X$ and $Y$ are sorts, usually $f:X\to Y$ means that $f$ is a function symbol. In this case, $X$ and $Y$ aren't sets and neither is $X \to Y$. It makes no sense to say $f\in X\to Y$ unless $\in$ isn't being thought of as set membership or we want to say $X\to Y$ means the set of function symbols from $X$ to $Y$. This latter view starts to get rather similar to the categorical view.

In type theory, usually $f:X\to Y$ means something like $f$ has type $X\to Y$ and $X\to Y$ is the type of functions from $X$ to $Y$. Types are not sets and part of the purpose of this notation is to remind one of that fact. Indeed, types are more like sorts and this notation is similar to how it is used in logic. Sometimes $Y^X$ is also used where $Y^X$ is used in a more first-class sense in a way that is compatible with the similar distinction I mentioned for category theory, so we might write $X\to Z^Y$ rather than $X\to(Y\to Z)$. Sometimes no distinction is being made and the notation is completely synonymous and the choice is made purely for typographical reasons. For computer programming, the choice is mostly typographical, f : X -> Y is easier to write and easier to read, though programming languages are also closely related to type  theories.

It doesn't really make sense to talk about which of these notations is "more fundamental" than the others in general. That said, the $f:X\to Y$ notation is usually making the least commitments if multiple notations are in use. Often $f:X\to Y$ isn't a proposition with a truth value, so it wouldn't make much sense to write $\{f\mid f:X\to Y\}$. Admittedly, in the context where it isn't a proposition, you usually aren't using set theory. If you really wanted to, you could meta-theoretically write $\{t\mid \cdot\vdash t:X\to Y\}$ to mean the set of closed terms of type $X\to Y$, say. This would have nothing to do with a set of functions though.


This is the element distinctness problem, and can be solved in polynomial time in many ways. For example, you can go over all pairs of elements and compare them, or if the elements are comparable, you can sort them and then check for duplicate elements (though in principle comparisons could be very time consuming, and in that case potentially the algorithms wouldn't be polynomial time; there's no such problem with the former algorithm).

Make sure you understand what "polynomial time" is. Also, you have a false dichotomy in your title: every problem in P is also in NP; if P=NP then every problem in P is also NP-complete; and if P≠NP then there are problems which are neither in P nor NP-hard.


If a key in a red-black tree has exactly one child (which isn't null) then it is always red

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be:

It is easy to see that it does not respect the fourth condition of the definition.
In the claim, when it is said that:

a key […] has exactly one child (which isn't null)

it actually means that it has two children, and exactly one of them is null. It is due to the fact that in the representation of a red-black tree, you can either represent ALL null leaves or represent none.
I will let you try to prove or disprove the claim knowing that and edit this answer if necessary.


Enumerate All Possible Strings Over Alphabet

Consider a string over $\Sigma$ to be a number written in base $|\Sigma|$ and implement a counter. Remember to include leading "zeroes": first generate all the length-1 strings, then all the length-2 ones, and so on.


Here is the idea behind proving this triple. Let us denote by $s_0,i_0$ the values before the block, and by $s_1,i_1$ the values after the block. We are given that $s_0 = 2^{i_0}$, and furthermore it is clear that $i_1 = i_0 + 1$ and $s_1 = 2s_0$. But then
$$
s_1 = 2s_0 = 2\cdot 2^{i_0} = 2^{i_0+1} = 2^{i_1}.
$$
Whether this constitutes a proof of not depends on your normative environment.


Converting an NFA to regex using GNFA algorithm?

You want to know why "the others" obtained a different expression?

When contructing a regular expression there is no unique correct answer. There are usually several expressions "that make sense". In this case you use state elimination method (I learned this under the name of Brzozowski and McCluskey). Here the order of removal determines the expression found. So: what do you get when removing $q2$ first?

You can also do "clever tricks" during the construction. In your example you have $b\cup aa^*b$ which is equivalent to $a^*b$.


Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$.

A grammar $G$ is strong $LL(k)$ iff for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have:

$$
First_k( \alpha \; Follow_k(A) ) \; \cap \; First_k( \beta \; Follow_k(A) ) = \emptyset
$$

The steps to obtain a $k$ for a certain grammar $G$ are thus as follows:

For each $n > 0$:

Check wether $G$ is $LL(n)$
If so, try proving $G$ is $LL(n)$
If not, we have found our $k = n - 1$

Some documents that might help with the actual proof:

About first and follow sets (LL(1))
Obtaining first and follow sets (LL(k)) with example


Why do we need so many sorting algorithms?

Some kind of sorting algorithms may end up being visually more pleasing, giving nicer intermediate steps allowing for visual inspection of data where a human can recognize where in the process one is and analyze what goes wrong and sanitze the data accordingly.

I know I have used sometimes some costly sorting algorithm because it came in handy during game programming, giving just the right effect(revealing something on monitor, sorting inventory, etc...) on screen without it looking computer generated.

Like T.S. Elliot said:

  The journey, Not the destination matters...

To see what I mean(source of images https://imgur.com/gallery/voutF):

  !

  !

  !

  !

  !

  !

  !


How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem

Double the graph size: make two clones of the input $G_1,G_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G_1,G_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G_1$ or all $G_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.


What are the major differences between row polymorphism and subtyping

Subtyping says given an expression of one type we can give it also another type.  We say the former is a subtype of the latter and this subtyping relationship induces many other relationships.  In symbols,
$$\frac{\Gamma\vdash E:S\qquad S<:T}{\Gamma\vdash E : T}$$

The key thing here (and the reason I reviewed it) is that the same expression is given two different types.  In parametrically polymorphic languages with implicit type instantiation we have the following subtyping relationship:
$(\forall \alpha.\tau) <: \tau[T/\alpha]$ for all types $T$.  If type instantiation is explicit like in System F, this subtyping relationship doesn't hold.

As a bit of an aside, we could say a language with row types (usually) has  subtyping relationships of the form $\{\ell_1:A,\ell_2:B\} <: \{\ell_2:B,\ell_1:A\}$ giving rise to $\{\ell_1:A,\ell_2:B\} \cong \{\ell_2:B,\ell_1:A\}$ where $S \cong T \iff S <: T \land T <: S$.  However, the way this is actually handled is by changing the notion of equality of types (i.e. unification) so that $\{\ell_1:A,\ell_2:B\} = \{\ell_2:B,\ell_1:A\}$, i.e. they unify.  In this case, the subtype relationship is the trivial $T <: T$ one.

Usually when we talk about a language with subtyping we mean one with a non-trivial subtyping relationship on ground types, i.e. types without free variables (which, of course, can and will generate subtyping relationships for non-ground types).  So a system with row polymorphism like Roy's is not a language with subtyping in this sense, though it does have the non-trivial subtype relationship that comes from any implicitly instantiated parametric polymorphic language.  Structural subtyping, on the other hand, explicitly states non-trivial subtyping relationships for ground types.

By row types, I'll mean having a non-trivial unification as described above or an equivalent.  Without this, row types are little more than nested tuples.  Note, row types are independent of parametric polymorphism; I do not mean to imply row variables.  From the argument about $(\cong)$ above, structural subtyping implies row types but not vice versa.  Parametric polymorphism is orthogonal (in the sense the you can have or not have it, there are definitely interactions) to row types or structural subtyping.  A system with structural subtyping + parametric polymorphism subsumes row type + parametric polymorphism (assuming some kind of "record union") in the sense that every term in the latter can be typed with the same type in the former.   The former is just able to type with additional types as well.  Using Brian's example, in a system with structural subtyping and parametric polymorphism answer would have the same type as in the row typing version, but it would also have the subtyping version's type as well.

So you presumably want to compare row type + parametric polymorphism with structural subtyping without parametric polymorphism.  The key benefit of the former (and sometimes drawback) is that it allows you to propagate information globally.  When $\rho$ gets instantiated to { c : Number }, everything that ever unified with it gets instantiated as well.  This may percolate up to the root of your application.  Carrying around row variables through large sections of code is not uncommon.  Subtyping's approach is to forget information: going from a subtype to a supertype loses (type) information.  This can often be what you want: there's a common type you care about and everything else is irrelevant details.  My bias is toward maintaining as much type information as possible and only discarding it explicitly.  The downsides of subtyping's approach is often evidenced by programs that are type correct but only because types were pushed to a(n informationless) "top" type, e.g. the empty record.  Reiterating, parametric polymorphism (in general) preserves type information, subtyping intentionally loses it.


Mistake in a proof of termination phase of Simplex algorithm in CLRS?

Because of line 9, $\Delta_l$ is going to be $\infty$ if and only if all the $\Delta_i$ with $i \in B$ are $\infty$. This can happen only when all the $a_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}_i \ge 0$ for all $i$. Therefore it is both feasible and it has unbounded objective value.

If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.


Decidability of the halting problem on real-life finite computers given unlimited input

The halting problem can be stated as follows:

  Given a program P and an input x, does P halt when run on x?

Here both P and x are finite. In some cases (for example, in program verification) we might also be interested in infinite input which is eventually periodic, or at the very least, has an effective finite description (i.e., it is given by some algorithm). Assuming that this algorithm is also executed on a real machine (otherwise it is "cheating"), the entire setup can be folded to a program running on a real machine, and so the property of having a finite number of states is recovered.


Is there any way to "pre-compute" a huge dataset in order to make *any* arbitrary linear-time computation on it sub-linear?

Multiplying the size of the dataset you have to pre-calculate over does not increase the amount of time it takes to calculate the average when the sum and length are pre-calculated; it will be a constant time operation. Moreover, calculating the sum and length of a dataset in itself is only linear time (doubling the dataset will result in doubling the amount of time it takes to pass over all data and therefore is only linear, the 'addition' operation is constant-time and does not contribute to the time complexity).

However, I think what you meant is the following:

If I had any possible data readily accessible, would that mean I can run a more optimal algorithm over this new dataset than I could over the original dataset?

The answer is no.

Some examples:

The original dataset contains 10 integers. We want to calculate the total when we multiply each number by every other number. This is an O(n^2) algorithm since for each element we have to pass over all other elements.
If we had precalculated the set resulting from multiplying each number by all other numbers it would only take linear time; O(n) since we only have to sum the numbers in the dataset. So for this function the hypothesis holds.
The original dataset contains 10 integers. We want to calculate the sum of the first two numbers. This will take O(1) time, as the size of the dataset does not increase the time it takes to sum the first two numbers. Now assume that we had precalculated this value then it would still be an O(1) algorithm. After all, no (0) time is still considered constant time.
The original dataset contains 10 integers. We want to know the value at the first index. This is obviously a constant time O(1) function and, as a result, one that cannot be done more efficiently regardless of any precalculated data.

P.S. do note that this is only the purest sense that it does not hold for every function; it might very well be that every real-world application can more efficiently be run over a set containing pre-calculated data).


Splay trees: why are depths of nodes on the access path halved?

Nobody has answered this question yet, and I can give some hints how to solve it.
I would much rather post this as a comment, but I can't since I don't have enough reputation.
So here is a link to the original paper: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
The basic idea is looking at zig-zig and zig-zag (zig only happens once when the parent of x is the root!):

Notice that if a node was in the search path before x was pushed to that position, it is now either in A or in B.
Notice that all nodes in A and B have at least 1 depth less than before the zig-zig operation

Notice that if a node was in the search path before x was pushed to that position, it is now either in B or in C.
Notice that all nodes in B and C have at least 1 depth less than before the zig-zag operation

Now just think about how many zig-zig and zig-zag operations there are for a node with depth d in the search path.


Finding no. of leaf nodes for each node in a BST

Traverse your graph in post order, create two auxiliary functions, $Cost$ and $Total$, first one demonstrates cost of your $g(x)$ at each vertex, second one calculates total number of leafs. set the cost function to zero: $Cost(leaf)=0$ for leaf, and $Total(leaf) = 1$ for leaf, then for parent node set this two functions as:

  $$Cost(v) = min\{Total(child_l),Total(child_r)\}$$$$Total(v) = Total(child_l) + Total(child_r)$$

Because is post order, will be filled correctly and is $O(n)$ algorithm.

But actually worst case complexity in different algorithm may be differ, you can show that you cannot do this better than $\Omega(n)$, and above algorithm is $\Theta(n)$, which gives a tight bound, but, may be someone implement it in a bad way that causes to the $\Omega(n^9)$, or may be someone else provide an algorithm of $\Theta(n^3)$, At all, I mean your current question is not well defined, and if it was for real exam, it was wrong, and any answer which satisfies $\Omega(n)$ barrier, is correct.


One example of compiler intrinsic functions is the floating point math functions that are part of the standard C math library.  On CPU architectures with on-chip support for floating point trigonometric functions like sine and cosine, the compiler might replace the function calls with a series of instructions that achieve the same result but using the available CPU instructions instead.

Another example is replacement of calls to C low-level memory copying functions such as memcpy and memmove.  These might be implemented directly using SIMD instructions if available, copying the blocks of memory many times faster.

Note that "... an intrinsic function is a function available for use in a given programming language whose implementation is handled specially by the compiler." This is in contrast to operators like addition and subtraction; the compiler would be expected to implement floating point arithmetic operators even without an FPU since the C language specification demands it. Intrinsic functions go further and implement things that are properly part of the C library of hosted implementations.


Knapsack Problem with exact required item number constraint

You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be discarded).

To ensure that you select at least $L$ items:

Add $n(V+1)$ to the value of every item.
Now the problem is equivalent to that of maximizing the number of selected items, breaking ties in favor of set of items with largest original total value, subject to weight constraints. There is a solution that selects at least $L$ items iff the optimal solution has a value of at least $n(V+1)L$.

To ensure that you select at most $L$ items:

Add $(W+1)$ to the weight of every item.
Add $L(W+1)$ to $W$.
Now every subset of more than $L$ items weighs at least $(L+1)(W+1) = L(W+1) + (W+1) > L(W+1) + W$, and is hence not feasible. Every subset of $L$ items that had an overall weight of $w$, now weighs $L(W+1) + w$, and hence is  feasible iff $w \le W$.
A subset with less than $L$ items might be feasible even if its overall weight is more than $W$, however its total value will always be smaller than $n(V+1)L$.


For a point $x$, let $d(x)$ be the sum of distances between $x$ and points in $A$. For $x \notin A$, the derivative $d'(x)$ has the nice formula
$$ d'(x) = |\{y \in A : y < x\}| - |\{y \in A : y > x\}|. $$
This shows why the median is the best answer when you don't have to select a point from $A$. For a point $x \in A$, $d(x)$ is the same as your objective function, hence the solution is to choose the median. You can find the median in linear time, as described in Wikipedia and various other resources.


There are plenty of problems where there is likely no way to verify a solution in polynomial time.

Amazingly, the problem "is p a prime number" is in NP due to some deep mathematical theorem that shows that for every prime number, there is a polynomial time proof that it is a prime number. (For many, many NP complete problems the part that there is a polynomial time proof is quite trivial).

A simple problem: Given an integer n, how many prime numbers p <= n are there? There are ways to calculate this in $O(n^{2/3})$ and possibly a bit faster (which is exponential in the problem size). But there seems to be no possible proof that is less time consuming then finding the solution from scratch. so no proof that doesn't take exponential time.

Here's a simple problem that I believe has an absurdly high time complexity: On the UK TV show "Countdown", the contestants are given six slightly random numbers, and another larger number, and are asked to form the larger number by combining any or all of the six random numbers using + - * and /. That's the simplest problem. The next, harder problem: Given six integers and some larger n, can all integers 1 ≤ i ≤ n be formed that way? The next, harder problem: Given n, are there six numbers a1 to a6 so that all integers ≤ n can be formed by combing a1 to a6?

And the final problem (as a decision problem): Given an integer k ≥ 1, and a larger integer n ≥ 1, are there k integers $a_1$ to $a_k$ such that all integers 1 ≤ k ≤ n can be formed by combining any or all of $a_1$ to $a_k$ using +, -, *, / ?


Coordinated Attack Problem On The Arbitrary Graph

The easiest way to do the reduction is to decompose your graph into two pieces $G_1,G_2$ arbitrarily, let one general "play" $G_1$, and the other one $G_2$. Details left for you.


co-NP is the set of complements of problems that are in NP. So co-NP contains problems such as non-3-colourability, Boolean unsatisfiability and so on.
Most complexity theorists believe that NP$\,\neq\,$co-NP and one consequence of this is that the complement of any NP-complete problem would be in co-NP but not in NP.

Wikipedia has more information on co-NP.


Find minimal spanning tree of graph with edge values from 1 to 5 integers

Take a look at the complexity of Kruskal's algorithm. Since the edges are with integer weights, you can sort them in linear time. The entire algorithm will take a total of $O(|V|\alpha(|E|)+|E|)$. We need $O(|E|)$ to sort, and an additional $O(|V|\alpha(|E|))$ for Kruskal's algorithm.


What's the purpose of the non-deterministic Turing machine?

I will try to address why the concepts of NDTM and NP are useful, and possibly what motivated their study.

NDTM is one of many variants of turing mahcine. For example, the classical (deterministic) Turing machine can be equipped with multiple heads and tapes, randomness or quantum states. It can also be constrained by a limited alphabet, limited tape or pre-determined head-movements (see here).

A TM is said to decide a language (a set of words using a pre-defined alphabet), if it can halt on any input written on the tape, and accept precisely inputs belonging to the language. A language is called decidable if any TM decides it. Similarly, a function $f$ on natural numbers is said to be computable if there exists a TM which, given an input $n$, halts with $f(n)$ written on the input tape.

It turns out that all of the mentioned variations of TMs (including NDTM) are equivalent in the set of functions they can compute (similarly, the languages they can decide). This holds for other, much more different models than TMs, and has led to the Church-Turing thesis, which informally hypothesizes that any "reasonable" model of computation is equivalent to the classical Turing machine. In this aspect, NDTMs are useful as an example of fantastical computational models that are nonetheless as strong as a classical TM, supporting the Church-Turing thesis.

As far as I understand (see here and here for history), Turing himself did not focus on complexity classes, and so the previous reason might have been his sole motivation. However, later on it was discovered that different TM variants are not equivalent in the set of problems (languages and functions) they can solve in a certain amount of computation steps (time), bound on working-tape size (memory) and success probability. With this finer resolution, it turns out that the different models are very different, resulting in a zoo of complexity classes for problems.

I hope this is helps show why NDTMs (and the NP complexity class) are not a definite model for the problems science could potentially solve efficiently, but just one of many variations of computational models (less realistic than random and quantum machines, for example). There are, however, some reasons for why the specific class of nondeterministic polynomial time ($NP$) is such a popular attraction of the zoo:

It is relatively easy to explain and reason about. While researchers are working on many other open problems in complexity theory, the question of whether $P\neq NP$ requires only basic knowledge in math to understand, and the concept seems so intuitive that it invites many solution attempts from amateur researchers.
Whether a problem is solvable in polynomial time in a computational model is seen as an approximate measure of practical tractability (this is Cobham's thesis).
Any complexity bound derived by NDTMs can be seen as a bound on verification time by classical TMs (see here for why). Since classical TMs are used as models of practical computation, this has practical implications.
Many real-world important problems just happen to be not just in $NP$, but $NP$-complete. This means that if $NP$ is indeed a different complexity class than $P$, all of these important problems are not solvable in polynomial time with classical TMs.

Note that the fourth reason is unrelated to how realistic NDTMs are as a computational models (compared to classical TMs or other variants), or to any initial motivation for the invention of the concept. NP-complete problems are just surprisingly common in real life, and the scientific interest in them mirrors that.


Why the pointer in linked list is of structure type?

The nodes in a linked list need to hold two things:

the node's value
a (possibly null) pointer to the next node

That makes them structs, so a pointer to a node is a pointer to a struct.


The maximum number of statements that could be true at the same time

There is a $O(k^4)$ time algorithm that works by considering all possible subsets of three out of the $k$ inequalities, looking at the "intersection point" of those 3 inequalities, and counting how many of the inequalities that intersection point satisfies.

In more detail:

This can be solved if you are familiar with some basic facts from linear programming and the simplex method.  Let $S$ be a set of $m$ linear inequalities in $n$ variables.  $S$ defines a $n$-dimensional polytope.  Then the following fact is useful:

Fact: If $S$ has a feasible solution, then it has a feasible solution that is one of the vertices of the corresponding polytope.

(Recall that a vertex is a single point that is a "corner" of the polytope.  Each vertex can be obtained by taking a subset of $n$ independent linear inequalities from $S$, converting them to equalities by changing $\ge$ to $=$, and solving to find the unique point at their intersection.)

For linear programming, a useful consequence of this fact is that, to find the optimal value of the objective function, it suffices to enumerate only the vertices of the polytope and compute the objective function for each such point.  Here we have no objective function and care only about feasibility, but this basic fact is still useful.

In particular, in your problem we have $n=3$ variables ($x,y,z$) and we want to find the largest possible subset of the inequalities, say $j$ of them, that are all consistent.  Any such subset of $j$ of the given inequalities corresponds to a set $S$ of $m=j+5$ inequalities: namely, the subset of $j$ inequalities, plus the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$.  In this way we get a set $S$ of $m=j+5$ inequalities on $n=3$ variables.  Now if there is a feasible solution to $S$, then one of the vertices of $S$ must be a feasible solution.

Essentially, this means that we can restrict our attention to only the vertices; we can ignore all other points in the polytope.

Of course, we don't know what $S$ is, so we don't know what the polytope is.  Nonetheless, we can still use this fact.  This fact means that we can restrict our attention to only the "possible vertices", where a "possible vertex" is a point that is a vertex of one such polytope.  In other words, consider all possible polytopes obtained by taking some subset of the given inequalities and adding the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$; take the union of the vertices of all of these polytopes.  Then it suffices to look only at these possible vertices -- we don't need to consider any other possible value of $x,y,z$.

How many possible vertices are there?  Well, each vertex is determined by choosing $n=3$ of the inequalities, converting them to equalities, and looking at their intersection.  So, there are only ${k+5 \choose 3} = O(k^3)$ possible vertices.  For each possible vertex, we can count how many of the $k$ inequalities it satisfies, and see which one satisfies the largest number of inequalities.  That one will be the optimal solution to your problem.


Words equal to the concatenation of their odd and even position - characters

It would be more convenient to index word positions starting with zero.
Let us take a look at $L \cap \Sigma^{2^n}$. Any word $w \in L \cap \Sigma^{2^n}$ satisfies
$$
w = w_0 w_2 \ldots w_{2^n-2} w_1 w_3 \ldots w_{2^n-1}.
$$
You can check that for $0 \leq m < 2^{n-1}$ and $b \in \{0,1\}$, this is equivalent to
$$
w_{2^{n-1}b + m} = w_{2m+b}.
$$
In other words, if we think of the index as an $n$-bit string, then this is the same as $w_i = w_{\mathrm{rot}(i)}$, where $\mathrm{rot}(i)$ is obtained by rotating $i$ to the left.

A necklace is an equivalence class of words under rotation. What we have shown above is that $w \in L \cap \Sigma^{2^n}$ iff $w_i$, interpreted as a function $\{0,1\}^n \to \Sigma$, is constant on necklaces. Denoting the number of necklaces of length $n$ by $N_2(n)$, we deduce that
$$
|L \cap \Sigma^{2^n}| = 2^{N_2(n)}.
$$
The explicit formula for $N_2(n)$ shows that $N_2(n) \sim 2^n/n$.

It is known that if $L$ is a regular language then there exists a modulus $m \geq 1$ such that for every $0 \leq i < m$ there exist constants $C,d,\lambda \geq 0$ such that for $N \equiv i \pmod{m}$,
$$
|L \cap \Sigma^N| \sim C N^d \lambda^N.
$$
We can calculate $\lambda$ as $\lim_{N\to\infty} |L \cap \Sigma^N|^{1/N}$ (the limit taken over $N \equiv i \pmod{m}$).

Now suppose that our $L$ were regular. Choose $i$ so that infinitely many values $2^n$ satisfy $2^n \equiv i \pmod{m}$. We have
$$
|L \cap \Sigma^{2^n}|^{1/2^n} = 2^{N_2(n)/2^n} = 2^{O(1/n)} \longrightarrow 1,
$$
and so $\lambda = 1$. However, that implies that $|L \cap \Sigma^{2^n}|$ should have polynomial growth (in $2^n$), whereas it clearly has superpolynomial growth.


examples for: A is mapping reducible to B but B is not mapping reducible to A

I now understand that there is a mapping reduction from the empty language to any other language except Sigma*, and there cannot be a reduction from a language to the empty language except for a reduction from the empty language to the empty language.


Here is a correct version of your result:

If a graph contains no isolated vertices, then every vertex cover is a dominating set.

For the proof, let $G$ be a graph with no isolated vertices, and let $S$ be a vertex cover. In order to show that $S$ is a dominating set, we need to show that every vertex not in $S$ has a neighbor in $S$. Suppose therefore that $v \notin S$. Since $G$ has no isolated vertices, $v$ has some neighbor $u$. Since $S$ is a vertex cover, it must contain one of $v,u$. Since $v \notin S$, necessarily $u \in S$. Therefore $v$ has a neighbor $u \in S$.
A stronger version of this result states that the condition of having no isolated vertices is tight.

Let us call a graph good if every vertex cover is a dominating set.
A graph is good iff it contains no isolated vertices.

We already saw one direction. Now suppose $G$ is a graph containing some isolated vertex $v$. Take an arbitrary vertex cover $S$. Since $v$ is isolated, $S \setminus \{v\}$ is also a vertex cover, but it is not a dominating set, since $S \setminus \{v\}$ doesn't contain $v$ or any of its neighbors (since it has none!).


Both $L_1$ and $L_2$ are decidable. Hence, they have algorithms $A_1$ and $A_2$ (respectively) that decide them.
Try to create a new turing machine (algorithm) using the two algorithms $A_1$ and $A_2$.
For example, for the union $L_1\cup L_2$, you can create the following algorithm:

run $A_1$ on the input. If it accepted, then also accept.
else, run $A_2$ on the input, and return what $A_2$ returned.


Greedy Heuristic for the Traveling Salesperson Problem

First let's name your points $P_A$, $P_B$, $P$, $P_C$, and $P_D$ (from left to right).

With the first heuristic you start at one point ($P$) and move to the closest point. From that new point, you move to the next closest point, and so on and so forth.

With the second heuristic you again start at one point ($P$) but you move to the point closest to one of the two ends of your current path. It is a simple improvement over the first heuristic.

For your example:

Current path: $P$. Closest point to $P$: $P_B$.
Current path: $P-P_B$. Closest point to $P$ or $P_B$: $P_C$.
Current path: $P_B-P-P_C$. Closest point to $P_B$ or $P_C$: $P_A$.
Current path: $P_A-P_B-P-P_C$. Closest point to $P_A$ or $P_C$: $P_D$.
Current path: $P_A-P_B-P-P_C-P_D$. The only choice left is to connect $P_A$ to $P_D$.


every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar

The linked discussion thread comes from comp.compilers, which at one time was the definitive discussion forum for questions of this form (disclaimer: I was a constant reader and occasional contributor to that forum, so my opinion might be biased.)

The rather interesting discussion thread in question dates from October 2002, and was an attempt to discover if there were unambiguous languages (not grammars) which could not be parsed with any $LR$ algorithm. In the course of the discussion, Sönke Kannapinn noted that the $LR(k)$, $LALR(k)$ and $SLR(k)$ sets of languages are identical, for all $k\ge 0$. (That's the message cited in the question, but in a more readable presentation.)

Kannapinn cites the source of his assertion: the 1990 text Parsing Theory Vol II by S. Sippu & E. Soisalon-Soininen, which definitely should be considered a "standard" textbook (as Kannapinn notes in an earlier message in the same thread). The question is addressed in Chapter 6.6 (SLR(k) Parsing, from pages 70-84), which terminates with Theorem 6.71:

  For any fixed $k>=0$, the families of $LR(k)$ languages, LALR(k) languages and SLR(k) languages are all equal.

The proof is too long to reproduce here, but the textbook should be available in any good university library. (If it isn't, demand that they acquire it.)

Coincidentally, there was another similar discussion thread the next year, in which I offered a simpler proof outline. I reproduce it here (without modification aside from an attempt to fight with MathJax and Markdown to make it a bit more readable), in case it's useful to someone, although of course it might be wrong since discussion posts in comp.compiler are not subject to the thorough review accorded to Springer Monographs. So if you find an error, let me know, and if you find the formatting ugly, feel free to fix it.

Take an $LR(1)$ grammar $$G = <N, T, P, S>$$ and create $$G' = <N', T, P', <S,\$> >$$ where $N'$ is a subset of $N \times T$ (that is, the non-terminals in G' are the cartesian product of the original non-terminals and the original terminals.)

$N'$ and $P'$ are constructed basically with the LR construction:

Start with $N' = \{<S, \$>\}$ and repeat the following until no new non-terminals are added:

Let $<A, a>$ be an element of $N'$ for which there are no productions in $P'$. Now, for each production in $P$ of the form:

    $$A \to w_1 w_2 ... w_n$$

    add all possible productions

    $$<A, a> \to w'_1 w'_2 ... w'_n$$

    where

    $$w'_i = w_i \text{ if } w_i \in T$$
    $$w'_i = <w_i, b> \text{ for each } b \in FIRST(w_{i+1}...w_n ++ a)
    \text{ if } w_ \in N$$

    The second definition is multiple valued, so you might have to add a lot of rules :)

    Furthermore, if any new rule mentions a non-terminal $<W, w>$ which is not yet in $N'$, add it to $N'$

It is clear that this must terminate, because all the sets are finite. Also, the function $FIRST$ used above never yields epsilon.

Now, I assert that $G'$ recognises exactly the same language as $G$, and
furthermore that if $G$ is $LR(1)$ then $G'$ is $SLR(1)$, because it is impossible to have a reduce/reduce conflict between $<W, a>$ and $<W, b>$.

Of course, all this has done is move the lookahead sets into the definition of the non-terminals, so the resulting $SLR$ table is going to be just as big
as the original $LR$ table (bigger, actually, since no merging of lookaheads
has been done), but I think it does answer the original question.


Trying to find all possible combinations

This might be a bit advanced for your level (I'm not sure where you're coming from), but this is technically a Knapsack problem. If you're unfamiliar, I suggest first reading a bit from Wiki: https://en.wikipedia.org/wiki/Knapsack_problem

Each of your options has a maximum loss, and some value to you. (I'm not quite sure what your value function here is -- is it the maximum profit? Or maybe $(max\,\,profit - max\,\,loss)/2$?) You have a cap on how much loss you'll assume as risk: your available money. Given that cap, you want to maximize your value.

If you think of the Knapsack as carrying options, then you have a "weight" on each option that is its maximum loss, and your max "weight" you bear is the money you have to risk. You want to maximize the value of your knapsack.

Now, the Knapsack problem is in general NP-hard: this means that no one has a solution to always find the true optimum quickly, and it's unlikely there ever will be. But, there are algorithms that do extremely well for most problems, or give approximate solutions. The Wikipedia article discusses a few.

From a practical perspective, one of the best options is running this as an "Integer Linear Programming" problem, or ILP. Writing your own ILP solver is hard, but there are good software libraries for it. There are also lots of tutorials online about tackling stock portfolio problems with ILP libraries. For instance, a minute of googling "Integer linear progrmaming stock option" took me to https://www.mathworks.com/help/optim/ug/maximize-long-term-investments-using-linear-programming.html, which talks about doing it in MATLAB. You can find many more, probably for Python and Java and R, to name a few likely candidates.


Where in the Chomsky Hierarchy are Regular Expressions as a language?

Are we talking regular expressions as in only union, concatenation and star?

Consider the following grammar:

$R -> a | b | c$

$R -> R+R$

$R -> RR$

$R -> R^*$

$R -> (R)$

This captures all regular expressions. So if we're only talking in the Chomsky hierarchy, then it's clearly context free.
If you allow parentheses, it's not regular, since well-nested parentheses are known to not be regular. If you want a proof, do a homomorphism from the language of REs to the language of well-nested parentheses.

I don't know where they fit in terms of more detailed classification (i.e. $LL(1)$, $LR(0)$ etc.).

You could probably find something about this if you searched for "parsing regular expressions."


Left- and right-linear grammars define regular languages, and it is straight-forward to convert the grammar into a form appropriate to build an NFA which can recognise the language.

That doesn't say anything about the ease of parsing the grammar, in the sense that parsing transforms a string into a parse tree which relates the various syntactic parts of the string. While we can prove that the regular language can be recognised in linear time and constant space, we cannot say much about the parse tree because there is no guarantee that the parse tree for a given string is unique. In other words, left- and right-linear grammars can be, and often are, ambiguous.

What we can say is that the transformation from left- to right-linear form does not preserve the parse tree; if the intention was to build a particular parse of each string, then the transformation will not help us.

Left-linear grammars cannot be parsed with an LL(k) parser, because no left-recursive grammar can be. However, there is no guarantee that the transformed right-linear grammar will be amenable to LL(k) parsing.

Either a left- or a right-linear grammar might be LR(1), although there are no guarantees. (But every LL(k) grammar is LR(k) so a grammar which is not LR(1) is also not LL(1).) If the intention is to parse, and not just recognise, it seems reasonable to use a grammar which actually reflects the intended syntactic structure, to the extent possible given the constraints of different parsing algorithms.

While it is evident that there are people who feel that their failure to understand the LR parsing algorithm somehow makes it less valuable (or even "evil"), that is not borne out by any objective metric: LR(k) parsers run in linear time and space, just like LL(k) parsers, and can be constructed in polynomial time if the grammar is LR(k). There are readily available tools which will compute the necessary tables for an LR(1) parser, and the parsing algorithm itself, given the tables, is just a few lines of simple code.


Why are non-relativizing proofs preferred to relativizing ones?

Let me try to answer your multifaceted question using an analogy from number theory (or rather, Peano arithmetic). The platonist point of view holds that every question about natural numbers has a YES/NO answer. This is known as "true arithmetic". However, as Gödel showed, some propositions concerning natural numbers can be neither proved nor disproved. The platonist point of view still holds that these propositions have a definite truth value with respect to the "true" set of natural numbers; Gödel just showed that the no finite list of axioms1 can specify the true set of natural numbers.

Let's see what this implies regarding the P vs. NP question. The platonist point of view holds that either P=NP or P$\neq$NP. It might be that P vs. NP is independent of the foundations of mathematics (say, ZFC), in which case we will be able to prove neither P=NP nor P$\neq$NP. But according to most researchers, this possibility is unlikely. Therefore we would really like to know whether P=NP or not in the real world, which is the same as2 whether P=NP or not according to the standard foundations of mathematics. This is the research question.

What about relativized models? Let me offer another analogy from number theory. If a polynomial identity is true over the integers then it is also true modulo $p$ for every prime $p$. So in order to disprove an identity, it is enough to show that it doesn't hold for some $p$. We can think of the integers modulo $p$ as a "relativized model". Let's consider an example: $1 + 1 = 0$ modulo $2$ but not modulo $3$. Does it mean that we are no longer sure whether $1 + 1 = 0$ or not? Not at all. We know that $1 + 1 = 2$, and in particular $1 + 1 \neq 0$. But in some relativized models, this equation fails to hold.

The (informal) local-global principle states that in some situations, there is a set of "relativized models" which is complete for some number-theoretic statements. The classical example is quadratic forms: given a quadratic form $Q$ and a number $n$, then $Q$ represents $n$ over the rationals (that is, $n$ is in the image of $Q$ when the inputs are arbitrary rational numbers) iff it represents $n$ over the real numbers and the $p$-adics.

Unfortunately, we have no similar theorems for complexity theory. In particular, given the truth value of relativized statements, we can deduce nothing about the original statement. The situation is even worse: it is not longer the case that a result true in the "true" world also holds relativized to any oracle. So we cannot even expect statements like the local-global principle to hold here.

Something like "relativized techniques" also occurs in Peano arithmetic. There are statements regarding the natural numbers which can be proved in ZFC but not in Peano arithmetic. The classical examples are the Paris–Harrington theorem and Goodstein's theorem. All proofs in Peano arithmetic are "relativizing" in the sense that they hold in all models of Peano arithmetic. The Paris–Harrington and Goodstein theorems fail in some non-standard models of Peano arithmetic, but these don't represent true arithmetic; in true arithmetic the theorems hold. The problem is with Peano arithmetic rather than with the statements themselves: there are some properties of the natural numbers that it doesn't describe, allowing these non-standard models to creep in. Gödel showed that this problem happens in all first-order models of arithmetic.

Now we can address your questions:

Why is a non-relativizing proof of IP=PSPACE preferred over oracle separations of the same two classes? We only care about the question IP=PSPACE? in the "true" world. It doesn't matter what happens in relativized worlds. Since there exist oracles which separate IP and PSPACE, proofs of IP=PSPACE must be non-relativizing. The situation is analogous to the one involving the Paris–Harrington and Goodstein theorems.  A different problem is that it is perhaps not clear how to define the relativized versions of these classes. This precludes presenting relativized results even as evidence.
P=NP holds with respect to some oracle and fails to hold with respect to another; why do we conclude that non-relativizing techniques are needed rather than that oracles lead to inherent contradictions? This is the same as the situation of $1+1 \neq 0$ above. This theorem is true, but has different truth values in different "relativized worlds" corresponding to the integers modulo $p$ for different values of $p$. This means that a proof of $1+1 \neq 0$ must include some step that doesn't hold modulo all $p$. It doesn't mean that working modulo $p$ "leads to inherent contradictions".
Aren't we seeing something similar in the "theory of types" developed in Principia Mathematica? The theory of types was developed as a consistent foundation for mathematics, after Russell discovered that naive set theory is inconsistent (using his paradox). No such foundational difficulties have been encountered in complexity theory.
What are the implications of Gödel's incompleteness theorem? The incompleteness theorem raises the possibility that P vs. NP is independent of the current foundations of mathematics. But this is considered unlikely by most researchers. Many difficult theorems have been proved in the past; some of them had been open for centuries (for example Fermat's last theorem). The fact that a theorem is difficult is no reason to think that it is beyond solution.

This leaves one question which you haven't asked: Why do we care about relativized results? I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results. A good example is the random oracle hypothesis, which states that if a complexity theory statement holds with respect to a random oracle, then it holds absolutely. For example, although the P vs. NP is "undecided" with respect to an arbitrary oracle, Baker, Gill and Solovay showed that P$\neq$NP with respect to a random oracle. Does that imply that P$\neq$NP? The fact that IP=PSPACE disproved this hypothesis. Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

Endnotes:

The usual axiomatization of Peano arithmetic actually uses a finite number of axiom schemes. Gödel's result holds in even greater generality, as Andrej Bauer indicates in his thoughtful comments.
See Andrej Bauer's comments for a dissenting opinion.


First, $NL\stackrel{?}{=} NP$ is still open, so $IS\in NL$ is possible (within our current knowledge, though we believe that they are different).

The problem with your proof, is that when you "guess $k$ vertices", you have to write them in your memory (when we say "guess", we mean that we write a vertex in the working tape, where at each step our machine writes either $0$ or $1$). Keeping $k$ vertices simultaneously (where $k$ is part of the input), requires more than logarithmic space.


How can you see which points in the spectrum is from which pixel in the original image?

As stated by @tomasz, the fourier transform relates only globally to the image since the pixels of the transform correspond to frequencies in the original image
(which you may intuitively understand - somewhat - as speed of color variation as you move on the original image).
This is well explained on the web : An Intuitive Explanation of Fourier Theory

Look in particular at the bottom of the page.


Does this DFA describe this regular expression?

For something to be a DFA, it should have transitions from every state for every letter in the alphabet. Your alphabet is {$a, b$}, so every state should have a transition for $a$ as well as $b$, e.g., your state 2 does not have a transition for $a$. Complete your DFA and you'll get what is that 5th state that you are missing.


Pumping lemma for $\{110^n10^{n-m}1^m: 1\le m<n\}$

You're basically there.  Taking $w=110^{2p}10^{2p−q}1^q$, there are actually three cases (you missed the first one).

$x=\varepsilon$, $y=110^{p-2}$, $z=0^{p+2}10^{2p-q}1^q$.
$x=1$, $y=10^{p-1}$, $z=0^{p+1}10^{2p-q}1^q$.
$x=110^r$ for some $r\in\{0, \dots, p-3\}$, $y=0^{p-r-2}$, $z=0^{p+r+2}10^{2p-q}1^q$.

In all three cases, taking $i=0$ means that the string $xy^iz$ is not in $L$.  I'd suggest trying $i=0$ and $i=2$ as your first two guesses in pumping lemma proofs – one of them usually works.

Notice that nothing above actually depends on the choice of $q$, so you can simplify things very slightly by just taking $q=1$ (or any other fixed, legal value).


Interesting Speedup & Amdahl's law problem

You can calculate the speedup in MFLOPs. Speedup is a dimensionless quantity, so you don't need to know the execution time to calculate it.
You need to know the old execution time only if you need to find out the improved execution time.

In this problem, we can calculate the increase in MFLOPS by dividing the ratio of Floating point instructions to total number of instructions after improvement by the ratio of Floating point instructions to total number of instructions before improvement, since the Cycles Per Instruction is 1 and clock cycle time remains the same.
Increase in MFLOPS = $\dfrac{(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ after\ improvement)} {(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ before\ improvement)} $


Event Prediction through Machine Learning

As usual in these kinds of situations, the best way to find out which machine learning approaches will perform best is to try them out and see which ones work best.  You can evaluate them using cross-validation.

It's unlikely that anyone here will be able to guess what will work best without knowing your data set.  So I recommend that you get to work trying some likely candidates.

The Orange software tool is very convenient for trying multiple different machine learning algorithms on the same data set.


Is zero allowed as an edge's weight, in a weighted graph?

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.

The reason you don't usually see zero-weight edges is that, in most contexts, an edge with weight zero is exactly equivalent to the absence of an edge. For example, if your graph represents countries and the amount of trade done between them, a zero-weight edge would mean no trade, which is the same as having no edge at all. If your graph represents distances, a zero-weight edge would correspond to two places at distance zero from each other, which would mean they'd actually be the same place, so should both be represented by the same vertex. However, in other contexts, zero-weight edges could make sense. For example, if your graph represents a road network and edge weights represent the amount of traffic, there's a big difference between a road that nobody uses (zero-weight edge) and no road at all (no edge).


Hint: try to do each language separately, and then your final grammar is S->S1|S2|S3.

To do your case 2, you can write

$S->aSc|X$

$X->aXb|\epsilon$.

I.e. you start by generating the c's and the exceeding a's, and then you generate the b's and the remaining a.


Placing 1d items in a 2d grid with constraints

The 1-dimensional case (a $1 \times n$ grid) is straightforward.  I'm not sure why you are having difficulty finding solutions when the grid is 1-dimensional.  If you don't have any constraints, then you just add up the lengths of the items; if their total length is $\le n$, you can solve it (just put the items next to each other), otherwise you can't.  To deal with the isolation constraint, you can note that the problem with tiles lengths $\ell_1,\dots,\ell_k$ and an isolation constraint is solvable if and only if the problem with tile lengths $\ell_1+1,\dots,\ell_{k-1}+1,\ell_k$ and no isolation constraint is solvable.

The 2-dimensional case (a $m \times n$ grid) looks much harder.  One approach, in practice, might be to use a SAT solver.  Introduce boolean variables $x_{i,j,k,d}$ and $y_{i,j}$, with the intent that $x_{i,j,k,d}=1$ if the $k$th tile starts at location $(i,j)$ on the grid and proceeds in direction $d$, and $y_{i,j}=1$ if location $(i,j)$ is covered by some tile.  Now you can formulate your problem as a set of boolean constraints on the $x$'s and $y$'s, then feed it to an off-the-shelf SAT solver.  You could experiment with this for the parameter sizes that tend to crop up for you in practice and see how well it works.  SAT solvers often work surprisingly well, though there is no guarantee: they are not a silver bullet, and the worst-case running time will remain exponential.  There are many other ways to represent this as a SAT problem, too, so you could try other representations as well to see which tends to work best with existing SAT solvers.

I'm not sure you're going to be able to do much better than this: as FrankW says, for 2-dimensional grids this smells like it might be NP-complete in the general case.


Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$

For the full proof we should give the definition of the automata: $N = (Q, \Sigma, \delta_N, q_0, F)$ is the original NFA. We yield a DFA via subset or powerset construction: $D = (2^Q, \Sigma, \delta_D, \{q_0\}, \{P \subseteq Q \mid F \cap P \neq \varnothing\})$, with $\delta_D(P, a) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\}$.

Now for the induction:
Base case: $\hat{\delta}_D(\{q_0\}, \varepsilon) = \{q_0\}$ by definition and $\hat{\delta}_N(\{q_0\}, \varepsilon) = \{q_0\}$.
Induction step: Let the statement be true for all $w \in \Sigma^n$, i.e. we land in some set $P \subseteq Q$ (which is a state in $D$). Consider some word $wa \in \Sigma^{n+1}$: $\hat{\delta}_D(\{q_0\}, wa) = \delta_D(\hat{\delta}_D(\{q_0\}, w), a) = \delta_D(P, a) = P^\prime$ with $P^\prime$ as given in powerset construction. By induction hypothesis we have that $\hat{\delta}_N(\{q_0\}, w) = P$ and $\hat{\delta}_N(\{q_0\}, wa) = \{q \in Q \mid \exists p \in P. q \in \delta_N(p, a)\} = P^\prime$.

Original answer for the other direction of the proof

I think you are overcomplicating things here. What you want to show is that if there is a language $L$ recognized by some DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$, then there is an equivalent NFA. From your post I assume, your textbook defines NFAs with transition functions $\delta^\prime\colon Q \times \Sigma \to 2^Q$ (an other possible way would be transitions relations $\Delta \subseteq Q \times \Sigma \times Q$).

So, given DFA $\mathcal{A}$, you can just define the NFA $\mathcal{A}^\prime = (Q, \Sigma, \delta^\prime, q_0, F)$ with $\delta^\prime(p, a) = \{\delta(p, a)\}$ for all $p \in Q, a \in \Sigma$, i.e. always map to the singleton with the only possible state that the DFA would reach (i.e. the transition graph is the same). It is obvious that $\mathcal{A}^\prime$ recognizes the same language as $\mathcal{A}$.

In summary, you may say that DFAs are just NFAs where the transition function maps each state and symbol to a singleton (or rephrasing for transition relations: DFAs are just NFAs where the transition relation ist total and functional).


Find largest subset of vertices in graph so that every pair of vertices have an edge between them

Unfortunately, the answer is no.

In graph theory, such a subset is called a clique. (Essentially, a graph is a set of nodes and a set of edges between those nodes, and a clique is a set of nodes in a graph such that every node in the set has an edge to every other node in the set.) What you want is to find the largest clique in a given graph.

This is called the Maximum Clique Problem, and it's NP-hard. The decision problem version, "is there a clique with size $k$?", is in fact NP-complete. So an efficient solution to the Maximum Clique Problem would prove that P=NP and earn you the $1,000,000 prize and eternal fame.


Problem on finite state machines in the feynman textbook

The numbers are encoded LSB first. In your example, $(00)(01)(10)(11)(10)(00)$ corresponds to the addition $011100 + 001010$, and the answer should be $011001(0)$, corresponding to the binary answer $(0)100110$. The bit in parentheses is the carry bit, which I don't think Feynman intended you to output.

More generally, Feynman wasn't very accurate, so you should think of a reasonable concrete interpretation of the problem which will result in an automaton which has a small number of states; I can think of several, some of which requiring less than four states. (It depends whether $(00)$ is a single digit or a pair of consecutive digits.) I don't think it's very important to guess what Feynman intended exactly.


The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, it may be easier to work from the top downwards to preserve all of the properties of the 2-3-4 tree while giving an extra key to the node you're deleting from. Here are the rules for deletion:

If node containing key has more than one key, just remove the key.
Otherwise, we're trying to remove a 2-node (node containing 1 key). Traverse the path from the root to this node and perform one of the following operations on every 2-node except the root node to transform it into a 3-node or 4-node (node containing 2 or 3 keys):

If node has a sibling that's a 3-node or a 4-node, have the parent steal a key from one such sibling and have the 2-node in question steal from the parent. The child of the sibling key we stole becomes a child of the node we just expanded.
If the node's parent is a 2-node and its sibling is also a 2-node, fuse all three together into a new 4-node. Note that this can only happen when the parent is the root since all other 2-nodes should've already been fixed.
If all of the node's siblings are 2-nodes, steal a key from the parent (we know we can do this because we're converting every node we hit into a 3-node or a 4-node) and fuse together the node, the stolen key, and an adjacent sibling.

So starting from the tree below, we see that 41 is the only key in its node so let's start from the root and perform operations as necessary on the way to 41. We start at the root 53 and do nothing:

    -->   53
        /    \
       /      \
      /        \
    46          60 | 70
   / \         /    \   \
  /   \       /      \   \
 /     \     /        \   \
41     48  55|59    65|68  73|75|79

Then we get to 46 which is a 2-node. One of its siblings has more than 1 key so we perform operation 1. In particular, have the parent steal a sibling key 60 and have the node containing 46 steal 53 from the parent. The original left child of 60 becomes the right child of 53.

              60
            /     \
           /       \
          /         \
   --> 46 | 53       70
      /   |  \       \   \
     /    |   \       \    \
    /     |    \       \     \
   41     48  55|59   65|68  73|75|79

Finally we're at 41 which is also a 2-node and all of its siblings are 2-nodes so we perform operation 3. In particular, we steal 46 from the parent and fuse 41, 46, and 48 into a new node.

                   60
                 /     \
                /       \
               /         \
              53         70
             / \         / \
            /   \       /   \
           /     \     /     \
--> 41|46|48  55|59  65|68  73|75|79

Now the node containing 41 has more than one key so we can go ahead and delete 41.


Help coming up with a solution to a combinatorial problem

One way to solve this is using generating functions.  The number of ways to get the number 6 using "2 additions" of 1, 2, or 3 is the coefficient of $x^6$ in $(x+x^2+x^3)^2$.   This generalizes: the number of ways to get the number $n$ using "$k$ additions" of 1, 2, or 3 is the coefficient of $x^n$ in $(x+x^2+x^3)^k$.  I'll let you play with some examples to see why this is so.

Once you know this fact, you can then use polynomial multiplication and repeated squaring to compute the polynomial $(x+x^2+x^3)^k$ and then read off the answer.

See also Calculating the number of multiplications necessary to evaluate a polynomial.


Check if two items are equal after replacing

I found a solution to my problem. Let's look at the simpler but equivalent problem in which an item is recursively defined as an empty list or a list of items. I'll summarize the algorithm.
Variables:

Int counter starting at 0
Hash map: list of integers $\to$ integer.
The integers represent equivalence classes.

Function find(item) $\to$ int:
Finds the equivalence class of an item. Recursively call find on all the children of item. Now you have a list of ints. If this list of ints is contained in the hash map, return the corresponding value. If not, add the list to the hash map with the counter as value. Increase the counter and return the value.
Function merge(int a, int b):
Merges two equivalence classes a and b. In the hash map, replace all occurences (both in keys and in values) of a by b. Now it can happen that one key is mapped to multiple values. If that happens, again merge those values.  Repeat this until every key maps to a unique value.
Algorithm:
For every rule c = d, call merge(find(c), find(d)). Then to see if a = b, check if find(a) = find(b).


If I understand you correctly, the order of the inputs to function F does not
influence the output W, so order is not important.
I'm deducing this from the three possible subsets in your example  at the top
where K = 2 and N = 3.

For a set of N elements, and a function F taking K inputs where order of
inputs does not matter, the complexity to
find all possible W outputs I don't think is O(N ** K). I'm using ** as to the
power of.

I would think it is  the same problem as finding the number of ways to choose
K elements from a set of N elements disregarding order. I think one could also
say the number of partitions of K elements over a set of N elements.

The number of ways to choose K elements from a set of N elements is:

N // since you are choosing from a set of N elements
* (N - 1)  // since next you are choosing from a set of N - 1 elements
* (N - 2)  // same reasoning as above
...
* (N - (K - 1))  // just before you have chosen K elements
* (N - K)  // you have chosen the K-th element

Sort of like factorial, but from N -  K + 1 up to N, which is the same as N! / (N - K)!.

Lastly,   we have to disregard order of the elements, and there is K! ways to
order K elemetns, which brings us to:

N! / (N - K)! / K!

As each W is calculated you can simply keep the highest yealding inputs, and
when you have tried all inputs you will be guaranteed   to have found the
right set of inputs.

So, supposing the above is correct (it worked for small mental verification of K = 2,
N = 4 and K = 3, N = 4 and K = 3, N = 5) then I suppose the complexity
analysis is O(N! / (N - K)! / K!) and not O(N ** K).

If you know F then you could optimise it, to get a linear improvement, or
maybe find inputs that could be omitted to get an even bigger speedup.

Without knowing F you are stuck with trying everything.

One other thing you could do is employ memoization to avoid having to evaluate
F for similar inputs.


How does this allow list operations to be applied to lists with elements of any type?

Most importantly, Section 11.12 does not introduce polymorphic lists, but introduces monomorphic lists annotated by a type of its elements.

For example, Fig. 11-13 introduces a new term cons[T] t t. Here [T] is a type annotation, which indicates a type of elements of the list. Note that T is a metavariable ranged over types, not an object-level type variable or a type-level abstraction. In other words, it is different statements that "For every type T, the type List T has property P" and "the type of polymorphic lists ∀X. List X has property P". See Section 3.1 for details of metavariables.

I think most of your questions are answered in short by the above explanation. The followings are more detailed answers.

Q1

Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference?

Neither. It introduces monomorphic lists annotated by an element type (No need of type inference).

Q2

What does "For every type T, the type List T describes ﬁnite-length lists whose elements are drawn from T" in Section 11.12 mean?

T is a metavariable. For instance, it implies a type List Bool describes finite-length lists whose elements are drawn from Bool.

Q3

Is [T]  part of the  the names of the list operators, e.g. nil[T], cons[T], isnil[T]?

T is a metavariable. It may give you an intuition to try typing some actual program which contains lists.

Q4

Does Section 23.4 use the same type List T as in Section 11.12?

Yes/No. Both sections try to define the type List T as "a type of lists whose elements are drawn from T", but they define List T individually: List T of Section 11.12 is defined in Figure 11-13, and List T of Section 23.4 is defined informally in sentences.

  ... suppose our programming language is equipped with a type constructor List and term constructors for the usual list manipulation primitives, with the following types. ...

As written in the book, the notation of List T is the same, but list-related primitives are defined differently.

Q5

I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12 cover lists?

Chapter 20 describes a type system to handle general recursive types, rather than a specific recursive type (e.g. List T). Actually the beginning of Chapter 20 takes List T as an example of recursive types.


What are the odds of a collision given a fixed hash table size?

Size of hashtable
When hashing $k$ items into a hash table with $n$ slots, the expected number of collisions is

$n - k + k(1-{\frac{1}{k}})^n$

The main statistic for a hash table is the load factor: $\alpha = \frac{n}{k}$
For a perfect hash the load factor also happens to be the probability that a collision will occur.

Open addressing
Back to the question:

  average time complexity to find an item with a given key if the hash table uses linear probing for collision resolution?

The length of probe sequence is proportional to $\frac{\alpha}{(1 - \alpha)}$. As the load factor $\alpha$ approaches 1, probe times goes to infinite.

The following graph shows the benefits and drawbacks of open addressing quite clearly.

Because of locality of reference open addressing is fast up to 70% load factor, after that running time deteriorates quickly.
Note that the graph only shows cache locality issues. Its for this reason that the chaining times do not go up much. In reality the chaining time goes up exponentially as well when the hash table fills up, albeit slower than the linear probing time.

Let $\alpha$ be the load factor

Double hashing has a time complexity of $O(2 * \frac{1}{2}(\dfrac{\alpha}{(1-\alpha)}))$

Linear probing has a time complexity of $O(1 * (\dfrac{\alpha}{(1-\alpha)}))$

So the time complexities are the same, but the constants are different.
Double hashing takes more time, but linear probing goes into pathological running time sooner as the fill factor goes up.


How many decidable decision problems are there?

There are a countable infinity of decidable problems. There must be at least a countable infinity, because all of the languages $\{a\}$, $\{aa\}$, $\{aaa\}$, ... are decidable. There cannot be more than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string).

There can be no formal language that describes them all without also describing some undecidable problems. This is because the set of decidable languages is not recursively enumerable, but any formal language would give a way to enumerate them. At least, assuming it was decidable whether a string was in the formal language or not. And, if you can't even decide whether a string was in your formal language, it wouldn't be any better as a description than, "The set of all languages decided by Turing machines."


Turing machine that accepts $L = \{a^{n^2} | n ≥ 1 \}$

Note that $1 + 3 + 5 + \cdots + (2n+1) =(n+1)^2$. The input is in unary on one tape, the other tape is a counter, initially containing a single marker. Both heads start at the left of their tapes. A step consists of;

If both heads are at the right end of their markers, quit; input is a square.
Add two markers to the right of the counter tape.
Return to the start of the counter tape.
Advance both heads as long as the counter tape still has unvisited markers.

All you're doing is computing the sum of odd numbers above until you either match the input tape (accept) or exceed it (fail).


Yes, you might be looking it the wrong way.

  If $x$ is larger than the tree's root's key (the median, or equivalently $k>n/2$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find $x$ in depth of $O(\log k)$.

First, let us be accurate. The root's key may not be the median, although it sits roughly in the middle.

Let $r$ be the root node. Let $n$ be the number of nodes in the whole tree and $n_l$ be the number of nodes in the left subtree of $r$. Let $h_l$ be the height of that subtree and $h$ be the height of the tree, so $h\le h_l+2$ since an AVL tree is height balanced.

Suppose $x$ is larger than the root's key.  That means
$$n_l < k \le n.$$ We also have, according to the properties of an AVL tree.
$$\log_2 (n+1)\le h \le h_l+2 \le c\log_2(n_l+2)+b +2\lt c\log_2(k+2)+b +2$$
where $c\approx 1.44$, $b\approx -0.328$. So, for all $k\ge3$,
$$\log_2(n)\le2\log_2(k)$$

So if you have traversed the entire (height) of the left branch in order find the $k$-th smallest element, you will use $O(\log n) = O(\log k)$ steps.

In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $k$-th smallest element, we have just proved that the worst case complexity is always $O(\log k)$


Is the language given by a context-free grammar always context-free?

Hint: A language $L$ is context-free iff there exists a context-free grammar $G$ such that $L = L(G)$. (Some people take this as the definition of context-free languages.)


Minor nit: your first displayed expression should be
$$
T(n) = \begin{cases}
  1 & \text{if $n=0$,}\\
  1 + \sum_{j=0}^{n-1}T(j) & \text{otherwise}
\end{cases}
$$
You can indeed solve this by looking at the recurrence tree, but you don't wind up with your sum of products expression (try it for $n=4$ to see that). For this problem there's an easier way, though:

Hint: What is $T(n+1)-T(n)$?

You can take a look at our reference question, on recurrence relations, as well.


Can I solve my decision problem in $O(n)$ time?

I use set difference to find out if there are any elements in $s$ that don't exist in $A$. This should be $O(n)$ in the best cases if there is a good hash. Since I'm dealing with integers it should be $O(n)$ Explained here

I then use $len(s)$ and $len(A)$ which takes $O(1)$ time according to here.

A = [1,2,3,4,9]
s = [1,2,3,4,9]

elem_not_in_A = set(s) - set(A)

if len(s) >= len(A):
    if len(elem_not_in_A) > 0:
        output False
    else:
        output True
else:
    output False

If the set difference remains $O(n)$ and all the other statements remain $O(1)$ then yes it can be solved in $O(n)$ time.


Algorithm for getting the outer boundary of a large graph

I think you can do this with marching squares, which is both fast and easy to implement.

To use marching squares you need to construct a scalar grid over your domain. Impose a regular grid over your region of interest. For each point in the grid, compute the distance (or time, etc.) between the grid point and your point of interest using a shortest path algorithm. Store this value at that point to serve as the scalar values of your grid. Then apply the marching squares algorithm to generate an isocontour for some isovalue $d$; all points on this contour will be distance $d$ away from your point of interest. More on the details of this algorithm on Wikipedia.

Additionally you can speed up the shortest path computation since your graph is a DAG. First topologically sort your DAG and then relax each edge, like you would in Bellman-Ford, in the order given by the sorting. The correctness follows from relaxing each edge along every path from the source node to every other node. Thus the single source shortest path can be computed for a DAG in $O(V+E)$.


AC-3 is an algorithm for solving CSPs. In order to use it solve a question, you need to present the question as solving a CSP.
In your case, the CSP is on four variables $P,M,O,D$ ranging over $\{0,1,2\}$. The constraints are:

$P \neq M$.
$D > O$.
$D \neq P$.
$D \neq M$.
$(P = O) \Rightarrow P = 1$.
$(P \neq O) \Rightarrow (P = 2 \lor O = 2)$.

We can convert them into the following explicit constraints:

$(P,M),(D,P),(D,M) \in \{(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)\}$.
$(D,O) \in \{(1,0),(2,0),(2,1)\}$.
$(P,O) \in \{(0,2),(1,1),(1,2),(2,0),(2,1)\}$.

You can now take any implementation of AC-3 and simply run it on these constraints.


Why cannot Operand forwarding remove all RAW hazards?

Sure!
And I can assure that is a fairly good question, if you are not able to see all the combinations.
See, operand forwarding can indeed remove all RAW hazards inside CPU but it is helpless when not all execution inside the CPU.
What I mean is all the RAW hazard scenarios, that we can write involving REGISTERS only and execution is some ALU operation, operand forwarding can escape the hazard.
like:
r1 <- r2 + r3            : I1
r4 <- r1 - r3            : I2
r1 is being calculated in ALU for I1, while I2 needs to load r1 as operand for ALU. Here the trick is even though you load the operands of ALU for execution, bt ALU will first execute I1 and then I2 in that order. So, even though r1 is not ready at the assigned time for operand fetch phase of I2, but it will be available before ALU starts execution of I2, and thus taking the benefit of same fact:

CPU notes that I2 is wanting the ALU execution output as an operand.
So, CPU saves this information as setting a bit inside the circuitry. And allowing I2 to proceed with "OPERAND FETCH PHASE" while skipping fetch of I2.

(Fetch of I2 is actually done, when CPU sees the RAW and sets the bit, but that's just assurance of fetch done, NOT THE ACTUAL FETCH)
THIS IS OPERAND FORWADING!
Now as soon as ALU computes the value, as the bit of oprand forwarding is 1, it transfers the contents of ALU output to the ALU operand.
(NOW THE GUARANTEE HAS BEEN COMPLETE, AND r1 for I2 has been fetched).
But observe, the write to r1 by I1 may be not done yet and in next cycles this be done. But I2 might be in ALU execution phase at this cycle.
So, as the FUTURE OPERAND(r1) is inside CPU and ALU being sequential, we could solve RAW.
But the problem is with LOAD/STORE involved in RAW.
load r1, Address1        : I1
r3 <- r1 + r2            : I2
Now the ALU for I2 can't get r1 before complete I1 is executed and r1 has been really written into.
So, this time "OPERAND FETCH PHASE" of I2 will have stall and can't proceed.
Hope this helps.


Devise a backtracking algorithm to allocate $p$ projects to $s$ students

I didn't get what you're exatly asking for? Backtracking is the solution. Are you looking for an actual implementation or an explanation of backtracking? Or a  better  performing approach in terms of runtime.

Here my pseudo code how I would generate all matching solutions.

state = [];  //array representing the current state, assigns students to projects

S = [..];    //array containing the students
P = [..];    //array with students
func assign(level) {
  if(level == S.length) {
    if is_valid_state() //ensure each project has at least one student
      output(state);
  }
  for(i = 0; i < P.length; i++) {
    state[level] = i;
    assign(level+1);
  }
}

level(0)

Can of course  be optimized by moving the final condition atop, but this would be my first thought of how to solving this the least efficient way (in terms of performance).


Does this A-Star heuristic already exist?

This idea is called True Distance Heuristics and as you suspected, it can be very efficient.
True Distance Heuristics
True Distance Heuristics (as well as "Pattern Database") is a technique that utilizes the memory to help with the search. The general idea is "let us pre-compute a few important accurate distances, to save a lot of time during the search".
This is also sometimes referred to as "Memory Based Heuristics".
Each technique has different memory requirements and require a different heuristic function (that, of course, may utilize the original heuristic function).  Also, some of course might be more beneficial in specific domains.
Differential
This technique suggests to choose k "pivot" states and store the shortest path from every state to each pivot
Canonical
This consists of 2 different data-sets:
Primary data: choose k pivot states and calculate all pairs shortest path among all of these k states.
Secondary data: From every node (out of all possible nodes), store distance to the closest canonical node.
Others
There are many other memory based techniques that uses this concept. Many prove themselves to be very beneficial, for a relatively small price to pay (in terms of space).
Food For Thought
As you suspected, these techniques can have admissible heuristics. Since it seems that you are interested in this field, I'll let you figure out the right heuristic functions on your on. I'll give you a hint that the formal proof uses simple math. Feel free to ask for these functions in the comments, and I'll answer.
I strongly suggest to draw these out in a simple drawing, it will make everything very clear.


Prove that the total distance is minimised (when travelling across the longest path)

Let $x$ be a vertex of your tree and consider a shortest route that visits every vertex and returns to $x$. It's easy to see that, regardless of the choice of $x$, any minimal route walks along every edge exactly twice: it must use each edge at least twice, or it wouldn't be able to get back to $x$; if it uses an edge more than twice, you can rearrange to avoid the backtracking.  Therefore, all such minimal routes have the same length, regardless of the choice of $x$.  Call that length $L$ (which is $2(n-1)$ if the tree is unweighted and there are $n$ vertices, but this isn't important).

Now, given a minimal route from $x$, let $y$ be the last vertex to be visited for the first time (i.e., the vertex which, when you first visit it, you say "Aha, now I've been to every vertex!").  The minimal route visits every vertex on its way from $x$ to $y$, and then returns immediately to $x$ along the unique shortest path.  Let $L_{xy}$ be the length of the walk taken from $x$ to $y$.  We know that $L=L_{xy}+d(x,y)$, and $L$ and $d(x,y)$ don't depend on how we got to $y$, so $L_{x,y}$ also doesn't depend on the route and we can say that $L_{xy}$ is the length of any minimal walk from $x$ to $y$ that visits every vertex.

The vertex $y$ must be a leaf: if it wasn't, when you first visited $y$, you wouldn't have visited any of the vertices "beyond" it.  Further, for any leaf $z$ of the tree, there are minimal routes from $x$ back to itself such that $z$ is the last vertex visited for the first time: let $v_1v_2\dots v_t$ be the path from $v_1=x$ to $z=v_t$ and don't go to $v_{i+1}$ until you've already visited every other descendant of $v_i$.

So, to get the longest walk from $x$ that visits every vertex, pick a route whose $y$ is the leaf at greatest distance from $x$.  None of the above depends on which vertex was chosen as $x$, $L_{xy}=L-d(x,y)$ is minimized by choosing $x$ and $y$ to be the vertices at greatest possible distance in the tree, which are both leaves.


Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain of $n/2$ nodes where the remaining $n/2$ nodes are attached as a balanced tree at the bottom of the chain. This gives every leaf depth $n/2+\log_2(n)=\Theta(n)$ With $n/4$ leaves at depth $\Theta(n)$ we have $\Theta(n^2)$ runtime for step 3 in this case. This is asymptotically the worst case since we have $n$ nodes at max depth $n$.

There's a better way to do this. Lets define a function $f$

$
f(v) =  \begin{cases}
v & \text{if}\quad \texttt{height}(v.left) = \texttt{height}(v.right) \\
f(v.left) & \text{if}\quad \texttt{height}(v.left) > \texttt{height}(v.right) \\
f(v.right) & \text{if}\quad \texttt{height}(v.left) < \texttt{height}(v.right)
\end{cases}
$

If the heights of the children of a node $v$ are the same, then clearly $v$ is the LCA of the deepest nodes of the subtree rooted at $v$. If the left subtree is taller, then we want the LCA of the deepest nodes of the subtree rooted at $v.left$, since they are deeper than the deepest nodes in the subtree rooted at $v.right$. The same logic follows for $v.right$ when it is taller.

The values for $\texttt{height}$ and $f(v)$ can be computed in a post-order traversal of $T$ in linear time.

Calling $f(root)$ should return the LCA of the deepest nodes in the tree.


First of all, the complement of a set is only defined when there is an (understood) universal set. In this case, the universal set is probably the set of all context-free grammars, but it could plausibly be the set of all grammars.

The complement of a set $A$ given a universal set $U$ is defined as the set of elements in $U$ but not in $A$; it is understood that all elements in $A$ are also in $U$. So if $U$ is the set of all context-free grammars, then the complement of ACFG is the set of all context-free grammars $G$ such that $L(G) \neq \Sigma^*$.
If $U$ is the set of all grammars then the complement of ACFG is slightly more complicated: it consists of all non-context-free grammars together with all context-free grammars $G$ such that $L(G) \neq \Sigma^*$.

If $G$ is a context-free grammar and $L(G) = \emptyset$ then $G$ certainly belongs to the complement of ACFG1; but other context-free grammars also belong there.

1This actually depends on your definition of grammar and on the value of $\Sigma$. If $\Sigma$ is understood and non-empty then what I wrote is correct; if $\Sigma$ is part of the grammar and is always non-empty, again what I wrote is correct; but if $\Sigma$ could be empty, then $\Sigma^* = \emptyset$, so what I wrote is wrong.


Algorithm to select sets of objects while maximizing number of objects covered

The problem you're describing can be seen as the weighted independent set problem, as follows: Construct a graph $G=(V,E)$, where every node $v$ in $V$ corresponds to your sets of objects. The nodes $v,w$ have an edge in $E$ if and only if they share an object. The weight of each node is the number of objects contained within the corresponding set.

Now, observe that maximizing the amount of objects used corresponds to finding a set of nodes in $G$ such that 1. none of the nodes are adjacent and 2. the sum of weights over these nodes is maximized. This is precisely the weighted independent set problem.

Unfortunately, this problem is NP-hard, which means an exact efficient algorithm is unlikely to exist (and even less likely to be found). This means that, unless you only have to deal with small values, you would either have to resort to heuristic or approximation algorithms, of which there are a few in the literature. It may be possible that only a particular kind of graphs arise (e.g. trees). In that case, there may be an efficient algorithm, but that depends on your input.


Scheduling: Existence of specific total order

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it.

Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological sort.

Here is an other attempt at a proof:

Let $\leq$ denote a partial order on $X$. I claim there exists a total order $\leq'$ compatible with $\leq$ such that the following never occurs:
$a\leq'\alpha\leq'b$
where $a \leq b$, and $\alpha$ is incomparable to both $a$ and $b$.
(Note that when I say comparable/incomparable I always mean with respect to $\leq$)

To see this choose a compatible total order $\leq'$ with the least amount of such "bad" pairs $(a\leq b)$. Suppose that this amount is non-zero and let $(a\leq b)$ be such a pair with smallest $a$ (with respect to $\leq'$). Let $\alpha_1 \leq' \alpha_2 \leq'\ldots\leq'\alpha_k$ denote all elements between $a$ and $b$ which are incomparable to both $a$ and $b$.

Now create a new total order $\leq^*$ from $\leq'$ by moving all $\alpha_i$'s right in front of $a$ to get $\alpha_1 \leq^* \alpha_2 \leq^*\ldots\leq^*\alpha_k\leq^*a$, the rest remaining unchanged. Notice that this is still compatible with $\leq$, as the only thing that could have gone wrong is that there was some $a\leq c \leq \alpha_i$ but this is impossible as $a$ and $\alpha_i$ are incomparable.

Notice also that, because all elements between $a$ and $b$ (with respect to $\leq^*$) are now comparable to $b$, we have created no "bad" pair $(\alpha_i\leq x)$ with $a\leq^* x \leq^* b$, otherwise we would have $\alpha_i\leq x \leq b$ meaning that $\alpha_i$ and $b$ are comparable. And we have created no "bad" pair $(x\leq a)$, otherwise $(x\leq b)$ would have been a bad pair to start with, contradicting our choice of $a$. Any other type of "bad" pair we created must have already existed previously.

Because $(a,b)$ is no longer a bad pair, $\leq^*$ has strictly less bad pairs than $\leq'$, which is impossible by definition of $\leq'$. Thus, $\leq'$ had no bad pairs to start with.

It is easy to show from here that $\leq'$ meets your requirements.


Name for the tree formed after collapsing cycles

For any given undirected graph $G$, the cycle graph $C(G)$ has vertices which correspond to the chordless cycles of $G$, and two distinct vertices of $C(G)$ are adjacent if and only if the corresponding chordless cycles have at least one edge in common. [1]

Judging from your example, you are interested in a similar notion for a directed graph.

[1] S.V. Gervacio. Cycle graphs. Lect. Notes Math. 1073, 279-293 (1984)


Short answer: Proof by induction is correct because we define the natural integers as the set for which proof by induction works.

On your interpretations and examples

Your understanding seems broadly correct, though there are a few places where your statements are not fully rigorous. Given that we're talking about logic, getting things precisely right is important.

You should mention that you're working in the domain of integers (naturals, to be precise, which are the nonnegative integers). Induction doesn't work on many larger domains such as real numbers.
When proving a property of the form $\forall n \gt 0, \ldots$, the case $n=0$ does not come up. The basic induction principle applies to all natural numbers: if $P(0)$ and $\forall n \in \mathbb{N}, (P(n) \to P(n+1))$ then $\forall n \in \mathbb{N}, P(n)$. Other statements such as “if $P(1)$ and $\forall n \in \mathbb{N}, (n \ge 1 \to (P(n) \to P(n+1)))$ then $\forall n \in \mathbb{N}, (n \ge 1 \to P(n))$” are also true (and easy to derive from one another).
“$P(n)$ is valid for $n:=n+1$” is not a rigorous statement since the last occurrence of $n$ is not covered by any quantifier. The proper way to write this is “for any natural $n$, if $P(n)$ holds then $P(n+1)$ holds”.
Regarding your second question, it isn't clear what you mean by “and, in fact, …”. It is not the case, for example, that $P(0) \wedge (\forall n \in \mathbb{N}, P(n) \to P(n+2))$ implies $\forall n, P(n)$ — these hypotheses only prove that the property holds on even integers.
Finally, this isn't a matter of rigor, but your choice of example is odd, as $n^2$ is normally defined as $n*n$ — so after expanding the definition, the property to prove becomes $\forall n \gt 0, n * n = n * n$, which doesn't need induction. A better elementary example would be $\forall n \in \mathbb{N}, n + 1 = 1 + n$.

The Peano axioms

Now, to turn to why proof by induction works. It is impossible to answer this question rigorously without explicitly stating how the natural numbers are defined, or what properties of the natural numbers we define. Many definitions exist.

One definition of the natural numbers is the Peano axioms. There are many minor variants of the Peano axioms; one (which assumes equality as a preexisting notion) is:

$0$ is a natural.
For every natural $n$, $S(n)$ is a natural.
For every natural $n$, $0 \ne S(n)$.
For every natural $n$ and $m$, if $S(m) = S(n)$ then $m = n$.
Let $P$ be any unary predicate over the naturals. Suppose that $P(0)$ is true and that for every natural $n$, if $P(n)$ is true then $P(S(n))$ is true. Then for every natural $n$, $P(n)$ is true.

The first two axioms describe ways to build naturals. The next two axioms state that naturals built in different ways are distinct. (Exercise: find a model where all the axioms hold except for #3. Maybe a bit harder: find a model where all the axioms hold except for #4.)

As you can see, with this axiomatisation of the naturals, the induction principle is an axiom.

If you try to define the naturals as a subset of the reals, you'll run into foundational trouble: where do the reals comes from, and how do you prove properties of them? For example, it's difficult to reason about sequences of reals (or anything else) without induction.

The most common foundation of mathematics is set theory, specifically, ZF (Zermelo-Fraenkel). From ZF, a common way to define naturals is as Von Neumann ordinals:

$0$ is the empty set: $0 := \varnothing$
the successor of an ordinal is the union of that ordinal with the singleton containing it: $S(n) := n \cup \{n\}$.

The existence of the empty set is guaranteed by any set theory that proves the existence of at least one set and even a weak version of the axiom of comprehension. The existence of a successor is guaranteed by pairing to prove the existence of $\{n\}$ (which is an abbreviated notation for the pair $\{n,n\}$), and one to prove and union to deduce the existence of $n \cup \{n\}$. This suffices to prove the existence of all the natural numbers.

In order to prove that all the natural numbers form a set, an additional axiom is needed. It can be stated as “the natural numbers form a set”. Usually, the axiom is formulated as “the exists an inifinite set”. This more general formulation does not guarantee that the natural numbers obtained by this construction form a set — there are models of ZF where the smallest infinite set contains more than just zero and its successors, called non-standard models. I won't dwell on these models; doing logic in these models tends to be somewhat non-intuitive, but they are nice in that they allow rigorous reasoning about “infinitesimally large” integers, and from there about infinitesimally small numbers such as the $\mathrm{d}x$ in $\dfrac{\mathrm{d}x}{\mathrm{d}t}$ beloved of physicists.

Let's call a set $x$ supernatural (this is not standard terminology) if it contains $0$ and if for any $y \in x$, $S(y) \in x$. A supernatural set contains all the naturals, and perhaps more. A common formulation of the axiom of infinity is that there exists a supernatural set; we'll assume that. Let $\mathbb{O}$ be a supernatural set.

Now let $\mathbb{N}$ be the intersection of all the supernatural subsets of $\mathbb{O}$. Since all the supernatural sets contain $0$ and there is at least one element in the family ($\mathbb{O}$ itself), $0 \in \mathbb{N}$. For any $n \in \mathbb{N}$, $n$ is a member of each supernatural subset of $\mathbb{O}$, therefore (by definition of supernatural sets) so is $S(n)$. Thus $\mathbb{N}$ itself is supernatural. We'll call this set the set of naturals. Intuitively speaking, $\mathbb{N}$ is the smallest set containing the naturals (though without further axioms it is not necessarily unique, e.g. in nonstandard models).

$\mathbb{N}$ satisfies the induction principle. To see this, consider a predicate $P$ over the naturals, such that $P(0)$ is true and for all $n \in \mathbb{N}$, $P(n)$ implies $P(n+1)$. Let $\mathbb{N}_P$ be the set of naturals that satisfy $P$, i.e. $\mathbb{N}_P = \{n \in \mathbb{N} \mid P(n)\}$. Then $\mathbb{N}_P$ is a supernatural set, so $\mathbb{N} \subseteq \mathbb{N}_P$ by definition of $\mathbb{N}$.

Other foundations of mathematics

There are foundations of mathematics that are not based on set theory. What you consider the foundations vs derived theorems is not important: as long as you prove that your foundations are equally consistent with one of the commonly accepted ones, you're doing the same mathematics as everyone else. The definition of $\mathbb{N}$ as a set of ordinals is merely one way to construct it. The Peano axioms (or any equivalent formulation) are the specification of the naturals, and it is this specification that defines $\mathbb{N}$, rather than any particular construction.

In particular, constructive foundations of mathematics tend to treat the naturals as the most fundamental notion, and the induction principle on naturals, or on some more general structures, as a foundational axiom. For example, in homotopy type theory, the Peano axioms are a consequence of the rules for constructing functions by recursion. In intuitionistic type theory with inductive types (e.g. in the calculus of inductive constructions, which is the foundation of the Coq proof assistant), the induction principle on naturals is an instance of the more general induction principle that holds on any constructed type.


$\mathsf{BPP=NEXP}$ is consistent with our current knowledge, thus, since $\mathsf{EXP, NEXP}$ are not low for themselves, it is not known whether $\mathsf{BPP}$ is low for them. A positive answer would imply $\mathsf{BPP\neq NEXP}$, and a negative answer would imply $\mathsf{P\neq BPP}$ (and in turn, that $\mathsf{P\neq NP}$), so currently, if you're looking for unconditional results, you will have no luck with $\mathsf{BPP}$.

Since even a (possibly weak) class as $\mathsf{BPP}$ is not known to be low for $\mathsf{EXP}$, you will need to look between $\mathsf{P}$ and $\mathsf{BPP}$ (which does not give you much wiggle room), or for classes who are currently incomparable with $\mathsf{BPP}$ (such as $\mathsf{QP}$ as you yourself noted, I doubt you can find a significantly stronger low class for EXP).


It depends on the exact definition of $k$-SAT that's being used.  If $k$-SAT is defined to have clauses of length at most $k$, your reduction is perfect; if it's defined to have clauses with exactly four distinct literals, then you're out of luck.


generalizing ball-bin problem to k-universal family

Let $B_j$ be the number of balls in the $j$'th bin. Then
$$
\mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] =
\sum_{i_1 < \cdots < i_k} \Pr[h(i_1) = \cdots = h(i_k)] =
\frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}.
$$
Let $C_j = B_j - (k-1)$. Then
$$
\mathbb{E}\left[\sum_{j=1}^n C_j^k\right] \leq k! \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] \leq n,
$$
and so with probability at least $1/2$,
$$
\max_j C_j^k \leq \sum_{j=1}^n C_j^k \leq 2n,
$$
hence $C_j \leq (2n)^{1/k}$, implying that $l_{\max} \leq (2n)^{1/k} + k-1$.


Another version of the online set cover problem?

A simple adversary argument shows that you must take every set you are offered, unless it's entirely covered by elements already taken. Indeed, otherwise there must be some element $x$ which hasn't appeared before; perhaps it will never appear again, so you must take the set.

Consider now the following instance:
$$
\{x_1\},\{x_2,\},\ldots,\{x_{m-1}\},\{x_1,\ldots,x_m\}.
$$
The algorithm takes all $m$ sets, but the last one would have sufficed. This shows that the approximation ratio can be as bad as $m$, the number of sets.


Is there a polynomial algorithm for optimal sorting on trees?

This problem is called Token Swapping, and you can find more information if you search by its name on google.

I couldn't find a proof that it is NP-complete on trees, but I've found a recent paper that gives a 2-approximation algorithm for trees:
http://erikdemaine.org/papers/TokenReconfiguration_FUN2014/paper.pdf