Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.

Given that we do not know the starting position of a player on this grid.

Given that the player can move 1 step in any cardinal direction every turn.

Given that the player cannot visit tiles he has already visited.

Given that we are told every turn in which direction the player has moved.

What would be a computationally efficient algorithm to pinpoint the player's location in the least amount of turns?

One way that comes to mind that would give me good results but would probably be computationally intensive is to try to apply the player's path to every possible starting position. If we can traverse the path without hitting an island or going off the map, then the end tile is a valid possible position for the player. At first we would have a lot of possible positions for the player but eventually, after several turns, we'd end up with only one possible position.

I don't very much like that approach as it seems computationally heavy.

Instead, I've implemented a simple solution using a bounding box. At the beginning of the game, the player could be anywhere. But as soon as he moves, we can narrow the bounding box. For instance, if the player's first move is north, we now know that he can't be in the bottom row of the map. All that is needed is to keep track of the top left and bottom right coordinates of that box and update them every turn according to the enemy's movement until the box is eventually narrowed down to the player position.

I like this solution because it is simple and computationally light. The problem is that it doesn't take into account the islands and the players' previously visited cells. Therefore, only when the bounding box hits the grids' limits can we narrow it down. If the player starts in the middle of the map and tends to stay there, it can take a long time before narrowing down his position.

Is there a way to refine my solution (bounding box) in a way that would at least account for the islands and at best for the player's visited tiles as well? If not, what other algorithm could I use?

Don't be so quick to reject your approach!  Your approach is a great solution.  On a $15\times 15$ grid, you'll only have to try 225 different options.  Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds.

As Knuth supposedly said once, "premature optimization is the root of all evil". My advice: Try that solution, implement, and measure its performance, before you even consider anything else.


Showing that u#v with u a substring of v is not context-free I need to find whether this language is context-free or not:

{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}

I suspect that it's not, and am trying to approach it via Pumping Lemma, but then I noticed that: any examples like a^n#a^n will not work, cos we can always make vwx in the second a^n such that after pumping, u is still a substring of v; then I tried playing around with # like a#ab^(n-3), but get lost with the choice of v and x since it's possible for one of them to be empty string.

This is homework so just a hint will be okay for me.

Okay I got confused when developing my ideas, and a simple example using Pumping Lemma would be: $a^nb^n\#a^nb^n$. Consider this: clearly $v$ and $x$ cannot contain $\#$, otherwise when pumping more or less $\#$ appear and the new string is not in the language. Now suppose $vwx$ are in the left $a^nb^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.; then if $vwx$ are in the right $a^nb^n$, then $v^0x^0$ will make the R.H.S. shorter than the left. This gives us the only possibility that $v$ in the first $b^n$ and $x$ in the second $a^n$, and clearly no matter how you pump it the new string cannot be in the same language, and this solves the problem.


Could computer architecture be reworked to support switching from binary to ternary, for example? I was investigating why computers use binary instead of ternary and, from what I understand, found it's for precision. We want to avoid getting the wrong answer when computing math, and if we were to look at a bit at the wrong time in, for example, a base-10 system we might accidentally catch it switching states and accept the output before it's done switching states.

Please let me know if I've misunderstood this. I know there's a lot going on under the hood in computer hardware.

Assuming I understood correctly though, would it be feasible to redesign computers to be able to switch "languages" in some components in real-time in favour of speed/size instead of accuracy? It's well-known that 8 bits in base-10 can store 390,625 times more data than in binary, so there are obviously massive implications if possible.

To clarify: my question is about the feasibility of designing a computer which could switch between the two languages in real-time based on user-defined required output.

Edit: As clarified above, I am not asking about the benefits of binary over ternary. I am asking about the benefits of using them together, in real-time, and if that could even be possible. Thanks.

Current computers use electronic parts which can easily distinguish between two states, by stating that high voltage = 0 and low voltage = 1, or vice versa. The hardware that is needed to combine two inputs x and y and produce an output equal to NAND (x, y) is very, very simple and any other logic can be produced very easily from this.

Your task in proposing ternary computers: Suggest how with current electronic parts, three states can be represented. Then suggest what would be a primitive operation that combines two ternary inputs and produces an output; what that operation would be, and how you would implement it. Then suggest how you could for example add two integer numbers that are made of 40 trits (I think that's the name, I might be wrong).

Of course your suggestion must not represent a trit using two binary states, because using two binary states you could easily represent four values with the same effort, which would surely be more efficient. So you might represent 0 = low voltage, 1 = medium voltage, 2 = high voltage. Have fun doing that reliably. (One problem that you have is that using low and high only, you can change states with force and therefore quickly. If you needed to change a state from high to medium voltage, you'd have to be careful not to overshoot to low voltage, so this would likely be slower).

Now it seems you not only want to implement ternary arithmetic, but you want to switch the hardware on the fly between binary and ternary. That's not running before you can walk, that's running before you even figured out that crawling might be a possibility.


FPT algorithm for edge dominating set I have been attempting to learn parameterized complexity on my own, and decided to go through all of the FPT race problems, and defining easy FPT algorithms for them, using concepts such as bounded search tree. I am stuck on figuring out an FPT algorithm for edge dominating set, defined as follows:

EdgeDominatingSet

Instance: A graph $G=(V,E)$; a positive integer $k$.

Question: Is there a subset $D\subseteq E$ with $|D|\leq k$ such that for each $e\in E$, either $e\in D$ or $e$ shares an endpoint with an $e'\in D$.

Parameter: $k$

I'm not looking to define anything fancy, just a simple FPT result. Any help would be great!

I'm not sure there are any really simple solutions. One algorithm is due to Fernau, and uses an enumeration of all vertex covers of size $2k$; within each of these, a simple dynamic programming algorithm attempts to find a small edge dominating set. Another (earlier) approach, due to Prieto, uses kernelization.


Why are inversions useful in computer science? In the second chapter of Cormen's textbook on Algorithms, he lists a discrete mathematics exercise on so-called "inversions", defined as follows:

  Let $A[1 \ldots n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

Question: Is this a mathematical concept that is used frequently in computer science? Are there some widely known applications of inversions that other people here know of? (I checked the wikipedia page for the concept, but it didn't list any).

To analyse many algorithms, in particular for the all-important sorting problem, the characteristics of permutations are important measures. For instance, the number of inversions determines the number of data movements when running insertion sort.


Can every context free language written as a intersection of another context free language and a regular language? I'm preparing an Formal language exam, One question from previous year's final is:

Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure context-free grammar and a regular language R so that $L = P \cap R$.

My solution to this question is quite simple. Assume context-free language P is equal to context free language L, and let regular language R to be $\Sigma^*$, where $\Sigma$ is the alphabet set. $\Sigma^*$ is definitely a regular language. So the answer to this question is yes.

However, I do came up with a more difficult problem. What if I add a limitation $P \neq L?$ Will this statement still hold? I current have no idea about this.

The question in the title of your contribution "Can every context free language written as a intersection of another context free language and a regular language?" is the one you answer above, by taking $P=L$ and $R=\Sigma^*$.

However that is not the question you quote from your test: "If $L$ is a context free language, then there exists a language $P$ that is generated by a pure context-free grammar and a regular language $R$ so that $L=P\cap R$." This additionally requires $P$ to be pure context-free, that is, generated by a grammar that has no dictinction between terminals and nonterminals.

Let $G$ be a context-free grammar with alphabet $\Sigma$ (terminals and nonterminals) and terminal alphabet $\Delta$. As an ordinary context-free grammar the language of $G$ equals $L(G) = \{ w\in \Delta^* \mid S\Rightarrow^* w\}$. Interpreted as pure grammar it cannot "see" terminals and the language is $P(G) = \{ w\in \Sigma^* \mid S\Rightarrow^* w\}$. Or, $L(G) = P(G) \cap \Delta^*$, which gives the answer to your final exam.
The elements in $P(G)$ are usually called sentential forms.


What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$? What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

If an $L$-complete problem (under first-order projection, or $NC^0$-reduction) has $NC^1$ circuit, then we have $L=NC^1$.

The $NC^1$ circuit for an arbitrary language $\mathbb{L}\in L$ is obtained by first projecting (in case of first-order projection) or doing a constant-depth transformation (in case of $NC^0$-reduction) to obtain an instance of the $L$-complete problem. Then, plugin the $NC^1$ circuit for the complete problem to solve the original problem overall.


How to find greatest set intersection of at least a given cardinality? While dealing with a problem, I uncovered this subproblem:

Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$.

Output: A subset of $S$, $T = \{S_{t_{1}},...,S_{t_{p}}\}$ so that $\mid$ $S_{t_{1}}$ $\cap$ ... $\cap$ $S_{t_{p}}$$\mid$ $\geq k$ with $p=\mid T \mid$ maximized.

I.e. find the greatest number of sets in $S$ whose intersection preserves at least $k$ elements.

Is there any way of solving this problem in reasonable time, say polynomial in $r$ and $n$?

I tried to create an algorithm to solve the problem in reasonable time for large sets and $n$ and got nowhere. There's the obvious brute force algorithm that runs in $n2^r$ time. I also tried to construct a DP algorithm that used smaller subsets for optimal substructure, i.e. making use of $(A \cap B) \cap C = A \cap B \cap C$ and that if $\mid A \cap B \mid < k$, then it's not worth searching any further with $A\cap B$. However, I didn't get anywhere since the number of different subsets grows too quickly.

On the one hand, the problem feels kind of "set coverish" and thus I suspect it's hard. On the other, I'd imagine a problem this simple to be mentioned in some list of hard problems if it were intractable.

Here is how to reduce clique to your problem. Given a graph $G = (V,E)$ and a number $\ell$, for each vertex $x$ let
$$
S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \neq x\right\} \cup \{ \{x,y\} : \{x,y\} \in E \}.
$$
In words, $S_x$ contains all edges in the graph touching $x$, and all edges not touching $x$, whether or not they're in the graph.

One can then show that for every set of vertices $A$,
$$
\bigcap_{x \in A} S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \notin A\right\} \cup \{ \{x,y\} : x \in A \text{ and } \{x,y\} \in E \}.
$$
In words, the intersection of $S_x$ for $x \in A$ consists of all edges in the graph touching $A$, as well as all edges not touching $A$ (whether in the graph or not). The size of this intersection reaches its maximum $\binom{|V|-|A|}{2} + \binom{|A|}{2}$ if and only if $A$ is a clique in the graph.

Choosing $k = \binom{|V|-\ell}{2} + \binom{\ell}{2}$, the graph contains an $\ell$-clique if and only if there are $p=\ell$ sets whose intersection contains at least $k$ points. The value of $n$ for this instance is $n = \binom{|V|}{2}$.


Smallest real root of a polynomial in a range I'm trying to numerically find the smallest real root of a polynomial in a given range. My initial plan was to shift the polynomial so that the bottom of the range was 0, expand the resulting expressions to find the new coefficients, then use the Jenkins-Traub algorithm until it finds the first (smallest) root or increases out of the range. However, the Wiki page says that it only generally finds the roots in increasing order, so it sounds like that's not guaranteed. Is there a way to guarantee finding the first root? If not, what is the most efficient way to solve the problem?

Finding all the roots then sorting is possible, but is inefficient as the degree of the polynomial gets larger, and, I hope, unnecessary. The bisection method is another common algorithm, but consider the polynomial:
$-5x^2+5x-1$
with a range of (0,2), which would cause the angle bisection to fail. The best answer is one that guarantees success with the fastest time for a reasonable degree polynomial (less than say 10).

I would like to propose mix of Sturm algorithm (to split range into ranges to know how many roots are there) and then run Newton method, which converges very fast with good initial guess.

Of course for Sturm - only up to first root range found.

Housholder is very tempting, but please check the runtime first to tweak the degree (and there is chance that it will in fact be Newton after all, when degree is equal one).

The main idea behind that is local root finding methods are faster than global ones, but they might diverge to some other place, but you are interested in the first one, so providing good initial guess will put Newton method in the radius of convergence.

The things to add: there might be many roots in small distance, so the main idea was to "pick one" range and start finding it, your idea of finding the slope is very neat, and if you merge the slope finding with initial range picking it seems like boosted Newton for very small cost.
The idea is to also show Newton method which root you are after (otherwise it might go after surrounding one).

About binary search, if you want to apply it until there is one root - yes, indeed, but if the idea is to check more ranges - I would cut it for resources savings.


Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$? More informally, the restriction is that when the edge is given, we can only proceed in to that direction.

I can simply perform a DFS and return a leaf found. I think this would take $O(d)$ time, where $d$ is the diameter of $T$. However, I'd like to answer a query in $O(1)$ time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.

"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses $O(n+m)$ preprocessing time and answers the queries in $O(1)$ time.

Yes, I think you can do this in $O(1)$ time.  I outline a method below.  There's probably a simpler way to do it, but the following should suffice.

Preprocessing. I'll assume we can view your tree as a rooted tree, with some root.  In pre-processing, annotate each internal node $w$ with one example of a leaf that is a descendant of $w$.  This can be done in $O(n+m)$ pre-processing time, using a very simple top-down traversal (DFS).

Also, define $p^*(\cdot)$ recursively as follows: if $w$ has any siblings, then $p^*(w)=w$; otherwise, $p^*(w)=p^*(v)$ where $v$ is the parent of $w$; and $p^*(r)=r$, where $r$ is the root of $T$.  In English, $p^*(w)$ is defined to be the node obtained by starting at $w$ and continuing upwards until we reach a node that has two or more children (or the root).  In pre-processing, we'll compute the value of $p^*(w)$ for each node $w$ and store it associated with $w$.  This too can be computed in $O(n+m)$ time.

Answering a query. Now, here's how to answer the query return any leaf that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$:

Case 1: Suppose $u$ is a child of $v$.  Then, answering your query amounts to returning any leaf that is a descendant of $u$.  This can be done in $O(1)$ time using the annotation on $u$.
Case 2: Suppose $u$ is the parent of $v$, and $u$ has at least one other child.  Then, look at any other child of $u$, call it $w$.  Then, answering your query amounts to returning any leaf that is a descendant of $w$.  This can be done in $O(1)$ time using the annotation on $w$.
Case 3: Suppose $u$ is the parent of $v$, and $u$ has no other children.  Then let $u'=p^*(u)$ and let $w$ be any other child of $u'$ (not an ancestor of $v$).  Then, answering your query amounts to returning any leaf that is a descendant of $w$.  This can be done in $O(1)$ time using the annotation on $w$.

In all three cases, the answer to the query can be computed in $O(1)$ time.


Zero knowledge proof - case of graph 3-coloring (not understanding the concept) In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem.
The context:

both know the graph (the prover and the verifier)

the prover solves a 3-coloring of the graph

repeat:
*the prover randomly permutes the colors
*the verifier asks for the coloring of an edge
*if the colors are different the process continues, and the verifier is more convinced that the prover actually solved the 3-coloring, if not, the verifier knows that the prover did not solve the 3-coloring

My question is: why couldn't a false prover (someone that does not know how to solve for the coloring) just always provide 2 different random colors?

Your misunderstanding stems from stating a wrong protocol for ZK 3-color verification. In fact the protocol is a bit more complex:
The prover first "commits" to colors. This means that he cannot change its commitment afterwards, but at the same time, he does not reveal the colors themselves.
Then, once the verifier asks for an edge, the prover "opens" its commitment, revealing the colors of that edge alone.
Since its commitment is binding, the prover cannot change the colors after committing to them. So if the prover does not have a legal coloring, he must commit to some invalid coloring of at least one edge, and will be found with some small probability.
This is repeated, each time with a new permutation of the colors, and new commitments.


Why NFA is called Non-deterministic? I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple and epsilon transitions, they are defined which means that the machine is deterministic for those transitions. Which means it's deterministic.

"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times".

"Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times".

A non-deterministic finite automaton (NFA) can have multiple transitions out of a state.  This means there are multiple options for what it could do in that situation.  It is not forced to always choose the same one; on one input, it might choose the first transition, and on another input it might choose the same transition.

Here you can think of "situation" as "what state the NFA is in, together with what symbol is being read next from the input".  Even when both of those are the same, a NFA still might have multiple matching transitions that can be taken out of that state, and it can choose arbitrarily which one to take.  In contrast, a DFA only has one matching transition that can be taken in that situation, so it has no choice -- it will always follow the same transition whenever it is in that situation.


Introductory book on Logic and Computation Can you give me some suggestions about a good introductory (but comprehensive) bookabout Logic and Computation?

Some fuzzy topics that I have in mind are:

Presburger artihm., PA, ZF, ZFC, HOL
Set theory, Type theory
Modeling Computation (Turing machines) in different theories
Links with computational complexity (FMT, descriptive complexity)

My answer could be late for this question, but I hope it will be helpful for other people looking for similar information.

I had taken a course about Mathematical Logic at National University of Singapore, in which the lecturer used this textbook:

A Concise Introduction to Mathematical Logic, 3rd edition, by Wolfgang Rautenberg

Personally, I like both the textbook and the course a lot.

The textbook initially appears to be quite difficult to read. However, once getting familiar with it, it is much easier to follow since the system of notation is very clear, the content is self-contained and the approach is by starting from foundation, no vague assumption. For example, this book develops the natural deduction calculus and Hilbert calculus, or prove two incompleteness theorems of Kurt Gödel from scratch.


Ant Colony optimisation for finding subsets with ~0 sum I have a set A = [x1, x2...xn] where xi in R (real). I need to find all non intersecting subsets with subset sum ~0 (approximately equal to zero).

Since the set can have non zero real numbers, I have opted to use Ant Colony Optimisation for this problem. I have implemented this in python and the program tends to be a  bit slow (python dictionaries for the graph). It takes around 60 seconds for 100 ants for single iteration. The algorithm goes like this:

Create a graph with the whole list of real numbers (fully connected)
Initialise the graph edges with w0
Each vertex has an associated value
Initialise the position of ants at random nodes
Ants select next nodes based on edge weights
Once an ant completes tour - the sum of all vertex values > threshold 1 (1000000) or < threshold 2 (~0.1), the path weights are updated based on path sum and global path updates (pheromone evaporation) after this

The questions I have:

Is the usage of ACO relevant here?
How can I improve the speed of the implementation?

Your problem is no harder and no easier than the approximate subset-sum problem.  There is a natural approach for your problem:

Find any subset that sums to something close to zero, and output it.  Remove those numbers from the set $A$.
Go back to step 1 and repeat, until the set $A$ is empty.

This requires a way to find a subset that sums to approximately zero, i.e., an approximation algorithm for the subset-sum problem.  That problem is well-studied and can be solved in polynomial time using an approach based on rounding and dynamic programming.

I don't see any reason to expect ant colony programming to be better than the standard approaches; and I wouldn't be surprised if it is worse.


What is total work of managing the dynamic array and why is it the same as for fixed array - O(n) I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book:

  Actually, we can efficiently enlarge arrays as we need them, through
  the miracle of dynamic arrays. Suppose we start with an array of size
  1, and double its size from m to 2m each time we run out of space.
  This doubling process involves allocating a new contiguous array of
  size 2m, copying the contents of the old array to the lower half of
  the new one, and returning the space used by the old array to the
  storage allocation system. The apparent waste in this procedure
  involves the recopying of the old contents on each expansion. How many
  times might an element have to be recopied after a total of n
  insertions? Well, the first inserted element will have been recopied
  when the array expands after the first, second, fourth, eighth, . . .
  insertions. It will take log2 n doublings until the array gets to have
  n positions. However, most elements do not suffer much upheaval.

  Indeed, the (n/2 + 1)st through nth elements will move at most once
  and might never have to move at all. If half the elements move once, a
  quarter of the elements twice, and so on, the total number of
  movements M is given by

  Thus, each of the n elements move only two times on average, and the
  total work of managing the dynamic array is the same O(n) as it would
  have been if a single array of sufficient size had been allocated in
  advance!

  The primary thing lost using dynamic arrays is the guarantee that each
  array access takes constant time in the worst case. Now all the
  queries will be fast, except for those relatively few queries
  triggering array doubling. What we get instead is a promise that the
  nth array access will be completed quickly enough that the total
  effort expended so far will still be O(n). Such amortized guarantees
  arise frequently in the analysis of data structures.]1

I don't understand why (n/2 + 1)st through nth will move at most once and might never have to move at all and total work of managing the dynamic array. Can someone please explain?

Also, why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays?

All that matters is the equation you are quoting. Here is another way to see it. Suppose you have $n$ items. You push one item at a time to the end of an initially empty array. When the array reaches size $2^k$ for some $k<\log_2 n$, you reallocate the array to size $2^{k+1}$ and move all items between $0$ and $2^k-1$ to the new location. The total number of item moves is:

$$ M=1+2+2^2+\cdots+2^{\lfloor\log_2n\rfloor}=2^{\lfloor\log_2n\rfloor+1}-1\le2^{1+\log_2n}-1=2n-1 $$

If you fill the array in a random order, the total number of item moves is bounded by $2n$, too. In all, the time complexity of filling an array of size $n$ is $O(n)$, no matter whether the array is dynamic or not.

  why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays

When you push an item to the end of an array of size $2^k$, you have to double the array and possibly copy $2^k$ existing items to a new location. This is not a constant-time operation. With dynamic array, each single operation is not always constant. However, such non-constant operations are so rare that the total number of operations to fill a dynamic array can still be $O(n)$.


Variable Capturing With Repetition of Variable Name I am very confused as to which variables are captured by which λ in the example below:

(λa.λb.(λa.a)aba)(ab)

I am new to lambda calculus and the repetition of variables makes this example hard for me to understand and reduce. Any help would be appreciated!

If you make the construction tree of the expression, a variable  $x$ of a leaf refers to that $\lambda x$ which is closest to $x$ in the path from $x$ to the root.

Another way to see it is with the use of scoping rules. The scope of each $\lambda$ is the body of the $\lambda$.

So, the scope of the inner-most $\lambda a$ is only $a$. This means that any occurrence of $a$ outside that parenthesis refers to a different variable than the $a$ inside the parenthesis (point 1).

The scope of the $\lambda b$ is $(λa.a)aba$, so similarly any $b$ outside this expression refers to a different variable (that just happens to have the same name).

The scope of the outermost $\lambda a$ is $\lambda b.(\lambda a.a)aba$. Here things are a bit more complex, because there's another $\lambda a$ inside. But according to point (1) the $a$ in $\lambda a.a$ is different than the $a$'s in the rest of the body. So, only the $a$'s in $aba$ refer to the outermost $\lambda a$.

Note that there are no lambda's to bind the $a$ and $b$ in subexpression $(ab)$ (on the right of the expression). Therefore, the $a$ and $b$ in $(ab)$ occur free.


How to solve $T(n)= 4T(\sqrt n) +\log^2n$? Consider the recurrence
$$T(n)= 4T(\sqrt n) + \log^2n. $$
 I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.

Let $S(n) = T(2^n)$. Then
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.


An n-dimensional index where the search key specifies an exact match on certain dimensions? I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value for that dimension. The value n, the number of dimensions, will be 4 or 5 in most cases.

For example, if I have a vector (1, 5, 9, 3, 7), I would want to be able to find such a vector by searching in the index with a search key specified as (*, *, 9, *, *), where * is a wildcard, and finding that vector and all other vectors with the value 9 in the 3rd position.

The reason for doing this is that I am building a path index for a graph database, where I precompute a large number of paths in a graph of length 4 or 5. These paths I store as vectors, where the first index in the vector specifies which path this is, and the remaining items specify the id of the nodes along that path.
 You can you use this to quickly answer graph queries such as:

"MATCH (person)--[likes]-->(food)--[madeBy]-->(company),

RETURN person, food, company".

You determine what ID you assigned the [likes],[madeBy] path, search in the B+tree for this ID, and now you have all the nodes on that path.

However, if you delete a specific food node from the graph, finding the relevant nodes in the B+Tree is not possible, since you don't know which paths it could be in. Therefore, finding it is O(n) in the index. You can also look at that node in the graph and compute all the paths it is in, which is another option I am looking in to, but it would be nice if there was a way to do this in the index itself. Such as, if you deleted a node with ID 5,  for a 5-dimensional index you could perform deletions: (*, 5, *, *, * ), (*, *, 5, *, * ), (*, *, *, 5, * ), (*, *, *, *, 5).

I appreciate any insight anyone has. Multi-dimensional indexing is new to me, and I have limited time to complete the project.

If you only want to be able to search on a single dimension at a time (as in your example), this is readily solved by precomputing an index.  Basically, you scan the entire database and build up an index for each dimension.  For instance, an index for the first dimension is a hashtable that maps from the value of $x_1$ to the tuple $(x_1,\dots,x_n)$, for each tuple.  You then build an index for the second dimension, for the third dimension, etc.  You do this once, in advance.  Once you have the index, it's easy to answer queries.  Also, it's easy to update the index when you insert or delete vectors.

A simple way to program this would be to insert your data into a database.  Most databases will automatically build indices and update them as you change the data in the database.  This will spare you having to implement that logic yourself.


Find all words of length $k$ in lexicographic order Given the alphabet $\Sigma = \{1,2,\dots, n \}$ and a parameter $k$ how can we find all words of length $k$ over $\Sigma$ in lexicographic order?
I thought of doing this recursively, but although the task is basic it seems pretty hard to come up with a general algorithm, even when using the last word as a parameter using recursion.
Will be glad for any help

You can do it either inductively or recursively.
Inductively, you just write out the numbers from $0$ to $n^{k-1}$ in base $n$, adding $1$ to all digits.
Alternatively, you can simulate a counter in base $n$ – that would be faster.
Recursively, you can proceed as follows:

Generate all solutions for $k-1$, and output them with prefix 1.
Generate all solutions for $k-1$, and output them with prefix 2.
...
Generate all solutions for $k-1$, and output them with prefix $n$.

Alternatively:
– Generate all solutions for $k-1$.

For each solution $s$, output $s1, s2, \ldots, sn$.


Proving $\#CYCLE \in \#P$ I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.

I saw this question:
Number of cycles in a graph? they mention the reduction from HAM #CYCLE in Counting Complexity by Arora and Barak, but I don't understand how does that help.

You have some directed graph, no one said it has a hamilton cycle, and the gadget doesn't return how many cycles there in the graph or a way to distinguish between them, it just makes all the cycles longer.

So instead, is it possible to use a topological sort to count cycles? since it can detect every cycle, we can use it to distinguish between them.

The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying
$$
 f(x) = |\{ |y| < p(|x|) : R(x,y) \}|.
$$
In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.


Is the intersection of two context free languages recursively enumerable? I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.

I could not, however, find a citation for this quotation (and searching has failed to turn up a restatement of this result somewhere else).

Can anyone provide a proof or a citation to the original proof for this result?  Can anyone state that it is false?

This result more easily follows from the fact that every context-free grammar is recursively enumerable, by enumerating all parse trees. The intersection of any two r.e. languages is r.e. - just enumerate them both and output every word that appears on both lists. The other direction (given by the quotation you found) is more interesting.

Edit: As Huck correctly comments, there are actually efficient algorithms for deciding membership in context-free languages. But the argument above holds for the most general grammars possible, in which case we prove that the language corresponding to any grammar is recursively enumerable. (Replace parse trees with the a sequence of rule applications.)


Acceptance of empty string by nondeterministic automaton Why is the input $\epsilon$ accepted by the nondeterministic finite automaton shown below?  Does it not leave $q_1$ and go to $q_3$?

You're confusing the concept of the empty string $\varepsilon$ with the concept of an $\varepsilon$-transition.

The empty string $\varepsilon$ is just the string with no characters.  The presence of a $b$-transition from $q_1$ to $q_2$ means that the automaton can move between those two states by reading character $b$ but the presence of an $\varepsilon$-transition from $q_1$ to $q_3$ doesn't mean that it moves by reading the character $\varepsilon$. Rather, it means that the automaton can (but is not forced to) move from $q_1$ to $q_3$ without reading any input at all.

So, when this automaton has no input, it can either remain in state $q_1$, which is accepting, or move to $q_3$, which isn't.  Since it can reach an accepting state, it accepts.


Modified Djikstra's algorithm So, I'm trying to conceptualize something:

Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:

movements on the graph are regulated by a circular cycle of length 48, in such a manner that:

  cycle{

     0 <= L <= 24  movement IS possible

    25 <= L <= 48 movement IS NOT possible

  }

For simplicity's sake, we will call this cycle 'time'.
The distance between nodes A and B is equal to:

  shortest_distance(A to B) - 1 OR shortest_distance(A to B) + 1

Depending on their orientation
the weight of the edges represents the 'time' it takes to travel between nodes.

I'd like to create an algorithm that will give me the shortest path with these constraints in mind, assuming one is leaving from node A at time(cycle) = 12, traveling towards node B. The shortest path would be defined as the path which takes the least 'time'.

Step one would obviously be to take into account the orientation affecting the shortest distance (i.e. which way are they oriented by above), which would be a simple addition or substraction to the result of djikstra's algorithm

What I'm having trouble figuring out is how to account for the cycle in the algorithm... could it be as simple as just an if statement checking to see if the current cycle time is within the constraints that allow movement?

Would my idea be viable? If not, does anyone h ave any suggestions at different ways I should look at this problem?

I know this question seems really basic, but I just can't wrap my head around it.

I didn't really understand your problem description, but if you go by the timezone analogy, the only thing stopping you from using Djikstra's algorithm are the negative costs on some edges (ie.: some edges go back in time). If this is the problem, you can get around it by using an alternate algorithm that can handle negative edges, like Bellman-Ford


number of comparison in sort algorith with special operation Let's define: $ a_i:a_j \Longleftrightarrow  a_i < a_j;\ a_i=a_j;\ a_i > a_j $
So it is similiar to normal operation $<$, but $:$ give information when elements are equal.
I want show that lower bound for sort array of $n$ elements with this operation is $\Omega (n\log n)$.

I know proof for normal comparison. Nevertheless I can't solve it, I thought about it a long time, but without effect.  Can you help me ?

(It isn't homework, nowadays I am on holiday :))

Let's suppose that it is possible to sort it with $:$ in time $o(nlogn$).
So we use ordinary comparisons: $<$ and $>$. If both $a_i<a_j $ and $a_j > a_i$ is not truth then we conclude $a_i=a_j$.  And now, we can sort in time:
$o(2nlogn)=o(nlogn)$ - it is impossible.


Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path on each node and when we compare we subtract the number of edges on this path * the constant so that we get the original weight. I understand there is also the negative cycles problem, but is there an efficient algorithm that tell if a graph contains a negative cycle ?

It's called Johnson's algorithm.

Instead of trying to keep track of the number of edges, it searches for a function $\delta:V\to \mathbb R$ so that for all edge $(v,v')$, $w(v,v')+\delta(v)-\delta(v')\ge 0$ and set that as the new weight $w'(e,e')$ of the edge $(e,e')$.

Then, for any path $p=v_1\cdot \dots\cdot v_n$ the $\delta$ values of all intermediate vertices cancel so that $w'(p)=w(p)+\delta(v_1)-\delta(v_n)$. And the shortest paths for $w$ and $w'$ therefore coincide.

Then remains the problem of finding such a $\delta$. The magic is that you can just add a new vertex $v_*$ and edges $(v_*,v)$ of weight $0$ for every vertex $v$, and then set $\delta (v)$ to be the weight of a shortest path $p_v$ from $v_*$ to $v$. Then the positiveness condition simply becomes $w(v,v')+w(p_v)-w(p_{v'})\ge 0$ which can be rewritten as $w(p_v)+w(v,v')\ge w(p_{v'})$ which is true because $p_v\cdot v'$ is a path from $v_*$ to $v'$ and $p_{v'}$ is a path from $v_*$ to $v'$ of minimal weight.


How is the problem of sorting in contiguous runs called? I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...).

  Given a sequence of values, sort it in a way that equal elements are compacted in runs (contiguous subsequences of identical elements).

For instance:

$$
\{1, 2, 4, 2, 1, 3\} \rightarrow \{ 2, 2, 4, 3, 1, 1 \}
$$

The runs are not otherwise sorted -- only equality comparison is required, not ordering; and they're compacted (there should not be two different runs containing equal elements).

Gopan et al. seem to define a more general problem and call it array partitioning [1].

The goals of array partitioning are twofold.  First, we
would like to isolate in separate groups [...]
we partition an array so that each element whose index is equal to
the value of any of the vari ables in the set is placed in a group by
itself. [...]
[W]e partition each array $A \in Array$ by grouping together elements of $A$
for which all partitioning functions in $\Pi_A$ evaluate to the same values.

I have not dug into how their formal framework captures your problem and it may not even do so. Still, I think the general idea is close enough to use the word.
Come to think of it, Quicksort-style partitioning is related as well: you want to partition w.r.t. identify, in Quicksort we partition w.r.t. equivalence classes induced by some pivots.

A framework for numeric analysis of array operations by D. Gopan, T. Reps and M. Sagiv (2005) [preprint]


Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

to

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considering only $n=2^k$. We assure ourselved that this step is valid -- that is, $T \in \Theta(T')$ -- because $T$ behaves "nicely". In general, we assume $n=b^k$ for $b$ the common denominator.

It is easy to construct recurrences which do not allow this simplification by using vicious $f$. For example, above recurrence for $T\,$/$\,T'$ with

$\qquad f(n) = \begin{cases}
                 1 &, n=2^k \\
                 n &, \text{else}
               \end{cases}$

will yield $\Theta(n)$ by using the Master theorem in the usual way, but there is clearly a subsequence that grows like $\Theta(n \log n)$. See here for another, more contrived example.

How can we make this "nicely" rigorous? I am quite certain that monotonicity is sufficient, but not even the simple Mergesort recurrence is monotone; there is a periodic component (which is dominated asymptotically). Is it enough to investigate $f$, and what are necessary and sufficient conditions on $f$ that ensure the Master theorem works?

Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).
Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this assumption later). We concentrate on your sample recurrence
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n). $$
This recurrence needs two base cases, $T(0)$ and $T(1)$. We make the assumption that $T(0) \leq T(1)$, which we also relax later on.
I claim that $T(n)$ is monotone non-decreasing. We prove by complete induction that $T(n+1) \geq T(n)$. This is given for $n = 0$, so let $n \geq 1$. We have
$$
\begin{align*}
T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\
&\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n).
\end{align*}
$$
This implies that
$$ T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rceil}). $$
So if $T(2^m) = \Theta(T(2^{m+1}))$, we're done. This is always the case if the solution for powers of two is of the form $T(n) = \Theta(n^a \log^b n)$.
Now let's relax the assumption that $T(0) \leq T(1)$. Consider a new recurrence $T'$ defined in exactly the same way, only $T'(0) = T'(1) = \min(T(0),T(1))$. We can prove by induction that $T'(n) \leq T(n)$. Similarly, we can define a new recurrence $T''$ satisfying $T''(0) = T''(1) = \max(T(0),T(1))$, and then $T(n) \leq T''(n)$. Invoking the Master theorem, we see that $T'=\Theta(h)$ and $T''=\Theta(h)$ for the same function $h$, and so $T = \Theta(h)$ as well.
Now let's relax the assumption that $f$ is monotone. Suppose that $f = \Theta(g)$ for some monotone function $g$. Thus $cg(n) \leq f(n) \leq Cg(n)$ for some $c,C>0$ and $n$ large enough. We assume for simplicity that $n=0$; the general case can be handled as in the previous paragraph. Again we define two recurrences $T',T''$ by replacing $f$ with $cg,Cg$ (respectively). Once again the Master theorem will give the same result (up to constant multiples), which is also identical (up to constant multiples) to what we would get by solving the original recurrence only on powers of two.


Interesting problem on tree You are given a tree of $N$ nodes with colors assigned to each node. You need to find for each node $X$, a value $AR[X]$.

$AR[X]$ = The sum of values of $CALC(X , i)$ for each $i$ from $1$ to $N$.

$CALC(A,B)$ = Count the number of non-repeating colors in the path from $A$ to $B$.

Can somebody suggest an efficient solution to this problem?

For a fixed root, there are two kinds of path: the ones which pass the root and the ones which don't. The first kind is special since we can seperate a path $(a,b)$ into $(a,r)$ and $(r,b)$, which might be easier to deal with via proper preprocessing. Consider following divide and conquer procedure:

Solve(T):
  Fix a root r
  for each a
    for each b s.t. (a,b) pass r
      AR[a]+=calc(a,b)
  for each branch T_i of r (which is also a tree)
    Solve(T_i)

Note that we neither miss a pair nor count a pair twice since $(a,b)$ don't pass $r$ if and only if they are in the same branch. In addition, it's not hard to prove that trees in depth-$d$ recursive call don't overlap. Therefore, if we can do the non-recursive part in $O(\text{size of tree})$, the complexity would be $O(\text{recursive depth}\times n)$. If we always choose $r$ as the centroid, recursive depth is bounded by $O(\log n)$ and hence the complexity would be $O(n \log n)$. Now let's see how to solve the non-recursive part.

For a pair of node $(a,b)$, let $\text{path}(a,b)$ denote the set of distinct values on the path from $a$ to $b$, and $I_{ab}(v)$ denote the indicator function which is $1$ when $v\in \text{path}(a,b)$ and $0$ otherwise. It's not hard to see $\text{calc}(a,b)=|\text{path}(a,b)|=\sum_vI_v$.

Recall that in each phase, we choose the centroid $r$ as the root and consider only the paths passing the root. Let $B_a=\{b\in T:(a,b)\text{ pass }r\}$. Using the indicator function above, we have $\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\sum_v I_{ab}(v)=\sum_v\sum_{b\in B_a} I_{ab}(v)$. Therefore, computing $\sum_{b\in B_a} I_{ab}(v)$ for each $a$ and $v$ also gives us the answer. (You can interpret this as the number of $b$ such that $v\in \text{path}(a,b)$.) To do this, consider the set $S$ for each value $v$ such that $S_T(v)=\{u\in T: v\in\text{path}(r,u)\}$. We need to maintain $|S(v)|$ for the whole tree and similarly $|S_i(v)|$ for the $i$-th branch of $r$. We will see how to implement this later.

Since $B_r=T$, $\sum_{b\in B_r}\text{calc}(r,b)$ is exactly $\sum_v|S(v)|$. Next, consider node $a$ in the $i$-th branch. Let $r_i$ denote the $i$-th child of $r$. For each node $b$ which is not in the $i$-th branch, we can split path $(a,b)$ into $(r,b)$ and $(r_i,a)$. Therefore, $$\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\text{calc}(r,b)+\sum_{b\in B_a}|\text{path}(r_i,a)\backslash\text{path}(r,b)|$$
It's not hard to see that the first term equals to $\sum_v(|S_T(v)|-|S_i(v)|)$, so let's focus on the second term. Now consider each node $u$ on the path from $r_i$ to $a$ and count $\text{value}[u]$ one by one. There are two possible cases:

$\text{value}[u]=\text{value}[u']$ for some $u'\neq u$ on the path from $r_i$ to $u$. In this case, we have already counted $\text{value}[u]$ before so just ignore it.
If not, we should count the number of $b$ such that $\text{value}[u]$ doesn't appear in $\text{path}(r,b)$ and add it to $AR[a]$. This is exactly $(n-n_i)-(|S(\text{value}[u])|-|S_i(\text{value}[u])|)$ where $n_i$ is the number of nodes in the $i$-th branch.

Note that the number we count for each $u$ is independent from $a$. Therefore we can do this for every $a$ in a single DFS which takes $O(n)$. (Tell me if you need more details.)

Now the only remaining part is the preprocessing which computes $|S(v)|$, and it's actually similar to previous steps:

Consider each node $u$.

If $\text{value}[u]=\text{value}[u']$ for some $u'\neq u$ on the path from $r$ to $u$, we have already counted $\text{value}[u]$ before so just ignore it.
If not, add $n_u$ to $|S(\text{value}[u])|$. Here $n_u$ means the size of subtree rooted at $u$.

$|S_i(v)|$ can be computed similarly. The preprocessing also takes $O(n)$.

The complete flow seems like

Solve(T):
  Choose a centroid r as the root
  Preprocess() //Compute |S(v)| and |S_i(v)| via a tree traversal

  AR[r]+=Sum{|S(v)|}
  for each node u
    AR[u]+=Sum{|S(v)|-|S_i(v)|}

  Update AR with the second term via another tree traversal

  for each branch T_i of r (which is also a tree)
    Solve(T_i)


Question regarding notation of a language decidability $1.\: A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$
$2.\:A_{DFA} = \{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$
I know how to proof that 1 is decidable by constructing a machine that always halts and accepts whenever $B$ accepts, otherwise rejects. what's the difference between 1 and 2. I find that it doesn't make sense to not include $w$ inside the encoding brackets but I have seen this notation in other places. are they both the same?

The languages are not the same.

In the first one, $w$ is a part of the input.
In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.


information about matching algorithms? I have been searching for matching algorithms similar to the Gale Shapley, or stable marriage algorithm, but with no luck.
The question is if there are other algorithms that are similar to the GS and used for the assignation of persons or items based on preferences?

A very similar well studied problem is the assignment problem. In essence, it seeks to find a matching in a weighted bipartite graph that has maximum weight. Such matching is not necessarily stable, but maximum weighted matching might be preferable than a stable one, depending on the application.

On the plus side, the well known Hungarian algorithm solves the assignment problem in an optimal manner. There are also other methods to solve it such as the Auction algorithms. As I said, the field includes well established methods.

Maybe you can think about representing your problem as an assignment one rather than stable marriage.


Unix glob() function and formal language equivalence Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, which is the minimal automata that we need?
For those that do not know what glob() does, it is a pattern matcher generator using a few operators:

* matches an unlimited number of consecutive characters. As this can be in any position, not only in the end of the pattern, I eliminated the possibility of expressing glob expressions in terms of regular expressions.
? matches exactly one arbitrary character, which is similar to a skip state in a finite automaton.
[abc] matches an arbitrary-length string consisting of only symbols in the brackets, and [!abc] matches an arbitrary-length string that includes anything but symbols in the brackets. Those character sets can also be listed in a shorthand notation like [a-z] or [!a-z].

Every glob expression can be recognized with a regular expression (the translation is straightforward).  Every regular language is also context-free, and there is a straightforward translation: convert the regular expression to a DFA, then turn that into a pushdown automaton that never uses or looks at its stack.  So, it follows that every glob expression can be recognized by some pushdown automaton, i.e., it recognizes a context-free language.


Continuous Mutual Correction from Multiple Sensors I'm stumped on what exactly to search for; so here is a non-scientists description of the topic.

I've got multiple sensors of different types that are measuring the same physical value in different ways. The sensors are all subject to significant error or temporary unavailability, but in greatly different ways. I want to develop code that can use all available sensor data by maintaining slowly changing corrections for each sensor based on the other.

I would love guidance on what exactly to look for to begin a literature search on the topic. Thanks.

Notes based on comments:

A silly example would be collection sampled data on an instrumented automobile's scalar velocity from:

wheel rotation frequency sensor
pitot type anemometer
tri-cup anemometer
MEMS accelerometer
GPS

The physical value being measured, the signal, is not periodic or in any way predictable. It ranges from 0.0 to Max, where max is greater than zero and noninfinite. It is relatively easy to define reasonable limits for max_value, max_delta_value and so on be observation and calculation from simplified Newtonian models.
At least one sensor is subject to calibration/bias drift continuously. This should be at least 4 orders of magnitude below reported value, but in nonnegligible.
At least one sensor is unbiased, calibrated and provides confidence range data along with sample data. Per sample error can be as much as 2 orders of magnitude greater than sample value.
All sensors use wireless communications of data, so all samples are not reported. No error in measurement is introduced in transmission.

The broad area that studies these kinds of topics is called estimation theory.  This is more a matter of statistics than of computer science, so you might want to take a look in some statistics textbooks and check out the Statistics.SE.

For instance, you might be interested in the Kalman filter.

That said, before one can devise a solution to your specific solution, we'd need a lot more information about what you know.  Do you know anything about the joint distribution of their sensing?  Do you know anything about the accuracy of each sensor (e.g., its variance)?  Are all sensors calibrated and unbiased?  Do you know anything about how the underlying physical value changes over time or the distribution it comes from?  Do some self-study of the literature, and make sure you know the answers to those before asking on Stats.SE.


Are statecharts with parallel states NFA, DFA, or none of the above? I'm looking for formal statements and proofs that I can make when using SCXML statecharts. As such, I'm trying to categorize it properly.

SCXML supports hierarchical states. I believe that any hierarchical state machine can be converted into an equivalent non-hierarchical state machine. And I believe that a "simple" non-hierarchical state machine can be considered a DFA (deterministic finite automata).

SCXML is not a "simple" state machine, however:

Transitions between states may be guarded by arbitrary code conditions. Only one transition from an active state will be taken as a result of a single event, but which transition is taken may vary. Given this, I believe that SCXML should be considered (for certain configurations) an NFA (non-deterministic finite automata).
Certain transitions may be taken not in response to an event, but as soon as a condition is valid. Given this, I believe that SCXML may at times be considered an NFA with ε-moves.
SCXML supports not just hierarchical states, but also "parallel" (orthogonal) states. These allow the runtime to be in more than one atomic ("leaf") state simultaneously.

This last detail gives me pause, as I have not found any formal statements classifying parallel state machines. Does the introduction of concurrent parallel states break any NFA definition?

I think that it doesn't. I think that you can convert any parallel state machine into an equivalent non-parallel machine via combinatorial explosion. But I'd like to know it for sure.

The paper Parallel Finite Automata for Modeling Concurrent Software Systems contains a proof and examples showing that a (non-hierarchical) parallel state machine can be converted into a non-parallel version. The technique is somewhat obvious: simply create the cartesian product of all concurrent sections and you have a DFA.

Combine with a proof that any hierarchical section of a state machine can be flattened into an equivalent non-hierarchal version, and there exists an obvious—but hard for me to formally notate—conversion process that involves flattening hierarchies and expanding parallel sections from the leaves on upwards.

The result is that any SCXML state machine can be converted into an equivalent version that contains neither hierarchy nor parallel states. At this point the state machine may be DFA, NFA, or NFA with ε-moves (depending on the transitions used), but all of these are similarly equivalent.

In summary, I believe that any SCXML state machine can be converted into an equivalent DFA, and as such the formalisms of DFA apply.


Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$ I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?

Algorithm A

i = 1
while i ≤ n
  s = 0
  while s ≤ i
    s = s + 1
  i = 2 ∗ i

The inner loop is clearly $O(i)$ (linear time).

The outer loop is clearly $O(\log n)$ (logarithmic time).

A visualitation of the loop in terms of an input $n$ would look as follows:

, the black lines represents the amount of work or iterations required in terms of $n$.

$\sum_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.


All-zeros subnet and All-ones subnet It is said that practically all-zeros and all-ones subnets are not used.

Let us consider an a network $200.200.13.13/25$

Here Network ID is represented by using $25$ bits and Host ID using $32-25=7$ bits.

Binary Representation : $11001000.11001000.00001101.00000000$

Last 7 bits which represent HID are $0000000$

Suppose we want to divide the network into $4$ subnets, so we will borrow $2$ bits from Host.

So the subnets will be

$11001000.11001000.00001101.00000000$ - $200.200.0.0/27$

$11001000.11001000.00001101.01000000$ - $200.200.0.64/27$

$11001000.11001000.00001101.10000000$ - $200.200.0.128/27$

$11001000.11001000.00001101.11000000$ - $200.200.0.192/27$

Now it is said that all-zeros and all-ones subnets are not used, then let us consider -

(i) the IP addresses ranging from $200.200.0.0 - 200.200.0.63$ which should belong to all-zeros subnet and

(ii) the IP addresses ranging from $200.200.0.192 - 200.200.0.255$ which should belong to all-ones subnet

Will belong to which subnet/network or will remain unallocated ?

Not "it is said", in IPv4 the "host part all zeros" address defines the (sub)net (and isn't available as host address), the "host all ones" address is broadcast for the (sub)net (and also isn't available as host address). All other addresses can certainly be used (and given that IPv4 addresses ran out, there is a lot of pressure to use all).


Taking intersection in large search As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once

сomputer -> About 2.14 bln results
science -> About 1.93 bln results

computer science -> About 377 mln results
"computer science" -> About 147 mln results
science computer -> About 0.97 bln results
"science computer" -> About 452k results

So, you have got 2 billion pages immediately. To find out the pages which contain both words, you seem to need to make an intersection. How do they make it immediately? I do not believe that they try all 10^18 matches

for p in pages(word1):
 for q in pages(word2):
  if p == q yield p

If you're asking how Google actually works, you'd have to ask Google.

If you're asking how a search engine could plausibly achieve this functionality in a reasonable amount of time (say, within 1 second), here are several strategies, any one of which could work fine:

Use a SSD.  Normally, a search index is a map from a search term to a sorted list of document IDs (the IDs of the documents that contain that search term).  Because these lists are sorted, you can compute the intersection of two lists in time linear in the length of those lists, by using the "merge" algorithm from mergesort.  (This is faster than the quadratic algorithm you list.)

As a result, the intersection can be computed in one pass, a streaming fashion.  For the parameters you mention, the bottleneck will be the time to read in those sorted lists from disk.  If you store them on a SSD, this can be relatively fast.  Some modern SSDs can achieve a read bandwidth of perhaps 2500 MB/s.  If each document ID is 4 bytes, reading in 4 billion document IDs will take about a half a second. The computation time is negligible in comparison, so the intersection could be computed under a second if indices are stored on a fast SSD.
Parallel computation. If you split the indices across multiple SSDs (say, using RAID or striping), you can increase the read bandwidth.  If you use a cluster of machines, each with their own SSD, you can parallelize both data transfer and computation.  The intersection task is trivially parallelizable, so you can achieve excellent speeds this way.  For instance, if you're using magnetic hard disks with read bandwidth of 200MB/s, striping the indices and computation across 8  machines is enough to finish this task in under a second.
Caching. You only need to do this work once.  Once you've computed the size of the intersection once, you can store it in a table and cache it for some time period (a month or more), as it's unlikely to change much in the future, and then once someone else asks the same cache, you can return the number of results instantaneously.
Estimation via random sampling. An even better approach is to avoid computing the entire intersection, but just estimate its size through random sampling.  You repeatedly do the following: randomly choose a document that contains computer, and check whether it also contains science.  Each trial (randomly picking a document that contains computer) can be done in one operation, by picking a random offset into the sorted list for computer, and then it's easy to check whether that document also contains the word science (say, by binary search into the sorted list for science).  Repeat this 1000 times, and you can get a good estimate of the fraction of documents containing computer that also contain science -- this uses the same principles as political polling, where we survey a random sample of people and then extrapolate to draw inferences about the entire population.  Multiply that fraction by the total number of documents containing computer, and you've got an estimate of the size of the intersection.

You can apply similar ideas to count the number of documents containing the phrase "computer science".


How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack? I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? I can understand the algorithm for Subset Sum Problem (SSP) which is a particular instance of 0-1 KP, but for the generalized problem there might be something wrong with the step:

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

As I understand, this is to search (eg. do binary search) on combined weights of all subsets of B, which takes logarithm time for each search. But after knowing which subsets have combined weight less than W, how to find the one of greatest value? If search on values of the subsets with weight < W, it takes linear time to find the maximum since the list of value is unsorted this time. As a result, the total time complexity is no longer $O^*(2^{n/2})$, but something like $O^*(2^n)$.

Even if it starts from finding the subset of greatest value (easy for a table) first without constriction on combined weight, after that, verification of weight will probably turn false and thus more tests are needed for other subsets, of which the number seems associated to the table size linearly again.

Now I can only assume the total value and combined weight are strongly positive correlated, so that after finding the subset with maximum allowed weight, it takes only constant time to search around this subset for the exact one of greatest value. But I am not satisfied with this explanation. So anyone has better ideas about this issue?

PS: I have read the original paper by Horowitz, Ellis and Sahni, Sartaj, but I found the problem defined there is a decision problem rather than the common optimization problem. Maybe somebody can provide ideas in this direction.

First, precompute the weights of every subset of $B$.

Sort them by weight and put the weights and subsets in parallel arrays so that $W[i] = weight$ and $S[i] = subset$.

Then make another parallel array so that $BEST[i]$ is the index $j$ of the set of greatest value such that $j<=i$.  You can do this with a single scan from $i=0$ upward, remembering the greatest value seen so far at every step.

Now, to search $B$, you do a binary search in $W$ to find the maximum permissible weight, and get the best set from the same index in $BEST$


DPLL algorithm: OLR vs. PLR Can someone please show me examples of what is the difference between OLR (one literal rule) and PLR (pure literal rule) using the DPLL algorithm?

The one literal rule, usually known as the unit clause rule, state that if you have a unit clause (a clause containing only one literal) then you should set that literal to the value which satisfies the clause.

The pure literal rule states that if some variable appears only positively or only negatively in all clauses, then you can set that variable accordingly (true if it appears positively, false if it appears negatively).

You can apply the unit clause rule but not the pure literal rule in the formula $p \land (q \lor \lnot p)$. The result would be setting $p$ to true and simplifying the formula to $q$. Another application of the unit clause rule will set $q$ to true and will satisfy the formula.

You can apply the pure literal rule but not the unit clause rule in the formula $(p \lor q) \land (p \lor r)$. The result would be setting $p$ to true, and satisfying the formula.


Are coevolutionary "Free Lunches" really free lunches? In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-player games in which a player tries to minimize expected search cost given optimal play, or at least good play, by an opponent.

Free lunches are "allowed" in this case because the exact choice of cost function to minimize changes depending on which fitness (i.e. objective) functions previous rounds of play have "ruled out." In other words, given that an opponent already knows something about the game, and chooses responses that minimize the player's expected return, the player can eliminate certain fitness functions without having to evaluate them. To illustrate how this works, W&M provide this chart:

Here, $\langle g \rangle$ represents the search algorithm that pays no attention to the opponent's moves; $\langle g \rangle_{1}$ represents the search algorithm that considers all possible opponent replies to each move; and $\langle g \rangle_{2}$ represents the search algorithm that samples just one possible opponent reply to each move.

This illustrates the character of the free lunch provided: algorithms that take into account information provided by the opponent do better than algorithms that don't, and those that collect as much information as possible from the opponent do better than those that only collect some. W&M amplify this point in their later discussion of opponent intelligence. They show that even when an opponent is not omniscient, but has partial knowledge, the player can exploit its partial knowledge. In the case of total ignorance this won't work because the opponent always replies with a random move. In that case, there appears to be no gain:

  the expected performance of the agent will be the average over the antagonist’s possible responses.

I guess this looks like $\langle g \rangle$ above. But in cases where the opponent has some knowledge, algorithm performance appears to increase monotonically with opponent intelligence.

What confuses me about all this is that the argument appears to boil down to the following trivial-seeming claim: across all problem domains, algorithms that bother to learn from knowledgable opponents do better than algorithms that do not. That is, as long as you don't turn down the free lunch, you can have it.

In effect, lunch is free because the opponent is buying.

If that's true, then couldn't we imagine a whole range of games in which, say, players play cooperative games with oracles, and those that refuse to cooperate perform worse on all problems? That's a free lunch in the same sense, right? But then we haven't explained where the oracle's knowledge comes from.

Does this mean that if we had to model the source of the other player's knowledge, we'd be back in the No Free Lunch zone? Or is the claim really that this sort of competitive play yields better outcomes even when both players start out in total ignorance, as the phrase "free lunch" seems to imply?

Coevolutionary algorithms can't magically accelerate progress on any arbitrary problem class. So in that sense, the conclusion at the end of the question is correct. However, it doesn't follow that all coevolutionary free lunches are trivial, as the conclusion of the question suggests.

I can't offer an exhaustive account of all the kinds of coevolutionary free lunches, but I can offer two examples, the first of which is trivial, and the second of which I would argue is nontrivial. The second is nontrivial because it helps explain why the no free lunch theorem really must hold.

The important difference between the two examples is this: in the first, the competing algorithms are competing to achieve the same overarching goal, while in the second, the competing algorithms are trying to achieve different goals. In the second case, the mismatch between the two algorithms' goals allows interesting things to happen. I'll begin with the trivial example.

Opponents seeking the same goal

Imagine a very simple optimization problem in which the search landscape is a 7x7 grid of cells. The primary goal is to find the cell with the maximum value. 48 of the cells have a value of 0, and one randomly chosen cell on the grid has a value of 1.

Our secondary goal is to discover a search strategy that finds the maximum value more quickly. But it follows from the initial problem that no strategy could possibly beat random search here, because nothing can be learned from one cell about another. Nonetheless, the coevolutionary free lunch theorem holds! Here's why:

Suppose you have two optimization algorithms, A and B, both searching the grid. It doesn't really matter what strategy they use, but for concreteness, we'll stipulate that they both use a random search strategy. The only difference between them is that B pays attention to A's moves, and when it sees that A has found the maximum value, it jumps to that cell too. In some sense, when that happens, B has still "lost" the contest. But if you run a lot of competitions, and then compare the average performance of A to the average performance of B, you'll see that B finds the maximum value faster on average.

The explanation is simple. The average time to first discovery -- whether by A or B -- stays the same. But whenever A beats B to the win, B doesn't bother looking anywhere else. It skips ahead to the best cell. When B beats A to the win, on the other hand, A just continues searching, plodding along until it finds the maximum value on its own.

This looks like a win if you're only counting the number of moves B makes. If you look at the total number of moves that A and B make together, they actually do worse together than either would on its own, on average. That's because of A's obliviousness. If we change A to behave the same way as B, then they do about as well together as either would on its own -- but no better.

So here, modeling both algorithms together returns us directly to the no free lunch zone, just as the question argues. In effect, A and B are just performing random search algorithms in parallel. The final number of search operations remains the same.

Opponents seeking different goals

Now imagine a very different scenario. Suppose we have a classification problem: recognizing sheep. Here, A's job is to look at a stream of pictures and say whether there are sheep in them. Simple enough.

But B's job is very different. B has the power to inject pictures of its own into the stream! Its goal is not to identify sheep; it just wants to slow A down.

How can B do this? There's a great blog post and associated Twitter thread about a closely related question by Janelle Shane. The Twitter thread begins:

  Does anyone have a picture of sheep in a really unusual place? It's for pranking a neural net.

And here's one of the first replies:

  How about an orange sheep?

Here's the orange sheep:

Turns out, this was perfect for pranking:

  You totally got it. Orange sheep are not a thing it was expecting.
  "a brown cow laying on top of a lush green field"

Here are a couple of other examples from Shane's blog post:

So what does this have to do with our problem? We can connect them by being more precise. Suppose A's goal is to reach greater than 99% accuracy, and B has the power to inject one picture into A's stream for every nine "natural" pictures. B looks for patterns in A's behavior and uses them to find pictures that mess with its model. This will keep A's accuracy below 99% for much longer than if A saw only "natural" pictures.

Two things follow from this. First, B will do much better if it pays attention to what A does. If B just picks images on the basis of some randomly chosen general principle like "sheep in odd places," then there's a good chance that A will be prepared for them already. If not, it will quickly learn to handle them correctly, and B will then have to adopt a new strategy. On the other hand, if B watches A's behavior, it can pick out the specific things that A is worst at, and focus on those. As soon as A improves at one of them, B can have another one ready to go. As long as B can find patterns in A's behavior, B will always present the most challenging images for A.

Second, A will do much better if it pays attention to which images B picks. After all, B is looking for patterns in A's behavior. If it finds patterns, then it will use those patterns to send fake or troublesome pictures to A. In turn, that means that there will be noticeable patterns driving B's choices. Here again, if A is paying attention to the patterns in B's behavior, it will more quickly be able to identify which pictures B is injecting.

What's important is that in this scenario, both A and B are relying on data that is guaranteed to have patterns. It is guaranteed to have patterns because if A is doing its best, A is doing something other than random search. And if B is doing its best, then B is doing something other than random search.

So initially, this looks like a really compelling free lunch situation. But what have we actually shown? We've shown this:

  As long as A is doing something other than random search, B can always find out-of-band samples that A's methods cannot handle.

That's the no free lunch theorem in a nutshell!

The only way A can prevent B from finding out-of-band images is by behaving in ways that look random to B. But if A's behavior isn't really random, then in the very long run, B will always be able to find the pattern -- even if B itself is only doing random search.

The very same argument works in the other direction. The only way B can prevent A from noticing patterns in its images is by behaving in random-seeming ways. But if B's behavior isn't really random, A will eventually find the pattern, even if it's only doing random search.

In this scenario, both algorithms will try to fool each other by adopting more and more complex, random-seeming behaviors. So in the very, very long run, they will slowly converge to a truly random search -- which is the best any algorithm can do on average across all problem domains.

An infinite pool of randomness

It might be that these coevolutionary learning strategies do still have this advantage over others: they may encourage both algorithms to explore the space of relevant non-random behaviors more quickly or extensively. I am not even sure of that. Either way, the no free lunch theorem holds in general, because the space of possible non-random behaviors is far, far smaller than the space of possible random behaviors.

How do we know? It would be off topic to go into a detailed proof, but consider the related question of how many long strings can be compressed into shorter strings. Regardless of the compression method, the majority of all strings cannot be compressed at all. This is easy to prove with a bin-counting argument. Suppose we consider binary strings, and start with the empty string. Assuming there can be no negative-length strings, that's incompressible. Now consider length-1 strings. There are two, but there's only one length-0 string, so only one of them can be compressed. Now we have two incompressible strings, and a third string that can be compressed by one bit. Moving on to length-2 strings: there are four, but there are only two length-1 strings, and the one length-0 string is already taken, so we can only compress two of the length-2 strings. The other two are incompressible. That's three compressible strings and four incompressible strings... and so on.

As the numbers get higher, one of the things you notice is that even among the compressible strings, half of them are only compressible by one bit, because they compress to strings that are themselves incompressible. A quarter are only compressible by two bits; an eighth are only compressible by three bits. No matter how you slice it, the number of substantially compressible strings is always much lower than the number of strings that are incompressible or barely compressible.

The line of reasoning for random behavior is similar. You could also connect these ideas to the proof that there are vastly more real numbers than integers. In the global scheme of things, the no free lunch theorem is true because the scope of randomness is unimaginably vast.


Short pipeline or long pipeline What is meant by a short pipeline?

Does that mean the instructions are split into small number of pieces OR length of a piece is short?

If by pieces one means possible stages that the instruction can be split into. For example, like this "short" Classic RISC pipeline with five stages:

Fetch Instruction Stage: Fetch the instruction.
Decode Instruction Stage: Decode the instruction.
Execute Stage: Execute the instruction.
Memory Access Stage: Access (read/write from/to) the memory.
Writeback Stage: Write results to the CPU registers.

Then a short pipeline means that the instruction is split into a low amount of these stages (pieces), but the amount of hardware and time spent in each stage will actually increase (length of the pieces) compared to if there were more stages.


How to read BNF syntax of C? Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a fair idea about how to read the syntax.

But I don't understand what the first two lines mean:

%token int_const char_const float_const id string enumeration_const
%%

Also I am reading BNF just because I am just curious. How should I proceed to understand the formal syntax by reading BNF?

Here is the BNF syntax of C.

Backus Normal Form does not define special syntax for %token.  So that would be a special syntax custom-added by a particular person or web page or tool.  Tool support is off-topic here, but if search for "%token" on the first link you gave, you'll find a brief explanation that appears to describe what %token means in the context of that particular example.

In other words: if you only want to understand BNF at a conceptual level, ignore it.  That's something that's not part of BNF, but is an add-on that was added for some special purpose.  If you want to understand that the specific syntax used by some specific tool (e.g., YACC), your best source is probably the reference manual for that tool.


What are the minimum and maximum numbers of elements in a heap of height h? I came across the question:

What are the minimum and maximum numbers of elements in a heap of height $h$?

To which I came up with this theory:
$$\sum_{i=0}^{h-1} 2^i = 2^h-1$$
$2^h-1$ is the internal nodes and that is understood according to the understood fact. But because nowhere except CLRS mentions heaps to be a Nearly Complete Binary Tree everywhere it is mentioned as a Complete Binary Tree.
The maximum number of elements can be easily computed:
$$\sum_{i=0}^{h} 2^i = 2^{h+1}-1$$
But I cannot get the point of computing the minimum number of elements:
Should it be:
$$2^{h}+1$$ for $0$ or $2$ children property
Or should it be:
$$2^{h}$$ for $0$ or $1$ children property
Reference1: https://walkccc.github.io/CLRS/Chap06/6.1/#61-1
Reference2: HeapSort
Thank you.

A heap of height $h$ is complete up to the level at depth $h-1$ and needs to have at least one node on level $h$.
Therefore the minimum total number of nodes must be at least
$
\sum_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h.
$, and this tight since an heap with $2^h$ nodes has height $h$.


Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters every time) - and only if they are all accepted (follows the condition) then accept w.
Is it possible in NFA? Is there other way to show the regularity of the language?

Nice question! This is a very nontrivial problem involving regular languages.
First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to run the automaton only once on the target string.
In this case it is simpler to reason on the complementary of the given language, namely on
$$L^C =  \{ w \in  (a,b) ^ * \mid \text{ there is a substring } u \text{ of } w \text{ such that } |u|_a−|u|_b>5 \text{ or } |u|_a−|u|_b<-5\}$$
The language $L^C$ is regular, as it is recognized by the following NFA:

(each state name is the difference $|u|_a−|u|_b$, the first letter of the substring $u$ is "found" nondeterministically by the NFA).
So, as $L^C$ is regular, also $L=(L^C)^C$ is.

Following Hendrick's suggestion, I tried to determinize the NFA and to draw its complement, and I get this nice DFA that recognize $L$:

Each name of an accepting state name is an interval: when, running the automaton, we are in state $[x_1,x_2]$ and we have read the string $z$ this means that for all $x\in [x_1,x_2]$ there is a suffix $u$ of $z$ such that $|u|_a−|u|_b=x$. Otherwise said, following Dmitry's suggestion, the automaton calculate the residual set of $z$.
In a sense, as Hendrick says, it is like we are running the automaton on each substring, but this do not mean that we can directly use a DFA that recognize strings such that the difference between the $a$s and the $b$s is in $[-5,5]$ (which would be easy to realize) and run this automaton on each substring of a given one, and in this way prove that the language is regular.

Lastly, I would write a trivial generalization of the result (I think that this is folklore, but I couldn't find a reference).
Let $T$ be a regular language on an alphabet $\Sigma$ and let $L$ be the language defined as follows:
$$L=  \{ w \in  \Sigma^* \mid \text{ for every substring } u \text{ of } w,\ u\in T\}$$
then also $L$ is regular.
Indeed, as above, consider $L^C$, the complement of $L$, namely
$$L^C =  \{ w \in  \Sigma^* \mid \text{ there is a substring } u \text{ of } w \text{ such that } u\not\in T\}$$
Then $L^C=\Sigma^*T^C\Sigma^*$, and therefore $L=(\Sigma^*T^C\Sigma^*)^C$ is regular, as the family of regular languages is closed under concatenation and complementation.
Cleary the result is still true for every family of languages closed under concatenation and complementation, but this is not a necessary condition. Indeed, the family of finite languages it is not closed under complementation, but clearly if $T$ is finite, then also $L$ is (as it is always the case that $L\subseteq T$).
On the other hand, this is not true for all classes of languages. Consider the family NR of non-regular languages, then $T=\{1^p\mid p\text{ is prime}\}\in\ $NR, but in this case we have $L=\varnothing$, which is regular.


Solving recurrence relation when cost of all combining steps is constrained I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n)$, where each $ 0 < d_i < 1$, $f(x) > 0$ for all $\, x > 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$.

I am asked to give an asymptotically tight bound on $T(n)$ if $\sum_{i=1}^{k} f(d_i) < 1$ and if $\sum_{i=1}^k f(d_i) = 1$ using the substitution method, and I am told not to worry about the base case. I am following the substitution method from CLRS section 4.3 and  basically means guess an upper bound, and then prove by induction.

I tried several guesses when $\sum f(d_i n) < 1$, but I get stuck regardless of my choice. If $T(n) = O(f(n))$, it must be true that
\begin{align*}
T(n)&\leq c f(d_1n) + c f(d_2 n) + \dots + cf(d_k n) + f(n)\\
&= c(f(d_1 n) + f(d_2 n) + \dots f(d_k n)) + f(n) \\
&< c + f(n) & \text{Since} \sum f(d_i n) < 1
\end{align*}
Which is false, unless $c < 0$, which can't be the case.

If $T(n) = \lg f(n) $ then it must be true that

\begin{align*}
T(n) &\leq c \lg (f(d_1 n)) + c \lg(f(d_2 n)) + \dots + c \lg(f(d_k n)) + f(n) \\
&=c [\lg f(d_1) + \lg f(n) + \lg f(d_2) + \lg f(n) + \dots + \lg f(d_k) + \lg f(n)] + f(n) \\
&=c \left( \left(\sum_{i=1}^{k} \lg f(d_i)\right) + k \lg f(n) \right) + f(n).
\end{align*}
Not sure how to proceed here. When I tried $T(n) = O\left(f(n)^2\right)$, I got

\begin{align*}
T(n) &\leq c \left( \sum_{i=1}^n f(d_i n)^2 \right) + f(n) \\
&< c + f(n) & \text{ since } \sum f(d_i n ) < 1 \implies \sum f(d_i n)^2 < 1  \\
&\leq c f(n)^2
\end{align*}
which doesn't seem too tight, but I'm not sure. Any comments or pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d_i)$ in some other way, but right now I am not seeing how to do so.

Form a recursion tree. The root represents $T(n)$, and has weight $f(n)$. It has $k$ children, the edges are labelled $f(d_1),\ldots,f(d_k)$, and the children itself have weights $f(d_1)f(n),\ldots,f(d_k)f(n)$; they correspond to $T(d_1n),\ldots,T(d_kn)$. Each child has its own $k$ children, and so on, only we delete nodes corresponding to $T(m)$ for $m < 1$. Note that the weight of each node is $f(n)$ times the weights of all edges from the node to the root. The total running time, assuming a base case around $1$, is the sum of all weights in the tree.

When $\sum_{i=1}^k f(d_i) < 1$, we can compute the total weight of the infinite tree (without the pruning described above) as
$$
f(n) \sum_{t=0}^\infty (f(d_1) + \cdots + f(d_k))^t = \Theta(f(n));
$$
here $(f(d_1) + \cdots + f(d_k))^t f(n)$ is the total weight at level $t$. Thus in this case we have $T(n) = \Theta(f(n))$.

When $\sum_{i=1}^k f(d_i) = 1$, each full level contributes $f(n)$, and each partial level (where some nodes were pruned) contributes at most $f(n)$. There are $\Omega(\log n)$ full levels and $O(f(n))$ full or partial levels, and we conclude that $T(n) = \Theta(f(n)\log n)$.


What is induction-induction? What is induction-induction?

The resources I found are:

the HoTT book, at the end of chapter 5.7.
nLab's article
a paper called Inductive-inductive definitions
this blog post also mentions inductive-inductive types

The first two references are too brief for me, and the latter two are too technical. Can anyone explain it in layman's term?
It would be better if there's Agda code.

Supplemental 2016-10-03: I mixed up induction-induction and induction-recursion (not the first time I did that!). My apologies for the mess. I updated the answer to cover both.

I find the explanations in the Forsberg & Setzer's paper A finite axiomatisation of inductive-inductive definitions illuminating.

Induction-recursion

An inductive-recursive definition is one in which we define a type $A$ and a type family $B : A \to \mathsf{Type}$ simultaneously in a special way:

$A$ is defined as an inductive type.
$B$ is defined by recursion on $A$.
Crucially, the definition of $A$ may use $B$.

Without the third requirement, we could first define $A$ and then separately $B$.

Here is a baby example. Define $A$ inductively to have the following constructors:

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

The type family $B$ is defined by

$B(a) = \mathtt{bool}$
$B(\ell(x, f)) = \mathtt{nat}$.

So, what is in $A$? First of all we have an element $$a : A.$$ Because of that, there is a type $B(a)$ which is defined to be $\mathtt{bool}$. Therefore, we can form two new elements $$\ell(a, \mathtt{false})$$ and $$\ell(a, \mathtt{true})$$ in $A$. Now we have $B(\ell(a, \mathtt{false})) = B(\ell(a, \mathtt{true})) = \mathtt{nat}$, so we can also form for every $n : \mathtt{nat}$ the elements
$$\ell(\ell(a, \mathtt{false}), n) :  A$$
and
$$\ell(\ell(a, \mathtt{true}), n) : A$$
We can keep going like this. The next stage will be that since
$$B(\ell(\ell(a, \mathtt{true}), n)) = \mathtt{nat}$$
there is for every $m : \mathtt{nat}$ the element
$$\ell(\ell(\ell(a, \mathtt{true}), n), m) : A$$
and the element
$$\ell(\ell(\ell(a, \mathtt{false}), n), m) : A$$
We can keep going.
A little bit of thinking reveals that $A$ is more or less two copies of lists of natural numbers, sharing a common empty list. I will leave it as an exercise to figure out why.

Induction-induction

An inductive-inductive definition also defines a type $A$ and simultaneously a type family $B : A \to \mathsf{Type}$:

$A$ is defined inductively
$B$ is defined inductively, and it may refer to $A$
Crucially, $A$ may refer to $B$.

It is important to understand the difference between induction-recursion and induction-induction. In induction-recursion we define $B$ by providing equations of the form
$$B(\mathsf{c}(\ldots)) = \cdots$$
where $\mathsf{c}(\ldots)$ is a constructor for $A$. In an inductive-inductive definition we define $B$ by providing constructors for forming the elements of $B$.

Let us reformulate our previous example as induction-induction. First we have the inductively given tpye $A$:

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

The type family $B$ is defined by the following constructors:

$\mathsf{Tru} : B(a)$
$\mathsf{Fal} : B(a)$
if $x : A$ and $y : B(x)$ then $\mathsf{Zer} : B(\ell(x,y))$
if $x : A$ and $y : B(x)$ and $z : B(\ell(x,y))$ then $\mathsf{Suc}(z) : B(\ell(x,y))$.

As you can see, we gave rules for generating the elements of $B$ which amount to saying that $B(a)$ is (isomoprhic to) the booleans, and $B(\ell(x,y))$ is (isomorphic to) the natural numbers.


The meaning of "set" in NP-complete problem Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more.

The traditional mathematical definition of a set does not allow duplicates; when multiplicities count, the object is called a multiset.

Are the sets in the NP-complete problems described by Garey and Johnson allowed to contain duplicates?

It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are forbidden, then there is a simple polynomial time reduction from the former to the latter showing that if the first version is NP-complete, so is the second one.


Can you explain this improvement to this frequency distribution algorithm? I came across the following in a text book:

  Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting.
  To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. By walking to the left of this point until the first the element is not k and then doing the same to the right, we can find
  this count in O(log n + c) time, where c is the number of occurrences of k. Even better, the number of instances of k can be found in O(log n) time by using binary search to look for the positions of both k − ε and k + ε (where ε is arbitrarily small) and then taking the difference of these positions.

The part I don't understand is the part I have emphasised in bold text - I can't understand how you might choose 'ε' and how you would know that the list even contains this 'ε'..

You don't really choose $\epsilon$. Rather, you (virtually) add $k-\epsilon$ and $k+\epsilon$ to your linear order at the correct spots, a feat which you accomplish by modifying your comparison function. Binary search requires you to answer queries of the form $x < y$. When looking for $k-\epsilon$ (or $k+\epsilon$), either $x$ or $y$ could be $k-\epsilon$ (or $k+\epsilon$), and so we have to extend the definition of the comparison function, as follows:
$$
k-\epsilon < y \text{ if } k \leq y \\
x < k-\epsilon \text{ if } x < k \\
k+\epsilon < y \text{ if } k < y \\
x < k+\epsilon \text{ if } x \leq k
$$
The comparison functions on the right are the original ones (with $x \leq y$ being shorthand for $x < y$ or $x = y$), and the ones on the left are the new ones.


Is $(^{1/2}) = \Omega(^{\sin(n)})$? As $-1 <\sin(n) < 1$, So $n^{\sin(n)}$ is bounded, but square root of $n$ tends to infinity. Is my logic correct? But from the other perspective, $1/n \leq n^{\sin(n)} \leq n$. I am confused.

First, let's unpack this. We say that $O(\sqrt{n}) = \Omega(n^{\sin n})$ if any function $f(n)$ which satisfies $f(n) = O(\sqrt{n})$ also satisfies $f(n) = \Omega(n^{\sin n})$.
In particular, if $O(\sqrt{n}) = \Omega(n^{\sin n})$ then $\sqrt{n} = \Omega(n^{\sin n})$. If $\sqrt{n} = \Omega(n^{\sin n})$ then according to the definition, there exist $C,N>0$ such that $\sqrt{n} \geq Cn^{\sin n}$ for all $n \geq N$. Let us assume that this is the case.
In what follows, I assume that the argument in $\sin n$ is measured in radians.
Since $2\pi$ is irrational, the sequence $n \bmod 2\pi$ is equidistributed in $[0,2\pi)$. In particular, there are infinitely many $n$ such that $n \bmod 2\pi \in (0.4\pi,0.6\pi)$, and so $\sin n \geq 0.95$. For each such $n \geq N$, we have
$$ \sqrt{n} \geq Cn^{\sin n} \geq Cn^{0.95} \Longrightarrow n \leq C^{1/0.45}.$$
Since there are infinitely many $n$ such that $\sin n \geq 0.95$, we can find one such $n$ which exceeds both $N$ and $C^{1/0.45}$, and so reach a contradiction. This shows that $\sqrt{n}$ is not $\Omega(n^{\sin n})$.