Advantages and disadvantages of microcoded vs hardcoded architectures

The distinction between "microcoded" and "hardcoded" multi-cycle control units is a relatively small implementation detail.  The distinction was more important in the 1950s when people were inventing new implementation techniques for state machines.  In modern processor design there are much more important implementation distinctions, like how much pipelining and instruction overlap you are going to try to achieve, whether you are going to speculatively execute instructions, and whether you are going to try to schedule instructions out-of-order.

That said, here's the distinction:  We divide the design into datapath and control.  Here's the picture of the MIC-1 from Tanenbaum's Computer Organization book.  (The image is by Suyog.karnawat, from Wikimedia commons.)  Everything in the design is the datapath except the box in the upper right hand side that says "Instruction decoder and control logic."

The "Insruction decoder and control logic" box is a finite state machine.  The datapath in this example is very simple, with only a single bus, so even an instruction to add two registers and put the result in a third register takes multiple cycles (each of which corresponds to a state in the state machine.)

Each instruction goes through the following steps/states (each of which takes a cycle)

move the PC (Program Counter) to the MAR (Memory Address Register)
assert the controls to perform a load from the memory bus
eventually the memory will return the requested data (which corresponds to the next instruction) and put it in the MDR (Memory Data Register)
move the instruction from the MDR to the IR (Instruction Register).  At this point the instruction gets decoded and we figure out what to do with it.  In this case it's an add operation so we know we need to:
move Ra to the X register
put Rb on the bus (so that it will go to the B input of the ALU) assert the ALU control lines and Mux select appropriately to do an add operation, the result of which will get saved in register Y
Move Y to the Rc register, and then every non-branch instruction ends by incrementing the program counter:
Put the PC on the bus, set up the ALU to increment (Select the MUX to put constant 1 on the A input and set up the ALU to Add) so that PC+1 will get saved in the Y register
Move the Y register back to PC

So 9 state transitions to perform a simple add instruction.

So the "Instruction decoder and control logic" is a finite state machine with inputs from the IR register, outputs are the control signals, and there must be some flip-flops inside to represent the state of the state machine.  But there are lots and lots of ways to implement a state machine.

$\lceil \log_2 N \rceil$ flip-flops (where $N$ is the number of states) and a lot of combinational logic (to calculate the control signals and next state).
$N$ flip-flops with one-hot encoding and a bunch of combinational logic (usually less than with option A, but a lot.)
Somewhere between $\lceil \log_2 N \rceil$ and $N$ flip-flops with some combinational logic of intermediate complexity.

And the combinational logic for the control signals and next state functions can be implemented any number of ways:

As NAND gates reduced (using Quine-McCluskey, or whatever) to sum-of-products form.
As NAND gates reduced to some relatively efficient multiple-level circuit.  (This is probably what people think they mean when they talk about "hardwired control.")
A design using Multiplexers for the combinational logic
A design using Programmable logic arrays (although I don't know if you can even buy these anymore.)
A design where the combinational logic is implemented with a ROM.  (This is probably what people think they mean when they talk about "microcoded control.")  The ROM might be a EEPROM so that it is somewhat easier to modify if you find a bug.

ROMs can get really huge if you're not careful.  For example a ROM-based design would almost always use $\lceil \log_2 N \rceil$ flip-flops, because making the state wider also makes it sparser, which is sometimes good for gates but not for ROMs.  Also, you would only use the opcode bits as part of the address to the ROM, not the register specifiers and such.

Finally with ROMs you might choose to make the microcode word wide (the microcode word produces the entire set of bits for the control signals) or narrow (the microcode word chooses one of a smaller number of possible control signal combinations and then there's a second ROM that translates from that smaller number to the actual required control signals.

So the distinction between "hardcoded" and "microcoded" is only one very small decision that needs to be made among hundreds of design decisions.  And it's certainly not the most important one.  (For example, you could choose to put a second bus on the datapath, which would enable you to perform some instructions with a lot less cycles.)


$1+\epsilon$ approximation for inapproximable problems

The first sentence says there is no approximation algorithm with $2-\epsilon$ for k-center, which means $k$ is part of an input, because there is no limitation on $k$, so $k$ can be arbitrary large (as $n$). This is common mistake in the context of approximation algorithms and parametrized complexity, this doesn't mean the algorithm runs in polynomial time, this says if you "fix" some parameters (e.g here k) you can have polynomial time algorithm, exactly like what you mentioned, mentioned algorithm is polynomial in $n$ but not in $k$, and when $k$ is not fix and is part of input, the algorithm is not polynomial. You can read more detail on fix parameter tractability in reference question.


This should really go in codereview.stackexchange.

In many languages, increasing the maximum possible int value either invokes undefined behaviour or produces the minimum possible value or both. If numberOfTerms == 2147483647 your code is most likely to never finish.

The execution time will be awful because you call a very expensive function Math.pow just to get a sequence that alternates between +1 and -1. Don't translate formulas literally, use your brain first. If numberOfTerms == 2147483646 then your code is quite likely not to finish before you give up.

The Leibniz formula is just awful to calculate π. To find n significant digits, you need to add $O (10^n)$ terms. Your function will never be as precise as the 3.141592653589 that I can quote from memory.

You have significant numerical problems because you will have rounding errors that are adding up badly, so I doubt you will get more than 8 digits correct ever.


Resending old frame when a damaged frame has been received in one bit sliding window protocol

Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted?

This could indeed be done when the error occured in the data. i.e. you're sure that it wasn't the acknowledgement or sequence number that was damaged. In that case, sender A could indeed send a new frame as described and avoid sending unnecessary duplicates.

However, although an error can be detected, it can not be detected where the error occured (in the data, acknowledgement or sequence number). If the error occured in the aknowledgement number then the client may unrightfully think that his previously sent frame was received correctly while it actually wasn't received correctly and so, if he sents a new frame with new data as proposed in the question, a client will miss a frame!


No subset of RE captures the set of TMs halting on themselves as input

According to the recursion theorem, there is a Turing machine $M$ such that $L(M) = \{\langle M \rangle\}$. If $P$ is a property such that $L_P = K$ then $\langle M \rangle \in K$ implies that $L(M) = \{ \langle M \rangle \} \in P$. Now it is easy to construct a different machine $M' \neq M$ such that $L(M') = \{ \langle M \rangle \}$. Since $L(M') \in P$ and $L_P = K$, we must have $\langle M' \rangle \in K$, yet $M'$ doesn't halt on $\langle M' \rangle$.

Note that this solution doesn't use the condition $P \subseteq RE$.


Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

Given a weighted directed graph and two nodes $s,t$, an $s$-$t$ cut is a set of edges, upon whose removal $t$ is not reachable from $s$. The weight of the cut is the total weight of edges removed. A minimum $s$-$t$ cut is one of minimum weight.

A similar definition works for undirected graphs and in the special case in which the graph is unweighted, in which all edges have unit weight.

If we think of a weighted digraph as a flow network with source $s$ and sink $t$, then any $s$-$t$ cut gives a restriction on the weight of any flow in the network, which must be at most the weight of the cut. The min cut max flow theorems states that the weight of a minimum $s$-$t$ cut coincides with the weight of the maximum flow. However, a cut and a flow are two very different things.

There's a related definition of cut which works just for undirected graphs.
A cut in an undirected graph is a set of edges whose removal disconnects the graph. (Any $s$-$t$ cut is a cut.) A minimum cut is one of minimum total weight (or, in the unweighted case, of minimum cardinality).

One reason that cuts are so powerful is that they can be found efficiently.


Is the language in the description context free?

The basic problem here is that context-free languages are not closed under intersection.

The example you give illustrates this. Thus, $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b\}$ is context-free, and similarly, so is $\{ w\in\{a,b,c\}^* \mid |w|_b \le |w|_c\}$. The intersection of these two languages $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b \le |w|_c\}$ is not context-free.


What would you get if you add parameters to context free grammars?

Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "Affix Grammars for Programming Languages", a version of which I found on Citeseer.

In that paper, Koster compares his formalism (and another similar one) with Van Wijngaarden two-level grammars, and finds them to be very similar.

Dick Grune's invaluable annotated bibliography of parsing techniques includes a large number of other useful references for affix grammars and other non-Chomskyian formalisms. (See section 18.2.6 of the bibliography, although there are useful papers in other sections.) Grune covers affix grammars briefly in §15.3.2 of the second edition of Parsing Techniques: A Practical Guide (and even more briefly in the first edition, available online) mentioning the fact that it is easy to adapt top-down (and other) parsing techniques.

Unless the domain of parameters is finite, in which case they can be removed by statically generating all possible productions resulting in a CFG, the class of affix grammars is certainly a strict superset of the set of context-free grammars. (An affix grammar for $a^n b^n c^n$ can be found in Dick Grune's Parsing Techniques reference above.)

Koster, who was also an editor of the Algol 68 report, was the original developer of the Compiler Description Language (CDL), based on his ideas about affix grammars. This toolkit and its later derivatives were used in production for many years. This page, which I found with a Google search and whose permanence I cannot guarantee, has links to the manual and download site for CDL3.


Discrete assignment problem with penalties

Riley's answer is excellent.  It is possible to improve the running time further to $O(mn)$ time, using dynamic programming.  This saves a factor of $n$ in the running time.

Define $T[i,j]$ to be the total profit of the best assignment for times $i,i+1,\dots,m$, assuming that at time $i$ the agent is assigned to task $j$.  We'll compute all of the $T[i,j]$ values, in order of decreasing $i$, using the following recurrence:

$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j \le n, j' \ne j\} - p),$$

or equivalently,

$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j' \le n\} - p).$$

Naively, it looks like filling in a single cell will take $O(n)$ time so computing all the $T[i,j]$ values will take $O(n^2)$ time.  However, we can speed it up with a trick.

Define

$$M[i] = \max(T[i,1],\dots,T[i,n]).$$

We obtain the improved recurrence

$$T[i,j] = c_{ij} + \max(T[i+1,j], M[i+1] - p).$$

We'll fill in the $T[i,\cdot]$ and $M[i]$ values simultaneously, in order of decreasing $i$.   Once we've filled in $T[i,1],\dots,T[i,n]$, we can compute $M[i]$ in $O(n)$ time.  Then, once we know $M[i]$, we can compute each $T[i-1,j]$ in $O(1)$ time using the improved recurrence, so we can compute $T[i-1,1],\dots,T[i-1,n]$ in $O(n)$ time once we know $M[i]$.  Finally, $M[1]$ is the final answer to the problem.

In this way, we do $O(n)$ work per value of $i$, and there are $m$ values of $i$.  Consequently, the total running time is $O(mn)$.


How many bits to represent a quantity $\omega$ bounded in a particular way?


Question 1

I think you are overcomplicating things, the question is about $\mathcal{O}$-notation, you don't need any meaning attached to these constants. Try making your life easy and pick simple ones:

You only need a lower bound, so just set $c_1 = d_1 = 1$, clearly $n + 1 \leq T_{\text{findMax}(n)}$.

Similarly you only need an upper bound, set $c_2 = 4$ and $d_2 = 42$, giving you $4n + 42 \geq T_{\text{findMax}(n)}$.

Question 2

It's not clear how $T_A$ is defined, so it's hard to answer Question 2.

Assume there is an algorithm $A$ with $T_{A(n)} = t < n$. So this algorithm is restricted to read/compare at most $t$ elements of $a_1,\dots,a_n$ and therefore there is always a sequence $a_1,\dots,a_n$ where the algorithm will fail, ie. the actual maximum is not among the $t$ elements. $\Rightarrow\!\Leftarrow$


If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?

This is something you will encounter over and over, not just in science but also in engineering, in law, in programming, and generally in jargon. If there is a definition for a term, then that term means exactly what the definition says it means. No more. No less.

In particular, you may have an intuitive notion of what the term means in English, but this is not English. This is technical jargon. A "peak" doesn't mean what you think it means, it doesn't mean what it means in English, it means exactly what its definition says it means.

So, depending on the definition, all elements could be the peak, or there could be no peak, or any element could be the peak, or maybe it could even be the case that the question doesn't even make sense because there is some precondition to the definition of "peak" that doesn't apply in this case.

Look at the definition. Apply it. Ignore any intuition about what you think the answer should be. Trust the result.


Name for multiset with fractional amounts?

I don't know a standard name for this, but what you've described is representable as a function into $\mathbb{R}$.

For your example, if $X$ is the set of your things then you can represent your 'fractional multiset' as a a function $f : X \to \mathbb{R}$ such that

$$
f(x) =
\begin{cases}
1 & x = \text{carpenter}, \text{sawyer} \\
0.5 & x = \text{woodcutter} \\
0.25 & x = \text{forester} \\
0 & \text{otherwise}
\end{cases}.
$$

If you're looking for a way to implement this in a programming language, if you need to store only finitely many things then you could use a map/dictionary data structure. For example in java you could use some implementation of Map<X, Float>

As for what to call this, "fractional multiset" sounds fine as long as you explain it in whatever context you're using. Alternately you could just refer to it as a "size/measurement function".


Parser theory: How to systematically compute FOLLOW sets?

The simple way to do it is the same as the simple way to compute FIRST sets, using a least fixed-point algorithm in which a set of inclusion rules are applied repeatedly until a fixed-point is reached:

Initialise all the sets to empty.
For every production in order, use the rules to add elements into the sets.
(As a slight efficiency, rule 2 only needs to be applied on the first pass. I didn't apply that to the trace below.)
If any set was modified during step 2, do it again.

So, here are the productions in order (I added the missing $*$ to $T'$, and inserted an augmented start rule $S$, which avoids the need for your special case rule 1):

$$\begin{align}
S &\to E\; $ \\
E &\to TE' \\
E' &\to +TE' \mid \epsilon \\
T &\to FT' \\
T' &\to *FT' \mid \epsilon \\
F &\to (E) \mid id
\end{align}$$

Set all the $FOLLOW$ sets to $\{\}$
First pass. I left out productions like $F\to id$ which don't match any of the rules.
$$ \begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &FOLLOW(E) = \{ \$ \}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &FOLLOW(E') = \{ \$ \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + \$ \}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * \}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &FOLLOW(T') = \{ + \$ \}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * + \$\}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &FOLLOW(E) = \{ ) \$\}\\
\end{array} $$
There were various changes, so we repeat step 2.
(Step 2, second pass)
$$\begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &\text{no change}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &FOLLOW(E') = \{ )\$ \}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &FOLLOW(T) = \{ + )\$ \}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &FOLLOW(T') = \{ + ) \$ \}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &FOLLOW(F) = \{ * + ) \$\}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &\text{no change}\\
\end{array} $$
(step 3, second pass) There were some more changes. Once again.
(Step 2, third pass)
$$\begin{array}{c|l|l}
S \to E\; $       &\text{Add }\$\text{ to }FOLLOW(E)     &\text{no change}\\
E \to TE'         &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E)\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
E' \to +TE'       &\text{Add }FIRST(E')-\{\epsilon\}\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(E')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(E')\text{ to }FOLLOW(T)
                                                     &\text{no change}\\
T \to FT'         &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T)\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
T' \to *FT'       &\text{Add }FIRST(T')-\{\epsilon\}\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(T')
                                                     &\text{no change}\\
              &\text{Add }FOLLOW(T')\text{ to }FOLLOW(F)
                                                     &\text{no change}\\
F \to (E)         &\text{Add })\text{ to }FOLLOW(E)      &\text{no change}\\
\end{array} $$

So the $FOLLOW$ sets are:
$$\begin{align}
FOLLOW(S) &= \{\}\\
FOLLOW(E) &= \{ )$ \}\\
FOLLOW(E') &= \{ )$\}\\
FOLLOW(T) &= \{ + ) $\}\\
FOLLOW(T') &= \{ + ) $\}\\
FOLLOW(F) &= \{ * + ) $ \}
\end{align} $$

That's a very simple grammar, of course. You might want to try it out with a more complicated one, although it is typical that it terminates after very few iterations and that many of the steps are obvious no-ops.


Adjacency-list to Adjacency matrix in logarithmic space?

Any time you have a problem parameterized by a number $n$ and you need an algorithm whose space usage is logarithmic in $n$, you should immediately think "loop counter". You can store numbers in the range $0$–$n$ in $\Theta(\log n)$ bits.

So, in this case, you can use an algorithm along the lines of

for i = 1 to n
    for j = 1 to n
        if j is in i's adjacency list
            write 1 to the output
        else
            write 0 to the output

The loop counters take $\log n$ bits each, and you might need a small amount of extra storage for book-keeping but you only need to store a constant number of data items, and none of those will be anything bigger than a number in the range $0$–$n$, so that's still only $O(\log n)$.


Stirling's formula asserts that
$$
n! = \Theta(\sqrt{n}(n/e)^n).
$$
Thus
$$
(\log n)! = \Theta(\sqrt{\log n}((\log n)/e)^{\log n}).
$$


$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.

You mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the parity of its left subtree, then you can do updates and lookups in time $O(\log n)$ each. That's fast, but not fast enough.

Now, consider the following generalization of your idea. Suppose that instead of using a binary tree, we use a multiway tree with branching factor $k$. We augment each key in each node with the parity of the all the subtrees preceding it (this generalizes the idea of storing the parity of the left subtree). Now, let's think about how we'd do a lookup or update in this tree. To do a lookup, we use a slightly modified version of the binary tree lookup algorithm from before: walk from the top of the tree down to the bottom, at each step accumulating the parity of the subtree purely to the left of each node. The height of the tree in this case will be $O(\log_k n)$ and we do $O(1)$ work per node, so the cost of doing a lookup will be $O(\log_k n)$.

However, with this setup, the cost of doing an update increases. In particular, if we change the parity of an element, we need to walk up from the bottom of the tree to the top, changing the stored parity of every key in every node on the path upward. There are $k$ keys per node and $O(\log_k n)$ nodes on the path upward from the leaves, so the cost of performing an operation like this will be $O(k \log_k n) = O(\frac{k}{\log k} \log n)$, which is too slow. If we could somehow eliminate this extra $k$ term, then we'd be in business.

The insight the paper has is the following. If you think about our initial problem, we had an array of size $n$ and wanted to be able to compute prefix parities. We now have a $k$-ary tree where, at each node, we need to be able to solve the prefix parity problem on arrays of size $k$ each, since each node caches information about the layers below it. In the above data structure, we solved the prefix parity problem at each node by just storing an array of the prefix parities, which means that if we need to perform an update, the cost is $O(k)$. The paper's insight is that by using a more clever data structure at each node, you can perform these updates significantly more efficiently.

In particular, the paper makes the following insight. Let's suppose that $k$ is "small," for some definition of small that we'll pick later. If you want to solve the prefix parity problem on an array of size $k$, then there are only $2^k$ different possible bit arrays of length $k$. Additionally, there are only $k$ possible lookup queries you could make on a bit array of size $k$. As a result, the number of possible combinations of an array and a query is $k 2^k$. If we pick $k$ to be small enough, we can make this quantity so small that it becomes feasible to precompute the result of every possible array and every possible query. If we do that, then we can update our data structure as follows. In each node of the $k$-way tree, rather than having each key store the parity of its left subtree, we instead store an array of $k$ bits, one for each key in the node. When we want to find the parity of all the nodes to the left of the $i$th child, we just do a lookup in a table indexed by those $k$ bits (treated as an integer) and the index $i$. Provided we can compute this table fast enough, this means that doing a prefix parity query will still take time $O(\log_k n)$, but now updates take time $O(\log_k n)$ as well because the cost of a prefix parity query on a given node will be $O(1)$.

The authors of the paper noticed that if you pick $k = \frac{\lg n}{2}$, then the number of possible queries that can be made is $\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$. Additionally, the cost of performing any operation on the resulting tree will be $O(\log_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$. The catch is that you now need to do $o(n)$ precomputation at the start of setting up the data structure. The authors give a way to amortize this cost away by using a different data structure for the initial queries until enough work has been done to justify performing the work necessary to set up the table, though you could argue that you need to spend $O(n)$ time building up the tree in the first place and that this won't affect the overall runtime.

So, in summary, the idea is the following:

Instead of using an augmented binary tree, use an augmented $k$-ary tree.
Notice that with small $k$, all possible $k$-bit lists and queries on those lists can be precomputed.
Use this precomputed data structure at each node in the tree.
Choose $k = \frac{\lg n}{2}$ to make the tree height, and, therefore, the cost per operations, $O(\frac{\log n}{\log \log n})$.
Avoid the upfront precomputation cost by using a temporary replacement data structure in each node until the precomputation becomes worthwhile.

All in all, it's a clever data structure. Thanks for asking this question and linking it - I learned a lot in the process!

As an addendum, many of the techniques that went into this data structure are common strategies for speeding up seemingly optimal solutions. The idea of precomputing all possible queries on objects of a small size is often called the Method of Four Russians and can be seen in other data structures like the Fischer-Heun data structure for range minimum queries or the decremental algorithm for tree connectivity. Similarly, the technique of using augmented balanced multiway trees with a logarithmic branching factor comes up in other contexts, like the original deterministic data structure for dynamic graph connectivity, where such an approach is used to speed up connectivity queries from $O(\log n)$ to $O(\frac{\log n}{\log \log n})$.


Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L

Yes, your algorithm is correct. The correctness can be proven by induction on $S$ easily.

Instead of growing by selecting the nearest point to $S$, a faster way in general should be just selecting the shortest edge available and including both of its end points. How to select the next shortest edge available? Construct a min-heap of all edges up front. Pop out the top of the heap one by one. Using a counter you can stop once all points are included. The length of the last edge included is the minimum edge size wanted.


Monte Carlo Tree Search in connect 5 tree design

In you implementation you need to separate the game rules from the mcts search algorithm. Mcts does not need an evaluation like minimax. When calling random playouts all you need to do is keep making legal moves till the game ends and mark the playout with an outcome of win/loss.

your game rules need functions like
legal_moves, make_move, undo_move, is_game_over, winnerIs and maintain a states that represent the position

your mcts needs
mcts, ucb_sample, expand, random_playout, backpropogation

for states you need
position {visits, value or total/count}


Time complexity to check if there is an edge between two nodes in an adjacency list

In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices.
Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{adjacent[u]}$.
A node can have at most $O(|V|)$ neighbors, from here the complexity follows.


Terminology - What does alphanumeric order mean in relation to decimals?

Alphanumeric sort means that every character is compared according to ascii representation.
Natural sort treats consecutive digits as one chatacter, so actually compares as integer. There is no place for decimals, but when you compare two numbers in the form $X.Y > W.Z$ it looks like decimal compare.

So what does "natural sort does not compare decimals" really mean?
The example above is just coincidence, like reading month.day as float and sorting will give good order, but adding and subtracting is not defined. Same here, "-" will not be identified as part of decimal, so comparison will be shifted. The separator might be given as anything, but will change results when inconsistent.


An O(n log sqrt(n)) sorting algorithm? Skiena TADM 2nd Question 4-28

Azzo is correct.  It's very simple:

$n\log \sqrt{n} = n\log n^{\frac{1}{2}} = \frac{1}{2}n\log n = \Omega (n\log n)$

Therefore Skiena's $O(n\log\sqrt{n})$ sorting algorithm does not violate the lower bound on comparison sorts.


Progress of algorithms in problem spaces

Yes and No. If you see this as "amortized" number of possibilities removed in each step, then yes (follows trivially since you need $n^2$ time but have a search space of $n!$), but it is very difficult to formalize a notion of how many possibilities in each step are removed. You would need a notion of what a "step" is. An elementary operation, like an addition? Then how does one addition in the middle of, for instance, bubble sort reduce the search space? Instead, you have some kind of "checkpoints" during the algorithm at which the search space gets smaller, for instance when you find the 1st element, the 2nd, and so on. A concrete counter example to your idea is an algorithm that uses $n^2$ time in a dummy loop, and then solves the problem. In the first $n^2$ steps therefore, the solution space does not get smaller.
No, see above.
Yes, trivially?


Is there a general algorithm to fill holes in terms of the Calculus of Constructions?

There is certainly a lot of research into this problem! It often goes by the name of elaboration. It is an undecidable problem in general, as you may have guessed. The "holes" are often called meta-variables or unification variables.

As I explain a bit in this answer, the problem reduces to higher order unification, on which several people have written whole PhD dissertations.

As you note in your examples, some cases are somewhat easy, and can be solved by the application of simple rules, whereas some seem significantly more difficult, and have more of a "theorem proving" feel to them.

A third possible case is a "type class" type problem, where ? represents some kind of structure, such as a group or field structure, as in

mul ? 2 3

with mul : forall G:Group, G.carrier -> G.carrier -> G.carrier or some variant. Here we need to find a G such that G.carrier == nat.

In general, you want to have 3 different "regimes" for each type of problem, the simple unification, theorem proving, and type class resolution problems respectively.

We explain this a bit in the following paper:

Elaboration in Dependent Type Theory, de Moura, Avigad, Kong & Roux.

You might want to look at the references of that paper for more info.

I've you've got a strong stomach, here is the open-source for elaboration in Lean.

Here is a wiki post that describes the interface to the elaborator in Idris.


What happens to uninterpreted predicates in Ackermann's reduction?

Essentially, you can treat uninterpreted predicates as boolean-valued functions (adding a new boolean sort if necessary) and replace them with boolean variables as you would other functions. For the given example:

Getting rid of $F$ and $G$ first:

$$\begin{align*}
p(z,f_1)&\wedge f_2=g_1\to p(x_1,y)\wedge x_1=f_1\to f_1=f_2\\
  &\wedge x_1=x_2\to f_1=f_3\wedge f_1=x_2\to f_2=f_3\\
  &\wedge (x_1=x_2\wedge g_2=x_3\wedge f_3=x_4)\to g_1=g_2
\end{align*}$$

Introduce boolean variables $b_1,b_2$ for $p(z,f_1)$ and $p(x_1,y)$, respectively, and add a condition that they are equivalent when the arguments agree:

$$\begin{align*}
b_1 &\wedge f_2=g_1\to b_2\wedge x_1=f_1\to f_1=f_2\\
  &\wedge x_1=x_2\to f_1=f_3\wedge f_1=x_2\to f_2=f_3\\
  &\wedge (x_1=x_2\wedge g_2=x_3\wedge f_3=x_4)\to g_1=g_2\wedge (z=x_1\wedge f_1=y)\to(b_1\leftrightarrow b_2)
\end{align*}$$


Solving functional equations for unknown functions in lambda calculus

This is a known problem, known as Higher Order Unification.

Unfortunately, this problem is undecidable in general. There is a decidable fragment, known as Miller's Pattern Fragment. It's used extensively in, among other things, typechecking of dependently-typed programs with metavariables or pattern matching. This fragment is where unification variables are applied only to distinct bound program variables.

This paper provides a great tutorial of how higher order unification works, and walks through a (relatively) simple implementation of it.

Unfortunately, it doesn't look like your function falls into this pattern fragment. That said, what I'm looking seeing is pretty similar to function composition. Does the following function satisfy your property?

$B = \lambda f\ g\ x\ \ldotp f\ (g\ x) $

We have:

$B\ f\ (\lambda x . M)$
$= B\ f\ (\lambda y . [y/x]M)$ by $\alpha$-equivalence
$ = \lambda x . f\ ((\lambda y. [y/x]M) x) $
$= \lambda x . f\ ([x/y][y/x]M)$
$= \lambda x . f\ M$


Interpretation of Turing's statement on universal computers

To understand what Turing means here, you first need to understand what Turing means when he uses the word "computer". He is not talking about any particular machine, but about someone or something that 'computes', where 'computing' means to transform inputs into outputs according to some specification or function.

The key difference between the everyday using of 'computer' and Turing's is the following: a 'computer' such as a pocket calculator or mobile phone consists of not only a 'computer' a la Turing, but also has an interface to this computer. Roughly, we can see this interface as a component that translates device input (touch screens, keys, etc.) to strings of 0's and 1's and translates this binary code back to device output (e.g. screen displays). This means that all the 'computer' has to do is compute on strings of 0's and 1's and leaves how to get input or present the output to the interface.

Now for the actual statement. What Turing says is the following:

If a computer can perform a certain (relatively simple) set of operations, we call it universal.
An universal computer can do anything another computer can do, given enough resources.

Part 1 should be clear. The 'resources' in part 2 is not very clear, but we can think a bit about what it means. Since a computer is something that only works with transforming binary code, the 'resources' of a computer are 'whatever is needed to perform this transformation on binary code'. What exactly are resources then depends on the type of computer: a mobile phone will need battery power to perform computations, while an engineer might be able to perform the same computations with a piece of paper and a good cup of coffee. Both of them will also need time to perform the computation.

We can now take a look at your calculator example. First of all, Turing's statement is only applicable if the simple calculators operations make it a universal computer. While a calculator is likely not universal, let's assume that it is for the moment. Then the computer 'inside'  the pocket calculator can do everything the computer 'inside' the graphical calculator can do, even though the graphical calculator can display things the pocket calculator cannot.

What you should realize is that the difference in displays is a difference in interfaces of devices, not of their computers. The pocket calculator may not be able to show you a function plot on the display, but the display can certainly show the coordinates of all points on the plot.


Does a time quantum affect priority non preemptive scheduling?

In non-preemptive scheduling the time quantum is not important for determining scheduling. The time quantum is only important when processes can preempt the CPU and 'cut' the line, such as in Round Robin scheduling. If you were given a time quantum for this problem I have a feeling it was stuck there to try to trip you up.

Your answer is correct though and it sounds like you understand the concept. Priority non-preemtptive scheduling can be visualized as a priority queue. If the queue is empty you can have the CPU, if not you get into line based on your priority and wait until whomever has the CPU releases it (on their own).


The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)

For a complexity class $\mathcal{C}$, we can define read-$k$-times $\mathcal{C}$ to be the set of problems $S \in \mathcal{C}$ for which there exists a $k$ such that an accepting computation for $S$ on input $w$ reads each bit at most $k$.

A consequence of a result from On lower bounds for read-$k$-times branching programs (1991) by Borodin, Razborov and Smolensky gives a separation between deterministic log space with unbounded reads and non-deterministic log space with bounded reads:

Proposition: There is a problem $S$ for which $S \in L$ but $S \not\in \text{read-}k\text{-times } NL$.

This means, to answer your question, we lose some languages since $L \not\subseteq \text{read-}k\text{-times }NL$ but $L \subseteq NL$.

My source of this proposition is from DynFO: A Parallel, Dynamic Complexity Class due to Patnaik & Immerman, who cite the BRS paper.


Are space allocated to C/C++ variables in secondary storage also in Compiled file?

Under most operating systems the binary executable and object files stored on disk contain three segments:

the .text segment (the code)
the .data segment stores the initial value for any global and static  variables that need to be initialized to specific values other than zero.
the .bss segment stores the global and static variables that don't need to be initialized, or are initialized to 0.  Typically only the size of the .bss segment is stored since the loader can easily create a segment in RAM of this size and fill it with zeros without wasting the time and disk space to store a bunch of redundant information in the executable stored on disk.

The wikipedia page https://en.wikipedia.org/wiki/Data_segment#Data gives some examples.

The stack and heap are typically not stored in the binary executable.  They are set up by the loader in RAM when the program is started.


How to show that all 2-terminal SP-graphs are O(log n)-outer-planar

The idea of the proof is to come up with a parameter of graphs $f(G)$ satisfying the following properties:

The outerplanarity of $G$ is $O(f(G))$.
If $G$ is the (serial or parallel) composition of two graphs $G_1,G_2$, then
$$ f(G) \leq \begin{cases} \max(f(G_1),f(G_2)) & \text{if } f(G_1) \neq f(G_2), \\
\max(f(G_1),f(G_2)) + O(1) & \text{if } f(G_1) = f(G_2). \end{cases} $$

If we are able to construct such a parameter, then your result follows (exercise). It could be that outerplanarity itself satisfies these axioms, but this is not clear. I was able to construct another parameter $f(G)$ which does satisfy these properties, and is very similar to the outerplanarity of $G$. Can you?

Here is my solution. For a two-terminal graph $G$, let $F(G)$ be the result of adding an extra edge connecting both terminals, and define $f(G)$ to be the outerplanarity of $F(G)$, when the extra edge is forced to be on the outer face. Clearly the outerplanarity of $G$ is at most $f(G)$.

It is easy to see that if $G$ is the serial composition of $G_1,G_2$ then $f(G) = \max(f(G_1),f(G_2))$. Now suppose that $G$ is the parallel composition of $G_1,G_2$. It is easy to see that $f(G) \leq \max(f(G_1),f(G_2)) + 1$. This is not good enough, however: we need to show that when $f(G_1) < f(G_2)$, then $f(G) = f(G_2)$ (without the $+1$). To that end, take a "good" planar embedding of $F(G_2)$ (with outerplanarity $f(G_2)$), and replace the extra edge with a copy of a "good" planar embedding of $F(G_1)$ (with outerplanarity $f(G_1)$). The result is a planar embedding of $F(G)$ with outerplanarity $f(G_2)$.


How correct was Justin Trudeau's explanation of Quantum Computing?

Trudeau's explanation wasn't wrong, but it also wasn't very informative.
Scott Aaronson, a well-known quantum computational complexity theorist, made a blog post discussing it:

What marks does Trudeau get for this? [...] Trudeau doesn’t really assert much here: basically, he just says that normal computers work using 1’s and 0’s, and that quantum computers are more complicated than that in some hard-to-explain way. [...]
[...] I’d grade Trudeau’s explanation as substantially more accurate than what you’d get from a typical popular article. [...] clearly suggests that he knows it’s more subtle than just “0 and 1 at the same time,” and he also knows that he doesn’t really get it and that the journalists in the audience don’t either. [...]
[Grade: B+].

There's a lot of discussion in the comments of that post.


Who first introduced the pushdown automaton?

Ginsburg (in his book The Mathematical Theory of Context-Free Languages, McGraw-Hill, 1966) states in the Historical References (Section 2.7, page 81):

  Pushdown acceptors were first formalized by Chomsky [Ch5] and Evey
  [Ev], although the notion of a pushdown tape has been used since 1954.

[Ch5] N.Chomsky, context-free grammars and pushdown storage, MIT Res. Lab. Electron. Quart. Prog. Rept. 65, 1962.

[Ev] R.J.Evey, The theory and applications of pushdown store machines, Mathematical Linguistics and Automatic Translation, Harvard Univ. Computation Lab. Rept. NSF-IO, May, 1963.

The context can be read from the Preface of the same book.

  The concept of a context-free language was first introduced by Chomsky
  in 1959 in an attempt to find a reasonable mathematical model of
  natural language such as English, French, etc. In the period
  1959-1960, several papers developing the theory were written. In the
  late 1960, it was discovered that the "ALGOL-like" languages, that is,
  the languages defined by Backus normal  form (the metalanguage used to
  describe the widely publicized programming language ALGOL-60), where
  identical with the context-free languages.  Since then, there has been
  a flurry of activity in the theoretical development of context-free
  languages. Much of this work has been done by those concerned either
  with natural languages in connection with computers, or with
  programming languages. The remainder has been by mathematicians and
  logicians intrigued by the inherent problems, techniques, and results.
  This activity has been given birth to a number of theoretical results
  of concern to computer science, and especially to programming
  technology. For example, we have the characterization of a
  context-free language in terms of a pushdown acceptor (a device used
  in the parsing aspect of compiling). [...]


How to convert improper CFG to weakly equivalent one?

First of all, Wikipedia does supply a reference to a standard textbook. Second, since a proper grammar is one without unproductive symbols, to make a grammar proper all you have to do is erase all unproductive symbols and all productions involving them.


Are statecharts with parallel states NFA, DFA, or none of the above?

The paper Parallel Finite Automata for Modeling Concurrent Software Systems contains a proof and examples showing that a (non-hierarchical) parallel state machine can be converted into a non-parallel version. The technique is somewhat obvious: simply create the cartesian product of all concurrent sections and you have a DFA.

Combine with a proof that any hierarchical section of a state machine can be flattened into an equivalent non-hierarchal version, and there exists an obvious—but hard for me to formally notate—conversion process that involves flattening hierarchies and expanding parallel sections from the leaves on upwards.

The result is that any SCXML state machine can be converted into an equivalent version that contains neither hierarchy nor parallel states. At this point the state machine may be DFA, NFA, or NFA with ε-moves (depending on the transitions used), but all of these are similarly equivalent.

In summary, I believe that any SCXML state machine can be converted into an equivalent DFA, and as such the formalisms of DFA apply.


Can we approximate the number of possible witnesses for an NP language?

The class of counting problems associated to languages in NP is called #P. More formally, $f:\mathbb{N}\rightarrow\mathbb{N}$ is in $\#P$ if there exists a nondeterministic polynomial time Turing machine $M$ such that for all $x\in\Sigma^*$, $f(x)$ is the number of accepting paths of $M$ on input $x$. This is equivalent to requiring the existence of a deterministic verifier $M(x,y)$ such that $f_M(x)=\big|\big\{y: M(x,y) \text{ accepts}\big\}\big|$.

You ask, given a language in $NP$ with it's verifier $M(x,y)$, can we approximate $f_M$? If the witnesses are of length $p(|x|)$ then obviously $0\le f_M(x)\le 2^{p(|x|)}$, but without knowing more about $M$ then we can't really say anything else about $f_M$. Note that computing $f_M$ is harder than asking whether a witness exists (obviously if you could count then you could determine existence). In fact, counting is considered much harder, as demonstrated by Toda's theorem (given an oracle for counting, one could decide the entire polynomial hierarchy in polynomial time).

So how hard is approximating such functions, or (allow me to focus on a specific $\#P$ complete language) how hard is it to approximate $\#SAT(\varphi)$, the number of satisfying assignments of a given CNF. In these lecture notes by Jonathan Katz, a constant factor approximation is considered, i.e. an algorithm producing a number inside the range $\left[2^{-k}\#SAT(\varphi),2^k\#SAT(\varphi)\right]$ for some fixed $k\in\mathbb{N}$. They show that with high probability, given an oracle for regular SAT, one can produce such an approximation in polynomial time (the algorithm can also be strengthen to yield an $1\pm p^{-1}(|\varphi|)$ approximation). So while exact counting is considered much harder than $NP$, an $NP$ oracle is enough to approximate $\#SAT$ with high probability.


The statespace explosion problem.

More specifically, software often uses unbounded loops, pointers into complex data structures on the heap, and dynamic allocation.  Each of these can cause rapid statespace explosion: the number of states increases rapidly, or becomes infinite.  Model checking has difficulty with that.  These constructs tend to be more common in software than in hardware, explaining why model checking tends to be more effective on hardware than on software (as a general rule, though there are of course exceptions).


Strongly connected and completely specified Moore equivalent of a Mealy Machine

Let $M_1 = \langle Q, \Sigma, \Delta, \delta, \lambda, q_0 \rangle $ be a Mealy machine where $\Delta$ is the output alphabet and $\lambda$ is the output function.

Let us denote states of the corresponding Moore machine by $q_{ib}$ if there is input $a$ and output $b$ such that $\delta(q_j, a) = (q_i, b)$. This means if the Mealy machine enters a state $q$ by emitting more than two different outputs then the state $q_i$ "splits". Also, denote corresponding Moore machine's transition function by $\delta'$.

Now consider two states $q_{ib_1}$ and $q_{jb_2}$ (of corresponding Moore machine). Existence of the state $q_{jb_2}$ implies that there is a state $q_k$ and input symbol $a$ such that $\delta(q_k, a) = (q_j, b_2)$. Since we made assumption that the Mealy machine is strongly connected, there is a string $w$ such that $\delta(q_i, w) = (q_k, b_k)$ for some output symbol $b_k$. So, we have
$$\delta'(q_{ib_1}, wa) = \delta'(\delta'(q_{ib_1}, w),a) = \delta'(q_{kb_k}, a) = q_{jb_2}$$
This shows that the corresponding Moore machine is also strongly connected.

As for the completely specification, let $q_{ib_1}$ be a state of the Moore machine, and $a$ is an input symbol. Then $\delta'(q_{ib_1}, a)= (q_{jb_2}, b_2)$, where $\delta(q_i, a) = (q_j, b_2)$, which shows it is completely specified.


One tape nondeterministic Turing machine accepting non-palindromes

Hint: to prove that a string $x_1x_2\cdots x_n$ is not a palindrome, we only need a value $i$ for which $x_i\neq x_{n+1-i}$.


I've used this compendium a few times...
Is this what you were aiming for?


Why do presenttations of proof systems in logic and automated reasoning not include the algorithm that finds proofs?

To simplify a bit, a system of inference rules generally defines a set of sequents, which are simply pairs of a list (or set) of propositions $\Gamma$ and a proposition $\phi$ written

$$ \Gamma \vdash \varphi$$

called the derivable sequents. The rules describe which sequents are derivable, and for any reasonable system, given $\Gamma\vdash\varphi$, and sequents $\Gamma_1\vdash\varphi_1,\ldots,\Gamma_n\vdash\varphi_n$, it is easy to tell whether

$$\frac{\Gamma_1\vdash\varphi_1\ldots \Gamma_n\vdash\varphi_n}{\Gamma\vdash\varphi} $$

is a valid derivation. This usually be done with some obvious algorithm.

Some much more difficult algorithmic questions are this:

Given $\Gamma\vdash\varphi$, is this sequent derivable?
Given $\Gamma$, how can we enumerate the set of $\varphi$ such that $\Gamma\vdash \varphi$ is derivable?

In general, there is no algorithm for answering question 1, and question 2 is quite difficult. In particular, when trying to prove $\Gamma\vdash\varphi$ a natural approach is to try to apply all possible rules until exhaustion. Several issues come up:

What order do we apply rules in?
How do we guess the $\Gamma_i\vdash \varphi_i$? If any variables appear on top that do not appear in the conclusion, you need to guess some instance for that variable.
When do we know if a derivation does not exist?

Because of the complexity of these issues, it's much more natural to separate the system of rules that describe the derivable sequents from the algorithms trying to find actual derivations of a given sequent.


Termination of Moore's algorithm to minimize deterministic automata

Most minimization algorithms assume automata to be complete s.t. for every state p and alphabet a, there is a transition where (p, a, q). Hence, for the case, we need to add one more state as a sink state.
The DFA becomes:

States: {1, 2, 3, 4}
Alphabet: {a, b}
Start : 1
Final : {3}
Transition :
{(1, a, 2), (1, b, 4), (2, a, 4), (2, b, 3), (3, a, 4), (3, b, 4),
(4, a, 4), (4, b, 4)}

By Moore's algorithm:

Picking edge(3,4) causes we mark edge(2,1) and edge(2,4) by b-transition.

Picking edge(2,4) causes we mark edge(1,4) by a-transition.

Now we don't have any unmarked edges left. Hence, no states has to be joined.


Is there a heuristic or function to determine if two arrays of integers are alike or similar

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures:

First, I consider distances most commonly associated with strings:

Edit distance: Here, we count minimum the number of 'edit operations' required to transform string $A$ into string $B$. These edit operations are usually inserting, deleting or substituting a single character in your string or array. Usually, the different operations have different costs. The Levenshtein distance is a special case of the edit distance that is commonly used to compare words.
Hamming distance: This distance simply counts the number of indices between two sequences that differ, which is the same method you described in your comment. This can at times be a decent metric, but it often doesn't come close to an our intuitive notion of 'similarity'.

There are many more string metrics, but those above are the most commonly known.

Next, you could also consider metrics over time series: here the sequences are interpreted as measurements at increasing time-steps. Usually, we assume there is some distance measure over the individual elements of your sequences, this can be taken as simply $d(x,y) = \begin{cases} 0 & \text{if $x=y$}\\ 1 & \text{if $x\neq y$}\end{cases}$, if you don't have a more reasonable notion of distance between your characters.

Dynamic Time Warping (DTW): This distance finds a suitable 'alignment' between the pair of sequence that minimizes the sum of the distances between the alignment. An advantage of this method is that this measure is insensitive to 'time shifts': The sequences $A=\langle 1, 2,3,4,5 \rangle$ and $B=\langle 0 ,1, 2,3,4\rangle$ have maximum Hamming distance, but a low DTW distance, as DTW is allowed to match the element $A[1]$ to $B[2]$, $A[2]$ to $B[3]$ and so on. Computing the DTW between two sequences takes $O(n^2)$ time (if both sequences have length $n$), but there are many faster approximations and heuristic speed-ups.
Longest Common Subsequence (LCS): This isn't always used as a similarity measure, but the length of a LCS between two sequences $A$ and $B$ can be seen as inversely proportional to the distance between $A$ and $B$ (i.e. long common subsequences mean high similarity). A disadvantage of this measure is that it often ignores too much of the relevant structure of the sequences, but it sometimes works fine.

Other similarity measures for time series can be found here.


Reducing one variant of Hamiltonian path to another

The simplest reduction, which is similar to what you were trying but simpler, is to add two new vertices to the graph in the instance of A: a vertex $v_s$ connected to $s$, and a vertex $v_t$ connected to $t$. Any Hamiltonian path in the new graph will connect $v_s$ to $v_t$, and so will restrict to a Hamiltonian path connecting $s$ to $t$. Vice versa, any Hamiltonian path in the original graph connecting $s$ to $t$ extends to a Hamiltonian path in the new graph connecting $v_s$ to $v_t$.


Are hardware specs relevant in software performance comparisons?

Yes, hardware specs are relevant.  No, relative performance differences are not hardware-agnostic.

Suppose I find that editing a certain movie on my laptop takes twice as long as printing a certain Word document on my laptop.  Does this mean if I do those two tasks on my desktop computer, the movie editing task will also take twice as long as printing the Word document?  No, not necessarily.

Maybe my desktop computer has a great GPU (graphics card) but my laptop doesn't have a GPU.  The GPU can be expected to speed up the movie-editing task, but it won't speed up printing from Word.  So, on my desktop it's even possible that the movie-editing task might be faster than the printing task.

This is one reason why hardware specs are relevant.


Checking if a given flow is a maximum flow

A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.


Proof that (x-y)(x+y) is more accurate than x²-y²

Suppose $y = x + \Delta$. Then $(x^2 - y^2) = x^2 - (x^2 + 2\Delta x + \Delta^2) = - (2\Delta x + \Delta^2)$ with leading term on the order of $2 \Delta x$. Multiply by $1 + \delta_1$ and that's still the leading term.

Compare to $(\delta_1 - \delta_2) y^2$ with leading term $(\delta_1 - \delta_2) x^2$.


Efficient Data Structure for Closest Euclidean Distance

It seems that the relevant data structure might be a dynamic Voronoi diagram.

Voronoi diagrams are often the answer when a set of points on the plane is involved.

In this case, since the point set is evolving, you want a dynamic version.


This is a consequence of the asymptotic equipartition property (AEP), which is a form of the law of large numbers. The AEP states that if a random variable has (binary) entropy $H$ and you take $n$ copies of it, then most of the data points have probability roughly $2^{-nH}$. This is only true for most data points, which is the source of the small statistical distance that you mention.

As an example, consider a $p$-biased coin. If you throw $n$ coins with bias $p$, then most likely you will get roughly $pn$ heads, each of which events has probability roughly
$$ p^{pn} (1-p)^{(1-p)n} = 2^{-nh(p)} .$$


Space complexity for finding the minimum number outside the list of numbers

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K<L$, $K=L$ or $K>L$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.


Examples for Partial Combinatory Algebras

Consider a subPCA $A$ of Kleene's first algebra. It contains $K$ and $S$. These are sufficient to implement every total computable function, so $A$ must contain at least these, and cannot be just some limited complexity class.

I do not quite understand why Kleene's second algebra and Scott's graph model aren't "topological". Kleene's second algebra is the universal 0-dimensional countably based Hausdorff space. Scott's graph model is the universal $T_0$ countably based space. These characterizations have no trace of computability, but because the spaces are universal it is to be expected that they have a very rich structure, and so can be made into models of $\lambda$-calculus.


There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to Buss.


Maxima of diagonals in a column wise and row wise sorted matrix

Great question! "Distance Transforms of Sampled Functions", by Felzenszwalb and  Huttenlocher shows how to compute this in $O(n \lg n)$ time.

"Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2}{\frac{\lg^2 n}{(\lg \lg n)^3}}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision tree model.


How to cluster images based on meta-information in tags

Yes, this has been studied, but the images seem to be completely irrelevant.

What you have is a set of texts, and you want to cluster them based on similarities.  You simply want to do text clustering.  A very simple way to start is to create a vector that represent each of the words.  Suppose that you have 1000 words.  Sort them, and you have a 1000 dimensional vector.  Now, each text (metadata) is represented by a vector with a 1 in position $i$ if the $i$th word is in the text and 0 otherwise.

Do clustering on these vectors as you normally would, you can easily start of with $k$-means clustering.


Comparing different implementations of genetic algorithms

Your first step, when doing a comparative analysis, is to identify your requirements.  We can't tell you what the requirements should be; that's something you'll need to figure out on your own.

Then, you can try to evaluate the libraries to determine how well they meet your requirements.  The particular style of evaluation depends upon what kind of requirement you want to evaluate.  For instance, evaluating performance is very different from evaluating reliability.


What does the "Lambda" in "Lambda calculus" stand for?

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006):

  By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to distinguish function abstraction from class-abstraction, and then changing “$\wedge$” to “$\lambda$” for ease of printing. This origin was also reported in [Rosser, 1984, p.338]. On the other hand, in his later years Church told two enquirers that the choice was more accidental: a symbol was needed and “$\lambda$” just happened to be chosen.


Would Schmidhuber's theories of everything be capable of performing hypercomputation?

If the hypothesis is that we live in a universe whose physics are computed by a Turing machine, then hypercomputation is trivially impossible in our universe.

The constants you're taking about are limits of computable numbers.  If all you have is a computer you can't produce such a number in finite time.

It sounds like you're taking two different things named after the same mathematician and assuming they're somehow connected when they're not.

(Disclaimer: I'm going off the information in the question alone.)


Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?

Yes, you can.

Kadanes's algorithm keeps the value of the best subarray in a variable, let's call it best_sum.
Notice the invariant in the algorithm.
best_sum will always (after each iteration) contain the value of the maxium subarray of the prefix of the array that you already visited.
Additionally you know the best suffix sum of the current prefix, let's call it current_sum, which you use to update best_sum.

You just need to do the same thing with the position.
Introduce three more variables current_startindex, best_startindex and best_endindex. current_startindex tells you, at which position the current best suffix starts. best_startindex and best_endindex indicate the start and end of the best subarray from the visited prefix.
Keep those variables valid in each iteration. E.g.
Whenever you update current_best, also update current_startindex.
And whenever you update best_max, also update the best_startindex and best_endindex, so that at the end of each iteration the value is correct.

After iterating over the complete array, best_sum will contain the sum of values of the maximum subarray, and best_startindex and best_endindex will tell you the positions.


Deciding whether set of running times is infinite

Suppose $L \in \textrm{RE}$.
Given a Turing machine $M$ you can construct another Turing machine $M'$ that takes an input $x$ and simulates $M$ on an empty input for at most $|x|$ steps.

If $M$ eventually halts, say after $c$ steps, $M'$ will always halt after at most $f(c)$ steps, (for some function $f$), regardless of the choice of $x$. This shows that $\textrm{Count}(M') \subseteq \{ 1, \dots, f(c) \}$ is a finite set.

If $M$ does not halt, then $M'$ will halt after simulating $|x|$ steps of $M$ for every choice of $x$. By picking different values of $x$ it is possible to build an infinite set of inputs such that each input results in a different running time of $M'$ (e.g, start with $x=$"1" and let $s$ be the number of steps taken by $M'$ on input $x$. The next value of $x$ will be a string of $s+1$ ones, so that $M'$ necessarily halts after some number $\ell$ of steps such that $\ell \ge s+1$. The next value of $x$ will have $\ell+1$ ones, and so on).

This shows that $\textrm{Count}(M')$ is an infinite set.

Therefore, since $L \in \textrm{RE}$ you have just found a way to accept all (and only) the Turing machines $M$ that do not halt on an empty input, showing that the complement of the halting problem is in $\textrm{RE}$.
This is a contradiction as it would imply that the halting problem is in $\textrm{R}$.


You don't need to use integers for any data. Just find the largest of three numbers x=max(a,b,c) and reduce both parts by x!. Then compute in doubles. For numbers as small as 500 both 32-bit ints and 32/64 bit doubles will be precise.

EDIT: Since 64-bit FP isn't enough to deal with 1500!, you can perform computations on (decimal) logarithms of multipliers.


Transitions needed for dividing two fixed integers

Using a Turing machine compiler I wrote I devised a program to do this in $O(c\log(q))$ transitions assuming $0 \le p < q$. More precisely it does it in $2 \lfloor \log_2(q) \rfloor +\lfloor \log_2(p) \rfloor + C$ states for some value $C$. I'm sure the value I found(~$409$) wasn't optimal.

The actual program itself is too long to include here(totaling $3584+18\lfloor\log_2(q)\rfloor + 9\lfloor \log_2(p) \rfloor$ lines) Here is the program in my pseudo language for approximating 5/9, it can be compiled with the program found here. The syntax for the language is also found there.

xn=1,4
while i decr {
    xnH=xn
    a=xnH
    a=a,0
    t=0,1
    while xnH decr {
        p=9,4
        while p decr {
            incr(a)
        }
        incr(t)
    }
    two=a
    two=two,2
    two=two,0
    first(two)
    while a decr {
        decr(two)
    }
    xnH=xn
    b=two
    b=b,0
    while xnH pop {
        b=b,1
        xn=xn,1
        incr(t)
    }
    pop(b)
    xn=xn,1
    while xn decr {
        p=two
        while p decr {
            incr(b)
        }
        incr(t)
    }
    xn=b
    incr(t)
}
xnH=xn
xnH=xnH,0
while xn decr {
    p=5,3
    while p decr {
        incr(xnH)
    }
    incr(p)
}
incr(xn)

xnH holds the final value(the whole thing is assumed to be after the decimal point). It shouldn't be too hard to extract out a single digit from it(in $O(1)$ states). Also as a note even for small values of i this program takes quite a long time to execute.


Doubts on Definition of Indistinguishable Encryption in the Textbook

Depends on how different your algorithms are. If you can compute $A_i$ from $i$ in polynomial time, then $A'$ with $A'(n) = A_n(n)$ is a polynomial time adversary too and violates the assumption (as it has non-negligible success probability). This would make your series of $A_i$ uniform and is one usual class of adversaries to consider.

If you'd like your crypto system to be secure against any such series of polynomial bounded adversaries you have to consider non-uniform adversaries (at least non-uniform in polynomial time), by e.g. defining a single adversary as a series of (randomized) circuits with polynomial size.


How to reformulate my problem as a mixed-integer quadratic problem

So it sounds like the problem is the following:

  Given $A,B,y,z$, I want to find the vector $a \in \mathbb{R}^n$ that minimizes $||y-Az-ABa||_2$, subject to the constraint that there must exist some matrix $P_s$ with exactly $s$ 1's on its diagonal and 0's everywhere else, satisfying $P_s (z+Ba)=0$.

Mixed-integer QCQP

This can be formulated as a mixed-integer quadratically constrained quadratic programming problem, as follows.

We have $n$ unknowns $a_1,\dots,a_n$, so $a=(a_1,\dots,a_n)$.  Also introduce $n$ integer zero-or-one unknowns $p_1,\dots,p_n$, with the intention that $P_s$ will be the diagonal matrix whose diagonal is $p_1,\dots,p_n$.  Add the cosntraint that $p_1+\dots + p_n=s$, to ensure that exactly $s$ of the entries on the diagonal are $1$.  Note that each entry of $z+Ba$ is a linear expression in the unknowns, so the constraint $P_s (z+Ba)=0$ can be expressed as $n$ quadratic constraints, each of the form $p_i \cdot e_i=0$ where $e_i$ is linear in $a_1,\dots,a_n$.

Now note that each entry of $y-Az-ABa$ is a linear expression of the $n$ unknowns $a_1,\dots,a_n$, so the objective function is a quadratic function of the unknowns.

Unfortunately, mixed-integer QCQP is a pretty challenging form of non-linear programming, so I don't know how well this will work in practice.  You might have to try it out with some solvers.

This is a pretty brain-dead approach.  There may be smarter approaches that are more effective than this, by taking advantage of the structure of your problem.


Type theory for imperative programming languages?

Sure there are type systems for all sorts of programming languages, including the imperative ones. It's probably best to look at something simple first that exposes the gist of the matter. A classic is John Reynold's The essence of algol, which was quite influential historically, and develops many important ideas.


"Given an algorithm, decide whether it runs in polynomial time" is this problem in NP?

No.  If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.
Why in exponential time?  Because $V$ runs in time $|w|^k$, it can read at most $|w|^k$ bits of the input.  So, it suffices to enumerate all possible strings $c$ of length at most $|w|^k$, and run $V$ on each of them.  The running time will be about $2^{|w|^k}$, which is finite and thus enough to make the original problem decidable.


Here is an elaboration of your approach. Every $m$ iterations, we use the FFT algorithm to compute $m$ values of the convolution in time $O(n\log n)$, assuming that the subsequent $m$ values are zero. In other words, we are computing
$$
\sum_{i=0}^{n-1} w_i a_{t-i+k}, \quad 0 \leq k \leq m-1,
$$
where $w_i$ are the $n$ weights (or the reverse weights), $a_i$ is the input sequence, $t$ is the current time, and $a_{t'} = 0$ for $t' > t$.

For each of the following $m$ iterations, we are able to calculate the required convolution in time $O(m)$ (the $i$th iteration needs time $O(i)$). So the amortized time is $O(m) + O(n\log n/m)$. This is minimized by choosing $m = \sqrt{n\log n}$, which gives an amortized running time of $O(\sqrt{n\log n})$.

We can improve this to worst-case running time of $O(\sqrt{n\log n})$ by breaking the computation into parts. Fix $m$, and define
$$ b_{T,p,o} = \sum_{i=0}^{m-1} w_{pm+i} a_{Tm-i+o}, \quad C_{T,p} = b_{T,p,0}, \ldots, b_{T,p,m-1}. $$
Each $C_{T,p}$ depends only on $2m$ inputs, so it can be computed in time $O(m\log m)$. Also, given $C_{\lfloor t/m \rfloor-p,p}$ for $0 \leq p \leq n/m-1$, we can compute the convolution in time $O(n/m + m)$. The plan therefore is to maintain the list
$$ C_{\lfloor t/m \rfloor-p,p}, \quad 0 \leq p \leq n/m-1. $$
For each period of $m$ inputs, we need to update $n/m$ of these. Each update takes time $O(m\log m)$, so if we spread these updates evenly, each input will take up work $O((n/m^2) m\log m) = O((n/m) \log m)$. Together with computing the convolution itself, the time complexity per input is $O((n/m)\log m + m)$. Choosing $m = \sqrt{n\log n}$ as before, this gives $O(\sqrt{n\log n})$.


Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

Here's the basic idea.

Let a dyadic interval be an interval of the form
$$ [2^b a,2^b(a+1)-1] $$
for some integer $a,b \geq 0$.

Claim 1. If $m < 2^n$ then any interval of the form $[0,m-1]$ can be written as the disjoint union of at most $n$ dyadic intervals.

Proof. Expand $m$ as a sum of decreasing powers of 2:
$$ m = 2^{a_1} + \cdots + 2^{a_k}. $$
Then we can write
$$
[0,m-1] = [0,2^{a_1}-1] \cup [2^{a_1},2^{a_1}+2^{a_2}-1] \cup \cdots \cup [2^{a_1} + \cdots + 2^{a_{k-1}},2^{a_1} + \cdots + 2^{a_k}-1].
$$

Claim 2. If $0 \leq m_1 \leq m_2 \leq 2^n$ then any interval of the form $[m_1,m_2-1]$ can be written as the disjoint union of at most $2n$ dyadic intervals.

Proof. The binary expansion of $m_1$ and $m_2$ is of the form $m_1 = x0y, m_2 = x1z$, where $|y|=|z|$. Let $m = x10^{|z|}$. Using Claim 1, we can express $[0,m_2-m-1]$ as a union of at most $n$ dyadic intervals. Shifting these by $m$, we express $[m,m_2-1]$ as a union of at most $n$ dyadic intervals. Similarly, using Claim 1 we can express $[0,m-m_1-1]$ as a union of at most $n$ dyadic intervals. Shifting and inverting, we express $[m_1,m-1]$ as a union of at most $n$ dyadic intervals.

(In both cases, one needs to check that shifting, and possibly inverting, preservers an interval being dyadic.)


How to prove/disprove distribution of division over union

Ok so i figured it out. Let $L_1$, $L_2$ be relation sets where $L_2$ is a subset of $L_1$. We know $R$ and $S$ are subsets of $L_1$ and $X$ is a subset of $L_2$. Since we do not know whether $X$ is a subset of $R$ and $S$, we can give the following counter example:

Suppose
$$\begin{align*}
  L_1 &=(1,2,3,4,5,6,7,8), \\
  R &= (1,2,3,4), \\
  S &= (5,6,7)\; \text{and}\\ X &= (1,3).
\end{align*}$$
Then, $(R \cup S) / X = (2,4,5,6,7)$ whereas $R / X$ and $S / X$ are illegal.


You want to solve the problem of graph isomorphism (GI). GI is not known to be in P or NP-complete; that is, we do not know any efficient algorithms.

Many algorithms have been proposed for GI. None applies to all graphs and is always fast, but you may be able to find one that is sufficiently fast in your application.

In 2015, Babai proposed a quasi-polynomial algorithm for GI [1]. As far as I know, peer-reviewed is not yet completed; I also do not know if it is practically feasible. If correct, it is the most "efficient" algorithm known in terms of Landau-style complexity.

Graph Isomorphism in Quasipolynomial Time by L. Babai (2015) [retraction note]


When is a regexp is not a Regular Expression?

tl;dr backrefs.

As soon as there is a \1 (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.

Backrefs allows you to match (a+)b\1 which matches n times a followed by b followed by n times a for any n>1. This is not a regular language (it's the poster child of a non regular language).

It is necessary and nearly sufficient that the backref references a group that contains a regexp that matches an arbitrarily long string or that it contains a * or +. The only exception (that I found) of a regexp of the form (A)B\1 where A is a finite language (could be replaced by a enumeration of all words that accepts them). You can convert it to word1+Bword1|word2+Bword2 etc. because A is finite.

Look-around groups don't remove the regularness of the regexp. A(?=B)C is the cross-section of regexes AB.* and AC and the cross-section of 2 regular languages is regular. Negative lookahead is similar except using the complement of B.* (complements of regular languages being regular). Lookbehind is exactly the same as well A(?<=B)C is the cross-section of AC and .*BC.


What are some comparative studies on program termination verification tools?

As mentioned by nekketsuuu, SV-COMP has a termination category, and the Termination Competition has been going on for quite some time (there is some overlap).

It depends on what kind of termination you are interested in. This paper on AProVE gives an overview of that tool, which covers many of the techniques involved in general program termination analysis and types of programs that can be handled, though it does not really analyze the comparative strengths of different tools.

Sadly, I'm not aware of any modern overview paper that does this, which is unfortunate. The tool description papers of the competition participants for your category of choice would be a good place to start.


Are conditionals necessary in computation?

One argument that conditionals are not fundamental to computation is that there are turing complete models of computation that don't use anything resembling conditionals. For example, you can think of the lambda calculus as an untyped programming language where the only operation is function application. There is no branching involved: all the computation is just taking the function's arguments, and substituting it in for all uses of that argument inside the function itself.

But, another way of looking at this is that any turing complete model of computation can simulate conditionals in some way. For example, a simple idea for branching in the lambda calculus is that "true" is a function that takes 2 inputs, an if branch and an else branch, and then returns the if branch $(\lambda x. \lambda y . x)$. Meanwhile "false" is a function that takes 2 inputs, an if branch and an else branch, and returns the else branch $(\lambda x. \lambda y . y)$.

Then, in the lambda calculus, a program like "if T then foo else bar" would be encoded like $(T)(foo)(bar)$, which is to say applying foo and bar as arguments to the function T.

Or, more trivially, every turing complete model can simulate the turing machine, which is a state machine (and thus evaluates based on a conditional at every time step).

Anyways, as for the more realistic models of computation that you are used to, one reason you need conditionals is because if you didn't have conditionals, every program you write would either loop forever or execute in O(1) ((where we consider the size of your program to be constant)). Think about it: no conditionals means no loops (unless you use an unconditional jump, but then you will just loop forever). But, without loops, each line of your program will be executed exactly once. Thus, every program runs in O(1). This essentially means you can't solve any interesting problems.

However, I would argue that the more fundamental issue here is that loops (or some equivalent, such as combinators) are fundamental for computation. If you remove the ability to make a "goto", then even with conditionals your language will not be turing complete (by the same argument: your code will simply execute along some control flow path exactly once then terminate in O(1), and not every problem can be solved in O(1)).


Can epsilon be in the input alphabet of an FST?

The alphabet $\Sigma$ of an automaton can be any nonempty set of finite symbols. Surely Greek-speakers would be upset if we forbade $\{\alpha, \beta, \dots, \epsilon, \dots, \omega\}$ as a valid alphabet! If you want, you can use $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ as your alphabet.  Or $\{A, \alpha, \clubsuit,8\}$. Or any other finite, nonempty set.

However, certain symbols have special meanings and we tend not to use them in automaton alphabets. For example, if you want your alphabet to consist of the symbols $\}$ and $\{$, things get a bit awkward: you start writing $\Sigma = \{\},\{\}$ and, er, yeah, that doesn't quite work.  Likewise, it's confusing if $\Sigma$ contains symbols such as ${}^*$, $($, $)$, $+$ and so on: you can easily write $\Sigma = \{{}^*, (, ), +\}$ but, now, when you try to write regular expressions over that alphabet, it's impossible to tell which characters in the regular expression are symbols from $\Sigma$ and which are operators in the regular expression.

$\epsilon$ fits into this second class. When $\epsilon$ isn't in the alphabet, we use that symbol to denote the empty string. As such, if you include $\epsilon\in\Sigma$, it becomes unclear whether writing "$\epsilon$" means "the empty string" or "the string containing one symbol, which is the Greek equivalent of 'e'". So, as a practical matter, we usually prefer not to use $\epsilon$ as a symbol in the alphabet. If you do need to include $\epsilon$ in your alphabet, you should use some other symbol to denote the empty string and you should say so. Similar reasoning applies to all other symbols that could be confused in this and other ways.


Number of compatible trees with an ancestry matrix

As hinted in the comments by @j_random_hacker, ancestry matrix, if valid, characterizes a unique rooted tree. A simple algorithm would be to create the tree from leaves to the root or vice versa.


The subset construction can be computed (and negated) in polynomial space. Remember that the output doesn't count as part of the space usage in bounded space computation.

Determinization can exponentially increase the number of states: the language of $0$–$1$strings such that the $k$th-from-last character is $0$ can be recognized by an NFA with something like $k+1$ states, but any DFA for that language has at least $2^k$ states.

So determinizing doesn't give you a polynomial space algorithm to determine if an NFA accepts its input.  But you can simulate all computation paths of the NFA simultaneously: as you read the input, just keep track of the set of states the automaton could be in, and see if that set includes an accepting state once you've read the whole input.


How is ARC consistency un-done after a recursive failure condition?

The obvious answer is: take a snapshot (checkpoint) of your state before applying the arc consistency inferences; recursively explore that option; and then if it is a failure, restore the state back to your snapshot.

Whether this is efficient depends upon the size of the state and the amount of work done during the recursive call.  For this particular application (Sudoko), I suspect you don't have much state, so I expect this will be a perfectly reasonable solution.

In more complex situations, you can use more sophisticated data structures that support undo/rollback.  For instance, persistent data structures are one way to make rolling back to a prior version faster, in some cases.  Partial persistence is enough; you don't need full persistence or confluent persistence.  However, for simple cases like this one, the overhead of persistence might outweigh any gain from avoiding copying the state.

If you want us to recommend a more efficient solution than the naive copying approach, you'll need to specify in greater detail what sort of data structures you need for this application (e.g., for storing the set of constraints).


How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

Suppose towards a contradiction that  $L$ is context-free and let $c$ be the pumping length of $L$.
Consider the word $a^{c^2} b^c$ which, by the pumping lemma, can be written as $uvwxy$ with $1 \le |vx| \le c$.

Notice that:

$vx$ cannot contain only $b$s, since otherwise $uwy \not\in L$.
$vx$ cannot contain only $a$s, since otherwise $uv^2wx^2y \not\in L$.
none of $v$ and $x$ contains both $a$s and $b$s, since otherwise $uv^2wx^2y \not\in L$.

We conclude that $v$ contains only $a$s, $x$ contains only $b$s, and $x$ contains at least one $b$. Then, by the pumping lemma, $a^{c^2-|v|} b^{c-|x|} = uwy \in L$. This is a contradiction since:
$$
(c  - |x|)^2 \le (c - 1)^2 = c^2 - 2c + 1 \le i^2 - c < i^2 - |v|.
$$


Pseudo code of recursive method of printing all permutations of $n$ given integers

Your procedure produces all permutations of the input, returning it to its original state at the end.

When the input has length 1, there is nothing to do.

Otherwise, suppose that the input is $a_1,\ldots,a_n$. Let us represent all permutations of $a_1,\ldots,a_n$ as $[a_1,\ldots,a_n]$.

Here is what the procedure does:

Output $a_1,[a_2,a_3,\ldots,a_{n-1},a_n]$.
Output $a_2,[a_1,a_3,\ldots,a_{n-1},a_n]$.
Output $a_3,[a_2,a_1,\ldots,a_{n-1},a_n]$.
...
Output $a_n,[a_2,a_3,\ldots,a_{n-1},a_1]$.

In the first step, the procedure just goes over all permutations of the tail of the list, consisting of all but the first element.

In the second step, it switches $a_1$ and $a_2$, goes over all permutations of the tail, and then switches $a_1$ and $a_2$ back.

In the third step, it switches $a_1$ and $a_3$, goes over all permutations of the tail, and then switches $a_1$ and $a_3$ back.

And so on, until in the $n$th step, it switches $a_1$ and $a_n$, goes over all permutations of the tail, and then switches $a_1$ and $a_n$ back.


Use minimum number of swaps so each bin contains balls of the same color

Maximal decomposition of an Eulerian directed graph into edge disjoint cycles is NP-Hard, at least according to this book: Algorithms and Applications:
Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday.

btw, here is an article which is relevant to the problem you seem to be trying to solve: Asymptotically optimal algorithm for the Dutch National flag algorithm.

For $n \le 6$, the paper gives a simple algorithm.


Are machine codes always numerical? (WIkipedia is Ambiguous)

Yes and no and, really, it doesn't matter.

All data in computers, including programs, is stored in devices that have two possible states – e.g., memory cells that can be at a high voltage or low voltage or areas of a disc that are magnetized north–south or south–north. These two-state systems are naturally interpreted as the binary digits 0 and 1.  Any sequence of 0s and 1s can naturally be interpreted as a number written in binary.

Machine code is data that is stored on computers. Therefore, it is stored in a sequence of two-state cells, which can be viewed as a sequence of binary digits, which can be viewed as a binary number (or a sequence of binary numbers if you divide it into blocks). Does that mean it is a binary number? Really, that's a question of philosophy. The computer doesn't say "That pattern of 1s and 0s represents the number 3476247, which means I should do X": it just says "That pattern of 1s and 0s means I should do X." To the computer, it's just an instruction. But if you and I want to talk about that instruction, it's probably easiest to first see it as a number and then figure out what instruction it stands for.


Find the number of strings in the language $(∅∅^∗ + ∅)$

Your language could be simplified as follows, using $\emptyset^* =\{\epsilon\}$:

$$
\begin{align*}
L(\emptyset\emptyset^*+\emptyset)
&=L(  \emptyset . \{\epsilon\} + \emptyset) \\
&=L(\emptyset +\emptyset) &    (\emptyset.\{\epsilon\}=\emptyset) \\
&=L(\emptyset) & (\emptyset + \emptyset = \emptyset)
\end{align*}
$$

So the language L accepts empty language which is $L =\{ \}$, which means that it contains zero elements.

Please be aware that the empty language is different from language consisting of the empty string, which is $L =\{\epsilon\}$, and which contains the element $\epsilon$, while the empty language contains zero elements.


Is bounded waiting satisfied in the 2 Process Solution?

A little remark first: The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm satisfies BW if a specific execution does.

For your question: For the specific execution in which only $P_1$ takes steps, BW is satisfied. However, it is not because "there exists a bound on the number of processes that may enter after process desires to enter CS". Instead, BW is satisfied simply because $P_2$ does not desire to enter the critical section. See the following definition from Mutual Exclusion (wiki).

  A $k$-bounded waiting property can provide a bounded waiting guarantee and it requires in every execution, a process can only enter the critical section at most $k$ times while another process is waiting to enter the critical section.

A more precise definition can be found in the Book: The Art of Multiprocessor Programming; Exercise 9 in Section 2.10:

  Define $k$-bounded waiting for a given mutual exclusion algorithm to
  mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.

Here, $D_A^j$ means process $A$ finishes its doorway section for the $j$-th time, and $CS_A^j$ denotes the interval during which $A$ executes the critical section for the $j$-th time.

In the execution above, $D_{P_2}^j \to D_{P_1}^l$ does not hold because $P_2$ does not take any steps at all. Thus, BW is trivially satisfied.

Suppose that $P_2$ has finished its doorway section (i.e., $D_{P_2}^1$ holds) and then halts. If $P_1$ continues entering and exiting the critical section, then BW is broken.

A little remark again:

  I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS.

It seems that you have a misunderstanding about $k$-bounded waiting property. $K$ here is about the number of entering (and exiting) the critical section, instead of the number of processes.


Complexity of testing if a number is a primorial

This is simpler than factoring.  You can simply multiply all prime numbers up to the point where you (a) reach $p_n$ or (b) get a product which is larger than $p_n$.  In the first case, you answer yes otherwise you answer no.

The reason it is simpler is that the prime factorization is trivial, whereas in the FACTORING problem, you don't know how many of each prime number you need.


Is the language of all words of the form $wxw^Rx^R$ context-free?

Denote your language by $L$, and consider
$$
L' = L \cap 10^*1110^*10^*10^+11.
$$
Any word in $L'$ is of the form
$$
10^a1110^b10^c10^d11,
$$
where $d > 0$.
Also, it is of the form $wxw^Rx^R$. Since both $wx$ and $w^Rx^R$ contain the same number of $1$'s, necessarily
\begin{align}
wx &= 10^a1110^{b_1} \\
w^Rx^R &= 0^{b_2}10^c10^d11
\end{align}
where $b_1 + b_2 = b$. We see that $x^R$ ends with $110$ (since $d>0$), and so $x$ starts with $110$. Hence $w = 10^a1$ and $x=110^{b_1}$, implying that $w^Rx^R = 10^a10^{b_1}11$. This shows that $b_2 = 0$ hence $b_1 = b$, and furthermore $c = a$ and $d = b$. That is, the word is of the form
$$
10^a1110^b10^a10^b11,
$$
where $b > 0$. Conversely, every word of this form is in $L'$ (take $w = 10^a1$ and $x = 110^b$).
Let $h\colon \{1,2,3,4,5\} \to \{0,1\}$ be the homomorphism given by $h(1) = 1$ and $h(2) = h(3) = h(4) = h(5) = 0$, and let $d\colon \{1,2,3,4,5\} \to \{2,3,4,5\}$ be the homomorphism that deletes $1$. Then
$$
d(h^{-1}(L') \cap 12^*1113^*14^*15^*11) \cup \{2^n4^n : n \geq 0\} = \{2^n3^m4^n5^m : n,m \geq 0\}.
$$
The latter language is well-known not to be context-free. Since all our operations preserve being context-free, we conclude that $L$ is also not context-free.


Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

Geographic information systems use spherical triangular quadtrees to solve this problem. They are analogous to a quadtree, but defined over a sphere using triangular patches.

There are different variants with different bells and whistles, but you can refer to Quaternary Triangular Meshes (Dutton. "Encoding and Handling Geospatial Data with Hierarchical Triangular Meshes"), Sphere Quadtrees (Fekete. "Rendering and managing spherical data with sphere quadtree") and HTMs (Kunszt. "The Hierarchical Triangular Mesh") as approaches you can extrapolate from.

The basic idea is that you partition the sphere into coarse triangular patches, then subdivide those patches into smaller triangular patches recursively as needed. You can then perform basic queries like you would on a quadtree.

See Chen. "An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM" for a survey of different techniques, and related problems.


Closed formula for two variable recurrence

I do not have a strong mathematical background, but I am afraid that recursive functions cannot always been written in closed form.

ex1.

f(n) = sum([1,2,..,n]) can be written as
f(1) = 1
f(n) = n + f(n-1)

Of course f(n) = n*(n+1)/2

ex2.

f(n) = prod([1,2,3,4,..n]) = n!
f(1) = 1
f(n) = n * f(n-1)

No known closed formula :( (I don't even know how to prove something like this)

In your case, I find it extremely difficult because your recursion makes use of an if statement under the min() function.


How to implement mutex on single processor (single core) system other than using spinlock

It is impossible to implement a mutex completely in userspace unless you have special CPU instruction that could simulate a semaphore or a lock (some "test and increment if true" instruction). pthread in Linux goes through the kernel to implement the mutex.


minimum cardinality maximal matching of graph

A 2-approximation can be obtained by returning a maximal matching, Call it M.
Let OPT be a minimum maximal matching then for each edge in M OPT covers at least one of its endpoints thus: |OPT|>=|M|/2
It would be better if you’ll be more explicit about what you did and what you’d like the algorithm to achieve (analysis of your idea, approximation factor, so on...)


If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?

If $f = O(g)$, then

$$\exists n_0. \exists c. \forall n. (n > n_0 \rightarrow f(n) \le c g(n))$$

The negation of this statement is

$$\forall n_0. \forall c. \exists n. (n > n_0 \land f(n) > c g(n))$$

This doesn't match your negation, so I believe your proof is incorrect.

I actually think the statement you're trying to prove is false. Try constructing functions f and g so that f is double g for a while, then g overtakes f and is triple f for a while, the f overtakes g and is quadruple g for a while, etc. Could you show that neither function is O of the other?

Hope this helps!


Is it possible to define a DFA for the language of words having exactly one double letter?

In general, if you claim to have found a regular expression for the language, you can follow Thompson's algorithm to convert that expression into an NFA and then using subset construction to convert that NFA into a DFA.


How to prove a L=L(G) without knowing the L?

In cases like this, where you have a grammar and want to guess what the language is, a good way is to approach the problem systematically, by trying to derive some short strings. For example, if you had a grammar $G$ like this,
$$\begin{align}
S &\rightarrow SA \tag{1}\\
S &\rightarrow \epsilon \tag{2}\\
A &\rightarrow aS \tag{3}\\
A &\rightarrow bA \tag{4}\\
A &\rightarrow \epsilon \tag{5}
\end{align}$$
then here are a few derivations, where the relevant production is labeled:
$$\begin{align}
\epsilon&: S \stackrel{2}{\Longrightarrow}\epsilon\\
a&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}aS\stackrel{1}{\Longrightarrow}a\\
b&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}bA\stackrel{4}{\Longrightarrow}b\\
aa&: S \stackrel{1}{\Longrightarrow} SA\stackrel{1}{\Longrightarrow}SAA\stackrel{2}{\Longrightarrow}AA\stackrel{3}{\Longrightarrow}aSA\stackrel{1}{\Longrightarrow}aA\stackrel{3}{\Longrightarrow}aaS\stackrel{2}{\Longrightarrow}aa\\
\end{align}$$
If you try this for, say $ab,ba,bb$, you'll find that they're all in $L$ which prompts a guess that this grammar generates all strings over the alphabet $\{a,b\}$. This isn't too hard to show, by induction on the length of a string in the language.

The proof goes like this:

Base. Show that the length-0 string, $\epsilon\in L(G)$. (We've done this already.)

Induction. Let $w$ be any string of length $n>0$. Our inductive hypothesis is that any shorter string, $z$ is in $L(G)$, i.e., there is a derivation $S\stackrel{*}{\Longrightarrow}z$. Now either $w=za$ or $w=zb$. We'll do one case and leave the rest to you:
$$
S\stackrel{1}{\Longrightarrow}SA\stackrel{3}{\Longrightarrow}SaS\stackrel{2}{\Longrightarrow}Sa\stackrel{*}{\Longrightarrow}za = w
$$
so $w\in L(G)$, as required.