Computationally and memory efficient algorithm for a relatively simple problem

I don't know what algorithm they use so I don't know whether this will be better, but there is an efficient algorithm for your problem, by using a tree.  Form the list of all endpoints of all ranges and bins, and sort it.  This partitions the real line into non-overlapping intervals, where each bin is a union of intervals that don't overlap.
Put those endpoints into a binary search tree.  Each internal node in the binary tree represents a union of those intervals.  You can store, in each tree, the min, max, sum, and sum of squares of all values in that interval, filling these in bottom-up.  Note that given these statistics for the two children of a node, it is easy to compute these statistics for the node itself in $O(1)$ time.
This yields an $O(n \log n)$ time algorithm, where $n$ counts the number of ranges + number of bins. It takes $O(n \log n)$ time to sort the endpoints, then $O(n)$ time to build the binary search tree, then $O(n)$ time to fill in each node bottom-up.
You might also enjoy reading about interval trees and segment trees, if you do a lot of computation on ranges/intervals.


Indeed, maxterm is the concept dual to minterm. As you mention,
$$
f(x) = \bigvee_{y\colon f(y)=1} \text{"$x=y$"} = \bigvee_{y\colon f(y)=1} \bigwedge_{i=1}^n \text{"$x_i=y_i$"}.
$$
Here $\vee$ is OR (your addition), $\wedge$ is ADD (your multiplication), the input is $x = x_1,\ldots,x_n$, and "$x_i=y_i$" is either $x_i$ (if $y_i$ is True) or $\bar{x}_i$ (if $y_i$ is False).

Similarly, we have
$$
f(x) = \bigwedge_{y\colon f(y)=0} \text{"$x \neq y$"} = \bigwedge_{y\colon f(y)=0} \bigvee_{i=1}^n \text{"$x_i \neq y_i$"}.
$$
This time "$x_i\neq y_i$" is $x_i$ if $y_i$ is False, and $\bar{x}_i$ if $y_i$ is True.

When the function is monotone, we can improve on the first representation:
$$
f(x) = \bigvee_{\text{$y$ minterm}} \text{"$x \geq y$"} = \bigvee_{\text{$y$ minterm}} \bigwedge_{i\colon y_i=1} x_i.
$$
Here "$x \geq y$" means $x_i \geq y_i$ for all $i$, and a minterm is a satisfying assignment of $f$ which is minimal in the sense that changing any 1 to 0 changes it to an unsatisfying assignment.

We can define maxterms analogously – maximal unsatisfying assignments, and then
$$
f(x) = \bigwedge_{\text{$y$ maxterm}} \text{"not $x \leq y$"} = \bigwedge_{\text{$y$ maxterm}} \bigvee_{i\colon y_i=0} x_i.
$$


Compression algorithms for small strings - building upon / extending Huffman

A simple variant of Huffman is due, I believe, to David Wheeler.

Suppose the alphabet is $\Sigma = \{s_1, \dots, s_n\}$ and let $\star$ be some new character that's not in $\Sigma$. For each character $s\in\Sigma$, let $p(s)$ be the most common character to occur immediately after $s$ in your dataset.

To compress the string $X=x_1\dots x_N$, you first scan through it and, each time $x_{i+1}=p(x_i)$, replace $x_{i+1}$ with $\star$, giving a new string over alphabet $\Sigma\cup\{{\star}\}$. Then run ordinary Huffman on the resulting string. The idea is that the character $\star$ should be really common in the modified string, so it should get a really short codeword.

For example, if your alphabet is $\{a,b,c,d\}$ and $p(a)=a$, $p(b)=a$, $p(c)=d$ and $p(d)=c$, then the string $abacd$ would be transformed to $ab{\star}c{\star}$ and $cdcdcd$ would be transformed to $c{\star}{\star}{\star}{\star}{\star}$.

Since all your example strings begin with Z, it might also be worth storing the most common initial character to allow you to replace the first character of the string with $\star$, too.


What is the significance of context-sensitive (Type 1) languages?

The context-sensitive languages are exactly the languages that can be recognized by a Turing machine using linear space and non-determinism. You can simulate such a Turing machine using exponential time, so you can recognize any such language in exponential time. Do note that the problem of recognizing some context-sensitive languages is $PSPACE$-complete, which means we're pretty sure you can't do better than exponential time.

Comparing this to type 0 languages, this means you can at least say something about how long it takes to recognize the language. A type 0 language may not even be decidable: the language of all Turing machines that halt is a type 0 language, but as recognizing this language is exactly the halting problem, it is not decidable.

Context-sensitive grammars are not very useful in practice. Context-free grammars are intuitive to work with, but as the examples on Wikipedia show, context-sensitive grammars very quickly become rather messy. Programs using polynomial space are much more easily designed (and the $PSPACE$-completeness guarantees the existence of some equivalent CSG that is only polynomially larger than the space usage of your algorithm).

The reason for their existence is that they form a very natural extension of context-free grammars (you allow context to determine which productions are valid). This will probably have inspired Chomsky to define them and name them the type 1 languages. Remember that this definition was made before computers became as fast as they are today: it's more of interest to formal language theorists than for programmers.

Unrestricted grammars get even weirder: there's no longer a notion of 'expanding' a nonterminal and replacing it with a production, possibly depending on context. You're allowed to freely modify the context as well. This makes unrestricted grammars even less intuitive to work with: programs are equivalent and a lot more intuitive.


How to build tree from graph with specific property

In a connected component, the minimum node can reach any other node without passing by a lower index node. As your initial graph is connected, the node 0 can indeed reach any other and is the perfect root for your tree.

For any connected component, you keep the index of the node it is attached to. Initially, there is none as 0 will be te root.

Once you considered the minimum node of a connected component, you can remove it as no other node in the CC may use it. Let's call this node $k$, you add $k$ to its place in the tree you are building, as child of the node index of the connected component.

Then either the connected component is still connected and its new index is $k$, either it is cut in several connected components, all having $k$ as index.


"Greater than" condition in integer linear program with a binary variable

I think I found the answer here!
It is sufficient to use the big-M method by introducing the following constraints:

B >= C + 1 - M*(1-A);

C >= B + 1 - M*A


Is Functional Complete means Turing Complete?

A Turing machine defines a function over all of $\Sigma^*$, it is a finite object which describes the operation on infinitely many inputs.

A logical circuit however, is defined over a specific number of variables, so it has a finite domain. Using boolean circuits over $n$ variables we can implement the set of all functions from $\left\{0,1\right\}^n$ to $\left\{0,1\right\}$, and no more (so no Turing completeness in the simple interpretation).

This is why, when dealing with logical circuits, the notion of non uniform computation is introduced. By non uniform, we mean that the mechanisem for processing some input $x$ might depend on $|x|$. In the context of circuits, this means that instead of talking about one circuit, were talking about a circuit family $\left\{c_n\right\}_{n\in\mathbb{N}}$, where $c_n$ is a circuit with $n$ inputs.

We say that a circuit family $\mathcal{C}_n$ decides some language $L$ if $\forall x\in\Sigma^*: x\in L \iff c_{|x|}(x)=1$. Note that non uniform computation extends the classical uniform computation, i.e. using circuit families of arbitrary size we can decide undecidable (relative to Turing machines) languages. Actually, we can decide all languages. If you want to reduce this back to the Turing model, then you must require the existence of a computable function $f$ which, given $n$, generates the circuit $c_n$.


How to transform an Abstract Syntax Tree (AST) to an Abstract Binding Tree (ABT)? (for machine learning fo theorem proving)

Your referenced paper doesn't define the term "abstract binding trees"; where did you get that phrase? (I did not look at your other references; this paper was interesting enough by itself).
The paper does define a variety of transformations on ASTs by examples, but IMHO those examples are sufficient to define or least lookup the necessary algorithms.
What I interpret the paper as saying is,  "(for our GNN-based theorem prover), you can use pure ASTs, or you can use a variety of variants which perform better because they take context into account".
If you work on compiling code, you already know the value of (semantic) context over a pure context-free parsing in validating program source text (and logical formulas are just a kind of programming text).   I make this point brutally obvious here: Life After Parsing
They seem to define context in three different ways:

bidirectional links between parent and child nodes.   Having links going both directions allows context to be computed bottom up, and to have context flow from some children of a node, to be passed as context to other children.  This sounds like the value one obtains by having an attribute grammar, which has synthesized properties and inherited properties.   I didn't read the paper carefully enough to understand what information was being propagated up, or what was being propagated down, or even how their GNN accomplished this effect.   Implementing this is rather trivial: one needs child links and parent links in the nodes.

joining nodes in the AST that represent the same variable.  What this is doing is taking into account scoping rules in the language, and amounts to replacing variable names by symbol table references.  They argue that the type information associated with the symbols should be included, which you get for  "free" if your symbol table includes type information, which any serious symbol table does.  Implementing this requires that your AST processing machinery be augmented with symbol tables, and that the AST is processed to replace identifier nodes with symbol table entries (well, with the content of the appropriate symbol table entry).   This is hard to do if your langauge is complex (e.g, symbol tables for C++ will make your head explode) you need an extremely organized attack to build/use these; this is part of the reason that building compiler front ends is hard.  But for the HOL representations being used by the authors, the "symbol" tables are pretty simple and you can probably do this in an ad hoc way with a tree-scanning procedure.

Merging common subtrees honoring variable type information into single trees.  This is classically what common sub-expression elimination does.   Its apparent value in this paper is that it can dramatically shrink the size of the tree and therefore the implied amount of work it takes to process the tree. (You can get an overly compressed tree for free if you use a GLR parser which produces maximally shared subforests which happen to also include expression trees, but  you have to split out shared subtrees based on type information after the fact).  I note this looks to me not so much as context usage but "merely" size reduction.

TLDR:  The authors appear to implementing classic compiler front end building techniques and algorithms to convert ASTs into what amounts to Directed Acyclic Graphs that encode type information for different variables.
[FWIW, a generalized AST-processing engine I build called DMS has: a) bidirectional links between parent and child nodes, b) shared subtrees via GLR parsing c) symbol table definition methods, d) attribute-grammar definition/execution which is easily used to scan  ASTs to link leaves to symbol table entries. AFAICT, DMS sort of does everything this paper suggests doing.  This is because you pretty much always need at least the results of all this to process any kind of AST in a semantically sensible way].
HTH.


Disprove that a function exists that counts the turing machines that halt on $\epsilon$

Your question seems to be confusing machines and languages. Define $L_k$ to be the set of encodings of Turing machines of length $k$ that halt on the empty input. The language $L_k$ is finite, and so computable. In particular, there is a function $f\colon N \to \Sigma^*$ satisfying $L(f(k)) = L_k$ (in fact, infinitely many such functions). What you want to show is that there is no recursive function satisfying this property.

The proof is by contradiction. Suppose that there were such a computable function $f$. Now suppose you are given the description $\langle T \rangle$ of some Turing machine, of length $k$, and you want to know whether it halts on the empty input. You compute $f(k)$, and check whether $\langle T \rangle \in L(f(k))$.

Here is a more challenging question: Is the function $g(k) = |L_k|$ computable? (This function gives the number of Turing machines of size $k$ that halt on the empty input.)


How to prove that a bounded pushdown automaton is regular?

If the stack has bounded height then there are only finitely many possibilities for its contents. Therefore a regular automaton can “remember” the entire contents of the stack. In other words, you can convert the PDA into an equivalent regular automaton in which each state stores both the state of the PDA and the contents of its stack.


Is 2-SAT with XOR-relations NP-complete?

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT.  Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$$ with $y$ and $z$ as new variables.


Since every language is a countable union of regular languages, you're basically asking whether one can decide whether a given language is regular. Thus, for any reasonable representation, this task will be undecidable.

Consider the following representation of your problem, say a machine $M$ represents an infinite series of regular expressions if given input $i$, $M$ produces a regular expression $r^M_i$. You now ask whether the following language is decidable:

$L=\left\{\langle M\rangle \Big| \text{$\bigcup\limits_{i}L\left(r_i^M\right)$ is regular}\right\}$

If $M$ does not represent a series of regular expressions, i.e. on some input $i$, $M(i)$ is not a valid regular expression, then $\langle M\rangle\notin L$. $L$ is undecidable, since you can reduce the language $L_R=\{\langle M\rangle | \text{$L(M)$ is regular}\}$ to it ($L_R$ is trivially undecidable by Rice theorem). Your reduction will, given $M$, generate a machine $M'$ which on input $i$ will simulate $M$ on all inputs of length $\le i$ for $i$ steps, and according to the result, will generate a regular expression which corresponds to the union of all words that were accepted during this simulation. Clearly $\bigcup\limits_{i}L\left(r_i^{M'}\right)=L(M)$, and the validity of the reduction immediately follows.


Why does the Turing Machine allow for multiple final states?

I've never seen a definition of Turing machines that allows multiple final states. All the definitions I've seen either have a single "halt" state or one "halt and accept" state and one "halt and reject" state.

There's no benefit to having multiple final states, though there's no real harm, either. In a finite automaton, it makes sense to have multiple final states because the automaton terminates when it runs out of input and whether or not the last state is final determines whether or not it accepts its input. (I prefer the term "accepting state", for this reason.)  But, for Turing machines, the machine halts precisely when it enters a final state, regardless of what's happening on the state.  So, if you have a Turing machine with multiple final states, you could just delete all but one of them and rewrite the transition function to jump to the one that remains, instead of the ones that were deleted.


Stability for couples in the Stable Matching Problem

Yes, it is stable. It doesn't need to assign the optimal choices for both sides. To break a marriage you need two willing parties, unhappiness of one side in a marriage doesn't make it unstable here.


How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

I propose a two-step solution:

Convert your extra-notation-CFG to a normal CFG
Convert the normal CFG to CNF, e.g. as described on Wikipedia.

Do perform step 1, removing the extra notation, apply these rules:

Whenever $A^+$ occurs in a production rule, replace it with $AA^*$.
Whenever $A^*$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow AB$.
Whenever $A?$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow A$.

It should be relatively straightforward to see that the transformed versions of +,*,? repeat the argument k times, where k is in $\{1, \ldots\}$, $\{0, \ldots\}$ and $\{0, 1\}$, respectively; i.e. the rewritten version has the same meaning (language) as the input.

To perform step 2, read the Wikipedia article; it is reasonably straightforward (if a bit tedious) to translate this into an algorithm.


Perhaps because a student with two majors might have an advisor in each department, so the ID wouldn't uniquely determine the advisor (and hence the AdvisorID and, perhaps, the AdvisorName). Remember, the definition of $A\rightarrow B$ is that if two tuples in the relation have the same value for attribute $A$, they must have the same value for attribute $B$.


closure of Context free grammer to homomorphism using PDA

The idea is to replace a single transition by a sequence of transitions.
Suppose for example that $h(\sigma) = \tau_1 \ldots \tau_\ell$, and consider a transition at state $p$ which replaces the symbol $A$ on the stack with the string $\alpha$, and moves to state $q$.
We replace this transition by a sequence of transitions $p \to s_1 \to \cdots \to s_{\ell-1} \to q$, which read the letters $\tau_1,\ldots,\ell$ in sequence; the states $s_1,\ldots,s_{\ell-1}$ are unique for handling this transition. The first transition $p \to s_1$ replaces $A$ with $\alpha$, and the rest don't change the stack.


First, note that  we print a * for every tuple $(i,j,k,r)$ such that
$0 \leq  i \leq j \leq k-200 \leq \sqrt{r}-200\leq \sqrt{n}-200$

For every $i$ and $j$ there are at most $(\sqrt{n}-200)$ options, for $k$ it is $\sqrt{n}$ and for $r$ it is $n$. Thus the upper bound for the number of * is $(\sqrt{n}-200)\cdot (\sqrt{n}-200) \cdot \sqrt{n} \cdot  n\in O(n^{2.5})$.

To compute the lower bound, we can take $i$'s in the range between $0$ and $\frac{\sqrt{0.5n}-200}{2}$, $j's$  between $\frac{\sqrt{0.5n}-200}{2}+1$ and $\sqrt{0.5n}$, $k$'s between $\sqrt{0.5n}+1$ and $\sqrt{0.75n}$, and finally, $r's$ between $0.75n+1$ to $n$. Thus the number of options for a tuple $(i,j,k,r)$ is more than $(\frac{\sqrt{0.5n}-200}{2})^2 \cdot (\sqrt{0.75n}-\sqrt{0.5n})\cdot 0.25n \in \Omega(n^{2.5})$.

Thus the answer is $\Theta(n^{2.5})$


Please check the paper@arXiv2015: A Complete Worst-Case Analysis of Heapsort by M. A. Suchenek.

This paper gives a rather involved lower bound; see Abstract and Theorem 12.2 on page 94.

To the specific question,

  Example of a 500-node worst-case array for Heapsort, created by my
  Java program, is included in Appendix A.3 page 110.


Minimal Spanning Tree With Double Weight Parameters

I'm going to assume you are not given negative weighted edges, because this may not work if there are negative weights.

Algorithm

For each of your edges, label them $1$ to $n$

Let $a_i$ weight A of edge number $i$

Let $b_i$ weight B of edge number $i$

Draw up this table

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

With each of the table elements being the product of row and column.

For each edge, sum the relevant table row and column (and remember to remove the element in the intersection since it has been summed twice).

Find the edge that has the largest sum, delete this edge if it doesn't disconnect the graph. Mark the edge as essential otherwise. If an edge has been deleted, fill its rows and columns with 0.

Correctness

The result is obviously a tree.

The result is obviously spanning since no vertices are disconnected.

The result is minimal? If there is another edge whose deletion will create a smaller spanning tree at the end of the algorithm, then that edge would have been deleted and nulled first. (if somebody could help me make this a bit more rigorous/and/or counter example then that would be great)

Runtime

Obviously polynomial in $|V|$.

edit

$(2,11), (11,2), (4,6)$ is not a counter example.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Then

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

\begin{align*}
(4,6) &= 44 + 8 + 24 + 66 + 12 = 154 \\
(2,11) &= 22 + 4 + 12 + 121 + 44 = 203 \\
(11,2) &= 121 + 22 + 66 + 4 + 8 = 221
\end{align*}

$(11,2)$ gets removed.

End up with $(2,11), (4,6) = 6 * 17 = 102$

Other spanning trees are

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$


Closure properties of undecidable languages

Let $K$ be some undecidable language. Define languages $A_0,A_1,B_0,B_1$ as follows:
$$
A_0 = \{ 0 w : w \in K \}, A_1 = \{ 1 w : w \in K \}, \\
B_0 = A_0 \cup \{ 1 w : w \in \{0,1\}^* \}, B_1 = A_1 \cup \{ 1 w : w \in \{0,1\}^* \}.
$$
See if you can use these languages to show that the collection of undecidable languages is not closed under concatenation, union or intersection.

As for complementation, try to use the fact that if you can decide a language $L$ then you can decide its complement $\overline{L}$ (why?).


Shouldn't the "even parity" function map 1101 to 0?

In this context, implementing something as a ROM just means a look-up table. If you want to know the parity of $x$, you put the binary coding of $x$ on the ROM's address wires and the value you read out is the value stored at that memory location within the ROM, which will be either 0 or 1.

And, yes, the contents of the ROM that you've quoted are wrong: they seem to be implementing parity in the sense that the output is 1 if, and only if, the input is an odd number, instead of implementing the even parity function.


How does a computer compute negative(-) and positive(+) Infinity?

The simple answer is that a computer that follows a floating point standard such as IEEE 754 does not really compute +/- infinity at all. Instead it treats it as an exception - a special case. Whenever the processor detects an attempt to divide a non-zero floating point number by zero, it sets the result to a special value that is then interpreted as +/-infinity, where the sign depends on the sign of the original number.

In IEEE 754 I believe the special values of +/- infinity are represented internally as a floating point number with a sign bit, an exponent set to all $1$s, and a significand set to all $0$s. This is a value that cannot result from normal (non-exceptional) floating point operations.


Why is this language involving reversal regular?

Notice that big unconstrained $z$ in the middle. You don't need the DFA to check anything if there is a way to decompose the word that dumps almost everything into $z$.

In particular, any word of the form $a b z b a$ where $a$ and $b$ are letters and $z$ is an arbitrary non-empty word is in $L$ (with words of length 1 for $x$ and $y$).

Conversely, suppose that you have a word $w \in L$: it can be broken down as $x y^r z y x^r$ with $|x| \ge 1$ and $|y| \ge 1$. If $|x| \ge 2$ then write $x = a b x'$: we have $w = a b x' y^r z y x'^r b a = a b z' b a$ where $z' = x' y^r z y x'^r$. If $|x| = 1$ then write $y = b y'$ and do a similar decomposition.

Conclusion: another way of describing $L$ is $L = \{a b z b a \mid a,b \in \{0,1\}, z \in \{0,1\}^{+}\}$. This language is regular; a regular expression that matches it is
00..*11|01..*10|10..*01|11..*11. Intuitively, an autotomaton recognizing $L$ only needs a finite amount of memory, because it only needs to memorize the first two letters.


Let's work it out through the conversion algorithm given in
Wikipedia.

input:
$S \to  abC \mid  babS \mid de$
$C\to aCa \mid b$

Introduce $S_0$:
$S_0 \to S$
$S \to  abC \mid  babS \mid de$
$C\to aCa \mid b$
remove $\epsilon$ rules: there are no $\epsilon$ rules, so nothing changes.
eliminate unit rules: Originally, there are none, but we added one, namely $S_0\to S$. Since it's the only one, we'll deal with it later (after $S$ is already in CNF). This will be done by adding, for any rule $S\to V_iV_j$, the  rule $S_0 \to V_iV_j$. But let's first complete the conversion.
replace all other rules into normal form: we take each transition which is not in the correct form and replace it with $N\to V_iV_j$, introducing new non-terminals $V_1, V_2,...$ as needed:

$S\to ab C$ $\Longrightarrow$ $S\to V_1 C$
setting $V_1 \to ab$. The new $V_1$ is not in CNF, but can easily be converted to CNF by re-defining it as $V_1\to AB$ with $A\to a$, $B\to b$.
$S\to babS$ $\Longrightarrow$ $S\to V_2S$ adding $V_2 \to bab$. Now $V_2$ is not in CNF, so we change it to $V_2 \to V_3B$ adding $V_3\to BA$. (skipping a trivial step here)
$S\to de$ is almost CNF. We change it to $S\to DE$ and add $E\to e$, and $D\to d$.
$C\to aCa$ $\Longrightarrow$ $C\to AV_4$ where $V_4 \to CA$.
$C \to b$ is already in CNF.

so we end up with:
$S_0 \to S$
$S\to V_1 C$
$S\to V_2S$
$S\to DE$
$C\to AV_4$
$C \to b$
$V_1 \to AB$
$V_2 \to V_3B$
$V_3 \to BA$
$V_4 \to CA$
and $A\to a$, $B\to b$, $D\to d$, $E\to e$.

Finally, we need to deal with the unit rule $S_0 \to S$. As said, we will replace the $S$ in the right-hand-side with the "content" of S. That is, we remove that unit rule and add instead:
$S_0 \to V_1C \mid V_2S \mid DE$.


What is the definition of Infinitely Often class in complexity

$L\in DTIME\left(2^{n^c}/n^c\right)$ if there exists a machine $M$ running in time $O\left(2^{n^c}/n^c\right)$ which correctly decides membership to $L$ for an infinite number of input lengths, i.e. for every $k\in\mathbb{N}$ there exists $n\ge k$ such that $\forall x\in\{0,1\}^n : M(x)=\mathbb{1}_{x\in L}$. You can think of it as having a non trivial special case where we can decide membership to $L$ (where by non trivial I mean an infinite set of inputs, not just very short ones).


Given directed connected weighted graph, check if d(v) = delta(s,v)

If $d$ indeed represents the length of the shortest path, we must have

$$
d(v)=
\begin{cases}
0, &\text{if $v=s$,}\\
\displaystyle\min_{u:(u,v)\in E}\{d(u)+w(u,v)\}, &\text{otherwise,}
\end{cases}
$$

where $w(u,v)$ is the weight of the edge $(u,v)$.

So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $d$ does not satisfy this property, it cannot represent the length of the shortest path. However, if $d$ does satisfy this property, does it really represent the length of the shortest path? I'll let you figure out this part.

For a further hint:

   Note what you need to prove is that, for all $v$, $d(v)$ is length of the shortest path from $s$ to $v$. Suppose the shortest path from $s$ to $v$ contains $k$ edges, you may try a mathematical induction on $k$.


Distance query in trees with integer edge weights (Constant time, linear space)

Pick an arbitrary node to be the root.  Store in each node its depth (distance from the root).  Also, build a least-common ancestor data structure so you can answer least-common ancestor queries in constant time.

Given two vertices $u,v$, compute their least common ancestor, $a$.  Now the shortest path from $u$ to $v$ goes up from $u$ to $a$, then down to $v$.  You can compute the length of this path as

$$(\text{depth}(u)-\text{depth}(a)) + (\text{depth}(v) - \text{depth}(a)).$$

That's the distance from $u$ to $v$.  Total running time is $O(1)$ time per query.  There exist LCA data structures that use only linear space.


There is a trick to achieve this. Basically you always keep the subset you are currently considering sorted.
subset = [];
function forSubsets(n,k,m=1){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m; i <= n; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}

As you can see on each recursion one element is added to the subset, which is equal or bigger than all previous elements (since the loop starts from m where m is the previously added element). The order for forSubsets(3,2) would be
[1,1]; [1,2]; [1,3]; [2,2]; [2,3]; [3,3];
Of course you have to adapt the implementation to your programming language, but I hope the recursive idea is understandable. yield syntax could also be used to implement this concept in a readable manner (e.g. Python). StackOverflow should be a better place for implementation details. By changing the bounds in the for-loop the you could also draw the subsets from $0,...,n-1$ instead of $1,...,n$.
Just for the sake of completeness: Here is the code for generating subsets without duplicate elements (but no duplicate subsets):
subset = [];
function forSubsets(n,k,m=0){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m+1; i <= n-k+1+subset.length; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}


Let's take a different view angle.

The problem is not really about encoding something like "decimals numbers" 0..127 into base-15 (which is messy). It's about converting a base-127 string into base-15. If you can see it that way, then it's just the same principle as with converting from, say, base-16 (hex) to base-10 (decimal), or base-10 to base-2.


Find number X by asking Hamming distance between X and Y in binary representation

One reasonable heuristic would be to use a greedy algorithm, which at each step picks a query that is likely to reduce the space of possibilities as much as possible.

Suppose you care about the maximum number of questions (worst-case).  Then I suggest the following strategy.  At any point, you have a set $S$ of possible values of $X$ that remain.  For each possible query $Y$ and each possible response $R$ to that query, let $n(Y,R)$ denote how many possibilities of $S$ would remain consistent with the response $R$ to query $Y$.  Define $n(Y) = \max_R n(Y,R)$.  Now, choose the query $Y$ that makes $n(Y)$ as small as possible.  [This is basically Knuth's minimax algorithm.]

Alternatively, suppose you care about the expected number of questions asked (average-case).  Then do the same, except now define $h(Y)$ to be the entropy of a random variable that takes on the value $R$ with probability $n(Y,R) / |S|$.  In other words, define

$$h(Y) = - \sum_R {n(Y,R) \over |S|} \lg {n(Y,R) \over |S|}.$$

Then choose the query $Y$ that minimizes $h(Y)$.

There is no guarantee that these procedures are optimal, but I bet they're pretty good.

Related but not the same: you might also be interested in Ulam's game, a generalization of the game of 20 questions.  Also, take a look at this post, which describes an algorithm for 20 questions based on entropy calculations.


Can one find the minima of a convex function efficiently?

Minimizing a submodular function can be done in polynomial time.  This applies to functions on the discrete hypercube $\{-1,1\}^n$.


Is there a name for complement of recursively enumerable set?

The complement of a recursively enumerable (RE) language is called co-recursively enumerable (co-RE).

As RE and co-RE form the first level of the arithmetic hierarchy, they are also known by aliases $\Sigma_1^0$ and $\Pi_1^0$.


How to calculate the depth of sorting networks?

For selection/bubble sorting network algorithms, the main tricky point is that "some operations are overlapped" or in other words because of pipeling! (it is shown in figure below)
You can find more information in these lecture notes by Rolf Karlsson.

This is the reason why the time complexity is linear!


Are there noncomputable functions with a finite search space?

Depends on what exactly you have in mind.

If the problem is to find an element with decidable (!) properties among a  recursively enumerable set $A$ (of finitely represented elements), then yes: if $A$ is finite, the problem is trivially computable. Just check every element.

If $A$ is finite but unknown, it's more interesting but still: the problem is computable, since there is an algorithm that checks the every element in $A$, even though we can't point it out. See this for an example.

If the identifying property is undecidable, then the problem may be¹ uncomputable. For instance, the search space for the question "Does TM M halt on input x?" is finite -- just two possible answers -- but the problem is (in)famously undecidable.

It's possible that the property as written down is not needed to identify the correct element.


Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree

You are asking two different questions:

What are the $2^{n_d} \binom{n_d}{m}$-many codimension $m$ neighbors of a given node?
Given a description of a neighbor, how to locate it?

Regarding the first question, a neighbor of codimension $m$ is given by (1) a subset $S$ of the coordinates of size $m$, (2) for each $x \in S$, a direction $d_x \in \{-1,+1\}$. The address of a neighbor is obtined by adding $d_x$ to coordinate $x$.

Regarding the second question, the simplest algorithm would consist of the following steps:

Find the address of the node by traversing the tree up.
Find the address of the neighbor. This part is described above.
Find the neighbor by traversing the tree down.

These steps are straightforward generalizations of the algorithm described in the link.


Can non-recursively enumerable languages be solved with dovetailing?

Dovetailing is just a technique for programming Turing machines. It doesn't give Turing machines any additional power. In particular, dovetailing cannot cause a Turing machine to decide an undecidable problem, recognize an unrecognizable language, and so on.

While dovetailing might seem like an arcane technique, it is actually very similar to context-switching, which enables our computers to run many programs in parallel. This doesn't give our computers any more power – on the contrary, context-switching incurs overheads.


Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

Let me try to sketch a method that counts the triplets by directly counting. Let me first assume that $a$ is sorted. I will also keep $x$ constant for this exposition (and iterate over $x$). For simplicity take $a[x]=0$, so the task is to count $(y,z)$ such that $a[y]+a[z]<0$. We can count the pairs, but not by going over all $n^2$ of them, but by following the "boundary" between negative and positive pairs. This is like counting the number of negative elements in a two dimensional array that is increasing in both dimensions. This seems to be possible in linear time? (for fixed $x$)

As an example we consider the following virtual two-dimensional array; i.e., it is not explicitly constructed, element $(y,z)$ just is $a[y]+a[z]$. We can count the elements $a[y]+a[z]>9$ by "walking" along the "boundary".

$\begin{array}{c|ccccc}
a & 1 & 3 & 4 & 7 & 8 \\\hline
1 & 2 & 4 & 5 & 8 & 9 \\
3 & 4 & 6 & 7 & \color{green}{10}& \color{green}{11}\\
4 & 5 & 7 & 8 & \color{green}{11}& \color{green}{12}\\
7 & 8 & \color{green}{10}& \color{green}{11}& \color{green}{14}& \color{green}{15}\\
8 & 9 & \color{green}{11}& \color{green}{12}& \color{green}{15}& \color{green}{16}
\end{array}$


Reduction from Partition problem to 3-Partition problem

To answer your bolded question: The sum of the numbers in $Y$ is $\frac{3m}2$. Thus $A$, $B$, and $C$ each need to be of size $\frac m2$. This can only be achieved by partioning as in the first direction.

Regarding your second question: You can not be sure that $\frac m2$ is an integer and you have to pay attention to it, in order to get a formally correct reduction.

The easiest way to address this is by having your reduction function distinguish two cases: If $\frac m2$ is an integer, it proceeds as you describe. If $\frac m2$ is not an integer, it exploits the fact that in this case the answer to the original question ("Can $X$ be partitioned?") is easy. I'll leave it as an exercise to figure out the details of this case.


A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $

I may be wrong, but it seems to me that the function defined by:
$f(n) = \left\{\begin{array}{rl}1 & \text{if }n=1\\2^{2^{\left\lfloor \log_2\log_2 n \right\rfloor+1}}&\text{otherwise}\end{array}\right.$
satisfy the conditions.
To explain why, the values taken by $f(n)$ will be $1, 4, 4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 256, 256, …$
The idea is that when $n=2^{2^k}$, then $f(n) = 2^{2^{k+1}} = n^2$, and when $n=2^{2^k}-1$, then $f(n) = 2^{2^{k}} = n +1$. That way, you will guarantee the 5 conditions: $(O(n^2) \setminus o(n^2)) \cap (\Omega(n) \setminus \omega(n))$ and increasing.


Why is C's void type not analogous to the empty/bottom type?

In C, void is used for multiple unrelated things. Depending on what it's used for, its meaning may be a unit type, an empty type, or something else.

When void is used by itself (as opposed to void*, a pointer to void), it's a unit type, i.e. a type with a single value. Functions that return void are said to “return nothing”, but what this really means is that they don't return any information. They return $0$ bits of information, which means that they return a value of a type that contains $2^0 = 1$ distinct values, i.e. a unit type.

This is not an empty type: a function that returns an empty type cannot return a value, since there is no value of that type. A function whose return type is empty can only loop forever, or abort the program, or raise an exception (longjmp) (or otherwise arrange not to return, e.g. by transferring control to another thread or process using functionality beyond standard C). To keep things confusing, it is conventional in C to use void in lieu of an empty type (C doesn't have an empty type).

The void type requires $0$ bits of storage. Because C insists on every object occupying a whole, nonzero number of bytes of storage, it's forbidden to create an object of type void, and there's a special syntax to return the void value (a return statement with the value omitted). There's no syntax that yields the value of type void, but that value is there whenever a function whose return type is void returns.

C does not have a bottom type in the sense of allowing any possible type. Even incomplete types specify the general nature of its values, e.g. pointers or structs or unions or functions. But void* is a pointer to any non-function type: it's the least element of the algebra of object pointer types, i.e. it's the bottom object pointer type. Unlike the general case of T* where T is some non-void type, void* is not the type of pointers to a value of type void, but the type of pointers to a value of unspecified type.


Possible to construct a probabilistic halting problem solver?

It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for every input. Second, the algorithm succeeds on a certain fraction of inputs.

For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but effectively) using deterministic computation, by trying all possible coin tosses.

For the second interpretation, we will have to work a bit harder. Suppose that your algorithm is guaranteed to work with an asymptotic success probability of $2/3$. That means that the fraction of inputs in $[1,N]$ for which it gives the correct answer is some $p_N \to 2/3$. Now suppose you're interested in a certain program $P$. It seems that under a reasonable encoding of programs, you would be able to come up with a long stretch $[M,10M]$ (say) of programs equivalent to $P$. By taking $M$ large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs, you will be able to ascertain whether $P$ halts or not. This rules out even this interpretation of a "probabilistic" algorithm.


How to properly solve T(n) = T(n-1) + O(2^n)?

What you did is fine for most purposes. If you want a really rigorous proof without "dot dot dots," then you need to use induction. For that you need to make the constant in big-Oh explicit, and use your "back of the envelope calculation" to come up with the induction hypothesis.


Let $Q$ be the set of states in a DFA $D$ for $R$. We replace $\Gamma$ with $\Gamma \times Q$, and update the PDA so that the stack contains, apart from the original stack symbols, also the state that $D$ is in after reading the current word on the stack. The PDA only allows transitions if the element at the top of the stack corresponds to an accepting state of $D$, and also checks this condition at the very end.


Expressing unsigned comparison through signed comparison of 2's complement

It's even a bit simpler, namely both:

a <u b == (a ^ m) <s (b ^ m), and,
a <s b == (a ^ m) <u (b ^ m)

Where m is the mask with the sign bit set.

I don't have a formal proof for that, but the image below shows what is happening. The top row shows the "unsigned order" of the number line, chopped in half, with the first part having a 0 in the top bit and the second half having a 1 in the top bit. The bottom row shows the same sub-ranges but in the "signed order". The bottom block in the signed case is the same block as the top block in the unsigned case. Notice that the signed and unsigned order of the two sub-ranges is swapped, but the order within the sub-ranges is the same.

XORing by m is equivalent to adding m and to subtracting m, so you may think of it as:

swapping the order of the two sub-ranges (xor)
pushing the two sub-ranges to the right (by the width of a block), with wrap-around to the left side (addition)
pushing the two sub-ranges to the left, with wrap-around to the right side (subtraction)

In any case the order of the blocks is swapped, so it swaps between the signed order and the unsigned order.


Complexity of Longest Palindromic Subsequence Algorithm

The dynamic programming approach is indeed O(n^2).
However, the recursive solution is exponential in n: any time two characters don't match, a subproblem of size k is converted into 2 subproblems of size k-1 each.
It's easy to see that, with all letters different, this produces a complexity of O(2^n).

Here is the example from the page you mention, modified to count and output the number of calls.
A local copy to prevent link rot:

#include <stdio.h>
#include <string.h>

int max (int x, int y) {return (x > y) ? x : y;}

int count;

int lps (char * seq, int i, int j)
{
   count += 1;
   if (i == j)
      return 1;
   if (seq[i] == seq[j] && i + 1 == j)
      return 2;
   if (seq[i] == seq[j])
      return lps (seq, i + 1, j - 1) + 2;
   return max (lps (seq, i, j - 1), lps(seq, i + 1, j));
}

int main ()
{
    char seq [] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int n = 1; n <= 26; n++)
    {
       count = 0;
       printf ("n = %d: answer = %d", n, lps (seq, 0, n - 1));
       printf (", count = %d\n", count);
    }
    return 0;
}

The output is:

n = 1: answer = 1, count = 1
n = 2: answer = 1, count = 3
n = 3: answer = 1, count = 7
n = 4: answer = 1, count = 15
n = 5: answer = 1, count = 31
...
n = 24: answer = 1, count = 16777215
n = 25: answer = 1, count = 33554431
n = 26: answer = 1, count = 67108863


I can't think of any counter-example for (i) right now. But (ii) and (iii) are true due to the Immerman–Szelepcsényi theorem[1], according to which $\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))$ for all $s(n) \geq \log(n)$.

[1]: Wikipedia - Immerman–Szelepcsényi theorem


Largest reported speedup for a parallel computation?

John Gustafson observed and reported speedups in excess of 1024 on early 80's supercomputers; this led him to the concept of scaled speedup (Gustafson-Barsis law), in contrast to the pessimistic Amdahl-Ware law.

Right now, in the era of multicore parallel supercomputers equipped with hundreds of thousands or millions of cores, performances are more commonly reported in terms of petaflops and efficiency. For instance, the winners of the last Gordon Bell prize at the Supercomputing 2012 conference, established the current world record for an astrophysical N-body simulation of one trillion particles performed on the full K computer, which appears to be number 4 in the June 2013 top 500 list. They reported 4.45 petaflops on 663,552 cores (the K computer was equipped with 82944 8-core processors in November 2012), and an efficiency (the ratio speedup/cores) of 42%. Translated in terms of speedup, that means a speedup of about 278,691.


What is the meaning of max() in intro. to algorithms?

Yes, as confirmed by Gokul, $\max(p,q)$ just means the larger one of its two parameters, $p$ and $q$. It can also apply to more parameters such as $\max(p, q, r, s, t)$, where it means the largest of all 5 variables or values.

Its opposite is $\min$, which is used in the same way but means the smaller one of two values or the smallest one of all given values.

You might want to check the list of mathematical abbreviations the next time you get confused by some math abbreviations.


Efficient way to calculate sum in sliding window?

One possible way would be to store the sum of all the submatrices of the form $((0,0),(i,j))$. You can compute each of these sums in $O(1)$ time per entry (by using the previous entries).

If you then want to know the sum of the submatrix $((x,y),(i,j))$, you can compute this in $O(1)$ from the stored sums using inclusion-exclusion. If we let $S$ denote such a sum, then

$$S((x,y),(i,j))=S((0,0),(i,j))-S((0,0),(x,j))-S((0,0),(i,y))+S((0,0),(x,y))$$


Finding exact corner solutions to linear programming using interior point methods

You might want to read the paper:

  Sanjay Mehrotra, On finding a vertex solution using interior point methods, Linear Algebra and its Applications, Volume 152, 1 July 1991, Pages 233-253, ISSN 0024-3795, 10.1016/0024-3795(91)90277-4. sciencedirect article link


Status on Naoki Katoh's "Rectangle Wiring Problem" (minimum length tree to cover a partitioned rectangle)?

This problem has been studied since 2002, under the name minimum-length corridor problem.

The problem is known to be NP-complete[1,2], but there is a constant factor polynomial time approximation algorithm[3].

There is more work on this problem, which you can find by searching the citation network of the papers below.

[1]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Complexity of the minimum-length corridor problem. Computational Geometry, 2007, 37.2: 72-103.

[2]: BODLAENDER, Hans L., et al. On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry, 2009, 42.9: 939-951.

[3]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Approximation Algorithms for the Minimum-Length Corridor and Related Problems. In: CCCG. 2007. p. 253-256.


Distribution of cycles length in a graph

When $k = n$ and self-loops are allowed, what you have is a random permutation. The expected length of the longest cycle in a permutation is known to be $\alpha n$ for $\alpha \approx 0.624$, see Shepp and Lloyd. If self-loops are not allowed then you will get a different constant $\beta$ that can probably be computed using the methods of Shepp and Lloyd.

When $k < n$, you just get a permutation on $k$ vertices, so instead of $\alpha n$ or $\beta n$ you would get $\alpha k$ or $\beta k$.


Hash functions and pathological data sets

An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ typically has massive size). Since $|U| >> n$, all of the elements of $U$ do not fit into the hash table; therefore, there will be collisions. Consider, for example, the universal set $U=\{a,b,c,d,e,f,g\}$ and a hash table with $n=3$ buckets. Since $|U|=7$, at least one bucket must necessarily contain $\lceil \: |U| \: / \: n \rceil = \lceil 7/3 \rceil = 3$ or more elements. In the case of the most clever hash function (which would spread out the elements of $U$ as evenly as possible), this bucket would contain exactly $3$ elements, like this (highlighted in red):

It is important to see that no matter how clever the hash function is, there will always exist a data set (for example, the set $\{b,g,a\}$) whose elements hash to the same bucket (for example, bucket number $1$). Such a pathological data set will make your hash table degenerate to its worst-case linear-time performance.


Ok, I think here is how it should look like. You duplicate the graph G as many times as many v places you have to visit (e.g. v0, v1, v2). The order you must visit these vertices is the constraint which is expressed as zero weight edges (G1.v0 -> G2.v0, G2.v1 -> G3.v1).


Is physical pages zeroed out before it's mapped to a virtual page?

Yes, the kernel zeroes out pages before allocating them to a user-level process.  The details depend on the specific operating system; some may zero it out when the page is needed, others might run a separate thread that periodically zeroes out pages in anticipation that they'll be allocated.


This method works in linear time, because end - start decreases by 1 on each iteration. It's $n - 1$ initially, hence the loop will make at most $n - 1$ iterations.


How can I fill bookcases with shelves of books using the least number of bookcases?

I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below.

Multiple bookcases

If you have multiple bookcases, and you need to put each shelf into exactly one of the bookcases, then you have an instance of the bin packing problem.

Each shelf corresponds to an item, and each bookcase corresponds to a bin. Now you want to find a way to put each item into one bin, i.e., put each shelf into one bookcase, so that every shelf is in some bookcase, and each bookcase has room for all the shelves that will go into it.

This can be modelled in a straightforward way as a bin packing problem:

The "size" of a shelf (an item) is the height of the shelf.
The "size" of a bookcase (i.e., of a bin) is the height of the bookcase.

Now you want to find a way to assign each shelf to one of the bookcases, so that the sum of the sizes (heights) of the shelves in each bookcase does not exceed the size (height) of the bookcase.  That is exactly the bin packing problem.

You should be able to use any standard algorithm for bin packing to solve your problem.  Given the number of bookcases and shelves you're likely to have in practice, any of them should be efficient enough for practical use.  For instance, one approach is to formulate this as an instance of ILP (integer linear programming), as described in the Wikipedia article on bin packing, and then solve the problem using an off-the-shelf ILP solver, such as lp_solve or CPLEX.  This will likely be very effective in practice.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into each bookcase, and then for each bookcase, find the tallest of the shelves that are going into that bookcase and put it at the top of the bookcase.

One bookcase

If you have one bookcase, and you can select some subset of the shelves to fill the bookcase, your problem is an instance of the knapsack problem.

Treat each shelf as an item that can be placed into the knapsack.  Then:

the "weight" of a shelf is its height,
the "value" of a shelf is the value of including that shelf in the bookcase (e.g., the number of books it'll enable you to store, or maybe just a fixed value that's the same for all shelves), and
the "capacity" of the knapsack is the total height of the bookcase.

The optimal solution to the knapsack problem will select a subset of items whose total weight doesn't exceed the knapsack's capacity, and that maximizes the sum of the values of the selected items.

In your context, that amounts to selecting a subset of the shelves whose total height doesn't exceed the height of the bookcase (and thus it'll be possible to fit all of the selected shelves into your bookcase), and that maximizes the sum of the values of the shelves (e.g., maximizes the total number of shelves that you fit into the bookcase, or the total number of books you can store in the bookcase, etc.).

There are many algorithms for the knapsack problem, such as the dynamic programming algorithm.  In your situation, I suspect the number of candidate shelves is small enough that any of these algorithms is likely to be efficient enough for real-world use.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into the bookcase, and then choose the one that is tallest and put it at the top of the bookcase.


A* 8-puzzle problem worst case memory usage

Since the number of possible positions is quite low when N = 3 (9! / 2 = 181,400), you can do an exhaustive search to find the worst case. Check the result, and maybe it leads to some insight.


For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is:

$$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$

explanation:
suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n_2-n_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$


Construct binary palindrome by repeated appending and trimming

I suspect that when n is not a mutiple of k then you may not get the desired wrapping effect.

In particular, let me interpret "after every k places from the start" as "the (k+1)th position in the array" - assuming 1-based indexing. Then in the given example on that page, with k = 4 and n = 10, your algorithm produces 1 0 0 0 1 1 0 0 0 1 - which is not a 4-length binary string being repeated and wrapped off at the end (the right answer would be 1 1 0 0 1 1 0 0 1 1.

If I am off-by-one on interpreting "k places from the start" (so say you were refering to the kth position), then even with n = 5 and k = 3 we get 1 0 1 0 1, whereas the right answer would be 1 1 0 1 1.


Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

My answer is just a hint. The following pattern should lead you to the right answer:

These strings belong to the language:
$w = 11 \Rightarrow 1^1\epsilon 1^1, n=1$
$w = 1011 \Rightarrow 1^1(01) 1^1, n=1$
$w = 11011 \Rightarrow 1^1(101) 1^1, n=1$ or $1^2(101) 1^2, n=2$
$w = 1001011 \Rightarrow 1^1(00101) 1^1, n=1$
$w = 11111 \Rightarrow 1^1(111) 1^1, n=1$ or $1^2(1) 1^2, n=2$
$w = 101010011 \Rightarrow 1^1 (0101001) 1^1, n=1$
$\cdots$
Finally, if $w=1^nw 1^n$ then it can be written as $1v1$, where $w,v \in (0+1)^*$.

These strings DO NOT belong to the language:
$w=0$
$w=01$
$w=100$
$w=0000$
$w=0001$
$w=1000010$
$\cdots$

Yo may want to look at the first and the last symbols of each string.


Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken

Don't be so quick to reject your approach!  Your approach is a great solution.  On a $15\times 15$ grid, you'll only have to try 225 different options.  Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds.

As Knuth supposedly said once, "premature optimization is the root of all evil". My advice: Try that solution, implement, and measure its performance, before you even consider anything else.


Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

The way i see it, talking about slowdowns on simulations of a specific Turing machine $M_0$ doesn't make much sense. I could always just run $M_0$ and call this a simulation, which will result in no slowdown. I could also hardwire the code of $M_0$ , and in case the input was $M_0$, use some better algorithm (as D.W. did in his answer).

The more interesting question here is (in my opinion at least), what is the optimal slowdown achievable when simulating an arbitrary Turing machine $M$ on some input $x$ ? (asymptotically, in terms of $|x|$ and the length of the description of $M$)

We look at all possible inputs, and examine the worst case slowdown (perhaps for some machine $M_0$ you can do a better job, but here we consider the worst case running time).

More formally, Let $\mathcal{U}(\langle M\rangle,x)$ denote the universal Turing machine, which takes as input an encoding of a machine $M$ and some string $x$, and outputs $M(x)$, or does not halt in the case that the computation of $M$ on $x$ does not halt. We know that we can implement $\mathcal{U}$ in such a way that if the computation $M(x)$ requires time $T$, then $\mathcal{U}(\langle M\rangle,x)$ requires time $O\left(T\log T\right)$. Here the $O$ notation hides constants which depend on the number of states and the alphabet size of $M$ (but independent of $|x|$). Your question then translates to whether we can implement $\mathcal{U}$ such that the computation of $\mathcal{U}(\langle M\rangle,x)$  requires only $O(T)$ time?

It seems that for single tape machines, it is not known whether this $\log T$ factor is necessary, however for $k\ge 2$ tapes machines we can avoid it (proved by Furer, 1982). See this post by Kaveh for a detailed discussion and related quotes.


Preparing precedence graph from fork and join code

x=2;
y=2;
z=2;

p1;

Fork L1  ; start p2

Fork L2 ; start p3

goto L3 ; stat P4

L1: p2;

fork L3 ;start p4;

goto L5

L3: join (x)

P4;

L4:  join(y)

s6;

Quit();

L2 : P3;

L5:  join(y)

 P5;

 goto L4


Here's an intuitive explanation:
It follows essentially from the nature of LL(1) parsers: LL(1) parsers build a LL(1) parsing table. The rows of the table are nonterminals, and the columns are terminals. We can think about LL(1) parsing as doing LL(1) table lookups upon encountering each symbol in the input: we look at the entry determined by the current nonterminal and the input terminal, and apply a corresponding production rule. Thus, the LL(1) table cannot contain multiple production rules at each entry, otherwise, the parser cannot decide which rule to apply.
If the right hand side of a production $\alpha$, $\beta$ have intersecting FIRST sets, then we'd have multiple rules at a single entry in the LL(1) table (i.e. duplicate/conflicting entries) --- having nontrivial intersection of FIRST sets essentially prevents us from constructing the LL(1) parsing table.
If you're still unclear about why this condition is necessary, I suggest you construct an example with intersecting FIRST sets on the right hand side of a production, and then try to manually construct an LL(1) parsing table or use one of the online visualization tools; you'll immediately find a conflict.


Modified Linear Bounded Automata Language

any location except i/p part means

(total unbounded tape area - tape area that includes i/p string)

= (infinity length - finite length) as we know i/p string length is always finite

= infinity length

in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can be used is of infinite length which is obviously not a function of the input string length.So it acts as a turing machine.


Counting sort on non-integers - why not possible?

If you naively apply the algorithm you need an encoding $f$ of strings of length $m$ into integers such that $s_1≤s_2$ iff $f(s_1)≤f(s_2)$. The bound on these integers is necessarily at least $c^m$ where $c$ is the number of possible characters.

You then have a complexity in $O(nc^m)$ where $n$ is the number of elements to be sorted. This could be interesting when $c^m$ is not too big compared to the usual bound $\log n$, which is possible, in very peculiar cases.

In general, one would prefer the bound $O(n\log n)$ which does not depend on the length of your strings and in general much faster than $O(nc^m)$. To give a formal comparison between them, the former would be $O(s\log s)$ and the latter $O(sc^s)$ where $s$ is the size of the input.

However what is possible if you know that you will have a number of different strings no greater than some $k$, and that there will be a lot of occurrences of the same strings, is to build a correspondence between these strings and $\{1,\dots,k\}$ on which you will apply the counting sort, thus obtaining a complexity of $O(kn)$ i.e. linear (since $k$ is constant). But in this case the counting sort is not the only one reaching a linear complexity, for example all algorithms using balanced trees can be adapted to be linear, even insertion sort which is quadratic in the worst case, becomes linear.


Construct DFA accepting strings ending with '110' or '101'

There cannot be a single final state. Consider any DFA for the language, and let $\sigma_{110},\sigma_{101}$ be its states after reading $110,101$ (respectively). Clearly $\sigma_{110},\sigma_{101}$ are accepting states. Moreover, they cannot be the same state since $1101$ is in the language but $1011$ is not.


Solving diophantine equations -- does having a bound on the size of the solution help?

No.

If I follow you correctly, your argument is that if P=NP, then $\mathrm{RH}10\in \mathrm{P}$ and the same procedure would be a valid algorithm for $\mathrm{H}10$, which contradicts with the fact that $\mathrm{H}10$ is undecidable.

The step that lacks proof is the claim that the implication:

  if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

To see that this claim doesn't follow, consider what a polynomial algorithm to solve $\mathrm{RH}10$ could be doing. We only know it lies in P somehow, so let's assume it runs in $O(n^k)$ time for some $k\in\mathbb{N}$. Let $l$ be such that we can verify whether a value is a solution for a Diophantine equation with $n$ variables in $O(n^l)$ time.

It is possible that this is done by the following algorithm $A$, given an instance $I$ of $\mathrm{RH}10$:

Identify a set $S\subseteq [-2^n,2^n]^n$ of size $O(n^{k-l})$ in $O(n^k)$ time such that $s$ is a solution to the Diophantine equation encoded in $I$ if and only if $s\in S$.
Iterate over all elements in $s\in S$ and test whether it is a solution of $I$. If a solution is found, report that $I$ has a solution, otherwise report it has not.

Observe that this is a valid algorithm to solve $\mathrm{RH}10$ in $O(n^k)$ if and only if there exist a procedure to carry out step 1. We don't know whether this is true, it is unlikely, but we don't know so it is at least possible.

Now, does the existence of algorithm $A$ give us a procedure to decide $\mathrm{H}10$? No. Algorithm $A$ requires that the solution values are restricted to some finite subset of $\mathbb{Z}^n$ to work. This is true even if we only use step 1. I hope it is clear that the existence of algorithm $A$ brings us no closer to deciding $\mathrm{H}10$.

Therefore, it is clear that the claim that

  if $\mathrm{RH}10$ in P, then $\mathrm{H}10$ must necessarily be decidable

is not motivated, as the possibility of the existence of algorithm $A$ is not dis-proven, while we have seen that the existence of algorithm $A$ contradicts your claim.


Minimum perfect matching with uneven vertices?

A perfect matching is one that includes every vertex so only graphs with an even number of vertices can have a perfect matching. If the number of vertices is odd, there is simply no perfect matching.


How to index a tree to allow efficient search for paths?

Root the tree in an arbitrary fashion. Given two nodes $x,y$, let $x_0 = x, x_1, \ldots$ and $y_0 = y, y_1, \ldots$ be the paths going up the tree all the way to the root. If $x_i = y_j$ then the unique path between $x$ and $y$ is $x_0,\ldots,x_i=y_j,\ldots,y_0$.
In order to find this path quickly (at the cost of a little bit of memory), generate the two paths in parallel, $x_0,y_0,x_1,y_1,x_2,y_2,\ldots$, storing the resulting vertices in a hash table, until they collide. This happens at time $\max(i,j)$, which is the same as the path length $i+j$ up to constant factors.

While the description above suggests that you have to store the entire tree ahead of time, this is not necessarily the case. In general, all you need to do is to have a consistent way of determining which of the neighbors of a given vertex is its parent. Whether this is possible without storing the entire tree depends on the problem. When it is possible, you can generate the tree "as you go", which prompts us to reduce the space complexity of the algorithm (perhaps you don't need to store the path from $x$ to $y$, but only to generate it vertex by vertex).

If space is at premium, you can save a factor of $k$ by storing only a $k$'th fraction of the vertices. Say that a vertex is ($k$-)special if the hash of its index is divisible by $k$. Perform the search as above, but only store special vertices. On average, this will cut the number of vertices stored by a factor of $k$. However, it doesn't give you the exact intersection point. Suppose that your sequences contain the special points $x_{i_1},\ldots,x_{i_a}$ and $y_{j_1},\ldots,y_{j_b}$, where $x_{i_a} = x_{j_b}$. To find the exact intersection point, it suffices to consider the small parts $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$.
If space is still at premium, you can use exponential search followed by binary search. We go over $k=1,2,4,8,\ldots$, and for each value of $k$, determine only the first $k$-special vertex after the initial vertices $x,y$. Suppose that for some $k$, these special vertices coincide. Now generate the sequence of $k/2$-special vertices, until they coincide. Let $x_{i_a}=y_{j_b}$ be the first time these sequences coincide. Then we can narrow the search down to $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$. Now we generate the sequence of $k/4$-special vertices, starting at $x_{i_{a-1}+1},y_{j_{b-1}+1}$ (unless these vertices are the same, in which case we are done); and so on. The running time is still linear, but the space requirements is down nearly to a constant (in expectation).
We can get the space down to a deterministic constant by defining special in terms of the depth of a vertex rather than in terms of its index, but depth is not necessarily easy to compute.


Is it decidable whether a Turing machine modifies the tape, on a particular input?

Yes, this is decidable.  Here are two different proofs of that fact.

A counting proof

Define a configuration to be the state of the tape, the location of $M$'s head, the state that $M$'s finite control is in, and whether or not $M$ has written to the tape yet.  Note that for a fixed $w$, if $M$ does not modify the tape on input $w$, there are only finitely many possible configurations, let's say $N$ of them.  $N$ can be easily computed; it is about $2 \times (\text{len}(w) + 2|M|) \times |M|$ where $|M|$ is the number of states in $M$'s finite control.  (See footnote *.)

So, run $M$ on input $w$ and keep track of all the configurations it enters.  One of three things must happen:

After at most $N$ steps, $M$ modifies the tape.  In that case you know $\langle M,w \rangle \notin L$ and there's no need to keep simulating $M$.
After at most $N$ steps, $M$ halts without ever modifying the tape.  In that case you know $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.
After at most $N$ steps, $M$ repeats some prior configuration without ever modifying the tape and thus enters a cycle.  In that case you know $M$ will loop forever on input $w$, without modifying the tape, so $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.

Thus, after simulating $M$ for $N$ steps, we learn whether $M$ will ever modify the tape on input $w$.

Footnote *: In this proof I will consider as equivalent all configurations where the head is more than $|M|$ cells to the right of the input and that differ only in the location of $M$'s head, and I consider as equivalent all configurations where the head is more than $|M|$ cells to the left of the input and that differ only in the location of $M$'s head.  Why?  If it ever reaches one of those configurations without modifying the tape, then it will loop forever without modifying the tape.  This follows by a pigeonhole argument; the finite control can't count higher than $|M|$, i.e., if it reaches one of those configurations, then some state of the finite control must have repeated during the time when it's wholly to the right/left of the input, so it has entered a loop.

A conceptual proof

For a given $w$, if $M$ doesn't write to the tape, it is equivalent to a two-way deterministic finite automaton (2DFA).  So, you can write down a 2DFA with the following three properties:

The DFA has a single accepting state $q_a$, with a self-loop (once it accepts, it stays accepting forever).  All other states are non-accepting.
If $M$ never writes to the tape on input $w$, the behavior of the 2DFA on input $w$ is equivalent to the behavior of $M$, and the 2DFA never transitions to the special accept state $q_a$ and never accepts.
If $M$ does write to the tape on input $w$ at some point, the behavior of the 2DFA is equivalent up until the point $M$ first writes to the tape; thereafter the 2DFA follows a transition to the special accept state $q_a$ and thus accepts.

How do we build such a 2DFA?  The 2DFA is just a copy of the finite control of $M$ (which is a finite automaton), except that it moves to $q_a$ whenever $M$'s finite control would modify the tape:

If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition doesn't write anything, then the 2DFA has the same transition.
If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition does write to the tape, the 2DFA has a transition $q_i \to q_a$ on symbol $i$.

Now the question just becomes: given a 2DFA, does it accept on input $w$?  This is decidable, as every 2DFA is equivalent to a (possibly exponentially larger) ordinary DFA.

Comparison of proofs

Either proof suffices to show that $L$ is decidable.  The counting proof has the advantage of not requiring fancy machinery like 2DFA.  The conceptual proof shows both that $L$ is decidable and something stronger: if we restrict attention to a single fixed $M$, then the set of $w$ such that $\langle M,w \rangle \in L$ is in fact a regular language (since 2DFA are equivalent in power to DFAs).  Pretty nifty!


Coding Theory Optimal Code with given max length

So first, some terminology.

A uniquely decodable code is a code where every string has at most one decoding.

A prefix code is a code where no code word is a prefix of any other. This is an interesting property because it means that the system is uniquely decodable without using lookahead.

A uniquely decodable code is optimal if it has minimal average code word length.

An optimal prefix code is, just as the name suggest, a prefix code that is also optimal.

The main result that you should know about uniquely decodable codes is the Kraft-McMillan inequality. It states that if you have an alphabet of size $r$ ($r=2$ if the codes are binary), and a uniquely decodable code with code word lengths $l_1, l_2, \ldots, l_n$, then:

$$\sum_i r^{-l_i} \le 1$$

And, conversely, for any code word lengths that satisfy the above inequality, there exists a prefix code with the same code word lengths.

Taken together, this means that for every uniquely decodable code, there is an equivalent prefix code.

I'm going to suggest looking at the link above, and work through the proofs. This should give you the head start that you need.

One of the questions that you asked, whether the two maximum-length code words differ only in the prefix, is true for optimal prefix codes, but doesn't have to be true for uniquely decodable codes in general. But as noted, for every uniquely decodable code, there is an equivalent prefix code.


Probability of loss using a binary symmetric channel

R3 encoding is a pair of algorithms:

Encoding: a bit $b \in \{0,1\}$ is encoded as the packet $bbb$.
Decoding: a packet $xyz \in \{0,1\}^3$ is decoded as the majority bit (the bit occurring most often).

Since the situation is symmetric, in order to understand the transmission error, it suffices to consider the case $b = 0$. Suppose we encode the bit $0$. So we transmit the packet $000$. Every bit is flipped with probability $p$, and this gives us a distribution on the received packet $xyz$. Finally, a transmission error occurs if $xyz$ is decoded as $1$, that is, if the majority of $xyz$ is $1$.
Therefore, the transmission error is the probability of the following event:

If $x,y,z \in \{0,1\}$ are independent identically distributed bits such that $\Pr[x=1] = p$, what is the probability that the majority of bits in $x,y,z$ is $1$?

You can compute this probability by brute force.


Showing that minimal vertex deletion to a bipartite graph is NP-complete

Your problem is a special case of a broader class of problems named node-deletion problems:

J. M. Lewis and M. Yannakakis, "The node-deletion problem for hereditary properties is NP-complete"

... This paper deals with the class of graph problems defined as follows:
for a fixed graph property $\Pi$, find the minimum number of nodes (or vertices) which must be deleted from a given graph $G$ so that the result satisfies $\Pi$. We call this the node-deletion problem for $\Pi$. Our results show that if $\Pi$ is a nontrivial property which is hereditary on induced subgraph, then the node-deletion problem for $\Pi$ is NP-hard. Furthermore, if we add the condition that testing for $\Pi$ can be performed in polynomial time, then our results imply that the node-deletion problem for $\Pi$ is NP-complete. ...

Your problem is the node deletion problem for bipartiteness, but (as noted by Pal), it is known today as the Odd cycle traversal (OCT) problem.

EDIT

For what regards a direct reduction, I thought of this one from 3SAT.

Given an instance of 3SAT with $n$ variables and $m$ clauses, build the following graph: add two nodes $x_i, \overline{x_i}$ for each variable and an edge between them. To simulate a truth assignment, add $n+1$ nodes for each variable $x_i$ and connect them both to $x_i$ and $\overline{x_i}$; in this way, in order to make a bipartite graph deleting at most $n$ nodes, at least one between $x_i$ and $\overline{x_i}$ must be deleted . Finally for each clause $C_j$ add 4 nodes and build an odd cycle that connects the variables in $C_j$.

The resulting graph $G$ can be made bipartite deleting at most $n$ nodes if and only if the original 3SAT formula is satisfiable.


Queue, moving the element at the tail to the head

If you can only push (enqueue) or pull (dequeue) from the queue, then your only option is to pull all the elements and re-enter them.

If you need such an operation, you can use deque (double-ended queue). See: http://en.wikipedia.org/wiki/Double-ended_queue .


Computation Tree Logic and its Temporal Opeators

First, a small comment - the $F$ operator comes from the word "future", rather than "finally", although it is indeed very tempting to say "finally".

The semantics of $Fq$ with respect to a computation $\pi$ is:
$$\pi\models Fq \iff \exists i\ge 0, \pi^i \models q$$
Thus, the 0th suffix is also considered, so if $q$ hold immediately, the formula is still satisfied.
Observe that you can capture the notion of "strict future" with the formula $XFq$.
The formula states that along every path ($A$), every state $s$ satisfies ($G$) the following: if $q$ and $r$ are true in $s$, then in every path starting from $s$, $q$ eventually appears.

I think this is what you meant in your second option.


Find the longest repeated pattern in a string

The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its length $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running pointers at a distance of $\ell$. In this way, one can verify whether a square of length $2\ell$ exists in linear time, giving a total running time of $O(n^2)$.

Kolpakov and Kucherov developed an algorithm for finding all maximal repeats in a word in time $O(n)$ [1], and their algorithm can be used to find all maximal squares in time $O(n)$. A repeat is a subword of the form $w^kx$, where $k \geq 2$ and $x$ is a proper prefix of $w$. The largest square contained in that repeat is $(w^{\lfloor k/2 \rfloor})^2$. Using this formula, given all maximal repeats in a word (of which there are only $O(n)$ many), one can find the largest square.

[1] Kolpakov, R., & Kucherov, G. (1999). Finding maximal repetitions in a word in linear time. In Foundations of Computer Science, 1999. 40th Annual Symposium on (pp. 596-604). IEEE.


Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four.

I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can actually read the following:

"In September 1988, James Allen determined the game-theoretic value through a brute-force search (Allen, 1998): a win for the player to move first. A few weeks later, in October 1988, connect-four was solved through a knowledge-based approach, resulting in the tournament program VICTOR (Allis, 1988; Uiterwijk et al., 1989a; Uiterwijk et al., 1989b). Recently John Tromp has calculated the game-theoretic value for all 8-ply connect-four positions (Tromp, 1993)."

You will find all the bibliographical references in the Bibliography chapter of the PhD in case you need further information. Of these, the most relevant to your case is Allis (1998). A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins. M.Sc. Thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam. Go to Chapter 6 and you'll discover that this game can be optimally solved just by considering a number of rules. And this take almost no time!

So, my first suggestion would be for you to consider none of the approaches you mention but a knowledge-based approach instead. From what I remember when I studied these works, most of these rules should be easy to generalize to connect six though it might be the case that you need additional ones. However, if all you want is a computer-game to give a quick reasonable response, this is definitely the way to go.

Additionally, in case you are interested in trying to extend the results by Tromp that Allis mentions in the exceprt I was showing above or even to strongly solve the game (according to Jonathan Schaeffer's taxonomy this implies that you are able to derive the optimal move to any legal configuration of the game), then you should read some of the latest works by Stefan Edelkamp and Damian Sulewski where they use GPUs for optimally traversing huge state spaces and even optimally solving some problems.

Hope this helps,


Computation equivalence of functional and procedural programming

One standard way to prove that a language is Turing-complete is to implement a simulator for a Turing machine (or for any other Turing-complete language) in that language.  That is typically straightforward but boring, for most general-purpose languages.
You can find more resources on Turing-completeness in turing-completeness; see especially, e.g., Is there an algorithm for converting Turing machines into equivalent Lambda expressions?.  You might also be interested in Which calculus is based on first-order functions and is Turing complete?, Are there minimum criteria for a programming language being Turing complete?, What does being Turing complete mean?, Are all turing complete languages interchangeable, Clear, complete, proof that a language is Turing Compete?.


Here is an approach which is not too efficient in terms of running time. Suppose your array has length $n$, say $A[1],\ldots,A[n]$. Given an element of your array, you can determine its rank (i.e., the value of $k$ such that it is the $k$th smallest element), so we can assume that the array contains a permutation of $1,\ldots,n$.

Consider now the cycle induce by the element $A[1]$, that is, write
$$
A[1] = x_1, A[x_1] = x_2, \ldots, A[x_\ell] = 1.
$$
If $x_1 = 1$ then $1$ is already at the correct place. Otherwise, you want to modify the array so that:
$$
A[1] = 1, A[x_1] = x_1, \ldots, A[x_\ell] = x_\ell.
$$
Hopefully you can see how to do it using constant space.

Go over all the elements $A[1],\ldots,A[n]$ in this way. Elements which you have already sorted (for example, $x_1$ in the example above) will already be at the correct place, so you will only modify each cycle once. In other words, you will only write to each position once.


Although Alan Turing is of course a very important computer scientist, the Turing test is only superficially related to computer science. It is more related to philosophy.

As long as machines exist people have wondered whether it is possible to construct a machine that can think. But to answer this question we must first answer the question what it means -- what is thinking? Turing tried to circumvent this philosophical problem by changing the question a bit: the goal is no longer a thinking machine but a machine which is indistinguishable from a thinking being.

The Turing test was intended as a thought experiment to make the reader think about (artificial) intellingence in some way, but it appealed to a lot of people. So people started to organize Turing tests for real, and if you're doing real Turing tests, then of course you need real rules. Last year the Turing test organized by the University of Reading attracted a lot of attention because, according to the rules fixed for that particular Turing test, one computer program beat the judges. See here for the press release.


Is There a Programming Language That Embraces Globals?

This seems to me (as to some commenters) to be simply dynamic
scoping. It was used often in Lisp to change the behavior of system
functions to get some extra features, or perform hidden actions such
as monitoring of programs.  The cost is indeed that large programs may
be difficult to manage and maintain. Since then, there was a long
battle between static and dynamic scoping, I would guess that static
scoping supporters provided techniques to do what was formerly done by
dynamic scoping. The book I would look for such techniques is Abelson and Sussman:
Structure and Interpretation of Computer Programs.

It is available on the web in different formats, including html and pdf


Automatically generate meaningful queries for a data table

I have no idea whether this has been addressed before. I have never
seen it (but I am not in databases), and I would be surprised  if no
one had adressed it. Since there are no answers yet, I will attempt to
give a view that may hopefully help. It is very elementary, and it
would really require more study of how this kind of view may combine with
the various types of queries one can make. What I write below was strongly
influenced by your example and the queries that go with it. But there
is more to a relational database.

As remarked by Raphael, generating queries is relatively easy. But
that is not your problem. What you want is meaningful queries. It is
a semantic issue that depends much on the semantics you attach to your
columns.

I suspect that you may have a typing problem, which I tend to
see also as a dimensional problem in the physics sense. It may not be
easy or even meaningful to attempt to deal with it in a purely
automated way. I am not thinking of elementary types as found in most
programming languages, but of abstract types as found now in object
oriented languages, and all languages with data abstraction.

Hence, first of all, you should look whether there is something to
be learned from object oriented databases.

I also know that physicists use "databases" to store their
experimental data before exploiting it with specialized software.  If
information can be found on these tools (usually very proprietary),
there is a possibility that they may have addressed this typing issue,
though a physicist told me that is not the case.

Also you should make clear what you intend to provide as input to your
generator, so that your queries make sense. Short of providing some
kind of semantic information, a column of numbers is just a column of
numbers, and any idea you may have to fold, spindle or mutilate them
with SQL queries is fair game. You have to say what data, what semantic information, you provide
to your generator, if you hope for an answer (which is a variant of
the GIGO principle).

I will attempt to illustrate a possible type vision with
physics. Physics uses a lot of scalar quantities: weight, distance,
speed, date, duration, temperature, heat.

You could have these quantities appear to qualify columns in the data
base of a physicist. But not all operations between them make sense.
Testing equality of weight and date probably does not. Actually,
testing equality between to quantities that have different physical
dimension is likely to be meaningless, unless there is some implicit
relation that only the database creator can know about. The same goes
for addition quantities with different dimensions.

Some dimensions have additive qualities, such as weight or volume,
while others do not, such as temperature or density, though they can
be averaged (some of them). Physicists distinguish them by talking of
intensive or extensive properties. Extensive properties are
proportional to the amount of material. They can be added.

I suspect that these concepts exists also for your store management
database, but may have to be refined (I am not sure). The price per
unit of a good is clearly an intensive property. Adding these prices
makes no sense (whether its concerns the same article or different
ones). But, for example, taking the average may have sense, if you do
it for distinct articles.

Now such a classification can lead to more knowledge. For example. the
ratio of two extensive properties is an intensive one. This is why the
price per unit is intensive.

But these concepts apply to properties of materials, and I suspect
things may be more complex than that in general. A ratio could be
additive in a context where   intensive/extensive does not apply.
Still, though speeds can be added in physics, if you have a column of
speeds in your database, it is very likely that adding them makes no
sense, and that taking the average makes a lot of sense.

More generally, dimension equations may give you hints of what makes
or does not make sense. Maybe there are other concepts such as
intensive and extensive properties.

Then, in the same spirits as abstract typing in programming languages,
with a specification that states the allowed primitive operations, you
could have a specification of your database that give you information
about columns (such as dimension, or allowed operations) from which
you can infer whether a queries is meaningful.

But I do not believe this can be inferred from a simple knowledge of
the database without any semantic knowledge provided by the
designer. This knowledge should be part of the design process anyway.

Another point is about ranking. I am not sure that making sense can be
rated on a subtler scale than (true, false). If things can make sense
at all, they can be very important to some people and without interest
to others.  This can probably be measured by actual database use. But
again, it also depends on what you want the ranking for, and on the
kind of semantic information you can provide.


What is Ironic complexity? What are some good resources to learn about it?

Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term:

  There is one technique that has had some striking recent successes in proving circuit lower bounds, and that bypasses the natural proofs, relativization, and algebrization barriers. This technique might be called “ironic complexity theory.” It uses the existence of surprising algorithms in one setting to show the nonexistence of algorithms in another setting. It thus reveals a “duality” between upper and lower bounds, and reduces the problem of proving impossibility theorems to the much better-understood task of designing efficient algorithms.

The survey contains some pointers which you might want to look at.

Ryan Williams has given a series of two talks on this recently at the Simons institute: part 1 and part 2.


Can a second process execute when the Operating System is performing a context switch?

(1) First, lets define our terms. From Wikipedia:

  In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.

In other words, a context switch is the act of transfering control from one process to another. To recall the current process, the CPU has to take a snapshot of its state before allocating resources to the new process.

(2) Now let's answer exactly what get's saved. Also from Wikipedia:

  registers and memory maps, updating various tables and lists, the PC, stack pointer, etc.

So, pretty much everything in the CPU needs to be stored somewhere else before loading in a new process' state.

Now let's consider your question by reasoning about two arbitrary processes, PID 1 and PID 2

PID 1 is preparing to hand the CPU to PID 2 and begins storing its state. Thus, all critical CPU elements are in use. One by one as these elements are stored, they are freed (often the timing is more complex) and the CPU can allocate those resources to PID 2.

Squeezing in an extra process would just cause overhead in the primary context switch between PID 1 and PID 2. You might even consider it a context switch inside of a context switch for any nontrivial process. Sure, if the ALU is open, it could probably do a quick calculation or two but what good would those results do when not a part of a process which is far more than just a few calculations?

Theoretically possible? Sure. Reasonable, NO. Instead of trying to use that time "lost" during a context switch, innovations focus on classifying different degrees of context switches. Basically, if you have a lightweight switch between a process, or perhaps a thread, the entire processor is not held up while doing so. For more reading, I suggest: https://en.wikipedia.org/wiki/Light-weight_process to see the difference in process types.

Clarification: The scheduler is a kernel space process.


shortest paths algorithm - why backtrack from the end node instead of starting from the starting node?

You want to find the shortest paths $S(s,v)$ to all nodes $v$ (31:30 in the video). In other words, we are interested in computing a function $f(v) = S(s,v)$, and, as explained in lecture, you can write it as $f(v) = \min_{(u,v) \in E} f(u) + w(u,v)$. In the end, it allows you to compute all such values in one go.
If you instead consider an equation $S(s,v) = \min_{(s,u) \in E} w(s,u) + S(u,v)$, you do can find $S(s,v)$ this way. However, you won't be able to find $S(s,u)$ for all other $u$ in the process, and you'll have to run the same algorithm again for other end vertices.


Is there any model of Game of Life compatible with hypercomputation?

Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".


Hardness of a special GAP-CLIQUE problem

The problem is solvable in polynomial time, using the following algorithm:

  Keep removing pairs of unconnected vertices, until a clique remains.

If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise).

Source: Boppana and Halldórsson, Alon and Kahale.


How to fool the plot inspection heuristic?

Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of $(\log n)^a$ from $n^b$. For example, $O(\sqrt{n} \log n)$ looks a lot like $O(n^{0.6})$:

[source]

For example, in "Some unexpected expected behavior results for bin packing" by Bentley et al., the growth rate of empty space for the Best Fit and First Fit bin packing algorithms when packing items uniform on $[0,1]$ was estimated empirically as $n^{0.6}$ and $n^{0.7}$, respectively. The correct expressions are $n^{1/2}\log^{3/4}n$ and $n^{2/3}$.


Algorithm to determine which vertices/edges would disconnect undirected graph if removed

For vertices you could use articulation point algorithm that uses DFS and runs in $O(|V| + |E|)$ time. Similarly you could find bridges. Look here and here. But if there is no bridge and you are interested in cut-set (of edges) I guess you could use maximum flow minimum cut algorithm by assigning weight equal to 1 to each edge if they are not weighted. And finally if you are interested in subgraphs whose vertices are connected with each other (there is a path between each pair of vertices) then use an algorithm for computing strongly connected components.


Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

Consider your binary tree as a binary search tree on the integers $1$ through $n$ to find that the answer for some given list $L \subseteq [1, n]$ will be $\{\min L, \max L\}$. In case you are not given a BST, you can traverse the given tree in-order to find those values in linear time (though that might be dependent on the data structure used to store $L$).


$\Gamma$ here is overloaded notation. The meaning of the expression $\Gamma(x) = \tau$ above the inference line here is given under the "Type rules." section of A Short Introduction to Systems F and F Omega on page 5. In this setting, $\Gamma$ is an inductively-defined function sending variables (in $\Gamma$ considered as a context, i.e. a list of variables) to their types.

A more illustrative, syntactic way to write the rule you give might be: $\frac{}{\Gamma,\ x : \tau\ \vdash x : \tau}$, where $\Gamma$ ranges freely over contexts. Note that the order of variables in a context here does not matter, so this rule allows us to project any variable in a context as a term.


If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

First, to be specific I’m going to assume your heuristic function runs in constant time and we have a graph G with n nodes, and that you are asking about linearity with respect to n.

I claim that in the worst case A* will run in quadratic time.

Suppose G is a complete graph where every edge has a weight of 10000 except for the “true path” which winds from the starting node along every other node until the final node, and these edges have weight 1.

By definition of A*, every time we visit a node, we look across all its edges to queue up nodes into our priority queue of paths to explore. By construction, we visit every node and hence consider every edge. It is a complete graph on n nodes, so there is roughly n^2 edges, thus this process takes quadratic time


Understanding time complexity of a while loop that will look over all vertices and edges

Because each edge contributes to two degrees, we have
$$\sum_v\mathrm{deg}(v)=2m.$$

The time taken by the whole loop is $O(m)$.

Your analysis is of course correct, but since you replace $\mathrm{deg}(v)$ with the upper bound $m$, you get a loose bound finally.

By the way this is BFS if you ignore the "color" action.


Optimal root in shortest path tree (SPT)

This problem is equivalent to computing the radius of a graph. The best known algorithms for computing radius essentially compute all pairs shortest paths, so the method that you suggest cannot be improved much. If the number of edges is large, maybe Floyd–Warshall algorithm could be faster.

References:

https://en.wikipedia.org/wiki/Distance_(graph_theory)

https://arxiv.org/abs/1506.01799


if $L \in NP$ then its mapping reducible to HALT?

It depends what type of reduction you're talking about. But if you mean a "many-one reduction with no time constraints" (a Turing machine that transforms instances of problem $L$ to instances of problem HALT such that the answers remain the same), then yes.

The algorithm goes something like this:

Take an input $x$
Use brute force to decide whether $x \in L$ (in potentially exponential but still finite time)
If the answer is "yes", let $T$ be a Turing machine that always accepts
If the answer is "no", let $T$ be a Turing machine that always diverges
Return $\langle T \rangle$

Now, when $\langle T \rangle$ is passed to a HALT oracle, the oracle will accept if $x \in L$, and reject if $x \not \in L$.


Equivalence relation Mathematical base In Computer science

In order to prove that $U$ is an equivalence relation, you need to use the definition: prove that $U$ is reflexive, symmetric and transitive. If you try to do that but it doesn't work, you can try to disprove the claim that $U$ is always an equivalence relation by giving a counterexample: equivalence relations $R$ and $S$ such that the corresponding $U$ isn't an equivalence relation (that is, it either isn't reflexive, isn't symmetric or isn't transitive); you can use your failed proof attempts to guide you in the construction.