How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra? At 15:30 in this talk  (p13 of this presentation here) Rich Hickey mentions the formalisms available for reasoning about Communicating Sequential Processes. He then goes on to mention that these haven't yet been applied to Clojure's core.async.

The only reference I know of for CSP is Hoare's book. I can see some examples of formalisms to describe CSP here.

Suppose I wanted to do the most basic of CSP as per Rob Pike's presentation in Go (slide 43 of this).

var (
    Web = fakeSearch("web")
    Image = fakeSearch("image")
    Video = fakeSearch("video")
)

type Search func(query string) Result

func fakeSearch(kind string) Search {
        return func(query string) Result {
              //time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
              return Result(fmt.Sprintf("%s result for %q\n", kind, query))
        }
}

How would I express this as an Algebraic statement? What benefit would it give me?

Taking a stab at it - I get

(Web → P) Π (Search → Q)  Π (Video → R)

Which tells me that the Search process can choose to interact with Web or Video depending on which environment the Search Process chooses to communicate with.

Assumptions

I'm told that you can't do this in pure CSP because of the timer. For an answer I'm happy to  assume we'll ignore the timer part of this.

As to the question what benefits it would give you, the answer is simplicity.

Modern programming languages are large beasts with complicated semantics, starting with syntax, and not ending with the rules for integer and floating point arithmetic (real languages, as you know, don't work with 'mathematical' integers and reals, but rather with finite approximations). A calculus boils programming languages down to some essentials of interest, in the case of CSP to agents that synchronise on names. This makes thinking about, and proving things to do with synchronisation much easier than doing so using a fully blown programming language. If you are not primarily interested in looking at computation from the point of view communication patterns engendered by synchronisation, then, maybe, CSP is not the right calculus for you.


Is "backward substitution" and "backtracking" the same thing? From my limited knowledge, they both are related to solving recurrence relation.
Solving recurrence relation using backward substitution
Solving recurrence relation using backtracking

Can the terms be used interchangeably?

In terms of algorithm, I found the following:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. wiki

Backward substitution is a procedure of solving a system of linear algebraic equations Ux=y, where U is an upper triangular matrix whose diagonal elements are not equal to zero. The matrix U can be a factor of another matrix A in its decomposition (or factorization) LU, where L is a lower triangular matrix. This decomposition can be obtained by many methods (for example, the Gaussian elimination method with or without pivoting, the Gaussian compact scheme, the Cholesky decomposition, etc.). Here we also should mention the QR decomposition when the matrix A is represented in the form A=QR, where Q is an orthogonal matrix and R is an upper triangular matrix. Since the matrix U is triangular, a procedure of solving a linear system with the matrix U is a modification of the general substitution method and can be written using simple formulas.
A similar procedure of solving a linear system with a lower triangular matrix is called the forward substitution. Note that the backward substitution discussed here can be considered as a part of the backward Gaussian elimination in the Gaussian elimination method for solving linear systems.
There exists a similar method called the backward substitution with normalization. The scheme of this modification is more complex, since a number of special operations are performed to reduce the effect of round-off errors on the results. algowiki

Are backward substitution and backtracking the same in terms of
recurrence relation?

Is backtracking algorithm is the same as the recurrence relation's backtracking?

Is backward substitution (same as back substitution?) in recurrence relation the same with backward substitution algorithm?

Is backtracking algorithm the same as backward substitution?

What are their relations to each other?
backtracking (recurrence relation) - backtracking (algorithm) - backward substitution(recurrence relation) - backward substitution(algorithm)

Can the terms be used interchangeably?

Backward substitution is a specific method to solve a particular problem: a linear system of equations;
Backtracking is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial solution to a complete solution.

This should answer your "can the terms be used interchangeably?" questions: no, they can't.
Imagine you are solving a crosswords puzzle. One algorithm would be: for each definition, find the list of possible words; then try every combination of those words and check if that combination solves the puzzle. This is a bruteforce approach and pretty inefficient. A much better approach is to use backtracking: for each definition, find the list of possible words; choose a word for the first definition; choose a word for the second definition; check immediately for any inconsistency between the two chosen words. If they are inconsistent, "backtrack" by choosing a different word for the second definition. If you run out of words for the second definition, "backtrack" even further by choosing a different word for the first definition. Only if they are consistent, move on to the third definition. This is a backtracking algorithm. Backtracking algorithms are often very straightforward to implement using recursion.
Backward substitution is a method to solve a system of linear equations. A system of linear equations is something that looks like:
a x + b y = c
d x + e y = f

As you can see it is a very specific problem. There is no notion of recursion here. Linear equations are often written in matrix form: A X = B; in my example, A = ((a b)(d e)), X = (x y) and B = (c f).
The article you linked mentioned "recurrence" because they had a problem with cascading linear equations; the linear equations are called a "recurrence relation" because they define a sequence, where X1 = A X0, X2 = A X1, X3 = A X2, etc.


What is a good method for modelling combinatorial tree (sport competition results)? Probably newbie question here, please point me out to relevant theories/tutorials if needed :

let say I want to evaluate the probabilities of the final rankings for a sport competition
the competition involved 8 teams, but I can simplify the problem to 4 contestants (say A - B - C - D)

the competition is splitted into n journeys during which every team faces another team (and only one). So with 4 contestants, I have 2 matches per journey
at the end of a match, 6 different points attributions are possible (depending on the score)

After one journey, there are 36 different possible combinations in terms of team's points. So the model looks like a tree with a journey at each level.

Even if I simplify the situation to 2 journeys left, I can't think of a elegant way to implement this problem rather than "manually" creating the tree with all the possible combinations at each level and counting the leaves ?

I'm not familiar with this kind of problem so I'm not sure about the path forward.

I can't follow how you get 30 combinations, you have 2 matches per journey each of the 2 matches can result in 5 different attributions, so you get 5*5 = 25 different attribution per match. At each journey there are 3 possibilities to make 2 matches. So the result would be 25/3 + 25/3 + 25/3 = 25 different point attributions.
Did I got something wrong?

You want to calculate how many different point attributions there are after n journeys and the probabilities to make a match are the same for every combination at every journey?


Nearest Neighbor Search in Spherical Coordinates I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. Then given these points in their spherical coordinates how can I go about determining their NN. I need an algorithm that is efficient (relatively) and more importantly accurate.

EDIT: For sake of argument and for the philosophical point let's accept the 'loss of information' to quickly summarize my research in astrophysics does not allow me to simply convert to Cartesian coordinates and use a nearest neighbor algorithm due to the universe expanding and me dealing with something called redshift. TLDR: I cannot convert to cartesian and must use an algorithm in spherical coordinates for nearest neighbor.

Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates.

I don't understand this restriction. Converting to Cartesian coordinates uses essentially the same trigonometric functions that you would need to find the distance between two points in spherical coordinates: the only fundamental difference is that working directly in spherical coordinates you can take the cosine of the difference of azimuthal angles rather than taking sine and cosine of the individual azimuthal angles.

In any case, you should be able to bound the error in converting to Cartesian coordinates and take that error bound into account to create a shortlist of candidates using k-d trees; then recalculate the distances for the points in the shortlist using the spherical coordinates directly.


How does node expansion work in a graph for AI search? I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city in Romania called Arad to Bucharest and the problem can be expressed as a graph like in the following image:

If when constructing the graph a Node holds a reference to its parent, the action that was applied to get there and the current state at that node plus the path cost, how would node expansion work?

I am not sure how I can expand Arad to give the three nodes attached because Arad does not hold a reference to its children, instead the children hold a reference to Arad.
** Edit I am now thinking (whilst I am still unsure how a node is expanded) that child nodes are not built until a node is expanded. Is this correct?
I could maintain a mapping between a node and its children as a hashtable or something like this but I don't think this would scale to a larger problem where there the journey were much larger.
Equally I could search all nodes at expansion time and then find which have Arad as their parent if I kept some sort of information about each node such as its number in the graph\tree, or the easiest would be for each node to hold a reference to all its child nodes but this does not match the description of a node and its properties specified in the book.
Can somebody explain how node expansion should work in a graph as I am guessing at how I might do it which might not be right.

It seems to me that you are confusing the graph itself with the search tree produced by some search procedure.
As you state, you can't go from one node to the next unless that node knows its neighbors (and not only its own parent). But the search tree is (perhaps implicitly) generated from a search procedure you perform on the actual graph. Perhaps this is what the authors mean with the description you quote.
The actual graph on which you do a search in you can represent via an adjacency list. There, given a node, you can locate its neighbors and the search progresses using that information.


NFA state complexity for the complement of EPAL restricted to a fixed length I've been having trouble proving the next statement:

  Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA with at most $O(n^2)$ states.

What I've been trying to do is that the complement of $L_n$ is

$\qquad\displaystyle L^c_n = \{w , |w| \not = 2n\} \cup \{ww', w \not = w'\}$.

I want a hint on what to think to prove this thanks!

Hint: further break up the difficult case $\{ww' : |w|=|w'|=n,w\neq w'\}$ as a sum $$\bigcup_{i=1}^n \{ \Sigma^{i-1} \alpha \Sigma^{n-i} \Sigma^{i-1} \alpha' \Sigma^{n-i} : \alpha \neq \alpha' \in \Sigma \}. $$
In total there are $n+1$ cases (including $\{w : |w| \neq 2n\}$), so if you can implement each one in $O(n)$ states, you're done.


Clock solitaire game and principle of deferred decision I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. The example they provided is a clock solitaire game. The game is as follows. Initially 52 cards are randomly grouped into 4 cards of 13 piles. The piles are labeled $1,2,3,...,10,Q,J,K,A$. The game starts by drawing a card from $K$ labeled pile. The next draw will be taken place from the pile with the face value of the drawn card. For an example suppose the drawn card is 7, then we go to the pile labeled $7$ and pick a card from this pile. We continue in this fashion. The game ends when we reach an empty pile. And one wins if all the piles are empty when the game ends. It is easy to show that the last card drawn must have face value $K$.

Now, to analyze the probability of winning, the author assumes a different probability space named "Principle of deferred decision". The idea is to "let the random choices unfold with the progress of the game, rather than fix the entire set of choices in advance." With this, they conclude that the probability of winning i.e., the probability that 52nd card being $K$ is 1/13. Can anyone explain why this is 1/13?

You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the game does stop. From that point of view, what we have is a completely random order of the deck; the game stops once the fourth king is reached; we win if the fourth king is the last card. Now the probability that the fourth king is the last card is the same as the probability that the last card is a king, which is 1/13.


Concentric convex hulls Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a convex hull possible, we move all these points to a visited set and continue. Every time we determine a convex hull, we only move the points to the visited set if the so constructed convex hull contains all the points from the visited set.
How can we do count such convex hulls in as efficient manner as possible?

It seems you are trying to perform onion peeling(convex layers) from the inside out, which is not possible.
A convex hull of given points is a polygon that contains all given points either on itself or inside it.
To solve the problem you have described you must generate a convex hull using an algorithm of choice. Now that you have the outer layer, for the inner layer, use the same algorithm and only supply the points inside the convex hull.

The pseudo code would be:
 for given dataset:
   generate a convex hull
   remove the points that make the convex hull from the dataset
   loop until the dataset has no points or more than 2(since a convex hull requires at least 3 points).


Inductive proof for Euclid's algorithm I'm studying The Algorithm Design Manual and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the exercises two days ago and I still haven't been able to go through the whole page.
Anyway, I'm trying to inductively prove Euclid's algorithm(I'm think the deductive proof is simpler but I want to familiarize myself with Inductive proofs). No matter how I approach the problem, I just prove the algorithm in a deductive way that doesn't require induction in any way.
I would really appreciate if you could give an inductive proof of Euclid's algorithm or provide me with a resource that does so.Thanks in advance.
The greatest common divisor of positive integers x and y is the largest integer
d such that d divides x and d divides y. Euclid’s algorithm to compute gcd(x, y)
where x > y reduces the task to a smaller problem:

gcd(x, y) = gcd(y, x mod y)

Prove that Euclid’s algorithm is correct.

Edit:
The deductive proof that I know of is as follows:
A. given that a,b,c,y,x are all integers we can prove:
a|b ^ a|c → a|(xb + yc)
B. p,q,r and t = (pr + q) are all integers.we want to prove gcd(pr+q,p)=gcd(p,q)
let m = gcd(pr+q,p) and n = gcd(p,q)
since A, n|p ^ n|q → n|pr + q
n is a common divisor of (pr+q,p) and m is the greatest common divisor of (pr+q,p) therefore, m >= n.
C. P: m|p which we know is true
Q: m|(pr + q) which is also true
R: m|q
we know that m|p ^ m|q → m|pr + q is true, so based on this and P,Q and R we can deduce that R is true.
m is a common divisor of (p,q) and n is the greatest common divisor of (p,q) therefore, n >= m.
B is true
Q is true
B ^ Q → m = n is also true.
therefore, m = n
gcd(pr+q,p) = gcd(p,q)

Here is Euclid's algorithm.
The input is two integers $x \geq y \geq 1$.
While $x > y$, the algorithm replaces $x,y$ with $y, x\bmod y$.
The final output is $x$.
In order to prove that this algorithm correctly computed the GCD of $x$ and $y$, you have to prove two things:

The algorithm always terminates.
If the algorithm terminates, then it outputs the GCD (partial correctness).

The first part is proved by showing that $x + y$ always decreases throughout the loop. The second part is proved by induction, using the equation $$ \mathit{gcd}(x,y) = \mathit{gcd}(y,x\bmod y). $$
Both parts also use the loop invariant $x \geq y \geq 1$.
What you call the "deductive proof" is only part of the proof of partial correctness. It forms the main technical part inside a proof by induction on the number of iterations.


First-order logic arity defines decidability? I've read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that's propositional logic, correct me if I am wrong)

The question is why arity leads to undecidable problems?

I would like to see some reference material, or at least some simple example of it, as a way to think in this passage from unary to n-ary and why it leads to undecidable problems.

Logic with unary predicates (not operators), is called monadic. The thing that is called propositional logic only has nullary predicates, i.e., constants true and false, and no quantifiers.

The undecidability of predicate logic follows because predicate logic (with at least one binary predicate) is powerful enough to describe how a Turing machine works, and so we can express in the logic sufficiently complicated statements about Turing machines to get undecidability. In contrast, in monadic logic, where we only have unary predicates, we cannot describe the working of a Turing machine. I am being deliberately vague here to give an idea without getting bogged down in technicalities.


Space-unconstructable function in the proof of Savitch's theorem I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it.

The proof I'm talking about is the same as is currently on Wikipedia. It starts by describing a function - let's call it CAN_YIELD(start, end, limit) for now.

It is then said that the non-deterministic Turing Machine can be simulated by a deterministic Turing Machine by calling CAN_YIELD(start_state, end_state, f(n)).

The proof then continues by describing that the function takes O(f(n)) space for one configuration and O(f(n)) for the recursion of the function. This nicely results in O(f(n)^2) which is the result we want.

The issue is that if the f(n) is not space-constructible, we don't know what limit number we should input into the CAN_YIELD function. I've seen some proofs saying that we can add something like a 'size' parameter and check if it is large enough - but again, we don't know the actual f(n) value, so I don't understand how this works.

One example of such proof can be found here. Another instance is this answer that states that we can replace the space-constructability requirement of the function by using a fixed space bound, which we increase after every iteration. Same issue as before, I don't see how that might work without knowing when to stop.

I'd be happy for any insight into this issue, or any corrections made to my statements!

Starting Point:        For inputs x, if    [there is no sequence of choices

which makes the non-deterministic machine accept x]  and

[for all positive integers S, there is a sequence of non-deterministic choices that,

when made for input x, will cause the non-deterministic machine to use more than S space]

then on input x, the deterministic machine is allowed

to run forever with no bound on its space usage.

Otherwise, such simulation would suffice for solving the halting problem:

Run the simulator until it halts or loops, then output accordingly.

With that in mind, the simulation works as follows:

S = 1
while True:
    run CAN_YIELD with space-bound S
    if that accepts then accept
    increase S by 1
    for end_state in configurations_at_which_the_nondeterministic_machine_might_have_just_used_more_than_space_(S):
        run CAN_YIELD with space-bound S and end_state
        if that accepts then break out of the for loop
    if the for loop ended without a break then REJECT


Understanding tables in Dynamic programming I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

While I was able to solve this in a linear fashion, I came across lots of solutions that used DP, like the one below,

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

I'm having a hard time understanding this. I've solved a few DP problems that involved grids (shortest path in 2d grid, largest square in binary 2d grid),  using a DP table there made perfect sense to me. However here I'm completely lost, I'm unable to understand how traversing a 2d table helps in solving this problem. Further more it appears we know when the characters don't match in the loop, so I don't understand why we don't terminate the search there (this is also probably due to my lack of understanding of how a table traversal leads to a solution). Is there a clear intuitive explanation for problems like these?

dp[i][j] represents whether text[i..] matches pattern[j..].

If pattern[j..] is starting with x* for some symbol x (including .), then text[i..] matches pattern[j..], or x*pattern[(j+2)..], if and only if

text[i..] matches pattern[(j+2)..] (i.e. x* matches an empty string), or
text[i] is x and text[(i+1)..] matches x*pattern[(j+2)..] (i.e. x* matches a non-empty string).

This is implemented by this part of code:

if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
}

On the other hand, if pattern[j..] is not starting with x*, text[i..] matches pattern[j..] if and only if text[i] matches pattern[j] and text[(i+1)..] matches pattern[(j+1)..]. This is implemented by this part of code:

else {
    dp[i][j] = first_match && dp[i+1][j+1];
}


Greedy algorithm for submodular optimzation In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to deal with it if $f$ can take values in the reals.

Problem: Given a monotone submodular function $f$ (whose value would be computed by an oracle) on
N = {1, 2, . . . , m}, find the smallest set S ⊆ N such that f(S) = f(N).

A greedy algorithm for this problem is as follows:

$S \leftarrow\emptyset$
while $f(S) \neq f(N)$ {
____find $i$ to maximize $f(S+i)-f(S)$
____set $S \rightarrow S\cup \{i\}$
}
return $S$

Question: Show that this is a $1+\ln f(N)$ approximation algorithm.

An argument is as follows: If $O$ is an optimal set, we can show that for the $i$ chosen in line 3 of the algorithm,

$$
f(S+i) - f(S) \geq \frac{f(N)-f(S)}{|O\setminus S|} \geq \frac{f(N)-f(S)}{|O|}
$$

Now letting $S_k$ denote the set $S$ after the $k$'th iteration (so $S_0=\emptyset$), and $z_k = f(N)-f(S_k)$ i.e., $z_k$ the "amount left" after the k'th iteration (so $z_0=f(N)$), the above inequality implies

$$
z_k \leq z_{k-1} - \frac{z_{k-1}}{|O|} = \left(1-\frac{1}{|O|}\right)z_{k-1}
$$

And therefore
$$
z_k \leq \left(1-\frac{1}{|O|}\right)^{k}f(N) \leq f(N)\exp(-k/|O|).
$$
Setting $k=|O|(1+\ln f(N))$, we have $z_k<1$, and because $f$ takes only integral values, it must be that $z_k=0$.

But the question does not stipulate $f$ take only integral values. How can you deal with an $f$ that takes non-negative reals?

The claim isn't true in general. Given a monotone submodular function $f$ and a positive constant $C$, let $g = f/C$. The algorithm is oblivious to the change from $f$ to $g$, and on the other hand $1 + \ln g(N) = 1 + \ln f(N) - \ln C$. In particular, by choosing $C$ large enough, you can get that the approximation ratio is any small enough number (even smaller than one or smaller than zero!).


A little help with regular expressions I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet:
all words that do not contain the substring "bbc"

I am having a really hard time understanding how to approach this question. I have done several other questions where a certain substring must be excluded, but this one really messes with my logic.

Thanks in advance

Some things I learnt while learning to answer this type of question:

Negation isn't easy to express. There are no shortcuts. The resulting expressions may be far more complex than the expression you would get if negation was a basic operator in the expression language - in which case you could write $\neg(.^*bbc.^*)$, where $.$ is a shortcut for $(a\cup\neg a)$
Lacking $\neg$, the only way to say $\neg a$ for some symbol $a$ is to enumerate all other symbols: $\neg a = (b\cup c \cup d \cup \ldots)$. In Unix-like regular expressions, you can of course use [^a].
In compound expressions, you can use left factorization.
E.g. $\neg(bbc) = \epsilon \cup \neg b\neg(bc) = \epsilon \cup \neg b(\epsilon \cup \neg c) = \ldots$.
The key insight is that this can be made to work with Kleene star expressions, too; I suggest you invent or look up the details yourself.


Halting problem for polynomial space bounded Turing machines A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable.

I do not understand why is halting decidable for this problem because $f$ is unknown to us.

You don't need to know $f$. It is sufficient to use the fact that there are only finite possible configurations.

Given an input $\langle \langle M\rangle,w\rangle$ where $M$ is a polynomially bounded TM, simulate $M$ on $w$ and record its configuration at every step. Whenever we find a repeated configuration, we can assert that $M$ does not halt on $w$.

Note if $M$ does not halt on $w$, it must experience a repeated configuration, so the process described above will always halt. Therefore this process is the decider for the halting problem.


Find interval sums with minimum number of operation Input:

A list $A=a_1,\ldots,a_n$, with $\oplus$ a associative operation on $M$, and $A\subset M$.
pairs $(s_i,t_i)$ for all $1\leq i\leq m$.

Output:
The list $b_1,\ldots,b_m$, where $b_i = \bigoplus_{j=s_i}^{t_i} a_j$.

We want an efficient algorithm to compute the output, such that it uses minimum number of $\oplus$ operations.

For example, if we have $m=2$ and want to find the sum on interval $(1,n-1)$ and $(2,n)$, then the best way is to first compute $t = a_2\oplus \ldots \oplus a_{n-1}$, then compute $b_1 = a_1\oplus t$ and $b_2 = t \oplus a_n$, using $n-1$ operations.

Note it is possible that we have to use $\omega(n)$ operations, consider we have the input that contain all pairs $(i,j)$, where $1\leq i\leq j\leq n$. This would require at least ${n \choose 2}$ operations, because there could be ${n \choose 2}$ different values.

Assume all elements in $M$ take $O(1)$ space. We also want to use as little additional memory as possible.

This problem was solved recently. The naive greedy algorithm works.

David Basin, Felix Klaedtke, Eugen Zălinescu, Greedily computing associative aggregations on sliding windows, Information Processing Letters, Volume 115, Issue 2, February 2015, Pages 186-192, ISSN 0020-0190


Using singly linked list instead of a doubly linked list? Are there advantages of implementing a singly instead of a doubly linked list other than space?

Other than saving space, the first advantage I can see for singly
linked lists over doubly linked lists is to avoid having to update two
links instead of one when you modify the list, when adding an element
for example.

Of course, one might say that you can always ignore the second link,
but in that case, it is no longer doubly linked, but only an unused
field.

What might also be seen as an advantage is that singly linked list are
necessarily consistent, though possibly wrong when there are bugs in
the program.  Doubly linked lists can end-up having inconsistent links
forward and backward. But it is debatable which of the two cases, if
any, is an advantage.

update:

I had tried to see some impact on garbage collection, but found
none. Actually, there is one when storage reclamation is done by
reference counting, as reference counting is defeated by loops, and
doubly linked lists contain loops. Singly linked list escape the
problem. Of course, there are ways around it for doubly linked lists,
such as the use of weak pointers, or programmable reference counting
as part of data abstraction.


Efficient Algorithm for determining who wins a game of Chess I was reading Jeff E's lecture notes on Algorithms when I came upon the following question:

Describe and analyze an efficient algorithm that determines, given a legal arrangement of
standard pieces on a standard chess board, which player will win at chess from the given
starting position if both players play perfectly. [Hint: There is a trivial one-line solution!]

My only thought is to form a tree of possibilities and go down every tree to see where it ends. But this is neither one line or efficient. Any help is appreciated(I prefer hints to full solutions, and I will accept a hint as an answer if it leads me to the answer).

When talking about standard chess with an $8\times 8$ board, there is no asymptotics, so you can solve the problem in $O(1)$ time.

Your idea works fine, since for each position the size of the tree is bounded by some constant independent of the input (the tree size is bounded by the number of possible positions). You can now ask whether this solution is feasible or has any practical implications? The answer is obviously no, but when analyzing the asymptotic complexity of the algorithm, this doesn't matter.


Asymptotics question Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?

I am really stuck and I tend to believe it's true, but I don't know how to prove it.

Any help would be appreciated!

We have
$$
\frac{n!}{(n/2)!(n/4)!\cdots 2!} =
\frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\
\binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.
$$
Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.


Find all group of neighbors with a constraint weight Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs.

I have nodes that have weights with each other. I want to find all unique groups of nodes, with the constraint that every node in the group has a weight with every other node a value that is less than a certain pre-specified constant.

Let's take an example. The following is a table of weights where the row number and column number can be considered as node numbers.

6   15   25    4    6    1    4
15  28   19   20   15   28    6
25  19    4   26    2   10    2
4   20   26   15    1   15   29
6   15    2    1   13   20   15
1   28   10   15   12    5   16
4    6    2   29   15   16    7

Considering a weight limit of 15 the result I generated using my brute force solution looks like the following:

1  5  4
1  6  4
1  7  5  2
1  7  6
2  7  5  3
3  7  5
3  7  6
4  5
4  6
5  7
6  7

Now consider the first result 1 5 4 the weight between 1 and 5, w(1,5)=6; w(1,4) = 4; w(5,4) = 1. we can't add node 6 to this group because w(5,6) = 20.

The solution I have now takes forever when the dataset is larger. Is there an optimized algorithm that I am missing? Thanks for the help.

Your problem is the same as listing all cliques in a graph.

Given your weight matrix, construct a graph in which two vertices are connected if the weight between them is below the threshold. A clique in this graph is the same as the sets of vertices you are interested in.

A graph could contain exponentially many cliques - even exponentially many maximum cliques (consider for example $n/3$ paths of edge-length 2). So in general you will need exponential time to list all cliques.


What is the motivation behind restore model of computation? The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory.

$\textit{Model of Computations}$

Word RAM : This a very well known model of computation.
Read-only word RAM: Where input memory is assumed to be read-only.
Permuted word RAM: Allow input memory to be permuted but not destroyed.
Restore model: This is a variant of permuted word RAM model, where the input memory is allowed to be modified during the process of answering a query, but it has to be restored to its original state afterward.

I know that why word RAM is the interesting model of computation in many cases but I don't have any idea what is the motivation behind studying problems in 3 and 4. Let us take the example of DFS(Depth-first Search). I know that the problem has been studied in word RAM and I also know about the space complexity of it in that model. I recently come across one paper in which DFS (see this) has been studied in 4th model of computation. The result is that DFS and BFS in place memory in linear time.

Question: What is the motivation behind restore model of computation?

The restore model is semantically identical to the read-only model. Both models are natural since you expect operations on objects to not alter them. For example, imagine running a query on a database. You don't want the query to modify the database, but you might not mind if the database is temporarily changed while running the query, as long as it is restored to its original state in the end.

(In fact, in this particular you might care, for many reasons: perhaps several processes access the database in parallel; or perhaps you are worried that a failure will stop the process in the model, thus leaving the database in a modified state. These are reasons why you'd sometimes prefer the read-only model.)

The restore model is more powerful than the read-only model, in the sense that it potentially requires less auxiliary memory. In recent times, this model is known as catalytic computation. See for example Koucký's expository article, which provides further motivations for this model.


Does this constitute as an LL grammar? For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar

\begin{align*}S&\to aAba \mid abbB\\
A &\to Aa \mid \lambda\\
B &\to Bb \mid \lambda
\end{align*}

Would the grammar above constitute as LL? I'm having trouble recognizing what exactly constitutes an LL grammar.

An LL grammar is a grammar that can be parsed by an LL parser. An LL parser is a parser which parses input from Left-to-right and constructs a Leftmost derivation of the sentence. (https://en.wikipedia.org/wiki/LL_grammar).

The explanation is still a bit confusing, so it's easier to think of it that by looking at only a portion of the input string, we can predict exactly which production rule to apply.

In the grammar you've given: $L(aa^*ba) \cup L(abbb^*)$

which has the production rules:

$$S \rightarrow aAba | abbB$$
$$A \rightarrow aA | \lambda$$
$$B \rightarrow Bb | \lambda$$

this grammar is the union of all strings which start with either an arbitrary amount of $a$'s or an $ab$.

Remember what I mentioned earlier about LL grammars parsing strings from left to right, and that we'd be able to predict which production rule to use by looking at a portion of the input string? This specific grammar satisfies these properties, and is therefore LL.

Let's look at an example:

Say we're given the strings $aaaaaba$ and $abbbbb$. Starting from the left, how many input characters must we read to see which production rule to use?

The answer is two.

All strings in the grammar $L(aa^*ba) \cup L(abbb^*)$ start with an $a$, and if the second character of the input string is also an $a$, then we must use the production

$$S \rightarrow aAba$$

and if the second character is a $b$ then we must use the production

$$S \rightarrow abbB$$

The only basic concept to keep in mind when dealing with LL grammars is whether or not you can accurately predict which production rule to use when only looking at a portion of the string.

I hope this helped, and if I either missed something or didn't explain sufficiently please feel free to correct me.


Expected behavior of the maximum ranking generated in optimal assignment Suppose n students have preferences over n different notebooks. Their preferences can be represented with a square matrix of size n where each column is a different permutation of the vector [1:n], where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.
For example, such allocation in the problem below
1    2    2
2    1    3
3    3    1
would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.
My question is the following. If the matrix with preferences is chosen uniformly at random, what is the expected maximum ranking in the assignment that minimizes the sum of rankings? In the example above, this is 2. I am interested in the maximum value that occurs in expectation if one of the possible matrices is chosen uniformly at random.
Simulations show that for n=100, this is 6.44 and for n=200 this is 7.04.
See Expected behavior of an algorithm to minimize rankings for further details.

Frieze and Sorkin showed that in the optimal solution of the assignment problem with weights chosen uniformly in $[0,1]$, the maximal value is $\Theta\bigl(\frac{\log n}{n}\bigr)$.
This suggests that the answer in your case is $\Theta(\log n)$.
I found this reference in the survey of Krokhmal and Pardalos mentioned in my answer to your original question. I suggest consulting the survey on your own for any further questions.


Why call it 'Time Complexity'? P.S. I have added the tag 'history', if there is any historical connotation.

Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.

Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows:

  The computational complexity of a sequence is to be measured by how fast
  a multitape Turing machine can print out the terms of the sequence.

Their first section, in which they prove (among else) a time-hierarchy theorem, is about "time-limited computations". They explicitly mention their concept of time:

  The machine operation is our basic unit of time.

The reference is to a multitape Turing machine, which they diligently define.

The intention here is to model the running time of algorithms using abstract machines, using number of steps as a proxy for time. Anticipating your criticism, they mention:

  Furthermore,
  the [complexity] classes are independent of time scale or of the speed of the components from
  which the machines could be built, as there is a "speed-up" theorem which
  states that $S_T = S_{kT}$ [i.e., $\mathsf{TIME}(T(n))$ = $\mathsf{TIME}(kT(n))$] for positive numbers $k$.

That is, multitape Turing machines can always be sped up by an arbitrary constant, and so there is no harm in associating number of steps with running time, since time complexity classes are "scale free".


Validity of self refering state with linear temporal logic 'X' connective Lets say we have model like the one above or a similar one where a node refers back to itself.

Now let's say if I want to know the validity of the formula:

$M, s_2 \models Xr$

Will this be valid or not. In my textbook it says :

$\pi \models X\phi$  iff $\pi^2 \models \phi$

If we are starting at state 2 then our path would be $S_2 -> S_2 ->  ...$

So, I'm not sure since state 2 is not actually transitioning to another states like State 0 or 1. Otherwise would transitioning to the same state in a path $\pi$ be enough to satisfy the "X" connective.

Your textbook correctly states that

$\pi \models X\phi$  iff $\pi^2 \models \phi$

under the assumption that $\pi$ is a word/trace of the transition system and the characters of the word are numbered starting with 1.

So the question that you should ask is how an infinite trace from state $s_2$ would look like and then evaluate the formula on that trace. LTL is only defined on infinite traces, so these are the ones that you should be looking at.

Note that checking if

$M, s_2 \models Xr$

holds does not make sense (in general), as LTL is defined over traces, but from a state in a labeled transition system, there could be multiple traces. So it is not clear what $M, s_2 \models Xr$  should mean - does it mean that it's defined on any trace or every trace? This syntax seems to come from computation tree logic (CTL).


What can give physical access to CPU? If an attacker has an unlimited physical access to CPU, but does not have access to memory, including RAM, can he attack and gain access to the user's data?

I heard the opinion that this is impossible according to the laws of physics, even with an electron microscope. It's true?

If you have unlimited physical access to the CPU, then you can send your own instructions into it, including instructions to read from arbitrary memory addresses. Looking at the voltages on the data bus then shows you exactly what's in that word of memory.

Remember, any data the computer is able to use, has to be accessible by at least one CPU. That's just how it works. So access to the CPU gives you theoretical access to everything else.

(Note: this is an answer to the question in the body, not the question in the title.)


What is a graceful algorithm to generate this number sequence 0                   0
1                   1
1 0                 2
1 0 0               4
1 0  1              5
1 0 0 0             8
1 0 0 1             9
1 0 1 1             11
1 0 0 0 0           16
1 0 0 0 1           17
1 0 0 1 1           19
1 0 1 0 1           21
1 0 1 1 1           23
1 0 0 0 0 0         32
1 0 0 0 0 1         33
1 0 0 0 1 1         35
1 0 0 1 0 1         37
1 0 0 1 1 1         39
1 0 1 0 0 0         40
1 0 1 1 1 0         46

So the idea of this sequence is based on patterns in the binary.
Namely we don't ever repeat patterns. So if you have 1 0, you will never include 1 0 1 0 or 1 0 1 0 1 0
And you also throw out all rotations of a binary sequence within a given digit length. If you have 1 1 0 0 you will never have 1 0 0 1

What is a minimalistic algorithm for generating this sequence and does this sequence have a name?  My interest in this sequence is musical as this is a concise list of rhythms in order of complexity.

I think the below algorithm should be workable. It doubles/triples/quadruples/quintuples/... what we've generated so far to find disallowed sequences. Then it generates all possible sequences by attaching a 0 and a 1 to every sequence found in the previous iteration and removes the disallowed sequences. Then it checks for rotations and removes those too.

First round, generate 1 and 0.

Second round, double these to 11 and 00. These are the strings that are not allowed in this round.

Find possible permutations. (1->{10,11} 0->{00,01}). Remove the disallowed ones we just figured out.

We now have 1, 0, 10, and 01. Find rotations: 10 and 01 are rotations, so remove them but leave one. Which? Let's say 01, as in the example.

Third round, we have 1, 0, 10. We're aiming for a three-digit sequence, and doubling the two-digit sequences would get us a four-digit sequence. Tripling 1 and 0 gets us 111 and 000, which we disallow.

Find possible permutations. (10->{100,101}). Nothing to remove.

We now have 1, 0, 10, 100, 101. Find rotations: no rotations.

Fourth round, we have 1, 0, 10, 100, 101. Aiming for four digits. We do doubling and quadrupling to get the disallowed four-digits sequences: 1111, 0000, 1010.

Find possible permutations. (100->{1000, 1001}, 101->{1010, 1011}). Remove disallowed 1010.

We have 1, 0, 10, 100, 101, 1000, 1001, 1011. Find rotations: no rotations.

One note about when you have to decide which rotations to keep: In the above example we had to decide between "10" and "01". Let's see how these sequences would develop:

10->100, 101

01->010, 011

100->1000, 1001

101->1010, _1011_

011->0110, _0111_

010->0100, 0101

Iterating "rotated sequences" produces rotations of what the other "rotated sequence" would have produced, so I believe it doesn't matter which rotation you keep.

Update: This seems to have something to do with Lyndon words (https://en.wikipedia.org/wiki/Lyndon_word). As I couldn't find a decent list of binary Lyndon words on the internet, I used the Python code I found here: https://gist.github.com/dvberkel/1950267 to generate some more.

I've modified it a bit to make it easier to use (removed one import and changed main function to immediately start generating binary Lyndon words). I've also added a small Perl script to check whether your words are Lyndon words: https://gist.github.com/qiqitori/31175ab58d099ac4ff7573f34e7344d5

Call the Python script using e.g. python lyndon_generator.py | head -n 1010

Call the Perl script using e.g. perl lyndon.pl

Here's what the Perl script outputs:

Found rotation 1 of 1 (1) at index 1
Found rotation 01 of 2 (10) at index 2
Found rotation 001 of 4 (100) at index 3
Found rotation 011 of 5 (101) at index 4
Found rotation 0001 of 8 (1000) at index 5
Found rotation 0011 of 9 (1001) at index 6
Found rotation 0111 of 11 (1011) at index 7
Found rotation 00001 of 16 (10000) at index 8
Found rotation 00011 of 17 (10001) at index 9
Found rotation 00111 of 19 (10011) at index 11
Found rotation 01011 of 21 (10101) at index 12
Found rotation 01111 of 23 (10111) at index 13
Found rotation 000001 of 32 (100000) at index 14
Found rotation 000011 of 33 (100001) at index 15
Found rotation 000111 of 35 (100011) at index 17
Found rotation 001011 of 37 (100101) at index 18
Found rotation 001111 of 39 (100111) at index 20
Found rotation 000101 of 40 (101000) at index 16
Found rotation 010111 of 46 (101110) at index 21

As we can see, index 10 and 19 are missing, but I would bet that the next two numbers in your sequence would be equivalent to index 10 and 19.


Expressing semantics of an array as a function An assignment questions asks the following:

  Consider an array 'var a : array[1..10] of real'.  Express the
  semantics of this array as a function, defining the domain and
  codomain (you might also be able to write the rule).  In this
  programming language, the subrange '1..10' is viewed as a genuine
  type, so we can comfortably say that 'a[13]' is a type error.

I've come up with a semantic that works as a function, that is: f(a[$x$]) -> $y$ where $x$ is a type defined by the numbers $1$ to $10$ and $y$ is the set of all Real numbers. Does this seems correct?

Would there be any difference if I wrote the function in the opposite way, that is: f($y$) -> a[$x$] ?

It makes little sense to think about how we are to encode an array as a function without explaining how we intend to implement the basic array operations. The characteristic property of an array is that we can

access the $i$-th element, and
set the $i$-th element.

In addition, certain equations must be satisfied. For example, if we look up the $i$-th element twice in a row, we will see the same value, etc. (These equations can be looked up in any standard source on the state monad.)

Now, it is quite obvious that an array can be encoded as a function. But we also have to implement get and set. Here is how we might do it in Haskell.

-- An array is represented as a function from integers to floats.
type Array = Int -> Float

-- create a new array all of whose elements are initialized to 0.0
new :: () -> Array
new () = \i -> 0.0

-- get a i returns the i-th element of aray a
get :: Array -> Int -> Float
get a i = a i

-- set a i x returns the array a, but with i-th element set to x
set :: Array -> Int -> Float -> Array
set a i x = \j -> if j == i then x else a j

We are not checking and bounds here, which we should. It may seem a bit unusual that set returns a new array, but there really is no way of modifying an existing one in a purely functional setting. Haskell has the so-called "monadic style" of programming which makes it much easier to work with this sort of encoding (although I wouldn't recommend the encoding for a real appliaction).


reducing subset-sum to partition Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)
Partition: Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

For $B=0$, you can always partition $L'$ into $\{2S-0\}$, $\{S+0\} U L$.
It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.

You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).

You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' > \sum_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.
(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ S' + S-B \}$ and $L\setminus M \cup \{ S'+B \}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.
(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| < S'$, so it is not possible that $\{S'+S-B\} \cup \{ S'+B \} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.


Hash function floating point inputs for genetic algorithm I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range defined for each parameter. My goal is to optimise these parameters to produce the fittest robot.

There are about 25 parameters to optimise over, all of which are >= 0. A generation consists of 32 robots and a typical evolutionary run may have 6000 generations, so that is 192000 robots in total.

One problem I was noticing was that many times, the same robot was being produced by the random mutation function and its fitness was re-evaluated. I want to try and minimise this from happening as the physics simulation engine has a large time expense.

It would be impractical (especially from a memory point of view) to remember all robot parameters that have ever been produced and use a brute force solution.

One solution I thought of was to use a hash function to and a large array of booleans, and everytime a mutation occurs, largeArray[hash(robotParameters)] is checked to see if it is set. If it is, the mutation occurs again to produce a different set of parameters, and if it isn't, largeArray[hash(robotParameters)] is then set.

What is a good hash function implementation that would work for me? Preferably, there would already be an implementation in Python or C++.

Hashing an array of floats

You need some hash function that:

low computational cost
low probability of generating the same hash value for two input vectors = evenly distributed hashes

If you language/library have some function for hashing float array, it should be ok.

For example, this function is what Java would do with an float array (it's not a direct copy of Java library):

int hashFloatArray(float[] arr) {
    //this is done in Arrays.hashCode()
    int h = 1;
    for (int i = 0; i < arr.length; i++){
        int floatAsInt = Float.floatToIntBits(arr[i]);
        //in C: int floatAsInt = *(int*)(&arr[i]);
        h = 31 * h + floatAsInt;
    }
    //this is done in HashMap
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Finding matching hashes

Storing hashes instead of whole float arrays reduces amount of memory needed. Space of hashes is smaller than the space of float arrays, so matching hashes never give 100% certainty that original objects (float arrays) where identical. The longer hashes the smaller is the change of hash collision (situation when two different inputs produce the same hash).

Array indexed with hashes (as OP proposed)

Indexing array with hashes means that the length of the array must be 2^k where k is length of key in bits. For example: Assuming single field of array occupies 1 byte (boolean variable usually occupy 1 byte). Using 30 bit key requires 2^30 * 1 bytes = 1GB of memory (O(2^k) space complexity). As mentioned before:

shorter key = smaller array = higher chance of hash collision
longer key = bigger array = lower chance of hash collision

Hash table (Hash set)

Hash table is a data structure that can be used to implement hash set. Main advantage of hash set is it's O(1) average time complexity combined with O(n) space complexity.

You can use hash set to store and effectively find:

long hashes (64 bit?) of float arrays without wasting memory
float arrays themselves (if you have enough memory)

Hash sets are available in standard libraries of almost all programming languages.

java.util.HashSet in Java
unordered_set in C++11
set in Python

Why comparing and hashing floats is a problem?

Let's take two float numbers: 1.2345678 and 1.2345679
The difference between them is small enough to have no influence on the quality of your Robot, but comparing 1.2345678 and 1.2345679 results in "not equal" and hashing them results in two different hashes. Introducing an "almost equal" term may be a good idea, but that can't be done with hashes.


Smallest non-halting unlambda program Is ```sii``sii the smallest Unlambda program that doesn't halt?

In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (call/cc) and $D$ (delay)? Is it $SII(SII)$?

Intuitively speaking, a non-terminating program needs either:

a combinator such as $Y$ which, when applied, reduces to a larger expression containing itself;
or two combinators such as $S$ which, when applied, replicate at least one of their arguments: one to do the initial replication and one to be replicated.

Unlambda lacks a combinator of the first type, but has two combinators of the second type: $S$ and $C$.

In the SKI-calculus, following the intuition above, a non-terminating term needs to somehow apply $S$ with the first argument being $S$. So it would have to be of the form $Swx(Syz)$, i.e. ```swx``syz in Unlambda). This suggests that $SII(SII)$ is minimal. (Note that I've only given an intuition, I haven't proved it!)

However Unlambda also includes c (call/cc), and this is a very powerful operator in terms of replicating its argument. A term of the form $Cfx$ applies its own continuation $\phi$ to the function $f$; if $f \phi$ itself arranges not to destroy its context, then the term won't terminate. For example, $CI(CI)$ is non-terminating (exercise: work it out). ``ci`ci is known as the Yin-Yang puzzle. To see it in action, make it print a trace of its execution: ``.@`ci`.*`ci.

Because $S$ requires 3 arguments and $C$ requires 2, intuitively, there can't be a non-terminating 3-combinator term, so the 4-combinator term we found above is minimal.

Here's a quick-and-dirty bash script that enumerates all possible Unlambda terms of up to 4 combinators (i.e. 3 application nodes) and prints out the ones that take more than 1 second to terminate. I omitted the I/O primitives which reduce like i, as well as e (exit) which obviously wouldn't help to make a program non-terminating. This is an experimental way to list the non-terminating terms — the terms not printed here are guaranteed to be terminating (assuming a correct implementation), and the terms printed here are likely to be non-terminating.

for a in s k i c d v; do
  for b in s k i c d v; do
    for c in s k i c d v; do
      for d in s k i c d v; do
        for p in @$a$b @@$a$b$c @$a@$b$c @@@$a$b$c$d @@$a@$b$c$d @@$a$b@$c$d @$a@@$b$c$d @$a@$b@$c$d; do
          p=${p//\@/\`}
              timeout 1 unlambda <<<$p || echo $p
        done
      done
    done
  done
done

The result of the experiment is that only the following terms are potentially non-terminating:

```scc?
``c?`c?

where each ? can be independently i, c or d. In other words, the non-terminating combinator terms are $SCCx$ and $Cx(Cy)$ (or so the experiment suggests, but it happens to be correct).

Exercises:

Work out the reductions for these terms and check that they are indeed non-terminating. Do they loop or do they grow forever?
Prove that all smaller terms terminate. (I don't think there's anything more interesting than a long case enumeration.)
How does $SCCI$ relate with my intuition above concerning the minimum content of a non-terminating term — the $S$ replicates only $I$?
Prove or disprove that there is no smaller non-terminating SKI term than $SII(SII)$. Are there others of the same size?


Why is building a heap $\mathcal O(n)$ and not $\theta(n)$? From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my pseudocode? Is there a more optimized way to do heapification?

Heapification(H[1...n])
for i <- floor(n/2) downto 1 do
  k <-i; v <- H[k]
  heap <- False
  while !heap && 2k <= n do
    j <- 2k
    if j <= n
      if H[j] < H[j+1]
        j <- j+1
      if H[j] > v
        H[k] <- H[j]
        k <- j
      else heap <- true
  H[k] <- v

Time complexity of algorithms is usually given as big O. There are many reasons for this, including tradition, but when pertinent reason is that in some cases the time complexity depends on the input. For example, a sorting algorithm might run in $O(n\log n)$ in the worst case, but in $O(n)$ in the best case, and so it is not correct to say that it runs in $\Theta(n\log n)$.

In your particular case, your algorithm runs not only in $O(n)$ but also in $\Theta(n)$. Stating that it runs in $O(n)$ doesn't rule out a matching lower bound — it just doesn't tell the complete story.


An advice to a self-learner of computational complexity I'm a mathematics undergraduate student (going to start my third year very soon). I'm trying to teach myself computational complexity. Sadly, there are no courses provided in my university on the topic and there are no specialists on it (In fact, it seems that my university has no specialists in theoretical CS at all). So, I have no choice to learn the topic except via self-study. I've already gone through the first few chapters of Computational complexity: A modern approach  [ but I did not solve any of the exercises (except two or three in the first chapter exposing what are TM's and Halting problem) ]

I face some problems with the exercises of in the text:

one thing is that I feel that the kind of thinking needed in computational complexity is quite different than that of mathematics that I'm familiar with (There is an emphasize on algorithmic thinking etc and how to reduce problems to other problems and to make a TM simulating another TM etc) which is something I find difficult.

Is there any way do you recommend to help me developing this level of maturity about algorithms, reductions etc?
One reason of difficulty of "1" is that I don't know to what extent should I be rigorous? For example, when I'm doing a reduction or a simulation, it's possible that I can see intuitively that something is clear and can be done but the details would be very very tedious to actually carry out and hence I feel that I don't understand the thing very well. The point is that, I know that there must be a compromise between rigor and intuitive thinking. But since I've no guide nor an instructor, I don't know where this line should be.

when should I carry out all the details if something somehow clear and when should I be satisfied with the intuition? It seems that there are much more details in computational complexity than is usually present in the math I know and hence, where the compromise should be?
I wonder if there exists any source of exercises\problems that are quite easier than those provided in Computational complexity: A modern approach so that I can train myself with the basic notions\constructions etc before tackling more complicated exercises. Also, a source of (quite-detailed) proofs
of the main theorems would be great since many theorems have only a sketch of the proof in the text.

For my background, I've learned basics of programming (I've trained for awhile in python, C and C++) but not much but I'm quite familiar with mathematics specially mathematical logic (up to completeness and Incompleteness theorems), advanced set theory (forcing), Algebra (linear, Abstract, universal algebra and some category theory) and basics of topology and reals analysis. I've taken a course on Discrete mathematics too (combinatorics + graph theory).

I apologise if my question is off-topic but I know no better place to propose those question than here.

My recommendation is to focus on two things: prerequisites, and practice.

Prerequisites: It's going to be harder to learn computational complexity without first having a good understanding of algorithms.  At many schools, a class in algorithms is a prerequisite to the class on computational complexity.  You mention you feel you may lack maturity in algorithms, and in your position, who wouldn't?  It's a non-trivial subject that you haven't studied.  So, my first piece of advice is: before spending too much time on computational complexity, first spend some time studying algorithms.  There are many good algorithms textbooks and online courses (e.g., via Udacity, Coursera, or EdX).  It might be helpful to spend some time learning that material.  You don't need to learn every algorithm in the world, but try to get a feel for some common algorithmic techniques; designing reductions is basically designing an algorithm, so this knowledge will be helpful.  Also, make especially sure you are comfortable with proofs of correctness for algorithms and asymptotic running time analysis.

Next, practice.  No one starts out with a maturity with reductions.  The way to get more comfortable with that is to practice -- do exercises until you either feel comfortable with the material, or the exercises uncover some gap in your understanding (which you can then go back and focus on learning more about).  You probably can't learn the material without this kind of practice.

To help you practice, it may be helpful to look for an online course (a MOOC) on computational complexity.  You can check Udacity, Coursera, or EdX.

How rigorous should you be?  Rigorous enough that you are convinced that you could fill in all the details if you needed to (and that a fellow classmate at a similar level of studies could fill in all the details without thinking hard -- they'd agree filling in the details is tedious but straightforward and obvious).


DFA / NFA Regular Languages Consider the non-deterministic finite automaton A: (in below figure)

1> convert this NFA to DFA

2> Find if there are equivalent states of your DFA

3> Minimize the DFA of <2> if possible

This is what i have got so far

4> further question: Prove that the DFA in <3> recogniese the intended language L.

I got stuck on this question, since the language says that "every occurrence of a is preceded by and followed by an occurrence of b"
this means:

L = {x bab)^n y |  x,y belongs to {b,empty}^n   where n is natural number}

In this case: the language can be:   bbb.....bbbb bab ... bab bbb....bbbb

But for my <3> DFA, the occurrence of a can appear without preceded by an occurrence of b.

I hope if there is anyone can point out my mistake.

many thanks

Here is the transition table for your NFA:

q    s    q'
S0   b    { S1 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }

There are a few problems that prevent this from being a DFA:

Two valid transitions from state $S_1$ on $b$;
No valid transition from $S_0$ on $a$;
No valid transition from $S_2$ on $a$.

Problems (1) and (3) can be solved by introducing a new, "dead", state, $S_3$; the transition table becomes:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

To solve problem (2), we can simply note that the transition $S_1 \rightarrow bS_2$ doesn't buy us anything in terms of strings accepted; the only way to get to an accepting state after doing that is to take the transition $S_2 \rightarrow bS_1$, and we could simply have applied the transition $S_1 \rightarrow bS_1$ twice to do the same thing. We can simply remove this transition and the resulting NFA accepts the same language. Here's the transition table:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

We have no $\lambda$-transitions and each transition maps to a singleton set of states; this defines the following DFA:

q    s    q'
S0   b    S1
S0   a    S3
S1   b    S1
S1   a    S2
S2   b    S1
S2   a    S3
S3   b    S3
S3   a    S3

Now, we may argue using the Myhill-Nerode theorem to see whether we have redundant states. Consider the ways to get to a string in the language from state $S_0$. We can see any string in the language (by definition) and end up in an accepting state. This state constitutes an equivalence class we have not yet observed.

Consider $S_1$. Our first observation is that any string in the language, if encountered starting at this state, will also lead to an accepting state, hence another string in the language. However, we can also see the string $ab$, among others, so this constitutes a new equivalence class, and the state is required.

Consider $S_2$. Any string in the language, except $\lambda$, leads to an accepting state of the DFA. This is a new equivalence class and the state is not redundant.

Consider $S_3$. No strings lead from here to an accepting state, so this is yet another equivalence class under the indistinguishability relation, and the state must be kept.

Therefore, the DFA whose transition table is given above is minimal for the language it accepts. Furthermore, it accepts the language of the NFA originally proposed.

To prove the DFA accepts the target language, there are a variety of approaches. The easiest one is actually by stating three facts about the syntax of your DFA, which prevents the excluded condition from occurring in any accepted strings:

The transition from $S_0$ on $a$ leads to a dead state (no string begins with $a$);
There is no transition to an accepting state on $a$ (no string ends with $a$);
Applying $q \rightarrow aq'$ and $q' \rightarrow aq''$ consecutively always leads to the dead state, where these transitions are any of those in the DFA (no string contains $aa$).

I suppose this is a proof by cases, if knowing what to call the proof is important :D


If P = NP, why does P = NP = NP-Complete? If P = NP, why does P = NP also then equal NP-Complete?

I.e. Why would it then be the case that P = NP = NP-Complete?

Assuming P != NP , there were problems in NP not in NP - Complete. When P = NP, all NP problems are actually now P.

Shouldn't there still be P = NP problems not in NP - Complete?

If $P=NP$ then every non-trivial language $L$ is NP-hard, where non-trivial means that $L$ is neither the empty language nor the language of all words. This follows immediately from the definition of NP-hardness (exercise!). In particular, every non-trivial language in NP is NP-hard, and so NP equals NPC plus the two trivial languages.


Why $\theta/2$ in common qubit representation? If we take angle names as shown on the Bloch sphere below and a typical qubit representation written as $\cos(\theta/2)|0\rangle + \mathrm{e}^{-\mathrm{i}\phi}\sin(\theta/2)|1\rangle$, why do we divide $\theta$ by $2$ in the cosine and sine parameters?

Short diagrammatic answer. Because states which are orthogonal as vectors, are represented as antipodal points on the Bloch sphere — orthogonal states of qubits are as far from each other as possible and represent a sort of 'opposite' of each other, and the Bloch sphere represents this idea.

Longer mathematical answer.
Consider the vector-valued function $\def\ket#1{|#1\rangle}$
$$ \ket{\psi_{\theta,\phi}} = \cos(\theta/2) \ket0 + \mathrm e^{i \phi} \sin(\theta/2) \ket{1}. $$
This function has a period of $4\pi$ in the argument $\theta$, as a result of that division by 2; this might be part of what you are finding strange.
However, when we consider quantum state vectors, we are not actually interested in the vector itself, as we are in the equivalence class of all vectors which are the same up to scalar factors (i.e. global phases).

Because $\ket{\psi_{\theta,\phi}} \ne \mathbf 0$, we always have $\ket{\psi_{\theta,\phi}} \ne \ket{\psi_{\theta+2\pi,\phi}} = -\ket{\psi_{\theta,\phi}}$; but we do have  $\ket{\psi_{\theta,\phi}} \propto \ket{\psi_{\theta+2\pi,\phi}}$ instead. That is, adding $2\pi$ to the angle $\theta$ gives you a vector $\ket{\psi_{\theta+2\pi,\phi}}$ which represents the same state.
Because we only care about the state-vector inasmuch as it represents a state, this vector-valued function with peridod $4\pi$ is used to stand for a state-valued function with period $2\pi$.

This becomes clearer if we use density operators to represent states, because global phases of state vectors do not affect the density operator. Define the operator
$$ \rho_{\theta,\phi} = |\psi_{\theta,\phi}\rangle\!\langle\psi_{\theta,\phi}| = \begin{bmatrix} \cos^2(\theta/2) & \mathrm e^{-i\phi}\!\cos(\theta/2)\sin(\theta/2) \\ \mathrm e^{i\phi} \!\cos(\theta/2)\sin(\theta/2) & \sin^2(\theta/2) \end{bmatrix};$$
using the double-angle formulae
$$ \begin{gather*}
\cos(\theta) = 2\cos(\theta/2)^2 - 1= 1 - 2\sin(\theta/2)^2\\
\sin(\theta) = 2\cos(\theta/2)\sin(\theta/2)
\end{gather*}
$$
we may re-write $\rho_{\theta,\phi}$ as
$$ \rho_{\theta,\phi} = \frac{1}{2}\begin{bmatrix} \cos(\theta) + 1 \;&\; \mathrm e^{-i\phi} \sin(\theta) \\ \mathrm e^{i\phi} \sin(\theta) \;&\; 1 - \cos(\theta) \end{bmatrix} ,$$
which is not the best representation for thinking about qubits, but certainly makes it very clear that the density operator corresponding to $\ket{\psi_{\theta,\phi}}$ is periodic in $\theta$ with period $2\pi$.

As icing on the cake, note that $\rho_{\theta,\phi}$ is Hermitian by construction.
So are the Pauli spin operators $\mathbf 1, X, Y, Z$, and those four are linearly independent.
That means that we can decompose $\rho_{\theta,\phi}$ as a linear combination of those four operators.
We may easily show, from the last expression for $\rho_{\theta,\phi}$, that
$$ \rho_{\theta,\phi} = \tfrac{1}{2}\Bigl(\mathbf 1 + \cos(\phi)\sin(\theta) X + \sin(\theta)\sin(\phi) Y + \cos(\theta) Z \Bigr).$$
If you take the coefficients for $X$, $Y$, and $Z$, and map them to coordinates in $\mathbb R^3$, what you obtain is the Bloch sphere representation: that is, the Bloch sphere not only represents qubit states, but it is specifically representing the decomposition of the density operator into spin matrices.


Lower bounds: Detecting a length 2 path Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.

Suppose the algorithm does less than $\frac{n^2-n}{2}-2(n-1)$ accesses to the matrix, then, there is at least one column (restricted to the upper triangular part of the matrix) such that there are at least two elements the algorithm have never checked.

This can be proved by contradiction, if every column has at most one unchecked element, then the algoritm have done at least $\frac{n^2-n}{2}-(n-1)$, but this contradicts the hypothesis.

Then, supposing every $a_{ij}$ element the algorithm has checked is equal to $0$, whatever the output of the algorithm, it may be wrong. Indeed, if the algorithm sais there are no paths, then, in the "doublely unchecked" column can happen that $a_{ij}=a_{kj}=1$, so there will be a path $i\to j\to k$ whose lenght is two. Otherwise, if the algorithm says there is a path, the matriz could be entirely made of $0$'s.

Note that if the graph is represented with an adjacency list for each vertex the statement does not hold, beacause there is an easy algorithm in $\mathcal{O}(n)$.


Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable? I know $USELESS_{TM}$ is undecidable, but am having trouble showing that it is recursively enumerable. I wanted to reduce $USELESS_{TM}$ to the halting problem, which would show that $USELESS_{TM}$ is recursively enumerable but don't see a way to go about doing this. (I think I would need to check every possible input to see if a state is not entered which I don't know how to simulate using a halting problem subroutine.)

The reason you are struggling to reduce USELESS to the Halting problem might be that it is not recursively enumerable after all. Since you already have a proof of undecidability, it is enough to see that USELESS is co-ce:

Given some TM M, we enumerate all its states as $s_1$ ... $s_n$. We can search through potential inputs $w_0,w_1,\ldots$ and mark each state that one of the computation visits. If we ever mark all states, we halt. This gives a procedure that recognizes exactly the complement of USELESS.


How to prove Landauer's principle I have some questions about energy emitted when one bit of information is processed.

Landauer's principle states the minimum possible amount of energy required to erase one bit of information is k T ln2
Considering this,

How this formula is found? In terms of energy and memory unit, what is the processing cost per bit for normal and reverse operations respectively?

(This is a cross-posted answer from Physics Stack Exchange)

The simple answer would be: consider a physical system that can be in two states. Its thermodynamic entropy is $k_B \log(2)$ due to this. When you erase the bit, then you have a definite microstate and the entropy is zero. Since entropy cannot decrease it has to go somewhere, and this means it needs to be transferred to the environment that has temperature T, giving us a cost $k_B T\log(2)$.

This is the simplified version of a slightly dodgy derivation (note how I facilely equated thermodynamic entropy with information entropy without justification and did not specify how erasure happened or the entropy got moved around). Once can do this more rigorously, like in this paper.

Also, it is worth pointing out it is a misconception that the cost has to be paid in energy. If you have an empty computer memory you can just swap the erased bit for a fresh zero reversibly. But empty computer memory is in a sense a heat reservoir at absolute zero but with very limited capacity (it will eventually run out). It is possible to show that the cost can be paid using other conserved quantities like spin. It is just that in practice we tend to move entropy around by dumping it as waste heat in a cool outside heat bath.

(Landauer's original paper)


Questions on Graph and Hamiltonian From this book and other study in complexity theory, I have seen the following statement:

  The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?

  Determining a that a Graph is not Hamiltonian is an NP-Complete problem.

No, determining whether a graph is not Hamiltonian is coNP-complete, and it is believed not to be NP-complete, indeed not in NP. Determining what a graph is Hamiltonian is NP-complete.


Deciding on decidability of a problem and reducing it to halting problem if not decidable Given are two following languages:

$L_1 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$

$L_2 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$

Are the languages decidable/undecidable/semi-decidable?

The intuition tells me that both languages cannot be decidable, for the simple reason that if any of them ends up in a loop, it can never be decided whether all states were visited. Is my way of thinking correct in both cases?

I would also say that $L_1$ is semi-decidable - in case all states were visited after some finite number of steps, we could decide the language and if not, we still won't be able to say anything about it.

Is it possible to reduce the halting problem to this problem to prove that it's not decidable?

Thank you!

The first language is semidecidable while the second one is not semidecidable.

Claim 1: $L_1 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$ is semidecidable.
Proof: On input $w\#x$ Simply simulate $M_w$ on $x$ and count the number of visited states. If the counter reaches $|Q|$ then ACCEPT. This shows $L_1$ is semidecidable/RE.

Claim 2: $L_2 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$ is not semidecidable.
Proof: Let $L_2$ be semidecidable. Then since $\overline{L}_1 = L_2$, i.e., $L_1$ and $L_2$ are complement of each other, $L_1$ (and so $L_2$) is decidable. In this case we can reduce the Halting problem to $L_1$ as following. Let $M$ be a Turing machine deciding $L_1$. We construct a Turing machine that decides the Halting problem. On input $w\#x$ we modify $M_w$ so that when $M$ halts, it first traverses all other states and then halts. We could do it by changing the ACCEPT state to a normal state, introducing a new ACCEPT state, and adding the following new transitions $$\delta(q_1, a) = q_2, \dots, \delta(q_n, a) = q_{new-accept}$$ where $a$ is a new alphabet symbol and when the modified $M_w$ is at the state $q_{old-accept}$ it first writes $a$ on the tape and enters the state $q_1$ (without moving the head, i.e, the head always reads $a$). Similarly for the the REJECT state. Thus $M_w(x)$ halts if and only if $M_w$ visits all states, which is decidable by $M$.


What is an uninhabited type? https://en.wikipedia.org/wiki/Type_inhabitation
The wiki article above says,

To be sound, such a system must have uninhabited types.

What is the definition an uninhabitated type? Do all programming languages have uninhabited types? What would be an example in Haskell? Or C? Or Java? Or Python?

"Inhabited" is the properly constructive notion of "non-empty". The idea is that to demonstrate that a type is inhabited requires exhibiting a particular construction with that type, while 'non-empty' means merely demonstrating that it is impossible to demonstrate that there are no such constructions.
"Uninhabited" is the negation of this, and so is equivalent to being empty, even constructively.
Haskell does not have an uninhabited type. For instance undefined is a valid term of every type. C, Java and any language with general recursion is not going to qualify either, although C and Java have many other problems even being considered analogues of formal logic. Python doesn't even have types in the type theoretic sense (or it has a single type that classifies everything trivially).
The reason why void does not really qualify is that it is not a 'type with no values', but a type where you disallowed from naming/manipulating values, because those values would be trivial. It is analogous to the unit type, with one featureless value.


Composition of combinators with arities greater than one In combinatory logic, the axiom of composibility asserts that for any two combinators, $A$ and $B$, there exists a combinator $C$ that composes $A$ and $B$.  That is, for all $A,B,x$ there exists a $C$ such that: $CABx = A(Bx)$.

But what if $A$ and $B$ have arities other than 1?  In particular, suppose that $A$'s arity is greater than $B$'s.  Say $A$ has arity 4 and $B$ has arity 2.  Presumably, this would mean that their composition should be $CABvwxyz = A(Bvw)xyz$, so that $A$ would then operate on the four combinators $(Bvw), x, y$ and $z$.  Is this correct?  Surely not $CABvwxyz = A(Bv)wxyz = (A(Bv))wxyz$.

I believe what I am confused about is the use of the 'variable combinator' notation (e.g., $Axy$).  It doesn't seem to me to be syntactically strict.  I believe it is a meta-notation, intended to express the arity of a combinator; which is fine, except that, given the subtleties of reasoning with combinators (at least for my humble comprehension :-) ), I would very much appreciate having an explicit re-write rule to transform one sequence of combinators into another. Is my thinking mis-guided?

One methodical way of accomplishing this is to construct a corresponding lambda term and to then convert it to a CL term using pseudoabstraction.

First some definitions. You want to compose two combinators $A$ and $B$ with arities $p$ and $q$, respectively. Let $C^\lambda_{p,q}$ represent the lambda term accomplishing this.

$C^\lambda_{p,q}$  must first accept $A$, then $B$, then the $q$ arguments $b_1,\ldots,b_q$ of $B$, and then $p-1$ remaining arguments $a_1, \ldots, a_{p-1}$ of $A$ (note: '$p-1$' because the argument $B(b_1\ldots b_q)$ has already been accepted). So $C^\lambda_{p,q}$ must accept $ p + q + 1$ arguments in total, and it must satisfy:

$$C^\lambda_{p,q} A B b_1 \ldots b_qa_1\ldots a_{p-1} \rhd_\beta A(Bb_1\ldots b_q)a_1 \ldots a_{p-1}$$

This easily works for:

$$C^\lambda_{p,q} \equiv \lambda xyb_1 \ldots b_q a_1 \ldots a_{p-1}.x(yb_1 \ldots b_q)a_1 \ldots a_{p-1}$$

So in your example with $p = 4$ and $q = 2$, we get:

$$C^\lambda_{4,2} \equiv \lambda xyb_1b_2 a_1 a_2 a_3.x(yb_1 b_2)a_1 a_2 a_3 $$

Now for the conversion. To this end we introduce the notion of pseudo-abstraction, as defined below by Hindley & Seldin in Lambda-calculus and Combinators:

Definition 1. (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$, thus:

$[x].M \equiv \mathsf{K}M$ $\hspace{29.8mm}$if $x \not\in FV(M)$
$[x].x \equiv \mathsf{I}$
$[x].Ux \equiv U$ $\hspace{33mm}$if $x \not\in FV(U)$
$[x].UV \equiv \mathsf{S}([x].U)([x].V)$ $\hspace{3mm}$if neither (1) nor (3) applies

Here, $\equiv$ denotes syntactical equivalence, and $[x]$ is not really part of the language of combinatory logic itself. Intuitively, a term $[x].M$ is just a name for a valid CL term which we can recover using the above definition. The definition will eliminate all bound variables. For example:

$$[xy].xyx$$
$$[x].([y].(xy)x)$$
$$[x].(\mathsf{S}([y].xy)([y].x))\text{(Def. 1.4)}$$
$$[x].(\mathsf{S}([y].xy)(\mathsf{K}x))\text{(Def. 1.1)}$$
$$[x].(\mathsf{S}(x)(\mathsf{K}x))\text{(Def. 1.3)}$$
$$[x].(\mathsf{S}x)(\mathsf{K}x)$$
$$\mathsf{S}([x].\mathsf{S}x)([x].\mathsf{K}x) \text{(Def. 1.4)}$$
$$\mathsf{S}([x].\mathsf{S}x)(\mathsf{K}) \text{(Def. 1.3)}$$
$$\mathsf{S}(\mathsf{S})(\mathsf{K}) \text{(Def. 1.3)}$$
$$\mathsf{SSK}$$

So $[xy].xyx \equiv \mathsf{SSK}$, i.e. when we write $[xy].xyx$, we really mean $\mathsf{SSK}$. You can verify that $\mathsf{SSK}$ captures the intended functionality:

$$\mathsf{SSK}xy \rhd_{1w} (\mathsf{S}x)(\mathsf{K}x)y \rhd_{1w} xy(\mathsf{K}xy) \rhd_{1w} xyx$$

similarly, the CL term $C^{CL}_{p, q}$ for $C^\lambda_{p, q}$ is simply:

$$[xyb_1 \ldots b_q a_1 \ldots a_{p-1}].x(yb_1 \ldots b_q)a_1 \ldots a_{p-1}$$

Of course, to do the elimination of variables manually even for $C^{CL}_{4,2}$ is tedious, but the point is that the meaning is fixed (and the process of elimination could easily be automated).


Satisfiabililty sufficient condition? The conjecture itself:

k-SAT formula is satisfiable if no pair of unit assignment $l$ and $\overline l$ imply the formula to contain unsatisfiable (k-1)-SAT.

Example (XOR-SAT has no edges and cycles in implication graph, so it's simple example):

$$(\overline x\oplus y\oplus z)\land(x\oplus y\oplus v)\land(x\oplus y\oplus w)\land(x\oplus z\oplus v)\land(x\oplus z\oplus w)\land(x\oplus v\oplus w)$$

If in this formula we'll put $x$, we get $(y\oplus z)\land(y\oplus\overline v)\land(z\oplus\overline v)$ which is unsatisfiable.

So, we only can put $\overline x$: this yields us $(y\oplus v)\land(y\oplus w)\land(v\oplus w)$ which is also unsatisfiable.

Now we conclude that formula is unsatisfiable.

My thoughts on it:

The rule surely works if $k = 2$: 2-SAT is unsatisfiable iff there are two unit assignments $l$ and $\overline l$ that make the formula to contain unsatisfiable 1-SAT (two opposing unit clauses).

In fact algorithm would be:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    if opposing unit clauses found
        assign -x_i
            while unit clauses are presented
                apply unit propagation
            if opposing unit clauses found
                return UNSAT
return SAT

And it does actually the same as implication graph analisys (primitive, though).

But what about $k > 2$?

For $k=3$  we'd need to change algorithm:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i = 1
    assign -x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i += 2
    if b_i == 3
        return UNSAT
    else if b_i == 2
        add clause x_i
    else if b_i == 1
        add clause -x_i
    if b_i > 0
       i = 1
return SAT

Maybe this is not the best implementation, but this is the idea of algorithm. It applies unit assignment and then solves 2SAT for all 2-clauses, in fact it finds all connectivities between opposing literals (finding connectivity between $x$ and $\overline x$ means new unit clause).

taking the contrapositive, another stronger way of stating your question is "a SAT formula f is satisfiable iff either the sub-formulas f1, f2 from the assignment of a variable x or not x are satisfiable". but this is exactly the idea behind the DPLL algorithm (originating as the simpler DP algorithm) provably guaranteed to find a SAT solution. your basic idea also shows the similarity of the method with Gaussian reduction; ie this is not usually remarked but DPLL algorithm appears to be like/ an analog of "boolean Gaussian reduction".


Compressing two integers disregarding order Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to represent.

So, if we're given a set {x,y} where x,y are two different 32-bit integers, can we pack them into 63 bits (rather 64)?  It should be possible to recover the original 32 bit integers from the 63 bit result, but without being able to recover their order.

Yes, one can.  If $x<y$, map the set $\{x,y\}$ to the number

$$f(x,y) = y(y-1)/2 + x.$$

It is easy to show that $f$ is bijective, and so this can be uniquely decoded.   Also, when $0 \le x < y < 2^{32}$, we have $0 \le f(x,y) < 2^{63} - 2^{31}$, so this maps the set $\{x,y\}$ to a 63-bit number $f(x,y)$.  To decode, you can use binary search on $y$, or take a square root: $y$ should be approximately $\lfloor \sqrt{2 f(x,y)} \rfloor$.


Writing the coherence conditions for a monad in a functional laguage i recently asked a related question about the relationship between monads in category theory and Haskell. The answerer showed me the following classes and instances:

class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f m = m >>== (ret . f)
  eta     = ret
  mu m    = m >>== id

instance MyMonad t => KleisliTriple t where
   ret      = eta
   m >>== f = mu (fun f m)

And told me I should show that the rules for each class are equivalent. I've finally gotten around to this exercise but I've already run into some confusion.

I know that the "laws" for a Kleisli Triple are as follows:

return x >>= f  = f x
m >>= return    = m
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

And I know that the coherence conditions for a monad can be written
$$\mu \circ \eta T = \mu \circ T \eta = id_C$$
$$\mu \circ \mu T = \mu \circ T \mu$$
Where $T$ is the endofunctor, fun in the Haskell class.

I know $(\eta T)_x = \eta_{T\, x}$ and $(T\eta)_x=T(\eta_x)$, so I think the rules for MyMonad could be written as follows:

mu . eta . (fun f) = f
mu . (fun eta) = id
mu . mu . (fun id) = mu . (fun mu)

Writing any of these expressions as a function with the desired type signatures loads in GHCI, but I don't think I'm right.

It's mainly associativity that I'm not confident about. Unwrapping associativity for the Kleisli triple yields

mu (fun g (mu (fun f m))) = mu (fun (\x -> mu (fun g (f x))) m)

Which seems  over-complicated, but unlike my attempt to express the category-theoretic constraints, this equation universally quantifies over the functions

f :: a -> m b
g :: b -> m c`

How close am I to coming to the correct conclusion? Hints would be appreciated.

First off, you've confused $\nu$ and $\eta$ in your class. I'm going to go with $\eta$.

The coherency law:

$$\mu \circ T \eta = \mu \circ \eta T = 1_T$$

translates to:

mu . fun eta = mu . eta = id

And the other coherency law:

$$\mu \circ T\mu = \mu \circ \mu T$$

translates to:

mu . fmap mu = mu . mu

Intuitively, the reason why the $T$ "disappears" when translating $\mu T$ to mu is the same reason why it "disappears" when translating $1_T$ into id: in Haskell, types are passed implicitly. If you translate this into System $F_\omega$ (or GHC Core!) the types are passed explicitly and the correspondence is more obvious. I'm going to leave you that one as an exercise.

One more thing. Don't forget the other conditions on mu and eta: they have to be natural transformations! The coherency conditions in category theory are:

$$\forall f : X \rightarrow Y, \eta_Y \circ f = T(f) \circ \eta_X$$
$$\forall f : X \rightarrow Y, \nu_Y \circ T^2(f) = T(f) \circ \nu_X$$

In Haskell:

∀ f, eta . f = fun f . eta
∀ f, nu . fun (fun f) = fun f . nu

In category theory, you might need to prove these, but in Haskell you don't because they are the free theorems for those functions. This is a very nice property of Haskell: Ignoring bottom values and general recursion, any function with the type of a natural transformation must be a natural transformation.

(This is also a good piece of intuition as to what is so "natural" about natural transformations. It means that the "forall" in a polymorphic type is a real "forall"; it's true for any type with no exceptions.)


Use of sorting in counterexamples for equations I came across a question which asked how sorting would help in searching for counterexamples to the conjecture that $$u^6 + v^6 + w^6 + x^6 + y^6 = z^6$$ has no non trivial solutions in integers.

The answer said to make two files containing values of $u^6 + v^6 + w^6 \pmod W$ and $z^6 - y^6 - x^6 \pmod W$. $W$ is the word size of the computer. Sort these, search for duplicates and go for further steps.

Can someone explain what these further steps would be in detail ?

You want to find solutions to $u^6 + v^6 + w^6 = z^6 - x^6 - y^6$. Obviously any solution would also have to be a solution modulo k, for every k. So the idea is to find the set of all possible values of $u^6 + v^6 + w^6$ modulo W, and the set of all possible values of $z^6 - x^6 - y^6$, and you need to find the elements that are common to both sets.

Question: What is the easiest way to check which elements two sets have in common? Answer: Sort the elements, that makes the search very easy.

The further steps: If you are lucky then both sets had few elements in common. So you can deduce values of u, v, w, x, y, z modulo W or modulo some other value. Which means you have reduced the search space. If there was a good amount of reduction, try different values instead of W. And at some point you start with an exhaustive search, but with fewer values needing to be searched.