Backtracking for listing k elements Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.

Describe a back tracking algorithm for efficiently listing all k-element subsets of n items.

For n = 5 the 3 element subsets are (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5)

In particular, I am interesting in first describing the solution vector representation to use, and then how I would partition the work among construct-candidates, is-a-solution and process-solution functions.

Unfortunately, backtracking is not taught in many universities although it is a basic technique in algorithms and programming. You can backtrack using two methods: recursive or iterative. In the iterative, you use a stack. In the recursive version, you use the built-in memory stack by calling functions recursively.

A code that generates something similar to what you want is the following (it is left as an exercise to do exactly what you want.).

void backtrack(vector<int> v, int index, int max, int n) {

1)  v.push_back(index);
2)  if (v.size() == n) { print(&v); }
    else {
3)      for (int i = index + 1; i <= max; i++) {
4)          backtrack(v, i, max, n);
        }
    }

}

This is called from the main function as: backtrack(v, 1, 5, 3);  where v is a vector, and 1 is the initial element to be inserted in the vector.

You can implement your print as following:

void print(vector<int>* v) {
printf("( ");
for (int i = 0; i < v->size(); i++) {
    printf("%d ", v->at(i));
    if (i < v->size() - 1) { printf(", "); }
}
printf(") \n");
}

Note that the output of the program above is: (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5). -- Try to correct it. [Hint: use a for-loop in main]. Usually, a backtrack function has a a helper function (e.g. backtrack_helper). I haven't used a helper in here. But you can use it in your improved version.

Remark:
I added some comments in the backtrack version to show how I got this backtracking. In 1) I did the action that is supposed to be taken. In 2) I check whether I have reached a correct solution . In our case, a correct solution is when we have a vector of size n (3). If I dont reach the correct solution, I go to backtrack more. The for-loop is the most important thing in the program. I check the last element to be inserted in the vector (call it index). Then in the for-loop I call backtrack for all the neighbors of this element. These neighbors are the elements that can be inserted after index. These are called sometimes legal neighbors of index. -- It may sound weird a bet now. Let me know if you need more clarifications.


Worst-Case Complexity of Quantifiers in Thompson's Construction My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the length of the regex pattern.
Consider this pathological example: $a^*a^*ab$, which should match at least one $a$ followed by exactly one $b$. I'm going to refer to the compiled NFA as having three parts, with a "front part" representing the first $a^*$, a "middle part" representing the second $a^*$, and a "back part" representing $ab$.
The front and middle parts would look like this, with a simple $a$ symbol transition for $N(s)$:

The back part would look like two of these symbol transitions, one for $a$ then one for $b$:

Let's try to match $aaab$:

The compiled NFA starts in the start state.
Having two options due to the first Kleene star, it splits execution. It doesn't matter which state goes where, so let's just say state #1 takes the epsilon transition to move on to the middle part, and state #2 stays in the front part.
State #2 would match the first $a$, then split again. Let's say state #2 proceeds along the loop-back epsilon transition and stays in the front part, while a new state #3 moves on to the middle part. Now there are three states.
Meanwhile, state #1 – now in the middle part – also splits due to the second Kleene star, and does basically the same thing as state #2 did in the front part. Let's say state #1 moves on again to the back part, while a new state #4 goes into the Kleene star construction in the middle part, matches the first $a$, and in turn splits again into a state #5 that loops back within the second Kleene star construction, so state #4 can move on to the back part like state #1 did, except that state #4 has already matched the first $a$.

At this point, you can probably see what I'm getting at; the first Kleene star causes execution to split, in the worst case, $O(n)$ times, where $n$ is the length of the input, then the second Kleene star potentially causes each of those $O(n)$ splits to split $O(n)$ times, resulting in $O(n^2)$.
So there must be some way of pruning the possible states and avoiding $O(n^2)$ splits. An obvious pruning strategy would be to prune states if we've already visited the same node before in another state which had already consumed exactly the same amount of the input string. Keeping track of how much input we've consumed at each state is important since we cannot greedily consume either as much or as little as possible in the Kleene star constructions; in the example above, the whole input is only matched if the front and middle parts consume only the first two $a$'s between the two of them, so the back part can get the third $a$ and the $b$. But, this pruning strategy would result in $O(nk)$ space and time complexity, where $k$ is the length of the regex pattern, since there are $O(k)$ nodes in the NFA, and each node can have a unique state depending on how much of the length-$n$ input string it's consumed. I'm ok with $O(nk)$ running time, but I'm concerned about $O(nk)$ space complexity for large inputs in my application.
Is there some more genius pruning strategy that I'm not aware of? I don't have access to ACM, so I'm not able to read the original paper, and none of the articles of read about it go into enough detail to untangle this kind of situation.

The point of a finite automaton is that the number of possible states that it can be in is finite. Specifically, if a NFA has $n$ states, then at any point in the input string, you can be in at most $n$ states at the same time.
The first observation is that you can precompute $\epsilon$ transitions. Define $\mathbf{closure} : Q \rightarrow 2^Q$ to be a function that takes a state and returns the state which are reachable using zero or more $\epsilon$ transitions. Then from this, we can compute an "extended" transition function $\delta^{*} : Q \times \Sigma \rightarrow 2^Q$, which maps a state and an input symbol to the set of states that are reachable from it, then you can use this algorithm to recognise a string:

Given the start state $s$, set $W := \mathbf{closure}(s)$. (Again, this can be precomputed.)
For each input symbol $a$, set $W := \cup_{s \in W}\,\delta^{*}(w, a)$.
Accept if there is a final state in $W$.

This algorithm looks like it takes $O(k^2n)$ space in the worst case, namely, the space to represent $\delta^{*}$. And the inner loop operation, $\cup_{s \in W}\,\delta^{*}(w, a)$, looks like it should take $O(k^2)$ time in the worst case.
This isn't quite true in the word RAM model, however. Consider that the space needed to store a set of states can be measured in bits; since $k$ is known in advance, the sets like $W$ and the codomain of $\delta^{*}$ can be represented as a bit vector, and set union can be a logical or. So in the word RAM model, the inner loop will actually take $O\left(\frac{k^2}{\log k}\right)$ time in practice.
Having said that, as you correctly guessed, Thompson's construction is not ideal for this use case. It has many advantages (not the least of which is that the space is linear in the size of the input regular expression), but the efficiency of its "obvious" recogniser algorithm is not one of them. As you rightly suspected, it produces a lot of unnecessary states that we can get rid of.
One obvious point is that it's trivial to optimise common "leaf" cases. For example, Thompson's algorithm will turn $a^*$ into a NFA with 4 states, but it should be obvious that you "need" fewer than that, and the complexity of the construction for $E^*$ is only needed because $E$ may be more complex.
Following this reasoning, it is possible, without too much difficulty, to construct an NFA with the following properties:

The number of states is equal to the number of alphabet symbols in the original regular expression (in some formulations, plus one for the start state, but here we will use a set of start states). That is, $a^*a^*ab$ should require exactly 4 states.
There are no $\epsilon$ transitions.
Every transition into a state $s$ has the same label.

Property 1 gives an accurate bound on the number of states which is computable at parse time.
Property 3 means that you can label states with alphabet symbols instead of transitions. Together with property 2, the transition function $\delta$ doesn't need to consider input symbols.
We define a normal NFA (NNFA) to be a 6-tuple $(\Sigma,Q,\delta,I,F,A)$ where:

$\Sigma$ is the alphabet.
$Q$ is a set of states.
$\delta : Q \rightarrow 2^Q$ (or, alternatively, $\delta \subseteq Q \times Q$) is the transition function.
$I \subseteq Q$ is the set of initial states.
$F \subseteq Q$ is the set of final states.
$A : Q \rightarrow \Sigma$ is a function which assigns labels to states.

Then the inner loop of the recogniser algorithm is to set:
$$W := \left\{ s\,|\,w \in W, s \in \delta(w), A(s) = \alpha\right\}$$
This should give you a lot of ideas as to how to implement this in data structures. For example, consider representing $\delta$ as a bit matrix and $A$ as a map from $\Sigma$ to a bit vector, where $A(\alpha)$ is the set of states $q$ which have the label $\alpha$. Then the inner loop becomes a bunch of bit vector unions (i.e. logical or operations) with a final bit vector intersection (i.e. a logical and). In the word RAM model, this is extremely efficient.
As to how to construct a NNFA, it's worth trying to come up with the idea behind it yourself, now that you know that it's possible. As a hint, start with Thompson's construction, and create a new automaton where the "new" states are the $\mathbf{closure}$ of every state which has a terminal transition coming into it. You can then think about how you could compute that automaton without explicitly constructing Thompson's automaton to begin with.
Once you've tried it, the best explanation that I've seen is Chang's PhD thesis. But here's the amazing part: Chang then goes on to give a compressed representation for a NNFA which takes $O(k)$ space, with a construction algorithm that uses $O(k)$ auxiliary space and $O(r)$ time where $r$ is (in some sense) the "size" of the input regular expression.
That effectively answers your question. There is indeed an algorithm which recognises regular expressions, which stores the automaton in $O(k)$ space, where $k$ is linear in the size of the input regular expression, and which takes $O(nk)$ time to recognise a string.


NFA with exponential number of states when determinized How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know how to start. Any suggestions to put me on the right track?

The standard example is the language $L$ of all words over an alphabet $A$ of size $n$ that don't contain all the different letters. There is an NFA accepting $L$ with $n+1$ states (or $n$ states if you allow multiple starting states): first guess a letter $a$ which is missing, then go (with an $\epsilon$-move) to an accepting state with self-loops for all letters other than $A$.

Any DFA for $L$ requires at least $2^n$ states. This can be seen using the Myhill-Nerode theorem. Let $S_1,S_2$ be two different subsets of $A$, and $w(S_1),w(S_2)$ words which contain all and only the letters in $S_1,S_2$, respectively. Without loss of generality, suppose $a \in S_1 \setminus S_2$, and let $w = w(A-a)$. Then $w(S_1)w \notin L$ while $w(S_2)w \in L$.


Dynamic programming and probability - list of problems Does anyone have a list of problems where you have to combine dynamic programming  with probability?

You can use search on this site to find some examples: https://cs.stackexchange.com/search?q=%5Bdynamic-programming%5D+probability


Beta reduction order in Lambda calulus Will it be wrong to use g for reducing (λx.λy.x) first in step (2) instead of using to reduce λg?

Is there a rule against it?

You can do that, beta reduction can be applied at any point where an abstraction is immediately followed by application $((\lambda x. \cdots)t)$. In general, as you ovserved, there might be many redexes, i.e. many points where beta reduction can be applied.

However, note that sometimes we want to study what happens if we restrict ourselves to some reduction strategy. Essentially, a reduction strategy is a rule which chooses which redex to beta reduce when there are many. When doing that, there is a unique reduction sequence, a kind of unique execution run, for any term.

So, unless an exercise mandates the use of a specific reduction strategy, you are free to apply beta reduction at any point.

As a final remark, note that the choice of the redex can affect the termination of our reduction sequence. For instance, $(\lambda x.\ y)\Omega$ where $\Omega=(\lambda w.ww)(\lambda w.ww)$ can immediately reduce to $y$, or can loop indefinitely on reducing $\Omega$ to itself.

The Church-Rosser property (aka confluence, aka diamond property, mentioned above by xuq01) only ensures that, whenever we reduce a term $t$ with many beta reduction steps, possibly in two different ways leading to two terms $t_1,t_2$, there is a way to "reconcile" $t_1$ and $t_2$ and beta reduce those (in many steps) to a common form $t_f$.

This ensures that choosing the "wrong" beta redex does not compromise the reachability of the "intended" result (e.g. a normal form, if it exist). However, as seen in the example above, if we insist in selecting the "wrong" redex, it is possible that we get stuck into an infinite reduction sequence, when another one would lead to the intended result.


What is meant by the notation $L(...)$? I am currently studying about formal languages and automata.
I am trying to solve a problem but there is a notation whose meaning I'm not sure of.

I have a question to find out the relationship between two languages $L_1$ and $L_2$:

$L_1:$

$S \to aSa|bS|e$

$L_2 \to L((ab+ba)^*)$

My question is, does it mean that $L(ab+ba)$ is the set $\{ab, ba\}$?

I mean, $L(ab+ba) = L(ab)\cup L(ba)$

This link confirms my intuition that $L(R)$ where $R$ is a regular expressions simply means "the language produced by the regular expression $R$".

In that case, $ab \in L_2$ but $ab \notin L_1$

In case link is down:

Operators used in regular expressions include:

Union: If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression.
L(R1|R2) = L(R1) U L(R2).

Concatenation: If R1 and R2 are regular expressions, then R1R2 (also written as R1.R2) is also a regular expression.
L(R1R2) = L(R1) concatenated with L(R2).

Kleene closure: If R1 is a regular expression, then R1* (the Kleene closure of R1) is also a regular expression.
L(R1*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...


The most efficient way of finding/storing neighbourhood info during octree creation Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check.

Since that is causing a bottleneck in my program I am looking to optimise this stage by somehow assigning the neighbours during octree-creation stage.

I am building a 'depth-first' recursive octree, which means that I go to the deepest level for every node, before moving on to it's neighbour...

What would be the best way to do something like this?

EDIT: The definition of 'neighbours' is the following. A neighbour is each node of the same level/depth which shares a face with the current node. Nodes which only share an edge or vertex should not be considered as neighbours. The picture below provides more clarity...

I don't know if there is a way while constructing the oct tree.
But here is way after you created the tree, which runs in O(N), where N is the number of Nodes.
For each node there has to be a maximal comparison of 8*6+7 = 55.
This might can be reduced but this might be fast enough.

loops through all nodes breadth-first.
A neighbour of a child is a neighbour child of the parent or a child of a the parents neighbours.

The comparison if two points are neighbours is here distance(node_1,node_2) == SMALLEST.
I don't know how you compare it. Maybe you can insert your code.
You could caluclate for each level the Euclidian distance of the points if you have equally spaced cuboids
and compare them. That would be the fastest way.

when nothing works, you can just make a list for each of the 8 comparisons, sort them and keep the lowest one.

call function calc_neighbours(root_node) after you created the oct tree

class Node:
    Node **childs // array of size 8 and pointers to the child node pointers
    Node *parent
    Neighbours **neighbours

function calc_neighbours(root_node):
    queue = create_queue()
    queue.add(root_node)
    while (queue.isEmpty() == false)
    {
        parent_node = queue.pop()
        for (int i = 0; i < 8; i++) // for each child_cube
        {
            queue.push(parent_node->child[i])
            for (int j = 0; j < 8; j++) // for each neighbour child_cube
                 if (i != j && distance(parent_node->child[i],parent_node->child[j]) == SMALLEST)
                    // filter out those who share only vertex/edge
                    parent_node->child[i]->neighbours.add(parent_node->child[j])
        }
        if (parent_node != root_node)
        // root node has no neighbours, loops through all neighbours of the parent's neighbour's child
            for (int n = 0; n < parent_node->neighbours->size(); n++)
                for (int i = 0; i < 8; i++) // for each child_cube
                    for (int j = 0; j < 8; j++) // for each neighbour child_cube
                         if (distance(parent_node->child[i],parent_node->neighbours[n]->child[j]) == SMALLEST)
                            parent_node->child[i]->neighbours.add(parent_node->neighbours[n]->child[j])
    }


Machine Learning: What program will derive the underlying algorithm in this series? This is a machine learning question. Given this series of categorical data, what program will derive the underlying algorithm and predict what comes next in the series?

Here is the series:

B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, ...

Anyone with knowledge of computer science may quickly realize that this series is simply counting in binary with "A" substituted for "0" and "B" substituted for "1". This is true, but...

the program that predicts what comes next must do so only by manipulating the symbols given in the series. It must not use hard-coded knowledge of binary counting.

I realize many patter recognition algorithms are available but I haven't seen how any can solve this deceptively hard problem.

-Edit-

Based on the votes that this problem is insolvable, I've done some refactoring and posed the question another way, with more constraints, here:
What program will derive the underlying algorithm in these question-answer pairs (updated)?

Without any a priori knowledge, the problem is insoluble. There are infinitely many possible answers and you have no wat at all to say that one of them is preferable to any of the others. How can you possibly tell just by manipulating symbols that the sequence is "Counting in binary using A and B for 0 and 1" rather than "B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, BABB, BBAA, widgeon, 27, expunge" followed by a list of the squares of every third prime, number written in base-14 using Hebrew letters instead of the even digits?

Wait – how would you even know that there is a next element?


Direct and Associate Cache - Offset, Index, and Tag I have two questions:

An 8-kB (8192 bytes) direct-mapped cache has 16-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

A 16-kB (16384 bytes) 4-way set associative cache has 8-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

For offset, it's: tag bits = address bit length - exponent of index - exponent of offset, correct?

Then the Index for a direct mapped cache is the number of blocks in the cache, and the Tag bits are everything else, right?

How would I calculate these? Because I'm a little confused on an associated cache vs a direct-map cache.

An 8-kB (8192 bytes) direct-mapped cache has 16-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

Since a cache line is 16-byte long, it can be represented with $\log_2 16 = 4 \text{b}$, which is the number of bits required for the offset field.
The number of lines in the cache are $\frac{8\text{kB}}{16\text{B}} = 512$.
The index maps these entire lines; therefore, $\log_2 512 = 9\text{b}$ are required.
The tag field gets the rest, that is, $64-9-4=51\text{b}$.

A 16-kB (16384 bytes) 4-way set associative cache has 8-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

As before, $\log_2 8 = 3\text{b}$ for the offset field.
Since the cache is 4-way associative, the number of sets are $\frac{16\text{kB}}{4\cdot 8\text{B}}=512$, which, again, requires $9\text{b}$ for the index field.
Finally, the tag is $52$ bits long.


Merging $k$ sorted lists in $O(n\log k)$ time This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet).

Question: Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: use a min-heap for $k$-way merging.)

Solution: The straightforward solution is to pick the smallest of the top elements in each list, repeatedly. This takes $k − 1$ comparisons per element, in total $O(k · n)$.
As the hint suggests, the idea for the “improved” solution is to keep the smallest element from each list in a heap; each element is augmented with the index of the lists where it comes from. We can perform a DeleteMin on the heap to find and delete the smallest element and insert the next element from the corresponding list.
Analysis: It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So I understand everything that's going on here. I just have one little question about this part:

$$O(k+n\lg k)=O(n\lg k)$$

The solution states:

  It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So in my head I want to do something like this:

$$O(k+n(2\lg k))=O(k+n\lg k)=O(n\lg k)$$

Is this also correct since there are two instances of $O(n\lg k)$? Is the solution just skipping over that one part assuming it's trivial?

Yes, you are right.

$O(c \cdot f(n)) = O(f(n))$ for any constant $c$.

It may also be written (maybe even more clear) in the form
$$O(k) + O(n \lg k) + O(n \lg k) = O(n \lg k)$$


Primitive Recursion equipped with an evaluator function The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ ev(i,j) $ which computes the $ i $th primitive recursive function on input $ j $.

I was wondering what you can compute with primitive recursion equipped with $ ev $, which I will refer to as secondary recursive functions.

More formally,

any primitive recursive function is secondary recursive
secondary recursive functions are closed under composition and primitive recursion (just like primitive recursive functions)
$ ev $ is secondary recursive
$ ev $ indexes function such that computing the index of a projection, composition, or recursion is primitive recursive.

Note that in the above, $ev$ is still only computing primitive recursion.  Thus, secondary recursion always halts - $ ev $ always halts and the other ways of building secondary recursive functions can't turn halting functions into non-halting functions.

I've found that some "nice" examples of non-primitive-recursive functions are secondary recursive.

For example, for any fixed $ n $ , the function $ f_n(a,b) = a \uparrow^n b $ is primitive recursive.  Given arbitrary $ n $, we can compute the index of $f_n$ (with some work), then use $ ev $ to compute $ arrow(a,b,n) = a \uparrow^n b $ which is not primitive recursive (it can be used to compute the Ackermann function).

We can also further generalize this to $n$-ary recursion, with $1$-ary recursion being primitive recursion, and $(n+1)$-ary recursion being primitive recursion equipped with an function that evaluates $n$-ary recursive functions.  (Then we can generalize this even further, with $ \omega $-ary recursive functions which are the union of $n$-ary recursive functions for all $n$, $(\omega+1) $-ary recursion being primitive recursion equipped with a function that evaluates $\omega$-ary recursion etc. )

I have 2 questions:

Have these been studied?  Do they have a name?
Are there any "nice" examples of functions which are recursive but not secondary recursive?

A paper of Sylvain Schmitz, Complexity hierarchies beyond elementary, seems to tackle a similar question. While not necessarily defining your exact class (I haven't read the paper), it discusses classes of function between primitive recursive and recursive (as well as between elementary and primitive recursive).


Combination with a minimum number of elements in a fixed length subset I have been searching for long but unable to find a solution for this. My question is "Suppose you have n street lights(cannot be moved) and if you get any m from them then it should have atleast k working.Now in how many ways can this be done"

This seems to be a combination problem, but the problem here is "m" must be sequential.

Eg: 1 2 3 4 5 6 7 (Street lamps)
Let m=3
Then the valid sets are,
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

Whereas, 1 2 4 and so are invalid selections.

So every set must have atleast 2 working lights. I have figured how to find the minimum lamps required to satisfy the condition but how can I find the number of ways in it can be done ?

There should certainly some formula to do this but I am unable to find it.. :(

Eg: Let n=7,m=4,k=3. The minimum number of lights that must be working to satisfy the condition that "atleast 3 of any 4 lights must be working" is 5. It is if 23467 are working. But there are more ways in which it can be satisfied like if 23467,13457... We have 4 such combinations in all for the taken values of n,m,k. I want to know how can we generalize this?

Can be represented like this :
n => 1111111
1 Indicates light working and 0 indicated not working.
0111110
0111011
1011101
1011110

Hope the question is clear.

For each particular $m,k$ you can get a recurrence formula and solve it. Perhaps this way you can obtain a general formula. Here is how to find the recurrence formula:

The language of all valid sequence is regular. Construct a DFA (deterministic finite automaton) that accepts the language. (An optimization: construct a "partial" DFA in which sometimes there is no outgoing edge labeled $0$.)
Suppose the transition matrix is $A$, the initial state is $s$, and the accepting states are $F$. Then the number of sequences of length $n$ is $\alpha_n = 1_F A^n 1_s$.
Compute the Jordan normal form of $A$, decompose $1_F,1_s$ according to the Jordan basis, and so obtain a formula for $\alpha_n$.

Instead of using DFAs, you can use generating functions, which really amounts to the same.

Here is a very simple example: $m = 2$ and $k = 1$. The regular language here is all words not containing $00$, that is $1^*(10)^*1^*$. The minimal partial DFA has two states $s_0,s_1$ which correspond to the two possible "histories" (we can assume that the part of the sequence before it actually starts consists entirely of 1s) - in general there will be $2^{m-1}$ states (if $k < m-1$ then actually less, since some of them would be invalid). The transitions are: On $0$, transition from $s_1$ to $s_0$; On $1$, transition from $s_0,s_1$ to $s_1$. The starting state is $s_1$. All states are accepting (this will always be the case with a minimal partial DFA). The transition matrix is
$$ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}. $$
Therefore
$$ \alpha_n = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$
The matrix $A$ has two eigenvalues $(1 \pm \sqrt{5})/2$, and furthermore
$$ A = \begin{pmatrix} 1 & 1 \\ \frac{1-\sqrt{5}}{2} & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} & -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} & \frac{\sqrt{5}}{5} \end{pmatrix}. $$
Thus
$$
\begin{align*}
\alpha_n &= \begin{pmatrix} \frac{3-\sqrt{5}}{2} & \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &=
\frac{5-3\sqrt{5}}{10} \left( \frac{1-\sqrt{5}}{2} \right)^n +
\frac{5+3\sqrt{5}}{10} \left( \frac{1+\sqrt{5}}{2} \right)^n.
\end{align*}
$$
The first few numbers (starting with $\alpha_0$) are $1,2,3,5,8,13,\ldots$, and we recognize the Fibonacci sequence: $\alpha_n = F_{n+2}$.

An alternative to following these steps is noticing that $\alpha_n$ is always defined by a recurrence relation of length at most $2^{m-1}$. So for general $m,k$, all you have to do is calculate enough of the sequence $\alpha_n$ to determine the coefficients: you need to calculate $\alpha_0,\ldots,\alpha_{2^m-1}$, which will give you $2^{m-1}$ equations.

Here is how to do it for $(m,k) = (2,1)$: $\alpha = 1,2,3,5$. If $\alpha_n = c_1 \alpha_{n-1} + c_2 \alpha_{n-2}$ then $3 = 2c_1 + c_2$ and $5 = 3c_1 + 2c_2$. We deduce that $c_1 = c_2 = 1$ and so the recurrence is $\alpha_n = \alpha_{n-1} + \alpha_{n-2}$.

Having recovered the recurrence relation, we solve it as usual. It will usually be the case that all roots of the characteristic polynomial are distinct, and that the asymptotics of the sequence are given by the largest root (though in principle it depends on the actual sequence).


Hueristic Algorithm to find the maximum clique Let the algorithm be defined as follows:

Consider the following heuristic algorithm for finding the maximum size clique
in a graph. (1). Delete from the graph a vertex that is not connected
to every other vertex. (2). Repeat (1) until the remaining graph is a clique.

Now, how do I show that this algorithm does not give a solution which is within constant times of the optimal solution?
I was reading about heuristic algorithms when I came across this problem. Any sort of input is appreciated.

Consider a graph which is the disjoint union of $K_i$ and $K_1$, the isolated vertex.

Let the order of selection of vertices be such that the isolated vertex is last.

Then your heuristic outputs solution 1 for any $i \in \mathbb{N}$.


What is the difference between a R-tree and a BVH? I've just read about R-Trees:

  The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

This seems to be a Bounding Volume Hierarchy (BVH) with axis-aligned bounding boxes (AABBs):

  A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree.

  [...]

  One of the most commonly used bounding volumes is an axis-aligned minimum bounding box.

Both allow overlapping nodes.

I've learned about BVHs in a Computer Graphics lecture and about R-trees by a professor who is mainly working on databases. So it might be that different communities developed the same datastructure independently.

Is there any difference between R-Trees and BVHs?

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful.

However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely important to decide what kind of bounding volumes to use. The bounding volume can be any geometric shape: circle, hexagon, square, trangle or rectangle. It is important to keep this bounding volume very simple (we want it to be easy to store, rather than a complicated geometrical shape) and easy to fit other objects in (we don't want to waste a lot of free space in the bounding volume, as it can cause exhaustive search.

Quote from [1],

  Below, I will first explain what a bounding-volume hierarchy is and
  how it is used. After that, I will explain what issues have to be
  addressed when designing a bounding-volume hierarchy. I will then
  focus on a particular class of bounding volume hierarchies, namely
  R-trees, and give an overview of our results on Rtrees.

R-tree is a class of BVH data structures that uses rectangles as bounding-volume. Rectangles are easy to store and they can cover other shapes easily. It is noted that R-tree is not the only class of BVH and there are other BVHs proposed using different shapes. Even among R-trees, there is a variety.

This data structure is important for different communities: computer graphics, computational geometry, database and others. All of them need to deal with situations where they need to query a set of geometrical objects (or vectors).

[1] Herman Johannes Haverkort, Results on geometric networks and data structures, 2004.


Order-preserving update of a sublist of a list of mutable objects in sublinear time Description

Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to "B", my derived list looks like ["B"].  Next, if I change my source list's "d" to "D", the derived list should look like ["B","D"].

Is it possible to make the insertions and removals in the derived list, while maintaining order, in faster than $O(n)$ time, $n$ being the size of the list?

Finally, I'd like to be able to know the index of where the insertion or removal takes place in the derived list in faster than $O(n)$ time.

An idea that doesn't work

I could keep the derived list in a tree, sorted by the source index. This way, when I needed to insert my item in derived tree-list, it would take $O(log n)$.  However, I would not be able to know that index of that insertion without walking the entire tree.

Thanks for your help!

Problem Statement

Let $S$ be an ordered list
Let $Si.filterProperty$ be $true$ for some elements in $S$
Let $F$ be an ordered list of all elements in $S$ where $Si.filterProperty$ is true

Let $T(i)$ be a function that:

Sets $Si.filterProperty$ to $true$
Inserts $Si$ into $F$, ordered in the same fashion as $S$
Returns the index in $F$ where $Si$ was inserted

Can $T$ and its side effects be faster than $O(n)$?

Any list-like data structures can be used within these constraints:

Insertion and side effects of insertion are faster than $O(n)$
We must know the index of the newly inserted item into $F$

At the time of writing I was not absolutely sure what the problem
was. This lead to a more general second answer. See details in
discussion at the end of this answer.

Apparently, the "idea that does not work" does not work because you do
not know the index of an element $S_i$ in $F$ organized as a tree.

This is what is addressed here. The problem is restated for clarity, as your statement of it is a bit hard to follow.

Restatement of the problem:

Given a set $S$ with an order relation, maintain an ordered list $F$
where elements of $S$ can be inserted or removed, and such that the
index of an element in $F$ is returned when the element is inserted.

Actually, the solution will do more, as it is possible to access any
element of $F$ given its index, or to retrieve the index given an
element of $F$. All operations are in time $\log n$.

Solution:

You keep the ordered derived list $F$ in a self-balancing binary
tree. I checked with AVL trees, but other types (such as red-black
trees) should work as well. In each node $N$ of the tree you keep a
count $\text{weight}(N)$ of the number of elements of $F$ in the subtree
rooted in $N$, node $N$ included.

This can be done by updating weight counts as you walk down from the
root of the AVL tree for $F$ to reach the place for the insertion or deletion.
Then, during the retracing phase that rebalances the tree, when
needed, you also update the weight counts according to the
rebalancing.  That only add constant cost to each elementary step,
thus does not change the $\log n$ time complexity of the algorithm.

Hence it is easy to use this weight to compute in $\log n$ time the
index of an element of the list $F$ when accessing it, either on the
way down from the AVL tree root, or by walking up to the root when
accessing the element directly.

The index is computed on the fly by adding the weights of all the immediate
siblings on the left of the path from the AVL tree root to the
concerned element of $F$.

Conversely, it is easy to find in $\log n$ time an element of $F$ from
its (left to right) index by walking down from the root and leaving
enough elements on the left.

Computing the index of $S_i$ in $F$ using weights:

Recall that the weight of a node $N$ is the number of nodes in the subtree rooted at $N$, node $N$ included.

Computing the index of $S_i$ from the weights in the tree is precisely
done as follows: you simply do a search for $S_i$ in the standard way of
binary search trees, with a modification to compute the index. Below
is a pseudo-code recursive version, adapted from the searching algorithm in
wikipedia. It raises an exception if $S_i$ is not in the AVL tree, and
the index count start at 0 for the first element. To have the count start at 1, the first return statement should be return node.left.weight+1.

function Find-recursive(S_i, node):  // call initially with node = root
    if node = Null then
        raise Key_Not_Found
    else if node.key = S_i then
        if node.left = Null then return 0
        else return node.left.weight
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        if node.left = Null then return Find-recursive(key, node.right)+1
        else return Find-recursive(key, node.right)+node.left.weight+1

When the path from the root goes to the right daughter, that means
that all nodes in the left daugther subtree, plus the current node, precede
$S_i$, and have to be added to whatever other predecessors will be
found while searching in the right daughter subtree.

I do not give here the modifications of the insertion and deletion code necessary to update the weight count, as this is a bit too long for an answer here, and not so hard to do.

About the question, and the two proposed answers

The precise specification of the problem took some time to agree upon.

This first answer to the question was written on the basis of an
initial specification that did not mention explicitly that the source list $S$
could be modified dynamically, by insertion or deletion, thus possibly
inducing a similar modification in the filtered list $F$.

The elements of list $S$ are mutable objects and have a filter-property
$P_F$ that may be true or false depending on operations performed on
an element. The purpose of the question is to maintain a sublist $F$ of
elements $s\in S$ such that $P_F(s)$, similarly ordered, such that the
rank in $F$ of an element $s\in S$ is known when it in inserted in $F$ due to
a mutation.

I assume in this first answer here that the list $S$ is constant,
except for changes to its mutable elements. Thus on may see the list
$S$ as a set (of list elements), totally ordered by the order of the
list, and that relative order of two elements can be checked in
constant time $O(1)$, for example by attaching its $S$-list rank to
each element.

In a much later comment to this answer, the author of the question
made it clear that he also wanted to be able to modify the list $S$
with insertion or deletion of elements. This more complex question is
addressed  separately in a second answer.

Why keep both answers? The first algorithm here is slightly more
efficient as all operations can be performed in time $O(\log|F|)$,
while the more general algorithm (second answer) requires time
$O(\log|S|)$. With a constant ratio $|F|/|S|$, the difference is only
an additive constant $\log|S|-\log|F|$. However this constant is to be
compared to a logarithmic complexity $\log|F|$, which may not be very
large itself. And this complexity is that of elementary operations on
a data structure, to be repeated often in larger algorithms. So this
apparently negligible difference may have a measurable impact on
performance of a larger algorithm using the structure.

To see it numerically, assume that $|S|=256$ and $|F|=16$. Then
$\log|S|=8$ and $\log|F|=4$, which give a performance ratio of $2$,
to which one should add that the structure of the more general
algorithm may be more costly to maintain.


How can union-find algorithm be used with "real" data In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described:

  The input is a sequence of pairs of integers, where each integer
  represents an object of some type and we are to interpret the pair p q
  as meaning “p is connected to q.” We assume that “is connected to” is
  an equivalence relation, which means that it is

  Reflexive : p is
  connected to p.
  Symmetric : If p is connected to q, then q is
  connected to p.
  Transitive : If p is connected to q and q is
  connected to r, then p is connected to r.

And it has one simple implementation called quick-find:

  One approach is to maintain the invariant that p and q are connected
  if and only if id[p] is equal to id[q]. In other words, all sites in a
  component must have the same value in id[].This method is called
  quick-find because find(p) just returns id[p], which immediately
  implies that connected(p, q) reduces to just the test id[p] == id[q]
  and returns true if and only if p and q are in the same component...To
  combine the two components into one, we have to make all of the id[]
  entries corresponding to both sets of sites the same value, as shown
  in the example at right.

My question is how can this be used for real objects? It works for integers, but what if I need to know whether the object A is connected to the object B, not if 3 is connected to 5? One solution I can think of is to have an array of objects where each object's index in the array corresponds to the index of the array used for connectivity. For example:

   1   2   3   4   5
[ { } { } {A} { } {B} ]   <---- real data

   1   2   3   4   5
[  1   2   3   4   3 ]    <---- connections (3 and 5 have the same group id 3)

Is that how it's applied?

Short answer: indirection.

For instance, each object could have a field that contains an index into the id array.

Or, you could use pointers.  Standard union-find data structures often use pointers instead of integers/indices/arrays.  Thus, each object has a pointer to another object in the same equivalence class.  See, e.g., https://en.wikipedia.org/wiki/Disjoint-set_data_structure or other standard presentations of union-find data structures.


Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it I am reading the proof of Theorem 3.21 in Sipser's textbook.

Theorem 3.21 A language is a Turing Recognizable iff some enumerator enumerates it.

First direction (<==).
Given an Enumerator E that enumerates language B, then we want to construct a TM M s. t. M that recognize language B. In order to do that, we do the following:
M="On input string x

Run E and compare each printed string with x
If x ever appears in the output of E, accept."

Given the following fact:

A TM M accepts input w if a sequence of configurations $C_1, C_2, ..., C_k$ exists s. t. $C_1$ is the starting configuration, $C_2$ to $C_{k-1}$ is the process configuration and $C_k$ is the accepting configuration.

My question: It is not clear how E accepts? e.g. What it does from my point of view is: It runs E without any input, if ever E printed out an arbitrary string, let's call it r, then if r==x, then we accept. I thought that we should do some processing like with given input x, then we should do some computation (moving from configuration to another) until we get to some arbitrary string that should be the output of the accepting state.
Note that I read all related answers to this question, but it didn't cover my question. For example: this and this.

The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too.
I drew something maybe it can help to have some intuition.


Shortest Path in a Directed Acyclic Graph with two types of costs I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$. I am also given two nodes in $G$, node $s$ and node $t$.
The goal is to find a path from $s$ to $t$ that minimizes the following cost: $$\sum_e w(e) + \max_e \{p(e)\},$$ where the sum and maximum are taken over all edges of the path.
Standard dynamic programming methods show that this problem is solvable in $O(E^2)$ time. Is there a more efficient way to solve it? Ideally, an $O(E\cdot \operatorname{polylog}(E,V))$ algorithm would be nice.

This is the $O(E^2)$ solution I found using dynamic programming, if it'll help.
First, order all costs $p(e)$ in an ascending order. This takes $O(E\log(E))$ time.
Second, define the state space consisting of states $(x,i)$ where $x$ is a node in the graph and $i\in \{1,2,...,|E|\}$. It represents "We are in node $x$, and the highest edge weight $p(e)$ we have seen so far is the $i$-th largest".
Let $V(x,i)$ be the length of the shortest path (in the classical sense) from $s$ to $x$, where the highest $p(e)$ encountered was the $i$-th largest. It's easy to compute $V(x,i)$ given $V(y,j)$ for any predecessor $y$ of $x$ and any $j \in \{1,...,|E|\}$ (there are two cases to consider - the edge $y\to x$ is has the $j$-th largest weight, or it does not).
At every state $(x,i)$, this computation finds the minimum of about $\deg(x)$ values. Thus the complexity is $$O(E) \cdot \sum_{x\in V} \deg(x) = O(E^2),$$ as each node is associated to $|E|$ different states.

This answer is mostly based on my earlier comments.
It is unlikely that there is an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for all graphs. It is still possible that there are faster algorithms for dense graphs ($E = \Omega(V^2)$) or somehow dense graphs ($E = \Theta(V^\alpha)$ for some $\alpha > 1$), but an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for sparse graphs ($E = O(V)$) would contradict so called $k$-cycle hypothesis
(you can check this paper and this paper for more details on the statement and its applications to lower bounds for dynamic shortest path and other graph problems).
The reduction
I prefer to state the $k$-cycle hypothesis in the following way, which is equivalent to the way it is usually stated (for more details, see the last section):

For any $\varepsilon > 0$, there is a positive integer $k$, such that there is no $O(|E|^{2 - \varepsilon})$ algorithm for checking whether there is a closed walk of length exactly $k$ in the given directed graph.

Let's reduce the problem of finding a closed walk of length $k$ in a given directed graph $G(V,E)$ to the problem in question for a slighty larger graph. Construct a new graph $H$ ($H$ will be a DAG), whose vertex set consists of a source vertex $s$, a sink vertex $t$ and vertices $(v, \ell)$ for each $v \in V, \ell \in [1, k + 1]$ ($k + 1$ layers, each being a copy of $V$).
Each edge $u \to v$ of the original graph splits into $k$ edges in $H$: $(u, \ell) \to (v, \ell + 1)$ for each $\ell \in [1, k]$, with each of those edges having $w$ and $p$ parameters set to $0$. Also, there will be $|V|$ edges from the source to the first layer ($s \to (v, 1)$ with parameters $w := v$ and $p := 3|V| - 2v$ for each $v \in V$; here I assume that vertices of $G$ are numbered from $0$ to $|V| - 1$). Similarly, there will be $|V|$ edges from the last layer to $t$ ($(v, k + 1) \to t$ with $w := v$, $p := 3|V| - 2v$).
Clearly, $H$ has $(k+1)|V| + 2$ vertices and $2|V| + k|E|$ edges.
Now, each $s \to t$ path $s \to (v_1, 1) \to (v_2, 2) \to \ldots (v_{k + 1}, k + 1) \to t$ in $H$ corresponds to a walk of length $k$ in the original graph ($G$). The corresponding walk is closed if and only if $v_1 = v_{k + 1}$. The main idea is that we have chosen the parameters $w$ and $p$ to ensure that paths with $v_1 = v_{k + 1}$ have the smallest possible cost.
Indeed, the cost of $s \to (v_1, 1) \to \ldots \to (v_{k + 1}, k + 1) \to t$ path in $H$ is $v_1 + v_{k + 1}  + \max(3|V| - 2v_1, 3|V| - 2v_{k+1}) = v_1 + v_{k + 1} + 3|V| - \min(v_1, v_{k + 1}) = 3|V| + |v_1 - v_{k + 1}|$. Hence, the shortest $s \to t$ path in $H$ has cost $3|V|$ if and only if the original graph $G$ contained a closed $k$-walk. Therefore, under k-cycle hypothesis, there is no $O(|E|^{2 - \varepsilon})$ algorithm for problem in question.
Can we do better for dense graphs?
Honestly, I don't know. Proving lower bounds for dense graphs seems to be difficult, because the problem is strictly simpler that dynamic shortest paths. Hence, the only
simple "vector of attack" is to try using the same methods that are used for dense graphs and hope that they will work even for the simpler problem. Maybe future answerers will be more succesful here?
As for faster algoritms, an existence of $O(VE)$ algorithm sounds plausible. The only thing that I managed to come up with is the following algorithm, whose complexity is a bit hard to estimate, but I suspect that it still should take $\Omega(E^2)$ time in the worst case:

Find some shortest ($s \to t$)-path in the original graph with respect to sum of $w$'s, breaking ties by minimizing the maximum of $p$'s (it is possible to do this by dynamic programming in $O(|E|)$ time). Let's say that the largest value of $p$ for edges on the chosen path is $P$. Then, all edges $e$ with $p_e \geqslant P$ can't appear in a path with a smaller cost (because otherwise the chosen path was not shortest with respect to sum of $w$'s). Therefore, we can delete all such edges and repeat the process.

Why did I choose an uncommon statement of k-cycle hypothesis?
Usually, it is stated in the terms of finding a simple cycle of length $k$, but for fixed $k$ finding a simple cycle can be reduced to finding a closed walk in (larger) graph by known techniques like color coding. All these techniques require blow up the size of the graph exponentially with respect to $k$ (otherwise we could solve Hamiltonian Cycle in subexponential time), but we can handle this, because $k$ is fixed and small.
Intuitively speaking, for small $k$, the "main problem", asymptotically speaking, is not ensuring that all vertices of the cycle are different, but remembering where the cycle started.
Because the problems are equivalent, I chose the one which is easier to work with. Moreover, apart from having a theoretical reduction, we also have a practical reduction now. For example, if we assume that there is no way to check whether a graph with $10^6$ edges has a closed walk of length $k = 6$ in under $10$ minutes on a normal computer (I would say, that this is a huge understatement, considering the large constant factors of graph searches; though I would be very positively surprised to be wrong), then there is no way to solve the problem in question for graphs with $10^6 / (k + 2) = 1.25 \cdot 10^5$ edges in under $10$ minutes, e.t.c. The point is, that the constant factors involved in the reduction are reasonably small.


Why we can't create a binomial heap in max-heap format? Why we can't create a binomial heap in max-heap format instead of min-heap format?

Why do you say that we cannot create a binomial max-heap?
Given any min-heap implementation you can always create its max version (and vice-versa).
An easy "black-box" way to see that this is true is considering what happens when all operations involving a key $k$ are actually performed on the key $-k$ instead.
That is, instead of inserting $k$ we insert $-k$; instead of deleting $k$ we delete $-k$; when we need to return the minimum key $k$, we return $-k$; etc...


Optimal generalized bisection method Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions:

$x$ is unique.
Given any $t \in [a,b]$ I can check, at some fixed computational cost, whether $t>x$. Let's call this operation $C(t)$.

Let $\epsilon>0$ be some small number. I'm interested in efficient algorithms to find an interval $I$, containing $x$, with length $<\epsilon$. The bisection method begins by using $C((a+b)/2), $ halving $[a,b]$, and repeating the process
 over $\log_2 \left((b-a)/\epsilon \right)$ times. I was wondering if there are more efficient modifications to it, such as breaking the interval into 3 or 4 subintervals at each iteration. Any other efficient alternative is also welcome. Thank you!

P.S. One can assume that $x$ is distributed uniformly in $[a,b]$, and that this process needs to be done many times for different $x$s.

Take any policy that you like. It will consist in a number of calls to $C$ during which you will reduce the size of the incertainty of the location of $x$.

Whatever rule you use, you can't beat dichotomy, because if you split in unequal subintervals, you can always end-up in the longest, which is longer than the half.

This also holds in the average sense. Assume a split in relative sizes $\alpha$ and $1-\alpha$, which will be performed with these probabilities. The expectation of the relative length after a division is $\alpha^2+(1-\alpha)^2\ge1/2$. The minimum is reached for $\alpha=1/2$.

You might only improve on this result when $x$ is not uniformly distributed and you have some information about this distribution, such as the histogram of frequencies. (In such a case, the optimal rule is probably to split in equiprobable subintervals.)


Are constituency grammars and dependency grammars two different types of context free grammars? From http://en.wikipedia.org/wiki/Parse_tree

A concrete syntax tree or parse tree or parsing tree[1] or derivation
tree is an ordered, rooted tree that represents the syntactic
structure of a string according to some context-free grammar.
Parse
trees are usually constructed according to one of two competing
relations, either in terms of the constituency relation of
constituency grammars (= phrase structure grammars) or in terms of the
dependency relation of dependency grammars.

Are constituency grammars and   dependency grammars two different
types of context free grammars?

I went through the wikipedia articles for constituency grammars and
for dependency grammars, but they seem to discuss only for natural
languages.
From the perspective of formal language and grammars, is it correct
that constituency grammars and   dependency grammars seem to be
about semantics, which is not just syntax/formal any more?

Thanks.

Concrete syntax trees and derivation trees exist for many types of
grammars (e.g. tree adjoining grammars, TAG). They happen to be
identical (up to labeling) in the case of CF grammars, but this is not
always the case, for example for TAG. (there are technical errors or
imprecisions in Wikipedia).

The derivation tree expresses how the rules are to be applied to
obtain the derived string. The derived tree (or concrete syntax)
associate a tree structure to the generated string, which may not be
context free.

Constituency grammars is a name often used by linguists to refer to
what we call Context-Free Grammar.  This is intended to contrast them
with Dependency Grammars based on a linguistic concept of dependency
used by linguists.

The idea of constituency is a classic idea in formal systems: terms
are formed with subterms. So the parse tree (very approximately) may
be seen as a term of an abstract algebra, and the semantics of the
whole is a composition of the semantics of the parts, the constituents
(I insist that I am simplifying a lot). While parse trees are concrete
syntax trees, the idea of abstract syntax trees (AST) was to emphasize
in programming languages the algebraic term structure to better
organize compilers and formal semantics.

Nevertheless, constituency is a syntactic concept, a very common one.

It has been extended to formalisms that consider discontinuous
constituents (or multi-parts constituents), such as TAG and Linear
Context-Free Rewriting Systems (LCFRS), which are strictly more
powerful than CF grammars.

As far as I understand, the idea of dependency is
related to lexicalized grammars (which also exists for extensions of
CF grammars).

The idea of a lexicalized grammar is that every rule instance used in
a derivation must be associated with a terminal of the generated
string (usually a single one). As is well known, every CF language has
a lexicalized CF grammar: you just put it in Greibach normal
form. Actually, the research of Sheila Greibach was probably motivated
by natural language considerations (she was working in the NL group of
Anthony Oettinger at Harvard). This concept of lexicalisation
comes from some natural language (NL) theories that consider that
construction of sentences is lexicon driven.

So far, we are still in the CF realm.

Dependency Grammar (DG), as much as I understand it as I am no specialist,
organizes the tree structure around the idea that each node of the
syntax tree is associated with a terminal (lexical element), as in
lexicalized grammar, but in such a way that it "controls" (dominates in
the tree structure) some part of the sentence, of which it is supposed
to be the central element (the exact term is "head"). So the verb will
be the head of a sentence, and the noun the head of the noun part of
the sentence, etc., according to some linguistic theory the
linguist is developing to organize language structure..

It is quite characteristic that the wikipedia article on Dependency
Grammars does not propose a formal definition of the concept. My
feeling from a quick glance at the literature is that it is mostly a
linguistic concept that can be formally dressed in different ways,
without a standard reference one. There are, however, some formal
definitions, for example in Dependency Grammars and Context-Free
Grammars, by Steven Abney (unpublished, 1994). I have also seen
contradictory statements regarding the power of DG, but it apparently
at best weakly equivalent to CFG. Specific algorithms have been
developed for dependency parsing, that seems to have interest for
linguists.

A dissertation (for sale) may contain interesting material: Dependency
Structures and Lexicalized Grammars: An Algebraic Approach*, Marco
Kuhlmann, Springer 2010. Slides about it are available.

Closely related to Dependency Grammar are Link Grammars, formally
defined, which also seem to have been designed for their parsing
properties, though advantages over CF grammars seem disputed.
Link Grammars are weakly equivalent to CF grammars, according to their
creators, Daniel Sleator and Davy Temperley.

But Dependency Grammars, or Link Grammars, though they may define the
same languages as all or part of the CF grammars, are not CF grammars,
and do not define the same structures for the strings.

It is worth noting also the Head Grammars, which are non-CF
constituency grammar, though they emphasize the concept of head more
often encountered with the dependency analysis of language. Head
grammars are LCFRS.

I believe semantics considerations enter the concept of Dependency
Grammars, but there in no clearcut limit between syntax and semantics
in Natural Language.

Constituency grammars are often just our good old, syntactic, formally
defined, context-free grammars, though it has been entended to more complex structures for constituants.


Name for class of algorithms preserving accuracy/confidence I am considering the following class of algorithms:

The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input.

The answer of procedure $f$ (we may assume it is boolean) may be incorrect with probability at most $p<1/3$.
The error of different calls to $f$ are independent
(thus we may increase the confidence of the result by repeatedly calling $f$ with the same argument and taking majority).

The algorithm  can call multiple times $f$ with any values.

We request that whatever the bound on error probability $p$ (unknown to the algorithm), the algorithm itselft must return its correct answer with error probability at most $p$.

The question is:
Is there any standard name for that class of 'confidence-preserving' algorithms?

For the sake of illustration, if we want to find the maximum of $3$ items and only have access to the items through some probabilistic oracle $f$ for comparing any pair of items, we can compare each pair $3$ times and take majority vote. The probability that each pair is ordered incorrectly is at most $3p^2$, hence the probability that we do not deduce the maximum correctly is at most $9p^2$. This is less than $p$ so the algorithm belongs to our class.

I'm not familiar with any standard name for this type of algorithm.  Go ahead and write your research paper and define a class with a name of your own choice (confidence-preserving seems like a quite good name to me).


Processes and Segmentation The following problem was on my final and in Gate 2006, but I don't understand how to solve it:

Different methods of memory management have different overheads:

The paging method for memory management uses two-level paging, and its storage overhead is $P$.
The storage overhead for the segmentation method is $S$.
The storage overhead for the segmentation and paging method is $T$.

  What is the relation among the overheads in the concurrent execution of the processes below?

  (a) $P < S < T \hspace{2em}$
  (b) $S < P < T\hspace{2em}$
  (c) $S < T < P\hspace{2em}$
  (d) $T < S < P$

Process    Total Size (in KB)    Number of segments
 P1              195                    4
 P2              254                    5
 P3               45                    3
 P4              364                    8

The page size is 1 KB.
The size of an entry in the page table is 4 bytes.
The size of an entry in the segment table is 8 bytes.
The maximum size of a segment is 256 KB.

I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page_count * 4 bytes for paging, S + segment_count * 8 bytes for segmentation, and T + segment_count * 8 bytes + page_count * 4 bytes for segmentation and paging.

(The inclusion of a maximum segment size is confusing since insufficient information is provided to determine if any of the 8 segments in process P4 are larger than 256 KB, though at most one segment can be.  Since the mean segment size is significantly less than the maximum allowed size, I just assume that no segment needs to use two segment table entries.)

It might help clarify the equations to substitute A < B < C with A = B + k1 = C + k1 + k2 (where k1 and k2 are greater than zero).  It should then be straightforward to determine what values of k1 and k2 are needed for equality and so derive the conditions under which each memory management method has greater overhead (with negative values for k1 or k2, of course, being impossible).


Approximation algorithms for an instance of the Monotone circuit satisfiability I have the following problem. Given a below boolean formula (of the type explained below) containing $n$ literals and two parameter $k$ and $l$, come up with a satisfying assignment of literals such that no more than $k$ of them are set to true. ($l$ will be explained below.)
An example boolean formula with 4 literals is as follows: $ (x_1 \lor (x_2 \land x_4)) \land (x_2 \lor (x_3 \land x_1)) \land (x_3 \lor (x_4 \land x_1)) \land (x_4 \lor (x_3 \land x_2)) $. Some properties of the kind of formulae I am dealing with:

The number of outermost clauses (connected via AND) is same as the number of literals.
There is a restriction on size of the innermost AND clauses, they can have at most $l$ literals. For example $l=2$ in the example above.

I did some literature search to realize that this is called as the "Monotone circuit satisfiability" problem in the complexity parameterization literature. My interest in the problem is largely practical, so I am looking for the best approximation algorithm known for the above problem. Any help / suggestions are much appreciated.

If this is a practical problem, rather than an approximation algorithm, I suggest using an off-the-shelf SAT solver.  There are standard ways to encode the constraint that at most $k$ variables are set to true, using an at-most-$k$-out-of-$n$ constraint.  For instance, Z3 has good support for this kind of constraint.
My impression is that approximation algorithms for SAT-like problems tend to perform very poorly.


Probabilities, Unigram and Bigram Assume that we have these bigram and unigram data:( Note: not a real data)
bigram:

#a(start with a) =21
bc= 42
cf= 32
de= 64
e#= 23

unigram:

# 43

a= 84

b=123

c=142

f=161

d=150

e=170

what is the probability of generating a word like "abcfde"?
I think for having a word starts with a the probability is 21/43. How about bc? is it like bc/b?

Augment the string "abcde" with # as start and end markers to get #abcde#. Now, as @Yuval Filmus pointed out,  we need to make some assumption about the kind of model that generates this data. Because we have both unigram and bigram counts, we can assume a bigram model. In a bigram (character) model, we find the probability of a word by multiplying conditional probabilities of successive pairs of characters, so:

$\Pr[\#abcde\#] = \Pr(a|\#)*\Pr(b|a)*\Pr(c|b)*\Pr(d|c)*\Pr(e|d)*\Pr(\#|e) $

To find the conditional probability of a character $c_2$ given its preceding character $c_1$, $\Pr(c_2|c_1)$, we divide the number of occurrences of the bigram $c_1c_2$ by the number of occurrences of the unigram $c_1$.

So, for example $\Pr(e|d) = count(de)/count(d) = 64/150$


Why do Benes networks form bipartite graphs when you build a constraint graph for them? I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the intuition that we don't want two paths for packets to intersect because we want to show that the congestion is 1 (i.e. that even in the worst case, packet paths don't collide). This is what at least I think is implied from the following OCW notes:

If one looks at page 3 of the notes it says:

  Color (i.e., label) the vertices of your graph red and blue so that
  adjacent vertices get different colors. Why must this be possible,
  regardless of the permutation π?

I understand it maybe for this small example, but why would the above be true in general?

I guess I didn't really understand why every constraint graph had to be bipartite or why it had to be 2 colorable.

For example, how do I know that as I form the constraint graph, that I will not have a some clique of size 3 or more? If this were the case it would be bad, because I would for sure need 3 colors at least!

I did notice that when we form the constraints, we form them by first considering a matching of the output packets that might collide and another set of constraint about packets that might collide when arriving to the destination. This two constraints adds two matching to the graph. Maybe the union of matchings forms bipartite graphs?

You didn't explain what Beneš networks are (note that your course notes use the wrong accent on the s!), but from the notes it seems that they describe FFT algorithms. In particular, they seem to be layered graphs. Such graphs have $L$ layers $1,\ldots,L$, and edges only go between adjacent layers $i,i+1$. Color all nodes in odd layers with one color and all nodes in even layers with another color. Since $i,i+1$ have different parities, this is a valid coloring.


How to convert DFA to regex with State Elimination I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states.

I have this difficult DFA i need help converting to RE:

using STATE ELIMINATION

if you could explain ripping state q1 from the DFA it would help a lot

If we're talking about the same Elimination problem then you should add an accept state and a start state. In addition, I allowed myself to disregard state $q_b$ as it never part of the language.

The start state will replace $q_0$. The accept state will replace $q_9$. Then to your request, we'll do the rest, starting from $q_1$.

From $q_1$ you either have 0 endless times or a 1 in other words, $0^* \cup1$ from $q_1$ to $q_2$.

Let us now rip $q_3$: from $q_2$ to $q_4$ you'll need 01. While from $q_4$ to $q_1$ you'll need 00.

Proceeding to rip $\{q_0, q_2\}$, note this is no more than a name and could just as well be renamed to $q_5$. Thus from $q_2$ to $q_1$ we have: $11*0$

All that's left is to close the circles which are probably cause your trouble:
For the fun of it, we'll go by order. Let us rip $q_1$:
This means $q_0$ reaches $q_2$ using a concatenation of 0 with the resulting regex of $q_1$ to $q_2$ which is we found and was $0^*1$. Removing $q_1$ then completes the self-cycle of $q_2$ and there would now be an arrow to self: $11^*0$.

Nearly done, remove $q_2$: remove $q_2$ thus connecting $q_0$ to $q_4$ through $0((0^*1)11^*0)^*01$, however, there are also the loops that are created to be taken into account, see the drawing attached: I realized that this is very confusing to read so I've added the following drawing:

I might have missed a character or two, but those are my two cents, also- remember to keep the loops in mind and their final transitions.

P.s. I noticed in the second NFA (yes, NFA as there are $\epsilon$ transitions), I have accidentally forgotten to add the transition itself from $q_2$ to $q_1$, however it is there in the next NFA


How to rank search results of short string lists I have a tree of foods, which I'd like to search to find relevant nodes. What's the best way to rank the results?

Here's an example sub-set after a search for "apple":

|-- apple pie
|-+ apples
| |-- cooking
| |-+ eating
|   |-- average
|   |-- Granny Smith
|   |-- Golden Delicious
|-- pork and apple casserole

Currently, I'm ranking based on which results come earliest in the full name of each leaf, so a result set would look like:

0 Apple pie
0 Apples, cooking
0 Apples, eating, average
0 Apples, eating, Granny Smith
0 Apples, eating, Golden Delicious
2 Pork and apple casserole

Where the rank is the index of the first token match, lower the rank the better.

I'd like to aggregate the matches, so that I don't display the full sub-tree on the initial search, for example:

Apples... (4)
Apple pie
Pork and apple casserole

The obvious way to rank these is to count the number of matching leaves, then the higher the rank, the better the match.

But, I'm not sure how to combine these rankings, since one is larger-is-better and one is smaller-is-better. Are there standard ways to combine rankings like this? (I'm not sure what to search for, so Google is giving me results about search engine optimisation, and searching web pages, which doesn't seem to apply.)

Although i dont really know how a result is better. I guess what you are doing is fine (And perhaps the best possibly you can get). Just one note to be more precise, you should be ranking a node $u$ based on the size of the subtree rooted at $u$ (not on the number of leaves in that subtree, or children of $u$). This is better (and more general).

But one way to solve issues like this in general is to give score to each node in your tree (a weight). The higher the score, the more it will be ranked above. Then, you will be looking for the subtree with highest weights. You compute this by summing the weights of all nodes in a subtree.

Example of weights (just to help you a bet):

closeness to search term (use hamming distance for example, or other metrics [e.g. look how spelling suggestion algorithms work.]
If this is a website of recipes for example, the nodes may be recipes and the weight of a node is how many "likes" it received from the website.

In conclusion, I guess what you are doing is the best approximation to have.  Adding the weights is a heuristic to give you perhaps better results.


How to handle missing continuous attribute values in ID3 (Iterative Dichotomiser 3)? I'm implementing the ID3 algorithm (Iterative Dichotomiser 3). I have an attribute which happens to be continuous like 12.21, 3.01, etc. AND have missing values which are marked as "NA".

How I'm discretizing the data: I'm finding the optimal split which results in the max information gain. How I'm dealing with missing values: I will use the most probable attribute value to replace the "?".

Of course I can do either process in both ways, and this is where my confusion arises. Is there a correct way in handling this?

Take a look at the C4.5 algorithm.  C4.5 is a successor to ID3.  It is more complex.  However, Wikipedia lists as one of its advantages over ID3 that C4.5 can handle data with missing attribute values.  So, you might take a look at how C4.5 handles missing attribute values -- or even simply use C4.5 rather than ID3.


Example of a code that can be decoded using bounded distance decoder In the book Information theory, Inference and Learning Algorithm, in chapter 13, MacKay defines bounded distance decoding

  A bounded distance decoder is a decoder that returns the closest codeword to a received binary vector $\mathbf{r}$ if the distance from $\mathbf{r}$ to that codeword is less than or equal to $t$; otherwise it returns a failure message.

Could anybody provide an example of a simple linear code that can be decoded by such a bounded distance decoder?

The simplest example is a repetition code. You encode the bit 0 as 000 and the bit 1 as 111. The decoder outputs the majority bit, which is always at distance at most $t = 1$.

As another example, suppose we encode 0 as 0000 and 1 as 1111. We can still correct up to one error (by taking the majority), but we cannot accommodate $t = 2$, since given 0011 we can't tell whether it came from 0000 or from 1111. Therefore we need to declare failure.


Which parser has the highest reduce moves? From what I have learned the number of reducing moves in the parsers are
generally in the order

LR(0)>= SLR(1) >= LALR(1).

But I am unable to understand where should I place CLR(1) in this category?

Is it CLR(1)>=LR(0)>= SLR(1) >= LALR(1) ?

The number of reductions in a successful parse is strictly dependent on the grammar, since every production must be reduced exactly once.

Consequently, all LR parsing algorithms which can parse a given grammar will parse all sentences accepted by the grammar using the same number of reduction steps (and the same number of shift steps).

The only moment in the parse where an extra reduction might possibly occur is just before an error action for a sentence which cannot be parsed by the grammar. The sequence of reduction/shift steps is still the same for all parsing algorithms up to and including the last shift; the only possible difference is some algorithms can perform more reductions before the error is noted.

This will be affected not only by the choice of parsing algorithm but also by the particular parse table compression algorithm used, since table compression generally involves replacing some error actions with the state default action in order to reduce table size. (Since the sentence is not recognised by the grammart, the parser will not be able to shift the lookahead token. So replacing an error action with a default reduction action must still produce an error before the lookahead token is shifted.)


What is the trick used in skip lists to minimize $k + \frac{n}{k}$? I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k.

Usually one traverses the "express line" (i.e. the top lane with least elements) first until you need to use lower lanes. This leads in the simple case of 2 linked-lists to a run time of:

$$ L_1 + \frac{L_0}{L_1} = k + \frac{n}{k}$$

in computer science courses it is common to optimize this equation without using calculus. The equation that it leads to solve is:

$$ k = \frac{n}{k} \implies k = \sqrt{n}$$

I was wondering if anyone remembered the alternative argument for optimizing the above equation?

If I recall correctly, it goes something like this:

we wish to choose a length of $L_1$ (i.e. k) that is as small as possible. But we also don't want it to be too small or $\frac{1}{k}$ will grow too much. So since the expression is sort of an "average" we just intuitively guess that its minimized that the "average" value. i.e. when $k = \frac{n}{k}$. I am not sure if this is completely correct or explained well but if someone remembers how to minimize this without using calc (as its usually taught in CS courses it would awesome!)

The method you mention is based on the following theorem:

  If $f \geq 0$ is non-decreasing, $g \geq 0$ is non-increasing, and $f(t) = g(t) = y$, then
  $$ y \leq \min_x [f(x) + g(x)] \leq 2y. $$

Note that there is (at most) a unique point $t$ such that $f(t) = g(t)$.

In your case, $f(k) = k$ is increasing and $g(k) = n/k$ is decreasing, and $f(\sqrt{n}) = g(\sqrt{n}) = \sqrt{n}$, so $\sqrt{n} \leq \min_k [k + n/k] \leq 2\sqrt{n}$. In fact, calculus shows that the minimum is indeed $2\sqrt{n}$.

The proof of the theorem is very simple: if $x \geq t$ then $f(x) + g(x) \geq f(t) = y$, whereas if $x \leq t$ then $f(x) + g(x) \geq g(t) = y$.


Count number of special onto functions We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$,

$$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$

1) $f(x,x) = 0$.

2) $f(x,y) = f(y,x) > 0$, for $y ≠ x$.

3) $f(x,y) \leq \max\{f(x,z),f(z,y)\}$ for all $x,y,z$ belonging to $[n]$.

How many such functions are possible for a given $n$? I have tried my best but I am not able to get any close to the solution! One may even see it as a undirected simple graph with n vertices, f(x,y) representing the edge weights. Any help is appreciated!

EDIT: i have been able to find that there are no such functions for n<3.

for n=3 we have one such function, for n=4, 13 are possible.

The parametrization you present is quite arbitrary, and the condition that the mapping be onto only serves to confuse; let's ignore it for now. Instead, given $n,c$, let us consider the number of colorings of $K_n$ using $c$ colors (in your case, $c=n-2$) such that condition (3) is satisfied: for every three vertices $i,j,k$,
$$ c(i,j) \leq \max(c(i,k),c(j,k)). $$
What does this condition mean? Let's start by considering the case $c = 2$. For any triangle $i,j,k$, the only situation which is forbidden is
$$ \{c(i,j),c(i,k),c(j,k)\} = \{1,1,2\}. $$

Let $G$ be the graph formed by the edges colored $1$. This condition states that if $(i,j),(i,k) \in G$ then also $(j,k) \in G$. It is not hard to prove that $G$ must be a disjoint union of cliques, and vice versa, every disjoint union of cliques satisfies the condition.

If $G$ is a disjoint union of cliques then the vertex sets of the cliques partition $[n]$; isolated vertices are considered as cliques of size $1$. Therefore the number of possible graphs (and so, possible colorings when $k = 2$) is the Bell number $B_n$.

The case of general $c$ is similar. Consider for example $c = 3$. The graph induced by edges colored $1,2$ must be a disjoint union of cliques, and within each such clique, the graph induced by edges colored $1$ must be a disjoint union of cliques. Therefore each possible coloring corresponds to a two step partition of $[n]$: first we partition $[n]$, and then we further partition each of the part. The number of such two step partitions is a so-called higher-order Bell number, the row $p = 2$ in this case. For general $c$, consult this table at row $p = c-1$.

Finally, what if we want to count the number of onto mappings? We can use the inclusion-exclusion principle. Let $X(n,C)$ denote the number of colorings using colors from $C$, and let $X(n,c) = X(n,[c])$; note that $X(n,C) = X(n,|C|)$. Also let $Y(n,C),Y(n,c)$ denote the number of onto colorings. We have

$$ Y(n,c) = Y(n,[c]) = \sum_{D \subseteq [c]} (-1)^{c-|D|} X(n,D) = \sum_{i=0}^c (-1)^{c-i} \binom{c}{i} X(n,i). $$

For example, if $n = 4$ and $c = 2$ then
$$ Y(4,2) = \binom{2}{0} X(4,2) - \binom{2}{1} X(4,1) + \binom{2}{2} X(4,0) = 1 \cdot 15 - 2 \cdot 1 + 1 \cdot 0 = 13. $$

How do we compute $X(n,c)$? The page linked to above gives the following recurrence:

$$
X(n,1) = X(0,c) = 1, \quad X(n,c) = \sum_{k=1}^n \binom{n-1}{k-1} X(k,c-1) X(n-k,c).
$$


Star operation in CS theory I have a question about the regular operation 'star' in computational theory.

IF $A$ is $\{ good , bad \}$ then

$A^* = \{ \varepsilon , good, bad , goodgood, goodbad, badgood , \dots \}$

What is the exact "regular operation" mean then ?

Can we use $^*$ operation only for regular language ? I don't think so.

$L = \{0^n1^n \mid n \ge 0 \}$ is a famous example of a non-regular language, but it seems we can create $L^*$?

The $^*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet (alphabets are commonly denoted by $\Sigma$).

Definition of $L^*$

$$L^*=\bigcup_{i\in \mathbb{N}_0}L^i=L^0\cup L^1\cup L^2\dots$$

Where, $L^0=\{\epsilon\}$ and $L^n=LL^{n-1}$ for $n\gt0$

Example

Let $\Sigma=\{0,1\}$.

$\Sigma^0=\{\epsilon\}$

$\Sigma^1=\Sigma\Sigma^0=\{0,1\}$

$\Sigma^2=\Sigma\Sigma^1=\{00,01,10,11\}$

$\dots$

$\Sigma^*=\{\epsilon,0,1,00,01,10,11,\dots\}$

In other words, $\Sigma^*$ is the set of all finite-length binary strings.


How to prove a language is regular? There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?

For instance, if I am given that $L$ is regular,
how can I prove that the following $L'$ is regular, too?

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Can I draw a nondeterministic finite automaton to prove this?

Yes, if you can come up with any of the following:

deterministic finite automaton (DFA),
nondeterministic finite automaton (NFA),
regular expression (regexp of formal languages) or
regular grammar

for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.

There are also useful properties outside of the "computational" world. $L$ is also regular if

it is finite,
you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as

intersection,
complement,
homomorphism,
reversal,
left- or right-quotient,
regular transduction

and more, or
using Myhill–Nerode theorem if the number of equivalence classes for $L$ is finite.

In the given example, we have some (regular) langage $L$ as basis and want to say something about a language $L'$ derived from it. Following the first approach -- construct a suitable model for $L'$ -- we can assume whichever equivalent model for $L$ we so desire; it will remain abstract, of course, since $L$ is unknown. In the second approach, we can use $L$ directly and apply closure properties to it in order to arrive at a description for $L'$.


Camera calibration without grid Ususally a grid pattern (circles or squares) is used for camera calibration. Features (circles or corners) are detected in a function (e.g. findCirclesGrid in OpenCV) and passed to the a camera calibration  function (e.g. calibrateCamera in OpenCV) together with corresponding object points (object coordinates).

Is it possible to calibrate a camera with circles which are "randomly" spread on a plane (object coordinates known)?
If yes, how does it affect the feature detection, i.e. findCirclesGrid? Is it less accurate?
If yes, how does it affect the calibrateCamera function? Can all parameters such as distortion for example still be computed?

Yes.  Any known pattern can be used for camera calibration, if you know the ground-truth shape.  You just need to have a number of points where you know (a) their location in the image and (b) their location in the physical world.  The procedure is simplest with a grid, so if you're choosing a pattern, might as well stick to that standard (why not?).

Questions about implementation and OpenCV are off-topic here, though.


Replace queries on string Let's define a replace query on some string $s$.

Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\},  l \geq r; \quad c_{i}, c_{j} \in C$. The replace query $\left(l, r, c_{i}, c_{j}\right)$ replaces all occurrences of $c_{i}$ with $c_{j}$ on $[l; r]$ segment of $s$.

There is a problem. Given string $s$ and $m$ replace queries $\left(l, r, c_{i}, c_{j}\right)$, perform them on $s$ and print the result.

Originally, the problem has low bounds on string length and queries count: $1 \leq n, m \leq 100$. The bruteforce solution seems to have $O(nm)$ complexity. But what if we increase the upper bound on $n$ and $m$ to, for example, $10^{10}$ or even $10^{100}$? Is there solution with better complexity?

The following approach will solve the problem in $O(km^2\log m + n)$ time, which is only better than $O(mn)$ if $n$ is extremely large compared to $m$ and $k$ is relatively small.  My hope is that someone can come up with a refinement of my "caching mechanism" that decreases the dependence on $m$.

The view from one position in the string

From the point of view of a particular position in the string, replace queries appear as a sequence of instructions of the form "If you are an x, change to a y", each of which occurs at a particular time.  The only instructions that are "visible" to a particular position in the string are those whose $[l, r]$ range includes that position.  The timestamp of an instruction is simply its position within the list of all replace queries: timestamps are therefore unique.

The idea is to build a directed graph that represents these time-stamped instructions as seen by the "current" string position (initially, position 1).  The vertices in this graph are the characters $c_1, \dots, c_k$; each directed edge $uv$ represents the instruction "If you are a $u$, change to a $v$", and is labelled with a timestamp, which is the position where it occurs within the list of all replace queries (starting from 1).  Note that an edge can be present multiple times, with different timestamps.  To find the "final" character at the current position, we start at time 0 at the vertex corresponding to the initial character at this position, and repeat the following steps as long as we can:

Choose the outgoing edge from the current vertex with the smallest timestamp that is greater than the current time
Move to the endpoint of this edge
Update the current time to the timestamp on this edge

The first step, choosing the "next" instruction, can be performed in $O(\log m)$ time if we use an adjacency-list graph representation that uses a self-balancing binary tree keyed by the timestamp to hold the set of outgoing edges for each vertex.  In the worst case, all $m$ instructions are visible to the current string position, so a single traversal therefore takes at most $O(m\log m)$ time.

Maintaining the instruction graph

Initially, we build this graph for position 1.  After determining the final character at that position, we update the graph as we move left-to-right through the string, processing each position in turn.

The $t$-th replace query $(l, r, c_i, c_j)$ requires 2 changes to the graph: An edge $c_ic_j$ with timestamp $t$ needs to be inserted when we reach position $l$, and that same edge needs to be removed when we reach position $r+1$.  Each of these changes takes $O(\log m)$ time using the graph representation described earlier.

Caching

The algorithm described so far performs the graph traversal at each of the $n$ string positions, so it takes $O(nm\log m)$ time -- worse than the original!  But all is not in vain.

Notice that for $m$ queries, there are only $2m$ times at which the graph changes -- so if we cache the final destination character for each distinct initial character $c_1, \dots, c_k$ whenever the graph changes, we can simply look up the answer in $O(1)$ time for each position until we hit the next query boundary.  This way, the full traversal need be performed at most once per distinct character after each change to the graph, for $O(km^2\log m + n)$ time.  (This approach -- "flush the entire cache as soon as the graph changes" -- is a very simple caching mechanism.  It may be that more sophisticated caching techniques can drop the time complexity further, by avoiding the recomputation of some cached final destination characters that do not change.)


Turing machine + time dilation = solve the halting problem? There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer can have access to an infinite number of a computation steps.

Assuming it's possible for a computer to functional perfectly for an infinite length of time (and I know that's a big ask): one could construct a computer HM which travels along this infinite worldline, computing the halting problem for a given M. If M halts, HM sends a signal to the finite observer. If after an infinite number of steps the observer doesn't get a signal, the observer knows that M loops, solving the halting problem.

So far, this sounds okay to me. My question is: if what I've said so far is correct, how does this alter Turing's proof that the halting problem is undecidable? Why does his proof fail in these spacetimes?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation.

However, what you'll likely want to know is whether a 'time dilation Turing machine' can solve the halting problem.

If you want to study this the influence of 'time dilation' on a Turing machine, you'll have to specify a formal model by which we can formally understand what it means for a Turing machine to make use of time dilation. Unfortunately, this format is ill-suited for providing such a formal model (unless someone else has written a paper about it) as creating the model is far too broad.

However, it isn't unlikely that some formalisation indeed is able to solve the halting problem. This paper by Scott Aaronson, Mohammad Bavarian and Giulio Gueltrini looks at computational models under the assumption that so-called Closed time-like loops exist and conclude that the halting problem is indeed computable within that model.


How to jump directly from level 0 to level 5 in a Gaussian pyramid without having the levels 1, 2, 3, and 4? I am current studying the Laplacian Pyramid as a compact image code by Peter J Burt and Edawrd Hudson.

I understood all the concepts but I am having trouble with the equivalent weighting function. I understand how it works but i can't find the relation between $h(n,m)$ and $w(n,m)$.

Here is the link for the paper. The equations are at the end of page 2.

$w$ is effectively defined by $$g_l(i,j) = \sum_{m=-2}^2 \sum_{n=-2}^2 w(m,n) g_{l-1}(2i+m, 2j+n)$$ and $h_l$ by $$g_l(i,j) = \sum_{m=-M_l}^{M_l} \sum_{n=-M_l}^{M_l} h_l(m,n) g_0(i2^l+m, j2^l + n)$$
Some straightforward substitution of the second into the first gives
$$\sum_{m_l=-M_l}^{M_l} \sum_{n_l=-M_l}^{M_l} h_l(m_l,n_l) g_0(2^l i+m_l, 2^l j + n_l) = \\
\sum_{m=-2}^2 \sum_{n=-2}^2 w(m,n) \sum_{m'=-M_{l-1}}^{M_{l-1}} \sum_{n'=-M_{l-1}}^{M_{l-1}} h_{l-1}(m',n') g_0(2^l i+2^{l-1}m+m', 2^l j+2^{l-1}n + n')$$
We conclude firstly that
$M_l = 2^l + M_{l-1}$, and since $M_1 = 2$ (and $h_1 = w$), we have $M_l = 2^{l+1}-2$. Secondly, that

$$h_l(m_l, n_l) = \sum_{\substack{-2 \le m \le 2 \\ |m_l - 2^{l-1}m| \le M_{l-1}}} \sum_{\substack{-2 \le n \le 2 \\ |n_l - 2^{l-1}n| \le M_{l-1}}} w(m,n) h_{l-1}(m_l - 2^{l-1}m, n_l - 2^{l-1}n)$$
by identification of weights of the same pixel of $g_0$.


Set which is easy to sample, but difficult to sample from its complement Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\frac{2}{3}$  members of $S$ of size $n$ (for all $n$).  $A$ does not have to be uniform.

Is there a set $S$ such that there exists an efficient algorithm $A$ such that for all $n$, $A$ generates at least $\frac{2}{3}$ members of $S$ (of size $n$), but any efficient algorithm for $S^C$ can only generate at most $\frac{1}{3}$ elements from $S^C$ of size $n$ (under complexity asuumptions)?

We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it.

A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\frac{2}{3}$ of the elements in $S$.

However, sampling from the complement of $S$ in the general case is even harder than you require: there exist sets $S$ such that there exists no Turing machine that given $n, x = 0^{n}$ as input outputs any string in $S$ of length $n$ starting with $1$. Furthermore, we can explicitly construct such a set $S$.

This is easy to prove by a diagonalisation argument. Let $K_{w, n}$ be the set of strings of length $n$ starting with $w$. There is a countable number of Turing machines, so let $M_{i}$ be the $i$th Turing machine. For $n \geq 2$, if $M_{n-1}$ on input $n, x = 0^{n}$ doesn't halt or outputs a string in $K_{00, n}$, set $S_{n} = K_{1, n} \cup K_{00, n}$. Otherwise set $S_{n} = K_{1, n} \cup K_{01, n}$. Then $S = \{\epsilon, 1\} \cup \bigcup_{i = 2}^{\infty} S_{i}$ is one such set.


Algorithm to check the distance between integers I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case.

I have a sorted array of pairwise distinct integers, say $[1,2,4,5,7,8]$
I need to know if there is a gap of at least two between two consecutive integers, i.e., if there are successive integers $a$ and $b$ in the list with $b>a+2$.

For example in the array given, the algorithm should return false, but for $[2,3,6,7]$, it should return true. Is it possible to solve it by mathematics instead of iterate and compare the integers one by one?

I will add some inputs and the desired output:

[1,2,4] -> false
[1,2,5] -> true
[1,2,4,6,8] -> false
[1,3,4,6,8] -> false
[1,4,6,8] -> true
[1,3,5] -> false

If you allow no missing elements, there is indeed an algorithm that does not
need to check all values:

Since the numbers are distinct and sorted, the algorithm

$\qquad\displaystyle
  [a_1, \dots, a_n] \mapsto \begin{cases}
                              \mathrm{true}, &a_n = a_1 + n - 1,\\
                              \mathrm{false}, &\text{else}
                            \end{cases}$

solves the problem.

If $a_n \geq a_1 + n$ there has to be a step larger than one.
On the other hand, $a_n < a_1 + n - 1$ can not happen without duplicates (pigeon-hole principle).

If you allow some missing elements but not too many in a row, this no longer works.
We will show this by an adversary argument.

Assume there was a deterministic, correct algorithm $A$ that reads $<n$ of
the input values.
Then, $A$ answers false for inputs with $n$ elements of the form

$\qquad\displaystyle I_1 = [1,3,\dots,2n-1]$.

By assumption, $A$ does not read at least one value; let's call that one $i$.
Without loss of generality, let $i \not\in \{1, 2n-1\}$; these cases can be dealt
with similarly. Then, $A$ also answers false on

$\qquad\displaystyle I_2 = [1,\dots,i-2,\mathbf{i+1},i+2,\dots,2n-1]$

because it is deterministic; if it does not read $i$ on $I_1$ it will also
not read $i+1$ on $I_2$ since the other elements are all the same.

But this result is wrong since there is a gap of $(i+1) - (i-2) = 3$ in $I_2$.
This contradicts our assumption that $A$ is correct; therefore, there can be no
such algorithm.