Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way:

let's suppose that $g$ is the computable function that represents $D$ $$g(x) = \left\{\begin{array}{rcl} 1 & \mbox{if} & \Phi_x(x)\downarrow\ \\ 0 & \mbox{if} & \Phi_x(x)\uparrow\ \end{array}\right.$$
let's suppose that it exists a Turing machine of index $i_0$ such that $g = \Phi_{i_0}$, than it is possible to define the function: $$g'(x) = \left\{\begin{array}{rcl} \uparrow & \mbox{if} & g(x)=1=\Phi_{i_0}(x) \\ 0 & \mbox{if} & g(x)=0=\Phi_{i_0}(x) \end{array}\right.$$
so $g'$ is also computable thus there is a Turing machine of index $i_1$ such that $g' = \Phi_{i_1}$, but then we will have that:
$$\Phi_{i_1}(i_1)\downarrow \iff g'(i_1) = 0 \iff g(i_1) = 0 \iff \Phi_{i_1}(i_1)\uparrow $$
$$\Phi_{i_1}(i_1)\uparrow \iff g'(i_1) \uparrow \iff g(i_1) = 1 \iff \Phi_{i_1}(i_1)\downarrow $$

which is a contraddiction. So an index $i_1$ doesn't exists that is the index $i_0$ that computes $g$ doesn't exists, that is $g$ is not recursive so $D$ is not recursive enumerable.

I'm quite confused on this topic, so tell me if I made any kind of error.

As Andrej states, what you've (correctly) done is show that $D=\{x:\Phi_x(x)\uparrow\}$ is not recursive. However, there are plenty of sets which are recursively enumerable but not recursive, so you're not done yet: you need to show that $D$ is not the domain of any partial recursive function.

REMARK: Some texts define a set to be r.e. if it is the range of a total recursive function, or is empty. This is slightly less elegant since it requires a separate clause to handle $\emptyset$; it also generalizes less well if one looks into higher computability theory. However, regardless of what definition your book gives, the equivalence between them should be a very early exercise.

There are a couple ways to do this:

You could argue directly: suppose $D$ is the domain of $\Phi_i$. Can you use the recursion theorem to cook up a $j$ such that $\Phi_j(j)\downarrow\iff \Phi_i(j)\downarrow$? Do you see why this gives a contradiction?
Alternately, note that $D$ is the complement of the Halting Problem $H=\{x: \Phi_x(x)\downarrow\}$. Two early results in computability theory are that (i) $H$ is r.e. but not recursive and (ii) if a set and its complement are r.e., then they are each recursive. Do you see how to prove each of these facts, and apply them to the current problem? (Note that this approach isn't actually much different than the first one, since the recursion theorem is used in proving (i).)

REMARK: Some texts define the Halting Problem differently, some common alternate candidates being $\{x: \Phi_x(0)\downarrow\}$ and $\{\langle x, y\rangle:\Phi_x(y)\downarrow\}$. It's a good exercise to show that these are all r.e. and Turing equivalent (indeed $1$-equivalent!) to each other.

By similar arguments you can show that minor variations of $D$ are also not r.e. - e.g. can you show that $\{x: \Phi_x(17)\uparrow\}$ is not r.e.?

Responding to the comments: one may be tempted to try to enumerate $D$, or things like $D$, by looking at approximations given by stages. E.g. we could let $D_s=\{x:\Phi_x(x)[s]\uparrow\}$; this is the set of indices of machines which on their own input don't halt in fewer than $s$ steps. The $D_s$s are r.e. - indeed, uniformly recursive - and approximate $D$ "from above" in the sense that $D=\bigcap_{s\in\mathbb{N}} D_s$. However, this ultimately isn't relevant to this problem since the intersection of infinitely many r.e. sets need not be r.e.


How many 3-SAT expressions with up to N variables are satisfiable? TL;DR

There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-sat expressions with exactly 4 variables. Of those, how many are satisfiable? How did you get that number?

Problem Statement

Assume you have a 3-SAT equation where all the clauses have exactly 3 distinct variables (i.e. $X$ and $\neg X$ will never appear in the same clause), and no clause appears more than once (i.e. some expression won't have both $(X \lor Y \lor \neg Z)$ and $(X \lor \neg Z \lor Y)$). With this construction, there are a finite amount of expressions with only N variables.

For the class of expressions with up to N variables, is there an equation to compute how many are satisfiable?

Example of N=3

For example, with N=3, there are 254 solutions.

We know this because for N=K, there are exactly $8 *\binom{K}{3}$ distinct clauses, as you must select three distinct variables for each clause, and 1 of 8 possible sign values for those variables (+/+/+, +/+/-, +/-/+, +/-/-, ...). If there are $8 *\binom{K}{3}$ possible clauses, then there must be $2^{(8 *\binom{K}{3})} - 1$ possible boolean expressions, because each clause may appear or not (so $2^{(8 *\binom{K}{3})}$) and we have to subtract one for the case with no clauses.

For N=3, there are 255 possible expressions (using the lemma above), and only one is unsatisfiable. So there must be 254 distinct satisfiable expressions.

How about for N=4?

There is almost certainly no non-trivial formula that will tell you the number of solutions. By non-trivial, I mean something not of the form
$$
\sum_{x_1, \dots, x_n\in\{0,1\}} f(x_1, \dots, x_n)\,,
$$
where
$$f(x_1, \dots, x_n)=\begin{cases}1 &\text{if $x_1, \dots, x_n$ satisfies the formula}\\
0&\text{otherwise.}\end{cases}
$$

Note that if we have a formula $F$ (trivial or otherwise) that tells us how many satisfying assignments there are, we can decide 3-SAT just by computing $F$ and checking whether $F=0$ (unsatisfiable) or $F>0$ (satisfiable). This means that computing $F$ is NP-hard so, assuming that P$\,\neq\,$NP, $F$ is difficult to compute, which suggests that $F$ can't have any nice form.

In fact, $F$ is complete for the complexity class #P, which is essentially at least as hard as all of the polynomial hierarchy. This means that it seems to be quite a lot harder than "just NP-hard". Furthermore, we can't even approximately compute $F$ in any efficient way unless P=NP. Even being able to approximate $F$ with exponential additive error would allow us to distinguish between $F=0$ and $F>0$ and thus allow us to solve 3-SAT. For example, given a formula with $N$ variables and $F$ solutions, we can create a formula with $2N$ variables and exactly the same clauses (so variables $N+1, \dots, 2N$ aren't mentioned in the formula and can take any value). This formula has $2^NF$ satisfying assignments and being able to approximate that number strictly better than $\pm 2^{N-1}$ would allow us to tell the difference between $F=0$ and $F>0$.


What is the reason of inaccuracy of operations on float numbers? I wonder why in JavaScript

0.1 + 0.2  // return 0.30000000000000004

4%0.1 // return 0.09999999999999978

http://jsbin.com/oHISAfU/1/edit  (Example)

In C the math.h library fmod function

printf("%f", fmod(4.0,0.1));  // print 0.100000

http://ideone.com/RG5Wyv (Example)

And in Spotlight (search feature in the Mac OS X ~ I already submit bug report) that support math operation

4%0.1 = 0.1

It's because 0.1 = 1 / 10 = 1 / (2 × 5) cannot be represented exactly in binary floating point.  This happens in C too:

 printf("%.20f", fmod(4.0,0.1));

prints 0.09999999999999978351.

Specifically, the only numbers that binary floating point can represent exactly are dyadic fractions of the form a / 2b, where a and b are integers.  Even more specifically, for IEEE single precision floating point numbers, a must be between -224 and 224 and b must, in effect, be between -151 and 104.  (Or at least approximately so; there are some tricky special cases like denormalized numbers.)  For double precision floats, the ranges are wider, but even so, a fraction like 1 / 10 cannot be represented exactly, because the denominator is not a power of two.


Can I express 100 as a three-digit 9's complement number? Reading the Appendix A (Binary numbers) of Structured Computer organization by Tanenbaum I've found this exercise:

  Signed decimal numbers consisting of $n$ digits can be represented in $n + 1$ digits without a sign. Positive numbers have $0$ as the leftmost digit. Negative numbers are formed by subtracting each digit from $9$. Thus the negative of $014725$ is $985274$. Such numbers are called nine’s complement numbers and are analogous to one’s complement binary numbers. Express the following as three-digit nine's complement numbers: $6$. $-2$, $100$, $-14$, [etc].

Ok, it all works fine with $6$ for instance: using the given rule it is $006 \mapsto 993$. That makes sense: as Tanenbaum says this system for negative-value representation is similar to one's complement: it has two different zero representation ($000$ and $999$) and it has negative possible value as much as the positive ones.

What I don't understand is how can $100$ fit in this scenario. To me, with 3 digits I ca only represent value in range $[-900, 099]$; moreover $100$ is not considered a positive number --it shoudl have a $0$ as leftmost digit.

Is there an error in Tanenbaum-exercise?, if not, where I'm wrong?

Nine's complement representation involves a choice of the exact range of positive and negative numbers. It is natural to let the sign depend on the MSD (most significant digit). It is even more natural to declare that numbers starting with $0,1,2,3,4$ are positive, those starting with $5,6,7,8,9$ are negative. The range of three-digit numbers is then $-500$ to $499$ rather than $-900$ to $99$, and $100$ becomes representable. I suspect that this interpretation is what Tanenbaum intended.


Why do all recent SAT solvers work on CNF instead of circuit SAT? After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG tracks. However since then it seems the focus has been entirely on either SMT or improving clausal SAT solvers.

Intuitively to me concentrating on circuit SAT seems to make a lot of sense: Many if not most problems are more naturally expressed as circuit SAT than CNF; circuits provide structural information that cannot be reverse engineered from CNF, but circuits can always be transformed into CNF; and at least the industrially significant field of logic synthesis seems to be a particularly good fit for AIGs.

So, what happened? Did it turn out that the extra structural information does not help solvers? Was AIG-based SAT solving a failed experiment?

there are a lot of different angles on your question. generally agreed with your premise that looking at "structural information" in a SAT formulation ought to be an excellent research area.

SAT encoded in CNF has been a standard for decades. it was solidified in the early-to-mid 1990s with the DIMACS format/ competitions.
what technically is "structural information"? it may be hard to formally nail that concept down and avoid near-tautological circles. there is not really any difference between a SAT CNF encoding and and other encodings that preserve a network structure. this is embodied in the "clause/ variable graph" concepts which very many SAT solvers tend to utilize. in other words, in some rough sense, every significant SAT solver uses "structural information".
yes, newer directions in research have focused on ASP and SMT solving which nearly actually embody the "structural information" you inquire about.
Tseytin transformation easily converts a circuit into SAT in P time/ space for input into a standard SAT solver. it is presumably widely used in many contexts esp EE circuit contexts.
there is some rather isolated research generally along the lines you mention but unfortunately (again along with your premise) it never seemed to develop much into a research trend. dont think that is due to lack of potential but more human factors. two favorite papers[1][2], another is to look at particular instances from areas such as "industrial instances" or "electrical engineering" instances of which there is some specialized research.
CS purists sometimes tend to want to avoid psychology/ sociology considerations in all the mathematical abstractions, but reasonably its still a factor in computer science. you ask about research trends, which are based on human psychological factors. its possible there is some streetlight effect going on here aka "low hanging fruit". one might say/ consider that even now a few decades old, SAT algorithmic research is somewhat in its infancy, such that big questions like P vs NP seem nowhere in sight, and maybe existing research while still substantial is still just "scratching the surface".

[1] Decomposing satisfiability problems
 or Using graphs to get a better insight into satisfiability problems, Herwig 2006 (83pp)

[2] The constrainedness knife edge Walsh 1998


Finding the k-shortest path between two nodes Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-shortest path, the $3^{rd}$-shortest, and so on.
Questions:

Is there an efficient algorithm to get the i-th-most-shortest-path between two nodes in a weighted graph?
Is there an efficient algorithm to get the k-most-shortest-paths between two nodes in a weighted graph?

An answer to either one is OK, though I wonder if an answer to the second question can be done more efficiently than $k$ calls to an answer to the first question.

In the $k$ shortest path problem, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein [1] has an algorithm running in $O(m+n \log n + k)$ time to find the $k$ shortest paths (allowing cycles) between a pair of vertices in a digraph. With the techniques of the paper, one can also find all path shorter than some given threshold, within the same time bounds. There is a vast literature on the subject, the Eppstein paper includes many references and discussion.

If you disallow cycles, you might want to look at the algorithm of Hershberger et al. [2].

[1] Eppstein, David. "Finding the k shortest paths." SIAM Journal on computing 28.2 (1998): 652-673. [CiteSeerX]

[2] Hershberger, John, Matthew Maxel, and Subhash Suri. "Finding the k shortest simple paths: A new algorithm and its implementation." ACM Transactions on Algorithms (TALG) 3.4 (2007): 45. [CiteSeerX]


Proof of correctness of this algorithm Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A_i + A_j = n$. Simple enough, here's an algorithm that does it:

CheckForPair(A, n, i, j):
    if i >= j or outOfBound:
        return false
    v := A[i] + A[j]
    if v = n:
        return true
    if v < n:
        return CheckForPair(A, n, i + 1, j)
    if v > n:
        return CheckForPair(A, n, i, j - 1)

CheckForPair(A, n):
    return ChcekForPair(A, n, 1, |A|)

Mathematically,

  $$
\begin{align}
CheckForPair(A, n, i, j) &=
\begin{cases}
false  & \text{if $i \ge j$ or $i < 1$ or $j > |A|$,} \\
true & \text{if $A_i + A_j = n$,} \\
CheckForPair(A, n, i + 1, j) & \text{if $A_i + A_j < n$,} \\
CheckForPair(A, n, i, j - 1) & \text{if $A_i + A_j > n$} \\
\end{cases} \\
\\
CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|)
\end{align}
$$

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

if $A_i$ + $A_j < n$, then $i$ must increase because $j$ cannot increase.
if $A_i$ + $A_j > n$, then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.

It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$
CFP(n,A) =
\begin{cases}
False& \text{if }A=[\;]\\
True& \text{if } first(A) + last(A) = n\\
CFP(n,tail(A))&\text{if }first(A)+last(A)<n \\
CFP(n,init(A))&\text{otherwise}
\end{cases}
$$
where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:

|A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:

$A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
$A_j = last(A)$: Analog to the previous case.
$first(A)<A_i\leq A_j<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.


How Splitting Summation method works I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align*}
\sum_{k=1}^{n} k &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\
&\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\
&= (n/2)^2\\
&= \Omega(n^2)\,\end{align*}$$

I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in other. How does this method work? Can anybody explain?

$$\begin{align*}
55 = 1 + 2 + \dots + 10 &= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\
&\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\
&= (10/2)(10/2) = 25\,.\end{align*}$$

If you're wondering how to come up with such substitutions, there's no general method: this is one of the creative things you have to do to produce mathematical proofs.


What is tight NSPACE complexity of $ALT\text{-}SPACE(a(n),s(n))$? According to Ryan Williams's answer $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(a(n)\log n)$.

  Does there exist any better bound (for example something like $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(\log (a(n))\log n)$), or is it tight or an open problem?

It's open, at least for the inclusion
$ALTSPACE(\alpha(n),\log n)\subseteq NSPACE(f(n))$ with $\Omega(\log n)\leq f(n)\leq \alpha(n)^{o(1)}$. According to Chandra, Kozen, and Stockmeyer, we know
$$DTIME(n^k)\subseteq ALTSPACE(n^{2k},\log n)\subseteq \mathsf{P}.$$

Therefore if it is true, then $\mathsf{P}\neq \mathsf{NPSPACE}$ which is not known to be true. On the other hand, rejecting it will yield $\mathsf{P}\neq \mathsf{NL}$, which is also not known to hold.


What the length of instructions on these processors will be? Let's say we have two computers with identical ISA, but different size of word in main memory. One is 32 bit and the other 64 bits. So will it be identical length of instruction, different, depends on memory or depends on cache memory and why ?

If the ISA is the same, the registers and instructions have the same size.

A CPU can have 32, 64 or wider busses for caches, external memory.

It has no relation with the size of instructions.

It has no relation with the size of integer registers.

You can see variants or extension of the same ISA with 64 bits support : MIPS III, SparcV8 vs SparcV9, x86 vs AMD64, ARMv7 vs ARMv8, Power32 vs PowerPC64, etc... The new instructions are either handled as a different mode, or using different opcodes.

The "size of word" is a term for compilers and programmers (int, long int, long long int...), not for hardware.

Of course, it makes little sense to tie a 64bits bus to a 8bits CPU, or the inverse.


Depth perception - detect how far into a scene a user is looking I would like to know about how we can detect how 'deep' into a scene a user is looking. If looking into a 3D environment, with an object close to the user and one further away, how can we detect when the user is looking at the object further away? Or, rather, how can we detect which object a user is looking at in a 3D environment?

I am asking here because I'm not sure what this technology is called, or even if it exists, and so am hoping for some pointers into what I should be reading/looking at.

If anyone has some resources for me (links, algorithm names, books, articles, etc.), it would help a lot, but if you are able to explain a little, I'd really appreciate that, too.

Many thanks.

If you know the gaze direction angles of each eye (as well as head position and orientation), then the corresponding rays intersect roughly at the fixation point in 3D.
This straightforward approach should work in theory, but in practice it is still quite challenging due to both technical and physiological factors.

Pfeiffer, Latoschik and Wachsmuth summarize quite accessibly the state of the art in 3D eye-fixation tracking as in 2008. Here, the intuitive approach I just described was still outperformed by another algorithm.

As the following link suggests, however, the problems with geometrical approaches may have been resolved since 2008. This commercial application appears to use the intersection-point method, though I doubt that the applied algorithms are published.


Is an Event Counter essentially an integer version of Barrier? Just like there exists binary and integer Semaphores, does the Event Counter play an integer version of a Barrier?

Event Counters are described in the paper

  Reed, DP; Kanodia, RK: Synchronization with eventcounts and sequencers. Commun. ACM 22(2):115-123, 1979, http://doi.acm.org/10.1145/359060.359076

There is an online versions of the paper here.

An event counter can function like a barrier when a set of threads all use the same value to await. For example, 3 threads can perform an await operation on the Event-Counter EC, using the same value. Then await(EC, common_val), and then threads each will block until the EC is advanced to the common value to synchronize with one another.

However, Event Counter along with Sequencers can be used in many other ways as well, while barrier primitives have only this one type of behavior, used only to allow a set of threads to move through multiple steps. Event Counter along with a Sequencer can also make up a semaphore.


Adding two running time from a function I have a method Func() that has two inner methods Func1() and Func2().

Func1() has a running time of $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))$ and Func2() has a running time of $O(k \lvert K \rvert \lvert V\rvert)$.

What is the running time of Func()?

Is it $\max \{ O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert)),O(k \lvert K \rvert \lvert V\rvert)\} $? or $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))+O(k \lvert K \rvert \lvert V\rvert)$?

If it is the latter one, how can it be simplified?

The summation rule of the big-O notation;

Given $T_1(n) \in \mathcal{O}(f(n))$ and $T_2(n) \in \mathcal{O}(g(n))$, than $$T_1(n)+T_2(n) \in \mathcal{O}(\max(f(n),g(n)).$$

So, if you call $Func1()$ and $Func1()$ inside of your function $Func()$ only once and there is no other significant computation, $Func()$'s running time is;

$$Func() \in \mathcal{O}(\max(k |M^2|(|L|+|M|\log |M|), k | K | | V | )) $$


Finite State Automaton Language We're given these two finite state machines where the alphabet consists of ${a, b, c}$. The question is to determine the language for the following two machines. I tried following the machines to find the language, but the languages I derived are quite verbose.

FSA #1

This FSA accepts words with at least one a followed by zero or more b's or words with at least one a followed by zero or more b's followed by at least one c.

FSA #2

This  FSA accepts words with at least one a followed by at least one b or words with at least one a followed by at least one b followed by one c.

I tried converting these FSAs to regular expressions and found that my solutions hold up, but I'm wondering if there is a more concise way to explain the language of each FSA. My language explanations seem quite verbose, so any help would be appreciated.

Finite state automatons recognize regular languages. The advantage of regular languages is that it is usually trivial to express them formally.

FSA #1

$$L(M_1) = \left\{ a^kb^lc^m | k > 0, l \geq 0, m \in \{ 0, 1 \} \right\}$$

FSA #2

$$L(M_2) = \left\{ a^kb^lc^m | k > 0, l > 0, m \in \{ 0, 1 \} \right\}$$


Can Yacc be used to generate three address code for Java 1? I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that  can be used for generating three address code and is strictly LALR(1), but the translation scheme I am employing makes it L-attributed. Now I have read that L-attributed LR grammars cannot be parsed by using bottom up parsing. So, can yacc be used here or not?

A grammar's parser serves to recognize the language generated. Tools like YACC augment the parser to (essentially) trace a parse tree (some automatically build an AST, abstract syntax tree) for the parsed string according to the grammar. You can then walk this structure to generate code. But that is a separate task, that commonly uses different tools.


Constant-depth threshold circuit for $\mathrm{PP}$ Is it proven that $\mathrm{PP}$ has uniform constant-depth threshold circuit?

Yes, Anuj Dawar and Yuguo He claim in their paper titled "Parameterized Complexity Classes uder Logical Reductions" [1] that $\mathrm{SAT}$ is $\mathrm{NP}$-complete, even under quantifier-free first-order projections, which are reductions even weaker than $\mathrm{AC}_0$ reductions.

The same result also holds true for $\mathrm{PP}$ with $\mathrm{MAJSAT}$.

First-order projection can be done in constant depth.

All that is left to be shown is proving that $\mathrm{MAJSAT}$ can be decided in constant depth. Indeed, our threshold circuit for this language has an overall $\mathrm{MAJ}$ gate as the output gate that receives the result from exponentially many result of every possible assignment to the variables of the given 3-$\mathrm{SAT}$ formula. And for each variable assignment, we can, in constant depth, evaluate the formula with this assignment.

[1] Anuj Dawar, Yuguo He, Parameterized Complexity Classes uder Logical Reductions, https://www.cl.cam.ac.uk/~ad260/papers/mfcs09.pdf


Print maximum frequency number in an array(with slight modification) There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.

Start by sorting the array. Now go over the array using four pointers, left, center left, center right, and right. The two central pointers bracket all the occurrences of some value $x$. The left pointer points at the leftmost value which is at least $x-M$, and the right pointer points at the rightmost value which is at most $x+M$. Using the positions of these pointers you can calculate the maximum frequency of $x$.

Traversing the array should take linear time, so the entire algorithm takes time $O(n\log n)$.

For a possibly simpler solution, you can sort the array and then use a single pointer to traverse it. Treat this pointer as one of the central pointers from the previous algorithm, and find the locations of all other pointers in logarithmic time using binary search. Traversal now takes time $O(n\log n)$, but this doesn't increase the asymptotic running time of the algorithm.


Is it possible to always construct a hamiltonian path on a tournament graph by sorting? Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?

I assume that you intend $\leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $\leq$ is really the smallest fixpoint of the equivalence you give:
$\qquad \displaystyle a \leq b \iff \exists\, v_0 \dots v_n. a \to v_o \to \dots \to v_n \to b$
with $n \geq 0$ and $v \to u \iff (v,u) \in E$.
The key argument here is that $\leq$ is indeed a total order. If it is, you can use it for sorting, and the result is by definition of $\leq$ a Hamiltonian path: consider the result of the sort $v_1 \dots v_n$. If there were no edge between $v_i$ and $v_{i+1}$, by $V_s = v_i \leq v_{i+1}$ there is $v \in V$ such that $v_i \leq v \leq v_{i+1}$. This contradicts that $\leq$ is a (total) order and $V_s$ is sorted with respect to $\leq$.
Unfortunately, $\leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K_4$:

[source]
Here, $a \leq d$ and $d \leq a$ (directed cycles are the culprits!) but $a \neq d$. So $\leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.


Unfeasible linear program becomes feasible if a variable is removed Apologies, not a computer scientist by trade but I'm playing with linear programming these days.

Let $\{x_i\}$ be $N$ optimization variables with bounds

$$l_i \leq x_i \leq u_i$$

I'm interested in telling if $\exists$ a feasible region under the constraint

$$\sum_i x_i = C$$

for a fixed value of $C$.

This is pretty easy (just check that $\sum_i l_i \leq C \leq \sum_i u_i$). But sometime it happens that while

$$\sum_i x_i=C\,$$

is too constraining,

$$\sum_{i\notin {\mathcal{S}}} x_i =C\, , $$
has a feasible region for some subset of index $\mathcal{S}$.

But at first sight it's hard to tell because there's $N$ variables, such that a brute force check runs in $2^N$.

Examples: $l_x=l_y=10$, $u_x=u_y=30$ and $C=15$  is not feasible but it would be feasible if one was to remove either $x$ or $y$ from the problem.

Is there some elegant solution to this problem? There's a nice geometrical way of understanding the problem.
In the two variable cases, removing either $x$ or $y$ amounts to projecting the region bounded by $[l_x, u_x],[l_y, u_y]$ onto $y$ or $x$ axis respectively. Then it's only a matter of asking whether the line $x+y=C$ crosses either of the "projected" regions (which are now lines).

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a subset of the $u_i$ that sums to $C$ (which is the Subset Sum problem).

If your problem did not allow $l_i=u_i$, if you were to require that $l_i<x_i<u_i$, you could get around this by setting $10000\cdot l_i<x_i<10000\cdot u_i + 1$ which for sufficiently large values of $10000$ ensures that $x_i$ will be "close enough".


Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)

Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.

Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.

In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) \cdot (A + B)$.

What's left is to look at the pairs of divisors of $N$.
If $N = X \cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.

The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem.  Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.

Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)


How does Pollard's rho algorithm work? I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and also on internet but still can not understand its structure or analysis.
This is a java implementation of the pseudocode from the CLRS book along with euclid gcd algorithm:

public static void pollardRho(int n) {
    Random rand = new Random();
    int i = 1;
    int x0 = rand.nextInt(n);
    int y = x0;
    int k = 2;
    while (true) {
        i++;
        int x = (x0 * x0 - 1) % n;
        int d = gcd(y - x, n);
        if (d != 1 && d != n) {
            System.out.println(d);
        }
        if (i == k) {
            y = x;
            k *= 2;
        }
        x0 = x;
    }
}

public static int gcd(int a, int b) {
    // fixes the issue with java modulo operator % returning negative
    // results based on the fact that gcd(a, b) = gcd(|a|, |b|)
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int tmp = b;
        b = (a % b);
        a = tmp;
    }
    return a;
}

Why does it choose $x = (x_0^2 - 1) \mod n$?
What does $y$ actually represent and why is it chosen to be equal to $\{x_1,x_2,x_4,x_8,x_{16},...\}$?
Why does it compute $\text{GCD}(y-x,n)$ and how does $d$ turns out to be a factor of $n$?
And why is the expected running time is $O(n^{1/4})$ arithmetic operations and $O(2^{\beta/4} \beta^2)$ bit operations assuming that $n$ is $\beta$ bits long?

I understand that if there exists a non-trivial square-root of $x^2 \equiv 1 \pmod{n}$ then $n$ is a composite and $x$ is a factor, but $y - x$ is not a square root of $n$ is it?

The idea behind Pollard $\rho$ is that if you take any function $f : [0, n - 1] \to [0, n - 1]$, the iteration $x_{k + 1} = f(x_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and consider it modulo $n = p_1 p_2 \dotsm p_r$, where the $p_i$ are primes:

$\begin{equation*}
  x_{k + 1}
    = f(x_k) \bmod n
    = f(x_k) \bmod p_1 p_2 \dotsm p_r
\end{equation*}$

Thus it repeats the same iteration structure modulo each of the primes into which $n$ factors.

We don't know anything about the cycles, but it is easy to see that if you go with $x_0 = x'_0$ and:

$\begin{align*}
  x_{k + 1}
    &= f(x_k) \\
  x'_{k + 1}
    &= f(f(x'_k))
\end{align*}$

(i.e., $x'$ advances twice as fast) eventually $x'_k$ and $x_k$ will span one (or more) cycles (see Floyd's cycle detection algorithm for details), thus in our case, $x'_k \equiv x_k \mod{p_i}$,
and $\gcd(x'_k, x_k)$ will be a factor of $n$, hopefully a non-trivial one.

Any polynomial works, but we want irreducible ones (no non-trivial factors, detecting those is not the point of the exercise). Linear polynomials don't give factors, next simplest to compute is a quadratic one, but just $x^2$ doesn't work either (reducible), so take $x^2 + 1$ for simplicity. Remember the idea here is to work with very large numbers, few and simple arithmetic operations are a distinct bonus. The analysis of the algorithm (e.g. in Knuth's "Seminumerical algorithms") models $f(x) \bmod p$ as a random function, which is close enough to explain the overall characteristics of the algorithm.


Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause I'm interested in the complexity of a particular variant of 1-in-3 SAT. Assume, as is usual, that clauses are allowed to be of length 1, 2, or 3. Then add the restriction that for any clause of length 3, at least one variable must be "unique," meaning it must appear in no other clause.

Another way to phrase this is, for each clause, at most two variables can be "non-unique" and appear in other clauses.

What is the complexity of this variant of 1-in-3 SAT?

This variant of 1-in-3 SAT is polynomial time solvable. I will try to show this using the fact that 2-CNF-SAT is polynomial time solvable: wikipedia 2-SAT. (There may be better ways or more efficient algorithms for this particular problem)

Given a special 1-in-3 sat formula $F$, do the following:

Keep the size-1 clauses
Replace any size-2 clause $(\ell_1, \ell_2)$ by formula $(\ell_1\vee \ell_2) \wedge (\neg \ell_1 \vee \neg \ell_2)$
For a size-3 clause $(\ell_1,\ell_2,u)$ where $u$ is unique to this clause: replace it by $(\neg \ell_1 \vee \neg \ell_2)$

It is easy to see that this results in a 2-CNF formula, let's call it $F'$. Use your favorite way to solve 2-SAT to find out whether $F'$ is satisfiable.

Verify that the original 1-in-3 SAT formula is satisfiable, if and only if $F'$ was satisfiable. (If this needs more explanation let me know)


Prim's Algorithm - Building the Priority Queue Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then set to $0$. All of the vertices are then inserted into the PQ.

Does that mean that we can insert the vertices in any order into the PQ?
Given that we can insert the vertices in any order, suppose we have a graph with the following vertices $a$, $b$ and $c$ and the following weights $w(a,b)=1$, $w(a,c)=2$. Once we set a.key = 0 and then extract a from PQ, we have b.key = 1 and c.key = 2. Given the answer to (1) was yes, my understanding would be that in a binary tree representation of the heap, $b$ would now be the root and $c$ would be a child of $b$. However, depending on the order in which the $a$, $b$ and $c$ were added to the heap, $c$ could be either the left or right child of $b$, right?
Suppose now that the graph has vertices $a$, $b$, $c$, $d$ and edges $(a, b)$, $(a, c)$, $(a, d)$. Suppose they were inserted into the heap in the order $a$, $b$, $c$, $d$. The binary tree representation of the heap should then be:
$a$ is the root, $\operatorname{left}(a) = b$, $\operatorname{right}(a) = c$, $\operatorname{left}(b) = d$

So, that would mean that the parent-child relationships do not correspond to the parent-child relationships in the original graph and they don't have to, right?

Assuming your PQ is backed by a heap (as you refer to it later). Since the only invariant in a heap is that the parent must be $<$ the children (heap property) you can see there can be no ordering between children of a single parent. A priority queue will always return you the minimal element regardless of order, just think about how $\min$ works: $\min\{1,2,3\}=\min\{2,3,1\}=\min\{3,2,1\}$.
Because a heap is represented in a continous array, you'll have $[b, c]$ after removing $a$ which means that $c$ will always be the left child. Look at the heap image on Wikipedia and notice it's leaning left.
Yes, that's the order they'll be in a usual heap, because all their weights are $\infty$. But any other structure (regardless of insertion order) would be acceptable as long as $a$ is the root, because it wouldn't hurt the heap property.

  parent-child relationships [in PQ's heap] do not correspond to the
  parent-child relationships in the original graph

That is absolutely correct. Just because your PQ is backed by a heap which encodes a tree you can't assume that the graph structure will have anything to do with the heap tree's structure. Just think about a non-tree graph with cycles and multiple edges between vertices: how would that be reflected in the heap's tree? There isn't even a correspondence with the partial MST.

Another argument: the whole structure correspondence breaks big time as soon as you modify just one key in the heap and sift it to it's place. For example:

     a(0)                            a(0)
   b(∞) c(∞)   --- d.key = 1 -->   d(1) c(∞)
 d(∞)                             b(∞)

even before modifying the key $d$ was the child of $b$ which wasn't true in the graph and is not even reachable. The same is true after modification for the reverse.

The best is to think of a PQ as:

interface PriorityQueue {
    add(node, cost)
    update(node, cost)
    (node, cost) popMin()
}

the fact that it's implemented as a heap shouldn't be of a concern, just assume that the PQ does add and update in $\mathcal{O}(n\log{n})$ and popMin in $\mathcal{O}(1)$ to get quasilinear runtime of Prim's algorithm. Even when you implement it you should separate the algorithm from the PQ implementation.


Signed and Unsigned Loads in a 32-bit Registers I have a question over this quote directly out of Computer Organization and Design, 5e:

Signed versus unsigned applies to loads as well as to arithmetic. The function of a signed load is to copy the sign repeatedly to fill the rest of the register—called sign extension—but its purpose is to place a correct representation of the number within that register. Unsigned loads simply fill with 0s to the left of the data, since the number represented by the bit pattern is unsigned.
When loading a 32-bit word into a 32-bit register, the point is moot; signed and unsigned loads are identical.

(Chapter 2.4, pg 76; Patterson and Hennessy). [emphasis mine]
I do not immediately grasp why signed values do not matter for a full 32-bit word in a 32-bit register. The authors do not go on to clarify exactly why this is. My best guess from the materials of the book is because registers are to be sign agnostic with regard to the data within them and how they are interpreted is up to the assembly code? This would make sense if it weren't for the lack of a signed lw operation for MIPS, the language chosen for the text.
Thank you for any clarification on this.

A $n$-bit bitstring can be interpreted semantically both as an unsigned integer in the range $0$ to $2^n-1$, and as a signed integer in the range $-2^{n-1}$ to $2^{n-1}-1$. There is always a way to assign an $n_1$-bit bitstring to an $n_2$-bit bitstring so that both have the same semantics, but the way to do that depends on whether the semantics is unsigned or signed. In the unsigned case, we use zero extension: we affix $n_2-n_1$ zeroes on the left. In the signed case, we use zero extension: we affix $n_2-n_1$ copies of the sign bit on the left.

As an example, consider $x=1111$, and suppose that we wish to assign it into an 8-bit bitstring. In the unsigned case, the value of $x$ is $15$, and the extension is $00001111$. In the signed case, the value of $x$ is $-1$, and the extension is $11111111$.

When $n_2 = n_1$, there is nothing to extend, so the signed and unsigned cases are the same. That's why the point is moot in such cases.


Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be contradictory.

But there are several other reformulations of this problem. E.g. d-Hitting set problem can be solved in polynomial time (when each class or set contains no more than d elements).

Maybe the weighted case has completely different algorithms and complexity estimation? Apparently the non-weighted problem is the special case of weighted one and therefore there should not be different complexity estimation, isn't so?

The unweighted case is a special case of the weighted case, corresponding to all weights being equal. Therefore the unweighted case is easier or as hard as the weighted case. The reason is that given an algorithm for the weighted case, you can use it to solve an unweighted problem by endowing the relevant objects with unit weight.


Is it legal to draw an NFA with fewer nodes than what I normally see? Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?

It is not a convention. You must know that a regular expression denotes one regular language and this language can be generated by an infinite number of differeny automatona (in this case we are talking about NFA).

Why are you always encountering the second automaton in the books? This is probably because the second automaton is obtained from the regular expression $1^*0$ using a well known method called Thompson's construction.

Which of the two automata is better? There isn't just one answer. The first NFA looks simpler but maybe you will have more work when you try to formally prove its correctness. In the other hand the second automaton looks more complex but it was obtained by a proven method so we are sure that it is correct.


Minimum distance in an undirected weighted graph to cover k nodes using teleportations I have been practicing problems on graphs and shortest paths and
I encountered a problem that I'm struggling to understand.
Can you give me any tips and/or can you confirm that I got the general
concept of the problem right?

In a given undirected weighted graph $G=(V,E)$ and an integer $k$ and
edges with positive weights, the starting point is node $v_0$.  You
have to visit every node from $v_0, v_1, v_2, \dots, v_{k-1}$.  If you
visit any of those $k$ nodes you are allowed to create a portal in
them.  You can only make portals in those $k$ nodes.  From one portal
you can teleport to any other without any cost to the path.
You have to create a function double shortestPath(int k) that
returns a shortest path to visit all $k$ nodes using teleportation
system (if necessary).

I sketched this graph and tried to understand the problem here. Lets say we have to visit nodes 0,1 and 2.

Edited (Please check the reply to see better example of the problem)
My approach is this: If I take this route $0 \to 5$ (cost 1) then $5
\to 4$ (cost 2), $4 \to 2$ (cost 3) and then jump from $2 \to 0$ and go
$0 \to 1$ (cost 9). This is the shortest path using teleportations.
Can someone tell me if I understood this problem correctly and maybe
give some tips on how to implement the algorithm?

You can do this in polynomial time with a greedy algorithm by always
traveling to the nearest un-visited terminal, and dropping a portal in
every terminal.
The crucial observations are these:

Since it's free to drop a portal and use one, you always put a portal in each of the terminals.
There is no point traveling anywhere but to a terminal.
When you move to a terminal, you always travel from the closest portal.

Let $G = (V, E, w)$ be the input graph and $T \subseteq V$ be your $k$
terminals, with $v_0 \in T$.
Start with $T' = \{v_0\}$.  While $|T'|<k$, pick a terminal not in
$T'$ that is of shortest distance from $T'$ and add it to $T'$.  Sum up
the distances traveled in total.
Notice that you can preprocess your graph in $O(t^2 (n+m))$ time to get
a new (complete) graph $G' = (T, E', w')$ with only vertices from $T$ and
where the edge $t_1t_2$ has $w'(t_1, t_2) = \text{dist}_G(t_1, t_2)$.
Edit: This answer is updated.  The previous answer was based on Steiner Tree.


calculating the string similarity of an optimal alignment description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the substring of s2, that has the biggest similarity to s1. The following alignments are possible:
[s2[:i] for i in range(len_s1)] + [s2[i:i+len_s1] for i in range(len_s2))]

e.g. for s1="ab" and s2="abcde" the following alignments should be considered:
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

The similarity between s1 and the substring s2_substr of s2 is defined in terms of a normalized version of the InDel Distance. The InDel-Distance is a variation of the Levenshtein distance, that only allows the use of insertions and deletions (this can be e.g. achieved using a weight of 2 for substitutions). The distance is normalized in the following way: $1 - dist / (len\_s1 + len\_s2\_substr)$. I am using a bitparallel algorithm to calculate the InDel-Distance in $O([len_s1/w]len_s2)$ with the computer wordsize w (64 bit or higher when using SIMD). The algorithm is described in the paper New Bit-Parallel Indel-Distance Algorithm by Heikki Hyyrö.
Example
Here is a small example that shows how this algorithm works:
For this example I am using the same example string shown above (s1="ab" and s2="abcde").
As shown above this generates the possible substrings of s2:
['', 'a', 'ab', 'bc', 'cd', 'de', 'e']

These substrings have the following similarities to s1

s1
len_s1
s2_substr
len_s2_substr
distance
similarity

'ab'
2
''
0
2 DEL -> 2
1 - 2 / (2+0) = 0

'ab'
2
'a'
1
1 DEL -> 1
1 - 1 / (2+1) = 0.66

'ab'
2
'ab'
2
0
1 - 0 / (2+2) = 1

'ab'
2
'bc'
2
1 INS, 1 DEL -> 2
1 - 2 / (2+2) = 0.5

'ab'
2
'cd'
2
2 INS, 2 DEL -> 4
1 - 4 / (2+2) = 0

'ab'
2
'de'
2
2 INS, 2 DEL -> 4
1 - 4 / (2+2) = 0

'ab'
2
'e'
1
1 INS, 2 DEL -> 3
1 - 3 / (2+1) = 0

In this case the alignment 'ab' <-> 'ab' has the biggest similarity, so the function should return a similarity of 1.
Naive solution
A naive sliding window approach could calculate the distance in the following way:
max_similarity = 0
for s2_substr in variations:
    substr_similarity = similarity(s1, s2_substr)
    max_similarity = max(max_similarity, substr_similarity)

However this would have to test len_s1 + len_s2 possible alignments, so
it has a complexity of O([len_s1+len_s2]*[len_s1/w]*len_s2. This becomes very slow for longer strings.
Different implementations of this algorithm
A relatively similar implementation is included e.g. in the Python library FuzzyWuzzy, which searches for the longest common substrings of s1 in s2. The starting points of those substrings are then used to calculate the best alignment. However it is not guaranteed, that the optimal alignment starts with one of the longest common substrings and therefore calculates a wrong similarity in many cases.
Question
Is there a faster algorithm to calculate this kind of similarity?
The algorithm has the following requirements:

defines similarity in Terms of the normalized InDel-Distance
allows Gaps at start and end of s2
when s2_substr is not placed at the start or end of s2 it requires the length len_s1

As suggested by D.W. the smallest distance with gaps at start and end can be found by making insertions to the smaller string free in the start (init first row of the distance matrix with 0 instead of insertion costs). The smallest value in the result row is the distance for the smallest alignment. However this approach has a couple of problems:

it does not guarantee, that the length of the substring s2_substr is len_s1 for substrings that do not start at the start or end of s2. (Maybe this could be guaranteed with a modification, that I am just not aware of)
it searches for the alignment with the smallest InDel Distance. However I am trying to optimize the normalized InDel Distance as described above. Since the normalization depends on the length of the substring s2_substr, which is not constant (at start/end of the string it can be smaller than len_s1), this does not always give the correct results.

I think you should be able to adapt the standard dynamic programming algorithm to this, with a minor modification: you simply treat deletions at the beginning and end of s2 as costing 0.


Density of regular language containing all squares I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.

Suppose we have a regular language $L \subseteq \{0,1\}^*$ and the language $ \mathbf{S} = \{uu: u\in \{0,1\}^*\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$. How would I show that there are at least $a2^n$ length $n$ binary words in $L$, for infinitely many $n$? Where $a$ is some constant that can depend on $L$.

Clearly $\mathbf{S}$ is non-regular, so there must be more length $n$ words accepted, but I am not sure how to get $\Theta(2^n)$ length $n$ words. Somehow one has to use the regularity of $L$, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.

Suppose that the Myhill–Nerode relation of $L$ has the equivalence classes $C_1,\ldots,C_m$. Let $N_i(n) = |C_i \cap \{0,1\}^n|$. If $x,y \in C_i \cap \{0,1\}^n$ then $x^2,y^2 \in \mathbf{S} \subseteq L$, and so $xy,yx \in L$ since $C_i$ is an equivalence class. Therefore
$$
|L \cap \{0,1\}^{2n}| \geq \sum_{i=1}^m N_i(n)^2.
$$
Since the function $x^2$ is convex, the right-hand side is minimized (under the constraint $\sum_i N_i(n) = 2^n$) when all $N_i(n)$ are equal. Therefore
$$
|L \cap \{0,1\}^{2n}| \geq m (2^n/m)^2 = \frac{2^{2n}}{m}.
$$

The same argument works if we replace $\mathbf{S}$ with similar languages. Suppose for example that $L$ contains the language of all palindromes $\mathbf{P}$. If $x,y \in C_i \cap \{0,1\}^n$ then $yy^R \in \mathbf{P} \subseteq L$, and so $xy^R \in L$. Just as before, this shows that $|L \cap \{0,1\}^{2n}| \geq 2^{2n}/m$.

Furthermore, for each letter $\sigma \in \{0,1\}$, we have $y\sigma y^R \in L$, and so $x\sigma y^R \in L$. Therefore
$$
|L \cap \{0,1\}^{2n+1}| \geq \sum_{i=1}^m 2N_i(n)^2 \geq 2m(2^n/m)^2 = \frac{2^{2n+1}}{m}.
$$
In total, we get, for all $n$,
$$
|L \cap \{0,1\}^n| \geq \frac{2^n}{m}.
$$

Consider now the language $L_k$ of all words in which the first $k$ letters are the same as the last $k$ letters, reversed. This language has $m = \Theta(4^k)$ equivalence classes, contains all large enough palindromes, and has density $1/2^k = \Theta(1/\sqrt{m})$. This suggests the following vague question:

  What is the minimal density of a regular language having $m$ equivalence classes and containing all palindromes or all squares?


Max-min of a nonconvex quadratic problem I am trying to solve the following problem, which is a simplification of our original question:

$\max\limits_{x,y}\min \{x_iy_i-b_i \mbox{ for } i=1,\ldots, n: x,y\in \Delta_n\}$

where $\Delta_n$ is n-dimensional unit simplex and $b_i$'s are arbitrary nonnegative numbers. $x_i,y_i$ is the $i^\mbox{th}$ entry of $x,y$ resp..

When all $b_i=0$, I can argue the optimum is $\frac1{n^2}$. But in general I have no progress. On the other hand, it would also be nice to show that this problem is NP-hard, but I am unable to think of a reduction from a combinatorial problem. It would be awesome to hear some suggestions! Thanks in advance.

Orion

I assume that your "unit simplex" is the set of all nonnegative points whose coordinates sum to 1, $\{x: x_i\ge 0, \sum x_i = 0\}.$

Note that the max occurs when $x=y$ as $x_iy_i\le \left(\frac{x_i+y_i}2\right)^2$.  This makes your problem easy to solve, as at the optimal $x$ either $x_i^2-b_i$ is the solution, or $x_i=0$ and the solution is less than $-b_i$, so a binary search on the sorted $b_i$ should get your answer quickly.


Are there any non-naive parallel sparse matrix multiplication algorithms? I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on algorithms for multiplying sparse matrices.

However, all I found so far were different ways of arranging the more or less naive "outer product" algorithm between processors - the same total number of multiplications/additions with different amounts of communication and additional algorithmic overhead (which, though, is undoubtedly important).

The most non-trivial algorithm I found was the Yuster-Zwick algorithm described in Fast sparse matrix multiplication, which is basically a combination of the same old naive algorithm and using a fast dense method for the dense part of the problem.

I looked at how sparse matrix multiplication is implemented in MLLib and it, too, appears to use the simple block-based algorithm.

Are there any parallel algorithms for multiplying sparse matrices that are substantially different from the naive one - as different as Strassen's or Coppersmith-Winograd's algorithms are from the naive algorithm for multiplying dense matrices?

For concreteness, let us assume that the matrices are sparse enough that number of non-zeros in the arguments and in the result are both $O(N)$.

This recent paper proposes a different approach, based on hypergraph partitioning.

Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. 2015. Brief Announcement: Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Multiplication. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA '15). ACM, New York, NY, USA, 86-88. DOI=10.1145/2755573.2755613 http://doi.acm.org/10.1145/2755573.2755613


Can we improve the precision of IEEE floats by dropping leading zeros in the mantissa? It seems like it would be possible to add more precision to the IEEE 32-bit mantissa system if the leading zeroes were also dropped, just like the leading 1 is dropped due to it being implicitly known.

For example, the number 17 would be represented as 0|10000100|00010000000000000000000. The leading 1 of the mantissa is always dropped, since every number in scientific notation starts with a 1. My question is why can't the leading zeroes also be dropped? If we know based on the exponent that the decimal place gets moved 4 spots, shouldn't we also be able to deduce, just like the implied 1, that all other missing bits afterwards would be 0? Granted, in this example it wouldn't make a difference, but for larger numbers, or numbers with a lot of digits past the decimal point, it seems like you would be able to get more precision the more implied bits you drop.

(As I'm typing this, I'm also realizing that you might even be able to drop the next 1 in the mantissa. If the computer knows the number of places to move the exponent, you could have as many zeroes as you want sandwiched between two implied 1's)

Does anyone know if this was ever addressed (or if I completely messed up in my calculations, and it isn't really possible to drop that many bits)?

If you drop the leading zeroes then $3,5,9,17$ and so on will all have the same representation. Don't forget that the number being represented need not be an integer.


Can someone provide a trivial example to the "reduction" procedure used to prove hardness? I cannot comprehend how you can prove hardness between two NP complete problems.

For example, let X be a NP hard problem, I want to prove Y is also NP hard.

I can do this by reducing X to Y, if Y is as difficult as X then it is NP hard, otherwise it is not.

But how is this done exactly? Do we restate the problem?

When I looked online it was something about reducing 3 SAT problem to Clique problem, but I don't even know what these problem are.

Is there a trivial example showing how this is done? Thanks!

First of all It may be a good idea to read about SAT and Clique problems. Quite a good point to start your research in NP problems. I'd suggest investigating SAT-3CNF, as it is a flagship example of an NP-Complete (both NP-Hard and in NP itself) problem.

Now, to show that an NP-Hard problem X can be reduced to Y would indeed prove that Y is NP-Hard too. To do that you need to provide a relation that maps X to Y (so for any example from X this function maps it to an example from Y.) What you basically want to show is that being able to solve Y efficiently, you'd be also able to solve X efficiently. Personally I believe you should start by reading about SAT-3CNF and Independent Set problems - there are some great examples explaining how they are equivalent, and the mapping is pretty intuitive. You may read about them, for example, here.

To answer your last question - I believe dealing with NP problems can be treated as non-trivial itself. Therefore I would recommend to spend just some time with them, get used to them and try to understand them, so that you are not just pointlessly trying to memorize problems and solutions.


Combinations of elements with mutual relationships I need to create the combination of 3 elements from a array of given n elements, however every of those 3 el. has to be in "relationship" with each other. Here is an example I can describe my issue better on:

We've got elements 1, 2, 3, 4, 5 & 6. We know following relationships:

1 <--> 2
1 <--> 3
1 <--> 4
1 <--> 6
2 <--> 3
2 <--> 5
3 <--> 5
3 <--> 6
4 <--> 5
4 <--> 6

A group {1,2,3} is viable, because 1 is in relationship with either 2 & 3 and 2 is in relationship with 3.

In a group {1,2,4} is 1 in relationship with 2 & 4, however 2 isn't with 4, thus this combination can't exist.

I programmed a functional solution(which involved the above mentioned creating of combinations, redirecting to the list of relations of every element) for small amount of elements and relationship, but I need to have one for approx. 500 000. I'm a high school student and I haven't met a branch of mathematics which would help me to understand or to solve this problem.

I've been searching the net and I think that a relational algebra (binary relations) might be the solution, yet I'm not quiet sure where to start.

Can you think of any hint, advice, web source or view that could help me?

Thank you

The relevant branch of mathematics is graph theory.

Your elements are the vertices of the graph and the relationships between them are the edges. The triples you're looking for are known as triangles: sets of three vertices with all possible edges between them.

I'm not quite sure what you're looking for in your question. If you just want a list of all the triangles in the graph, that can be done naively just by trying all the triples. If you have $n$ vertices in your graph, that takes about $n^3$ tests. More advanced algorithms turn out to be closely related to matrix multiplication, which can be done a little faster – roughly $n^{2.5}$ steps.  That might still be rather slow for half a million vertices. If you want to go faster, you'll have to either use approximations (if you're happy with finding most but not necessarily all of the triangles). Alternatively, the particular graph you're interested in might have properties that make it easier to find triangles, for example by ruling out a lot of the possibilities.

Your Google search term is "enumerating triangles in graphs".


Sorting array with at most two inversions I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case.

I have no idea how to prove that it is optimal in terms of the number of comparisons. The only argument which came up to my mind is that we of course have to read the whole array, but I don't think it is a proper argument. I tried to use argument similar to minimal number of comparisons to find minimum (with graph), but it doesn't seem to be good in that case.

How can I prove that $n$ comparisons is optimal in the worst case?

To show that the optimal number of comparisons is $m$, you have to prove that any algorithm that uses $m-1$ comparisons must make a mistake on some arrays. The usual way to accomplish that is through an adversary argument – you "react" to the queries of the algorithm in a specific way, and ensure that after $m-1$ steps, there are two different linear orders that are consistent with your answers to the queries (as well as comply with the constraints – in this case at most two inversions).


Time complexity of algorithm inversely proportional to size of sub problem? Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$.

Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$.

Therefore from I.H. (plugging in the formula at $\frac{n-1}2$):

$$T_n = C\log_2(\frac{n-1}{2}+1) + 1$$
$$T_n = C\log_2(\frac{n+1}{2}) + 1$$
$$T_n = C\log_2(n+1) - C + 1$$
Setting $C = 1$ gives

$$T_n = C\log_2(n+1)$$

And so by induction

$$T_n = \log_2(n+1)$$

This result makes very little sense to me. How come reducing the size of the subproblem from $n/2$ to $(n-1)/2$ increases the time it takes? (From Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$. Similarly, increasing to $(n+1)/2$ gives $T_n = \log_2(n-1)$. What am I failing to see here?

I am afraid that you fell prey to ambiguous notations.

To clarify, the subscript $\frac{n-1}2$ in the recurrence relation, $T_n = T_\frac{n-1}2 + 1$ must mean the integer division of $n-1$ by 2 as used in most programming languages, i.e., $\frac 22=1$ and $\frac32=1$. The following equality does NOT hold,

$$\log_2(\frac{n+1}{2}) = \log_2(n+1) - 1,$$
where the division on the left hand side is the integer division. For example, you can check the case when $n=2$.  In the light of that clarification, $T_n = C\log_2(n+1)$ with any constant $C$ cannot be a solution to that recurrence relation.

Now, you might insist that $\frac{n-1}2$ means the usual math division of $n-1$ by 2, i.e., $\frac{3-1}2=1$ and $\frac{4-1}2=1.5$, so that $T_n = C\log_2(n+1)$ could be a solution to that recurrence relation. Well, in that case, that recurrence relation, together with the initial conditions $T_0 = 0$ and $T_1 = 1$ does not define the value of $T_2$, since $T_2=T_{0.5}+1$, where $T_{0.5}$ is not defined. That means, it does not make any sense to involve $T_2$, $T_4$, etc in any equality, since they are not defined!

By the way, it is wrong that "from Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$". What Master's theorem tells us is, $T_n = T_{n/2} + 1 \Rightarrow T_n = \Theta(\log_2(n)).$


Does counting sort require mutation? I'm trying to implement counting sort in Haskell for a list of type (Int, String). I've been trying to do it according to Wikipedia's description.

After some attempts, I gave up, because the Wikipedia description makes heavy use of mutation in different places throughout the algorithm, which I just don't know how to translate to a declarative language.

So my question is, does counting sort require mutation or can it be implemented in a language like Haskell without fancy constructs?

First off, a persistent map from address to value can simulate RAM. There is a time overhead of $O(\log(s))$ and a space overhead of $O(s)$, where $s$ is the space used.* So an algorithm that runs in time $t$ and space $s$ in RAM has a purely functional algorithm in time $O(t \log(s))$ and space $O(s)$. However, simulating the RAM itself, at least conceptually, creates a purely functional computer, not version of the particular algorithm in question, so it probably isn't what you're looking for.

Fortunately this algorithm can be tweaked slightly to be purely functional. Using a persistent sorted map from list item to count, you can traverse the list, updating the count in the map for each list item encountered in $\theta(n \log(c))$ time and $\theta(c)$ space, excluding input and output lists, where $c$ is the number of distinct values. Then, you can concatMap the (list item, count) pairs to count occurrences of the list item. As the map is already sorted by list item, the resulting list will be sorted.

The original algorithm runs in $\theta(n)$ time and $\theta(c)$ mutable space, excluding input and output lists, so the functional version introduces a factor of $\log(c)$ in its run time, which is the same factor introduced by simulating the RAM.

* Specifically, as far as time is concerned, $s$ is the mutable space used, as any immutable space can be provided separately in a read-only array so it doesn't impose any time penalty.


About being able to sample a permutation of a finite set uniformly at random I was looking at this question.

So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt.

Is the above summary right?
Is there a reference to a proof of the above?
Is there a fundamental understanding of this impossibility?
If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility?
What are the consequences if hypothetically one could do the above?

Claim. Given access to finitely many samples of the uniform distribution over $\{1,\ldots,N\}$, you can sample uniformly from $\{1,\ldots,M\}$ iff $M \mid N^k$ (read: $M$ divides $N^k$) for some $k$.

Proof. Suppose first that $M \mid N^k$ for some $k$. Combine $k$ samples of $\{1,\ldots,N\}$ to get a uniform sample $x$ of $\{1,\ldots,N^k\}$, and return $x \pmod{M}$, which is understood to return a value in $\{1,\ldots,M\}$ rather than the more usual $\{0,\ldots,M-1\}$. There are exactly $N^k/M$ preimages of each $y \in \{1,\ldots,M\}$, namely $y,y+M,y+2M,\ldots,y+(N^k/M-1)M$. Therefore $x \pmod{M}$ is a uniform sample from $\{1,\ldots,M\}$.

Suppose next that using $k$ samples you can sample uniformly from $\{1,\ldots,M\}$. As before, we can think of the $k$ samples as a uniform sample from $\{1,\ldots,N^k\}$. Let $A$ be the preimage of $1$, that is the set of $x \in \{1,\ldots,N^k\}$ which cause the algorithm to return $1$. Since the algorithm returns $1$ with probability $1/M$, we must have $|A|/N^k = 1/M$ and so $|A| = N^k/M$, which can only happen if $M \mid N^k$. $\qquad\square$

Sampling a permutation on $M$ elements is the same as sampling a number in the range $\{1,\ldots,M!\}$. This is possible using finitely many samples from $\{1,\ldots,N\}$ if and only if $M! \mid N^k$ for some $k$.

This proof is quite elementary, so you can probably find many references, though none are really needed.


Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$ Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that
$T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$

There are two cases:

$c_1 + c_2 + ...+ c_k < 1$
$c_1 + c_2 + ...+ c_k = 1$

As I observed (from some problems), in case 1 $T(n) = \theta{(n)}$, in case 2 $T(n) = \theta{(n\log{n})}$
But I didn't find the theory says this always true,
so I'm wondering, generally is this true or a theorem or is there any counterexample?

For example,
of Case 1 : $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n = \theta{(n)}$  and
of Case 2 : $T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + n = \theta{(n\log{n})}$

Your observation is correct. More specifically, we have the following proposition.

(Asymptotic behavior of a kind of linear recurrence) Suppose $T(n)\ge0$ is defined for all $n$ greater than some constant.
$$T(n) = T(c_1n+h_1(x)) + T(c_2n+h_2(n)) + ...+ T(c_kn+h_k(n)) + c n$$
where $c_1, c_2, ..., c_k, c$ are positive constants smaller than 1 and $h_1, h_2, ..., h_k$ are functions bounded by a constant. There are three cases.

If  $c_1 + c_2 + ...+ c_k < 1$, then  $T(n) = \Theta({n})$.
If  $c_1 + c_2 + ...+ c_k = 1$, then  $T(n) = \Theta(n\log n)$.
If  $c_1 + c_2 + ...+ c_k > 1$, then  $T(n) = \Theta(n^p)$, where $p$ satisfies $\sum_{1 \le i \le k} {c_i}^{p} = 1$.

Note that $h_i(n)$ represents a small perturbation in the index of $T$. Since $\lfloor c_{i}x\rfloor =c_{i}x+(\lfloor c_{i}x\rfloor -c_{i}x)$ and that the absolute value of $\lfloor c_{i}x\rfloor -c_{i}x$ is always between 0 and 1, $h_{i}(n)$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function.
For example, $T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lfloor\frac{n}{4}\rfloor) + T(\lceil\frac{n}{8}\rceil) + n$ and $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n$ will have the same asymptotic behavior. Because of this same asymptotic behavior, recurrence relations might be written sloppily from time to time when only their asymptotic behavior are the only concern, such as possibly the case of the current question.

The above proposition is just a special case of the more general situation handled by the Akra-Bazzi method, also explained here.

The question has provided examples for the first two cases of the proposition.

Here is an example of the third case. Let $$T(n)= T(\lfloor\frac12n\rfloor) + T(\lfloor\frac23n\rfloor) + T(\lfloor\frac56n\rfloor)+2019n$$ and $T(1)=0$. Since $(\frac12)^3+(\frac23)^3+(\frac56)^3=1$, we conclude that $T(n)=\Theta(n^3)$.

Exercise. How about $T(1)=1$ and $T(n)= T(\lceil\frac27n\rceil) + T(\lceil\frac37n\rceil) + T(\lceil\frac67n\rceil)+2018n$?


Average-case analysis help I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis?

Considering the following algorithm A which takes as input a bit string b = b_1, b_2, ... , b_n (each b_i is either 0 or 1) and does the following:

A(b,n)
k = 0
FOR i = 1 TO n DO
    IF b_i = 1 THEN
        k = k + 1
j = k mod 2
IF j = 1 THEN
    FOR i = 1 TO k DO
        PRINT("Hello World")

Assuming each string is bit string b is equally likely, what is the average number of "Hello Worlds" that A will print?

The hint I have so far is I need to express the sum directly on the sample space, where $X$ below represents the number of times "Hello World" is printed,   and depends on individual inputs.
$$
E(X) = \sum_{L \in S_n} X(L) \cdot Pr(L)
$$

You haven't stated what the distribution of the initial vector is. I'm assuming that each $b_i$ is independently set to $0$ or $1$ with equal probability.

The first step is to find a formula for the expectation $E$. Let $k$ be the value of $k$, that is, the number of 1s in the vector. We know that $k$ has binomial distribution $\mathrm{Bin}(n,1/2)$. Then
$$
E = \sum_{\ell\text{ odd}} \Pr[k=\ell] \ell = \sum_{\ell\text{ odd}} 2^{-n} \binom{n}{\ell} \ell.
$$
A good idea now is to use the binomial identity $\binom{n}{\ell}\ell = \binom{n-1}{\ell-1}n$:
$$
E = \frac{n}{2^n} \sum_{\ell\text{ odd}} \binom{n-1}{\ell-1} = \frac{n}{2^n} \sum_{r\text{ even}} \binom{n-1}{r}.
$$
When $n$ is even, the binomial identity $\binom{n-1}{r} = \binom{n-1}{n-1-r}$ implies that
$$
\sum_{r\text{ even}} \binom{n-1}{r} = \frac{1}{2} \sum_{r\text{ even}} \left[\binom{n-1}{r} + \binom{n-1}{n-1-r}\right] = \frac{1}{2} \sum_r \binom{n-1}{r} = \frac{1}{2} \cdot 2^{n-1},
$$
and so
$$
E = \frac{n}{2^n} \cdot 2^{n-2} = \frac{n}{4}.
$$
I'll leave you the case of $n$ odd (you get the same answer, but a different trick has to be used).

The answer $n/4$ is what we expect. Here's why. If the if wasn't there, then $E$ would equal the expected value of $k$, which is $n/2$. As it is, we are only printing "with probability $1/2$", so we would expect the answer to be roughly half of $n/2$, that is, $n/4$. Since the printing condition depends on $k$, this heuristic calculation is wrong, though it turns out to predict exactly the correct value. Still, it lends credence to our calculation.


What does it mean the norm symbol applied to a concept? I'm reading this paper:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14
or
http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf

On page 1101 are introduced 2 functions without a precise definition.
It is said that they are functions of the type
$\textrm{f}:\mathbb{A}  \rightarrow \mathbb{N}$
where $\mathbb{A}$  is a set.
For example $\mathbb{A}$ can be a concept or an instance. For regular languages an instance can be a string on the alphabet and the concept a specific DFA (between all DFA on that alphabet) (alternately the concept can be defined as a subset of the set of sets made of all subsets on all the possible instances (namely a subset of $2^X$ where $X$ is the instance space namely all the possible instances). The instances on the subset are the $accepted$ instances, the others are $rejected$ ).

(http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1655&context=cse_research   for precise definitions of instance and concept, look at definitions)

The 2 functions are : $\vert \bullet \vert$ that works on a instance (for example a string). Does mean this function? Can be the length of that instance?

The other function is : $\lVert \bullet \rVert$ and works on a concept (namely yours input is a concept). But I'm not able to imagine what this function means in this context and in the paper isn't explicated.

The only property that the functions $|\cdot|$ and $\|\cdot\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\|x\|=n$.
The difference between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\|\cdot\|$ is defined on $\mathcal{C}$.

These functions are instantiated on page 1115: for $\mathcal{X} = \Sigma^*$, $|\cdot|$ is the length of the word; and for $\mathcal{C}$ being the set of all DFAs on $\Sigma$, $\|\cdot\|$ is the number of states.


How can a computer run an infinite loop? I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop at some point because there are only a couple billion transistors in a microprocessor? Maybe my logic is off.

In a contemporary processor there is, among many other things, a register (digital electronic component to hold some bits) called the Program Counter (PC). It holds the memory address to the current machine instruction.

During normal flow of the program, the PC will always be updated to address the next instruction. However, any loop will be implemented with so called branch or jump type instructions which will cause the PC to address some other instruction, rather than the next one.

One, if not the, simplest infinite loop, is one in which the PC is updated again to the same instruction.

An assembly (MIPS) code example (beq stands for Branch on Equal):

LABEL: beq $0, $0, LABEL # Comment: If 0 == 0,then goto LABEL.


On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query Consider an array of sets. As you know a set must not have multiple elements. I need a data structure to handle following queries:

Insert element x to all sets on interval [ L, R ].
Erase element x from all sets on interval [ L, R ].
Query the sum of sizes of sets on interval [ L, R ] of the array.

Is there any data structure to handle it in something better than $O(n \cdot q)$ Time/Memory complexity? (Something like $q \cdot log(n)$, $q \cdot \log ^ 2(n)$ or $q \cdot sqrt(n)$ where $q$ is the number of queries and $n$ is the size of the array).

Update: interval [ L, R ] means the interval of indices of the array from index L to index R.

I am assuming that inserting a value $x$ to a set already containing it does nothing, which is how sets usually work. Then this can be solved in amortised $\mathcal{O}(\log n \log q)$ time per query, with $\mathcal{O}(n + q \log n)$ memory usage.

Assume you have $n = 2^{h}$ sets (this is not limiting, add some unused sets if you need to). We will build a segment tree on the sets: build a perfect binary tree of size $2n-1$, and index the nodes such that node $1$ is the root, the children of node $i$, $1 \leq i < n$ are nodes $2i$ and $2i+1$, and nodes $n, \dots, 2n-1$ are the leaves. Each vertex represents some interval of the sets, with leaf $i+n$, $0 \leq i < n$ representing the $i$th original set (0-indexed), and each vertex representing the union of the intervals its children represent.

We will store in every node two sets: one containing every value occurring in every set of its interval, but not in every set of its parent's interval, called $all[i]$, and one containing every value occurring in some, but not all of the sets in its interval, called $some[i]$. We also store an integer $sum[i]$, which is $|all[i]|$ times the size of the node's interval, plus the sums of its children.

First note that this data is sufficient to answer queries of type 3 in $\mathcal{O}(\log n)$ time. Say we want to count the total size of the sets in interval $[a, b]$. DFS down from the root, and at every node,

If that node's interval is disjoint of $[a, b]$, return 0
If that node's interval is contained in $[a, b]$, return $sum[i]$.
Otherwise, return $|all[i]|$ times the size of the intersection of $[a, b]$ and this node's interval, plus the return values of recursive calls to this node's children.

Clearly storing the data this way requires at most $\mathcal{O}(n + q \log n)$ memory:

We initially need $\mathcal{O}(n)$ memory.
In a query of type 1, we at worst add $x$ to $\mathcal{O}(\log n)$ sets in our tree, since in segment trees, for any interval $[a, b]$ there are at most $\mathcal{O}(\log n)$ nodes, such that their interval is contained in $[a, b]$, but the interval of their parent isn't.
In a query of type $2$, say we delete $x$ from interval $[a, b]$. If $x$ doesn't occur in $a-1$ and doesn't occur in $b+1$, this operation in fact frees memory. Thus it always uses at most as much memory as two insertions, as we can extend the interval to be deleted until $x$ doesn't occur in $a-1$ and $b+1$, and then re-insert $x$ to the sides.
Queries of type $3$ are read-only, and use no memory.

How to perform operations 1 and 2? First note that we do everything in DFS-order, so updating the stored value is trivial: it's just the sum of the stored values of this node's children, plus the size of this node's interval times the size of this node's first set. So we only need to consider how to update the sets.

For this time complexity, we need amortised analysis. We will use a potential function with value

\begin{equation*}
f = \sum_{i = 1}^{2n-1} |some[i]| \log q
\end{equation*}

With this potential function, it costs no time to delete $x$ from interval $[a, b]$, if $[a, b]$ is the interval of some node $i$, and $x \in some[i]$, and we do not care about updating ancestors of $i$ for now. Deleting $x$ from $some[i]$ takes $\mathcal{O}(\log q)$ time, but the potential decreases by $\log q$. Then recurse to the children of $i$. If $x \not \in some[j]$ for either child $j$, then if $x \in all[j]$, delete $x$ from $all[j]$, otherwise return. This wastes $\log q$ time, but with large enough constants, the potential decrease covers that.

In operation 1, say we want to insert $x$ to interval $[a, b]$. We DFS down from the root, and at every node,

If that node's interval is disjoint of $[a, b]$, return.
If that node's interval is contained in $[a, b]$, first delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise, then add $x$ to $all[i]$ in $\mathcal{O}(\log q)$.
Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time. If $x \in all[j]$ for both children $j$, you have to remove it from $all[j]$ for both children, but this is again just $\mathcal{O}(\log q)$ time.

Thus insertion takes $\mathcal{O}(\log n \log q)$ amortised time, since cases 2 and 3 occur at most $\mathcal{O}(\log n)$ times. For deletion, very similarly, we again DFS and at every node,

If that node's interval is disjoint of $[a, b]$, return.
If that node's interval is contained in $[a, b]$, delete $x$ from the interval for either free if $x \in some[i]$, or at the cost of $\mathcal{O}(\log q)$ otherwise.
Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all[i]$ and $some[i]$ in $\mathcal{O}(\log q)$ time.

Here's a C++ implementation:

#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

class SegTree {
    private:
        vector<set<int>> all, some;
        vector<ll> sum;
        int h = 1;

        // returns 2 if x in all[i], 1 if x in some[i] and otherwise 0
        int val(int i, int x) {
            return all[i].count(x) ? 2 : some[i].count(x);
        }
        void update(int i, int x, int len) {
            int va = val(2*i, x), vb = val(2*i+1, x);
            if (va == 2 && vb == 2) {
                some[i].erase(x);
                all[i].insert(x);
                for (int c : {2*i, 2*i+1}) {
                    all[c].erase(x);
                    sum[c] -= len / 2;
                }
            } else {
                all[i].erase(x);
                if (va || vb) some[i].insert(x);
                else some[i].erase(x);
            }
            sum[i] = (ll)all[i].size() * len + sum[2*i] + sum[2*i+1];
        }

        // [a, b) is query interval, [ia, ib) is the node's interval
        ll recGet(int a, int b, int i, int ia, int ib) {
            if (b <= ia || ib <= a) return 0; // intervals are disjoint
            if (a <= ia && ib <= b) return sum[i]; // contained in query interval
            int mid = (ia + ib) >> 1;
            ll res = (ll)all[i].size() * (min(ib, b) - max(ia, a));
            res += recGet(a, b, 2*i, ia, mid);
            res += recGet(a, b, 2*i+1, mid, ib);
            return res;
        }

        void recErase(int a, int b, int x, int i, int ia, int ib) {
            int v = val(i, x);
            if (b <= ia || ib <= a || v == 0) return;
            if (v == 2) {
                all[i].erase(x);
                sum[i] -= ib - ia;
                if (ia < a) recInsert(ia, a, x, i, ia, ib);
                if (b < ib) recInsert(b, ib, x, i, ia, ib);
            } else {
                int mid = (ia + ib) >> 1;
                recErase(a, b, x, 2*i, ia, mid);
                recErase(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }

        void recInsert(int a, int b, int x, int i, int ia, int ib) {
            if (b <= ia || ib <= a || all[i].count(x)) return;
            if (a <= ia && ib <= b) {
                if (some[i].count(x)) recErase(a, b, x, i, ia, ib);
                all[i].insert(x);
                sum[i] += ib - ia;
            } else {
                int mid = (ia + ib) >> 1;
                recInsert(a, b, x, 2*i, ia, mid);
                recInsert(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h <<= 1;
            all.resize(2*h);
            some.resize(2*h);
            sum.resize(2*h, 0);
        }

        ll query(int a, int b) { return recGet(a, b+1, 1, 0, h); }
        void erase(int a, int b, int x) { recErase(a, b+1, x, 1, 0, h); }
        void insert(int a, int b, int x) { recInsert(a, b+1, x, 1, 0, h); }
};

int main() {
    int n, q;
    cin >> n >> q;

    SegTree seg(n);
    for (int i = 0; i < q; ++i) {
        int t, a, b;
        cin >> t >> a >> b;
        --a; --b;

        if (t == 3) {
            cout << seg.query(a, b) << '\n';
        } else {
            int x;
            cin >> x;
            if (t == 1) seg.insert(a, b, x);
            else seg.erase(a, b, x);
        }
    }
}
```


Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$
and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$

Find the longest contiguous subsequence such that

its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$, and
$(a_i + a_{i+1} + \cdots + a_j) \le D\cdot M$.

I can find the longest contiguous subsequence such that its sum is divisible by $D$, but I don't know how to include the second condition. Can anyone help me to solve this problem? I think it should work in something like $O(N)$ or $O(N \cdot \log N)$.

To find the longest contiguous subsequence such that its sum is divisible by $D$, I use the fact that $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ if and only if $(a_1 + a_2 + \cdots + a_{i-1}) \mod D = (a_1 + a_2 + \cdots + a_j) \mod D$. So, I calculate prefix sum and for every possible remainder I remember when it first occured.

There exists a linear time algorithm.

Compute partial sum $s_j = \sum_{i=1}^j a_i$ and their remainders $r_j = s_j \mod D$.
Consider the sequence $\{(j,s_j,r_j)\}_{j=0}^N$.  For each $0\leq r < D$, compute the subsequence consisting of all tuple $(j,s_j,r_j)$ such that $r_j  = r$.  An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time).  In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.
For each subsequence, apply the following algorithm on it.

Pick two pointer $i,j$, both initialized as the first element in the
subsequence.
If $s_j - s_i > DM$, point $j$ to the successor of $(j,s_j,r_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s_i,r_i)$ in the subsequence.
Repeat step 2 until $j$ points to the last element in the sequence.

Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s_j-s_i \leq DM$.


Split in AVL tree with complexity $O(\log n)$ Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.

The split operation divides the AVL tree into two derived AVL trees, based on key. One of the derived trees should contain all the vertices in which all keys less than the original key, and the second the rest.

I know this can be done in $O(\log^2 n)$ time.  Here's a link to implementation with complexity $O(\log^2 n)$:
https://code.google.com/p/self-balancing-avl-tree/

I also know how to merge two AVL trees, such that the keys of one tree are all smaller than the keys of the other, in $O(\log n)$ time.
Here's an implementation with complexity $O(\log n)$:

def Merge(l, r) {
    if (!l || !r)
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}

Yes, this is possible.

You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.

One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the height of the taller tree and $h_2$ is the height of the shorter tree. As such, merging a list of trees that have descending or ascending heights costs only $O(h_{\max} - h_{\min})$, since the sum telescopes.


Can a Von Neumann CPU be pipelined? Can you pipeline a pure Von Neumann architecture based CPU or do you need seperate data and instruction caches for this? If you include seperate instruction and data caches (then it isn't a von neumann CPU anymore, it's a modified Harvard), how do you unify the data of these caches so that they get stored in a single memory?

A processor that can only support one memory access per cycle can still be pipelined. Such a memory interface would represents a structural hazard for load and store operations. In addition, store operations would introduce the equivalent of a control hazard since they might change instructions that have already been fetched.

The structural hazard can be detected when the instruction is decoded and the pipeline stalled at instruction fetch at the appropriate point. This allows a load or store to execute at the cost of a pipeline bubble. For stores, the processor can speculate that a store does not address memory that holds instructions which will be in the pipeline (or at least that the store not change the semantics of any such instructions). This is comparable to predicting a branch. As branch prediction requires checking the condition and target, store conflict prediction requires a comparison of the store address with the addresses of all instructions that will have been fetched by the time the store data becomes visible to the instruction fetch stage. As a branch misprediction requires flushing the pipeline so would a store conflict misprediction.

If one allows a wider front end and buffering, the impact of the structural hazard can be reduced. Such buffering, even if it is after instruction decode, might be considered a cache.

A processor that breaks some instructions into multiple micro-ops and executes one micro-op per cycle could benefit from such a buffer even if only one instruction is fetched per cycle. Variable length instructions would naturally benefit from a buffer of fetched instructions since a fixed width fetch would often either fetch more than one instruction or fetch only part of an instruction.

If the data access width is greater than the typical instruction length, it also becomes natural to use this greater width for fetching instructions, buffering any excess.

The structural hazard related to loads and stores can avoided by multiporting (or accessing the cache twice within a single cycle) or pseudo-multiporting (banking) the memory. The processor would still have the quasi-control hazard for stores. The main benefits of such an implementation over having separate caches would be somewhat simpler handling of stores and faster operation when running self-modifying code. The processor could still handle the store issue with separate coherent caches, but implementing coherence and handling the delay in realization of stores in the instruction cache would add complexity.

I would argue that a modified Harvard architecture that implements a Von Neumann interface (i.e., is indistinguishable to software except with respect to performance) is Von Neumann. (Recent ISAs generally avoid such guarantees. The benefit of a simpler interface is generally not considered worth the complexity/performance tradeoffs.)


Interval tree: find all intervals containing a given interval Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$ is the number of intervals returned. The only solution I can think of is bruteforcing in $O(n)$ time, but that's clearly too simple.
While looking for an answer I came across stabbing queries and the problem seemed very similar to this one. Is this something I could base my algorithm on or am I on the wrong track?

Edit: I might have an idea, but I'm still missing something.
Let $I=[I_s,I_e]$ and $x$ a node. If $x.s \leq I.s$ then there is an interval that contains $I$ in the left subtree of $x$ if and only if $left[x].max\geq I.e$. Suppose you had a similar statement for the right subtree of $x$, then you could do the following:
If the condition for the left or/and subtree is satisfied, recurse on those trees. Since there must be an interval covering $I$ in these subtrees this will result in $k$ paths with a maximum length of $logn$.
If $x.s > I.s$ there can't be an interval in the right subtree that covers $I$, but there might be one in the left, so recurse on left. If this happens repeatedly until you find a leaf, you get a path of length $logn$ without finding anything.

My question is: given $x.s \leq I.s$, how can I know for sure whether the right subtree of $x$ contains an interval covering $I$?

Hint: A (non-root) interval can only contain I if its parent contains I.

For the algorithm in the pseudo-code below, TestInterval is not called for the same vertex twice, so the complexity is $O(n)$.

Consider the subtree S consisting of all nodes which TestInterval is called on. At every node in S which is not a leaf node, an interval must have been added to intervalContainingI (and k incremented). A binary tree with k non-leaf nodes can have at most $k+1$ leaf nodes. Therefore the complexity is in fact $O(k)$.

vector<int> intervalsContainingI;

void TestInterval(interval x)
{
    if (x.start <= I.start && x.end >= I.end)
    {
        intervalsContainingI.push_back(x);
        if (Exists(x.leftChild))
        {
            TestInterval(x.leftChild);
        }
        if (Exists(x.rightChild)
        {
             TestInterval(x.rightChild);
        }
    }
}

TestInterval(root_node);