How do binary trees use memory to store its data?

We use implicit array representation to store Binary Heaps, where if a node has an index $i$, its children are found at indices $2i + 1$ (for the left child) and $2i +2$ (for the right), assuming indices start at 0.

Now this is not wasteful for Binary Heaps since nodes are added in Breadth First method. However for normal Binary Trees implicit array representation is very expensive to grow and wastes space in the order of $O(2^h)$ where $h$ is the height of the tree (Consider skewed binary trees).

For trees having a large number of nodes we use Succint Data Structures as pointed out by Raphael. A normal binary tree of $n$ nodes is stored using $O(nlogn)$ bits (pointer representation), but succinct representations require just $2n + o(n)$ bits and carry out many sophisticated operations in constant time. This link gives us a good overview of a simple representation of succint representations.


How to understand these exposure algorithm rules for System F sub?

In a typing rule (and more generally any deduction rule), all metavariables¹ are universally quantified. That is, the rule can be applied for any instantiation that is syntactically correct. For example, (XA-PROMOTE) means “for any context $\Gamma$, for any type variable $X$, for any type $T$, for any type $T'$, if $\Gamma$ contains $X <: T$ and the typing judgement $\Gamma \vdash T \Uparrow T'$ is true, then the typing judgement $\Gamma \vdash X \Uparrow T'$ is true”. The rule (XA-other) states “for any type $T$, for any context $\Gamma$, if $T$ is not a type variable then the typing judgement $T \vdash T \Uparrow T$ is true”.

The question “which $T$ is it referring to?” is not meaningful: the rule does not refer to a particular $T$. On the contrary, the rule applies to any $T$; the conclusion applies to any $T$ that matches the premise.

In $\Gamma \vdash T \Uparrow T$, the left- and right-hand sides of $\Uparrow$ are the same type. The rule states that the relation $\Uparrow$ in any given context $\Gamma$ is symmetric on the subset of the set of all types that consists of the types that are not type variables. Some examples of typing judgements that can be derived by this rule are:
$$
\vdash \mathsf{Top} \Uparrow \mathsf{Top} \\
X <: \mathsf{Top}, Y <: X \vdash X \rightarrow \mathsf{Top} \Uparrow X \rightarrow \mathsf{Top} \\
X <: \mathsf{Top}, Y <: X \vdash (\forall Z <: Y, X \rightarrow Z) \Uparrow (\forall Z <: Y, X \rightarrow Z) \\
$$

I don't remember Pierce's presentation and I don't have the book here, but I think the reason XA-other has the premise that $T$ must not be a type variable is to make these rules syntax-directed: there's another rule that allows deriving judgement $\Gamma \vdash T \uparrow T$ when $T$ is a type variable. This is a presentation choice.

¹  A metavariable is a variable that is used to describe the system, for example $X$, $T$, $T'$ and $\Gamma$ in the rule (XA-PROMOTE). We use the term metavariable to distinguish this concept from a variable, which refers whatever the language calls a variable.


Quantified Boolean Formula vs First-order logic

Firstly, a quantified Boolean formula is a formula in quantified propositional logic (which consists of Boolean variables and quantifiers). A true quantified Boolean formula is a formula that can be made true (formulas have no free variables so they can be either true or false). Note that this term is also used for the true quantified Boolean formulas (TQBF) language which contains all true Boolean qualified formulas. Therefore, you probably had a comparison of the respective logics in mind, namely quantified propositional logic and first-order logic.

To make a connection of quantified propositional logic and first-order logic, let us consider predicate logic (that is more general, and includes first-order logic). When comparing propositional logic and predicate logic, a basic difference is that the latter includes a richer ontology: objects, functions and predicates on objects. (This allows more flexible and compact representation of knowledge, as expressing a binary predicate on a set of n terms might lead to n*n terms in propositional logic.) Having this in mind, effectively, first-order logic and quantified propositional logic add quantification to propositional and predicate logic, respectively.

Consequently, from the perspective of the comparison of the formal systems represented by these two logics, one might consider their expressiveness. While quantified propositional logic is restricted to Boolean variables (that might hold either true or false), first-order logic does not have such restrictions. It can model different sets of objects (terms), together with predicates and functions on them (it is most widely used to express properties in wide range of mathematical theories). Therefore, strictly speaking, first-order logic is more expressive.

One important distinction between these logics is in terms of decidability. Namely, to check whether a formula in quantified propositional logic is true is decidable (the language TQBF is decidable; more specifically, it is PSPACE-complete). Unlike quantified propositional logic, first-order logic is undecidable if the language has at least one predicate of arity at least 2 (other than equality). This means that there is no decision procedure that determines whether arbitrary formulas are logically valid. (This can be shown by encoding the statement "the Turing machine T halts on empty input", which is known to be undecidable, in first-order logic.)

Note that formulas in quantified propositional logic can be straightforwardly interpreted in first-order logic. (This is explained in more details in this answer.)


Creating a DFA that only accepts number of a's that are multiples of 3

The key idea here is to make a ring of three states, $q_0, q_1, q_2$ with $a$ transitions
$$\begin{align}
q_0 & \stackrel{a}{\rightarrow}q_1\\
q_1 & \stackrel{a}{\rightarrow}q_2\\
q_2 & \stackrel{a}{\rightarrow}q_0
\end{align}$$
On input $aaa$, for example, you'll start in state $q_0$ and pass to state $q_1$ on the first $a$, $q_2$ on the second, and back to $q_0$ on the third $a$. Clearly, any multiple of three $a$s will leave you in state $q_0$, so we make that a final state.

What to do about $b$s in the input? They don't have any effect on the number of $a$s, so include transitions
$$\begin{align}
q_0 & \stackrel{b}{\rightarrow}q_0\\
q_1 & \stackrel{b}{\rightarrow}q_1\\
q_2 & \stackrel{b}{\rightarrow}q_2
\end{align}$$
and you're done. In fancier terms, we're $q_n$ to "remember" whether the number of $a$s seen so far was congruent to $n\pmod{3}$. This idiom, using the states to remember certain situations, is fundamental when designing FAs.


There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\{x_1,...,x_n\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n> 1$, $m>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.


Preemptive multithreading is usually implemented by the operating system using timer interrupts.  Everything else can be done in software.  Even the timer interrupts aren't strictly necessary: in cooperative multithreading (what they had in Windows 3.1 and earlier and MacOS prior to MacOS X) the operating system would perform the thread switch whenever a thread did a system call (e.g. a file read or write.)

A process has an address space with one or more threads running in it.  Address spaces typically require hardware support for page tables.

There is no hardware support required for synchronization or communication.  Multiple threads in the same process communicate through the address space they share.  Threads within the same process typically synchronize using mutexes and condition variables.  Mutexes and condition variables can be implemented with load and store instructions.  (For the most part.  There are some processors that don't have sequentially consistent memory hardware, and for those the processor also needs to implement some kind of memory barrier instructions.)  When a thread needs to wait for a long time it will put itself to sleep by calling into the operating system.

Threads in different processes typically communicate through one of the abstractions implemented by the operating system (pipes, files, sockets).


"Forwarding pointer" is the name of a technique used in garbage
collection algorithms when data cells are being moved to a different
storage location, either because you are using a copying collection
technique such as Cheney's collector, or because you are doing a compaction phase to reduce
memory fragmentation. Compaction is usually associated with mark-and-sweep collectors, but it could be used in other contexts, though the care required by forwarding pointers may entail overhead that is more naturally acceptable with mark-and-sweep.

The forwarding pointer replaces the data cell that has been moved, so that any piece of code trying to access that cell through its old address can find the forwarding pointer to the new address. Exactly like a person moving to a new house will leave her new address on the mailbox (or at the post-office) of her old house. Of course, the code and data must be organized so that forwarding pointers may be recognized as such.

As far as I know, this was historically the first widespread use of the concept of forwarding pointer. But the idea of using forwarding pointers can be considered, and has been considered in other situations that require moving data to a different location, for example:

The concept is used in mobile computing when an agent moves to a
different location (agency) and must still receive messages sent to
its former location.
The concept is also used in data-base implementation when the organization and management
of data requires moving some part of it to another location.

Basically, forwarding pointers are a way of reorganizing incrementally
the storage structures or system organizations without disrupting (too much) on going computations,
and avoiding a complete sweep of the system space, by leaving the new address of moved constituents at their former location.

(You could have found some of that yourself by searching the web and wikipedia).


Tutorials/resources for building a toy SMT solver

I think these slides give a foundation of building a SMT solver, somewhat


This sequence is OEIS A173566. To understand how large it grows:
$a_n = 2^{2^{b_{n-1}}}$
where:
$b_0 = 0$
$b_n = b_{n-1} + 2^{b_{n-1}}$
The sequence $b_i$ grows faster than $2^{\cdotp^{\cdotp^{2^0}}}$, where there are $i$ 2's in the tower.
EXPTIME is $O(2^n)$, 2-EXPTIME is $O(2^{2^n})$, and in general, you can define n-EXPTIME . The sequence $b_i$ is not in n-EXPTIME for any natural n. So it, and therefore $a_i$, is not in the complexity class ELEMENTARY.
The definition above shows that $a_i$ is primitive recursive, which is interesting, because that means it doesn't grow as fast as the Ackermann function.
I think (but don't really have the time to formally prove or disprove right now) that means it's $\mathcal{E}^4$ in the Grzegorczyk hierarchy. Left as an exercise.


You cannot answer this question unambiguously. Different  OOP languages implement OOP paradigm differently.

In Ruby you will get only "Hi, I am bird!"

class Animal
  def initialize
    puts "Hi, I am animal!"
  end
end

class Bird < Animal
  def initialize
    puts "Hi, I am bird!"
  end
end

class Pigeon < Bird
  def initialize
    super # <= call to the superclass
  end
end

pg = Pigeon.new

In PHP we get only "Hi, I am bird!"

<?php

   class Animal {

      public function __construct()
      {
        echo "I'm Animal";
      }

    }

    class Bird extends Animal {

       public function __construct()
       {
         echo "I'm Bird";
       }

    }

   class Pigeon extends Bird {

      public function __construct()
      {
         parent::__construct();
      }

    }

   $Pigeon = new Pigeon();

  ?>

While in C++ you will get both "Hi I am animal!" and "Hi I am Bird!"

#include <iostream>
using namespace std;

class Animal
{
   public:
   Animal()
   {
     cout << "Hi I am animal!" << endl;
   }
};

class Bird : public Animal
{
  public:
  Bird()
  {
    cout << "Hi I am Bird!" << endl;
  }
};

class Pigeon : public Bird
{
  public:
  Pigeon():Bird(){} // <= call to the base constructor
};

int main()
{
  Pigeon pg;
}

In Swift (Apple) we get both, too

class Animal {
  public init() {
    print("I'm Animal")
  }
}

class Bird: Animal {
   public override init() {
     print("I'm Bird")
   }
}

class Pigeon: Bird {
   public override init() {
    super.init()
   }
}

var pigeon = Pigeon()

To understand why, you should get into details of how C++ implements OOP (vtables and etc.) and how Ruby classes lookup its methods and constants in the hierarchy, and other languages.

In addition if you want to see Object Oriented "Nightmare" then have a look at Lua, though I like it.

As to your question in the title: "Are grandparent classes also parents",
of course subclasses are related to all super-classes up in the hierarchy chain, but that relationship are implemented differently in different programming languages.


Lamport’s fast mutual exclusion algorithm intuition

In what sense are this locks fast/slow?

Lamport optimizes for a very specific scenario, as pointed out in the paper:

  The current belief among operating system designers is that contention
  for a critical section is rare in a well-designed system; most of the
  time, a process will be able to enter without having to wait.

The reasoning goes like this: Most of the time, only a single thread will attempt to get into the critical section. So the codepath that we should try to optimize is the one where the lock is readily available.

The case where there is actual contention on the critical section is considered exceptional. It is fine if the algorithm behaves less than ideal in that case - less than ideal here means, you will never let more than one process into the critical section, but if there's lots of contention, you might have to wait a long time (possibly forever) for your turn to enter the critical section.

To illustrate this point, let's take a look at a classic algorithm for mutual exclusion (coincidentally also by Lamport), the Bakery algorithm. Here, in a nutshell, a thread that wants to enter the critical section picks a number that represents its place in the waiting queue. The thread with the smallest number is at the front of the queue and can enter the critical section, all others have to wait. How do we determine whether we have the smallest number (and hence can enter the critical section)? We have to compare our number against the numbers of all the other threads. This means even if none of the other threads are in the queue at that time (no contention), we have to check the numbers of all the other threads. This is obviously not nice, as locking becomes more expensive as the number of threads increases.

The fast mutual exclusion avoids this: If there is no contention we check slow-lock, which is available. Then we check the fast-lock, which is also available and we enter the critical section. We only need two write operations and two read operations to get into the critical section, regardless of the number of threads.

  What's the point, for example, after freeing the slow lock, go back to the beginning of the algorithm?

It's the only safe thing to do. Remember, it is crucial that no more than one algorithm is allowed to enter the critical section. If we fail the slow-lock check, it means that some other thread might already be in the fast-lock check or even in the critical section. Thus we have to back off and restart from the beginning. We will keep doing this until the other thread has left the critical section, which will allow us to pass the check.


Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms?

Depends. Quicksort is not one algorithm. Performance depends on the details. You would adjust the algorithm slightly if moving items is expensive.

You might assume that items are in random order. That is often not the case. You may be able to sort items with non-random items faster than using quicksort. For example if an array starts or ends with many items in ascending or descending order sorting in linear time may be possible.


Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) where $n$ reappeared. Perhaps you just los $n$ in (3) but otherwise you had it on paper.

Let us try again:
\begin{align*}
T(n) &= n + (3/2) n + (3/2)^2 n + \cdots
\end{align*}
But when does sum end? (This is what created your mistake.) It ends when we get to the base case, which is $T(1)$. After $k$ unfoldings we have $T(n/2^k)$ so we will reach $T(1)$ when $k = \log_2 n$. Thus, we continue like this:
\begin{align*}
T(n) &= n + (3/2) n + (3/2)^2 n + \cdots + (3/2)^{\log_2 n} T(1) \\
&= \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i n\\
&= n \cdot \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i.
\end{align*}
It remains to add the sum. It is a geometric series, so we can look up the formula $\sum_{i=0}^k a^i = (a^{k+1} - 1)/(a - 1)$ and get
\begin{align*}
{\textstyle \sum_{i=0}^{\log_2 n} (3/2)^i} &=
\frac{(3/2)^{1 +\log_2 n} - 1}{3/2 - 1} \\
&= 2 \cdot ((3/2) \cdot (3/2)^{\log_2 n} - 1) \\
&= 3 \cdot (3/2)^{\log_2 n} - 2 \\
&= 3 \cdot (n^{\log_2 (3/2)}) - 2 \\
&\in \Theta(n^{\log_2 (3/2)}) \approx \Theta(n^{0.58})
\end{align*}
The final result is this sum multiplied with $n$, so it is
$$\Theta(n \cdot n^{\log_2(3/2)}) = \Theta(n^{\log_2 2 + \log_2 (3/2)}) = \Theta(n^{\log_2 3}),$$
assuming I can still do logarithms....


1/2 Approximation to MAX-DICUT by rounding a linear program

The constraints force $z_{ij} = \min(x_i,1-x_j)$. Therefore you have to show that
$$
\left(\frac{1}{4} + \frac{x_i}{2}\right) \left(\frac{1}{4} + \frac{1-x_j}{2}\right) \geq \frac{1}{2} \min(x_i,1-x_j).
$$
By symmetry, we can assume that $x_i \leq 1 - x_j$, and so we have to show that
$$
\left(\frac{1}{4} + \frac{x_i}{2}\right)^2 \geq \frac{x_i}{2}.
$$
You can check that this holds for all $x_i$. Equality holds when $x_i = 1-x_j = 1/2$, showing that the approximation ratio $1/2$ is tight (for the analysis).


How Do You Design an Algorithm for This Graph

Both questions can be solved in time $O(m + n \log n)$, where $n$ and $m$ are the the number of vertices and edges of the input graph graph $G$.

For question $1$: Create a directed graph $G'$ consisting of two copies of  $G$ (you can think of $G$ as directed by replacing each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$).

For each vertex $v$ that represents a gas station in $G$, let $v_1$ and $v_2$ be the vertices corresponding to $v$ in the first and second copy of $G$ in $G'$, respectively, and add the directed edge $(v_1, v_2)$ to $G'$. The weight of $(v_1, v_2)$ is $0$.
Finally, find the shortest path $P$ from home (in the first copy of $G$) to work (in the second copy of $G$). The length of $P$ is exactly of the shortest route from home to work that passes through a(t least one) gas station.

Question $2$ can be solved similarly. First, guess the order in which the stores are visited (there are only $2$ possible choices). Then, create a graph $G'$ with 3 copies of $G$.
Intuitively, going from the first copy to the second copy means visiting the first store, and going from the second copy to third copy means visiting the second store.


Essential difference between Assembly languages to all other programming languages

The two most obvious characteristics of an assembly language are:

It is specific to a particular CPU architecture.
There is a one-to-one correspondence between assembly language commands and machine code instructions (once you strip out labels, assembler directives and code comments).

By contrast, a high-level language will have the following characteristics:

It is portable to some degree i.e. it can be compiled to run on several different target platforms.
It provides a layer of abstraction (control structures and data structures) which allows the programmer to ignore the low-level details of the target platform. As a result, there is no longer a simple one-to-one correspondence between language commands and machine code instructions.

However, this is not a black-or-white distinction; there is a grey area where low-level and high-level languages overlap. For example, cross assemblers take assembly language written for one platform and translate it into machine code that can run on a different platform (usually with some restrictions). And there are assemblers (sometimes called "high level" assemblers) that support simple control structures such as IF structures and FOR loops.


For any language $L$ over alphabet $\Sigma$,

$\overline{L} = \Sigma^*\setminus L$ is the complement of $L$: the set of $\Sigma$-strings not in $L$;
$L^*$ is the Kleene closure of $L$: the set of strings $w\in\Sigma^*$ such that we can write $w=w_1\dots w_k$ for some $k\geq 0$ such that each $w_i\in L$.  For example, if $L$ is the set of English words, then correcthorsebatterystaple is in $L^*$.

Now, $\overline{L}^*$ is something-star, where "something" is $\overline{L}$. That is, it's the Kleene closure of the complement of $L$: the set of all strings $w\in\Sigma^*$ that can be written $w_1\dots w_k$ such that each $w_i$ is not in $L$. Essentially, we read left-to-right, so you parse "$\overline{L}$" before you reach the star.

Conversely, $\overline{L^*}$ is something-complement, where "something" is $L^*$, the Kleene closure of $L$. That is, it is the set of all strings that cannot be written $w_1\dots w_k$ where each $w_i\in L$.

These are not necessarily the same languages. For example, consider $\Sigma=\{1\}$ and $L=\{11\}$.  Then $1\in\overline{L}$, so $\overline{L}^*=\Sigma^*$. However, $$\overline{L^*} = \overline{\{1^i\mid i\text{ is even}\}} = \{1^i\mid i\text{ is odd}\}\neq\Sigma^*\,.$$


What mathematical background is enough to go through the entire Knuth's TAOCP?

If your only exposure to math is undergrad level calculus, numerical analysis, and probability, you probably don't want to start out with computer science by reading The Art of Computer Programming. This is not an easy set of books. They're also not the hardest books out there in computer science, but they definitely expect some kind of background in discrete math and algorithm analysis. I would start with an easier book, maybe Introduction to Algorithms (CLRS), which is also mathematical and treats its topic formally, but is designed for undergraduate students without previous background in the field. You should also get a more solid background in discrete math—topics such as combinatorics, recursion, Big O, number theory—as well as linear algebra. Knuth co-authored another book called Concrete Mathematics that might help with that.

Working through CLRS and Concrete Mathematics is probably enough to start TAoCP. The first thing you should do is work through the math in Volume 1 of The Art of Computer Programming. Knuth covers several of the topics in combinatorics and discrete math that will reappear in later volumes. However, he typically doesn't spend a ton of time introducing you to the math he uses. He doesn't assume you know everything, but he does dive in pretty quickly. I would solve a bunch of the easier exercises in each topic to get a grasp on it, and leave the harder exercises for a cold winter's evening.

As for MIX, I wouldn't even bother with it. Programming in assembly language is not a terribly useful skill today, and modern assembly languages look nothing at all like MIX because it was designed before CPU architectures had standardized, before everyone was using 32-bit (or 64-bit) binary computers and it was sometimes desirable to support decimal computers or computers with kooky word sizes. In recognition of this, Knuth created MMIX, a more modern-styled assembly language, and he's now porting all the MIX code in earlier books to MMIX. I would just ignore the fake assembly code completely. I found that trying to remember MIX's idiosyncrasies was an impediment to learning the high-level ideas behind algorithm; the pseudocode and the prose were much more helpful. If you want to learn about low-level programming, go learn about computer architecture, and maybe learn some MIPS or ARM assembly, but do it separately from your studies of algorithms; it's a huge topic in its own right, and you won't do yourself any service by trying to learn both at the same time.

If, however, you insist on learning MIX or MMIX, you can hunt down one of the simulators that let you actually run the code, and learn it like you would any other programming language: by figuring out what it can do and solving some simple exercises. (IIRC, the book even has some MIX exercises that you can complete.) Again, though, I wouldn't. As much as I love the books, they were created in an earlier time, and some parts haven't aged well. MIX is one of those things.


Does this progressive image compression exists?

I believe that the Stationary Wavelet Transform (SWT) meets your requirements:
https://en.wikipedia.org/wiki/Stationary_wavelet_transform

1) Any given level of coefficients could be used to reconstruct the original image by running normal reconstruction but assuming zeros for the other levels.

2) Each level of coefficients stores data about a different range of spatial frequencies in the original image, and thus they can be recombined arbitrarily.

3) Unless you quantize when or after you perform the transform, the SWT is lossless.

4) I haven't done any processing time evaluation, but optimized libraries are available: https://www.mathworks.com/help/wavelet/ug/discrete-stationary-wavelet-transform-swt.html

In general though, unless you require translation invariance, you would benefit from the downsampling in the more common Discrete Wavelet Transform (DWT). The downsampling results in smaller images which requires less space to store and time to process. No information is lost by this downsampling as the frequency filters in the DWT filter out and then store (in the higher resolution levels) the frequencies that then get lost in the downsampling. The lower frequencies simply need fewer samples to be accurately reconstructed (https://en.wikipedia.org/wiki/Nyquist_frequency).


Why RAID 2 would ever be used instead of RAID 3?

RAID 2 doesn't use parity: it uses a Hamming code. This allows error correction as well as error detection. Remember that a parity bit is just a bit that tells you whether the sum of the other bits is odd or even. It wouldn't make sense to have more than one of those because they'd all be telling you the same thing.

If you're using RAID 3 with four data bits and one parity bit, all you can do is detect when an odd number of bits have changed. You read the four data bits, add them together (mod 2) and, if the answer isn't equal to the parity bit, then you know that something has been corrupted. But you don't know what has been corrupted: it could be any one of the data bits, or it could even be the stored parity bit. All the disc controller can say is, "Sorry, but something's gone wrong and I can't give you the data you wanted."
Note that, if two bits get corrupted, you won't notice since, e.g., 1+0+0+1=0+0+1+1.

In contrast, RAID 2 would store three error-correcting bits along with the four bits of data. Having the extra two bits gives you more power: you can now detect and fix any single-bit corruption. This works by looking simultaneously at all seven bits (four data, three EC). Because of the way the code is designed, any two valid combinations must differ by at least three bits. If you see a valid combination, you're happy. If you see an invalid combination that's only one bit different from a valid one, then it must be at least two bits different from every other valid combination, so you can fix the error on the assumption that it's more likely that one bit was corrupted than two. (See Wikipedia for full details).  We assume that three bits being corrupted simultaneously is so unlikely that it will never happen: in principle, that could corrupt one valid combination into a different one.

The above assumed that two-bit corruptions are much less likely than one-bit corruptions. An alternative RAID 2 set up when two-bit corruptions aren't so rare would be to say "I don't know if this invalid combination was a one-bit or two-bit error but something's gone wrong." That would allow you to detect all one-bit and two-bit errors, but not correct anything.


is the alignment between two sequences of points with 'no cross line' constraint an NP problem?

You could prove that something is in NP by reducing it to an NP-complete problem. However, it's usually much easier to just demonstrate a nondeterministic polynomial-time algorithm that finds a solution, and even easier to demonstrate a deterministic polynomial-time algorithm that verifies a given solution.

Now, the trivial answer to your question is "No, this is not in NP" because there's a type error. NP is a class of decision problems (i.e., problems where the answer is "yes" or "no"), whereas your problem is to compute some object that minimizes some criterion.  However, the decision version of your problem is in NP: this is the problem where you're given a target weight $w$ and asked if there's a solution with weight at most $w$. It's easy to check deterministically in polynomial time that a proposed solution does have weight at most $w$.

Beyond that, there's not much to say. Your problem seems under-specified to me because the trivial solution "Don't match anything at all" has weight zero, which is best possible as long as the weights are non-negative. If you tighten up the definition of the problem, my guess is that the non-crossing requirement constrains the problem so much that it will have a deterministic polynomial-time solution. For example, if you match the first element of sequence $A$ to anything other than the first element of sequence $B$, then the first element of sequence $B$ can't be matched to anything without crossing. This suggests that dynamic programming will give an efficient solution.


Cormen RB-DELETE_FIXUP(T,x) when x has no siblings

Let $x$ denote the node you want to delete and $p(x)$ its parent. If $x$ has no sibling, then it necessarily means that $x$ is a red node, otherwise two path from $p(x)$ could have a different number of black nodes (therefore the tree is not a Red-black tree).
So the situation where $x$ is black and has no sibling can never happen (and the tree in your example is not a Red-black tree).


Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Let's fix some names. Let $q_1, \dots, q_k$ be the query strings and $w_1, \dots, w_n$ the existing phrases. Denote with $w_{i,1}, \dots, w_{i,k_i}$ the words contained in phrase $w_i$, and with $a \sqsubseteq b$ the relation "$a$ is a prefix of $b$".

Currently, you have implemented to obtain this:

$\qquad\displaystyle \{ i \in [1..n] \mid \forall j \in [1..k]\ \exists j' \in [1..k_i].\ q_j \sqsubseteq w_{i,j'}\}$.

Note how the $\exists$-operator does not preclude the same $j'$ for multiple $j$, and that's your problem (as far as I can tell). What you want is

$\qquad\displaystyle \{ i \in [1..n] \mid \exists J = \{j_1, \dots, j_k\} \subseteq [1..k_i]\ \forall j \in [1..k].\ q_j \sqsubseteq w_{i,j_j}\}$.

One way to implement this is to go with the double-indexing I used to describe the problem formally: each node gets the set of labels $(i,j)$ if its corresponding string is a prefix of $w_{i,j}$. Now, $i$ is a match if

every $q_l$ leads to a node with label $(i,\_)$ and
the second components of these labels are pairwise distinct (if there are multiple $(i,\_)$ for a single $q_l$, one has to check if there is a choice fulfilling the condition).

In your example, instead of just adding 6 to all these nodes you list, you'd add (5,1) and (6,1) to the prefixes of programming, and (6,2) to those of puzzles. Now, prog p gives you (5,1), (6,1) for prog and (5,1), (6,1), (6,2) for p; you can exclude 5 because it has the same second component for both query phrases whereas 6 has a "valid" match with (6,1) and (6,2).


How to partition a set into a given number of disjoint subsets subject to some conditions?

This problem is NP-hard by reduction from Vertex Cover.

In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$.  (Equivalently: Is it possible to kill every edge in $G$ by deleting at most $r$ vertices?)

First, partitioning $A$ into $s$ disjoint subsets is equivalent to assigning each element in $A$ exactly one of $s$ possible labels.  The basic idea of the reduction is to create a label $S_j$ for each vertex $v_j$ in $V$, and to "allow" each edge to be assigned only one of the two labels corresponding to its endpoints, in the following sense: assigning an edge a corresponding label introduces no (genuine) constraint on what other edges can be assigned the same label, while assigning an edge to a non-corresponding label prevents any other edge being assigned the same label -- which of course has the effect of pushing up the number of distinct labels required.

To construct an instance $(A, a, s)$ of your problem from an instance $(G, r)$ of Vertex Cover:

Set $k$ to $|E|$, and create an element $(i, j)$ in $A$ for each edge $v_iv_j$ in $E$.  (These pairs can be thought of as the integers $1, \dots, k$; any bijection between them will do.)
Set $a_{(b, c), d}$ to $|E|$ if $d=b$ or $d=c$; otherwise, set $a_{(b, c), d}$ to 1.
Set $s=r$.

If $(G, r)$ is a YES-instance of Vertex Cover, then it's easy to see that the just-constructed instance of your problem is also a YES-instance: just pick the labels $S_j$ corresponding to the vertices $v_j$ in any solution $U$, and for each edge $v_bv_c \in E$ assign the corresponding element $(b, c) \in A$ whichever one of the labels $S_b$ or $S_c$ was picked (choose arbitrarily if both labels were picked).  This solution uses $s$ subsets, and is valid because the only $a_{ij}$ in force are those for corresponding labels, which have the (non-) effect of preventing more than $|E|$ edges being assigned the same label.

It remains to show that a YES-instance $X=(A, a, s)$ of your problem implies that the original $(G, r)$ is a YES-instance of Vertex Cover.  This is slightly more complicated, since a valid solution $Y$ to $X$ may in general assign an edge $(i, j)$ a non-corresponding label $S_m$, i.e., $m \notin \{i, j\}$, meaning that we can't necessarily "read off" a valid vertex cover $U$ from a valid solution $Y$.

However, assigning a non-corresponding label has a high cost that severely limits the structure of the solution: whenever an edge $(i, j)$ is assigned such a label $S_m$, with $m \notin \{i, j\}$, the fact that $a_{(i, j), m} = 1$ ensures that it must be the only edge assigned this label.  So, in any solution $Y$ containing such a non-correspondingly-labelled edge $(i, j)  \mapsto S_m$, we could construct an alternative solution $Y'$ as follows:

Arbitrarily choose the new label $S_z$ for $(i, j)$ to be either $S_i$ or $S_j$.
Assign $(i, j)$ this new label.  If this results in an invalid solution, it must be because exactly one other edge $(i', j')$, $z \notin \{i', j'\}$ had already been assigned the label $S_z$.  In that case, set $(i, j) = (i', j')$ and go to step 1.

The above algorithm must terminate in one of two ways: either a new label $S_z$ is found that introduces no contradiction, or a complete cycle of vertices is found.  In the former case, a valid new solution with $s-1$ sets is found, while in the latter case a valid new solution with $s$ sets is found; either way, we have constructed a valid new solution with at least one more edge assigned to a corresponding label.  After repeating this entire process at most $|E|$ times, we will have produced a valid solution $Y''$ from which a solution to the original Vertex Cover problem can be read off.

This construction is clearly polynomial time, so it follows that your problem is NP-hard.


Complexity of "does a directed graph have <=1 Hamiltonian cycles?"

Your problem clearly belongs to $\mathsf{co\text{-}NP}$. An easy "no" certificate consists of 2 distinct Hamiltonian cycles. The certificate can clearly be checked in polynomial-time.
The same certificate is also a "yes" certificate for problem in 3 (i.e., "Does a directed graph G has at least 2 Hamiltonian cycles?"), showing that it belongs to $\mathsf{NP}$.


What you are doing is called (simple) "object pooling", a topic that has been discussed numerous times. It can be said to have nothing to do binary trees.

The simplest and yet efficient approach is to use a single stack or list, just like the C++ vector class or Java ArrayList, so that you do not have to maintain the "linked list" to keep track of the different allocated node blocks. Initially a block of $N$ nodes is allocated. Use a tail pointer to remember the first free node. Whenever it runs out of free nodes, just allocate $2N$ nodes or $cN$ nodes for a factor $c>1$ of your choice. Memory copy the existing nodes to the new block and free the previous block. Do not worry about the performance of copying nodes, which is just one (system) call that should have been optimized by your language runtime and operating system.

In general, do not write these kinds of utilities from scratch by yourself unless as an exercise to broaden your skill set or enhance your understanding. For example, there is an object pool in boost library if you can use C++. Also, do not do it just for the sake of performance unless you have identified node allocation and deallocation is the performance bottleneck. The recent c/c++ runtime might be fast enough for you on object allocation and deallocation.

I would recommend that you search "object pooling" on the web or, more directly, inside github.com with your choice of language, C if you want to dive further. You will be able to find many articles and many working implementations, (for example, simple object pool.

Finally, in many cases, especially in many programming contests, all you need to do is to preallocate a huge number of nodes like a few millions of them upfront. Then just use them without deallocation. Simple, stupid and wonderful.


Based on some research into other things related to TMs, I discovered that any NDTM that has at most $k$ possible branches at each step can be modified into an NDTM that has at most $2$ possible branches at each step at the cost of a $\log_2(k)$ slowdown. Though I can not find any mention of this anywhere in the textbook, I assume this is what the authors are assuming.


Cancellation of inequalities in floating point arithmetic

Consider the case that x and y hold the largest representable value for the current type, and z is positive infinity. By the rules of floating point arithmetics, x + y is now infinity, which isn't less than infinity. On the other hand, z - y is also infinity, which the largest representable value is less than.
Another example would be when x is very small negative, and y = z and much larger in magnitude than x. Then x + y = y = z, but z - y = 0, which is larger than x.
The examples work for your second question as well if you flip the signs of all numbers - !(l > r) is nearly equivalent to l <= r. NaNs break the equivalence, but those aren't useful as examples to your question anyways.


Sort complexity expressed via distinct number of elements

You can use a balanced binary search tree to sort $A$ in time $O(a\log\alpha)$ by going over the elements of $A$, for each element searching whether it already appears in the tree, inserting it if it isn't already there. You can then perform the second stage in $O(\log \alpha)$ per element of $B$, for a total of $O(b\log\alpha)$.

If you are allowed to use hashing on the elements of $A$ and $B$, then you can use a dynamic hash table to compute the intersection in expected $O(a+b)$ time by using a similar strategy.


Simple generator of pseudo-random permutations of variable length short sequence

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.


How this expression leads to the given sequence

Stirling numbers of the second type satisfy
$$ \newcommand{\stirling}[2]{\genfrac\{\}{0pt}{}{#1}{#2}}\stirling{n}{0} = 0, \qquad (n \neq 0)$$
and so there is no need to define $A(0;x)$, and so the formula seems to work. You can also play with the Mathematica code which can be found in the entry corresponding to the sequence. I am puzzled, however, what is meant by "fractional iteration of $e^x-1$".

The recurrence given is for generating functions. Let's rewrite it:
$$
A_1(x) = 1, \qquad A_n(x) = \sum_{k=1}^{n-1} \stirling{n}{k} A_k(x) x.
$$
Using a table for the Stirling numbers, we get
$$
\begin{align*}
A_1(x) &= 1 \\
A_2(x) &= \stirling{2}{1} A_1(x) x = 1 \cdot 1 \cdot x = x \\
A_3(x) &= \stirling{3}{1} A_1(x) x + \stirling{3}{2} A_2(x) x = 1 \cdot 1 \cdot x + 3 \cdot x \cdot x = x + 3x^2 \\
A_4(x) &= \stirling{4}{1} A_1(x) x + \stirling{4}{2} A_2(x) x + \stirling{4}{3} A_3(x) x \\ &= 1 \cdot 1 \cdot x + 7 \cdot x \cdot x + 6 (x + 3x^2) x  = x + 13x^2 + 18x^3
\end{align*}
$$
and so on. The numbers in the table are $a(n,k) = A_n(x)|_{x^k}$ :
$$
\begin{align*}
a(2,1) &= 1, \\
a(3,1) &= 1, \\
a(3,2) &= 3, \\
a(4,1) &= 1, \\
a(4,2) &= 13, \\
a(4,3) &= 18,
\end{align*}
$$

If you prefer an actual recurrence on the coefficients, here is what you get:
$$
\begin{align*}
a(n,l) = \begin{cases} 1 & l = 1, \\ \sum_{k=l}^{n-1} \stirling{n}{k} a(k,l-1) & l > 1. \end{cases}
\end{align*}
$$


Space complexity of breadth-first search

That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found at depth $d$, that is precisely the number of nodes awaiting for expansion.

Indeed! You could actually remove any node after expanding it. So far, you are correct when you are guessing that you could actually remove all nodes expanded in the previous depths whose sum gets so far as $b^0+b^1+b^2+b^3+...+b^{d-1}$. Now, here comes the question:

Why would you do it? Why would you actually remove those nodes? If you do not remove them, you could easily implement a duplicate detection mechanism: if a node $n$ is found at depth $d_1$ it is stored in memory. If it is found again at depth $d_2$, $d_2>d_1$ then its expansion can be skipped because a shortest path to it was already found ---given that the edge costs are all the same.
Oh yeah! you might be thinking that this idea is not worthy as it requires to store in memory a rather large number of nodes: $b^0+b^1+b^2+...b^{d-1}$, isn't it? So that while duplicate detection seems desirable it might be too costly.

Note however that the sum of the terms of the geometric progression $b^0+b^1+b^2+...+b^{d-1}$ equals $\frac{b^d-1}{b-1}$ so that adding duplicate detection requires only a small fraction ($b-1$) of the nodes actually required to be stored in memory ($b^d$).

In other words, we say that the memory requirements of Breadth-First Search are dominated by the number of nodes awaiting to be expanded, $b^d$. Additional memory can be used as the total number of nodes in memory, $b^d+\frac{b^d-1}{b-1}=\frac{b^{d+1}-1}{b-1}$ (in case that duplicate detection is implemented), is much smaller than the number of nodes required to store the nodes in the subsequent level, $b^{d+1}$.

Test these numbers, even if $b=2$, note that with duplicate detection, the number of nodes in memory is $2^{d+1}-1$ which is smaller than $2^{d+1}$, the number of nodes required to store in memory for exploring an additional level without duplicate detection. The situation worsens significantly if you consider larger branching factors. For example, with $b=10$, the number of nodes required with duplicate detection is $\frac{10^{d+1}-1}{9}$, which is only 11% of the nodes required to be stored in memory for exploring the subsequent depth without duplicate detection, $10^{d+1}$ ...

Hope this helps,


Skienna's recursive algorithm for edit distance

The two strings s and t are compared starting from the high index,
down to index 1. This is not visible since the initial call to
string_compare is not provided. The i and j arguments for that
initial call are the length of strings s and t.

It should be noted that s and t could be globals, since they are
the same in all calls.

A call to the function string_compare(s,t,i,j) is intended to
compute the minimum edit distance of the prefixes s[1..i] and t[1..j].
It first compares the two strings at indices i and j, and the
recursively at lower indices.

It always tries 3 ways of finding the shortest distance:

by assuming there was a match or a susbstitution edit depending on
whether s[i]==t[j];
by assuming there is an insertion edit of t[j];
by assuming there is an deletion edit of s[i];

Then it computes recursively the sortest distance for the rest of both
strings, and adds 1 to that result, when there is an edit on this call.

When s[i]==t[j] the two strings match on these indices. Hence the
corresponding indices are both decremented, to recursively compute the
shortest distance of the prefixes s[1..i-1] and t[1..j-1]. A
proper match does not increase the distance. Hence
dist(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1]).

When s[i]=/=t[j] the two strings do not match, but can be made to
match by a substitution edit. Hence the same recursive call is
possible, but the resulting shortest distance must be incremented by
one for the substitution edit. Hence dist(s[1..i],t[1..j])=
dist(s[1..i-1], t[1..j-1])+1.

That is why the function match returns 0 when there is a match, and
1 when there is none.

Another possibility is not to try for a match, but assume that t[j]
is due to an insertion edit in the case of the smallest distance.
Hence that inserted symbol is ignored by replacing t[1..j] by
t[1..j-1], ie by computing the shortest distance of s[1..i] and
t[1..j-1], which is string_compare(s,t,i,j-1), and then adding 1
for the insertion edit.

The next and last try is the symmetric one, when one assume that the
symbol s[i] was deleted, and thus does not have to appear in t.

The results of the 3 attempts are strored in the array opt, and the
smallest value of the 3 is kept as shortest distance for s[1..i] and
t[1..j].

The decrementations of indices is either because the corresponding
string elements match, or because they have been taken into account by
an edit operation.


Branch and bound for minimum linear arrangement

One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage it yourself.

I have seen it solved in two ways using this technique. We can slightly improve your bounding algorithm as well.

The textbook method

Using binary variables $x_{ij}$ representing $f(i) = j$, you can define continuous variables $f(i) = \sum_{j=1}^n j x_{ij}$

Add constraints $\sum_i x_{ij} = 1$ and $\sum_j x_{ij} = 1$ representing that one position is assigned one and only one node.

For each edge, the cost $c_e$ has two constraints : $c_e \geq f(i) - f(j)$ and $c_e \geq f(j) - f(i)$, and you want to minimize $\sum_e c_e$

You can give this problem to an integer programming solver, which will be happy to do the backtracking for you and more - or you can solve the linear programming relaxation yourself each time (just if you want to learn, the solver optimizes it internally).

Another relaxation

Instead of using the positions as binary variables, you can use $f(i) < f(j)$ i.e. node $i$ goes before node $j$. This is more adapted if you want to do the branching yourself and don't specify those variables explicitly.

With this approach, you can sometimes have a faster problem to solve at each node - here it can be solved as a simpler minimum-cost flow problem as shown by this paper. I wouldn't recomment it unless you are willing to investigate much time and research into your problem.

Other techniques

For branch-and-bound, any lower bound on your cost function will do.
For small problems your bounding approach is perfectly fine.

You could make it tighter: for each edge with an unplaced node, pick the best possible free labeling to estimate its cost. Several edges may use the same placement for different nodes, but this will be better than estimating their cost as 0.

There are many possible variations on this scheme: pick the best free label for each unlabeled node (irrespective of overlaps) or consider overlaps only inside small groups of nodes.


Is purely functional programming in some situations less efficient than imperative programming?

Yes.  There are problems where we can prove there is a $\Omega(\lg \lg n)$ factor slowdown.  We also know that the slowdown is at most $O(\lg n)$ in all cases.  See What classes of data structures can be made persistent?.


Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak

You are correct that $T$ needs to know which Turing machine accepts $L$. This Turing machine is $M$, and you can hardcode it into $T$. There is absolutely no problem with that.

Here is a similar example. Suppose that there is a proof that $P \neq NP$. Then there is a Turing machine that prints a proof of $P \neq NP$.

Proof: According to the assumption, there is a proof $\pi$ that $P \neq NP$. Construct a Turing machine $T$ that prints $\pi$. Then $T$ prints a proof of $P \neq NP$. $\quad\square$

What seems to worry you is that you think of $T$ as accepting $L$ as an input, from which it is supposed to come up with the Turing machine $T$. But this is not the case – all we have to do is to show that for each $L$ there exists an appropriate Turing machine $T$. Moreover, it is not clear how $T$ would accept $L$ as input – a language is, in general, an infinite object.

Sometimes we do need to be worried about the issue that you raised. Here is an example. Let $L_1,L_2,\dots$ be an infinite sequence of decidable languages. For each $L_i$, there is a Turing machine $T_i$ that decides $L_i$. But is there a Turing machine $T$ that accepts an index $i$ and a word $w$ and returns whether $w \in L_i$? Not necessarily (I'll let you come up with a counterexample). When such a machine $T$ does exist, we say that $L_1,L_2,\dots$ are uniformly decidable.

No such uniformity condition appears in your question. We could impose such a condition artificially by providing $L$ as an input via a Turing machine, not necessarily running in exponential time, that accepts $L$. In this case, your criticism would be valid – given a Turing machine that accepts a language in $\mathsf{EXP}$, it is not clear how to find a Turing machine accepting the same language and running in exponential time.


Is $P$ defined for TM which decide or accept a language?

Both definitions are the same. They just use a different wording. The difference between "decide" and "accept" is commonplace in computability theory, but in complexity theory different terminology is typically used, since we usually deal with machines that always halt.

The class $\mathsf{P}$ consists of all languages $L$ for which there exists a Turing machine $T$ such that:

$T$ runs in polynomial time. This means that there is a polynomial $p(n)$ such that $T(x)$ stops within $p(|x|)$ steps, where $|x|$ is the length of $x$.
If $x \in L$, then $T$ accepts $x$.
If $x \notin L$, then $T$ rejects $x$.

Suppose we have a machine $T$ with a different guarantee:

If $x \in L$, then $T$ halts after $p(|x|)$ steps.
If $x \notin L$, then $T$ never halts.

The language $L$ is in $\mathsf{P}$, since we can construct a different machine $T'$ which simulates $T$ for $p(|x|)$ steps, accepts the input if $T$ halts, and rejects the input if $T$ doesn't halt. Perhaps that answers your question.


How can primitive recursion be a special case of minimization?

Your suspicion is correct. Without primitive recursion we get a very small class of functions, namely maps of the form $f(\vec{x}) = x_i + m$, possibly with some undefined values.
Let $\mathcal{F}_k$ be the least class of partial maps $f : \mathbb{N}^k \to \mathbb{N}$ closed under $0$, successor, projections, composition and minimization.

Theorem: For every $f \in \mathcal{F}_k$ there exist $i$ and $m$ such that, for all $\vec{x} = (x_1, \ldots, x_k) \in \mathbb{N}^k$, either $f(\vec{x})$ is undefined or $f(\vec{x}) = x_i + m$.

Proof. We proceed by induction on the structure of $f$. It is obvious that $0$, successor, projections, and compositions preserve the stated property. Now consider $f \in \mathcal{F}_k$ which is defined by minimization of $g \in \mathcal{F}_{k+1}$, so that
$$f(\vec{y}) = \min \{x \in \mathbb{N} \mid g(x, \vec{y}) = 0\}.$$
By induction hypothesis there are two possibilities:

There exists $m$ such that $g(x, \vec{y}) = x + m$ whenever $g(x, \vec{y})$ is defined. In this case:

If $m = 0$ then $f(\vec{y}) = 0$
If $m > 0$ then $f$ is everywhere undefined

There exists $m$ and $i$ such that $g(x, \vec{y}) = y_i + m$ whenever $g(x, \vec{y})$ is defined. In this case:

if $m = 0$ then $$f(\vec{y}) = \begin{cases}0 & \text{if $y_i = 0$ and $g(0, \vec{y})$ is defined}\\ \text{undefined} & \text{otherwise} \end{cases}$$
if $m > 0$ then $f(\vec{y})$ is everywhere undefined.

In all cases minimization preserves the stated property. $\Box$
Let us also try to speculate how the falacy "primitive recursion is a special case of minimization" arises. Suppose $f : \mathbb{N} \to \mathbb{N}$ is defined by primitive recursion by
\begin{align*}
f(0) &= k\\
f(n+1) &= h(n, f(n)),
\end{align*}
where $h : \mathbb{N}^2 \to \mathbb{N}$ is primitive recursive. Then there is a primitive recursive function $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ such that
$$
g(x, y) = \begin{cases}
0 & \text{if $f(x) = y$},\\
1 & \text{otherwise.}
\end{cases}
$$
The map $g$ involves a good deal of arithmetic, encoding of lists as numbers, etc. Cruicially, $g$ may be more complicated than $f$ and $h$.
Therefore, we could define $f$ by minimization as
$$f(x) = \min \{y \mid g(x,y) = 0\}.$$
However, we need the entire primitive recursion machinery to get the suitable $g$, so we cannot infer from this that primitive recursion can be dispensed with in the presence of minimization.


Algorithms with O(sqrt(N)) SPACE complexity?

$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called meet in the middle scheme.

Two notable examples off the top of my head are the classical sieve of Eratosthenes and the baby-step giant-step algorithm for the discrete logarithm over a finite group.


I am thinking if jk = ik, let's denote jk=ik=m, then we think of subsequences of [0,m-1] and [m+1,n], treat [m+1,n] as a standalone tree. And according to the paper, T and T' will be of same weighted path length if αn = α. So let's make a tree of subsequence [m+1,n] with last item being α, with weighted path length sum being Tk. And then replace the right-subtree of jk/ik with Tk for both T and T'.
Let's denote the weighted path length sum of [0, m-1] of T and T' being T0 and T0'. Because jk = ik, the levels of T and T' are both k. SoC(T) = T0 + k*Ak + Tk(starting from level k+1); C(T') = T1 + k*Ak + Tk(starting from level k+1); And C(T) should be equal to C(T'). So T1 = T1'
Replace right subtree of ik of T with right subtree of jk of T' will yield T'' with same weighted path length as T'.
PS: actually I don't quite know how it proves j2<=i2, j3<=i3 using induction and left-right symmetry, anyone can help answer that?


Does approximation ratio depend on the input size $n$?

Not all NP-hard problems admit constant factor approximation algorithms (in polynomial-time). One such well-known example is the problem of finding a maximum clique, which cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$ unless P = NP (see Wikipedia, though this is also mentioned in the introduction of Williamson & Shmoys).


The direct edge (a) from initial state 1 to final state 3 is not included in the RE.


Algorithm for selecting a sample that's as spread out as possible?

I assume that for dates $d_1\leq d_2\leq\cdots\leq d_n$ you want $k>1$ samples of minimal total absolute distance from the ideal sample points $s_i=d_1+(i-1)(d_n-d_1)/(k-1)$, $i\in[k]$.

If you can repeat elements, just sample at $\operatorname{argmin}_{j\in[n]}|d_j-s_i|$ for each $i\in[n]$.

Without repeating elements the following dynamic program solves your problem in time $O(n^3)$ and space $O(n^2)$: let $M(i,j)$ be the minimal total absolute distance for $k-i+1$ samples chosen from $a_j,\ldots,a_n$ from the ideal samples $s_i,\ldots,s_k$. Distance $M$ satisfies
\begin{align*}
M(i,j) =
\begin{cases}
  \min_{j\leq j'\leq n} |d_{j'}-s_i|+M(i+1,j'+1), & \text{$i\leq k$, $j\leq n$, }\\
  0, & \text{$i>k$},\\
  \infty, & \text{otherwise},
\end{cases}
\end{align*}
and $M(1,1)$ is the minimum solution value.


Algorithm to compute power function on interval [0, 1]

The Weierstrass Approximation Theorem states that any continuous function can be approximated on a bounded interval $[a, b]$ as closely as desired by a polynomial. In practice, instead of using Taylor series expansions, one uses polynomial minimax approximations $p(x)$ which approximate the function on the chosen interval with the minimal maximum error (thus the name).
When one looks at the graph of the error function $f(x) - p(x)$ one observes that it oscillates such that all extrema are of equal magnitude and neighboring extrema have opposite sign (equi-oscillation property), and that there are a total of $n+2$ extrema for a polynomial of degree $n$. This behavior of the error function can be used to construct the minimax polynomial, as also noted in gnasher729's answer.
The standard algorithm used to do this is called the Remez algorithm, named after the Russian mathematician who published it in 1927. This functionality can be found in ready-to-use form in widely used tools such as Maple and Mathematica, as well as the software tool Sollya, which provides an fpminimax command to generate minimax polynomial approximations. One can also create one's own implementation of the Remez algorithm, and I have used such code for this answer.
While the minimax polynomial is well defined mathematically, when the coefficients need to be stored in a finite-precision floating-point format and the polynomial evaluated is evaluated in finite-precision floating-point arithmetic, the error
function $(f(x) - p(x)$ becomes deformed and no longer satisfies the equi-oscillation criterion. That means we wind up with a polynomial that is merely close to the true minimax polynomial. Many tools do not adjust for this effect at all, delivering coefficients based on high-precision internal computations. Sollya takes the finite-precision storage of the coefficients into consideration, and thus can often deliver superior results.
A minimax polynomial of degree five suffices to approximate $x^{2.2}$ to within the accuracy desired by OP. $f(x)=p(x)+\epsilon, \:\: |\epsilon| < 7.4\cdot10^{-5}$. We can observe the equi-oscillation property of the error function $f(x) - p(x)$ and its seven extrema by plotting it, e.g. with Wolfram Alpha. Exemplary C code looks as follows:
/* Approximate x**(2.2) on [0,1] with minimax polynomial. Max. err < 7.4e-5 */
float pow_2p2_minimax (float x)
{
    const float c0 =  1.06425546e-1f; //  0x1.b3eb46p-4
    const float c1 = -3.56089801e-1f; // -0x1.6ca2cep-2
    const float c2 =  5.86735249e-1f; //  0x1.2c6890p-1
    const float c3 =  6.73461437e-1f; //  0x1.58cff0p-1
    const float c4 = -1.05324369e-2f; // -0x1.59207cp-7
    const float c5 =  7.38649687e-5f; //  0x1.35cfe8p-14
    return ((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5;
}

Note that the minimax polynomial does not return zero at the origin. If we desire this property, we can add this additional constraint by using $f(x) = x^{2}p(x) +\epsilon$. An example, with $|\epsilon| < 1.33 \cdot 10^{-4}$, is shown in this exemplary C implementation (plot of error function):
/* Approximate x**(2.2) on [0,1] with constrained minimax. Max. err < 1.33e-4 */
float pow_2p2_constraint (float x)
{
    const float c0 = -3.66555989e-1f; // -0x1.775a74p-2
    const float c1 =  1.19028902e+0f; //  0x1.30b6c8p+0
    const float c2 = -1.55231142e+0f; // -0x1.8d6448p+0
    const float c3 =  1.19035530e+0f; //  0x1.30bb20p+0
    const float c4 =  5.38091123e-1f; //  0x1.1380aep-1
    return x * x * ((((c0 * x + c1) * x + c2) * x + c3) * x + c4);
}

The computation of $x^{1/2.2}$ is a bit trickier. The easiest approach that does not suffer from premature underflow seems to be the following: Compute $y = \sqrt{\sqrt{x}} = x^{\frac{1}{4}}$, then compute $y^{\frac{20}{11}} = p(y) + \epsilon$ = $x^{\frac{5}{11}} = x^{1/2.2}$. The square root function is very fast on many modern processors, but slow on others, so this may not be a universal win, depending on how pow() is implemented. To achieve the error bound desired by OP, a minimax polynomial of degree six is needed, resulting in $|\epsilon| < 7.5 \cdot 10^{-5}$. Exemplary C code looks like so:
/* Approximate x**(1/2.2) on [0,1] with minimax polynomial. Max. err < 7.5e-5 */
float pow_0p4545_minimax (float x)
{
    const float c0 =  3.07896197e-1f; //  0x1.3b4924p-2
    const float c1 = -1.06079876e+0f; // -0x1.0f9082p+0
    const float c2 =  1.48817670e+0f; //  0x1.7cf926p+0
    const float c3 = -1.18180847e+0f; // -0x1.2e8b00p+0
    const float c4 =  1.42678642e+0f; //  0x1.6d41e0p+0
    const float c5 =  1.98969673e-2f; //  0x1.45fdeep-6
    const float c6 = -7.45610159e-5f; // -0x1.38bb48p-14

    /* compute x**0.25 */
    x = sqrtf (sqrtf (x));
    /* compute (x**0.25)**(20/11) = x**(1/2.2) */
    return (((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5) * x + c6;
}


Problem in finding the floating point representation?

Both answers seem wrong to me. A quick conversion in C++:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

int main (void)
{
    float x = -10.75;
    uint32_t* p = (uint32_t*)&x;
    printf("%x\n",*p);

    return 0;
}

Gives the output: c12c0000

Which is 1 10000010 010110000…

Your mantissa calculation is the correct one, but the binary exponent is +3, not -3 (that is, your number is greater than 1, not less than 1). In bias-127, that exponent becomes 130 (decimal).


The notation $\|x_n - \mu\|^2$ stands for the squared $L_2$ norm of the vector $x_n - \mu$.
The squared $L_2$ norm of the $d$-dimensional vector $v = \begin{pmatrix} v_1 & \cdots & v_d \end{pmatrix}$ is $$\|v\|^2 = v_1^2 + \cdots + v_d^2. $$
In particular, when $d = 1$, we have $\|v\|^2 = v_1^2$.
The formula you state works for the Gaussian multivariate distribution, when the various variables are independent and have the same variance $\sigma^2$. The formula in the general case is a bit more complicated.


How can lazy learning systems simultaneously solve multiple problems?

Let's see:

  Because the target function is approximated locally for each query to
  the system,

If i am going to predict the class (for example) of a brand new instance i compare it with the most similar in the train dataset. Imagine a 2D graphic with lots of points and i put the new point, so i compare with the other points locally, and the class of the nearest to it will help me say what is its class.

  lazy learning systems can simultaneously solve multiple problems
  and deal successfully with changes in the problem domain.

Maybe, these problems are the ones created by the eager methods that try to simulate the hyperplanes (boudaries) in a function, in logic predicates, etc between the classes and these hyperplanes make lots of mistakes. And simple local comparisons with the similarity with the train dataset could do a better work.


Names of power-of-two bit operations on bitsets that would not assume any number interpretation

You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers $0,\ldots,7$ (where $0$ is the LSB and $7$ is the MSB), then $00010010$ is the same as $\{1,4\}$.

Your first function asks whether the set has size $1$. If we name the bits using numbers as above, the second function is maximum and the third is minimum.


Is O((n^2)*log(n)) greater than O(n^(2.5))?

In order to compare 2 complexities just calculate a limit of their ratios as below:

$\displaystyle\begin{align*}
 \lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}}
   &= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}}
    = \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}}
    = \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\
    &\underset{\left| k = \sqrt{n} \right|}{=}
      \ \ \lim_{k\to\infty}\frac{2log{(k)}}{k}
    = 2\lim_{k\to\infty}\frac{log{(k)}}{k} \\
    &\leq 2\lim_{k\to\infty}\frac{ln{(k)}}{k} \\
    &\overset{\ast}{=} 2\lim_{k\to\infty}\frac{(ln{(k))'}}{k'}
    = 2\lim_{k\to\infty}\frac{\frac{1}{k}}{1}
    = 2\lim_{k\to\infty}\frac{1}{k} \\
   &= 0
\end{align*}$

We use L'Hôpital's rule to simplify calculating a limit for $\frac{\ln(k)}{k}$ at *.

As you can see, $O(n^2\times\log(n))$ is lower than the other.


Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see problem 2). So in that sense it's not really a modification, it's how Dijkstra himself described the algorithm to begin with. As Wikipedia puts it:

Dijkstra's original algorithm found the shortest path between two given nodes,[6] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

([6] is the same paper I linked to)
However, in my perception, the original version is the more popular one.
To make the exit condition a bit more precise, the algorithm can terminate when a goal node is taken out of the frontier. That can also happen if a goal node is tied for the lowest cost with other nodes. The same applies to A*. I intentionally use "a goal", because Dijkstra's algorithm also works with multiple goals or with a predicate that is evaluated to determine whether a node is a goal node.
By the way a recurring incorrect variant of Dijkstra's algorithm is to test whether a node is the goal when it is first reached and then terminate, but this fails to take into account that as long as a node is still in the frontier, it may be possible to find a shortcut to it.


Hash values that are impossible to reach

Regarding common cryptographic hash functions such as the SHA-2 family, it is highly likely that they are surjective (i.e. all potential $2^{256}$ values of SHA2-256 have a preimage). However, given $y$, finding $x$ such that $\text{SHA2-256}(x) = y$ is believed to be a computationally infeasible problem — that's preimage resistance, one of the defining properties of cryptographic hash functions. It's possible that there's a non-constructive way to provide that SHA2-256, but no such way is known, and as far as I know cryptographers tend to think the only way these functions might be proven surjective is by providing a way to compute inverses, which would mean that the functions would be broken.

To summarize, given $y$, it is probably (in the we-believe-it-but-we-could-be-wrong sense) theoretically possible to find $x$ such that $\text{SHA2-256}(x) = y$, but probably (in the chance-for-a-random-$y$ sense) practically impossible.

Hash functions for applications such as hash tables are a different matter. The point of such functions is to spread the input as wide as possible onto a finite-size output, so it is beneficial to cover as much output range as possible. It's often easy to find preimages for these hash functions, but that isn't guaranteed. A given hash function may or may not cover its whole potential $2^N$ output set.


Finding a maximal independent set in parallel

There is a minor mistake, the probability of $v$ being minimal is $1/(d+1)$. That doesn't change anything, but it is still worth pointing out.

The problem is that the events you are summing aren't disjoint. Consider two vertices that aren't adjacent but have a common neighbour. If both vertices end up being minimal amongst their neighbours, then the common neighbour gets counted as being coloured twice.

We need to examine what happens in a vertex more closely. Let's compute the probability (and thus expectation of the indicator variabele) of a single vertex getting coloured.

Assume for the sake of analysis that the graph is $d$-regular and contains no triangles or squares. We will compute the chance that a given vertex $v$ does not get coloured. There are $d+1$ possibilities: the $v$ might be the smallest amongst it neighbours, $v$ might be the second smallest, third smallest, and so on... We are not interested in the case that it is the smallest, since then it gets coloured.

If $v$ is the second smallest, there is one vertex that is smaller. The probability of this vertex being smallest amongst its neighbours is $\frac{1}{d}$ (and thus $v$ getting coloured). The probability of the remaining neighbours being smallest amongst their neighbours is 0 (since $v$ is smaller). The total probability (of $v$ not getting coloured) from this case is $\frac{1}{d+1}\cdot\frac{d-1}{d}$.

If $v$ is third smallest, there are two smaller vertices. The probability from this case is $\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

Continuing on like this, we find that the probability that $v$ does not get coloured is $\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. The probability of a given vertex getting coloured is thus $1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. As $d\to \infty$, the probability becomes $\frac{1}{e}\approx 0.368$.

Hence the probability that a given vertex gets coloured is a constant, so the expected number of vertices that gets coloured in the first step is indeed $O(n)$.

That does not make the algorithm $O(1)$. Assuming the probability stays constant (which is not entirely justified considering nodes get coloured and no longer participate in the algorithm, the graph does not remain $d$-regular), in the $k$-th step there will be (in expectation) ${(\frac{1}{e})}^kn$ uncoloured nodes. The decay is exponential, so the algorithm takes $O(\log n)$ steps.

Perhaps somebody else will be able to offer a more precise analysis, but from my argumentation it seems likely the algorithm is $O(\log n)$.


Using consecutive outputs from the PRNG to form a tuple is fine if you use a good enough PRNG.  So, one reasonable approach is to simply use a good PRNG, and then not waste brain power worrying about issues like this.

One way to get a "good enough" PRNG is to use a cryptographic-quality PRNG.

RANDU is a truly lousy PRNG (for instance, the least significant bit of its output is not random at all), so no surprise that all sorts of bad things happen when you use its output.  But the root cause there is not using tuples from RANDU; the root cause is using RANDU.


Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution

It's true that we can run $A$ even more times, but $O(\log n)$ times suffices for us to obtain a certainty of $1 - 1/(100n)$ (say) for each $x_i$. Applying the union bound, we deduce that the algorithm finds a valid truth assignment with probability at least $1 - 1/100$.

If you run $A$ polynomially many times then you get an exponentially small error, which is not needed here.


Formula to see where a memory address can be depicted in cache?

Your Result Is Correct

Tag
Set
Offset

0011 0000
0000 1010 001
0 0001

Don't doubt your methods for finding the address location in a set-associative cache. Your approach is absolutely correct, but first, let's clarify some terminology:
From your question you use the term "index." If I am correct you are using this to refer to the "set" in the set-associative cache? I will use the term "set" from this point forward in place of "index" to avoid confusion since it is more explicit with regard to the type of cache in question.

Your Question. . .
You asked about:

Something that involves a division or modulo of the address?

The Short Answer Is. . .
. . .yes! However, just not with set-associative cache. Modulo division is used when attempting to find a block to which a memory address may be mapped using a Direct Mapped Cache scheme. Subdividing the cache blocks into sets that map to a main memory location based on a portion of its address removes the necessity to obtain a cache location via modulo division.
The Long Answer. . .
Direct mapping involves the process where block X of main memory is mapped to block Y of cache memory, mod N, where N is the number of blocks in cache.[1]
Example:
Provided you are given a cache memory consisting of four blocks and a main memory consisting of eight blocks, the direct mapping scheme will be as follows:

CacheBlocks
Mapping
Main MemoryBlocks
MappingFormula

CB 0
MM 0MM 4
MM 0
MM 0 % 4 = CB 0

CB 1
MM 1MM 5
MM 1
MM 1 % 4 = CB 1

CB 2
MM 2MM 6
MM 2
MM 2 % 4 = CB 2

CB 3
MM 3MM 7
MM 3
MM 3 % 4 = CB 3

MM 4
MM 4 % 4 = CB 0

MM 5
MM 5 % 4 = CB 1

MM 6
MM 6 % 4 = CB 2

MM 7
MM 7 % 4 = CB 3

The Difference
Direct Mapped Cache does not require any searching and is therefore less expensive. However, main memory is constantly being swapped in and out of cache. In the above example, you can see that either block of cache may only hold one of two blocks of main memory at a time. Imagine the scenario where CB 0 is polled for MM 0 but is currently holding MM 4. The CPU would need to expunge MM 4 and bring in MM 0. If the next read/store cycle required MM 4, the process would occur again leading to cache thrashing.[1]
In an ideal world we would use Fully Associative Cache, wherein each block of main memory has its own location in cache and does not have to share with any other addresses. The best way of implementing this type of cache is to have each memory address assigned to any free location at random. However, this requires additional structures within the CPU that search every cache location in parallel.[1] Not only does this translate into a higher monetary expense for the additional hardware structures, it also comes with a look-up cost by having to search each cache block for a hit.
The answer is to strike a happy medium by using Set-associative Cache that combines advantages of the two other types. Each main memory block may be assigned to a specific set location similar to direct mapping, but the exact block in cache will differ based upon the next free block within the set similar to Fully Associative Cache.

Links Regarding Different Cache Mapping Schemes
https://www.geeksforgeeks.org/cache-memory-in-computer-organization/
https://en.wikipedia.org/wiki/Cache_placement_policies

[1]Null, L., & Lobur, J. (2015). Ch. 6 Memory: Direct Mapped Cache. In The Essentials of Computer Organization and Architecture (4th ed., pp. 350-365). Burlington, MA: Jones & Bartlett.


How to prove Transitive property of Reducibility with a TM?

The properties that reductions have are:

They preserve language membership (or Yes-instances, or whichever phrasing you prefer).
They are computable.

So then given that you have two reductions $f$, which takes instances of $A$ and produces instances of $B$ such that $x \in A \Leftrightarrow f(x) \in B$, and $g$ which does the same for $B$ and $C$, you need to show:

$x \in A \Leftrightarrow g(f(x)) \in C$.
$f\cdot g$ is computable.

The first should be a fairly straightforward application of basic logic. The second is also easy.

You can't just take $A=HALT_{TM}$ though, as all you would show then is that $HALT_{TM} \leq_{m} C$, whereas your question (appears) to ask for a proof of the transitivity of many-one reductions in general. (As a comparison would showing that $(10^{100} < b) \wedge (b <c) \Rightarrow (10^{100} < c)$ show that $(a < b) \wedge (b <c) \Rightarrow (a < c)$?)


Consider the potential function
$$
\Phi(w_1 \ldots w_n) = \sum_{i=2}^n 2^i 1_{w_i = w_{i-1}}.
$$
Applying one of the rewrite rules always decreases the potential: if we change $abb$ to $bab$ at positions $i,i+1,i+2$, then we lost $2^{i+2}$ and might have gained $2^i$. Since the potential is non-negative, every derivation ends.

Suppose now that the initial word contained an equal number of $a$'s and $b$'s. The same is true for the final word, since the rules don't change the number of $a$'s or $b$'s. It therefore suffices to prove that any word that has $n$ letters $a$ and $n$ letters $b$, and doesn't contain $abb$ or $baa$, has the form $(ab)^n$ or $(ba)^n$. We prove this by induction.

The base cases $n=0,1$ are trivial, so suppose that $n \geq 2$. Assume without loss of generality that the final word ends with $b$. It must have a suffix of the form $ab^k$ (since it contains at least one $a$). Since it contains no $abb$, we must have $k = 1$. Remove the suffix $ab$ and apply induction to deduce that the word is either $(ab)^n$ or $(ba)^{n-1}ab$. The latter case cannot happen since it contains $baa$, and so the word must be $(ab)^n$.

We can slightly strengthen this result by noticing that the rewrite rules never change the final letter of the word. So we reach $(ab)^*$ if the original word terminated with $b$, and reach $(ba)^*$ otherwise.


Distance transform with variable "impedance"

I don't know whether there is a name for the transform you want but it can be computed in time $\tilde{O}(N)$ where $N$ is the number of entries of the matrix, assuming that the weights are non-negative.
Let the dimensions of the input matrices be $n$ and $m$. Call $A$, $W$, and $D$ the matrix with the pixel data, the weights, and the distances in output, respectively. Assume for simplicity that $W[i,j]=0$ whenever $A[i,j]=0$.
Create a directed graph $G = (V,E)$  where $V = \{s\} \cup \{1, \dots, n\} \times \{1, \dots, m\}$ and $E$ contains all edges $(s, (i,j) )$ for which $A[i, j]=0$ and
and edge $( (i,j), (i',j') )$ with weight $W[i',j']$ for each pair of vertices $(i,j)$ and $(i', j')$ that satisfy $|i-i'|+|j-j'|=1$.
The distance $d(i,j)$ from $s$ to $(i,j)$ in $G$ is exactly the distance you are looking for, i.e., $D[i,j] = d(i,j)$.
To compute all values $d(i,j)$ it suffices to run any single-source shortest-path algorithm from $s$ on $G$. Using Dijkstra's algorithm the time required is $O(|E| + |V| \log |V|) = O(N \log N)$.
Faster algorithms might be possible if you have additional assumptions about the weights. For example, if they are bounded by a constant then $O(N)$ time suffices.


General structure of solutions to 3-SAT circuits

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s dichotomy theorem, which was recently extended to arbitrary alphabets.

3SAT has no polymorphisms. NAE-3SAT has only negation as a polymorphism. All other classes of polymorphisms correspond to CSPs solvable in polynomial time. See Allender et al., The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.


Is a partial function Turing-computable?

So, some of the functions you talk about might be technically uncomputable, but the problem can become decidable with trivial modifications.

For example, consider the function taking a natural number to its predecessor. If you define it partially, nothing comes before $0$, and there's no algorithm to solve this, because there isn't a correct answer. The algorithm can't find it because it doesn't exist.

But, if you make a choice, and say that the predecessor of $0$ is $0$, or some special character, now you have a total function, from which you can extract your partial one.

I suspect most of the "real world" partial functions you talk about fall into this category. You just define a special "fail" output for any inputs where there's no defined output.

What the definition of computability is talking about really is whether a Turing Machine halts for all inputs. If it halts on all inputs, the result is whatever is on the tape, so it's considered total. If it doesn't, then it's partial.

For your specific questions:

Yes, termination is absolutely part of the definition of computability. Otherwise, everything is decidable: I make a Turing machine that runs forever, and since it doesn't ever give a wrong answer, I've "solved" the problem. Given this, solving a problem without termination is pretty meaningless.

A function is computable if there exists a Turing Machine computing it which halts on all inputs.

How does non-termination fit in? Basically, we don't allow non-termination, because of the problem I mentioned above. There is a special class of problems, called "recursively-enumerable" or "semi-decidable" decision (yes/no) problems, where the Turing Machine halts on all "YES"-valued inputs, but might not halt on all NO-valued inputs.

Another thing to watch here is your quantifiers. A problem is decidable if there exists a Turing Machine that solves it and always halts. I can make a Turing Machine solving addition that sometimes loops forever, but that doesn't mean that addition is undecidable, because there exists another machine that solves it and always halts.


Here is a formal or informal proof, depending on how the probability distribution is defined.

Let $S_k=\left\{vvs\in\{0,1\}^\infty\mid v\in\{0,1\}^k,\ s\in\{0,1\}^\infty \right\}$, the sequences of infinite binary digits that repeat their initial $k$ binary digits immediately once (or more), where $k\ge1$.

$$\begin{align}
\text{Prob[$S_k$]}
&\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w\text{ can be extended to an element in } S_k\right\}\\
&\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w=vv \text{ for some } k \text{ binary digits } v\right\}\\
&=\frac1{2^{2k}}\#\left\{v\in\{0,1\}^{k}\right\}\\
&=\frac1{2^{2k}}2^{k}\\
&=\frac1{2^k}\,.
\end{align}$$

Given an integer $i\ge1$ and a prefix-repetitive toss $S$, we know $S$ must be contained in $S_k$ for some $k\ge i$ since there infinitely many initial segments $v$ such that $vv$ is a prefix of S. Hence,
$$\begin{align}
\text{Prob[$S$ is prefix-repetitive]}
&\le\sum_{k=i}^\infty\text{Prob[$S_k$]}\\
&\le\sum_{k=i}^\infty\frac1{2^{k}}\\
&=\frac1{2^{i-1}}\,.\\
\end{align}$$

Let $i$ go to infinity, we see that
$$\text{Prob[$S$ is prefix-repetitive]} = 0\,.$$

Here are three related exercises.

Exercise 1. Show that the number of all prefix-repetitive tosses are more than countably infinite. Hence the approach mentioned in the question is unlikely to succeed.

Exercise 2. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of an unfair coin, then Prob[S is prefix-repetitive] = 0.

Exercise 3. An infinite binary sequence $S \in \{0, 1\}^\infty$ is prefix-palindrome if there are infinitely many strings $v \in \{0, 1\}^*$ such that $vv^R$ is a prefix of $S$, where $v^R$ is the reverse of $v$. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of a coin, then Prob[S is prefix-palindrome] = 0.


This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP.


You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.

Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it effectively is multiplication by a constant.
Now at every node you have at most $m$ sorted elements, so you can perform binary search giving $log_2(m)$, so the proper complexity is $O(log(N) * log(m))$.
Since $m << N$, and what is more important, is that it does not depend on $N$, so it should not be mixed, or it might be given explicitly (with $m$ not $N$ or appearing $n$).


Maximize area of light with 4 light sources on a diagram of a room

This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions:

Global optimization - a branch of numerical analysis, that deals with various iterative algorithms, able to find an argument of the optimized function, giving its minimum or maximum value over all the function domain. Sometimes the global optimization problem is solved as a sequence of local optimizations (with random starting points), however in general case there are no guarantee that the optimal solution will be found by this method. Please see this paper, where authors apply the Gradient descent method to maximize the area of the region, visible to the observer in a simple polygon (without holes).

Visibility polygon for a point $p$ in the plane configuration with possible boundary and obstacles is the polygonal region $V(p)$ of all points of the plane visible from the p. You'll need to compute visibility polygons many times for different points, so it makes sense to pre-process the original polygon (together with its holes) to make this computation faster. Please see this paper, where authors do exactly that - their approach needs $O(n^3log(n))$ pre-processing time, and it allows to compute the visibility polygon with $k$ vertices in $O((1+min(h,k))log(n)+k)$ time, where $h$ is the number of holes. The visibility polygon for four points will be a union of four visibility polygons (and this union can have holes) - so you'll need to compute this union. Please see Boolean operation on polygons as a starting point for your research as well.

Optimization problems on real numbers are intrinsically inexact and their solutions are approximations - the question is how close your solution should be to the optimal one. The gradient descent method might be enough in your case, where the bounding polygon is simply a rectangle, and holes also have simple shape.


Prime checking and factorization with just bit cheking

Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned).  This can be done for all $d$.  However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, one-by-one, is far too inefficient.

In other words, this approach to factorization is not likely to be useful, no matter how many tricks you accumulate.


Does cooperative scheduling suspend processes when they perform an  I/O operation?

In a truly "cooperative" setting, and if there was no hardware protection, a process could certainly block on I/O and not relinquish control until the I/O was done (or never relinquish control at all). For example, Windows 3.1 was this way: if a single user process wanted to take over the entire computer, and prevent anything else from running, it could.

But on a system with multitasking you expect the system API I/O commands to relinquish control of the processor when they are called. So when a running process blocks on I/O, assuming that the process uses the normal system APIs, other processes will be allowed to run until the I/O is complete, and eventually the original process will resume once the I/O is done. In other words, calling a blocking I/O function is one way that a process on a cooperative system can voluntarily suspend itself.


minimum spanning tree and minimum heavyweight spanning tree

Hints:

Scaling.
Almost every graph would answer this.


The Dense Subgraph Problem (thanks @PalGD) is a special case of the above problem--with no node weights and unit edge weights. See the solutions for the dense subgraph problem here. These solutions (LP and 2-approximation Greedy) easily generalize to the above problem (generalizing LP requires a bit of understanding/effort, but generalizing Greedy is trivial).


It is not easy to come by books that consider the denotational semantics of $\lambda$-calculus. One possibility is:

Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi

Type-theoretic accounts are easier to get hold of:

Bob Harper, Practical Foundations of Programming Languages (there is also a printed version).
Benjamin Pierce, Types and Programming Languages.
Frank Pfenning's course on Computation and Deduction, I think he also published a book with the same title.


Defining the goal function in an optimization problem

If you know the minimum and maximum values for $a,b,c$, you can use a weighted linear combination.  e.g., if $a,b,c \in [0,1000]$ (they are all between 0 and 1000), then you can use the objective function

$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$

Minimizing this function is guaranteed to be optimal under your partial order.

Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic.  It's not guaranteed to give optimal results, but it might be good enough in your particular application.


Physical Meaning Behind Matrix Factorization

The idea in matrix factorization is to find the latent variables which connect the input and the output. Suppose that we are interested in a movie recommendation system, and that movies "live" on a one-dimensional axis, having romantic comedies in one end, and action movies in the other. Each "input" and "output" move can be rated in this scale (say $1$ to $-1$). Given the input movies, we can estimate a person's location $p$ on the axis (say a point in $[-1,1]$) by taking the inner product between the movies they saw and their "ratings" $r_i$, i.e. $p \approx \frac{1}{n} \sum_{i=1}^n r_i$, where $1,\ldots,n$ are the movies seen by the person. Given the location, we can estimate how much that person will like other movies: movie $t$ will be liked by an amount proportional to $pr_t$ (this is just a simplistic linear model).

In this example, the recommendation matrix can be decomposed as an outer product $A_{it} = r_i r_t$. More generally, the situation could depend on several latent variables, and this is the general situation described by matrix factorization. The number of latent variables is the "middle" dimension in the factorization. If you have found a good factorization with only a few variables, then you have a succinct explanation of your data that could have predictive power.


Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2?

In the realm of classical physics (where you don't need quantum mechanics to predict what is going on), we have no known method of computation that will be significantly faster than a standard classical computer.  Indeed, it is a standard belief that none exists.
The one exception is quantum mechanics.  Quantum computers are believed to be able to solve some problems significantly faster than classical computers -- though only a few special problems; for most, they offer no benefit (and quantum computers are not expected to offer any significant speedup for NP-complete problems).  It is a standard belief that no physical process that can be described by quantum mechanics offers any significant speedup over a quantum computer (in particular, a quantum computer is universal and can simulate any quantum mechanical process).
In short, the answer to your question is "no, there is no known physical process that holds any promise for solving NP-hard problems in polynomial time".


Iterative Byzantine consensus in directed graphs with unbounded malicious nodes

As you are probably well aware, it is provably impossible to reach consensus if a majority of the peers are faulty, malicious, or dishonest, if we assume they are all fully connected (as is typically the assumption for distributed systems).

If you are imagining that for some reason honest peers are better-connected than faulty/malicious peers, well, there are two problems with that model:

The first problem is that the model is not realistic.  In practice, faculty/malicious peers are typically just as well-connected as honest ones.  In the case of unintended software faults, there is no reason to expect that connectivity will be at all correlated to software failure rates.  In the case of malice (e.g., peers that are compromised or dishonest), well, attackers can typically arrange to be as well-connected as the honest peers, and can often arrange to be even better-connected.
The second reason is that if we really did have such a separation, the problem would become trivial.  For instance, we could just pick a threshold and ignore all peers whose connectivity is below that threshold.  If this ensures that a 2/3 majority of the remaining peers are honest and non-faulty, then this reduces to the standard Byzantine consensus problem.

But ultimately I think it is the first problem that is the big one.  It would only make sense to even think about such a setting if we had some sample application where there is evidence that your assumption is valid.  Lacking that, there is not a clear reason to study such a model.

The web of trust doesn't actually seem to meet your assumptions, unless you are very careful about how you define them.  An attacker can create one dishonest node $x$ (that is connected to a few honest peers), and then create lots of additional dishonest nodes $y_1,y_2,\dots,y_n$ and have $x$ endorse all of the $y_i$'s.  The $y_i$'s can also endorse lots of honest nodes.  Now, at least by some measures, the $y_i$'s are well-connected.  There is also the risk of Sybil attacks, where the attacker creates many fake identities ("Sybils") and gets them connected to many honest nodes.

In the cryptographic world, you could look at the research directions under the catch-phrases "reputation systems" and "trust metrics".  Some of them are designed to estimate the amount of trust one can have in a node, based upon its connectivity and the endorsements that nodes make in each other.  However, academic research hasn't had a ton of impact in practice, because it is hard to make them work well in practice, and because Sybil attacks are hard to stop.