Which object-oriented programming language is the closest to the untyped sigma-calculus?

JavaScript looks perfectly like untyped sigma calculus.

It supports first-class citizens, described in paper concepts in terms of prototypes, closures, clone (called split), (dynamic) method override, objects dynamic creation, extension, delegation, subsumption, object fragments and polymorphism (which is understatement in terms of this language). Essentially it supports every operation described in the paper.

Since it uses prototype based inheritance the update of methods is one of the basic operations in this model. It recently started to support hierarchical class inheritance (but it was not needed, since emulating any kind of hierarchical behavior is possible with very short code).

Origins of Cardelli work predates the creation of JavaScript, but also worth mentioning is that JavaScript description as general purpose any language emulator with very short code to support such was described by Don Knuth (which predates Cardelli work, no connection between Knuth paper and creation of JS was ever made in any direction, but both papers exactly describe the JS properties).

Other languages fail with method backups or dynamic method override. But this is not the case for other prototype based languages (at least the most populqr ones), which fully support $\varsigma\text{-calculus}$ (take for example "Self").


find a path to visit every node in graph not necessarily once

You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods.
If the graph is strongly connected, then it is easy.  Let $s$ be the starting node.  Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since the graph is strongly connected).  Repeat, appending to the end of the path, until every vertex has been visited.
If the graph isn't strongly connected, decompose it into a dag of scc's.  Then you can reduce the problem to finding a path through this dag (within a scc, use the algorithm of the first paragraph).  You can find a path to visit every node in a dag iff the dag is itself a path, i.e., it has the structure $v_1 \to v_2 \to \dots \to v_k$, and then it is trivial to write down this path.
This is not a Hamiltonian path, since it may visit the same vertex multiple times.


Your question is a bit like this: "I am a programmer by hobby, and I learned about von Neumann machines. Why should I care about them?" And the answer is: because they're the theoretical model of computing machines that transformed our society.
Your question about the $\lambda$-calculus has a similar, but less grandiose answer. The $\lambda$-calculus was invented before Turing machines as an answer to "what is computation?" In itself it is not terribly practical, but it has been immensly influential in programming. Many programming concepts that we use today originated in the $\lambda$-calculus. Various languages support $\lambda$-calculus to various degrees, but almost all of them are in debt to $\lambda$-calculus to some degree (even the ones that are claimed to be "anti" $\lambda$-calculus).
If you are a hobby programmer, you should learn a programming language with good support for $\lambda$-calculus, as that will give you the joy of actually using the concepts. For instance, you can try one of the following:

Haskell
OCaml
Racket

Many popular languages have partial support for $\lambda$-calculus, which they implement to varying degree. If you know one of them, you could try the functional programming style (which is what $\lambda$-calculus is about), but keep in mind it's not the Real Thing:

Python lambda give rudimentary support for $\lambda$-calculus.
You can try functional programming in Javascript
Java has been retro-fitted with $\lambda$-expressions to give some rudimentary support for $\lambda$-calculus.
C++ has $\lambda$-expressions too.

LISP belongs to this list as well, as it does not have true support for $\lambda$-abstraction.


Bounds on probe lengths and number of rehashes with universal hashing

This does not seem like a good example for teaching purposes, as there's no clean analysis or useful conclusions you can draw.

In particular, from only the assumption that you have a weakly universal hash function, you can't draw any useful conclusions about the probability of a having less than K items in the bucket.  That would require some notion of K-wise independence.  Weak universality is a weakened form of 2-wise independence, and if $K>2$, it gives you no information about K-wise independence.  In particular, the hash function could be arbitrarily bad, and the probability could be arbitrarily high.  You need stronger assumptions about the hash function to do any useful analysis.

Instead of assuming weak universality, if you want to get a clean analysis, I suggest you assume that the hash function is (or behaves like) a random function, chosen uniformly at random from the set of all possible functions with that signature.  Then the calculations get easy, since each output of the hash function is uniformly random and independent of all other outputs.


Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$

Let's redo your calculation. You want
$$ \log^kn \geq C \sqrt{n} $$
to hold for some $C>0$ and large $n$. Taking the logarithm,
$$
k \log \log n \geq \log C + \tfrac{1}{2}\log n,
$$
and so
$$
k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n}
$$
should hold for large $n$. In other words,
$$
k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log n}\right).
$$


Determining if an undirected connected graph is minimally connected

If $G$ is an undirected graph, it's a standard lemma that the following are equivalent:

$G$ is a tree.
$G$ is connected and has no cycles.
$G$ is connected and the number of edges is one less than the number of vertices.

Therefore, yes, your solution is also correct.

(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way.  There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)


What kind of optimization problem this belongs to?

Yes, many standard methods can handle this.  Your score is called a loss function.  In particular, let $\ell(x_i,y_i)$ denote the penalty (score) if on input $x_i$, your decision rule outputs $y_i$.  If $x_1,\dots,x_n$ is a training set, we define the total loss over the training set (the empirical risk) of a decision rule $f$ to be

$$L(f) = \sum_{i=1}^n \ell(x_i,f(x_i)).$$

Now your goal is to find $f$ that minimizes the total loss $L(f)$.  Many machine learning algorithms can be used in this manner, with an arbitrary loss function.  Typically, we require that the loss function be differentiable, and then we use gradient descent to find $f$ that minimizes $L(f)$.  For instance, if you are using neural networks, then you use gradient descent to find weights for the neural network that minimize $L(f)$.  Often you add a regularization term to the loss function, too, to prevent overfitting.


I am skeptical that machine learning is the right tool for this problem.  I would look for a more direct solution, perhaps using peak detection or changepoint detection, or some other form of classical method for time-series analysis.
If you do use machine learning, cross-entropy loss is not the right loss for your problem, and you will definitely need to change that.


Where can I find a high quality copy of Turing's On Computable Numbers?

There is a very high resolution scan in the Turing Digital Archive, however it's presented via a flash player plugin which makes reading mildy awkward and doesn't seem to allow printing.

There are a handful of marginally nicer PDF copies than that Caltech one you link available online [1][2], however they all seem to have been drawn from the same photocopy at some point.


Relation between Hamming distances of columns and rows

The condition on the columns implies that $2t < n$. Suppose that the condition on the rows is not satisfied. The rows therefore form a code of minimal distance at least $n-t > n/2$ of size $n$. The Plotkin bound implies that unless $n-t$ is extremely close to $n/2$, such a code cannot exist. If $t$ is very close to $n/2$, however, the columns form a code of minimal distance close to $n$, which is again ruled out by the Plotkin bound (except perhaps for very small $n$).

I'll let you fill up the details and check for which $n$ this argument works.


Alternatives to multiplication/division/modulo for encoding choices?

You can implement ANS using only additions, masks and shifts. Take a look at Finite State Entropy (FSE), it's a performance-focused version of ANS with accurate compression.


Relationship between Independent Set and Vertex Cover

Well, strictly speaking it's not the complement; co-VC is co-NP-complete whereas Independent Set is NP-complete.  If they were the same, we would know that co-NP was equal to NP, which we do not, and indeed most people believe they are not.

But an easy way of seeing that they are not the same if to consider $(K_4, 2)$, the complete graph on four vertices) which is neither a yes-instance of Vertex Cover nor of Independent Set.  Similarly, the instance $(K_2,1)$ is a yes-instance for both.

However, they are related in the following way.
A set of vertices $C \subseteq V(G)$ of a graph $G$ is a vertex cover if and only if $V(G) \setminus C$ is an independent set.  This is easy to see; for every endpoint of an edge, at least one vertex must be in $C$ for $C$ to be a vertex cover, hence not both endpoints of an edge are in $V(G) \setminus C$, so $V(G) \setminus C$ is an independent set.  This holds both directions.

So $(G,k)$ is a yes instance for Vertex Cover (a minimization problem) if and only if $(G,n-k)$ is a yes instance for Independent Set (a maximization problem).


Classic texts on computational complexity include Hopcroft & Ullman's text {1} and Sipser's text {2}.  With patience, they should both be accessible.

{1} Hopcroft, John E., R. Motwani, and J. D. Ullman. "Introduction to Automata Thoery, Language, and Computation (2nd edition)". Addison-Wesley, Reading (2001).

{2} Sipser, Michael. Introduction to the Theory of Computation. Cengage Learning, 2012.


Need help with adding elements to hashtable with linear probing

It's not explicitly defined - rather there's an implicit subindex (based off the table's size) to the hash-function. At the start we had e.g., $h(0) = h_7(0) = 3$. They are then informing you that $h_14(0) = 8$. There is no explained reason for this. They then re-insert the data to the larger hash table going over the old data in the order it appears in the hash table.


Multiple paths for a accepting string in NFA?

Yes, there can be many paths from the starting state to the ending state. It is not too difficult to cook up many trivial examples of when this happens, for instance

Clearly accepts the string $ab$ but it can go through either $s1$ or $s2$.

However, in DFA's this will never happen because at each state there is only a single possible transition for each character, and those fixed transitions uniquely determine the path.


backpropagation algorithm seems to be forcing output values to middle than extremes

I have run into a similar issue when trying to train a neural network with hidden layers for regression.
My network simply learned to always predict the mean of all target values in the training set.

In my case, the problem was missing input normalization (my input data had values in the 100,000s) in combination with sigmoid units:
The easiest way for the network to reduce the loss function (mean squared error) was to simply set the weights in the early layers to very small values and the output unit's bias to the data's mean value.

After that, the network was stuck and no amount of training seemed to change anything, since the absolute gradient values were too small.


What were the research outcomes of the Univalent Foundations Program year (Homotopy Type Theory)

The book is itself representative of the research product of the program. The code that they wrote actually is mostly in Coq, to my knowledge, and certainly the development that accompanies the book was written in Coq.

Homotopy Type Theory itself essentially constitutes Martin-Löf, together with the univalence axiom, which essentially states that equivalent types are equal. The notion of equivalence comes from a view that establishes a connection between a synthetic homotopy theory and Martin-Löf type theory, hence the name. This axiom gives way to a powerful type theory that the book shows is capable of reasoning about a lot of important existing foundational mathematics.

In fact, part 2 of the book comprises developments of a more traditional, topologically-motivated version of homotopy theory, set theory, category theory, and a nice constructive presentation of the real numbers. I have not explored the Coq code that much yet, but my understanding is that all of these presentations are accompanied by corresponding Coq source. Since we can formulate all of these important foundations entirely within homotopy type theory, the hypothesis that it might be an important foundation for mathematics going forward makes sense. The idea is that mathematicians will be able to extend these seminal developments towards more results in fields like algebra, topology, and analysis.

Inasmuch as homotopy type theory pertains to being able to do mathematics in Coq via the Curry-Howard correspondence, you can think of homotopy type theory as corresponding to a more powerful instance of Curry-Howard. The most exciting contribution of this work is really that it gives mathematicians language for speaking about mathematics in terms of type theory, and the idea is that this should enable on the one hand, more mathematics being accompanied by mechanized proofs in provers like Coq, as well as computer proofs that correspond more closely to their plain English equivalents. Anyone who has used Coq will tell you that the proofs that you produce often don't end up looking much like equivalent plain-English proofs at all.


2-dimensional ranking of multiple arrays

Here is a solution quite simple to implement, that only improves the $d$ factor.
For the increasing series $[1, 2, .., n]$, get the tuple list of the coordinates to increase in your output array. For $d = 2$ and $n = 4$, this is $H=[(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]$. Asymptotically (not exactly due to $(a, a)$ being always valid), there are $O(\frac{n^d}{d})$ terms in this list.
Initialize an output array $B$ of size $n^d$ to zeros.
Then, for each of the $m$ arrays $A$ and for each tuple $(a_0, a_1, ..., a_d)\in H$, increase $B[A[a_0], A[a_1], ..., A[a_d]]]$ by 1.
It achieves $O(\frac{m n^d}{d})$.
EDIT
For $d=3$, basically, both tuples $(0, 1, 2)$ and $(0, 2, 1)$ are in the coordinates list to increase. But if you want to use the knowledge that $B[a, b, c] = B[a, c, b]$, you have to keep only tuples non-decreasing after the 2nd integer. So here you leave $(0, 2, 1)$. Be careful to still keep $(a, b, b)$ tuples like $(0, 2, 2)$.
Then you will divide the number of terms in the list by about a factor $2(d-1)!$ for the general case).
At the very end, you have to add a $O(n^d)$ step to gather counts on $B[a, b, c]$ and $B[a, c, b]$. For every tuple $(a, b, c)$ with $b < c$,

$S = B[a, b, c] + B[a, c, b]$
$B[a, b, c] = S$
$B[a, c, b] = S$

This runs in $O(\frac{m n^d}{d!})$.


What happens when you don't use a metric in k-means?

You should use k-means when you have coordinates and a euclidian distance metric. Its not just the distance that matters - you need to reassign cluster centers. So if you have coordinates, why use something other than euclidian distance? If you don't have coordinates, you can't use K-means.


Data structure for storing edges of a graph

If your graph is sparse then you should store it using adjacency "lists", though you probably want something more efficient than a list (or perhaps you don't, depending on usage). It's simplest if you store each edge at both endpoints. This can be implemented in many ways, for example you can store all data in some big array, and store only pointers in the adjacency "lists".


Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language

$A$ is regular since it's the union of the following $3$ regular languages:

$\{0^i 1^j : i \bmod{3} = 0, j > 0 \}$ for which a regular expression is $(000)^*11^*$.
$\{0^i 1^j : i \bmod{3} = 1, j > 1 \}$ for which a regular expression is $(000)^*0111^*$.
$\{0^i 1^j : i \bmod{3} = 2, j > 2 \}$ for which a regular expression is $(000)^*001111^*$.

A reguar expression for $A$ is then $E = (000)^*(1 + 011 + 00111)1^*$. You can now easily construct a NFA from $E$.


It's better to use the parametrization $p_i = 2^{-k_i}$. Multiply the equation $\sum_{i=1}^n p_i = 1$ by $2^{k_n}$ to get
$$
\sum_{i=1}^n 2^{k_n-k_i} = 2^{k_n}.
$$
The right-hand side is even, so the number of $i$ such that $k_i = k_n$ must be even as well (why?). This implies that $p_{n-1} = p_n$.

For your second question, it is known that the minimum expected codeword length is at least $H(p) = \sum_i p_i \log (1/p_i) = \sum_i p_i k_i$. The converse to Kraft's inequality shows that there is a prefix code with codeword lengths $k_1,\ldots,k_n$, and so with expected codeword length $H(p)$.


Djikstra's shortest path vs Brandes algorithm for betweeness centrality

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph.

This isn't necessarily true. Perhaps there is a different algorithm that is faster than what you outline. One possible explanation for the discrepancy in running times is that the NetworkX library uses a smarter algorithm. However, it's hard to know because you haven't told us how the function betweenness_centrality is implemented in NetworkX. It is also possible that it uses an algorithm along similar lines, but employs some optimizations that don't affect the asymptotic running time (big O) but does save a large constant factor.


How to analyze the worst case of weighted quick-union method on union-find

This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer.

To prove that each level has a binomial coefficient, we use induction.
The base case of $n=1$ is ${1 \choose 0}$ is 1. $n$ represents the height of the nodes while the $0$ is just an arbitrary level of the tree.
Now, assume that at each level the number of nodes is ${n \choose i}$ where $0 \le i < n$ for a tree $T_n$. When we combine 2 trees of size $2^n$ (let's call them $T_1$ or $T_2$), then one of them is chosen to point to the root and the other is chosen to become the root. Let's say that the root of $T_1$ is chosen to point to $T_2$. If this is the case, the depth of each nodes increases by 1. That means, in a sense, each node is "pushed" down the tree to the next level below. Now, if, by the inductive hypothesis, we have ${n \choose i}$ nodes at each level of $T_2$. However, for each level $i$ in the $T_1$, the number of nodes at is equivalent to the previous level in $T_1$, $i-1$. Therefore, for each level $i$ in $T_1$ connected to $T_2$, the number of nodes is ${n \choose i-1}$. So, if we count the number of nodes on each level, it's just the sum of the number of nodes at each level of $T_2$ and then the number of nodes at each level of $T_1$ connected to $T_2$. So, the number of nodes is ${n \choose i} + {n \choose i-1} = {n+1 \choose i}$. This fits the form of the inductive hypothesis; therefore it is proven.


When you say "cycle", do you mean a simple cycle of length 40 (so no vertex is allowed to be repeated), or would you allow an arbitrary walk of length 40 that ends where it starts (i.e., vertices are allowed to be repeated in the cycle)?  The answer to your question depends on what you mean by cycle, so I'll answer both cases.

Simple cycles

The problem of testing whether a graph contains a simple cycle of length $k$ is hard.

No efficient algorithm is known; all known algorithms have running time that is exponential in $k$; and if $k$ is part of the input, the problem is NP-hard.  See here and here.  In your case, $k=40$.  The best algorithms that I know of have either a $O(k!)$ factor or a $O(n^{k/2})$ factor in the running time, so they will be totally infeasible: $O(n^{20})$ is not feasible for any non-trivial value of $n$, and $k! \approx 2^{159} \approx 10^{48}$, which is also infeasibly large.  (See Louis's answer for pointers to an algorithm of the former type.)

If you allow repeated vertices

If you allow the cycle to contain repeated vertices, then the problem becomes much easier, and there is a polynomial-time solution.

Hint: Consider the adjacency matrix of the graph, $M$.  Look at $M^2$.  Can you find any relationship between the $i,j$ entry of $M^2$ and paths of some length?  Can you generalize?

(Since this looks like a natural exercise problem, I am just giving you a hint, and letting you take it from here.)


Deciding between two algorithms with similar runtime in two parameters

A better comparison is $n$ versus $m\log m$. When $n = \Theta(m\log m)$, both algorithms have running times $\Theta(m\log m)$. When $n \gg m\log m$ (or rather $n = \omega(m\log m)$, the second algorithm has running time $\Theta(n)$ and the first one has running time $\Theta(m\log n) = o(n)$ since $m = o(n/\log n)$. When $n \ll m\log m$ (or rather $n = o(m\log m)$) the second algorithm has running time $\Theta(m\log m)$ and the first one has running time $\Theta(m\log n) = o(m\log m)$.


Is something missing in this EXPLORE algorithm?

This might be a bit too much, but I tried the best I could to condense it.  Unfortunately, Java doesn't allow one to write concise code...  So, here's breadth-first and depth-first traversal of a graph (I used JGraphT) library for graph implementation.  This should better illustrate the idea.

package tld.se.doodles;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultDirectedGraph;

public class GraphSearch {

    public static void main(String ...args) {
        DefaultDirectedGraph<Integer, DefaultEdge> graph =
                new DefaultDirectedGraph<>(DefaultEdge.class);
        int[][] vertices = {
            {1, 2}, {1, 3}, {2, 1}, {2, 3},
            {3, 5}, {3, 6}, {3, 4}, {4, 7},
            {5, 2}, {5, 6}, {6, 3}, {6, 7}
        };
        Arrays.stream(vertices)
                .forEach(pair -> {
                        graph.addVertex(pair[0]);
                        graph.addVertex(pair[1]);
                        graph.addEdge(pair[0], pair[1]);
                    });
        depthFirstTraversal(graph);
        breadthFirstTraversal(graph);
    }

    private static void depthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Depth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        dftHashed(start, graph, cache);
    }

    private static void dftHashed(
        Integer from, DefaultDirectedGraph graph, HashSet cache) {
        if (!cache.contains(from)) {
            cache.add(from);
            System.out.format("Visiting: %d%n", from);
            graph.<DefaultEdge>edgesOf(from).stream()
                    .forEach(edge ->
                             dftHashed((Integer)graph.getEdgeTarget(edge),
                                       graph, cache));
        }
    }

    private static void breadthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Breadth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        HashSet<Integer> firstGen = new HashSet<>();
        firstGen.add(start);
        bftHashed(firstGen, graph, cache);
    }

    private static void bftHashed(
        HashSet previous, DefaultDirectedGraph graph, HashSet cache) {
        cache.addAll(previous);
        HashSet<Integer> next = (HashSet<Integer>)previous.stream()
                .flatMap(vertex -> {
                        System.out.format("Visiting: %d%n", vertex);
                        return graph.<DefaultEdge>edgesOf(vertex)
                            .stream().map(graph::getEdgeTarget);
                    })
                 .collect(Collectors.toCollection(HashSet::new));
        next.removeAll(cache);
        if (!next.isEmpty()) bftHashed(next, graph, cache);
    }
}


What is the exact definition of a dictionary in the concept of linear algebra and computer science?

Yes, as it says, a "dictionary" is just the word they're using for a matrix with entries of a particular type that's used for a particular purpose. They're drfining the term "dictionary" in the text you quote.


Confusion in Banker's Algorithm: How resources are allocated?

The maximum resources are an estimate by the process of what they might need, the currently allocated is what the process holds at the moment. The idea is that processes request more resources as they need them (and at those points you run the algorithm to see if it could lead to deadlock to grant the resources asked for, by seeing if there is a process that could finish and release all it holds if it goes on to ask for it's maximum announced request, releases what it holds, and so on). If a process releases resources, that clearly can't lead to a deadlock, thus no special handling (except for recording what is free now) is needed.

Think of you e.g. building a box out of wood, and the tools needed. You'll need a saw, a drill, a screwdriver, among other tools. You'd announce that, but you won't require all together, while you are busy with the saw somebody else could use the drill and screwdriver, so it doesn't make sense to ask for all at the start, or keep all until finished.


Determine whether a context-free language is deterministic or not

The language that is usually cited as not accepted by any DPDA is $\{a^mb^nc^nd^m\} \cup \{a^mb^mc^nd^n\}$. This is because we don't know whether to push or pop when $b$ arrives. The language you describe seems to be accepted by the DPDA you have constructed.


How to solve recurrences with transcendental terms?

The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant.

(Confusingly, in information theory the same notation is used for the function $\log + \log\log + \log\log\log + \cdots$.)


Using a 16-bit 2,s Complement normalised floating-point representation; 10-bit fractional mantissa and a 6-bit integer exponent: express 2.171875

I am lost with the given algorithm for a normalized representation.

The most significant bits should be kept, which is not what I see in your example.

1.111010010 x 2^4 = .1111010010 x 2^5 (This keeps the dot leftmost, and
one can possibly truncate bits to the right - or even round 0xxx down, and 1xxx up for positive numbers). Having a 1 immediately after the dot, allows the highest precision, compare with .00001111010010,
sign 1 bit = 0 (both ones complement, twos complement)
mantissa '1' + 8 bits = 111101001
exponent 6 bits two-complements = 000101
result: 0 11110101001 000101

This is just one possible variant: a ones complement mantissa with extra sign bit (but almost a two's complement mantissa). Here it shifted till a .1xxx
for a nonzero number. (Hence that 1 is almost redundant.)

Now your recipe:

1.111010010 x 2^4 = 1111.010010 x 2^1
sign 1 bit = 0 (both ones complement, twos complement)
mantissa 9 bits = 1111 01001
exponent 6 bits two-complements = 000001
result: 0 11110101001 000001

It only differs in the implicit +4.

For the .1 method:

2.171875 = number < 1, times 2^exp = 0,54296875 x 2^2
0,54296875 = 0.1xxx
etcetera


Equivalence in finite sets of turing machines

Hint: Since $S$ is finite, there are finitely many legal queries, and we can hardcode the answers to all of them.


A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for example the Wikipedia article on graded poset.


Java Bytecode

Similar to Microsoft's CLS, the Java Bytecode that the Java virtual machine executes gives you the (theoretical) possibility of using libraries from one JVM-targeting language with another JVM-targeting language. For example, Java libraries can be used in Scala, which IMO is a much better language than Java itself. Libraries written in Scala could be used in Clojure, or in Jython, or in one of these languages.

However, although interoperability is theoretically possible because of the common byte code to which all these languages compile, it is said (my personal experience is fairly limited) to sometimes be complicated to actually get it working.

Another, in the context of your question probably equally big drawback is, that using libraries from other languages often forces you to program in that languages style - and consequently "rip" you out of the style of the language you are actually programming in. For example, due to the lack of closures/anonymous functions and higher-order functions, Java libraries often don't have "nice" interfaces in the functional programming sense. Scala libraries, on the other hand, are usually written in a functional way.

Multi-platform languages

Another way of addressing your problem are multi-platform languages such as Haxe.

  Haxe can be compiled to all popular programming platforms with its
  fast compiler – JavaScript, Flash, NekoVM, PHP, C++, C# and Java
  (soon).

To be fair, I don't have any experience with Haxe, so all I can do is conjecture. That said, I see this approach as a double-edged sword. On the one hand, it allows you to implement libraries only once and then compile them to C++, PHP, etc., and use them from their. On the other hand, if you write a client or a library depending on other libraries in Haxe, you are probably limited to Haxe libraries, and, for example, cannot use the highly appraised C++ library Boost.

A similar, although assumably less powerful approach is followed by Apache Thrift.

  Apache Thrift allows you to define data types and service interfaces
  in a simple definition file. Taking that file as input, the compiler
  generates code to be used to easily build RPC clients and servers that
  communicate seamlessly across programming languages. Instead of
  writing a load of boilerplate code to serialize and transport your
  objects and invoke remote methods, you can get right down to business.

General worries

I assume that the "out of style" problem mentioned in the context of JVM-targeting languages is actually more general and probably something that makes it difficult to truly achieve what you want. If you specify interfaces arbitrarily general, it is likely that they feel out of place when used in any concrete programming language.

A second problem related to interfaces is which data structures to use as input/output data structures. For example, which data structures should a language-independent sorting library accept and return - arrays, sequences, lists, vectors, streams? And how are these mapped from/to data structures that actually exist in a given concrete language?

Another general problem I can see is performance. A library that is implemented in one language and cross-compiled into another is probably of poorer performance than one that is directly implemented in that language - which is not automatically a problem, but can definitely sometimes be one.


C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?

The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes that the time needed to advance iterators is constant).
The C++ specification do not mandate any particular implementation as long as it conforms to the required complexity so your question cannot be answered without inspecting the particular implementation that you are using.
However, just to convey the intuition, here are two possible implementations that would conform to the requirements:

Given random access iterators $x$ and $y$, distance($x$, $y$) returns $y-x$.
For general iterators increment $x$ until it equals $y$. Return the number of increments performed.

The type std::set does not return a random access iterator, therefore std::distance can take linear time and the second implementation above can be used. Now your question reduces to "how can the standard library iterate over the elements of a std::set in sorted order?"
The answer to this question depends once again on the implementation as there is no particular data structure mandated by the standard to implement std::set.
Since you mention red-black trees, which are a special kind of BSTs, this can easily be done by noticing that the order of iteration coincides with the order in which the vertices of a BST are visited by an in-order visit.
Notice that the concept of distance completely abstracts from the data structure used to store the elements of the set. Instead it only refers to the positions in which two elements appear when using an iterator to access the collection's contents.
In the case of std::set the elements appear in sorted order. This also means that the distance between an iterator pointing to the beginning of the collection and an iterator pointing to an element $x$ is exactly the number of elements that are smaller than $x$.


Operations on OBDD: negation through Shannon's expansion

Maybe it is better to understand if you make a truth table for both functions. You can see that if $(\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ is true then $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ is also true, because both $f$ terms are true and either $x_1$ is true or $\neg x_1$ is true. And if $(\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ is false then you have to do a case study:

If both $f$ terms are false then is $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ also false
If exactly one $f$ term (w.l.o.g. $\neg f|_{x_1=0}$) is false then it is equivalent to $(x_1 \wedge \neg f|_{x_1=1})$

Therefore, both formulas $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1}) \vee (\neg f|_{x_1=0} \wedge \neg f|_{x_1=1})$ and $(\neg x_1 \wedge \neg f|_{x_1=0}) \vee  (x_1 \wedge \neg f|_{x_1=1})$ are equivalent.


Local to global algorithms in gossip based P2P networks

Another solution would be to use SWIM gossip (Scalable Weakly-consistent Infection-style Process Group Membership Protocol), or it derivatives like Serf (which includes the vivaldi network and SWIM) or even Consul (which implements raft consensus, key value store, and Serf).


Could someone suggest me a good introductory book or an article on graph clustering?

The book The Elements of Statistical Learning by Trevor Hastie,
Robert Tibshirani and
Jerome Friedman covers a lot of learning and clustering algorithms including various graph clustering algorithms. Algorithms such as Spectral Clustering are phrased algebraically, as is much of the book. The good thing is that a pdf of the book is available from the authors' website, linked above. It has an extensive bibliography to help you beyond what is presented in the book.

There's also an implementation of Spectral Clustering in R which works quite well and has lots of options.


Detection of redundant boolean constraints

The simplification you're describing is called subsumption.  It's a standard technique and some SAT solvers (e.g. minisat) will apply it along with other simplification techniques as a preprocessing step before attacking the SAT problem itself.  In particular, subsumption and equivalent variable substitution together, applied to the generated CNF formula, are enough to do the common subformula elimination you described in the question.  That's because each circuit transformation yields an output variable, and output variables derived from the same circuit can be efficiently identified and reduced to references to a single variable.  After that normal subsumption rules applied to clauses will eliminate the common subformulas.

If you're using a solver that doesn't do this preprocessing, then you can do thr rough equivalent of it during conversion to CNF.  First you'll need to apply duplicate circuit suppression while you're doing the Tseitin tranformation.  As you're doing the transformation to CNF, memoize each circuit you've converted. If you encounter the circuit again, skip the circuit conversion and use the same output variable that you used for the memoized circuit.  Once you've converted everything to clauses, do normal clause subsumption, i.e. check each clause A against every other longer B clause to see if A's literals are a subset of B's.  If so, then A subsumes B and clause B can be discarded from the formula.


What is the best way to avoid using goto statements in the pesudocode for an algorithm?

In many cases, GOTO statement can be replaced by loops. For example, in your case, the inner loop is just "while string(i) = path(j), decrease both i and j", and the outer loop is a "loop forever", also known by the C idiom "while true".


How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

"Maximum" here means that no graph can have more than $n \choose 2$ minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say $n-1$. This is less than $n \choose 2$ which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs that have more than the maximum number of minimum cuts.


Evolving artificial neural networks for solving NP problems

No. This direction is unlikely to be useful, for two reasons:

Most computer scientists believe that P $\ne$ NP.  Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem.  If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm.  It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.
Neural networks aren't "magic".  They are a way of trying to find patterns.  For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective.  But they're not magic fairy dust.  Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem.  It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning.  We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning.  Neural networks aren't some kind of magical silver bullet that solve all machine learning problems.  They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something).  But don't be fooled.  Don't believe the hype.  Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers.  Not anytime soon, anyway.  That's just science fiction.


If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

This proof uses both construction and knowledge of closure properties of regular languages.

First, we know that regularity of languages is closed under the reversal operation, see proof of Thm. 4.2 here.

We can then define an operation named chop such that:

$$
\text{chop}(L)=\{w|aw \in L\}, \text{ where } a \in \Sigma,
$$

We can construct an NFA for chop, which simply omits the first transition (hence removing the first character):

This NFA is incomplete, but is just for the sake of illustration

Therefore the regularity is closed under the chop operation.

Finally, observe that we can produce R/a operation using chop and reversal:

$$
L/a = (\text{chop}(L^{R}))^{R}
$$

Hence L/a has been constructed using closure properties so must be regular.

Hope this helps!

Source: Formal Languages module, second year, BSc Computer Science University of Warwick.

Edit: capitalisation of first word.


Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem:

While the proof of theorem (1.1.13) is somewhat involved, the reconstruction algorithm that comes out of it is actually quite easy.  It proceeds  one  column  at  a  time,  starting  with  a  column  whose  sum  is  the highest and working in order down to the lowest column sum. In each column, we place the 1’s in those rows where with the largest number of 1-positions left, that is, such that the row sum minus the number of 1’s already filled in is the largest.


Underlying language to specify various types of logic

One answer is that we use English, but that's not what you're looking for.

To make the question more precise, let us ask what sort of formalism is useful for describing logics. This is still quite broad, because a logic has several parts: syntax, rules of inference, semantics, etc.

Syntax is pretty well understood and we know that the syntax of a language can be described in terms of formal grammar. That is a well developed theory. In any case, concrete syntax is rather boring from the point of view of logic.

It is far more interesting to ask what we need to specify the inference rules for a logic. Because a general logic can be just about any formal system, let us consider only traditional logics: classical first-order, intuitionistic first-order, second order, higher-order, simple type theory, dependent type theory and so on. One answer is that we should use a logical framework (LF). It is a variant of type theory designed in such a way that when we specify a logic in it we have:

  A statement in the logic is provable if, and only if, the corresponding type in the logical framework is inhabited.

This is desirable because it says that the logical framework is neither too weak nor too powerful.

In terms of logical strength LF is very weak: it is a dependent type theory with first-order kinds and $\Pi$'s. Speaking vaguely and in terms of logical connectives, this is a bit like using as our meta-theory a logic which has only $\forall$ and $\Rightarrow$ (and no equality).

There are implementations of logical frameworks, for instance Twelf. Of course, the point of such a tool is not just description of logics, but also the study of their meta-theoretic properties. Among the Twelf case studies you can find formalization in LF of cut elimination, the double negation translation, classical modal logic S5, and a bunch of more programming-language oriented examples.

One may also ask what formalism is necessary to specify semantics of a logic. The semantics of traditional classical first-order logic goes under the name of Tarski model theory and uses set theory, although it is well known that a much weaker system suffices (a fragment of Peano arithmetic). Other kinds of logic require different approaches, but in general it is the case that the meta-theory needed for the description of semantics is much less complicated than the semantics itself. For instance, the models of intuitionistic higher-order logic are elementary toposes. The axioms for an elementary topos are essentially algebraic, i.e., we can express all the axioms of an elementary topos with equations (we do not even need any logical connectives, just equations), see Section II.2 of Lambek and Scott's "Introduction to Higher-Order Categorical Logic".


can't quit understand one step of the recurrence time complexity calculation

It obviously is not correct. To fix it, define $S(m)=T(2^m)$, and then we would have $S(m)=S(m/2)+1$. Now, continue with the proof replacing everywhere $T(m)$ with $S(m)$. After you solve what $S(m)$ is, substitute $m=\log(n)$ in the solution to get what $T(n)=T(2^m)=S(m)$ is.


Can someone please help with the proof of this?

Take unambiguous grammars for L and R with start symbols $S_L$ and $S_R$. For L union R take a grammar that starts with $S->S_L$, $S->S_R$. Since no string is both in L and R, only one of the initial two rules can succeed, so the grammar is unambiguous.


Arranging Colors in a Grid; Two Dimensional TSP?

You can solve the problem with any solver for the Quadratic Assignment Problem (QAP). In the traditional QAP, facilities are assigned to locations such that the cost of transporting necessary goods between any two facilities is minimal. QAP is NP-hard.

Here we assign the colors $C$ to the swatches $S$. The weight or flow $w : S \times S$ between the locations is $1$ if they are neighbors and zero otherwise – you may define neighborhood however you like. The distance $d : C \times C$ would be LAB-metric you already defined.


I believe that the answer is yes: any min-cut constructed in this way from a max-flow will also have minimum possible cardinality, among all possible min-cuts.

There can be multiple min-cuts, all with the same cost.  They form a lattice structure: the intersection of two min-cuts is another min-cut, and the union of two min-cuts is another min-cut.  You can identify a "smallest" element in this lattice by taking the intersection of all min-cuts; this will be another min-cut, and it will have the smallest cardinality of all min-cuts.

As I understand it, it is possible to prove that the min-cut obtained from a max-flow is always this "smallest" min-cut.  Or, to put it another way, if you think of the source $s$ on the left and the sink $t$ on the right, then any min-cut obtained from a $s,t$-max-flow will be always be a "leftmost" cut.  Also, it will follow that any other min-cut will be a superset of this cut found by max-flow, exactly as you conjectured.

For references to these results, and other related material, see the following questions (note: you may need to double-check some of the claims yourself, as I have not personally verified them):

Does Ford-Fulkerson always produce the left-most min-cut

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723


Characterization about Kleene Closure, when is a language $L=L^*$?

What your argument actually shows is
$$
L = L^* \Rightarrow L=L^2 \Rightarrow L = L^+.
$$
Indeed, suppose that $L = L^*$. On the one hand, $L^2 \subseteq L^* = L$. On the other hand, since $\epsilon \in L$, we have $L = \epsilon L \subseteq L^2$.
Next, suppose that $L = L^2$. Inductively, $L = L^n$. In particular, if $w \in L^+$ then $w \in L^n$ for some $n$, and so $w \in L$, showing that $L^+ \subseteq L$; and $L \subseteq L^+$ trivially holds.
If $L = L^+$ then we cannot conclude that $L = L^2$. For example, $a^+ = (a^+)^+$ but $a^+ \neq a^+a^+$.
If $L = L^2$ then we cannot conclude that $L = L^*$. For example, $\emptyset = \emptyset^2$ but $\emptyset \neq \emptyset^*$.
However, it is possible to prove the following:

If $L = L^+$ and $\epsilon \in L$ then $L = L^2$. This shows that if $\epsilon \in L$, then $L = L^+ \Leftrightarrow L = L^2$.
If $L \neq \emptyset$ then $L = L^2 \Rightarrow L = L^*$. This shows that if $L \neq \emptyset$, then $L = L^* \Leftrightarrow L = L^2$.

Indeed, if $L = L^+$ and $\epsilon \in L$ then $L^2 \subseteq L^+ = L$, and $L \subseteq \epsilon L \subseteq L^2$.
Next, if $L \neq \emptyset$ and $L = L^2$ then let $w$ be a word of smallest length in $L$. Since $L = L^2$, we can write $w = xy$, where $x,y \in L$. By assumption, $|x|=|y|=|w|$, and so $|w| = 2|w|$, implying that $w = \epsilon$. Together with $L^+ \subseteq L$, this shows that $L^* \subseteq L$, and so $L = L^*$.

Another nice characterization is:
$$ L = L^* \Leftrightarrow L = M^* \text{ for some language } M. $$
One implication is trivial. In the other direction, if $L = M^*$ then $L^* = (M^*)^* = M^* = L$.
This characterization remains true if we impose restrictions on $M$, for example $M \cap M^2 = \emptyset$. Indeed, suppose that $L = L^*$, let $\tilde L = L \setminus \{\epsilon\}$, and let $M = \tilde L \setminus \tilde L^2$. Note that $M^2 \subseteq \tilde L^2$, and so $M \cap M^2 = \emptyset$. Also, clearly $M^* \subseteq \tilde L^* = L$. On the other hand, we can prove inductively that $L \subseteq M^*$.
Indeed, let $w \in L$. If $w = \epsilon$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L$. If $w \in M$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L^2$, that is, $w = xy$, where $|x|,|y| < |w|$. By induction, $x,y \in M^*$, and so $w = xy \in M^*$.


Probability Distributions and Computational Complexity

The complexity of probability distributions
comes up particularly in the study of distributional problems like
DistNP in Levin's theory of average case complexity theory.

A distribution is P-computable if
its cumulative density function can be evaluated in polynomial time.

A distribution is P-samplable if
we can sample from them  in polynomial time.

If a distribution is P-computable then it is P-sampable.
The reverse is not true if certain one-way functions exist.

You can extend the definitions to other complexity classes.

Oded Goldreich has a nice introductory notes on the topic
that you may want to check.


Here's a trick that video game designers have used for years. A computationally cheaper approximation to Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is to use
$$
d=\max(|x_1-x_2|, |y_1-y_2|)+\min(|x_1-x_2|, |y_1-y_2|)/2
$$
The relative error between this and the Euclidean distance is no more than 11.8%, which might be good enough for your purposes.


What is the growth rate of the world wide web?

There is much interesting research in this area that is ongoing. See eg

Using search engines to estimate size based on pages counted eg How Large is the WWW by Dobra and Fienberg
Theoretical models of networks that model the growth of the web and reflect its small world graph structure eg Models for the Growth of the Web by Ho, Pu, Tsiatas


Why does the copycat strategy work for two parallel chess games?

The setting in the link you gave (where is it referred to as $chess\lor \neg chess$) is that the player is playing on two boards with different colors, and has to win in at least one.

In that case you can win by mimicking your opponent as follows. Let $b_{\text{white}},b_{\text{black}}$ be the boards on which you play white/black correspondingly. Whenever the opponent makes a move $x$ on $b_{\text{black}}$, you play $x$ on $b_{\text{white}}$, similarly when your opponent makes a move $x$ on $b_{white}$ your play $x$ on $b_{black}$. The result is that you are playing the same position on both boards, only with different colors.


Is it possible to solve 3SUM in $O(n^2)$ time?

A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:

Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
For each $a \in A$:

Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. This can be done in $O(n)$ by traversing $B$ from the smallest to the largest and $C$ from the largest to the smallest. (Tip: Comparing $b + c$ with $k-a$ each time.)


Not multiplying by $2Cn/\delta$, does not result in

  ... Exact Cover having no solution if the optimal DTSP tour has length at least $L+\delta+Cn$.

It in fact would result in a length at least $L+\delta$. This length is not always greater than $L+ Cn$, hence the need to multiply all distances by $2Cn/\delta$, after which one obtains the authors' result : $2CnL/\delta+2Cn$.


Why is binary search faster than ternary search?

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:
 $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} > 1$, we actually get more comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.


Search Heuristics Where the Search Space Has No Gradient

Search heuristics will be useless on those kinds of problems.  It will effectively degenerate to brute-force search: trying all possibilities in hopes that one of them works.  That's very unlikely to find you the solution, except in the smallest possible problems, as its running time is exponential.

What else can you do instead?  You'll need to consider other kind of approach: e.g., a  SAT solver or ILP solver, an approximation algorithm or any of the other standard methods of dealing with NP-hardness.


Optimizing iteration over all permutations of a bit array

There's no possibility of an efficient algorithm here, unless you have more information about $T$. $T$ might only return true for one input and, in the worst case, you'd have to try all $2^n$ possibilities for that input before finding the right one. Or $T$ could return true iff its input contains $n/2$ $1$'s: there are exponentially many such strings and you'd have to try all of them to maximize $f$, since none of those strings is a binary subset of any of the others, so you have no information about the behaviour of $f$ on that set of strings.


Why doesn't a time cutoff convert NP problems into co-NP?

The mistake I made was in the very last step: flipping the result. Doing that requires more than an $\mathsf{NP}$ machine, because I'm recombining the massively parallel computation then doing something else. $\mathsf{NP}$ machines finish with the merging, they can't continue on.

To run my algorithm I'd need a machine with the ability to query an $\mathsf{NP}$ machine then continue. A $\mathsf{P^{NP}}$ machine can do that... but it makes sense that $\mathsf{P^{NP}}$ would contain $\mathsf{coNP}$.

See also: Oracle Machines (Complexity Classes), and the Polynomial Hierarchy.


Smallest segment after whose removal all elements are distinct

The idea is that you can check whether the answer is at most some value $m$ in time $O(n)$. Applying binary search on $m$, you obtain an $O(n\log n)$ solution.

How do you check whether the answer is at most $m$ in time $O(n)$? The idea is to slide a window of length $m$ across your array. If at some point all elements outside the window are distinct, then we are done.

How do we implement this sliding algorithm? Let $A$ be the original array. We initialize an array $M$ which contains the histogram of the elements in $A_{m+1},\ldots,A_n$, as well as the number of distinct elements $x$. If $x = n-m$ then we are done. Otherwise, we modify $M$ to contain the histogram of $A_1,A_{m+2},\ldots,A_n$:

We remove one copy of the element $A_{m+1}$ from $M$. If the new count of this element is $0$, then we decrease $x$.
We add one copy of the element $A_1$ to $M$. If the new count of this element is $1$, then we increase $x$.

In this way, we can update $M$ in time $O(1)$ per shift.

The solution you link to does all this, apart from maintaining $x$; this is done automatically by the C++ map data structure.

Another point is the time complexity of this solution, which might depend on your exact computation model.


IA network that is path-consistent, but not consistent

Yes, you are correct.

Here is the classic example of an interval algebra network that is path consistent, but not consistent. It appears in Allen, James F. (26 November 1983) "Maintaining knowledge about temporal intervals". Communications of the ACM. ACM Press: 832–843. doi:10.1145/182.358434.

It seems the arc between interval $B$ and $C$ in the above figure is missing its arrowhead. However, you can assign either direction to that arrow since the relationship $(d\ di)$ is symmetric.

  It should be noted that this algorithm, while it does not generate inconsistencies, does not detect all inconsistencies in its input. In fact, it only guarantees consistency between three node subnetworks. There are networks that can be added which appear consistent by viewing any three nodes, but for which there is no consistent overall labeling. The network shown in Figure 5 is consistent if we consider any three
  nodes; however, there is no overall labeling of the network. To see this, if we assign the relationship between $A$ and $C$, which could be $f$ or $fi$ according to this network, to either $f$ alone, or $fi$ alone, we would arrive at an inconsistency. In
  other words, there is no consistent labeling with $A-(f)\to C$,
  or with $A-(fi)\to C$, even though the algorithm accepts $A-(f\ fi)\to C$.

I would encourage you to read that seminal paper by Allen for more information.


$m/p$-equivalence holds after union with an arbitrary finite language

Hint: You could prove that $A\cup C\equiv_p A$. For both directions, try functions in the form
$$h(w)=\left\{\begin{array}{ll}w & w\notin C\\ \textrm{something hardwired} & w\in C.\end{array}\right.$$


For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$.
It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.

It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.

Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.


Prove that there is no computability reduction HP $\le$ $\Sigma$*

Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions.

Suppose towards a contradiction that such a reduction exists and is computed by a Turing machine $M$. Furthermore, let $M'$ be a decider for $L'$. Then there is a Turing machine which solves $L$, namely by directly simulating $M$, answering all of its oracle queries by simulating $M'$ on them, and, at the end, answering what $M$ does. This contradicts $L \not\in \textsf{R}$.

The case of the halting problem follows from it not being in $\mathsf{R}$ (since it is not even in $\mathsf{RE}$) and, naturally, $\Sigma^\ast \in \mathsf{R}$.

An aside: If you find the idea of classes closed under Turing reductions interesting, I suggest you look up the computation-theoretical notion of Turing degree. $\mathsf{R}$ would be the "base case" (i.e., degree zero) in that context.


Optimization problem over bidirectional connected graph

This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you don't select).  It presumably remains NP-hard, but can be solved by a number of methods.  Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to it.


Problem with understanding the Mathematical Equations related to Testing Tool

They are statements about patterns of correct and incorrect code:

For all call sites L1, there does not exist a store site L2 such that ... (and here I’m not clear—is that L2 may follow L1? Or that the truth of the statement may follow from the program, depending on L1 and L2?)
For all call sites L1, there exists a store site L2 such that ... (idem.)


Best algorithm to make a smooth route through a raw set of GPS-points with some errors?

Use a Kalman filter.  This is a powerful way to smooth the data to eliminate noise, in a way that takes into account the dynamics of how physical objects move.


Convex Hull algorithm - why it can't be computed using only comparisons

For a slightly more general way of looking at this, what you want to do is equivalent to saying you can reconstruct the convex hull from the orderings induced by projections onto the coordinate axes.

To see you can't do this, just observe that for three points $a$, $b$, and $c$, knowing that $a < c < b$ in both projections doesn't let you figure out whether $c$ is above, below, or on the segment $ab$.  (Start with $c$ on the segment and then perturb it up or down by a small amount.)

This indicates that you'll need the "left turn" and "right turn" predicates.


m-CNF formulas satisfiability approximation

If such a constant-factor approximation algorithm would exist, and it would run in polynomial-time, you could use it to solve CNF-SAT in polynomial time. Since CNF-SAT is NP-hard, this may give you the desired result.

Sketch:
Given a CNF-formula f, feed sufficiently many copies of the formula to your approximation algorithm. If f is not satisfiable, the algorithm must always output 0. If f is satisfiable,  it should output a number > 0 (at least, if the other numbers are chosen correctly).


MergeSort k arbitrary words in linear time

General case:

If there is a linear time sorting algorithm $\mathcal{A}$ for this problem, then one can divide a list into random parts, and use $\mathcal{A}$ to sort. But comparison based sorting has a lower bound $\Omega(n \log n)$. Therefore there is no such algorithm $\mathcal{A}$.

Note: Merge routine combines sorted arrays into one sorted array. There is a similar problem to your problem called k-way merging, but that is also required sorted arrays. The complexity of k-way is $\mathcal{O}(n \log k)$

Finite alphabet case:

If we assume that the alphabet is finite, and in your case it seems only lower case letters then one can use the Counting Sort algorithm.

Assuming that the total length of the words is $n$ and there are at most $t=26$ letters, the Counting sort can sort this array in $\mathcal{O}(n+t)$-time.

To achieve this with Counting sort, you need to convert this into an array and map the letters with an integer. And, call;

 countingSort(array,26)

The Counting sort is not in-place. The space requirement for this question is $\mathcal{O}(t)$

Note 1: Counting sort is not a comparison based sorting algorithm, it uses counting, thus it is not bounded by the lower bound of the comparison based sorting algorithms.
Note 2: Counting sort, also, can be implemented stable.


If L is a regular language then the language replace(L,σ,τ) is also regular

Let $A$ be the alphabet and let $a$, $b$, $c$, ... be the letters
(this is easier to type).

Hint.
Consider the (non-deterministic) transducer $A^* \to A^*$ defined by $1 \xrightarrow{c \mid c}1\xrightarrow{a \mid b} 2 \xrightarrow{c \mid c} 2$
(more precisely, there are transitions $1 \xrightarrow{c \mid c} 1$ and $2 \xrightarrow{c \mid c} 2$ for any letter $c$ of $A$, including $a$ and $b$, but there is a single transition form $1$ to $2$). For each transition, the left hand part of the label is the input letter, the vertical bar is a separator and the right hand part is the output letter.


Are the following Big Oh Notations equivalent?

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$.  If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$.

For a more formal treatment, try to rewrite each of your statements that involve big-$O$ in terms of "There are constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n)\leq k\,g(n)$." You'll probably find that it's not even clear what these formal statements should be and that, if you manage to figure that out, then some of the formal statements will be false.

The underlying point you've overlooked is that big-$O$ provides upper bounds but, if you have a quotient $a/b$ then upper-bounding that quotient requires upper-bounding $a$ and lower-bounding $b$. Big-$O$ can't express that lower bound.


Given a set of sets, find the smallest set(s) containing at least one element from each set

The problem is the well-known NP-complete problem Hitting Set. It is closely related to Set-Cover. The NP-completeness proof can found in the classic book of Garey and Johnson.

If you want to approximate it, you might want to translate your instance first to Set-Cover, and then apply an approximation algorithm for Set-Cover. However, Set-Cover cannot be be approximated by a constant factor in polynomial time, unless P=NP as shown by Lund and Yannakakis.

If you are interested in exact solutions and your inputs behave nicely, I would recommend using a fixed-parameter tractable. The running time is here not only expressed in terms of the input length $n$ but also in terms of an additional parameter $k$. If the running time is $O(f(k)\cdot n^{O(1)})$, we call the algorithm a FPT-algorithm. Here, $f(k)$ is an increasing function. So if $k$ is constant we have a polytime algorithm. The first chapter of the book by Flum and Grohe, explains an FPT-algorithm for hitting set (more precisely for $p$-card-hitting set). The algorithm is easy to implement and uses the method of bounded search trees. Still it needs to much space to explain here, basically you break down the necessary(?) brute-force search, into small pieces (when $k$ is small).


$\ell_1$ Minimization of Probability Distribution and KL-Divergence

Have you looked into Jensen-Shannon Divergence? It avoids the situation you described by adding a midpoint. Formally we have,
$$\mathrm{JSD}(P||Q) = \frac{1}{2} \mathrm{KL}(P||M) + \frac{1}{2} \mathrm{KL}(Q||M)$$ where $M = \frac{1}{2}(P + Q)$. Informally, JSD is nice when you want to compare distributions that seem to have the same shape, but dont completely overlap.


Do networking ports come from "port-mapped I/O"?

Moving my comment to an answer, while the word "port" is being used in the same non-technical sense for both "port-mapped I/O" and for "network ports", they have literally no technical connection.

In port-mapped I/O, the "ports" are accessed with special CPU instructions (in, out in the x86 family) which communicate with hardware devices. For x86, at least, due to the limited "address space" of port-mapped IO (and other reasons), memory-mapped IO or direct memory access are used for bulk data movement. There's nothing magical about port-mapped I/O.  Modern ARM processors, for example, don't have it at all and instead rely entirely on memory-mapped I/O.

Network "ports" are just pieces of data in TCP or UDP packets to allow multiplexing connections to a single IP address (or host because it technically could be over a network level protocol other than IP).  As far as the network hardware and CPU is concerned, the port is just another piece of data in the packet like any other.  The operating system will use the port to route the packet to the appropriate application on the host


Introductory book on Logic and Computation

My answer could be late for this question, but I hope it will be helpful for other people looking for similar information.

I had taken a course about Mathematical Logic at National University of Singapore, in which the lecturer used this textbook:

A Concise Introduction to Mathematical Logic, 3rd edition, by Wolfgang Rautenberg

Personally, I like both the textbook and the course a lot.

The textbook initially appears to be quite difficult to read. However, once getting familiar with it, it is much easier to follow since the system of notation is very clear, the content is self-contained and the approach is by starting from foundation, no vague assumption. For example, this book develops the natural deduction calculus and Hilbert calculus, or prove two incompleteness theorems of Kurt Gödel from scratch.


Complexity of parity game solving compared to PLS, PPA, and PPAD

Yes, solving parity games is known to be in PPAD (and thus PPA and PPP too) and PLS, and is thus unlikely to be hard for either (since this would imply containment of one of these classes in the other).

See, e.g.,

Daskalakis, Constantinos, and Christos Papadimitriou. "Continuous local search." Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011.

and combine the membership of Simple Stochastic Games (SSGs) in CLS (which is in PPAD and PLS) with the well-known observation that solving parity games can be reduced to solving SSGs in polynomial time.

The reason that these problems are in PPAD is that they admit "optimality equations", rather like Bellman equations, that characterize solutions as fixed points. The reason these problems are in PLS is that they can be solved with local improvement algorithms like strategy improvement (a two-player generalization of policy iteration for MDPs).


An encoding algorithm with an expensive encoder and a cheap decoder

There is a public-key scheme that achieves this, based on timelock cryptography.  It is parameterized by a parameter $t$, which controls how slow encoding is.  The time to encode (without knowledge of the private key) will be about $O(t)$; the time to decode (with knowledge of the private key) will be about $O(1)$; and the time to generate a private-public keypair (which should probably be counted as part of the running time spent by the decoder) is approximately $O(\lg t)$.  Consequently, by making $t$ sufficiently large, you can have an arbitrarily large ratio between the time to encode and the time to decode.

The specific construction is based on timelock cryptography and the Rabin cryptosystem.  Generate a RSA modulus $n=pq$ that has the following special form: $p=4u-1$, $q=4v-1$, $u \equiv v \pmod 2$, and $\gcd(p-1,q-1)=2$, where $u,v$ are integers.  Let $\alpha$ be the integer such that $\alpha \equiv u \pmod{p-1}$ and $\alpha \equiv v \pmod{q-1}$.  Pick a positive integer $t$, and compute the exponents $e=2^t \bmod \varphi(n)$ and $d = \alpha^t \bmod \varphi(n)$, where $\varphi(n)=(p-1)(q-1)$.  Make $n,t$ public.  The private key is $d$.

To encode a message $x$, you represent your message as a number $x$ that is a perfect square modulo $n$, a la Rabin's cryptosystem.  Then compute $E(x) = x^{2^t} \bmod n$.  This can be computed by repeatedly squaring $x$ (do it $t$ times).

To decode a codeword $y$, you compute $D(y) = y^d \bmod n$.  Given knowledge of the private key, this can be computed efficiently, regardless of the value of $t$.

The person who creates the keypair can compute $d$ efficiently, using $O(\lg t)$ modular squaring operations (compute $\alpha$ using the Chinese remainder theorem, then compute $d$ using fast modular exponentiation, using knowledge of the factorization of $n$).

The parameter $t$ controls the time to encode.  By choosing $t$ sufficiently large,  you can make encoding 10 seconds.  In contrast, decoding takes constant time (you can choose RSA parameters so that you can decode in 0.01 seconds).  Or, to put it another way, creating the keypair takes $O(\lg t)$ time; encoding takes $O(t)$ time; and decoding takes $O(1)$ time.  Therefore, the designer of the scheme can choose how long it takes to encode and how big the gap between encoding vs decoding will be.

This is basically the reverse of a timelock puzzle / timed-release cryptography.  See https://crypto.stackexchange.com/q/606/351, Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?, and Is it possible to create a "Time Capsule" using encryption?.

Why does this scheme work?  In other words, why does decoding undo the encoding operation?  It works for basically the same reason the Rabin cryptosystem works.  In particular, raising to the $\alpha$th power computes a square root modulo $n$: raising to the $(p+1)/4=u$th power modulo $p$ computes a square root modulo $p$; raising to the $v$th power computes a square root modulo $q$; and by the Chinese remainder theorem, raising to the $\alpha$th power does both simultaneously, thus computes a square root modulo $n$.  Thus $f(x)=x^2 \bmod n$ is a one-way permutation on the set of squares (quadratic residues) modulo $n$, and its inverse is $g(y)=y^\alpha \bmod n$.  The crucial thing is that, without knowledge of the factorization of $n$, there is no known way to speed up repeated application of the function $f$; but with knowledge of $n$, you can dramatically speed up repeated application of the function $g$.  So, encoding involves iteratively applying $f$; decoding uses the trick to apply $g$ many times, but faster than the naive method.


How to calculate the time complexity of a Catalan-like recurrence by substitution?

You can use induction. First, check directly that $P(n) \geq 2^{n-2}$ for all $n \leq 4$ (the relevant values are $1,1,2,5$). Now suppose that $P(n) \geq 2^{n-2}$ holds for all $n \leq m$, where $m \geq 4$. Then
$$
P(m+1) = \sum_{k=1}^m P(k) P(m+1-k) \geq \sum_{k=1}^m 2^{k-2} 2^{m+1-k-2} \geq m 2^{m+1-4} \geq 2^{m+1-2},
$$
since $m \geq 4$.


Approximation algorithm for weighted set cover, using multiplicative weights

Yes, fractional weighted set cover and, indeed, all explicitly given packing/covering LP's can be solved using multiplicative-weights algorithms in poly time independent of the width. There are many papers in this line of work. The earliest are probably due to Garg and Konemann. See e.g. https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 .


What is the meaning of undecidability in Rice Theorem?

Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems.


Combinatorial Optimization: Shortest distance given sets of drivers and riders

These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have).

My favorite "big hammer" for this kind of scheduling problem is to use integer linear programming, as that has been used successfully for a number of different scheduling and operations research tasks.

The best way to formulate this as an ILP problem may depend on the parameters (how many drivers and riders you have), but let me describe one illustrative approach.  Suppose each car can have up to 5 riders.  Then consider all possible ways to choose a combination $S$ of 1 driver and up to 5 riders.  For each such, compute the total distance $d_S$ of the shortest route that involves that driver picking up all riders and taking them to the destination (this might involve $5!=120$ shortest-path computations).  Now introduce a zero-or-one variable $x_S$ for each combination $S$, with the intended meaning that $x_S=1$ means we select that combination.  We require that each participant is selected exactly once; thus, for each participant $p$, we add the equality $\sum_S x_S = 1$, where $S$ ranges over all combinations with $p \in S$.  Then, we minimize the linear objective $\sum_S d_S x_S$, where $S$ ranges over all combinations.  This ensures we minimize the total distance, while ensuring every participant reaches the destination.

Then, apply an off-the-shelf ILP solver.  If the number of riders and drivers is small enough, it should find an optimal solution.  If it is taking too long, many ILP solvers will let you terminate them early and report the best solution found so far, which may be effective at finding a good but not optimal solution.

This particular formulation might work well if the number of riders is not too large.  If the number of riders is very large, you might need to consider other formulations.


Can an alphabet for a Turing machine contain subsets of other alphabets?

An alphabet is a set of symbols, therefore if your you treat $\{a,b,c\}$ as a single symbol (in some other alphabet), it is a valid alphabet.


Classification problem where one attribute is a vector

Yes.  If you have a non-trivial data set of this form, this would be a reasonable fit for statistical analysis.

For independent variables, you have one binary feature for each core item (indicating whether that item was purchased or not); the outcome is a binary variable (win or loss).  Accordingly, one reasonable approach would be to try logistic regression.  You'll have one independent variable $X_i$ for each item; $X_i=1$ means that item $i$ is one of the 6 items that the champion purchased in this game, $X_i=0$ means item $i$ was not purchased.  You'll have a dependent variable $Y$; $Y=1$ means that the champion won this game, $Y=0$ means the champion lost.  Then logistic regression will tell you which items tend to be associated with winning games.

There are other methods you could try as well: pretty much any method for supervised classification that works well with binary/categorical variables.

The one thing I don't recommend you do is multiply the item codes.  That's not going to help.  Instead, just have 20 features, where each feature indicates whether a particular item was purchased or wasn't.


Equivalence of two lambda expressions for NOT

In order to prove the two NOT forms are not generally equivalent, all you have to do is find a term that when each is applied, returns a different result such as:

$NOT1 \; \lambda x.\; x \; \;\;=\;\; (\lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t )) \; \lambda x.\; x \;\; =\;\; \lambda x. \; x \; $

$NOT2  \; \lambda x.\; x \; \;\;=\;\; (\lambda x.\lambda t.\lambda f.xft)  \; \lambda x.\; x\;\; =\;\; \lambda t.\lambda f. ft \; $


How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1?

You can write your recurrence as
$$
T(n) = \sum_{i=1}^k a_i T(b_i x + h_i(n))  + g(n)
$$
with:

$k=2$
$a_1 = a_2 = 1$
$b_1 = \frac{1}{2}$, and $b_2 = \frac{1}{3}$
$h_1(n) = h_2(n) = 0$
$g(n) = 1$

From Akra–Bazzi theorem, the solution to your recurrence is $T(n) = \Theta\Big( n^p \big(1 + f(n)\big)\Big)$, where $p$ is such that $a_1 b_1^p + a_2 b_2^p =1$ and $f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u$.

Substituting, we have $2^{-p} + 3^{-p} = 1$, which shows that $0.78 < p < 0.79$.

Therefore: $$
f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u \le \int_1^\infty \frac{1}{u^{p+1}} \text{d} u = \frac{1}{p} = \Theta(1),
$$

and the solution to your recurrence is $T(n) = \Theta( n^p )$.


Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?

For that I take:

  x:a ; y:b ; z:c

You can't do that. You have to first give a pumping length $p$ and then you have to show that there is no decomposition of the word $abc$ into $xyz$ with $|y|\ge 1$ and $|xy| \le p$ for which $xy^n z \in F$. If we take your word $abc$ and decompose as $x=\varepsilon$, $y = a$, $z=bc$ then the pumped words are $a^nbc$ and are all in $F$.


How to extend Bellman-Ford to solve the $k$ shortest path routing?

It seems that we can use the following generalization of Bellman-Ford. Let's store a set $Pt_{v}$ of $k$ numbers for each vertex $v$ of graph $G$ which initially are all equal to $+\infty$. The only exception is a vertex $s$ (the vertex from which all paths are calculated). Its set $Pt_{s}$ should be initialized to a single value of $0$ and $k-1$ values of $+\infty$.

Now let's run $k \cdot |V|$ iterations of relaxations (instead of $|V| - 1$ iterations like in usual Bellman-Ford) and try to maintain the following invariant. After $i$-s iteration for each vertex $v$ the $j$-s least number from $Pt_{v}$ should be not greater than the length of the $j$-s shortest path from $s$ to $v$ containing not more than $i$ edges. This invariant will be maintained by means of proper edge relaxations. For each $(u, v)$ edge relaxation we should assign $Pt_{v}$ to a set of $k$ least numbers from a set $Pt_{v} \cup \{x + weight(u, v)|x\in Pt_{u}\}$.

So after all $|V|-1$ iterations each set $Pt_{v}$ will contain $k$ shortest paths from $s$ to $v$. The proof of correctness for this algorithm should be literally the same as for usual Bellman-Ford.

This is a loopy algorithm. Its time complexity is $O(|V|\cdot|E|\cdot k^2)$ (because single edge relaxation can be done in $O(k)$ time using a selection algorithm).


Least number of comparisons needed to sort (order) 5 elements

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

Sort the first two pairs.
Order the pairs w.r.t. their respective larger element.

Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.
Insert $e$ into $[a,b,d]$.
Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

See also Electronic Data Sorting by H.B. Demuth (1985)
Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)


Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

The complement of a deterministic context-free language is also deterministic context-free. Since $\{a^nb^nc^n \mid n \geq 0\}$ is not context-free, its complement cannot be deterministic context-free. However, the complement is context-free, since it can be written as follows:
$$
\overline{a^*b^*c^*} \cup \{a^{n+k} b^n c^m, a^n b^{n+k} c^m, a^{n+k} b^m c^n, a^n b^m c^{n+k}, a^m b^{n+k} c^n, a^m b^n c^{n+k} \mid n,m \ge 0, k \ge 1 \}
$$


There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path.  See https://en.wikipedia.org/wiki/K_shortest_path_routing.  I'd suggest that as a natural place to start.


Does there exist a type system for a non-let-polymorphic lambda calculus?

I am not sure what you mean by type system being decidable. I guess you mean type checking and type inference. (strictly speaking type inference is not a decision problem, although it can be casted as one and people usually think of it that way).

In addition to intersection types, I would also suggest looking at System F where universal quantification does not appear only at the let construct. For system F, type inference is undecidable: paper


How did MacLisp's garbage collector "run in the register set"?

The 16 high-speed registers of the PDP-10 ISA were addressible as locations 0-15 of physical memory, so that the code literally could run in the registers if it was short enough and you could devote a block of registers to it.  Not only could it use registers for temporary storage, it could use them as a code cache as well.


Integer linear programming formulation of formula in DNF

You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy your condition.  (That's because any system of linear inequalities forms a convex polytope.)

It's not quite clear to me from your question about what your condition is, so I'll try answering your question with both plausible interpretations I see.

Interpretation #1:

In the first possible interpretation, the boolean formula is $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$.  This means the polytope needs to contain all of the following seven points:

$$(0,1,1,1), (1,0,0,1), (1,0,1,1), (1,1,0,0), (1,1,0,1), (1,1,1,0), (1,1,1,1)$$

and not any of the other nine points where the formula is false.

There are various ways to check whether there exists such a polytope.  One way is to enumerate all possible inequalities $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 + c_5 \ge 0$ and look for combinations $(c_1,\dots,c_5)$ such that this inequality is true for all of the seven points listed above.  Then, we check whether a system of constraints obtained by using all of those inequalities has the desired property (in particular, each of the other nine points violates at least one of these inequalities).  You can then minimize the set of constructed inequalities, to remove redundancies.

Here is one such system of constraints that works:

$$\begin{align*}
x_2+x_4-1 &\ge 0\\
x_1+x_3-1&\ge 0\\
x_1+x_2-x_3+x_4-1 &\ge 0
\end{align*}$$

Another way to have obtained this system of constraints would be to convert the DNF formula you listed to CNF, and then translate each "OR" constraint into a single inequality using the techniques from Express boolean logic operations in zero-one integer linear programming (ILP).  The formula $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$ is equivalent to $(x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_1 \lor x_4) \land (x_2 \lor x_4)$.  That then yields the following system of constraints, which also works:

$$\begin{align*}
x_1+x_2-1 &\ge 0\\
x_1+x_3-1 &\ge 0\\
x_1+x_4-1 &\ge 0\\
x_2+x_4-1 &\ge 0
\end{align*}$$

Interpretation #2:

In the second plausible interpretation, you want the boolean formula

$$(x_1 \land x_2 \land \neg x_3 \land \neg x_4) \lor (\neg x_1 \land x_2 \land x_3 \land x_4) \lor (x_1 \land \neg x_2 \land \neg x_3 \land x_4).$$

Thus, you want the polytope to contain only the three points

$$(1,1,0,0),(0,1,1,1),(1,0,0,1).$$

We can apply the same methods to get a system of inequalities for this formula.  Here is one solution that works:

$$\begin{align*}
-x_1-x_3+1 &\ge 0\\
-x_2+x_3-x_4+1 &\ge 0\\
x_2+x_4-1 &\ge 0\\
x_1+x_3-1 &\ge 0\\
x_1+x_2-x_3+x_4-1 &\ge 0
\end{align*}$$


Selecting items from two arrays without duplicate indices to get maximum sum

There are two ways to interpret the problem.

$k$ is part of the input

Let $a=(a_1, a_2, \cdots, a_n)$ and $b=(b_1, b_2, \cdots, b_n)$ be the two given array. Suppose we have chosen $k$ values from array $a$, $a_i$ where $i$ ranges over some index set $I$ that has $k$ elements. Then we have to choose the $n-k$ values from array $b$, $b_j$ where $j$ ranges over all indices that are not in $I$. The sum of all numbers are

$$\sum_{i\in I}a_i+\sum_{i\not\in I}b_i=(\sum_{i\in I}a_i-\sum_{i\in I}b_i) + (\sum_{i\in I}b_i+\sum_{i\not\in I}b_i)=\sum_{i\in I}(a_i-b_i)+\sum_ib_i$$

Since $\sum_ib_i$ is a constant, the sum reaches the maximum if $\sum_{i\in I}(a_i-b_i)$ reaches the maximum. So we can select the $k$ largest elements in the array $a-b=(a_1-b_1, a_2-b_2, \cdots, a_n-b_n)$. The indices of the those elements are the indices of the elements in $a$ that we should choose.

The $k$ largest element can be selected in $O(n)$ time using quickselect, this algorithm can be implemented in $O(n)$ time. It can also be implemented in $O(n\log n)$ easily by sorting the array $a-b.$

$k$ is not part of the input

Solve the previous problem  for $k=0$. Let the maximum sum obtained by $m_0$.
Solve the previous problem again but for $k=1$. Let the maximum sum obtained by $m_1$.
And so on.

Find the maximum number among $m_0, m_1, \cdots, m_n$. That is the maximum sum we want in this interpretation the problem. A bit of extra bookkeeping will let us know the numbers we should select to reach that maximum sum.

Exercises

Exercise 1. How about the case of smallest sum?

Exercise 2. How about exactly $k-1$ values from the first array and $n-k$ values from the other array?


Proving that the scramble of a regular language is context-free

First, two remarks. When $L = (01)^*$, we have $\newcommand{\scramble}{\mathrm{SCRAMBLE}}\scramble(L) \cap 0^*1^* = \{ 0^n 1^n : n \geq 0 \}$, and this shows that we can't expect $\scramble(L)$ to be regular.

Second, when $L=(012)^*$, we have $\scramble(L) \cap 0^*1^*2^* = \{ 0^n 1^n 2^n : n \geq 0 \}$. This shows that it's important that the alphabet have only two symbols.

Now for the proof. It is actually enough to assume that $L$ is context-free (and not necessarily regular). For a word $w$, let $p(w) = (\#_0(w),\#_1(w))$, and define $P(L) = \{ p(w) : w \in L \}$. Parikh's theorem states that $P(L)$ is a semilinear set, that is, a finite union of sets of the form
$$
x + \sum_{i=1}^m \mathbb{N} y_i,
$$
where $x,y_1,\ldots,y_m \in \mathbb{N}^2$. It is thus enough to show that for every linear set $S$, the language $L(S)$ of words $w$ such that $p(w)$ belongs to $S$ is context-free.

A pushdown automaton accepting $L(S)$ proceeds as follows. We will assume for simplicity that $x = (0,0)$; for general $x = (x_0,x_1)$, the PDA will ignore the first $x_0$ zeroes and $x_1$ ones, but will only accept if these actually appear.

When the PDA starts running, it guesses a mode $i \in \{1,\ldots,m\}$. When it reads $0$, it pushes it to the stack. Meanwhile, it keeps track of the number of $1$s it has read. Once it has read $(y_i)_1$ of them, it removes $(y_i)_0$ zeroes from the stack (pushing, if necessary, "negative" $0$s which will get cancelled later with actual $0$s). Then it guesses another mode $i \in \{1,\ldots,m\}$ (possibly the same one).

Upon reaching the end of input, the automaton verifies that it hasn't read any $1$s in its current phase, and that the stack is empty. This completes the construction. We leave it to the reader to prove that it actually works.


calculting distance between a person and the object in the image

No, it's not possible without extra information.  Just think: if the house was 20 feet tall and 100 feet away, you couldn't distinguish that from the case where the house was 30 feet tall and 150 feet away.  Those two would lead to exactly the same image.
Here are some possible options you could consider:

If you have two pictures of the same house taken from two different positions, and you know the relative positions (e.g., one was 10 feet to the right of the other), then you may be able to infer the distance to the house, using parallax.

If you know the height of some feature in the image -- say, the door -- and you know all of the camera parameters (in particular, the angular resolution of a single pixel or of the field of view), then you can work out the distance to the house.  So if you could calibrate the camera in advance, and make a guess/assumption about the height of the door, you could draw an inference about the distance to the house.
However this does require knowing all the camera parameters, which will probably require some calibration; I just knowing the image format, resolution, etc. and the camera resolution etc. will not be enough, and even knowing the model of the camera will probably not be enough. (Possibly if you knew the exact model of the camera and could go buy another camera of the same model, you might be able to calibrate the second one and assume both cameras have the same calibration.  I don't know if that would work.)

See also Using Headpose Vector and 2D Points to Compute Distances.  You might also look into camera intrinsics, camera extrinsics, the pinhole camera, and similar topics from computer graphics / computer vision.