$UP^{\ O}\neq P^{\ O}$ for some oracle $O$ The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$.

I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $L\notin P^{\ O}$, i.e. $UP^{\ O}\neq P^{\ O}$.

I find a lot of struggle of finding an explicit $O$, and more struggle to proof it without finding one. I don't have access to the paper which is in the complexity zoo in the link above, can you please explain why it is true or provide me with access to the paper?

Here is the construction from Rackoff's paper Relativized questions involving probabilistic automata. We construct the oracle $O$ using diagonalization, in steps. At step $t$ we will construct the initial segment $O_t$ of $O$ which consists of $O \cap \bigcup_{i=0}^{n_t} \Sigma^i$ for some $n_t$, where $n_0 < n_1 < \cdots$ is an increasing sequence. We will maintain the following invariant: $O_t$ contains at most one string of each length. This will guarantee that the following language is in $UP^O$:
$$
L = \{ x : \exists y \in O \cap \Sigma^{|x|} \}.
$$

The construction will use an enumeration $M_i$ of all polynomial time Turing machines, with the guarantee that the running time of $M_i$ is at most $in^i$. It is a standard fact that such an enumeration exists.

Let $O_{t-1}$ be the initial segment constructed at step $t-1$ (or $\emptyset$ in the first step). We now show how to construct $O_t$. Choose the smallest $a_t > n_{t-1}$ such that $ta_t^t < 2^{a_t}$. Run $M_t$ on the string $0^{a_t}$, answering NO to all queries outside of $O_{t-1}$. Let $b_t$ be the length of the largest string queried, and let $n_t = \max(a_t,b_t)$. If $M_t$ accepts, set $O_t = O_{t-1}$, guaranteeing that $0^{a_t} \notin L$. Otherwise, set $O_t = O_{t-1} \cup \{x\}$, where $x$ is some string of length $a_t$ which $M_t$ didn't query (such a string must exist since $ta_t^t < 2^{a_t}$), guaranteeing that $0^{a_t} \in L$. You can check that $O_t$ satisfies the invariant stated above.

By construction, $L \in UP^O$ (the UP machine guesses $y$ of the same length as the input and verifies that $y \in O$), while $L \notin P^O$ since $M_t$ answers incorrectly on the string $0^{a_t}$, by construction.

Beigel, in the paper On the relativized power of additional accepting paths, shows that $P^O \neq UP^O$ for a random oracle, crediting this result to Rudich's PhD thesis. In fact he proves even stronger separations, showing that allowing more accepting paths increases the (relativized) power of polytime machines.


How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP? I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or maximum) with target value in decision version. Thus, the decision version can be solved in poly-time as well. Since, the decision version is $\mathcal{NP}$-hard, so is the optimization version, i.e., the optimization version is $\mathcal{NP}$-hard.
My question is how to prove the converse direction: if the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?
I in advance thank you for any suggestions!

If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

This depends on how technically precise you want to be.

The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm can produce the output in time polynomial in the encoded length of the input, so $OP \not\in \mathcal{P}$. However, the decision version $DP$ takes as input both the input of $OP$ and the guessed answer, so it is allowed time polynomial in the sum of the two, and in particular does not need to execute in time polynomial in the length of the problem per se.

However, if you're guaranteed that the output of $OP$ has (asymtoptically) an encoded length which is polynomial in the encoded length of the input (say $O(n^a)$ for input length $n$ and unknown $a$), then you can do a binary search, starting at any reasonable guess, doubling unless you get high enough, and then searching back down. The number of calls of the decision problem is $O(n^a)$, each call of the decision problem takes time polynomial in $n$, and the product of two polynomials is a polynomial.


every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar."
And wiki says, "a language can be generated by an LR(k) grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar"
Is the first statement in that discussion forum is correct?
I found wiki statement at many places but nowhere I found the first statement except in that discussion.
Please tell me if first one is correct or not, and If possible provide some source that confirms this statement. Thanks in advance.

The linked discussion thread comes from comp.compilers, which at one time was the definitive discussion forum for questions of this form (disclaimer: I was a constant reader and occasional contributor to that forum, so my opinion might be biased.)

The rather interesting discussion thread in question dates from October 2002, and was an attempt to discover if there were unambiguous languages (not grammars) which could not be parsed with any $LR$ algorithm. In the course of the discussion, Sönke Kannapinn noted that the $LR(k)$, $LALR(k)$ and $SLR(k)$ sets of languages are identical, for all $k\ge 0$. (That's the message cited in the question, but in a more readable presentation.)

Kannapinn cites the source of his assertion: the 1990 text Parsing Theory Vol II by S. Sippu & E. Soisalon-Soininen, which definitely should be considered a "standard" textbook (as Kannapinn notes in an earlier message in the same thread). The question is addressed in Chapter 6.6 (SLR(k) Parsing, from pages 70-84), which terminates with Theorem 6.71:

  For any fixed $k>=0$, the families of $LR(k)$ languages, LALR(k) languages and SLR(k) languages are all equal.

The proof is too long to reproduce here, but the textbook should be available in any good university library. (If it isn't, demand that they acquire it.)

Coincidentally, there was another similar discussion thread the next year, in which I offered a simpler proof outline. I reproduce it here (without modification aside from an attempt to fight with MathJax and Markdown to make it a bit more readable), in case it's useful to someone, although of course it might be wrong since discussion posts in comp.compiler are not subject to the thorough review accorded to Springer Monographs. So if you find an error, let me know, and if you find the formatting ugly, feel free to fix it.

Take an $LR(1)$ grammar $$G = <N, T, P, S>$$ and create $$G' = <N', T, P', <S,\$> >$$ where $N'$ is a subset of $N \times T$ (that is, the non-terminals in G' are the cartesian product of the original non-terminals and the original terminals.)

$N'$ and $P'$ are constructed basically with the LR construction:

Start with $N' = \{<S, \$>\}$ and repeat the following until no new non-terminals are added:

Let $<A, a>$ be an element of $N'$ for which there are no productions in $P'$. Now, for each production in $P$ of the form:

    $$A \to w_1 w_2 ... w_n$$

    add all possible productions

    $$<A, a> \to w'_1 w'_2 ... w'_n$$

    where

    $$w'_i = w_i \text{ if } w_i \in T$$
    $$w'_i = <w_i, b> \text{ for each } b \in FIRST(w_{i+1}...w_n ++ a)
    \text{ if } w_ \in N$$

    The second definition is multiple valued, so you might have to add a lot of rules :)

    Furthermore, if any new rule mentions a non-terminal $<W, w>$ which is not yet in $N'$, add it to $N'$

It is clear that this must terminate, because all the sets are finite. Also, the function $FIRST$ used above never yields epsilon.

Now, I assert that $G'$ recognises exactly the same language as $G$, and
furthermore that if $G$ is $LR(1)$ then $G'$ is $SLR(1)$, because it is impossible to have a reduce/reduce conflict between $<W, a>$ and $<W, b>$.

Of course, all this has done is move the lookahead sets into the definition of the non-terminals, so the resulting $SLR$ table is going to be just as big
as the original $LR$ table (bigger, actually, since no merging of lookaheads
has been done), but I think it does answer the original question.


Collision entropy definition The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by

$$\mathrm{H}_{2}(X)=-\log \sum_{i=1}^{n} p_{i}^{2} \tag{1}$$

Take two random variables $X$ and $X'$ which follow the same probability distribution. The probability of a collision is then simply $P_{\rm coll} = \sum_{i=1}^{n} p_{i}^{2}$. I would then expect that we say the collision entropy is just $H(P_{\rm coll})$ i.e.

$$-\left(\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(\sum_{i=1}^{n} p_{i}^{2}\right) - \left(1 -\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(1-\sum_{i=1}^{n} p_{i}^{2}\right)$$

This is in analogy with the binary entropy but with the probability replaced with the probability of a collision.

What is the motivation behind choosing $(1)$ to be the definition of collision entropy?

When $X$ is distributed uniformly over a domain of size $n$, then Shannon entropy, collision entropy and min-entropy are all equal to $\log n$. In a sense, all of these parameters measure the amount of uncertainty in $X$.

In contrast, your proposed definition is always between $0$ and $1$, tending to zero as $X$ gets more unpredictable. This is quite different from other notions of entropy, in which zero stands for predictable.


Efficiency of 0-1 linear programming w.r.t. number of binary variables I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.

Lets say I have a fixed number of $n$ variables in my program of which $k \leq n$ are binary. The other $n-k$ variables are continuous. My question is:
What can be said about the efficiency of solving these problems with respect to $k$? I know that 0-1-programming is NP-hard, but does it make a difference whether $k$ is small or large?

In my problem setting, I can somewhat modify the parameter $k$, i.e. the number of binary variables. Is it recommendable to lower them if possible ($k=0$ is impossible)? If so, why?

Thanks in advance

P.S.: If someone could point me to a paper discussing this, I'd happily download it.

If the other variables are integer variables

This is still NP-hard, even when $k=0$, for the same reason that integer programming is hard.

As for whether lowering the number of binary constraints will help in practice, that depends, and usually the only way to know is to try it.  It will depend on what the price of doing that is, as well as depend on the behavior of your ILP solver (which can sometimes be hard to predict).

I would expect that binary variables are harder to deal with than integer variables with a larger range.  In particular, if we have an integer variable whose values are in the range $\{0,1,2,\dots,r\}$, then I would expect that the smaller $r$ is, the harder the problem is.  Heuristically, the larger the value of the integer variable is, the better it can be approximated with a continuous variable (not restricted to integers), so the closer it comes to linear programming.  A standard strategy for ILP solvers is to solve the linear program without the integer constraints, then fine-tune the solution somehow to make everything an integer (e.g., round to the nearest integer).  We might hope that the larger the integers, the less error this process will introduce.  So, binary variables might be a lot harder than integer variables whose value will be large and whose range of plausible values is large.  This is not a hard-and-fast rule; just a rule of thumb to help you think about formulating your problem as an integer problem.

As always, the ultimate answer is to try it and see.

See also https://cstheory.stackexchange.com/q/16530/5038 and https://cstheory.stackexchange.com/q/29317/5038.  The operations research community studies what properties of ILP problems tend to be solvable more efficiently with existing ILP solvers (as "rules of thumb" and heuristics).

If the other variables are continuous variables

Then yes, the fewer binary constraints, the faster the ILP solver probably will be.  With no binary constraints (or integrality constraints), this becomes linear programming, which can be solved in polynomial time and for which there are efficient algorithms.  It's the binary constraints that make the problem hard.  The more binary constraints you have, the harder things can get.


Why is the quantity of sentences not finite? I'm currently studying formal languages. My lecture states that, while the words of a language are finite, the sentences build with the underlying grammar are not. But I don't get why this should be generally true. I can imagine grammar which leaves me with a finite amount of sentences.

I agree that one could create a language with infinite amount of sentences but I can't see why it should be generally the case.

Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number,
2 is a number,
3 is a number,
4 is a number,
5 is a number,
6 is a number,
7 is a number,
8 is a number,
9 is a number,
10 is a number,
11 is a number,
12 is a number,
13 is a number,
14 is a number,
15 is a number,
16 is a number,
17 is a number,
18 is a number,
19 is a number,
20 is a number,
21 is a number,
22 is a number,
23 is a number,
24 is a number,
25 is a number,
26 is a number,
27 is a number,
28 is a number,
29 is a number,
30 is a number,
31 is a number,
32 is a number,
33 is a number,
34 is a number,
35 is a number,
36 is a number,
37 is a number,
38 is a number,
39 is a number,
40 is a number,
41 is a number, and
42 is a number. Of course, one could also think of other thing to point out, for example, that the son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of my
son is my
grand
grand
grand
grand
grand
grand
grand
grand
grand
son. I hope I did not make a mistake there, or two mistakes, or three mistakes, or four mistakes, or five mistakes, or six mistakes, or seven mistakes. Let us stop there, as 7 is a nice number.

Do you still think that there is a bound on the length of grammatically correct English sentences?


Is this a reduction from decision problem to non-decision problem? Notations :

AUT$(X)$ (where $X$ is a graph) is the group of automorphisms of the graph $X$

$G=\langle A \rangle $ means group $G$ is generated by set $A$.

$G_{\{\Delta\}}$ is the set-wise stabiliser of $\Delta$

STAB

Input : $A \subseteq \text{Sym}(\Omega)$ and $\Delta \subseteq \Omega$

Find : Generator of $\langle A \rangle_{\{\Delta\}} = \{g \in \langle A \rangle \mid \Delta ^ g = \Delta\}$

ISO

Given : $X_1 = (V,E_1)$ and $X_2 = (V,E_2)$

Find : Is $X_1$ isomorphic to $X_2$?

Claim : ISO $\le_{P}$ STAB ( polynomial time reduction )

Proof : Take disjoint union $X=X_1 \cup X_2$ and note that
AUT$(X) \le \text{Sym}(V) =G$
$G$ acts on the set $V \choose 2$ i.e. set of all unordered pair of vertices.
 Clearly $E \le$ $V \choose 2$ and AUT$(X) = G_{\{E\}}$ under the above group action.

  Question : Is this a polynomial time reduction from decision problem to non-decision problem? Please note that It is possible that I may have misunderstood the reduction

Reference : Poly time computation in groups by E.M Luks  See Page no 3

It seems that the author uses the notation $A\le_p B$, where $A,B$ can be either function or decision problems, for saying that given an oracle for $B$, one can solve $A$ in polynomial time.

It is then shown that the isomorphism problem is reducible to finding the generators of a setwise stabilizer group (STAB) by showing that it is reducible to finding the generators of the automorphism group (AUT), and that $AUT\le_p STAB$. The latter is shown by viewing vertex permutations as an operation over vertex pairs, and seeking the generators of the corresponding stabilizing group relative to $E$.


Given a list of points on a sphere find the place for another point such that most space is covered? Suppose I knew my current location as a geographical point (Lat/Lng) and had a standard radius to search (meters). Now given a list of previously searched geographical points as the centers of circles with the same standard radius that are nearby my point but do not encompass my point what would be a good algorithm for determining where to place the center of the new geographical point such that the circle around it covers the most area not covered by other circles while also containing my current geographical point?

I've already done some thinking and I thought perhaps something to do with the average of all the points would perhaps work, but it becomes tricky because the points are on a sphere instead of on a plane.

Of course because this is the real world we must take all distances as "sphere" distances instead of straight-line distances. An algorithm which uses straight line distance but can be substituted for sphere distance is also acceptable.

I'm sure there is a name for this problem, I just could not find a name so I figured I would ask here.

The general problem is called Circle packing, which gets easier with equiradius circles, to get hexagonal grid and put circles on hexagon vertices and one in the center. This works on Euclidian space, so the hexagon coordinates should be converted by some kind of mapping, for example Vincenty formulae.

This method will give really neglible overlapping, but to be exact further corrections might be needed (like error calculation at intersection points to shift the centers). For small radius (like 50m) error will be very small (using the mapping to sphere). Performing grow on already available circles will give the problem of initial rotation to fit more space, so with many initial circles not fitting the grid only general method (iterative one) will give the optimum.

The deterministic optimization shows the method to treat circle packing as quadratic optimization.


Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.

When we say that hitting set is NP-hard, we mean that the following decision problem is NP-hard: given a set system $S$ and an integer $k$, decide whether there is a hitting set for $S$ of size at most $k$.


# of permutations satisfying special inequalties of each element0 Recently I was solving a counting problem, which needed this subproblem to be solved:

Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations $p_1, p_2, \cdots, p_n$ which satisfy:

for all $1 \le i \le t$, $p_i \le f(i)$, and
for all $t < j \le n$, $p_j \ge f(j)$.

For my problem, $n$ is quite big (about 40, which enabled me to think of meet-in-the-middle), but $t$ is quite small (about 10-15). So I tried to solve the problem with an algorithm regarding $t$, but failed.

I tried to exploit the fact that, if we consider only one of the conditions, the problem becomes super-easy. So I allocated first $t$ elements of the permutation(tried all possible cases), and then calculated # of possible permutations of the remaining $n-t$ elements. This method could give an answer reasonably faster than iterating all possible $n!$ permutations. However it is still really slow, maybe using an $2^n n^2$ dp approach would be faster than this.

I believe that iterating first $t$ elements is not required to solve the problem, but couldn't find any way. Could you please help me solve this problem?

A faster approach

It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations.  This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.

The idea is to enumerate all possible subsets of $t$ elements.  We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in).  There are $\binom{n}{t}$ such choices for $S$.

For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\{1,2,\dots,n\}\setminus S$ so that the last $n-t$ elements satisfy the second condition.  Then, we multiply these two counts.

Each of those counts can be computed efficiently.  For instance, to compute count (i), we compute

$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$

where $g(i) = |S \cap \{1,2,\dots,f(i)\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$).  Similarly, to compute count (ii), we compute

$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$

where $h(i) = |\overline{S} \cap \{f(i),\dots,n\}|$.

These two counts can be computed using $O(n)$ operations, leading to the claimed running time.

A further optimization

You can further optimize this, by splitting $S$ into two parts.  Decompose $S$ into

$$S = S_1 \cup S_2,$$

where $S_1 \cap S_2 = \emptyset$, by defining

$$\begin{align*}
S_1 &= S \cap \{f(t+1),f(t+1)+1,\dots,n-1,n\}\\
S_2 &= S \cap \{1,2,3,\dots,f(t+1)-1\}.
\end{align*}$$

Now notice that to count (ii), we don't actually need to know both $S_1$ and $S_2$: it's enough to know $|S_1|$ and $S_2$: the exact elements in $S_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j>t$.

Furthermore, since $|S|=t$ and $|S|=|S_1|+|S_2|$, it suffices to know $S_2$.  Once we know $S_2$, we can compute $|S_1|=t-|S_2|$ and then compute count (ii).

Similarly, once we know $S_2$, we can also compute count (i).

So, we're going to enumerate all possible values for $S_2$, i.e., all subsets of $\{1,2,3,\dots,f(t+1)-1\}$ of size $\le t$.  There are

$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$

possible choices for $S_2$.  Then we obtain an algorithm whose running time is $O(Q \cdot n)$.  The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.

In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$.  For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.

Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0).  It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.


what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata my doubt is

what is the difference between transition function (delta) and extended transition function  (delta cap ) in finite automata ?

both of them when started at a state q for a string w will lead to same sate p what is the difference

  is transition functions gives the transition over an input alphabet ,
  where as the extended transition symbol gives a transition for the
  string w using the transition function?

I read some references in order to answer your question ,

Transition function : takes as arguments a state and an input symbol and returns a state, denoted by δ .
Extended transition function : Describes what happens when we start in any state and follow any sequence of inputs ,means is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w).  denoted by ˆδ .
in simple term : transition function takes two parameters: a state and a symbol , while extended transition function takes a state and a string.

Example of transition function :

Example of extended transition function :


Recovering data from under sampled data streams I’m trying to analyze a repeated data stream from a sensor.  The data probably has events at the 100us scale, it occurs at a fairly random interval, and the signals are extremely similar.  The problem is that I don’t have any sensors that have sub-millisecond refresh rates.  The best I can do with what I have is about 1ms sensor reads.
So . . .
The idea is that if I sample a large number of event the chances are that the sampling ticks are falling on different sections of the signal.  If this is true then a series of 10-20 events should give me the data that I need to reconstruct the signal.  The signals repeat in a fairly random fashion and are very similar in each dataset so the chances are that each sampling run is gathering “pieces” of the total dataset.
Is there a name for this sort of procedure so that I can start to research how to do it?  Are there algorithms or toolsets in the open source world to accomplish this task?
Right now I’m literally graphing the data on graph paper and overlaying the image.  This is less than ideal . . .

It's not the same, but it reminds me of super-resolution.


How to reconcile the different definitions of asynchrony? There are 3 definitions of asynchrony that I know of:

In event-based programming, asynchrony refers to the execution of tasks in a non-sequential way, which may involve creating another thread. For example with AJAX, we can perform HTTP requests and handle their response in a new thread so that the program doesn't block to wait for results.

In communication, a channel is asynchronous if both parties don't need to be present at the same time (e.g., emails), and synchronous if they do (e.g., telephone).

In distributed systems, an asynchronous model is one where messages may take an arbitrary long time to transit. It implies that there is no way to know for sure if a node has crashed or it/the network is just being slow.

However I struggle to reconcile these 3 definitions. Is there a common denominator that I'm missing, or is the term asynchrony used in 3 completely different contexts?
Thank you for your help.

The unifying definition is that one part of the system triggers an event in another part of the system, and the triggerer does not know when the event will take place.
To put it another way: in a synchronous system, you know when things (will) happen. In an asynchronous system, you don't know when things (will) happen.
In event-based programming, a thread creates another thread, and then it has no control over when the thread will do its job. For example, with AJAX, the new theard performs an HTTP request, and the original thread continues executing without knowing when the HTTP response comes back.
In communication over an asynchronous channel, the sender of a message does not know or care when the recipient will be available receive the message.
In an asynchronous distributed system, the sender of a message does not know when (or possibly even whether) the recipient will receive the message and potentially reply to it.


Finding the union, subtraction, and intersection of two DFAs I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts:

I can prepare the union, subtraction and intersection DFA of two DFAs by preparing their product automaton and then suitably choosing final state. If $A_1$ and $A_2$ are non final states of DFA1 and DFA2 respectively and $F_1$ and $F_2$ are final states of DFA1 and DFA2 respectively, then,

For union of the DFAs, any state having any final state will be final:$A_1F_2, F_1A_2$ and $F_1F_2$.
For intersection of the DFAs, any state having both final states will be final:$F_1F_2$
For subtraction DFA1-DFA2, state having DFA1's final state but non final state of DFA2 will be final: $F_1A_2$

While preparing product automata for union and subtraction of DFAs, I may have to mark state $F_1D_2$ as final, where $D_2$ is dead state in $DFA_2$ and $F_1$ is final state in $DFA_1$. State $F_1D_2$ need not be dead state in the union, subtraction and intersection DFA. Is that right?
I can also prepare union DFA by introducing new start state with $\epsilon$-transitions to start states of both $DFA_1$ and $DFA_2$. Then I can reduce the $\epsilon$-NFA if required. I will have to mark final state as explained in 1st bullet point in point 1. I found this approach is similar to product automaton approach, its just that it avoids unreachable states while product automaton approach forces to consider all, even unreachable states. Is that right?
If point 3 is correct, can I prepare intersection and subtraction DFAs by following approach stated in point 3 but marking final states as stated in point 1?

Yes, your understanding on point 2 is correct.

Your understanding on point 3 is mostly correct, except where you say "mark final state as explained in 1st bullet point in point 1".  That statement doesn't type-check, as you can't do that to the $\epsilon$-NFA.  If you've created an $\epsilon$-NFA, then its states are of the form $S_1$ or $S_2$ (where $S_1$ is a state of DFA1 and $S_2$ a state of DFA2), not of the form $S_1S_2$.  So, it's not an option to mark $A_1F_2$ as final, as that's not a state of the $\epsilon$-NFA.  Fortunately, you don't need to do that.  You create the $\epsilon$-NFA as you described, then that works immediately with no further changes needed.  The final states of the $\epsilon$-NFA are the final states of DFA1 and the final states of DFA2.  (Perhaps you are thinking: create the $\epsilon$-NFA, convert it to a DFA using the subset construction, then mark final states specially.  But there's no need to mark final states specially: the subset construction already takes care of marking the final states correctly.)

No, you can't do this for intersection or subtraction.  Try it on some examples.  I think you'll quickly be able to find some examples where it goes wrong.  Also, my comments about point 3 apply here as well.


In which order to solve subproblems when using memoization? I am currently trying to solve a task with memoization.  I have following recursion:

A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) )

I am not sure in which order the sub-problems should be solved best, so that  multiple calculations are avoided.

Does someone have an idea which order is best?

Let me show you the general approach to figuring this out.  Then I'll let you apply that technique to your specific situation.

Well, it's clear that you need to solve $A(i,j-1)$, $A(i-1,j-1)$, and $A(i-1,j+1)$ before solving $A(i,j)$.  So, you need to pick an order that ensures all three of those are solved before you try to solve $A(i,j)$.  What order would work for that?

I suggest you try drawing a picture.  Draw a grid, with one dot for each $(i,j)$.  Draw an arrow from $(i,j-1)$ to $(i,j)$, an arrow from $(i-1,j-1)$ to $(i,j)$ and an arrow from $(i-1,j+1)$ to $(i,j)$ for each $(i,j)$.  You might do this for, say, a 4x4 grid.  Look at the resulting picture.  Can you find an order of traversing the dots, so that is consistent with all of the arrows?  Hint: try topological sorting that graph.  What order does that give you?  Can you generalize?  What would work for a 5x5 grid?

If you're not sure, just write a recursive program and apply memoization.  Then you won't need to explicitly pick an order to build things out bottom-up; the computer will take care of that for you.  See When can I use dynamic programming to reduce the time complexity of my recursive algorithm? and https://en.wikipedia.org/wiki/Memoization.


CFG - Left factoring in recursive nested productions I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with the follow exception. I've provided the simplest case to illustrate the problem below.

S -> a b S | T
T  -> a c T | d T | ϵ

This grammar rightly generate a FIRST(S) - FIRST(T) clash, as both S and T can generate a as a first terminal.

One (clearly wrong) attempt to left-factor the a terminal was to substitute T into the S production.

S -> a b S | a c S | d S | ϵ

This would allow for left factoring like so:

S -> a U | d S | ϵ
U -> b S | c S

However, this grammar is no longer equivalent, as it would accept the string acab when the original grammar would not.

I'm hoping that there is some way to manipulate this grammar that I'm not aware of to eliminate the FIRST(S) and FIRST(T) clash. Is there a method to left-factor a terminal in recursive nested productions as is described above?

You can solve this with regular expressions:

S -> a b S | T

is equivalent to

S -> (a b)* T

and

T -> a c T | d T | ϵ

is equivalent to

T -> (a c | d)*

Subtitute T into the rule for S:

S -> (a b)* (a c | d)*

Now, you can use a standard method to derive a right regular grammar.


DFA - Accept all strings that does not contain a certain substring So I have been trying to create a Deterministic Finite Automaton(DFA) in Jflap that accepts all strings from the alphabet {a, b, c} except those that contain the substring "abc". However i keep running into issues where certain strings that should be allowed aren't, such as "acbc". Do you have any tips or tricks that can be used to get around these kind of issues?
DFA that accepts any string that contains substring "abc" below

This is the inverted DFA of Image 2 which should accept all string combinations of the language{a,b,c} that do not contain the substring "abc"
Final Automaton


NLP: Automatically categorize words semantically into non-predefined classes I am looking for a method to categorize a given word into semantically into classes. A simple example would be:

chair -> furniture

The most reasonable way to do so that comes to my mind, would be to create a tree containing words, where chair is a predecessor of furniture. Then one could define a threshold that describes the level of the tree predecessor that should be taken as the result.

Is there some existing research/tools or even trees that fulfill the described task? I cannot find anything in google because I do not know the specific term for my problem. Keyword Clustering as a technique seems a little different, because is works on existing data and return multiple matches.

You're looking for Wordnet https://en.wikipedia.org/wiki/WordNet ...


Conditions for a node to be a leaf node on DFS tree Question:
Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in term's of v's discovery time d[v] and finishing time f[v].

I honestly have no idea what the answer to this question from a past exam may be...

A node v is a leaf node on the DFS tree if and only if f[v] = d[v] + 1.

The proof is obvious once you follow the DFS, marking each node's discovery time and finishing time. A leaf is defined as a node that has no children.
Let $v$ be a node.

Suppose $v$ has children in the final DFS tree. That is, we will go forward to a child $u$ of $v$ right after we have discovered $v$. That is, $d[v]+1 = d[u]$. The finishing time of $v$ must come after that. So f[v] $\gt$ d[v] + 1.
Suppose $v$ has no children in the final DFS tree. That is, we will go backtracking once we have discovered $v$. That is, we will finish $v$ right after we have discovered it. That is,  f[v] = d[v] + 1.

For people who are not familiar with discovery time and finishing time of a node v associated to a DFS, you can check either Stanford course note or Carnegie Mellon course note. Of course, you may just search by yourself.


Using interval graphs to find authorship disputes The first chapter of the book "Graphs and their uses" by Oystein Ore says that interval graphs can be used to resolve authorship disputes, but I couldn't find any details.  How does this work?  What is the algorithm?

From the text (Chapter 1.7):

  Interval graphs have also been used to investigate the likely authorship of disputed pieces of writing, such as certain works of Plato. Various features of an authors prose style are studied for their appearance in several literary works. By drawing a graph in which the vertices correspond to these literary features and the edges correspond to pairs of them which occur together in the same work, we obtain a situation very similar to our archaeological example. As before, we can then investigate whether the resulting graph can be represented as an interval graph, and we can thereby attempt to arrange the works in chronological order. By doing this, it has sometimes been possible to relate the style of the disputed piece of writing to that of the author in question, and thereby to determine the likely authorship.

I'll explain shortly the "archaeology example" your excerpt refers to. It seems that the authorship dispute problem is really no different from it, and any practical application would face similar problems as I will describe.

Around 1900, Flinders Petrie formulated a problem known as sequence dating while studying 800 types of pottery found in 900 Egyptian graves. To each artifact, we associate a time interval (unknown) during which it was used, and to each grave a time point (unknown) when its contents were interred. Then, the problem is to figure out the time relationships between the artifacts and the graves.

Now consider a graph $G$ whose vertices correspond to distinct artifacts. There is an edge between two vertices if they were found in some common grave. Assuming each pair of artifacts whose usage intervals intersect are to be found together in some grave we have that $G$ is an interval graph. Furthermore, an interval assignment for $G$ is a candidate for the usage intervals of the artifacts. However, of course in practice, it might be that we have incomplete data so the assumptions do not hold, and in any case, we need additional techniques to choose the correct interval assignment.


Universal memcomputing machines (UMM) This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular.  They prove that their UMM can solve NP problems in P, although they don't claim P = NP.  In their next paper, they go on to build a physical model of this UMM with moderate success. Does this mean P=NP?

The authors suggest a new computation model that solves NP problems in polynomial time. Another such model has been known for a long time – non-deterministic Turing machines. They can also solve NP problems in polynomial time. In fact, one common definition of NP is the set of problems solvable by non-deterministic Turing machines in polynomial time.

If the authors succeed in realizing their machine physically (which is doubtful), then this shows that the "efficient Church–Turing thesis", which states that all physically realizable computation models can be simulated by a Turing machine using only polynomial overhead – is false. Another candidate for refuting this thesis is quantum computers, but they are conjectured not to be able to solve all NP problems in polynomial time.


Negligible functions in definitions of statistical closeness and computational indistinguishability Statistical closeness implies computational indistinguishability.

Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible function that is used in definition of computational indistinguishability?

Can we say anything about the negligible function used in computational indistinguishability if we know how the negligible function in definition of statistical closeness looks like?

What about the special case: negligible function in definition of statistical closeness is zero?

Definitions from Goldreich, Foundations of Cryptography:

Ensemble = sequence of random variables, $\{X_i\}_{i \in \mathbb{N}}$

Computational indistinguishability:

Two ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p$ and all sufficiently large $n$'s,

$
  |P(D(X_n) = 1) - P(D(Y_n) = 1)| < \frac{1}{p(n)}.
$

(this definition actually says that $|P(D(X_n) = 1) - P(D(Y_n) = 1)|$ is negligible function in $n$)

Statistical closeness:

Ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are statistically close if their statistical difference $\triangle(n)$ is negligible.

$
\triangle(n) = \frac{1}{2} \sum_a |P(X_n = a) - P(Y_n = a)|
$

Statistical distance between $X_n$ and $Y_n$ can be defined as the maximum, over all functions $D$, of
$$ |P(D(X_n) = 1) - P(D(Y_n) = 1)|. $$

In particular, if the statistical distance between two sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ is negligible (eventually smaller than $1/p(n)$ for any polynomial $n$) then they are computationally indistinguishable.
The other direction is not true, and this is what drives all of cryptography.

I leave it an exercise to show that if two sequences distributions have zero statistical distance (i.e., they are copies of the same random variables) then they are computationally indistinguishable.


Does FOL extended with least-fixed points satisfy the Compactness Theorem? I am aware that first-order logics (FOL) satisfies the compactness theorem. That is, if a FOL theory is insatisfiable, a finite subset of the axioms of such theory is insatisfiable too.
Is it the case that FOL extended with least-fixed point (LFP) satisfies the compactness theorem too?

No, it does not satisfy compactness anymore.
Least fixed point operators can let us define, for example, the standard part of a model of $\mathsf{PA}$. The standard part of a model $\mathfrak{A}=(A;+^\mathfrak{A},\times^\mathfrak{A},0^\mathfrak{A},1^\mathfrak{A})$ of $\mathsf{PA}$ is just the smallest subset of $A$ containing $0^\mathfrak{A}$ and closed under $n\mapsto n+^\mathfrak{A}1^\mathfrak{A}$. But this is exactly a least fixed point definition: the standard part of $\mathfrak{A}$ is the least fixed point of the operator $$\Phi(P): x=0\vee\exists y(P(y)\wedge y+1=x).$$
This in turn lets us pin down the standard model of $\mathsf{PA}$ up to isomorphism by the theory $\mathsf{PA}$ + "Every element is standard." But this contradicts compactness: no compact logic can ever pin down an infinite structure up to isomorphism (this is really just the observation that the upwards Lowenheim-Skolem theorem is just a compactness corollary).


Is the "modular subset product" problem NP-complete? While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is replaced by modular arithmetic?

A concrete example is the subset product problem, which was known to be $NP$-complete. I wonder if we consider the problem over ring $\mathbb{Z}_n$, as formulated below, it is still $NP$-complete?

  Given $t, n \in \mathbb{N}$ and a finite set of integers $S$, determine whether there exists $S' \subseteq S$ such that $\prod_{s \in S'}s \equiv t \pmod n$.

My principal difficulty in approaching the problem is that I cannot figure out how the (polynomial) reduction works, supposing the $NP$-completeness is retained, due to the "cyclic" behavior of modular arithmetic. I've tried to search for variants of the problem but no luck. Thank you for any explanations, suggestions or references.

The claim that you linked to (that subset product is strongly $NP$-complete), is incorrect: it is only weakly so. The numbers $s\in S$ are small and can be represented in unary, but $t$ has to be represented in binary for the reduction to work.

If you consider it over $\mathbb{Z}_n$ it remains weakly $NP$-complete, since we can just take $n$ to be $\Pi_{s\in S} s$. In this case, the fact that we're doing modular arithmetic becomes irrelevant. $n$ will be exponential in $\Sigma_{s\in S} s$ so that $\log n$ (the size of a binary representation of $n$) will be polynomial in the size of the original instance (in which all $s\in S$ were represented in unary).


Can a greedy algorithm have more than one subproblems to solve after making greedy choice? For example:
s = <s1 s2 s3> is my problem,

I make greedy choice s2 and solve s1 and s3 in a greedy way.

In CLRS, it was mentioned regarding "designing greedy algorithms"

  Cast the optimization problem as one in which we make a choice and are
  left with one subproblem to solve

So why is it that we are left with only one subproblem in greedy method after making greedy choice?

I think what you are talking about is Divide and Conquer (and Combine) techniques:

Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.
CLRS 3rd Ed Ch 4, pp. 65

If not D&C, then at least a variant. It seems you are making an greedy choice, then this divides the problem into multiple, and you solve these subproblems the same way. Consider the following problem which I think can be solved as you mentioned:

Given a directed binary tree $T$ (meaning edges are directed from parent to child) with positive integer values on the nodes, determine the directed path with maximal sum of node values.

Here is how we can solve this:

We make a "greedy" choice to include the root node. Since the values are positive, we know that the root node can only increase the sum of node values.
We now can either go left or right (not both since it is directed towards leaves).
Solve the left case, what is it's maximal path? Let's say it's of weight $L$.
Solve the right case, what is it's maximal path? Let's say it's of of weight $R$.
Now we combine these results, if $L > R$ then we prepend the root node to the path returned from the left case, else we prepend the root node to the path returned from the right case.
If we get down to a leaf node, simply return it because it will be it's own maximal path since values are positive.

So this is a kind of "greedy" algorithm in the sense that we make a greedy choice (include the root node always). However, it is much more of a divide and conquer algorithm based on the definition of D&C. This is why greedy must only be left with one subproblem. If we have multiple subproblems then we are either in the case of Divide and Conquer or Dynamic Programming most likely.


Learning a small disjunction I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form

$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$

but I don't know the values of $i_1,\dots,i_k$.  I am given many pairs $(x,f(x))$ for random values of $x$ (chosen uniformly and independently at random).

I'm looking for an efficient algorithm to recover $i_1,\dots,i_k$, given this information.  How efficiently can this be done?  How many pairs are needed?  Randomized algorithms are OK.  I'm particularly interested in the regime where $k \ll n$.

This is similar to the learning juntas problem, but it might be much easier.  With the learning juntas problem, we know that $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ but neither $i_1,\dots,i_k$ nor $g$ are known.  Here, we know $g$ and know that it is a disjunction, so it seems like the problem might be much easier.

I can see an information-theoretic lower bound: $\Omega(k \lg n)$ pairs are needed.  There are ${n \choose k}$ possible candidates for $f$, and each pair gives us only one bit of information about $f$, so we need at least $\lg {n \choose k}$ pairs; for small $k$, ${n \choose k} = \Theta(k \lg n)$.  How close to this can one get?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).

$\Theta(2^k \lg n)$ queries are necessary and sufficient.

Algorithm

Define $I = \{i_1,\dots,i_k\}$.  Our goal is to recover $I$.  Given $x$, define $Z(x) = \{i : x_i = 0\}$.  For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$.  This suggests the following algorithm:

Set $J := \{1,2,\dots,n\}$.
For each $x$ in the input such that $f(x)=0$, set $J := J \cap Z(x)$.
Output $J$.

Analysis: It's guaranteed that this algorithm will output a set $J$ satisfying $I \subseteq J$.  Can we ensure that $I=J$?  Well, if we have $c \lg n$ values of $x$ where $f(x)=0$, then for any fixed $j \notin I$, $\Pr[j \in J] \le 1/2^{c \lg n} = 1/(2^c n)$; then by a union bound, $\Pr[J \ne I] \le 1/2^c$.  So, the probability that this produces the wrong output can be made exponentially small in $c$, as long as we have $c \lg n$ values of $x$ where $f(x)=0$.

Moreover, given $m$ pairs, we expect $m/2^k$ of them to have $f(x)=0$.  So, if we have $c \cdot 2^k \lg n$ pairs, we expect $c \lg n$ where $f(x)=0$.  Therefore, $O(2^k \lg n)$ pairs suffice to ensure that this algorithm will give the correct answer (except with negligible probability of failure).

Lower bound

This is the best we can do.  We can extend the information-theoretic lower bound in the question.

Let's start by showing that $\Omega(2^k)$ pairs are needed.  For a random $x$, we have $\Pr[f(x)=0] = 1/2^k$.  Therefore, we obviously need $\Omega(2^k)$ pairs to have a good chance of observing at least one pair where $f(x)=0$.  With $o(2^k)$ pairs, there's an overwhelming probability that all pairs satisfy $f(x)=1$, in which case we have learned nothing about $f$.  So, $\Omega(2^k)$ pairs are needed.

We can improve this lower bound a bit.  Call $x$ good if it satisfies $f(x)=0$.  Suppose we have to examine $p$ pairs before we see the first good value of $x$.  Once we see our first good value of $x$, how many bits of information have we learned about $f$?  Only $\lg p$ bits (because one of those $p$ pairs yields 0 and all the rest are 1; there are $p$ ways to select one of them to be 0).  It takes about $2^k$ pairs to see the first good value of $x$.  So, after observing $2^k$ pairs, we expect to learn about $k$ bits of information about $f$.  In general, each good value of $x$ gives us about $k$ bits of information about $f$, and we need to see about $2^k$ pairs per good value obtained.  Now as described in the question, we need $\Omega(k \lg n)$ bits to specify $f$ uniquely.  Therefore, we need $\Omega(\lg n)$ good values of $x$, so we need $\Omega(2^k \lg n)$ pairs in total.

This gives a lower bound that matches the performance of the algorithm above, to within a constant factor.  Therefore, the algorithm above is asymptotically optimal.


Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$ Given we change the rule to:

  $-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$

I was wandering whether it's possible and how would it affect the trees' height, would it still be logarithmic?

Would the exact same balancing techniques work? (if we took those methods from a normal AVL and try to convert our modified AVL to a normal AVL running from down to top or to down).

I've tired drawing some schematics in order to find out what would be the minimal number of nodes $m$ for some tree $T$ with height $h$ like we did with a regular AVL but I had a real hard time formalizing it.

If the maximal branch is of height $h$ then you know that all the other branches have at least height $h-s$.

Lets consider $n$ the number of nodes in the two extreme case:

All branches of height $h$: $n=2^h$
One branch of height $h$ the others of height $h-s$: then $n=2^{h-s}+s$

Hence $ 2^{h-s}+s=\frac{2^h}{2^s}\leq n\leq 2^h$ since $s$ is a constant the height is still logarithmic in the number of nodes.

I think this answer your other questions too.


Software management of TLB misses? I'm reading an OS textbook and it was talking about TLB misses being handled by software. I'm very new to all this by the way. So there's a context switch to some kernel procedure. But surely in this case the TLB is not flushed, and the kernel code doesn't itself use the TLB, since that would defeat the purpose? But then how exactly does it work? I don't know why the text wouldn't address such a seemingly obvious question.

Plus you're still using virtual memory, right? So you would be doing two context switches, a bunch of page table lookups in memory, in addition to the actual kernel instructions, per missing TLB entry. It just seems counterintuitive to do all that work to make use of something that's supposed to save you work. Sorry if I'm getting something completely wrong here. Thank you in advance.

Textbooks don’t have to include everything. There should be room for you to figure out things yourself. Otherwise, how would we ever create things not found in today’s textbooks?

Maintaining the TLB is a tiny bit of code in the operating system. But every single instruction accessing memory relies on the TLB. Do you think the TLB does NOT save enormous amounts of work? 99.99% of all memory accesses are fast because the TLB tells you immediately where the data is. Having to update the TLB sometimes is a very small price to pay.


Efficiently finding $k$ smallest elements of Cartesian product Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + \dots + x_n$, where $x_i\in A_i$.

I can't simply create all combinations in memory and sort them because of large amount of data.

For example, I have 1000 drinks, 1000 main courses and 1000 desserts. I want to find the 100 cheapest meals but I can't store all 1,000,000,000 elements in memory.

Additional details

I have Drinks, Main Courses and Desserts already sorted.
I've found some solutions like Efficient sorted cartesian product of 2 sorted array of integers but only for 2 lists. For greater amount of sets it still memory-consuming.
Lazy generating next "sorted" value will be useful.
If no efficient exact algorithm, it could be heuristic or approximation algorithm.
It's similar to X + Y sorting problem , efficient faster than O(n^2 * log n) solution is unknown

Question:

Are there an efficient ways to get only $k$ cheapest(*) elements of Cartesian product?
(*) Price of the result element is sum of all numbers in that element.

If $k$ is known in advance, we can do the following. I will assume that each list $A_j$ is sorted according to cost. What we will do is a weighted form of breadth-first exploration of index tuples $(i_1,\dots,i_n)$, storing the current candidates in a (bounded length) priority queue $Q$ according to their cost $A_1[i_1]+\dots+A_n[i_n]$. Initially $Q$ contains just the initial tuple $(0,\dots,0)$.

In each iteration, pop the first tuple $t=(i_1,\dots,i_n)$ off $Q$; this is a cheapest previously unexplored solution. Then generate its successors of the form $t^{(j)}=(i_1,\dots,i_j+1,\dots,i_n)$, compute their cost, and insert them into $Q$ accordingly.

We can avoid creating duplicates by only creating the successors $t^{(j)}$ up to the first index $j$ for which $i_j>0$; e.g. for $t=(0,1,0,2)$ we would only create $(1,1,0,2)$ and $(0,2,0,2)$ (the other tuples $(0,1,1,2)$ and $(0,1,0,3)$ instead get created as successors of $(0,0,1,2)$ and $(0,0,0,3)$, respectively). This eliminates the need for a closed list of explored tuples. We still need to store the priority queue $Q$, but it can be bounded to length $k-j$, where $j$ is the current iteration, with any entries beyond that discarded.

For example, suppose we have $A_1=(1,5,7),A_2=(1,2,5),A_3=(1,3,4)$, and $k=4$.

Initially, $Q=[(0,0,0)]$.
Pop $(0,0,0)$, with cost $3$, and push $(1,0,0),(0,1,0),(0,0,1)$. Their costs are $7,4,5$, respectively, and $Q$ is now $[(0,1,0),(0,0,1),(1,0,0)]$.
Pop $(0,1,0)$ (cost $4$), and push $(1,1,0)$ (cost $8$) and $(0,2,0)$ (cost $7$). $Q$ is now $[(0,0,1),(1,0,0),(0,2,0),(1,1,0)]$; since we only need two more solutions, we can drop the last two, getting $[(0,0,1),(1,0,0)]$.
Pop $(0,0,1)$ (cost $5$), and push $(1,0,1)$ (cost $9$), $(0,1,1)$ (cost $6$), and $(0,0,2)$ (cost $6$). $Q$ is now $[(0,1,1),(0,0,2),(1,0,0),(1,0,1)]$; again, we can drop unneeded entries since we only want one more, getting $[(0,1,1)]$.
Pop $(0,1,1)$; done.

To see that this method is correct, we just need to prove the following:

Given the above restrictions, any index tuple $i=(i_1,\dots,i_k)$ (with $0\le i_j\le size(A_j)$) is reachable along the unique path $(0,\dots,0)\to\dots\to(0,\dots,0,i_k)\to\dots\to(0,\dots,0,i_{k-1},i_k)\to\dots\to i$.
The cost of the tuples along that path is nondecreasing, since the weights are nonnegative.
If there is another tuple $i'$ with a higher cost, and $i'$ is popped off $Q$ during the algorithm, then so are all tuples along the path to $i$ (using induction).
If a tuple $i'$ is discarded due to the length restriction, then there are at least $k$ tuples whose cost is no greater than that of $i'$.


A deterministic FA for $0^*1^*$ is required A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are accepting, $Q_1$ is initial, there is a move under $0$ from $Q_1$ to $Q_1$, a move under $1$ from $Q_1$ to $Q_2$ and finally a move from $Q_2$ to $Q_2$ under $1$.

To construct a DFA, note the following:

An empty string or any string containing only $0$s is accepted, so
any $0^*$ is accepted.
Zero or more $0$s followed by one or more $1$s is accepted, so any
$0^*11^*$ is accepted.
Zero or more $0$s followed by one or more $1$s followed by $0$ is
rejected, so any $0^*11^*0$ is rejected.
Any extension to a rejected string is also rejected (i.e. there is no
route back from a rejecting state to an accepting state), so any
$0^*11^*0(0+1)^*$ is rejected.

This suggests a three state DFA with two accepting states and one rejecting state ...


If O(f) = O(g), why also Θ(f) = Θ(g)? How we can prove that if $O(f(x))=O(g(x))$ then $Θ(f(x))=Θ(g(x))$?

Hint: Follow these steps:

Since $O(f) = O(g)$ then in particular $f = O(g)$ and $g = O(f)$.
Since $f = O(g)$ and $g = O(f)$ then $f = \Theta(g)$ (which is equivalent to $g = \Theta(f)$).
Since $f = \Theta(g)$, if $h = \Theta(f)$ then also $h = \Theta(g)$, and vice versa, and so $\Theta(f) = \Theta(g)$.

It is somewhat confusing that $O(f) = O(g)$ means one thing and $f = O(g)$ means another thing; if $O(f)$ is the collection of all functions $h$ such that for large enough $n$ and some $C > 0$, $h(n) \leq Cf(n)$, then $O(f) = O(g)$ is set equality while $f = O(g)$ should more properly be written $f \in O(g)$.


parsing left linear CF grammars In Introduction to Formal Languages by György E. Révész a polynomial time algorithm that can convert a left linear grammar to a right linear one is presented.

Trying to understand when it is useful I read that left linear grammars are generally harder to parse than right linear grammars.

Is this statement true?

I'm asking because I would say that there is no difference between recognizing the two in terms of hardness, but I found arguments about a difference between them.

In particular in these slides on page 8, the author argues that "left linear grammar are evil" and provides the following example:

Grammar

A → Babc

B → Cb | D

...

with $w = abbabc $.

The motivation seems to be that after checking for abbabc it is necessary to check the first part abbabc if can be derived from B that has 2 rules associated: Cb and D, while it could be done easily with a right linear grammar.

Left- and right-linear grammars define regular languages, and it is straight-forward to convert the grammar into a form appropriate to build an NFA which can recognise the language.

That doesn't say anything about the ease of parsing the grammar, in the sense that parsing transforms a string into a parse tree which relates the various syntactic parts of the string. While we can prove that the regular language can be recognised in linear time and constant space, we cannot say much about the parse tree because there is no guarantee that the parse tree for a given string is unique. In other words, left- and right-linear grammars can be, and often are, ambiguous.

What we can say is that the transformation from left- to right-linear form does not preserve the parse tree; if the intention was to build a particular parse of each string, then the transformation will not help us.

Left-linear grammars cannot be parsed with an LL(k) parser, because no left-recursive grammar can be. However, there is no guarantee that the transformed right-linear grammar will be amenable to LL(k) parsing.

Either a left- or a right-linear grammar might be LR(1), although there are no guarantees. (But every LL(k) grammar is LR(k) so a grammar which is not LR(1) is also not LL(1).) If the intention is to parse, and not just recognise, it seems reasonable to use a grammar which actually reflects the intended syntactic structure, to the extent possible given the constraints of different parsing algorithms.

While it is evident that there are people who feel that their failure to understand the LR parsing algorithm somehow makes it less valuable (or even "evil"), that is not borne out by any objective metric: LR(k) parsers run in linear time and space, just like LL(k) parsers, and can be constructed in polynomial time if the grammar is LR(k). There are readily available tools which will compute the necessary tables for an LR(1) parser, and the parsing algorithm itself, given the tables, is just a few lines of simple code.


Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve? So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty categories? If enough human puzzle solvers were used, the average time for a human to complete a puzzle and the percentage of people who successfully solved the puzzle could be computed for the human sample, and difficulty categories assigned accordingly. But it seems like there should be predictable scenarios that keep appearing as various puzzles are being solved that affect the average human difficulty, which could be automatically detected as a computer solves the puzzle and then these patterns could be assembled into a predicted average difficulty for humans. Are there / what are good techniques to do this? Maybe machine learning with enough training data of human performance on sample puzzles?

There are have been many such attempts. Most of them try to derive deduction rules which humans seem to use to solve Sudoku puzzles.

My money is on this approach:

Mária Ercsey-Ravasz & Zoltán Toroczkai (2012), The Chaos within Sudoku, Scientific Reports 2:75, Nature.

The idea is based around the notion of transient chaos in a dynamical system.

In dynamical systems, when you change the state, there is often a period of time where a transient signal dominates, before the system manages to get itself into a steady state solution. If the dynamical system is nonlinear, the transient may be chaotic.

This is different from a chaotic attractor (e.g. the Lorentz attractor), in that the steady state that the system is eventually drawn to isn't chaotic, just the transients.

The time that the system takes for the transients to die down is called the escape rate. What the authors found is that if you turn the puzzle into a SAT problem, and then turn that into an equivalent dynamical system (where the attractor of the dynamical system is the solution to the SAT problem), the escape rate of the system correlates quite well with how Sudoku puzzles are rated for hardness.

The interesting thing about this approach is that it's independent of Sudoku. Any puzzle which can be turned into a SAT problem fairly directly (the SAT problem and the puzzle can't diverge too far) can be analysed in the same way.


How does automatic differentiation work? What is the intuitive idea behind automatic differentiation?

If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f?

double f(double x, double y)
{
    double res = x*x;
    double res2 = x*y;
    double res3 = res + res2
    return res3;
}

If I read the corresponding Wikipedia entry correctly I need nothing besides the chain rule, but I don't understand how this can be done in practice.

My understanding so far is that I use a table of the derivatives of all involved basic functions, such as:

$dx/dx=1$
$dy/dx=0$
$d(x*y)/dx=y$
$d(x+y)=dx/dx+0$
$d(x^2)/dx=2x$

How do I get the final function from this?

I would expect something like this:

double f(double x, double y, double* dx)
{
    *dx = 0;
    double res = x*x;
    ? *dx = 2*x ?
    double res2 = x*y;
    ? *dx = *dx ?
    double res3 = res + res2
    ? *dx = ??? ?

    return res3;
}

Edit: I have found this video "Beautiful Differentiation" of a talk at the International Conference on Functional Programming (ICFP) 2009, by Marcom Wallace which explains the topic quite well.

The function is given as a "decorated" tree. Your sample function has a root node decorated "+", with one child representing $x^2$ and the other $yx$. The first child has root node "^", with children "$x$" and "2", both leaves. The second child has root node "*" with children "$y$" and "$x$".

In principle, automatic differentiation just applies the rules of differentiation recursively. In your case, we start with $\partial f/\partial x = \partial(x^2)/\partial x + \partial (yx)/\partial x$. To compute $\partial (yx)/\partial x$, we use the product rule:
$$ \frac{\partial(yx)}{\partial x} = y \frac{\partial(x)}{\partial x} + \frac{\partial(y)}{\partial x} x. $$
For variables we know that $\partial x/\partial x = 1$ while $\partial y/\partial x = 0$, and simplification (one of the basic building blocks in any computer algebra system) gives $\partial(yx)/\partial x = y$. It is similar for $x^2$, though here the rule is more complicated: $(f^g)' = f^g (gf'/f+g'\log f)$.

In practice, there are probably some optimizations. Using pattern matching techniques (that is, by having specific rules) we can, for example, recognize $x^2$ for what it is, and directly calculate $\partial(x^2)/\partial x = 2x$. Similarly, if there is a subtree not depending on $x$, we could directly conclude that its derivative with respect to $x$ is zero.


Solving system of linear inequalities I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $

I know these inequalities can be solved using Bellman-Ford algorithm. But there is also another condition. I want to find the solution that maximizes $\ x_n - x_1$

As far as I know the default Bellman-Ford algorithm minimizes it. How do I do that?

The obvious (but perhaps not optimal) solution would be to give it as input to a LP solver.


Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your answers, but I can't really understand Yuval's solution and Matt's solution would be too long for an exam question.
From lecture we were given 3 methods to prove non-regularity. I thought that 3 methods are all classical methods to prove non-regularity, but it seems like the third one isn't so 'classical'.
The third one is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language.
Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.

I'd like to show my proof using this method.

Suppose that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is regular.
We have ${2(n+1)}\choose{n+1}$ = ${2n \choose n+1}{2 \choose {0}} $ + ${2n \choose n}{2 \choose {1}}$ + ${2n \choose n-1}{2 \choose {2}}$.
i.e. ${2(n+1)}\choose{n+1}$ = $2*{2n \choose n}$ + ${2n \choose n+1}$ + ${2n \choose n-1}$  .        $(\ast)$
Then we define $\ L_n = L_{0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}}:=\{ y \in (\Sigma_{bool})^* | 0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}y\in L \} $ for every $n\in \mathbb{N} $.
Let $y_1$ be the first word in $L_n$. Obviously $y_1= $  $0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} $ by $(\ast)$. By the theorem,  there exists a constant $c$ ,such that for any $n \in \mathbb {N}$,
$\ K(y_1) \leq \lceil log_2(1+1)\rceil+c $.
Thus we can bound the Kolmogorov complexity of all elements in $S=\left\{0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} | n\in \mathbb {N}\right\}$ by constant $c$. However, this is an infinite set , we have only limited number of programs of length $\le c$. So we can't bound the Kolmogorov complexity of the elements in $S$, this means $L$ can't be regular.

If you don't know this theorem, you can find it here Proof of non-regularity, based on the Kolmogorov complexity. I don't know if my solution is right or not, if you find any problems please let me know.

A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.

In the same way, we get that the following languages are not regular:
$$
\{0^{\lfloor n\log n \rfloor} : n \in \mathbb N\},
\{0^{n^2} : n \in \mathbb N\},
\{0^{2^n} : n \in \mathbb N\},
\{0^{n!} : n \in \mathbb N\}
$$
and so on.


Recurrence relation and time complexity of recursive factorial I'm trying to find out time complexity of a recursive factorial algorithm which can  be written as:

fact(n)
{
 if(n == 1)
 return 1;
 else
 return n*fact(n-1)
 }

So I write the recurrence relation as

T(n) = n * T(n-1)

Which is correct according to this post: Recurrence relation of factorial

And I calculate the time complexity using substitution method as follows:

T(n) = n * T(n-1)  // Original recurrence relation
= n * (n-1) * T(n-2)
...
= n * (n-1) * ... * 1
= n!

But according to this post, here, both recurrence relation and time complexity are incorrect.

What am I doing wrong or not getting correctly?

Your understanding of how recursive code maps to a recurrence is flawed, and hence the recurrence you've written is "the cost of T(n) is n lots of T(n-1)", which clearly isn't the case in the recursion. There's a single recursive call, and a multiplication of the result.

Assuming the numbers aren't large, the multiplication is constant time, and it's a single operation, not a multiplier on the number of recursive calls:

$$
T(n) = T(n-1) + c_{1}
$$

The base case is $T(1) = c_{2}$

If we simplify things further, and assume $c_{1} = c_{2} = 1$ (it makes no difference to the final asymptotic analysis anyway), you get:

$$
T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = T(n-2) + 2 ...
$$

And the same final result as the StackOverflow question of $T(n) = n$.


Find a regular language that becomes non-regular if you cut away the middle third of all words Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$.
Show that $A'$ is not necessarily regular language.

This is an excercise of Sipser, I've no idea how to construct $A,A'$ please help someone

Hint: Let $A = a^+ b^+ c^+$ and consider $A' \cap a^+c^+$.


Use tree in-order traversal to determine whether a BST or Heap Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

I need to determine whether each one of those lists represent a valid BST / min or max heap, or none.
I was trying to figure how to approach this, but besides brute-forcing every possible option I couldn't figure a "smart" way to solve this.

What indicators can I use, if there are any, or the way to solve this would be literally brute forcing every option?

None of them can be a BST. An in-order traversal of a BST visits the vertices in non-decreasing order of their keys (this is easy to prove by induction).

To determine if they are heaps, notice that by the number of elements in the list you already know the topology of the tree (heaps are completely binary trees up to the one-to-last level, and all the leaves on the last level are packed on the left side). Then the exercise boils down to writing down the given keys in the same order of the traversal and checking if the heap property holds.

In the specific example the first sequence cannot be a in-order traversal of a heap since the resulting tree would have a path with keys $23, 1, 53$ (in increasing order of depth).
The same argument applies to the second sequence for a path with keys $71, 32, 49$.


How again do certain sorting methods use $o(n \log n)$ time? I hope this question isn't too 'soft' for here.  It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this question eight minutes ago but must have misplaced it, so please help me find it again:

Most classical sorting algorithms one reads about are comparison sorts, in which a single comparison produces a binary outcome (let's break ties arbitrarily).  The motivation for this I remember is that they are general, requiring only that an ordering be prescribed over the items, and insensitive to how the items are encoded, but suffer from a $\Omega(n \log n)$-time barrier simply for reason of needing to do enough comparisons to distinguish the $n!$ possibilities.  One then meets algorithms such as radix sort, which is supposed to beat this under caveats such as the space of items being discrete and bounded, and assuming the ability to retrieve any decimal/etc. place in constant time.  But as I recently thought about it, this operation is essentially a $b$-way switch as opposed to the (ordinary) $2$-way kind used in comparison sorts.  Then radix sort would be subject to the same lower bound on time taken since the foregoing gives an improvement of $(\log b)/(\log 2)$ (at most?).  So how is radix sort ever preferable to one of the standard comparison sorts?  I know this is a contradiction, but not how so.

In my experience this kind of paradox typically dissolves when formalised.  I would rather have an intuitive reason that explains it away if such is available, though.

Radix sort cannot be reduced to a comparison-based sort. If the alphabet is binary, then in some sense you are doing 2-way comparisons, since each bit is either 0 or 1. If there are $n$ numbers of width $w$, radix sort takes time $O(nw)$. Therefore as long as $w \ll \log n$, radix sort will be faster than any comparison-based sort.

What does the condition $w \ll \log n$ mean? If numbers have width $w$ then they are in the range $0$ to $2^w-1$. When $w \ll \log n$, there are less than $n$ possible numbers, so some numbers repeat. In this regime you can beat comparison-based sorting.

Another algorithm beating comparison-based sorting in the regime in which there are less than $n$ possible number is counting sort. Suppose that the domain is of size $m$. We initialize an array of size $m$, and count how many elements of each type there are. We can then unpack this histogram into the sorted array. This runs in time $O(n+m)$. If $m \ll n$ then this algorithm runs in optimal $O(n)$ time.

In both of these cases, the algorithms cannot be rephrased in the decision-tree model (try doing it!), and so aren't subject to the limitations of comparison-based sorting. No paradoxes here.


Is the number of NP-complete problems finite? It should be straight forward to show that there are infinitely many NP-hard problems:

Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and yields a yes answer iff a vertex $x \in V$ exists which, when removed from $V$ yields a new graph $G'=(V\backslash\{x\}, \{(u,v) \in E\,|\, u \neq x \land v\neq x\}$ which is a positive instance of $3COL$.

$R1V3COL$ can indeed be reduced to 3-colorability problem (which is proven to be NP-complete) by (as an example reduction) simply removing a vertex from $G$ and testing if $G$ is 3-colorable. If $G$ is not 3-colorable remove another vertex from $G$ and test it. Repeat until there are no vertices left for testing.

Therefore we know $R1V3COL$ is an NP-hard problem.

We can now reduce $R2V3COL$ to a $R1V3COL$ problem (by a similar concept as shown above for $R1V3COL$ to $3COL$ to show that $R2V3COL$ is in NP-hard and so on for every Remove n Vertices 3-COL problem. In other words we can always reduce $R(n)V3COL$ to $R(n-1)V3COL$. Therefore we know that there have to be infinitely many NP-hard problems and we are done.

Now to my Lemma:
I cannot think of a simple proof to show that a certain problem with infinitely many variations (like $R(n)V3COL$) is also in NP to prove NP-completeness and therefore prove that infinitely many problems are in the subclass NP-complete.

As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).


Can an NP-hard problem be polynomial on average? I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this?

If $P \neq NP$, can there be an algorithm solving an $NP$-hard problem with amortized (average case) running time of $O(n^k)$ for a constant $k$?
Are there any problems which are $NP$-hard which are also in $BPP$, or even $PP$?

Can anyone answer or provide a reference answering either of these questions?

It would seem that the question has been answered at CSTheory.SE.

Summary: it is, indeed possible.

For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm.

This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long as it still contains the hard instances, it will be NP-hard, but the probability of success with a fast algorithm will be raised.


NFA for all strings not containing 1010 if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?

the starting state accepts 0,1 so I can essentially take the string 1010 and self loop it in the starting state itself... is that correct?

As mentioned in the comments, your NFA actually accepts all strings. What you have hit upon is the fact that NFAs are not resilient to complementation. Whereas given a DFA for a language, you can turn it to a DFA for the complement of the language by complementing the set of accepting states, the same doesn't hold for NFAs. In fact, "complementing" an NFA (that is, constructing an NFA for the complemented language) could result in exponential blow-up in the number of states!

As an example, consider the language of all words over $\{1,\ldots,n\}$ which do not contain all symbols. There is an NFA with $n$ states accepting the language (the NFA has multiple initial states, which might not be allowed under your definition), but any NFA for the complement must contain at least $2^n$ states. This blow-up is worst possible due to the powerset construction which converts an NFA with $n$ states to an equivalent DFA with $2^n$ states, which can be complemented without increasing the number of states.


What type of math classes are good to take for computer science majors? I am an undergraduate computer science student at Cal Poly (SLO) and I have some flexibility in which math courses I can take, but I don't know which math courses would be most beneficial. I have already taken a statistics/probability course and Calculus 3. My options are pretty flexible for a Mathematics/Statistics elective. What type of math is most useful to know for the field of computer science? I still don't know what type of career I would like, so general answers are okay; or some specific classes for specific career paths would be great too. Thanks!

Discrete maths will be the first priority.

then number theory.


Is $n \log n$ in $O(n^{1.46-\varepsilon})$? I am trying to figure out the solution of the recurrence relation
$$T(n) = 5T(n/3) + n \log n$$ using the Master Method.
I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the part that $\frac{n \log n}{n^{1.46}}$ must be polynomially smaller. If something is polynomially smaller does it mean it can not be bounded either from below or from above (or both)?

When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon > 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$.
This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$.
In other words you want $\frac{g(n)}{f(n)}$ to  grow at least as fast as some polynomial/root of $n$.
In your particular case, $n \log n$ is indeed polynomially smaller than $n^{1.46}$, and this follow from the fact that $n \log n \in O(n^\alpha)$ for any $\alpha >1$.
A a concrete choice of $\varepsilon$, you can pick $\varepsilon=0.1$ yielding $n \log n \in O(n^{1.46-0.1}) = O(n^{1.36})$.
To see this you can consider the limit:
$$
\lim_{n \to \infty} \frac{n \log n}{n^{1.36}} =
\lim_{n \to \infty} \frac{\log n}{n^{0.36}}  =
\lim_{n \to \infty} \frac{1}{0.36 \cdot n^{0.36}} = 0,
$$
where we used L'Hôpital's rule.
In the above, the choice $\varepsilon = 0.1$ was just a convenient value that works, but any choice of $\varepsilon \in (0, 0.46)$ suffices.


How would I prove that the regular expression rejects string? Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$.
Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused on how to explain it.

Any word accepted by this regular expression has to be either in length 3 or to end with $aba$ or $baa$.
Try to prove this fact, and use it to show that $aabaabba$ must be rejected.


Can such an algorithm be written using recursion I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so that the sum of the elements is equal to N. Note that several elements can have the same value.

A simple example to demonstrate this, if N=16, and that we have 3 elements, a, with a value of 3, b with a value of 3 and c with a value of 4, we have:

a+a+a+a+c = 12
a+b+a+b+c = 12
c+c+c+c = 12
b+b+a+b+c = 12
etc...

The algorithm I wrote is pretty straightforward, yet I have a huge trouble making it generic. Indeed, my algorithm depends on the numbers of elements given as input. Here is what I came up with, in pseudo-code:

Input: a list of element (input)
Output: A list of elements so that the sum of their value == N (output)

FOR element_1 IN input
    sum := element_1.value

    IF sum EQUALS N
        output.push([element_1])

    FOR element_2 IN input
        sum := element_2.value

        IF sum EQUALS N
            output.push([element_1, element_2])

        FOR element_3 IN input
            // etc, there will be as much inner for loops are there are elements in input

RETURN output

Note that the algorithm is working, and the results are correct.

The problem here is that my algorithm depends on how many numbers there are in the input list. To be precise, the algorithm will work if there are less elements in the input list than there are inner for loops, and fail otherwise. Thus, I wondered, is this possible to write this algorithm using recursion ? So that I can write a generic code, that will adapt to the length of the input list.

I tried, yet didn't succeed, I don't know much about algorithmic, and I wondered if there are cases where recursion cannot be applied, and if this case is one of them.

Off the top of my head i would perform a recursion this way:

Solve(N,V,target_value):
    if target_value == 0:
        return {}
    if target_value<0 or |V|==0:
        return false
    for 0<=i<N:
        sol = Solve(N-1,V\V[i],target_value-V[i]
        if sol is feasible:
            add [V[i]+sol] to the list of feasible solutions
    if there are any feasible solutions, return them. else return false.

This is obviously pseudo-code that needs to be tweaked a bit. But the general idea is to reduce the problem instance by thinking "If I take element i, what other elements do I have to take?". So assuming you take element i, you reduce the target value and exclude i from the available other elements and perform a recursive call.

The recursion base is reached when:

The target value becomes negative (= we put too many elements into the sack already!)
We used up all elements and still didn't reach the target value! The problem is therefore unsolvable
We reached the target value and can return the current chain of elements. This is done by returning an empty list, which is then filled when the stack is being unwinded (line 9).


How does dynamic memory-allocation exactly work? I have wondered about ordinary code. Assume we are running this code on any modern System like Unix/Linux/Mac/Windows. This code is C, but it should work with every language which is close to the hardware.

int a = 8;
//printf("%d", (int)&a);

This will show obviously that the system allocated the int dynamically. So there is no static address used. Now we continue by:

a = a+1;

Now, my question follows:

Since the address to "a" is allocated dynamically, we need presumably a pointer which points to a pointer pointing to "a". But how do we store this pointer? We would again need a dynamically allocated address and would, therefore, pass the problem. So, in my mind, we need static addresses the program can use, but how does the process know these addresses?

How does the process store its own allocations, so that after initializing a variable, the process knows what the variable actually is or at least where the variable was allocated?

If this question is not clear enough, please comment below.

Thank you!

Consider the following code:

int a = 8;
a = a+1;

On my system, this snippet compiles to the following code:

movl    $8, -20(%rbp)
movl    -20(%rbp), %edi
addl    $1, %edi
movl    %edi, -20(%rbp)

The register rbp points at the top of stack. The variable a is located 20 bytes below the top of stack.

The first assembly line about implements the C line int a = 8, and the rest implement a = a+1 by first loading a into the register edi, then increasing edi by 1, and then storing edi back at a.

If you want to try it out, use the following command:

cc -O0 -S <progname>.c

The assembly will appear in <progname>.s.


Consensus algorithm for imperfect annotators I'll pose the question in the abstract first and then describe concretely what I'm trying to do.
Suppose I have a set of 1000 000 multiple-choice questions and 10 oracles that can answer the questions. But the oracles are imperfect and don't always answer correctly. Some oracles answer more accurately than others. We don't know which ones are better beforehand though. All answer correctly with probability greater than 60% and less than 100%.
Suppose each oracle answers 100 questions. One in every 10 questions, however, is not a new question but a (random) question that a different oracle has already answered. Which lets you check whether they each got the same answer or not.
Now my question is this, suppose I want to rank the oracles at the end in order of most reliable to least reliable, what's the best metric?
Naively, we could just ask, which oracle had the highest proportion of co-coinciding answers out of all the questions they answered that were also answered by another oracle. But this ignores that fact that if an oracle's answer disagrees with a different oracle, it could be the different oracle that was wrong.
So I think there needs to be a way to scale the penalty based on the rating of the oracle that disagreed.
Is there an algorithm for this sort of ranking?
The two that came to my mind are the Buchholz system, and page rank. Because they both consider secondary comparisons, not just direct comparisons. But I'm not sure how I could apply them.
Concrete context: I have lots of annotators annotating data. We get to send some of the data to multiple annotators, but not all of it. I'm looking for a way to identify annotators who perform poorly so that I can either remove their annotations or reduce the weight of their annotations.

Technically speaking, you can't.  If you flip all of the oracle outputs, then it maintains the same level of agreement but reverses the ranking.
But this is probably a trivial case that's unimportant in practice.  Suppose we can assume that every oracle has accuracy that's at least 50%.  Then one approach would be to take all questions that are rated by at least three oracles, take the majority vote among all oracles that rated it, and then measure agreement with that majority.  I think that should give a correct ordering of the oracles, given enough data (i.e., in the limit, as the number of data points goes to infinity, it should converge to the correct ordering).
In practice you could consider using a more sophisticated model that captures both differences in the accuracy of each oracle and differences in the difficulty of each question.   I'm not sure whether this will lead to a major difference in outcomes significantly, but there is tons of work in the research literature you could read about to see what methods have been studied.  Here are some example papers:

Online crowdsourcing: rating annotators and obtaining cost-effective labels, Welinder et al.

Lean crowdsourcing: Combining humans and machines in an online system, Branson et al.

Get another label? improving data quality and data mining using multiple, noisy labelers, Sheng et al.

Max-Margin Majority Voting for Learning from Crowds, Tian et al.

Active visual recognition with expertise estimation in crowdsourcing, Long et al.

and probably many more - I'm not expert on this topic, so I have no idea whether these are the most important or useful papers, so I suggest doing a literature search of your own.


What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot? If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at 1 and 1, then what would happen? If they are switched, nothing is really sorted. And the same goes for the two indexes both landing on numbers greater than the pivot, for example, 7 and 7. How would Hoare's algorithm handle such a case?

You've misunderstood the algorithm and it doesn't have the behaviour you suggest.

Let the pivot value be $p$. The algorithm searches from the left for a value $\ell\geq p$ and from the right for a value $r\leq p$. It then only swaps them if they're in the wrong order relative to each other, i.e., if $\ell>r$, so it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.


Is there any scenario whereby randomly shufflying a sequence improves it's compressibility? I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1.

You take a test sequence and compress it with a standard compression algorithm. You then shuffle that sequence randomly using a PRNG, and re-compress.  We expect that the randomly shuffled sequence to be harder to compress as any and all redundancy and correlations will have been destroyed. It's entropy will have increased.

So if there is any auto correlation, $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} > 1$ .

This works using NIST's recommended bz2 algorithm, and on my data samples, the ratio is ~1.03.  This indicates a slight correlation within the data. When I switch to LZMA, the ratio is ~0.99 which is < 1. And this holds over hundreds of runs so it's not just a stochastic fluke.

What would cause the LZMA algorithm to repetitively compress a randomly shuffled sequence (slightly) better than a non shuffled one?

I now think that it's because of this:-

  ZPAQ has 5 compression levels from fast to best. At all but the best level, it uses the statistics of the order-1 prediction table used for deduplication to test whether the input appears random. If so, it is stored without compression as a speed optimization.

... from https://en.wikipedia.org/wiki/ZPAQ#Compression

I'm referring to LZMA in my question, but I'm not familiar with how it's implemented in code. If it followed the same speed optimisation strategy as ZPAQ, the hypothesis would be consistent with my observations. You can imagine in edge cases where $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} = 1 - \epsilon $, that an $n$ order predictor decides that there is insufficient advantage to be had due to the necessary compression encoding overhead. My $\alpha \approx 0.01$, but recently I've seen it as high as 0.04.


Turn words array from a document with their coordinates into sentences I have an array of words with their coordinates in the document, I want to turn them into sentences.
For example this:

  [
    {
        "bounds": [
          {
            "x": 10,
            "y": 10
          },
          {
            "x": 15,
            "y": 10
          },
          {
            "x": 15,
            "y": 15
          },
          {
            "x": 10,
            "y": 15
          }
        ],
        "desc": "Hey"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 10
          },
          {
            "x": 24,
            "y": 10
          },
          {
            "x": 24,
            "y": 15
          },
          {
            "x": 18,
            "y": 15
          }
        ],
        "desc": "Name"
      },
          {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "What"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "Sup"
      }
]

Should Have turned into this:

Hey Name
What Sup

The coordinates are not accurate just an example, also the algorithm needs to deal with words that are in the middle of sentences and other extreme cases.

What it the best way I can do it (Ideally implemented with JavaScript)?

On this site, we only care about algorithm itself and not javascript. From what I gathered, your problem statement (without the javascript part) is:

  Given a set of rectangles in described in Cartesian coordinate,
  (1) partition the set into "lines"
  (2) sort rectangles within each "line" by their position along the "line"

The reason I put the word "line" in quotation is because there are many ways to define it, and you didn't give enough information to decide which one.

Let's formulate this a bit: we are given

set $S$ of rectangles
four functions $t,b,l,r \colon S \rightarrow \mathbb{N}$ standing for top, bottom, left and right coordinate of the rectangle respectively.

We need to output:

ordered partition of $S$ such that "each partition is a line"

For convenience, I'm going to let $\sim \subseteq S \times S$ denotes the equivalence relation that partition $S$ into lines.

Here are three separate (not exhaustive) examples of definition of a line:

Two rectangle is in the same line if they have the same bottom $y$ value.$$x \sim y \iff bx = by$$
A rectangle is in the same line with its nearest neighbour in $y$ direction that is not further than some threshold.
$$y = min_z |bx-bz| \implies (|bx-by| \leq T \implies x \sim y)$$
don't forget to make $\sim$ transitive.
Decide on the direction of a line first which may not be parallel to $x$ axis. Change the basis of coordinate. Then apply one of the above.

Decide on one you want according to the degree of sophistication needed to handle your input. Once you have the partition (supposed by $y$ value), you can then sort each by $x$ value.

Finally, there is also the alternative to do Hough Transform which is also generally applicable to bitmap images. In our case, our image is one of rectangles (or centre of rectangles, or corner of rectangles).