Nearest neighbour based on subjective human comparison - is this a thing? I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into...

I have a collection of items that I would like to have a human subjectively compare such that I can derive some consistent dataset that can be queried for k nearest neighbours for a given item that is present in the data.

i.e. if I ask a human, given item A, which item is most similar, B or C (repeated over a set of such items)

I can later present back, when queried, here are the items most similar to A.

The desire is simply to record a person's subjective comparisons of a set of items and have a means to allow them to query it.

Any pointers as to algorithms or structures to read up on would be greatly appreciated.

Distance metric learning

It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items.  If the human tells you that A is more similar to B than to C, then you learn that $D(A,B) < D(A,C)$ (probably).  Based on many instances of this, you can learn a distance metric $D(\cdot,\cdot)$.  Then, you can use $k$-nearest neighbors with this distance metric.

Overview

How does distance metric learning work?  Well, you can do a search and you'll find a lot of material.  Basically, you identify some features that you think might be relevant.  So, let $f(A)$ denote the feature vector associated to $A$.  Then you want to learn a distance metric of the form

$$D(A,B) = d(f(A),f(B))$$

where $d : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ is the distance function that you want to learn.  There are various methods for this.  In one of them, we assume that $d$ takes the form

$$d(x,y) = (x-y)^\top A (x-y)$$

where $A$ is some positive semidefinite matrix that is to be learned.  The training set gives us comparisons of the form $d(x_A,x_B) < d(x_A,x_C)$, i.e.,

$$(x_A-x_B)^\top A (x_A-x_B) < (x_A-x_C)^\top A (x_A-x_C).$$

You could then form a convex optimization problem of the form

minimize $||A||_F$

subject to $A \succeq 0$ and $(x_A-x_C)^\top A (x_A-x_C) < (x_A-x_B)^\top A (x_A-x_B)$ for all $x_A,x_B,x_C$ in the training set.

Here $||A||_F$ is the Frobenius norm.  Also $A \succeq 0$ means that $A$ is positive semidefinite).  (This can be expressed by writing $A=M^\top M$ and using the entries of $M$ as your unknowns, though sometimes it is easier to leave it in the form $A$.)  Then we apply some algorithm for convex optimization to learn $A$ or $M$.

That's one example of a method; there are many others.  For instance, you might add a margin to the inequality above, and require that $d(x_A,x_B) < d(x_A,x_C)-1$ (so they are well-separated).

The effectiveness will be partly determined both by the metric learning method you use, but the set of features you come up with are also extremely important.  You'll want to use your domain knowledge about what attributes of items might be relevant or helpful in determining similarity.  If you have good features,  you'll probably find that distance metric learning is more effective.

To learn more

There are many schemes for distance metric learning.  A websearch and a search on Google Scholar should turn up a bunch of candidates.  You want to learn a distance metric from relative comparisons.  See also https://en.wikipedia.org/wiki/Similarity_learning.


How do you prove that this TM decides a language that is undecidable? In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language

$$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w \in L(M)$}\}.$$

$T$ is a TM defined as follows. On input $\langle M,w \rangle$,

Write the description of a TM $R$ that works as follows. On input $x$,

Run $T_A$ on $x$.
If $T_A$ accepts $x$ then accept.
If $T_A$ rejects $x$ then run $M$ on input $w$ and accept if $M$ does.

Run $P$ on input $\langle R \rangle$, accept if $P$ rejects and reject if $P$ accepts.

Here:

$T_A$ is a TM that decides the language $A$.
$P$ is a TM that can decide the language
$$  Z = \{\langle M\rangle | M\text{ is a TM and } L(M) = A\}. $$
$ A = \{(0 \cup 1)^a(1 \cup 2)^b(2 \cup 3)^c | a \geq b\} $.

How can you prove that $T$ decides $A_{TM}$ ?

Hint: The exact definition of $A$ is not important; you just need $A \neq \Sigma^*$. When is $L(R) \neq A$? (look at the third line!)


Pentary Search Recurrence Relation I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is:

C(n) = C(n/5) + 14/5

However, I got it wrong and the professor didn't really explain why.

Can you help me?

Thanks!

Edit:

Pentary search is dividing the array into 5 parts and look for a specific key.

In perspective:

1|2|3|4|4

These are the number of comparisons made by the computer from pentary search.

Adding all possible comparisons I get 14 over 5 slots. This is why I have 14/5

There is at least one thing that could be wrong with your recurrence, depending on how exactly the algorithm is stated: you are overlooking the case that the element could be found before recursion.


How to prove transitivity in small-o of asymptotic analysis? Here is my proof, but I am not sure whether it is correct.

We know:

$\qquad \begin{array}{l}
 \forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\
 \forall {c_1},\exists {n_2},0 \le g\left( n \right) \le {c_1}h\left( n \right),\forall n \ge {n_2} \\
 \end{array}$

Hope to prove:

$\qquad \begin{array}{l}
 \forall c,\exists {n_0},0 \le f\left( n \right) \le ch\left( n \right),\forall n \ge {n_0} \\
  \Rightarrow 0 \le f\left( n \right) \le {c_1}g\left( n \right) \le {c_1}\left( {{c_1}h\left( n \right)} \right),\forall n \ge \max \left\{ {{n_1},{n_2}} \right\} \\
 \end{array}$

Let $c = {c_1}^2$. Then,

$\qquad 0 \le f\left( n \right) \le {c^2}h\left( n \right),\forall n \ge {n_0} = \max \left\{ {{n_1},{n_2}} \right\}$

Is there any mistake?

Comment on your proof:
You write
"Let $c = {c_1}^2$." Strictly speaking, this doesn't make sense, since you haven't set $c_1$ to any value yet at this point. To be formally correct, you need to start with some given $c$, and then set $c_1$ to $\sqrt{c}$ and proceed from there (which is what I've done below where $\epsilon = c$).

To show that $f(n) \in o(h(n))$, you need to show that $\lim_{n\rightarrow\infty}\frac{f(n)}{h(n)}=0$. Or, in other words, for any constant $\epsilon$, there exists $N>0$ such that
$$
\forall n \geq N\colon |f(n)| \leq \epsilon|h(n)|. \qquad \text{(A)}
$$
Before proving (A), let's write out our assumptions explicitly:
Since we have assumed $f(n) \in o(g(n))$, we know that for any $\epsilon$, there exists an $N_f$ such that
$$\forall n \geq N_f\colon |f(n)| \leq \epsilon |g(n)|. \qquad\text{(1)}$$
Analogously, by $g(n) \in o(h(n))$, we know that there is $N_g$ such that
$$
\forall n \geq N_g\colon |g(n)| \leq \epsilon |h(n)|, \quad\text{(2)}
$$
for any given $\epsilon$.

Proof of (A): Suppose we are given some $\epsilon$. Let $$N = \max\left(N_f(\sqrt{\epsilon}),N_g(\sqrt{\epsilon})\right),$$
where $N_f(\sqrt{\epsilon})$ and $N_g(\sqrt{\epsilon})$ are constants that make (1) and (2) true for $\sqrt{\epsilon}$.
It follows that
$$
\sqrt{\epsilon} > \frac{|g(n)|}{|h(n)|} > \frac{(1/\sqrt{\epsilon})|f(n)|}{|h(n)|},
$$
and therefore $|f(n)| \leq \epsilon |h(n)|$, as required.


Approximation of minimum bandwidth on binary trees Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes.

The decision problem is NP-complete even for binary trees. Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978.

What is the best known efficient approximability result for computing minimum bandwidth on binary trees? What is best known conditional hardness of approximation result?

Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no PTAS for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an approximation factor of $k$. So, unfortunately there's no PTAS nor APX for the problem.

However, for some types of graphs, the problem can be solved or approximated in polynomial time. For a recent survey, see Petit J., Addenda to the Survey of Layout Problems, 2011. In the survey, see Tables 3, 4 and 8. The survey also gives a nice list of references if you want to dig in deeper to some direction. This is an more updated version of the older survey by Diaz et al., A survey of Graph Layout Problems, 2002.

In case you are interested in the exact algorithm as well, I think currently the fastest one is given by Cygan M. and Pilipczuk M., Even Faster Exact Bandwidth, 2012. The algorithm runs in $O(4.83^n)$ time.


EQtm is not mapping reducible to its complement This is a problem from Sipser's book (marked with an asterisk).

$EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$

We know that neither $EQ_{TM}$ nor $\overline{EQ_{TM}}$ are recognizable so unsure how to go about proving there can't be a mapping reduction from one to the other.

Any hints?

Your language is $\Pi_2$-complete: it can be written as a $\Pi_2$ formula, and TOT can be reduced to it. The complement is therefore $\Sigma_2$-complete. No computable reductions can exist between $\Pi_2$-complete and $\Sigma_2$-complete sets (why?).


Understanding Dijkstra's notation $f.x.y$ I recently discovered that I have a fondness for the work of Dijkstra. I am currently reading random EWDs, and stumbled across one with some notation that I couldn't quite grasp.

Dijkstra states that $[ x < y \implies f.x.y < f.y.x]$

OK, so. This isn't a list comprehension, right? Why the brackets?

Also, how could this be read aloud? What does $\implies$ mean?

And finally, what does $f.x.y$ and $f.y.x$ mean?

And how could this statement be written more conventionally? And does Dijkstra's notation derive from anything, or is it entirely his own invention?

I think this would read as follows in modern notation (although  field-local variations are possible):

$$\forall x y. x < y \Rightarrow f(x,y) < f(y,x).$$

Read aloud: for all x and y, x is less than y implies that f of x and y
is less than f of y and x.

If you read the first sentence of the linked document, it says that square brackets represent universal quantification over $x$ and $y$. The second states that $f$ is a function. => is ASCII art for $\Rightarrow$ (logical implication).

The main problem here is missing context (and detective skills). This article refers to EWD878. Perhaps looking there would have helped. Indeed, looking at that article, you see notation slightly closer to what is used today (at least, by Haskell programmers: f.x.y becomes f\ x\ y).


DFA that recognizes 0 in every odd position I had a question that asked for the DFA that accepts the following language:

{w | every odd position of w is a 0 }

Should this DFA accept the empty string, since it doesn't have an odd position?

Yes, since $|\epsilon| = 0$, there are no odd positions; therefore, that DFA would accept $\epsilon$.


find function which is in o(log^k(n)) for fixed value of k and in ω(1) I need to find a function $f$ which is in $o(\log^{k} n)$ for fixed value of $k$ with $f = \omega(1)$. I know that for little $o$ the function should be strictly less than $c\log^k n$ for all $c$ and large enough $n$; and for little $\omega$ it should be strictly greater than $c\cdot 1$ for all $c$ and large enough $n$, but I am stuck here. How does one usually solve such type of problems?


How many neurons is needed for UAT to hold? The universal approximation theorem states that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of Rn, under mild assumptions on the activation function.

How many neurons is needed? For a function in 3 variables and one output.
And how many adjustable parameters does that give in the neural network?

There is not a particular number. You have to decide how much you want to approximate your function.

UAT, in informal language, means that neural network can approximate any given function f when given appropriate parameters (which are to be found experimentally; their learnability isn't a question here!).

If you have a function of 3 variables, then a neural network with 20 neurons may approximate it far better than one with the 10 neurons. It is possible that after a certain number of neurons, the difference between the outputs, i.e., (F - f) becomes very less.

I answer this question following Occam's razor, thus not mentioning any un-necessary terms. Please ask, if you have any additional or specific questions in it.


NP-completeness proof via reduction I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 1's such that Ax >= b. I've seen that 3-CNF SAT is reducible to this problem.

However, here's a slight variant: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 2's such that Ax >= b.

The fact that vector x must consist of 0's and 2's kind of throws me off here. For the original problem, we just could reduce from 3-SAT by adding the inequalities 0 <= xi <= 1 for each boolean variable. But here, I can't just add the following inequalities:

0 <= xi <= 2

because x cannot equal 1.

Am I allowed to add an inequality, such as xi != 1? If not, what reduction can I use to show that the given problem is NP-complete? Thanks for any help.

Suppose you are given a 0-1-Integer-Programming instance. You need to substitute $x_i$'s, $x_i \in \{0,1\}$, with new variables $y_i$'s as G. Bach mentioned. The substitution is $x_i = y_i/2$, $y_i \in \{0,2\}$.

By this substitution, you get
 0-1-Integer-Programming $\leq_P$ 0-2-Integer-Programming
 and also 0-2-Integer-Programming $\leq_P$ 0-1-Integer-Programming by reverse substitution.
(This is because the polynomial reduction function in this case is invertible).

Therefore 0-2-Integer-Programming is also NP-complete
(from 0-1-Integer-Programming $\leq_P$ 0-2-Integer-Programming).

By the way, you are not allowed to add $x_i \neq 1$ in canonical integer programming problem. Basically it means $x_i \leq 0$ OR $x_i \geq 2$. We can't have OR constraints, all we can have is AND constraints.


Are there peer-reviewed papers studying the pros and cons of functional programming? Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in fields such as Machine Learning, Language Design, etc.?

There is a famous paper "Why Functional Programming Matters" by John Hughes. The main argument of this paper is the modularity of functional programs.

Also, the work by Chris Okasaki about functional data structures is very interesting. The article "Red-Black Trees in a Functional Setting" provides a very clear implementation of red-black trees using functional programming language, which is much simpler than their imperative implementation in the book "Introduction to Algorithms" by Tomas H. Cormen et al.


How one epoch completes in Perceptron? I am confusing on completing one epoch, I am using Single Layer Feed Forward neural Network approach. Lets suppose i have a data of OR Gate:

X1  X2   Target
0   0    0
0   1    1
1   0    1
1   1    1

Now we initialize weights (w1 and w2 with 0) and bias 1, it satisfy our first condition  0   0   0 with delta rule (T-O=0) but when we use same weight and same bias with 0  1  1 this row not satisfy with (w1 = 0 , w2 = 0, b= 1) so we change our weight and bias values, now my question is:

We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is 1  0  1 with new weight and bias value or with old one which is (w1=0, w2=0, b=1) ? and if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch ? but how because we didn't check the first row with new value.

We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is 1  0  1 with new weight and bias value or with old one which is (w1=0, w2=0, b=1) ?

The Perceptron processes one example at a time. The weights are immediately applied and subsequently updated (if the prediction is not correct).

  if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch?

Applying the learning rule to each example in the training set is called an
epoch.

Finishing an epoch doesn't mean that the perceptron converges to zero training error (it's typical to run multiple epochs).

For example, given:

(X1)--\
       \
        \ W1
         \
(X2)--W2--+-Y---O
         /
        / B
       /
 (1)--/

with:

$$Y = W_1 \cdot X_1 + W_2 \cdot X_2 + B$$

$$
O = \begin{cases}
0 & \text{if $Y \le 0$} \\
1 & \text{if $Y > 0$}
\end{cases}
$$

$$\delta = Target - O$$

$$\Delta W = \epsilon \cdot \delta \cdot O$$

If $\epsilon = 1$ and $W_1 = W_2 = B = 0$:

X1  X2  Target   W1    W2     B     Y  O  Delta   W1'   W2'     B'
 0   0     0      0     0     0     0  0      0    0     0      0
 0   1     1      0     0     0     0  0      1    0     1      1  <-error
 1   0     1      0     1     1     1  1      0    0     1      1
 1   1     1      0     1     1     2  1      0    0     1      1
--------- END OF EPOCH 1 / NOT CONVERGED ------------------------
 0   0     0      0     1     1     1  1     -1    0     1      0  <-error
 0   1     1      0     1     0     1  1      0    0     1      0
 1   0     1      0     1     0     0  0      1    1     1      1  <-error
 1   1     1      1     1     1     3  1      0    1     1      1
--------- END OF EPOCH 2 / NOT CONVERGED ------------------------
 ...
--------- END OF EPOCH 3 / NOT CONVERGED ------------------------
 ...                                                              NO ERROR
--------- END OF EPOCH 4 / CONVERGED ----------------------------


Proof of commonality of acceptors in majorities In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N majority sets of acceptors having either at least one acceptor in common, or acceptors that are distinctly present in each N-1 sets of acceptors.

"Therefore if two proposals are agreed to by a majority, there must be at least one acceptor that agreed to both. This means that when another proposal, for example, is made, a third majority is guaranteed to include either the acceptor that saw both previous proposals or two acceptors that saw one each."

I have an intuitive understanding of why this is so (should be a simple pigeonhole principle application), but I am having difficulty proving this formally. I would like a formal proof.

Let $A,B,C$ be the first, second and third majorities. If there are $M$ players, we can think of $A,B,C$ as subsets of $[M] = \{1,\ldots,M\}$ satisfying $|A|,|B|,|C|>M/2$.

If $A,B$ were disjoint then $|A \cup B| = |A| + |B| > M$, which contradicts $A \cup B \subseteq [M]$; that's why two majorities always have an acceptor in common.

If $C$ intersects $A \cap B$ then the third majority includes an acceptor that saw both previous proposals, so suppose that $C$ is disjoint from $A \cap B$. Define
$$ A' = A \setminus (A \cap B), \;\;\; B' = B \setminus (A \cap B) \;\;\; U = [M] \setminus (A \cap B). $$
In order to show that the third majority includes two acceptors that saw one of the previous proposals each, we need to show that $C$ intersects both $A'$ and $B'$. If $C$ didn't intersect $A'$ then $|C \cup A'| = |C| + |A'| > M - |A\cap B|$, which contradicts $C \cup A' \subseteq U$ since $|U| = M - |A\cap B|$; so $C$ must intersect $A'$. Similarly, $C$ must intersect $B'$.


Question about space complexity I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to v, and which nodes are outwardly adjacent to v. To get around this, my idea was to use a list of pairs, where each pair consists of two sets - which correspond directly to the inward and outward adjacency sets of any vertex in the graph.

I understand that the maximum number of edges in a directed acyclic graph of size $n$ is $\frac{n(n-1)}{2}$. In the proposed graph encoding, the existence of a vertex u in vertex v's 'in' set implies the existence of an edge (u, v). The existence of a vertex u in vertex v's 'out' set implies the existence of an edge (v, u). Additionally, $u \in in(v) \iff v \in out(u)$. Therefore, my intuition tells me that this representation of a directed acyclic graph has a space complexity of $\mathcal{O}(2|E|)$, since the existence of each edge $(v, u)$ is implied twice; once by $v \in in(u)$ and once by $u \in out(v)$.

My question is, does my intuition fail me?

You say  "using a structure similar to an adjacency list". So space complexity required for storing undirected graph using adjacency list is $O(|V| + |E|)$, in your case $O(|V| + 2|E|)$. That is implemented using a list of nodes where each node has two fields: label of the vertex and pointer to the list of adjacent nodes (in your case two lists).

But I don't know how you are going to use the graph. If you are interested in simply a set of edges then you could store them in a list as triples $<u,v,weight>$. But if at some point for a node $v$ you want to systematically loop on all adjacent vertices (inward or outward) then you should use adjacency list.

Finally if you want to decide in $O(1)$ if there is an edge $<u,v>$ then you should use hash like data structure to store pairs $<u,v>$.


median filter one after the other Operate on an image by performing Median Filtering in a 3x3 window.
Operate on the resulting image by performing, again, Median Filtering in a 3x3 window.
Can the resulting image be obtained from a single Median filtering?

my initial thought is that it can be done with the right mask. maybe a median next to a median.
but i'm not sure.

The median is a value of a sample which states that half of the other values of the sample have higher values and the other ones are smaller ones. In a 3⨉3 filter you are selecting the median out of a sample of 8 elements. Let's assume we have the following values in our sample (an image of size 3⨉3):

1  2   4
8  16  32
64 128 255

If we apply the median filter for the upper left value [sample: {2, 8, 16}], the median is 8 (not processing out of boundary values). After the first application of the median filter we get a new sample:

8  8  16
16 20 16
16 32 32

If we apply the median filter again, we get:

16 16 16
16 16 20
20 16 20

So my point here is that after each application of the median filter, you will get a new sample [0]. But the evaluation of one new pixel depends on all the other sample values and modifies the sample itself. Because of this dependence I cannot see any way to be able to apply the filter twice in one step. I also did not find any literature about this [1].

[0] Unless the image contains only the same value at each pixel which we cannot assume.
[1] which I don't want to use as a pro or contra argument.


Algorithm to add sum of every possible xor-sum sub-array I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

Problem Statement

XOR-sum of a sub-array is to XOR all the numbers of that sub-array.
An array is given to you, you have to add all possible such XOR-sub-array.

Example

Input

Array :- 1 2

Output :- 6

Explanation

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

for (int i=0, p=1; i<30; i++, p<<=1) {
    int c=0;
    for (int j=0; j<=N; j++) {
        if (A[j]&p) c++;
    }
    ret+=(long long)c*(N-c+1)*p;
}

In pseudocode:

Set $r = 0$
For $i$ from $0$ to $29$, let $p = 2^i$.

Set $c=0$
Iterate over the array $A$. For each element $A[j]$:

If $A[j] \mathbin\& p \ne 0$ then increment $c$. ($\&$ is bitwise and.)

Add $c \times (N-c+1) \times p$ to $r$

After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A[j]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A[i-1]$ is $1$ and the same bit in $A[j]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A[i-1]$ and $1$ for $A[j]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k[i-1],A^k[j])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.


Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language?

I've tried applying the pumping lemma for CFGs and proving case by case (taking x=uvw, at first v is int $a^+$, then v is in $a^+b^+$ etc.but I'm failing to find a contradiction). Any help is welcomed.\

PS: The suggestion does not solve my problem. I know the technique of applying the pumping lemma for CFG to prome a language is not context free, but I don't know how to use it on this particular language.

Firstly I want to point out that what you want to prove that $L$ is a context free language or CFL not grammar. A CFL can be defined by a CFG, but they are very different things.
Anyway, back to your question.

I'm going to give you somewhat informal reasoning, but I think you will be able to formalize it if necessary.

Let us assume that $L$ is in fact a CFL. Then the pumping lemma for CFL's holds for $L$. Let n be the number of the pumping lemma for L.

Consider the word $w = a^nb^{n+1}c^{3n+4} \in L$

From the pumping lemma we have that $w = uxyzv, |xyz| \leq n, |xz| \geq 1, (\forall i \geq 0)[ux^iyz^iv \in L$]

We have two inequalities we can try to break:

$i < j$
$i + 2j + 3 < k$

Assume $xz$ does not contain $c$. This means that $xz$ contains only $a$'s or $b$'s (or both). Since $xz \geq 1$ This means we can pump up the word as much as necessary to break inequality $(2)$ -The right side of the inequality will remain the same when we pump up, but the left side will increase by at least $1$ on each step.

So we have deduced that $xz$ must contain a $c$.

Assume that $xz$ contains only $c$'s. Since $xz \geq 1$ we can pump down to remove at least one $c$. This will again break inequality $(2)$ since the right side will become less than or equal to the left.

So we have deduced that $xz$ must contain both a $b$ and a $c$. But since $xz$ contains a $b$, this means that we can pump down and remove at least one $b$, thus breaking inequality $(1)$.

Thus we have shown that no matter how we break up $w$ we can always pump it out of the language. This is contradiction with out assumption that $L$ is a $CFL$ so it must mean that $L$ is not a $CFL$.


Rigorous Books on Algorithms I thoroughly enjoyed my algorithms class but I felt that it lacked rigor. Most of the time I was able to intuitively understand why the algorithms presented worked and why they had the time complexity that was presented but I'd like to be able to prove such things. As such, I'd like a book that goes over lots of common algorithms and has a focus on proving the correctness and time complexity of the algorithms. Any good recommendations?

Note: please edit this answer and add to it, do not create new answers

Rigorous books:

The Art of Computer Programming by Knuth

A Discipline of Programming by Dijkstra

Introduction to Algorithms by  Cormen, Leiserson, Rivest, and Stein

Algorithms by Sedgewick and Wayne

Dr Dobb's Essential Books on Algorithms and Data Structures
This also includes introduction to algorithms

Algorithms + Data Structures = Programs by Wirth and its followup:
Algorithms and Data Structures

The Science of Programming by Gries and
A Logical Approach to Discrete Math by the same author

Algorithms on Strings, Trees and Sequences by Gusfield

Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik

The Theory of Parsing, Translation, and Compiling (part I and II) by  Aho and Ullman

The Design and Analysis of Computer Algorithms by  Aho, Hopcroft, and Ullman

Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman

Obviously the list can be extended quite a bit.
Note that as the field of computer science has expanded, books are unable to keep up and thus you'll have to turn to research papers.


Problems that are easy on bipartite but hard on general graphs Are there any problems that are easy for bipartite graphs, but hard for general graphs?

I am asking because some classical problems are formulated in reference to people looking for a spouse, such as the marriage problem (for straight people) and the stable marriage problem (for straight people). Both are in FP.

If one removes the requirement that there are two genders and that every man has to marry exactly one women, the general stable marriage problem (my term) is the same as the stable roommates problem, and a solution is no longer guaranteed to exist. I wonder if there are other problems which are explained using similar metaphors for which there is also an increase in complexity.

There are several well-known NP-complete problems that become solvable in polynomial-time for bipartite graphs. For example, 3-coloring is easy as bipartite graphs are precisely the 2-colorable graphs. Another example is independent set which is made easy by König's theorem.

Wikipedia also lists a problem that is NP-hard for general graphs but is trivially in P for bipartite graphs: the odd cycle transversal problem.


Different boolean degrees polynomially related-2? Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p_{0,\epsilon}$ be the minimum degree (of degree $d_{0,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree (of degree $d_{1,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$?

Above holds if $\epsilon\in(0,1)$
Relations among different boolean approximations

There solution considered $0<\epsilon<\frac{1}{2}\leq\delta<1$.
Solution showed relation between $d_{0,f,\epsilon},d_{0,f,\delta}$ is a linear function with constant multiplicative factor as long as we have fixed $\epsilon,\delta$.

This along with solution to another problem in Different boolean degrees polynomially related? shows $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$ holds if we have fixed $\epsilon,\delta$.

(1) I am most interested in case where we have not fixed $\delta$ and/or $\epsilon$. Say $\delta=1-\frac{1}{h(n)}$, $\epsilon=\frac{1}{g(n)}$ (that is either/both $\delta$ or/and $\epsilon$ changes) with some functions $g(n)$, $h(n)$ of $n$ (logarithmic/polynomial/exponential). I am interested in how fast do degrees (multiplicative factors) grow.

(2) There was a comment on sign degree. I understand sign degree is an useful parameter. However for sign degree as I understand ranges of functions involved are over $\Bbb R\backslash\{0\}$ (Only criteria is approximating function takes same sign as $f$). Here ranges are different.

You're asking several questions. Here are answers for some of them.

The OR function has degree $n$, but it can be approximated by the function $(x_1+\cdots+x_n)/n$. This shows that $d_{1,\text{OR},1-1/n} = 1$.
If you have a polynomial $P$ representing $f$ in the sense that $P(x) = 0$ whenever $f(x) = 0$ and $|P(x)-1|<1$ whenever $f(x) = 1$, then for small enough $\epsilon > 0$, the function $P-\epsilon$ sign-represents $f$.
The correct tradeoff between (say) $d_{0,f,\epsilon}$ and $d_{0,f,\delta}$ for different $\epsilon,\delta$ can be studied using approximation theory, i.e. Chebyshev polynomials and the related Markov and Bernstein theorems and their ilk. The functions converting a $\delta$-approximation to an $\epsilon$-approximation can be constructed explicitly using Chebyshev polynomials, and lower bounds on their degrees can be obtained using Markov–Bernstein theorems. This is similar to the way that the tight bound $\Theta(\sqrt{n})$ for the approximate degree of the OR function $d_{\text{OR},\epsilon}$ is proved.


A simple Query regarding Modulus Notation? Aren't these two Modulus equations exactly the same (seems obvious):

$ X = 0 \ (mod\ B) $
$ X = B \ (mod\ B) $

The reason for the query is the following NP Complete Problem from Garey and Jhonson:

AN2, Simultaneous incongruences.

Given a collection $ [(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod \ b_i)$?

If both are equivalent why do we require $a_i≤b_i$ in the problem definition as its equivalent to $a_i<b_i$ ?

Note that the definition of this problem considers positive integers without $0$, which is instead denoted by $B \bmod B$.


What is the definition of a $\Pi_1$-sentence? What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence?
I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall n_2\dots\forall n_k \psi$ where $\psi$ is a formula in the language of Peano arithmetic with only bounded quantifiers. And for the analytical hierarchy, a $\Pi_1^1$-sentence  is a sentence of the form $\forall X_1\forall X_2\dots\forall X_k \psi$ where $\psi$ is a formula in the language of second-order arithmetic with no set quantifiers.

I found the following definition for this notation in section "5 Proving Independence" of an article on the possibility of undecidability:

  Let’s define a $\Pi_1$-sentence to be any sentence of the form, “For all $x$, $P (x)$,” where $P$ is function that can be proven to be recursive in Peano Arithmetic, PA.

People talking about $\Pi_1$- and $\Pi_2$-sentences sometimes refer to Shoenfield's absoluteness theorem, which seems to talk about $\Pi^1_2$-sentences, i.e. refers to the analytical hierarchy. Can I deduce from this that people talking about $\Pi_1$-sentences use $\Pi_1$ as a shorthand for $\Pi^1_1$ (because $x^1=x$...)? But the quoted definition looks much more like the condition from the arithmetical hierarchy to me, even so I'm not sure whether it is really equivalent to it.

Since Peano arithmetic is a first-order theory, all quantifiers are first-order, so it's a $\Pi_1^0$ sentence. The article probably contains examples supporting this interpretation.


What does it mean to logically imply another predicate? Consider the following predicate formulas.

$F1: \forall x \exists y ( P(x) \to Q(y) ).$

$F2: \exists x \forall y ( P(x) \to Q(y) ).$

$F3: \forall x P(x) \to \exists y Q(y).$

$F4: \exists x P(x) \to \forall y Q(y).$

Answer the following questions with brief justification.

(a) Does $F1$ logically imply $F2$?

(b) Does $F1$ logically imply $F3$?

(c) Does $F1$ logically imply $F4$?

(d) Does $F2$ logically imply $F1$?

(e) Does $F2$ logically imply $F3$?

(f) Does $F2$ logically imply $F4$?

(g) Does $F3$ logically imply $F1$?

(h) Does $F3$ logically imply $F2$?

(i) Does $F3$ logically imply $F4$?

(j) Does $F4$ logically imply $F1$?

(k) Does $F4$ logically imply $F2$?

(l) Does $F4$ logically imply $F3$?

Logically implies really confuses me. Attempt:

Writing it in English first:

F1: We have that $x$ never satisfies $P$ or there is a $y$ that satisfies $Q$

F2: For some $x$ $P$ isn't satisfied, or $y$ always satisfies $Q$

F3: Some $x$ doesn't satisfy $P$ or some $y$ satisfies $Q$

F4: $x$ never satisfies $P$ or $y$ always satisfies Q

By definition of logically implies: A formula $F$ logically implies a formula $F'$ iff every interpretation that satisfies $F$ satisfies $F'$

So:

(a) So for $F1$ $x$ never satisfies $P$ meaning it'll always be true whereas some $x$ can satisfy P in $F2$, thus this doesn't logically imply.

(b) ... yeah I don't know how to explain any of this - any assistance even tips are appreciated I'm stumped

Apparently $b$ is true I don't get it though.

according to $F1$, $x$ never satisfies $P$ and by prepositional logic of $p \to q$ is not p or q.

then $F1$ is always true whereas $F3$ there can exist a P that satisfies Q and some y that doesn't satisfy Q so every interpretation doesn't satisfy? I'm understanding this poorly.

$F_1$ says for all $x$, there exists a y such that $P(x)$ implies $Q(y)$.

$F_2$ says for there exists a $x$, for all $y$ such that $P(x)$ implies $Q(y)$.

$F_3$ says that for all $x$, if $P(x)$ holds, then there exists a $y$ such that $Q(y)$.

$F_4$ says that there exists a $x$, such that if $P(x)$, then for all $y$, $Q(y)$ holds.

The first one means that for all values of $x$, there exists some value of y such that the $P(x)$ implies $Q(y)$.

The second one says that there exists a common $x$ for all $y$ such that $P(x)$ implies $Q(y)$.

Both of them aren't the same, which is what you have pointed out too and you can solve the rest of them in the same way.

Also, a good way would be to some concrete example and see if it holds or not. It makes the intuition a bit easier.

EDIT: If you want more help with logical implications, there's a book called How To Prove It by Daniel Velleman whose first two chapters deal with logic, which is a good read.


Relationship between MIPS (Million Instructions per second) and operating frequency of a processor Let's say there is an algorithm that runs on a processor at x MIPS, operating at a clock frequency of y MHz. If I double the operating frequency to 2y, what happens to the MIPS? It seems to me that doubling the operating frequency should double the instructions executed per second, i.e, MIPS = 2x, is this correct?

Only if you double the speed of everything. Which you can’t in practice.


Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable Past year paper question:

Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$.

Show that the following language is not recursively enumerable:

$L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$

I tried to show that we can reduce $L_e$, the set of Turing machines that accept no strings, to $L$. To do this, I need to find a transformation $f$ such that is $\mathrm{Lang}(M)$ is empty, then the machine represented by $f(M)$ has some string $x$ but not $xx$, and if $\mathrm{Lang}(M)$ is not empty, then the machine represented by $f(M)$ contains $xx$ if it contains $x$.

But I am not sure how to find such a transformation. Can someone show a transformation to solve this problem?

First, recall that the problem "$L(M)\neq\emptyset$" is semidecidable.

Define $f(M)$ as $a^i$ where $M_i$ is a TM such that

it accepts $aa$ iff $L(M)\neq\emptyset$,
it accepts any other string (including $a$).

For the first step: when $M_i$ receives $aa$ as input, it semi-decides $L(M)\neq\emptyset$. If that holds, the semi-decider halts in finite time, so $M_i$ can accept. If that does not hold, the semi-decider diverges, making $M_i$ diverge. This is fine, since $aa$ is not accepted.

Note that we never reject $aa$, because we do not have a full decider for $L(M)\neq\emptyset$. This however does not matter: we do not have to reject $aa$, we only have to avoid accepting it, and diverging suffices.


How can I prove that my greedy algorithm for least guards is optimal? This is the problem:

  An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).

No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

Start at the beginning of the hallway.
Find the position of the closest artwork from the entrance.
Put the guard at position closest artwork + 5m ahead.
Eliminate all the artworks covered by the guard.
Re-do the process but this time start where the range of the previous guard ended

Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?

You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it.

In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not have to add one and hence, the optimal can not be better. In case it is not, it is easy to show, that an optimal that woul have covered it should have used strictly more guards.


Efficient algorithm to find vertex with paths to every other vertex $G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!

You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.


Term for array of identical type and different types What is proper terminology to distinguish between an array (ordered list) data structure in which each element is of identical type/class, and an array in which each element can be different?

A structure containing only the same type is homogeneous, and a structure containing different types is heterogeneous.


Sum of divisors summatory function with Erathosthenes' sieve I ran across the following problem from an online problem bank: there are up to $~10^5~$ queries each of which asks to compute the sum
$$\sum_{k = L}^{R} \sigma(k)$$
where $\sigma(k)$ is the sum of divisors of $k$. It is given that $1 \leq L \leq R \leq 5\cdot 10^6$.

My solution (described below) is based on Erathosthenes's sieve. I've implemented it in C++ and it works in about $0.9$ seconds on average which is too slow. I know that this problem can be solved at least twice faster but don't know how.

So here is my solution (arrays are 0-based):

M = 5 * 1e6
M = array of zeroes of size M + 1
A[1] = 1
for (k = 2; k <= M; k += 1)
    for (j = k; j <= M; j += k)
        A[j] += k

I precalculate $\sigma(k)$ via Erathosthenes' sieve for each $k$ below max possible value. When the main loop reaches $k$,  $A[k]$ keeps the value of $\sigma(k)$. Then I reassign $A[k]$ to be $\sum_{i=1}^{k}\sigma(i)$. After such preprocessing all queries can be computed in $O(1)$ time by computing $A[R] - A[L-1]$.

How can I make it faster? I know two formulas:
$$ (a) ~~~~~ \sigma(p_{1}^{a_1} \cdots p_{s}^{a_s}) = \prod_{i=1}^{s} \frac{p_{i}^{a_i + 1} - 1}{p_{i} - 1}$$
$$ (b) ~~~~~ \sum_{k=1}^{n} \sigma(k) = \sum_{k=1}^{n} k \left \lfloor \frac{n}{k} \right \rfloor$$

The problem with (a) is that computing it (at least in my implementation) is slower than given above. The problem with (b) is that I don't understand how to compute prefix sum with such approach faster than in $O(n^2)$ time.

Is there a more efficient algorithm for this problem?

(The problem bank credits the original source of the problem as 2012 Kharkiv, Winter School, Day of Sergey Kopelovich, Problem H.)

This isn't really computer science...

You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a table s where you store the sum of divisors for all 1 ≤ j ≤ k, for k = 1 to M. That's easy, $s_0 = 0$, $s_{k+1} = s_k + d_{k+1}$. And then f (L, R) = $s_R - s_{L-1}$.

The first table is the problem. You handle this in $O (n \log n)$. And you only need a factor two, you say...

You will have an array d with 5 million entries, likely 4 byte per entry = 20 Megabyte. On a typical processor that you would have in your home computer, 20 Megabyte doesn't fit into any cache. And your code does lots of accesses to elements of that array in quasi random order. For each potential divisor k, you visit all numbers that are divisible by k, and increase the sum of divisors by k.

Let's do that with fewer visits: When you visit j which is divisible by k, add the two divisors k and j/k. But when you do that, start with $j = k^2$, adding only k (because k = j / k, and you don't want to count the divisor twice), and then add k and j / k for further j. You don't need to divide, because j / k will equal k+1, k+2, k+3 etc. We initialise the array for the case k = 1, that is setting A [j] = 1 + j / 1 for j ≥ 2.

A [1] = 1
for (j = 2; j ≤ M; j += 1)
    A [j] = 1 + j

for (k = 2; k*k ≤ M; k += 1)
    j = k*k
    A [j] += k
    j += k
    s = k + (k + 1)
    while j ≤ M
        A [j] += s
        j += k
        s += 1 // s equals k + j / k

You don't save operations. However, you are now accessing the array A in a much more regular pattern, so this will save you time because access to the items will be faster. j will be smaller, making the number of iterations for each j larger, which will make branch prediction work better.

For more improvement, you would find out how many array items fit into the processor cache in your computer, then perform the whole code for subranges of the array only (for example changing only A [0] to A [99999], then changing A [100000] to A [199999], and so on). That way, most memory accesses will only access cache memory, which might be substantially faster.

You are doing N lookups in a table of size M. If M is substantially larger than N, then you should probably think about approaches that don't build this table, and that may be a lot slower per lookup, but faster overall due to the small number of lookups. Even in the case here where N ≤ 100,000 and M = 5,000,000, you might for example not count divisors 1, 2, 3, 4, j/1, j/2, j/3, j/4 in the table (which makes it a bit faster to build), and handle that during the lookup.

Or you could add the sum of the divisors for odd numbers only, then calculate the sum of divisors for even numbers (if the sum of the divisors of an odd k is s, then the sum for 2k is 3s, for 4k it is 7s, for 8k it is 15s etc), which would save almost a factor 2.

PS. I measured it... making the algorithm for counting all sums of divisors more cache friendly by adding both j and k/j doubled the speed. Calculating the sum of divisors for odd k first, then calculating even k from the odd values, makes it a total of 7 times faster. Obviously all just constant factors.


Why is OPT at least the most valuable item for FPTAS Knapsack? In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V \leq V^*$, where $V$ is the value of the maximum valued item and $V^*$ is the optimal solution.).

Why is that? I mean, we could have a knaspack problem with two items, one with value $10000$ and size $10000$, and one with value $1$ and size $1$, and for a knapsack capacity of $1$ clearly the optimal solution is $1$, but $V = 10000$, and $V^* < V$.

It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out items that are too large to fit even alone is easily possible in a polynomial-time preprocessing step.

If the sources do not mention that they are sloppy.

And in that case, every item fits into the knapsack alone, hence you can obtain the maximum item value with a trivial singleton solution.

Nota bene: As soon as we are talking algorithms and want to derive running times, such assumptions are not necessarily w.l.o.g. In case the running time cost of the preprocessing is dominant we should not lie it away.


why is the max number of Nodes mod(N/m) + mod(N/m^2) + 1 in R-tree? I am going through Antonin Guttman's paper on R-tree. It mentions the max no of nodes given N index records in an R-tree is |N/m| + |N/m^2| + 1.

If there are N index records and if we choose to have minimum number of entries (m) in each node, wouldn't we just need N/m nodes at max? Why do we also have N/m^2 + 1?

Here's a link to the paper

Here is the relevant excerpt of that paper.

  The height of an R-tree containing $N$ index records is at most $\lceil\log_m N\rceil$, because the branching factor of each node is at least $m$. The maximum number of
  nodes is $\lceil\frac Nm\rceil + \lceil\frac N{m^2}\rceil + \cdots + 1$. Worst-case space utilization for all nodes except
  the root is $\frac mM$.

The paper you saw is so fuzzy that you mistook the formula as $|\frac Nm| + |\frac N{m^2}| + 1$.

How to explain the correct formula? Since all leaves are on the same level and each leaf-node contains at least $m$ index records, there are at most $\lceil\frac Nm\rceil$ leaf nodes. The number of the parents of all leaf nodes is at most $\lceil\frac{\frac Nm}m\rceil=\lceil\frac N{m^2}\rceil$. And so on.

Here is a copy of that paper that is more legible.


Complexity of finding factors of factors of N number for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j+=i)
        for(int k = j; k <= N; k+=j)

How to express this mathematically to calculate the complexity of the above code. I guess, its complexity is $O(N\log\log N)$ but couldn't prove it mathematically!

For each value of $j$, the inner loop runs for $O(N/j)$ iterations. Fixing $i$ and varying over all $j$ in the middle loop, the total number of iterations in the inner loop is
$$
O(N/i + N/(2i) + N/(3i) + N/(ki)) = O(N\log k/i),
$$
where $ki$ is the maximal multiple of $i$ which is at most $N$. We can bound $k$ by $N/i$, and so the expression above equals $O(N\log (N/i)/i) = O(N\log N/i)$. Summing over all $i$ from 1 to $N$, we get $O(N\log^2 N)$.

Using rudimentary calculus (approximating the sum by an integral), you can show that if you sum $N\log (N/i)/i$ over $i$ from 1 to $N$ then you still get $\Theta(N\log^2 N)$, and so the bound above should be tight.


Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct.

Question: What would be the complexity of its inversion?

On the one hand, if all eigenvalues are the same, then the matrix is equal to $aI$. Therefore, the inversion is $O(n)$.

On the other hand, if we can't assume anything than the inversion is $n^{2+\epsilon}$ where $\epsilon \approx 0.37$.

Note: Eigenvalues and eigenvectors are not given.

If the matrix has two distinct eigenvalues, you can find them using power iteration.

Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| > |\lambda_2|$.  Then you can use power iteration to find $\lambda_1$.  Next, set $A' = A - \lambda_1 \text{Id}$.  $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ reveals $\lambda_2$.

The running time depends on the exact values of $\lambda_1,\lambda_2$; power iteration converges geometrically with ratio $|\lambda_2|/|\lambda_1$, so if $|\lambda_2$ is sufficiently smaller than $|\lambda_1$, you can obtain a very precise estimate with a fairly small number of iterations; if they are very close, power iteration will be ineffective.

I don't know how to generalize this handle a matrix with three distinct eigenvalues.


Upper Bound on Runtime of Memoized DP Algorithms I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions.

However, I am now trying to determine a "Big-O" for a DP problem I've memoized.  I don't really care about the answer to this specific problem, but am more interested in a method I can use for other programs I write, or a resource that I can read to learn how to analyze this type of program.

In case a concrete example helps, the following is my program to solve this box stacking problem.  (I wrote my solution before looking at theirs, which appears to use bottom-up DP instead of top-down/memoization.  Thus, I don't think I can cross-apply their time complexity to my algorithm.)

Below is the pseudo-code for my solution.  Assume that putting something on the memo and checking the memo can be done in constant time.

Let a box have parameters width (w), height (h), and depth (d)
reward(maxW, maxD, elementH):
  Zero max1, max2, max3
  If memo contains key (maxW, maxD), return associated value.

  for each box B in the list of input boxes:
    //If the box fits in any orientation, put it on the pile and recurse
    if (B.w < maxW AND B.d < maxD) OR (B.w < maxD AND B.d < maxW)):
      max1 = max(max1, reward(B.w, B.d, B.h) + B.h)
    if (B.h < maxW AND B.d < maxD) OR (B.h < maxD AND B.d < maxW)):
      max2 = max(max2, reward(B.h, B.d, B.w) + B.w)
    if (B.h < maxW AND B.w < maxD) OR (B.h < maxD AND B.w < maxW)):
      max3 = max(max3, reward(B.h, B.w, B.d) + B.d)

  put (maxW, maxD) onto memo, associated with max(max1, max2, max3)

  return max(max1, max2, max3)

A general trick that works for a lot of DP problems is to look at the parameters in your recursion -- the run time is then $O(n \times max(parameter_1) \times \dots \times max(parameter_k))$ where $n$ is the number of iterations (or, the number of inputs).

Consider for example a DP to solve the subset sum -- the recursion is given by $Q(i,s) := MIN(Q(i − 1,s), Q(i − 1,s − x_i)) $ where $0 \leq s \leq T$ and $T$ is the target sum.

The run time is then $O(n \times max(s)) = O(nT)$. And of course, this trick works with memoization only. If you have not done memoization, it is truly exponential (not pseudo-polynomial).

Why does this work? In each iteration $i$, we have to look at at-most $T$ different sub-problems (post memoization) before we hit the base case.


Programming in Propositional Logic article notation question I was reading this article about propositional logic and transforming problems to SAT. The author often uses the following notation (taken from Dominating set section):

I don't understand what $[v,i]$ and $[w,i]$ stand for in $at\_most\_one$ and $at\_least\_one$ parts. I checked the paper twice and didn't find the part where he defines this notation. Has anyone already seen this notation and knows what it means? Why is $i$ needed? Can anybody provide example for a simple graph and for some K (2 or 3).

The set $X$ is a collection of ordered pairs $[v,i]$ (this is just a strange notation for an ordered pair), in which $v$ is a vertex and $i$ is an index from $1$ to $k$. Informally, $[v,i] \in X$ means that $v$ is the $i$th vertex in the dominating set. The formula $F$ states two things:

There is at most one $i$th vertex (i.e., $X$ doesn't contain $[v,i],[u,i]$ for $v \neq u$).
The vertices in $X$ form a dominating set.

The reason we want the index $i$ is that the logic isn't strong enough to count the size of $X$. It is strong enough to express "at most one" and "at least one", so we use this particular encoding to be able to express "the dominating set has size at most $k$".


Termination of a composition of terminating functions Suppose there are two functions:

$ f : X \rightarrow Y $ and $g : Y \rightarrow Z$

Both $g$ and $f$ can be implemented as algorithms that yield the correct result in a finite amount of time.

It appears to be obvious, that there is also a correct and terminating algorithm that computes the composition of the two $g \circ f$.

But why is that so? Do I need to argue that for both functions, there is a representation in the lambda calculus and in that calculus (with a small-step semantics), there is a trivial implementation of $\circ$? Doesn't that require an encoding of $X$,$Y$ and $Z$? Is there a more fundamental theorem?

Indeed this is obvious. Now you need to "prove" it. The difficulty will depend on what definitions (and axioms) you assume when you say that "$f$ and $g$ can be implemented". Start by making these definitions explicit.


Correct name for a recursive descent parser that uses loops to handle left recursion? This grammar is left recursive:

Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

So in theory, recursive descent won't work. But by exploiting the properties of the grammar that each left-recursive rule corresponds to a specific precedence level, and that lookahead of a single token is enough to choose the correct production, the left-recursive rules can be individually parsed with while loops.

For example, to parse the AdditionExpression non-terminal, this pseudocode suffices:

function parse_addition_expression() {
    num = parse_multiplication_expression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            num += parse_multiplication_expression()
        else if (current_token == MINUS)
            num -= parse_multiplication_expression()
        else {
            unget_token()
            return num
        }
    }
    return num
}

What is the correct name for this type of parser? This informative article only refers to it as the "Classic Solution": https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

There must be a proper name for this type of parser.

It is just an LL(1) parser implemented with recursive descent.

Starts with:

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

apply left-recursion removal to get an LL(1) grammar:

AdditionExpression  ::=
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

write the corresponding functions:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    parse_AdditionExpressionTail()
}

function parse_AdditionExpressionTail() {
    if (has_token()) {
        get_token()
        if (current_token == PLUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else if (current_token == MINUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else {
            unget_token()
        }
    }
}

remove tail recursion:

function parse_AdditionExpressionTail() {
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

inline:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

and you have just to add the semantic processing to get your function.


Why can't OSes swap out processes that are waiting for I/O? In the book, Operating System Concepts, 9th Edition, there is this paragraph that I don't quite wrap my head around.

  Swapping is constrained by other factors as well. If we want to swap a
  process, we must be sure that it is completely idle. Of particular
  concern is any pending I/O. A process may be waiting for an I/O
  operation when we want to swap that process to free up memory.
  However, if the I/O is asynchronously accessing the user memory for
  I/O buffers, then the process cannot be swapped. Assume that the I/O
  operation is queued because the device is busy. If we were to swap out
  process P1 and swap in process P2, the I/O operation might then
  attempt to use memory that now belongs to process P2. There are two
  main solutions to this problem: never swap a process with pending I/O,
  or execute I/O operations only into operating-system buffers.
  Transfers between operating-system buffers and process memory then
  occur only when the process is swapped in. Note that this double
  buffering itself adds overhead. We now need to copy the data again,
  from kernel memory to user memory, before the user process can access
  it.

This is quite a handful for me to swallow for now. I have a lot of questions.

What are I/O buffers? Are they located in the I/O device?
How and why does the I/O asynchronously access user memory?
Why would an I/O operation attempt to use P2 memory when P1 gets swapped with P2?

To probably generalize my questions, why shouldn't we swap processes with pending I/O? If we do so, would there be memory corruption or segmentation faults?

One scenario that can explain this more obviously is as follow: Suppose that a process wanted to read a disk block to a buffer in its address space (An I/O buffer is just a portion of the processe's memory. eg. char[1024]). The process will make a system call to ask the OS to issue an I/O to read the corresponding disk block into that buffer in the memory of the process and then the process sleeps waiting for this I/O operation to complete (Because it may take some time before the operation is completed by the device and at that time we can schedule another process for execution instead of letting the CPU idle). Now, to execute that I/O, the OS will probably program some kind of DMA (Direct Memory Access) device to automatically copy the data from the disk controller to the the buffer in the memory of the process without having to interrupt the CPU (Hence, the name direct access to memory). Now, if it happens that the process is swapped out, its physical memory will be freed (the memory where the buffer that receives the disk block content from the DMA is situated) and it will probably be allocated for another process. Which means that, when the DMA starts to copy the disk block content to the initially provided memory buffer (Initial buffer that was later freed and given to another process while the disk block was being read), that content is not actually being copied to the sleeping process's memory but some other process memory. And that's why the OS should not swap a process waiting for I/O. Otherwise, don't program the DMA to copy the disk content directly to the process's memory buffer but instead copy everything into some kernel buffer (Kernel memory) and then copy that content into the process memory again once it's ready (Swapped in) but this is a double duty and may incur some overhead.

Hence:-
So we can say that resources generated after the i/o processing for the original requesting process might be swapped with some other process, due to swapping of memory spaces between the processes.


Decidability of empty intersection of two languages accepted by Turing machines I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle
  L = \{ (R(M_1), R(M_2)) \mid L(M_1) \cap L(M_2) = \emptyset \}$,

where $R(M_1)$ and $R(M_2)$ are representations of Turing machines $M_1$, resp $M_2$ and $L(M_1)$, $L(M_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M_1)$ and $L(M_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is undecidable and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M_1$ and not $M_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?

It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M_1$ that accepts all inputs. $L(M_1)\cap L(M_2) = L(M_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.


Probabilistic algorithm with two-sided error I am currently studying probabilistic algorithms and came across three major complexity classes:

BPP: worst-case polynomial time, two-sided error
RP: worst-case polynomial time, one-sided error
ZPP: average-case polynomial time, no error

At first I couldn't understand why one would use an algorithm that could err. I figured it does make sense in some cases though, like primality testing for RSA encryption. The algorithm used there has a one-sided error only, though.

Even after hours of thinking about it, I failed to think of an algorithm with two-sided error that actually makes sense and could be / is used in practice.

Any pointers would be greatly appreciated.

Monte Carlo methods are inherently not one-sided, though it's dubious whether they're usually two-sided. The general idea is that in order to estimate the expectation of a random variable $X$, we take the average of many samples of $X$.

For example, suppose that you're a petroleum company, and you're trying to decide where to look for oil. For every square in some grid you have some random variable $X_i$, expressing the probability that there is oil in square $i$, that you can estimate using your (noisy) data. You have some threshold $\theta$ in mind, and will start drilling in every square $i$ for which $X_i \geq \theta$. Using a Monte Carlo algorithm (say, simulating the geological history of the area), you can determine $X_i$ up to some error $\epsilon$. This translates to a two-sided error algorithm.

You can also think of computation in general as having two-sided error. Hardware errors occur with extremely low probability, and they can affect the answer in every which way.


Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez) I'm learning the initialization methods for Lloyd's algorithm. And I have a hard thing finding examples where Kmeans++ works better than Gonzalez and where the reverse is true so Gonzalez works better than Kmeans++. Does anyone have an example input (Pointset and value k) for these two scenarios?

Partial Answer:
Let us construct an instance where k-means++ initialization performs better than the Gonzalez initialization.
Consider the real line. Place $n$ points at the origin, i.e., position $0$. Place $n$ points at the position $1$. Lastly, place $1$ point at the position $n^{1/4}$. Let us cluster this pointset with $2$ clusters, i.e., $k = 2$.
In the optimal clustering, one center is placed at each of the two positions $0$ and $1$. The optimal k-means cost would be $\Theta(\sqrt{n})$ since the cost of $2n$ points at positions $0$ and $1$ is exactly $0$ and the cost of point at position $n^{1/4}$ is at most $\sqrt{n}$.
With the Gonzalez algorithm, only the following two center sets are possible (you can try this your own):

Center set where one center is at position $0$ and the other at $n^{1/4}$
Center set where one center is at position $1$ and the other at $n^{1/4}$

Without loss of generality, after this initialization, Lloyd's algorithm will cluster the points at positions $0$ and $1$ within the same cluster. And, the point at position $n^{1/4}$ would be clustered in a different cluster (singelton cluster). The $k$-means cost would be $\Theta(n)$.
With the k-means++ algorithm, the first center is chosen uniformly at random. With the high probability, the center would be chosen from positions $0$ or $1$. Without the loss of generality, suppose the first center is chosen from position $0$. Then, the probability that the second center will be chosen from position $1$ is $n/(n+\sqrt{n}) \geq 1/2$. And,  the probability that the second center will be chosen from position $n^{1/4}$ is at most  $\sqrt{n}/(n+\sqrt{n}) \leq 1/(2\sqrt{n})$. As you can see, the second center would be chosen from position $1$ with a high probability.
Therefore, with high probability, after this initialization, the $k$-means algorithm would open centers at positions $0$ and $1$. And, the $k$-means cost would be $\Theta(\sqrt{n})$. This cost is better than the cost with the Gonsalez algorithm that had cost $\Theta(n)$.


How to find contour lines for Appel's Hidden Line Removal Algorithm For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all assume you have access to OpenGL, unfortunately I do not have access to anything like that for the DCPU-16 (or any kind of hardware acceleration).

I found a fairly good description of Appel's algorithm on Google Books. However there is one issue I am having trouble figuring out.

  Appel defined contour line as an edge shared by a front-facing and a
  back-facing polygon, or unshared edge of a front facing polygon that
  is not part of a closed polyhedron. An edge shared by two front-facing
  polygons causes no change in visibility and therefore is not a contour
  line. In Fig. 8.4, edges AB, EF, PC, GK and CH are contour lines,
  whereas edges ED, DC and GI are not.

I understand the rules of the algorithm and how it works once you have your contour lines, however I do not understand is what I need to do to determine if a edge is "shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron" from a coding point of view. I can look at a shape and I can know what lines are contour lines in my head but I don't have a clue on how to transfer that "understanding" in to a coded algorithm.

Update

I have made some progress in determining contour lines. I found these two lecture notes from a University of Buffalo class on computer graphics.

  Consider the edges. These fall into three categories.

  An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored.
  An edge joining two potentially-visible faces is called a 'material edge' and will require further processing.
  An edge joining a potentially-visible face and an invisible face is a special case of a 'material edge' and is also called a 'contour
  edge'.

Using the above two pieces of information I am able to get closer to being able to write this out as code, but I still have a long way to go.

For the "-facing" rule to hold, you must make sure that all faces are properly oriented. Use the right-hand rule for instance, that means that the vertices of a face should be numbered in such a way that a positive rotation in the plane of the face corresponds to a normal pointing outside of the polyhedron. (Got it ?) Or more simply, every face must come with its outward-pointing normal.

Dangling faces, i.e. not belonging to a closed polyhedron can be seen as having an undeterminate orientation.

Now computing the parts of an edge which are hidden by a contour polygon is the main course. This problem is very close to that of clipping a line segment by a polygonal window in 2D. First consider the line of support of the line segment and find intersections with the polygon. By using a parity rule, you can easily determine the parts inside and outside the polygon.


Use Dijkstra to find negative cycles in a graph I will state the problem:

  Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph.

So, I saw the runtime, and I immediately said we need to use Dijsktra's implementation with a fibonacci heap.
I suggested the following:

  Run dijkstra, and mark the distances array as $d$. -- $O(|E| + |V|log|V|)$
  Do relax on each edge -- $O(|E|)$
  For each edge $<u,v> \in E$: -- $O(|E|)$

  3.1 if ( $d[v] < d[u] + w(<u,v>)$), report "negative cycle".
  report "No negative cycles"

Would this work?

No, it won't work.  If your graph has a negative weight edge and Dijkstra computes the shortest paths wrong, then it might be possible to relax an edge (to make the shortest paths correct) even though there is no negative-weight cycle in the graph.


Why reverse pipeline stages in cycle-level simulator? In pipeline simulator exercise, it says that:

  Traversing the stages in backwards order simplifies the instruction flow through the pipeline.

Also, in gpgpu-sim source code, the stages are reversed (line 2442):

void shader_core_ctx::cycle()
{
    m_stats->shader_cycles[m_sid]++;
    writeback();
    execute();
    read_operands();
    issue();
    decode();
    fetch();
}

Why? What problem it solves? Can anyone elaborate a bit or give a pointer to books/papers on this particular "trick"?

Many thanks!

This solves the problem that, if you put them in "forward" order, an instruction can stream all the way from fetch to writeback in a single cycle of the emulator. An other solution is explicitly emulating the clocked logic between the stages as it would exist in hardware, but it takes more effort that way. Running the stages in reverse is a simple trick that also ensures that instructions properly "wait" at the boundaries between stages.


Brzozowki's algorithm doesn't work for this corner case I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:

In this DFA, $S_0$ and $S_1$ are nondistinguishable and should be merged after minimization, but they are not.
The process of minimization is like this:

I tried to find out why by reading @Hendrik Jan's proof here, Proof of Brzozowski's algorithm for DFA minimization?

However, I find that this case bypasses the proof, because that in the reversed DFA, the initial state $q_0$ cannot be reached by $q_0$ using any words (but initial state is always considered reachable and cannot be removed). So did I miss anything, or does Brzozowki's algorithm has any specification for this corner case?

(It bypasses the proof like this: in the second series of reversal-determinization, $S_0 = \{q_1\}$ and $S_1 = \{q_0, q_1\}$, for any $w$, $\delta(q_0, w)$ in $S_0$ iff $\delta(q_0, w)$ in $S1$, so we say $S_0
= S_1$, assuming all states can be reached by $\delta(q_0, w)$, but $\delta(q_0,w)$ will never be $q_0$)

the initial DFA I was working on:

I have looked into some other corner cases and have a tentative answer: when we are doing the determinization after reversal, there is a corner case where in the DFA before reversal, some states cannot be reached  by applying any word to the initial state (two possibilities: the initial state cannot go back to itself or we are adding a state as the new initial state, because when we are doing reversal, there are 2 or more final states). In these cases, two sets are considered the same set if the only differences between them are the "unreachable" states before reversal.

I think we can prove that by reversing the proof process in the link cited in the question.


Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space.

The original problem appears here,
however the solution uses $\lg n$ space.
A problem in my course required adjusting the algorithm such that we use constant space.

I thought of the following algorithm:

MyAlgorithm(root, num)
    min<-findMin(root)
    max<-findMax(root)
    while(min.key <= max.key && min != max)
        if((min.key + max.key)=num) return true
        if((min.key + max.key) < num)
            min<-successor(min)
        else
            max<-predeccessor(max)
    return false

According the CLRS book both predeccessor() and successor() functions time complexity depends on tree height which is $O(\lg n)$ in our case since red-black tree is balanced.

However, we have the while loop which theoretically can run almost n times.

For example, because the algorithm above is equivalent to searching for the number num in a sorted array, say we have this array and num<-3:
$$
1,2,3,4,5,6,7,8,9,10
$$
In this case we'll call predecessor(max) $8$ times which is almost $\Theta(n)$ or $\Theta((n-2)\lg n)=\Theta(n\lg n)$ asymptotically.

Am I wrong in my conclusions? How can I prove that the time complexity is indeed $\Theta(n)$?

So we are given a binary search tree $T$ (we, however, do not require it to be balanced). Also we are given an integer; let's call it target_number. We wish to query whether there are two distinct nodes in $T$ such that the sum of their values equals target_number. In order to do that, we need two functions: get_successor(x) and get_predecessor(x). Given a node x get_successor(x) returns the tree node whose value is larger than that of x and is the smallest such value. The definition of get_predecessor(x) is symmetric.

The algorithm is now (as in your question): point to the minimum node, and point to the maximum node. Compute the sum $S$ of the nodes pointed by the two pointers. If $S$ is less than the target number, move left pointer to its successor node. If $S$ is greater than the target number, move right pointer to its predecessor node. Otherwise, we have a match and return true.

query(root, target_number)
    left_finger  = the minimum node of the entire tree rooted at root
    right_finger = the maximum node of the entire tree rooted at root

    while left_finger != nil and right_finger != nil and left_finger != right_finger
        tentative_sum = left_finger.value + right_finger.value
        if tentative_sum < target_number
            left_finger = get_successor(left_finger)
        else if tentative_sum > target_number
            right_finger = get_predecessor(right_finger)
        else
            return true
    return false

Next, we need to give a strong argument that it runs, in fact, in $\Theta(n)$. Take a look at operation get_successor: If you start from the minimum node and visit the entire tree in successor order, you do $\Theta(n)$ work regardless the fact that get_successor runs in worst case $\mathcal{O}(\log n)$, and that is why: you visit each node at most three times: from the parent, returning from the left child and returning from the right child; we spend constant time at each node.

As you can see from the below diagram, each node x has at most 3 incoming arcs and has at most 3 outgoing arcs. Traversing each arc is $\Theta(1)$. So basically, if we start from a minimum node, and keep advancing to the successor nodes, we do essentially in-order traversal that is, however, iterative instead of recursive. Same argument for starting from the maximum node via get_predecessor.

Now, we do the same traversal but in "both directions" (the left_finger proceeds towards successor nodes and right_finger proceeds towards predecessor nodes, and we terminate (at latest) when the two fingers meet. Thus, running time is linear in tree size and space complexity constant since no recursion is involved.


Proving $S=SL\implies S=\emptyset$ Let $L\subseteq \Sigma^*$ such that $\{\epsilon\}\not\in L$. Then for any $S\subseteq \Sigma^*,
 S=SL\implies S=\emptyset$.

So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $0\le|w|\le |v|$ for some $v\in S$. Now $|w|\ne 0$, since $|w|=0\implies\{\epsilon\}=w\in S=SL\implies \{\epsilon\}=xy$ for some $x\in S$ and $y\in L\implies x=y=\{\epsilon\}\in L$ which contradicts that $\{\epsilon\}\not\in L$.
Thus $w\ne\{\epsilon\}$ and $\{\epsilon\}\not\in S$. So we have
\begin{align}
w \in S &\implies w\in SL\\
&\implies w=sl\;\text{for some}\; s\in S\; \text{and}\; l\in L\\
&\implies |w|=|s|+|l|
\end{align}
Here I'm stuck now. I think if I can show that $|l|=0$, then we can arrive at a contradiction.
Your help is highly appreciated.

You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.


How can Lagrange Multipliers and Penalty Method be applied to optimize algorithms? I have a programming assignment which I was told that is solvable with some DP algorithm. The question is a variant of LIS problem where at most $k$ exceptions (restarts) are allowed.
But I know that there is a better solution. My professor mentioned Lagrange Multipliers and giving a penalty for each restart. But after googling these terms I wasn't able to find out anything related to algorithms. Every article is about Calculus and function optimization.
I also read about them on Wikipedia but I can't figure out how to use them.
Is there a keyword that can describe better what I want to read?

This technique is called Lagrangian relaxation.

The regular $DP$ approach, where $DP[a][b]$ represents the length of the longest increasing subsequence that ends in the $a$'th number and restarts at most $b$ times, is $\mathcal{O}(nk \log n)$. For convenience we'll assume the last number is the largest, and therefore $DP[n][k]$ is the value we are looking for (if this isn't the case, append $\infty$ and after calculating the answer decrement it by $1$).

To optimize this, we'll select some $\lambda \in \mathbb{N}$ which represents the cost of every exception, and compute $DP'[a] = \max_{b} DP[a][b] - \lambda b$. This can be done in $\mathcal{O}(n \log n)$: first sort the values, and keep a range maximum data structure over them, with all positions $j$ initialised to $v_{j} = 0$. Assume the value at position $i$ is the $p_{i}$th in the sorted list of values. Then $DP'[i] = \max(1 + \max_{j < p_{i}} v_{j}, 1 - \lambda + \max_{j > p_{i}} v_{j})$, and we set $v_{p_{i}} = DP'[i]$.

What use is computing $\max_{b} DP[n][b] - \lambda b$ to us? Notice that as we increase $\lambda$, the optimal $b$ in the maximum cannot increase. Similarly as we decrease $\lambda$, the optimal $b$ cannot decrease. If $\lambda = 0$, it is optimal to take all elements to our subsequence, and if $\lambda = n$, it is optimal to have $0$ exceptions. If we can find $\lambda$ for which the optimal $b$ can be $k$, then $DP[n][b] = DP'[n] + \lambda b$. Further, if such $\lambda$ exists, we can do binary search for it, yielding a $\mathcal{O}(n \log^{2} n)$ algorithm.

Note that we can modify the $\mathcal{O}(n \log n)$ algorithm to calculate the minimum and maximum values of $b$ that achieve the maximum value with the specific $\lambda$ with no increase in complexity. We can always find a $\lambda$ for which $\min_{b} \leq k \leq \max_{b}$, but this doesn't guarantee that there exists some subsequence with $k$ exceptions achieving the maximum. However, if we can show that $DP[n][b]$ is concave, i.e. $DP[n][b+2] - DP[n][b+1] \leq DP[n][b+1] - DP[n][b]$, we get this result, as we know that $DP[n][\min_{b} + 1] \leq DP[n][\min_{b}] + \lambda$ (due to maximality), therefore $DP[n][\max_{b}] \leq DP[n][k] + (\max_{b} - k) \lambda$, hence $DP'[n] = DP[n][\max_{b}] - \lambda \max_{b} \leq DP[n][k] - \lambda k$ and there exists a subsequence with $k$ exceptions achieving the maximum.

EDIT: Here is a C++ program for finding a maximal subsequence in $\mathcal{O}(n \log^{2} n)$. I use a segment tree for the range maximum data structure.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 2 * (int)1e9;

pair<ll, pair<int, int>> combine(pair<ll, pair<int, int>> le, pair<ll, pair<int, int>> ri) {
    if (le.first < ri.first) swap(le, ri);
    if (ri.first == le.first) {
        le.second.first = min(le.second.first, ri.second.first);
        le.second.second = max(le.second.second, ri.second.second);
    }
    return le;
}

// Specialised range maximum segment tree
class SegTree {
    private:
        vector<pair<ll, pair<int, int>>> seg;
        int h = 1;

        pair<ll, pair<int, int>> recGet(int a, int b, int i, int le, int ri) const {
            if (ri <= a || b <= le) return {-INF, {INF, -INF}};
            else if (a <= le && ri <= b) return seg[i];
            else return combine(recGet(a, b, 2*i, le, (le+ri)/2), recGet(a, b, 2*i+1, (le+ri)/2, ri));
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            seg.resize(2*h, {-INF, {INF, -INF}});
        }
        void set(int i, pair<ll, pair<int, int>> off) {
            seg[i+h] = combine(seg[i+h], off);
            for (i += h; i > 1; i /= 2) seg[i/2] = combine(seg[i], seg[i^1]);
        }
        pair<ll, pair<int, int>> get(int a, int b) const {
            return recGet(a, b+1, 1, 0, h);
        }
};

// Binary searches index of v from sorted vector
int bins(const vector<int>& vec, int v) {
    int low = 0;
    int high = (int)vec.size() - 1;
    while(low != high) {
        int mid = (low + high) / 2;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Finds longest strictly increasing subsequence with at most k exceptions in O(n log^2 n)
vector<int> lisExc(int k, vector<int> vec) {
    // Compress values
    vector<int> ord = vec;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    for (auto& v : vec) v = bins(ord, v) + 1;

    // Binary search lambda
    int n = vec.size();
    int m = ord.size() + 1;
    int lambda_0 = 0;
    int lambda_1 = n;
    while(true) {
        int lambda = (lambda_0 + lambda_1) / 2;
        SegTree seg(m);
        if (lambda > 0) seg.set(0, {0, {0, 0}});
        else seg.set(0, {0, {0, INF}});

        // Calculate DP
        vector<pair<ll, pair<int, int>>> dp(n);
        for (int i = 0; i < n; ++i) {
            auto off0 = seg.get(0, vec[i]-1); // previous < this
            off0.first += 1;

            auto off1 = seg.get(vec[i], m-1); // previous >= this
            off1.first += 1 - lambda;
            off1.second.first += 1;
            off1.second.second += 1;

            dp[i] = combine(off0, off1);
            seg.set(vec[i], dp[i]);
        }

        // Is min_b <= k <= max_b?
        auto off = seg.get(0, m-1);
        if (off.second.second < k) {
            lambda_1 = lambda - 1;
        } else if (off.second.first > k) {
            lambda_0 = lambda + 1;
        } else {
            // Construct solution
            ll r = off.first + 1;
            int v = m;
            int b = k;
            vector<int> res;
            for (int i = n-1; i >= 0; --i) {
                if (vec[i] < v) {
                    if (r == dp[i].first + 1 && dp[i].second.first <= b && b <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1;
                        v = vec[i];
                    }
                } else {
                    if (r == dp[i].first + 1 - lambda && dp[i].second.first <= b-1 && b-1 <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1 - lambda;
                        v = vec[i];
                        --b;
                    }
                }
            }
            reverse(res.begin(), res.end());
            return res;
        }
    }
}

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

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    vector<int> ans = lisExc(k, vec);
    for (auto i : ans) cout << i+1 << ' ';
    cout << '\n';
}

EDIT2: Thanks to Jaehyun Koo over at Codeforces I now know how to show concavity. The following is a modified version of his proof.

Consider the array partitioning problem. In it we are given values $cost[A][B]$ representing the cost of interval $[a, b)$, and wish to partition the array into intervals $[0, x_{1}), [x_{1}, x_{2}), \dots, x_{k}, n)$. Let $DP[n][k]$ denote the maximum sum $\sum_{i = 0}^{k} cost[x_{i}][x_{i+1}]$, where $x_{0} = 0$, $x_{k+1} = n$. We claim that $DP[n][k]$ is concave if the costs are Monge, that is, for all $a \leq b \leq c \leq d$ we have $cost[a][d] + cost[b][c] \leq cost[a][c] + cost[b][d]$.

First we'll show that our problem is an instance of the array partitioning problem with Monge costs. Set $cost[a][b]$ to be the length of the longest increasing subsequence in the interval $[a, b)$. Then $DP[n][k]$ for this instance of the array partitioning problem equals $DP[n][k]$ for our longest increasing subsequence problem. It remains to show that the costs are Monge.

Choose $a \leq b \leq c \leq d$, and take any LIS $L_{a, d} = x_{1}, \dots, x_{cost[a][d]}$ in the interval $[a, d)$, and any LIS $L_{b, d} = y_{1}, \dots, y_{cost[b][c]}$ in the interval $[b, c)$. We will combine them into two increasing subsequences in the intervals $[a, c)$ and $[b, d)$ of equal total length. To do this, let $x_{i}$ be the first $x$ and $x_{j}$ be the last $x$ in $[b, c)$. If $x_{i} \leq y_{1}$, set $L_{a, c} = (x_{1}, \dots, x_{i-1}, y_{1}, \dots, y_{cost[b][c]})$, $L_{b, d} = (x_{i}, \dots, x_{cost[a][d]})$. If $x_{j} \geq y_{cost[b][c]}$ do the same reversed. Otherwise, exists some $t, h$ s.t. $y_{h} \leq x_{t} \leq y_{h+1}$. Then set $L_{a, c} = (x_{1}, \dots, x_{t}, y_{h+1}, \dots, y_{cost[b, c]})$ and $L_{b, d} = (y_{1}, \dots, y_{h}, x_{t+1}, \dots, x_{cost[a, d]})$. Hence our cost array is Monge.

Now we'll show that the array partitioning problem with Monge cost is concave. Note that $DP[n][k+2] - DP[n][k+1] \leq DP[n][k+1] - DP[n][k]$ is the same inequality as $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$. Take any partitions $x_{0}, \dots, x_{k+3}$ and $y_{0}, \dots, y_{k+1}$ with values $DP[n][k+2]$ and $DP[n][k]$ respectively. Take any $0 \leq i \leq k$ such that $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$. Such $i$ always exists, as some interval $[y_{i}, y_{i+1}]$ must be the first such that the last $x$ before the end of the interval, $x_{j+2} \leq y_{i+1}$ has $j \geq i$, thus $x_{i+2} \leq x_{j+2} \leq y_{i+1}$ and $y_{i} \leq x_{i+1}$ as otherwise the interval $[y_{i-1}, y_{i}]$ would contain $x_{i+1}$ contradicting the minimality of $i$.

We make the partitions $y_{0}, \dots, y_{i}, x_{i+2}, \dots, x_{k+3}$ and $x_{0}, \dots, x_{i+1}, y_{i+1}, \dots, y_{k+1}$, both of length $k+1$. What is the difference in total value? Most terms cancel, but in the sum of values of the original we have $cost[x_{i+1}][x_{i+2}]$ and $cost[y_{i}][y_{i+1}]$, while in the new one we have $cost[y_{i}][x_{i+2}]$ and $cost[x_{i+1}][y_{i+1}]$. But since $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$, by the Monge property $cost[y_{i}][y_{i+1}] + cost[x_{i+1}][x_{i+2}] \leq cost[y_{i}][x_{i+2}] + cost[x_{i+1}][y_{i+1}]$, hence the total value can only increase, and $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$.


How is average precision related to the precision-recall curve? As background, in Information Retrieval, there are many metrics to assess how well search results are retrieving information.

A simple one is precision, where we calculate the fraction of documents returned that are relevant to our query. There is a second (or more general?) metric, precision@K: For a ranked result set, we calculate the fraction of documents at rank $k$ or higher which are relevant. So if the first document is relevant, the second is not, and the third is, then precision@3 is 1/3.

On to average precision. As I understand it (thanks in part to this), for this we get the rank of every relevant document in the result set, and then average the precision@k values at each of those ranks. It's even clearer if you look at my link.

Ok, my question: Both Wikipedia (here) and my IR book give the same explanation I gave, but then they start talking about precision-recall curves. My understanding of precision-recall curves is from machine learning, but I assume the concept is similar: You plot precision and recall against each other (on the x and y axis), showing how a decrease in one leads to an increase in the other.

I don't see how that relates to average precision, which is only a metric of precision and not of recall.

Wikipedia says: Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision p(r) as a function of recall r. Average precision computes the average value of p(r) over the interval from r=0 to r=1.

If I had to guess, it seems like they're describing calculating both average precision and average recall for every rank, or something. But if so it's confusing that they'd put it under Average Precision, and I'm very unsure of my interpretation.

So, how is average precision related to precision-recall graphs? It probably goes without saying that any other tips on understanding that Wikipedia section are also humbly appreciated.

Let $p(r)$ be the best precision which can be achieved at recall $r$. The average precision is
$$ p_{avg} = \int_0^1 p(r) \, dr. $$
Let $r(p)$ be the best recall which can be achieved at precision $p$. The average recall is
$$ r_{avg} = \int_0^1 r(p) \, dp. $$
Notice that the functions $p(r)$ and $r(p)$ are inverses of one another.

We can express these quantities using the function $\chi(p,r)$, which is 1 if precision $p$ and recall $r$ are achievable at the same time, and 0 otherwise.
We have $p(r) = \int_0^1 \chi(p,r) \, dp$, and so
$$ p_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dp dr. $$
Similarly, $r(p) = \int_0^1 \chi(p,r) \, dr$, and so
$$ r_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dr dp. $$
As a consequence, $p_{avg} = r_{avg}$.

Yet another interpretation of this common quantity is the area below the precision–recall curve. It is also the area below the ROC curve.


Both a language and its complement are not context free Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?

Yes, there is.
Consider the language $L = \{a^p \mid p \text{ is prime}\}$ which is not contextfree, neither is its complement. Both statements are very easy to check via Pumping-Lemma.