title: Big Oh vs Big Theta

text:
# Question
Title: Big Oh vs Big Theta
I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n\_0$ s.t. $f(n) \leq cg(n) \forall n \geq n\_0$.

Similarly, $f(n) \in \Theta(g(n))$ means that $f(n)$ grows approximately as fast as $g(n)$. i.e. $f(n) \in O(g(n)), \Omega(g(n))$.

What I don't get is why people use big Oh for the running time of an algorithm? Shouldn't we be using big Theta. When we say "Running time" of an algorithm, we refer to worst case running time i.e. $T(n) = max \\{ ALG(x): |x| = n \\}$.

So, ex: the worst case running time of linear search on an input of size $n$ ($n$ elements and a target value) is $\Theta(n)$ and $O(n)$, but $\Theta(n)$ gives more information. So, why do algorithm books use $O(n)$ and not $\Theta(n)$.

# Answer
> 1 votes
I see two reasons why people prefer Big Oh over Big Theta:

1. The runtime complexity of an algorithm is *not necessarily* defined as the worst-case runtime complexity. You might also just see it as the runtime on an arbitrary instance of length $n$. Then, if you write for example that the runtime $t(n)$ of an algorithm is in $\mathcal{O}(n^2)$ this means that whatever input of length $n$ you choose, it will always grow asymptotically slower than the function $c \cdot n^2$ for some constant $c$ -- so we're then obviously making a statement about the worst-case runtime.
2. Sometimes when you analyze the runtime complexity of an algorithm you don't know for sure if the worst-case complexity you're giving is really tight. Take for example the runtime complexity of matrix multiplication. There it is still not clear if the runtime $n^{2.3728639}$ is really the worst-case. And thus the runtime is known to be in $\mathcal{O}(n^{2.3728639})$ while it's not sure if it's in $\Theta(n^{2.3728639})$.

But also, you are right that in some cases it would be better to provide a Big Theta bound than a Big Oh bound.

# Answer
> 4 votes
A (sloppy) upper bound is easier to prove than a tight upper bound, let alone upper *and* lower bounds.

Some algorithm's runtime *can't* be given with the same function as upper/lower bound. E.g. simple sorting algorithms are $O(n^2)$, but have lower bound $\Omega(n)$.

Some insist of striving to give performance in asymptotic terms via $\sim$, where $f(n) \sim g(n)$ if

$$\lim\_{n \to \infty} \frac{f(n)}{g(n)} = 1$$

(say as an average, or worst case, in term of number of some critical operation, such as comparisons when sorting). I.e., wiggle room, but no (possibly humongous) constants swept under the rug.

# Answer
> 1 votes
If big-Theta can be used in place of big-Oh, it should be used unless it adds unnecessary difficulty for understanding. There are some subtle cases when big-Theta cannot be used in place of big-Oh, e.g.:

Consider the following problem: sort arrays of even length. The program to solve this problem could be: if array length is odd exit immediately, if array length is even do bubble sort. What's the worst-case running time of this algorithm?

It is surely $O(n^2)$, but it is NOT $\Omega(n^2)$ in the sense $\Omega$ is usually defined. Instead, its worst-case running time is "$\Omega(n^2)$ infinitely often" so to speak (warning: non-standard terminology).

# Answer
> 1 votes
In the reply of "why do algorithm books use big-Oh and not Theta":

Big-Oh is used for the worst case analysis and Big-Omega is used for best case only. But analyzing in terms of Big-Theta, we talk about both Big-Oh & Big-Omega simultaneously.

ie. For Big-Theta it is necessary that Big-Oh == Big-Omega , otherwise we can't talk about Big-Theta.

So, where ever(book/any doc) you see the use of Big-Theta , they are giving the complexity of both Big-Oh & Big-Omega(and both are equal too). But many cases they are not equal then we only use Big-Oh just for worst case.

---
Tags: algorithm-analysis, asymptotics, ambiguity
---


# Question
Title: NSPACE for checking if two graphs are isomorphic
I was studying nondeterministic Turing Machines and came across the following question:

Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible.

My attempt at answering this question goes something like this:

* If G1 and G2 have different no. of vertices and/or edges, reject
* Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.
* Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.

At some point, the above algorithm will go thru all n! possible orderings of G1's vertices, and will exhaustively check to see if there's a bijection.

Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1's vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph?

This is all very confusing, and I'm unsure whether I'm thinking thru this problem the right way. I'd appreciate any help.

# Answer
Saying that at some point your algorithm goes through all $n!$ options is incorrect. You "guess" the permutation, and then check if it is an isomorphism, not just a bijection, the important condition you need to verify is $(u,v)\in E\_{G\_1} \iff \left(f(u), f(v)\right)\in E\_{G\_2}$. You need to store the permutation (which requires $n\log n$ space, since keeping the index of a vertex in {v\_1,...,v\_n} requires $\log n $ space). The verfication can reuse space, so you only need enough additonal space to find the permutations $f(u), f(v)$ for any edge $(u, v) \in E\_{G\_1}$, and check if the corresponding edge exists in $G\_2$. To find those you only need counters up to $n$, which can be saved in logarithmic space. Overall you used $O(n\log n)$ space. Note that you didn't actually need the power of PSPACE here (didn't do anything exponential), so this also proves $GI\in NTIME(n\log n)$.
> 2 votes

# Answer
The algorithm you proposed can be made to work in $O(n \log n)$-space, where $n$ is number of vertices. While permuting the vertices of graph $G\_1$, you can also keep the mapping and reverse mapping from and to original vertices. That way you need not rewrite the whole graph. And you can still check if a particular edge in $G\_1$ maps to an edge in $G\_2$ and vice-versa.

Also, planar graph isomorphism is log-space.
> 2 votes

---
Tags: turing-machines, space-complexity, nondeterminism, graph-isomorphism
---


# Question
Title: To check whether a given number has been computed previously or not
Given a 64 bit positive integer. How to determine in the most efficient way whether the given integer has ever been seen or not?

Implementation in C++11 (Please do include this fact, while suggesting your opinions)

Intent: I am generating numbers randomly, by flipping one bit at a time. I need to check every time on generation of a number whether it has been previously generated or not? ex: 1,4,8,16,3,5,9,11,12, .... .

Current Solution:
1.I can create an unordered\_map. However, I would be wasting memory for storing the value part which is boolean in this case. And also hashing isnt the cheapest operation and also their is a penalty of rehasing.

2. Can create a list and keep it sorted. Too expensive operations --Sorting and lookup.

# Answer
> 1 votes
You could use a hashtable to keep track of all values you've seen before. (You could also use a balanced binary tree data structure, but it will probably be less efficient in practice, due to the overhead of the pointer traversals.)

If you don't mind occasional false positives, you could use a Bloom filter, and that might be even more efficient -- at the cost of occasionally declaring "I've seen this number before!" when you actually haven't.

Questions about specific C++ libraries are off-topic here but can be asked on Stack Overflow once you know what data structure you want to use.

---
Tags: algorithms, data-structures
---


title: Convolutional and Linear block codes

text:
# Question
Title: Convolutional and Linear block codes
Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to implement and does better (than linear codes) in cases where you have higher error probability rates and noisy channels. Information bits are spread along the sequence. Lastly, these codes have memory.

However, linear block codes, especially the newer ones such as polar code, can actually achieve the channel capacity. And, in block codes, information bits are followed by parity bits and code information in blocks. Lastly, they are memory less.

How exactly can a noisy channel contain "memory?" I've read some articles, but would like some more clarification. Right now, I am under the impression that, if we find that an error occurs, with much higher frequency, on the 4th bit, for example, then we shall have some redundancy bit at that location, so no real information is lost. So that when we decode, we simply ignore the 4th bit. Am I right in my understanding?

# Answer
> 3 votes
A memoryless channel is one where the probability of an error at a particular bit is independent of what happened at all prior bit positions. A channel can have memory if errors are correlated across bit positions.

For instance, consider the following simple binary channel: if there was no error in the prior position, then there is a probability of 0.1 that this position and the next 7 positions are all flipped (have an error); otherwise (with probability 0.9) this position is not flipped (no error). This would be an example of a channel with memory, because the probability of error for a particular bit depends upon the location of previous errors. Slightly more generally, bursty errors are an example of a channel with errors.

Note that the question of whether the *channel* has memory is independent from whether the *code* has memory. You can use a memoryless code with a channel that has memory; or use a code with memory with a memoryless channel.

---
Tags: communication-protocols, error-correcting-codes
---


# Question
Title: Why is my trivial reasoning for $PSPACE = PH$ wrong?
If $\sum\_i^p$ denotes $ith$ polynomial hierarchy. And $\sum\_i TIME( T(n) )$ denotes set of languages accepted by $T(n)$ time alternating Turing machine $M$ whose initial state is labeled $\exists$ and sequence of choices leads $M$ to change at most $i-1$ times from states with one label to another.

Then I know $\sum\_i^p= \cup\_c\sum\_i Time ( n^c)$. Then by taking summation on $i$ both sides we get $PH=\cup\_i \sum\_i^p=\cup\_i\cup\_c \sum\_i TIME(n^c)=\cup\_c\cup\_i \sum\_i TIME(n^c)=\cup\_c \sum\_i TIME(n^c)=\cup\_c \ TIME(n^c)=AP=PSPACE$ where $AP=\cup\_c ATIME(n^c)$ ie. set of languages having polynomial runtime using an alternating Turing machine.
Thus we get $PH=PSPACE$, which I know does not have a proof. I am misunderstanding something trivial, but cant figure out what ?

# Answer
> 6 votes
Alternating polynomial time allows for an unbounded number of alternations. In contrast, every level of the polynomial hierarchy only allows for a *fixed* number of alternations. Therefore your argument only shows that $\mathsf{PH} \subseteq \mathsf{AP}=\mathsf{PSPACE}$.

---
Tags: complexity-theory, nondeterminism
---


title: Universal Multi Head Turing Machine

text:
# Question
Title: Universal Multi Head Turing Machine
It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?

# Answer
> 5 votes
No. The logarithmic overhead comes from the fact that the machine you're simulating could have an arbitrarily large state set $Q$ and arbitrarily large tape alphabet $\Gamma$. To simulate any such machine using a fixed, constant number of states and a fixed, constant tape alphabet, you need to code $Q$ and $\Gamma$ as multiple symbols in the universal machine's tape alphabet: specifically, you need $\log |Q|$ symbols to write down the current state of the simulated machine, and each character of the simulated tape will take $\log |\Gamma|$ symbols on the universal machine's tape. (The base of the logarithm will depend on how many symbols you use: for example, simulating in binary will give logs to base 2.)

Because of this, the logarithmic slowdown is unavoidable, even if you use multiple tapes. Indeed, if you only use a single tape, it'll be even worse than logarithmic.

However, see Shreesh's answer for a more significant source of logarithmic overhead, which is logarithmic in the *running time* of the simulated machine, not just the length of its description.

# Answer
> 5 votes
The logarithmic factor in efficiency of universal turing machine $O(C T(n)\log T(n))$ is to simulate $k$ working tapes in fixed number of working tapes of universal turing machine. ***It is not because of alphabet size, number of tapes, or number of states***.

$C$ depends on $M$'s alphabet size, number of tapes, and number of states, but it is independent of $n$ (or $T(n)$), so it can be taken as $O(1)$. Also, we can not just take a very large number of tapes in universal turing machine and say that we will simulate on those tapes; for simple reason than the number of tapes in the simulated turing machine can be higher than whatever number we fix for universal turing machine.

We can simulate $k$ working tapes on a single working tape using $k$ tracks. Or may be $2k$ tracks if we want to keep heads and other markers on a separate track. We can keep the markers just using $k$ tracks also, if we spread out the input and use the in between spaces for markers, similar to what Alan Turing did in his celebrated paper.

In every step of simulation, for moving heads in multi track, we will have to go to and fro the whole tape, leading to a $O(T(n))$ overhead. This will give us $O(CT(n)^2)$ simulation time. There is a clever trick involved that lets us write on multitrack machine with $O(\log T(n))$ overhead. Instead of moving the $k$ heads on the multi-track machine we move the track contents under the head. Furthermore we keep a lot of intermediate special blank spaces on both sides of head in each track to allow us shifting the tape contents more efficiently. This allows us to simulate each step of the turing machine in ***amortized*** $O(\log T(n))$ time. Thus turing machine will be simulated in ***amortized*** $O(C T(n)\log T(n))$ time.

See the complexity theory book of Arora and Barak for details.

Arora and Barak uses 3+ tapes, one for input, one for output and a few as working tapes. But in fact we can use a single tape for all of these and still can simulate any turing machine on any input in $O(CT(n)\log T(n))$ time.

Furthermore, we still don't know if the extra $\log T(n)$ factor is unavoidable for sure, though most probably it is unavoidable. But we might be able to prove that we need $\omega(1)$ overhead. That is, we might be able to prove that we can not simulate every turing machine without any overhead.

---
Tags: turing-machines
---


# Question
Title: Reference Request: Overlaps between complexity theory and dynamical systems?
Per Wikipedia:

> In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a lake.
>
> At any given time a dynamical system has a state given by a set of real numbers (a vector) that can be represented by a point in an appropriate state space (a geometrical manifold). The evolution rule of the dynamical system is a function that describes what future states follow from the current state. Often the function is deterministic; in other words, for a given time interval only one future state follows from the current state however, some systems are stochastic, in that random events also affect the evolution of the state variables.

Is there any result on dynamical system (i.e. solving dynamical equations, finding asymptotic states to a system, dynamics in chaotic system) with complexity theory, hardness for finding a solution, etc.?

Thanks

# Answer
> 3 votes
This is a well-researched area. For a representative result, see Kawamura's proof that solving ODEs is difficult.

A different line of works studies the hardness of computing Nash equilibria and related problems. See for example the recent breakthrough of Bitansky, Paneth and Rosen, who base hardness of cryptographic assumptions; earlier work based it on complexity theoretic assumptions.

---
Tags: complexity-theory, reference-request, discrete-mathematics, mathematical-foundations, physics
---


title: Confusion in Pumping Lemma

text:
# Question
Title: Confusion in Pumping Lemma
I would like to know whether we could pump $ba$ into $bbba$ where *x*=$b$,*y*=a,*z*=$\epsilon$ using the finite state machine given in the image 1.

For example as given in this image 2 where the *string* $babb$ could be pumped into $bbbabb$ using the pumping statement $b^kabb\in L(M\_1),\forall k,k \ge0$ where *x*=$\epsilon$,*y*=$b$,*z*=$abb$,can we pump the string $ba$ into $bbba$ using the pumping statement $b^ka\in L(M\_1),\forall k,k \ge0$ where *x*=$b$,*y*=$a$,*z*=$\epsilon$?

# Answer
To pump a string there is a minimum length on the string. This depends on the language. If a DFA is also given then the minimum length for pumping will be smaller than the number of states.

Since the DFA has 4 states in the problem that you refer to, any acceptable string of length greater than or equal to 4 can be pumped. So yes $bbba$ can be pumped.

However, which substring is going to be pumped is not your choice. In $bbba$ the substring that can be pumped is either $b$, $bb$, or $bbb$.

Suffix $ba$ cannot be said do be *pumpable* in $bbba$ because $bb(ba)^0$ is $bb$ which is not acceptable. Strangely, pumping also means pumping 0 times (which amounts to removing the substring).
> 2 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: On deterministic weighted graph isomorphism from randomized
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\\{w\_1,\dots,w\_s\\}$ where $s=\Omega(n^\alpha)$ where $\alpha\in\[0,2\]$ and the edge weights are picked uniformly. We can think of the second graph as being generated as follows: Input the weighted first graph to a black box and the black box returns the second graph based on some mechanism.

For every $n$ fix a set of weights.

For every input graphs you assign weights uniformly from a distribution. Then you feed in the input graph, weights and the second graph to the black box and the black box returns you the weighted second graph. Then you have to decide isomorphism on these two weighted graphs. So the probability is over all *assignments* of weights (the weight set is fixed for every $n$ in some worst case way). If this has an algorithm that is in $\mathsf{BPP}$ then in theory it should be conjecturally derandomizable.

# Answer
> 1 votes
Consider first the case of two colors. We can identify with each vertex $x$ its color distribution $a$, which is the number of edges of color 1. The distribution of $a$ is $\mathrm{Bin}(n,1/2)$, and so if we divide the vertices into bins according to their color distribution, the heaviest bin will contain $O(\sqrt{n})$ vertices with high probability. If we repeat the process, we the heaviest will contain $O(\log n)$ vertices with high probability. Once more, and we expect all bins to have size 1.

What this sketch suggests is that even if you have a constant number of colors (in this case, 8) then with high probability, every vertex will have a unique color distribution (histogram of colors of the edges adjacent to it). This makes graph isomorphism very easy for such graphs.

Of course, this sketch isn't rigorous. To know for sure, you will have to make it rigorous, and find whether it indeed works; perhaps a constant number of rounds isn't enough, but $\alpha\log n$ rounds (as in your case) are.

---
Tags: algorithms, complexity-theory, randomized-algorithms, weighted-graphs, graph-isomorphism
---


# Question
Title: Results on the difficulty of specific random 3-SAT problems?
This is a companion question to Results on number of solutions to random 3-SAT?

Let $A$ and $B$ be two problems drawn from random 3-SAT, both with the same number of variables and clauses. If $A$ has fewer satisfying assignments than $B$, do SAT solvers perform worse when trying to solve $A$ vs. $B$? Are there any results on this? (I'm a physicist by training, so a follow-up would be: is this even an interesting CS problem?)

EDIT: I wrote a quick little DPLL-based program to calculate the number of satisfying assignments for $\alpha = 4$ and $N = 80$. Here are the # of solutions and time to complete for a few random runs to illustrate the phenomenon that I'm looking for insight into:

* 368 solutions, 2.2 s
* 192 solutions, 8.4 s
* UNSAT, 3.2 s
* 50492 solutions, 2.6 s
* 1212 solutions, 13.9 s

As illustrated above, both the number of solutions and the time to run can fluctuate significantly; is there any relationship between the two?

# Answer
Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:

1. Below a certain threshold, the problem is easy. Moreover, the solution set is "continuous" (with high probability), in that all solutions are (more or less) connected.
2. After a certain threshold, there are no satisfying assignments (with high probability).
3. Between the two thresholds, the instance is satisfiable (with high probability), but a satisfying assignment is conjectured to be hard to find. Moreover, the solutions belong to exponentially many small clusters that are "far away" from each other: any path connecting them goes through an assignment that satisfies a relatively small fraction of clauses.

These thresholds have been calculated by physicists, but their work is not mathematically rigorous. Rigorously much is known, especially for random $k$-SAT and similar problems for large $k$, but the actual behavior for 3SAT hasn't been rigorously proven.

The literature on the area is enormous, but unfortunately I can't find a recent survey, though these probably do exist. You can start by reading a very short, relatively recent survey by Coja-Oghlan. A recent important rigorous result is Ding, Sly and Sun, who prove rigorously that the unsatisfiability threshold for $k$-SAT exists for large enough $k$.
> 8 votes

---
Tags: reference-request, satisfiability, 3-sat
---


# Question
Title: What is the difference between the friend class and inheritance consept in C++?
In C++ ,friend class allows us to inherit the proprieties of one class to another class(es) which is also possible using inheritance. And also in inheritance we can set different levels of privileges to the child class(es) depending on our requirements, which suggests inheritance is more useful than friend class. Then what more can friend class do which cannot be done using inheritance? Why is friend class introduced when there is already inheritance property which has even more functionalities?

# Answer
To declare a class (or a function) a `friend` allows the friend to access private members \[the naming in C++ is *not* my fault!\] (data or function) directly. They aren't "inherited" in any meaningful way. Yes, it creates a interdependency, but very different and a lot weaker than inheritance does.
> 3 votes

---
Tags: programming-languages, object-oriented, c
---


# Question
Title: Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?
Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P\_1 = P\_2 = P\_2 .. = P\_m =0$. I understand that there is some theorem which says that if there is no solution to these simultaneous equations then one necessarily will be able to find polynomials $Q\_1,Q\_2,..,Q\_m, R\_1, R\_2,..,R\_k$ such that $deg(P\_iQ\_i)$ and $deg(R\_i^2)$ are all $\leq d$ for some $k$ and $d$ such that, $\sum\_{i=1}^m Q\_iP\_i + \sum\_{j=1}^k R\_j^2 = -1$

* Can someone kindly reference this theorem and its proof?

Now lets say one is looking at a $d$ which is not sufficiently large. Then one will be looking at the set of all polynomials of the form $S = \sum\_{i=1}^m Q\_iP\_i + \sum\_{j=1}^k R\_j^2$ such that $deg(P\_iQ\_i)$ and $deg(R\_i^2)$ are all $\leq d$ for various $k$. But this is a convex set in the set of polynomials? And $-1 \not \in S$. Then there will exist a separating hyperplane between S and $-1$ and the normal to that plane gives a degree-d pseudo-distribution on S.

* Does someone have a concrete example of the above phenomenon?
* Why is this pseudo-distribution indistinguishable from an actual distribution on $S$ if one is only looking at moments $\leq d$?

# Answer
The theorem you are referring to is known as the Positivstellensatz, but you are citing it incorrectly; given only polynomial *equations*, the relevant theorem would be the Nullstellensatz. See also lecture notes of Laurent and blog posts of Amir Ali Ahmadi.

Regarding pseudodistributions, Barak defines them as linear operators for low-degree monomials which satisfy the crucial property $E\[P^2\] \geq 0$ for low-degree $P$. These are all the properties you need when looking at low-degree moments.
> 1 votes

---
Tags: complexity-theory, np-complete, optimization, np-hard, np
---


title: A problem solved by weighted median

text:
# Question
Title: A problem solved by weighted median
> Given a set of $n$ points $p\_1,p\_2,\ldots,p\_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x\_1,x\_2,\ldots,x\_n$ (not necessarily in ascending orders) and associated weights $w\_1,w\_2,\ldots,w\_n$ such that $\sum\_{i=1}^n w\_i = 1$. The objective is to find a point $p$ on the straight line such that the sum $\sum\_{i=1}^n |x\_p-x\_i|w\_i$ is minimum, where $x\_p$ is the $x$-coordinate of $p$.
>
> Prove that the sum $\sum\_{i=1}^n |x\_p-x\_i|w\_i$ is minimum at a point $p$, where $p$ is such that $\sum\_{x\_i\<x\_p} w\_i \< \frac{1}{2}$ and $\sum\_{x\_i\>x\_p} w\_i \leq \frac{1}{2}$.

I am trying to use algorithm Select to prove it. The algorithm divides the x-coordinates into $\[n/5\]$ sublists such that first $\[n/5\]-1$ sublists contain exactly 5 elements each, while the remaining one contains $n \pmod 5$ elements. Then we find the median of each sublist. Repeat the same process for each sublist.

But I think I get the gist of the problem, I think it is sufficient to prove that if $q$ is any point on the line such that $q≠p$,then $\sum\_{i=1}^n|x\_q-x\_i| w\_i≥\sum\_{i=1}^n|x\_p- x\_i | w\_i$, where $x\_q$ is the x-coordinate of $q$.

But I am going no where with this. Am I using the wrong approach? Should I be using algorithm Min to get this? If yes, can someone explain how to get it?

# Answer
> 1 votes
I don't see how using the **select** algorithm, or indeed any algorithm, is useful here. Instead, try to use the following observation:

> Let $I = \\{ i : x\_i \< x\_p \\}$ and $J = \\{ j : x\_j \> x\_p \\}$. Then the derivative of your objective function with respect to $x\_p$ is $$\sum\_{i \in I} w\_i - \sum\_{j \in J} w\_j. $$

---
Tags: algorithms, optimization, search-algorithms
---


# Question
Title: Merge k sorted arrays of exponentially increasing lengths
I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet.

Given $A\_1, A\_2, ..., A\_k$ sorted arrays where $|A\_i| = 2^i$, what is the most efficient way to merge them all? I'm looking for a comparison-based algorithm with the best asymptotic running time possible.

# Answer
We can describe any merging algorithm in a tree form (each internal node corresponds to a merged array). Suppose that the cost of merging two arrays $B,C$ is *exactly* $|B|+|C|$. Then the total cost equals $\sum\_{i=1}^k d\_i |A\_i|$, where $d\_i$ is the depth of the leaf $A\_i$.

Consider now an arbitrary merge tree $T$. Suppose that $A\_k$ is not a child of $T$. In that case, we can form a new tree $T'$ as follows: let $T^-$ be $T$ with $A\_k$ removed (and its sibling promoted to its father), and let $T'$ be the tree with children $A\_k$ and $T^-$. The cost of $T'$, denoted $C(T')$, satisfies $$ C(T') = 2^k + C(T^-) + \sum\_{i=1}^{k-1} 2^i \< 2\cdot 2^k + C(T^-) \< C(T). $$ Here $2^k$ is the cost of $A\_k$ and $\sum\_{i=1}^{k-1} 2^i$ is the additional cost of all other leaves (since they are all one level deeper).

We conclude that $A\_k$ must be merged last. Continuing this way, we see that the optimal schedule merges $A\_1,A\_2$, merges the result with $A\_3$, merges the result with $A\_4$, and so on.
> 3 votes

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Count all pairs of x,y such as x + y = c && x XOR y = d
> Given two decimals $c$ and $d$; $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements: $$ x+y = c\\ x \text{ XOR } y = d $$

Killed already a day still can't solve that task in 2s. Even with optimizations brute-force algorithm doesn't terminate when $c$ and $d$ closer to upper bound.

**UPDATE** Took a while to figure, here is solution:

```
void solve( Scanner in, PrintWriter out ) {
    long sum = in.nextLong();
    long xor = in.nextLong();

    long andMask = andMask( sum, xor );
    if( andMask == -1 ) {
        out.print( 0 );
        return;
    }

    long sample = sample( sum, andMask );
    if( sample == -1 ) {
        out.print( 0 );
        return;
    }

    out.print( combinations( sample, andMask ) );

}

long andMask( long sum, long xor ) {
    if( ( sum - xor ) % 2 != 0 ) return -1;
    return ( sum - xor ) / 2;
}

long sample( long sum, long andMask ) {
    if( ( ( sum - andMask ) & andMask ) != andMask ) return -1;
    return sum - andMask;
}

long combinations( long sample, long andMask ) {
    long combinations = 1;
    int major = major( sample );
    for( int i = 0; i < major; i++ ) {
        if( bitValue( sample, i ) == 1 && bitValue( andMask, i ) != 1 ) {
            combinations *= 2;
        }
    }

    if( andMask == 0 ) {
        combinations -= 2;
    }
    return combinations;
}

int major( long sum ) {
    int major = 0;
    while( sum > 0 ) {
        major++;
        sum = sum >> 1;
    }
    return major;
}

int bitValue( long value, int bit ) {
    return ( int ) ( value >> bit & 1 );
}

```

# Answer
Hint: $x+y=(x \text{ XOR } y)+2(x \text{ AND } y)$.
> 2 votes

---
Tags: combinatorics, counting
---


# Question
Title: Calculating time complexity of a code which may be incorrect
I am a sophomore taking a course in algorithm analysis. We were asked by our professor to calculate time-complexity of several C functions, but some of them were incorrect and would result in a compile error. As far as I know time complexities of correct algorithms are calculated and then we choose which one to implement. We tried to discuss this with her but she insisted on solving those problems nevertheless stating that it doesn't matter whether the code gets executed or not.

*Is there a way one can realise that the algorithm is incorrect after finding it's time complexity?*

*Does it make sense calculating time complexity for an incorrect program?*

PS :

1) The program wasn't implementing any proven algorithms, it was just some loops.

2) This may sound like a silly question, but my professor got me confused.

Downvotes are welcome but please give your opinion.

# Answer
> 3 votes
On a more practical level, it sounds like this probably just stems from a typo on the instructor's part. If this is in the context of a big-O exercise, I'd just fix the typos and move on. Instructors do make mistakes too!

Getting a bit more abstract, if a program won't run, it doesn't really make sense to speak of its time complexity because it has no runtime.

Getting even more abstract - you actually can use big-O analyses to show that certain pieces of code cannot be correct. For example, suppose someone proposes a new comparison-based sorting algorithm. If you do a big-O analysis and see that it runs in time O(n) in the worst case, you are guaranteed that the code has to be wrong because of the requirement that all comparison-based sorting algorithms run in time $\Omega(n \log n)$ on average. This is different than talking about code that won't even compile, but it does show that analyzing the time complexity of incorrect (here, legal but wrong) code may be worthwhile.

# Answer
> 1 votes
Not obviously - if complexity is below the lower bound - it is probably wrong (e.g. summing N elements require to read N, cannot get lower), but N^2 tells this is not optimal, but this is unknown from that stat whether it works in fact.
If there are simple loops - you can calculate complexity without executing it.
Wall time may be misleading and takes into account resources, cache and other factors.
Simple mistakes in the code like "foor" instead of "for" prevents it from compiling - but if you can correct such mistakes - it changes nothing in complexity.
If code is damaged beyond repeair - it cannot be calculated at all.

Because this is excersise to calculate complexity - yes it makes sense.
If you were given pseudocode - it also does not compile, but still you can calculate it.

# Answer
> 1 votes
Correctness is relative -- with respect to what specification¹?

Technically, C code is *never* run; it is always compiled to some machine code. So, if you want to be really nitpicky, it is *impossible* to properly analyse the runtime cost of C code. You'd need to be told which compiler and machine will be used for executing it.

That said, we usually want to analyse the *represented algorithm* with respect to some *abstract cost measure* instead. That makes a difference because now there is some tolerance for simple syntax errors. As long as it is clear what algorithm we talk about, analyze away. In fact, most sources use more or less well-defined pseudocode instead of real code.

---

1. If the code compiles and does not do what you want it to, it *still* has meaningful runtime costs.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?
This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \\{0,1\\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=\[0100001\dots 01\]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x\_i + x\_j + \dots + x\_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\\{0,1\\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C\_0 = \[0\dots 0\], C\_1 = \[0\dots 0 1\]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b\_i + b\_j + \dots = 1$?", where $b\_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A\_i$ and $B\_i$ where $|A\_i| = |B\_i|$ and ask questions of the form "is $x$ of type $A\_i$ or $B\_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that *any* size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.

# Answer
> 3 votes
Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}\_{2^k}$ for $k\>1$.

---
Tags: coding-theory, encoding-scheme
---


# Question
Title: Does preparing min DFA by combining equivalent states always result in min DFA
I know the following fact:

> If $Ma\_N=\\{w:n\_a (w)=Nk,k≥0\\}$, then Number of states in $$Ma\_{N1}×Ma\_{N2} =Ma\_{N1}∪Ma\_{N2} =Ma\_{N1}∩Ma\_{N2} =Ma\_{N1}-Ma\_{N2} =LCM(N1,N2)$$ where $n\_a (w)$ is the number of occurrences of $a$ in $w$

I recalled the example I solved: the DFA for the language $(111+11111)^\*$. It was given as follows:

It was backed by the fact that Any number greater than 8 can be factored into sum of 3s and 5s.

**Q.1** Can we interpret this language as union of two: $(111)^\*\cup (11111)^\*$?

**Q.2** If yes, then should forming union DFA by forming product DFA (and making desired states final as required by union operation) of above two languages $(111)^\*$ and $(11111)^\*$ and then applying DFA minimization by finding equivalent states result in 9 states? I tried it as below using JFLAP (product DFA on left and auto generated min DFA on right). But I didnt get 9 states. Instead I got number of states $=LCM(3,5)=15$ states.

**Q.3** So can we conclude we cannot always get minimum DFA by the approach of combining equivalent states (may be especially when the DFA can be simplified using some mathematical insights)? Or did I made some mistake?

# Answer
> 1 votes
The answer to Q1 is no.

$1^{11}$ is in $(1^3 + 1^5)^\*$, but not in $(1^3)^\* + (1^5)^\*$

I think that leads to the remaining confusions.

---
Tags: formal-languages, automata, finite-automata, compilers
---


# Question
Title: Restricting possible permutations in Graph Isomorphism problem
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.

Call two such graphs $2n$ vertex labelled graphs $G$, $H$ whose adjacencies are $A$ and $B$ respectively $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ iff there is a permutation $P$ such that $A=PBP'$ on the condition that the permutation $P$ permutes only supervertices (only a subset $n!$ of permutations of $(2n)!$ allowed). In particular, the permutation must map even-numbered vertices in $G$ to even-number vertices in $H$; and if vertex $2i$ in $G$ is mapped to vertex $2j$ in $H$ by the permutation, then vertex $2i-1$ in $G$ must be mapped to $2j-1$ in $H$.

Is $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ $\mathsf{GI}$-$\mathsf{complete}$?

# Answer
It's GI-complete. Here's a simple reduction. Let $G\_0,H\_0$ be any two connected, undirected graphs on $n$ vertices. Consider the vertices of $G\_0$ as even-numbered vertices of $G$, and add $n$ odd-numbered vertices that aren't connected to anything. Construct $H$ from $H\_0$ similarly. Now $G$ is vertex-pair-isomorphic to $H$ if and only if $G\_0$ is isomorphic to $H$, so solving vertex-pair-isomorphism is at least as hard as solving graph isomorphism.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, permutations, graph-isomorphism
---


title: Big-O and little-o notation

text:
# Question
Title: Big-O and little-o notation
I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following:

$$O(n^c) = o(n^k) \text{ for } k \> c$$

For example, $O(n^2) = o(n^3)$ since $3 \> 2$. Basically, any constant times $n^2$ will still grow more slowly than any constant times $n^3$ for large enough $n$.

Does it make sense to have both sides of an equation consist of big-O and/or little-o notations like this, or does one side of the equation have to consist of a bare function only? Thanks.

# Answer
I can suggest two different plausible ways of interpreting the notation.

* One way to understand notation like $O(n^2)$ is to treat it as denoting a *set* of functions. With this viewpoint, we might interpret the claim $O(n^2) = o(n^3)$ as claiming that the set $O(n^2)$ contains exactly the same set of functions (no more, no fewer) as the set $o(n^3)$.
* Another way to understand notation like $n \lg n = O(n^2)$ is to treat this as claiming that the function $n \lg n$ is in the set $O(n^2)$. In other words, when we have $= O(n^2)$ on the right-hand side, we treat that as a sloppy short-hand for $\in O(n^2)$. With this viewpoint, we might interpret the claim $O(n^2) = o(n^3)$ as being equivalent to $O(n^2) \subseteq o(n^3)$, i.e., that the set $O(n^2)$ is a subset of the set $o(n^3)$.

Both interpretations are plausibly defensible: neither one is ridiculous or obviously wrong.

Notice how we start from two different perspectives that are very similar, yet we end up with two completely different interpretations of the claim $O(n^2) = o(n^3)$. This is a sign that writing something like $O(n^2) = o(n^3)$ is a bad idea -- it can easily be misinterpreted. It would be better if the author wrote this differently, in a way that makes it clearer what the author's intent was.

So, this notation is ambiguous or potentially confusing. If you see this in some written material and can't ask the author, you'll just have to guess what was meant from context.
> 2 votes

# Answer
Many people cringe at the notation $n^2=O(n^3)$, since, strictly speaking, $O(n^3)$ is a *set* of functions, defined by $$ O(n^3)=\\{f\mid \exists k\>0, N\ge 0\\, \[f(n)\le kn^3\text{ for all }n\ge N\\} $$ In other words, $$ O(n^3)=\\{1, n, n^2, n^2\log n, n^3, 3n^3+15n^2,\dotsc\\} $$ which is to say $O(n^3)$ consists of all functions $f(n)$ that are eventually less than a constant multiple of $n^3$.

With this understanding, to be precise we should write $n^2\in O(n^3)$, rather than the sloppier $n^2=O(n^3)$. This means that it is indeed notationally correct to ask whether $O(n^2)=o(n^3)$, since they are both sets of functions.

\[Note, by the way, I'm not asserting that $O(n^2)=o(n^3)$. I'll leave that to you to prove or disprove.\]
> 2 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Amortized analysis of base Fibonacci counter
We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good potential function.

Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers. In other words, instead of an array of bits, we keep an array of fits, where the $i$th least significant fit indicates whether the sum includes the $i$th Fibonacci number $F\_i$. For example, the fitstring 101110 represents the number F6 + F4 + F3 + F2 = 8 + 3 + 2 + 1 = 14.

a. Describe an algorithm for an increment operation.

b. Show that a sequence of $n$ operations is amortized $O(n)$ using the potential method.

c. Do the same thing above, but now add a decrement operation.

---

This is what I started out with:

The general rule is to never let two consecutive Fibonacci numbers exist in the counter at the same time. In other words, no two 1's can occur consecutively. This is because of the definition of Fibonnaci numbers, i.e. a number such as 011 can be replaced by 100.

In general, when incrementing, change the least significant bit that's a 0 to 1 (this is one of the two "1" representations that are the first two bits in the counter). Starting from the most significant bit, if some positions $i$ and $i-1$ have 1's, then change them to 0's and change position $i+1$ to a 1. Keep recursing until there are no more consecutive 1's.

Now we will use the potential method to show that the amortized cost of $n$ consecutive increment operations is $O(n)$.

We will define our potential method as follow: (this is one part I'm having trouble with)

I then made the following observation: Suppose the $i-th$ operation makes $x\_i$ Fibonnaci conversions (changing consecutive 1's to 0's and changing the next significant bit to a 1). Then the actual cost is $1 + 3x\_i$.

Any help is appreciated! Thanks!

# Answer
As far as I know, there's no general method for designing a potential function, which makes sense when you consider that they can be used for different purposes. I've been trying on and off for 20 years, and to this day, I have no idea how Sleator and Tarjan came up with the function they used to prove the optimality (with respect to an arbitrary PDF) of splay trees.

Having said that, it often helps to work backwards. I'm going to show you what I mean for the algorithm for incrementing binary numbers. This should give you some ideas about how to proceed.

Let's start by simply checking the number of bit-flips required to increment numbers, starting with zero:

```
+--------------+---------+
| Bit sequence | # flips |
+--------------+---------+
|            1 |       1 |
|           10 |       2 |
|           11 |       1 |
|          100 |       3 |
|          101 |       1 |
|          110 |       2 |
|          111 |       1 |
|         1000 |       4 |
|         1001 |       1 |
|         1010 |       2 |
+--------------+---------+

```

So that's the ruler function, which you may recognise as being the solution to the Tower of Hanoi problem. It satisfies the recurrence:

$$a(2n) = 1$$ $$a(2n+1) = 1 + a(n)$$

But that's neither here nor there. What's interesting is that as you go on, the average number of flips per increment seems to trend towards 2; you can write a little program yourself to verify this, or you can note that half the increments flip one bit, a quarter flip two bits, and in general $\frac{1}{2^i}$ of them flip $i$ bits for $i\>0$. Do the sum yourself.

So we need to design a potential function so that each increment "costs" two flips. If the increment only flips one bit, we want to put another flip in the bank, as it were, so we can withdraw it later. If the increment flips two bits, we want the potential function to be the same, and so on.

Recall that for an operation which transform the state $S\_b$ into the state $S\_e$:

$$T\_{\hbox{amortised}}(S\_b \rightarrow S\_e) = T\_{\hbox{actual}}(S\_b \rightarrow S\_e) + \Phi(S\_e) - \Phi(S\_b)$$

In our case, we want all increments to have their amortised time to be at most 2. So:

$$2 \ge T\_{\hbox{actual}}(0 \rightarrow 1) + \Phi(1) - \Phi(0) = 1 + \Phi(1) - \Phi(0)$$ $$2 \ge T\_{\hbox{actual}}(1 \rightarrow 10) + \Phi(10) - \Phi(1) = 2 + \Phi(10) - \Phi(1)$$ $$2 \ge T\_{\hbox{actual}}(10 \rightarrow 11) + \Phi(11) - \Phi(10) = 1 + \Phi(11) - \Phi(10)$$

And so on. This gets us somewhere, because it gives us some bounds on what the potential function might be.

There are a number of potential functions which could satisfy these constraints. In this case, however, there's a straightforward optimal solution. Setting $\Phi(0) = 0$ and making the inequalities equalities gives us the potential function:

$$\Phi(0) = 0$$ $$\Phi(1) = 1$$ $$\Phi(10) = 1$$ $$\Phi(11) = 2$$ $$\Phi(100) = 1$$

There's no obvious pattern so far, but if you extend this on, you'll find that $\Phi(S)$ is the number of 1's in $S$ (i.e. the Hamming weight of $S$). This makes intuitive sense, when you think about it: Incrementing a zero takes only one flip, but incrementing a one takes more than one. So the number of ones in the string is a measure of how "hard" it will be to increment it in the future. It's a reasonable analogue of "potential energy".

Now that we've identified a candidate potential function, we can now work forward again to try to prove the result.
> 2 votes

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


# Question
Title: How do multiple branches from one node occur with the Monte Carlo Tree Search?
I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (right?). So, a branch never comes out from a non-leaf node. So how could one node have multiple branches (multiple child nodes) coming out of it? Here's a picture, for clarity:

So wouldn't that process just keep getting repeated? It's not a leaf node, so the algorithm won't branch (create another child node)... so it has to pick the next node. And since it only has one option, it must pick that one. It just continues down, until it reaches the end. What's the point of that?

I'm probably missing something big here, but all the pages I've look at don't really explain this. It just magically repeats selection, expansion, simulation, and back-propagation, until it constructs a nice tree at the end. How?

**EDIT:** I figured it usually creates only one child node because of this taken of this source:

> In its simplest and most memory efficient implementation, MCTS will add one child node per iteration.

Also, even if you create just two or three, would that really be enough to cover all the possible moves, especially if the branching factor is large? How would one determine how many child nodes to create?

# Answer
It sounds like you're reading a summary/overview. You might be reading too much into one sentence there. The sentence says "MCTS will add one child node per iteration". That doesn't mean each node will have only one child after the process finishes. You might have one iteration that adds one child of X, and a later iteration that adds another child of X, and an even later iteration that adds yet another child of X, and so on.

Similarly, nothing says that MCTS is limited to adding only two or three children per node.
> 0 votes

---
Tags: algorithms, search-algorithms, trees, randomized-algorithms, monte-carlo
---


# Question
Title: NL and NP compute different binary relations, so what?
Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input string.

It is easy to see that the nondeterministic transducers using polynomial time can compute different binary relations than the nondeterministic transducers using logarithmic space. (Trivial examples like $\\{(1^n,ww^R):n\in\mathbb N, |w|\leq n\\}$ suffice to see this. **Edit:** This assumes that the output is generated symbol by symbol, see András Salamon's comment. If random access to write only output memory is assumed, then $\\{(1^n,w):n\in\mathbb N, w\in D\_2, |w|\leq 2n\\}$ where $D\_2$ is the Dyck language of all strings of matching brackets over two pairs of brackets, say $\\{ \[,\], (,) \\}$ is an example. However, proving that this example really works is non-trivial.)

Can anything of interest be concluded from this basic observation? For example, concluding that there must exist an oracle $A$ such that $NL^A \neq NP^A$ would be of interest, but things don't work that way. Or concluding that directly programming in NP is easier that directly programming in NL, because more powerful *subroutines* are available. That sort of sounds true, even so *subroutines* generally can have more that a single input string and produce more than a single output string. (So one could try to prove that if all those possible subroutines would be equal, then there could not exist an oracle for which the relativized decision problems are different. But even this will probably fail.)

---

**Edit:**

* WLOG, we can restrict us to NL tranducers that never repeat a configuration. These are exactly those NL transducers that only use polynomial time.
* The random access to write only output memory is well outside NL. But it is still inside NP, so the composition of those NL transducers could be done inside NP. This should be good enough to conclude things about powerful *subroutines* or oracles, if this is possible at all. (Even the symbol by symbol output tape was outside of NL, it was just less obvious.)
* The oracles $A$ such that $NL^A \neq NP^A$ are white box oracles, where the problem $A$ is (expected to be) outside of the considered complexity classes. The conclusions about *subroutines* from the basic observation might tell us something about black box oracles from the same or weaker complexity classes. Or they might at least provide a motivation to prove black box separations between complexity classes relative to oracles from weaker complexity classes.

# Answer
We know that $NL \subseteq NP$, but that $NL \subsetneq NP$ is not known. So one cannot outright say that $NL$ and $NP$ are different.

We only know for sure $NL \subsetneq PSPACE \subsetneq EXPSPACE$ by space hierarchy theorem. And $P \subsetneq EXPTIME$,and $NP \subseteq NEXPTIME$ by time hierarchy theorem.

We only know for sure is $$L\subseteq NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE =NPSAPCE \subseteq EXPTIME \subseteq NEXPTIME\subseteq EXPSPACE$$

Only above four inclusions are known to be strict. All the other inclusions are unknown and open problems. (Though most but not all have unproven belief that each of them is strict).

See https://en.wikipedia.org/wiki/PSPACE#Relation\_among\_other\_classes.

Also, I think, we might be able to prove that there exists a language $B$ for which $NL^B \neq NP^B$. Probably $U\_B$ and $B$ of Baker, Gill and Soloway will work here too. And we are also able to show that $NL^A = NP^A$ for $A = TQBF$, the $PSPACE$ complete problem to decide the true quantified Boolean formulas.
> 1 votes

---
Tags: complexity-theory, nondeterminism, relational-algebra, transducers
---


# Question
Title: How convert instances of a language efficiently into 3SAT instances?
The following question is from Sanjeev Arora and Boaz Barak ( not homework )

> Show that for every time constructible $T:N \to N$, if $L \in NTIME(T(n))$ then we can give a polynomial-time Karp reduction from $L$ to $3SAT$ that transforms instances of size $n$ into 3CNF formulae of size $O(T(n)logT(n))$. Can you make this reduction also run in $O(T(n)logT(n))$?

The best I could come up with is a $O(T(n)^3)$ formula. We take each configuration to be of at most length $T(n)$ and the machine runs for $T(n)$ steps. So we have a grid of $T(n)$ rows each with $T(n)$ columns. Each row represents a configuration. We just impose the condition that each row follows from the previous by using $M's$ ( where $M$ is a machine deciding $L$ in $O(T(n))$ time ) transition function in at most one step. The first row should represents start configuration and last row represents the accept configuration. Thus an $O(T(n)^3)$ formula is formed by this approach.
How can I do better ?

# Answer
> 2 votes
The idea is to reduce an instance $x$ to $\phi$ that uses only $O(T(n))$ symbols and clauses. $\log T(n)$ will be the length of binary representation of each symbol. This is the upper limit that you cannot cross if you want to solve the problem. So, you will have to optimize quite a bit. See the oblivious TM and state representation in Arora and Barak to get an idea.

---
Tags: complexity-theory, nondeterminism
---


# Question
Title: Convolutional Neural Network Feature Engineering?
I'm working through the tensorflow tutorial, and I see how you go from 28 x 28 to zero-padding and applying a 5x5x32 convolution to get 28x28x32 and max-pooling etc. What I'm confused about is the 32 outputs seem to be described as filters acting upon the 5x5 layers. The description is typically something like these are equivalent to filters being used to feature engineer, but when you set up the network you don't define any filters. So how do the filters come about?

I read this question as well Intuition for convolution in image processing and although it's informative, it doesn't describe how the filters come about.

This is the tutorial, you can see the description of the layers in the first and second convolutional layers: https://www.tensorflow.org/versions/r0.7/tutorials/mnist/pros/index.html

# Answer
Your questions phrasing is a bit confusing. I'll try to answer my interpretation of your confusion.

I think the base of your confusion relays on the assumption that 2D convolution receives a 2 dimensional array as input. This is not true - The input of a 2D convolution layer is a 3 dimensional array. At the beginning you have an image which can be greyscale/RGB, let's consider an RGB image of 28x28, this image is represented as a tensor of 3x28x28 (greyscale will be 1x28x28), generally - colors x width x height as the colors can exceed 3 for opacity etc. A 2D convolutional layer with patch size 5x5 will be a applied over each patch of size 5x5 of the images over all colors. To sum it up, slice the image to cubes of patch size (which overlap according to the stride parameter) each of these patch is taken with all it's colors as the input to the filter.

The process I've described above is the application of a single filter over the input. The result of "running" the filter over the input is a matrix (as the dot product of each patch of the image with the filter is a scalar). Now, take 32 such filters stacked on top of the other, the output will be 32 matrices where each matrix is the application of a different filter over the input.

As far as dimensions go, let's assume you apply 5x5x32 over a 1x28x28 image (without padding & stride=1) you'll have: $\frac{input\ size-patch\ size}{stride}+1$, where I assumed everything is symmetrical for both axises. So you have output of $\frac{28-5}{1}+1=24$, which means the second layer is of size 32x24x24.

You can either think of the second layer as an "image" of size 24x24 with 32 "colors" which is weird but some people do it, or you can think about everything in terms of 3 dimensional arrays and understand exactly how a filter is applied over each 3 dimensional array.

Why is this referred to as filters?

Let's consider the case where you apply a 2D convolutional layer with parameters 5x5x1. What does this layer actually do? How does it look? (consider the case where your images are greyscale for simplicity), The layer is actually a dot product of each patch of size 5x5 with a 2D weight matrix of size 5x5. Organized to form a 2 dimensional array of results (which is the output layer). The 5x5 weights matrix is called "filter". You can think of it as a gaussian for a moment, the 5x5 weight matrix is applied over each patch of the image thus blurring the image. This is applying a gaussian filter over the image. Now instead of a gaussian filter, you learn the weights and have a general filter. Now consider a layer of 5x5x32, it is the same, but with 32 different filters.
> 4 votes

---
Tags: neural-networks, features
---


title: Writing context free grammar

text:
# Question
Title: Writing context free grammar
I have the following language:

{0m1n0n1m | m,n ≠ 0}

I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each other, so could we treat them in a case as the same?

So could something like

S --\> 0S1S0S1S

or

S --\> 0101 | 0S10S1 | ε

# Answer
> 0 votes
For simpler language $\\{1^n0^n\ | \ n \> 0\\}$, we can write grammar as $S \rightarrow 1S0\ |\ 10$.

Now we can replace the non-terminal $S$ by $A$. And write context free grammar for the language in the question. $A$ is in the center of $0^m$ and $1^m$. Also remember $m,n \> 0$.

$A \rightarrow 1A0 \ | \ 10$
$S \rightarrow 0S1 \ | \ 0A1$

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Deterministic vs. Non-Deterministic PDA?
The following is an example of language $a^nb^n$ where $n \geq 1$

From what I have heard that in *finite state machines* if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, the definition was: "If a PDA has more than one paths going accept state then it is non-deterministic PDA" but what about epsilons?

So, Is this an example of Non-deterministic or Deterministic PDA? How to recognize NPDAs from DPDAs? Can I create both NPDA and DPDA for this language as above?

# Answer
> 6 votes
Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.

Your example is deterministic. Check:

* From state $q\_0$ with $Z\_0$ on the stack, on reading $a$ there is one possibility. In the same case there is no alternative on input $\epsilon$
* Similarly, from $q\_0$ with stack $a$, only one option. No $\epsilon$ alternative
* In $q\_0$, with $a$ on the stack and inputs $a$ and $b$, again one move only. No $\epsilon$ alternative

You can complete the analysis for the other possible combinations of state, stack symbol, an possible input, making sure there is one option for a given input symbol, and if $\epsilon$ input is allowed, no "real" symbol alternative is available (e.g. in $q\_1$ with $Z\_0$ on the stack, only $\epsilon$ can be read).

---
Tags: automata, pushdown-automata, nondeterminism
---


# Question
Title: Why do black-box deep learning algorithms produce better word similarities than cognitively plausible ones?
Why do black-box deep learning algorithms (e.g. Mikolov et al 2013) produce better word similarities than cognitively plausible ones (e.g. Baayen et al 2011)? Could we combine the best of both worlds, biologically motivated learning mechanisms and state-of-the-art performance?

# Answer
> 2 votes
The short answer is that we don't know *why* current ML algorithms work well on a particular dataset, or *why* other ML algorithms don't.

Most researchers focus on finding ML algorithms that achieve high accuracy, regardless of how they achieve it. Cognitive plausibility typically isn't a goal.

Generally, across much of computer science, our best methods often differ from how the brain works. This is true for machine learning, for computer vision, for playing games like chess, and other tasks. That could be viewed as an opportunity for improvement and a failure of our methods, or as an indication that the methods that will work best for computers might be different from the ones that our brains have evolved. We just don't know.

---
Tags: algorithms
---


# Question
Title: Total number of calls during insertion into binary tree
The problem:

Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree level-by-level. Leave your answer in the form of a sum.

code for INSERT function:

```
procedure INSERT(x: elementtype; var A: SET);
begin
    if A = nil then begin
       A -> .element := x;
       A ->.leftchild := nil;
       A ->.rightchild := nil;
    end;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then
        INSERT(x, A ->.rightchild);
    end;
end;

```

The main confusion for me here is with leaving my answer in the form of a sum. I'm not all that great at sums (haven't taken Calc 2 yet), so I don't really know how to set them up or extract information from them all that well. Any help here would be greatly appreciated.

For clarity: This is a review problem where the answer is:

Let $2^k \leq n \leq 2^{k+1}$. Then $k = \log n$ and the number of calls equals,

$$ \sum\_{i = 0}^{k - 1} (i + 1)2^i + (k + 1)(n - 2^k + 1) $$

I'd like to know the process behind getting this answer. Thank you.

# Answer
The key observation here is that the input is assumed to be such that all insertions fill level 0 (the root level), then completely fill level 1, then completely fill level 2, and so on.

In filling level $i$ we will have constructed $2^i$ new nodes, each of which will require $i+1$ calls to INSERT, so the total cost to fill level $i$ will be $(i+1)2^i$. Thus, the cost to fill levels $0, 1,\dotsc, k-1$ will be $$ \sum\_{i=0}^{k-1}(i+1)2^i $$ Now let's say we're finishing by filling level $k$ partially or fully. We're then inserting elements $n=2^k,2^k+1,2^k+2, \dotsc, 2^{k+1}-1$. Each of those will cost $k+1$ calls to INSERT, so for $n$ elements we will have used $n-2^k+1$ insertions, each of cost $k+1$ for a total of $(k+1)(n-2^k+1)$ calls. That must be added to the cost of filling the upper rows, so you get a total cost of inserting $n$ elements level-by-level equal to $$ \left(\sum\_{i=0}^{k-1}(i+1)2^i\right) + (k+1)(n-2^k+1) $$
> 1 votes

---
Tags: trees, binary-trees, sets, binary-search
---


# Question
Title: Which is the proper algorithm to figure repeated substrings of longest total length?
Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length of $T$, times the number of times that $T$ occurs in $S$ without overlap.

I need an algorithm that does the following:

Given a string $S$, find the substring $T$ whose value is maximal, out of all substrings of length at least two; the index of each location where $T$ appears in $S$; and the value of $T$ (the total number of characters across all of those occurrences of $T$).

You can assume the string $S$ is ANSI encoded, where each character is one byte.

Example:

```
String => "AOOISDF000923RJJASPDFIJJ1023ASPD499FJJDSJIK"

Has the following repetitions:
1 - "DF", two times, total characters (4)
2 - "23", two times, total characters (4)
3 - "JJ", three times, total characters (6)
...
N - "ASPD", two times, total characters (8)

```

The desired output would be ASPD, because it has produced the largest total amount of characters (8).

Is there an efficient algorithm for this problem? Is there a search term or name for this that I could use to search for it, or papers in the literature that describe techniques for this problem?

# Answer
> 2 votes
You might want to check out the literature on the longest repeated substring problem, which is closely related but is trying to optimize a different metric. There are many algorithms and techniques; it's possible some of them could be adjusted to apply to your problem.

For instance, one can find the optimum solution to your problem in $O(nr)$ time using Rabin-Karp's method, where $r$ is the length of the longest repeated substring in $S$. First, we compute $r$ using any standard method. Then, for each $i$ in the range $1,2,\dots,r$, we look for the substring $T$ of length $i$ that is repeated the most number of times (without counting overlaps). This can be done in $O(n)$ time for a fixed value of $i$, by using a rolling hash to compute the hash of all length-$i$ substrings of $S$ and for each such length-$i$ substring, compute the number of times it is repeated (without counting overlaps). This can be done using a hashtable and a greedy algorithm (each time you see a substring $T$, if it doesn't overlap with the last accepted occurrence of $T$, increment the count for $T$ and accept this occurrence, otherwise reject it).

For many distributions on input strings, $r$ is relatively small compared to $n$: e.g., $r = O(\lg n)$. If that applies to your situation, then this Rabin-Karp-based method will be easy to implement and perform reasonably well.

You could also look at suffix trees or suffix arrays. Each internal node in the suffix tree represents a candidate for the substring (a substring that occurs more than once in $S$). However, it's not quite clear to me at the moment how to efficiently account for overlap according to your problem statement, so I don't have a specific algorithm to suggest.

# Answer
> 1 votes
You describe the first step of the "greedy off-line textual substitution" described in

* Alberto Apostolico, Stefano Lonardi: Off-Line Compression by Greedy Textual Substitution. Proc. IEEE, vol. 88 no. 11, pp. 1733-1744, Nov. 2000
* Alberto Apostolico, Stefano Lonardi: Some Theory and Practice of Greedy Off-Line Textual Substitution. Data Compression Conference 1998:119-128
* Alberto Apostolico, Stefano Lonardi: Compression of Biological Sequences by Greedy Off-Line Textual Substitution. Data Compression Conference 2000:143-152

---
Tags: algorithms, optimization, strings, substrings
---


# Question
Title: What is a visual bag of words and how is it implemented?
I'm currently working on implementing a bag of visual words in Python. I get the general gist of how it works but I can't seem to find any sources that explain it in more detail to a level where I can implement it. I'm guessing scikit learn and scikit image would come in but I can't seem to point myself in the right direction. Any help?

# Answer
> 3 votes
This is the original paper:

Gabriella Csurka, Christopher R. Dance, Lixin Fan, Jutta Willamowski, and Cédric Bray. Visual Categorization with Bag of Keypoints. Workshop on Statistical Learning in Computer Vision, ECCV, 2004.

---
Tags: image-processing, classification
---


# Question
Title: Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?
One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 in CLRS 3rd edition page 122 where by acting randomly we manage to impose a distribution on our inputs).

With Simple Uniform Hashing (SUHA) we have that the hash function "evenly distributes" the keys in a random fashion across the hash table. This way the average length of a chain is not too long. Is the randomness that we assume inherently exists in this magic hash function the way we battle worst-case inputs? i.e., is this exactly how we ensure that the expected runtime will be small, since our hash function is random and no series of keys is bad? (i.e., a worst case input doesn't exist because the hash function will act randomly and hence, make the expected chain lengths small).

I am not sure if this is right or if this is the right way to think about it, but that's how I think of hash tables, that they are random so no chain can get too long (usually) and hence we perform well.

# Answer
Yes, your understanding is correct. That's exactly the role the hash function plays.

A pair of keys $x,y$ might collide with one hash function, but not with another. For any fixed set of keys, the expected number of collisions is small. Moreover, for any fixed set of keys, the probability of having a large number of collisions is very small. That's why we can say that the average-case running time is good, and why there's only a tiny probability that the running time is high.

To put it another way: Since the adversary doesn't know what hash function we will be using, he can't craft inputs (a set of keys) that will trigger worst-case behavior. The randomization ensures we only need to worry about average-case behavior (the adversary has no way to force us into the kind of situation that would trigger worst-case behavior). And, hash tables have excellent average-case running time.
> 1 votes

---
Tags: data-structures, randomized-algorithms, hash, hash-tables
---


# Question
Title: On graph isomorphism over exponential word sizes
Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes?

(Shamir's poly time Integer Factoring algorithm is over exponential word sizes).

# Answer
> 3 votes
Yes, this is known. It has been shown that if you allow unlimited word sizes, then programs in the RAM model can compute arbitrary #PSPACE problems in polynomial time. #PSPACE is a huge complexity class: it includes all of PSPACE and NP, and in particular, it includes graph isomorphism (and factoring). Therefore, yes, graph isomorphism can be done in polynomial time if you allow unbounded word sizes.

This result was shown in the following research paper:

Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini. A characterization of the class of functions computable in polynomial time on Random Access Machines. STOC 1981. https://dl.acm.org/citation.cfm?doid=800076.802470

The transdichotomous model was invented to eliminate this anomaly.

---
Tags: complexity-theory, time-complexity, space-complexity, polynomial-time, graph-isomorphism
---


# Question
Title: Can you form a group with assembly instructions under the MIPS-32 architecture?
Would it be possible to form such a group using the `ADD` instruction and the `NOT` instruction?

# Answer
Sure. The integers modulo $2^{32}$ form a group. The group operation is addition modulo $2^{32}$, which can be implemented by the ADD instruction. You don't need the NOT instruction.

There are other groups you could form, such as the integers modulo 2, and many more. I recommend you read the definition of a group and play around with some examples.
> 3 votes

---
Tags: group-theory
---


title: How to solve T(n) = T(n-1) + n^2?

text:
# Question
Title: How to solve T(n) = T(n-1) + n^2?
See title. I'm trying to apply the method from this question. What I have so far is this, but I don't know how to proceed from here on:

T(n) = T(n-1) + n2

T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 - 2n + 1

T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 - 4n + 4

T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 - 6n + 9

Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives:

T(n) = T(n-2) + 2n2 - 2n + 1

T(n) = T(n-3) + 3n2 - 6n + 5

T(n) = T(n-4) + 4n2 - 12n + 14

Now I have to find a pattern but I don't really know how to do that. What I got is:

T(n) = T(n-k) + kn2 - ...???

# Answer
Don't expand the squared terms; it'll just add confusion. Think of the recurrence as $$ T(\fbox{foo}) = T(\fbox{foo}-1)+\fbox{foo}\\;^2 $$ where you can replace *foo* with anything you like. Then from $$ T(n)=T(n-1)+n^2 $$ you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding $$ T(n) = \[T(n-2) + (n-1)^2\]+n^2 = T(n-2)+(n-1)^2+n^2 $$ and similarly $$\begin{align} T(n) &= T(n-2)+(n-1)^2+n^2\\ &= T(n-3)+(n-2)^2+(n-1)^2+n^2\\ &= T(n-4)+(n-3)^2+(n-2)^2+(n-1)^2+n^2 \end{align}$$ and in general you'll have $$ T(n) = T(n-k)+(n-k+1)^2+(n-k+2)^2+\dotsm+(n-1)^2+n^2 $$ Now if we let $k=n$ we'll have $$ T(n) = T(0)+1^2+2^2+3^2+\dotsm+n^2 $$ Now if you just need an upper bound for $T(n)$ observe that $$ 1^2+2^2+3^2+\dotsm+n^2\le \underbrace{n^2+n^2+n^2+\dotsm+n^2}\_n=n^3 $$ so we conclude that $T(n)=O(n^3)$, in asymptotic notation.

For a more exact estimate, you can look up the equation for the sum of squares: $$ 1^2+2^2+\dotsm+n^2=\frac{n(n+1)(2n+1)}{6} $$ so $$ T(n)=T(0)+\frac{n(n+1)(2n+1)}{6} $$
> 15 votes

# Answer
Just start with:

$\begin{align} T(k) - T(k - 1) &= k^2 \\ \sum\_{1 \le k \le n} (T(k) - T(k - 1)) &= \sum\_{1 \le k \le n} k^2 \\ T(n) - T(0) &= \frac{n (n + 1) (2 n + 1)}{6} \end{align}$

by telescoping (see also square piramidal numbers).
> 6 votes

---
Tags: recurrence-relation
---


# Question
Title: How can I check constraints on my state machine behaviour?
My background is fairly practical rather than theoretical, so this question may be a bit basic.

I have a state machine with events, and events may optionally trigger action functions to be called as part of the state transition. In practice, actions functions do things like lighting LEDs. The state machine is defined in an in-house domain-specific language, and a tool generates C code from the definition.

I have constraints that need to be satisfied -- eg "when in state A, only LED 1 and 5 should be lit."

What practical techniques are there to check that my state machine design satisfies my constraints?

I considered using Prolog. If I could enter the side-effects of my action functions, the state machine states, and the valid transitions and action functions, I should be able to query whether the constraints hold true -- is this correct?

Are there other frameworks or tools that could be useful in this situation?

# Answer
> 5 votes
Use a model checker. This is exactly what they're good for. You might look at SPIN and NuSMV as a starting point, but there are many others as well.

---
Tags: programming-languages, proof-techniques, automated-theorem-proving
---


# Question
Title: Without primes in $P$ does integer factorization lie in $coNP$?
In integer factorization we ask 'Given $N$ is there a $a\in\[2,\sqrt{N}+1\]$ such that $a|N$?'.

Is the above problem in coNP because we know primes is in $P$?

That is there is no such factor $a$ of $N$ iff $N$ is prime and we have AKS certificate.

So was it not known prior to 2004 that integer factoring was in coNP?

# Answer
> 3 votes
First of all, you're misstating integer factorization: your version is completely equivalent to primality.

Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.

# Answer
> 1 votes
Without primes in P does integer factorization lie in coNP?  Yes.

So was it not known prior to 2004 that integer factoring was in coNP?  No.

---
Tags: factoring, co-np
---


# Question
Title: 3-partition problem: why $b/4 < x_i < b/2$?
Why does the definition of the 3-partition problem contain the condition $$\frac{B}{4}\<x\_i\<\frac{B}{2}?$$

I don't understand why leaving out this condition changes the 3-partition problem.

# Answer
The 3-PARTITION problem is NP-complete even without this condition. It is a stronger result that 3-PARTITION is NP-complete even with this condition. The condition presumably comes from the reduction used to prove that 3-PARTITION is NP-hard.

The fact that 3-PARTITION is NP-complete even when all integers are bounded in $(B/4,B/2)$ can be helpful when using 3-PARTITION to prove that other problems are NP-hard.
> 2 votes

---
Tags: complexity-theory, partition-problem
---


# Question
Title: Check if a tree is formed by 3 subtrees with given number of nodes
I have run into a contest problem (ACM like) that sounds like this:

*Input:* a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$
*Question:* Can the tree be partitioned into three trees of $X,Y,Z$ nodes by removing only two edges?

I am promised that $N \le 10^5$. My code must finish within 200ms.

The brute-force method of generating all possible partitions of X, all possible partitions of Y, and all possible partitions of Z and checking if they form the tree is too slow. This got me thinking about dynamic programming. The only thing I see here to help me form a DP algorithm is counting how many children does a node have (treating the current node as a root of a tree). However, checking between the nodes themselves for X, Y, Z would still take $O(N^3)$ time, which is too much.

So do you see any other algorithm for this task?

Example: We're given a tree of 8 nodes and X = 3, Y = 3, Z = 2 and the following edges: 2-3; 4-2; 2-1; 1-5; 1-8; 5-6; 5-7. The answer is yes because you can delete edges 1-2 and 1-5 to form 3 partitions like this {1,8} (Z) and {2,3,4}/{5,6,7} (X/Y).

This problem is from a preparation stage of a local competition that happend a while back.

# Answer
Let's root the tree arbitrarily at node $r$. Now with a DFS, compute the size of each subtree rooted at each node $v$. Let $good(u,i)$ be true, if there is some subtree rooted at $v$ where $v$ lies in the subtree rooted at node $u$ such that the size of the subtree rooted at $v$ is exactly $i$. We will maintain this property for only three values of $i \in \\{X,Y,Z\\}$. This can be done in the same DFS itself (which is left as an exercise for you).

Since we have rooted the node at $r$, due to the DFS traversal from $r$, all nodes except $r$ have a parent which we will denote by $p(u)$ for a node $u$. Now let's compute the same function $good'(u,i)$ for the same 3 values of $i$ but instead for the subtree which is obtained after deleting the subtree rooted at node $u$. This value can be computed via a second DFS (which I also leave as an exercise for you).

> **HINT**: Read up on how to find the longest and second longest paths starting at some node in a unrooted tree for each node.

Now the answer to the question is "Yes" if $\exists\ u \in$ tree $T$ such that $good(u,i)$ is true and $good'(u,j)$ is true and $i \not= j$

Since we have only two DFS traversals, the time complexity is $\mathcal{O}(n)$ and a constant amount of memory per node implies $\mathcal{O}(n)$ memory as well.
> 1 votes

---
Tags: algorithms, trees, dynamic-programming
---


title: Proof that MAX CLIQUE is NP-Hard

text:
# Question
Title: Proof that MAX CLIQUE is NP-Hard
My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD?

**Remarks:**

MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k\>0$. Does the graph $G$ contain a maximum clique of size $k$?

I have been looking for a formal proof that MAX CLIQUE is **NP-Hard**, still I haven't found one. The book of Computers and Intractability (Michael Garey) in the final chapters mentions briefly that the full proof is on the phd thesis of Ernet Legget: http://dl.acm.org/citation.cfm?id=907661 . I couldn't find the copy of the book on the internet nor any survey whit the proof.

# Answer
There is probably a proof in Karp's original paper. Here is a simple reduction from SAT. Given an instance $\varphi$ of SAT with $m$ clauses, construct an instance of MAX-CLIQUE as follows. For each clause $C$ and each literal $\ell$ appearing in $C$, there is a vertex $(C,\ell)$. Two vertices $(C\_1,\ell\_1),(C\_2,\ell\_2)$ are connected if $C\_1 \neq C\_2$ and $\ell\_1 \neq \lnot \ell\_2$. This has a clique of size $m$ iff $\varphi$ is satisfiable (exercise).
> 4 votes

# Answer
The standard reduction from SATISFIABILITY to CLIQUE is outlined in Karp's classic paper, see page 97.
> 2 votes

---
Tags: complexity-theory, np-hard, decision-problem, np
---


title: Typing dependent pattern matching

text:
# Question
Title: Typing dependent pattern matching
I'm curious on how to type a **dependent** pattern matching in a functional language. What should the rule for typing

```
match e with
| C_1 a_1_1 a_1_2 ... a_1_n1 -> e_1
| C_2 a_2_1 a_2_2 ... a_2_n1 -> e_2
| ...
| C_m a_m_1 a_m_2 ... a_m_nm -> e_m
end

```

be, where e is of type T, which has constructors C\_i for each i.

I think that to prove that the pattern match has a type T', we need to prove that each e\_i has type T' under specific assumptions, but I can't quite pinpoint those assumption to add into the context.

# Answer
In general matching with dependent types can be quite subtle! You'll note that in the Coq documentation that the *extended* pattern-matching syntax is

```
match t as x in T1 return T2 with
    | C1 a1 ... an
    ...

```

In particular, ommiting any of the `as`, `in` or `return` clauses can prevent type inference of the statement.

Intuitively, if the type of (say) constructor $C\_1$ is $$ \Pi(x\_1:A\_1)\ldots(x\_k:A\_k).I\ \vec{p}$$ and the type of the matched term $t$ is $$ I\ \vec{v}$$ then you get the *constraint* $$ \vec{p}\[\vec{a}/\vec{x}\]\simeq \vec{v}$$ which may lead to an undecidable problem, as explained in Goguen *et al*.

Then all you need is for each right hand side to correspond to the appropriate instance of the return type. This return type may depend on $t$, so the `return` clause specifies the pattern of the return type as a function of $x$ (which represents $t$ through the `as` clause).

More formally, each $e\_i$ must have type:

$$ T\_2\[C\_i\ \vec{a}/x\]$$

and the type of the whole match expression is $$ T\_2\[t/x\]$$

More details can be found here.
> 6 votes

---
Tags: type-theory, semantics, dependent-types, inductive-datatypes
---


# Question
Title: Woman optimal Gale Shapley Stable Matching
I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can have. I was thinking is it possible to have a woman optimal solution with a guaranteed stable matching? Let's say each woman has a different man as her most preferred partner. Then can we say that we can ensure stable matching by simply assigning the most preferred man to each woman?

I am having problem understanding that, since by definition the matching is stable if no man or woman prefer another to their current situation. Wouldn't it give as stable matching if each woman has the most preferred man, considering they all unique?

# Answer
> 3 votes
Yes, of course you can switch the roles of men and women in the algorithm and you'll get a woman-optimal solution. It's just convention that we call one side of the graph "men" and the other side "women" but the algorithm itself doesn't care what names we use. We could just as well call them "horse" and "blueberry".

---
Tags: algorithms, matching
---


# Question
Title: Integer Arithmetic Coding misunderstanding of parameters
Given this alphabet $\\{a,b,c\\}$ where $P(a) = 2/5$, $P(b) = 2/5$, $P(c) = 1/5$. Encode this string : $bcba$.

I have to encode this using 5 bits.

I have been looking in the Introduction to Data Compression book, and I can't figure out what my "Total Count" is and neither my $n\_i$.

$F\_x(k) = \frac{\sum\_{i=1}^k n\_i}{TotalCount}$

How do I calculate the (What's k? is the question pretty much):

Cumulative\_Count(k) $= \sum\_{i=1}^k n\_i$

Is my total count = 4? or $2^5$

# Answer
> 0 votes
Presumably $n\_i$ is the number of occurrences of the $i$th symbol, and TotalCount is the total number of occurrences (so $\sum\_{i=1}^m n\_i$, where $m$ is the number of symbols). So $F\_x(k)$ counts the relative fractions of the first $k$ symbols.

To know for sure, you should check your textbook, which surely defines everything somewhere. You might have to read earlier sections or chapters.

---
Tags: information-theory, data-compression
---


title: Question simplifying boolean expression

text:
# Question
Title: Question simplifying boolean expression
This is what I have so far, so I just want to know if I am doing everything right or wrong. I am novice in the topic.

I have been given:

$(A \oplus B) \land \neg A \lor A$

* XOR = $\oplus$

By order of operations regroup:

$(A \oplus B ) \land (\neg A \lor A)$ // XOR

(~A B + A ~B) * ~A + A // Distributive law

(~A ~A B + ~A A ~B) + A // Idempotent Law

~A B + A ~A ~B + A // Inverse Law

~A B + 0 ~B + A

**~A B + A**

Is this statement right?

# Answer
> 1 votes
Note that $\land$ has higher precedence than $\lor$ (see order of precedence@wiki). Therefore,

$$(A \oplus B) \land \lnot A \lor A = ((A \oplus B) \land \lnot A) \lor A = (((\lnot A \land B) \lor (A \land \lnot B)) \land \lnot A) \lor A$$

Then iteratively apply the distributive law and you will get $A \lor B$.

---
Tags: boolean-algebra
---


# Question
Title: Why are Complexity Notations Called Asymptotic?
Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?

# Answer
> 2 votes
There are several answers to this.

1. "Asymptotic" here means "as something tends to infinity". It has indeed nothing to do with curves.
2. There is no such thing as "complexity notation". We denote "complexities" using asymptotic notation, more specifically Landau notataion.
3. "Complexity" is a mostly empty, overused and overloaded term.

However, in the context of algorithms in TCS, it is usally agreed upon that it means "the $\Theta$-class (also "order of growth") of the worst-case running-time cost function" of a given algorithm.

Similarly the "complexity" of a problem means "the best worst-case complexity among all algorithms for this problem".

These can be overridden by adding qualifiers, e.g. "average-case space complexity".

Note that item 3 is my own opinion; some people disagree. You will indeed find "complexity" used for many things in the literature and on this site. In case of doubt or ambiguity, ask the author.

# Answer
> 7 votes
I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes.

> The word asymptotic stems from a Greek root meaning "not falling together". When ancient Greek mathematicians studied conic sections, they considered hyperbolas like the graph of $y = \sqrt{1 + x^2}$ which has the lines $y = x$ and $y = -x$ as "asymptotes". The curve approaches but never quite touches these asymptotes, when $x \to \infty$.
>
> Nowadays we use "asymptotic" in a broader sense to mean *any approximate value that gets closer and closer to the truth, when some parameter approaches a limiting value* \[emphasis added\]. For us, asymptotics means "almost falling together".

---
Tags: complexity-theory, algorithm-analysis, terminology, landau-notation, notation
---


# Question
Title: Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair
What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?

# Answer
Look at it this way.

RMFF- Places Task one after the other until the processor goes beyond the bound

RMNF - Looks at all the processors and see where the task will fit

P-Fair - Uses max utilization of 1 for each processor.

RM can only use N(2^(1/N)-1), this means that both RM will have a different value than P-Fair when utilization is between that value and its upper bound.

As for the RMFF, RMNF just think about it and play with the numbers and you will find answer. Make up task and start placing them according to both methods.

P.S: 2 more hours? Hope it helped.
> 0 votes

---
Tags: runtime-analysis, parallel-computing, scheduling, real-time, multi-tasking
---


# Question
Title: Why is word-addressable the exception, not the rule?
As stated on Wikipedia:

> Most modern computers are byte-addressable

instead of word-addressable. Why is this case? Since the CPU processes words (of predominantly 64 bits or 8 bytes) now, wouldn't the word-addressable approach be more efficient?

# Answer
> 7 votes
Byte operations will always be important because a lot of a modern workload involves bytes. Text processing and bytecode interpretation (including emulation of other CPUs) are obvious examples, but also device drivers often need to be able to manipulate bytes efficiently.

Byte-addressed memory can be emulated with word-addressed memory and a reasonable assortment of bit manipulation instructions, however this means that you need more instructions to do the same thing, and those instructions have long chains of data dependencies between them.

RAM is reasonably cheap, but the instruction pipeline in a modern CPU is not.

Every so often, ISA designers reason that byte and short word load/store instructions aren't that important. Within two revisions, those instructions inevitably get added. This was the case with MIPS and Alpha, for example. Code density, it turns out, is quite important.

Note that this isn't true of arithmetic and logic operations. Given a sufficient number of registers (which, I might add, 32-bit x86 and earlier did *not* have), there doesn't seem to be any gain in implementing byte and short-word arithmetic and logic instructions. Well, for non-vectored instructions, anyway.

# Answer
> 1 votes
In the end, what the CPU does when accessing data in *cache* is irrelevant, memory access is by cache line (i.e., 128 byte blocks for the Pentium 4).

---
Tags: computer-architecture, operating-systems, memory-management, memory-hardware
---


title: How does a register remember value?

text:
# Question
Title: How does a register remember value?
So I am studying this great book, and Chapter $3.1$ is about **registers**.

Quoting from this book / chapter:

> A register is a storage device that can "store" or "remember" a value over time, implementing the classical storage behaviour $out(t) = out(t-1)$.

What is mean by:

> the classical storage behaviour $out(t) = out(t-1)$ ?

If **$out(2) = out(1)$** and **$out(1) = out(0)$** how are we ever going to **store** a value?

# Answer
> 3 votes
Registers can be thought of as collections of flip-flops. These have inputs which, when activated, change the stored value. When not activated, the stored value stays the same. Look at the truth tables in the Wikipedia article.

---
Tags: computer-architecture, memory-hardware, digital-circuits
---


# Question
Title: Is the "Bidirectional Dijkstra" algorithm optimal?
In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g., this, and this. Also there is some software that uses this algorithm (for example this DBMS). But some posts express doubts about the optimality of this algorithm, such this, and this. Which one is correct? Is the bidirectional Dijkstra's algorithm optimal or not?

# Answer
> 4 votes
When we talk about the "bidirectional Dijkstra" algorithm, we actually mean a family of similar algorithms which are implementations of a more abstract idea. All of these algorithms are optimal (produce an optimal solution). Some algorithms may work only under some assumptions on the input, for example only in the unweighted case, which is what the doubtful posts seem to have in mind.

More generally, algorithms usually come with correctness proofs. These proofs show that under certain conditions, the algorithm has certain guarantees. If these conditions don't hold, that the guarantees don't necessarily hold. When using an algorithm, check that the conditions that you know hold indeed imply the guarantees that you are looking for.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How does SARSA handle episode termination
When applied to domains that are episodic and have a "final" state but no final action, like a game, how does SARSA update the Q-values?

e.g. A game agent would receive this series: $$ s\_0,a\_0,r\_0,s\_1,a\_1,r\_1,.....s\_{N-1},a\_{N-1},r\_{N-1},s\_N $$ Based on the traditional definition, which updates the *current* Q-value using the \*future Q-value, shouldn't it be impossible to apply SARSA, since there's no future action to use when plugging in the $(s\_t, a\_t, r\_t, s\_{t+1}, a\_{t+1})$ values?

# Answer
> 1 votes
You can think of the terminal state as a loop for every possible action where you receive zero reward. Once you enter the terminal state, not matter what action you choose, you will receive zero reward.

---
Tags: machine-learning, reinforcement-learning
---


title: Big Omega of a while loop

text:
# Question
Title: Big Omega of a while loop
I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is `Ω(1)`, because it takes at least constant time.

What if let's say I have a while loop `i < n`, then its `O(n)`, but does that mean that its `Ω(1)` or `Ω(sqrt(n))` or something else because we can say that it takes at least constant time? I just don't understand, its straightforward with upper bound, but lower bound confuses me a lot.

I am confused about this code. Can we say that its lower bound time is `Ω(sqrt(n))` or perhaps `Ω(log n)`, because it can do at least as good?

```
i=1
while(i<n)
 i+i
end

```

# Answer
Any code that gets executed takes time $\Omega(1)$. That's the most you can say if you don't know anything more about the code. For example, if all your know is that your loop has the form `while i < n ...`, then it could be that $i = n$, so the loop immediately terminates.

Here are some concrete cases in which we can calculate the complexity:

```
i = 1
while i < n:
  i = i + 1

```

This runs in time $\Theta(n)$.

```
i = 1
while i < n:
  i = i + i

```

This runs in time $\Theta(\log n)$.

```
i = 1
j = 1
while i < n:
  i = i + j
  j = j + 1

```

This runs in time $\Theta(\sqrt{n})$.

See if you can prove all these claims.
> 3 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Monotone property of heuristic in $A^*$ algorithm
In the $A^\*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent.

I was able to understand the admissible property, however, I am not able to wrap my head as how the monotone property guarantees that any node can be explored only once (i.e., the path that lead to that node has the shortest path). As stated in the wiki page ,

> "If the heuristic $h$ satisfies the additional condition $h(x) \le d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In such a case, $A^\*$ can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and $A^\*$ is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$."

# Answer
> 3 votes
## When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) \> d(b,c) + h(c)$.

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

## Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $$d(a,b)+d(b,c) \< d(a,c)$$ is true, we must visit $b$ first. We can add $h(c)$ on both sides without changing anything. $$d(a,b)+d(b,c)+h(c) \< d(a,c)+h(c)$$ If the monotonic constraint is fulfilled, we can replace $d(b,c)+h(c)$ by $h(b)$, since it's less or equal. The equation $$d(a,b)+h(b) \< d(a,c)+h(c)$$ is still true. This also happens to be the test the $A\*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to achive.

---
Tags: algorithms, graphs, shortest-path, heuristics
---