Is there a language that can be Turing-reduced from all languages?

I assume you're asking if there's a language $\Omega$ such that, for all $L\subseteq\{0,1\}^*$, $L\leq_T\Omega$.  In that case, the answer is “no.”

For any language $\Omega$, the languages that Turing-reduce to $\Omega$ are those that can be decided by a Turing machine with an oracle for $\Omega$. For brevity, I'll say “$\Omega$-Turing machines” instead of “Turing machines with an oracle for $\Omega$.” $\Omega$-Turing machines are at least as powerful as ordinary Turing machines (exactly as powerful, if $\Omega$ is decidable; strictly more powerful of it isn't).

The same argument that shows the undecidability of the ordinary Turing machine halting problem also shows that any machine model that is at least as powerful as Turing machines can't decide its own halting problem.  So, in particular, no $\Omega$-Turing machine can decide the halting problem for $\Omega$-Turing machines.  In other words, for any language $\Omega$, the halting problem for $\Omega$-Turing machines isn't Turing-reducible to $\Omega$.

This means that there's no “hardest language” (or class of languages) to which all languages are Turing-reducible. This is related to the concept of Turing degrees, which form an infinite hierarchy of ever more difficult languages: start with the decidable languages, then the languages decided by Turing machines with an oracle for the halting problem, and then iterate by making each subsequent level be the languages decided by Turing machines with an oracle for the halting problem corresponding to the previous level.


Binary representation of 129 when using 8bits for two's complement?

The range of integers representable in 8 bits using two's complement is –128 to +127.

If instead the numbers are unsigned, then the range becomes 0 to 255.


We can prove that if $f(n)$ is $O(\log{n})$ and $g(m)$ is $O(m)$ then $f(n)g(m)$ is $O(m \log{n})$. To say that $mO(\log{n}) = O(m \log{n}))$ is an abuse of notation.

See Wikipedia for similar properties of big O: http://en.wikipedia.org/wiki/Big_O_notation#Properties.


Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

The expression $\lceil \log_2 n \rceil - 1$ for the height of a $n$-element heap is wrong.
For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc...
In general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log_2 2^i \rceil - 1 = i-1$.
The equality $\lceil \log_2n \rceil -1=\lfloor \log_2 n\rfloor$ is also wrong, as it can be seen by picking $n=2^i$ for any $i \in \mathbb{N}^+$.


Nilsson's sequence score for 8-puzzle problem in A* algorithm

See if this explanation can help you:

Current pos:   Goal:
*AC            ABC
HBD            H*D
GFE            GFE

How to calculate the score:

Center

B in the center -> 1

Distances (manhattan distance)

A must move LEFT -> 1
B must move UP   -> 1
sum of distances = 2

Successors (clockwise)

current: ACDEFGH*  (skip B because it is in the center)
goal:    ABCDEFGH

the [tile,tile clockwise to it] pairs  are:
[A,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,*]
([*,A] is not considered)

the "goal" pairs are:
[A,B], [B,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,A]

There are 2 pairs that do not match the goal pairs:

[A,C], [H,*]

So the final score is: $distances + 3*(center + 2*successors) = 2 + 3 * (1 + 2*2) = 17$


Not able to devise a concrete solution for the given graph query

Your problem is very similar to interval scheduling, and it seems it can be solved similarly using a greedy approach. Note first that you can solve each row separately. For each row, you scan the row from left to right. Assign each policeman to the leftmost thief that he can capture and isn't already taken (if any). Intuitively, this should work, and you can try proving that it does using the standard proof method of comparing the greedy solution to an optimal one.


I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here.

In most programming languages, you can simulate a Turing machine by:

simulating the finite automaton with a program that uses a finite amount of memory;
simulating the tape with a pair of linked lists of integers, representing the content of the tape before and after the current position. Moving the pointer means transferring the head of one of the lists onto the other list.

A concrete implementation running on a computer would run out of memory if the tape got too long, but an ideal implementation could execute the Turing machine program faithfully. This can be done with pen and paper, or by buying a computer with more memory, and a compiler targeting an architecture with more bits per word and so on if the program ever runs out of memory.

This doesn't work in C because it's impossible to have a linked list that can grow forever: there's always some limit on the number of nodes.

To explain why, I first need to explain what a C implementation is. C is actually a family of programming languages. The ISO C standard (more precisely, a specific version of this standard) defines (with the level of formality that English allows) the syntax and semantics a family of programming languages. C has a lot of undefined behavior and implementation-defined behavior. An “implementation” of C codifies all the implementation-defined behavior (the list of things to codify is in appendix J for C99). Each implementation of C is a separate programming language. Note that the meaning of the word “implementation” is a bit peculiar: what it really means is a language variant, there can be multiple different compiler programs that implement the same language variant.

In a given implementation of C, a byte has $2^{\texttt{CHAR_BIT}}$ possible values. All data can represented as an array of bytes: a type t has at most
$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$ possible values. This number varies in different implementations of C, but for a given implementation of C, it's a constant.

In particular, pointers can only take at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ values. This means that there is a finite maximum number of addressable objects.

The values of CHAR_BIT and sizeof(void*) are observable, so if you run out of memory, you can't just resume running your program with larger values for those parameters. You would be running the program under a different programming language — a different C implementation.

If programs in a language can only have a bounded number of states, then the programming language is no more expressive than finite automata. The fragment of C that's restricted to addressable storage only allows at most $n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ program states where $n$ is the size of the abstract syntax tree of the program (representing the state of the control flow), therefore this program can be simulated by a finite automaton with that many states. If C is more expressive, it has to be through the use of other features.

C does not directly impose a maximum recursion depth. An implementation is allowed to have a maximum, but it's also allowed not to have one. But how do we communicate between a function call and its parent? Arguments are no good if they're addressable, because that would indirectly limit the depth of recursion: if you have a function int f(int x) { … f(…) …} then all the occurrences of x on active frames of f have their own address and so the number of nested calls is bounded by the number of possible addresses for x.

A C program can use non-addressable storage in the form of register variables. “Normal” implementations can only have a small, finite number of variables that don't have an address, but in theory an implementation could allow an unbounded amount of register storage. In such an implementation, you can make an unbounded amount of recursive calls to a function, as long as its argument are register. But since the arguments are register, you can't make a pointer to them, and so you need to copy their data around explicitly: you can only pass around a finite amount of data, not an arbitrary-sized data structure that's made of pointers.

With unbounded recursion depth, and the restriction that a function can only get data from its direct caller (register arguments) and return data to its direct caller (the function return value), you get the power of deterministic pushdown automata.

I can't find a way to go further.

(Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)


Can CYK Parsing algorithm generate the parsing tree in O(n^3)?

It depends what you mean by build a parse tree.

You can build a parse forest in $O(n^3)$ time and space. The forest represents all parse trees, even an infinite number of parse trees, because it is a graph, not a tree. From a parse forest, it is possible to produce a single parse tree in time linear to the size of the forest, and it is possible to iterate through all possible parses.

So if you either consider that "build a parse tree" means "find one of the possible parses" or if you consider that it means "build a datastructure which represents all possible parses", then you can certainly do that with a CYK grammar in $O(n^3)$.

If, on the other hand, you intend "build a parse tree" to mean "build all parse trees for a sentence", then it is not limited to exponential time; it is easy to write a grammar with an infinite number of possible parses for certain sentences.


Edit distance for huge strings with bounds

You can use the usual dynamic programming algorithm. Instead of computing the edit distance between all prefixes of the input strings, compute only the edit distance between prefixes whose length is at most 100 apart. This reduces the number of entries to compute from $10^{14}$ to roughly $2\cdot 10^9$, which is feasible.


Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument.
You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. If the strings are random, checking just the first symbol will weed out all but a fraction of the strings (like the program you show does, bailing out early).
If you assume random strings over an alphabet of $m$ symbols, they will agree with the first $k$ symbols of your needle (which you are looking for in the haystack) $1/m^k$ of the times. The number of checks to do for each string will then be on average:
$\begin{align*}
   c
     &= 1 + \sum_{2 \le k \le d} \frac{k}{m^k}
\end{align*}$
(you do $1$ check regardless, then $k$ more checks if $k$ symbols match).
To compute this sum, note that:
$\begin{align*}
  f(z)
    &= \sum_{0 \le k \le d} \frac{z^k}{m^k} \\
    &= \frac{1 - z^{k + 1} / m^{k + 1}}{1 - z / m} \\
    &= \frac{m^{k + 1} - z^{k + 1}}{m^{k + 1} - z m^k}  \\
  f'(z)
    &= \sum_{0 \le k \le d} \frac{k z^{k - 1}}{m^k} \\
  f'(1)
    &= \sum_{0 \le k \le d} \frac{k}{m^k} \\
    &= \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \\
  c
    &= 1  + f'(1) \\
    &= 1 + \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2}
\end{align*}$
Thus the number of symbol comparisons for one string is approximately $(m + 1) / m$, as you'd suspect.


Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

One very simple approach is to use a linear model.  Let $I(x,y)$ be the pixel intensity of the pixel at coordinates $(x,y)$.  We can fit to a linear model:

$$I(x,y) = \alpha x + \beta y + \gamma,$$

where $\alpha,\beta,\gamma$ are parameters to be determined.  If we are given the pixel intensity at each corner of the triangle, then we know the value of $I(x,y)$ for each corner point $(x,y)$.  Since a triangle has 3 corners, this gives us 3 linear equations in 3 unknowns.  We can solve this system of linear equations to find $\alpha,\beta,\gamma$, and then use this linear model to fill in the value of all other points.

In particular, if the $i$th corner is at $(x_i,y_i)$ and has pixel intensity (value) $v_i$, then we get a system of three equations:

$$\begin{align*}
I(x_1,y_1) &= v_1\\
I(x_2,y_2) &= v_2\\
I(x_3,y_3) &= v_3
\end{align*}$$

Expanding the linear model, this becomes

$$\begin{align*}
\alpha x_1 + \beta y_1 + \gamma &= v_1\\
\alpha x_2 + \beta y_2 + \gamma &= v_2\\
\alpha x_3 + \beta y_3 + \gamma &= v_3
\end{align*}$$

Here we have three unknowns ($\alpha,\beta,\gamma$) and the rest are known constants.  So, we can solve this system of linear equations for $\alpha,\beta,\gamma$.  This involves inverting a $3 \times 3$ matrix and then multiplying it by a $3$-vector, so it should be relatively efficient.

Once you have derived the parameters $\alpha,\beta,\gamma$, you can now evaluate the value $I(x,y)$ at any other point $(x,y)$ in the triangle (or on its interior).  This lets you interpolate the value at each fill-in point.

The approach I described above works for black-and-white images.  If you have a color image, you can interpolate independently for each of the 3 channels (R, G, and B; you might get better results if you work in a transformed color space, e.g., HSV, CIELAB, CIECAM02).

I recommend you take a look at barycentric coordinates, as they simplify the formulas for interpolation in a triangular mesh.

If you are familiar with interpolation for image processing, bilinear interpolation is a slight generalization of this approach, where you add a $\delta xy$ term to the linear model.  However, bilinear interpolation isn't applicable here, because it requires 4 points: 3 points isn't enough.

It's possible to come up with more sophisticated interpolation models.  For instance, you could fit a linear model to more than 3 points (e.g., taking the corner points of all adjacent triangles as well), and use ordinary least squares linear regression to find a best-fit linear model, weighting the corners of the adjacent triangles lower than the corners of the target triangle.  You could also build generalizations of bicubic interpolation, etc.

More generally, I recommend that you do a bit of research on "tetrahedral interpolation", as I believe that is the catch-phrase for the kind of problem you are asking about (or the generalization of it to 3 dimensions).


Why isn't every monotonic grammar context sensitive free?

If you're asking why the grammar with the rule $AB \to BA$ is not context-sensitive, you can find an explanation here.

The short answer is that it depends on the definition, but with one standard definition, the rule $AB \to BA$ simply doesn't satisfy the criterion for a rule to be allowable in a context-sensitive grammar.


why does LSPACE(log space) complexity class exist but not logtime?

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting.
What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform circuits. A related complexity class is ALOGTIME, which is the uniform version of NC¹. Buss famously proved that the formula evaluation problem is ALOGTIME-complete. For comparison, the circuit evaluation problem is P-complete.
Algorithms running in $o(n)$ time on random-access machines are known as sublinear time algorithms. Such algorithms also abound in the area of data structures.


I'll try to answer my own question. The solution is an application of matrix transformations.

This lecture tries to explain some of the maths.

https://www.khanacademy.org/math/precalculus/precalc-matrices/matrices-as-transformations/v/transforming-position-vector

I think what I need to do is apply both a translation and scale matrix to each vertex in the "virtual" coordinate system to get them into the "physical" coordinate system.

Still trying to get my head around exactly how to do that.


What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$


Regarding your first question, the Core i3, Core i5 and Core i7 share the same instruction set, apart for a few marginal instructions. In particular, there is backward compatibility, and so code that works for Core i3 would also work for Core i5 and Core i7 (unless it uses some undocumented behaviours, or specifically tests for the processor version). However, to get superior performance, optimizers need to know the exact target processor, and special instructions should be utilized. This can be handled in at least two ways: (1) crucial functions could have several versions, depending on the processor (either completely different versions or just different optimizing parameters), (2) libraries are used which implement the previous approach.

Regarding your second question, the operating system is usually relied on for handling files, so yes, even an assembler needs to interact with the operating system.


Mutation considered harmful, but is there a safe set

Ask not how to get rid of the evil mutable state, but rather how to tame it by provding structured and predictable ways of using it.

Just because goto is harmful you wouldn't remove all flow control from a language, right? You'd rather think of ways of using control flow in a structured way, and then you would invent the while loops.

There is not single best solution on how to structure and control mutable state, but there are some good ones. For example, you can have the programmer describe quite explicitly which part of the program can do what and who "owns" stateful parts of memory. The compiler will then check for compliance. An example of this sort of thing is Rust.

There is a more general phenomenon which encompasses mutable state, namely computational effects. Mutable state is tricky to get right, but so is concurrency, I/O can be tricky depending on what you do, etc. These are all computational effects, and we can ask whether there are general and structured ways of dealing with them.

The most popular general way of controlling computational effects is to use monads. These are programming language constructs that allow you to express presence of certain computational effects (could be mutable state) with typing information. This way the programmer will be able to see that a certain piece of code may cause effects, and the compiler will complain if things don't fit.

Another method that has caught some interest lately is algebraic effects and handlers. It's less general than monads, but it also organizes your code in a way that is often a bit more flexible than monads (The people of the Internet want to know this too.) Briefly, handlers are a generalization of the familiar exception handlers that allow you to intercept any computational effect and do something with it. I like to explain their usefulness with the slogan
$$\frac{\mathtt{handlers}}{\mathtt{callcc}} =
\frac{\mathtt{while}}{\mathtt{goto}}.
$$
That is, just like while is the structured way to do goto, handlers are the structured way to do non-local flow control in a functional setting (callcc has been called "the goto of functional programming").


Data structures as algorithms themselves

Yes, a data structure can be thought of as an algorithm.  A data structure is a collection of state together with one or more algorithms that operate on that state.

A data structure can be thought of as a tuple $(s,f_1,f_2,\dots,f_k)$ where $s$ is its state, and each $f_i$ is an operation that can be performed on the data structure; the operation $f_i$ can read the state $s$ and its input parameters, and possibly modifies $s$ and possibly returns a new value.  Alternatively, from an object-oriented viewpoint, you can think of a data structure as an object; $s$ is the state of the object, and $f_1,\dots,f_k$ are the methods that can be invoked on the object.  Normally, $f_1,\dots,f_k$ are described as algorithms that operate on $s$ and their inputs.  This lets you use the language and concepts of algorithms to analyze various data structures.

I'm not sure there is a formal specification of what counts as a data structure, but this seems to get about close as I've seen.

You might be interested in the notion of abstract data type (ADT) from programming languages.  You can think of a data structure as an ADT, or more carefully, you can think of an ADT as the specification and the data structure code as a particular implementation of that ADT.  When people talk about data structures informally, they don't always distinguish between specification vs implementation; the term ADT helps make that distinction more precise.

I don't know if people normally try to formally define what we mean by "data structure"; it's a loose term that is more useful to illustrate a particular type of concept in computer science.  If I wanted to make it as precise as possible, the notion of an ADT would probably be the first formalization I'd consider.  An ADT is like an interface specification, and a specific data structure is like a particular way of implementing that specification.


Is there a general-case sweep line algorithm for line segment intersection?

Usually these algorithms can be adapted to the general case, but the details are messy and hard to get right. Another option is perturbation:

Move each line segment by some small amount in all directions.
Extend the segments slightly on both ends.

If you choose your parameters carefully (i.e., small enough), you are likely to have all the same intersections, but you will be in general position with probability 1. How small is small depends on your input, and this is a limitation of this approach, but in practice you can probably heuristically choose a small enough perturbation.

Implementing this using "virtual infinitesimals", you can come up with a version of Bentley–Ottman that doesn't require general position. The idea is to do the perturbation by some infinitesimal amount, and record the results formally (e.g. $1$ goes to $1+\epsilon$, where $\epsilon$ is an infinitesimal). When running the algorithm, you will need to compare values which involve these infinitesimals, which you can do formally (for example, $1+\epsilon < 1 + 2\epsilon$).


Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same

In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}[u]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}[u]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$.

The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's algorithm. As shown in the proof for the standard Dijkstra's algorithm, it also holds that for each visited node $v$, $\mathtt{dist}[v]$ is the shortest distance from source to $v$.

Now consider a node $v$. Let $P$ be a shortest path from source to $v$. Suppose $\mathtt{dist}[v]$ is first updated through $u$ (i.e., it is updated to $\mathtt{dist}[u]+w(u)$), and when $\mathtt{dist}[v]$ is first updated, $x$ is the first unvisited node on $P$, then $\mathtt{dist}[x]+w(x)\le w(P)\le \mathtt{dist}[u]+w(u)$, where $w(P)$ is the shortest distance from source to $v$. Also note at this time $u$ is chosen instead of $x$, we have
$\mathtt{dist}[u]+w(u)\le \mathtt{dist}[x]+w(x)$, hence $\mathtt{dist}[x]+w(x)= w(P)= \mathtt{dist}[u]+w(u)$, i.e., $\mathtt{dist}[v]$ is first updated to the shortest distance from source to $v$, and it will not be updated any more.


Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?

Your polynomial is primitive, which means that the order of $x$ modulo your polynomial is exactly $2^{15}-1$. In particular, $x^a \not\equiv 1$ modulo your polynomial for all $1 \leq a \leq 2^{15}-2$, which means that your polynomial doesn't divide $x^a-1$ for this range of $a$.

(This also means that your polynomial should divide $x^{2^{15}-1}-1$, in contrast to what the question claims.)


Karp hardness of an equidistant set in digraph

This is $NP$-complete by reducing from the undirected version which was proven hard by Yuval's reduction.

For every pair of vertices $u$, $v$ in the undirected graph, if $dist(u,v)=2$ then we create two new vertices $x_{uv}$, $x_{vu}$ and add 4 arcs $(u,x_{uv})$, $(x_{uv},v)$, $(v,x_{vu})$, $(x_{vu},u)$. This guarantees that $dist(u,v)=dist(v,u)=2$ in our digraph.

Finally, add two vertices $src$ with outgoing arcs to all original vertices and $dst$ with incoming arcs from all original vertices. Add $x_{src,dst}$ with two arcs similarly. Note that we do not have the opposite direction of $x_{dst,src}$.

Now set $k=m+1$.

It is necessary to manipulate the case of having some $x_{uv}$ vertex in an equidistant set. But, this is impossible (as long as $k=m+1>4$ like in Yuval's reduction). To see this, suppose that $x_{uv}$ is included in some equidistant set. Clearly, from $x_{uv}$ going out, in one step, you must end at $v$. And, to reach $x_{uv}$ in one step, you must go from $u$. So, there cannot be any vertex within distance 2 (in both directions) of $x_{uv}$, except for $x_{vu}$. So, our equidistant set can be of size only $2<m$.That means we cannot have any $x_{uv}$ vertex in our set. If instead we have $x_{src,dst}$ in our set, we can easily see that there cannot be any other $x_{uv}$ in our set. In all cases, we still have at least $m+1-1=m$-equidistant set without any $x_{uv}$ vertices.

Conversely, if we have an $m$-equidistant set in the undirected graph, then we can add $x_{src,dst}$ to this set to form an $m+1$-equidistant set.


Big number of false positives in binary classification

It's hard to know, from just the information you've given us.  It could be any number of things: overfitting, insufficient training data, class imbalance, or something else.  The first step is probably to figure out the source of the problem, then you can explore the solutions.

There are standard diagnostics to check for overfitting (cross-validation, comparing accuracy on the validation set to accuracy on the training set, etc.). I'd suggest you use them to diagnose whether the network seems to be overfitting.  There are many ways to combat overfitting: regularization, early-stop training, dropout, etc.

There are also ways to check if the problem is that you just don't have enough training data.  For instance, you can take different-size subsets of your training set (10K, 20K, 30K, 40K, 50K) and plot how accuracy depends on the size of the training set.  If accuracy seems to be gradually improving as training set size increases and doesn't appear to have reached a plateau yet, that's a suggestion that obtaining more training data might be useful.

Finally, class imbalance might be a factor.  When you have 5 times as many non-food instances as food instances, that's call class imbalance.  There's lots written on that subject and many techniques (undersampling the minority class, oversampling the majority class, using class weights, adjusting the threshold for classification, and more).  I suggest you do some reading about that topic.  It's not necessarily true that you need to train on a training set with balanced classes; that's one strategy, but it's not the only one, and it may not be optimal.

Hopefully this will help you narrow down what might be going on and then ask a more focused question.


Original literature on adversary argument

The oldest literature can be traced back to Andrew Yao's min-max principle, which inturns has its elder root from von Neumann's.

History of game theory is not continuous in time. At least, there was some rise and then fall in the intensity of mathematicians' attention to this theory.


Hint for (1): consider a different type of value, $\mathrm{value}(s) = 1$ if $s$ ends with $z$, and $\mathrm{value}(s) = 0$ otherwise. Define the language $L$ as in your case, and consider $L \cap x^* z y^* z$.

Hint for (2): consider the language $L_\alpha = \{xy : \mathrm{value}(x) = \mathrm{value}(y) = \alpha \}$. What is the relation between $L_\alpha$ and $M_\alpha = \{ x : \mathrm{value}(x) = \alpha \}$? Is $M_\alpha$ regular?


I have no clue what these various types are. You might want to ask the Wikipedia author who added these types, Wleizero. I can add to the list other types, such as double greedy algorithms, randomized greedy algorithms, reverse delete algorithms, and probably many more.

There are several frameworks for greedy algorithms which might interest you, for example priority algorithms studied by Allan Borodin and his coauthors. However, a laundry list of algorithms does not make a classification. I suggest you just ignore this list of types.


Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

A quick result is that $PSPACE=\Sigma_2$.
First show that $PSPACE\subseteq P/Poly$, and as a result $PSPACE\subseteq \Sigma_2$ (If finding an entry of a computation table is in P/Poly, then it is also in $\Sigma_2$, since we can guess a circuit and locally verify its correctness as described here).
To see why having a PSPACE-complete sparse language $S$ puts PSPACE in P/poly, given $L\in PSPACE$, let $f$ be a reduction from $L$ to $S$. Note that if $|f(x)|$ depends only on $|x|$, then $L\in P/Poly$ since we can concatenate the circuits for $f$ and for $S$ (which is in P/Poly due to being sparse). To overcome the fact that $f$ might vary in the output's length for same input size, note that on length $n$ inputs $f$ can produce output of length $\le n^c$, so given $x$ we can take as a hint all $|x|^c$ circuits for $S$ on input sizes $0,1,...,|x|^c$. Among these circuits, we have the "right" circuit which is able to determine the membership of $f(x)$ to $S$.


Operations under which the class of undecidable languages isn't closed

Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$, $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$, then $AB=\{0,1\}^{\ast}$ (why?)


Why are finite automata defined as ordered $n-tuples$ and not as sets?

A DFA fundamentally has five components, and those components aren't interchangeable. You can't freely swap the set of final states and the set of input symbols, for example, without just making a mess of everything.

The standard representation just says "those five things make a DFA". In other words, a DFA is just those five things in sequence, nothing more or less. The order matters, not because the input symbols have to come before final states, but because you need to know which is which and not get that wrong. Without an order, you wouldn't know that.

But, if you wanted to represent a DFA as some sort of dictionary instead, like $\{``Q":\{\ldots\}, ``\Sigma":\{\ldots\},\ldots\}$, that would be perfectly fine. Or a list of pairs, or really any way you like that makes it clear what's what.


Finding the total capacity of two communication channels

If the channels are not coupled (i.e., their effect on the input is independent of each other) then their combined capacity is the sum of their individual capacities. See for example Wyner, Capacity of Product of Channels, who also considers the converse.


This is similar to what is known as counting sort. Whether your method is more efficient than other methods depends on the model of computation, which you haven't specified. For example, what if the dynamic range of the numbers is really large, say they are integers from $0$ to $2^{100}$? You could use some adaptive approach ("scanning" from top to bottom, stopping each time a number is reached), but it really depends on what your computer is allowed to do, and in practice you probably won't be able to pull it off. Counting sort is a conventional algorithm which uses a very similar idea in situations in which the dynamic range is small, in which case the algorithm is highly effective.


NP completeness of closest vector problem

As far as I know, it is not known that the shortest vector problem is NP-hard for any $L^p$ norm other that $L^\infty$. It is known that the shortest vector problem is "NP-hard under randomized reductions" for all $L^p$, a result first proved by Ajtai. See for example Miccanccio's paper and the results he references. Since then better inapproximability results have been obtained, but as far as I can tell nobody could prove an unconditional NP-hardness result.


Algorithm for computing partitions of a set of n elements into subsets of size m

Two possible  possible solutions.

Given a set $S$ of size $n$ and a positive integer $m < n$. First generate all $m$-size subsets of $S$, for example, in lexicographic order and store them. Let $C$ be the set of all $m$-size subsets of $S$. The size of $C$ is $\binom{n}{m}$. The following algorithm generates all partitions

Generate(S, Partition)
  if S is empty
    print Partition
    return

  for each T in C such as T is a subset of S
    add T to Partition
    Generate(S-T, Partition)
    remove T from Partition
end

This algorithm repeats partitions but you can check if a Partition repeats. If it does then do not print it. One possible solution is checking its lexicographic order.

The second approach, which I think is simpler, is to systematically generate all $(n/m)$-size subsets of $C$. If for some $(n/m)$-size subset $T$ all sets in $T$ are mutually exclusive, then $T$ is a partition and so print it.

Example: $S=\{a,b,c,d\}$ and so $C = \{\{a,b\},\{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}\}$. Then using the second approach we systematically generate all $4/2=2$-size subsets of $C$. Thus while generating if we have $\{\{a,b\},\{a,d\}\}$ then we just skip it since it's not a partition. But if we have $\{\{a,b\},\{c,d\}\}$ then we print it since it is a partition. Furthermore, there is no chance of generating duplicate of a subset of $C$ since we generate all (distinct!) combinations of $4/2=2$ elements from $\binom{4}{2}=6$.

For generating combinations of $k$ elements from $n$ you could look, for example, here.


Are there algorithms with non-convex and non-concave computational complexity?

Yes, there are algorithms whose complexity in $\Theta$ can only be described using a non-convex, non-concave function. Here's one such algorithm (that serves no practical purpose, but still).

Read the length of the input $n$
If $n$ is even, halt
If $n$ is odd, loop for $n^2$ steps, then halt.

Suppose the complexity $T(n)$ of this algorithm is $\Theta(f(n))$, then there are $c,k$ so that for sufficiently large $n$, $cf(n)\leq T(n)\leq kf(n)$. Suppose (for contradiction) that $f$ is convex.

Let $n$ be odd and sufficiently large, we have that $2f(n)\leq f(n-1)+ f(n+1)$ (by concavity) and thus $\frac{2}{k}T(n)\leq\frac{1}{c}(T(n-1)+T(n+1))$. Substituting the original run time:

$$\frac{2}{k}(n+n^2)\leq\frac{2}{c}n$$

In other words, we have (up to some constants) $n^2\leq n$ which is a contradiction. So $f$ can not be convex, and by a similar argument can not be concave either.


How do you know if a language accepted by a DFA is $Σ^*$?

You don't input a language to a DFA. Each time you run the machine, the input is just a string. The language accepted by the DFA is the set of inputs that cause it to end in an accepting state (called a final state by some authors). Therefore, the automaton accepts $\Sigma^*$ if every possible input leads to an accepting state.

So, to decide if an automaton accepts $\Sigma^*$, you need to check if every input does indeed lead to an accepting state.


Complexity of recursion T(n) = 2T(n-1) + C?


Prove finding a near clique is NP-complete

I think the following reduction works (unless I missed something):

Given $G=(V,E)$ and $k$, output $G'$ which is obtained from $G$ by adding $2$ new vertices $\{x,y\}$. that are each connected to all the vertices in $V$ (but not to each other). Finally, the output is to search for a $k+2$ near clique.

Clearly this is polynomial (linear).

If there exists a $k+2$ near clique in $G'$, then if $k+1$ of its vertices are contained in $V$, then $G$ has a $k$-clique.
If less than $k+1$ vertices are from $V$, then at least $k$ of them are, since $x$ and $y$ are not connected between them. But then, the $k$ remaining vertices in $G$ must form a clique.

Conversely, if $G$ has a $k$-clique, then just add the two new vertices $x,y$ to get a $k+2$-near clique.


Rabin-Karp

Rabin-Karp string search would be a good candidate, because it can use a rolling hash function.

You pick a segment length $\ell$.  For each "needle", you hash its first $\ell$ characters, and store it in a hashtable keyed on the hash.

Then, as each character of text arrives, you compute the rolling hash of the last $\ell$ characters, look it up in the hash table, and possibly find one or more candidate needles that might match; then you test them directly.

This requires that the segment length be shorter than the shortest needle, but long enough to make hash collisions rare (i.e., so that the first $\ell$ characters of a needle mostly uniquely determines the needle).  If you have a wide range of needle lengths, I suppose you could pick two segment lengths $\ell_1,\ell_2$, have two hash tables, and store each needle in appropriate hashtable according to its length.

Aho-Corasick

The Aho-Corasick algorithm would also be a good candidate.  It solves exactly this problem, and doesn't require any assumptions on the lengths of the needles.

You might also look at Commentz-Walter.


It depends on what definitions you use.  Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of length $n$.  Papadimitriou [2], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the work tapes.

However, the space analogue of the linear speedup theorem implies that, actually, these two definitions are equivalent, so you should pick whichever one is most convenient for you. Since you want to distinguish between machines that use up to $c_1n$ work space and those that use up to $c_2n$, the Papadimitriou-style definition seems more appropriate to your needs. Make sure you clearly and explicitly define $\mathrm{SPACE}(f(n))$ before using it. But do be aware that anything you can do with $n$ worktape cells using a $k$-symbol alphabet, I can do with $n/2$ cells by using an alphabet of size about $k^2$. Unless you're using a fixed tape alphabet, $\mathrm{SPACE}(c_1n)$ and $\mathrm{SPACE}(c_2n)$ are the same complexity class, even with the Papadimitriou-style definition.

References

Michael Sipser, Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013. (Earlier editions almost certainly use the same definition.)
Christos H. Papadimitirou, Computational Complexity. Addison Wesley Longman, 1994.

Acknowledgments
Thanks to The Vee for pointing out an error in an earlier version of this answer.


Is it better to store the magnitude of an arbitrary-precision number in BigEndian or LittleEndian order in an integer array?

You are replacing magnitude[i] by magnitude[SZ-i]. That won't have any effect on complexity nor ease of implementation. Depending on the way simplifications occur, one or the other could have slightly less index adjustments, but I won't dare a guess which. Little endian seems slightly more in line with the usual presentations of the algorithms (for instance in TAOCP), big endian had a more intuitive representation of the number in memory, but that's an opinion more than a fact.

If you look at memory access patterns, there was a time when cache prefiller handled better increasing consecutive accesses (which would have favored little endian), but nowadays, I don't think it still make a difference at least on workstation and server processors.

So I don't think there is a compelling argument to choose BE over LE or ortherwise. Take the one which make you more at ease.


How do I use message passing to find the maximum of all values in a grid?

Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes.

After this, the last row would contain the maximum values of each column. Then, we could have the last row propagate the maximum value in the right direction so that the (n,n)th element contains the maximum value from this row. Since this row contained the maximum values from each column, (n,n)th element will essentially possess the maximum value from the entire grid.

We could then choose to propagate this value through the grid in parallel backwards till all the nodes know about this maximum value.

Complexity will be O(n) and there will be 4n hops of message passing through this proposed scheme.

Edit: Here's A pseudo-code. Disclaimer: not tested, might contain bugs

findMaxAllThreads(){
    int maxVal;

    // At the start, each element's max value will exactly be its value itself.
    maxVal = procId.val;

    // If this is the first element in the column, simply send the current
    // max value to the next element within the column.
    if(procId.row == 1)
        sendMessage(procId.row + 1, procId.col, maxVal);

    // For any other element in a particular column, except the last one,
    // compare the received value with the current max value and send the
    // updated value to the next element.
    else if(procId.row < n)
    {
        // wait for the message from the previous element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value till this node.
        if(val > maxVal)
            maxVal = val;

        // send the updated max value to the next element in the column.
        sendMessage(procId.row + 1, procId.col, maxVal);
    }

    // If we reach the last element in the column, we need to propagate the
    // values rightwards to the next element within the last row.
    else
    {
        // Receive the message from the (n-1)th element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value. Note that this will be the maximum value of
        // this particular column.
        if(val > maxVal)
            maxVal = val;

        // If this is the (n,1)th element in the whole grid (bottom left), then
        // simply propagate the max value to the next element rightwards in the
        // row.
        if(procId.col == 1)
            sendMessage(procId.row, procId.col + 1, maxVal);
        else
        {
            // Wait for the value from the previous element in this row.
            recvMessage(procId.row, procId.col - 1, val);

            // Update the max value till now.
            if(val > maxVal)
                maxVal = val;

            // If this is not the (n,n)th element in the grid, propagate the
            // value to the right.
            if(procId.col != n)
            {
                // Propagate the max value to the right.
                sendMessage(procId.row, procId.col + 1, maxVal);
            }

            // if this is the bottom-right (n,n)th element in the grid, wait
            // for the final value arriving from  the (n, n-1)th element from
            // the left.
            else
            {
                // Receive the message from the (n-1)the element in the nth row.
                recvMessage(procId.row, procId.col - 1, val);

                // Update the value. Note that this is also the maximum value
                // in the entire grid.
                if(val > maxVal)
                    maxVal = val;

                // Now maxVal contains the maximum value from all the processes.
                // We could choose to report it or if we want, we could
                // propagate it all the way back to the first node, so that
                // it's known globally as the max value.
            }
        }
    }
}


If P = NP, then how not cannot solve NP-hardness (the one that doesn't intersect with NP-complete) in polynomial-time?

You have your reductions the wrong way around. A problem $X$ is NP-hard if every problem in NP can be reduced to $X$. That is, saying that $X$ is NP-hard means that, if we had an efficient algorithm for $X$, we would have an efficient algorithm for every problem in NP: $X$ is easy implies all of NP is easy.

So, suppose that P$\,=\,$NP. Then, all of NP is easy, but that tells us nothing about $X$, because the implication goes the wrong way. Maybe $X$ is easy; maybe it's hard. In fact, some NP-hard problems are definitely hard: the halting problem is NP-hard but it's undecidable, regardless of what the relationship between P and NP turns out to be.


Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?

"By definition" recent research papers usually contain non-trivial results and they often (always?) require a deep knowledge of the argument in order to be well understood, so if you pick a paper at random you'll probably find a bunch of obscure signs in your hands :-)

So my suggestion is to look at "old" research papers (but not "too old"):

pick a particular argument/theorem that you think you have understood informally (or an argument that intrigues you);
read more about it on a theory of computation book or on Internet (for example start from Wikipedia and look at the references at the bottom, or search it on Google adding the keywords "introduction" or "lecture notes");
finally search the paper in which that argument/theorem was originally published and read it;

For example one of the fundamental basic results in computational complexity is the (deterministic) Time Hierarchy theorem. Very informally the theorem says that given more time, a Turing machine can solve more problems. You can start reading the Wikipedia article, then pick a lecture note with a more formal proof Googling around (for example pick this one by Arora). Finally when you think that you've understood the proof well download and read the original paper R. Stearns and J. "Hartmanis paper On the computational complexity of algorithms", 1965. You'll find that it contains even more details and is more formal.


What kind of Neural Network (if any) could fit two sets of data points?

Try a common feed-forward neural network with one hidden layer and train it with error backpropagatin to find a coherence between your input (temperature values) and output (migration patterns). In order to train a neural network, you have to have pairs of input and output vecors, i.e. in your case, one temperature measurement position corresponds to one migration position. If you cannot assign single input-output pairs, you might do some preprocessing (for example, simply grouping your data into a grid on the x-/y- plane and taking the mean of each grid). The question to find a suitable number of neurons in the hidden layer is discussed here.

Note that there exist many machine learning techniques to learn relations between input and output data. Furthermore, there exists a notable variety of artificial neural networks in structure as well as in training algorithms. As your question explicitly demands a neural network, this answer tries to provide a rather straightforward standard method.

For pattern analysis (in order to understand and/or visualize the patterns/correlations) some statistical approaches might be more suitable, e.g. clustering the data with k-means/EM-algorithm.


Group adjacent sections to create groups with biggest value, value is changing in groups

Your problem can be solved with dynamic programming using a straightforward algorithm.  Let $V[i..i+j]$ denote the value of a single group with numbers $i,i+1,\dots,i+j$.  You say you know all of those values.  Let $A[i]$ denote the value of the best way to group all of the numbers $1,2,\dots,i$.  Then $A[i]$ satisfies the recursive equation
$$A[i] = \max(A[i-4] + V[i-3..i], A[i-3] + V[i-2..i], A[i-2] + V[i-1..i], A[i-1] + V[i..i]).$$
Set $A[-3]=A[-2]=A[-1]=A[0] = 0$.  You can evaluate $A[1]$, $A[2]$, $A[3]$, etc. in that order, using a linear scan.  This takes 44 iterations of the loop, and each iteration of the loop uses a few simple lookups and operations, so the total running time will be extremely fast.  Finally, $A[44]$ holds the solution to your answer, i.e., the value of the best way to group the numbers 1,..,44.  If you want to retrieve the grouping itself, you can do that via standard techniques with prev pointers (each time you take a max, remember which one was the largest; or go back and re-compute it).


Why does little endian apply to numbers and not to text strings?

The premise is wrong. Unicode encodings include UTF-16BE, UTF-16LE, UTF-32BE and UTF32-LE. Only UTF-8 has no Litte-Endian or Big-Endian variants.

Fundamentally, Endian-ness is about the byte order of multi-byte words, and you're thinking of text encodings which use a single byte per character (i.e. ASCII). There's no order to a single byte.


A linear temporal property that represents this (basic) execution?

Since you are asked to formulate these properties in LTL, you might want to think of them as properties given with predicates over infinite sequences of states (or events where each event changes the state); in your case, you know that at each state some of the three propositions, {a, b, c} might be true.

When we talk about LTL, it's good to summarize what does the formalism support to figure out whether the given property can be formulated in it. Note that previously mentioned propositions are often formulated as state formulas, which might hold in a particular state. So, LTL supports: state formulas (propositions that might hold in particular state), (standard) Boolean operators (like logical or ||), and path quantifiers (like globally G and next X, which produce other state formulas), which effectively allow state formulas to describe sequences of states.

I will describe one potential solution in the "extended" LTL, which includes additional operators besides the fundamental ones. (These are easily expressible using only the basic operators, next and until; more details can be found in a more thorough treatment of LTL).

  So far all I have done is split the property into two parts such that the property P is the union of P1 and P2 but I don't know how to formulate my answer.

Indeed, at the top level, as you recognized, you should have union, which effectively translates to || of P1 and P2:

P1 || P2

Going back to P1 ((1) a and b never happen at the same time), which states that something should never happen, it's good to think whether such temporal quantification can be translated to some of the offered quantifiers in LTL. This is indeed possible, and "never some property P" can be expressed in terms of combining a Boolean operator and a quantifier, in the following way:

   G( not P ) (always, P is not true)

thus, P1 can be expressed by using given propositions as:

   G( not (a && b) ) (always, it is not true that both a and b hold)

On the other hand, as Shaull pointed out, the second property is a bit trickier. Although, such a requirement might have been written more precisely (to avoid ambiguity), we can interpret it to mean that a and c should happen, at some point, such that c happened earlier than a.

Now, when we identified earlier, we might think of another LTL quantifier that semantically matches the notion of ordering states (or events). That quantifier is:

   X (quantifier for next, i.e. formula that will hold in the next state)

Thus (under the interpretation that both propositions must be true at some point), we want to say that eventually, c happens, while at a point after that, eventually a happens as well:

   F( c && X(F a))

arriving at the final solution:

   P1 || P2 = (G( not (a && b) )) || F( c && X(F a))

which checks that either of the given properties are satisfied in the execution, as you originally suggested.

After you have an idea of how the formula should look like to makes sense (semantically, with respect to the property you want to model), you always want to check whether the formula is well formed, i.e. whether the formula is syntactically correct. (More details can be found in one of the more thorough treatments of LTL.)


Fast algorithms that work on some large percentage of possible inputs

Not quite what you're looking for but the concept of a randomized approximation scheme (RAS) is closely related and very widely studied.  This is an algorithm for computing a (numerical) quantity $f(x)$ given an input $x$ and an error tolerance $\varepsilon$. With probability at least $\tfrac23$, the algorithm returns a value $\hat{f}$ such that $(1-\varepsilon)f(x)\leq\hat{f}\leq(1-\varepsilon)f(x)$. With probability at most $\tfrac13$, the algorithm either returns an answer outside that range or says, "Uh, I dunno." If the algorithm runs in time polynomial in $|x|$ (the length of the input) and $\varepsilon^{-1}$, it's called a fully polynomial randomized approximation scheme (FPRAS).

Only succeeding with probability at least $\tfrac23$ sounds pretty terrible – "Oh, wow, it's wrong one time out of every three!". However, it's easy to boost that to any satisfactory probability by running the algorithm repeatedly and taking the median answer (counting, "Uh, I dunno" as $\infty$).  By a Chernoff bound, taking the median of $O(\log |x|)$ runs gives failure probability polynomial in $|x|^{-1}$ and taking the median of polynomially many runs gives exponentially small failure probability.


Relationship between dependent sum type and dependent product type?

I believe you meaning the following.

A value of type $\prod_{n : \mathbb{N}} P(n)$ is a function which takes a value $n$ of type $\mathbb{N}$ as input and outputs a value of type $P(n)$. So the domain of such a function is $\mathbb{N}$. What is its codomain? Well, the type of the result depends on the value of the input, which is why it's called a dependent product. So it doesn't really have a codomain in the traditional sense.

But we can also view this situation as follows: Yes, such a function $f$ has a codomain, namely the dependent sum $\sum_{m : \mathbb{N}} P(m)$; but with the condition imposed that $(\mathsf{fst} \circ f)(n) = n$ for all $n : \mathbb{N}$, where $\mathsf{fst} : \sum_{m : \mathbb{N}} P(m) \to \mathbb{N}$ is the first projection.

More precisely, the following types are indeed equivalent ("equivalent" as in the HoTT book):

$\prod_{n:\mathbb{N}} P(n)$
$\prod_{f : (\mathbb{N} \to (\sum_{m : \mathbb{N}} P(m)))} \prod_{n:\mathbb{N}} ((\mathsf{fst} \circ f)(n) = n)$ (the type of functions satisfying the stated condition)


Difference between multi-agent systems and distributed systems

What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?

Multi Agent System
According to the book;  Innovations,theories in  multi agent systems and applications, September,2015

It states that in multi agent system,agents have the ability to solve complex real world problems besides being autonomous and interlinked. thus exhibiting some intelligence

Therefore,MAS falls under the umbrella of Distributed Artificial intelligence.e.g. Autonomous cars,SoftBots to mention but a few.

On the otherhand in Distributed systems,agents perform a specific task with the centralised agent taking control of the goal,that's achieved.e.g cellular network applications controlled by NOC,aircraft system that is controlled by Area Control Centres.

Therefore,Distributed systems,fall under the umbrella of  Distributed Computing


Single tape Turing Machine that accepts string with at least five G's and at most three T's?

In general, whenever you try to design a machine accepting a language with this kind of "finite conditions", the easiest solution is to hard-code those conditions directly into the states of your machine.
Here, you would have 24 "counting" states, labelled by $(g, t)$ for $0 \leq g \leq 5$ and $0 \leq t \leq 3$. Whenever you read some $G$ while already in state $(g, t)$, you move on to the corresponding state $(g+1, t)$ (and if you read a $T$, you go to $(g, t+1)$). Otherwise, you simply loop on your current state.
Now, you have to enforce your conditions: if you read a $T$ while in a state $(g, 3)$, you reject the word, and if your word end while you are in a state $(g, t)$ with $g < 5$, you reject too.
Of course, there is probably some technical details to work out precisely, and there might exist some clever and trickier ideas to do this, but this method is easy to understand and can be immediately generalised to all the problems of this kind.


Why can the alphabet be represented in numbers in base 256

A number in base ten is just a sequence of digits 0–9, with the string $d_n\dots d_2 d_1 d_0$ representing the number $10^nd_n + \dots + 10^2d_2 + 10^1d_1 + 10^0d_0$. Similarly, a character in an 8-bit character set can be considered to be a "digit" between 0 and 255, so a sequence $d_n\dots d_1d_0$ of these "digits" represents the number $256^nd_n + \dots + 256^2d_2 + 256^1d_1 + 256^0d_0$.

Another way to see this is to write the number out in binary.  For example, a 32-bit binary number can be considered as having 32 binary digits (bits) or 4 256-ary digits by collecting the bits into groups of 8.  In the same way, an 8-digit decimal number can be considered as a 4-digit number in base-100.  For example

$$38572856$$

can be considered as

$$38\,57\,28\,56 = 38\times 100^3 + 57\times 100^2 + 28\times 100^1 + 56\times 100^0 = 38572856\,.$$

For the Latin alphabet, base 26 would be the most natural representation, since the letters can be treated as 26 different "digits".  You may also have heard of Base-64 encoding which uses the 64 characters A...Za...z0...9+/ in that order as 64 "digits".  The advantage there is that all 64 of the characters can easily be included in a text file and, by using Base-64, you can code three bytes of binary data (24 bits) into four characters (4x6 bits), which is a acceptably inefficient.


When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:

$$C_i = \frac{1}{i+1} { 2i \choose i }$$

are the Catalan numbers. Using Stirling's approximation, we find:

$$\log C_{2n} = 2n - O(\log n)$$

So to represent a binary tree with $n$ nodes, it is sufficient to use two bits per node. That's a lot less than two pointers.

It's not too difficult to work how how to compress a static (i.e. non-updatable) binary search tree down to that size; do a depth-first or breadth-first search, and store a "1" for every branch node and a "0" for every leaf. (It is harder to see how to get $O(\log n)$ access time, and much harder to see how to allow updates to the tree. This is an active research area.)

Incidentally, while different balanced binary tree variants are interesting from a theoretical perspective, the consistent message from decades of experimental algorithmics is that in practice, any balancing scheme is as good as any other. The purpose of balancing a binary search tree is to avoid degenerate behaviour, no more and no less. Stepanov also noted that if he'd designed the STL today, he might consider in-memory B-trees instead of red-black trees, because they use cache more efficiently. They also use $n + o(n)$ extra pointers to store $n$ nodes, compared with $2n$ or $3n$ for most binary search trees.

As for hash tables, there is a similar analysis that you can do. If you are (say) storing $2^n$ integers in a hash table from the range $[0,2^m)$, and $2^n \ll 2^m$, then it is sufficient to use

$$\log {2^m \choose 2^n} \approx (m-n)2^n$$

bits. It is possible to achieve close to this bound using hash tables.

To give you the basic idea, consider an idealised hash table where you have $2^n$ elements stored in $2^n$ slots (i.e. load factor of one where every "chain" has length one).

If you hash $m$ bits of key into $m$ bits of hash, then store this in a $n$-bit hash table, then $n$ bits of the hash are implied by the position in the hash table, and you therefore only need to store the remaining $m-n$ bits. By using an invertible hash function (e.g. a Feistel network), you can recover the key exactly.

Of course, traditional hash tables have Poisson behaviour, so you would need to use a technique like cuckoo hashing to get close to a load factor of one with no chaining. See Backyard Cuckoo Hashing for further details.

So if space usage is a far more important factor than time (subject to time being "good enough"), it may be worth looking into this area of compressed data structures, and succinct data structures in particular.


What is an example for a decidable language not in P?

Yes, there are decidable languages that are definitely not in P. The time hierarchy theorem says that P$\,\neq\,$EXP, so P$\,\neq\,$R, independently of the P vs NP problem. Any EXP-complete problem is definitely not in P: for example determining whether white has a winning strategy from a position in generalized chess ("generalized" in the sense of allowing a board of any dimensions, with any arrangement of any number of pieces, but otherwise following all the rules of standard chess).


CTL - model checking for formula $A [a \cup b]$

Your answer $Sat(A(a \cup b)) = \{ s_1, s_2, s_3, s_4 \}$ is correct. And your conclusion that the model does not satisfy the property is also correct because the initial state $s_0 \notin Sat(A(a \cup b))$.

In my opinion, there is a typo in Line 7:
$$Q := Q \cup \left( \{ s \mid \forall s' \in Q. (s,s') \in R \} \cap Sat(\phi) \right).$$

According to the fixed point interpretation,
$Sat(A(\phi \cup \psi))$ is the smallest set $T \subseteq S$ satisfying
$$Sat(\psi) \cup \{ s \in Sat(\phi) | Post(s) \subseteq T \} \subseteq T.$$
Therefore, the iteration step for Line 7 should be:
$$Q := Q \cup \left( \{ s \mid \forall (s,s') \in R. s' \in Q \} \cap Sat(\phi) \right),$$ or concisely,
$$Q := Q \cup \{ s \in Sat(\phi) \mid \forall (s,s') \in R. s' \in Q \}.$$

By the way, this lecture note by Joost-Pieter Katoen is quite out-of-date (back to 1999). In 2007,  along with Christel Baier, he has published a wonderful book on model checking "Principles of Model Checking (The MIT Press)". You should read it now (online version avaiable).


Comments on "Which combinatorial problem is similar to this problem?"

You are probably assuming that the cost function is efficiently computable, so that "does there exist a selection of the $n$ options with less than $c$ cost" is an NP decision problem. This assumption is not actually stated in the original question. The question merely states "The cost function can be any function, not necessarily linear."
As D.W.'s answer says, "you will need to know something about the cost function and take advantage of some structure or properties it has." Making the assumption that the cost function can be computed in time polynomial in $n$ gives it a little bit of structure. (Exactly how much structure this gives it is the essence of the P vs. NP problem.)


Time complexity of solving a set of 2-sat instances?

Although 3SAT problem is NP-complete, there is a polynomial algorithm making use of the beautiful SCC (Strongly Connected Component) directed graph algorithm.

Suppose there are $n$ variables and $m$ clauses in the 2SAT instance $\mathcal{I}$. The parameters $n$ and $m$ represent the size of $\mathcal{I}$

The 2-SAT instance is modeled by a directed graph $\mathcal{G_I}$, with

$2n$ vertices: for each variable $x$ in $\mathcal{I}$, there are two vertices $v_x$ and $v_{\bar{x}}$ (i.e., variable and its negation).
$2m$ edges: for each clause $x \lor y$, there are two directed edges $\bar{x} \to y$ and $\bar{y} \to x$. Note that the latter two implicative forms are equivalent to $x \lor y$.

The polynomial algorithm (it is actually a linear algorithm) proceeds as follows:

Obtain the SCCs of $\mathcal{G_{I}}$ in linear time $O(n + m)$;
Assign True to each literal (Notice: not the variable) in the destination SCC (denoted $SCC_d$);
Delete $SCC_d$ and its corresponding source SCC ($SCC_s$). (Note the symmetry in the graph $\mathcal{G_{I}}$);
Repeat (2) and (3) until $\mathcal{G_{I}}$ is empty.

For example:

$\mathcal{I} = (x_1 \lor x_2) \land (\bar{x_2} \lor x_3) \land (\bar{x_1} \lor
  \bar{x_2}) \land (x_3 \lor x_4) \land (\bar{x_3} \lor x_5) \land (\bar{x_4} \lor
  \bar{x_5}) \land (\bar{x_3} \lor x_4)$

The graph $\mathcal{G_{I}}$ is:


Precise runtime of the algorithm to find number of digits in an integer

There are two answers here:

$\log_{10} n = \log_{10} 2 \log_2 n$, and $\log_2 n$ is (almost) the length of $n$ in bits.
We don't care about the exact complexity. The point of big O notation is to hide multiplicative constants. A function is $O(\log_2 n)$ iff it is $O(\log_{10} n)$. Moreover, the exact time complexity depends on the exact computation model used (i.e. compiler, CPU, operating system and environment – presumably this code snippet runs on actual hardware and its execution time is measured in seconds), which you haven't specified anyway. Again, the point of big O notation is that these details don't matter since they only affect the complexity by a multiplicative constant.

Another point which you should consider is that in practice, either value has a fixed length, or it is variable length (bignum). If it has fixed length (say it's a 32 bit integer), then the correct parameter here is not the length (which is constant) but the value itself. If it has variable length, then the division instruction cannot be reasonably assumed to take constant time.


Problem on Floating Point Representation

First, this is not the way standard IEEE P754 single precision floating point numbers are represented :

Exponent is not two's complement, there is instead an offset, for IEEE normalised : F=2^(Exponent - 127) * 1.Mantissa * Sign
Normalised numbers have an exponent different from 00 (being denormals) and FF (for infinites, NaN)

If this peculiar format has no implicit 1, mantissa should be between 0.10[..]0000 and 0.11[..]1111 :  Answer (D) or between 1.0000 and 1.11111, which is your proposal.

(IIRC, Intel double extended x87 80bits format does not have the implicit 1 and works as you describe. It is not striclty IEEE compliant, the 8087 being older than the standard.)


Can normal physics laws be simulated in Digital physics?

The laws of physics are stated in the form of mathematics. Differential equations are pretty popular, for example classical mechanics can be described with differential equations.

You can program a computer to take some initial state of the universe and apply all the laws of physics to it to get a new state of the universe. This comes with a couple of caveats. First, you need to somehow discretize the time steps you compute. Differential equations operate under continuous time, but a numerical simulations does discrete steps. It's reasonably well understood how to do that without losing too much precision. This brings us to a second problem, precision. Physics is generally formulated using real (or complex) variables, but computers only deal with finite precision. Usually this is ok, because in reality we can also only distinguish things with finite precision. Lastly, our laws of physics are not yet complete. There are a number of phenomena where we don't really know what's supposed to happen, so the simulation won't represent the real universe perfectly, even if we start with a proper starting state (which we can also only guess) and use sufficient precision and sufficiently small time steps.

Note that it is completely impractical to simulate all laws of physics as we know them on real computers. Even simulating single molecules with all relevant laws is very hard even for supercomputers.

Nevertheless, physicists simulate things all the time, sometimes using bold approximations to cut down the required computation. It's really important in physics to do simulations. Wikipedia has on overview article on Computational Physics and Richard Feynman has written a classic paper called Simulating Physics with Computers.

It is of course also possible to tweak the laws of Physics a bit and do your simulation. You can change the equations, or the constants and see what happens to your simulated system. You can for example find that changing some constants just a little produces an inhospitable universe.

Now I don't think it's possible to change fundamental mathematical truths in your simulated universe, because Physics makes no prediction about mathematics. You can't change the laws of Physics such that 1+1 != 2.


Linear time labeling algorithm for a tree?

Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:

Put all vertices in a priority queue, with their priority being their degree.
While the queue is non-empty:

Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).

In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:

Initialize an array of length $V$ with the degrees of all vertices.
Initialize another array of length $V$ with "alive".
Go once through the first array, and push all vertices of degree $1$ to a queue.
While the queue is non-empty:

Pop a vertex $v$.
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Mark $v$ as "dead".
If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
If the new degree of $u$ is $1$, push $u$ to the queue.

Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.

Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.

You run this algorithm on the root.


Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?

My teacher:

This kind of tricky wording is to be expected the AP Exam. The phrase "have the same value" we can take to mean equal. Now, "not all three equal" does not mean "all three different", it means at least one is different. So let's use the test case {a=0, b=0, c=1}

! (a == b || b == c || a == c)

! (0 == 0 || 0 == 1 || 0 == 1)

! (true or false or false)

! (true)

false

a > b || b > c || a > c

0 > 0 || 0 > 1 || 0 > 1

false || false || false

false

a >=b && b >= c && c >= a

0 >=0 && 0 >= 1 && 1 >= 0

true && false && true

false

a != b && b != c

0 != 0 && 0 != 1

false && true

false

0 != 0 || 0 != 1

false || true

true

When you think about it logically, given three things, one of them has to be not equal to one of the other two in order for all three of them to not be the same.

Thus the correct answer is A.


You can reduce from the Hamiltonian path problem. Given an instance of the Hamiltonian path problem with $n$ vertices:

Add a start vertex $s$ and an ending vertex $t$.
For every vertex $v$ that is not $s$ or $t$, add edges $(s, v)$ and $(v, t)$ with weight $n-1$ and $n-2$ respectively.
For every other edge, assign it weight $-2$.

Now the previous graph has an Hamiltonian path if and only if there is a simple path with negative total weight from $s$ to $t$ in the new graph.


One way that always works and is relatively easy to turn into code is Edmond's rotational embedding scheme. Let $G$ be a connected graph with vertices $V(G)=\{v_1, v_1, \dotsc, v_p\}$. For every vertex $v\in V(G)$ choose a permutation $\pi_v$ of the vertices adjacent to $v$. Then the collection of permutations $\pi_{v_i}$ determine an embedding of $G$ in a orientable surface $S_n$ of genus $n$, and, conversely, every embedding of $G$ in $S_n$ is determined by some collection of permutations as described above.

For example, consider $K_4$ with vertices labeled $\{1, 2, 3, 4\}$ and permutations
$$\begin{align}
\pi_1 &= (2\ 4\ 3)\\
\pi_2 &= (1\ 3\ 4)\\
\pi_3 &= (1\ 2\ 4)\\
\pi_4 &= (3\ 1\ 2)
\end{align}$$

The permutations will correspond to the counterclockwise order in which the adjacent vertices are encountered in the embedding (hence the term rotation). The permutations give rise to permutations, $\pi$, of the directed edges, defined by $\pi((v_i, v_j)) = (v_j, \pi_j(v_i))$. In the example above, we'll have
$$\begin{align}
\pi((2, 1))&=(1, \pi_1(2)) = (1, 4)\\
\pi((1, 4))&=(4, \pi_4(1)) = (4, 2)\\
\pi((4, 2))&=(2, \pi_2(4)) = (2, 1)
\end{align}$$
and we're back where we started, having generated a 2-cell $(2, 1, 4)$. Starting the process with the directed edge $(1, 2)$ gives rise to a 2-cell $(1,2,3,4,1,3,2,4,3)$ and we stop here, having used all 12 directed edges in $K_4$. We know that for an orientable 2-cell embedding in $S_n$ of a graph with $p$ vertices, $q$ edges, $r$ faces we'll have
$$
p-q+r=2-2n
$$
in this case we have $p-q+r=4-6+2=0=2-2n$ so $n=1$, meaning that $K_4$ has genus no larger than 1.

Of course, as presented this is a terribly inefficient algorithm, since there will be factorially many permutations for each vertex. There are some tweaks that will speed this up and there are some more modern approaches/modifications one could use (Edmond's paper came out in 1960), but the upshot is still that there's no efficient way to compute the genus of a graph.


3-dimensional matching approximation algorithm (implementation details)

We don't need the maximum matching, just one of cardinality $2$ if it exists.

Scan $S_r$ looking for a triple $T$ such that $\lvert T \cap \{a, b, c\}\rvert = 1$. If no such $T$ exists, then the maximum cardinality of a matching is clearly $1$. Otherwise, assume without loss of generality that $T = \{a, x, y\}$.

Scan $S_r$ again looking for a triple $U$ such that $T \cap U = \varnothing$. If no such $U$ exists, then every triple intersects both $\{a, b, c\}$ and $T$. For every $U \in S_r$, we have $\{a\} \subseteq U$ or $\{b, x\} \subseteq U$ or $\{b, y\} \subseteq U$ or $\{c, x\} \subseteq U$ or $\{c, y\} \subseteq U$.

There are several possibilities for a cardinality-$2$ matching $\{T_1, T_2\}$. There's an easy test for those of type $\{b, x\} \subseteq T_1$ and $\{c, y\} \subseteq T_2$. Similarly, $\{b, y\}$ and $\{c, x\}$. The only other types are the four like $\{a\} \subseteq T_1$ and $\{b, x\} \subseteq T_2$. To test for those, gather all triples of the form $\{b, x, z\} \in S_r$ and discard the ones in excess of three. Try each of the remainder against all possibilities containing $a$. The three $\{b, x, z\}$ candidates suffice because no triple containing neither $b$ nor $x$ intersects all three.


Can two equal classes be separated wrt an oracle?

While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as well.

Problems with the current definition

First of all, as @D.W. mentioned in the comments, the claim 'Language class $X$ is defined w.r.t. machine $M$' is ill-posed. There is no need to define a class of languages with a machine at all. Even if we have a language which is commonly described w.r.t. some machine, such as $P$, there is nothing preventing us to give an equivalent definition that uses no machine at all! (Not sure if this is doable or has been done. Perhaps you can do something based on $\lambda$-calculus?)

The second problem is that oracle access is not a modifier/property of a language class! This follows immediately from the previous point: if I define a language without using a machine, how on earth am I able to use this oracle if I don't even have a machine?

The crucial mistake that leads to your problem is that a 'language' under oracle access actually depends on the definition of the language and a 'language' with oracle access is not invariant under the method you use to define the language. In fact, the often posed statement $P^O = NP^O$ is an example of really bad notation, as $P$ and $NP$ aren't actually languages here, but methods to define languages!

Let's make this precise: Let $\mathcal{X}$ be a 'definition method' for languages that can access oracles (for example, a set of machines and some acceptance rules) Let $L(\mathcal{X})$ be the language class that is defined by $\mathcal{X}$. Let $\mathcal{X}^O$ be the extension of $\mathcal{X}$ with access to the oracle $O$.

Rephrasing the question

Your question can now be rephrased as follows, let language classes $A$, $B$ such that:

  There exists an $\mathcal{X},\mathcal{Y}$ such that $A= L(\mathcal{X})$, $B = L(\mathcal{Y})$ and $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type'.
  $\mathcal{X}$ and $\mathcal{Y}$ are able to use unbounded space.
  $A=B$
  There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

By combining 3 and 1, we can do without $A$, $B$ and focus on the machines:

  $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type' and are able to use unbounded space.
  There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

Now, the question crucially depends on what 'the same type' means. If $\mathcal{X} = \mathcal{Y}$, then satisfying both 1 and 2 becomes impossible, as  we now do have $\mathcal{X}^O = \mathcal{Y}^O$, so $L(\mathcal{X}^O) = L(\mathcal{Y}^O)$.

So, a necessary condition for statements 1 and 2 is the claim:

  There exists an oracle $O$ such that $\mathcal{X}^O \neq \mathcal{Y}^O$.

You can define 'type' however you wish, but if two machines don't behave the same when I give them the same oracle, I don't consider those machines to be of the same type.

So, in conclusion, after rephrasing your question more formally and giving a property which I believe 'type' should adhere to, the answer to your question is actually no.


The reduction rule you ask for is the usual one for IF statements. It consists of two computation rules and one context rule:

  $\text{IF TRUE}$ $a$ $b$ $\to$ $a$
  $\text{IF FALSE}$ $a$ $b$ $\to$ $b$
  $\dfrac{a\to a'}{\text{IF}~a\ b\ c\to \text{IF}~a'\ b\ c}$

In both the call-by-value (strict) and call-by-need (lazy) settings, both $a$ and $b$ can be arbitrary expressions. They need not be values.

Rules of this kind, that reduce specific functions (here IF), are often called delta rules.

Now, the reason step (2) above is necessary is so that the reduction rules for $\text{IF}$ can apply. $\text{IF}$ requires 3 arguments, but in the original term it has only two, so cannot be reduced. ($\text{IF}$ is being partially applied, just
like any function in Haskell. This means that only part of its arguments need to be supplied.) The use of $\eta$-expansion provides the additional argument, without changing the semantics.


Number of possible sequence partitioning

The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^*1$. Other variants can be solved in a similar way.

Suppose that the original sequence is $a_1,\ldots,a_n$. Let $b(i,x)$ denote the number of ways to partition $a_1,\ldots,a_i$ into any number of subsequences of the form $10^*1$ and $x$ subsequences of the form $10^*$ (open subsequences).

Initially $b(0,0) = 1$ and $b(0,x) = 0$ for $x > 0$. Let us now consider how to calculate $b(i+1,\cdot)$ given $b(i,\cdot)$. There are two possibilities to consider:

If $a_{i+1} = 0$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ by attaching $a_{i+1}$ to any of the open subsequences. Thus $b(i+1,x) = xb(i,x)$ in this case.
If $a_{i+1} = 1$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ in one of two ways: either it "closes" an open subsequences, or it forms a new open subsequences. Thus $b(i+1,x) = (x+1)b(i,x+1) + b(i,x-1)$.

The total number of partitions is then $b(n,0)$. Since $0 \leq x \leq n$, we can compute $b(n,0)$ in time $O(n^2)$ using dynamic programming.

As an illustration, here is a run of the algorithm on the sequence $1,0,1,1,0,1$. The columns correspond to $i$, and the rows to $x$:

$$
\begin{array}{c|cccccc}
x/i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
0 & 1 & 0 & 0 & 1 & 0 & 0 & 3 \\
1 & 0 & 1 & 1 & 0 & 3 & 3 & 0 \\
2 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\
3 & 0 & 0 & 0 & 0 & 1 & 3 & 0 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 3
\end{array}
$$


Every $NP$-complete problem is an example of this! It's just a question of how good the lower bounds are.

For example, there's an $\Omega(n)$ lower bound on basically every problem, since you need to read your entire input to solve it. This is a very imprecise lower bound, but it does exist.

So, you're not going to get a good list of a bunch of problems like this, because such a list would be too large, and uninformative.

Whether there are problems with notable lower bounds is a different issue. I don't know of any that fit your criteria (sorting is the most famous one, but it's in $P$). Here's an example question about bounds on 3SAT:

https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat

Not very informative, as you can see.
The known lower bounds in such a case will always be polynomial. If there were any problems verifiable in polynomial time (in $NP$) with an exponential lower bound, that would imply that $P \neq NP$.


Does stay put TM recognizes same languages as standard TM

No, the key terms are not "recognizes" and "decides", but rather "simulates". Given a Turing machine that can stay put, you can simulate it using a Turing machine that doesn't stay put. Given a transition of the form:

On state $s_1$, if the symbol under the head is $\alpha_1$ then change it to $\alpha_2$, stay put and transition to state $s_2$

you replace it with a pair of transitions

On state $s_1$, if the symbol under the head is $\alpha_1$ then change it to $\alpha_2$, move right and transition to $s'$
For every symbol $\beta$: On state $s'$, if the symbol under the head is $\beta$ then change it to $\beta$, move left and transition to state $s_2$

Here $s'$ is a new state that is used only to handle this transition.

The new Turing machine doesn't stay put but simulates the original Turing machine.

As the OP points out, we can actually improve this simulation by not adding new states at all (except for possibly one more state, a "stuck" state). Suppose we are at state $s_1$, see the symbol $\alpha_1$, and stay put. Let us continue to follow the machine. Either the machine never moves away from its spot, or it eventually moves either left or right, transitioning to state $s_2$ after changing the original symbol to $\alpha_2$. In the latter case, we can change the transition to a simple transition to $s_2$. In the former case, we can move instead to a special "stuck" state in which the Turing machine finds itself in an infinite loop; this state can be common for all "stuck" situations.

If we are guaranteed that the original Turing machine never gets stuck, and this is probably the assumption in your textbook, then we can do away with the "stuck" state, so that no new states are needed at all.


Message receipt verification in a cluster

Your suspicion is correct: under these conditions, there is no way to guarantee a solution. Yours is a consensus problem, and there is a general result that states the impossibility of consensus in an asynchronous network with failures. This result is sometimes known as FLP after its authors (Fischer, Lynch and Paterson) [FLP].

The original consensus states roughly this (see [FLP] or [L96] or [T00]): suppose you have $N$ processes with $N \ge 3$. The processes can communicate by sending asynchronous messages: there is no notion of real time, messages can take arbitrarily long in transit. Furthermore, a process may fail (it stops emitting messages). Define a configuration as an assignment of boolean values (0 or 1) to each process, and consensus as a configuration in which all non-failed processes have the same value. Each process may change its assigned value based deterministically on the messages it has received; the collection of algorithms executing on each process defines a distributed algorithm. The FLP result states that there is no algorithm that can reach a consensus from an arbitrary initial configuration, such that there is always at least one process that keeps its initial value. (In other words, the only solutions are the trivial one where all processes pick the same value.)

In your case, the failures are in transmissions rather than in processes, but this only makes the situation more difficult: you can simulate a process failure by losing all the messages to and from that process.

The FLP result implies that there is no distributed algorithm that will always (given sufficiently many received messages) lead to either all processes deciding on taking the action, or no process taking the action, unless they are all primed to act or all primed not to act.

Having clocks does not help: they are part of the local algorithm. They would help if you could put a bound on the message travel times: timeouts in transmissions are the usual way of solving consensus in practice.

Bibliography

[FLP] Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process". April 1985. Journal of the ACM 32 (2). DOI:10.1145/3149.214121

[L96] Nancy Lynch. Distributed Algorithms. Elsevier, 1996. 1-55860-348-4. http://groups.csail.mit.edu/tds/distalgs.html

[T00] Gerard Tel. Introduction to Distributed Algorithms. 2nd ed. Cambridge University Press, 2000. 0521794838.


Find a minimum-weight perfect 2-matching

From an answer to my other question it turns out that one can convert this problem to standard matching.

Find a minimum-weight perfect b-matching, where b is even

I still wonder whether this would give the most efficient approach?


Grammar for all words other than $wq,qw$

How about
\begin{align*}
S&\to q\mid w\mid qqB \mid wwB \mid qwA\mid wqA\mid \varepsilon \\
A&\to qB\mid wB \\
B&\to qB\mid wB\mid \varepsilon
\end{align*}
We can just explicitly include strings of length 0, 1 or 2 that are allowed, but add another non-terminal after the length two strings which are not allowed to force us to add at least one more terminal, then make sure after that we can add any letters we want in any order.


Given a vertex, find a path between it and each other vertex that minimizes the maximum weight in the path

Let $T = \{s\}$, and let $Q$ be a new empty priority queue. Insert each edge incident on $s$ in $Q$. While there are still nodes with $d$ from $s$ yet to be computed, extract and remove the minimum from $Q$.

If such edge connects a node $u$ in $T$ with a node $v$ not in $T$, add each edge incident on $v$ that still isn't in $Q$ to $Q$, then set $M[v]$ to $\max\{M[u], w(u, v)\}$.

Otherwise, disregard the extracted edge and extract more edges until you find a suitable one.

The overall complexity is $O(|E| \log |E|) = O(|E| \log |V|^2) = O(|E| \log |V|)$.

To informally prove correctness, we can observe that whenever we set $M[v]$ to a certain value $x$, we can certainly reach $v$ from $s$ with a path in which each edge weighs at most $x$. On the other hand, no better path exists, because we already gave each edge lighter than $x$ a chance to connect to $s$.


Hungarian Assignment Algorithm Implementation

The article you linked assumes that the reader knows how to apply the Hungarian algorithm on a similarity matrix because they have note in the introduction to Section 3 that Zager et. al. used the Hungarian algorithm for this purpose in the paper here.

Furthermore, there is no requirement in the Hungarian algorithm that necessitates integral entries; neither the Wikipedia article and this slide deck mention any requirement for the entries to be integers.  Authors may use integer values for examples because they're easy to work with, but that does not mean the algorithm requires them.


Maintaining an array supporting sum requests

Suppose for simplicity that $n = 2^N$ (otherwise, extend the array by zeroes). Maintain the following values:
$$
a_1, \ldots, a_n \\
a_1 + a_2, a_3 + a_4, \ldots, a_{n-1} + a_n \\
a_1 + \cdots + a_4, a_5 + \cdots + a_8, \ldots, a_{n-3} + \cdots + a_n \\
a_1 + \cdots + a_8, a_9 + \cdots + a_{16}, \ldots, a_{n-7} + \cdots + a_n \\
\cdots \\
a_1 + \cdots + a_{n/2}, a_{n/2+1} + \cdots + a_n \\
a_1 + \cdots + a_n
$$
By computing each line from the preceding one, you can compute all of these sums in $O(n)$.

Operation 1 can be implemented in $O(\log n)$ since each element is only involved in $\log n$ sums.

Operation 2 can be implemented in $O(\log n)$ since the sum can be broken into $O(\log n)$ sums of the type above.

Operation 3 and Operation 4 easily reduce to Operation 2 (exercise).

Details left to you.


Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$?

You need a data structure that supports the following three operations efficiently:

insert an element into the set
delete an element from the set
find the largest element in the set

There are multiple such data structures.  One reasonable choice is a balanced binary search tree, where all three operations can be implemented in $O(\log n)$ time.


Denote by $E_i$ the expected number of turns it takes get to the $N$th floor from the $i$th floor. You are interested in $E_1$. The numbers $E_i$ satisfy the recurrence
$$
E_i = 1 + p_i E_{i+1} + (1-p_i)E_1,
$$
valid for $i < N$, with a base case $E_N = 0$.

In order to solve this system of equations, multiply the $i$th equation by $p_1 \cdots p_{i-1}$ to get
$$
p_1 \cdots p_{i-1} E_i = p_1 \cdots p_{i-1} + p_1 \cdots p_i E_{i+1} + [p_1 \cdots p_{i-1} - p_1 \cdots p_i] E_1.
$$
Summing this for $1 \leq i \leq n-1$, we get
$$
E_1 = 1 + p_1 + p_1p_2 + \cdots + p_1 \cdots p_{n-2} + (1 - p_1 \cdots p_{n-1}) E_1,
$$
and so
$$
\begin{align}
E_1 &= \frac{1+p_1+p_1p_2\cdots+p_1\cdots p_{n-2}}{p_1 \cdots p_{n-1}} \\ &= \frac{1}{p_1 \cdots p_{n-1}} + \frac{1}{p_2 \cdots p_{n-1}} + \cdots + \frac{1}{p_{n-1}}.
\end{align}
$$


Is the maximum coverage variant of Vertex Cover also NP-hard?

Optimization problems cannot be NP-complete. Only decision problems – where the answer is YES or NO – can be NP-complete. This is because the notion of NP-completeness is defined only for decision problems. When we (loosely) say that an optimization problem is NP-complete, we really mean that their decision version is NP-complete.

The decision version of Set cover: given a set system $S$ with union $U$ and a number $r$, can we cover $U$ with $r$ sets from $S$?

The decision version of Maximum coverage is: given a set system $S$, a number $r$ and a number $t$, are there $r$ sets from $S$ that together cover at least $t$ elements?

See if you can prove that the decision version of Maximum coverage is NP-complete given that the decision version of Set cover is NP-complete, and then see if you can do the same for your new problem related to Vertex cover.

I should mention that Uri Feige proved in 1998 the following strong result regarding Maximum coverage. There is a polytime reduction $f$ taking a 3CNF $\varphi$ to an instance $(S,r,t)$ of Maximum coverage such that:

If $\varphi$ is satisfiable then there are $r$ sets from $S$ that together cover at least $t$ elements.
If $\varphi$ is not satisfiable then all choices of $r$ sets from $S$ cover at most $(1-1/e)t$ elements.

Informally, we say that it is NP-hard to approximate Maximum coverage up to $1-1/e$. Why?

A polytime algorithm $A$ for Maximum coverage is a $\theta$ approximation if given an instance $(S,r)$ with optimal value $O$, $A$ outputs a subset of $S$ of size $r$ that covers at least $\theta O$ elements. If there was a polytime $1-1/e+\epsilon$ approximation algorithm for Maximum coverage, for any $\epsilon > 0$, then you could use it to solve 3SAT, as follows:

Given $\varphi$, run $f$ and calculate the instance $(S,r,t)$.
Run $A$ on $(S,r)$, getting a cover which covers $B$ elements.
$\varphi$ is satisfiable iff $B > (1-1/e)t$.

I leave you to figure out why this works.

The approximation ratio $1-1/e$ is achieved by the greedy algorithm, so this result is optimal.


Polygon casting - Removing from mold by rotation

Consider the marked edge of the following object (light gray) in its mold (dark gray) -

Where must $p$ be such that an arbitrary points on the edge will not be pushed against the mold? This figure shows the direction a point on the edge will be moving in when rotated around a point $p$ -

Notice that the point will be moving perpendicular to the line connecting it with $p$. Now recall that in order not to push on the mold, the points of the edge must move in the direction of the inner half-plane defined by the edge. This means that the possible locations for $p$ lie on a half-plane perpendicular to the edge. Here's the half-plane (in green) corresponding to an inner point of the edge -

The half-plane corresponding to the upper vertex of the edge, in this case, is contained in all of the half-planes for inner points, and so a rotation around any point in it moves the entire edge such that it does not push on the mold.

Whether $P$ can be removed with a rotation around $p$, is thus equivalent to whether $p$ is in the common intersection of the half-planes defined by $P$'s edges.


The complexity of a computational problem depends on the exact representation of the input.

One of the go-to examples here is the Knapsack problem. Given $n$ items with (integer) weights $w_1,...,w_n$, and two integers $W,V$, decide whether there exists a subset $S\subseteq [n]$ such that $V\le \sum\limits_{i\in S}w_i\le W$. We know that the problem can be solved in time $O(nW)$ in the word-ram model. This means that assuming $P\neq NP$, knapsack is not NP complete if the input is of size $\Omega(nW)$, hence it is not complete when $W$ is encoded in unary. Thus, when talking about the NP completeness of knapsack, it is important to specify that we're talking about the version where $W$ is encoded in binary, or "binary knapsack" for short.


Mutual information and moment generating functions

The moment generating function $M_X$ is a property of a random variable $X$. It's defined by the expected value of $e^{tX}$ (where $t$ is the argument).

Since the exponential function $e^x = \sum_0^\infty \frac{x^n}{n!}$ contains all natural powers of its argument as a summand, the expected value of a sum is the sum of the expected values ($\mathbb{E}(\sum_i X_i)=\sum_i\mathbb{E}(X_i)$) and the expected value of a natural power of $X$ ($\mathbb{E}(X^n)$) is called it's $n$-th moment, the $n$-th moment is present in the $n$-th summand:

$$M_X(t)=\mathbb{E}(e^{tX})=\sum_{i=0}^\infty \frac{t^i\mathbb{E}(X^i)}{i!} \quad .$$

If you now consider the $k$-times derivative of $M_X$:

$$M_X^{(k)}(t)=\mathbb{E}(e^{tX})=\sum_{i=0}^\infty \frac{\mathbb{E}(X^{i+k})}{i!} \quad ,$$

and use $0$ as an argument, you get
$$M_X^{(k)}(0)=\mathbb{E}(X^k)\quad,$$

so the $k$-th moment was generated.

Now look at the mutual information:

$$I(X,Y) = \sum_{(x,y)}P(X=x,Y=y)\log\left(\frac{P(X=x,Y=y)}{P(X=x)\cdot P(Y=y)}\right) = \mathbb{E}(\mathrm{PMI}(X,Y)), $$

which is the expected value of the pointwise mutual information (it's likely that they actually deal with the continuous case where $I$ and $\mathrm{PMI}$ are defined using integrals and densities, respectively). So mutual information does not have a moment (or moment generating function), but it is the first moment of a random variable, so:

$$I(X,Y) = M_{\mathrm{PMI}(X,Y)}'(0)\quad.$$


Dynamic Programming - Thief Variation Probem

For $i=1,\dots,N$, and $r \in \{S,R,B\}$
define $OPT[i,r]$ as
the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:

If $x=S$  (as in Skip) then house $i$ must not be robbed.
If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we pretend that house $i+1$ exists even when $i=N$).
If $x=B$ then Both house $i$ and house $i+1$ need to be robbed.

For $i=1$ you have $OPT[1,S] = 0$, $OPT[1,R] = x_1$, $OPT[1,B] = y_1$.

For $i>1$ you have:
$$
OPT[i, S] = \max\{ OPT[i-1, S], OPT[i-1, R] \},
$$
$$
OPT[i, R] = \max\{ x_i + OPT[i-1, S], y_i + OPT[i-1, B] \},
$$
$$
OPT[i, B] = \max\{ y_i + OPT[i-1, S], z_i + OPT[i-1, B] \}.
$$

The optimal profit is then:
$\max\{OPT[N, S], OPT[N, R] \}$ and can be computed in $O(N)$ overall time using the above formulas.


This is definitely possible, although the tensor has of course certain additional structure (constraints).

If you consider the following conditional defined for a categorical response $Y$ on categorical predictors $X_i$:

$P(Y|X_1,\ldots,X_n)$

this correspond to a conditional probability tensor of size $d_0 \cdot d_1 \cdot \ldots \cdot d_n$. Here $Y$ (as a categorical response) takes $d_0$ levels.

Foremost the elements of the tensor have each to be nonnegative.

You can find papers on this, e.g. "Bayesian Conditional Tensor Factorizations for
High-Dimensional Classification" by Yang and Dunson (pdf, arxiv).

Of course, if the random variables concerned are not categorical variables, but either continuous random variables or taking an infinite number of values (or both), the mapping to finite tensors won't be so trivial. You'll need something like an infinite tensor (as an extension of an infinite matrix).


What is uniformity in Boolean circuits exactly?

Here is the binary encoding of 5: $$101$$ And here is its unary encoding: $$11111$$ Hopefully the difference is apparent.
Let's see what happens if we switch to binary encoding in the context of the linked question. Given the binary encoding of $n$, we need to produce a circuit, operating on $n$ bits, in logspace, and so in polynomial time. How much time do we have? The binary encoding of $n$ has length roughly $\log n$, so we have time $O(\log^C n)$, which isn't enough to produce a circuit which reads all input bits.
In contrast, if we use unary encoding, then the length of the input is $n$, and so we have time $O(n^C)$, which is more reasonable (in addition, we are only allowed to use $O(\log n)$ space).