How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?

A general resource graph which cannot be completely reduced but which is free from deadlock is illustrated below.

R1 and R2 are reusable resources, and P1 and P2 processes.


Is there a paradigm for composing "incremental update" functions in a pure dataflow style?

This field has been invented many times, and goes under many names, such as:

Online algorithms.
Streaming algorithms, stream queries, continuous queries.
Dynamic data structures.
Self-adjusting computation (as per Andrej).

(And possibly more.) Those are not the same, but related.

Paraphrasing  Cai et al (1): There are two core ways of implementing online algorithms generically (i.e. without reference to any specific algorithmic problem):

Static incrementalisation. Static approaches analyse a program at compile-time and produce an incremental version that efficiently updates the output of the original program according to changing inputs. Static approaches have the potential to be more efficient than dynamic approaches, because no bookkeeping at runtime is required. Also, the computed incremental versions can often be optimised using standard compiler techniques such as constant folding or inlining. This is the approach investigated in (1).
Dynamic incrementalisation. Dynamic approaches create dynamic dependency graphs while the program runs and propagate changes along these graphs. The most well-know approach is Acar's self-adjusting computation. The key idea is simple: programs execute on the original input in an enhanced runtime environment that tracks the dependencies between values in a dynamic dependence graph; intermediate results are cached. (As you might imagine, this tends to use a lot of memory, and much research in this field is about how to limit memory usage.)  Later, changes to the input propagate through dependency graphs from changed inputs to results, updating both intermediate and final results; this processing is often more efficient than recomputation. However, creating dynamic dependence graphs imposes a large constant-factor overhead during runtime, ranging from 2 to 30 in reported experiments.

In addition, one can always  try and come up 'by hand' with an online version of a given algorithm. This can be difficult.

(1) Y. Cai, P. G. Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for Higher-Order Languages: Incrementalizing λ-Calculi by Static Differentiation.


Number of grid points in d-dimensional sphere of radius r

I'll assume $l,d$ are given in unary, otherwise the problem has a trivial exponential lower bound as the number of solutions can be $\Omega(2^d)$, e.g. in the case of $l=d$, each entry could be zero or one.

If we are given $1^l,1^d$, then this can be solved in polynomial time. Suppose $d=2^k$ (this will simplify things), and let $A(d,l)$ be the recursive algorithm for counting the number of solutions which is defined as follows:

$A(d,l)=\sum\limits_{l'=0}^l A\left(\frac{d}{2},l'\right)A\left(\frac{d}{2},l-l'\right)$

I'm pretty sure $A$ can be made to run in polynomial time using memoization, by keeping a $d\times l$ size table of the values we computed so far.


What type of math classes are good to take for computer science majors?

Discrete maths will be the first priority.

then number theory.


Here is the post for the 2nd modification, which is

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

The solution is based on DP. For the sub-problem (i-j) i.e. v[]i, v[i+1], ..., v[j] there are two choices:

The user chooses the i-th element with value v[i]: The opponent either chooses (i+1)-th element or j-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value v[i] + min(F(i+2, j), F(i+1, j-1))

The user chooses the j-th element with value v[j]: The opponent either chooses i-th element or (j-1)-th element. The opponent intends to choose the element which leaves the user with minimum value.
i.e. The user can collect the value v[j] + min(F(i+1, j-1), F(i, j-2))

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.
F(i, j) = Max(v[i] + min(F(i+2, j), F(i+1, j-1)), v[j] + min(F(i+1, j-1), F(i, j-2)))
Base Cases
F(i, j)  = v[i] If j == i
F(i, j)  = max(v[i], v[j])  If j == i+1

Here is a pice of code in Python that solves it
def optimalStrategyOfGame(arr, n):

    # Create a table to store solutions of subproblems
    table = [[0 for i in range(n)] for i in range(n)]

    # Fill table using above recursive formula. Note that the table is
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.
    for gap in range(n):
        for j in range(gap, n):
            i = j - gap

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is
            # F(i, j-2) in above recursive formula
            x = 0
            if((i + 2) <= j):
                x = table[i + 2][j]
            y = 0
            if((i + 1) <= (j - 1)):
                y = table[i + 1][j - 1]
            z = 0
            if(i <= (j - 2)):
                z = table[i][j - 2]
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
    return table[0][n - 1]

[SOURCE] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/


Interpretation of '1/3' in IEEE floating point representation

The fractional part is in binary: $(0.01010101\ldots)_2 = (0.333333\ldots)_{10}$. To convince yourself of this, try multiplying the binary $0.0101010101\ldots$ by $3$: you will get $0.111111\ldots = 1$. In a similar way, the decimal $0.0101010101\ldots$ equals $1/99$.

The mantissa (fractional part) in fact has an implicit $1.$ in front, so it actually equals $(1.01010101\ldots)_2 \approx 4/3$. The exponent should therefore be $-2$, since $1/3 = 4/3 \cdot 2^{-2}$. The exponent itself is stored with an offset of $1024$ (or more generally, $2^{w-1}$, where $w$ is the width of the exponent field), that is, instead of $-2$ we actually store $1022$, which in binary reads $01111111101$.

You should note that the floating point number doesn't represent $1/3$ exactly, rather a number pretty close to $1/3$. The only numbers representable exactly in floating point (given enough precision) are dyadic numbers, which are numbers of the form $A/2^B$ (for integer $A,B$).


A* Search Algorithm Implementation with Priority Queue

Yes, you move on with A.  You always pick the element in the fringe that minimizes $h(x) = f(x) + g(x)$.


Why floating point representation uses a sign bit instead of 2's complement to indicate negative numbers

Two's complement makes sense when the two entities in question have the same "units" and the same "width". By width I mean that, say, if you're adding an N bit number and an M bit number, where N and M are different, then you better not use two's complement. For floating point numbers, we have the problem of units: if the exponents are different, then we are mentally shifting one of the mantissas, and now we're at the same problem as before (with the width).

As for the exponent bits, by using a bias instead of sign+magnitude we gain one more value (otherwise we'd have +0 and -0). Here two's-complement makes sense when multiplying or dividing numbers (since then we're adding or subtracting the exponents), but not as much sense when adding or subtracting.

Edit: A commenter remarked that you can add two's complement integers of different lengths using sign extension. There is also some problem with detecting overflow, but that's also fixable. In summary, you could probably use two's complement, if you're careful enough. (You also need to handle multiplication and division.)


Proving that a Turing machine decides a language in NP

In general, ZF does not prove that $T$ decides $L$, unless ZF is inconsistent.

Take e.g. $L$ to be the language of words having even length (which is in P, hence in NP).

Consider the TM $T$ which on input $w$, crafts the first $|w|$ proofs in ZF.
If any such proof proves a contradiction, accept.
Otherwise, accept if and only if $|w|$ is even.

We note that $T$ decides $L$ if and only if ZF is consistent. So, if ZF can prove that $T$ decides $L$, it is proving its own consistency, hence by Godel's second incompleteness theorem ZF is inconsistent.


Differences between substitution and rewriting?

There are three differences between substitutions and rewriting systems:

Substitutions happen one symbol at a time, while a rewrite rule can rewrite an entire substring at once.
Substitution is a single-valued function while in a rewriting system, several rewriting rules can apply to any given substring.
A substitution must specify what value is substituted for each symbol. Rewriting systems need not apply in all situations.

I would say that the first two are the major differences. You can define substitutions so that they are partial functions, and then the third difference doesn't apply.


An exact solution for biclique vertex-cover problem on a bipartite graph

If you have an exact algorithm for the partitioning problem (perhaps one is mentioned in the paper describing the approximate algorithm?), you immediately have an exact algorithm for the covering problem.

First, observe that a partition is a valid cover.  Now suppose the partitioning algorithm reports an optimal partition with $k$ bicliques, and suppose to the contrary that there exists a cover $C$ with fewer than $k$ bicliques.  But any cover can be turned into a partition easily: Whenever two bicliques in the cover contain the same vertex, delete the vertex from one of them.  (This works because bicliques are hereditary: every induced subgraph of a biclique is also a biclique.)  This will result in a valid cover with at most as many bicliques as there were originally (it may cause a biclique to have zero vertices: In that case, the original cover was not minimal).  Repeat this vertex deletion step until all bicliques are pairwise vertex disjoint.  If we apply this to the cover $C$, then because we started with strictly fewer than $k$ bicliques and never increased the number of them that we have, we now have a partition with strictly fewer than $k$ bicliques, contradicting the known optimal solution from the partition solver.  Thus the optimal partition must have also been an optimal cover.


You can say whatever you want as long as it is accurate.  Both $O(n)$ and $O(\text{Depth})$ are accurate, so you can say either one.  $O(\text{Depth})$ is more descriptive, since $\text{Depth} \le n$ always holds.

I don't know why you don't think it provides any insight; I think it does provide some potentially useful information.


Prove that the set of recursive languages is infinite


How do you classify properties as Trivial and Non-trivial?

A property $P$ is a set of Turing machines. The property is trivial if it contains every TM, or if it is empty.

Essentially, in order to check if a property is trivial, just check if there is a TM that satisfies it and if there is a TM that does not satisfy it. If both kinds exist, then the property is nontrivial. Otherwise it is trivial.

However, deciding this can be difficult...

For example, consider the property $\{M: L(M)=\emptyset\}$. This is a non-trivial property, since there are TMs with an empty language, and there are TMs with a nonempty language.

A trickier example is $\{M: L(M)\in RE\}$. Initially, this may seem like a nontrivial property. But recall that every TM recognizes its own language. So $L(M)$ is in RE for every $M$. Thus, this property is simply the collection of every TM. So it is trivial.


Languages that are not subset, but are union

Yes. Let $L_1=\{a\}, L_2=\{\epsilon\}$. Obviously both languages are regular and neither is a subset of the other. We then have
$$
(L_1\cup L_2)^*=(a+\epsilon)^*=a^*
$$
and since
$$
L_1^*=a^*,\quad L_2^*=\epsilon^*=\epsilon
$$
we have
$$
L_1^*\cup L_2^*=a^*\cup \epsilon = a^*
$$


Are all countable partial functions computable?

You must be mistaken about a definition.  It is not that any single computable partial function is countable.  Rather, the set of all computable partial functions is a countable set.  (There isn't any such thing as a countable partial function.)


Can you connect an output from a logic gate to 2 or more logic gates or inputs?

In circuit complexity, the fan-out of a gate is the number of gates its output is connected to (similarly, the fan-in is the number of inputs to the gate). A circuit in which all gates have fan-out 1 is known as a formula. It is known that some $n$-bit functions can be computed by circuits of size $O(2^n/n)$ but require formulas of size $\Omega(2^n/\log n)$. It is conjectured that polynomial size circuits can compute more functions than polynomial size formulas, but this conjecture, known as the $\mathsf{NC^1} \stackrel?= \mathsf{P}$ question, remains unproved.


Given list of numbers find for each number in the list the next distinct number

Here is pseudocode for an algorithm which outputs the entire answer array $a_1,\ldots,a_n$:

Set $\mathit{first} \gets 1$ (first index in the current run)
Set $\mathit{curr} \gets 1$ (index of the current element being scanned)
While $\mathit{curr} < n$:
   Set $\mathit{curr} \gets \mathit{curr} + 1$
   If $l_{\mathit{curr}} \neq l_{\mathit{first}}$:
     Set $a_{\mathit{first}},\ldots,a_{\mathit{curr}-1} \gets l_{\mathit{curr}}$
     Set $\mathit{first} \gets \mathit{curr}$
   End If
End While
Set $a_{first},\ldots,a_n \gets \bot$ (no different element to the right)

This algorithm uses linear time and $O(1)$ auxiliary space.


Categorization of Binary search as Divide and Conquer

This might seem silly but here we go.

Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$.

The divide step - We divide our search space into two ranges - $[L,mid-1]$ and $[mid,R]$.
The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x < A[mid]$. Then we combine the knowledge that $x$ can be in $[L,mid)$ and $x$ cannot be in $[mid,R]$ to reduce our search space to $[L',R'] = [L,mid-1]$


Being a computer organizations and architecture expert

Study and practice for years.  Years and years.
No one understands all of it.  Everyone specializes.
People get a broad sense of the field, but they don't learn all of it.  Then, they learn what they need to know, when they need to know, and only then.

So, keep at it.  You can understand enough to be effective, even if you don't know everything.


ARM STM instruction: page fault problem with MMIO

What if the STM instruction were executed speculatively, and an instruction ahead of it faults? Or it's behind a mispredicted branch?

I can't speak for all ARM variants (things have probably changed over time), but the semantics of any instruction must be that if the instruction causes a fault, it's as if the instruction didn't happen.

What modern ARM cores probably do is use the store buffer. All stores (apart from TCM, which is by definition not MMIO) go through the store buffer. The only difference is in how the store buffer is flushed.

Presumably the store buffer has enough entries to satisfy a STM instruction. If the instruction (or an instruction ahead of it) faults, the relevant entries in the store buffer are purged. When the instruction retires (i.e. when it reaches the head of the reorder buffer), the stores are released for writing.


If you're interested in knowing the big-oh (O) then :
logn (for first for statement) * (n-logn) times

Therefore, n*logn - log^2(n)

For big oh complexity, the complexity for above mentioned nested loops would be:

n*logn (since big-oh is only interested in larger values)

And as David motioned, that link has detailed explaination.


$O(n^2)$ running time vs $O(n^2)$ worst case

Suppose that you have an arbitrary array of $n$ numbers, and you give it to  Quicksort to sort.
The expected running time of the algorithm is $O(n \log n)$.  However, if the array is sorted, but in the wrong direction, and you pick the first element as pivot, then the algorithm might actually run in time $O(n^2)$.
That means that if you look at how Quicksort behaves with increasingly larger arrays of reversely sorted data, the time it uses grows as $n^2$.
However, if you spend $O(n)$ time to shuffle the array before sorting it, the expected running time is $O(n \log n)$; i.e. very few time will the algorithm spend close to $O(n^2)$ many operations.

A different example is with respect to amortized complexity.  For example, adding a single element to an ArrayList in Java takes $O(1)$ time, most of the time.  However, on a rare occasion, Java needs to create a new array and copy all the elements over to this new one.  That takes $O(n)$ time.
This means that the worst case complexity for ArrayList.add is $O(n)$, but if you do this operation $n$ times, the total complexity is also $O(n)$, so we say that the amortized complexity is $O(1)$.


What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy?

Mathematicians and philosophers often assume that machines (and here, he probably means "computers") cannot surprise us. This is because they assume that once we learn some fact, we immediately understand every consequence of this fact. This is often a useful assumption, but it's easy to forget that it's false.

He's saying that systems with simple, finite descriptions (e.g., Turing machines) can exhibit very complicated behaviour and that this surprises some people. We can easily understand the concept of Turing machines but then we realise that they have complicated consequences, such as the undecidability of the halting problem and so on. The technical term here is that "knowledge is not closed under deduction". That is, we can know some fact $A$, but not know $B$, even though $A$ implies $B$.

Honestly, though, I'm not sure that Turing's argument is very good. Perhaps I have the benefit of writing nearly 70 years after Turing, and my understanding is that the typical mathematician knows much more about mathematical logic than they did in Turing's time. But it seems to me that mathematicians are mostly quite familiar with the idea of simple systems having complex behaviour. For example, every mathematician knows the definition of a group, which consists of just four simple axioms. But nobody – today or then – would think, "Aha. I know the four axioms, therefore I know every fact about groups." Similarly, Peano's axioms give a very short description of the natural numbers but nobody who reads them thinks "Right, I know every theorem about the natural numbers, now. Let's move on to something else."


Deciding whether a Language is Context-free/Regular/Non Context-Free

Your reasoning for the positive statements seems sound to me, although they lack some detail if formal proofs are required. In particular, you might at least want to give the automata for $L_4,L_5,L_6$ and $L_7$; especially the latter can be considered non-trivial, depending on your level of expertise.

You lack proofs for

$L_2 \notin \mathrm{REG}$ and
$L_3 \notin \mathrm{CFL}$.

Both are true and straight-forward to prove; you find all you need in our reference questions for the regular and context-free case, respectively.


Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?

You are asking several questions. I will only answer some of them.

Suppose that the running time of an algorithm as a function of $n$ satisfies $T(2^k) = O(2^k \log 2^k)$. Is it true that $T(n) = O(n \log n)$? Without any more information on the running time, this is patently false. For example, consider the function
$$
T(n) = \begin{cases} n\log n & \text{if $n$ is a power of $2$}, \\ n^2 & \text{otherwise}. \end{cases}
$$
However, in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold. Suppose that $T(n) \leq Cn\log n$ whenever $n$ is a power of $2$. Given arbitrary $n$, we can find $m \leq 2n$ which is a power of $2$, and then
$$
T(n) \leq T(m) \leq Cm\log m \leq 2Cn \log n + O(n) = O(n\log n).
$$

Suppose now that there is a data structure such that the first $n$ operations take time at most $Cn$ whenever $n$ is a power of $2$. If we let $T(n)$ denote the maximal time that $n$ operations take, then $T$ satisfies the conditions stated above (in particular, monotonicity is built-in), and so the amortized time per operation is indeed $O(1)$. Your case is a bit more complicated since different operations have different amortized running times, but the conclusion should be the same.


No. Any algorithm to locate those two peaks will take $\Omega(N)$ time, assuming that the only operation allowed is to compare two elements in the array, i.e., the comparison mode.

Otherwise, suppose algorithm $A$ do not need that much time. Let $arr[0], arr[1], \cdots, arr[N-1]$ be the given array. Then for some $N$ large enough, $A$ will have only checked at most $N-3$ elements before it has terminated. Suppose for all comparisons that have done by $A$, it will be found that $arr[i] < arr[j]$ where $i<j$.

Let $arr[a], arr[b], arr[c]$ be three elements that have not been checked yet, $a<b<c$. Whatever $A$ have done, the two peaks could be $\{arr[a], arr[N-1]\}$. They can be $\{arr[b], arr[N-1]\}$ as well. Since $A$ cannot distinguish these two cases, $A$ cannot possibly have determined the two peaks.

Exercise. (less than one minute) Modify the above argument so that it becomes valid in the case when a peak must have both left neighbor and right neighbor.


First, let us notice the following:
$$
L(S) = \{ xyz \mid x,z \in \{0,1\}^*, |x|=|z|, y \in L(A) \} \\
L(A) = 0L(B)1 \cup 1L(B)0 \\
L(B) = (0+1)^*
$$
Putting everything together, we get
$$
L(G) = \{ x\sigma y \tau z \mid x,y,z \in \Sigma^*, \sigma,\tau \in \Sigma, |x|=|z|, \sigma \neq \tau \}
$$
In other words, a word $w$ is in the language if there exists $i \leq |w|/2$ such that the $i$th symbol from the left is different from the $i$th symbol from the right. The condition $i \leq |w|/2$ can be eliminated, and we get that for some $i$, the $i$th symbol of $w$ is different from the $i$th symbol of $w^R$. In other words, $w \neq w^R$.

So your grammar generates the language of non-palindromes.


Try this: Legendre's_three-square_theorem

Assume $4\not\mid N$. If not, divide $N$ by $4^k$ and multiply $2^k$ back in the end. Find an $A$ satisfying $N-A^2\not\equiv0,4,7 \mod 8$. It's always valid to choose $A=\lfloor\sqrt{N}\rfloor$ or $\lfloor\sqrt{N}\rfloor-1$. (Choose the even one if $N\equiv 1,5 \mod 8$ and the odd one otherwise.) Now $N-A^2$ is an integer in $O(\sqrt{N})$ and you can find $B,C,D$ in $O(\sqrt{N})$ easily.

Edit: Since $B,C,D\le cN^{\frac{1}{4}}$ for some small constant $c$, we can enumerate two of them (suppose $B$ and $C$) and check whether the corresponding $D$ is an integer. This works in $O(\sqrt{N})$. There might be some faster solutions.


Comparing the sizes of two search spaces by comparing their numbers of possibilities

There is no easy way to predict which ILP model will be faster to solve.  Counting the number of variables is not a reliable predictor.  Estimating the size of the "search space" (the number of feasible solutions) is not a reliable predictor.  There is, in general, no fully reliable way to tell which model will be faster -- short of actually trying both.

Instead, my recommendation is that you try experiments.  Try solving both models, and see which takes longer to solve.  If your problem is parameterized in size, you can try solving for smaller sizes and see if a pattern emerges.


Travelling Salesman: Big O Complexity when starting city is fixed

The start city makes no difference. You're constructing a tour through all the cities, so it doesn't matter if you do ABCDEA or CDEABC.

Held–Karp solves TSP in time $O(n^22^n)$, which is much faster than $\Theta(n!)$.


How to count all contiguous subsequences with positive sum?

Given the array $A_1,\ldots,A_n$, start by computing $B_i = \sum_{j \leq i} A_j$. You want to count the number of pairs $i_1 < i_2$ such that $B_{i_1} < B_{i_2}$, where $0 \leq i_1,i_2 \leq n$. Each such pair corresponds to a a contiguous subsequence $A_{i_1+1},\ldots,A_{i_2}$ whose sum is positive. This is the same as the classical problem of counting the number of inversions in an array (this is what you get if you reverse $B$), which can be solved in $O(n\log n)$.

It is plausible that you can do better in your case since the numbers are $\pm 1$.


Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution

One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n < 2m$, where $m = 2^k$. Then
$$
 T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n).
$$
Details left to you.


I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here.

It is not possible to sort in $O(n)$ for one of the other bounds. Indeed, the problematic part would be sorting values not in the bounds $[\sqrt{n}, n\sqrt{n}]$: sorting $\frac{n}{2}$ values requires $\Omega(n\log n)$ time.
On the other hand, sorting $\frac{n}{\log n}$ values can be done in $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ time.


If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$

$\newcommand{\co}{\mathsf{co}\text{-}}$

Let $A\subseteq \Sigma^*$ be some class of languages. Saying $\co{A}\subseteq A$ means that $A$ is closed under complement, and this is equivalent to $\co{A}=A$.

To show the other direction, $A\subseteq \co{A}$, let $L\in A$ be some language in the class $A$. $\overline{L}\in \co{A}$, and since we know $\co{A}\subseteq A$, we have $\overline{L}\in A$, which means $L\in \co{A}$.


Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?

Try constructing an NFA for $\hat L:=\{w|$ there is an odd length prefix of $w$ that is $\notin L\}$, given a DFA for $\overline L$, and then show $L_1=\overline {\hat L} $.

If I'm not mistaken, this should work out.


The parametrization you present is quite arbitrary, and the condition that the mapping be onto only serves to confuse; let's ignore it for now. Instead, given $n,c$, let us consider the number of colorings of $K_n$ using $c$ colors (in your case, $c=n-2$) such that condition (3) is satisfied: for every three vertices $i,j,k$,
$$ c(i,j) \leq \max(c(i,k),c(j,k)). $$
What does this condition mean? Let's start by considering the case $c = 2$. For any triangle $i,j,k$, the only situation which is forbidden is
$$ \{c(i,j),c(i,k),c(j,k)\} = \{1,1,2\}. $$

Let $G$ be the graph formed by the edges colored $1$. This condition states that if $(i,j),(i,k) \in G$ then also $(j,k) \in G$. It is not hard to prove that $G$ must be a disjoint union of cliques, and vice versa, every disjoint union of cliques satisfies the condition.

If $G$ is a disjoint union of cliques then the vertex sets of the cliques partition $[n]$; isolated vertices are considered as cliques of size $1$. Therefore the number of possible graphs (and so, possible colorings when $k = 2$) is the Bell number $B_n$.

The case of general $c$ is similar. Consider for example $c = 3$. The graph induced by edges colored $1,2$ must be a disjoint union of cliques, and within each such clique, the graph induced by edges colored $1$ must be a disjoint union of cliques. Therefore each possible coloring corresponds to a two step partition of $[n]$: first we partition $[n]$, and then we further partition each of the part. The number of such two step partitions is a so-called higher-order Bell number, the row $p = 2$ in this case. For general $c$, consult this table at row $p = c-1$.

Finally, what if we want to count the number of onto mappings? We can use the inclusion-exclusion principle. Let $X(n,C)$ denote the number of colorings using colors from $C$, and let $X(n,c) = X(n,[c])$; note that $X(n,C) = X(n,|C|)$. Also let $Y(n,C),Y(n,c)$ denote the number of onto colorings. We have

$$ Y(n,c) = Y(n,[c]) = \sum_{D \subseteq [c]} (-1)^{c-|D|} X(n,D) = \sum_{i=0}^c (-1)^{c-i} \binom{c}{i} X(n,i). $$

For example, if $n = 4$ and $c = 2$ then
$$ Y(4,2) = \binom{2}{0} X(4,2) - \binom{2}{1} X(4,1) + \binom{2}{2} X(4,0) = 1 \cdot 15 - 2 \cdot 1 + 1 \cdot 0 = 13. $$

How do we compute $X(n,c)$? The page linked to above gives the following recurrence:

$$
X(n,1) = X(0,c) = 1, \quad X(n,c) = \sum_{k=1}^n \binom{n-1}{k-1} X(k,c-1) X(n-k,c).
$$


What is the origin of λ for empty string?

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics.

Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty string, with the same justification.


Well, it depends of the kind of automata you are using. Roughly speaking, finite automata can only count modulo $d$ for some fixed $d$: for instance, you can test whether a word contains an odd number of $0$ or whether its length is a multiple of $5$. For your problem, finite automata will not suffice and you need a more powerful model of automata, for instance a pushdown automaton.


Probability of terminating in a state in a probabilistic algorithm

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a move to $b$. When $a=b=0$, we arbitrarily define $\ell(0,0) = 1$ and $r(0,0) = 0$.

If we are at the situation counted by $\ell(a,b)$, then known formulas show that we move to the situation counted by $\ell(a-1,b)$ with probability $1-1/(b-a+2)$, and to the situation counted by $r(a,b+1)$ with probability $1/(b-a+2)$. Together with an analogous argument for $r(a,b)$, this gives the recurrences
$$
\ell(a,b) = \left(1 - \frac{1}{b-a+1}\right) \ell(a+1,b) + \frac{1}{b-a+1} r(a+1,b), \\
r(a,b) = \frac{1}{b-a+1} \ell(a,b-1) + \left(1 - \frac{1}{b-a+1}\right) r(a,b-1).
$$
We want to show that for $i=1,\ldots,n-1$,
$$
r(i-n+1,i) + \ell(i-n,i-1) = \frac{1}{n-1}.
$$
We will prove the stronger result
$$
r(i-n+1,i) = \frac{i}{n(n-1)}, \\
\ell(i-n,i-1) = \frac{n-i}{n(n-1)}.
$$
When $n=2$, we need to show
$$
r(0,1) = \ell(-1,0) = \frac{1}{2},
$$
which can be checked directly. For $n > 2$, we have
$$
r(i-n+1,i) = \frac{1}{n} \ell(i-n+1,i-1) + \frac{n-1}{n} r(i-n+1,i-1) = \\
\frac{1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{n-1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{i}{n(n-1)},
$$
and similarly
$$
\ell(i-n,i-1) = \frac{n-1}{n} \ell(i-n+1,i-1) + \frac{1}{n} r(i-n+1,i-1) = \\
\frac{n-1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{1}{n} \frac{i-1}{(n-1)(n-2)} =
\frac{n-i}{n(n-1)}.
$$
(We don't really need to calculate the two cases separately, since symmetry arguments show that $r(i-n+1,i) = \ell(-i,n-i-1)$.)


Longest simple walk below a certain weight

Without the "vertex-transitive" restriction, the problem is NP-hard, by reduction from Hamiltonian path.

Without the "vertex-transitive" or "number of neighbors" restrictions, the reduction is easy: set $w$ equal to the number of vertices minus one, and assign weight 1 to all edges.  To accommodate the restriction on the number of neighbors, replace each node with a network of nodes shaped like two trees connected at their roots; each in-edge connects to a leaf of the first tree, and each out-edge connects to a leaf of the second tree, and put weight 0 on all the tree edges.

I don't know if this reduction can be extended to handle the case of vertex-transitive graphs as well.


Are there 3-colorable maps that can never be colored?

Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

Every formal statement in propositional logic can be translated to a map 3-coloring instance. The video is being very sloppy with calling this 'every mathematical statement', as there's many mathematical statements that aren't captured in propositional logic.
Propositional logic is decidable (it's equivalent to the SAT problem).


Complexity of transposing matrices represented as list of row or column vectors

If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.


How can I partition a graph such that as few edges as possible cross partition boundaries?

Your problem is known as graph partition. Apart from $n$, the problem has a parameter $\epsilon \geq 0$, and it is required that each part have size at most $(1+\epsilon)|V|/n$. The Wikipedia article mentions several relevant algorithms. The case $n = 2$ is known as minimum bisection when the parts are required to be exactly equal, and this is a well-known special case.


This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an indicator that you performed one division (since after erasing the first triplet you will have the space to store this "1"). Then you have to bring all the new zeros together and repeat the procedure. The number of ones you have written will be equal to $k$ (and if at some point you cannot perform the division, that is you don't have a power of three - you reject the language).
Next, you begin erasing the ones that come after zeros. Each turn will consist of wiping out exactly $k$ ones - for example the $k$ ones that you have on the left can be replaced by zeros in order to indicate that a one on the right has been erased. At the end of the turn, you replace all the zeros by ones again. Again, if you cannot perform the whole round, you must reject the language.


First problem to be considered np complete?

You can find the original paper of Cook online: The complexity of theorem-proving procedures. You can also find Levin's paper in Russian: Universal Sequential Search Problems. A translation can be found in the appendix to a historical survey by Trakhtenbrot: A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms. You can even find Karp's Reducibility Among Combinatorial Problems.

Cook showed that the set of DNF tautologies (i.e., the complement of SAT) is NP-complete in his sense (oracle reducibility). Karp mentioned that SAT is actually NP-complete with respect to many-one reductions. Levin's paper mentions six different problems, but has no proofs (as was customary).


Segmentation technique for handwritten text (cursive and unconstrained)

As mentioned in comments there is no one right way to recognize handwriting. That said, Here are two techniques you could explore.

Watershed segmentation works by creating a topological map of the image to determine which objects distinct and with or without connection to other objects. I recommend it to you because watershed excels at naturally or man-made round objects. It has been documented for use in handwriting recognition. This is an easy one to get started with too. You can simply call watershed in matlab, OpenCV, or scikit

Machine Learning / Deep Learning (ML) is a daunting term to some but we usually get the chance to stand on the shoulders of giants such that ML on images is about as difficult as editing an large collection of vacation photos. Bag of words is a particular technique which works well on finite object sets. Note that like most ML BoW requires pre-classified training materials so be prepared to provide at least 100 different samples of a cursive uppercase 'Q' along with all the other characters you wish to recognize. Nonetheless, if you've got the time and resources to train it, a ML solution can be incredibly powerful in handwriting recognition.


How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine

An answer shamelessly copied from myself:

A multi-tape Turing Machine is mostly the same as a single-tape machine, except we have an extended transition function $Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$ where $k$ is the number of tapes. So in each state, the transition function reads the contents of each tape, moves to a new state, (maybe) writes something on each tape and moves each head - just as a regular TM, except now we have more things to read, write and move.

As your question suggests, such a machine can be simulated by a single-tape TM. Even better, it can be done with only quadratic slowdown (so for polynomially closed classes, it's sufficient to talk about single-tape machines).

The proof for this is somewhat involved, and easily available with a simple web search, so I'll just sketch the key mapping of the $k$ tapes to a single tape.

The basic idea is pretty straightforward; we simply add a few new symbols and keep track of each tape and head one after the other. At each step in the computation we can only have visited a finite amount of any of the tapes, so we need only to store this much information about each tape. Thus for each $\gamma \in \Gamma$ we add a new symbol $\underline{\gamma}$ to $\Gamma$ which will indicate where the head (for each tape) is at any point in the computation. We also introduce a separator character $\#$ to $\Gamma$ which will indicate the start and end of the "virtual" tapes. Given input $\omega = \omega_{1}\ldots\omega_{n}$ (we can assume that even on the multi-tape machine all of the input is on the first tape - proving why is a good exercise) on the multi-tape machine, our single-tape machine will have input
$$
\underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots
$$

We then use the state of the single-tape machine to encode what state the multi-tape machine is in and what the heads are looking at. The transition function of the single-tape machine is a multistage simulation of the multi-tape transition function, where we perform the $k$ different tape actions appropriately, moving up the single tape to each section in turn. The only wrinkles left are shifting everything along when we run out of space in a section (but such a sub-machine is a simple exercise) - we never reduce the size of each section.

A (hopefully) simple example:

Say we have a 3-tape TM, where the input alphabet is just $\Sigma=\{0,1\}$, the tape alphabet is $\Gamma=\{0,1,\sqcup\}$ and the input is $\omega=10101$. The initial tape state of the machine looks like:
$$
\begin{array}{lc}
\text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$
The "$\wedge$" is to denote where the read/write head is on each tape.

To construct the combined single-tape machine, we need to add new symbols to the tape alphabet:

We need a symbol that will denote the start and end of the simulated tapes
For each symbol in $\Gamma$ we also need a version that indicates that the simulated tape head is at that character on the simulated tape.

So for the single-tape machine, our new tape alphabet is $\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$. The initial state of the tape is:
$$
\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$
Note the difference between the head of the machine (the $\wedge$) and the simulated heads of the 3 simulated tapes (the underlined characters). Of course the tape extends infinitely to the right as usual. I have also cheated mildly by moving the tape head to the first character on the first string; strictly it should start out on the leftmost cell, but this is a trivial technicality.

So we have three marked out sections (between the $\#$ marks), which will correspond to the 3 tapes of the original machine.

Now let's make up an action for the machine. Let's say that the original machine reads from the first tape, if it sees a $1$, it writes a $1$ on the second tape, if it sees a $0$ it writes a $1$ on the third tape. At each read or write, the head moves to the right.

So after the first "step" (perhaps requiring several states and transitions in the actual machine), the tapes should have a $1$ on the second tape, and the first and second heads will have moved right one step:

$$
\begin{array}{lc}
\text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$

On the second go around, the first tape reads a $0$, so we write to the third tape instead:

$$
\begin{array}{lc}
\text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$

The single-tape machine simulates this by moving the underline (by using the alternate version of the characters in $\Gamma'$, and writing to the appropriate simulated tape. So after the first step, the combined tape looks like:

$$
\#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$

After the second step:

$$
\#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$

Of course this is a high level view of the process - I haven't attempted to explain how to construct the states, or how each simulated tape gets longer (for this, you need a little routine that checks if you've run into the end of the simulated tape, then moves everything to the right one step along and squeezes in a new blank - i.e. it only adds simulated tape cells when they're needed).


Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?

Pumping lemma works easily. Somewhere it says "if the language is regular then for every string in the language..." Just check the pumping lemma for strings that start with exactly one a.


Number of maximal cliques in graphs without common neighbourhoods

Suppose that $n$ is a perfect square, and identify its vertex set with $\{1,\ldots,\sqrt{n}\}^2$. Connect $(a,b)$ to $(c,d)$ if $a \neq c$ and $b \neq d$. You can identify a vertex from the set of its neighbors, so the open neighborhoods are all distinct. The number of maximal cliques is $\sqrt{n}!$, which isn't polynomial.


Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?

You can reduce the Exact Cover problem to your problem. The elements in the Exact Cover problem corresponds to the balls in your problem. For each subset $T$ in the Exact Cover problem, we construct a bin $i$ with $S_i=\{\emptyset, T\}$. Then there exists an exact cover if and only if all balls can be put into the bins. Hence, your problem is NP-hard.


Proving correctness of search algorithms

The idea of the algorithm is to maintain the following invariant:

  If $x$ is in the matrix, then it is in the submatrix whose top right corner is $e$.

The invariant clearly holds in the beginning, since $e$ is the top right corner of the original matrix.

If $e > x$ then all elements below $e$ are also larger than $x$, and so $x$ cannot be contained in that column. Therefore the invariant continues to hold with $e$ replaced with its left neighbor (if $e$ has no left neightbor, we can deduce that $x$ is not found in the matrix).

If $e < x$ then all elements to the left of $e$ are also smaller than $x$, and so $x$ cannot be contained in that row. Therefore the invariant continues to hold with $e$ replaced with its neighbor below (if any).

On an $n \times m$ matrix, this process terminates in at most $n+m$ steps, either finding $x$ or determining that it does not appear in the matrix.


Check for common element in two arrays using FFT

This one is a bit esoteric, but:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
Could be decomposed to (as noted by @NotDijkstra)
$$
\prod_{i=1}^{n} p(x_i)
$$
where
$$
p (x) = \prod_{j=1}^{n} (x - y_j)
$$
reduces to a polynomial with roots $y_i$. Coefficients of this polynomial could be computed with FFT, see https://arxiv.org/pdf/1608.01357.pdf. It could be done even faster using divide and conquer strategy - recursively split the formula into two polynomials and multiply them with FFT (see answers).
Polynomial representation in its turn would allow fast exponentiation of x, or even multi-point evaluation
Although, I don't see any advantages over traditional approach in terms of speed or complexity except if it's implemented on specialised ASICs/FPGAs/GPUs.


Exhaustive list of ways to distribute n objects to k sets

The objects you are interested in enumerating are counted by Stirling numbers of the second kind. In particular, $\genfrac{\{}{\}}{0pt}{}{n}{k}$ is the number of ways to partition a set of size $n$ into $k$ non-empty parts. The Stirling numbers satisfy the recurrence
$$
\genfrac{\{}{\}}{0pt}{}{n+1}{k} = k\genfrac{\{}{\}}{0pt}{}{n}{k} + \genfrac{\{}{\}}{0pt}{}{n}{k-1}.
$$
Indeed, either element $n+1$ is in a partition of its own, or it joins one of the other $k$ parts. The initial conditions are $\genfrac{\{}{\}}{0pt}{}{0}{0} = 1$ and $\genfrac{\{}{\}}{0pt}{}{0}{n} = \genfrac{\{}{\}}{0pt}{}{n}{0} = 0$ for $n > 0$. In other words, if $n = k = 0$ then there is a unique solution (the trivial solution), and if $n = 0$ or $k = 0$ otherwise then there are no solutions.

You can use this recurrence to recursively generate all partitions you are after.


Power of nondeterministic type-1 min-heap automaton with both a heap and a stack

A heap and a stack can both be used to implement a counter. 2 counters suffice to recognize $RE$. (See also)


What does Arora mean by 'computational history'?

The computational history consists of the contents of the tape of the Turing machine after each step. These are the variables in the SAT instance produced by the Cook-Levin theorem, which is the combinatorial problem which represents the computational history.

This representation is fragile in the sense that even when the SAT instance is unsatisfiable, we may be able to satisfy almost all of its clauses - say, all but a constant number. This is because the reduction in the Cook-Levin theorem is very local: if we flip a single bit in the computational history, then this falsifies only a small number of clauses.
In contrast, the PCP theorem guarantees that the SAT instance is either satisfiable or at most 99% of its clauses can be satisfied, and this implies a hardness of approximation result for MAX-SAT.


A problem similar to the Bin packing problem?

One way to solve your problem is to use binary search over the maximum weight.  In other words, pick a threshold $t$, and check whether it's possible to pack your items into $m$ bins, without using more than a total weight of $t$ in each bin.  This is exactly the bin packing problem: is it possible to pack the items into $m$ bins of capacity $t$?  You can apply any algorithm for bin packing to this problem.  Then, use binary search on $t$.

Be warned that it is NP-hard, so don't expect an efficient algorithm that produces the optimal solution in a reasonable amount of time for large problem instances.


What is the time complexity in solving a polynomial equation of degree N in one variable?

The time complexity doesn't just depend on N. It's possible that due to the coefficients, you have to evaluate the polynomial with very high precision to determine whether some minimum of the polynomial near a point x has a value >0, =0 or <0, and you need to know this to know the number of roots near to x (0, 1, or 2).


What you have to do is systematic search for a string $x$ such that $f_w(x) = |x|$ or in other words $M_w(x) = |x|$. Given $w$ your TM $M$ should try ALL  input strings $x$, not just to simulate  $M_w$ on a single $x$.

If you wait $M_w(x)$ until it halts then you ($M$) may stuck in case $M_w$ does not halt on $x$. So, that option is not possible.

One possible way is to systematically try all pairs $(x,i)$ which means  "simulate $M_w(x)$ for $i$ steps". Your strings may be encoded an put in one to one correspondence with integers. So a pair $(i,j)$ means simulate $i$th string $s_i$ for $j$ steps on $M_w$. Each time you simulate $(i,j)$ you check if after $j$ steps $M_w(s_i)$ halts and if yes then compare its output with $|s_i|$. If the output is equal to $|s_i|$ then ACCEPT and halt, otherwise you go to the next pair $(i,j)$. Thus so on until you ($M$) find a pair $(i,j)$ such that $M_w(s_i)$ halts after $j$ steps and its output is equal to $|s_i|$.

In other words, you simply give a chance to your machine $M$ to run on every $x$ for a certain number of steps, and after running for the certain number of steps you check if it halts and if it halts you compare its output with the input length.

Now to prove that it is semi-decidable notice that if indeed there is $x$ such that $f_w(x) = |x|$ then there are integers $m$ and $n$ such that $s_m = x$ and $M_w(s_m)$ halts after $n$ steps. You will eventually find that pair $(m, n)$ after a finite number of steps since you systematically try all pairs $(i,j)$. If such pair does not exist at all then your machine never halts and will run forever. Thus that set is semi-decidable.    Similar post


Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:

  Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.


Why is finding minimum number of comparisons to sort $n$ elements so difficult?

Let's say the size of the array is such that there are $2^{k-1} < x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons.

Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible permutations into two subsets, each of size at most $2^{k-1}$. And each subset you need to split into two subsets of size at most $2^{k-2}$ etc. If these subsets don't have the same size, then after j comparisons the size of the largest subset could exceed $2^{k-j}$, and you lost.


Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$

The three options have different meanings in mathematics:

The first option means that $x$ increases as $N^2$ increases.
The second doesn't really make sense.
The third has the meaning you are presumably after (perhaps "with" is better replaced by "in").

You can rephrase the first two options as follows:

$x$ grows as $N^2$ - this is informal, and doesn't differentiate between $x \sim N^2$ and $x = \Theta(N^2)$.
$x$ grows as $O(N^2)$ - this is an awkward phrasing, and it is better to use symbols: $x = O(N^2)$. Note, however, that this is not the same as your third option - it corresponds to $x$ growing at most quadratically in $N$. To get the same meaning, you have to use big Theta: $x = \Theta(N^2)$.

You mention rigor. Rigor is a property of proofs, whereas here there are no proofs. Your descriptions might be informal, but could help explain rigorous proofs.

The best two options are "$x$ grows quadratically in $N$" and $x = \Theta(N^2)$". Both are acceptable.


You don't get an empty list. See this. However you won't get the desired results because in python int divided by int is always int.  You may want to try this:

import math

factor_list = [ ]

def integer_test(x):

    if math.floor(x) == math.ceil(x):
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(1.0 * x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

In this code x/count is a double. So the integer_test will only return true if it's ceiling and floor return the same number i.e the integer itself.


Find the number of words in a language of given length

You can solve the general problem using linear algebra. First, construct a DFA for the language $S^*$. Then, describe its transition function in matrix form: if the state space is $Q$, construct a $Q \times Q$ matrix $A$ in which $A(s_1,s_2)$ is the number of letters that would cause a transition from $s_1$ to $s_2$. If $s$ is the starting state, let $1_s$ be the corresponding vector, and let $j$ be the all-one vector. The number of words of length exactly $n$ is $1_s A^n j$ (or perhaps $j A^n 1_s$ if I mixed things up). You can use the spectral decomposition of $A$ to get a formula, or you can calculate it quickly using repeated squaring.

That is the general theory. In your case, it's not too hard to enumerate all words of length up to $7$ by hand. I challenge you to do that.


Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it?

Your understanding is not correct. There are two major programming paradigms: imperative programming and declarative programming.

In imperative programming you basically tell your computer what to do to solve a certain problem by providing an algorithm which might be implemented as a composition of different functions and/or methods. Often one distinguishes between object-oriented and procedural programming as the two main subparadigms of imperative programming, where the latter one is often scripting but the lines between scripting and "software engineering" (i.e. writing fully fledged programs) is blurry. Procedural programming can be engineerish, too.

In declarative programming you do not tell your computer how to solve the problem but rather what is the problem. Again, one might distinguish between subparadigms where one might be more frequent for hacky scripts where others are more profound.

You might want to check out C, Java, and Haskell (for instance) as procedural, object-oriented (i.e. the two mainly imperative languages) and a functional (i.e. a declarative language) language. Maybe implement functions to sort a list of integers in each of them, the differences between the latter as opposed to the first two should become very clear, but also the corresponding Wikipedia pages should provide good insights. However, e.g. in C++ (object-oriented) there are some features whose origins are in functional (declarative programming), e.g. lambda functions. On the other hand Haskell also has some sort of loops which are strictly speaking a rather imperative concept, so programming language designers adapt concepts from other languages from another paradigm, the line is blurred and not as clear as 30 years ago.

The difference between scripting and software engineering is even less clear. I would say it depends on the size of the program, reliability, use cases, how well it is documented, ... whether a certain program is a script or "fully fledged".


What is the time complexity of the below code?

Let $V(0)=12$ and $V(j)$ be the value of the variable $i$ immediately after the $j$-th iteration for $j \ge 1$.

$$
\begin{align}
V(j) &= \frac{7}{3} \cdot V(j-1)^5 \\
&= \left(\frac{7}{3}\right)^{1+5} \cdot V(j-2)^{25} \\
&= \left(\frac{7}{3}\right)^{1+5+25} \cdot V(j-3)^{125} \\
&= \dots \\
& = \left(\frac{7}{3}\right)^{\sum_{k=1}^{j-1} 5^k} + V(0)^{5^j} \\
&= \left(\frac{7}{3}\right)^{\frac{5^j - 1}{4}} + 12^{5^j}
\end{align}
$$
(I'm hand-waving a bit when the dots are used. If you want a formal proof you can use induction on $j$).

For your algorithm to stop you need that $V(j) \ge n$. When does this happen?

   Notice that $V(j)$ is monotonically increasing.
 Then, you need more than $s = \lfloor \log_{5} \log_{12} n/2 \rfloor$ iterations since:
 $$V(s) = \left(\frac{7}{3}\right)^{\frac{5^s}{4}} + 12^{5^s} < 2 \cdot 12^{5^s} \le n,$$
 and at most $S = \lceil \log_{5} \log_{12} n \rceil$ iterations since:
 $$ V(S) = \left(\frac{7}{3}\right)^{\frac{5^S}{4}} + 12^{5^S} > 12^{5^S} \ge n. $$

 Each iteration requires constant time (assuming that each arithmetic operation can be carried out in $O(1)$ time, which might or might not be reasonable if you're dealing with large values). Therefore the time complexity is $\Theta(\log \log n)$.


What are the hardest problems that are in P if and only if P=NP?

Well, here is a trivial example of a problem.

Inputs: a program P, an input x
Desired output: if P=NP, output "sweet!", else if P halts on x output "halts", else output "doesn't halt"

If P=NP, then this problem is in P.  If P$\ne$NP, then this problem is very hard (it's undecidable).

I realize this might not be what you're looking for; if so, perhaps it illustrates just how tricky it is to specify properties of this sort.


On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)

The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.


How many operations at maximum needed to compute powering of a number, i.e. $N^k$?

It depends on what you mean by operations. If multiplication of unbounded numbers is considered one operation, then repeated squaring takes at most $2L$ operations. In that case we don't care about the size of $N$.

If we only consider multiplication of $L$-bit integers as a unit operation, then multiplying $ML$-bit integers takes $O(M^2)$ operations using the high-school algorithm (in fact, much better algorithms are known), and so repeated squaring, in which the integers have size $L,2L,4L,\ldots,2^LL$, takes $O(1^2 + 2^2 + \cdots + 2^{2L}) = O(2^{2L}L)$ operations. Using fancier multiplication algorithms that take $\tilde{O}(L)$ operations (if they exist in this setting) reduces the number of operations to $\tilde{O}(2^L)$.


Recursive definition of a language $ L $ over $ \{a,b\} $

There is no problem to obtain $b$'s anywhere in the string: basically you can just "read" the string from left to right, and add the $aba$ to the end. That leaves one with only two recursive steps: if $w\in L$, then $wa\in L$ and $waba\in L$.

A bigger problem is that you now do not generate strings like $ababababa$!

This can be handled by having rules like: if the string ends with a $a$ we can add $ba$ to the end.


state of the art of subset, set containment and partial match queries

I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.


We can apply a linear transformation to get into the situation
$$
\begin{align*}
x' &= \frac{x+C}{Ax+By+1} \\
y' &= \frac{y+D}{Ax+By+1}
\end{align*}
$$
The Jacobian of the mapping
$$
J = \begin{vmatrix} \frac{\partial x'}{\partial x} & \frac{\partial x'}{\partial y} \\ \frac{\partial y'}{\partial x} & \frac{\partial y'}{\partial y} \end{vmatrix}
$$
is the infinitesimal area element of the mapping. That is, it is the area of an epsilonic rectangle around the image of a point $(x,y)$.
In our case, the Jacobian turns out to be
$$
J(x,y) = \frac{1-AC-BD}{(Ax+By+1)^3}.
$$
This function is either increasing or decreasing in each of the inputs $x,y$, and so after the initial affine transformation, one of the corner rectangles has the maximal area (and same for the minimal area). The linear transformation might change the sense of the axes, but otherwise only affects the area by a constant factor.


Solve modulus with constraints for multiple equations

Expand the equivalences $150 \equiv 2 \pmod{x}$, $50 \equiv 1 \pmod{x}$ into $150 = 2 + k_1 x$, $50 = 1 + k_2 x$ for some integers $k_1, k_2$ and deduce that $148 = k_1 x, 49 = k_2 x$. There is no
integer solution since $\gcd(148, 49) = 1$. But (for example; another system) if you replace $150$ with say $65$, then you have $\gcd(49, 63) = 7$. Since $x$ must be $> t_1, t_2$ (or your given upper bound on $t_1, t_2$), we can set $x = 7$ (or other factors of the gcd which satisfy the aforementioned conditions). You can probably turn this into an algorithm. The dominant cost is gcd computation.


Finding a series of numbers that maximise $\ \sum f_i(x_i) $

Following is a trivial Dynamic Programming algorithm for your problem:
Let $T$ denote a table of size $(m+1)$ x $(m+1)$.
Here, $T[i][j]$ stores the maximum value of $\sum_{t = 1}^{i}f_{t}(x_{t})$ such that $\sum_{t = 1}^{i}x_{t} \leq j$.
Induction Case: Since there are $m+1$ possible choices for $x_{i}$, check each one of them.
$$T[i][j] = \max_{p \in \{0,\dotsc,m\} \textrm{ and } p \leq j} \Big\{T[i-1][j-p] + f_{i}(p)\Big\}$$
Base Case: For $i = 0$ means there is no function. Therefore, the value is $0$.
$$T[0][j] = 0 \quad \forall j \in \{0,\dotsc,m\}$$
Output: The algorithm will output $T[m][m]$ which is simply the maximum value of $\sum_{t = 1}^{m}f_{t}(x_{t})$ such that $\sum_{t =1}^{m} x_{t} \leq m$
Running Time Analysis: Since the size of the table is $O(m^{2})$ and computing each entry takes $O(m)$ time. The overall running time is $O(m^{3})$.


Prove if a property of a Turing Machine is decidable or not, how can I do it?

To show that a language is decidable, you need to provide a description of a total Turing machine, i.e, on all input, the Turing machine should halt and accept or halt and reject.
Take the example of the first problem, we can build a total Turing machine, that on input $M$(where $M$ is a Turing machine) runs it all inputs of length at most 100. Note that if $M$ halts on all inputs within 100 steps, then it must halt on all inputs of length at most 100 within those many number of steps. If $M$ does so, our constructed Turing machine halts and accepts, else halts and rejects. Since  we have to check only on a finite number of input strings, the constructed machine always halts and hence is total.
As for the second problem, the property of accepting all strings with an 'a' in them is a non-trivial one for recursively enumerable sets($L(M)$ or the language recognized by a Turing machine $M$ is an R.E set) and hence from Rice's theorem, the language of deciding recursively enumerable sets with this very property is undecidable.


Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square

In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) \cdot (A + B)$.

What's left is to look at the pairs of divisors of $N$.
If $N = X \cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.

The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem.  Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.

Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)


Just another Divide-And-Conquer question - but somehow different

Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 > j_1$. Your code also has a few bugs — are you returning indices or stock prices?

The idea behind the divide and conquer solution is that the optimal solution is of one of three forms:

Buy and sell within the first half.
Buy and sell within the second half.
Buy within the first half and sell within the second half.

The first two are taken care of by the recursion, and for the third you just need to compute the minimum of the first half and the maximum of the second half.

There is also a simple (and faster) solution not involving any kind of recursion or sorting. The idea is to scan the array from left to right, keeping at any given point the smallest value seen so far. At any given point in time, you can consider the gain from buying at the smallest price seen so far and selling at the current price. The maximum over all these possibilities is the optimal strategy. This algorithm takes linear time, and can even be implemented online.


Why databases make the distinction between basic logical operations and functions

Database indices are typically binary search trees, meaning you can do range queries on them very efficiently.  If you handed the database the >= relation as a black box, on the other hand, it would have to iterate over every single record in the table performing the check.


How to Construct a Lattice from Program Statements

There is no such thing as a "DataFlow Graph lattice".  Those are two separate things.  A data flow graph is a graph that represents how data flows in a program, which can be helpful in data flow analysis.  A lattice is a mathematical object that can be helpful for data flow analysis.

Data flow analysis is a broad subject.  There are many techniques for data flow analysis (many use lattices, but it's not a hard requirement).  They don't all use lattices in the same way.  So, there's no one way to do the conversion you are referring to.

To learn more about the subject, I suggest reading a good textbook on program analysis.


How to prove universality in complex systems?

In order to show that your computation model is universal, you have to show that you can implement every computable function in your model. You do this by picking some other computation model $M$ and showing how to simulate $M$ in your model. For somewhat more formal definitions, see this answer.

As stated, this sounds difficult, and the first step is to look at various proofs of universality to get some ideas of what is involved. Some examples are listed in the Wikipedia article. It's possible that your model can easily simulate one of the simpler computation models such as counter machines, and this is perhaps the first thing to check.

It is also possible that your model is not Turing-complete but is still quite strong, say PSPACE-complete or EXPTIME-complete.


Properties of Reverse Polish Notation expressions that are algebraically invariant

You ask for a computable property that can be used as a fingerprint for equivalence (algebraic equivalence in your case).
There are two general approaches to this kind of question:

Take a canonical element of the equivalence class (a normal form) as the fingerprint.
Take the equivalence class itself as the fingerprint. Of course this requires classes to be finite. For computability of the equivalence class we also need a computable bound on the size of members of the class. (Plus decidability of equivalence. But that is a general requirement, because fingerprints imply this decidability.)

In this answer I only consider the case where you only have addition, subtraction, and multiplication. None of your examples has division, so I assume that this restriction already is relevant for you. In this case, an algebraic expression essentially (up to syntax) is a multivariate polynomial.
For example, the expression $x\cdot(x-z-z)$ yields the polynomial $x^2-2xz$ (more precisely $\sum\{x^2, -2\prod\{x,z\}\}$, to stress that polynomials do not carry information about the order of additions or multiplications. That is, $x^2-2xz$ is the same polynomial as e.g. $-2zx+x^2$).
This polynomial is already close to the fingerprint you want: Different polynomials are extensionally different over the real numbers. Which means that they can be shown to be different by subtituting suitable real values.
Hence polynomials are normal forms for expressions.

Renaming of variables is not yet covered. (Also observe that normalizing to polynomials may have the effect of losing variables: $x+y-x$ would be normalized to $y$, in which $x$ does not occur any more.)
But we can take equivalence classes of polynomials: The degree and number of monomials imply a size bound. Equivalence is decidable just by trying out variable renamings.
With canonical variable names $x_1, x_2, x_3, \ldots$, the above polynomial $x^2-2xz$ yields the equivalence class $\{x_1^2-2x_1x_2, x_2^2-2x_1x_2\}$.

While we have achieved computability, we do not yet have efficiency. So, can we do any better? Can we have a normal form for polynomials? If you consider the special case where all monomials are the product of two distinct variables (like $x\cdot y$), the problem of canonizing polynomials becomes graph canonization, whose complexity is unknown.


Is it computationally possible to voice-recognize and word-tag-time-align audiobooks to their actual text?

The fact that humans can understand audio books shows that it is computationally possible. This does not make the problem easy for an AI. It also does not mean that you can write a formalism of the language in audio form for parsing. Anything involving audio / recordings is going to involve lots of fuzzy data. This is not generally what someone would call parsing, but instead speech recognition. If you can properly recognize words in the correct context then the rest of the stuff you mentioned like dictionary lookup, and moving around a book is basically trivial.

It is easier to do this if you already have the words though. I would recommend something like splitting the audio based on breaks, and then applying speech recognition on each section to make sure the word matches the audio that was split. This is to check if errors in splitting exist. If there is an error where the word does not match the audio a human could be prompted to manually split them.


A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$.

We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is not hit. For a bit not to be hit, it has to be missed each time. Since it has $k|S|$ opportunities to be hit, and each time it is missed with probability $1-1/n$, in total a bit is missed with probability $(1-1/n)^{k|S|}$. Thus a bit is not missed with probability $1-(1-1/n)^{k|S|}$.


Take a peek at Anderson's classic "Security Engineering" (PDF legally available for free at the link). It won't help you with the details, but it gives an overview of the whole area, for (more or less) laypeople.


Creating Best Clusters of Objects Based on Distance Between Them

You can use Cluster Edge Deletion, however, the problem is NP-hard.

Create a graph where the vertex set is the set of your objects, and you create an edge between two objects if the distance is at most the threshold.

Now, the Cluster Edge Deletion problem is to find the set with fewest edges to delete such that the remaining graph is a cluster graph (a graph whose connected components are cliques).  In this solution, every object belongs to a cluster in which the distance to every other object is bounded by the threshold.

Alternatively, you can run $k$-means (with increasing $k$) until you're satisfied with a solution.  Take note that the $k$-means algorithm is randomized and gives an approximate solution (as also this problem is NP-hard), so you might want to run the algorithm several times per $k$.


Relation between Undecidable problems and NP-Hard

I believe that this answer by Yuval Filmus all the questions you have asked.

  If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.

  We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.

  The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s \in SAT$ iff $f_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.

  By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.

To summarize,

Halting problem is NP-hard.
If $P\ne NP$, not all undecidable problems are NP-hard.
If $P = NP$, all non-trivial sets are NP-hard.

The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.

  There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

  If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

  On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have  coNP ⊆ NP. This means NP = coNP.

  The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

So, assuming $NP \ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P \ne NP$).


What is this hash of array data structure called?

No, this data structure does not have a commonly-used name. It so similar to a  hash table that it is very unlikely to have been the subject of a peer-reviewed publication.


Maximum number of segments with no intersection

I can show you a solution that I suspect is $O(n \log n)$, but I haven't proven the runtime.  Edit: Following a linked solution, I amended this solution to be simpler and run in $O(n \log n)$.

So the issue is that if you take a greedy approach, you might choose a 'bad' segment that blocks a favorable choice later.  That is, choices you make at the beginning affect what choices you have available later on.  This suggests a dynamic programming approach.

First step is to sort the segments by their start times.  Then, you need to define exactly what you're going to calculate.  We'll define $numsegs(i)$ as the max number of segments possible when segment $i$ is included and has the earliest start time of all included segments.

Then your final answer is going to be the maximum of value of $numsegs(i)$ for all possible values of $i$.  Now you need a formula for $numsegs(i)$.

Think about how to calculate $numsegs(0)$, the maximum segment count when you include the first segment.  If we include the first segment, then we can only include other segments that begin after the first segment ends.  So we need to find the index of the first segment that is compatible with segment 0.  We can do this in $O(\log n)$ time with a simple binary search - let that index be $k$.  Now, we can say that $numsegs(0)$ is 1 (for segment 0) plus the maximum of $numsegs(k), numsegs(k+1), \dots, numsegs(n)$.  (There's an edge case to consider as well.  If segment $i$ doesn't have any compatible segments after it, then $numsegs(i)$ is just 1.)

You can compute $numsegs(i)$ in a very similar way.  Note that $numsegs(i)$ depends only on $numsegs$ values greater than $i$.  Therefore we can compute $numsegs(n-1)$ first, then $numsegs(n-2)$, and so on, caching the values as we go, and we'll never have to recalculate any $numsegs$ values.

This solution is actually $O(n^2)$.  To compute $numsegs(i)$, you have to find the maximum among potentially $n-i$ following $numsegs$ values.  How then to get the total runtime down to $O(n \log n)$?

Edit: As a linked solution pointed out, we can compute the maximum quickly using caching.  Suppose we want to know the maximum $numsegs$ value starting from index $k$.  We can just compare $numsegs(k)$ to the maximum starting from $numsegs(k+1)$, which we cached in a previous step.


Document definition in information retrieval

For a formal definition of document in the Information Retrieval context, you can look at IR glossaries.

A common definition is:

Document:  Specific unit of retrieval (usually text). It can be a web page, an article, a book, a section or chapter.

(see for example the Glossary of the book Modern Information Retrieval by
Ricardo Baeza-Yates and Berthier Ribeiro-Neto)


Simulate a regular Turing Machine with one that cannot write blanks

To simulate a Turing machine $M$ that can write blanks with a Turing machine $M'$ that can't, just give $M'$ an extra character in its alphabet. Whenever $M$ writes a blank, $M'$ writes this new character and, whenever $M'$ sees the blank or the new character, it does what $M$ would do if it saw the blank.


Finding a suitable sum here is a bit awkward since sums in mathematics tend to step up by one, always. So we have to normalize the sequence of values of i

$\qquad i = 1, 2, 4, 8, \dots [i<n]$

to

$\qquad i' = 0,1,2,3, \dots [???]$.

My notation already suggests that it's about finding the right termination predicate.

Roughly speaking, you're looking for the inverse operation to the repeated step function, which by itself is $i \mapsto 2i$.
I'm not sure how to lead you towards an answer unless you know about logarithms. If you do, it should be kind of obvious; roughly:

$\quad i' = 0,1,2,3, \dots [i'<\log_2 n \pm 1]$.

Do some tinkering to find out whether you need to use $\lfloor \log_2 n \rfloor$ or $\lceil \log_2 n \rceil$ as upper bound on $i'$.
Now, the rest is elementary.

Note that you can go about this by normalizing the for loop first:

for(i=1; i<n; i=i*2)
    print(i)

becomes

for(i' = 0; i' < log(2,n) +- 1; i'++)
    print(2^i');

Note that for functional equivalence, I start with $i'=0$ so that $2^{i'} = i$ in each iteration; you can also use $2^{i'-1}$ instead and start with $i'=1$. Try out a few things -- some make the code nicer, others the mathematics afterwards.

Make sure -- by proof and/or testing -- that the normalized loop computes exactly the same thing as the old one, and then it's all standard. You might need a cheat sheet to simplify the sum.


This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP,
we provide a polynomial-size certificate,
and then we show how to check it in deterministic polynomial time.

The certificate is just the following:
a set of integers $\{x_{u,v}\mid (u,v)\in E\}$.
Intuitively, $x_{u,v}$ is the number of times the solution path
traverses $(u,v)$.

We now describe the
verification algorithm.

We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}>0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.
We check whether

$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover,
$y_s := \sum_{(s,u)\in E'} x_{s,u}$.
We check whether there exist real values $z_v$, for every $v \in V$, such that

$d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
bound of the rational interval $d(v)$), and
$\sum_{v \in V} z_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify
a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4.
form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).


Inheritance, and dynamic access to members/attributes and methods in Java-like languages

I suspect that this is intimately related to shadowing of fields in Java.

When writing a derived class, I can, as in your example, write a field x that shadows the definition of x in the base class. This means that in the derived class, the original definition is no longer accessible via name x. The reason Java allows this is so that derived class implementations are less dependent on the base class implementation details, thereby (only partially) avoiding the fragile base class problem. For instance, if the base class did not originally have a field x, but then subsequently introduced one, Java's semantics avoid this breaking the derived class implementation.

The variable x in the derived class can have a completely different type than the variable in the base class – I tested this, it works. This is in stark contrast to method overriding, where the type needs to be sufficiently compatible (aka, the same). So when I have a variable of type A in your example, the only type I can derive for it is the one specified in class A (or above). As this can be different from the type declared in class B, it is only type safe to return the value of the field x from class A. (And naturally, the semantics must be the same regardless of what the type of the field is in class B.)


Difference between Dependent type , refinement type and Hoare Logic

There is recent work by Paul-André Melliès and Noam Zeilberger that explores this.  In particular the papers Functors are Type Refinement Systems and An Isbell Duality Theorem for Type Refinement Systems.  There's also a video of a talk on the first one.

I think there is a lot of confusion around refinement types due to people thinking of particular systems as representative which causes goals and details of those particular systems to be attributed to the general idea.  The short of it is type refinement systems classify terms that exist independently whereas (non-refinement) types, dependent or otherwise, are part of terms.  This may sound familiar and possibly even a bit contradictory.

The potentially familiar and possibly contradictory seeming part comes about if you view types à la Curry (extrinsically) versus types à la Church (intrinsically).  When we think of types à la Curry, we think of types as classifying untyped terms that already have meaning.  In types à la Church, the only terms that exist are well-typed terms, i.e. the type constraints are part of our syntax.  So what I'm saying is that a Curry-style type system is actually a type refinement system refining untyped terms, while a Church-style type system is not a type refinement system.  This means that, for example, we can think of the simply typed lambda calculus as either a type refinement system or as a non-refinement type system.

Of course, no one says that our terms have to be untyped terms.  We could just as well apply a type refinement system to typed terms, and, historically, this is the context in which refinement types (by that name) arose.  However, applications to soft typing illustrate something closer to the situation described above.

So far I haven't said anything about dependent types.  The reason is that it is a completely orthogonal concern.  I would say the archetypal dependent type systems are usually presented in a Church-style, and thus are not type refinement systems, but NuPRL (based on Computational Type Theory, a variant of the most archetypal dependent type theory, Martin-Löf type theory) is blatantly a type refinement system as I've described.  Terms in NuPRL may not even have types!  Admittedly, the fact that "PRL" stands for "Program Refinement Logic" might be a tip-off too.  On the flip side, Refinement Types for ML describes a refinement type system, possibly the origin of the term, which is not a dependent type system in any way.

As for Hoare triples, they are a type refinement system.  They are actually used as an example of a type refinement system in the first paper.  However, Hoare Type Theory gives something which can be viewed as a non-refinement type system for a language having Hoare triples.

To have an answer about the "power" of different systems, you need to specify a particular (family of) dependent type system(s) and a particular (family of) refinement type system(s).  The term "dependent type system" covers a very broad class of type systems, and "type refinement systems" is even broader.  Even then, the terms aren't mutually exclusive, so it would not be a comparison between "dependent type systems" and "refinement type systems".  However, if by "dependent type system" you are thinking of something like Coq, and for "refinement type system" something like Liquid Types then it is pretty one-sided.  Coq is generally viewed as powerful enough to handle virtually all of mathematics in practice; you could literally implement and prove correct a SMT solver within Coq and then use it; and a very close analog to the subset type can be formulated. (NuPRL literally has subset types.)  On the other side, SMT solvers are usually restricted to decidable theories where Coq has no such limitation; and many systems like Liquid Types have a limited and non-extensible language for specifying predicates.  (Of course, by "dependent type system" you could mean Dependent ML, and by "type refinement system" NuPRL [which is also a dependent type system] which would be one-sided in the other way.)


Relation between Machine code and Von Neumann architecture

Asking whether machine code abstracts the von Neumann model is a category error – it's a statement that doesn't type-check. The von Neumann model is essentially a system architecture: it's a way of designing computers. Machine code is a sequence of instructions: a way of telling a computer what to do. Those are two completely different things.

Machine code arguably doesn't abstract anything. It's the most concrete, specific thing there is: it runs on only one specific kind of CPU (or perhaps a family of very closely related ones).


Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems

There are no upper bounds on the complexity of polynomial-time reductions between $\mathrm{NP}$-complete problems, other than that they're in polynomial time.

Let $\mathrm{NP}_k = \mathrm{NTIME}[O(n^k)]\setminus\mathrm{NTIME}[O(n^{k-1})]$. By the nondeterministic version of the time hierarchy theorem, there are problems in $\mathrm{NP}_k$, for all $k$.

Let $X$ be any $\mathrm{NP}$-complete problem. There is some $t$ such that $X\in\mathrm{NTIME}[n^t]$.  Consider some problem $L\in\mathrm{NP}_k$ for some $k>t$.  If we have a reduction from $L$ to $X$ that runs in time $n^r$, then we can solve an instance of $L$ in time $O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length $O(n^r)$, and then solving that instance in time $O((n^r)^t)$.  This contradicts the nondeterministic time hierarchy theorem if $k>rt$.


Why can the state space of the 15 puzzle be divided into two separate parts?

Perhaps the simplest way to understand the proof is by the idea of a conserved quantity : find some quantity that can be derived from a configuration and show that every move preserves that quantity.  A static version of the idea is found in the following old puzzle:

  Remove the northeast and southwest corner squares from a standard 8x8 checkerboard.  Can the remaining 62 squares be tiled using 31 dominos?

Here, the parity principle is simple: each domino takes up exactly one black and one white square on a checkerboard, so any shape that can be tiled by the dominos has to have exactly as many white squares as black.  Since the 62-square shape has 32 squares of one color and 30 squares of the other, there's no way of tiling it.

The conservation principle for the 15-puzzle is a bit more complicated, but it's fairly close to this: it's also a parity principle.  Let's number the blank square '16' for the time being and imagine it being filled in; then we can talk about the state of the puzzle as a permutation of the numbers (1...16).  Now, given an arbitrary permutation of the numbers (1...$n$), we can count how many pairs of numbers we have to swap to return all the numbers to their 'original place'.  There are many different possible sets of swaps that can be made - for instance, if you have the permutation (3, 2, 1) you can get back to (1, 2, 3) by either swapping the first and third positions (3 with 1) or by swapping the first and second positions (3 with 2), then the second and third positions (3 with 1), then the first and second positions (1 with 2).  (The minimum number of swaps that need to be made is called the number of inversions of the permutation, and it's an interesting quantity in its own right, but that's not important here).  However you swap numbers around, though, the total number of swaps will either always be odd (like it is for (3, 2, 1)) or always be even; we call this number the parity of the permutation.

Now, going back to the fifteen puzzle: every move is to swap the blank square (the one we've labeled as '16') with some other square, one unit away from the blank square's current position.  This means that a swap always comes with a move of one square - so if you consider the quantity 'total number of swaps I have done' + 'moves the 16 is away from its home square', then this quantity will always be even.  In particular, when the 16 is back at its home square (0 moves away) then the overall number of swaps that's been performed must be even.  This means that the parity of the permutation of the numbers (1..16) corresponding to our resulting position is always even.  But now imagine the position of the original puzzle where the 14 and 15 have exchanged places; the 16 is at home but there's been only one 'swap' made.  Since this is an odd number of swaps rather then an even number, it can't possibly be reachable from the base configuration.

There's one more minor catch: this shows that there are at least two categories that 15-puzzle positions can fall into, but it doesn't show that there are only two.  For that, a slightly more complicated result is needed: namely, that any even permutation can be decomposed as a product of what are known as 3-cycles (i.e. swaps $a\rightarrow b\rightarrow c\rightarrow a$).  I won't try to prove this here, but the simplest proofs work algorithmically - similar to how bubble sort shows that every permutation can be generated by swapping only adjacent elements.  With this result in hand, though, it's easy to get any even permutation: we can get an arbitrary 3-cycle by moving our three elements into positions 11, 12, and 15 on the puzzle (with the blank square in position 16, of course), and then moving the blank square Up, Left, Down, Right - you can convince yourself that this motion cycles the three elements.  Once we've done this, we just undo the same motions that got the three elements into those positions, leaving the final positions of all the other elements unchanged from their starting positions.  This way of getting an arbitrary 3-cycle, along with the theorem allowing any even permutation to be expressed in terms of 3 cycles, then gives a way of getting every reachable (i.e., corresponding to an even permutation) position.


Remember that $1)$ application is left associative and $2)$ application has higher precedence than abstraction. This is:

$1)$ $ A B C = (A B) C \neq A (B C)$
  $2)$ $ \lambda x. A B = \lambda x. (A B)  \neq (\lambda x. A) B$

So

$KII = (KI)I = ((\lambda x y. x) I) I = (\lambda y. I) I = I$


Kleene star closure of a context free grammar

There is a silly problem that you might need to add a production of the form $S\to\epsilon$, since otherwise you don't necessarily generate $\epsilon$. But the real problem is that $S$ can be used in the right-hand side of productions, and when you add the rule $S\to SS$, things could break. The "correct" way to turn a grammar of $A$ into a grammar of $A^*$ is to add a new start symbol $S'$ and the productions $S' \to S'S|\epsilon$.

In order to find a counterexample, think of the problems mentioned in the previous paragraphs, and try to find an example which manifests them. All it requires is some experimentation.


How does Instruction Set Architecture (ISA) affect performance?

Same ISA means they understand the same instructions in binary. They can certainly be very different in speed. Look at e.g. the x86 family (disregard the instructions added over time). The very latest Pentium is certainly much faster than the first 386, and even within each "number" there are variations.
Even crasser, remember ye goode olden days of i486 and overclocking? Even the same chip can (sometimes) run at different clock rates. BTW, that is something current laptops do: To conserve battery power, the CPU runs at a lower clock rate when possible.


Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

Construct a new graph $G'$ with the same set of vertices, and with an edge $(u,v)$ iff there is a path of length 2 from $u$ to $v$ in the original graph.  Then, check whether $G'$ has any cycles of any length.  A cycle in $G'$ corresponds to an even-length cycle in the original graph, and vice versa, so this provides a correct algorithm.  The running time is $O(|V||E|)$.


If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$.
In other words, no word containing an odd number of 1s is also in $L(M)$.
Then, by definition of $A$ you should accept.
Conversely, if  $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B  \neq \emptyset$.
That is, there is some word $w \in L(M)$ such that $w$ contains an odd number of 1s. Then, by definition of $A$, you should reject.


Looking for a ranking algorithm that favors newer entries

You could use any function that gives a lower weight to older entries. For example, if data consists of scores, $s_1,\ldots,s_n$, where the index  corresponds to the 'time of arrival' of the entry, that is, newer entries have larger indices, then you could use a weight function that increase as $i$ increases. So any 'increasing' function will do. Examples include:

$f(x)=e^x$
$f(x)=\log x$
$f(x)=x$
$f(x)=x^2$

etc.

Then your function will be

$\dfrac{\sum_{i=1}^n s_i\cdot f(i)}{\sum_{i=1}^n f(i)}$.

Actually, it makes more sense to give the newest entry the lowest index and make the weight function decreasing. This way you can tune it by setting the weighting that you want to give to the first element.

Wikipedia has an entry on weight functions, some examples can be found on the page about weighted means.


Does pre-emption of a process occur when that process is busy waiting?

There are two broad concepts at play here: "synchronization" and "pre-emption". To make sure both processes run mutually exclusively, they first try to make sure the other one executes in the hope that in the future, the other process will ultimately unblock them by setting their respective flags.

To make sure both processes run to completion on this premise, the OS or any scheduler for that matter, should ensure that both processes are given their share on the CPU. Now coming to your question:

  So does a process pre-empt if it's busy waiting?

Yes, absolutely. If the scheduler (OS) upholds multi-tasking (say round-robin scheduling?) then the busy-waiting process will indeed pre-empt at some point in time. But keep in mind things get a little complicated when features like process priorities are added into play.

The other question:

  But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ?

follows the answer to previous question that P1 would be pre-empted and eventually, P0 will run to completion thereby allowing P1 to also run to completion.

Final thoughts:

This is a basic synchronization primitive and a great example to help understand synchronization/mutual exclusion concepts. But, it doesn't take into account performance and busy-waiting is definitely not good performance-wise. There are other primitives that operate in post-wait fashion instead of busy-wait (Semaphores, for instance) which could be a better option.


What the length of instructions on these processors will be?

If the ISA is the same, the registers and instructions have the same size.

A CPU can have 32, 64 or wider busses for caches, external memory.

It has no relation with the size of instructions.

It has no relation with the size of integer registers.

You can see variants or extension of the same ISA with 64 bits support : MIPS III, SparcV8 vs SparcV9, x86 vs AMD64, ARMv7 vs ARMv8, Power32 vs PowerPC64, etc... The new instructions are either handled as a different mode, or using different opcodes.

The "size of word" is a term for compilers and programmers (int, long int, long long int...), not for hardware.

Of course, it makes little sense to tie a 64bits bus to a 8bits CPU, or the inverse.