maximizing inner product of vectors in an ellipsoid and a given vector I have been wrestling with this for quite a long time but couldn't convince myself that the following is true:

What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid. Also, $A_{t, a}$ is a matrix that "describes" the shape of the ellipsoid. $\hat{\theta}_{t,a}$ is the red point that is the center of the ellipsoid, and $c_t$ is the "radius" of the ellipsoid.

I cannot show to myself that $\displaystyle\max_{\theta_{a}} x_{t,a}^{T} \theta_{a}$ can be derived into the LHS form: $x_{t,a}^{T} \hat{\theta}_{t,a} + c_t \sqrt{x_{t,a}^{T} A_{t,a}^{-1} x_{t,a}}$

Can anyone show me how this is true?

Thanks!

For more context, you can view it here: http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf

There must be something wrong if you look at the dimensions. Actually the constraint should be
$$(\theta_a-\hat{\theta}_{t,a})^TA_{t,a}(\theta_a-\hat{\theta}_{t,a})\leq c_t^2.$$

The inner product takes its maximum on the boundary of the ellipsoid so we can make the constraint a equation. The gradient of Lagrange function has to be zero at the maximum:
$$\left\{\begin{array}{rcl}
x+2\lambda A(\theta-\hat{\theta}) &=&\vec{0} \\
(\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&=&0
\end{array}\right.$$

So
$$x^T(\theta-\hat{\theta})=2\lambda(\theta-\hat{\theta})^TA(\theta-\hat{\theta})=2\lambda c^2,$$
$$x^TA^{-1}x=4\lambda^2(\theta-\hat{\theta})^TAA^{-1}A(\theta-\hat{\theta})=4\lambda^2c^2,$$
which implies $x^T\theta=x^T\hat{\theta}\pm c\sqrt{x^TA^{-1}x}$. Since it's the maximum we take the positive sign here, so we have the LHS you wanted.


Show how to do FFT by hand Say you have two polynomials: $3 + x$ and $2x^2 + 2$.

I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how FFT algorithm would multiply these two polynomials. (Note: there is nothing special about these polynomials, but I wanted to keep it simple to make it easier to follow.)

I've looked at the algorithms in pseudocode, but all of them seem to be have problems (don't specify what the input should be, undefined variables). And surprisingly, I can't find where anyone has actually walked through (by hand) an example of multiplying polynomials using FFT.

Suppose we use fourth roots of unity, which corresponds to substituting $1,i,-1,-i$ for $x$. We also use decimation-in-time rather than decimation-in-frequency in the FFT algorithm. (We also apply a bit-reversal operation seamlessly.)

In order to compute the transform of the first polynomial, we start by writing the coefficients:
$$ 3,1,0,0. $$
The Fourier transform of the even coefficients $3,0$ is $3,3$, and of the odd coefficients $1,0$ is $1,1$. (This transform is just $a,b \mapsto a+b,a-b$.) Therefore the transform of the first polynomial is
$$ 4,3+i,2,3-i. $$
This is obtained using $X_{0,2} = E_0 \pm O_0$, $X_{1,3} = E_1 \mp i O_1$. ( From twiddle factor calculation ).

Let's do the same for the second polynomial. The coefficients are
$$2,0,2,0.$$
The even coefficients $2,2$ transform to $4,0$, and the odd coefficients $0,0$ transform to $0,0$. Therefore the transform of the second polynomial is
$$ 4,0,4,0. $$

We obtain the Fourier transform of the product polynomial by multiplying the two Fourier transforms pointwise:
$$ 16, 0, 8, 0. $$
It remains to compute the inverse Fourier transform. The even coefficients $16,8$ inverse-transform to $12,4$, and the odd coefficients $0,0$ inverse-transform to $0,0$. (The inverse transform is $x,y \mapsto (x+y)/2,(x-y)/2$.) Therefore the transform of the product polynomial is
$$6,2,6,2.$$
This is obtained using $X_{0,2} = (E_0 \pm O_0)/2$, $X_{1,3} = (E_1 \mp i O_1)/2$.
We have obtained the desired answer
$$ (3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3. $$


half precision floating point multiplication A = 0   10011   0011110111

B = 1   00011   0010011000

exponent is 15, mantissa is 10 bits and first bit is implicit. Can somebody please tell me the final answer cause I am having trouble figuring out what is happening with exponent since there are 3 extra zeroes in front of mantissa multiplication. I got that exponent is 7(00111 in binary). Thanks in advance

When multiplying floating points:

we add the (real) exponents, to get the output exponent
we multiply the two mantissas (remember the implied 1), round and shift as necessary.

So the new exponent is $E=(19-15) + (3-15)= -8$.

The multiplication of the mantissas give
$$1.0011110111_2  \times = 1.0010011000_2 = 1.01101100111010101$$

taking only 10 digits (rounding down, see here) we get
$M= 0110110011$.

The sign is a minus.

So the output is
$Out= 1\ 00111\ 0110110011$.

For sanity check, let's convert to decimal and see that it makes sense.

$A = (-1)^0 \times 2^{4} \times 1.2412109_{10} = 19.8593744$

$B = (-1)^1 \times 2^{-12} \times 1.1484375_{10} = -0.0002804 $

Then,

$A\cdot B = -0.0055686$

We can convert $Out$ from above to decimal, and get
$Out = (-1)^1 \times 2^{-8} \times 1.4248047 = -0.0055656$ and the error is $0.000003 \approx 2^{-18}$ which makes sense (since the real exponent is $2^{-8}$ and we have a 10 digit significand)

See also https://oletus.github.io/float16-simulator.js/  for a calculator, and https://en.wikipedia.org/wiki/Half-precision_floating-point_format or https://en.wikipedia.org/wiki/Floating_point for definition and some more explanations.


How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related? I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all going to be tested and yes we have a text (AI - A Modern Approach), but no, we did not cover everything in class).

I "know" a few things about the mathematical descriptions of all of those, but I know pretty much nothing about their usage or practical applications.

Here are my questions (and I apologize for my naivety):

What kind of machine learning algorithm classes do they belong to? Since they all need training, does it mean that they are all supervised learning algorithms?
They all have an underlying structure that allows a graph to represent them, where directed edges denote dependencies between states. The probability of being in a state is computed as a conditional probability from ancestors of the state. Does that sound about right?
In what kind of situation do you want to use which of the algorithms? Is it possible to some it up, or does it require subtle differentiation and expert-level knowledge?
Why do Neural Nets get special treatment? I heard of many classes teaching Neural Nets, but I have heard of no such thing for the other guys.

No, needing training has nothing to do with unsupervised/supervised. Supervised learners need labels, unsupervised learners do not (they do things like clustering, density estimation, dimensionality reduction). In fact you can use all of them for supervised and unsupervised learning, except maybe CRFs, since an unsupervised CRF would more likely be referred to as a markov random field (MRF) since there is no conditional per se. Someone might argue with me on this last point and I probably wouldn't argue back.
No, CRFs have undirected edges. ANNs can have undirected edges also (for example autoencodes with tied weigths). ANNs don't need have a probabilistic interpretation.
Sometimes it would be obvious. For example, if I'm doing Image Denoising I'm not going to use an HMM. Other times it will depend on things like what the practitioner has experience with, what works well in this domain, or a myriad of other factors.
Out of all the thing on your list ANNs are the only one that need not have a probabilistic interpretation. Furthermore, the techniques used for training ANNs normally are of a different flavor than what is used for other methods. That being said there are lots of classes that will focus on other types of models and likely not discuss ANNs, for example Probabilistic Graphical Models, Generalized Linear Models, etc.


Existence of a route following one-way streets I am trying to understand the approach for this problem:

  "If all streets are one way, there is still a legal way to drive from
  one intersection to another"

The question is to prove that it can be done in linear time. I am not looking for direct answers but the approach to this problem.

How can I think about this problem in terms of graph theory? AFAI understand, this will result in a DAG. But then should I choose BFS or DFS and why to prove it? (both are liner time algos)

First, it definitely won't result in a DAG, just a digraph. You need to get from A to B and B to A in order to satisfy your condition for nodes A and B, but that itself is a cycle.

Lots of time BFS and DFS are equivalent in relation to a problem, so it doesn't matter which one you choose. Here, the real trick is not choosing between DFS and BFS, but dealing with the fact that the graph is directed.

If you don't want a direct answer, here's the strategy I would use: first find a representation for the streets in terms of a digraph. What corresponds to edges? What corresponds to nodes?

Then, you need to find a graph algorithm that will work for this problem. What information do BFS and DFS give you about the graph? How can they be adapted to a directed graph?

To give you a little hint, I'd recommend you Google Eulerian chains.


Do exponential functions grow faster than logarithmic? For example:

$f(n) = n(log_2 n)^4$ vs $g(n) = n^{1/3}$

Does f(n) grow slower than g(n) as a general rule, even for decimal exponents? I tried doing a limit test but symbolab limit calculator is saying that Steps are currently not supported for this problem.

I graphed them over a large range and it does appear that g(n) grows asymptotically faster.

I think you may be confused about the definition of Big O - graphing f(n) and g(n) shows f(n) surpassing g(n) at nearly every scale.

O(f(n)) > O(g(n) because g(n) is a fractional power polynomial, which is by definition sublinear (if you linearly plug numbers into a square root, cube root, etc., the rate at which the output increases decreases with each successive computation). g(n) is a "n log star n" polynomial meaning it follows the form of a log to a power multiplied by n. The rate of growth of these types of functions far exceeds fractional polynomials and its not hard to see why - n is a term of the function, so we know its at least linear.

Here's a helpful resource: https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities


Compute relational composition in $O(|E||V|)$ Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs.

Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\mathcal{O}(|E||V|)$.

Case 1: $|E| \le |V|$. Two for loops over $E(X)$ and $E(Y)$: Runtime $ \le \mathcal{O}(|E|^2) \le \mathcal{O}(|E||V|)$.
Case 2: $|V| \le |E|$

Draw the graph $(V(G),E(X) \cup E(Y))$: $(O(|V|)+\mathcal{O}(|2E|)))$. We call edges from $E(X)$ black and from $E(Y)$ red.
Topologically sort it (Kahn: $\mathcal{O}(|V|) + \mathcal{O}(|E|)$). Let the first level be $0$, and edges go from a level to a higher level.
Draw this graph twice.
In the first copy, remove every red edge beginning at even level, and every black edge beginning at odd level: $\mathcal{O}(E)$.
In the second copy, remove every "black even" and "red odd": $\mathcal{O}(E)$.
For the first copy:

for all nodes $u$ on level $2i$
for all nodes $v$ on level $2i+1$
report edge $(u,v)$ (Runtime $\mathcal{O}(V^2) \le \mathcal{O}(EV)$).

For the second copy: The same for "$2i+1$".
Union the reported nodes, throw out duplicates  $\mathcal{O}(V^2) <= \mathcal{O}(EV)$ (I hope the graph representation allows this).

Could some of you please look over my algorithm and check whether

it is correct
it is in $\mathcal{O}(|E||V|)$

If it's correct, does my algorithm already "exist"? If not, could you provide an alternative? I'll accept the first answer, but upvote if some more people are so kind to check.

EDIT: Step 6 Seems to be in $O(E^2)$ sometimes. I wish this would not be true. Has anyone a working algorithm?

Theorem 2.29 on page 60 of Parsing Theory of Sippu and Soisalon-Soininen gives an algorithm for computing (among other operations on relations) the composition of two relations. The algorithm runs in $O(t(|V|+|E|))$ time, where $t$ is the time needed to perform union or assignment operations on sets of vertices. The result of this operation is a set of vertices per vertex representing its neighbors. This algorithm works on arbitrary graphs, not just acyclic ones.


Cases of the Four Color Map Theorem I've been searching for a specific case of the four color map theorem all over the internet, but can't seem to find a reliable explanation.

Does anyone know one or two "cases" of maps as applied to the four color map theorem, including how it could be proved by hand?

The only explanation given on the web is Appel & Haken's computer-based proof, which is not helpful in the sense that the code used in their programs is not available to the public, nor do I understand it completely.

Also, can someone please explain (in depth) what Kempe's chains are and how they work? (maybe also provide an example?)

I am writing a paper for my math class about the four color map theorem, and so far the internet has not been very promising.

Kempe chains are explained in textbooks on graph theory. They appear in the five color theorem, an easy result which is proved using them.

The four color theorem is unfortunately rather complicated. You can try reading a summary of the Robertson et al. proof (including pointers to the computer code they use), Steinberger's simplified proof or Gonthier's account of his group's computer-checked proof.


Completeness of formal definition of 'hardness on the average' While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for simplicity.)

Definition : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if there exists a probabilistic polynomial-time algorithm $G$ such that
for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$
where $X_n := G(1^n)$ is a random variable assigned the output of $G$.

My question is why the statement of the existence of qualified algorithm G is sufficient?
In other words, why the above definition gives a formal definition of 'hardness on the average' instead of following definition, which is more intuitive(?) to understand and more strict.
Why is the above definition sufficient?
( Now I'm thinking that problem might occur when $G$ has only polynomial number of possible outputs, but if so, let's replace 'for any $G$' with 'for any $G$ which have exponentially many possible outputs' in following definition.)

(strong?) Def : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if for any probabilistic polynomial-time algorithm $G$ and for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$
where $X_n := G(1^n)$ is a random variable assigned the output of $G$.

Another question is that whether a following simpler definition is equivalent to original definition or not?

(simple) Def : Hard on the average :
$h:\{0,1\}^*\to \{0,1\}^* $ is hard on the average if for every probabilistic polynomial-time algorithm $A'$ every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,  Pr$[A'(U_n)=h(U_n)]<\frac{1}{p(n)}$
where $U_n$ is a random variable uniformly distributed over $\{0,1\}^n$.

Hard on average is sometimes defined as in your third (simple) definition: a function $h$ is hard on average if on a uniformly random input, its output cannot be predicted by a ppt with more than a negligible probability. The first definition also captures the situation in which the "correct" input distribution is different. For example, consider the function
$$ h(xy) = \begin{cases} H(x) & y = 0, \\ 0 & y \neq 0, \end{cases} $$
where $|x| = |y|$ and $H$ is some hard-on-average function (under the simple definition). The function $h$ is not hard on average under the simple definition, but it's hard on average under the more complicated definition. I'm not sure why we should be interested in such functions, but there's probably a reason. You'll have to continue reading and reflect when the more complicated definition is needed.

As for your second definition, it is far too strong. Consider for example what happens if $G$ always outputs the zero string. You are still capturing something - the halting function will still be hard - but there's no notion of "average". You have indeed anticipated this in your comment (though it only really applies in the non-uniform setting), but the resulting notion is still probably too strong.

The notion of hard on average came out of an attempt to proof the security of some notion. While it is indeed meant to capture some intuitive sense of hardness on average, the details were determined from some argument who used them, from some construction that obtained them; they're not arbitrary. These notions have been found to be useful, which is why they continue being used. Your suggested notion might be helpful as well, but the onus of proof is on you.


Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G? The following problem is from my algorithms class:

  Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff  $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph induced by $C$. A biclique is called maximal if it is not a subset of a larger biclique. Then our problem asks whether there exists a subset of $V$ of size at most $k$ hitting all maximal bicliques of $G$, i.e., can we find $k$ vertices in $V$ such that every maximal bicliques of $G$ cantains at least one vertex of these $k$ vertices. Prove the problem is NP hard.

I'm trying to prove
$$\text{Vertex-Cover} \le_p  \text{This-Problem}$$
but haven't came up with a solution until now. Could anyone help me out here?

Is an independent set a biclique?

After figuring out the first reduction from Vertex Cover (VC) described below, I realised that I had assumed that a biclique has at least one vertex in each part (and thus at least one edge).  But in many ways it makes more sense to consider an independent set (IS) to be a biclique too: it is a complete bipartite subgraph induced by two disjoint vertex subsets $A$ and $B$ -- it just happens that one of the subsets is empty -- so it (vacuously) meets the criteria.  (Similarly, a one-vertex graph is still considered a bipartite graph, and still considered a clique.)  I could not quickly find a "standard" definition to confirm either possibility, so I'll first give a reduction that considers only complete induced bipartite subgraphs with both vertex sets nonempty to be bicliques, and then describe how to modify the construction when independent sets are also considered to be bicliques (which turned out to be much trickier).

I'll call the problem in question "Maximal Biclique Hitting Set" (MBHS).  A biclique that contains at least one edge (i.e., is not an IS) is an "edgy" biclique.

Reduction from Vertex Cover for "edgy" bicliques

The following construction builds a MBHS instance $(G' = (V', E'), k')$ that replaces every edge in the input graph $G = (V, E)$ with a "rectangle" in which the two pairs of diagonally opposite vertices form a 4-vertex maximal biclique.

Add all vertices and edges in $G$ to $G'$.  For every edge $uv$ in $E$, create two new vertices $x_{uv}$ and $y_{uv}$ in $G'$, and the three edges $x_{uv}y_{uv}$, $uy_{uv}$ and $vx_{uv}$.  Set $A_{uv} = \{u, x_{uv}\}$ and $B_{uv} = \{v, y_{uv}\}$ and observe that $(A_{uv}, B_{uv})$ forms a biclique with 2 vertices in each part.

To see that this biclique is maximal, consider any other vertex $z \in V' \setminus \{u, v, x_{uv}, y_{uv}\}$.  To be able to add $z$ to $A_{uv}$ to form a larger biclique $(A_{uv}', B_{uv})$, $z$ must be adjacent to both $v$ and $y_{uv}$ -- but by construction, the only vertices adjacent to $y_{uv}$ are $x_{uv}$ and $u$, and $z$ is not either of those.  Similar reasoning shows that $z$ cannot be added to the other side ($B_{uv}$) either.  Since $z$ was arbitrary, $(A_{uv}, B_{uv})$ must be a maximal biclique.

Finally, set the threshold parameter $k'$ for the MBHS instance to $k$.  This concludes the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k'$.  The VC directly gives a solution to the MBHS instance, since every maximal biclique in $G'$ (both the rectangle bicliques that we created, and any bicliques already present in $G$) contains some edge of $G$, and every edge of $G$ contains at least one vertex in the VC solution.

If there is a solution to the constructed MBHS instance of size at most $k'$, then there is a solution to the original VC instance of size at most $k$.  Assume there is an edge $uv$ in $G$ whose corresponding edge in $G'$ is not covered (i.e., neither of its endpoint vertices is in the MBHS solution), since otherwise we are already done.  Let $(\{u, x_{uv}\}, \{v, y_{uv}\})$ be the unique rectangle maximal biclique that contains $uv$ in $G'$: then it must be that at least one of $x_{uv}$ or $y_{uv}$ is in the MBHS solution, since there is no other way to hit this biclique.  Replace whichever one of these two vertices is in the solution (choose arbitrarily if both are) with either $u$ or $v$ (again, choose arbitrarily) to create a new MBHS solution of the same size (at most $k$) with one more $G$-edge covered.  This can be repeated until every edge in $G$ is covered by a vertex in the MBHS solution, which remains of size at most $k$.  Finally, discard any remaining "rectangle vertices" (vertices not in $V$) from the solution, leaving a VC of size at most $k$.

When independent sets are considered bicliques too

If independent sets are also bicliques, the construction above can fail, most obviously on a graph containing vertices but no edges (which has a single maximal biclique, but an empty VC).

Create $|V|+1$ copies of $G'$ (that is, of the graph constructed for the reduction for edgy maximal bicliques).  Call this new graph $G''$.  The key observation is that in $G''$, there are $|V|+1$ copies of each maximal edgy biclique in $G'$ that all need to be hit separately, but a set of vertices that hits every maximal IS in a single copy of $G'$ suffices to hit every maximal IS in $G''$.  (There are actually vastly more maximal ISes in $G''$ than in $G'$, since to form a maximal IS in $G''$, we may independently choose a maximal IS from each copy of $G'$.  But an IS in $G''$ cannot be maximal unless it includes some $G''$-IS in each copy -- so it suffices to choose a particular copy and hit every maximal IS in that copy.)

Let $k''$ be the threshold parameter that together with $G''$ forms the constructed instance of MBHS.  Set $k'' = k(|V|+1) + |V|$.  Essentially this allows us to spend $k$ vertices hitting edgy maximal bicliques in each of the $|V|+1$ copies of $G'$, plus up to $|V|$ vertices to hit maximal ISes.

That ends the description of the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k''$.  To see this, first replicate the VC solution across all $|V|+1$ copies of $G'$ in $G''$: these vertices hit every edgy maximal biclique for a cost of $k(|V|+1)$.  Now add every remaining vertex from the first copy of $G'$ to the solution, ensuring that we hit every maximal IS in that copy of $G'$, and thus every maximal IS in $G''$ overall, for at most $|V|$ more vertices.  Every maximal biclique is now hit and we have used at most $k(|V|+1) + |V| = k''$ vertices.

If there is a solution to the constructed MBHS instance of size at most $k''$, then there is a solution to the original VC instance of size at most $k$.  By the pigeonhole principle, at least one of the $|V|+1$ copies of $G'$ has at most $k$ vertices in the solution.  These $k$ vertices necessarily hit all edgy maximal bicliques in that copy, since there is no other way to hit these bicliques, and so can be transformed into a solution to the original VC instance of size at most $k$ in the same way as described earlier for the "edgy bicliques" version of the reduction.

Obviously all steps can be carried out in polynomial time, so the MBHS problem is NP-hard.  (It's not clear to me that it is in NP though -- there could be exponentially many maximal ISes (consider a $3n$-vertex graph consisting of $n$ vertex-disjoint triangles), so checking that each one is hit takes too long.  Does anyone have thoughts on a certificate that can be checked in poly-time?)

Bonus material: A failed reduction attempt

My first attempt at dealing with non-edgy bicliques was to add one new vertex $p$ to $G'$, and connect it to every other vertex in $G'$: Now every maximal independent set originally in $G'$ becomes a maximal biclique with $p$ on one side, and intuitively it seems that it would be a good idea to include $p$ in the MBHS solution, as it would hit every such biclique for the cost of just 1 vertex.  The problem is that it could be that every maximal IS in $G'$ is already hit by some vertex in the VC, meaning that it is not actually necessary to include $p$, and that doing so would therefore yield a suboptimal solution.  (This can happen when the given threshold $k$ is loose; in particular, it will always happen for $k=|V|$.  If OTOH $k$ is the minimal threshold for which the answer to the VC problem is YES, then at least one maximal IS misses every vertex in the VC solution, and we would be justified in forcing $p$ into the solution -- but we don't know whether this is the case at the point when we are mapping the VC instance to the MBHS instance, and it is NP-hard to find out!)  The general approach here, of trying to design a gadget that will cause all ISes in $G'$ to become edgy bicliques, can be expressed precisely as: Find a small graph that has an optimal MBHS solution with the additional property that every maximal IS in the graph is hit by some vertex in the solution.  But after trying several examples with 2, 3 or 4 vertices, I wasn't able to come up with such a gadget.


How to traverse a graph in reverse with dfs So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, run dfs on original graph. Then an optimization was given, which was to instead of using the naive implementation of remaking the entire graph with the arcs reversed, you can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

The lecturer made it seems so simple to do this and gave no further explanation. I'm completely stumped on how you can achieve this. Can someone give me some help or point me in the right direction?

Just take the code for DFS and, every time it says "If there is an edge from $x$ to $y$", replace that with "If there is an edge from $y$ to $x$."


The last failure link in KMP automaton I know that in order to build i's failure link, I compare i's and j's success links:
If they are the same (if a = b), then i's failure link should point to state j + 1.
If they aren't the same, we go to the state pointed by j's failure link and do the same. (we stop when we fail at the initial state)
How do you compute the last state's "failure" link? For example if the pattern is "ABA":

How do we compute that after we found a match, we should go to state 1? State 3 doesn't have a character it's expecting to see, so how do we do it?

The link for position $i$ is not determined by the letter at position $i$  but instead by the letter $b$ at position $i-1$ (and the failure link at $i-1$).

For the rest you correctly describe the algorithm: follow the failure links until we find a position $j$ such that the letter at that position equals $b$.

Usually the failure link at the last letter is not computed. The reason is that one does not need it: when we have reached the last position we have found the pattern! However, if we want to find the next match, a failure link at the end would be helpful.


Question about Circuit-SAT NP-Complete Proof I have two questions about the proof that Circuit-SAT is NP-Complete from here (just the first 1.5 pages):
https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture22.pdf

The THEOREM 1 states that the size of $C_n$ is bounded by some polynomial in $n$. Where is this necessary in the proof? It seems like what really matters (coming from the reduction definition) is that we can find $C_n$ in polynomial time. I am not sure where the size comes in.
How would one "hard-wire" $G$ into the circuit in the second paragraph? I understand why it is necessary. However, wouldn't one need to also show that this hard-wiring takes polynomial time as well?

You're right.  All that matters is that the reduction runs in polynomial time.  (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.)
Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1.  If the circuit has polynomial size, this modification takes polynomial time, since you're only modifying at most polynomially much stuff.


Proof that a given language is not context-free Given the language $L = \{w \in \{a,b\}^* \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma.

Assuming $L \in CFL$, would it be possible to start with defining a language $L' := L \cap a^+$ which has to be context-free since $CFL$ is closed under intersection with $REG$.
Now I would have to proof that $L' = \{w \in a^+ \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ isn't regular because the alphabet contains only one symbol.

Let $k$ be the constant of the Pumping lemma and $m > k$ and $m > 42$. So $z = a^{m^2\cdot\sqrt{m^2}} = a^{m^3} \in L'$.

$|z| = |uvw| = m^3 ...$

How to continue?

Use the pumping lemma for CFLs. Let N be the pumping lemma's constant, and take $\sigma = a^{N^{3/2}}$, which certainly has $\lvert \sigma \rvert \ge N$. So we can write $\sigma = v w x y z$ with $\lvert w x y \rvert \le N$ and $w y \ne \epsilon$ such that for all $k \ge 0$ we have $v w^k x y^k z \in L$.

But here only lengths matter. Call $u = \lvert w y \rvert$, so that the length of the pumped string is:

$\begin{align}
\lvert v w^k x y^k z  \rvert = N^{3/2} + (k - 1) u
\end{align}$

where we know that $u \le N$.

Now look for $n$ such that $(n + 1)^{3/2} - n^{3/2} > N$. By the binomial theorem:

$\begin{align}
(n + 1)^{3/2} - n^{3/2}
  &=   n^{3/2} \left( (1 + 1/n)^{3/2} - 1 \right) \\
  &=   n^{3/2} \left( 1 + \frac{3}{2 n} + \dotsb - 1 \right) \\
  &\ge \frac{3 \sqrt{n}}{2} \\
  & > N
\end{align}$

This is $n > 4 N^2 / 9$. This provides a stride larger than $N$ between lengths of strings in the language, the pumped string will fall short.


Every connected graph on more than 3 vertices has two vertices whose removal doesn't disconnect it Prove that every undirected connected graph with $|V| > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected. Describe an efficient algorithm to find two such vertices.

How would I go about solving this?

Prove that every undirected connected graph with |V | > 2 has at least
  two vertices such that if one or both are removed (along with their
  incident edges) the resulting graph is still connected.

If your graph is connected, then you always have a Spanning Tree, now you can reduce the problem to proving that Every Finite Non-Trivial Tree has at Least 2 Leaf Nodes.

  Describe an efficient algorithm to find two such vertices.

A very obvious way would be just to find 2 leaf nodes of your Spanning Tree.


Is the language $(a^n)^mb^n$ context free? $(a^n)^mb^n$  for $m,n\ge 1$
This can be rewritten as $a^{nm}b^n   $
i.e. number of $a$'s is a multiple of number of $b$'s, or for every m $a$'s there is one $b$. I thnk this language can be accepted by NPDA. For every m $a$'s one a can be pushed into the stack, and similarly one can be popped on encountering a $b$. But the NPDA needs to try this for every possible m, where m varies from 1 to maximum string length of $a$'s.

The difficulty of trying every possible $m$ is, in fact, insurmountable. That language is not context-free.

For the sake of contradiction, assume it is context-free. Let $p$ be its pumping length. Consider the word $a^{p^2p}b^{p^2}$. I will let you take it from here.


Worst Case Space Complexity of Merge Sort and Bubble Sort I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(n), linear? All space we need is the exact number of the elements, right? Please enlighten me.

Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part.  This extra space is the reason for the O(n) space complexity.

During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space.

int leftPartition[] = new int[ leftPartitionSize ];
int rightPartition[] = new int[ rightPartitionSize ];

So, merge sort uses auxiliary arrays to sort.  However, quick sort is an in-place sort that uses O(1) space as no auxiliary space is required to sort the data.

Side note:  You might also see the space complexity of merge sort as O(nlog(n)).  Some would argue that because of the way the recursive calls to merge sort work, the space complexly at any given point is at most O(n).  Others might say that adding all the space for all recursive calls requiresO(nlog(n)).  The log(n) is because each repeated call to merge sort cuts the existing array in half.

If you want true O(n) complexity, you can pass an auxiliary array as a parameter into the sort method.  Therefore, each call to merge sort will use the same array without the need to split the array in half with each call.   However, this implementation is quite a bit harder to implement.


Hash functions and pathological data sets So I'm watching an Algorithms course in Coursera, and we are currently discussing hash tables. He's talking about the importance of a good hash function, and about how an ideal hash function would be a "super clever hash function guaranteed to spread every data set evenly".

Then, he explains that the problem is that such a hash function does not exist (and that for every hash function there is a pathological data set), and that the reason for this is as follows:

Fix a hash function $h: U \to \{0, 1, 2, ..., n-1\}$. By the Pigeonhole Principle, there exists a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$. If a data set draws only from these, everything collides.

The bolded part is what's confusing me. Why does there exist a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$? I can't really visualize what he means.

An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ typically has massive size). Since $|U| >> n$, all of the elements of $U$ do not fit into the hash table; therefore, there will be collisions. Consider, for example, the universal set $U=\{a,b,c,d,e,f,g\}$ and a hash table with $n=3$ buckets. Since $|U|=7$, at least one bucket must necessarily contain $\lceil \: |U| \: / \: n \rceil = \lceil 7/3 \rceil = 3$ or more elements. In the case of the most clever hash function (which would spread out the elements of $U$ as evenly as possible), this bucket would contain exactly $3$ elements, like this (highlighted in red):

It is important to see that no matter how clever the hash function is, there will always exist a data set (for example, the set $\{b,g,a\}$) whose elements hash to the same bucket (for example, bucket number $1$). Such a pathological data set will make your hash table degenerate to its worst-case linear-time performance.


NP-COMPLETE:Why say "reduction algorithm computes reduction function"? In Chap 34.3 NP-completeness and reducibility of the  book, Introduction to Algorithm(3rd Edition), the author states(the original text):

We call the function f the reduction function, and a polynomial-time algorithm F that computes f is a reduction algorithm.

In my mind, function should be a machine dependent implementation(a set of instructions) of the algorithm. Why does he say algorithm computes function?

A function is a mapping from elements in the domain to elements in the range. Here is an example of a function: $f(n) = n!$. If you want a machine to compute $f(n)$ given $n$, you need an algorithm, for example: given $n$, multiply together all the numbers from $1$ to $n$. There can be other algorithms for computing $f$. The function exists without reference to a machine. In fact, some functions (such as the halting function) cannot be computed by any algorithm.

You might be confusing the mathematical meaning of the term function with its meaning in programming languages, which is what you describe.


Emulating boolean circuits using addition and multiplication (mod 5) I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates.

Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out I can map the operations like this:

a and b -> a*b (mod 5)
a or b -> 2*(a+b)*(a+b+2) (mod 5)

I was wondering if there was a simpler approach.

For the application I have in mind, a toy example of secure multi party computation using secret sharing, I haven't shown/discovered/figured-out yet if it's safe to re-use private values. If I have to recompute a, b, and a+b two times in order to do an or, costs would be exponential in the length of the circuit. (I'm only using tiny circuits so that's not a big deal, but it would be interesting to know if it was just a non-issue via a clever transformation.)

There are many other solutions. For example, even keeping your True and False, you can have $a\lor b = 1 - (1-a)(1-b) = a+b-ab = a + (1-a)b$ and so on.


Hitting probability of random walk within given number of steps Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.

What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?

We can travel to 4 neighbors.

that is ( i , j+1 ), ( i , j-1 ), ( i-1, j ), ( i+1 , j ) if they are inside the matrix.

If there are only 3 neighbors which are inside the matrix then the probability with which we will go to that neighbor is 1/3(for each of the three).

How to solve this problem?
I am able to find the solution for exactly k steps.

for exactly k steps problem,
I make a matrix, dp[m][n][k+1];
initial all values are zero

except dp[x][y][0]=1;

dp[a][b][q]= weighted average of probablity of neighbours.

for example dp[0][0][4] = 0.5 * dp[1][0][3] + 0.5 * dp[0][1][3];

answer will be dp[i][j][k];

For every point $(a,b)$ and number of steps $t \leq k$, compute inductively (i.e., using dynamic programming) the probability of reaching $(a,b) \neq (x,y)$ in $t$ steps without hitting $(x,y)$. Given this information, you can easily compute the probability of hitting $(x,y)$ in at most $k$ steps.


CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$ I've been struggling to find the grammar to generate the language

$$L = \{a^{2n}b^n : n \text{ is natural}\} \cup \{a^mb^{2m} : m \text{ is natural}\}.$$

I've considered

$$S \to aS|Sb|ab,$$

which works in some cases, but not all (we can derive $a^{k}b$ for example).

What considerations am I not taking into account? There first is the requirement that in a degenerate case we generate $abb$ or $aab$, and there's the consideration that we need to double the number of respective symbols each time.

A promising alternative seems to be

$$S \to aSb|a|b,$$

which balances the left and right sides such that one is always greater than the other by one, but not by a factor of two.

In this case you have the union of two trivially CGF languages and usually that is achived by the following trick. You write some $S_1$ grammar for the first one, $S_2$ grammar for the second one and just "or" them somewhere at the top level (here it's $S$). Your approach was just to use single recurrent literal, if I can say like that, and thus it was difficult to come up with CGF rules.

You would get something like this:

   $S \to S_1 | S_2 $

 $S_1 \to a^2 S_1 b | a^2 b$

 $S_2 \to a S_2 b^2 | a b^2$


What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$? I'm analyzing the computational complexity of an algorithm whose input size is $n$. Finally, I've ended up with
$T(n) = {m^\frac{n-1}{m}}$ where $m$ is a constant. Can one explain the type name corresponding to this computational complexity (e.g., exponential, etc.)?

Since $c=m^{\frac{1}{m}}$ is a constant, your $T(n) = c^{n-1} \in \Theta(c^n)$ is simply exponential.


Find non-overlapping subsets that maximize the sum of their values Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value.

Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?

Yes this problem has already been studied. It is a well-known $NP$-complete problem known as Set-Packing. Your problem is a weighted optimization variation, but the same principles apply.


A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept? First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).
I) Vectors
A vector have a axiomatic meaning, i.e., given a set $\mathcal{A}$ of objects, their objects can be called vectors if and only if they satisfy the vector space axioms $[1]$. Of course that, 3D vectors (little arrows), function, matrices and so on are different objects, but under a well defined vector addition $\boxplus$, and scalar multiplication $\boxdot$ they are the same: Vectors!
Furthermore, I think that is impossible to talk about more complicated objects like Tensors without a vector space structure underlying the mathematical usage of CS objects.
II) My doubt
So, I would like to know: arrays, lists, strings are the same object as vectors? In other words, they satisfy the vector space axioms?
$$* * *$$
$[1]$ https://en.wikipedia.org/wiki/Vector_space#Definition

The objects you mention are not the same.
In particular, lists and (mutable) strings are dynamic data structures whereas arrays are not; their size is fixed.
Now, whether some set of instances of data structures forms a vector space depends on the underlying types, some do, others do not.
Considering e.g. boolean arrays of fixed size $n$ together with the usual addition/scalar multiplication of $\mathbb F_2^n$ yields a vector space, integer arrays of fixed size $n$ do not yield one with the usual operations.


Why is my run time calculation of selection sort different? This is the pseudocode I used:

Their calculation seems to be different from mine. Can someone explain how they derived it? Here is mine in comparison:

Line 1: $c_1 \cdot (n-1)$
Line 2: $c_2 \cdot (n-1)$
Line 3: $c_3 \cdot n $
Lines 5-6: $c_4 \cdot \frac{n(n-1)}{2}$ (the if statement executes with an arithmetic progression)
Line 9: $c_5 \cdot n$

Altogether,
$$T(n) = c_1(n-1) + c_2(n-1) + c_3n + c_4 \frac{n(n-1)}{2} + c_5n,$$
which simplifies to
$$ T(n) = \frac{c_4}{2} n^2 + c_1n + c_2n + c_3n - \frac{c_4}{2} n + c_5n - c_1 - c_2. $$

Both of you get the same result, $\Theta(n^2)$.
Your calculation is more detailed, and takes into account all parts of the code. In contrast, the calculation in the textbook only considers the most significant part of the code (time-wise), and counts the number of iterations rather than the running time.
If I were writing the textbook, I would rephrase this sentence along the following lines:

The running time of selection sort is dominated by the inner loop (5–7), which runs $\frac{n(n-1)}{2}$ times. The total running time is proportional to that, and so it is $\Theta(n^2)$.

There is no need to carry the various constants as you do. The correct way to simplify your original formula is to state that $T(n) = \Theta(n^2)$, since you can't say anything more about the constants $c_1,\ldots,c_5$ anyway.


Find if two numbers are linked by a greatest common divisor Two numbers $x,y$ are 'connected' if $gcd(x,y)>g$. Here $gcd$ is the greatest common divisor. A path exists between two numbers $x,y$ if given $g$ and $n$ there is a sequence of numbers that connect $x$ to $y$ such that all numbers along the path are less than or equal to $n$.
How do you find if there exists a path between two numbers and if this needs to be repeated for multiple pairs of numbers would it be more optimal to first find all existing paths.
I've tried a basic approach of breadth-first search, where each query between two numbers involves calculating $gcd(x,y)>g$. However, this is quite laborious and want to see if there is a more optimal solution.
As a simple example to motivate the problem, let $x=10, y=30, z=18$. Assume $g>4$ and $n=50$. Then $x$ and $z$ are not directly connected but there is a path connecting $x$ to $y$ and from $y$ to $z$.

That's an interesting problem. First of all, calculating directly the gcd between two numbers is clearly the fastest way to decide if they are connected. But as you noticed, quite unefficient for your problem.
A solution is to use prime factorization. Let's denote $P(z)$ the multiset prime factorization of a number $z$. Thus, you note that $gcd(x, y) = P(x) \cap P(y)$.
Once you have the prime factorization $P(x_0)$ of a number $x_0$, you may compute all sub-multisets (there are $2^k$ for $k$ primes values), and if the product $p$ of any sub-multiset is above $g$, any multiple of $p$ lesser than $n$ is connectected to $x_0$. Also note that all these multiples are a clique.
In fact, to generate all the connected numbers, you are only interested by "irreductible" sub-multisets. By irreductible, I mean that removing any (the smallest) prime factor would make the product lesser than $n$. Indeed, a reductible sub-multiset is already a multiple of an irreductible one and would generate no new connection. This may help to prune the loop on all sub-multisets of $x_0$.
Let's take a small example: $n = 100$, $g=10$, $x_0=60$.
$P(x_0) = \{2, 2, 3, 5\}$. The irreductible sub-multisets above $g$ are:

$P(12) = \{2, 2, 3\}$ => generating connections to $12 \times [1, 8]$
$P(15) = \{3, 5\}$ => generating connections to $15 \times [1, 6]$
$P(20) = \{2, 2, 5\}$ => generating connections to $20 \times [1, 5]$

Thus, we may generate the exhaustive list of the numbers conneted to $x_0$: $12, 24, 36, 48, 60, 72, 84, 96, 15, 30, 45, 75, 90, 20, 40, 80, 100$.
Also note that by construction you already have partially the prime factorization of all these numbers.
In your question, it is quite unclear of what may be the limits of ($n$, $g$). Or if your several ($x$, $y$) share the same ($n$, $g$). What I discussed until now is the fastest way I found to explore the graph of connections. But for very high ($n$, $g$), it may be unconvenient to list explicitely all connections of a number. If you do a BFS/DFS, an important point is that there is no point to explore again the clique of an irreductible multiset. In fact, I think I would try to do the BFS/DFS on the graph of these irreductible multiset instead of the graph of the number values.
Also remember that it may exist no path between $x$ and $y$. For example with $g = 20$ and $n = 80$, one may identify some connected components:

$\{31, 62\}$
$\{35, 70\}$
$\{21, 42, 63\}$
$\{25, 50, 75\}$


Can a Turing Machine run for infinitely many steps and halt? Is it possible for an ordinary Turing Machine, for some input x, to run for an infinite number of steps but also halt? Or do we say that Turing Machine does not halt on x?

The answer to your question, whether a Turing machine can run for infinitely many steps and subsequently halt, is negative. If a Turing machine runs for an infinite number of steps and never halts, then it just never halts. It runs forever. A Turing machine halts if it at some step, it halts. If this never happens, then it doesn't halt, and instead runs for infinitely many steps.

One can define infinite time Turing machines for which infinite computations do result in an output, but these are different from the ordinary Turing machines taught in your class. In particular, infinite time Turing machines can "compute" uncomputable functions.


proof of correctness for greedy knapsack algorithm I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement 1 if statement 1 ≥ statement 2 but I don't really know how. Any help on this matter will be really appreciated. Thanks!

Statement 1 and Statement 2 refers to the red highlighted boxes, from the attached picture, tagged as 1 and 2 respectively.

Original source: http://oucsace.cs.ohiou.edu/~razvan/courses/cs4040/lecture15.pdf

Slides are not a substitute for a textbook or careful exposition.  This is especially true when reading a proof.  Slides are intended for presentation in real-time, and as a result often leave out some details.  If there is some aspect you don't understand when reading a set of slides, usually the best thing to do is to find a proper written exposition of the subject -- usually a textbook (but sometimes written lecture notes can be adequate, if written in enough detail).

In this case, on the previous slide, the statement of the theorem mentions "nonincreasing order of $p_i/w_i$", which means that $p_1/w_1 \ge p_2/w_2 \ge \cdots$.  In particular, $p_k/w_k \ge p_i/w_i$ when $k<i$.  The inequality you are referencing then follows.


How would one use "BUT" logic in a ternary logic computer in a practical way? Using three valued logic one can define a multitude of ternary operations.  When dealing with 5:3:1[1] operations, its very easy to see how OR and AND work, but I'm confused as to how ternary BUT is supposed to be useful. As mentioned here in TriINTERCAL's[4] docs the truth table for ternary BUT is as follows:

BUT(True, True) = True
BUT(False, True) = False
BUT(False, False) = False
BUT(True, False) = False
BUT(Unknown, x) = Unknown   for all x

This is a 5:3:1 operation, as out of the 9 possible cases, 1 of those leads to True, 3 lead to False, and 5 to Unknown.

How could such an operation be used in practice (either on single trits[2] or multiple trytes[3])?

The individual who created the Tunguska ternary computer emulator claims that other people found BUT a useful operation coming from TriINTERCAL, even though the author of TriINTERCAL mentions that they don't seem to be useful.

[1]
5:3:1 operations are what you call binary ternary operations where the 9 possible values of the operations are split up like so among True, False, and Unknown, but not necisarily in that order.

[2]
A trit is a ternary bit. A trit holds the value 0,1,2, or False, Unknown, True.

[3]
A tryte is a ternary byte.  Though the value can vary, it is typically 6 trits (3^6 possible values = 729, so more than a byte).

[4]
TriINTERCAL is a programming language based off of INTERCAL that utilizes ternary logic instead of binary.

In the article "The A-Z of Programming Languages: INTERCAL" Naomi Hamilton (Techworld Australia) interviews Don Woods, one of the authors of INTERCAL. More about INTERCAL.

On page 3 of the article the last question is:

  Naomi: "Is there anything else you'd like to add?"

  Don: "... Much of the fun of INTERCAL comes from figuring out how it can be used to do something that would be trivial in other languages. More fun is had by extending the language with weird new features and then figuring out what can be done by creative use of those features."

Apparently the authors of TriINTERCAL took the spirit of the language to heart, yet avoided adding an entirely useless operation.

TriINTERCAL differs from INTERCAL only in the width of the data types (one-spot data types are 10 trits wide and two-spot data types are 20 trits wide), and in the operators available in expressions. "AND" and "OR" are generalizations of the INTERCAL binary versions, "BUT" is new, and "Sharkfin" and "What" are two different interpretations of "XOR" (both of which are available in TriINTERCAL). "Mingle" mingles trits, rather than bits, whereas "Select" ANDs the two original numbers, then sorts all the bits in the first number corresponding to 2's in the second number to the least significant end, 0's in the second number to the most significant end, and 1's in between them.

"AND", "OR", "Mingle", and "Select" operate just like their binary counterparts if no trits with the value 2 are present.

Here are TriINTERCAL's operators (According to Esolang.org):

$$
\begin{array}{cc|cc} \text{AND}\quad\qquad & \& & 0 & 1 & 2 \\
\hline
& 0 & 0 & 0 & 0 \\
& 1 & 0 & 1 & 2 \\
& 2 & 0 & 2 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{OR}\quad\qquad\;\;\; & \lor & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 1 & 2 \\
& 2 & 2 & 2 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{BUT} \quad\qquad & @ & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 0 \\
& 1 & 1 & 1 & 1 \\
& 2 & 0 & 1 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{SHARKFIN} & \land & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 2 & 0 \\
& 2 & 2 & 0 & 1 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{WHAT} \, \qquad & ? & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 2 & 0 & 1 \\
& 2 & 1 & 2 & 0 \\
\end{array}
$$

  Question: "How would one use “BUT” logic in a ternary logic computer in a practical way?"

Taking some liberty with the English language and the meaning of the TRiINTERCAL operators I'll explain it thusly:

The "AND" operator: Max(True), unless one is false.

The "OR" operator: Max(True), unless both are false.

The "BUT" operator: Find the 'middle ground' if allowed; if both sides fully agree then sway that way. Put another way: Always "1" unless one input is "0" or "2", then choose that instead; with "0" overriding "2".

The "SHARKFIN" operator: Addition (Mod 3). Put another way: Add and wrap, never exceeding two.

The "WHAT" operator: If both sides agree it's false, prefer "1" over "2"; oops, disregard that ... [But you weren't asking about what] ;)

  Question: "How could such an operation be used in practice (either on single trits or multiple trytes)?"

The webpage "MuppetLabs" website describes it this way:

  "In TriINTERCAL programs the whirlpool (@) denotes the unary tritwise BUT operation. You can think of the whirlpool as drawing values preferentially towards the central value 1. Alternatively, you can think of it as drawing your soul and your sanity inexorably down....".

  "As for operators, ? is always subtract without borrow, and ^ is always add without carry. V is the OR operation and always returns the max of its inputs. & is the AND operation, which chooses 0 if possible but otherwise returns the max of the inputs. @ is BUT, which prefers 1, then 0, then the max of the remaining possibilities. Rather than add more special symbols forever, a numeric modifier may be placed directly before the @ to indicate the operation that prefers one of the digits not already represented. Thus in files ending in .5i, the permitted unary operators are ?, ^, &, @, 2@, 3@, and V. Use of such barbarisms as 0@ to represent & are not permitted, nor is the use of @ or ^ in files with either of the extensions .i or .2i. Why not? You just can't, that's why. Don't ask so many questions.".

[NOTE: In my opinion the Truth table provided by Esolangs (for "WHAT") is incorrect, it should be this:]

$$
\begin{array}{cc|cc} \text{WHAT} \, \qquad & ? & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 0 & 1 \\
& 2 & 2 & 1 & 0 \\
\end{array}
$$

Please see Esoteric Programming Languages for less information.


Merging two splay trees whose ranges may overlap in $O(\log N)$ I have two splay trees, $A$ and $B$.

When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$.

My question is; when all elements of $A$ are not necessarily smaller than all elements of $B$, how can we still merge $A$ and $B$ in $O(\log N)$?

What I have already tried:

Splay $A$'s largest element, splay $B$'s smallest element. The root $R_A$ of $A$ doesn't have a right child anymore, and the root $R_B$ of $B$ doesn't have a left child anymore. Compare $R_A$ and $R_B$. If $R_B$ is bigger than $R_A$,  make $R_B$ the right child of $R_A$, which fails when $R_A$ is larger than $R_B$.

No, you cannot merge two splay trees whose ranges may overlap in  $O(\log N)$, where $N$ is the total number of nodes. You may have to move at least $\Theta(N)$ nodes in general or average situations.

It contains no information at all when we know "whose ranges may overlap". The ranges of any two splay trees may overlap.

It contains no information at all when we know all elements of A are not necessarily smaller than all elements of B. That is the same as all elements of A are not necessarily larger than all elements of B.


Why isn't deque implemented as a dynamic array? We know that std::vector in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to reach O(1) amortized push_back time. But changing capacity of a vector is essentially allocation of new memory block and copying old data into it. That means we can as well implement a vector which can grow in both directions with amorized O(1) push_back and push_front time.

But std::deque is implemented in different, rather complicated way, not storing data in a contiguous manner and suffering from related issues (e.g. more frequent page faults when iterating). Why so? Are there any obstacles disallowing to implement deque as a dynamic array?

The reason why std::deque is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to std::vector.

You already partially said it: changing the capacity of an std::vector requires reallocating the memory and copying the entire content to the new memory. While it is true that the std::vectorreallocation scheme achieves a O(1) amortised complexity, the implementation of std::deque guarantees a true O(1) complexity bound for appending.


What happens when the xor inBlock chaining returns false? "With block cipher, each plaintext block is XOR-ed with the previous ciphertext block and then encrypted, this is known as block chaining. This prevents identical blocks of plaintext from producing the same ciphertext each time they are encrypted"

What happens inside the clause of the "XOR" statement, to make two equal plain text blocks encode into two different cipher text blocks?

Say you have blocks ABCDEA that you want to encrypt. If you do this naively, then the first and second A produce the same encrypted result, and an attacker would know that your first and last block are the same.

Instead you encrypt to A’B’C’ etc. by encrypting A -> A’, A’ XOR B ->B’, B’ XOR C -> C’, ..., E’ XOR A -> F’. It looks like you are encrypting random data, nothing an attacker can do.

The identical plain text blocks are XOR-ed with different previously encrypted blocks, that what’s making them different.


Faster Algorithm for Computing Norm Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:

$$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$

Store a list of all "factorials" (least common multiplies of $\{1,\ldots,k\}$) and use binary search. That reduces the number of divisions in the worst case. If the numbers $n$ you are getting are "random" then you might want to start with smaller trial divisions, or perhaps with an exponentially growing $k$, i.e. try $1,2,4,8,\ldots$ until you find some $k$ for which the LCM does not divide $n$, then take it from there using binary search.

By the way, since the LCM grows exponentially, even your algorithm only requires $\log n$ divisions. Each division takes time $\tilde{O}(n)$, so in total both your algorithm and mine are $\tilde{O}(n)$.


Maximum Independent Subset of 2D Grid Subgraph In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.

However consider the following subset of graphs:

Create an $N \times N$ grid of unit square cells.
Build a graph $G$ by creating a vertex corresponding to every cell.  Notice that there are $N^2$ vertices.
Create an edge between two vertices if their cells share a side.  Notice there are $2N(N-1)$ edges.

A Maximum Independent Subset of $G$ is obviously a checker pattern.  A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.

Now we create a graph $G'$ by copying $G$ and removing some vertices and edges.  (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)

By what algorithm can we find a Maximum Independent Subset of $G'$?

As JeffE mentions in a comment, a grid graph is an example of a bipartite graph. If you take a bipartite graph, and remove some of the vertices, it will still be a bipartite graph.

Königs Theorem states, that for bipartite graphs, the number of vertices in a minimum covering, equals the number of edges in a maximum matching.

As mentioned in the answer for Maximum Independent Set of a Bipartite Graph:

  The complement of a maximum independent set is a minimum vertex
  cover

What you are asking, is how to find a maximum independent set in a grid graph with some vertices removed, and the way to do that, is to use some of the algorithms for finding a maximum matching in a bipartite graph, from that construct a minimum vertex cover, and then invert it to get a maximum independent set.

The figure below shows a bipartite graph with a maximum matching (in blue), a minimum vertex cover (in red) and consequently also a maximum independent set (in white):


"Subpaths" of Dijkstra's shortest path also shortest? I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra's algorithm. Am I correct in assuming that the shortest path from C to B would be C > D > B, and that the shortest path from D to F would be D > B > F?

Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A  \rightarrow  C  \rightarrow  D  \rightarrow B  \rightarrow  F  \rightarrow E$.


How do stack-based cache algorithms avoid Belady's anomaly? I was going through page replacement algorithms from Galvin's Operating System book. I encountered this line about LRU:

  A stack algorithm is one in which the pages kept in memory for a frame set of size N will always be a subset of the pages kept for a frame size of N + 1.

And it states that stack based algorithm does not suffer from Belady's anomaly. Can anyone explain how it avoids Belady's anomaly?

Stack based algorithms implies that a set of n pages will be a subset of n+1 pages. Why?

In LRU every time a page is referenced it is moved at the top of the stack, therefore the top n pages of the stack are the n most recently used pages. Furthermore, since in LRU the near future is an approximation of recent past, we effectively will reduce the page faults if we increase n.

That is, if number of frames are now made n + 1, top of the stack will have n+1 most recently used pages. Hence, set of n pages are a subset of n+1 pages and as page faults are directly proportional to n (due to the LRU assumption) increasing n will never increase page faults.

An intuitive case(special case) is to think that the LRU stack uses n = number of total pages required by the process. There will be no page faults. And if n=1, there will be page faults equal to total pages required by the process.


Ω(f(x)) and worst case analysis I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms.
Something in the asymptotic part is kinda of confusing to me.
Proving the Theta
The analysis above gives a quadratic-time upper bound on the running time of
this simple pattern matching algorithm. To prove the theta, we must show an
example where it actually does take Ω(mn) time.
Consider what happens when the text t = “aaaa . . . aaaa” is a string of n
a’s, and the pattern p = “aaaa . . . aaab” is a string of m − 1 a’s followed by a b.
Wherever the pattern is positioned on the text, the while loop will successfully
match the first m − 1 characters before failing on the last one. There are
n − m + 1 possible positions where p can sit on t without overhanging the end,
so the running time is:
(n − m + 1)(m) = mn − m 2 + m = Ω(mn)
This example is clearly meant to be the worst possible running time of the algorithm, however, instead of O(mn), Ω(mn) has been used.
Isn't Ω the lower bound of the algorithm, meaning for big enough n(s) the algorithm cannot perform better than this?
If it is then why is Ω used to show the worst performance, shouldn't Big Oh be used instead?
Any help would be much appreciated.

I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases.
In some sense, $\Omega$ is just the pessimistic view of the worst case running time. This shows that in the worst case (e.g. the word+pattern of your problem) you cannot expect a running time that is faster than $c \cdot mn$ for some constant $c$. However, the first paragraph of Proving the Theta suggests that they also show that the algorithm is guaranteed to run in time $\mathcal{O}(mn)$, this is the optimistic view, stating that you will never find and example where the running time is worse than $c' \cdot mn$ for some constant $c'$. Both parts combined give you that the running time is in $\Theta(mn)$.


Congruence of Squares for Factoring After coming across the assertion that given

$$
    x^2 = y^2 \pmod n \\
    x \neq \pm y \pmod n
$$

we can then conclude that n factors into

$$
    n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y).
$$

in this article, I attempted my own example but it doesn't seem to work.  I think there's a missing hypothesis, but more importantly, I'm interested in understanding why this would work under the correct conditions.

First, the example given was

$$
\begin{align*}
    &6^2 = 1^2 \pmod {35} \\
    &x+y = 7 \\
    &x-y = 5
\end{align*}
$$

So applying the gcd with $35$ simply retains the values, yielding the correct factorization

$$35 = 7 \times 5.$$

However, my test example was

$$
\begin{align*}
    &8^2 = 4^2 \pmod {24} \\
    &x+y = 12 \\
    &x-y = 4
\end{align*}
$$
If we just blindly applied the stated result, we would get

$$24 = 12 \times 4.$$

I would guess the problem is that my selected factors are not coprime.  Does anyone have any intuition for why this method works (when it works) or any hints towards a proof?

After some brief pondering, I've noticed it certainly works if the values $x+y$ and $x-y$ are coprime.  Their product divides $n$ yet they contain no overlapping factors, so by collecting the factors of $x+y$ and $x-y$ which are also factors of $n$, we will end up with precisely all the factors of $n$ and nothing extra.

The  assertion is not correct in general, as you have discovered.

However, here is what is correct:  $\gcd(x+y,n)$ is a factor  of $n$, and $\gcd(x-y,n)$ is a factor  of $n$.  Why?  Well, this is trivial: $\gcd(\text{anything},n)$ is always a  factor of $n$.  Of course, the gcd might be 1, but that's still a divisor of $n$.

We can say even more.   If we let $r=\gcd(x+y,n)$ and $s=\gcd(x-y,n)$, then their product is a multiple of $n$: i.e., $rs$ is a multiple of $n$.  Thus, you can replace $s$ with $s'=n/r$ and now $r,s'$ will have the property you want: both $r$ and $s'$ are divisors of  $n$, and $rs'=n$.  (Why is $rs$ a multiple of $n$? Because if  $x^2  \equiv y^2 \pmod n$, then it follows that $x^2 - y^2 \equiv 0 \pmod n$.  Now $x^2-y^2 = (x-y)(x+y)$, so it follows that $n$ divides $(x-y)(x+y)$, i.e., $n$ divides $rs$.)

This makes this method useful for factoring.  However, beware that there is no guarantee that get a non-trivial factor out of this.  For instance, consider $n=15$.   Then if $x=8$ and $y=7$, we have $x^2 \equiv y^2 \equiv 4 \pmod n$, but $\gcd(x-y,n)=1 $ and $\gcd(x+y,n)=15$, so we obtain that $15 = 1 \times 15$ -- true, but not very useful for factoring $n$.  What we can say is that if $n$  is the product of two large primes, and if you can randomly sample  two $x,y$ such that $x^2 \equiv y^2 \pmod n$, then with probability about $1/2$, $\gcd(x-y,n)$ and $\gcd(x+y,n)$ will give you the full factorization of $n$.

If you want us to comment on an assertion it helps to give a reference for it.  My guess would be that there is additional context you are not  providing, such as the assumption that $n$ is a product of two primes.


Number of cycles that arithmetic instruction takes for 25% improvement in performance? The program has the following proportion of instructions:
Arithmetic: 70%
Load/Store: 10%
Branch: 20%

The question is to find the number of cycles on average that an arithmetic instruction take for a 25% improvement in performance if load/store and branch instructions are not improved at all?

How to proceed with such type of questions?

Hint: You have 100 fruit: 70 Apples, 10 Lychees and 20 Bananas. You want to reduce the number of apples until you have only 75 fruit left. How many apples do you have to eat?


decision diagram and decision tree difference What are the difference between decision diagram and decision tree? Is BDD a type of DD? what are the other type of DD? what are the algorithms used for it

Decision tree is a tree.

Discision diagram is not necessarily a tree.

A binary decision diagram is a directed acyclic graph.

See the diagram at https://en.wikipedia.org/wiki/Binary_decision_diagram


Prove correctness of the iterative algorithm Description:

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Code:

class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}

The problem may seem very simple but the solution I came up with is quite intuitive and hence it may be prone to errors in situations like interviews, I would like to know if there is some sort of formal check for the correctness? if yes then, is there any generic approach?

Let Nums be the value of the array after method execution,
and nums the initial value. Let,

P(i) = Nums[0..i-1] is the same as nums[0..i-1], but ignoring `val`.

Your algorithm is correct if P(nums.length) is true.
This can be shown by realising that P is true at the beginning
of the loop, and each iteration of the loop preserves P.

Initially, i = 0 in the for loop, and we have

   P(0)
 = Nums[0..0-1] is the same as nums[], but ignoring `val`.
 = Nums[] is the same as nums[], but ignoring `val`.
 = true

Next, assuming P(i), for $i \leq nums.length$, show P(i+1) ;-)

This is some of the work of the Hoare Calculus mentioned above.


Keep k+ties largest elements in a stream I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element.

For example, I have $[10, 7, 7, 9, 10, 10]$ and $k = 4$, then I want to output $[10, 9, 10, 10]$. However, if $[10, 7, 7, 9, 10]$ and $k = 4$ I want to output $[10, 7 , 7, 9, 10]$. Note that in the first example number of unique elements is less than $k$.

If I didn't want these ties, I'd probably use min-heap and keep track of top-$k$ elements in that heap, replacing minimum every time larger element comes from the stream. However, with ties I would have to perform searching inside the heap the element if it's already there and only then perform replacement/addition.

What is the best way to keep track of top-k + ties elements from the coming array of integers?

Note: $n>>k$.

Keep a binary heap, where each element in the heap is a unique key value together with a pointer to a list of all the items with that key value.

For instance, with the input list $[10,5,7,5,7,9,10]$, the unique key values are $5,7,9,10$, so you'd have a heap containing the following 4 elements: $5$ (with a pointer to the list $[5]$), $7$ (with a pointer to the list $[7,7]$), $9$ (with a pointer to the list $[9]$), and $10$ (with a pointer to the list $[10,10]$).  Now you can find the top-$k$ elements (with ties) straightforwardly using this heap data structure.


Finding a Hoare logic correctness proof for a Repeat-Until loop How can we prove a program in repeat until using Hoare Logic?

I've found a rule like this:

{P} S {R}, {R ^ ~B -> P}, {R ^ B -> Q}

for

{P}
repeat
  S
until B
{Q}

But I still can't find any explanatiom how I can use this rule

For example in this question:

{x > 0 ^ y > 0}
     z:=0; u:=x;
     REPEAT
        z:=z+y;
        u:=u-1;
     UNTIL u=0;
{z = x * y}

How I can use the rule to prove this program?

UPDATE
I've tried to find invariant loop:

R : Z = X*Y + (Y - Y*U)

But I still confuse what is P?

Note that the loop is not the outermost construct in your program; that is a sequential composition. In order to apply this rule, you first need to take care of the initial assignments. In this case that is straightforward: you get that the formula $x>0\wedge y>0\wedge z=0\wedge u=x$ holds after $z:=0; \ u:=x$.

For the loop rule, you need three formulas: a precondition $P$, a postcondition $Q$, and an invariant $R$, satisfying the premises of the rule. The precondition $P$ also needs to follow from the formula we obtained above. The postcondition $Q\equiv z=x*y$ is already given in your initial triple. What is left to do is therefore to find $P$ and $R$ such that

$(x>0\wedge y>0\wedge z=0\wedge u=x)\to P$,
$\{P\}\ z:=z+y;\ x:=x-1\ \{R\}$,
$(R\wedge u\neq 0)\to P$,
$(R\wedge u=0)\to z=x*y$.

A special case which may be worth trying here is to assume that the third condition holds with equality, i.e. $P\equiv (R\wedge u\neq 0)$. This reduces the problem to finding $R$ such that

$(x>0\wedge y>0\wedge z=0\wedge u=x)\to (R\wedge u\neq 0)$,
$\{R\wedge u\neq 0\}\ z:=z+y;\ x:=x-1\ \{R\}$,
$(R\wedge u=0)\to z=x*y$,

which is essentially an application of the usual while rule. As for how to find $R$, that is in general a very tricky problem. You seem to be looking in the right direction, but you invariant still needs some work (checking which of the conditions it fails, and how, may help with that).


For a given k-DNF formula, what is the size of the formula for the purpose of complexity? I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $n$ in the time complexity would refer to in this case (that is that I don't know how the "size" of a k-DNF is defined, nor was it defined in the assignment). Is it the number of clauses, the number of literals (distinct or nondistinct?) or something else? I think they should all be equivalent for the purpose of complexity, but I would rather adopt the standard convention.

The two standard conventions are number of clauses and number of literals (counted with repetition!).
The two measures are within a factor of $n$ of each other.


Approximating NP-complete problems Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it.

Could we get around this by finding an algorithm which approximates the solution to a certain accuracy?

That is, would the result above bar the existence of an algorithm which finds a maximum independent set to an accuracy of 0.5? I.e., it is guaranteed to be less than 0.5 away from the size of a maximum set? (And hence implying that it actually is a maximum independent set.)

It seems to me that the latter wouldn't violate our proofs of non-tractability, which are discrete in nature, while still giving an answer that satisfies the problem from a practical perspective.

We do not know for certain that independent set cannot be solved exactly in polynomial time. However, it is considered unlikely, and this is the famous P$\neq$NP conjecture.

In cases where exact optimal solutions cannot (probably) be found in polynomial time, it is natural to look for approximately optimal solutions. Algorithms tackling this are known as approximation algorithms. If an algorithm always returns a solution whose value is within $\rho$ of the optimum, then we call it a $\rho$-approximation algorithm, and say that its approximation ratio is $\rho$.

A good example is MAX-3SAT, in which we are given a 3CNF formula, and our goal is to find an assignment maximizing the number of satisfied clauses. The corresponding decision version is a generalization of 3SAT, and so it is NP-complete. However, if we choose an assignment at random, it satisfies $7/8$th of the clauses in expectation, and we can in fact deterministically find such an assignment. Since the optimal solution satisfies at most a $1$-fraction of the clauses, this algorithm has an approximation ratio of $7/8$. It is a consequence of the PCP theorem that it is NP-hard to do any better (this is a result of Håstad). We say that MAX-3SAT is NP-hard to approximate within $7/8+\epsilon$ for any $\epsilon > 0$.

The independent set problem is much harder than MAX-3SAT. Indeed, it is NP-hard to approximate within $n^{1-\epsilon}$ for any $\epsilon > 0$. The best approximation algorithm known has approximation ratio $O(n(\log\log n)^2/\log^3 n)$ (as per Wikipedia).

In practice, independent set can probably be approximated better, but this is different to formalize, since it is not clear what properties real-world graphs satisfy. For random $G(n,1/2)$ graphs (in which each edge is chosen with probability $1/2$ independently), there is a $1/2$-approximation algorithm (the approximation ratio is with high probability over the choice of the graph).

Sometimes one considers smooth analysis of algorithms to model real-world instances. The idea is that real-world instances are noisy, and so instead of being interested in a specific graph $G$, we should be looking at a "neighborhood" of $G$ formed from graphs close to $G$ (differing by a relatively small number of edges). It could be the case that some algorithm has good approximation ratio on most of the graphs in the neighborhood of any graph $G$. I am not aware of any such analysis for independent set.


Understanding Murmur3 The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety of different functions (plus it has good distribution of values and adequate speed).

Choosing the seed

Is there any particular method of choosing the seed values for the Bloom filter application? By selecting them randomly, I give up the deterministic nature of the algorithm and hand-picking these values seems a little bit too brave. Is it known, whether two seed values s1 and s2, where s1 != s2, yield the same function (borrowing a linear algebra term: they would be linearly dependent) ?

Limiting the hash domain

The Murmur3 hash is a 32-bit value. Since the Bloom filter might not need all 32 bits, is it still OK with respect to the uniformity to just apply the modulo function to this value?

You have asked two questions. I will answer them one by one.

Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is reasonable, then all small sets of seeds should look "the same". I don't know the Murmur3 family, but it's probably reasonable enough.

Note that linear dependence is not the correct measure here — you want a $k$-tuple of hash values generated from $k$ different seeds to look like a random $k$-tuple of values, either statistically or computationally. Linear dependence is just one possible wrong thing that could happen.

Limiting the hash domain. If the modulus isn't a power of 2 then the resulting value wouldn't be uniform, but usually it will be "close enough" to uniform, particular with respect to the performance of a Bloom filter. Indeed, it is standard practice to generate a random number in a range $\{0,\ldots,m-1\}$ by taking a random 32-bit or 64-bit value modulo $m$.

In the specific case of Bloom filters, if you know that every value in $\{0,\ldots,m-1\}$ appears with probability in the range $[c/m,C/m]$ then you can adjust the analysis of the Bloom filter to see what you get. You can then calculate $c,C$ in your case (exercise) and choose parameters for the Bloom filter accordingly. You will probably find out that in most cases the parameters you get by assuming $c=C=1$ are very close to the ones that you get by taking into account the actual $c,C$.


Bidirectional Dijkstra vs Dijkstra Are there any kind of graphs where Bidirectional Dijkstra would expand more than Dijkstra?

I tried to come up with an argument like this:

Let node $n$ be expanded by Bidirectional Dijkstra. Now there are two possibilites:

Node $n$ was expanded in the forward search
Node $n$ was expanded in the backward search

If $n$ was expanded in the forward search, then it would have been expanded in Dijkstra's algorithm also because forward search of Bidirectional Dijkstra is essentially just Dijkstra stopped earlier.

If $n$ was expanded in the backward search, there are two cases possible:

$n$ is on the actual shortest path between start and goal.
$n$ is not on the shortest path between start and goal.

If $n$ is on the actual shortest path between start and goal, then $n$ will also be expanded by Dijkstra.  If $n$ is not on the shortest path between start and goal, then $n$ might not be expanded by the Dijkstra.(I am not sure how to use this case. Does this suggest that Bidirectional Dijkstra can expand more nodes than Dijkstra?)

Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following your reasoning.

Consider a graph $G(V, E)$ where $V$ is the set of vertices, $E$ is the set of edges and you want to find the shortest path between two vertices $s, t\in V$ (from source and target respectively). Say there is a single path of length $\ell$ from $s$ to $t$, $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$. Let us assume further:

$s$ has only one descendant, $u_1$
And, in general, $u_i$ has only one descendant, $u_{i+1}$, $1\leq i<\ell - 1$

However, $t$ has many different descendants: $\{v_1, v_2, \ldots, v_k\}$. For the sake of clarity, let us assume without loss of generality that the cost of all edges is 1 and that the path $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$ is the only optimal path.

Now, Bidirectional Dijkstra would expand first $s$ in the forward search and then $t$ in the backwards search. The forward OPEN list contains only $u_1$, whereas the backward OPEN list contains $\{v_1, v_2, \ldots, v_k\}$ and $u_{\ell-1}$. Next, $u_1$ is expanded in the forward search and the forward OPEN list only contains $u_2$. However, the backward search might choose $v_1$ for expansion. This is your case! $v_1$ does not belong to the optimal path, yet it is expanded by Bidirectional Dijkstra (admittedly, this depends on the tie breaking strategy but assume $k$ is too large and ties are broken randomly). In the end, the forward search would go all over $\pi$ whereas the backwards search might be entertained expanding descendants of nodes $v_i$.

However, the Unidirectional search algorithm would have gone all the way through $\pi$, as it is its only choice, finding the goal node in precisely $\ell$ expansions.

To prevent this, Ira Pohl's principle of cardinality is applied often. It dictates to expand nodes from the OPEN list with less nodes. In this case, it would suggest expanding only nodes from the forward search, making Bidirectional Dijkstra to behave like Unidirectional Dijkstra. However, it should not be very difficult to make some maths to find a little bit more involved case where Ira Pohl's principle of cardinality does not help and Bidirectional Dijkstra still expands more nodes than Unidirectional Dijkstra.

In general, we say that Bidirectional Dijkstra expands only $O(b^{d/2})$ nodes whereas Unidirectional Dijkstra has to expand $O(b^d)$ nodes, but this assumes that the branching factor is the same for the forward and backward search.

For a much broader discussion on the topic which also includes the intricacies of applying bidirectional search to heuristic search I do strongly recommend you reading: Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant. Bidirectional Search that is guaranteed to meet in the middle. AAAI 2016.

Hope this helps,


Clique in P when the input graph's connected components have at most $3\log|V|$ vertices? What's the time complexity of the clique problem for input graphs where each connected component has size at most $3\log|V|$? Is it in P?

Indeed, it is:

Consider the input $G,k$. First, it is easy to verify that the sizes of the connected components are as required.
Now, if $k>3\log |V|$, then clearly there is no clique of size at least $k$.

Otherwise, we can find the maximal clique in each component by considering all the subsets of the component.

For a component of size $3\log |V|$, there are $2^{3\log |V|}=|V|^3$ possible subsets of vertices. Once we identified the maximal clique in each component, we can compare this size to $k$, and return the answer.


Give the Regular-Expression (NFA) with specific Separation Patterns Question:
Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.
Attempt:
Followed the way we construct the set of strings such that $a$ occurs the odd number of times, I got the following solution:
$$b^*a(bb(bb)^* abb(bb)^*a)^*$$
But then I found the pattern $abbaa$ is not acceptable, as $a$ can appear multiple times consecutively. Is there any systematic way to solve the above problem?

I'll assume that no $a$s can appear together without interruption by a group of $(bb)^+$s, even if they form a group of odd $a$s. In that case
$$
a(bb)^+ (a(bb)^+ a(bb)^+)^*
$$
should suffice, where $x^+$ is defined simply as $x^+ = x x^*$.


Sampling maximal shortest paths in a graph? Let S be the set of all possible shortest paths in a directed graph. A path s in S is said to be maximal if it is not a subpath of another path in S i.e. it cannot be extended to another shortest path.

Let M be the set of all maximal paths in S.

Does anyone know how to efficiently sample paths from  M. Ideally, I would like the probability of sampling the longer paths in M to be higher.

Example: In the directed triangle, (1,2,3), we have 3 maximal paths, 1->2->3, 2->3->1, and 3->1->2

Non-maximal paths are prefixes or suffixes of shortest paths

So a maximal path is just a path that begins at a vertex $u$ with no in-edge and ends at a vertex $v$ with no out-edge.

It's straightforward to see that if a shortest path $P$ from $u$ to $v$ is a subpath of some shortest path $Q$ from $x$ to $y$, then $P$ is also a subpath of a shortest path $R$ from $x$ to $v$, and a subpath of a shortest path $S$ from $u$ to $y$.  Thus the following statements are equivalent:

$P$ is not maximal;
There exists a shortest path $Q \ne P$ that contains $P$ as a subpath;
There exists a shortest path $X \ne P$ that contains $P$ as a subpath, is longer than $P$ and either begins at $u$ or ends at $v$.

(1) and (2) are equivalent by definition; (2) follows from (3) trivially; (3) follows from (2) by the reasoning above and the fact that, since $Q \ne P$, at least one of $R$ and $S$ must be longer than $P$ and end at one of $P$'s two endpoints; $X$ can be whichever one this is.  We will use (3) to efficiently determine whether a given shortest path is maximal.

Maximality is determined by endpoints and length

If some shortest path from $u$ to $v$ could be extended to a longer shortest path, then all shortest paths from $u$ to $v$ could be so extended -- since the only property we care about is the length, and that doesn't change.  So the question of whether a given path $P$ from $u$ to $v$ is maximal is entirely determined by the length of $P$, and its start and end points $u$ and $v$ -- it is not necessary to know what specific internal vertices $P$ uses.  Thus, for any pair of vertices $(u, v)$, we can determine in a preprocessing step whether this vertex pair is "maxable"; a path $P = (u, \dots, v)$ is then maximal exactly when the pair $(u, v)$ is maxable and $P$ has length equal to the distance between $u$ and $v$.

The idea is to build a complete list of all maxable pairs $(u, v)$ and the number $n_{uv}$ of shortest paths between them.  Once these are known, paths can be uniformly sampled using a simple recursive procedure.

Determining maxable pairs

Let $A$ be the set of all vertex pairs $(u, v)$ such that $v$ is reachable from $u$.  This can easily be determined in $O(n^2+nm)$ time by starting a DFS from each vertex in turn.

We determine the set of maxable pairs by initially declaring that every vertex pair $(u, v)$ such that $v$ is reachable from $u$ is maxable; we then "cross out" all pairs $(u, v)$ for which some shortest path from $u$ to some $x$ has a shortest path from $u$ to $v$ as an initial subpath; finally, we "cross out" all pairs $(u, v)$ for which some shortest path from some $x$ to $v$ has a shortest path from $u$ to $v$ as a final subpath.  By (3) above, all pairs $(u, v)$ that have not been crossed out are maxable.

I'll now describe the first "crossing out" step.  The second is identical, except that we first reverse all edge directions, and when we are about to cross out some pair $(u, v)$, we instead cross out $(v, u)$.  The following assumes an unweighted graph; if the edges are weighted, you can replace the BFS with Dijkstra's algorithm.

From each vertex $u$ in turn, perform BFS on $G$, using $u$ as the root.  For each vertex $v$ visited at level $L$ during a particular BFS, if $v$ is adjacent (in $G$) to any vertex on level $L+1$ of the BFS tree, cross out the pair $(u, v)$.  This is because the paths in $G$ whose vertices start at the root $u$ of a BFS tree and thereafter occupy strictly increasing levels in that tree are exactly the shortest paths starting at $u$, and the "downward" (w.r.t. the BFS tree) edge leaving $v$ indicates that there is some $x$ for which a shortest path from $u$ to $x$ uses a shortest path from $u$ to $v$ as a subpath.  This can be performed in $O(n+m)$ time per root vertex, for $O(n^2+nm)$ time overall.

Let $Z$ be the set of maxable vertex pairs that remain after the above has run.

Counting shortest paths

As a further preprocessing step, we would like to count the number of shortest paths between any pair of vertices $(u, v)$.

For any vertex $u$, the number of shortest paths from $u$ to every other vertex $v$ can be calculated in $O(n+m)$ time with BFS.  This means that the total time needed to compute the number of paths between every pair $(u, v)$ of vertices is $O(n^2+nm)$.  Let $n_{uv}$ be the number of paths from $u$ to $v$.  Discard any pairs $(u, v)$ for which $n_{uv} = 0$, i.e., for which $v$ is not reachable from $u$.

Let $n_z = \Sigma_{(u, v) \in Z} n_{uv}$.

Sampling algorithm

The input is a graph $G$.  If $G$ has no vertices, return an empty path.  (This will arise as a base case later on.)  If it has at least one vertex then it has at least one maximal path (even if that consists of a single vertex).

The next step is to choose a start and an end vertex for the path.  This works differently depending on whether we are at the top level of the call stack or not:

If we are at the top level of the call stack, choose an endpoint pair $(u, v)$ from $Z$ at random with probability $n_{uv}/n_z$; otherwise
Let $n = \Sigma_{(u, v) \in A \cap (V(G)\times V(G))} n_{uv}$.  Choose an endpoint pair $(u, v)$ from $Y$ at random with probability $n_{uv}/n$.

These probabilities ensure that paths are chosen uniformly at random; if you want to weight paths in some other way, you are of course welcome to push these probabilities around.  $u$ will be the first vertex in your random path, and $v$ will be the last.  If $u = v$ then we are done: return the single-vertex path $u$.

Otherwise, construct a subproblem to recurse on: this is the induced subgraph $G'$ of $G$ whose vertex set is the intersection of $X$ and $Y$, where $X$ is all vertices in $G$ that are reachable from a child of $u$, and $Y$ is all vertices in $G$ that $v$ is reachable from, except for $v$ itself.  Recurse on this subproblem; it will produce a (possibly empty) path $P$.  Return the path $u, P, v$.

Note that whenever two vertices $u$ and $v$ still remain in $G'$, the number of paths between them $n_{uv}$ also remains unchanged -- so it's not necessary to recalculate these for each subproblem.  $X$ and $Y$ can each be found using DFS in $O(n+m)$ time, intersected in $O(n\log n)$ time (sort each list, if necessary, then use a $O(n)$ list merge) and the edges of $G$ that remain in $G'$ found in $O(m)$ time.  Each recursion level shrinks the graph by at least 2 vertices, so there are at most $O(n)$ recursive calls.  Thus the overall time complexity for sampling is $O(n(n + m + n\log n)) = O(n^2\log n + mn)$.


PSPACE and DTIME $2^{cn}$ This is a HW question that I'm stuck on and was hoping for some help.
we're supposed to prove that:

  PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$)

This can be proved by contradiction. You can use the fact that $PSPACE$ language remains $PSPACE$ if we remove polynomial length padding, where as $DTIME$ does not.


Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$? Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:
$f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh.
So, $O(g(n))$ is substitutable for $c\cdot g(n)$:
$f(n) = O(g(n)) + O(g(n))$
And by the max rule of sum:
$f(n) = O(g(n))$

Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think):
$$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$
Now  $f(n) = c\cdot g(n) + O(g(n))$ means, that  $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have
$$f(n) = c\cdot g(n) + \phi (n) \leqslant c\cdot g(n) + C\cdot g (n)=(c+C)g (n)$$
so $f \in O(g)$ and your claim is correct.
The general rule can be worded as follows:
If $f \in O(g)$, then $f+O(g)=O(g)$


Normal form after decomposition of a relation I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF.

I felt a bit suspicious regarding this claim, but couldn't find anything to prove this statement wrong.

Am I correct in thinking that this statement doesn't hold all the time, or Am I wrong? It would be really helpful if someone can correct me if I am wrong?

Thanks in advance!

I think you are wrong.

Here is a rough sketch of a proof (by contradiction) that the original claim is true.

Suppose that the claim is false: this means that R1 or R2 (or both) are not
in 3NF. Without loss of generality, suppose that R1 is not in 3NF. This means that, among all the dependencies
holding in R1, there is at least a dependency X → A in which X is not a superkey
(and so it is neither a candidate key) and the attribute A is not prime.

Now consider the definition of lossless decomposition: for each possible
valid istance r of R, we have that r = πT1(r) ⨝ πT2(r), where T1 are the attributes of R1 and T2 are the attributes of R2.

This means that each valid instance of R1 is a projection on the attributes T1
of some valid instance of R. But this implies that if X → A is valid in an instance r1 of R1, it will be also valid in an instance r of R obtained by joining r1 with some instance of R2 (because, for the definition of join, the tuples of r1 will appear in r unchanged, possibly repeated).

So this means that X → A is also valid in R, contradicting the initial hypothesis that R is in 3NF.