Gas Station Problem - Dijkstra's Algorithm variation

We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with some arbitrary cost of refilling - the cost here wouldn't matter. So in effect, we set $S = S \cup \{\text{source, target}\}$.

In the first phase of the algorithm, for every $s \in S$, we want to find all the other towns in $S$ that we can reach without refueling, if we start out with a full tank from $s$. For this, we can take two approaches:

Run Floyd–Warshall using $w(u, v)$ as the weight of every edge, to find the shortest distance from any town to any other. Now, for every $s \in S$, we iterate through every other $t \in S$ and if the shortest distance from $s$ to $t$ is $\leq k$, then we can reach $t$ from $s$ without refueling. So we create a new graph $G'$, whose vertex set is $S$, and add a directed edge $(s, t)$ with a weight of $c(s)$. This approach takes $\mathcal{O}(|T|^3)$ time and $\mathcal{O}(|T|^2)$ space.
Another way to construct the same $G'$, would be to start a Dijkstra's from every $s \in S$, and stop when the distance is more than $k$, which in the worst case wouldn't help our complexity. This approach would require $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.

The second approach is asymptotically better than the first one, but the first one is easier to implement. So you can decide which fits your needs better.

Now on to the second phase of the algorithm, where we have the graph $G'$ with us, which again is a directed weight graph, but now the weights are costs of refilling. So all we have to do is run a Dijkstra's on this graph starting from $\text{source}$. The answer is the shortest distance to $\text{target}$.

So the total algorithm needs $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.


What are definite languages? How do you formally define them?

A language L is definite if there is some k(> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w.

There is of course room for interpretation here. Assuming they mean "[it] only depends on the last $k$ symbols of $w$", here's a slightly more precise rephrasing:

  A language L is definite if there is some $k$ so that all words that share the same $k$-suffix are either in or not in the language.

Try to work from here.


Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$

Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log_2 n) \cdot x$, since at each step we subtract at most $\log_2 n$, and thus it takes t least $n/\log_2 n$ steps to reach zero.

In the other direction, denote by $m$ the current input ($n$, $n-\log_2n$, and so on). As long as $m \geq n/2$, the input decreases by at least $(\log_2 n)/2$ at each step, and so it takes at most $2n/\log_2 n$ steps to reach $n/2$. Then it takes at most $4\sqrt{n}/\log_2 n$ steps to reach $n^{1/4}$, and so on. After $\log\log n$ such phases, $m$ will be $O(1)$. This gives an upper bound proportional to $x$ times
$$
\frac{2n}{\log_2 n} + \frac{4\sqrt{n}}{\log_2 n} + \cdots \leq \frac{2n}{\log_2 n} + 4\sqrt{n} + 8n^{1/4} + \cdots + 2\log n \cdot n^{1/\log n} = \\
O(n/\log n + \sqrt{n} \log\log n) = O(n/\log n).
$$
Thus $T(n) = \Theta(xn/\log n)$.


Is there an example of Dinitz's algorithm running with the worst time complexity?

Dinic's algorithm runs in $O(|V|^2 \cdot |E|)$ time, so it might never make $|V|^2 \cdot |E|$ steps.
Finding a single example is insufficient, as any finite-size counterexample can be "hidden" as a constant in asymptotic notation. You will need an infinite sequence of networks of strictly increasing size with a lower time bound of $\Omega(|V|^2 \cdot |E|)$ to prove that the bound is indeed tight.


Comparison of Decision Trees: RTED vs MLE

The main difference between MLE and RTED is that RTED can compare any kind of decision tree even non binary such as CHAID. In addition, each of them has different approach for scanning the tree. MLE is from top down and find all the possible paths while RTED can go in breadth way.


Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

There is no reason to convert the Mealy machine to a deterministic one – indeed, this is not always possible. Suppose that the input alphabet is unary but the output is binary. A deterministic machine has one output of each length, but a non-deterministic machine can have many.

Instead, the idea is to construct an NFA which keeps track of both the Mealy machine $M$ and a machine $T$ accepting $L$. Denote by $w$ the (unknown) word in $L$ on which we run $M$. At each point in time we guess the next symbol in $w$ and transition in $T$, guess a corresponding transition in $M$, and "accept" the symbol output by the $M$-transition (if any). The accepting states of the NFA are those in which $T$ is at an accepting state.

I'll let you go over the details.


Integer Programming Traveling Salesman - Checking if Tour is Complete

First, an overview is as follows:

  The last constraints enforce that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.
  To prove this, it is shown below (1) that every feasible solution contains only one closed sequence of cities, and (2) that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

Interpreting the last constraints as a theorem:
$$u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n \Leftrightarrow \text{there is only a single tour covering all cities.}$$
then part (1) is the necessary condition ("$\Rightarrow$"): every feasible solution in ILP implies a unique tour; and part (2) is the sufficient condition ("$\Leftarrow$"): every single tour corresponds to (at least) one feasible solution.

For your questions:

  I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalities?

We aim to prove the part (1): every feasible solution contains only one closed sequence of cities. To this end, we should exclude the case that two or more disjointed subtours that only collectively cover all cities: For instance, subtours $0 \to 1 \to 2 \to 0 \bigcup 3 \to 4 \to 3 \bigcup 5 \to 6 \to 5$ covering all cities $0, \cdots, 6$ is not a legal tour, but it does satisfy the first and the second set of equalities.

Consider any subtour which does not pass through the city $0$ and sum the inequalities of $u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n$ for the subtour (taking $3 \to 4 \to 3$ as an example):

Summing up $$(u_3 - u_4 + n \cdot 1 [x_{34} = 1] \le n-1) \text{ and } (u_4 - u_3 + n \cdot 1 [x_{43} = 1] \le n-1),$$ we have $$2n \le 2 (n-1).$$

Generally, for a subtour (which does not pass through the city $0$) with length $k$, we will get $nk \le (n-1) k$. Contradiction.

Therefore, every subtour must pass through the city $0$. Further, the first and the second equalities enforce that all subtours must be disjoint. As a consequence, there can only be a single tour covering all cities.

  I guess I don't understand how this detects that we pass through all the nodes.

As I mentioned in the "overview", part (2) is the sufficient condition: We are given a single tour covering all cities, we aim to show that this tour corresponds to some feasible solution in this ILP. Because such a given tour trivially satisfies other constraints which do not involve these $u_i$ variables, it suffices to show that there are values for $u_i$ that satisfy the last constraints. This is proved by construction: Choose $u_{i}=t$ if city $i$ is visited in step $t$.


In bit recoding multiplication, e.g.   01101 times 0, -1, or -2.

For multiplying with -1:
Take 2's complement of 01101 i.e: 10011
For multiplying with -2:
Add 2's complement of 01101 i.e: 10011 + 10011= 100110


Remove $u$ and $v$ (as well as all edges connected to them), and for any removed edge $(u,x)$, add an edge from $s$ to $x$ with the same capacity; for any removed edge $(y,v)$, add an edge from $y$ to $t$ with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including $e$ in the original graph.


Thre are multiple algorithms already developed like Dijkstra's algorithm, Bellman-Ford algorithm or A* search algorithm.

The problem you face is also well described on Wikipedia.

Maybe there is something specific about your assignment like memory or time complexity?


Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n

Let me show you how to solve these without using the master theorem. For the first item:

$$
T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n.
$$
This shows that $T(n) = O(n\log n)$. Since clearly $T(n) = \Omega(n\log n)$, we can conclude that $T(n) = \Theta(n \log n)$.

The second item can be solved in the same way.


Well, the state should be dp[n], the optimal answer for some prefix of size n. Considering the different tiles, the transitions should be intuitive:
dp[n] = max(dp[n-2] + max(a[n], a[n-1]), dp[n-3] + max(a[n-1], a[n-2] + a[n]))
Of course, if any of the indices n-2, n-1, or n-3 are less than 0, then the involving terms should be omitted from the calculation. This is just a general representation of what the transition should be.


As mentioned in the question, obviously $O(nm) \subseteq O(n + nm)$ as $n,m \rightarrow  \infty $.

The reverse is also true when $n, m$ grow ever larger:

For all $n,m \geq 1  : m +nm \leq nm+nm = 2nm$ and so:
$O(m+nm)  \subseteq O(nm+nm) = O(2nm) = O(nm)$ as $n,m \rightarrow \infty$.

$O(2nm) = O(nm)$ as $n,m \rightarrow \infty$ is a property of big-O that follows directly from the definition.

With respect to the penultimate line in the question (the long sequence of equalities), there is some unusual notation. To make sense there, the product of two sets must be an element-wise product such as $O(n) \cdot O(m) =\{fg ∣ f∈O(n), g∈O(m)\}$. The ‘$+$’ sign before the first equal sign probably means the Minkowski sum A+B={a+b ∣ a∈A and b∈B} instead of A∪B, but in both cases the first equality would hold.


If it's a black box, you can't reduce it to SAT.  That's exactly what it means to be a black box: a black box is one where you can feed in any input $x$ you like, and get back $f(x)$, but where you know nothing about the structure of $f$ (for instance, you are not given an algorithm for $f$, you do not know the CNF for $f$, and so forth).

In particular, given only black-box access to $f$, in the worst case, you need $2^n$ queries to the black box to determine whether $f$ is satisfiable: you need to evaluate $f$ on every possible input, in the worst case.  Consider any algorithm which makes at most $2^n-1$ queries to the black box.  Suppose it got back $0$ as the answer to every query.  Then there is some input, say $x'$, which has not been queried.  Now the correct answer as to whether $f$ is satisfiable depends upon whether $f(x')=0$ or $f(x')=1$, but the algorithm has no clue which is the case.  No matter what the algorithm outputs, an adversary could always pick a $f$ (after the fact) that is consistent with all of the queries made to the black box but that makes the algorithm's output wrong.  Therefore, no deterministic algorithm can do better than $2^n$ queries, in the worst case.

It's not in EXPTIME, and it's not in NP, because it is an oracle problem, whereas NP and EXPTIME are for non-oracle problems -- but it is in the analogue of EXPTIME for oracle problems.... and in the analogue of NP for oracle problems, too.


An algorithm for k-way array partitioning

I can't even figure out how to do it out of place, other than allocating n dynamic sized arrays and finally concatenating them together.

Which is the approach used by the explanation in Wikipedia, so it's not necessarily a bad one.

  My question is: how to implement this efficiently, preferably in place?

I assume you know how to do a quicksort partition. To do the multi-way split in place, you can turn it into a series of quicksort partitions.

# Splitters are sorted
# min and max indices are inclusive
multipartition(array A, int Amin, int Amax, array Splitters, int Smin, int Smax):
    if Amax <= Amin:
        return
    if Smax < Smin:
        inner_sort(A, Amin, Amax)
    else:
        Smid = Smin + (Smax - Smin) / 2
        split_idx = partition(A, Amin, Amax, Splitters[Smid])
        multipartition(A, Amin, split_idx - 1, Splitters, Smin, Smid - 1)
        multipartition(A, split_idx + 1, Amax, Splitters, Smid + 1, Smax)

I assert that this is as efficient as the non-in-place approach based on binary search given in the Wikipedia article, because each element of A will take place in $\log(|\text{Splitters}|)$ calls to partition, which is linear time.


Representing a sentence using propositional logic

The sentence says that a male "is smart (S) if he is tall (S)", that gives $T \Rightarrow S$, but it also says "but otherwise is not smart", which gives $\neg T \Rightarrow \neg S$, and this is equivalent to $S \Rightarrow T$ by contraposition. Thus together this gives $S \iff T$ under the condition $M$. Therefore (b) is correct.


Upper bound on the number of subgraphs in a tree

Let us prove by induction that any tree on $n$ vertices has at least $2^{n-1} - n$ induced disconnected subgraphs.
When $n = 1$, this is clear since $2^{n-1} - n = 0$. Now suppose $n > 1$, and let $T$ be a tree on $n$ vertices. Choose an arbitrary leaf $v$, let $T'$ be the tree obtained by removing $v$, and suppose that $v$ is connected to $u \in T'$. By induction, $T'$ has at least $2^{n-2} - (n-1)$ induced disconnected subgraphs. Each of these correspond to two induced disconnected subgraphs of $T$, one including $v$ and one not including $v$. Moreover, for any $w \in T'$ different from $u$, the subgraph induced by $\{v,w\}$ is disconnected, and does not arise from an induced disconnected subgraph of $T'$ (since the subgraph of $T'$ induced by $\{w\}$ is connected). In total, we get this many induced disconnected subgraphs of $T$:
$$
2(2^{n-2} - (n-1)) + (n-2) = 2^{n-1} - 2(n-1) + (n-2) = 2^{n-1} - n. \quad \square
$$
This is tight, as the example of a star shows. If the center of the star is $x$ and the other vertices are $y_1,\ldots,y_{n-1}$, then the subgraph induced by any subset of $\{y_1,\ldots,y_{n-1}\}$ of size at least 2 is disconnected. There are $2^{n-1} - (n-1) - 1 = 2^{n-1} - n$ of these.


Why is the number of states for DFA is 3n + 1 for this language

This is indeed a curious example. The reason why it works is the following (I show you on the example of $L_3$, but the argument is generic).
Start with the minimal DFA accepting $\{S_n\}$, which clearly has $|S_n| + 1 = 3n + 1$ states. The states can be encoded by factorisations of $S_n$ in two factors (the reason of this encoding will appear shortly). Thus for $S_3$ you get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{0} (000, 111111) \xrightarrow{1} (0001, 11111) \xrightarrow{1} (00011, 1111) \xrightarrow{1} (000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
Now it is possible to accept the words $S_i$ by adding new transitions (but no new state!). For instance, if you want to accept $011$, you add the transition $(0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1)$ to get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
and to accept $001111$, you add the transition $(00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111)$ to get
$$
(\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
The trick is that you still get a deterministic automaton, due to the choice of the words added to the original automaton.


Lower bound on space of DFS keeping the running time linear

The questions as stated seems to be beyond reach. Without the time constraint, a superlogarithmic space lower bound on your question would imply that $\mathsf{L} \neq \mathsf{NL}$, a famous conjecture in complexity theory.

What you are looking for is known as a time-space tradeoff, and these are not known for the RAM model, though similar results are known for restricted models such as the cell-probe model and comparison-based algorithms with memory (modeled as branching programs).

Time-space tradeoffs for reachability have been studied under the JAG model and its variants, which is a pebbling-based model. The best known time-space tradeoff, due to Edmonds and Poon, implies that polynomial time requires space roughly $\Omega(n/2^{O(\sqrt{\log n}})$, and this has been achieved by Barnes et al. in their paper A sublinear space, polynomial time algorithm for directed $s$-$t$ reachability. (The work of Edmonds and Poon is cited by Barnes et al.)


How to show the function is not Turing computable?

Since I assume this is a homework question, I won't give a fully detailed proof but rather a sketch with some gaps to fill.

Consider the function
$$g(x)=
\begin{cases}
  x+1 & \text{ if } \varphi_x(x)\downarrow\\
  \uparrow & \text{ otherwise}.\end{cases}$$
This function is computable (convince yourself of that!), so it has an index $e$.

Now consider the function $f$ on $e$, then computing $f(e)$ comes down to verifying whether $\forall n\  \varphi_e(n)\uparrow$. Can you see why this contradicts that the halting problem is not computable?


How to calculate the number of weights for a CNN?

Each receptive field of a filter has a weight. Furthermore, the whole filter has a single bias.
This gives for a single filter:
2*2*1+1 = 5 weights per filter.
5 filters * 5 weights = 25 weights for all filters.
The conv layer produces shape (4, 4, 5) if we assume the stride is 1.
The fully connected output layer (dense layer) has 5 neurons. Each of them is connected to the output of the conv layer.
So it's (4*4*5) * 5 neurons = 400 connections. Each of these connections has a weight. Each neuron in the dense layer also has a bias, so there are 5 more weights.
To sum up: 25 parameters for conv layer, 405 parameters for dense layer. 430 in total.


tl;dr: we can show that they are in fact isomorphic. Defining two different instances over them does not make them different. Defining two different functions over two types does not make them non-isomorphic! The instances are not describing an initial algebra structure, the data keyword is. As you say, the two instances play no role in the specification of the initial algebra.

In our example, we work with algebras
for the functor $1 + -$. That is, an algebra $A$ is given by a morphism $1 + A \to A$, or, in other words, an element of type $A$, which can be seen as a morphism $1 \to A$, and an endomorphism $A \to A$.

data Nat0 = Zero | Succ0 Nat0
data Nat1 = One | Succ1 Nat1

Here, Zero and One are the elements while Succ0 and Succ1 are the endomorphisms. We will see that they are isomorphic as F-algebras. A morphism $f$ between two F-algebras $A$ (with element $a$ and endomorphism $u$) and $B$ (with element $b$ and endomorphism $v$) is a $f \colon A \to B$ making the following diagram commute.

$$\require{AMScd}\begin{CD}
A+1     @>f+1>>  B+1\\
@VVa+uV        @VVb + vV\\
A    @>f>>  B
\end{CD}$$

And, in fact, we can find a pair of invertible morphisms making them isomorphic.
I will only define the first one, but the second one is analogous and checking that they are inverses should be easy.

$$\require{AMScd}\begin{CD}
\mathsf{Nat0}+1     @>f+1>>  \mathsf{Nat1}+1\\
@VV\mathsf{Zero+Succ0}V        @VV\mathsf{One + Succ1}V\\
\mathsf{Nat0}     @>f>>  \mathsf{Nat1}
\end{CD}$$

The commutativity of the diagram determines that the only possible $f$ must send Zero to One and Succ0 x to Succ1 x. This translates into code as follows.

f :: Nat0 -> Nat1
f Zero = One
f (Succ0 x) = Succ1 x

Precisely because $A$ is initial, this is the only possible $f$ making this diagram commute. We had no choice when defining $f$ (apart from undefined or any other of the constructions that make this kind of categorical reasoning fail in Haskell).

What about the two instances? They define two different functions over each one of the types, but that does not make them non-isomorphic as algebras. As you say, the instances play no role on the definition of the two algebras. The algebra structure concerns only the $1+A \to A$ morphism, not the two additional morphisms $A \times A \to A$ and $A \times A \to \mathsf{Bool}$ that define the instance. Even if we call the two different functions add, the second one is simply a different function. We could rename the second add, and we would see that they are, essentially, two different instances of the same class for (essentially) the same type.

What if we want an "add" (a binary) function to be part of the algebra? Then we would be looking for the initial algebra for the functor $F(X) = 1 + X + X \times X$, and neither Nat0 nor Nat1 (with their respective add functions) are initial algebras for this functor. The initial algebra would be the following one.

data Foo = Zero | Succ Foo | Add Foo Foo

What if we also want an "equality" function to be part of the algebra? There may be a better approach for this, but we can consider algebras on the category whose objects are pairs of types. An algebra is of the form $F(A,B) \to (A,B)$ for some endofunctor $F$, and in this case, we consider algebras of the form $(1 + A + A \times A, A \times A) \to (A,B)$. The natural numbers ($A$) and the booleans ($B$) endowed with zero $1 \to A$, the successor function $A \to A$, addition $A \times A \to A$, and the equality function $A \times A \to B$ would be an algebra of this form, but not the initial algebra. I think the initial algebra in this case could be written in Haskell as follows.

-- Initial algebra (where the object is a pair of types!).
data A = Zero | Succ A | Add A A
data B = Equ A A

-- Given any other algebra.
data C
data D
z :: C
s :: C -> C
a :: C -> C -> C
e :: C -> C -> D

-- There is a unique morphism (two morphisms) from the initial
-- algebra making the relevant diagram commute.
u1 :: A -> C
u1 Zero = z
u1 (Succ x) = s (u1 x)
u1 (Add x y) = a (u1 x) (u1 y)

u2 :: B -> D
u2 (Equ x y) = e (u1 x) (u1 y)

Where the relevant diagram is the following one.

$$\require{AMScd}\begin{CD}
(1+A+A\times A,A \times A)    @>>>  (1+C+C\times C,C \times C)\\
@V(Zero+Succ+Add,Equ)VV        @VV(z+s+a,e)V\\
(A,B)    @>(u1,u2)>>  (C,D)
\end{CD}$$


Finding the Best Fitting Plane Given a Set of 3D Points

This is exactly the problem that PCA (principal component analysis) solves.  So, use PCA -- that provides an algorithmic solution to this problem.  See this explanation over at Statistics.SE for an explanation of why PCA solves this problem.

[Least squares fitting is almost a solution to this problem, except that it doesn't minimize the orthogonal distance -- it minimizes the distance along the $y$ axis, or any single axis you might pick.]

If for some reason you didn't want to use PCA, you could frame this as a mathematical optimization problem (the objective function is the total orthogonal distance) and then use any standard optimization technique -- e.g., gradient descent -- to find an approximate optimum.


Arithmetic code: from interval to code value

You transmit the bit pattern of the left(smaller) end, until you either run out of bits or you find a difference of the left and the right (bigger) number.  The first difference will have a 0 on the left side, and a 1 on the right side.  If this 1 is not the last bit on the right side, you transmit this 1 and you are done, you transmitted the shorted number from within the interval.

a=0011001100
b=0011010010
->001101

If this 1 is the last bit you cannot transmit it directly, because then you would send exactly the right end which is not within the interval.  In this case you have to continue sending bits from the left side, until you hit the next 0.  Here you transmit a 1, and you are done.

a=00110010101
b=00110011000
->0011001011


Support of a codeword in a binary linear code proof

If a codeword of weight 3 existed whose support was a subset of a codeword of weight 4, then you must have a codeword of weight 1 (since the difference of codewords is also a code word).

A codeword of weight 1 has one 1 and the rest zeros. Now, can you show that these don't exist?


time complexity of erasing repeated entries

The basic algorithm is to first put all the members of S into a hash table $\mathcal{S}$.  Then walk down the list T, recording its elements in a hash table $\mathcal{T}$ as you go.  If an element has already been recorded in hash table $\mathcal{T}$ then you delete it from T.  If an element does not appear in hash table $\mathcal{S}$ then you delete it from T.  When you've completed your walk down T, there will be no repeated elements left in it and every remaining element will be a member of S.

Hash table insertions and lookups have amortized O(1) runtime so the whole algorithm scales O(n).


Assembly language is normally untyped, in the sense that there is no type-checking.  Adding type-checking is a non-trivial research challenge (hence the papers you see).  Papers on typed assembly language should explain the motivation.  One application is that they can be used to support proof-carrying code, which can be used to securely execute untrusted code.  Another potential application is to support formal verification.  But I suggest reading some of the key papers to see what they say about the applications and motivation for typed assembly language.

You can find other papers yourself by doing a literature search -- see https://crypto.stackexchange.com/q/8316/351.


Is the halting problem always decidable for non-universal programs?

To answer the first part of your question - Two counter machines are not exactly Turing-complete. That is, there are some functions that cannot be computed with them, for certain counter-values. This is a very slight weakness, so 2CM are actually very close to being Turing complete, but still.

As for your suggested model - could you formalize it in more detail? It's not clear enough as it is.


Has category theory had an impact on computer science?

Categories can be used to model databases, and have been used for data integration. See also this paper. There's a pretty gentle introduction in chapter 3 of Seven Sketches in Compositionality.
Coalgebras are a generalization of automata, and have provided insight into notions of bisimulation. I saw a talk about this, but also found this paper
Closed symmetric monoidal categories have been used to model linear logic, but also to model quantum computation (which is itself related to linear logic). There's a Rosetta Stone paper that discusses this.
CRDTs are a cornerstone of distributed computing, and while I don't understand it myself, it looks like there is some connection to category theory
Guarded recursion and the Topos of Trees generalize step-indexing, which has been used to model higher-order separation logic. This is a tool for verifying programs with heap memory and/or concurrency, and has been applied in Iris.

I think it's also worth mentioning that the Programming Language concepts are not exactly isolated or esoteric. Monads originated in Category theory: my understanding is that Moggi (a category theorist) first applied them, and they were brought into Haskell by Philip Wadler.
But, monadic interfaces are everywhere. Errors in Rust are monadic, as are basically any langage's Option type. Promises in Javascript are monads. Using monads gives a beautiful implementation  of Software Transactional Memory, a lock-free approach to concurrency.
And, of course, category theory is basically at the heart of modern logic research, which underlies most CS theory.


Fitting different rectangles inside a rectangle

As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions.

A lot approaches ignore rotation, but can be expanded fairly easily to support it. As you seem to be aware of approaches without rotation, I'll focus on the rotating part.

A good resource is 'One thousand ways to pack the bin', by Jukka Jylänki. It covers many heuristic algorithms, and considers rotation part of the problem. Most of the rest of this post summarizes this paper.

While rotation makes the problem a lot harder to solve exactly, it doesn't make most heuristic methods much more complicated, as they cannot afford to make complicated choices and so choose heuristically how to rotate.

Shelf heuristic

For the shelf algorithms, rotation is quite simple:

If the current rectangle starts a new shelf, we rotate such that the shelf height is minimal.
Otherwise, rotate such that the width is minimal while still fitting the shelf (if it fits at all)

Point 2 is actually the best way to rotate given that the rectangle will be packed in the current shelf while for point 1 one could argue to do the opposite and this could indeed be better in some cases. (such as the case that all remaining rectangles are squares with length equal to the long side of the first rectangle of the shelf)

Guillotine heuristic

For the guillotine algorithm, the choice for rotation isn't so clear (perhaps a reason why Jylänki leaves this open), but one reasonable method is to try both orientations to decide whether a rectangle 'fits'. If both fit, one could try to pick the one that matches the split rule (for example, choose the rotation that minimizes the area of the chosen free rectangle when using the Best Area Fit variant)

Other heuristics

For the Maximal rectangle algorithm and the Skyline heuristic, supporting rotation here is similar to the Guillotine case, there aren't really any particular choices other than trying to fit with both orientations and pick the one which makes more 'sense' with respect to the rest of the specific heuristic.

There are more algorithms, but I think this gives a good overview of the ideas of how to support rotation. As you might have noticed, these methods aren't too fancy, that is sometimes the best you're going to get.


Algorithm to compute $n^{\log k}$ in $O(\log\log k)$

The idea is to use repeated squaring. Compute $n,n^2,n^4,\ldots n^{\log k}$. To compute $n^{2^i}$ use the fact that $n^{2^i} = n^{2^{i-1}} n^{2^{i-1}}$. Note that the answer of $n^{2^{i-1}}$ will be known in the $i$th iteration.


Distribution of the number of bits changed during generation of all binary tuples

It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely $2^n-1$. We can then rephrase your question as follows. Let $\pi$ be a random permutation of $\{0,1\}^n$. You are interested in the distribution of
$$
X = \frac{1}{2^n-1} \sum_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)),
$$
where $d$ is Hamming distance. We can compute the moments of $X$ using linearity of expectation. The expected value of $X$ is
$$
\mathbb{E}[X] = \mathbb{E} d(\pi(0),\pi(1)) = \mathbb{E}_{x \neq 0} d(0^n,x) = \frac{\frac{n}{2} 2^n}{2^n-1} \approx \frac{n}{2}.
$$
The second moment of $X$ is
$$
\mathbb{E}[X^2] = \frac{1}{2^n-1} \mathbb{E} d(\pi(0),\pi(1))^2 + \frac{2(2^n-2)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(1),\pi(2)) + \frac{(2^n-2)(2^n-3)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx
\mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \left(\frac{n}{2}\right)^2.
$$
More generally, for every fixed $t$ we have
$$
\mathbb{E}[X^t] \approx \left(\frac{n}{2}\right)^t.
$$
This suggests that $X$ is tightly concentrated around $n/2$.

Going further, one is tempted to conjecture that the distribution is roughly normal, since the dependence between non-adjacent summands is very slight. This can be verified or refuted by repeating the calculation above with $d(\pi(i),\pi(i+1))$ replaced by $d'(\pi(i),\pi(i+1)) = d(\pi(i),\pi(i+1)) - n/2$. Since $d(\pi(i),\pi(i+1))$ is distributed almost like $\mathrm{Bin}(n,1/2)$, this suggests that $X$ is distributed almost like $N(n/2,n/4)$, a normal random variable with mean $n/2$ and variance $n/4$.


Find a straight line to divide two convex polygons by equal area

This is known as the Ham-Sandwich theorem:

  Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line.

Note: Convexity is not needed. And $\mathbb{R}^2$ can be replaced by $\mathbb{R}^d$ with "line" replaced by a $(d{-}1)$-dimensional hyperplane.

(Image from curiosity.com.)

See the Wikipedia link
for computational versions.

Added in response to @WillardZhan's request:

  Ivan Stojmenovíc. Bisections and ham-sandwich cuts
  of convex polygons and polyhedra. Inf. Process. Lett.
  38(1): 15-21. 1991.
  (CiteSeer PDF download.)

  Abstract. We present a linear time sequential algorithm for finding a straight line that bisects two given disjoint convex polygons (i.e. cuts both of them into parts of equal area).

  Abbott, Timothy G., Erik D. Demaine, Martin L. Demaine, Daniel M. Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung. "Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane." In CCCG, pp. 61-64. 2005.
  (PDF download.)


Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

For $p>0$, you can always split $0^{3p}$ into $uvxyz$ such that $u=x=\varepsilon$, $v=0$, $y=0^2$, and $z=0^{3p-3}$. Such a split clearly satisfies $|vxy|\leq p$, $|vy|\geq1$. Finally, for all $n\geq0$, $uv^nxy^nz=0^{3(p-1+n)}$, which is in $L$, since $0^{3m}\in L$ for all $m$.

Since you want to show, that for an arbitrary split satisfying the length conditions, there is some $n$ for which $uv^nxy^nz\notin L$, the choice of $0^{3p}$ is unfortunate.


How to minimize this DFA with already merged states?

After inputs $\epsilon$, $a$, $ab$, $abc$, $abca$ we must be in five different states because appending $b$ to one of these leads to an accept only for $abca$, appending nothing to any of the others leads to an accept only for $abc$, appending $c$ leads to an accept only for $ab$, appending $bc$ to any of the remaining only for $a$.

A bit more formally, given a string $\alpha$, we note in a 4-tuple whether $\alpha$, $\alpha b$, $\alpha c$, $\alpha bc$ are accepted. For $\alpha = \epsilon, a,ab,abc,abca$, these 4-tuples are $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(1,0,0,0)$, $(1,0,0,1)$, hence all distintc. This is only possible if these $\alpha$ correspond to differnt states.


Descriptive complexity: 3-colorability example

The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.


Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?

I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.
Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic idea, it suffices to consider the simplest possible model, in which there is only one head, and at each step, it has to move (either one step to the left, or one step to the right). We simulate $M$ for $|w|$ steps. Either it has moved to the left (in which case we know the answer), or otherwise, it has gone past the input.
In the latter case, suppose that the Turing machine is at some state $q$ after $|w|$ steps. Let's say that a state is bad if when $M$ reaches it, if the input under the head is blank, then it moves left. Construct a directed graph in which there is an arrow from $q$ to $p$ if $M$ transitions from $q$ to $p$ when the input under the head is blank. There are three cases:

The path starting at $q$ reaches a bad state. In this case the head of $M$ will eventually move left.
The path starting at $q$ reaches a halting state or closes a cycle, in both cases not going through a bad state. In this case the head of $M$ will never move left.

This shows how to decide whether $M$ every moves left upon reading $w$.

This might seem to contradict Rice's theorem, but it doesn't. The reason is not what you state — the problem is not trivial: there are pairs $(M,w)$ for which $M$ does move left when running on $w$, and there are other pairs when this doesn't happen. Rather, the property of never moving left is a syntactic property rather than a semantic property: it depends on the Turing machine $M$ instead of on its language $L(M)$.


How many bits needed to describe completely random function?

The word random is misplaced here, the question is how many bits are required to describe a function from $U$ to $\{1,...,n\}$. The connection to randomness here is simply the fact that you need to deal with an arbitrary function (since you pick one uniformly at random). Thus, you cannot rely on any structure of the function, which could allow a more compact description (e.g. a constant function would require only $\log n$ bits to describe).

One way to look at it, is saying that you need to specify the output for every possible input. Since there are $|U|$ possible inputs, and specifying an element in the range requires $\log n$ bits, this results in a $|U|\log n$ length description. You can also use the fact that there are $n^{|U|}$ different functions from $U$ to $[n]$, so you need $\log n^{|U|}=|U|\log n$ bits to index an element in this set.


what's analogy learning algorithm ? differences from induction learning algorithm?

In a nutshell, (statistical) machine learning is a certain approach to artificial intelligence. Traditional artificial intelligence incorporates hard-coded rules which are written by humans. Statistical machine learning, in contrast, has the computer learning the rules by itself using statistical means.

There are several paradigms used for statistical machine learning, such as support vector machines, artificial neural networks, and genetic algorithms. Recently a certain type of artificial neural networks, deep neural networks, has come to the fore due to unprecedented performance. Machine learning using deep neural networks is known as deep learning.


How exactly does a CPU do process scheduling?

The operating system arranges for periodic timer interrupts, which only it can handle, so it periodically regains control of the CPU without requiring the co-operating of any other process. Also, when a process tries to access the hardware, that is mediated by the operating system, which gives it another opportunity to decide which process to run next.


Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$

The two notions of distance are not equivalent. That is, you can find a pair of points $p,q$ such that $p$ is closer to the origin with respect to the distance $\sqrt{x^2+y^2}$ (known as $L_2$), and $q$ with respect to the distance $|x|+|y|$ (known as $L_1$). An example is $p=(2,2)$ and $q=(3,0)$. However, you can simplify your task by considering $x^2+y^2$ instead of $\sqrt{x^2+y^2}$.

There is no need to sort the distances. Instead, you can use a comparison-based linear time selection algorithm.


Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?

You're basically there. If the machine uses at most $s(n)$ tape cells for inputs of length $n$, then it can't visit more than $C(n)=|Q||\Sigma|^{s(n)}s(n)$ different configurations (possible states times possible tape contents times possible head positions).  Since the machine decides a language, it must halt for all inputs, which means that it can't repeat a configuration, since a deterministic machine that repeats a configuration must loop forever. Therefore, by the pigeonhole principle, it can't run for more than $C(n)$ steps on any input of length $n$.

If $s\in o(\log\log n)$ then $C(n) = o(n)$ so the machine terminates after fewer than $n$ steps for all sufficiently large $n$. Intuitively, the machine can't stop in, say, $\sqrt{n}$ steps because, in that many steps, it hasn't seen the whole input, so it doesn't even know what $n$ is.

More formally, let $t(n)$ be the greatest number of steps taken by the machine on inputs of length $n$. Let $w$ be an input long enough that $t(n)<n$ for all $n\geq |w|$, and choose $w$ so that the machine runs for $t(|w|)$ steps on this input.  We know that $t(|w|)\leq C(|w|)<|w|$, so the machine must terminate before it has time to read the whole input. Because it doesn't read the whole input, its execution on input $wz$ must be the same as its execution on $w$, for any string $z$. Therefore $t(|wz|)=t(|w|)$ for all strings $z$, so the function $t$ is constant for all inputs greater than length $|w|$.

Because it halts in a constant number of steps, it only uses a constant number of tape cells, so the language it decides is in $\mathrm{SPACE}(O(1))$.


Easy-to-describe example of uncomputable function

A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.


The obvious approach for typical path finding problems such as this one is that you store the state of the problem in a data structure, usually a lookup array.

In this case, you will have 2 variables, one for your position and one for the bear's position. Since the bear's movement is dependent on other factor, you can do a top down search approach and recursively check your options.

The running time will be polynomial to the size of the grid which will be $O((wh)^2)$.
There might be other optimizations, but this will be the general direction.


Regular Expression to Context-Free Grammar

I assume you want to get a grammar that generates the same language as the given regular expression.

You can achieve that by the following steps:

Translate the regular expression into an NFA.
Translate the NFA into a (right-)regular grammar.

Both translations are standard and covered in basic textbooks on formal languages and automata. Note that any regular grammar is also context-free.


Neural network for PDE: Should we train the PDE using more initial and boundary data at the beginning?

There is sadly very little theory that is useful for predicting the behavior of neural networks.  Also, their effectiveness tends to be dependent on the particular workload/task you are trying to solve it.  While I know it's not what you were hoping to hear, I suggest that you try it in empirical experiments.


Blockchain uses a cryptographic hash function that is designed to have collision resistance.  Thus, while it's possible you might run into a pair of inputs that produce the same output... it's very very unlikely to happen by chance; and it is believed to be very difficult to intentionally find such a pair of inputs.

Disk space has nothing to do with collisions in the hash function.


I don't know the language in detail, but my guess is: no, stack cleanliness is not computable.

For every natural $n$, consider a Brain-Flak program $P_n$ which does the following:

take a natural $k$ as input;
without modifying the stack below, simulate Turing Machine number $n$ on empty input, for at most $k$ steps;
if the machine does not halt within $k$ steps, revert the stack to the original state, and return $0$;
otherwise, if it does halt, modify the stack below and return $0$.

$P_n(k)$ is guaranteed to halt for any inputs $n,k$.

$P_n$ will be stack-clean (on all inputs $k$, by definition) if and only if the TM number $n$ never terminates on empty input.

The latter is known to be undecidable (it's not even semi-decidable).

Hence stack cleanliness over input arity 1, output arity 1, and constant zero function is already undecidable.


The game is actually an instance of two-persons Pebble game, as @HendrikJan pointed out, and as such is proven to be $EXPTIME-complete$. The following is a summary based on a proof by Kasai, Adachi and Iwata in SICOMP 8 (4).

For starters, it's pretty obvious that the game is in $EXPTIME$ - we can simply check all the possible games and see if there is winning strategy. To proove it's $EXPTIME-hard$ is a little bit more challenging.

First we need to know the notion of Alternating Turing machines (or ATMs for short). We will further tighten the definition to get so-called standard ATM:

We say an ATM $M$ is standard if

$M$ has only one work tape with the head initialized to the first cell of the tape,
if a configuration $C$ of $M$ is existential (universal), then every configuration $C’ \in Next_M(C)$ is universal (existential),
the initial state is existential and the accepting state is universal, and
$Next_M(C) = \emptyset$ if and only if $C$ is an accepting configuration.

Where $Next_M(C)$ deontes set of possible configurations after one move starting from configuration $C$

Now there come two important lemmas proven by Chandra, Kozen and Stockmayer in Journal of the ACM 28(1):

Lemma 1

For every $S(n) \geq log (n)$, if $L \in ASPACE(S(n))$, then $L$ is accepted by a standard ATM within space $S(n)$.

Lemma 2

$EXPTIME = APSPACE$

Having those two in mind, we now see that, given a standard ATM $M = (Q, \Sigma, \Gamma, \delta, b, q_1, q_a, U)$ such that only $p(n)$ cells are
available on the work tape for some polynomial $p$ in $n$, and a word $w = w_1 w_2 ... w_n$, we need to construct, in logarythmic space, an instance of pebbles game $G$ such, that $w$ is accepted by $M$ iff. first player has winning strategy in $G$.

In order to do that we will need

set of fields $X$ consisting of

fields representing the state of working tape ($\{1..p(n)\} \times \Gamma$)
fields representing current state of machine and it's heads ($Q \times \{1..n\}  \times \{1..p(n)\}$)
fields representing work tape transitions ($Q \times \{1..n\}  \times \{1..p(n)\} \times \Gamma^2)$
three additional fields $s_1, s_2, t$ to ensure that correct player wins the game

Set $R$ of rules that translates $\delta$ into our game:

For each element of $Q \times \{1..n\}  \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a', (d', d'')), a \neq a'$ then this transition can be encoded with the following rules:

$([q, i, l], [l, a], [q, i, l, a, a'])$
$([l, a], [q, i, l, a, a'], [l, a'])$
$([q, i, l, a, a'], [l, a'], [q, i+d', l+d''])$

For each element of $Q \times \{1..n\}  \times \{1..p(n)\}$ if $\delta (q, w_i, a)$ contains $(q', a, (d', d''))$ we need just one rule:

$([q, i, l], [l, a], [q, i+d', l+d''])$

Finally we need to have "game finishers" rules:

for each $i$ and $l$ there should be rule $([q_a, i, l], s_1, s_2)$
we also add rule $(s_2, s_1, t)$

And to start the game properly we need the set $S = \{[q_1,1,1],s_1\} \cup \{[l,b] | 1 \leq l \leq p(n)\}$, which denotes that we're in initiall state, both heads are at the beggining of the tapes, and the working tape is empty.

From this, the proof of the fact that $w$ is accepted by $M$ iff. first player has a winning strategy in $G$ should be pretty straightforward.


How to turing reduce equivalent languages $Q$ to infinite language $I$

Given $M_1$ and $M_2$ you construct a machine $M$ that on input $w$ does the following:

it runs $M_1$ on the first $w$ inputs ($\epsilon$,0,1,00,01,..) for $w$ steps each.

if  $M_1$ accepts some input, you run $M_2$ on the same input and check it accepts too. (note, $M_2$ may not halt!)
If $M_1$ rejects some input, you run $M_2$ for $w$ steps and verify it doesn't accept during that time.

you do the same with $M_2$: run $w$ steps on each of the first $w$ inputs, and verify everything works, or reject otherwise
if all checks pass - accept. Otherwise reject.

The idea is the following: as long as $M_1$ and $M_2$ behave the same, you will keep accepting all $w$'s. but as long as you find a difference, then you will reject that $w$ and all inputs $w'>w$, thus the accepted language becomes finite. You should be careful because machines may not halt. For instance, $M_1$ may reject some input, but $M_2$ won't halt on it -- still, they both "reject" it, and this case should be carefully analyzed.


what does this phrase mean: "train a policy network"

A policy is just a response or action given a state (situation).  Training a neural network with samples from an expert is just searching for a function F that efficiently maps states to actions.

For example for chess, a neural network can be trained with the action to be taken in a given state of the board.  This can be trained using a database of existing (human) expert games.
The resulting network is a policy network that maps a given board setup (state) to the chess move to be executed in that state that more likely leads to a win (action).


Check whether set of strings is prefix-free via lexicographic sort?

Yes. The common prefix is maximal with the closest predecessor (if you're treating the empty string as less than any other, which you are).  Edit:  in general if a prefix key exists it will be the immediate predecessor or there will be another key in between which shares the same prefix, and your test will fail on that.  eg ABC, ABCD, ABCE will fail on the first pair even though the last key also contains ABC and is non-consecutive.  The LCP is indeed maximal with the closest predecessor neighbor, but that predecessor neighbor may not be a prefix; I just wanted to clarify that.
There are situations where the longest common prefix is useful; in particular to augment a suffix array, which is a sorted list of suffixes.  Look up LCP Array. The LCP+1 (roughly) is called the distinguishing prefix; string sorting algos express their complexity in terms of O(n log n + D), where D is the sum of all the distinguishing prefixes of all the keys.  So it's a familiar idea.
"Prefix free" is the term that I remember.
You can put them in a trie and look for strings that end on an intermediate node.  It's a variant of sorting.


What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons.

The key to the problem is not to use a function that computes the Levenshtein distance but to use one that computes the Levenshtein distance if the distance is less than a certain threshold, and fails (or, rather, returns +∞) if the distance is greater than the threshold.

This is because you are only interested in closely similar paragraphs. You have no interest at all in the precise distance between paragraphs that are different enough to be unrelated. So as soon as a distance has got high enough to be uninteresting, the function can exit at once; and this will mostly happen very early on indeed during the execution of the function.

The higher the threshold, the longer the running time but the smaller the proportion of false negatives.

If you know something more about the documents (such as that each paragraph matches at most one paragraph in the other document) then you could make one pass with a low threshold, exclude the matched paragraphs from further consideration, make one pass over your now reduced corpus with a higher threshold, exclude those reduced paragraphs, and so on.

Implementation detail: Presumably you would be calculating a Levenshtein distance on words rather than on characters. If that is the case, you should first assign a number to each word - for example, by sorting the entire corpus, calling the first word '1', the second word '2', and so on. That way your paragraph comparisons would be done by comparing numbers rather than words, which is faster.


Is the universe problem for one-counter automata with restricted alphabet size undecidable?

It must be undecidable for an alphabet with two symbols. It is possible to code any alphabet into two letters, e.g., map 16 symbols to the length 4 binary strings $aaaa, aaab, \dots, bbbb$. Then equality to $\Sigma^*$ is equivalent to equality to all possible codes for strings. In the 16 letter example this means equality to all strings of a multiple of four letters. Clearly that is not universality. That is obtained by adding those binary strings that are not coding. That is a regular set and can be generated by a one counter automaton.

The same explanation, with $\LaTeX$ for those who appreciate it.
Assume universality is undecidable for $\Sigma$. Let $h: \Sigma^* \to \{0,1\}^*$ be an injective morphism. Now $L = \Sigma^*$ iff $h(L) = h(\Sigma^*)$. This in turn is equivalent to $h(L) \cup R = \{0,1\}^*$ where $R$ is the (fixed) regular language $\{0,1\}^* - h(\Sigma^*)$. Hence we cannot decide whether the binary one counter language  $h(L) \cup R$ is universal. Note that language is one counter as the family is closed under morphisms and union (with regular languages).

As you state "I think that" I can also confirm the question is decidable for a one letter alphabet. It is decidable for push-down automata (hence context-free languages) as one letter CFL are (effectively) equivalent to regular languages.


The winding number $w$ of a polygon has to be calculated around a certain point $P$. Since your question is ambiguous, I'll suppose you've already determined $P$.

Given a list of n vertices $v_0, v_1, ... v_{n-1},v_0$ (notice $v_n = v_0$) given in counter-clockwise order, a simple linear way to calculate the winding number is
$$
w = \frac {1}{2\pi}\sum_{i=0}^{n-1} \theta_{v_i,v_{i+1}}$$ where $\theta_{v_i,v_{i+1}}$ is the angle between $\vec{v_iP}$ and $\vec{v_{i+1}P}$, which you can obtain using dot product and arcosines.

Your second solution consists of casting a ray $R$ from $P$. The winding number of your polygon can then be calculated as the number of edges $E_+$ that cross $R$ going counter clockwise, minus the number of edges $E_-$ that cross $R$ going clockwise.

I.e.: $w = E_+ - E_-$

If you want further insight (and proof) on how to determine $E_+$ and $E_-$, I highly suggest you research the "point in polygon" problem and the "crossing number" often associated with that problem.


How is expected value in entropy derived?

Here is the definition of the expectation of a discrete random variable $Y$:
$$
\mathbb{E}[Y] = -\sum_y \Pr[Y = y] \cdot y.
$$
In your case, $Y = \log P(X)$, where $X \sim P$. Therefore
$$
\mathbb{E}[X] = \sum_y \Pr[\log P(X) = y] \cdot y.
$$
Notice that
$$
\Pr[-\log P(X) = y] = \sum_{x\colon \log P(x)=y} \Pr[X = x] \cdot y = \sum_{x\colon \log P(x)=y} \Pr[X = x] \cdot \log P(x).
$$
Therefore
$$
\mathbb{E}[X] = \sum_y \sum_{x\colon \log P(x) = y} \Pr[X = x] \cdot \log P(x) = \sum_x \Pr[X = x] \log P(x) = \sum_x P(x) \log P(x).
$$


Datastructure for managing (abstract) sets

One simple approach:
For each abstract set $A$ create a node. Let each node maintain a list of
1) complementary sets
2) disjoint sets
3) overlapping, i.e. they are not equivalent but have a non-empty intersection
4) proper subsets

For example, consider the following node

NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

Assume that you have created a set $A$. Allocate a new node for this set and let $A$ point to this node.

 HASH TABLE
 ______________
 |A| |-> 123F65
 ______________

Then assume you add a new set $B$ with a property $A=B$. You don't create a new node, just make $B$ point to the same location $A$ points to, 123F65.

 HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 ______________

Then assume you add a new set $C$ which is a proper subset of $B$. Create a new node for $C$ and make $C$ point to that node. Additionally add $C$ to to the list of proper subsets of $B$ in 123F65.

NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> [ C ]
----

NODE: 153F60
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 |C| |-> 153F60
 ______________

So for example, if I want to find out if $A$ and $B$ is disjoint, I would check if $A$ is a subset of any $B$'s complementary or if $B$ is a subset of any $A$'s complementary. If yes then the answer is "disjoint", otherwise they are not disjoint or insufficient information.

Note that this data structure is just a kick-off. You may have to change it as you will ask different questions or you want to speed up queries.


Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?

Let $V_P(n)$ represent the value of the optimal solution to a problem $P$ with size $n$. According to Bellman equations, this value is computed from the value of the optimal solutions of its subproblems $P'$: $V_P(n) = \oplus \{v_{P'} + V_{P'}(n')\}$ where $\oplus$ is an  operator such as $\max$, $\min$, +, ... $v_{P'}$ is an operator which steps from $P$ to $P'$, and $P'$ are the subproblems of $P$ with size $n'$ which is always strictly less than $n$, the size of the original problem.

From here, it seems affordable to create a graph $G(V,E)$ where $V$ are the values of the optimal solutions of different problems, and there is an edge between two vertices $u$ and $v$ if and only if $v$ represents a problem $P'$ which is acknowledged as a subproblem of task $P$ represented by vertex $u$. For example, when using Dynamic Programming for computing the Fibonacci numbers, if $u$ represents $Fib(n)$, then there are two edges from it to other vertices representing $Fib(n-1)$ and $Fib(n-2)$.

If this is the graph you meant in your question then, clearly, the resulting graph is a Directed Acyclic Graph because:

Each vertex is directed in only one direction: from $u$ to $v$ as only one problem ($P'$) can be a subproblem of another, $P$.
It is impossible to form a loop as $n'<n$.

All this said, however, I do not think that this characterization is too useful as it also applies to other techniques such as Divide and Conquer and plain recursion. As you are asking whethere there is more about it or not, let me highlight that an important issue to consider when deciding whether to use Dynamic Programming or not, is if the problem $P$ shows suboptimal structure, see this definition in the second paragraph.

Hope this helps,


Turing Machine with additional finite memory of size $n$

I don't think that you can "embed" the extra memory into the alphabet and "carry" it with the head moving around without a $|Q|$ blow-up (blow-up comparable to the one of approach 1).

So a (weird!) approach to keep the size of $|Q|$ low, that can work is the following:

embed both the extra memory and $Q$ into the alphabet $\Gamma_M = \{H,h\} \times Q \times \Gamma \times  \Gamma^n$
use only ONE cell (marked with embedded symbol $H$) to represent the current state of $M_{mem}$ + symbol under its head + the content of the extra-memory
use some additional states to SHIFT the tape around the cell $H$

Very informally you have:

                  q1
                  S
....0 1  1 1 0 0 [0] 1 1 0 0 0 ...
    h h  h h h h  H  h h h h h
                  ^
                  q_sim

In this condition, the (standard) Turing machine $M$ is on state $q_{sim}$ and is on symbol $\langle H,q_1,0,S \rangle$ that represents: head of $M_{mem}$ is on state $q1$, reading a $0$ and the content of the extra memory is $S$

Now if $M_{mem}$ writes a 1, writes $S'$ on the extra memory, moves $L$eft and enters $q_2$; the standard $M$ on state $q_{sim}$ writes $\langle H,q_2,1,S' \rangle$ and enters a sequence of states $q_{r_1},...,q_{r_k}$ that shift the whole tape one cell to the right and returns back on the cell marked with $H$ and state $q_{sim}$; simulating in this way the movement of the $M_{mem}$'s head:

                  q2
                  S'
....  0 1  1 1 0 [0] 1 1 1 0 0 0 ... << tape shifted right
      h h  h h h  H  h h h h h h
                  ^
                  q_sim

Note that the standard $M$ simulates $M_{mem}$ transitions using only a single state $q_{sim}$ (plus two extra-states for accept/reject).

Also note that the symbol corresponding to the extra memory $S'$ is NOT MOVED, so the total number of states of $Q_M$ required to shift the "underlying" tape (simulating the move of the head of $M_{mem}$) depends only on $\Gamma$, not on $n$:

$\Gamma_M = \{H, h\} \times Q \times \Gamma \times \Gamma^n $

$\delta_M = Q_M \times \Gamma_M \to Q_M \times \Gamma_M \times \{L,R\}$

and $|Q_M| = k |\Gamma|+c$

You can also choose to embed the states of $M_{mem}$ into $Q_M$: in this case the alphabet is: $\Gamma_M = \{H, h\} \times \Gamma \times \Gamma^n $, but you must use more states: $|Q_M| = k |Q| |\Gamma|+c$

The above construction can also be generalized to standard Turing machines and (very informally) it roughly represents a switch from:

$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L,R\}$ to

$\delta : \Gamma \times Q \to \Gamma \times Q \times \{L,R\}$


Longest AP that can be formed (with difference 1) in an unsorted array of integers

If you're allowed to use hash tables, you can get a linear time algorithm.

Go over all nodes, putting the unique nodes in a hashtable, and constructing a new array only with the unique values. Now go over the new array and upgrade it to a graph $G = (V,E)$ in which $V$ are the unique values and the edges connect $i$ to $i+1$. Go over the graph, and whenever you see a vertex with no incoming edge, follow the unique path emanating from it and count its length. The answer is the maximal length of such a path.

This solution uses a hashtable to efficiently construct the graph. This suggests that you might not be able to do better than $n\log n$ if you are only allowed to use comparisons. One way to prove it would be by reduction from element uniqueness, which is known to require $n\log n$ comparisons.


Can a program exist that halts only if it can prove that it doesn't halt?

We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true statement. We think of $\pi$ as a proof of $p$. (If $\pi$ is not a valid proof, then $\Pi$ outputs some fixed true statement.) We consider sound proof systems which are rich enough to prove statements about the halting of Turing machines.
Let $Q(q)$ be the program that enumerates over all strings, and halts if it ever finds a string $\pi$ such that $\Pi(\pi) = p$, where $p$ is an encoding of "The Turing machine encoded by $q$ never halts when run on $q$". Let $[Q]$ be an encoding of $Q$. If we run $Q$ on $[Q]$, then $Q$ halts iff there is a $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$.
(Using the recursion theorem, we can transform $Q$ to a Turing machine $P$ which runs $Q$ on $[P]$, which is the setup in the original post.)
If there is a $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$, then $Q$ doesn't halt when running on $[Q]$. We conclude that there cannot be any $\Pi$-proof that $Q$ doesn't halt when running on $[Q]$, because if such a $\Pi$-proof existed, then $Q$ would halt when running on $[Q]$. Therefore $Q$ doesn't halt when running on $[Q]$. However, there is no $\Pi$-proof of this fact.
This is an example of incompleteness. The proof system $\Pi$ is unable to formalize the argument above. One reason is that $\Pi$ cannot even prove its own consistency (i.e., that it does not prove a contradiction, as per Gödel's second incompleteness theorem), not to say soundness (which $\Pi$ may not even be able to express).


Higher Residuocity Problem w.r.t. a composite Modulus

Testing whether $q$ is a quadratic residue modulo $n$ is hard when $N$ is composite: it is as hard as factoring $N$, which is believed to be hard when $N$ is large.

The same is true for your problem.

If the factorization of $n$ is known and $k=2$, you can test whether $q$ is a quadratic residue; find all square roots, call it $y$, such that $y^2 \equiv q \pmod n$, then for each such square root $y$, test whether $y + c^2 \bmod n$ is a quadratic residue and find a square root of it, i.e., an $x$ such that $x^2 = y + c^2 \pmod n$, and then you will have a solution to your original problem.  This will be efficient if there aren't too many square roots, i.e., if $N$ doesn't have too many different prime factors.

Alternatively, assuming $n$ is squarefree and has known factorization $n=p_1 \cdots p_m$ and assuming $k$ is not too large, you can factor the polynomial $(x^2-c^2)^k-q$ over $\mathbb{Z}/p_i\mathbb{Z}$ (separately for each prime factor $p_i$ of $n$), then if this polynomial has a root modulo every $p_i$, combine solutions via the Chinese remainder theorem.


Randomized vs deterministic approach for multiset equality

To understand the complexity of the randomized algorithm, you must delve into the implementation details.

Suppose $S_1,S_2$ consist of $m$ elements, each bounded by $n$ in absolute value, i.e. the input size is $O(m\log n)$. Let $P_S=\prod\limits_{w\in s}\left(x-w\right)$ be the polynomial corresponding to the set $S$. $P_{s_1},P_{S_2}$ are degree $m$ polynomials. Thus, in order to succeed with constant probability in testing whether $q(x)=P_{S_1}(x)-P_{S_2}(x)$ is the zero polynomial, you need to evaluate it at numbers in the range $[0,cm]$, for some constant $c$.

Suppose you choose $y$ uniformly at random from this range, then in order to avoid blowup in the intermediate values while computing $q(y)$, you need to compute the values modulo some $k$ (the standard trick in PIT).

Note that the blowup here is not exponential, unlike in PIT where the polynomials are given as algebraic circuits, so you can in fact directly compute $q(y)$. However, this will lead to handling $\Omega(m)$ bit numbers, which will result in quadratic running time, so you can still compute $q(y) \bmod k$ for a random $k$ chosen appropriately to save some time.

If $k$ is chosen at random from some range $[1,R]$, then a "good" event is that $k$ does not divide $q(y)$, in that case $q(y)\neq 0$ iff $q(y) \bmod k \neq 0$. To lower bound this probability, note that $k$ is prime with probability $\approx \frac{1}{\log R}$ (here you need some finite version of the prime number theorem), and that $q(y)\le (cm+n)^m$, hence it has at most $m \log (cm+n)$ different prime factors.

$
\begin{align*}
&
\Pr\limits\left[\text{$k$ is prime $\land$ $k$ is not a product of $q(y)$}\right]=
\Pr\left[\text{$k$ is prime}\right]\cdot\\
&
\Pr\limits\big[\text{$k$ is a product of $q(y)$} \big| \text{$k$ is prime}\big]\approx \frac{1}{\log R}\left(1-\frac{\log (cm+n)^m}{R/\log R}\right)
\end{align*}
$

Choosing $R=(m+n)^2$ suffices to make the above probability high enough, and yields constant success probability after $\approx\log R$ evaluations. Each evaluation requires $O(m)$ additions/multiplications of numbers with $\log R$ bits, thus the overall running time is $O(m\log ^2 R\log\log R)$, which is worse than sorting. Perhaps sharper bounds on the success probability will allow you to get rid of one of the logarithmic factors, but taking numeric operations into account will eventually show that you cant beat naive sorting. However, the randomized approach is not without merits, as it allows you to determine multiset equality between two parties with logarithmic communication (you only need to send $y,k$ and the evaluations of $P_{S_1},P_{S_2}$ on $y$ modulo $k$).


What fraction of all combinations is guaranteed to be deadlock free?

Let's assume for simplicity that A and B take 5 seconds to request for the next resource and B starts requesting for resources 1 second after A's request.

If A requests for 1 first and B requests for either 2/3 first, it will create a deadlock. This happens because when A requests for either 2/3 it will be blocked and B will be blocked when it requests for 1. So both processes will block each other and in turn will be blocked by each other.
If A and B both request for 1, then A wins out and B will be blocked. So there will be no deadlock.

So the entire problems rests on B's choices. Therefore $\frac{1}{3}$rd of the cases will be deadlock free.


How can I identify that a restricted variant of Boolean SAT remains hard or not?

Your problem cannot be solved in polynomial time, for a boring reason: the size of the output might be exponential in the time of the input.  Therefore, there is no hope for a polynomial-time algorithm.

For instance, consider the boolean function $f:\{0,1\}^n \to \{0,1\}$ that outputs $1$ if its input vector has at least $n/2$ ones (i.e., its Hamming weight is at least $n/2$), and $0$ otherwise.  This function can be represented by a polynomial-size monotone formula.  However, there are exponentially many minimal $x$ such that $f(x)=1$.  In particular, each $x$ of Hamming weight $n/2$ is such a minimal input, and there are ${n \choose n/2}  \approx 2^n/\sqrt{n}$ such inputs.

So, there's no hope.

As Andrej Bauer points out, a related problem (testing whether there exists an input of Hamming weight at most $k$ that causes the boolean function to output $1$) is also NP-complete; see Prove NP-completeness of deciding satisfiability of monotone boolean formula.


Finding the largest 3-clique-free induced subgraph

Both definitions leave your problem NP-hard, and have been answered on cstheory.

Interpretation 1, where you require the largest triangle free sub-graph, is NP-Hard and has been answered here.
Intepretation 2, where you need a partition such that both the induced sub-graphs are triangle free, has been answered here.

Note that the answers I linked to are for general $H$-freeness and are a class of $NP$-Hard problems.


Does the normal form theorem imply that every partially computabe function is primitive recursive?

No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate.

What does seem to follow from this is that every computable function is $\mu$-recursive as primitive recursion is a subset of $\mu$-recursion. In fact I happen to know this to be true because $\mu$-recursion is turing complete.

You can check out primitive recursion and $\mu$-recursion on Wikipedia.

I also found a wikipedia page with some related matters. In particular they give another form of the Normal Form Theorem that seems slightly stronger; see here.


Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$

Obviously not. You must inspect all the points and, on a classical, deterministic computer, you can't possibly look at $n$ points in only $O(\log n)$ time.

Note that this answer applies equally to the original question (is it possible in $\log n$ time?) and the revised one (is it possible in $|Q|+\log n$ time?). The answer could well be $Q=\emptyset$, but you can't figure that out in time $o(n)$.


Reconstruction of drawing sequence from video

You should have a look at background segmentation algorithms. The hand is moving over the rather static drawing. One very simple approach would be to store the last N images and compute the variance of the color for each pixel. The pixels with a low variance will be your painting (and the canvas you draw an) so a subsequent thresholding should seperate the drawing from the canvas.


Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs.

It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of Karp's 21 hard problems. On the other hand, finding whether a graph is acyclic can be done with any graph traversal method in polynomial (actually linear) time. Hence, $\operatorname{P}^{\text{Acyclic}} = \operatorname P$. Hence, if you solved the task you are given in polynomial time you would have proven $\operatorname{P} = \operatorname{NP}$.


Given a list of points on a sphere find the place for another point such that most space is covered?

The general problem is called Circle packing, which gets easier with equiradius circles, to get hexagonal grid and put circles on hexagon vertices and one in the center. This works on Euclidian space, so the hexagon coordinates should be converted by some kind of mapping, for example Vincenty formulae.

This method will give really neglible overlapping, but to be exact further corrections might be needed (like error calculation at intersection points to shift the centers). For small radius (like 50m) error will be very small (using the mapping to sphere). Performing grow on already available circles will give the problem of initial rotation to fit more space, so with many initial circles not fitting the grid only general method (iterative one) will give the optimum.

The deterministic optimization shows the method to treat circle packing as quadratic optimization.


Tips for understanding the Pumping Lemma for Context-Free Languages

One way of looking at the pumping lemma is in terms of the pumping game, a two-player game parametrized by an infinite language $L$. The two players are the Prover and Challenger, and the game goes as follows:

Prover picks an integer $n$.
Challenger picks a word $w \in L$ of length at least $n$.
Prover chooses a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \ge 1$.
Challenger chooses an integer $i$.
If $xy^iz \in L$ then Prover wins, otherwise Challenger wins.

The pumping lemma states that:

  If $L$ is regular then Prover has a winning strategy.

The pumping lemma is often used in the contrapositive:

  If Challenger has a winning strategy then $L$ is not regular.

Here is an example: we will show that Challenger has a winning strategy for the language $L = \{a^nb^n : n \geq 0\}$.

In response to Prover's choice of $n$, Challenger chooses the word $w = a^n b^n$. In response to Prover's choice of a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \geq 1$, Challenger chooses $i=0$. Then $xy^iz = a^{n-|y|}b^n \notin L$, and so Challenger wins.


The importance of the membership problem

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.


Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

Now that we know the answer, we could simplify the proof.
Let's prove that $$T(n)\in\Theta\left(n^2\right)$$
Define $k=k_n$, index of $n$ in base $3/2$, to be the smallest $k$ such that $n/(3/2)^k<1$.

Upper bound:
Assume that $C$ is very large such that $T(1)\leq C=C\cdot1^2$, $1-3C<-C/2$, and that for all $k<K$ and all $m$ with index $k$ we have $$T(m)\leq C(m^2-1/2)$$
Note: We are going to use the $-1/2$ to carry out the induction as it was done in the other answer.
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. It follows that
$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\
&\leq 5C(n/3)^2-5C/2+C(2n/3)^2-C/2+1\\
&=Cn^2\left(5/3^2+(2/3)^2\right)+1-3C\\
&=Cn^2+1-3C\\
&\leq Cn^2-C/2\\
&=C(n^2-1/2)\end{align}$$

Lower bound:
Assume that $D$ is such that $D>0$, $T(1)\geq D\cdot 1^2=D$, $1-3D\geq -D/2$, and that for every $k<K$ and $m$ of index $k$ we have $$D(m^2-1/2)\leq T(m)$$
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Therefore,
$$\begin{align}
T(n)&=5T(n/3)+T(2n/3)+1\\
&\geq 5D((n/2)^2-1/2)+D((2n/3)^2-1/2)+1\\
&=Dn^2\left(5/3^2+1/(3/2)^2\right)-5D/2-D/2+1\\
&=Dn^2+1-3D\\
&\geq D\left(n^2-1/2\right)
\end{align}$$

By induction we have proven that for all $n$ we have $$D(n^2-1/2)\leq T(n)\leq C(n^2-1/2)$$
Therefore, $$T\in \Theta(n^2-1/2)=\Theta(n^2)$$


Trying to understand CLRS bucket sort analysis

You are asking why

$\qquad\displaystyle \sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik}
\quad=\quad \sum_{j=1}^{n}X_{ij}^2 + \sum_{j = 1}^{n}\sum_{1 \leq k \leq n,\\ k \neq j}X_{ij}X_{ik}$

holds (in expectation, but that's irrelevant for this; it might not always be, though!).

Note that the left-hand side and the second summand on the right-hand site are identical except for the $k \neq j$ constraint. That is, the difference between the two terms is exactly

$\qquad\displaystyle \sum_{j=1}^n \sum_{1 \leq k \leq n,\\k=j} X_{ij}X_{ik} \quad=\quad \sum_{j=1}^n X_{ij}X_{ij} \quad=\quad \sum_{j=1}^{n}X_{ij}^2$.

No deep insight here, just basic manipulation of sums.


Continuous Mutual Correction from Multiple Sensors

The broad area that studies these kinds of topics is called estimation theory.  This is more a matter of statistics than of computer science, so you might want to take a look in some statistics textbooks and check out the Statistics.SE.

For instance, you might be interested in the Kalman filter.

That said, before one can devise a solution to your specific solution, we'd need a lot more information about what you know.  Do you know anything about the joint distribution of their sensing?  Do you know anything about the accuracy of each sensor (e.g., its variance)?  Are all sensors calibrated and unbiased?  Do you know anything about how the underlying physical value changes over time or the distribution it comes from?  Do some self-study of the literature, and make sure you know the answers to those before asking on Stats.SE.


Is it possible to build a heap from the root to the leaves?

Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array).

There is a very cute data structure (on the implementation level) for priority queues that is based on binary trees, has the same heap ordering of keys, but is not perfectly balanced. They are called leftist trees.
Arbitrary leftist trees can be merged efficiently.
This efficiency is obtained by forcing a height balance between the two subtrees of a node. The shortest distance to a leaf is the measure for this balance.

Perhaps these leftist trees are a better binary tree implementation for priority queues than heaps (which are arrays disguised as trees)?


Have non-regular language classes of infinite words been studied?

We have the following MSO characterization of regular nested word languages:

  Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.

The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:

  Theorem  8.4 (MSO characterization of $\omega$-languages).
  A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.

Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.


Yes, there is a usage for the negative imaginary zero. But first, I will say something about the negative zero in general.

Why have a negative zero?

First of all, the main reason to have a signed zero for floating points is that floating points have only limited precision and we often want to distinguish the following cases of a real number $x$, represented by a floating point:

$x\geq 0$, which we will denote by $+0$.
$x<0$, which we will denoted by  $-0$.

As we cannot distinguish between these cases ordinarily in our floating point representation when $|x|$ is smaller than the floating point precision, we need a special notation for this. We want to distinguish between these two almost $0$ numbers, as this difference can be 'enlarged' with the appropriate function: when we have defined $1/0=\infty$ (we work with the extended reals) we have $+0={-0}$, but $1/{-0}={-\infty}\neq +\infty = 1/{+0}$.

The negative imaginary zero

For the following, consider a complex number $z=x+i\cdot y$, with $x$ the real part and $y$ the imaginary part, represented by a floating point for $x$ and another floating point for $y$.

One important application where we want to distinguish between $-0$ and $+0$ is when computing the inverse elementary functions (i.e. $\ln(z), \sqrt{z}, \arcsin(z)$) for the complex numbers. All these functions are defined in terms of $\ln(z)$, the complex logarithm.

I won't go into the details why, but this function is discontinuous on the whole negative real number line: $\ln(x + i\cdot +0)\neq \ln(x+i\cdot{-0})$ for all $x\leq 0$, this is half-line known as the branch cut of the complex logarithm. (Note that we also want to know the sign of $x$ here to see whether are 'on' this line in the first place!)

For example, we have $-4+i0 = -4 - i0$, but $2i=\sqrt{-4+i0 }\neq \sqrt{-4-i0}=-2i$. So, we need to distinguishing between $+i0$ and $-i0$ to know on which 'side' of the branch cut we are to compute the complex logarithm $\ln(x)$ and all other inverses of elementary functions defined from it. For more on this topic, see these notes by Prof. W. Kahan.


It looks like your question can be written formally

  $\exists i,j\in\{1,..,n\}\:\exists S\subseteq A_i\:\exists T\subseteq A_j :
(\sum_{y\in T}v_{i,y}>\sum_{x\in S}v_{i,x})\land (\sum_{x\in S}v_{j,x}>\sum_{y\in T}v_{j,y})$

If the above is true, then persons $i$ and $j$ benefit from swapping items from $S$ and $T$.

This is hard to decide. Here is an idea for a reduction. We simplify things by assuming there are only two persons $P_1$ and $P_2$, that $P_1$ has just coins and banknotes in $A_1$, that $P_2$ has just $A_2=\{x\}$ and that they would both profit if $P_1$ can buy item $x$ at price $V$ from $P_2$. This is because $v_{1,x}-1=V=v_{2,x}+1$, i.e., $P_1$ thinks that
by paying $V$ for $x$ he wins $1$, while $P_2$ thinks he wins $1$ by selling $x$. They will trade iff $P_1$ can find some coins and notes in his $A_1$ that add up to $V$ exactly (we assumes that $P_2$ only has $A_2=\{x\}$ so he cannot make any change). NB: the coins and notes are items $c\in A$ with $v_{1,c}=v_{2,c}$, their face value is the same for both persons.


If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

You are essentially asking the following question:

  Suppose that $f(n) \geq g(n)$ for some $n$. Is there a universal constant $C$ such that $\min_n f(n) \geq C \min_n g(n)$?

Hopefully this formulation makes it easier to answer.


Why can L3 caches hold only shared blocks?

Perhaps I can shed some light on associativity. These caches aren't just open blocks of memory, so don't think of them as some kind of generic container. Each block of memory has a real address (whether this is physical or virtual doesn't matter, just assume it is a fixed address). At each level of cache this memory can only be cached at very specific locations in the cache.

For example, memory address X can be stored in the L1 cache at location Y0. This is a direct mapping. But suppose it can also be stored at location Y1, then it is 2-way associative (which is fairly common). Being storable in N-locations makes it N-way associative. When the chip chooses a cache location it checks only these N places -- it does not scan the entire cache (which would be too slow/complicated).

This should clarify what they mean by saying the shared cache must have an aggregate higher associativity than the lower caches. So if L1 is 2-way, L2 is 4-way, and there are 4 processors, they shared cache must be > 24-way associative (I don't have the article, but this sounds like what they mean). This follows then, that at least one of these shared locations must not be cached in any of the private caches.

I can't say for sure what their "pathological" case is, but I can explain a common one, one that can affect things like binary search. Say the L1 cache is 1-way associative and 4KB in size. The locations where memory can be stored is likely a simple mod of the address (X mod 4K). Say then you have a large block of data which is a power of 2 (which is common). In a binary search you always chop the size in half, so a search on a 256K block would have you check address 128K, 64K, 32K, 16K, 8K, 4K, and the lower.  But you should see a problem here. Those first 6 addresses all map to the exact same cache location. So each access requires an eviction and load, despite you accessing only a tiny amount of memory.


How do I assign homes to hospitals based on locality? (clustering, kmeans?)

Construct a graph $G=(V,E)$ where $V$ contains two nodes $s$ and $t$, a node $u_x$ for each hospital $x \in X$, and a node $v_y$ for each home $y \in Y$.
There is an edge between $s$ and each $v_y$ of capacity 1.
There is an edge of capacity $10000$ between each $u_x$ and $t$.
Moreover, there is an edge $(v_y, u_x)$ if an only if $y$ is within $50$ miles from $x$. Edges $(v_y, u_x)$ have unbounded capacity.
Compute a maximum flow $f$ from $s$ to $t$. The value $|f|$ of the flow tells you the maximum number of homes that can be assigned to some hospital. Moreover, $f$ itself tells you a possible assignment: assign $y \in Y$ to $x \in X$ if and only if $f(v_y, u_x)=1$.


Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

This is a nice exercise.  You should probably do it yourself, to get the learning benefit.  I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example.  Basically, keep trying what you've been doing, but be more systematic and exhaustive about it.  You're on the right direction -- keep at it.


What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1

Yes, your NFA is correct. You are probably making some mistake during your conversion to a DFA.

Note that after the conversion from the NFA to the DFA, the states will no longer be $S = \{A,B,C,D,E\}$. Instead they will be all possible subsets of $S$. So in your case $A$ is not giving two different transitions to $C$ and $E$, instead it is giving one single transition to the state $\{C,E\}$


why recursive languages does not come under Chomsky hierarchy?

The hierarchy is defined in terms of grammars. It is still an open question whether there is a natural grammar formalism for recursive languages (check out this question), and certainly no such formalism had been known at the time Chomsky wrote his paper.


We will use the notation $\binom{n}{k}$ instead of your $C(n,k)$. The idea is to use Pascal's identity $$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$ and its proof: there are $\binom{n-1}{k}$ not containing $n$, and $\binom{n-1}{k-1}$ containing $n$. Suppose we want to encode combinations not containing $n$ before combinations containing $n$. We work recursively. If the input set $S$ doesn't contain $n$, then we recurse on $S$ as a combination in $[n-1]$. If it does contain $n$, we recurse on $S \setminus \{n\}$ as a combination in $[n-1]$ (of size $k-1$), and add $\binom{n-1}{k}$ to the result.

Here is Python code for the procedure:

def encode(n, k, S):
    if n == 0:
        return 0
    if n not in S:
        return encode(n-1, k, S)
    S.remove(n)
    return encode(n-1, k-1, S) + choose(n-1, k)

The function choose (not supplied) should compute the Binomial coefficient. You can also decode the resulting code:

def decode(n, k, C):
    if n == 0:
        return []
    if C < choose(n-1, k):
        return decode(n-1, k, C)
    C -= choose(n-1, k)
    return decode(n-1, k-1, C) + [n]


This notion seems to be a measure of uniformity. If $\sigma=1$ you get a uniform distribution on $\{0,1\}^n$ (since the sum over all strings of length $n$ is $1$), but for other $\sigma$s (e.g. $\sigma = 2^{-k}$) it's still  distribution on $\{0,1\}^n$, not on $\{0,1\}^{n-k}$ or similar. Thus saying that a distribution on another (disjoint) set is an upper bound is absolutely wrong (but they are related, s.b.).

If for some $x$ the probability is greater than $\frac{1}{2^n}$ it has to be smaller for others. On the other hand for $\sigma=\frac{1}{2}$ at least half of the strings have nonzero probability since the sum of any number of elements $< 2^{n-1}$ is smaller than $1$. This holds for any $\sigma > 0$, i.e. $\sigma 2^n$ elements have nonzero probability.

Using this you can compare the distribution for $\sigma=2^{-k}$ to the distribution for $\sigma=1$ (i.e. uniform) on $\{0,1\}^{n-k}$. It's easy to see that the entropy of the distribution with $\sigma=2^{-k}$ on $\{0,1\}^n$ (let $H$ be a random variable with this distribution) is at least the entropy of the uniform distribution on $\{0,1\}^{n-k}$ (RV denoted by $U$) since for every injection $f: \{0,1\}^{n-k}\rightarrow \{0,1\}^n:$
$$\mathbb{P}(U=x)\geq \mathbb{P}(H=f(x)) \quad .$$


Is the language of words that are unbalanced in the first half context-free?

Perhaps it can be proved using Ogden's Lemma and its generalization by Bader and Moura, this is a rather informal sketch of the proof.
First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \{ 0,1 \}$ and $\Sigma' = \{ a, b, c\}$:
$h(11) \to a$
$h(00) \to b$
$h(01) \to c$
$h(10) \to c$
If $L$ is CF then also the new language $L'$ obtained is CF by closure properties.
Informally $L'$ contains an unbalanced number of $a$ and $b$ in the first half and the number/occurences of $c$ doesn't matter.
Further restrict $L'$ by intersecting it with the regular language $R = \{ a^* (c^* b^*)^*  \}$; let $L'' = R \cap L'$
For example the string
$a a c b | cccc \in L''$ corresponds to $11\;11\;10\;00\; |\; 10\;10\;10\;10 \in L$ ($|$ is used to mark the half of the string for better readability)
$a b c c | cccc \notin L''$ corresponds to $11\;00\;10\;10\;|\;10\;10\;10\;10 \notin L$
Suppose that $L''$ is CF, and $p$ is its pumping length. Build $w \in L''$ concatenating these four parts:

$(\;a^p\;)$ leading $a$'s

$(\;c^j\;)$ a sequence of $c$s, we'll fix $j$ below

$(\;c^{p} \;b\;)$ repeated $p + p!$

If $n$ is the constant of the Bader-Moura's condition, then we pick $j$ large enough to exclude all the symbols in part 1 and 3: $j \geq n^{p+(p+1)(p+p!)+1}$

$(c^k)$ where $k$ is large enough to be pumped exluding all  previous symbols: $k \geq n^{p + j + (p+1)(p+p!)+1}$

$w = a^{p} \; c^j \; (c^{p} \;b )^{p+p!} \; c^{k} $
Now we mark the first $a$ sequence as distinguished, the string $vx$ must contain $0 < q \leq p$ distinguished positions ($\#a_{vx} = q$) by Ogden's lemma; $vx$ can also contain one $b$ (not more than one because the $b$s are spaced with more than $p$ symbols $c$) and $0 \leq r < p$ symbols $c$ ($\#c_{vx} = r$).

if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=0$, $\#c_{vx}=r$:

then we can pump $i = p! / q $ times and we obtain the same number of $a$s and $b$s; if after the pump some $b$s fall after the half of the string, we can pump the final $c^k$ independently from the rest of the string and we can "push" all $a$s and $b$s back in the first half (and $\#a_{w'} = \#b_{w'} = p + p!$), so the pumped string $w'$ is not in $L''$

if $vx$ is such that $\#a_{vx}=q$, $\#b_{vx}=1$, $\#c_{vx}=r$:

then each time we pump we increase the number of $a$s and $b$s, but we cannot guarantee that we reach the same number (e.g. in the case $\#a_{vx}=q=1\#b_{vx}$). But in this case the derivation tree "isolate" the $c^j$ part of the string from the final part $c^k$, so we can pump them independently.
We can pump $c^j$ as many time as needed to "push" $p!$ symbols $b$s to the second half of the string. Suppose that the pumping length of $c^j$ is $s$ (that must be even), the half of the string is shifted towards the $b$s by $s/2$. We have $s \leq p$ so after each pump at most one $b$ is "pushed" to the second half, because the "distance" between $b$s is $p$. So also in this case we get a string $w'$ not in $L''$


Part 1 looks OK.

For part 2, to show no witnesses exist, you have to proceed by contradiction. Assume witnesses $c,m$ exist, so we have $n^2 \leq cn$ for all $n\geq m$. Now, to reach a contradiction, find at least one value of $n \geq m$ for which $n^2 > cn$. The value for $n$ can be defined in terms of $c,m$. It shouldn't be too hard to find one.

For part 3, the text suggests to use 2. That is, to prove that if we had (by contradiction) witnesses for 3, we could derive from them some witnesses for 2.

(Honestly, to me this way sounds harder than simply tackling 3 on its own, without exploiting 2. Maybe you were introduced to some theorem which can apply here to shorten the exercise? I have no idea.)


What is this question asking for?-->Test this code, find an error in the program and "construct an instance to demonstrate the error" (in C)

As noted by Tom van der Zanden in a comment, and given you already know what's wrong with the code, think of an input that will cause the program to fail, just run the program with that input and you have your instance. Does it make more sense if you think of the phrase, "for instance"?

You may be overthinking it (a good sign actually), if this is just a very basic C language course, they are probably being rather obvious in what they are asking for.

KISS -- Keep It Simple, Sailor


Division by a constant can always be recast as multiplication by a constant followed by a shift.  The relevant papers are:

Robert Alverson, "Integer Division Using Reciprocals," IEEE Int'l Symp Comp Arithmetic, (ISCA-10):186-190, 1991.

Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," ACM Conf on Prog Lang Dsgn and Impl, (PLDI-1994):61-72.

Daniel J. Magenheimer, Liz Peters, Karl W. Peters, and Dan Zuras, "Integer Multiplication and Division on the HP Precision Architecture," IEEE T. Comp., 37(8):980-990, August 1988.


Proving that $ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$?

One of the equalities 12 tell us that now
$(u\cup v)^* = u^*(vu^*)^*$.
Applying this to the last expression we obtain
$(b\cup (a\cup\lambda))^*$.

Also $(u\cup \lambda)^* = (u^*\lambda^*)^* =
(u^* \lambda)^* = (u^*)^* = u^*$.

Do you have associativity of $\cup$ so that $(b\cup (a\cup\lambda))^* = ((b\cup a)\cup\lambda))^*$? It should be a basic property.


What's the correct term for this analog of cryptography?

It's not an exact match to your question, but you're probably looking for something in the field of steganography.


A question on the linear speedup theorem

I didn't check your working but your conclusion isn't at all absurd.  For every Turing machine that decides $L$, and for every $x\in\Sigma^*$, there is another Turing machine $M_x$ that decides $L$ and that runs for exactly $|x|+1$ steps on input $x$. Note that this is more than twice as fast as your conclusion of $2|x|+4$. This also means that, for all languages $L$ and all strings $x\in\Sigma^*$, $t^L(x)=|x|+1$.

$M_x$ operates as follows. First, it reads the first $|x|+1$ characters of the input.  If these are the string $x$ followed by a blank, it accepts if $x\in L$ and rejects if $x\notin L$; if they are not $x$ plus a blank, it returns to the left-hand end of the tape and does whatever $M$ would do. Note that $M_x$ does not need to contain any algorithm to decide whether $x\in L$. If $x\in L$, the machine is programmed "If my input is $x$, accept it; otherwise, rewind and do what $M$ would do.", and if $x\notin L$, the machine is programmed "If my input is $x$, reject it; otherwise, rewind and do what $M$ would do."


Your DFA does not recognize $(a|b)^*abb$. For example it does not recognize $abb$.


for two languages in $NP$ does one of them karp reducible to another?

The theorem, as stated, is false: if $A=\emptyset$ and $B=\Sigma$, then we cannot reduce either of them to the other. If take either of $A,B$ to be non-trivial problems in $P$, the claim is true, which is not hard to show (see here). If either of $A,B$ is NP-complete, then the claim also holds by definition of NP-hardness.

So, the only case left is for problems $A,B\in NP-(NPC\cup P)$, the NP-intermediate problems. Note that such problems exist if and only if $P\neq NP$.

It would not be very surprising to me for two NP-intermediate problems to be incomparable, but this would be very hard to prove, as we currently do not have a good idea of what problems even could be NP-intermediate. So, it would seem that the full answer to your question is an open problem, but if I had to guess then I'd guess the answer is no.


How can I draw a Moore diagram for a given circuit?

Don't try to draw the automata. Because there will be 32 states each having five transitions. Rather try to describe the transition function and output as hinted by DylanSp. i.e.

q01001 -> 1 -> q11001 (output 1), meaning if switches 2,5 are on and you put on switch 1, the lamp is lighted.

Another one.
q11001->2->q10001 (output 0), meaning if switch 1,2 and 5 are on and you put off switch 2 than the lamp is unlighted.

I assume that input consists of a sequence of 1,2,3,4,5 indicating which switch is flipped. starting state is q00000. I assume, final state will be probably those transitions where lamp is lighted, if that is what you are trying to do.