Method for finding correlation between data sets Let's say that I have $N$ data sets where I have data points at some fixed frequency, such as "daily".

What would be a good method for finding correlation between any of the data sets, or choosing a single data set, and asking what other data sets are most correlated?

To make it less abstract, imagine that I'm logging how much water I drank a day in ounces, how much exersize i did a day in minutes, my mood level, and how bad of a headache I had that day from 1 (no headache) to 10 (bad headache).  I'd want to be able to see if my headaches were correlated (keeping in mind, it might not be causation) to me drinking less water perhaps, or doing less exercise.  However, it's possible that there may be a lag between cause and effect (or correlation), etc.

That's my basic question, but in case it's relevant to the answer, I'm also wondering how I might be able to handle missing data (maybe some days didn't get data?).

Also, I was wondering what if the data sets AREN'T at the same frequency?  Like one data set may be weekly while the others are daily.

My best guesses at how to approach this could be to use a discrete Fourier transform of each data set, and then do a dot product between the frequency histograms to find ones that had similar frequencies (even if different phases), and then I could use the phase information to figure out the kind of lag time there is.

Since I'm also interested in negative correlation, I'm thinking that when i do the dot product between the histograms and get my 0 to 1 answer, that i would report "correlation" as $abs(dotProduct-0.5)$ so that things close to either 0 or 1 were treated as important.

Is there a better way? Is my best guess a reasonable approach?

Thanks!

Let's start with comparing two time series.  To compare them, you probably want to use cross-correlation.  The cross-correlation computes the correlation between signal $f$ and a delayed version of signal $g$, for all possible delays.  An efficient way to compute the cross-correlation is indeed by using a FFT, taking the product, and then applying an inverse FFT.

Now suppose you have $k$ time series.  I think the best you can do is to compute the cross-correlation between each pair of time series.  This requires ${k \choose 2}$ cross-correlation computations.


Proving that a Turing machine decides a language in NP Suppose a deterministic Turing machine T decides language L and L is in NP. Then must it be provable in ZF that T decides L?

In general, ZF does not prove that $T$ decides $L$, unless ZF is inconsistent.

Take e.g. $L$ to be the language of words having even length (which is in P, hence in NP).

Consider the TM $T$ which on input $w$, crafts the first $|w|$ proofs in ZF.
If any such proof proves a contradiction, accept.
Otherwise, accept if and only if $|w|$ is even.

We note that $T$ decides $L$ if and only if ZF is consistent. So, if ZF can prove that $T$ decides $L$, it is proving its own consistency, hence by Godel's second incompleteness theorem ZF is inconsistent.


Is structural induction on terms applicable when a function is involved? Assume an evaluation-relation on terms $t \Downarrow v$. If I want to prove correctness of a function $\phi$ w.r.t. evaluation, I have to show that the following implication always holds:

$$\frac{\phi(t) \Downarrow \phi(v)}{t \Downarrow v}$$

Naturally, this is a candidate for structural induction. But on what structure? Is it sufficient to run the induction over terms, or do I have to run it over the derivation tree? Structural induction is usually only allowed for direct sub-terms, but the function could, in principle, yield completely different results.

Is it sensible to consider $\phi$ part of the promise or do I have to consider it a part of the recursive structure?

You probably shouldn't write $\cfrac{\phi(t)\Downarrow \phi(u)}{t\Downarrow u}$ for "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

I'll take a concrete example: Terms are made using $0,S,+$. And there are six rules:

$$\cfrac{}{0 \Downarrow 0}(0)\hspace{2em}\cfrac{x\Downarrow y}{Sx \Downarrow Sy}(S)\hspace{2em}\cfrac{x\Downarrow y}{x+0 \Downarrow y}(+0)\hspace{2em}\cfrac{x\Downarrow y}{0+x \Downarrow y}(0+)\hspace{2em}\cfrac{x+y\Downarrow z}{x+Sy \Downarrow Sz}(+S)\hspace{2em}\cfrac{x+y\Downarrow z}{Sx+y \Downarrow Sz}(S+)$$

Note that $(0+)$ and $(S+)$ are superfluous (but do not break the uniqueness of the normal form).

I'll provide three examples where different proof techniques apply.

Let's take $\phi(x)=Sx$.

Suppose that for some $a$, $Sa=\phi(a)\Downarrow \phi(b)=Sb$. The only rule that allows you to prove this is the rule $(S)$ with $x=a$ and $y=b$ (because it's the only rule that can have successor on both sides of $\Downarrow$ in the conclusion), so you must have $a\Downarrow b$, which is what you want. So you can prove that "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

You were able to prove it without even using induction because the definition of $\phi$ wasn't inductive.

Remark

But you can not compose rules to get $\cfrac{St\Downarrow Su}{t\Downarrow u}$ (because there are more $S$ in the conclusion than in the premise and all rules have at most as many $S$ in the conclusion as in the premise).

Your result is a meta-theorem but not a theorem (because it's not just a combination of the rules).

A theorem would, for example, be $\cfrac{}{S0\Downarrow S0}$ (that you get by composing $(0)$ and $(S)$ or $\cfrac{x\Downarrow y}{x+S0\Downarrow Sy}$ (that you get by composing $(+0)$ and $(+S)$).

Let's take another example: $\varphi(0)=0$, $\varphi(Sx)=SSx$ and $\varphi(x+y)=\varphi(x)+\varphi(y)$.

Now suppose that $\varphi(a)\Downarrow \varphi(b)$.

We'll prove $a\Downarrow b$ by induction on the size of the proof of $\varphi(a)\Downarrow \varphi(b)$.

If it's of size $1$, then it has to be just an application of $(0)$ so $\varphi(a)=0=\varphi(b)$ and so $a=0=b$ and $(0)$ gives us the proof we want.

If it's of size $>1$, the last rule is not $(0)$ so you do case analysis and apply the induction hypothesis on the premise of the rule. You'll have to do case analysis, but you should be able to prove that it works.

There should be some case where you can do induction on terms to prove the thing but I couldn't find one. It feels more natural when you have a small step transition system $\to$ and define a big step one $x\Downarrow y$ by $x\to^* y$ and for any $z$, $y\not\to z$. Then, it you manage to prove that $\phi(x)\to \phi(y)$ implies $x\to^+ y$ and that $x\to y$ implies $\phi(x)\to^+\phi(y)$, you will get that $\phi(x)\Downarrow \phi(y)$ implies $x\Downarrow y$.

The main thing you should remember is that "case analysis" < "induction on terms" < "induction on proofs" in terms of what you can proove but often, the number of cases you have to handle often grows. So you should try the proofs techniques in that order until you get one that works.


Infix vs postfix vs prefix - which has the smallest processing time Infix, prefix (polish notation) and postfix (reverse polish notation) are all forms of arithmetic operations. As I understand it, infix is what we use in maths where the rules of BODMAS (Bracket, Order, Division and Multiplication, Addition and Subtraction) are used to decide what order the operations are used in. I can understand this being more computationally expensive to calculate than pre/post fix as the processor would have to reorder the equation so that it follows BODMAS. However, I do not understand why there is both prefix and postfix as they just change the order of tree traversal, so logically would take the same amount of processing time as each other. Is there any reason for choosing one over the other, and is my belief of infix being slower than post/prefix correct?

You can express the same in prefix and postfix without brackets.

For example, a + b * c can be ambiguous so it can give 2 different results so you need some precedence to solve the expression(as you have mentioned BODMAS) but both the trees if traveled in prefix or postfix leads to a unique results like (a + b) * c will have postfix ab+c* and a + (b * c) will have abc*+.


What algorithm should I use to find a minimal tree that include certain nodes within a graph? Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or the total amount of edge weight) included in the tree is minimum.

This is the famous Steiner tree problem in graphs, which is known as NP-hard.


Union grouping in bipartite graphs? I'm trying to figure out a good (and fast) solution to the following problem:

I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on multiple teams and a team can have multiple players). I'm working on creating a UI element on a form that allows a user to select multiple teams (checkboxes). As the user is selecting (or deselecting) teams, I'd like to display the teams grouped by the players.

So for examples:

If the selected teams have no common players, each team will have its own section.
If the user selects two teams and they have the same players, there would be one section containing the names of the two teams and all the players.
If TEAM_A has players [1, 2, 4, 5] and TEAM_B has players [1, 3, 5, 6]. There would be the following sections: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION _Z = [TEAM_B, 3, 5]

I hope that's clear. Essentially, I want to find the teams that players have in common and group by that. I was thinking maybe there is a way to do this by navigating a bipartite graph? Not exactly sure how though and I might be overthinking it. I was hoping to do this by creating some type of data structure on the server and using it on the client. I would love to hear your suggestions and I appreciate any help you can give!

I'll present an algorithm by example. Initialize a list of lists containing a list containing all of the players.

[[1, 2, 3, 4, 5, 6]]

For the first team, TEAM_A, replace each list by two lists, where the first list contains TEAM_A and the players on TEAM_A and the second list contains the players not on TEAM_A. Duplicate all of the existing team entries in both lists (none here).

[[TEAM_A, 1, 2, 4, 5], [3, 6]]

Discard all lists with no players (none here). For the second team, TEAM_B, replace each list by two lists, where the first list contains TEAM_B and the players on TEAM_B and the second list contains the players not on TEAM_B. Duplicate all of the existing team entries in both lists.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6], []]

Discard all lists with no players.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6]]

Well implemented, this should run in time proportional to the product of the number of teams and the number of players.


Are graphic cards using the Map-Reduce model when performing typical gaming rendering I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. However when reading about the graphic pipeline I am not sure if there is a point at which the Map Reduce model is used. If not, what kind of parallel computations (just the general model of them so I could read more about it) are done during the typical rendering process of modern graphics cards? If it is used, where would that be on the below pipeline?

This model isn't appropriate for rendering games, so it's not used in game engines. However, it can be implemented on GPUs. F.e. if you are going to implement Spark / relational algebra on GPUs, it may be a part of implementation.


Prove the probability of which a hash function is collision-free Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct points in $\{0, 1\}^n$. If we choose $h$ randomly form $H$ and let $E$ be the event that $h(x_1), ..., h(x_M)$ are all distinct. We need to show that $Pr[E] \ge \frac{3}{4}$.

$\textbf{Markove's inequality:}$ If $X$ is a random variable which only takes non-negative values then, for any $t \ge 0$, $Pr[X \ge t] \leq E[X]/t$.

The idea is to compute $Pr[h(x_i) = h(x_j)]$, compute the expectation of the random variable $Z = |\{(i,j) : h(x_i) = h(x_j)\}|$ and use the Markove's inequality to prove the question.

For two independent points $x_i$ and $x_j$, the probability that $h(x_i)$ and $h(x_j)$ are equal is $1 - \{\text{the probability two independent points has the different hash values}\}$, which is $1 - \frac{2^{n/2}}{2^{n/2}}\cdot \frac{2^{n/2} - 1}{2^{n/2}}$. That shows $Pr[h(x_i) = h(x_j)] = \frac{1}{2^{n/2}}$.

As for the random variable $Z$, maybe we can let $Z_{i,j} = 1 \text{ if }h(x_i) = h(x_j)$. Otherwise, $Z_{i,j} = 0$. Then we can get $Pr(Z_{(i,j)}) = \frac{1}{2^{n/2}}$. This is where I stuck. I know how to compute the expectation the single random variable, which is $\sum_{i=1}^{n} x_i P(X = x_i)$. But I have no idea how to expand this formula to the pair random variable $(i,j)$. Also I am a little confused how Markove's Inequality could be used in this proof.

Could someone give me some hints? Any help would be appreciated. Thanks in advance.

For every $i < j$, the probability that $h(x_i) = h(x_j)$ is at most $2^{-n/2}$. The number of pairs of indices $1 \leq i < j \leq M$ is $M(M-1)/2 < M^2/2 = 2^{n/2}/200$, hence a union bound implies that the probability that $h(x_i) = h(x_j)$ for some pair $i < j$ is at most
$$
2^{n/2}/200 \cdot 2^{-n/2} = 1/200.
$$
It follows that the probability that $h(x_1),\ldots,h(x_M)$ are all distinct is at least $199/200$.


Find a hole while travelling along an infinite wall There is an infinite wall with a hole somewhere, you are placed on that wall at an unknown position. Let the distance between your initial position & the hole be $x$. Find the average distance traveled in terms of $x$ until you find the hole. What's the complexity of this problem in terms of $x$ and how does an algorithm look like that solves it?

If you can go only left or right, than you can do the following strategy:

DIRECTION = Right
For i = 0 to infinity do:
    Go 2^i steps to DIRECTION.
    Go back to the initial place.
    CHANGE_DIRECTION
    STOP if you found the hole

If the distance between the start place and the hole is n, you will find the hole within O(n) steps. You can easily calculate the exact average number of steps given this algorithm.


In a DFA, does every state have a transition on every symbol of the alphabet? If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?

You seem to have stumbled on a contentious issue.  Apparently computer scientists like to argue.  I certainly like to argue, so here goes!

My answer is an unequivocal: No.  A deterministic finite automata does not need a transition from every state for every symbol.  The meaning when $\delta(q,a)$ does not exist is simply that the DFA does not accept the input string.

While you can create a definition of DFA that requires that $\delta(q,a)$ does exist, it is simply not the case that a missing transition makes the resulting structure (whatever you call it) in any way nondeterministic as many of the commenters are claiming.  If you are taking a course on automata theory then the next topic will be context-free languages and push-down automata where the distinction between nondeterministic and deterministic automata is crtical, and you need to use the correct definition of non-determinism.

Non-determinism is associated with having more than one legal transition.

I think we all agree with the following Wikipedia definition (which I'll show in just a second is slightly ambiguous):

A deterministic finite automaton $M$ is a 5-tuple, ($Q$, $\Sigma$, $\delta$, $q_0$, $F$), consisting of

a finite set of states ($Q$)
a finite set of input symbols called the alphabet ($\Sigma$)
a transition function ($\delta : Q \times \Sigma \rightarrow Q$)
a start state ($q_0 \in Q)$
a set of accept states ($F \subseteq Q$).

Let $w = a_1 a_2 \cdots a_n$ be a string over the alphabet $\Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r_0, r_1, \ldots, r_n$, exists in $Q$ with the following conditions:

$r_0 = q_0$
$r_{i+1} = \delta(r_i, a_{i+1})$, for $i = 0, \ldots, n−1$
$r_n \in F$.

The ambiguity, and the controversy is over the defintion of the transition function, $\delta$ (number "3" in the first bulleted list.)  We all agree that what differentiates a DFA from an NFA is that $\delta$ is a function rather than a relation.  But is $\delta$ a partial function or a total function?

The definition of the DFA works just fine if $\delta$ is a partial function.  Given an input string, if you reach a state $q_i$ with an input symbol $a_j$ where there is no next state then the automata simply does not accept.

Moreover when you extend this definition to create the definition of push-down automata it will be the case that you must make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic.

If the partial function bothers you then here is a trivial transformation that makes $\delta$ a total function.  (This transformation is not like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs.  None of those facts is true of the subset construction algorithm.)

add a state $q_{\mathrm{error}}$
for every pair $(q_i, s_j)$ where $\delta$ is undefined, define $\delta(q_i, s_j) = q_{\mathrm{error}}$.

This automata has a $\delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.

Edit, January 2019

Commenter @Alex Smart rightly critiques me for neither giving references, nor for explaining why we should care.  So here goes:

The reason we care about the exact definition of determinism vs non-determinism, is that some classes of non-deterministic automata are more powerful than their deterministic cousins, and some classes of non-deterministic automata are not more powerful than their deterministic cousins.  For finite automata and Turing machines the deterministic and non-deterministic variants are of equivalent power.  For pushdown automata there are languages where the distinction is important: There are NPDA that accept the language, and no DPDA accepts the language.  For the linear bounded automata the question is (or was last time I checked) open.  The increase of power of NPDA over DPDA comes from allowing multiple transitions, not from turning the transition function from a total function to a partial function.

Books from the compiler community:

Aho and Ullman, Principles of Compiler Design, 1977: First defines NFA (page 88) with a transition relation, then (p. 90-91):

  We say a finite automaton is deterministic if
  1. It has no transitions on input $\epsilon$.
  2. For each state $s$ and input symbol $a$, there is at most one edge labeled $a$ leaving $s$.

Aho, Sethi, and Ullman, Compilers, principles, tecniques, and tools, 1988 reprint, is similar, it first defines NFA with a transition relation, then (p. 115-116):

  A deterministic finite automata (DFA, for short) is a special case of a non-deterministic finitie automaton in which ... there is at most one edge labeled $a$ leaving $s$.

(Note that in the comments @Alex Smart says, "the dragon specifically mentions that the function is total."  I assume he is talking about the later edition with co-author Lam, which I don't have access to at the moment.)

Appel, Modern Compiler Implementation in Java, 1988 (p. 22):

  In a deterministic finite automaton (DFA), no two edges leaving from the same state are labeled with the same symbol.

Appel then goes on to explain that when using DFA to recognize longest matches we explicitly make use of the missing transitions to decide when to stop (p. 23):

  when a dead state (a nonfinal state with no output transitions) is reached, the variables [which record the longest match we've seen so far] tell what token was matched, and where it ended.

Books from the switching-theory community:

Kohavi, Switching and Finite Automata Theory, 2/e, 1978, p. 611 says:

  Because a state diagram describes a deterministic machine, the next state transition must be determined uniquely by the present state and the presently scanned input symbol.

I would typically interpret uniquely to mean "exactly one", not "no more than one".  (I.e., Kohavi seems to be saying that determinism requires a total function)

Books from the theory-of-computation community:

Here it seems to be more common to define DFAs before NFAs, and require DFAs to have a total transition function, but then define NPDAs before DPDAs, and define "determinism" as being a restriction of the transition relation to having no-more-than-one entry for each state/symbol pair.

This is true of Hopcroft and Ullman, 1979, Lewis and Papadimitriou, 1981, and, especially of Sipser, 2006, who uses the definition of DFA pedagogically to introduce precise formal definitions, and explain their importance and explicitly says (p.36):

  the transition function, $\delta$, specifies exactly one next state for each possible combination of a state and an input symbol.

This seems to follow the historical development.  Deterministic finite automata were introduced in the 40s and 50s.  Non-determinisitc finite automata were introduced in the paper by Rabin and Scott, "Finite automata and their decision problems, IBM J. Rsrch and Dvpt, 3(2):114-125, 1959.  Following earlier authors, Rabin and Scott define deterministic finite automata (which they call ordinary automata) as having a transition function "defined on the Cartesian product $s\times\Sigma$ of all pairs of states and symbols."  (Which I would interpret as meaning a total function).

Interestingly Rabin and Scott, also define non-deterministic finite automata in terms of a total function!  Page 120, Definition 9:

  A nondeterministic (finite) automaton ... is a system where ... $M$ is a function[!] of $S\times\Sigma$ with values in the set of all subsets of $S$.

That is: the transition function being total does not make the system deterministic!

Sipser 2006 follows Rabin and Scott and uses a total transition function from states/symbols to the power set of states for his definitions of non-deterministic finite automata, non-deterministic PDA, and non-deterministic Turing Machines, but skips the topic of deterministic PDA.

Both Hopcroft and Ullman, 1979, and Lewis and Papadimitriou, 1981 use partial functions in their definitions of deterministic PDAs.  They first define NPDAs with a transition relation, and then when they get to PDAs, Lewis and Papadimitriou say (p. 135),

  A pushdown automaton is deterministic, intuitively speaking, if there is at most one transition applicable to each configuration.

While Hopcroft and Ullman say (p. 112):

  The PDA ... is deterministic in the sense that at most one move is possible from any ID.


Proving special case of SAT is in P Let SAT-100 be the following problem:

Input: Any boolean logic formula

Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.

This is the description of a problem that is apparently in $P$. (old exam question)

I have tried to design an algorithm but I got stuck, so here it goes:

Input: boolean logic formula F
    If(count(variables in F)) < 100:
       return false
    else
        # try all combinations of input variables

And here is the problem: building and evaluating all combinations of input variables can't seem to be polynomial because:

$$ { n \choose 100} = \frac{n! }{100!  \cdot (n-100)!} \in \mathcal{O}(n!)
$$

and this nasty factorial can't be bounded with any polynomial that I know of.

I don't think  the exam is wrong, so I must have overlooked something.

Note that
$$\frac{n!}{(n-100)!100!}<\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)< n^{100}.$$

Thus, your algorithm runs in polynomial time


Computing set difference between two large sets I have two large sets of integers $A$ and $B$.  Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long.

What is the best algorithm to compute $A\setminus B$ and $B\setminus A$? In other words, how can I efficiently compute the list of entries of $A$ that are not in $B$ and vice versa?  What would be the best data structure to represent these two sets, to make these operations efficient?

The best approach I can come up with is storing these two sets as sorted lists, and compare every element of $A$ against every element of $B$, in a linear fashion.  Can we do better?

If you are willing to store the sets in a specialized data-structure, then you can possibly get some interesting complexities.

Let $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Then you can do set operations $A\cup B, A\cap B,A\setminus B$ and $A\Delta B$, each in $\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$ expected time. So essentially, you get the minimum size of the two sets, or, the size of the symmetric difference, whichever is less. This is better than linear, if the symmetric difference is small; ie. if they have a large intersection. In fact, for the two set-difference operations you want, this is practically output-sensitive, since together they make up the size of the symmetric difference.

See Confluently Persistent Sets and Maps by Olle Liljenzin (2013) for more information.


Subsampling of Frequent Words in Word2Vec I am reading through the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

Under section 2.3 on page 4 the authors discuss subsampling of frequent words.

Now based on my understanding of subsampling of frequent words, the goal is to reduce the number of times we sample frequent words. But here is what the paper states:

"To counter the imbalance between the rare and frequent words, we use a simple subsampling approach: each word $w_i$ in the training set is discarded with probability computed by the formula

$$P(w_i) = 1 - \sqrt{\frac{t}{f(w_i)}}$$

where $f(w_i)$ is the frequency of word $w_i$ and $t$ is a chosen threshold typically around $10^{-5}$."

Now, I am interpreting $f(w_i)$ as an integer value that essentially counts the number of times $w_i$ occurs in the corpus. But this seems to not make any sense because all words then discarded with probability $.99$ or greater. Should I instead be interpreting $f(w_i)$ as $\text{count}(w_i)/\text{total_count}$ where $\text{total_count}$ is the number of words in the corpus?

My guess is that we should regard $f(w_i)$ as a number between 0 and 1, i.e., the number of times word $w_i$ appears divided by the number of words.  This makes it an estimate of the probability of occurrence of word $w_i$.

Then the formula seems to lead to reasonable results.  If you have a very frequent word (appears as a $10^{-3}$ fraction of the words), we have $P(w_i) = 1 - \sqrt{10^{-2}} = 0.9$, so it's very likely to be discarded.  If you have a moderately infrequent word (probability of occurrence $10^{-5}$), then we have $P(w_i) = 1 - \sqrt{1} = 0$, so it won't be discarded.  If you have a word that is even rare than that, it won't be discarded either.  So this discards very frequent words with high probability and keeps almost all words that are rare or moderately rare.


Commonly used Error Correcting Codes We know error correcting codes are parameterized as (n,k,d) codes. I wanted to know the values of these parameters for some commonly used error correcting codes in computer memories or in DRAMs, etc.

I just wanted to see some values for these parameters, used in real life applications.

I'm sure this greatly varies according to the application and the specific code in use.

Though not for DRAMs, maybe this will give you some insights:

  For CDs encoding, a (28,24)-Reed Solomon code is used.
  For DVDs, it is a (208,194)-Reed Solomon code.

Symbols are over $GF(2^8)$, that is, 8 bits per symbol.  The notation is $(n,k)$-ReedSolomon for a linear $[n,k,d]$ code ($k$ being the dimension). RS is an MDS code and has $d=n-k+1$.

(I think this was the source, but maybe you can find it online):
Stephan Wicker and Vijay Bhargava (eds.), Reed-Solomon Codes and their Applications, IEEE Press, 1994


center selection problem: Simple greedy algorithm I am trying to understand the following text which defines a greedy algorithm for center selection problem:

  It would  put the first center at the best possible location for a
  single center, then keep  adding centers so as to reduce the covering
  radius, each time, by as much as  possible. It turns out that this
  approach is a bit too simplistic to be effective:  there are cases
  where it can lead to very bad solutions.

  Kleinberg, Jon. Algorithm Design (p. 607). Pearson Education. Kindle
  Edition.

Is the term "single center" typo for "single site"?

Some body please guide me how by adding centers we can reduce the covering radius?

Zulfi.

Given a set of points, the task is to find a set of centers minimizing the covering radius, defined below. The centers themselves could be arbitrary points in space, or sometimes must be selected among the points or among a set of potential centers.

The covering radius is the minimum $r$ such that each point in the set is at distance at most $r$ from a center. Clearly, adding centers can only reduce the radius, and in general it does. As a very extreme examples, given $n$ distinct points, for any $n-1$ centers that we choose, the covering radius will be positive, while if we take all the points as centers, the covering radius drops to zero.

As another example, consider three points on the real line at locations $-1,0,1$. The best choice for a single center is $0$, with covering radius $1$. The best choice for two centers is $-1/2,1/2$, with covering radius $1/2$. However, if we first put a center at $0$, no choice for the second center will reduce the covering radius.


A graph in descriptive complexity - is $x$ already a vertex? So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use relation like $v(x)$ to say that $x$ is a vertex?

(First-order logic) formulae are independent of structures; you just have variables, predicates and possibly functions (in addition to the syntactical symbols). To decide whether a formula $\varphi$ is true in a given structure $S$ (consisting of a universe of individuals $U$ and an interpretation of predicates $I$), i.e. whether $S$ is a model of $\varphi$, you apply the semantic rules of first order logic.

Concerning your specific question: if you have $\varphi = \forall x: F$ where $F$ is some formula, then $x$ denotes exactly all vertices iff you defined your structure $S = (U,I)$ such that $U$ contains exactly all vertices. Note that if you do that and want access to the edges, then you'll need to define some predicate $e(x,y)$ such that $e(x,y) \Leftrightarrow \text{there is an edge between } x \text{ and } y$.

More generally: the quantifiers do not differentiate between elements of your universe, the predicates will have to do that. If you want to check $F$ only for all vertices but your universe contains elements that are not vertices, then you do what you suggested: introduce a predicate $v(x)$ and use $\varphi' = \forall x: (v(x) \rightarrow F)$


How does a Single Pass Compiler does parsing,analyzing and generating code all at once? I would like to know how a single pass compiler does parsing,analyzing and generating code all at once as said in P.14 of SIngle Pass Compilers.Is it possible to do all these at once since you can't generate an code without parsing or analyzing it which should be done earlier before producing the object code?

PROGRAM Demo
{
  INTEGER i;
  i= 4;
  WRITELN(i + 5);
}.

Line 1: enter the program name in the symbol table. Generate the program prologue.
Line 3: enter the declaration of variable i in the symbol table.
Line 4: evaluate the constant expression and generate code for the initialization of i.
Line 5: parse the function call and the argument expression. Generate code for the evaluation of the expression i + 5, the push on the stack and the call of the WRITELN predefined function.
Line 6: Generate the program epilogue.

Done.


Applying subproblem technique to permutations with grouping I am trying to apply overlapping subproblems and dynamic programming to permutations.

Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$.

Given some string, I am trying to count the number of valid permutations- where a valid arrangement is defined as an ordering with no $1$ that stands alone from other 1s.

Example input string: $0101$

Example of valid arrangements: $1100, 0011, 0110$

Not valid: $0101, 1010, 1001$

EXPECTED OUTPUT: $3$

For example:

Say our input string contains four 1s and two 0s.

I suppose my difficulty is coming with defining the sub-problem. I initially thought I could set up a string with only the $0$ elements with slots/bins in between. $[ ] 0 [ ] 0 [] $, and then continue to use combinatorics to compute the number of additional arrangements possible with each 1 added in.

The first 1: 0 possibilities, because it will never have a 1 to accompany it.

Adding the 2nd 1: 3 possibilities, because the pair can go in either of the 3 slots.

Adding the 3rd 1: 0 new possibilities, because it must go with the other 2 ones, wherever they are.

Adding the 4th 1: We have enough to make 2 groups of $1$s now... here is where I start getting unsure. I'd think it would be an additional 3 possibilities. $\binom{3}{1} + \binom{3}{2} = 6$ total

Would anyone have an idea if I'm on the wrong track, or if not, how to proceed? This approach doesn't seem like it works for larger values. Thanks!

The subproblems can be broken down as follows.

f0 :- Number of available 0s.

f1 :- Number of available 1s.

ld :- The last digit of the string generated till now.

dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1]

dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1]

which basically boils down to,

Say at any step the string is S0

then S011 and S00 are valid as well.

Similarly,

if the string is S1 then S11 and S10 are valid as well.

The following code solves the given problem recursively.

def rec(f0,f1,stn): # Frequency of 0,Frequency of 1, List to store generated output
  if f0==0 and f1==0:
    print(''.join(stn))
    return -1;
  if len(stn)==0 or stn[-1]=='0':
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])
    if f1>1:
      rec(f0,f1-2,[x for x in stn]+['1','1'])
  else:
    if f1>0:
      rec(f0,f1-1,[x for x in stn]+['1'])
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])

rec(4,4,[])

You can easily solve the overlapping subproblems issue by using a dp-table along with the propagation rules listed above.

Output of the code for a string with 4 1s and 4 0s:-

00001111
00011110
00011011
00111100
00110011
00110110
01111000
01100011
01100110
01101100
11110000
11000011
11000110
11001100
11011000


Are real computers finite state machines? They have finite resources so they can be modeled by finite number of state what is the same that a finite state machine. There are any proof that it is not true?

Thanks.

Yes, real computers are finite state machines: they have finite memory so there's a finite number of states the machine can be in. One consequence of this is that a real computer can't recognise $\{a^nb^n\mid n\geq 0\}$.

"But hang on a second!" you're saying, "Any idiot could write a program that recognises that language."  Well, suppose your computer has $n$ bits of total storage (memory, disk, anything else you might have plugged in).  Even if you use all of that storage to count how many $a$'s you've seen, you can only count up to $2^n$.  That means your program can't tell the difference between a string that starts $a^{(2^n)}$ and one that starts $a^{(2^n+1)}$.

But you need to consider the scale of these numbers. A typical computer has, say, 1TB of storage.  That means that $n=8\times 2^{40}$ and $2^n \approx 10^{2,600,000,000,000}$.  In contrast, the number of atoms in the universe is only about $10^{80}$ and some physicists estimate that the universe will cease to exist in any interesting way in only about $10^{100}$ years, which is about $3\times 10^{116}$ nanoseconds.  (Fun fact: the number of seconds in a year is within half a percent of $\pi\times 10^7$.)

In other words, your 1GHz computer only has time to read in about $3\times 10^{116}$ characters before the heat death of the universe, and that's a looong way short of the number of characters you need to feed it to verify that it can't actually accept $a^nb^n$.  So, in practical terms, you can consider your computer to be a Turing machine instead of a finite state machine.


Program Counter Incrementation When instruction Is More Than One Word How is program counter(PC) incremented when instruction takes more than one word? How does PC know when to increment by one word or by more than one word since incrementation is done before decoding the instruction(if I am correct)?

Who says incrementing the program counter would have to happen before decoding the instruction? Modern decoders will actually decode several instructions simultaneously (if the first instructions are simple enough so that the decoder can find the start of the next instructions with negligible delay).

That's what Intel processors with their fabulously complex instruction set do. The decoder is given a large range of bytes. For some instructions it's easy to determine the length, for some it's difficult.

So the decoder tries to find the length of the instruction starting at the first byte, and very quickly finds that it is a simple instruction say of 3 bytes, or something more complicated. The decoder does the same thing simultaneously assuming an instruction starting at byte 1, at byte 2, at byte 3 and so on. (Duplicating hardware is cheap when a chip can have billions of transistors).

Once the decoder has these numbers (instruction at #0 is 3 bytes, instruction at #1 is difficult, instruction at #2 is 6 bytes, instruction at #3 is 2 bytes, instruction at #4 is difficult, instruction at #5 is difficult etc. ) it combines these results and knows there is a 3 byte instruction at #0, followed by a 2 byte instruction at #3, followed by a difficult instruction at #5. The information about the instruction starting at #1, #2, #4, #6 etc. is thrown away.

And then the decoder gets really going: It can decode several simple and one complex instruction. So the processor decodes the simple instruction at #0, the simple instruction at #3, and the complex instruction at #5. And when it has the length of that complex instruction at #5, then it increases to program counter.


Iterate unique sets of integers I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have already been generated, where the order doesn't matter.
To be clear: I'm not looking for ways to filter duplicates from a pre-computed set of sets.
I'm asking if there is an algorithmic approach to generate the unique combinations of values, without producing duplicate combinations/repetitions along the way that must be tested for and removed.
For example, I wrote this counter, which will generate all sets of length K with members bounded at N, but with duplicates.
JavaScript:
function count(k, n, m = 0) {
    // Create counting columns
    let cols = Array(k).fill(m);
    let rows = [];

    while (true) {
        rows.push(cols.slice(0));

        for (let j = 0; j < k; ++j) {
            ++cols[j];

            if (cols[j] <= n) {
                break;
            } else if (j === k - 1) {
                return rows;
            }

            // If no overflow, reset column and increment the next on next loop
            cols[j] = m;
        }
    }
}

Output:
> let k=3, n=5, m=1

> count(k, n, m).join('\n');

"1,1,1
2,1,1
3,1,1
1,2,1
2,2,1
3,2,1
1,3,1
2,3,1
3,3,1
1,1,2
2,1,2
3,1,2
1,2,2
2,2,2
3,2,2
1,3,2
2,3,2
3,3,2
1,1,3
2,1,3
3,1,3
1,2,3
2,2,3
3,2,3
1,3,3
2,3,3
3,3,3"

But, as you can see, that produces 1,2,3 as well as 3,2,1.
An example case: if I'm searching for sums of cubes that equal a cube, I don't need to test 2^3 + 16^3 + 12^3 = 18^3 if I've already checked that 2^3 + 12^3 + 16^3 = 18^3.
So I wouldn't want to generate an equivalent set again after having already tested an alternate order of the same terms.
Many thanks.

There is a trick to achieve this. Basically you always keep the subset you are currently considering sorted.
subset = [];
function forSubsets(n,k,m=1){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m; i <= n; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}

As you can see on each recursion one element is added to the subset, which is equal or bigger than all previous elements (since the loop starts from m where m is the previously added element). The order for forSubsets(3,2) would be
[1,1]; [1,2]; [1,3]; [2,2]; [2,3]; [3,3];
Of course you have to adapt the implementation to your programming language, but I hope the recursive idea is understandable. yield syntax could also be used to implement this concept in a readable manner (e.g. Python). StackOverflow should be a better place for implementation details. By changing the bounds in the for-loop the you could also draw the subsets from $0,...,n-1$ instead of $1,...,n$.
Just for the sake of completeness: Here is the code for generating subsets without duplicate elements (but no duplicate subsets):
subset = [];
function forSubsets(n,k,m=0){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m+1; i <= n-k+1+subset.length; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}


Why there is a probability in the completeness part? Interactive Proof System : An interactive proof system for a language $L$ is a two-party game between a verifier and a prover that interact on a common input in a way satisfying the following properties:

The verifier strategy is a probabilistic polynomial-time procedure (where time is measured in terms of the length of the common input)
Correctness requirements:
Completeness: There exists a prover strategy $P$, such that for every $x ∈ L$, when
interacting on the common input $x$, the prover $P$ convinces the verifier with probability at least $\frac{2}{3}$.
Soundness: For a false assertion, no convincing proof strategy exists (in the case of NP, if $x \notin L$ then no witness $y$ exists).

My Question : In the completeness part why there is a probability comming into picture?

The standard definition of $\mathsf{IP}$ involves probability both in the completeness and soundness requirements. Removing randomness all together reduces $\mathsf{IP}$ to $\mathsf{NP}$ (the witness is the full accepting transcript).

Note that you can amplify the success probability by "repeating the protocol" (i.e. talking with a prover $P'$ who simulates repetitions) and taking the majority vote (you need to be slightly careful here, since your dealing with a special prover who has access to previous interactions, but you're saved by the universal quantifier in the soundness requirement).

If what's bothering you is the fact that the protocols you are familiar with satisfy completeness with probability $1$, then one example is the proof for graph non isomorphism being in $\mathsf{AM[2]}$, using the set lower bound protocol, where the completeness probability is smaller than 1.

That said, you can in fact remove the probability from the completeness requirement (i.e. say that there exists a prover which convinces $V$ with probability $1$, $V$ is still probabilistic) without changing the class $\mathsf{IP}$, but this is a non trivial fact, which follows from the protocol for TQBP in the $\mathsf{IP=PSPACE}$ proof (which succeeds with probability 1 in case the formula is true).


Resource bounded reductions for RE-Complete problems Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this reduction in polynomial time in general? Exponential time? Polynomial space?

On the surface, defining an oracle machine like $P^{H}$, where $H$ is a black-box that solves the halting problem in $O(1)$ time seems to provide a tremendous amount of power over $P$ alone. However, if the reduction from a problem in $P$ (primes, 2-SAT, etc) to the halting problem takes exponential time (or worse!) then $P^{H}$ isn't that much more powerful than $P$ in terms of what it can solve quickly.

The reduction from $M$ to $HALT$ is essentially the function $x \mapsto \langle x, M\rangle$. This function can be computed very easily in linear time.

$P^{HALT} = Exp^{HALT} = Rec^{HALT}$. The computation you want to perform inside your reduction can be delegated to $HALT$ as part of $M$ in the reduction, i.e. just include the code for wherever you want to do inside your reduction and passed it on to $HALT$ and $HALT$ will execute that for you.

Let's say your reduction from $M$ to $HALT$ is $N$. We can define a new reduction as $x \mapsto \langle x, HALT \circ N \rangle$ from $M$ to $HALT$. The new reduction only attaches a fixed string (the code of $HALT \circ N$) to its input $x$ and computable easily in linear time.

The possibility of delegating work in reduction to $HALT$ is the reason that the reduction class doesn't matter (as long as your class of reductions are computable functions and powerful enough to attach strings) and we end up with the same class of functions when attach a $HALT$ oracle whether the class of reductions is $P$ or $Exp$.


Correctness proof: 2-approximation of greedy matching-algorithm Input: number of edges and vertices, and array of all edges in graph.

Output: array of edges that construct a matching, so that:
$$\frac{\text{the number of edges in this matching}}{\text{the number of edges in maximum matching}} \geq \frac{1}{2}$$

Algorithm I implemented

Loop:

take a random edge (actually in order it was given);
if we can add it to our matching then add;

Finally we get a matching.

The proof of condition from given section by contradiction: let's compare our matching with the maximum one. Let's consider one edge from our matching. There're two cases: the same edge is in the maximum matching or not. If it belongs to the maximum then it's OK. If not, then there's could be not more than two adjacent edges in maximum matching. Let's assume that it happened with each edge in our matching. Nevertheless, our matching satisfies the given conditions: it has not less than 0.5 of number of edges in maximum matching.

However the proof seems not really good to me. I guess there also should be a proof by induction by edges of matching. But I can't come up with a good idea.

Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching).

For all $e\in M'$ let $M_e\subseteq M$ be the set of edges in $M$ who have common vertices with $e$, meaning all $e_M\in M$ such that $e_M\cap e\neq\emptyset$. Obviously $\forall e\in M': |M_e|\le 2$, since at the worst, $e=(u,v)$ and both $u,v$ are matched to some other vertex in $M$.

Note that $M=\bigcup\limits_{e\in M'}M_e$. To see why, suppose for the purpose of contradiction that there exists $e\in M$ with no common vertices with any $e'\in M'$. This means that our algorithm could have added $e$ to $M'$, contradiction. So we have:

$|M|\le\sum\limits_{e\in M'}|M_e|\le 2|M'|$.


Hoare logic, proving conjunction rule from basic rules, possible or not? (This is HW.) Suppose I have these following proof rules given.

I am currently considering if I can prove the conjunction rule (given below) from the above given Hoare logic rules.

My answer would be "no", because from the proof rules of Hoare logic, I can neither use the Implied rule to prove it (because from $A$ I cannot infer $A \wedge B$) nor introduce it anywhere from the first four proof rules (the only one which introduces conjunction in the post-condition requires a while). I am fairly confident that this line of reasoning is correct, but am I missing anything? For example, can I argue on a the propositional logic level that since I have $P$ as a precondition, and I have $Q_1$ and $Q_2$ as postconditions, I can simply introduce conjunction on the propositional logic level (instead of inferring purely on Hoare logic)?

Your reasoning is fine as far as the derivability of this rule. To respond to the latter part of your last paragraph, if the rules you've listed are all the rules available, then those are the only rules you can use. A derivation is a tree of applications of rules. You need to be able to state what rule you're using at each node in that tree. A(n explicit) proof that this rule was derivable would be an actual derivation, i.e. tree of rule applications.

There's a different and (slightly) harder question that you probably were not asked which is whether the Conjunction Rule is admissible. That is, could the Conjunction Rule be added without causing any problems, i.e. unsoundness.


dynamic programming exercise on cutting strings I have been working on the following problem from this book.

  A certain string-processing language offers a primitive operation which splits a string into two
  pieces. Since this operation involves copying the original string, it takes n units of time for a
  string of length n, regardless of the location of the cut. Suppose, now, that you want to break a
  string into many pieces. The order in which the breaks are made can affect the total running
  time. For example, if you want to cut a 20-character string at positions $3$ and $10$, then making
  the first cut at position $3$ incurs a total cost of $20 + 17 = 37$, while doing position 10 first has a
  better cost of $20 + 10 = 30$.

I need a dynamic programming algorithm that given $m$ cuts, finds the minimum cost of cutting a string into $m +1$ pieces.

The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.

In formula:

$\qquad \displaystyle \operatorname{mino}(s, C) =
  \begin{cases}
    |s| &, |C| = 1 \\
    |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\ &\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' > c\}) \end{align}\right] &, \text{ else}
  \end{cases}$

Note that applying memoisation to this recursion actually saves work as switching the order of any successively applied pair of cuts results in the same three subproblems being solved.


Polynomially related lengths under two different encodings I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this concept of a function that is polynomially related to input lengths obtained using some encoding scheme. Let $$Len:D_{\Pi}\rightarrow \mathbb Z^+$$ be a function that maps instances $\in D_{\Pi}$ (the set of instances of decision problem $\Pi$) to positive integers (lengths). Let $x$ be the string obtained from $I\in D_{\Pi}$ under some encoding $e$. If there exist polynomials $p$ and $p'$ such that $$Len(I) \le p(|x|)$$ and $$|x| \le p'(Len(I)),$$ We say that $Len$ is polynomially related to the input lengths obtained by the encoding $e$. I cannot digest that; my understanding is that two encodings are polynomially related if converting from one another requires a polynomial amount of time. Can anybody clarify things a bit?

Garey and Johnson are referring to the fact that any encoding scheme for some instance $I$ of a problem $\Pi$ will only differ in length (i.e. number of bits) by a polynomial amount. For example, consider two possible ways to encode a graph: adjacency matrix, and adjacency list.

It is not possible to obtain a super-polynomial speedup by using one encoding over another for various instances of problems. Again, this notion relies on the fact that encodings are reasonable. That is to say, we are not unnecessarily padding our encoding with some "junk" information.


Determining grammar decidability Got a final coming up, so I gotta get this concept down.

Given $A= \{(G_1,G_2 \mid G_1$ and $G_2$ are two CFG's and $L(G_1)=L(G_2) \}$.
Is $A$ decidable?

Would it be sufficient to take an undecidable language such as $B= \{x \mid L(M_x)$ is a CFG $  \}$. Then reduce it to A with function $f(x) = G'_{M_x}$?

I don't really understand your reduction, but there is a very easy reduction from
$ALL_{CFG}=\{G| G \text{ is a CFG and } L(G)=\Sigma^*\}$.
Given $G$, Simply output $(G,G_{\Sigma^*})$, where $G_{\Sigma^*}$ is a (concrete) grammar that generates every word.

And the problem $ALL_{CFG}$ can be shown to be undecidable with a very nice (but elaborate) reduction from the word problem for TMs.


Is there an implementation of higher kinded types in typed lambda calculus? I can see that we can do higher kinded types ( * -> *) -> * in Scala and Haskell and other languages. I'm looking for a simpler vanilla implementation of just the basic static type checking system - perhaps in Prolog or MiniKanren.

My question is: Is there an implementation of higher kinded types in typed lambda calculus?

I doubt you find mainstream languages with HKTs simpler than Scala and
Haskell. And even those don't implement HKTs fully.
Tim Sheard's Ωmega   and
some interactive proof assistants have HKTs too.

Chapters 29 and 30 of   Types and Programming Languages
show exactly how HKTs are added to a typing-system and how to do type-checking with HKTs. Why not do it yourself, it's instructive!


Computation is effectively computable in theory and in practice My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice?

In trying to understand these concepts further, I have a couple of sub-questions as well:

Is there a relationship between a computation being EC in theory and being EC in practice? (It seems just by taking the usual meaning of the words, EC in practice should imply EC in theory.)
Is there an example of a computation that is EC in theory but not EC in practice?
How about EC in practice but not EC in theory?

Either explanations or links to where these explanations may be will be helpful.

The only definitions of the term "effectively computable" that I can find online are that the phrase just means "computable" (which is usually taken to mean "Turing-computable"). As such, computability is an absolute concept: either a function is computable or it is not. Are you asking about whether a function that is computable can actually be computed in practice? If so, the answer is clearly no: it's easy to construct families of problem instances that would require more time than the expected lifetime of the sun, for example. For example, take large instances of EXP-complete problems: $2^{100}$ exceeds the age of the universe in nanoseconds.  (That is, a 1GHz computer that had been running since the beginning of time wouldn't have executed $2^{100}$ instructions yet.)


Minimize range of distances between two sets of points I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A and B such that the range of distances between the points is the smallest.
For example, consider $n=3$, $A_1 = (0,0)$, $A_2 = (1,0)$, $A_3 = (3,0)$, $B_1 = (1,1)$, $B_2 = (3,2)$, $B_3 = (-1,0)$.
The best pairing will is $A_1 \text{ and } B_1$, $A_2 \text{ and } B_3$, $A_3 \text{ and } B_2$, because the distances are $(\sqrt{2}, 2, 2)$, giving the smallest range of $2 - \sqrt2$.
Ideally, I am looking for a solution which is able to solve the problem quickly (<5 seconds) for $n=300$.
The naive solution of trying all n! permutations is clearly too slow. I also thought about finding all n^2 combinations of distances, sorting them, and then removing the extremes until no possible pairing exists, but I don't know how to determine whether removing one possible connection will make it so no pairing exists.

Here is a simple algorithm to get you started.
Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a<b$ in $A$, use a bipartite matching algorithm to determine whether there is a matching that uses only distances in the range $[a,b]$. Choose the pair minimizing $b-a$. In total, there are $O(n^4)$ invocations of the matching algorithm.
It is easy to improve upon this. For example, for each $a$ we can find the best $b$ using binary search (this is essentially bottleneck matching), dropping the number of invocations down to $O(n^2\log n)$. You can improve this further (in practice) as follows:

Let $a$ be the minimal element in $A$.
Find the minimal $b$ such that an $[a,b]$-matching exists.
Decrement $b$, and find the maximal $a$ such that an $[a,b]$-matching exists.
Increment $a$, and find the minimal $b$ such that an $[a,b]$-matching exists.
And so on, until no more matchings are possible.

Here an $[a,b]$-matching is one only using weights in $[a,b]$, and "increment/decrement" are relative to $A$.
You can probably improve this even further, even in this oblivious setting where we do not use the fact that the distances originate from a planar embedding of the points.


Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete? MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem
is to find a subgraph with R vertices that is connected and maximizes the sum of the weights
(or values) of the R vertices.
CMCG Problem: The CMCG problem is the MCG problem with a constraint of having one predetermined (fixed) vertex included in the solution.
In 1 it has been stated (First paragraph, Section 1) that MCG is an NP-complete problem, which is proved in [3] (However I could not find the technical report [3] anywhere on the internet).
In 2 it has been "claimed" that CMCG is NP-complete (second to last paragraph, Section 3). But did not provide any proof.
I want to know (and see a proof, if possible) that if CMCG is NP-complete.
In 1 it has been shown that Steiner tree problem, which is NP-complete is a special case of the CMCG problem. Does it imply that CMCG is NP-complete?
[3]:Lee, H. F., and D. R. Dooly. The maximum-weight connected graph problem. Technical Report 93-4, Industrial Engineering, Southern Illinois University, 1993.

Firstly, note that you can reduce $CMCG$ to $MCG$ by setting the value of the node that must be in the set to the  sum of all positive weights of all other nodes $+1$ and then applying $MCG$ and retrieving the result set. Thus $CMCG\in NP$.
As proved in the paper the $NP$-complete Steiner-Tree problem can be reduced to $CMCG$ meaning that $CMCG$ is $NP$-hard. If a problem is in $NP$ and $NP$-hard it is by definition $NP$-complete.
Hope this helps.


Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution.

The degree distribution is the relative frequency of vertexes in the original graph that have a certain degree.

The clustering coefficient distribution is the relative frequency for each vertex degree of two neighbours (of a vertex with that degree) to have a link between them.

Does anybody know any literature and algorithm to do this? The stuff I have found was always very theoretical..

Thanks!

You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work for an arbitrary degree distribution (not just scale-free). The link I gave above has code for generating BTER graphs too.


inclusion and concatenation of languages so for a homework assignment i need to prove the following:

We have arbitrary languages L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4*

Prove that the followging is either true or false:

If L1 ∪ L2 ⊆ L3 ∩ L4, then L1◦L2 ⊆ L3◦L4 (◦ = concatenation)

Now i know this is true, but i don't know how to approach this problem...

Any tips on pointing me into the right direction are appreciated!

The assignment tests basic definitions (and some elementary set theory).

As you know, for arbitrary $L_1,L_2$, you have $L_1\cdot L_2 = \{ x\cdot y \mid x\in L_1, y\in L_2\}$.

Now if $L_1\subseteq L_3$ and  $L_2\subseteq L_4$ then $L_1\cdot L_2 \subseteq L_3\cdot L_4$. This is rather clear, or if you want, can shown with elementary steps. Take any $z\in L_1\cdot L_2$, then $z=xy$ for $x\in L_1$ and $y\in L_2$. However, because of the inclusions, $z=xy$ for $x\in L_3$ and $y\in L_4$, thus $z\in L_3 \cdot L_4$.


Tailrecursive definition for a function In an exam I took we were asked to provide a tailrecursive definition of a recursive function. I failed miserably and the provided solution makes absolutely no sense to me. If anyone could explain that would be very helpful for my resit. The provided solution is the following:

Given are the functions $f, g, h \in \mathbb{N} \rightarrow \mathbb{Z}$ with $f.0 = 20, g.0 = 37, h.0 = 13$ and for $n>0$:

$$
f.n = 3*g.n-7*h.n \\
g.n = n^2-h.(n-1) \\
h.n = f.(n-1)+g.(n-1)
$$

For the tailrecursive version of $f$ specify

$$
\psi \in \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{N} \rightarrow \mathbb{Z} \\
\psi .a.b.c.d.n = a * g.n + b * h.n + c * (n + 1)^2 + d
$$

Such that $f.n = \psi .3.(-7).0.0.n$

Then

$$
\psi .a.b.c.d.0 = 37 * a + 13*b+c+d
$$

and

$$
\psi .a.b.c.d.(n+1)\\
= \text{\{ spec \}}\\
a*((n+1)^2+h.n)+b*(4*g.n-7*h.n)+c*((n+1)^2+2*n+3+d)\\
= \text{\{ arithmetic \}}\\
4*b*g.n+(a-7*b)*h.n+(a+c)*(n+1)^2+d+c*(2*n+3)\\
= \text{\{ Construction Hypothesis \}}\\
\psi .(4*b).(a-7*b).(a+c).(d+c*(2*n+3)).n
$$

The main problem I am having is how they arrived at the specification, since the actual calculation I can follow. If anyone has any insights as to how the specification was obtained I think I would be able to grasp the answer better.

Thank you in advance.

I cannot find a way to make the specification coincide with what your solutions say, but I can get very close to that (personally, I think that your solutions contain a small mistake).

The first part should be $a*((n+1)^2-h.n)$ (and not $a*((n+1)^2+h.n)$), as per the definition of $g$ in terms of $h$.

The second part, $b*(4*g.n-7*h.n)$, comes from the definitions of $h$ and $f$: $b*h.(n+1)=b*(f.n+g.n)=b*((3*g.n-7*h.n)+g.n)=b*(4*g.n-7*h.n)$.

Finally, $c*((n+1)^2+2*n+3$ is just a (uselessly convoluted) way of writing $c*(n+2)^2$.


Minimal size of contracting a DAG into a new DAG We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:

Only nodes with the same number can be contracted into the same new node. $F(x) \neq F(y) \Rightarrow x' \neq y'$. (However, $x' \neq y'\nRightarrow F(x) \neq F(y)$.)
We add all the old edges between new nodes: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$.
This new graph is still a DAG.

What is the minimal $|V'|$? What is an algorithm creating a minimal new graph?

One approach to solving this problem would be to use integer linear programming (ILP).  Let's tackle the decision version of the problem: given $k$, is there a way to contract same-color vertices to get a DAG of size $\le k$?

This can be expressed as an ILP instance using standard techniques.  We're given the color of each vertex in the original graph.  I suggest that we label each vertex with a label in $\{1,2,\dots,k\}$; all vertices with the same label and same color will be contracted.  So, the decision problem becomes: does there exist a labelling, such that contracting all same-color same-label vertices yields a DAG?

To express this as an integer linear program, introduce an integer variable $\ell_v$ for each vertex $v$, to represent the label on vertex $v$.  Add the inequality $1 \le \ell_v \le k$.

The next step is to express the requirement that the contracted graph must be a DAG.  Notice that if there is a labelling of the form listed above, without loss of generality there exists such a labelling where the labels induce a topological sort on the contracted graph (i.e., if $v$ precedes $w$ in the contracted graph, then $v$'s label is smaller than $w$'s label).  So, for each edge $v\to w$ in the original graph, we'll add the constraint that either $v$ and $w$ have the same label and same color, or else $v$'s label is smaller than $w$'s label.   Specifically, for each edge $v\to w$ in the initial graph where $v,w$ have the same color, add the inequality $\ell_v \le \ell_w$.  For each edge $v \to w$ where $v,w$ have different colors, add the inequality $\ell_v < \ell_w$.

Now see if there is any feasible solution to this integer linear program.  There will be a feasible solution if and only if the labelling is of the desired form (i.e., contracting all same-color same-label vertices yields a DAG).  In other words, there will be a feasible solution if and only if there is a way to contract the original graph to a DAG of size $\le k$.
We can use any integer linear programming solver; if the ILP solver gives us an answer, we have an answer to the original decision problem.

Of course, this isn't guaranteed to complete in polynomial time.  There are no guarantees.  However, ILP solvers have gotten pretty good.  I would expect that, for a reasonable-sized graph, you've got a decent chance that an ILP solver might be able to solve this problem in a reasonable amount of time.

It's also possible to encode this as a SAT instance and use a SAT solver.  I don't know whether that would be more effective.  The ILP version is probably easier to think about, though.

(I hope this is right.  I haven't checked every detail carefully, so please double-check my reasoning!  I hope I haven't gone awry somewhere.)

Update (10/21): It looks like ILPs of this form can be solved in linear time, by processing the DAG in topologically sorted order and keeping track of the lower bound on the label for each vertex.  This has me suspicious of my solution: have I made a mistake somewhere?


Integer Linear programming formulation if then condition I want to create constraints such that I can implement the following condition:

Let A be an integer variable >= 0 with an upper bound of 12

I want to introduce the following variable B also an integer:

if A = 1 then B = 0 else B = A

you can introduce a binary variable z verifying the following constraints :

(A-1) <= 12*z
z<= 0.5*A
-(1-z)*12 <= B-A <= (1-z)*12
-12*z <= B <= 12*z


Optimization problem in a social network I would appreciate anybody's help with a problem I am trying to solve.

A little background:

given is a social network consisting of people represented as a directed graph, with edge from person A to person B if person A is a follower of pers B on that network. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself

Problem:

The optimization version of this problem is as follows: given a social network and
a parameter k, compute the maximum possible number of people that can be directly reached
by up to k (observers).

The search version of the problem is to compute a set of up to k observers, which reaches the
maximum number of people.

Show that given a hypothetical algorithm for the decision version of the problem, both the
optimization and search versions of the problems can be solved with at most a polynomial
overhead (i.e., if the algorithm for the decision version takes O(T(n)) time on instances of size n then the optimization and search versions can be solved in O(T(n)c) time for some constant c).

The optimization version can be solved with logarithmic overhead by binary searching on the range $[0,\dots, n]$ of the possible values of $k$, where $n$ is the number of nodes of the input graph.

The search version of the problem can be solved with a polynomial overhead by first solving the optimization problem to obtain the maximum number $m$ of people than can be reached by $k$ observers and then:

guessing an observer $v$ in the input graph $G$,
computing the set $R$ of vertices than can be reached by $v$, and
checking whether $k-1$ observers are enough to reach $m-|R|$ people: if this is the case, then the problem is equivalent to the one of selecting $k-1$ observers in $G-R$, and the whole procedure can be repeated. Otherwise, try with a different vertex $v$.

Solving an instance of your problem when $k=0$ is trivial.

At most $n$ attempts are necessary to guess the right vertex, and the whole procedure is repeated most $k$ times, i.e., the decision problem needs to be solved at most $O(\log n + nk) = O(nk)$ times.


Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a heuristic that does the following:
Given a set S containing N start coordinates and a set G containing N goal coordinates, calculate the minimum number of total unit translations of the start points required to move each start points to a goal point such that each goal point is covered. The difficulty is that it does not matter which goal point each start point ultimately lands on.
Here’s a 2d example: You're given a checkerboard with 8 pieces placed randomly on the board in locations specified in set S. G is defined as the set of 8 squares in the bottom row of the board (y=0). For each move, you're allowed to move one checker piece to an adjacent square. Calculate the minimum number of moves required to cover each spot in G with a piece.
I’ve played around with exhaustive solutions to this problem such as generating all the N! ways to arrange the pieces on the goal nodes and finding the distance for each, and I’ve also tried running a search algorithm to find the optimal paths, but these approaches seem too costly to be used as a good heuristic. It’s not so important that I’m able to calculated the actual correct minimum. If I could estimate it within a small margin of error and that error was relatively consistent regardless of the points in the two sets, that would be perfectly fine.
Is there a more efficient way to calculate this than the exhaustive method I tried? A more mathematical way? Or if not, is it possible to estimate it reliably?

How about:

Build a weighted complete bipartite graph where the left vertex set is $S$, the right vertex set is $G$, and the weight of the edge between $s \in S$ and $g \in G$ is the 3-D Manhattan distance from $s$ to $g$.
Solve the assignment problem for this graph.

This finds the exact minimum. It does unfortunately take about $O(n^3)$ for a typical network flow algorithm, though.


Show language not regular How can I show that $\{a^ib^jc^k|i=0 \lor j=k\}$ is not regular?

I tried applying the pumping lemma but it does seem to have a pumping length of 1?

Alternatively there is the Myhill–Nerode theorem.
Are $\{a^ib^j|i=0 \lor j\in\mathbb{N}\}$ infinite many equivalence classes?

Consider the intersection of your language with $ab^*c^*$.


Shortest path where weights are computationally expensive to calculate Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where weights of $ij \in E$ are calculated with CalculateEdgeWeight($ij$).

Is there a shortest path algorithm that does not require the knowledge of all edge weights by the end of the algorithm so that the use of CalculateEdgeWeight is minimized? What if we have bounds on the possible weights?

The problem you are concerned with has been examined also in the literature. See the paper Szepesvári, C. 2004. Shorteset path discovery problems: A framework, algorithms and experimental results. Association for the Advancement of Artificial Intelligence 2004, pp. 550--555.. In this paper, the following is said at the very beginning:

  In this paper we introduce and study Shortest Path Discovery
  (SPD) problems, a generalization of shortest
  path problems: In SPD one is given a directed edge-weighted
  graph and the task is to find the shortest
  path for fixed source and target nodes such that initially
  the edge-weights are unknown, but they can be queried.
  Querying the cost of an edge is expensive and hence the
  goal is to minimize the total number of edge cost queries
  executed.

Note that this work assumes edge costs to be unknown. A practical application of this theoretical assumption arise (as mentioned above) in those cases where querying the cost of an edge is very expensive ---as in your case. The algorithms considered in this paper are sound and they attempt at reducing the number of queries.

It seems, however, that your question also refers to the applicability of typical search algorithms such as A$^*$. Recall that A$^*$ expands all nodes $n$ such that $f(n)<f^*(s)$ where $f(n)=g(n)+h(n)$. In other words, it has to expand necessarily all nodes with an $f$-value which is lower than the cost of the optimal solution. The answer provided by Tom van der Zanden goes in this direction indeed. However, truth is that A$^*$ also generates (thus, it evaluates and stores in OPEN) a number of nodes with $f(n)\geq f^*(s)$ which are absolutely unnecessary.

This problem is of importance since the number of nodes generated grows exponentially with the depth of the search traversed. In your case it is twice importance because that extra amount of nodes have to be evaluated (and this requires querying a function its edge cost). A number of strategies have been proposed to save those extra generations in the context of A$^*$. For a good introduction and a plausible solution to this problem see: Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013 In case this paper fits your needs check the publications page by Ariel Felner because he also contributed with an additional paper.

Hope this helps,


Prove that the language is not regular Prove that the following language $Σ = \{1\}$ is not regular.
$L$ = $\{w | |w| = k$, where $k$ is a prime number}.

How should one go about proving this? Should I use pumping lemma for this?

We use the pumping lemma for regular languages.

$w \in L$, $|w| = n$, and $n$ is prime.

according to the lemma, $w$ can distribute to $xyz$ s.t:

$\bullet y \neq \epsilon $

$\bullet |xy| < n$

$\bullet$ for any $i \geq 0$ $ xy^iz \in L$

Now, let us denote $|y| = k$.

Now we only need to think of an $i$, where $|xy^iz|$ is not prime.

let's choose $ i = n$.

$|xy^{i+1}z| = n+ik = n+kn= (k+1)n$

since $(k+1)n$ is not prime (divides by $k+1$), we reached a contradiction and we can conclude $L$ is not regular.


Making a grammar ambiguous by applying a morphism I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous?

I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if there's a string $x \in L(G)$ having two different leftmost derivations in $G$". I would like a good explanation and if it's possible, an example.

Morphism:

I will consider two alphabets,  $Σ_1$ and $Σ_2$, where $\Sigma_1$ is the terminal alphabet of $G$.
A morphism is a function of the form $h\colon Σ_1^* \to Σ_2^*$
which satisfies: $h(xy)=h(x)h(y)$ for all $x,y \in \Sigma_1^*$.
When applying the morphism to a grammar on $\Sigma_1$, the result is a grammar on $\Sigma_2$ (that is, the morphism is only applied to the terminals in $G$).

The answer depends on the grammar $G$. If $G$ generates at most one word, then no morphism will make it ambiguous (prove!). If $G$ generates more than one word, then the morphism sending all characters to the empty string will make it ambiguous (why?).


Graph coloring decision problem NP-complete Given a graph $G = (V, E)$ and a natural number $k$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $k$ edges are polychromatic.
Prove that this problem is NP-complete.

I thought about reducing it to the 3-colorability problem, but I can't figure out a possible transformation that would work.
Any leads?

A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.

I'll let you work out the details.


How to decide if two conjunctive queries cannot have any result in common Consider the following queries:

Q1: age > 18 & age < 24 & gender = 'male'

Q2: age > 25 & gender = 'male' & major = 'CS'

Q3: age = 20 & major = 'CS'

Clearly, given any database instance $D$, we can decide $Q1(D) \cap Q2(D) = \emptyset$ and $Q2(D) \cap Q3(D) = \emptyset$. However, we cannot decide about the result of $Q1(D) \cap Q3(D)$.

I'm aware of query containment, in where the result of one query always is a subset of the results of another query. Also, I'm aware of query equivalence, in where the results of two queries should be exactly the same given any database instance.

However, I'm looking for an algorithm/terminology for my case, where before evaluating the two queries, I can decide the intersection of their results are always empty. Indeed, due to conflicting selection conditions, they cannot have any common result.

Your example queries are not conjunctive queries in the sense I came to know them. On Wikipedia they also are defined differently. What you maybe are looking for is the boolean query evaluation problem. $Q_1(D) \cap Q_2(D)$ can be expressed as $(Q_1 \wedge Q_2)(D)$, thus deciding whether $Q_1(D) \cap Q_2(D)$ is empty is the same as deciding whether $(Q_1 \wedge Q_2)(D)$ has any solution at all.
For conjunctive queries (as defined by Wikipedia) there are algorithms, faster than the brute force method, for this problem, if the query has a certain form, for example acyclic conjunctive queries.


Basic complexity theory (in Oracle Separation of BQP and PH) I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$.
Aaronsons paper was helpful, but I still have some questions left.

Raz and Tal derive Corollary 1.5 from 1.4 "by the relation between black-box separations and oracle separations", but aren't those the same thing? I thought the following all mean the same:

black-box model
oracle model
relative/relativized problem
query complexity

It would make more sense to me if Corollary 1.5 follows from 1.4 by the relation between promise problems and decision problems in the black-box model.
I am not sure how to interpret the fact that there is randomness in the problem. I think of a class such as BPP as languages solvable by a regular Turing machine with access to a random tape, which can make an error with a constant probability over its random bits. However we need to consider the worst case instantiation of the problem (right?). For a language to be in PH, there needs to be a PH-machine (without access to randomness) that does not fail on any input. Now for any oracle-output coming from one distribution there is a non-zero probability that it was actually generated by the other distribution, so the PH-machine will be wrong sometimes. Why is that argument not sufficient to show that the problem is not in PH (or any other "zero-error" class for that matter)?
What exactly is meant by an AC$^0$ circuit with access to an oracle? I've seen this described as "a circuit with access to the oracle's truth table", which I could understand if the oracle solved a decision problem $f: \{0,1\}^n \rightarrow \{0,1\}$, then the circuit input nodes are $x_i = f(i)$ for $i \leq 2^n$. However, here the oracle samples from one of two distributions on $\{\pm 1\}^{2N}$ and the circuit is defined as $A: \{\pm 1\}^{2N} \rightarrow \{\pm 1\}$. Does that mean the circuit only gets access to a single query output?

Let me answer your questions one by one.

Black-box separations versus oracle separations

Black-box algorithms are given access to a black box. For example, an algorithm might get black box access to a function $f\colon \{0,1\}^n \to \{0,1\}$. This means that the algorithm can obtain the value of $f(x)$ for any given $x \in \{0,1\}^n$, but is not otherwise given any explicit description of $f$.

As an example, consider the following promise black box problem: given a function $f$ which is either the constant $0$ or balanced (that is, half its values are $0$ and half are $1$), determine which of these two cases $f$ belongs to. There is a very simple randomized algorithm which makes a constant number of queries and outputs the correct answer with constant probability; but every deterministic algorithm must make exponentially many queries in the worst case. This is an example of a black-box separation between promise versions of $\mathsf{P}$ and $\mathsf{BPP}$.

Oracle separations also pertain to black-box algorithms, but now we want to fix the black box. In order to separate two relativizable complexity classes $A$ and $B$, we need to find a specific oracle $O$ such that $A^O \neq B^O$ (or prove that one exists). For every oracle $O$, the classes $A^O$ and $B^O$ consist of languages decided by algorithms with no auxiliary input. Rather, these algorithms have access to an $O$-oracle. But in contrast to the situation in the preceding paragraph, here the oracle is not part of the input. Rather, it is fixed.

The standard example is Turing machines with access to an oracle to the halting problem. In contrast to the example given above for black-box algorithms, here the oracle is not an input but rather an additional mechanism that the machine can make use of.

On randomness

A language $L$ is in $\mathsf{BPP}$ if there is a randomized polytime machine $T$ such that:

If $x \in L$ then $\Pr[T(x) = 1] \geq 2/3$.
If $x \notin L$ then $\Pr[T(x) = 1] \leq 2/3$.

When considering the black box version of $\mathsf{BPP}$, the definition remains exactly the same. The black box is not randomized; only the algorithm is randomized. As an example, consider the promise problem of determining whether an input black box is the constant zero function or is balanced. This problem can be solved in $\mathsf{BPP}$ by sampling a few points, or in $\mathsf{E}$ by querying the first $2^{n-1}+1$ values of the black box.

Randomization is part of the algorithm, not the decision problem.

Oracle circuits

The paper you are reading doesn't actually use these — the oracles are only applied to $\mathsf{BQP}$ and $\mathsf{PH}$. But for completeness sake, let me mention that the most common model uses oracle gates, which are gates that provide access to the oracle.

An advice

Let me close with an advice. The paper you are trying to read is at the forefront of research. It would be extremely hard to appreciate it without having some background. This paper is probably not a good entry point into complexity theory. I suggest familiarizing yourself with complexity theory first, for example by reading parts of the textbook by Arora and Barak.


Minimum length of string using chars appearing in a given string but not a substring of that string Suppose we're given a string like "aabaccbbca", and want to find a short string that's not a substring of this string. However, we're limited to using the characters that appear in the string: in this case we can use 'a's, 'b's, and 'c's, but nothing else.

In that example case, there's no length-0, length-1, or length-2 solutions. There's lots of length-3 solutions. Actually, finding the minimum length is a lot more interesting than finding a specific solution.

So my question is: how can we efficiently compute the minimum length for which solutions exist to this 'find string with same alphabet that doesn't appear as a substring' problem?

Examples:

 minLengthMissingSubstring("") == 1
 minLengthMissingSubstring("a") == 2
 minLengthMissingSubstring("abc") == 2
 minLengthMissingSubstring("aabaccbbca") == 3
 minLengthMissingSubstring("abbaccbbca") == 2
 minLengthMissingSubstring(
    "0001002003004011012013014021022" +
    "0230240310320330340410420430441" +
    "1121131141221231241321331341421" +
    "22423323424324433343444431442223") == 4

$O(n \log_m n)$ solution, using a trie and a length cutoff

Relevant wikipedia articles: De Bruijn sequence, Trie

With an alphabet size of $m$, there are $m^t$ substrings of length $t$ that need to appear in a string in order to push the minimum missing substring length (our output) past $t$. But each character we add to a string can only eliminate one additional substring of length $t$. If our string is shorter than $m^t$, we know there must be a missing string of length $t$. This gives a bound on the length of the substrings we need to search in terms of the input string's size.

We know the input size $n$ and we know the alphabet size $m$, but we don't know our output value $t$. However, we know that $t$ must satisfy $m^t \leq n$. Re-arranging, we find that $t \leq \log_m n$. So we can use $t_{\text{cutoff}} = \lceil\log_m n\rceil$.

To make it easy to look for missing strings, we're going to insert every substring, up to the cutoff length, into a trie:

def buildTrie(text, cutoff):
    root = TrieNode()
    trail = [root]
    for c in text:
        newTrail = [root]
        for t in trail:
            t[c] = t[c] or TrieNode()
            newTrail.add(t[c])
        trail = newTrail[:min(len(newTrail), cutoff - 1)]
    return root

The above function takes $O(\text{len}(\text{text}) \cdot \text{cutoff})$ time to finish, which in our case is $O(n \log_m n)$.

With our truncated trie in hand, we search through it for holes corresponding to missing substrings:

def firstLevelWithHole(trieNode, alphabet):
    if trieNode is None: return 0
    return 1 + min(firstLevelWithHole(trieNode[c], alphabet) for c in alphabet)

This search scans the whole trie. However, because the trie is cutoff at level $\log_m n$ and has fan-out at most $m$, we've done only $O(m^{\log_m n}) = O(n)$ work.

So our overall algorithm is:

def minMissingStringLength(text):
    alphabet = new Set(text)
    if len(alphabet) <= 1: return len(text) + 1
    cutoff = math.ceil(math.log(len(text), len(alphabet)))
    trie = buildTrie(text, cutoff)
    return firstLevelWithHole(trie);

And it takes $O(n \log_m n)$ time and $O(n)$ space.

Notes

The algorithm is easily tweaked to return a specific missing substring, instead of just the length.
It's probably possible to reduce this to $O(n t)$ time by creating the trie in short-substring-first order, and scanning for holes before starting the next level.
For truly huge alphabets, the dictionary lookups start costing $O(\lg m)$. I've omitted this cost from the analysis. Also you would want to modify the hole-finding to short-circuit instead of evaluating the whole tree, because it could add an $\Omega(m)$ cost otherwise.


Is $E^{quasiP}$ equal $E$ or larger? Let $quasiP$ be the quasipolynomial time complexity class.

Is $E^{quasiP}=E$ false?

Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k>1$?

Suppose that $T(n) = n^{\omega(1)}$, and consider the complexity class $\mathsf{E}^{\mathsf{DTIME}(T(n))}$. Given a Turing machine $M$ and an input $x$ of length $n$, an $\mathsf{E}^{\mathsf{DTIME}(T(n))}$ machine can write $1^{2^n}$ and then ask the oracle whether $M$ halts on $x$ within $T(2^n)/\log T(2^n) = 2^{\omega(n)}$ steps. This cannot be done in $\mathsf{E}$ according to the time-hierarchy theorem.


Using Loop Dependence analysis for vectorization How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?

I found a few resources which helped me to understand the more complex algorithms for use of loop dependence analysis.

The basic way in which the result from Loop Dependence Analysis is utilized is through various tests such as

Dependence Test of various types such as GCD Test, Conservative Test etc. help in determining if the dependency exists and they can further be utilized to test if the
Loop Transformation is safe or not.

Following are a few references which helped:

1) http://www.cs.cmu.edu/afs/cs/academic/class/15745-s09/www/lectures/lect6-deps.pdf

2) http://www.cs.utsa.edu/~qingyi/cs6363/slides/Ch02Dependence.pdf

3) http://www.cs.arizona.edu/~collberg/Teaching/553/2011/Handouts/Handout-33.pdf


How to find $L_q = \emptyset$, a state that is not reachable for any given string? In the book Introduction to Languages and the Theory of Computation, I'm reading section 2.6 on how to minimize the number of states in an FA.
I'm having trouble understanding a notation defined as $L_q$. Here's what the book says:

Suppose we have a finite automaton $M = (Q, \Sigma, q_0, A, \delta)$ accepting $L \subseteq \Sigma^*$. For a state $q$ of $M$, we have introduced the notation $L_q$ to denote the set of strings that cause $M$ to be in state $q$:
$$L_q = \{ x \in \Sigma^* | \delta^*(q_0, x) = q\}$$.
The first step in reducing the number of states of M as much as possible is to eliminate every state $q$ for which $L_q$ = $\emptyset$, along with transitions from these states. None of these states is reachable from the initial state, and eliminating them does not change the language accepted by $M$.

I tried looking at this automaton to try to understand this definition:

How can any of the states $1$ through $5$ be $L_q = \emptyset$ if I can find a string that can reach every state for this FA?
That is I can reach state $2$ with string $a$, and state $5$ with string $ab$, etc. Is this a correct way to approach this?

You're right. There is no such state with $L_q = \emptyset$

The first step in the minimization algorithm is: "delete all nonreachable states".


Is the power of a natural number logspace-computable? Given a constant $n\in\mathbb{N}_+$, is the simple power function
$$
λ\,x\in\mathbb{N}_+.\,x^n
$$
logspace computable by a logspace transducer (which has a read-only input tape, a working read-write tape (on which the transducer is allowed to use $\mathcal{O}(\log (\text{input size}))$) cells, and a write-only output tape), assuming that the input and the output are in binary?  (It is not even clear to me how to do it for $n=2$ in logspace.) Any ideas or references?

Yes, iterated multiplication is even in uniform TC0:

Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65: 695–716. doi:10.1016/S0022-0000(02)00025-9.

Explanation: We have TC0 ⊆ NC1 ⊆ L, where TC0 denotes the class of Boolean circuits with constant depth and polynomial size, where unbounded fan-in threshold gates are allowed, NC1 denotes the class of Boolean circuits with logarithmic depth and polynomial size, and L denotes logspace.


Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1 I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, however basically the author explains that it's a translation of the classic pencil and paper method and the Knuth book is the one that provides all the details. I really want to understand the analysis but for some reason that I can't quite understand it is a bit strange in the exposition.

It firstly starts by saying that

  "a moment's reflection about the ordinary process of long division shows that the general problem breaks down into simpler steps, each of which is the division of an $n+1$-place dividend $u$ by an $n$ place integers $v$.

I of course agree with such intuition, but it's because I've been taught in that way, not because there's a proof. It shouldn't be hard to work out the why however since

$$
\begin{array}{l}
u = \sum_{j=0}^{m+n-1} u_j b^j \\
v = \sum_{j=0}^{n-1} v_j b^j
\end{array} \Rightarrow \frac{u}{v} = \frac{\sum_{j=0}^{m+n-1} u_j b^j}{v} =
\frac{\sum_{j=m-1}^{m+n-1} u_j b^j}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \frac{\sum_{j=0}^{n} u_{j+m-1} b^{j+m-1}}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} =
\frac{\sum_{j=0}^{n} u_{j+m-1} b^j}{v}b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \left(q_{m-1} + \frac{r_{m-1}}{v} \right)b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = q_{m-1}b^{m-1} + \frac{r_{m-1}b^{m-1} + \sum_{j=0}^{m-2} u_j b^j}{v}
$$
where $0 \leq r_{m-1} \leq v - 1$, using an induction argument I can show that I have always to do this (i.e. that the problem is to perform several iteration of dividing an $n+1$ digit number by an $n$ digit number. One key observation is that of course if
$$
0 \leq q_{m-1} \leq b - 1
$$
then $q_{m-1}$ represent the most significant digit of the division

Later the problem is stated as

  Let $u = (u_nu_{n-1} \ldots u_1 u_0)_b$ and $v = (v_{n-1} \ldots v_1
v_0)_b$ be nonnegative integers in radix-$b$ notation, where $u/v <
b$. Find an algorithm to determine $q = \left\lfloor u/v
\right\rfloor$.

From this point I have a problem (which is the object of my question). After the observation made that the condition $u/v < b$ is equivalent $(u_n \ldots u_1) < (v_{n-1} \ldots v_0)$ I would also observe that  $v_{n-1}$ is not necessaraly 0. It is later defined the quantity
$$
\hat{q} = \min \left( \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1}} \right\rfloor,b-1\right)
$$
Where is not actually stated any condition on $v_{n-1}$, which at least shouldn't be $0$. Then the author proves both theorems $A$ and $B$ which they make perfectly sense to me if $v_{n-1} \neq 0$.

One could argue that before the theorems it is said

  ...as long as $v_{n-1}$ is reasonably large...

However I think that this statement should be interpreted more like "we now show how much large $v_{n-1}$ has to be in order to..." So there's actually no assumption here, he wants to show that.

The question is...
Shouldn't basically the condition $v_{n-1} \neq 0$ be clearly stated?
I'm sure there's something subtle about the condition $u/v < b$ that I'm missing...

(I have other questions but I'll go through that later)

Theorem B on page no. 272 of the book states that,

  if $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, then q ∈ [ q̂ - 2 , q̂ ].

Therefore, the algorithm is valid only when $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, which makes $v_{n-1} \neq 0$ obvious. To ensure this we need to multiply both u and v by a factor ${(= (base-1) / v_{n-1})}$.


Convex hull algorithm in $O(\min(mn, n\log n))$ I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$.

My first guess was QuickHull, which has a best case running time of $O(n \log n ) $ and a worst case running time time of $O(n^2)$. However, I am a little bit confused about the fact that this convex hull does not have to contain all points. Can I ignore this? I guess yes because I must assume the worst case and this would include all points.

Any ideas or hints?

The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other one. This runs in time $O(\min(mn,n\log n))$.

In fact, you can do better – Wikipedia lists several $O(n\log m)$ algorithms, which is strictly better than the guarantee you are looking for.


Consequences of $NP=coNP=BPP=RP$ What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?

Unless I'm missing something obvious (it is getting late here), the second isn't possible - $BPP = coBPP$, so $NP=BPP \rightarrow NP = coBPP \rightarrow NP = coNP$.

In the first case, some of the consequences would be:

"Feasible" algorithms for $NP$-complete problems, for at least the randomised version of feasible.
$PH \subseteq NP$
Unless $P = NP$, adding randomness adds computational power.
Strong pseudorandom number generators do not exist (nor do one way functions). (we would need $BPP = P$ for them to exist, but that would imply $P=NP$, in which case they don't).


Is there an implicit condition OPT<P(|input|) in approximation schemes? Sorry if my question is banal. Consider an approximation scheme such as FPTAS that guarantees to find a soln>(1-eps)OPT for maximization. Now consider if OPT=exp(|input|) so It easily can be seen that soln is exp(|input|) So its run-time will be exponential too(just a print of result is exponential). So can we say the condition OPT<P(|input|) is a necessary condition for any problem that we want to find an approximation scheme algorithm for that?

FPTAS is commonly used for optimization problems whose associated decision problem is in NP.  For those problems, it is guaranteed that the optimal solution has polynomial size (that's part of the definition of NP), so this issue does not arise.