How to know if a problem belongs to NP Class? What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we make a distinction about the space-time solvability of such problems. Also, I know that you can make reductions (of polynomial time) between problems, so if you know that a problem belongs to a certain class, then the other problem will also belong to this class. Also, I know that the Simplex algorithm solves problems for linear programming

What I would like to know: I would like to know how to "guess" if a problem belongs to NP Class. Does it have to do with the constraints of the problem, the number of constraints, the "type" of constraints?

An example In this link https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/ we can see an algortihm that solves "Maximum profit by buying and selling a share at most k times" with dynamic programming.

However, what if we increase the constraints. Let's say that we are limited to a net worth (we don't have unlimited money) or we can buy and sell more than one stock at a time but we are limited to the ammount of stocks we can buy or sell in the given time, or there are multiple stocks of various companies we can choose from but we are limited in the total number of stocks we can have.

How can we know what kind of constraints make the problem harder and harder "moving" it from P to NP Class ? What kind of constraints should a problem have to be sure that this problem certain belongs either to P or NP Class ?

Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast.
From my experience, it's more about the type of problem than what specific constraints you give it.
For example Indipendent-Set: Including a vertex at one end of the graph may inpact if you can take a vertex at the other end of the graph. This kind of unforeseeable side-effects makes it impossible to really find an algorithm, because you can't decide anything about your solution because you don't know the implications.

On the contrary is sorting: If you use quicksort, you can pick a pivot and split the elements into 2 parts, the ones lower and the ones higher than the pivot.
This way you already made the problem easier: You only need to sort these 2 parts, and you know which of them belongs to which side of the pivot.

Getting such a handle on a NP-hard problem was not successful yet.

I know that this was pretty vague, in the end you can't generalize your question. Every change to a given problem may generally make it NP-hard, you need to look individually.

To prove that something is NP-hard, you can try to reduce an known NP-hard problem to it. This is how it's done with most of them.

An example for your question would also be:
The Maximum-Cut problem is NP-hard, but if you only ask if there exists a cut of size |E|, then it becomes easy, because it is equivalent to asking if the graph is bipartite


Finding minimum spanning tree of a special form graph I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:

My idea was a recursive solution:
Suppose the algorithm recieve the graph with n as a parameter,

if n==2 then:
    take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
    take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
    - recursivly call the algorithm for n-1
    - take the lower cost edge between v0-->vn and v(n-1)-->vn

I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.

That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs.

Here is a counterexample with $n=3$.

The graph above was drawn at https://graphonline.ru/en

All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.

By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.


Does there exist a travelling salesmen generating algorithm? I'm curious if somebody has already figured this out.  Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling salesmen problem is known a priori, and such that we have a uniform distribution on the set of points? For example, I can think of an algorithm that will generate such a sequence by plotting a polygon, and the minimum distance would be the points going around the outside of the polygon, but the distribution on point-sets from this algorithm is highly biased.

So I would hope for an efficient algorithm that generates a set of points in $[0,1]^2$ (and its corresponding TSP solution), with equal probability to any set of points, i.e., each point has iid uniform distribution on $[0,1]^2$.  You could interpret "efficient" as "polynomial time".

PS: I strongly suspect that no algorithm could exist because if so, I imagine the problem would be solvable, so in this case, is there a database somewhere with a large number of solutions for randomly generated sets of points?

For posterity and because I never received any answers in the end: my best guess is $\forall x_0 \in [0,1]^2$ was to pick any point $x_1 \in [0,1]^2$, then generate a second point $x_2$ such that the interior angle between the line between $x_0$ and $x_1$ is greater than 90$^{\circ}$ and less than 180$^{\circ}$.  Now I can see two paths forward, one is to make a sort of quasi convex structure (obviously not every solution) by alternating whether the angles are interior or exterior and staying within the bounds. The solution is then $x_{0,...,n}$ for the minimum path.

The second possibility would be to put restrictions on the distance from the last point to the next point, (say halving each time) and again requiring the angle to be constrained, but perhaps this time we can loosen the constraint to greater than 90$^{\circ}$ and less than 270$^{\circ}$ and just require that we cannot cross a line we've already made. I can't guarantee this algorithm will always generate the correct solution, however I can guarantee that it won't generate all points in $[0,1]^2$, so the question remains unfortunately unanswered.

And for the PS in my original question: this might be a good place to get started for those looking.


Counting Minimum Spanning Trees I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph $G=(V,E)$ given by

When running Kruskal's you can end up with:

However, as you might note, there are several other minimum spanning trees that are still valid. An example would be getting rid of edge $BD$ and adding edge $AB$ or $CB$. So how can you determine the total number of different minimum spanning trees that exist in the graph, without having to inspect for all the different possibilities?

The best exposition on how to count the number of minimum spanning trees is, as far as I have seen, a stackoverflow answer by j_random_hacker.

In the course to answer a different question, that answer explains very well an algorithm that counts the number of MSTs.

It establishes that Kruskal's algorithm can find every MST.
It breaks up the Kruskal's algorithm into a series of blocks, each of which consists of a sequence of adding the edges of the same weight into a component multigraph that has been built in the previous block of operation.
It proves that the number of MSTs is the product of the number of spanning forests in the multigraph for each block-defining weight.
Finally, the number of spanning forests for a multigraph can be computed by Kirchhoff's theorem.


Slowdown in making nondeterministic Turing machines deterministic For every nondeterministic Turing machine, must there exist an equivalent deterministic one that runs in no more than twice the time?
Why or why not?
Can anyone explain?

If this were the case, then we would have P${}={}$NP, since then any polynomial-time NTM could be made into a polynomial-time DTM.
Your question is whether NTIME$(f(n))\subseteq{}$DTIME$(2f(n))$ for any function $f\colon\mathbb N\to\mathbb N$.  For $f\in\omega(n)$, one has DTIME$(2f(n))={}$DTIME$(f(n))$. So in this case, the question boils down to whether NTIME$(f(n))={}$DTIME$(f(n))$ or not. This question seems open.
What is known is that DTIME$(n)\subsetneq{}$NTIME$(n)$, see https://people.math.gatech.edu/~trotter/papers/34.pdf
It is also known that NTIME$(f(n))\subseteq{}$DTIME$(2^{O(f(n))})$, so you can simulate any NTM by a DTM with exponential slowdown.


Is a supercomputer more powerful than the total of all the world's computers in 2004? The supercomputer I am researching has 2.2 petaflops and boasts total memory of 1000 terabytes and disk space of 23.5 petabytes.

Is this more computing power than the total of the entire worlds computing power 10 years ago (2004)?

No, and not by a long way.

Take 25,000,000 ordinary desktop PCs from 2004.  To exceed the supercomputer you're talking about, each would need an 88megaflop CPU, 40Mb of memory and a 940Mb hard disk. In 2004, CPU clock frequencies were already in the GHz range, RAM in the hundreds of megabytes and hard drives in the gigabyte range. And there were many more than 25,000,000 computers in the USA, let alone the world.


How shall I understand the undesirable consequences of dynamic scoping? In Practical Foundation of Programming Languages by Harper

  8.4 Dynamic Scope

  Another approach, called dynamic scoping, or dynamic binding, is sometimes advocated
  as an alternative to static binding. The crucial difference is that with dynamic scoping the
  principle of identiﬁcation of abt’s up to renaming of bound variables is denied. Consequently, capture-avoiding substitution is not available. Instead, evaluation is deﬁned for
  open terms, with the bindings of free variables provided by an environment mapping variable names to (possibly open) values. The binding of a variable is determined as late as
  possible, at the point where the variable is evaluated, rather than where it is bound. If the
  environment does not provide a binding for a variable, evaluation is aborted with a run-time
  error.

  In the higher-order case, the equivalence of static and dynamic scope
  breaks down. For example, consider the expression

 e = (λ (x : num) λ (y : num) x + y)(42).

  With static scoping e evaluates to the closed value v = λ (y : num) 42 + y, which, if applied, would add 42 to its argument. It makes
  no difference how the bound variable x is chosen, the outcome will
  always be the same. With dynamic scoping, e evaluates to the open
  value v'  = λ (y : num) x + y in which the variable x occurs free.
  When this expression is evaluated, the variable x is bound to 42,
  but this is irrelevant because the binding is not needed to evaluate
  the λ-abstraction. The binding of x is not retrieved until such time
  as v' is applied to an argument, at which point the binding for x
  in force at that time is retrieved,and not the one in force at the
  point where e is evaluated.

  Therein lies the difference. For example, consider the expression

e' = (λ (f : num → num) (λ (x : num) f (0))(7))(e)`.

  When evaluated using dynamic scope, the value of e' is 7, whereas
  its value is 42 under static scope. The discrepancy can be traced to
  the rebinding of x to 7 before the value of e, namely v', is
  applied to 0, altering the outcome.

  Dynamic scope violates the basic principle that variables are given
  meaning by capture-avoiding substitution as deﬁned in Chapter 1.
  Violating this principle has at least two undesirable consequences.

  One is that the names of bound variables matter, in contrast to static
  scope which obeys the identiﬁcation principle. For example, had the
  innermost λ-abstraction of e' bound the variable y, rather than
  x, then its value would have been 42, rather than 7. Thus, one
  component of a program may be sensitive to the names of bound
  variables chosen in another component, a clear violation of modular
  decomposition.

  Another problem is that dynamic scope is not, in general, type-safe.
  For example, consider the expression

e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)

  Under dynamic scoping this expression gets stuck attempting to
  evaluate x + y with x bound to the string “zero”, and no further
  progress can be made.

What does it mean by "with dynamic scoping the
principle of identiﬁcation of abt’s up to renaming of bound variables is denied" and "consequently, capture-avoiding substitution is not available"?

Why under dynamic scoping, "had the innermost λ-abstraction of e' bound the variable y, rather than  x, then its value would have been 42, rather than 7"? How does  "static scope  obey the identiﬁcation principle" here?

How "Under dynamic scoping this expression gets stuck attempting to evaluate x + y with x bound to the string “zero”"?  Isn't it that x in e' is bound to 7?

Thanks.

I think you're right that that example is a bit confused. I believe the fix is the following, if I got my parantheses right.

e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)

should instead be

e' = (λ (f : num → num) (λ (x : str) f) ("zero"))(e)(7)

If we evaluate e first we'll get:

(λ (x : num) λ (y : num) x + y)(42).

x = 42
(λ (y : num) x + y).

We've finished evaluating e, since we got to a lambda. But evaluating it in the above expression will cause the bad addition "zero" + 42, since, regardless of what we do with the environment, the x="zero" binding will be the closest. The immediate reduction of the above gives:


Indentation based Grammars Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars.

I can see that a "preprocessor" can convert indent changes into tokens which are then handled in grammars, yet can one also perform the parsing based upon a single grammar without changing the intrinsic complexity of the 2nd grammer?

Any modern compiler consists of multiple phases, at least

lexing,
(context-free) parsing and
target code generation.

Additional phases are static analysis (names, types, ...) and optimisations.
Each phase uses the result of the prior as input.

Now, the lexer processes the actual program text and transforms it into a token stream. For instance, the (sub)string "abc" becomes a token StringLiteral("abc"), if becomes IF and myMethod becomes Identifier("myMethod"). Tokens typically hold additional information, e.g. their position in the original program text. The context-free grammar used for syntax parsing is expressed in terms of these tokens, usually ignoring their parameters.

At this point, it should be clear that handling whitespace is nothing crazy: instead of dropping all whitespace (like a Java compiler would do), you could as easily lex the strings "  " or \t to a token Indentation used in the grammar.


If P = NP, do these NP-complete problems reduce to these specific easier versions? I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al.
Chapter 8 has the table below and I am wondering:

if  $P = NP$ does each of the problems on the left reduce to the easy problem (in $P$)in its immediate right?

The book mentions that

the problems on the left are all difficult for the same reason! At their
core, they are all the same problem, just in different disguises! They are all equivalent:

does this imply that the problems on the right are also the same problem but in different guises? Can they be solved the same way like solving SAT for NP-complete problems? If so, what's the equivalent of SAT for problems in $P$ ?  I understand that SAT reduces to all problems in $NP$  but is there a problem in $P$ that sort of holds the same position as SAT in $NP$?

Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if $P=NP$? This was asked in a true-false question and couldn't get it right. The options were: true, false, true if $P=NP$, true $P \neq NP$. In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right?

If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally similar problems for the left and right columns to make the point that a seemingly small change to an efficiently solvable problem can make it NP-complete, and vice versa.

2. The book mentions that "the problems on the left are all difficult for the same reason! At their core, they are all the same problem [...]" does this imply that the problems on the right are also the same problem but in different guises?

I would say no. NP-complete problems are all polynomially equivalent, meaning that given an oracle that computes the answer to one in polynomial time, you can answer any other in polynomial time. Because there is no polynomial-time algorithm known for any of them without the oracle, the amount of time you save by using the oracle dominates the total time for large enough problem sizes, so you can argue that the oracle is doing the heavy lifting. This applies to any pair of NP-complete problems, so they all contain models of important parts of each other in a nontrivial way – somewhat like different computational models can simulate each other
Problems in P are trivially polynomially equivalent: given an oracle for one, you can solve any other one in the usual way and ignore the oracle. But you can't argue from this equivalence that the oracle played any role. P contains many problems like "is the input nonempty?" that are of no use in solving any other problem and clearly don't "contain" interesting problems like MST.
If it turns out that P=NP then it becomes much harder, perhaps impossible, to formalize the relationship between the problems that were formerly considered NP-complete; the apparent similarity between them might just be an illusion.

3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if P=NP?

In the trivial sense, yes. If P≠NP, then it doesn't (if it did, that would give you a polynomial-time algorithm for Hamiltonian path).

In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

It might be reducible to some other spanning-tree algorithm, but that algorithm would have to be flexible enough that you could encode the Hamiltonian-path constraint somehow in the input.


Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP.
Its also experimentally known that 3SAT has the most difficult known cases when the clause to literal ratio is approximately 4.2.

Q1. Is there a similar result for 3MaxSAT where the approximation algorithm for satisfying some 7/8+e of clauses becomes almost always difficult if 3MaxSAT has some specific format (like 3SAT in 2.) ?

Q2. Is there a benchmark set available for 3MaxSAT approximation algorithms for such cases?

Q3. Is there a similar approximation hardness result for 3SAT (like 3MaxSAT in 1.) if informed that the given 3SAT is satisfiable? Is just the clause to literal ratio is sufficient to represent completely the hardest cases for such approximation algorithms too?

The reason that 3SAT is hardest empirically when the clause-to-literal ratio is 4.2 is because this is the satisfiability threshold (the threshold at which a random 3SAT becomes unsatisfiable with high probability). However, this is a very different type of hardness than NP-hardness. First of all, the model is different: you are generating a random 3SAT instance with a given clause-to-literal ratio, and hardness applies only on average. Second, there is no formal connection between the satisfiability threshold and computational hardness. There are some properties of the solution space which we think make the problem hard near the satisfiability threshold, but this is just a heuristic.

Now for your actual questions:

While there are definitely no formal results, it might be the case that known practical approximation algorithms for MAX-3SAT perform poorly near the satisfiability threshold.
No idea.
You are asking two questions. Regarding your first question, if you had an algorithm which approximated MAX-3SAT only on satisfiable instances, say achieving 99% performance, you could run it on any given instance, and so determine whether it is satisfiable or less than 99% satisfiable. We know that this is unlikely as long as the performance is larger than 7/8. Regarding your second question, the instances coming out of the hardness proof are not arbitrary, so there is a class of formally "hard instances", but I don't think it has anything to do with the satisfiability threshold.


Regular languages closed under quotients with arbitrary languages When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final states are those from which we can reach a final state of $M$ with a string from $B$. How can we just say it's possible to take such a set?

Does this proof also work for a similar property (I don't know the name) that creates the set
$\{ x \mid \forall y \in B : xy \in R \} $?

The (right) quotient of $R$ by $B$ is the language
$$
  RB^{-1} = \{x \in A^* \mid \exists y \in B,\ xy \in R\}
$$
and indeed, if $(Q, A, \cdot, q_0, F)$ is the minimal DFA of $R$, then $RB^{-1}$ is accepted by the automaton $(Q, A, \cdot, q_0, S)$, where
$$
S = \{q \in Q \mid \exists y \in B\ \ q \cdot y  \in F\}.
$$
On the other hand, let $R/B =  \{x \in A^* \mid \forall y \in B\ \ xy \in R\}$. Then one gets
$$
  R/B = \bigcap_{y \in B} \{ x \in A^* \mid xy \in R \} = \bigcap_{y \in B} Ry^{-1}
$$
Since $R$ is regular, there are only finitely many distinct languages of the form $Ry^{-1}$, and each of it is regular. It follows that $R/B$ is also regular.

This gives a proof that the languages $RB^{-1}$ and $R/B$ are regular for any $B$. However, if you want to find effectively an automaton accepting these languages, this is a different story and you may need to identify which of the right quotients  $Ru^{-1}$ are of the form $Ry^{-1}$ with $y \in B$, a question that might be undecidable, depending on $B$ and $R$...


Developing a Context Free Grammar whilst knowing the number of terminals I am trying to develop a CFG for the language $L$ defined by:

$L = \{a^{n+2}bba^{n-2} | n > 1\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

$S \rightarrow aaaaXbbX$ (Production 1)
$X \rightarrow aX | \Lambda $ (Production 2)

This would be right if we were somehow forced to substitute the same value of the non-terminal $X$ in both its appearances in production 1. However, we can substitute $X \rightarrow aX$ in its first apperance in production 1 and $X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $a's$ off as defined in the language $L$.
The first question is, is there even a CFG for this?
Well, I would say according to theory, yes there is because:

I am asked to draw a Determinate Push Down Automata for this language; and
According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?

Your attempt was pretty close! But I think that this is the way to go for you

$$S \rightarrow a a a a X$$

$$X \rightarrow a X a \mid b b$$

The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.

So after that, it's a question of making a CFG that generates $L = \{a^n b b a^n \mid n \geq  0\}$. That's exactly what $X$ does. Every time you see a $X$ you have to put a leading and trailing $a$ in and you can't terminate until you put the $b b$ in the middle since otherwise the $X$ gets expanded to another $X$.


Infix to postfix conversion I am somewhat stuck in converting an expression with negative numbers from infix to postfix.

Suppose we have a expression like

a = -b - (-c - d) .

At some places I read that you can parathesize the negative numbers to solve the problem. But if I parathesize them as

a = (-b) - ((-c) - d), then at the beginning of the postfix expression I would get "ab-" which means a-b and is incorrect.

Can someone help me?

Canonically, we convert from infix to postfix form only expressions. However, you can enhance this by introducing the assignment operator = in addition to the standard four binary operators +, -, *, and /. Just define the conversion as: a = b  becomes  ab=. So for example, a = x + 5 becomes ax5+=.

As for the negative numbers, you can parenthesize them (as you suggest). For example,  a = -b + 2 becomes a(-b)2+= or just separate each operand or operator by a single space, for example the previous postfix expression can be written as a -b 2 + =. This is another example: derv = -dy/dx + 5*(-x) becomes derv(-dy)dx/5(-x)*+= or derv -dy dx / 5 -x * + =.


how is an arbitrary dimension "reshaper" turned into a function given a linear index? i have an arbitrary "reshaping" function which, given a linear sequential array can "reshape" it to 2D or 3D.  the order in which the X-dimension, Y-dimension and Z-dimension may all be changed, as well as the size of the X, Y and Z dimensions, may all be changed, at runtime.  consequently it is not possible to use static compilers or static allocation.

here is a function that, for the full sequential range, prints out a corresponding (remapped) set of indices:

(xdim, ydim, zdim) = (3, 2, 5)
lims = [xdim, ydim, zdim]
idxs = [0,0,0]
order = [1,0,2]

for idx in range(xdim * ydim * zdim):
    new_idx = idxs[0] + idxs[1] * xdim + idxs[2] * xdim * ydim
    print new_idx,
    for i in range(3):
        idxs[order[i]] = idxs[order[i]] + 1
        if (idxs[order[i]] != lims[order[i]]):
            break
        print
    idxs[order[i]] = 0

what i actually need is a function which, when it is passed an arbitrary index, returns one (correct) remapped index.

i suppose what i could hypothetically do is have a function that sets up the full array (at startup time), and indexes it.  i would however like to see an algorithmic version of the above.

If the index of $(i,j,k)$ is $p = i + xj + xyk$ then you can compute $i,j,k$ given $p$ as follows:

i = p mod x
j = (p / x) mod y
k = (p / x) / y

Using this you can solve your problem.


Convert FOL clauses to PROLOG I am very new to PROLOG so it might be a very trivial question, but I absolutely have no idea how to solve it. There are 4 sentences I need to formulate into PROLOG code:

  All hounds howl at night.
  Anyone who has any cats will not have any mice.
  Light sleepers do not have anything which howls at night.
  John has either a cat or a hound.

I convert sentences to well-formed formula in first-order predicate calculus like that

- ∀x (HOUND(x) → HOWL(x))

- ∀x ∀y (HAVE(x,y) ∧ CAT (y) → ¬∃z (HAVE(x,z) ∧ MOUSE (z)))

- ∀x (Light_Sleeper(x) → ¬∃y (HAVE (x,y) ∧ HOWL(y)))

- ∃x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

Now I don't know how to write them in Prolog.
Also, how can I make query on them?

If you can convert them to Horn clauses, you can convert them to Prolog.

If you can't convert them to Horn clauses, I don't think you can convert them to Prolog.

So, convert them to Horn clauses first, and then see the answer to this question:

Horn clause to Prolog


How to describe Deterministic Transitive Closure in FOL? In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.
Hence, taking into account that FOL captures LOGSPACE, the following should be possible:

Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
Define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)").

I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.

Hence, taking into account that FOL captures LOGSPACE, it should be possible to:

Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
It should be possible to define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)")

Actually this is not correct: first-order logic does not capture logspace. As you said earlier in your question, FOL plus deterministic transitive closure captures logspace, that is
$$
\text{FO(DTC)} = \text{L}
$$
but
$$
\text{FO} \ne \text{FO(DTC)},
$$
i.e. deterministic transitive closure is not definable in first-order logic.
More generally, FOL is quite limited. FOL captures a class called uniform $\text{AC0}$ (see the complexity zoo and Immerman's diagram); it is the class of queries computable in "constant parallel time". And transitive closure, even deterministic transitive closure, cannot be done in $\text{AC0}$ (with a circuit of constant depth). Even something very simple, calculating the parity of the number of input bits, can't be done in $\text{AC0}$.

How to describe Deterministic Transitive Closure in FOL?

To reiterate: it is impossible.


Linked List with Merge Sort Is Merge Sort the best sorting technique to sort a linked list? Also, which sorting technique is worst for a linked list?

Merge sort uses a divide and conquer method. What makes merge sort efficient for sorting a linked list?

It is really inefficient to access a certain index in a linked list, which is what many sorting algorithms rely on. MergeSort, however, divides and merges lists, which LLs do efficiently. You can find some code and an explanation here.


Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths? I am curious of knowing of an efficient algorithm for the problem:

Given two vertices s,t in a directed graph, is there a vertex x such that xs and xtare paths?

I can of course do a BFS from each node of the graph resulting in a quadratic time algorithm.

Or I can reverse all the edges of the graph, do a BFS from s store all reachable vertices in a hashtable, do a BFS from t and check for each reachable vertex if it is in the table, ifso, I found x.  While the running time is linear, the extra space requirement is ugly.

Is there any elegant O(E + V) time algorithm for this problem?

tl;dr I wrote some solution but realized it is not perfect. Since I didn't want all this typing to go waste I figured I might post my observations here rather than splitting them in the comments.

I think that the problem can be solved for any arbitrary $s,t$ and $x$ in $\mathcal{O}(V+ E)$. In fact we can extend the problem to answer $Q$ queries of the form $(s,t,x)$ with $\mathcal{O}(V+E)$ pre processing and $\mathcal{O}(1)$ per query. I am having trouble completing step 6, but I am pretty sure that it can be done. Someone in the comments may know.

Find all strongly connected components (scc) of the graph using Kosarjau's or Tarjans algorithm. This step will take $\mathcal{O}(V+E)$ time.
Using a hash table, you can check if two nodes belong to the same stongly connected component in $\mathcal{O}(1)$ time.
If two nodes $u$ and $v$ belong to the same strongly connected component, then there exists paths both from $u$ to $v$ and $v$ to $u$.
Now what remains to be checked is if two nodes $u$ and $v$ do not belong to the same strongly connected component, does there still exist a path from $u$ to $v$.
We will modify the given graph $G$ to a new graph $G'$ which we shall call the strongly connected component graph or scc graph for short. In the scc graph, each node corresponds to one strongly connected component in the original graph i.e. we compress all nodes belonging to the same scc to a single node. It can be proven that the scc graph is a Directed Acyclic Graph (DAG for short).
Now our task reduces to check if there exists a directed path between $u$ and $v$ in the DAG. Topological sort can give an ordering such that for any path from $u$ to $v$, $u$ will appear before $v$ in the ordering. Thus we can check if index of $u$ in the topologically sorted sequence of vertices is less than that of $v$ in $\mathcal{O}(1)$ but this method also gives false positives and this is where I am stuck.
I feel that we can augment step 6 with some additional data to complete the algo. One method I was thinking of was to maintain some constant $K$ number of random topological sorts and if the inequality $index(u) < index(v)$ is true for all $K$ sequences then we can conclude with high probability that there is a path from $u$ to $v$.


How to use Parallel Semaphores for Dining Philosophers Problem I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the different cases using simple semaphores (i.e asking the last philosopher to grab the right fork before the left while the others grab right first) however, these still violates the concurrency requirement.
He explained that these types of problems begin to show the importance of advanced synchronization and how we need more but he didn't go into details because that subject belongs to the actual Operating Systems course.
I am curious as to how you could implement AND semaphores to solve the dining philosophers problem. I did some research and could not find any great resources showing implementations using AND or monitors.
Could someone go into some detail or point me to an article/textbook that does?

Assume we have 4 processes p[0], p[1],...,p[3] and 4 mutexes m[0],m[1],...m[3]. Now in order to solve the dining philosophers problem, we only need to make one of the philosopher (one of the processes) to take the folk (one of the mutexes) in reverse direction than the other philosophers. Note that by doing this, we are trying to avoid deadlock.

So in practice, we need to make all processes to follow certain implementation, except one.
All processes (philosophers) should follow this implementation:
while(1)
{
   down(m[(i+1) % 4]);
   down(m[i]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

except one process should follow this:
while(1)
{
   down(m[i]);
   down(m[(i+1) % 4]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

Note by down we mean taking the folks and by up we mean releasing the folks, and note how both implementations differ. For example, we made one of the philosopher to take the fort (down) in reverse order than the others.
I hope this could help.


Intersection and union of a regular and a non-regular language Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample.

I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is regular. I can construct a finite automaton for this: $L_1$ is regular, $L_2 \cap L_1$ is regular, so remove all the paths (finite amount) for $L_1 \cap L_2$ from the finite amount of paths for $L_1$. So there are a finite amount of paths left for this whole thing. This thing is disjoint from $L_2$, but how can I prove that the union of $L_1 \setminus (L_1 \cap L_2)$ (regular) and $L_2$ (not regular) is not regular?

We can prove this by contradiction.
Lets define $\overline{L_1} = \Sigma^* \setminus L_1$. Then we can reformulate $L_2$:

$L_2 = ((L_1 \cup L_2) \setminus L_1) \cup (L_1 \cap L_2) = ((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$

We know:

Regular Languages are closed under union, intersection and complement
$\overline{L_1}$ and $L_1 \cap L_2$ are regular
$L_2$ is not regular

Now assume $L_1 \cup L_2$ is regular: Then $((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$ is regular (as it is only a union/intersection of regular languages), so $L_2$ would be regular. That is a contradiction, therefore our assumption is false, and $L_1 \cup L_2$ can not be regular.


Skip lists with limited height This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions.

I am asked to find a method of arranging items in a skiplist, with height limited to 3 and unlimited number of elements, in such a way such that searching takes worst-case $\Theta (n^{1/3})$. No restriction on how expensive the arranging part is; just describe what subset of the keys go into which level.

I am somewhat confused. How can a skiplist with a limited number of items have search complexity anything other than $\Theta(n)$? Clearly, with any clever algorithm, I can just fill the skiplist with a horrendous amount of elements, and as the number of elements goes up, surely the handicapped skiplist can't do any better than a linked list asymptotically? I think I can prove this for the simple set of rearranging algorithms that put a random proportion $q$ of the items into the second layer, and another random proportion $p$ of items within these items to the top layer.

Am I missing anything obvious? Is the question faulty?

Hint: If the height is $k$, then the search complexity should be $O(kn^{1/k})$ (so the best choice is $k = \log n$, giving logarithmic time). Each level should contain every $n^{1/k}$th element of the lower level. Do the obvious thing - find the two elements bracketing your element in the first level, then the two elements bracketing it in the second level, and so on.


What's the most time efficient way to find the number of nodes reachable from each root and no other root? Suppose there are n nodes.
These nodes are connected by m unique directed edges. Sets of these edges may form cycles.
Each node has an associated quantity.
r of these nodes are selected as root nodes.

A node a can be said to reach node b if

a is b or
there exists a directed path from a to b.

The goal: For each root node, find the sum of the quantities of all nodes which it can reach and no other root can reach.

This includes the root itself. For example, if root 2 can reach root 1, then root 1's associated quantity will be counted to neither root 1 nor root 2's sum. On the other hand, if no root other than root 1 can reach root 1, then root 1's associated quantity will be counted toward root 1's sum.

I'm trying to puzzle out how to do this with the minimum number of calculations, but I think I need to brush up on my graph theory. This problem is quite a lot easier on a tree, but I've found dealing with cycles makes things much more complicated. I'm having a tough time finding a solution which doesn't incessantly re-traverse the graph.

A rough sketch, you can fill in the details:

Using Strongly Connected Components (SCCs), you can reduce the graph to a DAG. If you run topological sort on this DAG, all incoming edges to a node will be processed before any outgoing edges. Then just store at each node which root has reached it, or if none/more than one roots have reached it.


General question on approach to showing sample size required is $\Omega(\cdot)$ I was not able to find a similar question in the archives, so pardon this relatively elementary question if it has been asked before.

Let $E_n$ be some event that depends on the sample size $n$ and suppose we are looking for an upper bound on $n$ that guarantees $Pr(E_n)\geq 1-\varepsilon$ for some $\varepsilon\in(0,1)$.  For example, if we are flipping a biased coin that lands heads with probability $p>.5$ and we define the event $E_n = \{\text{# of heads}>\frac{n}{2}\}$ then we are looking for $n\in O(f(p))$ since the sample size will be a function of the parameter $p$.  One way I have seen this approached is to upper bound the probability of $E_n$ NOT occurring and then set this upper bound to be at most $\varepsilon$ and then solving such that we get $n\geq\text{ something involving } p$.  My interpretation of this is that it is sufficient to have $n$ this big to guarantee $Pr(E_n)\geq 1-\varepsilon$ which is why it is an upper bound.

My question then is this: if my interpretation above is correct, is there an analogous approach to showing a lower bound for $n$ i.e. $n\in\Omega(g(p))$?

There is a difference between the two questions. Let $p_n$ be the number of heads in $n$ trials divided by $n$. We know that for large $n$, $p_n$ is very close to $p$; qualitatively this is the law of large numbers, and quantitatively this is the central limit theorem. This phenomenon is known as concentration. This is what you use to give an upper bound on $n$. In contrast, to give a lower bound on $n$ you need to show anti-concentration: that for small $n$, $p_n$ has a reasonable probability of being somewhat far from $p$. The techniques for showing anti-concentration are often more delicate.

In your particular example, concentration can be shown using classical inequalities such as Chernoff's inequality. For anti-concentration you can use the Paley–Zygmund inequality, but you won't necessarily get good bounds. To get nearly tight bounds you can use a general-purpose double-sided inequality such as Berry–Esseen, or a specialized one à la de Moivre–Laplace.


Formal Description Of Data Structure For Infinite Sets Of Reals The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it can represent uncountable and infinite sets. What prior work can I reference for this data structure?

I'm not sure you need to reference any prior work; it's a basic enough approach.  You can just say that you represent a set as a union of intervals.  If you were inspired by Sympy, you could cite Sympy and that page.


Hard Drive Seek Time using FIFO, SSF, SCAN A hard disk spins at 6000 rpm (revolutions per minute), and it takes 100 μs (on average) for the head to traverse one track. Consider the following sequence of disk track requests: 27, 129, 110, 186, 147, 41, 10, 64, 120. Assume that initially the head is at track 30 and is moving in the direction of decreasing track numbers. Compute the time it takes to serve the requests using (1) FIFO, (2) SSF (Shortest-Seek First), (3) SCAN.

I understand the difference between the different algorithms and I generally get how to calculate it.

My questions is, when I calculate the Average rotational time, i.e. (60/6000) / 2 = 5ms, do I need to multiply this by the number of tracks moved?

My FIFO calculation as an example:

(3+102+19+76+39+106+31+54+56) * (5ms + 0.1ms) = 2478.6ms

I add up the number of tracks moved and multiply this by the average rotational time + the time it takes to traverse each track.

Is this approach correct?

Thank you

@greybeard why he divided by 2
on average we will need to wait for half a rotation of the disk for the correct sector to come under the head. Thus, on average, the rotational latency is half the time it takes the disk to make a complete revolution.

do I need to multiply this by the number of tracks moved?
No. Because average rotational time is the time to move head from one sector to any other sector in same track. This movement is done by disk rotation.

In your question we will consider any sector in given track. So when track changes from 30 to 27, it takes 3 track movement and 1 average rotation so time 3*0.1+5

In general, total time = seek time + rotating latency

Seek time : time to change track

Edited

(3+102+19+76+39+106+31+54+56)*0.1 + number_of_time_movement_occured * rotational_latency
= 486 * 0.1 + 9 * 5
= 48.6 + 45
= 93.6


Complexity of scalar operations for integers I am currently studying the complexity of matrix multiplication and Wikipedia's article says "The matrix multiplication algorithm that results of the definition requires, in the worst case, n³ multiplications of scalars and (n−1)n² additions for computing the product of two square n×n matrices. Its computational complexity is therefore O(n³), in a model of computation for which the scalar operations require a constant time (in practice, this is the case for floating point numbers, but not for integers)."

I'd like to know why integers' scalar operations does not require constant time.

The quote from Wikipedia doesn't say that scalar operations on integers don't take constant time; on the contrary, it says that the analysis of the matrix multiplication is based on the assumption that those scalar operations do take constant time. This assumption is stated not because it's false, but because it is true only in some contexts.

If you use a fixed-width integer type, such as 32-bit or 64-bit integers, then arithmetic operations such as + or * take asymptotically constant time simply because there are only finitely many different inputs, so whichever inputs they are slowest for is a constant bound on their running time.

On the other hand, if you use a language like Python where integers are not bounded by a fixed number of bits, then arithmetic operations are not constant time, and generally cannot be done in constant time on real hardware.

The algorithm we use to add numbers on paper requires adding the rightmost digits, maybe carrying a 1 to the next column left, adding the digits in that column and carrying, and so on in a loop. This algorithm is O(log n + log m) because the number of digits you need to add is logarithmic. The algorithm for adding integers in Python has a lot of special details regarding the data structure used to represent those integers, but the way it works is essentially the same; a loop over the digits of the number from right to left, in O(log n + log m) time.


Calculate the minimum absolute difference between the maximum and minimum number from the triplet of 3 arrays Question is:

Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively.

There is another question: Find i, j, k such that :
max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimized.
Return the minimum max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])). A, B & C are sorted arrays.

Reading the solution approach here and here, I realize that the solution approach for both these questions is same, to:

minimize abs( max(a,b,c) - min(a,b,c) )

I'm not sure why this follows and how we should go about relating these two questions and their algorithms. Why are these two questions identical?

Can you see the following equality?
 abs( max(a,b,c) - min(a,b,c) ) = max(abs(a - b), abs(b - c), abs(c - a))

Here is a hint to prove the equality.

   Without loss of generality, we can assume a >= b >= c.

By the way, the first abs is not necessary since max(a, b, c) is always no less than min (a, b, c).


Block detection in repeated stream I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation.

Here are the specifics:

There is an N-length block of data contained in a stream
The block is repeated many times in the stream
the data is highly corrupted, some bytes could just be wrong, where as others can be detected as missing (erasures)
There is a function F(data) which can say if a block represents valid data (the probability of a false positive is virtually zero)
F can also provide a probability value that even if the block is not valid data whether the block itself is valid (but just has too much corruption to be recovered)
The chance of corrupted data is very low compared to missing data

For example, say I have this data stream and wish to recover the 10 length sequence 1234567890. The data is just a rough visual example (I can't guarantee recovery is actually possible from this bit). A . represents a missing byte, and <break> indicates an unknown block of data (no data  and not length known). Note also the Qs as an example of corrupt data.

23.5678901.3456789<break>2345678..1..4567QQ012345678..3456

How can I take such a stream of data and recovery probably blocks of N data? As the actual data includes forward error recovery the block recovery need not be perfect. All it needs to do is give probable reconstructed blocks of data and the F function will attempt to do error recovery.  Thus I expect F fill have to be called several times.

I'd like to find something better than simply calling F at each point in the stream since the error rate could be high enough that no single run block of N can be recovered -- the repetitions in the stream must be used somehow.

I think what you want is impossible to do without further assumptions on F.

Consider the following, rather simple data stream for a target data length of 5:

123441233512245113451255513555 ...

Note that not a single block contains 12345 (our original data). In order to find a proper combination of data parts, you would have check all combinations, in general. What is the probability that some combination other than 12345 is accepted by F? And this is on a stream without lost or corrupt symbols and ignoring the problem of overlaps between blocks which might by accident be valid data!

Therefore, I think keeping a buffer of size $N$ and running F in every time step is the best you can do. Note that you can skip evaluation of F if there is a corrupt symbol in the buffer (provided you can identify those). You still have the problem of overlap errors and wrong valid blocks, though.

You have more potential if F has nice properties, for example if it is able to identify valid parts of data. Then you can store only maximal valid parts and piece those together. Also, formatting the data stream can help; a simple example would be markers for the beginning of a data block (that would get rid of problems with overlaps and reduce the amount of calls to F). Furthermore, usual assumptions such as "error probability is small" can make waiting for a full valid copy of the data viable; many protocols break down if virtually every other symbol is corrupt.

All these are not new problems. I suggest further reading on

error detection and correction codes,
codes in general and
communication protocols.


Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations) I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.

The bound should be $nm \lg(m)$. I need to prove this using a decision tree.

I tried counting the number of possible permutations (which would be the number of leaves in the tree) but
I got stuck. I tried the following:

When merging the 2nd array with the first, we have $\binom{2n}{n}$ possibilities to place the elements. When merging the 3rd, we have $\binom{3n}{n}$ and so on, so the total number of permutations is:

$$\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}$$

The height of the tree is denoted $h$.

$$h > \lg{\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}}$$

And from here I don't know how to prove the complexity.

My question is - did I count the permutations correctly? Is there a more simple bound? How to continue from here?

Also, ould this problem possibly be equivalent to the problem of sorting an $m$-sorted array of size $nm$? Because in this problem it is easy to prove that the bound is $nm \lg(m)$.

Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In particular, this shows that for $k \geq 2$,
$$
\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}.
$$
Therefore
$$
\log \binom{kn}{n} \geq n\log k - O(\log n),
$$
where the big O doesn't depend on $k$. Summing this for $k=2,\ldots,m$, we deduce
$$
h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm),
$$
using Stirling's formula again.


Two's complement general formula In college, we've seen some general formulas to compute the decimal value a of a binary representation $a_{N-1} \dots a_2 a_1 a_0$ in two's complement, $N$ being the number of bits.
For $a \ge 0$ we've seen $a= \sum_{i=0}^{N-2} a_i 2^i$, which seems correct to me if I work it out.
But for $a < 0$ our book says $a=-2^{N-1}+\sum_{i=0}^{N-2} a_i 2^i$ and this is where I go wrong.

Can someone explain with an example why this is correct or which formula is right?

Let $a_{N-1} \cdots a_0$ be the two's complement representation of the number $a$. The more general formula is:
$$a = -a_{N-1}2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i$$
(I am sure you can figure out how your formulas can be derived from this one.)

Why does this hold? For $a \ge 0$, $a_{N - 1} = 0$ and then the value of $a$ is simply the value of the binary representation $a_{N-2} \cdots a_0$. For $a < 0$, on the other hand, let $b = -a \ge 0$ have binary representation $b_{N-1} \cdots b_0$. Then
$$\sum_{i=0}^{N-1} a_i 2^i = \sum_{i=0}^{N-1} (1-b_i) 2^i + 1
= \sum_{i=0}^{N-1} 2^i - \sum_{i=0}^{N-1} b_i 2^i + 1  = 2^N - b$$
since the two's complement is defined as the complement of the representation $b_{N-1} \cdots b_0$, plus one, and $\sum_{i=0}^{N-1}2^i = 2^N - 1$. Since $a$ is negative, $a_{N-1} = 1$ and then:
$$a = -b
= -2^N + \sum_{i=0}^{N-1} a_i 2^i
= -2^N + 2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i
= -2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i
$$

I have refrained from giving an explicit example as you had asked; I believe explaining why the formula works in the first place is far more instructive.


Find a regular language that is "infinitely between" two other regular languages Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq L_{3} \subseteq L_{2}$ and both $L_{2} - L_{3}$ and $L_{3} - L_{1}$ are infinite.

My solution to this problem is choosing $L_{1} = \{a\}$ (or some other single word in the language), $L_{3} = \Sigma^{+}$, and $L_{2} = \Sigma^{*}$.

Are these choices valid? I think that $\Sigma^{+} - \{a\}$ is infinite, but I am unsure whether or not $\Sigma^{*} - \Sigma^{+}$ is infinite.

Because regular languages are closed under complement and intersection, $L_2 - L_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths.

Therefore, by the pumping lemma, there exist some words $x$, $y$, and $z$ such that the concatenation $x y^k z$ is in $L_2 - L_1$ for all $k \geq 0$.

Now consider the language $L'$ consisting of all words of the form $x y^{2k} z$ - that is, words where the $y$ is repeated an even number of times. Clearly, $L'$ is regular and infinite, and so is $L_2 - L_1 - L'$, since it contains all strings $x y^k z$ where $k$ is odd. Therefore, setting $L_3 = L_1 \cup L'$ satisfies the problem.


Quadratic Probing Infinite Loop? I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element?

According to https://en.wikipedia.org/wiki/Quadratic_probing:

  In the case of quadratic probing, with the exception of the triangular
  number case for a power-of-two-sized hash table[2], there is no
  guarantee of finding an empty cell once the table gets more than half
  full, or even before the table gets half full if the table size is not
  prime.

Does this mean that Load Factor should always be 0.5 for a Hash Table that uses Quadratic Probing?

What is the proof of this claim?

No. It means you should count how many slots you have checked, and if you have checked more than the available number of slots, you resize the table.

In practice, if you regularly visit more than ten slots, then either the hash function is bad (nothing you can do about it while your program is running), or your load factor is too large. Not finding an empty slot will only happen if an attacker can decide your hash values.


Sum of products over k-permutations Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to most efficiently calculate the sum, over all $K$-permutations, of products $A[1,n_1] * A[2,n_2] * ... * A[k,n_K]$?
For example, let $K=3$ and $N=5$. One possible K-permutation is (5, 1, 3), and the corresponding product is $A[1,5] * A[2,1] * A[3,3]$. But what must be calculated is the sum of such products over all K-permutations, e.g.:
$$
A[1,1] * A[2,2] * A[3,3] + \\
A[1,1] * A[2,2] * A[3,4] + \\
A[1,1] * A[2,2] * A[3,5] + \\
A[1,1] * A[2,3] * A[3,4] + \\
A[1,1] * A[2,3] * A[3,5] + \\
A[1,1] * A[2,4] * A[3,5] + \\
...
$$
I am not even sure there is an efficient (polynomial time) solution, the most I have been able to come up with has about $2^M$ complexity which is unacceptable.

When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.
For general $K$, your function is a known extension of the permanent. Ryser's algorithm, one of the $\tilde{O}(2^N)$ algorithms for the square case, extends to the rectangular case as well.


Find all items which are subsets of an item I have a problem that I think should have been studied. I am looking for algorithms for it.

Each item is a set of key-value pairs.
Let $x$ be an item and $F$ be a set of items.

Each key and each value can appear multiple times.
The number of possible keys and possible values can be arbitrary large.

We are given $x$ and $F$. We want to find all those items $y$ in $F$ such that $y.val \subseteq x$.

For example,

$x = \{(a,1), (b,2), (c,3), (d,4)\}$

$F= \{$
$(A, \{(a,1)\}), $
$(B, \{(a,1), (b,2)\}),$
$(C, \{(a,1), (b,3)\}),$
$(D, \{(b,2), (c,3), (d,4)\}),$
$(E, \{(a,1), (b,2), (c,3), (d,4)\}),$
$(F, \{(a,1), (b,2), (c,3), (d,4), (e,5)\}),$
$(G, \{(a,1), (b,2), (c,3), (e,5)\})$
$\}$

The answer is:
$A$ yes, $B$ yes, $C$ no (right keys, wrong values), $D$ yes, $E$ yes (exact match),
$F$ no, $G$ no.

Has this problem been studied?

The problem seems similar to finding features from a DNA sequence or detecting plagiarism in a document.

I asked this problem in theoretical CS stack exchange and did not get very helpful answers. https://cstheory.stackexchange.com/questions/18052/find-all-items-which-are-subsets-of-an-item

Your problem is the same one faced by SAT solvers who want to eliminate subsumed clauses from a CNF formula.  Any clause $B$ that contains a superset of the literals of another clause $A$ in the formula is redundant and can be removed without changing the satisfiability of the formula.  We say $A$ subsumes $B$, so $B$ can be discarded.  Instead of single valued literals, you have these item tuples but it is the same problem as finding $A$.

The algorithms used are refinements of the naive algorithm, where you iterate through each element of a potential subset, checking to see if it occurs in $x$.
If you sort $x$'s items you can reduce the linear time search to log $\vert{x}\vert$.  If you use a hashtable to store $x$'s items you can have amortized constant time for each search.  Because of the hashing overhead, save this optimization for large sets.  Bitmask signatures for each set allow you to do a cheap initial check, only doing the expensive iteration and searching of $x$ if the bitmaps can't rule out a subset match.


Exit quickly from a maze with a local view of the maze How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)?
You don't know the maze configuration but you know where your player is, and which direction are opened from his position.
Another point, the player can move RIGHT/DOWN/LEFT/UP, and the exit is at the bottom right.
I tried to mainly follow RIGHT/DOWN and avoid dead ends, but I think we can do better!

The fact that the exit is in the bottom right and has coordinates $(49, 49)$, while the player has coordinates $(1,1)$ makes me think that the maze has a fixed size of $49 \times 49$. If that's the case the exit can be found in constant time.
In fact, there is a fixed strategy (i.e., a sequence of moves) that uses a constant number of moves and exits the maze, regardless of the maze layout!
You can construct this strategy as follows: enumerate all possible maze layouts $L_1, L_2, \dots$ (a crude upper bound on the number of mazes is $2^{49^2}$).
You can construct the sequence $S$ of moves iteratively. Initially $S$ is the empty sequence. Then, for each $L_i$ you can extend $S$ as follows:

Assume that the maze layout is $L_i$, and compute the position $p$ in which the player would end up by following the steps in $S$ from position $(1,1)$ in $L_i$.
Find a sequence $S_i$ of at most $49^2$ moves that make the player walk from $p$ to $(49,49)$ in $L_i$. This sequence always exists and can be found, e.g., with a breadth first search from $p$ in the graph induced by $L_i$.
Append $S_i$ to $S$.

The resulting sequence $S$ has length at most $2^{49^2} \cdot 49^2 < 2^{2413} = O(1)$.
Notice that the above algorithm is only needed to construct $S$ once and for all.
An algorithm that solves your original problem can just output the hardcoded strategy $S$, without even looking at its input.


Where does the CPU get its first instructions from? In order for the BIOS code to matter, it must be evaluated by the processor. However, the processor itself needs to do work to actually get access to the BIOS code, since the CPU only performs instructions that are given, something must give the instructions to the CPU (since I can't imagine a way for instructions to just "flow" from BIOS to the CPU without anything in between).

Where are the instructions for loading BIOS and passing control to it stored, and who passes these instructions to CPU so that CPU can preform them?

1. (A summary of the answer-in-comments by Jukka)

Startup code is stored in ROM (non-volatile memory) at a fixed address X.

When you activate the "reset" signal in the CPU, the CPU will initialise its registers to certain hard-coded values. The instruction pointer is one of these registers that are initialised to certain hard-coded values. In essence, the CPU manufacturer picks this hard-coded address X.
Hence, when you reset your CPU, the instruction pointer is reset to the same fixed address X. The CPU starts to execute instructions as usual: fetch the next instruction from address X, decode it, execute it, etc

Then whoever puts together a complete computer has to make sure that there is something useful at address X (e.g., a ROM memory chip with meaningful startup code).

2. Elaboration

The CPU has a very simple way of working, known as the FETCH-EXECUTE cycle:

(a)  FETCH: It goes to the memory and brings the instruction that
 is at address [PC].  (PC is a name of an internal CPU register; it
    holds the address of the instruction we need to perform next..).
(b) Execute: The PC executes the instruction it has just
    retrieved from the memory
(c) PC $\gets$ PC+1.(*)
(d) Go back to (a).

This fetch-execute loop happens all the time, regardless of the program you are running. In particular, when the CPU boots up (say, when its power goes from 0 to Vcc) the CPU simply begins to perform the above loop.

The initial value of PC depends on the specific CPU. It can be that the CPU wakes up with PC=0, or it can be that PC=0xFFF0 (as happens with Intel's X86 family), or with any other value PC=$PC_{init}$.
If you press the reset button, or turn the power off and on, the CPU  restores the PC to its initial value $PC_{init}$ and the CPU begins running the program that is in the memory at address $PC_{init}$, through the fetch-execute loop.

Now it is the computer designer task to make sure that the BIOS sits in the memory at address $PC_{init}$. The BIOS usually resides in a non-volatile memory so there is always a program to run in that address, even if you just turned the power off and on (this deletes the RAM but not the BIOS. It is more difficult to delete/change the BIOS, although possible and happens, e.g., when your device updates its "firmware").

(*) Advancing the PC by +1 assumes that each instruction takes 1 address of the memory space. The is rarely the case. In real systems we may see here PC+4 (as in the 32b MIPS) or PC+x (with $x\in\{1,...,7\}$ which depends on the instruction itself) as in the X86 family, etc.


Tokenization Problem Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult.

My Regular Expression experience is profoundly in JavaScript and I'm concerned that it poisoned my thinking of Regular Expressions. For the life of me I can't figure this out. Answer A and Answer B I can rationalize, though my logic might be inherently flawed somehow. Being unable to understand how Answer C works brings me to the conclusion that I am profoundly missing something.

The Problem:

Consider the string abbbaacc Which of the following lexical specifications produces the tokenization ab/bb/a/acc ?

Answer A
a(b + c*)
b+

Answer B
ab
b+
ac*

Answer C
c*
b+
ab
ac*

The two ways that I have tried to resolve Answer C

removing tokens(which I assumed is the correct way.)

abbbaacc

c* passes and returns token **cc**  //abbbaa
b+ passes and returns token **bbb** //aaa
ab passes and returns no token //aaa
ac* passes and returns no token //aaa
ending tokens:
[cc, bbb]

Keeping String Whole:

abbbaacc

c* passes and returns **cc**
b+ passes and returns **bbb**
ab passes and returns **ab**
ac* passes and returns **acc**
ending tokens:
[cc, bbb, ab, acc]

I've tried other random ways as well but nothing turns out. I really am frustrated with this problem and I've been working on it for quite some time. I've reviewed the coursework that I have and I'm just at a loss. I am convinced that I must be conflating the more common Regular Expressions with this but I don't see where I'm doing so in any way that would make this answer correct. If anyone could provide any assistance I would greatly appreciate it!

Tokenisation does not search. [Note 1]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.
Although there are other tokenisation algorithms, the most common one -- usually called maximal munch -- works as follows.
At each step:

Find the longest match of each pattern starting at the current input point. (This can be done in a single linear-time left-to-right scan of the input.)

Select the longest of all these matches. If more than one pattern has the same longest match, select the pattern which comes first in the list of patterns. Report the selected pattern and the corresponding matched prefix as the next token.

Remove the matched prefix from the input, and continue from the first step.

In effect, the match in the first step is a match of a regular expression created from the disjunction of all the patterns. The regular expression matching algorithm is modified so that:

It also reports which alternative matched, and

It leaves unmatched input in the input strean, rather than insisting that the regular expression match the entire input.

For your answer C, the regular expression created is $c^*+b^++ab+ac^*$.  (Some tokenisers would correct the first pattern to $c^+$ because selecting an empty match would cause the above algorithm to fall into an endless loop.)
The longest prefixes successively matched by this disjunction are:

$ab$ (3rd alternative). The 4th alternative matches $a$, but that us shorter.

$bb$ (2nd alternative) The second alternative will also match $b$, but that's not the longest prefix matched by this pattern.

$a$ (4th alternative)

$acc$ (4th alternative)

Notes

This should be intuitive. After all, most programs are read left to right and token order matters: $a = b + c;$ cannot be written as $a b c =+ ;$, and the parser will expect to see the tokens in left-to-right order, so if the lexer produced the stream,  $a b c =+ ;$, the parser would get confused.


How does the momentum term for backpropagation algorithm work? When updating the weights of a neural network using the backpropagation algorithm with a momentum term, should the learning rate be applied to the momentum term as well?

Most of the information I could find about using momentum have the equations looking something like this:

$W_{i}' = W_{i} - \alpha \Delta W_i + \mu \Delta W_{i-1}$

where $\alpha$ is the learning rate, and $\mu$ is the momentum term.

if the $\mu$ term is larger than the $\alpha$ term then in the next iteration the $\Delta W$ from the previous iteration will have a greater influence on the weight than the current one.

Is this the purpose of the momentum term? or should the equation look more like this?

$W_{i}' = W_{i} - \alpha( \Delta W_i + \mu \Delta W_{i-1})$

ie. scaling everything by the learning rate?

Using Backpropagation with momentum in a network with $n$ different weights $W_k$ the $i$-th correction for weight $W_k$ is given by

$\Delta  W_k(i) = -\alpha  \frac{\partial E}{\partial W_k} + \mu  \Delta W_k(i-1)$
where $\frac{\partial E}{\partial W_k} $ is the variation of the loss w.r.t. $W_k$.

Introduction of the momentum rate allows the attenuation of oscillations in the
gradient descent. The geometric idea behind this idea can probably best be understood in terms of an eigenspace analysis in the linear case. If the ratio between lowest and largest eigenvalue is large then performing a gradient descent is slow even if the learning rate large due to the conditioning of the matrix. The momentum introduces some balancing in the update between the eigenvectors associated to lower and larger eigenvalues.

For more detail I refer to

http://page.mi.fu-berlin.de/rojas/neural/chapter/K8.pdf


Selecting the right partition in NAUTY Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and attempt to further split the partition on more cells. What I found is that depending on the order of which you select cells during refinement, you can get different equitable partitions (at least up to the permutation of cells in the equitable partition). I guess this corresponds to the quote from Practical Graph Isomorphism II:

It is well known that for every colouring π there is a coarsest equitable colouring π' such that π' < π, and that π' is unique up to the order of its cells.

An example of this would be Example 7.7 (page 257), where selecting {1,3,7} instead of {2,4,5,6} will result in a permuted equitable partition

And more importantly these 2 equitable partitions can give 2 different certificates, so it is important to select the right order on the cells to get minimal among possible equitable partitions.

So my question is how does nauty ensure that during refinement it will find the “right” equitable partition and not lose the equitable partition that would potentially lead to the minimal certificate? In order words, among all (a) coarsest partitions how does it make sure to select the coarsest partition (because it selects just one equitable partition)?

After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected deterministically so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not necessarily give the certificate minimal among all possible discrete partitions, but rather minimal among some subset of them.


Are device drivers state machines? I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- i.e. do they read and write to memory, or not?

Many device drivers do read/write to memory.  For instance, consider a network device; it reads the packets to be sent from memory and writes the packets it receives to memory.  Or think of a hard disk driver; it does something analogous.   So, ultimately, it will depend on the driver.

That said, device drivers often do have a portion of their internal state that can be thought of a state machine.  For instance, the states could be something like UNINITIALIZED, ACTIVE, SUSPENDED, where it is initially in UNINITIALIZED state on boot; after it initializes the device registers, it could transition to ACTIVE state; on suspend, it might put the device into suspend mode and switch to the SUSPENDED state, and so on.  This only accounts for part of the behavior of the device driver, but it can still be a helpful way to organize the driver.  Or, in other words: often, some important aspects of the driver's behavior or state can be thought of as DFAs even though that's only approximately true.


how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?

The nice thing about small Boolean circuits like this, is there are only a few possible inputs.

With two input wires, there are $2^2=4$ possible inputs to your circuit: $00, 01, 10, 11$. You can test each one and write down its output. Then compare that to the XOR gate's outputs.

If the two line up, then the circuits are equivalent! And if they're not, something has to be adjusted.


How to simulate a parallel computer (with certain number of processors) on a serial computer I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor. I know the basics of GAs and I know how to design a GA algorithm to solve the TSP. I thought that this could be an example of an "embarassingly parallel" problem in the sense that I could assign each processor a fixed number of chromosomes (i. e, potential solutions, with solution meaning a given sequence of cities to be visited as specified by the chromosome) with the task of calculating the objective function for each of the assigned chromosomes. In this case, the objective function for a given chromosome is the inverse of the total distance described by that chromosome. The task of performing crossover and mutation would be carried out by a master processor. If this is a valid or reasonable way of parallelizing the problem, then there's no need for inter-processor communication during the objective function evaluation step and I can hardly see this as a truly parallel problem. Since minimum communication is needed, wouldn't the speed scale with the number of processors? What would we learn from such a simulation that we don't already know? I'll be grateful for any thoughtful answers.

The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard.  Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution.  This can be a good trade-off if you're programming, say, a driving-direction app, but it doesn't get around the NP-hard issue since it doesn't reliably solve the actual NP-hard problem.

Note that genetic algorithms are stochastic (probabilistic).  It's entirely possible that you could guess the exact best solution on the first go, or that you'd never guess it after a billion years.

  I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor.

As others have said, this will cause your program to run slower than if you hadn't split it up.  Parallel solution techniques are inefficient compared to single-threaded solution techniques; the only reason that we use them is to leverage additional processors.  If you don't actually take advantage of additional processors, you pay the cost for it without enjoying the benefit.

That said, almost all modern computers have multiple cores, even cell phones and tablets.  In the paragraph above, "processor" refers to a processing unit, which single CPU's have multiple instances of.  Your computer probably has at least 2 if it's a laptop or 4 if it's a desktop.

Also, note that processors often claim to have twice as many "logical cores".  When doing numerical problems, you mostly just care about physical cores; ignore the additional logical cores.  With Intel processors, this means ignore Hyper-Threading.  With AMD processors, this often means dividing their claimed count by two, since I think that they share floating-point units (FPU) between cores.  Those extra logical cores are useful in common computer tasks where there are thread waits and such, but they're usually harmful in scientific computing.

  Since minimum communication is needed, wouldn't the speed scale with the number of processors?

Ideally, if you get 100% parallelization efficiency, total speed is equal to the speed of each of the individual processors working individually, combined.  Lots of things detract from that ideal, including communication time.

As much as possible, you want to split the problem up into large chunks that a processor can focus on, then combine those chunks at the end, or at least infrequently.

Too much communication will actually make a bunch of processors working together slower than a single one working alone.  For example, consider

return a + b + c + d;  // Single-threaded calculation

If you split this up into

half1 = worker1.Add(a, b);
half2 = worker2.Add(c, d);
return half1 + half2;

, your program will run much slower than in the first case, despite using multiple cores.  The problem is even calling other threads costs far more than simply adding the numbers together, so you've slowed the program down by a huge factor as soon as you do the first worker call.

The trick to remember is that you want to call workers only when you have a lot of work for them to do while the current thread does a lot of work itself.  If that doesn't hold, then it's more efficient to just do the work in the current thread.

  What would we learn from such a simulation that we don't already know?

Nothing, really.  This is a common homework problem in many college classes on optimization, so it's been done hundreds of thousands of times before.  I'm assuming that this is part of one of your homework problem sets.

Conclusion

If you're in college, you may have access to a good version of Visual Studio through Microsoft Imagine (previously called DreamSpark).  If not, you can download Visual Studio 2015 Community (noting that 2017's in RC right now).

If you use C# in Visual Studio, it should be pretty straightforward to create your parallel genetic algorithm optimizer for the traveling salesman problem.  Since your PC's probably already multi-core, you can take advantage of the speed up from it.  But, even if it's not multi-core, you can still do multi-threaded runs, and the OS will interleave the threads to simulate a multi-core process.


Why is adding log probabilities considered "numerically stable"? Every once in a while, I come across the term numerical stability, which I don't really understand. In particular, I have seen a description of the practice of "adding logs rather than multiplying numbers" as "numerically stable." I would like to know why this is considered numerically stable.

By "adding logs rather than multiplying numbers" I mean that if you have several numbers, for example 0.01, 0.001, 0.0001, and you want to get their product, you can instead add the logs of each term. In this case assuming log base 10, the result would be -2 -3 -4 = -9. This doesn't give you the same output as multiplying, but it's a good way to get something like the product so that you don't experience numerical underflow.

My question is that I'm a bit confused because the definitions of numerical stability I've found on the Internet don't seem to apply to this case. The definitions of "numerical stability" I've found are that it occurs when a "malformed input" doesn't affect the performance of an algorithm, see for example here. In this case I don't really see how we would consider the numbers 0.01 etc "malformed," they are what they are. It would be more accurate to say that the algorithm (of multiplying them) is bad in this context since the computer can't handle it, so we choose a better algorithm. So why do people say this is "numerically stable"?

A "numerically stable" method calculates a result in a way that will not produce excessive rounding errors.

Given a small number x, let's say x = 0.00079, it is possible to calculate log (1 + x) with much higher precision than 1 + x. (Of course calculating log (1 + x) avoids adding 1 + x). In both cases the relative error will be small and about equal size, but since the logarithm is very small, it's absolute error is much smaller.

So if you want to calculate the product of values $1 + x_i$ for many small i, then you use a clever method to calculate $log (1 + x_i)$, add those values, and calculate the exponential. With probabilities, it is possible that you have say 1,000,000 events each with small probability $p_i$, and the probability that none of the events happens is the product of $1 - p_i$, and calculating that probability is more precisely done by adding logarithms (you would also keep the rounding errors down by always adding the two smallest values).

In other situations, using logarithms can be less precise. For multiplication, the relative error is independent of the size of the numbers. But if you add logarithms, and say their sum is around 100, then each addition loses precision because 7 bits of the mantissa are used to store the 100. The precision of your result will be much less. So it's quite the opposite of numerically stable.

Start with x = 1, y = 0. Then for i = 1 to 100, multiply x by i, and add log i to y. Then for i = 1 to 100, divide x by i, and subtract log i from y. Except for rounding errors, you should end up with x = 1 and y = 0. Check how much the difference is.

PS. How do we calculate log (1 + x) without calculating 1 + x? There is the power series around 1, $ln (x) = (x-1) / 1 - (x-1)^2 / 2 + (x-1)^3 / 3 ...$.  If we substitute 1 + x, then $ln(1 + x) = x / 1 - x^2 / 2 + x^3 / 3 ...$, which is obviously calculated without ever calculating 1 + x.

That's an important lesson: Given a problem that suggests an obvious sequence of steps to solve it, you will very often find a better and less obvious solution. To calculate log (1+x), the obvious sequence of steps is to calculate y = 1+x, z = log (y), but there is a much better solution that completely avoids the first step.


Regular expression for the language where every a is surrounded by b's I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b + bab)^*$. The teacher pointed out that my answer makes an $a$ surrounded by at least two $b$s, which isn't correct. I can't for the life of me figure out how to fix it to make it correct. Can anyone help?

Here is a regular expression for your language: $(b(ab)^*)^*$. It's not hard to check that every $a$ is bordered by $b$s in both directions. The other direction is more complicated and left to you.


Trouble understanding this proof about the minimum number of states of a deterministic finite automaton So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding why the proof of proposition 5 works in proving the statement.

My understanding of the proof is that we assume there's a DFA consisting of $<n$ states and we construct $n$ strings. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction.

I have two questions,

1) Do we have to make strings such that each would be in its own state or can we just make a set of any $n$ strings and so long as we can append something to each pair such that one of the strings in the pair is accepted and the other, rejected (leading to a contradiction)?

2) Does the proof imply that there is a DFA of exactly six states or just that there aren't any DFAs of five, four, three, two,or one state(s)?

Let $L$ be an arbitrary language. We say that two words $x,y$ are equivalent modulo $L$, written $x \stackrel{L}{\sim} y$, if for all words $z$, either both $xz,yz$ are in $L$, or both are not in $L$.

Lemma 1. Suppose that $x_1,\ldots,x_n$ are pairwise inequivalent modulo $L$. Then any DFA for $L$ must contain at least $n$ states.

Proof. Consider a DFA accepting $L$. Let $q_i$ be the state that the DFA reaches after reading $x_i$. I claim that $q_1,\ldots,q_n$ are all distinct. Indeed, consider any two states $q_i,q_j$. Since $x_i,x_j$ are inequivalent modulo $L$, there exists a word $z$ such that $x_iz \in L$ and $x_jz \notin L$, or vice versa; without loss of generality, assume the former. Since $x_iz \in L$, $\delta(q_i,z)$ must be an accepting state, whereas since $x_jz \notin L$, $\delta(q_j,z)$ must not be an accepting state. This shows that $q_i \neq q_j$. $\quad\square$

This is the method which is used in Proposition 5 that you mention.

What is the best lower bound that Lemma 1 can give us? Once you notice that $\stackrel L \sim$ is an equivalent relation, it is not hard to check that the maximum $n$ that you can choose is the number of equivalence classes of $\stackrel L \sim$:

Corollary 2. Any DFA for $L$ must contain at least $n$ states, where $n$ is the number of equivalence classes of $\stackrel L \sim$. In particular, if $\stackrel L \sim$ has infinitely many equivalence classes, then $L$ is not regular.

It is natural to ask whether this method is optimal:

If $L$ is not regular, can we always prove this using Corollary 2?
If $L$ is regular, is there always a DFA having $n$ states?

The positive answer to both questions is the main result of Myhill–Nerode theory, which you might learn about in the future.


What are some undecidable problems for recursive languages? When we say a class of languages is decidable we mean that the membership problem can be solved. However even though the membership problem is solvable for the class, there may exists some problems for the same class which are undecidable. For example Context free languages are decidable yet the problem of determining whether the language generated by context free grammar is unambiguous is undecidable.

I want to know some undecidable problems for recursive languages. Please don't problems related to context free and context sensitive language and then say that these languages are also recursive. The problems I want must be for only recursive languages and not for any proper subset of this class.

For recursive languages, membership is decidable by definition, so most undecidable questions with regards to them will involve quantifiers. It's decidable to check if there's a given input is accepted, but it's undecidable to check whether a recursive language accepts any string, for example.

That said, questions like this are almost never phrased in terms of recursive languages, because there's representation of languages that captures exactly the recursive languages. Generally we represent languages as Turing Machines, but these characterize the recursively enumerable languages.

When it comes to RE, there's something called Rice's theorem,which says that any non trivial property of RE languages is undecidable. This holds for anything that's a property of the language itself, not just the specific representation.


are they any implications if i reduce a sha256 result into 248 bits? i am working a prototype using some cryptographic properties.
the question is simple but perhaps deep enough for me to decide :

sha256 is a strong hash function, but i have space for 248 bits only.
my guess is if i remove any 8 bits the resulting mySHA248 will keep
all good properties with slightly less entropy/collision resistance.

You will get slightly more collisions, which is not a problem in many use cases, but overall hash properties are preserved.

If some hash loses its properties by omitting last few characters (or any selected ones), then hash is flawwed by having internal correlated structure.

In fact, NIST publication effectively trims hash to desired number of bits.


Why are palindrome and not-palindrome both context-free? Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two NCFLs that makes complement work?

You make the mistake of assuming that

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$

while in truth

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.

In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.

As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,

$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.

The complement is a nice exercise and can be found elsewhere on the site.


How does the function to curry and uncurrying another function work? The following is the code to curry or uncurry a function in Haskell:

curry :: ((a, b) -> c) -> a -> b -> c
curry f a b = f (a, b)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (a, b) = f a b

I can understand the type signature part but not the function definition. Would you please explain me how those function bodies turn a curried function into an uncurried one and vice versa?

The meaning of curry can be easier to be seen when the type signature is written as

curry :: ((a, b) -> c) -> (a -> b -> c)

that is, a function taking a single parameter of type (a, b) and yielding a result of type c is turned into a function taking two separate values of types a and b yielding the same result type c.

We might define curry for this signature like this:

curry f = g

where f :: ((a, b) -> c) and g :: (a -> b -> c).

f is passed by the user, but how do we get g? We know g is a function taking two parameters and yielding a result type, so it must structurally look like \x -> \y -> z, where x :: a, y :: b, and z :: c (\v -> e is the syntax for lambda-expressions in Haskell). We now have to find a way to get the result z from x and y such that the types work out correctly.

As both result types c must be the same, the only way to get z is to use f and apply it to a value of type (a, b). So we know z = f (?, ?) where (?, ?) must have type (a, b). Where do we get values of these types from? Again, as the types must match exactly, the only option is to use x and y here. We get

curry f = g
    where g = \x -> \y -> f (x, y)

This would be a proper implementation for curry. One that is easier to read is to inline g:

curry f = \x -> \y -> f (x, y)

As Haskell allows us to define functions with multiple parameters, we can resolve the lambda-expression and simplify this to

curry f x y = f (x, y)

which is (beside different variable names) the same implementation as in your question.

For uncurry the procedure is similar (note that you had missing parentheses in the type signature for uncurry in your original question which lead to a different type).

From

uncurry :: (a -> b -> c) -> ((a, b) -> c)

we conclude

uncurry f = g
    where g = \(x, y) -> z

with f :: (a -> b -> c), g :: (a, b) -> c, x :: a, y :: b and z :: c. Following the types, z can only be defined by z = f x y. From that we get

uncurry f = g
    where g = \(x, y) -> f x y

and after inlining g and removing the lambda

uncurry f (x, y) = f x y


Proving that a spanning tree of graph is not a minimum Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$.

Now I assume that there exists a spanning tree of $G$, let's call it $T'$, that has a path from node $u$ to node $v$ with all edges in a path from weight $<w_i$ for some $1 \le i \le n-1$. And I assume that the path from $u$ to $v$ in $T$ has at least one edge with weight $\ge w_i$. I other words, the path from $u$ to $v$ in $T$ has an edge which is heavier than all the edges in the corresponding path in $T'$.

I need to prove formally that $T$ is not a MST.

What I've tried is to somehow find a tree which is of less wight than $T$ using Kruskal's algorithm, but I couldn't manage to do it.

If you remove that edge you mentioned with weight $\geq w_i$ from $T$, then the new $T$ has two components (because it's a tree). But one of the edges on the cheap path connecting $u$ and $v$ in $T'$ would reconnect these two components in $T$. And the substitution saved you a bit in terms of weight.


Is the language of all TMs accepting all strings starting with 010 decidable? I am trying to figure out if this language is decidable:
$$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$

My intuition is that it is. Whatever string $w$ starts with 010 it accepts, and if it doesn't it rejects.

According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.

$\qquad$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $M_1$ and $M_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M_1 \rangle ,\langle M_2\rangle  \in L$ or $\langle M_1 \rangle ,\langle M_2\rangle \notin L$.

Property 2 (Non-trivial) − There exists $M_1$ and $M_2$ such that $\langle M_1 \rangle \notin L$ and $\langle M_2 \rangle \notin L$.

Now,

$\quad$ 1) For any two TMs, $M_1$ and $M_2$ with $L(M_1) = L(M_2)$ either both $M_1$ and $M_2$ both accept all strings starting with 010 or both don't accept.

$\quad$ 2) There exists TMs that accepts strings starting with 010 and not accepting strings that starts with 010.

Therefore, the property of the language of a TM to start with 010 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$L$ is recognizable as TMs that accepts when given as input strings starting with 010 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).


Simple paths with halt in between in directed graphs I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$.

Find a simple directed path¹ from $s$ to $t$ through $v$.
Find a simple directed path from $s$ to $t$ that goes through two fixed edges in $G$.

I do not know if there are polynomial time algorithms for them. Does anyone have solutions or references for them?

A simple directed path does not allow any vertex to appear more than once.

As Tsuyoshi Ito notes, the first problem can be solved using network flow. This was described in detail in cstheory.