Prove that a and b commute if and only if they are powers of the same word Two words $a$ and $b$ commute if $ab=ba$.

How to demonstrate that $a$ and $b$ commute if and only if they are powers of
the same word ?

$ab=ba \Leftrightarrow \exists \space  \tau  \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'}$

The demonstration in this direction is trivial:

$\space \exists \space  \tau  \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'} \Rightarrow ab=ba$

But I don't manage to find an elegant solution for the other direction.

If $ab=ba$ then the word $w = ab$ satisfies $R^{|a|}(w) = w$, where $R$ is the right-rotation operator, and $R^{|a|}$ just applies this operator $a$ times. Since $R^{|w|}(w) = w$, Bezout's identity implies that $R^{(|a|,|w|)}(w) = w$, where $g = (|a|,|w|)$ is the greatest common divisor of $|a|$ and $|w|$. Since $g \mid |w|$, we see that $w = z^{|w|/g}$ for some word $z$ of length $g$. Since $g \mid |a|$, we see that $a = z^{|a|/g}$ and $b = z^{|b|/g}$.


What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$ Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity class $\mathsf{SPARSE}$?

If by SPARSE you mean the set of languages where the acceptance occurs on a set of zero density, then it is not in EXP or EXPSPACE. It isn't even computable. To see this, pick your favorite computable enumeration of Turing machines T_n, and consider the language L in the alphabet {0,1} where a string S is in L if and only if L is consists just of n 1s, and where T_n halts on the blank tape. Since the problem of whether a given Turing machine halts on the blank tape is undecidable (if one can do it, one can solve the Halting Problem), our language L is undecidable. Using this same trick with a padding argument we can make languages which are as sparse as we want but are not computable.


Halting problem reducing to the blank tape halting problem I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this.

The blank tape problem takes a machine and an empty tape and tells if this machine halts or not
We prove it is unsolvable by proving it reduces to the halting problem

Whenever I read online, I read that we we write the input on the tape and we run this on the halting problem.

How do we construct the reduction?
Why do we write the input on the tape?
Isn't this all about having an empty tape?

update:
I think my misunderstanding is in the definitio of input and tape

Short version first: The typical reduction for this problem assumes that we can decide the blank tape halting problem, but this gives us a way to decide the halting problem (which in this situation we already know is undecidable). It does so by taking the input to the normal halting problem, and making a new TM that always starts with a blank tape, and writes the normal halting problem input to the tape as its first set of steps - so if this modified machine halts when starting with an empty tape, the normal halting problem input halts with whatever its input. Therefore we can't decide the blank tape halting problem.

Now, with some formality.

We have two languages:

$HALT_{TM} = \{\langle M,w\rangle \mid M \text{ is a Turing Machine that halts on input } w\}$
$BLANKHALT_{TM} = \{\langle M\rangle \mid M \text{ is a Turing Machine that halts on input } \varepsilon\}$

  Lemma. $BLANKHALT_{TM}$ is undecidable.

Proof.
We already know that $HALT_{TM}$ is undecidable. We show that $BLANKHALT_{TM}$ is also undecidable by reduction from $HALT_{TM}$ (i.e. we show that if we could decide $BLANKHALT_{TM}$, we could decide $HALT_{TM}$).

Assume (for contradiction) that $BLANKHALT_{TM}$ is decidable, and we therefore have a Turing Machine $T$ that decides it. Using $T$, we can construct a Turing Machine $R$ that decides $HALT_{TM}$ where $R$ is:

On input $\langle M, w\rangle$

Construct a new Turing Machine $M_{w}$ that does the following:

Starts with a blank tape (or rejects otherwise).
Write $w$ to its tape.
Moves its head back to the start, and from here just copies what $M$ does.

Run $T(\langle M_{w}\rangle)$, if $T$ accepts $\langle M_{w}\rangle$, accept, otherwise reject.

But this would decide $HALT_{TM}$, which we know is undecidable, so $T$ can't exist and $BLANKHALT_{TM}$ is also undecidable. $\Box$

Again, note precisely what each machine is doing:

$R$ decides $HALT_{TM}$, with input $\langle M,w\rangle$.
$T$ decides $BLANKHALT_{TM}$ by assumption.
$M_{w}$ is basically a wrapper for the input $M$ given to $R$ that starts with a blank tape, but as its first actions writes the other input $w$ to its tape - so it starts with a blank tape, but it really does what $M$ does on input $w$.

Note that we "run" neither $M$ nor $M_{w}$, we just construct their descriptions, and give those as input strings to $R$ and $T$ respectively.


What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies? F+ and F* is defined as follows:

F+: closure of F

F+ = {fd | F |= fd}
Set of all FDs deduced from inference rule (normally: Armstrong axioms)

F: cover of F

{fd | F |- fd} cover of F
Set of all FDs entailed by F (all FDs that are true)

So my question is: What is the difference between F+ and F*? Can you also give an example to demonstrate the difference.

Closure and cover are two completely different things.

The closure of a set of attributes or a functional dependency $f$ is a set of relation schemes that can be implied by $f$. In order to find the closure, we can expand the FD or the set of attributes based on the given set of FDs by replacing each relation with the ones inferred by it. For example,

$$X = \{ f_1:A \rightarrow BC,~~~ f_2: C \rightarrow D,~~~ f_3: BD \rightarrow E, ~~~~f_4: F \rightarrow G , ~~~~f_5: F \rightarrow H \}$$

then the closure of $f_1: A \rightarrow BC$ or $\{A\}$ is $\{A,B,C,D,E\}$:

$$A \rightarrow_{f_1} ABC \rightarrow_{f_2} ABCD \rightarrow_{f_3} ABCDE$$

while the closure of $F\rightarrow G$ is $\{F, G, H\}$.

The cover of a set of functional dependencies $X$ is a set of functional dependencies $Y$ that is equivalent to $X$ and the left-side of each functional dependency in $Y$ is unique. Though, not every cover is minimal, and we are usually looking for minimal cover. For example a cover of $X$ is,

$$Y=\{f_1:A \rightarrow BC,~~~ f_2: C \rightarrow D,~~~ f_3: BD \rightarrow E, ~~~~f_4: F \rightarrow GH \}$$

Please do some search before posting your questions, there are plenty of resources on the web, including Wikipedia and Wikipedia.


Why in Declarative Programming variables are not reassigned? I've read that a Declarative language is called "stateless". This means that we can imagine that internally every variable is a constant variable, and it never get reassigned ( in contrast with what usually happens in procedural programming).
How can this work?

This isn't as exotic as it sounds, and you can do it in a procedural language fairly easily.  The basic idea is just that instead of changing a value you just have a function return a new value.  For instance, instead of something like

string read()
{
  string s = '';

  while((string c = getchar()) != '\n')
  {
    s += c;
  }

  return s;
}

you could write something like

string read()
{
  string c = getchar();

  if(c == '\n')
  {
    return '';
  }
  else
  {
    return c + read();
  }
}

See how no variable ever gets reassigned here?

There are some subtleties here that I'm not going into, but I just wanted to illustrate that the idea is not that farfetched.


Data structure for a static set of sets I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, \ldots\}$. The number of sets in $U$ is nearly a million. Also a set in $U$ will mostly contains 8-20 elements.

I am looking for a datastructure for storing collection of sets that support following operations:

set matching,            e.g. check if set $\{h,r,l,a\}$ is present in $U$
subset matching          e.g. check if set $\{h,r,l\}$ is subset of any set in $U$
superset matching        e.g. check if set $\{h,r,l,a,s\}$ is superset of any set in $U$
union matching           e.g. check if set $\{h,r,l,a,e,d\}$ is union of sets in $U$
approximate set matching e.g. check if set $\{h,r,l,e\}$ is present in $U$, should return true

In particular, we can assume that once the data structure is built, no modifications are made but only queries of the above type (the structure is static).

I was thinking of trie data structure. But, it demands storing data in some order. So I have to store every set as a bit vector, but then the trie becomes binary decision tree. Am I in the right direction? Any pointers will be appreciated.

Generically, these are sometimes called subset/containment dictionaries. The fact that you had partial matching in your question (but deleted it) is actually not a coincidence, because subset/containment queries and partial matching are equivalent problems for sets.

You probably want to use an UBTree (unlimited branching tree) for this; it's basically a modified trie. See Hoffmann and Koehler (1998) for more details.

You could also have a look at the more recent set-trie data structure proposed by Savnik (2013) for the same purpose. (If you miss the color in the graphs in that preprint paper and don't have access to the official Springer publication [in which the colors aren't missing], there's precursor to that paper which has almost the same graphs/info and no missing colors.)

Both papers (Hoffmann & Koehler, and respectively Savnik) have experimental results, so you can have some idea what they can handle in practice. Both seem to handle data sets with a cardinality of U around 1M.

If you somehow have TCAM hardware (or the money for it), there's a way to leverage that for subset/superset queries. You can actually do both subset/superset queries in parallel assuming you have enough TCAM words (2x |U|).
Since TCAM words can be configured to be 144-bit wide, you and you have only 95 bits/letters to test, you wouldn't even need to bother with Bloom/hashing, you'd have an exact test using TCAM; this is trivial enough I'll even say here how: every {0, 1} bit-vector corresponding to every set in your U is simply turned into a {0, *} vector for subset queries and to a {1, *} vector for superset queries.

A more general problem tackled in ETI (no free copy, sorry) is finding a set with given similarity measure. For example, the similarity measure can be $J(Q,S)=\frac{|Q\cap S|}{{|Q\cup S|}}$ and the query for a given $Q$ can be to find all $S$ (in the database) with $J(Q,S)\geq 0.3$. Both the constant and the similarity measure are user-definable as a predicate in ETI. (The $J$ given as example here is called the Jaccard index.)


Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC Lets consider $$ACYCLIC = \{\langle G \rangle | G \text{ is acyclic}\}$$
We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. However, I wonder if correct answer is following approach:

The idea is to check each existence of each length of cycle. Let $n$ will be number of cycles.

    for l = 1..n
       is_cycle = non-deterministally check if there exists cycle of length l
       if (is_cycle == "yes")
          then return "no"
    return "yes"// graph is acyclic because there is no cycle of length 1..n

Is it correct approach in $NL$?

You cannot implement this part in NL:

nondeterministically check something
if yes, return no

Consider the following analogy: the language $K$ of all Turing machines that halt is recursively enumerable but its negation isn't. That is, $K$ is accepted by some nondeterministic Turing machine, but its negation cannot be accepted by any nondeterministic Turing machine. This means that you provably cannot implement the following using nondeterminism:

nondeterministically check if the given Turing machine halts
if yes, return no

Your idea suffers from the same problem.

Here is a different angle. The following algorithm checks nondeterministically that $s$ and $t$ are connected:

guess a path $w$ from $s$ to $t$
verify that $w$ is a path; if so, output yes, otherwise, output no

The semantics of this algorithm are as follows:

If there is some witness that causes the algorithm to output yes, then the input is a yes input.

If all witnesses cause the algorithm to output no, then the input is a no input.

What you are trying to do is as follows:

guess a path $w$ from $s$ to $t$
verify that $w$ is a path; if so, output no, otherwise, output yes

All inputs are yes instances in this case, since there is always some witness $w$ that isn't a path from $s$ to $t$.
In order to check that there is no path, you would have to do the following:

go over all possible paths $w$ from $s$ to $t$
if none of them works, output yes, otherwise, output no

Unfortunately, this doesn't describe a nondeterministic Turing machine.


Runtime of searching for a number in an array? Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).

But how about in the case where we know the number definately exists in the array? Does the runtime change then?

Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?

Regardless of whether the number is present in the array, all n elements will still be examined in the worse case. For example if searching for the number 5:

array1 = {6, 8, 3, 7, 8, 2}
array2 = {6, 8, 4, 9, 4, 5}

Searching array1 will require looping over all 6 elements (leading to 5 not being found).
Searching array2 will also require examining all 6 elements, with the final element being 5 and the search returning true.

As for the average number of searches, I believe you are referring to the average number of elements examined? This is difficult. If you are wondering what the average case is for arrays of ints with length 6, you would need to generate all possible permutations of arrays  of ints with length 6, then search them all for your desired number (say 5) and calculate the average. This will differ again if you only include permutations that have at least one element which is 5 (average will improve).

For a brute force search algorithm like this, all you can really be certain of is that the average case will be somewhere between the best best case O(1) (5 is first element of the array) and the worst O(n)


How to reduce MaxUNSAT to MaxSAT? Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ?
When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is almost the same. And for a propositional formula f in CNF it holds:
|f| = MaxSAT(f) + MinUNSAT(f)

where |f| is the number of clauses of f.
When considering MaxUNSAT and the corresponding MinSAT problem, the same relationship holds:
|f| = MaxUNSAT(f) + MinSAT(f)

Now, I was wondering if there is also a relationship between those two pairs, e.g. to reduce MaxSAT to MaxUNSAT or MinSAT (or the other way round) ?
Unfortunately, I could not figure out one by myself. And maybe there is none ?
Update 1: Inspired by Yuval Filmus's answer, I will give a reduction for my question.
Reduction from MaxUNSAT to its corresponding decision problem:
Let $\phi = {C_1, ..., C_m}$ a set of clauses over the variables $x_1, ..., x_n$, then it holds:
$$MaxUNSAT(\phi) = BinarySearch(0, |\phi|, MaxUNSAT(\phi, k) )$$
with

BinarySearch(start, end, CompareProcedure( )):
Searches for the element e between start and end so that CompareProcedure(e)=true and CompareProcedures(e+1)=false

and
$$MaxUNSAT(\phi, k) := \exists v\in\{0, 1\}^n:\sum_{i=1}^m 1 - I_v(C_i) \geq k$$
where $I_v$ is the interpretation of a propositional formula under assignment $v$.
Reduction from decision problem $MaxUNSAT(\phi, k)$ to SAT:
One can reduce the devision problem $MaxUNSAT(\phi, k)$ to the SAT problem by adding blocking variables to each clause and adding a cardinality constraint as propositional formula to limit the number of used clauses with help of the blocking variables.
I can describe this in more detail, if needed.
Conculsion:
One can reduce the MaxUNSAT problem to the SAT problem and then solve the SAT problem with the MaxSAT problem. This is a reduction that works in polynomial time.

Both MaxSAT and MaxUNSAT are NP-complete, and so can be reduced to one another. MaxSAT is NP-hard by (trivial) reduction from SAT. To see that MaxUNSAT is NP-hard, we follow Creignou [1] and reduce from MaxCUT. Given an instance $G=(V,E)$ of MaxCUT, consider the instance
$$ \bigwedge_{(x,y) \in E} (x \lor \lnot y) \land (\lnot x \lor y). $$
Each cut corresponds to a $0/1$ assignment to the vertices. If an edge $(x,y)$ is separated by a cut, then one of the two corresponding clauses will be unsatisfied, and otherwise none will be unsatisfied.

[1] Creignou, A dichotomy theorem for maximum generalized satisfiability problems, JCSS 51, 511-522 (1995).


How to approach analysis of randomized algorithm Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any integer between $1$ and $n$ has equal probability. A simple process using this information is to loop for some fixed number of iterations $M$ that, for ease, is a multiple of $n$, and do the following:

Randomly obtain some constant $k \leq n$ number of integers from $U$ and place them into a set $V$
For $i^* = \arg \min V$, do update $C(i^*) \leftarrow C(i^*) + 1$

Ultimately, I want to be able to investigate the quantity $P\left( | C(i) - \frac{1}{n}\sum_{j=1}^n C(j) | \leq \epsilon \right)$ for any $i$. The question I have is if this simple algorithm allows, in probability, for the values of $C(i)$ to remain close to their average values regardless of how many iterations we do. This probability is obviously of a form where one could take advantage of say Hoeffding's inequality but I am not quite sure how to make use of the algorithm structure to get to that point.

I am not very well versed in randomized algorithms and so any insight into how to approach the analysis of such a simple algorithm would be insightful.

Let $P$ be the distribution of $i^*$, which you can calculate explicitly:
$$
\begin{align*}
p_i := \Pr[P=i] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k.
\end{align*}
$$
This is the probability that all samples are at least $i$ minus the probability that they are all at least $i+1$.

The counter $C(i)$ has binomial distribution $\mathrm{Bin}(M,p_i)$, which will be concentrated around $Mp_i$. In contrast, $\frac{1}{n} \sum_{j=1}^n C(j) = \frac{M}{n}$. Therefore you can only expect $C(i)$ to be close to $\frac{1}{n} \sum_{j=1}^n C(j)$ if $p_i \approx \frac{1}{n}$. Even when $p_i \approx \frac{1}{n}$, the concentration of $C(i)$ is not so good – the standard deviation is $\sqrt{Mp_i(1-p_i)} \approx \sqrt{M/n}$, so the probability that $C(i)$ is very close to $M/n$ is probably quite small.


Suffix array and counting distinct substrings of specific length I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.

I started with the algorithm for counting ALL distinct substrings. I solved it after this explanation: https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/  . The problem right now is that I can't figure out how to only count the substrings of my given length, and not all possibilities.

I also computed the array which tells me how many suffixes are lexicographically smaller than suffix_array[i].

Any ideas what I could use to do it?

The geeksforgeeks solution gives an efficient algorithm that accomplishes the following:

Sorts the suffixes of the input string in lexicographic order.
For every two adjacent suffixes in this order, finds the longest common prefix.

If you are after the number of distinct substrings of length $\ell$, you should proceed as follows:

If the first suffix has length at least $\ell$, initialize your counter with 1, otherwise with 0.
Now go over all the suffixes in lexicographic order. If the new suffix has length at least $\ell$ and the lcp with the preceding suffix has length smaller than $\ell$, then increment the counter.

For example, suppose that the string is ababa, and you're after substrings of length $\ell = 3$. The ordered suffixes are a, aba, ababa, ba, baba. The algorithm proceeds as follows:

The first suffix a is shorter than $\ell$, so the counter starts at 0.
The second suffix aba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered aba.)
The third suffix ababa has length at least $\ell$, but the lcp with the preceding suffix also has length at least $\ell$.
The fourth suffix ba has length less than $\ell$.
The fifth suffix baba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered bab.)


Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither? In Python, we have metaclass and abstract class.

In Java and C#, we have interface and abstract class.

The relation between a metaclass and a class is instantiation, so it extends the instantiation relation between a class and an object.

The relation between an abstract class and a class is inheritance, so it extends the inheritance relation between concrete classes.

The relation between an interface and a class is implementation.

Is this implementation relation an instantiation relation, an inheritance relation, or neither?
If neither, can this relation be viewed as some extension of some relation between some classes or objects?
is an interface more like a metaclass or an abstract class?

Thanks.

From notes I have from university, here is an explanation I found useful that may help

  An interface, or protocol as it is sometimes called, is a device that is used to allow unrelated objects to interact with one another, by implementing an agreed upon system of behavior. When a class implements an interface, the class agrees to implement all of the methods defined in the interface. Interfaces are useful since they capture similiarity between unrelated objects without forcing a class relationship.

The important line is the bottom, there is no class relationship between classes that impliment an interface. You cant view it in the same way you would with instances of classes and abstract classes. These give a direct relation in terms of object type and subtype.  It is not a guarantee of relation between objects but instead a guarantee of functionality.

To your bullets I would say; Neither, not really, and it is not really like either metaclass or abstract class at all.


Which element is at its final position after the partitioning step in Quicksort? In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position.

  The entry a[j] is in its final place in the array, for some j.

  No entry in a[lo] through a[j-1] is greater than a[j].

  No entry in a[j+1] through a[hi] is less than a[j].

And this comes from Algorithms, 4th Edition, as well:

  First, we arbitrarily choose a[lo] to be the partitioning item—the one
  that will go into its final position.

Does the pivot go into its final position for all inputs without exception?

The details depend on the partitioning method used, but usually the pivot ends up in its final position.

That follows from the second and third statement, by the way: all elements smaller than the pivot are to the left of it, and the larger to the right. The pivot is in between, and that is clearly its final position in the sorted array.

That the second and third statement hold is the central property of the partitioning method used.


Big-O complexity upon taking exponent If $X \sim \mathcal{O}(\log n)$, then $e^{-X} \sim \mathcal{O} (?)$

Is this a valid question to ask?

The statement $X = O(\log n)$ gives an upper bound on $X$, which implies a lower bound on $e^{-X}$ (which is a monotone decreasing function). You can say
$$
e^{-X} = e^{-O(\log n)} = n^{-O(1)}.
$$
In other words, there exists a constant $C > 0$ such that for large $n$,
$$ e^{-X} \geq \frac{1}{n^C}. $$


Is it necessary for NP problems to be decision problems? Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems are decision problems. So what type of problems are basically in the class NP ? And is it unnecessary to say that solutions to such problems have a polynomial length output(as decision problems necessarily output either 0 or 1) ?

Indeed problems in NP are decision problems which output 0 or 1 for a given input string. Prof Roughgarden is referring to the fact that problems in NP have short polynomially bounded proof (in the input length) of membership that can be verified efficiently (by polynomial time algorithm).


A clarification on $PP$ Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following:

On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is the length of the input.
On a NO instance, output YES with probability $1/2 - 1/2^n$."

Can we replace $2^n$ by something larger like $2^{n^{1+\epsilon}}$ or $2^{2^n}$? It seems that this case should be already known to be distinct from $BPP$.

First, let me change your definition of PP a little bit:

On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$

On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$

Here, I replaced the error term with $\epsilon(n)$ and added $\geq$ and $\leq$. If we don't include $\leq$ and $\geq$, then problems in $BPP$ would not fall under our definition of $PP$.

You can replace the error with any small $\epsilon(n)>0$ you want, but you are not accomplishing anything by going past $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$.

Realistically, we do not need an error term smaller than $\epsilon(n)^{-1} = 2^n$ because you can amplify the error by a polynomial amount to get $2^{poly(n)}$ (since we are a polynomial time machine).

We unfortunately can't amplify beyond this, but that turns out not to matter. There does not exist a probabilistic polynomial time Turing machine that can accept or reject with error probability $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$. A probabilistic polynomial time Turing machine does not have a large enough number of configurations to accept or reject with such a fine grained/detailed error.

To see what I mean, think about how you would design a PPTM that outputs YES with probability just $1/2^{2^n}$. The best you could do is use almost all of your runtime to generate $poly(n)$ random bits and accept if they are all $0$'s. The probability of this happening is bounded by $1/O(2^{poly(n)})$.


Fundamental motivation behind the use of bits and binary representation This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory?

If for technical reasons building ternary computers where the information is encoded as trits was easier than building traditional binary computers, I get the feeling that most theoretical computer science and information theory would still use bits and base-2 representation by default.

Even if I have an intuitive feeling of why, I would have liked to know a formal explanation of that: from a purely theoretical standpoint what makes bits and binary representation special compared to any other base?

If the answer is more complex than one may first think, links to books and scientific papers are welcome.

Well, the fact is that binary values are much easier to handle technically that ternary values. And there are reasons for it. So if there was some technical breakthrough where suddenly ternary values become easy to handle, there would be a good reason to believe that binary values would have a similar breakthrough very soon.

So yours is a purely hypothetical question. And you are making assumptions about how people would react in a purely hypothetical situation.

In lots of situations, for many algorithms, binary or ternary doesn't matter. At a high level, we just talk about integers. But for many basic operations, ternary is at a disadvantage. Design a format for signed integers. Preferably one where the same representation is used for positive signed integers and for unsigned integers. You have a problem unless you use one trit and use it as a sign bit. Which means you now have a representation where not every trit value is valid.

Floating-point arithmetic: I don't remember if it was Knuth and Kahan who showed that "round to nearest even" has some very nice properties, and then showed that you have these nice properties whenever the floating-point base is 8k + 2 (including binary and decimal, what a luck) but not for base 3.

Design the logic for a full-adder. Two inputs from 0 to 2 and one input 0 or 1 (the carry from the previous operation). Quite complicated. Much much more complicated than binary. Going one level down, is there anything like NAND and NOR for trits that can serve as the basis of all logical operations? Try creating a fast multiplier. For binary, the basis for this is an operation which produces x*0 or x*1. Now you need something that produces x*0, x*1 or x*2. Wait, that can't be stored in a single trit. Trouble. Plus you can't use the ordinary full adder to finish off the fast multiplier.


Find a diffrent minimal spanning tree for a graph For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST:

Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$.
I want to find another minimum spanning tree $T'$ that has at least 1 different edge $e'$
such that the weight of $e'$ is differ from any weight of edges in $T$.

If $T'$ doesn't exist I can claim that every 2 different MST must have the same weight for each edge.
My intuition says that this claim is wrong but on the other hand I can't find example of $T'$ to contradict this claim.

You cannot find such a MST. Every two minimal spanning trees must have the same multiset of edge-weights.
Actually you can find the proof in the link that Raphael added:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?


3 * O(n^2) vs O(n^3) Currently while I was coding, I got a doubt.

While I was solving a particular type of problem I found it to be solved in    $O(n^3)$.

I have broken that problem and solved it in $O(n^2)$.

But to solve it I have broken that $O(n^3)$ to $3$ * $O(n^2)$

Is it a better solution than $O(n^3)$ or will it matter the number of $O(n^2)$ also?

Multiplying $O\left(n^2\right)$ by $3$ doesn't change it.  Literally, it remains the same thing:

$$3{\cdot}O\left(n^2\right)~=~O\left(3n^2\right)~=~O\left(n^2\right).$$

This is because such complexity qualifications don't track scalar multipliers.

The reason that we discard scalar multipliers is pretty simple: the actual run time will depend on how fast particular computer instructions work, such that if we cared about scalar factors, our complexity qualifications would become extremely context-specific.

For example, many real-world systems will speed up as they run a long-running algorithm due to optimizations that kick in as an algorithm runs (e.g., branch profiling CPU's and hot-spot code optimizations in VM's).  So, any scalar projection of run-time behavior would have to account for these factors.  Such an analysis could still be quite helpful and worth studying when appropriate, but that's not the role that complexity classes intend to fill.

So, as general performance analyses qualifications, complexity classes tend to focus on the largest order-affecting factors while hand-waving the scalar stuff as implementation-dependent.


RPI cluster performance related to network performance I'm writing my thesis and i have built a RPI cluster, containing 10 nodes which consists of RPI model 3b. I've them connected to two gigabit switches. I don't know the CAT of the cables. They are not connected to the Internet, they just live in their private network.

Further more, i've calculated the theoretical performance by the formula:

number of cores * average frequency * 16 FLOPs/cycle = x GFLOPS (Got the formula from https://www.slothparadise.com/how-to-run-hpl-linpack-across-nodes/ )

after i applied it, it turns out i should have 76,8 GFLOPS in theory assuming that the source is relaiable and correct. When i benchmark it using HPL 2.1 i've only reached little about 7 GFLOPS at best when trying out various variations.

Now to my question: i've read up on the RPI model, and it says it only have 10/100 Ethernet. Is that the source of my problem? Seeing i get out GFLOPS from a node, but the network transportation is much less then Gigabit speed which would mean 76,8 GFLOPS * 0,1 Gigabit/second = 7,68 GFLOPS (in theory). Or am i way off the tracks in my thinking?

I really appriciate any help, so i can know if i have to keep working on the configuration for the benchmarking or if i can move on. Also, i'm sorry if i have posted in the wrong place.

Stay safe out there!

I think i have solved it now. The problem was that in the example in the source they had:

8*3,50*16 and i was assuming (which is a very bad thing to do) that i should change everything except the 16, that it was a constant of sorts. Turns out, my RPI should have somewhere between 0 and 2 in the last multiple, alas it should be

4*1,2*x where x is somewhere between 0 and 2 (as my estimation) thus i have only to find out the actual number for X, and for some reason it seems hard to find it, one would have thought that the instructions per second or instructions per cycle would be documented for RPI.

bottom line, there was nothing wrong except for my thinking. sorry for this post, i should had read up a little bit more before i posted. I blame it on stress.

EDIT: i forgot to give the source that helped me solve the problem, here it is:

https://www.gpike.com/en/raspberrypi/benchmarking#hplc

and thx for the help!


Why is channel capacity of AWGN infinite? My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I don't understand how the professor can directly say the channel capacity is infinite. Don't we need to maximize mutual information between input and output to get the channel capacity? How to do that for continuous variables?

Here is a coding scheme that demonstrates the main idea:

Encoding: Let the power constraint $P$ be fixed and suppose we want to transmit one information bit a time. We set our coding scheme as $X(0) = \sqrt{P}, X(1) = -\sqrt{P}$, where $X$ is the encoding function.

Decoding: Let $Y$ denote the received signal and $Z$ the additive Gaussian noise like you defined. We set the decoder as $\hat{X} = \mathbb{1}_{\{Y > 0\}}(Y)$, where $\mathbb{1}_A(w)$ is the indicator function that yields $1$ if $w \in A$ and $0$ otherwise.

Probability of error: Let $P_e$ denote the probability of error. We assume the information bits are equally likely, since otherwise we could simply use optimal source coding to ensure they are. Then,

\begin{align}
P_e &= \frac{1}{2}P(Y>0 | X = -\sqrt{P}) + \frac{1}{2}P(Y \leq 0 | X = \sqrt{P}) \\
&= \frac{1}{2}P(Z > \sqrt{P} | X = -\sqrt{P}) + \frac{1}{2}P( Z \leq -\sqrt{P} | X = \sqrt{P}) \\
&= P(Z > \sqrt{P}) = 1 - \Phi\left(\sqrt{\frac{P}{\sigma^2}}\right),
\end{align}

where $\Phi(t) = \int_{-\infty}^t \frac{1}{\sqrt{2\pi}}e^{-\frac{-t^2}{2}}$ is the Gaussian cdf. The key observation here is that, as a cdf, this is a non-decreasing function that converges to $1$ in the limit. By increasing $P$, we can make it arbitrarily close to $1$. In other words, let $\epsilon > 0$, for large enough $P$, $P_e < \epsilon$. Without a power constraint, we can send one bit of information with arbitrarily small probability of error. This coding scheme proves a rate of $1$ is achievable.

Ok, so how do we get from an achievable rate of $1$ to $\infty$? Let's see what happens when we increase our rate from $1$ to $2$, by encoding two information bits at a time. Let
$$X(b_1, b_2)=\begin{cases} \sqrt{P}, &\text{ if } (b_1,b_2) &= (0,0) \\ \frac{\sqrt{P}}{2}, &\text{ if } (b_1,b_2) &= (0,1) \\ -\sqrt{P}, &\text{ if } (b_1,b_2) &= (1,0) \\ -\frac{\sqrt{P}}{2}, &\text{ if } (b_1,b_2) &= (1,1) \end{cases}$$

Now, if you follow the same procedure as above, you'll find out that $P_e = P\left(Z > \frac{\sqrt{P}}{2} \right) = 1 - \Phi\left(\sqrt{\frac{P}{4\sigma^2}} \right)$. Therefore, we can again find a (larger) $P$ that allows us to squeeze $2$ information bits into $1$ coded bit with an arbitrarily small probability error. As you can imagine, if $P$ is unbounded, we can simply keep doing this to encode more and more information bits to in a single coded bit without sacrificing from $P_e$.

Moral of the story: Without a bound on transmission power, we can pick a set of coded bits (codewords of length 1) that achieve arbitrarily small $P_e$ and we can do this for an arbitrarily large set of code bits to squeeze as many information bits into 1 as we want. So, the achievable rates is unbounded and since the capacity is the smallest upper bound on the set of achievable rates, it is $\infty$.


How to revert a carryless polynomial multiplication? In the carryless multiplication of two polynomials in a 8-bit environment, is it possible to obtain the original 8-bit values from the result?

As an example:

$$\begin{align}
(x^{11} + x^{10} + x^9 ) + (x^7 + x^5 + x^4 + x^3 + x^1) &= (x^6 + x^5 + x^1) \times (x^5 + x^3 + x^2 + x^0)\\
(x^{11} + x^{10}) + (x^6 + x^4 + x^2 + x^1) &= \text?\times\text?\quad \hbox{(each value must fit in 8 bits)}
\end{align}$$

I know that I can try every possible value (it's only two 8-bit values) but that seems blunt!

Yes, there are efficient algorithms for this.  All you need to do is factor the resulting polynomial, but taking all coefficients modulo 2.  This is known as polynomial factorization in the field $GF(2)$.  There are standard algorithms for polynomial factorization, and they are quite efficient.  For instance, you could look at Sage or another mathematical computation toolkit; it's likely to have an existing implementation of those algorithms.

Note that after you've factored the polynomial, there may still be some ambiguity about what the original two polynomials were.  For instance, if you are given the polynomial $x^5+x^3$, the two polynomials might be $x^2+1$ and $x^3$, or they might be $x^3+x$ and $x^2$, etc.  You won't be able to tell, given just the product.


fixed point in regular expressions I've posted this question first on StackOverflow but this section seems more suited for this kind of questions.
Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll figure out the regular expression I'll derive the equivalent Finite Automaton that accepts the language generated by the grammar), but instead I'm trying to understand the methodology to derive regular expressions (if they exists, from context-free grammars)

I have this productions of a context free grammar (axiom S, e is the empty word)

S->AS|b|A
A->abA|Ab|e
I have to figure out a regular expression (if exists) that generates a language equivalent to the one generated by that grammar.

So far i wrote that

L(S)=L(A)L(S) + b + L(A) = L(A)*(L(A) + b) (by Arden Rule)
L(A)=(ab)*(L(A)b+e)

I've tried the method of finding the fixed point (I'd like more info about that since seems I can't get the hang of it

for A: 0 -> e -> (ab)*(b+e) -> (ab)*[(ab)*(b+e)](b+e)

should i check if (ab)(b+e) = (ab)(ab)*(b+e) (if that's is the fixed point? Or should i go ahead?) It's not the first exercise I'm having trouble with so any help would be appreaciated, Thanks.

As all productions in  $A\rightarrow \mathrm{ab}A\text{ }|\text{ }A\mathrm{b}\text{ }|\text{ }ε$ are linear, and (crucially) there is only one non-terminal symbol, all derivation sequences can be reordered into equivalent ones where left-side derivations always precede (or always succeed) right-side ones.

For instance:

$wAv \Rightarrow  w\mathrm{ab}Av \Rightarrow  w\mathrm{ab}A\mathrm{b}v \Rightarrow  w\mathrm{abab}A\mathrm{b}v \Rightarrow  w\mathrm{abab}A\mathrm{bb}v\equiv \\wAv \Rightarrow  wA\mathrm{b}v \Rightarrow  wA\mathrm{bb}v \Rightarrow  w\mathrm{ab}A\mathrm{bb}v \Rightarrow  w\mathrm{abab}A\mathrm{bb}v$

(This is a hint of what an inductive proof using fixed-points would look like in this particular case. Check this if you are determined to go down that road).

This means that this grammar can be converted into a regular grammar in two steps, by grouping left-linear and right-linear productions:

1.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow A''\mathrm{b}\text{ }|\text{ }ε$

2.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow \mathrm{b}A''\text{ }|\text{ }ε\\$

So $\mathcal{L}(A) = (\mathrm{ab})^*\mathrm{b}^*$


What is the difference between ∀ and Π in the Calculus of Constructions? As I've learned, the Calculus of Constructions has only two binders - $\lambda$ and $\Pi$. Morte, for example, has $\forall$ as a mere alias of $\Pi$. Yet, on the paper Self Types for Dependently Typed Lambda Encodings, there are types such as:

$$\begin{gather}
  \mathrm{Nat} := \forall X. (X \rightarrow X) \rightarrow X \rightarrow X \\
  \mathrm{It} : \forall X. \Pi x : \mathrm{Nat}. (X \rightarrow X) \rightarrow X \rightarrow X \\
  \mathrm{Ind} : \forall P : \mathrm{Nat} \rightarrow \mathord{\ast}. \; \Pi x:\mathrm{Nat}. \; (\Pi y:\mathrm{Nat}. (P \, y \rightarrow P (S \, y))) \rightarrow P \, \bar 0 \rightarrow P \, x
\end{gather}$$

Notice that the paper uses both $\forall$ and $\Pi$. Moreover, $\forall$ is used both with the syntax $\forall a : b \rightarrow c$ and $\forall a . b$. I can't parse those expressions. What is the difference between $\forall$ and $\Pi$, and how would you express those types on Morte?

I had only a quick and cursory look at the paper — so take this with great care.

It appears that $\Pi X$ is used to express dependent products as in the calculus of constructions. Instead, $\forall X$ looks more like polymorphic types in ML.

The main difference is that, if $t : \Pi x. P(x)$ then $t T : P(T)$, while if $t : \forall x. P(x)$ then $t : P(T)$. Note that the former requires an additional argument, the second does not: the polytype gets instantiated automatically. Rules $\mathit{App}$ and $\mathit{Inst}$ at page 7 cause this difference.

Of course, this also means that introducing $\Pi$ requires a lambda, while introducing $\forall$ does not.

There also is some type / kind distinction related to this, but I can't comment on that precisely.


A recursive language minus a recursively enumerable language results in a recursive language? I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question.

Aren't all recursive languages also recursively enumerable? Does this mean the answer to the question is that a recursive language minus a recursively enumerable language results in a recursively enumerable language, but more specifically, a recursive language?

Let $L$ be an r.e. language which is not recursive (for example, $L$ can be the language of descriptions of Turing machines that halt on the empty input). Then $\Sigma^*$ is recursive but $\Sigma^* \setminus L$ is not recursive (exercise).

More generally, when faced with a question like this, try the following two approaches in parallel:

Try to prove the claim.
Try to refute the claim using a counterexample.

The two approaches can even feed each other.


Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time? In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of vertices). But how can we talk about a polynomial time reduction if we generate exponential-size numbers?

I guess that this is the key why Vertex Cover is strongly NP-complete and Subset-Sum is only weakly NP-complete. But I didn't get why it is in fact a polynomial time reduction.

The key is indeed that the numbers are expressed in binary. As you observe, the numbers could have a value that is exponential in the size of the vertex cover instance. If the reduction "wrote them out" in unary when computing the Subset-Sum instance, this would take exponential time. However in binary, writing down the bits of the number (i.e. computing their representation in the Subset-Sum instance) only takes polynomial time.

Just to emphasise the distinction, it only takes 7 digits to write out 1,000,000 in base ten, so writing it down takes about 7 steps. If we did it in unary, it would take about a million steps. The same thing is happening in the reduction, if it were using unary, it would not be polynomial in the size of the graph, but in binary - because what we're measuring is the number of steps taken to write it down - it is polynomial.


find maximum sum of xors we are given an Array

Array size <= 10^4 .

0 <= A[i] <= 15

We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum those xors.

for example,  one subset could have indices 0, 3, and 7, and another subset could have indices 1, 2, and 4
find the max sum.

4^n approach is very expensive.

there are only 16 different values of xor so for each value of xor=X we can search in array if is it possible to partition the array such that we get xor=X.

For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can determine the possible XORs resulting from partitions of the array into four subsets, and so calculate the maximum sum. The resulting algorithm runs in linear time.


How to practically measure entropy of a file? I'm trying to measure now much non redundant (actual) information my file contains.  Some call this the amount of entropy.

Of course there is the standard p(x) log{p(x)}, but I think that Shannon was only considering it from the point of view of transmitting though a channel.  Hence the formula requires a block size (say in bits, 8 typically).  For a large file, this calculation is fairly useless, ignoring short to long distance correlations between symbols.

There are binary tree and Ziv-Lempel methods, but these seem highly academic in nature.

Compressibility is also regarded as a measure of entropy, but there seems to be no lower limit as to the degree of compression.  For my file hiss.wav,

original hiss.wav  = 5.2 MB
entropy via the Shannon formula = 4.6 MB
hiss.zip = 4.6 MB
hiss.7z = 4.2 MB
hiss.wav.fp8 = 3.3 MB

Is there some reasonably practicable method of measuring how much entropy exists within hiss.wav?

Entropy is a feature of a random variable. A given file has zero entropy, since it is constant. Entropy makes sense in many situation in which there is no channel, and you can apply it to a random ensemble of, say, WAV files, generated from a given source. In this case, your $x$ is the entire WAV file.

The actual WAV file (excluding the header) can be thought of being generated by some Markovian source. This source produces sounds amplitudes ("samples") in a sequence, each one depending on the ones preceding it. After running the process for very long, the entropy of each sample (more accurately, the conditional entropy given the preceding samples) gets very close to some limiting value, which we define to be the entropy of the source. The entropy of $N$ samples is $N$ times that number (in the limit; again, more accurately, we are measuring the conditional entropy). Lempel and Ziv showed that if the sample entropy is $H$ bits, then their algorithm compresses $N$ samples to $HN + o(N)$ bits, with high probability (the probability is over the samples). Lempel–Ziv compression is quite popular in practice, used for example in the popular gzip format.

Due to this result of Lempel and Ziv, the entropy of a source can be approximated by compressing a long sequence of samples using the Lempel–Ziv algorithm. This doesn't estimate the entropy of the specific samples, which is not a well-defined concept (a constant sequence has zero entropy), but rather the entropy of the source generating it.

A related concept is algorithmic entropy, also known as Kolmogorov complexity. It is the length of the shortest program generating your file. This quantity does make sense for an individual file. In the case of a file generated by a random source, the Lempel–Ziv theorem shows that the algorithmic entropy of a file is bounded, with high probability, by its Shannon entropy. Unfortunately, algorithmic entropy isn't computable, so it's more of a theoretical concept.

To complete the picture, I suggest reading Shannon's paper on Prediction and entropy of printed English for a different approach to estimating the entropy of a source.


Model marbel toy with finite automata I'm resolving this question of Hopcroft and et al Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x_1,x_2$ and $x_3$ cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next will take the opposite branch.

I got resolve the question ...

a)Model this toy by finite automaton: To model this toy, a state is represented as sequence of three bits followed by r or a (previous input rejected or accepted). For instance, 010a, means left, right, left, accepted. Then the Transition table is

b)Informally describe the language of the automaton

but not b) question. How I will be able to resolve this question?

EDIT
I see a solution here I modify my question using suggestions and that solution. According that solution exist a case:

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0, or (X-3) mod 4 = 0 (X is the numbers of 0's and 1's).

For my question, from this case I get the subcase

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0.

Then, the restrictions are: the number of 1's, without the ending, is even and the number of 0's is impar. I will be able to verify that configuration with that restrictions for few instances, but How I will be able to demonstrate that the $x_2$ interrupt configuration is \?

Count $A$'s and $B$'s. The next $A$ will only exit at $D$ iff the first two levers are in right position. When does that happen? The first lever toggles at every $A$, but the second lever interacts with the $B$'s.

At the same time, the situation for $B$ is symmetric. The next $B$ will not exit $D$ only if both levers are left. When does that happen?


How can I calculate optimal batch sizes for calls to an external server? So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - roughly 30 seconds. I could group all those commands together and send them off, have the server execute them all, and then get my results. But that's significantly slower than grouping those commands into batches, which I send off all at the same time, and can then execute on that server in parallel.

However, I can't make the batches too small, because I'm doing this from a browser, and most modern browsers can only keep ~6 concurrent open connections with the same server. So you get a trade off - for large batch sizes, I'm not sending enough concurrent commands to the server. For small batch sizes, I'm sending so many that the browser gets backed up.

I've tried this experimentally, and I wind up with data that looks something like this (pardon the terrible drawing):

On the x axis is the number of batches I use, and on the y axis is the time the whole resulting calculation takes. I haven't succeeded in finding a model that really works for this data, only a basic crude approximation.

All I really want to know is, is there research on this kind of thing I can look up? Some way that, given code execution times on the server, and delay times for getting there, I can calculate the optimal batch size? I can't be the only person who's wanted to solve this problem. If there isn't, then what do you think?

Here's the simplest model I can think of.  Assume that each command takes $\beta$ seconds to complete, and it takes $\alpha$ seconds to create a connection.  Then I would expect that it would take $\alpha+\beta k$ seconds to complete a batch of size $k$.  If there are $N$ commands in total, then we'll need $N/k$ batches.  With 6 concurrent TCP connections to the server at a time, this means it'll take $N/(6k) \times (\alpha + \beta k)$ seconds to complete all of the batches.  As a function of the batch size, this is

$$f(k) = {\alpha + \beta k \over 6k} N.$$

You can find the optimal batch size by finding $k$ that minimizes $f(k)$, which can in turn be done using calculus by taking the derivative and setting it to zero: $f'(k)=0$.  Note that

$$f'(k) = {6\beta k - 6(\alpha + \beta k) \over 36k^2} N
= {\alpha \over 6k^2} N.$$

Setting this to zero, we find that $f(k)$ is minimized by taking $k$ as large as possible; in the limit we have $\lim_{k \to \infty} f(k) = \beta/6 N$.

Obviously, this is not what you observe empirically, which suggests that this model is not accurate.  I suggest as a next step you start to brainstorm why the model might be inaccurate or what factors it might be overlooking.  You might also want to measure and plot some additional metrics, e.g., the average time it takes for each batch to complete (as a function of batch size, i.e., the time between starting execution of command 0 from batch $i$ to starting execution of command 0 from batch $i+1$).


King of the North: Placing bannermen surrounding castle I was trying to solve the King of the North problem in Kattis. Basically, the problem is, the king has a castle to protect. To do this, he wants to place bannermen across the open areas surrounding the castle (some parts are closed thanks to natural barriers).

A more detailed description of the problem:
Given a grid of $R$ rows and $C$ columns, where one square contains our castle and some contain walls. We can place bannermen, who can blockade a square. Each open square has a different amount of bannermen required to form a blockade, which is given. Our task is to determine the minimum amount of bannermen that have to be fielded such that the castle is unreachable from the edge of the grid. (walls and blockaded squares are impassable)

Please go through the attached link for an even more detailed (and colourful) description of the problem.

My idea to solve this:

  Go to each outermost corner of the map. From each of these points, do a A* search. This will give the shortest path from the point to the
  castle.
  For each such point on the shortest path, try to see which ones are 'critical' - meaning placing bannermen on those points will force the
  enemy to take a longer path.
  Among all such critical points, see which ones need lesser bannermen.

Anyone has a better idea?

I do not like my approach, particularly because it involves heuristics, and I am not sure whether it is correct.

This appears to be a max-flow/min-cut problem. Consider the directed graph $G$ with all non-hill/wall squares as vertices and edges between the neighbouring non-hill/wall cells in the map.

As the weights in the problem are on the vertices, but we need them as capacities on the edges, replace each vertex $u$ by the pair of vertices $u_{in}$, $u_{out}$ such that $c(u_{in},u_{out}) = w(u)$ and all incoming edges of $u$ are connected to $u_{in}$ and all outgoing edges of $u$ are connected to $u_{out}$. Give the capacity $+\infty$ to all other edges (so we cannot 'cut' those edges).

Call our castle the sink and connect all borders of the map to a source. Note that the edges can be bidirectional, except for those connected to the source or sink.

Now, the minimum amount of bannermen to required to protect the castle is equal to the minimum value over edges in our graph $G$ we need to remove such that the sink (our castle) cannot be reached from the source (the outside of the map). This is precisely the minimum cut on this graph $G$. So, we can compute the number of men required in $O((R+C)^3)$ using the Edmonds-Karp algorithm, where $R,C$ is the amount of rows and columns in our map. Given that $R,C\leq 300$, this approach is likely fast enough to solve the problem within the time limit.

Your approach looks a lot like an heuristic approach to the min-cut problem. I don't see any reason that this would be always be correct in this case, so that approach would likely fail, as you suspect.


Compression of domain names I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or domain name (U-label) consists of a string of Unicode characters, typically constrained to one language depending on the top-level domain (e.g. Greek letters under .gr), which is encoded into an ASCII string beginning with xn-- (the corresponding A-label).

One can build data models not only from the formal requirements that

each non-Unicode label be a string matching ^[a-z\d]([a-z\d\-]{0,61}[a-z\d])?$;
each A-label be a string matching ^xn--[a-z\d]([a-z\d\-]{0,57}[a-z\d])?$; and
the total length of the entire domain (A-labels and non-IDN labels concatenated with '.' delimiters) not exceed 255 characters

but also from various heuristics, including:

lower-order U-labels are often lexically, syntactically and semantically valid phrases in some natural language including proper nouns and numerals (unpunctuated except hyphen, stripped of whitespace and folded per Nameprep), with a preference for shorter phrases; and
higher-order labels are drawn from a dictionary of SLDs and TLDs and provide context for predicting which natural language is used in the lower-order labels.

I fear that achieving good compression of such short strings will be difficult without considering these specific features of the data and, furthermore, that existing libraries will produce unnecessary overhead in order to accomodate their more general use cases.

Reading Matt Mahoney's online book Data Compression Explained, it is clear that a number of existing techniques could be employed to take advantage of the above (and/or other) modelling assumptions which ought to result in far superior compression versus less specific tools.

By way of context, this question is an offshoot from a previous one on SO.

Initial thoughts

It strikes me that this problem is an excellent candidate for offline training and I envisage a compressed data format along the following lines:

A Huffman coding of the "public suffix", with probabilities drawn from some published source of domain registration or traffic volumes;
A Huffman coding of which (natural language) model is used for the remaining U-labels, with probabilities drawn from some published source of domain registration or traffic volumes given context of the domain suffix;
Apply some dictionary-based transforms from the specified natural language model; and
An arithmetic coding of each character in the U-labels, with probabilities drawn from contextually adaptive natural language models derived from offline training (and perhaps online too, although I suspect the data may well be too short to provide any meaningful insight?).

Huffman coding is optimal for letters and can certainly be adapted to sequences. For instance, if the sequence "ab" results in fewer bits than the bits for "a" and "b", then simply add it to the tree ...and so on.

...you can also probably use some simple library which does that all for you with near optimal performances, so that you won't gain much using your custom made super fancy compression algorithm.


Conditional probability in Expectation Maximization (EM) I've got the following equation:
$p(j = 1 | x, \theta) = \frac{p(j=1,x | \theta)}{p(x | \theta)}$
Why does it hold? Or maybe, how do I use Bayes Theorem in this case, i.e. if we do not only have $p(j = 1 | x)$ but $p(j = 1 | x, \theta)$?

I think I found the solution.
In general we have:
$$p(\theta,x,j=1) = p(j = 1 | x, \theta) \cdot p(x,\theta) \\
\Leftrightarrow \frac{p(\theta, x, j=1)}{p(x, \theta)} = p(j=1| x,\theta)$$
By using this, we get:
$$p(j = 1 | x, \theta) = \frac{p(\theta, x, j=1)}{p(x,\theta)} = \frac{p(j=1,x|\theta) \cdot p(\theta)}{p(x|\theta) \cdot p(\theta)} = \frac{p(j=1,x | \theta)}{p(x|\theta)}$$


Is the set of pairs of TMs at least one of which accepts the empty word semi-deciable? L = { < M1,M2 > | M1,M2  are TM's and Ɛ ∈ L(M1) ∪ L(M2) }

Where Ɛ = Epsilon

I know that this language is undecidable, but why it is semidecidable too.

What i have tried is =>

Using Rice's Theorem, part 2

T(no) = (0,1)^+ and T(yes) = (0,1)*

Which gives that T(yes) is not a subset of T(no), and this says that it is semidecidable.

Is my understanding right ?

Rice's second theorem can be used to show for some sets that they are not semi-decidable, but not the opposite.

In order to show that this set is semi-deciable, just follow the definition and construct a semi-decider.

   Idea: Simulate both $M_1$ and $M_2$ on $\varepsilon$ simultaneaously using dovetailing. If either one halts and accepts, stop simulating and accept.


Efficiency/Redundancy in Chomsky normal form I have a context-free grammar with the following production rules, $S$ being the start symbol:

$$\begin{align*}
S &\to AB \\
A &\to a \\
B &\to a\end{align*}$$

Is this in Chomsky normal form?

My problem is I thought CNF is supposed to be an efficient way to write a grammar, yet the grammar is not efficient in the sense that we can clean its rules as follows:

$$\begin{align*}S &\to AA\\
A &\to a\end{align*}$$

Both grammars are in CNF. One of the possible rule formats for CNF is $A \to BC$, where $A$, $B$, and $C$ are non-terminals, but it is not necessary for them to be different from another. Hence, in your case, $S \to AA$ is also a valid rule for CNF.

I should add CNF has nothing to do with an "efficient" way to write a grammar (however you should define that; if you simply mean the description is shorter, then counterexamples abound). Rather, CNF is useful when employing techniques such as the CYK algorithm.


Dynamic programming table for finding similar substrings is too large Substring Diff
  Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of
  mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}$. In set
  notation, $M(i, j, L)$ refers to the size of the set $\{0 \leq x < L \mid p_{i + x} \neq q_{j + x}\}$.

  Given an integer $K$, your task is to find the maximum length $L$ such
  that there exists pair of indices $(i,j)$ for which we have $M(i, j, L) \leq K$. Of course, we should also have $i + L - 1 \leq n$ and $j + L - 1 \leq n$.

  Constraints

  $0 \leq K \leq |P|$
  Both $P$ & $Q$ would have the same length
  The size of each of the string would be at the max 1500
  All characters in $P$ and $Q$ are lower-case English letters.

The recursive function will have the form:

longest(string1, string2, allowed_mismatches) =
    {
        ... (something :P )
    }

The state space then has size $K^3$. With an upper bound on $K$ of 1500, the running time and space usage will be terrible... So direct dynamic programming will not work without some additional property to reduce the state space.

Ideas?

UPDATE

Using the ideas suggested by both Yuval and Vor, I came up with the following solution that works like a charm, running in $O(K^2)$ time and using $K$ space.

def longest_range_min_sum(str1, str2, start1, start2, slice_size, max_sum):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < slice_size:
        if str1[start1 + i + longest] != str2[start2 + i + longest]:
            running_sum += 1
        if running_sum > max_sum:
            if str1[start1 + i] != str2[start2 + i]:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest

import sys

data = sys.stdin.readlines()
num_cases = int(data.pop(0))
for ignore in xrange(num_cases):
    max_mismatches, str1, str2 = data.pop(0).split()
    max_mismatches = int(max_mismatches)
    m = n = len(str1)
    longest = 0
    for i in xrange(m + n + 1):
        if i > n:
            slice_size = m - (i - n)
        else:
            slice_size = min(i, m)
        if slice_size == 0:
            continue
        end1 = max(m, m - i)
        if i > n:
            end1 = m - (i - n)
        start1 = end1 - slice_size
        end2 = min(i, n)
        start2 = end2 - slice_size
        #print zeros_and_ones
        #print str1[start1:end1], ' - ', str2[start2:end2]
        longest_in_sub = longest_range_min_sum(str1, str2, start1, start2, slice_size, max_mismatches)
        #print longest_in_sub
        longest = max(longest, longest_in_sub)
    print longest

One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.

What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The sequence in question is $J_1 = I_1 - I_0,\ldots,J_{t+1}=I_{t+1}-I_t$. Every $K+1$ consecutive numbers $J_a,\ldots,J_{a+K}$ correspond to a maximal solution for your problem of length $J_a + \cdots + J_{a+K} - 1$. The entire algorithm takes linear time.

Edit: This calculates the maximal $L$ such that $M(i,i,L) \leq K$ for some $i$. The actual problem wanted to find the maximal $L$ such that $M(i,j,L) \leq K$ for some $i,j$. By considering all possible shifts, we can solve this in $O(N^2)$ time and $O(K)$ space.


Complexity of the language of all TMs $M$ such that $L(M)$ is decidable Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?

This set is not r.e. nor co-r.e., in fact it's complete at the 3rd level of the arithmetic hierarchy ($\Sigma^0_3$-complete). This is shown in Soare's textbook.


Are there any countable sets that are not computably enumerable? A set is countable if it has a bijection with the natural numbers, and is computably enumerable (c.e.) if there exists an algorithm that enumerates its members.

Any non-finite computably enumerable set must be countable since we can construct a bijection from the enumeration.

Are there any examples of countable sets that are not computably enumerable? That is, a bijection between this set and the natural numbers exists, but there is no algorithm that can compute this bijection.

Are there any examples of countable sets that are not enumerable?

Yes.  All subsets of the natural numbers are countable but not all of them are enumerable.  (Proof: there are uncountably many different subsets of $\mathbb{N}$ but only countably many Turing machines that could act as enumerators.)  So any subset of $\mathbb{N}$ that you already know is not recursively enumerable is an example – such as the set of all numbers coding Turing machines that halt for every input.


Counting different words in text using hashing I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table?

My intuition says that applying the hashcode function to every word in the text, as result we will have words with different hash values in different buckets and the same words will have the same bucket and therefore we will have a collision problem which we can resolve using the chaining method.

Does it work like that?

If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table.

So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up.

But you still have to deal with collisions, because two different words can have the same hash code.

This way, the expected time complexity is $\mathcal{O}(n)$, where $n$ is the total count of characters in the text, assuming a good hash function.


Randomized Rounding of Solutions to Linear Programs Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global optimum. However, enforcing integral solutions has runtime that is exponential in the worst case. To cope with this barrier, several approximation methods related to ILPs can be used,

Primal-Dual Schema
Randomized Rounding

The Primal-Dual Schema is a versatile method that gives us a "packaged" way to come up with a greedy algorithm and prove its approximation bounds using the relaxed dual LP. Resulting combinatorial algorithms tend to be very fast and perform quite well in practice. However its relation to linear programming is closer tied to the analysis. Further because of this analysis, we can easily show that constraints are not violated.

Randomized rounding takes a different approach and solves the relaxed LP (using interior-point or ellipsoid methods) and rounds variables according to some probability distribution. If approximation bounds can be proven this method, like the Primal-Dual schema, is quite useful. However, one portion is not quite clear to me:

  How do randomized rounding schemes show that constraints are not violated?

It would appear that naively flipping a coin, while resulting in a 0-1 solution, could violate constraints! Any help illuminating this issue would be appreciated. Thank you.

Of course, if you round, you have to verify that rounding preserves feasibility.

Let us for example consider the relaxed VERTEX-COVER LP formulation.
$$
\begin{array}{lll}
\text{min} & \sum_{v\in V}c(v)x_v & \\
\text{s.t.} &x_u+x_v\ge1, & \quad (u,v)\in E \\
&x_v\ge 0. & \quad v\in V
\end{array}
$$

It is known that the solution to this problem is half-integral, i.e., each variable is either $0$, $1$, or $1/2$. The rounding scheme works as follows, whenever your solution contains $x_v=1/2$ you round up and set $x_v=1$. The constraints of the ILP were
$$
\begin{array}{lll}
 &x_u+x_v\ge1, & \quad (u,v)\in E \\
&x_v \in \{0,1\}. & \quad v\in V
\end{array}
$$
Both constraints are fulfilled after the rounding. And you have a nice 2-approximation.


Lazy streams and infinite series I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard:

  A lazy stream is an infinite list of values that is computed lazily.
  The stream of keystrokes that a user presses on the keyboard can be
  represented as an infinite (or arbitrarily long) list of all of the
  keystrokes that the user is ever going to press. You get the next
  keystroke by taking the head element of the stream and saving the
  remainder. Since the head is only computed lazily, on demand, this
  will result in a call to the operating system to get the next
  keystroke. What’s special about the lazy stream approach is that you
  can treat the entire stream as a value and pass it around in your
  program. You can pass it as an argument to a function or save the
  stream in a data structure. You can write functions that operate on
  the stream as a whole. You can write a word scanner as a function,
  toWords, that transforms a stream of characters into a stream of
  words. A program to obtain the next 100 words from the standard input
  might look something like apply show (take 100 (toWords stdIn)) where
  stdIn is the input stream and take n is a function that returns the
  first n elements in a list. The show function is applied to each word
  to print it out. The program is just the simple composition of the
  functions. Lazy evaluation ensures that this program is equivalent to
  the set of nested loops that you would write for this in an [imperative]
  program. This is programming at a much higher level than you typically
  get with [imperative] languages.

I take it he doesn't mean just a list of the 26 letters of the alphabet, rather, something more like every possible word and combination thereof, i.e., similar to the theoretical possibility of finding yours and everyone's birthday if you look hard enough in the irrational never-repeating infinite stream of $\pi$ places. That is, somewhere in the infinite series of $\pi$ decimal places is your birthday mmddyyyy-style. Is this in fact what is meant here? Also, is this in any way related to infinite recursion?

In a similar vein, I once was told that no functional language is truly pure, and he gave the example of a function that "goes out" and gets the exact time from an atomic clock. Is this the same sort of issue, where, e.g., an infinite list of possible times is available for a list operation?

No, that's not what the author means. The author means the specific sequence of characters the user will actually type. If the user is about to write a letter to Al that might be:

'D'::'e'::'a'::'r'::' '::'A'::'l'::rest

The point is that you conceptually have "all" of the characters, and you can (with a bit of care) process this list like any other list.


Conditions for Linear Diophantine Equations to always have a solution Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution.

Over $\mathbb N$, is there any such constraint that guarantees that a solution always exists? Or, if not, can it be tested in polynomial time?

Short answer: No.  Most likely, no useful constraint exists; and it can't be tested in polynomial time.

Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP.  In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP).  Here's how the reduction works:

Suppose we have an ILP instance with variables $x_1,\dots,x_k$.  We'll modify it by introducing variables $x_1^+,\dots,x_k^+$ and $x_1^-,\dots,x_k^-$.  Then we'll replace each inequality

$$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$$

with the equality

$$c_0 + c_1 x_1^+ - c_1 x_1^- + \dots + c_k x_k^+ - c_k x_k^- = y_j$$

and the inequality $y_j \ge 0$, where $y_j$ is a fresh new variable.  Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x_i^+ \ge 0$, $x_i^- \ge 0$, $y_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables.  Note in particular that we are guaranteed to have $v>n$, since we must have $k>0$.  Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x_i^+ = \max(0,x_i)$ and $x_i^- = \max(0,-x_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x_i = x_i^+-x_i^-$).  Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem.  Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too.  That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP.  You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).


If A is poly-time reducible to B, is B poly-time reducible to A? Basically, is the following statement true?

  $A \leq_p B$ $\rightarrow$ $B \leq_p A$

Short answer: No.

For one example, take $A$ to be the language $A = \{0, 1\}^*$, i.e. the language that contains every possible string. It is polytime reducible to pretty much anything, for example 3-SAT (the reduction outputs the formula $x\wedge y \wedge z$ on every input). But 3-SAT is definitely not reducible to $A$: there is nothing to map unsatisfiable instances to.

Maybe a bit less silly. Take $A$ to be any problem in P. Take $B$ to be a problem complete for exponential time (for example the problem of deciding, given a Turing machine $M$, an input $x$, and a number $k$ written in binary, whether $M$ halts on $x$ within $k$ time steps). Because $B$ is complete for exponential time, $A$ is reducible to $B$. Because a polytime reduction from $B$ to $A$ would imply a polytime algorithm for $B$ and therefore for any exponential time problem, contradicting the time hierarchy theorem, such a polytime reduction does not exist.


Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time? Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to check if the diagonals equal $N$ as they get set, but I realized this wouldn't work if a vertex appeared in multiple negative-weight cycles.

No, there isn't (not unless P=NP).  Take an unweighted directed graph on $n$ vertices, and set all of the edge weights to $-1$.  Now there is a simple cycle of weight $-n$ if and only if there is a Hamiltonian circuit in the original graph.  But detecting the existence of Hamiltonian circuits is NP-hard.  Therefore your problem is NP-hard, too.


Algorithm to find all acyclic orientations of a graph I am working on acyclic orientations of undirected graphs and have the following questions:

Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ?
What is the number of acyclic orientations?
It is known (from here) to be $(-1)^p\ \chi(G,-\lambda)$ for a graph $G$ with $p$ vertices where $\chi$ is the chromatic polynomial evaluated at $-\lambda$; but I wasn't successful in understanding how to evaluate $\chi$ at a negative value ($-\lambda$).

As Yuval noted, you can count the number of acyclic orientations by evaluating the chromatic polynomial of a graph at negative unity. For computing chromatic polynomials, there are efficient algorithms known for some graph classes.

There is also a recursive algorithm for generating all acyclic orientations of a graph given by Squire [1]. The algorithm requires $O(n)$ time per acyclic orientation generated. Roughly 20 years ago this was the fastest algorithm known; it's possible a faster one is known now, or that you can improve Squire's algorithm by known techniques.

[1] Squire, M. B. (1998). Generating the acyclic orientations of a graph. Journal of Algorithms, 26(2), 275-290.


In Constraint Programming, are there any models that take into account the number of variable changes? Consider a CSP model where changing the value of a particular variable is expensive. Is there any work where the objective function also considers the number of changes in the value of the variable during the search process?

An example: The expensive-to-change variable may be in the control of some other agent and there is some overhead of involving that agent to change the variable. Another example: The variable participates in one of the constraints, and the satisfaction of this constraint involves calling an expensive function (such as, a simulator), e.g. $z = f(x, y)$ is the constraint, and $f$ is an expensive-to-compute function. Therefore, $x$ and $y$ are expensive-to-change variables.

It sounds like you want a cost-sensitive (cost-aware, budgeted) optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on $x$ and $y$) is a multicriteria optimization problem, and those tend to be very hard to solve. A common approach is to specify a budget for the maximum allowable costs and then minimize the objective function with respect to $costs(x,y) \le Budget$. This formulation tends to fit nicely into existing frameworks as an additional constraint. Of course, specifying the cost function and the allowable budget in such a way that you get meaningful solutions can be difficult - this will depend on the specific problem you are trying to solve.


Two definitions of universal hash functions I have seen two definitions of universal hash functions in the literature.

For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$.

Definition 1:

  A family $\mathcal H$
  of hash functions from $[n]$ to $[m]$ is a
  $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$ and any possibly identical
  $v_1,\ldots,v_k\in[m]$, $$ \Pr\limits_{h\in\mathcal H} [h(x_1)=v_1\wedge \cdots \wedge h(x_k) = v_k] \leqslant 1/m^k \enspace . $$

Definition 2:

  A family $\mathcal H$
  of hash functions from $[n]$ to $[m]$ is a
  $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$, $$ \Pr\limits_{h\in\mathcal H} [h(x_1)=\cdots=h(x_k) ] \leqslant 1/m^{k-1} \enspace . $$

In both definitions if equality holds then it is called strongly $k$-universal or alternatively $k$-wise independent hash family.

Clearly the first definition implies the second. But is the other direction true?

It is easy to see that this is not the case for $n\leqslant m$.

  This is a counter example when $[n]\subseteq [m]$:

  Consider the family $\mathcal H$ composed of only one element, the
  identity function: $x \mapsto x$. It satisfies the second definition
  since for all $x \neq y \in [n], \Pr_{h\in\mathcal H} [h(x) = h(y)] = 0 \leqslant 1/m^{k-1}$. However, it does not satisfy the first definition
  since for all $x,y\in[n], \Pr_{h\in\mathcal H}[h(x) = x \wedge h(y) = y] = 1 > 1/m^k$.

  This answer is inspired by this other answer.

However, hash functions are usually employed in applications where $n>m$. So my question is whether this is also the case for $n>m$.

The two definitions are not equivalent.  The second definition does not imply the first.  You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.


Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ I'm trying to find a CFG for the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
What I thought about unsuccessfully is the following:
$S \rightarrow SASBS \mid SBSAS \mid \epsilon$
$A \rightarrow a \mid aa \mid aaa $
$B \rightarrow b \mid bb \mid bbb $
Which has the following problems:
(1) It does not take into account words that do not have a's or b's
(2)
It is possible to add a greater number of a's or b's than the allowed distance, for example aaabaaab is a word generated by that CFG
I've been thinking about it for a long time and it seems like a dead end because it seems that making CFG's is more of an art than anything else, I would greatly appreciate any help

You can write your language as a union of simpler languages:
$$
\{ a^{i+2} b^i : i \geq 0 \} \cup
\{ a^{i+1} b^i : i \geq 0 \} \cup
\{ a^i b^i : i \geq 0 \} \cup
\{ a^i b^{i+1} : i \geq 0 \} \cup
\{ a^i b^{i+2} : i \geq 0 \}
$$


Are these problems NP-Complete? I got 2 decision problem that I need to answer if they are in P or they are NP complete:

  1.Just like subset sum:
  given the integers or natural numbers ${\displaystyle w_{1},\ldots ,w_{n}}$ does any subset of them sum to precisely ${\displaystyle W}$?

but now instead of $W$:

  does any subset of them sum to $W'$  such: $W-10 \leq W'\leq W+10$ ?

I think this problem is NP complete.

My idea was to create a reduction from subset sum to this problem:
I thought to add the all the number between -10 to 10 : {-10,-9,-8....,0,1,2,....10} to ${\displaystyle w_{1},\ldots ,w_{n}}$
and now i can find any $W'$.

  2.Just like 3-dimensional matching:
  Let X, Y, and Z be finite, disjoint sets, and let T be a subset of X × Y × Z. That is, T consists of triples (x, y, z) such that x ∈ X, y ∈ Y, and z ∈ Z. Now M ⊆ T is a 3-dimensional matching if the following holds: for any two distinct triples $(x_1, y_1, z_1) ∈ M$ and $(x_2, y_2, z_2) ∈ M,$ we have $x_1 ≠ x_2, y_1 ≠ y_2$, and $z_1 ≠ z_2$.

But now:

  each vertex can be in only 3 triples.Is there a $M' ⊆ M$ that is a perfect matching?

I think this problem is in P .to prove this I thought about (hopefully polynomial) algorithm:

a.take a random vertex and find all the matches that he's in .

b.If the vertex is in only 1 match,put this match in M' and delete it form M.
otherwise do nothing.
(and delete all the vertex in this match from the hypergraph and all the matching they are in)

repeat a and b 3 times.It should take $O(3|X||Y||Z||M|)$.

Is my answers right?

Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S_1, W_1 \rangle$ be an instance of Subset Sum. Define $S_2$ as the multiset obtained by multiplying each number in $S_1$ by $100$, and $W_2 = 100 W_1$. The instance for your problem is $\langle S_2, W_2 \rangle$.

If there is a set $C_1 \subseteq S_1$ such that $\sum_{x \in C_1} x  = W_1$, then let $W'$ be the sum of the elements in corresponding subset for $S_2$. We have $W' = \sum_{x \in C_1} 100x = 100 \cdot W_1 = W_2 \in \left[W_2-10, W_2+10\right]$.

If there is a set $C_2 \subseteq S_2$ such that the sum $W' = \sum_{x \in C_2} x$ of its elements satisfies $W_2-10 \le W' \le W_2+10$, then pick $y   = W' - W_2$, so that $W'  = W_2 + y$ and $y \in [-10, 10]$.
We must have $y=0$ since $W' = W_2 + y = y \pmod{100}$ and $W'$ must be a multiple of $100$. This shows that $W' = W_2$  and that the corresponding subset of $S_1$ has a sum of $\sum_{x \in C_2} \frac{x}{100} = \frac{W'}{100} = \frac{W_2}{100} = W_1$.

Your second problem is already known to be $\mathsf{NP}$-Complete even when when no vertex occurs in more than three triples. See problem SP1 in  "Garey & Johnson, Computer and intractability: a guide to the theory of NP-completeness".


Thompson's construction, The empty-expression Why this case exists in Thompson's construction algorithm?

Isn't just a special case of:

where the symbol a is replaced by ϵ?

It's not a special case since $a$ is a symbol of the alphabet whereas $\epsilon$ is a symbol representing the empty word. However, you could lump the two cases together if you wish.

It all boils down to your recursive definition of regular expression. Most definitions will have three "axioms": $a$ for $a \in \Sigma$, $\epsilon$, and $\emptyset$. This necessitates three different base cases in the construction.


Nim game tree minimax Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player alternatively thereafter does the same to some single stack when it is his turn to play. The game proceeds until each stack has either just one penny or two—at which point continuation becomes impossible. The player who first cannot play is the loser. Show, by drawing a game tree, whether any of the players can always win.

My question is why does 4-2-1 not go to 2-2-2-1 ?

According to the rules:

  player divides the original stack into two stacks that must be unequal.


Finding an element in array, whose index number and element value same Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

If the array had $A[i]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1.  The complexity is indeed $\theta(log_2n)$


Cover points with minimal number of spheres of fixed radius I have a set of k n-dimensional points:

P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn).

A distance D(Pa, Pb) is defined between any two points, which satisfy usual properties:

D(Pa, Pb) >= 0
D(Pa, Pb) = 0 <=> Pa = Pb
D(Pa, Pb) = D(Pb, Pa)
D(Pa, Pc) ≤ D(Pa, Pb) + D(Pb, Pc)

What is the algorithm to find areas in which these points aggregate?
More specifically, given a radius R find the smallest set β of n-dimensional "balls" B(C) such that every point lies inside at least one of the balls:

ⱯPa ƎB(C) ∈ β => D(Pa, C) ≤ R

There is definitely more than one solution (in most cases a ball could be moved a little so that it would still contain the points) and probably there is something else I am missing. But I need an algorithm that would provide at least one solution.

Example:

If
k = 5, n = 2, R = 2, D(Pa, Pb) = euclidean distance on a plane
P1(0,0), P2(1,1), P3(4.5, 4), P4(-4, 1), P5(4,4),

Then
B1(0.5, 0.5) (contains first two points), B2(-4,1) (contains only 4th point), B3(4,4) (contains 3rd and 5th points)

Construct a graph. Represent every point by a node and connect two nodes with an edge if the distance of the represented points is $\leq R$.

Then, a minimial clique cover of the graph tells you which points should belong to the same sphere, one per cluster; pick the center of each set as center for the sphere.

Unfortunately, Minimal Clique Cover is NP-hard so no efficient algorithm is known for it. There may be algorithms suitable for your application in the literature, though.

Does it get any better? I don't have a proof, but this feels like a clustering problem to me which tend to be NP-hard. You may want to try and apply the ideas of hierarchical clustering.


Classes of circle rims The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 otherwise. We want to find the VC dimension of $\mathcal{F}$

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\{(x_1,y_1),\dots,(x_3,y_3)\}$ that all have the label 1, with radius $r_1 = r_2 = 1$, and $r_3 = 0$, it is impossible to shatter them. Is my intuition correct?

In fact, the VC dimension is 3.

To show this, we need to show that there is a set of 3 points which is shattered, and that no set of 4 points is shattered.

All sets of 3 points behave the same, but for definiteness let us choose three points $x,y,z$ which form the corners of an equilateral triangle. By symmetry, there are only 4 cases to consider:

$\emptyset$: choose some arc which avoids all points.
$\{x,y,z\}$: choose the complement arc.
$\{x\}$: choose a small arc around $x$.
$\{y,z\}$: choose the complement arc.

This shows that the VC dimension is at least 3.

To show that the VC dimension is at most 3, let us consider some arbitrary set of points $x,y,z,w$, presented in clockwise order starting at an arbitrary point. An arc that contains both $x$ and $z$ must contain either $y$ or $w$, and in particular there is no arc that contains exactly $\{x,z\}$.


Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)? My book states that the language
$$L_1 = \{a^nb^n\mid n\geq 1\}$$
is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really imagine how this grammar should not be applicable or why it shouldn't be a valid type 3 grammar:
$$S \to aS \mid bS \mid b\,.$$

For my understanding this grammar produces the language in question and also fulfils the type 3 criteria.

$S\Rightarrow bS\Rightarrow baS\Rightarrow bab$.

However, $bab$ is not $a^nb^n$ for any $n$.

(Exercise.) Is the following grammar a grammar for $L_1$?

$S \to Sa \mid Sb \mid a$


Number of finite strings over a countably infinite alphabet If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?

It's countable.  The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $\bigcup_{\ell\geq 0}S_\ell$, which is a countable union of countable sets, which is countable.

Usually, you can only get an uncountable set from countable ones by taking the power set.


Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not i'm trying to figure out whether this Union $\left [  L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ is regular then its intersection with $L(a^*b^*)$ should be regular which is $K\cap L(a^*b^*)=L(a^*)\cup L(b^*)$ right ?

1 - Does this implies that the Union is also regular ?

2 - i know that $L=\{a^lb^mc^m|l,m\ge1\}$ is CFL, but is $L_1$ also CFL ?, which is basically  $L_1=L\cup \{\epsilon ,a,bc\}$

3 - is $K$ regular or not and how to prove it ?

Any Hints would be appreciated.

You are not starting with the right proof idea. It's this:

I want to show $L$ is not regular.
Assume towards a contradiction that $L$ is regular.
Since REG is closed against $f$, I conclude that $L' = f(L)$ is also regular.
But I already know that $L'$ is not regular (from elsewhere). Contradiction; $L$ can't be regular.

See here for complete examples.


Minimizing a multivariate polynomial over the hyper-cube is NP-Hard In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, \ldots, x_n)$ and $\alpha$, does $\min_{0 \leq x_i \leq 1} p(x_1, \ldots, x_n) \leq \alpha$?

My idea is to reduce it to MAX-SAT as follows. Suppose I am given the formula:

$(x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee \overline{x_3}) \wedge (\overline{x_1} \vee x_2 \vee \overline{x_3})$

Then I consider:

$p(y_1, y_2, y_3) = y_1 (1 - y_2) y_3 + (1 - y_1) (1 - y_3) + (1 - y_1) y_2 (1 - y_3)$

If $p$ reaches a minimum at a corner of $H$ then the assignment:
$$x_i = \textit{true} \ \text{if} \ y_i = 0 \ \text{and} \ x_i = \textit{false} \ \text{if} \ y_i = 1$$
is a solution for MAX-SAT value for the corresponding formula and since MAX-SAT is NP-Hard we are done. However, how do I proceed if $p$ reaches its minimum at an interior point? Or is it the case that it will always be a corner?

Hint: Modify your polynomial slightly so that (a) it is always negative, (b) its only zeroes are solutions to SAT.