Is there a language with non-isomorphic minimum-state UFAs? For all regular languages L, by the Myhill-Nerode classes, all state-minimal DFAs for L are isomorphic.  On the other hand, "a regular language may have many non-isomorphic state-minimal nfas".  What about Unambiguous Finite Automata?  Every DFA is also a UFA, so every regular language has at least one UFA.  The natural numbers are well-ordered, so in turn every regular language has at least one state-minimal UFA.

Is there a regular language whose state-minimal Unambiguous Finite Automata are not all isomorphic to each other?

In their paper "A note about minimal non-deterministic automata" Arnold, Dicky and Nivat observe that the problem of finding non-isomorphic minimal automata was solved in a report by Christian Carrez (Lille, 1970).

They give the following example, which happen to be both unambiguous, so are applicable in your case too.


Why does backtracking work the way it does? I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking and Divide et Impera.

The example problem that I chose for my questions is the n queens problem (given n queens and a n*n chessboard, how do you position the queens such that they can't attack each other?).
I understood that the basic idea is to generate all possible placements (by generating a cartesian product) and then simply discarding them as they come along if they are invalid (through the validation function).

Here is my sample implementation:

    int valid (int k)
    {
    for (int i = 1; i < k; i++)
    {
        if (sol[i] == sol[k]) return 0;
        if (abs(sol[i] - sol[k]) == abs(i - k)) return 0;
    }
    return 1;
}

void print ()
{
    for (int i = 1; i <= n; i++)
    {
        cout << sol[i];
    }
    cout << endl;
    how++;
}

void backtrack (int k)
{
    if (k == n+1) print();
    else
    {
        sol[k] = 0;
        while (sol[k] < n)
        {
            sol[k]++;
            if (valid(k)) backtrack(k+1);
        }
    }
}

Why is it that in the validation function, the checking of the solution is done progressively by checking 1 with k, 2 with k and so on. I think that the solution can be correct in pairs of (i, k) but wrong overall (for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly)?

for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly?

You have already tested that 1 and 2 are placed correctly, otherwise you wouldn't call backtrack(3).

Recall that sol[i] = j means that the queen in column $i$ is put at row $j$.  By calling backtrack(k+1) you have already verified that every queen in $1 \dots k$ are placed correctly (non-colliding).


Checking if there is a single path that visits all nodes in a directed graph Given a directed acyclic graph G, give a linear time algorithm to determine if the
graph has a directed path that visits every vertex.

You can assume you are given a list of nodes and two adjacency lists: Enter[v] which contains all the edges entering node v, and Exit[v] which contains all the edges leaving node v.
I was thinking that I could pick a node that doesn't have edges entering it and run DFS on it. During DFS, every time I get to a node with no children, I check if all the nodes have been visited. If not, I backtrack and explore a different path each time. If I make it back to the original node or if I hit a node with no children, I can check if I have seen all the nodes. If not, I return that there is no such path, else I have found a path.
Would this work?

The problem is how to deal with visited vertex.

If you keep following, the time complexity is not linear because of repeated visiting. Otherwise, your algorithm will fail in the following simple example:

1 --> 2 -----------> 3 --> 4
        \         /
         --> 5 -->

The first search find 1-2-3-4, then it goes back to 2 and find 1-2-5-3. Now because 3 is visited, the search stops, and thus finally fails.

A hint (or answer) to solve the problem: performing a topological ordering firstly.


Combining Production Rules using Reinforcement Learning Production systems have been used to solve puzzles such as the Tower of Hanoi for years with hard-coded production rules. However, has there been any research in using reinforcement learning to combine basic production rules into more complex ones with the goal of solving a puzzle?

Note that I've asked a similar question on Cogsci.SE, but with a greater cognitive perspective. In my opinion, the two perspectives are different enough to merit semi-cross-posting.

this writeup by Kenan Deen solves the Tower of Hanoi problem with reinforcement learning and Markoff decision processes.

Tower of Hanoi – Reinforcement Learning

there is some other research on using genetic programming in "solving" (successfully playing) video games. these approaches do find "subroutines" that can be regarded as subgoals. for example, in playing pacman, an algorithm might have a subroutine/ subgoal that eats ghosts if they are blue, otherwise, run away from them. the sample algorithms are sometimes encoded as LISP-like trees. see eg

Evolving diverse Ms. Pac-Man playing agents using genetic programming / Lucas.
possibly the earliest case of this technique for solving pacman was reported by Koza in 1992 in the book Genetic Programming: on the programming of computers by means of natural selection


which neural network is good for predecting the value of strings I have a dataset that contains some strings. A numeric value is assigned to each string.
I want to develop a machine learning (deep learning) model to get a string and predict its value.
What neural network do you suggest for this model? Should I use RNN (LSTM)?

Assuming the strings are variable-length, a recurrent neural network would be a reasonable choice: either a LSTM or a convolutional network.


Are IEEE floating point numbers intervals or point values? The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision for a given number of computations.

Now, I am wondering whether floating point numbers, i.e., the objects represented and manipulated in such a system, should be looked at as intervals—a contiguous set real numbers—or as point values—a unique real number. (Which interval? Crudely, with round-to-nearest, the nominal value plus-or-minus half a ulp.)

The arguments for intervals I see come mostly from the representational aspects of the system:

Numbers from ‘outside’ of the system—measurement data, say—are encoded with reduced precision and so the bit-level representation is in general clearly not the ‘true’ value, but—given the information about the rounding rule used—represents an interval in which the ‘true’ value lies.
Numbers from ‘inside’ of the system that are the result of a series of computations within the system have also been subject to the effects of intermediate rounding and so again—given the information about the rounding rule used—represents an interval in which the ‘true’ resulting value of the computation lies.

The arguments for point values I see come from the computational aspects of the system and the typical discussions of floating point:

Computations are performed on the real value that nominally corresponds to the bit-level representation, using some extra bits to enable precision guarantees. They are not applied to the interval bounds implied by the bit-level representation (and information about the rounding rule used in its generation), which would be possible in principle using some extra bits and double the effort (each computational step…).
Put differently: interval analysis is not applied.
If interval analysis were used, rounding rules would not be needed.
In the discussions of floating point I have seen, they are always generally treated as point values, e.g., depicting them as discrete points on the real line.

Now, the above arguments are composed by someone that has not read up on the floating point literature in detail, so they may not represent the common view among knowledgeable people in the field. I would like to learn the views of these people and the arguments used. (So I am not necessarily looking for an answer ‘point values’/‘intervals’ to the binary question of the title of this question.)

I have not specified restrictions to the binary or decimal systems. This may be relevant, I feel: in the binary case, the representations are normalized, so no significance information is available, but in the decimal case, the representation is not normalized. This means, I think, that in the latter case a crude way of doing interval analysis is possible (by reducing the number of significant digits)—not that this means it is actually done—, but in the former case, such crude analysis is not possible (although it would be far less crude, given the small magnitude steps—factors of 2).

That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings.

If you tried to claim that IEEE 754 floating point numbers did represent intervals, then you would run into deep, deep trouble when you try to define floating-point arithmetic.


Running time - Linked Lists Polynomial I have developed two algorithms and now they are asking me to find their running time.
The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are addition and multiplication.

In general for lists the running for these two operations are ($x,y$ are the lists lengths):

Addition: Time $O(x+y)$, space $O(x+y)$
Multiplication: Time $O(xy \log(xy))$, space $O(xy)$

Can someone help me to find the running times of my algorithms?
I think for the first algorithm it is like stated above $O(x+y)$, for the second one I have two nested loops and two lists so it should be $O(xy)$, but why the $O(xy \log(xy))$ above?

These are the algorithms I developed (in Pseudocode):

 PolynomialAdd(Poly1, Poly2):
 Degree := MaxDegree(Poly1.head, Poly2.head);
 while (Degree >=0) do:
      Node1 := Poly1.head;
      while (Node1 IS NOT NIL) do:
         if(Node1.Deg = Degree) then break;
         else Node1 = Node1.next;
      Node2 := Poly2.head;
      while (Node2 IS NOT NIL) do:
         if(Node2.Deg = Degree) then break;
         else Node2 = Node2.next;
      if (Node1 IS NOT NIL AND Node2 IS NOT NIL) then
         PolyResult.insertTerm( Node1.Coeff + Node2.Coeff, Node1.Deg);
      else if (Node1 IS NOT NIL) then
         PolyResult.insertTerm(Node1.Coeff, Node1.Deg);
      else if (Node2 IS NOT NIL) then
         PolyResult.insertTerm(Node2.Coeff, Node2.Deg);
      Degree := Degree – 1;
 return PolyResult;

 PolynomialMul(Poly1, Poly2):
 Node1 := Poly1.head;
 while (Node1 IS NOT NIL) do:
      Node2 = Poly2.head;
      while (Node2 IS NOT NIL) do:
           PolyResult.insertTerm(Node1.Coeff * Node2.Coeff,
                              Node1.Deg + Node1.Deg);
           Node2 = Node2.next;
      Node1 = Node1.next;
 return PolyResult;

InsertTerm inserts the term in the correct place depending on the degree of the term.

 InsertTerm(Coeff, Deg):
 NewNode.Coeff := Coeff;
 NewNode.Deg := Deg;
 if List.head = NIL then
    List.head := NewNode;
 else if NewNode.Deg > List.head.Deg then
    NewNode.next := List.head;
    List.head := NewNode;
 else if NewNode.Deg = List.head.Deg then
    AddCoeff(NewNode, List.head);
 else
    Go through the List till find the same Degree and summing up the coefficient OR
    adding a new Term in the right position if Degree not present;

The running time of the InsertTerm subroutine is $\Theta(n)$ where $n$ is the number of terms in the polynomial, and this is the worst-case complexity as well as the average-case complexity absent any information about the monomial being inserted.

The outer loop of PolynomialAdd runs MaxDegree(Poly1.head, Poly2.head) times. Inside each iteration, the inner loops search for a node with the right degrees in each polynomial. For terms of degrees that are absent from the monomial, or present near the end of the monomial, the running time of the inner loop is $\Theta(n)$ where $n$ is the number of terms in the respective monomial. The running time of InsertTerm has been discussed above; here all I need to know is that its $\Theta(n)$. Hence the running time of PolynomialAdd is $\Theta(\max(x,y) \cdot (x + y))$ where $x$ and $y$ are the number of terms in the polynomials Poly1 and Poly2 respectively.

The number of calls to InsertTerm in PolynomialMul is clearly $xy$, since the outer loop always runs $x$ times and the inner loop always runs $y$ times. I assume that Node1.Deg + Node1.Deg is a typo and you really meant Node1.Deg + Node2.Deg. I won't give a full proof here, but intuitively speaking, this is going back and forth inside the result list, and so on average the time spent in insertTerm is about half the length of the list: $\Theta(x+y)$. Therefore the running time of PolynomialMul is $\Theta(x\,y\,(x+y))$.

It is possible to implement polynomial addition and multiplication with faster running times, but you'll need to improve your code. The core idea is that you waste a lot of time in InsertTerm, inserting at random positions in the result list. Instead, arrange to construct the result list in order: first the lowest-degree term at the end of the list, then the previous term, etc. (Alternatively, if you find it easier, construct the list in the other order, starting with the highest-degree term and maintaining a pointer to the next pointer in the last node). Furthermore, do not traverse the arguments again on each iteration through the loop: in addition, iterate over the two arguments simultaneously; in multiplication, where you need to combine terms of different degrees, remember where you stopped so you can start again from the same point.


What is the point of (Compactness theorem in the) Overspill principle? The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states

  Let $\phi$ be a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a model of $\phi$ with at least $n$
  elements. Then $\phi$ has a model with infinitely many elements.

IMO, it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite. What needs to be proven here? There are no other options obviously for any school kid.

PS The answers state that there is a difference between having infinite amount of models and single infinite model. But this is similarly stupid. At first, I do not see whether I claim that I have a single infinite model or approach it by having all denumerable models. Secondly, it does not matter since in any case you should have an infinite model in order to respond to any natural number.

Nevertheless, I started to understand why people (mistakenly) ask me to differentiate between infinite amount of models and models of infinite size. They fail to recognize that principle "The fact that I can always name a number larger than yours implies that we have an infinite model/set", which is intuitive and used to prove the overspill theorem, also implies that the model of infinite size exists. The set of models $A = \{M_k, M_l, M_m \ldots\}$ has sizes $S = \{k, l, m, \ldots\}$ correspondingly. When you speak about size of models, you basically speak of the numbers in $S$. When you say "a model of size n" you just say "n". Thus, we can forget about set of models and speak only about S. Now, you say that "whatever integer you have, set S contains a larger one." This basically means that S contains an infinite number (i.e. $A$ contains infinite models). What to be proven here?

In other words, what is the point of expanding $\phi$ with infinite set $\{I_1, I_2, \ldots\}$ in the proof and applying the Compactness theorem? This says that there is an infinite model. But this is obvious without even without it, right from the the premise of the overspill principle.

The theorem says that when a sentence has arbitrarily large (finite) models, then it also has infinite models.

The antecedent of the theorem:

  $\phi$ is a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a model of $\phi$ with at least $n$
  elements.

is equivalent to saying that there are infinitely many different models,
but it does not state that any of these models are infinite in size.

In fact, it would be clearer to use:

  $\phi$ is a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a finite model of $\phi$ with at least $n$
  elements.

This is not exactly the same statement, but as an antecedent within this theorem, it is equivalent.

The consequent:

  $\phi$ has a model with infinitely many elements.

does not say anything about how many different models there are - it just says something about the size of at least one of them.

To see that the truth of this theorem doesn't simply follow from its structure, consider the following statement, which has the same structure:

  Let $\phi$ be a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is an equivalent sentence of predicate logic with at least $n$ elements. Then there is an equivalent sentence with infinitely many elements.

Is this a theorem, too?  No, this statement is false, for the simple reason that all sentences of predicate logic have finitely many elements by definition.


Principle of Duality I would like to know how to alter/add NOTs when applying Duality principle.

Suppose I have P = XY(X+Y) +  NOT(Y), how to find its dual?

My book says that while applying Duality Principle to a relation:

Change all 0s to 1s
Change all ORs to ANDs
Change all ANDs to ORs

But it doesn't say anything about NOTs.

In the dual boolean algebra, NOT is the same NOT operation we have in the original boolean algebra.

Your book does not say anything to handle NOT because there's nothing that needs to be done. Simply leave the NOTs unaffected in your formula.


Showing the following sequents are not valid $\lnot \forall x P(x) \models \forall x \lnot P(x)$
$P(x) : x$ is divisible by 2
or $P(x) : x$ is a dog.
or $P(x) can be anything.

I want to show the following sequents are not valid ..Isn't the following sequents equal or the first sequent the whole negation of the statement and the second sequent is the negation of the $P(x)$ .. Can anybody explain this with examples?

First, $\phi \models \psi $ means that $\psi$ is a consequence of $\phi$. In other words, if $M$ is a structure and if $M \models \phi$ ($M$ models $\phi$) then $M \models \psi$ ($M$ also models $\psi$).

Now, regarding your statement $$\lnot \forall x P(x) \models \forall x \lnot P(x)$$
clearly $\forall x \lnot P(x)$ is not a consequence of $\lnot \forall x P(x)$. To show it consider the set of natural numbers as a structure $M$ and $P(x)$ as the predicate "$x$ is divisible by $2$". Then
$$\lnot \forall x P(x)$$
means "Not for all $x$, $x$ is divisible by $2$ which is a true sentence (since in fact odd numbers are not divisible by 2), while
$$ \forall x \lnot P(x)$$
means "For all $x$, $x$ is not divisible by $2$" which is not a true sentence (since in fact even numbers are divisible by $2$).

So, the structure $M$ (the set of natural numbers) is an example showing that $M \models \lnot \forall x P(x)$, but $M \nvDash  \forall x \lnot P(x)$ and your statement
$$\lnot \forall x P(x) \models \forall x \lnot P(x)$$
is not true.


Under what conditions is K-means clustering transformation-invariant? Given a set of data points $X = \{x_1, x_2, \ldots, x_m\}$ where $x_i \in \mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c_1, c_2, \ldots, c_k$.

Now, if we create a new dataset $Y = \{y_1, y_2, \ldots, y_m\}$ where $y_i = Ax_i + b$ and $y_i \in \mathbb{R}^d$ and run K-means on $Y$ to get clusters $g_1, g_2, \ldots g_k$.

Under what conditions of $A$ and $b$ are we guaranteed to get the same clusters?

Let's assume that K-means is using the euclidean distance and has same initial conditions on both algorithms, that is, if the initial centers for X are $c^0_1, \ldots, c^0_k$ then the initial centers for Y are $g^0_1, \ldots, g^0_k$ where $g^0_i = Ac^0_i + b$.

So far I've thought that $A$ has to be full rank and $b$ can be any vector. However, I haven't been able to prove it.

The answer depends on your K-means algorithm, but what follows should work for standard algorithms.

You will get the same result if your transformation $T$ satisfies two conditions:

It preserves distances: $d(z,w) = d(T(z),T(w))$, where $d$ is your metric, say $d(z,w) = \|z-w\|$.
It preserves averages: if $\sum_i p_i z_i$ is a convex combination that $T(\sum_i p_i z_i) = \sum_i p_i T(z_i)$.

You can check this by going over the algorithm, showing that it always makes the same choices.


Polynomial Hierarchy --- polynomial time TM Consider, for example, the definition for $\Sigma_2^p$ complexity class.

$$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$

where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some polynomial $p$. Here, $M$ must be polynomial time. But polynomial in the size of what exactly? For example, if we choose (guess) some $u_1$, do I consider it to be fixed size when talking about time complexity of $M$? More precisely, should $M$ be polynomial only in the size of $x$?

An example. Consider the problem whether, given a graph $A$, there exists a graph
$B$ such that $B$ is subgraph isomorphic to $A$.

$$A \in L \Leftrightarrow \exists B \; \text{SubGraphIsomorphic}(A, B) = 1 $$

Now, subgraph isomorphism is NP-complete. If $B$ is fixed, then there is a TM
that implements $\text{SubGraphIsomorphic}$ in deterministic polynomial time. If $B$ is not fixed, then I cannot claim such a thing unless I know $\sf P=NP$. Is this problem in $\Sigma_{1}^{p}$, i.e. $\sf NP$? (Ok, this problem has trivial solutions, but I hope it helps to pinpoint my confusion.)

My confusion generalizes for all $\Sigma_{i}^p$.

Your definition of $\Sigma_2^P$ is a bit misleading. Both $u_1$ and $u_2$ have to be bounded in length by some polynomial in $|x|$, and this usually forms part of the formula rather than part of the descriptive text. The predicate $M$ has to be polynomial time in the combined input length, which is the same as being polynomial time in $|x|$ since both $u_1$ and $u_2$ have length polynomial in $|x|$.

You have not described the predicate SubgraphIsomorphic correctly. You are given two graphs $A,B$, and you have to decide whether $B$ is isomorphic to a subgraph of $A$. We write it as an NP-predicate as follows:
$$(A,B) \in \mathrm{SubgraphIsomorphic} \leftrightarrow \exists |P| \leq |(A,B)| \mathrm{Isomorphic}(A,B,P), $$
where $\mathrm{Isomorphic}(A,B,P)$ is true if $P$ encodes an injection from the vertex set of $B$ to the vertex set of $A$, and $(x,y)$ is an edge of $B$ iff $(P(x),P(y))$ is an edge of $A$. This is a polytime predicate. Moreover, the injection can be coded in length polynomial in the input $(A,B)$ (for simplicity, I'm assuming that the encoding is such that $|P| \leq |(A,B)|$).


What does instantiating existential variables with out of scope variable imply? I have following unfinished proof of a lemma:

Goal forall (P : Type -> Prop) (Q : Prop),
  ((forall x, (P x)) -> Q) -> (exists x, P x -> Q).
Proof.
  intros.
  eapply ex_intro. intros. apply H. intros. eapply H0.

The problem is the last eapply failed, with the message

Error:
In environment
P : Type -> Prop
Q : Prop
H : (forall x : Type, P x) -> Q
H0 : P ?x
x : Type
Unable to unify "?x" with "x" (cannot instantiate "?x" because "x" is not in
its scope: available
arguments are "P" "Q" "H").

The proof steps themselves look very phishy already. The proof constructs an existential variables to sit in place of $x$ in the second half, and then tries to instantiate it using the $x$ obtained as premise after applying the hypothesis (forall x, (P x)) -> Q. The proof steps look cyclic proof to me.

What in general does this message imply? What types of logical mistake does this message indicate here?

There is a recent github issue from Coq actually indicates that instantiating evars outside of scope CAN prove falsehood, except that it's blocked by QED.

https://github.com/coq/coq/issues/8215

When you do an existential introduction, you are saying there is some term $t$, which is represented by the unification variable ?x, such that $P(t)\to Q$. You then try to apply $P(t)$ to $H : (\forall x.P(x)) \to Q$. It tries to generalize P ?x, because if it can show that $P(c)$ for a fresh constant $c$ (represented by x in the Coq output), then $\forall x.P(x)$ would follow. It attempts to unify that fresh constant, x, with the unification variable ?x, but this is disallowed. From a logical perspective, ?x represents a term $t$ and that term is, by definition freshness, distinct from the fresh $c$ (i.e. x) which is just to say $c$ wasn't in scope when we introduced $t$, so $t$ can't have depended on it.

As a simpler scenario, we can't prove $\exists x.\forall y.x = y$ by using existential introduction with $y$. $y$ isn't in scope at that point.


Reducing 3SAT to a Set Splitting Problem I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the fact if it is possible to color the items red and blue so that each set $S_i$ contains at least one red item and at least one blue item.

I know this this problem is in NP and it is fairly simple to prove (at least that is what I think).

I actually want to prove that the problem is NP hard by reduction from 3SAT. I want to be able to convert an instance of 3SAT into an instance of the aforementioned set-splitting such that a yes instance of 3SAT get mapped to a yes instance of set-splitting and vice versa.

I have a basic intuition about how I can do this: given a 3SAT formula $f$ on $n$ variables I will create $2n+1$ items. One to denote each $x_i$ one for each $\overline{x_i}$ and an extra item.
I am not quite sure how to proceed beyond this basic intuition. This might be a gap in my understanding of the problem. Is this the right way to approach this? If so, how can I use this intuition to actually prove that this is NP hard by way of reduction from 3SAT?

Thank you!

Your problem is a generalization of NAE-SAT, an NP-complete version of SAT (see for example David Witmer's lecture notes in which we want each clause to have at least one satisfied literal and at least one falsified literal.

In order to convert NAE-SAT to your problem, identify literals with items, have a set per clause, and also have a set per variable, forcing the two literals to get opposite colors. Details left to you.


Potential function binary heap extract max O(1) I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.

I know that the insert function should "pay" more in order to reduce the cost of the extraction, and this has to be in regards to the height of the heap (if $ \lfloor \log(n) \rfloor $ gives the height of the heap should the insert be $2\log(n)$ or $ \sum_{k=1}^n 2\log(k) $)

Try the following:

The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function

$$\Phi(H)=\sum_{i\in H}2  w_i.$$

Let us now analyze the heap operations. For insert you add a new element add depth $d$ at most $\log(n)$. This increases the potential by $2d$, and can be done in $O(1)$ time. Then you "bubble up" the new heap element to assure the heap-property. This takes $O(\log n)$ time and leaves $\Phi(H)$ unchanged. Thus the costs for insert are $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$.

Now consider the extractMin. You take out the root and replace it by the last element in the heap. This decreases the potential by $2\log(n)$, thus you can afford to repair the heap property, and therefore the amortized costs are now $O(1)$.

If you have a general question for the potential function you should pose this as a different question.


Correlation between high cpu/ram usage and poor computer performance I'm researching electromigration and the effects of high cpu/ram usage on a computer.

There are tons of discussions on these topics taking place via forums and message boards, but I am looking for credible sources that are backed by metrics.

There's a general-interest article from the IEEE about transistor aging that's based on the paper "An Array-Based Odometer System for Statistically Significant Circuit Aging Characterization" (2011) by Keane, Zhang, and Kim. They present:

  A system that facilitates efficient statistical aging measurements involving the mechanisms of bias temperature instability (BTI) and hot carrier injection (HCI) stress.

Roberto Lacerda de Orio's dissertation "Electromigration Modeling and Simulation" (2010) has a comprehensive treatment of the physics of electromigration, as well as a numerical model and "several simulation studies of electromigration".

You may find more references in this SuperUser thread.


proof of convergence in arbitrary precision PRNGs consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow).

srand(x)
z = 0
while (z >= 0)
{
  r = rand(100)
  if (r <= 50) z -= 1
  else z += 1
}

the PRNG is inited with seed x (also arbitrary precision). the PRNG rand(100) generates a value between 0..99. hence for 51 values the accumulator var z is decremented, for 49 values it is incremented.

it is expected due to the law of large numbers that this program will halt for all initial seeds x. however,

  how does one prove it will halt for all initial seeds x?

it seems such a proof must depend on the details of the construction of the PRNG. am assuming there exist PRNGs such that a different random sequence is generated for every initial seed x (ie the infinite set of naturals). that in itself may be up for question. are such PRNGs known? where are they used? etc.. so an answer may come up with an arbitrary PRNG for the purposes of the question. a single example fulfilling the criteria would be an acceptable answer.

looking for related literature, similar problems/proof considered, etc.

You ask us for a proof this program will always halt for all initial seeds, but no such proof is possible in general.  For instance, if the PRNG always outputs the number 66, then this will never halt (assuming you use big integers).  Obviously that would be a really lousy PRNG, but if you aren't willing to assume that the PRNG is good, then no proof is possible.

On the other hand, if you assume that the PRNG is good (i.e., computationally indistinguishable from truly random values), then this is not really a question about PRNGs.  Indeed, it's not even a question about computer science.  It is a question about whether a particular random walk will eventually return to its starting point.  (As such, this question really belongs on a mathematics site, not CS.SE.)

You ask for a proof that the random walk will never return to its starting point (that the probability of return to the initial point is exactly zero).  I do not think any such proof is possible, because I do not think the statement is actually true.


Question about how can i determine if counting sort is the right option over other sorting algorithms So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm.

Now i find that solutions for that question given by my professors are wrong because they do gave this as answer:( pseudocode)

Sorting(A,k) //where k is a value inserted by the user(?)
{
max=a[0];
for i=1 to n // n=dim
{
    if( a[i] > max) update max with a[i]
}
if( max <= k*n) then countingsort(A)

else heapsort(A);

return A;

Now that being said, if k is really a value inserted by the user, this makes that solution not really case sensitive or a proper valuation of counting sort time complexity. It seems to me that it isnt a general algorithm, which should be instead the purpose of that exercise i guess.
my solution is:

Sort(A){
    int max, i;
    int min;
    if( arr[0] > arr[1]){
        max=a[0];
        min=a[1];
    }

    for(i= 2 ; i < n ; i++){
        if(a[i] > max) max=arr[i];

        else if( a[i]< min) min=arr[i];
    }
    range= max-min; // range for counting sort
    if(range/n < log n) counting sort(A,range);

    else mergesort/heapsort(A......);

    return A;
    }

If (range/n) < logn , it means that range < nlogn, which implies it ""should"" be better than other optimal sorting algorithms.
It might be not the most accurate way but it seems like it should be something like that, shouldnt it?

I wouldn’t be too happy with your professor’s solution. You noticed that it will refuse to do a very fast counting sort if all item are either nk+1 or nk+2. That’s bad. What is fatal is that it will always do a counting sort if the array elements are all negative. (Please don’t tell me that a sorting algorithm which can only handle positive numbers would ever be considered).


Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was asked to check if it is possible to reduce the time from $O(n\log n)$ to $O(n)$ if using a determinstic Turing machine with two tapes (instead of one).

I am really stuck on it and don't know how to implement it. This is what I have so far:

First, we check that in the input word there are no zeros right of the ones. Then, for each zero in the input, we increase a binary counter and for the ones we do the same, creating a binary counter and increasing by one. if the counters are equal, accept, if not, reject. But i don't know how to implement it on a Turing machine, aside from the problem that if the counters of one and zero are far from the writing-reading head, then reaching it would take a lot of steps (time).

Regarding improving it to $O(n)$ time using a deterministic Turing machine with two heads: we go over with one head along the input string until we meet the first 1. then we count the number of one with one tape, and with the other the number of 0's. then we compare and accept if they are equal. So it is basically $k$ steps until the first 1, creating the counter, and counting each 1 $n$ times, then creating a counter with the second tape and comparing to the number of 0's in the beginning until the first one. So the total is $O(n)$. But how do I implement it on a Turing machine?

If you are allowed an auxiliary tape, then the algorithm is very simple:

Scan to the end of the input, while checking that the input belongs to $0^*1^*$.
Copy the input in reverse to the auxiliary tape, switching 0s and 1s.
Check that both tapes contain the same word.

If the input is $0^a 1^b$ then the second tape will contain $0^b 1^a$, so the algorithm will accept if and only if $a = b$. It clearly runs in linear time.

If you only have one tape, then the algorithm is more subtle. We scan the input from left-to-right, maintaining a counter just left of the current symbol being scanned. At each step, we do as follows:

Read the next symbol $\sigma$ and remember it.
Copy the counter one step to the right; this step takes $O(\log n)$ time.
Either increment the counter (if $\sigma = 0$) or decrement it (if $\sigma = 1$).

At the end, we accept if the input belongs to $0^*1^*$, and additionally the counter has the value zero.

Using crossing sequences, you should be able to show a matching $\Omega(n \log n)$ lower bound for one-tape Turing machines. The idea is to consider the set of inputs $0^m1^m,\ldots,0^{2m}1^{2m}$, and to consider the states that the Turing machine is when it crosses the window between the $m$th and $2m$th position. There must be $m+1$ different crossing sequences, hence there must exist a crossing sequence of length $\log m$, which corresponds to a running time of $\Omega(m\log m) = \Omega(n\log n)$.


Complexity of recursive algorithm I'm having hard time understanding time complexity of my solution for combination sum problem. The problem is as follows:

  Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

  The same repeated number may be chosen from candidates unlimited number of times.

Below is my solution written in Java using recursion:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> results = new ArrayList<>();
    recurse(results, candidates, target, 0, new ArrayList<>());
    return results;
}

private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        if (candidates[i] > target) {
            return;
        }
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

One can observe that the problem size of each recursive step is potentially not changed and the depth of the recursion is bound by target value e.g. if the candidates array contains number 1 the recursion will happen target times. If I simplify the code the interesting part is:

private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

Which feels like O(candidates.length * target) for the most pessimistic candidates input with number 1.

Since my solution is not really a divide and conquer algorithm I guess that I can't apply the master theorem. It feels like a  backtracking algorithm but I'm not familiar with finding upper bound for that type of algorithms.

Can someone please advise how to approach complexity analysis of above code?

The obvious algorithm tries all subsets, i.e., is $O(2^n)$ if you have $n$ elements to select. And your algorithm does that (try with first element, try without first element).

Complexity is given by the recurrence:

$$T(n) = 2 T(n - 1), T(0) \text{ given}$$

(try two posibilities for first one, recurse on the $n - 1$ others for each).


Min-cut in graph with demands/lower bounds This week I read something about network flow from Algorithm Design. But I am confused about some concepts.

We say, if a graph G contains some nodes with demands, positive or negative, how to define the min cut for these graphs? If we still use the definition for simple graph, the value of max flow is not equal to the capacity of min cut. Or is it totally meaningless to talk about min-cut in a network with demands on some nodes.

Another thing is  how to define the capacity of a min-cut for graph with lower bound on its edges. Still the sum of capacities of edges out of starting set? Or say, now we have a lower bound for this cut which is the sum of lower bounds of edges out of starting set.

Max flow and min cut are dual problems, in a technical sense: there are linear programming formulations of both, and these linear programs are dual to each other. This is explained in the Wikipedia article on the max-flow min-cut theorem.

Given a variant of the max flow problem, you can find the corresponding min cut problem by writing the linear programming formulation of the max flow problem, and dualizing it. I'll let you figure out what you get in your cases.


Can timestamp be used in synchronization of processes having Race Condition? I am wondering whether timestamp can be used to solve process synchronization problem, when race condition occurs? Below is an algorithm for entry as well as exit sections for every process who wants to enter in critical section. Entry section uses FCFS (First Come First Serve) technique to give access to critical section.

    interested[N] is shared array of N integers where N is number of processes.

    // This section executed when process enters critical section.
    entry_section (int processNumber) {
        interested [processNumber] = getCurrentTimeStamp ();  // Gets the current timestamp.
        index = findOldestProcessNumber (interested);         // Find the process number with least timestamp.
        while (index != processNumber);
    }

    // This section executed when process leaves critical section.
    exit_section (int processNumber) {
        interested [processNumber] = NULL;
    }

According to me, this algorithm satisfies all conditions for synchronization, i.e., Mutual Exclusion, Progress, Bounded waiting and Portability. So, Am I correct?

Thanks for giving your time.

The short answer is yes, since what you're essentially doing with the timestamps is making all potentially conflicting processes sequential. Of course, in sequential systems there are no race conditions (a bit of a simplification, but nevertheless). In what way does timestamping processes differ from creating locks on resources, which is the current standard in parallel computation? You may want to reflect on what the real issues with race conditions are. Maybe this definition from Wikipedia might help:

  "A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events."

So the primary issue to consider is what happens when you don't have control over the process(es) that cause(s) the race condition.


Nonuniform input distributions in average case analysis When we perform average case analysis of algorithms, we assume that the inputs to the algorithm are sampled uniformly from some  underlying space. For example, the average case analysis of quicksort  assumes that the unsorted array is uniformly sampled from the $n!$ permutations of $\{1,\ldots,n\}$.

Suppose instead that the inputs to an algorithm are chosen  non-uniformly over the input space.

Is the resulting analysis still "average case" analysis?

If the distribution causes the algorithm to perform at its worst (resp. best), is there a standard name for it? E.g. "adversarial (resp. favourable) distribution of inputs".

Yes, the expected running time under some other distribution would still count as an example of average-case analysis.  However, when you describe it to someone, make sure you explain what distribution you're using.  I wouldn't recommend that you just call it "average-case analysis" without also explaining that you're using a non-standard probability distribution.

The worst-case distribution is always a point distribution that assigns all its probability to a single input.  In  other words, the worst-case probability distribution that makes the expected running time as large as possible is in fact just a single input: the input that makes the algorithm run as long as possible.  Consequently, this kind of worst-case analysis coincides with the "standard" notion of worst-case running time.  For this reason, there is no need for a special "name" for this; worst-case running time already covers it.

The same is true for best-case running time and the probability distribution that makes the expected running time as small as possible.


Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable? Given a language $L$, I sometimes try to find a subset of $L' \subseteq L$ which I can prove is undecidable. I conclude that if a subset of $L$ is undecidable, then $L$ must be undecidable as well. Is this correct for arbitrary languages $L$ and $L' \subseteq L$?

What if someone said: $L'$ could be empty (we don't know due to the undecidability of $L'$), and we cannot conclude anything about $L$ from $L' = \varnothing$, therefore the proof is insufficient. Is this a valid point?

For example, in order to prove that the language
$$L = \left\{ w : M_w \text{ halts on a a finite set of inputs} \right\}$$
is undecidable ($M_w$ is a turing machine constructed from $w$), I use the fact that $L \text{ is undecidable} \iff L^c \text{ is undecidable}$. $L^c$ can be described as
$$L^c = \left\{ w : M_w \text{ halts on an infinite set of inputs} \right\}$$
and
$$L' = \left\{ w : M_w \text{ halts on all inputs } \Sigma^* \right\}$$
can be considered a subset of $L^c$. Using reduction, I can then prove that $L'$ is undecidable. If my assumption about subsets is correct, then $L^c$ must be undecidable as well, and therefore $L$ is undecidable.

(I know that the undecidability of the above language can be proven simpler, but I need an example for the use of subsets.)

No, your conclusion is not correct. The fact that $L'\subseteq L$ is undecidable do not imply anything about $L$. Indeed, consider $L=\Sigma^*$
for some finite alphabet $\Sigma$. Then, $L$ is decidable.

Now consider $L'\subset L$ such that $w\in L'$ iff $w$ is the description of a halting Turing machine written with characters from $\Sigma$. Then, $L'$ is, of course, undecidable.


Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo $n$.

I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $\left.\mathbb{Z}\middle/n\mathbb{Z}\right.$ and square it. If $r$ was a square, $r^2$ can have up to $4$ different square roots and the basic idea of the algorithm is that the oracle has some chance not to choose $\pm r$, but one of the other two roots. It will turn out that we then can determine a factor of $n$ using Euclidean's algorithm.

I formalized this to

Input: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.

Output: $p$ or $q$

Take a random number $r$ between $1$ and $n-1$
If $r\mid n$ then return $r$ (we were lucky)
$s:= r^2\pmod{n}$
$t:=\sqrt{s}\pmod{n}$ (using the oracle)
If $t\equiv \pm r\pmod{n}$ then goto step 1.
Return $\gcd(t-r,n)$

One can show that $t \not\equiv \pm r\pmod{n}$ implies that $\gcd(t-r,n)\neq 1,n$ and therefore get that the return value of the algorithm is a non-trivial factor of $n$.

Inspired by my main question "How do I prove that the running time is polynomial in the bit-size of the input?" I have some follow up questions:

Do I have to show that a lot of numbers between $1$ and $n-1$ are squares? There must be a well-known theorem or easy fact that shows this (well... not well-known to me ;-).
Are there any more details I have consider?
Has every square of a square exactly $4$ square roots modulo $n$?

Where in the analysis of the algorithm does the number of squares ("quadratic residues") come in? As to their number, you know that $a^2 \pmod{n}$ is always a square, and every number has up to $4$ square roots. That should help you show that there are a lot of squares.
Try to prove that your algorithm works, and see if anything is missing.
Suppose $n = pq$ ($p,q$ different primes) and $(x,n)=1$. Then if $x$ is a square, then $x$ has two square roots modulo $p$ and two square roots modulo $q$, and so four square roots in total by the Chinese remainder theorem. We know that a number $x$ such that $(x,p)=1$ has at most two square roots since the polynomial $t^2-x$ can have at most two roots modulo $p$. If it has one square root $y$ then $-y$ is another one.


Chernoff bound when we only have a lower bound of expecation This question: Chernoff bound when we only have upper bound of expectation  is similar, but for an upper bound of expectation.

The standard Chernoff bound says that is $X$ is a sum of 0/1 random variables, then, for any $\delta \in (0,1)$,

$P(X \leq (1-\delta) E(X)) \leq e^{-\frac{\delta^2 E(X)}{2}}$.

Suppose we only have $\alpha \leq E(X)$. Is it true, and if so, how to prove, that

for any $\delta \in (0,1)$,

$P(X \leq (1- \delta) \alpha) \leq e^{-\frac{\delta^2 \alpha}{2}}$.

You can use a coupling. Let $X = X_1,\ldots,X_n$, and suppose that $\Pr[X_i=1] = \beta_i$ (so $\beta := \mathbb{E}[X] = \sum_i \beta_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha_i = p\beta_i$. Let $Z_i \sim \mathrm{Bernoulli}(p)$, and define $Y_i = X_i Z_i$. Notice that $X_i \geq Y_i$ and that $\Pr[Y_i=1] = p\beta_i = \alpha_i$. If we define $Y := Y_1 + \cdots + Y_n$ then $X \geq Y$ and $\mathbb{E}[Y] = \sum_i \alpha_i = \alpha$, and so Chernoff's bound apply to $Y$, showing that $\Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}$. Since $Y \leq X$, we conclude that
$$
\Pr[X \leq (1-\delta)\alpha] \leq \Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}.
$$


Scott-continuous functions: an alternative definition I'm really struggling with this property:

Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup_{x\in D} x)=\bigcup_{x \in D}f(x)$, for all $D \subseteq Cl(X)$ such that $D$ is a directed set.
Directed set is defined thus: $D \subseteq $ POSET$ $ is a directed set iff $ \forall x, x' \in D$ $  \exists z \in D $ such $ x \subseteq z$ and $x' \subseteq z$.
$Cl(X) $stands for cliques of X: $\{x \subseteq |X| \mid a,b \in x \Rightarrow a$ coherent $b \}$.

Many books give that as a definition of Scott-continuous functions, but unluckly not my teacher. He gave us this definition of continuous:

$f : Cl(X) \rightarrow Cl(Y)$ is continuous iff it is monotone and $\forall x \in Cl(X), \forall b \in f(x), \exists x_0 \subseteq_{fin} x, b \in f(x_0)$,
where monotone is defined as:
$f$ is monotone iff $a \subseteq b \Rightarrow f(a) \subseteq f(b)$

This is the proposed proof I have, but I can't understand the last equation.
Proof of $f$ continuous implies $f(\bigcup D)=\bigcup f(D)$:
Let $b \in f(\bigcup D)$. By the definition of continuity, $\exists x_0 \subset_{fin} x \mid b \in f(x_0)$. Note that $x_0$ is the union of  $\{ x_i \mid x_i \in D\}$.
If $D$ is direct then: $\exists z \in D \mid x_i \subseteq z$ then $x_0 \subseteq z$. By the definition of monotony, $f(x_0)\subseteq f(z)$ so $b \in f(z)$ (???) $\subseteq \bigcup f(D)$. And  even that is true we should show that $\bigcup f(D) = f(\bigcup D)$, not just $\subseteq$.
The proof of the other implication is even worse so I can't write it here... Can you explain to me how the proof can work?

The definition of continuity used by your teacher is the nicer one.  It tells you pretty concretely what continuity means.

Suppose $b \in f(x)$.  That means that given all the information of $x$, possibly an infinite set of tokens (atoms), the function produces some element that has the atomic piece of information $b$.  (It could have other information too, but we are not concerned with that at the moment.)  Your teacher's definition says that it is not necessary to look at all the infinite information of $x$ in order to produce the output information $b$.  Some finite subset of $x$ is enough to produce it.

(Melvin Fitting's book "Computability theory, semantics and logic programming", Oxford, 1987, calls this property compactness and defines a continuous function as being monotone and compact.)

This is the essence of continuity.  To get some finite amount of information about the output of a function, you only need a finite amount of information about the input.  The output produced by the function for an infinite input is obtained by piecing together the information it produces for all finite approximations of the infinite input.  In other words, you don't get any magical jump in going from the finite approximations to their infinite union.  Whatever you get at infinity, you should already get at some finite stage.

The standard equation $f(\bigcup_{x \in D} x) = \bigcup_{x \in D} f(x)$ is pretty to look at, but it doesn't tell you all the intuition I have explained above.  However, mathematically, it is equivalent to your teacher's definition.

To show that $\bigcup_{x \in D} f(x) \subseteq f(\bigcup_{x \in D} x)$, it is enough to show that $f(x)$ is included in $f(\bigcup_{x \in D} x)$, for each $x \in D$.  But that follows directly from monotonicity of $f$ because $x \subseteq \bigcup_{x \in D} x$.  So, this is the "easy" direction.

The other direction, proved by your teacher, is the interesting one: $f(\bigcup_{x \in D} x) \subseteq \bigcup_{x \in D} f(x)$.  To see this, use the intuition I have mentioned above.   Any atomic piece of information $b$ in the left hand side comes from some finite approximation of the input: $x_0 \subseteq_{fin} \bigcup_{x \in D} x$.  That is, $b \in f(x_0)$.  Since $x_0$ is finite and it is included in the union of the directed set, there must be something in the directed set that is larger than $x_0$, perhaps $x_0$ itself.  Call that element $z$.  By monotonicity, $f(x_0) \subseteq f(z)$. So, $b \in f(z)$.  Since $z \in D$, $f(z) \subseteq \bigcup_{x \in D} f(x)$.  So, now $b$ is seen to be in the right hand side too.  QED.

As you have noted, showing that your teacher's continuity implies the pretty equation is the easy bit.  The harder bit is to show that the pretty equation, despite looking like it is not saying very much, really does say everything in your teacher's definition.


Rate Monotonic maximum execution time There are several periodic tasks (Period, Execution time),

e.g.:

A = (20, 9)
B = (12, 4)
C = (4, X)

What methods/tests can be used for finding the maximum execution time X for which the task set will be schedulable by Rate Monotonic.

First of all, this problem is (weakly) NP-hard, see this paper by Ekberg and Yi, because it generalizes the problem of deciding which task sets are schedulable by Rate Monotonic.

However, assuming that your periods and execution times are integers, you can find the answer in pseudopolynomial time. Simply try all values of $X$ from $0$ to $p$, where $p$ is the period of the task with variable execution time. For each of these values, simulate the Rate Monotonic algorithm until time $\max_{i=1}^n p_i$ (that is, the largest period in your task set), to check that the task set is schedulable. The largest value of $X$ for which your task set results schedulable in the simulation will give you the answer.

You might be able to do somewhat better if you have more information about your tasks. For example, if the variable task is the one with largest period (not true in your example), I think the following will work:

Simply simulate the Rate Monotonic algorithm time step by time step, as if $X$ was infinitely large, and doing the following in addition:

Initialize a counter $K$ to zero.
At every time unit in which Rate Monotonic tells you to run the lowest priority task, you increase the counter $K$ by one.
After $p_n$ time units (where $p_n$ is the period of your lowest-priority task), stop the simulation.

The value of $K$ at the end of the simulation will be the largest possible value of $X$.


Applications in Computer Sciences of Partition Functions A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$.

These were studied extensively in mathematics by MacMahon, Hardy, Littlewood and Ramanujan. Rademacher provided a way to approximating $p(n)$, improving on a formula by hardy and Littlewood. More recently, K. Ono and A. Wiles have come up with new interesting results.

Are there applications of partition functions in Computer Sciences, perhaps in the theory of elliptic curve cryptography or complexity?

there is a connection between partition functions and counting possible edge and vertex colorings in graphs, but its very abstract. see eg Graph parameters and invariants of the orthogonal group, Regts
there are applications of partition functions to simulating Ising models for Spin glasses in physics. spin glasses have been shown to have deep connections to NP complete phase transitions.


Ackerman hierarchy for higher order primitive recursion in System T Gödel defines in his System T primitive recursion over higher types. I found notes from Girard where he explains the implementation of System T on top of simply typed lambda calculus. On page 50 he mentions that once we use more types in the recursor we gain more expressive power with the system.

I don't understand how exactly this happens. Is it possible to come up with sort of Ackermann hierarchy with the higher order primitive recursion, i.e. a hierarchy of faster and faster growing functions where each function is expressible in System T but the diagonal is not? I guess so, but the construction does not seem evident to me and I would be interested seeing how one would construct it, or receive pointers to literature.

I'm after something concrete. I'm aware of the general diagonal argument that proves existence of a function not in T, but I would like to see how one would really "step up in the type hierarchy".

(This is a very partial answer, only addressing the first point, and not the main question about the hierarchy.)

I don't have a proof to point out to you, but the idea is that a single first-order recursor on naturals such as
$$
\begin{array}{l}
rec: (nat \to nat) \to nat \to nat \to nat
\\
rec\ f\; z\; n = f(f(\ldots f(z))) \qquad \mbox{($n$ times $f$)}
\end{array}
$$

would be much less powerful than having the full (primitive) recursion scheme

$$
rec_U: (U \to U) \to U \to nat \to U
$$

since the latter roughly resembles a polymorphic term in System F, which can be used at many types $U$.

Indeed, the basic $rec$ only gives us access to the first order primitive recursion scheme, as we can find in a computability / recursion theory book.
With only that, we know functions like Ackermann's are not definable. (Well, this is not that obvious since here we also have higher-order lambdas, it's only recursion which is constrained. But the point should stand anyway, I think.)

With the $rec_U$ scheme, instead, we can choose $U = nat \to nat$, which allows us to define Ackermann's function, as Girard shows in the book mentioned by the OP. Hence, the scheme is strictly more powerful.


Error in solution in Types and Programming Languages? I'm reading Types and Programming Languages and trying to understand the solution to exercise 5.2.4 on untyped lambda calculus / Church numerals:

  Define a term for raising one number to the power of another.

The proposed solution says:

  $\textrm{power2} = \lambda m. \lambda n. m~n$

In an attempt to understand how this solution works, I tried it on 01 as follows:

$$ \begin{array}{ll}
& \textrm{power2}~c_0~c_1 \\
\rightarrow & c_0~c_1 \\
= & (\lambda s.\lambda z.z)~c_1 \\
\rightarrow & \lambda z.z
\end{array}$$

The result doesn't look like a Church numeral to me. Is it an error in the solution, or have I misunderstood something?

If $power2~m~n$ stands for $m^n$, then it should be

$$power2=λm.λn.n~m$$

Let's try it on $0^1$:
$$
\begin{array}{ll}
& power2~c_0~c_1 \\
= & (λm.λn.n~m)~c_0~c_1 \\
\rightarrow & c_1~c_0 \\
= & (λs.λz.s~z)~c_0 \\
\rightarrow & λz.c_0~z \\
= & λz.(λs.λz.z)~z \\
\rightarrow & λs.λz.z \\
= & c_0
\end{array}
$$
Works fine.

Let's try it on $1^0$:
$$
\begin{array}{ll}
& power2~c_1~c_0 \\
= & (λm.λn.n~m)~c_1~c_0 \\
\rightarrow & c_0~c_1 \\
= & (λs.λz.z)~c_1 \\
\rightarrow & λz.z
\end{array}
$$

Wait, we should have got $c_1$.

Although syntactically $λz. z$ is different from it, but it has the same behavior as $c_1$.
In fact, you can use the function $equal$ (ex. 5.2.7) to prove it:
$$
equal = λm. λn.~and~(iszro~(m~prd~n))~~~(iszro~(n~prd~m))
$$

By the way, another form of the power function, given in the solution to this exercise have the arguments swapped:

$$power1 = λm. λn. m~(times~n)~c_1$$.


Best Algorithm for searching for an index in an array such that A[i] = i Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons.
The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome.
My algorithm works as follows :

Search(A , start , end)
  Find mid
  if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
    Search (A,start, mid-1)
  else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
    Search(A,mid+1,end)
  else if(A[mid] = mid)
    return A[mid];
  else
    return false;
end

Edit: edit contains my algorithm. Kindly forgive any typesetting errors

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit:
To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$.
The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits.
Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit)
This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

to answer your question in the comment to this answer:

this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?

while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms.
This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not sharp in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.


How to get enclosed spaces from a series of connected nodes I have a bunch of connected walls in a list and the data for them is like so:

Wall
{
   Node A;
   Node B;
}

Node
{
   float x;
   float y;
}

I want to find the rooms from the connected walls as an array of connected points to represent each room's perimeter.

This is an example visually of what i am trying to find:

The red dots are the nodes, and the lines are the walls, the numbers are the identified rooms that the walls created.

The walls can be at any angle, not sure if that matters though.

I am wondering what algorithms exist that can help me solve this problem, what is the best way to approach this?

One approach is to use a data structure for representing a planar graph.  Each node corresponds to a vertex in the graph, and each walls corresponds to an edge in the graph.  Then, you are looking for the set of faces in this graph.  Standard data structures for representing planar graphs should make it easy to retrieve the set of faces.

For instance, one standard data structure is the DCEL data structure.  It explicitly contains one record for each face, so once you have converted this to a DCEL data structure, then it is straightforward to iterate over all faces.  There are standard algorithms for constructing a DCEL data structure from the set of vertices and edges.  Or, instead of a DCEL, it looks like you could alternatively use a quad-edge data structure or a winged-edge data structure.  The keyword is to look for data structures for polygon meshes.  This has been studied in great detail in the computer graphics and computational geometry fields.

Alternatively, you could solve your problem directly.  For each node, find all of the walls associated with it, sort them by their angle, and store that sorted list associated the node.  After doing that for all nodes, then you can iterate through all rooms.    Pick an wall, then you can find the room to the "right" of that wall by simulating the left-hand rule: stand to the right of that wall, put your left hand on the wall, and walk forward, going in a circle around the perimeter of the room.  To simulate that rule, as you walk forward, you'll walk to the endpoint of the current wall; at that node $d$, to find the next wall you proceed to, look in the sorted list of walls incident on $d$, and find the next one in sorted order, then follow that wall.  It might be a bit trickier to work out the details of this, than to use an existing implementation of a DCEL data structure.


how one memory can be accessed simultaneously in instruction fetch and data read? In modern computer architecture, pipeline has stage that access memory for normal data and instruction in parallel.

But datas and instructions are usually in same memory, and their access address is different.

But how pipelined cpu can access them in parallel? Are the memory has   two address port for read data and instruction respectively?

If they are in separate memory, they can be accessed simultaneously. But what if there are only one memory for them? one of them is just stalled?

Modern CPUs usually feature separate instruction and data caches, so effectively, even if from a software PoV, everything is coming from a single memory space, there are physically separate busses and memories for instructions and data ("harvard", which is used for all reasonably fast CPUs nowadays).

There are also multi-port memories able to sustain several accesses simultanously. There is a great variety of architectures, for example DSPs or GPUs may have different memory organization than traditional CPUs.

In computers, with something like an x86 or an ARM, with an OS and applications, code memory is separate from data memory (there are attributes in MMU mappings), code is read-only. Except during on-the-fly dynamic compilation, or some library linkage, code is never modified through data accesses, there is no self-modifying code. It is nowadays far more efficient to have separate code and data memories for first level caches.

Many years ago, when one couldn't put billions of transistors on a die, there were shared or off-chip caches, and sometimes data accesses could effectively stall instruction fetches.


When is the output of shortest path $\subset$ MST? I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like:

The shortest path $B \rightarrow C$ is in no way contained in the MST. Are there known conditions on the graph and the edge weights that ensure that all vertex-to-vertex shortest paths are contained in the minimum spanning tree?

A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either endpoint of that edge, the shortest path tree contains the edge. So if we fix the source node for the SSSP tree, then it'll be difficult to say more than that the SSSP tree and the MST are equal for graphs that are trees themselves.

Raphael mentions in a comment that the same argument holds for weighted graphs with triangle inequality; to adapt the argument, we only need to consider the lightest edge on that cycle.

Generalizing in a different direction, whenever you have a weighted graph with weight function $w > 0$ that doesn't have a unique MST, then for every MST there is some node for which the MST is not a shortest path tree. The proof will assume that all edge weights are positive; I originally thought that since the set of MSTs is invariant under adding the same value to all edge weights, this would show the result for general graphs, but it doesn't since the set of shortest path trees is not invariant under that operation. Thus, the result will only be proven for graphs with positive weights. Regarding notation, $w > 0$ means that $w$ is positive everywhere.

Proof: Take two different MSTs $S = (V, E_S)$ and $T = (V, E_T)$ of some graph $G = (V,E)$. Consider a lightest edge that is in $S$ but not $T$, that is $ \{u,v\} = e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Take the unique $u-v-$path $p_{u,v}^T \subseteq E_T$ in $T$. We know $e \not \in p_{u,v}^T$. Note also that $|p_{u,v}^T| \geq 2$.

Any two MSTs have the same multiset of edge weights, see e.g. Raphael's proof here; due to this, the weight of the lightest edge in $E_S \setminus E_T$ is the same as that of the lightest edge in $E_T \setminus E_S$. Now take all edges on $p_{u,v}^T$ that are not in $S$, that is $\Delta = (p_{u,v}^T \setminus E_S) \subseteq (E_T \setminus E_S)$. We know that $\Delta \neq \emptyset$ since otherwise, $\{e\} \cup p_{u,v}^T$ would be a cycle in $S$. Any lightest edge in this difference, $e' \in \arg \min \{w(f): f \in \Delta\}$, satisfies $w(e) \leq w(e')$ due to the choice of $e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Since all edge weights are positive and $|p_{u,v}^T| \geq 2$, we know that $w(e) \leq w(e') < w(p_{u,v}^T)$. Thus, $T$ is not a shortest path tree for $u$. $\square$


Packing unsplittable flows problem For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ :

Let's define as flow a sequence of element of the same type represented in the following diagrams using the same colour. Every flow must be routed into the same output stream keeping the elements ordered as found on the input stream:

Another correct solution that is more balanced than the previous one:

Considering also that:

After a number of elements (called $timeout$) on the input stream without any element of the type of a specific flow, that flow should be considered ended and the element found should be the starting point of a new flow

I have some questions:

Do you know any paper covering this kind of problems?
What is a good algorithm that maximise the throughput, in other words keeping the output stream balanced?

Update

Thanks to @D.W. for the comments, here some clarifications:

I am looking for an "online algorithm" where a "reasonable" latency is allowed therefore a lookahead-buffer/moving-window is definitely allowed
I am not looking for theoretical guarantees, I am looking for an approximate algorithm to try against few hundreds test cases made of [millions..billion] elements with a mix of few elephant flows and many mice ones.
The stream balance I am looking for should be considered over a period of time and not in an "absolute sense". In other words an algorithm that fills the first stream only then the second and then the third is as balanced as an algorithm that fill only the first stream

The obvious algorithm is the greedy algorithm.  Each time you see a new element that's not part of an existing flow, you identify which output stream currently has lowest occupancy, and route that element to that output stream.  When you see an element that is part of an existing flow, you obviously have no freedom about where to route it; it has to go to the same output stream as the rest of the flow.

In an online setting where you must decide immediately where to route each element and where you have no information about the distribution of flow sizes or other domain knowledge, this is the natural strategy.  When you see the first element of a flow, you have no information about how large the flow will be, and you must decide immediately where to route it based only upon the current state of the output streams.  It's not clear whether there is any theoretical sense in which one can provably do better, if we have zero knowledge.

Now in practice I suspect you will typically have some a priori knowledge about the distribution of flow sizes.  In this case, you can do bit better.

For instance, suppose you knew that all flows were either mice (they have 1 element) or elephants (they have 1000 elements).  Then it would be easy to do better.  When you get a new element that's not part of an existing flow, look at the existing flows in the output streams.  For each existing flow in an output stream that has more than 1 element, you know exactly how many more elements are yet to be received in that flow, so you get a lower bound on how full that output stream will become once all of the remaining packets in the existing flows arrive (it is a lower bound since for the flows where you've only seen one packet you don't know yet whether they are mice or elephants).  Call this the degree to which that output stream is "committed".  Now you can use these lower bounds to pick which output stream is least committed, and route the new element to that output stream.

If you additionally know what fraction of flows are mice and what fraction are mice, instead of computing a lower bound you can compute an expected value and choose which output stream to route to by going for the choice where the expected value of the imbalance is minimized.

In general, you can use a greedy algorithm that uses expected output stream commitment as the basis for choosing an output stream.  Let the random variable $X$ be distributed according to the distribution on flow sizes, i.e., $X$ is a random variable that counts the number of elements in a randomly chosen flow.  Suppose you have seen $k$ elements in a particular flow, so far.  Then the conditional expectation $\mathbb{E}(X | X\ge k)$ is in some sense your "best guess" at what the total flow size will be; it is the expected flow size, given that the flow contains at least $k$ elements.  Thus, you can compute this for each active flow, and compute the sum of these values for each output stream, and route the new flow to the least-committed output stream.  If you know the distribution of $X$, you should be able to compute $\mathbb{E}(X | X\ge k)$ easily.

This algorithm is fairly simple and should be pretty efficient: it requires $O(1)$ state per active flow (a counter to keep track of the number of elements seen in that flow so far).  Assuming you can compute the conditional expectation in $O(1)$ time, the algorithm requires $O(1)$ time per element.

Whether this algorithm is sufficiently better than the simple greedy (choose the lightest output stream, based only upon its current size, not its expected commitment) in practice can only be answered by experimenting on some realistic data sets.


How can I prove that a build max heap's amortized cost is $O(n)$? Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair.  We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.


Can a DFA just have one state that is both the initial state and the final state? so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}.

can i not just have one state (initial and final state) that loops a,b to itself?

thanks

A DFA is defined as a tuple $\langle \Sigma,Q,\delta,q_0,F \rangle$, with $\Sigma$ a finite alphabet, $Q$ a set of states, $\delta$ a transition function, $q_0$ an initial state, and $F\subseteq Q$ a set of accepting states.

Take $Q=F=\{q_0\}$ with $\delta(q_0,\sigma)=q_0$ for every $\sigma$. This DFA accepts every string, since it's run is always of the form $q_0,q_0,q_0,...,q_0$, and $q_0\in F$.


IA network that is path-consistent, but not consistent I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be used to determine consistency for IA (Interval Algebra), since it is just a necessary but not sufficient condition. From this i would say that it must exist a IA Network which is path consistent, but not consistent. However i cannot construct such a network.
Is my assumption wrong? If not what would be an example of a IA network which is path consistent but not consistent?

Yes, you are correct.

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

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

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

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


What is the natural language of computers mathematics or logic? I was reading about the history of computers where i came by machine code

  A Machine code or machine language is a set of instructions executed directly by a computer's central processing unit (CPU). Each instruction performs a very specific task, such as a load, a jump, or an ALU operation on a unit of data in a CPU register or memory.

The computer here does logical operations like load or jump steps using the machine code.

From the Wikipedia page a computer is

  A general-purpose device that can be programmed to carry out a set of arithmetic or logical operations automatically.

This means from the machine code the computer can perform logical or arithmetic operations, but which principle computers are based on  the logical principle or the mathematical principle ?

What can be said also as the natural language of a computer ?

====

[Edit] both answers solved my problem.

====

There is really no such thing as a natural language for computers. Natural language is a concept from linguistics, and pertains mostly to humans (and perhaps also to some animals).

The corresponding concept for computers is machine language or native code, which is what the computing core of the computer (the CPU) runs. Machine codes consists of various instructions, some of which perform arithmetic and logical operations. Others are in charge of control flow, of memory access, and so on.

Related to machine language is assembly code, which is a readable representation of machine code. While machine code consists of bytes, assembly code consists of textual symbols. (Assembly code also usually contains some features which make it a barebones programming language.)


How many permutations in a trainset? If I have the following pieces to a train set:

(12) Curve
(4) Straight

Such as this train set.

I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. It's not as simple as just creating a list , such as the following, where s=straight and c=curve, and creating all permutations, since the pieces are reversible:

sssscccccccccccc

For example, a Curve piece can either curve left or curve right. I thought about doubling the number of curve pieces and calling them 'cr' and 'cl' and then doing permutations on a list such as:

ssssclclclclclclclclclclclclcrcrcrcrcrcrcrcr

However, I think that is introducing more problems, so I'm thinking of creating a tree structure as such:

Each level of tree represents adding a new piece, where cl=Curve Left, s = Straight, cr = Curve Right.

I would then traverse each path in tree structure and determine if it forms a 'solution'. A solution would be defined as starting point = ending point, however, that is a different problem/algorithm as it requires knowing the lengths and arcs of the pieces. The algorithm would need to account for solutions that consist of all pieces (16 in this case), 15, 14 ... down to 8 (as that would be the smallest number to make a circle from the trainset in the picture). To solve those solutions, I would just create paths to all the nodes at a given level. Does this seem reasonable or other thoughts?

I bought that set for my grand son (nice and cheap Ikea product, kids love it from 18 month to 80 years, though not rcommended before 3 years of age), so I am very experienced with the
problem.

For the uninitiated, the tracks are oriented because they connect with a hole on one end and a hooking tongue on the other end. So curved tracks have to be placed with one side or the other up, depending on which way you want to turn. The Ikea picture does not make it obvious: the little plastic pieces are actually glued as tongue on one end of a track, but the curves track have grooves for the wheels on both sides.

Counting the configurations

I will use the word configuration for a way of putting the track
elements together. It seems more appropriate than the word
"permutation" which has a precise technical meaning.

The first analysis, described in this section, consist in evaluating
the total number of possible configurations. This will help us to
actually enumerate them in the next part.

You have 16 track elements, including 4 straight and 12 curved.

If you consider your 16 elements in succession, you have $\binom {16} 4
=\frac{16!}{4!\times 12!} $ ways of choosing a combination of
positions for the 4 straights tracks, among 16.

Now, if you consider the curved tracks, they can be placed either as
left curve or as right curve. For 12 tracks that makes $2^{12}$
possibilities (using train tracks to implement binary numbers makes
for heavy duty computers).

So the total number of "permutations" (that use of the word does not
seem too appropriate) is the product of the two numbers, since they
correspond to independent choices, i.e.,
 $$\frac{2^{12}\times 16!}{4!\times 12!} $$

But this answer may not be quite correct: if you have a closed circuit, you can consider it to start with any of the track elements, so that it counts for 16 "permutations", though one might consider it should count for 1. Hence, it might be appropriate to substract 15 from the result for each closed circuit that can be constructed. Geometric analysis of the shape of track elements shows that there are several closed circuits that can be constructed. Note that, except for the eight shape with crossing
tracks, circuits are oriented, and each shape must me counted twice.

Other closed circuits are possible with with less track elements, in particular with exactly 8 curves, and 0, 2, or 4 straight. But we now ignore the issue of closed curves.

If you consider $n$ elements, $8\leq n\leq 16$, of which $m$ are straight, with $0\leq m\leq 4$, the number of circuits is
$$\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Thus, for all possible values of $m$, with a number $n$ of elements, including at most 12 curved, the total number of circuits is:
$$\sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Finally, considering all possible values of $n$ in $[8,16]$, we get the
number of circuits:
$$\sum_{n=8}^{n=16} \sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Then there is the small number of cases when the circuit is closed, which one can analyse to count all their starting element variants as the same circuit.
Note that when the track does not cross itself, each closed shape comes in two variants: clockwise and counter-clockwise. But should I go in so many details.

Enumerating the configurations

The analysis used for counting configurationscan be repeated
identically to enumerate them.

We consider $n$ track elements, of which $m$ are straight and $p$ are
curved: $n=m+p$. We want to enumerate all the circuits that use all
these elements.

First, we want to place the $m$ straight track in the sequence of $n$
track element position. For this you must enumerate all combinations
of $m$ integers among the first $n$ integers. Algorithms already
exists to enumerate these conbinations, available in wikipedia, or
fromn other sources, so there is no point in developing that further
here.

Then, for each such combination, you simply try all possible
combinations of left or right positionning of curved track elements,
which you can do by enumerating all possible sequences of$0$ and $1$,
hence simply using a counter to enumerate in binary all integers from
$0$ to $2^p-1$. It is advisable to use the fast changing bits in the
enumeration on the end side of the configuration, in order to factor
the beginning of computations that might be used to check whether the
configurations give a closed circuit.

Of course, this can be repeated for other values of $m$ and $p$. But
configurations for smaller values are just prefixes of the
configurations for the maximum values of $n$ and $m$. So, doing it only for the maximum values should be enough to observe on the fly whatever we are interested in regarding smaller configurations. THis is detailed regarding closed circuits in the next section.

Checking a configuration

Given a configuration for a sequence of track elements, and starting
from porition (0,0), and direction angle 0, one can compute the
position and direction at the end of the first track element, then
propagate to the end of the second, and so on till the last. The
circuit is closed if the end of the last track element is in position
(0,0) with direction angle 0.

The shape of the track elements is determined by the fact that 8
curves make a full circle, and 12 cuves and 4 straight make an eight
shaped curve. One can use the radius of the circle as distance unit,
Then the staight track elements have a length of 1 radius.

For simplification, one can also take$45^o$ as the angle unit, so that
each curved track changes the orientation by plus (left) or minus
(right) one unit, and 8 units make a full circle. Hence orientation can be represented byrf an integer modulo 8.

Positions of track elements ends should not be computed as real
numbers, but as expression using integers and $\sqrt 2/2$, of the form $a+b\sqrt 2/2$, a bit like
complex numbers where $i$ is replaced by $\sqrt 2/2$. That makes the computations much cheaper, based on integer arithmetics on pairs $(a,b)$, and the
$\sqrt 2/2$ ultimately cancel each other for closed circuits.

Actually, to explain it formally, plane coordinates reachable from the
origin with straight and curved track elements are all expressible as
$a+b\sqrt 2/2$. Hence, since 2 coordinates are used on the plane, and
since $1$ is incommensurable with $\sqrt 2$, plane coordinates can be
seen as a 4-dimensional vector space over the field $\mathbb Q$ of
rationals, or better, since we use only integer coordinates in that
vector space, as a 4-dimensional module over the ring $\mathbb Z$ of
integer. See this mathematics question which is a followup to the question answered here.
Hence following track element by track element the configuration of a
circuit, for the purpose of checking whether it is closed, can be done
using only integer addition and substraction.

A circuit starts at the origin with orientation $0$. The circuit is
closed when it ends also at the origin with orientation $0$. In the
four dimensional space, the coordinates of the origine are $(0,0,0,0)$

I guess any reader can further develop the computation details, for
each type of track element. (this answer is already very long).

As explained in the previous section, doing the enumeration for maximum values of $n$ and $m$ will include smaller configurations as prefixes. In particular,
if you are looking for closed circuits of all sizes, the simplest is
to compute all configurations with the maximum values of $n$ and $m$,
and check closure not just at the end, but at every step of the
computation of track elements positions. However, there is a
possibility for some optimization in performing these checks, as no closed circuit can be found
with less than eight curved track elements.


What happens when there are two same IP addresses? IPv4 addresses run out few years ago. But everywhere I can see mine or someone elses IP address it's in IPv4, not IPv6. I understand that world switched to IPv6? So why we can see address in older format? Does that mean somewhere someone can have same address as I? How can that work?

ISPs asign one IPv4 address to a customer, and your "WiFi box" acts as a router/NAT box/ DHCP server doling out addresses from a private range internally. It is possible that the "outside" IPv4 address is itself in a private range, leaving your ISP through a mere handful  of IPv4 addresses via NAT (real one, your box really does PAT, port forwarding through one IPv4 address).


rebalance red-black tree with many violations Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...).

I have a situation where I graft several sub-trees from one red-black tree onto another. After these grafts I would like to consider re-balancing the resulting tree.

Are there any approaches to doing this, either applying existing techniques in a brute force manner, or strategies that would make it efficient. It isn't entirely clear that existing algorithms can be naively applied.

In general, I would say that the algorithm you want is a tree union (also called a merge), which takes two trees and combines them so that the new tree contains the union of the keys of both inputs. You can read a brief description on Wikipedia, or a more in-depth description (which generalizes to other balancing schemes such as AVL, BB[α], Treap) in a recent paper.

However, it seems that your use-case is slightly more specific than a tree union. In particular, I'm guessing that the subtrees you are grafting onto the existing tree don't violate the ordering property of the BST. In this case the algorithm you want is even simpler than a tree union, and is much closer to a simple insertion:

// graft B onto T
function graft(T, B):
  let (L, R) = split T at B.root.key
  return join(L, join(B, R))

This algorithm is inspired by the union algorithm but does not need to recurse, because of the nice properties of the input. It uses two functions which I've summarized below; you can find them described in more detail in the links I provided above.

split cuts a tree at a specific key k, producing two trees L and R where all keys in L are less than k, and all keys in R are greater than k.
join takes two trees (L, R) where all keys in L are smaller than all keys in R and combines them into a single tree.

Both split and join have logarithmic time complexity. Because of this, graft only takes logarithmic time. If you have a small number of branches to graft, then simply iteratively applying graft should be fastest. However if you have a large number of branches to graft, it may be faster to first combine them into a single tree and then merge this tree with the original.


Dependent types vs refinement types Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of dependent types which distinguishes them?

If it helps, I came across Refined types via the Liquid Haskell project, and dependent types via Coq and Agda. That said, I'm looking for an explanation of how the theories differ.

The main differences are along two dimensions -- in the underlying theory,
and in how they can be used. Lets just focus on the latter.

As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments
so that verification (and inference) is completely automatic, meaning one does not require "proof terms" of the sort needed in the full dependent setting. This leads to significant automation. For example, compare insertion sort in LH:

http://ucsd-progsys.github.io/lh-workshop/04-case-study-insertsort.html#/ordered-lists

vs. in Idris

https://github.com/davidfstr/idris-insertion-sort/blob/master/InsertionSort.idr

However, the automation comes at a price. One cannot use arbitrary functions as specifications as one can in the fully dependent world,
which restricts the class of properties one can write.

Thus, one goal of refinement systems is to extend the class of what
can be specified, while that of fully dependent systems is to automate
what can be proved. Perhaps there is a happy meeting ground where we can
get the best of both worlds!


How do you know if a language accepted by a DFA is $Σ^*$? I know that a language that is input into a DFA (call it $X$) is regular just by being accepted by it, but given that it is accepted, how can one figure out that $L = Σ^*$? In other words, what does a DFA that accepts anything from $Σ^*$ even look like? When I learnt about DFAs, it was always under the context that $L(X)⊆ Σ^*$.

I get that this must be a DFA that accepts any input from $Σ^*$, but I have trouble wrapping my head around it. This is all of course assuming that $Σ$ is any finite set.

You don't input a language to a DFA. Each time you run the machine, the input is just a string. The language accepted by the DFA is the set of inputs that cause it to end in an accepting state (called a final state by some authors). Therefore, the automaton accepts $\Sigma^*$ if every possible input leads to an accepting state.

So, to decide if an automaton accepts $\Sigma^*$, you need to check if every input does indeed lead to an accepting state.