Provide some help regarding the "Dining Philosophers Problem"?

Righties: will never try to acquire the left fork before they have the right one.

Lefties: will never try to acquire the right fork before they have the left one.

Deadlock: Assume that you reached deadlock, this means that none of the philosophers can eat (so each philosopher holds at most one fork, and cannot pick up the other one). Sine you have both righties and lefties, there exists two adjacent philosophers with opposite orientation, lets denote them by $p_r,p_l$.
Notice that $p_r,p_l$ cannot pick up any forks, if one of them holds the fork in between, $f_{p_r,p_l}$ , then it means he already got the other fork, since $f_{p_r,p_l}$ lies right to the leftie $p_l$ and left to the rightie $p_r$. So $f_{p_r,p_l}$ is available, and thus if $p_r$ or $p_l$ can pick up the other fork, they can pick up $f_{p_r,p_l}$ and eat, contradicting deadlock. $p_l$ cannot pick up the fork to his left, hence (because the system is in deadlock) the philosopher left to $p_l$ is a rightie, and already picked up the fork to his right (or to $p_l$'s left). Let us denote the $k'th$ neighbor to $p_l$ from the left by $p_l^k$, so we have shown $p_l^1$ is a rightie and owns the fork to his right. $p_l^2$ (left neighbor of $p_l^1$) must also be a rightie and own his right fork, otherwise either he or $p_l^1$ can eat. It is easy to see (by induction) that for all $k$, $p_l^k$ is a rightie owning his right hand fork. however $p_r=p_l^{n-1}$ (where $n$ is the number of philosophers), so $p_r$ is a rightie owning his right fork, contradicting the fact that $p_r,p_l$ do not own any forks.

This is illustrated in the following figure. Red squares are forks, arrow from a philosopher to a fork indicates that he is waiting to use this fork (not ownership). All philosophers left of $p_l$ are righties waiting to use their left fork (already owning their right one). This goes on until you reach $p_r$, who you know is waiting for his right fork and not the left one (which leads to contradiction).

Starvation: Starvation means that there exists a philosopher which is stuck waiting to eat. Suppose that some right hand philosopher $p_r$ is stuck waiting to pick up his right fork (the proof is very similar in case he's waiting for his left). Let us denote by $p_r^k$ the k'th neighbor of $p_r$ to the right. We know that the protocol is deadlock free, so there exists minimal $m$ such that $p_r^m$ is eating. We can see by induction that all $p_r^{j}$  for $j<m$ are lefties holding their left fork. This is clear for $p_r^1$ (otherwise $p_r^1$ would be either eating or leaving the fork right of $p_r$ available, in any case $p_r$ will eventually be able to pick up the fork to his right). Suppose $j,j+1<m$ and $p_r^j$ is a leftie holding his left fork. Since both $p_r^j,p_r^{j+1}$ are not eating (by minimality of $m$), $p_r^{j+1}$ is a leftie holding his left fork. When $p_r^m$ is done eating, $p_r^{m-1}$ will be able to pick his right fork and eat, when he's done $p_r^{m-2}$ will be able to pick his right fork and eat,... Finally, $p_r^1$ will be done eating, allowing $p_r$ to pick his right fork, contradicting the fact that he is stuck.


Space complexity analysis of binary recursive sum algorithm

In a given tree, all the vertices of this tree correspond to binarySum() calls.
The value of parameter n to binarySum() is halved at each recursive call.
Also, each recursive call finishes after all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence.
Thus when any binarySum() call corresponding to leaves in above call tree is active, its parent, grandparent and so on are still active as well.
Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, which is always equal to the height of the recursive calls tree is 1 + log$_2$n.
For example in binarySum() recursive calls tree above, with n = 8, at any of the calls correspnding to leaves,

Why does the depth of recursion affect the space, required by an algorithm? Each recursive function call usually needs to allocate some additional memory (for temporary data) to process its arguments. At least, each such a call has to store some information about its parent call - just to know where to return after finishing. Let's imagine you are performing a task, and you need to perform a sub-task inside this first task - so you need to remember (or write down on a paper) where you stopped in the first task to be able to continue it after you finish the sub-task. And so on, sub-sub-task inside a sub-task... So, a recursive algorithm will require space O(depth of recursion).

@randomA mentioned the Call Stack, which is normally used when a function invokes another function (including itself). The call stack is the part of the computer memory, where a recursive algorithm allocates its temporary data.


Analysis of a LALR shift-reduce conflict

This conflict arises because when the parser is at the beginning of a line and the lookahead is VAR, it can't tell whether or not to reduce an empty maybe_specifier. In this simple grammar, that decision could be resolved with one more lookahead token, making the grammar LR(2), but that might not be true in the original unsimplified version.

So the conflict is not an artefact of the LALR algorithm, and it is important to fix. (The yacc default resolution "choise shift over reduce" will make it impossible to parse lists which don't start with a SPECIFIER.)

A simple fix is to defer the parsing decision for the first entry in a list:

list:
  VAR
| SPECIFIER VAR
| list maybe_specifier VAR
;

Again, that might or might not be useful in the context of your full grammar.


Who conceived the concept of Discrete Event Simulation, and when?

Cornell's Conway, Johnson and Maxwell's paper Some Problems in Digital Systems Simulation, was published in 1959 in Management Science.  It discusses many of the key points of a discrete event simulation, including managing the event list (they call it an element-clock) and refer to "more efficient but more complicated methods" for locating the next event, but don't discuss the heap data structure.  This paper refers to earlier publications, but they don't seem to discuss the specifics of a discrete-event simulation like this paper does.


How to count number of 1s of the first k positions in a bitset (bitmap)?

Popcount is going to be your best option here. As j_random_hacker mentions in a comment, popcount on a single word can be done in $O(\log W)$ time if implemented by hand, or $O(1)$ if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again, $W$ should also be a constant for any given machine).

(Note: if $b$ is longer than a single word, then you can just use popcount directly on the first $\lfloor \frac{k}{W} \rfloor$ words, and ignore the last however many others, in $O(\frac{k}{W})$. It's only the one word in the middle that you need any fancy algorithm for. So I'm going to be solving the special case where $k < W$. If this isn't the case, which it normally won't be, then replace $k$ with $k \bmod W$.)

The part that depends on $k$ is getting rid of the $W-k$ unneeded bits. One way to do this is masking: generate a mask of $k$ ones, then AND your value with it. (You can generate such a mask by starting with 1, left-shifting $k$ times, then subtracting 1 and taking the complement. Or you can start with only the highest bit set and arithmetic-right-shift $k$ times.)

Another way is to just push the unneeded bits off the end of the word: logical-right-shift your number $W-k$ times and the unwanted bits will be gone.

Which of these is most efficient depends on the specifics of your machine. If it can do bitwise operations and variable shifts in a constant number of clock cycles, then the whole thing is still $O(1)$. If it can't do variable shifts, then it takes $O(k)$; if it can't do constant-time bitwise operations, then there's no way to get better than $O(W)$.


Height of AVL tree with balance condition of 2

Let $T_h$ denote the minimal number of nodes that a standard AVL tree of height $h$ could have.
If $h>0$, then there's the root and two subtrees. One of the subtrees must have height $h-1$. The other must have height at least $h-2$, otherwise it's not a valid AVL tree. So we have the recurrence:
$$T_h = T_{h-1} + T_{h-2} + 1$$
And we can throw in $T_0 = 0$ and $T_1 = 1$ for obvious reasons.
The easy way to solve the recurrence is to denote $F_h = T_h + 1$. Then:
$$\begin{align*}F_0 & = 1 \\ F_1 & = 2 \\ F_h & = F_{h-1} + F_{h-2}\end{align*}$$
That is, they're Fibonacci numbers with the sequence offset by 3.
Since:
$$F_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$
Inverting this, we get:
$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T_h \right) + 3$$
And that is where the 1.44 comes from.
So what you need is to solve the recurrence:
$$U_h = U_{h-1} + U_{h-3} + 1$$
with suitable initial conditions.
If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:
$$\begin{bmatrix} U_h \\ U_{h-1} \\ U_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix} U_{h-1} \\ U_{h-2} \\ U_{h-3} \\ 1\end{bmatrix}$$
Therefore:
$$\begin{bmatrix} U_{h+2} \\ U_{h+1} \\ U_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}^{h} \begin{bmatrix} U_{2} \\ U_{1} \\ U_{0} \\ 1\end{bmatrix}$$
Next, perform eigendecomposition on the matrix. Let:
$$M = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$
Suppose you can find a matrix $Q$ and a diagonal matrix $\Lambda$ such that $M = Q \Lambda Q^{-1}$. Then:
$$M^h = Q \Lambda^h Q^{-1}$$
Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.


Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial number of items in the tree and $k$ is the number of items deleted (and returned to the caller). Full disclosure: I am the author.

I have to emphasize that the data structure does not support the insert operation, but is optimized for clone and delete_range. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.


Big O of rational function using the definition

Rewrite $\frac{3x^3+2x^2+x+1}{4x^2+1} = \frac{3}{4}x \cdot \frac{12x^3+8x^2+4x+4}{12x^3+3x} = \frac{3}{4}x (1 + \frac{8x^2+x+4}{12x^3+3x})$.

Clearly, the limit of $f(x) = \frac{8x^2+x+4}{12x^3+3x}$ for $x \to +\infty$ is $0$ and hence, for any constant $c'>0$, there is a constant $x'_0$ such that $f(x) \le c'$ for all $x \ge x'_0$. Pick your favorite constant $c'$, for example $c'=1$. You want to figure out any value of $x'_0$ for which $f(x) \le 1$ or, equivalently:

$$
12x^3+2x - 4 \ge 8x^2.
$$

This is clearly true for $x'_0=1$. Indeed, if $x \ge 1$:
$$
12x^3+2x - 4 > 12x^2 - 4 \ge 8x^2 + 4x^2 - 4 \ge 8x^2.
$$

Going back to the original formula we can conclude that, for every $x \ge 1$,
$$
 \frac{3}{4} x \cdot \left(1 + \frac{8x^2+x+4}{12x^3+3x} \right)
\le \frac{3}{4} x \cdot (1 + 1)
= \frac{3}{2} x.
$$

Which satisfies the definition of $O(x)$ once you pick $c = \frac{3}{2}$ and $x_0=1$.


Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon > 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$.
This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$.
In other words you want $\frac{g(n)}{f(n)}$ to  grow at least as fast as some polynomial/root of $n$.
In your particular case, $n \log n$ is indeed polynomially smaller than $n^{1.46}$, and this follow from the fact that $n \log n \in O(n^\alpha)$ for any $\alpha >1$.
A a concrete choice of $\varepsilon$, you can pick $\varepsilon=0.1$ yielding $n \log n \in O(n^{1.46-0.1}) = O(n^{1.36})$.
To see this you can consider the limit:
$$
\lim_{n \to \infty} \frac{n \log n}{n^{1.36}} =
\lim_{n \to \infty} \frac{\log n}{n^{0.36}}  =
\lim_{n \to \infty} \frac{1}{0.36 \cdot n^{0.36}} = 0,
$$
where we used L'Hôpital's rule.
In the above, the choice $\varepsilon = 0.1$ was just a convenient value that works, but any choice of $\varepsilon \in (0, 0.46)$ suffices.


Is it possible to repeat a wildcard in regex?

Using backreferences you can accept non-regular languages such as the language of squares $ww$, which is accepted by (.*)\1. This language cannot be represented as a non-extended regular expression at all.


Constructing all context-free languages from a set of base languages and closure properties?

That is possible, but perhaps not exactly in the way you ask. As a start take the Dyck language $D_2$ of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$, or more abstractly $a_1,b_1,a_2,b_2$.

Then every context-free language can be obtained from $D_2$ using homomorphisms, inverse homomorphisms and intersection with regular languages. The context-free languages are called "the principal cone generated by $D_2$", in old books denoted $\mathcal{M}(D_2)$. See a related question: "Which languages are recognized by one-counter machines?"

In fact, we need only one of each operations (well-chosen). Each CFL can be written $g(h^{-1}(D_2) \cap R)$, where $g$, $h$ are homomorphisms, and $R$ is a regular language. Intuitively, $R$ is a program of a PDA, $g$ maps each instruction to the letter read, $h$ to the push and pop operations of the stack. Finally $D_2$ codes proper stack behaviour.

This result is related to the Chomsky–Schützenberger Theorem (or as can be seen in wikipedia, one of them). The statement linked here in wikipedia (a) does not need an inverse homomorphism, while (b) it does not restrict to two pairs of brackets.
Theorems of this type are from the area of "Abstract Families of Automata", where Ginsburg and Greibach are important names. A related result by Nivat states that operations of the form $L \mapsto g(h^{-1}(L) \cap R)$ for fixed $g,h,R$ are the finite state transductions.


From the result of $k$-sorting an array you can tell which elements of the original array were the $n/k$ smallest, the $n/k$ largest, and which belong to each of the other $k-2$ blocks of $n/k$ elements in between. In particular, there are at least $\binom{n}{n/k,\ldots,n/k}$ different leaves, which works out to $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$. This gives you the correct lower bound.

What you calculated is the number of different ways to completely sorted a $k$-sorted permutation. Therefore your lower bound is for sorting a $k$-sorted permutation, and for this task your lower bound is tight: a $k$-sorted permutation can be sorted in $O(n\log (n/k))$.


Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$

You should really be asking a third question: what happens if $n$ isn't a perfect square. The answer to this question is that the actual recurrence should have $T(\lfloor \sqrt{n} \rfloor)$ or $T(\lceil \sqrt{n} \rceil)$ instead of $T(\sqrt{n})$, though in the analysis we will only consider inputs which are "recursive" squares.

Regarding your first question, there can be more than one base case. For example, perhaps $T(n) = 1$ for all $n \leq 100$. You are guaranteed to eventually hit this base case. In this case, as in most cases, the exact form of the base case doesn't affect the big Theta asymptotics (but it does affect the hidden constant).

Finally, regarding your second question, suppose that your base case specifies $T(n)$ for $n \leq C$. The recursion tree (which is a particular interpretation of some features of the recurrence) has the following form:

The root is one instance of size $n$.
The root has $\sqrt{n}$ children which are instances of size $\sqrt{n}$.
Each node at depth 1 has $\sqrt{\sqrt{n}} = n^{1/4}$ children which are instances of size $\sqrt{\sqrt{n}} = n^{1/8}$.
More generally, a node at depth $d$ is an instance of size $n^{1/2^d}$. You can prove this by induction by checking the case $d = 0$ (where $n^{1/2^d} = n$) and calculating $\sqrt{n^{1/2^d}} = n^{1/2^{d+1}}$.

The recursion terminates when the instance has size at most $C$, and this happens when $n^{1/2^d} \leq C$. At the point that this happens, we have $n^{1/2^{d-1}} > C$ (assuming $n > C$), and so $\sqrt{C} < n^{1/2^d} \leq C$. Taking the logarithm, $\frac{1}{2} \log C < \frac{\log n}{2^d} < \log C$ and so $\frac{\log n}{2^d} = \Theta(1)$, implying $2^d = \Theta(\log n)$. We can conclude that $d \approx \log\log n$. This is the number of layers in the tree. Jeff uses $C = 2$, which is how he gets his particular formula.


How to prove a problem is NOT NP-Complete?

A problem $Q$ is NP-complete if it is both NP-hard and in NP.  This means that you need to disprove one of these two.

Under the assumption that P $\neq$ NP, you can give a polynomial time algorithm solving $Q$.  Rarer, under the assumption that graph isomorphism is not NP-hard, you can show that $Q$ is polytime reducible to graph isomorphism.
You show that $Q$ is not in NP.  This is harder, and you must usually use other assumptions, like non-collapse of polynomial hierarchy, that NP $\neq$ coNP or show that it is hard for some other class higher than NP, e.g. by showing that it is NEXPTIME-hard.

Usually, the answer is to give a polynomial time algorithm, which would be the simplest for DNF-SAT, but this relies on the hypothesis that P $\neq$ NP.  However, proving that DNF-SAT is not NP-complete without any assumptions implies, as Shaull points out, proving that P $\neq$ NP, so that is somewhat trickier.


A path from the last node to the leaf would always be a longest path. This is because the last node is always at the lowest level in the heap. Now, assume the root is at level $0$. Then the number of nodes at a completely filled level $i$ would be $d^i$.

Let level $k$ be the last completely filled level in the heap. So the number of nodes upto (and including) level $k$ is: $$\sum\limits_{i = 0}^{k}d^i = \frac{d^{k+1} - 1}{d - 1}$$

Now, the last node - the $n^{th}$ node - can either be the last node at level $k$, or it can be in an incomplete level $k+1$. Taking care of these two cases, it can be seen that:
$$\frac{d^{k+1} - 1}{d - 1} \le n < \frac{d^{k+2} - 1}{d - 1}$$
$$\Rightarrow k\le \log_d(n(d-1) + 1) - 1 < k+1$$

Now, equality is only if the last node is the last leaf of level $k$, which also has distance $k$ from the root. If not, that is if there is a level $k+1$, then the $\log$ term would not be an integer, and applying the ceiling operator would give the right height of $k+1$. Thus, if the last element of the array is at position $n$, the height of the heap is:
$$h = \lceil \log_d(nd - n + 1) \rceil - 1$$
You can change the base of the logarithm using the change of base formula. Note that this is the same method that Yuval gives in his answer.


DFS timestamps, how important are they in pathfinding?

Correct.  If you just want to check which nodes are reachable, or find any path from $s$ to $t$, you don't need the timestamps (the pre and post values).


This is just the assignment problem: you need to find a maximum-weight matching between the users and frequencies.  The Hungarian algorithm solves this in time $O(n^3)$.


Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions?

System calls could be done, and have been done, with normal (normal enough) call instructions. However, the operation wouldn't be a normal call: the privilege level changes, and it is unsafe to allow calling arbitrary offsets (which might not be the entrypoint of a subroutine) with a lot of privileges. So there should be some mechanism that both limits the possible destinations and changes the privilege level. That mechanism is similar in function to how a dedicates system call instruction would work, but it could be triggered by a normal subroutine call instead.
Call gates on x86 are an example of that, a mechanism that allows system calls to some locations that have been set up in advance, by using relatively normal far calls. 32bit code does not normally use far calls though, so it's not really the same thing as a completely standard subroutine call. Far calls were more usual in the 16bit era, and the 80286 which introduced call gates was still a 16bit processor, but it seems that call gates did not see much use on the 80286. Similar mechanisms existed on some other old processors.


The Complexity Zoo has a pronunciation guide by Scott Aaronson "for those who insist on communicating verbally about complexity." It recommends the "p slash polly" option.


Solving consensus for a known number of processes

I was wrong the object has an infinite binary consensus number.

if (input = 0) test-and-reset(obj)
prev = fetch-and-add(obj, 2)
if (prev mod 2 = 0)
    decide(0)
else
    decide(1)


Ford-Fulkerson Algorithm not "pushing back" flow

No, it is not true that "the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges". If you look at the wiki article of Ford and Fulkerson method you will see the following pseudocode:

Algorithm Ford–Fulkerson
Inputs: Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
Output: Compute a flow $f$ from $s$ to $t$ of maximum value

$f(u,v) \leftarrow 0$ for all edges $(u,v)$
While there is a path $p$ from $s$ to $t$ in $G_f$, such that $c_f(u,v) > 0$
  for all edges $(u,v) \in p$:
    Find $c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}$
    for each edge $(u,v) \in p$
      $f(u,v) \leftarrow f(u,v) + c_f(p)$ (Send flow along the path)
      $f(v,u) \leftarrow f(v,u) - c_f(p)$ (The flow might be   "returned" later)

In the last line $f(v,u)$ is clearly decremented.

In the example below one will have to decrease flow in the middle edge to get max-flow. There is no other way.

If you want to know, if there exist a sequence of augmenting paths that never decrease the flows, then the answer is possibly yes. Proof might be non-trivial though.


Nested Loop Time Complexity vs Successive Loops

I think that the first algorithms running time is actually $\mathcal{O}(x^4)$.

The outer for loop executes exactly $x$ times,
the inner for loop executes at most $x$ times during every one of these $x$ iterations of the outer loop

In fact, the inner loop executes exactly $\frac{x(x+1)}{2}$ times, and $\frac{x(x+1)}{2} = \frac{x^2 + x}{2} = \mathcal{O}(x^2)$, since our asymptotic notation allows us to essentially ignore the constant factors.

So already we have a growing complexity of $\mathcal{O}(x^2)$. If we now consider the contents of the inner for loop, which you say is a quadratic time calculation of $x$. I read this as follows: the complexity of the inner loops body is a quadratic function of x $\rightarrow \mathcal{O}(x^2)$. My answer is based largely upon this assumption.

If my assumption is correct, then a time complexity of $\mathcal{O}(x^4)$ easily follows from this reasoning: the outer and inner for loop collectively produce $\mathcal{O}(x^2)$ iterations of some algorithm that takes $\mathcal{O}(x^2)$ steps to complete itself. An extremely informal (read: not quite right, but right enough to demonstrate a point) mathematical argument for this might be:

($x$ outer loop iterations) $\cdot$ ($x$ inner loop iterations) $\cdot$ ($x^2$ loop body steps) $= x^4$ total steps.

With the second algorithm, the same reasoning can be used. Again, we have some procedure, which takes $\mathcal{O}(x^2)$ steps to run, which is being executed $x$ times. This gives us $\mathcal{O}(x^3)$ steps in total. Since we have two loops of this form, we can conclude that algorithm 2 has a time complexity of:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3)$

Note that in this case we have two consecutive loops that, asymptotically speaking, do essentially the same amount of work. In reality it might be that our first loop which calculates $y$ performs some constant factor amount more or less steps than our second, which calculates $z$, but here that doesn't matter, since we're focusing on the rate of growth of our running time. One way of thinking about it is as follows:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3 + x^3) = \mathcal{O}(2 \cdot (x^3)) = \mathcal{O}(x^3)$.

Here we can drop the 2, since its a constant factor.


Does RAM get an indication of data size required

RAM just gets requests for data to move to/from the CPU (really the MMU). Data is moved in units of cache lines.


Finding the similarity between large text files

My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.

Yes, the problem you expose is widely studied in computer science/machine learning and there are dozens of algorithms to do what you are looking for. Depending on the precise specifications of what you are looking for, the complexity of the algorithm may vary.
When I happened to have to perform this computation, I personally used the TF-IDF approach.

As I said it depends a lot on what you want to achieve and even a minimum change in the initial specifications can lead to a drastic change in the algorithm. You could also take a look at this link.


Is it possible to solve the critical section problem with an atomic subtract operation?

If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing test-and-test-and-set operation with atomic-fetch-and-decrement.

So, for example, if you have 32-bit integers and less than 4 billion threads the following should work:

initialize: x = 0

acquireLock:
  repeat:
    while x != 0:
      # do nothing
    tmp = atomicFetchAndDecrement(x) # (decrements x and returns *new* value of x)
  until tmp == -1

releaseLock:
  x = 0

Each thread only decrements the counter once for each time that it sees the counter get reset to 0, so the value of x never becomes smaller than -numberOfThreads.

The real value of fetch-and-increment is that you can make critical sections that are "fair" in the sense that threads are given the lock in the order in which they first request it.  Like this:

initialize: nextTicket = 0; current = 0

acquireLock:
  myTicket = atomicFetchAndDecrement(nextTicket)       # (decrements and then returns *new* value)
  myTicket = myTicket + 1                # make up for the weird atomicFetchAndDecrement semantics
  while current != myTicket:
    # do nothing

releaseLock:
  current = current - 1                  # does not need to be atomic, releaser is only writer

Again, with 32-bit integers this works as long as the number of threads is less than $2^{32}$.


why are deterministic PDAs not closed under concatenation?

Pick the languages:

$L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too.

$L_0 = 0^*$ is DCFL (regular)

But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL.

Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

If we intersect $L_{conc}$ with the regular language $0a^*b^*c^*$, we should get a DCFL language:

$L_{conc} \cap \{0a^*b^*c^*\}$ = $0L_1 \cup 0L_2$. suppose $0L_1 \cup 0L_2$ is a DCFL, so $L_1 \cup L_2$ should be a DCFL, too but:

$L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}} = \overline{\{a^ib^ic^i\}}$ which is not DCFL $\Rightarrow$ contradiction.


Is it theoretically possible to dynamically grow array size in stack memory?

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication.

First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your existing array elements down to the new array position every time you enlarge the array.

After that, it is really a linguistic question. In assembler you can obviously do it, because you can do anything in assembler. Whenever you want your array to be n bytes bigger, just subtract n from the stack pointer.

In C there is often a function - disapproved of by all respectable computer scientists and therefore very useful when it is useful - called alloca or _alloca - which allocates n bytes of data on the stack and returns a pointer to the new allocation. I would be very surprised if two consecutive alloca calls did not just allocate contiguous stack space, so although there isn't a realloca function, you could effectively simulate its behaviour.

Where life gets interesting is when the compiler decides to use the stack for its own purposes: for instance, it might precompute the arguments for several function calls and push them all onto the stack before calling any of the functions. Usually such compilers notice a call to alloca and disable optimisations in the function that uses it - this is one of the reasons for disapproving of alloca.

The main difficulty you would run into would be that, if you wanted your array indices to be "the right way up" - a[0], a[1], a[2] and so on - then every reallocation would require data to be moved, which is a bore. And you can't write your own function in C to do this (that is, both the extra stack allocation and the data movement) because when you call a function, you usually push a return address onto the stack, so the stack-based array is (as you showed in your pictures) blocked by that extra piece of data and can't be enlarged. You would have to write a special realloca function in assembler which pops the return address and keeps it safe; subtracts an appropriate amount from the stack pointer; pushes the return address again; and then does the necessary memory movement. It would actually be quite fun to implement, though not at all portable because different systems will use the stack in different ways in a function call.

Is it used? Yes, I have used alloca for things I know to be small, because I love not having to rampage all over the heap and I love not having to deallocate. But your more elaborate scheme - I haven't heard of anyone who has done it.

Except in assembler - where one can do a beautiful merge sort by using the stack to store data.


The simplest approach is to formulate this  as an instance of integer lienar programming.  You have zero-or-one variables $x_{i,j}$, where $x_{i,j}=1$ means that item $i$ is placed into knapsack $j$.  Then all of your constraints can be straightforwardly expressed as linear inequalities on these variables.


Skolemization with multiple arguments -- how to unify

"Everyone has a heart" gets first encoded first as $\forall x. \text{Person}(x) \Rightarrow \exists y. \text{Hart}(y) \wedge \text{Has}(x,y)$. Then you get the Skolemization (that you found in RN) from that.

Now "Everybody who has a house pays utilities" is just $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ because there is no assertion that anything exists in this statement. However, if you want to spell out what houseowner means, $\forall x.\text{Houseowner}(x) \Leftrightarrow (\text{Person}(x)\wedge\exists y.\text{House}(y) \wedge Has(x,y))$. And you can skolemize that... but it's not even needed for what you want to infer.

As to "Jane and Mark have a house", it's actually a bit ambiguous. Do they have the same house? But that's an irrelevant detail if you just encode $\text{Houseower}(\text{Jane}) \wedge \text{Houseower}(\text{Mark})$. From that it immediately follows that $\text{Houseower}(\text{Jane})$ and using $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ it follows that $\text{PaysUtilities}(\text{Jane})$ with the obvious unification $x=\text{Jane}$.

As you can see, the definition of houseowner (which asserts the existence of a house etc.) is completely irrelevant to the inference you wanted. In general, not every "has" in the English language gets translated into a binary predicate, unless it's relevant to what you want to prove. Nobody managed to invent a rigorous way to formally and universally translate all of English (or any other natural language) into first-order logic. While there are some guidelines, a translation of a problem statement from natural language to FO ultimately uses a problem-specific encoding method.

Also note that your first sentence "Everybody who has a house pays utilities" bears some resemblance to a donkey sentence, but it's not actually one; you'd have to say "Everybody who has a house pays utilities on it" to get a donkey sentence.


For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE"

The error is in this paragraph:

  We know $\varphi \notin \mathsf{3SAT}$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $$ containing all true literals, then if $()$ adds $=$ to each clause, wouldn't $()$ belong to $\mathsf{4NAE}$?

Here's your argument, broken into steps:

Suppose $\varphi \notin \mathsf{3SAT}$. Thus, every assignment for $\varphi$ has at least one falsified clause.
Suppose there was some assignment in which each clause contains a falsified literal. Then $f(\varphi) \in \mathsf{4NAE}$, by choosing $z=T$.

I fail to see the contradiction here. Indeed, if there is some assignment in which each clause contains a falsified literal, then if you complement it, you get a satisfying assignment, as you show in your post. This means that if (1) holds, then (2) cannot possibly hold.

You argument is basically saying "what if I had an unsatisfiable $\varphi$ together with an assignment in which each clause contains a falsified literal". If such a $\varphi$ existed, then your reduction wouldn't have been sound. Fortunately, no such $\varphi$ exists. It's true that you have to rule out the existence of such $\varphi$, which you do by showing that if (2) holds then (1) doesn't hold.


how can i know if a First order logic sentences is valid or unsatisfiable or neither?

A formula is valid if all of the possible truth-assignments to its variables evaluate to true.

A formula is satisfiable if at least one of the truth-assignments to its variables evaluates to true.

The formula you gave is :

  $1 = 2$

Since this contains no variables, under any truth-assignment, the expression is $1 = 2$, which is false.

Neither of the above conditions have been met.

Therefore the formula is neither valid nor satisfiable. Since it is not satisfiable, we can say that it is unsatisfiable.


Why minimum vertex cover problem is in NP

You don't have to verify that $V'$ is minimum.
The decision version of Vertex Cover (which you have quoted in your question) only asks you to decide whether there is a vertex cover of size at most $k$.
To verify that $V'$ is a valid yes-certificate for an instance $\langle G=(V,E), k \rangle$ you just check that:

$V' \subseteq V$,
$|V'| \le k$, and
$\forall (u,v) \in E, \{u,v\} \cap V' \neq \emptyset$.


There are dozens and dozens of stack machines out there in the wild, and they all have different instruction sets. So there's no single correct answer.

Some people might consider using CALL like that cheating: after all, it relies on things like ADD and CMP and JMP and DUP and such all being implemented in the machine, so why don't you call them instructions? But if you're going that route, you can get rid of POP too, and implement that with CALL. The only reason you can't get rid of PUSH too is you need some way to get opcodes and arguments onto the stack.

If you don't want to use CALL like that, the minimum for Turing-completeness would be something like PUSH, ROT (rotate the stack in some controllable way), DUP (duplicate the top of the stack), CMP (compare two values), JMP (some sort of conditional GOTO), and SUB (subtract one number from another). An actually useful machine would have more, things like ADD and AND and such.


Why is the carry of any n base system equal to the radix in arithmetic?

Background
Writing a number in base $r$ means to write it in the form
$$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$
where $0\leq a_i< r$, for all $i=0,1,\ldots,n$. The positional notation that we use consists in just writing the digits $a_i$ from right to left
$$(a_na_{n-1}\ldots a_2a_1a_0)_r$$
Some people write parentheses and maybe the radix as a subscript. Some people write a bar over the digits, and in the decimal positional system, which is the most popular, we just write the digits.
You can think of the digits as buckets that can only be filled up to the value $r-1$.
The carry actually depends on the position of the digit, only that when you compute you imagine that it is the degree zero position, the units. Actually, when you are inside algorithms like adding or converting numbers from one radix to another in each iteration you have already divided enough by $r$ such that the digit that you are treating has become the degree zero position or you are treating it as such.
The carry at the $k$-th position
For example, suppose that you are looking at position $k$ and the digits at that position and the one that follows are
$$a_kr^k+a_{k+1}r^{k+1}$$
You can divide by $r^k$ to get $a_k+a_{k+1}r$, which implicitly is what happened if we just write the two digits $(a_ka_{k+1})_r$.
Now, the maximum carry will happen when $a_k$ is as full as it can be and we add to it the maximum digit that we can add. This is $a_k=r-1$ and we add $r-1$. Then we get
$$\begin{align}
(a_k+a_{k+1}r)+(r-1)&=(r-1)+a_{k+1}r+(r-1)\\
&=(r-2)+\mathbf{r}+a_{k+1}r\\
&=(r-2)+(a_{k+1}+1)r
\end{align}$$
As you can see, it is $\mathbf{r}$ the amount that we have to move out of the $k$-th position to re-write the number as a sum of powers of $r$ in which the coefficients are all between $0$ and $r-1$. Well, it is really $r\cdot r^k$, because we divided by $r^k$. In terms of the contribution to the next ($k+1$-th) digit the carry contributes $1$, when carry over happens. Otherwise it contributes $0$ to the next digit.
Potentially, $a_{k+1}+1$ is larger than $r-1$, so $(a_{k+1}+1)r$ will have to spit out an $r^2$ (actually $r^2\cdot r^k$), but well that's the carry generated by the $(k+1)$-th position.


Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that
$$
\sum_{i<j} d(i,j) = 87.
$$
Hence the average distance is
$$
\frac{1}{6^2} \sum_{i,j=1}^6 d(i,j) = \frac{1}{36} \left(\sum_{i<j} d(i,j) + \sum_{i>j} d(i,j) + \sum_{i=j} d(i,j)\right) = \frac{2\cdot 87}{36} = \frac{29}{6}.
$$

A simple way to do the calculation is as follows. Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is
$$
\frac{2}{n^2} \sum_e w_e k_e (n-k_e).
$$
For example, in our case we get
$$
\frac{2}{36} (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) = \frac{29}{6}.
$$


Minimum length of string using chars appearing in a given string but not a substring of that string

$O(n \log_m n)$ solution, using a trie and a length cutoff

Relevant wikipedia articles: De Bruijn sequence, Trie

With an alphabet size of $m$, there are $m^t$ substrings of length $t$ that need to appear in a string in order to push the minimum missing substring length (our output) past $t$. But each character we add to a string can only eliminate one additional substring of length $t$. If our string is shorter than $m^t$, we know there must be a missing string of length $t$. This gives a bound on the length of the substrings we need to search in terms of the input string's size.

We know the input size $n$ and we know the alphabet size $m$, but we don't know our output value $t$. However, we know that $t$ must satisfy $m^t \leq n$. Re-arranging, we find that $t \leq \log_m n$. So we can use $t_{\text{cutoff}} = \lceil\log_m n\rceil$.

To make it easy to look for missing strings, we're going to insert every substring, up to the cutoff length, into a trie:

def buildTrie(text, cutoff):
    root = TrieNode()
    trail = [root]
    for c in text:
        newTrail = [root]
        for t in trail:
            t[c] = t[c] or TrieNode()
            newTrail.add(t[c])
        trail = newTrail[:min(len(newTrail), cutoff - 1)]
    return root

The above function takes $O(\text{len}(\text{text}) \cdot \text{cutoff})$ time to finish, which in our case is $O(n \log_m n)$.

With our truncated trie in hand, we search through it for holes corresponding to missing substrings:

def firstLevelWithHole(trieNode, alphabet):
    if trieNode is None: return 0
    return 1 + min(firstLevelWithHole(trieNode[c], alphabet) for c in alphabet)

This search scans the whole trie. However, because the trie is cutoff at level $\log_m n$ and has fan-out at most $m$, we've done only $O(m^{\log_m n}) = O(n)$ work.

So our overall algorithm is:

def minMissingStringLength(text):
    alphabet = new Set(text)
    if len(alphabet) <= 1: return len(text) + 1
    cutoff = math.ceil(math.log(len(text), len(alphabet)))
    trie = buildTrie(text, cutoff)
    return firstLevelWithHole(trie);

And it takes $O(n \log_m n)$ time and $O(n)$ space.

Notes

The algorithm is easily tweaked to return a specific missing substring, instead of just the length.
It's probably possible to reduce this to $O(n t)$ time by creating the trie in short-substring-first order, and scanning for holes before starting the next level.
For truly huge alphabets, the dictionary lookups start costing $O(\lg m)$. I've omitted this cost from the analysis. Also you would want to modify the hole-finding to short-circuit instead of evaluating the whole tree, because it could add an $\Omega(m)$ cost otherwise.


DFA and equivalence classes: counting odd numbers of b's

Your first and third equivalence classes are equivalent to one another. They both contain strings in which there are an even number of $b$s: in the first class, that number is zero; in the third class, it's at least two.  For any string in either of those classes, adding a string with an odd number of $b$s gives a string in the language, and adding a string with an even number gives a string not in it.


Construct a graph in which the vertices are all cells not marked 'b', and in which two vertices are connected if they are adjacent in the matrix. Use BFS from the 'a' vertex to go over all vertices in order of distance from 'a', until you find the first 'c' vertex. The overall complexity is $O(MN)$.


Is there a model of ZF¬C where some program always terminates but has no loop variant?

I think you are really asking a question about the definition of the notion of well-foundedness.

I think the notion of loop variants is a bit of a red herring here: I would argue that any reasonable definition of well-foundedness should enable proving that a loop is terminating iff there is a well-founded relation which acts as a variant for it, almost as a tautology.

The issue is that the classical definition of a well-founded order $<$ on $X$:

  There are no infinite sequences $x_1>x_2>x_3>\ldots$

is not a very nice definition, either from a constructive standpoint or when one is uncomfortable with the use of the axiom of (dependent, thanks Andrej!) choice. Assuming the latter, this definition is equivalent to the much nicer definition:

  Every non-empty subset $P\subseteq X$ has a minimal element, that is, some $x\in P$ such that $y \not< x$ for every $y\in P$.

This definition is already much nicer, and I think it can be used to prove the variant lemma without choice.

Finally, the constructive version of well-foundedness is this:

  For every $P\subseteq X$, if for every $x\in X$, $\{\ y\ |\ y < x\ \}\subseteq P$ implies $x\in P$, then $P = X$.

This definition seems more unwieldy, but it is actually the one you want: it enables induction over well-founded orders, without using either choice or excluded middle. Assuming excluded middle, it is equivalent to the previous one.

Finally, the business in the wikipedia article about ordinals is not really necessary for any technical analysis of termination, and, in addition, choice is not required if you define $\omega_1$ to be the order type of the set of countable ordinals (ordered by the prefix relation).


Is queue a storage allocation area in memory?

You've been misled by homonyms.

There is a data structure called stack: a container where items can be added at any time but only the most recently added can be removed. And there is an area in memory called stack, which is where function arguments, local variables, return values and return addresses are stored¹. There's one stack memory area per thread. The two concepts have the same name because the stack memory area is organized as a stack data structure: an item is added when a function call is executed, and it is removed upon return from a function; since function calls are nested, the item that's removed is the last one that was added and not yet removed.

There is a data structure called heap: a tree of ordered items where each node holds a smaller value than all of its children². And there is an area in memory called heap, which is where storage is allocated dynamically. There is one heap per process. The two concepts are completely unrelated, they have the same name because there's a finite supply of English words with roughly the right connotations and it happens that the same word was picked for both.

There is no reason why a word that is a name for a data structure should also be a name for an area in memory. There can be queue data structures in an operating system, of course, but there's no area in memory that's called “the queue”.

Process control blocks are not organized as a queue, and they are not a storage allocation area, they're just a common name for the place in memory where the operating system stores information about each process (and not every operating system has all the information in one place, so not every OS's description mentions a “process control block”).

¹  This is just the 10000-foot view. Return addresses and arguments could be placed in different areas, some arguments typically end up in registers, etc.
²  That's a min-heap; a max-heap is a tree where each node holds a larger value than all of its children.


If a language is not Turing reducible to two languages, may it still be Turing reducible to their "union"?

A classical theorem of Sacks states that if $L$ is not computable, then it is almost surely not computable relative to a random oracle. In other words, if $O$ is a random oracle, then the probability that $L$ is computable given $O$ is zero.

Now take your favorite uncomputable $L$, and choose $L_1,L_2$ at random among all languages such that $L = L_1 \Delta L_2$ (here $\Delta$ is symmetric difference). Individually, $L_1,L_2$ are random oracles, and so almost surely $L$ is not computable given just $L_1$ or just $L_2$. However, it is clearly computable given both.

Another solution is to take any two incomparable Turing degrees $L_1,L_2$ and $L = \{ 0x : x \in L_1 \} \cup \{ 1x : x \in L_2 \}$. The proof then follows practically by definition.


Minimum spanning tree of multi directed graph

As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).


Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$

The usual definition is that $n_a(w)$ refers to the number of $a$s in $w$.

Based on this definition, $L_1$ consists exactly of words that begin with an even number of $a$s followed by half as many $b$s (no $c$s are permitted). Therefore, you have $\varepsilon, aab, aaaabb, aaaaaabbb,... \in L_1$.

Whereas $L_2$ consists of words containing an even number of $a$s and half as many $b$s (in any order and with an arbitrary number of $c$ in between).

Thus every word in $L_1$ is also in $L_2$ (formally $L_1 \subseteq L_2$), but there are words in $L_2$ that are not in $L_1$:

For some $n \geq 0$, consider words of the form $b^n a^{2n}$. They are in $L_2$, because they contain an even number of $a$s and half as many $b$s, but if $n > 0$, then it does not match $a^{2n} b^n$, because the $a$s come after the $b$s. You have $\varepsilon, baa,bbaaa,bbbaaaaaa,... \in L_2$, but $baa,bbaaa,bbbaaaaaa \notin L_1$.
The same argument applies for $w = (aab)^n$. You have $\varepsilon, aab,aabaab,aabaabaab \in L_2$, but $aabaab,aabaabaab \notin L_1$.
A word can have an even number of $a$s and half as many $b$s and also contain $c$s. For example, $a^{2n} b^n c \in L_2$. But the words in $L_1$ by definition only contain $a$s and $b$s.


No, your reduction is wrong. The function $(\lambda x y z. z y x)$ is applied to three arguments: $a$, $a$ and $(\lambda p q. q)$. It is not, as you wrote, a the function $(\lambda x y z. z y x)$ applied to the term $a a (\lambda p q. q)$; that second term does not appear in $M$. Strictly speaking, functions in the lambda-calculus take three arguments, they are effectively curried, so if you add optional parentheses $M$ can be written
$$
(((\lambda x. (\lambda y. (\lambda z. (z y) x))) a) a) (\lambda p. (\lambda q. q))
$$
This reduces by substituting $a$ for $x$ in $(\lambda y. (\lambda z. (z y) x)))$, then $a$ for $y$ in the result of this:
$$
M \to (\lambda y z. z y a) a (\lambda p q.q) \to (\lambda z. z a a) (\lambda p q. q)
$$
then substitute $(\lambda p q. q)$ for $z$, after which a new redex appears:
$$
\ldots \to (\lambda p. (\lambda q. q)) a a \to (\lambda q. q) a \to a
$$


A $log(k)$ algorithm for the matroid secretary problem

It seems that there is a typo – $v_{i+1} - v_i$ should be $v_i - v_{i+1}$.

Suppose first that all elements are distinct. Then (using the convention $v_0 = 0$)
$$
 \sum_{i=1}^{q-1} (v_i-v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\
 \sum_{i=1}^{q-1} i (v_i-v_{i+1}) + q v_q = \\
 \sum_{i=1}^q i v_i - \sum_{i=2}^q (i-1) v_i = \sum_{i=1}^q v_i.
$$

Consider now the general case, in which we have
$$
v_1 = \cdots = v_{j_1} > v_{j_1+1} = \cdots = v_{j_2} > \cdots,
$$
where $j_r = q$. Then for $j_0 = 0$, $j_{r+1} = j_r+1$, and $v_{q+1} = 0$, we have
$$
 \sum_{i=1}^{q-1} (v_i - v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\
 \sum_{\ell=1}^{r+1} \sum_{t=0}^{j_\ell-1} (v_{j_{\ell-1}+t} - v_{j_{\ell-1}+t+1}) n_{j_{\ell-1}+t}(B^*) = \\
\sum_{\ell=1}^{r+1} (v_{j_{\ell-1}} - v_{j_{\ell-1}+1}) (j_1 + \cdots + j_{\ell-1}) = \\
\sum_{\ell=1}^r v_{j_\ell} j_\ell = \sum_{i=1}^q v_i.
$$
(This calculation might not be 100% correct, but you get the idea.)


In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour.  So, I think you should focus on optimizing time complexity.  A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that node.  This achieves $O(n)$ space, if there are $n$ data points within the past hour, and $O(\log n)$ time per data point that you receive.


If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Triple42   rdf:type        rdf:Statement .
:Triple42   rdf:subject     :Vaccination .
:Triple42   rdf:predicate   voc:canLeadTo .
:Triple42   rdf:object      :Autism .
:Triple42   voc:publishedIn <https://example.com/articles/vaccination-and-autism> .

But you would probably want to say something about the argument, not about the RDF statement expressing the argument. You can use n-ary relations for this, e.g., by introducing an instance that represents the argument:

@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Argument1 a voc:Argument .
:Argument1 voc:publishedIn <https://example.com/articles/vaccination-and-autism> .
:Argument1 voc:textualRepresentation "Vaccination can lead to autism!" .

(and then use properties that dissect the argument to represent it in a machine-readable way)

Relevant vocabularies: PROV, schema:ClaimReview


An algorithm for effecient resource redistribution

There is no polynomial-time algorithm unless $\mathsf{P}=\mathsf{NP}$. Here is a proof.
Let $d_1, d_2, \cdots, d_n$ be the change for each warehouse to reach its target level. For the example in the question, they are $200-250=-50$, $\ 200-150=50$, $\ 150-45-150=105$, $\ 320-205=115$, $\ 350-130=-220$. We assume that sum of all $d_i$'s is 0; otherwise, it is not possible.

Proposition: The target levels can be reached in less than $n-1$ steps if and only if there exist some $d_i$'s but not all of them whose sum is $0$.
Proof.

"$\Leftarrow$". Suppose, WLOG, $d_1+d_2+\cdots+d_k=0$ for some $1\le k\lt n$. Suppose $k\ge2$. Then we can find $d_i\le0\le d_j$ for some $1\le i,j\le k$. We can transfer $\min(-d_i, d_j)$ fish from warehouse $i$ to warehouse $j$. Then either warehouse $i$ or warehouse $j$ reaches its target level. Now we can apply math induction.

"$\Rightarrow$". Suppose the target levels can be reached in some $k$ steps, $k\lt n-1$. At most $k+1$ warehouses are involved in those $k$ steps. The sum of changes for those warehouses must be 0. Note that $k+1<n$.  $\checkmark$.

Let us consider the following warehouse-distribution problem, which is an easier version of the original warehouse-distribution problem.

Given $n$ warehouses with some fish and their target levels of fish,
can we use less than $n-1$ transfers to reach their target levels?

Let us recall, as explained in the Wikipedia article subset sum problem, it is $\mathsf{NP}$-hard to decide, given a multiset of integers, whether there is a non-empty subset whose sum is zero.
Given a multiset of integers $f_1, f_2, \cdots, f_n$, we can construct the following instance of warehouse-distribution problem. Let $f=\sum_{i=1}^n|f_i|$. Let $n+1$ warehouses have $g_1, g_2, \cdots, g_{n+1}$ fish respectively, where $g_1=f+f_1$, $g_2=f+f_2$, $\cdots$, $g_n=f+f_n$ and $g_{n+1}=nf-\sum_{i=1}^nf_i$. The target for each warehouse is $f$ fish. We can verify easily, thanks to the proposition above, that we can use less than $n$ transfers to reach all target levels if and only if there is a non-empty sub-multiset of all $f_i$'s whose sum is zero. Hence, the warehouse-distribution problem is at least as hard as the subset sum problem.

Since a polynomial-time algorithm is unlikely, let me give an algorithm of time-complexity about $O(n2^n)$.

Compute the changes, $d_1, d_2, \cdots, d_n$.

For each subset $S$ of $\{1,2,\cdots, n\}$, compute $\sigma(S)=\Sigma_{i\in S}d_i$. When $\sigma(S)=0$ and $S$ is non-empty,  $S$ will be called a zero-set.

For each subset $S$, let $p(S)$ be the biggest number of disjoint subsets of $S$ that are zero-sets. $p(\emptyset)=0$. For non-empty $S$, use the following recurrence relation to compute $p(S)$. A proof of the recurrence relation is given later.
$$p(S) = \begin{cases}
      \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is not a
 zero-set} \\
      1 + \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is a
 zero-set} \\
\end{cases}$$
where $S\setminus\{a\}$ means $S$ without $a$.

The answer is $n-p(\{1,2,\cdots,n\})$.

First, for any subset $S$, we have
$$\max_{a\in S} p(S\setminus\{a\})\le p(S)\le 1 + \max_{a\in S} p(S\setminus\{a\}).$$
Suppose $S'$ is a subset of $S$. Since any disjoint subsets of $S'$ can be considered as disjoint subsets of $S$, we have $p(S')\le p(S)$. In particular, for any number $a\in S$, we have $p(S\setminus\{a\})\le P(S)$.
Suppose $S_1, S_2, \cdots, S_{p(S)}$ be some disjoint subsets of $S$ that are zero-sets. Let $a\in S_1$. Then $S_2, S_3, \cdots, S_{p(S)}$ are also disjoint subsets of $S\setminus\{a\}$, i.e., $P(S)=1+(P(S)-1)\le 1+ p(S\setminus\{a\})$. $\quad\checkmark$.
Now, Let me explain the recurrence relation in the step 3 above.
There are two cases.

$S$ is not a zero-set.
Suppose $S_1, S_2, \cdots, S_{P(S)}$ are disjoint subsets of $S$ that are zero-sets. If the union of all these subsets is $S$, then $S$ must a zero-set as well, which is not true. So there is a number $a\in S$ that is not in any of $S_1, S_2, \cdots, S_{P(S)}$. That means all of $S_1, S_2, \cdots, S_{P(S)}$ are subsets of $S\setminus\{a\}$. That is, $P(S) \le P(S\setminus\{a\})$. So, $p(S) = \max_{a\in S} p(S\setminus\{a\}).$

$S$ is a zero-set.
Let $a\in S$. Suppose we have disjoint subsets $S_1, S_2, \cdots, S_d$ of $S\setminus\{a\}$ that are zero-sets. Let $S_{d+1}$ be all the numbers in $S$ but not in any of those subsets. $S_{d+1}$ contains $a$. $S_{d+1}$ is also a zero-set since $\sigma(S_{d+1})=\sigma(S)-\sigma(S_1)-\sigma(S_2)-\cdots-\sigma(S_d)=0$. Since $S_1, S_2, \cdots, S_{d+1}$ are disjoint subsets of $S$ that are zero-sets, $p(S) \ge 1 + d$. That means, $p(S)\ge 1 + \max_{a\in S} p(S\setminus\{a\}).$ So, $p(S) = 1 + \max_{a\in S} p(S\setminus\{a\}).$  $\quad\checkmark$.


You are right. It seems you completely understand this already: in any case the result can be found many places, as it is a basic result about the Turing degrees.


How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming?

You can solve this problem filling the following table.

Let's say that $cost(row,col)$ is the minimal cost that can be achieved starting from one node on the leftmost edge of the grid and ending in the cell $(row, col)$, only performing valid operations.

The answer to the problem will be the minimum among all $cost(i,j)$ where $j=last\_col$. Notice that table $cost$ table is the same as $opt$ table, but now you have the proper semantic of it's entries, so it's easy to fill base values, and extract final values.

Step 1:
Base values: Fill first column entries with there current value. i.e $cost(i,j)$ where $j=0$. It is $cost(i,0)=value(i,0)$ since the only way you can reach node $(i,0)$ starting in a leftmost node and performing valid operation, is starting in the node itself.
Step 2:
The same you described before. This holds, because you can only get nodes on the $j^{th}$ column from the $(j-1)^{th}$ column, and since you are filling $cost$ table in increasing order of columns, previous values will be computed when you need to compute current values. [This is dynamic programming]
Step 3:
As I said before, and you said too, return the minimal value among all entries in the last column of $cost$ table.

Why Bellman Ford (BF) works here in the way you do it.

BF algorithm finds shortest path in a graph from a single source to every other node inside the graph. In the $k^{th}$ step BF have already computed shortest path starting from source node $S$ to every other node using at most $k$ edges.

Let's transform our problem into a valid instance for BF, and the let's modify BF to run in $O(n^2)$.

Let's say we convert each cell of the grid into a node, and you put an edge between node $u$ and $v$ if the transition from $u$ and $v$ is valid. Let the cost of edge between $u-v$ be the original cost of the cell $v$, so moving through this edge adds to the overall cost getting into node $v$, as we expect.

Now we have two problems.

Problem 1, the running time of our algorithm will be $O(nodes \cdot edges)$ where $nodes$ is $n^2$ and $edges$ is $O(nodes) = O(n^2)$ so overall complexity will be $O(n^4)$.
Problem 2. There are several sources, so we need to run BF starting at every source, and this increase the overall complexity by a factor of $n$.

Let's get rid of both problems, starting from problem 2. If you add an extra node connected to every node at the first column, you simulate the process of starting at every node in one run. Look at the following image for more understanding. I didn't pain all connection but just a few.

To get rid of the first problem, you need to exploit the structure of our graph. It is not so general. You can only reach nodes in the $k^{th}$ column in the $k^{th}$ step, and since there is no backward edge, in this step only nodes in this column needs to be updated. So overall complexity will be $O(nodes) = O(n^2)$.


If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

Not quite.  If there's an exponential lower bound for a NP-complete problem, then it follows that no NP-complete problem can be solved in polynomial time.  However, there will be some other NP problems (which aren't NP-complete) that can be solved in polynomial time.

If there's an exponential lower bound for any NP problem, then it follows that P != NP.  In particular, an exponential lower bound for some problem means that the problem is not in P.  So, if you have an exponential lower bound for some NP problem, that means the problem is in NP but not in P -- which means NP contains a problem that is not in P -- which means that NP != P.

It might help to recall that NP is a set of problems (the set of all search problems where YES answers have a polynomial-size witness that can be verified in polynomial time).  Similarly, P is a set of problems (the set of all search problems that can be solved in polynomial time).  So, if you've found one element of NP that is not an element of P, you can immediately conclude that those two sets are not the same sets.

Or, to put it another way: your second paragraph is the contrapositive of the statement in the first paragraph.  If there is a NP problem with a non-polynomial lower bound, then not every problem in NP can be solved in polynomial time.  If not every problem in NP can be solved in polynomial time, then it follows that no polynomial-time algorithm can be found for any NP-complete problem.

See What is the definition of P, NP, NP-complete and NP-hard? for more background.


Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

Say we are at state j (in the question's example, j is 5). This means that so far we have successfully matched j characters (characters 0 to j-1 of the pattern). Now, we receive a new character - call it newChar.

Case 1: newChar is the character we wanted ('C' in the example). All is good and we have now a match of j+1 characters (characters 0 to j of the pattern).

Case 2: newChar is not the character we wanted. Let's assume the most optimistic situation: that we've now matched j characters of our pattern. (We couldn't have a match of j+1 characters in this case, because otherwise we would be in Case 1.) The last of these j characters that we matched is newChar. To have a total of j characters matched, then, we must have matched characters 1 to j-1 of the pattern plus newChar.

Because a mismatch puts us in Case 2, and Case 2 only uses characters 1 to j-1, we need only run the simulation using the last j-1 characters.


Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers

Statement (2) requires that the smallest prime number whose square exceeds $j$ is in the list. If $j=p_{n+1} > (p_n)^2$, then the smallest prime number whose square exceeds $p_{n+1}$ is $p_{n+1}$ itself. As $p_{n+1}$ is not in the list while tested, (2) no longer holds.

You indeed show that all primes that are divisors of $j$ are in the list. So, an algorithm that tests all divisors in the list would be correct. However, this isn't what the algorithm in the text does, it first looks for a prime of which the square exceeds $j$, but doesn't have to be a proper divisor of $j$.

So, the algorithm as stated in the text does require property (2), which relies on the fact that $j=p_{n+1} > (p_n)^2$. In your analysis, you made the change that only the primes that divide $j$ properly need be in the list. This is a valid algorithm, but it is a different algorithm than the one in the text.

In other words, while having all primes that are proper divisors of $j$ in the list is nessecary, it isn't sufficient to run the algorithm as stated in the text.


How does one generate all the terms of a multivariate polynomial algorithmically?

You can generate all non-negative integer solutions to $d_0 + \cdots + d_N \leq D$ recursively. The recursion is as follows:

If $N = 1$, generate $0,1,\ldots,D$.
Otherwise, for each $d_N \in \{0,1,\ldots,D\}$, generate all solutions for $N:=N-1$ and $D:=D-d_N$, and append $d_N$ to all of them.

If you don't like recursion, you can also implement this iteratively. Start with the zero solution, and repeatedly try to "increment" it. To increment a solution, find the largest $i$ such that $d_0 + \cdots + d_i < D$ (if any; otherwise, you're done), increment $d_i$, and set $d_{i+1} = \cdots = d_N = 0$. This generates all solutions in lexicographic order.

As an optimization, you can store and update the running sums $s_i = d_0 + \cdots + d_i$ to speed up the procedure. This optimization should make the increment routine run in amortized $O(1)$ time.


Which algorithm can calculate an optimal allocation of students to projects?

This sounds much like a problem for minimum-cost maximum flow.

Construct a network.
The nodes will be the students, the projects, and the added source and sink.

Add an edge with capacity $1$ and cost $0$ from the source to each student.

Add an edge with capacity $y$ and cost $0$ from each project to the sink.

Add an edge with capacity $1$ and cost $r_{i,j}$ from each student $i$ to each project $j$, where $r_{i,j}$ is the rank given by student $i$ to project $j$, the most preferred being ranked $1$.
(Alternatively, we can give negative scores, $-m$ up to $-1$, or even $-(2^m)$ up to $-(2^1)$, and more negative is more preferred.
I believe the exact scheme is not significant.)

Now find the minimum-cost maximum flow.
The maximum-ness of the flow means that each student is assigned to some project, because the maximum flow is obviously equal to the number of students.

The condition which can break is that each project gets at least one student.
(Before proceeding to remedy this, first, check if the values $n$, $m$, and $y$ make failing this condition at all possible.)
We can force it by splitting the edges from projects to the sink: instead of one edge of capacity $y$ and cost $0$, we can have an edge of capacity $1$ and cost $-L$, and another of capacity $y - 1$ and cost $0$.
The value $L$ is a large constant, effectively infinite compared to all other costs: if we just use the ranks from $1$ to $n$, perhaps something like $m \cdot n$ will suffice.
This way, a minimum-cost flow will have to add at least one student to every project in order to use all of the available edges of cost $-L$.

The thing left to prove is that the resulting arrangement is stable.
Indeed, if the stable condition was not satisfied, we could just make a local change, like switching a student to their more preferred project, or swapping the projects for two students.
These would result in strictly lower cost with the same flow, which would in turn contradict the fact that we found the minimum cost flow.

I'm not going into details here (we should start with a formal definition of stableness when only one side has preferences), but hope that they turn out trivially right.
In the unfortunate case they don't, the first I'd do is revisit the cost assignments for $r_{x,y}$.


If A is poly-time reducible to B, is B poly-time reducible to A?

Short answer: No.

For one example, take $A$ to be the language $A = \{0, 1\}^*$, i.e. the language that contains every possible string. It is polytime reducible to pretty much anything, for example 3-SAT (the reduction outputs the formula $x\wedge y \wedge z$ on every input). But 3-SAT is definitely not reducible to $A$: there is nothing to map unsatisfiable instances to.

Maybe a bit less silly. Take $A$ to be any problem in P. Take $B$ to be a problem complete for exponential time (for example the problem of deciding, given a Turing machine $M$, an input $x$, and a number $k$ written in binary, whether $M$ halts on $x$ within $k$ time steps). Because $B$ is complete for exponential time, $A$ is reducible to $B$. Because a polytime reduction from $B$ to $A$ would imply a polytime algorithm for $B$ and therefore for any exponential time problem, contradicting the time hierarchy theorem, such a polytime reduction does not exist.


Reduce the following decision problem to CNF-SAT

Yes, you certainly can reduce it to SAT: the problem you state is obviously in NP, and thanks to Cook's theorem, everything in NP can be reduced to SAT.

I suspect that wasn't what you actually meant to ask.  Actually, your problem is in P: Hall's theorem says that such an assignment exists if and only if the corresponding bipartite graph has a perfect matching.  You can test whether a bipartite graph has a perfect matching in polynomial time using standard algorithms.


any hope for a universal automatic parser?

You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those strings.

To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a grammar given a finite set of finite strings?, and the the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms.

There's no hope for automatically building an interpreter for the language, because that depends on the semantics (meaning) of the programs, and you can't determine that solely from the program source code; the most you can hope to learn is to characterize the syntax of the language, not the semantics.


What are some of these "high-level" instructions found in CISC architectures?

I know of two main aspects of complex instructions.

addressing modes.  There are two sub-aspects here:

RISC tend to be load/store machines (that this the only instructions which access memory are those whose sole goal is that access), CISC tend to allow operands to be in memory and to be accessible with a variety of addressing modes.  When each operand can have an independent addressing mode like on the VAX, that make the instruction complex.
the addressing modes of CISC tend to be more complex than those of RISC.  When, like the PDP-10, the number of memory access needed to determine the true operand is unbounded, it makes the instruction complex.

the instructions themselves. That's what you are probably thinking about. Setup of complex stack frames with automatic saving of registers, which register to be saved being determined by a bitmap (see VAX) and other complex context switching state mechanism (see 80386 task gate or whatever their name is), polynomial evaluation (see VAX), insertion in a linked list (I don't remember where I've seen that and don't want to dig it out, VAX and PDP-10 are candidates), it is folklore (I don't know how true it is) that some machines in the IBM 360 family had instructions who where designed for the only usage of  improving their Cobol library sorting function.

I think they all can be regrouped with one characteristic: complex instructions are those who need to do a relatively large (and I'd not argue strongly against defining large as being greeter than one), sometimes variable number of memory accesses.  That characteristic brings true nightmare:

you need a relatively complex state machine to handle them, and to decide how to handle interrupts during the time they execute;
you need to be handle multiple page fault (in simple instruction you have two: one for the instruction, one for the data memory) which means that they may be interrupted and resumed for internal reasons several times, making the first issue more important.


From your table, the following is apparent: at iteration $i$,
$$
\text{main_f} = (i+1)x + \binom{i+1}{2}.
$$
You should be able to prove this formula by induction.


Context-free string that satisfies constraint?

It is not necessary to define a string that has exactly length $p$. It only has to have length at least $p$. So $(i,j,k) = (2p^2,2p^2,2p)$ so that $2p^2+2p^2 = (2p)^2$ for a string of length $4p^2+2p$ would be OK.


An operational semantics for lambda-calculus normal order evaluation strategy

You can use the following rules:

$\frac{t_1 \longrightarrow t_1'}{t_1 t_2 \longrightarrow t_1' t_2}$

$(λx. t_1) t_2 \longrightarrow [x \mapsto t_2]t_1$


Difference between Image Analysis and Computer Vision

Maybe the web does not have an answer, but the classical book of Image Processing by Gonzalez and Woods has. I will summarize a part from a chapter that I have read.

There is no clear boundary between the three areas of Image Processing, Image Analysis and Computer Vision. Some say that, what inputs and outputs images is Image Processing, but should the simplest task of computing the average of an image (that is a number) be excluded? Computer Vision though, is a branch of AI, that is much different from the other two fields, since it focuses on learning, making inferences and taking actions based on visual inputs. Image Analysis (a.k.a Image Understanding) is between Image Processing and Computer Vision, but with no clear boundaries. However, one could define three distinct processes based on a hierarchy level. The low-level processes consume and produce images (e.g noise reduction, contrast enhancement, image sharpening), the mid-level processes take images and output attributes (e.g edges, contours, object identities). Example tasks include image segmentation and object description and recognition. Lastly, high-level processes try to comprehend the recognized objects and at the far end, introduce cognitive functions for emulating human vision.

For more details, one can go and read the source, because luckily, that chapter is available online as a sample. The particular content lies in page 18 beginning from the third paragraph "There is no general agreement..." until the end of the next page's first paragraph "...for the methods used in this application area". I would have quote the whole content in case the website shuts down in the future, but I don't know if this is legal.


Memory cells (addresses) read into a cache

Cache lines are aligned.  That means that the bottom-most bits of the start address of the cache line are always 0s.

If you have 8-byte cache lines they will always be read in address ranges $[8i, 8(i+1) - 1]$.  For example, if you read address 117 (decimal) = 1110101 (binary) then the 8 byte cache block that gets read in is the set of bytes in the range 112 (decimal) = 1110000 (binary) through 119 (decimal) = 1110111 (binary).


Knuth's scale goes up to 50 (for "unsolved research problems"). Note that the scale is meant to be (roughly) logarithmic, i.e., adding 10 to the number multiplies the work required by a factor, with 50 meaning some so ridiculously large amount of work to be done that it can be taken practically as "infinite".

Fermat's Last Theorem used to be 50 as an example in the preface, with Wiles' proof it is now "just" extremely hard, i.e., it got demoted to 45 in later editions.

So the answer to the question is "no". By definition 50 is the highest value on the scale.


An algorithm to check if two DFA are disjoint

Construct the intersection DFA of both DFA's. Then, check if there is a path from the starting state to any end state.
If there is a path, then the two DFA's are not disjoint. If there isn't, then they are.


We can prove the following theorem:
Theorem: A language $L$ is regular if and only if there exists a DFA or NFA for language $L$.
Turing machines are more powerful than DFAs and NFAs. In particular,  every finite state automaton can be simulated by some Turing machine.
So, according to the above propositions, the answer to your question is yes: every regex has a Turing machine whose language is identical.


Suppose $G = (V, E)$ is a tree with 25 vertices such that there exist some constants $c \geq 0$ and $m \geq 2$ such that $\operatorname{deg} v \equiv_m c$ for all $v$. Note that we can equivalently write $\operatorname{deg} v = a_v m + c$ for some $a_v \geq 0$.

Since $G$ is connected by definition, we get that it must have 24 edges in total, giving us
$$ \sum_{v \in V} \operatorname{deg} v = 2 \cdot |E| = 48.$$
We can express this sum using the aforementioned decomposition of the degrees in $G$ to get
$$
\begin{align*}
 \sum_{v \in V} \operatorname{deg} v
 &= \sum_{v \in V} a_v m + c \\
 &= c |V| + m \sum_{v \in V} a_v \\
 &= 48.
\end{align*}
$$
Due to the both terms in the rewritten sum being non-negative, we get that $c$ must be 1 if we are to find any solutions.
Hence we get that $m$ must divide $48 - c|V| = 23$, which implies $m = 23$ as we required $m \geq 2$.

At this point, we know that any such $G$ satisfying your conditions does so with $c = 1$ and $m = 23$.
By using our new formula again, we find that the sum of our $a_v$ must also equal 1 and therefore, $G$ must be isomorphic to a tree with 1 internal node and 24 leaves, which is also known as the star graph $S_{24}$.


Best time complexity of sorting numbers in range [1...n log n]

Note in the RAM model, indirection always takes constant time regardless of how large the address is, so each process of radix sort with base $b$ takes $O(n+b)$ time. As a result, the radix sort takes $O((n+b)\log_b(n\log n))=O((n+b)\log_b n)$ time. Choosing $b=n$ makes the asymptotic time linear.

Edit: as suggested by Thinh D. Nguyen, since extracting each digit under base $b$ requires division and modular arithmetic, which are not supported by the standard RAM model, we may want to use the word RAM model instead.


Traversing a graph in finite time, maximizing utility

I think this is the knapsack problem, with the following correspondences:

item: activity
item weight: activity performance time
item value: activity utility
knapsack maximum weight: finite time horizon T

One solves it using dynamic programming.

(I don't think a graph model would be useful here, as it does not seem easy to encode the problem into a standard graph problem.)


Using Dijkstra's algorithm with negative edges?

Short answer is that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice.

Here's an analogy: (that might help, or confuse even more) Take a convex optimization problem and poke a concavity into it. Now ask the question why it can't be solved with a linear program. The problem is that the linear program's premise is that once we reach the edge of a convex surface in the direction of optimality, we know for certain it is optimal. With a concavity, this no longer works and the algorithm falls flat. The negative values are like these concavities, they introduce local extrema making it harder to find the global one.


Are the following loops $O(n^2)$ complexity

It's quite easy, you just have to write down the first terms :

1.) The print instruction will be called $n$ times, then $n/2$ times, then $n/4$ times, etc...
Finally, the number of calls to print is $\Sigma_{i=0}^{\log n} \frac{n}{2^i} = n \Sigma_{i=0}^{\log n} \frac{1}{2^i} = n \frac{1-1/2^{\log n}}{1-1/2}=\mathcal{O}(n)$.

2.) The print instruction will be called $n$ times, then $n/2$ times, then $n/3$ times, etc...
Finally, the number of calls is $\Sigma_{i=1}^{n} \frac{n}{i} = n \Sigma_{i=0}^n \frac{1}{i} = \mathcal{O}(n \log n)$.


The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $[C] = 1$ if $C$ is true and $[C] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$:
$$P = \dfrac{\sum\limits_{p\le n^c} [p\text{ prime}] [p \mid (a-b)]}{\pi(n^c)}$$

Since $|a-b| \le 2^n$, there are at most $n$ distinct primes that divide $a-b$. The prime number theorem directly gives an upper bound for the denominator. Thus:
$$ P \le \dfrac{n}{n^c/\ln(n^c) + o(n^c/\ln(n^c))}
     = \dfrac{c \ln(n)}{n^{c-1}} (1+o(1))$$

You won't get an exact bound from an asymptotic version of the prime number theorem. An exact bound, if I am not mistaken, is $\pi(x) \gt \dfrac{x}{\ln(x)}$ for $x \ge 11$. Using this bound, we see that if $n^c \ge 11$ then
$$
P \le \dfrac{c \ln(n)}{n^{c-1}}
$$

Application: we can compress $a \le 2^n$ (which takes $n$ bits to represent exactly) approximately by storing $a \mod p$ for several random prime numbers $p_i$. If we use $k$ primes chosen independently of the value of $a$, then the representation requires $k \, \lceil c\,\log_2(n) \rceil = O(k \log(n))$ bits to store the values modulo every chosen prime. The probability of a collision on each prime is at most $c \ln(n) / n^{c-1} = O(\ln(n)/n^{c-1})$. To evaluate how the precision increases with $k$ would require further analysis.


Possible to connect arbitrary number of dots without intersections?

It is (almost always) possible. Let the two points be $p_1=(x_1,y_1)$ and $p_2(x_2,y_2)$. Wlog, assume that $x_1<x_2$. Denote by $q_1$ ($q_2$) the point with smallest (largest) $x$-value greater (smaller) then $x_1$ ($x_2$) (and smallest (largest) $y$, if there are multiple candidates). Then you can do the following:

Determine the set $S_1$ of all the points with $x\leq x_1$.
If $|S_1|=1$, connect $x_1$ and $q_1$.
If $|S_1| > 1$ and all the points in $S_1$ are on the same straight line:

If all points outside of $S_1$ are on the same straight line, there is no solution
Otherwise denote by $r_1$ the point with smallest $x$-coordiate not on the straight line. (If there are multiple such points choose the one with smallest $y$-coordinate.)
Connect the points in $S_1$ starting with $x_1$. Connect the last of these points with $r_1$ and (if $r_1 \ne q_1$) connect $r_1$ with $q_1$.

If $|S_1| > 1$ and the points are not all on one straight line, determine the convex hull of $S_1$.
At least one of the neighbours $n_1$ of $p_1$ on the convex hull can be reached from $q_1$ without intersecting the convex hull.

Draw a (reverse) path from $q_1$ to $n_1$ and then along the convex hull to the point with smallest $x$. Continue in left-to-right-order (skipping points already included) until $p_1$.

Analoguously connect the points with $x\geq x_2$.
Connect the points with $x_1<x<x_2$ (i.e. from $q_1$ to $q_2$) in left-to-right-order (ignoring $r_1$ resp. $r_2$, if applicable).


Proving that co-finite languages can be decided in constant time

Your observation that co-finite languages are regular and hence in linear time is absolutely correct. Unfortunately, it's not enough, since there are definitely regular languages that require linear, and not constant, time (e.g., even checking if your input matches $0^*$ requires you to look at the whole input, unless $\Sigma=\{0\}$).

There are only finitely many strings not in a co-finite language. So, how much input do you need to read before you know whether the input is one of those?


Automorphism of a Graph with a given Set of Permutations

If you only want an automorphism, then just consider the identity permutation.  That's an automorphism -- the trivial automorphism.

If you want a non-trivial automorphism, then if I understand your problem statement, this is as hard as the graph automorphism problem.  No polynomial-time algorithm is known for this problem.  It's not known to be NP-complete (it's not even known to be GI-complete).  Nonetheless, finding a polynomial-time algorithm for this problem is an open problem, so you shouldn't expect it to be easy to find a polynomial-time algorithm for your problem, either.

In practice you can use open-source tools like Nauty, BLISS, or SAUCY to find an automorphism; on most graphs they (empirically) are very fast.

Justification of claim that this is as hard as graph automorphism:

We can reduce graph automorphism to your problem.  Let $G$ be an arbitrary undirected graph, with $n$ vertices.  Construct an undirected graph $H$ with $2n$ vertices as follows: for each vertex $v$ of $G$, add another vertex $v'$, and add an edge $(v,v')$.  Keep all the edges between unprimed vertices, but don't add any edges between primed vertices.

Note that the automorphisms of $G$ are in one-to-one correspondence with the automorphisms of $H$.  If $\pi$ is an automorphism of $G$, it can be extended to an automorphism of $H$ simply by permuting the primed vertices in the same way as the unprimed vertices.  If $\pi'$ is an automorphism of $H$, by projecting it to the vertex set of $G$ we obtain an automorphism of $G$.

Now define $H_1,\dots,H_n$ as follows: each $H_i$ is the subgraph induced by the two vertices $v_i,v'_i$.  In other words, $H_i$ has vertex set $\{v_i,v'_i\}$ and has a single edge $(v_i,v'_i)$.  Thus, $H_i$ has a non-trivial automorphism that swaps $v_i$ and $v'_i$, and this corresponds to a permutation $\pi_i$ of $H$ (one that leaves all other vertices of $H$ fixed).  Define $\alpha$ to be this set of permutations.

Now if you can find a non-trivial automorphism of $H$, you can immediately obtain a non-trivial automorphism of $G$ (i.e., you've found a way to solve the graph automorphism problem on an arbitrary graph $G$).  If $H$ has no non-trivial automorphism, neither does $G$.  This completes the reduction.


Given an array $A$, find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$?

Consider the absolute worst case, where every element is equal to every other element. This means that the algorithm has to output $n(n-1)(n-2)(n-3) \in O(n^4)$ quadruples. So in the worst case we can't do better. But often for problems like this it's useful to also consider cases where we don't have to output as much.

So let's do better. If you sort the data in $O(n \log n)$ (making sure to store the original indices) you can then in an $O(n)$ step find all equivalence classes. Then you can output all quadruples by first iterating over all possible pairs of equivalence classes and then iterate over all possible combinations of elements from those two equivalence classes.

Those last two steps are in theory $O(n^4)$, but are a lot smaller when the equivalence classes get smaller.


Is every CPU instruction ultimately read and write?

Ultimately, the state of the machine must change after executing every single instruction: if it did not, then the machine would be stuck in an infinite loop of executing the same instruction again and again. So, in that sense,  some value in memory or in a register to be changed after each instruction is executed. At a minimum, this would be advancing the program counter.

If you want to count that as a "write" instruction then, yes, every instruction is a write instruction. However, then we would be in the situation that the phrase "write instruction" would mean exactly the same thing as "instruction", so it wouldn't be a useful piece of terminology. OK, so perhaps we want to define a write instruction to be one that directly alters a register or the main memory, where, by "directly alters", I'm excluding the automatic increment of the program counter.  Well, OK, but that's not very useful, either, since every instruction I can think of does that, apart from a no-op.  That wouldn't be a useful definition, either.

So, typically, "write instruction" is understood to mean an instruction that writes a value to some location in the main memory. Clearly not all instructions do that: for example, typical arithmetic instructions operate only on the registers.  Similar arguments can be made for reading.


What is considered an asymptotic improvement for graph algorithms?

The most permissive definition is as follows.
Suppose that $f(V,E),g(V,E)$ are two running times of graph algorithms solving the same problem.
We say that $f$ is an asymptotic improvement in some regime on $g$ if there exists a sequence $V_n,E_n$ with $V_n \to \infty$ such that
$$
\lim_{n\to\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.
$$
Sometimes the regime is not deemed interesting, but that's a more subjective matter.
Note also that the problem already manifests itself for one-variable functions. Consider
$$
f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &\text{if } n = 2^m, \\ n & \text{otherwise}. \end{cases}
$$
Is $f$ an asymptotic improvement over $g$? It is for inputs of a certain length, and is indeed so under our permissive definition above.


How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2?

If all edge weights are $1$ or $2$ you can have a linear time algorithm to find shortest path.
First perform a BFS and for every edge $(u,v)$ of weight $2$ add an vertice at the middle $w$ so that you now have two edges of weight one $(u,w)$ and $(w,v)$.

After this BFS your new graph have all it edges of weight $1$ and have at most $2X$ edges.

Now perform an other BFS on this graph to find the shortest path. It gives you a complexity of $O(2X+Y)$.
Thus the total complexity is $O(X+Y)$


You need to choose an NP-hard problem, and show a deterministic polynomial-time algorithm that transforms any instance of this NP-hard problem to an instance of your city problem that is true if and only if the original instance was true. As you suggested in the question, Hamiltonian path is a good choice for the starting problem.

Try to create an algorithm that takes any Hamiltonian path instance and constructs a "city problem" instance which has the same truth value. You must also write a proof that, for any input instance of Hamiltonian path, the corresponding output instance of the "city problem" has the same truth value.

Hint 1:

   Think about subdividing edges.

Hint 2:

   If you take an arbitrary (undirected simple) graph and subdivide each edge once, you get a graph in which none of the original vertices are adjacent to each other.


Algorithm for implementing the modulus "%" operator?

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift and many others, a % b is defined as a - b * (a/ b). And that’s what you implement.

To be efficient: Most processors have built-in division and multiplication. Many support faster implementation of division if b is known. And at last if you want to know whether a % b = 0, you can do that without calculating a / b exactly which makes it a bit faster.


What computational complexity classification does autonomous/self-driving cars belong to?

Complexity theory is mostly interested in decision problems and in optimization problems, and your problem belongs to neither class. Complexity theory is also interested in other resources, such as communication, but at the cost of neglecting computational complexity.
Apart from not fitting the mold of problems typically considered in complexity theory, your problem is also not well-defined. There is no accurate and formal specification of the required behavior. Without such a specification it is hard to mathematically gauge its complexity.
While it is possible to abstract some aspects of "autonomous driving" into pieces which do fit current theory, in my opinion it doesn't bring us any closer to understanding the actual difficulty of solving this problem.
Complexity theory won't help you in understanding the problem of poverty, or even the problem of writing poetry, or even the decision problem of determining whether a given poem is "good" or "bad". It is not an all-encompassing theory of reality, and as you observe, it doesn't even capture all problems in which computers are involved.
Autonomous driving, in particular, combines hardware, software, legal issues, and philosophical issues. When designing autonomous vehicles, we also design the sensors available to the software controller, the mechanical interventions it is allowed to use, the laws it complies with, and so on. All of these important and pertinent issues are beyond what computational complexity theory offers.


An online parallel algorithm for finding top K elements

Here is one naive solution:
Let the number of parallel processes be $m$. Then, keep a separate buffer/heap/balanced tree for each of the $m$ processes. Divide the range of input into $m$ sections. Whenever you read a number, insert it into the appropriate process' heap. This way, each process only works on its own heap/tree. When you are done with the input, and want to output the top $k$ elements, do a partial mergesort to find the overall top-k.

This will require $O(km)$ space and $O(n\log k + km\log k)$ time.


Isn't polynomial identity testing over arithmetic *expressions* trivial?

For a univariate polynomial $p(x)$, yes, it's that easy.

For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works.

In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials.  Ricky Demer gives a simple example: $p(x,y) = xy$ is of degree two, but has infinitely many roots.


Longest path in DAG or finding DAG diameter

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

That's not how the diameter is usually defined; it's rather the maximum distance, i.e. the length of the longest shortest path. As such, any general-purpose APSP algorithm helps you find the diameter of DAGs.

  here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path.

Infinite loops are not the problem; finding longest paths is NP-hard in general graphs.

  Is any polynomial time order algorithm for this problem....?

As explained on Wikipedia [1], the Longest Path problem can indeed be solved efficiently on DAGs by finding the shortest path in the graph obtained by multiplying all weights by $-1$.

Algorithms by R. Sedgewick and K. Wayne (2011)


In which category is the supercomputer SUMMIT according to Flynn's taxonomy?

Summit is a parallel system that apparently contains many nodes, where each node is powered by one or more POWER9 processors.  Each POWER9 processor contains a vector scalar unit that Wikipedia says can be described as a SIMD unit.  However, the Summit system as a whole would normally be used in a MIMD mode, as each POWER9 processor can run a separate program. It doesn't have to -- you could run the same code on each node, or different code on each node -- but each node runs asynchronously and independently, so I would classify the entire system as MIMD.


When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?

I don't like how you expressed this - the ten times faster computer is ten times faster. It will solve the same problem and answer the same question ten times faster. Of course if you give it a question that would take 100 times longer on the old computer, then it will take only 10 times longer on the new computer.

If you had an algorithm that took n log n microseconds (and in CS "log" usually means log base 2) to solve a problem of size n, a problem of size 10 n would take 10n log (10n) microseconds on the old computer, and n log(10n) microseconds on the new computer.

log (10n) isn't ten times or twice as much as log n - the factor 10 turns into a constant. log (10n) = log n + log 10 ≈ log n + 3.3. If n = 10 it's twice as much. If n = 10 billion it's only ten percent more.

Two things to consider: No computer is just "ten times faster". A computer does many different kinds of operations. Some may be ten times faster, some even more, some less. And Big-O is concerned about asymptotic values: I could have an algorithm that takes on my computer n^2 microseconds if n ≤ 1,000,000 and 10n^2 microseconds if n > 1,000,000. So if you want to find actual execution times, you need more than Big-O.

And it is very common that actual execution times are quite different from what Big-O makes you belief when n is small. For example, let f(n) = n + 1000 log n. f(n) = O(n). But for n ≤ 10,000 f doesn't behave very linear at all.


Proof for Turing Machines being able to simulate any algorithm in the same time complexity

This is not a formal statement, but either a definition or an empirical observation. The full claim is something like the following:

"A reasonable model of computation (for discrete data) together with a reasonable notion of time complexity will have the property that it can be simulated by a Turing machine with at most polynomial increase in time complexity."

The two occurances of "reasonable" here are generally not seen as formal notions, but rather as informal notions. We can trivially define models of computation with notions of time complexity not having the property above, but these models do appear artificial. On the other hand, models people actually want to use have the property.

Any attempt to formally define what a "reasonable model of computation with time complexity" is would probably include the possibility of polytime-simulation by a TM as an axiom.


Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$

Rearrange the numbers in sorted order so that you have $x_1\le x_2\le \dotsm \le x_n$. Now let $m$ be the median value, $x_{\lceil (n/2)\rceil}$, i.e., the value for which half of the elements are greater than or equal to $m$. This will minimize $\sum_{i=1}^n |x_i-m|$. (If $n$ is even, any value $m$ in the range $x_{\lceil (n/2)\rceil}\le m\le x_{\lceil (n/2)\rceil+1}$ will do for $m$).

For example, if $x_1=1, x_2=2, x_3=4, x_4=8, x_5=16$, the median value will be $m=x_3= 4$ and you'll have
$$\begin{array}{ccccccccc}
& |x_1-4| & + & |x_2-4| & + & |x_3-4| & + & |x_4-4| & + & |x_5-4|\\
=& |1-4| & + & |2-4| & + & |4-4| & + & |8-4| & + & |16-4|\\
=& 3 & + & 2 & + & 0 & + & 4 & + & 12\\
=& 21 &&&&&&&&
\end{array}$$

so the minimum value of the sum will be 21.

It's not too difficult to show that this algorithm is correct: inductive proofs for $n$ even and $n$ odd will do it. To see what's going on, try graphing something like $y=|x-1|+|x-3|$ and looking for the $x$ value(s) that minimize this function.