Speaker independent voice command recognition I am looking for a software, a library or an algorithm that can be trained to recognize about a dozen speaker independent voice commands. The commands will be very distinct phrases of 4-5 words each. They can be chosen to sound very different from each other. Additionally, the commands will be in more than two different languages. The user will be guided to say only the exact phrases and talk slowly, loud and clear in front of the microphone.

I am currently looking for an algorithm that can compare speech spectrograms and give me a matching percentage, but no luck so far. Any ideas?

If it helps, the code can be written for the specific phrases only, and, in worst case, the phrases can be reduced to 3 or 4.

Software

There are many many speech recognition toolkits and software packages, which should be able to do what you want.  See, e.g., https://en.wikipedia.org/wiki/List_of_speech_recognition_software for a partial list.

For instance, if you're looking for open source software, you could try Sphinx, Simon, or any number of other software packages.  They can be trained in various ways, and probably can be used for what you want.  There are also many proprietary speech recognition tools, which might meet your needs as well.

Algorithms

The algorithms used by speech recognition systems are pretty standard.  You split the audio into frames, use the MFCC transform to compute Mel features, then use Dynamic Time Warping or a HMM with Gaussian mixture model to recognize the spoken phrases.  I would anticipate this standard pipeline would likely work for your requirement, if you train it appropriately.

(I'm not sure why you want to start from a spectrogram rather than from the audio clip itself.)


Can one build a "mechanical" universal Turing machine? This question connects different disciplines so it's awkward to choose a SE site for it, but I'll go with this one because here (I hope) the shared culture will make information transfer easier.
So computers as we know them use electricity and I don't know what other invisible things that I don't understand. I was wondering, is this a matter of efficiency, or of necessity? Can one achieve universal computation with just "moving parts"? Perhaps "Newtonian physics" is some term for this, although I guess it includes gravity which isn't really what I mean. You know, just good old solid pieces of matter moving around.
To get some picture of what I mean, here is a "LEGO Turing machine". I'm afraid that the big gray block on top uses electricity, but could one replace it with a "mechanical" thing, powered perhaps by rotating a piece? I have no idea how such things be designed, and the state transitions for a universal TM have to be fairly complicated, so I have no intuition for whether this is possible or not.

Sure. Electricity is unrelated to the model of computation.
The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially equivalent to a deterministic finite automaton.
Here's a Turing Machine made of wood:
https://www.youtube.com/watch?v=vo8izCKHiF0&ab_channel=RichardRidel


Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations? I can compute this easily in the case that $xy < 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$.

I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but I'm not sure where to go from there.

Use two integers to represent one integer. Assume you are using c/c++. You can use a struct that has two long long unsigned integers to represent $x$, $y$ and $z$. So you can express $x = 2^{32}x_1+x_2$ with $x_1$ being a nonnegative integer smaller than $2^{32}$ and $x_2$ being a nonnegative integer not greater than $2^{32}$. I would assume you will know the rest.

Or you can choose to use some libraries or built-in classes. For example, you can use BigInteger class in Java.

(It goes without saying that you will not have these problems if you were using Python, Ruby, etc.)


If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete? Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete.

Why these two languages in particular? Can't we reduce any other language in ${\sf P}$ to them by outputting them when accepting or not accepting?

As there are no strings in $\emptyset$, any machine that computes it always rejects, so we can't map Yes-instance of other problems to anything. Similarly for $\Sigma^{\ast}$ there's nothing to map No-instances to.


Why if L and ¬L (Complement of L) are turing-recognized both are turing-decidable? I can't understand this theorem:
If both L and L complement are turing-recognized, both are turing-decidable
Proof:

w is M input
if w ∈ L then M1 accepts w and M accepts w
if w ∉ L then M2 accepts w and M rejects w

M is a TM containing M1 and M2.

I will try to explain it in simpler terms.
If $L$ is Turing recognizable, there exists a TM $M_1$ that halts and accepts any input string $w \in L$. It is not guaranteed to halt on any input string $w \notin L$.
If $\bar{L}$ is Turing recognizable, there exists a TM $M_2$ that halts and accepts any input string $w \notin L$. Similarly to above, $M_2$ is not guaranteed to halt on any input string $w \in L$.
Now, for every $w$ we have two options: either $w \in L$ or $w \notin L$. Therefore for any input string $w$, exactly one of these machines will halt and accept. This allows us to construct the decider described in you proof. Create a machine $M$ that simulates $M_1$ and $M_2$. With $w$ as input, accept $w$ if $M_1$ accepts, reject if $M_2$ accepts. This machine is a decider for $L$ and therefore $L$ is decidable.
To prove $\bar{L}$ decidable as well, you could apply the same logic, but it is sufficient to point out that decidable languages are closed under complement.


NP and finite automata A language $L$ is in NP if and only if there exist polynomial $q$, and a deterministic polynomial Turing machine $M$ such that, for all $x\in L$, there is a string $y$ such that $|y|\leq q(|x|)$ and $M(x,y) = 1$.

My question is is it possible to exchange $M$ for a finite automaton?

Thank you

What you have given is a definition. You can define anything you want.  The class of languages defined as

  A language $L$ is in UC (user71565's class1) if there are a polynomial $q$ and a DFA $A$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $A$ accepts $xy$

is a perfectly legitimate class of languages.  For example, it includes all regular langauges (take $y=\varepsilon$ for every $x$).

However, because this is not the same definition as the definition of NP that you quoted in your question, you shouldn't expect that UC$\,=\,$NP.  In fact, we can quickly see that UC$\,\neq\,$NP, using the pumping lemma and a language such as $\{0^n1^n\mid n\geq 0\}$, which is in NP but cannot be recognized by any DFA.

Interestingly, though, the following definition is equivalent to the normal definition of NP:

  A language $L$ is in NP2 if there are a polynomial $q$ and a deterministic logspace Turing machine $M$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $M(x,y)=1$.

That is, we can weaken from a deterministic polynomial-time verifier to a deterministic logspace one, without changing the class of languages defined. This is a consequence of Fagin's theorem, which says that the verifier can actually be a formula of first-order logic.  The expressive power of first-order formulas is strictly weaker than deterministic logspace Turing machines.

1 There's something of a tradition of naming language classes in this way. For example, the class NC of languages decidable in polylog time with polynomially many processors stands for "Nick's class", after Nick Pippenger.


Algorithms that are using John's ellipsoid The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for algorithms based on those ellipsoids, or any significant practical use that requires finding them explicitly.

Rimon and Boyd use Lowner–John ellipsoids in their "...method for estimating the distance between a robot and its surrounding environment".

From the abstract:

  First, approximate the detailed geometry of the robot and its
  environment by minimum-volume enclosing ellipsoids. ... Then
  compute a conservative distance estimate using ... [a] formula for the
  distance of a point from an n-dimensional ellipse.

E. Rimon and S Boyd. Obstacle Collision Detection Using Best Ellipsoid Fit. Journal of Intelligent and Robotic Systems, 1997 - Springer


Can a Post machine have more than one accepting state? I was searching through Google and I couldn't find anything.

Can a Post machine have more than one accepting state?

According to the description on Wikipedia, there could be more than one accepting state. The truth is, it doesn't matter. The model with a single accepting state and the model with many accepting states are equivalent. A machine of the former kind is also a machine of the latter kind. In the other direction, starting with a machine with many accepting states, single out one of them as the "real" accepting state, and add transitions from the other states to the chosen accepting state.


detect closed shapes formed by points I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other).

Now I need to find the (possibly approximate) centers of the closed shapes. Alternatively, it's good to "recognize" the closed shapes and to fill them. I don't know what is easier given the coordinates of points forming the shapes.

A possible example with 3 closed shapes to detect is given below.

Points can be also added along the image's borders, thus, closing all open shapes. Then all "regions" in the figure will be closed, but the question persists.

find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
Number all curves 1..n. Set some order of segments in them.
For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI[1] is null. If not, SOI[1]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
Obviously, you are looking only for simple bordered areas, that have no curves inside.
Pieces of curves between two adjacent non-null intersection points we'll call segments.
Having SOI for each curve:

for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
For the right attempt, make only left turns, for the left attempt, make only the right turns.
If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
Remember all successful attempts
Repeat this for all segments of curve 1
Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

Edit:
How to find the orientation of the intersection.

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix:

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.


Quicksort where element comparison outcome is random. Probability of element being in a certain position So we have this block of pseudocode:

Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];
qsort(Monsters,rand_compare);

  qsort() sorts the array via quicksort where we use the last element
  as pivot. To compare two elements it uses rand_compare, which, with
  equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or
  "2. element is bigger" and never "both are equal". What is the
  probability that M8 appears in position 0, 1 or 2, respectively, after
  applying qsort ?

I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?

In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625


Maximum Independent Set of a Bipartite Graph I'm trying to find the Maximum Independent Set of a Biparite Graph.

I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":

  Problem:

  Given a bipartite graph $G = (U,V,E)$, find an independent set $U' \cup V'$ which is as large as possible, where $U' \subseteq U$ and $V' \subseteq V$. A set is independent if there are no edges of $E$ between
  elements of the set.

  Solution:

  Construct a flow graph on the vertices $U \cup V \cup \{s,t\}$. For
  each edge $(u,v) \in E$ there is an infinite capacity edge from $u$ to
  $v$. For each $u \in U$, there is a unit capacity edge from $s$ to $u$,
  and for each $v \in V$, there is a unit capacity edge from $v$ to
  $t$.

  Find a finite capacity cut $(S,T)$, with $s \in S$ and $t \in T$. Let
  $U' = U \cap S$ and $V' = V \cap T$. The set $U' \cup V'$ is
  independent since there are no infinite capacity edges crossing the
  cut.  The size of the cut is $|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$. This, in order to make the independent set as large as
  possible, we make the cut as small as possible.

So lets take this as the graph:

A - B - C
    |
D - E - F

We can split this into a bipartite graph as follows
$(U,V)=(\{A,C,E\},\{B,D,F\})$

We can see by brute force search that the sole Maximum Independent Set is $A,C,D,F$. Lets try and work through the solution above:

So the constructed flow network adjacency matrix would be:

$$\begin{matrix}
  & s & t & A & B & C & D & E & F \\
s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\
C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\
F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
\end{matrix}$$

Here is where I am stuck, the smallest finite capacity cut I see is a trivial one: $(S,T) =(\{s\},\{t,A,B,C,D,E,F\})$ with a capacity of 3.

Using this cut leads to an incorrect solution of:

$$ U' = U \cap S = \{\}$$
$$ V' = V \cap T = \{B,D,F\}$$
$$ U' \cup V' = \{B,D,F\}$$

Whereas we expected $U' \cup V' = \{A,C,D,F\}$?  Can anyone spot where I have gone wrong in my reasoning/working?

The complement of a maximum independent set is a minimum vertex cover.

To find a minimum vertex cover in a bipartite graph, see König's theorem.


Question regarding coin change algorithm (DP and greedy) The question goes something like this:

Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy approaches would compare?

Intuitively I want to answer that DP will be faster because greedy runs the same number of comparisons regardless of the relationship between the elements in V. But DP is a recursive call on previous elements, so the fact that there is always a ratio of p between each denomination of V would suggest that DP will end up making less recursive calls. Can anyone confirm my answer or tell me why I'm wrong?

In terms of running time, the greedy algorithm is still going to be faster than the DP algorithm. DP will always produce the optimal solution regardless of values in V. Greedy, on the other hand, takes advantage of extra structure present in some value choices that allow it to effectively ignore possible ways of getting to the goal value. A coin system where the values are powers of p would allow the greedy algorithm to also consistently produce the optimal solution.


Order Mistake Definition in CLRS On page 53 or CLRS it has said :

  We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions
  $$\begin{align}
 O(g(n,m)) = \{  f(n,m)  : &\text{there exist positive constants }c,
 n_0,\text{  and } m_0 \\
   &\text{ such that } 0 \le  f(n,m) \le cg(n,m)\\
   &\text{ for all } n\ge n_0\text{ or } m \ge m_0 \}
\end{align}$$

I think this definition has a problem cause if  $n \ge n_0$ for some constant $n$ then we don't need to grow $m$! I feel something is Wrong! It must be the word "and" instead of "or" for example :
$f(x , y ) = x^2 + y^2$
$g_2(x,y) = x^2 + y$
$g_1(x,y) = x^2 + x*y$

by the definition $f(x,y)$ is $O(g_1(x,y))$ !
or even $f(x,y)$ is $O(g_2(x,y))$ ?

please guide me .

Well, there is not really a completely satisfying way to have the big-O Notation with multiple variables. Therefore CLRS present one way of a generalization. Putting an and instead of the or would give a new definition with other problems.

See this article for a discussion on the subject.


Classification of 2d arrays of outlines I am not experienced in machine learning but I have been looking at the Python toolklit scikit-learn. I have thousands of mammograms and I have written an algorithm to find the outline of the images. I have some cases where the outline of the mammogram is not correct. I would like to be able to take these thousands of outlines of mammograms that are arrays (of different lengths) of the x and y coordinates of the edge and to classify them. This would allow me to find the outliers and also possibly allow me to categorise the images. Does a clustering algorithm exists that would allow me to do this?

Edit 1:

Expected outline

Unwanted outline

It's hard for me to tell, but it sounds like you want to automatically detect the mammograms where the outline is incorrect.  I'm assuming the desired outline is the perimeter of some convex region in the image.

I'm not sure whether clustering is going to be the ideal approach here.  The first approach that comes to mind for me is something like this: we might want to build a classifier $C$ that accepts an image $I$ and a point $(x,y)$ as input and outputs either 0 or 1 according to whether $(x,y)$ is considered inside the region.  As features, you might include at least the following:

the grayscale intensity of $I(x,y)$, i.e., the darkness of the pixel at location $(x,y)$ in $I$.
the grayscale intensity of the neighborhood of $(x,y)$ in $I$.  This could be computed as the intensity of $I'(x,y)$, where $I'$ is the result of applying a Gaussian blur to $I$.
for each line $\ell$ that's part of the outline you were given for $I$, the value of $f(\ell,(x,y))$, where you define $f(\ell,(x,y))$ to be $1$ or $0$ depending on which side of $\ell$ the point $(x,y)$ is on.  For uniformity, you might choose a common orientation where one side of $\ell$ is towards the "inside" of the convex region given by the outline, and then let $f(\ell,(x,y))=1$ if $(x,y)$ is on that side of $\ell$ and let it be $0$ if $(x,y)$ is on the opposite side.
for each line $\ell'$ that's part of the edges you detected by applying an edge detector to $I$, the value of $f(\ell,(x,y))$.

Given these features, or some other suitable features of your choice, you might try to build a classifier $C$ by training on thousands of mammograms where you have ground truth (where you know what the correct outline is); for each such mammogram image $I$, you might pick a few hundred points $(x,y)$ at random, and then train on the resulting hundreds of thousands of inputs to $C$.  Since you know ground truth, you'll know what the desired/correct value for $C(I,(x,y))$ is, so you can apply supervised learning to try to infer a classifier $C$.

Once you've built a classifier $C$, you might then apply it to every new mammogram in your test set to try to infer the correct outline.

I don't know whether this will be effective in practice, nor whether it solves the problem you want to solve, but this is the first thing that springs to mind for me.


maximum weighted path(s) in a DAG Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current approach is doing the followings.

Add an extra node $S$ (source) and put directed edges to all starting nodes with zero weight. Similarly, add a sink node $T$ and put directed edges from all end nodes to $T$ with zero weight. Now, the problem is to find all maximum weighted paths between $S$ and $T$. Make the edge weights negative, i.e. weight $w$ becomes $-w$. Find the all single-source shortest path from $S$.

My question is, if there is any other efficient method to achieve this. The other thing is that, I need to find all maximum weighted paths if there exists more than one such paths. How can I find all maximum weighted paths efficiently?

Does maximum flow algorithm help?

Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe:

Negating edge weights and running a DAG-Shortest-Path algorithm.

In your case we could implement it similar to the following (transcribed mostly from CLRS 24.2) assuming input is an adjacency list:

0.  Max-Weight-Paths(Graph G(E, V)):
1.    add Super-Source S, and Super-Sink T // takes O(V + E)
2.    negate all edge weights              // takes O(V + E)
3.    topological sort G.V                 // takes O(V + E)
4.    for each vertex u in sorted order:
5.      for each vertex v in G.adj[u]:
6.        Relax(u, v)                      // 4-6 takes O(V + E)

Now for returning all max weight paths we can simply modify the relaxation step (6) a little bit. Instead of only containing a back pointer to one parent, we can maintain a linked list of back pointers to all parents of equal total distance like so:

0.  Relax(Vertex u, Vertex v):
1.    if distance(v) > distance(u) + w(u, v):
2.      distance(v) = distance(u) + w(u, v)
3.      parents(v) = {u}
4.    elif distance(v) == distance(u) + w(u, v):
5.      add u to parents(v)

Assuming parents(v) is maintained as a list, the Relax step still takes $O(1)$.

Then in the end you can return all max weight paths by starting at the sink T and traversing back up through parents(T) an so on. This traversal will return a DAG itself if multiple max weight paths exist. So just be smart about the traversal and the whole thing should take $O(V + E)$.

Edit, when I say be smart about the returning traversal, keep in mind a bad case scenario, something like this where all edge weights are equal:

There would technically be $6^2$ max weight paths, you could expand this example to get graphs with very large amounts of max weight paths due to combinatorics. So it might be more useful to return the DAG of max-weight paths rather than each individual. Although if you must return individual paths then you might be out of luck, because there are a lot of possibilities.


Complexity class of Determining Hamiltonian cycle I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ?

1) Graph is undirected , and  every node has degree two.

Any help will be appreciated. Thanks.

If every node has degree two, then the test for a Hamiltonian cycle boils down to testing connectivity, since the graph must then consist of 0 or more disconnected cycles.

The algorithm is as follows:

Choose a starting node v
marked[v] = true
x := v
while x has an unmarked neighbour u
    x := u
    marked[u] = true
if all nodes in the graph are marked, return true, else return false

Suppose we see $v_1 \cdots v_n$ in this process. Since each node has degree 2, we only stop when we see a node with both its neighbors marked, so $v_1 \cdots v_n$ is a cycle in the graph. Since we see two edges from each $v_i$, there can be no other nodes connected to any $v_i$ that are unmarked. Thus, either $v_1 \cdots v_n$ is all nodes in the graph, and there is a cycle, or there is another connected component, and there is not a cycle.

Clearly this test is linear time, so the problem is in $P$.


How to Trace Path in Proof that Regular Languages are Closed Under Reversal I'm self studying automata theory and I need help with proving that regular languages are closed under reversal.

I have a basic proof, but am unsure about last statement in my proof. Is this sufficient? Could you help me explain why it works? Is it rigorous enough?

Problem:
For any string $w=w_1w_2\cdots w_n$, the reverse of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order, $w_n\cdots w_2w_1$. For any language $A$, let $A^\mathcal{R} = \{w^\mathcal{R} | w \in A \}$. Show that if $A$ is regular, so is $A^\mathcal{R}$.

Proof:
Let $N = (Q, \Sigma, \delta, q_0, F)$ be an DFA recognizing $A$. We construct an NFA $M = (Q', \Sigma, \delta', q_0', F')$. Let $Q' = \mathcal{P}(Q) \cup \{q'_0\}$. For this NFA, $q'_0$ is a new start state. Let $F' = \{q_0\}$, the start state of $N$.

Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$,
\begin{equation*}
\delta'(q,a)  = \begin{cases}
F & q = q'_0, a = \epsilon\\
q'_0 & q = q'_0, a \neq \epsilon\\
\{ x |  x \in Q\ and\ \delta(x,a) = q \}&q \neq q'_0
\end{cases}
\end{equation*}

For any $w \in \Sigma^*$, there is a path from $q_0$ to $q_{acc} \in F$ in $N$ if there is a path following $w^\mathcal{R}$ from $q'_0$ to $q_0$. Therefore, $w^\mathcal{R} \in A^\mathcal{R}$ iff $w \in A$.

Whether a proof is sufficiently detailed is in part a question of taste. Your last statement is very general and with little detail. A more detailed argumentation could be like this:

Let the path from $q_0$ to $q_{acc}$ go through the sequence of states $q_0 -> q_1 -> ... -> q_{n-2} -> q_{n-1} -> q_{acc}$.
Transition $q_{n-1} -> q_{acc}$ reads the letter $w[n]$ (w has length n) which is equal to $w^R[1]$. According to the third clause in the definition of $\delta'$ there is a transition $\delta'(q_{acc},w[1]) = q_{n-1}$ which can start a path for $w^R$ in M.
Now you can continue by induction or by simply stating that the same is true for every transition in the path for $w$. At any rate, since your construction is on the level of transitions, your argumentation should go down to the level of transitions somewhere and not stop at the level of paths.


Dynamic programming to find the least possible balance of a full binary tree I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.

I need to find the least possible balance of any full binary tree with $x_1,x_2,\cdots,x_n$ as the weights of its leaves. I don't need to output the tree, just the value.

I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node:

For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is:

I am looking for some hints as to what the sub-problems might be.

You should think about how your binary tree can be arranged. For each tree you have some nodes $x_1,\dots,x_k$ to the left and some $x_{k+1}, \dots, x_n$ to the right of the root. Now, the best possible imbalance for that root will be the arrangement that gives you the smaller ratio. So, you have to figure out a way of doing this evaluation in every internal node of your tree (considering the subtree rooted there). Another tip is to consider growing your tree while preserving the minimum imbalance. The "matrix-chain" problem is quite similar to this one, so you should take a look at it too. Good luck.


Confused about Telescoping/Domain Transformation Question I have been working on the following domain transformation problem however, I am stuck on how to continue to receive the solution. I would greatly appreciate it if someone can explain how I can complete this:

T(1) = 0

T(n) = T(n/2) + n^2

The following is what I have so far:


What does Dijkstra's algorithm become, when you replace path cost with edge cost? Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are positive and distinct). Nodes are never re-visited. What can we say about the resultant paths?
One obvious result is that they are minimax paths (that is, the maximum edge cost of a path found is the minimum of that of any path to that goal). But the condition seems to be stronger than that: An edge pair will tend to have a large number of tied minimax paths (since only one edge really constrains the path), but this algorithm seems to robustly prefer paths with fewer high-cost edges.
What I think is going on is, the edge costs for the found path from a to b, if sorted in descending order, produce a sequence that is the lexicographic minimum over all paths from a to b. In a sense, it's more "strongly" minimax, with ties broken by the second-highest-cost edge, and so on. But I can't prove this to myself, even informally.
Is this a known algorithm? Does it actually have that property?

The following answer assumes that you know the working of Dijkstra's algorithm. Here, we are working with a variant of Dijkstra's algorithm as mentioned in the question. Hope it will be helpful.
Suppose $s$ is the source vertex and $v$ be any vertex in $V$.
Statement: Dijkstra's algorithm outputs the lexicographically smallest path from $s$ to $v$ if all the edge weights in the graph are positive and distinct.
Proof: Suppose $p = (s,u_{1},\dotsc,u_{q},v)$ is the lexicographically smallest path from $s$ to $v$. For the sake of contradiction, assume that the algorithm outputs $p' = (s,w_{1},\dotsc,w_{r},v)$ and $p' \neq p$. Let $(w_{i},w_{i+1})$ be an edge in $p'$ that act as a tie breaker when we compare the orderings of $p$ and $p'$. In other words, every edges in $p'$ that has the higher weight than the weight of $(w_{i},w_{i+1})$ does also appears in $p$. Let $E_{h}$ be the set of edges in $p'$ that have weight higher than the weight of $(w_{i},w_{i+1})$.

Claim: There is an edge $e$ in $p$ such that $e \notin E_{h}$ and $weight(e) > weight(w_{i},w_{i+1})$.
Proof: I will assume that you are familiar with the fact that the algorithm maintains a cut $(S, V \setminus S)$ such that all the vertices in $S$ are declared visited and the shortest path to them has been found. Now, suppose that just before the algorithm adds $(w_{i},w_{i+1})$, the cut is $(S_{i}, V \setminus S_{i})$. It implies that for all $j \leq i$, $w_{j} \in S_{i}$ and for all $j > i$, $w_{j} \in V \setminus S_{i}$. Also, $s \in S_{}$ and $v \in V \setminus S_{i}$. Now, consider path $p$. Since $p$ is a path from $s$ to $v$, there is an edge $e$ in $p$ that is also present in the cut $(S_{i}, V \setminus S_{i})$. Firstly, we will show that $e$ does not belongs to $p'$. For the sake of contradiction assume that $e$ also belongs to $p'$. Therefore, let us define $e$ to $(w_{t},w_{t+1}) \in p'$.
Case $1$:  $e$ appears before $(w_{i},w_{i+1})$ in the path sequence
$p'$. It means $w_{t}$ and $w_{t+1}$ belongs to $S_{i}$. It
contradicts that $(w_{t},w_{t+1})$ belongs to the cut $(S_{i},V \setminus S_{i})$.
Case $2$: $e$ appears after $(w_{i},w_{i+1})$ in the path sequence
$p'$. Let $(S_{t-1},V \setminus S_{t-1})$ be the cut just before
$(w_{t-1},w_{t})$ was added to the solution. We know that  $w_{t-1} \in S_{t-1}$ and also $w_{t} \in S_{i} \subset S_{t-1}$. Therefore, it
contradicts that $(w_{t-1},w_{t})$ belongs to the cut
$(S_{t-1},V\setminus S_{t-1})$.
From the above two cases, we can say that $e \notin p'$ and therefore $e \notin E_{h}$.
Also, note that the edges $e$ and $(w_{i},w_{i+1})$ both belongs to the cut $(S_{i},V \setminus S_{i})$, and the algorithm chooses $(w_{i},w_{i+1})$ over $e$. Therefore, the weight of $e$ is greater than the weight of $(w_{i},w_{i+1})$. This
proves the claim.

The above claim implies that $p'$ is lexicographically smaller than $p$. Therefore $p = p'$. It contradicts our initial assumtion that $p \neq p'$. Hence proved.


Is Half - Palindrome subset of a context-free language context-free? Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a DFA. Is it possible to create a PDA here as well? I am stuck on this or even if there is a counter example?

Let $L=\{a^n b^n c^m d d c^k b^k a^m\}$, then $L$ is context-free. I claim
$L'=\{a^n b^n c^n d\}$ which is not context-free.

Suppose $x\in L'$. Then $x$ must be of the form $a^i b^j c^k d$. Then $x x^R = a^i b^j c^k d d c^k b^j a^i \in L$, which means that $i=j=k$. Conversely, it's clear that $\{a^n b^n c^n d\} \subseteq L'$.


DFS timestamps, how important are they in pathfinding? I am writing a work on pathfinding algorithms and DFS is a part of it. And the book Introduction to Algorithms and many another websites mention timestamps. And they say timestamps could be used for others algorithms using DFS, topological sorting and etc.

So for pathfinding these timestamps dont really matter?

Thank you for helping.

Here is the section from the book mentioning timestamps:
Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex has two timestamps: the first timestamp :d records when is first discovered (and grayed), and the second timestamp :f records when the search finishes examining ’s adjacency list (and blackens )

Correct.  If you just want to check which nodes are reachable, or find any path from $s$ to $t$, you don't need the timestamps (the pre and post values).


Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is it true for any problem on graph which has such a greedy algorithm.

Yes, for every simple graph problem I can think of it's pretty simple to come up with some greedy strategy that gives the optimum if you order your vertices correctly.
Take for example Independent Set. The simplest strategy imaginable for finding an independent set is to fix some ordering $(v_1,\ldots,v_n)$ on the vertices of your graph $G$, putting vertex $v_i$ into your independent set $I$ if it has no neighbors among the vertices that have been put into $I$ so far. This always leads to a maximal independent set, and it's easy to see that every maximal independent set (including those of maximum size) can be generated this way, by just taking an ordering where evey vertex in the set comes before every vertex not in the set.
This strategy also works for other vertex subset problems like Feedback Vertex Set or Dominating Set. Unfortunately, it is pretty uninteresting and unlikely to give much insight into these problems. It's potentially more interesting when such strategies can be devised for more complex problems like Treewidth.


Proof that if a function is computable with standard programs it is computable with Turing Machines Where can i find a proof related to the subject mentioned?

To write a proof, you need to define your claim precisely. "Standard programs" is not a precise term.

However, if we define "standard program" to be, for example, any valid program in the C programming language, then you can write a proof. To prove this, you describe how to simulate any valid C-program with a Turing machine, or describe a "compiler" that takes a C-program and outputs an equivalent Turing machine. Since the C-language has many features, the proof will be long and tedious, but it is doable. I don't know if anybody has gone through the trouble to write a full formal proof.


Variation of MAX 3-SAT Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)?

I'm trying to think of an efficient algorithm to solve this problem. This is sort of a variation of the MAX 3-SAT, but with a fixed k. If we have m clauses, checking naively would get $\binom{m}{k}$ comparisons, but this seems factorial (if we approximate with Sterling's formula, exponential) complexity.

What could be an efficient way to check this? I must be missing something. Thanks.

This is the decision version of MAX-3SAT, which is known to be NP-complete. In particular, if you choose $k = m$ then you get the classical NP-complete problem 3SAT.


Is it possible to design a programming task that is unsolvable? Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least one of those outputs is incorrect.

That is, the program need not terminate for all outputs, but the outputs it does generate must all be correct, and there must be an infinite number of inputs for which it will terminate.

Not too sure about this, but my intuition says that the question may be related to the Halting problem/Turing machines.

As an example, the halting problem, (as far as I understand) does not meet this requirement, as one could run the input program, and output "terminated" if it terminates. If the input program never terminates, nor does the solution, so it never generates an incorrect output.

A simplified example can be the following:

$$T( n ) = \begin{cases}
\max \{ M(n) \mid |M| \leq n \} + 1 & \text{if such max exists}\\
0 &\text{otherwise.}
\end{cases}$$

In other words the "unprogrammable" (uncomputable) task $T$ (or better uncomputable function $T$) simply picks all programs $M$ of size at most $n$ as "input" and outputs the maximum value that they output on input $n$, plus 1.

Given a program $M_i$ that satisfies your assumption ( ... which produce an answer in finite time for a (countably) infinite number of inputs ...), there will always be an $x_0$ such that $|M_i| < x_0$ and $M_i$ on $x_0$ halts, and we have:

$$M_i(x_0) \leq \max \{ M(x_0) \mid |M| \leq x_0 \} < T(x_0)\,.$$


The optimal way to reverse engineer a binary classification problem I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.

In a scenario very similar to popular binary classification machine learning contests, competitors are required to submit their answers to the test set containing N data points. The accuracy of the submission will be announced. The competitors can then submit a new answer, and the new accuracy will always be published, no matter improved or not.

If the competitor has no information about the test set at all, what is the optimal way (in the sense that the least submissions are needed) to crack the challenge?

Your problem is tackled in Vaishampayan, Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle. Vaishampayan relates this problem to one considered in Lev and Yuster, On the size of dissociated bases, and the upshot (if I understand things correctly) is that a random test set of size $O(N/\log N)$ (for an appropriate hidden constant) would do if you don't care about carrying the decoding procedure efficiently. Vaishampayan describes a more structured solution using $o(N)$ tests which can be implemented efficiently.


Minimum number of states in the DFA I am trying to solve following problem but unable to solve this. Can anyone tell me how to approach this kind of problems where it is not easy to make DFA.

  The minimum number of states required to construct a DFA that recognizes the language of strings over the alphabet ${a,b}$ whose tenth symbol from the right end is $a$?

I tried converting R.E of the language which is $(a+b)^*a(a+b)^9$ into DFA but couldn't convert. Can anyone convert this into DFA or provide a $generalized$ solution when it is $n^{th}$ symbol from the right hand of the string?

Let $L_n$ consist of all words over $\{a,b\}$ such that the $n$th symbol from the right is $a$. The minimum number of states in a DFA accepting $L_n$ is $2^n$.

First, let us construct a DFA with so many states. The states of the DFA correspond to strings of length $n$ over $\{a,b\}$. The starting state is $b^n$. When in state $\sigma_1\ldots \sigma_n$ and reading $\sigma$, we move to state $\sigma_2 \ldots \sigma_n \sigma$. A state is accepting if the first symbol is $a$.

Second, we use the Myhill–Nerode theorem to show that $2^n$ states are necessary. We claim that all words of length $n$ are pairwise inequivalent. Indeed, let $x \neq y$ be words of length $n$. Then $x_i \neq y_i$ for some $i$, say $x_i = a$ and $y_i = b$. This implies that $x b^{i-1} \in L_n$ whereas $y b^{i-1} \notin L_n$, showing that $x,y$ are inequivalent modulo $L_n$.


Asymptotic calculation check for triple-nested for-loops I have the following repetition structure:

sum = 0
for (i = 0; i < n; i++) {
   for (j = 0; j < i*i; j++) {
      for (k = 0; k < j; k++) {
         sum++
      }
   }
}

By the following, I have reasoned the runtime of this structure to be in $O(n^7)$ :

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2}(\sum_{k=1}^{j} k))$

$= \sum_{i=1}^{n}(\sum_{j=1}^{i^2}(\frac{j^2+j}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\sum_{j=1}^{i^2}j^2 + \sum_{j=1}^{i^2}j))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\frac{i^2(i^2+1)(2i^2+1)}{6} + \frac{i^2(i^2+1)}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n} \frac{2i^6+3i^4+i^2}{6} + \sum_{i=1}^{n} \frac{i^4+i^2}{2})$

$= \frac{1}{2} (\frac{1}{3} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{6} \sum_{i=1}^{n} i^2 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{2} \sum_{i=1}^{n} i^2)$

$=\frac{1}{6} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 +\frac{1}{3} \sum_{i=1}^{n} i^2$

$\approx \frac{n^7}{42} + \frac{n^5}{10} + \frac{n^3}{9}$

$\therefore \text{runtime} \in O(n^7)$

The approximation at the end comes from the rule:

$\sum_{i=1}^{n} i^k \approx \frac{n^{k+1}}{k+1}$

Is this correct? I'm fairly confident that it is but some of the results that I've gotten from running the structure in JMH (Java Micro-Benchmarking Harness) don't really reflect this result so I just want to confirm.

As Yuval Filmus and gnasher729 have pointed out my original equation for the repetition structure is indeed wrong. I believe this to be the true correct answer:

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2} j)$

$= \sum_{i=1}^{n} (\frac{i^4+i^2}{2})$

$= \frac{1}{2} \sum_{i=1}^{n}i^4 + \frac{1}{2} \sum_{i=1}^{n}i^2$

$\approx \frac{n^5}{10} + \frac{n^3}{6}$

$\therefore runtime \in O(n^5)$


Why can't we use a hash tables for collision resolving in hash tables? To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can't we use another hash table allocated to each slot of the primary hash table?

The method you propose is, as far as I know, the historically first one for "perfect" hashing in linear space. In perfect hashing, lookup takes $O(1)$ time in the worst-case. (Recall that in most simple hash tables, lookup takes $O(1)$ time only in expectation.)

The idea is to use chaining (rather than open addressing), but make each chain a hash table of size $\Omega(m^2)$ where $m$ is the number of items in the bucket.

This is sometimes called "FKS", after the initials of the inventors. Here are some freely available resources:

"Universal and Perfect Hashing" by Avrim Blum
"Storing a Sparse Table with $O(1)$ Worst Case Access Time" by Fredman et al.
"Dynamic perfect hashing" (Wikipedia) supports dynamic insertion and deletion with expected amortized $O(1)$ time, in addition to (like other perfect hashing algorithms) $O(1)$ worst-case lookup time.


Determine whether a variable has positive influence in Boolean function Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$.
Given a function $f$ presented in $\text{CNF}$, and a coordinate, are there any known methods for determine if the coordinate has positive influence?

Given a CNF $\phi$ and a variable $x_i$, deciding whether $\phi$ depends on $x_i$ is NP-complete. It is clearly in NP: all we need to verify that $\phi$ depends on $x_i$ is two inputs different on $x_i$ on which $\phi$ evaluates to different values.

In the other direction, we reduce from SAT. Given a CNF $\psi = C_1 \land \cdots \land C_m$, let $x$ be a new variable and consider the CNF $\phi = \psi \land x$. If $\psi$ is satisfiable then $\phi$ depends on $x$, since substituting such a satisfying assignment reduces $\phi$ to $x$. If $\psi$ is not satisfiable then $\phi$ is always false, and in particular doesn't depend on $x$.


Can all languages have semantic and logical errors? I have been reading about PHP and many authors mention semantic and logical errors separately. As an example of a semantic error, they give a function called with incorrect number of parameters: this will not be caught by the parser, but will throw an error when run.

Yet in languages such as C++, this will be caught by the compiler. I would say that it's a syntax error then. What is the difference then between a semantic and a logical error?

For example, in How to think like a computer scientist, the author uses "logic error" and "semantic error" interchangeably. On the other hand, in the Visual Basic .NET. Primer Plus, "logic error" is separated from "semantic error".

I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't have a precise universally accepted definition, and so people are using the terminology slightly differently. I wouldn't get hung up on it.

Both "logic" and "semantic" imply something to do with the meaning of the programming, so it would be easy to regard them as the same.

If I were to draw a distinction, a useful one I can see is that a logic error is when the program ends up meaning something other than what the programmer intended, and a semantic error is when the program ends up not meaning anything (consistent) at all. With those definitions, you could either regard logic errors as a superset of semantic errors, or that logic errors exclude errors that result in the program being inconsistent.

For example, the following pseudo code contains only a logic error:

x = read_number_from_user("x: ")
y = read_number_from_user("x: ")
print("The product of x and y is: ")
print(stringify(x + y))

The meaning of this program (taken solely as-is and without considering the programmer's intent) is perfectly straightforward and consistent. But it doesn't mean what the programmer intended it to mean.

OTOH, the following pseudo code contains a semantic error:

name = read_string_from_user("What is your name?")
print(name + 1)

At least, it does if we assume that adding a string and a number doesn't mean anything. In languages like PHP it does mean something, and this wouldn't be a semantic error.

Your example of a semantic error in PHP as calling a function with an incorrect number of parameters is actually interesting, because it's debatable whether you should call that a semantic error (with the definition I'm using).

Functions are defined dynamically at runtime in PHP. So calling a function with an incorrect number of parameters could be regarded as a logic error; perhaps the wrong include statement was executed, causing a different function with the same name to be included than the one the call was supposed to go to. Even if not, calling a function with the wrong number of arguments does mean something; it means lookup the function with this name and pass it these arguments. It's only operationally at runtime that it turns out the interpreter is unable to carry out those requests; just as x / y means something, but may be impossible to carry out if y happens to be 0 at runtime.

Ultimately, how you classify errors using a distinction like the one I'm making here between logic and semantic errors (even if it's not exactly the one I'm making) depends very much on the particular language you're talking about and how you assign meaning to programs in the language. Most commonly used languages do not have a standard way of assigning meaning to their programs, which means that everyone uses a slightly different way of doing so (though everyone's interpretation would agree very closely on almost all operational effects), and would analyse the "logical" vs "semantic" distinction differently.

Another similar way of looking at it would be to say that semantic errors are whatever causes the programming language to reject the program as invalid (apart from syntactic errors, though again you could call those a subset of semantic errors if you want). If the programming language accepts the program then it means something, and if it fails at runtime then that is the result of a logic error. This is pretty much assigning the programming language implementation (interpreter, compiler + runtime system, whatever) as the definition of what programs mean.


Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers I want an algorithm to list all possible ways to map a series of integers $M = \{1,2,3,...,m\}$ to another series of integers $N = \{1,2,3,...,n\}$ where $m > n$, subject to the constraint that only contiguous integers in $M$ map to the same integer in $N$.

E.g.: 5 -> 2:
  (1, 2, 3, 4), (5)
  (1), (2, 3, 4, 5)
  (1, 2, 3), (4, 5)
  (1, 2), (3, 4, 5)

This seems like it should be a standard problem with a well known solution, but I can't find it.

To clarify, I am not looking for the total number of solutions, but for pseudocode or the name of a corresponding algorithm to exhaustively list all solutions.

Suppose that the image of your mapping has size $k$. This implies a division of $\{1,\ldots,M\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus
$$
 \sum_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}.
$$
Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.


How to prove computational completeness of a variant of P system I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove its computational completeness.

I also know that in order to prove computational completeness many research papers normally prove the equivalence of their variants of P system with variants of formal languages (e.g. context-free, context sensitive languages, Turing machines etc.), those of which are already known to be computationally complete.

My question is how exactly can I prove equivalence of a variant of P system with a formal language?

When you have studied a lot of papers, as you say, then you must have seen how it works. You prove a system to be computationally complete by showing how your new system is able to simulate a Turing machine. Instead of a Turing machine you can use any computational model that in itself is computationally complete, like counter automata (register machines) for example.

In P system theory there are many variants, some work on strings, other on numbers. The model you choose to simulate ideally must match that domain.

So, you do not use "formal language" as such, but only the models studied by formal language theory.


In predicate logic, is the "environment" only needed when free variables are present? Suppose there exist no free variables in a given predicate logic formula. Is then a model alone sufficient to fully interpret the formula and make inferences? Don't we need an environment or variable lookup table (as often mentioned)?

It is not so that the model alone allows you to make inferences and that you don't need an environment at all; it is rather that, if no free variables occur, then you may as well start with an empty environment. Quantifiers modify the current environment, so you do need one. However, if there are no free variables around, then any of the assignments in the initial environment will not be used, and all variable values will come from the quantifiers anyway. Therefore, by trimming unnecessary assignments in the initial environment, you get an empty one.


How many queries does it take to find the best flight? I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and on a certain date) the search engine returns the cheapest flight in this subset. My goal using the search engine, however, is not so simple as restricting to a subset and finding the cheapest flight. Rather, I mentally place a certain dollar value on how much I am willing to pay extra for various options: e.g., willing to pay \$20 extra for nonstop, willing to pay \$50 extra for closer airport. I want to find the cheapest flight after these dollar values are taken into account.

This raises an algorithmic question: how many queries to the search engine does it take to find the best flight? We can formulate this as the following search problem:

$X$ is a search space (set of flights);
$f: X \to \mathbb{R}^+$ is an unknown price function, where $f(x)$ is the price of $x$;
$g: X \to \mathbb{R}^+$ is a known additional cost to us, which we assume is a weighted sum of $k$ known indicator functions:
$$
g(x) = \alpha_1 [x \in A_1]
+ \alpha_2 [x \in A_2] + \cdots + \alpha_k [x \in A_k],
$$
where $\alpha_i \ge 0$ are weights and $[x \in A] = \begin{cases} 1 &\text{if } x \in A \\ 0 &\text{otherwise} \end{cases}$ is the Iverson bracket.

The problem: Determine $\min_{x \in X} (f(x) + g(x))$, using queries to an oracle which, on input any subset $X' \subseteq X$, returns $\min_{x \in X'} f(x)$ and $\arg\min_{x \in X'} f(x)$.

Question 1: As a function of $k$, how many queries to the oracle are needed in the worst case?

It can easily be done in $2^k$ queries: the sets $A_1, A_2, \ldots, A_k$ collectively partition $X$ into $2^k$ regions, so we can query on each subset. Is there a better algorithm in general?

Question 2: Assume that the actual minimum of $f(x) + g(x)$ falls into at most $k' \ll k$ of the indicator sets $A_i$ (so I'm not going to pay too much extra). As a function of $k$ and $k'$, how many queries to the oracle are now needed?

There are problem parameters where you need $2^k$ queries in the worst case.  I'll prove this by giving an explicit example of an instance where you need $2^k$ queries.

Suppose $X = \{0,1\}^k$ and $A_i = \{x \in X : x_i = 1\}$ (this is without loss of generality in any case).  Suppose $\alpha_i = 1/2^i$.  Pick a single value $x^* \in X$, and define

$$f(x) = 1 - g(x) - 2^{-k-1} [x = x^*].$$

To any query set $X'$ we can associate a single element $m(X') = \arg \max_{x \in X'} g(x)$.  Notice that the results of the query $X'$ depends only on $m(X')$, and there are $2^k$ possible values for $m(X')$.  Thus we can identify each query with the value of $m(X')$, so effectively there are only $2^k$ different queries (where I consider two queries different if their value of $m(\cdot)$ differs; formally, consider the equivalence relation induced by $m(\cdot)$, choose one canonical representative for each equivalence class, and from here on we will assume that each query is one of these $2^k$ canonical representatives).  Now I claim that out of these $2^k$ possible queries, there is only a single one that gives you any useful information about $x^*$.  In particular, the only thing you learn about $x^*$, when you query on the set $X'$, is whether $x^* = m(X')$ or not.  Why?  If $x^* = m(X')$, then the oracle will return $x^*$, and you can recognize that this has happened by looking at the value of $f$.  However, if $x^* \ne m(X')$, then the oracle will return $m(X')$ as well as the value of $f$ on that element, and that is something you could have computed on your own using your knowledge of $g$, so you have learned nothing about $x^*$ other than that it is different from $m(X')$.  Moreover, there is only a single (canonical) set $X'$ where $x^* = m(X')$.

So, you have a search space of size $2^k$, and each query only lets you test a single candidate for $x^*$.  It's like playing a game where I think of a secret number, and you can ask me questions like "is your number 17?" where you replace 17 with any number of your choice.  It's easy to see that this game will require $2^k$ guesses in the worst case, and $2^{k-1}$ guesses on average.

So for that setting of weights, you can't do any better than $2^k$ queries.

(As a generalization, for your Question 2, this will require ${k \choose k'}$ queries in the worst case.)

In contrast, there also exist choices of weights where this allows an efficient solution.  Consider the case where $\alpha_1=\cdots=\alpha_k=1$.  Then you can query on the subsets $X'_0 = \{x \in X : g(x) = 0\}$, $X'_1 = \{x \in X : g(x)=1\}$, .., $X'_k= \{x \in X : g(x)=k\}$.  Then, take the best of those results -- the one that has the smallest value of $f(x)+g(x)$.  After doing $k+1$ queries, this is guaranteed to find you the optimal solution to the problem.  As a generalization, if the set of sums $\{\sum_i c_i \alpha_i : c \in \{0,1\}^k\}$ has cardinality Q, then Q queries suffice to obtain the exact answer.

So, ultimately, the number of queries needed to the oracle depends on the weights.  There are some choices where this might require many queries, and other choices where very few queries suffice.

One nice thing is that you can approximate the optimal value to within an additive error of $\delta$ using $(\sum_i \alpha_i)/\delta$ queries.  In particular, query the subset $X' = \{x \in X : g(x) \le t\}$ for $t:=\delta,2\delta,3\delta,\dots,\sum_i \alpha_i$.  Take the best solution found over all of those queries, and that will be at most $\delta$ worse than the optimum.


How does a hard drive knows what bit is the beginning of of a byte/word? I'm guessing I could replace the words "hard drive" with "random access medium" but let's be more specific here. Also for the sake of this question, let's not consider SSDs. Just plain old hard-drives with heads and magnetic discs.

I'd guess that the hard drive doesn't care about things as bytes and receives instructions from the OS on about where to move it's head, but that'd assume that the OS has knowledge of sectors, cylinders or whatever physical properties of the drive and it's stored data so that doesn't feel right.

So, how does this work?

Simplified, the operating system sees disk storage as a randomly accessible set of sectors, each sector containing some fixed number of bytes.  The OS asks the disk controller for a sector using some standard protocol and it is the responsibility of the disk controller to retrieve the sector with the bits and bytes in the same order in which they were written.  The communication protocol (e.g. SCSI) specifies both bit and byte order for reads and writes so there is no space for confusion about where the data starts and stops.

Operating systems can and do take into account the characteristics of storage media for the sake of efficiency, such as existence of onboard cache, rotational delays, and head movement, but those things have no bearing on where bytes and sectors start.


Find smallest enclosing circle On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known radii and positions with respect to the origin. (It is possible that some smaller sub-circles are partially or entirely inside some larger sub-circles.)

The entire plane is gridded uniformly into pixels with sides being horizontal and vertical (along coordinate axes). The size of the pixels is fixed and known a priori but otherwise much smaller than the size of parent circle; there are on the order of few $\times 10^{5}$ pixels all over the parent circle.

$\sim 1\%$ of the area of the parent circle is colored in the form of a few clumps across the parent circle covering $\sim 10^{3}$ pixels.  These colored pixels are mostly inside sub-circles; all are entirely inside the parent circle. We are given the 2D Cartesian coordinates for (the centers of) all colored grids.

Each colored grid is associated with the smallest sub-circle that contains it.  If the pixel falls within multiple sub-circles, only the smallest of the circles should be chosen.

Finally, I would like to calculate the total number of colored grids associated with each sub-circle. Is there an efficient algorithm for this?

Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data.

Here is a simple approach.  Store all of the colored pixels in a quadtree.  Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle.  Query the quadtree data structure to find all points contained within that square.  For each such point, test whether it falls within the sub-circle.  If it does, mark that point as associated with that sub-circle, unless it is already associated with a smaller sub-circle.

I expect the running time of this approach will be approximately $O(n+m)$ where $n$ is the number of colored points and $m$ is the number of sub-circles (assuming there is not too much overlap among the sub-circles, which seems likely to be the case for the parameter settings you listed).  Thus, it should be very efficient.

You can alternatively replace the quadtree with any other data structure for 2D data, such as a k-d tree, though for the parameter sizes you mention, I expect that anything will already be quite fast and so it probably won't be necessary to worry too much about optimizing this as much as possible.


Variant of assignment problem This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to find an assignment matrix $A$ which is again an $n \times m$ binary matrix (contains ones and zeros) and if $A_{ij}$ is $1$ it shows $i$-th person from first group has assigned to $j$-th person of second group, and maximize $\displaystyle\sum_{i}\sum_{j} C_{ij}A_{ij}$, subject to following constraints:
$$
1)\;\; \forall i: \;\; \displaystyle\sum_{j} A_{ij} = 1 \\
2)\;\; \forall j: \;\; \displaystyle\sum_{i} A_{ij} \le 2
$$
how should I solve this problem?
*how should we solve if we have another matrix $D$ and we also want $\displaystyle\sum_{i} D_{ij}A_{ij} \le constant$ ?

You want to assign $n$ persons to $m$ groups, so that

Each person is assigned one group.
Each group is assigned at most two people.
For each possible person $i$ and group $j$ there is a score $C_{ij}$, and you want to maximize the sum of scores of all assignments.

If such an assignment is at all possible, then $n \leq 2m$.
Create an instance of the usual assignment problem (in which we are looking for a one-to-one correspondence between persons and groups) as follows:

There are $n$ real persons $1,\ldots,n$ and $2m-n$ dummy persons $n+1,\ldots,2m$.
There are $2m$ groups, composed of two copies of the original groups: $1,\ldots,m$ and $m+1,\ldots,2m$.
The costs $C'_{ij}$ of the instance are: for $i \in \{1,\ldots,n\}$ and $j \in \{1,\ldots,m\}$, define $C'_{ij} = C'_{i(j+m)} = C_{ij}$, and set all other costs to zero.

Every feasible solution of the original problem translates to a feasible solution of the new problem with identical cost, and vice versa.


P vs NP and can an oracle make P=EXPTIME? As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$.

I don't fully understand this logic. Diagnolization (Time Hierarchy Theorem) proves that $P \neq EXPTIME$. Does it therefore mean that there is no oracle $X$ that could ever make $P^X = EXPTIME^X$ ?

First let me try to be a bit more precise about your first sentence.  The reasoning you list shows that no relativizing proof can prove or disprove P=NP.  "Diagonalization" is a fuzzy concept, and depending on what you mean by it, might or might not relativize -- diagonalization proofs tend to relativize, but no guarantees.  So the oracle result rules out some/many kinds of diagonalization proofs, but maybe not all.  See, e.g., https://cstheory.stackexchange.com/q/6575/5038.

Second, let's discuss your final question.  Yes, it is indeed true that $P^X \ne EXPTIME^X$ for all $X$; there is no oracle $X$ that will make them equal.  I'll talk through why that is.  The standard way to prove $P \ne EXPTIME$ is to prove $TIME(p(n)) \ne TIME(p(n)^2)$ (the time hierarchy theorem), then notice that this implies $P \ne EXPTIME$ (since $TIME(2^n) \ne TIME(2^{2n})$, but $P \subseteq TIME(2^n)$ and $TIME(2^{2n}) \subseteq EXPTIME$).  The proof of $TIME(p(n)) \ne TIME(p(n)^2)$ uses diagonalization.  This proof does indeed relativize.  In particular, for all oracles $X$, we do indeed have $TIME^X(p(n)) \ne TIME^X(p(n)^2)$.  It follows that, for all oracles $X$, we have $P^X \ne EXPTIME^X$ (by the same argument as before).

See also: https://cstheory.stackexchange.com/q/8902/5038, https://cstheory.stackexchange.com/q/6575/5038.


Constructively deciding whether a decidable predicate holds universally I am trying to obtain the proof of the proposition:

$(\forall x \in \mathbb{N}, P(x)) \vee (\neg \forall x, P(x))$

given that the property $P$ is decidable for every $x \in \mathbb{N}$, i.e.

$\forall x \in \mathbb{N}, P(x) \vee \neg P(x)$

This is easy to prove (even without using the decidability of $P$) if I include the law of excluded middle, i.e.,

$\forall P, P \vee \neg P$.

However, I am trying to obtain a constructive proof for the same. Is the proposition true without including the law of excluded middle? If so, how do I prove it? This seemingly simple property is needed to prove something about a complex system, and I am trying to not use the law of excluded middle unless it's absolutely necessary.

The best I could come up with is the following:

$\forall y, (\forall x \le y, P(x)) \vee \neg (\forall x \le y, P(x))$

I do not know how to proceed beyond this (or if this is even useful).

Any help would be appreciated.

You are asking for a constructive proof of the Lesser limited principle of omniscience (LLPO), which states (in one of its forms) that for a decidable proposition $P$ on natural numbers
$$(\forall n \in \mathbb{N} \,.\, P(n)) \lor \lnot \forall n \in \mathbb{N} \,.\, P(n).$$
That's exactly your problem. It is well known that LLPO is not provable constructively.

Unless you have some further conditions on $P$ which you did not tell us about, you're stuck.


Fork() execution and number of processes If a process executes the following code

fork();
fork();
fork();

The total number of child processes created is given as 7 by a text book.
But how does that happen

fork generates 2 processes right? Are both the processes referred to as child processes? One process is the parent parent and one is the child right?
Even if both the processes are referred to as child processes,2*3=6? The main process is not a child process,how does the number 7 come into the picture.

Update:

Each fork call duplicate process, so after first call there are two of them. You may call the one with pid = 0, the master process (parent, top, original).

After that two processes are in the second line (second fork), executing it, there are four processes now. I have not seen such distinction, but you may at that point say that two of them are child processes.

After the final fork, there are eight processes altogether, according to your materials, the original process is called parent and the rest are childs.

To draw it properly you should create a tree, with two children after each fork, where in fact one of them is the original caller.


What counts as automatic program analysis? I'm trying to understand the definition of program analysis on Wikipedia:

  Program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness.

What is the meaning of "automatic" here?

Are parsers static analysis tools, since they will throw an error if they encounter syntactically invalid code?

Is running a program an example of dynamic analysis, since it will provide me with an output (though I still have to interpret it myself)?

What if I explicitly throw a this can't happen exception when the program reaches an invalid state?

What about using a debugger to pause execution?

There is no sharp formal definition.

"Static" denotes "before running the program".

"Dynamic" denotes "while running the program".

"Automatic" stands for "without the intervention of the user". For instance, Hoare logic can be used to prove program properties, but (at least in its basic form) it requires user-provided invariants. Abstract interpretation, instead, often results in a totally automatic analysis. Type checking is usually regarded as automatic, since the type checker does not (usually) ask the user to provide hints about, e.g., why a given expression has the given type.

Parsing is static, but it's such a preliminary stage that probably most people wouldn't consider as program analysis at all. If a text file does not respect the syntactic rules, it is not part of the programming language (a language being a set of strings, after all!), hence it is not even a program, hence parsing is not program analysis. I would not be very interested in the syntax errors reported by cc kitten.jpeg, for instance.

Observing the program when it is being run is definitely a "dynamic" approach. Using a debugger, observing fired exceptions fall in this category.


Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$? In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts on all inputs may use on any branch of its computation is $2^{O(f(n))}$. However, I don't see why such a machine couldn't run for an arbitrary (but finite) number of steps in one of its branches. For instance, consider the following linear space machine for deciding SAT: on input $\phi$ rewrite the contents of the first tape cell $2^{2^{n}}$ times, then evalaute $\phi$ on every possible truth assignment. This machine runs in linear space (since it doesn't need to visit anything beyond the second tape cell for the first part of its execution), but its run time exceeds $2^{O(n)}$.

Despite the similar titles, my question is not a duplicate of this one. The confusion in the linked question is about the constants that result from using an arbitrary alphabet. The author admits that they understand the $2^{O(f(n))}$ time bound for machines that use a binary alphabet (which is precisely what I don't get), and therefore none of the answers address my question.

Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in.  That means there are at most $|Q|\,f(n)\,|\Sigma|^{f(n)}$ different configurations for the machine.  If the machine runs for more steps than that, it must visit the same configuration twice.

For a moment, let's pretend the machine is deterministic. If it visits the same configuration twice, it will take exactly the same sequence of steps and visit a third time, and infinitely often, so it cannot terminate.  However, we know that it does terminate for all inputs.  Therefore, it runs for at most $|Q|\,f(n)\,|\Sigma|^{f(n)}=2^{O(f(n))}$ steps.

But, actually, the machine is nondeterministic. Still, if some computation path visits the same configuration twice, we know that there is a computation path in which, by making the same nondeterministic choices again, the machine reaches the configuration a third time, and so on. Since we're told that every computation path terminates, we know that no computation path visits the same configuration twice, so we're done as in the deterministic case.


Maxima of diagonals in a column wise and row wise sorted matrix Let $\{a_i\}$ and $\{b_i\}$ be non-decreasing sequences of non-negative integers.

How fast can one find
$$c_j=\max_{0 \leq i< j}\{a_i+b_{j-i-1}\}$$
for all $0\leq j\leq n-1$?

Naively, it takes $O(n^2)$ time, but I'm hoping monotonicity can help here.

It's easy to observe $\{c_i\}$ is also non-decreasing. If we consider the matrix $M$ where $M_{i,j} = a_i+b_j$, then it is a matrix sorted in both row and column direction, and we are searching for the maximum element in every diagonal.

However, if it's an arbitrary column wise and row wise sorted matrix, this problem require $\Omega(n^2)$ time.

Proof: Let all the numbers below the main diagonal be $\infty$. The elements in the $k$th diagonal are randomly numbers from $(k,k+1)$. Reading any entry provides no information for any other entry.

Edit: This problem is much harder than I anticipated. We can model this problem as a convolution problem over the semiring $(\min,+)$ (take the dual, search for min instead of max), and it can be solved in $O(\frac{n^2}{\log n})$ time according to a Ryan Williams's answer on mathoverflow. It doesn't use the information that the sequence is non-decreasing though.

Great question! "Distance Transforms of Sampled Functions", by Felzenszwalb and  Huttenlocher shows how to compute this in $O(n \lg n)$ time.

"Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2}{\frac{\lg^2 n}{(\lg \lg n)^3}}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision tree model.


Using humans as components to build a computer? Ok before I start I realise this is on the fringe of on-topic (I have read the Questions help for this site), particularly as this is not a real-world problem. However:

I cannot find anything relevant on Google
From a purist point of view surely it must fall within Computer Science?

In any case, if I have overstepped a boundary then I apologise and welcome the  Closure as I am an avid user of other SE sites so I understand the issues.

Caveats aside, here it is:
I have long wondered if it would be possible to build a functioning computing system, using humans as discrete logic components, to solve problems that individual humans could not solve in a practical timesscale. For example, imagine a number of humans stranded on an island without any machines, that needed to crunch some complex numbers to escape.

I imagine arranging people so that they receive inputs from other groups within the system, make simple decisions (perhaps binary decisions, perhaps not) and pass the outputs to other groups.

Then I imagine some kind of programming language could be developed to control the data and computation flow and the language could be used to solve complex problems without individuals understanding the overall problem.

So I guess the above is not an answerable question- but does anyone know of any research, books, papers or whatever on what it would take to achieve, what kinds of of problems could be addressed and potentially solved, what kind of control language could be deployed and how the architecture could be scaled up to handled more complex problems?

I suppose, in essence, I am looking for anything on "idealised" atomic (as in self contained) and standard computing units that could be arranged at will- I am just thinking in human terms.

I find the idea fascinating and alluring. I'd love to try it out one day and see what performance could be achieved! Sorry for the tags I have used, as I was searching the tags here I quickly became aware I have no idea of the correct terminology for what I am thinking, though I am sure it exists within the field...

Actually, until the 1950s the word computer was used to refer to a human who did arithmetic calculations.  One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with discrete logic components, but rather have each human perform multiple arithmetic operations and then coordinate their results (along with some error checking.)  How to organize these kinds of large computations may be covered in numerical methods books from the 1940s or early 1950s.

The first version of the Logic Theorist by Newell, Simon and Shaw was simulated using humans in 1956 (less expensive than computer time).  They later won a Turing Award for basic contributions to AI, the psychology of human cognition and list processing (the Logic Theorist may have been the first program to use linked-lists to represent data structures.)  And the experience influenced Simon's later ideas on emergent behavior (see his Sciences of the Artificial.)

As pointed out in the comments and other answers, there is now an emerging discipline of Human-Based Computation, where various incentives are used to get humans to do parts of a larger calculation, where those parts make good use of human problem solving or pattern recognition.  One example of this is reCaptcha, where users need to enter two words to prove that they are not a bot, one a distorted image that is used for the actual "proof" and the second an actual word from a scanned book, which is used to produce a digitized version of the book.  Another example is the Amazon Mechanical Turk where a business can outsource "microtasks" to human workers for small sums of money.  The mechanical turk has been used, for example, to collect annotations on 250,000 images for image processing research.  The key seems to be breaking the problem down into a pile of independent work items, with significant amounts of redundancy used to reduce errors.  (E.g., you assign the same work item to 2 different humans, and then if they provide conflicting answers you assign the work item to a third human to resolve the difference.)


Does an insecure router bypass the privacy guarantee of a VPN connection? If I have a router that has a vulnerability that allows an attacker to gain full control it, does using a VPN on the network with the said router prevent an attacker from being able to snoop on the connection?
In other words, does using a VPN secure the connection from a device to a router? And would a VPS make a difference in this scenario?

If you're talking about a VPN that extends to your PC/device, and similarly on the other side of the communications, and the insecure router somewhere in the path in between, then yes, an attacker should not be able to eavesdrop/snoop on the connection. The traffic would be encrypted and the attacker would not be able to understand it. This is one of the points of using the VPN in the first place. It creates a "virtual" private network over infrastructure (including routers) that may be insecure. If it doesn't even offer you this protection, then what is the point of using the VPN in the first place?
If you're talking about a site-to-site VPN, where traffic to/from your PC/device needs to get to/from the entry point of the VPN through, say, your office infrastructure, and if your office infrastructure is not otherwise secured, and this insecure router is part of that office infrastructure, then yes, an attacker may be able to eavesdrop/snoop, but even then it is not bypassing the privacy guarantee of the VPN, because the eavesdropping/snooping would be happening outside of the path that is protected by the VPN.


Algorithms for solving Flow game Lately I've been toying with an automatic solver for the Android/iPhone game Flow.

In this game, you start with several pairs of squares on a grid, and you have to connect each pair, without crossing the paths, and by using every square on the grid. Here's a simple 7x7 example (the hardest boards in the game are 11x13).

Beginning:

Finished:

In most cases, a few simple rules can all but solve the problem. For example, if a node only has one uncovered exit, it must extend that way, and if extending in a direction would make a part of the board unreachable, then that move is forbidden. But is there a more general way? I've been trying to figure out if it is a specific case of a general graph algorithm, perhaps some kind of Path Coloring.

Note that the game presents other variants of the problem, such as a hexagonal grid, and 'warps' that connect squares on opposite sides of the board. Also, as far as I can tell, there is only ever one correct solution. I'd also be interested in how they can generate the starting positions.

I suggest formulating this as an instance of SAT.

You can formulate this as an instance of SAT by thinking of it as trying to color each square in the grid with a color.  For each color, arbitrarily designate one of the two endpoints as the "starting position" for that color, and the other endpoint as the "ending position".  Define boolean variables $x_{i,j,c,k}$, with the intended meaning that $x_{i,j,c,k}$ is true if grid square $(i,j)$ is colored $c$ and is the $k$th square along the path from the starting position for $c$ to the ending position for $c$.

You can write down a boolean formula representing the constraints on the variables $x_{i,j,c,k}$ that must hold, for this to be a valid solution to the puzzle.  For instance:

If $x_{i,j,c,k}$ is true, then either $(i,j)$ must be the end position for color $c$, or else $x_{i',j',c,k+1}$ must be true for some square $(i',j')$ that is adjacent to $(i,j)$.  Moreover, this is true for exactly two squares (not more, not less), unless $(i,j)$ is the starting position, in which case it is true for exactly one square.
For each square $(i,j)$, exactly one of the $x_{i,j,c,k}$ is true.
If $(i,j)$ is the starting position for color $c$, $x_{i,j,c,0}$ is true.  If $(i,j)$ is the ending position for color $c$, one of $x_{i,j,c,k}$ must be true.

And so on.  This ensures that the solution to the formula contains a path that starts at the starting position for color $c$ and ends at the ending position.

Then, feel this boolean formula to an off-the-shelf SAT solver and ask it to find a solution.

This may be an effective solution for the puzzle sizes you mention. I expect it may be more effective than trying to write your own custom rules, as SAT solvers embody many clever strategies built up over decades of research to try to find solutions for these kinds of combinatorial questions.  At least, it should be pretty easy to implement in just a few hours and see how well it works.

Apparently, this puzzle is NP-hard, so you should not expect to find a polynomial-time solution.  This suggests to me that a SAT solver might be a reasonable approach.


Question about system calls I had read about the various functionalities of system calls recently in one of my coursebooks and about how they are used to allocate memory for new processes. The book didn't specify whether it was possible to combine multiple memory allocation requests within a single system call.
So I asked one of my teachers and they said that it was indeed possible.
I feel that this would probably decrease the system's performance in some way but I cannot seem to give a concrete reason for the same.

Could someone explain why the performance drops in this case?

Thank you for your time.

In a standard operating system like Unix, no.  You can't directly make multiple requests.  But, you can make one big request for a lot of memory.  The system call lets you request a certain amount of memory, and you choose how much to request.

In practice your program doesn't make that system call every time you want to allocate memory. Instead, you have a standard library function, such as malloc(), which has a pool of available memory.  When you call malloc(), it selects a region of available memory and allocates that to the caller, and keeps track that it has been allocated.  When the available memory runs out, then it uses a system call to ask the operating system for a bunch more memory.  So, it might only need to invoke the system call infrequently, even if you call malloc() a lot.

See https://en.wikipedia.org/wiki/Memory_management#DYNAMIC, https://en.wikipedia.org/wiki/Sbrk, https://en.wikipedia.org/wiki/C_dynamic_memory_allocation, https://en.wikipedia.org/wiki/C_dynamic_memory_allocation.


Do ‘unspoofable’ email protocols exist? Been getting a lot more spam lately and this question came to mind.
We already use SSL certificates to authenticate websites, can we do something similar for email?

If so, why do I still receive spoofed emails?

There are several protocols actually:

SPF Sender Policy Framework is used to verify that the e-mail address used to send the message is valid e.g. if the sender had rights to use the given domain.
Recipients can verify this by checking the ips of the agent dropping the mail against the allowed ips listed in the domain DNS records.
DKIM DomainKeys Identified Mail is used to verify that a given message hasn't been tampered in transit.  Recipients can verify this using the public key of a given domain along with the signature included in DKIM signed e-mails.

These are actively used in SPAM filtering.  You can see it in action by looking at the headers of most e-mails today.  You can look for the headers: Authentication-Results, DKIM-Signature, Received-SPF.


The intersection of 2 CFL I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$.
I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is to the $n$ and not to the $m$ or something else?
Thank you in advance.

The set $A$ cointains all the strings on the alphabet $\{a,b,c\}$ starting with $a$, ending with $c$ and with the same number of $b$s and $c$s. Similarly, $B$ is made by strings on the same alphabet, starting with $a$, ending with $c$ and with the same number of $a$s and $b$s.
So the intersection $A\cap B$ simply cointains all the strings on the alphabet $\{a,b,c\}$ starting with $a$, ending with $c$, with the same number of $b$s and $c$s and the same number of $a$s and $b$s. By the transitivity of equality (I mean, if $x=y$ and $y=z$ then $x=z$, where $x$, $y$ and $z$ are the numbers of $b$s, $c$s and $a$s in a string), you can express these last two condition by saying that the number of $a$s, $b$s and $c$s is the same, i.e., that the strings in $A\cap B$ are of the form $a^n b^n c^n$ for some natural number $n$ (of course here you can use the letter $m$, or any other letter you prefer, instead of $n$).


Is my proof for a context free language correct? Same number of a's as b's I have the following grammar G:
$$
\begin{align*}
&S \to aB|bA \\
&A \to a|aS|bAA \\
&B \to b|bS|aBB
\end{align*}
$$

I am going to prove that this language L(G) consists of words with the same number of a's and b's by strong induction.

Inductive hypothesis: $S$ produces $m$ $a$'s and $m$ $b$'s, $A$ produces $m+1$ $a$'s and $m$ $b$'s, $B$ produces $m$ $a$'s and $m+1$ $b$'s for some integer $m$.

Base: The smallest string produced by $S$ is $ab$ or $ba$. The smallest string produced by $A$ and $B$ is $a$ and $b$ respectively. All three satisfy the IH.

Induction: Assume the inductive hypothesis is satisfied for all strings of length $k$ or less.

For strings of length $k+1$:

(1). $A\to aS$; then $S$ inductively derived a string of length $k-1$ with same number of $a$'s as $b$'s. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $a$ in $aS$ and we get a string of length $k+1$ with same number of $a$'s as $b$'s.

(2). $A\to bAA$; then each $A$ on the right hand side has one more $a$ than $b$. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $b$ in $bAA$ and we get a string of length $k+1$ with the same number of $a$'s as $b$'s.

Can I continue for $B\to bS$ and $B\to aBB$? Am I totally wrong here?

First of all, you've never said what exactly you are trying to prove. From the title, one might guess that you're trying to prove that the given grammar generates the language $L = \{ w \in (a+b)^* : \#_a(w) = \#_b(w) \}$. However, it seems that you are only trying to prove that every word generated by the grammar is in $L$. (The other direction is even harder.)

In order to prove your claim, you strengthen the claim, trying to prove the following:

If $S$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = \#_b(w) = m$.
If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = m + 1$ and $\#_b(w) = m$.
If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = m$ and $\#_b(w) = m + 1$.

In order to prove the strengthened claim, you need to prove by induction some claim $P(m)$. However, you never state what $P(m)$ is. Your "inductive hypothesis" is actually the statement that you're trying to prove by induction. One way to interpret your inductive hypothesis is the following: $P(m)$ states that

If $S$ generates $w$ then $\#_a(w) = \#_b(w) = m$.
If $A$ generates $w$ then $\#_a(w) = m + 1$ and $\#_b(w) = m$.
If $A$ generates $w$ then $\#_a(w) = m$ and $\#_b(w) = m + 1$.

However, this is simply false. You need to come up with a predicate $P(m)$ that you could prove by induction. Once you've done that, you can check whether your proof works.

The rest of your proof contains several other problems, but let's start with the more major problems mentioned above.


Three Partition-Function Algorithms Comparison I have implemented three algorithms codes, in Swift:

1- Polynomial coefficient:

 // create polynomial
func arrangePoly(ofTerms term: Int, toLength len: Int) -> [Int] {
    var a = Array(repeating: 0, count: len+1)

    for i in stride(from: 0, to: a.count, by: term) {
        a[i] = 1
    }
    return a
}
// polynomial product
func productToN(array1 a: [Int], arrayb b: [Int], toPower n: Int) -> [Int] {
    var res = Array(repeating: 0, count: n+1)

    for (pa, ca) in a.enumerated() {
        for (pb, cb) in b.enumerated() {
            if pa+pb <= n {
                res[pa+pb] += ca*cb
            }
        }
    }
    return res
}
// test code: partition of N
var p1 = arrangePoly(ofTerms: 1, toLength: N)
var res = p1

for i in 2...N {
    res = productToN(array1: res, arrayb: arrangePoly(ofTerms: i, toLength: N), toPower: N)
}
print(res[N])   // coefficient of x^N

2- Euler recurrence relations:

func eulerPartition(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            let sign = power(-1, k-1)
            sum += sign * (eulerPartition(n-(k*((3*k)-1)/2)) + eulerPartition(n-(k*((3*k)+1)/2)))
            k += 1
        }
        return sum
    }
}

3- Divisor sum formula:

// sigma(k) is the well-known sum of divisors of k
func part(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            sum += sigma(k) * part(n-k)
            k += 1
        }
        return sum / n
    }
}

All the three versions gives the same results for each n >= 1, but with different efficiency. While the Euler recurrence algorithm is assumed, theoretically, to be the fastest of the three, the polynomial coefficient algorithm works the best on my core2duo  laptop in spite of it is not recursively coded like the others. I am sure I have done something wrong, but I can not figure what or where.

Any idea?

Your implementation of the Euler method doesn't use memoization, so you keep computing and recomputing the same values. This is like computing the Fibonacci numbers along the following lines:

Fibonacci(n)
  if n = 0 or n = 1, return n
  otherwise, return Fibonacci(n-1) + Fibonacci(n-2)

You should modify the implementation so that after calculating eulerPartition for a certain $n$, if you are given the same $n$ again then you immediately return the previously calculated value.


How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$ Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.

Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s odd 1’s, even 0’s odd 1’s, odd
1’s, even 0’s – and combine them ...

But I can't understand how it works

Who can help?

Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow:
\begin{align}
S &\rightarrow X_{00},\\
X_{01}&\rightarrow \epsilon,\\
X_{00}&\rightarrow 0X_{10},\\
X_{00}&\rightarrow 1X_{10},\\
X_{01}&\rightarrow 0X_{11},\\
X_{01}&\rightarrow 1X_{00},\\
X_{10}&\rightarrow 0X_{00},\\
X_{10}&\rightarrow 1X_{11},\\
X_{11}&\rightarrow 0X_{01},\\
X_{11}&\rightarrow 1X_{10},\\
\end{align}
where the first index tells the parity of the number of zeros and the second one the parity of the count of ones.

Try to prove the correctness as an exercise.