Finding the spots furthest away from bad data The real-world problem I'm trying to solve is to create an algorithm which finds the ideal channels where I can transmit radio traffic, inside a radio frequency band that could contain various disturbances. These n ideal channels are those who are furthest away from any of the disturbances, but also the furthest away from each other. Where n is a constant picked by me, depending on how many channels the radio can support.

In abstract terms, I have a chunk of generic data where each item could either be labelled "good" or "bad". It can be considered to be an array of booleans, or illustrated as a series of 1=good and 0=bad, for example 0010111100.

In this data, consecutive sequences of good data form good segments:

0010111100   data size=10
  ^ ^
  | +------- good segment 2, size 4
  +--------- good segment 1, size 1

In the best case, there only exists one good segment covering all of the data:

1111111111   data size=10, 1 good segment with size 10

No matter the nature of the data, I need to find the n "best places" that are furthest away from any bad data, but also from each other. It is considered equally bad to be near a "bad" item as it is to be near another "best place".

The ideal solution is where the minimum distance between all "best places" and bad data/other best places is as long as possible, for all best places.

For example, in the case of 1111111111 where n=3 places, they could be located as follows (simply divide the data size by 3):

1111111111   data size=10, n=3
  ^  ^  ^

Or in case of 0110111110 n=3, the following would be fine:

0110111110   data size=10, n=3
 ^   ^ ^

or

0110111110   data size=10, n=3
  ^  ^ ^

In case there is too much bad data, the problem has no solution. The sum of all good segment sizes must be at least n or there exists no solution.
Example:

0000010001   data size=10, n=3, no solution possible.

I suppose one solution is to find the n best segments out of all the good segments - then simply find the n best places at the center of those segments.

But one problem then is that there aren't necessarily n good segments. In that case, the best places have to be divided across what good segments there are.

Are there any similar existing algorithms that could be used or modified to suit the above scenario?

I'm also wondering if there is a particular data structure that would beneficial to use in this case, other than a raw array? A heap binary tree consisting of good segments?

I am going to assume you want to maximize the "separation".  In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.

Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m = $ the data size.  I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.

To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan.  Select the left-most place you can.  Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place).  Keep iterating.  When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.

Now you can use binary search from here.  If the number of places that could be selected was less than $n$, decrease $s$ and try again.  If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again.  There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate.  If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.


string concatenation vs language concatenation What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure why.

C is a regular expression over $\Sigma\{a,b\}$. We can design a finite automaton that can accept the language which can be generated from C. On the other hand, the language D is not regular. Using pumping lemma for regular language it can be proved that D is not regular. Hope this will help you. If you need more explanation then please feel free to ask.


Is the set of minimal DFA decidable? Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for every other DFA $B$ with less states than $A$, $L(A)\ne L(B)$ holds. I'm trying to figure out how come that $\mathrm{MIN}_{\mathrm{DFA}} \in R$? How come it is decidable?

What is about this kind of DFAs that is easy to decide?

Given two DFAs $A,B$, it is decidable (even efficient!) whether $L(A) = L(B)$: use the product construction to get a DFA for $L(A) \triangle L(B)$, and now use reachability analysis.

In order to determine whether $A$ is a minimal DFA, one can just try all DFAs $B$ with less states, looking for one satisfying $L(A) = L(B)$. Alternatively, there are algorithms for minimizing DFAs which are vastly more efficient than that approach. They are even more efficient if all you want to know is whether the DFA is minimal or not.


Read regular Expression from NFA Good evening everyone!
Can someone help me with the following task?
So we have this NFA:

I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$
Unfortunately I don't understand how this is possible. If I look at the NFA, then we can accept a word that only includes one a without any b's. But the regular expression in the solution does not make that possible.  Or am I missing something?
I also converted the NFA to a DFA however that didn't help much.
Thanks!

The direct edge (a) from initial state 1 to final state 3 is not included in the RE.


Finding all paths with lengths in a fixed interval in sparse graphs What is the most efficient way to find all paths of length M to N in a large sparse graph?

Some general information:

Graph has 30,000 to 50,000 nodes
Average number of edges per node ~ 10
M=4, N=7
Graph has cycles

Assuming a directed graph.

Paths of length $1$ are simply the edges.

paths of length $i+1$:

Unite on all nodes $v \in V$ {concatenate all paths of length $i$ that end with $v$ with all paths of length $1$ that start with $v$}.

repeat for $i=1$ to $7$.

Note that this method avoids redundancies, so you don't need to check for them.


If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$ I'm trying to work out a proof by construction that $L/a$ would be regular.

$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be changed is the set of accepted states ($F$)

I came up with the following definition of $F'$ for the new

$F' = \{q ∈ Q | \delta(q, a) ∈ F\}$

Where $Q$ is the set of states (the same for both machines), and $\delta$ is the transition function (also the same for both machines).
I believe this would make any state that has a transition to an accepting state in the first machine an accepting state in the second machine (including prior accepting states, if they have a self-loop).

Am I missing anything here? It seems suspicious to me that I would only need to modify the set of accepting states and not any other component.

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

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

We can then define an operation named chop such that:

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

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

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

Therefore the regularity is closed under the chop operation.

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

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

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

Hope this helps!

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

Edit: capitalisation of first word.


Dual problem of a maximization primal problem $P$? Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$.

The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a primal minimization problem.

Then what is the dual problem of $P$ ?

Is it implicit, that the dual problem of $P$ is the dual problem of $P$ stated as the minimization problem $\min -c^T x$ ?

Surely these two primal problems are equivalent in the sense that their optimal solution $ \bar x$ are equal (if it exist). However, the objective values are the same only if we ignore the sign !

As you mention, maximization and minimization problems are equivalent. Given a recipe for dualizing a minimization problem, you can convert it into a recipe for dualizing a maximization problem as follows:

Negate the objective function and change the maximum to a minimum.
Compute the dual.
Negate the objective function and change the maximum to a minimum.

The new dual problem will have the same objective value as the primal one (under some mild conditions). This property easily follows from the same fact for duals of minimization problems.

If you're careful enough, you should also get that dualizing twice brings you back to the original program.


Polymorphism and Inductive datatypes I'm curious. I've been working on this datatype in OCaml:

type 'a exptree =
  | Epsilon
  | Delta of 'a exptree * 'a exptree
  | Omicron of 'a
  | Iota of 'a exptree exptree

Which can be manipulated using explicitly typed recursive functions (a feature that has been added quite recently). Example:

let rec map : 'a 'b. ('a -> 'b) -> 'a exptree -> 'b exptree =
  fun f ->
    begin function
    | Epsilon -> Epsilon
    | Delta (t1, t2) -> Delta (map f t1, map f t2)
    | Omicron t -> Omicron (f t)
    | Iota tt -> Iota (map (map f) tt)
    end

But I've never been able to define it in Coq:

Inductive exptree a :=
  | epsilon : exptree a
  | delta : exptree a -> exptree a -> exptree a
  | omicron : a -> exptree a
  | iota : exptree (exptree a) -> exptree a
.

Coq is whining. It doesn't like the last constructor, and says something I don't completely understand or agree with:

Error: Non strictly positive occurrence of "exptree" in "exptree (exptree a) -> exptree a".

What I can understand is that inductive types using a negation inside their definition like type 'a term = Constructor ('a term -> …) are rejected, because they would lead to ugly non well-founded beasts like (untyped) λ-terms.
However this particular exptree datatype seems innocuous enough: looking at its OCaml definition, its argument 'a is never used in negative positions.

It seems that Coq is overcautious here.
So is there really a problem with this particular inductive datatype?
Or could Coq be slightly more permissive here?

Also, what about other proof assistants, are they able to cope with such an inductive definition (in a natural way)?

This has come up on the Coq mailing list several times, but I never saw a conclusive answer. Coq isn't as general as it could be; the rules in (Coquand, 1990) and (Giménez, 1998) (and his PhD thesis) are more general and do not require strict positivity. Positivity enough is not enough, however, when you go outside Set; this example came up in several discussions:

Inductive Big : Type := B : ((B -> Prop) -> Prop) -> Big.

With plain data structures such as yours, the inductive type would not cause problems other than making the implementation more complex.

There is a general way to define types such as this defined as the fixpoint of a polynomial:
$$F = \epsilon + \delta\, (F \times F) + \omicron\, \mathrm{id} + F \circ F$$

Instead of attempting to define the function $\mathrm{exptree} : a \mapsto \mathrm{exptree}(a)$, define the family of types $\mathrm{exptree}, \mathrm{exptree} \circ \mathrm{exptree}, \mathrm{exptree} \circ \mathrm{exptree} \circ \mathrm{exptree}, \ldots$. This means adding an integer parameter to the type that encodes the number of self-compositions ($\mathrm{exptree}^0(a) = a$, $\mathrm{exptree}^1(a) = \mathrm{exptree}(a)$, $\mathrm{exptree}^2(a) = \mathrm{exptree}(\mathrm{exptree}(a))$, etc), and a supplementary injection constructor to turn $a$ into $\mathrm{exptree}^0(a) = a$.

Inductive et : nat -> Type -> Type :=
  | alpha : forall a, a -> et 0 a                      (*injection*)
  | omicron : forall n a, et n a -> et (S n) a         (**)
  | epsilon : forall (S n) a, et (S n) a
  | delta : forall n a, et (S n) a -> et (S n) a -> et (S n) a
  | iota : forall n a, et (S (S n)) a -> et (S n) a
.

You can proceed to define values and work on them. Coq will often be able to infer the exponent. Set Implicit Arguments would make these definitions prettier.

Definition exptree := et 1.
Definition et1 : exptree nat :=
  delta _ _ (omicron _ _ (alpha _ 42)) (epsilon _ _).
Definition et2 : exptree nat := iota _ _ (omicron _ _ et1).

You may prefer to decrease the argument by 1, so that exptree is et 0. This removes a lot of S n in the definition, which may make some proofs easier, but it requires splitting the initial case from the recurrence case in every constructor that takes an $a$ in an argument (instead of adding a single injection constructor for $a$). In this example, there's only a single constructor to split, so this should be a good choice.

Inductive et : nat -> Type -> Type :=
  | omicron_0 : forall a, a -> et 0 a
  | omicron_S : forall n a, et n a -> et (S n) a
  | epsilon : forall n a, et n a
  | delta : forall n a, et n a -> et n a -> et n a
  | iota : forall n a, et (S n) a -> et n a
.
Definition exptree := et 0.
Definition et1 : exptree nat :=
  delta _ _ (omicron_0 _ 42) (epsilon _ _).
Definition et2 : exptree nat :=
  (iota _ _ (omicron_S _ _ et1)).

I think this is the same principle proposed in a more general form by Ralph Mattes.

References

Thierry Coquand and
Christine Paulin. Inductively defined types. In Proceedings of COLOG'88, LNCS 417, 1990. [Springer] [Google]

Eduardo Giménez. Structural Recursive Definitions in Type Theory. In ICALP'98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 1998. [PDF]


$O(n^2)$ running time vs $O(n^2)$ worst case The use of the phrase "worst-case running time" is really confusing to me.
Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of the algorithm is sub-quadratic?
If it is then why do we say that $O(n^2)$ is the worst case time?
Or do they have different meanings?
Thank you.

Suppose that you have an arbitrary array of $n$ numbers, and you give it to  Quicksort to sort.
The expected running time of the algorithm is $O(n \log n)$.  However, if the array is sorted, but in the wrong direction, and you pick the first element as pivot, then the algorithm might actually run in time $O(n^2)$.
That means that if you look at how Quicksort behaves with increasingly larger arrays of reversely sorted data, the time it uses grows as $n^2$.
However, if you spend $O(n)$ time to shuffle the array before sorting it, the expected running time is $O(n \log n)$; i.e. very few time will the algorithm spend close to $O(n^2)$ many operations.

A different example is with respect to amortized complexity.  For example, adding a single element to an ArrayList in Java takes $O(1)$ time, most of the time.  However, on a rare occasion, Java needs to create a new array and copy all the elements over to this new one.  That takes $O(n)$ time.
This means that the worst case complexity for ArrayList.add is $O(n)$, but if you do this operation $n$ times, the total complexity is also $O(n)$, so we say that the amortized complexity is $O(1)$.


Can't understand this division algorithm in Computer Architecture So, I'm preparing for an exam where I have solve divisions using this division algorithm:

While I understand the theory (image above), I couldn't understand this example below:

My problem is with the "First Step", apparently you place the dividend in the "Remainder" box but I don't undetrsand how did they come up with the divisor (10 000), where did this number come from?

The divisor is the 2 put into the upper 4 bits of the 8 bit divisor register.


Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?

Hint. Consider a word a length $\geqslant k$ accepted by $M$ and a successful path for this word. Now prove that this path goes at least twice through the same state, thus producing a loop.


Question about H-gate on entangled qubits I have a question about the Hadamard Gate on entangled qubits. I’m very newb to quantum computing and does not have any professional knowledge in physics nor mathematics. However I’ve tried some different algorithms in IBM’s quantum experience and think I got the idea about how the qubits works in the block sphere. Because of my poor knowledge in physics I need a simple explanation and I want to understand it...

My problem:

When I do the following operation:

q[0]: H   ( + )   H
q[1]:          *

H = Hadamard Gate
( + ) = CNOT control
* = target

I get the following results when I measure q[0] and q[1] after 1000 shots:

1/4 times: 11
1/4 times: 01
1/4 times: 10
1/4 times: 00

What I don’t get is why the first qubit is measured as as a 1 (only) 1/2 times and as a 0 1/2 of the times. My theory before the measurement was that q[0] would always be measured as a 1 all the times since I put it in superposition <+| and then put it back (after the second H gate and the CNOT) to be measured along the X-axis. So what have I missed?

Assuming that the initial quantum state is $\left| 00 \right\rangle$, the effect of the circuit is
$$
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix} \cdot
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} =
\begin{bmatrix} 1/2\\1/2\\1/2\\-1/2 \end{bmatrix},
$$
where the rows and columns are indexed by $\left|q_0q_1\right\rangle = \left|00\right\rangle,\left|01\right\rangle,\left|10\right\rangle,\left|11\right\rangle$. When you measure the two qubits at the end, you should get each of the four possibilities with probability $(\pm 1/2)^2 = 1/4$, which is exactly what you have observed.

If, however, you apply the CNOT gate with input roles reversed, you get
$$
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix} \cdot
\frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & -1 & 0 \\
0 & 1 & 0 & -1
\end{bmatrix} \cdot
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} =
\begin{bmatrix} 1\\0\\0\\0 \end{bmatrix},
$$
so in this case you will always measure $\left|00\right\rangle$.


Big-O Notation of Anagram solution algorithm In Solution 1: Checking Off of Problem Solving with Algorithms and Data Structures, just beneath the ActiveCode: 1 extract (included at the bottom of this post for reference), it is stated:

  each of the n characters in s1 will cause an iteration through up to n
  characters in the list from s2.

...which to paraphrase (less succinctly), means "each character in s1 could result in all characters in s2 being inspected".

The following sentence states:

  Each of the n positions in the list will be visited once to match a
  character from s1.

Firstly I'm unsure which list is being referred, I think it means the variable alist, i.e. s2. Is this correct?

  The number of visits then becomes the sum of the integers from 1 to n.

Secondly (and the real point of this post), if each item in the list (variable alist) is inspected for each character in s1, then why is this not simply O(n) = n^2 as per "nested loops"?  If n=5, then then sum(n) = 15, where as n^2 = 25.

I'm fine with simplifying the equation for summing 1 to n integers to get n^2, but I'm confused about how sum(5) = 15, whereas O(n) = n^2.

ActiveCode: 1 Checking Off (active5)

def anagramSolution1(s1,s2):
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcba')

Edit to add

Having written this out it struck me that perhaps dropping the (1/2) and (1/2)n from the formula to sum(n) is the reason for the difference of actually summing n, as opposed to just doing n^2.

To be absolutely clear, I understand the formula for summing n is n^2 when dropping the non-dominant terms. What I don't understand is why we're summing n and not immediately and directly stating it is actually n^2 as a result of the nested loop and this sentence:

  each of the n characters in s1 will cause an iteration through up to n
  characters in the list from s2.

Let's be concrete. Suppose s1 = 'abcd' and s2 = 'dcba'.

For the a in s1, it will take 4 iterations to find the a in s2.
For the b in s1, it will take 3 iterations to find the b in s2.
For the c in s1, it will take 2 iterations to find the c in s2.
For the d in s1, it will take 1 iteration to find the d in s2.

So in this case, it does take sum(i) for i = 1,...,n iterations.

Now some quiet meditation should convince you than if s2 is an anagram of s1, it will again take exactly the same number of iterations; the summands will just appear in a different order. (After all, whatever is the first character in s2 will only require 1 iteration to be found, the second character requires 2 iterations, etc.)

If s2 is not an anagram of s1, then the algorithm will short-circuit when the first character not in s2 is tested. So then the algorithm will take less than O(n^2) time. But in the worst case, the algorithm takes O(n^2) time.


Prove finding a near clique is NP-complete An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if there exists $S \subseteq V$ where $|S| = k$ and $u,v \in S$ where $(u,v) \not\in E$, and $S$ forms a clique in $(V,E \cup \{(u,v)\})$. How can I show finding a near clique of size $k$ in $G$ is NP-complete?

I think the following reduction works (unless I missed something):

Given $G=(V,E)$ and $k$, output $G'$ which is obtained from $G$ by adding $2$ new vertices $\{x,y\}$. that are each connected to all the vertices in $V$ (but not to each other). Finally, the output is to search for a $k+2$ near clique.

Clearly this is polynomial (linear).

If there exists a $k+2$ near clique in $G'$, then if $k+1$ of its vertices are contained in $V$, then $G$ has a $k$-clique.
If less than $k+1$ vertices are from $V$, then at least $k$ of them are, since $x$ and $y$ are not connected between them. But then, the $k$ remaining vertices in $G$ must form a clique.

Conversely, if $G$ has a $k$-clique, then just add the two new vertices $x,y$ to get a $k+2$-near clique.


Importance of space constructability in time space relation in complexity I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem.

Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $S$ is not space constructible?

My other question is about Remark 4.3, the book claims that if $S$ is space constructible then you can make an $NSPACE(S(n))$ machine halt on every sequence of non-deterministic choices by keeping a counter till $2^{O(S(n))}$. I am not sure how we can keep such a counter in $S(n)$ space. The space constructability of $S$ implies that we can compute $S(n)$ in $O(S(n))$ space, not $2^{O(S(n))}$ in $O(S(n))$ space.

To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably some of these inclusions do hold regardless of space-constructibility.

Regarding the second question, suppose that you computed $S(n)$ (in binary), and are interested to compute $2^{CS(n)}$. First, multiply $S(n)$ by $C$; this uses $O(\log S(n))$ space. Second, count $CS(n)$ spaces, fill them with zeroes, and add a one to the left. You have computed the binary representation of $2^{CS(n)}$, using additional $S(n)+1$ space.


Type Theory and Principia Mathematica Part IV "Relation Arithmetic" As

type theory is a principle focus of modern computer science,
its origins are in Bertrand Russel's theory of types,
Principia Mathematica is both the origin of and is expressed in the theory of types, and
relational databases are among the highest value, most researched applications of computer science

it seems Russell's "Relation Arithmetic"* (developed in Principia Mathematica Part IV "Relation Arithmetic") would be an active field of study in modern computer science.

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments:

  "I think relation-arithmetic important, not only as an interesting
  generalization, but because it supplies a symbolic technique required
  for dealing with structure. It has seemed to me that those who are not
  familiar with mathematical logic find great difficulty in
  understanding what is meant by 'structure', and, owing to this
  difficulty, are apt to go astray in attempting to understand the
  empirical world[emphasis JAB]. For this reason, if for no other, I am sorry that the
  theory of relation-arithmetic has been largely unnoticed."

Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use?  If so, why?

*A good, informal, introduction to relation-arithmetic is in Introduction to Mathematical Philosophy, by Bertrand Russell.  One must first understand Russell's abstract definition of "number", drawn from Frege (Chapter II "DEFINITION OF NUMBER").  Then one can proceed to Chapter VI "SIMILARITY OF RELATIONS" where he defines relation-arithmetic.

Briefly, there are no "sets" in the sense we think of "set theory" -- there are only "relations" which may be "similar" to one another.  All relations that are "similar" to one another comprise a "relation number".  Similarity between two relations, P and Q, obtains if there is a one-to-one correspondence between the relata of P and the relata of Q such that if a relationship holds in P, the relationship also holds in Q between its corresponding relata.  One can even think of ordinary numbers as relation numbers if one restricts the relations to one place relations (monadic/unary/property/etc.).  I emphasize this because although Russell uses the word "class similarity" rather than "relation similarity" in Chapter II, it is apparent that he considers "class" to be a degenerate case of "relation" when one carefully reads Chapter IV.  Because of this, and the fact that type theory is considered an alternate foundation for mathematics used in computer science, it may be incorrect to dismiss relation-arithmetic as a degenerate case of category theory or some other more complex mathematical structure in which it may be encoded or modeled.  Such modeling or encoding should be the other way around.

"Relation numbers", thus defined, are then defined to have the ordinary arithmetic operators, addition, multiplication and even exponentiation.

relational databases are among the highest value, most researched applications of computer science

James, what do relational databases have to do with the question? And why have you tagged this q with 'relational-algebra'? It seems to me entirely gratuitous.

Just because databases are 'relational' does not mean they have much to do with whatever Russell meant by 'relation-arithmetic'.

Relational database theory sticks to simple set theory and FOPL. Precisely because it wants to avoid getting into higher-order complications (and type theory).

Similarly just because historically Russell's theory of types kicked off an area of research, does not mean that everything these days to do with type theory must therefore derive from Russell, or that his later musings would necessarily help.

  Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use? If so, why?

I'd say yes, entirely unnoticed.

Again what relevance does the "critical role computers play" have wrt Russell?

On looking at a few of the standard early works in programming language type theory, I see no citations of Russell: Landin 1965 on the semantics for ALGOL; Strachey 1967; Reynolds 1983.

The Reynolds paper has the word "relations" in the abstract. And cites a paper Morris 1973 'Types are not Sets'. And mentions [Dana] "Scott's discovery of how to construct sufficiently rich universes without encountering Russell's paradox".

Modern type theory derives mostly from typing models for Lambda Calculus; of which Russell had no inkling. That could be why.

BTW your opening link to the answer on type theory, which mentions "Russell's paradox occasionally shows up" then points to some results in Haskell I think is again drawing a very long bow. Also those results back in 2010 are for some early developments of then-new type-level features. I'd classify them as bugs. They rely essentially on Impredicativity about which the compiler's user guide says "GHC has extremely flaky support for impredicative polymorphism, ..."; indeed I think the feature is to be blocked as a 'very hard problem to get right'.


Sum rule for Big-O with equal complexity-functions? One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined complexity is $f_1 + f_2 = O(\max(g_1, g_2))$.
But what do we pick if both complexity-functions are equal? E.g., if $f_1(n)$ is the sorting of an array and $_f2(m)$ as well, then the complexities are $O(n\log(n))$ and $O(m\log(m))$. Applying the rule would be $O(\max(n\log(n), m\log(m)))$. I think that picking any of those would yield a valid but very unintuitive estimation as you would drop one variable. Besides that, it's not clear which one to pick.
Is it the case that you are not supposed to use the rule when there are multiple variables involved?

It depends on if some variables on dependent on another, or if they are given as parameters in the problem. For example, in many graph-related problems, $n$ can be the number of vertices, and $m$ can be the number of edges. In this case, $m$ can be as large as $O(n^2)$. So in the general case, say if we have an algorithm whose first phase runs in $O(n)$ and second phase runs in $O(m)$, we just add the two terms together and do not attempt to simplify --- the final runtime is $O(n+m)$.
In terms of several variables given as parameters that aren't necessarily related: eaving multiple variables inside the final equation is standard, e.g. I can say that multiplying an $m\times n$ matrix and an $n\times p$ matrix takes $O(mnp)$-time using schoolbook multiplication, or solving the knapsack problem takes $O(nt)$-time where $n$ is the number of items and $t$ is the target sum.
In special cases like planar graphs and other sparse graphs, we know that $m=O(n)$, so we can safely substitute $n$ in place of $m$ in the final running time for simplification.
As a digression, this illustrates why on sparse graphs (where $m=O(n)$) one would prefer to use Dijktra's in a loop for all-pairs shortest path (in contrast to a transitive-closure based algorithm like Floyd-Warshall); since now Dijkstra runs in $O(m \log n) = O(n \log n)$, the overall complexity for using Dijkstra's in a loop becomes $O(n^2 \log n)$, which is better than Floyd-Warshall. By contrast, note that Dijkstra's runs in $m \log n$ for the general case, which means on dense graphs where $m=O(n^2)$, it becomes less efficient than Floyd-Warshall in terms of worst-case running time.
In other cases, there can be variables aren't even polynomially bounded by a given parameter --- take the knapsack example above, where $t$ can be exponential in $n$.


Is there a name for "yield first result parallel map"? Context

In randomized algorithms two schemes of computation are common:

Las Vegas algorithms with random running time
Randomized algorithms that have a probability of success, and have to be executed multiple times before getting the answer

You can also transform the latter in the former with a loop but they really don't have the same properties (like an optimal restart sequence for Las Vegas algorithms), so I want to distinguish the two.
It is also possible to have randomized algorithms that can fail AND that take a random amount of time.

Parallelization with map

When parallelizing, it is common to use a map primitive: just execute those algorithms in parallel.

However, while waiting the answers from each of the nodes at each "batch", one loses tremendous amounts of time, for example if one instance of the algorithm takes much more time than the others: most processes will be idle. Of course, it is possible to group batches to avoid this situation, but then one will have to wait for the end of the batch which will take more time.

"Yield first result parallel map"

The good solution would to be able to return the result in the parent node immediately when one node finds it, hence the name "yield first result parallel map". Then there should be a way to either stop directly the children (I don't know any clean way) or be able to use the free nodes while the busy ones finish their now useless computation. Maybe one should also be able to get those calculations back in a queue if they have a result.

Another way to express it would be "getting the results of a parallel map in an asynchronous queue".

Is this concept known? Does it have another name? Is it implemented somewhere (I implemented it in MPI but was wondering whether there are other implementations)?

You might be able to achieve this in a system for distributed promises / distributed futures.

Some systems will have an operation any that does what you want: if p1,p2,..,pn are promises, then any(p1,p2,..,pn) returns a new promise q that resolves as soon as any of the promises p1,..,pn do.  In other words, once the first promise resolves, q immediately resolves (with that value), without waiting for any of the other promises to resolve.  See, e.g., promise.any in Javascript Q, Promise.any in Bluebird or Promise.any? in Concurrent Ruby.

That said, this is only half the story.  When one promise resolves, what happens to the other promises?  Do they keep executing or get terminated?  The answer will probably depend on the specific system.  If you're unlucky, all the other computations keep running, eventually the other promises resolve, and then their result is just thrown away.  That'd be a waste.

However, if you're lucky -- if the system supports it, and the underlying scheduler is smart enough -- then perhaps the scheduler will terminate the computations associated with the other promises as soon as it is known that they are not needed.  How could that be implemented?  One way is that the implementation of any might cancel all of the other promises as soon as one of them resolves.  The system could be designed to propagate cancellation transitively, and the scheduler could be implemented to terminate any in-progress computation that exists solely to resolve a promise that has subsequently been cancelled.

Ultimately, it's likely to be system-dependent whether the other computations are terminated or not in this situation, and you might need to test individual systems to determine whether they do what you want.


terminology for grouping words in a string? We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g.

Hello World! This is May from the dairy farm.

Strings with sub-groups of two:

Hello World!
World! This
This is
is May
...

You are probably looking for the term n-grams, with $n = 2$ in your case. This is very useful in natural language processing and speech recognition.


Converting sets into regular expressions In my book:

The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba.
The set {01, 10} to regular expression 01 + 10

Does the +'s here represent concatenation or union?

We don't quite convert a set to a regular expression. Rather, we give a regular expression for a language (i.e., a regular expression which defines the same language). For example, a regular expression for the language $\{01,10\}$ is $01+10$, and a regular expression for the language $\{abb,a,b,bba\}$ is $a+b+abb+bba$. There can be other regular expressions. For example, another regular expression for the second language is $a(\epsilon+bb) + b(\epsilon+ba)$.

Regarding the syntax of regular expressions, this should be explained in your book.


Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user? The types of problems I am trying to solve are as follows:
Given a set of co-ordinates such as: (1,2), (3,3), (6,2), (7,1), a value of k such as k=3 and an initial set of centroids such as c1=(2,2) and c2=(5,4), perform the k-means/median algorithm.
Now, with samples that small, I can easily work it out on paper. However, if I have 200 co-ordinates to start with and 10 centroids, it starts to get a lot more tricky.
I have already found this calculator: https://scistatcalc.blogspot.com/2014/01/k-means-clustering-calculator.html and several others which serve a similar function. I have also found python code doing similar operations. However, all these tools initialize centroids randomly or using k-means++. I, on the other hand, want to initialize the centroids manually.
Is there an online/offline tool/code/platform that can achieve this?

I think this should be possible using the scikit-learn implementation; see here: https://stackoverflow.com/questions/38355153/initial-centroids-for-scikit-learn-kmeans-clustering.


Strongly connected and completely specified Moore equivalent of a Mealy Machine Problem: Prove that if a Mealy machine is strongly connected and completely specified, the corresponding Moore machine will also be strongly connected and completely specified.

My approach so far:

As the Mealy Machine is completely specified, we have 2 cases for each state:

All transitions coming into this state have the same output.
At least 2 transitions coming into this state have different outputs.

For case 1:
The equivalent for this state would simply be changing the notation, i.e. mark all transitions into this state simply by the input symbols and just mention the output with the state as is.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

For case 2: The equivalent for such a state requires the 'splitting'/addition of new states such that each 'split' state corresponds to the different outputs that can be generated. We split a state into a 2 corresponding states.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

Strongly Connected Machine: If for any two states $S_i, S_j$ of the machine, there exists a finite sequence of input characters that can make the machine transition from $S_i$ to $S_j$, the machine is strongly connected.

Completely Specified Machine: Consider $M = (I,O,S,F,Z)$

$I:$ Input Symbols
$O:$ Output Symbols
$S:$ Set of States
$F:$ Transition function $F: S\times I \rightarrow S$
$Z:$ Output function
$Z: S \rightarrow O $ (Moore)
$Z:$ $S\times I \rightarrow O$ (Mealy)

Now, if for every $(p,x)$ such that $(p \in S, x \in I)$ there exist some $q \in S$ and $y \in O$ such that $F(p,x) = q$ and $Z(p,x) = y$ (Mealy), $Z(p) = y$ (Moore)

My Question:

I'm having a hard time trying to formally prove the above while I can see it is true with the above intuition. I can similarly say that if the mealy machine was strongly connected, even after replacing it with 1(or 2) states, it would most definitely still be strongly connected. I was looking for help on formalising this above approach or a more solid proof on this.

Let $M_1 = \langle Q, \Sigma, \Delta, \delta, \lambda, q_0 \rangle $ be a Mealy machine where $\Delta$ is the output alphabet and $\lambda$ is the output function.

Let us denote states of the corresponding Moore machine by $q_{ib}$ if there is input $a$ and output $b$ such that $\delta(q_j, a) = (q_i, b)$. This means if the Mealy machine enters a state $q$ by emitting more than two different outputs then the state $q_i$ "splits". Also, denote corresponding Moore machine's transition function by $\delta'$.

Now consider two states $q_{ib_1}$ and $q_{jb_2}$ (of corresponding Moore machine). Existence of the state $q_{jb_2}$ implies that there is a state $q_k$ and input symbol $a$ such that $\delta(q_k, a) = (q_j, b_2)$. Since we made assumption that the Mealy machine is strongly connected, there is a string $w$ such that $\delta(q_i, w) = (q_k, b_k)$ for some output symbol $b_k$. So, we have
$$\delta'(q_{ib_1}, wa) = \delta'(\delta'(q_{ib_1}, w),a) = \delta'(q_{kb_k}, a) = q_{jb_2}$$
This shows that the corresponding Moore machine is also strongly connected.

As for the completely specification, let $q_{ib_1}$ be a state of the Moore machine, and $a$ is an input symbol. Then $\delta'(q_{ib_1}, a)= (q_{jb_2}, b_2)$, where $\delta(q_i, a) = (q_j, b_2)$, which shows it is completely specified.


Best and worse case inputs for heap sort and quick sort? So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?

Heap sort:
best case - nlogn
worst case - nlogn

Quick sort:
best case - nlogn
worst case - n^2

Where I get confused on these two is:

heap- Since the best and worst case are the same does it not matter
the input order? The number of comparisons and assignments will
always be the same? I imagine in a heap sort it may be the same since
the real work is done in the insertion, but the sorting only uses the
removal of the max/min heap? Is that why?
quick sort- This one I don't know for sure. I'm not sure what the
best case and worst case situations are for this. If its a already
sorted list of 10 strings for example wouldn't we always have to
choose the same amount of pivots to get complete the recursive
algorithm? Any help on this explanation would really help.

heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?

The number of comparisons made actually can depend on the order in which the values are given. The fact that the best and worst case are each Θ(n log n) - assuming all elements are distinct - only means that asymptotically there's no difference between the two, though they can differ by a constant factor. I don't have any simple examples of this off the top of my head, but I believe that you can construct inputs where the number of comparisons differs by a constant factor between the two approaches. Since big-O notation ignores constants, though, this isn't reflected in the best-case and worst-case analysis.

  quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.

The number of pivots chosen is indeed the same regardless of the execution of the algorithm. However, the work done per pivot can vary based on what sort of splits you get. In the best case, the pivot chosen at each step ends up being the median element of the array. When this happens, there are (roughly) n comparisons done at the top layer of the recursion, then (roughly) n at the next layer because there are two subarrays of size n / 2, then there are (roughly) n at the next layer because there are four subarrays of size n / 4, etc. Since there are Θ(log n) layers and each layer does Θ(n) work, the total work done is Θ(n log n). On the other hand, consider choosing the absolute minimum of each array as a pivot. Then (roughly) n compares are done at the top layer, then (roughly) n - 1 in the next layer, then (roughly) n - 2 in the next, etc. The sum 1 + 2 + 3 + ... + n is Θ(n2), hence the worst case.

Hope this helps!


Constructing hitting sets for randomized algorithms Suppose A($\cdot$,$\cdot$) is an efficient randomized algorithm and L is a language such that

$\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$ and if $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$.

Let $H$ be a hitting set such that for all inputs $x$ of length $n$, if $x \notin L$, then $\exists y \in H, A(x, y) = 0$.

We need to show that there exists a hitting set $H$ of size $O(n)$.

My idea is that from the condition $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$, we can get that $x \notin L, \text{Pr}_r[A(x, r) = 1] < \frac{1}{2}$. Then we can randomly choose $y_1$, $y_2$, ..., $y_m$ to construct a set $S$. Then for any input $x \notin L, \Pi_{i = 1}^{i = m}Pr[A(x, y_i) = 1] < 2^{-m}$. Therefore, the probability that there exists at least one $y_i$ such that $A(x, y_i) = 0$ is $1 - 2^{-m}$. Now the problem is if we need to prove the hitting set $H$ must exist, then $1 - 2^{-m}$ should be 1, which means $m$ should be large enough. However, I cannot find the relationship between $m$ and $n$ and how come if $m$ in size of $O(n)$ would prove such $y_i$ must exist.

Or maybe I am going in the wrong way. Can somebody help me with this?
Any help would be appreciated.
Thanks in advance.

Suppose that $H$ consists of $m$ seeds chosen uniformly at random (thus $|H|$ could be smaller than $m$). For each $x \notin L$, the probability that $A(x,r) = 1$ for all $r \in H$ is at most $2^{-m}$. Since there are at most $2^n$ inputs of length $n$ not in $L$, we get that the probability that $H$ is not a hitting set is at most $2^n/2^m$. Choosing $m = n+1$, we see that the probability that $H$ is not a hitting set is at most $1/2$, and in particular there must exist a hitting set of size at most $n+1$. If $L \cap \Sigma^n \neq \emptyset$, we can improve this to $m = n$.


Reduce Vertex Cover with size k to Vertex Cover with size n/2 Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:

$k = n/2$: This case is trivial.
$k > n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
$k < n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.


Exact Analysis of the Merge Sort When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is:

$T(n) = 2T(n/2) + \Theta(n)$

But how I can formally prove that even if I consider any input, the complexity stays the same? While looking in the answers to the exercise 4.3-5 of the book Introduction to Algorithms on this site, he mention the recurrence for the odd sized input is as follow:

$T(n) = T((n-1)/2) + T((n+1)/2) + \Theta(n)$

And justifies that:

  However, shifting the argument in $n.log(n)$ by a half will only change the value of the function by at most $\frac{1}{2}\frac{d}{dn}(n.log(n)) = \tfrac{log(n)}{2} + 1$, but this is $o(n)$ and so will be absorbed into the $\Theta(n)$ term.

But I did not understand his justification very well. Somebody could explain to me?

(Exercise 4.3-5: Show that $\Theta(n.log(n))$ is the solution to the "exact" recurrence for merge sort.)

Let us consider the recurrence
$$
T(n) =
\begin{cases}
1 & \text{if } n = 1, \\
T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n & \text{if } n \geq 2.
\end{cases}
$$
Using OEIS (A033156), we find that the exact solution to this recurrence is
$$
T(n) = n(\lfloor \log_2 n \rfloor + 3) - 2^{\lfloor \log_2 n \rfloor + 1}.
$$
Curiously, OEIS presents a different recurrence relation with the same solution:
$$
T(n) =
\begin{cases}
1 & \text{if } n = 1, \\
T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 & \text{if } n \geq 2.
\end{cases}
$$
The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.


Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous? Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?
According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars generating them.
Every regular language is also DCFL, hence they will follow the same, but I doubt if every grammar corresponding to a DFA is non-ambiguous and that of NFA is ambiguous.

Let us consider the following construction of a regular grammar from an NFA. We will have a non-terminal $S_q$ for each state $q$. The starting symbol is $S_{q_0}$. If there is a transition from $q$ to $q'$ upon reading $\sigma$ (possibly $\sigma = \epsilon$), then we add the transition $S_q \to \sigma S_{q'}$. If $q$ is an accepting state, we add the transition $S_q \to \epsilon$. Whether the result is a regular grammar or not depends on your definition of a regular grammar (and on whether you allow $\epsilon$ transitions), but let's ignore this aspect.

You can check that this grammar is unambiguous if and only if, each word $w$ accepted by the NFA has a unique accepting path in the NFA, where an accepting path is something that looks this way:
$$
q_0 \xrightarrow{\sigma_0} q_1 \xrightarrow{\epsilon} q_2 \to \cdots \to q_f,
$$
where $q_f$ is an accepting state, and the symbols on top of the arrows spell $w$. Such an NFA is known as a UFA (U stands for Unique).

Every DFA is a UFA since every word has a unique path through the DFA (or, depending on your exact definition, at most one path). Some NFAs are UFAs, others are not.


How does consistency imply that a heuristic is also admissible? A heuristic function $h (n)$ is...

Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal.
Admissible if $h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

To proof the statement in your question, let us proof that consistency implies admissibility whereas the opposite is not necessarily true. This would make consistency a stronger condition than the latter.

Consistency implies admissibility:

Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is admissible (where $t$ is a goal) since edge costs are assumed to be non-negative and thus, the optimal cost from one node to itself is necessarily 0. This certainly holds in case the heuristic function is admissible but we want to proof that consistency necessarily implies admissibility. For this, let us assume further that $h(t)=0$ for any goal ---and this fact will be used in the base case below.

The proof proceeds by induction:

Base case: take any predecessor of the goal node $t$. Let $n$ denote it, so that $t$ is a successor of $n$. If the heuristic function is consistent, then $h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$ and hence, $h$ behaves admissibly in this case.

Note that the base case does not assume that the edge $\langle n, t\rangle$ is necessarily the optimal solution from $n$ to $t$ and, indeed, there might be a different path from $n$ to $t$ with a lower cost. The importance of the base case, is that $h(n)\leq c(n,t)$ for all ancestors of node $t$! This result will be reused in the induction step.

Induction step: consider a node $n$. The optimal cost to reach the goal $t$ from $n$, $h^*(n)$, is computed as: $\min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\}$, where $\mathrm{SCS}(n)$ is the set of successors of node $n$. As consistency is assumed by hypothesis, then $h(n)\leq c(n,n')+h(n')$. Furthermore, as $h(n')\leq h^*(n')$ is assumed by the induction step then $h(n)\leq c(n,n')+h^*(n')$  and this is true for all successors $n'$ of node $n$. In other words: $h(n)\leq \min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\} = h^*(n)$, so that $h(n)\leq h^*(n)$.

Admissibility does not necessarily imply consistency:

For this, a simple example suffices. Consider a graph which consists of a single path with 10 nodes: $\langle n_0, n_1, n_2, ..., n_9\rangle$, where the goal is $n_9$. Let us assume wlog that all edge costs are equal to 1. Obviously $h^*(n_0)=9$, and let us make $h(n_0)=8$, $h(n_i)=1, 1\leq i<9$ and $h(n_9)=0$. Clearly, the heuristic function is addmissible:

$h(t)=0$
$h(n_i)=1\leq h^*(n_i)=(9-i)$, $\forall i, 1\leq i<9$.
Finally, $h(n_0)=8\leq h^*(n_0)=9$.

However, $h(n)$ is not consistent and $h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$.

Hope this helps,


Shortest past including an edge from a given set I am working on the following problem.

There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find the minimum number of broken roads taken. If no good road is taken, display −1.

I am trying to use Dijkstra shortest path algorithm for this. I have assigned weight 0 to the good roads and 1 to broken roads. Then I find the shortest path taken. According to me, this shortest path should be equal to the minimum number of broken roads taken. For considering the case where all the roads are broken, I check if the total weight of path is equal to the number of roads taken, then display −1. But I understand, this algorithm will not work always.

What would be the right approach for this problem?

Create two copies of your graph. The first copy represents not having taken a good road, and the second copy represents having taken a good road. You transfer between the copies by taking a good road. The weighting scheme you describe will result in minimizing the number of broken roads. Details left to you.


Proving regular languages are closed under a form of interleaving I've got the following definitions:

$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\,(L_1,L_2)\ \  = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$
when both $L_1$ and $L_2$ are languages.

I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Thanks in advance.

Hint. Because $L_1$ and $L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and $M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA $M$. For each character it receives, $M$ can decide to act either like $M_1$ or like $M_2$.


Identity productions in regular grammar If a grammar is of the following form (i.e. all its productions are), is its language regular?

$B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$
$B → aC$ - where $B$ and $C$ are in $N$ and $a$ is in $Σ$
$B → ε$ - where $B$ is in $N$ and $ε$ denotes the empty string, i.e. the string of length 0.
$B → A$ - where $A$ and $B$ are non-terminals in $N$

(1. - 3. quoted from wikipedia)

I only added the 4th rule and I assume that the language is regular. However, I cannot find any reference that supports this intuition.

Yes the language is regular.

Productions 2 and 3 are like transitions in a finite state automaton: $B \to aC$ is like moving from state $B$ to state $C$ while reading $a$; $B\to \varepsilon$ indicates that $B$ is like a final state where we can stop the computation (i.e., end the dirivation in grammar terminology).

The production $A\to B$ is like an $\varepsilon$-transition in finite state automata. This may be practical, but does not change the language generating capabilities of the grammars.


minimum number of nodes that traverse all the graph In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover problem nor dominating-set problem since we don't need to select node 3. We say that, if we select node 0, we can go to node 1 from there and if we select node 2, we can go to node 3 and then node 4 from there.

Also, the number of nodes can be up to 10^5 and the algorithm's runtime must be 1 second or less. Any suggestion would be useful.

Try combining Tarjan's strongly connected components algorithm with a topological sort.


Procedure for finding if Overflow occurs on addition I have two 4-bit 2's complement numbers a,b, and their sum in s (Also a 4-bit 2's complement number). Using only the basic logical operations, I need to write a procedure to find if an overflow occurs. If there is an overflow, the output needs to be 1000 otherwise it is 0000.

The inputs in this procedure are a, b, s, and output is 1000 or 0000 depending on the inputs. I am allowed to use AND, OR and NOT operators

I know that there is an overflow if a and b have the same most significant bit and c has a different most significant bit but can't seem to figure out what the expression should be except that whatever the result is, needs to be ANDed with 1000 for the final result. How do I solve this?

I found the solution and have answered it here

The final answer is

(((NOT a) AND (NOT b) AND s) OR (a AND b AND (NOT s))) AND 1000


Tarjan's SCC : example showing necessity of lowlink definition and calculation rule? Several questions (1, 2) have been asked about this topic already but I am trying to be more specific.

In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is already on the stack is

    // It says w.index not w.lowlink; that is deliberate and from the original paper
    v.lowlink  := min(v.lowlink, w.index)

I understand that this rule is necessary to compute lowlink accordingly to its formal definition, which in Tarjan's paper is (emphasis is mine)

  LOWLINK(v) is the smallest vertex which is in the same component as v and is reachable by traversing zero or more tree arcs followed by at most one [back edge] or [cross edge].

What I do not understand is :

Would removing the emphasized restriction in the definition lead to a calculation with v.lowlink  := min(v.lowlink, w.lowlink) ?
Would removing the emphasized restriction lead to incorrect detection of a graph's SCCs (if so, I am looking for an example of such a graph) ? If not, would this modification guarantee that in a given SCC, all nodes ultimately have the same lowlink value (again, if not, I am looking for a counterexample) ?

I am currently at the following point (which might be wrong !) :

Let v and w be as in the code (exploring v's successors, w already on stack). v is on the stack too, and so is r, the root of v and w's SCC (in Tarjan's sense) (it is a common ancestor of v and w in the spanning tree).

For the proposed modification of the algorithm to yield a bad result, one needs to have w.lowlink < r.lowlink (this is the case where, by propagating the lowlink information back to r after finishing DFS, we will get an inconsistent value for r). For this to happen, w must have gotten its lowlink value from a vertex x discovered before r and belonging to a different SCC than r. But x needs to be in the stack when we were DFSing from w (if it were not the case, one would not have updated w.lowlink when reaching x because x is already discovered at that time). Since x is discovered before r, it is deeper in the stack than r, and thus it is still in the stack when we are DFSing from v. But then wouldn't all these nodes belong to the same SCC, rooted by x.lowlink ?

For a given vertex, the only thing that matters in the algorithm is if there is an edge from the vertex or a child-vertex to a ancestor-vertex in the DFS exploration tree. In this case, we know that the vertex belongs to the same SCC as it's parent. In such a case, we are sure that the vertex itself or a child-vertex has a direct back edge to an ancestor of the vertex, and this ancestor has a lower index that the current vertex, so the v.lowlink will differ from v.index. We actually do not need to know the top-vertex of the SCC at this step.

So, using v.lowlink  := min(v.lowlink, w.lowlink) instead of v.lowlink  := min(v.lowlink, w.index) will lead to a correct algorithm too.
The difference is that in this case, v.lowlink will not represent the vertex with the smallest id reachable from v  nor the SCC top vertex, but just v if there is no such vertices, or any parent vertex that belongs to the same SCC (maybe the top-vertex), depending of DFS order. I think it's just lack in formal definition, and thus, wasn't used.

Let's see what appends when we use this alternative instruction. When we update v.lowlink because we have found a new back edge to a ancestor vertex, we will now set v.lowlink with the value of w.lowlink. But this vertex is an ancestor and is still in the stack: we may not have already explored all the child vertices of this ancestor and thus, w.lowlink can change in the future: this is why we dont's know exactly what will be the final value of v.lowlink because it depends of the DFS order. We can juste be sur that it will be w.index or a vertex with a lower index that belongs to the same SCC (so the algorithm will work as expected): the value of lowlink still differs for differents vertices of the same SCC.

The following example show how DFS order alters lowlink values in this alternative algorithm:

In this case, assuming we are exploring vertices in the order 0-1-2-3-4, when we consider the vertex 3, the vertex 4 has not been explored yet. The lowlink value of vertex 1 is so 1, and vertices 2 and 3 will take the same value. But we will later find the back edge from 4 to 0, and set the lowlink value of vertices 4 and 1 at 0. If we had explored vertex 4 prior to vertex 2, all vertices would have 0 as lowlink value.

And for the last question, yes, all this verteces belong to the same SCC, rooted by x.lowlink or an ancestor of the vertex with id x.lowlink


Loop invariant for a division algorithm I'm having problems trying to understand the concept of loop invariants.

I have the following code, where M and N are predefined constants.

a = 0
b = M
c = 1
while M - c * N >= 0:
  a = c
  c = c + 1
  b = M - a * N
print(a, b)

I have figured out this code is actually a division algorithm, where in the end prints out a as the quotient of M/N and b as the remainder. But it's unclear to me what the invariant here is. Can I say c-a is the invariant since c-a=1 is always true before and after every iteration? How could I prove that in a mathematical perspective?

A loop invariant is an expression that is true through all iterations. But it should also lead to the post-condition being true when the loop terminates. Although c-a=1 is true, It doesn't help you in achieving the post-condition.

Intuitively, You would want the invariant to be a*N + b = M because that's what division is and that's what guarantees that you'll get the post-condition ( a=quotient, b=remainder) when the termination condition ( b < N ) is true.

The formal proof should follow from this idea.


What is the computational complexity of intuitionistic propositional logic? Consider the decision problem: given formulas of propositional logic $\phi_1, \ldots, \phi_n, \psi$, determine whether $\phi_1, \ldots, \phi_n \vdash \psi$ intuitionistically.  This problem is well-known to be decidable, for example using an algorithm derived from the LJT* sequent calculus.  I was wondering if the computational complexity of this problem is known.

Trivially, the complexity is polynomial-equivalent to the complexity of the intuitionistic tautology problem: $\phi_1, \ldots, \phi_n \vdash \psi$ if and only if $\phi_1 \wedge \ldots \wedge \phi_n \rightarrow \psi$ is a tautology; and conversely, $\phi$ is a tautology if and only if $\vdash \phi$.
Certainly, the problem is co-NP-hard: as a corollary of the double-negation embedding, a formula $\phi$ is classically satisfiable if and only if $\lnot \phi$ is not a tautology of intuitionistic logic.

On the other hand, if I'm not mistaken, the problem is in PSPACE: the only rule of LJT* which could possibly increase the total length of a proof context is in the first subgoal of $(\alpha, \beta \rightarrow \gamma, \Gamma \vdash \beta) \wedge (\gamma, \Gamma \vdash \delta) \implies (\alpha \rightarrow \beta) \rightarrow \gamma, \Gamma \vdash \delta$.  But in that case, the second copy of $\beta$ should still be at most equal to the length of a formula in the original context.

(Also, since the Rieger-Nishimura lattice, the free Heyting algebra on one generator, has a simple computable description, the special case of this problem restricted to problems with a single atom would be in P.  That would be a severe restriction, though.)

Beyond that, in a quick Google search, I didn't find any results directly on this problem, just a few papers where the abstracts seemed to indicate they were considering fragments of propositional logic.  I also can't find any proof on my own which would refine the status.  (For example, for all I know, it might be possible that whenever the sequent is not intuitionistically valid, there exists a Kripke model of polynomial size which demonstrates this - in which case the problem would be co-NP-complete.  Or more generally, a Heyting algebra with a polynomial-size "description" would suffice.  It's harder for me to imagine some way to reduce a problem such as QBF to an instance of this problem to prove it's PSPACE-complete, though I also can't entirely rule out the possibility.)

A quick google search shows that the problem is PSPACE complete, a result apparently first proven by R. Statman.


Clique-problem for planar graph I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion

  This follows already from Kuratowski's theorem: a clique is at most of size 4.

I've never heard of that theorem before and the exercise indicates to proof it with the fact, that the class of planar graphs is closed under sub graphs.
Thank you for your help!

Regarding the proof of the statement you quoted (to complement Juho's answer):

Let $G$ be a connected planar graph with $V > 2$ vertices, $E$ edges and $F$ faces. We know from Euler's formula that $V-E+F=2$.

Now let us count the number $q$ of $(e,f)$ pairs where $e$ is an edge and $f$ is a face incident to $e$. Because every edge is incident to at most two faces, $q \leq 2E$. Because every face is incident to at least $3$ edges, $q \geq 3F$. Thus, $3F \leq 2E$. Using this together with Euler's formula we get that $3V = 3E - 3F + 6 = E +6 + (2E - 3F) \geq E+6$. Thus $E \leq 3V-6$.

Now, if some graph had a clique of size $5$, by taking this clique as a subgraph we would have that the complete graph on $5$ vertices $K_5$ is planar. But this graph has $V=5$ and $E=10$, thus $E > 3V-6$, which contradicts what we have just shown. Thus, $K_5$ is not planar and our original graph has no clique of size $5$ or more.


Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list? There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).

On average, how many of these random comparisons will you need to be able to sort the list?

Some follow-up questions:

What does the distribution for the number of comparisons needed look like?
What is the answer if you use $k$-ary comparisons instead of binary ones.
What is the answer if the comparisons are made without replacement (i.e. you won't get the same comparison twice)?
Given a set of comparisons, how can one check if the list is sort-able? I'm almost certain the answer is to construct a DAG and topological sort, but I just want to confirm.

An exact-ish answer would be nice, but a big $O$ answer is fine too, I suppose.

Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons.

Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order.  Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, you will have no way to tell which order they should appear in.  The same is true of every pair of adjacent element.  So, there are $n-1$ coupons (one per adjacent pair of elements), and you need to collect them all.  Based on the coupon collector problem, we know you'll need $\Theta(n \log n)$ randomly chosen coupons before we've collected them all.  Each observation has a $2/n$ chance of being a coupon, so in total we'll need $\Theta(n^2 \log n)$ observations before we've collected all the coupons.  If we collect all the coupons, we can sort the $x$'s; if we're missing any coupon, we can't sort them.

The subsequent questions boil down to facts about the coupon collector problem, and you can use the tail bounds on Wikipedia to bound the information about the distribution.

If comparisons are chosen without replacement, then you need $\Theta(n^2)$ observations.

A reasonable way to check whether the list is sortable is to do a topological sort, then check that you've observed a comparison between every pair of adjacent items in the topologically sorted order.


Solving problems related to Marginal Contribution Nets So, I encoutered this problem in examination:

  Consider the following marginal contribution net:

  $\{a \wedge b\} \to 5$

  $\{b\} \to 2$

  $\{c\} \to 4$

  $\{b \wedge \neg c\} \to −2$

  Let $v$ be the characteristic function defined by these rules. Give the values of the
  following:

  i) $v(\emptyset)$

  ii) $v(\{a\})$

  iii) $v(\{b\})$

  iv) $v(\{a, b\})$

  v) $v(\{a, b, c\})$

My answer is below, but I am not sure.

  i) $v(\emptyset) = -2$

  ii) $v(\{a\}) =  0 - 2$

  iii) $v(\{b\}) =  2 - 2$

  iv) $v(\{a, b\}) = 5 + 2 - 2$

  v) $v(\{a, b, c\}) = 5 + 4 + 2 - 2$

If anybody knows how to solve this kind of problem, could you confirm?

Exact same problem is shown on page 4 of following paper:
Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games (by Samuel Ieong and Yoav Shoham)

I got the following answer:

$v(\emptyset)=0$
$v(\{a\}) = 0$
$v(\{b\}) = 2-2 = 0$
$v(\{a,b\}) = 5+2-2 = 5$
$v(\{a,b,c\}) = 5+2+4 = 11$

Here's a general approach to doing this calculation.
Consider a set $A\subseteq \{a,b,c\}$. Define a map $I_A:\{a,b,c\}\to\{\text{True},\text{False}\}$  as follows:
$$I_A(x) = \left\{ \begin{array}{l@{~~}l} \text{True} & \mbox{if}~x\in A \\
\text{False} & \mbox{otherwise}
\end{array}\right.$$
This is the so-called indicator function of set $A$.

Now take each element of the marginal contribution net and evaluate whether it is true or false given $I_A$. If it is true, add the contribution. If not, add no contribution. More explicitly, given element $\psi\to c$, add $c$ only if $I_A\models\psi$ holds.

Here the notation $I_A\models\psi$ simply means evaluate the truth of the formula $\psi$ given the assignment of the variables $\{a,b,c\}$ to true or false.

Consider $v(\{a,b\})$. This corresponds to the map
$I_{\{a,b\}}=\{a \mapsto\text{True},b\mapsto\text{True},x\mapsto\text{False}\}$. Given this assignment of truth values, we can conclude that:

$a\wedge b$ is true, so $5$ is contributed.
$b$ is true, so $2$ is contributed.
$c$ is false, so nothing is contributed.
$b\wedge\neg c$ is true, so $-2$ is contributed.

Therefore the total contribution is $5+2-2=5$.


All-to-All Broadcast on a Balanced Binary tree Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree?

Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages between any two nodes connected by bidirectional channels takes time ts + twmk if the communication channel (or a part of it) is shared by k simultaneous messages.

Should I use Scatter technique on it, i.e, All-to-Personalized Communication?

There are 8 processors: P0..P7, each contains one of the messages M0..M7 so

P0: M0, P1:M1, P2:M2, P3:M3, P4:M4, P5:M5, P6:M6, P7:M7

P0, P1, P2, & P3 are on the left subtree and P4, P5, P6, P7 are on the right subtree.

Step1:

All the processes make a copy of the message and left subtree processors exchange the copy with the corresponding processors on the right subtree. Result is that each processor now has two messages as shown below:

P0 & P7: M0, M7

P1 & P6: M1, M6

P2 & P5:M2, M5

P3 & P4:M3, M4

Step2:

Now P3 & P0 would make a copy of their messages and exchange the copy. Pairs of P1, P2 and P4,P7 and P5, P6 would repeat this action. The result is shown below:

P0, P3, P4 & P7: M0, M3, M4, M7

P1, P2, P5 & P6: M1,  M2, M5, M6

Step3:

Now P0 & P1, would make a copy of their messages and exchange the copy. Pairs of P2, P3 and P4, P5 and P6, P7 would repeat this action. The result is the final broadcast:

P0, P1, P2, P3, P4, P5, P6, P7 would all contain the messages:

M0, M1, M2, M3, M4, M5, M6, M7

Zulfi


Predicate Logic - Natural Deduction; Assumptions about exists-elimination I am stuck on how to progress with this proof; i cannot see my next move.

The task is to show $S \to \exists x Q(x) \vdash \exists x (S \to Q(x))$ using natural deduction for predicate logic.

My first attempt was the following;

1: $S \to \exists x Q(x) \space \space \space \space \space \space premise$
2: $x_{0} \space \space S \to Q(x_{0}) \space \space assumption$  (start of scoped box, i do not know how to write them here)
3: $\exists x(S \to Q(x)) \space \space \exists x \space introduction \space 2$ (end of scoped box)
4: $\exists x(S \to Q(x)) \space \space \exists x \space elimination \space 1,2-3$

However, i am not so sure that this is correct. The rule for $\exists$ elimination is
$\frac{\exists x \phi \space \space(And \space we \space manage \space to \space infer \space \gamma \space from \space replacing \space x \space in \phi \space with \space a \space fresh \space variable)}{\gamma}$
I do not know how to render the rule here (bonus question), but here's a link to where it is better described (page 16).

In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Can anyone explain if my thinking is correct, and point out my next move, or if i am wrong please explain why i am wrong? (Incidentally the link above describes exactly those rules my course litterature allow me to use, so if i could get help in terms of those rules i would be doubly grateful).

In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Exactly right. Your second move was illegal for the reason you said.

The problem is a bit tricky because of the annoying $S \to$ in front of the $\exists x Q(x)$, which means we can't eliminate the existential just yet. In order to get to $\exists x Q(x)$, we need to first have a proof of $S$, or know that $S$ is true. But we don't!

So how do we remove $S$ in front if we don't know it's true? Try first proving, as a lemma, that $S \lor \lnot S$: the law of the excluded middle. Next, your proof will have two cases: one if $S$ is true, and one if $S$ is not true. If $S$ is true, you should be able to eliminate the existential to get your $x$. If $S$ is not true, you should be able to prove $\exists x (S \to Q(x))$ by taking any $x$ at all.

By the way, in case you're interested: one reason this inference is difficult to solve is that not all logicians agree with it! There are logicians who proposed something called "Free Logic", with the main idea being that it is possible for no objects to exist at all. If no objects exist at all, then $S \to \exists x Q(x)$ might be true (it will be true if $S$ is false), but $\exists x (S \to Q(x))$ is definitely false no matter what, because there does not exist any $x$ period.


Induction on recursive formula Okay so I have this recursive formula
$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$
$T\left(n\right) =T\left(1\right)\ +\ c_{2}*n\cdot\sum_{k=1}^{⌊\log\left(n\right)⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}*(n-1)$
I've been trying for a few hours to prove the correctness of it by induction, I feel like I've tried everything. The closest I got was defining $n=2^{x}$ and prove the correctness for every $x$ but I can't seem to get the right answer.. How do you prove something like that?
The main question is how do I prove $T(n) = T(n/2) + c_{2}n = T(1) + c_{2}*(n-1)$

The series $\frac{1}{2^k}$ is a geometric progression. Hence, $\sum_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$
You can continue from here.


Interval schedule maximization when encountering intervals with equivalent end points In interval scheduling, the greedy solution which maximizes the schedule that contains the largest number of "compliant intervals" involves initially sorting the list of intervals in ascending order by the end-times/point of each interval.

What confuses me, is if two or more intervals have the same ending time.

When performing the initial sort, should one base the sort of the sub-range of intervals on start time?

and if so should it be in ascending or descending order?

The greedy algorithm can be characterized as follows:

Let $I$ be the initial set of intervals

1) Select an interval, $x \in I$, with the earliest finishing time.

2) Remove $x$ and all intervals intersecting $x$ from $I$, obtaining $I^{'}$.

3) add $x$ to the solution

4) Set $I=I^{'}$

5) Continue until $I$ is empty.

Here, $x$ is some remaining interval that finishes before all other intervals in $I$. When we add $x$ to our solution we have already removed any interval with the same finish time as $x$ that may have had a start time which was "too early." If there is some other $y\in I$ with the same finish time as $x$ that is present when $x$ is chosen, then by necessity, both $x$ and $y$ begin after the last interval we added to our solution, so either is a legitimate choice.


How to recognize a STRIPS planning problem has no solution? Strips –Stands for STanford Research Institute Problem Solver (1971).

STRIPS Pseudo code -

STRIPS(stateListstart, stateListgoals)
1.Set state = start
2.Set plan = []
3.Set stack = goals
4.while stack is not empty do
     1.STRIPS-Step()
5.Return plan

STRIPS-Step()
switch top of stack t:
1.case this a goal that matches state:
    1.pop stack
2.case this an unsatisfied conjunctive-goal:
    1.select an ordering for the sub-goals
    2.push the sub-goals into stack
3.case this a simple unsatisfied goal
    1.choose an operator op whose add-list matches t
    2.replace the twith op
    3.push preconditions of op to stack
4.case this an operator
    1.pop stack
    2.state = state + t.add-list -t.delete-list
    3.plan = [plan | t]

Some explanations -

state - is a list of predicates.

stack - is a stack which includes both predicates or operations.

[plan | t]  - add the opreration t to list plan.

If the stack gets empty, it means that plan holds the solution plan.

Since the algorithm is running while stack is not empty do, how can I recognize that there is no solution (i.e plan) which led to the goal state ?

Those who are not familiar with this algorithm,  you can see its running example here. Brief introduction: imagine a crane which picks boxes and put them each other , so operation can be put box A on box B and state can be box A is on box B .

Realize that STRIPS solves linear planning problems. By this I mean those planning tasks where the order in which the goals are satisfied is not relevant and these are, in practice, easier to solve than the non-linear planning problems ---be aware, however, that STRIPS is PSPACE-complete anyway and it is necessary to restrict it quite a lot to prove it to be NP-complete (though whether both classes are equal is still unknown but, ... may I say unlikely?)

Non-linearity is quite intriguing. It does not only mean that a particular planning task with, say, 3 goals $G=\{g_1, g_2, g_3\}$ can only be satisified in a particular ordering (such as: first $g_2$, then $g_1$ and finally $g_3$). It might also imply that while some goals are achieved simultaneously, others have to be satisified in a particular order. A good discussion on the subject can be found in Korf, Richard E. Planning as Search: A Quantitative Approach. Artificial Intelligence 33, pp. 65--88. 1987

From your pseudocode, realize that STRIPS commits to a particular order in line 2.1 of STRIPS-step and it never tries any other one. In fact, the ordering selected for the goals is strict after step 2.2. Thus, STRIPS explores the whole state space engendered by the definition of the planning task for a particular ordering of the subgoals If this ordering has not been properly chosen, then the problem is unsolvable for STRIPS.

In the end, all that STRIPS can say is that a problem is unsolvable for a particular ordering but not whether the planning task is solvable or not. Although it is not shown in your pseudocode, recall that STRIPS can discard a particular operator if its preconditions introduce goals that were considered before ---i.e., it avoids circular reasonings. And, in the end, it will have no available operator if the problem is unsolvable for the selected ordering.

PRODIGY was an attempt to solve this problem by explicitly enumerating all the different orderings of the subgoals which, however, might become very easily an unmanageable number. FF, Hoffmann, Joerg, Nebel, Bernhard. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14, pp. 253--302. 2001, however, can detect that some planning tasks are unsolvable even if they are non-linear planning tasks just by verifying that the relaxed graphplan cannot achieve them. Nevertheless, this procedure is sound but incomplete ---i.e., some unsolvable planning tasks can seem solvable fooling FF.


Prove this language is decidable? $L$ is defined over the alphabet $\{a,b\}$ and it's decidable.
The language is $\mathrm{perm}(L)$ which is the set of all permutations of all words in $L$.

So far my proof is the following:

Construct a TM $M$ that decides the language $\mathrm{perm}(L)$. $M$ has input $w$.
Let $\pi(w)$ be a random permutation of w. Then feed it to $M$: $M$ accepts if $\pi(w) \in L$ or rejects if $\pi(w) \notin L$.

I.e. if we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \in L$, $M$ should halt and accept.
If we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \notin L$, $M$ should halt and reject.

Is this correct and enough?

To show it's decidable, you just need to give some effective procedure to decide the language. While giving a TM is a pretty straightforward way to do this, it's not the only way. A much easier way to show this language is decidable is to give plain-old pseudocode for an algorithm to decide the language. Consider this:

AcceptsPermutation(
    word : string,
    Accepts : string -> Boolean)
1. permutations = GenerateAllPermutations(word)
2. result = false
3. for each permutation in permutations do
4.     if Accepts(permutation) then result = true
5. return result

In the above pseudocode, Accepts is a function that accepts the target language. Since the target language is decidable, this function is guaranteed to exist; in fact, you have a TM that computes it (or at least, you have something close).

If you can produce pseudocode to generate all permutations of a word, then you're already done. Consider the following:

GenerateAllPermutations(word : string)
1. if length(word) <= 1 then return {word}
2. else then
3.     result = {}
4.     for n = 1 to length(word) do
5.         first = word[n]
6.         rest = GenerateAllPermutations(word[1...n-1] + word[n+1...length(word)])
7.         for each permutation in rest do
8.             result.add(first + permutation)
9.     return result

Apologies if that isn't quite right... with luck, it's enough to convey the idea.

Suppose you really, really want to stick to Turing Machines. We can still make this problem a lot easier by relaxing the restrictions. Consider a multi-tape, multi-TM scenario: one TM reads the input tape, and begins writing permutations to an auxiliary tape. Once a permutation is written, the TM stops, activates a second TM on the new tape, and waits for the answer. If the TM accepts, so do we; otherwise, write the next permutation to the tape. If we run out of permutations to write, reject.

The TM on the second tape is the TM we assume exists since the language $L$ is decidable. All you need now is a $TM$ that can write permutations to a second tape. We might imagine a single-tape TM that works like the above algorithm... it might make the tape look something like this:

Someword_Omeword_Meword_Eword_Word_Ord_Rd_D_
Someword_Omeword_Meword_Eword_Word_Ord_rD_R_
...
someworD_somewoR_somewO_someW_somE_soM_So_O
someworD_somewoR_somewO_someW_somE_soM_sO_S_

Very roughly, the way to get the tapes to look like this is to:

Write out the initial one by capitalizing the first letter, scanning to the end, adding a blank, copy all the lower-case letters between the last two blanks, and repeat until nothing is copied.
Scan to the front; then, scan right, copying each upper-case letter to the second tape as a lower-case letter, until you see two blanks in a row.
Run the second TM on the second tape, to see if that's an accepted permutation.
Clear the second tape.
From the end of the first tape, scan backwards until you see a lower-case letter preceding a blank, erasing anything you see. When you do see a lower-case letter right before a blank, scan left until you see an upper-case letter; change it to lower-case, move right, and change that letter to upper case. Move to the second blank space to the right. Then, proceed to recreate the permutation string as in (1).
Continue in this way until, while scanning left, you see two blanks in a row. This means you've erased the entire tape without finding a matching permutation; since this procedure tries all permutations, you're done.

To make sure you've got it, try to work out the 3rd and 4th permutation strings generated by the above method, as well as the 3rd and 4th from last strings. They should be those given below:

...
Someword_Omeword_Meword_Eword_Word_oRd_Od_D
Someword_Omeword_Meword_Eword_Word_oRd_oD_O
...
someworD_somewoR_somewO_someW_somE_sOm_Sm_M
someworD_somewoR_somewO_someW_somE_sOm_sM_S
...


Connected Vertex Cover I'm trying to prove the Connected Vertex Cover problem is NP-complete. That is given a graph $G=(V,E)$ and integer $k$, is there a subset $X$ of $V$ such that $|X|≤k$ and that for every edge $(u,v)\in E$ at least one of $u$ and $v$ are in $X$. Furthermore, the subgraph $G[X]$ induced by $X$ must be connected.

I know the structure of an NP-complete proof. But I have no idea what problem to reduce to connected vertex cover and how to go about it.

(First, a side note: it happens that Connected Vertex Cover isn't actually NP-hard for all classes of graphs. In particular, it's solvable in polynomial time in chordal graphs and graphs with maximum degree 3. However, it is NP-hard for planar graphs with maximum degree 4 in particular, and that's the easiest case to prove.)

For this, you'll want to reduce from Planar Vertex Cover. This is the special case of Vertex Cover where the input graph is planar, and it itself can be proved NP-hard by reduction from Planar 3Sat. (Planar 3Sat is, similarly, the special case of 3Sat where the input graph is planar. Proved NP-hard by reduction from normal 3Sat, and it itself is used to prove that various games are NP-hard, such as Super Mario Bros, Super Mario Bros 3, and Super Mario World.)

This reduction was first done by Garey and Johnson in 1977. I'm currently trying to find the full details of their proof, but these lecture notes provide a general overview.


Substituting two different identifiers with the same identifier in Coq - why does this work? I'm playing around with Coq and Software Foundations and is somehow very confused by something I took for granted since forever.

To prove

Theorem app_length_cons : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

we can first prove

Theorem app_length_cons' : forall (X:Type) (l1 l2:list X) (x:X),
                             length (l1 ++ x :: l2) = S (length (l1 ++ l2)).

which is a straightforward induction,

Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  rewrite -> IHl1'.
  reflexivity.
Qed.

Then simply

Proof.
  intros.
  apply app_length_cons' with (l1:=l1) (l2:=l1).
Qed.

However, there is something strange going on here - in the induction proof, we are doing induction on l1 and not l2 - and from the proof, it looks like we are assuming l2 doesn't change in the induction case. But when we later apply it with l2:=l1, we are breaking this assumption.

Indeed, if we try to prove

Theorem app_length_cons'' : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

use the same method

Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  -- Can't rewrite use IHl1' : length (l1' ++ x :: l1') = S (length (l1' ++ l1')),
  -- since the goal is S (length (l1' ++ x :: h :: l1')) = S (S (length (l1' ++ h :: l1')))

it looks like the assumption that l2 doesn't change is broken thus the proof won't work.

I'm pretty sure I'm missing something here. Why can we substitute different identifiers with the same identifier?

it looks like we are assuming l2 doesn't change in the induction case.
  But when we later apply it with l2:=l1, we are breaking this
  assumption.

No. If we regard l1 to be a value which is repeatedly decreased in the induction proof, note that we let l2 to be equal to the initial value of l1 -- such value will not change in the induction steps. In other words: the value of l1 will decrease, but l2 will always be the initial value of l1.

We can even compare it with recursion in programming:

# pseudocode
def f(x, y):
   if x==0: return baseValue
   use f(x-1, y)
   return something

Just because f(x, y) is defined by induction on x, it does not mean that later on we can't call f(a, a) where both arguments have the same value a.


Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)? This is the algorithm I'm using:
https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627

Specifically C#, but the linked thread has numerous languages.

Worst case time complexity should be O(|V|^{2}\log |V|+|V||E|)}
https://en.wikipedia.org/wiki/Johnson%27s_algorithm

My findings running benchmarks using the first algorithm linked:

[polygons (each 3 vertices and 3 edges): milliseconds]

10: 332 ms (~30 vertices, 30 edges)
11: 789 ms
12: 2344 ms
13: 7524 ms
14: 16788 ms
15: 54182 ms (~45 vertices, 45 edges)

That's exponential growth!

My only question:
Is this a polynomial time algorithm that I'm using to find all cycles in a graph or not?

Thanks :)

The question seems based on a faulty premise. There are multiple algorithms that Johnson invented, and you're confusing them.  One of his algorithms is for finding shortest paths (that's the one Wikipedia article talks about), another is for enumerating all cycles (that's the one the Stack Overflow answer cites).  They don't have the same running time.

Second, you're using some random person's code, but maybe that code sucks and isn't a good/valid implementation of the algorithm.  We don't do questions about code here.

Also, as David Richerby says, you obviously can't output all cycles in polynomial time if there are exponentially many of them (where there can be).  Therefore, you shouldn't expect an algorithm to enumerate all cycles with polynomial running time.

Finally, you can't disprove an asymptotic running time analysis by benchmarking it on 6 points.

I think you need to read Johnson's original paper, understand it, and implement it yourself.  Sometimes there are no shortcuts.


Proving a language with $(ab)^n$ is not regular with pumping lemma? I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:
\begin{align}
L_1 &= \{(ab)^n c^m \mid n\ge 1,  m\ge 2n \} \\
L_2 &= \{(ab)^n a^k (ba)^n \mid k<3\}
\end{align}
For $L_2$ my approach was:

Let us be given a number $p$. Let $z = (ab)^p a^k (ba)^p$, which satisfies $|z| = 2p > p$, and let $z = uvw$ be its decomposition satisfying $|uv| \leq p$ and $|v| > 0$. This means that $v = (ab)^j$ for some $0 \le j \le p$. We choose $i = 2$ for $uv^iw$, which equals $(ab)^{p+j} a^k (ba)^p$. This word has more $ab$ than $ba$, which means that it doesn't belong to the language. Therefore $L_2$ is not regular.

Mainly I am actually confused with the $(ab)^n$, we should decomposed it so that we can pump $v$, but it is necessary to consider different cases of $v$, or is this sufficient?

Let's suppose, for concreteness, that $p = 3$.
You choose the word $z = (ab)^3a^k(ba)^3$. How does this word look like? It is impossible to tell, since we don't know what the value of $k$ is. Let's therefore take $k = 3$, that is, we are looking at the word $z = (ab)^3(ba)^3 = abababbababa$.
Next, we are given a decomposition $abababbababa = uvw$, where $|uv| \leq 3$ and $v \neq \epsilon$. There are six possibilities:

$u = \epsilon$, $v = a$, $w = bababbababa$.
$u = \epsilon$, $v = ab$, $w = ababbababa$.
$u = \epsilon$, $v = aba$, $w = babbababa$.
$u = a$, $v = b$, $w = ababbababa$.
$u = a$, $v = ba$, $w = babbababa$.
$u = ab$, $v = a$, $w = babbababa$.

You need to be able to handle all of them. There are four different cases: $v \in (ab)^*$, $v \in (ba)^*$, $v \in a(ba)^*$, $v \in b(ab)^*$. For each of them, you need to find a value of $i$ so that $uv^iw \notin L_2$. When showing that $uv^iw \notin L_2$, you have to show that there are no $n \geq 0$ and $k < 3$ such that $uv^iw = (ab)^n a^k (ba)^n$.