It seems that your tables are 1-dimensional. So basically for an integer $x$ you define some value $T[x]$ and you are looking for a function $f$ such that $f(x)=T[x]$.

There is a name for the problem that tries to find a function that runs through a given set of sample points, this is known as interpolation. Your problem is special, since your sample points are given by $(x,T[x])$ and the $x$s are the indices of your table.

The most classical approach is to use a polynomial as a function (but there is also theory about other classes of functions). It is a well known theorem that if you have $n$ samples, then you can find a polynomial $f(x)=\sum_{i=0}^{n-1} a_i x^i$ that coincides with your samples. There are different ways how determine the $n$ parameters $a_i$ of the polynomial.

One way to determine the polynomial is the method of Lagrange, you define for every index $i$ of you table the coefficient
$$L_i(x):=  \prod_{j=1,j\neq i}^{n} \frac{x-j}{i-j}.$$
If you look how $L_i(x)$ behaves on the samples, then you get
$$L_i(x)=\begin{cases} 1 & x=i  \\ 0 & x= \text{table index}\not= i \end{cases}.$$

Now you can easily come up with the desired polynomial by setting
$$f(x):=\sum_{i=1}^n T[i]L_i(x).$$
You can bring $f$ in the form $\sum_{i=0}^{n-1} a_i x^i$ if you like.

Concerning you example {4,5,7}, you get $$f(x)=4 ((x - 2)/-1*(x - 3)/-2) + 5 ((x - 1)*(x - 3)/-1) +
 7 ((x - 1)/2*(x - 2))),$$
which simplifies to
$$f(x)=4-\frac{x}{2}+\frac{x^2}{2}.$$

For further reading visit the Wikipedia page on interpolation.

Here is a final remark. The table has in almost all cases the more compact representation, and it has the faster look-up time for sure.


Typical set in Shannon's source coding theorem

The elements in the typical set have typical probability, close to $2^{-NH(x)}$. An element with untypically large probability, say the one with maximal probability, may not satisfy this constraint. Same goes for the rest of $S_\delta$.

The source coding theorem does take the typical set as an encoding scheme.


A key-value datastructure with fast (on average) member move and nearest neighbors search?

An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.


What is responsible for the 1-1 correspondence between characters and binary?

Internally, everything is binary and only binary. The only places that characters exist are places where you can literally see them with your eyes. For your benefit, and your benefit only, the system contains code that associates pictures such as a or 6 with those binary values and displays those pictures on the screen or on printer paper.


Simulating a TM with a 2-head, right moving TM

Yes you can simulate a standard Turing machine, indeed you can easily simulate a Tag System which is Turing complete (and can simulate a Turing machine with only a polynomial-time slowdown).

Informally to simulate a k-tag system, you keep the write head at the end of the tape (on the first blank symbol) and use internal states to store the production rules; with the read head you can read k symbols, and append the symbols of the corresponding production rule at the end of the tape.

For example if you have a 2-tag system with the following production:

a --> aab

and the tape is:

a b a b c a b c _
^               ^
Read            Write

you can read the first two symbols and apply the production:

a b a b c a b c a a b _
    ^                 ^
    Read              Write

Furthermore it is also easy to see how a k-Tag system can simulate a Turing machine; a hint: use a special symbol to mark the position of the head, and just rewrite (with one symbol of delay) on the right what you read with the read head but on the "new copy" change the symbol on the right of the head marker according to the transition table of the simulated TM and also change the head marker position one step left or right  (and at every "copy cycle" write also two "empty spaces" to allow the expansion of the tape); use internal states to keep track of the copy phase and of the current state of the simulated TM.

For example if you use # to mark the head position and one transition is:

q1, read a -> q2, write b, move left

a c # a a b c a b c _ a _
    ^RH               ^WH (q1 and c are buffered in the internal states)

a c # a a b c a b c _ a _
      ^RH               ^WH (here the "simulated" TM is on symbol "a"
in state q1 and we can apply the transition above)

a c # a a b c a b c _ a # c b _
        ^RH                   ^WH (q2 is buffered in the internal state)

continue with the copy and start another "cycle":

a c # a a b c a b c _ a # c b a b c a b c _
                    ^RH                   ^WH

... let me know if you need more hints.


Finding a (Small-Big-Medium) subsequence

Your algorithm is wrong in the detail of finding a local maximum after $m$ as pointed out in the comments.

Divide-and-conquer can be used to solve this problem. If such $i_1,i_2,i_3$ exist, there are four cases:

$i_1,i_2,i_3\le n/2$, or
$i_1,i_2\le n/2$ and $i_3>n/2$, or
$i_1\le n/2$ and $i_2,i_3>n/2$, or
$i_1,i_2,i_3> n/2$.

Cases 1 and 4 can be checked by solving the sub-problems on $(x_1,\ldots,x_{n/2})$ and $(x_{n/2+1},\ldots,x_n)$. For other cases, numbers less than $\min_{i\le n/2} x_i$ are useless, so we can filter them in $O(n)$ time first. In the following analysis, we assume all numbers are no less than $\min_{i\le n/2} x_i$.

For case 3, $i_1$ can be adjusted to $\arg\min_{i\le n/2} x_i$, then $i_2$ and $i_3$ exist if and only if $x_{n/2+1}<\cdots<x_{n/2}$ does not hold. Therefore we can also check this case in $O(n)$ time.

For case 2, since we have passed case 3, we can assume $x_{n/2+1}<\cdots<x_{n/2}$. Let $r_1=n/2$, and $r_{i+1}$ be the largest index smaller than $r_i$ such that $x_{r_{i+1}}>x_{r_i}$. Similarly let $l_1=1$, and $l_{i+1}$ be the smallest index larger than $l_i$ such that $x_{l_{i+1}}<x_{l_i}$. We mark each element with which sequence its index belongs to. This can be done in $O(n)$ time and space. Easy to see $i_1$ and $i_2$ can be adjusted to $l_s$ and $r_t$ respectively for some $s$ and $t$. Furthermore, we can adjust them such that no $l_j$ or $r_j$ lies between $l_s$ and $r_t$. So we can scan from $x_1$ to $x_{n/2}$ once to get all possible $(i_1,i_2)$ pairs in $O(n)$ time.

For example, suppose $(x_1,\ldots,x_{n/2})=(40,60,30,10,50,20)$, then
$\{r_i\}$: $6,5,2$, and $\{l_i\}$: $1,3,4$. We mark these elements as $40_l,60_r,30_l,10_l,50_r,20_r$. Possible $(i_1,i_2)$ pairs are $(40,60)$ and $(10,50)$.

Every possible $(i_1,i_2)$ pair is an open interval. We need to determine whether any of $x_{n/2+1},\ldots,x_n$ falls into these intervals. Note $x_{n/2+1},\ldots,x_n$ are sorted and so are these intervals, we can determine it in $O(n)$ time.

Now checking for case 2 and 3 costs $O(n)$ time and space, so this algorithm costs $O(n\log n)$ time and space in total.


Is it possible to turn an eulerian NFA into a linear size DFA?

I don't think so.

Suppose you could. Then you can also do this:

Take any NFA $\mathcal A$ with alphabet $\Sigma$, states $Q$, transitions $\Delta$, initial states $I$ and final / acception states $F$.
Add transitions to make the graph eulerian in the following way. Take any enumeration of the transition $p_i\overset{a_i}{\to}q_i$. For each $i$, add a transition $q_i\overset{b_i}{\to}p_{i+1}$ where $b_i$ is a new letter (and the indices are modulo the number of transitions). Note that you add $|\Delta|$ letters and transitions so this transformation is linear.
Add transitions to make the graph strongly connected in the following way. Take any enumeration of the states $s_j$. Add a new letter $c$. For each $j$, add a transition $s_i\overset{c}{\to}s_{i+1}$. In other words, add a Hamiltonian cycle using only the new letter $c$. Note that this transformation adds $1$ letter and $|Q|$ transitions so it's linear.
Use your magic procedure to build a new deterministic automaton $\mathcal B'$ so that it recognizes the same language as $\mathcal A'$ (the modified automaton) and $|\mathcal B'|=O(|\mathcal A|)$.
Remove added letters ($b_i$ for each $i$ and $c$) and all transitions using them. Call the new automaton $\mathcal B$.

Since $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^* $ (because if you don't use the new letters, then you're taking a path that already existed), and similarly $\mathcal L (\mathcal B) = \mathcal L (\mathcal B')\cap \Sigma^* $, we have $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^*=\mathcal L (\mathcal B')\cap \Sigma^*=\mathcal L (\mathcal B)$ with $\mathcal B$ a DFA so that $|\mathcal B|=O(|\mathcal A|)$.

But this can not be because of the usual counterexample where the size of the corresponding DFA is of exponential size. To get an explicit counterexample, you can apply the procedure to that counterexample.


There is no efficient algorithm to do what you want, unless P=NP.
In fact, there is no efficient algorithm do even decide whether a feasible partition of the dataset into two groups exists.
You can see this by reducing from the partition problem:
Given a (multi-)set of positive numbers $X=\{x_1, x_2, \dots, x_n\}$ we want to decide whether there exists a subsets $S$ of $X$ such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$. Without loss of generality we can assume that $0 < x_i \le 1$ (by simply dividing all $x_i$ by $\max_{i=1, \dots, n} x_i$).
Then, for each $x_i \in X$ you can create a row in your dataset with:

ID = $i$;
Score = $0$;
P1 = $x_i$;
Flag = false.

Finally, pick $n = m = \frac{1}{2}\sum_{x \in X} x$.
A feasible parition into two groups $A$ a and $B$ induces a subset $S$  such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$.
Specifically if $i_1, i_2, \dots, i_k$ are the IDs of the rows selected into $A$, you can define $S = \{x_{i_1}, x_{i_2},  \dots, x_{i_k}\}$.
Conversely, given a set $S = \{x_{i_1}, x_{i_2},  \dots, x_{i_k}\}$ such that $\sum_{s \in S}  s= \frac{1}{2} \sum_{x \in X} x$, you can select $A$ as the set of rows with IDs in $\{i_1, i_2, \dots, i_k\}$ and $B$ as the set of rows not in $A$.


Determine whether given f is shortest path function

Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function.

You need to strengthen your second condition.


Induction on typing derivation in refinement types system

It's a form of structural induction.

As we see on page 12 of the text, the typing relation is defined inductively by four rules.

For example, the rule abs says that given a deduction $\Gamma, x:r \vdash t : S$ we can form the new deduction $\Gamma \vdash \lambda x.t : R \to S$.

Compare with how, given a natural number $n$ you can form a new natural number $n+1$.

To prove a proposition $P(n)$ about an arbitrary natural number by induction you note that $n$ is either

$0$, or
$m+1$ for some $m$

In the first case, you prove $P(0)$ directly. In the second, you assume you have a proof of $P(m)$ and use this to prove $P(m+1)$.

Similarly, to prove a proposition about an arbitrary derivation $\Delta$ of the type judgement $\Pi \vdash t :R$ you note that $\Delta$ is either

$ \dfrac{}{\Pi \vdash x : R}\textsf{ var}$ and $t=x$ a variable
$\dfrac{\Pi \vdash s : S \to R, \Pi \vdash u : S }{\Pi \vdash s(u) : R}\textsf{ app}$ and $t=s(u)$, an application, for some derivations $\Delta_1, \Delta_2$ of the type judgements $\Pi \vdash s : S \to R, \Pi \vdash u : S $
$\dfrac{\Pi, x:r \vdash s : S}{\Pi \vdash \lambda x.s : R \to S}\textsf{ abs}$ and $t=\lambda x.s$, an abstraction, for some derivation $\Delta_1$ of the type judgement $\Pi \vdash s : S$
$\dfrac{\Pi \vdash t:S, R \leq R}{\Pi \vdash t : R}\textsf{ sub}$, for some supertype $S$ of $R$ and a derivation $\Delta_1$ of $\Pi \vdash t : S$

In the first case, you prove $P(\Delta)$ directly, and in the other three you assume $P(\Delta_1)$ and $P(\Delta_2)$ and then prove $P(\Delta)$.

There is an example in the proof of lemma 2.3.10 of the text, page 33.


The Eclipse Builder infrastructure actually does this, I believe. You might find this link useful.


How to Formally define $\delta$ in a DFA?

You're over-thinking this.

You need to define the value of $\delta(q,\sigma)$ for every $q\in Q$ and $\sigma\in\Sigma$ and, ideally, make it clear that you have done so. What format you use is a matter of your and your instructor's personal preferences.


How to find degree of polynomial represented as a circuit?

If the coefficients are small, then for large $x$ the polynomial is roughly equal to $Cx^d$. If you plug in both $x$ and, say, $2x$, then the ratio should be roughly $2^d$. Given bounds on the coefficients and the degree, this method can be made rigorous.

Another idea uses difference sequences. For a polynomial $P(x) $, the polynomial $P(x+1) - P(x)$ has degree smaller by one,  the polynomial $P(x+2)-2P(x+1)+P(x) $ has degree smaller by two, and so on (in general, the coefficients are binomial coefficients with alternating signs). Using polynomial identity testing you can find the degree by binary search. This seems less efficient than your approach.


Reducing from Hamiltonian Cycle to Subgraph Isomorphism

In $\mathrm{Subgraph\,\,Isomorphism}$, you're given two graphs $G$ and $H$, and the question is whether you can delete some vertices and edges from $G$ to get $H$ (i.e. $H$ is a subgraph of $G$). The reduction from $\mathrm{Hamiltonian\,\,Cycle}$ to $\mathrm{Subgraph\,\,Isomorphism}$ is really just rephrasing what it means for a graph to have a Hamiltonian cycle.

A Hamiltonian cycle in a graph is a cycle that includes every vertex, so if we ignore the other edges in the graph, we can think of the Hamiltonian cycle as a subgraph of the original graph with the properties that it contains all the vertices, only some of the edges, and those edges make a cycle. That is, a Hamiltonian cycle in an $n$-vertex is isomorphic to the graph $C_{n}$.

So if we start with $G$ and we can find a subgraph that's isomorphic to $C_{|V(G)|}$, $G$ must be Hamiltonian. This is the same as solving the $\mathrm{Subgraph\,\,Isomorphism}$ problem where $H=C_{|V(G)|}$.


Push down automaton for Language of same number of as and bs

The usual approach is to prove by induction the following kind of statement:

  The set of configurations reachable from the initial state upon reading a word $w$ is ...

Here ... depends on $w$. Having proved this kind of statement, you can deduce which words are accepted by your machine, hence proving its correctness.


Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using adjacency lists.

Let the purported vertex cover be $S$, of size $k$. Start by counting all edges in $G$, stopping once you reach $kn$. If there are more than $kn$ edges, then $S$ is not a vertex cover, and we can stop. In time $O(|E|) = O(kn)$, you can count (1) $\sum_{i \in S} \deg(i)$ and (2) the number of edges connecting vertices in $S$. The total number of edges covered by $S$ is the difference between these two numbers, which you can compare to $|E|$.


Depth-2 circuits with OR and MOD gates are not universal?

The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.


Do a pair of parallel edges form a cycle in a graph

Graph theory is notorious for having nonequivalent definitions of the same term being used by different authors in different places, so it is important to check the definition of the terms in your case. If you use the definition I'm familiar with
\begin{align*} &\text{A }\textit{cycle }\mathcal{C}\text{ is an alternating sequence of vertices and edges, beginning with a vertex }v_0\\ &\text{ such that no vertices or edges repeat except that }v_0\text{is both the first and last element}\\ &\text{of the sequence} \end{align*}
In that case if $G=(V,E,f)$, $v_1,v_2\in V$, $e_1,e_2\in E$ and $f(e_1) = f(e_2) = \{v_1,v_2\}$ then $v_1e_1v_2e_2v_1$ is a cycle in $G$.


Complexity of Monotone (+,2) SAT problem?

This is NP-complete.  In fact, it remains NP-complete when $F^+$ is restricted to be in 3-CNF form (not just CNF).

The proof is by demonstrating that this problem is at least as hard as testing 3-colorability of a graph.  The correspondence is clean and elegant.  Let $G=(V,E)$ be an undirected graph.  Introduce variables $x_{v,c}$, for $v \in V$ and $c \in \{1,2,3\}$, to represent a 3-coloring of the graph.  Here $x_{v,c}$ means that we've given vertex $v$ the color $c$.

To represent that each vertex must receive at least one color, we will introduce clauses $x_{v,1} \lor x_{v,2} \lor x_{v,3}$ for each vertex $v$.  This gives us $F^+$, i.e.,

$$F^+ \equiv \bigwedge_{v \in V} (x_{v,1} \lor x_{v,2} \lor x_{v,3}).$$

To represent that no two endpoints of a single edge may receive the same color, we will introduce a clause $\neg x_{u,c} \lor \neg x_{v,c}$ for each edge $(u,v) \in E$.  And, to represent that no vertex may receive more than one color, we will introduce a clause $\neg x_{v,c} \lor \neg x_{v,c'}$ for each $c,c' \in \{1,2,3\}$ such that $c\ne c'.$  Let $F^-_2$ denote the corresponding formula.

$$F^-_2 \equiv \bigwedge_{(u,v) \in E} (\neg x_{u,c} \lor \neg x_{v,c}) \; \;  \land \bigwedge_{v \in V,c\ne c'} (\neg x_{v,c} \lor \neg x_{v,c'}).$$

Then it is easy to see that $F^+ \land F^-_2$ is satisfiable if and only if $G$ has a 3-coloring.  In fact, each satisfying assignment of $F^+ \land F^-_2$ corresponds immediately to a 3-coloring of $G$, and vice versa.  Therefore, testing the satisfiability of this class of formulae is at least as hard as testing 3-colorability of an undirected graph, so it is NP-hard.


Selective Background Updating in Running Gaussian Average Method for Background Subtraction

1) You start with first frame of video. Gather several frames to calculate accumulators, denote everything like background - at first frame you do not know which is which. Yes, recalculate.

2) Yes we shall update variance.

Never used unmodifief version: remember to use illumination infependent color space. Think about taking running variance on your own.


Algorithm for automatic construction of natural deduction proofs

Usually we require the theorems of a proof system to be recursively enumerable, so you can at least write an algorithm that will eventually produce a proof of any theorem. This is usually a relatively easy algorithm to implement. Of course, if you give it something that is a non-theorem, you won't be able to tell with this approach.

For classical propositional logic, we could, of course, use truth tables to check whether something is a tautology first, and then do this search for a proof. This would give a computable (i.e. recursive) algorithm. It would be more direct and efficient to use a constructive proof of completeness for classical propositional logic though. There are certainly even more direct and efficient ways to search for a classical propositional logic proof.

For intuitionistic propositional logic, there is the proof system LJT described in Contraction-free sequent calculi for intuitionistic logic and implemented in tools like Djinn.

Theoremhood for a first-order theory in (classical or intuitionistic) first-order logic is generally not computable. Some particular first-order theories are decidable, but most aren't. They are at least semi-decidable via the argument in the first paragraph. There are, of course, tons of automated theorem provers that will attempt to find proofs, but they may fail. For theorems, they may fail due to resource limitations1. For non-theorems, they just don't have a way of showing that something is contingent. They could find a proof for the negation of your formula, but that technically doesn't rule out your formula being a theorem since your theory could be inconsistent. Model checking techniques could be used to attempt to find counter-models to show that some formula can't be a theorem (but may still be contingent). Most model checking tools are not aimed at full first-order logic though. They have essentially the same theoretical and practical limitations as automated theorem provers.

1 Just because something is computable doesn't mean it's computable within our universe.


If a person owns property in the town, then when voted out, they presumably forfeit the property.  This creates an economic incentive to systematically rob minority groups via things like the Spanish Edict of Expulsion which expelled the community of Jews that had thrived prior to the Reconquista from Spain.  Although the decree technically allowed them to sell their possessions (at firesale prices) before fleeing, they were not allowed to take the proceeds with them:

  And we likewise give license and faculty to those said Jews and Jewesses that they be able to export their goods and estates out of these our said kingdoms and lordships by sea or land as long as they do not export gold or silver or coined money or other things prohibited by the laws of our kingdoms, excepting merchandise and things that are not prohibited.

Such incentives might be sufficient for cartels to arise.  A cartel that can corner the market on readily available portable wealth can combine that control with bloc voting to vote out an identifiable minority group in such a way that they have little option but to liquidate assets through the cartel making the cartel members wealthy.

Any analysis should take into account such incentives.  Game theory, since it does not by itself model irrational tendencies like in-group/out-group bias, might have a hard time predicting such things.


Dijkstra's algorithm runtime for dense graphs

The runtime of Dijkstra's algorithm (with Fibonacci Heaps) is $O(|E|+|V|\log|V|)$, which is different from what you were posting.

If $|E|\in \Theta(|V|^2)$, that is your graph is very dense, then this gives you runtime of $O(|V|^2+|V|\log|V|)=O(|V|^2)$. A better runtime would be "surprising", since you have to look at every edge at least once.

When using binary heaps, you get a runtime of $O((|E|+|V|)\log|V|)$ which for $|E|\in \Theta(|V|^2)$ gives $O(|V|^2\log |V|)$.


Is this a standard representation of a 'space' character?

The symbol ␢ has a unicode representation: 2422-unicode-blank-symbol.

It is an old typographic symbol for specifying explicit blanks in code.
As Wikipedia states:

  This was used in the early years of computer programming when writing
  on coding forms. Keypunch operators immediately recognized the symbol
  as an 'explicit space'.

ps. I also learned this symbol as Turing tape blank. I will check an old book later. Nowadays I would use B or if I am feeling adventurous ␣ 'open box' (U+2423) $\text{\textvisiblespace}$.


Well, there is a lot of bibliography on whether one algorithm is better than the other. In particular, the main insight is: "in the presence of duplicates (e.g. grids), A$^*$ should be preferred, whereas in other cases IDA$^*$ should be in general preferred". For example, heuristic planners usually prefer best-first search strategies such as A$^*$ instead of IDA$^*$ (just because duplicates occur in many domains). For example, to solve the $N$-Puzzle, the $N$-Pancake, or the TopSpin, IDA$^*$ is the current algorithm of choice. For other cases, such as Rubik's Cube or Towers of Hanoi, IDA$^*$ is still the algorithm of choice but be careful and try to implement a good strategy for handling symmetries. In the case of grids, A$^*$ is the right choice.

There is a wonderful paper about how to implement A$^*$ and makes a lot of considerations that, I think, fit your question: Ethan Andrew Burns, Matthew Hatem, Michael J. Leighton, Wheeler Ruml. Implementing Fast Heuristic Search Code

Let me know, please, whether this helps or not,


How does random number probabilities work in distributed systems?

Yes - this is a consequence of the Law of Large Numbers.  https://en.wikipedia.org/wiki/Law_of_large_numbers
Yes - it still holds for pseudorandom number generators if they are any good.
Seed each PRNG independently.


Convert conjunctive normal form to equivalent boolean formula with only NAND gates

Yes, it can be converted to such a formula of size $O(n)$ (i.e., only a constant-factor increase in formula size).  The conversion simply recursively applies the following rules:

$$\begin{align*}
\neg a &\equiv NAND(a,\text{True})\\
a \lor b &\equiv NAND(\neg a, \neg b)\\
a \land b &\equiv \neg NAND(a,b)
\end{align*}$$

It is easy to check that the resulting formula has linear size.

For instance, the clause $x_1 \lor \neg x_2 \lor \neg x_3$ represents $(x_1 \lor \neg x_2) \lor \neg x_3$, so applying the above rules we obtain the boolean formula

$$NAND(NAND(NAND(NAND(x_1,\text{True}),x_2),\text{True}),x_3).$$

In this way, each clause can be converted to a boolean formula of size $O(1)$.  All that remains is to convert the conjunction of these clauses, and that can be done by expressing $c_1 \land \cdots \land c_m$ as $((c_1 \land c_2) \land \cdots) \land c_m$ and then applying the rule for $a \land b$ repeatedly.


Monitoring files in preservation archives

This is not an answer to the question per se, but an extended comment.

There was an interesting set of slides regarding CERN's Advanced Storage (CASTOR) at CHEP'2010. This is a large mixed media archive with some 25 PB of tape archives (ca. 2010). One of the presentations: "Tape archive challenges" highlights some of the issues that seem to question the assumptions set in the OP.

  Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers.

Not quite. Even if you have a controlled environment in the tape storage you should expect a very small percentage of the tapes to fail. Therefore it makes sense to keep repacking the data constantly. Also older tape drives may fail making the data on old tapes inaccessible.

The latter reason makes archivists keep copying tapes at a much higher rate than their physical life span would suggest. Marty Perlmutter, "The Lost Picture Show: Hollywood Archivists Can't Outpace Obsolescence".

  Disks are most at risk when the read/write head is flying close to the medium.

When the disk is spinning it constantly monitors itself for errors due to wear and errors due to defects in the manufacturing process. While rotation increases the probability of an error it also through predictive failure analysis reduces the chance of an error to occur undetected. On the contrary, as a mechanical unit a disk that was stored on a shelf might just fail to spin up.

A probabilistic approach to consistency checking has to be aligned with the statistical thresholds set for different actions. Suppose that a probabilistic model says that with probability 50% there is one error for a 1000 cartridges in a tape library. Does it give any hint on the possible action but to check consistency for the complete archive in order to find the possibly damaged part so that it can be rebuilt.

Many papers with statistical models of reliability of computer systems based on queuing theory have this problem. While they provide formulas to quickly estimate parameters of computer systems they often rely on some generic assumptions that may or may not apply in a particular setting.


Is the calculation of infinite sums solvable by a computer?

It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.


What is a "name/variable of base type" in applied $\pi$-calculus?

“Base type” is a type that isn't built from other types. Types built from other types include data structures (e.g. lists, arrays, pairs, …), functions, etc. In the context of the pi-calculus, base types exclude channel types.

Some typical example of base types in practice are integers, booleans, floating point, etc. From a theoretical point of view, a base type is one that is a base case in the type grammar, and more generally this implies that there's no type equation that relates this type with “interesting” constructed types. For example, a value of a base type is not a channel or anything that contains a channel.

“$n$ is name of base type” here means that $n$ is a channel that transports opaque values, as opposed to a channel that can transport a channel name. So $(\nu n.P)^{ch} \equiv \nu n.\mathsf{out}(ch, n).P^{ch}$ holds only when the output operation isn't extruding any of the channels in $P$.


Finding cache block transfer time in a 3 level memory system

I guess you got the access time wrong. Access time means time to locate a data on a memory. So, whoever accesses the memory (be it CPU or some other device) it will be the same.

Coming to first question here. A block is transferred from L2 to L1. And L1 block size being 4 words and data bandwidth being 4 bytes, it requires 1 L2 access (for read) and 1 L1 access (for store). So, time = 20+2 = 22 ns.

For the second question, L2 block size being 16 words and bandwidth between memory and L2 being 4 words, we require 4 memory access (for read) and 4 L2 access (for store). Now, we need to send the requested block to L1 which would require 1 more L2 access (for read) and 1 L1 access (for store). So, total time

= 4 * (200 + 20) +  (20 + 2)

= 880 + 22

= 902 ns


How much can matrix multiplication algorithm be parallelized?

Ypu're starting from a completely wrong point.

The execution time of matrix multiplication does not come from the number of multiplications and additions, it's the number of uncached memory accesses that kill you. Reading a number that's not in any processor cache takes about 100 times longer than a multiplication.

So the first step is rearranging the order of operations to perform as many operations as possible using only data that is present in the fastest processor cache. That's your first step before you even think about doing things in parallel.

The next step is adding multiple sums in parallel, still in one thread. Instead of summing up C[i,j] for example you add six sums C[i, j], C[i,j+1], C[i, j+2], C[i+1, j], C[i+1,j+1], C[i+1, j+2] in parallel. This means you are limited by the throughput of operations, not the latency.

The next step is using SIMD instructions. Your processor quite likely has instructions that perform 2, 4 or 8 floating-point operations just as fast as a single floating-point operation.

Once you have done all this, especially the first part where the work is divided up into "blocks", you can easily process multiple blocks on multiple threads. What you need to be careful about is that you have enough cache memory to do so.


Uncertainty of coroutines writing to single socket

I ended up using a buffer limit and a queue.
I knew that this may not answer this question fully but it's the only optimal solution I could find.


Proving inequalities related to Dijkstra's algorithm

Consider a shortest path from $s$ to $v$. Let $u \in \mathrm{IN}(v)$ be the vertex preceding $u$ in this shortest path. The path from $s$ to $u$ is also a shortest path, and so $\mathit{spdist}(s,v) = \mathit{spdist}(s,u) + w(u,v)$.


Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

Sems to be a decent approach.

The trick you need is to leave the last B  marked, say you generate bbX rather than bbb. Now the final X can absorb the C's using the production CX -> aX.

In the end you are left with the final X which can change into b again.

Of course the final production X -> b might be applied too soon, when there are still C's around. This is harmless. Now the C's cannot disappear and the derivation will not succesfully end.

In ordinary context-sensitive grammars one is usually not very interested in unsuccesful derivations, but it might be hard to consider all cases when writing formal proofs. It is some times possible to write more deterministic grammars by simulating linear bounded automata. In state p read a then write b move left to state q one would have the rewrite rule xpa -> qxb (for every letter x). Then the only problem is to make the final state disappear.


You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.


Secondary Storage in Von Neumann Achitecture

The von Neumann architecture concerns only memory and CPU, not peripherals or devices.  Storage, such as a hard disk or SSD, is typically a device, and thus is outside the scope of what's normally shown in the von Neumann architecture.  Thus, in a picture of the von Neumann architecture, the block labelled "memory" should be understood to refer to RAM -- not hard disk or SSD.

In particular, in the von Neumann architecture, the CPU can access memory through a bus (the memory bus).  In real computers, typically the memory bus cannot be used to read or write the hard drive; there's a separate path for accessing devices like the hard drive.  (That's from the perspective of the architecture/hardware level.  However, the lines can admittedly start to get blurred a bit from the user application's perspective, given memory-mapped devices, virtual memory, and demand paging.)


Algorithm to find the size of a quotient of a free group

I think you're asking: given a group presentation $\langle X | R \rangle$, determine the size of the group.

Unfortunately, it is undecidable to determine whether the group is finite or infinite.  See the Adian-Rabin theorem.

For some additional references, see also https://math.stackexchange.com/a/606/14578, https://math.stackexchange.com/q/3106606/14578, https://math.stackexchange.com/q/2756802/14578, https://math.stackexchange.com/q/1516849/14578, or the following lecture notes: Presentation of Groups.  Derek Holt.


Generating values from a probability density function

You can integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled from using a suitably constructed Markov chain.

See also this set of slides for more details.


Programming Symbols : Instance/Instantiation

In most contexts, objects are values and classes are types, so I would simply use the colon, representing the "has type" relation:

$Object : Class$

That said, this depends on your context, and whether $:$ carries some other meaning. You could also use $\in$, since you can identify a class with the set of objects that are instances of that class.


Generate scale-free networks with power-law degree distributions using Barabasi-Albert

The short answer is that you can't use that software as-is to get what you want. For a fixed $m$, the Barabasi-Albert model always has the degree distribution $P_k \sim k^{-3}$, regardless of $m$. The exact formula for the probability degree of what those pieces of software implement (which is the BA model) is

$$ P_k = \frac{2m(m+1)}{k(k+1)(k+2)}$$

The papers (with $\lambda \neq 3$) are probably talking about some kind of generalized BA model, I presume. It would help to give more details (full citations) on them.

EDIT: OK, I'll have at look at those refs. In the meantime, I've discovered there's R package called igraph that can do what you want. The relevant theory paper/cited used there is:

"Connected Components in Random Graphs with Given Expected Degree Sequences" by Fan Chung, Linyuan Lu.

It has some 400 citations in Google Scholar, so it's probably a widely used method. The later, 2009 paper cited on that R package page clearly says "SF networks contain heterogeneous degrees, and their distribution follows a power law, $P_d(k) \sim k^{-\lambda}$. To construct artificial SF networks, a stochastic model called the Chung and Lu (CL) model is used."

EDIT2: I think you have misread Huang et al. "We build synthetic random, scale-free and small-world networks using Erdos-Renyi model, Barabasi-Albert model and Watts and Strogatz model [9] respectively." It doesn't say anywhere they got BA to do any power other than 3. There's a figure caption which says "We use ‘k-n’ interdependence model to couple two synthetic scale-free networks $G_p$ and $G_c$ with the power law exponents 2.5 and 3 respectively." But that doesn't mean they used BA for those 2.5-degree graphs. There's one later figure which only says "Barabasi-Albert model is used to generate scale-free network with power law exponent 3."

EDIT3: The paper by Buldyrev et al. doesn't say anywhere they've used any BA graphs. "Simulation results for P8 as a function of p for for SF networks with $\lambda$ = 3, 2.7, 2.3". They don't say how they got those graphs. The do cite the BA papers, but only in long list of 10 papers about various random network models. The second paper of this group by Havlin et al. does indeed give on p. 5 the BA model as having an indeterminate/unspecified $\lambda$, citing the 1999 BA paper. I don't really want to call this paper wrong, but the only correct reading of it is $\lambda = 3$. Again it doesn't say how they generated their $\lambda = 2.7$ graphs from their Fig 8. I can see how reading this paper you can conclude that BA can generate such graphs... but it can't.

EDIT4: Yes, I found it now in the actual version published in Nature "For two interdependent scale-free networks2 with power-law degree distributions, $P_A(k) \sim P_B(k) / k^{-\lambda}$, we find that the existence criteria for the giant component are quite different from those in a single network." The citation is indeed misleading in the same way as in the Halvin et al., but they don't say they've used the BA process to generate the graphs. The passage can be interpreted as only a citing BA 1999 reference for what scale-free network means and/or who originated the concept. In any case, trust the math... you can find the derivation for the BA degree formula in numerous places, including BA's own paper or in more detail in a later book[let]. BA obviously understood the generality of what they observed, so they stated a law that is more general (arbitrary $\lambda$) than what their construction provides, i.e. $\lambda = 3$. As I said before, there are other methods (subsequently published by others, e.g. Chung and Lu) to get a different $\lambda$, but they are not using the BA construction, even though their graphs are correctly called scale-free too.


The solution in the question is correct.

The constraint $i\ne j$ is the one that gives us trouble. To get around it  we have to split into two cases: (i) $i<j$, and (ii) $i>j$ (but still $i<2j$)

thus
$S\to S_{(i)} \mid S_{(ii)}$
as the first production splits into this two cases.

Now, divide and conquer:  case (i) is very simple, since we only need $i<j$,
$S_{(i)} \to aS_{(i)}b \mid B$
$ B \to Bb \mid b$

This is your $S_2$.

For case (ii), we need to $j< i < 2j$, so for every single $a$, the variable $C$ will generate exactly one $b$, and at a certain point we switch to the variable $D$ that will generate two $a$'s for each $b$.
$S_{(ii)} \to aCb $
$ C \to aCb \mid D$
$ D \to aaDb \mid aab$

This is your $S_1$.


Yes.

Sándor Horváth, J. Karhumäki and H. C. M. Kleijn characterized the context-free languages consisting only of palindromes in their paper Results Concerning Palindromicity, 1987.

Theorem. A context-free language $L\subseteq\Sigma^*$ is palindromic, iff it is of the form
$$ L= \bigcup_{x\in\,\Sigma\cup\{\lambda\}}\{uxu^R : u\in L(x)\}$$

where the $L(x)$ is a regular language uniquely determined by $L$ for all $x \in\Sigma\cup\{\lambda\}$.

In particular, the theorem tells that a context-free languages that consists of only palindromes of even length must be of the form $\{uu^R : u\in L\}$ for some regular language $L$.


I can not help but think: this is divide & conquer, plain and simple!

M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input.  It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations.  Different stages can perform different operations.

  So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

MapReduce does not break new ground in the theory of computation -- it does not show a new way of decomposing a problem into simpler operations.  It does show that particular simpler operations are practical for a particular class of problem.

The MapReduce paper's contribution was

evaluating a pipeline of two well understood orthogonal operators that can be distributed efficiently and fault-tolerantly on a particular problem: creating a text index of large corpus
benchmarking map-reduce on that problem to show how much data is transferred between nodes and how latency differences in stages affect overall latency
showing how to make the system fault tolerant so machine failures during computation can be compensated for automatically
identifying specific useful implementation choices and optimizations

Some of the critiques fall into these classes:

"Map/reduce does not break new ground in theory of computation."  True.  The original paper's contribution was that these well-understood operators with a specific set of optimizations had been successfully used to solve real problems more easily and fault-tolerantly than one-off solutions.
"This distributed computation doesn't easily decompose into map & reduce operations".  Fair enough, but many do.
"A pipeline of n map/reduce stages require latency proportional to the number of reduce steps of the pipeline before any results are produced."  Probably true.  The reduce operator does have to receive all its input before it can produce a complete output.
"Map/reduce is overkill for this use-case."  Maybe.  When engineers find a shiny new hammer, they tend to go looking for anything that looks like a nail.  That doesn't mean that the hammer isn't a well-made tool for a certain niche.
"Map/reduce is a poor replacement for a relational DB."  True.  If a relational DB scales to your data-set then wonderful for you -- you have options.


How does these Probing time occurs for hash tables

To give you a test of the analysis, here it is for chaining.

When the load factor is $\alpha$, the length of the list at each cell is distributed $\mathrm{Bin}(N,1/M)$, and its expected value is $N/M = \alpha$. When the probe is not found, we have to go over the entire list, and thus we have something like $\alpha$ probes in expectation. When the probe is found, the length of the list is $\mathrm{Bin}(N,1/M)$ conditioned on being positive, which is somewhat larger than $\alpha$ (and can be calculated exactly). In this case, assuming that the probed element is chosen at random from the set of all elements, its position in the list is uniformly random, and so in expectation it is found at the middle of the list, and therefore we have something like $\alpha/2$ probes.

If we are more careful then we will probably get the formulas stated at the first row of the table, or at least something very close.

The other rows of the table result from similar analysis. Each case is different. If you want to know more, I suggest you look for other online or offline resources rather than probing us here.


Can all NP-complete cryptosystems be broken if one is broken?

As Yuval points out, contemporary crypto systems are not based on
NP-complete problems.

NP-hardness is a worst-case notion of hardness. A problem
might be NP-hard but easy to solve in many cases, or on average,
or even in most cases. A crypto systems that was easy to crack on
average would not be useful.  We want crypto systems that are
hard to crack in almost all cases (we cannot ask for all cases
because the adversary can -- in principle -- just guess the
secret used).

This seemingly stronger notion of hardness is formalised by  one-way functions.

Incidentally, the existence of one-way functions implies $P \neq NP$,
so you can imagine that we don't know if they exist.  The reverse
implication (does $P \neq NP$ imply the existence of one-way
functions) is also an open problem.

There is an interesting theory of physical unclonable function which can be
seen as the physical analogue of a one-way function.


Union of every language within group of decidable languages is also decidable?

You don't define $H_0$. Presumably it's an undecidable set.
First, $f : \mathbb{N} \to H_0$ only means that all the values of $f(x)$ are in $H_0$, i.e. the image of $f$ is a subset of $H_0$: $f(\mathbb{N}) \subseteq H_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H_0$, that is, $f(\mathbb{N}) = H_0$.
Second, the image of a recursive set by a recursive function is not necessarily recursive. It's obviously recursively enumerable, by definition of “recursively enumerable”: if $g$ is recursive, then it's partial recursive, and $g(\mathbb{N})$ is a recursively enumerable set. But $g(\mathbb{N})$ might not be recursive. For example, consider a function $g$ whose input is an encoding of a program (that doesn't take arguments) and an integer: $g(\langle P,n\rangle)$ which runs $P$ for $n$ steps and returns $\langle P\rangle$ if $P$ terminates in less than $n$ steps and $0$ otherwise. The function $g$ is recursive (its definition is an algorithm to run it), but its image is the set of encodings of terminating programs, which is not decidable. Coming back to our original problem, it's possible to have a recursive $f$ such that $f(\mathbb{N}) = H_0$ but $H_0$ is not recursive.
Third, $f$ might not be recursive anyway. (And if you apply the previous paragraph, you'll notice that it can't be recursive if $H_0$ is not recursively enumerable.) All you know is that there exists a function $f$ such that $f(\mathbb{N}) = H_0$. An example of how to define this function is: $f(x) = x$ if $x \in H_0$ and $f(x) = h_0$ if $x \notin H_0$, where $h_0$ is the smallest element of $H_0$. This is a perfectly good mathematical definition, but it isn't an algorithmic definition: since $H_0$ isn't decidable, there's no algorithm to choose between the case $x \in H_0$ and the case $x \notin H_0$.
Intuitively speaking, to decide whether $x \in \bigcup_{i\in\mathbb{N}} L_i$, you need to figure out which $i$ to check, then check whether $x \in L_i$. But there's no reason why there would be an algorithmic way to pick $i$. (And to make things worse, $x$ might be in multiple $L_i$, possibly infinitely many — but the proposed property is wrong even if the $L_i$ are disjoint, as seen with the example of singletons which can easily be renumbered to make them distinct and therefore disjoint.)


Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete

In fact, it does not prove NP-completeness (see a list of our related reference questions).

For the shortest path problem (SPP)  to be NP-complete, it is crucial you allow negative edge weights. Then, there is a simple polynomial-time reduction from the Hamiltonian path problem to SPP. In other words, you take an arbitrary instance $I$ of the Hamiltonian path problem, and construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. To make the reduction work, you only need to set up the edge weights in $I'$ suitably.


Computing the k shortest edge-disjoint paths on a weighted graph

A comment by D.W. makes a lot of sense (it would do in general but it does in this specific case since there are many different variants of the same problem). Hence, in my response I just refer to a few variants of the same problem (which contain descriptions of various algorithms):

Usually, the term $k$ shortest edge-disjoint paths is plainly interpreted as follows:

  Given a graph $G$ and $k$ pairs of distinct vertices $(s_i, t_i)$, $1 \leq i \leq k$, find whether there exist $k$ pairwise disjoint shortest paths $P_i$, between $s_i$ and $t_i$ for all $1 \leq i \leq k$.

And this is taken from the paper you pointed to: Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics. Volume 85, Issue 2, pp 113--138. 1998.

This problem is known to be NP-hard for arbitrary values of $k$ but the authors actually provide a polynomial algorithm for the case of $k=2$ with positive edge-costs.

In this variant, there is no interest in minimizing any particular metric. The best result, to the best of my knowledge, refers to Directed Acyclic Graphs (DAGs) and $k=2$:

Torsten Tholey. Linear time algorithms for two disjoint paths problems on directed acyclic graphs. Theoretical Computer Science, 465:35–48, 2012

However, the oldest formulation I know of this problem actually considers the minimization of a specific metric:

  Given a directed graph G containing $n$ vertices, one of which is a distinguished source $s$, and $m$ edges, each with a non-negative cost, find a pair of edge-disjoint paths from $s$ to $v$ of minimum total cost.

This problem is known to be a special case of minimum-cost network flow, and there is a brilliant, splendid, beautiful and amazing algorithm for solving it with $k=2$: Suurballe's algorithm.

Another variant that has received some attention imposes a limit on the number of edges (and these are known as Length Constraints):

  Given a graph $G$ compute a pair of disjoint paths between nodes $s$ and $t$ of an undirected graph, each having at most $K$ edges.

Again, this problem is known to be NP-complete: Spyros Tragoudas and Yaakov L.Varol. Graph-Theoretic Concepts in Computer Science, volume 1197 of Lecture Notes in Computer Science, chapter Computing disjoint paths with length constraints, pages 357–389. Springer Verlag Heidelberg, 1997.

Approximation algorithms have been developed also for this particular variant. See: Longkun Guo. Frontiers in Algorithmics, volume 8497 of Lecture Notes in Computer Science, chapter Improved LP-rounding Ap- proximations for the k-Disjoint Restricted Shortest Paths Problem, pages 94–104. Springer International Publishing, 2014.

In all these works (but the first two ones), the authors refer to shortest paths but watch out what D.W. is asking in his comment: this is not to find the minimum number $m$ of shortest paths from which a set of $k$ shortest paths could be extracted such that they do not share any edge. In general, the computation of these $k$ shortest paths refer to an additional metric. For example, Tragoudas and Varol consider the minimization of the maximum length and Guo introduces the minimization of an additional parameter, $delay$.

Summarizing, there are many variants of the same problem, Suurballe's minimizes the sum of the cost of the pair of paths, others consider the minimization of the longest path (Tragoudas and Varol), and this is known as a min-max version but also max-min versions exist and this is just in case a metric is used. If not, it depends whether you impose limits or not on the length of the paths and other cases. All of them, however, are known to be exponentially hard.

I would like to end just by pointing out that I am not aware of any generalization of A$^*$-like search algorithms that deal with this problem. I think that can be definitely an interesting line of research.

Hope this helps,


Feasibility of linear inequalities with binary variables

Use an off-the-shelf integer linear programming solver.  That's exactly what they are designed to do.  The problem is NP-hard in general, so there are no guarantees -- there are certainly some problems that no existing solver can solve in any reasonable amount of time -- but you might get lucky.

Checking whether a feasible solution exists is also NP-complete, and it is (asymptotically, in general) about as hard as finding a feasible solution if one exists.


executing threads with no synchronization

Hint: Let $C = B \pm A$ be the final instruction being executed. Clearly $A \in \{3,4\}$ and $B \in \{5,6\}$, and this shows that $C \in \{1,2,3,8,9,10\}$. For the other direction, show that by carefully scheduling both threads, you can choose which of $C = B \pm A$ is executed last, and choose the value that $A$ and $B$ get prior to that instruction being executed.


The general fitting formula for pretty much any function is $F(x)=a*x+b$

so if you have a function inside a function it would be $F(G(x))=a*G(c*x+d)+b$ by virtue of substitution.

You made a tiny error. Instead of $y=a+b \log(cx)$ you probably want $y=a+b \log(cx + d)$

try to fit your function again. a multiplier should never equal to zero, because that would imply you don't have a function of $x$.


Process Synchronization: Dekker's algorithm

When P1 runs again, it set its flag to True. Your scenario assumes P0 is executed continuously, while P1 never gets a chance to execute its code. This also happens in the simple case where there is only one process running, but obviously this does not contradict bounded waiting.

An implicit assumption when talking about protocols for mutual exclusion is that all of the processes involved will eventually run and execute their current command (otherwise it is meaningless to talk about properties such as bounded waiting or starvation freedom).


$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?

Lets assume towards contradiction that L is regular.
Then, by closure properties, we have $\bar L$ is regular, and thus also $\bar L \bigcap (a^*b^*c^*)$ is regular. But calculating it, we find out $\bar L \bigcap (a^*b^*c^*)=\{a^nb^nc^n\}$ is not regular.


First you need to understand the goals of Microsoft Research.

  Our labs are unique among corporate research facilities in that they
  balance an open academic model with an effective process for building
  research results into product development. This approach, unique among
  corporate research facilities, pays off for Microsoft as enhancements
  to virtually every product and service it offers and as entirely new
  lines of business for the company. At the same time, it produces
  significant technological and intellectual advances across the
  spectrum of computer science.

from: Inventing the Future of Computing

Second you need to see how these ideas are translated into current projects.

  Windows 7. The latest version of Microsoft’s flagship operating system
  incorporates a number of “under the hood” technologies from Microsoft
  Research that contribute to the product’s improved performance,
  reliability and usability. These include enhancements to handwriting
  recognition, graphics performance, networking and security.
  Additionally, the product development team made use of a number of
  Microsoft Research technologies to write and test code efficiently and
  more thoroughly identify potential security issues.

See: Bringing Innovations to Life and Making Computers More Capable and Useful

Lastly you need to understand that Singularity has been used as a springboard for other projects:

  Microsoft describes Singularity as a research project "which
  demonstrated that modern programming languages and software
  engineering techniques could fundamentally improve software
  architectures." Singularity ended up spawning and/or influencing a
  number of other operating system research projects at Microsoft,
  including Barrelfish, Helios, Midori (Wikipedia) and Drawbridge.

from The father of Microsoft's Singularity OS moves on


How to express modalities in lambda calculus - are some extensions required?

Are extensions required? Not really. You can take an axiomatic description of a modal logic and simply provide a "primitive" lambda term for each. The modal operators would become type constructors. Haskell's IO monad can be viewed this way. Coherence conditions like the monad laws would provide some conversions between terms.

A different approach, which does involve extending the lambda calculus, is described in Frank Pfenning's and Rowan Davies' A Judgmental Reconstruction of Modal Logic.  Note, this is for an intuitionistic modal logic. This involves changing the context, or specifically, having multiple contexts to include hypothetically valid propositions. You get rules like:$$
\frac{\Delta;\cdot\vdash M : A}{\Delta;\Gamma\vdash\mathsf{box}\ M:\square A}\qquad\frac{\Delta;\Gamma\vdash M:\square A\quad\Delta,u::A;\Gamma\vdash N:B}{\Delta;\Gamma\vdash\mathsf{let\ box}\ u=M\ \mathsf{in}\ N : B}$$
You should read the $\mathsf{let\ box}\ u = M\ \mathsf{in}\dots$ as pattern matching/a destructuring bind against $M$.

We have:$$
(\lambda m.\mathsf{let\ box}\ u= m\ \mathsf{in}\ u) : \square A \to A \\
(\lambda f.\lambda x.\mathsf{let\ box}\ f'=f\ \mathsf{in\ let\ box}\ x'=x\ \mathsf{in\ box}\ (f'x')) : \square(A\to B)\to\square A\to\square B \\
(\lambda m.\mathsf{let\ box}\ u=m\ \mathsf{in\ box}\ (\mathsf{box}\ u)) : \square A \to \square \square A$$
Handling possibility as opposed to or in addition to necessity requires a bit more cleverness.


How do I solve a search problem on an infinite graph?

I believe you can use any algorithm for heuristic search.  On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.


Name of a tree with arbitrary number of branches at each fork point?

Rooted Tree

  How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

That is none other than an rooted tree itself or, more accurately, an arborescence or branching tree or out-tree according to the following quote from Wikipedia entry on rooted tree.

  A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree.

Multitree

Your are also interested in what you might call "Poly-hierarchical rooted graph".

  An arbitrary rooted tree could also be a poly-hierarchy as far as I understand, with some nodes having an indegree > 1 i.e. multiple parents.

However, since every vertex other than the root has a single parent in a rooted tree by definition, it is not a viable idea to call them "Poly-hierarchical rooted tree". The conventional name for them is multitree as illustrated below, thanks to Wikipedia.

  A multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items $a$, $b$, $c$, and $d$ forming a diamond suborder with $a\le b \le d$ and $a\le c \le d$ but with $b$ and $c$ incomparable to each other (also called a diamond-free poset).

Polytree

You might be interested in polytree, as illustrated below, thanks to Wikipedia again. It is "also known as oriented tree or singly connected network". It is "a directed acyclic graph whose underlying undirected graph is a tree."

Hasse Diagram

Another related concept is Hasse diagram, which is "used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction", as illustrated below.

Exercise 1. Draw a polytree that is not a rooted tree. Draw a multitree that is not a polytree. Draw a Hasse diagram that is not a multitree.

Exercise 2. Every rooted tree is a polytree. Show that every polytree is a multitree. Show that every multitree is the Hasse diagram of some finite partially ordered set.


prove that in binary heap buildheap function does at most 2N-2 comparison

Floyd's method of constructing a heap consists of applying heapify on all non-leaf nodes. Running heapify on a node $v$ costs twice the height of the subtree rooted at $v$ (where the height of a leaf is 0), with only one exception: if the unique deepest path terminates at an only child, then the cost is twice the height minus 1.
Consider now a heap on $n$ elements, and suppose that $2^h \leq n < 2^{h+1}$. Let us first compute the total number of comparison when ignoring the very last level. In other words, we are considering the case of a complete binary tree with $h$ levels, containing $2^h-1$ nodes in total. The total sum of heights is
$$
(h-1)2^0 + (h-2)2^1 + (h-3)2^2 + \cdots + 1\cdot 2^{h-2} + 0\cdot 2^{h-1} = \\
(2^0 + 2^1 + \cdots + 2^{h-2}) + (2^0 + \cdots + 2^{h-3}) + \cdots + (2^0) = \\
(2^{h-1} - 1) + (2^{h-2} - 1) + \cdots + (2^1 - 1) = \\
2^h - h - 1.
$$
The total number of comparisons is twice that.
The actual heap contains $m = n - 2^h + 1$ nodes at level $h+1$. These increase the sum of heights by 1 for each node which contains one of these $m$ nodes as a descendant. At depth $d$ (where the root is depth zero), there are $\lceil m/2^{h-d} \rceil$ such nodes. This shows that if $n$ is odd, the number of comparisons is exactly
$$
2(2^h-h-1) + 2\sum_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil.
$$
If $n$ is even, then there are some nodes in which the unique deepest path terminates at an only child. To determine how many, let us denote by $x$ the odd leaf. The node $x$ is always the unique child of its parent. Going one level up, $x$ is the unique node at depth 2 iff $n$ is divisible by 4. Continuing in this way, it is not hard to check that if $2^r$ is the largest power of 2 dividing $n$, then the number of such nodes is $r$, and so we have to subtract $r$ from the above formula:
$$
2(2^h-h-1) + 2\sum_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil - r.
$$
We can simplify this formula using $2^h/2^{h-d} = 2^d$, to get
$$
2\sum_{d=0}^{h-1} \left\lceil \frac{n+1}{2^{h-d}} \right\rceil - 2h - r.
$$
Replacing the ceiling with a floor and changing the order of summation, this simplifies to
$$
2\sum_{d=1}^h \left\lfloor \frac{n}{2^d} \right\rfloor - r.
$$
This is always at most
$$
2\sum_{d=1}^h \frac{n}{2^d} < 2n,
$$
and so at most $2n-1$. In fact, the same argument shows that the sum itself is less than $n$, and so at most $n-1$, hence the number of comparisons is at most $2n-2$.
We can also get a more explicit expression for this quantity. Let the binary expansion of $n$ be $b_h b_{h-1} \ldots b_0$, where $b_h = 1$. The sum equals
$$
(b_h \ldots b_1)_2 + (b_h \ldots b_2)_2 + \ldots + (b_h)_2 = \\
b_h (2^{h-1} + \cdots + 1) + b_{h-1} (2^{h-2} + \cdots + 1) + b^0 (0) = \\
b_h (2^h - 1) + b_{h-1} (2^{h-1} - 1) + \cdots + b_0 (1 - 1) = \\
n - (b_h + \cdots + b_0).
$$
Thus, if we denote by $\sigma$ the sum of all digits in the binary representation of $n$, then we get
$$
2n - 2\sigma - r,
$$
a formula also appearing on Wikipedia.
Since $\sigma \geq 1$, this is always at most $2n - 2$.


Does every r.e. set containing the set of total recursive functions contain all partial recursive functions?

Take $A = \{i\ |\ \phi_i(0) \downarrow \}$. It is obviously r.e., and includes $\mathrm{Tot}$.

Yet, it does not contain any index of, say, the always-undefined function $u$. Nor indices for any recursive partial function which is undefined at $0$.

The Kleene set also works: $K = \{i\ |\ \phi_i(i) \downarrow \} \supset \mathrm{Tot}$, yet it does not contain any index for $u$. (And it is r.e.)


Sequential numbers to unique-looking numbers

Not sure what you mean by "totally obvious". Technically, every permutation of $\{1,\dots,10^8\}$ would work here.
You can randomly generate such a permutation, store it in an array, and use this array as an index.
If you want a specific example, which may look at first glance non-sequential, take some big number $p$ such that $\gcd(p,10^8)=1$ (e.g. $p= 19683$), then the id of user $i$ will be $i \cdot p \pmod{10^8}$. This is guaranteed to be unique for each user (up to $10^8$ users).
It may look random only at a glance, but anyone who takes enough time can figure out this is not random.


When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA?

It's not clear to me how to interpret "can be considered", so I'm going to identify one technical question that can be answered.
Given a FSM $F$ and an input sequence $S$, it is possible to build another FSM $F'$ so that the execution of $F'$ on the empty input is in one-to-one correspondence with the execution of $F$ on $S$ (and in particular, both end at the same end state(s); e.g., either $F$ accepts on $S$ and $F'$ accepts on the empty input; or $F$ rejects on $S$ and $F'$ rejects on the empty input).
The proof is a straightforward application of the product construction: we construct one FSM $F_0$ that outputs the fixed sequence $S$, and then compute the parallel composition of $F_0$ with $F$.
The following is also true: given a Turing machine $T$ and a fixed input $P$ (i.e., initial state of the tape $P$), then it is possible to construct another Turing machine $T'$ such that execution of $T$ on input $P$ has the same result as execution of $T'$ on any input.
Formal proofs with Turing machines are often tedious and uninformative, so it's easier to see how this is true by considering a real-world program.  For instance, suppose we have Python code that defines some function t():
def t(x):
    ...

and we have some fixed string p.  Consider the following Python function t':
def t(x):
    ...
def t'(x):
    return t(p)

Then it is easy to see that the behavior of t' on any input is equivalent to the behavior of t on input p.  (Here we have hard-coded a lexical constant string in the place indicated with p above.)  You can do the same thing with Turing machines, where the machine first writes $P$ on the tape, and then starts executing $T$, to define a Turing machine $T'$ that proves the claim above.


Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

Unfortunately, (weighted) maximum independent set is very hard to approximate. You might be able to do a bit better if you can analyze the graphs in your application (perhaps they are not truly arbitrary).

In any case, luckily your graphs are quite small (200 thousand vertices or so). A naive algorithm (say a greedy one) will run quite fast, but might be far from the optimum. Especially since several hours (or even days) of runtime is fine, I'd experiment with a genetic algorithm.

Being a rather central problem, there are studies into this as well. For a starter, one could look at [1]. In practice, I would expect one to be quite happy with such an approach.

[1] Hifi, Mhand. "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems." Journal of the Operational Research Society 48.6 (1997): 612-622.


Checking if sequence is almost strictly in ascending order

It does not cover all cases! Consider the sequence [2, 6, 4, 8, 7].
Before the return statement, the values of seq1 and seq2 are: $seq_1 = 2$, $seq_2 = 0$. So the function would return $True$. However, the sequence is not almost strictly increasing, because you need to remove at least two elements from it to obtain an increasing sequence.

So, either the Java implementation is not faithful to the conceptual algorithm, or the conceptual algorithm is wrong.

The problem can be solved by finding the length of the longest increasing subsequence (LIS) of the given sequence. Call $n$ the length of the original sequence. If the LIS has length $\ge n-1$, the sequence is almost increasing according to your definition. If the LIS has length $\le n-2$, the sequence is not almost increasing.


Number of submatrices with a particular sum- Answer Explantion

The two-pointer algorithm is described in this post. Given a non-negative sequence $\alpha_1,\ldots,\alpha_n$ and a target sum $S$, we want to find the number of pairs $(i,j)$ such that $\alpha_i + \cdots + \alpha_j = S$. Let's make life a little easier by requiring the sequence to be strictly positive. For each $i$ there is therefore at most one $j$ such that $\alpha_i + \cdots + \alpha_j = S$, and we could find it by enumerating over all $j$ (resulting in an $O(n^2)$ algorithm) or using binary search (this requires $O(n)$ preprocessing, and leads to an $O(n\log n)$ algorithm).

The two-pointer algorithm is very similar but uses data from the $i$th iteration to make the $(i+1)$th iteration faster. Here is one variant For each $i$, we calculate the minimal index $j(i)$ such that $\alpha_i + \cdots + \alpha_{j(i)} \geq S$. The main observation is that $j(i)$ is a non-decreasing sequence, that is, $j(1) \leq \cdots \leq j(n)$. This suggests the following algorithm:

Initialize $j(0) = 0$.
For each $i$ in turn, calculate $j(i)$ by going over $j = j(i-1),j(i-1)+1,\cdots$ until $\alpha_i + \cdots + \alpha_j \geq S$. We then set $j(i) = j$. If $\alpha_i + \cdots + \alpha_{j(i)} = S$, we have found a subsequence summing to $S$.

This algorithm runs in linear time (basically since the index $j(i)$ keeps increasing) and finds all contiguous subsequences summing to $S$. I'll also let you figure out yourself what to do when some entries could be $0$.


Finding all paths between a set of vertices in a DAG

Any algorithm for your problem will have to take exponential time in the worst case.  However, if you're willing to live with this, there is a straightforward recursive algorithm to solve your problem.  Details below.

Generalizing a little bit, your problem is essentially the following:

Input: a dag $G=(V,E)$, three sets $S_0,S_1,S_2 \subseteq V$ of vertices

Output: the set of all paths that start some element of $S_0$, end at some element of $S_1$, and all of whose intermediate vertices are from $S_2$

To see the relationship to your problem statement, let $S_0$ be the set of vertices that are reachable from vRoot and also contained in vSet; let $S_1$ be vSet; and let $S_2$ be the complement of vSet.

There is no efficient algorithm for this problem, because in the worst case there could be exponentially many such paths.  Therefore, any algorithm to print all such paths will necessarily have to take exponential time, in the worst case.  Of course you could build algorithms that are efficient on some inputs, but no algorithm will be efficient on all possible inputs.

However if you are willing to live with this limitation, here is an approach you could use.  Basically, it's easy to come up with a recursive algorithm for this problem:

Compute the set $S_0$ of vertices that are reachable from vRoot and are contained in vSet.  This can be found in linear time using DFS or BFS.  You can also compute $S_1$ and $S_2$ in linear time.
Enumerate all paths of the desired form recursively.  We will build a procedure $F$ so that, for a vertex $v \in V$, $F(v)$ returns the set of all paths that start at vertex $v$ and end at some vertex in $S_1$ and where all other nodes (the intermediate nodes) are all within $S_2$.  You can compute $F$ via a simple recursive procedure:

For each $w \in S_2$ such that there is an edge $(v,w) \in E$, compute $F(w)$.
Now we can return $$F(v) = B(v) \cup B'(v) \cup \{v@p : w \in S_2, (v,w) \in E, p \in F(w)\},$$

where $v@p$ denotes the path that starts at $v$, goes to $w$, and then follows the path $p$; and where $B(v),B'(v)$ are defined as follows:

if $v \in S_1$, then $B(v)$ is a singleton set containing the path of length 0 that starts at $v$ and stops there; if $v \notin S_1$, then $B(v)$ is the empty set.
$B'(v) = \{v \to w : w \in S_1, (v,w) \in E\}$.

Finally, calculate $F(v)$ for each $v \in S_0$ and output the union of all of those paths.
For better performance, I recommend that you use memoization to avoid ever calculating $F(v)$ more than once for any particular vertex $v$.

This immediately gives you a recursive algorithm that solves your problem, and whose running time is linear in the size of the graph plus the size of the desired output.  In other words, this algorithm is about as efficient as you could possibly hope for, given the problem statement.


I think I may solve it but I'm not sure: In short the sorting can be done in $\Theta(n)$, so the book statement, hence my assumption, is not correct. The "Sort points by y-coordinate in Left, and Right" actually only need to merge it, and this step is $\Theta(n)$.


Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$

The proof is by contradiction. We assume that $\mathsf{P} = \bigcup_{k=1}^\infty \mathsf{DSPACE}(\log^k n)$, and reach a contradiction.
Let $L$ be any language in $\mathsf{DTIME}(n^{\log n})$. Thus there is a Turing machine for $L$ which runs in time $n^{C\log n}$, and in particular, uses space at most $n^{C\log n}$. Let $L' = \{ x10^{|x|^{C\log |x|} - |x| - 1} : x \in L \}$. Then $L' \in \mathsf{P}$, and so $L' \in \mathsf{DSPACE}(\log^k n)$, for some $k$. In terms of the true input size $m$, we have $n = m^{C\log m}$, and so $L \in \mathsf{DSPACE}(\log^k (n^{C\log n})) \subseteq \mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{P}$. This contradicts the time hierarchy theorem.


A problem regarding Extended Euclidean Algorithm

Here are some ideas to get you started.

A number $n$ cannot be represented as a linear combination of $n_1,n_2$ unless $(n_1,n_2) \mid n$, since all linear combinations of $n_1,n_2$ are multiples of $(n_1,n_2)$.
The extended Euclidean algorithm gives you values $a_1,a_2$ such that $a_1n_1+a_2n_2 = (n_1,n_2)$, and in particular $$\frac{n}{(n_1,n_2)} a_1 n_1 + \frac{n}{(n_1,n_2)} a_2 n_2 = n.$$
If $n = b_1 n_1 + b_2 n_2$ then all other representations are of the form $$n = \left(b_1 + \frac{n_2}{(n_1,n_2)} t \right) n_1 + \left(b_2 - \frac{n_1}{(n_1,n_2)} t \right) n_2.$$

Try to use these ideas to solve the problem on your own.


$\mathsf{Steps}(\Pi)$ is defined just above, in the paragraph below Definition 4.1. It's the set of node labels in the proof, i.e. the set of propositions that are proved as lemmas in that proof.

Thus a local inference system is a set of propositions such that every deduction $T \vdash u$ can be proved from lemmas that only involve terms that are subterms of the proposition $u$ or of the premises $T$.


Find a maximum matching that saturates a given set of vertices

After some research, I found out that my question is a special case of the problem of priority matching. In this case there are two priority classes, $X_0$ and $X_1 := V\setminus X_0$. The goal is to find a matching that maximizes the number of saturated vertices in $X_0$, and subject to that, the number of saturated vertices in $X_1$. There are efficient algorithms that solve this problem for any number of priority classes. It is known that any priority matching is also a maximum-cardinality matching.


SAT solver optimizations of DPLL for unsatisfiable formulas

Conflict analysis and clause learning and non-chronological backtracking should help a lot, for both satisfiable and unsatisfiable instances.  They discover large portions of the search space where no solution can reside and prune the search to avoid traversing those.

You could also try two-watched-literals unit propagation, but I'd try the others first, as I expect they'll make a bigger difference.


Randomize List with guaranteed Index Change

NOTE: updated (before it had low=i+1 always, this missed some valid results, and missed the extra check needed for the last index)
**NOTE: update 2 - randomize order to ensure uniformity **
Consider the following approach:
loopIndex[0..n-1] = permute([0..n-1])
index[0..n-1] = [0..n-1] // track indices
for i=0..n-2
   idx = loopIndex[i]
   if index[idx] == idx
      low = i+1
   else low = i
   swapIdx = random(low,n) // random(start,end) --> start <= i < end
   swapElement(index, idx, loopIndex[swapIdx])
   swapElement(array, idx, loopIndex[swapIdx])
finalIdx = loopIndex[n-1]
if index[finalIdx] == finalIdx
   finalSwapIdx = random(0,n-1)
   swapElement(index, finalSwapIdx, finalIdx)
   swapElement(array, finalSwapIdx, finalIdx)

PROOF NOT YET UPDATED
Note the following:

loopIndex is used to give a random ordering on which we process the elements. This ensures that any non-uniformity is "smoothed out".
If an index $j$ is selected as swapIdx then that element is swapped to a place where it's not processed again in the loop.
If an index $j < n-1$ is never selected as swapIdx then when $i==j$ the element will be swapped out from $j$ and never can return to $j$.
The final check handles the case where the final element was never selected. In this case, we swap between $n-1$ and some other random element.

Proof of uniformity by induction on the index -
Let $p(j,k)$ be the probability that after completing $i=j$, the element at index $j$ is the element that originally had index $k \neq j$ (clearly $p(j,j)=0$).
Then $p(0,k)=\frac{1}{n-1}$ clearly.
Assume then that the statement holds for all $j \leq t$ and we now prove for $j=t+1$.
$p(t+1,k)$ is the probability the element with original index $k$ is not in the first $t$ elements at step $i=t+1$, times the probability that $k$ is swapIdx now. By the assumption, this is then:
$$
\left(\frac{n-2}{n-1}\right)\left(\frac{n-3}{n-2}\right)\dots\left(\frac{n-t-1}{n-t}\right)\left(\frac{1}{n-t-1}\right) = \frac{1}{n-1}
$$
(Note that there is a minor difference between $k \leq t$ and $k > t+1$. For the former, it must not have been selected as a swapIdx for $j \neq k \leq t$, and it must not have selected $t+1$ as its swapIdx. For the latter, it must not have been selected as a swapIdx. The result though is the same in terms of the math).


Chernoff bounds and Monte Carlo algorithms

Let's suppose that we have a polynomial time randomized algorithm $A$ for a decision problem $\Pi$ with the property that
$$
\mathrm{Pr}[A \text{ is right}] > 1/2
$$
for all inputs.  (In particular, independent of the input length $n$.)

We can use Chernoff bounds to show something stronger, namely that for any fixed $c$, there is a polynomial time, randomized algorithm for $\Pi$ that is correct with probability at least $1-n^{-c}$.

The algorithm is very simple: On an input of length $n$, we run $A$ a polynomial number of times $N$ (to be determined below) and then report the majority answer.  Call this algorithm $A'$.

What we need is a bound on
$$
\mathrm{Pr}[A' \text{ is wrong}]
$$
in terms of the number of repetitions $N$.  The hypothesis about $A$ implies that there is an $\epsilon > 0$ such that
$$
\mathrm{Pr}[A \text{ is right}] \ge 1/2 + \epsilon
$$
Since the $N$ runs of $A$ are independent, for any $k\in [N]$ we have
$$
\mathrm{Pr}[k \text{ of } N \text{ runs of } A \text{ are right}]\ge Pr[X = k]
$$
where $X$ is a binomial random variable with parameters $N$ and $1/2+\epsilon$.  Since the algorithm $A'$ is wrong exactly when at most $N/2$ of the runs of $A$ are right, we obtain an upper bound on the failure probability by a "tail estimate" bounding
$$
\mathrm{Pr}[X \le N/2]
$$
This is a prototypical time to use a Chernoff bound, since a binomial r.v. is the sum of $N$ independent random variables.  One instance of the Chernoff bound says that if $Y$ is the sum of $N$ independent r.v.'s with support in $[0,1]$ and $t > 0$, then
$$
\mathrm{Pr}[Y < E[Y] - t] \le e^{-2t^2/N}
$$
Thus, since $E[X] = N/2 + N\epsilon$, we take $t = N\epsilon$ to obtain
$$
\mathrm{Pr}[A' \text{ is wrong}]\le e^{-2\epsilon^2 N}
$$
So we can take $N = (1/2)\epsilon^{-2}c\log n$, and we get the claimed error probability for $A'$.


Approximation factor of NP-complete problems

The crucial assumption here is that the value is an integer.

If the value is an integer, then telling whether there is a valid solution with value $\le 10$ is as hard as telling whether there is a valid solution with value $\le 10.999$ (it's the question).  Thus, you shouldn't expect a polynomial-time approximation algorithm with approximation factor $10.999/10$ or better -- if you had such an approximation algorithm, you could tell whether there was a valid solution with value $\le 10.999$, which would tell you whether there is a valid solution with value $\le 10$, which would let you solve the original problem, which would mean that you have found a polynomial-time algorithm for a NP-complete problem.  That would be unexpected.


Is this an abuse big O notation as a power of a number?

This is perfectly standard use of big O notation, despite some purists disliking it. Here is what the passage you quoted means:

Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) = O(t(n))$.

This is still somewhat ambiguous, since it’s perhaps not clear what variables the big O depends on. In this case, big O hides a universal constant:

There exists a constant $C>0$ such that the following holds.
Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) \leq Ct(n)$ for all $n$.

This allows us to rephrase the statement in yet another way:

There exists a constant $C>0$ such that the following holds.
Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{Ct(n)}$ time deterministic single tape Turing machine.

(This assumes that by “$f(n)$ time machine” we mean a machine running in time at most $f(n)$.)


Operating systems have Application Programming Interfaces, whose functionalities are available as libraries that are linked to the code produced by the programmer.

This does not mean they constitute virtual machines. They just encapsulate operations that are not directly accessible to the programmer, either because they depend on low level instructions or protocols that are protected, or because they are provided as high-level standard services.

What happens is simply that what you write in a language that compiles to machine code is only a part of what will be running. Usually a very small part.


shortest time based on traffic congestion data

There is no special "algorithm theory" behind this.

You decomposed this data into a graph, right? You have intersection nodes, and you have edges with path difficulty (distance/average speed), yes? The congestion data simply modifies the average speed of the edge, so it's just A* business as usual. Regular shortest path heuristics will probably still be relevant for conservation purposes if you're lazy.

Obviously a prominent example of an implementation of this would be https://maps.google.com/.


Are the undecidable languages closed under complement?

Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?


Why is log(n) a space-constructible function?

Because when we write $\log n$ it's either in a context where it doesn't matter (e.g. Landau bounds) or with the implicit meaning of $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.

It certainly doesn't make sense to talk about constructible functions with real range, I would assume your source is talking about $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.


Can you explain in terms of logic gates how Babbage’s Analytical Engine worked?

The documentation is quite clear they're still working out what the design was supposed to be.

Taking an approximation - they have developed a Java program to run sample programs. The logic behind the source code shows how it may have worked.


What are the disadvantages of Fibonacci Heaps?

$O(1)$ merely means that no matter how large your heap grows, the operation will always take roughly the same time to execute. It doesn't mean "the fastest".
Wikipedia article you linked has section named "Practical considerations":

Fibonacci heaps have a reputation for being slow in practice due to
large memory consumption per node and high constant factors on all
operations. Recent experimental results suggest that Fibonacci heaps
are more efficient in practice than most of its later derivatives,
including quake heaps, violation heaps, strict Fibonacci heaps, rank
pairing heaps, but less efficient than either pairing heaps or
array-based heaps.


What is the difference between modulo and modulus?

"modulo" is an operator.  For instance, we might say "19 and 64 are congruent modulo 5".

"modulus" is a noun.  It describes the 5 in "modulo 5".  We might say "the modulus is 5".

No, the two should not be used interchangeably.  It would be incorrect to say "19 and 64 are congruent modulus 5".  It would also be incorrect to "the modulo is 5".

See also https://en.wikipedia.org/wiki/Modular_arithmetic and https://en.wikipedia.org/wiki/Modulo_operation.  Both define the word "modulus", and as far as I can see they use it correctly.


What does a ball of center v and radius r with at most r hops away mean?

An undirected (possibly weighted) graph defines a metric space, in which the distance between two vertices $x$ and $y$ is the length of the shortest path between $x$ and $y$; here the length of the path is the sum of the weights on the edges (weights are assumed to be non-negative), or the number of edges if the graph is unweighted. Given a metric, a ball is defined according to your formula.

If the maximal degree is $d$, the number of vertices in a ball of radius $r$ is at most $1 + d(1+\cdots+(d-1)^{r-1})$, which is what you get for a $d$-regular graph.


Is this a correct grammar for untyped lambda calculus?

Your grammar looks fine. You can make a recursive descent parser for it.

The AST for (\x.x)(\y.y) is, if I got everything right,

term
  application
    atom
      lparen
      term
        abstraction
          lambda
          lcid
            x
          dot
          term
            application
              atom
                lcid
                  x
              application'
                eps
      rparen
    application'
      atom
        lparen
        term
          abstraction
            lambda
            lcid
              x
            dot
            term
              application
                atom
                  lcid
                    y
                application'
                  eps
        rparen
      application'
        eps


What's the difference between $O(1)$ and $o(1)$?

A function is $O(1)$ if it is bounded from above. It is $o(1)$ if it tends to zero. Any function which is $o(1)$ is also $O(1)$.

For example, $\sin^2 x$ is $O(1)$ but not $o(1)$, and $1/x$ is both $O(1)$ and $o(1)$.


All you need to do is show that a machine with $m$ states can halt with $\Omega(2^m)$ 1's on the tape.

There are many ways to prove this. This is just one suggestion, and it may be sub-optimal.

Let $T$ be a machine that on a word of the form $0^i1^j$, when the head is in the leftmost $0$, halts with $0^i1^{2j}$ on the tape and the head at the leftmost $0$.

$T$ is a fixed machine, and thus has $t$ states, for a constant $t$.

We now construct the machine $M_i$ as follows: first, $M_i$ writes $0^i1$ on the tape, using $i+1$ states. It then moves the head to the left most cell, using another single state.
Then, if the leftmost cell is $0$, it erases it and passes control to $T$ (this requires $t+1$ states).
If the leftmost cell is $1$, it halts.

$M_i$ has $i+2+t$ states, and after it halts the tape contains exactly $2^i$ 1's (since in every call to $T$ we double the number of 1's, and we call $T$ $i$-times).

Thus, if $M_i$ has $m$ states, it halts with $\frac{2^m}{t+2}\in\Omega(2^m)$ 1's, and we are done.


Complexity of Two problems graphs with cycle

The first problem can be answered by finding the length of the shortest cycle in $G$, a parameter known as the girth of $G$. Indeed, if $G$ has girth $g$ then $G$ contains a cycle of length at most $k$ iff $g \leq k$. You can use BFS to find the girth efficiently, see for example these course notes. Therefore this problem can be solved in polynomial time.

The second problem is NP-complete by reduction from Hamiltonian cycle, as you mention (just choose $k = n$).


Can the concatenation of two non-regular languages be regular?

Hint: Let $C$ be the language of words that have the same number of 1's as 0's.  Is $C$ regular?  Let $A = \{0,1\}^* \setminus C$.  Is $A$ regular?  Now, can you find a non-regular language $B$ that will make $AB$ regular?


Hint:

   Yes

Solution:

   $$\{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}\}: k \geq 1 \land n_1 = k \land \forall i. n_i = n_{i+1} \}$$

 and therefore the complement is

 $$\{a,b\}^{\ast} \setminus \{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}: n_1 \neq k \lor \exists i. n_i \neq n_{i+1}\}$$

 which is context-free as you can easily write a nondeterministic PDA.


Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets

Concretely, let us count the number of ways to partition $[n]$ into $k$ non-empty ordered subsets, which are themselves ordered by increasing order of the first element. For example, a valid partition of 10 into 5 sets is
$$
\{1,4,5\},\{2,3,6\},\{7\},\{8,10\},\{9\}.
$$
Note that $1<2<7<8<9$.

The base cases $k=0,k=1,k=n$ are easy, so suppose $2 \leq k < n$. A partition of $[n]$ into $k$ ordered subsets can be obtained in two ways:

Taking a partition of $[n-1]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.
Taking a partition of $[n-1]$ into $k$ ordered subsets, and adding $n$ to the 1st subset, the 2nd subset, ..., the $k$th subset.

By recursively generating all partitions of $[n-1]$ into $k-1$ or $k$ ordered subsets, you can thus generate all partitions of $[n]$ into $k$ ordered subsets.

As D.W. mentions, this is just the recurrence for the Stirling numbers.


What is the difference between undecidable language and Turing Recognizable language?

A language $L$ is decidable if there exists a Turing machine $M$ such that:

If $x \in L$ and $M$ is run with input $x$, then $M$ halts at an accepting state.
If $x \notin L$ and $M$ is run with input $x$, then $M$ halts at a rejecting state.

(In particular, $M$ always halts.) If no such Turing machine exists, $L$ is undecidable.

A language $L$ is recognizable (or, recursively enumerable, abbreviated r.e.) if there exists a Turing machine $M$ such that:

If $x \in L$ and $M$ is run with input $x$, then $M$ halts.
If $x \notin L$ and $M$ is run with input $x$, then $M$ doesn't halt.

If no such Turing machine exists, $L$ is unrecognizable.

A basic fact about these definitions is:

  A language $L$ is decidable if and only both $L$ and $\overline{L}$ are recognizable.

Your language $A_{TM}$ is one way of stating the halting problem (there are many equivalent ways). It is recognizable but not decidable.


It is conjectured that the complexity of SAT on $n$ variables is $\tilde\Omega(2^n)$ (a version of this is SETH, the strong exponential time hypothesis). In contrast, Grover's algorithm solves it in $\tilde O(2^{n/2})$.

On the other hand, it is conjectured that quantum computers cannot solve NP-hard problems in polynomial time, that is $\mathsf{NP} \not\subseteq \mathsf{BQP}$.


How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

Sort T. Then take elements while T[i] >= i+1.

For example sorted(T)=[6,4,3,3,1,1]. Then, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3 and finally, T[3] = 3 < 4 so we have S = [T[0], T[1], T[2]].


Traversing a graph with respect to some partial order

This is a job-shop scheduling problem, known as $1|\textrm{prec},p_i=1|\Sigma w_i C_i$. It is $NP$-complete.

Lenstra, J.K. and Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. In Operations Research, vol. 26, pp. 22-35 (1978)

Sadly the paper is not open-access. They show $NP$-hardness by reduction from Linear Arrangement (also known as Graph Bandwidth)


Show that the regular language is contained in another

It is just a simple subset proof:

Let $(u, v) \in (L_1 \otimes L_2)^+$. Thus, there is a decomposition of $(u, v)$ into $(u_1 \ldots u_k, v_1 \ldots v_k)$ with $u_i \in L_1$ and $v_i \in L_2$ and $k > 0$. Hence, we have $u \in L_1^+, v \in L_2^+$. So overall we have $(u, v) \in L_1^+ \otimes L_2^+$.


Showing that algorithm has STOP property and finding its computational complexity function

You have already proven $a < b$. Let $g$ be the gap between $a$ and $b$, so $b - a$.

Show that the algorithm terminates when $g = 1$.
Show that when $g > 1$ we have as postcondition that the new $g' \leq \lceil g/2 \rceil$ in the loop body, and thus $g' < g$.
Show that it's impossible to skip $g = 1$, and thus the algorithm must terminate.


How can I efficiently plot the inside of an ellipse?

Following @Evil's comment, I suggest two steps. For each ellipse $E$:

(1) Computing a bounding box $B$ for $E$.

(2) For each row of pixels in $B$, walk left-to-right until a pixel $p_1$
is discovered to be inside $E$.
Then walk right-to-left until $p_2$ is in $E$.
Then all the pixels from $p_1$ to $p_2$ are in $E$
(because of convexity).

The most difficult step is computing a bounding box for the ellipse.
You likely don't need it exactly.
Here are two sources:

"How do you calculate the axis-aligned bounding box of an ellipse?."
"How do you find a tight-fitting, axis-aligned, bounding box of a rotated ellipse in AS3?."


First of all, for your definition of NP-complete, we require the reduction to be polynomial time. This makes it so that if we could solve an NP-complete language, L, in polynomial time, we would have a polynomial time algorithm for all of NP by composing the polynomial time reduction with that algorithm for L.

Note that the size of the output of a reduction has to be less than the run time of the reduction. The biggest output possible given a fixed run time would be one where a Turing machine, M, prints to its output tape at every step.


Express semantic duplicates of records formally

The basic mathematical concept at play here is a binary relation. For a certain measure of similarity, two records are either similar or not. Formally, a binary relation assigns a truth value (true or false) to every ordered pair of records. The usual notation to state that two records are similar is $r_1 \approx r_2$ where $\approx$ is the notion of similarity. There can be multiple notions of similarity (allowing for more or fewer differences between records).

Given the intended purpose, any notion of similarity should be reflexive: a record is similar to itself. Any notion of similarity should probably be symmetric: if $r_1$ is similar to $r_2$ (for a given notion of similarity) then $r_2$ is similar to $r_1$ for that same notion of similarity. It's less clear whether the similarity relation should be transitive, which would make it an equivalence relation. If $r_1$ is similar to $r_2$ and $r_2$ is similar to $r_3$, does that make $r_1$ similar to $r_3$? Or in other words, is a duplicate of a duplicate a duplicate? If your intuition of similarity is that the records are at most a certain distance from each other, then no (this thread on Math.SE discusses this intuition). But if you think of all records falling into a well-defined bucket, with sufficiently similar records ending up in the same bucket, then you have an equivalence relation, and the buckets are called equivalence classes. If you have a way of defining a privileged element in each equivalent class (a “completed” or “presentation” version of the record), that's called a canonical representation.

Equality is the finest (i.e. most discriminating) equivalence. It is normally written $=$. A generic equivalence relations is typically written $\equiv$. If you need to consider more than one equivalence relation, then the typical notation scheme is to use $=$ or $\equiv$ with some ornaments on it.

The terminology “hard duplicate” or “soft duplicate” isn't standard, but it's comprehensible. “Equal” vs. “equivalent” or “equal” vs. “similar” are more standard terms.

To define an equivalence, a typical approach is to give rules: “if $r_1$ and $r_2$ are such that … then the two records are equivalent”. For example, you might have a rule that if two records are the same except for letter case variations on the name field then they're equivalent. Two records are equivalent if there's a way to find a chain using those rules plus the “built-in” reflexivity, symmetry and transitivity rules from one record to the other.

To define a non-transitive similarity, a typical approach is to define a distance between records.

The general problem of determining when records in a database should be treated as representing the same entity is called data normalization. With respect to database design, that's database normalization.