Automated geometric theorem-proving using synthetic methods This question is about geometric theorem proving and is inspired by this  Math.SE  post.  Currently, Euclidean-geometric theorem provers, as referred to in the post, use coordinate geometry to convert a geometry problem into a set of algebraic equations.

  Why haven't people developed a theorem prover that uses synthetic reasoning ?

By 'synthetic' I mean reasoning from axioms. I feel that synthetic reasoning would be more insightful than solving a large number of equations; yet, am unsure about how well it yields to implementation. Can you offer more insight? What would be the benefits and drawbacks of such a prover?

Also,I felt that my question would be more appropriate here than on Math.SE.

(Note: I don't know anything about geometric reasoning, so I'm shifting from my limited experience in automated theorem proving in another field. I think the fundamental issue is the same.)

Synthetic reasoning tends to blow up exponentially. Typically, after $n$ steps of reasoning, there are about $a^k$ ways to choose a next step for some $a \gt 1$. There might be some overlap because there are multiple ways to prove the same theorem, but you still end up with a really fast combinatorial explosion in practice.

Reasoning from the goal is typically a lot tamer, because you tend to try to deduce the goal from simpler premises. It's still impractical in all but rather constrained settings (e.g. some arithmetic or geometric theories).

Putting a geometric problem into equations sets a boundary on the problem. You have $p$ equations and $q$ unknowns, now go and solve. Since the problem is bounded, the search for a solution will not go on forever. Furthermore, this form is convenient for many shortcut tricks that allow for faster solving, because solving algebraic equations is a well-known problem.

This choice of method is not less insightful than synthetic reasoning. An algebraic solver can keep track of the reasoning steps that it uses, and produce a proof trace that explains why the purported solution is really a solution. (Not all solvers bother to keep a proof trace.) This proof trace can be expressed in terms of geometric axioms. Thus you can get the same amount of insight no matter how the proof was obtained. (Insight, or lack thereof: in synthetic reasoning, “and then you apply this lemma” doesn't tell you why this lemma rather than any other lemma.)


Does a Turing machine really need an infinite tape Turing machines are usually described as having an infinite tape (i.e. a tape with infinitely many memory locations), but I think it only needs to have a  tape that has a sufficient but finite number of memory locations for the problem it's working on, (although, of course, it is unknown in advance how many locations will be needed.) Am I right?

Alternative question: if and when a Turing machine halts, has it only used a finite portion of its tape?

The answer to your alternative question is "yes". A Turing machine that halts, halts in a finite number of steps, and it can only move the head a finite distance from the starting position in a finite number of steps.

However, a Turing machine need not halt and may use up an ever growing number of tape positions as it executes. Further, we cannot in general tell how much tape a Turing machine will need to execute correctly.

Sometimes people speak of needing an "unbounded" or "ever extendable" tape rather than an "infinite" tape. About the only significance to this difference in wording is that the former wording makes it a bit clearer that the notion of a Turing machine should not be problematic to a finitist (though perhaps still for an ultrafinitist).


Proving closure under reversal of languages accepted by min-heap automata This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

  Is HAL closed under reversal?

Consider the language
$$L_{\times 2} = \big\{ x\bot y\bot z  \mid x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$$
(where $\#_0(x)$ denotes the number of zeros in $x$).

It is easy to decide $L_{\times 2}$ using a HAL machine — observe that the machine needs to keep track of two properties: the number of zeros in $x$ vs $y$ and the length of $x,y$ (vs $z$). It can push a 0 into the heap for every zero it sees in $x$ (and then later pop 0 for any zero seen in $y$); additionally it pushes 1 for any bit in $x,y$ (and later pops 1 for any bit of $z$). Since all the 1s are pushed down the heap, they don't interfere with the 0 count. The $\bot$ serves as a delimiter, and can be practically ignored.

Now, let $L = L_{\times 2}^R$, be the reverse language. That is,
$$ L = \big\{z\bot y \bot x \mid  x,y,z\in \{0,1\}, \#_0(x)=\#_0(y) \text{ and } |x|+|y|=z\big \}$$
We will show that no HAL machine can decide $L$.

The intuition is the following. As above, the machine must keep track of both the length of $z$ and the number of zeros in $x,y$. However, in this case it need to track them simultaneously. This cannot be done via a heap. In more details, after reading $z$, the heap contains information about the length of $|x|+|y|$.
while reading $y$ the machine must also keep in the heap the number of zeros in $y$. However, this information cannot interfere with the information the heap already has on the length we expect $x$ to be. Very intuitively, either the information about the number of zeros will be "below"  the information about the length of $x$, and then we cannot access it while reading $x$, or it is "above" that information, rendering the latter inaccessible, or the two information will be "mixed" and become meaningless.

More formally, we are going use some kind of a "pumping" argument. That is, we will take a very long input, and show that the "state" of the machine must repeat itself during processing that input, which will allow us to "replace" the input once the machine repeats its "state".

For the formal proof, we require a simplification of the structure of the HAL machine, namely, that it doesn't contain a "loop" of $\varepsilon$-transitions$^1$. With this assumption we can see that for every input symbol the machine processes, the content of the heap can increase/decrease by at most $c$  (for some large enough constant $c$).

Proof.
Assume $H$ decides $L$, and consider a long enough input (say, of length $4n$, thus $|x|=|y|=n$, $|z|=2n$, ignoring the $\bot$s hereinafter). To be concrete, fix $z,y$ and assume that $\#_0(y) = n/2$. Observe that there are ${n \choose n/2}$ different $x$'s such that $z\bot y \bot x \in L$.

Consider the heap's content immediately after processing $z\bot y$. It contains at most $3nc$ symbols (where each symbol is from a fixed alphabet $\Gamma$), by our assumption. However, there are ${n \choose n/2}$ different $x's$ that should be accepted (which is substantially larger than the amount of possible different contents for the heap, as this increases exponentially, while the different number of heaps increases polynomially, see below).
Take two inputs $x_1,x_2$ that should be accepted, so that the following holds:

The prefix of length $n/2$ of $x_1$ has different number of zeros than the prefix of $x_2$ of the same length.
By the time the machine reads a prefix of  length $n/2$ of the $x$ part, the heap looks the same for both $x_1$ and $x_2$, and also, the machine is in the same state  (this must happen for some $x_1,x_2$, for large enough $n$, as there are more than $2^{0.8n}$ different options$^2$ for $x_1,x_2$, and at most $(3.5cn)^{|\Gamma|}|Q|$ different options for heap content and state$^3$).

It is clear that the machine must accept the word $z\bot y \bot x_1^px_2^s$, where $x_1^p$ is a prefix of $x$ of length $n/2$ and $x_2^s$ is a suffix of $x_2$ of the same length. Note that the number of zeros in $x_1^px_2^s$ differs from the number of zeros in $x_1$ and $x_2$ (that is, from $\#_0(y)$), due to the way we chose $x_1$ and $x_2$, thus we reached a contradiction.

$^1$  Does this assumption damages generality? I don't think so, but this indeed requires a proof. If someone sees how to get around this extra assumption, I'd love to know.
$^2$  Let's fix $x_1$ so that it's prefix (of length $n/2$ has exactly $n/4$ zeros). Recall that using Stirling's approximation we know that $\log {n \choose k} \approx nH(k/n)$ where $H()$ is the Binary entropy funciton. Since $H(1/4) \approx 0.81$ we have ${n \choose n/4} > 2^{0.8n}$ for large enough $n$.
$^3$  Assuming alphabet $\Gamma$, there are $|\Gamma|^n$ different strings of length $n$, so if this was a stack we were screwed. However, pushing "01" into a heap is equivalent to pushing "10" - the heap stores only the sorted version of the content. The number of different sorted strings of size $n$ is  ${n+1 \choose |\Gamma|-1}\approx n^{|\Gamma|}$, for a constant $|\Gamma|$.


Algorithm for cost function maximization I have a system that takes in 'm' inputs and provides a cost value as an output. The system is a "black box" to me. The inputs can be varied and the corresponding output can be observed, however, I have no prior knowledge of the function that this box implements. Given that I can fiddle with the input values(all real valued), is there an algorithm or a learning based solution that can maximize the cost function in minimum number of iterations? I think this might be a well known problem, however, this genre is way beyond my ken and I am finding it difficult to frame the terms I should be googling for. A link or mention of the name of the algorithm or a short description of the solution would be appreciated.

If don't know anything about the function, then your problam is practically unsolvable: The function in the box could be 0 evereywhere, except for a single set of inputs, where it is 1. No strategy can guarantee that you find this set of inputs in finite time.

The situation might look better, if you can assume some sort of smoothness and/or monotony conditions.


What is the difference between a problem and an algorithm? I can say that $x * y$ is a problem, but I can also say that $x * y$ is an algorithm for finding a rectangle area.
I have been reading Wikipedia about an algorithm and a problem, but I am not sure about their definitions. Could you please explain it to me in more detail?

A problem is a thing that needs to be done; an algorithm is a procedure for doing it.

To address your specific example, "What is $x\times y$?" is a problem and "Multiply the length by the width" is an algorithm for solving the problem, "What is the area of this rectangle?" It uses, as a subroutine, some unstated algorithm for multiplying numbers.


Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and you can't go trough it all, but you can choose any item. In the second, you must choose to accept or reject an item permanently, so if you get to the end, and the last item is a dud, you're stuck with it.

You have no prior knowledge of the range of scores found in the list. As you look at elements of the list, continuously adapt your threshold for acceptance, until you are able to choose an item without having exhausted the list.

For the second variation (finite list), I've seen it in some semi-joking context about dating, where you spend up until age 35 dating people as "samples" and rejecting them all in due time, then past age 35, take the first person who is above the threshold learned from the previous samples.

These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term.

The example about dating appears in Hannah Fry's Ted Talk "The Mathematics of Love"


What can a quantum query to a function do? The $n$-qubit Hadamard gate acts as,
$$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$
So it is capable of producing the uniform superposition state over an exponential number of states in what is to be seen as a ``single" step.

Now if one is given a boolean function $f$ then how is it that the above uniform superposition state can be converted into   $\frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} f(x) |x\rangle$ by a ``single query to $f$ in superposition" ?
Can someone give a mathematical or a gate picture of this ''single query to $f$ in superposition" ? What is the unitary operator which corresponds to this ''single query to $f$ in superposition"  ?

A part of this confusion arises because I am under the impression that if kets are indexed by elements of $\{0,1\}^n$ then a ''single" quantum query to a Boolean valued function $f$ is ``by definition" a transformation of the form  $\vert x \rangle \vert y \rangle \rightarrow \vert x \rangle \vert y \oplus f(x) \rangle$ or which is often thought of as the operator $O_f(x)$ acting as $O_f(x) \vert y \rangle =  \vert y \oplus f(x) \rangle$
But I can't see the transformation in the question as a any combination of $O_f(x)$ kind of operators!

the gate $f$ performs the transformation
$$\rvert x\rangle \rvert0\rangle \to \rvert x\rangle \rvert 0\oplus f(x)\rangle, $$

but $0$ is idempotent for $\oplus$ so you simply get $\rvert x\rangle \rvert f(x)\rangle$.
Now, by linearity, if you input a superposition instead of a basis states, you'll get a superposition of the "answers", e.g.,

$$\frac1{\sqrt2}(\rvert 0\rangle \rvert0\rangle+\rvert1\rangle |0\rangle) \to \frac1{\sqrt2}(\rvert 0\rangle \rvert f(0)\rangle+\rvert 1\rangle \rvert f(1)\rangle)$$

Then, if you start with a Hadamard, and get an equal superposition of all basis states, you end up with a superposition of all possible "answers".
$$\frac1{N} \sum_x \rvert x\rangle \rvert 0 \rangle \to \frac1{N} \sum_x \rvert x\rangle \rvert f(x) \rangle.$$

The fact that $x$ or $0$ are in fact a "string" over $\{0,1\}$ doesn't make any difference - treat them as a single quantum system of higher dimension (or treat each qubit as a separate function $f_i$ where $f_1()f_2()\cdots f_n()=f()$ are the bit-wise functions.


Question of checking the $n$th root Problem:
Input : $n$, $k$

Check : Is $\frac{k}{4h -1} = n^{\frac{1}{h}}$? for any $  0 \le h <= n$.

Question: What is the fastest algorithm for the above problem assuming the model of computation is RAM?

The function

$$f(h) = \left( {k \over 4h-1} \right)^h$$

is monotonically decreasing for $h < k+1/4$, and monotonically increasing for $h>k+1/4$.  (How do I know?  Set $f'(h)=0$ and solve for $h$.)

Therefore, one approach is to use a binary search on $h$ within the range $[0, \min(k+1/4,n)]$ to search for $h$ such that $f(h)=n$, followed by another binary search on $h$ within the range $[k+1/4, n]$.  You could also replace the binary search with a method with faster convergence, such as Newton's method.


Is an oracle ever useful if you can't control the input instances? Let's say $F$ is an oracle for a problem in  $\mathbb{NP}$, but I cannot call this oracle with any input instance.  Instead, whenever I call $F$ I get returned a random instance and solution.  Thus, I know that $F$ is in fact capable of solving arbitrary $\mathbb{NP}$-hard problems, I just can't specify which one I want it to solve.

Is it possible to use such an oracle to solve an $\mathbb{NP}$-complete problem faster?  My gut says no because the naive use of the oracle still requires $O(2^n)$ time by calling the oracle enough to check every solution.  I just can't think of a way to prove this.

As Xodarap pointed out, if you require your algorithm with the “random oracle” to always output the correct answer, then the random oracle is useless.  The problem becomes more interesting if we allow small probability of error (where the probability is with respect to the random instance chosen by the oracle).

In addition, as Vor pointed out in comments on the question, it is meaningless to say “random instance” without specifying a probability distribution.  One of the reasonable assumptions to make here is that this random instance is chosen uniformly at random from the set of all strings of length p(n), where n is the input length and p is some fixed polynomial.  We could make other, weaker, assumptions on the probability distribution.

Here we will make the assumption quite general, and will show that existence of a randomized polynomial-time algorithm with a “random oracle” for NP-complete problems has a surprising consequence even under this weak assumption.

Let’s drop the requirement that the “random oracle” will solve a problem in NP (on a randomly chosen instance).  Now the “random oracle” can be any predetermined probability distribution over polynomial-length strings, and every time it is asked, it emits a string according to this probability distribution.  The only requirement is that this probability distribution depends only on the input length.  Note that your model is indeed a special case of this model.  In your model, the probability distribution is required to have the following form: it first chooses a uniformly random instance y from a set depending on the input length, and then returns a pair (y, g(y)), where g: {0, 1}*→{0, 1} is the characteristic function of some decision problem in NP.  Now we allow any probability distribution, as long as the distribution is determined by the input length alone.

An “oracle” of this general form is called a randomized advice.  The class of decision problems which can be decided by a randomized polynomial-time algorithm with a randomized advice (with bounded two-sided error) is called BPP/rpoly, and it is known that this class is equal to P/poly.  (The inclusion BPP/rpoly⊆P/poly can be proved in the same way as a well-known inclusion BPP⊆P/poly.  For a proof of the latter, see e.g. Theorem 6.3 of Goldreich [Gol08].)

This means that if an NP-complete problem can be solved in your model, then NP⊆P/poly.  However, it is known that NP⊆P/poly implies that the polynomial hierarchy collapses to the second level [KW98, Cai07].  Most complexity theorists consider a collapse of the polynomial hierarchy as a big surprise.  If we believe that the polynomial hierarchy does not collapse, then NP-complete problems cannot be solved efficiently with the “random oracle” in your sense.

References

[Cai07] Jin-Yi Cai.  S2p ⊆ ZPPNP.  Journal of Computer and System Sciences, 73(1):25–35, Feb. 2007.  DOI: 10.1016/j.jcss.2003.07.015.

[Gol08] Oded Goldreich.  Computational Complexity: A Conceptual Perspective.  Cambridge University Press, 2008.

[KW98] Johannes Köbler and Osamu Watanabe.  New collapse consequences of NP having small circuits.  SIAM Journal on Computing, 28(1):311–324, 1998.  DOI: 10.1137/S0097539795296206.


Flow value over edges in Max flow/Min Cut Ford Fulkerson Is it true that if a given edge e is in the min cut of a graph that there exists a max flow of the graph that has e with its full capacity?

Yes. More precisely, for every min cut $(W,\bar{W})$, there is some max flow $f$ such that $f(x,y)=0$ if edge $(x,y)$ goes from $\bar{W}$ to $W$, and $f(x,y)$ equals the capacity of $(x,y)$ if edge $(x,y)$ goes from $W$ to $\bar{W}$. This is usually proven using the linear programming formulations of min cut and max flow, and follows by the complementary slackness property.


What algorithm can I use for a rule based system? I'm doing research for a system that is based on rules. The goal of the system is to fire when some of the rules are true.

Explanation (requirements/working of the algorithm):
The algorithm will run in the background of an app. There will be a lot of data available about the user. The algorithm will apply the defined Business Rules to the data. When an X amount of the rules result in true, the algorithm should fire. The goal of the algorithm is to fire when the user shows any possible problems (based on data / the business rules that result in true).

Examples of Business Rules:

  IF a user is in the app between 2-5AM more than 5 times in 2 weeks THEN the user is not sleeping at the correct times.
  IF a user moved house twice THEN a user moves house a lot

The Business Rules are in the If condition(s) then action format.
The condition can be of any type. It would be really nice if it will be "easy" to add new forms of conditions in the future and the algorithm can handle such changes.

I'm looking for an algorithm that can be of use for the goal described above. Preferably without the use of Machine Learning. So I'm looking for an up-to-date/newer version of an Expert System.

When I did research, almost every time I came back to an Expert System. I think it perfectly fits my requirements. However I can't find anything recent on Expert Systems. It looks like it is outdated, as mentioned in this post, four years ago.

I saw something like an Recommendation System in this post. Still I don't think this will solve my problem because it focuses on recommendations...

Does anyone else have ideas for an algorithm?

EDIT: Tried to add useful information

You don't need an algorithm.  Since you already have a set of rules, all you need to do is implement the rules.

The simplest implementation strategy is to simply re-evaluate all the rules each time something changes.  However, in some cases this might repeat work unnecessarily and there might be more efficient implement the rules.

For instance, if one of your rules is "IF the user has bought more than 1000 items today THEN sound an alarm", then re-evaluating this each time an item is bought might be unnecessarily inefficient.  A more efficient approach would be to keep a counter for each user that keeps track of how many items the user has bought today; each time an item is bought, increment the counter and sound an alarm if it is over 1000; and each midnight, reset all counters to zero.

So in some cases optimizations might be possible.  However, that is entirely depend on the specific of the rule, and there's not much we can say in general.  If you have a question about how to implement a specific rule efficiently, you can ask a new question specifically about that particular rule.


Solving recurrence relation for asymptotic analysis How to solve the recursion:

$
T(n) =
\begin{cases}
T(n/2) + O(1),  & \text{if $n$ is even} \\
2T(\lceil n/2 \rceil) + O(1), & \text{if $n$ is odd}
\end{cases}
$

I know that it can be written as O(n). But I want to find a tighter bound. For example, when dealing with powers of two, T(n) is O(logn), which will most probably allow for a tighter bound overall.

So, how to solve this recursion?

Suppose $n = 2^m + 1$. Then
$$
T(n) \geq 2T(2^{m-1}+1) \geq 4T(2^{m-2}+1) \geq \cdots,
$$
and so $T(n) = \Omega(n)$ for $n$ of this form. Therefore you cannot get a better worst-case bound than $O(n)$.

In more detail, this example shows that if $T(n) = O(f(n))$ for a monotone function $f(n)$ then $f(n) = \Omega(n)$. You might be able to get an upper bound using more information on $n$.

Let's analyze a similar but slightly simpler recursion,
$$
S(n) = \begin{cases} S(n/2) + 1 & \text{if $n>0$ is even}, \\ 2S(\lfloor n/2 \rfloor) + 1 & \text{if $n$ is odd},\\ 0 & \text{if $n = 0$}. \end{cases}
$$
Let us denote
$$
S(a_1,\ldots,a_k) = S(2^{a_1} + \cdots + 2^{a_k}),
$$
where we implicitly assume that $a_1 > \cdots > a_k$. We have
$$
\begin{align*}
S(a_1,\ldots,a_k) &= 1 + S(a_1-1,\ldots,a_k-1) \\ &=
2 + S(a_1-2,\ldots,a_k-2) \\ &= \cdots \\ &=
a_k + S(a_1-a_k,a_2-a_k,\ldots,a_{k-1}-a_k,0) \\ &=
a_k + 1 + 2S(a_1-a_k-1,a_2-a_k-1,\ldots,a_{k-1}-a_k-1) \\ &=
(a_k + 1) + 2(a_{k-1}-a_k) + 4S(a_1-a_{k-1}-1,\ldots,a_{k-2}-a_{k-1}-1) \\ &=
(a_k+1) + 2(a_{k-1}-a_k) + 4(a_{k-2}-a_{k-1}) + \cdots + 2^{k-1}(a_1-a_2) \\ &=
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1.
\end{align*}
$$
Notice now that
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \geq \\
2^{k-1} a_1 - 2^{k-2} (a_1 - 1) - \cdots - (a_k - (k-1)) + 1 = \\
a_1 + 2^k - k,
$$
and on the other hand,
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \leq \\
2^{k-1} a_1 - 2^{k-2} (k-2) - 2^{k-3} (k-3) - \cdots - 0 + 1 = \\
2^{k-1} (a_1 - k + 3) - 1.
$$
This gives us a lower bound of $\Omega(\log n + 2^{|n|})$ and an upper bound of $O(n)$, where $|n|$ is the Hamming weight; note that if $n = 2^m-1$ then the lower bound is linear in $n$. Indeed,
$$
S(2^m-1) = 1 + 2S(2^{m-1}-1) = 1 + 2 + 4S(2^{m-2}-1) = \cdots = \\ 1 + 2 + 4 + \cdots + 2^{m-1} S(1) = 2^m-1.
$$

It is likely that you can find a similar formula for $T$.


Showing that tournament sort requrires O(n log n) comparisons I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.

On to my question. Before I do, this is a class question that has been asked, answer, and considered to be over; however, I'm struggle accepting the answer. For this reason, I'm here hoping someone can word it in a way that I understand it.

The problem is as follows:

Show that if n is a power of 2, tournament sort requires O(n lg n) comparisons.

I refer to a rooted tree graph of six levels (0-5) with the vertices doubling at each level: i.e  1, 2, 4, 8, 16, 32. I see a pattern very similar to binary. I'm not implying the problem is binary related, but it is powers of 2 and I'm very comfortable with binary.

Using that 2^5 = 32, n=32; therefore, n is a power of 2. No argument here. Now I read the problem to say that 32log32 (nlogn) will result in the number of comparisons. The aide answering my question said, "the calculated results of the nlogn were immaterial. I just needed to know there were 5 levels down, and therefore 5 levels up." Additionally, he kept referring to 5log5 which I still don't see a result that makes any sense to me.

As I study the question, I read it to say that the nlogn should provide me with a number of comparisons, based on n. I cannot make that happen with a known values.

Can someone please help me to follow this better?

Initially you place the elements you want to sort in the leaves of the tournament tree. Then you fill all the internal nodes with the bigger of the two elements in their respective children. This takes $n-1$ comparisons.

After that, you have the largest element in the root. So you can remove it and place it in the output. Now all the comparisons where this element was involved have to be redone. This is one comparison per level of the tree, making $(\log n) -1$ comparisons (-1, since on the lowest level, there is only one candidate element left, so you don't need to compare.)

Now the second largest element is at the top and you can repeat the procedure. And so on. In the end you will have made up to $\log n$, i.e. $O(\log n)$ comparisons for each of the $n$ elements.

Summing up, we have $n-1 + n\cdot O(\log n)$ comparisons. By the rules of $O$-notation, that is in $O(n\log n)$.


How to calculate sum of binomial coefficients efficiently? I want to compute the sum

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$

where $n$ and $k$ can be up to $10^{14}$ and $k\le n$.

I found several links on stack overflow to calculate sum of binomial coefficients but none of them works on large constraints like $10^{14}$.  I tried doing it by changing series using the relation $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and came up with a brute force solution which is of no use. Is there any way to do it efficiently?

This question is from the TCS codevita 2016 round 2 contest, which has ended.

Hint: Use Lucas's theorem.

In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.

Spoilers

Don't peek at any hint until you've spent a good amount of time thinking about the previous one!

A more in-depth hint if the previous wasn't enough:

   Let $p=10^9 + 7$.  Use Lucas's theorem to express $\binom{n}{i}$ in terms of functions of $n \bmod p$ and $i \bmod p$.  Simplify the resulting sum by grouping terms.

If that's still not enough of a hint:

   Consider the case where $k$ is a multiple of $p$.  You should be able to come up with an efficient algorithm for that whose running time is something like $O(k/p)$.

Then for a final answer:

   Generalize to the case where $k=ap+b$.  You should be able to express this as a sum of the previous form, plus $b$ more terms.  As a result you should be able to achieve a final running time of $O(p)$.


Finding both the longest and shortest path in a convex polygon Let $S$ be a convex polygon on $n$ points. Given two points $A$ and $B$, where $A$ is left of $S$, and $B$ is right of $S$, what's an algorithm to find the shortest path from $A$ to $B$, that avoids the interior of $S$? What about the longest path?

The shortest path will be made out of straight lines connecting A, B and the vertices of S.

The most simple solution is to check a bunch of paths, starting with path AB; then AXB and AYB where X and Y are the topmost and bottommost points of S; then extending to the left or right neighbors of X and Y, if some intersections happen.

A smarter solution would be to find the points P, minimizing and maximizing the angle between $\vec {AP}$ and $\vec {AB}$. Those will be the points where your path enters and leaves S.

The longest path is, obviously, infinite.


Average number of inspections Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$:

$$p(i) =
\begin{cases}
1/2^{n−1},  & \text{if i = 0} \\
1/2^i, & \text{otherwise}
\end{cases}$$

Assume linear search is used and every search is successful - every element we look for exists.

What is the average number of nodes inspected for a search under random(elements in the linked list are stored in a random order) organisation and what is the average number of nodes if sorted based on their decreasing probability(i.e., it starts with the element ‘1’, followed by element ‘2’, then ‘3’, and so on, with the last node containing element ‘0’.) for large values of n?

I know the answer for the first part is surely not $n/2$(since the probability is not the same for all of the elements) but I do not really know much more than that... but when sorted, I suspect it should be something close to $$\sum_{i=1}^{n-1} i*{1/2^{i}} + n * 1/2^{n-1}$$ because it takes one comparison to get to first element, two to the second, etc. and the last one takes n comparisons times the probability of 0. I also found the $$\sum_{i=o}^{∞} a*b^a = b/(1-b)^2$$ which in this case would be equal to 2 (b = 1/2) but I have no clue how to tackle the edge case - '0'. :(

I am also aware of this thread but there each of the numbers had the same probability and it is not exactly the same.

I hope to find an answer to this as it has been bothering me for quite a while and I am truly curious about the result.
Any hint will be greatly appreciated!

Well, let's see. Please point out if I understood the problem model incorrectly.

Suppose we have $n = 5$ elements. Suppose it's sorted in the way $s = [1, 3, 4, 0, 2]$. Then using linear search we are going to with probability $(1/2)^3$ have 2 steps in our search and with probability $(1/2)^4$ have 4 steps in our search.

So, what's the average number of steps we need to find an element giving arbitrary sorting $s$? Let's say $X$ - number of steps needed in our search. Probability to get $X=i$ steps is equivalent to request a search for an element $k \in \{0,1,2,..,n-1\}$ giving we have it at the $i$th position. That is $$P(X = i) = \sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position)P(the\ element\ k\ is\ at\ ith\ position)$$ Then we notice that $P(the\ element\ k\ is\ at \ ith\ position) = \frac{(n-1)!}{n!} = \frac{1}{n}$ because we have an element at a fixed position and $(n-1)!$ possible permutations for other elements out of the total $n!$ possible permutations of our $n$ elements.
Then we notice that $\sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position) = 1$. It means that $P(X=i) = \frac{1}{n}$. So, the expectation is just $\sum_{k=1}^{n} \frac{k}{n} = \frac{n+1}{2}$.

Of course, the second part is much easier to derive, it's just $$E(X|sorted\ in\ decreasing\ probability) = \sum_{k=1}^{n-1} \frac{k}{2^{k}} + \frac{n}{2^{n-1}}$$ (just notice that the elements are going to be from $1$ to $n-1$ and then the element $0$, however $0$ could be the pre-last element because it have same probability as $n-1$). So, we just calculating the expectation of the probability distribution, though this time not for the joint probability but conditional.


How do we guess the recurrence relation from the given equation In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is
\begin{equation}
T(n)=2 T(\lfloor n / 2\rfloor)+n
\end{equation}

the author guessed the solution was $O(n \log n)$ and proved it below, my question is how to make the guess? I wanted to know why it cant be $O(n^2)$? How do you guess them correctly at first?

\begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \lg (\lfloor n / 2\rfloor))+n \\ & \leq c n \lg (n / 2)+n \\ &=c n \lg n-c n \lg 2+n \\ &=c n \lg n-c n+n \\ & \leq c n \lg n \end{aligned}

To guess simple recurrences most useful step is to study basic intuition beyond so-called master theorem that looks at any recursion as if it is implicit tree.

Your case is admissible for it and thus easy: on each step you have half of task (peek one branch down in tree), and $O(n)$ work. Multiply tree height and amount of work on each step and you will get your guess. But you will probably never guess any inadmissible case.


How is a program stored before compiling? When we write code, after compilation the code will be converted to machine language and then stored in the hard disk. But before compiling the code, it is still in the high-level language. How and where is the memory allocated for the source code before compilation?
I assume that before compiling the code is stored in RAM. How is the code stored in RAM? Because I think we can store only machine language in RAM.
If there is any wrong with my question or it is a wrong way of asking, please comment below. It will be helpful.

Here is a brief overview of a typical compilation and execution flow on a Von Neumann machine:

Type in the source code in a plain text editor.
This source code consists of characters. Characters are encoded as bits. An example of encoding is ASCII. These bits are stored on the disk, when you save the source code.
Invoke the compiler to compile the source code. The compiler parses the source code file(s), produces object code and links the object files to produce a machine language file called executable. The executable is stored on the disk.
Run the executable. This is called execution.

At all steps in the process, the operating system controls and co-ordinates processes and does the memory management.

Data is stored in the RAM temporarily when the process running on the machine requires it.

Data is stored on the disk when it needs to be stored permanently.

There is also a process called swapping which is done by the OS when there is no RAM memory left. A section of the disk memory is used for swapping.

There can be multiple processes running on the machine. These processes can run parallely or concurrently. The operating system allocates resources for processes and schedules the processes to run using scheduling algorithms.

This was just a brief overview. To learn more, I highly recommend the free online course on MIT's OCW called Computational Structures.


Do non-computable functions grow asymptotically larger? I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all non-computable functions grow asymptotically larger than computable ones?

Edit:

Great answers below but I would like to explain in plainer english what I understand of them.

If there was a computable function f that grew faster than the busy beaver function, then this means that the busy beaver function is bounded by f. In other words, a turing machine would simply need to run for f(n) many steps to decide the halting problem. Since we know the halting problem is undecidable, our initial presupposition is wrong. Therefore, the busy beaver function grows faster than all computable functions.

If you take any noncomputable set of natural numbers, the characteristic function of the set takes only the values $\{0,1\}$ and is noncomputable. So it is not the case that every noncomputable function grows very quickly, they can even be bounded.

The Busy Beaver function grows more quickly than every computable function because it is constructed to do so. The proof that it is noncomputable proceeds by first proving that it grows faster than any computable function.

More generally, say that a set  $A \subseteq \mathbb{N}$ has "hyperimmune-free degree" if every function computable from $A$ is bounded by a computable function. Certainly every computable set has hyperimmune-free degree. It is known that there are also many noncomputable sets that have hyperimmune-free degree. So it is not the case that everything noncomputable will have to compute some fast-growing function.

However, it is also the case that an r.e. set that is noncomputable will not have hyperimmune-free degree. If $B$ is r.e., and enumerated by index $e$, the function $f$ such that $f(n) = k$ if $e$ enumerates $n$ in $k$ steps, and $f(n) = 0$ if $e$ does not enumerate $n$, is computable from $B$ but this function is bounded by a computable function if and only if $B$ is computable.


Getting ALL negative weight cycles of a graph using Bellman-Ford I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.

After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle canceling algorithm to minimze the flow's cost. I'm basically using the Bellman-Ford algorithm from the sink of the residual graph with the max flow.

The problem is that Bellman-Ford gives me one negative weight cycle (the one that reduces more the cost), and in a given example, such cycle has a bottleneck capacity of 0, so I cannot send flow around it. However in the very same example, other negative weight cycles exist with a bottleneck capacity strictly greater than 0. Sending the bottleneck flow among these cycles would certainly reduce the cost of my assignment, nevertheless the Bellman-Ford implementation does not seem to be capable of yielding such cycles.

How might I get all the graph's negative cycles, to finally get the min cost assignation?

For this university project, the algorithm's performance is not relevant.

You can use a brute force over all sequences of vertices, check if the permutation represents a negative cycle, and if so- print the cycle. This is not an efficient algorithm (runs at $O(n^{n+1})$), but a simple one

Suppose all vertices are denoted by $1,2,\ldots,n$. We denote by $C[i]$ the $i^{th}$ node in the cycle, for $i=1,2,\ldots,k$, where $3 \leq k\leq n-1$ is the size of the cycle.

A pseudo code of the algorithm goes as follows:

Let $k\gets 3$
If $k==n$, then terminate the algorithm.
Let $C[i]\gets 1$ for $i=1,2,\ldots,k$
Check if $C=(C[1],C[2],\ldots,C[k],C[1])$ is a negative cycle in the graph. If so- print $C$
If $C[1]=C[2]=\ldots=C[k]=n$, then $k \gets k+1$ and go to step 2.
Otherwise, select $C[j]=\min_i C[i]$ (if there are multiple $j$-s with the minimal value, select the one with the minimal index), assign  $C[j]\gets C[j]+1$ and go to step 4.


Why are there no complete problems for NP ∩ coNP? The fact that PPAD is a subclass of TFNP seems to be taken as evidence that PPAD cannot be shown complete (or hard) for classes of independent interest like NP ∩ coNP. Slightly confusing, it even seems to excuse that it has not yet been shown complete for PPA, in which it is contained and which has complete problems.

A hint why this is expected is given at the end of Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989):

  Finally can we hope to have TFNP complete problems? As with other classes  (such as NP ∩ coNP, R, BPP etc.) whose machine based definition is semantic instead of syntactic (i.e., depends on a property that the machine exhibits when computing on any input), we do not expect such problems to exist.

I had a similar experience with R (or rather RP) that I started to settle for completeness of smaller classes, until I suddenly realized that the lower end (first the compressed word problem for monoids, then the compressed word problem for free groups) was actually P-complete, i.e. I had wrongly believed that those would be hard problems.

How valid are such excuses really for failing to show completeness (or hardness) of "believed to be difficult" problems with respect to complexity classes of independent interest?

It is still open whether $\mathrm{NP\cap coNP=QP}$, where $\mathrm{QP=\cup_k2^{log^k(n)}}$.
And in this answer, we have shown that $\mathrm{QP}$ has no complete problem.
If now someone shows that $\mathrm{NP\cap coNP}$ has some complete problem, that would imply $\mathrm{NP\cap coNP\neq QP}$.


Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course be an exponential slowdown.  However, what penalty can one expect in terms of space resources?  Unless one has access to an $RNG$, presumably one has to keep track of which configurations one has already tried?  Can we simulate the $NDTM$ with the $DTM$ using only polynomially more space?

Savitch's theorem shows that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2)$.


What is the time complexity of it? I can calculate the time complexity of the following loop:

for (int i = 1; i < n; i++)

The time complexity of it is $O(n)$.

but I can't calculate the time complexity of the next two loops.

I can't find any hints.

for (int i = 0; i < n; i+= 2)

for (int j = 1; j < n; j*= 2)

Its hard to tell what the "complexity" of a loop without knowing what each iteration performs, but what we can do is count how many times each loop iterates:

  for (int i = 1; i < n; i++)

You correctly stated this loop iterates $n$ times.

  for (int i = 0; i < n; i+= 2)

The above loop iterates until $i \geq n$, or in other words, $k$ times, when $i+2k = n \rightarrow 0+2k = n$ (since you initiate $i=0$ and increment it by $2$). Solve the trivial equation, and you get $k=\frac{n}{2}$, which is $O(n)$ iterations.

  for (int j = 1; j < n; j*= 2)

Same as the second time, we must solve $2^k = n$, since you multiply $j=1$ by $2$ each iteration. Solve and get $k=\log(n)$


Class P is closed under rotation? Is the complexity class $P$ closed under rotation, where rotation is defined as $\text{rot}(L) = \{ wv \mid vw \in L \}$?  How would we prove it?

Yes. Suppose that $L \in P$, then $x \in rot(L)$ if and only if there exist $u,v$ such that $x = uv$ and $vu \in L$.

A simple polynomial time algorithm for deciding membership in $rot(L)$ is: given the input $x =x_1 x_2 ... x_n$ generate the $n$ rotated strings $x_1 x_2 .. x_n,\, x_2 x_3 .. x_n x_1,\ldots, x_n x_1 .. x_{n-1}$ and check
in polynomial time whether at least one of them belongs to $L$; in that case accept ($x \in rot(L)$) otherwise reject ($x \notin rot(L)$).


$PSPACE$ not equal $DSPACE(2^n) $ It seems pretty obvious that $PSPACE$ is not equal to $DSPACE(2^n) $. Can this be shown using the space hierarchy theorem? Is that the most simple and straight-forward way?

Can this be shown using the space hierarchy theorem?

Yes. By the space hierarchy theorem, there is a language $L\in\mathrm{DSPACE}(2^n)$ that is not in $\mathrm{DSPACE}(f(n))$ for any $f=o(2^n)$.  In particular, this language is not in $\mathrm{DSPACE}(n^k)$ for any $k$, so it is not in $\mathrm{PSPACE}$.

  Is that the most simple and straight-forward way?

It's hard to imagine anything simpler!


Sliding window protocol, calculation of sequence number bits I am preparing for my exams and was solving problems regarding Sliding Window Protocol and I came across these questions..

  A 1000km long cable operates a 1MBPS. Propagation delay is 10 microsec/km. If frame size is 1kB, then how many bits are required for sequence number?
  A) 3 B) 4 C) 5 D) 6

I got the ans as C option as follows,

propagation time is 10 microsec/km
so, for 1000 km it is 10*1000 microsec, ie 10 milisec
then RTT will be 20 milisec

in 10^3 milisec 8*10^6 bits
so, in 20 milisec X bits;

X = 20*(8*10^6)/10^3 = 160*10^3 bits

now, 1 frame is of size 1kB ie 8000 bits
so total number of frames will be 20. this will be a window size.

hence, to represent 20 frames uniquely we need 5 bits.

the ans was correct as per the answer key.. and then I came across this one..

  Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is
  25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

  What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly?
  Assume that no time gap needs to be given between transmission of two frames.

  (A) l=2 (B) l=3 (C) l=4 (D) l=5

as per the earlier one I solved this one like follows,

propagation time is 25 ms
then RTT will be 50 ms

in 10^3 ms 10^6 bits
so, in 50 ms X bits;

X = 50*(10^6)/10^3 = 50*10^3 bits

now, 1 frame is of size 1kb ie 1000 bits
so total number of frames will be 50. this will be a window size.

hence, to represent 50 frames uniquely we need 6 bits.

and 6 is not even in the option. Answer key is using same solution but taking propagation time not RTT. and their answer is 5 bits. I am totally confused, which one is correct?

Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts.

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).
Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

$No.\ of\ frames = \left(25*10^{-3}*10^{6}\right)/10^3 = 25$

Thus, we will need minimum of $5\ bits$ to represent sequence number distinctly.
HTH


Explain better this new inventory for Word Sense Disambiguation My question is about CSI (Coarse Sense Inventory), described in the paper CSI A Coarse Sense Inventory for 85% Word Sense Disambiguation (C Lacerra, M Bevilacqua, T Pasini, R Navigli).

Before the question, let me quickly describe the new CSI using phrases taken from the above paper.

CSI is a "a resource that avoids sense distinctions that are
too ﬁne-grained for WSD, while maintaining a granularity that is still meaningful for the task".

CSI is "obtained by linking WordNet concepts to a new set of 45 labels".

The comparison between WordNet and CSI is given in table 7:

Question: What is a semantically-empty prediction? (The paper doesn't explain well what is a semantically-empty label)

The paper says:

  "we also added the semantically-empty label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster."

I suggest you read that as though it had said

  we also added the label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster.  This label is not associated with one specific semantic meaning; it is a catch-all for the categories that could not be mapped to any of the other labels.


Do all NP complete problem have polynomial verifier? Say we want to factor a large number.

Factoring it is in NP.

Verifying it is definitely in P.

However, how do we know that there is no other factors besides the one we found?

So it seems that verifying it isn't in NP either.

Now I am getting confused with NP definition here. I know that NP includes all P.

But then there is this side definition that NP are problems with polynomial verifier.

Is there a proof that all NP problems have P verifier?

If the answer is true, yes all NP problems and hence all NP complete problems have P verifier, then please tell me the proof.

A problem is in NP if and only if it has a polynomial verifier – that's the definition of NP. All NP-complete problems are in NP – that's part of the definition – and so have a polynomial verifier.

Factoring is not a decision problem, so it neither belongs to NP nor doesn't belong to NP. You can turn Factoring into a decision problem in many ways, for example asking if the $i$th bit of the $j$th factor of $n$ is equal to $b$. In that case a witness will be the list of factors of $n$. We can check that the factors multiply to $n$, and that they are all prime (since primality testing is in polynomial time).

(We are using here the unique factorization theorem, stating that a positive integer can be factored as a product of primes in a unique way. The same property doesn't hold in some more general situations.)

It is suspected that the decision problem corresponding to Factoring is not NP-complete, though it is certainly in NP, as the preceding paragraph shows.


Context-switch between two processes In response to a clock interrupt, the OS saves the PC and user stack pointer
of the currently executing process, and transfers control to the kernel clock
interrupt handler.

Then the clock interrupt handler saves the rest of the registers, as well as other machine state, such as the state of the floating point registers, in the process PCB.

Why these information are saved in 2 separate moments ? And what is the purpose of "PC and user stack pointer" ?

the OS saves the PC and user stack pointer of the currently executing process, and transfers control to the kernel clock interrupt handler.

This is not done by the OS, since the PC is still pointing to the process code. It is the CPU that performs this step, just before jumping to the kernel interrupt handler (hence modifying PC and SP), which can then save the rest of the state in the PCB.

Since the first step is implemented at a lower level (in the CPU hardware / firmware) it should be simple so that the CPU design does not require too much effort.

Saving registers is much simpler (cheap) when done at the assembly (OS) level, which requires less effort to design/code with respect to the CPU level. Hence, usually the CPU is made to save just enough to allow the OS to save the rest.


Finding all pairs of points with no point in between Suppose there are $n$ points $p_1,p_2,\dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If there are $k$ pairs with the described property, design an algorithm with $O(n\log k)$ that uses idea of divide and pruning.

I think if we check all points we can solve this problem, but running time will exceed $O(n\log k)$.
I think for solving this problem we can use projective geometry duality, but I am stuck. Any help would be appreciated.

If you can select $p_j$ in $O(n)$ time such that it's part of the middlemost group of elements with the same color, the following algorithm works. However I haven't found such a prerequisite.
After finding $p_j$ we can do an $O(n)$ scan to find $p_k$, the minimal element $>p_j$ with the opposite color. We can do a similar scan for $p_i$, the maximal element $<p_j$ with the opposite color. Finally we can partition our array in $O(n)$ time into three subarrays, left ($\{\leq p_i\})$, middle (rest, all with same color as $p_j$), and right ($\{\geq p_k\}$).
In an analysis similar to quicksort you can prove that if we recursively apply the above partitioning to the left and right subarrays we end up with a call tree that has height $\log k$ and at each level of the tree we do a combined $O(n)$ operations, thus a total runtime of $O(n \log k)$.
Afterwards (or during) you can simply iterate over each adjacent partition and output the opposite colored pairs (because each partition is uniformly colored).


How to remove cycles from a directed graph by edge contraction? We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A->B and B->A, we replace them by a single vertex. In case of A->B, B->C, C->A we also replace them by one vertex. We replace N vertices when all reachable from each other. Edges leaving a vertex stay as edges leaving the group containing the vertex.
For example,

digraph cyclic {
        rankdir=BT;
01
2->3
3->2
5->2
6->4
8->3
9->4
a->4
a->9
9->a
b->8
b->c
c->b
6->7
7->8
8->6
}

We must obtain

digraph acyclic {
        rankdir=BT;
01
5->23
678->23
678->4
a9->4
bc->678
}

How is algorithm?
Practical application of problem: we have class where method depends from fields and other methods. How decomposite to max number smallest classes? we allow multiple inheritance, inheritance diamond, but not allow cycles.

Since the only way to get rid of a cycle by edge contractions is to contract all the edges of the cycle to result in a single vertex, the vertices of the new graph are the strongly connected components of the original graph. Two vertices have an edge between them if the original components corresponding to these two vertices had such an edge in the same direction.

Strongly connected components can ve found in linear time.


Why are combinators important in lambda calculus? I just recently learned a little about the lambda calculus, from the brief intro in the text Programming Language Pragmatics and this outstanding 4-video sequence from Adam Doupé. Basically I learned the gist of lambda calculus, $\alpha$-conversion and $\beta$-reduction, a bit of Church numerals, addition/subtraction, and the $Y$ combinator.

In this I learned the concept of a combinator, i.e. that it is an abstraction with no free variables. Simple concept. And there seemed to be this idea I kept reading between the lines, that we can/should turn non-combinator abstractions into combinators by wrapping them in abstractions that bind the free variables. For example, we can take the abstraction $(\lambda x. xy)$ and wrap it in $(\lambda y. \lambda x. xy)$ to bind the $y$.

But it was never really explained why it is important or useful to prefer combinators.

I'm assuming its because combinators allow us to easily combine expressions (surprise surprise) without the need of any externally-supplied variables. So in other words we could evaluate an arbitrary-length series of combinator applications without having to provide any initial conditions ahead of time. Which to me sounds like the equivalent in programming of avoiding global variables so as to avoid looking up values outside the current scope, in order to make it easier to understand the program and reduce errors. It also seems to align with the idea of a "pure functional" language that has no variables and no side-effects, which would imply such a language is effectively a series of combinator applications.

Is that correct?

The word "combinator" has some connotations that you don't seem to be intending here and sometimes a stricter definition.  Another term for the definition you gave is a closed term.  The opposite is an open term.  The programming language equivalent of an open term would be an expression referring to a variable that's simply not in scope.  Not just not in the current scope, but not in any containing scopes either.  Most languages simply don't allow this.  We can model let expressions that locally bind a name with lambda abstraction and application. In particular, let x = E in B becomes $(\lambda x.B)E$.  The top-level, or global, scope can then be thought of conceptually as just a short-hand for wrapping your program in a bunch of let expressions.  The point being, even global names are bound.  The analogy to an open term, in this context, would be a term with one or more completely undefined variables in it.

Now clearly a closed term is self-contained which is useful. Further, for the purposes of computation, we never need to consider anything other than closed terms (assuming we start with nothing but closed terms).  More precisely, for computation we usually care about weak (head) normal form which is the normal form for call-by-value(/name) reduction.  An important aspect of these reduction strategies is they never reduce under a lambda.  As such, any instance of $\beta$-reduction using these reduction strategies will only involve closed terms and will only ever produce a closed term assuming the initial term was closed.  So, for the purposes of programming and computation closed terms are all that matters. Optimizing compilers, though, manipulate programs and often do perform reduction under a lambda and as such do need to deal with open terms.  Proof assistants also need to deal with open terms as they usually need to reduce to normal form to compare lambda terms for equality. (Actually, they can often avoid going all the way to normal form.)

The focus on "combinators" isn't driven by software engineering concerns.  It's simply a fact that for many purposes you only need to consider closed terms.  The theory and formal manipulation of open terms is quite a bit hairier than for closed terms, so it is useful to limit to closed terms when possible.


Minimum number of vertices whose removal makes the graph an independent set It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent set of size greater than equal to $k$.

I was looking at the complementary problem - "Whether or not removal of at most $k$ vertices from a graph can make the resulting graph an independent set".

  If the input graph $G$ contains a set $W$ of size at most $k$ for
  which $V(G)\setminus W$ is independent set, then it can be found in
  $2^{O(k \log k)}\cdot n^{O(1)}$ time as follows:

  Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
  There are now only $k^2$ edges in the current graph.
  Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at
  least $(n-2k^2)$.
  So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal
  of which set makes the graph an independent set.

My question is does the new problem has $2^{O(k)}\cdot n^{O(1)}$ time algorithm?

Yes, and the algorithm is straight forward branching.

Suppose that you are given a graph $G$ and an integer $k$.  If $k = 0$, we simply return whether $G$ is an independent set.  If $G$ is an independent set, we return "yes".  Otherwise, we branch.  If there is an edge $uv$ in $G$, we recurse on $G-u, k-1$ and $G-v, k-1$.  Since the budget drops with one for every recursive call, we call ourselves at most $2^k$ times.

The correctness is left as an exercise.


Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array? Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types:

Ascending (e.g., 1,2,4,6);
Descending (e.g., 6,4,2,1);
Ascending rotated (a non-trivial circular shift of an ascending array, e.g., 4,6,1,2);
Descending rotated (a non-trivial circular shift of an descending array, e.g., 4,2,1,6).

The task is to determine the type and the maximum element of $A$.

Since $A$ is "sorted", is there a $O(\log n)$-time approach or is the best possible time complexity $O(n)$, as suggested in the link?

Let $A = \langle a_1, \dots, a_n \rangle$ be the input array.
I will only consider the case $n \ge 3$, otherwise the problem is trivial.

The key property is that the order relation between all but one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$), and "less than" if $A$ is some circular shift of a decreasing array. Examining the first and last elements suffices to determine if the shift is trivial or not.

In practice you can determine the type of $A$ in constant time, as follows:

Look the majority value $x$ among $\textrm{sign}(a_1-a_n)$, $\textrm{sign}(a_2-a_1)$, and $\textrm{sign}(a_3-a_2)$.
If $x = +1$ then $A$ is some circular shift of an increasing array. If $\textrm{sign}(a_1-a_n)=-1$, $A$ is of type "ascending", otherwise it is of type "ascending rotated".
If $x = -1$ then $A$ is some circular shift of a decreasing array. If $\textrm{sign}(a_1-a_n)=1$, $A$ is of type "descending", otherwise it is of type "descending rotated".

As for returning the maximum, I will only discuss the case in which $A$ is a circular shift of an increasing array (the complementary case is handled similarly). Notice that, if the maximum element is in some position $a_j$, then all $a_1, \dots, a_j$ are larger than or equal to $a_1$, while all ements $a_{j+1}, \dots, a_n$ are smaller than $a_1$. This allows you to binary search for the last element that is larger than or equal to $a_1$, i.e., $a_j$.


Why can't linear bounded automata accept an empty string? The linear bounded automata (LBA) is defined as follows:

  A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that $\Sigma$ must contain two symbols $[$ and $]$, such that $\delta(q_i,[)$ can contain only elements of the form $(q_j,[,R)$ and $\delta(q_i,])$ can contain only elements of the form $(q_j,],L)$

Informally this can be interpreted as follows:

  In linear bounded automata, we allow the Turing machine to use only that part of the tape occupied by the input. The input can be envisioned as bracketed by left end marker $[$ and right end marker $]$. The end markers cannot be rewritten, and RW head cannot move to the left of $[$ or to the right of $]$.

Now I read that context sensitive grammar imitates the function of LBA and is defined as follows:

  A grammar is CSG if all productions in context sensitive grammar takes form
  $$x\rightarrow y,$$
  where $x,y\in(V\cup T)^+$ and $|x|\leq|y|$

Now people say that CSG cannot contain lambda or empty production (which takes form: $x\rightarrow \lambda$) as it will make make it impossible to meet the requirement $|x|\leq|y|$ and this can be understood.

However, what I don't understand is how informal interpretation of the working of LBA given above explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?

Linear-bounded automata are able to accept the empty string. The equivalence between linear-bounded automata and context-sensitive grammars needs to be cognizant of this discrepancy between the two models. Usually a context-sensitive grammar is allowed one extra product to optionally produce the empty string. Alternatively, there is an equivalence between LBAs not accepting the empty string and CSGs.


Comparison between IDA* and Recursive best first search How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity?

Both algorithms are intended to be memory-efficient heuristic search algorithms.  From my understanding, RBFS just updates the $F(n)$ value for the parent node for which the current execution was stopped in comparison to IDA*, so it avoids redundant computation to a certain extent, but I'm not sure what exactly this means for the number of nodes expanded or its space complexity.

My main motive of this question was to identify all possible reasons that led to development of RBFS (which can be considered as a successor of IDA*).

Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. Artificial Intelligence, 62 (41--78), 1993. In fact, RBFS is much more than "just updating the $F(n)$ value for the parent for which the current execution was stopped". RBFS stores the so-called stored $f$-value of each node $n$ as $F(n)$. An invariant of the algorithm is that the stored $f$-value is the minimum static $f$-value (ie., the usual $f(n)=g(n)+h(n)$) among all leave nodes generated in a tree rooted at $n$. From here, $F(n)\geq f(n)$ for all nodes $n$ given that costs are monotonic. Initially, when a node is expanded for the first time $F(n)=f(n)$. Later on, when backtracking after examining its descendants, its $F$-value (ie., the stored $f$-value) is accordingly updated.

So, if nodes beneath node $n$ are examined, up to what point are they developed? Another parameter used in RBFS is an upper bound $B$ which is initially set to $+\infty$. Do not read $B$ as a global upper bound! Indeed, every time a node is selected for expansion, $B$ is updated to the minimum between the current value of $B$ and the second-best $F$-value. So here you are a second invariant of RBFS: every time a node is selected for expansion, it has an $f$-value which is less or equal than the second best $f$-value in the whole search tree. This is true: first, because $B$ is updated using the second-best $F$-value which amounts to compare it with all the descendants of its siblings; second, the other component used is $B$ itself which was, in turn, computed in the same way by its ancestors. Finally, remember that after every expansion, nodes are sorted in increasing order of their $F$-value.

As a result, RBFS expands nodes in the same order of A*! So far, I do not see it as a successor of IDA*, but instead, as a new member of the large family of best-first search algorithms. Note that in the preceding statement I solely refer to the new expansions. There will be often in between an arbitrarily large number of re-expansions.

For a more didactical explanation of the algorithm refer to the paper Ariel Felner. The Collapse Macro in Best-First Search Algorithms and and Iterative Variant of RBFS. Symposium on Combinatorial Search (SoCS 2015), 28--34. Israel, 2015. During his dissertation Ariel openly said that this is an algorithm poorly understood in general and there was agreement. Conclusion: read this paper also if you are interested in understanding RBFS (I do sincerely doubt that my review suffices for a good understanding of the algorithm).

Regarding your questions:

Note that in the first paragraph I expliclty refered to backtracking ie, RBFS is implemented as a depth-first search algorithm. So far, its memory requirements are $O(bd)$ where $b$ is the branching factor and $d$ is the depth where the solution lies.
Assuming that the expansion of every node is the dominant operation and that it takes the same amount of time in spite of the node been expanded, then the number of expansions directly relates to the time complexity. Korf proved that, in the general case, the time complexity is (as one would expect) $O(bˆd)$ where $b$ is the asymptotic branching factor. Also, the best and worst case analysis are analyzed by Korf in the original paper.

As you mentioned the relationship with IDA* let me also remark that Korf proved that RBFS expands less nodes (in total, considering also re-expansions) than IDA* in the average-case in case of monotonic costs. If costs do not grow monotonically then these algorithms cannot be compared as they traverse entirely different search trees. Since IDA* is known to be asymptotically optimal, then RBFS is asymptotically optimal as well.

Hope this helps,


Is this intersection of DFAs correct? I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\{0,1\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then combined:

Is the given procedure for combining DFAs correct?
EDIT: Originally wrote union; actually taking the intersection.
Would someone suggest material on constructing DFAs
given restrictions on length and number of $0$s or $1$s?

According to link given by Merbs, I have developed this FA.   This FA does not accept a language of even length.

Yes, this is called the Product Constuction - given DFAs $M_1$ and $M_2$, we can construct $M=M_1\times M_2$:

$M$ consists of pairs of states from its constituent DFAs, so if the original DFAs
have states $A,B,C$ and $x,y,z$, the product would be $\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\}$.
The transition function is updated such that if on a particular step, a string would cause $M_1$ to transition from state $A$ to $B$ and $M_2$ to transition from $x$ to $y$, then the product would transition from $Ax$ to $By$
The initial state is the pair consisting of the initial states of the constituent DFAs (i.e. $Ax$).
If we are constructing the DFA that determines whether both of
the two constituent DFAs would accept the string, then the accept
states of $M$ is the intersection (those pairs made up of accept states from both).
If we are constructing the DFA that determines whether either of the two
constituent DFAs would accept the string, then the accept states of
$M$ is the union  (those pairs made up of accept states from either).
In your example, $x_1$ and $y_0$ are the accept states of $M_1$ and $M_2$; the intersection would be $\{x_1y_0\}$ while the union would be $\{x_1y_0,x_1y_1,x_0y_0\}$.

I’ve included some other DFAs regarding restrictions on length for reference.


Implementing reliable pairwise average in distributed systems Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p_val and q_val are the values of p and q respectively). p and q want to compute the average of their values and change their values to the average. If one node changes its value to the average, the other node should change as well. This problem is called distributed reliable pairwise average.

  Question: Is it possible to implement distributed reliable pairwise average? or it is impossible?

I think that it is impossible. Please consider the following simple protocol:

Each node sends its value to the other node.
Each node after receiving the value of the other node changes its value to the average.

Suppose that p receives q_val but q doesn't receive p_val due to occurring a link-failure, so if p changes its value to the average, it is not correct. It seems that they need to send acknowledgments. If they start to send acknowledgments, they enter an endless loop.

Full reliability is simply not possible in (distributed) systems; at some point of fractional system failure you reach a level where system state and/or data is no longer recoverable. You should consider that this is dependent not only on node failure, but also on data distortion (bits might flip as they travel across the network, etc.). As a result, you can reach very high levels of certainty about correctness but it's very difficult if not impossible to guarantee it.

One of the most well known examples of this is the Byzantine Generals/Byzantine Fault problem, which deals with consensus in networks (https://en.wikipedia.org/wiki/Byzantine_fault).


Integrality gap and LP-rounding I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:

$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
then, does it have sense to do an approximation-algorithm with LP-rounding?
I mean, by definition of $\alpha$-approximation, I know that this is true for an algorithm, in case of minimization problem, that:

$$\mathrm{SOL} \le \alpha \mathrm{OPT}.$$

But since I want to do an approximation with LP-rounding, isn't $\mathrm{SOL}$ equal to  $\mathrm{OPT}(\mathrm{ILP})$?  This will mean that $\alpha = 1$ (?).

So, if I can design an approximation-algorithm for this given problem, what is the best approximation factor that I can get, given there is no integrality gap?

For first question: No, it doesn't make sense. If there is no ratio between OPT(ILP) and OPT(LP-relax) (i.e. integrality gap is 1) which is very rarely to happen (only happen with problem that is in $P$), then this means that you reach the optimal solution for this problem. It is known that LP-relax cannot give the optimal solution for a problem (except for problems in P as I said), and this is why we define integrality gap to see how far it from the optimal solution of the problem (or optimal solution of the ILP).

For second question: Yes, it is true, $\alpha = 1$.

For third question: if you design an approximation algorithm for a given a problem, then I believe you are talking about problem that lies in NP-hard. Then the best factor you hope for max/min problem is 1 (Note that max problem has ratios between [0-1], whereas min problem has ratios between [1,$\infty$)). In reality, all NP-hard problems cannot get a polynomial approximation algorithm with ratio 1 unless P=NP "since ratio 1-approximation algorithm is the same as exact algorithm". So, it should be closer to 1 for both max/min problems but not equal 1.


Why does a Turing Machine need at least two states? I read in some text book ( either ullman or peter linz) that a turing machine must have at least two states. I don't understand why?

For example if we want to build a Turing Machine for the empty language then we can start in state $q_o$ (accept state). We will define only one transition for epsilon on which the input would be accepted. However if the input is something else then since we have not defined any transition we would enter dead configuration.

what's the problem with this approach?

TL;DR: technically, there need to be an accepting and rejecting state and they need to be different; but it's not a big deal and, at an intuitive level, one-state machines work just gine.

A Turing machine is typically defined to be a tuple $M=\langle Q, \Sigma, \Gamma, \delta, q_0, q_\mathrm{acc}, q_\mathrm{rej}\rangle$ where the items are the state set, input and tape alphabets, the transition function (or relation for a nondeterministic machine), and the initial, accepting and rejecting states, respectively.

The accepting and rejecting states must be distinct because the machine cannot simultaneously accept and reject. Therefore, there must be at least two states.

In principle, you might want to define a Turing machine that has only one state: the initial state would be the accepting state and there'd be no rejecting state, or vice-versa. There's nothing morally wrong with that but it would make the definition more complicated.  Instead of saying "A Turing machine has distinct accepting and rejecting states", you'd have to say "A Turing machine either has distinct accepting and rejecting states, or it has just one state which is either the accepting state or the rejecting state." That's more complex, and it doesn't buy you anything, so people don't do it.

But note that this isn't really an important point. You can perfectly well think of Turing machines with just one state and it won't hurt you in any way, unless you try to write down a formal definition. Any machine that you want to think of as having one state, you can easily rewrite as having two states: just add the second state, which will be inaccessible.


Routing algorithm for train network I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges represent the time taken to travel from one station to another.

For any particular vertex, there might be multiple edges going from that vertex to another (as there could be, for example, a scheduled service that departs from A to B hourly each day - meaning 24 journies in a day and 24 edges between the two vertices for this one journey).

In terms of my analysis, I want to be able to find the shortest path from all stations to all other stations. I can then use algorithms such as BetweennessCentrality on the resultant data to find the most "important" vertices. This type of analysis obviously lends itself to using Dijkstra’s algorithm to find the shortest paths.

However, using Dijkstra’s algorithm will mean that real-life constraints are ignored. For example, Dijkstra’s algorithm won’t take into consideration you can’t set off from station A at 10:00, arrive at B at 10:30 and then take a train from B to C at 8:00 (you are not a time traveller!).

Dijkstra's algorithm also won't take into account time spent waiting in a station for a train to arrive in a situation where a passenger would have to change trains.

I have looked into modifying Dijkstra's algorithm to take these factors into account but as these factors change on a case by case basis you are unable to apply them to the network as a whole.

The ConnectionScanAlgorithm does take real-life constraints into account and scans through a network’s nodes and edges with a given start and end node in mind (I believe this is how train ticket websites find a quickest route).

However, since I need the routes from all stations to all other stations, to make use of the ConnectionScanAlgorithm I have to pass through every combination of station pairings (for me, this is some 36 million combinations) which is far too time expensive.

Are there any algorithms out there which are applicable to this problem?

If not, what is the best way to go about forming a solution?

Here is a list of algorithms might help you:

RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal unlike CSA.
Connection Scan Algorithm: This is a fast algorithm that doesn't need heavy preprocessing.
Trip-Based Public Transit Routing: requires more preprocessing compared to CSA and RAPTOR
Transfer Patterns

You might also wanna look at OpenTripPlanner algorithms bibliography


Is the tree shown a valid red-black tree? I have made a red-black tree and I think that it is not valid. Could someone please verify?

As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes and these NULL nodes are considered to be black.
So, by this logic, if we consider the order root->left->left->left as black, then no. of black nodes to that NULL node are 2.
Also, if we consider the node root->right->right->right->right->right as black, then no of black nodes to that NULL node are 3.
So, according to the above argument, it should not be a valid red-black tree.
Am I right or am I missing some important concept?

You are correct $-$ the red-black tree you have drawn is not balanced.

For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed.

However for your tree, the path 00 results in a black height of $2$ and the path 1000 results in a black height of $3$. 0 = go left, 1 = go right.


What techniques could be used to support thread-local contexts and resources in a language? I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used.

Quite often in programming - especially if you are implementing a solution that repeatedly processes similar inputs - it is useful to have access to a thread-local context.

I am sure many are familiar with this problem: the typical case I am taking about is where you have a processing engine taking input messages/requests (e.g., an MDB or a Servlet in Java) that is instantiated individually for several threads, and this engine repeatedly processes the messages using some resources or context that it owns. These resources could be expensive to recreate (and therefore we would like to reuse them), or alternatively, they need to be retained across requests in the thread, but do not need global scope in the application.

In this case, code needs to be able to access that context in an efficient way, but due to the stack+heap-based approach of most languages this is difficult. The current solutions are to either use something like ThreadLocal in Java or to pass a pointer to the context down the stack, both which are not really language constructs, and both of which impose some overhead (and in the second case have practical issues).

It occurs to me that such a thread context is a bit like a second stack. A stack has thread scope and can be efficiently accessed by the thread.

Possibly solutions to implement this in-language might be to maintain the context at the base of the stack; however, this would have to be a fixed size. For a variable sized context, a reference could be stored at the base, but with some loss of efficiency for minimalist requirements. Other options might be possible if the hardware supported multiple stacks per thread.

As a trivial example of what I mean to illustrate the performance impact of existing solutions would be to imagine each "engine" receives a message and then increments a counter (counting the number of messages processed per for each thread). Using ThreadLocal would be many times less efficient that simply incrementing the contents of a known memory address. Even a global counter would require some synchronization and therefore would create a choke point.

A more practical example would be the maintenance of a resource pool such as an object pool where expensive-to-create objects or buffers can be re-used across invocations.

To be clear: this is not really a multi-threading issue, so solutions such as semaphores, etc. are not the solution - on the contrary, they are part of the problem.

A thread-local resource does not need to be shared between threads. It is local, so any solution adding the overhead of synchronization is adding an unnecessary performance penalty.

It would be interesting to know how this might be done (or if it has been done already), with particular consideration to the hardware support available to make it efficient.

One example of a language system built from bottom up to support this kind of situation is Erlang. It is well worth looking into.

It is built around the concept that you create a lot of tasks. The tasks never share variables and only communicates via messages. The task has a "thread-local" context which is maintained using a very specific construct of tail-recursion. It is not uncommon to have thousands or even millions of task in a Erlang system.

Erlang comes with a set of constructs and tools known as OTP which helps in handling a number of common situation in soft real time systems. I especially like how it allows you to update the programs in a running system on the fly.


Floyd–Warshall algorithm on undirected graph I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm.

In case of undirected graphs should I change the assignment statement inside the if condition to

dist[i][j] = dist[j][i] = dist[i][k] + dist[k][j]

or they are equivalent?

Every undirected graph can be represented as directed graph by replacing every edge $(i,j)$ with 2 edges $(i,j); (j,i)$. And if you're running Floyd–Warshall algorithm on such directed graph - it would work correctly, as always.


Language Containment of Automata If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?

I will guide you through it, giving you the most important ideas. Yet, I will leave the details for you, many details actually. For two languages $A, B$, it holds that $A\subseteq B$ iff $A\cap\overline{B} = \emptyset$. This is an easy exercise and I leave it to you. Now given two automata $C_1$ and $C_2$, we can check whether $L(C_1)\subseteq L(C_2)$ by checking the emptiness of $L(C_1)\cap \overline{L(C_2)}$. In general, constructing an automaton for the intersection of two automata is easy, regardless of whether the automata are DFAs or NFAs (by easy I mean it can be done in time polynomial in the two automata): indeed, one can show that the product construction of automata can be generalised to NFAs. So, given two NFAs, one can build an NFA over their product to recognise their intersection. Then, to check whether the product automaton is empty, we can simply check if there is a path from an initial state to an accepting state in the product - which can be done in time polynomial in the size of the product automaton (polynomial in the size of the automata that we're intersecting). So, to solve the above problem, one can do the following.
Given automata $C_1$ and $C_2$, construct an automaton for $D = \overline{L(C_2)}$, then construct a product automaton $E$ for $L(C_1)\cap L(D)$, and finally check whether $L(E)$ is empty - which takes time polynomial in $|E| = |C_1|\cdot |D|$. So the complexity depends on the size of $C_1$, and on the size of $D$ which recognizes $\overline{L(C_2)}$. So $|E|$ is polynomial in the sizes of $C_1$ and $C_2$ iff $|D|$ is polynomial in them. To sum up:

If $C_1$ is an NFA and $C_2$ is a DFA, then $D$ is obtained from $C_2$ by flipping accepting and rejecting states. So $|D| = |C_2|$, and thus solving the problem takes time polynomial in $|C_1|\cdot |C_2|$. Hence, the problem in this case is in P.

If $C_1$ is a DFA and $C_2$ is an NFA, then $D$ is obtained from $C_2$ by applying the subset construction. So $|D| = 2^{|C_2|}$, and thus solving the problem takes time polynomial in $|C_1|\cdot 2^{|C_2|}$, which is exponential. Hence, the problem in this case is in EXPTIME. In fact, it can be shown that the problem is in PSPACE. Idea: we do not need to construct the whole product automaton, and then find a path in it. Instead, we can find this path nondeterministically on the fly in polynomial space (use the fact that PSPACE = NPSPACE, and the fact that given a state in the product, you can compute its successor states if you have the description of $C_1$, and $C_2$. Once you guess a successor state, you can remove the current state. This way, you do not need to construct the whole product, you only store the current state in the guessed path). I left out some important small details to you. Also, you can show that the problem in this case is PSPACE-hard by reducing the NFA-universality problem to it. Indeed, given an NFA $A$, a reduction outputs $C_1, C_2$, where $C_1$ is a DFA that accepts all words, and $C_2 = A$. Clearly, $L(A) = \Sigma^*$ iff $L(C_1)\subseteq L(C_2) = L(A)$. Thus, PSPACE-hardness follows.


Chazelle's discrepancy book: greedy method In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem 1) is obtained by a simple probability argument.  Unfortunately, I fail to follow the intended argument.  Could someone enlighten me?

Here $\chi(S_i) = \sum_{v\in S_i} \chi(v)$ is the discrepancy of the set $S_i$ with respect to a function $\chi$ that assigns weights to each element.

  Given a set system $(V,S)$, with $|V| = n$ and $|S| = m$, pick a random coloring $\chi$, meaning that for each $v_j$, the "color" $\chi(v_j)$ is chosen randomly, uniformly, and independently, in $\{-1,1\}$.  We say that $S_i$ is bad if $|\chi(S_i)| > \sqrt{2|S_i|\ln (2m)}$.  By Chernoff's bound, we immediately derive
  $$Pr[S_i \text{ is bad}] < \frac{1}{m};$$

and now the bit I don't follow:

  therefore, with nonzero probability, no $S_i$ is bad.

Clearly this holds if the $m$ events "$S_i$ is not bad" are mutually independent.  It also holds by a form of the Lovász Local Lemma if these events form the edges of a hypergraph (with $V$ as vertices) that is "nice enough".  But I don't see why this is immediately apparent in every case, as the author seems to imply.  If the $n$ individual values $\chi(v_j)$ are iid, then I simply don't see that the $m$ events "$S_i$ is not bad" are necessarily of a nice enough form to use the probabilistic method, and they certainly don't seem to be iid.

What am I missing?

Any counterexample must be rather large (with the size of $m$ exponential in $|S_i|$), so I provisionally do believe the statement.  But I would like a convincing proof, or a pointer to another reference.

My oversight was that $|S| = m$, so there are $m$ events of the form "$S_i$ is bad".  Then since $Pr[\cup_{i=1}^m A_i] \le \sum_{i=1}^m Pr[A_i]$ for any collection of events $\{A_i \mid i=1,2,\dots,m\}$, it follows that $Pr[\text{some }S_i\text{ is bad}] < 1$, so $Pr[\text{no }S_i\text{ is bad}] > 0$.


Select K columns from matrix and one element from each row that has maximum sum Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each row and calculate sum - S. Task is to find such K columns, so that this sum S will be maximum for given matrix N x M and value K.

Example:

K: 2
Matrix:
\begin{bmatrix}1&2&3&4\\4&3&2&1\\3&1&4&5\end{bmatrix}

Select column 1 and 4:
\begin{bmatrix}1&4\\4&1\\3&5\end{bmatrix}

Select maximum values from rows:
\begin{bmatrix}4\\4\\5\end{bmatrix}

We got sum 13, this is maximum sum for given matrix and for given K.

It looks similar weighted assignment problem or weighted bipartite matching, but I don't know how to reduce this task to them.

Thank you!

There is trivial reduction from set cover. Consider 0-1 matrix where columns are subsets, rows are set elements and 1 means that subset contains element. Algorithm for your problem then can find K subsets to cover (sum max elements to n) set.

So your problem is NP-hard, no chances.


Matrix for modular exponentiation in Shor's algorithm I'm trying to simulate Shor's algorithm with a model using vectors for quantum registers and matrices for quantum gates, however I'm stuck at the modular exponentiation bit of Shor's algorithm, having no idea how to build the corresponding matrix (unlike Hadamard and QFT). How can I build said matrix?

Note that Shor's algorithm doesn't require modular exponentiation. All you need is (controlled) modular multiplication.

There are two steps to getting the matrix for modular multiplication:

Write a function to turn any permutation into a matrix.
Apply it to the permutation $a \rightarrow a \cdot k \pmod{r}$.
(Optional) Instead of making that matrix and multiplying by it, save massive execution time by just applying the permutation directly.

For step 1, just have a function like this:

import numpy as np

def make_permutation_matrix(n, permutation):
    r = np.zeros((n, n))
    for i in range(n):
        r[permutation(i), i] = 1
    return r

Then for step 2, use it:

import math
k = pow(base, exponent, modulus)
n = math.ceil(math.log(modulus, 2))
mul_matrix = make_permutation_matrix(
    2**n,
    permutation=lambda x: x*k % modulus)


IP addresses and Subdomains? If a school has an IP that's like 10.0.x.x, and a department in that school has it's own site that's an extension of the school's site, does that department's IP just change the last two numbers in the IP?
Does the school have to purchase extra domain space?
Could I have additional addresses established at my IP address, just by changing the last numbers?
Am I completely wrong with my idea of IP numbers?

As we are talking about IPv4 addresses here, you have to consider two things:

Usually, your Internet Service Provider (ISP) will assign you one IPv4 address. This can either be changing (the common case for private households) or static. However, there is usually one IP address at a time that you can be reached from the outside of your network.
Internally, you can organize your network independent from those policy. For this purpose, some standard IP ranges like 192.168.*.* and 10.*.*.* are reserved to be used arbitrarily by the local network administrator.

Hence, it is up to the network administrator how the additional department is included in the school's local address space.

Generally, you want to talk of different loosely coupled networks in terms of subnets. To determine a certain subnet, you specify a subnet mask, which fixes the first $n$ bits of an IP address as "the network's address".

So, the admin would assign the additional department a "network address" of, e.g., 10.0.54.0/24. This means, the first 24 bits of this IP identify the network and everything after the 24th bit can be assigned arbitrarily to the devices of that network. In this particular example, any device with an IP address between 10.0.54.1 and 10.0.54.254 would be logically seen as part of the network 10.0.54.0/24.

Assuming that the whole school is connected to some kind of router (which uses NAT to "translate" the local IP addresses to the global IP address assigned by the ISP, roughly speaking), it is then up to the router configuration whether the department is reachable directly. This router will most likely run a web server or delegate http requests to a device of the network that runs a web server. Based on the configuration of this delegation or request processing, you can instruct the router to delegate any request to, e.g., department.myschool.com to the web server of the department and then you are fine.

However, you have to have a top level domain for this, even with a wildcard contract such that every request to *.myschool.com is forwarded to your school's router, that then can decide to forward requests to department.myschool.com accordingly.
Another way to have this flexibility would to use different ports for different web servers in your local network. But this would burden anyone who is interested in your department's website to guess or somehow know the port your web server is listening to.


Matrix of a graph and computational complexity Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ otherwise.
Now, suppose we define a special kind of matrix product for matrices whose entries are only 0 or 1. In this special matrix product we replace addition by OR and multiplication by AND. With this being our definition of the matrix product answer the following questions:

If $B_2 = (A+I)^2$ then argue that $B_2 = C_2 +I$ where $C_2$ is the adjacency matrix of the graph $G′ = (V,E′)$ with the same vertex set as $G$. We say that $(i,j) ∈ E′$ if $(i,j) ∈ E$ or there exists a $k ∈ V$ such that $(i,k),(k,j) ∈ E$.
Is it possible to compute $C_2$ (by some other way perhaps) in time which is $o(n^2)$? Or is there some example on which the time taken to compute $C_2$ has to be $Ω(n^2)$? Cause I think that in this case the time taken would be $θ(n^2)$

I tried manipulating $B_2$ and then applying the new matrix product properties, but I wasn't able to give a concrete argument about $C_2$. As far as the complexity goes, I have no idea on how to go about with it. Any help is appreciated. Thanks!

Let $B_1 = I + A$. Then $B_1(i,j) = 1$ iff $d(i,j) \leq 1$, where $d(i,j)$ is the distance between $i$ and $j$ in the graph. Now $B_2 = B_1^2$, and so by definition,
$$
(B_2)_{ij} = \bigvee_k (B_1)_{ik} \land (B_1)_{kj}.
$$
In words, $(B_2)_{ij} = 1$ iff there exists a vertex $k$ such that $(B_1)_{ik} = (B_1)_{kj} = 1$, i.e. $d(i,k) \leq 1$ and $d(k,j) \leq 1$.

We can now prove that $(B_2)_{ij} = 1$ iff $d(i,j) \leq 2$. Indeed, if $(B_2)_{ij} = 1$ then there exists $k$ such that $d(i,k),d(k,j) \leq 1$, and so $d(i,j) \leq d(i,k) + d(k,j) \leq 2$. Conversely, suppose that $d(i,j) \leq 2$. We consider two cases. If $d(i,j) \leq 1$ then $k := j$ satisfies $d(i,k) \leq 1$ and $d(k,j) = 0 \leq 1$, and so $(B_2)_{ij} = 1$. If $d(i,j) = 2$, choose a shortest path from $i$ to $j$, and let $k$ be the vertex in the middle. Then $d(i,k) = d(k,j) = 1$. In both cases, $(B_2)_{ij} = 1$.

You cannot compute $C_2$ faster than $n^2$, simply because it contains $n^2$ many entries. The asymptotically fastest way known to compute $C_2$ is by squaring $I + A$ (using the usual matrix multiplication), zeroing the diagonal, and replacing each entry larger than 1 with 1. This takes time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.


Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$ The proof is in the image below, taken from "Quantum Computing Since Democritus":

Here's what I don't totally get: my understanding of random algorithms is that randomization is not done over the input space; the inputs are still worst case. So that when a random algorithm has some error, what I interpret that to mean is that given any input string to the algorithm, there is at most such-and-such probability of outputting a wrong answer.
If I take the same string $s$ and run it through the random algorithm with error rate $e<1$ an $n$ amount of times, I should expect $ne$ wrong answers.
I haven't been able to reconcile the above with the technique used in the linked proof; in particular, the jump from $2^{-n^2}$ being the error rate of the BPP algorithm to saying that a $2^{-n^2}$ fraction of random strings cause us to err. If someone could explain this proof a little more verbosely I think I'd find that very helpful.

What he here means by a "random string" is not an element of the input space, but rather a string of random choices, i.e. a series of coin flips that have been taken while executing the randomized algorithm. If you enumerated every possible such series of coin flips, you would see that at most a $2^{-n^2}$ fraction of them would lead the algorithm to conclude with the wrong answer.