Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

SMT solver is a SAT solver + decision procedure

A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible":

  The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment

  — (wikipedia)

This means that SAT solvers can also give the satisfying assignment, in addition to deciding the problem.

TL;DR SMT solvers solve a generalization of the SAT problem, depending on the types/constraints allowed in the theory. Furthermore, they also allow encoding of higher level type-relationships than the SAT encodings allow.

A SAT solver usually deals with many single boolean variables, that are related only through the clauses/constraints of the CNF. A QF_BV (quantifier-free bitvector) theory SMT solver is basically a SAT solver + more information about the relationships. For example, a QF_BV SMT solver is reducible to SAT1. So why use a QF_BF SMT solver? The the major advantage is that in SAT, an integer is represented by different variables, that at first glance might appear unrelated. A SAT solver would spend much time relearning simple relationships, like $(A = B) \wedge (B = C) \implies (A = C)$ on an integer level, while the SMT solver knows that the individual bits are related this way from the outset, because the QF_BV SMT language is on an integer level (fixed bit-width). Thus a QF_BV SMT solver can reason on the integer level, in addition to the bit level.

See Beaver SMT solver which can even output the equivalent SAT problem that would need to be solved.

While the QF_BV SMT solver has this advantage over a SAT solver, I don't think this is a complexity advantage: they both essentially equivalent and take exponential time to solve their worst-case problems. But practically, a QF_BV SMT solver might be much quicker due to this extra knowledge. See my answer to Limits of SMT solvers, for an example of something considered "hard" that (current) QF_BV SMT solvers and SAT solvers would both choke on.

There are also SMT solvers that try to solve even tougher problems than Boolean Satisfiability (for example allowing types and constraints on reals, or allowing quantifiers); obviously these are theoretically at least as slow as a SAT solver. These SMT solvers are a solving a generalization of the SAT problem; instead of using binary variables, each "theory" allows relationships/constraints over different domains, such as reals, or quantified (for-all) constraints.

  Theorem prover

A automated theorem prover is a solver that given some sort of proof system, some assumptions, and a goal to prove, will "fill in the gaps" between the assumptions and the goal. It will also have some sort of verifier to check proofs (which runs quickly). A theorem prover can rely on a SAT solver to fill in the blanks; in fact, if $P=NP$ and there is a practical algorithm to solve NP-complete problems, one can potentially prove almost all useful provable things (in reasonable time):

  But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook, [19]

    ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.

  — (wikipedia)

  [19]: Cook, Stephen (April 2000). The P versus NP Problem. Clay Mathematics Institute (PDF).

The reason this would work is because "formal proofs can easily be recognized in polynomial time" via the verifier, and $P=NP$ would imply that that problems that can be verified in polynomial time can be answered in polynomial time as well.

But for now, automated theorem mostly provers use heuristics or exponential time algorithms (but are still helpful).

  Constraint solver

These are usually reformulations of the SAT/SMT solvers into other languages. If you've ever use any SAT/SMT solvers to solve a problem, you can really get to love the non-deterministic ability of the solvers. That is, instead of telling the computer how to do something, you tell it what you want, ie. what properties you want the output to have, and a SAT/SMT solver will in a non-deterministic "fill it in", without bothering you with the implementation details. This sort of programming paradigm is very appealing, and is called constraint programming, and to run, it must use a constraint solver (which might use a SAT/SMT solver in the backend, depending on the types and constraints it allows you to use).

  But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms.

AFAIK, Z3 is a suite of many tools, including a SMT solver, several theorem proving/model checking languages, and more.

  And what is the most general term for all of them?

I think the generalization of the satisfiability problem is Satisfiability Modulo Theories, and so "SMT solver" would be the most general of all of these. However, not all actual SMT solver implementations solve all the theories, so this doesn't mean that all SMT solvers are equally general.


Oven cooking queue problem: need help to determine its nature

This problem is NP-hard: it is a more general version of Minimum Multiprocessor Scheduling. You should not expect efficient algorithms that compute the optimal solution in all cases.

The main difficulty is finding out what is the "best" oven in which to cook an ingredient. Once you know (in some way or the other) which ingredients should go in which oven, you can not go wrong by queueing them based on their preparation time.

So one way to compute the best solution is as follows: perform a cycle in which you try all possible assignments of $K$ ingredients to $N$ ovens, which is $N^K$ possibilities. For each of these possibilities, compute the solution based on queueing by preparation time in each oven. The best of all solutions you generate is the optimal solution. This of course will only be practical if $N$ is very small (like in your example) and $K$ is also small.


Can one reduce a problem of unknown complexity to a hard problem to show hardness?

The proof is not correct.  As you've indicated the reduction needs to go in the other direction, i.e. integer programming must be reduced to their problem, not the other way around.


Why don't computers use the same architecture?

Why aren't all cars identical? Wouldn't that make easier to build and repair them?

There are big and small cars, cheap and expensive cars, fast gas guzzlers and slow energy savers… And similarly there are many different types of computers.

Here are a few criteria that influence the architecture of a computer. Optimizing for some of the criteria will have a cost against some other criteria.

Speed to execute sequences of integer operations
Speed to execute sequences of floating-point operations
Speed to execute sequential computations that require a lot of memory
Speed to make parallelizable integer computations
Speed to make parallelizable floating-point computations
Speed to make parallelizable memory-intensive computations
Power consumption when idle
Peak power consumption
Ability to scale power consumption according to the amount of computation at a given time
Special-purpose computations (graphics processing, cryptography, digital signal processing, …)
Volume
Design cost
Per-unit manufacturing cost for large amounts
Per-unit manufacturing cost for small amounts
Possibility to connect many peripherals
Ability to execute tasks in real time, i.e. fine control over the execution time of each operation (e.g. to control a physical object)
Isolation between tasks (for robustness and security)

This is of course not an exhaustive list. In practice, you'll find architectures that find a few sweet spots, optimizing for some criteria at the expense of others.

Here are a few examples of different compromises.

Intel x86 processors tend to be very good at raw speed for sequential execution of pure computation and memory accesses. ARM tend to be less fast, but consume less power, which is a large part of why x86 is so common on computers that are plugged into the mains while ARM is prevalent on computers that almost always run on battery such as mobile phones.
GPU are very good at executing many tasks in parallel, which is well-suited to drawing images that consist of millions of pixels. But they're bad at accessing lots of memory in random ways, so they don't make good general-purpose processors.
An MMU translates memory addresses used by programs into memory addresses used by the hardware. This allows the operating system to execute programs each in their own address space, so that they don't interfere with each other. This means that each memory access can take a variable amount of time, though, which is why most processors designed for real-time systems don't have an MMU.
FPGA are extremely flexible processors — you can reconfigure them to optimize them for whatever computation you want to do today. But they aren't cheap.

Add to that historical factors. Designing a new processor architecture takes years of effort by teams of hundreds or thousands of highly-trained engineers, and changing architectures involves rewriting a lot of software, so it doesn't happen often. So just like you can have different car models from different manufacturers that have the same strengths and weaknesses, you can have different processor architectures from different manufacturers that vie for the same applications.


Both a language and its complement are not context free

Yes, there is.
Consider the language $L = \{a^p \mid p \text{ is prime}\}$ which is not contextfree, neither is its complement. Both statements are very easy to check via Pumping-Lemma.


Calculating match % and ranking according to that

There is probably no algorithm that is significantly better than doing a pairwise comparison between all pairs of users.

You can, as you say, memoize (remember) the top-5 match for each user, so that you never have to recompute the top-5 for that user again in the future, but you'll still need to compare that user to each other user at least once.  Basically, each time a new user appears, you compare them to all other users, to compute their top-5 matches (and update the top-5 matches of other users by adding this user to the top-5 lists of other users where appropriate).

That's basically the brute-force algorithm.  I don't expect there to be an alternative that is better in practice.

In principle, there are a variety of methods.  One method is to use a locality-sensitive hash.  The simplest form of LSH is to choose a random subset of questions, then for each user extract their answers to those questions, hash that, and store the user in a bucket associated with the user's hash value.  Then two users who are very similar have a decent chance of ending up in the same bucket.  If you construct 100 such data structures, each with a different subset of questions, and if you choose the parameters right, you might have a decent chance of finding all of the top-5 matches in this way (along with some other extraneous matches, but those can be filtered out by doing a full comparison for each potential match).  However, this is pretty fiddly with respect to parameters, and if people tend to answer only some of the questions, I suspect it won't perform that well in practice.


Difference between $F(n)=O(n)$ and $F(n)\le O(n)$?

The notations $f(n) = O(n)$ and $f(n) \leq O(n)$ mean the same thing. Sometimes want to emphasize that the asymptotic estimate is coarse, and then you can use $\leq$, for example $\log n \leq O(n)$. This is not too common if all you're doing is just stating a single estimate, but is more common in a long calculation in which some steps are equations and some steps are inequalities, for example
$$ H_n + 5n = \log n + O(1) + O(n) \leq O(n). $$
In this particular example a simple equality would be more common, but in more complicated situations you could see an inequality. It is up to the authors' personal style. As a reader, you can just ignore this distinction.


Yes. $P \subseteq P/\text{poly}$.  In particular, every polynomial-time algorithm can be simulated by a family of polynomial-sized circuits: the circuit just emulates the behavior of the algorithm.  That this is possible should be pretty clear from the fact that we execute algorithm on CPUs, which are themselves complex circuits built of gates, so it's perhaps not surprising that you can emulate the algorithm in a circuit whose size is not too much larger than the running time of the algorithm.  See, e.g., Why does a polynomial-time language have a polynomial-sized circuit?, https://cstheory.stackexchange.com/q/6721/5038, Why isn't P and P/poly trivially the same?, https://en.wikipedia.org/wiki/P/poly, How to relate circuit size to the running time of Turing machine.


Does a generator really stops the execution at the machine code level, and does it not use the stack?

It depends on the language implementation, but most do it by packaging the local variables of the generator function, together with the instruction pointer from where the last yield occurred, into a heap-allocated closure object. This is what is inside the opaque "generator object" that represents the stream of values in the language. The heap variables representing the saved instruction pointer and generator function locals are updated in place whenever the generator function yields, and reloaded to resume execution of the generator function whenever the next value is demanded from the generator.

It is important to remember that, when you get down to the machine code level, the computer has no concept of a "stack" and a "heap". Those are abstractions added by programming langauge runtime environments on top of the fundamental concepts of contiguous RAM and goto.

Generators are another feature that language runtimes can implement on top of these basic primitives. So the literal answer to the question "Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?" is yes, absolutely.

Generators are an instance of a more general concept called continuations and the call/cc operator. A continuation is often implemented as literally the state of the stack and instruction pointer packaged into a heap-allocated object.

Note that most programming language specifications allow the implementation total latitude as to how memory management works as long as the semantics of the language are conformed to. This is important for the implementation of lazy functional languages, which generalize the generator concept so that all data structures and subexpressions are generated lazily by default. These languages often have implementations that barely resemble the C locals+malloc model. Check out Simon Peyton Jones's books on the implementation of functional programming languages and the Spineless Tagless G-machine for more info. 1 2 3


There is no nontrivial monoid in LI. LI is actually a (pseudo)-variety of finite semigroups: it is the class of finite semigroups $S$ such that, for every idempotent $e \in S$, $eSe = e$. If $S$ is a monoid, you can take $e = 1$, the identity of the monoid and get $S = 1S1 = 1$ so the monoid has to be trivial.


How can we find the number of pairs of intersecting ranges on a circular number line?

This is solvable in $O(n \log n)$ time, too, by considering the complement of the intervals that wrap around and using a suitable data structure.
There are two types of intervals that can appear on a cycle:

Intervals that do not wrap around: e.g., $[0.3,0.5]$ does not wrap around.  In general, this includes all intervals of the form $[a,b]$ with $0\le a \le b \le 1$.

Intervals that wrap around: e.g., $[0.8,0.1]$ wraps around; it is equivalent to $[0.8,1.1]$ or $[0.8,1] \cup [0,0.1]$.  In general, this includes all intervals of the form $[b,a]$ with $0\le a < b \le 1$; each such interval is equivalent to $[b,1] \cup [0,a]$.

Let $A$ denote the set of intervals that do not wrap around, and $B$ the set of intervals that do wrap around.  Also, let $\overline{B}$ denote the complements of the intervals in $B$, i.e., $\overline{B} = \{\overline{b} \mid b \in B\}$.  For instance, the interval $[0.8,0.1]$ wraps around; its complement is $(0.1,0.8)$, which does not wrap around. It is easier to think about intervals that do not wrap around, and this decomposition  will help us to deal only with intervals that do not wrap around.
Now, we will separately count the number of overlaps between (1) an interval in $A$ and an interval in $A$;
(2) an interval in $A$ and an interval in $B$;
(3) an interval in $B$ and an interval in $A$; and
(4) an interval in $B$ and an interval in $B$.
(1) can be counted with your sweepline algorithm, as we don't need to deal with wraparound.  (4) can also be counted in the same way, as two intervals overlap iff their complements overlap.  I will show below how to count (2); case (3) will then follow by symmetry.  This covers all the cases, so it suffices to count up these four cases and sum them up.
Note that intervals $a \in A, b\in B$ overlap iff $a$ is not a subset of $\overline{b}$.  So, it suffices to count the number of pairs $a \in A, \overline{b}\in \overline{B}$ where $a$ is a subset of $\overline{b}$; then you can subtract that from $|A| \cdot |B|$.
To do that, you can use the data structure in Data structure for interval subset queries.  Store all the intervals $\overline{B}$ in the data structure.  Then, for each $a \in A$, count the number of intervals in $\overline{B}$ that $a$ is a subset of.  This can be done in $O(\log n)$ time per query interval $a$, for a total time of $O(n \log n)$.
Therefore, you can count each of the four cases in $O(n \log n)$ time, and thus compute the overall sum in $O(n \log n)$ time as well.  I think.  I encourage you to check my reasoning to make sure I haven't made any mistakes.


Need clarification about the use of Big-O to describe matrix sparsity

What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. For example:

  Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.

What this really means is:

  For every $C > 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.

The constant hidden inside the big O depends on $C$.

A similar convention explains the following sentence:

  There is a function $f\colon \{0,1\}^n \to \{0,1\}$ whose maximal influence is $O(\log n/n)$.

(The meaning of maximal influence is not important here.) What this really means is:

  There is a sequence of functions $f_1,f_2,\ldots$ such that $f_n\colon \{0,1\}^n \to \{0,1\}$ and the maximal influence of $f_n$ is $O(\log n/n)$.

Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.


Recurrence for quaternary search algorithm

Your recurrence is wrong, which is why you get the wrong answer. I suspect that the reason your recurrence is wrong is that you don't quite understand the algorithm. Try mimicking your reasoning on binary search until you successfully get the correct running time in that case.

Moreover, as mentioned in the comments, the running time (assuming constant-time comparisons and the RAM machine model) is $\Theta(\log n)$, but cannot get more accurate than that. To get $\log_4 n$ you need to count something more specific, such as the number of comparisons performed by the algorithm.


Heterogenous and Asymmetric Computing's differences

Heterogenous computing as opossite to homogenous or symmetric means that processing units differ, which is exactly the same as asymmetric (which is just not symmetric).
But there are more usage differences - asymmetric computing (processing) is more about different CPUs which are used to perform assigned tasks, in embedded systems this is by design, in general purpose by executing in given context, commonly about "local" environment.
Heterogenous is used to talk about tasks computed on different processing units (CPU, GPU and dedicated hardware), also used to describe distributed systems where processing takes place on totally random devices connected.

To make it full - symmetric means exactly the same vector, while homogenous is less strict and requires the results to be the same among devices (the same floating point representation), but does not require exact devices.


Non-quadratic search for specific difference between elements in sorted array

I know of two.

Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the difference of the pointed-to elements is too small, and the right pointer leftward whenever it is too large; the invariant here is that any satisfying pair must be taken from the interval of elements spanned by the 2 pointers.
Build a hash table containing every element as key (the value for each key is unimportant), then loop through every element $x$
again, checking whether $x+d$ or $x−d$ is in the hashtable.


You want to assign $n$ persons to $m$ groups, so that

Each person is assigned one group.
Each group is assigned at most two people.
For each possible person $i$ and group $j$ there is a score $C_{ij}$, and you want to maximize the sum of scores of all assignments.

If such an assignment is at all possible, then $n \leq 2m$.
Create an instance of the usual assignment problem (in which we are looking for a one-to-one correspondence between persons and groups) as follows:

There are $n$ real persons $1,\ldots,n$ and $2m-n$ dummy persons $n+1,\ldots,2m$.
There are $2m$ groups, composed of two copies of the original groups: $1,\ldots,m$ and $m+1,\ldots,2m$.
The costs $C'_{ij}$ of the instance are: for $i \in \{1,\ldots,n\}$ and $j \in \{1,\ldots,m\}$, define $C'_{ij} = C'_{i(j+m)} = C_{ij}$, and set all other costs to zero.

Every feasible solution of the original problem translates to a feasible solution of the new problem with identical cost, and vice versa.


It sounds like you found the answer yourself, you are describing Vertex Cover, which in many ways are very similar to Independent Set, both problems are NP-complete.
The relation to Independent Set is that in a graph $G = (V,E)$, a set $S$ is a minimal vertex cover if and only if $V \setminus S$ is a maximal independent set.
If you know that Independent Set is NP-complete, then it follows that Vertex Cover is NP-complete too.
In other words, you are also looking for a maximum Independent Set.
Vertex cover.  Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at most $k$ such that all edges in $G$ are incident to a vertex in $S$?
Independent set.    Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at least $k$ such that the induced graph $G[S]$ has no edges?


Does proofs are programs apply to any functional program?

In Haskell there are more programs than there are Coq proofs because Haskell has general recursion whereas Coq does not. (In fact Coq allows you to extract proofs into Haskell code.)

The reason that Coq does not have general recursion is that with it we can "prove" anything, simply by saying "to prove $t$ just make a recursive call to itself":

proveAnything :: t
proveAnything = proveAnything

In some languages, for instance in OCaml, you can't do it this way so you have to go indirectly through a recursive function call:

let rec proveAnythingAux _ = proveAnythingAux ()
let proveAnything = proveAnythingAux ()

This shows that type theory can be used for many things, two of which are programming and logic. The difference between these two is general recursion: we want it in programming but it makes logic inconsistent.


Data structure for maintaining large space-efficient filtered array

There is a simple and clean solution that satisfies all of your requirements.

To delete elements, you scan the set of array indices (from 1 to $n$), querying the filter on each and deleting each element that is to be deleted, compacting the array as you go (to shift everything after the deleted element forward one slot).  The deletion operation can be implemented in $\Theta(n)$ time, with a single linear scan.  This satisfies all of your requirements.  (Note that you did not specify any restriction on the running time of the deletion operation.)  In particular, it is space-efficient: it does not require any extra space (it has 0 space overhead, since after deletion, all of the space that's not in use for storing undeleted array elements is immediately available for other use).  Looking up the $i$th element of the array takes constant time, thanks to the compaction: you just index into the $i$th element of the compacted array.

If for some reason this solution is not acceptable to you, then you need to re-think the requirements more thoroughly and edit the question to pose the exact set of requirements more carefully.

Given the problem as you've stated it, I don't think it will be possible to do better than this trivial solution.  You can't do better than $\Theta(1)$ time for lookup.  You can't do better than 0 space overhead.  And I don't think you can do better than $\Theta(n)$ time for deletion, given how you specified the interface to deletion (which works by specifying a filter that is an oracle that, on input $i$, tells you whether index $i$ should be deleted or not).  Even just figuring out which elements of the collection to delete requires querying the filter on all $n$ possible indices, which takes $\Theta(n)$ time.  So, I don't think you can do any better than $\Theta(n)$ time for the deletion operation -- and in particular, I don't think you can do any better than the above scheme, at least not with this specification of how the filter is provided.


Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

There probably will be no formal proof; probably the only way to tell which is better is through experiments.

But some intuition seems possible.  $h_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is treated the same as a tile that is far away from where it belongs.

In contrast, $h_2$ does take this information into account.  Instead of treating each tile as either "correct" or "incorrect" (a binary decision), $h_2$ introduces shades of grey that take into account how far the tile is from where it belongs.  It seems plausible that this might possibly yield some improvement.

Of course, the only way to find out which one actually works better is to try the experiment.  But this might give some intuition about why one might reasonably hope that $h2$ could be potentially be better than $h_1$.


So, there are two distinct uses of the word "map", that I'll unpack here.

The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to $2x$", then we're saying $\forall x \ldotp f(x) = 2x$.

This usage includes "memory mapped IO:" there is a (conceptual) function associating each piece of memory with a particular IO action. Nobody actually ever writes out the function, but it is indeed there: for each piece of mapped memory, there's some IO associated with it. Maybe a part of a disk, maybe a hardware register on a peripheral, etc.

Likewise, bit arrays (and arrays in general) fall into this: each index has a single element associated with it (at any given time), so an array is effectively an encoding of a finite-domain function.
In functional programming and derivatives (such as MapReduce), map refers to applying a transformation across a structure.

The original map comes from Lisp, where it referred to the function that took another function and a list, and returned the result of applying the function to each element of that list.

But, this phenomenon is quite general. In Haskell, a data structure that admits such an operation is called a functor, and the operation is called fmap (for historical reasons, to avoid conflicts with the list map).

These all are related through the concept of a Functor from category theory, which is an abstraction of structures admitting a "map" operation.


The difference between $\beta$-reduction and $let$

In the untyped lambda calculus, $\mathsf{let}$ is indeed useless, and most presentations leave it out. But in many typed lambda calculi, $\mathsf{let}$ is useful because it has a more general typing rule.
The best known example is the Hindley-Milner type system, which derives its power from let-polymorphism. In $(\lambda x.e_1) \: e_2$, the expression $e_1$ has one particular type, which is also the type of $x$ when typing $e_1$. But in $\mathsf{let} \: x = e_1 \: \mathsf{in} \: e_2$, $e_1$ can be polymorphic, and the instances of $x$ in $e_1$ can have different specializations of this polymorphic type.


Difference between Bayesian Networks and Dynamic Bayesian Networks

A DBN means that your model is replicated over each time discrete time step t, called slice. Variables of each slice can be connected together, as well a from previous slice to a latter slice (in this precise direction only). The probability tables and links remain the same in each slice if the model is stationary, which is the default case (otherwise they are a function of t).

In a 2TBN (2-step Timeslice Bayesian Network), there are links only between the previous and current slices.

For more information c.f. section 3.2 of http://journal.frontiersin.org/article/10.3389/fncom.2014.00131/full


How to write program to list all the function values without repeating?

You can implement your task by keeping track of the values that have appeared so far. You maintain an array $S$ that starts empty. You compute the values $f(0),f(1),f(2),\ldots$, and for each value, you check whether it is already in $S$; if so, you don't do anything; otherwise, you print it, and add it to $S$.


Consider using the definition of Big-O. If $f(n) \in O(g(n))$, then there exists a $c, n_0 > 0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$. Similarly, we can write a similar inequality for $g(n)$. We have that if $g(n) \in O(h(n))$, then there exists a $d, n_1 > 0$ such that $g(n) \leq dh(n)$ for all $n \geq n_1$.

To show what you are trying to show, consider putting both pieces together. Not only do we know that $f(n) \leq cg(n)$, but we also know that $g(n) \leq dh(n)$. Putting these two together gives $f(n) \leq c'h(n)$ where $c' = c \cdot d$, for the appropriate conditions. Can you verify what those are? In particular, for what values of $n$ does this hold?

From there, the desired result follows by definition of Big-O.


Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

Here is a natural approach to explore the extreme case.

Let node $r$ be the root of a red-black tree.

Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height.

Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of the nodes among red-black tree of the same black height.

Now let $h=1,2,3,\cdots$ be larger and larger. Can you see the trend?

Here is a related exercise.

Exercise (red-black trees may not be weight-balanced). Given $\alpha\lt 1$, show that there is a red-black tree which has a proper subtree that has more than $\alpha$ of all nodes.


Enumerating weighted permutations in sorted order problem

Seems like a straightforward recursive algorithm, combined with streams (also known as lazy lists or generators), should work.  i.e.,

def subsets(m, S):
  if m==0:
      return [{}]
  if S is empty:
      return []
  s = min(S)
  S' = S \ {s}
  T = subsets(m, S')
  U = [u.union(s) for u in subsets(m-1, S')]
  return merge(T, U)

With the obvious definitions and Python-ish notation.  This returns a list in the desired order, i.e., a list of subsets, sorted by the sum of the elements in each subset.  Here I haven't provided the merge routine, but it can be implemented using the standard algorithm for merging sorted lists.

For clarity of exposition, I've written the above using lists and list comprehensions.  However, for an actual implementation, you should use streams (e.g., Python generators and generator comprehensions) rather than lists.  If you do that, there's no need to build all of the lists and represent them in memory; the algorithm shown above can proceed in a streaming fashion.

This is the kind of problem where a language with explicit support for lazy evaluation will shine.  With lazy evaluation, I believe you can implement a beautiful, elegant solution that looks clean but has excellent memory complexity.


There is no notion of quantification in the standard $\lambda$-calculus as introduced by Church. As far as I can tell from Liang's paper, it deals with a specialized version of $\lambda$-calculus in which $\lambda$-expressions can be logical expressions containing quantifiers and logical connectives. This approach is meant as a way of formally representing natural language statements. Thus, we are really dealing with an applied $\lambda$-calculus with function symbols that correspond to logical connectives and function symbols and are to be interpreted in this way.


You can for instance take as ground truth data the movielens dataset, remove some rating links between users and movies. You can rank your algorithm by counting the number of link that you can guess right. Usually machine learning algorithm also guess the rating score.


Good resources for understanding semidefinite relaxation for combinatorial problems

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys is an excellent handbook on approximation algorithms. It has an entire chapter devoted to the topic of SDPs. As of now you can download the older version directly from their website; however the printed text is pretty affordable.


The second NFA doesn't accept $100$. Make sure that you understand when an NFA accepts a given word. In this case, your NFA gets stuck at the very first character, since there is no transition labelled $1$ from the initial state.


Can someone explain why there are two summations here?

And why are they exactly the same? I showed a math professor and he
  thinks they're labelled wrong but couldn't figure it out. I don't even
  get why there are two.

When in doubt, check the book's errata (Page 4).

  $$ \sum_{R(j)} a_j = \Bigg( \lim_{n\rightarrow \infty} \sum_{\color{red}{{\substack{R(j)\\-n\leq j<0}}}} a_j \Bigg ) + \Bigg(\lim_{n\rightarrow \infty} \sum_{{\substack{R(j)\\0\leq j< n}}} a_j \Bigg) $$

Because $R(j)$ is a relation involving $j$, so you must check whether it's satisfied for negative values as well.

The previous paragraph also has a typo:

  $$ \color{red}{\sum_{j=1}^{\infty} a_j} = \sum_{j\geq 1} a_j = a_1 + a_2 + a_3 + \cdots $$


Intuitive description for training of LSTM (with forget gate/peephole)?

LSTM is designed to process a stream of data chunks (each chunk being the set of inputs for the network at this point in time) that arrive over time and observe features occurring in the data and yield output accordingly.  The time lag (delay) between the occurrence of features to recognize may vary and may be prolonged.

One would then train the network by streaming training examples in randomized ordering which should also have some timeshift noise added in the form of idle passes (have the network activate when inputs are at default idle values eg: when no audio in the case of a speech processor) [exception: if any training data should obey periodic timeshift patterns such as music then the timeshift noise should keep the timeshifting synchronized eg: in music making sure a start-of-measure training example isn't shifted to mid-measure and so forth]

It is possible also to have a semi supervised setup where the network is always in a training configuration and it's trained with examples that expect output of an idle value when no feauture is present or the appropriate expected value when a feature is presented to train).

If feedback format training is desired it can be emulated by:

saving the internal state (time t)
activating the network on current inputs (now at t+1)
supervisory process evaluates the output obtained at t

3a if correction is needed first rewind to the saved state (rewinds network back to t)
3b generate a training example with the correction
3c run a train (backprop) pass for this slice rather than an activation

thus one implements a feedback style system since training examples are basically only created while the network is "getting it wrong."  The feedback format is useful if one wants the network to attempt improvisation (like Schmidhuber's music example).

it should be pointed out that part of the correction feedback (and thus training examples) necessarily includes those that enforce idle valued output when features are not present at the current time

It was mentioned by the OP that [there is no separation of inputs] except that actually there is.  If one thinks of a voice recognition scenario one has periods of utterances (features the LSTM should detect) interspersed with long periods of silence.  So to address the concern it would be fair to say those periods of silence are in fact separating the sequenced groups of inputs (those silences too are actually a feature the network needs to detect and learn to respond with idle valued outputs ie: learn to do nothing when silence).

A note about resetting of the network

Any reset or recalling of a saved network state in the LSTM sense has a meaning of "go back in time" thus undoing any learning the LSTM performed prior to the reset.

Thus you were correct in stating LSTMs are not reset prior to each training sample nor tranining epoch.  LSTMs want their data streamed, or provided in an 'online' manner, so-to-speak.


Is it possible to make a grammar LL($1$) which recognizes palindroms?

No. The language of palindromes over any alphabet with at least two elements is not deterministic, and thus has no LR or LL grammar.
The language of even-length palindromes $L_{epal}=\{ww^R \mid w\in\Sigmạ^*\}$  is a classic example of a non-deterministic context-free language, and you can find the outline of a proof in Hopcroft & Ullman (and other standard texts). The restriction to even-length palindromes simplifies the proof, but it can be extended to the language of all palindromes $L_{pal}=\{w \mid w=w^R, w\in\Sigmạ^* \}$. Without doing more work, though, it's evident that $L_{epal}=L_{pal}\cap (\Sigma\Sigma)^*$, and deterministic CFLs are closed against intersection with regular languages.


A general algorithm for greedy algorithms

There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued mostly by Borodin and his coauthors.

Before discussing the work of Borodin et al., let me briefly mention the subject of matroids and greedoids. They answer the following question:

  Consider the greedy algorithm for maximizing a linear objective subject to constraints. For which constraint structure does this algorithm produce optimal results?

We can think of the constraints as a set system, any member of which is a feasible solution. For hereditary set systems (any subset of a feasible set is feasible), the greedy algorithm produces an optimal result if and only if the constraints form a matroid. Greedoids answer a more refined question.

Back to Borodin's priority algorithms. The exact definition of a priority algorithm depends on the context, but here is a general flavor. There is some iterative procedure for constructing a solution for a given instance. The instance consists of a set of objects (think scheduling algorithms). At each step of the procedure, the algorithm chooses an ordering of all objects, and the best available object according to the ordering is added to the solution set. All objects incompatible with this object are thrown out, and the following iteration is executed. The process stop when the set of available objects becomes empty.

What I described above is the adaptive priority model. In the fixed priority model, the ordering is chosen once and for all rather than at each step. In both models, the algorithm is not allowed to look at the set of available objects (that would be cheating).

The situation for graph algorithms is somewhat more complicated, see for example Borodin, Boyar and Larsen, Priority algorithms for graph optimization problems, and there are several models which are more realistic than the model considered above. There are several other variants of priority algorithms which can be explored through the relevant work of Borodin and others.


UCT (Upper Confidence bounds applied to Trees)

This result is stated in:

Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.

It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.

The main reference for this is:

Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3), 235-256.

To give you some intuition about the convergence given infinite time, you need to understand the UCB1 formula: it makes a tradeoff between exploring the best move and exploring the least explored moves. As the term for exploring the least explored move can grow arbitrariy large and the payoff is smaller than 1, if you have infinite time, you will end up exploring it infinitely many times, even if its payoff is $0$.

Therefore, at a fixed node, given infinite time, you will explore infinitely many times each possible move. Repeat this by induction : you will explore the whole tree in infinite time. So in the end, what actually matters is the score of each node, as the exploration bias will go to $0$.

In short : what removes the MCTS flaw is the fact that you have infinitely many moves, it removes the randomness.


Expressing division in relational algebra in terms of other operations

Let $R(A,B)$ and $S(B)$ be two relations. Division should find all values of A in R that are connected with all values of B (in S). Think $AB\div B=A$.

Question 1: Yes. $R\div S=\pi_A(R)-\pi_A(\pi_A(R)\times S-R)$

Question 2:

$\pi_A(R)\times S$ : this contains all possible AB pairs.

$R$ : this contains the actual AB pairs.

For the values of A that are connected to all values of B, after we do the difference, those will be gone. In the difference $\pi_A(R)\times S-R$ there are only values of A that are NOT connected to all B.

The rest is obvious.


Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification

To compute the probability for $\geq n$, you first compute the probability for an unbounded until and subtract from it the probability for $\leq n-1$. If you compare the sets of paths these formulas represent then you will that they are indeed the same. You start off with a set of all paths satisfying "reach B via C", let's call it $T$. From this set, you remove any paths where B is reached in $\leq n-1$, let's call it $U$. So the set of paths where B via C is reached in $\geq n$ steps is represented by $T \setminus U$. Using properties of probability measures, you can write $Pr(T\setminus U) = Pr(T) - Pr(U)$.

You can safely assume that $B$ and $C$ are disjoint without loss on generality. If  they are not, then reaching a state from $B \cap C$ satisfies the "until", so you can just consider $(C\setminus B) \bigcup B$.


Syntax directed translation part of which compiler phase?

I do not have the dragon book with me so my answer may be off. But generally speaking the syntax directed translation means that you start with a sequence of token (so right after the lexer) and produce something. The translation is said to be directed by the syntax because the something must be produced in a very specific way. For each grammar rule, the translation defines the translation of the left-hand-side nonterminal as a function of the right-hand-side nonterminals' translations, and the values of the right-hand-side terminals.

Here is an example. If you have the following grammar rule:
$$stmt \rightarrow\boldsymbol{if}(expr)\text{ }stmt\text{ }\text{ }\boldsymbol{else}\text{ }stmt$$
And if we denote by $[\cdot]$ the translation then the above rule generates the translation rule
$$[\boldsymbol{if}(e)\text{ }s_1\text{ }\text{ }\boldsymbol{else}\text{ }s_2]=T_{if}([e],[s_1],[s_2])$$
where $T_{if}$ if the translation action for this rule.

One obvious use of SDT is to generate the AST of the input. In which case $T_{if}$ would look something like (I use ML-like syntax)
$$T_{if}(e,s_1,s_2)=AstIfNode(e,s_1,s_2).$$
But they are other possibilities. Furthermore, it is possible to generate an AST with attributes so that we can perform semantic analysis at the same time. For example if we have the rule
$$expr\rightarrow expr\boldsymbol{+}expr$$
then a translation for a "calculator-like" language could be
$$T_{+}(e_1,e_2)=\begin{cases}\{type=int,val=e_1.val+e_2.val\}&\text{if }e_1.type=int\text{ and }e_1.type=int\\\{type=error\}&\text{otherwise}\end{cases}$$

If we start to have identifiers, then we can attach a symbol table to the nodes. For a simple language you can build an entire compiler with a SDT (one-pass compiler), going from source code to machine code. But more advanced compilers usually just use SDT to produce an AST and then do more complicated things (notably they modify the AST).


Does the language of Regular Expressions need a push down automata to parse it?

You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques.

One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma on $(^p)^p$.

That said, you probably do not want to code a PDA by hand. Consider using a parser generator like ANTLR or byacc. If, on the other hand, you want to investigate the parsing of languages by programming parsers yourself, you should continue with other basic parsing algorithms such as CYK, Earley, recursive descent and LR.


How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

This answer assumes that $T(w)$ is the set of inputs that the Turing machine $M_w$ halts on.

Given a Turing machine $M$, construct a new Turing machine which runs $M$ in parallel on all inputs. Once $M$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.)

In order to run $M$ on infinitely many inputs, you do the following:

Start with some enumeration $x_1,x_2,\ldots$ of all inputs.
Run $M$ for one step on $x_1$.
Run $M$ for one step on $x_1,x_2$.
Run $M$ for one step on $x_1,x_2,x_3$.
And so on.

This is known as dovetailing.

The argument above reduces $L$ to the halting problem, and so shows that $L$ is r.e. We can also reduce the halting problem to $L$, hence showing that $L$ is r.e.-complete. To do this, suppose that we are given a Turing machine $M$ as input to $H_0$. We construct a new Turing machine which:

On input $\epsilon$, transfers control to $M$.
On input $0,00,\ldots,0^{41}$, halts.
On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H_0$.


Why does PCP theorem imply that NP problems are hard to approximate?

Take as an example SAT. The PCP theorem (in one formulation) shows that there is a PCP for SAT which uses $O(\log n)$ bits of randomness, queries $O(1)$ places, always accepts on YES instances, and rejects on NO instances with probability at least $\alpha > 0$. The PCP queries at most $2^{O(\log n)} = n^{O(1)}$ different locations in the proof, so the entire proof can be encoded in polynomial size. For each of the $2^{O(\log n)}$ possible queries, we can write a formula of constant size that is true if and only if the verifier accepts. Taking all these formulas together in CNF form, we get a CNF $\psi$ (which depends on the instance of SAT) on polynomially many variables (representing the bits of the proof) with polynomially many clauses (each possible query gives rise to $O(1)$ many clauses).

By the definition of PCP, for each $\phi \in \mathrm{SAT}$, there is a proof that satisfies the verifier on all possible queries. In other words, $\psi$ is satisfiable. On the other hand, for each $\phi \notin \mathrm{SAT}$, every proof is rejected with probability at least $\alpha$. This means that any assignment satisfies at most $1-\alpha/O(1)$ of the clauses of $\psi$, the $O(1)$ factor coming from the fact that the result of each query is encoded using $O(1)$ different clauses, one of which must be falsified if the query leads to rejection by the verifier.


Equivalence of NFA and DFA - proof by construction

It is true that this construction may result in a DFA with unreachable states. The general construction begins simply by including all possible states, then adding the appropriate transitions, so typically the resulting DFA won't be the smallest DFA that accepts the same language (in terms of the number of states).

An alternative approach is to only add states as you generate the transitions (rather than adding all states at the start). This will give you only reachable states, but even then, this DFA may not be the smallest possible.

Nonetheless both approaches result in a DFA that accepts the same language as the initial NFA.

Thus given an NFA with $q = |Q|$ states, we can always generate a DFA with $2^{q} = |\mathcal{P}(Q)|$ states that accepts the same language as the NFA.

Generating the minimal DFA is a slightly different question (but we know that it will have no more than $|\mathcal{P}(Q)|$ states).


Checking whether an integer is a square or higher power

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it suffices to consider only prime $k$. Given $k$, we compute $\sqrt[k]{n}$ using binary search or using some fixed-point iteration such as Newton's method. Either way, we find a candidate for $\sqrt[k]{n}$, and can check whether $(\sqrt[k]{n})^k = n$ or not. For more details on computing $\sqrt[k]{n}$, consult for example this paper (mentioned in Ricky Demer's deleted answer), Step 1.


For anyone visiting this thread in the future, FIFO can have less page faults in some scenarios.

In this one ( <2, 6, 5, 7, ..., ..., ...> ), it can be completed with 2, 8, 6.

The access of 2 means that the least recently used page is 6, but the first page in is still 2.

The access of 8 replaces 2 in FIFO, but 6 in LRU.

The access of 6, therefore, is a hit with FIFO, but a miss with LRU.


In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions?

To be precise, the nodes represent the blocks (consisting a set of statements) and the edges represent possible data flow (the execution path).
Now basically the data flow analysis gives the information regarding the definition and use of data in the program  (Available Expression, Reaching Definition, Live variable).  This information is needed for code optimization.
And moving on to the graph theory applications in the compiler design, I would say Register allocation is the best example (Btw this can be done after gathering information from the data flow analysis).
This is a vast area, not easy to explain everything clearly. So, I would highly recommend to read a good book on compilers to get deeper insights


What is the difference between Big-O and worst-case run time?

Wikipedia says:

  Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

So it is not the definition of the "worst case".

Wikipedia defines best, worst, and average cases as

  In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

By resource we usually refer to time or/and space (memory) required to solve a certain problem.

It also says:

  Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case - for example, the worst-case scenario for quicksort is $O(n^2)$, but the average-case run-time is $O(n\log{n})$.

To sum up: Big-O notation is a pure mathematical concept and notation, which is used in Computer science to express the worst-case scenario for a given algorithm.

Here we have some useful posts:

How does one know which notation of time complexity analysis to use?
How do O and Ω relate to worst and best case?
Sorting functions by asymptotic growth


I do not understand your notation, but the $\beta$-rule is not right (because you write down abstractions). It is:
\begin{align*}
\mathtt{natrec} \; 0 \; x \; f &= x \\
\mathtt{natrec} \; (\mathtt{succ}\;n) \; x \; f &= f \; n \; (\mathtt{natrec} \; n \; x \; f)
\end{align*}
where $x$ and $f$ are arbitrary (well-typed) terms. (Beware: not every term of a function type is of the form $\lambda x . e$!)

You can read $\beta$ rules as saying what happens when you apply a destructor to a constructor (for instance $\mathtt{fst} (a, b) = a$). An $\eta$-rule says what happens when you destruct a thing and then put it back together (for instance $u = (\mathtt{fst}\;u, \mathtt{snd}\;u)$.

We take numbers apart with $\mathtt{natrec}$ and put them together with $0$ and $\mathtt{succ}$, so the $\eta$-rule would be:
$$\mathtt{natrec} \; n \; 0 \; (\lambda \; x\; m \,.\, \mathtt{succ}\; m) = n.$$


Operation with second-order logic formulas

Out of the standard logical operations ($\lor$, $\land$, $\neg$, $\implies$), the only ones that meet your conditions are $\lor$ and $\implies$.


Is A times B of NP-complete languages A and B necessarily NP-hard?

Yes, the problem remains NP-hard. Reducing to $A\times A$ doesn't exactly solve the problem, since you want to reduce to $A\times B$.

However, you can proceed as follows: since $B$ is NP-hard, then $B\neq \emptyset$. Thus, there exists $w\in B$. Fix such $w$. We now show that $A\le_p A\times B$: given input $u$, the reduction outputs $\langle u,w \rangle$.

Clearly this can be done in polynomial time, since $w$ is fixed.

Now, since $w\in B$, then $u\in A\iff \langle u,w \rangle\in A\times B$, and we're done.

As for your question "where is my colleague wrong": you can indeed verify in polynomial time whether $\langle u,v \rangle\in A\times B$ if you are given witnesses for the membership of $u\in A$ and for $v\in B$. This shows that $A\times B\in NP$, but it has nothing to do with hardness.

Intuitively, membership in NP is an upper bound on the complexity, whereas NP-hardness is a lower bound.


Knapsack Problem with Constraints on Item Values

Yes your algorithm runs in $O(n)$ time if you use the median of medians algorithm.
You can prove that to yourself by looking at your algorithm and noting that in every loop the size of the array we are considering is cut in halve. And the runtime of the loop body is $O(n)$ (if we use median of medians and array copying/filtering is $O(n)$ anyway). Now we get the following sum:
$$\sum_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum_{i=0}^{\infty} \frac{n}{2^i} = n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$
The $\log(n)$ comes from the fact that you can only divide the array size $log(n)$ times in halves until you arrive at $1$ (because $2^{\log(n)} = n$). Every term of the sum expresses the cost of one execution of the loop body.


Find Index In Sorted Array Such That A[i] = C1 * i + C2

Finding i such that A[i] = i, where A is a sorted array, needs to check every single array element in the worst case. Choose an array where A[i] = i-1 for every i except that A[k] = k for one single k. If you looked at any number of array elements other than A[k], every single one of the remaining elements could be the one you are looking for.
Now replace every array element with A[i] * C1 + C2, and unless C1 = 0, you have exactly the same problem.
Of course you can be optimistic, and often you will find i a lot quicker. Let's say you have array elements a[1] to a[1000], and you find that a[500] = 770. You now know that 1 <= i <= 499 or 770 <= i <= 1000. You just significantly reduced the number of choices. Of course my first example would have a[500] = 499, which tells you nothing apart from i ≠ 500.


Efficient algorithm to translate/shift polynomials

Use FFT. Suppose that $\deg P \leq n$ and we use FFT on $n$ points (usually $n$ would be the smallest power of 2 which is at least $\deg P$). Let $\omega$ be an $n$th root of unity. The Fourier coefficients of $Q(x)
= P(x+d)$ are
$$
\hat{Q}(m) = \sum_{i=0}^{n-1} Q(i) \omega^{mi} = \sum_{i=0}^{n-1} P(i+d) \omega^{mi} = \sum_{i=0}^{n-1} P(i) \omega^{m(i-d)} = \omega^{-md} \hat{P}(m).
$$
This shows how to compute the Fourier transform of $Q$ from that of $P$ in linear time. Since FFT takes time $O(n\log n)$ (for suitable $n$), the overall running time is $O(n\log n)$. Choosing $n$ as indicated above, this becomes $O(\deg P \log \deg P)$.


Calculating CPU throughput on a single cycle vs multicycle datapath

Every instruction in a CPU goes through an Instruction execution cycle. In other words every instruction goes through multiple stages like Fetch,Decode,Execute,Writeresult. In modern processor the number of stages can go up to 20. So for single cycle instruction execution (all stages finish their work), the clock duration need to be large and hence the processor should operate at lower frequencies. CPI would be 1 and hence throughput is 1/F, where F is processors clock frequency.
But most modern processors use pipelining. They take advantage of the fact that each stage hardware is different and therefore multiple instructions can be at different stages of instruction execution cycle, at the same time. The clock frequency can be higher as amount of work being done (Max of all stage execution time) is smaller. The performance will be optimal if all stages of instruction execution cycle take equal amount of time.  Hence a pipelined processor with n stage is able to provide a throughput of one instruction per cycle. CPI should be P where P is the number of pipeline stages. But often a pipeline get stalled and different types of instructions (integer,float, branch, load,store...) take different number of cycles to complete. Hence CPI will vary for each program depending on instruction mix.
Pipelined processor having superscalar execution capabilities are able to take advantage of the fact that there are multiple processing/execution hardware in a processor, e.g., Integer ALU, floating-point ALU, memory management unit. So taking advantage of this fact more than one instruction can be in its execution stage at the same time. To support this fetch and decode stages have the capability to read and process multiple instruction in parallel. They are then able to feed multiple instruction to the execute stage, and more than one instruction is then completed per cycle. CPI will be lower in this case, even going to a value less than 1. In other words more than one instruction is able to complete within a single cycle.


Closed form solution for a single layer linear perceptron

Yes, there is a closed form solution.

In the most general terms, $WX = Y$ is a linear equation, so it can be solved as $W = X^{-1}Y$. If $X$ has no inverse, using the pseudo-inverse $X^\dagger = X^T(XX^T)^{-1}$ will give the $W$ that minimizes $\sum_i||Wx_i - y_i||^2$.

For practical computation, it's best to compute the pseudo-inverse from a matrix decomposition, rather than multiplying the matrices explicity. The safest option is the singular value decomposition. The wikipedia article details the procedure.

The principle behind this solution used only basic calculus. Calling the error $E$, we set $\frac{\partial E}{\partial w_{ij}} = 0$ and solve for $w_{ij}$. This is detailed in [1, pages 89–93) and [2], both available online.

Alternative phrases for this problem are multivariate linear regression and affine registration.

[1] Neural Networks for Pattern Recognition, Christopher M. Bishop.

[2] Fitting affine and orthogonal transformations between two sets of points, Helmuth Späth, 2004


Somewhere which is not part of the user accessible memory (i.e. not in the main memory nor in the cache -- that would be too slow, one of the main use of OOO is to hide part of the latency of main memory and low level caches).  Probably in register files inside the processor or possibly in the same kind of memory cells used for L1 caches (but not in the L1 caches).  Modern processors have lot of internal state which is not directly accessible.


It does hold that
$$
\forall x \forall y \forall z \, [p(y,z) \to p(x,z)] \quad \longleftrightarrow \quad
\forall x \forall y \forall z \, [p(x,z) \to p(y,z)],
$$
since $\forall x \forall y$ is the same thing as $\forall y \forall x$. So your logic is incorrect.

Similarly, if $\varphi$ is promised to be symmetric then the equivalence holds, for similar reasons.

A simple example where the equivalence doesn't hold is $\varphi(x,y) = x$, $p(x,y) = x$.

In this case the first statement is
$$
\forall x \forall y \forall z \, [x \land y \to x],
$$
whereas the second statement is
$$
\forall x \forall y \forall z \, [x \land x \to y].
$$
(This assumes that the statements are interpreted as $(\varphi \land p) \to p$ rather than $\varphi \land (p \to p)$.)


polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

Let $L_1=\emptyset$ and $L_2=\{\langle M\rangle\mid M\text{ halts on empty string}\}$. Let $s$ be a string that does not belong to $L_2$, for example, the empty string, which is a string that does not even represent a Turing machine. The reduction $f$ is $\forall x, f(x)=s$.

Now you can see $L_1\in\mathbf{P}$ and $L_2\notin\mathbf{P}$ (in fact, $L_2$ is undecidable), and $f$ is a polynomial-time reduction (it just ignores the input and outputs $s$ directly). Also, $x\in L_1\Leftrightarrow f(x)\in L_2$ (note $x$ always $\notin$ $L_1$ and $f(x)=s$ always $\notin$ $L_2$).

This is a counter-example.


First, you can get the time complexity down to ${\cal O}(n)$, while keeping the same space complexity. You can do this by filling visited in a single run of printBottom:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
         visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
     }
     if(lev[hd-min] <= level){
         visited[hd-min].push_back(node->data);
     }
     printBottom(node->left, level+1, hd-1, min, visited, lev);
     printBottom(node->right, level+1, hd+1, min, visited, lev);
}

with the initial call printBottom(root, 1, 0, min, visited, lev);

If you insist on the nodes beig output in order of increasing value of hd, I don't think you can improve space consumption. However, if you allow a different order of output, you can get rid of visited, by first determining for each value of 'hd', which level should be output and then making another pass, printing the values that match:

void fillLev(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
     }
     fillLev(node->left, level+1, hd-1, min, lev);
     fillLev(node->right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] == level){
         cout << node->data;
     }
     printBottom(node->left, level+1, hd-1, min, lev);
     printBottom(node->right, level+1, hd+1, min, lev);
}

with calls fillLev(root, 1, 0, min, lev); and printBottom(root, 1, 0, min, lev);.


Number of elements with lower index equal to some element, for all items on an array

Do a linear scan over the array, and use a hashtable.  Each time you see an element, add it to the hashtable (with a count of 1) if it's not already present, or increment the count of the item in the hashtable if it is already present.  As you see each element $a_r$, you can compute $f(0,r,a_r)$ by looking up $a_r$ in the hashtable and finding its count, and then record this value of $f$.  This will lead to an expected running time of $O(n)$ if you use a suitable hash function.

If you want deterministic running time, use a balanced search tree instead of a hashtable; that will achieve $O(n \log n)$ worst-case running time.


In which direction should I carry out a reduction when proving decidability/recognizability?

When we reduce a language A to a language B, we take an instance $x$ of A and transform it into an instance $f(x)$ of B so that $x \in A$ iff $f(x) \in B$. The way to remember that this is the correct direction is that shows you how to decide A if you can decide B. This is the normal, everyday life meaning of "reduction".

The linked answer does exactly that – it transforms an instance of $\overline{HALT}$ to an instance of $L_{all}$, thus reducing $\overline{HALT}$ to $L_{all}$.


Generally, for functions $f(n) \in \Omega(\log(n))$, we have that
$$
 \mathrm{NSPACE}(f) \subseteq \mathrm{DTIME}(2^{O(f)})
$$
A proof can be found on slide 28 onwards of the slide set from:

 http://www.informatik.uni-leipzig.de/alg/lehre/ws12_13/KOMPL/folien-eng.pdf

I don't know if $\mathrm{NSPACE}(n) \subseteq \mathrm{DTIME}(2^{n})$ is true. TSP is in $\mathrm{NSPACE}(n)$, but the best deterministic algorithm known is in $ \mathrm{DTIME}(n^22^{n})$ (as far as I know).


I3 productions are:
S->(.T)
T->.T,S
T->.S
here you need to add closure of S
S->.a
S->.(T)


How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

Real machines have access to a stack, and so can implement recursion. This is all that is needed to implement the Ackermann function.

However, the Ackermann function grows very fast, so you would only be able to calculate a few of its values given realistic time and space constraints.


Compute equality comparison without comparison operators

Let $W$ be the number of bits, $A, B$ integers to compare.

$Result =
(NOT((A - B) \text{ OR } (B - A))) >> (W - 1)$.

Here NOT negates bits. $A - B$ and $B - A$ is zero iff numbers are equal otherwise they are of different signs which ORed together will give a negative number.
The result is $1$ if numbers are equal and $0$ otherwise.


Finding the mistake(s) within this "proof" of NP being closed for complement

You just need to show that swapping final and non-final states doesn't complement the language accepted by an NTM, e.g., by showing that, for at least one NTM $N$ (which you can construct to have whatever properties you need), there is a  string that is accepted by both $N$ and $N'$, or rejected by both.


Is this language defined using twin primes regular?

If the twin prime conjecture is true, then $L = a^{*}$, which is regular. If the twin prime conjecture is not true, then there are finitely many twin primes; indeed, there is a largest pair of twin primes $\{p, p + 2\}$. In this case, $L = \{a^{n} | n < p + 1\}$, a finite language. In either case, you get a regular language, so I think it's safe to conclude that $L$ is a regular language... we just won't know which one it is until the twin prime conjecture is resolved.


Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k

This problem is NP-complete.  Even testing whether there exists a single subset that sums to $k$ is NP-complete; that is known as the subset sum problem.  Therefore, you should not expect any efficient solution to this problem.

If you are asking for any way to solve it, without regard to efficiency, one approach is to enumerate all possible subsets that sum to $k$, build a graph with an edge between each pair of subsets that are not disjoint, and search for a maximum independent set in this graph.  Another approach would be to use integer linear programming; define the zero-or-one $x_{ij}$ integer variable to be 1 if the $i$th subset includes the element $j$, and then add constraints to reflect the problem statement, i.e., $\sum_j x_{ij} j = k$ and $x_{ij} + x_{i'j} \le 1$ for all $i\ne i'$.  Then, apply an off-the-shelp ILP solver.


Enumerate all combinations of operations that fit memory and time criteria

You can use uniform-cost search in the space of possible combinations of operations. Each node will be an ordered list of operations performed. Terminate the search when the maximum memory or time allotment is reached.


Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?

Any problem that is provably not $\mathsf{NP}$ complete (w.r.t. polynomial time reductions) would mean that the class of problems reducible to it are distinct from $\mathsf{NP}$. In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$.

In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete.

Regarding primality and AKS algorithm for it:

Note that the according to the current state of knowledge, it is possible that primality is NP-complete. Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being $\mathsf{NP}$-complete.

You are probably interested in the list of problems that are conjectured to be between $\mathsf{P}$ and $\mathsf{NP}$ (known as $\mathsf{NP}$-intermediate) in which case you can check the answers to Problems Between P and NPC.


Finding k-nearest neighbors to a set of nodes in a large graph

The Floyd-Warshall algorithm computes all-pair shortest paths in $|V|^3$ time. Then you could compute the "shortest paths" from all nodes in $V$ to the subset $S$ by storing each shortest path in a $|V|$-size array, and sort these distances/array. First $k$ values will give you the $k$-nearest nodes.


O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.


Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$

The upper bound is easy. Because a tree with $n$ nodes has height $\Theta(\log n)$, when inserting the sequence of elements each tree has height at most $O(\log n)$, so the total complexity is $O(n\log n)$.

You're right with the lower bound. After inserting $n$ elements the tree has height $\Theta(\log \frac{n}{2})=\Theta(\log n - \log 2)=\Theta(\log n)$. So we can split the sum into two and bound each part by its lowest element:
\begin{align}
\sum_{i=1}^n \Theta(\log i)
&= \sum_{i=1}^{n/2} \Theta(\log i) + \sum_{i=n/2+1}^n \Theta(\log i) \\
&= \frac{n}{2} \Omega(\log 1) + \frac{n}{2} \Omega(\log\frac{n+1}{2})\\
&= n\,\Omega(\log n) \\
&= \Omega(n \log n)
\end{align}


Why do we use stacks and not queues on system-level?

Because some things need to be done LIFO and some things FIFO.

For example, when a function call returns, it needs to return to the last item on the call stack, i.e., the function that called it. It would make no sense to return to the first item on the call-stack. Conversely, if you're serving requests, the next request you serve is the first one to enter the service queue. (It turns out that, actually, serving queues from the back can be more efficient but that has the obvious disadvantage that it risks starvation for things at the front of the queue and, in real-life queues of people, it just gives people a huge incentive to leave the queue and re-join.)


Can an alphabet be $\{ε\}$ or $\mathbb{N}$?

An alphabet can be any finite set of symbols. $\{\epsilon\}$ is a finite set of symbols so you can certainly use it as an alphabet.  The strings over this alphabet are the empty string, $\epsilon$, $\epsilon\epsilon$, $\epsilon\epsilon\epsilon$, etc. Note that, in this context, we need some other notation for the empty string (some people use $\lambda$ for that anyway) and, in this context, $\epsilon$ does not denote the empty string: it denotes the one-character string whose only character is an epsilon. Likewise, $\epsilon\epsilon$ denotes the two-character string consisting of two epsilons.

Because it's confusing, we normally try to avoid having $\epsilon$ as a character in the alphabet. However, in some circumstances, it is a natural thing to do:

If you want to recognize languages of Greek words, it would be unnatural to use any alphabet other than the Greek one, $\{\alpha, \beta, \dots, \omega\}$ and that includes $\epsilon$.
If you want to write out a grammar for the strings that constitute valid regular expressions, e.g., over alphabet $\{0,1\}$, then you're going to need to use symbols $\{0,1,(,),+, {}^*, \epsilon,\emptyset\}$ (and life could get very confusing indeed).

So, if you want to stay sane, avoid having symbols such as $\epsilon$ in your alphabet as far as possible. But, if you can't avoid it, you just have to do it and use some other notation for the empty string.

$\mathbb{N}$ is not finite so it's normally not allowed as an alphabet, especially in the sort of formal language theory that's taught to undergraduates. It certainly makes sense to consider infinite alphabets in other contexts but, for most purposes, we stick to finite alphabets.


Machine Learning algorithms based on "structural risk minimization"?

The structural risk minimization principle is a principle that is at least partly 'used' in all machine learning methods, since overfitting is often to be taken into account: reducing the complexity of the model is (supposedly and in practice) a good way to limit overfitting.

SVMs explicitly have a parameter for the complexity (the dimension of the feature space, or even the kernel function) and it's necessary because increasing the complexity is a part of the learning algorithm.
Neuronal networks also have a easy indicator of their complexity (number of 'cells') and is part of the associated learning algorithm.
Without this principle grammar inference would be both stupid and perfect grammar is the list of all possible words, so every non-trivial algorithm at least acknowledges this principle.
Decision trees have their own notion of entropy.
Clusters can be simply counted or kind of 'use' the principle intrinsically or have a fixed number of clusters and in that case you apply the principle at a higher level.

To be perfectly honest I don't really know about what happens in genetic programming but they don't have an intrinsic notion of complexity.

I don't know well Inductive logic programming but it doesn't seem to scale very well to this principle.


In the olden days, you wrote up a sequence of operations to be executed (typically on punched cards, a job), and handed them to the operator to be loaded. The operating system took such a batch of commands to execute off it's input queue, ran them until the end (or something failed), and took the next one. Output was collected (probably printed out) to return to you.

If the above is what is meant, the crucial difference is that in batch processing you get (perhaps the next day) the feedback that the job failed because of a syntax error or some equally irritating glitch. With a command line interface you run one command, can check it's output or correct the command before entering the next one.


Name for Turning DAG into redundant tree

I am not aware of any standard name for that kind of tree.  One of the wonderful things about language is that we can describe things we don't already have a name for; there are many more interesting concepts than there are pre-existing widely-recognized names.  I recommend that, if you find in your writing you need a concise name for it, you choose a name that seems suitable to you, and define it before first use.


Since you allow non-simple paths(i.e. walks), seems like a dynamic programming algorithm will work.

For each $1 \le m \le k$, and every vertex $u$, we compute $D[m,u]$ where $D[m,u]$ is the weight of the shortest walk of length exactly $m$ starting at $v$ and ending at $u$. We are looking for $D[k,w]$.

This can be computed as

$$D[m+1, u] = \min_{x \in Pred(u)}\{D[m,x] + w[x,u]\}$$

Where $Pred(u)$ (predecessor) is the set of vertices which have an outgoing edge to $u$ and $w[x,u]$ is the weight of edge $x\to u$. You start with $D[1,u] = w(v,u)$ (allowing $\infty$).

You can add auxiliary structures to find the actual walk.

Running time: $O(k |E|)$.

This is because for each number of required edges from 1 to k, we go through the indegree of each vertex and in total, we visit all $|E|$ edges. We visit all $|E|$ for each number of the required edges ($k$) so the final run time is $O(k |E|)$ .

btw, if we wanted only simple paths, then this is probably $NP$-Hard, as we can set $k=n$ and reduce some variant of Hamiltonian Path problem to it.


Why does lower integer represent higher priority in scheduling literature?

This has always troubled me too.  The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things).

In schedulers we use the word priority in the sense of:

  the right to take precedence or to proceed before others[1]

It came into English from Norman French after the Norman conquest of England in 1066.  It came into Norman French from the Latin word prior, which (in English) means

  existing or coming before in time, order, or importance[1]

I added the emphasis on the word order to emphasize that we are using the word in the sense that requires we use ordinal numbers.  So you should think of it in terms of a medieval court hierarchy.  The king is seated at the dinner table first because he has the highest rank.  The prince (etymology: via Norman French from Latin princeps, which means "first citizen"[2]) is seated second because he has the next highest rank.  Then the dukes are seated third because they have the next highest rank.  And so on.  The knights are seated last because they have the lowest rank.  (The common folk with no title don't get seated at all because they have no rank at all.)

[1] This is from the definition from Google.  I think they may have gotten it from Oxford English Dictionary.
[2]http://en.wikipedia.org/wiki/Royal_and_noble_ranks


Is there any practical trick to mentally count in Gray code?

I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer will carry through larger values too.
Take a Gray code, and count the number of 1's:
Case I:
Odd number of 1's: flip the bit one position before the last '1'.
Case II:
Even number of 1's: flip the last bit.
Examples:

Even case:
After 10100101, the next one is 10100100.

Explanation: there are 4 1's so we apply the even case, i.e., flip the last bit.

After 111011010, the next one is 111011011.

Explanation: there are 6 1's so we again flip the last bit.

Odd case:
After 110111, the next one is 110101.

Explanation: there are 5 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

After 1100100, the next one is 1101100.

Explanation: there are 3 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.
I hope this helps!


Compute pair of similar list from a collection of lists

Build a hash of element -> list of lists that contain that element. From that it's easy to find all pairs of lists that share an element. Of course listing all pairs is still $O(n^2)$, since there might be quadratically many. But finding just $k$ pairs is $O(k+m)$, where $m$ is the total number of elements in all sets.


Different definitions of complexity class DP

Equivalence follows immediately from the definitions.  The definition of $\setminus$ is:
$$A \setminus B = A \cap \overline{B}$$
where $\overline{B} = \Sigma^* \setminus B$ denotes the complement of $B$.  Now taking $L_1=A$ and $L_2=B$, it is trivial to prove that $L$ meets the first definition iff it meets the second definition, since $B \in NP$ iff $\overline{B} \in coNP$.


As for your main question, I recommend this short survey by Martin Grohe.

  Are the queries that are needed in practice usually simple enough that there is no need for a stronger language?

I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This comes from the point of view of somebody who has done some work as a freelance developer of relatively simple web sites and other applications, so I'm not sure about the real uses of SQL in bigger industries/larger databases.

In the rare cases a more powerful language might be needed, my guess is that software developers deal with them by using the language in which they write the application, not the queries (like C++ or java).


How many range are completely inside a given range

I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni but, I think, is easier to code (arguable).

Here is the data structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each node stores a sorted subarray. This structure requires $O(n \log n)$ memory (because there are $\log n$ layers and each of them requires storing $n$ numbers). It is built in $O(n \log n)$ as well: you just go bottom-up and for each inner vertex merge sorted lists of its children.

Here is an example. Say 1 5 2 6 8 4 7 1 be an original array.

|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|

This structure can answer queries of form "how many numbers $\leq x$ are there in range $[l, r]$" in $O(\log^2 n)$ time: just make a reqular query to a segment tree (traversing $O(\log n)$ nodes) and make a binary search to know how many numbers $\leq x$ are there in that node (additional $O(\log n)$ from here).

This can be speed up to $O(\log n)$ using Fractional Cascading technique, which basically allows you to do the binary search not in each node but only in the root. However it is complex enough to be described in the post.

The original problem is reduced to this one exactly the way Jouni explained: having your segments sorted by left endpoint, you create the array of left endpoints $A$ and a Merge Sort Tree of right endpoints $B$. Use the binary search on $A$ to find the range, $[l, r]$, of indexes of left endpoints lying in $[c, d]$ and make a query "how many numbers $\leq d$ are there in range $[l, r]$ in array $B$".


What are the mathematical prerequisites for adaptive machine learning algorithms?

The precise mathematical skills that you'll need for your studies will vary depending on exactly which area of ML you'll be working in. In general though Bayes theorem, probability theory and statistics will be your constant companion. Getting a good grasp of these is extremely helpful when it comes to fully understanding how learning algorithms work, and how they can be modified.

Partial differential equations, linear algebra, and mathematical induction are also very important. However beyond these it is difficult to say exactly which areas you should brush up on. In my opinion it depends on what problem you are trying to solve.

For instance is it a regression problem? Is it a classification problem? Are you clustering data? You mention adaptive algorithms, but many ML algorithms could be considered adaptive. As you become familiar with the ML field you'll find that people use different terms to describe exactly the same thing :) a little frustrating to be honest! But the second link you provided is from a non - computer science journal, so just be aware the definition of adaptive in this paper may mean something different in ML. For instance I don't work in adaptive algorithms, but my work has to adapt to high throughput data streams so is most certainly adaptive. But it falls under the category of Semi-supervised learning.

I would recommend taking a look at the following books for more information:

Machine Learning by Tom M. Mitchell, 1997 - This is a great and relatively easy going introduction to machine learning. Despite being over ten years old, this book covers the key topic areas, and introduces you to important concepts. Indirectly this will introduce you to the mathematics of Machine Learning. You'll be able to tell from this book what type of mathematics skills your particular problem may require.

Artificial Intelligence: A Modern Approach by Stuart Russell & Peter Norvig, 3rd Edition, 2009 - All encompassing text (1000+ pages) covers machine learning in great detail. Authoritative text.

Pattern Recognition and Machine Learning (Information Science and Statistics), Christopher M. Bishop, 2006 -  Excellent authoritative text that goes in to ML in great depth. This includes introductory chapters that get you up to speed with the mathematics required to understand learning algorithms (including probability). Can be hard going if you have no mathematics experience.

To support any reading you do I suggest you take a look at the Andrew Ng machine learning course on Coursera. I watched some of these before starting my own study, so too did many of my friends.


Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup

There is no general way to find a decider TM for $L_k$

You are correct that $L_k$ is recursive because, being a subset of the
finite set $\Sigma^k$, it is also finite.

You would like to rather find a decider TM for $L_k$, and you suggest
some techniques. Without even going into the details of these
techniques and why they do not work, you do not stand any chance of
ever succeeding.

The first thing you should notice is that the finiteness argument
tells you that there exists a decider TM $M_k$ for the language $L_k$,
but it does not tell you what this TM is. It is an example of a
non-constructive proof: you prove that a decider exists, but you
cannot tell which it is.

Now, suppose that, given $k$, you have a procedure $\mathcal P(k)$ to
find such a decider $M_k$ for the language $L_k$ (rather than just
prove it exist). Then, given any Turing machine $M$, then there is an
integer $k'$ such that $|\langle M\rangle|=k'$, so that $\langle
M\rangle\in \Sigma^{k'}$. Then you can use the procedure $\mathcal P$
to find a decider TM $M_{k'}$ that can determine whether $\langle
M\rangle\in L_{k'}$. So you have a way to decide whether the TM $M$
halts on empty input. And this works for any TM $M$. However, this is
not possible, because it is undecidable whether a given TM $M$ halts
on empty input.

So the procedure $\mathcal P$ cannot exist.

Since you are looking for a general way to find the decider TM
$M_{k'}$, you cannot succeed because that method would be precisely a
procedure such as $\mathcal P$.

Note that this proof could still leave the (very remote) possibility
of finding a decider for some specific values of $k$, but you would
have to identify precisely the concerned values, and the method would
not work for all values of $k$. I am not advising you to try.


Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

I assume that you intend $\leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $\leq$ is really the smallest fixpoint of the equivalence you give:
$\qquad \displaystyle a \leq b \iff \exists\, v_0 \dots v_n. a \to v_o \to \dots \to v_n \to b$
with $n \geq 0$ and $v \to u \iff (v,u) \in E$.
The key argument here is that $\leq$ is indeed a total order. If it is, you can use it for sorting, and the result is by definition of $\leq$ a Hamiltonian path: consider the result of the sort $v_1 \dots v_n$. If there were no edge between $v_i$ and $v_{i+1}$, by $V_s = v_i \leq v_{i+1}$ there is $v \in V$ such that $v_i \leq v \leq v_{i+1}$. This contradicts that $\leq$ is a (total) order and $V_s$ is sorted with respect to $\leq$.
Unfortunately, $\leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K_4$:

[source]
Here, $a \leq d$ and $d \leq a$ (directed cycles are the culprits!) but $a \neq d$. So $\leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.


Has there been a lexer that takes in much more than a regular language?

FORTRAN is famous for having some difficult to lex constructs, but those difficulties result probably more from having been designed before the classification was established (or at least known in programming circles)
Several languages are described with a type-3 lexers but some characteristic are easier to handle by feeding information from the parser to the lexer (C/C++ typedef, C++ templates, Ada/VHDL attributes)
Several languages have layout rules (Python, Haskell) which are usually not described as type-3 lexers (I don't know if it is possible to do so or not)


Why don't compilers automatically insert deallocations?

Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed.  Even if you ensured that your compiler never did the second one and allowed the programmer to insert calls to free() to fix those bugs, knowing when to call free() for that compiler would be even harder than knowing when to call free() when using a compiler that didn't try to help.


Good beginner source to learn about how computers work

What I have got for you is :

Computer  Systems - A  Programmers Perspective
Computer Organization and Design
The Elements of Computer System
The Pattern on the Stone (Misleading title)
Code - The Hidden Language of Computer Hardware and Software

These books should help you understand how computer works. A bit knowledge of computer hardware is a must and it will surely speed up your learning process.


Computer science is a science only by name. In practice, it is a blend of engineering, mathematics, and empirical science.

With that out of the way, here are a few comments about the Church–Turing thesis. First, about the thesis itself. We can think of at least three interpretations of the Church–Turing thesis. Under the first, stronger interpretation, any computation that can be done in the physical world can be modelled by (say) a Turing machine. This is a thesis which indeed can be refuted, and people have tried to refute it, though so far unsuccessfully (Scott Aaronson suggests to regard this as a "law of nature").

The second, weaker interpretation only claims that any computation done in practice (now) can be modelled by a Turing machine. This thesis is essentially correct, though to make it truly correct you need to make it mathematically precise; Nachum Dershowitz and Yuri Gurevich have done just that, though their formulation doesn't necessarily reflect the intuitive content of the thesis.

The third interpretation, very related to the second, is that any pseudocode that we can describe can be implemented on a Turing machine. We use this thesis implicitly whenever we describe and analyze algorithms, both in very theoretical areas (recursion theory, computational complexity, theoretical algorithms and data structures, approximation algorithms) and in more applied areas, in which the pseudocode is often translated to code in practice.

Second, in practice the more interesting thesis is what is sometimes called the Cook–Karp thesis. This thesis states that the class $\mathsf{P}$ embodies all decision problems that can be solved efficiently in practice. In my view, this thesis is dubious. There are three main attacks on this thesis.

The first attack is that the class $\mathsf{P}$ is defined asymptotically, whereas we are interested in problems of finite size. It could be that for practical input size, a problem which is perhaps not in $\mathsf{P}$ can be solved efficiently (for example, small cryptosystems can be broken even if they are secure). Conversely, it could be that a problem is in $\mathsf{P}$ but it cannot be solved efficiently, since the polynomial time "kicks in" only for large problems.

This is very related to the second attack, which is that polynomial time algorithms need not be efficient: they could have a large (big O) constant or a large exponent. A good example for a large constant is fast matrix multiplication algorithms, which are not practical due to the large constant. A good example for a large exponent is deterministic primality testing (the AKS algorithm), which isn't practical due to the large exponent.

A third attack, which is more speculative at this point, is that quantum computers can efficiently solve some problems which we think classical computers cannot. While quantum computers still exist only on paper, unless we believe that there is some fundamental obstacle to constructing them (as some people indeed do, for example Gil Kalai), we have to contend that in the future the class $\mathsf{P}$ would have to be enlarged to the corresponding quantum class $\mathsf{BQP}$.

A related attack states that randomized algorithms can be stronger than deterministic ones: for example randomizes primality testing is practical while the AKS algorithm isn't. However, it is believed that "randomness doesn't help", in the sense that $\mathsf{P}=\mathsf{BPP}$ (which doesn't mean that randomized algorithms can't be faster; it only means that they can only be polynomially faster).


Who (and when) first defined interval graphs?

I was able to track the first occurences of interval graphs down to

G. Hajos, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957) page 65

This reference refers to a book of (talk) abstracts. In the abstract of Hajos  interval graphs are defined, without actually calling them interval graphs. Moreover it says, that he gives conditions whether a graph is a interval graph and he discusses how to reconstruct the intervals defining the graph, when the graph fulfills these conditions.


if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$

b(x) is between $c_1·x$ and $c_2·x$ if x is large. g (x) is between $d_1·x$ and $d_2·x$ if x is large. So f (x) is between $c_1·x$ and $d_2·x$ if x is large, which makes it $\Theta(x)$.


Yes and no.

If P=NP, then every problem in NP, in particular 3SAT, can be solved in polynomial time. Hence it reduces to every nontrivial problem (and 2SAT is nontrivial) using polynomial time reductions. Which are the reductions in the definition of NP-hardness.

NL, on the other hand, is not closed under polynomial time reductions (unless NL=P), as these can use polynomial space (exceeding logarithmic space). That is why for the definition of NL-hardness, logspace reductions are used. Hence neither can we conclude that 3SAT is in NL, nor that NL=NP.


A real-world example for a kind of real-time applications

Example 1: Playing a multimedia stream where Task 1 must decompress an audio "frame" while Task 2 must decompress a video frame by the same deadline: the playback time for a given video frame.

This is a little unrealistic though because in practice there's a demux task that task 1 and 2 both depend on, and usually the audio and video playback frames have different repeating deadline frequencies.

Example 2: A robot might run all its control loops with the same frequency for simplicity. The control loops all depend on receiving a new set of sensor input values, then they all run, and they all send outputs to the actuators. E.g. Task 1 controls the motor for the left side of the tank drive, Task 2 controls the motor for the right side of the tank drive, while Task 3 controls the robot arm. It just simplifies things a bit to give all the control loops the same deadline unless there are interdependencies such as needing to mux the actuator control data into a single packet to send over a network to the actuators. In that case, a Mux task depends on all the control loop tasks.


How is adversarial autoencoder better than an ordinary autoencoder?

In an adversarial autoencoder, the discriminator network can help generate a more suitable distribution of the latent parameters than would be produced through random selection. If the statistical distribution of the compressed representation is completely unaltered and done in a way as to maximize only the reconstruction accuracy, it is very hard to generate new, high-quality output images because we have to guess the distribution of these latent variables. In a variational autoencoder, this problem is solved by forcing the latent parameters (compressed representation) to conform to a normal (Gaussian) distribution, allowing us to easily generate new images. Using a discriminator to determine a suitable distribution increases the quality of the results produced because the constraints imposed are done in such a way that the reconstruction error can still remain very low and thus the output images are not blurry.