Smallest DFA that accepts given strings and rejects other given strings Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus B$?

In other words, $A$ represents a set of positive examples.  Every string in $A$ needs to be accepted by the DFA.  $B$ represents a set of negative examples.  No string in $B$ should be accepted by the DFA.

Is there a way to solve this, perhaps using DFA minimization techniques?  I could imagine creating a DFA-like automaton that has three kinds of states: accept states, reject states, and "don't-care" states (any input that ends in a "don't-care" state can be either accepted or rejected).  But can we then find a way to minimize this to an ordinary DFA?

You could think of this as the problem of learning a DFA, given positive and negative examples.

This is inspired by  Is regex golf NP-Complete?, which asks a similar questions for regexps instead of DFAs.

There is a lot of literature on learning DFAs given positive and negative samples. If $A$ and $B$ are finite I don't see how the problem would ever be undecidable though. If $A \cap B = \emptyset$ then obviously the DFA that accepts only the strings in $A$ satisfies your requirement and one can simply enumerate all smaller DFAs. If $A \cap B \neq \emptyset$ then clearly no such DFA exists.

Finding the minimum DFA consistent with a given set of strings is NP-complete. This result appears as Theorem 1 in Angluin's paper On the complexity of minimum inference of regular sets. So clearly your problem is also NP-complete.

For lots of good links and discussion on learning regular languages check out the CSTheory blogpost On Learning Regular Languages.


Why is the counting variant of a hard decision problem not automatically hard? It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a problem for which decision is easy, but counting is hard.

But consider an arbitrary NP-complete problem (say 3-COL). Can we immediately say something about the hardness of its counting variant?

Really what I'm asking is: why do we need another proof to show a counting variant of a hard decision problem is also #P-hard? (Sometimes you see parsimonious reductions that preserve the number of solutions, and so on). I mean really, if the counting problem was easy, you could automatically solve the decision problem as well! So how could it not be hard? (OK, maybe it is hard, but I'm not sure for what definition of hard).

The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard".

A decision problem is hard if it's NP-complete under polynomial-time many-one reductions (a.k.a. Karp reductions, a.k.a. polynomial-time mapping reductions).
A counting problem is hard if it's #P-complete under polynomial-time Turing reductions (a.k.a. Cook reductions).

As such, if a decision problem is NP-complete, we know that the corresponding counting problem is NP-hard but that's not the definition of what a hard counting problem is.  Being #P-complete seems to be a much stronger statement than just being NP-hard – Toda has shown that #P-complete problems are hard for the entire polynomial hierarchy under randomized reductions so, as a complexity class, #P feels much closer to PSPACE than to NP.

Going in the opposite direction, it's clearly true that, if the counting problem is easy in the sense of being in FP, then the decision problem is in P. After all, if you can efficiently count, you can certainly tell if the answer is nonzero.  However, just because the counting version is "not hard" (i.e., not #P-complete) doesn't imply that it's "easy" (i.e., in FP).  Ladner's theorem extends to #P so, if FP$\,\neq\,$**#P** then there's an infinite hierarchy of distinct complexity classes between them so our "not-hard" counting problem could be complete for any one of those classes and, therefore, not be "easy" (in FP).

Having said that, I don't think we have any counterexamples to the conjecture that a decision problem being NP-complete means that the counting version is #P-complete.  So, it's not a theorem but it is empirically true.


VC dimension of finite unions of one-sided intervals What is the VC dimension of $k$ finite unions of one-sided intervals:

If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these intervals can shatter $4
$ points as below, assuming that $a_1>a_2>a_3>a_4$:

Point $p_1$ at interval $(-\infty, a_1]$
Point $p_2$ at interval $[a_1, a_2]$
Point $p_3$ at interval $[a_2,a_3]$
Point $p_4$ at interval $(-\infty, a_3]$

For $k$ finite unions I think answer is $k+1$, am I right?

Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval can shatter only 2 points.


What is the output of a 2-tag system? Considering a 2-tag system as defined by wikipedia, how do I identify the result  of the computation?

There are two types of Post tag systems: with halting symbols, and without.

A Post tag system with a halting symbol gives its output in the same way that a standard Turing machine does: on the tape. Whatever is written on the tape when it hits the halting symbol is its output.

A Post tag system without a halting symbol is a bit trickier. It only halts when the tape has too few symbols left to do another step of processing. So there's no way to give any output on the tape. Thus, its output is the sequence of intermediate states the system has been in in the process of producing the result.

The Wikipedia article you linked gives an example of this: a halting-symbol-less 2-tag system to compute the modified Collatz sequence.


Counting solutions of a particular type in HORN SAT I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same.

Suppose we have a HORN SAT -: $(x_1) \land (x_2 \implies x_1)$, then the solutions are $(1, 0)$ and $(1,1)$. For solutions of type #, I would like to eliminate $(1,1)$ as after negating $x_2$ we will still have a valid solution. In some sense $(1,1)$ is not a minimal solution. Do solutions of type # have a formal name? It seems natural that SAT solvers must strive to obtain solutions of type # and use those to generate other solutions.
Since the problem of HORN satisfiability is easy, are there efficient algorithms for counting HORN sat solutions? If so, could someone please point me to a good reference.

Finding the minimal solution can be done in polynomial time (in fact, linear time), using the standard algorithm.  There is always only a single minimal solution, and the standard algorithm for testing satisfiability of a HornSAT instance will also give you the minimal solution.

Counting the number of solutions is #P-complete and thus seems to be quite hard; see Is #HORNSAT polynomial?.


SQL, optimizing a select statement in relational algebra is it possible to rewrite the following sql statement
$\pi_{R.a,S.d} (\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}((R\times S)\times T))$
?

My problem is, i dont know if it is possible to split $\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}$ to $\sigma_{R.b = "d"} \land \sigma_{S.d \geq 100 \lor T.d \geq 200}$,because the rules say i can split $\sigma_{x \land y}$ to $\sigma_{x} \land \sigma_{y}$ but i am not allowed to split $\sigma_{x \lor y}$.

Relations R(a,b,c), S(b,d) with a,d are integers, b,c,d are strings.

Edit: It is important to use brackets to specify which bool statements are compared, also if you have a statement that uses $ \land and \lor $ you are not allowed to not write the brackets, that was my major mistake. correct formular
$\pi_{R.a,S.d} (\sigma_{(R.b = "d" \land S.d \geq 100) \lor T.d \geq 200}((R\times S)\times T))$

In this case we are not allowed to split the $\sigma$ statement because we are bound to the $\lor$.

We could split the $\sigma$ if the statement would be:

$\pi_{R.a,S.d} (\sigma_{R.b = "d" \land (S.d \geq 100 \lor T.d \geq 200)}((R\times S)\times T))$
to
$\pi_{R.a,S.d} (\sigma_{S.d \geq 100 \lor T.d \geq 200}((\sigma_{R.b = "d"}(R)\times S)\times T))$
Which would lead to a smaller kartesian product.
At the end:
What we are seeking is to bring the $\sigma$ as close to the leafs as possible to reduce our kartesian produkt

I suspect this is a homework question.

Edit: OK, you're trying to invent your own homework. Well done for trying. You might have bitten off too much.

We need first to sort out the headings of your relations. As per my comment above, Cartesian product must have no attributes in common between operands. I'll assume headings: R(a,b), S(c,d), T(e,f) -- that is, no b in common between R, S; no d in common between S, T. Then I don't need to put the dot-prefix on attribute names. Your question becomes:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100) \lor f \geq 200}((R\times S)\times T))$

(If you do want attributes in common, then instead of $\times$, use Natural Join $\bowtie$. And the whole point about Natural Join (a beautiful operation, at the heart of the Relational Model) is that it 'commons up' the attribute names. So you still don't need the dot-prefix.

And what it's trying to teach you is that the Boolean operators (AND /\, OR \/) within a Select expression (sigma) are equivalent to certain set operators over the relations.

Edit: OK you've shown one equivalent for $\land$, which is to push the $\sigma$ inside the $\times$. More usually, you'd use set intersection $\cap$.

Yes you are allowed to 'split' a selection that is a disjunction (your sigma x\/y). Think about what is the set-theoretic operator that's equivalent to disjunction.

Edit: The set-theoretic operator is union $\cup$. For both intersection and union, we need the headings of the operands to be the same -- that is, the full Cartesian product.

Also beware: what's the relative precedence of the disjunction vs the conjunction in that sigma expression?

Edit: OK, you've answered that. So the outermost operator is $\lor$. Let's rewrite that to $\cup$ between relation values:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100)}((R\times S)\times T) \cup \sigma_{(f \geq 200)}((R\times S)\times T))$

Now in the left operand of $\cup$ we have a $\sigma$ with a $\land$. We can push that inside, as you've already shown. Similarly in the right operand we can push the $\sigma$ inside:

$\pi_{a,d} ( ((\sigma_{(b = "d")}R\times \sigma_{(d \geq 100)}S)\times T) \cup ((R\times S)\times \sigma_{(f \geq 200)}T))$

But notice in the right operand of $\cup$, we still have bare $(R \times S)$. So the union is going to include every (a,b) pair from S, and every (c,d) pair from R. (I suggest you try that out with a few sample sets of attribute values for those relations.) Your outermost projection, just takes a from R and d from S. So all the business with the $\sigma$s and $\land$, $\lor$ is rather pointless. And relation T is superfluous.

The most reduced form of your formula is:

$\pi_{a,d}(R \times S)$

Or even:

$(\pi_{a}(R)) \times (\pi_{d}(S))$


Is there a way to measure the maximum random bits of the outputs of a generator? I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG.

Let $F_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus_{k = 1}^{|G(s)|} G(s)[k]$. Obviously, $F_{1}$ is not a PRG, since the last bit can be predicted. But if we remove the last bit, it is a pseudorandom string.

Let $F_{2} \colon s \mapsto G(s) \Vert G(s)$, $F_{2}$ cannot be PRG, too. but if only choose $|G(s)|$ bits properly, it can be pseudorandom.

So, if $F \colon \{0,1\}^l \to \{0,1\}^n$ is a polytime deterministic generator. Perhaps, $F$ is not a PRG, but $F$ may be closed to a PRG. Namely, there exists a compression algorithm $A \colon \{0,1\}^{n} \to \{0,1\}^m$, where $n \geq m > l$, such that $A \circ F$ is a PRG. Is it well-defined? Can we use something like $n - \min_{A} m$ to measure how is $F$ closed to PRGs? Is there a standard way to measure the maximum random bits of all the outputs of $F$?

You might be looking for computational min-entropy.


Boolean logic: why is the "opposite" of and equal to or? In boolean logic, why is the "opposite" of AND (&) equal to OR (|)?
For example, why would  !(A & B) be equal to (!A | !B)?
I understand that not A would simply be !A, but why does AND change to OR?

This is called DeMorgan's law, and let us think about it like this... By the way, let

$\land$ be &&
$\lor$ be ||
$\neg$ be !

You have a door, and the door has two locks. To open the door you therefore need keys $A$ and $B$, written $A \land B$.
Well, suppose that someone is not able to open the door. Well, then that must be because they don't have both keys, or, $\neg (A \land B)$.
But analysing this situation, if you do not have two keys, you either lack $A$ or you lack $B$, or in other words, you either $\neg A$ or you $\neg B$.
Hence, $\neg (A \land B) = \neg A \lor \neg B$.
You can go through the exercise with a door where you need 1 of 2 keys to open for the reverse case.


Matching girls with boys without mutual attraction (variant of maximum bipartite matching) Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like.

Does this problem have a name? Is it feasibly solvable? Sounds hard to me...

Ps. note that since the attraction is not neccessarily mutual the standard max-flow solution does not work.

I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp.

You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not increase you objective function (# of mutal attractions).

If you want to maximize the number of happy people, then you set the weights of the complete bipartite boys-girls graph as follows

mutual attraction = 2 happy people
one sided attraction = 1 happy people
otherwise = 0 happy people

You then can compute the maximum weighted bipartite matching.


Is Functional Complete means Turing Complete? I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates.

A Turing machine may halt or not in a particular input but a combinational(not sequential) logic circuit always gives an output in a particular input. You may not agree with my point on combinational circuit but a combinational circuit is just a deterministic system so I can evaluate step by step in a input until it gives an output, in other words, there is no loops in a combinational circuit, I think.

So, I want to know whether I can represent any computable function only by those three gates ?

Any way, thx!

A Turing machine defines a function over all of $\Sigma^*$, it is a finite object which describes the operation on infinitely many inputs.

A logical circuit however, is defined over a specific number of variables, so it has a finite domain. Using boolean circuits over $n$ variables we can implement the set of all functions from $\left\{0,1\right\}^n$ to $\left\{0,1\right\}$, and no more (so no Turing completeness in the simple interpretation).

This is why, when dealing with logical circuits, the notion of non uniform computation is introduced. By non uniform, we mean that the mechanisem for processing some input $x$ might depend on $|x|$. In the context of circuits, this means that instead of talking about one circuit, were talking about a circuit family $\left\{c_n\right\}_{n\in\mathbb{N}}$, where $c_n$ is a circuit with $n$ inputs.

We say that a circuit family $\mathcal{C}_n$ decides some language $L$ if $\forall x\in\Sigma^*: x\in L \iff c_{|x|}(x)=1$. Note that non uniform computation extends the classical uniform computation, i.e. using circuit families of arbitrary size we can decide undecidable (relative to Turing machines) languages. Actually, we can decide all languages. If you want to reduce this back to the Turing model, then you must require the existence of a computable function $f$ which, given $n$, generates the circuit $c_n$.


Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?
The best prime complexity I have found is $O(|V|^2)$, and the complexity of the Kruskal algorithm is $O(|E|\cdot \log(|E|))= O(|V|^2 \cdot \log(|V|))$.
Any ideas for how to improve the time complexity so that we get something more efficient than $|V|^2$?

Since it is a complete undirected graph, the number of edges are $\Theta(n^{2})$, where $n = |V|$. In order to find the MST, you must find the edge of minimum weight among all the given edges since it is always a part of the Minimum Spanning Tree. Since, the lower bound of finding the minimum among $N$ elements is $\Omega(N)$. Therefore, you can not do better than $\Omega(n^{2})$ if the graph is complete.


Prove that the language of squares is not regular using homomorphism If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular.

Assume that the language $L=\{yy:y \in \{0,1\}^*\}$ is given.
Can you provide a homomorphism for $L$ like $h$ that $h(L)$ is not regular?

Note : I don't want a simple homomorphism. I want a good homomorphism that $h(L)$ is obviously not regular. So there should be no need to use pumping lemma to prove that $h(L)$ is not regular. But you can use the pigeonhole principle.

As illustrated by other answer and comments there seems to be no easy way just using morphisms. Still it is a good observation that simple closure properties can be of help.
In your case I would suggest intersection with regular languages as a tool: $L\cap 0^*10^*1 = \{0^n10^n1 \mid n\ge 0\}$ whch some recognize immediately as non-regular.

Alternatively one could include morphisms, inverse morphisms and intersection with regular languages (or, equivalently, finite state transductions). With these regularity preserving operations $L$ can be transformed in to $ \{a^nb^n \mid n\ge 0\}$, mother of all non-regular examples.


Why doesn't relu cause back propegation to get stuck Say you have a neural net that is being trained using back propagation and you are using relu activation. Say the input to a node is a weighted sum of the previous layer with a bias term and say for a particular data point, this weighted sum plus bias is negative. Then relu returns 0. Notice the change in the loss as a function of the change in one of these weights or the bias is 0. Therefore the network won't improve the bias as the network does back propagation. Why is this not a problem?

Normally, any ReLU unit will return 0 for some samples and not for other samples (in particular, it'll probably return 0 for about half of the samples).  Because of how SGD works, it won't get stuck: the former samples will yield a contribution to the gradient of 0, but the latter samples will have a non-zero gradient, so the weights and bias will be updated for the latter samples.  So it's not a problem; the weights and bias still get updated for many of the samples.
That said, there can be cases where this problem can occur.  If the ReLU unit outputs 0 for all (or most) samples, then SGD won't update the weights, and learning for that neuron will get stuck.  This is sometimes called the "dying ReLU" problem.  See, e.g., https://datascience.stackexchange.com/q/5706/8560 and https://en.wikipedia.org/wiki/Rectifier_(neural_networks)#Potential_problems.   Typically we're able to avoid this problem by appropriate initialization of the weights and by suitable choice of learning rate for SGD, so it's usually not a big deal in practice if you choose those appropriately, but it can happen.


Can ropes (AVL trees) be interned? Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?

I recently implemented a rope data structure in Lua as an AVL tree.

However, I realized a since the ropes are not interned, they can't be used efficiently as keys in a dictionary. (Lua walks over all new strings made by concatenation or slicing in order to intern them, making these $\Theta(n)$ operations, but guarantees fast dictionary lookup by only comparing addresses)

Can AVL tree ropes (or another type of balanced tree) be interned in a similar fashion in better than $O(n)$ time? Can fast interning be proved impossible?

Below is what I have thought of so far. I haven't found any resources about interning non-string data structures.

Hashing: You can efficiently determine the hash value of a concatenation or a slice with extra bookkeeping for some hash schemes (like Java's). However, you can't guarantee there are no collisions in these hashes (and actually their slicability/concateability can make them very easy to attack).
Normalizing: There are many different shapes that AVL trees with identical contents can take on. I could try to pick one special form for each size and designate it as the "canonical" form. When new trees are made when concatenating or slicing, in addition to balancing the tree, we reshape it to its canonical form. Naively this should not be efficient, because the vast majority of forms for a given size are $O(n)$ edits away from any particular canonical form. However, maybe if all subtrees are given some particular form, canonicalizing can be made efficient.

I tried the obvious perfectly-balanced tree as the canonical shape, but I couldn't make an efficient way to concatenate these. Another version I considered was "as left leaning as possible" but this had the same result.

I'll present two candidate solutions.

Solution #1: Associative hashing

Yes.  You can associate a hash value with the contents of any binary tree data structure (including a rope).  The basic idea is that you augment each node of the tree to store a hash value.  The hash for a node is $H(h_1,\dots,h_k,x)$ where $h_1,\dots,h_k$ are the hashes on its $k$ children and where $x$ is the value stored in the node.  In this way, any time you update a node, you can update its hash (and all of its ancestors' hashes) in $O(\log n)$ time.  Since all operations take $O(\log n)$ time anyway, this doesn't increase the asymptotic time of the basic tree operations.  Now the hash value at the root of the tree summarizes the contents of the entire tree, so can be used as the index into a hash table.  Basically, you use that hash value instead of using the address of the object.

You don't need to worry about hash collisions.  With a good hash function, hash collisions are sufficiently rare to not be worth worrying about.  And if you're using a hashtable, you always have the possibility of hash collisions, so you need a good hash function in any case.

The big shortcoming of this approach is that it doesn't take care of normalization; the hash value reflects both the contents of the nodes as well as the structure of the tree, so if you have two trees with the same contents but with a different structure, they will end up with a different hash value.  However, you can fix that up by a clever choice of the hash function.  In particular, I suggest you use an associative hash function, which is a function $H$ and a binary operation $\cdot$ where $H(x) \cdot H(y) = H(x,y)$.  Now you can use $h_1 \cdot H(x) \cdot h_2$ as the hash value for a node, where $h_1,h_2$ are the hashes of its two children and $x$ is the value stored in this node.  In this way the hash value at the root will be equal to what you'd get if you concatenated all of the values at all of the nodes (in infix order), then hashed them.  So now the hash value of the tree depends only on the contents of the tree, not on its structure.

Where do you find an associative hash function?  They take some cleverness to construct, but one option is to let $H$ denote the $SL_2(\mathbb{F})$-based hash function in https://crypto.stackexchange.com/a/17936/351 and $\cdot$ represent matrix multiplication.

With this technique, my construction is now normalizing as well, and it should be efficient.

Solution #2: SeqHash

A possible alternative would be to use the SeqHash data structure from the following paper:

VerSum: Verifiable Computations Over Large Public Logs.  Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich.  CCS 2014.

This data structure lets you store a sequence of characters in a deterministic tree-based data structure.  In particular, it provides a hash of the data in the data structure that is normalizing (because the data structure is deterministic).  It also provides $O((\log n)^2)$ time insertion, deletion, concatenation, and lookup into the data structure.  It's not a rope, but it might be a possible alternative to a rope that meets your interning requirements.

Related: see also Canonical representation of finite maps on non-overlapping finite rational intervals.


What's the directory structure on disk that keeps the information of all files? I'm reading Operating System Concepts by Avi Silberschatz(9thE), in chapter 11 File-System Interface, when the author explains the concepts of file, he states that

  The information about all files is kept in the directory structure, which
  also resides on secondary storage. Typically, a directory entry consists of the
  file’s name and its unique identifier.

I think the directory structure that holds the information of all files is of critical importance， which the author does not extend in depth though. I don't even know the terminology for this concept of directory structure. It should be somewhere on the disk and well maintained. Could anyone clarify it for me? Any literature and links will be appreciated.

Thanks in advance!

Your intuition is mostly correct. I believe the description is not really sufficient. Directory entry should at least be able to allow the OS to be able to locate some parts the file on disk for I/O operations. File System is divided into some fixed size partitions of available space ranging from 1-16KB. For efficient implementations a file is not necessarily written in contiguous blocks therefore the challenge is mostly having an efficient way of determining which blocks belong to which file without giving up on too much space and being efficient at the same time. Similarly other meta information should also be kept such as user permissions, hard links and so forth.

Currently Unix inode system is an efficient implementation. An other example would be maintaining a FAT (File Allocation Table) which is less efficient. I believe reading about Inodes would be great place to start.


Calculi for a computability class Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the complete set of push down automata, with nothing more powerful.

First question: Can a language exist that expresses up to the power of finite state machines but nothing higher?

Next. Working at the power of Turing machines we have the lambda calculus which with a little bit of sugar is a nice programming language. In addition there are weaker forms of the lambda calculus that are not Turing complete such as the simply typed lambda calculus.

Second question: What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus.

Grammars can be restricted to only allow regular languages. This of course does not change the fact that context free grammars can represent regular languages.

Third question: Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? Such as those talked about in "https://en.wikipedia.org/wiki/Regular_grammar".

These questions are all directly related. Pardon how convoluted this is.

You are asking several questions. Let me answer them one by one, though not in the same order.

Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? You are misunderstanding the article. One does not check that a grammar is regular. Rather, we define a grammar as regular if it satisfies the constraints described in the article. Regular grammars indeed generate all (and only) regular languages, and it's not too hard to show this by interpreting them as NFAs (exercise).

As an aside, the following is undecidable: given a context-free grammar, check whether the language it generates is regular.

Can a language exist that expresses up to the power of finite state machines but nothing higher? Yes, for example the language of regular expression, the language of DFAs, the language of NFAs, the language of regular grammars, and so on.

What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus. This question is not really well defined, and it is very easy to cheat. A reasonably natural example is finite automata – if you add two stacks you get a model having the same power as a full-fledged Turing machine.


Find 8 numbers whose sum is closest to a defined value I have a file that has a number (a positive integer) on each row.

Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible.

So, supposing that I have a file that looks like this:

  345
  3
  2
  3453
  1234
  6
  7
  34
  12
  1111
  48
  413

If the given number is 526 I would like to get a solution like:  3+2+6+7+34+12+48+413 = 525. So those are the 8 numbers that best fit our condition.

Is there an efficient algorithm with a low complexity?

The file can have >1000 rows and the numbers won't be bigger than 10k.

Dynamic programming

One approach is to use dynamic programming.  If you have $n$ numbers ($n$ rows in the file), and each number is in the range $1..m$, then the obvious dynamic programming algorithm has running time about $8mn$.  For your parameter size, this might be adequate.

In particular, let $A[1..n]$ be an array of your $n$ numbers.  Define $T[x,i,j] = 1$ if there is a way to write $x$ as a sum of $j$ numbers from among $A[1..i]$, or 0 if not.  Now we have the relation

$$T[x,i,j] = T[x,i-1,j] \lor T[x-A[i],i-1,j-1]$$

(with the convention that $T[x,i,j]$ always evaluates to 0 if $x$ is negative).  Consequently, you can compute all of the $T[x,i,j]$ values iteratively.  There are $8mn$ values to compute, so this takes $8mn$ time.

Once you have filled in the $T$ table, now you can answer any query quickly.  Suppose you want to find the closest number to $q$ that can be written as a sum of 8 numbers.  Then you should scan $T[q,n,8]$, $T[q+1,n,8]$, $T[q-1,n,8]$, $T[q+2,n,8]$, $T[q-2,n,8]$, etc., until you find the first entry that is one.  This takes at most $m$ iterations.

In total, the running time is $O(mn)$, where the constant hidden by the big-O notation is small.  The space required is $O(mn)$ as well, but this can be reduced to $O(m)$ if you fill in the $T$ table in the right order and discard entries once they are no longer needed.

Two-way merge

There's an alternative algorithm that will probably be significantly faster for your specific problem.  The basic idea is to first find an algorithm that works for sums of 2 numbers, then apply that repeatedly.

Let $S$ be a set of numbers.  Define $S \bowtie S$ to be the set

$$S \bowtie S = \{s+t : s, t \in T\}.$$

In other words, $S \bowtie S$ is the set of all possible sums of two values from $S$.  In our case, we're going to represent $S$ as a sorted list of numbers.

It turns out you can compute $S \bowtie S$ from $S$, using a FFT-based convolution procedure.  Let $N$ be the smallest power of two that is larger than $2m$.  Define a $N$-vector $v$ whose $i$th coordinate is 1 if $i\in S$, or 0 otherwise.  Compute $v \otimes v$, the convolution of $v$ with itself.  It turns out that $v \otimes v$ is the $N$-vector for $S \bowtie S$, so you can recover $S \bowtie S$ from $v \otimes v$.  Also, you can compute the convolution $v \otimes v$ using a discrete FFT over the $N$th complex roots of unity: you take the FFT of $v$, square every entry, then take the inverse FFT.   The running time of the FFT is $O(N \lg N)$.  Since $N=O(m)$, it follows that the running time of this procedure is $O(m \lg m)$.

Now we repeat this recursively three times.  In other words, we let $S = $ the set of numbers in the original file, compute $T = S \bowtie S$ (the set of 2-way sums), compute $U = T \bowtie T$ (the set of 4-way sums), and then compute $V = U \bowtie U$ (the set of 8-way sums).  This gives us the set of all numbers that can be represented as a 8-way sum.

If you like, a more elegant way to compute the set of 8-way sums is as follows: let $N$ be the smallest power of two that is larger than $8m$, form a $N$-vector $v$ where $v_i=1$ if and only if $i$ is part of the original file, take the discrete FFT of $v$ (over $N$th complex roots of unity), raise each entry to the 8th power, then take the inverse FFT.  This gives you a $N$-vector that has a 1 in its $i$th coordinate if and only if $i$ is an attainable 8-way sum.

Finally, given a query $q$, we can quickly look it up in $V$ (using binary search, say) and find the nearest number to $q$ that's in $V$.

The total running time will be $O(m \lg m)$, and the total space will be $O(m)$.  For your parameter settings, this should be extremely fast, given that $m$ is no larger than 10,000.  However, the implementation complexity is much higher, since you need to implement a FFT, worry about round-off error and precision for complex numbers, and so on.


Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the relevant decision problem belongs in NP (section 2.5 on page 6). To do this, they describe an algorithm that nondeterministically solves the Cube in polynomial time. It seems to me that this is more effort than necessary.
In particular, the relevant decision problem is as follows: The Rubik's Cube problem has as input a permutation $t$ and a value $k$. The goal is to decide whether $t$ can be solved in $k$ or fewer moves. So rather than constructing a nondeterministic polynomial time solution algorithm, they could simply give a certificate that a "yes" decision is just a list of at most $k$ moves and verify that checking this is polynomial time.
So my questions are as follows. Are the two definitions below actually equivalent?

NP is the complexity class of decision problems that are solvable by a nondeterministic Turing machine in polynomial time.
NP is the complexity class of decision problems for which a solution can be confirmed in polynomial time (deterministically)?

And if they are equivalent, why would the authors of the linked paper choose the more difficult method (or am I wrong about this assumption)?

Note that I am posting this question on multiple StackExchange websites as I'm not sure where it's best fit. If it is inappropriate here, I'll happily delete it. Similarly, I'll link to a good solution on another site if it gets answered there.

The certificate you propose might not be polynomial in the size of the input.
The input size of the problem is $O(n^3 + \log k)$, while your certificate has size $\Omega(k \log n)$. This is not polynomial, e.g., for $k = 2^n$.
Your certificate would work if you set it, e.g., to an empty list whenever $k = \Omega(\frac{n^2}{\log n})$, and modify the verifier to just check whether the input configuration of the cube is solvable for any such value of $k$ (thus ignoring the certificate).


How to order the functions based on complexity $2^n$ vs $n^{\log n}$? How to order the functions $2^n$ vs $n^{\log n}$ based on their complexity?

I found this question in a programming website (InterviewBit). But the answer given there, $n^{\log n}, 2^n$, does not seem convincing.

The graph of the two functions also indicates that $n^{\log n}$ is more complex than $2^n$.

I also tried substituting a couple of large value for $n$ like $10^{10}$ or $10^{10000}$. They all seem to indicate that $n^{\log n}$ is more complex than $2^n$.

Is $n^{\log n}$ greater than $2^n$?
Assuming 1 is true, how to prove it without using graphs?

Firstly, your plot is wrong. See this:
https://www.wolframalpha.com/input/?i=plot%5B+y%3D2%5Ex,+y%3Dx%5Elog_2(x)%5D

Take the base 2 logarithm of them:
$\log_2 (2^n) = n$, $\log_2 (n^{\log n}) = \log n \cdot \log_2 (n)$.

As you can see, $n$ is larger than $\log n \cdot \log_2 (n)$; therefore $2^n = \omega(n^{\log n})$.

So, the answer to your first question is no. I also show you an easy proof sketch.


Why don't we encode church numerals like this? I think the following encoding also works.

ZERO := λf. λx. x
ONE  := λf. f
TWO  := λf. f f
THREE:= λf. f (f f)

Note: the original encoding is

ZERO := λf. λx. x
ONE  := λf. λx. f x
TWO  := λf. λx. f (f x)
THREE:= λf. λx. f (f (f x))

Why is the original one better?

I think what you really are asking for are criteria for judging correctness of coding. Once you have got these, you can answer your question on your own.

Correctness of coding of some structure always originates from the structure itself. The structure of natural numbers $\mathbb{N}$ is:

A constant $0$,
A unary operation $S$,
For each set $A$, a recursion operator $\mathsf{rec}_A : A \to (\mathbb{N} \to A \to A) \to \mathbb{N} \to A$, subject to equations:
$$\mathsf{rec}_A \; x \; f \; 0 = x$$
and
$$\mathsf{rec}_A \; x \; f \; (S n) = f \; n \; (\mathsf{rec}_A \; x \; f \; n).$$

So whatever your coding of natural numbers is, it has to have $0$, $S$ and $\mathsf{rec}$ (only one will do in the untyped $\lambda$-calculus as there are no types to worry about) such that the above equations are satisfied for all suitable $x$, $f$ and $n$.

You can ask yourself:

  Does your coding allow you write down $0$, $S$ and $\mathsf{rec}$ which satisfy the desired equations?

If it does, then it's a valid coding. There are many codings of natural numbers.


Finding the Kth largest element can be optimized to O(n) only if k is a constant? There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$.

The thing I don't understand is....  Those algorithms wouldn't work if $k$ is dependent on $N$.  Therefore $k$ must be a constant.

But if it's a constant why isn't it easiest to simply loop like bubble sort for $k$ times?  So you pushed the $k$ largest elements to the end of the array. No?    Complexity would be $O(nk)$ but $k$ is a const so it would be $O(n)$.

Why do we need crazy algorithms like median of medians and using quicksort if this alone works?

The $k$th largest element can be found in time $O(n)$ for all $k$ using a deterministic algorithm. See Wikipedia or many textbooks, such as Cormen et al., Introduction to Algorithms.

Given the $k$th largest element, you can find the $k$ largest elements in $O(n)$ using a simple scan. If all elements are distinct, you just output all elements which are at least as large as the $k$th largest. Without this assumption, you output all elements which are strictly larger than that element, and then enough copies of the $k$th largest one.


Finding cache block transfer time in a 3 level memory system Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it :

A computer system has an L1 cache, an L2 cache, and a main memory
unity connected as shown below. The block size in L1 cache is 4 words.
The block size in L2 cache is 16 words. The memory access times are 2
nanoseconds, 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache
and main memory unit respectively.

When there is a miss in L1 cache and a hit in L2 cache, a block is
transferred from L2 cache to L1 cache. What is the time taken for this
transfer?

(A) 2 nanoseconds
(B) 20 nanoseconds
(C) 22 nanoseconds
(D) 88 nanoseconds

When there is a miss in both L1 cache and L2 cache, first a block
is transferred from main memory to L2 cache, and then a block is
transferred from L2 cache to L1 cache. What is the total time taken
for these transfers?

(A) 222 nanoseconds (B) 888 nanoseconds
(C) 902 nanoseconds (D) 968 nanoseconds

First thing that came to my mind was, how to calculate the transfer time using the given access time. During a miss, a block of data is moved from main memory to cache. Then CPU will access it. So, wouldn't be access time > transfer time ?
Then I thought, lets assume access time = transfer time & do the calculation.
Now first question. The question already states there is a miss in L1, so I will not consider L1 access time. Since there is a miss in L1 & hit in L2, a entire block from L2 has to be moved to L1. L2 block size is 16 words, but data bus size is 4 words.
So we have to move 4 words * 4 times.
To transfer 4 word it takes 20 ns. To transfer 4 words, its 80ns. Isn't it the time transferred from L2 to L1 ? The question does not say anything about accessing L1 after moving the data. But 80ns is not in the option !
Similar case with second question also.
Time to move main memory to L2 = 4 words * 4 times = 4 * 200 = 800ns
Time to move L2 to L1 = 80ns [earlier calculation]
So total time taken is 880ns. Which is again not in the option.
Either I am doing a very big mistake or options are wrong or question isn't framed correctly. If I am doing anything wrong, please give me some hint & I will try to work on this exercise again.

I guess you got the access time wrong. Access time means time to locate a data on a memory. So, whoever accesses the memory (be it CPU or some other device) it will be the same.

Coming to first question here. A block is transferred from L2 to L1. And L1 block size being 4 words and data bandwidth being 4 bytes, it requires 1 L2 access (for read) and 1 L1 access (for store). So, time = 20+2 = 22 ns.

For the second question, L2 block size being 16 words and bandwidth between memory and L2 being 4 words, we require 4 memory access (for read) and 4 L2 access (for store). Now, we need to send the requested block to L1 which would require 1 more L2 access (for read) and 1 L1 access (for store). So, total time

= 4 * (200 + 20) +  (20 + 2)

= 880 + 22

= 902 ns


Comparison of two line segments along a ray I have a point $q$, a ray $L$ (halfline which is cast from $q$) and two non-intersecting (intersection is only possible at endpoints) line segments $s_1, s_2$. I want to efficiently compute which of the two line segments along the ray $L$ is visible ("comes first").

I found the following description of a possible solution:

Why are at most five orientation predicates sufficient? I tried it on a few examples but can't convince myself fully.

The best way to see this is to describe the algorithm more carefully:

Pick one of the segments, say $s_1$. First, we test the orientation of the points $a_2,b_2$ w.r.t. $s_1$. If both lie on the same side of $s_1$, we test the orientation of $q$ w.r.t. $s_1$. Then, we have two cases:

$q$ lies on the same side as $a_2,b_2$. This means $s_1$ is further away, as your figure shows.
$q$ lies on the other side as $a_2,b_2$. This means $s_2$ is further away, which can also be seen from the figure, with a little imagination.

If $a_2$ and $b_2$ do not lie on the same side w.r.t. $s_1$, note that, since $s_1$ doesn't intersect $s_2$, it follows that $a_1,b_1$ are on the same side w.r.t. $s_2$!

So, we now only need to test whether $q$ lies on the same side as $a_1$, w.r.t. $s_2$: If it does, $s_2$ is further. If it doesn't, $s_1$ is further.

So, we have exhausted all possibilities and determined which segment is further using only four orientation tests! (In the first case, we test $a_2,b_2,q$ w.r.t. $s_1$ and in the second $a_2,b_2$ w.r.t. $s_1$ and $q,a_1$ w.r.t. $s_2$)
So, we were able to improve upon the given $5$ in the description, by postponing the testing of $q$, such that $q$ only has to be compared to one segment and not $2$.

(Note that in the given configuration, if we assume $q$ isn't collinear with any of the segments, no points are on the linear extension of the segment, which means they are always on exactly one side.)


Variant of the knapsack problem and box stacking I'm facing a problem described as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h_i$, width $w_i$, depth $d_i$ and value $v_i$. You want to create a stack of boxes with a height limit $H$ and maximize the sum of the values, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each larger or equal than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. You are also allowed to use multiple instances of the same type of boxes.

I realized that it is a combination of the knapsack problem and the box stacking problem with small variations. I tried to solve it using the knapsack algorithm adding the box stacking restrictions, but I'm not getting the right results. Does anyone know a similar problem or could indicate me an algorithm? I have to implement it using dynamic programming.

This is a good dynamic programming exercise.  Here's a hint.

   Let $f(i)$ denote the maximum height that can be achieved if you have the $i$th box at the bottom.  Can you find a recursive relation to let you compute $f$ in a recursive fashion?

Think about that one.  If you get stuck, here's another hint:

   Oops, you'll probably discover that doesn't quite seem to work.  What additional information would we like to know about the box at the bottom, to enable you to find a recursive relation?  You might need to add an extra parameter to $f$, so it becomes $f(i,\text{something})$ -- what should you put as the "something"?

If you can answer those hints, you should be very close to finding a dynamic programming algorithm for the problem.


Is this a correct way to show that a problem is coNP-complete? Let $A$ be a problem that I want to show it is coNP-complete.
I know I could just show its  complement $\bar{A}$ is NP-complete
 or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show that $Q$ can be Karp-reduced to $A$.

But I wonder if the following steps are sufficient to show that A is coNP-complete?

   Show that $A$ is in $coNP$ by showing that its complement is in NP
   Choose one coNP-complete problem $Q$ and Cook-reduce it to $A$.

Does the coNP-complete class still be distinguishable (under the assumption $P\neq NP$) from the NP-complete class? since it seems that any coNP-complete problem is Turing-polynomially equivalent to any other NP-Complete problem.

No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness.

SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions.

Some questions on this site which are relevant are this one and that one, as well as a few others.


Alternative formulation of complexity class $BPP$ In Aurora and Barak, they give the following alternative definition of $BPP$:

What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to represent $poly(|x|)$ many coin toss results, but what is $R$? And why is this a subscript to $Pr$?

The subscript to $\Pr$ denotes which random variable the probability is over. In this case the probability is over $r$, which is samples uniformly at random (this is what is conveyed by $\in_R$) from $\{0,1\}^{p(n)}$. You can think of $r$ as representing a sequence of $p(n)$ many random coin tosses.


How to develop an $O(N)$ algorithm solve the 2-sum problem? Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.

Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.

  How to find an algorithm which is of order $O(N)$?

Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l])
     --left;
   else
     ++right;

It is obvious the algorithm takes $O(N)$ time.


Undecidability of emptiness of LBA How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?

Given a Turing machine $M$, we can construct an LBA $B$ which on input of length $n$ checks whether $M$ halts on the empty input within $n$ space. Therefore $L(B)$ is empty iff $M$ doesn't halt.


Why is the set for which a decision problem is true called a "language"? When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".

Why this strange terminology?

I believe a lot of this came out of linguistics research. People wanted to write down a formal description (grammar) of, e.g., the English language. By extension, the set of strings defined by any grammar is a language and, since unrestricted grammars are Turing-powerful, any computable set of strings is the language of some grammar.


Number of FLOPs (floating point operations) for exponentiation What is the number of floating point operations needed to perform exponentiation (power of)?

Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this? How does it work if $n$ isn't an integer?

Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...

There most certainly is a faster way to do this for non-negative integer powers. For example, $x^{14}=x^{8}x^{4}x^{2}$. It takes one multiplication to compute $x^2$, one more to compute $x^4$, one more to compute $x^8$, and two more to multiple those three numbers. This suggests a simple cost and a simple algorithm.

Convert the non-negative integer power to base 2.
Count the number of ones in this representation.
Add the power of two corresponding to the most significant non-zero bit in this representation.
Subtract one.

This yields a concise algorithm for any non-negative integer power. This algorithm is the most efficient, up to $x^{14}$. This algorithm suggests six multiplications are needed to compute $x^{15}$ since $x^{15}=x^8x^4x^2x$. However, 15 is 120 in base 3 and 30 in base 5, both of which imply that only five multiplications are needed to compute $x^{15}$: $x^{15}=(x^3)^4x^3$ from the base three representation, and $x^{15}=(x^5)^3$ from the base five representation. The minimum number of multiplications needed to compute $x^n$ where $n$ is a non-negative integer is in fact an NP-complete problem. But it's a whole lot less than $n-1$ multiplications.

  ... and how does it work if $n$ isn't an integer?

There are some tricks one can use if $n$ is a rational. But if $x$ is real and $n$ is a non-negative real, one must resort to approximation techniques. (For example, approximation techniques are used twice-fold in calculating $\exp(n\ln(x))$.)


Question about turing machines I've been reading a book about turing machines and it has a challenge about a building a Turing Machine that has as many 0s as many 1s but that can appear in any order.

I don't understand how do you set the reading to the beginning and then make a transition to the beginning.

But it deals with only 0s that shows up before 1s, how would i go about in the same instance if i find something like 100, or 100001?

The Turing machine uses the tape alphabet $\Gamma = \{0,1,x,\epsilon\}$.
Writing down all the transitions explicitly is tedious, so I'll just summarize the main steps:

Move right until you find a 1 or $\epsilon$.
If a 1 is found proceed as follows:

Replace the $1$ with $x$.
Move the head back to the initial position (move left until you find $\epsilon$, then move right once).
Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
Replace the 0 with $x$.
Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
Replace the 0 with $x$.
Move the head back to the initial position.
Repeat everything from the very first step.

Otherwise, if no 1 is found:

Move left until you find a $0$ or $\epsilon$. If no 0 is found, accept.
Reject.


Prove or disprove {wtw^R | |w| = |t|} is context free The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$

It looks like the language can be "pumped" by context free pumping lemma, but the pumping lemma doesn't prove the language is context free. So I'm thinking of building a PDA that recognizes it. But I'm stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $w$ and $t$, then compare the values after $t$ which is string $w^R$. But still hard for me to come up a whole construction at this moment, any suggestions?

Suppose $S_c$ is context free. Then let $p$ be the pumping length and choose $s = 0^{2p}0^p1^p0^{2p}$ in $S_c$ that satisfies the pumping lemma. Thus, we can break $s$ into $uvxyz$, with $|vxy| \leq p$ and $|vy| \geq 1$. And for all $i$, $uv^ixy^iz$ is a string in $S_c$.
We have three cases.

$vy$ contains all 0s and these 0s can be chosen from either the beginning $0^{2p}$ of $s$, middle $0^p1^p$ of $s$ or the last $0^{2p}$ of $s$. Now, by pumping lemma, since $uv^ixy^iz \in S_c$, for all $i$. We choose $i = 2$, so we have $s' = uv^2xy^2z = uvvxyyz$. Clearly, since $vy$ contains all 0s, and regardless which part of $s$ are chosen from, this string is the form of $wtw^R$ such that $|w|$ = $|t|$ = $w'$ with either $w$ is all 0's and $w'$ is not all 0s or vice verse. This implies that $w' \neq w^R$ or $w' \neq w$.

$vy$ doesn't contain any 0s in last $0^{2p}$ of $s$ (We choose in the last part of $s$, but it's essentially the same by choosing first or middle part of $s$). Similarly, either the length of $uv^2xy^2z$ is not multiple of 3 (since pumping will increase the number of 1's), or this string is the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ consists all 0s but $w'$ contains some 1s. Thus $w' \neq w^R$.

$vy$ contains some 0s and some 1s in last $0^{2p}$ of $s$. From pumping lemma, since $vxy \leq q$, $vxy$ must be sub-string of $0^p1^p$. Then, by pumping the string $s' = uv^ixy^iz$ for all $i$, the length is string is not multiple of 3 since pumping increases number of 0s or 1s, or the string is in the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ is all 0s but $w'$ is not all 0s.

Thus, we can conclude that all three cases above reach contradiction and hence $S_c$ is not context free.


Asymptotics of a logarithmic series Given that,

$T(n) = \sum_{i=2}^{n} \log_i n$

I need to find the asymptotic boundary of $T(n)$.

Answer given is $\theta(n)$.
Please provide explanation.

First, the change-of-base formula may be helpful here:
$$
\log_b(x) = \frac{\ln x}{\ln b}
$$
Also, with sums I always find it helps to write out the sum explicitly, so let's do that:
$$
T(n) = \sum_{i=2}^{n} \log_i n
= \log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_n(n)
$$

Now if you want to show this is $\theta(n)$, there are two things: you should show it is lower bounded by $cn$, and it is upper bounded by $Cn$, for some constants $c$ and $C$.

For the lower bound, use the fact that each term is greater than or equal to $1$.
For the upper bound, I suggest dividing the sum into two parts: from $i = 2$ to $i = \sqrt{n}$, and $i = \sqrt{n}$ to $n$. So the first part is
$$
\left(\log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_{\lfloor\sqrt{n}\rfloor}(n)\right).
$$
Here we have $\sqrt{n}$ terms, each which is at most $\log_2(n)$. The second part is
$$
\left( \log_{\lceil \sqrt{n} \rceil}(n) + \cdots + \log_n(n) \right).
$$
Here we have at most $n$ terms, but you can show (using the change of base formula above) that each term is at most $2$.

Now adding up the two parts, you should get an upper bound of
$$
\sqrt{n} \log_2(n) + 2n,
$$
so the final step is to show this is $O(n)$.


Concurrency: Is it order-independability or interruptibility of tasks? After researching concurrency I am unable to discern if it is either of these specifically or it encapsulates both?

I was also wondering if someone could provide some programming applications/real world examples I am struggling to grasp the concepts entirely and it feels like every where I look people have different understandings.

Just two re-define the two concepts I believe it to be:

Order independent: There is 3 Tasks A, B and C they need to be completed for the application to finalize, and are able to be completed in any order.
Interruptible: Tasks are able to be halted mid processing in order to complete part of one of the other tasks.

Point 2 I am most uncertain about how is this advantageous for a serial application? I am guessing it would be to do with user input/bypassing locks or waits caused by requiring further information so other tasks can be completed.

NOTE: I am trying to apply these in a context outside of parallelism.

Concurrency is working with tasks that may run simultaneously.  In my experience, when this term is used, the main focus is on correctness: making sure a system works as intended.

One way of doing that is to impose additional constraints on the system and ensure that they are always met.  Order independence and interruptability are examples of two such constraints.  You may want them to hold for your concurrent system.   But they are not required properties of concurrent systems in general: for many concurrent systems, they do not hold and do not need to hold.

For instance, in MySQL, you can configure to what extent you want your transactions to be isolated, with full serializability (order independence) as the highest level.


Determining an appropriate number of buckets for a hash function I would like to select an appropriate number of buckets in my hash table for this scenario:

A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed by the 2-character initials of the customer's name, transformed into integers using the mapping: A=01, B=02,..., Z=26. It is expected that on average no more than 8 comparisons is made every time a search is requested.

How would you select an appropriate number of buckets for a division hash function, and a multiplication hash function, based on this scenario?

The number of buckets in a hash structure will almost always be on the order of the number of items in the hash structure.

The phrase "on the order of" is intentionally imprecise. That means you could have twice as many buckets as items. Or two times as many items as buckets. But the two values (bucket count and item count) are generally correlated in a linear (not exponential) manner, within a factor of 10.

If the hash function is fairly good, and the number of buckets is prime, then anywhere up to one item per one bucket will result in a median search depth of one and an average search depth just over one. Generally, because the relative cost of a bucket is small, it makes sense to maintain a ratio of buckets to items that is greater than 1, but only minimally so.

Your description of your solution is confusing, because you have 10,000 records identified by initials, but only 676 combinations of initials (26 x 26). It is likely that you are layering complexity onto complexity in a vain attempt to save clock cycles and RAM, both of which you are likely to waste as a result of the inherent complexity of your solution. A smart guy named Donald Knuth once said: "Premature optimization is the root of all evil (or at least most of it) in programming." I'm almost certain you are well down that path already, and I suggest that you back out of that choice.


How to find the element of the Digit Sum sequence efficiently? Just out of interest I tried to solve a problem from "Recent" category of Project Euler (  Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as follows ( in the original question sequence has two ones in beginning , but it does not change the sequence ) :

  The Digit Sum sequence is 1,2,4,8,16,23,28,38,49.... where the $n^{th}$ term of sequence is sum of digits preceding it in the sequence. Find the $10^{15}th$ term of the sequence.

The naive solution can't be implemented because it takes a lot of time. I tried to reduce the problem to a case of matrix exponentiation ( that would takes $O(log ( 10^{15}))$ amount of time ) but could not come up with such a recurrence fitting the linear criteria as recurrence for this sequence is quite peculiar. It can be seen that the sequence is governed by the recurrence :

$$ a_n = a_{n-1} + d( a_{n-1} ) ..... (1 )$$

where $a_n$ is $n^{th}$ term of the sequence and $d$ is a function which when given a natural number as input returns sum of digits of the number ( eg. $\;d(786)=21$ ). My second approach was to try to find some pattern in the sequence. It can be seen that the first few terms of the sequence can be written as

   a_1 = 1
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

From the pattern above it becomes that $n^{th}$ term of the sequence can be  generated by the following method :

Write $2^{n-1}$ $1$'s with addition symbol between them.
Leaving  the first $1$, then apply the function $d$  on the next $2^{0}$ terms then on next $2^{1}$ terms, then on next $2^{2}$ terms and so on.
Then  apply the above method recursively on arguments of each $d$ function applied.

for example if n=3 we perform the following manipulations:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

By dynamic programming I can generate the $n^{th}$ term using the above method in time $O(log ( 2^{10^{15}} ) )$, which again is no better than the naive solution.

EDIT 1
Another thing that can be observed is that $d(a_n) = d(2^{n-1})$. For example $d(a_6)=d(23)=d(32)=5$. But I am unable to make use of this point. I again tried to find a linear recurrence relation ( for matrix exponentiation ) , but I am unable to find it.

EDIT 2

Following is the graph when the sequence is plotted for smaller range ( first $10^6$ terms of the sequence  are plotted ).

PS: I know it is not advisable to ask solutions from Project Euler. But I just want a new direction or a hint, as I have been moving in circles for past few days. If that is also unacceptable I can remove the question if suggested.

Since you asked for " a new direction or a hint " and I don't know the answer, I'll leave this here, I hope it's helpful.
some ideas:

It makes sense there would be a pattern mod 9, since

$\forall k > 1,k \in \mathbb{Z}\quad10^k \equiv 1 \mod 9$

Which you can prove by induction.

This means that all numbers are congruent to the sum of their digits mod 9.

Further,
$a_n = d(a_n) \mod 9 \implies $
$$a_{n} = a_{n-1} + d(a_{n-1}) = 2d(a_{n-1}) \mod 9$$

If we keep expanding this recurrence we get

$a_{n} = 2^n \mod 9$

Which explains the pattern mod 9.

It also gets us $a_n = 9k + 2^n$. Every iteration we get a gap that is divisible by 9. How wide are those gaps?

Here's some less than general code:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i

a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

The plot (for the first 100) looks exponential, but I don't think it's perfect.

Here's the output of

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

The last thing I have is that it seems if you sum the digits of a number, and then sum the digits of the resulting number, and repeat this, you eventually get that number mod 9.

Makes sense given the above fact about powers of 10 mod 9.

$$n \equiv d(n) \equiv d(d(n)) \equiv \cdots \mod 9$$

It gives an interesting sequence of numbers though.

Edit: Apparently this is called a "digital root".


Small hard 3-SAT instances I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4.

However, I would like to know if there is a similar result in the case for the number of clauses is small. For example, for < 20 clauses?

For example, if you had 8 clauses and you took a clause/variable ratio of 4, then you would have 2 variables, but this would be quite trivial to solve.

Do there exist heuristics for generating difficult small instances, or is it a simple matter of testing to see what works?

If the number of clauses is very small, then there's no clause/variable ratio that makes 3-SAT hard.  3-SAT with < 20 clauses is easy.  It's asymptotically easy (technically, the running time is $O(1)$) and easy in practice (using off-the-shelf SAT solvers).

One way to derive hard instances is based upon cryptography, where you convert the problem "find a value $x$ whose SHA256 hash starts with 128 zeros" to SAT, or "find a 128-bit AES key $k$ that encrypts a fixed 128-bit string to another fixed 128-bit string".  However, these are still going to have thousands of variables and tens of thousands of clauses, at minimum.


Can the height of a binary search tree be less than that of a red-black tree? This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne.

"Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than the height of the red-black BST, or prove that no such sequence is possible."

I think that in most cases, if not all, the height of a RBT is less than the height of a BST because the RBT ensures balance. However, is it possible for the height of a BST to be less than the height of a RBT? If so, how? Else, how to prove it?

The fact that a red-black tree is balanced just means that if it contains $n$ nodes then its depth is $O(\log n)$. There is no requirement for the depth to be optimal (i.e. $\lceil \log_2 (n+1) \rceil-1$), only for it to be optimal up to constants. Therefore it is definitely possible for a red-black tree to be deeper than some other binary search tree.

The advantage of balanced trees is that they are guaranteed to be balanced even after operations on the data structure. Since the running time of operations is usually linear in the depth, it is enough for the depth to be $O(\log n)$ rather than the optimal $\approx \log_2 n$.


Current value of flow in a network Confused about a question regarding flow networks.

Question is: Given the network below, what is the current value of flow in this network?

Does the current flow of a network refer to the maximum flow or something else?

The question is asking how many units are flowing from $s$ to $t$ under the current flow.

The maximum flow problem asks for the maximal number of units that can flow from $s$ to $t$ under any flow.


Need help finding/writing an algorithm to reassign items to groups with minimal changes I have some users in groups, like this (groups are letters, users are numbers):
{
  a: [1, 2, 3],
  b: [4],
  c: [5],
  d: [6],
  e: [7, 8, 9, 10]
}

I receive a new description of the grouping of these users like this:
[1, 2, 3, 4, 5, 6, 11],
[7, 8, 9, 10]

Now, I need to rearrange the users to minimize "changes", so in this case, they'd end up like this:
{
  a: [1, 2, 3, 4, 5, 6, 11],
  e: [7, 8, 9, 10]
}

A more nuanced example is this:
from:
{
  a: [1, 2, 3, 4, 5, 6]
  b: [7],
}

to:
[1, 2, 3, 7]
[4, 5, 6]

options:
{
  a: [1, 2, 3, 7],
  c: [4, 5, 6]
}
{
  a: [4, 5, 6]
  b: [1, 2, 3, 7], // THIS IS BEST
}

In this example, the second choice is best, because we move [1, 2, 3] to b rather than [4, 5, 6] to c and [7] to a.
I've been trying to come up with some heuristics, like starting with the largest invalidated group, then in that group, take the largest group that are still together after the change, and letting them keep their place.
That kind of thing seems to work, except in the second example, I can't think how to make it pick option 2 over option 1.
I'm wondering if this is a solved problem, if it can even be done without multiple passes and comparisons, and if I'm attacking this in a vaguely sensible way.
Any guidance would be greatly appreciated.

Every user either remains in their initial group, or moves to some other group for a cost of 1. So it suffices to look for a matching between new groups and old groups that maximises the number of users who don't need to move; subtracting the number of stationary people from the total number of people gives the number of people who need to move.
To do this, create an instance of the Assignment Problem, a.k.a. Maximum-weight Bipartite Matching, in which you have a vertex in A for every current group, a vertex in B for every new group, and an edge between every pair of vertices with weight equal to the number of users shared by the two groups (edges with weight 0 can be omitted). The goal is to find a matching -- a subset of edges, no two of which share an endpoint -- of maximum weight. To solve problem instances the size of your examples, trying all possibilities with brute force would be fine, but they can be solved more efficiently using the Hungarian Algorithm or linear programming, as described on the linked page.


The power of relativised proofs I've been trying to understand why, for instance, even though there are oracles $A$ for which $P^A \neq NP^A$, we still don't know if $P=NP$.

As I understand it, it's because it's easy to construct languages that can only be efficiently taken advantage of in a non-deterministic settings. For example, pick a single arbitrary string and call that your language; then all you need is non-determinism to try every string and you're okay in $NP$, yet still trapped into brute force in $P$.

My question is, what exactly separates this from a regular $NP$ problem? Why is this fundamentally different from an $NP$ problem that accepts only on some arbitrary predetermined certificate (or is it even possible to construct such a problem)?

Is it just the fact that $NP$ problems are required to have some sort of structure, whereas in the relativised case we're free to build our language arbitrarily? Or is there some deeper difference I'm missing?

The reason has little to do with the problems in $\mathbf{P}$ and $\mathbf{NP}$ themselves; it is due to the computation models they describe. Recall that, if $A$ and $B$ are complexity classes, $A^B$ only really makes sense if $A$ can be expressed as a class of machines which can be equipped with oracle access (to the problems in $B$). $A^B$ does not make sense if $A$ cannot be expressed in terms of machines (which can use oracles).

This means the class $A^B$ is not obtained simply by taking the class $A$ (as a set of languages) and performing some operation on them using $B$ as a parameter (as the rather deceivingly simple "exponentiation-looking" notation would lead you to believe). Rather, it is a class belonging to a machine model of its own accord, namely the machine model of $A$ given oracle access to problems in $B$. In fact, it is rather surprising that the whole thing is well-defined, that is, that taking any two machine models for $A$ and granting both of them oracle access to $B$ yields the same class $A^B$ (actually, this only works if you are so careful as to give them both oracle access in a proper way).

That we can obtain relativizing results from certain (i.e., relativizing) proofs is, thus, even more surprising. As you can see, these are the sort of proofs which still work even if you replace the machine models with any closely-related ones (i.e., their oracle versions). Since they generalize in this way, they actually turn out to be very useful in that we can derive corollaries from them (for the respective relativized classes). An example of such a proof would be the inclusion $\mathbf{BPP} \subseteq \Sigma_2$.

In a nutshell, $\textbf{P}^A \neq \textbf{NP}^A$ does not really tell us anything about the relation of $\textbf{P}$ to $\textbf{NP}$ since $\textbf{P}^A$ (resp., $\textbf{NP}^A$) can be a class which is completely unrelated to $\textbf{P}$ (resp., $\textbf{NP}$). For an extreme example, consider what happens when $A$ is the class of languages which are (efficiently) reducible to the halting problem; in this case $\mathbf{P}^A$ contains languages which are not even recursively enumerable. And there are even classes which have been shown to be equal, but which do not relativize in almost any way (e.g., $\mathbf{IP}$ and $\mathbf{PSPACE}$).


why is $\Pi_2$ smaller than $NP\cap coNP$ Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT}  \}$. What is the smallest class that $A$ is known to belong to?
Apparently, the answer is $\Pi_2$, although I thought it was $NP \cap coNP$, since if we have a non-deterministic machine $M_1$ that decides $SAT$ and another non-deterministic machine $M_2$ that decides $\overline {SAT}$, then we can define a machine $M_3$ that on input $(\phi_1, \phi_2)$, runs $M_1$ on $\phi_1$ and $M_2$ on $\phi_2$, and only accepts if both machines return True. If the input does belong to $A$, then for some set of nondeterministic choices, we know $M_3$ will accept. If the input doesn't belong to $A$, then either $M_1$ or $M_2$ always return False, and so $M_3$ always rejects.
My first question is whether my explanation correctly shows $A \in NP \cap coNP$. More importantly though, why is $\Pi_2$ smaller than $NP\cap coNP$!?

You seem to be using the following definition of $\mathsf{NP} \cap \mathsf{coNP}$: it consists of all languages of the form $L_1 \cap L_2$, where $L_1 \in \mathsf{NP}$ and $L_2 \in \mathsf{coNP}$. However, in reality $\mathsf{NP} \cap \mathsf{coNP}$ consists of all languages $L$ such that $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$.


Determining states in a DFA In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q_0$ and $F$. I am wondering how one understands thinking about the number of states to construct such a DFA.

Example:

$$\{w \in\{0,1\}^*\mid w\text{ contains at least two $0$s but does not contain }000\}\,.$$

In the solution, there are 7 states required, $(q_0, q_1, ..., q_7)$.

How should one typically begin understanding the sequence in which they write their states to then cross $\Sigma$ and $Q$ to find the transitions?

Here is one way of thinking about it. You are receiving a sequence of zeros and ones. At each moment the sequence might stop and you need to decide to accept or reject the resulting word. At each point in time, think about what properties of the sequence you need to remember to decide whether to accept a word or reject it. The number of these properties is a proxy for the number of states. The properties also suggest descriptive names of states.

For this problem, you need to know if you have seen exactly one zero, at least two zeros, and if you have seen three consecutive zeros. In case you have seen exactly one zero, you need to know if it is the last character (this gives 2 states). In case you have seen at least two zeros you need to remember the last two characters of the string (this gives 4 states, in principle, but in this case two can be combined for a total of 3). You need to remember if you have seen 3 consecutive zeros (1 more state). You also need a start state for a total of 1 (start) + 2 + 3 + 1 = 7 states.

So you can describe a state by a tuple (a,b), where a is 1 if you've seen exactly one zero so far, and 2 if you have seen at least two zeros, and b indicates the last bits you've seen. You can have the following states:

(0,*) - haven't seen any zeros yet, aka start state

(1,0) - have seen one zero and it is the last character of the string

(1,1) - have seen one zero, but it was some time before, it is no longer the last character

(2,00) - have seen at least 2 zeros, and the last two characters are zeros - DANGER - one more zero and I need to reject

(2,10) - have seen at least 2 zeros, and the last two characters are 10 - we are relatively safe, because we need to see 2 zeros before we decide to reject

(2,*1) - have seen at least 2 zeros, and the very last character is 1 - we are quite safe, we'll have to see 3 zeros before we decide to reject.

All the above states are assuming you have not seen three consecutive zeros. Of course, once you decide to reject due to three consecutive zeros, you always reject - this gives one more state.


Time complexity dependent on magnitude of input I'm trying to analyze an algorithm that looks like this:

def foo(L):
    for n in L:
        for x in range(n):
            ...

What would be its time complexity? First I thought $O(n)$, where $n$ is the number of elements in $L$, but that seems a little optimistic given that numbers can become very large. Then I thought $O(n^2)$ but that seem quite arbitrary too. $O(nm)$ where $m$ is the maximum value in $L$ perhaps?

Your result of seems correct, assuming none of the omitted operations modify the values of the variables n, L or x.

For a fixed value $k$ of n, the inner loop (for x in range(n):) loops over the set (or list; it is irrelevant for the analysis) $\{ 0, \dots, k - 1\}$, which contains $k$ elements. The outer loop (for n in L:) simply loops over each element of $L$ for a total of $|L|$ iterations, $|L|$ being the length of $L$. Thus, assuming the omitted operations are executed in $O(1)$ time, we obtain a time complexity of $O(m|L|)$ (as you propounded), where $m$ is the maximum value in $L$.

Incidentally, if you know the average value for the elements of $L$ you could also use the above reasoning to derive the average time complexity as well. (Just plug in the average value for $k$.)

As pointed out by @Raphael in the comments, of course, there is plenty of room for improvements if more assumptions are made about the contents of $L$.


How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length If I have the following system, I am wondering how to calculate the number of valid strings it contains.

The system is something like this, which can have arbitrary variations.

Only consists of an alphabet $\Sigma$.
It can't spell any words in a blacklist word list $\rho$.
It can't have more than $n$ characters of the same type in a row.
Every word $\omega$ it generates is no more than $m$ in length.

So for example, we might have this system:

$\Sigma = (a, b, c, d, e, f, g, h)$
$l = \texttt{len}(\Sigma)$
$\rho = (\texttt{bed},\texttt{fad},\texttt{dad},\texttt{bead},\texttt{deed},\texttt{fade})$
$n = 3$ (so can't match /aaaa|bbbb|cccc|dddd|eeee|ffff|gggg|hhhh/)
$m = 20$

Say we have a random number generator, which uses a radix algorithm to convert it into a string using the characters in the alphabet $\Sigma$. The thing is, this random number generator might generate strings like the following, which we just have to drop and forget, then try generating another one until we get one that matches the constraints. Don't know of a better way to do that, but that's beside the point. So it might generate these ones, which are invalid.

afbcdeabeadbeaaaadaf
[bead and aaaa]
bedddddagheadfffeeee
[bed and dddd]

So the question is, how do I calculate how many strings are invalid? I know how to calculate the possible strings given the constraints, that is simply:

$$z = l^m = 8^{20}$$

I don't know how to calculate the number of strings that are invalid though, in a general way (so I can change the value of $m$, $n$, $\Sigma$, or $\rho$). Wondering how to formulate this problem mathematically or algorithmically so that I can figure out that "there are x number of invalid strings", and so I can calculate:

$$y = z - x$$

to get the total amount of possible strings given the constraints.

The language of valid strings is regular.  Build a DFA to recognize the language, then use standard techniques to count the number of words accepted by the DFA (see Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038).

How do you build a DFA to recognize the language?  Via a product construction.  Let $L_a$ denote the set of all words that don't have $n+1$ $a$'s in a row, and let $L_\rho$ denote the set of all words that aren't in the blacklist.  Then your language is $\Sigma^{\le m} \cap L_\rho \cap L_a \cap L_b \cap \cdots$.  You can easily build DFAs for each of the individual languages, and then use the product construction to build a DFA for their intersection.

Warning: the size of the DFA can potentially blow up exponentially in $|\Sigma|$.  However, this will remain polynomial in $n$, $m$, and $|\rho|$.


How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

I have tried to reduce this problem to another undecidable one such as whether two context-free grammars accept the same language. However, I'm not sure how to use it as a subroutine.

Here is my approach: I'll show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is known to be not decidable.

Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ you can build a sequence (incl. repetition) such that the concatenated $x_i$s and the concatenated $y_i$s of this sequence form the same word. Notice that the alphabet has to have at least 2 characters.

So, let $P$ be an instance of the PCP.
Consider the following context-free grammar, where we've introduced a new terminal symbol $t_i$ for the $i$-th element in $P$. The grammar has the following rules:
$$
\begin{align}
S& \to X \; ! \;Y \\
X& \to x_1 X' t_1 \mid x_2 X' t_2 \mid  \cdots  x_n X' t_n \\
X'& \to x_1 X' t_1 \mid x_2 X' t_2 \mid  \cdots  x_n X' t_n \mid \varepsilon\\
Y& \to y_1 Y t_1 \mid y_2 Y t_2 \mid  \cdots  y_n Y t_n \mid \varepsilon \\
\end{align}
$$
(The variable $X'$ is only there to rule out $S\Rightarrow !$).

Of course, given any grammar, we can find a corresponding PDA that accepts the same language as the grammar.  So, construct the corresponding PDA, and then use the hypothetical algorithm for your problem to determine whether this PDA accepts any word of the form $u!v$ (i.e., whether one can derive any word of the form $u!v$ from this grammar).  I will show how to use this information to solve the PCP instance $P$.

Assume now that $u!v$ is a word in this grammar.
The word $u$ has two parts, the suffix, consisting of the $t_i$ terminals, and the remainder called prefix.  The same is true of $v$.
We have $u=v$ if and only if their prefixes and suffixes coincide. The suffixes coincide only if we have used the same sequence of tuples from $P$ to built the words $u$ and $v$. The prefixes of $u$ and $v$ coincide if the concatenation of the $x_i$s and $y_i$s (based on the reversed tuple-sequence given by the $t_i$s) is the same. Hence $u=v$ if and only if there is a solution for the PCP instance $P$.

Similarly, if there is a solution for the PCP instance $P$, then from the solution it is easy to construct a word of the form $u!v$ that is derivable from this grammar.

It follows that the PCP instance $P$ has a solution if and only if this grammar contains a word of the form $u!v$.  If there was an algorithm to decide your problem, we could use it to solve PCP.  But of course PCP is known to be undecidable, so your problem is undecidable, too.


algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence For e.g if the array is 2,2,3,3,5 and k=3
there are total 18 subequences
1 subequence of length 0(i.e empty subsequence)
5 subsequences of length 1

8 subsequences with length 2

4 subsequences with length 3

how to proceed?

You can solve this using dynamic programming. Let me show instead the solution using generating functions, which can also be implemented using dynamic programming.

Suppose that there are $m$ distinct values in the array, appearing $n_1,\ldots,n_m$ times. The generating function
$$ \prod_{i=1}^m (1+n_ix) $$
counts the number of subsequences with distinct values of size $k$, in the sense that this is the coefficient of $x^k$. For example, in your case $m = 3$ and $n_1=n_2=2,n_3=1$. Therefore the generating function is
$$
(1+2x)^2(1+x) =
(1+4x+4x^2)(1+x) =
1+5x+8x^2+4x^3.
$$


Any notions of operations in basic postulates of lambda calculus I am learning Lambda Calculus from the book by Hindley and Seldin . They start the formal postulation of lambda calculus as follow :

(a) all variables and atomic constants are λ-terms (called atoms);

(b) if M and N are any λ-terms, then (MN) is a λ-term (called an application);

(c) if M is any λ-term and x is any variable, then (λx.M) is aλ-term (called an abstraction).

In the second postulate $MN$ has been termed as a $\lambda$ term . How to define $MN$ , what does it mean ? Is it an operation?
Is there any scope of defining operations in lambda calculus which are associative and/or distributive  ?

You can think of application $MN$ as an algebraic operation, where the operator has been elided for convenience. Instead of $MN$ some people write $M @ N$, or even
$$
apply(M, N)
$$
So $apply(\cdot, \cdot)$  is a binary operation, and, as @chi points out,
 $apply(\cdot, \cdot)$ is is neither associative nor commutative. The precise nature of what $apply(\cdot, \cdot)$  does depends on exactly what $\lambda$-calculus you have in mind.


Polynomially related encodings CLRS states that:

  For some set $I$ of problem instances, we say that two encodings $e_1$ and $e_2$ are polynomially related if there exist two polynomial-time computable functions $f_{12}$ and $f_{21}$ such that for any $i \in I$, we have $f_{12}(e_1(i)) = e_2(i)$ and  $f_{21}(e_2(i)) = e_1(i)$.

My understanding of the above statement says that, for example, if we have base 2 encoding of a problem, we can convert it to base 3 encoding of the problem in polynomial time and vice versa.

I wanted to confirm from the respected community if my understanding is correct, or am I having a flaw in my understanding?

Also, If I am correct, CLRS states one more thing: "unary encodings are expensive". I want to know, what do the authors mean by that? Do they mean to say that representing 8 by 11111111 is costlier than representing 8 by 1000?

Yes, it's correct that you can convert between base-2 and base-3 representation (in either direction) in polynomial time.  Thus, that would be a good example of two encodings that are polynomially related.

You can't convert from binary (base-2) to unary representation in polynomial time; it causes an exponential increase in the size of the instance.  That's probably what is meant by "expensive".


Can we obtain a state diagram of a single Turing machine When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different number of states - if so, how can Turing machine be described with the set of finite number of states, along with others? In other words, if we follow the formal definition of Turing machine, can we construct a state diagram of a Turing diagram, assuming infinite memory exists?

There are two possible meanings of state here:

One of the finite states in the finite control mechanism of the Turing machine.
The entire state of the Turing machine, including its internal state (the one from the previous definition), the locations of the heads, and the contents of the tapes.

If you are looking for a state diagram of the second type, then it's infinite. If you're looking for a state diagram of the first type, then it's finite.

Different programs seem to have different number of states – every program is finite (has finitely many states, under the first interpretation above), but there is no bound on its length: it can be as long as you want, as long as it's finite. The same is true for Turing machines.


Find shortest path for a volatile graph Let me define a volatile graph first:

It is an undirected graph in which the weight of each
edge varies every time we query it. That is, when we request the weight
w(e) of edge e, we obtain an approximate value ˆw(e) defined as follows:
wˆ(e) = w(e) + η, where η ∼ N (0, σ).
Here, N (0, σ) is a Gaussian distribution with mean zero and standard
deviation σ.

How to obtain a shortest path for such a graph. Let it be denoted as (G, u, v, p).
Find the correct shortest path between vertices u and v on a volatile graph G with confidence p. We can define p in any manner we want as long as it is consistent to the fact that as p grows, the probability that our algorithm returns the true shortest path should also grow

Here is a rough sketch of an iteratively improving algorithm that I believe should work pretty well while minimizing the number of queries we do. It can also immediately start finding paths and slowly improve the paths it finds as it goes.

The first step is to evaluate every edge (if you wish to improve initial accuracy, evaluate every edge $k$ times) and use Dijkstra's to find the shortest distance $d_v$ from every vertex $v$ to the target vertex. This forms our initial belief of the graph.

Our goal is to find an accurate $\mu_e$ average weight for each vertex, but we want to be most certain about our precision "near" what we believe to be the optimal path(s). We do this by repeatedly finding a path from the start vertex to the target, in a probabilistic fashion, by repeating the following procedure:

If we are currently at vertex $v$ we have a choice from some edges. We currently believe that each edge has weight $\mu_e$, and when we take that edge we would get to vertex $w$ with remaining (believed) distance $d_w$. We consider this a multi-armed bandit problem, where choosing edge $e$ going to vertex $w$ would have cost $\mu_e + d_w$, and we want to minimize cost. We use this to probabilistically choose an edge, we query its weight, we update $\mu_e$ and $d$ with this new weight and then move to $w$.

As we keep repeating the above process we will balance exploration of the graph with exploitation automatically due to the multi-armed bandit.


Prove this langage isn't regular using the pumping lemma How can I prove that this language isn't regular using the pumping lemma for regular language?

$$L = \{a^nb^m| n,m > 0, \gcd(n,m)=1\}$$

I've already checked this answer: Proof that a language involving $gcd$ is not context-free but don't understand this part.

"Let s' be $a^{(n+ik)}b^m \ with \ k \geq 1$. Then s' e L if $gcd(n + ik, m) =$ , however the modular equation $n+ik = 0(m)$ have a solution $i = nk^{(-1)(m)}$ ..."

I don't understand how he proved, $gcd(n+ik, m) \gt 1$, could someone explain me more clearly the answer please.

Thank you.

As you know, the Pumping Lemma for regular languages states that if $L$ is a regular language, then there is an integer $p$ such that is $s$ is any string in $L$ with length $|s|\ge p$ then we can write $s=xyz$ with

$|y|>0$,
$|xy|\le p$, and
$xy^iz\in L$ for all $i\ge 0$.

If we let $s=a^nb^m$ for distinct primes $n,m\ge p$ then certainly $s\in L$ since $\gcd(n,m)=1$. Now we know that in this case $y=a^k$ with $0<k\le p$ and so if we pump $y$ we'll have $xy^{i+1}z=a^{n+ik}b^m$. Now we'll try to get a contradiction by showing that there is some $i$ for which $\gcd(n+ik,m)\ne 1$. We can get this if we can find an $i$ such that $m$ divides $n+ik$, since then we'll have $\gcd(n+ik,m)=m$.

In other words, we want an $i$ such that $n+ik\equiv 0\pmod m$. In modular arithmetic land we'll then have the following chain of equivalences:

$$\begin{align}
n+ik &\equiv 0\pmod m\\
ik &\equiv -n\pmod m\\
i &\equiv -n(k^{-1})\pmod m
\end{align}$$
The last step follows from the fact that when the modulus is prime, any nonzero value has a multiplicative inverse.

Here's an example: Suppose $p=6$, then we could pick $n=11,m=7$ and pump the string $a^{11}b^7\in L$. If it happened that $k=4$ then we could use $i=-11\cdot 2$, where the $2$ came from the fact that $4\cdot 2\equiv 1\pmod 7$. In other words, we'd have

$$
i=-11\cdot 2\equiv -22\equiv -1\equiv 6\pmod 7
$$
and then the pumped string would be $a^{11+6\cdot 4}b^7=a^{35}b^7$ and this is clearly not in $L$, since $\gcd(35,7)=7\ne 1$
$$
$$


C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)? I'm working on the problem: Count smaller elements on right side using Set in C++ STL
The solution is to add each element to the set and then to count the elements on the left, the distance function is called.
This is the algo:
1. Traverse the array element from i=len-1 to 0 and insert every element in a set.
2. Find the first element that is lower than A[i] using lower_bound function.
3. Find the distance between above found element and the beginning of the set using distance function.
4. Store the distance in another array Lets say CountSmaller.
4. Print that array

I'm having a hard time to visualize or understand how can distance function be used with a set like structure since internally, the set data is stored as a self balanced tree (Red Black Tree). Whats the concept of distance for a self balancing tree and how does calling distance() give us the count of smaller elements on the right side?

The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes that the time needed to advance iterators is constant).
The C++ specification do not mandate any particular implementation as long as it conforms to the required complexity so your question cannot be answered without inspecting the particular implementation that you are using.
However, just to convey the intuition, here are two possible implementations that would conform to the requirements:

Given random access iterators $x$ and $y$, distance($x$, $y$) returns $y-x$.
For general iterators increment $x$ until it equals $y$. Return the number of increments performed.

The type std::set does not return a random access iterator, therefore std::distance can take linear time and the second implementation above can be used. Now your question reduces to "how can the standard library iterate over the elements of a std::set in sorted order?"
The answer to this question depends once again on the implementation as there is no particular data structure mandated by the standard to implement std::set.
Since you mention red-black trees, which are a special kind of BSTs, this can easily be done by noticing that the order of iteration coincides with the order in which the vertices of a BST are visited by an in-order visit.
Notice that the concept of distance completely abstracts from the data structure used to store the elements of the set. Instead it only refers to the positions in which two elements appear when using an iterator to access the collection's contents.
In the case of std::set the elements appear in sorted order. This also means that the distance between an iterator pointing to the beginning of the collection and an iterator pointing to an element $x$ is exactly the number of elements that are smaller than $x$.