What purpose do the leaves in a range trees serve? I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:

When you remove the leaves:

It's just a regular BST.
And, every implementation I see of a range tree/range searching, for example, doesn't put the points in the leaves like in the first image.

So, why do depictions of range trees show all the points in the leaves when that would double the amount of space required? Is it just for visualization purposes, or does it represent the output? Is a range tree just a BST with a range query? This may seem nitpicky, but it really confuses me.
Graphic source: graphics.stanford.edu/courses/cs428-03-spring/03Talks/Range.pdf It isn't unique to this specific example. It's seen here: cs.uu.nl/docs/vakken/ga/slides5b.pdf and here:cs.umd.edu/~meesh/cmsc420/ContentBook/FormalNotes/MountNotes/…, even though they seem to just use regular BSTs and don't seem to put the leaves in the nodes

EDIT: It's probably just for  visual purposes: http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf

The Range Tree is made from the input array. The array is sorted and then the tree is built. This means that in the standard construction we have started with the array, this may indicate the leaves. And this BST comes from the sorted array, so there is no point in changing it to e.g. self-balancing trees in the standard case and if there are modifications to the points, the self-balanced trees would perform worse (with very complicated implementation for rotations).

But the Range Tree can be more dimensional, them the leaves represent more dimensions, which leads to several decisions: are these actually pointers or integers (as in example)? Do we want to save memory? Are internal nodes used somewhere else to perform destructive operations?
If the footprint really matters, using integers is a good idea, if there are more dimensions or the integers are cheaper than pointers (to me integers are twice cheaper) this design would be better. So if you add pointers instead of the integers it gets heavier, also the ranges might be smaller, so the savings are bigger.

Also like Raphael pointed it looks like in-order traversal, so it may be right thread in the tree as well.

It may also be for illustratory purposes as you indicated.

Please take a look at the Range trees lecture from Marc ban Kreveld.


Does approximation ratio depend on the input size $n$? I have started study of approximation algorithms and have confusion about the definition of approximation algorithm. I have two textbooks: by Cormen and the second one by Williamson.

Cormen's textbook says

  If an algorithm achieves an approximation ratio of $\rho(n)$, we call it a $\rho(n)$-approximation
  algorithm.

Williamson's say

  An $\alpha$-approximation algorithm for an optimization problem is a polynomial time algorithm that for all instances of the problem produces a solution whose value is within a factor of $\alpha$ of the value of an optimal solution.

So, the first definition defines approximation factor depended on $n$, while the second one does not mention of dependence of $\alpha$ on $n$.

Also I have never seen (yet at least) something like for example $(n/10)$-approximation algorithm, but seen $2$-approximation, or $3/2$-approximation.

My question: could someone clarify the precise definition of the approximation algorithm? (Wikipedia didn't help much). In particular, why do we need the dependence on $n$ if all ratios seem to be constant?

Not all NP-hard problems admit constant factor approximation algorithms (in polynomial-time). One such well-known example is the problem of finding a maximum clique, which cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$ unless P = NP (see Wikipedia, though this is also mentioned in the introduction of Williamson & Shmoys).


is $0^x1^y$ context-free? given that L is regular, does the following make a context-free language?:

i) $\{0^x1^y \mid 0^{x+y} \in L\}$

ii) $\{0^x1^y \mid 0^{x-y} \in L\}$

since L is regular, i presumed that i) can be put into a pushdown automata, but i don't see how to do that for ii). if ii) cannot be put into a pushdown automata, it means it is neither context free nor regular? how can it be shown?

and regarding i) it is a context free, right?

thank you very much for your effort. first post here and i'm glad to join this community

Your first language is actually regular: if $s$ is the substitution mapping $0$ to $\{0,1\}$, then
$$
\{ 0^x 1^y : 0^{x+y} \in L \} = s(L \cap 0^*) \cap 0^*1^*.
$$
Your second language is context-free, since we can write it as $L \cap 0^*$ concatenated with $\{0^y 1^y : y \geq 0\}$. It need not be regular, as the example of $L = \{\epsilon\}$ demonstrates: in this case, your language is just $\{0^y1^y : y \geq 0\}$.


How to find the most unique vectors in a set? A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the set, the number generally equal to the dimension of the vectors. In math terms I believe I want to find a subset of vectors that has the biggest angle from its neighbours in that sub set. Vector length is also a factor, i.e. a unique but nearly zero length vector is less preferred than one less unique in angle but has a finite length.

An example:

1: [1 2 4 1 5]

2: [1 1 2 1 3]

3: [1 2 4 1 4]

...

9999: [2 1 1 2 2]

10000: [4 5 4 2 1]

vectors 1 and 3 are quite similar, 2 less so, 10000 is most different. I think the dot product and higher order 'angle' is the best measure of uniqueness, though there may be better.

Visually, collapsing the dimension down to 2, the vectors below in black represent the full set, the vectors in red are the subset of seven most unique.

Concept update: 03/05/2018

I have recently stumbled upon the concept of the Latin hypercube, and the higher dimensional mathematics behind it that attempt to find an even spread of higher-dimensional vectors. I don't know exactly how this could be applied, but it has been the closest concept so far. Can anyone see how it might be applicable to the problem?

I suspect your problem might be NP-hard (by reduction from Clique), so it might be hard to find an efficient algorithm for it.

One heuristic is to use the farthest-point first method, where at each stage you pick the point whose angle to the others already picked is as large as possible.  In other words, suppose we have already picked a set $S$ of vectors.  Now we find the vector $x$ that maximizes $\min \{\text{angle}(x,s) : s \in S\}$, add it to $S$, and repeat.  This most likely won't give the optimal set of vectors, but it might give something that is somewhat close to optimal.

Another possible approach is to use binary search and some kind of clique-finding algorithm.  Let $t$ be a threshold.  Form an undirected graph $G$ where each vector is a vertex in the graph; and you have an edge $(u,v)$ if the angle between the two vectors $u,v$ is at least $t$.  Then if you can find a clique of size $k$ (where $k$ is the desired size of your subset), then you've found a subset of vectors that are all at angle $\ge t$ from each other.  Now repeat this, using binary search on $t$ to find the largest $t$ for which you can find a $k$-clique.  In this way you might be able to take advantage of methods in the literature for finding $k$-cliques.  (For instance, one simple preprocessing step you can do to reduce the size of the graph is:  delete any vertex whose degree is less than $k$, and repeat until convergence.)


Given a bitstring generate all bitstring with n flipped bits For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and I want to have all bit strings with $2$ bits flipped. That should result in the following bit strings:

1010
1100
1110
0000
0011
0101

So given a bit string of length $n$ and where $k$ bits will be flipped the result will be $\binom{n}{k}$ bit strings. Is there an efficient way to generate all of them? The bit strings I have as input are just unsigned integers so I can use bit twiddling!

Let your initial bit string be x.

For all numbers b with k bits set (i.e. where k bits are 1), output x xor b.

Finding all numbers with k bits set is described elsewhere, for example here


Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete? I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without having explicit constructs for recursion or iteration. Obviously the higher-order functions would be implemented with recursion or iteration, but the requirement is that recursion or iteration could not be directly exposed to the programmer. That is to say, recursion or iteration can be baked in a finite set of pre-defined, built-in higher-order functions, but the language must not have an explicit construct for iteration or recursion. The set of higher-order functions can be arbitrarily large, but must be finite.

Alternatively, if the answer is no, which is the biggest set of problems that could be computed by such a language? Is that set a known set (eg. equivalent to pushdown automaton)?

A functional language such as (a fragment of) Agda has:

inductive types (lists, trees, numbers, etc.)
higher-order functions
structural recursion (a generalization of fold and map)

However, such a language is not Turing complete. If we add the fix-point operator, which is a higher-order function

fix_t : (t -> t) -> t

then we can use that to implement general recursion and we have a Turing-complete language. Conversely, in Turing-complete functional language it is possible to implement fix_t, at least in the case t = nat.

So the obstruction to Turing completeness of functional languages is whether they can implement the fixed-point operator. (Partial combinatory algebras from another answer to this question also have the fixed-point operator.)


Finding the longest repeating subsequence Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ such that $w=w' \cdot w' $. That is, $w$ is a string whose halves appear twice in a row. Note that $w$ is a subsequence of $s$, but not necessarily a substring.

Examples:

For 'ababccabdc' it will be 'abcabc', because 'abc'='abc' and 'abc' appears (at least) twice in 'ababccabdc'.

For 'addbacddabcd' one option is 'dddd' because 'dd' appears twice (I cannot use the same letter several times, but here i have 4 'd's so its ok), but its of lebngth 4. I can find a better one of length 8: 'abcdabcd', because 'abcd' is a substring of 'addbacddabcd' that appears twice.

I'm interested in finding the longest repeating subsequence. This is also called "finding the longest/largest square", but I've read many articles in which a square is defined for a substring and not for a subsequence.

I can easily use a brute force algorithm that will take $O(n^3)$ by iterating on all options for a breakpoint in the string, and then I will have two strings in which I'll be looking for largest/longest common subsequence, but each check will take $O(n^2)$ using a dynamic programming technique, so the entire time will be $O(n^3)$. I found a more efficient algorithm for longest common subsequence which takes $O(\frac{n^2}{\log n})$ , so the running time will be $O(\frac{n^3}{\log n})$.

I am looking for a more efficient algorithm for longest repeating subsequence problem. Perhaps my idea of iterating over all breakpoints wastes too much time, and can be reduced to less iterations. Or perhaps an algorithm with a different attitude can solve this problem.

I've searched in many journals and previous questions, and most of the results I found were about a substring and not about a subsequence.

I've also read that this can be done using suffix trees, but this too was relevant to substrings and I am not sure if such an idea can be extended for subsequence.

I'm looking for a solution that runs in time $O(n^2)$. If there exists one in time $O(n \cdot \log n)$ that will be even better (I am not sure if such exists).

Here is a dynamic programming solution.

Suppose that the input string is $x_1\ldots x_n$. Create a table $T$ whose rows and columns are indexed by $0,\ldots,n$ (where $n$ is the length of the string), populated by the rule
$$
 T[i,j] =
\begin{cases}
0 & \text{if $i = 0$ or $j = 0$}, \\
T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\
\max(T[i-1,j],T[i,j-1]) & \text{otherwise}.
\end{cases}
$$
The answer is $T[n,n]$.


Building a verifier for sentences involving addition over the natural numbers Consider the model $(\mathbb{N},+)$; that is, the natural numbers equipped with the addition relation, PLUS($x$,$y$,$z$), where PLUS($x$,$y$,$z$) is true iff $x + y = z$. Let Th$(\mathbb{N},+)$ be the theory of this model; that is, the set of true sentences in the language of the model. For example, the sentence $\forall x \exists y [x + x = y]$ is a true sentence in this model. Let's assume for simplicity that all of these sentences are in prenex normal form.

I'm interested in coming up with either an (efficient) verifier for Th$(\mathbb{N},+)$ or a nondeterminstic algorithm that decides Th$(\mathbb{N},+)$. In the former case, I'm wondering what a certificate could be. If all of the quantifiers in the input statement are existential, this isn't a problem: a certificate would just be an assignment of all the variables. However, things are made difficult when the input has a universal quantifier, since it isn't obvious how we can check that something holds for all members of an infinite set.

$\left(\mathbb{N},+\right)$ is a model of Presburger arithmetic. Persburger arithmetic is a complete theory (see the answer here), so for any model $\mathcal M$ for Presburger arithmetic (lets denote this theory by $T$) and every first order formula $\varphi$ in the language of $T$ it holds that:

$\mathcal{M}\vDash \varphi \iff T \vdash \varphi$

To see why this follows for completeness, assume $M\vDash \varphi$, then obviously $T\not\vdash \neg\varphi$, thus by completeness $T\vdash\varphi$ (the $\Leftarrow$ implication is trivial).

This shows you why your question reduces to finding a decision procedure for Presburger arithmetic. This has a known double-exponential lower bound, you can find a proof in Rabin and Fischer's paper "Super-Exponential Complexity of Presburger Arithmetic". This bound also holds for nondeterminstic algorithms.


Maximum Chromatic number of Cayley Graphs with large degree It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}$ and not complete. I think the maximum chromatic number is $\lceil\frac{3n}{5}\rceil$. As an example of a graph attaining the attaining the upper bound, we consider the complete graph with order divisible by $5$ and remove a $2$- factor. The two factor we remove is the disjoint union of $\frac{n}{5}$ $5$-cycles. Then, the chromatic number is $\frac{3n}{5}$.
Are there any Cayley graphs with degree $\ge\frac{n}{2}$, and not complete, such that their chromatic number exceeds $\lceil\frac{3n}{5}\rceil$. And, also, are there other Cayley graphs with chromatic numbers between $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{3n}{5}\rceil$

Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most $\frac{3}{5}n$.
Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected $k$-chromatic regular graphs on $n$ vertices for all $k > 1$ and $n \geq \frac{5}{3}k$. You can check their construction to see whether it can be adapted to give Cayley graphs.


Why some rules in Elementary Cellular Automata halt and others don't? I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps and 100 steps are the same, like Here}.

Unlike rule 110 which shows different behavior when N = 20, 100 or 200, i know that it is universal but does that mean if a cellular automaton structure does not halt {continue to show different pattern when changing N steps} does that means it is always universal ?

Your problem is formalized in research as follows: given a CA, is it "Turing complete"? This has been proved for a limited set of CAs including rule 110 in the early 2000s by Cook in a notable proof. it was probably first proved for a CA for the game of life by Conway in the 1970s. There are empirical ways of analyzing CAs that can rule out Turing completeness, and "signs/ circumstantial evidence" that a CA might be Turing complete, but no CA can be proved Turing complete or not from a finite number of example cases.

TMs can execute an arbitrary number of steps and then halt, so that is a characteristic required of the CA simulation. But there is no standard way of defining whether a CA "halts" and thats up to the universality mapping. There is currently no general theory of CA←→TM mappings. There are different mappings in the literature and Cooks mapping is also called "weakly Turing complete" because it requires infinitely recurring patterns specified on the CA input.

There is no general way to find whether particular CAs and rules are universal. This is essentially equivalent to the halting problem in general.

Unfortunately Wikipedia does not highlight Turing completeness in CAs. Here are two useful alternative references.

Universal Cellular Automaton / Wolfram Mathworld by Weisstein
Universality in Elementary Cellular Automata / Cook


What is tail recursion? I know the general concept of recursion.  I came across the concept of tail recursion while studying the quicksort algorithm.  In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm.  It is not clear to me what tail recursion really means.

Can someone explain the concept with a proper example?

Some answers provided by the SO community here.

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.  For example, the function

int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

since it does some computation after the recursive call has returned.

Tail recursion is important because it can be implemented more efficiently than general recursion.  When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function.  This means that we need a call stack whose size is linear in the depth of the recursive calls.  When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller.  That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.


PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1 Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$.
I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if there's a 1 in the $v$ portion?
The question has previously been posted here but I couldn't figure out much from the answers to that.
PDA recognising all strings with a $1$ in the second half

A pushdown automaton accepting this language proceeds as follows:

Push a marker $S$ to the top of the stack.
Push $A$ to the stack for each input symbol read.
At some point, nondeterministically transition to the second phase.
Pop $A$ from the stack for each input symbol read, marking whether you ever read $1$.
Fail if you encounter $S$.
Succeed if you successfully read the entire input, and encountered $1$ during the second phase.

It is also easy to give a context-free grammar for this language, using $\Sigma$ as a shortcut for the alphabet:
\begin{align}
&S \to \Sigma S \mid \Sigma S \Sigma \mid \Sigma T 1 \\
&T \to \Sigma T \Sigma \mid \epsilon
\end{align}


What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable? I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement.  If you can also give some tips on how to implement the algorithm(s) you mention in the answer, that would be great.

Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.


Can a DTM simulate an enumerator E? An enumerator is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Enumerator_(computer_science)

A Deterministic Turing machine is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Turing_machine

How are these definitions different? Can a DTM M simulate an enumerator E, for part of its computation can it call an enumerator E as a subroutine and run it to some point then do something with its output etc?

I assume the answer is yes, you can do things like enum in normal programming with universal language / universal machine. Since DTM is usual definition of universal machine it can perform an enumeration-- just want to be sure, maybe I'm wrong and its a fundamentally different kind of machine?

Yes. A deterministic Turing machine can simulate another deterministic Turing machine (possibly only up to some point), and an Enumerator is a particular kind of deterministic Turing machine.


Proof required for edges in a minimum spanning tree G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

The answer is only statement 2 is correct.

I was able to prove statement 1 is false using contradiction. When we think of a complete graph with 4 vertices and edge weights 1,2,5,6 in non diagonal and diagonal edges 3 and 4. 4,5,6 will create a cycle and we can exclude the lighest edge e (4) from it, in a MST.

But statement 2 cannot be proved using the same. What should be the proof for proving statement 2 is correct?

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? May it be the case that another edge in the cycle can play the 'role' of e in MST?


Prove that not all languages over unary alphabet are regular Let the alphabet be $\{0\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument.
My Ideas:
The set of all languages over $\{0\}$ is uncountable. This can be proved with the diagonalization argument. So to prove the statement, I have to show that set of all regular languages over $\{0\}$ is countable. Not sure how to prove that.

You can show this in many ways. For example, every language can be defined using a regular expression, and the number of regular expressions over a fixed alphabet is countable, since a regular expression is just a word over some alphabet.


Meaning of "positive position" and "negative position" in type theory? What does "in positive position" and "in negative position" mean in the context of type theory?

The only thing I understood from Bob Harper's blog post on the topic is that there is a connection between polarity in this sense in type theory and polarity in logic, but I don't know what that connection is.

Unfortunately "polarity" is a somewhat overloaded concept in type theory. "Positive position" and "negative position" refer to a different notion of polarity than what Bob's talking about with focusing/polarization.

Your Meaning

When you're defining an inductive type you give a series of rules which correspond to operations for the type you're defining. For example you might say a Nat is something with

a value zero : Nat
a function suc : Nat -> Nat

And then expect that Nat contains all the values that can be generated from repeatedly applying suc to other Nats and includes zero. In line with this inductive construction we get an recursion principle across Nats which works based on the fact that any Nat is generated by those constructors.

rec : A -> (A -> A) -> Nat -> A

so that

rec Z S zero = zero
rec Z S (suc n) = S (rec Z S n)

However, there are some restrictions on what we can write as rules. Otherwise, we can write down a series of rules for which the recursion principle cannot be justified. Consider the "inductive type" D with one constructor

d : (D -> D) -> D

Here there isn't a sane recursion principle here. and for good reason! If we had some recursion principle, we could use it to encode a version of self application and with it, nontermination. This means D can't be called "inductive" because inductive types are finite constructions generated from repeatedly applying constructors!

In order to deal with this we restrict how inductive types can be recursive in type theory. Specifically, we stop them from appearing in "negative places". This is that notion of polarity you were talking about. The polarity of a position is determined thusly,

The argument starts in a positive position
Everytime we go to the left an arrow, the polarity flips

So X is positive in the first two and negative in the second two

X
Int -> X
X -> Int
(Unit -> X) -> Int

This idea is justified with a recourse to category theory where an inductive type with whose only recurrences are positive gives rise to a covariant functor. The details of how this works and why its interesting a a bit long.

Bob Harper's Meaning

In his blogpost Harper was talking about a different meaning of polarity. This polarity is reference to how various connectives in logic are given meaning. In particular, we can classify connectives in two ways

Positive connectives can be defined by defining how to introduce them (their introduction rules)
Negative connectives can be defined by defining how to use them (their elimination rules)

In programming language terms, this nicely captures the distinction between lazy and strict types. A strict type is defined by its values. A lazy one is defined by how can pattern match on them. In order to handle this properly, we define a language with 2 main constructs, ways to build up positive types and "spines" to decompose negative types. We can use this to incorporate both strict and lazy computation into one language.

In order to understand this better, I refer you to chapter 38 of Bob Harper's book.


Heuristics & Constrain Satisfaction Problem Differences I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications.

When using Backtracking on a problem, I understand we are calculating the set of all allowable solutions to satisfy some property. This uses the idea of some form of constraint to make sure we can reduce the problem and not have to calculate every possible permutation.

So is the Backtracking algorithm just an application of a CSP?
But when I saw an example of solving a sudoku puzzle with the Backtracking algorithm, it took many more steps than a CSP description of it.

Also, how would the idea of using heuristics to solve a problem relate in with this?

There is a good chance I'm getting confused with some of the terminology so any advice would be greatly appreciated.

CSP is a problem.

Backtracking is an algorithm that searches for a solution, basically, by trying every possibility, and backtracking as soon as it knows it is wrong. Thus it can be applied to many problems, by searching the solution space.

A heuristic algorithm is an algorithm that finds a solution using some trick to speed it up. Some heuristic algorithms might work well for particular types of problems, while remaining slow in the worst-case. Other heuristic algorithms might terminate quicker, but in the worst-case might not find a solution, or it can find an approximate solution.

From wikipedia:

  This is achieved by trading optimality, completeness, accuracy, or precision for speed.


Is computing a square root of a number and having more than 2 roots a reliable way to decide primality? I was reading CLRS and it mentions that if $p$ is a prime of the form $4k+3$ and $a$ is a quadratic residue, then $a^{k+1}$ is a square root of $a$.  One can also easily show that $a^{-k}$ is a square root of $a$ as well.

Can we use this to get a primality test, for numbers $N$ of the form $N=4k+3$?

After reviewing Miller-Rabin (and after asking the related question Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function? ) and thinking about it a little more I thought of an algorithm that seems promising.  The intuition is that if $N=pq$ (or some other composite) there will be more than 2 square roots. Therefore, if we can find more than 2 square roots, we have evidence that $N$ is a composite.  With that idea, here is the algorithm:

PrimalityTest$(N)$: (where $N = 4k + 3$)

Choose $x \in \mathbb{Z}_N$ and compute $a = x^2 \pmod N$.
Compute $y = a^{(N+1)/4} \pmod N$.  (Notice that if $N$ is prime, this is just computing a square root of $a$.)
If $y^2 \equiv a \pmod N$ but $y \not \equiv \pm x \pmod N$ then there are more than 2 distinct square roots of $a$. Therefore, return "composite".
If $y^2 \not \equiv a \pmod N$ then return "composite".  (If $N$ were prime, then step 2 would have computed a valid square root of $a$, so by the contrapositive, if $y$ is not a valid square root, then $N$ is not prime.)
If $y^2 \equiv a \pmod N$ and $y \equiv \pm x \pmod N$ we have no idea what $N$ is. Therefore, go back to step 1 and choose a different $x$.  If this step happens too often, simply return "prime".

I believe this will succeed with probability 1/2, since it has half chance of choosing a "bad" square root that gives us no information. The only step I am not sure how to analyze probabilistically is step 4, but it seems that step 2 might do nonsense when $N$ is composite, it seems the probability that 4 catches is is quite high. I'd guess around $\frac{N-2}{N}$.

There are composite numbers where this primality test fails with probability 1: it always outputs "prime", even though the number is actually composite.  These numbers are basically the Carmichael numbers, with a slight twist.  Therefore, this is unfortunately not a correct primality testing algorithm.

Recall that $N$ is a Carmichael number if $x^{N-1}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}_N^*$.  All Carmichael numbers are odd.  I'll define a super-Carmichael number to be a number $N$ such that $x^{(N-1)/2}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}_N^*$.

Now consider what happens in your algorithm if $N$ is a super-Carmichael number.  We pick $x$ randomly, then compute

$$y=a^{(N+1)/4}=(x^2)^{(N+1)/4}=x^{(N+1)/2} = x^{(N-1)/2} \cdot x = x \pmod N,$$

since $x^{(N-1)/2} = 1 \pmod N$.  It follows that we also have $y^2 = x^2 \pmod N$.  Thus, no matter what value of $x$ you choose, you'll always find that $y^2 \equiv a \pmod N$ is true and that $y \equiv \pm x \pmod N$ (when $N$ is a super-Carmichael number).  So, your algorithm will always give an incorrect answer, when you run it on a super-Carmichael number.

For instance, $1729 = 7 \times 13 \times 19$ is a super-Carmichael number: we have $x^{36} \equiv 1 \pmod{1729}$ for all $x \in \mathbb{Z}_{1729}^*$, and $36$ divides $(1729-1)/2 = 864$.  Therefore, your algorithm gives an incorrect answer on 1729.  I suspect there are infinitely many super-Carmichael numbers.  I also suspect that your algorithm might actually give an incorrect answer on all Carmichael numbers (not just the super-Carmichael ones), but I haven't tried to check the details to see if that's actually true.


Compare two methods of random permutations I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's
call it X. A way of comparison I could think of is the following:

One starts from the standard configuration of n objects [0, 1, 2, ...., n-1] and
apply each method a fairly large number of times successively to permute them
and each time one computes the Hamming distance of the result from the standard
configuaration. One obtains thus the frequency distribution of the Hamming distances
for each method. If these are fairly comparable to each other, then X could be
 practically employed in place of the theoretically perfect one.

Is this line of thought of mine correct? Does anyone have an idea of a better method
of comparison? Thanks in advance.

Your method of comparison is very easy to defeat. I assume that by "Hamming distance from the regular configuration" you mean the number of fixed points. Make a table of the number of permutations in $S_n$ having $k$ fixed points (this can be computed recursively), and fix a single permutation with $k$ fixed points for every $k$. This way you can sample a permutation in a ways that matches this particular statistic of random permutations, but probably performs rather differently compared to a truly random permutation.


Strategies for becoming unstuck in understanding TCS I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of Computation by Michael Sipser) and lectures; however when asked to prove something or come up with a formal description of a specific TM, I just choke.

What can I do in such situations? I guess my issue is with fully comprehending abstract concepts to the point I can actually use them. Is there a structured way to approaching a new, abstract concept and eventually build intuition?

Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly.

In my opinion, understanding concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere.

First of all, you have to grasp the content to some extent. To this end, I have found it useful to ask the following question whenever something is unclear to you:

Why are we doing this?
What are we going to use this for?
What similar things does this relate to?
How do other sources explain it?
What exactly do I not understand?

After you have answered these questions (or discovered follow-up questions and treated them the same way) and still have problems, go to your teachers (or here). By now you should be able to formulate a focused, precisely formulated question; answering such questions is your teachers' job (and StackExchange's philosophy).

Other than that, it is exercise and experience. Try to reproduce proofs after having read them; take care to not learn them by heart but distill the important ideas from them. After some time, you should be able to reproduce all basic proofs by filling in gaps between the major steps. Even later, you will begin to see patterns in statements and proofs. This is how people look at a statement and say "Oh yeah, sure, use method X with theorem Y and then just use Z to get what you want.". It is pattern recognition fueled by years of training. Be patient.

As for basic exercises, go and find text books with some. Off the top of my head I can refer to Concrete Mathematics by Graham, Knuth, and Patashnik. This book is not only a precious toolbox for computer scientists, it also contains loads of exercises with solutions (!). Remember to attempt to solve them before looking up the answers and to reproduce answers you had to look up.

Another useful book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Included is a sizeable chapter on mathematical basics. It also contains many exercises; solutions are available via the linked page (Supplemental Content). There is also a video lecture by one of the authors which may go nicely with the book.

For introductore lectures regarding proofs, have a look at Linear Algebra Proofs on Khan Academy. I have not watched them, but hopefully they are both basic and helpful. There are many more proofs on Khan Academy; I just figure that linear algebra proofs might fit computer science best. Do no hesitate to watch others, too.


Assigning $m$ balls to $n$ buckets - recursive algorithm I came across the following problem and the answer to that problem:

Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, $(1,2,3)$ and $(3,2,1)$ are considered the same.
As an example, if $m = 3$ and $n = 2$, you should return 2, since there are two possibilities: $(1,2)$ and $(3,0)$.

Here is a recurrence which seems to work:
$$
f(m,n) =
\begin{cases}
1 & \text{if } m = 0 \text{ or } n = 1 \\
f(m,m) & \text{if } n > m \\
f(m,n-1) + f(m-n, n) & \text{if } 1 < n \leq m
\end{cases}
$$
This solution seem to work. However I don't understand how $f(m,n-1) + f(m-n,n)$ works. Why is it considering $m-n$ balls into $n$ bins?

An assignment of balls into $n$ bins falls into either one of the following two cases.

Every bin has as last one ball. So let us assign one ball to each bin first. What remains to do is to assign the remaining balls to the bins.
Otherwise. That is, there is at least one bin that has no ball. This case is the same as assigning all balls into $n-1$ bins.

Exercise. Verify that we are counting without duplicates and without missing assignment.


TRNG by hamming distance of processor tics I hardly remember on a lecture, where it was told, that the distance of the practical actual running-speed of a processor to the previous tic is used, to generated a true random entropy for seeding. But I cannot find any source for proving this memory right.

So my question arises: Is this a way to generate a true random seed and spawn so a trng?

You are talking about using the relative jitter of 2 timers to source entropy.

That is indeed an option for entropy generation.

However in terms of cryptographically secure RNGs (the reason you would go to such length to create randomness) this jitter can be influenced by the load on the processor and electrical noise. This provides a side channel to try and influence or predict the entropy used for the generator.


Reduce undecidable language to decidable language? What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable):

If $M$ accepts $w$ then returns an LBA which decides the language {'111'}.

Clearly if $(M,w)$ is in $A_{\mathrm{TM}}$ then $f(M,w)$ is in $A_{\mathrm{LBA}}$ but then $A_{\mathrm{TM}}$ would be decidable!

What am I missing here?

... but then $A_{\mathrm{TM}}$ would be decidable!

No. Because your $f$ is not computable since one cannot compute whether $M$ accepts $w$, as Yuval Filmus said in the comment.


Partially homomorphic encryption (on addition modulo N) not based on prime factorization A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data.

Such a function is homomorphic on addition modulo if the following holds for some cryptographic function $E$:

$
E(x)\cdot E(y) = E(x+y\mod N)
$

and on xor:

$
E(x)\cdot E(y) = E(x \oplus y)
$

This is called a partially homomorphic encryption.

Such schemes are described on the Wikipedia page:

http://en.wikipedia.org/wiki/Homomorphic_encryption

However, all the partially homomorphic schemes on XOR and addition modulo are based on prime factorization.

Are there partially homomorphic encryption methods on XOR or addition modulo that do not are not based on prime factorization (other than the fully homomorphic system proposed by Gentry based on lattice cryptography).

This paper by Mykletun, Girao and Westhoff suggests the El-Gamal method:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=99E3442A4CF314F9AF334969DF9C7974?doi=10.1.1.61.5322&rep=rep1&type=pdf

Typical ElGamal is homomorphic with respect to multiplication. You can get an additively-homomorphic variant by encrypting $g^m$ instead of $m$. When you decrypt, however, you will get back $g^m$, not $m$. Therefore, you have to solve a discrete log to get $m$ back. This is feasible if we place certain restrictions on $m$ (e.g., the space from which $m$ is drawn is small enough to brute-force the discrete log). Security of ElGamal relates to solving discrete logs.

You can get an elliptic curve variant of ElGamal by using an elliptic curve group instead of a multiplicative group of integers modulo some number. This will get you an additively homomorphic cipher without the need to solve discrete logs. Security of this cipher would relate to solving discrete logs in the elliptic curve group.

I am not aware of alternatives for XOR.


Time complexity of algorithms I have some questions that I don't understand about time complexity.

Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case
complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
Given that the best case complexity of the algorithm $A$ is $O(f(n))$ and the worst case
complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
Given that the average case complexity of the algorithm $A$ is $Θ(f(n))$ and the worst
case complexity of A is $O(g(n))$. It follows that $f(n) ∈ O(g(n))$.

I will appreciate if you can help me understand those!
Thanks a lot!

The first and the last statements are correct, while the second one is incorrect.
Statement 1
Denote by $T_{min}$ the actual running time of the algorithm $A$, in the best case, and $T_{max}$ in the worst case. By how we chose $T_{min}$ and $T_{max}$ it follows that $T_{min}\le T_{max}$.
From our assumptions, $T_{min}=\Omega(g(n))\implies T_{min}\ge c_1g(n)$. Also from our assumptions, $T_{max}=O(f(n))\implies T_{max}\le c_2f(n)$.
Combining them together we get:
$c_1f(n)\le T_{min} \le T_{max} \le c_2g(n)$, which means that $f(n)\le \frac{c_2}{c_1}g(n)\implies f(n)=O(g(n))$
Statement 2
Consider the following algorithm:
if lst[0] != 0:
    for x in lst:
        print(x)

And consider the inputs $I_1:=[0,1,2,3,...,n]$ and $I_2:=[1,2,3,...n+1]$.
Clearly, the algorithm takes $O(1)$ time with input $I_1$, but $\Omega(n)$ time with input $I_2$. Obvoiusly, $n\neq O(1)$ and thus the statement is incorrect.
Statement 3
Repeat the proof of statement 1. Note that also $T_{avg}\le T_{max}$ and thus the proof still holds.


The number of different regular languages Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?

As an example, let us consider $n=3$. We then have $2^{18}$ different transition configurations and $2^3$ different start- and end state configurations, so we have an upper bound of $2^{24}$ different languages.
However, many of these will be equivalent and since testing for that is PSPACE-Complete, it is probably unfeasible to test each setting.
Are there other means or combinatorial arguments that bound the number of different languages accepted by a given resource?

This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part.

The paper starts with a quite rigorous asymptotic for the number of distinct languages accepted by a DFA with $n$ states over a unary alphabet. This is done by observing under which conditions a given $n$-state unary DFA is minimal. In such cases the description of the automaton may be mapped (bijectively) to a primitive word, and the enumeration of such words is well-known and done with the help of the Möbius function. Using that result, bounds for non-unary alphabets, both in the DFA and in the NFA case, are proven.

Let's go into more detail. For a $k$-letter alphabet, define
\begin{align*}
 f_k(n) &= \text{the number of pairwise non-isomorphic minimal DFA's with } n \text{ states}\\
 g_k(n) &= \text{the number of distinct languages accepted by DFA's with } n \text{ states}\\
 G_k(n) &= \text{the number of distinct languages accepted by NFA's with } n \text{ states}
\end{align*}
Note that $ g_k(n) = \sum_{i=1}^n f_k(i)$. We start with $f_1(k) $ and $g_1(k)$.

Enumeration of Unary DFA's

A unary DFA $M = (Q, \{a\},\delta, q_0,F) $ with states $q_0,\dots, q_{n-1}$ is minimal iff

It is connected. Thus, after renaming, it the transition diagram consists of a loop and a tail, i.e. $\delta(q_i,a) = q_{i+1}$ and $\delta(q_{n-1},a)=q_j$ for some $j \leq n-1$.
The loop is minimal.
If $j \neq 0$, then either $q_{j-1} \in F $ and $q_{n-1} \notin F$ or $q_{j-1} \notin F $ and $q_{n-1} \in F$.

The loop $q_j,\dots, q_{n-1}$ is minimal iff the word $a_j \cdots a_{n-1}$ defined by
\begin{equation*}
 a_i = \begin{cases}
        1 \quad \text{if } q \in F, \\
        0 \quad \text{if } q \notin F
       \end{cases}
\end{equation*}
is primitive, which means it cannot be written in the form $x^k$
for some word $x$ and some integer $k \ge 2$.
The number $\psi_k(n)$ of primitive words of length $n$ over $k$-letter alphabets is known, see e.g. Lothaire,Combinatorics on Words. We have
\begin{equation*}
 \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d}
\end{equation*}
 where $\mu(n)$ is the Möbius function. With the help of $ \psi_k(n) $ the paper proves exact formulas for $f_1(n)$ and $g_1(n)$ and shows that asymptotically (Theorem 5 and Corollary 6),
\begin{align*}
  g_1(n) &= 2^n \left(n-\alpha+O \left(n 2^{-n/2} \right)\right) \\
  f_1(n) &= 2^{n-1}\left(n+1-\alpha+O \left(n 2^{-n/2} \right)\right).
\end{align*}

Enumeration of DFA's

The next step is a lower bound for $f_k(n)$. Theorem 7 states that
\begin{equation*}
f_k(n) \ge f_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}.
\end{equation*}
For a set $\Delta \subset \Sigma$ of an automaton $M$, define $M_{\Delta}$ as the restriction of $M$ to $\Delta$.
The proof works by considering the set $S_{k,n}$ of DFA's $M$ over the $k$-letter alphabet $\{0,1,\dots,k-1 \}$ defined by

Letting $M_{ \{0 \}}$ be one of the $f_1(n) $ different unary DFA's on $n$ states, and
Choosing any $k-1$ functions $h_i : Q \to Q$ for $1 \le i < k$ and defining $\delta(q,i) = h_i(q)$ for $1 \le i < k$ and $q \in Q$.

The observation is then that $S_{n,k}$ contains $f_1(n) n^{ (k-1)n}$ different and minimal languages.

Enumeration of NFA's

For $G_1(n)$ one has the trivial lower bound $2^n$, since every subset $\epsilon, a,\dots, a^{n-1}$ can be accepted by some NFA with $n$ states. The lower bound is improved slightly, yet the proof is rather lengthy.
The paper Descriptional Complexity in the unary case by Pomerance et al shows that $G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n $.
Proposition 10 shows that, for $k \ge 2$ we have
\begin{equation*}
 n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1.
\end{equation*}
The proof is quite short, hence I include it verbatim (more or less). For the upper bound, note that any NFA can be specified by specifying, for each pair $(q,a)$ of state and symbol, which subset of $Q$ equals $\delta(q,a)$ (hence the factor $ 2^{kn^2}$. We may assign the final states as follows: either the initial state is final or not, and since the names of the states are unimportant, we may assume the remaining final states are $\{1,\dots,k\}$ for $k \in [0..n-1]$. Finally, if we choose no final states, we obtain the empty language.
For the lower bound the authors proceed in a similar way as in the proof for the DFA case: Define an NFA $M=(Q,\Sigma,\delta,q_0, F)$ with $\Sigma = \{ 0,1,\dots,k-1 \}$, $Q=\{ q_0,\dots, q_{n-1} \}$ and $\delta$:
\begin{align*}
 \delta(q_i,0) &=q_{(i+1) \mod n} \quad \text{for } 0 \le i <n \\
 \delta(q_i,j) &=h_j(i) \quad \text{for } 0 \le i <n,\, 1 \le j < k
\end{align*}
where $h_j: \{ 1,\dots,n-1\} \to 2^Q$ is any set-valued function. Finally, let $F=\{q_i\}$ for any $i \in [0..n-1]$. There are $ 2^{(k-1)n^2} $ such functions and $n$ ways to choose the set of final states. One can then show that no two such NFA's accept the same language.


Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7) I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
switching in a particular type of input/output crossbar. Here is the
setup. There are n input wires and n output wires, each directed from
a source to a terminus. Each input wire meets each output wire in
exactly one distinct point, at a special piece of hardware called a
junction box. Points on the wire are naturally ordered in the
direction from source to terminus; for two distinct points x and y on
the same wire, we say that x is upstream from y if x is closer to the
source than y, and otherwise we say x is downstream from y. The order
in which one input wire meets the output wires is not necessarily the
same as the order in which another input wire meets the output wires.
(And similarly for the orders in which output wires meet input wires.)
Figure 1.8 gives an example of such a collection of input and output
wires. Now, here’s the switching component of this situation. Each
input wire is carrying a distinct data stream, and this data stream
must be switched onto one of the output wires. If the stream of Input
i is switched onto Output j, at junction box B, then this stream
passes through all junction boxes upstream from B on Input i, then
through B, then through all junction boxes downstream from B on Output
j. It does not matter which input data stream gets switched onto which
output wire, but each input data stream must be switched onto a
different output wire. Furthermore—and this is the tricky
constraint—no two data streams can pass through the same junction box
following the switching operation. Finally, here’s the problem. Show
that for any specified pattern in which the input wires and output
wires meet each other (each pair meeting exactly once), a valid
switching of the data streams can always be found—one in which each
input data stream is switched onto a different output, and no two of
the resulting streams pass through the same junction box.
Additionally, give an algorithm to find such a valid switching.

This is the algorithm I've came up with so far:

Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
Return the set M of input-to-output wire matchings

I'm having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in  the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven't made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions - then no instability can exist.

Your algorithm is clean and correct.
Here is an easy proof.
Let $\text{junction}(x,y)$ stand for the junction between input $x$ and output wire $y$. Let $\text{stream}(x,y)$ stand for the stream from input wire $x$ to output wire $y$, which must be switched at $\text{junction}(x,y)$.
The book has proved the Gale-Shapley algorithm must produce a stable and perfect matching. As an application, your algorithm must produce a stable and perfect matching between the input wires and output wires.
Suppose, for the sake of contradiction, an execution of your algorithm produces a matching $M$ that includes $\text{stream}(i,o)$ and $\text{stream}(i',o')$ that meet at some junction $J$. Since $\text{stream}(i,o)$ passes $J$, $J$ is either on the same input wire or the same output wire as $\text{stream}(i,o)$. Similarly, $J$ is either on the same input wire or the same output wire as $\text{stream}(i',o')$. Since input wires are disjoint to each other, $J$ cannot be on $i$ and $i'$ both. Similar, $J$ cannot be on $o$ and $o'$ both. So, $J$ must be either $\text{junction}(i,o')$ or $\text{junction}(i',o).$

Suppose $J$ is $\text{junction}(i,o')$.

Since $\text{stream}(i,o)$ passes $J$, $J$ is upstream to $\text{junction}(i,o)$ on input wire $i$, i.e, $i$ prefers $o'$ to $o$.
Since $\text{stream}(i',o')$ passes $J$, $J$ is downstream to $\text{junction}(i',o')$ on output wire $o'$, i.e, $o'$ prefers $i$ to $i'$.

So $(i, o')$ is an instability with respect to $M$.

Otherwise, $J$ must be $\text{junction}(i',o)$. Symmetrically, we will get that $(i', o)$ is an instability with respect to $M$.

However, $M$ is a stable matching. We have arrived at a contradiction. $\quad\checkmark$


Difference between regular language and context free language What is nature of difference of regular language and context free language?

My guess is

RL - CFL = RL
CFL - RL = CFL

Am I correct with this?

No, those are not quite correct.

For any alphabet $\Sigma$, the language $\Sigma^*$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.

However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.


Asymptotic analysis of a real-valued function involving complex numbers I have an algorithm which computes the size of maximum independent set of a graph $G(V, E)$. Let $n=|V|$ be the number vertices, $m=|E|$ be number of edges, and denote the size of maximum independent set of the graph $G$ as $\alpha(G)$ .

Now, I want to estimate the worst-case running time the algorithm needs to compute $\alpha(G)$. I have come up with the following recurrence relation
$$T(n) \leq T(n-1) + T(n-4) + O(n^2)$$
where $T(n)$ denotes the worst case running time. I also assume that the graph has in worst case $n^2$ edges. This algorithm makes two recursive calls and so I have $T(n-1) + T(n-4)$.

My approach is to solve the following inhomogeneous recurrence relation

$$a_n=a_{n-1}+a_{n-4} + n^2, \text{ where } a_0=a_1=a_2=a_3 = 1$$
This relation has two particular solutions
$$a_n^* = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n$$
where $z_1,z_2,z_3,z_4$ are characteristic roots of the characteristic equation $z^4 - z^3 - 1 = 0$
and
$$a_n^+ = B_2n^2 + B_1n + B_0$$
which gives the following general solution
$$ a_n = a_n^* + a_n^+ = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n + B_2n^2 + B_1n + B_0$$

My problem is that two of the roots $z_1,z_2,z_3,z_4$ are complex, one is real positive, and one is real negative, and I do not know how in general we estimate the rate of growth of functions having complex numbers like in this case. I would like to know if there is any general approach widely used in computer science and math to deal with such functions.

Only the root(s) with largest magnitude matters (for generic initial conditions), and the asymptotic rate of growth is exponential in this magnitude (assuming no repeated roots). In your case this root is real, and it's a simple exercise to show that the others don't affect the asymptotic rate of growth.

A more complicated case is recurrences such as $a_n = a_{n-2}$. In this case there are two roots of largest magnitude, both complex. This corresponds to the periodic nature of the recurrence. Nevertheless, for generic initial conditions, the growth rate is $\Theta(1)$, agreeing with the first sentence above.


Mathematical proofs implemented purely by Lambda Calculus I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task.

Is there a simple example, lambda abstraction or application that can be shown to be a valid mathematical proof? For example what does it take to make a Church numeral successor function regarded as a mathematical proof?

So, the trick is that the untyped lambda calculus is not very useful as a mathematical proof, since it has non-halting terms.

Lambda Calculus as a proof system is most useful with types, particularly in terms of the Curry-Howard Isomorphism. Phillip Wadler has a great article outlining this.

The basic idea is that lambda abstraction corresponds to the way that you prove an implication. To write a function of type $A \to B$, you assume you have a value of type $A$, and use it to construct a return value of type $B$.
This is exactly how you prove $A \implies B$: assume that $A$ holds, then use this to prove $B$.

Not every lambda term corresponds to a mathematical proof in the sense we're used to, although each term can be regarded as a proof that its type is inhabited. In particular, to prove anything really useful, you need dependent types, where types are allowed to be indexed by values.

For Church-Numerals, their typed version if $\forall a \ldotp a \to (a \to a) \to a$, which, when interpreted as a proposition, is really boring. It's saying that if something holds, and it implies itself, then that something still holds.

For more information on the various type systems for Lambda Calculi, I'd start with the Lambda Cube.


Proof of correctness of algorithms (induction) I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and proving their formulas I can do it, I have no problem understanding why it is correct. When I get a loop on the other hand, I cannot even get started. I have a hard time combining the Loop invariant (also finding it) and the proof.

For example the following is a complete mystery (i tried reading a few similar questions on SO, but I still don't get it)

function multiply(y, z)
    if z = 0 then return(0) else
    return(multiply(cy, ⌊z/c⌋) + y · (z mod c))

I understand that I am asking a lot, but is it possible for someone to try to explain it step by step ? I am learning the book on my own, this is not a homework and I am not trying to cheat on anything, I just do not understand it.

how do I include the if else statement in the proof?

In this example, the if statement describes the basic case and the else statement describes the inductive step.

Induction on $z$.

Basis: $z = 0$.

$$ \text{multiply}(y,z) = 0 = y \times 0. $$

Induction Hypothesis: Suppose that this algorithm is true when $0 < z < k$. Note that we use strong induction (wiki).

Inductive Step: $z = k$.

\begin{align}
\forall c>0 : \text{multiply}(y,z) &= \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) \\
&= cy\cdot\left\lfloor \frac{z}
{c}\right\rfloor+y\cdot (z \text{ mod } c) \\
&= yz.
\end{align}


Why does counting sort copy the input elements? When I was reading about counting sort in Introduction to Algorithms for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the first thing we do after allocating an auxiliary array.

I was sure the algorithm would look like this:

public static int[] countingSort2(int[] input, int k) {
    // 0 <= input[i] < k
    int[] result = new int[input.length];
    int[] auxiliary = new int[k];

    for (int j = 0; j < input.length; j++) {
        auxiliary[input[j]] = auxiliary[input[j]] + 1;
    }

    int resultIndex = 0;
    for (int i = 0; i < auxiliary.length; i++) {
        if (auxiliary[i] != 0) {
            for (int m = 0; m < auxiliary[i]; m++) {
                result[resultIndex++] = i;
            }
        }
    }
    return result;
}

But of course, the canonical implementation is different:

public static int[] countingSort(int[] a, int k) {
    int c[] = new int[k];
    for (int i = 0; i < a.length; i++)
        c[a[i]]++;

    for (int i = 1; i < k; i++)
        c[i] += c[i - 1];

    int b[] = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--)
        b[--c[a[i]]] = a[i];

    return b;
}

I wonder why they needed to fill the auxiliary array again and then put elements of the input array to the output array.

They do not need to do it this way, but they might have found it more elegant.

Their idea is not:

  Put every element j in 0..k-1 into b exactly c[j] times.

But rather:

  Use the counts to compute the position of every a[i] in b.

That is what the second loop is for: it subsequently computs the offsets for the block of elements i in b.
(The should use j here to avoid confusing, but well.)

As KWillets notes, the latter idea lends itself¹ better to sorting more complex data, say objects, by an integer key; then you would need to copy the references in proper order. Note how it is even stable!

On the other hand, if you do not need resp. make use of this, I expect the first idea to be much more efficient in practice: observe how the second implementation makes non-sequential accesses to arrays b and c which may cause a lot more cache misses than the alternative.

The given implementation can only sort integer arrays, of course.


Does spanning tree make sense for DAG? Why cannot I find any information about spanning tree for DAG ?  I must be wrong somewhere.

Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem. The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.


How do you "time" the measure of binary streams? This is just something I've been wondering just out of curiosity. I apologize if this doesn't fall under the category of this forum, and if so feel free to divert me :)
Whenever a computer does anything, it always handles a sequence of bits. My question is: how does it actually measure what bit goes in what place? I'm curious of the electric current that gets sent into the transistors, and how these are actually placed correctly in the binary stream. I understand the concept of the transistors and how a threshold voltage determines whether or not a bit is 0 or 1, but how are these bits actually placed in sequence?
Say if we have a binary sequence of 00010010001. How does whatever component handling this stream know how "long" it has to wait with no current before it places a 0-bit, and then moves on? According to my understanding, for the first three 0-bits, there will be no current going into the transistors. But does it have to "wait" for a set amount of time before it determines that a single bit is 0? I'm generally just confused as to how a computer knows the difference between a single 0-bit, and (for example) 10 different 0-bits. When does a computer know to set another bit?. Appreciate any feedback! :)

To most components we can attach an internal clock, that is made sure to "tick" at a rate with intervals bigger than the time needed for the current to pass through the circuit. Then, each "tick" the components look at their input and evaluate the output.
This is what defines "when" and "what" a component sees, which (also) allows it to differentiate even between a single 0 and series of 0's.


Finding (and possibly extracting) source code in heterogenous text data set I'm looking for a way to recognize and possibly extract source code from text files that may contain only source code, source code mixed with plain text or just plain text without any source code.

There's different source code contained in the data set, just to name a few examples: Java, C, Python, Bash, PHP, Javascript, ...

An example of a mixed file would look something like this:

Title
=====

Introduction
------------
dolor sit amet, consetetur sadipscing elitr, sed diam
nonumy eirmod tempor invidunt ut...

Description
-----------
Labore et dolore magna aliquyam erat, sed diam voluptua:

    [.c snippet]

At vero eos et accusam et justo duo dolores et ea rebum.

Proof of Concept
----------------
Stet clita kasd gubergren, no sea takimata sanctus est
Lorem ipsum dolor sit amet.

-- sourcefile.c --

[Full .c source file]

The above is only an example and while there might be some files with similar layout, most of them differ quite a bit.

Only looking for one specific language would be preferred, but not required.

My first naive approach when looking for Java source code was to run a simple keyword search using Java keywords, but the results weren't that great. Most java keywords are neither unique to java nor sparingly used in plain text, so what turned up as top results was mostly C files, and of course, this doesn't tackle extraction at all.

I recognize that this is a difficult problem, and I've had no success googling for this topic. The most interesting thing I've found was this paper titled Extracting Code Segments and Their Descriptions from Research Articles, but it's not quite relevant since it's much more focused on the Descriptions part than it is on the Code Segments part.

Is there some kind of algorithm or existing program or library that solves this or a similar problem? Or maybe some kind of neural network flavor?

There are many possible ways you might do this.  I'll suggest one.

I suggest you train a classifier to recognize whether a sequence of characters is code or text.  Here, the goal is to build a boolean classifier that either outputs "text" or "code".  You'll train it only on documents that are entirely text or entirely code (no mixed documents).  Build a classifier that not only outputs a classification, but also a confidence (a likelihood value for the chosen classification).

Now, to apply it to mixed documents, run the classifier on all substrings.  If a substring $S$ is classified as "code" with high confidence (high likelihood), above some threshold, and there's no superstring $S'$ of $S$ (of length not too much longer than $S$'s length) that is also classified as "code", then output $S$ as one of the code elements from the mixed document.  You'll need to select a threshold with a little bit of experimentation.

I suspect this might work nicely.  You'll have to try it to see, though.

So, how do you build such a boolean classifier?  One simple approach would be to use a simple linear classifier (e.g., SVM or naive Bayes) with features based on bag-of-words on lexical tokens.  That alone might suffice (e.g., code tends to have many instances of tokens like "{" and "return", but text doesn't).  You could also try bag-of-words on individual characters.  If you want to build a more sophisticated classifier, you could train a character-level recurrent neural network (e.g., a LSTM or a CNN); this might achieve higher accuracy, given a large enough training set, but probably will also require a bit more technical knowledge.


Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not? Possible Duplicate:
  Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

Is $L=\{ a^nb^m \mid n,m \ge 0, n\ne m\}$ a regular language?

I think it is but can't prove it.

Using Ran G.'s comment which links to a very similar question:

Suppose $L$ is regular. $M=a^*b^*$ is regular, too, so since regularity is closed by set difference, $M\backslash L=\{a^nb^n\}$ would be, too, which is the usual counterexample.


Is the unsolvability of the N-Body Problem equivalent to the Halting Problem There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, there are some special cases of n-body systems for which an analytic function is known.

In much the same way, there is no general algorithm which can predict the result of an arbitrary Turing machine. Although, there are many kinds of Turning machine which can be determined to halt or run forever.

Are these two results equivalent? Does the proof of one of these imply the other? Would a magic machine that is able to solve the halting problem be able to predict the state of an n-body system with exact precision? Or vice versa, would a general analytic solution to the n-body problem allow us to decide the halting problem on an arbitrary Turing machine?

My initial guess on how to approach this would be to show that an n-body system under gravitation is Turing complete. I suspect that it is considering the universe is Turing complete and essentially operates under gravitation (and a few other forces that behave similarly), but I have no idea how to go about proving this.

But I am skeptical that that approach is sufficient considering I find it possible (though I think unlikely) that the lack of an analytic general solution to the n-body problem could be independent of it being Turing complete.

Edit:
After reading some other tangentially related questions, I realized that the number of dimensions in which gravity is operating could be relevant to the question. I'm specifically asking about gravity in 3 spatial dimensions. But, given facts such as you need at least 3 rules to make a universal Turing machine and gravity in 2 dimensions would have just an inverse law $ \propto 1/r $ instead of an inverse square law $ \propto 1/r^2 $ resulting in no closed orbits, I can see it turning out that gravity in three dimensions is Turing Complete, but not in two or one.

There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which asks about calculating future trajectories or orbits of objects all subject to $n^2$ gravitational interactions; it has been studied for centuries including by e.g. Newton and Gauss. It basically reduces to a large array of differential equations and such systems have been proven to contain undecidability scenarios. However, this is a somewhat unusual crosscutting area of physics and mathematics that is not widely cited in either field and there do not seem to be widely cited single references either.

See e.g.

Church’s thesis meets the N-body problem / Smith
On an Undecidable Problem Related
to Difference Equations with Parameters / Abramov
Decidability and Undecidability in Dynamical Systems 2.2.2 n-body problem / Hainry


In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed? I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick.

This is a link to the paper: Sokoban+ is pspace complete

In the paper, they proved that a problem called sokoban+ is pspace complete, they did it by reducing simulation of a turing machine with bounded tape to that problem.

sokoban+ is like sokoban, but the player can pull and push obstacles and all pieces are 2 x 1 rectangles (instead of 1 x 1 like in normal sokoban).

In figure 7, they show a drawing of the cell gadget, this represents a cell of a turing machine.

In the cell, the player enters, chosses a simbol (0 or 1) and if the player chooses correctly, he can go to a simbol gadgdet which will be open only if he has chosen the correct symbol. He goes through the symbol gadget, closing it, and then he goes to a gadget that forces the player to go to the next cell.

My question is, if in this cell and state the symbol of the tape has to change, how does the cell gadget registers that the symbol has changed?

Thanks for your help!

In the paper they created gadget called a gate. This gadget has two entrances, from one entrance the player can open the gate, the other entrance can be traversed only if the gate its on the open state.

In the cell gadget, there are $2k + 2$ gates where $k$ is the number of states the turing machine has and the other two gates correspond to the symbols ($0$ or $1$) that the tape of the turing machine can have.

When the player enters the cell gadget, he accesses a chamber corresponding to the state the turing machine is at that moment. In the chamber, there are two gates that correspond to the two possible symbols that the turing machine can have. There, the player can open one of the gates, the opened door has to coincide with the symbol that the turing machine has in that cell.
He opens the gate by entering through one of the two entrances of the gate, he cannot access the other entrance from here. After opening the gate, he can traverse one of the two symbol gates, closing it.

After traversing the gate, the player reaches a different corridor, from that corridor he can access only the "state gates" that have the same symbol that the symbol gadget has (if they are opened), so he must have chosen to open the correct gate gadget in order to continue. Assuming that the player decided to open the correct state gadget, he can return to the same gate he opened before by entering through the second entrance of the gate (I thought that the player went to a different gate after that, the figure confused me).

After traversing the gate from this second entrance, the player closes the gate. From here he goes to a corridor that allows the player to open one of the symbols gadgets he visited previously (not a different one), and he will only be allowed to open the symbol gadget that the turing machine will write in that state and symbol configuration (if he decides not to open the symbol gate, he will be trapped if he decides to return to the gadget).


Is #HORNSAT polynomial? A Horn clause is a disjunctive clause of literals containing at most one unnegated literal. Examples are
$$
\neg p \lor \neg r \lor \neg q,\\ \neg s \lor q,\\ \neg s \lor \neg q\lor r,\\ s,\\ \neg r \lor t,\\ \neg q \lor \neg t\lor p.
$$
Determining whether or not a set of Horn clauses is simultaneously satisfiable takes polynomial time: this is the problem known as HORNSAT. The algorithm does the following:

If there is a clause containing only a single positive literal, set the letter of that literal to true; then remove the negation of that literal from all clauses containing it. Repeat until no such clauses exist.
Then, if there is an empty clause, the set is not satisfiable.
If there is no empty clause, the set is satisfiable, with satisfying assignment given by setting all unset letters to false.

Following the algorithm, you can quickly see that the above set of clauses is not simultaneously satisfiable, since the last five clauses force all used letters to be true, while the first clause asks at least one to be false.

Now, the problem #HORNSAT asks the following: given a set of Horn clauses, how many simultaneously satisfying assignments are there? One might expect the problem to be easier than #SAT, since HORNSAT is so much easier than SAT; on the other hand, it "feels" NP-hard.

Even if decision is easy, the counting problem #HORNSAT is #P-complete [1], the counting analog of NP-completeness problem. Thus it is very unlikely it has a polynomial time algorithm (for example, if $P \neq NP$ then #HORNSAT has no ptime algorithm).

See [1] for a dichotomy characterizing the clause restrictions leading to tractable instances of #SAT. More precisely, it is shown that the only restriction of clauses that gives tractable instances for #SAT are the clauses of the form $x_1 \oplus x_2 \oplus ...\oplus x_n = 0$ where $\oplus$ is the sum modulo $2$. The other restrictions (#2-SAT, #HORNSAT, ...) are all #P-complete.

[1] Nadia Creignou, Miki Hermann: Complexity of Generalized Satisfiability Counting Problems. Inf. Comput. 125(1): 1-12 (1996), http://www.sciencedirect.com/science/article/pii/S0890540196900164?via%3Dihub


Fermat's last theorem: How to (partially) solve by programs No three distinct positive integers $a, b, c$ can satisfy the equation
  : $a^n + b^n=c^n$, if $n$ is an integer greater than two.

The above statement, known as the Fermat's last theorem is proven with rigorous mathematics. I happened to stumble on one particular statement:

  Proofs were eventually found for all values of $n$ up to around $4$
  million, first by hand, and later by computer.

What I understand is, somehow a computer program assured the theorem was correct upto some value of $n$.

Let us simplify and only stick to $n=3$ (the smallest possible value of $n$). Now my question is, how do I write a program that can ensure that there is no integer solution for $a,b,c$? A complete program is not required, rather some discussion (preferably in pseudocode format) would be appreciated.

See for example Sophie Germain.
Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem.  She used her theorem to prove that all primes up to 100 would work. Apparently checking her theorem was quite a lot of work because later her theorem was used to check first the primes up to 187 and then up to about 1700. Having a computer and being able to check primes using software would have been very helpful. The "intelligent" work was done by Sophie Germain, a lot more boring work could have very well done by a (then non-existing computer).

Kummer proved an improved theorem, which unfortunately was even harder to verify. There were further improvements made, and this was used to check all primes up to 125,000 and later up to 4,000,000. Checking one prime took about 80 minutes on a 1970's computer - that would have been absolutely impossible to do by hand.

So there is a combination: Mathematicians find a way to decide for certain primes p that $a^p + b^p \neq c^p$ for all $a, b, c \geq 1$. The actual method to decide is too much work for a human to do in any reasonable time, so a computer comes very useful.

Wiles' theorem was completely different, all done by hand. However, if you follow the discussion at Wikipedia, you'll find there was mathematics beyond the reach of most mortals, based on more mathematics beyond the reach of most mortals, etc. quite a few levels deep.


Finding a closed formula for recurrence relation I'm trying to find a closed formula for the below recurrence relation:

For the first one, $n$ is some power of 2

$$T(n) = \begin{cases}
4  & \text{if $n=1$} \\
2T(\frac{n}{2}) +4 & \text{else}
\end{cases}$$

$$T(n) = \begin{cases}
1  & \text{if $n=0$} \\
T(n-1) +3^n & \text{else}
\end{cases}$$

I tried to use the substitution and tree methods but I'm not sure what I'm doing and I think I get the wrong answer.

When you are not sure of whether you get the right answer, you can write a simple program in any of your favorite languages to double check.

For example, for the first function, I became pretty confident that I got the right answer once I had run the following script in Python.

def T(n):
    if n == 1: return 4
    return 2 * T(n // 2) + 4

for i in range(1, 20):
    print(T(2 ** i), 2 ** (i + 3) - 4)

Similarly, I ran the following script for the second function.

def S(n):
    if n == 0: return 1
    return S(n - 1) + 3 ** n

for i in range(20):
    print(S(i), (3 ** (i + 1) - 1) // 2)


Context free grammar where number of a's is larger than number of b's in any prefix of the string The prefixes of the string aabab are a, aa, aab, aaba, aabab.
If the number of a's should be greater or equal to the number of b's, the grammar would be

S -> aS | aSbS | e,

but I need it with strictly more a's than b's in any prefix.
I thought of this grammar, but I'm not sure it is correct.

S -> aS | aSAbA | a
 A -> aA | aAbA | e

In short, take your grammar for  the language having a greater or equal number of $a$'s in every prefix, but rename the startsymbol to $P$, i.e.
$$
 P \to aP \mid aPbP \mid \varepsilon.
$$
Then simply note that your condition requires a word to start with an $a$, hence the following will do the job:
$$
 S \to aP.
$$
For if $S \to w$ then $w = auv$ with $|u|_a \le |u|_b$, where $|u|_a$ denotes the number of $a$'s in $u$ (and analog for $|u|_b$), hence for the prefixes of $w$ the assertion follows. And conversely it works the same.

For your given grammar, this is correct (but I leave my answer as it seems to be simpler). For a proof note that if the produced word contains at least one $b$, then it must have at least two $a$'s before it, and this is what your production $aSAbA$ takes care of, where from $A$ we can just derive words having at most as many $a$'s as $b$'s in every prefix.

Let me give another approach to think about this. Might be a little bit to much theory, but just for education and reasoning. Note that the famous Dyck language is defined as
$$
 D := \{ w \in \{a,b\}^{\ast} :  |u|_a \le |u|_b \mbox{for each prefix $u$ of $w$ and } |w|_a = |w|_b \}.
$$
It is quite simple to give a grammar for this language, for example
$$
 S \to \varepsilon \mid SS \mid aSb.
$$
Now if we denote by $\mbox{pref}(L)$ the set of prefixes of some language $L$ then your initial language of words having at most as many $a$'s as $b$'s in any prefix is $\mbox{pref}(D)$. And it is quite easy to derive a grammar from it, just make sure every production could be finished any time on the right (for a general argument see this post), hence we could give the grammar
$$
 S \to \varepsilon \mid SS \mid aSb \mid aS \mid a
$$
where the production $S \to aS$ could also be leaved out. Now simply note that words fulfilling your restriction have to start with an $a$ and proceed as above.


Differences between the Actor Model and Communicating Sequential Processes (CSP) When we look at the Actor Model and Communicating Sequential Processes we see that they are both trying to do concurrency based on message passing, yet they are distinct.

(We see implementations of the CSP Model in go-lang's goroutines (and Clojure's core.async) and the Actor Model in Scala's Akka toolkit)

I'm trying to get a simple list of the differences between the Actor Model and CSP. So far I have:

actors message passing is asynchronous, CSP message passing is synchronous
actors are composable, CSP is not (necessarily)
actors always have unbounded non-determinism, CSP may have bounded or unbounded non-determinism
actors have variable topology whereas CSP has fixed topology
actors have the principle of locality, CSP does not have locality
actors are designed around their behaviour, CSP doesn't not necessarily have this

Is this correct? Is there anything I'm missing?

Assumptions

When I say 'actor model' - I mean the theoretical basis behind the implementation in Scala's Akka framework

Here is how I think Erlang works. I believe Akka is very similar.

Each process has a single mailbox. Messages are put into the
receiver's mailbox by the sender, and fetched by the receiver using
pattern matching. This matching process can change message ordering in
the sense that the oldest message in a mailbox may not match, but a
younger one does. In this case the younger one is consumed
first. Other than that, message ordering is preserved.

With this in mind, the asynchronous $\pi$-calculus extended with input
pattern matching input from buffer describes Erlang (and hence Akka)
semantics accurately, although one needs to do a bit of work in the
encoding, since the $\pi$-calculus doesn't have the restriction to
single channels per process. However, one usually doesn't want an
encoding, but rather a calculus that models the target system
directly.  Such a calculus exists, and it's called Featherweight
Erlang. It is by Mostrous and Vasconcelos. Their paper focusses on
typing, but you can ignore that and just look at the untyped calculus in Section 3.


Find out whose turn it is to buy the croissants A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The purpose of this question is to determine an algorithm for deciding whose turn it will be to bring croissants tomorrow.

Constraints, assumptions and objectives:

Whose turn it is to bring croissants will be determined the previous afternoon.
On any given day, some people are absent. The algorithm must pick someone who will be present on that day. Assume that all absences are known a day in advance, so the croissant buyer can be determined on the previous afternoon.
Overall, most people are present on most days.
In the interest of fairness, everyone should buy croissants as many times as the others. (Basically, assume that every team member has the same amount of money to spend on croissants.)
It would be nice to have some element of randomness, or at least perceived randomness, in order to alleviate the boredom of a roster. This is not a hard constraint: it is more of an aesthetic judgement. However, the same person should not be picked twice in a row.
The person who brings the croissants should know in advance. So if person P is to bring croissants on day D, then this fact should be determined on some previous day where person P is present. For example, if the croissant bringer is always determined the day before, then it should be one of the persons who are present the day before.
The number of team members is small enough that storage and computing resources are effectively unlimited. For example the algorithm can rely on a complete history of who brought croissants when in the past. Up to a few minutes of computation on a fast PC every day would be ok.

This is a model of a real world problem, so you are free to challenge or refine the assumptions if you think that they model the scenario better.

Origin: Find out who's going to buy the croissants by Florian Margaine. My reformulation here has slightly different requirements.

There are two categories of solutions to this sort of problem that I'm aware of: biased lotteries and filtered/generated random sequences.

First, let's dispense with easy but wrong solutions that keep no state.  Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" criterion.  You can select a random sequence that picks all people equally (just going around the list does that; permutations provide randomness), but once people start going on vacation your sequence now has holes.  Unless you keep track, you will again find yourself with binomial distributions instead of maintenance of equal effort.

Let's also commit to having actual randomness.  You might want this so that, for instance, a person cannot schedule their vacation on the basis of a deterministic algorithm so that they are never present when it is their turn to buy croissants (until they use up all their vacation days, I suppose).

So, on to the two types of solutions.

To construct a biased lottery, first note that we can pick from pretty much any continuous distribution (with finite deviation) to generate numbers for our lottery.  The loser can then be the person with the lowest number.  Then the simplest bias is to keep track of whether each individual has bought more or less than their share.  You can measure the bias in units of croissants.  You can tune the degree of randomness by changing the width and shape of the distribution--this will also determine how far away any individual can get from "the same number of times".  Gaussians are easy; they allow for reasonable surprise without having tails that are too long ("unfair").  So the basic shape of the solution is (in Scala code)

case class Employee(var bias: Double) {
  def eat         { bias -= 1 }
  def buy(n: Int) { bias += n }
  def roll        = bias + stdev * Random.nextGaussian
}

You can keep track of who bought last and give them a hefty bias bonus (e.g. 10*stdev) to keep people from buying twice in a row save in the edge case where vacation structure allowed everyone to have bought "last" time.  (i.e. you buy, then go on vacation.)  Same thing for not being present on the day they're selected.  (If someone is absent every other day they eventually will come up as they burn through their bias bonus; I consider this a feature rather than a bug.)

So, you collect your list of present employees for the day, have them all roll for the lottery, pick the lowest, and update.  You can choose whether to have the buying bonus be equal to the number of employees (good when the cost is negligible but the trip to get croissants is burdensome), the number of employees present (good if the trip is easy but the cost is burdensome), or something in between (to acknowledge both burdens).  It's probably better to only have the "eat" penalty for people who are present, but you can do it either way if you feel that merely being on vacation doesn't give you a right pitch in less.
To construct a filtered random sequence, first you need to generate a random sequence.  Shuffling a list of the employees is as good a way as any to start.  Just go through the list, in order, from day to day.  If someone can't buy because they're absent or can't be told or bought before, skip them.  Now you have a problem: you're accumulating people who have been skipped.  That's okay, though.  When you get to the end of your sequence, append the list of skipped employees to the full list before shuffling.  Now the probability of coming up is proportional to the number of times you've been skipped, which maintains the "same number of times" property.

If you use a standard shuffle, it's also particularly easy to quantify the randomness when there are no vacations.  If you picked people completely at random, the knowledge of who was to bring next would contain $\log_2(N)$ bits of information if there were $N$ employees.  Instead, however, only $N!$ instead of $N^N$ possible sequences are allowed, so the information is reduced by $\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$ bits (for large $N$; for $N=10$ it's $~1.14$).

Personally I favor the biased lottery solution as the control over the randomness is better.  With filtered sequences, you can come up with more complex ways to generate sequences.  For example, rather than taking a random permutation, perform local swaps out to a certain distance, or allow swapping of people out of the pool entirely (but they go onto the skipped-list)—but these things require more algorithmic effort.  With the lottery, you just adjust the standard deviation.


Algorithm for fastest division below threshold Take a number i. You need to split it in two pieces as many times as necessary so that all splits are less than or equal to j. How does one obtain this with the minimum number of splits? Examples:

Splitting it in half is optimal here:

i = 4, j = 2
4 -> 2, 2 // (1 split)

However, splitting in half is not optimal here:

i = 9, j = 3
9 -> 5, 4 // Split nine in half
5 -> 3, 2 // Then you have to split the 5
4 -> 2, 2 // and the 4 (3 splits)

The optimal solution here would be:

i = 9, j = 3
9 -> 6, 3
6 -> 3, 3 // (2 splits)

Is there some straightforward way to obtain the optimal split without brute-force iteration?

The optimal strategy is the greedy one: repeatedly split chunks of size $j$. This strategy results in $\lceil \frac{i}{j} \rceil - 1$ splits. We can prove that this strategy is optimal by induction on $i$. The strategy is clearly optimal for $i \leq j$. Now suppose that we split $i > j$ as $i = i_1 + i_2$. In total, this choice will use up at least this many splits:
$$
1 + \lceil \tfrac{i_1}{j} \rceil - 1 + \lceil \tfrac{i_2}{j} \rceil - 1 = \lceil \tfrac{i_1}{j} \rceil + \lceil \tfrac{i_2}{j} \rceil - 1.
$$
Let $\alpha = i/j$, $\alpha_1 = i_1/j$, $\alpha_2 = i_2/j$, so that $\alpha = \alpha_1 + \alpha_2$. To complete the proof, notice that $\lceil \alpha_1 \rceil + \lceil \alpha_2 \rceil \geq \lceil \alpha \rceil$, and so the quantity above is always at least $\lceil \tfrac{i}{j} \rceil - 1$, as claimed.

I have described one optimal strategy. Using the proof above, we can actually describe all optimal strategies. Splitting $i$ to $i_1+i_2$ is optimal iff $\lceil \frac{i_1}{j} \rceil + \lceil \frac{i_2}{j} \rceil = \lceil \frac{i}{j} \rceil$. When does that happen? Define
$$
i = aj-b, \quad i_1 = a_1j-b_1, \quad i_2 = a_2j-b_2,
$$
where $0 \leq b,b_1,b_2 < j$. A splitting is optimal iff $a_1 + a_2 = a$. Notice that
$$
i_2 + i_2 = (a_1+a_2)j - b_1 - b_2.
$$
This shows that the splitting is optimal iff $b_1 + b_2 = b$ (rather than $b + j$).


The difference between dynamic logic and temporal logic To find the difference, I'd just encountered with assertions below about temporal logic in Wikipedia:

  another variant of modal logic sharing many common features with
  dynamic logic, differs from all of the above-mentioned logics by being
  what Pnueli has characterized as an "endogenous" logic, the others
  being "exogenous" logics. By this Pnueli meant that temporal logic
  assertions are interpreted within a universal behavioral framework in
  which a single global situation changes with the passage of time,
  whereas the assertions of the other logics are made externally to the
  multiple actions about which they speak. The advantage of the
  endogenous approach is that it makes no fundamental assumptions about
  what causes what as the environment changes with time. Instead a
  temporal logic formula can talk about two unrelated parts of a system,
  which because they are unrelated tacitly evolve in parallel. In effect
  ordinary logical conjunction of temporal assertions is the concurrent
  composition operator of temporal logic. The simplicity of this
  approach to concurrency has resulted in temporal logic being the modal
  logic of choice for reasoning about concurrent systems with its
  aspects of synchronization, interference, independence, deadlock,
  livelock, fairness, etc.

I could not realize the difference, considerably. Can't dynamic logic cover every time-driven aspect within arguments, as well as temporal logic?

Or why is dynamic not supposed to handle concurrent systems?

Would you please clear the case?

OK, dynamic logic adds assertions that specify what modal situation should exist following an action, however way this action is specified. In temporal logic the modal aspect is not emphasized. For example, if we consider dynamic alethic logic, the alethic bit would be missing from temporal logic. I hope this helps.


Efficient Algorithm to compute radius of tree Given an acyclic undirected graph alike to this one :

(Here the center is the node '2', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost nothing about this online

Yes, it can be done in $O(n)$ time.

Rooted trees

First let me describe how to do it for a rooted tree.  We'll compute several quantities for each node $v$ in the tree:

Let $p(v)$ denote $v$'s parent.
Let $h(v)$ denote the height of $v$ (i.e., the distance from $v$ to its deepest descendant).  You can compute $h(v)$ for all nodes $v$ in $O(n)$ time via a simple recursive traversal.
Let $f(v)$ denote the length of the longest simple path that starts $v \to p(v) \to w \to \cdots$ such that $w$ is a sibling of $v$, i.e., $p(v)=p(w)$ and $v \ne w$.  In other words, it's the length of the longest path that starts from $v$ by going up once and then immediately going down.  Note that

$$f(v) = \max \{2+h(w) : p(w)=p(v), w \ne v\}.$$

Suppose we've computed $h(v)$ for all nodes $v$.  Also, suppose that for each node we keep track of its two children with the two largest $h(\cdot)$ values.  Then, we can compute $f(v)$ for each node $v$ easily.
Let $g(v)$ denote the length of the longest simple path that starts $v \to p(v) \to \cdots$.  In other words, it's the length of the longest path that starts by going up from $v$ (possibly several times).  Note that $g(v) = \max \{ f(p^i(v))+i : i \ge 0\}$ and moreover

$$g(v) = \max(f(v), g(p(v))+1).$$

Therefore, if you've computed $f(v)$ for all nodes $v$, you can easily compute $g(v)$ for all nodes via a simple recursive traversal.
Let $e(v)$ denote the eccentricity of node $v$, i.e., $e(v) = \max\{d(v,w) : w \in V\}$.  The eccentricity of a node $v$ is given by $e(v) = \max(h(v),g(v))$.

This gives us a way to label all the nodes with their eccentricity, in $O(n)$ time.  Then we simply find the node whose eccentricity is the smallest.  The algorithm runs in $O(n)$ time in all.

Unrooted trees

If we have an unrooted tree (as in the question), we can first turn it into a rooted tree (do a DFS; then the DFS tree will be a rooted version of the tree), then apply the previous algorithm.